mlsanityData to 7 Oct 2026

Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition

arXiv 2410.07574 ↗First posted 10 Oct 2024stat.ML cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

We study the gap-dependent bounds of two important algorithms for on-policy Q-learning for finite-horizon episodic tabular Markov Decision Processes (MDPs): UCB-Advantage (Zhang et al. 2020) and Q-EarlySettled-Advantage (Li et al. 2021). UCB-Advantage and Q-EarlySettled-Advantage improve upon the results based on Hoeffding-type bonuses and achieve the almost optimal √T-type regret bound in the worst-case scenario, where T is the total number of steps. However, the benign structures of the MDPs such as a strictly positive suboptimality gap can significantly improve the regret. While gap-dependent regret bounds have been obtained for Q-learning with Hoeffding-type bonuses, it remains an open question to establish gap-dependent regret bounds for Q-learning using variance estimators in their bonuses and reference-advantage decomposition for variance reduction. We develop a novel error decomposition framework to prove gap-dependent regret bounds of UCB-Advantage and Q-EarlySettled-Advantage that are logarithmic in T and improve upon existing ones for Q-learning algorithms. Moreover, we establish the gap-dependent bound for the policy switching cost of UCB-Advantage and improve that under the worst-case MDPs. To our knowledge, this paper presents the first gap-dependent regret analysis for Q-learning using variance estimators and reference-advantage decomposition and also provides the first gap-dependent analysis on policy switching cost for Q-learning.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 48 of its 67 references that are in the map. First posted on arXiv 10 Oct 2024.

Builds on

48 of 67 references.

References · 48

  1. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 723
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2019A Survey of Autonomous Driving: Common Practices and Emerging Technologiescited by 373
  4. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  7. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  8. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  9. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  10. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  11. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  12. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
36 more
  1. 2017Device Placement Optimization with Reinforcement Learningcited by 84
  2. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  3. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  4. 2020Variance-Reduced Methods for Machine Learningcited by 79
  5. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  6. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  7. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  8. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  9. 2020Q-learning with Logarithmic Regretcited by 59
  10. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  11. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  12. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  13. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  14. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  15. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  16. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  17. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  18. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  19. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  20. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  21. 2018A Survey on Compiler Autotuning using Machine Learningcited by 40
  22. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  23. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  24. 2018Exploration in Structured Reinforcement Learningcited by 34
  25. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  26. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  27. 2018Learning to Optimize Join Queries With Deep Reinforcement Learningcited by 32
  28. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  29. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  30. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
  31. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  32. 2023Federated Q-Learning: Linear Regret Speedup with Low Communication Costcited by 19
  33. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  34. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
  35. 2024Federated Q-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Costcited by 9
  36. 2018Variance Reduction Methods for Sublinear Reinforcement Learningcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 6; 2026: 1.

8 papers.

  1. 2024In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before An Ongoing Trajectory Terminatescited by 7
  2. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  3. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  4. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  5. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  6. 2025Explainable reinforcement learning from human feedback to improve alignmentcited by 1
  7. 2025Tail Distribution of Regret in Optimistic Reinforcement Learningcited by 0
  8. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0