Closing the Gap on the Sample Complexity of 1-Identification
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913125168578560 |
|---|---|
| author | Li, Zitian Cheung, Wang Chi |
| author_facet | Li, Zitian Cheung, Wang Chi |
| contents | 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 \textsf{None} otherwise. The agent must guarantee correctness with probability at least $1-δ$, while minimizing the expected number of arm pulls $\mathbb{E}[τ]$. 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 $\mathbb{E}[τ]$ 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 $\mathbb{E}τ$ when there are multiple qualified arms, which is an open problem in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_15620 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Closing the Gap on the Sample Complexity of 1-Identification Li, Zitian Cheung, Wang Chi Machine Learning 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 \textsf{None} otherwise. The agent must guarantee correctness with probability at least $1-δ$, while minimizing the expected number of arm pulls $\mathbb{E}[τ]$. 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 $\mathbb{E}[τ]$ 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 $\mathbb{E}τ$ when there are multiple qualified arms, which is an open problem in the literature. |
| title | Closing the Gap on the Sample Complexity of 1-Identification |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2601.15620 |