# Navigating to the Best Policy in Markov Decision Processes

arXiv: https://arxiv.org/abs/2106.02847 · HTML: https://mlsanity.com/paper/2106.02847/

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Sample Efficient Reinforcement Learning with REINFORCE](https://mlsanity.com/paper/2010.11364/) (2020)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [Active Exploration in Markov Decision Processes](https://mlsanity.com/paper/1902.11199/) (2019)
- [Adaptive Sampling for Best Policy Identification in Markov Decision Processes](https://mlsanity.com/paper/2009.13405/) (2020)
- [Provably Correct Optimization and Exploration with Non-linear Policies](https://mlsanity.com/paper/2103.11559/) (2021)
- [Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time](https://mlsanity.com/paper/1704.01869/) (2017)

## Built on by (most cited first, 29 of 29)

- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs](https://mlsanity.com/paper/2203.09251/) (2022)
- [Gap-Dependent Unsupervised Exploration for Reinforcement Learning](https://mlsanity.com/paper/2108.05439/) (2021)
- [Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition](https://mlsanity.com/paper/2410.07574/) (2024)
- [Towards Instance-Optimality in Online PAC Reinforcement Learning](https://mlsanity.com/paper/2311.05638/) (2023)
- [Adaptive Exploration for Multi-Reward Multi-Policy Evaluation](https://mlsanity.com/paper/2502.02516/) (2025)
- [Performative Policy Gradient: Optimality in Performative Reinforcement Learning](https://mlsanity.com/paper/2512.20576/) (2025)
- [MCTS-GEB: Monte Carlo Tree Search is a Good E-graph Builder](https://mlsanity.com/paper/2303.04651/) (2023)
- [Test-Time Regret Minimization in Meta Reinforcement Learning](https://mlsanity.com/paper/2406.02282/) (2024)
- [Model-Free Active Exploration in Reinforcement Learning](https://mlsanity.com/paper/2407.00801/) (2024)
- [Best Policy Identification in Linear MDPs](https://mlsanity.com/paper/2208.05633/) (2022)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)
- [Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/2506.06521/) (2025)
- [Optimal Best Arm Identification with Fixed Confidence in Restless Bandits](https://mlsanity.com/paper/2310.13393/) (2023)
- [Fair Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2408.17313/) (2024)
- [Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design](https://mlsanity.com/paper/2506.09508/) (2025)
- [Policy Testing in Markov Decision Processes](https://mlsanity.com/paper/2505.15342/) (2025)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [Asymptotically Optimal Sequential Testing with Markovian Data](https://mlsanity.com/paper/2602.17587/) (2026)
- [Robust Phi-Divergence MDPs](https://mlsanity.com/paper/2205.14202/) (2022)
- [Q-Learning with Fine-Grained Gap-Dependent Regret](https://mlsanity.com/paper/2510.06647/) (2025)
- [Minimax PAC Bounds for Learning in Exogenous Contextual MDPs](https://mlsanity.com/paper/2606.25170/) (2026)
- [Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback](https://mlsanity.com/paper/2605.23182/) (2026)
- [Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environments](https://mlsanity.com/paper/2608.21995/) (2026)
- [Cost-Aware Best-LLM Identification using Dueling Feedback](https://mlsanity.com/paper/2609.30360/) (2026)
- [Distinguish or Homogenize: Last-Chance Policy Identification and Risk-Budgeted Recovery under Irreversible Resource Depletion](https://mlsanity.com/paper/2609.36741/) (2026)
- [Average-Reward Policy Identification from a Single Continuing Trajectory](https://mlsanity.com/paper/2610.20486/) (2026)

## 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.