The Batch Complexity of Bandit Pure Exploration
Authors: Adrienne Tuynman
Rémy Degenne
Venue: ICML 2025 poster (2025)
Keywords: bandits
batched learning
pure exploration
Primary area: theory->online_learning_and_bandits

Abstract: In a fixed-confidence pure exploration problem in stochastic multi-armed bandits, an algorithm iteratively samples arms and should stop as early as possible and return the correct answer to a query about the arms distributions.
We are interested in batched methods, which change their sampling behaviour only a few times, between batches of observations.
We give an instance-dependent lower bound on the number of batches used by any sample efficient algorithm for any pure exploration task.
We then give a general batched algorithm and prove upper bounds on its expected sample complexity and batch complexity.
We illustrate both lower and upper bounds on best-arm identification and thresholding bandits.

The Batch Complexity of Bandit Pure Exploration
Adrienne Tuynman'
Rémy Degenne
Abstract
delay between giving a treatment patient and seeing the effect can be on the order of months. It is not possible to use fully sequential algorithm, which would take too long. Moreover, adapting at each time step can have high computational cost.
In a fixed-coffidecce pure exploration problem in stochastic multi-armed bandits, an algorithm iter- atively samples arms and should stop early as possible and return the correct answer to a query about the arms distributions. We are interested in batched methods, which change their sampling be- haviour only a few times, between batches of ob- servations. We give an instance- -eeeeneed lower bound on the number of batches used by any sam- ple efficient algorithm for any pure exploration task. We then give general batched algorithm and prove upper bounds on its expected sample complexity and batch complexity. We illustrate both lower and upper bounds on best-arm identifi- cation and thresholding bandits.
This motivates looking into batched algorithms: the algo- rithm pulls multiple arms within a single batch, and can only observe the results at the end of the batch. An advantage is that all arms in a batch can be pulled in parallel, reducing greatly the length of the test in applications with large delay, Its lessened adaptivity also reduces the computational cost. Of course, being less adaptive than a typical bandit method could lead to worse algorithms. The key question is then how few batches one can use while keeping a performance comparable to a fully sequential algorithm.
1.1. Fixed Confidence Pure Exploration
We study K-armed bandit models, which we represent by a vector of real distributions with the vector of means denoted by μ4 (J4)EE]K] At each timestep / E N, agent interacts with the bandit by choosing an arm i [K] to sample. It then observes Xt,,, a realization of Vi, and proceeds to the next step. One common objective is regret minimization, where the agent must maximize E Xt..l-- See (Bubeck et al., 2012; Lat- timore & Szepesvári, 2020) for extensive surveys. We focus another goal, pure exploration, in which the agent must answer question about such as identifying the arm with the highest mean (Even- -Dar et al., 2002; Kaufmann et al., 2016). In pure exploration problems, we have a set Z of pos- sible answers, and a function μ1 + i ((L) E I that depends on the means of the distributions and provides the unique correct answer for that instance. For a given pure explo- ration problem and vector of means μ., we denote by All,, the set of vectors of means fı' such that i" (xx') # i (44). Essentially, Alt,, is the set of means that disagree with p.
1. Introduction
((i){E(K) with finite means,
A Multi Armed Bandit (MAB) is a model of sequential interaction that was introduced in (Thompson, 1933) to cre- ate better medical trials. This framework has since been expanded to various fields, and has seen applications to on- line advertising and recommendation systems. In MAB, an algorithm chooses at each time an arm among finite number (it pulls it) and then observes sample from prob- ability distribution associated with the arm. The goal of the interaction will be to identify quickly which arm has the distribution with highest mean.
By making use of past observed rewards to continuously update the way they sample, MAB algorithms reach their objective faster than traditional fixed randomized trials. For applications like online advertising, obtaining feedback can be quick, if for example the feedback is click an ad- vertisement. Adapting after almost each interaction is then feasible. However in applications like clinical trials, the
A pure exploration algorithm samples arms in a bandit in- teraction (following a sampling rule) until a time at which it decides to stop (with a stopping rule). Once stops, it returns an answer i I. good pure exploration algo- rithm should have low probability of error Pe + i (n)) and stop quickly (use few samples). When the number of samples is fixed and the objective is to minimize the proba-
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189- CRISIAL, F-59000 Lille, France. Correspondence Adri- enne Tuynman sadrienne.tuynmann @ fr>, Rémy Degenne <remy.degenne www.deeennnneiiiiff...... @n..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Batch Complexity of Bandit Pure Exploration
bility of error, one talks about fixed-budget pure exploration (Audibert et al., 2010). We consider instead the fixed con- fidence objective, in which the probability of error is fixed and the agent aims to achieve it with the minimum number of samples. We focus on d-correct algorithms. That is, algorithms that satisfy Pi + {W)) S 6 (Garivier & Kaufmann, 2016).
We will prove results for general identification problems, and specialize them three particular cases. Let be permutation such that (l(11) .... Po(K).
In Best Arm Identification (BAI), I = [K] and, for some instance for which (a(1) > Po(2), the correct answer is i" ("(()) = o1) the best arm.
We focus on bandit models where each arm [K] has SuubGaussian distribution V4 of constant o². That is, for all X E R. Beg (e < e2 For example, both bounded and Gaussian distributions are sub-Gaussian
In Top-k, I = (k(K) the set of all subsets of [K] of size k, and the correct answer for some in- stance for which Ha(k) > Ma(k+1) is ((() =
(2) [k:)] the of the best & arms. Note that top-1 is BAI.
Finally, we study batched algorithms (Agarwal et al., 2017; Jin et al., 2019). In practical settings, it not always possi- ble to adapt at every single timestep. Therefore, we want the agent to only observe results and take decisions a limited number of times. At the beginning of a batch, the agent decides how many times to sample each arm i E [K], then observes all the realizations of those pulls. It then can pro- ceed to the next batch. Crucially, the agent cannot change anything during a batch: it cannot change its sampling de- cision and cannot stop a batch early. For d-correct batched algorithms, for each pure exploration problem, we want to control the sample complexity To (the number of samples used), and the batch complexity Rs (the number of batches used, which is the number of times the results were observed and the sampling rule was updated).
In the Thresholding Bandit Problem (TBP) with threshold т (Locatelli et al., 2016), I is the set of all subsets of [K], and the correct answer for some instance for which Vi, μ4 + is = {i: p > T the set of all arms that have their mean above the threshold.
1.2. Related Work
The problem of batched bandit algorithms has been studied in fixed-confidence BAI and Top-k. Some of the works cited below consider a task with multiple agents that limit the number of rounds in which they communicate, but their methods also give batched bandit algorithms. Hil- lel et al. (2013) derived an algorithm for s-BAI (the algo- rithm needs to return an arm with mean within of the best) which progressively eliminates arms. They show high probability bounds on the batch and sample complexities: with probability 1 - 6, it uses less than log(1/s) batches samples with A max Pt, pr.=). =.. Agarwal et al. (2017) consider 8-correct algorithms for BAI that use given number of batches, and give worst-case upper bound on the number of samples used by their algorithm (also elimination based), but their method requires the knowledge of a lower bound on the gaps of the arms.
In all pure exploration problems, the expectation of the stopping time of 5-correct strategies on an instance v is bounded from below as follows (Garivier & Kaufmann, 2016). Let Σ be the simplex, KL the Kullback-Leibler divergence and kl the KL between Bernoulli distributions.
and uses O (2)) -2 log K log (
[TA] 2 (M)) 1 - 5) 2 T (1z) log(1/(222))
K
in which (f*) = sup inf WEEK AE
w. (I,
This result has been expanded to pure exploration problems with multiple correct answers by (Degenne& & Koolen, 2019) in the asymptotic regime 5 - 0. This T (14) is the instance- dependent complexity of instance ç in this problem. Our objective is to develop algorithms with a sample complexity approaching T (μ)) log(1/5) for all μ. As we are in the o-subgaussian setting, T' (p) < (1)) where
Jin et al. (2019) and Karpov et al. (2020) designed 8-correct algorithms for the Top-k problem, and give each bounds with high probability on the batch and sample complexities. (Jin et al., 2023) is the work which is closest to our approach when it comes to algorithms. They study the BAI setting and prove bounds on the expected batch and sample complexity. Compared to bounds with probability 1 -, that requires that they control the complexities also in the event of probability
(T))
sup inf wEAx AEAlL
Σ we
(Mi - 2z)2
8. Their method for finite is also elimination based, but they additionally propose an algorithm with guarantees as
20²
8 + 0 that is inspired by the Lanck-and-Stopr BAI algorithm (Garivier & Kaufmann, 2016). Finally, Lu et al. (2019) build a batch-based algorithm for heavy-tailed distributions in a Track-and and-Stop fashion, but with the goal of minimizing computational complexity, and thus do not aim to control the batch complexity itself.
(by Donsker- Donsker-Varadhan Varadhan duality, see for example Lemma 2 of (Wang, 2021)) with equality for Gaussians with variance o².
Our goal is to obtain algorithms that have sample complex- ity as close to (H)) log(1/6) as possible while using few batches.
2

---

