mlsanityData to 14 Oct 2026

Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs

arXiv 1905.03814 ↗First posted 9 May 2019cs.LG math.OC math.STcited by 105

Not on the map. Why?

Cited by 28 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the widetildeO(√HSAT)-minimax rate. The key technique in our analysis is a novel "clipped" regret decomposition which applies to a broad family of recent optimistic algorithms for episodic MDPs.

Key facts. Cited by 105 papers in the map (data through 14 Oct 2026). First posted on arXiv 9 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 32; 2022: 22; 2023: 16; 2024: 14; 2025: 15; 2026: 6.

105 papers.

Sort:

By area:

  1. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  2. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  3. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  4. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
  5. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  6. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  7. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 43
  8. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  9. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  10. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  11. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  12. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
38 more
  1. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  2. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  3. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  4. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 34
  5. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  6. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  7. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  8. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 31
  9. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  10. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  11. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  12. 2021Fast Rates for the Regret of Offline Reinforcement Learningcited by 26
  13. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 22
  14. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  15. 2023Replicable Reinforcement Learningcited by 21
  16. 2021When Is Generalizable Reinforcement Learning Tractable?cited by 20
  17. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  18. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 19
  19. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 18
  20. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 18
  21. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  22. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  23. 2021Provably Efficient Multi-Task Reinforcement Learning with Model Transfercited by 16
  24. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 15
  25. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
  26. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  27. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 15
  28. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  29. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  30. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  31. 2021Can Q-Learning be Improved with Advice?cited by 13
  32. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  33. 2021Confidence-Budget Matching for Sequential Budgeted Learningcited by 12
  34. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12
  35. 2021Adaptive Discretization in Online Reinforcement Learningcited by 12
  36. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  37. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 11
  38. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10

50 most cited of 105 All 105 (JSON)