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

arXiv:2609.38659v1 Announce Type: cross Abstract: 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 ilde{O}Big(frac{K-A}{sqrt{KA}}sqrt{T} Big) minimax regret, where T is the total number of interactions and ilde O(dot) drops all constant and logarithmic factors, improving the previous ilde{O}(sqrt{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 ilde{O}(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 leq A leq K-1.

Related

• Mixture-Greedy for Online Generative Model Selection: Is UCB Necessary in Diversity-Aware Multi-Armed Bandits?
• Multi-Armed Bandits With Best-Action Queries
• Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits

Source: arXiv cs.AI | 2026-10-01