mlsanityData to 7 Oct 2026

Navigating to the Best Policy in Markov Decision Processes

arXiv 2106.02847 ↗First posted 5 Jun 2021stat.ML cs.LGcited by 28

Not on the map. Why?

Abstract (arXiv)

We investigate the classical active pure exploration problem in Markov Decision Processes, where the agent sequentially selects actions and, from the resulting system trajectory, aims at identifying the best policy as fast as possible. We propose a problem-dependent lower bound on the average number of steps required before a correct answer can be given with probability at least 1-δ. We further provide the first algorithm with an instance-specific sample complexity in this setting. This algorithm addresses the general case of communicating MDPs; we also propose a variant with a reduced exploration rate (and hence faster convergence) under an additional ergodicity assumption. This work extends previous results relative to the generative setting~citepmlr-v139-marjani21a, where the agent could at each step query the random outcome of any (state, action) pair. In contrast, we show here how to deal with the navigation constraints, induced by the online setting. Our analysis relies on an ergodic theorem for non-homogeneous Markov chains which we consider of wide interest in the analysis of Markov Decision Processes.

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). Builds on 20 of its 50 references that are in the map. First posted on arXiv 5 Jun 2021.

Builds on

20 of 50 references.

References · 20

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  2. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  3. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  4. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 116
  5. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  6. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  7. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  8. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  9. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  10. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  11. 2020Sample Efficient Reinforcement Learning with REINFORCEcited by 85
  12. 2020Adaptive Reward-Free Explorationcited by 77
8 more
  1. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  2. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 62
  3. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  4. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  5. 2019Active Exploration in Markov Decision Processescited by 27
  6. 2020Adaptive Sampling for Best Policy Identification in Markov Decision Processescited by 20
  7. 2021Provably Correct Optimization and Exploration with Non-linear Policiescited by 13
  8. 2017Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Timecited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 3; 2024: 4; 2025: 9; 2026: 6.

28 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. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  4. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
  5. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  6. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  7. 2023MCTS-GEB: Monte Carlo Tree Search is a Good E-graph Buildercited by 5
  8. 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
  9. 2024Model-Free Active Exploration in Reinforcement Learningcited by 5
  10. 2025Adaptive Exploration for Multi-Reward Multi-Policy Evaluationcited by 5
  11. 2022Best Policy Identification in Linear MDPscited by 4
  12. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
16 more
  1. 2025Performative Policy Gradient: Optimality in Performative Reinforcement Learningcited by 4
  2. 2023Optimal Best Arm Identification with Fixed Confidence in Restless Banditscited by 3
  3. 2024Fair Best Arm Identification with Fixed Confidencecited by 3
  4. 2025Pure Exploration with Feedback Graphscited by 3
  5. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  6. 2025Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Designcited by 3
  7. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  8. 2022Robust Phi-Divergence MDPscited by 1
  9. 2025Policy Testing in Markov Decision Processescited by 1
  10. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  11. 2026Minimax PAC Bounds for Learning in Exogenous Contextual MDPscited by 1
  12. 2026Asymptotically Optimal Sequential Testing with Markovian Datacited by 0
  13. 2026Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedbackcited by 0
  14. 2026Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environmentscited by 0
  15. 2026Cost-Aware Best-LLM Identification using Dueling Feedbackcited by 0
  16. 2026Distinguish or Homogenize: Last-Chance Policy Identification and Risk-Budgeted Recovery under Irreversible Resource Depletioncited by 0