[2505.15643] Optimal Best-Arm Identification under Fixed Confidence with Multiple Optima

Computer Science > Machine Learning arXiv:2505.15643 (cs) [Submitted on 21 May 2025 (v1), last revised 4 Mar 2026 (this version, v2)] Title:Optimal Best-Arm Identification under Fixed Confidence with Multiple Optima Authors:Lan V. Truong View a PDF of the paper titled Optimal Best-Arm Identification under Fixed Confidence with Multiple Optima, by Lan V. Truong View PDF HTML (experimental) Abstract: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. Comments: Subjects: Machine Learning (cs.LG); Information Theory (cs.IT); Machine Learning (stat.ML) Cite as: arXiv:2505.15643 [cs.LG]   (or arXiv:2505.15643v2 [cs.LG] for this version)   https://doi.org/10.48...