Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Authors: ZITIAN LI
Wang Chi Cheung
Venue: ICML 2025 poster (2025)
Keywords: 1-identification
Bandits
Complexity
Primary area: theory->online_learning_and_bandits
TL;DR: Targeting on a open problem 1-identification, we design a new algorithm and prove matching upper and lower bounds.

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 $\mu_0$, or to output \textsf{None} if it believes such an arm does not exist. The agent needs to guarantee its output is correct with probability at least $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.

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Zitian Li!
Wang Chi Cheung'
Abstract
problems. For example, consider firm experimenting mul- tiple new campaigns, and seeks to know if any new paign 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 bench- mark and alternatives, in terms of profit, welfare other metrics.
Motivated by an open direction in existing lit- erature, we study the 1-identification problem, fundamental multi-armed bandit formulation on pure exploration. The goal is to determine whether there exists an arm whose mean reward is at least known threshold (l,, or to output None if it believes such an arm does not exist. The agent needs to guarantee its output correct with probability least 5. (Degenne & Koolen, 2019) has established the asymptotically tight sample complexity for the I-identification prob- lem, but they commented that the non-asy -symmptotii analysis remains unclear. We design a new algo- rithm 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 to a polynomial logarithmic factor. The numer- ical result also indicates the effectiveness of our algorithm, compared to existing benchmarks.
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 ((Juurdan & 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 polynomial logarithm factor.
(SEE),
1. Introduction
Secondly, we conduct numeric experiments to compare the performance of I-identification algorithms. The numeric re- sults suggest the excellency of our proposed SEE algorithm and also the weakness of some benchmark algorithms.
The l-identification problem is 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 Ho 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 least 1 5 for given tolerance parameter d (0, 1). while ensuring the number of arm pulls, aka sample complexity, as small as possible.
Notation. For an integer K >> O, denote [K] {L,..., .il,..,,), K}. For μa E [0, 1], we denote N(,, σ²) ) as the normal distribu- tion with mean and variance a². Denote EE and Eyy, as the expectation operator while the second one is to highlight that the expectation is determined by both the instance 4 and algorithm alg.
The 1 1-identification problem models numerous real-world
2. Model
DDepartment of Industrial Systems Engineering & Manage- ment, National University of Singapore, Singapore. Correspon- dence to: Zitian <lizitian @ u.nus.edu eduu, Wang Chi Cheung risccwo@nus.cdu.gg...
An instance of I-identification is specified by the tuple Q = (K),, = {va [=][K]- (o, 8). The set [K] represents the collection of K arms. For each a E [K], v/a is the probability distribution of the reward received by pulling arm a once.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
The probability distribution V., and in particular its mean

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Ma ER R. are not known the agent. For each arm E [K] which has random reward R. Vas we assume that the random noise R. - Ma is I-sub-Gaussian. The parameter No is a known threshold. The agent's 's main goal is to ascertain whether there is an arm a E [K] such that Pa 2 /4g- The parameter 5 E (0, is the tolerant probability of a wrong prediction. Unless otherwise stated, we always assume #1 2 #22 2 ... μk. but the order remains unknown to the agent.
it is also 8-PAC.
Objective. The agent aims to design a (A, 8)-PA pulling strategy (I,, T, â) that minimizes the sampling complexity B[r].
3. Literature Review
We review existing research works on the I-identification problem. To aid our discussions, we define the following notations for describing bounds on sampling complexity. We define Di.j = |p4 Myl for all i,j E [K] U {0} and
Dynamics. The agent's pulling strategy T,, is parametrized by a sampling rule π = [ /-1 a stop- ping time r and a recommendation rule à E [K] U (None). When a pulling strategy is applied on a 1- identification problem instance v, the strategy generates history A1, XI,... Ar, Xy. Action A [K] is chosen contingent upon the history (t = {(Ag, X.)) via the function Ty (L 1)). In addition, we have X, ~ VAi- The agent stops pulling at the end of time step T, where r is a stopping time' with respect to the filtration {o (o(H(()) (1)
K
2
11
low
Σ
A
1,a
a=1
K
2
2
H
H
max A
0,a {
a=1
(1)
K
Upon stopping, the agent outputs à E [K] U {None} to be the answer, using the information (T). Outputting à [K] means that the agent concludes with arm â satis- fying Ma 2 No,, while outputting á None means that the agent concludes with no arm having mean reward 2 po. We allow the possibility of non-termination case there is no recommendation à.
H1
A
HD = Σ
A
2
4=2
1,a
0:/4a 2/o
0,0
2
2
HBAL
+
Σ
A
1,0
oo, in which
Since A1,1 0, we equivalently have H!T 3 +
Σx max m .A.... Table 1 summarizes the existing algorithms and their performance guarantees with notations in (I). Details are as follows.
To facilitate our discussions, we introduce the definitions of positive and negative instances.
Definition 2.1 (Positive and Negative Instances). Denote v as distribution vector equipped with a mean reward vector { Ja=1- We call v positive instance, if μ4 > Po. And we call a negative instance, if p1 < pi.
The I-identification problem is a pure exploration problem with possibly multiple answers, which has been studied in (Degenne & Koolen, 2019). They consider the case when V, belongs to the one-parameter one-dimensional exponential family for each a E [[], and propose the Taay--Traa--an--SSoer (S-TaS) algorithm. S-TaS satisfies F(r] = (M), which depends not only on lim sups-+0 log(1/8]
Correspondingly, we denote SPos {v: : M1 > ho and we further define
Sucg {v 141 < }0). For A
S - {v= p4 111-M po 2 }} and SIic = {v po M1 A). is clear that Spos = Ua>oSa and S = UA this paper, we assume that the underlying instance belongs to Spos S For an instance v E S U we define (w) as the set of correct answers. For v E Spos, we have (*()) = (a : (4 2 po), while for instance E S we have i (v) = (None}. We mainly focus on analyzing PAC algorithms, with the following definitions.
Snog In
[H]](k] but also {valne(k]- With their lower bound E(y]
lim infs- Tog( (4) any 8-PAC algorithm, they conclude S-TaS achieves asymptotic optimality. We display the bound T (14) in the special case when V42 N( 1) for each E A, where (") specializes to the bounds in the first row in Table 1. Nevertheless, the non-asymptotic sample complexity of the 1-identification problem remains a mystery in (Degenne & Koolen, 2019), who comment that "Both lower bounds and upper bounds in this paper are asymptotic... A finite time analysis with reasonably small o(log] })) terms for optimal algorithm is desirable."
Definition 2.2. A pulling strategy is 8-PAC, if for any E 1), E Spos U S it satisfies (r. < +00, á E (())) 1-8
Definition 2.3. A pulling strategy is (A, 8), if is 8- PAC, and for any A, 5,0% > O, we have suppest us E,T < +00.
(Kano et al., 2017) study the Good Arm Identification prob- lem, where the agent aims to output all arms whose mean reward is greater than fn-- This objective is different from our objective, which requires returning only a qualified arm if exists, but the expected stopping time of their first output
Clearly, a 1-identification pulling strategy is (A, PPAC,
FFor any f, the event (r = t] is
2

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Table 1. Comparison of hounds. "pos" and "neg" in the second column correspond to f4 > 1o and M4 po respectively. The definitions of different H'ss ss are at the equation (I). We determine whether a sampling complexity upper bound is nearly optimal by comparing with the lower bound, An upper bound nearly optimal iff the gap is up to a polynomial logarithm factor.
Algorithm
Bound
Nearly Opt
Nearly Opt in Negative
Comment
Positive
H pos
S-TaS
lim
Rr log 3
V
Asymptotic
H ncg
O log + H1 log log 5 + K)
c
min min Au.ay
pos neg
HDoC
Er <
O log K + K
X
X
min
An.a+1
eE(K
O(Hollog $
pos
APGAI
Er <
0 )) neg
X
Asymptotic Optimal in the case neg
SEE
Er
O(H log 2) + P tM log
Da.
K
pos
Even the Ollog 3 matches lower bound in some cases
011 (log + H1
(This work)
neg
[2(H log } + 1. H
pos
Lower Bound (This work)
ET
NA
NA
In pos, m E [] satis- fies Um 2 no pm+11
1( log }
neg
is exactly the Er in our formulation. They propose algo- rithm HDoC, whose sub-optimality of their sampling com-
complexity remains unclear. Appendix A.3 proves algo- rithm HDoC, lilHDoC, APGAI are not (A, 6)-PAC, and Appendix E.3 provides additional discussion on APGAI.
plexity upper bound comes from two perspectives. Firstly, the term 3 implies that the upper bound is vacuous (equal to infinity) when there exists a E [K] such that faa = μ4. even in the case of μ1 > po- Secondly, when μ1 μoo (Kano et al., 2017)'s bound includes H1 log log(1/8), and Hi grow linearly with K. (Kano et al., 2017) comment that log
Besides the above work, there are other research works related to I-identification, despite not directly solving the I-identification. (Kaufmann et al., 2018) provide asymptotic sample complexity bounds on classifying positive and nega- tive instances, but their algorithm does not output a quali- fied arm à E [K] on positive instance. (Katz- -KauzlSamuels & Jamieson, 2020) propose the idea of "Bracketing" to solve the I-identification problem. Their algorithm only applies for positive instances but not the negative instances, since the algorithm is not required certifying if there is no arm with mean reward at least μig More discussion on (Katz- Samuels & Jamieson, 2020) is provided in Appendix A.
"Therefore, in the case that K = 21 log log 4 ) there still exists a gap between the lower bound in ... and the upper bound in in..... ". (Tsai et al., 2024) incorporate the LIL concentration event (Lemma 3 in (Jamieson et al., 2014)) into the algorithm HDoC with an additional warm-up stage. But the proposed algorithm lilHDoC still suffers from the same sub-optimality as HDoC
(Jourdan& & Réda, 2023) mainly focus on designing any- time algorithms on Good Arm Identification. They propose pulling rule APGAI with the stopping rule GLR. Their algo- rithm achieves nearly optimal asymptotic sample complex- ity bounds on negative instances, but is still sub-optimal on positive instances. The stopping rule GLR can be combined with other pulling rules to guarantee the 8-PAC property, but in general there no non-trivial upper bound on Er. Finally, we remark that the Good Arm Identification formu- lation assumes Pa F po for all E [K], and their upper bounds are vacuous if there exists an arm whose mean reward is exactly Po-
The I-identification problem can be solved by considering a Best Arm Identification problem, which has been well studied. We can take arm 0 as a virtual arm which always returns a deterministic reward with value pv. Apply- ing an algorithm for the fixed confidence setting (Even-Dar et al., 2002; Gabillon et al., 2012; Jamieson et al., 2013; Kalyanakrishnan et al., 2012; Karnin et al., 2013; Jamieson & Nowak, 2014), the agent achieves aon-asympto high probability upper bound. For example, (Jamieson & Nowak, 2014) guarantee (ry(T < OHH (log 1 + log [1 > 1-8 for v E SPoR Pr,,(T < O(H (log } + log H(=r)) > 5 for E S And the logarithmic term 17A1, H can be improved. Nevertheless, the high probability up- per bound cannot imply ET < +oo. To address this issue, (Chen & Li. 2015; Chen et al., 2017) develop the Parallel
Table summarizes the comparison, with imprecision on HDoC and APGAL. Details are in appendix A.2. Among them, S-TaS is (A, 8)-PAC, but the non-asymptotic pulling
3

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Simulation Algorithm, which takes a BAI algorithm as an Oracle and converts this algorithm into new algorithm. The new algorithm is still 8-PAC, and guarantees not only the above high probability upper bound, but also finite up- per bound on Er. (Garivier & Kaufmann, 2016; Kaufmann et al., 2016; Garivier et al., 2019) provide asymptotic up- per bounds relating to IE,, complemented with matching lower bounds. Though there are many existing works on the BAI problem, the comparison of asymptotic results in these two formulations (Garivier & Kaufmann, 2016; Degenne & Koolen, 2019) suggests that it is inefficient to solve the 1 I-identification by the corresponding BAI problem.
and stops if there is an arm whose lower confidence bound (LCCB)ís > Mo- LUCB G guarantees the high probabil- ity bound Pro(ua > -oo T < O(1ff log(Htf /8')) > 8' for V E S and Pry(â = None, T < O H log( (H/ /8))) > 1 - 8' for v E Suce, where 8' E (0, 1) is the input tolerance level.
Algorithm takes LUCB G as an oracle by sequentially calling with tolerance level òş at phase k. The sequence JEN is non-increasing with k, and in phase lo 5% should be larger than the required tolerance level 6. In line 12 of Algorithm 1, we trust the negative prediction of LUCB G only when the 6g is smaller than the required tolerance level 6. The intuition is consistent with the conclu- sion in (Degenne & Koolen, 2019), which concludes lower bound 12 log }) is required for negative instance. Then, it is natural to accept the negative output "None" when 0g < 0()).
Our work is related to other topics, such as BAI in the fixed budget setting and the e-Good Arm Identification problem. We provide additional discussions in Appendix A.I.
4. Algorithm
While meeting a positive instance, we wish LUCB . can 1 identify a qualified arm with pulling times O ( log de which is line 6. Then we turn to keep pulling âg with confi- dence bound defined by true tolerance level 6, corresponding to the line 8. Line 5 is to avoid LUCB_C _G from getting stuck into a non-stopping loop, which is possible when the "good event" doesn't 't hold.
4.1. An Informal Algorithm
Algorithm 1 SEE(Informal)
I: Input: Action set [K]. threshold no. tolerance level 6, C> 1.
2: Tune {ōx, T }
3: for Phase h-- = 1,2, ... do
4: (Exploration) Run algorithm LUCB_G G with tolerance level 62 and previous exploration history.
Based on the above idea, Algorithm seems to be able to solve the problem. However, there are still two main con- cerns in Algorithm 1, stopping from adopting it directly, The first one is LUCB-G cannot guarantee the lower bound of Ha, - Mo, which makes it hard to set up maximum pulling times T% in the exploitation phase. To address this issue, we introduce a tunable parameter C > 1 and adopt a larger radius when calculating the LCB in Algorithm 3.
Stops until one of the two conditions holds.
5: Total pulling times in all exploration phases is greater than T Take åz = Not Complete
6: -LUBB.C G stops and output a E [K] U (None).
7: if âz E [K] then
8: (Exploitation) Keep pulling arm åg with samples independent of exploration.
The second concern is LUCB_G requires at the start of exploration phase k, LCB., < 1o holds for all E [K]. But in Algorithm 1, it is possible that at the end of phase k - 1, the last collected sample of arm â is so large, such that LCB of xx- is still above Ho at the start of phase k. To address this issue, we define a temporary container Q. When the LUCB G is going to output an arm â we transfer the latest collected sample of a into Q. If we pull arm á [K] in the future exploration period, transfer the sample back from Q history. The reason of transferring back from Q is concentration inequality like (3) requires consecutive integer index summation, and we cannot skip or abandon any samples.
Stops until one of the two conditions holds.
9:
* Pulling times of âg is greater than Te
10:
. LCB defined by 8 is above No. output âu as
qualified arm
11:
else if à. = None and 0% < 3 then Output the instance is negative
12:
13:
end if end for
14:
Before rigorously describing the algorithm, we provide an overview with a simple algorithm sketch. This sketch presents the overall framework of SEE, but some required adaptations are explained in the full in the subsequent parts of this section.
4.2. Sequential Exploration Exploitation
Algorithm 1 introduces the key idea of SEE. Algorithm LUCB G in line 4 is defined in (Kano et al., 2017), which can be considered an adapted BAI algorithm UCB in (Jamieson & Nowak, 2014). In each round, LUCB.G GG pulls the arm with the highest upper confidence bound (UCB),
For simplicity, define [x] = max [x]] 1}. We define the confidence radius
U(t (), = 22 21lgg2 e) log
2( 2[log f
8
(2)
t
4

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
To rigorously present the algorithm design, we split Algo- rithm 1 into three parts with more adaptation. Algorithm 2 is the main body, calling Algorithms 3 and 4 to conduct the pulling procedure. We elaborate on them one by one.
Algorithm 3 SEE- SEE-Exploration
I: Input: Action set [K], threshold Ho. confidence level 6, tunable parameter C' > 1, History H
U X x Temporary Container Q, Termi- nation Round T.
Algorithm 2
1: Input: Action set [ threshold Noo confidence level
2: Define Ma (H(.) No
No
X No
L t= 17 U UQ].
8, C > 1, scheduling parameter {ōx, Ogg, SR t (Default: C = 1.01, 5% = 1/33,, ag = 5", BR ) 2: Calculate 2xo = 1000 1 log(4K/ T
UCB,(HH 8) = Ma (HL0 + (N 8/K).
LCB, (H 56 = Pa (H - C. CN 88KK).
3: while True do
1000,3x
4: Determine A!" arg [k] UCB,, .))
3: Initialize: 70 71th = Q = 0. No No V. E
5: Get (X, Q, At) by calling Sampling Rule(Alg 5),
[K].
At AT 2r,Q&& Q
4: for Phase k: = 1,,,, do
6: NAy = =Naş + 1, = + At, He = 7000 U
5: (Exploration) Call Algorithm 3 with
{(Ar)
K + K. Po - Ho, 5 + 6x. C C, 70 + H100
if 1 T then
Q, - T T denote (āx. 7000 (2 as the output.
Break and take à Not Complete else if va [K], UCB, (H(T, S no then
6: if âR E [K] then
10:
Break and take à = None
7:
(Exploitation) Call Algorithm with K K, 140 Mo; < 5, Htt + Hat T 4 0k, t Orky denote (ans, 70 7) as the output. if ans Qualified then Return à = 0z..
11:
else if LCBAF A= (H 55) > 140 then
12:
Hº = 700 {(4ge X))
13:
Ar = No 1, Q = Q ((47)))
14:
Break and take = a
8:
15: end if'
9:
16:
end while
10: end if
17:
Return (ā, 7000 (,t)
11:
else if åg None and d% 8/3 then Return à None.
13:
end if
14:
end for
Algorithm 4 SHE-Exploitation
1: Input: Action set [K], threshold No, confidence level 8, Termination Round T', Predicted arm à E [K] Toler-
SEE, displayed in Algorithm 2, takes No: K, 5, C, (ōx, ore, ] as input, where μo: K, 8 model parameters and C, {6x, ak. 3x tt tunable parameters. Besides C = 1.01, 6₂ = 1/38, 0g 5
ance Controller a, History H uk ((a X xx )
t = 7
2: while No < T do
2², other choices are also available, see Appendix B.1.
3: Sample ~ Vaa
4: H 7d U ((,, No = No +1,=
Following Algorithm 1, Algorithm sequentially calls ex- ploration and exploitation oracles in each phase, while main- taining three sample sets H 7 Q. When calling the Ex- ploration Algorithm 3, H Q are updated. When calling Exploitation Algorithm 4, Hd is updated.
5: if X UNN 8
14o then
à Ka
6: return (Qualified, H .t)
7: end if
end while
return (Unqualified, H
Besides Ht.e H.a Q, Algorithm 2 further specifies Th = 1000(C + 13 1og(4K/6x) and T 10003, log( 4a K/5). The coefficient 1000 is to simplify the calculation in the proof of Lemma B. If we replace 1000 with another fixed positive constant, the main conclu- sion still holds.
Algorithm 5 Sampling Rule
I: Input: Arm a E [K]. Temporary Container Q
2: 3a, X) E Q such that a = A then
Algorithm 3 follows LUCB G in (Kano et al., 2017), with three major modifications. The first is adopting (2) as the radius of the confidence interval, which is smaller than the original LUCB.G. The second is adopting C U(.-) for the LCB in line 2, where C > In the case of a positive
Q Q= {(a, X)), At 0. return X, Q.
4: else
5: Sample X ~ MA, At 1, return X, Q, At
6: end if
5

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
instance, factor C can guarantee Påx > Whi + (1
8-PAC algorithm. The lower bound mainly comes from the existing results in the literature.
W)ot where w C-1
C+3 conditioned on an event that holds
with probability 2 1 =' Details are in Lemma B.4. The third is using the temporary container Q to conduct the modified sampling of an arm X in line 5.
5.1. Performance Guarantee of Algorithm 2
Before stating the main theorems of Algorithm 2, we in- troduce some notation. Define ft. (1/t) Σ 2,5
Algorithm 5 conducts the modified sampling for Algorithm 3. It only collects a new sample for arm A E [K] when Q does not contain sample on A. We only increase the total pulling times when we collect a new sample from VA- Algorithm 5 returns the updated Q together with the sample X. The necessity of using Q to temporarily store the latest collected sample X in line 13 in Algorithm 3 is discussed in section 4.1 I and Lemma B.6. From the above discussion, we know for each a E [K]. Q contains at most one tuple whose first element is a:
(./t)>==>
p = (1/1) E X2,
2, and
A3 min k EaN:VaE[K],Kl
| - Maa s U(1 8x x
(3)
n = min k KEN: [K)
Lemma 4.1. Throughout the pulling process, |Q] S K holds with certainty.
8 | Mal S (t, Kat }
Algorithm 4 takes (K, noo 6, T, a) as the input. The parame- ters K, Pg. 8 are model parameters, which remain the same in all phases. By contrast, the parameters I and å generally change across different phases. During phase k Algorithm 4 keeps pulling arm äş until one of the two following con- ditions is met. The first is when the total pulling times of arm āg in all exploitation periods is T, which should be 7xx at the phase k. In this case, the exploitation period cannot guarantee that Ma, > No holds with probability 2 1 - 6, and requires Algorithm 2 to run the next exploration period with smaller tolerance level 6k+1. The second condition is when the LCB, defined with the input tolerance level 8, of å is above foo In this case, Algorithm 2 adopts this result and outputs âR as à, asserting that the instance is positive.
Here k kt are the minimum phase indices such that the respective concentration inequality hold, in phase k, we use (t, x) and Utt, A to define the UCBs and the LCBs during the exploration and exploitation periods. Not hard to see n², n are random variables. By Lemma D.3 in the Appendix, we have the following.
Lemma 5.1. For all ls E N, it holds that
T Tōkz-1
5 n² 8
Pr(n* 0 2 k)) S
Pr(x" 2 k)
6
6 ak-1
Since 1o dg = 0, lim Og = +o,, we observe
that Pr(x** < +o0) 1, Pr < +oo) = 1. We first
show that Algorithm 2 is 5-PAC, which is mainly due to the design of our stopping rule. Theorem 5.2. Algorithm 2 is 8-PAC.
Throughout the pulling process, the samples collected among all the exploration periods are shared, as are the exploitation periods. By contrast, the exploration periods never share samples with the exploitation period. To dis- tinguish between the two sets of periods, we denote T and of as the total pulling times of Algorithms 3 and 4, from the start of phase to the end of phase k. We also denote No (TT"). (rf') as the total pulling times of arm E [K] stored in 7 and H", at the end of phase k. From the algorithm design, it is clear that the following Lemma holds.
Sketch Proof of Theorem 5.2. The first step is to show Pr(T = +00) < Pг(x** = +x)) + Pr(n = +00) = O. indicating that T too with certainty. Then, we know à E [K] U (None) in Algorithm 2 is well defined with certainty.
If v is positive, the event à &f (²() occurs only in the following two scenarios. The first scenario is when an exploration period outputs None in phase k such that dg < 5/3. The second scenario is when an exploitation period outputs an arm with mean reward- < Po- The probabilities of both events are at most 5 multiplied by an absolute constant, and we can conclude Pr. $ 8" (v)) < 8.
Lemma 4.2. At the end of phase k 1. Tee < THs Th
S Ep=1 T 2. IQ1 + 17000 = T 3.
Since
| = a=1 a (TC2). we can further conclude
ΣK1 No (TT) < T
< K K+> Ex= (Tg).
K
If v/ is negative, the event â & i (v) occurs only when an exploitation period outputs an arm, which is the same as the second case in the discussion of positive v. We then have (r et i" (v)) < 8 again, hence the Lemma proved. Ll
5. Main Results
In this section, we demonstrate upper bounds of Er by applying SEE, and provide lower bounds on Er for any
6

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
The full proof is in Appendix B.2. The following theorem shows that Algorithm is nearly optimal in minimizing Er.
holds for all k: 2 max(x ,'], a E [K] with certainty. Summing up the above inequality for all [K] and using
the fact that TE < K + +> Na(TE) (Lemma 4.2), we complete the proof of (4). Lemmas B.4, B.6, B.8 contain more details.
Theorem 5.3. Apply Algorithm 2 to an instance we have log 7- A..1 y- ( } + +log ))
+ (log
K Do,1
)
V E SP where ME S
ET S
The next step is to show conditioned on μag, 2 wpl + (1 w w)Ho,, k 2 max L"} can guarantee the exploitation pe- riod output Qualified, and the algorithm must stop. This is straightforward, k 2 kat guarantees (
only depends the constant C' but independent of model parameters K, ò and (Ha)øzv In particular, when we set C to be an absolute constant such as C = 1.01, y is also an absolute constant.
02 Kay <
No. E. X
w(m)-Po) implies 2
U(N
6 > No- as Kae
From the definition of H1T
know K <
H
No
and 1/A < H, Thus, we have log(K/ A
0.1) <
Meanwhile, having k 2 L" guarantees TV is large enough
2 log HPp Meanwhile, since max ( 1 2 1,,14 /4,
such that Algorithm 4 will not quit the While loop before
we have H < 8K/AA, leading to log 111 < log 8 +
Net large enough such that U āg² Kor < w(m -po)
ag
log( K f,o). Thus, it is equivalent to state the upper bound
holds. Combining these intermediate steps, we have
7
log
A + (log HPT -HT
V/ E SPOs
As Theorem 5.7 discusses the existence of log Ao.1' we adopt the current expression for further comparison. The full proof is in Appendix B.2.
as IE 1
.. (H1 1/ + log H)
V Sueg
8max (Nte ../) )+
1K
0
K mmaxiie .ny log
K log K
max f1et .m + log log max max ( Al.a)
0
max [ (A Ab.a}
Sketch Proof of Theorem 5.3. The main idea is to split T = 700 +T* and we derive upper bounds for both Er and
4K KBam log 8,c0
5 "M log 11m0)
+
Er" In the following, we only summarize the main steps
1K
1
of upper bounding E,ee, when instance v positive. Proofs for other cases are similar.
0 KB log
+0
11 log
6,50
1
0
H log
+0
H1mh log
Define L' [log2 24[++1"H
[log2
192(C+1)² w A
6pm
K C-1 Via routine calculations, we have I," Z where w = C43
H log
dy
L'. To prove Theorem 5.3, the most important intermediate step is to show that in phase & 2 max{xx L'), Algorithm 3 always outputs à E [K]. pa > wHi + (1 w)oo with certainty. In addition,
holds with certainty. Take expectation on both sides, we can use inequalities such as
4K denaxe .1/--1
00
K Kmmaxin 11)-1 11) log
4K
4K Pr(x = k)
E log
Bg log
8
8%
5% K + log log max AF, Baan log
(4)
1=1
A a: 3
Lemma 5.1
T 62
4K Bg log
= Ollog K)
The intuition is as follows. Firstly, at the end of phase max(x"0 L'} we have
to derive the upper bound of E,
Ta (a= 11-1 ( 5 K Bmaxxxn _1)-1 log d ( 1
4K
Combining Theorems 5.2 and 5.3, we know Algorithm 2 is (A, 8)C..
This is guaranteed by the Lemma 4.2. Then, starting from phase max L'}. T is large enough, such that Algo- rithm 3 will not enter the case of line 8. By induction, we have
5.2. Lower Bounds
We derive lower bounds for both positive and negative in- stances based on techniques in existing works. Without extra description, we assign unit variance Gaussian noise for each of the arm in the constructed instances. The results in (Garivier & Kaufmann, 2016; Degenne & Koolen, 2019) can be adopted to show the following:
Na(78)) < max Na Na nn .13--
K. log og
log log af 26,1)
maxfA? A
7

---

Near Optimal Non Non-asymptotic Sample Complexity of 1-Identification
Theorem 5.4. For a unit variance Gaussian instance equipped with mean reward vector { Po > maxigask pas any ô-PAC I-identification algorithm alg would satisfy EagT 2 ( (1)()
for is { J and the alg must satisfy Bu..)gNa(T)) 2
(1 (1/4011//////////// //.0/ Va 2.
The full proof is in Appendix C.3. Theorem 5.7 implics the expected pulling times of unqualified arms would be impacted by the gap between the best arm and the thresh- old. Nevertheless, we caution that this impact might only occur when 11, is sufficiently small. If A1.0 is suffi-
Detailed proof can be found in Appendix C.I. Comparing with the upper bound in Theorem 5.3, the gap between the upper and lower bounds in the negative case is up constant and polynomial logarithm factor polylog( (7))0)) in the 5 independent part. We also derive a lower bound for a positive instance, based on the analyses in (Degenne & Koolen, 2019) and "Katz-Samuels & Jamieson, 2020).
Thus, 1og(1/Aio) < A1.0 ciently small, is possible Σx Ai.a the (11og(1/4).)) term might not occur in the upper bound of Er, since the upper bound of EEr usually contains O(1/Af.o)
Theorem 5.5. Consider any {poJa-u E [0, 1] satis- fying pr 2 H2 2 ... 2 PK, P1 > Ho- Consider in- stance v that takes a permutation of {Ja]azı as the re- ward vector, and po as the threshold. Then, for any 8-PAC 1 I-identification alg, any 6 E (0, 1), we have En.aiaT 2 Q (H log 3) = 12( log 3). Ad.1
6. Numerical Experiments
We conduct numerical evaluations on SEE and existing benchmark algorithms on synthetic instances. The bench- mark algorithms include HDoC, LUCB G in (Kano et al., 2017), lilHDoC in (Tsai al., 2024), Murphy Sampling (MS) in (Kaufmann et al., 2018) and TaS in (Garivier & Kaufmann, 2016). Algorithm MS and TaS are not origi- nally designed for I-identification, but we adapt these algo- rithms by applying the GLR stopping rule (see Lemma 2 in (Jourdan & Réda, 2023)). In what follows, we call these adapted versions as adapted-MS and adapted-Tas respec- tively. While adapted-MS and adapted-TaS are still 8-PAC, there is conviaivial theoretical guarantees their sample complexity bounds. Hence, these adapted algorithms are heuristic. In Appendix E.3, we discuss APGAI in (Jour- dan & Réda, 2023) on its numerical performance, which presents a significantly different trend from others.
Theorem 5.6. Consider any {pola=o JK E [0,1]KK1 satis- PK.- For any 8-PAC I I-identification alg, any d E (0, 16), we can find a posi- tive instance v whose mean reward vector is permuta- tion of vector {μa]ø= and the threshold is po, such that Ey,aigT 2 Ω (H1).
fying Pn > No 2 112 2
The full proof is in Appendix C.2. The last step is to com- bine Theorem 5.5 and 5.6. If we assume (41 > 140 2 /22 2 -.KK, for any 8-PAC algorithm, we can find an instance V taking {pa K 1 E [0. 1] as a permutation of reward vec- tor, such that E,T 2 Ω log i 2 + Exk2 max 47, : The reason is A1.e > Ao.a holds for all a 2 2. Together with Theorem 5.3, we deduce that the gap between upper and lower bounds is at most a factor poly(log Ao. {log An. )==)), if the mean re- ward vector satisfies μ11 > 1o 2 P2.... 2 PK. Theorem 5.3 guarantees our bound's dependence on log 1/5 is nearly optimal, but it still remains unclear what would be tight upper and lower bound of the 8 independent part, if there are multiple arms above /40-
We do not include algorithms S-TaS (Degenne & Koolen, 2019) and APT G (Kano et al., 2017) in the benchmark algorithm list, since the performance of algorithm S-TaS heavily relies on the position of the qualified arm in the positive case, as shown by (Jourdan & Réda, 2023). And (Kano et al., 2017) show that empirically APT G performs poorly compared to the HDoC, LUCB.G.
K
We consider six different groups of reward vectors, which are "All Worse", "Unique Qualified", "One Quarter", "Half Good", "All Good" and "Linear". The main difference among these groups is the number of qualified arms. All instances in "All Worse" group are negative, whose mean rewards of all arms are below 14g Due to the low execu- tion speed of algorithm MS on group "All Worse", we do not apply MS the instance "All Worse". Other groups of instances are positive, meaning that there is at least one arm whose mean reward is > p4y We set 10 as our forced stopping threshold for each group of experiments. Every algorithm stops and outputs an answer at or before the num- ber of arm pulls reaches 1 The details of the numerical setting, tuning of the parame-arsmeters in SEE, and other implementation details can be found in Appendix E.
Besides the lower bounds for the total expected pulling times, we also derive a lower bound for the pulling times of arm whose Mo < μo- The following theorem can only imply the possibility that the O(log(1/ ( in Theorem 5.3 is required.
Theorem 5.7. Fixed any po E [0, 1). {Ha) E |0, 1|K-1 satisfying μo > u22 2 ... 2 pk.. For any (A, 8)- 1 l-ddentification alg, any 8 < 1/e². we can find a small enough Λ > O, such that for any P1 (Po, Po + A0,1). we can find a problem instance whose mean reward vec-
"We do not find any related results in the literature, which motivates us to state the partial result in what follows.
8

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identiftcation
Figure illustrates the numerical results. In "AllWorse", proposed algorithm SEE outperforms all the benchmarks, and the advantage of SEE becomes more obvious as K increases. In "One Quarter", "Half Good", "All Good", "Linear" ", adapted-TaS and adapted-MS outperform SEE when K I 50. However, as K increases, the leading gap of adapted-Tas and adapted-MS becomes smaller. When K 200. SEE outperforms adapted- and adapted-MS in instances "One Quarter", "Half Good", "All Good". In instances "Unique Qualified",, adapted- and adapted-MS consistently have better numerical performance. In compar- ison with benchmark algorithms in (Kano et al., 2017), our proposed SEE outperforms HDoC, lilHDoC and LUCB G in most the instances, except K = 10, 20 in the "Unique Qualified" group. When gets smaller, the above phe- nomenon is more pronounced. Altogether, SEE is competi- tive among all the algorithms with theoretical claims.
AllWorse, 6=0.001
Unique, 6=0.001
Empircal Stapping Timax
125000
250000
700000
73000
100000
50000
25000
100
130
300
150
200
OneQuarter, 6=0.001
HalfGood, 6m0.000
6-0.001
Empitial Stapping times
80000
100000
60000
75000
40000
50000
20000
20000
2004
130
200
320
150
200
AllGood, 6=0.001
Linear, 6=0.001
Empincal Stapping Times
100000
The numerical performance is consistent with our theoret- ical analysis. As Theorem 5.3 suggests, if we apply SEE to a positive instance, the empirical stopping times increase proportionally to K. However, our dependence on K is bet- than the existing algorithms'' sample complexity bounds, in the sense that the coefficient of the in sample com- plexity bound is independent of K on positive instances. This property does not hold for the sample complexity up- per bounds for algorithms HDoC and lilHDoC. The above provides intuition on larger leading gap of SEE in the case of smaller 8.
50000
100000
60000
50000
40000
2004
150
200
120
150
200
LUCB_G
BINDoC
HDoC
755
AllWorse, 6=0.0001
Unique, 6=0.0001
300000
175000
Empinccll Stopping
100000
200000
75000
In our numerical experiments, adapted-MS and adapted- TaS have good performances, especially in the case of small arm number. However, from figure 2 in the appendix E.2, it can be observed that their empirical stopping times are not monotonically decreasing as the proportion of the qualified arm increases. In contrast, SEE performs better when the proportion increases, which suggests the stability and robustness of our proposed SEE.
100000
50000
25000
0
1000
7007
OneQuarter, 6=0.0001
HalfGood, 6=0.0001
Empincal Stopping
80000
100000
75000
40000
50000
20000
25000
7. Conclusion
0
1000
150
200
200
We study the I-identification problem in the fixed confidence setting, and design new algorithm SEE. We establish a non- asymptotic sample complexity upper bound for Er under SEE, which nearly optimal the negative instance and positive instance with unique qualified arm. The superior performance of SEE is also corroborated by numerical experiments.
AllGood,
6.00001
Linear, 6-0.0001
150000
100000
Enpincal Stapping
75000
100000
50000
50000
25000
40000
100-
200-
K
LUCB,G
IIHDoC
Acknowledgment
HDoC
TS5
M5
This research work is funded by Singapore Ministry of Education AcRF Tier 2 grant (A-8003063-00-00)
Figure Numerical Experiments on SEE Benchmarks
9

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Impact Statement
Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. Pac subset selection in stochastic multi-armed bandits. In ICML, volume 12, pp. 655-662, 2012.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Kano, H., Honda, J., Sakamaki, K., Matsuura, K., and Sugiyama, M. Good arm identification via bandit feed- back. Machine Learning, (2), 2017
References
Karnin, Z., Koren, T., and Somekh, O. Almost optimal exploration multi-armed bandits. International con- ference on machine learning, pp. 1238-1246. PMLR, 2013.
Chen, L. and Li, J. On the optimal sample complexity for best arm identification. arXiv preprini arXiv: 2015.
Chen, L., Li, J., and Qiao, M. Nearly instance optimal sample complexity bounds for top-k arm selection. In Artificial Intelligence and Statistics, pp. 101-110. PMLR, 2017.
J. and Jamieson, K. The true sample com- plexity of identifying good arms. In International Con- ference on Artificial Intelligence and Statistics, pp. 1781- 1791. PMLR, 2020.
Degenne, R. and Koolen, W. M. Pure exploration with multiple correct answers. Advances in Neural Information Processing Systems, 32, 2019.
Kaufmann, E. and Kalyanakrishnan, S. Information com- plexity bandit subset selection. Conference on Learn- ing Theory, pp. 228-251. PMLR, 2013.
Even-Dar, E., Mannor, S., and Mansour, Y. Pac bounds for multi-armed bandit and markov decision processes. In Computational Learning Theory: 15th Annual Con- ference Computational Learning Theory, COLT 2002 Sydney, Australia, July 8-10, 2002 Proceedings 15, pp. 255-270. Springer, 2002.
Kaufmann, E.,, Cappé, O., and Garivier, A. On the com- plexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1-42, 2016.
Kaufmann, E., Koolen, W. M., and Garivier, A. Sequential test for the lowest mean: From thompson to murphy sampling. Advances in Neural Information Processing Systems, 31, 2018.
Gabillon, V., Ghavamzadeh, M., and Lazaric, A. Best arm identification: A unified approach to fixed budget and fixed confidence. Advances in Neural Information Pro- cessing Systems, 25, 2012.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Garivier, A. and Kaufmann, E. Optimal best arm identifi- cation with fixed confidence. In Conference on Learning Theory, pp. 992-1027. PMLR, 2016.
Locatelli, A., Gutzeit, M., and Carpentier, A. An optimal algorithm for the thresholding bandit problem. In Interna- tional Conference on Machine Learning, pp. 1690-1698. PMLR, 2016.
Garivier, A., Ménard, P., and Stoltz, G. Explore first, exploit next: The true shape of regret in bandit problems. Mathe- matics of Operations Research, 44(2)3377-399, 2019.
Mason, B., Jain, L.,, Tripathy, A., and Nowak, R. Finding all epsilon-good arms in stochastic bandits. Advances in Neural Information Processing Systems, 33:20707- 20718, 2020.
Jamieson, K. and Nowak, R. Best-arm identification algo- rithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference Information Sciences and Systems (CISS), pp. 1-6. IEBE, 2014.
Mukherjee, S., Naveen, K. P., Sudarsanam, N., and Ravin- dran, B. Thresholding bandits with augmented ucb. arXiv preprint arXiv: (XXiv:/704.0228) 2017.
Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S. On finding the largest mean among many. arXiv preprint 300.v:3306.39111 2013.
Tsai, T.-H., Tsai, Y.-D., and Lin, S.-D. lil'hdoc- an algo- rithm for good arm identification under small threshold gap. In Pacific-Asia Conference Knowledge Discovery and Data Mining, pp. 78-89. Springer, 2024.
Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S. ucb: An optimal exploration algorithm for multi- armed bandits. In Conference on Learning Theory, pp- 423 439. PMLR, 2014.
Zhao, Y., Stephens, C., Szepesvári, C., and Jun, K.-S Re- visiting simple regret: Fast rates for returning a good arm. In International Conference on Machine Learning, pp. 421 10-4488 PMLR, 2023.
Jourdan, M. and Réda, C. An anytime algorithm for good arm identification. arXiv preprint arXiv:2310.10359, 2023.
10

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
A. Additional Literature Review
A.I. Additional Review on (Katz-Samuels & Jamieson, 2020) and Others
(Katz-Samuels & Jamicson, 2020) put forward FWER-FWPD (Algorithm 2) to solve their proposed k-identification problem. which slightly different from the definition in this paper. FWER-FWPD an anytime algorithm, returning a subset R2 C [K] each round I, and never stops. The set R2 contains all the arms whose mean reward are believed to be greater than Hi up to time f. The set R1 is initialized the empty set. Algorithm FWER-FWPD sequentially adds more and more arms into R2 While (Katz-Samuels & Jamieson, 2020) do not provide explicit stopping time in their algorithms, in their analysis they consider another sequence of stopping times A min |Re n {a : Pa > No 2 k}, denoting the first round index whose R2 contains at least & qualified arms. Since the set (a: paa >> [o is unknown to the agent, Algorithm FWER-FWPD is unable to figure out the exact value of {As}, which is called Unverifiable Stopping Time. It is evident that A is equal to infinity, if {a: : Pa > }of = O. In this case, the algorithm FWER-FWPD may never stop with keeping R2 0, Vt N, meaning that the Algorithm FWER-FWPD cannot handle a negative instance v. For this reason, we do not conduct direct comparison between the FWER-FWPH and the algorithms in table 1.
If we apply the Algorithm FWER-FWPD to positive instance v, we can still derive conclusion by adapting the upper bound of EA1. Theorem 8 in (Katz- Sanuuls & Jamieson, 2020) guarantee that Pr(3t, R2 n {a 14 < mo0) < 106. Thus, we can consider stopping time 7 = min(t: (t: R2 * 0} as the termination round in our formulation. Taking à as the unique element in R,, we have Pr(Ha- < no)= I Pr(3t, R2 n {a : Pa < po)) < 106. It is evident that T S A1. By the upper bound mentioned in Theorem in (Katz-Samuels Jamieson, 2020) we have
EA1 So 500((
((151))
K m
log A
K + log
K (--
K log 3 log 8 ) A
1)
log
-1
m
The above bound can be taken as an upper bound of ET of the FWER-FWPD Algorithm in (Katz-Samuels & Jamieson, 2020) coupled with the stopping time λ₁. The sub-optimality of the above upper bound mainly comes from two parts. Firstly. the dependence on ô is log log log j instead of the commonly seen result log J. Then, in the asymptotic regime, i.e. + O, this upper bound is larger than all the upper bounds on positive instance in table 1. Secondly, the coefficient of log }/2 log log 1/ is the inverse minimum gap between qualified arms and Poo In the case A << 41,0, the upper bound is much larger than the lower bound, the upper bound becomes loose. This theoretical upper bound remains competitive only when the number of qualified arm m is proportional to K, and the 8 is considered constant. These are also the assumptions adopted by (Katz-Samuee & Jamieson, 2020).
There are research works aiming to output all the arms better than the threshold (4o- As previously mentioned, (Kano et al., 2017) aim to output all the arm sequentially and its first outputting round is indeed the т. Besides the fixed confidence setting adopted by the above papers, (Locatelli et al., 2016; Mukherjee et al., 2017) work on the fixed budget setting, which aims to maximize the probability of correct output given finite number of rounds.
Another related topic is c-Good Anm Identification. The agent needs to find all the arms (Mason et al., 2020) in fa Na 2 MM- - } or only one arm (Even-Dar et al., 2002; Gabillon et al., 2012; Kalyanakrishnan et al., 2012; Kaufmann & Kalyanakrishnan, 2013; Katz- SaazelS & Jamieson, 2020). In the second case, if the gap A is known to us, then the G-Goo Arm Identification and I-identification are equivalent by taking = A But it is unclear whether equivalence still holds the largest mean reward of on simple regret, under the fixed budget setting.
is unknown. Besides the fixed confidence setting, (Zhao et al., 2023) works
A.2. Comments on Table 1
Due to the space limit, we only present imprecise upper bounds for algorithm HDoC and APGAI in the table 1. Their actual upper bounds are larger, still suffering from the suboptimality discussed in the section 3. Following are more details.
Regarding algorithm HDoC, Theorem 3 in (Kano et al., 2017) proves for v E Spos we have
K log( K max n2/)
K
tmin [||i An,a oF
K(5 log zे
E,T < M1
+
2(A1, - -2e)2 + 8na +
2ca
4ea
2=2
where na
(Ao log
[A..e-o' log 5y K76
Av K78
(Ao.a -cyz ) ,
min
min Do.a; min aE(K]
Anati oE[K-1]
It is easy to see n1 2
s.

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
? log K/6)
1o5+ 2 4e
In addition, log(K maxje(k] n2) 2 Mloog log }),, suggesting that
46,1
k
log( K [ nz))
2( - 20)²
K
log log &
20
2( ((1,, 1,a 20)²
2=2
log log
20
2 ,
1
20 log log
Thus, we can conclude
H Hlg K x
K
+ H1 log log 8 2
K
'log(K K max ma n2)) 2(A1,a 2c)²
+ K
(min aE(K] A0, -0
K + log 22
Sn +
8ma
26
4e
2=
and the actual upper bound for v E S still suffers from the suboptimality from two perspectives mentioned in the section 3. The term 1 implies the upper bound can be infinity. And the term H1 log log(1/5) suggests there is still gap between the upper and lower bounds.
Regarding algorithm APGAI, (Jourdan Réda, 2023) do not explicitly provide upper bound for Er. Therorem (Jourdan & Réda, 2023) suggests
KT²
E S C (PM((8)
L,
8PM
6
Kx²
E & (m)
+
+ 1, E STRE
6
with definition
CROS (8) = sup
l:15
Σ
(Ve(1,0) + /3log()2 + DOos (ma)a
D
a:jta Z,o
K Σ
(8) = sup
titt
(Ve(t,ō)+ + v /logt) + D (1 iK
((Ha)a=))
0.a
K
1 2 4 log log(e")) +
2c(t, -W
22og
8
W- W_1(-e
logær
W-1 is the negative branch of the Lambert W function. And D ([Maa De 1= are further defined in the appendix in (Jourdan & Réda, 2023). From the above definition, know c(t, 2 2(log K) ), suggesting that (Vc(t,o) + logg 2)2 2 2(oog ). Further, we can conclude CTos (0) 2 (2(Hollg )) and CTT (5) 2 (HHT" )).
Thus, there exists a E [K], Pa = po for an instance v E Spm (P)x = co, resulting in a vacuous upper bound.
A.3. HilDoC,, HDDC,, APGAI are not (A, 6)-PAC
In this subsection, we are going to show lillDoC in (Tsai et al., 2024), HDoC in (Kano et al., 2017), APGAI in (Jourdan & Réda, 2023) are not (A, PPCC. To do this, we suffice to construct an instance y E Spos, such that E,T = +oo holds for all these three algorithms.
12

---

Near Optimal Non Non-asymptotic Sample Complexity of 1-Identification
Consider a two-arm instance with μ4 Mo = 122 Arm follows unit variance Gaussian and arm returns constant reward. Easy validate E Spos
Algorithm lilHDoC applies uniform sampling on 2 arms, by pulling each arm T times. With non-zero prob p. UCB, (t) < Ao holds for all s T. Then, arm I will get removed from the arm set, so as algorithm HDoC. In this case, both lilHDoC and HDoC will keep pulling arm without termination. other words, we find an event with positive probability, such that T = +00, We can conclude HDoCT = +o0, E.JHHDDT = +o0.
The same idea also applies to the algorithm APGAL With non-zero probability, the first collected sample from arm is below /Ag. Conditioned on this event, APGAI will keep pulling arm 2 without termination, meaning that Bx,APGAIT +00.
B. Analysis of Algorithm 2
B.1. Selection Rules of C, (ōx, Ock, 8k 1=
Regarding C, any C > 1 is available for the algorithm analysis. And C' will only impact the constant coefficient in the upper bound mentioned in Theorem 2, which is ignored as is predetermined.
Regarding {ōk, ark. 1:00 there are some restrictions on the decreasing/increasing speed of the sequence. Generally speaking, we require (6x 1 is decreasing sequence with limit zero and {ax, 3 ) are increasing sequences with limit infinity. And they should fulfill following properties
B&+1 2 2,3k. 9k+1 log ōk+1
2 2 log
8%
+00
8k- 3/ log Okk
< +00
+00
ak +00
Bg log
ak-1
1
S Okk 4
k=
With out loss of generality, we can take 8 9o ag 1. Considering all these requirements, taking 6z , Bx
2h, ag 5* is suitable choice. It is also possible find other sequences.
B.2. Proof Main Theorems
Before illustrating the proof of Theorem 5.2 and 5.3, we need some preparations. Section B.3 includes all the required lemmas complement the proof.
We firstly prove Theorem 5.2, which asserts Algorithm 2 is 8-PAC. Recall the definition of of 8-PAC, we need to prove (r < +0,, à E it (v)) > 1 d holds for any 8 (0,1) 1) and E SP U Here we split the proof into two steps. The first part is to show Pr(r < +o0) 1, which is guaranteed by Lemma B.2. Then, given the first step, we just need to show (ā E (v)) >
Equivalently, suffice to prove (r & i (v)) < 5 holds for any E (0, 1) and v E SPOs U Sueg.
Proof of Theorem 5.2. By the Lemma B.2, we know 7 < +oo with certainty. Thus, à E [K] U [None} in Algorithm 2 well defined with certainty.
For positive instance v,
Pr(a & (v))
<Pr(a = None) + Pr(ā
[K], Ma < mo)
8
E
X
òR + Uli
SPr 31 E, 36 <
3
K
< Mm
13

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Σ
X
Pr
3t E N, 3a E [K]. Ma < no,
Ut, Ka1
) > 1o
E X
8
Pr
3 E N.
+ Ut,
< po
+
3K
Σ1 s==
X
8 و ) > Mo
Pr
3 E N, Ea E [K] Ma < po:
1.5
Utt Kai
π²
8
<.
6
3
5
For negative instance v,
Pr(â & i(()))
= Pr((a E [K]
E.=
X
< Pr
31 E N, 3a E [K], Ma < po:
Ut,
> no
K(n
8 ?
5 < 6.
To prove Theorem 5.3, i.e the upper bound of (ET, need more preparations. As the sketch proof in section illustrated, the most important step is to find the upper bound of phase index such that that the Algorithm 3 starts to output correct answer with an appropriate upper bound of T
Since the proof is too long, we split the proof of Theorem 5.3 into two parts. In the first part, we prove the upper log A
+ (log ) 11fth) for the case v E Sp In the second part, we prove the upper bound ET < 0 peg (log? 1/2 + log f1(")), for the case v E ST Lemma B.4, B.6 and B.8 are required for the case v E SP And
bound ET S O
1
Lemma B.5, B.7 and B.9 are required for the case v E S
24(C+ 1) A1 L. [log2 192(C+1) w 1, where C-1
Proof of Theorem 5.3, positive case. Denote L' [log2
Easy to C+3'
K 00 + 7t and derive an upper bound for Er and E,st separately.
see L' < L". We split
Since take 8&= 2h 5x
have
24(C + 1)
H
By 220
K
+1 +1=
K
log
1
$ log
glog2
24C 11
log 3
(l0g2
24(C
1)2 12 +1) = 010g
115T0 (og
K
K
14108a
192(0-12
192(C 1)2
31"
wh
22.
w²Ag.1
A
11)2 1t log,
192(C + 1)2
1 = log A2,1
log
8 log
A
log
1+ logg
w²A2
We ignore constant C' as it is a predetermined constant in the Algorithm 2.
By the Lemma 1, B.8, we know the exploration period after phase max[ L'} will always output à E [K], μ4a > wpi + (1 - W) and the forced termination at line 8 never triggers. By the Lemma B.3, we know the exploitation period will return "Qualified" after phase max( I."), conditioned on the event Pa, wan (1 w) In summary, the algorithm must terminate no late than the end of phase max{<* kal L' L"}. By the Lemma B.8 we can conclude
4K
<0 (Kimax(n* 1/3 log Smax((oe_L1)
+
14

---

Near Optimal Non Non-asymptotic Sample Complexity of 1-Identification
log
K
+ log log
K
log
K
log log
( nit (1
33.1
max
max Df, Ag.
D
max
A 1,a b
a=2
4h'
4K'
00 0 log HP
+
0
K Byte log
KB log
+
8
1
H log
+
H1Th log
+0
11Th0 log
+0
H log
81"
K
1
4K
00
H
oss log
+
H
log
+
MS log
+
K log
8,00
ÓNa
0.1
Take expectation on both side, we have
4K
+00
4K
B log
3x log
Pr(n = k)
k=1
400
π 6k-1
4K 8F
Bk log
k=1
=Oogg K).
+00
1 Pr(n ks)
E Elog
log 6pm
8pm
+00
d log 8,
=0(1.
1
+00
1
E log
log
Pr(nt* 1:)
8Rt
8pm
2
+00
1
log
6
Oak
jnt
k=1
= =0().
Thus, conclude E, < O H log 48,1
The remaining work is prove an upper bound for E,st, Recall we take Bx 2 a = Is not hard to see for any integer N E N, we have +1 log 4kØN=1 >> 2 log 4Kax and E Bn log 4ka,, conclude
8= S BB log 4Kox-1 Thus,
fR R 1
4Kan
10003 log 8
4K (0
2000 m000mmmxx/ea ,", log
<o
(Bac Bece log
4K B log
4Ka, + Br. Bog
4Ka
8
holds with certainty. From the definition, we know BIN, an" $ <0(tt) ). Thus, we can conclude
log K + log
1d 20 Be
<0(Bce log 6
4Ka
4Kam
A
+ Br log
+0
A
15

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Take Expectation on both side, we get
a
+00
akat
E 0 log
Bk log
Pr(n = k)
4000
πT
4kax
3r log
6
8
k=1
K
(log
4kaga
+00
4K
EB log
3p log
Pr(nt = k)
2
4Kat
By log
6ak-1
8
<0 (log K).
log 4 +log 28.1
In summary, we have Eys < 0 Combining the following upper bounds,
2b.1
log K
+ log Do.1
E, 50
K 2
Er 50
HPSS log
we have proved the positive part of theorem.
The above completes the proof of inequality Er <0 ( log Do.
H1mm) for the E S The following is going to prove another inequality EEr S O(HTT 1 + log 1), v E Seeg Theorem 5.3.
+ (log
K
24 D
Proof of Theorem 5.3, negative case. Define L' 7t and derive an upper bound for EE and Era separately.
[log2
I" minsk 8 {}} =[log $7 We split
By the Lemma B.9 and B.5, we know
log
+ log log Ab.a
00
KB ( pim log
4K
+0
max ne)
Dg.0
4K KB log
4h
50
+
KB log
K
0(H log (e)ee)+
8pmm
1
1
0
11 (log
log
+ log
Similar to the proof of positive part, we can take expectation on both side and it is not hard see
4K"
KB log
=0
nog log H())
di/
4K
n
5x
4K
EK 9y log
K 3r log
S
O(K)
8,00
8x
km
16

---

Near Optimal Non Non-asymptotic Sample Complexity of 1-Identification
O log
50 (I1 log (!
1
1
O(H log
50
1 log
toc
E log
π
11
log 0%
< O(H
8,
6
1=
In summary, we can conclude Erdh & O ( (log 3 + H)
For the upper bound of lErS, the idea similar. From the Lemma B.9 and B.5, we know the exploration oracle would alway output áR = None for phase index & 2 max(x" L'}, and we can conclude
4Kan
100033 log
4K max(mm, D')+1
22000 m 11++1 log
6
so 60(8. Bee++ +1 log
4Kamu+1
(0 log 4Ka
+0
8
Apply the same calculation above, assert E7 I 00 20(1
K log
M log 19
8
Combining the upper bounds, get Er < 0
1/ + FT.
B.3. Supplement Lemmas
In this section, we illustrate more on the supplement lemmas of the main Theorems 5.2 and 5.3. The first lemma is about the upper bound the smallest round index k; such that the Algorithm SEE does receive âg Not Complete, conditioned on the concentration inequality.
Lemma B.1. Denote
113(log
2Kaa + log log AA 5
96
2 u 0,1
+ 11)(C+))>(lo))))
2K + log log 96(C++) 8c
113(C + 1)og K + log log 96(C+1)² 3
max (A 3,.
A
max max(A' (A A..)
K 113(log 5c
+ log log N
The
0,a
4=1
where w E (0, 1). Define
Tvve
pos = min
k:
pos
2 k
pos = min
1: Th 2 000
Tvve
nSS min
k:
2 n
2
We have L <
flog2
2)( mm5m
<
[log2
192(C+1)² A
nez < logg
w
Before the proof, we want to highlight reminder:
2
K
2
max A
A2 122
28.1
2
8(K - 1)
8K
H
+
A
max A0.
A
A
A
A
2
17

---

Near Optimal Non Non-asymptotic Sample Complexity of 1-Identification
Thus, we have [log2 21(++1)# Lemma B.I.
< [log2
192(C41)]
A 1. In the following appendix, we will continue to use the notations in
K
Proof of Lemma B.I. By the following calculation, we have
[1o
2K 8
+ log log w=
4kan
1000 log
8
w A
log
2K 8
+ log log
96
4ko
w A
8k log
8
w a
2
4K
96
BBx
log
log log
W
0
2
96
5
log w
W²
U,1
0.1
96
* 2 log2
w
W²Ai,1 0,1
22 k > log2
192(C + 1)2
w2 A
Thus, we can conclude L
< 1log2
192(C-1)²
113(C + (log
2K &
log log 90(C+1) Ab.1
K 113(C + (log 2K + log log
96(C+1)2
500 - 1)2 Bx log
4K
b.
max (2, A.... A...
òz
A
max m [. 4,,0)
o=2 2
(log + log log
2K
D6(C++12
2K + log log (log
96
4K
Ab,1
max A7 max
A Ag,a
< Bk log
8F
D
4K
2K 2 (log
=K3; Bg log
+ log log(96(C + 1)a 17 AP
5%
pos
log log(96(C C + 1)2 POS
3 2-
K
4K log
5x log(96(C (C + 1)
2HP
B 2 K
0%
4K
2* z 2H po
24(C + H1
3k
K
K
24(C + 1)² 11
k > llog2
K
Thus, we can conclude pos
Tog
24(C++1)2 11
K
Similarly, by the following calculation
K
2K 113(log dn
+ log log
96
4K
A.
500(C + 1)2 log
A
log 2K K
K log log
96 Ao
KK 3
+
log 1k
A2 0,a
log
1K
A ú,a
a=1
a=1
K
4K
96
<8g 2
K
log
> log log
Va E
[K]
K
0z
12
0,a
18

---

Near Optimal Non Non-asymptotic Sample Complexity of 1-Identiffcation
K
2
a==
Db.a
log
4K
2
log log
Va E
[K]
K
0%
A 0,a
10=1
A
4K
96
Ya
[K]
K
A
0
2o=1
K
A
2
K
24
22
K
3
K
0,a
24
o==1
loga
K
Σ
K
24
Thus, we can conclude L
llog2
K
Lemma B.2 (T must be finite). Apply Algorithm 2 to I-Identification instance have Pr(T < +00) = 1.
Proof pf Lemma B.2. Here we use the same notaion Lemma B.1. Since B& 2h, not hard see T 2 27 Thus when k 2 Les and the algorithm call exploration algorithm 3, have
k
2
T
27h
+
2
21
T%
Since at the start of phase ki, the
17 + |01 <
The
k- we can assert k 2 L can fulfill the condition of T Σx No +
113(C+1)((log 2 +log log 96r0+1122
113 2x +log log max a
47,1
Σx
in Lemma B.4. Similarly, 2 pos
A
a=
max A2 AB..)
113(log 2K log log
0G
can also fulfill the condition T
Lemma B.3. And 2 Do can fulfill the condition
w
113(C+1)* (log $ +log log #
T D Da=1 No +
Lemma B.5.
Recall the definition
Σ ===1
X
2 +
log
2K [Ki[ggg +
0 min
N E
Ma
du
t
t
Xet
2 . 2
2[ogg
{]
log
2Kaz ( [log 1)
R min
KeN:Va E [K).
1
a.a
Pa
For positive case, by the Lemma B.3, B.8, B.I, we know the algorithm must terminate at the phase max(x* ",, n Since the length of phase k is bounded by O(K By log 5.8 +0 or at = +o) = O.
Las }.
dag with certainty, we know Pr(r < +00) Pr(x
For negative case, denote L' minfk: & < ). By the Lemma B.9.B.1, we know the algorithm must terminate the phase max(L', k0e = Since the length phase k is bounded by O By log b.8) Pr(r < +00) = Pr( = +00) = O.
4ag with certainty, we know
The following lemma states the conditions that can guarantee the output of exploitation period (Algorithm 4).
19

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Lemma B.3 (Correctness of Exploitation Period), Conditioned the event
Ex= Xa
5 Ka
)
E
va E VEE,
Ha < Ut,
113(log 24 +log log
26 =
and à E [K), wpi + (1 - w)Hoo- IfT
Algorithm would output Qualified.
*113,1
Proof of Lemma B.3. For arm [K], pa > wii + (1 - w) and E N, we have
Σ
X 2.3
8
Ut,
po
Ka
8
Ha
(U, Ka
140
Ha Mabwni + (1- 20 (1,
8
< w(Hi - 10)
Ka
4 log
2Ka (2g(
V
112 2
log log w
Lemma 2.2g
WA
which implies the algorithm would return Qualified before the Ng is no less than T.
After the discussion the conditions of the Algorithm 4), the following two lemmas turn "good conditions" of the Algorithm 3.
Lemma B.4 (Property of UCB Rule, for Positive Case). Consider pulling process controlled by Algorithm 3. Assume the
imput H satisfies LCB, < po holds for all E [K] at line 2. Apply the pulling process to a positive instance and further
113(C+1) (log 2 +log log P6(0+112
113(C+1)²(og 24 +log log mas(a] 6.a
86(C+112
assume T T>EK No -
A6.1
+
K
We have
max| 23......
Conditioned on the event
{{
Σt
Xee <U
E
(K],
Ma
4 K
t
at the end of the pulling procedure (line 17), we have
(log 2K +log log
I. Na(H!) & max
No
max (3)
for E [K].
a
max (Ag A7
C-1 2. à E [K], Ma whi + w)Ho, C43
113(C+1) (log 2 +log log 0orc
Proof of Lemma B.4. For simplicity,
denote
T
Af.0
T
AP.
113(C+1)2(og 28 Hog log
SEC++132
113(C+1) 2K +log log mave 45 .f..
D61C+112
Not hard to see min(T T
A6.
max A6, Af..)
Consider a 2 2. For pulling times N, through the following calculation,
Σ
X 0.5
8
x= t
+ U(1, K
< pr
F
5
Ha
Ut,
-)
< μ1
K
20

---

Near Optimal aon-asymptotic Sample Complexity of 1-Identification
4 log
log(2t)
1
t
Lemma D.2
112 log
2k
5
64 64
log
A
96
A 2
64 log
log
we know (t) < < UCB, (t) + (a)t)= 2 log
26
+ 1.
Af.a
Af.a
Similarly, consider E [K] such that 14 < Ma S u1. through the following calculation,
-= X
8 2
C. UC,,
no
K
8 E Ua - (C+ Ull
R z μa
4log
2K (og(
=(C+1)
An.a
28(C + 1) log 2K
16(C + 1)2 log
log
(4((C+1))
Lemana D.2,
A
D
16(C+)) log log
24(0
we know that LCB.(t) > Po < (t) 28 lox 2K
Ag.
+ 1. Once LCB, 2 Nu happens,
A6,0 à.
the algorithm stops and take arm a as the output
We are ready to prove the first claim. According the above discussion and the condition LCB, < Pp, we know No T
holds for all [K]. We prove the first claim through the discussion on three cases.
113(C+1)*(og 2K +lug max A.. .7. 1..
#6(C+1)2
1. If No < T < T." the algorithm assures N₂ (H S To = max
No
max (A
as
64 log log
UCB, < μ1 < UCB = (2(*)) > 112 2
of.
1 and arm will never be the arm with highest
Af.
Af..
upper confidence bound before Na (H is no less than T/-
2. Tf No T." the algorithm never pulls arm its upper bound must below In this case, (aHe)) < NO max N70 1a3(C+) 2K +log log maxt 42 43
max (A) A
113(C+1)2(lg 2K +log log max 45 47
96
3. If No S T S T. the algorithm assures Na(H!)) T max No
max ( A..))
the algorithm will output a before its pulling time is less than T.
By the first claim, we know
K
K
113(C + 1log 1) 2K log log maxt D3 A
96(C+1)2
Na <
max
No 21
max A D.a A
a=1
K
2K + log log max A Af 113(C + 1)
96(C+1]
No
3
max A 1q,)
<T.
21

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Thus, the algorithm would not output Not Complete. From the good event E we know the à o None, since UCB, is always above Ho. We can conclude á E [K] We just need to prove pa > wam (1 w)jo-
Prove by contradiction. If å E [K] and Pa < win + (1 - w)No, we have
8 K (I + U(N((7"0- 1),
A,- ā, arg
max ISiSK
8
Pa,Na(Tm)) - C. C-U((((T
> 140
K
Pa - CUN((N(T - 1)) = - C. UNN((( -1,
-1, K
< 400-
As take Ul1 )) 2222max (1o0g (1.1) log 2K((Doxg
we get
Pa,Na(re) - CU((N((TT) > 140
* - /2 2ma (ToRg No(rm)).1) 1) log
2K[[log2 (T()))))2
5
> 140
Na(T)
Paa- (C 1) 122 2max ( (Nog (1(1))).1) log 2K([log; Na(19)))22
(T(
140
3wi/1 + +(1 (1-w)mo - -CC 1) 2 2max [log, (1(1=) log
2K 2K'[log, (1
> 140
Na(700
Exw(11 - -mo) > (C 1) 2 2max/ (lug, (11) log
2A [log, (1
Na
2w(H1 - mm) 2v 2- 2max
(log, [log, Na(1")).11 log
2 [lng No (a(m)))
C-1
Na (700)
On the other hands,
(a.Na(T--1) + - U(N((T"* -1) S m1
Euaa + +Na(" - 1)) S 11
w1/1 + +(1 - w))00 + 2UVNN( 1)) & SM1
2 2 2mmx (10g2 (a(r 17,13 log 2K (K(lo 11))
5
S - (1-w) - mO)
Na Na(r
2- 2max (log, -1(1)) log 2K([log, -1))
(1 (- - -Ma)
Na(r
2
Notice that
2m (1oog Na(r"))111,1 log 2K N₂ 11]
Na (7
Na(ro0) / 2max llog, No (1 log 2K([log, Na(r
Na(ree) -1 -1
Na(r
2/2. 2maxx/// logg No log 2k (logg Na(re))]
8
Na (r
22

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
and by w
C-1 C+3
(1- w)
1
C-1
4
2w
C+3
2
2
2(C + +3)
C
we can conclude
- -C-N))-CUUNN(F9)) {) 4d
K
8
-MaMa1-"1 + +U(Na(T - 11, K
S ln
5 P U'Na(T - 1)) < ( + + UNNi(T 1))
-A, #
We have found a contradiction. And we can conclude pa 2 E+3 + C43Ho, conditioned on the event E
Lemma B.5 (Property of UCB Rule, for Negative Case). Consider pulling process controlled by Algorithm 3. Apply the 113(C+1)) (log +log log 25,
pulling process to a negative instance and further assume Σk No + + Conditioned the event
A3.
Σ X uo.
E \Ya [K],
t, K
at the end of the pulling procedure (line 17), we have
113(1ng
28 + log log,
26
1. Na(H))) S max
NO a>
J. sor Va E [K].
forva
2. None
98 113(log 2K +log log
Proof of Lemma B.5. For simplicity, denote Ta
AG..
Consider 2 1. For pulling times N, through the following calculation,
Σ X a.e
8 Ut,
Mo
t
K
5m Ma +2. Utt,
R)
5
log
2K log (2t)
2
Au,a
112(log
+ log log A
Lemma D.2 1
A 0,a
86 112(log 2N +log log
A8.0
we know (t) < ne = N.(t) bound while UCB, < μo. the algorithm would stop and take à None. Thus, arm a will never get pulled once UCB, < no holds.
2
If arm still the arm with highest upper confidence
A
We are ready to prove the first claim, by analyzing the following two cases. For 2 1,
1. If No < Ta, the algorithm assures Na(H()) < Ta max No, Ta as the above discussion indicates.
23

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
2. If N2 Ta then the upper confidence bound of is smaller than the 14 the start of the algorithm. This arm will never get pull till the end of the algorithm. Thus, Na (HH No max max(Na, Ta).
Then, we turn to the second claim. From the good event, we know LCB, < pa < po holds for arm a E [K]. That means the algorithm will not output à E [K]. In addition, from the first claim, we know
K
2K 113(log
log log 96
5
Na
max
No a2
K
K
113( 2K
log log
96
27,
No
A 0
a=1
ST.
Then the algorithm must terminate before the round T. Since the upper confidence bounds of all arm E [K] are below Nus the algorithm will output à None.
The following lemma shows the condition of Lemma B.4 can be fulfilled in phase k > max N0T [logz 24(C+1)) 11
K
L.
Lemma B.6. Apply Algorithm to 24(C+1)) HTTh
positive 1-identification instance v. for phase index
k N
max
ne [log2
= L, before running the exploration (at the Line 2 of Algorithm 3), we have
K
(log 2K + log log
96(C-1)2
(log K o + log log 96(C+1)2 max A A0,0
A
T 2 1 + 113(C
max (A/,. 4
and LCB,(H (H 8x) μn holds for all E [K].
24(C+1)* "
Proof of Lemma B.6. By the Lemma B.1, we know to 2 flog2
implies
K
The > 113(C + 1)² 2
(log 2K Oz A
+ log log 96(C+1)
26,1
K (log
8
log log max
D6(C+1)
[A
max A2
0,a
Also, from the algorithm design, we know at the start of phase k. 17 < - Since we take 3r 24 we have
T
Combining these two results, have
(log
2K de
+ log log 96(C+1)' A
K (log 3 + log log max (A, 47,0
96(C+1]2
Th 2 2 + 113(C + 112
max A A7.
The remaining work is to prove (HLs, 8&) S Po holds for all a E [K]. before the start of phase We complete this by discussing the value of âx-1-
If â = None, we have LCB. 5ạ) < LCB.(H 5 LCB, (H 6x-1) S Po. forall E [K].
If à=-1 Not Complete, ut-1 [K]. Then we can further assert LCBB 0 5&) < LCB,,HHe 8p-1) < Po-
also assert LCB, (H 56-1) No. Va E [K]. or the algorithm would take
If ă E [K]. then we can firstly assert LCB, (H 6x-1) < no: Va # â Or the algorithm would output other arms instead of 0 Thus, we have LCB,, 5τ) < L.B., (Hee, 5k-1) < po, Va + â
24

---

96 Near Optimal Non-asymptotic Sample Complexity of 1-Identiftcation
Then, we turn analyze 0g-1- Before the execution of line 13, the following inequalities must hold
X + Σ s=
Xän-
òk-1 uk-1
C.
Noc
140
Nee Rx-1
K
No. Σ mm
Xāp-
On K
C.U 62-1
1,
S
Noe R6-1
Since we put the last collected sample X into Q. we can assert flaz-.
before the start of phase k must be
Eon - Xay- Since U (NEr 1, 8 R
> U
Nee 0c
1, K we know before the start of phase k.
Nap-1
LCBa, 1HH, 8&) < pa must hold.
ΣK
20
The following lemma shows the condition of Lemma B.5 can be fulfilled in phase k 2 max A [log2
L.
K
Lemma
B.7.
Apply
Algorithm
to a negative I-identification instance v. for phase index
k z
Σ
max
ce [log2
L, before running the exploration (at the Line 2 of Algorithm 3), we have
114(log
2K A
log log
96
Th 2 17 Σ
&
A 0.a
Proof of Lemma B.7. By the Lemma B.1, we know t: 2
floge
implies
K 114(log
2K 6n
+ log log A
T
A
Also, from the algorithm design, we know at the start of phase k 17 S T
Since we take 3r 2* we have
T
Combining these two results, have
K 114(log
2K log log
de
A
T 2 1700
A 0,a
Given the above preparations, we are now ready to bound 7. with certainty, for large enough phase index k. The following two Jemmas correspond to positive and negative instances separately. These two lemmas are also the final preparations for two main theorems 5.2, 5.3.
Lemma B.8.
Apply Algorithm 24( 2 H
to positive 1-identification instance for phase index
k 2
max KM llog,
=: L, we have
K
4K 81-1
Th
$1000(C + 1)2 log +
(log 2K + log log bn
96(C+1)3 A
K (log + log log max [ Ag
96(C+
114(C
22
max maxxA1 1 /, 0,0
a=2
holds with certainty, and āg [K], Mäy wii + w)Ho,, where w C43
25

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identiftcation
Reminder: Th is the total pulling times in all the exploration periods up end of phase k.
Proof of Lemma B.8. It is not hard see T 500(C + 1)2 log
1K d% 2 _- hold for all k 122 2. as Bx. -2. By the
Lemma B.I, we also know
24(C' + 1)
k 2
loga
K
(log 2K Ou
+ log log
96(C+1)2
(log K + log log 96(C-1)2
h 2
Ag.1
max ; 3g
113(C +
A
max A [,a= A 0,0
a=2
24(C+1) K
Thus, conclude for k 2 [log2
have
T T
Tee 2
2
(log
2K
+ log log 96(C++))
K (log 2K log log 96(C+1)2
A
max (Ai.a. 4. b.0)
2T + (18(++1))
A
max Ab.a
From the algorithm design, we know the total pulling times in the exploration period up to phase k - is at most k-1- By
the Lemma B.6, validate the conditions in Lemma B.4 holds for k: 2 max (n00, [log2 A(C+1)9M1 Thus,
assert 0z E [ Mäa, 2 wai + (1 wo. w C-1 for L. The remaining work is to prove the upper bound of rf. C43
In the following, induction prove
log 2K + log log max (A Ag.a
96(C++)2
N₂ Na(TE) I max
Na Na(IF-)
max D A..a)
holds for all A: > L, E [K]. By the Lemma B.4, we know the above inequality holds for k: = L, Va E [K]. Then if & holds, for the case of + 1, we firstly derive
log bx max Af, 28,
log log 96(C+1)2
No (o(T S max
113(C
max i.a1 A3 0.a
The reason similar the proof in the Lemma B.4.
log 2K +log log max (3) Sp,a) de+s
0
. Na 2 113(C+ + 1)²
from the condition k 2 ke we know
A A A....
X E
dk+1 K
0,5
Mo < Utt
holds for all t E N, E [K]. Following the same discussion in Lemma B.4, the algorithm will never pull arm a due to its upper confidence bound below fl, while the upper confidence bound of arm 1 is always above fl. Thus, Na Na(7f))
log 28 +log log ecc 1
If Na())) < 113(C + 1)2
maxt of 28.03
we can still conclude
max
Ag.
Σl X
8x+1 Ut,
Ho
t
26

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
would be either being output or stopping pulling before Na (7(1))) is less from the condition & 2 xee Then 96(C++122 than 113(C + 1)²
log 28 5641
+log log
max [4] -0,a)
1 A6.
Use the induction, we can conclude
log 2K
+ log log
96(C+1)2
Na(TH-1) S max
Na(Tg)) 113(C+11
0x+1
max / A 46,
max A A 0,a
log O2
log log
96 96(C-1)2
No Na(TL-1). 10,,,11,11000 113(C+ max
max
Aj 20,0
max A 1,a+ A
),a)
log 2K
+ log log max i Aon.
96(
de+1
+
max AA...
log 2K
+ log log max ( Ab.0)
96(C++) 1)2
66+1
Na(TE-1), 113(C1 +12
max
max A A
The induction is completed.
Then, for k 2 L, we can conclude
Lemmn 4.2
7
+
Na(Tf)
0=1
K Σ a=l
log 2K + log log max A 2
9)(C++1)2
0r+1
<K +
No Na(Ti-
113 1)?
max A 1,0 0.0
a=1
4K
<1000(C + 1)2 log
82-1
(log 6%
+ log log
96(C+1)3 A3
K (log K
log log 96(C+1)2
5
max [ax{AA] a
114(C + 1)
A 0.1
max(A; A1,a A3 b
am 2
Lemma
B.9. Apply 24 Ex
Algorithm 2 to negative 1-identification instance v, for phase index k
23
max
Ae [loge
K
=: L, we have
2K + log log D K 114(log
4K
by
< +)0(C+1))K3L-1 log 81-1
2
holds with certainty. And a None.
Proof of Lemma B.9, Similar to the argument in the proof of Lemma B.8, we conclude for phase index A >
Σx 22
[log2 K we have
The 2
7
k
2
27

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
2--- 113(1og
2K
+ log log
96
A6.0
A
From the algorithm design, we know the total pulling times in the exploration period to phase it 1 is at most T R-1' By the Lemma B.5, validate the conditions of Lemma B.5 hold for l proved 0 None for & ne
Σ
kte
[log2
Thus, we have
K
Σ
[log2
Ag.a
).
The remaining work is prove the upper bound of (1(r))
In the following, we use induction to prove
113(log
2K 3c + log log
96
(a(rg) max No(rE-1).
holds for all k 2 L, a E [K]. By the Lemma B.5, we know the above inequality holds for &t = L, Va E [K]. Then if & holds, for the case + 1, we can further derive
113(log
2K
+ log log Do
0x+1
Na(Tit1 S max No(rf²),
A2
The reason similar to the proof in the Lemma B.5.
113(log +lo log -)_
If (Tf)
0,00
from the condition & 2 k know
4
X Σ{=
8k+1
Ha Ut,
holds for all / E N, a E [K]. Following the same discussion in Lemma B.5, the algorithm will never pull arm due to its upper confidence bound is below Pa. If its upper confidence bound is the highest, the algorithm would output None.
Thus, Na(TEin) = (a(t))
113(1og 6441 +log log A
If (r
we can still conclude
X 6.S
8k+1 (t,
Ho
K
113(log 28 +log log 90
&g
2b.. A8..
from the condition 2 0 Then arm a will never get pulled before N₂ (T(rt) is no less than as its upper confidence bound is already smaller than μo before that happens.
Use the induction, we can conclude
113(log
+ log log
8es1
D
Nº (a(T S max
N. (,
A 0,a
2K 113 0%
+ log log
96 Ao.
113(log
2K 0241
96 + log log
D
max
(T
A 0,a
A
2K 113 113(log
+ log log
max
Na(TE_1)
8
20,0
A 0,0
28

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
The induction is completed.
Then, for k 2 L, we can derive
Lemma 4.2
T
S
K
Na (Tk)
113 2K + log log
96
<K +
Na (a(TT-1) Σ
8x
0,0
A 0,0
==1
a=1
114
2K o2+1
log log Do.a
96
4K
$1000(C* + 1)2 log
8
A
U,a
C. Lower Bound
C.1. Negative Case
Proof of Theorem 5.4. Following the section 2.1 in (Garivier & Kaufmann, 2016), define
Alt(v) (v/ (1/) * None),
and the kl-divergence between two Gaussian distribution d(N d(N(pa; 1), N(as 1)) (No Aa)2 the kl-diverence between bernoulli distribution kl 1 5) = log 1-5 + (1 6) log 8
Following the same step in the proof of Theorem from (Garivier & Kaufmann, 2016),
conclude
K
(Ha
Aa)
kl 1 - 8) < ETT sup WEÊK (EAL(())
inf
Wa
2
a=1
By the example in the (Degenne & Koolen, 2019), derive
K
Σ
supwes, inf inf Ex=1
K
Wa
(Mo Aa
2
a=
A
which means E,T 2 kl(5,1 5) Ex D
Q(H log !))
C.2. Positive Case
In this section, we slightly adapt the conclusion in(Katz-Samuels & Jamieson, 2020) and (Kaufmann et al., 2016) to prove theorem 5.5 and 5.6.
Proof of Theorem 5.5. For this instance v. take { as its permutation of the mean reward vector, such that the mean reward of the ith arm is Pa.- Then, we consider alternative instance v', whose mean reward of 4th arm is
Pa, < pa for some A 0. The answer set (²') (None). Apply the Lemma I in (Kaufmann et al.,
/4 140 A
Pa, > 140
2016), we get
M4 + 2)2 (n4
1E, No, (T) 2 kl(6, -8),
2
8 1-8 where kl(6,1 8) oog
+ (1 88)llog log 8
29

---

Near Optimal Non- Non-asymptotic Sample Complexity of 1-Identiftcation
2 uu. which implies (Ai-Po+ A)²
By the assumption, we have a 2 P2 2
(m]= S holds for all such that μui 2 Mo. Thus,
we can conclude
T
Σ
Na,a, (T)
(14 140 + 2)
Σ
N (r)
(11 14 + A)
2, 8)
(1 - pa + 2)2
Since kd 1 6) 2(log } and E,T
2k1(4, 1-6) (11 pm +2)
holds for all A > 0, conclude Eu,aigT 2 52(
log A
Proof of Theorem 5.6. The algorithm might take μ1 P40 M2 identifying I arm among good arm. We can directly apply the Theorem I in (Katz-Samuels & Jamieson, 2020) to derive lower bound, which asserts we can find a positive instance // whose mean reward vector is a permutation of vector {Ma 1K and the threshold pA, such that
MK prior knowledge and solve the problem by
ENT 2
(5)
A
AZ
a=3
1,0
By the Theorem 5.5, we can also conclude E,T 2 M Combining the result with (5), we get
1og
2 52
by the assumption μn > 140 > μ2 and d
Ao.1
112
To
K
E, 2 l
Σ
Q (H1).
AZ,a
C.3. Lower Bound for a Suboptimal Arm
Before proving Theorem 5.7, we need to firstly introduce lemma, talking about a "high probability lower bound" of the optimal arm, if is also the uniqe qualified arm.
Lemma C.1 (High Probability Lower Bound). Denote as a I-dentification Gaussian problem instance with fixed variance 1. Jm=n as the number of alternative arms and mean reward of all the arms v. If in > 140 > P2 > >> PK.
Denote K, {Ma K
then for any 10, and any 8-PAC algorithm,, we have
log
Pr(N)(7) C(ui - m0)2 2 1-16 8- 11-1-60 20 8-
-33
where can be any values greater than 1.
Proof of Lemma C.I. Define instance s' with mean rewards Ç1, (12, ... PK where i1 < 140- other words, the only difference between v and v/ the mean reward of arm while others are all the same. Since the algorithm 5-PAC, we know
Pr(output arm 1) >1
Pr(output none) >1 6.
of
Apply the transportation equality, we get
Ni(r)
> Pr(output arm E, (output arm exp
Σ
Zz,0
/
==1
30

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
expl (N 7
where 11 is the realized KL divergence, Z1, log
(As fai (2X1, 1.. p1)
X1. N(1,, 1). Or
expl A
we can directly assume Z1.s i.dd N ( "A)² (M1 ())))). Before moving on, we firstly prove concentration result for
the sum E 11.-- For any fixed number N, I, define CN. maxisIgN Ex= Z1.5 (m) (" < <T]. We can
assert Pr %,. 12 N -لليي (mn (onnn-n))))) (EN,J) 2 1 1-11--0 exp EN(HI-A1)) by the following application of maximal incquality (Theorem 3.10 (Lattimore Szepesvári, 2020)).
12
(M1 )212 >
Pr Zi A N [e] =
max ISISN
Σ
Z1,
(M1 )1)
Σ 21, > I
Pr
max ISTSN
2 ved - N(0,(P1 -1133)
==1
A= Nie1 A11
Pr
max ISTEN
II exp (1Z1.))
exp(AT)
21. N(0.( )))
$=1
Maximal Incquality
E
21.
22dd N(O.iu 100-i11-A11 2))
T==1 exp (ZZ1.0)
N
exp(AI)
NAP -
exp
2
1 2N
exp
exp(AT)
)2
To apply the Maximal Inequality, we need to validate (II exp (1Z1.)) J is a submartingale, which is not hard. By the Jensen Inequality, we have
+++
E
exp
(221.s)
II exp
(2Z1,5)
s=1
E exp (AZ1,0+1) )
II exp (AZ1.0)
s=1
E (AZZ,tz))
))
II exp (2Z1.)
2 exp
s=1
II exp
(221,))
Adding the concentration term into the transportation equality, get
8 > /' Pr(output arm
Ni(r)
-E, 1 (output arm 1) exp
Σ Zn,5
log
Ex (output arm () <
1u1)2 )
C(u
log 1
N.(r)
exp Σ
(Mi
121)
Z1.))
(N)
(#1 -2²z)
exp
2
2
log 1 2C (-20
log I
2 exp (-T) exp
E, I1 (output arm ())(N((7) < C(u )2
log
C0n R1
31

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
The last inequality is equivalent
log
log 1
exp(I)exp
2 E, Il (output arm 1) < C(pi p1)
2C
PH(AnB)aPYA)-PP((5) exp(T) exp
log
log 3
82 Pr((N(() < C(u =11)²"
Prr(-output arm
- Pr(-5
log t
2C
Cims 11m1-1112
log 2C
log 1
outputt arm 1) + exp(T) exp
++ @+Pr(-E
Pr(NN((T C(1i - 161)
lox
Oius A113
log 1 2C
C12
log 1
+8 + exp(I) exp
+ exp exp
Pr((N1(T)
2log 1
C(u1 =i1)2
log
log 1 2C
C12
PP((Ni(T) C(u )m))
2 1 - exp(1) exp
8 exp
2 log 8
Take I = 2 log I. we get
log
Pr(N)(T)2 C(u i1)
2 - 5 - 51-1 1 20 8
As the above inequality holds for any i4 < No, we can take 1i + po. Thus, Pr,(NN(T) >
log 1
2 1 -
5
C(p Ho
81- ---i-te vo - 8 87. We complete the proof.
Then, are ready to prove Theorem 5.7.
Proof of Theorem 5.7. Take M2 512 3 1536, MI 8M2.
Let 1 to be small enough, such that
exp (-4V3- -2) 2)
sup shs us Ao,a So.a
E Va 2.
2
In the following, we take μ1 as any value in (No, Ho + Ao,1l, and take A #1 14o- We are going to prove, for all a 2 2,
log a
we have (a) M.Aia
log A0.1 define instance v/g by taking the mean M,
Prove by contradiction. If there exists an arm 2 2, such that Na(r) <
2/40 - 11
i i=1
reward of ith arm as
2/0 Pe
i=
for all arm a E [K], a 2 2. In other words, "flip" the mean reward of arm 1
Mi and a, while keeping others the same as the instance v. From this definition, we know 1/2 E Soo. i²(v)) {a).
i i 1,a
By the Markov Inequality, we know
log 1
M₂
Pr Na(T)
2 1
M2
Mi
Define == minfr, minft: Ni(t) 2 Ag, have
}}. Then we get N1(T) 2 A
Ni(F)
According to the lemma C.I,
A
log /
Pr Ni(T) >
> - 3v8.
84
32

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Through simple calculation, derive
log A and Ni(f)
Pr
Na(P) -
M2
Do.1
log Ao.
1
Pr
Na(7) S M2 0,a
N1((T) 2
A
6<minf 2.227
log A
log 1
Pr
Na(T) -
NN(TT) 2
M2
8
log Dd.1 M2
log $
2 Pr
Na(T) S
- Pr Ni(T) <
8A
M2 3v8.
21
M1
Denote Na(F)
and (1(F)
the event, can apply the transportation equality in the Lemma
25,1
18 of (Kaufmann et al., 2016), we have
NI
(F
Pr(g) = (g1(g))))
Σ
Zz
Σ
Za,
s=1
s=1
where
exp( (X (11))-
(X1,s +11 -2110 - -(X1,- - 1m1) (2X1,s 2/10) - 2220)
Z1, log
exp(
[X + -2000)
2
2
exp(
(No.s~Mo)f
(Xa.s Ha - 2220) - (Xa,s 2 (2Xo, 2210
-210)
Zo, log
exp(
(Xa. tHo
-2po)" 2p00)
2
2
and X1, (11, 1), Xa,s ~ (uas 1). In other words, we can directly assume Zi, ~ N2222, 423,1) and Za,s
N22A a,a 2.
Let 71 be positive integers be determined. Denote the concentration event of realized KL.-divergence
& = max
maxixss 1515 Eim (7 - 2 S $1 Ea = max
El_ (Za,s 222 s Ta Similar to
log IstS
33,1
My
the proof of Lemma C.I, we can derive probability bound for both events E1, Ea. Notice that
El4- - 11) 111)
Pr Z, N(,
max I8tST
A= T/2
E2, (2,NN(
11T exp(A(Z. -1)
exp(AI)
exp( TA30²
3 exp(AA)
=exp(- 2T
holds for all positive and T. The first inequality guaranteed by the maximal inequality of submartingale (Theorem 3.10
33

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
in (Lattimore & Szepesvári, 2020)). By the above inequality, have
1
1
Pr((i) 2 exp
=
-xp
2
0,1
4A
8
1
M212
Pr(C.) 2 exp
exp
8 1og D
4
M2
Plug in these inequalities to the transportation equality, we get
Pr(g)
> (L) exp (-N1(FF) 240,1 -Na(F) 24
(i(F)
N.(F)
Σ am1
(Z),a 24
Σ
(Zz,a - 2.
exp
ER (E) exp exp (-N1())24 - Na(7)2A
(-p(-11-1 (l))
2 ZE, (()
log Do.1
exp
M2
24
A2
24
0,1
exp (-11 12)
21og Ab,1 2
2 (E) exp (-1 Ia) exp
exp
M2
2log D
2 2exp (-11 - La) exp
-2
(Pr(E) - -Pr(-E)) Pr((Ee))
M2
v
2 loog A
2exp (-11 - -aa) exp
M2
M2 358 exp
1212
exp( 12
1
Mi
8 1og A
Take 12
16 log A0,1"
11 = 4/3, 3/8 3. M2 = 512 x 1536, M1 = 8M2 we get
Pr(E)
2 log 1
1
2 exp
log
4/3
exp
M2
0,1
1
M2
exp(
exp(-3)
8
8
512
2
exp
(-4V3)
exp
-(
+
1
log
1
(1
exp
M2
exp(-3)
M2
4
A
8
512
1
(-4v3)
1
1
22
exp
exp
log
2
2
2
0,1
34

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
further
Pr
(I( 2
%/2
A 0.1
log 25.1 and Ni(e)= =
1
2 Pr
(a(F)= 1
Mz4g,a
4
(-4v3) exp
exp
log
-2
2
2
A
1
2 exp
(-4v3 -2) -2) exp
llog
+
log
A
A
0,1
1
2 exp
(-4v3 -2) exp
log
0
By the Markov Inequality, we have
exp (-4v3 2)
E N2.N 2 exp (-4V3- - 2) exp
log
2
2
200.1
exp( (4V3-)
From the construction of μr. we know T
200.1
supuresto
An,a
US Ap,a
ET contradicting to the fact that
V/2 E S So.e"
We complete the proof.
D. Technical Inequality
D.1. Inequality about z and log
This section includes some mathematics inequalities for simplifying calculation.
Lemma D.1. For any 2 a 2 O.
b 2 e², we have x 2 b 2a log log x 2 log(2) +
Ifb, a e, we have
+ a log log x < a log log(x)
The second inequality also implies x 2 a log log(z) xx) +b = x 2 b + a log logb.
Proof. We prove the first claim. Easy see d(x- xog then zo log To > Ho log(e2 + 2a log log e²) > Tig log e² (No, +0o). On the other hand, easy to check
log Take To + 2a log log b.
dx
x log
x logg
200 > a. Thus x a log log(z) - increases in the interval
a log log b
=b + 2a log log b log log(b + 2a log log b
log log a log log(t + 2a log log b)
=a (2 log log log 2a log log b))
=a (log(log b)2 - log log(b + 2a log log b))
(log 6)2²
=a log
log(b (b + 2a log log b)
(log b)2
Za log
log(b + 2b log log b)
35

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
b)) logb log(1 + 2 log b)
=a log
Notice that
(log b)2 - log - log(1 + log log b)
= log b(log b - 1) log(1 + 2 log log b)
626² log b log(1 + 2 log log b)
log b 2 log logb
2> log Va>0
0,
we can conclude 20 - a log log To - > 0 holds for all x 2 b + 2a log log b.
Then we turn to prove the second claim. As d(z-- log aoga=b) dx point of loga-a in the interval (e, b + log b). Thus,
x 2-g we know there is at most 1 zero
log
log
max eSagbra log log
a alg log z b maxfo a log bla=e, loggog b/2=b+a log log b.
Easy
e alogloge b- = e b< 0,
and
b + log log log(b log log b) b
=a log log b log log(b + a log l)
<alog log b log log(b) b)
=0.
That means
max eS25b bia log log
a looglog log b 0. The second conclusion done.
Lemma D.2. For any A (0,1),K 2,5 8 (0, 21, C 2 1, we can conclude
28C log
160 log
log
210
>
2 +
2
8C log
2K
802 log log, + 16C log log 21
2t
2
4 4log
2K (log, 20)2
+0
A
t
Proof. By simple caleulation, we derive
28C log 2K
160 log
21C2 log
42
1
A2
2
26C log 21
2K 8
320 log
loo
24 A2
2
2
2 log 320 log 2402 A²
2k 8
log
320 log(
2K
+1
2
2
bog( log y. N2,22
2 log 5
32C log
24 olog
A7
0
2t
A
A
36

---

Near Optimal Non Non-asymptotic Sample Complexity of 1-Identification
24C log 8
2K
32C² log
21C log
A²
+ log (log 2
0
2t
A
A
2240 log "
24C log A
2
32C log log
+1
A
Lemma D.1, 21C log 28 >e²
24C log 5
2K
16C log log (2t)
=
A
A
8C log 0
2K
+ 16C log log2 e + 16C² log (2g A loy 2t)
2t
2K log 20
0 + 8C log
log 2
st>
A
2C
log 2k à + SC log(log, 2f)
A/>
A
4 4log
(Io,, 20)2
+01
A.
t
D.2. Probability Bound of Good Event
+00 Lemma D.3 (Adapt Lemma 3 in (Jamieson et al., 2014)). Denote (x as i.d.d oL-subgaussian random variable with true mean reward μt = 0. For any 5 E (0, 1), we have
2(logg 2 loog t2
n²2
Pr
36
X,1
V 2022 11 log
Or equivalently,
2(oog2 t +2
n22
Pr
3t,
X²l V 2022 Dogg f log
5.
Lemma D.3 is fundamentally the same as the lemma 3 in (Jamieson al., 2014). The only different part is the constant outside the square root. But for simplicity and completeness, rewrite part of proof and leave it here.
Proof of Lemma D.3. Define us = 2 k 2 1. Define x = / 2202uu log 2(log, m²
S: = E X₃ and the event
2(log, )x
2(log, ux))
Es
max Se > V 22 log ISASuk
U
min IStSuR
S, < -1 20 log
8
8
For A > 0, notice that
exp(A(
Σ X.)) X
=exp(A
x.) Eexp((A))
2 exp((A
x.)) exp(XXX))
#=1
=exp(>(
X.)).
4=1
37

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
Take A
_ NNO
conclude (exp(AS,)) is a submartingale. Then,
Pr
max u
St 2 x
Pr
max exp(ASt) > exp (Az)) ssss
exp (ASuc)
exp (Ax)
"=
exp(
exp (Az)
expl 2u
Step * is by the maximal inequality for the submartingale. Take v u2 log
2(1oRg un)
we have
2(log2 uz))
2logg uz)2
8
5
Pr
max ISASS
Se 2 / 22 log
E exp -log
8
5
2(log2 uz
2k
For the part of Pr (minigtsu, St < -x), the proof similar. We can conclude Pr(Fx) S g² and further Pr(U S
6
Thus,
2(log, max (2 Inga +1, 2})²
Pr
3,,
X 2 /
20 max 2logg ( ,,, log
8=1
2(log2 4x)
Pr
3k; mAx 1ut
Σ X.12 2 //
20 log
s=1
228
PriUt S 6
Some Comments follows.
We can similarly prove Pr (3t X,l 2
2022[lon +1 log
2no 2 llw (1
8 holds for all 6 (0. 1).
65
Since [log, /1= 5 1 + log, L, we have
28
20 22uxx (loux 17.1) log 2(log, 2 2oooga f)2
36, Σ
X
2(log2 21)²
> Pr
3t,
X,
2
402tlog
E. Numerical Experiment
F. Settings of Numerical Experiments
The parameter setting SEE is 6g = 1 3+ 90 = 24 5* - 1.01. In all numerical experiments, all the algorithms
in section achieve 100% accuracy in identifying correct answer of either a qualified arm in a positive instance or outputting None in a negative instance.
38

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
We took number K 10, 20, 30, 40, 100, 150, 200 and the tolerance level 6 0.001, 0.0001. Fix Mo 0.5, A 0.15, set up 6 instances, by considering different number of arms whose mean rewards are above /4o For
number μk 0.25; (2) Unique Qualified, whose = PK = Pos (3) One Quarter Qualified, whose mean reward vector is | /1K/4++2 =
K, we define (1) AllWorse, whose mean reward vector is μ1 μ22
mean reward vector is μ11 = PAo + A, H2 = A3
μK = Mo: (4) Half Good, whose mean reward vector is #1 = P2 P2- -.. K/22| = do + A, μ1 K/2//+1 = P|2/21+2 = -..-------... PK- Pgi (5) All Good, whose mean reward
Jn = 12 = = |[//1| = 140 + A, ||
=
2(-1) 1 isisi K. vector #1 = = PK Ho + A (6) Linear, whose mean reward vector μ4, = 4o A + R
For instance "AllWorse", the set of correct answer is {None), while for the other instances which are positive, the answer set (v) contains at least one arm. In each experiment setting, we run 1000 independent trials and compute the empirical average of the stopping times.
To avoid an infinite loop in a trial, we set a forced stopping threshold 10 in each instance. All the algorithms, including SEE, HDoC, lilHDoC, LUCB_G, -aat, adapted-MS, stop in all trials before the total pulling times reach 10a
HDoC and LUCB G's performance on "All Worse" instances are very similar, leading to two nearly overlapping curves. The radius of each error bar is 3 times the standard error of the empirical stopping times across 1000 repeated trials. The error bars do not appear to be visible, as they are much smaller than the empirical stopping times.
When implementing the algorithm lilHDoC, its originally proposed length of warm-up stage is larger than the total pulling times of some of the benchmark algorithms. To allow comparisons, in our numerical experiment, we only uniformly pull all the arms 200 times for the algorithm lilHDoC.
E.2. Supplement Figure
Figure 2 compares the trend of empirical stopping times, when the proportion of qualified arms increases in positive instances. For algorithms adapted- TaS and add the empirical stopping times increase as the proportion increases, while for our proposed SEE, the trend is inverse.
E.3. Correctness of APGAI algorithm
Table 2. Number of Failure, APGAL, = 0.001
Instance Type \
10
20
40
50
AllWorse
0
0
0
0
Linear
0
1
Unique
373
449
462
520
549
OneQuarter
152
32
22
7
6
Table 3. Emprical Stopping times + 3 APGAI, 5 = 0.001
Instance Type \ K
10
20
30
40
50
AllWorse
5099 + 54
10703 + 78
16524 + 96
22450 + 114
28501 129
Linear
11800 + 2757
12814 + 5496
18145 = 11685
11979 + 8601
11819 +: 9723
Unique
201716 + 22404
485772 1 45444
749871 = 68136
1096819 + 91215
1454700 + 112848
OneQuarter
90246 17187
46501 + 17532
46890 + 22569
25511 + 17547
23000 + 19224
In compared to other benchmarks, APGAT's numerical performance is significantly different, the sense that the stopping time it either very small or very large, which makes its curve of stopping times either much below or much higher than all the others. And sometimes it might get stuck in a non-stopping loop.
We tune some of the numeric experiment setting to see the non-stopping phenomenon more clearly. For APGAI, we set the forced stopping threshold as 50000 * K, where K is the arm number. Once the total pulling times is no less than the forced stopping threshold, we mark this experiment as a failure, and take the forced stopping threshold as the total pulling times of APGAL. Table 2 records the number of failure for experiments K = 10, 20, 30, 40, 50 and instance type "All Worse", "Unique Qualified", "One Quarter", "Linear". The tolerance level 5 0.001, with repeating times 1000. Except the
39

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
SEE
TaS
MS
K=50, 6=0.001
K=100,
6=0.001
K=150, 6=0.001
Empirical Stopping Times
50000
16000
35000
14000
30000
40000
12000
25000
30000
10000
20000
8000
15000
20000
6000
10000
Unique
OneQuarter
Halr-
All
Unique
OneQuarter-
Half-
All
Umique-
OneQuarter
Halr.
All
SEE
TaS
MS
K=50, 6=0.0001
K=100,
6=0.0001
K=150, 6=0.0001
Empirical Stopping Times
50000
16000
35000
14000
30000
40000
12000
25000
30000
10000
20000
15000
20000
8000
10000
Unique
OneQuarter-
Half-
All-
Unique-
OneQuarter
Halr-
All.
Unique
OneQuarter-
Half.
All
Figure 2. Numerical Experiments on SEE and Benchmarks
40

---

Near Optimal Non-asymptotic Sample Complexity of 1-Identification
negative instance "All Worse", failure frequently occurs in some of positive instances. In the "Unique Qualified" group, least 35% of experiments end up with "failure". While in other groups, failure also occurs. In group "One Quarter", the number of failures decreases arm number K increases, suggesting APGAl's good performance relies more on the number of qualified arms, instead of the fraction of qualified arms.
The huge number of failure experiment also affects the estimation of the EP.APTIT Table 3 records the confidence interval for estimating EP.APGI ignoring the decimal. group "All Worse", there aren't t any failure, and the empirical mean group "Unique Qualified", failure frequently occurs. Both cases result in
outperforms all the other benchmarks. relatively small standard error in the numeric experiment. While for the group "Linear" and "One Quarter", the less frequently occurrence of failure greatly increase the standard error of the empirical mean stopping times. In some cases, 3*Std is nearly the same as the empirical mean value. In addition, because of the existence of the forced stopping threshold, the empirical mean we recorded is only lower bound estimation for the true APGAPT. Due to large standard error, we cannot conclude whether the current repeating times is sufficient to approximate EA,APGATT.
Given the time-consuming simulation for APGAI and significantly different pattern, we do not apply APGAI to instances with larger arm number. And we believe is unsuitable to compare APGAI with other benchmarks, given the difficulties of estimating APGATT.


Reviews:
[{"review_id": "1cxEj718Bz", "reviewer": "Reviewer_M2Aq", "summary": "In this paper, the authors consider the identification problem a pure exploration problem with bandit feedback, where the objective is to determine where there exists an arm whose mean reward is at least a known threshold or to output None if it believes such an arm does not exist. They proposed an algorithm termed sequential-exploration-exploitation and provided a non-asymptotic analysis of the sample complexity. More precisely, they provided non-asymptotic lower and upper bounds of the expected sample complexity and proved that they match up to a constant. Finally, they conducted experiments on synthetic environments and demonstrated that the proposed method overall outperforms the baselines.\n\n## update after rebuttal\nMy major concern was the poor readability of the paper. However, the authors provided a more intuitive explanation of the algorithm in their response, and I believe the paper could be improved in light of the points raised during the author-reviewer discussion phase. Therefore, I will keep my positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your suggestions. Let us respond below to the points raised, and we look forward to discuss more in the next iteration.\n\n1. \"If $\\mu_1>\\mu_0\\geq\\mu_2\\geq...\\geq\\mu_K$, does the lower bound work for all permutation of [K]\"\n\n     We cannot expect the current lower bound holds for any permutation of [K], but we can only guarantee there exists a permutation such that our lower bound holds.  Consider a \"naive\" algorithm which keeps pulling arm 1 until\n    + LCB_1>$\\mu_0$ holds or\n    + UCB_1<$\\mu_0$ holds.\n\n    If UCB_1<$\\mu_0$, it turns to keep pulling arm 2 until similar conditions hold. Then if the mean reward of arm 1 is indeed $\\mu_1$, its pulling complexity is $\\Theta(\\frac{\\log\\frac{1}{\\delta}}{\\Delta^2_{0,1}})$. The lower bound $\\Omega\\left(\\frac{\\log\\frac{1}{\\delta}}{\\Delta_{0,1}^2} + \\sum_{a=2}^K\\frac{1}{\\Delta_{1,a}^2}\\right)$ does not hold. But we can \"punish\" this naive algorithm by considering another permutation. Let the mean reward of arm K is $\\mu_1$, then this algorithm will suffer complexity $\\mathbb{E}\\tau\\geq \\Omega\\left(\\sum_{a=1}^K\\frac{\\log\\frac{1}{\\delta}}{\\Delta_{0,a}^2}\\right)$, which is much larger than the lower bound. \n\n2. \"The lower bound if $\\mu_1>\\mu_0\\geq\\mu_2\\geq...\\geq\\mu_K$ does not hold\"\n\n     + For the instance with multiple qualified answer, i.e. $m:=|\\{a:\\mu_a>\\mu_0\\}|>1$, we only know the lower bound $\\Omega(\\frac{\\log\\frac{1}{\\delta}}{\\Delta_{0,1}^2}+\\frac{1}{m}\\sum_{a=m+1}^K\\frac{1}{\\Delta_{1,m}^2})$. \n     + The proof is similar to Theorem 5.5, by combining the Theorem 1 in Katz \\& Jamieson 2020 and Kaufmann et.al 2016. In this case, the $\\delta$-dependent part of our upper bound is nearly optimal, but the $\\delta$-independent part is loose.\n     + Our current result is meaningful. Our result is the first to achieve nearly optimality of $\\delta$-dependent part in this case. \n        +  Also, $\\delta$ dependent and independent term in the bound are tight, for the case of unique qualified instance\n        +  **None of the existing algorithms can achieve same theoretical performance as us**.\n\n3. \"The readability of the paper could be improved.\"\n\n    Thanks for your suggestion. In our revision, we will focus more on explaining the intuitions and the reasons behind our algorithm design, which is carefully chosen so that our current bounds can be achieved. We welcome the reviewer to check out the 3rd point of our response to the reviewer eELW. \n\n(Primarily for addressing Reviewer d2eW) Here we also list the summary of pulling and stopping rules across different algorithms. The main difference between ours and existing work is \n+ we adopt decreasing tolerance level in the UCB expression. Equivalently speaking, increasing radius of the confidence interval.\n+ **we do not eliminate any arm.**\n\nComparison of sampling rule\n+ HDoC: lilHDoC pull arm by $\\arg\\max\\_{1\\leq a\\leq K} \\hat{\\mu}\\_{a,t}+\\sqrt{\\frac{2\\sigma^2 \\log t}{N\\_a(t)}}$.\n+ LUCB-G: pull arm by $\\arg\\max\\_{1\\leq a\\leq K} \\hat{\\mu}\\_{a,t}+\\Theta(\\sqrt{\\frac{2\\sigma^2 \\log \\frac{\\log N\\_a(t)}{\\delta}}{N\\_a(t)}})$.\n+ APGAI: pull arm by $\\arg\\max\\_{1\\leq a\\leq K} \\sqrt{N\\_a(t)}(\\hat{\\mu}\\_{a,t}-\\mu\\_0)^+$, if $\\max \\hat{\\mu}\\_{a,t} > \\mu_0$,\n\n   pull arm by $\\arg\\max\\_{1\\leq a\\leq K} \\sqrt{N\\_a(t)}(\\mu\\_0-\\hat{\\mu}\\_{a,t})^+$, if $\\max \\hat{\\mu}\\_{a,t} \\leq \\mu_0$,\n+ Our proposed SEE: \n   + UCB rule in exploration, but the tolerance level decreases (radius of confidence interval increases) at each phase,\n   + Keep pulling the same arm in exploitation.\n\nComparison of stopping rule\n+ HDoC, lilHDoC, SEE: \n   + LCB defined by $\\delta$ is above $\\mu\\_0$ for an arm, output qualified arm,\n   + UCB defined by $\\delta$ is below $\\mu\\_0$ for all arms, output None.\n+ APGAI: \n   + $\\max\\_{1\\leq a\\leq K} \\sqrt{N\\_a(t)}(\\hat{\\mu}\\_{a,t}-\\mu\\_0)^+ > \\sqrt{2c(t,\\delta)}$,\n   + $\\min\\_{1\\leq a\\leq K} \\sqrt{N\\_a(t)}(\\mu\\_0-\\hat{\\mu}\\_{a,t})^+ > \\sqrt{2c(t,\\delta)}$.\n    \nThe radius of our confidence interval is also defined by lil rule, but we improve the constant compared to the Jamieson et.al 2014. See appendix D.2.\n\nReferences \n+ Katz & Jamieson 2020, The true sample complexity of identifying good arms \n+ Kaufmann et.al 2016, On the Complexity of Best-Arm Identiﬁcation in Multi-Armed Bandit Models\n+ Jamieson et.al 2014, lil’ UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits", "claims_and_evidence": "The main contribution os this paper is non-asymptotic analysis of the sample complexity with matching lower and upper bounds. The claims are supported by Theorem 5.3 and theorems in Sec 5.2ms in Sec 5.2.", "methods_and_evaluation_criteria": "Theoretical results show the proposed method is $\\delta$-PAC with a nearly optimal sample complexity. Although the experiments use synthetic environments, considering the theoretical nature of the paper, I believe it is a standard experimental setting.", "theoretical_claims": "I have not checked proofs. A sketch of a proof is provided after Theorem 5.3, I have not checked the correctness of it.", "experimental_designs_or_analyses": "As I wrote above, the experimental design is standard for a theoretical paper.", "relation_to_broader_scientific_literature": "I believe that the 1-identification problem is practically important, and an optimal algorithm for it would be beneficial for even outside the ML community.", "essential_references_not_discussed": "To the best of my knowledge, related works are adequately discussed.", "other_strengths_and_weaknesses": "- Strengths\n    - They provided a non-asymptotic analysis of the sample complexity and proved that the proposed algorithm is nearly optimal.\n    - Experimental results on several problem instances support the effectiveness of the proposed method. \n- Weaknesses\n    - As far as I understand, the lower bound provided in Theorem 5.5 holds only for some problem instances $\\nu$. Also, the same theorem requires the condition $\\mu_1 > \\mu_0 \\ge \\mu_2 \\ge \\dots \\mu_K$ which does not cover all cases of positive instances.\n    - The readability of the paper could be improved. For instance, after Theorem 5.3, the authors provided a sketch of a proof over a half page. It is partially due to the short review period, but, I was unable to follow technical details. Would it be possible to move technical details to the appendix and focus on the main idea of the algorithms and proofs?", "other_comments_or_suggestions": "Related to the second weakness, is it possible to add theoretical properties (as propositions or lemmas) of each sub algorithms instead of providing very detailed descriptions of the algorithms?", "questions_for_authors": "1. By the statement of Theorem 5.5, there exists a positive instance $\\nu$ such that the inequality holds.  Does the lower bound provided in Theorem 5.5 hold whenever $\\mu_1 > \\mu_0 \\ge \\mu_2 \\ge \\dots \\mu_K$ holds, or does it hold for only specific instances?  Such an analysis is standard for related problem settings (e.g. BAI problem)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8CJWxYzNyr", "reviewer": "Reviewer_eELW", "summary": "This paper addresses the problem of 1-identification in stochastic multi armed bandits. In particular, given a reward threshold $\\mu_{0}$ an algorithm solving the 1-identification problem has to return an arm whose associated expected reward is greater than $\\mu_{0}$ whether it exists. The authors propose the fixed confidence SEE (Sequential-Explore-Exploit) method, exhibiting a non-asymptotic sample complexity. Additionally, the authors propose a lower bound for the sample complexity in the considered setting, showing that their proposal matches (up to logarithmic factors) the lower bound, thus being near-optimal. Finally, the authors validate their method against baselines, evaluating the empirical stopping time of the methods.\n\n## Update after rebuttal: I believe that including the comments provided by the authors during the rebuttal will enhance the paper. I maintain my positive score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your suggestions. We will correct the typos, and we look forward to discuss more in the next iteration. We will also remove part of the sketch proof to allow space for algorithm description.\n\n1. \"the reported plots do not show the confidence intervals\"\n\n    In fact, all figures indeed include the error bars, but many of these error bars are too small to be visible, especially in the experiment group \"All Worse\". Please check the notebook Visualize-Demo-Delta\\_0p15.ipynb in the supplement files for details.\n\n2. \"compare their method to some algorithm thought to address best arm identification\"\n    \n    + LUCB\\_G algorithm, one of the benchmarks, can be considered **an adaptation of BAI algorithm UCB** in Jamieson \\& Nowak 2014.\n\n    + In fact, a BAI algorithm without adapted stopping rule would fail to terminate with a qualified arm in the 2 arm instance $\\mu_1=\\mu_2>\\mu_0$. Thus, we only focus on BAI benchmark with adaptation like the previous point.\n\n3. (Also for d2eW) \"The paper is well-written and easy to follow until Section 4,\"\n\n    We will try our best to provide more intuitions on SEE in our revision. The complicated design seems to be needed for our current algorithm framework. In the following, we will show a simpler version, and discuss why this version fails to work. Then, we explain why we adopt the current design. An **informal and simpler SEE** is as follows. (We only consider positive instances)\n\n--alg starts--\n\nFor phase index $k=1,2,\\cdots$\n+  (Exploration) Run LUCB\\_G with previous exploration history and tolerance level $\\delta_k$. Stops when\n     +  LUCB\\_G stops and return $\\hat{a}_k$, or\n     +  The total pulling times in all exploration phase $\\geq T_k^{\\text{ee}}$\n+  (Exploitation) If $\\hat{a}_k\\in [K]$, keeps pulling $\\hat{a}_k$. Stops when\n     +  $\\text{LCB}_{\\hat{a}\\_k}^{et}(\\delta) > \\mu_0$, or\n     +  Total pulling times of $\\hat{a}_k$ $\\geq T_k^{\\text{et}}$\n\n--alg ends--\n\nwhere LUCB\\_G is in Kano et.al 2017, very similar to the alg UCB in BAI area. We wish at the phase $k$ such that $k\\geq \\max\\{\\kappa^{ee}, \\kappa^{et}\\}$ (i.e concentration inequality (3) holds), $\\beta_k\\geq \\Omega(1/(\\omega^2 \\Delta_{1,0}^2))$, we have \n+ the LUCB\\_G algorithm can guarantee $\\mu_{\\hat{a}\\_k}\\geq \\omega \\mu_1+(1-\\omega)\\mu_0$. \n+ Then the above algorithm terminates at the end of phase k. \n\nTo achieve this, we need to guarantee **at the start of an exploration phase k,**   $LCB\\_{a}^{ee}(\\delta\\_k) < \\mu\\_0$ **holds for all**  $a\\in [K]$. However, the above informal SEE **cannot** guarantee this. \n+ It is possible that at the end of phase k-1, we have $LCB\\_{\\hat{a}\\_{k-1}}^{ee}(\\delta\\_{k-1}) > \\mu\\_0$, \n+ the last collected sample of arm $\\hat{a}\\_{k-1}$ is so large, such that $LCB\\_{\\hat{a}\\_{k-1}}^{ee}(\\delta\\_{k}) > \\mu\\_0$ also holds. \n\nThis issue ruins the theoretical analysis of the above informal SEE. To fix this issue, we introduce a **temporary container** Q. \n+ If the LUCB\\_G returns arm $\\hat{a}\\_{k-1}$, we transfer the lasted collected sample of $\\hat{a}\\_{k-1}$ into Q from the exploration history $\\mathcal{H}^{ee}$. \n+ Notice that $LCB^{ee}\\_{\\hat{a}\\_{k-1}}(\\delta\\_{k-1}) < \\mu\\_0$ holds **without the latest collected sample**, then at the start of the next , we can guarantee $LCB\\_{a}^{ee}(\\delta\\_k) < \\mu\\_0$ **holds for all**  $a\\in [K]$. \n\nThis is indeed line 14-17 in our Algorithm 2. \n\nIf the phase k pull $\\hat{a}\\_{k-1}$ again, \n+ we transfer back the latest collected sample from Q to the $\\mathcal{H}^{ee}$\n+ as the concentration ineq (3) requires the empirical mean $\\hat{\\mu}\\_{a,t}^{ee}=\\sum_{s=1}^t X\\_{a,s}^{ee}/t$ to be **consecutive summation of indexes of collected sample**. We cannot drop any collected sample.\n\nThis is line 5-9 in our Algorithm 2.\n\nTo rigorously formalize the above idea, we have to spend much space in showing the details. Also, we improve the concentration inequality in Kano et.al 2017, which ends up with our current section 4. \n\nThere are also other ways to fix the issue, such as\n+ Drop all the collected sample in previous phases, and prove independent concentration ineq for each phase\n+ Use an extra concentration event, bounding $|\\hat{\\mu}\\_{a,t}-\\hat{\\mu}\\_{a,t-1}|$\n+ Create multiple algorithm copies like Katz \\& Jamieson 2020 or Chen & Li 2015\n\nBut all these methods will result in one or more problems\n+ lead to worse numeric performance\n+ impose harsh restrictions on the parameters $C, \\beta\\_k, \\delta\\_k, \\alpha\\_k$\n+ strictly larger logarithm factor \n\nConsidering all these pros and cons, we adopt our current algorithm design.\n\nReferences \n+ Katz & Jamieson 2020, The true sample complexity of identifying good arms\n+ Chen & Li 2015, On the optimal sample complexity for best arm identification\n+ Kano et.al 2017, Good arm identification via bandit feedback\"\n+ Jamieson & Nowak 2014, Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting", "claims_and_evidence": "The claims made by the authors are supported by both theoretical and experimental evidence.", "methods_and_evaluation_criteria": "The methods and the evaluation criteria are appropriate for validating the claims done by the authors.", "theoretical_claims": "I briefly went through the proofs, and the theoretical claims seems to be sound.", "experimental_designs_or_analyses": "I checked the validity and the soundness of the reported experiments. The only issue I feel to highlight is in the fact that in the experimental section the authors state that they made 1000 runs of the same experiment, but the reported plots do not show the confidence intervals. I suggest to show also the confidence intervals of the presented curves, in order to assess the statistical significance of the results.", "relation_to_broader_scientific_literature": "The authors propose, as they highlight and up to my knowledge, the first method solving the 1-identification problem providing non-asymptotic expected stopping time (in the fixed confidence setting). Moreover, the authors seems to provide the first lower bound for the sample complexity in this setting and they show their method to be nearly optimal.", "essential_references_not_discussed": "The related works section is complete and enriched by additional discussion in the appendix. The authors provide the reader with a complete overview of the contribution of the recent literature. I feel (up to my knowledge) all the essential references are discussed properly in this work.", "other_strengths_and_weaknesses": "**Strengths**\nThis paper makes a step towards the closure of the 1-identification problem for stochastic multi armed bandits. The paper is complete in the sense that the authors not only provide a novel method and its theoretical analysis, but also they provide the lower bound for the setting allowing for checking the optimality of the proposed method (and of other predecessors). Additionally, I appreciated the rich related works section and the parallel done with the best arm identification, motivating why it is not convenient to just apply a BAI method. Finally, I have appreciated the presence of the sketches of the proofs.\n\n**Weaknesses**\n1. The paper is well-written and easy to follow until Section 4, where the algorithm is explained. Indeed, the presented pseudo-codes are a little bit hard to follow, even if in the following part it is explained. I suggest to insert in the main paper a more conceptual version of the pseudo-code, leaving the current proposed version in the Appendix.\n2. This excess of complexity is a feeling that remains even for the section about the main theoretical results. I suggest just to report the core results, without the presented level of details in the main paper, for instance for what concern lines 349--364 (left).\n3. At line 304 (left) the authors cite a lemma in appendix, I suggest at least to say what this lemma is about in the context of the main paper.\n4. Besides the comment that I have previously posted on the experimental validation, and even if I think the amount of experiments is adequate for a theoretical paper, I suggest the author to compare their method to some algorithm thought to address best arm identification in order to further highlight the inefficiency of such methods in this setting.\n5. Minors: lack of running title; lack of text in Lemma 5.1; SEE in the abstract is expanded in Sequential-Exploration-Exploitation but in the following it is expanded in Sequential-Explore-Exploit; Lemma 4.2 needs to be restated in my opinion.", "other_comments_or_suggestions": "Typo:\n1. line 133 (right)\n2. line 149 (right)\n3. line 182 (left)\n4. line 262 (left)", "questions_for_authors": "See previous sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6f2lgmMnso", "reviewer": "Reviewer_K8WR", "summary": "This paper studies the 1-identification problem, a multi-armed bandit exploration problem with the goal of identifying an arm whose mean exceeds a given threshold. The paper introduces a new algorithm that achieves near-optimal non-asymptotic sample complexity. Theoretical guarantees establish its efficiency in both positive and negative instances. The authors also conduct numerical experiments that demonstrate SEE outperforms some baseline algorirthms.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Our primary contributions lie in the theory towards optimal performance on the 1 identification problem, and there could be misunderstanding in the numerical performance of AP-GAI. We are thankful for the perspective that motivates us to clarify more, and we look forward to discuss more in the next iteration. Let us provide the following clarifications:\n\n1. As discussed in the reviewing process, the main contribution is **we design a new algorithm with best performance guarantee**, compared to all the existing algorithms.\n\n2. Regarding numerical performance \n    + HDoC's curve is slightly below (within 3 standard error) SEE in the group \"Unqiue, $K=10$\" . In other groups, its curves are all above SEE.\n    + LUCB\\_G's curves are all above SEE.\n    + APGAI's curves are below SEE in group \"AllWorse\" and \"Linear, $K\\geq 30$\", Other are all above SEE.\n\n3. The numerical performance is of AP-GAI has to be interpreted carefully, different from other algorithms.\n    \n    + It is generally impossible for an algorithm to outperform all the others across all the scenarios. \n       \n       For example, a naive algorithm that keeps pulling arm 1 can defeat all the existing algorithms, if the optimal arm is exactly arm 1.\n\n   + In the plots in section 6, our proposed SEE outperforms all other benchmarks except AP-GAI. It appears from the figure that APGAI is can outperform our proposed SEE in some of the plots\n        \n       +  However, as stated in the section 6 and the appendix E, the plotted points in the Figure are only **lower bounds of the  the realized empirical stopping time $\\tau$ of AP-GAI**, thus the plotted lines for AP-GAI only serves as a lower bound but not the actual performance of AP-GAI.\n\n       +  In the \"Unique\" experiment group, AP-GAI always fails to terminate even after $8000\\cdot K$ rounds, making its performance much worse than all the others. In our evaluation, AP-GAI is the only algo that suffers from the non terminating issue.\n\n       + In other groups,  with some small but non-zero probability (Quarter 14/1000-52/1000, Linear 1/1000-3/1000), AP GAI stuck into non-stopping pulling procedure and we have to terminate it before the real termination. This results in the large error bar in the graph.\n\n       + Considering stability on overall performance, we feel that SEE is better than AP-GAI, since non terminating is a serious issue, and effectively means that the expected stopping time can be infinite. In our revision, we will emphasize the non terminating issue for clarification.\n\n4. The notations and definitions (\"None\", delta-PAC, ...) follow the convention in existing research, such as Kano et.al 2017, Degenne & Koolen 2019. We thank the reviewers for suggestion in improving the intuition about SEE. While the complicated algorithm design is necessary, we plan to provide more intuitions in our revision.\n\n5. Additional numerical experiments\n\nFollowing the reviews, we implement \n+ two extra benchmarks Adapted-TaS(A-TaS) and lilHDoC (see 8th point in our reply to reviewer d2eW)\n\n   Due to the time and space limit, we only present the result in K=30, $\\delta=0.001$, with 1000 independent repeating times\n+ an extra RealLfie instance in appendix I.1.1 of Jourdan & Reda 2023, **whose mean reward vector comes from real-world therapeutic protocols data**, $\\delta=0.001$, with 1000 independent repeating times\n\nFollowing table reports the empirical stopping times. We ignore the decimal number.\n\n| Method       | All Worse | Unique | One Quarter | Linear | RealLife(Extra) |\n|---------------|--------------|----------|----------|----------|------|\n| SEE(This work)  | 19885 $\\pm$ 60 | **11029 $\\pm$ 180** | **7106 $\\pm$ 154** | **9266 $\\pm$ 150** | **281 $\\pm$ 2** |\n| HDoC | 23601 $\\pm$ 42 | 12023 $\\pm$ 122 | 11313 $\\pm$ 108 | 13620 $\\pm$ 143 | 472 $\\pm$ 3 |\n| LUCB\\_G | 23601 $\\pm$ 42 | 18401 $\\pm$ 179 | 15114 $\\pm$ 136 | 18234 $\\pm$ 176 | 395 $\\pm$ 3 |\n| APGAI | **16496 $\\pm$ 33** | 143266 $\\pm$ 3548 | 14716 $\\pm$ 1504 | 8762 $\\pm$ 1262 | 1568 $\\pm$ 571 |\n| A-TaS(Extra) | 280904 $\\pm$ 377 | 32111 $\\pm$ 180 | 37393 $\\pm$ 277 | 38562 $\\pm$ 302 | 1766 $\\pm$ 8  |\n| lilHDoC(Extra) | 37099 $\\pm$ 50 | 14930 $\\pm$ 108 | 17542 $\\pm$ 125 | 19363 $\\pm$ 160 | 3610 $\\pm$ 0 |\n\nSEE ranks 2nd in the \"Allworse\" group and is the best in all the other groups. The extra numeric experiments also suggest the superior numerical performance of our proposed SEE.\n\nReferences \n+ Kano et.al 2017, Good arm identification via bandit feedback\n+ Degenne & Koolen 2019, Pure Exploration with Multiple Correct Answers\n+ Jourdan & Reda 2023, An Anytime Algorithm for Good Arm Identification", "claims_and_evidence": "I find it concerning SEE does not outperform all other baselines, even in the synthetic experiments. Based on the evidence provided by the authors, the APGAI method performs overall better, hence the limited impact of this work.", "methods_and_evaluation_criteria": "The method was only evaluated on the synthetic benchmarks. Evaluating it on real-world datasets, e.g., Yahoo! Today Module User Click Log, would strengthen the results.", "theoretical_claims": "I did not check the proofs.", "experimental_designs_or_analyses": "The experimental design of the synthetic benchmark described in Section 6 and Appendix E.1 seems sound.", "relation_to_broader_scientific_literature": "I am not familiar with the literature in the 1-identification domain, but based on these empirical results, the method seems insignificant.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "See other comments.", "other_comments_or_suggestions": "I believe the paper could be written much more clearly. For example, (the list is not exhaustive)\n* Abstract begins with: _Motivated by an open direction in existing literature_ - all papers are\n* L015: _or to output None_ - this is clear only to people using Python\n* L104: _It is obvious to see (∆, δ)-PAC is stronger than δ-PAC._ - you should be more precise in what stronger means\n* Page 4: All three algorithms took too much time to study, and their presentation could be simplified with a diagram\n* The paper could use a Conclusions section summarizing the main takeaways and discussing future work", "questions_for_authors": "Can you evaluate your method and the baselines on a real-world dataset and share the results?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fl9bfFTzhJ", "reviewer": "Reviewer_d2eW", "summary": "This paper studies fixed-confidence $1$-identification for sub-Gaussian distributions, where the learner should output one arm whose mean exceed a given threshold if it exists, and output none otherwise. This pure exploration problem with multiple correct answers has been considered under different names in the literature, e.g., Good Arm Identification or any low arm, and with slightly different variants. The authors propose an algorithm named  Sequential-Exploration-Exploitation (SEE), see Algorithm 1. This is a phase-based algorithm that call two subroutines at each phase, an exploration algorithm whose sampling rule is based on UCB indices (Algorithm 2) and an exploitation algorithm that only pulls the candidate answer from Algorithm 2 to verify it is actually a good arm (Algorithm 3). A non-asymptotic upper bound on its expected sample complexity of SEE is given in Theorem 5.3. For positive instance, the upper bound remarkably only features the gap between the mean of the best arm and the threshold. Two lower bounds have been derived on the expected sample complexity for negative instances (Theorem 5.4) and positive instances with only one good arm (Theorem 5.5). They also derived a lower bound on the number of pulls of suboptimal arms for positive instances with only one good arm (Theorem 5.6). The empirical performance of SEE is compared with the ones of several algorithms from the literature on several instances.\n\n**## update after rebuttal**\nIncluding the discussions will improve the paper in its revised version, hence I maintain my positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your suggestions, and we will correct the typos in the revision. Due to length limit, we can only answer part of the questions in comments. We are looking forward to discuss more in the next iterations.\n\n1. \"no non-asymptotic lower bound when the instance has multiple correct answer\"\n    + Please check the 1st and 2nd point in the response to the reviewer M2Aq.\n    + If there are multiple qualified arms, our upper bound is nearly optimal regarding the $\\delta$-dependent part, but the $\\delta$-independent part is loose.\n    + Despite that, **none of the existing algorithms can achieve same theoretical guarantee as us**. \n\n2. \"Motivation of temporary container Q and complicated alg design\"\n    \n    Please check the 3rd point in our response to Reviewer eELW.\n\n3. \"Theorems 5.5 and 5.6 require the instances to be Gaussian and not solely sub-Gaussian\"\n\n    + Gaussian dist with variance $\\leq 1$ is 1-subgaussian. Theorems 5.2, 5.3 work for all subgaussian instances, while Lower bound(Theorems 5.5, 5.6) show it is nearly tight in a sub-class of the subgaussian dist.\n    + It is generally impossible to expect the lower bound works for all 1-subgaussian dist. For example, if all the reward are deterministic, an algorithm pulling all the arms once can be $\\delta$-PAC with sample complexity $K$.\n\n4. \"differences of sampling and stopping rules among HDoC, LUCB-G, APGAI, lil’HDoC, SEE\"\n\n    Please check the last part in our reply to the reviewer M2Aq. The main difference between ours and existing work is \n    + we adopt increasing radius of the confidence interval.\n    + **we do not eliminate any arm.**\n    \n5. \"compare the lower bound of Theorem 5.6 with Proposition 2 in Kaufmann et al. (2018)\"\n\n    Summary of result:\n    + Sum up the lower bound in our theorem 5.6, we get $\\mathbb{E}\\tau\\geq \\Omega(\\sum_{a=2}^K\\frac{\\log 1/\\Delta_{1,0}^2 }{\\Delta_{1,a}^2})$, meaning the term $\\log 1/\\Delta_{1,0}^2$ in the Theorem 5.3 might be required.\n    + In Kaufmann et al. (2018), they derive the lower bound $\\Omega(\\frac{1-K^3\\delta}{K\\max\\\\{\\Delta_{1,0}^2, \\Delta_{0,K}^2\\\\} })$\n\n    We have $\\log 1/\\Delta_{1,0}^2$ in the numerator and no K in the denominator, suggesting that our bound is stronger. But we require more assumptions.\n    + Only $\\mu\\_1$ is above $\\mu\\_0$\n    + $\\mu\\_1-\\mu\\_0$ is sufficiently small\n    + we are required to output an arm while they do not\n\n6. \"Discussions on lilHDoC\"\n    + Synergizing HDoC with the lil rule, and their framework requires a warm up stage\n    + Derive an extra high-probability upper bound for each $N\\_a(\\tau)$, \n\n       $\\Pr(N\\_a(\\tau) < O(\\frac{ \\log\\frac{K}{\\delta}+\\log\\log\\frac{K}{\\delta\\Delta_{0,a}^2} }{\\Delta_{0,a}^2})) > 1-\\delta$\n      + in the case $\\Delta_{0,a}=0$, this upper bound is infinity\n      + still suboptimal as $\\log\\log\\frac{1}{\\delta}$ exists, and the upper bound is infinity for some $\\nu\\in \\mathcal{S}^{pos}\\cup \\mathcal{S}^{neg}$\n    + We will include this discussion in our literature review.\n\n7. \"lilHDoC, HDoC and APGAI might be $(\\Delta, \\delta)$-PAC algorithm\" \n    \n   Here we rigorously prove lilHDoC is not $(\\Delta, \\delta)$-PAC. Consider a two-arm instance with $\\mu_1>\\mu_0=\\mu_2$. Arm 1 follows unit variance Gaussian and arm 2 returns constant reward.\n   + With non-zero prob p, $\\text{UCB}_1(t) < \\mu_0$ holds after the warm up stage.\n   + Then arm 1 will get removed from the arm set. In this case, lilHDoC will keep pulling arm 2 without termination\n   + In an event with positive prob, $\\tau=+\\infty$. We can conclude $\\mathbb{E}\\tau=+\\infty$\n\n   Similar idea applies to APGAI, HDoC. They are not $(\\Delta, \\delta)$-PAC.\n\n8. \"Compare with TaS, MS, lilHDoC in numeric part\"\n\n    While we implement lilHDoC and an adapted version of TaS, the algorithm MS is incompatible with our model\n    + TaS is not designed for 1-identification. The only available stopping condition is provided in Theorem 10, Degenne & Koolen 2019 (S-TaS), which **doesn't provide an explicit value for \"large enough C\"**\n\n       We use the pulling rule in TaS, while adopt the stopping rule of S-TaS, using a lower bound on required C. **Equivalently, we remove the \"Sticky\" part in S-TaS**.\n    + lilHDoC's length of warm up stage is already much larger than the SEE in our numerical settings.\n\n       We set T=200 as the warm up pulling times for each arm.\n    +  MS only determines if an instance is positive or negative, but does not identify a good arm in the former case. MS does not solve the GAI problem, unlike SEE which both solve GAI and identify if an instance is positive or negative. Thus, MS and SEE cannot be compared on the same ground.\n       \n    Point 5 for reviewer K8WR shows the results.\n\nReferences\n\n+ Jamieson et.al 2014, lil’ UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits\n+ Kaufmann et al. 2018, Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling\n+ Degenne & Koolen et al. 2019, Pure Exploration with Multiple Correct Answers", "claims_and_evidence": "**Non-asymptotic lower bounds only on instances with a unique correct answer.** Theorem 5.4 holds for negative instances where the only correct answer is None. Theorems 5.5 and 5.6 holds for positive instances with a unique good arm. Therefore, there is no non-asymptotic lower bound when the instance has multiple correct answer, which seems to be restrictive. Could the authors comment on the challenges posed by instances with an arbitrary number of good arms ? Taking two arms as an example would already be valuable. My interest is sparked by the fact that non-asymptotic lower bounds are quite challenging to obtain for a pure exploration problem with multiple correct answers, as being correct on one instance doesn't necessarily imply that we are incorrect on an alternative answer due to non-unique correct answers. For example, in terms of $\\log(1/\\delta)$ dependency, the only tight lower bound in this case is asymptotic in $\\delta \\to 0$. As I am less familiar with lower bounds based on the random permutation model, I would appreciate having insights on the limitations of multiple correct answer for this kind of lower bounds.\n\n**Misleading statement on the matching upper and lower bounds on the pulling complexity.** Given the above comment on the fact that there is no lower bound for positive instances with more than one good arm, it is important to reformulate the statement that suggests matching upper and lower bounds for any instances. For example, Line 27-28 “achieve near optimality, in the sense of matching upper and lower bounds on the pulling complexity”  or “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.”\n\n**Gaussian instances.** To the best of my understanding based on reading the proofs, Theorems 5.5 and 5.6 require the instances to be Gaussian and not solely sub-Gaussian (as in Theorem 5.4). Therefore, this should be added to the statements, or the proof should be adapted. For Theorem 5.5, this comes from Lines 1444-1446. For Theorem 5.6, this comes from lemma C.1 which is used in the proof.\n\n**Non-asymptotic upper bound of Theorem 5.3.** Even though $\\gamma$ seems to be an absolute constant, it would be valuable to have a more explicit closed-form constant. This would allow to better understand the impact of each of the hyperparameters used in SEE. Based on a detailed reading of the proofs, it is not possible to clearly extract a formula from the proofs that heavily rely on $O(\\cdot)$ notation. Moreover, it also seems like this constant will be very large.\n\n**Non-asymptotic lower bound of Theorem 5.5.** While I understand the need to restrict the parameter $\\delta$, it is not clear why the authors restrict themselves to mean parameters in $[0,1]^{K+1}$. Could the authors comment on where they used this condition and why it is important ? This seems unnecessary based on the existing literature proving adopts the random permutation model to prove lower bounds, e.g. Simchowitz et al. (2017, The simulator: Understanding adaptive sampling in the moderate-confidence regime), Chen et al. (2017, Nearly instance optimal sample complexity bounds for top-k arm selection), Al Marjani et al. (2022, On the complexity of all $\\epsilon$-best arms identification) or Poiani et al. (2024, Best-Arm Identification in Unimodal Bandits).\n\n**Non-asymptotic lower bound of Theorem 5.6.** Similar question, namely why the boundedness of the mean parameters is important. In that case, the condition $\\delta< e^{-8}\\approx 3. 10^{4}$ starts to become restrictive for practical application. Could the authors comment on whether finer analysis would allow to get a weaker condition on $\\delta$.", "methods_and_evaluation_criteria": "See “Experimental Designs Or Analyses” section for details on the empirical evaluation.", "theoretical_claims": "I checked the correctness of the theoretical results. The depth of my proofreading is detailed in the question on “Supplementary Material”. I highlighted some typos or minor errors in the question “Other Comments Or Suggestions”.", "experimental_designs_or_analyses": "For varying dimension ($K \\in \\{10,20,30,40,50\\}$) and confidence level ($\\delta \\in \\{10^{-k}\\}_{k \\in \\{2,3,4\\}}$), the experiments consider multiple instances with and varying that address specific cases of interests: one negative instance (AllWorse) and several positive instances. The positive instances have either two groups of arms and varying number of good arms (Unique versus OneQuarter), or have linearly decreasing mean (Linear). The experiments are repeated $1000$ times and errors bars are shown.\n\nWhile the experimental setup is convincing, three important benchmarks are missing: Track-and-Stop, Murphy Sampling and lil’HDoC. Updating the plots with those benchmarks will go a long way to provide satisfying empirical evidence on the performance of SEE compared to existing algorithms.  This is important and possible during the author-reviewer discussion, at least to have preliminary results.\n- Track-and-Stop (TaS) algorithm from Garivier and Kaufmann (2016) adapter to GAI. Namely, on top of forced exploration and based on C-Tracking, the optimal allocation is the Dirac distribution on the empirical best arm when the empirical best mean exceeds the threshold, and it is inversely proportional to the inverse square mean gap to the threshold otherwise.  A more detailed description exists in Appendix I.2.3 of Jourdan and Reda (2023). As TaS is a reference algorithm for fixed-confidence pure exploration problems, it is important to include it. Appendix I.5 of Jourdan and Reda (2023) suggests that it performs well.\n- Murphy Sampling (MS) algorithm from Kaufmann et al. (2018). The improved stopping rule of MS is tailored to a slightly different pure exploration problem (Section 5), i.e., return whether the instance is positive without returning a good arm. However, the sampling rule of MS can be used for GAI when combined with the  recommendation/stopping rule in Section 4 of Jourdan and Reda (2023). Appendix I.5 of Jourdan and Reda (2023) suggests that MS performs well.\n- lil’HDoC algorithm from Tsai et al. (2024, “lil’HDoC: An Algorithm for Good Arm Identification Under Small Threshold Gap”). Since it numerically outperforms HDoC, it is important to understand whether SEE outperforms it. See “Relation To Broader Scientific Literature” for more details.", "relation_to_broader_scientific_literature": "The authors should rephrase the following false (or at least misleading) statement on the literature (L 147-150). “HDoC and APGAI are both $\\delta$−PAC algorithm, but they are not $(\\Delta, \\delta)$-PAC, as they both suffer from the infinite complexity issue, i.e. the upper bound of $\\mathbb E[\\tau] = + \\infty$ if there exists an arm $a$ whose $\\mu_a = \\mu_0$”. While the known upper bound on the expected sample complexity of both algorithms tends to infinity, it doesn’t imply that the expected sample complexity goes to infinity. In order to prove such a statement, one would need to have a lower bound on the expected sample complexity that tends to infinity when there exists an arm $a$ whose $\\mu_a = \\mu_0$. Therefore, the current known results don’t imply that  HDoC and APGAI are not $(\\Delta, \\delta)$-PAC. While it seems legitimate to conjecture that APGAI might not be $(\\Delta, \\delta)$-PAC based on the empirical evidence, HDoC might still be $(\\Delta, \\delta)$-PAC.", "essential_references_not_discussed": "To the best of my understanding, the authors totally omitted one key related work, namely Tsai et al. (2024, “lil’HDoC: An Algorithm for Good Arm Identification Under Small Threshold Gap”). This paper proposes lil’HDoC, which builds on HDoC by using the law of iterative logarithm. Similarly, as for HDoC, lil’HDoC is designed to sequentially return all the arms above a given threshold. It is $\\delta$-correct for this task (Theorem 1) and enjoys guarantees on the sample complexity to return the $k$-th best arm above the threshold (Theorem 3). Using their Theorem 3 for the best arm of a positive instance yields a high probability upper bound on the sample complexity scaling as $O(\\Delta_{0,1}^{-2} \\log(\\log(\\Delta_{0,1}^{-2}/\\delta)/\\delta))$. While being guarantees in high-probability, it seems reasonable to expect that lil’HDoC is also $(\\Delta, \\delta)$-PAC. Moreover, given the improved performance of lil’HDoC compared to HDoC, it is quite important to compare it with SEE.", "other_strengths_and_weaknesses": "**Lack of conclusion.** The paper cruelly lacks a conclusion that summarizes the contributions and discusses open problems. Could the author write a sketch of the conclusion that they would add in a potential camera-ready version ? Even in the submitted version, some spaces should have been saved to write a proper conclusion. For example, one could put in Appendices some plots showing the impact of $\\delta$ for all the instances in Section 6.\n\n**Lack of algorithmic simplicity.** It’s worth noting that SEE is quite convoluted algorithmically speaking, and some components exist only for the sake of analysis. \nFirst, this is a phased-based algorithm which calls two distinct subroutines at each phase (Algorithms 2 and 3) that do not share samples. This seems to be wasteful. Could the authors elaborate on whether the lack of sharing between observations is only to facilitate the analysis, or whether it is rooted in more fundamental reasons ?\nSecond, the authors mention that the temporary container $Q$ exists only to “facilitate our theoretical analysis”. Could the authors discuss the challenges that arise from simplifying the algorithm by removing the temporary container $Q$ ? It would be great to actually remove this altogether.\nThird, there are four hyperparameters with arguably “subjective” choice of default values, i.e., $C$ and $(\\alpha_{k}, \\beta_{k}, \\delta_{k})$. \nFourth, it is unclear to me what is the intuition behind the exploration and exploitation horizons $(T_{k}^{ee}, T_{k}^{et})$, which are very large. For example, with default hyperparameters values, we obtain $T^{ee}_{1}/K \\approx 20.000$. Therefore, the first exploration horizon is actually larger than the empirical stopping time in the experiments of Section 6. \nGiven the simplicity of the GAI setting, it seems unsatisfactory to solve it with a convoluted approach.", "other_comments_or_suggestions": "- Theorem 5.4 could be stated more precisely instead of using the $\\Omega(\\cdot)$ notation. The authors show that $\\mathbb E[\\tau] \\ge \\log(1/(2.4 \\delta)) H_{1}^{neg}$.\n\n- Theorem 5.5 could be stated more precisely instead of using the $\\Omega(\\cdot)$ notation. The authors actually have a result that is not too difficult to state in details.\n\n- End of page 12 to beginning of page 13. The $\\delta_{k-1}$ and $\\alpha_{k-1}$ should not be moved outside the sum over $k$.\n\n- Line 617. $\\beta_k = 2^k$.\n\n- Lines 618-621. There seems to be an error in the block equation. Since $3^{\\log_2(x)} = x^{\\alpha}$ where $\\alpha = \\ln(3)/\\ln(2) >1$, the authors should obtain that $1/\\delta_{L’} = O((H_{1}^{pos}/K)^\\alpha)$ and $1/\\delta_{L’’} = O(\\Delta_{0,1}^{-2\\alpha})$. Instead, they claim that the same upper bound holds with $\\alpha=1$. This doesn’t seem to change the main result, as only $log(1/\\delta_{k})$ terms appear.\n\n- Lines 702-705. The first $\\delta$ should be a $\\delta_{k-1}$ and the last inequality should be $\\log(K/\\delta)$.", "questions_for_authors": "1. Could the authors discuss in more details what are the differences between their sampling rule and stopping rule and the ones used previously in the literature, e.g., HDoC, LUCB-G, APGAI and lil’HDoC.\n\n2. To the best of my understanding, the sampling rule used in Algorithm 2 seems to bear similarity with lil’UCB from Jamieson et al. (2014). Could the author highlight the differences ?\n\n3. Could the authors compare the lower boundof Theorem 5.6 with Proposition 2 in Kaufmann et al. (2018) ? Both seems to say something on the expected number of selection of suboptimal arms.\n\nSeveral other questions have been asked in the previous sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the fixed-confidence “1-identification problem,” which is one of the important problems in pure exploration in multi-armed bandits. In this problem, the algorithm is given a certain threshold value, and if it believes that there exists an arm whose mean exceeds that threshold, it outputs one such arm; if it believes none exist, it outputs “none.” The authors propose a new algorithm called SEE and provide a non-asymptotic theoretical analysis. Furthermore, they prove a lower bound and demonstrate near-optimality.

The reviewers pointed out issues with the statement and presentation of the results (Reviewers M2Aq and d2eW), the algorithm description (Reviewer eELW), and a lack of comprehensiveness in the experiments (Reviewers eELW, K8WR, and d2eW). However, it was discussed that these can be addressed through revisions in the camera-ready version.

Considering that non-asymptotic theoretical analyses have already been provided in the closely related topic of good arm identification, the contribution may seem somewhat incremental. The authors also discuss the assumption of $\mu_a \neq \mu_0$, but this appears to be a minor difference.

Nevertheless, I believe that the research topic and results are indeed important to the community and have practical implications.
Decision: Accept (poster)