Optimal and Practical Batched Linear Bandit Algorithm
Authors: Sanghoon Yu
Min-hwan Oh
Venue: ICML 2025 poster (2025)
Keywords: linear bandit
batched bandit
exploration-exploitation
Primary area: theory->online_learning_and_bandits

Abstract: We study the linear bandit problem under limited adaptivity, known as the batched linear bandit. While existing approaches can achieve near-optimal regret in theory, they are often computationally prohibitive or underperform in practice. We propose BLAE, a novel batched algorithm that integrates arm elimination with regularized G-optimal design, achieving the minimax optimal regret (up to logarithmic factors in $T$) in both large-$K$ and small-$K$ regimes for the first time, while using only $O(\log\log T)$ batches. Our analysis introduces new techniques for batch-wise optimal design and refined concentration bounds. Crucially, BLAE demonstrates low computational overhead and strong empirical performance, outperforming state-of-the-art methods in extensive numerical evaluations. Thus, BLAE is the first algorithm to combine provable minimax-optimality in all regimes and practical superiority in batched linear bandits.

Optimal and Practical Batched Linear Bandit Algorithm
Sanghoon Yu'
Min-hwan Oh'
Abstract
Despite the rich literature on fully adaptive linear bandit algorithms those that update policies parameters
We study the linear bandit problem under lim- ited adaptivity, known as the batched linear ban- dit. While existing approaches can achieve near- optimal regret in theory, they are often compu- tationally prohibitive underperform in prac- tice. We propose BLAE, a novel batched algo- rithm that integrates arm elimination with regu- larized G-optimal design, achieving the minimax optimal regret (up to logarithmic factors in 2) in both large-K K and small-K regimes for the first time, while using only Oloog log 7') batches. Our analysis introduces new techniques for batch- wise optimal design and refined concentration bounds. Crucially, BLAE demonstrates low com- putational overhead and strong empirical perfor- mance, outperforming statc-of-the-art methods in extensive numerical evaluations. Thus, BLAE the first algorithm to combine provable minimax- optimality in all regimes and practical superiority in batched linear bandits.
ery round (Auer 2002 Abe et al. 2003 Dani et al. (0088
Chu et al. 2011 Abbasi- Yadkori et al. 2011 Li et al. 2019 Kirschner et al.
2021). many practical systems of- ten cannot afford such frequent updates because of com- putational or operational costs. Large-scale recommenda- tion systems, for example, cannot retrain policies every in- teraction, and in clinical trials, continually changing treat- ments can be both logistically and ethically prohibitive. These constraints have motivated a growing body of work on batched linear bandits, where policy updates occur in small number of discrete batches (Abbasi-Yadde Yadkori et al.
2011
Han et al., 2020 Esfandiari et al., 2021
Ruan et al.
2021 Hanna et al. 2023 Ren al. 2024 Zhang et al.
2025
Batched linear bandit algorithms must strike delicate balance between exploration and exploitation within each batch, aiming to minimize both the number of policy up- dates and the cumulative regret. Although recent work pro- vides strong theoretical guarantees (Ren et al. 2024 ZZhng et al. 2025), their empiricial limitations may undermine the intended benefits of batched learning. In numerical experi- ments (see Section[). the method of Ren et al. (2024) tends to eliminate arms prematurely (often including the opti- mal arm) and suffers in practical performance, while other methods update parameters rather too frequently (Abbasi-) Yadkori al. 2011 Esfandiari et al. 2021 Still oth- ers require such substantial computation that they become infeasible even at moderate problem scales (Ruan et al.,
1. Introduction
Stochastic linear bandits form cornerstone of sequential decision-making and online learning, enabling an agent to repeatedly select actions from a feature- based action set and observe stochastic rewards drawn from an unknown linear model (Abe & Long 1999 Auer 2002 Dani et al. 2008 Li et al. 2010 Abbasi-Yadkon et al. 201 Latti- more & Szepesvári, 2020). This framework elegantly cap- tures settings where the action space can be large but struc- turally low-dimensional, as actions naturally embed into a feature space. Such structure enables efficient general- izatiin and has been successfully applied across a wide range of domains, including clinical trials and precision medicine (Lu et al., 202T) to recommender systems (Li
2021 Hanna et al.) [023 Zhang et al. 2025) (sce Ap- pendix Much of this empirical inefficiency observed with the methods in Ruan et al. (202T); Hanna et al.) 2023 ; Zhang et al. (2025) stems from algorithmic compo- nents tailored to contextual settings with time-varying fea- tures; when these algorithms are applied the plain, fixed- feature linear bandit, they cannot exploit the static structure and therefore still incur excessive computation.
al. 2010) and inventory control (Jin et al. 2021a).
Consequently, despite recent progress, it remains unclear whether batched linear bandit algorithm can simulta-
'Scoul National University, Scoul, Republic of Korea. Corre- spondence to: Min-hwan Oh <minoh krr.
'Note that AbbasiiYaddkori et al. 2011 Section 5.1) intro- duced the rare-switching OFUL that attains batch complexity of Od log
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Optimal and Practical Batched Linear Bandit Algorithm
neously attain minimax-optimal regret and exhibit strong empirical performance. This open challenge motivates our central research question:
tially outperforms existing batched linear bandit al- gorithms, offering combination of provable near- optimality across all regimes and strong empirical per- formance.
Can we design a provably optimal and practically superior batched linear bandit algorithm?
Overall, BLAE demonstrates that provably optimal worst- case regret can be achieved alongside low batch complexity and tractable computation eeepy objectives in batched ban- dit research. By uniting strong theoretical guarantees with robust empirical performance, BLAE helps resolve the long- standing tension between provable efficiency and practical viability in the batched linear bandit setting.
A positive answer to the question above would bridge the gap between theory and practice. offering a concrete blueprint for algorithms that are both statistically sound and computationally viable for batched linear bandits.
Our Contributions. We present practical and minimax-optimal batched linear bandit algorithm, Batched Linear bandit Algorithm with Elimination (BLAE), that simultaneously addresses both computational efficiency and theoretical guarantees with practicality. We summarize our contributions below:
2. Related Work
A growing body of work has investigated batched bandits, in which the learner is allowed to update its policy only at a small number of discrete batch points, thereby reconciling near-optimal regret guarantees with a strict limit adap- tivity (Abbasi- Yadkori et al.)
Novel Batched Algorithm and Regret Guarantees. We propose BLAE, which constructs a judiciously de- signed urm-elimination strategy integrated with reg- ularized G-optimal design. BLAE achieves a worst- case regret (Theorem 1 of
2011
Perchet et al. 2016
Gao et al. 2019 Han et al.
2020
Ruan et al.) 202 Jin
et al. c Hanna et al.
2023
Esfandiari et al. 2021
Jin et al. 2024 Ren et al. 2024 Zhang et al. 2025).
o( (Vlog(KT) A Vd+ T) log log T)
Several of the earlier contributions focus on the multi- armed setting (Perchet et al. 2016 Gao et al. 2019 Jin et al. (021b|e). Subsequent work extends batching to linear contextual bandits, beginning with Gaussian-type feature models (Han et al. 2020) and later generalized to adver- sarial features (Esfandian et al.) 202I). More recent algo- rithms attain near-optimal regret while reducing the batch complexity to the minimal Ollog log T) (Ruan al. 2021
where K is the number of arms, d is the feature di- mension, and T' is the total time horizon. To the best of our knowledge, this is the tightest known bound for batched linear bandits. More importantly, BLAE is the first batched linear bandit algorithm that (up to logarithmic factors in 2") simultancously matches the lower bounds of ((dvT) for the large-K K regime (K 2 )) and C(VdTloog K) for the small-K regime (K & )ce)).
Hanna al. 2023 Ren al. 2024 Zhang al. 2025
Despite these theoretical advances, many existing meth- ods face practical obstacles. Algorithms that rely on (log T) batches (Abbasi-Yadkorii et al., 2011] Esfandi- ari ct al. 202T) still update more frequently than the de- sirable (log log Io) increasing computational overhead. Approaches that do match the lower batch complexity of- ten employ two-phase updates that split each batch into separate "estimation" and "policy-leamning stages (Ruan) et al., 2021 Zhang et al., 2025); this structure inflates run- time and may leave the information matrix ill-conditioned. Furthermore, the algorithms of Ruan et al. (2021). Hanna et al. 2023). and Zhang et al. (2025) incorporate subrou- tines tailored to time-varying features. Even after pruning these components to fit our fixed-feature setting, the imple- mentations remain computationally intensive and become impractical at moderate problem sizes (see Appendix F.. Although those routines are justified in broader settings, we find no simple way to streamline them for the plain fixeu-feature linear bandit, leaving much of the burden un- resolved.
Batch Complexity. Notably, BLAE achieves the minimax optimal regret for both the large- K and small-K K regimes with minimal batch complexity of Olloglog']
Refined Technical Analysis. Key our results are analysis techniques for regularized G-optimal de- sign under batch updates (Lemma 3). along with a concentration bounds that accommodate both batch- ing and regularization (Lemmas D and 2 Addition- ally, our refined analysis of efficient coverings of the unit sphere provides both theoretical guarantees and practical improvements (Lemma g These technical tools may be of independent interest for both batched and batche bandit research.
Practical Superiority. Extensive numerical evalua- tions demonstrate that BLAE consistently and substan-
2

---

Optimal and Practical Batched Lincar Bandit Algorithm
Table I: Worst-case regret and batch complexity comparison in batched linear bandits. BLAE achieves a regret bound of Ó( ((vdTlog K A dvT). matching the best-known (and indeed minimax-optimal) results for fully adaptive linear bandit problems. Moreover, BLAE operates with only Olog log batches, comparable to the lowest batch complexity among existing methods. The regret bound of BLAE simultaneously covers both the large-K K regime (K 2 I) with (dv'T) regret and the small-K K regime (K I O(e*)) with O(vdT log K) regret matching the lower bounds for the both regimes, thereby establishing the tightest known performance guarantees for batched linear bandits.
Paper
Worst-Case Regret
Batch Complexity
Abbasi-Yadkori et al.
(011
Odd T log T)
Od T)
Esfandiari et al. (2021)
((v df log(K'T)) (KTT)
O T')
Ruan al. 2021
0 dT loog (KK'T') log log log T)
O (log log T)
Hanna et a.. (0223
O (dy 'oog T log log ?')
o (log log T)
Ren al. 2024)
O V d' log KTT) log log T')
O (log log 7")
Zhang et al.
2025
0 ( log (dK'T) log T log(dT)) log log T)
o (log log 7)
Dani et al.
2008
(Lower bound)
(dyTT)
Zhou (2199)
(Lower bound)
(f log
This work
O(VaT (Vlg (T) A vd log T) log log 7) Olog (loglog7 7)
A recent work (Ren et al. 2024) shows that Olog Io) batches suffice to achieve the regret O(VTTlogg K) in the small-K regime (log K v (d)), the tightest bound known so far. However, designing an algorithm that achieves op- timal regret in both the large-K and small-K regimes si- multaneously remains open problem. Empirical exper- iments (Section ()) further reveal notable weaknesses: the algorithm often eliminates arms prematurely-incclddnn the optimal arm-anm is highly sensitive to the hyperpa- rameter %, whose choice can enlarge the third batch to (log T))+ exhausting the horizon and impeding ex- ploitation.
||>| = Vx² Hr. The trace, determinant, and adjugate (the transpose of the cofactor matrix) of H are denoted by (H)ce(H), det (H), and adj( H) respectively, We denote by [n] the set {1, (I,...,yL n for positive integer n, and use A to denote the minimum operator.
3.2. Problem Setting: Batched Linear Bandits
The stochastic linear bandit setting is classical framework for sequential Dacision-making in which an agent aims to maximize cumulative reward by selecting actions (often called arms) with unknown but linearly structured rewards. Specifically, the agent maintains a set of K arms A := (a(1), _,(2) ..... .....,,(RR) (K)),, ), each embedded in d-dimensional feature space, (kk) Rd for all k: [K]. and repeatedly chooses which
In contrast, our proposed algorithm, BLAE, bridges these gaps by attaining minimax-optimal regret guarantees (up to log factors of T') in both the large- K and small-K regimes, while using only Ollog l') batches. We address the common pitfalls of excessive computational overhead and premature arm elimination by introducing refined regu- larized G-optimal design approach. As result, BLAE con- sistently outperforms existing methods in numerical exper- iments (Section 7 demonstrating that it is not only theo- retically minimax-on optimall but also practically robust.
to pull over horizon of T rounds. At each round E [7', an arm I, A is selected, and a noisy reward of the arm It.
r: = (I,, 0*) + ?
is observed, where H" E d is an unknown parameter vec- tor, and is an independent o-subgaussian noise with zero mean. The agent's 's objective is to minimize the cumulative expected regret, defined as
3. Preliminaries
Σ (1x", ,-0,,-0----0 (Fe, -(0) 00))0)))
3.1. Notations
R(T) E
We denote the cardinality of a set by J. and the indi- cator function by 1z(x), where 1x)x
if x E A, and 1 (z) 0 otherwise. For vector norm is denoted by || and the weighted fo-norm as- sociated with positive definite matrix H is defined as
where x² argmax (xr 0*) is an true optimal arm in terms of expected reward.
Rd, the lx-
In fully adaptive linear bandit settings, the policy is typ- ically updated immediately after observing the reward r.
3

---

Optimal and Practical Batched Linear Bandit Algorithm
from the selected arm 24, before the next round begins. However, in many practical applications, such frequent up- dates can be infeasible due to computational or operational constraints. For example, retraining a large-scale recom- mendation policy after every user interaction may be im- practical in terms of both time and resource consumption. In this work, we focus on the batched variant of linear ban- dits, where policy updates occur only infrequently, rather than after every round.
larized G-optimal design problem:
A
X
2f T&T 2 x00)))))
Ve(Te) = I+ E
Ce
To. argmin max TEE,, #EAr-1
| vi(ee) 1.
Here, À E R and E (0, 1] are the regularization parame- ter and the exploration-exploiation rate for the f-th batch, respectively. The set D, denotes the space of all probability distributions over the arms in Ar-1
Batching as Limited Adaptivity. In batched linear ban- dit settings, the T rounds are structured into B disjoint butches:
|
{ AA
De TE E TR
Σ Tei 1
20
{1.... T} = 11+11, ....,,. 41] U... U [ tb)
Batch 1
Batch B
For the l-th batch, the algorithm is designed to approxi- mately match the batch size T - ity distribution used for arm allocation is a weighted combi- nation of σद and a distribution that assigns full probability to a single arm, given by
where to = 0, LB = T. and B is the total number of al- lowed policy updates. A batch is thus a contiguous block of rounds during which the agent must use fixed policy. In other words, within each batch, the agent is not able to update its policy, effectively deferring feedback from that entire batch until the end. Only at the end of batch É can the agent update its policy using the rewards collected from rounds 4 + to 4. Consequently, the agent has at most B opportunities to adapt its strategy over the entire horizon, rather than T'- in the fully adaptive setting.
The eventual probabil-
f2-1 E argmax (z, 0c-1). xEAr-2
Here, -7-1 is the estimated optimal arm based on the ob- servations from the (e-1)-th batch. If multiple arms satisfy the criterion, one is selected arbitrarily.
Challenges in Batched Decision-Making. The restric- tion to B policy updates (with B < T) necessitates a more careful balance between exploration and exploitation within each batch. Since the agent cannot adjust its actions mid-batch in response newly observed rewards, it must design an effective exploration strategy at the beginning of the batch. This strategy involves selecting arms in a way that both collects sufficient information to refine parameter estimates and maximizes the immediate rewards.
Given this probability distribution, the arms are pulled pro- portionally to their assigned probabilities. For notational convenience, we designate the first arm as the estimated optimal arm from the previous batch among all remaining arms. (Line 8).
Notably, BLAE does not enforce any fixed choice of cg (0, 1]. which provides both theoretical and practical flexi- bility in balancing exploration and exploitation. In particu- lar, setting c1 = 1 for the first batch is merely a concrete instantiation reflecting the lack of prior information; subse- quent batches can adapt oj as more data become available. This design ensures that the presence of o does not hinder performance or introduce undue complexity.
In the remainder of this paper, we focus on designing a batched linear bandit algorithm with as few updates as possible, while maintaining regret close to the best-known fully adaptive bounds.
After pulling arms according to the allocated probabilities, we update the regularized least squares estimator and the estimated optimal arm. (Line 11) Using the estimators Ó and 47. we then apply the following elimination rule to re- move suboptimal arms (Line 12).
4. Algorithm: BLAE
We introduce Batched Linear bandit Algorithum with Elim- ination (BLAE), whose pseudocode is provided in Algo- rithm [ As its name suggests, our algorithm BLAE sequen- tially eliminates arms and updates the available arm set A (1) ((Ab)))) after completing each batch l.
A =
f - Ac-1 (0c, 22 - x) S 5t
Before the start of the E-th batch, the algorithm determines the policy के- == iTa..... ..., TiAA I over the remaining arms in A to construct an effective sampling strategy for that batch (Line 6). This policy is computed by solving a regu-
Here, while the construction of the elimination threshold E, is crucial for our theoretical analysis (its order is spec- ified in Theorem | and the actual values are specified in Lemma D. to maximize practical performance, we use the
4

---

Optimal and Practical Batched Lincar Bandit Algorithm
Algorithm BLAE
5. Regret Analysis
1: Input: Arm set A, horizon T, regularization parameter
As we delve into the regret analysis of our proposed algo- rithm (Section we first present the standard assumptions used in the literature.
X, exploration-exploitaiio rates (ct ) elimination bounds {
2:
3: Initialize: batch + 0, time t- 0, arm set Ao +- A
5.1. Assumptions
4: while do
5: ! f+++;;
Assumption (Boundedness). |||| S for all x A and |00112
6: T + argmin m
maX I|lll in Eq.
7: for +
1,,,,..... 1,2,,,12,000
Ar-1l do
8:
Pull arm (11) repeatedly for the following times 26-1 {
Note that the boundedness is assumed without loss of gen- erality. If ||==|| S C and ||Ø* 12 I C' for some constant C, then the regret bounds would scale by factor of C. This is standard assumption in the linear bandit literature.
(0-ce)-1(1)(0)) A T T-1 2- 4-(1T x =--(7"=(000i + (1-c)) (1)
9:
10:
end for
The noise d) is a I-subgaussian random variable for all time steps E [T].
Assumption 2.
11:
Update batched regularized least squares estimator
Og and estimated optimal arm 17;
Similar to Assumption I the I-subgaussianity assumption ensures that the regret bounds remain independent of scale for analytical convenience. This is also standard assump- tion in the literature.
12:
Update A fI Ac-1 (0c, 27 x) {
Rename arms A + { = 21)), x (2)) (,,),..,(((Adl) :
14:
end while
bounds without simplification, resulting complex rela- tional expressions rather than straightforward forms.
5.2. Worst-Cas Regret of BLAE
Theorem 1 (Regret of BLAE). Suppose the BLAE algorithm is executed for total of T rounds with K arms. If the K² time horizon satisfies T 2 Q(max (d Kja K$ }), and given that 2 2, let
Finally, the algorithm reorders the remaining arms in the arm set such that the estimated optimal arm from the cur- rent batch is placed first, ensuring consistency with the in- dexing convention used in Line 8 (Line 13).
Et 0
V
2 2
(Iog(KT) A vd+
Batched Regularized Least Squares Estimation. We estimate 8* using regularized least squares estimator in batch-wise manner. After the completion of the f-th batch, the estimator are updated as follows
where X O(1) and c O(1), with ot (0, e 1. Then, the worst-case regret of the BLAE algorithm is upper bounded by
H
Σ ==
I + AI, O, - 8=1-1--
IsTa
R(T) ( (og(KT) A V log T) log log T)
= = K A AdVT)
A naive approach would be to apply the ordinary regular- ized least squares estimator for all S S 4.. However, due to policy updates, the noise terms 7)s for 1 S S t--1 influence the arm selection process in the b-th batch. To de- rive the concentration bound in Lemma] ! we require H to be independent of the noise terms 7/s used for estimator updates. This independence condition is not satisfied in the standard regularized least squares setting, necessitating a refined estimation approach.
Discussion of Theorem 1 Theorem 1 shows that BLAE achieves regret bound of Ö (VdT log K A dvT)), match- ing the best-known (and indeed minimax-optimall results for fully adaptive linear bandit problems. Moreover, BLAE operates with only O(log log T) batches, comparable to the lowest batch complexity among existing batched lin- ear bandit methods. Critically, this bound simultaneously covers both the large-K regime (K > M())) with (dvTT) regret and the small-K regime (K I O)ee)) with (VVIT log K) regret, thereby establishing the light- est known performance guarantees for batched linear ban- dits in both regimes. To our knowledge, this is the first time such matching lower bounds have been simultane- ously achieved under limited adaptivity.
While independence is maintained within each batch batch-i.e. i...,
among samples collected before policy update oc- curs-we adopt a batched version of regularized least squares estimator to ensure the necessary independence properties. Further mathematical details and the proof can be found in Section
5

---

Lemma establishes an upper bound on the uncertainty. measured by the Mahalanobis norm ||>|| for any arm in the f-th batch. Most G-optimal design methods used Optimal and Practical Batched Linear Bandit Algorithm
Central our result new techniques for regularized G-optimal design under batch updates (see Lemma B) alongside rigorous concentration bound that handles both batching and regularization (Lemmas[] and We also re- fine the construction of unit-sphere coverings to optimize batch-wise exploration (Lemma [ These technical contri- butions may be of independent interest for other batched (and potentially non-batched) bandit problems.
as defined above. For convenience, define
|| Bl .Be (I
Et == max x.yEAL-1
as it frequently used in regret analysis and also stated in Theorem [ Most existing concentration inequalities focus on individual arms. However, our arm elimination strategy explicitly accounts for the difference between an arm and the estimated optimal arm .ÿ. By constructing a concentration inequality based the difference between arms, effectively derive tighter upper bound compared to conventional inequalities that analyze individual arms independently. Intuitively, this approach leverages the fact that |a - y| S ||=|| + llvll. enabling a more structured and practical elimination process. Moreover, this result ensures that the optimal arm is preserved throughout the arm elimination process, while suboptimal arms are reliably removed with high probability. Consequently, for all arms available in the f-th batch, it can be ensured that the suboptimality gap satisfies As = (x* - =x, 00 s 28) with high probability.
5.3. Proof Sketch of Theorem
In this section, we sketch the proof of the worst-case regret bound in Theorem 1 and present key lemmas, with their detailed proofs deferred to the Appendix.
Lemma (Batch concentration with regularization). After the E-th batch (e 2 1), the following results holds. For any Re and 0 < 8 <
TP (lr, (er - )r) >> < (V2 5-1 VA)[ 21-6 8.
Lemma D establishes that the inner product between the estimation eгrоr and an arbitrary vector æ is upper bounded by the Mahalanobis norm |0]| with high probability.
Lemma (Joint concentration with regularization), Define the following terms
Lemma (Regularized G-optimal design). After the E th batch (f 2 1). the following results holds. For an exploratio--eppliiattoon rate ct in (0,
81 + [log2 logg T1)2
(0) = 2 log
+ +2VX,
(15/64)d-182
d
max ÆEAr11
||
26
(12(0) = V 2
8/(1 12 A [lo22 log2 TT)
+ VX,
dd +
C
ex(0)= = max 2.
|| - vllm= (0) A (6))
Here, is a constant within the interval (0, 1). Then, the following event holds with probability at least 1 - 8,
in bandit algorithms omit regularization and rely solely the
equivalence theorem (Kiefer & Wolfowitz 1960). However, similar to the argument in Lemma under an arm elimination setting, the informa- tion matrix He may not remain invertible without regu- larization. Thus, a refined analysis that explicitly incorpo- rates the regularization term is necessary. This lemma fur- ther demonstrates that we can derive even tighter upper bound the uncertainty compared to approaches that do not account for regularization. The exponential decay term T af_1 2 ensures that uncertainty decreases rapidly as the batch index E increases and the time horizon T grows, high- lighting the algorithm's 's adaptability to batch-wise updates. By leveraging the bound AS S 16)) which holds for all arms available the l-th batch with high probability. and applying Lemma we can effectively bound the ex- pected cumulative regret as described in Theorem
B 10 0. 10-00 00) s (E()), Vz, y E Ac-1]
n
Lemma 2 provides a high probability guarantee that the es- timation error remains tightly controlled across all batches and arm pairs. The term 3e1 quantifies the difference be- tween the batched regularized least squares estimator de and the unknown parameter 0*, which plays crucial role in establishing the regret bound of (dv'T) in the large-K K regime. Similarly, Sez captures the discrepancy between Óe and 0* from a different perspective, which is essential for deriving the regret bound of O (DVddIloo log K) K))n in the small-K regime. By defining (5) = (6) A (5) as the min- imum of these two terms, our framework seamlessly han- dles both regimes. This motivates the construction of (5)
6

---

Optimal and Practical Batched Lincar Bandit Algorithm
6. Why Many Existing Provable Batched Linear Bandit Algorithms Underperform in Practice?
thors claim [0'| < (6T)), the algorithm must caleulate arg A, (a,0) for each 0 E O' each batch step. creating tremendous computational burdens that far exceed what is tractable for real-world applications.
In this section, we examine why several recently proposed methods - strong theoretical guarantees- tend to underperform in empirical evaluations.
Lastly, Algorithm 1 in Zhang et al.] (2025) adopts a two- phase batch-splitting strategy similar to that of Ruan et al.) (02T]. thereby inheriting the similar limitations. As with its counterpart, the algorithm produces suboptimal policies in fixed-arm environments and incurs considerable compu- tational overhead from computing a G-optimal design at every round of the first batch, cost that grows rapidly when the action set is large or the time horizon T increases.
A recently proposed and provably efficient algorithm, Explore-Fstimate- Eitntttt--lmmminttt----ploe (E') by Ren et al. (2024). serves as an example of why theoretically sound methods in batched linear bandits underperform in prac- tice. Specifically, Ex suffers from two critical practical is- sues that lead to performance deterioration. First, E occa- sionally eliminates the optimal arm prematurely due to its climination strategy. E applies D-optimal design concen- tration bound from Lattimore & Szepesvári (2020), which assumes independence in the sampling process. However, E does not perform least squares updates in a batch-wise manner, thus it fails to properly account for the indepen- dence assumption required for the bound hold in the batched setting (see Section 4 As a result, this elimination constructed without the necessary constraints often leads to the premature elimination of the optimal arm.
Our runtime experiments Table T confirm that these ap- proaches (Ruan et al., 2021] Hanna et al.] 2023 Zhang et al.] 2025) struggle to scale efficiently even for mod- erately sized T and other problem parameters, rendering them impractical for large-scale problem instances. More- over, all three methods (Ruan et al.] 2021 Hanna et al.) 2023 Zhang et al., (025) assume that contexts are drawn independently and identically distributed (i.i.d).. In fixed- arm environments, the contexts remain identically dis- tributed but are not independent, violating this assumption and undermining the theoretical validity of these methods in our setting.
Second, the batch sizes of E are highly sensitive to the hyperparameter % where the third batch size scales with ((1g)))++7) When choosing relatively large values of y, as Ren et al. (2024) set in their practical set up, the third batch size often exhausts the entire horizon, leaving prac- tically no time to effectively exploit information learned in the third batch. Consequently, the algorithm relies only on information from the first two, relatively short batches. If suboptimal arm identification occurs during these early batches, this leads directly to linear regret.
More broadly, the combination of premature arm elimina- tion, extensive computational costs, and the lack of consid- eration for independence requirements in batched settings helps explain why methods that appear theoretically sound may struggle to deliver in real-world applications.
7. Numerical Experiments
7.1. Experimental Setup
Other algorithms also encounter significant challenges in practical evaluations of batched linear bandits. For in- stance, BatchLinUCB -DG (Ruan et al., 2021) splits each batch into two phases: the second phase depends on newly gathered context to refine the policy, a require- ment that proves ineffectual when arms are fixed across rounds. Our numerical experiments consistently show that BatchLinUCB-DG struggles to execute meaningful explo- ration, frequently failing to "double" the determinant of its information matrix and thus settling on degenerate (of- ten zero) exploration distributions. In addition, its mixed- softmax policy, which incorporates a G-optimal design at every round, incurs substantial computational overhead, thereby restricting its applicability to larger-scale prob- lems.
In this section, we empirically evaluate the performance of the BLAE algorithm. We measure the cumulative regret over T = 100, 000 time steps. The K arms and 0* are randomly sampled from d-dimensional uniform distribu- tion. The experiment is repeated 10 times, with the arms being independently resampled from the uniform distribu- tion in each run. We conduct experiments with the fol- lowing (K, d) parameter pairs (K, d) = (50. 5), (50, 10), (100, 5), (100, 10), (200, 5), (200, 10). (400, 5). (400, 10).
We compare the performance of BLAE with the previ- ously known state-of-the-arr algorithms: Explore-Estimane Estimate- Eliminate- (denoted by E Ren et al. 2024), Rarely Switching OFUL (denoted by RS-OFUL; Abbasi- Yadkori ct al. 2011). and the phased elimination algorithm with D-optimal design (denoted by PhaEl imD: Esfandiari et al.. For BLAE, we set the parameters as À = and ez = | for é. 2 1. This choice allows et to adaptively reflect the level of un-
Algorithm 3 in Hanna et al. (2023) addresses yet another dimension of complexity by transforming the contextual bandit into a non-contextual one through constructing a 7-
2021 Lattimore & Szepesvári
net e' over a bounded parameter space. Although the au-
7

---

Optimal and Practical Batched Lincar Bandit Algorithm
RS-OFUL
PhaFlimD
E
BLAF
40000
10
40000
10
Regret
Batch
10
Regret
Batch
10
20000
20000
10
10a
10
10
2000
50000
Time step
Time step
Time step
Time stop
(a) K 50,50040 d
(b) K = 50, = 10
RS-OFUL
PhaElimD
E
BLAE
40000
10
40000
10
Regret
Batch
102
Regret
Batch
10
20000
20000
10
10
10P
10
Time step
Time step
Time step
Time step
(c) ( 100, 5
(d) K 100, d 10
RS-OFUL
PhaElimD
BLAE
40000
107
40000
10
Regret
Batch
102
Regret
Batch
10a
20000
20000
0
10F
0
10a
20001
1000
(0000 s000 [0000)
20000
43000
09000
19000
100000
4000 (A00) 30000
20000
.0000
60000
10000 100000
Time step
Time step
Time step
Time step
(e) K 200, d 5
(f) K
200, d
10
RS-OFUL
PhaFlimD
E
BLAE
40000
10
40000
10
Regret
Batch
10
Regret
Batch
10
20000
20000
10a
10a
0.
10
10a
2000
5000
60000
40000
60000
Time step
Time stop
Time step
Time step
(g) K 400, d
(h) K 400, d 10
Figure 1: Regret and batch complexity over time for different values of K and d.
certainty based on the number of remaining arms, ensuring both flexibility and practical applicability. For E we con- figure the parameters identically to the practical setup in Ren et al. (2024). For RS RS-OFUL, we the switching pa- rameter C 0.5. For PhaElimD, sizes as T instead of g² to achieve better performance.
7.2. Experimental Results
For the experimental results, we present two types of fig- ures to summarize our evaluations. First, the average of cumulative regret (solid line) with its standard deviation (shaded region) plotted based on 10 independent runs. Second, the average batch complexity (solid line) is de- picted using the same 10 trials, illustrating how frequently each algorithm updates its policy.
design the batch
Algorithms proposed by Ruan al. (2021): Hanna al. 2023); ; Zhang et al. (2025) incur significant computational overhead; their runtimes are reported in Section F as expla- nation for their empirical inefficiency is presented in Sec- tion 6 Accordingly, we omit regret plots for these methods.
As illustrated in Figure I BLAE consistently and signif- icantly outperforms all other algorithms, cxhibiting both low cumulative regret and notable aubility--Srrpasinngg even RS-OFUL, which executes over 100 parameter up- dates, far more than BLAE. These outcomes confirm that BLAE not only achieves the tightest known theoretical guarantees but also delivers strong empirical performance,
8

---

Optimal and Practical Batched Linear Bandit Algorithm
thereby fulfilling its design objectives of near-optimal re- gret and minimal batch complexity.
versity.
Among recently proposed methods, E+ (Ren et al. 2024 is shown to attain minimal batch complexity (Figure I This advantage, however, comes at a cost in regret perfor- mance: the algorithm records the highest cumulative regret and shows marked instability. Minimizing the number of batches is therefore of limited value if the resulting regret is unsustainable. Across 80 independent experiments, E shows substantial performance variability due to its aggres- sive urm-elimination policy and sensitivity to batch size. As noted in Section 6 its elimination strategy fails to re- spect independence in the batched setting, occasionally dis- carding the optimal arm prematurely. In addition, the algo- rithm's s sensitivity the hyperparameter 7 often causes the third batch to consume almost the entire horizon, leaving little opportunity for exploitation. Our evaluation used the official implementation released by Ren et al. (2024).
References
Abbasi- Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24:2312-2320, 2011.
Abe, N. and Long, P. M. Associative reinforcement learn- ing using linear probabilistic concepts. In International Conference on Machine Learning, . pp. 3-11, 1999.
Abe, N., Biermann, A. W., and Long, P. M. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37:263- 293,, 2003.
Abeille, M. and Lazaric, A. Linear Thompson Sampling Revisited. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, vol- ume 54, pp. 176-184, PMLR, PMLR, 2017.
Overall, the superior empirical results of BLAE validate its unique advantage: couples a proven minimax-optimal re- gret bound with practical efficiency. This combination of theoretical optimality and consistently strong performance sets BLAE apart from prior batched linear bandit methods.
Auer, P. Using confidence bounds for exploitation- exploration trade-offs. Journal of Machine Learning Re- search, 3(Nov):397-422 2002.
Chu. W., Li, L., Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial In- telligence and Statistics, pp. 208-214. JMLR Workshop and Conference Proceedings, 2011.
8. Conclusion
We present a practical and minimax-optimal algorithm for batched linear bandits that unifies theoretical tightness and empirical efficiency. By integrating arm elimination with a regularized G-optimal design, method achieves Ö(VdT log K A dvT) regret in only (log log T) batches, matching known lower bounds for both large- K and small-K regimes. Extensive numerical evaluations confirm its superiority over existing methods, illustrating how our method bridges the gap between provable effi- ciency and empirical performance.
Dani, V.. Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. 2008
Esfandiari, H., Karbasi, A., Mehrabian, A., and Mirrokni, V. Regret bounds for batched bandits. In Proceedings of the AAAI Conference Artificial Intelligence, vol- ume 35, pp. 7340-7348, 2021.
Gao, Z., Han, Y., Ren, Z., and Zhou, Z. Batched multi- armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Han, Y., Zhou, Z., Zhou, Z., Blanchet, J., Glynn, P. W., and Ye, Y. Sequential batch learning in finite-action linear contextual bandits. arXiv preprint arXiv:2004.063: 2020.
Acknowledgements
Hanna, O. A., Yang, L., and Fragouli, C. Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. In The Thirty Sixth Annual Confer- ence on Learning Theory, pp. 1791-1821. PMLR, 2023.
This work was supported by the National Research Foun- dation of Korea (NRF) grant funded by the Korea gov- emment (MSIT) (No. R8-2002-NN071853 and RS-2023- 00222663), by Institute of Information & communications Technology Planning& & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2025-00263355) and by AI-Bio Research Grant through Scoul National Uni-
Jin, R., Simchi-Levi, D., Wang. L., Wang, X., and Yang, S. Shrinking the upper confidence bound: A dynamic product selection problem for urban warchouses. Man- agement Science, 67(8):4756 4771, 2021a.

---

Optimal and Practical Batched Lincar Bandit Algorithm
Jin, T., Tang, J., Xu, P., Huang, K., Xiao, X., and Gu, Q- AI- most optimal anytime algorithm for batched multi-armed bandits. In International Conference on Machine Learn- ing, Pp.
Zhang, Z., Ji, X., and Zhou, Y. Almost optimal batch-regret tradeoff for batch linear contextual bandits. In The Thir- teenth International Conference Learning Represen- tations, 2025.
PMLR, 2021b.
Jin, T. Xu, P., Xiao, X., and Gu, Q. Double explore- then-commit: Asymptotic optimality and beyond. In PMLR,
Zhou, Y. Lecture 14: Lower bounds for linear bandits, 2019. Scribed by Ali Bibak.
Conference Learning Theory, pp. 2021c.
Jin, T., Yang, Y., Tang, J., Xiao, X., and Xu, Op- timal batched best arm identification. Advances Neural Information Processing Systems, 37:134947- 134980, 2024.
Kiefer, and Wolfowitz, J. The equivalence two ex- tremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
Kirschner, J., Lattimore, T., Vernade, C., and Szepesvári, C. Asymptotically optimal information-direes sam- pling. In Conference on Learning Theory, pp. 2777- 2821. PMLR, 2021.
Lattimore, T. and Szepesvári, C. Bandit algorithmss Cam- bridge University Press, 2020.
Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual- bandit approach to personalized news arti- cle recommendation. In Proceedings of the 19th inter- national conference World wide web, pp. 661-670, 2010.
Li, S. Concise formulas for the area and volume of a hyper- spherical cap. Asian Journal of Mathematics Statis- tics, 4(1):66-70, 2010.
Li, Y., Wang. Y., and Zhou, Y. Nearly Aimimax-optimal regret for linearly parameterized handits. In Conference on Learning Theory, pp. 2173-2174. PMLR, 2019.
Lu, Y., Xu, Z., and Tewari, A. Bandit algorithms for precision medicine. In Handbook of Statistical Meth- ods for Precision Medicine, pp. 260-294. Chapman and Hall/CRC, 2021.
Perchet, V., Rigollet, P., Chassang, S., and Snowberg, Batched bandit problems. The Annals of Statistics, 44 (2):660-681, 2016.
Ren, X., Jin, T., and Xu, Optimal batched linear bandits. In International Conference on Machine Learning, pp- 92391-42416 PMLR, 2024.
Ruan, Y., Yang. J., and Zhou, Y. Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Sympo- sium on Theory of Computing, pp. 74-87, 2021.
10

---

Optimal and Practical Batched Lincar Bandit Algorithm
Appendix
A. Proof of Lemma 1
The proof Lemma relies on the following two technical lemmas. Here, we assume that subgaussian random variables have zero mean.
Lemma 4, Let X be a o-subgaussian random variable. Then for any 2 O, the following concentration bound holds
P(X 2 6) Se
Proof. Let À > O. By Markov's inequality and the definition of subgaussianity, we have
PP 2 E) (e AX e S Ble de S X2g² -Ae
To optimize the upper bound, we À ,2 Substituting this value of X, we obtain the desired inequality.
Lemma 5. Let X be o-subgaussian random variable, and let X1 and X2 be independent 01 ou-uaaaaussa and d2- subguussian random variables, respectively. Then, the following properties hold
(a) For any E R, cX is cub-auaaaasii
(b) X1 + X2 is of + o2 subgaussian.
Proof. By the definition of subgaussianity, for any R. have EleAx] $ x²0²
Substituting with et proves (a) as
follows
Mex)] = (je S sea)20?
3²07
2303 Using the indepen-
By the definition subgaussianity, for any E I, we have E[eAX1] S e x and E[cAXo] s x dence of X1 and X2, we can write
2d 2202 =
x²(of
E Ble = Ele E[c
Thus, (b) is also proved.
Proof of Lemma I. For any Rd, substituting Or with the batched regularized least squares estimator and expanding rs. obtain
(x, 0: - 0*) = -xx H
TyYs - 6*)
s=t--11
(x, H
Fy (1: 0" + 17)) - 0*)
s=t-111
(x, H
Es + (He xT)Ø*) 8*)
s=t-1+1 +1
(x, H
FzN]s \0
s=1-111
Σ
(a, H.HH,'oal 2.aMa M(x, H, 000)
(1)
s=1-111

---

Optimal and Practical Batched Lincar Bandit Algorithm
The matrix Hg is independent of the noise terms (m [RsJs +1- (1 14 s-t-1111111 are mutually independent. According to Lemma the term
Furthermore, these 1-subgaussian random variables
-llTaxh (a, H
2.)' is
Σ
(ar, H HH,,xxh xx)² subgaussian.
Applying the concentration inequality from Lemma 4
this subgaussian random variable yields
(3)
P
(x, He
2, S
2 2
(x, H₂ xx,²
Hz'r0)
2 - 8.
(2)
-=t--1t1
For the second term in (1), we apply the Cauchy-Schwann inequality, yielding
| |
<x, H 00) S ||>||| =,:10=1110011 ||0| S
(3)
VA
Combining inequalities (2) and (3) with equation (1), we obtain
P (z, (z,0s- 0-) S
2 log
(ar, 11/ax.) + VAIIrlAA,'
21-6.
1=
To obtain a more concise bound, we observe that
(x, H Hx S of H
Σ
H == x² H HeH ||01| Iaat + AI
1+1
smte 1+1
This completes the proof of Lemmal
P
(x. 0e -00-03--1 5
(
1
+ vx)
|| |1lll15'
2 1 1
8)
B. Proof of Lemma 2
The proof of Lemma relies on the following five technical lemmas.
Lemma 6. LL 20100) Let Aa denote the surface area of an d-dimensional hypersphere of radius I, and let A denote the surface area hyperspherical cap d-dimensional sphere of radius 1. Then, the following result holds for é (0, 71 where (a, b) is the regularized incomplete beta function
Ad
d
A
ssia &
2
2
Lemma 7. (Abeille & Lazaric 2017) For any integer d 2
r( dd+1
2
<
V
T +1)
Lemma 8. For any (0,1), 1), there exists finite cover C' C 8d-1 such that for all Sd-1, there exists Ce with ||z - yll S S. and [Cyl < 2nd (52 - 544 d-1 Here, Sd-1 = {x E Rd ||||| = 1} denotes the (d - -)ddimensional unit sphere Rdd and d 2.
12

---

Optimal and Practical Batched Lincar Bandit Algorithm
Proof. Let X RR. A subset C' X is called an (-cover of X if X U Bş(x). Similarly, (-packing of X is subset P C X' such that for any distinct 2; y E P, ||ar yll Ç. We define N()) the minimum cardinality of Ç-cover of Sd-1,, and (() as the maximum cardinality of an (-packing of g Specifically,
(()) [in C is an Ç-cover of 5d-13, M()) max : Pis an Ç-packing of sd-13.
Now, let P be an arbitrary (-packing of Sd-1, For any distinct x, y E P. we have gg(x) (z) (v) O. Therefore, write
L PEP
Bg (2) c s
(4)
From (4) and Lemma 6 and the arbitrariness
( (-packing P. we obtain
As
2
2
M(S)
A
I (2 (2) 1 1211- 4)
d-1 (
Using the monotonicity of + (1 (1-t)- - on (0, }), along with < we derive
<<² - 4 < for C E (0, 1), and applying Lemma
2B d-1
(3 f)
d
B
2 ()
dd1
222
2B( d-1 .2
10 -0- $)
1 (1 t)
dt
2B( d-1
2 :2)
(0 : + dt
(d-1)B( d-1 2
- (62- ((2 $ 1-1
(d-1)v=
I(
(<2 ")
I())
d/r
1(()))
(C2 $ d=l
r(
V
2 ) 1=1
Here, (2 b) is the incomplete beta function and B(a, b) is the beta function. Since M({) < (5² - < oo, there exists a maximal (-packing Pg of 5d-1, this case, Ps is also an (-cover of 5d-1, implying N(C) S M().
Thus, combining these results completes the proof:
N(C) S M(S) < V2rd
(52 - +)
Lemma 9. After the l-th batch (e 2 1), the following bound holds for any 0 < ( < 1 and d 2 2 with probability at least
1 1-6 6
00 x (id - logg -<x-<x)) log( V2rd
vA
1-c
13

---

Optimal and Practical Batched Lincar Bandit Algorithm
Proof. If 02 02, the lemma is trivial. Thus, we only consider the where Of o Oz.
Let X ! 0.) Since |||||| 1, it follows that X E ESt-1, where g the unit sphere in IR.
|1,-0, lleee
Let Cc C 5d be the Ç-covering set given in Lemma and define the event
E 3x Oe 8.1. (13 x, 02 0.) >
+ VA
2 log
Using the property || a=l = |||||| 1 for all E Sd-1, and by applying Lemma | we have PP S 8. When the event E does occur, the following inequality holds
|6 - 102---l1m,. = max (H² G2 0.)
zc5d-1
= max min ( (x - y), 02 - -0.) ) + (11, y. 02 0.) #ES*-1 DEC;
s max min |l0e - 00 0111 || ull ( y. 02 0.) = yECs
(Gsl
< <lIδ: 0-11 +
2og (1) + vx
4 A5² - -ct) 2logg
V2ndd
S cll0: 0- 11 +
(d- (d-1)log
+ VV.
Therefore, we prove Lemma
Vid 1) log( 4c2 <<==<=) + 2 log(
V2rdd
+ VA
10 1m 5
21-8.
1 1-
Here, E (0, 1) is a tunable parameter. Although one could optimize over Ç. we fix Ç = 0.5 for simplicity, as this choice affects the results only up to a constant factor. We nevertheless retain Ç as a symbolic variable in the subsequent analysis to preserve generality; readers may safely substitute ( = 0.5 throughout. For convenience, we define
max ||x ulli
z,yEA
Lemma 10. After the f-th batch 2 1), the following result holds for all x. y E Ae-1 with probability at least
(xx 0: 60) s Me. Be(8 8log log, T))
Proof. Using the Cauchy-Schwarz inequaaal and Lemma 9 the following result holds for all x. y E Ae-1 with probability
at least 1
10 u vl? (v (d 1)log( 3p
4 + 2 2log
2v/ard
+ V
[x y, -0)0- | vlla, 1 10
1-6
Since ||x - ulpp, S M3, we obtain
VM (Va- log( (रक-))) + 2 log( 2v2xd vā
5
P (x 0e - -
Vx, y E Ac-1
21- ---2
(5)
1-
14

---

Optimal and Practical Batched Lincar Bandit Algorithm
Next, by applying Lemma to the (1 pairs of æ; E Ar-1 such that (xr 0e 0*) 2, E Ag-1, the following holds with probability at least 1 -
know that for all
2220gg
- - vā || -ylm,,,
1s= y. 0, 8111 =
8
Since ||x - yl | S
Mr we obtain
P (x u 1' VMe (1220gg (Ac-112- Ac-2l
+ vx
21-3 5
Ve, E Ac
(6)
2
Using the definition of (e(6), we calculate 3e(6 + 81logz log, 17) as
V 1) logg 40t ca) ) 2log( 2222rd VX
1 -
Be(6 öflog, logg M]-
A
22og
+ V2
1 1-5
Combining the result from (5) and (6), we prove Lemma 10
(1(x= y, de 8y S /Me Be(6 + 8 öfloge log, TQ), Vx, y E Ac-)) 21-6.
Proof of Lemma 2. At the [log2 log2 -1 -th and (1 + [log2 log2 -1)-th batch, the number of arm pulls satisfies
T
Dogg TT T gloogg long
2 lugg
T
2
Thus, the total number of batches B is bounded by
B S 1+ [log, log2 T
Let E. {1(x= y. 02 8-) s (E()), Vx,y y E A By Lemma 10
we have
5
P 1+ [log, log, T
By definition, F= F= Ee, the following holds
B8
P(E =
E3 < P(E)) 1 + [lgg log, T"
56.
Therefore, we prove Lemma 2
P(E) > 2-
C. Proof of Lemma 3
The proof of Lemma relies on the following four technical lemmas.
Lemma 11. Af R + Rdxd is d x d matrix, then the following holds
d det (es))(()) = trace (adi(A) (A) d
ds A(8)
ds
15

---

Optimal and Practical Batched Lincar Bandit Algorithm
Proof. Recall that (e) can be expressed polynomial in the entries diy of A. Concretely,
det(A) = sgn (1) ... Ad,r(d)
BESa
where the sum is over the symmetric group Sa and sgn(o) denotes the signature of a. Consequently, the partial derivative of (e)((A) with respect to particular entry aij involves only those terms in the polynomial that contain dgj- From the definition of the adjugate, the (j, i)-th entry of adj(A) is precisely the cofactor corresponding to a.y. Concretely,
i det((A) = (adj(A))
Da.j
Next, let us regard A as dependent on a variable 5, so that each entry aij becomes aiy(s) By the chain rule, we have
(de( d asy(s)
det(A(s)) E
dais
I5tJad
Substituting (7) into this sum yields
det del( (((() E (adi(A))
(áe A(s))
ds
ji'
1st.sa
Notice that the above expression is precisely the trace of the product adj(A) ds A(s). Indeed, writing matrix products in terms of their indices shows that
(adi(A)) 5s (d)(())) = trace adj((A) d
Σ S
ds A(s)
Therefore, we prove Lemmal
d det det(A(s)) trace adj(A) A(8)
ds
ds
Lemma 12. Let f Di - R be defined as
|d
f(a)) = log(ddtt = log det
I
Σ i=
Te
T
C2
Then f is concave function..
Proof. Define T {X Raxd X 0}, and let g: T - R be given by
g(X) log log(det(X))
The gradient of g(X), using (7) and symmetry of X, is computed as
adj(X)T adj(X) x
Vx9(X)=
det(X)
det(X)
Using Lemma 11 for any symmetric matrix U E Iddxd the Hessian of g(X) is computed as follows
d²
[ =
log(det(X + sL'))
ds²
d
trace(adj(X + s(')U)
ds
det(X st)
trace((X + -UU)
ds ===0
trace( (X sU) - U( + -t)
ttrcce(X -UX-e(--UX--U)
16

---

Optimal and Practical Batched Lincar Bandit Algorithm
Since X-1 is positive definite and U is symmetric, have
= trace( X x trace(X- -ox--)) -raace((x- --X- 4) 2 0.
Thus, the Hessian is negative semidefinite, which implies that g concave for X Next, observe that Vi DD + T is an affine map. Since composition of a concave function with an affine map concave, follows that f(Te) g (TTe)) concave. Specifically, for any Te, tee De and
[0, 1]. we have
g(Vi(ATe (1 A)ff)) ((AV((m)) + (1 A)V((Fe)) 2 Ag(V((Te)) + (1 A)g((V((Fe))
Therefore, (TTE) is concave function of ree-
Lemma 13. Let f Rdd - R be concave and differentiable function, and let C C Rdd be a non-empty convex set. If x' argmax (()), then the following holds
( Vf(x')) 50, VoEC.
Proof. Define æss) sz +1 s)x* for [0, 1]. Since C is convex, have a(s) E C' for all E [0, 1]. Let 6(s) == f(((s)) for [0, 1]. Because x" is the maximizer of f(x) over C, follows that
Φ(0) f(=)((())))))))) f(x(s)) ((s), Vs E [0, 1].
Thus, d(s)'s right derivative at 0 must be non-positive
0 ž ('(0+) (x-+))=\((())((---))>)) =²).
Therefore, prove Lemmal 13
(xr - V((²))) so, V.
Lemma 14. After the f-th batch (E 2 1), the following bound holds
de
max 2EAc-1
||a1|i0(=2) S
dd
+ T 2f
Proof. Let us define f(TT)) = log(det(V((Tt)). We compute the gradient of f(Te) component-wise
a
(VS(Te)):
(og(())(V((TTe)
Ina
det dV
det((V(FFT)
Oe
Using Lemma we obtain
(((())))) (ee(TV((T) trace adT((V((TT)) (Te))
trace (Ve(Te) (Ve(Te)
1 .T 2 16-1 (1)) (0)
trace(Ve(TT.)
=T 24ا ||00 (1 [1(
Since VI(TT) is a linear function of iT. the function f(TT) is continuous. Furthermore, as the domain of f is the compact set D,, the Weierstrass theorem guarantees the existence of a maximizer T/ E urgmax,,ed, f(r)). Additionally, it is well known that matrix inversion is a continuous operation on the set of invertible matrices, which implies that Ve(TT)) is a continuous function of ny. Since the maximum of finitely many continuous functions is also continuous and the set De
17

---

Optimal and Practical Batched Lincar Bandit Algorithm
compact, the Weierstrass theorem ensures the existence of minimizer σ. argmin R,DD, max ( Since De is compact and f(Te) is concave by Lemma
12 Lemma
13 implies
0 N (Vf(T)) ne Tt), VTT E De.
Expanding this inequality yields
A--il
1A--1l
0 0
(V((T)))TT - n(aa)
Σ
1 T 2
(0.00)
( (Tes - T/s), VTT E De
i=1
When we set me to be Dirac distribution (O..... 1, ,,....00) 0) and divide by T 2f 2 we obtain
|
0 2 ||x
|,:00)
( Tt/j
==1
(+)) -110100
trace Thyy 2,10 2011 V=(m)/)1)
Adc-il
Téj T 2 ا(02ا00 V((xT))11
T
trace
A ()(a(+)))1)
= =I1a000 (B2(()))) - T
trace (race((VV ((Ve(T))
21 T of
trace(1 A - )
-
Ci
26-1
XT
=|00|0 (B dT
trace (acce(V(77)) (=(z))-1)
ct
Let X1, N2. Na be the eigenvalues of Vi(TT)). By the Cauchy- inequality, we have
d2
d²
trace trace(Ve(r)) (Ve(o()))
X
(race(Ve(
1==1
Using Assumption]
I
we obtain
A 1l
trace (V((T))) = trace
+
T 2
i=1
AA--l
dA
Σ
22
|12
C2
i=1
z
T
C2
which implies
de
trace trace(Ve(TT)) (V((T()-2)
(9)
d) + T x C2
Combining (8) and (9), we obtain
& X
dei
| 12
((())))
5 d7
d) + T
C2
dd
18

---

Optimal and Practical Batched Lincar Bandit Algorithm
Since this inequality holds for all 1 sis A and प. minimizes maxze | over Dz, where
मे E argmin max EeD mEAr-1
[ 1
we conclude Lemma [4
deg
max zEAr-1
|
S max || sEAr-1
|
S
d'
111 Proof of Lemma 3.. Define or IT [aiaa vaza(?),.... ...., /a (ollAr-11) be a matrix whose columns are the vectors v vaja(i) (1), Then, the following holds
(GeT + (1- oe) [11) - The for 1 i S |Ae-1), and let X ==
Ar-1l
A
H₂ = +
Σ
[ x
(CeTT +1 ce) 111(0))=00001 =eVe((T)
Σ
axx (0)
=cVVl(T)) =ceVi(mt)+Xx'
Using the Sherman-Morrisee Morrisoo---oobbbryyy formula and the positive definiteness of (1 + x V2(V((T))) - we have
HE Vi(
1 Vi x(I x(I -x X"( 1
Vi(aT))
Cz
Ce
C2
Therefore, we prove Lemma
d
max | ||=1|2,,- zEAc-1
S max
1 oe
|
veloz))
-1 dd T
2
C2
D. Proof of Theorem 1
Proof of Theorem 1. Define the nice event E as
E n 1(0 v, -000 S ee, Vo, y E A
By Lemma [] this nice event occurs with high probability
P(E) 2 T
We decompose the cumulative expected regret using the nice event E as follows
T
R(T) =
E 5 P(E))
Σ x xx,
+
(e" - Iz, 0-) 1 IPEE)
Using Assumption I and the Cauchy-Schward inequality, we obtain
(x- - -x,, 0²) < [x= - xτ, 0")
(x0 ,,>' I + k 8*)
|| ||@01| + || |011
2.
(10)
19

---

Optimal and Practical Batched Lincar Bandit Algorithm
Therefore, the following bound cumulative expected regret holds
R(T) 2T P(F))
Σ fx-
Ic.
0r)
(P(F)
T
& 0(1) + E
Σ
(x
Tiz, 0-) E
From now on, we assume that E occurs. We claim that x² E Ae for 1 SE $ B. We prove this by mathematical induction. For since Ap. we obtain
(01, fj - x²) (0] 0" + + , 0 - x²)
(01 0 2 x²) + 10 24 x²)
S E1
Therefore, x² E Ai holds, establishing the base case. Now assume x² A Then
27 - -x)) (0p 0r + 0 27 x²)
= (0e- 0", 31 x² + (0" 23 - x²))
< Et
Therefore, x= E Ae holds. By induction, we conclude that x² E Ar for all S E For each suboptimal arm xx( x²), define la min A, 25,} as the first phase where the suboptimality gap of arm larger than 25g, If suboptimal arm r( x²) not climinated in the first &z 1 batches, after the & batch, we obtain
(0c, 22, - x) 2 1 x=" x)
(0 8r 0r x² x)
(0c, f", ,, x) + 10",x" x))
x²
2 -E + A
> Etz
Therefore, we know suboptimal arm x* x²) will be eliminated in the first l, batches
4 Ae.. Vx E Ao
Thus, for é 2 2, the suboptimality gap of any arm included in A is smaller than 25 in l-th batch, where
A, S 2 Vr E Ac-1.
(11)
Using the triangle inequality, obtain the following bound for l 2
Mr max ||x vlli,,'
S max (||=11 1 |1Bll H, .)2
A.
< max 4||xr 1||
(12)
zEAL-1
20

---

Optimal and Practical Batched Lincar Bandit Algorithm
Let Regret, denote the cumulative expected regret of the E-th batch when E occurs. Combining (11) and (12), obtain the following bound of cumulative expected regret
B
B Σ (T xf
Regretz
S
+
2=
2 Mi-1 (v (d- 1) 4 + log /2xd + flog2 log, T)) + VX)
(1 5)/ 2 + (AAc-1))
4 max || (V(a- - 1) log (5o-5r) + 2 log( 21' 2mddl + [logg log, Tl)) + v2) sEAL-2
(1 <) (T 2 x + (Ae-1l)
B (VT(( - + +(ee-1)) (V(d 1) log( (<ं--)) + log(27 22d((1 + [log2 loga T1)) + vA
2=
(1 (1- dA + -T z cL-1
Here, we use
5 S M, (d- 1) log( (,ج-ς)) + (2 + [loge log, T))) + vx
Using 2> 2(K3) and B < 1+ [log, log, T7, derive the following bound for the cumulative expected regret incurred during the batches with f 2 2
(Vo2 +loog[ vd
(T +K)
B
B Σe o
Regret, =
11111 7
2=2
V +++1
2--1 (VT + KT
(Voz + d dloog log log T) va)
Σ o
11-1-1 --
t=2
dI
--
[B 1)(TT KT 8) d dlogT T
0
dT 28
28
+1
(VdT + VaKT- (KKT+t/d + log 7 log log
VIT- +
= o (VaT /d log T log T)
Ö(dVT)
We can derive a similar upper bound using an alternative bound for Et,
5 Mr. (V2log (T(A))
Ae- Togg log, T()) + vx)
21

---

Optimal and Practical Batched Lincar Bandit Algorithm
This leads the following bound for the cumulative regret after the second batch
B
B
Regret
+ (Ae-1))2EE-1
2
2=
B
2/ M1 ( + (ee-ll (v (Vllog(T((AL (1 + [log2 logz T)) + Vx)
2=2
B
(T (+a + Ae-2l) ( (22lg[(T|Ae22) + [log log2 T7)) + v2)
4 max
| Hi-
zEAr-2
2m
8 4V + (e-i1) ( (2lloT Ac-2 2 log, log, T))) + vZ) +
2=
d) d TA+T== 26-1 2 Ct-1
Using T' ) and B < 1++
[log2 log, T7, we derive the following bound for the cumulative expected regret incurred
during the batches with l 2 2
Vd(T of x + KK)
(Vog(( KT log log T) + +1)
Regret,
Σo
0
2=
8=2
Vd+T
(VdT+ + VOKT 2-11
B
Vool KT log log T") +
Σ
0
2=2
dI
[B () + VaKT
2)
log(KT log log T) +11
28 dT
28
+1
(VdT+ + VakT $ ) log(K')) log log T
0
VdT
O ( ( dT LoT'log(A)) KT) log log T
-((v d' log K)
Thus, the regret except for the first batch is bounded by
B
Regret, = O(VdT (V (og(KT) A Vd
log log = Ö6 d' log K A ddT)..
Using (10) and 2 Q2
K² the cumulative expected regret for the first batch can be easily bounded follows
(d log K Kid
Regret, S 2(VV + KK = O log K A dvT).
Thus, the worst-case regret is given by
R(T) = OVV Vd + [og+log]] T) log log T) Ö(VdT log K A dVT).
E. Additional Experiments
E. Runtime Comparison Analysis
We provide a runtime comparison with batched linear bandit algorithms in Ruan et al. (2021): Hanna et al. (2023); Zhang al. (2025). The experiments were conducted with 50 arms and a feature dimension of 5, where all arms and the
22

---

Optimal and Practical Batched Lincar Bandit Algorithm
unknown parameter O sampled from normal distribution. Under the same experimental setting, the BLAE algorithm 10 runs when T 100,000. In contrast, shown in Table 2 the algorithm in Ruan et al. (2021) requires average of 464.2 seconds for T = 5000, while the algorithm in Zhang et al. (2025) takes an average of 717.8 seconds for I = 5000, demonstrating their limitation in large-scale problems. Furthermore, the algorithm in Hanna et al. )023) faces severe computational challenges due to the construction of @' as mentioned in Section [ The 1000, O' would contain approximately 10t5 vectors, making the algorithm infeasible even for moderate values T. Due to these computational constraints, we were unable to measure its runtime.
requires average of 0173 seconds
size of O' is ( meaning that for
From this experiment, we conclude that the batched linear bandit algorithms proposed in Ruan al. (202I): Zhang et al.
2025) Hanna et al. 2023) impractical for our setting.
Table Average runtime (seconds) over 10 runs for the normal distribution setting with K 50 and d 5.
Runtime
Time step
Ruan al.
2021
Hanna
2023)
Zhang al
2025
BLAE (Ours)
T 500
89.2
10000
57.1
0.26
T 1000
132.4
10000
88.9
0.35
5000
464.2
10000
717.8
0.55
E.2. Additional Comparisons of Regret and Batch Complexity
In this section, we provide additional experimental results for the instances where arms are randomly sampled from a Gaussian distribution, following the same format as in Figure Similar to the uniform distribution case, we repeat each experiment 10 times, independently resampling the arms from the Gaussian distribution every run. We observe similar trends under the Gaussian distribution setting. As shown in Figure the gap in mean regret is even more pronouneed compared to the uniform distribution case, further demonstrating the practical superiority of the BLAE algorithm. It consis- tently outperforms all other algorithms, achieving the lowest mean regret and the highest stability, even in comparison to RS RS-OFUL, which utilizes over 100 batches. In contrast, the algorithm proposed in Ren et al. (2024) demonstrates the weak- est empirical performance and notable instability over 80 independent trials, particularly resembling the behavior observed under uniform distribution case.
RS-OFUL
PhaElimD
E
BLAE
50000
50000
40000
10a
40000
Regret
30000
Batch
Regret
30000
Batch
20000
10a
20000
10a
10000
10000
10
10a
Time step
Time step
Time step
Time step
(a) K 50, d =
(b) K = 50, = 10
RS-OFUL
PhaElimD
BLAE
50000
50000
40000
10a
40000
104
Regret
30000
Batch
Regret
30000
Batch
20000
10a
20000
10a
10000
10000
0-
20000
(000)
10000
50000 100000
20000
43000
60000
3000
100000
2000
400))
50000
100000
20000
40000
60000
90000 100000
Time step
Time step
Time
Time
(c) K 100, 5
(d) K= 100, d
23

---

Optimal and Practical Batched Lincar Bandit Algorithm
RS-OFUL
PhaElinD
E
BLAE
50000
50000
Regret
30000
Batch
Regret
30000
Batch
20000
10a
20000
107
10
10a
20000
Time step
Time step
Time step
Time step
k- 5
(d) = = 200, d = 10
RS-OFUL
BLAE
50000
50000
40000
10a
40000
10
Regret
Butch
Regret
Batch
20000
10a
20000
10a
10000
10000
10P
40000 60000 Time step
Time step
Time step
Time step
(c) = 400, d 55
(d) K = 400, 10
Figure 2: Regret and batch complexity over time for different values of K and d
24


Reviews:
[{"review_id": "3dmFuPppK8", "reviewer": "Reviewer_ohEo", "summary": "The paper tackles the well-studied batched linear bandits problem and provided tight regret bounds in the small and large arms (K) closing the gap in the upper and lower bounds. Experiments show that they perform well on simulated datasets over the existing algorithms.\n\nOverall: The paper is clearly laid out with both the theoretical contributions and the experiments showcasing the benefits. In particular, care has been taken to highlight the issues with existing approaches and how the current approach solves them.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for taking the time to review our paper and for providing thoughtful and valuable feedback. We greatly appreciate your recognition of our work and your constructive comments. Below, we address each of your comments and questions in detail:\n\n---\n### **Experimental Results in the Small-$K$ Regime**\n\nWe thank the reviewer for this suggestion. We conducted experiments in the small-$K$ regime with $K = 2, 4, 8, 16$, and the detailed results are in Figure 1 of Section 1 in [this link](https://tinyurl.com/3m6f4v5n).\n\nAs shown in Figure 1, BLAE consistently outperforms existing methods in the small‑$K$ setting. While $E^4$ (Ren et al., 2024) performs competitively for $K=2$, this trivial case is straightforward for any algorithm. Therefore, apart from this trivial case, our results confirm that BLAE remains superior across all small-$K$ regimes considered.\n\n---\n### **False Elimination of Optimal Arms in $E^4$ (Ren et al., 2024) as a Function of $K$**\n\nWe appreciate the reviewer’s insightful question. To investigate whether the frequency of mistakenly eliminating the optimal arm in $E^4$ (Ren et al., 2024) increases with $K$, we conducted experiments across a range of $K$ values—from small to large regimes. Each experiment was repeated 20 times, and we tracked the rate at which the optimal arm was falsely eliminated. Detailed results can be found in Table 1 of Section 2 in [this link](https://tinyurl.com/3m6f4v5n).\n\nThe data in Table 1 clearly indicate an increasing trend in the elimination rate as $K$ grows. This trend helps explain why $E^4$ (Ren et al., 2024) performs worse than other batched linear bandit algorithms, particularly in large-$K$ regimes.\n\n---\n### **Potential Applications of Refined Analysis in Other Settings**\n\nWe appreciate the reviewer raising this valuable point. Our refined analysis indeed applies naturally to broader settings, including the **pure exploration** scenario. In pure exploration, the primary goal is to accurately identify optimal arms within a given budget, without explicitly focusing on cumulative regret. Our approach, which combines a regularized G-optimal design with an arm elimination strategy, efficiently discards suboptimal arms with high probability, significantly improving the accuracy and efficiency of exploration.\n\nFurthermore, since **best arm identification** is a widely-studied and applied setting—where exactly one optimal arm must be correctly identified—our refined analytical methods directly apply here as well. Specifically, our algorithm’s ability to consistently maintain the optimal arm with high probability demonstrates its practical utility for reliable best-arm selection.\n\nThus, our theoretical refinements meaningfully contribute both to general pure exploration and specifically to the best arm identification problem.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, lemma 1, 2, 3 and Theorem 1", "experimental_designs_or_analyses": "Yes, section 7.1", "relation_to_broader_scientific_literature": "Summarized in Table 1, pretty comprehensive.", "essential_references_not_discussed": "Not that I am aware of", "other_strengths_and_weaknesses": "Pros:\n\n(i) The provided regrets are tight and match the established lower bounds for the problem. Both the communication rounds O(loglog T) and the regret bounds of O(d\\sqrt(T), \\sqrt(dTlogK)) are optimal. \n(ii) The main issue is the refined technical analysis of the batched least squares regression problem and the lack of independence across batches. \n(iii) The experiments show that the regret is much better for the BLAE algorithm not only in terms of the mean but also variance in sharp contrast with E4. This is further explained due\n to the elimination of the optimal arm. \n\nCons:\n\n(a) It would have been interesting to show the results in the small K regime and that it is only in the large K regime, it is suboptimal.", "other_comments_or_suggestions": "NA", "questions_for_authors": "(1) Are there experiments showing that Ren et al is competitive in the small K setting with the BLAE algorithm? The explanation that the best arms are getting eliminated (Ren et al) could be further explored to show that this happens increases as a function of K?\n(2) What are the other settings where the refined analysis could be of interest as alluded to in the paper?", "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": "YmpCN1POdU", "reviewer": "Reviewer_Aajf", "summary": "In this paper, the authors study the linear bandit problem under limited adaptivity, known as the batched linear bandit. They propose a novel batched algorithm that integrates arm elimination with regularized G-optimal design, achieving the minimax optimal regret in both large-K and small-K regimes for the first time, while using only loglogT batches. Finally, the algorithm demonstrates low computational overhead and strong empirical performance, outperforming state-of-the-art methods in extensive numerical evaluations.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for reviewing our paper and providing valuable feedback. We appreciate your recognition of our work and your constructive comments. Below, we address each of your comments and questions in detail:\n\n---\n### **Performance in the Large $K$ Regime**\n\nWe thank the reviewer for raising this important point. We conducted additional experiments with much larger $K$ values, with detailed results available in Table 2-4, and Figure 2 of Section 3 in [link](https://tinyurl.com/3m6f4v5n).\n\nAs shown in Table 2-4, BLAE is the fastest among optimal algorithms, with runtime comparable to that of suboptimal algorithms. Moreover, Figure 2 demonstrates that BLAE consistently achieves significantly lower regret and maintains stable performance even as $K$ becomes very large, confirming the scalability of our approach in large, finite action spaces.\n\nRegarding infinite (continuous) action spaces, we clarify that our theoretical guarantees (and many others) and algorithmic design assume a finite action set. Thus, extending the current method to a continuous action domain is outside the scope of this paper.\n\nTo our knowledge, prior studies have not provided experimental evaluations for very large values of $K$ (e.g., $K = 1000, 2000, 5000$). Thus, we strongly believe that our extensive experiments sufficiently demonstrate that our algorithm offers superior performance and robustness, positioning it as the most effective solution for large-$K$ regimes. We would be more than happy to perform further experiments if needed.\n\n---\n### **Experimental Performance of $E^4$**\n\nWe thank the reviewer for noting the discrepancy in $E^4$'s results. While Ren et al. (2024) theoretically established a sub-linear regret bound, our experiments exhibited (near-)linear regret behavior.  \nWe emphasize that we used the exact implementation officially provided by Ren et al. (2024).  \nWe identified two primary reasons for this empirical performance discrepancy:\n\nFirst, $E^4$ occasionally eliminates the optimal arm prematurely. Table 1 of Section 2 in [link](https://tinyurl.com/3m6f4v5n) shows how frequently false elimination of the optimal arm occurs over 20 independent experimental runs.\n\nSecond, the batch size in $E^4$ is highly sensitive to hyperparameter $\\gamma$. In particular, the third batch size scales as $O((\\log T)^{1+\\gamma})$. When choosing a relatively large value of $\\gamma$ (e.g., $\\gamma = 10$, as in the Ren et al. (2024) setup), the third batch size often exhausts the entire horizon, leaving practically no time to effectively exploit information learned in the third batch.  \nConsequently, the algorithm relies only on information from the first two, relatively short batches. If suboptimal arm identification occurs during these early batches (as frequently observed), this leads directly to linear regret. In contrast, BLAE's $\\ell$-th batch size has order $O\\left(T^{\\frac{2^{\\ell}-1}{2^{\\ell}}}\\right)$, avoiding this issue.\n\nWe conducted additional experiments by carefully tuning the hyperparameter $\\gamma$ for $E^4$ from 10 down to 0.99, to their advantage. The results of these additional experiments, presented in Figure 3 of Section 4 in [link](https://tinyurl.com/3m6f4v5n), confirm that careful tuning of $\\gamma$ leads to sub-linear regret behavior. However, we also observe that reducing $\\gamma$ for the sake of regret performance **significantly increases the number of batches**.  \nHence, there is a clear tradeoff with regard to the control of $\\gamma$ in $E^4$.\n\nMoreover, even after the tuning of $\\gamma$ in $E^4$ for the sake of regret performance, the performance of $E^4$ still results in noticeably worse regret performance compared to BLAE (Figure 3 in [link](https://tinyurl.com/3m6f4v5n)). Thus, the tuning leads to increased batch complexity although the regret performance increases. Despite careful tuning for $E^4$, overall numerical performances in both regret and batch complexity of $E^4$ still show clearly inferior practical performance compared to BLAE.\n\n---\n### **Computational Complexity Analysis and Scalability**\n\nWe thank the reviewer for this insightful question. To the best of our knowledge, all prior works on batched linear bandits have not provided theoretical complexity analyses, as exact theoretical complexity analyses for comparisons are challenging due to various optimization subroutines in each algorithm. Therefore, any derived theoretical complexity bounds would likely be overly crude and may not be suitable for comparisons for their true computational performance in practice.\n\nTo evaluate computational cost, we provided empirical runtime experiments in Appendix E and conducted additional extensive evaluations (see Table 2-4 of Section 3 in [link](https://tinyurl.com/3m6f4v5n)).\n\nOur empirical results address scalability when $K$ is very large. Even at large $K$, our experiments show that our method significantly improves computational efficiency compared to existing optimal algorithms.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The proof sketch part is convincing, the proof looks correct to me.", "experimental_designs_or_analyses": "The experimental result is good in general, while I have several concerns. \n\n1. All the choices of $K$ are not very large. I am wondering what will be the result (especially the runtime) if $K$ is chosen to be very large or infinity (continuous action space).\n \n2. I am not very convinced of the experimental result of $E^4$. In Ren et al, a sub-linear regret upper bound is derived. However, in the experiment in this submission, it seems to have linear regret. Is there any contradiction? Will tuning the failure probability improve the result?", "relation_to_broader_scientific_literature": "This paper studies the batched linear bandits. The algorithm in this paper is the first to match the lower bounds for both small K and large K at the same time.", "essential_references_not_discussed": "NA.", "other_strengths_and_weaknesses": "Strengths:\n\n1. Matching the two lower bounds at the same time is a very nice result.\n\n2. The algorithm is simple and computationally efficient in experiments.\n\n3. The presentation is clear in general.\n\nWeakness: \n\n1. Is there any theoretical analysis on the computational complexity? How does it scale if $K$ is very large or even infinity?\n\n2. Please refer to the points mentioned in the experimental result part.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "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": "CjcSSsZiP9", "reviewer": "Reviewer_bpRV", "summary": "This paper studies the batched linear bandit problem. The authors propose a new algorithm for this problem and show that this achieves near optimal regret. Compared to other algorithms which also achieve near optimal regret in this problem, the authors claim that their proposed algorithm is more computationally efficient and performs better in practice. To illustrate this, experimental results in simulated environments are provided.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time and review. However, with all due respect, there appear to be some misunderstandings, which we  sincerely hope to clarify in our response.\n\n---\n### **Batched Learning Setting**\nIn the batched linear bandit setting, the learner chooses both the number of batches and when to update parameters. This is **the standard setup in the literature** (Esfandiari et al. (2021), Ruan et al. (2021), Hanna et al. (2023), Ren et al. (2024), Zhang et al. (2025)).  This is the key aspect of the batched linear bandit problem because one wishes to design an algorithm that can update parameters as infrequently as possible while still achieving provably optimal regret.\n\n---\n### **Consistency of Parameter Choice in Theory and Experiments**\nWe confirm that **the choice of $\\varepsilon_\\ell$ is consistent across theory and experiments**.  Its order is defined in Theorem 1 and rigorously maintained throughout the paper, including experiments. The precise definition of $\\varepsilon_\\ell$ is given in Lemma 2, which depends on parameter $\\varepsilon$ (distinct from $\\varepsilon_\\ell$). $\\varepsilon$ is an arbitrary constant in (0,1) (chosen as 0.5 in all experiments which is theoretically valid). Our algorithm BLAE employs identical parameter choices in both theory and practice, ensuring optimality in both domains. **There is no \"difference in hyperparameters for theory & practice.\"**\n\n---\n### **Experimental Results for Larger Dimension $d$**\nWe conducted additional experiments with larger $d$ values. Results appear in Figure 4 of Sec. 5 in https://tinyurl.com/3m6f4v5n. These demonstrate that regret difference increases with $d$.\n\n---\n### **Runtime Comparison of the Main Algorithms**\nWe conducted additional runtime experiments with larger arm counts $K$. Results in Table 2-4 of Sec. 3 in https://tinyurl.com/3m6f4v5n demonstrate that BLAE is the fastest among optimal algorithms, with runtime comparable to suboptimal algorithms even in very large-$K$ settings.\n\n---\n**Lemma 1**: \nOur Lemma 1 adaptation explicitly incorporates the regularization term to achieve our specific bound, which is crucial to our analysis. While sharing structural similarities with standard results, its subtle differences merit attention.  We will include the relevant previous result related to Lemma 1 in the revision (e.g., Chapter 20 in Lattimore & Szepesvári (2020)).\n\n---\n### **Effect of Different Choices of Epsilon on Results**\nAs mentioned, the elimination threshold $\\varepsilon_\\ell$ is defined based on parameter $\\varepsilon$ (distinct from $\\varepsilon_\\ell$). In all experiments, we followed the theoretical guideline for $\\varepsilon_\\ell$ and $\\varepsilon$.\n\nSince theory allows $\\varepsilon \\in (0,1)$ to be chosen arbitrarily, we tested sensitivity to different $\\varepsilon$ values. Results in Figure 5 in https://tinyurl.com/3m6f4v5n show BLAE remains robust across various $\\varepsilon$ values. Note again that **in all of our experiments the parameter choices satisfy the conditions of the theoretical results.**\n\n---\n### **Clarification on Hyperparameter Selection for Other Algorithms**\nAll experiments were conducted fairly. For $E^4$ (Ren et al., 2024), we used their exact public implementation. All baseline algorithms used theoretically suggested hyperparameter values from previous literature, while BLAE’s hyperparameters followed our theoretical results, ensuring fair and transparent comparisons.\n\n---\n### **Significance of Contributions**\nTo understand our contributions, it's essential to recognize the limitations in existing batched linear bandit literature:\n\n- **Ren et al. (2024):** Optimal regret only for small-$K$ regime, exhibit poor practical performance (see Figure 1 of our paper).\n- **Abbasi-Yadkori et al. (2011) and Esfandiari et al. (2021):** Higher batch complexity, making them theoretically suboptimal.\n- **Ruan et al. (2021), Hanna et al. (2023), and Zhang et al. (2025):** Impractical due to excessive runtimes (see Table 2 of our paper).\n\nThe key motivation for batched linear bandits is computational efficiency without sacrificing regret or batch complexity. In contrast to previous methods, **BLAE is the first algorithm that simultaneously achieves provable optimality in both small-$K$ and large-$K$ regimes, while maintaining practical efficiency in both regret and batch complexity**.  \nTherefore, our contribution addresses a critical gap in existing literature, aligning with the fundamental motivation of batched linear bandits.\n\n---\n### **Clarifying small-$K$ and large-$K$**\nIt is NOT a matter of whether existing algorithms work or not. The existing algorithms \"work\" in both small-$K$ and large-$K$ regimes. But, their optimality was **proven only in one of the regimes**—never in both. In contrast, **BLAE uniquely achieves optimality simultaneously in both regimes**.\n\n---\nWe hope our responses clarified the key points and respectfully ask that the evaluation reflect our contributions.", "claims_and_evidence": "- From section 3, it is not clear if the batches are given to us or if they are something the learner can pick. \n- The choice of epsilon seems very important but is only given in the Theorem 1 in terms of its order. For experiments, it seems a different value of epsilon is chosen, and it is not clear if this choice satisfies the conditions of the theorem. Therefore, it is not clear if the exact same approach is optimal in theory and practice.", "methods_and_evaluation_criteria": "- It would be good to see results for larger d – it seems that maximum d=10 is actually quite small.\n- It would also have been good to show a run time comparison of the main algorithms used in the experiments.\n- The run time experiments in Table 2 of the appendix are interesting, but it would good to make it obvious from the main paper.", "theoretical_claims": "The proof of Lemma 1 seems fairly standard (unless I am missing something). Discussion & references of similar proofs would be appreciated.\n\nThere were several steps in the proofs I did not understand:\n- Not clear where number of pairs comes from in715.\n-  In 891, why can we pick pi this way?\n-  Where does the assumption T>Omega(K^5) come from? (1071)\n-  Why is there a second bound in 1099? – I think this is to get the different results, but the structure of the proof could make it clearer.\nI also did not understand lines 912,933-944,1050, 1077. More justification should be provided.\nI think probably the proofs are correct (and I do not necessarily need detailed explanations of all these steps in the rebuttal, I just thought it might be helpful to point out the parts which were difficult to follow).\n\n\nI don’t think the proofs of Lemmas 4,5,11,13 are necessary to include as they are standard results that have been proven before in the literature. References to existing proofs are fine to include instead.", "experimental_designs_or_analyses": "- It would be good to see results for different choices of epsilon. In particular, how does choosing epsilon according to Theorem 1 alter the results? \n- It seems there are hyperparameters of other algorithms as well, but it is not clear how these have been chosen. Was the same procedure used for BLAE as well as the other algorithms? It seems that for E^4 the parameters were configured according to theory, which does not seem to be a fair comparison.", "relation_to_broader_scientific_literature": "There is a good discussion of related work, although the analysis should be related to similar analyses in related work.", "essential_references_not_discussed": "na", "other_strengths_and_weaknesses": "- One concern is the size of the contribution. I think the introduction does not do a sufficient job explaining why the work in this paper is solving an important question. \n- Another concern is the difference in hyperparameters for theory & practice. The authors claim that their algorithm is effective for both, but seemingly requires different tuning for each (unless I have missed something).", "other_comments_or_suggestions": "It would be helpful in the table to explain whether each algorithm works in the ‘large’ or ‘small’ K regime in Table 1. Since one contribution of this paper seems to be an algorithm which works in both regimes, it would be good to easily be able to understand what regiemes existing works cover.", "questions_for_authors": "1)\tFairness of experiments in terms of choice of hyperparameters of prior work\n2)\tChoice of hyperparameters – are the same ones used in theory and practice?\n3)     Importance of contribution", "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": "Vm4Fs0icuu", "reviewer": "Reviewer_o6Aa", "summary": "The paper introduces BLAE, a new algorithm for batched linear bandit problems. The central challenge in batched learning is balancing exploration and exploitation within discrete batches, as frequent updates may not be feasible in real-world applications. BLAE combines arm elimination and regularized G-optimal design to achieve near-optimal regret bounds while maintaining practical computational complexity.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time. However, with all due respect, we are very concerned by the current assessment. We sincerely hope to establish some common grounds with our response.\n\n---\n### **On Computational Cost**\nTo our best knowledge, all prior works on batched linear bandits have not provided theoretical complexity analyses, as exact theoretical complexity analyses for comparisons are challenging due to various optimization subroutines in each algorithm.\n\nFor fair comparisons of computational cost, we provided empirical runtime experiments in Appendix E and conducted additional extensive evaluations (Table 2-4 in https://tinyurl.com/3m6f4v5n). Our experiments show that **our method significantly improves computational efficiency compared to existing optimal algorithms.**\n\n---\n### **Batch-wise vs. Fully Sequential**\nObviously, even optimal *batched* algorithms will underperform *fully sequential* ones due to limited information in batched settings. Thus, direct comparison is inherently unfair, as the problem settings are fundamentally different.\n\nNevertheless, per your request, we conducted additional experiments comparing batched algorithms with the fully sequential LinUCB. Results (Figure 6 in https://tinyurl.com/3m6f4v5n) clearly show that the regret difference between BLAE and LinUCB is the smallest among existing batched algorithms, with competing batched methods exhibiting significantly larger performance gaps.\n\n---\n### **Regularization Parameters and Elimination Thresholds**\nThe reviewer's comment is incorrect. The regularization parameter $\\lambda_\\ell$ is explicitly stated in Theorem 1 as $O(1)$ (set to $\\lambda_\\ell = 1$ in experiments). The elimination threshold $\\varepsilon_\\ell$ is explicitly stated in Theorem 1 and precisely defined in Lemma 2.\n\n---\n### **Real-world Datasets?**\nRegret evaluation in bandit literature typically relies on simulations since offline datasets may not contain feedback for all counterfactual actions that an algorithm can take. Thus, absence of real-world datasets is typically not considered a weakness, particularly for a theoretical work.\n\nNevertheless, we conducted extra experiments based on real-world dataset *MovieLens*. The results (Figure 7 in https://tinyurl.com/3m6f4v5n) confirm that BLAE consistently outperforms existing methods, validating its practical effectiveness.\n\n---\n### **Assume Batch-wise Independence?**\nNo, our proof **does not assume** \"batch-wise least squares estimation independence across batches,\" irrespective of regularization. Independence is achieved (rather than assumed) solely through our batch-wise design.\n\nThere appears to be a clear misunderstanding. This is serious because it may present challenges to the reviewer in evaluating our main results. We sincerely would like to ensure we are on the same page.\n\n---\n**Elimination efficiency?**   We are unaware of any standard notion of \"elimination efficiency.\" Could the reviewer rigorously define what is meant by this term?\n\n---\n**Ablation?**\nAltering batch size is unnecessary, as it is proven optimal batch complexity. Additional evaluations on varying regularization  $\\lambda_\\ell$ are provided. (Figure 8 in https://tinyurl.com/3m6f4v5n).\n\n---\n### **Novelty**\nWe strongly rebut \"incremental contribution\" comment.  The use of G-optimal design or arm elimination in itself should not diminish novelty. By that standard, many impactful papers using optimal design would have been rejected.\n\nTo highlight a few of our contributions briefly: our refined analysis (Lemma 3) significantly improves exploration strategies beyond standard G-optimal design. We derived a new bound for this. Existing concentration inequalities in arm elimination inherently depend on $K$, making them suboptimal in large-$K$ scenarios. In contrast, our novel analytical framework utilizes efficient coverings of the unit sphere, providing sharper, more general regret bounds. Crucially, our proposed elimination strategy attains a unified optimal regret bound of $O(d\\sqrt{T} \\wedge \\sqrt{dT\\log K})$ using only $O(\\log\\log T)$ batches. Please refer to our paper for more contributions.\n\n---\n### **G-optimal Design**\nA key advantage of our algorithm is that we compute the G-optimal design only $O(\\log\\log T)$ times across $T$ rounds. Thus, given that computing optimal design requires at most $O(Kd^3)$, the average computational complexity due to G-optimal design in our algorithm is merely\n$O\\left(\\frac{K d^3 \\log\\log T}{T}\\right)$, which tends to zero as $T$ increases. This highlights a crucial benefit of our batched update.\n\n---\n**Suboptimal in Large-$K$ Cases**\nThere might be a misunderstanding. Existing methods being suboptimal in large $K$ case is not about \"misidentification of the best arm\" in large $K$. Rather, these methods always yield $K$-dependent regret, even for large $K$, but ours don't (see Table 1)\n\n---\nWe hope our responses clarified the key points and respectfully ask that the evaluation reflect our contributions.", "claims_and_evidence": "Yes, most claims made in the submission are supported.\nHowever, \n\n1. The authors argue that prior methods require excessive computation, but no formal computational complexity analysis is presented. \n\n2. Theoretical bounds support the claim, but there is no empirical comparison between \"batch-wise estimation\" vs. \"using all past data\".", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria (e.g., regret, batch complexity) are well-chosen for the problem of batched linear bandit learning.\n\nHowever,\n\n1. The paper does not discuss how regularization parameters or elimination thresholds are selected.\n2. No comparison with fully adaptive (non-batched) methods like LinUCB. While non-batched methods are not direct competitors, it would be useful to show how much performance is sacrificed by batching.\n3. No real-world dataset tested.", "theoretical_claims": "The theoretical claims in the paper are largely well-supported by the proofs provided.\n\n1. The proof assumes batch-wise least squares estimation is independent across batches due to regularization. However, this assumption lacks explicit justification, and a more rigorous bound on the impact of past information loss on regret would be helpful.\n2.  The batch complexity proof seems correct under typical conditions, but it would benefit from a more explicit discussion of elimination efficiency in large-K cases.", "experimental_designs_or_analyses": "1. The paper does not provide extensive evidence of BLAE's performance on real-world datasets with more complex dynamics and noise, particularly when the author mentions that other batch linear Bandit algorithms perform poorly in practical applications, especially in large-scale scenarios.\n2. No comparison with fully adaptive methods (e.g., LinUCB).\n3. Batch complexity is explicitly measured; but no runtime/memory usage comparisons.\n4. Needs ablation study on batch size, regularization, and elimination strategy", "relation_to_broader_scientific_literature": "The problem of linear bandits has been widely studied in the literature. The BLAE algorithm builds on this foundational work by considering the batched learning scenario, where updates are made periodically (rather than after each round). This shift to a batched setting allows for more efficient exploration and the possibility of reducing computational overhead while still maintaining a low regret bound.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Other Strengths:\n\n1. The comparison with E4 and RS-OFUL shows that BLAE consistently achieves lower regret and fewer updates per batch.\n\n2. Develop batch-wise optimal design strategies that efficiently allocate exploration efforts and can be generalized to both small-K and large-K settings.\n\n3. Introduces a novel concentration bound accommodating both batching and regularization.\n\nOther Weaknesses:\n1. I believe this paper makes an incremental contribution. The combination of G-optimal design and arm elimination is a classic approach, and even the use of regularized G-optimal design is not particularly novel. Achieving $O(loglogT) $ batch complexity in batched learning is also quite a standard result. It would be helpful if the authors could highlight the difficulties in the proof, particularly the challenges associated with unifying the large-K and small-K cases.\n2. The computational cost of solving G-optimal design in batched settings is not analyzed.", "other_comments_or_suggestions": "1. In small-K cases, eliminating suboptimal arms is straightforward. However, in large-K cases, elimination could lead to misidentification of the best arm if not enough data is collected. The paper could further clarify why earlier methods, e.g.,   (Ren et al., 2024), failed to achieve this bound in the large-K setting.\n2. A brief discussion of why batch-wise estimation does not significantly degrade performance (or an empirical comparison with full-history least squares) would be useful.\n3. While the theoretical proof is rigorous, an intuitive explanation of why batch complexity reduces from $O(\\log T)$ to $O(\\log \\log T)$ would help readers unfamiliar with batched bandit theory.", "questions_for_authors": "1. The paper highlights that traditional regularized least squares methods rely on all past time steps for parameter updates, but early noise can affect future arm selection. To mitigate this, BLAE uses a batch-wise approach with regularization to ensure parameter updates within each batch are independent. My concern is the feasibility of this approach—relying on a single batch may discard valuable information from earlier batches. Is there theoretical or experimental support for this batch-wise update method, and how does the algorithm balance using only one batch of data while potentially losing useful information from earlier steps?\n\n2. Does BLAE sometimes eliminate the optimal arm too early? Reporting how often the best arm is mistakenly eliminated would provide insights into the method’s robustness.\n\n3. How does BLAE scale computationally for large-K settings?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the batched linear bandits problem, and proposes the BLAE algorithm to solve it. The key design of BLAE is arm elimination with regularized G-optimal design and the algorithm achieves the minimax optimal regrets in both large-k and small-k settings. Although some reviewers still have concerns in experiments, I find this submission technically solid and interesting. Therefore, I recommend weak acceptance. Finally, authors are encouraged to write professionally and tune down the tone in communication with reviewers in the future.
Decision: Accept (poster)