# Closing the Gap on the Sample Complexity of 1-Identification

arXiv: https://arxiv.org/abs/2601.15620 · HTML: https://mlsanity.com/paper/2601.15620/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jan 2026.

## Built on by (most cited first, 1 of 1)

- [Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback](https://mlsanity.com/paper/2605.23182/) (2026)

## Abstract (arXiv)

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.