Closing the Gap on the Sample Complexity of 1-Identification

Li Zitian, Cheung Wang Chi · 2026

Read Closing the Gap on the Sample Complexity of 1-Identification by Li Zitian, Cheung Wang Chi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-15620.txt.

Introduction

Li Zitian and Cheung Wang Chi close a gap in bandit theory in a 2026 arXiv paper. Their topic is 1-identification, a pure-exploration problem. An agent faces a set of arms, each with an unknown mean reward. A threshold is known in advance. The agent must say whether some arm meets the threshold. If it believes none does, it outputs None. Sampling is costly, so efficiency matters.

Sample complexity counts how many pulls a correct answer needs. The title claims the paper closes the gap on that count. Closing a gap means upper and lower bounds now meet. The problem is fully understood in that sense, up to the stated terms. Identification tasks appear in testing and screening. Knowing the true sampling cost guides how such tests should be run.

Catalog record

CREATORLi Zitian, Cheung Wang Chi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE192 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-15620

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Closing the Gap on the Sample Complexity of 1-Identification Li Zitian, Cheung Wang Chi Abstract 1-identification is a fundamental multi-armed bandit formulation on pure exploration. An agent aims to determine whether there exists a qualified arm whose mean reward is not less than a known threshold μ 0 \mu_{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 − δ 1-\delta , while making expected total pulling times 𝔼 ​ τ \mathbb{E}\tau as small as possible. We work on 1-identification with two main contributions. (1) We utilize an optimization formulation to derive a new lower bound of 𝔼 ​ τ \mathbb{E}\tau , when there is at least one qualified arm. (2) We design a new algorithm, deriving tight upper bounds whose gap to lower bounds are up to a polynomial of logarithm factor across all problem instance. Our result complements the analysis of 𝔼 ​ τ \mathbb{E}\tau when there are multiple qualified arms, which is an open problem left by history literature. K eywords 1-identification, Fixed Confidence, Pure Exploration 1 Introduction 1.1 Model & Problem Formulation We study the 1-identification problem 1 1 1 This name origins from Katz-Samuels and Jamieson 2020 , Li and Cheung 2025 . In Degenne and Koolen 2019 , it is also called Any Low Problem. , a variant of the best arm identification problem. An instance of 1-identification consists of a tuple of four elements: \nu=([K],\rho=\{\rho_{a}\}_{a\in[K]},\mu_{0},\delta) . The set [K] denotes the arm set \{1,2,\cdots,K\} , and we assume K\geq 2 . For each a\in[K] , \rho_{a} is the reward probability distribution associated with arm a . The reward distribution \rho_{a} is not known to the agent for each a . By pulling arm a once, the agent receives a random reward distributed as \rho_{a} . We denote r_{a}^{\nu}:=\mathbb{E}_{R\sim\rho_{a}}[R] as the mean reward of arm a under reward distribution \rho_{a} . We assume the random noise R_{a}-r_{a}^{\nu} to be 1-sub-Gaussian. The real number \mu_{0} is a threshold known to the agent. The agent’s main goal is to predict whether there is an arm a\in[K] with r_{a}^{\nu}\geq\mu_{0} , and to identify such an arm in the positive case, while outputting “ None ” in the negative case. The quantity \delta\in(0,1) is the tolerant parameter on the probability of a wrong prediction. The agent’s pulling strategy is specified by a sampling rule \pi=\{\pi_{t}\}_{t=1}^{\infty} , a stopping time \tau and a recommendation rule \hat{a}\in[K]\cup\{\textsf{None}\} . When a pulling strategy is applied on a 1-identification problem instance with reward distribution \rho , the strategy generates a history \{U_{0}\}\cup\{A_{t},X_{t},U_{t}\}_{t=1}^{\tau} , where A_{t}\in[K] denotes the arm pulled at t , X_{t}\sim\rho_{A_{t}} denotes the reward received, and U_{t}\sim\text{Unif}(0,1) is an internal random seed. Arm A_{t}\in[K] is chosen contingent upon the history H(t-1)=\{U_{0}\}\cup\{(A_{s},X_{s},U_{s})\}^{t-1}_{s=1} , via the function \pi_{t}(H(t-1)) . The agent stops pulling at the end of time step \tau , where \tau is a stopping time with respect to the filtration \{\sigma(H(t))\}^{\infty}_{t=1} . After time step \tau , the agent outputs the prediction \hat{a}\in[K]\cup\{\textsf{None}\} . We require that \hat{a} is measurable with respect to \sigma(H(\tau)) , i.e. determined by the information H(\tau) . Outputting \hat{a}\in[K] means that the agent concludes with arm \hat{a} satisfying r_{\hat{a}}^{\nu}\geq\mu_{0} , while outputting \hat{a}=\textsf{None} means that the agent concludes with no arm having mean reward \geq\mu_{0} . We say that \nu is a positive instance if \max_{a}r_{a}^{\nu}>\mu_{0} , and say that \nu is a negative instance if \max_{a}r_{a}^{\nu}<\mu_{0} . For \Delta>0 , we define \mathcal{S}^{\text{pos}}_{\Delta}=\{\nu:\max_{a}r_{a}^{\nu}-\mu_{0}\geq\Delta\} , \mathcal{S}^{\text{neg}}_{\Delta}=\{\nu:\mu_{0}-\max_{a}r_{a}^{\nu}\geq\Delta\} , and take \mathcal{S}^{\text{pos}}=\cup_{\Delta>0}\mathcal{S}^{\text{pos}}_{\Delta},\mathcal{S}^{\text{neg}}=\cup_{\Delta>0}\mathcal{S}^{\text{neg}}_{\Delta} . We define i^{*}(\nu) as the set of correct answers. For \nu\in\mathcal{S}^{\text{pos}}_{\Delta} , we have i^{*}(\nu)=\{a:r_{a}^{\nu}\geq\mu_{0}\} , while for instance \nu\in\mathcal{S}^{\text{neg}}_{\Delta} , we have i^{*}(\nu)=\{\textsf{None}\} . We don’t consider instance whose \max r_{a}^{\nu}=\mu_{0} and mainly focus on analyzing PAC algorithms, with the following definitions. Definition 1 . A pulling strategy is \delta -PAC, if for any \delta\in(0,1),\nu\in\mathcal{S}^{\text{pos}}\cup\mathcal{S}^{\text{neg}} , it satisfies \Pr_{\nu}(\tau<+\infty,\hat{a}\in i^{*}(\nu))>1-\delta . Appendix A.3 in Li and Cheung 2025 shows that a \delta -PAC algorithm can still suffer from \mathbb{E}_{\nu}\tau=+\infty for some \nu\in\mathcal{S}^{\text{pos}} . Thus, we further introduce the following definition, which can be considered “Stronger \delta -PAC”. Definition 2 . A pulling strategy is (\Delta,\delta) -PAC, if it is \delta -PAC, and for any \Delta,\delta>0 , we have \sup_{\nu\in\mathcal{S}^{\text{pos}}_{\Delta}\cup\mathcal{S}^{\text{neg}}_{\Delta}}\mathbb{E}_{\nu}\tau<+\infty . The agent aims to figure out a (\Delta,\delta) -PAC pulling strategy (\pi,\tau,\hat{a}) that minimizes the sampling complexity \mathbb{E}[\tau] . 1.2 Lit Review on 1-identification Before illustrating our main contribution, we first review the weakness in the history literature and we start the review by unifying the notations. In the following paper, we consider a reward vector \{\mu_{a}\}_{a=1}^{K}\subset[0,1]^{K} satisfies that \mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{K} . Also, we consider \mu_{0}\in[0,1] and define \Delta_{i,j}=|\mu_{i}-\mu_{j}| for \forall i,j\in[K]\cup\{0\} . For an instance \nu , we assume r_{a}^{\nu}=\mu_{a} without further explanation. In addition, we introduce different complexity terms occurred in the history result. \displaystyle\begin{split}H_{1}^{\text{neg}}=&\sum_{a=1}^{K}\frac{2}{\Delta^{2}_{0,a}},H^{\text{low}}_{1}=\sum_{a:\mu_{a}<\mu_{0}}\frac{2}{\Delta_{1,a}^{2}},H=\frac{2}{\Delta^{2}_{0,1}}\\ H_{1}=&\sum_{a=2}^{K}\frac{2}{\Delta^{2}_{1,a}},H_{0}=\sum_{a:\mu_{a}\geq\mu_{0}}\frac{2}{\Delta^{2}_{0,a}}\\ H^{\text{u}}=&\frac{(\frac{K}{m}-1)}{\Delta^{2}},\Delta:=\min_{a:\mu_{a}>\mu_{0}}\Delta_{a,0},m:=\arg\max\{a:\mu_{a}>\mu_{0}\}\\ H(j)=&\frac{1}{j}\sum_{a=1}^{K}\frac{1}{\max\{\Delta_{j,a}^{2},\Delta_{a,0}^{2}\}}\end{split} (1) The discussion on the sample complexity focuses on two cases: instance \nu is negative or positive. There has been abundant research achieving the tight approximation of sample complexity on a negative instance, which is similar to the Best Arm Identification. Regarding the lower bound of \mathbb{E}\tau , Theorem 5.4 in Li and Cheung 2025 asserts \mathbb{E}\tau\geq\Omega(H_{1}^{\text{neg}}\log\frac{1}{\delta}) , if we apply any \delta -PAC algorithm on an instance \nu . Meanwhile, Algorithm HDoC in Kano et al. 2017 , APGAI in Jourdan and Réda 2023 , SEE in Li and Cheung 2025 , are able to guarantee \mathbb{E}\tau\leq O(H_{1}^{\text{neg}}(\log\frac{1}{\delta}+\log H_{1}^{\text{neg}})) , ignoring some logarithm factor. In addition, Algorithm Sticky Track and Stop (S-TaS) in Degenne and Koolen 2019 is able to guarantee \lim\sup\limits_{\delta\rightarrow 0}\frac{\mathbb{E}\tau}{\log\frac{1}{\delta}}\leq T^{*}(\nu) , where T^{*}(\nu)=H_{1}^{\text{neg}} if \nu is negative and the reward follows Gaussian distribution with variance 1 . Contrast with the negative instance, the complexity of positive instance remains a mystery, as the proposed upper bounds for a positive instance suffer from different looseness. For simplicity, we consider a positive instance \nu and denote \mu_{1}\geq\cdots\geq\mu_{m}>\mu_{0}\geq\mu_{m+1}\geq\cdots\geq\mu_{K} and only consider reward following Gaussian distribution with variance 1 . We propose Table 1 to summarize the looseness in the current result, with imprecise formulation because of space limit. The actual upper bound existing in the history literature is not smaller than our presented formulation, and we can still observe the looseness in our presented formulation. Following the Appendix A.2 in Li and Cheung 2025 , we put details of simplification on history upper bound in Appendix A . Table 1: Comparison of non-asymptotic upper bounds on \mathbb{E}\tau for a positive instance \nu . “LB” denotes Lower Bound. \surd_{\text{cond}} means the upper or lower bounds are optimal under some specific instances. The definitions of different H ’s are at the equation ( 1 ). We determine whether a sampling complexity upper bound is nearly optimal by comparing with the lower bound. An upper bound is nearly optimal iff the gap is up to a polynomial of \log K,\{\log\frac{1}{\Delta_{a,0}^{2}}\}_{a=1}^{K} . Algorithm Non-asymptotic Bound Optimality S-TaS, Degenne and Koolen 2019 Poiani et al. 2025 \mathbb{E}\tau\leq O(\frac{\log(1/\delta)}{\Delta_{0,1}^{2}}+\frac{K^{2}}{\Delta_{0,1}^{4}}) \times HDoC, Kano et al. 2017 \mathbb{E}\tau\leq O(\frac{\log\frac{K}{\delta}}{\Delta_{0,1}^{2}}+H_{1}\log\log\frac{1}{\delta}+\frac{K}{\epsilon^{2}}) \times lilHDoC, Tsai et al. 2024 \mathbb{E}\tau\leq O(\frac{\log\frac{K}{\delta}}{\Delta_{0,1}^{2}}+H_{1}\log\log\frac{1}{\delta}+\frac{K}{\epsilon^{2}}) \times APGAI, Jourdan and Réda 2023 \mathbb{E}\tau\leq O(H_{0}(\log\frac{K}{\delta})) \times FWER-FWPD Katz-Samuels and Jamieson 2020 \mathbb{E}\tau\leq

Read the complete text