# Can Q-Learning be Improved with Advice?

arXiv: https://arxiv.org/abs/2110.13052 · HTML: https://mlsanity.com/paper/2110.13052/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 57 references that are in the map.
- First posted on arXiv 25 Oct 2021.

## Builds on (most cited first, 30 of 32)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [Transfer Learning in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2009.07888/) (2020)
- [Closing the Sim-to-Real Loop: Adapting Simulation Randomization with Real World Experience](https://mlsanity.com/paper/1810.05687/) (2018)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Sim-to-Real Robot Learning from Pixels with Progressive Nets](https://mlsanity.com/paper/1610.04286/) (2016)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [Personalized HeartSteps: A Reinforcement Learning Algorithm for Optimizing Physical Activity](https://mlsanity.com/paper/1909.03539/) (2019)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [Revenue Optimization with Approximate Bid Predictions](https://mlsanity.com/paper/1706.04732/) (2017)
- [Taking a hint: How to leverage loss predictors in contextual bandits?](https://mlsanity.com/paper/2003.01922/) (2020)
- [Provably Efficient Multi-Task Reinforcement Learning with Model Transfer](https://mlsanity.com/paper/2107.08622/) (2021)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)
- [The Pareto Regret Frontier for Bandits](https://mlsanity.com/paper/1511.00048/) (2015)

## Built on by (most cited first, 13 of 13)

- [Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity](https://mlsanity.com/paper/2210.09579/) (2022)
- [Chasing Convex Bodies and Functions with Black-Box Advice](https://mlsanity.com/paper/2206.11780/) (2022)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions](https://mlsanity.com/paper/2307.10524/) (2023)
- [Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspective](https://mlsanity.com/paper/2502.19255/) (2025)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Learning-augmented Online Minimization of Age of Information and Transmission Costs](https://mlsanity.com/paper/2403.02573/) (2024)
- [Efficiently Solving Discounted MDPs with Predictions on Transition Matrices](https://mlsanity.com/paper/2502.15345/) (2025)
- [Robust Knowledge Transfer in Tiered Reinforcement Learning](https://mlsanity.com/paper/2302.05534/) (2023)
- [Out-of-Distribution-Aware Electric Vehicle Charging](https://mlsanity.com/paper/2311.05941/) (2023)
- [Safe Exploitative Play with Untrusted Type Beliefs](https://mlsanity.com/paper/2411.07679/) (2024)
- [Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approach](https://mlsanity.com/paper/2510.19528/) (2025)
- [Augmented Hypothesis Testing with Persona-Based LLM Simulations](https://mlsanity.com/paper/2609.24629/) (2026)

## Abstract (arXiv)

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.