Optimal Batched Best Arm Identification
Authors: Tianyuan Jin
Yu Yang
Jing Tang
Xiaokui Xiao
Pan Xu
Venue: NeurIPS 2024 poster (2024)
Keywords: Best arm identification
Batched bandits
Primary area: bandits

Abstract: We study the batched best arm identification (BBAI) problem, where the learner's goal is to identify the best arm while switching the policy as less as possible. In particular, we aim to find the best arm with probability $1-\delta$ for some small constant $\delta>0$ while minimizing both the sample complexity (total number of arm pulls) and the batch complexity (total number of batches). We propose the three-batch best arm identification (Tri-BBAI) algorithm, which is the first batched algorithm that achieves the optimal sample complexity in the asymptotic setting (i.e., $\delta\rightarrow 0$) and runs in $3$ batches in expectation. Based on Tri-BBAI, we further propose the almost optimal batched best arm identification (Opt-BBAI) algorithm, which is the first algorithm that achieves the near-optimal sample and batch complexity in the non-asymptotic setting (i.e., $1/\delta$ is finite), while enjoying the same batch and sample complexity as Tri-BBAI when $\delta$ tends to zero. Moreover, in the non-asymptotic setting, the complexity of previous batch algorithms is usually conditioned on the event that the best arm is returned (with a probability of at least $1-\delta$), which is potentially unbounded in cases where a sub-optimal arm is returned. In contrast, the complexity of Opt-BBAI does not rely on such an event. This is achieved through a novel procedure that we design for checking whether the best arm is eliminated, which is of independent interest.

