mlsanityData to 7 Oct 2026

Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap

arXiv 2102.04692 ↗First posted 9 Feb 2021cs.LGcited by 48

Not on the map. Why?

Abstract (arXiv)

This paper presents a new model-free algorithm for episodic finite-horizon Markov Decision Processes (MDP), Adaptive Multi-step Bootstrap (AMB), which enjoys a stronger gap-dependent regret bound. The first innovation is to estimate the optimal Q-function by combining an optimistic bootstrap with an adaptive multi-step Monte Carlo rollout. The second innovation is to select the action with the largest confidence interval length among admissible actions that are not dominated by any other actions. We show when each state has a unique optimal action, AMB achieves a gap-dependent regret bound that only scales with the sum of the inverse of the sub-optimality gaps. In contrast, Simchowitz and Jamieson (2019) showed all upper-confidence-bound (UCB) algorithms suffer an additional Omegaleft(fracSDeltaminright) regret due to over-exploration where Deltamin is the minimum sub-optimality gap and S is the number of states. We further show that for general MDPs, AMB suffers an additional frac|Zmul|Deltamin regret, where Zmul is the set of state-action pairs (s,a)'s satisfying a is a non-unique optimal action for s. We complement our upper bound with a lower bound showing the dependency on frac|Zmul|Deltamin is unavoidable for any consistent algorithm. This lower bound also implies a separation between reinforcement learning and contextual bandits.

Key facts. Cited by 48 papers in the map (data through 7 Oct 2026). Builds on 16 of its 26 references that are in the map. First posted on arXiv 9 Feb 2021.

Builds on

16 of 26 references.

References · 16

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2019Introduction to Multi-Armed Banditscited by 475
  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. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  8. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  9. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  10. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  11. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  12. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
4 more
  1. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  2. 2020Q-learning with Logarithmic Regretcited by 59
  3. 2018Exploration in Structured Reinforcement Learningcited by 34
  4. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 13; 2023: 6; 2024: 4; 2025: 10; 2026: 3.

48 papers.

Sort:

By area:

  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  2. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  3. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  4. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  5. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  6. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  7. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  8. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  9. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  10. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  11. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  12. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
36 more
  1. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  2. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  3. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  4. 2023Best of Both Worlds Policy Optimizationcited by 17
  5. 2021Provably Efficient Multi-Task Reinforcement Learning with Model Transfercited by 16
  6. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
  7. 2021Can Q-Learning be Improved with Advice?cited by 13
  8. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  9. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
  10. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  11. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  12. 2022Logarithmic regret bounds for continuous-time average-reward Markov decision processescited by 7
  13. 2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7
  14. 2025Automatic Reward Shaping from Confounded Offline Datacited by 6
  15. 2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5
  16. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  17. 2022Cooperative Online Learning in Stochastic and Adversarial MDPscited by 4
  18. 2024Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysiscited by 4
  19. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  20. 2022Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regretcited by 3
  21. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  22. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  23. 2021Query-Reward Tradeoffs in Multi-Armed Banditscited by 1
  24. 2023Robust Knowledge Transfer in Tiered Reinforcement Learningcited by 1
  25. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
  26. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  27. 2026PlanningBench: Generating Scalable and Verifiable Planning Data for Evaluating and Training Large Language Modelscited by 1
  28. 2022Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamicscited by 0
  29. 2024A Fast Convergence Theory for Offline Decision Makingcited by 0
  30. 2024State-free Reinforcement Learningcited by 0
  31. 2025Logarithmic Regret for Nonlinear Controlcited by 0
  32. 2025Multi-Fidelity Hybrid Reinforcement Learning via Information Gain Maximizationcited by 0
  33. 2025Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approachcited by 0
  34. 2025Tail Distribution of Regret in Optimistic Reinforcement Learningcited by 0
  35. 2026On-line Learning in Tree MDPs by Treating Policies as Bandit Armscited by 0
  36. 2026Optimal Multi-Reward Reinforcement Learningcited by 0