# Bandits with many optimal arms

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 47 references that are in the map.
- First posted on arXiv 23 Mar 2021.

## Builds on (most cited first, 11 of 11)

- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [On Regret with Multiple Best Arms](https://mlsanity.com/paper/2006.14785/) (2020)
- [Pure Exploration in Infinitely-Armed Bandit Models with Fixed-Confidence](https://mlsanity.com/paper/1803.04665/) (2018)
- [Sample complexity of partition identification using multi-armed bandits](https://mlsanity.com/paper/1811.05654/) (2018)
- [Polynomial Cost of Adaptation for X -Armed Bandits](https://mlsanity.com/paper/1905.10221/) (2019)
- [Learning the distribution with largest mean: two bandit frameworks](https://mlsanity.com/paper/1702.00001/) (2017)

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

- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration](https://mlsanity.com/paper/2212.00333/) (2022)
- [Best Arm Identification for Stochastic Rising Bandits](https://mlsanity.com/paper/2302.07510/) (2023)
- [Active Ranking of Experts Based on their Performances in Many Tasks](https://mlsanity.com/paper/2306.02628/) (2023)
- [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026)
- [Non-Stationary Lipschitz Bandits](https://mlsanity.com/paper/2505.18871/) (2025)
- [Clustering Items through Bandit Feedback: Finding the Right Feature out of Many](https://mlsanity.com/paper/2503.11209/) (2025)
- [Bandits with Dynamic Arm-acquisition Costs](https://mlsanity.com/paper/2110.12118/) (2021)
- [Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2410.02994/) (2024)
- [Stochastic Sample Approximations of (Local) Moduli of Continuity](https://mlsanity.com/paper/2509.15368/) (2025)
- [Active Bipartite Ranking with Smooth Posterior Distributions](https://mlsanity.com/paper/2602.24263/) (2026)
- [InvEvolve: Evolving White-Box Inventory Policies via Large Language Models with Performance Guarantees](https://mlsanity.com/paper/2605.00369/) (2026)
- [Complexity Analysis of a Countable-armed Bandit Problem](https://mlsanity.com/paper/2301.07243/) (2023)
- [Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits](https://mlsanity.com/paper/2306.01995/) (2023)
- [Exploration Unbound](https://mlsanity.com/paper/2407.12178/) (2024)
- [The Statistical Benefits of Multiple Responses for Learning from Demonstrations](https://mlsanity.com/paper/2609.33291/) (2026)
- [Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity](https://mlsanity.com/paper/2609.38659/) (2026)

## Abstract (arXiv)

We consider a stochastic bandit problem with a possibly infinite number of arms. We write p^* for the proportion of optimal arms and Delta for the minimal mean-gap between optimal and sub-optimal arms. We characterize the optimal learning rates both in the cumulative regret setting, and in the best-arm identification setting in terms of the problem parameters T (the budget), p^* and Delta. For the objective of minimizing the cumulative regret, we provide a lower bound of order Omega(log(T)/(p^*Delta)) and a UCB-style algorithm with matching upper bound up to a factor of log(1/Delta). Our algorithm needs p^* to calibrate its parameters, and we prove that this knowledge is necessary, since adapting to p^* in this setting is impossible. For best-arm identification we also provide a lower bound of order Omega(exp(-cTDelta2 p^*)) on the probability of outputting a sub-optimal arm where c>0 is an absolute constant. We also provide an elimination algorithm with an upper bound matching the lower bound up to a factor of order log(T) in the exponential, and that does not need p^* or Delta as parameter. Our results apply directly to the three related problems of competing against the j-th best arm, identifying an ε good arm, and finding an arm with mean larger than a quantile of a known order.