mlsanityData to 7 Oct 2026

Planning in Markov Decision Processes with Gap-Dependent Sample Complexity

arXiv 2006.05879 ↗First posted 10 Jun 2020cs.LG stat.MLcited by 34

Not on the map. Why?

Abstract (arXiv)

We propose MDP-GapE, a new trajectory-based Monte-Carlo Tree Search algorithm for planning in a Markov Decision Process in which transitions have a finite support. We prove an upper bound on the number of calls to the generative models needed for MDP-GapE to identify a near-optimal action with high probability. This problem-dependent sample complexity result is expressed in terms of the sub-optimality gaps of the state-action pairs that are visited during exploration. Our experiments reveal that MDP-GapE is also effective in practice, in contrast with other algorithms with sample complexity guarantees in the fixed-confidence setting, that are mostly theoretical.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). First posted on arXiv 10 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 5; 2024: 6; 2025: 8; 2026: 7.

34 papers.

Sort:

By area:

  1. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  2. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  3. 2023Fast Rates for Maximum Entropy Explorationcited by 32
  4. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  5. 2023Towards Theoretical Understanding of Inverse Reinforcement Learningcited by 21
  6. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  7. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  8. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  9. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
  10. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  11. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  12. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
22 more
  1. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  2. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  3. 2025SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfercited by 8
  4. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 5
  5. 2025Adaptive Exploration for Multi-Reward Multi-Policy Evaluationcited by 5
  6. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 4
  7. 2024Inverse Reinforcement Learning with Sub-optimal Expertscited by 4
  8. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  9. 2023Optimal Best Arm Identification with Fixed Confidence in Restless Banditscited by 3
  10. 2025Efficient Learning for Entropy-Regularized Markov Decision Processes via Multilevel Monte Carlocited by 3
  11. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  12. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  13. 2025Policy Testing in Markov Decision Processescited by 1
  14. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  15. 2026Second-Order Smooth Planning with Optimal-Transport Bellman Smoothingcited by 1
  16. 2024State-free Reinforcement Learningcited by 0
  17. 2026An Efficient Algorithm for Thresholding Monte Carlo Tree Searchcited by 0
  18. 2026Asymptotically Optimal Sequential Testing with Markovian Datacited by 0
  19. 2026On-line Learning in Tree MDPs by Treating Policies as Bandit Armscited by 0
  20. 2026Theoretical Foundations of max@k Reinforcement Learningcited by 0
  21. 2026Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identificationcited by 0
  22. 2026Provably Safe Sim-to-Real Transfercited by 0