mlsanityData to 7 Oct 2026

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

arXiv 2609.38659 ↗First posted 29 Sep 2026stat.ML cs.AI cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

29 of 47 references.

References · 29

  1. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
  2. 2023SWE-bench: Can Language Models Resolve Real-World GitHub Issues?cited by 3,193
  3. 2024LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Codecited by 1,906
  4. 2023Automatic Prompt Optimization with "Gradient Descent" and Beam Searchcited by 628
  5. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  6. 2021Adapting to Misspecification in Contextual Banditscited by 81
  7. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  8. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  9. 2019Pure Exploration with Multiple Correct Answerscited by 60
  10. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  11. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  12. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
17 more
  1. 2019The True Sample Complexity of Identifying Good Armscited by 37
  2. 2017Good Arm Identification via Bandit Feedbackcited by 29
  3. 2020The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Armscited by 27
  4. 2021The Pareto Frontier of model selection for general Contextual Banditscited by 24
  5. 2025Adaptive LLM Routing under Budget Constraintscited by 21
  6. 2020On Regret with Multiple Best Armscited by 16
  7. 2021Bandits with many optimal armscited by 16
  8. 2018Pure Exploration in Infinitely-Armed Bandit Models with Fixed-Confidencecited by 15
  9. 2019Smoothness-Adaptive Contextual Banditscited by 15
  10. 2021Pareto Optimal Model Selection in Linear Banditscited by 14
  11. 2020Adaptation to the Range in K-Armed Banditscited by 12
  12. 2020Bandit algorithms: Letting go of logarithmic regret for statistical robustnesscited by 12
  13. 2019Polynomial Cost of Adaptation for X -Armed Banditscited by 9
  14. 2021From Finite to Countable-Armed Banditscited by 8
  15. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  16. 2025Optimal Best-Arm Identification under Fixed Confidence with Multiple Optimacited by 2
  17. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2

Built on by

Not cited yet.