Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids
Authors: Tianyuan Jin
Qin Zhang
Dongruo Zhou
Venue: ICLR 2025 Poster (2025)
Keywords: Bandits
Primary area: reinforcement learning

Abstract: We investigate the problem of batched best arm identification in multi-armed bandits, where we want to find the best arm from a set of $n$ arms while minimizing both the number of samples and batches. We introduce an algorithm that achieves near-optimal sample complexity and features an instance-sensitive batch complexity, which breaks the $\log(1/\Delta_2)$ barrier. The main contribution of our algorithm is a novel sample allocation scheme that effectively balances exploration and exploitation for batch sizes. Experimental results indicate that our approach is more batch-efficient across various setups. We also extend this framework to the problem of batched best arm identification in linear bandits and achieve similar improvements.

Published as a conference paper at ICLR 2025
BREAKING THE (og(1/A2) BARRIER: BETTER BATCHED BEST ARM IDENTIFICATION WITH ADAPTIVE GRIDS
Tianyuan Jin" Qin Zhang Dongruo Zhou?
l DDeaarmmett of Electrical and Computer Engineering, National University of Singapore DDpaarment of Computer Science, Indiana University Bloomington sianyuanenus nus. edu..eddu..... sg, qzhanges @iu. edu, dz130iu. edu
ABSTRACT
We investigate the problem of batched best arm identification in multi-armed bandits, where we aim to identify the best arm from a set of n arms while mini- mizing both the number of samples and batches. We introduce an algorithm that achieves near-optimal sample complexity and features an instance-sensitivy batch complexity, which breaks the log(1/A2) | barrier. The main contribution of our algorithm is a novel sample allocation scheme that effectively balances exploration and exploitation for batch sizes. Experimental results indicate that approach is more batch-efficient across various setups. We also extend this framework to the problem of batched best arm identification in linear bandits and achieve similar improvements.
INTRODUCTION
In online learning, it is common to process data in batches each with fixed policy, as frequently policy changes may incur significant additional costs. For example, in clinical trials, patients are typically treated the same at time, since every policy switch would trigger separate approval process [Thompson] 1933 Robbins| 1952). In crowd-soureing, it takes time for the crowd to answer questions, and thus a small number of rounds of interaction with the crowd is critical in time-sensitive applications (Kittur et al. 2008). Similar phenomena occur in compiler optimization (Ashouri et al.) 2019), hardware placements (Mirhoseini al., (017), database optimization (Krishnan et al. [2018). etc. Therefore, the design of eatch-efficient learning algorithms is of central importance in online learning. In this paper, study the following problem.
Best Arm Identification in Multi-Armed Bandits. set of arms, each associated with reward distribution NV4, 1), where μ4 is unknown mean. Pulling the i-th arm gives reward sampled from its reward distribution. In the problem of best arm identification in MAB (BAI-M), the goal is the identify the with the highest mean Ms max P4 with success probability (1 8) for a given å using the minimum number of pulls/samples We assume that there exists a unique best arm among the arms.
multi-armes bandits (MAB), we have
Batched Learning. In the batched model, learning progresses in rounds, where the set of arms to pull must be decided at the beginning of each round. Let & (= 1). f2..... tas denote the starting time steps of the M batches. For convenience, we define t T + 1, where T is the final time step. The i-th batch spans from time steps I; to (4++1 1), and we refer to (4+=1 4;) as the size of the i-th batch. There are two variations of this model: the first the fixed grid, where l1,..., IM are determined at the at the very beginning of the learning process, and the second is the adaptive grid, where tÜ can be chosen based on the rewards observed up to time (t, 1).
Alphabetic author order
A2 is the difference of means between the best arm and the second best arm. In this paper, consider the fixed-confidence variant of BAI-M. The other variant is referred to as fixed-budget, where given sample hudget T,, want to identify the best with the smallest error probability.

---

Published as a conference paper at ICLR 2025
In this paper, we focus on the adaptive grid setting and investigate the design of batched algorithms for BAI-M. We will also extend our results to best arm identification in linear bandits (BAI-L), with its formal definition deferred to Section 4
Sample and Batch Complexity. For a batched learning algorithm, we define its sample complexity as the total number of arm pulls required to identify the best arm, and its batch complexity as the total number of batches needed to accomplish this task.
It is well-known that for BAI-M, the sample complexity of the algorithm can be made instance- sensitive. That is, the sample complexity can be written as function of the input parameters, which wwwpa//innnnnnnnnnnneeneede
can be much better than the be an input instance for BAI-M. W.l.o.g., assume that Jai > μ/2 2 2 Pn- Let A, lu
bound for many inputs. Let I {1r) )mm
be the mean gap between the best arm and the i-th best arm. Several algorithms (Even-Dar al. Even- -ar et al. 2006 Audibert et al. [2010] Kalyanakrishnan et al. 2012 Karmin et al. 2013 Jamieson et al. 2014 Carpentier & Locatelli [ Chen et al.] (211)) are able of achieving sample
complexities on the order of O(Hz)), where hides some logarithmic factors, and
1
H1
(1.1)
A
2=
is called the instance sample complexity of the input 1. Among these algorithms, the successive elimination (SE) algorithm proposed in Even-Dar al. (2002) can be naturally adapted to the fixed
grid batched setting with a batch complexity of log (1/2).
Preserving the optimal sample complexity H,, the bound (1/(1/))) has been proven as nearly minimax-optimal for the batch complexity of BAI-M, even in the adaptive grid setting (Tao et al. 2019) However, this does not exclude the possibility of designing instance-sensitive batched algorithms that outperform the successive elimination algorithm for many inputs. In this paper, we try to address the following question:
In the adaptive grid setting, can we design bandit algorithms for BAI-M that achieve nearly optimal sample complexity while breaking the (og(1/A2)) barrier for batch complexity?
1.1 OUR CONTRIBUTIONS
In this paper, we answer the above question affirmatively. We propose new algorithms for batched best arm identification for both multi-armed bandits and linear bandits. Both algorithms achieve a smaller batch complexity for many inputs (and are never worse for all inputs) compared to the state-of-the-art algorithms (Even-Dar al., 2002: Fiez et al. 2019a).
Our contributions are summarized in the followings: First, we propose an instance-sensitiiv quantity R, to capture the batch complexity of an instance I in MAB.
Definition 1.1 (Instance- sensitive batch complexity of MAB). Set Lo = 1, Uo = 0, and C =15/2.
We recursively define for 1,2,... ... the quantities
L, = AL + 1
Σ
1 and U, = j A 2
C
(1.2)
A
jEU,-1
We stop when Ur = [mx] (1}. Let R₁ be the value of r when we stop
Intuitively speaking, L, represents the pull budget on each remaining arm in the r-th batch. Definition 1.1 introduces adaptive grids for batch sizes that are instance-dependent (as they depend the gaps
Tao et al. 2019) showed that to achieve Ō(Hi) time complexity in the (1))-agent collaborative learning model, ? log 2/ log log _t2 rounds of communication is necessary. This lower bound can be straightfor-
wardly translated to the batched lcarning model, proving an Ω (log a log log 1, batch lower bound under
sample complexity Ö(H,). "We note that setting C to be any positive constant will not change the asymptotic value of RG, For the sake of convenience in the analysis, choose C 15
2

---

Published as a conference paper at ICLR 2025
L
U1
Ex. 1
L2
U
Ex. 2
Lg
Loggn=1
U2
U3
Utogn-1
Ex. 3
L
L2
L3
L
SE Ing
1 1 2
2
Figure 1: Visualization of the three examples. The detailed description of three examples are listed
from Ex. to Ex. 3 Each suboptimal arm is represented by disk (with slight shifts to avoid overlapping), while the best arm is represented by square. I represents the average number of arm pulls by successive elimination, and I4 represents the average number of arm pulls by IS-SE. U, represents the set of eliminated arm in the i-th batch. In all three examples, successive elimination needs (llg n)) batches. However, for the first two examples, IS-SE only needs ((1) batches. For the third example, IS-SE shares the same batch complexity as successive elimination.
A5). This contrasts with successive elimination, which uses fixed grids L, = 4"; see Section for a detailed explanation. It is easy to see that log(1/Az) is upper bound of R,, We will shortly give examples showing that for some instances I, the gap between R, and log(1/ / A2) can be fairly large. We further provide the following upper bound for Ry:
R₁ S O(a + log H H))n)),
(1.3)
where a denotes the number of indices i such that Ug # U,-1 It is not difficult to see that both terms (1.3) are no larger than log(1/A2).
Second, we propose a new algorithm named Instance-Sensitive Successive Elimination (IS-SE), which achieves nearly optimal sample complexity ((Hr) and batch complexity O(R,), IS-SE utilizes the arm elimination framework similar successive climination, but updates its batch size according to Definition I.] We note that due to the inherent randomness in the arm pulls, it is not feasible to design an algorithm that strictly follows Definition 1.1 Consequently, we cannot compute I., values precisely, and this inaccuracy will propagate and accumulate with each successive batch. Therefore, we need new ideas to simulate the recursion process described Definition [.1
Third, we extend the definition of R2 to the best arm identification in linear bandits, and propose the Sensitie-e RAGE (IS-RAGE) algorithm as an counterpart of IS-SE. We show that IS- RARG finds the best arm with nearly optimal sample complexity well an improved batch complexity.
Examples. To show that our instance-dependent batch complexity R, for MAB always no worse than and often significantly outperform the state-of-the- thrt----ttttttt batch complexity log(1 1/22), we present a few examples; see Figure for their visualizations.
Ex. The best arm has mean 1;; (n 2) arms have mean [ 1). and 1 arm has mean
(1
1
vi
For this instance, R, = O(1), while log(1 A2) log n (loogn).
Ex. 2 The best arm has mean 1: (n log2 +1 arms have mean (1 )); arm has mean (2 1);
arm has mean ( : ..... and arm has mean vn For this instance, R2 0(1),
while log(1/A2) log vni Olognn).
3

---

Published as a conference paper at ICLR 2025
Ex. 3 Let z 3n-2 (n). The best arm with mean 2; arms with mean (2 2 4 arms with mean (1 :): ...; and arm with mean (3 + For this instance, R₁ Ö(log n)) which is comparable log(1/ 22) = log v (log
Notations and Conventions. We use lower case letters to denote scalars and vectors, and upper For a vector E R and
case letters denote matrices. We denote by [n:] the set (I.....,)) n2.. positive semi-definite matrix Σ E Rdxd, we denote by ||x|| the vector's Euclidean norm and define
||x||x = vx Σx. Unless otherwise stated, log z refers to the logarithm of x with base 2.
For convenience, in MAB, given subset of arms S [n], we define the partial instance complexity of A to be HI'), where I' = A U {u.}-
2 RELATED WORK
A rich body of research exists bandits, reinforcement learning, and online learning problems in the batched model. We review the most relevant ones to our work.
Batched best arm identification has been studied in both multi-armed bandits (Jun et al. 2016
Agarwal et al. 2017: Jin et al. 2019) and linear bandits (Fiez et al. 2019b Soare et al. 2014a). However, the batch complexities in those algorithms are not iustance-sensitive. Recently, Jin et al. (2023) studied settings where 6 approaches O, deriving optimal sample and batch complexities for this setting. They also studied the finite 5 scenario, noting that in this case, the batch complexity of the proposed algorithms is not instance-sensitive.
The other basic problem in bandits theory is regre! minimization. The early work UCB2 (Auer et al. 2002) for regret minimization in multi-armed bandits can be implemented in log T batches where 7 is the time horizon. Through a sequence of papers (Perchet et al. [016)] Gao al. 2019 Esfandiari et al.) 2019), almost optimal begret-batch tradeoffs have been established for both minimax and instance- dependent regret. Desachiincch et al. (2013) studied a setting where one can change the policy at any time. Jin et al. 2221)) considered the scenario in which the time horizon T is not known in advance, as well as batch algorithms in the asymptotic regret setting. Several papers (Kalkanli & Özgür 2021 Karbasi al. 202 Karpov & Zhang 2021) studied batched Thompson sampling for nullti-armed bandits. Regret minimization has also been studied for linear (contextual) bandits (Eslandiari et al.
2019 Han al. 2020 Ruan et al. 2021 Zhang al. 2021). among which Zhang al. (2021) obtained almost optimal regret-batch tradeoff for almost all settings.
We also note that there is a strong connection between the batched model and the collaborative learning (CL. model, which has gained attention in recent years. Notable works include: (Hillel et al., 2013] Tao al., 2019) on BAI w.r.t. sample complexity and round complexity tradeoffs; Karpov et al. (2020) on top-m best arm identifications: [Wang et (2019) on regret minimization w.r.t. sample complexity and communication cost tradeofi's; and Karpov & Zhang (2023) on BAI
w.r.t. sample complexity and communication cost tradeoffs; Karpov & Zhang (2024) on regret minimization w.r.t. sample complexity and round complexity tradeoffs. In particular, the batched model is essentially equivalent to the non-adaptive version of the CL model. (Tao et al. (0119) showed that in the non-adaptive CL model, there is an algorithm for fixed-confidence BAT that achieves almost optimal sample complexity using (og(1/22) rounds (for worst-case input), where the round complexity is almost tight, up to a log (og(1/Ag) factor. When the upper bound result is adapted to the batched model, we get an algorithm with log log(1/ (1/A2) batch complexity, which is not senancc-eensitive.
INSTANCE-DEPENDENT BATCHED ALGORITHM FOR MULTI-ARMED BANDITS
In this section, we present our batched algorithm IS-SE for MAB and analyze its complexities.
4

---

Published as a conference paper at ICLR 2025
Algorithm 1 Instance-Sensitive Successive Elimination (IS-SE)
Require: a set of arms X, confidence parameter Peonts sample complexity parameter Samplee and grid parameter Bgria.
1: Let S < [n]. r f- L1 t- .grid 81 f-
36 52
2: while [s, > do
3: for each arm i E do
4: pull arm for L, log(r2n/5)) times; let P. be the empirical mean of arm i;
5: end for
6: let p < max,es, fi,, and let e + D7 Dz
7: delete the arm set O, Sr such that for each i in S, for which of > Beont/ VTr.
8: set Sp+1 +- S, O,, and set
Prample ΣΣ E())
L f- Benaarr
|/,41| s=1jE0.
9: r+r++;;
10: end while
Ensure: the arm in S,
3.1 THE ALGORITIM
Our algorithm is based on successive elimination (SE) with a refined scheme to update the batch sizes. We include the details of IS-SE in Algorithm [
We start by describing the SE algorithm and then introduce our algorithm, emphasizing the key differences. The SE algorithm can be seen as special realization of Algorithm with Ssamll 0. At r-th batch, we denote S, as the set of arms that have not been eliminated yet. In each batch, SE follows round-robin approach, pulling each arm in the S, for roughly L, times (up logarithmic factor). After the arm pulls, SE estimates the reward mean for each arm and eliminates those whose estimated mean is least / below the empirical best arm, where Scont is parameter controlling the confidence level for eliminating suboptimal arms. SE then sets the number of pulls for the next batch using a simple multiplication rule: Lr+1 == Seria Ly, where Seria > is parameter that controls the batch-sample complexity tradeoff.
Following the analysis in Daa et al. (2002), we can show that SE finds the best arm with high probability using 8gnia (())) pulls and Olog (1/ 22) batches. By selecting Sgrid as a constant, e.g., 2gria- = 4, we recover the result in Even-Dar et al. (2002). Our main observation that such batch update rule may be too conservative. We can incorporate additional term into the batch update scheme that decreases the batch complexity for many input instances without increasing the overall sample complexity.
Our approach. IS-SE (Algorithm D at Line we introduce the r-th batch an additional budget E. Ejeo, (e7)- which represents the estimated instance complexity of the set of eliminated arms in the first r batches (i.e., arms [n]] \ S,+1);
then uniformly distribute this additional budget to the set of remaining arms S,+1 scaled by the parameter Ssample. Intuitively, we can think that in order to eliminate arms in [r]] \ 5,41, one has to spend at least Ex Σjeo, (e)) Therefore, would not be big waste to use this amount of budget for the next batch.
(sg)=² pulls.
3.2 THE ANALYSIS
The following theorem suggests that Algorithm I able find the best arm and its sample complexity only suffers an additional log n min (log n, log(1 /2) factor compared with the optimal sample complexity, Moreover, its batch complexity outperforms 1og(1/A2).
Theorem 3.1. Select Beong 5.2,, B Promple 25/9 and Berid 4. With probability -, Algorithm
1 satisfies the following conditions:
1. (Correctness) Algorithm 7 returns the best
5

---

Published as a conference paper at ICLR 2025
2. (Batch complexity) Define } and } in (1.2) (Definition 1.1.
Let R2 to be the minimal r E N satisfying [Uy| = n - 1. Then the batch complexity of Algorithm [ is bounded by Ri- Furthermore, suppose that 0 = To S
Ta R2 satisfying v1 S i a, Ur. # Ueeti-
Then R₁ S a + 151 (450H, /n) = O
150
3. (Sample complexity) Algorithm Thas sample complexity of
of (Iog(n/0) + log log A,2 log min 4 H11)
We provide proof sketch here and leave the full proof to Appendix B
Proof Sketch. For sample complexity, we start by showing that with high probability, the additional term Ex=1 Ejeo, (e))-² at Line aapprxxmmatss the partial instance complexity over the eliminated arms, that is, Σi=1E DjeO A, up to some constant. We then show that the additional sample budget Vmm1 Ejoo, (c)) included at each update of L,+1 is not overly costly. Specifically, prove that the sum of these terms only contributes an extra log min (n, A, Hy to the overall sample complexity.
For batch complexity, we align the number of batches that IS-SE uses with the batches defined in Definition I.] A major challenge is to deal with the randomness introduced by the sampling steps in IS-SE. We use induction to bound L, by L, and 0; by Ur.
For the inequality R₁ S a + log 1s (450H,/m) /n), we show that in each batch, we either eliminate more arms (i.e.. U, & Ur+1), or the estimated instance complexity Eie(n] (ef)=² doubles. These proof techniques may be of independent interest.
We make some remarks regarding Theorem 3.1
Remark 3.2. IS-SE finds the best arm with ((H)) sample complexity and most + log log(H, H1) butch complexity. Note that < log(1/ A2) due to the fact that L >> 4L, and H1/n S 1/42. Therefore, the batch complexity is always no more than log(1/A2).
Remark 3.3. Although IS-SE achieves both instance-sensine complexity R1, it does not need either H₃ R₁ as its input.
sample complexity Ö(Hr) and batch
Remark 3.4. One might argue that IS-SE is not necessarily superior to SE because its sample complexity exceeds H1 by some logarithmic factors, and similar improvements in batch com- plexity might be achieved by adjusting the Berid parameter in SE. However, for any choice of Byni poly log(n/ (8A2)), the batch complexity of SE can only be bounded by O(log, (1/A2)) (llog(1/A2) log (6/(2))))) which for many input instances, such as much worse than Rj.
Ex. and Ex. 2
is still
4 INSTANCE- BATCH COMPLEXITY FOR LINEAR BANDITS
In this section, we extend our instance-dependent batched MAB algorithm to the linear bandits setting. In best arm identification in linear bandits (BAI-L), we again have a set of arms, but now each arm is associated with a d-dimensional attribute vector. Let 2; E Ed denote the context associated with the i-th arm, and we use X to denote the collection of all contexts. We assume || [l2 S 1 for all arms. Given an error probability 8, our goal is to identify an arm X. = arg max x 8 with probability (1 - 8) using the smallest number of arm pulls, where 8 E IRd is an unknown vector representing the hidden linear model, and each pull of an arm returns a value x 0" + e, where ~ N 1).
We introduce few more notations. Let (SS) == fi x' Vx, x' E S, o x'} and let y² == {v.-22 - 2 corresponding value.
Vr E S S) {r.)). We will use the following optimal design for given set A and its
Definition 4.1. Given the arm set X C Rd satisfying |X| = n. and a test set A C pd we define the optimal design of A by X(A), which
X(A) == argmin max |uvl 3 XEAX DEA
[xex Anaen -11, where A x= (AERIXI :120,
Σ>=
X

---

Published as a conference paper at ICLR 2025
Algorithm 2 Instance-Sensitive RAGE (IS-RAGE)
Require: a set of arms X, confidence parameter Peonss sample complexity parameter Saample> and grid parameter Sgria.
1: Let S| X, L1 Berid, Ai X()(S))), + p()((S)))
2: while [S do
3: set d, + 8/7² and N, 4 4 log S /6.
4: set { x f- Round , .N,, X. ((,))) where Round() is defined Definition 4.2 Nr and obtain observed rewards of ~N((0)) xt. 1); let
5: pull 1.p.. p Fr
0,
6: set Pz e
-0, 0, 5% max Pzz and Eo t D'2 - 7: set the elimination O, {xr S Bontt/ / L. and set en -
8: let S,41 + S, \ Or, X & ((4(()+1)) )), and pr+1 + p()(Sr+1))
+1 and set 9: let T, satisfy that gid I Lr iggid
Eln Ogna p()(X \ E 10= : cx > Auamlle (
Lr+1 f- Se +
(4.1)
p(v(X U00 0.))
10: r+
11: end while
Ensure: the arm in Sr
We also define the optimal design value of A by p(A) = maxyedAA=M(4) llvl
(xex Aga T)-1
Our algorithm relies on the Round function introduced by (Allen-Zhu et al. This function outputs multiset of size N from the input set X with specific approximation guarantees.
2021 Fiez et al. 2019a)
Definition 4.2 (Allen al. 2021 Fiez et al. (2019a)) ). There is a function Round(), (X, N, N, X,YY that outputs a multiset (zi, ), where E X for all i E [N] and N is the total number of arms, and the measurement set. If > then the output multiset satisfies
max WEY
C =
max N DEY
llyll ( T--
We define value eh* to represent the instance complexity of BAI-L, analogous to how Hi character- izes the instance complexity for BAI-M.
Definition 4.3 Soare et al. 2014b); Fiez et al. (0019a). We define 2i+ 2 (X) as follows:
x x. 2
(Ew'ex (z)))
min XEAX
max
(=.)
(x. - x)
It has been shown that 1/" is the instance-sensitvv lower bound of the instance complexity of BAI-L, with certain existing algorithms like RAGE achieving this bound up to logarithmic factors (Soare
et al. 2014b Fiez al. 2019a).
4.1
THE ALGORITIM
Our algorithm IS-RAGE is described Algorithm which built upon the RAGE algorithm proposed by Fiez al. 2019a).
RAGE can essentially be seen as an implementation of Algorithm 2 with Sample = 0. At round r, RAGE maintains set S, that includes the optimal arm æ. with high probability. It allocates budget
7

---

Published as a conference paper at ICLR 2025
N, based on observations from the previous (r 1) rounds, and then calls the Round function (as defined in Definition 4.2) to generate a multiset of arms X, = {zy..... .......................... xx RAGE pulls each arm in X, and computes 8, using ordinary least-squares (OLS) over the arm set and the reward set. Based on 0,. it calculates the suboptimality gap e for each a E S, and eliminates arms with large e-- RAGE then continues the next round with reduced arm set S,+1 = S, Or, where O, is the set of arms eliminated in round r.
Our approach. Similar to IS-SE, IS-RAGE (Algorithm 2 introduced an additional sample budget term at (4.1) when allocating the sample budget per arm for the next batch. The first term in the right hand side of (4.1) is the same as that in RAGE, which aims double the current number of pulls for each arm. For the second term, we uniformly distribute the estimated partial instance complexity of all eliminated arms (represented by Le in (4.1) to the set remaining arms Sy+1. where p()((X U,,1,,)) represents the "effective" cardinality of S,+1 for BAI-L. To better understand why 1 approximates the partial instance complexity of all eliminated arms, we have the following lemma.
Lemma 4.4. For any L > O, we have L p(y(2 x:: defined in Definition 4.3
: A. S 15/VL)) I 900ee, where vp" is
Roughly speaking, by selecting L - Pgni Lemma 4.4 shows that approximates the total instance complexity d² over the whole arm set X, which naturally serves upper bound of the partial instance complexity of eliminated arms x E - O.. We claim that such an algorithm design is necessary for linear bandits due to the fact that arms in linear bandits are often linearly dependent, while arms in MAB are independent.
Remark 4.5. We note that the hyperparameter Ssample governs how the updated Ly+1 relates to the partial instance complexity of the eliminated arms. As Bsample increases, each 1; in (.. also scales up, functioning similarly to Brample in IS-SE.
4.2 THE ANALYSIS
We try to show that IS-RAGE achieves the instance complexity o up some logarithmic factors, with a better batch complexity. Similar to Definition [.I] we define the instance-sensitive batch complexity for linear bandits as follows. For simplicity, we abuse the notations and reuse R₁, Lys L, for linear bandits.
Definition 4.6. Define a sequence L, = 4T. for some integer T, as follows. Let Ur == fx|A2 15/ V and
Lr+1 +- 4h, E 4th p()(X \ (xE U, A 15- 15-2-'1)
(4.2)
p()(X) (.))
and we select L,41 = 4t satisfying 4t s i.41 4'+ Denote R3 to be the minimal r satisfying U, X.
Generally speaking, the second term of the RHS in (4. gives an approximation of the partial instance complexity of arms in Uy. Ideally, we would like to use a definition similar to d= directly define the partial instance complexity of arms in U,.. However, since x, is unknown to the agent, we are unable to compute v/" directly.
We have the following theorem regarding Algorithm Theorem 4.7. With probability at least 5, Algorithm satisfies the following conditions:
1. (Correctess)) Algorithm 2 returns the optimal arm μt.
(Batch complexity) Algorithm 2 runs at most R₃ batches where Ri is defined in Definition 4.6 Furthermore, R₁ can be bounded as
900 log (1/
Rí S a logg
(X))
where is the number of different U, 's and 10 is defined in Definition
8

---

Published as a conference paper at ICLR 2025
12
Number of batches
20
Number of batches
12.5
10.0
7.5
Number
5.0
SE
2.5
6
10
20 40
80
100 120
0.0
10
20
25
30
Sample complexity -109
Sample complexity -10
Sample complexity 100
(a) SE v.s. IS-SE, (m)
(b) SE v.s. IS SE, (n)
(c) SE v.s. IS-SE, Ba(n)
Number of batches
70
Number of batches
10
Number of batches
16
8
RAGE I5-RAGE
B-RAGE
IS-RAGE
10
30
40
60
80
100 120
Sample complexity -10"
Sample complexity
Sample complexity -10
(d) RAGE v.s. IS-RAGE, Bi (m)
(c) RAGE IS-RAGE, (2)
(f) RAGE IS-RAGE, Ba(n)
Figure 2: Sample complexity v.s. number of batches.
3. (Sample complexity) Algorithm 2 has sumple complexity of
Qeb logo (1/A2) log(( +og(()/2)))))))
We provide a proof sketch here and leave the full proof to Appendix C approach to that of Theorem 3.1 but involves more technical details due the added complexity of linear bandits.
The proof follows a similar
Proof Sketch. Similar to the proof to IS-SE, we first prove that ex serves as a good approximation of the suboptimality gap Ar under high probability event. For batch complexity, we align the number of batches r with the batches R, we have defined in Definition 4.6 We still use induction to bound L, 2 I., and U, C O
deal with the randomness introduced by the sampling steps in IS-RAGE. Unlike IS-SE, due to the definition of 4, we force L, to be the power of 4 to make sure the induction step can be proceeded, which makes our analysis slightly different from that of IS-SE.
To show that R, S + +log
900 Log, (1/A2)v we adapt similar strategy as IS-SE with a new bound (i)'(X))
on the partial instance complexity of linear bandits. Finally, to prove the sample complexity result, we show that the additional sample complexity introduced by the summation of can be upper bounded by polylog( X {1/8)²> which suggests that the sample complexity of IS-RAGE is the same as di* up to some logarithmic factors.
Remark 4.8. Theorem 4.7 shows that IS- IS-RAGE can find the best arm with ( sample complexity, which is only log(1/ / /A2) worse than RAGE Fiez et al. (201 9a). Meanwhile, only requires O(a 1i (X)) + log log(1 //22)) number of batches. We can verify that both a and log (X)) are smaller than log(1/ 22) which suggests that our bound the batch complexity is tighter.
log
x0"
EXPERIMENTS
We run experiment on both synthetic data and real-world data too validate the effectiveness of our proposed algorithm.
In the following, we test our proposed algorithms (IS-SE and IS-RAGE) with baseline algorithms (SE and RAGE) over synthetic data here.
DDue limited space, please refer Appendix for the experimental results on real-world data.

---

Published as a conference paper at ICLR 2025
Bandit setting. We evaluate our algorithm using the three examples introduced earlier. These examples are denoted as (n), (n)n,, and (n)n), corresponding to Ex. 1 Ex. 2 and Ex. 3 respectively, where represents the number of arms in each case. When the agent selects arm with a mean reward (, the environment returns an observation a + 6, where e ~ (0, 0. For the multi-armed bandit setting, we test our algorithm setting, we set the dimension d = n and define the arm set as X = {ex [e: where e, represents the i-th basis vector n-dimensional space. Due memory constraints, we test the linear bandit algorithms with 500.
each B. (n) with
1000. In the linear bandit
Algorithms. We compare IS-SE (Algorithm[] 1 with SE across different parameter configurations on various bandit instances. For both SE and IS-SE, we set the confidence level ó = 0.1. Specifically, we evaluate SE with different values of ggnd and IS-SE with varying selections of both 3 3gni and Gaampee- Note that SE is equivalent to IS-SE when Brample = O. For SE, we fix Beert = 1 and test it
with Serid E (2.3,... 3, ..., 8}. For IS-SE, we also set Beeat and test with Bani E {2, .... 8) and Sxample E (0.5, 1, 2].
We also compare IS-RAGE (Algorithm 2) with RAGE. Specifically, for both RAGE and IS-RAGE, we set the Bonnt 1 and the confidence level 5 = 0.1. Note that RAGE is equivalent to IS-RAGE when Ssample = 0. For RAGE, we test it with 3grid E ( 8). For IS-RAGE, we test it with Ogri E {2, 3, ..... 8 and Bsampl E {0.5, 1.5, 2].
For each parameter set, we run the algorithms 10 times, reporting the mean and variance of the number of batches and sample complexity needed to identify the best arm.
For simplicity, we report the results of IS-SE with Ogri = 5 for all three instances, and we report the results of IS-RAGE with Ssamle = 1 as well. In the first two bandit instances B1 (n) and (n)), our IS-SE and IS-RAGE consistently outperforms SE and RAGE. This indicates that, for the same sample complexity, IS-SE and IS-RAGE are more efficient on allocating samples across batches, resulting in lower batch complexity compared to SE and RAGE. This aligns with analysis in the introduction, where showed that IS-SE achieves an (11) batch complexity. while SE has an O(log n) batch complexity. For the third bandit instance (n).). the results of SE and IS-SE can hardly be separated, so do RAGE and IS-RAGE. This suggests IS-SE and IS-R RAE do not yield a better sample-batch tradeoff compared with SE and RAGE, which also aligns our analysis in the introduction.
Results. The results are recorded in Figure 2
CONCLUSION AND FUTURE WORK
In this paper, we have proposed algorithms for best arm identification in multi-armed and linear bandits, achieving near-optimal sample complexities along with instance-sensitive batch complexities. Our batch complexities can be significantly better than log(1/Az) for many input instances, where the latter is minimax-optimat up to a algorithms in online learning, we believe that exploring algorithms with instance sensiiive batch complexity could be interesting direction for other bandit and online learning problems. A couple of immediate questions arise from this work. First, would valuable to analyze the average batch complexity of our algorithms on typical input distributions. Second, it would be beneficial to run experiments on larger datasets to better assess their practicality real-world applications.
factor. Given the importance of batched
ACKNOWLEDGMENT
Qin Zhang was supported in part by NSF CCF- 1844244 Tianyuan Jin was supported by the Singapore Ministry of Education AcRF Tier 2 grant (A-8000423-00-00).
REFERENCES
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 COLT, pp. 2017.
10

---

Published as a conference paper at ICLR 2025
Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near- discrete optimization for experimental design: A regret minimization approach. Mathematical Programming. 066:4394478, 2021.
Amir Ashouri, William Killian, John Cavazos, Gianluca Palermo, and Cristina Silvano. A survey on compiler autotuning using machine learning. ACM Comput. Surv., ((()::6:1-99:44) 2019.
Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pp. 41-53, 2010.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):25-225,, 2002.
Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In COLT, pp. 590-604, 2016.
Nicolò Cesa- Cesa-Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. In NIPS, pp. 1160-1168, 2013.
Lijie Chen, Jian Li, and Mingda Qiao. Towards instance optimal bounds for best arm identification. In COLT, pp. 535-592, 2017.
Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab S. Mirrokni. Batched multi-armed bandits with optimal regret. CoRR, abs/1910.04959, 2019.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi- bandit and markov decision processes. In COLT, pp. 255-270, 2002.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. International Conference on Computational Learning Theory, pp. 255-270. Springer, 2002.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning 2006.
Research,
Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff Sequential experimental design for transductive línear bandits. Advances in neural information processing systems, 32, 2019a.
Tanner Fiez, Lalit Jain, Kevin Jamieson, and Lillian J. Ratliff. Sequential experimental design for transductive linear bandits. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Buc Buc, Emily B. Fox, and Roman Garnett (eds.), NeurIPS, pp. 10666-10676, 2019b.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. In NeurlPS, 2019.
Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose H. Blanchet, Peter W. Glynn, and Yinyu Ye. Sequential batch learning in finite-action linear contextual bandits. CoRR, abs/2004.06321, 2020.
Eshcar Hillel, Zohar Shay Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed exploration in multi-armed bandits. In NIPS, pp. 854-862, 2013.
Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil' UCB : An optimal exploration algorithm for multi-armed bandits. In COLT, pp. 423 423,439, 2014.
Tianyuan Jin, Jieming Shi, Xiaokui Xiao, and Enhong Chen. Efficient pure exploration in adaptive round model. In NeurlPS, pp. 6605-6614, 2019.
Tianyuan Jin, Pan Xu, Xiaokui Xiao, and Quanquan Gu. Double explore-then seaere-thh--commmit Asymptotic optimality and beyond. In Mikhail Belkin and Samory Kpotufe (eds.), COLT, volume 134 of Proceedings of Machine Learning Research, pp. 2584-2633 26333. PMLR, 2021.
Tianyuan Jin, Yu Yang, Jing Tang. Xiaokui Xiao, and Pan Xu. Optimal batched best arm identification. arXiv preprint arXiv:2310. 24....4999 2023.
11

---

Published as a conference paper at ICLR 2025
Kwang-Sune Jun, Kevin G. Jamieson, Robert D. Nowak, and Xiaojin Zhu. Top arm identification in multi-armed bandits with batch arm pulls. In Arthur Gretton and Christian C. Robert (eds.), AISTATS, volume 51 of JMLR Workshop and Conference Proceedings, pp. 139-148. JMLR.org, 2016.
Cem Kalkanli and Ayfer Özgür. Batched thompson sampling. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), NeurlPS, pp. 29984-29994, 2021.
Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. In ICML, pp. 227-234, 2012.
Amin Karbasi, Vahab S. Mirrokni, and Mohammad Shadravan. Parallelizing thompson sampling. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), NeurlPS, pp. 10535- 2021.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In ICMI, pp. 1238-1246, 2013.
Nikolai Karpoy and Qin Zhang. Batched thompson sampling for multi-armed bandits. CoRR, abs/2108.061 12, 2021, URL / 2twp://011.01111022221
Nikolai Karpov and Qin Zhang. Communication--ffiiienn collaborative best arm identification. In Brian Williams, Yiling Chen, and Jennifer Neville (eds.), AAAI, pp. 8203-8210. AAAI Press, 2023.
Nikolai Karpov and Qin Zhang. Communication-efficinn collaborative regret minimization in multi- armed bandits. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan (eds.), AAAI, pp. 13076-13084. AAAI Press, 2024.
Nikolai Karpov, Qin Zhang, and Yuan Zhou. Collaborative top distribution identifications with limited interaction (extended abstract). In FOCS, pp. 160-171. IEEE, 2020.
Aniket Kittur, Ed H. Chi, and Bongwon Suh. Crowdsourcing user studies with mechanical turk. In Mary Czerwinski, Arnold M. Lund, and Desney S. Tan (eds.), CHI, pp. 453-456. ACM, 2008.
Sanjay Krishnan, Zongheng Yang. Ken Goldberg, Joseph M. Hellerstein, and Ion Stoica. Learning to optimize join queries with deep reinforcement learning. CoRR, abs/ abs/1888.013 808.03196, 03196, 2018.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Azalia Mirhoseini, Hieu Pham, Quoe V. Le. Benoit Steiner, Rasmus Larsen, Yuefeng Zhou, Naveen Kumar, Mohammad Norouzi, Samy Bengio, and Jeff Dean. Device placement optimization with reinforcement learning. In /CML, pp. 2430-2439 2017.
Vianney Perchet, Philippe Rigollet. Sylvain Chassang, and Erik Snowberg. Batched bandit problems.
The Annals of Statistics, 44(2):660-611, 2016.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Sociery, 58(5):527-5)) 535. 1952.
Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. In Samir Khuller and Virginia Vassilevska Williams (eds.), STOC '21: 53rd Annual ACM SICACT Symposium Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pp. 74-87. ACM, 2021.
Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), NeurlPS, pp. 828-838-88 836, 2014a
Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014b.
Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In David Zuckerman (ed.), FOCS, pp. 126-146. IEEE Computer Society, 2019.
12

---

Published as a conference paper at ICLR 2025
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-22 294, 1933.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: How much communication is needed to achieve (near) optimal regret. CoRR, abs//1904.00 2019.
Zihan Zhang, Xiangyang Ji, and Yuan Zhou. Almost optimal batch-regret tradeoff batch linear contextual bandits. CoRR, abs/21 10.08057, 2021. BtRl:ttps://aaee wwtprrwwww...gaa/////beea
08C57
A EXPERIMENTAL RESULTS ON REAL DATA
In this section, provide the experimental results the real-world data set.
Number of batches
e
We evaluate algorithms the Movielens25M datase which contains 25 million ratings for 60,000 movies by 160,000 users. We formulate this as multi-armed bandit (MAB) problem by selecting the top 1,000 movies with the most ratings and treating each movie as arm. The reward for pulling an arm corresponds to the negative rat- ing given by user for the associated movie. To accelerate the sampling process, consider only the first 50 ratings for each movie across all users.
O
4
IS-SE
8.0
0.2
0.4
0.6
Sample complexity -10
Figure lens25M
SE v.s.
IS-SE on Movie-
We compare SE and IS-SE on the Movielens25M dataset. Each algorithm tested with 3grid E {2, 4, 6, and Asample {0.5, 1, 1.5, 2}. For each parameter configu- ration, we run the algorithms 10 times and report the mean
and variance of the number of batches and the sample complexity required to identify the best arm. The results are shown in Figure 3 We observe that IS-SE consistently outperforms SE in terms of the sample complexity-batee complexity trade-off, highlighting the effectiveness of our algorithm.
B PROOF OF THEOREM 3.1
We now prove Theorem 3.1 We need the following technical lemma which characterizes the concentration properties of subgaussian random variables.
Lemma B.1 (Corollary 5.5 in Lattimore & Szepesvári (2020). ). Assume that Xi,..., Xn are inde- pendent, o-subguassian random variables centered around μ. Then for any e
TUE2 and
ne²
P( 2 p +
exp
P(A exp
20
20
where j 1/n Et= N,, We often use the following equalivent inequality: have
20 log((/0) 22)
P j P1é-
1
Next we start our main proof. We divide our proof into two parts. In the first part, we prove that our algorithm can find the optimal arm, and we bound the sample complexity for our algorithm find the optimal arm. In the second part, we prove that our algorithm enjoys a better batch complexity compared with the vanilla (1)2).
B. PROOF CORRECTNESS OF THEOREM 3.1
Proof of Correciness of Theorem
3.1
For any fixed arm i at batch we have
1
2 (
26
P
< exxp
2 T,r
<
L,
L,
2
13

---

Published as a conference paper at ICLR 2025
Applying the union bound over all arms and all batches, we have
2 T.p
201
=²81
P
n
10 mi
71 r
3
(21ig
Let ue,, arg maxics, PT. Therefore, with probability least x 728 /
have for all r 1,
2
p
L S p4, - p1 S P1
L
Therefore, with probability at least
x 8 3 = 1 - 6, Algorithm will return the best arm.
For simplicity, we denote the event defined in [B.1 as &, i.c.,
2
=
10 pal 2
Lep
B.2 PROOF OF BATCH COMPLEXITY OF THEOREM 3.1
Proof of Batch Complexity of Theorem 3.7 We condition on event E. First, by Li Algorithm | and the fact that J4, S S A we have
L 2 4L, f(U)==10)) where f(A) = ΣSEa 1/4
[A]
Recall the "virtual" sequences { and {Ur} we have defined in 1.2 We prove by induction that for all r,
U, S Uz-10,
and
(B.1)
L, 2 L,
(B.2)
Assuming that both (B.1) and (B.2) hold for step r. we first prove that (B.2) holds for step (r 1):
L,+1 2 4L, + f(U,_, O.) 2 4I, + f(U,) = L,+1,
where the second inequality uses the induction hypothesis.
We next prove that (B.1) holds for step (r + 1). To this end, consider the set of eliminated arms Or+1- Note that by our algorithm design, O,-1 satisfies
O [ U O. 10t1 5V2/ 1//2//Ln.. I-
We also know that for any j E U/+1, j satisfies that A, > 1 based on the definition of
Up41. By (B.2), we have A > / By ej 2 A we further have ef > 2/
then we directly have j E U Otherwise, we We now consider any Ur+1- j U Os, have
jE ([n]) U O (5: 5/2/Lr+1) Or+1,
which again suggests j 1 O,, Therefore, B. holds for (r 1). Consequently, both (B. and B.2 hold for every r 0.
By B.2), the total number of batches can be bounded by the smallest satisfying L, > 1/43. Note that L, is a fixed sequence. Let Rt be the smallest r satisfying L, 2 1/22, which is the batch complexity want further bound.
Consider the quantity
450
H, I, (onn-111)-
Σ
where U, 11: A, 2/T.).
A
JEU,
14

---

Published as a conference paper at ICLR 2025
By definition of Hy, we have Hu n and HR41 450H.
We first observe that {Hr} is an increasing sequence.
450
1n+1(n-1U++H)) - U1++1)) +
Σ
A
jEU++1
450
> Ln - (U-++1) +
A
jEUn+1
L,(n-IUF)) L, UU, (U++1|)
Σ
450
Σ
450
jEU 3
43
jEUr+1/U,
450
2 L,([U,l (U++1)) + (IU,) - (U,+1)) + In - |U,1) + Σ
3
jEU
450
2 (n - (U)) +
AT
JEU,
where the first inequality holds since {I.r} is an increasing sequence, and the second inequality holds since for any & Ur, have A, I / by the definition of Uy..
We next show that when Ur+1 Ur, we have that Hr+1
451 H,. Note that
150
(n- -UU++2))
Σ
450
A
jEU++1
450
450
= (n-1(n-100 - + L (U++1)) +
Σ
A
A
jeU.
jEUr+I/U,
451
450
4L,(n -UU+) + Σ
+ -101-11111
Σ
A
A7
JEU,
JEUr+1/U,
451
(L,(n - (U-1) Σ
A
jEU,
451
(n-n11U71) + Σ
450
450
-
A7
JEU,
Therefore, suppose that 0 = SrI ...
To = R satisfying V1 vlsis a, Ur, + Ur-11 For any
1 < i S a and any r; < r < Ti+1. we have
451
451
1-
/55
1:11 1111
H Z H H 2 ...
H 2
H
450
450
450
which gives
Ti+1 < + log H - log Hr.
Taking the summation, have R. log
4b0 (450H/n).
B.3 PROOF OF SAMPLE COMPLEXITY OF THEOREM 3.1
Proof of Sample Complexity of Theorem 3.7 We derive the sample complexity under event E. We know that at the r-th batch, all; j E S, satisfy
2
1g A
p=1+ 10 - Mj S 2
L,
Thus, for all j O,, we always have
2
A - A 3/
L
15

---

Published as a conference paper at ICLR 2025
which means 3 S A. Note that Lr+1 4,, guarantees that the number of arm pulls in S,+1 at the (r + 1)-th batch is at least times larger than that the r-th batch. Assume arm i is eliminated at the ry-th batch. The total number of pulls of arm i can be bounded by
N₂ ll Lr, ((lgg() log log A Lr.).
Therefore, only need to bound E Trr.-
We divide Lr, into two parts Ij and I2, and bound them separately.
1
L,
+ 44r-1
|s
S
==1 JEO,
13
Bounding term Ei>1 R. complexity:
We take the summation of 1 ,...., to bound the total sample
Σ4-LX ri-
Σ
99
s=1 JEO, S
S A
JEO,
where the inequality holds since for all j Os, we have } S ej S A., Next, note that |S,] = 10,l+ + [OB|, where B is the total number batches. We have
B-1
ΣΣΣ S. JEO.
S min min n1 B} Σ
A
S.
A3
2
JEO.
==1
j>l
j>1
where the last inequality holds since for each
|0
- |S,) and
10,1-1
10.1
Σ
SSA]
S - k
Bounding term Eis1 Iz. By the definition of r, and under the event E, we have
2
2
A < t + + All s 5 V/ Lr,-1 + V Lrr:-1
7
LM-11
where the second inequality holds because the i-th arm will not be eliminated at the (r; 1)-th batch. Therefore, we have L,,-1 S
2 which suggests
AZ
ΣEsO
Σ
1
A
1>1
1
Combining the two parts and using the fact that = (Oog(( 1/42)), the total sample complexity is bounded by
2 >>x L., log(r?n/61)
< (010((///)+ + log 4, Σ Lr,
122
i22
< o (10((n/))) + log
Boggog,511 A2 log migfmin. (n,, 4- Σ 1
122 A3
C PROOF OF THEOREM 4.7
Like Theorem 3.1 we prove our theorem for its correctness, batch complexity and sample complexity. We have the following lemma:
16

---

Published as a conference paper at ICLR 2025
Lemma C.1 (Section 2.2 in Fiez al. (2019a)). Civen set Y C R., for any fixed design T1,...g 2N
(multiset) as well as their stochastic reward R1 R1,.., Ry satisfying R₃ 0_x; x4 NN 1), let 0s be the OLS estimate. Then
P PY E
EyeEY Y.
-.) 2 (0)
-2/oo S
(C.1)
We define the event & as follows & = nE,, where
e == Vy V(S,), (0, 0.)'y y IIvll E xx1)-1 2/ (looool((s(s))))
(C.2)
Lemma C.I suggests that E, holds with probability least 8,, therefore we have & holds w.p. least
2, o 2 1- 6.
Next assume & holds. We show that 1/34, S S. 55/3n. First have
1 - 421= 10,- (x' x) - 0_ (x. - -x]l-
(C.3)
To further bound it, for any x E Sr, we have
0,7 (x² x) 0_ (x, x) = (0, - 0.) T - z)) + + +0. x.)
s (0, 0.) Tx= -x)
< max |1 -(x))-1 2 log( [og(|S/1//00 1//) DE)(S.)
(C.4)
where we use Lemma C.I and the fact that xr, E S,. Next, we further have
07 (x. - x) - 0_ (x.. - x) = 0, (x" - x.) - (0. - 0r) (r)T(x.. (x. - x)
2 (0. 0r) (Ix- -x) x))
2 max |M | T 2/ (og(1S,12/6)
(C.5)
(E)
where we use the fact that 0, (x" x.) 0. Therefore, for any S,, we have
1 - max yEV(S.)
| =x / /oo([ S+1/6) = 2 c)p./N, (C.6)
Then for all x E O,,, we always have
A 2 6 6xz - A, 2
3/2 -Ael,
which means 1/3A, S < 5/3A,
C.I PROOF OF CORRECTNESS OF ALGORITHM! 2
Proof of Correctness of Algorithm 2 Suppose & holds. Let x. be the & with max, f. Assume that Ix E S,. Then we want prove that Is E S with high probability. Actually have with probability 8,
c, 0_ (a. x.) 10,- 0.) T.))(a0 -x.)
S (0,- 0.)T [x=xx----- - -x.)
|| Ixexx ax --1 2 2
max
vEV(S.)
max vE)(S.)
1yyliE (A)))
2 Ioolool S, +1)
< 5/ VT..
(C.7)
where the first inequality holds since x. maximizes 0_ x, the second one holds due to Lemma C.1 and the fact that x² r", Sr, the third one holds due the ROUND function, the fourth one holds sinee [)S))) I < ? and the definition of pr. the last one holds due to the definition of N,. Therefore, know that v. will not be discarded round under E
17

