# On Finding the Largest Mean Among Many

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2013.

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

- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Best-Arm Identification in Correlated Multi-Armed Bandits](https://mlsanity.com/paper/2109.04941/) (2021)
- [Geometry of the Minimum Volume Confidence Sets](https://mlsanity.com/paper/2202.08180/) (2022)
- [A Batch Sequential Halving Algorithm without Performance Degradation](https://mlsanity.com/paper/2406.00424/) (2024)
- [Near Optimal Non-asymptotic Sample Complexity of 1-Identification](https://mlsanity.com/paper/2506.06978/) (2025)
- [Continuous Time Bandits With Sampling Costs](https://mlsanity.com/paper/2107.05289/) (2021)
- [UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity](https://mlsanity.com/paper/2511.22273/) (2025)
- [Exact Minimum-Volume Confidence Set Intersection for Multinomial Outcomes](https://mlsanity.com/paper/2601.18145/) (2026)
- [Box Thirding: Anytime Best Arm Identification under Insufficient Sampling](https://mlsanity.com/paper/2602.18186/) (2026)

## Abstract (arXiv)

Sampling from distributions to find the one with the largest mean arises in a broad range of applications, and it can be mathematically modeled as a multi-armed bandit problem in which each distribution is associated with an arm. This paper studies the sample complexity of identifying the best arm (largest mean) in a multi-armed bandit problem. Motivated by large-scale applications, we are especially interested in identifying situations where the total number of samples that are necessary and sufficient to find the best arm scale linearly with the number of arms. We present a single-parameter multi-armed bandit model that spans the range from linear to superlinear sample complexity. We also give a new algorithm for best arm identification, called PRISM, with linear sample complexity for a wide range of mean distributions. The algorithm, like most exploration procedures for multi-armed bandits, is adaptive in the sense that the next arms to sample are selected based on previous samples. We compare the sample complexity of adaptive procedures with simpler non-adaptive procedures using new lower bounds. For many problem instances, the increased sample complexity required by non-adaptive procedures is a polynomial factor of the number of arms.