# Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 47 references that are in the map.
- First posted on arXiv 29 Sep 2026.

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

- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms](https://mlsanity.com/paper/2002.10121/) (2020)
- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [Adaptive LLM Routing under Budget Constraints](https://mlsanity.com/paper/2508.21141/) (2025)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [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)
- [Smoothness-Adaptive Contextual Bandits](https://mlsanity.com/paper/1910.09714/) (2019)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Adaptation to the Range in K-Armed Bandits](https://mlsanity.com/paper/2006.03378/) (2020)
- [Bandit algorithms: Letting go of logarithmic regret for statistical robustness](https://mlsanity.com/paper/2006.12038/) (2020)
- [Polynomial Cost of Adaptation for X -Armed Bandits](https://mlsanity.com/paper/1905.10221/) (2019)
- [From Finite to Countable-Armed Bandits](https://mlsanity.com/paper/2105.10721/) (2021)
- [Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification](https://mlsanity.com/paper/2410.07533/) (2024)
- [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026)
- [Optimal Best-Arm Identification under Fixed Confidence with Multiple Optima](https://mlsanity.com/paper/2505.15643/) (2025)

## Abstract (arXiv)

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For K-armed bandits with A optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a tildeOBig(fracK-A√KA√T Big) minimax regret, where T is the total number of interactions and tilde O(·) drops all constant and logarithmic factors, improving the previous tildeO(√KT/A) regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of A up to tildeO(1) factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of K-armed bandits with A over the entire range of 1 ≤ A ≤ K-1.