# Adaptive Sampling for Best Policy Identification in Markov Decision Processes

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2020.

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

- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs](https://mlsanity.com/paper/2203.09251/) (2022)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [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)
- [Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning](https://mlsanity.com/paper/2206.00796/) (2022)
- [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)
- [Preference-based Pure Exploration](https://mlsanity.com/paper/2412.02988/) (2024)
- [Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Model](https://mlsanity.com/paper/2506.00286/) (2025)
- [Best Policy Identification in Linear MDPs](https://mlsanity.com/paper/2208.05633/) (2022)
- [Optimal Best Arm Identification with Fixed Confidence in Restless Bandits](https://mlsanity.com/paper/2310.13393/) (2023)
- [Policy Testing in Markov Decision Processes](https://mlsanity.com/paper/2505.15342/) (2025)
- [Asymptotically Optimal Sequential Testing with Markovian Data](https://mlsanity.com/paper/2602.17587/) (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)
- [Towards Optimal Policy Improvement](https://mlsanity.com/paper/2610.01566/) (2026)

## Abstract (arXiv)

We investigate the problem of best-policy identification in discounted Markov Decision Processes (MDPs) when the learner has access to a generative model. The objective is to devise a learning algorithm returning the best policy as early as possible. We first derive a problem-specific lower bound of the sample complexity satisfied by any learning algorithm. This lower bound corresponds to an optimal sample allocation that solves a non-convex program, and hence, is hard to exploit in the design of efficient algorithms. We then provide a simple and tight upper bound of the sample complexity lower bound, whose corresponding nearly-optimal sample allocation becomes explicit. The upper bound depends on specific functionals of the MDP such as the sub-optimality gaps and the variance of the next-state value function, and thus really captures the hardness of the MDP. Finally, we devise KLB-TS (KL Ball Track-and-Stop), an algorithm tracking this nearly-optimal allocation, and provide asymptotic guarantees for its sample complexity (both almost surely and in expectation). The advantages of KLB-TS against state-of-the-art algorithms are discussed and illustrated numerically.