The Batch Complexity of Bandit Pure Exploration
All those works cover Top-k or its special case BAI. How- ever, many other pure exploration problems have been stud- ied in the fully sequential setting, like thresholding bandits (Locatelli et al., 2016) or the problem of detecting if any arm has mean larger than a threshold (Kaufmann et al., 2018). We seek to analyze general pure exploration problems and answer the following questions: what is the minimal ex- pected batch sample complexity needed to get an expected sample complexity close to what is achievable by fully se- quential algorithms? Can we design general pure explo- ration algorithm with near-optimal sample complexity and that reaches that minimal batch complexity?
any Gaussian instance ja with variance o² with T (1) (Tuin; T.ax). Let (12") JoSnEN be sequence of such Gaus- sian instances with T (u") (n²) E (Tmins Tmax) for some Ç E (0,1).
1). Then
>ln(1/6)
P u (Rs > 2) N(28+)))
-V 2(55 1(5-1-11 1 -1
SN
with
N-1 Σ n=0
(n²)
(u 12
SN
1+
sup WESK KE[K]
W 2
1.3. Contributions
In order to get a lower bound on the number of batches, it remains to construct the right instance sequences for each problem. should start with an easy instance μº, and end with N fe the instance whose complexity we want to study, with each succeeding instance being quantifiably harder than the previous one. See an illustration in Figure 1.
We show a link between sample and batch complexities. We build in Section 2 a general method for computing batch complexities lower bounds for 8-correct pure exploration algorithms. We demonstrate how to apply that method to Top-k (including BAI) and thresholding bandits. The lower bounds we obtain instance dependent: contrary to previ- ous work, we don't tt merely state that there exist an instance on which the algorithm requires some number of batches, but we give a lower bound for the batch complexity of each instance, function of its complexity T".
Wy (n) -17)
SuPweA ΣjE[K] n++ pm
14
20
M1 P2
(T*()"))-
In Section 3, we construct a general batched algorithm for pure exploration problems, taking inspiration from Track- and-Stop (Garivier & Kaufmann, 2016). The batch com- plexity of that algorithm is close to the lower bound under mild conditions that are satisfied on Top-k and thresholding bandits. Moreover, its sample complexity is close to optimal in the high confidence regime (small error probability 6).
P2
Figure 1. Illustration of a sequence of instances
An ideal sequence would minimize the sum SN, thus al- lowing us to get to a larger N. As getting such minimiz- ing sequence is difficult, we use simpler sequences μ² y + x= (n" - y) with y the constant vector (y, (y.,,.... y) with y E R. for some starting mean vector μa" In order to be able do so, important ingredient is the following condition:
2. Lower Bound on the Round Complexity
It seems obvious that using more batches will make it possi- ble to use less samples, as the algorithm can more quickly adapt to its observations. What then is the precise relation between the sample complexity and the number of batches?
Tao et al. (2019) focus on the problem of collaborative learn- ing with limited interaction, in which multiple agents take samples in environment and observe their own rewards, but must minimize the number of times they communicate their rewards with the other agents. They manage to find link, in some specific 2-armed instances, between how much faster an algorithm can get when communication is allowed, and the number of times the algorithm communicates. They do so by constructing a sequence of gradually more difficult instances, each requiring one more batch than the previous one. Generalizing this idea lets reach the following result, for any pure-exploration problem.
Assumption 2.2. For any mean vector μu, there exists y E R such that for all x E (0, 1] and μz' = =u + (1 - z)y (where y is the constant vector (y. (.. .)), (T* x (T))
This assumption essentially states that the complexity of the instance scales quadratically as the instance is linearly scaled in that manner, with all arm means concentrating around some value y. This is useful for constructing se- quences of instances and analyzing how the complexity evolves.
Top-k and thresholding bandits both satisfy that assumption. For top-k. concentrating arm means around any value makes arm means get closer, makes gaps shrink linearly, and thus
Lemma 2.1. Suppose that a S-correct algorithm satisfies p (T& > (p) In(1/8)) I c. for some 7 > on
3

---

The Batch Complexity of Bandit Pure Exploration
makes the complexity grow quadratically. For thresholding bandits, concentrating arm means around the threshold value has the same effect. With that condition, it is possible to simplify the bound of Lemma 2.1. We give general result for the exploration problems satisfying this condition in Appendix A. We then apply this result to Top-k and TBP. Theorem 2.3. For Top-k and TBP. for a d-correct algorithm on Gaussian instances with variance a² of complexity T E (Tmin: T m, we have for any such Gaussian instance μ of complexity Th E (Tmin; T that
but the sample complexity is only controlled in the regime 8 - O, in which lower bound goes to O. Since [Ta]]]] is not controlled otherwise, " can be large, making our lower bound small and consistent with 3 batches.
Necessity of miin- The bound depends on Tiin. which is the minimal complexity for which the sample complexity of the algorithm is bounded by (T* log(1/)). Since no al- gorithm uses less than sample, every algorithm has such a
Tii greater than (10g(1/5))- and the lower bound is then of order log(T" (nx) log(1/ (1))). Tiin is tradeoff between prior knowledge and batch complexity. In the extreme situa- tion in which T (4)) is known and the algorithm is 6-correct only on instances of that complexity, the lower bound is O. Our algorithm will use at most 5 batches in that case: any lower bound has to be a small constant.
T
[Rs 2 min-
Tiin
2ln
In (1)
fe, Cs}
Tinin
In (+)
1
6
Tinn
65
3. A General Algorithm
with
We present an algorithm for pure exploration in bandits with upper bounds on both its batch and sample com- plexities. We take inspiration from the Track-and-Stop method (Garivier & Kaufmann, 2016), which is fully se- quential (it does not use batches) and has asymptotically op- timal sample complexity. The principle of Track-and-Stor for Gaussians is to try to sample according to w" (H) = argmaxwed infxe Alt, E, ui - A,)2/(20*) the vec- tor of ideal sampling proportions at μ.. At time 4, having sampled arm approximately w times leads to an algo- rithm that has minimal asymptotic sample complexity. Of course w (n) is unknown: Track-and-Stop estimates μ by its empirical mean fa, then approximates w² ((4) by w (ft) and uses those proportions. Some amount of uniform explo- ration is added to ensure convergence of the estimates.
In (n)
(2)
Cs = 1 47
1+
8
T Tin
0²
[T(
sup 7 v:T (pT)(())E(Tnnn)) min- ) In (1)
and where A max; p4 pi-mii: min: in the Top-k setting and 2
A max; [4g - T| in thresholding bandits.
We give all details of the proofs in Appendix A. For 8 small enough, the batch complexity is of order
(")
In Timi
Ω In
[n
(H) Tmmm
+ In
(7 (n((
max. A?
min,
This is the first lower bound on batch complexity as a func- tion of the sample complexity for all pure exploration prob- lem satisfying Assumption 2.2, Our algorithm will have a batch complexity of order In Tiin
We introduce a batched algorithm that first samples uni- formly until it has estimated the sampling proportions and complexity well enough, then uses last phase in which samples like Track-and-Stoo
(x) almost matching the
lower bound.
For collaborative bandits (where periods without com- munication are the analog of batches), Tao et al. (2019) have worked algorithms As satisfying E.,, [rs] O ( [TaT]) where the infimum is over fully sequen- tial algorithms. Their results can be adapted to the batched setting to show that there are two-armed instances on which In A,
3.1. Stopping Rule
To check whether we can stop, a commonly used method in parametric pure exploration is the Generalized Likelihood Ratio (GLR) test (Garivier & Kaufmann, 2016). Since we consider the non-parametric class of sub-Gaussian distribu- tions, we use Gaussian version of that test. The stopping rule of the algorithm is to stop at the end of a phase if
those algorithms must satisfy [Rss]] = [n A Our result valid for more pure exploration problems than just BAI; it is a bound on general K Kaareed Gaussian instances rather than specific two-armed instances; and gives instance- dependent bounds instead of merely the existence of an unspecified hard instance.
inf Σ
(pt
8(t,6)
(I)
XEAig
20
Lemma 3.1 ((Garivier & Kaufmann, 2016)). Any algorithm using the stopping rule (1) with a threshold (tt, 5) satisfy- ing (31 No (Ri-)=)²
> (tt,)) S 8 and returning 20
Theorem 2.3 does not contradict the guarantees of Tri-BBAI (Jin al., 2023). Their algorithm always uses 3 batches,
i" (ft") is 5-correct.
4

---

The Batch Complexity of Bandit Pure Exploration
We provide below threshold that works for sub-Gaussian distributions in any pure exploration problem. For partieular problems like BAI it should be possible to derive improved thresholds, as was done in parametric cases by Kaufmann & Koolen (2021). I. Our threshold is derived using the method of mixtures, as in that paper and other bandit articles (Abbasi- Yadkori et al., 1). It uses the techniques of (Degenne, 2019) to fine-tune the constants. While the BAI literature contains many similar thresholds for parametric settings, we could not find that result for Gau-Sann distributions.
and j are switched. Then, (*)) TT* but is strictly more difficult sample that both instances are solved at the same time, so T (Lu, H²)) > T*
Lemma 3.4. IfT (B) < +oo, then if after sampling each arm N; 2 you (BYT" (B) times the empirical estimate fa in B, then inf Alta Σ, Nid(pi, X.) Z
Proof. By the condition on No then the fact that ja E B and finally definitions of कh and T",
inf XEAlta
Σ
NNi (x)
Let W-1 be the negative branch of the Lambert W function and let W: (1, +00) + R be the function defined by ((x) = -W1(-e-"). It satisfies x + In S ((x) x x + 1/2 S 2x.
2 7T (B)
inf
Σ (B)d((((A))))
XEAlta
2 T (B) inf inf vEB AEAlt
Σ AB) y
Lemma 3.2. The following threshold satisfies the condition distributions:
of Lemma 3.1 for
K_ W! 8tt, = 2 K
et)
en²
In +
4ln In
+
2ln In
K)
6
This entails that picking 7 2 (tt allows us to meet the stopping condition after that one batch, if indeed j e B. The number of samples used in the batch would be T' (B) 2 (t)) 6). A good set B therefore a confidence zone for ja, and additionally has small ('(B) ratio to not oversample.
See Appendix B for the proof. Roughly, ignoring additive constants, 8(1, 5) v ln(1/0)+2K In I . The linear depen- dence in K may be unavoidable in general (for the problem of telling if the means belong to the unit ball, if μ is the center) but could be improved in problems like BAI. The threshold for exponential families of (Kaufmann& & Koolen, 2021) depends logarithmically on the number of arms.
(T))
3.3. The Algorithm
Our algorithm is shown in pseudo-code in Algorithm 1. It works in phases. Each phase contains at most two batches, although the second batch is rarely done. We define "phase complexity" T, To for To a parameter of the algorithm. In each phase in first batch we start by sampling arms uniformly until the number of samples for each arm is at least 2 where 4,,- will be set later.
3.2. Known Confidence Set
In order to design an algorithm, we first ask the following questions: given enough information, could return correct answer within one batch? How would we sample and what would be the sample complexity?
Suppose that we know a set B which likely contains js and will likely contain the empirical mean vector f for any amount of sampling we perform. Since we will be using only one batch, we have to select the number of samples for each arm in advance. We want that number of samples to be sufficient to enable the stopping rule, for any 4e' E B. Our solution will be based on two worst-case definitions.
Then we use the empirical mean at that point j to find a set B, that likely contains p. B, is defined as a ball in infinity norm centered jí" and of radius e, which we will choose later. We write Bac (jz ex) == {u' 11 1e'l S Ex) and set B, B E..).
We then check whether the worst-case complexity T' (B,) exceeds the phase complexity T,, If it does, we skip to the next phase: we need more exploration to get tighter set. If it does not, we enter the second batch of the phase and sample according to y (B,)T" (B,). Yr is chosen large enough such that under a typical event, the algorithm then stops. The expected number of batches will be the number of phases required reach the right complexity range plus small constant.
Definition 3.3. For any B a set of instances, define (with 0-1 = +00)
Σ wi (U: Ax)2
wn w'(B)- = argmax inf inf wEAK WEB AEAlt,
20²
-1
(v:- 21)2
TB))= = max inf inf WEAK WEB XEALt,
Σ
wi
20
There are several quantities appearing in the algorithm, which we now specify. N₂ is the number of samples ob- served for arm i and t = Σ N₁. S(t, d) is the thresh- old of Lemma 3.2. The uniform exploration amount is
Note that TBBB) 2 maxuen T (H)) but those two quan- tities may not be equal. To see this, imagine an instance w such that w: (p) # wy (14), and instance v' such that arms
5

---

Our algorithm explores uniformly until the worst-case com- plexity T (B,) is close to (w)) For that to work, the distributions of the arms and the problem geometry need to The Batch Complexity of Bandit Pure Exploration
Algorithm 1 Phased Explore then Track (PET)
T' (B,) T and the second batch is not entered, or the algorithm stops.
1: Input: Starting complexity To
2: < 0, 6 0, Vi NN <- 0
Let R := minfr 2 E &x = the first phase after which when the good event happens, the estimated worst-case complexity is small enough. The batch complexity Rs and sample complexity TB of PET satisfy
T be
3: while not stop do
4: for each arm i E [K] do
5: while N, < 1, do
6: Pull arm i
(1) log
)
7: N₂ < N; +; 1
Rs S R + max R
+1
8: end while
To
+
9:
end for
+ 2 +00
10:
Compute the empirical mean vector jt".
I(E
11:
B, + { 11 +1'll S E
r=1
(v: Az)²
w +- argmax inf inf wEAK VEB, AEAlLy
Σ wi
+00
20²
TB S tR- + Σ
I(E))t,41
(vs 1 12))3
T (B,) + inf inf BEB, AEALL
E Wi
where [x] = max [x]}
20
12:
IT T (B.)
S T. then
Proof in Appendix C.2. The theorem gives upper bounds the batch and sample complexities that depend on the random variable Rº. We then need to control R", which requires an understanding of how T (B,) changes as we explore.
13:
for each arm i E [K] do
14:
Pull arm i [T. times:
15:
N₂ < N; + Nr T 1 t t + TT
16:
end for
17:
Compute the empirical mean vector fi" end if
3.4. Batch and Sample Complexities
if inf Alll E, N₂ (i -21) > B(t, 8) then
19:
20
20:
it < arg max; js
We derive upper bounds on the batch and sample complexi- ties of Algorithm 1.
21:
stop + true
22:
end if
23:
r r +++1
24:
end while
be such that we can indeed estimate the complexity. To be able to write bound on the sample and batch complexities, we further need to quantify the speed of estimation. We introduce an assumption to that effect. We will check that this assumption satisfied on various tasks like best arm identification and thresholding bandits.
parametrized by 4tr 32T (n,2. The confidence 20²
In 2K with Pr 2 region width is Er 2%,,, P.
Finally, "r is the solution to 7 O), in which 4, = =K2 + 7T,. 4, is an upper bound for the sam- ple complexity until the end of phase r for any r. It is obtained by considering that in the worst case, both batches are entered at each phase up to r. Theorem 3.5. Algorithm I 8-correct.
Assumption 3.8. There exists a function R+ such that for any μ., for all I b(()) and any n' (H, = {v RK || allco e). In T (B,, In (N') S Se/b())
R +
Assumption 3.8 allows us to know how much uniform ex- ploration is enough to relate the worst case complexity T (Bxo (1),)) over a ball and T' ((z)) for μı' in that ball. We introduce another assumption, which is simpler to check on many problems.
This is a consequence of Lemma 3.1 and 3.2.
In order to describe the number of batches and of samples used by the algorithm, we introduce "good" event, under which the algorithm behaves as expected.
Definition 3.6. Let E,, be the event that in phase r, ft" and belong to B,,
Assumption 3.9. For all μa, for all 2 0,
T (B (H.ee)
sup T*')..
That event will happen with high probability and when it does, we can bound the batch and sample complexity.
The reason for introducing Assumption 3.9 is that it provides a potentially simpler way to prove Assumption 3.8, as we show in the next lemma.
Lemma 3.7. For any pure exploration problem, PET (Al- gorithm 1) such that at phase r, if &, holds then either
6

---

The Batch Complexity of Bandit Pure Exploration
Lemma 3.10. For all ia and μl with ll palloo x v (02/(2T<(x]).
have shown that for two arms the optimal dependence is O(T (1²) In In T (n)), which means that our algorithm loses factor K. This is due to the uniform exploration: we sample until every arm's mean is estimated within (T)()//² We conjecture that a more adaptive explo- ration could improve that dependence. It is possible in BAI, as demonstrated by Jin et al. (2023). How to do for any pure exploration problem an open question.
(n') - (n) S V 02 (x)) ll ull
8
As a consequence, if Assumption 3.9 is satisfied, then As- sumption 3.8 is satisfied with b(μz)= = /
We can now present the guarantees of our algorithm, for any pure exploration problem for which Assumption 3.8 holds. Theorem 3.11. Suppose that Assumption 3.8 is satisfied and let TV (u) == max { binzz (e)" J. Then PET (Al- gorithm 1) has expected batch and sample complexities which satisfy
Sketch of proof By Lemma 3.7, we can bound the batch and sample complexities by finding an upper bound for R = minfr Vr' 2 r, & = T (Bx) < T and by bounding the probability of &
Let ro min(r | 2s,, S b(u)3, where b(μ)) is defined in Assumption 3.8. Then for any r 2 to. under E,, B, Boo 6r) _ Box (1,, 20r,) and thus for any n³ E B,, In Th (B.) T' (B,) SeT (n) since μ E By.
(H + logg (H)
E [Rs] S max log2
(H) 0
/ +2,
To
I 1. Hence in the event E,, we get
E [ro]
4n
(max{To, To (1)) + 1
Let ri minfr | T, 2 eTT (1)). Then for r 2 max (ro in the event &,, T, 2 (n) 2 T (B,). We get that R < = max
20K (In K + 4) (To, To (11) + 1)
48K( max (To; (1)) In max (To: Ty (11)
+ To In(4o))
By concentration, since suppose -- GuuuGaassia arm distributions, for & Pr. We can thus bound the expected batch and sample complexities.
2o 2h, log 2K we have P(E,) < p.
If Assumption 3.9 is satisfied, we get from Lemma 3.10 that (4) S (M)) The batch complexity of the algo- rithm is then bounded by log2" To + 5. This should be compared the In (T)
(")
Tiin term of the lower bound, where Tuin is the smallest complexity on which the algorithm is both d-correct and has expected sample complexity close to T (p+) log(1/)). Since PET uses To for the first guess of the sample complexity, it cannot match the sample com- plexity of an instance f with T (+²)= S To. hence To is the Twin of our algorithm. Hence, PET matches the In T' (n) TTiin component of the batch complexity lower bound. We also remark that if we know exactly T (1x) in advance, then we can use it as To and the algorithm runs in at most 5 batches.
E [Rs]] Sr" + max 0, - log2 (H)
+
To
to0
+ 2
Pr
r=1
to0
E [ < F,.- +
pr
With our choices of pr. Vr and li,r we can finally compute bounds on the sums, ro and rı (see Appendix C.2).
On the sample complexity side, the 5-dependent term is proportional to T (I)) log(1/5), which is the right depen- dence in 8, up to the multiplicative constant. The optimal asympiotic complexity as 8 + 0 is exactly (u) log(1/8), with factor 1. Our constant could be improved: we made the bound simple at the expanse of a few larger constants. For example the factor 4 in 4 In (3) (Tī (44) + T is the result of using the coarse inequality x + log x S 2x twice. In the definition of T7 (H1), the in 2e2**()) (H) is due to the choice of doubling Т, at each phase: choosing multiplication by (1 + e) instead of 2 would reduce that. The e factor, well
3.5. Best Arm Identification and Thresholding Bandits
We have provided general theorem about Algorithm on generic pure exploration task with sub-Gaussie Gaussian distribu- tions. However, that theorem requires that Assumption 3.8 be satisfied. We now show that Assumption 3.8 holds on the Top-k task (including BAI) and on the thresholding bandit problem, by showing that we have Assumption 3.9.
Lemma 3.12. In Top-k, including best arm identfiicttin, as well as for thresholding bandits, Assumption 3.9 holds. That is, for all l and all 2 O,
as the 8 in b(μz), could also be reduced to 1 + e at the cost of constant terms elsewhere.
The dominant term of the sample complexity as function of TT* (II) is 48KT (p1) In T* (1.). Jamieson et al. (2014)
(B # WEB((()))
max
T*
7

---

The Batch Complexity of Bandit Pure Exploration
1.50x:00
10
1.30x.0'
x.00
30
10C
104
800
(a) Number of samples before stopping in random BAI instance, logarithmic scale
(h) Number of rounds before stopping in random BAI instance
(c) Number of samples hefore stopping in the min. threshold setting, hard instance
Figure 2. Experimental results, 6 0.05, N 1000 runs
The proof (in Appendix C.5) hinges on the fact that, when- ever it contains only one answer, Bo (H,,E) contains instance that is more difficult than all the others, in the sense that sampling optimally to decide the answer of that instance also solves all other instances in the set. This is a stronger property than the equality of the lemma. From the existence of that hardest instance, we also get computationally easy way compute wt (It, E)) and T (1t,))) first compute and then compute w" (b) and T* (b)).
distributions are Gaussian with variance and the confidence level 8 0.05, which is chosen for its relevance to statistical practice. We compare
Round Robin (or uniform sampling), where the stop- ping rule is checked only at timesteps (900 x 2" r2)1 Track-and-Stop (TaS) (Garivier & Kaufmann, 2016), where the empirical value of w is updated only at timesteps (900 x 2")r, and the stopping rule is only checked at those times;
44
Our algorithm PET, with To = 1;
towards more difficulty
Opt-BBAI (Jin et al., 2023) with = 1.05 and the quantities described in their Theorem 4.2.
(p..e)
The initial batch sizes for TaS and Round Robin were chosen to approximate the initial batch size of our algorithm, to not disadvantage them in terms of round complexity. We modified TaS in order turn it into a batch algorithm. Note that there formal guarantee for the batch or sample complexity of that modification of TaS, but sensible baseline.
b
12
it
Figure 3. b satisfying T" (Bao (H,, = (b)
For the BAI experiment, we run each algorithm on 10-arm instances where the best arm has mean 1, and each other arm has mean uniformly sampled between 0.6 and 0.9. See Figure ((a) for the box plots of the sample complexities. The mean is indicated by black cross. While both algorithm and Opt-BBAI outperforms Opt-BBAI for the sample complexity. That algorithm is asymptotically optimal as 8 + 0 but it uses batches that seem to be too large for moderate values of 5 like the 0.05 we use.
We display in Figure 3 representation of what happens in two-armed BAI. As long as μn >> #2,, bringing ja down and μ2 up can only make the problem harder. If E is small enough that all the instances in (1, E) have the same answer, then the instance on the comnrr of B (μ,,) E) closest to the line Yi = H2 strictly more difficult than all the others. That means that sampling enough to solve it is enough to solve all the other instances.
similarly few batches, PET
3.6. Experiments on the BAI setting
While the batch modification of TaS might seem be good alternative for the BAI experiment, there are instances of the thresholding setting where it performs sub-optimally. That effect was first observed in (Degenne et al., 2019) for the fully online TaS and reflects that, contrary to our results, the sample complexity guarantees of TaS are only asymp- totic. We run the algorithms on a thresholding bandit with threshold 0.6 and two arms with means 0.5 and 0.6 and ob-
Our algorithm PET near-optimal in round and sample complexities for many pure exploration problems, and has theoretical guarantees for any pure exploration problem. To ascertain its practical performances, we compare it to baselines and state of the art algorithms for best arm identi- fication and thresholding bandits.
Each experiment is repeated over 1000 runs. All reward
8

---

The Batch Complexity of Bandit Pure Exploration
serve that batched TaS has high average sample complexity (see Figure 2(c); the mean is the black cross), while PET does not.
Multi-Armed Bandits, and Ranking from Pairwise Com- parisons. In Proceedings of the 2017 Conference on Learning Theory, pp. 39-75. PMLR, June 2017.
Audibert, J.-Y., Bubeck, S., and Munos, R. Best Arm Iden- tification in Multi-Armed Bandits. In COLT 2010 The 23rd Conference on Learning Theory. pp. 41-53, Novem- ber 2010.
4. Perspectives
We proved instance-dependent lower bounds for the batch complexity of any 8-correct pure exploration algorithm. These lower bounds get larger the sample complexity of the algorithm decreases. We introduced the Phased Ex- plore then Track algorithm, for which we proved an upper bound for the sample complexity close to the lower bound for fully adaptive methods, as well as an upper bound for the batch complexity that is close to our lower bound.
Bubeck, S., Cesa-Bianchi, N., et al. Regret analysis of stochastic and nonstochastic multi-armed bandit prob- lems. Foundations and Trends Machine Learning, (1):1-122, 2012.
Degenne, R. Impact of Structure on the Design and Anal- ysis of Bandit Algorithms. PhD thesis, Université Paris- Diderot, 2019.
The main open question raised by our work is how to explore in better way than uniformly for a general pure exploration problem. The goal of the exploration is to find a set B, such that the worst case complexity T' (B,) ) is close to T (p)), which means estimating both 7 (4) and w² (H).. Uniform exploration leads to a close to optimal batch complexity and to a sample complexity which has a good dependence in (1)6) However, comes at the cost of KT sam- ples used to explore every arm, which should ideally be around (M) instead. For BAI and Top-k, the climination strategies of (Hillel et al., 2013; Jin et al., 2023) achieve that improvement, but the elimination criterion uses the particu- lar link between the gaps and T in Top-k. We would need to find a way to extend the elimination approach to other problems, for which there might not even be an obvious notion of gaps.
Degenne, R. and Koolen, W. M. Pure Exploration with Multiple Correct Answers. In Advances in Neural Infor- mation Processing Systems 32 (NeurIPS 2019), 2019.
Degenne, R., Koolen, W. M., and Ménard, P. Non- Asymptotic Pure Exploration by Solving Games. In 33rd Conference Neural Information Processing Systems (NeurIPS 2019), June 2019.
Even-Dat E., Mannor, S., and Mansour, Y. PAC Bounds for Multi-armed Bandit and Markov Decision Processes. In Kivinen, J. and Sloan, R. H. (eds.), Computational Learning Theory, pp. 255-270, Berlin, Heidelberg. 2002. Springer. ISBN 978 978-3-540-45435-9, doi: 10.1007/ 3- Garivier, A. and Kaufmann, E. Optimal Best Arm Identifica- tion with Fixed Confidence. In Conference on Learning Theory (COLT), 2016.
Acknowledgements
The authors acknowledge the funding of the French National Research Agency under the project FATE AAN222CEE23 0016-01) and the PEPR IA FOUNDRY project (ANR-23- PEIA-0003). The authors are members of the Inria team Scool.
Hillel, E., Karnin, Z. S., Koren, T., Lempel, R., and Somekh, O. Distributed Exploration in Multi-Armed Bandits. In 26th International Conference on Neural Information Processing Systems, November 2013.
Impact statement
Jamieson, K., Malloy, M., Nowak. R., and Bubeck, S. Lil' UCB An Optimal Exploration Algorithm for Multi- Armed Bandits. In Proceedings of The 27th Conference on Learning Theory, pp. 423 429-439. PMLR, May 2014.
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.
Jin, T., Shi, J., Xiao, X., and Chen, E. Efficient Pure Explo- ration in Adaptive Round model. In 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada, 2019.
References
Yadkoi-Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Jin, T., Yang, Y., Tang, J., Xiao, X., and Xu, P. Optimal Batched Best Arm Identification, October 2023.
Agarwal, A., Agarwal, S., Assadi, S., and Khanna, S. Learn- ing with Limited Rounds of Adaptivity: Coin Tossing,
Karpov, N., Zhang, Q., and Zhou, Y. Collaborative Top Distribution Identifications with Limited Interaction. In

---

The Batch Complexity of Bandit Pure Exploration
2020 IEEE G Annual Symposium Foundations of Computer Science (FOCS), pp. 160-171, Durham, NC, USA, November 2020. IEEE. ISBN 978-1-72819-611-3. doi: N011009FFC444700.220.00000
Kaufmann, and Koolen, W. M. Mixture martingales revis- ited with applications sequential tests and confidence intervals. Journal of Machine Learning Research, 22 (246):1-44 2021.
Kaufmann, E., Cappé, O., and Garivier, A. On the com- plexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17 (1):1-42 42, 2016.
Kaufmann, E., Koolen, W. M.. and Garivier, A. Sequential test for the lowest mean: From Thompson Murphy sampling. Advances in Neural Information Processing Systems, 31, 2018.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Locatelli, A., Gutzeit, M., and Carpentier, A. An optimal algorithm for the Thresholding Bandit Problem. In 33rd International Conference on Machine Learning (ICML 2016), 2016.
Lu, S., Wang, G., Hu, Y., and Zhang, L. Optimal Algo- rithms for Lipschitz Bandits with Hcavy-tailed Rewards. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Tao, C., Zhang, Q., and Zhou, Y. Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armer Bandits. In Symposium on Foundations of Computer Science (FOCS). IEEE, 2019.
Thompson, W. R. On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3/4):285-29) 294, 1933. ISSN 0006-3444, doi: 10.2307/2332286.
Wang, Y. Sub-gaussian eтror bounds for hypothesis testing. In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 3050-3055. IEEE, 2021.
10

