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

arXiv:2609.38659 · stat.ML, cs.AI, cs.LG, math.ST, stat.ME, stat.TH · Submitted 2026-09-29 · Read on arXiv

stat.ML, cs.AI, cs.LG, math.ST, stat.ME, stat.TH

Submitted: 2026-09-29

Updated: 2026-10-01

License: http://creativecommons.org/licenses/by/4.0/

The gist: We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers.

Terminology

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 (K-A over sqrt KA sqrt T) minimax regret, where T is the total number of interactions and O(times) drops all constant and logarithmic factors, improving the previous (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 (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 at most A at most K-1.

Sources

Related papers