# On Regret with Multiple Best Arms

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

## Key facts

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

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

- [Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces](https://mlsanity.com/paper/2207.05849/) (2022)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [Efficient Sequential Decision Making with Large Language Models](https://mlsanity.com/paper/2406.12125/) (2024)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Pareto Regret Analyses in Multi-objective Multi-armed Bandit](https://mlsanity.com/paper/2212.00884/) (2022)
- [Norm-Agnostic Linear Bandits](https://mlsanity.com/paper/2205.01257/) (2022)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026)
- [Infinite Action Contextual Bandits with Reusable Data Exhaust](https://mlsanity.com/paper/2302.08551/) (2023)
- [Graph Learning Is Suboptimal in Causal Bandits](https://mlsanity.com/paper/2510.16811/) (2025)
- [Max-Utility Based Arm Selection Strategy For Sequential Query Recommendations](https://mlsanity.com/paper/2108.13810/) (2021)
- [Improving Sequential Query Recommendation with Immediate User Feedback](https://mlsanity.com/paper/2205.06297/) (2022)
- [Complexity Analysis of a Countable-armed Bandit Problem](https://mlsanity.com/paper/2301.07243/) (2023)
- [Exploration Unbound](https://mlsanity.com/paper/2407.12178/) (2024)
- [Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity](https://mlsanity.com/paper/2609.38659/) (2026)

## Abstract (arXiv)

We study a regret minimization problem with the existence of multiple best/near-optimal arms in the multi-armed bandit setting. We consider the case when the number of arms/actions is comparable or much larger than the time horizon, and make no assumptions about the structure of the bandit instance. Our goal is to design algorithms that can automatically adapt to the unknown hardness of the problem, i.e., the number of best arms. Our setting captures many modern applications of bandit algorithms where the action space is enormous and the information about the underlying instance/structure is unavailable. We first propose an adaptive algorithm that is agnostic to the hardness level and theoretically derive its regret bound. We then prove a lower bound for our problem setting, which indicates: (1) no algorithm can be minimax optimal simultaneously over all hardness levels; and (2) our algorithm achieves a rate function that is Pareto optimal. With additional knowledge of the expected reward of the best arm, we propose another adaptive algorithm that is minimax optimal, up to polylog factors, over all hardness levels. Experimental results confirm our theoretical guarantees and show advantages of our algorithms over the previous state-of-the-art.