mlsanityData to 7 Oct 2026

Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs

arXiv 2506.06521 ↗First posted 6 Jun 2025cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

We consider the gap-dependent regret bounds for episodic MDPs. We show that the Monotonic Value Propagation (MVP) algorithm achieves a variance-aware gap-dependent regret bound of tildeOleft(left(sumDeltah(s,a)>0 fracH2 log K land mathttVarmaxcDeltah(s,a) +sumDeltah(s,a)=0frac H2 land mathttVarmaxcDeltamin + SAH4 (S lor H) right) log Kright), where H is the planning horizon, S is the number of states, A is the number of actions, and K is the number of episodes. Here, Deltah(s,a) =Vh^* (a) - Qh^* (s, a) represents the suboptimality gap and Deltamin := minDeltah (s,a) > 0 Deltah(s,a). The term mathttVarmaxc denotes the maximum conditional total variance, calculated as the maximum over all (π, h, s) tuples of the expected total variance under policy π conditioned on trajectories visiting state s at step h. mathttVarmaxc characterizes the maximum randomness encountered when learning any (h, s) pair. Our result stems from a novel analysis of the weighted sum of the suboptimality gap and can be potentially adapted for other algorithms. To complement the study, we establish a lower bound of Omega left( sumDeltah(s,a)>0 fracH2 land mathttVarmaxcDeltah(s,a)· log Kright), demonstrating the necessity of dependence on mathttVarmaxc even when the maximum unconditional total variance (without conditioning on (h, s)) approaches zero.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 43 of its 59 references that are in the map. First posted on arXiv 6 Jun 2025.

Builds on

43 of 59 references.

References · 43

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2018Top-K Off-Policy Correction for a REINFORCE Recommender Systemcited by 181
  7. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  8. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  9. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  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. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
31 more
  1. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  2. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  3. 2020Q-learning with Logarithmic Regretcited by 59
  4. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  5. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  6. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  7. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  8. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  9. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  10. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  11. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  12. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  13. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  14. 2018Exploration in Structured Reinforcement Learningcited by 34
  15. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  16. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  17. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  18. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  19. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  20. 2018Deep Reinforcement Learning for Dynamic Treatment Regimes on Medical Registry Datacited by 23
  21. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  22. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  23. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  24. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  25. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  26. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  27. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  28. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  29. 2022Variance-Aware Sparse Linear Banditscited by 11
  30. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  31. 2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  2. 2026On-line Learning in Tree MDPs by Treating Policies as Bandit Armscited by 0
  3. 2026Optimal Multi-Reward Reinforcement Learningcited by 0