# On the Optimal Sample Complexity for Best Arm Identification

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2015.

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

- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Variance-Dependent Best Arm Identification](https://mlsanity.com/paper/2106.10417/) (2021)
- [Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits](https://mlsanity.com/paper/2306.02208/) (2023)
- [On Elimination Strategies for Bandit Fixed-Confidence Identification](https://mlsanity.com/paper/2205.10936/) (2022)
- [Optimal Batched Best Arm Identification](https://mlsanity.com/paper/2310.14129/) (2023)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds](https://mlsanity.com/paper/2504.19952/) (2025)
- [Approximate Top-m Arm Identification with Heterogeneous Reward Variances](https://mlsanity.com/paper/2204.05245/) (2022)
- [PAC Best Arm Identification Under a Deadline](https://mlsanity.com/paper/2106.03221/) (2021)
- [Policy Testing in Markov Decision Processes](https://mlsanity.com/paper/2505.15342/) (2025)
- [Near Optimal Non-asymptotic Sample Complexity of 1-Identification](https://mlsanity.com/paper/2506.06978/) (2025)
- [A positive resolution of the gap-entropy conjecture](https://mlsanity.com/paper/2609.10529/) (2026)
- [Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits](https://mlsanity.com/paper/2306.01995/) (2023)
- [Protocols for Verifying Smooth Strategies in Bandits and Games](https://mlsanity.com/paper/2507.10567/) (2025)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)
- [Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification](https://mlsanity.com/paper/2609.13703/) (2026)

## Abstract (arXiv)

We study the best arm identification (BEST-1-ARM) problem, which is defined as follows. We are given n stochastic bandit arms. The ith arm has a reward distribution Di with an unknown mean μi. Upon each play of the ith arm, we can get a reward, sampled i.i.d. from Di. We would like to identify the arm with the largest mean with probability at least 1-δ, using as few samples as possible. We provide a nontrivial algorithm for BEST-1-ARM, which improves upon several prior upper bounds on the same problem. We also study an important special case where there are only two arms, which we call the sign problem. We provide a new lower bound of sign, simplifying and significantly extending a classical result by Farrell in 1964, with a completely new proof. Using the new lower bound for sign, we obtain the first lower bound for BEST-1-ARM that goes beyond the classic Mannor-Tsitsiklis lower bound, by an interesting reduction from Sign to BEST-1-ARM. We propose an interesting conjecture concerning the optimal sample complexity of BEST-1-ARM from the perspective of instance-wise optimality.