# Optimal Best Markovian Arm Identification with Fixed Confidence

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2019.

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

- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Federated Best Arm Identification with Heterogeneous Clients](https://mlsanity.com/paper/2210.07780/) (2022)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Performative Policy Gradient: Optimality in Performative Reinforcement Learning](https://mlsanity.com/paper/2512.20576/) (2025)
- [Learning to Detect an Odd Restless Markov Arm with a Trembling Hand](https://mlsanity.com/paper/2105.03603/) (2021)
- [Best Arm Identification in Restless Markov Multi-Armed Bandits](https://mlsanity.com/paper/2203.15236/) (2022)
- [Optimal Best Arm Identification with Fixed Confidence in Restless Bandits](https://mlsanity.com/paper/2310.13393/) (2023)
- [Asymptotically Optimal Sequential Testing with Markovian Data](https://mlsanity.com/paper/2602.17587/) (2026)
- [Sequential Community Mode Estimation](https://mlsanity.com/paper/2111.08535/) (2021)
- [Pure Exploration under Mediators' Feedback](https://mlsanity.com/paper/2308.15552/) (2023)
- [Pure Exploration with Infinite Answers](https://mlsanity.com/paper/2505.22473/) (2025)
- [Non-Asymptotic Analysis of (Sticky) Track-and-Stop](https://mlsanity.com/paper/2505.22475/) (2025)

## Abstract (arXiv)

We give a complete characterization of the sampling complexity of best Markovian arm identification in one-parameter Markovian bandit models. We derive instance specific nonasymptotic and asymptotic lower bounds which generalize those of the IID setting. We analyze the Track-and-Stop strategy, initially proposed for the IID setting, and we prove that asymptotically it is at most a factor of four apart from the lower bound. Our one-parameter Markovian bandit model is based on the notion of an exponential family of stochastic matrices for which we establish many useful properties. For the analysis of the Track-and-Stop strategy we derive a novel concentration inequality for Markov chains that may be of interest in its own right.