已知最优臂数量时，高效识别任意最优臂的理论最优方法
Optimal Best-Arm Identification under Fixed Confidence with Multiple Optima
- 利用已知最优臂数量的结构信息，设计更优的采样策略
- 新下界比已有结果更紧，且算法达到该理论极限
- 适用于需快速定位任一最优解的强化学习与实验设计场景
我们研究在固定置信度设置下的随机多臂赌博机中的最优臂识别问题，重点关注存在多个最优臂的情形。不同于以往处理最优臂数量未知的情况，本文假设最优臂的数量已知。我们推导了一个新的信息论下界，充分利用了这一结构性知识，其严格优于先前的界限。基于 Track-and-Stop 算法，我们提出一种考虑平局的停止规则，并证明该算法在渐近意义下为实例最优，达到了新下界。我们的结果首次为已知最优臂数量的多最优情形下提供了 Track-and-Stop 的最优性保证，既提供理论洞见，也给出高效识别任意最优臂的实际指导。
原文摘要 · Abstract (English)
We study best-arm identification in stochastic multi-armed bandits under the fixed-confidence setting, focusing on instances with multiple optimal arms. Unlike prior work that addresses the unknown-number-of-optimal-arms case, we consider the setting where the number of optimal arms is known in advance. We derive a new information-theoretic lower bound on the expected sample complexity that leverages this structural knowledge and is strictly tighter than previous bounds. Building on the Track-and-Stop algorithm, we propose a modified, tie-aware stopping rule and prove that it achieves asymptotic instance-optimality, matching the new lower bound. Our results provide the first formal guarantee of optimality for Track-and-Stop in multi-optimal settings with known cardinality, offering both theoretical insights and practical guidance for efficiently identifying any optimal arm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。