Closing the Gap on the Sample Complexity of 1-Identification

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 μ0, or to output textsfNone otherwise. The agent must guarantee correctness with probability at least 1-δ, while minimizing the expected number of arm pulls mathbbE[τ]. 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 mathbbE[τ] 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 mathbbEτ when there are multiple qualified arms, which is an open problem in the literature.