Closing the Gap on the Sample Complexity of 1-Identification

arXiv:2601.15620v2 Announce Type: replace Abstract: The 1-identification problem is a fundamental pure-exploration problem in multi-armed bandits. An agent aims to determine whether there exists an arm whose mean reward exceeds a known threshold mu_0, or to output extsf{None} otherwise. The agent must guarantee correctness with probability at least 1-elta, while minimizing the expected number of arm pulls E[au]. We study the 1-identification problem and make two main contributions. First, for instances with at least one qualified arm, we derive a new lower bound on E[au] via a novel optimization formulation. Second, we propose a new algorithm and establish upper bounds that match the lower bounds up to polynomial logarithmic factors uniformly over all instances. Our result complements the analysis of Eau when there are multiple qualified arms, which is an open problem in the literature.

Source: arXiv cs.LG | 2026-05-15