Near Optimal Non-asymptotic Sample Complexity of 1-Identification

Zitian Li, Wang Chi Cheung · 2025

Read Near Optimal Non-asymptotic Sample Complexity of 1-Identification by Zitian Li, Wang Chi Cheung (2025) 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-2506-06978.txt.

Introduction

Zitian Li and Wang Chi Cheung study a pure test task for choice machines. The work dates to 2025. A user asks if any choice pays at least a set level, or if none does. The machine must be right with high chance while using few pulls.

Past work fixed the long-run cost of this task but left the short-run cost unclear. The authors give a new method and prove its cost is close to the best possible cost. The gap is only a small log factor. Tests on data also show the method beats older methods. The result helps users who must test options with care and low waste.

Catalog record

CREATORZitian Li, Wang Chi Cheung
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE152 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-06978

Browse the full library · About the Tower of Babel

Full text

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

Near Optimal Non-asymptotic Sample Complexity of 1-Identification Zitian Li, Wang Chi Cheung Abstract 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 \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 . ( 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. 1 Introduction The 1-identification problem is a fundamental multi-armed bandit formulation on pure exploration. The goal of the learning agent is to identify an arm whose mean reward is at least a known threshold \mu_{0} if such an arm exists, and otherwise to return None if no such arm exists. We study the fixed confidence setting, where the agent aims to return the correct answer with probability at least 1-\delta for a given tolerance parameter \delta\in(0,1) , while ensuring the number of arm pulls, aka sample complexity, as small as possible. The 1-identification problem models numerous real-world problems. For example, consider a firm experimenting multiple new campaigns, and seeks to know if any new campaign is more effective than the existing one. The firm may have a long history of applying the existing campaign, with sufficient data to determine the impact and reward by utilizing this campaign. Similar scenario applies to other industries such as service operations, pharmaceutical tests, simulation which involves comparisons between a benchmark and alternatives, in terms of profit, welfare or other metrics. Summary of Contributions. We make two contributions to the 1-identification problem. Firstly, existing research works only guarantee asymptotic optimality ( Degenne & Koolen 2019 ; Jourdan & Réda 2023 ) , or non-asymptotic near optimality in the case where all the mean rewards are smaller than the threshold ( ( Jourdan & Réda 2023 ) , or applying a Best Arm Identification algorithm). Novel to the literature, our proposed algorithm achieves the non-asymptotic optimality in the sample complexity both the positive case when there is a qualified arm, i.e. an arm with mean reward at least the threshold, and the negative case when there is no qualified arm. We prove matching upper and lower sample complexity bounds, and the gap between these upper and lower bounds is up to a polynomial logarithm factor. Secondly, we conduct numeric experiments to compare the performance of 1-identification algorithms. The numeric results suggest the excellency of our proposed SEE algorithm and also the weakness of some benchmark algorithms. Notation. For an integer K>0 , denote [K]=\{1,\ldots,K\} . For \mu\in[0,1] , we denote N(\mu,\sigma^{2}) as the normal distribution with mean \mu and variance \sigma^{2} . Denote \mathbb{E} and \mathbb{E}_{\nu,\textsf{alg}} as the expectation operator while the second one is to highlight that the expectation is determined by both the instance \nu and algorithm alg . 2 Model An instance of 1-identification is specified by the tuple Q=([K],\nu=\{\nu_{a}\}_{a\in[K]},\mu_{0},\delta) . The set [K] represents the collection of K arms. For each a\in[K] , \nu_{a} is the probability distribution of the reward received by pulling arm a once. The probability distribution \nu_{a} , and in particular its mean \mu_{a}:=\mathbb{E}_{R\sim\nu_{a}}R , are not known to the agent. For each arm a\in[K] , which has random reward R_{a}\sim\nu_{a} , we assume that the random noise R_{a}-\mu_{a} is 1-sub-Gaussian. The parameter \mu_{0} is a known threshold. The agent’s main goal is to ascertain whether there is an arm a\in[K] such that \mu_{a}\geq\mu_{0} . The parameter \delta\in(0,1) is the tolerant probability of a wrong prediction. Unless otherwise stated, we always assume \mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{K} , but the order remains unknown to the agent. Dynamics. The agent’s pulling strategy (\pi,\tau,\hat{a}) is parametrized 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 \nu , the strategy generates a history A_{1},X_{1},\cdots,A_{\tau},X_{\tau} . Action A_{t}\in[K] is chosen contingent upon the history H(t-1)=\{(A_{s},X_{s})\}^{t-1}_{s=1} , via the function \pi_{t}(H(t-1)) . In addition, we have X_{t}\sim\nu_{A_{t}} . The agent stops pulling at the end of time step \tau , where \tau is a stopping time 1 1 1 For any t , the event \{\tau=t\} is \sigma(H(t)) -measurable with respect to the filtration \{\sigma(H(t))\}^{\infty}_{t=1} . Upon stopping, the agent outputs \hat{a}\in[K]\cup\{\textsf{None}\} to be the answer, using the information H(\tau) . Outputting \hat{a}\in[K] means that the agent concludes with arm \hat{a} satisfying \mu_{\hat{a}}\geq\mu_{0} , while outputting \hat{a}=\textsf{None} means that the agent concludes with no arm having mean reward \geq\mu_{0} . We allow the possibility of non-termination \tau=\infty , in which case there is no recommendation \hat{a} . To facilitate our discussions, we introduce the definitions of positive and negative instances. Definition 2.1 (Positive and Negative Instances) . Denote \nu as a distribution vector equipped with a mean reward vector \{\mu_{a}\}_{a=1}^{K} . We call \nu a positive instance, if \mu_{1}>\mu_{0} . And we call \nu a negative instance, if \mu_{1}<\mu_{0} . Correspondingly, we denote \mathcal{S}^{\text{pos}}=\{\nu:\mu_{1}>\mu_{0}\} and \mathcal{S}^{\text{neg}}=\{\nu:\mu_{1}<\mu_{0}\} . For \Delta>0 , we further define \mathcal{S}^{\text{pos}}_{\Delta}=\{\nu:\mu_{1}-\mu_{0}\geq\Delta\} and \mathcal{S}^{\text{neg}}_{\Delta}=\{\nu:\mu_{0}-\mu_{1}\geq\Delta\} . It is clear that \mathcal{S}^{\text{pos}}=\cup_{\Delta>0}\mathcal{S}^{\text{pos}}_{\Delta} and \mathcal{S}^{\text{neg}}=\cup_{\Delta>0}\mathcal{S}^{\text{neg}}_{\Delta} . In this paper, we assume that the underlying instance belongs to \mathcal{S}^{\text{pos}}\cup\mathcal{S}^{\text{neg}} . For an instance \nu\in\mathcal{S}^{\text{pos}}\cup\mathcal{S}^{\text{neg}} , we define i^{*}(\nu) as the set of correct answers. For \nu\in\mathcal{S}^{\text{pos}} , we have i^{*}(\nu)=\{a:\mu_{a}\geq\mu_{0}\} , while for instance \nu\in\mathcal{S}^{\text{neg}} , we have i^{*}(\nu)=\{\textsf{None}\} . We mainly focus on analyzing PAC algorithms, with the following definitions. Definition 2.2 . 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 . Definition 2.3 . 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 . Clearly, if a 1-identification pulling strategy is (\Delta,\delta) -PAC, it is also \delta -PAC. Objective. The agent aims to design a (\Delta,\delta) -PAC pulling strategy (\pi,\tau,\hat{a}) that minimizes the sampling complexity \mathbb{E}[\tau] . Table 1: Comparison of bounds. ”pos” and ”neg” in the second column correspond to \mu_{1}>\mu_{0} and \mu_{1}<\mu_{0} respectively. 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 logarithm factor. Algorithm Bound Nearly Opt in Positive Nearly Opt in Negative Comment S-TaS \lim\limits_{\delta\rightarrow 0}\frac{\mathbb{E}\tau}{\log\frac{1}{\delta}}=\begin{cases}H&\text{pos}\\ H_{1}^{\text{neg}}&\text{neg}\end{cases} \surd \surd Asymptotic HDoC \mathbb{E}\tau\leq\begin{cases}O(H\log\frac{K}{\delta}+H_{1}\log\log\frac{1}{\delta}+\frac{K}{\epsilon^{2}})&\text{pos}\\ O(H_{1}^{\text{neg}}\log\frac{K}{\delta}+\frac{K}{\epsilon^{2}})&\text{neg}\end{cases} \times \times \begin{array}[]{rl}\epsilon=&\min\Big\{\min\limits_{a\in[K]}\Delta_{0,a},\\ &\min\limits_{a\in[K-1]}\frac{\Delta_{a,a+1}}{2}\Big\}\end{array} APGAI \mathbb{E}\tau\leq\begin{cases}O(H_{0}(\log\frac{K}{\delta}))&\text{pos}\\ O(H_{1}^{\text{neg}}(\log\frac{K}{\delta}))&\text{neg}\end{cases} \times \surd Asymptotic Optimal in the case neg SEE (This work) \mathbb{E}\tau\leq\begin{cases}O(H\log\frac{1}{\delta})+O(H^{\text{pos}}_{1}\log\frac{K}{\Delta_{0,1}})&\text{pos}\\ O(H_{1}^{\text{neg}}(\log\frac{1}{\delta}+\log H_{1}^{\text{neg}}))&\text{neg}\end{cases} \surd \surd Even the O(\log\frac{1}{\Delta_{0,1}}) matches lower bound in some cases Lower Bound (This work) \mathbb{E}\tau\geq\begin{cases}\Omega(H\log\frac{1}{\delta}+\frac{1}{m}H^{\text{low}}_{1}-\frac{1}{\Delta^{2}_{1,m+1}})&\text{pos}\\ \Omega(H_{1}^{\text{neg}}\log\frac{1}{\delta})&\text{neg}\end{cases} NA NA In

Read the complete text