Can Q-Learning be Improved with Advice?

Abstract

Despite rapid progress in theoretical reinforcement learning (RL) over the last few years, most of the known guarantees are worst-case in nature, failing to take advantage of structure that may be known a priori about a given RL problem at hand. In this paper we address the question of whether worst-case lower bounds for regret in online learning of Markov decision processes (MDPs) can be circumvented when information about the MDP, in the form of predictions about its optimal $Q$-value function, is given to the algorithm. We show that when the predictions about the optimal $Q$-value function satisfy a reasonably weak condition we call distillation, then we can improve regret bounds by replacing the set of state-action pairs with the set of state-action pairs on which the predictions are grossly inaccurate. This improvement holds for both uniform regret bounds and gap-based ones. Further, we are able to achieve this property with an algorithm that achieves sublinear regret when given arbitrary predictions (i.e., even those which are not a distillation). Our work extends a recent line of work on algorithms with predictions, which has typically focused on simple online problems such as caching and scheduling, to the more complex and general problem of reinforcement learning.

References in corpus (22)

• Transfer Learning in Deep Reinforcement Learning: A Survey
• Optimization, Learning, and Games with Predictable Sequences
• Improving Online Algorithms via ML Predictions
• Reinforcement Learning in Healthcare: A Survey
• Sim-to-Real Robot Learning from Pixels with Progressive Nets
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Minimax Regret Bounds for Reinforcement Learning
• Revenue Optimization with Approximate Bid Predictions
• Scheduling with Predictions and the Price of Misprediction
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Is Q-learning Provably Efficient?
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Stochastic bandits robust to adversarial corruptions
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Accelerating Optimization via Adaptive Prediction
• Online Learning with Imperfect Hints
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs
• Provably Efficient Multi-Task Reinforcement Learning with Model Transfer
• The Effect of Q-function Reuse on the Total Regret of Tabular, Model-Free, Reinforcement Learning