{"id":"arxiv/2609.38659","url":"https://arxiv.org/abs/2609.38659","tags":["stat.ML","cs.AI","cs.LG","math.ST","stat.ME"],"score":0,"title":"Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity","domain":"stat.ML","source":"arxiv","authors":["Kaixuan Ji","Qiwei Di","Qingyue Zhao","Heyang Zhao","Quanquan Gu"],"reviews":0,"subject":"stat.ML","summary":"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 $\\tilde{O}\\Big(\\frac{K-A}{\\sqrt{KA}}\\sqrt{T} \\Big)$ minimax regret, where $T$ is the total number of interactions and $\\tilde O(\\cdot)$ drops all constant and logarithmic factors, improving the previous $\\tilde{O}(\\sqrt{KT/A})$ regret. We then provide a…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}