# An Optimal Elimination Algorithm for Learning a Best Arm

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

## Key facts

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

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

- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Vector Optimization with Stochastic Bandit Feedback](https://mlsanity.com/paper/2110.12311/) (2021)
- [Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learning](https://mlsanity.com/paper/2211.12004/) (2022)
- [Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization](https://mlsanity.com/paper/2307.02108/) (2023)
- [Approximate Top-m Arm Identification with Heterogeneous Reward Variances](https://mlsanity.com/paper/2204.05245/) (2022)
- [Optimal Streaming Algorithms for Multi-Armed Bandits](https://mlsanity.com/paper/2410.17835/) (2024)
- [ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits](https://mlsanity.com/paper/2210.01860/) (2022)
- [Maximal-Capacity Discrete Memoryless Channel Identification](https://mlsanity.com/paper/2401.10204/) (2024)
- [Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits](https://mlsanity.com/paper/2412.00345/) (2024)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)

## Abstract (arXiv)

We consider the classic problem of (ε,δ)-PAC learning a best arm where the goal is to identify with confidence 1-δ an arm whose mean is an ε-approximation to that of the highest mean arm in a multi-armed bandit setting. This problem is one of the most fundamental problems in statistics and learning theory, yet somewhat surprisingly its worst-case sample complexity is not well understood. In this paper, we propose a new approach for (ε,δ)-PAC learning a best arm. This approach leads to an algorithm whose sample complexity converges to exactly the optimal sample complexity of (ε,δ)-learning the mean of n arms separately and we complement this result with a conditional matching lower bound. More specifically: