arXiv：cs.LG（机器学习，全量分类）· Kaixuan Ji, Qiwei Di, Qingyue Zhao, Heyang Zhao, Quanquan Gu·· 5 小时前AI 评分30
多最优臂多臂老虎机：极小极大遗憾与非自适应性
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
AI 导读
针对有 A 个最优臂的 K 臂老虎机，该研究对已有子采样算法给出更精细分析，将遗憾上界改进为 Õ((K-A)/√(KA)·√T)，并给出匹配下界，证明该速率接近极小极大最优。研究还表明，要达到近最优遗憾，需在 Õ(1) 因子内已知 A 的取值。
正文
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 $\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 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 $\tilde{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$.
| Subjects: | Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Statistics Theory (math.ST); Methodology (stat.ME) |
| Cite as: | arXiv:2609.38659 [stat.ML] |
| (or arXiv:2609.38659v2 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2609.38659 arXiv-issued DOI via DataCite |
Submission history
From: Kaixuan Ji [view email]
[v1]
Tue, 29 Sep 2026 23:33:10 UTC (54 KB)
[v2]
Thu, 1 Oct 2026 03:05:49 UTC (54 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org