Near Optimal Non-asymptotic Sample Complexity of 1-Identification
This work addresses a fundamental gap in pure exploration for multi-armed bandits, providing a non-asymptotic solution to an open problem in the literature.
The paper tackles the 1-identification problem in multi-armed bandits by designing the Sequential-Exploration-Exploitation (SEE) algorithm to achieve near-optimal non-asymptotic sample complexity, with upper and lower bounds differing by a polynomial logarithmic factor.
Motivated by an open direction in existing literature, we study the 1-identification problem, a fundamental multi-armed bandit formulation on pure exploration. The goal is to determine whether there exists an arm whose mean reward is at least a known threshold $μ_0$, or to output None if it believes such an arm does not exist. The agent needs to guarantee its output is correct with probability at least $1-δ$. Degenne & Koolen 2019 has established the asymptotically tight sample complexity for the 1-identification problem, but they commented that the non-asymptotic analysis remains unclear. We design a new algorithm Sequential-Exploration-Exploitation (SEE), and conduct theoretical analysis from the non-asymptotic perspective. Novel to the literature, we achieve near optimality, in the sense of matching upper and lower bounds on the pulling complexity. The gap between the upper and lower bounds is up to a polynomial logarithmic factor. The numerical result also indicates the effectiveness of our algorithm, compared to existing benchmarks.