---

Published as a conference paper at ICLR 2025
C.2 PROOF OF BATCH COMPLEXITY OF ALGORITHM 2
We first have the following lemma, which restates Lemma 4.4 Lemma C.2. For any L > O, we have
L. A
900e
(C.8)
Proof. We have
L. P((( (x: > 15/VL]))
L. min
max
|1y|13 Erex Auax 1
XEA (
< <..L. min ΛEA
11 x1-1="10 " xxex Tx
||y xx || [I Ae ( T)-
< 4. 225 min
max AEA (x
A
|1 xx 113
(x Agazn )-1
S 4. 225 min max
XEAR yEX
A
= 900 "
(c.9)
where the first inequality holds since be A ||e e E A and some metric
bll S 2 max ||a cll for some set A. some ||; the second one holds since for any y E X (x: A. > 15 /VT,, we
have L 225/4y
Now we start to prove batch complexity of Algorithm 2
Proof of batch complexity of Algorithm 2 Suppose holds. Similar the MAB setting, we use induction to prove the batch complexity of Algorithm 2 4 and
Recall that T, satisfies that 4 I L, <
L,41 t 4h, ΣE 4th -OXX (EEVE > 2- 2-1 5/3)))
P( U.))
EtH 4' -(0(( \ 15 2,2111))
2 4T +
(C.10)
p()(X (U,,
where we use the fact that en T, satisfies that I,, 4T. and
S <5/3A, under the event. We define the virtual sequence L,, follows:
L,t1 t 4I, + Σh. 4' (((( (o E U.. A, 15.2-1)) U, = > 15)
p('(X \ Uz))
(C.11)
and we select L,+1 = 4TH satisfying 4T < L,41 < 4+
Next, we use induction to prove that
L, < Lr,
(C.12)
U, C 0,
(C.13)
Suppose both C.12 and CC.33 hold for 1,..., For r + 1, we first prove (C.12 holds.
Since C.I3 holds for r, we have U, C _,",,,
O., Note that by the definition of T,, we have another
definition of Up. which is U, = {ar A, 15 2 F. Therefore, for all t < T,. we have
{o U, A, 15 2- ) (a A 15-2-
(C.14)
Meanwhile, since U, - O., we have
(a E U, A, 15 2 C (r E Us A 15 2 (s: A, > 15. 15.2-%.
(C.15)
18

---

Published as a conference paper at ICLR 2025
Therefore, combining (C.14) and (C.15). we have fir Up A. 15 15.2 2- fx E U,=102: Ag 13. Then we have
p()(X ( : A 15 - 2)) - p()((x fre A 15- 15)
(C.16)
Since (C.12 holds for r, it suggests that T, Tr Then following (C.10). we have
Lr+1 2 4L, + Σl 4" p()(X \ fx
A. > 15.2 (5.22"1) 2))
p()(X \ U,==
ΣE= 4" p \ for E 1,,,0,= 02 15 2))
2 4L, +
( \U+)
4L, ElS 4' p fxr E Ur :Ax > 15.2... 2))
p()(X \U))
2 L,+11
(C.17)
where the second inequality holds since U, C C O₂ and T, 2 Tr, the last inequality holds due the definition of L,+1. Thus, we prove that C.12 for r + 1.
Next we show that CC.13 also holds for + Consider O,41, whose definition is
O.+1 fI X 0, > 5/ L/
(C.18)
For any x E Up+1, we have U,41 + 5/ V Lr+11 which be derived as follows:
E U/+1 + A 2 15/ L, A 15/ Lrti + o 5/v
L,+1.
(C.19)
We now consider any U,+1 If U O,, the induction is done. Otherwise, have Or+1 by definition, which again suggests that x E -*+1 O,. Then (C.13) also holds for r + 1.
Next we only consider the sequence Lp 4T., We consider the sequence
Tr H, = 4th p()(X)
fx A > 15 15. 2-)) U, = A. >,11//
(C.20)
Based on H,, we have the definition of L,-1, which is
L 4L, (x/ X U,)), 1/4 L S L,+1 < L
(C.21)
First we would like to show that H, S H,41- is obivious since T,41 > T, due to the fact that L 4h..
Next we would like to show that 4 p(0' < H, < 900 (1/2(1)2)) For the left hand side, note that
H, 2 H = 4. p()(()) 24 (x)(())
(C.22)
For any 1 T2 have
4' xX fIEU.:A, 15-2-"1) = 4" -(0(( - fx A. > 15 15-2 2)-)-11)) - 900 30" where the inequality holds due to C.8 Therefore, H, < 900 (T+) I 900 log, (1/ 1/ where we use the vacous bound that T, log (1/2(11//))) (1/A2).
Finally, we show that for any satisfying when U, = Ur+1, we have Hrs1 2 5/4 H,. We have
Tr
H
4
p
E A, > 15-2-(1))
Tr+1
Σ
4 p()(X / fo E U, A. > 15-2
t=1
19

---

Published as a conference paper at ICLR 2025
Σ 1=1
4' / 15)2
4,
Σ 4
Σ
4 ,()(( (EEU; > 15-2
t=1
Σ
4'- (2 > 15-2-')))
5
H
(C.23)
4
where the first inequality holds since Ly-1 4TH 1, the second one holds due to the definition of Lr+1, the last one holds trivially. Therefore, it is easy to bound R as
R S a + logs// (900 logz (1/
(C.24)
p()* (X))
where a is the number of different U..
C.3 PROOF OF SAMPLE COMPLEXITY OF ALGORITHM
To prove the sample complexity, we first show the following lemma holds, which includes several claims.
Lemma C.3. Suppose & holds. Then for any we have the following claim:
S,+1 (X U 0,) S 12 A. S L.).
(C.25)
Furthermore, for any t $ Tr, we have
(X fz E E A. 5.2 (1) f2 A. 15 2-
(C.26)
Proof. CC255 holds since 2 & U O2 - S L/ which suggests that A, S 15/ 15/ L, by
the fact that c > A2. To show (C26). we fix r and t < T,,, and note that for any E X {z
-0 O2 A > 5 t we have either
1. $ 0,
E 1, and A, 55.2-
For the first case, we have A, < 15/ by (C.25). Using the definition of T, (4 S L, < < we have L, 4', which further suggests that A, 15 2 For the second case, we always have A, < 5- 2 < 15-25 2 Therefore, (C.26) holds.
Next we start to prove the sample complexity of Algorithm
Proof of sample complexity of Algorithm 2 Suppose & holds. Recall the definition of L, we have
Tr+1 = 4T, + Σ 4'h +(1X \ for E U,-10, :6z > 2- 2-t.5/3))
P()(X \ 0.,,
ΣT. 4' p(1(X {I E U O2 A. 25.2
< 4L,
p \ O.))
21=1 4' p(U(f2 E X A, S 15.22-2 15))-))) pV((X \ U,=)
< 4L,
(C.27)
where for the first inequality, use the fact cu 5/2 Ars and the second one holds due to C.26). Now, we start to bound Nr+1, which is
N441 (2g((2 1// P Irt1,d]
20

---

Published as a conference paper at ICLR 2025
4d + 16 log (
4d + log X 1)) (,)=
T 4' 012(122 E X A. I 15 2)))
AL,
p()(X U.)=
4d + 16
Tt
(AL.D(M(X \ (.-10.)) + Σ 4
4d 11+1610g(1116--
T.
(L. S 15/ (r))) + Σ 4' 4 :
S 4d + 16 16 (
3600 + 900
(C.28)
where the second inequality holds due to
C.25 and the last one holds due to C..) Therefore, by
C.28
let B denote the total number of batches which is always bounded by log(1 A2), we have
N 4p()(x)) + Σ N S Owv log (1/A2) log( log() (16))
+ log(1/ (1/2)d)),
where the fact that p (X)) S d, which is the standard property of design (see Section 21.1
in Lattimore & Szepesvári (2020)).
21


Reviews:
[{"review_id": "M0bHbszw2x", "reviewer": "Reviewer_AcUK", "summary": "This paper studies the classical best-arm-identification (BAI) problem in the batched setting. The batched setting means that the agent has only limited number of batches. In each batch the agents can arrange which arms and how many pulls for each arm and only receive the results of the pulls after this batch. In this setting, the classical BAI algorithms are not viable. \n\nThe authors propose new batched BAI algorithms with adaptive batch sizes (the number of arms pulled in each batch), and achieve a sample complexity of \\tilde{O}(\\sum_i 1/\\Delta_i^2), which is the first to break the bound of \\tilde{O}(n/\\Delta_2^2), where Delta_2 is the largest reward gap between the optimal and sub-optimal arms.\n\nThe authors also extend the batched BAI problems to the linear bandit scenarios and achieved similar results.", "questions": "Any study on the lower bound on sample complexity given the lower bound batch complexity?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "First, this paper studies a pretty interesting problem. Batched BAI is a very practical setting in industry. For instance for parameter tuning, people will not wait for the last model to complete training before starting another one, given each model training takes days. Batched BAI is a more practical setting for parameter tuning. However, there have not been enough works in this area. Hence, I think this paper is studying an impactful problem.\n\nSecond, the results in this paper are good. Ignoring the logarithmic parts, the algorithms have achieved the same sample complexity as the best of BAI. Although I guess ultimately, we should be able to achieve n\\log(\\delta^-1) sample complexity as classical BAI someday, the n\\log(n)\\log(n/\\delta) is still good enough at this stage. The authors further extend the works to linear bandits. \n\nThird, the algorithms have some novelties. The algorithm uses precise allocations of the batch sizes in order to keep both sample complexity and batch complexity low.", "weaknesses": "Some numerical comparisons will strengthen this paper, and also illustrate the improvements of the proposed algorithms. \n\nSome minor suggestions about the writing. 1. Better not use \\Delta_2 in abstract while not explaining it. It may cause confusion to some readers. 2. Present more details about the works in CL area, as they share a lot of similarities to the problem in this paper. 3. In the introduction, before using heavy math notations, try to use more natural words to explain what BAI is and what batched BAI is, which can help readers understand what this paper is doing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "pNwhLG0TU2", "reviewer": "Reviewer_eBKQ", "summary": "The paper considers the problem of batched best-arm identification with a goal of minimizing the batch complexity, which could be an issue for fixed-confidence best-arm identification depending on the minimal gap between the best arm and the second-best arm. The contributions include new algorithms for both k-armed bandit and linear bandit settings as extensions of classic algorithms.", "questions": "The RAGE algorithm, which serves as the building block algorithm in this paper, has publicly available code. Since the proposed algorithm is an extension of it, I wonder if the authors could reproduce some results to demonstrate the improvements.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The first algorithm reduces the batch complexity dependence on the minimal gap between the best arm and the second-best arm.\n- The paper is well-written and very easy to understand.", "weaknesses": "- There are some improvements in the experiments, showing roughly a 2x gain, but it's hard to call them impressive, as the experiments are limited in scale and only cover simple problem instances. Additionally, there are no experiments on the linear bandit setting.\n- The contribution mainly reduces a logarithmic factor in batch complexity by transferring it to sample complexity. However, it’s difficult to see an absolute impact on the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "2IGY5cAzah", "reviewer": "Reviewer_GT9n", "summary": "This paper proposes two algorithms, instance-sensitive successive elimination and RAGE, where the batch complexities can outperform the $\\log(1/\\Delta_2)$ bound.", "questions": "See above", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "(1) Theoretically, the paper demonstrates that the proposed algorithms achieve near-optimal sample complexity while breaking the barrier for batch complexity.\n\n(2) An instance-sensitive quantity, $R_I$, is introduced.", "weaknesses": "(1) A significant issue is that the two algorithms lack empirical support, making it challenging to convince readers of their practical value.\n\n(2) Breaking the $\\log(1/\\Delta_2)$ barrier appears to be conditional, depending on the number of arms with nearly optimal means being relatively limited compared to the total number of arms. In such cases, the allocation may rapidly focus on only a few arms. I am uncertain whether these algorithms offer any advantage over the original SE under these conditions.\n\n(3) The issue of a small gap $\\Delta_2$ is more serious in the fixed-budget setting and has been observed in Bayesian Best Arm Identification (BAI). For example, the paper Exploration for Fixed-Budget Bayesian Best Arm Identification (arXiv: 2408.04869) discusses this. More related work should be considered.\n\n(4) Some parts of the paper are difficult to read, possibly due to the theoretical depth. For instances, it’s challenging to understand $R_1$ from Definition 1.1 across the three examples in Figure 1. $\\Delta_2$ is undefined, though it appears to represent the gap between the best and second-best arms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "wWwODXV7tA", "reviewer": "Reviewer_2sNi", "summary": "The authors conducted a study of the batched BAI problem in both MAB and linear bandit settings, and improved the existing bounds. They proposed IS-SE and IS-RAGE, which stem from the previous algorithms and both have good performance in some cases (outperformed the O(1/Delta) bound). The experiments also corroborated these results.", "questions": "The examples mention that: in certain cases, IS-SE can have fewer batches than log(1/Delta). Why is this the case and when would this happen?\n- In this case, do other algorithms also need log(1/Delta) batch, or just the same as IS-SE？\n- Does it truly imply O(1) batches ( since SE still need log(1/Delta))? This is not so clear.\n\nPost-rebuttal: the authors have provided responses that help answer these questions.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors proposed a new algorithm that, in some ways, improves the original result in MAB and linear bandits setting. The theoretical result is solid. The experiment was compared with the SE algorithm comprehensively.", "weaknesses": "The authors need to compare with more algorithms beyond SE. The novelty of the proposed algorithm is not clearly stated. Also, why is the proposed solution better?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)