---

The Batch Complexity of Bandit Pure Exploration
A. Proofs of the lower bounds
A.1. Preliminary lemmas
For the sake of completeness, we start by restating and proving some results from (Tao et al., 2019) in slightly more general language.
Definition A.1. For some integers r and n, define T/6 the number samples before the end round r.
Lemma A.2 (Generalization of Lemma 27 of (Tao et al., 2019)). For an algorithm, two instances v and v' and r E N.
n m) 2 Pu(Rs 2r+1, S m) Pulto > n) aD - -D 1lrv
where D is the distribution of rewards the algorithm got from v over steps.
Proof. Fix deterministic algorithm.
First of all,
(Rs 2 1 1, S T
r+1 TB < n) C (Rs 2 r + 1, Sn+m)
(2)
And, since (Rs 2 + S m, - Tz < n) is determined by the first m rewards (at the end round r using less than m samples, the algorithm must choose the length of round + 1),
Per RRs 1r+ S m, T r+1 T3 < n) 2 P. (Rs 2 2r+1, S m3 r+1 T/ <n) - 10 -D71
(3)
On the other hand,
(R + (Rs 1 m)) \ (Rs
1, m,
m, 741 - T3 n) = (Rs 2 r 1,78 S m, 741 - T3 n)
5 > n)
hence
P. Po(Rs 2 TJ S m, T/t
<f P. 2 r 1 5 PP(T n}
(4)
Hence, using Equations (3) then (4)
(Rs 2 1, ++1 In m) 2 P. (Rs 2 r
2 PRss 2 r+ < m -1 - - D
P Pu(Rs 2 1 S m) - Pu D DDill
Lemma A.3 (Generalization of Lemma 26 (Tao et al., 2019)). For any ò-correct algorithum, for all m, E N and any two bandit instances v, v', we have
Pu(Rs 2 2r+1,75 S m) 2 Pu(Rs 2 2 S mm mm-22 25 - - DD' ITV.
Proof. Consider the event Fi = (Rs = T, < m). Denote by F2 the event that the algorithm returns the best arm of instance v. Then (T( A Po
With D the distribution of rewards over m samples and some v' Alt
Pr &P A F2) + D Drv
PPr DD Dn lrv
2 + |
D DTV.
On the other hand, <
Therefore P, (y & 26 2 D. lzv. Using Py 2 2r+1 <
m} 2 P, Rs r,7g S mm] (F.),, we conclude.

---

The Batch Complexity of Bandit Pure Exploration
Lemma A.4. For any ò-correct algorithm, for all m,r N and any bandit instance v, have
Pu(Rs 2 2r+1, m) 2 Ps r5 S mm) 28
V 2 (T+
Proof. First apply Lemma A.3 to an arbitrary instance v' Alty. Then using Pinsker's inequality yields
(0t (ni- - -1,)²
DDD Divvrr S V (L(DD/DDD)
Σ iE(K]
EyIN ml
2
with a the number of times arm is pulled before time m.
As this is for all instances v' E Alt we can obtain an inequality using the infimum over those instances,
Ep [N (#:
X₂)²
inf e'E,
| D llv S
inf AEAlt
2
m
iE[K]
(14 x;)
inf 2 wEEK AEA
sup
Σ VE[K]
Wt
(T-(1))~+,
2
by definition of T*
Finally, we also give technical result to solve inequalities of the form (k: + N2 (aaa+bbii N)) S...
Lemma A.S. Let p 2 e, a, b 2 and k be real numbers, and let A max(e, + a}. Then [n((In (A+bmmmn) satisfies (k + (a b N)) p.
Proof. If N 0, the equality is p, which is true since p 2 Otherwise, N 2 and (In blmnn 2 A2c. so N < [n p/ e] < In p. Therefore
N <
$ N p) blmlpp))
$ Imp
and finally (k + N2 bb) Sp.
A.2. The lower bound in the general cases
We give here result for any sequence of instances.
Lemma A.6. Let there be a sequence of instances (V" Jugnsn such that the probability of error is bounded by and for
any n E [0,N N - 1), Gn 2 Pun [TA > In). Then
PyN R4 > N 2- 2N8
Σ
Cn +
X
(T
1
+
E (p - )2
Xn-1
202
&E[K]
where X,, Em- Fú. x- is any positive real number, and No. is the number of times arm is sampled before time
12

---

The Batch Complexity of Bandit Pure Exploration
Proof of Lemma A.6. By lemmas A.2 and A.4, for any m,
Patti {Rs 2 n + 1, n+1 S m + fnf 2 Pun [Ro 2 n 1 S {m) - -cn - 1 - -D
1
|TV
P RRo
n, T3 S mm} 20 1/2
111
(T*
(nu+t -191
Σ
E[Nm.bl
Cn
2
20²
sE[K]
and with X, = Lis-1 Db
X Xa-1
Pen+i (Rs 2 n1 + 1, (,,) 2 (Ro 2 n, S xn - 28 Cn -
(T (T))-
2
Xn-1
B[ (1, 11
2 KE(K]
Xn-1
20²
So that finally
PuN (Rs 2 N, S [NN=1] PLo Rs
0 8 S
1r11}
2N8
Xn-1
E E[Nx al (1, - 12
((T*
On
2
Xn-1
202
iE|K]
and we conclude since for any x-1 2 P.o 2 1, 1, S <m11}
(we always at least 1 round).
= From there, we derive the result for (==) (TTT(((4)) Lemma 2.1. Suppose that d-correct algorithm satisfies F2 (Ts > (T) S for some N 0 on any Gaussian instance çt with variance o² with T (H) E (Tmin: m.ax). Let (μ") JonnNS be sequence of such Gaussian instances with T (1x") = T (p"))-- E (Tmin; maxx) for some ( E (0, Then
7 1l(1/8) SN
P Par (Rs > N) N(28 + c) - -V 2(5 1)
with
N-1
(ne)
(4 11,1)22
SN = Σ
1+
sup WEEK
2
n=0
KE[K]
Proof of Lemma 2.1. We apply Lemma A.6 on the sequence (v" JosnSN with x-1 = [ That way,
X, = =
TT" (H')))
-T (1²) log(1/0)
5-1-1
5 (1+1)
= (1²) log(1 (10))
5-1-1
Under Assumption 2.2, we can pick a sequence of instances of means 1aa11 zxp + (1 - x)y and control the sequence of Th (H²). That way, we get the following result:
13

---

The Batch Complexity of Bandit Pure Exploration
Lemma A.7 (Batch lower bound on affine sequences). For problems which Assumption 2.2 is satisfied; for any algorithm such that, for any Gaussian instance satisfying T (11) E (T mmm) T max) the probability of error is smaller than and such that (T( > 7 log(1/0)T S have for any o-Gaussian instance of complexity T* (pt) (Tmins I max), ) for the corresponding IR given by Assumption for μ., that P (RRs
2 N) 2 for
In Timn
T (p)
N min
In
T (1) In
max(e,
28
Tiin
with C - 4y log(t)
(1+
T' (2)) 20²
and A = max; [ui V/-
Proof. Fix some (o-Gaussian) instance nd of complexity T (m) = To (Tmins Tmma).
For some Ç E (0, 1) to be fixed later, define the instance of mean f 5- 1/222" + (1 1// We then have S"T*(H²) = T (f²)) by hypothesis. We can thus construct a sequence of instances of length N as long as Ç > Tx)))
Tmin
(u.V
14 Nn
(5-(N-n-11/) -C- y)²
20²
20²
N
(1 - 2/222
20
We apply Theorem 2.1 on the reversed sequence (UN (UN-slosisN:
(lg((18)
A
PR > N) 1- N-26 +c)
1
(H) sup
Σ
Wi 2a
(1 2//2)2
2(5-1 -
WEAK KE(K)
7 1og(1/5)
T (22
N 26 + c+
14
2(c-1-1) 11
202
2 5/8 cc)
for
5 = 1 1+4N2 log (
Th (1)))
1
202
We can apply Lemma A.5 with p sufficient condition is
(x") Tann
k 1, 0, and a 47 1og(1/8) 1+
T" (μ²)A²
We get that
20
In ("
N <
Tmin
(5)
In
In
(40 max (c, Tmin
T " with C = 47 (1 [+
2
20
Therefore, by picking N that satisfies (5) and N 8(2++c) we have that P, > N) >
Lemma A.8 (Batch lower bound on affine sequences, expectation constraint). For problems on which Assumption 2.2 satisfied; for any 8-correct algorithm such that, for any Gaussian instance satisfying T* T*())) E (T miin T Tmax) Ey [T8) S
14

---

The Batch Complexity of Bandit Pure Exploration
Y 1og(1/6)T*'14 (p)) have for any a Gaussian instance of complexity (p) (T (imi: max)) for the corresponding
y E IR given by Assumption 2.2 for p that P. (Ro 2 N) 1/2 for
In (1))
(1)
Tiin
N 2 min
In
T (1) In
max C3}
3
Tmin 35
Tmii
with C max e, 1 + 4y log(1/0) In (")
1+
("uss 20
and A = max; 1 3/.
Tinnn
Proof. For instance v, for some algorithm satisfying E, [T8] S llygo1/1/))) (fe), we have by the Markov inequality that (T(Ts 2 (t/c)]((p)) log(1/))) & c. Applying Lemma A.7, (Rs 2 N) 2 1/2 for
In [')
N min
Tain
1
In
T (14) In
maxfe, 03
20 + c
Tiui
with C C= 4y/ /llg(()) (1
1
V
T (2))
and A = max; 1 31-
20
Choosing max {o, (log
Tame
i < log (w)
Tiin
then
In T" Twin
(w)
N 2 min
In In (+)
maxfe, C%}
3
Tmin
Tmi
with C² = max
e, 1 + 4y log(1/8)
(())) In
1+
T min
2
8 2 (log [() Tini
-1
In (p)
Timn
1
N min
'35
In
In (H) Tinn
max (e, C3})
A.3. The top-k and BAI settings
All that remains is to show that our problems satisfy Assumption 2.2. We start with top-k, and first give technical result giving a simple formula for T (44).
Lemma A.9. For any w Σg.
inf AEAlt
Σ [E[K]
wid(pi Ac)
min wad(Has + wrdlus, Mab) 62k+1 ask
where Pab
Well Welte Che 4-W (arms are assumed to ordered, Nh1 2 po 2.....
We 4a--0
Lemma A.10. In the top-k problem, setting p' = J/t + (1 z)y where y is a constant vector and x > 0, Alt Alt Ard DA and (T* (1²)) 2²² (T)
15

---

The Batch Complexity of Bandit Pure Exploration
Proof. First of all, for any arms i, 14g 113 x0(; pb)) with x > 0. Therefore, the ordering of arms is conserved, and Altw' Alty. Moreover, since At u4 Ml+1 20ss pk+1)) xA, for S and A p 14 xA!" otherwise, do have A!" x Furthermore.
(44 2:)
(T (T') = sup inf wEΣN YEAlt
Σ ws 20 [E|K]
(1'a - -mabb)
(16g - 1lab))
sup
min 62k+1 ask
+ wb
20²
20²
wELk
with
Wall + Wott Ipab + (1 zx)y
(ab(w)=
Wo + w/
So that
(Na Hub)2
(16 Mob)
(T' x² sup min wEEx
Wa
+ wh
62k+1
20²
20²
ask
= (1))
With these results, we can apply Lemmas A.7 and A.8. We see that the value does not impact the proof: we thus choose the value that minimizes max; juy - y/. which is y max, d1 min, Hi.
2
A.4. The thresholding setting
Lemma A.11. In the thresholding bandit problem, setting μL' = zq + (1 F where T is the constant vector of value the threshold and 0, yl All A. xx and (T*()')) (T))
Proof. First of all, for any arm i, 14 T x(u; r) with x > 0. Therefore, All, All,' Moreover, At = =144 - -T = [4 T| AA! Furthermore,
(4) - A1)
(T") = sup inf wein AEAlt
Σ
20
[E[K]]
(p) - T)2
-T)2
sup sup weΣx iE[K]
20²²
(14 - 7)2
= x² sup sup Wi
WEEx K|
202
= (T)
B. Concentration and threshold for the stopping rule
We suppose that each arm is sampled once during the first K time steps.
16

---

The Batch Complexity of Bandit Pure Exploration
Theorem B.1. Suppose that the arm distributions -auss-Gnssnnnn Let Pe, be the average of arm & at time and N1.k be the number of times arm is sampled up to time t. With probability 1 6, for all t K,
1
K
(ie.k - -2
e
K [I A=1
2 1m + In Nea))
N
W
2ln
In
2
2g²
R=1
B.1. Proof of the concentration theorem
We can assume w.l.o.g. that μı = 0 for all k and x² = 1.
Let St,k = E.= X = k). We want a bound on
Ne.
We first remark that 4/²² = supx A jx². Apply that to x = St,k/ V N₂, to get
L.k
sup
ApSr,
2 No.ad
1
N₁,6
1
sup
Xo,
2 N
A
The advantage of that formulation is that we can concentrate the sum for any fixed value of (or any distribution on X) thanks to a martingale argument.
Lemma B.2. For all p & ((RR)), ), the process 1. m> Exup exp (Eimr Ab, Xa,k - }x2.)] is a non-negative supermartin- gale with expectation bounded by 1.
Corollary B.3. For all p E P(RK) and x 2 0,
P
31 In Exup exp
A X
= Ako
2x sea
2
Equivalently.fo for all 1).
P
3t, In EAnp
exp
Σ Au. No.k
2 2xē,
]]
12 2 88.
Proof. Use Ville's inequality and the fact that the process is a non-negative supermartingale,
We don't want bound an integral over p. but the supremum over X, so we need to relate the two quantities. We do that for Gaussian priors over X.
Lemma B.4. For p = (0, diag(o;;)) 2)),
In E Ex~p
exp
Σ Ae, Xa,t, -
Eye,
t
-/
]]
1
Σ
In(1
No,
1
S (Nrx + o
k=1
17

---

The Batch Complexity of Bandit Pure Exploration
Proof.
Expp exp Σ Ar,XXe. Xa,k,
II
E BB exp SpSSL
2 No
]
k V (2TTr S. exp AASic
1
o X2
- 2
Nr.
dd=
2
=II
1
1
/ exp
(-2 NN,, -z2) (Me
St.
)
2 1 S
)
ad
V (1 + No
2 (No, + +0%)
Ax2
(Ne + 0
2 No. + o8
exp
V(++ N2. V1++Nuu0F)
N oo
Corollary B.5. Let NO0 diag(o 2)), mamax = maxt N..a
ai and mm.min ming N..
a2_ Then
$2
S + m)xx
Ex
exp Σ dk, Xo.k.
2 2/x,,
1 12.
]
+
K
In(1 + mo.min))
Nr,
2
Proof. Using Lemma B.4,
K
]]
K
2 _/2
In Ex-p
exp Σ dxe Xa.
+
In(1 + N2,
Ni. + tok
2 k=1
Then
K
S2, N1, + 7),max))
K
L.k
N o
+ M,,
N
k=1
Finally, Nr.o0= -1 min,
If NE. was a known, unchanging number, we could choose of x Nr, to get Tt. = mim and we would choose it to minimize the right hand side. The strategy to use that "known Nr,, case even if they are random is to put geometric grids on the number of pulls of each arm, define distributions that are adapted to each cell of the grid, and combine them into a mixture of Gaussians.
6 Let (Jmi....ng MnNN ENEN be non-negative real numbers that will be chosen later. For i E N, let w; x (:11. The
weights (w:) satisfy Eien w; hence also Σ Em......x [l Wn,) =
K
Let Pai..... x (0,e | "_......x)) This is a product distribution, with each marginal being a Gaussian with mean 0 and variance that depends on the number of grid cell.
With probability 1 - 8, for all (nI,..., E I and all f,
1
In E Ex Bx
exp Σ
An. Xa,
No.
<
In
Wnk
18

---

The Batch Complexity of Bandit Pure Exploration
This is simply an union bound using Corollary B.3, with weight I Wne for Pai....
In particular, there exists (RI....; such that for all k E [K], eM N I enutt For that choice, e M e Bag K.
<
Rg. For those values, using Corollary B.5 with ox = e"" Maa with probability 1 - 8,
Ne.
K
K
K +
S (1 + Ba Bxx.....)))
In In
+ 8
In(1 + emaj..nn
Ni.k
Une
2
k=1
K/2
1
K
(1 + Bog
In
In
+
In(1 ( + The ?mi.....x
Wny
k=1
In (Ven /6)*
K
IT (ng + +1)
K
(1 ax
In(1 mot.....k))
6
2
This is where we choose m/r....... to minimize the right hand side.
By Lemma A.3 of (Degenne, 2019), the minimal value is attained at some M such that
) In (Ver2/6) I (nx + 1)²
K
(1 + Mmp
+
In(1 + m
2
K 2
2
(Ven2/00
I (nk + 1)2
= W
1+ In
K
By the choice of ng, satisfies ni < In No.
We get that with probability
8, for all t,
52
L
K
W
1
2 K
In (Vex2/6)
I (1 + In Ne.))
Nr.
2
K
K
2 K
In 1
W
In
(ET /6)
[1 +
2
K
This ends the proof of the theorem.
B.2. Upper bounds on ((1, 8) and on 7
We choose the threshold
K W 2
en²
2
K (I
2 in 1 m))
Bt, 8)
2ln
In
+
6
K
K
k=
We can get an upper bound that is not random by maximizing over (N₂ (Ne,)ke(K)
under the constraint Σx N = t. We get
K W 2
C
t
2 In 1
B
8)
2ln
+ 4in
1 +
In
+
K
K
We can get further upper bounds by using W ((x) S x + In + 1/2 < 2x. This gives
c
B(t, < 2K In
+ 4Khh In
[ In K
+ 2l
6
8
C
$ 2K In
+ 4K In
+ 2 2n
6
K
8
The right asymptotic for Btt, 8) as 5 - 0 (1/6).. We lost factor 2 in the upper bound above.
19

---

The Batch Complexity of Bandit Pure Exploration
Lemma B.6. Let My be the solution 8(,,,)) = "/r for.for I, = 2( + Tr and 1,r 327, (n(2n/222))))
Then
7r. S 41m J + 8K In((,) 4K Kk))
Proof. We use an upper bound for Btt, 8): 7r is bounded from above by the solution 7/ to
en
4k (2(321((2V2KT))) + kT.) + 21n
2K In
Then either 7 < 8K In(22/2TT, or Y is less than the solution to
en
10 YT,
1
7 2K In
4K
2
50em2
YT,
2K In
+ +-K1M In
+ 21n
3
That is,
1
800em 2
%/ = 4KW
In 3
+ (T,)
In
2K
2
3
800
< <411 8
+ 8K In(T,) + 4K In
At this point, we get
800em?
7/ S max
41n J 8K (n(,),
4K In
8K In(2 In(2V2KK,))
1
800em²
< 8K (T.)) max 4 +
4K In
8K In(2v 2K)
3
800e
s 8K 88K (T,)) + 41
+ 4K In
+ 8K ln(2/2K)
3
(6400ex2
< <8KI((T)) + 41n In
4K
K
8
3
8K 8K (T,,) 4 In
444 41111+ In
C. Proofs related to the algorithm
C.1. Additional Lemmas
Lemma C.1. Let (Xi)een be i.i.d. ---uu-Gaausian random variables with mean μ. For N, let pma be the average of the first n random variables. Then
xx2 P(3n 2 N. fn 2 S e 26
Nz2
P(3n > N, pn S 4 8) Se
20
Proof. Given .i....,Nw) the process M,(A): n の >ル 1n (X,-)) - 2 is nonnegative supermartingale for any À E R by the Gabssaa hypothesis, with expectation X EN (X. - No at 0.
20

---

The Batch Complexity of Bandit Pure Exploration
By Ville's inequality,
P(3n, Mn(A) 2 1/6 , I De Ei -N)
For all x IR and all 8 (0, 1),
P 2 N, A
(Xi 11
= x22 lm(116)
= EE 2 O, (.) 2 1/6 Xx)]
2
1=1
A (X,-)- -No
]No220]
I 0E
<6.
Reordering, we get, for X 2 0,
1 x²²
1
1
1 In ) nd 8)
P An 2 N, phn 2 +
In
SP
3n 2 N, Po 2 / 0²2 +
2
NA 8
88.
N+2 Choose 8 = and -5 to obtain
P(n N, An 2 st+) 6 20
The second inequality is obtained similarly, with X < O.
Lemma C.2. The probability of E, satisfies
P(E,) 2 21-2K 2K expl 1 22/20
Proof. & is the event that || - -2" S & and || 10 E.. We use union bound over the arms bound the probability of the complement E,. For each i E [K]. nC and ji are empirical means of at least 2"|,, samples, We can thus apply Lemma C.1 (twice, once for deviations from above and once for deviations from below).
Lemma C.3. Let pr e (0, 1]. For the choice E,
2g In 2K the probability of the event E, is is,, 2 Pr. P.
27,
C.2. Proof of Lemma 3.7
T (B,) > T, then the algorithm does not enter the second batch of the phase by definition of the algorithm.
I' (B,)= < T. then by the choice of yr and Lemma 3.4, under &, the stopping condition is triggered.
We now prove the complexity upper bounds. Let C,, be the event that the algorithm attains phase r and does not stop at that phase. We proved that (T" (B,) I T,} E S Cę for all r. That is, C, S & u (T' (B,) > T.}.
Recall that R min(r Vr 2 r, En + T (B,) I.
t00
Rg = Σ
I(C,-1) + I(C,-1 (B.) TT))
r=1
to0
n¹
< R² +2
Σ
I(Cr-11) + Σ I(C A (B.)))..)) ST)).
r=R++1
rml
By definition of R", for r 2 R we have (T' > T2} C &c. Using that property and the inclusion we proved on C, we have, for r > R
C--1 و U (T (T 1E
21

---

The Batch Complexity of Bandit Pure Exploration
Therefore,
+.0
R
Rs S R8" +2
Σ
I(E--1) + Σ A
(B))
r=
1=1
When E, happens (n) S TT'(BB, (B,), hence (T" (B,) IT) _ 3, U (T* ST.).
Rs R² +2
I(E--1) + Σ I(E Σ (() s TT))
r=
Rº + +++12 22122 Σ
I(E + Σ
I[[ (14) TT))).
r=1
}. with [x+ = max [x]].
Finally, R (IT S T.)) = max 0, - logg
(')
To
We now bound the sample complexity Tg. Since i, is an upper bound on the sample complexity up to phase r,
S
< Ig +
Σ
(1(Cr-11}
r=ft+1
toa
S lR. +
[1(EE-11
T= +1
C.3. Proof of the batch and complexity upper bounds
We finish the proof of Theorem 3.11 from where stopped in the main text. We have
E R& S r" max 0,r- - loga
T (H)
+ + 2 Pr.
To
to0
E [T8] S Fr- + Σ prtr+1
In those expressions, r" max (ro, rı) with ro min(r | 2e, S b()),, r minfr | T, 2 eT* and i,
(Kli,r/To Tr with // 32 ln2v2KTT))
The choice of pr is trade-off between the sums and ro. We choose p. = T2
Bounding the sums complexity is
The sum in the batch complexity is bounded by To 2/3. The sum that appears in the sample
i
Pr-
T2 r
ro. H+1
ma H+
We will need the values of a few sums.
2To
To
In
1
+00
rln2 + In In(4T,)
T
To
2"
To
22

---

The Batch Complexity of Bandit Pure Exploration
Let CK 4 + 4K + In K). By Lemma B.6, 7, &8K (KII(T))) + cK,5 An upper bound the sample complexity
until the end of phase is then
L, 2% (32K In + 2N+
& (n,K))(T))) + 32K In(2v 2K) + cx,8)T,
The sum that appears in the sample complexity is at most
48K (4T,) + 32K ln(2/2K) + CK.
To
Bound on r" and E
E - (48KIn In(Knn Tr, 1) 32K ln(2//K) + cx,6) mTx Tr,
Recall that ro minfr 2 0 2s, S b(m),, 1i min(r 2 0 2 T, eT (M))
If we get upper bound n T, we then have r; S logg To
We get bound on T,, from its definition: if ro 2 1, then
-1 S <eT (ps) hence in the end T,, I max 2cT (1)).
ro 2 1. then since E 2 /22 we get an inequality on Tm
20
b(μ)
In (2KT7)
n
1100-1
With the value of 1,, and using 2T T this becomes in the end
a² Tr S max b(
Let Tī (1) = max beuyy 26T (m)). We have proved max m Tr,} & max (n)} hence
E S (48K ma (x)) 32K In (2 + CK.8) [Tx Tī (μ)
and r* S max {o. logg
(p) To
Putting things together
For the round complexity,
(1))
(1)
(*))))
E [R]] max 0,
max
O, 0,
0,
log2
1 + To²
To
To
To
If (T) 2 To. then
(14)4)
(*)
E [Rs] < 2 2lgg
log2
+ +1+ +TTT0
To
To
Tž (1)
T (H1)
< log2
log2
+
To
T (14)
Tg (1)) < To. by definition, To > Th (14) 2 T (fz). We then have
(H)
E [Rs] < 0 max 0, 0,10g2
0 + +1+12
To
< 1 2
23

---

The Batch Complexity of Bandit Pure Exploration
So that finally,
(1)
logg (H)
[R S max
logg
To²
To
(1²)
E [8 & (48K In max (To: T5 (1)) } - 32K In(2/2K) cx.)) mTx (5 (1))
48KIn 4Tt) + 32К In(2/2K) + CK.6
To
Let us simplify the sample complexity.
1 + 4K Kln 32k (n(2 + cx,5 = 32 In(2 + +41n
= =41n + 44 + +11++44000
I 41n
20K K +
1 + (I K + 4)) max (1))
E [Ts] S (48K In max (To, T5 (n)} + 4 5
1 + 20K(In K + 4))27
+ (48K In(47)) + In
44 (1)
+ 20K K + +4) (max (1)) + 1
+ 48K 118((ma Ty (4)) In [To, (x) + To In(4T)))
C.4. Implication between the two assumptions
We prove Lemma 3.10.
Lemma C.4. Let v and v' be two instances and let wi = arg max inf XE E uilm 2.)2. Then
(T- -T (1') 20 1 1'1100
Proof. For w E Σx and a E RK, let |2]|| v V w.a.f. It satisfies the triangle inequality and ||=|| S ||0]||.. For any À and
A|Ias
A|la + |1 Im- ||
We can take an infimum on both sides over lambda in Alt and then apply the result to w/ to get
20 (14-1
inf || - Alli, + llea- 112g.
A
Either All,, = All and we can replace by that on the right hand side, jel E All In that second case inf 1|
Alla, = < infxEAle,r || Alkenn We thus have
2202T 5
|| inf rEAL
Alluan 11lee 1e' a'llomn
We maximize over w get in 11 Alllen S (202T((1'))- (1/)-1 hence
(20 < 2202T + |1 1 11
s v (0 11 11' 12l
After dividing by 2202, this is the inequality of the lemma.
24

---

The Batch Complexity of Bandit Pure Exploration
Corollary C.S. For all I and pl.
2 (nT - (n) S (x)) llee 14
Proof.
(4') - In (4) = 2In 1+ (T) (T-
(T-
V T (1) (T()
VT*(H²')-
S ('())) 1140-1111 p0l120
Corollary C.6. For all I and pl with || 1'1 S (0=((2T((11).
In (n)) s / / (m) 1| - pll
Proof. One of the two inequalities need prove due Corollary C.5. For the other, by the same corollary,
(n') - In (M) S (T( l| 14'1
remains to show (n') I 4T (H). By Lemma C.4 and the the hypothesis on || - p0l120
(T)- (T'(
22 1 11' 1'llo0 S TT)
Reordering proves the inequality.
C.5. Proofs for Top-K and thresholding bandits
This section devoted to the proof Lemma 3.12. We start with a preliminary result allowing us to compute wn (B) once we have found suitable instance B.
Lemma C.7. If all instances in share the same correct answer i and if there exists some mean vector E such that
Σ Emx(b)= (M:: - Ax.2
inf Σ wi((b (b. AEAlt
A₂)²
inf inf EEB XEALI,
(6)
20
202
where w()) argmax inf infxEAl, E, W/ (m;-2;)² then T' (B) max T TH (H).
(m(-20)²
Proof. For some w E Σg, writing f(w, 1t) = infxEAlt, E, W/ 272
for clarity,
f(w, < f(w,b) inf wEB,
because E Br from the definition of wb from the hypothesis
f(wb, b)
V inf f(wb, 11) WEB
so that (b) argmax, inf DeB, f(w, v) w² (B).
25

---

The Batch Complexity of Bandit Pure Exploration
-1
(14 2x)3
(B)= = Σ u (B)
inf inf
WEB xeAlt,r
202
Σ ut wb) (1g
2x0
inf inf
v' EB xEAll
20²
(b. - 21)3
inf Σ wi (b) AEAlt
by Equation (6)
20²
T (b)
hence T(B) S max B T (v). By definition, we have the other inequality, and conclude.
Lemma 3.12. In Top-k, including best arm identification, as well for thresholding bandits, Assumption 3.9 holds. That is, for all and all e 2 0,
T (Boo
max (n')). (A.E))
We prove the result separately for top-k and TBP. In both cases, we give certain mean vector b, and then we show it satisfies the premise of Lemma C.7, then we use that result to show that T (Bxc (14, e)) (b).
Proof of Lemma 3.12 for top-k. Assume without loss of generality that the arms are well ordered, #n 2 12 2 ... 2 uK.
μkk Pk+1 & 2e, then there exists E Boo E) such that by = but1. T (Boo(HH 2 max (1)) 2 (b) +00, therefore
T' (H, = max T*()).
V'E
When p0++1 > 2σ, define
b, p4
if < k if 2 k +1
b; = +E
and, for any v',
Σ Wi (u4 - A1)²
We argmax inf XEAL
20
WEEK
Let there be some v' Boo (H). Then for < k. mh 2 - by and for 2 1 L, uh S tE b, and Alt, = Alto.
We know from Lemma A.9
Σ Ew;(b) (m) - Ax)2
(H'a - Mlaj)
wy (M/ - Hay)
min AEAlL
=wa(b)
(7)
202
202
202
for some a <k<k+is> and plaj
(b (b) 1la +
w.
10, (b) 11g.
If plas (ba, ph),, then
w. 12,0) (0,+,,,b)10 (b)(6 - 14a9)
0+ (b)(H))) - -b,)2 (b)(bb - -ba)² + (b)bb(bb - -b))
If plaj (b,,
(a(b)((' 22 + w,(b)/ WWas) 2 (a( - 1'a))
(b) - pby))
26

---

The Batch Complexity of Bandit Pure Exploration
If way bg)
(a(b)(p'a )4as2 + wny(b(((s Haj)² 2 wa(b) b,)² +
2 (b) - b,)² + w,((b(b, - b,)²
In all three cases.
wa(b)(H'a Hag)² + (b)(((p)) plas)2 2 dal
inf
(abb)(bo 2)2 + (b)(b) 2)
inf E w;(bb((; Xa)²
Alt
and therefore, by Equation (7),
(es - Ax)²
(be - (b)=
Ve' E (H,
inf AeAlts
Σ (s)
2
inf
Σ wi(bb
20²
AEAl
20²
and therefore
Σ wb) (v: X112
(b, 2;)
inf vEBx (p,s) AEAlty
inf
inf AEAlth
Σ w.(bb)
(8)
202
20²
We can thus apply Lemma C.7, and conclude
T(B = max NEBw(H..)
(V)
Proof of Lemma 3.12 for thresholding bandits. If for some |p; - 7| e, then there exists b (2o such that b; T. Therefore, T (1,, 2 maxp (v') 2 (b) +00, therefore
T" (H,,
max V'EB
(v').
When ming 1ike r| E, define U = E [K] p4 T] and L [K] U. Define
bi μ4 ifieU
b, = +e if L.
and for any v', wa argmax inf Au, E, W. (1/-2:)²
20
Let there be some v E Boo (1,, c). We know minAcAlt E, w/ (b)
-11²
wr(b) (4(-r) 20
for some j.
20
For all E E. a 2 Mi E b, r; for all E L, 11 S Mi + b; <. Therefore,
wy(b) (ul 77 2 wy(b)
(br 7))
inf Σ Ewi(b) (b. 2,)
20²
202
A
20
We thus have Ve E Boo (H,,) infxEAuly Al1s E, (b)
> inf infxe Alto E.wi(b)
(b, (b:-),)² 20 and
20
wib(b) (Vi
Σ wx(b) (b: x₂)²
inf inf vEB, AE Alte
> inf
202
AEA
202
and by Lemma C.7,
(H,,))) = (V))).
vEBx<1.
27


Reviews:
[{"review_id": "AOyftRaOPC", "reviewer": "Reviewer_mFdv", "summary": "The paper investigates pure exploration problems with a specific focus on batch complexity.\n\nFirst, the authors establish a theoretical lower bound for batch complexity and characterize it in relation to sample complexity, which is well understood from previous work. They then propose the PET algorithm, which nearly attains the lower bound.\n\nBoth theoretical analysis and experimental results demonstrate the effectiveness of PET.\n\n## update after rebuttal\nOverall, I appreciate the technical novelty of this paper and will therefore maintain my current 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": "We thank the reviewer for their helpful suggestions. \n\nThe inequality on line 94 comes from Donsker-Varadhan duality, and can more precisely be found in Lemma 2 of Wang 2021, upper bounding the difference of means by the square root of the KL divergence for two sub-Gaussian variables.\n\nLemma 3.1 is a version of the Chernoff stopping rule (relaxed with the same inequality as above), which can be found for BAI in Garivier and Kaufmann 2016.\nOne can find a generalization of the Chernoff stopping rule for any pure exploration problem for example in Theorem 1 of Degenne et al. 2019 (Non-asymptotic Pure Exploration by Solving Games).\nOur concentration result is in Lemma 3.2. While this specific threshold beta is a new result, it employs the classic techniques used to derive such Chernoff stopping rule thresholds (we were surprised not to find such a threshold for the sub-Gaussian case in the literature).", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The work is mostly theoretical but also contain some experiments which have reasonable design.", "theoretical_claims": "I checked the flow of some parts of proofs but I’m not certain all are correct.", "experimental_designs_or_analyses": "The design of conducted experiments are seems sound.", "relation_to_broader_scientific_literature": "The key contributions of the paper are in the area of online decision-making (bandits).", "essential_references_not_discussed": "I am not aware of any missing prior works.", "other_strengths_and_weaknesses": "Strenghts:\n* The authors address three well-known problems—BAI, Top-K, and TBP—within a unified framework, with their approach and results applicable to all.\n* Considering the problem for sub-Gaussian distributions is an interesting contribution, as most previous work has focused on the 1-parameter exponential family.\n* The paper provides rigorous theoretical results along with experiments demonstrating the effectiveness of the proposed algorithm.", "other_comments_or_suggestions": "It would be better to restructure Subsection 3.1. Perhaps defining the threshold first and then presenting Lemma 3.1 would improve clarity.\n\nLine 117: \"is or order\" → \"is order\".", "questions_for_authors": "1. Can you elaborate on the inequality in Line 94? The explanation provided is quite brief.\n2. I did not fully understand the reasoning behind Lemma 3.1. You assume a sub-Gaussian distribution and then use similar quantity from the Gaussian distribution (GLR), along with a new threshold, to derive a concentration inequality. Is this inequality a novel result? I am unsure whether the cited previous work has addressed this specific case. Could you clarify?", "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": "wDxiqoHsjZ", "reviewer": "Reviewer_yvDd", "summary": "This work studies the batch complexity in the bandit pure exploration including best arm identification, top-k arm identification, and thresholding bandit problems. The paper begins by establishing a lower bound on the number of batches required for an algorithm that is $\\delta$-correct for any Gaussian instance with sample complexity in a certain range. It then proposes an algorithm, named PET, that works in phase. Theoretical analysis shows that its batch complexity is close to the lower bound, and its sample complexity is also asymptotically optimal in the high confidence regime.", "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": "We are grateful for the reviewer's insights and corrections.\n\nThank you for pointing out a few unclear passages.\nIn Assumption 2.2, $y$ (in normal font) is a scalar, and $\\bf{y}$ (in bold) is the vector $(y,y,...,y)$. \nWe will make sure to clarify this.\nIn Algorithm 1, we indeed did not detail where $r$, $t$ and $N_i$ (respectively the round count, the timestep count, and the number of samples of arm $i$) are updated.\nWe will add a line to explicitly mention their update.\n\nIn Lemma 2.1, $T_{\\min}$ and $T_{\\max}$ are indeed specific to the algorithm - and to the degree of optimality considered, impacting the values of $\\gamma$ and $c$ - all algorithms are not uniformly optimal everywhere. While $T_{\\max}$ could be set to $+\\infty$ for some algorithms, fixing some $T_{\\min}$ is necessary to guarantee the finiteness of $\\gamma$, as explained around line 209.\nNo algorithm can achieve a sample complexity that is withing a constant multiple of $T^*$ if $T^* \\approx 10^{-10}$, as every arm must be sampled at least once: $T_{\\min}$ should be at least of order 1.\nThat Lemma should also indeed use $S_N$ instead of $S_n$, thank you for noticing that typo.\n\nIt is correct that $T_0$ should have more of an impact on the bound of Theorem 3.11.\nThis bound is indeed only valid for $T_b^*(\\mu)$ big enough compared to $T_0$.\nMore precisely, in the Appendix, line 1173, $r_0$ and $r_1$ are necessarily strictly positive, which we forgot to reflect in the final bound.\nTo account for the case of large $T_0$, the batch complexity bound should be modified to be the maximum of 4 and the expression in Theorem 3.11.\nIn the sample complexity bound, one needs to replace every instance of $T_b^*(\\mu)$ with $\\max\\{ T_b^*(\\mu),32KT_0\\ln(2\\sqrt{2K}T_0)\\}$.\nWe are very thankful to the reviewer for pointing out this mistake.\n\nWith that correction, one can see the need to balance $T_0$: a very small $T_0$ will lead to a small initial batch size, so we can efficiently solve even easy instance without wasting sample complexity, but at the cost of way more batches for complex instances. A very big $T_0$ will minimize the number of batches required, but the initial batch might be way bigger than necessary, requiring more samples than would be optimal.", "claims_and_evidence": "This paper is highly technical, not easy to read. I am not confident about my understanding of the claims made in this paper.", "methods_and_evaluation_criteria": "The suggested algorithm is sensible to me. The sample complexity and the batch complexity are key performance metrics for batched pure exploration problems.", "theoretical_claims": "I had a hard time parsing and understanding the statements in the main body. I gently believe that the proofs are solid, but I am not sure.", "experimental_designs_or_analyses": "- I believe some experiments on Top-K or TBP should also have been conducted.\n- In addition, I hope to see some experiments supporting the statement “$T_{min}$ is a tradeoff between prior knowledge and batch complexity”.", "relation_to_broader_scientific_literature": "I believe the research question that this paper asks is interesting and impactful. Given that the batched queries can be thought of as a restriction in the adaptivity, the results in this paper suggest how much we can reduce the adaptivity while preserving the sample complexity. I would believe that high level insights can also be applied in different learning tasks.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "A clear weakness of this paper is readability. See my suggestions below.", "other_comments_or_suggestions": "I would like to recommend the authors to refine the statements for better readability. For example,\n- In Assumption 2.2, it is totally unclear whether $y$ is a vector or a scalar. I would rather write: For any mean vector $\\mu$, there exists a vector $y$ such that $T^\\star(x \\mu + (1-x) y) = x^{-2} T^\\star(\\mu)$ for all $x \\in [0,1]$\n-  Lemma 2.1 is also extremely cryptic. Are $T_{min}$ and $T_{max}$ specific to the algorithm? Should it be $S_N$ instead of $S_n$?\n-  In Algorithm 1, the variables $r$, $t$, $N_i$ are initialized but never updated.\n- …", "questions_for_authors": "Although I was not able to follow all the details, I am curious about the meaning of $T_0$ in Algorithm 1. It seems like an algorithm parameter, but it appears in Theorem 3.11 only, which implies that a larger $T_0$ leads to smaller batch complexity and smaller sample complexity without losing anything. Does Theorem 3.11 hold only if $T^\\star(\\mu) \\geq T_0$? Otherwise, why don't we set $T_0$ to be extremely large.", "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": "urGU0fR96e", "reviewer": "Reviewer_mSwP", "summary": "The paper investigates the batch complexity of fixed-confidence pure exploration problems in stochastic multi-armed bandits (MAB), where the algorithm is allowed to change its sampling strategy only across batches. The authors derive novel instance-dependent lower bounds on the number of batches required by any sample-efficient algorithm for general pure exploration tasks. They propose a general batched algorithm named \"Phased Explore then Track\" (PET), inspired by the Track-and-Stop method, and provide upper bounds on its expected sample and batch complexities. Numerical results are presented to show the effectivenes of the algorithm.", "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": "We are thankful to the reviewer for their helpful comments.\n\nFirstly, we'd like to redirect the reviewer to the two last paragraphs of our response to reviewer yvDd: the bound on the sample complexity in Theorem 3.11 was not accurate in the regime of big $T_0$. The parameter $T_0$ impacts the size of the first batch, and needs to strike a balance between sample optimality for easy instances, and round complexity for hard instances.\nWe have not tried varying $T_0$ in the experiments, to try and keep all the compared algorithms with the same initial batch size so none would be particularly penalized by how easy/hard the tested instance was.\n\nWe have thought of a few ways to replace uniform exploration. One would be to try and generalize BAI arm elimination schemes (see for example Algorithm 2 of Jin et al 2023), in which suboptimal arms stop being sampled. In general pure exploration, one could imagine stopping an arm $i$ once $N_i\\geq \\overline{w}^*_i(B)\\overline{T}^*(B)$, since no instance in the confidence set would require more samples of that arm.\nWe could also forgo uniform sampling altogether, only sampling according to $\\overline{w}^*(B)\\overline{T}^*(B)$ at each batch. However, either of those methods would make the confidence set $B$ behave in more complex ways.\n\nIn the most general setting we consider, there is no obvious way of computing $\\overline{w}^*(B)$ and $\\overline{T}^*(B)$. Under Assumption 3.9, one would need to compute $w^*(\\mu)$ and $T^*(\\mu)$ over $B$ and find the supremum of $T^*$ (heuristically, finding the most difficult instance in $B$).\nHowever, in BAI and thresholding this is much easier, since we know precisely where the hardest instance $b$ lies.\nIn BAI, it is the instance in which the best arm is moved down as much as possible, and the other arms moved up as much as possible.\nIn thresholding, it is the instance in which every arm is moved closer to the threshold. See Appendix C.5 for the proofs, and line 1330 for definition of $b$ in the BAI case.\nBecause of this, computing $\\overline{w}^*(B)$ and $\\overline{T}^*(B)$ has exactly the same cost as computing $w^*(\\hat{\\mu}_t)$ and $T^*(\\hat{\\mu}_t)$ in Track-and-Stop, and any method used to compute those also applies to our algorithm.", "claims_and_evidence": "The claims presented in the submission are supported by convincing evidence. The authors provide theoretical proofs for the lower bounds on batch complexity (Lemma 2.1 and Theorem 2.3), as well as detailed analyses of their proposed algorithm's upper bounds. Experimental results validate the effectiveness of the proposed algorithm", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem at hand.", "theoretical_claims": "I skimmed through the proofs of the main theoretical claims. The proofs appear sound and mathematically rigorous, with no evident errors.", "experimental_designs_or_analyses": "No significant issues were identified with these experimental designs or analyses.", "relation_to_broader_scientific_literature": "The paper's contributions relate to existing literature on batched bandit algorithms and pure exploration problems and collaborative bandits with communications (which can be interpreted as batched observation). It builds upon fundamental work on fixed-confidence pure exploration (Garivier & Kaufmann, 2016). It generalizes previous studies that focused specifically on BAI or Top-k identification to the class of pure exploration problems with batched observation.", "essential_references_not_discussed": "The most relevant references have been discussed.", "other_strengths_and_weaknesses": "See comments in the other sections.", "other_comments_or_suggestions": "Typos:\n\nPage 4 line 177: \"or\" → \"of\"\n\nPage 5 line 329: \"an other assumption\" → \"another assumption\"\n\nPage 8 line 439: \"That effect that was first observed\" → \"That effect was first observed\"", "questions_for_authors": "1. How sensitive is the algorithm's performance to the choice of $T_0$? How significantly does it affect your empirical results?\n\n2. Could you elaborate further on potential approaches to replace uniform exploration (Lines 6-9 in Algorithm 1) with more adaptive strategies for general pure exploration problems? Would such approaches significantly reduce practical sample complexities?\n\n3. Have you considered computational aspects when implementing your algorithm? In practice, how costly is it to $\\bar{w}^\\star$ and $\\bar{T}^\\star(\\cdot)$? Is there a way to solve it through bisection methods similarly to (Garivier & Kaufmann, 2016) for the Top-1 (BAI) setting?", "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": "AacnJEQX8Q", "reviewer": "Reviewer_KpQ9", "summary": "The authors derive an instance-dependent lower bound on the batch complexity required by any $\\delta$-correct pure exploration algorithm. This lower bound is expressed as a function of the instance’s complexity,  $T^\\star(\\mu)$, and shows that as sample efficiency improves, the minimal number of batches required increases. This result is novel in that it quantifies, for every instance, the minimal “round” or batch count needed.\n\n Building on the Track-and-Stop methodology, the paper introduces a new algorithm called Phased Explore then Track (PET). The algorithm is designed in phases. In each phase, it first performs uniform exploration to reliably estimate the means and the instance-dependent complexity; then, if a predetermined complexity threshold is met, it transitions into a more adaptive sampling phase. The authors prove that PET is $\\delta$-correct and provide upper bounds on both its sample complexity (which is nearly optimal, up to logarithmic factors in  $1/\\delta$ ) and its batch complexity.\n\nThe general results are then specialized to well-studied pure exploration tasks such as Best-Arm Identification (BAI), Top-k, and thresholding bandits. For these settings, the authors show that the algorithm’s performance nearly matches the derived lower bounds.\n\t\tEmpirical results are provided for both BAI and thresholding bandit problems. The results indicate that PET achieves a favorable balance between sample and batch complexities by using only a few batches while keeping the sample complexity near-optimal.\n\t\tFor the stopping rule as they consider non-parametric distribution, they use mixtures method.", "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": "We thank the reviewer for their insightful suggestions.\n\nThe suggested paper, ``Optimal $\\delta$-correct best arm selection for heavy tailed distributions'', contains a BAI algorithm for a different class of non-parametric distributions (given by a moment constraint).\nThey also use batches in a Track-and-Stop method. The main motivation for the batches seems to be to reduce the computational cost of the algorithm, and minimizing the expected batch complexity is not a goal they consider (and no bound is given).\nThey mostly use constant batch sizes, which would lead to a batch complexity that is proportional to $\\log(1/\\delta)$, which should not be the case according to the lower bound. \nThank you for the reference: we will include discussion of that paper in our revision.\n\nOn the usage of an $l$-norm instead of a KL divergence, it is first due to our goal of tackling the non-parametric sub-Gaussian setting, in which this is the natural distance measure.\nIf we were to consider parametric families of distribution, we would want to use a KL divergence.\nHowever a hurdle with that lies in Lemma 3.10. Indeed, we would need to have guarantees about the variation of the KL in a confidence region around a mean estimate.\nInvestigating how to get past this problem and generalize the results for $\\tilde{T}^*$ instead of $T^*$ would be interesting future work.\n\nWe do not understand the last question about recovering the results of Garivier and Kaufmann 2016 by imposing structure on the batches. Could you expand on what you mean by that question?\nTheir algorithm is not batched (or rather has all batches of size 1), so we don't see what the structure on the batches would be.", "claims_and_evidence": "Theorem 2.3 provides a lower bound on the necessary number of batches; Theorem 3.5 establishes the $\\delta$-correctness of the PET algorithm; and Theorem 3.11 gives upper bounds on both the expected batch and sample complexities.\n\nAll the proofs are given in appendix, and seem correct.\n\nSome numerical experiments support the theoretical findings.\n\n\n## update after rebuttal\"\nI have read the discussions and finally I keep my assessment unchanged", "methods_and_evaluation_criteria": "The synthetic numerical experiments provide sufficient evidence given the theoretical nature of the work.", "theoretical_claims": "proof coherence checked globally", "experimental_designs_or_analyses": "no relevant here", "relation_to_broader_scientific_literature": "The state of the art is correct", "essential_references_not_discussed": "nothing special", "other_strengths_and_weaknesses": "The use of batches in best-arm identification problems is real, and interesting to study theoretically.\nThe contributions are solid and rather clear, though pretty unsurprising.\nThis work hence seems to be a decent incremental contribution.", "other_comments_or_suggestions": "On page~1, the introduction could benefit from clearer phrasing in the following sentence: \"...samples is fixed and the objective is to minimize the probability of error, \\textbf{we} talk about fixed-budget pure exploration (Audibert et al., 2010).\" As the paper focuses on fixed-confidence settings, the use of the word \\textbf{we} here may cause confusion.\n\t\n A clearer motivation for investigating batched methods would enhance the paper. Fully adaptive algorithms, such as Track-and-Stop, require solving a min-max optimization problem at each round to determine optimal sampling proportions, which can be computationally intensive and impractical in many applications. In contrast, batched methods fix the sampling strategy for an entire batch, thereby reducing computational demands and enabling parallel sampling. Emphasizing this computational trade-off would further justify the focus on batched approaches, particularly in scenarios with delayed feedback or limited adaptivity.\n\t\n In the paper \"Optimal $\\delta$-Correct Best-Arm Selection for Heavy-Tailed Distributions,\" a batch algorithm is introduced. The authors should cite this work and discuss the differences between their approach and the one presented in that paper.\n\t\nRegarding Assumption 3.8 and line 5 of the algorithm, the paper employs an $l$-norm to quantify the distance between instances. Given that KL divergence often provides a tighter and more informative measure—especially in Gaussian settings—could the authors clarify the rationale behind this choice? Would it be possible or beneficial to replace the $l$-norm with a KL divergence measure in these parts of the analysis? Clarifying this point would help readers understand the trade-offs between tractability and the precision of the bounds.\n\t\n The definition of $\\mu^0$ as the initial instance appears to be missing. Including this definition would enhance clarity.\n\t\n\n It would be helpful to add some intuition for Assumption 2.2, such as: \"It essentially states that the ‘difficulty’ (as measured by the inverse of the complexity) scales as $x^2$ when the instance is linearly scaled in this manner. This property is useful for constructing sequences of instances and analyzing how the complexity evolves as the instances become progressively more challenging (i.e., as the gaps shrink).\"\n\t\nOn page~7, it seems that the authors intended to refer to Lemma~3.7 rather than Theorem~3.7, as the latter does not appear in the paper. Clarifying this reference would improve accuracy.", "questions_for_authors": "Is it possible to directly recover the results of Garivier–Kaufmann (2016) by imposing some structure on the batches? Clarification on this point would be appreciated.", "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: **Summary:** This work studies the batch complexity in pure exploration, proposing a novel characterization that differs from the standard $\log(1/\Delta_2)$ bound. Instead, it argues that the optimal batch complexity should scale as $\log(T^*/T_{\min})$, where $T^*$ denotes the optimal sample complexity and $T_{\min}$ is a given lower bound. The authors analyze several variants of the multi-armed bandit problem, establishing both upper and lower bounds on the batch complexity that nearly match.

**Justification:** All reviewers agree that this paper contributes significantly to the study of pure exploration, particularly in the underexplored area of batch complexity. Notably, it provides the first known lower bound for batch complexity in this setting. However, the current bounds on several key quantities, such as batch and sample complexity, remain somewhat loose. This reduces the perceived strength of the proposed framework and algorithms. I recommend that the authors include further discussion or refinements to better clarify the tightness of these bounds.
Decision: Accept (poster)