mlsanityData to 7 Oct 2026

Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning

arXiv 2107.01264 ↗First posted 2 Jul 2021cs.LGcited by 33

Not on the map. Why?

Abstract (arXiv)

We provide improved gap-dependent regret bounds for reinforcement learning in finite episodic Markov decision processes. Compared to prior work, our bounds depend on alternative definitions of gaps. These definitions are based on the insight that, in order to achieve a favorable regret, an algorithm does not need to learn how to behave optimally in states that are not reached by an optimal policy. We prove tighter upper regret bounds for optimistic algorithms and accompany them with new information-theoretic lower bounds for a large class of MDPs. Our results show that optimistic algorithms can not achieve the information-theoretic lower bounds even in deterministic MDPs unless there is a unique optimal policy.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). Builds on 18 of its 38 references that are in the map. First posted on arXiv 2 Jul 2021.

Builds on

18 of 38 references.

References · 18

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  7. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  8. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  9. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  10. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  11. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  12. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
6 more
  1. 2020Q-learning with Logarithmic Regretcited by 59
  2. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  3. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  4. 2017Minimal Exploration in Structured Stochastic Banditscited by 40
  5. 2018Exploration in Structured Reinforcement Learningcited by 34
  6. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 8; 2023: 5; 2024: 7; 2025: 8; 2026: 2.

33 papers.

Sort:

By area:

  1. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
  2. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  3. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  4. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  5. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  6. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  7. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  8. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 29
  9. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  10. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  11. 2021Can Q-Learning be Improved with Advice?cited by 13
  12. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
21 more
  1. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  2. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  3. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  4. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  5. 2024Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysiscited by 4
  6. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  7. 2022Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regretcited by 3
  8. 2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
  9. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  10. 2024Graph Attention-based Reinforcement Learning for Trajectory Design and Resource Assignment in Multi-UAV Assisted Communicationcited by 2
  11. 2024Multiple-policy Evaluation via Density Estimationcited by 2
  12. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  13. 2023Robust Knowledge Transfer in Tiered Reinforcement Learningcited by 1
  14. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
  15. 2025Multi-User Contextual Cascading Bandits for Personalized Recommendationcited by 1
  16. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  17. 2024State-free Reinforcement Learningcited by 0
  18. 2025Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approachcited by 0
  19. 2025Tail Distribution of Regret in Optimistic Reinforcement Learningcited by 0
  20. 2026Multi-Agent Reinforcement Learning with Submodular Rewardcited by 0
  21. 2026Smaller Abstract State Spaces Enable Cross-Scale Generalization in Reinforcement Learningcited by 0