Optimal Batched Best Arm Identification
Tianyuan Jin', Yu Yang", Jing Tang', Xiaokui Xiao', Pan Xu
"National University of Singapore
"The Hong Kong University of Science and Technology (Guangzhou)
Duke University
(ckxiao>@nin edu. ag, jingtangGust. hk, {yu. {yu. yang, pan. xu) xuuudukeeeeeem edu
Abstract
We study the batched best arm identification (BBAI) problem, where the learner's s goal to identify the best arm while switching the policy as less as possible. In particular, we aim to find the best arm with probability 1-8 for some small constant 6 > while minimizing both the sample complexity (total number of arm pulls) and the batch complexity (total number of batches). We propose the three-batch best arm identification (Tri-BBAl) algorithm, which is the first batched algorithm that achieves the optimal sample complexity in the asymptotic setting (i.e., 0 + 0) and runs in 3 batches expectation. Based on Tri-BBAI, we further propose the almost optimal batched best arm identification (Opt-BBAI) algorithm, which is the first algorithm that achieves the near-optimal sample and batch complexity in the con-asymptotic setting (i.c., 5 is finite), while enjoying the same batch and sample complexity as Tri-BBAI when tends to zero. Moreover, in the non-asymptotic setting, the complexity of previous batch algorithms is usually conditioned event that the best arm returned (with probability of at least 6), which is potentially unbounded in cases where sub-optimal arm is returned. In contrast, the complexity of Opt-BBAI does not rely on such an event. This is achieved through novel procedure that we design for checking whether the best arm is eliminated, which is of independent interest.
the
Introduction
Multi-armed bandit (MAB) is fundamental model in various online decision-making problems, including medical trials [40], online advertisement [5], and crowdsourcing [43]. These problems typically involve bandit with multiple arms, where each arm follows an unknown distribution with a mean value. At each time step, the learner selects an arm, and receives a reward sample drawn from the chosen arm's s distribution. Best arm identification (BAI) aims to identify the arm with highest mean reward, which can be approached with fixed budget or fixed confidence level [14, 4, 19].
In this paper, assume that there is unique best and study BAT with fixed confidence. Specifically, we consider a set [n] = {1, 2..... n of n arms, where each arm i is associated with a reward distribution having mean value μ4z Without loss of generality, for bandit instance denoted by {14 .2..... Pa we assume that
2 ... 2 pn. At each time step t, the learner selects an arm and observes sample drawn independently from the chosen arm's 's distribution. In the fixed confidence setting, the learner aims to correctly identify the best arm (arm 1 in our context) with probability of least
where 8 > 0 a pre-speeifee precccedfe confidence parameter. Meanwhile, the learner seeks to minimize the total number of arm pulls, also known as the sample complexity.
Denote by a" (A) (A: a (A) # }} be a set of models that have a different best arm from the model Ja, and Pt = (w E PT: Σi W/ 1} be the probability simplex. Garivier and Kaufmann [17] showed that for bandits with reward distributions that are continuously parameterized by their means, the number N; of pulls
arg max; the best arm for an arbitrary bandit instance X. Let Ali
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

by any algorithm that returns the best arm with probability of at least 1 - is bounded by
[N6]
lim inf 8-2
T (11),
(1.1)
l0g(1/6)
where T (p) is defined according to
n Σ ws d(ui, Xi) ditssii))
T (M)
sup weP
inf ACAlt(A)
(1.2)
and d(us; A;) is the Kullback-Leibbe (KL) divergence of two arms' distributions with means μi; and As respectively. We say that an algorithm achieves the asymptotically optimal sample complexity if satisfies
E.,
lip
S (m))
(1.3)
8->0 log(1/8)
The well-known Track-and-Stop algorithm [17] solves the BAI problem with asymptotically optimal sample complexity. However, it fully sequential algorithm, which is hard to be implemented in parallel. The learner in such an algorithm receives immediate feedback for each arm pull, and adjusts the strategy for the next arm selection based on the previous observations. Unfortunately, this sequential approach may not be feasible in many world applications. For instance, in medical trials, there is typically a waiting time before the efficacy of drugs becomes observable, making impossible to conduct all tests sequentially. Instead, the learner needs to group the drugs into batches and test them in parallel. Similarly, in crowdsourcing, the goal is to identify the most reliable worker for specific task by testing candidates with sequence of questions. Again, there is often waiting time for workers to finish all the questions, necessitating the grouping of workers into batches and conducting parallel tests. In such scenarios, the results of pulling arms are only available at the end of each batch [22, 1, 39, 37, 15, 24, 25, 38].
Motivated by these applications, we study the problem of batched best arm identification (BBAI). In BBAI, we are allowed to pull multiple arms in a single batch, but the results of these pulls are revealed only after the completion of the batch. The objective is to output the best arm with a high probability of at least 1 - ó, while minimizing both the sample complexity (total number of pulls) and the batch complexity (total number of batches). This leads to the following natural question:
Can we solve the BBAI problem with an asymptotically optimal sample complexity and only using constant number of batches?
Furthermore, the aforementioned results hold only in the limit the confidence parameter å ap- proaches zero, which may provide limited practical guidance since we often specify fixed confidence level parameter > O. To address this, some algorithms [31, 21] have been proposed solve the BAI problem with finite confidence. Specifically, for some universal constant C, these algorithms satisfy that with probability
E[Nd S O
Σ log log A-
(1.4)
A7
where A, = 141 p4- In addition, Jamieson al. [21] demonstrated that for two-armed bandits, the term log log A,_ is optimal as 2 - O, where A2 is assumed to be the gap between the best arm and A3
the second best arm. In the context of the batched setting. Jin al. [22] proposed an algorithm that achieves the sample complexity in (1.4) within Olog (n) log (1/ 1/Az)) batches, where log (n) is the iterated logarithm function'. Furthermore, Tao et al. [39] proved that for certain bandit instances, any
algorithm that achieves the sample complexity bound shown in (1.4) requires at least S2 log A
log log A batches. It should be noted that the batched lower bound proposed by Tao et al. [39] assumes ò as a constant, making it inapplicable in the asymptotic setting. Therefore, an additional question that arises is:
Can we achieve the optimal sample complexity (1.3) and (1.4) adaptively, taking into account the specified confidence level parameter 5, while minimizing the number of batches?
SSpecifically, log" (n) denotes the number of times the function log(-) needs to be applied to n until the result less than 1.

---

Table 1: Comparison of sample and batch complexity of different algorithms. In the asymptotic setting (i.e., 8 - 0), the sample complexity of an algorithm is optimal if it satisfies the definition in (1.3). The field marked with "_" indicates that the result is not provided. The sample complexity presented for [31, 22] is conditioned on the event that the algorithm returns the best arm, which can be unbounded when it returns sub-optimal arm with certain (non-7ero) probability (see Remark 4.4 for more details). In contrast, the sample complexity presented for [17, 26] and our algorithms is the total expected number of pulls that will be executed.
Algorithm
Asymptotic behavior (6 -+
Fimite confidence behavior
Sample complexay
Batch complexity
Sample complexity
Batch complexity
Karnin et al. [31]
Not optimal
(logn log R
lngtln Ar"))
(logn log + Ollog (xx log 1
Jin et al. [22]
Not optimal
Ollog 2,>
Inginnd, o? Ounli (wrnin))
Eist
Wang et al. [42]
Optimal
oly (log(T/0))
Agrawal et al. [?]
Optimal
F" (as) Too)log (m ollog 8
Karpov al. [32]
10
Inginilig log 2::2)
Oflng +
Lower bound [39]
Iostlan 1,
(Qlo(1//a2))
Tri-BBAI (Our Algorithm I)
Optimal
Opt-BBAI (Our Algorithm 2)
Optimal
3
0 Eis1
Ingiis log 4. 37
OfTor x))
In this work, we provide positive answers to both of the aforementioned questions. Specifically, the main contributions of our paper can be summarized as follows:
We propose Tri-BBAI (Algorithm 1) that returns the best arm with a probability of at least 1 - by pulling all arms for total number of at most T* log((/)) times when å + O. Tri-BBAI employs three batches in expectation when 8 - 0. Therefore, Tri-BBAI achieves the optimal sample within constant batches. As comparison, Track- [17] also achieves the optimal sample complexity but requires solving the fight-hand side of (1.2) after each arm pull, resulting in a batch complexity of the same order the sample complexity, which is a significant computational overhead in practice.
Built upon Tri-BBAI, we further propose Opt-BBAI (Algorithm 2) that runs in O(log(1/A)) expected batches and pulls at most (
is1 Ei>1 A, log(n n log ()) expected number of arms for finite confidence d. is also important to note that Opt-BBAI achieves the same sample and expected batch complexity as Tri-BBA asymptotically when 5 - O. Moreover, for the finite confidence case, this sample complexity matches (1.4) within a log(.) factor and matches the optimal batched complexity within log log(-) factor. To the best of our knowledge, Opt-BBAI is the first batched bandit algorithm that can achieve the optimal asymptotic sample complexity and the near-optimal aonaasympooiic sample complexity adaptively based on the assumption 8.
Notably, in the non-asymptotic setting, the complexity of earlier batch algorithms [22, 32, 39, 24] typically depends on the event of returning the best arm, which occurs with probability of at least 6. However, this complexity could potentially become unbounded if a sub-optimal arm is returned instead. Unlike these algorithms, the complexity of Opt-BBAI is not contingent on such an event. This is made by employing an innovative procedure to verify if the best arm is eliminated, a method that holds its independent interest. To the best of our knowledge, Opt-BBAI is the first algorithm that achieves the optimal asymptotic sample complexity while providing the optimal non-asymptotic sample complexity within logarithm factors.
We also conduct numerical experiments to compare our proposed algorithms with the optimal sequential algorithm Track-and-Stop [17], and the batched algorithm Top-k 8-Elimination [22] on various problem instances. The results indicate that our algorithm significantly outperforms the Track and Stop method in terms of batch complexity, while its sample complexity is not much worse than that of Track and Stop. Additionally, our algorithm demonstrates notable improvement in sample complexity compared to [22], while exhibiting similar batch complexity.
For ease of reference, we compare our results with existing work on batched bandits in Table 1.
2 -Non-asymptott here refers to finite confidence. In this paper, we use names non-as aonastymtooicc and finite confidence interchangeably.
Due to the space limit, put the experimental results in Appendix E.
3

---

Table 2: Comparison of sample complexity of different algorithms.
Algorithm
Asymptotic behavior (6 - 0)
Finite-confidence behavior
Kalyanakrishnan et al. [30]
((
((H(p) log(H
O
Karnin et al. [31]
((H( log(1/8))
o
Σist
log(log A
Garivier and Kaufmann [17]
T' (1)) log(1/0)00(1/0))
Jamieson et al. [21]
((H(4))0((1/8)
Eiss
logilog d, 11
of ((H()) log H()))")) )r))) ) O( (u)²) ((H Amia)) O(HH(u) mmmi
Jourdan and Degenne [26]
(o)
Degenne ct al. [12]
T (
Katz-Samuels al. [33]
O(T' (og(1/6)
Wang et al. [42]
T' log(1 (00(00000000(10
Opt-BBAI (Our Algorithm 2)
T (4) log Log(L/))+0(1/))
Eisl
log(n log
2 Related Work
The BAI problem with fixed confidence is first studied for 00, 1] bounded rewards by Even-Dar et al. [14]. The sample complexity of their algorithm scales with the sum of the squared inverse gap, i.e., (n)) Ei>1 1/ Garivier and Kaufmann [17] showed that H()) " (n) < 2H (ni) with (#) defined in (1.2) and proposed the Track-and Lorkk-ad-Stoor algorithm, which is the first one in the literature proved to be asymptotically optimal. Later, Degenne et al. [12] viewed T (H)) as a min-max game and provided an efficient algorithm to solve it. Jourdan et al. [27] studied the asymptotically optimal sample complexity for any reward distributions with bounded support. Degenne et al. [13] studied pure exploration in linear bandits. Their proposed algorithm proved to be both asymptotically optimal and empirically efficient.
There are also many studies [30, 10, 8, 31] that focus providing non-asymptotic optimal sample complexity. The best non-asymptotic sample complexity was achieved by Chen et al. [10], which replaces the term log log A, in (1.4) with a much smaller term. Furthermore, when we allow a loss of the quality of the returned arm, the problem is known as (c, 5) BAI, for which various algorithms [29, 14, 6, 9] are proposed, achieving the worst-case optimal sample complexity.
There are a few attempts to achieve both the asymptotic and non-asymptotic optimal sample complex- ity. Degenne et al. [12] provided a non-asymptotic sample complexity (nTT (Hx)²). which could be mI (H) larger than the optimal sample complexity. Recently, Jourdan and Degenne [26] managed to achieve sample complexity that is 8-asymptotically optimal (with w1 fixed at 1/3 in (1.2)), render- ing it asymptotically optimal up to factor of L/B. Mcanwhile, they also reached a non-asymptotic sample complexity of ((H( - log H )o)) for some a > 1, where H(u) = Ei>, 1/4?. Wang et al. [42] explored both asymptotic and non-asymptotic sample complexities. Their algorithm achieves asymptotic optimality and shows a non-asymptotic sample complexity of On ( min)) However, this non- -aymytttooiic sample complexity is nH (11)² /// / away from being optimal. Jour- dan et al. [28] studied (c, PAC BAL proposing an asymptotically optimal algorithm and providing non-asymptotic sample complexity. When
0, it aligns with our setting, our non non-asympon asymptotic sample complexity is better scaled. Specifically, Jourdan ct al. [28] offered a non-asymptotic sam- ple complexity scale of n/ A3 log(1/ / A2), whereas ours is more instance-sensitive complexity is related to all gaps, not just 22. Additionally, Jourdan et al. [28] considered a practical return result any time while still ensuring good guarantee on
our sample
scenario where the algorithm the returned arm. For ease of reference, we summarize the sample complexity of different algorithms in Table 2. As shown in Table 2, our algorithm is the only one that achieves both the asymptotic optimality and non-asymptotic optimality within logarithm factors.
Another line of research [31, 4, 7] investigated BAI with fixed budget. where the objective is to determine the best arm with the highest probability within T pulls. Audibert et al. [4] and Karnin al. [31] offered finite-time bounds for this problem, while Carpentier and Locatelli [7] presented tight lower bound, demonstrating that such finite-time bounds[4, 31] are optimal for certain bandit
"To derive the near- optimal non non-asy asymptotic sample complexity, a should be 1. However, As explained in their original paper. the algorithm will be sub-optimal set a close 1.

---

instances. However, the asymptotic optimality for this problem remains unknown. Interested readers are referred recent advancements[11, 35] the asymptotic results of BAI with fixed budget.
In addition, some recent works [1, 22, 39, 32] also focused on hatched BAT in non-asymptotic setting. Agarwal et al. [1] studied the batched BAI problem under the assumption that A2 is known. They proposed an algorithm that has the worst-case optimal sample complexity of O (n and runs in (1g"(1) batches. Later, Jin et al. [22] provided the algorithms that achieves the sample complexity given in (L.4) within (log(1/ /2)) batches, where Ô hides the log log(-) factors. Tao et al. [39] studied the BAI problem in the general collaborative setting and showed that no algorithm can achieve (I.4) with o(log / log log - batches. Karpov et al. [32] further proposed an algorithm
which has the sample complexity Ei>1 log(n log A-2 and the batch complexity (loog(1/A)) (2)). We
note that the lower bound of batch complexity given by Tao et al. [39] can only be applied to constant 8. In other words, the lower bound of complexity for the asymptotic setting remains unknown. Agrawal et al. [2] studied the optimal batch size for keeping the asymptotic optimality. They showed algorithm with batch size m o(log(1/6) achieves the asymptotic optimality. The batch complexity of the algorithm is O(7 (p) (og(1/0)/m) Wang et al. [42] provided an algorithm that uses O( Vlogo-o 8-1) batches and retains asymptotic optimality for linear bandits. However, for the asymptotic setting, such batch size is still too large as it grows to infinity as 6 decreases to O.
3
Achieving Asymptotic Optimality with at Most Three Batches
3.1 Reward Distribution
We assume the reward distributions belong to a known one-parameter exponential family that is commonly considered in the literature [17, 16, 36]. In particular, the measure ve of such probability distributions with respect the model parameter 0 satisfies dree
dp (a) exp(x0 b(0)), for some measure p and b(0) = log(ʃ e² dp(x)). For one-parameter exponential distributions, it is known that (0) [F and the mapping (/ + 0 is one-to-one. Moreover, given any two mean values and μt. we define d( p²) to be the Kullback-Leibler divergence between two distributions with mean values μ and p².
3.2 The Proposed Three-Batch Algorithm
Algorithm I shows the pseudo-code of our proposed Tri-BBAI algorithm. In particular, Tri-BBAI has four stages. In what follows, we elaborate on the details of each stage.
Stage I: Initial exploration. In this stage, we pull each arm for L1 times. Denote by i" (t) the arm with the largest empirical mean at time (i.e., after we pull all arms for a total number of times), i.e. (t( = max;g[m] (t). Let To = nLI, Fix t T--1 2 To, we let by (t:(t) + c for i * 8" (t) and bg (c) for i (t). Let w0" (1²) = arg wax inf inf (E w3 d(us, Az)). Then, we calculate w" (b?) according to Lemma A. and T* (B²) according to Lemma A.2. We note that arm 1 is assumed be the arm with the highest mean in these two lemmas. However, in the context of ba, the index of i (t) might be different. To align with the standard practice, we can rearrange the indices of the arms 6 so that i" (I) corresponds to index 1.
for the aforementioned ba = [b]. bbg ... }.
Purpose.
To achieve the asymptotic optimality, we attempt to pull each arm for around wi (+)
times. We can show that with a high probability. w (b*) (6"))"((b")) (b9)) is close to wi (u)T" (H), which implies that pulling arm for a number of times proportional w (b²)I"" is likely ensure the asymptotic optimal sample complexity.
Stage II: Exploration using w* (b²) and T' (b²). Stage II operates in batches with the maximum number of batches determined by log(1/5). At batch g, each arm i is pulled pe. TV times in total. Here
T = min { (aw, (b2)7" log 5-1
(3.1)
where the definition of wo wb²) and (ba) could be found in Stage I. We then evaluate the stage switching condition, |n (bo) - wi (be--) S 1/vī for all i E [m]. If this condition is met, we go to the next stage; otherwise, we proceed to the next batch within Stage II.
5

---

Algorithm 1: Three-Batch Best Arm Identification (Tri-BBAI)
Input: Parameters e, 6, L2, L3. a and function B(t, 8). Output: The estimated optimal arm.
Stage Round exploration
for i 4- 1 to n. do
[ Pull arm for L1 times;
t t i-n and TO &
5 Stage HI:Ronnd exploration
Let wō (b") = (1/n, 1/n, 1/n) and Tア = L1 for all i [n];
for q = 1,2
lo/(1/)) do
(t) t maXie[n] (t);;)
for each i E [n] (t) do
10
L bf (.(t) +G
(0)(0) (1)
12
for i < 1 to n do
Pull arm i for (0, T. pec ] times;
/**/ Note that 7 min {aw] (69) (b9) log L2] by (3.1)
14
1 t- (0, 7 (0 ]
15
1 (b9) W (ba- < 1/ for all E [n] then
16
Break;
17
Tq t;
18 T + t, and (T) = maXie[a] PT(T);
19 Stage III: Statistical test with Chernoff's stopping rule;
Compute Zz(T) according to (3.3);
21 miijje(J) (m (T( 2 ((T 8/2) then
L return (T):
23 Stage IV: Round 3 exploration for 1 to do
24 L Pull arm for total max(0, La L - T:) times;
+ nL3, and (t) < max (t):);
return i" (t):
Purpose. Pulling arm proportional to u (b*)T"* (b?) provides statistical evidence for the reward dis- tributions without sacrificing sample complexity compared to the optimality per our above discussion. Meanwhile, we also set a threshold L2 to avoid over-exploration due to sampling errors from Stage I.
The rationale for running Stage II in multiple batches is based empirical considerations. In experiments, 8 is always finite. Consequently, the error of arm i, (i, Hal, remains constant since the number of pulls of arms is limited. Given that the stopping rule in Stage III is highly dependent on the error arm i and the number of pulls T; := maxp:peN 1 7." there is constant probability that the stopping rule may not be met, leading to significant sample costs in Stage IV. Adding the condition in Line ensures that w" (ba) converges and that the sample size TV as defined by w" (b?) and T'* (b?). closely approximates aw" (H)l** (M) log 5-1, This alignment significantly increases the probability that the stopping rule will be satisfied in experiments.
Moreover, such modification doesn't hurt any theoretical results. To explain, in our analysis for Tri-BBAI, we demonstrate that 5 approaches 0, w" (b") will be very close to (/1) and the probability that Line 15 is not satisfied could be bounded by 1/log² 8-1, which means with high probability Stage II costs 2 batches. Besides, q < log(1/5) which implies that even if Line 15 is not satisfied, the number of batches required for Stage number of batches required for Stage II is 2 as 8 approaches 0.
most log(1/ (1/).. Therefore, the expected

---

Stage III: Statistical test with Chernoff's stopping rule. Denote by (t) the number of pulls of arm at time t. For each pair of arms and j. define their weighted empirical mean as
(L)(() == N:(1) + (1) + N₂(t) it(()
(.(t) (.(t)
(3.2)
NN(1) + N2))
where (1) and (t) are the empirical means of arms and j time t. For ja(()) 2 (z((), define
Zi d(jsstt, (t)())) + d(ps(t) (t))))
(3.3)
(, (t) == (t)
We test whether Chernoff's s stopping condition is met (Line 21). If so, return the arm with the largest empirical mean, i.e., i" (T). where r is the total number of pulls examined after Stage II.
Purpose. The intuition of using Chernoff's s stopping rule for the statistical test is two-fold. Firstly, if Chernoff's stopping condition is met, with a probability of at least - 6/2, the returned arm (7) in Line 22 is the optimal arm (see Lemma B. Secondly, when 5 is sufficiently small, with high probability, Chernoff's 's stopping condition holds (see Lemma B.4). As a consequence, our algorithm identifies the best arm successfully with high probability of meeting the requirement.
Stage IV: Re-exploration. If the previous Chernoff's stopping condition is not met, we pull each arm until the total number of pulls of each arm eqauls L.3 taking into account the pulls in the previous stages (Line 24). Finally, the arm with the largest empirical mean returned (L.nne 26).
Purpose. If Chernoff's s stopping condition is not met, i" (T) might not be the optimal arm. In addition, when each arm is pulled for La times, we are sufficiently confident that i" (t) is the best arm. Since the probability of Stage IV happening is very small, its impact on the sample complexity is negligible.
3.3 Theoretical Guarantees of Tri-BBAI
In the following, we present the theoretical results for Algorithm 1.
Theorem 3.1 (Asymptotic Sample Complexity). Given any 5 > 0, let c log log(d-1)> L
Vlog8- L2 6 log and L3 = (log 8-1) Meanwhile, for any given a E (1, e1.e/2]. define function (t,, as B(t, = log(log (1/8)t** ( /8). Then, for any bandit instance μt, Algorithm I satisfies
n
E, [N5]
lim 8-0
< (M).
log (1/8)
By letting a in Theorem 3.1 approach 1 (c.g., a = 1 + 1/ log )- we obtain the asymptotic optimal sample complexity.
Theorem 3.2 (Correctness). Let e, In, I2,, Lz, a. and (1,, be the same as in Theorem 3.1. Then, for sufficiently small 8 > 0, Algorithm 1 satisfies (i" (Na) + 1) S 8.
Theorem 3.3 (Asumptotic Batch Complexity). Let c, L1, Lz. L3. a. and B(t, 8) be the same as in Theorem 3.1. For sufficiently small 8 > 0, Algorithm 1 runs within 3 + o(1) batches in expectation. Besides, Algorithm runs within 3 batches with probability - 1/ log(1/²))
To the best of our knowledge, all previous works in the BAI literature [18, 12, 2, 42] that achieve the asymptotic optimal sample complexity require unbounded batches 5 - 0. In contrast, Tri-BBAI achieves the asymptotic optimal sample complexity and runs within 3 batches in expectation, which is significant improvement in the batched bandit setting where switching to new policies is expensive.
Remark 3.4. Apart from best arm identification, regret minimization is another popular task in bandits, where the aim is to maximize the total reward in T rounds. Jin et al. [25] proposed an algorithm that achieves a constant batch complexity for regret minimization and showed that their algorithm is optimal when 7 goes to infinity. In regret minimization, the cost of pulling the optimal arm is O, indicating that the allocation we; (i.e., the proportion of pulling the optimal arm) is close to 1. In the BAI problem, the main hardness is find the allocation w, for each arm since even pulling arm 1 will increase the sample complexity of the algorithm. Therefore, the strategy proposed by Jin al. [25] cannot be applied the BAI problem.
'Recent work by Kaufmann and Koolen [34] offers improved deviation inequalities allowing smaller selection of Btt, 8) without sacrificing the asymptotic optimality. However, it remains uncertain whether this refined parameter choice is applicable to our batched bandit problem. For ease of presentation, we use the parameter choice of & in Garivier and Kaufmann [17].
7

---

Algorithm 2: (Almost) Optimal Batched Best Arm Identification (Opt-BBAI)
Input:
Parameters 6, c, L1, I2, T.3, a and function B(1, 8). Output: The estimated optimal arm.
Stage I. and III: the same as that in Algorithm
Stage IV: Exploration with Exponential Gap Elimination
3 S. f- [n]. Bg f- 0, r + 1;
while [. do
//,4,, 8, x 6/ 6/(407/ (r),.r)),,, + O, and 7r + 8p; Let ey 6 2-2 Successive elimination /*/ Eliminate arms whose means lower than jar by at least cr for each arm E S, do
7
Pull arm for d, + 32 log(2 0,) times; Let P be the empirical mean of arm i; Let + maxjes, p. Se S <
10
11
Set Sr+1 Sr
12
Checking for best arm elimination /0*/ Reduce the risk of the best arm being eliminated
13
Let B, f- -B,-1 d, Sr]:
for j < do
15
for each arm E S S5+1 do
if Br 25 B, then
7j < (75)²: Repull arm i for total b 1og(2/7;) times;
19
Let p. be the empirical mean of arm in Sy; Eg 11;
if 3i E Sy. / > x. 2 then return Randomly return an arm S,;
21
22
23
r +
return The arm in Sp:
4 Best of Both Worlds: Achieving Asymptotic and Non-asymptotic Optimalities
The Tri-BBAI algorithm shown enjoy the optimal sample complexity with only three batches in the asymptotic setting. However, in practice, we are limited to finite number of samples and thus cannot go zero, which is critical concern in real-world applications. Consequently, obtaining the optimal sample and batch complexity in non-asympiotic setting becomes the ultimate objective of a practical bandit strategy BBAI. In this section, we introduce Opt-BBAI, which can attain the optimal sample and batch complexity in asymptotic settings and near-optimal sample and batch complexity in con-asymptotic settings.
We assume a bounded reward distribution within [0, 1]. which aligns with the same setting in the literature [31, 21]. Again, we consider that the reward distribution belongs one-parameter exponential family. By refining Stage IV of Algorithm 1, we can achieve asymptotic optimality and near non-asymptotic optimality adaptively based on the assumption å in various settings.
The pscudo-code for the algorithm is provided in Algorithm 2. The main modification from Algorithm I occurs in Stage IV. Intuitively, if the algorithm cannot return at Stage III, then the value of log 8-1 may be comparable to other problem parameters, such as 1/Ag. Therefore, we aim to achieve the best possible sample and batch complexity for the non-asymptotic scenario. Stage IV operates in rounds, progressively eliminating sub-optimal arms until a result is obtained. Each round consists of two components: Successive Elimination and Checking for Best Arm Elimination.
Suecessive Elimination. In the r-th round, we maintain set Sr, potential set for the best arm. Each arm S, then pulled d, = 32/e² (2g(2/5,,) times. Line 11, all possible sub-optimal arms climinated. This first component of Stage IV borrows its idea from successive elimination [14].

---

Purpose. After d, number of pulls, arms are likely to be concentrated on their true means within distance of c,/4 with high probability, Hence, with high probability, the best arm is never eliminated at every round of Line 11, and the final remaining arm is the best arm.
Issue of Best Arm Elimination. Due successive elimination, there is small probability (s 6,) that the best arm will be eliminated. The following example illustrates that, conditioning on this small-probability event, the sample and batch complexity of the algorithm could become infinite.
Example 4.1. Consider a bandit instance where μr > 122 = As > M4 2 ... 2 ju. the best arm is eliminated at certain round and never pulled again, the algorithm tasked with distinguishing between the 2nd and 3rd best arms will likely never terminate due to their equal means, leading to unbounded sample and batch complexity.
To address this issue, we introduce a Check Best Arm Elimination component into Stage IV.
Checking for Best Arm Elimination. In the r-th round, we represent the total sample complexity used up to the r-th round as B,.. We employ 75 as an upper bound for the probability that the best arm is eliminated in Sj. If Line 16 is true (B,2y-22 2 >> B,), we adjust Y to 7J and pull each arm in Sj for 32/e log(2/7g) times (Line 18), subsequently updating their empirical mean (Line 19). Finally, we return a random arm in S, if the condition at Line 21 holds.
If Line 16 is satisfied, it indicates that the sample costs, based on the event of the best arm being eliminated in the r-th round, exceed /2/2%, In this case, we increase the number of samples for arms in Sj and re-evaluate if their empirical mean is lower than that of the current best arm *, This ensures that the expected total sample costs, assuming the best arm is eliminated at Sj, are bounded by -i,=1 B I By. Line holds, we randomly return an arm from S,.. Since this only happens with a small probability, we still guarantee that Algorithm will return the best arm with probability of at least 1 - 8.
Purpose.
In what follows, we provide the theoretical results for Algorithm
Theorem 4.2. Let e, L1, L2, L3, a, and ((t, be the same as in Theorem 3.1. For finite å e (0, 1), Algorithm 2 identifies the optimal arm with probability at least 1 - 6 and there exists some universal constant C' such that [[NN) S C(E A log (n log 1-) and the algorithm runs in C' Colog(1/A))) (1/A2) expected batches.
When is allowed to go to zero, we also have the following result.
Theorem 4.3. Let e, L1, L2. L3. a, and B(t, be the same as in Theorem 3.1. Algorithm 2 identifies the optimal with probability at least 5 and its sample complexity satisfies simsups-p [/s[/Na//ogt (18) S aT (H4), and the expected batch complexity of Algorithm 2 con- verges to when 8 approaches 0.
The results in Theorems 4.2 and 4.3 state that Algorithm achieves both the asymptotic optimal sample complexity and constant batch complexity. Moreover, it also demonstrates near-optimal performance in both non-asymptotic sample complexity and batch complexity. Notably, this the first algorithm that successfully attains the optimal or near-optimal sample and batch complexity. adaptively, in asymptotic and non-asymptotic settings.
Remark 4.4. Jin et al. [22] achieved near-optimal sample and batch complexity in a non-asymptotic setting. However, their results are contingent on the event that the algorithm can find the best arm (with probability - 8). Consequently, with a probability of å there is no guarantee for its batch and sample complexity to be bounded. As demonstrated in Example 1. the batch and sample complexity in [22] could even be infinite.
In contrast, the batch and sample complexity introduced in Theorem 4.2 is near-optimal and does not rely on any specific event due to the procedure "checking for best arm elimination" we proposed. Our technique could be of independent interest and could be further applied to existing elimination- based BAT algorithms [14, 21, 22, 31] to ensure that the sample and batch complexity is independent of the cow-probability event that the best arm is climinated.

---

5 Conclusion, Limitations, and Future Work
In this paper, we studied the BAI problem in the batched bandit setting. We proposed a novel algorithm, Tri-BBAI, which only needs 3 batches in expectation to find the best arm with probability 1 1- 6 and achieves the asymptotic optimal sample complexity. We further proposed Opt-BBAI and theoretically showed that Opt-BBAI has near-optimal non-asymptotic sample and batch complexity while still maintaining the asymptotic optimality as Tri-BBAl does.
In our experiments, although Tri-BBAI utilizes a limited number of batches, its sample complexity does not match that of Garivier and Kaufmann [17]. Designing a batched algorithm with sample complexity comparable to Garivier and Kaufmann [17], while maintaining constant number of batches, presents an intriguing challenge.
As for future work, an interesting direction is to investigate whether our "checking for best arm elimination" could be beneficial to other elimination- based algorithms. Additionally, some research [3, 23] implied a strong correlation between batch complexity in batched bandit, and the memory complexity and pass complexity in streaming bandit. Thus, it could be valuable to assess if our techniques could enhance the results in the field of streaming bandit.
Acknowledgements
We would like to thank the anonymous reviewers for their helpful comments. This research is funded by Singapore Ministry of Education AcRF Tier 2 grant (A-8000423-00-00) by the National Research Foundation, Singapore under its AI Singapore Program (AISG Award No: 1SSG-PPD/2021- 01004[T]), by the Ministry of Education, Singapore, under its MOE AcRF TIER 3 Grant (MOE- MOET32022-0001), by National Key R&D Program of China under Grant No. 2023YFF0725 100, by the National Natural Science Foundation of China (NSFC) under Grant No. 62402410 and U22B2060, by Guangdong Basic and Applied Basic Research Foundation under Grant No. 2023A15151101
and by Guangzhou Municipal Science and Technology Bureau under Grant No. 2023A0300667 and 2024A04J4454,
In particular, T. Jin supported by Singapore Ministry of Education AcRF Tier 2 grant (A- 8000423-00-00) and by the National Research Foundation. Singapore under its AI Singapore Program (AISG Award No: BSSG-PDD2202111 11:20221010004 -01100([T)) X. Xiao was supported by the Ministry of Education, Singapore, under its MOE ACRF TIER Grant (MOE-MOET32022-000 supported by National Key R&D Program of China under Grant No. 2023YFF0725101 National Natural Science Foundation of China (NSFC) under Grant No. 62402410 and U22B2060, by Guangdong Basic and Applied Basic Research Foundation under Grant No. 0023A151511013 and by Guangzhou Municipal Science and Technology Bureau under Grant No. 2023A0300667 and 2024A04J4454. P. Xu was supported in part by the Whitehead Scholars Program the Duke University School of Medicine. The views and conclusions in this paper are those of the authors and should not be interpreted as representing any funding agencies.
J. Tang was partially
by the
References
[1] Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Proc. COLT, pages 39-75, 2017. (pp. 2 and 5.)
[2] Shubhada Agrawal, Sandeep Juneja, and Peter Glynn. Optimal 8-Correct Best-Arm Selection for Heavy-Tailed Distributions. In Algorithmic Learning Theory, pages 61-110. PMLR, 2020.
(pp. 3, 5, and 7.)
[3] Sepehr Assadi and Chen Wang. Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits. In Proceedingy of the 52nd Annual ACM SIGACT Symposium on theory of computing, pages 1237-1250, 2020. (p. 10.)
[4] Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pages 41-53, 2010. (pp. and 4.)
[5] Dimitris Bertsimas and Adam Mersereau. learning approach for interactive marketing to a customer segment. Operations Research, 55(6): 1201112011110 1135, 2007. (p. 1.)
10

---

[6] Wei Cao, Jian Li, Yufei Tao, and Zhize Li. On top-k selection in multi-armed bandits and hidden bipartite graphs. In Proc. NeurIPS, pages 1036-1044, 2015. (p. 4.)
[7] Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference on Learning Theory, pages 590-604. PMLR, 2016.
(p. 4.)
[8] Lijie Chen and Jian Li. On the optimal sample complexity for best arm identification. arXiv preprint arXiv: 2015. (p. 4.)
(9] Lijie Chen, Anupam Gupta, and Jian L... Pure exploration of multi-armed bandit under matroid constraints. In Proc. COLT, pages 647-669, 2016. (p. 4.)
[10] Lijie Chen, Jian Li, and Mingda Qiao. Towards Instance Optimal Bounds for Best Arm Identification. In Proc. COLT, pages 535 2017. (p.4)
[11] Rémy Degenne. On the Existence of a Complexity in Fixed Budget Bandit Identification. arXiv preprint arXiv:2303.09466 2023. (p. 5.)
[12] Rémy Degenne, Wouter M Koolen, and Pierre Ménard. Non-asymptotic pure exploration by solving games. Advances Neural Information Processing Systems, 32, 2019. (pp. 4 and 7.)
[13] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432- 2442. PMLR, 2020. (p. 4.)
[14] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi-armed bandit and Markov decision processes. In Proc. COLT, pages 255-270, 2002. (pp. 1, 4, 8, and 9.)
[15] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched Multi-armed Bandits Problem. In Proc. NeurIPS, pages 501-511, 2019. (p. 2.)
[16] Aurélien Garivier and Olivier Cappé. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proc. COLT, pages 359-376, 2011. 5.)
[17] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Proc. COLT, pages 998- 1027, 2016. (pp. 2, 3, 4, 5, 7, 10, 13, 25, and 26.)
[18] Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-comee strategies. In Proc. NeurlPS, pages 784-792, 2016. (p. 7.)
[19] Aditya Grover, Todor Markov, Peter Attia, Norman Jin, Nicolas Perkins, Bryan Cheong, Michael Chen, Zi Yang, Stephen Harris, William Chueh, et al. Best arm identification in multi-armed bandits with delayed feedback. In Proc. AISTATS, pages 833-842, 2018. (p. 1.)
[20] Peter Harremoës. Bounds on tail probabilities in exponential families. arXiv:1601.05179 2016. (p. 18.)
arXiv preprint
[21] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil' ucb: An optimal exploration algorithm for multi-armed bandits. In Proc. COLT, pages 423-439, 2014. (pp. 8, and 9.)
[22] Tianyuan Jin, Shi Jieming, Xiaokui Xiao, and Enhong Chen. Efficient Pure Exploration in Adaptive Round model. In Proc. NeurIPS, pages 6605-6614, 2019, (pp. 2, 3, 5, 9, and 25.)
[23] Tianyuan Jin, Keke Huang. Jing Tang. and Xiaokui Xiao. Optimal streaming algorithms for multi-armed bandits. In International Conference on Machine Learning, pages 5045-5054. PMIR, 2021. (pp. 10, 25, and 26.)
[24] Tianyuan Jin, Jing Tang, Pan Xu, Keke Huang, Xiaokui Xiao, and Quanquan Gu. Almost optimal anytime algorithm for batched multi-armed bandits. In International Conference on Machine Learning, pages 5065-5073. PMLR, 2021. (pp. 2, 3, and 15.)
11

---

[25] Tianyuan Jin, Pan Xu, Xiaokui Xiao, and Quanquan Gu. Double explore- thooor--the-committ Asymp- totic optimality and beyond. In Conference on Learning Theory, pages 2584-2633, PMLR, 2021. (pp. 2 and 7.)
[26] Marc Jourdan and Rémy Degenne. Non-Asymptotic Analysis of a UCB-based Top Two Algorithm. arXiv preprint arXiv:2210.05441,, 2022. (pp. 3 and 4.)
[27] Mare Jourdan, Rémy Degenne, Dorian Baudry, Rianne de Heide, and Emilie Kaufmann. Top two algorithms revisited. arXiv preprint arXiv:2206.0000 05979, 2022. (p. 4.)
[28] Mare Jourdan, Rémy Degenne, and Emilie Kaufmann. An purepsilon-Best-Aee Identification Algorithm for Fixed-Confidence and Beyond. Advances in Neural Information Processing Systems, 36:16578- 2023. (p. 4.)
[29] Shivaram Kalyanakrishnan and Peter Stone. Efficient selection of multiple bandit arms: theory and practice. In Proc. ICMI. pages 511-518, 2010. (p. 4.)
[30] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. PAC Subset Selection in Stochastic Multi-armet Bandits. In Proc. ICML, pages 655-662 2012. (p. 4.)
[31] Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In Proc. ICML, pages 1238-12466 1246, 2013. (pp. 2, 3, 4, and 9.)
[32] Nikolai Karpov, Qin Zhang, and Yuan Zhou. Collaborative top distribution identifications with limited interaction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 160-171. IEEE, 2020. (pp. 5, 25, and 26.)
[33] Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, et al. An empirical process approach the union bound: Practical algorithms for combinatorial and linear bandits. Advances in Neural Information Processing Systems, 33: 10371- 2020. (p. 4.)
[34] Emilic Kaufmann and Wouter M Koolen. Mixture martingales revisited with applicationn to sequential tests and confidence intervals. The Journal of Machine Learning Research, 22(1):
11140-11183 2021. (p. 7.)
[35] Junpei Komiyama, Taira Tsuchiya, and Junya Honda. Minimax optimal algorithms for fixed- budget best arm identification. Advances in Neural Information Processing Systems, 35: 10393-10404, 2022. 5.)
[36] Pierre Ménard and Aurélien Garivier. A minimax and asymptotically optimal algorithm for stochastic bandits. In Proc. ALT, pages 223-237, 2017. (pp. 5, 15, and 18.)
[37] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, 44(2).660-681, 2016. (p. 2.)
[38] Xuanfei Ren, Tianyuan Jin, and Pan Xu. Optimal Batched Linear Bandits. In Forty-first International Conference on Machine Learning, volume 235, pages 42391 42311-42416. PMLR, 2024.
(p. 2.)
[39] Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In 2019 IEEE 60th Annual Symposium on Foundations Computer Science (FOCS), pages 126-146. IEEE, 2019. (pp. 2, 3, and 5.)
[40] William Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 1933. (p. 1.)
[41] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018 (p. 20.)
[42] Po-An Wang, Ruo-Chun Tzeng, and Alexandre Proutiere. Fast pure exploration via frole. Advances Neural Information Processing Systems, 34:5810-5821, 2021. (pp. 3, 4, 5, and 7.)
[43] Yuan Zhou, Xi Chen, and Jian Li. Optimal PAC multiple arm identification with applications crowdsourcing, In Proc. ICML, pages 217-225, 2014. (p. 1.)
12

---

Notations.
Denote by ji the empirical mean of arm i after its s-th pull and by (t(t) the empirical mean of arm i time (i.e., after a total number of pulls are examined for all arms). We use A; Pi p for the gap between the optimal arm and the i-th amm Throughout the paper, we use the following asymptotic notation. Specifically we use f()) S (6) to denote that there exists some óg, such that for any d < do. [(0) S g()). Similarly, we use ((6) Z g(6) to denote that there exists some dp, such that for any 8 < 60. f()) g()).
A Computing w² (n) and (M)
In this section, we introduce two useful lemmas that help calculate (b(bb and (b) in Algorithm and Algorithm 2, which are also used in [17]. For case of presentation, we first define some useful notations. For every c [0, 1], we define
Le(H, p¹) == cd(H, op + (1 - c)μ') + (1 -c)ddd'' 1 op + (1 c)p²)
For any arm E [n] \ {1}, we define
gi(x) = (1 x) 1+ (m),
Lemma A.1 (Garivier and Kaufmann 17, Lemma 3). For every E Pa.
inf AEA
Σ wid(kis Ai) wi)d
min (wi + wi)l wi
(4).
Besides,
(')))= sup min (wi wi)) w1 w.P, lffl
(11, pe);
(A.1)
and
w (1)) arg max min (wi + wi)l wi (ui,us). ##1
(A.2)
WEP,
witmy
Lemma A.2 (Garivier and Kaufmann 17, Theorem 5), For i E [n], let
2x(1") o (u) Σie(n) xi(y")'
where y² is the unique solution of the equation
Fy(y) = 1, and where
d [1 1=2,(0)
Fa: +
1=2 d (4ss 1+2((9)
(1+)()))
in continuous, increasing function on [0, ((,d(())22)) such that Fu(2) + oo when y - d(u1,
B Proof of Theorems in Section
B.1 Proof of Theorem 3.2
Proof of Theorem 3.2. The proof of Theorem 3.2 requires the following two Lemmas, which guaran- tees the error returned by Line 22 and Line 26 of Algorithm respectively.
Lemma B.1. [17, Proposition 12] Let μ be the exponential bandit model. Let 8 (0. For sufficiently small > 0, the Chernoff's stopping rule Line 21 of Algorithm with the threshold
B(t, log 2 12g())))
ensures that P (i 1) 8/22.
Recall ig is the empirical mean of arm v after its s-th pull. Let E = (Vs > La and [m] j [14 - 6, Pi + +]]. The following lemma shows that PP(E)) < 8/2, where E denotes the complement event of E.
13

---

Lemma B.2. For sufficiently small 5 > 0%, we have
P(E)) - 6/2. If E happens, we have that at Line 26 of Algorithm 1, (t) 2 A1 - < #4 + fa((t) for all i > 1, which means 8 (t) Combining Lemma B.1 and Lemma B.2, Theorem 3.1 follows immediately.
B.2 Proof of Theorem 3.1
Proof of Theorem 3.1. Recall in Algorithm 1, b = (z) and 6" = (t(t) + e for all e
[n] \ fir (t)), where = Tq. Let &n be the intersection of the following four events:
E) 022 {09 [e 3c/2, -c/2],,
(B.la)
E 7221 {for all i [n] \ {1), E jus + t/2,, 3
(B.
E - 0220(A (T,) μn -
(B.lc)
E = (2rr(for all i [m] (1), Pa(TT) S 14 + e/2}.
(B.ld)
Here (B.la) and (B.1b) ensure that the estimation of w" (b*) and T (b9) is close to w" (p) and T* (1), and (B.lc) and (B.1d) ensure that arm 1 has the largest average reward at time Tg.
Lemma B.3, For sufficiently small O, we have
P((E)) (log 8-1)2
Lemma B.4. If Eg holds, then for sufficiently small 8 0, we have
1. Ti = aw; ( (w) (ogg_/0)) ologg(16)))
2. ww((b²) u (b)) S 1//l for all i [n];
3. mingglo/M ZT( 2 8/2,
From Lemma B.4, if is sufficiently small and Eo holds, then Algorithm will return at Line 22. Besides, we note that the total number of pulls of any arm is more than L3 (log(8 ((og( times. Therefore,
B[Ns] S nL, + 1{8)} (aT (H) 6
5-1 log(1/)))) + 1[8) (L2 + nLs)
< [( aT (1) log 8-1 + o(n log(10))) + 1L8
$ 11E)] aT (4) log 8-1 +n
< <T (4)
(B.2)
We further have
E[Ng]
lim 6-1
log 8 S aT (H).
This completes the proof.
B.3 Proof of Theorem 3.3
Proof of Theurem 3.3. Stage I costs one batch. For Stage II, note that (P()) S Tog(8-ryr and Eo occurs, then |w (b?) w (b') 1/v7 for all [n] (from the second statement of Lemma B.4), which means Stage II costs batches. Moreover, from Lemma B.4, 5 sufficiently small and Eo holds, then Algorithm will return at Line 22. Otherwise, the algorithm goes to Stage IV and costs one batch. Therefore, for sufficiently small ó, the expected number of batches
< F(E))) log(1/6) ()- + + P(EE) = 3 + o(1).
Finally, if Eo is true, the algorithm costs 3 batches. Therefore, with probability 1/ log(1/5²). Algorithm costs 3 batches.
11
'If event E' occur for sufficiently small 6 >> 0, it signifies that there exists 6, E (0, 1) such that for all 8 < do. event E consistently holds.
14

---

B.4 Proof of Supporting Lemmas
The proof of Lemma B.3 requires the following useful inequalities.
Lemma B.5 (Maximal Inequality). Let N and M be positive integers, let 7 0, and f be the empirical mean of n random variables i.i.d. according to the arm's distribution with mean μ. Then, for x < p.
P(EN In n < M. S 2) Se M(=-))
(B.3)
and for every x 2 14,
P(EN En M, Pm 2 x) S M(x -Na=W
(B.4)
where Vo is the maximum variance of arm's 's distribution with mean μ E [z, pl] and Vi is the maximum variance of arm's 's distribution with mean j E [p,
Note that Lemma B.5 is an improved version of Lemma of [36], where we use a much smaller variance upper bound to tighten the inequalities for the case x S μ and the case 2 respectively.
Lemma B.6. [24, Proposition 1] For and n¹ -E.
d(u, 2 d(u, p² e), and d(p,)() S d(p - -,,
(B.5)
Now, we are ready to prove Lemma B.3.
Proof of Lemma B.3. Let V be the maximum variance of reward distribution with mean μ E [Mt M1]. From Lemma B.5, we have that for 2 L1,
P(3s 2 L1 : ff & [pn - 11 + c/2))
$ P(3s 2 In :p 2 nn + P(3s 2 In : S PM c/2)
$ 2e 22---110 (2V)
1
(B.6)
n(log 8 122
where the second inequality is from Lemma B.5, and the last inequality due to that for sufficiently
small 8 > 0, L1 = Vlog 8 2 8v/e2 log(n(log 8 1))). Similarly, for E [n]] {1}.
1
P(Es 2 L1 23 $
+ e/2)) 2 n n(log 8 1)2 - - e/2, e/2,
(B.7)
Define events:
A = sA) 2 Ln ( E [M - c/2, M1 + c/21}
and
A (for all E [n] \ {13, Vs 2 L1 0 E [m Mi + t/21]. Assume that both events A₁ and A₂ hold. Then, we have
if μ1 c/2 #4 c/2 A - p
where the last inequality we assumed c S min;31 1 A. This further implies 1 (TTT) for any q 2 0 and thus b4- = f e. Therefore, we have for any q 2
bf = iu (T 1) - & jIn 31/2,11 - <//2]:
2. Vi E [n] \ (1). by = A + [wu - c/22,
/2,,44 μu + c/2]:
3. (T(T 2 pM - E//2:
4. and Vie e [n] (1), (T 144 e/2.
15

---

which means Eo defined in (B.1) occurs. Therefore, we have P(En) 2 P(A, A2)
=P( (V8 2 Li A E [M1 - +
{Vs 2 L1 / E 114-
- E/2, + +
=P (3s> 11 A9 1/2,
n (E)
{ ر1 0 $ [p - +
+ +/21}
μ1 2 2:14 + 2
P1 2 L j &
Σ
3s I i $
E
14 + 6
2
2
2 1 (log 8 1-2
where the last inequality is due to (B.6) and (B.7).
Proof of Lemma B.4. Assume Eo is true. Recall that A2 m #1 - -4s. For sufficiently small d 0 such that 42/8, we have by E [e] A2/4,11 ui] and 6ī lus + A2/4]. Let
[(b) = ( [m - 22/4, /4, mn] and for any i E [m]] \ (1), E [p + A2/4]] Therefore
(w (b*) v
max an (b' (0'''"'00 (b*) < co. b'EC(b)
Since maxy aw; (b)) oo is independent of 8, we have aw (B")("
max aw; (b") S log log 8-1 8-1// L2, CcC())
which implies T = min (b")T* 0og5-1, , = ow,"" (bo) T (b") log 5-1 Besides, as w" (b9) and (b4) are continuous on 69 we have that ba + pe, w (ba) + w (()) and (b9) T" (H)). Note that 66 Mi| I 2e and e approaches 0 as 5 approaches O. Recall r is the stopping time of Stage II and T, is the number of pulls of arm time т. Therefore, for sufficiently small 6,
T
max TP aw? (n)TT* (#) log 5 o(log(1/8)). p-E
Moreover, for sufficient smaller ó and Vi [n]], u (b²) (n) = o(1) and thus
| (bb) - i (b²) < 1/V7.
which means the condition in Line 15 is satisfied and the Algorithm goes to Stage III.
Assume Tig'- We have
ZT:(T) (T) d(an (T), (()))) + Ni(7)
d(((((),
Ni(TT) d(Pi(T). ((;(T))) + N.(TT)) d(Ai(T), ((i(T))
[w](bb) (T) (ii(T)) w/ (d)) (r.())
2 aolooo
(B.8)
T (by')
(b"''
where the last inequality is due to T, 2 Tod = aw:(bb (B")TT (b")) log(1/5). In what follows, we will show
wi (bb') ((((7) T-bbr--1
wi (bb)) d((a(()) 2
T-
The following minimization problem is convex optimization problem
min try SAa
(be') d(fa()) Arw) w/ (be') d((p((T), diw),
16

---

which is solved when we have \1w Aiw (1s(T), The proof of this lemma is based on the assumption that Eo occurs. Note that Eu occurs, then by (Tg- c pn c/2 S (r) and
by (T) + (i(T) for all i [m] {1}. Therefore, (1(T) 2 of 2 o9 2 (T(T). Let wf (b² bi + wi(br) + w (ba') by.
w wb Nw (b0) (6V)) (0g by) " (br') + W (bo)
Then, (o) bg) is the solution to minimizing wi((d) d(b) 2) + wt (b2)) d(bb 2) for (6% ).).
Case 1: if (TT(T) E (6% Ai(()),, then
wi wi("") (()i((), (T)(T)) + ui (ba)) d(A:(()) (1((T))
2 wi (bb") d(01 (T), in (T)) + oi (b²)) d((i(T)) 69))
z ui (b d(b) by + wf((( (b d(bb b9t)
2 (b d(b) AW (Brr 6g )) + w (b") d(b) (oo (oor (6) ))
(B.9)
where the first and second inequalities are due to (B.5) and the last inequality is due to the fact that wi (bb") -dbb 2²) + w (b") d(bp 2²) achieves minimum
(or) bbg
Case 2: if (T) E (B9) b9'), we have
w wi(')) d(pi (.(()) + w/ (b ((i;(T), 2 wi(''") d(D9 (T)((T) + 1 (bd) ) d(Ds fir((T))
2 wi((b") d(b) Aw- (6] 69 + w (b d(bs (we (bf (26)),
(B.
where the first inequality due to (B.5) and the last inequality due to the fact that for x E (b9 699) wba') d(by x)) + wt (b4) d(bp' x) achieves its minimum at >m (bi... .............................. ..' 69
Case 3: if (mi(T) E (i:(T), by similar to (B.9) and (B.10), we have wi((b') d(p)(T) (T), u (b") d(p:(T), (1:(T)
2 u (b") d(b)' Aw-roor (66 69 + w (b") d(b) (orr (o(..)))))
(B.11)
Combine all three cases, we obtain
wi (ba))
+ (b
2 (bY) d(bi, A 89 )) + w (b²) d(bs" - (09',,009''') ,89)))
(B.12)
Note that (T) = Xw (br)) (f (T), we have
wi(b)) ). d(
w (b('r)
(ba''-
T-bb')
w wb('') d(D9 (w (09'.8')) 18'1)
us (bb) ). dd(b? -wo 10'')9")
(ba')
T (bx'')
(B.13)
where the first inequality due to (2.12) and the last inequality is due (A.1). Note that conditioned on event Ep. for sufficiently small 8 > O, we have 1 = (T). Therefore, for any i E [n] \ {1}.
Zz(T) ZI((T)
[ (w(( d(pi (I)()) + wi(b"") d(a (T),((T)) (bb'
log 8-1,
(b4'))
2 log 1-
17

---

where the first equality is from (3.3), the second equality is from (B.8), and the last inequality is from (B.13), Finally, for 2 1 log log 8 log d we obtain
(log 10
2 log 2(log(2/6)) (nI2 + = -B(T,8/2),
Zz(T) 2 log
8
which completes the proof.
B.5 Proof of Maximum Inequality
Proof of Lemma B.5. Recall that the result of Lemma 4 of Ménard and Garivier [36] is: for Pn S μ4,
P(N & n E M, d( u)) 2 7) S No.
(B.14)
By Lemma of Harremoës [20]. we have
" y - d(æ, 11) =
(x 12)
dy S
(B.15)
(w)
2Vo
where (vy the variance the distribution with mean y. As a simple consequence of (B.15) and (B.14), we have
PON < n M, 2x Me (2==
(B.16)
For the case when f. 2 μ. we can directly follow the idea of Lemma of Ménard and Garivier [36]. For the case jin. μr, aim to show
P(EN & n S M, d(p 14) 2 7) S NN7
(B.17)
We let (() be the log- log-moment generating function of vo. Recall that due We use the following properties of one exponential family.
dp (z) exp(x0 b(0)).
1. M(A) b(O A) b(0):
2. (L 10) b(0) b(0,) (00) 01);
3. [[(o]] = (0)..
Let [[va] μ.. Let 0 0 (01))) μl, and y d(z, 14), have
==dz,1) = (L ua) = A= - -M()-
Since d(z,p) is monotone increasing for ,4, obtain O. If event (EN S n S
M, d(pn, 11) 2 7 and jan 2 14, one have
An 2 p. Apn ( Az M(A) =, Ampn mM N7.
By Doob's maximal inequality for the exponential martingale exp(Amfan - (A)))).
P(3N < M, M(d(Aa, u) 7) S P(EN <n M, Anpa -nM(A) N7)
Se- Ny.
(B.18)
Combining above inequality and (B.15), we obtain for in 2 1b
P(EN < n S M, d(Ans p) 2 7) S (((=-))
(B.19)
This completes the proof.
C Proof of Theorems in Section 4
In this proof, we define "one round" as single iteration of the While Loop of Algorithm 2.
Proof of Theorem 4.2. Proof of Correctness. We first show that the best arm not eliminated by Line 11 for any round For any 1, let El be defined follows.
El = = S,, Vr < 1}.
(C.I)
18

---

Lemma C.I. Line 11 of Algorithm 2 satisfies
P r21
Σ
pi 2
p.
cr
2
6 8"
4
To streamline our presentation, we define ee = 7/30 = (6,)²' and 1i as the sth updates of parameters f,. Tt.. and pi. respectively, within the second For Loop. For any fixed j. we define (s) to be the following set of rounds, where E remains to be the same value s:
())s {r 1,2.....
round of Algorithm 2).
(C.2)
Then the condition of Line 21 could be represented as
5j The following lemma shows that with high probability, Algorithm 2 will return at Line 22. Lemma C.2. Line 21 of Algorithm 2 satisfies
3i Sj and Uy(s), 21
P
nn n 121 (Eti(()
max 1h" < <
{j
2
36
IES,
16
Note that Algorithm 2 will return arm I at Line 24 1: Arm is always maintained Sy, and Algorithm 2 never return Line 22.
According Lemma C.I, there is probability of at least 1 1 8/8 that Arm will never be eliminated at Line 11. Given that Arm is never eliminated at Line 11, Lemma C.2 suggests that there is probability of at least 35/16 that we will never loop back at Line Hence, with a probability of 5/2, Stage IV will identify the optimal arm. By incorporating the results of Lemma B.1, we find that with a probability exceeding 8/2 8/2, which is greater than 5, Algorithm will return the optimal arm.
Proof of Sample Complexity. Let N' be the sample complexity Stage IV. Let & = 8 The following lemma shows the sample complexity conditioned event E.
Lemma C.3. The expected sample complexity N' conditioned on event has the order
log (n/6log(A)
E[N' E]
A
Now, consider the expected sample complexity if the best arm is eliminated at round r. We prove the following lemma. Lemma C.4. The sum of expected sample complexity N' each loop has the order
log (n/8log(A) log(A, (A, ()7))) )
Σ E[N' 1(8", (ET+1)CH = 0 Σ
A
The number of pulls of all arms in the first three stages is more than max /log 5-1 L2). By combining the above results, Lemma C.3 and Lemma C,4 together, we can obtain the following total sample complexity
E N = (1ogg5 5-1) log log 5-1 1 + log (no (no-1log4)
log 4, 471)) (
A?
1>1
Since in the non-asymptotic setting, ö is finite. Then
E[N = O Σ log log A,
A?
Proof of Batch Complexity. Just as we discussed the proof of sample complexity, we first demonstrate the batch complexity conditioned the event of E.
19

---

Lemma C.5. Conditional on event &, Algorithm 2 conducts (log((1/A)) batches in expectation.
Let B' be the number batches we used Stage IV. We consider the expected batch complexity the best arm is eliminated at some round We prove the following lemma.
Lemma C.6. The sum of expected batch complexity B' at each loop has the order
Σ EIB' 1[ (E = ((1og(1/4 r
By combining Lemma C.5, Lemma C.6, the fact that the first three stages use (log(1/6)) batches, and is constant in non-asymptotic setting, the batch complexity of Algorithm 2 is ((lo(11/A5)
Proof of Theorem 4.3. Let En be the event defined in (B.1) in the proof of Theorem 3.1. From Lemma B.4, if 5 is sufficiently small and & holds, then Algorithm will return at Stage III. Note that the expected number of pulls in Stage IV is S (log 8 1² Hence, the expected number of pulls of arms is no more than 2(log 8 1)2 times. Therefore, for any e' > 0
E[No] S (b) log 8-1 + oolog((1/)) + 2n 5-2
S aT (1) 0 --
+ 2n.
(C.3)
Therefore,
[N
lim 8-20 log 8 S (p),
Moreover, there exists some universal constant C, such that the expected number of batches used in Stage IV is S C' log(1/A2)) 1{E5) & o(1), where the last inequality is due to Lemma B.3. Form Theorem 3.3, the batch complexity the first three Stage 3 + o(1). Therefore, the total expected batch complexity is 3 + o(1).
D Proof of Supporting Lemmas
The proof of the supporting lemmas requires the following concentration inequalities.
Lemma D.I. [41, Theorem 2.2.6] Let X,,..., Xx [0,1] be independent bounded random
variables with mean Then for any > 0
he
P( 2 + t) S exp
and
(D.1)
2
ke²
P( S t) s exp
(D.2)
2
where jt 1/k 1/ X
D.1 Proof of Lemma C.1 From Lemma D.1,
PP ( mil 6, < 2exp
(-
(_dd,e
2d,
6r.
64
Applying union bound, we have
U 15-m-12 m1
8,
r21iE|m]
(E(n)
40x² 72
1>1
(D.3)
20

---

The aforementioned inequality suggests that, with a probability of at least 1 6/8, the condition
10 p4 S fr holds true for any E [n] and 2 1. Then, for any r >
p z μM
2 p. 2 0 4
Therefore,
Σ
P
p 2
p.
+r
gr
2
8
8
r21
D.2 Proof of Lemma C.2
From Lemma D.1,
P |0/ - mil 2 9 53e = -6,)²²
Applying union bound, we have
P YUU 121521
|0 187--113 ml 1
2)
<ΣΣΣ (8,)2
2"
40 f²
121 8>1
8
Σ
8
(D.4)
16
Besides, from (D.3), we obtain
|0 - mil s (t)
8 {g] 21
(D.5)
8'
r21 iE(n]
Define events
& = 0 Oie(n) (1/ - mul S c,/8),
and
& 0221 0s21 Cies, (1/ pal <t//8}.
If Eg and E truly hold, we have that (1): for any j and arm E SJ.
Te Sp. 8
3e < 14
3ej 4
14 S r
8
where the second inequality is due Line 11 of Algorithm 2: (2): for any fixed j. and any r E Us). where (s) is defined in (C.2) and represents the set of all rounds in which parameter E updated for exactly times,
D < p.
< P1
5eg <
p
5j D.
S
Ej 2
2
Therefore, if E and & truly hold, the event // and r E (s). It's noteworthy that, according to (D.4), P(E:) 2 1 1-8/16, and from (D.5). P(Ea) 2 1 - 6/8. Therefore,
< consistently holds for all j. 8, i Sj.
TP
max iES;
<x 6j
//1 )
2 1
8 8
38
8 16
16
121
21

---

D.3 Proof of Lemma C.3
We first focus bounding the number of pulls of arm within the first For Loop. Define
A;
min r: ( <
2 S
From Lemma D.1 and the union bound, for r 2 r()),
(f12 10 vil
cr(()
cr(()
})
2d,
P
17 mil 2
- 4 exp
8
8
64
S 4(8,)
10r())-T
(D.6)
Let E the event 10; - us| S f/00/8 8 and 1 - -1 S ((1) truly hold at r-th round. Conditioned on E and E
S + cr 5 S A
cr S
3 2
S p Cr+ s
which arm i will be eliminated. Therefore, the total sample cost of arm in the first For Loop of Algorithm 2 is
Σ
32 log (2/6, + Σ
10" 10--r(i-1 32 log(2/6,) =0
log(1 (1/6(())
rSn
(>r(1)
=0 log (n/6 log( (A,)))
A
Consequently, we define to be the total sample complexity in the first For Loop Algorithm Then we have
E B O Σ log (n/ō (n/5log(AA7))
A
Now, we bound the sample complexity within the second For Loop. We let Lj be the total number of pulls of arms in S, \ (S1+1 within the second For Loop. We let
B₁
= min (0,1,2,-.1
(6,)²*
As per Line 16, n, represents the total count of arm re-pulls in the set S \ SJ+1. Consequently, we can establish the following bound for Ly.
L, S (B, -B00-
Σ 2 < B, -,
==0
where the first inequality is because 75(++1) = 735 and pull the arms in S for total
32
2
32 2
2
Σ
log
log
(B, BB-1) 2"
1ES,
155
times at Line 18 and the last inequality is because for nj >
B
6 H 6
2 B,2
(5,
(5,)2*/+
where the first inequality is due to the definition of ny. Therefore,
B, Σ4
SH.
J21
J>1
j>1
Now, we conclude that conditioned on event E, the total expected sample complexity
log (n/ōlog( (og((A)))) 4-)
A?
22

---

D.4 Proof of Lemma C.4 From Lemma D.1,
IP 10 Mil
Er
S exxp
(-
2dnez
- (d,)
2
4
Applying union bound, we have
IP U P.
mal
Cr
5 Σ (8,)²
2
JES,
SES,
S (8,)
(D.7)
The aforementioned inequality suggests that, with a probability of least 1 - (6,)3, the condition P 14: I 6//4 consistently holds true for any E S,. Then,
Er 2 pc 2
Er 2 1oe cr-
p1
2
Therefore.
P(E (E S (5,))
(D.8)
For any fixed j. recall the definition of (s) in (C.2). Assume E", E", (g"+1) truly hold and denote (s) r r } the rounds where f, We note that at r -th round, each arm within the first For Loop of Algorithm 2 is pulled at least
32 4
2
log
8,
times. Besides, each arm within the second For Loop is pulled least
32 2
log
times. Then, similar to (D.7), for -h round, we have
IP UiES,, { { Hil
Er ))
2
exp
2e
32 4
log
2
S
Σ
(62))at1
16
RES,
EE
+
Then, apply union bound over all rounds in Us(s), obtain
1)) < (52))'/2
P Ulelen Uies,y
mil
Moreover, if ET, (E happens, the best arm is eliminated at r-th round. Then for any rounds in U, (8), we have pulled arm for at least
32-2-
2
log
2
times the second For Loop. Recall that p." is the sth updates of parameter jo within the second For Loop. From Lemma D.1, we have that
P p
M1
Er < exp
2c
16
32-2"
log
22)) S (5%)2"/) /2.
5,
2
2//22/
Therefore, if 8T, (gr+1)e happens, with probability
1 Tre 1 (83)2--1
(D.9)
it holds that
UiEry UsES, 105- 107-- 1ps1 2 e {) and 6TS > /1 4'
4
23

---

and thus for all / E [s1]
1 2 pn
P
2
which means Algorithm returns at Line 22. Before we continue, we will first show that the number of pulls in the second For Loop is lower than the first For Loop. Assume the algorithm stops r'-th
round. Let sf m Br 2 > By}. The number of pulls for Sj \S SSt+1 at second For Loop most
Σ
(By B 2' -
B,2"
==1
$ Bj 2
B₁
2 713s 7305
< 2,, (
(6,)
I B,,
Therefore, the total number of pulls within the second For Loop is at most
(B (
B,
Σ 63 S Br,
121$=1
J>1
which means the number of for the second For Loop is lower than the first For Loop. Finally, we obtain
B[N' 1(8", (Er+1)9) ( Σ ((5.)3)2-
Br (6.)2-29
=,,,,,,
8, log (n/ō log( A 111)
A
In the first inequality, used the fact that if the algorithm stops in some rounds in Us(s), the total number pulls all arms is at most B./ 2*) + B,/ 2*), wheih comes from the first and second For Loop respectively. Moreover, the factor (a) 3a)2"))"=)) is because from (D.9), if gr, (Er+1ye holds, then Algorithm 2 returns some rounds in (s) (at Line 22) with probability at least 1 - (( The last equality is because from Lemma C.3, if E", (gr+1ya holds, then
log (n/6 (og(l,o(110) A, ))
E[B.] S O
A
Finally,
log (n/8 log( A,
Σ E|N 18 EE (8 0
Σ
A?
D.5 Proof of Lemma C.5
We note that each round within the While Loop costs one batch. Let
r(2) = min r: r < A₂ r
Let E" be the event
(222) n
1o mil s (r(2) 11
10 Hil s
24

---

Conditioned on E" and E,
(2
(x(2)
x S
M A,
S 01 cx(2) S.. (2
8
which means all sub-optimal arms have been eliminated and the algorithm returns. From Lemma D.1 and the union bound, for 2 r(2),
2d, 2d)
P((EE)) < 4n exp
4n(6,))-)()) S 10
(D.10)
64
Therefore, the total batch cost is
1
O(r2) = 0 (108 (
D2 )
Σ
10"-12
r2r
This completes the proof.
D.6 Proof of Lemma C.6
The proof of this lemma similar that Lemma C.4. have the following results.
1: From (D.8), we have
P(E (E < (5,))
2: From (D.9), we have Ex and (g++1)o truly hold, then with fixed l,, Algorithm 2 returns Line
22 with probability
(5
(D.11)
We first compute the size of (s).. From Algorithm 2, we know that the arm kept in the set S, will be pulled times larger compared to (r 1)-th round. Besides, we update &p to + 1, the number of pulls exceeds B,/ ([,)() 2n) (Line of Algorithm 2). It is easy to see after log, n rounds, the number of pulls of any arm exceeds B, and then after In (5.)=" rounds, the number of pulls of single arm exceeds (,, -2)). Therefore, the size of (s(s) is at most In (8,)0*.2 let U be the total number of rounds used. Then, obtain
1 + In n. We
ElU [8", (E" (E"11)9) S P(E", (Er+()))))))))))))))))))))))))) + E 0 Σ (18))))2-1
(Inn In (8,)2" 2
<PP(E", (E)+1)9) Sr. We have shown in Lemma C.5, Ers1 rP(E", (Er+1)))))) = O(log(1/22) Therefore, the total number rounds is
E 118 (grt1)9) = (log(1/A22),
which completes the proof.
E Experiments
In this section, we compare our algorithms Tri-BBAI and Opt-BBAI with Track-and-Stop [17]. Top-k ò-Elimination [22), ID-BAI [23] and CollabTopM [32] under bandit instances with Bernoulli rewards. All the experiments are repeated in 1000 trials. We perform all computations in Python on R9 5900HX for all our experiments. The implementation of this work can be found at http::/ggthubbcco//aaxubbbb/b//p
-atchhed-tttee--ee Batched-Best-Anee
Data generation. For all experiments in this section, we set the number of arms n 10, where each arm has Bernoulli reward distribution with mean μr for i e [10]. More specifically, the mean rewards are generated by the following two cases.
Uniform: The best arm has μ41 = 0.5, and the mean rewards of the rest of the arms follow uniform distribution over [0.2, 0.4], i.e., μ4 is uniformly generated from [0.2, 0.4] for i [n] \ (1).
Normal: The best arm has μl = 0.6, and the mean rewards of the rest the arms are first generated
from normal distribution (0.2, 0.2) and then projected the interval [0, 0.4).
25

---

Implementation details. The hyperparameters of all methods are chosen as follows.
Track-and-Stop [17] is fully sequential algorithm and thus the only parameter that needs to be set is the (()) function in the Chernoff's s stopping condition (similar to Stage III of Algorithm 1). Note that the theoretical value of (3()) in Track-and-Stop [17] is of the same order as presented in Theorem 3.1. However, they found that a smaller value works better in practice. Therefore, we follow their experiments to set 3 log ((log(t) 1)/8).
Top-k d-Elimination is a batched algorithm that eliminates the arms in batches. It has two parameters c and 8. our experiments, we fix 0.1.
ID-BAI| [23] is designed to identify the best arm among set of bandit arms with optimal instance- dependent sample complexity. We use the same algorithm setting of the original paper in our experiments.
Collab TopM [32] the algorithm to identify the Top-m arms within multi-agent setting. We set the as 1 and the agents K as 1.
For Tri-BBAI and Opt-BBAI, we set a 1.0013, and c 0.01. We use the same ((t) function for Chernoff's s stopping condition as in Track-and-SS -top.. Moreover, for the lengths of the batches, set L1, Le and L3 to be the value calculated by Theorem 3.1.
Results. We present a comprehensive comparison on the sample complexities and batch complexi- ties of our algorithms and baseline algorithms in Tables and 4. Notably, our algorithms Tri-BBAI and Opt-BBAI, also including Top-K K 8 Elimination and CollabTopM, require significantly fewer batches than Back-anddStop Furthermore, the sample complexity of Tri-BBAL and Opt-BBAI is significantly lower than that of Top-K 6 Elimination, ID-BAI and CollabTopM. Additionally, the sample complexity of Tri-BBAI and Opt-BBAI is comparable to Track and Stop when is large, and is at most 3.6 times greater than Track and Stop when ö is very small. Additionally, also provide the runtime comparison in Tables 3 and 4. Our algorithms have a significantly reduced runtime compared to Track-and-Stor achieving nearly x000 speedup.
"From Theorem 3.1, we can select to be any constant within the range (1, e/)). To optimize the convergence rate of E.Nss/(oog((/0)) (H)), slightly above specifically we choose 1.001.
26

---

Table 3: Experimental results in terms of sample complexity, batch complexity and runtime under the uniform mean rewards. The number of arms is n The experiments are averaged over 1000 repetitions.
Dataset
5
Algorithm
Sumple Complexity
Batch Complexity
Runtime (s)
Recall
Track-and-Stop
668.49 + 298.62
668.49 = 298.62
276.94 + 135.67
100%
Top-k d-Elimination
32472
2.01
0.04 = 0.01
100%
ID-BAI
120427
0.136 + 0.003
100%
1 10
CollabTopM
2T290.205 4806-435
3.001 0.031
0,032 1: 0.006
100%
Tri-BBAI
365.232 + 21.85
3,99 0.11
102 0.23
90.1%
Opt-BBAI
1220.30 +: 586.92
4.89 1.01
0.95 +: 0.22
100%
Track-and-Stop
971.281371001
977.23 371.61
100%
Top-k 8-El Eliiiination
52734
0.01
0.07 + 0.01
100%
10-2
ID-BAI
146948 0
0.167 + 0.
100%
CollahTopM
35449.181 5530.988
3.0
0.042 0.006
100%
Tri-BBAI
1114.41 98.68
3.96 0.19
105 0.19
99.3%
Opt-BBAI
1929.65 + 604.11
4.64
1.00
1.02 0.18
100%
Track-and-Stop
1468.15 448.88
1468. 15 = 418.88
624.82 219.14
100%
Top-k Eliiinattion
72996
2
0.10 0.01
100%
10-3
ID-BAI
173478 =
0.197 1: 0.006
100%
CollaTTopM
43457.489 1519.169
3.0
0.051 + 0.006
100%
Tri-BBI
2005.07 +: 175.13
3.88 0.33
1.09 0.13
100%
Opt-BBAI
2781.41 658.40
4.37 0.98
101 0.14
100%
Track-and-Ster
1769.72 + 467.36
1769.72 467.36
743.96 + 196.39
100%
Top-k d-Elimination
93258 =
2 2: 0.01
0
100%
Uniform
1 10
ID-BAI
199999
0.257 +: 0.005
100%
CollabTopM
51823.644 6379.805
3.0
0.061 0.007
100%
Tri-BBAI
2989.96 + 274.36
3.81 + 0.39
1.10
100%
Op-BBAI
3752.31 + 739. 60
4,20 +: 0.99
1.00 1.00:.012
100%
Track-and-Stop
2135.09 535.01
2135.09 535.01
821.99 = 137.83
100%
Top-k d-Elimination
113520 0
0.01
0.15
100%
ID-BAI
226528 +
0.257 + 0.005
100%
10-3
CollabTopM
60263.887 4:: 6367.285
3.0
0.071 4: 0.007
100%
Tri-BBAI
4066.34 381.41
3.74 0.44
100%
Opt-BBAI
4799.49 + 852.00
4.04 0.96
1.03 + 0.12
100%
Track-and-Stop
2517.93 G61.65
2517.93 = 561.65
1085.30 = 202.72
100%
Top-k Elimination
133782 0
2+ 0.01
0.18 0.01
100%
1 10-6
ID-BAI
253041 0
0.288 +: 0.006
100%
CollabTopM
67958.078 6750.415
3.0
0.081 + 0.008
100%
Tri-BBAI
5185.75 +: 484.85588
3.63 1:5:100 0.48
1.12 112::0.11
100%
Opt-BBAI
5871.33 951.60
1.07
100%
Track-and-Stop
2342.67 538.77
2012.67 598.77
1232.91 192.82
100%
Top-k 5- d-Elimination
154044 +
2++ 0.01
0.21 0.01
100%
10-7
ID-BAL
279579
0.317 1: 0.006
100%
CollaTTopM
76627.155 7000.211
3.0
0.008
100%
Tri-BAAT
6334.49 + 613.88
3.58
0.49
1.12 0.12
100%
Op--BBII
7055.16 + 1059.50
3.82 + 0.93
1.11 111::00 0.16
100%
Track-and and--and
3347.02 +: 535.16
3347.02 535.16
1464.84 359.57
100%
Top-k d-Elimination
174306 0
0.00
0.23 0.01
100%
10-8
ID-BAI
306108 0
0.347 + 0.006
100%
CollabTopM
84995.542 :1:5::2:::77 7270.987
3.0
0.100 1 0.009
100%
Tri-BBAI
7486.57 :: 764.36
3.49 0.50
1.13
Opt-BBAI
$136.01 +: 1094.05
3.64 0.85
1.10 0.12
100%
Track-and-Sin
3609.64 + 638.68
3609.64 + 638.68
1661.90 .96 + 266.15
100%
Top-k 6-Elimination
194568 =
2 2 0.01
0.26 1: 0.01
100%
1 1x 10-9
ID-BAI
332628
0.006
100%
CollahTopM
92703.663 7639.167
3.0
0.109 + 0.009
100%
Tri-BBAI
8759.03 + 844.59
3.41 4:11:00 0.49
1.12 0.10
100%
Opt-BBAI
9315.58 + 1264.28
3.56 0.83
1.11
100%
Track-and-Stop
1136.94 605.10
1136.94 665.10
1714.68 237.00
100%
Top-k d-Elimination
214830 0
0.01
0.28 0.01
100%
ID-BAI
359158 =
0.407 + 0.
100%
1 10
CollabTopM
100894.264 7704.855
3.0
4 0.009
Tri-BBAI
10083.60 6.60 +: 1005.54
3.30 0.45
1.26 0.18
100%
Opt-BAI
10548.19 1277.15
3.48 0.78
0.99 + 0.09
100%
27

---

Table 4: Experimental results in terms of sample complexity, batch complexity and runtime under the normal mean rewards. The number of arms is n 10. The experiments are averaged over 1000 repetitions.
Dataset
Algorithm
Sample Complexity 305.21 + 183.51
Batch Complexity
Runtime (s)
Recall
Track-and-Stop
305.21 + 183.51
154.42 + 64.49
100%
Top-k 6-Elimination
32472.0 1
2.00
0.04 1: 0.01
100%
1 10
ID-BAI
120427 0
0.145
100%
CollabTopM
11834.088 4: 2208.601
2,888 + 0.315
0.015 0.003
Tri-BBAI
334.49 32.80
3.89 0.32
98.3%
Opt-BBAT
793.23 + 358.
4.18 + 0.79
+.16
100%
Track-and-Stopy
490.95 + 206.28
490.95 + 206.28
+2.42++81.0
100%
Top-k Elimination
52734 1:
2 0.01
0.07 1.01
100%
1 10
ID-BAI
0.011
CollabTopM
16145.218 2235.120
2.933 0.250
0.021
100%
Tri-BBAI
893.05 +: 121.47
3.62 0.48
1.11 0.11
100%
Opt-BBAI
1236.33 381.17
3.74 T 0.71
1.11 0.13
100%
Track-and-Stog
699.18 198.64
699.18 + 198.64
264.66 + 116.82
100%
Top-k Elimination
72996
0.01
0.10 0.01
1 10
ID-BAI
173478 +
0.204
100%
CollabTopM
20414.549 2277.714
2.960 + 0.193
0.027 + 0.004
100%
Tri-BBAT
1532.76 201.18
3.37 0.48
1.3
100%
Opt-BBAI
1747,15 389.65
3.43 0.58
1.07 1071 0.10
100%
Track-and-Stop
S33.0S 231.48
833.S 1 231.0
315.10
Top-k &-Elimination
93258
2
0.12
100%
Normal
x 10-4
ID-BAI
199999 11
0.236 0.015
100%
CollabTopM
24673.111 1: 2584.898
2,962 + 0,191
0.032 0.005
100%
Tri-BAI
2141.11 = 282.37
3,20 0.40
1.13 - 0.08
100%
Opt-BBAI
2263.174 405.72
3.19 0.42
1.6 0.08
100%
Track-and-Stop
972.75 245.18
972.75 + 245.18
336.78
100%
Top-k & Ellimination
113520 +
2.00.01
0.15 0.01
100%
ID-BAI
226528 1:
0.269 0.044
100%
10
CollabTopM
29081,141 2323.11210 105
2,982 1 0,132
0.039 0.005
100%
Tri-BBAI
2838.36 1: 353.12
3.09 0.28
1.14 0.08
Opt-BBAI
2881.61
0.09
100%
Track-and-Stop
1122.53 308.73
1122.53 308.73
468.14 +: 138.87
100%
Top-k & E-Elminnaiion
133782 +
2 0.01
0.17 0,01
100%
1x 10
ID-BAI
253049 +
0.312 + 0.038
100%
CollabTopM
33386.52 2133.062
2.987 0.113
0.043 0.005
100%
Tri-BBAT
3516.52 467.48
0.18
1.14 0.08
100%
Opt-BBAI
3556.59 477.73
3.04 0.20
1.15 1. 0.15
100%
Track-and-Stop
1256.29 308,88
1256.20 308.88
54.76 74.00
100%
Top-k ElEiminntion
154044 +
2 0.00
0.20 - 0.02
100%
1x 10-7
ID-BAI
279579 +
0.336
CollabTopM
37499.802 2413.418
0.117
0.048
Tri-BBAI
4218.39 523.49
3.01 0.09
1.15 0.08
100%
Opt-BBAI
4220.78 623.11
3.02 + 0.13
1.16 1 0.13
100%
Track-and-Stop
1433.20 = 365.44
1438.20 355.41
366.44 101.01
100%
Top-k &- Elimination
174306 +
2.0.
0.23 + 0.01
100%
1 10
ID-BAI
306108
100%
CollabTopM
41924.698 1:: 2206.559
2.992 0.089
1055-10.000
100%
Tri-BBAI
4912.6- =1: 613.69
3.01 + 0.08
1.13
100%
Opt-BBAI
4940.68
650.75
3.00 0.06
+.12
100%
Track-and-Stop
1632.12 348.14
1632.12 348.14
590.42 56.25
100%
Top-k é-Elimination
194568
0.0001
0.26
1x 10
ID-BAI
332628 +
0,393
100%
Co
46244.241 + 1816.041
2.997 0.054
1039=00000
100%
Tri-BBAI
5637.36 743.53
3.00 0.05
1.14
100%
Opt-BBAI
5661.51 740.74
3.00 0.05
1.03 + 0.06
100%
Track-and-Stop
1747.29 318.88
1747.29 318.88
790.89 119.52
100%
Top-k 8-Elimination
214830 1
2
0.28 1.001
100%
1x 10-10
ID-BAI
359158 +
0.423
100%
CollabTopM
50556.41 1822.998
2.997 + 0.054
1.007
100%
Tri-BBAT
6356.78 787.53
3.00 0.03
1.30 0.16
100%
Opt-BBAI
6355.28 793.45
3.00
100%
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims presented in the abstract and introduction accurately represent the contributions and scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the discussion in Section 5.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
We provide the full set of assumptions and complete proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer:| Yes]
Justification: We include all information needed to reproduce the main experimental results in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
30

---

Answer:[ Yes]
Justification:
We have uploaded my source and will make the full code public this work
gets accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.. ec/
Policy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: haaliii/ggiee//ee
/ /nips...
sssisssnn wwwssssoiiiiyyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have included all the test details in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We report the error range in Tables 3 and 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
31

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We state all information on the computer resources in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https //tner/nneuipeee httpp///eeerrpp..ppppeiiiieeeeee wwtppppic/ttccccceceeeecccccaeee itw.:/eeeeiciiiiieieeeeeeneee
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification:
There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "UFvQrZe1j5", "reviewer": "Reviewer_YCPj", "summary": "The paper presents two novel algorithms for the batched best arm identification (BBAI) problem. The first is the Tri-BBAI algorithm, which employs three batches with the expectation of achieving the asymptotic optimal sample complexity. Based on Tri-BBAI, the authors conceived the Opt-BBAI algorithm, which achieves the near-optimal sample and batch complexity when δ is finite and it does not tend to 0. Opt-BBAI enjoys the same sample and batch complexity of Tri-BBAI for the asymptotic setting", "questions": "- Reward distributions are assumed to belong to a single one-parameter exponential family, a common choice in literature. Are there any limitations in choosing different reward distributions that could affect the effectiveness of the presented approach?\n- I have some doubts about the necessity of presenting both Tri-BBAI and Opt-BBAI in the paper. If Opt-BBAI achieves the same performances of Tri-BBAI in the asymptotic settings, why is it necessary to describe Tri-BBAI as well, considering that Opt-BBAI also addresses non-asymptotic settings? Could you explain and give some intuition about the need to\npresent Tri-BBAI?\n- The choice of exactly three batches in the Tri-BBAI algorithm is not entirely clear. Additionally, I would like to ask the authors to provide some intuition regarding the optimal batch complexity of 2 for both Tri-BBAI and Opt-BBAI (shown in Table 1) compared to the structure of Tri-BBAI algorithm which employs at most 3 batches. What is the intuition behind these results? Why was a 2-batch algorithm not considered from the beginning?\n- Experiments have been carried on crafted environments. Since authors argued about the benefits that their work would bring in real-world settings, I would expect to find an experiment on a such real-world scenario.", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Tri-BBAI is the first batched algorithm to achieve optimal sample complexity in an asymptotic setting\n- Opt-BBAI is the first batched algorithm to achieve near-optimal sample and batch complexity in non-asymptotic setting\n- Both algorithms are supported by valid theoretical analysis\n- Batched solutions may bring benefits to real-world scenarios that cannot rely on sequential methods, like Track-and-Stop algorithms", "weaknesses": "- The paper dedicates a significant portion to the introduction and related works, only beginning to describe methodologies and algorithms on page 5. I suggest reducing the introductory section to allow more space for discussing comparisons with existing algorithms (Table 2) and for elaborating on the experimental results.\n- The paragraph on the notation is partially useful, since it presents some notations that are never utilized in the main paper, but only in the appendix and may be employed to describe other unclear symbols.\n- I found some statements a bit misleading. For example, at line 251 the period ”In this section, we introduce Opt-BBAI, which can attain the optimal sample and batch complexity in both asymptotic and non-asymptotic settings adaptively [...]” is in contrast with lines 255-256 where, always regarding Opt-BBAI, is correctly said that ”we can achieve asymptotic optimality and near non-asymptotic optimality adaptively[...].\n- The claim at line 714 ”the sample complexity of Tri-BBAI and Opt-BBAI [...] is at most 2.6 times greater than Track and Stop when δ is very small” is not true, since in the second experiment for δ = 1 × 10−10 the ratio is evidently larger.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable time and effort in providing detailed feedback on our work. In the following, we present answers to your suggestions (S) and questions (Q) point-by-point. We hope our response will fully address all of the reviewer's points. \n\n---\nS1: Reduce the introductory section to allow more space for discussing comparisons with existing algorithms (Table 2) and for elaborating on the experimental results.\n\nA-S1: Thank you for this suggestion. In our revision, we will shorten the introduction and move the related work section to the last two sections before the acknowledgments. We will only include additional related work that was not previously introduced. The space saved will be used to discuss more comparisons with existing algorithms (in Table 2 of our manuscript) and present our experimental results. \n\n---\n\nS2: The paragraph on the notation is partially useful.\n\nA-S2:  We agree. The paragraph on the nation will be moved to the appendix.\n\n---\nS3: I found some statements a bit misleading. For example, at line 251 the period ”In this section, we introduce Opt-BBAI, which can attain the optimal sample and batch complexity in both asymptotic and non-asymptotic settings adaptively [...]” is in contrast with lines 255-256 where, always regarding Opt-BBAI, is correctly said that ”we can achieve asymptotic optimality and near non-asymptotic optimality adaptively.\n\nA-S3: Thank you for careful reading and pointing out this typo. We will revise the paper accordingly, i.e., claim that we adaptively attain the optimal sample and batch complexity in asymptotic settings and near-optimal sample and batch complexity in non-asymptotic settings.\n\n---\n\nS4: The claim at line 714 ”the sample complexity of Tri-BBAI and Opt-BBAI [...] is at most 2.6 times greater than Track and Stop when δ is very small” is not true, since in the second experiment for $\\delta = 1 × 10^{−10}$ the ratio is evidently larger.\n\nA-S4: Thanks for pointing out this. It should be 3.6.\n\n---\n\nQ1: Reward distributions are assumed to belong to a single one-parameter exponential family, a common choice in literature. Are there any limitations in choosing different reward distributions that could affect the effectiveness of the presented approach?\n\nA-Q1: For any reward distribution that belongs to an exponential family, the algorithm satisfying Eq (1.3) is asymptotically optimal. Therefore, different reward distributions do not affect the asymptotic behavior of my algorithm, as it is asymptotically optimal.\n\n---\nQ2: I have some doubts about the necessity of presenting both Tri-BBAI and Opt-BBAI in the paper. If Opt-BBAI achieves the same performances of Tri-BBAI in the asymptotic settings, why is it necessary to describe Tri-BBAI as well, considering that Opt-BBAI also addresses non-asymptotic settings? Could you explain and give some intuition about the need to present Tri-BBAI?\n\nA-Q2:  Our first algorithm introduces a method for designing an algorithm that achieves asymptotic optimality within constant batches.\nOur second algorithm presents a framework for integrating an asymptotically optimal algorithm with one that has near-optimal non-asymptotic sample complexity. This results in a new algorithm that is optimal or near-optimal in both asymptotic and non-asymptotic settings. Additionally, the second algorithm provides new techniques to ensure that the sample complexity does not depend on high probability events.\nThe primary focuses of the two algorithms are distinct. Combining them into a single algorithm would result in a lengthy and complex structure, potentially making it difficult for the reader to grasp the core ideas.\n\n---\n\nQ3: Intuition regarding the optimal batch complexity of 2 for both Tri-BBAI and Opt-BBAI (shown in Table 1) compared to the structure of Tri-BBAI algorithm which employs at most 3 batches. What is the intuition behind these results? \n\nA-Q3:  This is a typo. The batch complexity in Table 1 of my manuscript should be 3, and we will correct this accordingly. \n\nWe provide an intuitive explanation of my algorithm by detailing the purpose of each step, specifically in Lines 181-184, 187-189, 209-213, and 217-219.\n\nConsider a two-armed bandit problem with a gap $\\Delta$. Previous studies estimate $\\Delta$ using exponentially decreasing values, such as $1/2$, $1/2^2$, etc., requiring at least $\\log (1/\\Delta)$ batches. In Tri-BBAI, we initially explore each arm $\\sqrt{\\log (1/\\delta)}$ times. This initial exploration ensures that the true means of each arm is in a small range with a small failure probability of $p = 1/\\log^2(1/\\delta)$. We then use the estimated means to calculate the optimal sample size for each arm, as defined by asymptotic optimality (see Eq. 3.1). In the subsequent exploration phase, we sample each arm to the calculated optimal size and verify whether the best arm is identified with a probability of $1-\\delta$. \n\n\n---\nQ4: Real-world experiments.\n\nA-Q4: Obtaining real-world data presents significant challenges. In the literature on best arm identification that explores asymptotic optimality, experiments are typically conducted on synthetic data. We consider conducting real-world experiments to be an interesting direction for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "wuL6Ks0pWj", "reviewer": "Reviewer_3W3Z", "summary": "This paper considers the problem of BAI in the fixed confidence setting, in the context of finding the best arm in as few batches as possible. That is, instead of observing the reward of each arm pulled in turn, the learner makes multiple pulls in a single batch and only observes all rewards after the completion of said batch. The first result of the paper is to show that it is possible to achieve asymptotically optimal sample complexity, with only a constant number of batches. Specifically the authors propose the Tri-BBAI algorithm, which is shown to have asymptotically optimal sample complexity, PAC guarantees and requiring at most 3 batches in expectation, Theorems 3.1, 3.2, 3.3 respectively.\n\nThe authors then describe a second algorithm Opt-BBAI which has near optimal finite confidence guarantees as well as being asymptotically optimal.", "questions": "Do the authors have an idea as to why the Tri-BBAI has poor experimental performace against Track and Stop?", "limitations": "No concern.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Best arm identification under fixed confidence is well studied problem and running algorithms in batches has clear practical relevance. Thus, achieving both asymptotically optimal sample and constant batch complexity is a nice result.", "weaknesses": "When considering finite confidence guarantees the authors could also compare with the recent work \"An ε-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond\", Jourdan, Degenne, Kaufmann.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all of the reviewer's points. \n\n---\n\nQ1: When considering finite confidence guarantees the authors could also compare with the recent work \"An $\\epsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond\", Jourdan, Degenne, Kaufmann.\n\nA1: Thank you for highlighting this reference. The paper studies $\\epsilon$-best arm identification, proposing an asymptotically optimal algorithm and providing non-asymptotic sample complexity. [1] is not for the batched setting. When $\\epsilon = 0$, it aligns with our setting, and our finite sample complexity is better scaled. Specifically, [1] offers a non-asymptotic sample complexity scale of $n/\\Delta_{2}^2 \\log (1/\\Delta_2)$, whereas ours is more instance-sensitive, as our sample complexity is related to all gaps, not just $\\Delta_2$. Additionally, [1] considers a practical scenario where the algorithm can return a result at any time while still ensuring a good guarantee on the returned arm. We will compare our results with those in [1] in our revision.\n\n---\n**Reference**\n\n[1] Jourdan M, Degenne R, Kaufmann E. An $\\varepsilon $-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond[J]. Advances in Neural Information Processing Systems, 2023, 36: 16578-16649.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "SVSTJOhSZR", "reviewer": "Reviewer_vkzZ", "summary": "The paper \"Optimal Batched Best Arm Identification\" introduces Tri-BBAI and Opt-BBAI algorithms to identify the best arm in multi-armed bandit settings. Tri-BBAI achieves optimal sample complexity with only three batches on average as the confidence parameter $\\delta$ approaches zero. Opt-BBAI extends Tri-BBAI for finite-confidence settings, providing near-optimal sample and batch complexities for finite $\\delta$.", "questions": "N/A", "limitations": "N/A", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The paper is generally well-written. The theoretical analysis looks solid.", "weaknesses": "First, I don't think the regime when $\\delta$ approaches $0$ is interesting. In a typical scenario, we want to set the confidence relatively small, and it doesn't make a lot of sense to consider the algorithm's performance on extremely small values.\n\nThe paper doesn't fairly compare previous results. It mentions the work \"Collaborative top distribution identifications with limited interaction,\" and work \"Optimal streaming algorithms for multi-armed bandits\", but it doesn't include it in the table, which can lead to the impression that Opt-BBAI is the first algorithm to achieve $O(\\log \\frac{1}{\\Delta_{2}})$ batch complexity. However, many algorithms have already achieved similar results. Moreover, these algorithms are not included in experiments. Significant work should be done to implement a fair comparison and properly acknowledge other works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all your questions. \n\n---\nQ1: I don't think the regime when $\\delta$ approaches 0 is interesting. In a typical scenario, we want to set the confidence relatively small, and it doesn't make a lot of sense to consider the algorithm's performance on extremely small values.\n\nA1: We respectfully disagree with this argument for the following reasons:\n\n1. Many influential works adopt asymptotic optimality and have been published in top conferences such as ICML, NeurIPS, AISTATS, and COLT. We only mention a few here, including:\n\n[1] Garivier, Aurélien, and Emilie Kaufmann. \"Optimal best arm identification with fixed confidence.\" COLT 2016.\n   \n[2] Degenne, Rémy, et al. \"Gamification of pure exploration for linear bandits.\" ICML 2020.\n   \n[3] Jedra, Yassir, and Alexandre Proutiere. \"Optimal best-arm identification in linear bandits.\" NeurIPS 2020.\n   \n[4] Lattimore, Tor, and Csaba Szepesvari. \"The end of optimism? an asymptotic analysis of finite-armed linear bandits.\" AISTATS 2017.\n   \n[5] Degenne, Rémy, Wouter M. Koolen, and Pierre Ménard. \"Non-asymptotic pure exploration by solving games.\" NeurIPS 2019.\n   \n[6] Kirschner, Johannes, et al. \"Asymptotically optimal information-directed sampling.\" COLT 2021.\n\nIn recent years:\n   \n[7] Jourdan, Marc, and Rémy Degenne. \"Non-asymptotic analysis of a UCB-based top two algorithm.\" NeurIPS 2023.\n   \n[8] You, Wei, et al. \"Information-directed selection for top-two algorithms.\" COLT 2023.\n   \n[9] Jourdan, Marc, Rémy Degenne, and Emilie Kaufmann. \"An $\\epsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond.\" NeurIPS 2023.\n   \n[10] Jourdan, Marc, et al. \"Top two algorithms revisited.\" NeurIPS 2022.\n   \n[11] Deep, Vikas, Achal Bassamboo, and Sandeep Kumar Juneja. \"Asymptotically Optimal and Computationally Efficient Average Treatment Effect Estimation in A/B testing.\" ICML 2024.\n   \n[12] Wang, Po-An, Kaito Ariu, and Alexandre Proutiere. \"On Universally Optimal Algorithms for A/B Testing.\" ICML 2024.\n   \n[13] Ren, Xuanfei, Tianyuan Jin, and Pan Xu. \"Optimal Batched Linear Bandits.\" ICML 2024.\n\n2. Considering the asymptotic performance is also practical. An algorithm that is optimal as $\\delta$ approaches 0 consistently shows good empirical performance compared to algorithms that involve large constants in sample complexity. The experimental results in this paper, along with comparisons to the two extra works you suggested (see Table 1 in the general response and Table 2 in the attached PDF file), all demonstrate this fact.\n\n3. Our paper also contributes to the field of batched algorithms in the non-asymptotic setting. As highlighted in our contributions (Lines 94-100), the batch/sample complexity of earlier batch algorithms typically depends on the event of returning the best arm, which occurs with a probability of at least $1−\\delta$. However, this complexity could potentially become unbounded if a sub-optimal arm is returned instead. In contrast, the complexity of Opt-BBAI is not contingent on such an event. This is achieved through a new technique, i.e., Checking for Best Arm Elimination (see Lines 277-288).\n\n---\nQ2: The paper mentions the work [14] and [15], doesn't include it in the table, which can lead to the impression that Opt-BBAI is the first algorithm to achieve $O(\\log⁡ (1/\\Delta_2))$ batch complexity.\n\nA2: For [15],  their algorithm is actually not for the batched setting. All their algorithms call their Algorithm 1 as a component which is fully sequential. Consequently, their algorithm is not for the batch setting.\n\nFor [14], we reported their results in Lines 151 and 152. In the revision, we will include it in the table as well. Regarding your comment that “which can lead to the impression that Opt-BBAI is the first algorithm to achieve $O(\\log(1/\\Delta_2))$ batch complexity.”, we believe this is a misunderstanding of our work since  \n1. We explicitly mentioned in Lines 151 and 152 that the algorithm in [14] runs in $O(\\log (1/\\Delta_2))$ batches. We will add their batch complexity to our table in the revision.\n2. We did not claim to have developed the first algorithm to achieve $O(\\log(1/\\Delta_2))$ batch complexity. Instead, as clearly outlined in Lines 86-101, our primary contribution is that we propose the first algorithm that adaptively achieves optimal sample and batch complexity in an asymptotic setting, and near-optimal sample and batch complexity in a non-asymptotic setting. Additionally, we have introduced new techniques for addressing issues in previous work, where batch and sample complexity depended on high-probability events.\n\nWe will polish our writing further to incorporate the above discussions into our revision for a clearer presentation.\n\n---\nQ3: Experimental comparison with [14] and [15].\n\nA3: We added these two baselines. Due to space limitations, the experimental results are shown in the general response and the attached PDF file. The experimental results demonstrate that our sample complexity is significantly lower than that of the two baselines. This is because our algorithms are asymptotically optimal, whereas the sample complexity in the baselines involves large constants. We will incorporate these results in the final version.\n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them and if you don’t, would you kindly consider increasing your score?\n\n---\n**References**\n\n[14] Karpov, N., Zhang, Q. and Zhou, Y., 2020, November. Collaborative top distribution identifications with limited interaction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) (pp. 160-171). IEEE.\n\n[15] Jin, T., Huang, K., Tang, J. and Xiao, X., 2021, July. Optimal streaming algorithms for multi-armed bandits. In International Conference on Machine Learning (pp. 5045-5054). PMLR.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "vgBroRrH46", "reviewer": "Reviewer_Uhz8", "summary": "This paper studies the Batched Best Arm Identification (BBAI) problem in multi-armed bandits. The goal is to design an efficient algorithm that correctly finds the arm with the highest mean with probability $\\ge 1 - \\delta$, while minimizing: (1) the sample complexity, defined as the total number of arm pulls; (2) the \"batch complexity\", defined as the number of rounds in which the algorithm requests arm pulls. (Formally, the algorithm specifies the number of times it pulls each arm in the $r$-th round after observing all the outcomes in the previous $r-1$ rounds.)\n\nThe main results of this work are:\n- An algorithm (termed Tri-BBAI) that achieves an asymptotically (i.e., as $\\delta \\to 0^{+}$) optimal sample complexity in three batches in expectation.\n- Another algorithm (termed Opt-BBAI) that achieves: (1) near-optimal sample and batch complexities in the non-asymptotic setting; (2) the same guarantees as Tri-BBAI in the asymptotic setting.", "questions": "I don't have specific questions for the authors.", "limitations": "Limitations have been adequately addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This work studies a fairly natural problem. While the setup is not new, I liked that the authors explored certain perspectives that are different from prior work, namely: (1) asymptotic optimality of sample complexity; (2) focusing on the expected number of rounds, rather than treating it as a hard constraint.\n- The results are pretty strong: The algorithms achieve asymptotically optimal sample complexities within a (small) constant number of rounds (in expectation).\n- The presentation is clear in general. I found the main paper fairly easy to follow.", "weaknesses": "I think a major weakness of the work is that its main result is fairly intuitive, and arguably, its proof does not give new insights to the design of pure exploration algorithms. Here is why: For simplicity, suppose that we only have two arms with means $1/2+\\epsilon$ and $1/2-\\epsilon$, and the parameter $\\epsilon > 0$ is *unknown*.\n\nIn this case, the \"natural\" algorithm is to make geometrically decreasing guesses on $\\epsilon$: $\\epsilon_1, \\epsilon_2, \\ldots$, where each $\\epsilon_k = 2^{-k}$. At guess $\\epsilon_k$, we would pull each arm $(1/\\epsilon_k)^2$ times to get an $O(\\epsilon_k)$-approximation of the means. If the means are clearly separated, we get the answer; otherwise, we continue with smaller guesses. Clearly, this approach requires many rounds ($\\Omega(\\log(1/\\epsilon))$ rounds) of adaptivity.\n\nOn this instance, very roughly speaking, the authors' approach is to start with the guess, say, $\\epsilon_k = 1/\\log^{1/3}(1/\\delta)$. For each fixed $\\epsilon$, when $\\delta$ is small enough, the guess would be smaller than the actual $\\epsilon$, and the algorithm wins the game in $O(1)$ rounds. Also, this first round only takes $(1/\\epsilon_k)^2 = \\log^{2/3}(1/\\delta) \\ll \\log(1/\\delta)$ samples, so this will not affect the asymptotic behavior as $\\delta \\to 0^{+}$.\n\nIn general, the Tri-BBAI algorithm uses a round-robin strategy as an inefficient exploration round. The length of this round is chosen as a function of $\\delta$, so that the asymptotic behavior is not affected. Therefore, for each fixed instance, there exists some $\\delta_0 > 0$ such that whenever $\\delta < \\delta_0$, this inefficient exploration succeeds with a good probability, and may guide the algorithm to sample in an asymptotically optimal way in the rest. As a result, this asymptotic optimality might only hold for extremely small values of $\\delta$: From Line 492, the analysis needs $1/\\log\\log(1/\\delta) = \\epsilon \\le \\Delta_2$ to go through; in other words, $1/\\delta$ needs to be **doubly exponential** in $1/\\Delta_2$.\n\nAdmittedly, this weakness was addressed by the other algorithm Opt-BBAI, which achieves a sample complexity bound for finite $\\delta$ as well. However, it should be noted that the complexity contains a $\\sum_{i=2}^{n}(1/\\Delta_i)^2\\log n$ term, which could be higher than the optimal sample complexity by a $\\log n$ factor. In contrast, the state-of-the-art bounds for (non-batched) BAI (e.g., [Karnin-Koren-Somekh, ICML'13][Jamieson-Malloy-Nowak-Bubeck, COLT'14][Chen-Li, arXiv'15][Chen-Li-Qiao, COLT'17]) are tight up to a doubly-logarithmic factor.\n\nDespite the weakness mentioned above, I think this submission presents some solid work and a nice observation (Lines 72-73), namely, the need for many rounds of adaptivity only arises when $\\delta$ is small (or moderate), and goes away when we focus on the asymptotic regime. Therefore, I lean towards accepting the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging comments. The example you provided perfectly captures our main idea. We greatly appreciate this clear and concise explanation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We would like to express our gratitude to all the reviewers for your insightful comments and for recognizing the strengths of our work. We summarize these strengths as follows:
* Reviewer YCPj, Reviewer 3W3Z, and Reviewer UhZ8 all appreciated that our algorithm achieves the optimal sample and batch complexity in asymptotic settings and near-optimal sample and batch complexity in non-asymptotic settings. In particular, Reviewer 3W3Z states that these are nice results, and Reviewer UhZ8 states that the results are pretty strong.
* Reviewer YCPj and Reviewer 3W3Z valued the potential practical use of our algorithm. Reviewer YCPj mentions that batched solutions may benefit real-world scenarios that cannot rely on sequential methods, such as Track-and-Stop algorithms, and Reviewer 3W3Z notes that best arm identification under fixed confidence is a well-studied problem and running algorithms in batches has clear practical relevance.
* Reviewer UhZ8 appreciated our consideration of perspectives different from prior work, specifically: (1) asymptotic optimality of sample complexity, and (2) focusing on the expected number of rounds rather than treating it as a hard constraint.

We also received numerous valuable suggestions and have revised the paper accordingly. In particular, the following major changes have been made in our response and will be incorporated into our final version:
1.  As suggested by Reviewer vkzZ, we added two baselines. Due to space limitations, we presented the experimental results on the Normal dataset in the following Table 1 and the Uniform dataset in Table 2 of the attached PDF file. The results are consistent across both the Normal and Uniform datasets, and we will incorporate them in the final version.
2. As suggested by Reviewer YCPj, we shortened the introduction. The space saved will be used to discuss more comparisons with existing algorithms presented in Table 2 of our manuscript and present our main experimental results.



---
#### **Table 1:** Experimental results in terms of sample complexity, batch complexity and runtime under the normal mean rewards. The methods are ID-BAI, CollabTopM and our two algorithms. The number of arms is $n=10$. The experimental results are averaged over 1000 repetitions.
| Dataset | $\delta$ | Algorithm | Sample Complexity | Batch Complexity | Runtime (s) | Recall |
|---|---|---|---|---|---|---|
| **Normal** | **$1×10^{-1}$** | ID-BAI | 120427±0 | - | 0.145±0.012 | 100% |
| | | CollabTopM | 11834.089±2208.691 | 2.888±0.315 | 0.015±0.003 | 100% |
| | | Tri-BBAI | 334.49±32.80 | 3.89±0.32 | 1.08±0.16 | 98.3% |
| | | Opt-BBAI | 793.23±358.15 | 4.18±0.79 | 1.05±0.16 | 100% |
| | **$1×10^{-2}$** | ID-BAI | 146948±0 | - | 0.171±0.011 | 100% |
| | | CollabTopM | 16145.218±2255.120 | 2.933±0.250 | 0.021±0.004 | 100% |
| | | Tri-BBAI | 893.05±121.47 | 3.62±0.48 | 1.11±0.11 | 100% |
| | | Opt-BBAI | 1236.33±381.17 | 3.74±0.71 | 1.11±0.13 | 100% |
| | **$1×10^{-3}$**  | ID-BAI | 173478±0 | - | 0.204±0.013 | 100% |
| | | CollabTopM | 20414.549±2277.714 | 2.960±0.195 | 0.027±0.004 | 100% |
| | | Tri-BBAI | 1532.76±201.18 | 3.37±0.48 | 1.13±0.10 | 100% |
| | | Opt-BBAI | 1747.15±389.65 | 3.43±0.58 | 1.07±0.10 | 100% |
| | **$1×10^{-4}$** |  ID-BAI | 199999±0 | - | 0.236±0.015 | 100% |
| | | CollabTopM | 24673.111±2584.898 | 2.962±0.191 | 0.032±0.005 | 100% |
| | | Tri-BBAI | 2141.11±282.37 | 3.20±0.40 | 1.13±0.08 | 100% |
| | | Opt-BBAI | 2263.174±405.72 | 3.19±0.42 | 1.06±0.08 | 100% |
| | **$1×10^{-5}$** | ID-BAI | 226528±0 | - | 0.269±0.044 | 100% |
| | | CollabTopM | 29081.141±2323.105 | 2.982±0.132 | 0.039±0.005 | 100% |
| | | Tri-BBAI | 2838.36±353.12 | 3.09±0.28 | 1.14±0.08 | 100% |
| | | Opt-BBAI | 2881.61±430.05 | 3.08±0.27 | 1.09±0.09 | 100% |
| | **$1×10^{-6}$** | ID-BAI | 253049±0 | - | 0.312±0.038 | 100% |
| | | CollabTopM | 33386.52±2133.062 | 2.987±0.113 | 0.043±0.005 | 100% |
| | | Tri-BBAI | 3516.52±467.48 | 3.03±0.18 | 1.14±0.08 | 100% |
| | | Opt-BBAI | 3556.59±477.73 | 3.04±0.20 | 1.15±0.15 | 100% |
| | **$1×10^{-7}$** | ID-BAI | 279579±0 | - | 0.336±0.019 | 100% |
| | | CollabTopM | 37499.802±2413.418 | 2.986±0.117 | 0.048±0.005 | 100% |
| | | Tri-BBAI | 4218.39±523.49 | 3.01±0.09 | 1.15±0.08 | 100% |
| | | Opt-BBAI | 4220.78±523.11 | 3.02±0.13 | 1.16±0.13 | 100% |
| | **$1×10^{-8}$** | ID-BAI | 306108±0 | - | 0.362±0.018 | 100% |
| | | CollabTopM | 41924.698±2206.559 | 2.992±0.089 | 0.055±0.005 | 100% |
| | | Tri-BBAI | 4912.64±613.69 | 3.01±0.08 | 1.15±0.07 | 100% |
| | | Opt-BBAI | 4940.68±650.75 | 3.00±0.06 | 1.12±0.10 | 100% |
| | **$1×10^{-9}$** | ID-BAI | 332628±0 | - | 0.393±0.017 | 100% |
| | | CollabTopM | 46244.241±1816.041 | 2.997±0.054 | 0.059±0.005 | 100% |
| | | Tri-BBAI | 5637.36±743.53 | 3.00±0.05 | 1.14±0.08 | 100% |
| | | Opt-BBAI | 5661.51±740.74 | 3.00±0.05 | 1.03±0.06 | 100% |
| | **$1×10^{-10}$** | ID-BAI | 359158±0 | - | 0.423±0.015 | 100% |
| | | CollabTopM | 50556.41±1822.998 | 2.997±0.054 | 0.067±0.007 | 100% |
| | | Tri-BBAI | 6356.78±787.53 | 3.00±0.03 | 1.30±0.16 | 100% |
| | | Opt-BBAI | 6355.28±793.45 | 3.00±0.03 | 1.03±0.05 | 100% |

Meta-review: This paper discusses the best arm identification in the bandit problem under the batched setting. Two algorithms are proposed for this problem. The first one achieves the asymptotic optimality with respect to the error probability within almost three batches, and the second algorithm achieves the optimality in both the error probability and other parameters with the number of batches depending on the gap parameter. Results of experiments are given in the appendix to verify the performance of the algorithms.

The main strength of the paper is that the proposed algorithms achieve good sample complexities with a theoretically and empirically very small number of batches in various settings. On the other hand, there are several concerns on the writing/structure of the paper and comparison with other algorithms. The authors gave a plan of the revision to address these concerns and some additional results of the experiments are shown in the rebuttal. I judged that they are reasonable and I determined to recommend acceptance, but I expect that the authors very carefully revise the paper so that it falls within a minor revision while addressing all the above concerns.

Another criticism on the paper is that the asymptotics in $\delta$ is not very important. Though I partly agree that very small $\delta$ is practically not realistic, I think it is still significant that the optimality in $\delta$ is achievable jointly with the optimality in other parameters unless the criticism is accompanied with some support on the triviality of this combination. Still, I expect that the authors explain the significance on this point more clearly in the final version.

Following is my own comment to the paper:
- On Algorithm 1: in Line 15, $t$ and $\tau_q$ are opposite? I also got a similar concern on the unused notation as YCPj like $\tau_q$, and I hope that the authors very carefully check them.
- My concern is that, not only the sample complexity is 2-3 times worse than the Track-and-Stop algorithm even for $\delta=10^{-10}$, its slope with respect to $\log 1/\delta$ also seems 4-5 times worse even though $\alpha=1.001$ (very close to 1) is used in the experiments. This seems to mean that the asymptotic behavior in e.g. Theorem 3.1 does not appear even in this extremely small $\delta$. I think there should be some discussion on this point in relation with the concern by Uhz8. Related to this, why is $\alpha=1.001$ used in the experiments rather than $\alpha=1+1/\log \delta^{-1}$ suggested below Theorem 3.1? I don't see the necessity of the use of $\alpha$ very close to 1 if the asymptotic behavior cannot be observed.
Decision: Accept (poster)