mlsanityData to 14 Oct 2026

Q-Learning with Fine-Grained Gap-Dependent Regret

arXiv 2510.06647 ↗First posted 8 Oct 2025stat.ML cs.LGcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study fine-grained gap-dependent regret bounds for model-free reinforcement learning in episodic tabular Markov Decision Processes. Existing model-free algorithms achieve minimax worst-case regret, but their gap-dependent bounds remain coarse and fail to fully capture the structure of suboptimality gaps. We address this limitation by establishing fine-grained gap-dependent regret bounds for both UCB-based and non-UCB-based algorithms. In the UCB-based setting, we develop a novel analytical framework that explicitly separates the analysis of optimal and suboptimal state-action pairs, yielding the first fine-grained regret upper bound for UCB-Hoeffding (Jin et al., 2018). To highlight the generality of this framework, we introduce ULCB-Hoeffding, a new UCB-based algorithm inspired by AMB (Xu et al.,2021) but with a simplified structure, which enjoys fine-grained regret guarantees and empirically outperforms AMB. In the non-UCB-based setting, we revisit the only known algorithm AMB, and identify two key issues in its algorithm design and analysis: improper truncation in the Q-updates and violation of the martingale difference condition in its concentration argument. We propose a refined version of AMB that addresses these issues, establishing the first rigorous fine-grained gap-dependent regret for a non-UCB-based method, with experiments demonstrating improved performance over AMB.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 42 of its 50 references that are in the map. First posted on arXiv 8 Oct 2025.

Builds on

42 of 50 references.

Closest ancestors · 3

Same direction, newest first

  1. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning5 Jun
  2. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition10 Oct
  3. 2024Achieving Constant Regret in Linear Markov Decision Processes16 Apr

Other references · 39

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  4. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  5. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  6. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  7. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  8. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  9. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  10. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  11. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  12. 2020Q-learning with Logarithmic Regretcited by 60
27 more
  1. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  2. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
  3. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
  4. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  5. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 43
  6. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  7. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  8. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  9. 2018Exploration in Structured Reinforcement Learningcited by 34
  10. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  11. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 34
  12. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  13. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
  14. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
  15. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  16. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 19
  17. 2023Federated Q-Learning: Linear Regret Speedup with Low Communication Costcited by 19
  18. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 18
  19. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  20. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  21. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  22. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  23. 2024Federated Q-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Costcited by 10
  24. 2018Variance Reduction Methods for Sublinear Reinforcement Learningcited by 6
  25. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 6
  26. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  27. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2026Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning
  2. 2025Tail Distribution of Regret in Optimistic Reinforcement Learning
  3. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism
  4. 2026Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation
  5. 2024Optimistic Q-learning for average reward and episodic reinforcement learning
  6. 2025Provably Efficient and Agile Randomized Q-Learning
  7. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  8. 2026Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning