# Optimal Best Arm Identification with Fixed Confidence

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

## Key facts

- Cited by 239 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2016.

## Built on by (most cited first, 30 of 239)

- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification](https://mlsanity.com/paper/2206.04646/) (2022)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [Open Problem: Optimal Best Arm Identification with Fixed Budget](https://mlsanity.com/paper/2303.00950/) (2023)
- [A/B/n Testing with Control in the Presence of Subpopulations](https://mlsanity.com/paper/2110.15573/) (2021)
- [Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs](https://mlsanity.com/paper/2203.09251/) (2022)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Information-Directed Selection for Top-Two Algorithms](https://mlsanity.com/paper/2205.12086/) (2022)
- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [On Speeding Up Language Model Evaluation](https://mlsanity.com/paper/2407.06172/) (2024)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Bandit Pareto Set Identification: the Fixed Budget Setting](https://mlsanity.com/paper/2311.03992/) (2023)
- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Bregman Deviations of Generic Exponential Families](https://mlsanity.com/paper/2201.07306/) (2022)
- [Dealing with Unknown Variances in Best-Arm Identification](https://mlsanity.com/paper/2210.00974/) (2022)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Vector Optimization with Stochastic Bandit Feedback](https://mlsanity.com/paper/2110.12311/) (2021)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Best Arm Identification with Fixed Budget: A Large Deviation Perspective](https://mlsanity.com/paper/2312.12137/) (2023)
- [Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identification](https://mlsanity.com/paper/2402.10592/) (2024)
- [Active Adaptive Experimental Design for Treatment Effect Estimation with Covariate Choices](https://mlsanity.com/paper/2403.03589/) (2024)
- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [Pure Exploration in Bandits with Linear Constraints](https://mlsanity.com/paper/2306.12774/) (2023)

## Abstract (arXiv)

We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the `Track-and-Stop' strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis.