Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits
Authors: Zihan Zhang
Xiangyang Ji
Yuan Zhou
Venue: ICLR 2025 Poster (2025)
Keywords: contextual linear bandit
online batch learning
Primary area: learning theory
TL;DR: We establish near-optimal batch-regret trade-off for contextual linear bandit problem.

Abstract: We study the optimal batch-regret tradeoff for batch linear contextual bandits. For this problem, we design batch learning algorithms and prove that they achieve the optimal regret bounds (up to logarithmic factors) for any batch number $M$, number of actions $K$, time horizon $T$, and dimension $d$. Therefore, we establish the \emph{full-parameter-range} (almost) optimal batch-regret tradeoff for the batch linear contextual bandit problem. 

Along our analysis, we also prove a new matrix concentration inequality with dependence on their dynamic upper bounds, which, to the best of our knowledge, is the first of its kind in literature and maybe of independent interest.

Published as a conference paper at ICLR 2025
ALMOST OPTIMAL BATCH-REGRET TRADEOFF FOR BATCH LINEAR CONTEXTUAL BANDITS
Zihan Zhang
Xiangyang Jil
Yuan Zhou
ABSTRACT
We study the optimal batch-regret tradeoff for batch linear contextual bandits. For this problem, design batch learning algorithms and prove that they achieve the optimal regret bounds (up to logarithmic factors) for any batch number M, number of actions K, time horizon T, and dimension d. Therefore, we establish the full-puurameter-runge almost optimal batch-regret tradeoff' for the batch linear contextual bandit problem.
Along our analysis, we also prove a new matrix concentration inequality with dependence on their dynamic upper bounds, which, to the best of our knowledge, is the first of its kind in literature and maybe of independent interest.
INTRODUCTION
Online learning and decision decision-making is an important aspect of machine learning. In contrast to the traditional batch machine learning where the learner only passively observes the data, an online learner may interact with the data collection process by deciding on which data point to query about. On one hand, sequentially making active queries may fully utilize the power of adaptivity based on the observed data and help to achieve better data efficiency. On the other hand, in many practical scenarios, it is also desirable to limit these queries to a small number of rounds of interaction, which helps increase the parallelism of the learning process, and reduce the management cost and the total time span. In light of this, the batch online learning model, which is a combination of the two major aspects of machine learning, has recently attracted much research attention. has been shown that for many popular online learning tasks, very small number of batches may achieve nearly minimax-optima learning performance, and therefore it is possible to enjoy the benefits of both adaptivity and parallelism.
To understand the impact of the batch constraint to online learning and decision-making problems, in this paper, we study the optimal batch algorithms for the linear contextual bandit problem. In a linear contextual problem, the learning algorithm observes a context (also referred to as a context set as usually have context vector for each candidate action) at the beginning of each time period, and the expected reward of each candidate action is determined by a hidden linear function of the context. The learning algorithm has to learn the linear function and maximize its total reward over all time periods. The readers may refer to Section for the detailed problem definition. The linear contextual bandit problem widely studied due its simplicity and abstraction (via the context) for the personalized treatment in decision- peciiion-mmkinn,... enabling plenty of real-world applications such as advertisement selection, recommendation systems, and clinical trials.
One practical reason that calls for the batch online learning model is due to the expensive policy deployment and communication cost. Large-scale online advertisement or recommendation systems (Li et al. 2010) may have to take a long time or pay expensive overhead cost to update their policies. In many distributed or offline systems (such as designing and updating the policy for autonomous vehicles or robotic arms), such an overhead cost becomes even more significant. During the execution of the policy, we usually may not be able to monitor the process (e.g., the data collected from the environment) in real time, due to the high communication cost and latency in the distributed (or large- scale) system. Similar challenges arise in medicine and clinical trials. The price of implementing a
Paul G. Allen School of CSE, University of Washington. Email: zihanz4
edu
I Department of Automation, Tsinghua University. Email: xyji i 8t sinhuu edu.cc cn Yau Mathematical Sciences Center, Tsinghua University and Beijing Institute of Mathematical Sciences and Applications. Email: yuan-zhcuee i inhuaa edu.cn

---

Published as a conference paper at ICLR 2025
new policy can be costly due to the inherent risks in healthcare, which limits the adaptivity of the deployment method. In such cases, the learner seeks to minimize the number of policy updates under steady environment, making the batch learning framework with stochastic contexts particularly well-suited.
In the batch online learning model, refer the time of each policy update the beginning of a batch. The learning algorithm may decide the policy only based on the data collected from the previous batches, and the data collected from the current batch may only be available the end of the batch. Due to the non-real-time natural, the learning algorithm also has to decide the length of each batch when the batch begins, without any information from the current batch.
We formalize the above intuition and define the batch complexity of the linear contextual bandit problem as follows.
Definition (Batch complexity). For a linear contextual bandit problem with time horizon T, we say that the batch complexity of learning algorithm is (at most) M in the, if the learner decides length T₁ and a policy n (a policy a mapping from the context space to the set of distributions over all candidate actions) before the learning process starts, and executes steps (which corresponds the first batch). Based on the data (context sets, played actions and the rewards) obtained from the first T2 steps, the learner then decides T2 and T2, and executes T22 for T2 time steps (the second batch). The learner repeats the process for M times/batches. In general, at the beginning of the k-th batch, the learner decides Tk (the size of the batch) and TT based the data collected from the first (k- - 1) batches. The batch sizes should satisfy that Σk=1
in the first Ti time
M Ts -T
Naturally, there is tradeoff between the batch complexity and the regret performance in batch online learning. There have been quite few recent works studying such relationship for multi-armed bandits (Perchet et al. 2016) Gao al. 2019 Estandiari al. (02T). Gao al. (2019) proved optimal regret bound for every number of batches and show that M Olog log 7 batches suffice to achieve the
minimax--ppimaa regret without the batch constraint. Han et al. (2020); Ruan al. (202T) studied the batch algorithms for linear contextual bandits. While Han et al. (2020) studied a special case of
the problem where the contexts follow Gaussian-type distributions. Ruan et al. (2021) provided an algorithm for all context distributions. In particual, Ruan et al. (2021 showed that M Olog log T')
batches suffice to achieve the minimax-optimea regret without the batch constraint]
While the exact batch-regret tradeoff for aamlid bandits is relatively better understood (and arguably easier to study), the optimal tradeoff curve for linear contextual bandits is more challenging and remains open.
In this work, we address this question on the exact batch-regret curve and prove the optimal regret (up to logarithmic factors) for batch linear contextual bandits for the full range of the problem parameters Below, we summary our contributions and comparison with the related works.
1.1 OUR CONTRIBUTIONS
We summarize our contributions and technique ingredients as below. For more detailed overview of the high-level ideas, we refer the readers to Appendix 3
Recall that Gao et al. (2019) showed that for multi-armeds bandits, the optimal regret using at most
M batches is at the order of 7'a-2 M (ignoring the polynomial dependence on other problem parameters and the poly-logarithmic dependence on T). For batch linear contextual bandits, we establish a similar (but slightly trickier) tradeoff. More specifically, we design Algorithm [ (in Section 4 and prove the following regret upper bound.
Theorem 2. Let be the dimension of the feature space and K be the number of candidate arms. For any T > d and M > 1, Algorithm 7 may at most M batches and its regret RT is bounded by
2-- é min {T's 2- M44 de 2 M42 T MIx da 2-1 min ( K, d) 2- (.-M1T) MHH) 1)
1-2-M+2
9-M-1
Botth the O(log log I') bound in (Ruan et al 2021 and our work (as well as (Han et al. 2020 focus on the trechastc-connext case of linear contextual handits, which is the most technically interesting and practically useful setting of batch linear contextual bandits. Please refer Section T.2.1 for more discussion.
2

---

Published as a conference paper at ICLR 2025
Note that the regret upper bound in Theorem 2 takes the minimum between two terms. When T is comparably large (c.g.. T' 2 mid d]2 2 - ) the second term in our upper bound is smaller, and its asymptotic dependence on T matches the optimal bound for batch multi-armes bandits (Gao
al. 2019 2
On the other hand, when T is relatively small (c.g.. T v O( (K, d)2- =)))))))) )),
simpler analysis would kick in to give a better regret bound, which results as the first term. We refer the readers Appendix [ for full proof.
When there are no constraints on the number of batches, it is well known that the Manimmx--optima regret is / log K x poly log I' (see, e.g.. (Dani et al. 2008
Chu et al. 2011 Li al. 2019)).
Ruan et al. (2021) showed that with only M log log 7 + batches (the logarithms are of base 2). their batch algorithm may match the regret performance (up to logarithmic factors) as the no-batch-constran
setting, The following simple corollary of our Theorem 2 recovers the main result of (Ruan al. 202I). Moreover, the batch algorithm in (Ruan al., 202T) only works for
T 2 (2(d while in contrast, our Corollary 3 works for every T 2 (and note that T < d the trivial scenario).
Corollary 3. For and M [log log(T)) + 1, the regret of Algorithm iis Rr Ō(VTd).
While the two-phase regret curve in Theorem may seem completely due to technicality, it surpris- ingly turns out to be exactly optimal. In Appendix C we complement Theorem 2 with the following lower bound.
Theorem 4. Fix any K K22 T d. and any batch number M 2 1. For any learning algorithm with batch complexity M, there exists a linear contextual bandit problem instance with dimension d and K arms, such that the expected regret Ry is at least
1-2-M-2 Rr 2 ( min (T2-2-M44 2-2 T 2-22- 2- min K, d) 2- 1)
M
We note that the above upper and lower bounds match (up to factors logarithmic in T', d. and K) for all M & [log log T7 and all non-trivial parameter settings for T, d, and K. When M > [log log T7, by Corollary 3 our Algorithm [ already achieves the unconstrained minimax optimaal regret (up to logarithmic factors). Therefore, we achieve near-optimal regret bounds for batch linear contextual bandits under all non-trivial parameter settings.
We also note that the Q(VKT= XTT) regret lower bound established by Gao et al. 2019) for 1-2-(M-1)
K-arm M-batch multi-armed bandits, and the 12 T (M- regret bound by Han
al. (2020) for d-dimensional M batch linear bandits with Gaussian contexts. If we treat multi-armed bandits as a special case of linear contextual bandits with K = d arms with orthogonal features, the lower bounds Gao et al. (2019) and Han al. (0200) are weaker than our Theorem 4 especially in This gap demonstrates that intrinsic additional difficulty of the batch linear contextual bandit problem with general context distributions.
the case < T < d min K, dd
In the analysis, we require a stronger matrix concentration inequality to address the challenges posed by dynamic upper bound. As independent contribution, introduce new matrix concentration inequality (refer to Lemma 20 in Appendix [ to avoid the dynamic upper bound.
1.2
ADDITIONAL RELATED WORKS
1.2.1
LINEAR CONTEXTUAL BANDITS
The linear contextual bandit problem (Abe & Long 1999 Auer et al. (002) studies the bandit problem where the actions are associated with (known) features and their mean rewards are defned by an (unknown) linear function of the associated features. Compared with the multi-armed bandit problem, the linear structure on features could help the learner to infer the mean reward of an action given the observation on the other actions, and therefore enables the possibility to achieve regret upper bounds independent from (or weakly dependent on) the number of actions.
2 However, this does not mean that the batch linear contextual bandit problem is casier than hatch mumti- bandits, the dependence and h is worse
3

---

Published as a conference paper at ICLR 2025
There are generally two types of problem settings studied about linear contextual bandits: adaptive contexts and adaptive contexts. In the non-adaptive-come context setting, the context sets are independent from all other randomnesses (including the randomnesses in rewards and used by the algorithm). One can also think of this as that the contexts are fixed (by an adversary) before the
learning process starts. In this setting, the optimal minimax regret bound is O dT min d, In K ) up to poly (T) factors (Auer et al., 2002 Abe al. 2003 Dani al. 2008 Chu et al. 201 I
Abbasi- Yadkori et al.) 2 Li et al. 2019). In the adaptive-coniext setting, the context sets are
chosen by an adaptive adversarial, where the context sets at any time step may depend the outcomes
and the learner's 's decisions in previous time steps. In this setting, the problem becomes harder for the
learner. To the best of our knowledge, the state-of-the-art regret upper bound for the adaptive-context setting is ((d//I((KT)
(Abbasi- Yadkori et al. 2011
In this work (as well as the most related works (Han et al., 2020 Ruan et al. 2021; Zanette et al. 202T) on batch linear contextual bandits), we focus on particularly useful case the non-adaptive- context setting, namely the stochastic contexts. In this case, the context sets at each time step are independently generated from a pre-defined (but unknown) distribution D. In many real-world applications such clinical trial and recommendation system, the patients customers can often be viewed as independent samples from the population and therefore stochastic contexts are a natural abstraction of these practical scenarios. On the other hand, (Han et al. (2020) has shown that even in the non- ran--aapptve-coneee setting, in the worst case, many as (2(TT) batches are needed to achieve
any VT -type regret, which is less useful practice.
1.2.2 BANDIT LEARNING WITH LIMITED ADAPTIVITY
Batch learning fits into the broader learning with limited adaptivity framework that recently attracts much research attention due to its potentially lower computational cost and close relation to distributed and parallel learning.
The number of batches is natural measurement of the adaptivity needed by the learner. Besides the above mentioned works (Perchet et al., 2016 Gao et al.) 2019) (for batch multi-armed bandits) and |uan et al. (202I) (for batch linear contextual bandits), Han et al. (2020) studied batch linear contextual bandits with Gaussian-type features Esfandiari et al. (2019) studied batch adversarial multi-armed bandits and Jin et al.] (2021a b. 2023) focused on the asymptotic regret bounds with
batch limits.
Hanna et al. 2023b) designed batch linear bandit algorithms for stochastic contexts via an elegant reduction to the fixed-action-set setting. Hanna al. (2023a) further proposed an oracle-efficient algorithm for the batched context linear bandit problem with infinite arms at the price of suffering additional poly(d) factors in the worst case regret.
For the non-contextual linear bandit problem, recent work by Ren et al. 2024) introduced the E* algorithm, which achieves minimax optimal regret bound with Ollog log(T)) batches, and an asymptotic optimal regret bound using just three batches.
2 PRELIMINARIES
Linear Contextual Bandits with Stochastic Context Sets. We consider the linear contextual bandit problem with the hidden linear model described by the d-dimensional vector 0 ||0|| ~o < 1. There is also distribution D over the context sets hidden from the learner. Given the time horizon T. during each time step t e {1, 2, ..... T). stochastic context set of K feature vectors, X, {æ1,1, ......... xt, is drawn from D and revealed to the learner. The feature vectors are in Rd and D guarantees that Vi E {1, K} [ < almost surely
The learner has to choose and play action (defined by its associated feature vector) ye E X, and receives the reward r, = y. 9 + 6,, where é, is an independent Gab-Gausiinn noise with zero mean and variance proxy bounded by 1. The goal of the learner is to minimize the total (expected) regret
Rr := E Σ [x],
y. 0)]
NNoe that our formulation is more general than the usual linear contextual handits setting where ||0]|2 5 and [ It also includes K-armed multi-armed bandits special case.
4

---

Published as a conference paper at ICLR 2025
Batch Learning. Given the batch complexity M, batch learning algorithm aims minimize the regret Rr defined above, subject to the constraints in Definition I
Notations. For any non-negative integer N, we let [N] denote ,1, N.. We use Epl: and Prpl-] to denote the expectation and probability over the distribution P respectively. We use I to denote the d-dimensional identity matrix. We use log to denote the logarithm base 2, and use In to denote the logarithm base e. Throughout the paper, the Ō(.) and (2(-) notations hide the logarithmic factors of T, d. and K. We also define To = To and Th Σ T; for S l: S M.
TECHNICAL OVERVIEW OF OUR ALGORIHTM
In this section, we summarize our techniques contribution and sketch the high-level ideas in the algorithms and regret analysis.
Our algorithms are dimination-baseen following (Ruan al. 2021 At each time step t. give the set of context vectors X; { 2t.2. & 1. we maintain confidence interval Zz,; for æ,, for each i. candidate action ær.,, eliminated when there exists another candidate action ær,5' such that L entirely lies above Z,,. meaning that the action Zt,; cannot be the optimal action. Then, the clever part of the policy is to decide a distribution over the remaining candidate actions and randomly choose one to commit to according to the distribution.
For the construction of the confidence intervals, we adopt the classical elliptical confidence intervals based the regularized ordinary least-square (OLS) estimation (Chu al. 2011). Given group of context vectors that are played in history {yr } and corresponding observed rewards {rr Ir- (such that r, y 0 + G where e, is 1-subgaussian noise), we construct the confidence interval for any candidate action with context vector æ to be
I(x, A)
x avæ x aave
NI-1.1).
with A = XI Σx= y. is the regularized information matrix, θ A- EE T- is the regularized OLS estimation of the hidden vector 0, and a, À are hyper-parameters satisfying that = ((vin((dT))))) + Avd).
Define w(x, A) = min {(in(KaT) (
to be the width of the confidence interval [(x A). To reduce the regret, we would like to design policies to cleverly perform exploration in order to reduce the width of future estimations. Formally, we introduce the following problem which is the key to our optimal batch learning algorithm.
+
The Problem of Single-Phase Learning for Exploration Policy. Fix m1, > 0. Let (Y,} {x be two groups of i..d. context sets following the same unknown distribution D. After observing {X:)"= we are asked to design the parameter and an exploration policy π so as minimize the following expected maximum width EM-widthi D, A) = Ex~D fmaxzex w( -Ex-Dmaaxxxx A)].
where A +I ΣØ= y and y, ~ (YG)) for all < $ n.
In our batch learning algorithm, we need to solve the above problem once during each batch. During the k-th batch, we let D D2 be the distribution of the set of the remaining context vectors after the elimination process based on the information learned for the first (k - 1) batches. {X,)," is obtained from the (k= - 1)-th batch, and we solve the above problem for which serves as the exploration policy for the k-th batch. The minimization goal the above problem helps to reduce
the regret starting from the (k 1)-th batch.
To facilitate discussion, we use W(m, n) to denote the minimax optimum of expected maximum width achieved the best learning algorithm G. That is, we let
W(m, n2) inf sup E, EX..Y, J~ ((xAA)-(((X.))) [EM-width
where g is the single-phase learning algorithm decide and À based {X,)
In (Ruan et al.) 2021), the authors showed the existence of a good policy æ and the choice of that the bound of the expected maximum width leads the desired optimal regret for M
5

---

Published as a conference paper at ICLR 2025
(log log T) batches. Their constructive proof (given the distribution D) is based a reward- free LinUCB algorithm (Algorithm 2 in their paper). However, to learn such a good policy based on {X; the authors employed more complicated procedures (such as CORELEARNING and CORFIDENTIHIAATION))
Both (Zanette al. 2021 and work are inspired by the reward-free LinUCB and find that one may leverage this a aigorithmic framework to design learning algorithms as well. The authors of (Znnttte al. 2021 worked on a similar task as the single-phase learning problem defined above
and their result implies that W(m, n) S O (plyy In(mndT) vln(K) (Vd/n + vd/m) 4
In comparison, in Section 4.1 we propose
to solve the single-phase learning problem. In Lemma 5 we analyze our algorithm and show that
W(m, n) So poly In(mndT), vI(() (V d
(1)
Clearly, the performance of our Exp-Policy outperforms that the results in (Zanette et al. 2021 in terms of the dependence m. Note that in our batch learning algorithm, m represents the number of samples in the previous batch, which is much smaller than the size of the current batch (represented by n). Therefore, the d/ m term in our bound usually dominates and it is crucial for us to make this /m--factr improvement to achieve the optimal regret in the batch learning model. Indeed, without this improvement, the result of (Zanette al. (02T) does not even imply the desired optimal regret for M = O(log log T') batches (the result of (Ruan et al. ) )
The proof of Lemma 5 is based on the analyais of reward-free LinUCB, and involves scaled-and clipped update rule and a dynamic concentration incquality for PSD matrices. Below we present the high-level ideas.
Learning the Exploration Policy via Reward-free LinUCB. In (Ruan et al. 2021). the authors showed that given { )}ー=1 ~ D&m,, the reward-free LinUCB algorithm can produce {y, 1y= (and therefore also form policy) such that
EM-wicth( (D,)) = (lddd/(n///))//)
(2)
x T to make sure that U where U - = V.y and 6 > 0 is polynomially small (e.g., =
is invertible while we do not lose much in equation 2 In this work, our ExxpPolle licy algorithm
cannot direct access [- but has to learn the distribution D and construct a policy π based on a much smaller data set {
To make learning possible, we first notice that the original reward-free LinUCB in (Ruan al. 2021 produces {3, 1 by the so-called argmax policy: y = (Y,)), == arg max {y Wjy where W, = xI + Σq=1 My is the regularized information matrix obtained from the samples before One may combine {πy} via carefully chosen probability weights to form desired one-shot policy π.
In our algorithm Exp-Policy (Algorithm 2). we observe that we may approximately learn the pm policy x from { as long as we are able to approximately construct (W,) based on the (X.} data set. I.e., for any W = W,. we would like to construct W as long as 2(1) W x W & Õ(1) W, and the key here is to lower bound W by 2(1) W.
To illustrate the main technical challenge and our solution, let consider the following task: let 2; ~ т (X,) and W = IL (xI + Σ x. ), we would like to choose appropriate regularization parameter À > 0 so that with high probability (over the randomness of {X,} and (æ.3) it holds that
2(1) W < n (Y) + Ex-DDawr xx
(3)
"We state this implication by making the "large IS Al" assumption in (Zanette et al. 2021 'Comparing equation]] [ and equation 2 we also find that the cost we pay in the expected maximum width for learning about Ödd/m).
'We warn the readers that this is an oversinplification of the algorithm by omitting few important techniques such as the volume- lazy update of the W, matrices. However, we choose to the current presentation to hetter motivate technical contributions.

---

Published as a conference paper at ICLR 2025
We note that this task may seem bit different from our goal: 1) π is unknown to the learner, and
cannot be used to construct W; 2) the upper bound is quite different from W = xI + Σ}= y 3 Indeed, these issues may be (quite non-trivially) resolved by observing that 1) π is a mixed policy and can be iteratively updated to its final form and 2) relate the Right-Hand-Sidoe of equation 3 to W by another matrix concentration inequality.
We now focus on the task of equation
3
which is equivalent to
2(1)
KI +
x m (AI+ (x=),
(4)
Note that since 2; (X;) are i.i.d. random variables, standard matrix concentration inequalities would imply equation 4 when mAl upper bounds æz,r! (up to logarithmic factors of the inverse of the failure probability) almost surely, i... mA (2(1) < A 2 ((1/m). This choice of X would lead to d/ m term instead of the d/m term in equation] 1
The Sealed-and-Clippee Update Rule. While is not possible to establish equation I (with high probability) for a smaller (c.g., = o(1/m)), we introduce the scaled-and sadled-nddclipped update rule in the reward-free LinUCB (Line of Algorithm 2 which eventually leads to the improvement of X.
More concretely, instead of working with W clipped version of æ; and the leeedddand-lppppe information matrix U
m (xI + E x. ). we define the scaled-and-
x. min (V TeTUUa1 )
1
x;. = Σ p=1
2
We will use } to construct the mixed argmax policy instead of W's. The downside of this new shorter feature vectors {œ,} instead of the original ones, which leads the slower growth of the information matrix. However, this slowing effect is not too bad if we repeat each æ; by In(1/k) O(I T) times, the original information matrix. Through a more rigorous analysis, we will see that this effect would only hurt the regret by logarithmic factor.
update rule is that
information matrix Ug would upper bound
On the other hand, the benefit of our scaled-and-clipped update rule is that instead of establishing cquation[4] we only need to lower bound the Right-Hand-Side of equation Jyy the scaled-and-clipped information matrix, i.e., to prove that the following inequality holds with high probability.
m
9(1)
KI
x C
< m (AI+ (xx
(5)
where a; min
m. and we assume that n, x (X) are i.d. (as we did in
equation
Let U xI Σn - ã. To prove equation 5 we only need to show that there exists constants
22
0 such that
C o GU + mXI + mDx + (x)
which implies that
(o2 - (I) & mAI + EX (X) O & mAI+ + Ex~ (x))
where the last inequality is due the clipping operation in the update rule.
Now let us focus on the task of establishing equation 6 Thanks to the definition of the scaled-amd and- clipped version R, we have that क. U almost surely. Therefore, is possible establish equation 6 as long as we choose mA 2 (2(x) to cover the x7 term in U (which only requires that 2 (2kmm))===-))) = 2m 2), leading the better d/ m error term in equation [ On the other hand, however, we note that U, while serving as an upper bound of the random matrices क; is also a random variable by itself. We do not find sharp matrix concentration inequalities literature fit our need, and we have to resort to the matrix concentration inequality with dynamic upper bounds proved in Lemma 20 The formal version of equation is stated and proved in Lemma 14
"The definition of ã; here is slightly different from the real algorithm (up to logarithmic factor L.). We make this simplification only to better explain the main algorithmic ideas.
7

---

Published as a conference paper at ICLR 2025
3.1 LOWER BOUNDS
To construct the lower bound instances, we first construct M mutually independent sub-problems with dimension d/M. At each time step, a uniform random sub-problem (i.e., its context set) is selected and presented to the learner: To analyze the regret performance of any batch learning algorithm, we divide the time horizon T into M consecutive stages with properly chosen lengths {Ti J for each stage. We will show that, for each & E [M)) during the k-th stage, if the learner does not start a new batch and update its policy, then large regret would incur for the k-th sub-problem in this stage.
.,....M) M). we choose the Our construction for the sub-pro problles is as follows. For each à f1.3. ...... sub-problem to be the hard instance for the K-armed linear contextual linear bandit problem with burn-in time (Tx-)) other words, we construct the k-th sub-problem so that is hard for the learner to find a good policy for the k-th problem during the first Eisk-1 Ti time steps.
The most interesting sub-problent design is for k = 2, where the learner suffer more regret due to lack of context information. In this sub-problem, we consider a linear contextual bandit problem d/M arms (assuming that K 2 d/M). However, during each time step, only (d/ (d/22M) + 1) arms are presented the learner. particular, we set the first (2M) arms to the frequent arms that always appear in the context set. For the rest d/ (2M2 infrequent arms, we choose one of them uniformly randomly and include the chosen one in the context set at each time step. The best exploration strategy for the learner is to play the infrequent arm with a higher probability, e.g., á and play the frequent arms with probability 4 with insufficient information, and his best strategy is to play the arms with the same probability. As result, the infrequent arms are insufficiently explored, which leads to an extra ② factor in the regret.
M. However, the learner can not tell whether an arm frequent or infrequent
BATCH LEARNING ALGORITHM
We now present our batch learning algorithm in Algorithm I which corresponds to Theorem Let the time schedule (7h J such that Σ Ts 2 T to be determined later. We can then accordingly calculate the end of each batch by Ti min E==1
E Tk. T
In preparation for explaining the algorithm, we first introduce few variables and notations used in the algorithm. During the k-th batch, the algorithm learns an estimation, namely Oz, of the hidden vector 0, as well as an information matrix A that used construct the confidence interval for the estimated rewards based on Oz. More specifically, given the pair (Ak, 0x), we set the confidence
interval for the expected reward of any feature vector æ to be [xe 02 + av x A='a], xz] where [a + b]
denotes the interval [a b, + b] and we set a = (n
Given the pair (Ak: 0s), for any context set X C ıRd, we define the following natural elimination procedure based on the corresponding confidence intervals
C(X;(As. 0z)) = E x 0 ay A
max
O 170x-a/5 B MEX
In words, E(X; (As. 0x)) returns the set of the survived feature vectors, each of which remains possible to hold the highest expected reward when assuming all confidence intervals based on (Ax. 0x) contains their estimation targets. By the end of the k-th batch, the algorithm would have learned l pairs {As, 0.)) and we naturally extend our elimination procedure to {(A,, ) as E E(X; [(A,, , ))))/z)) := E(;; (A,, Q,)). When X ~ D and given ((A,, 0,)) we denote the distribution of E(;; {(A,, O.) by DR+1-
We now explain the key steps of the algorithm. For the first batch, take actions according the local optimal design policy T which is defined by the famous General Equivalence Theorem in (Kiefer & Wolfowitz 1960) (see L Appendix(A]
For k 2 2, at any time & during the k-th batch, the algorithm observes the context set X, D, eliminates some of the sub-optimal arms in Line and denote the set of the survived arms by x(A
8

---

Published as a conference paper at ICLR 2025
Algorithm 1 Batch Learning
1: Initialize: À 10/T; Au + AI; 0u 0:
2: for 1, 1,2...., Ti do
, 3: Observe Xx;
4: Play the arm with the feature vector ~ (X,) and receive the reward fr;
5: end for
6: A₁ + + T//2 y:y: 01 + AT -T'2211 Tryt:
Ti/2
7: - Exp Policy [E(X,, {A1, (0,,01)11
8: for = ..... M
9: for T 1, Tk-1 + ...... To do
10:
Observe Xxi
11: x + E(x,, (Ac, O;)
Play the arm with the feature vector y: Th (X(1)) and receive the reward rri
13:
end for
A& XI ET- TT-1+T//2 you.
0% + A Σ +2/2
Lt=Tr- X ((++1) + {X,,, (A,, (.)
- rey
15:
Tsi
16: Th+1 Exp Policy (1x
(k+1)
T= IT,T111
end for
By the definition above, the x!") follows the distribution De when conditioned on the first (A: - 1) batches. The algorithm then uses exploration policy m 1 to stochastically select and play an arm Y: x-A)
At the end of the k-th batch, our algorithm divides the Ta data points collected in the batch into two parts of the equal sizes. In Line L our algorithm calculates Aş and Og using the standard ridge regression and the first part of the data points. In Line | the new exploration policy TH is learned by the Exp- Policy procedure using the context sets from the second part of the data points. Note that the context sets fed into Exp- Policy go through the elimination procedure based {A,, 0) 0=1=> which depends on the first part of the data points.
4.1 LEARNING THE EXPLORATION POLICY
We describe the Exp- Policy procedure by Algorithm 2 Given group of context vectors 1 the algorithm simulates the reward-free linear bandit algorithms. In each time step, the algorithm first clip the context vectors according the current information matrix W, and then chooses the arm with clipped maximal variance. The information matrix is updated with doubling trick, which helps reduce both the number of updates and the complexity of the output policy. With Algorithm 2 we have the results below.
Lemma S. Let {Zu Ji be m i.i.d. stochastic context sets following a distribution D. Let π be the output by running Exp Policy (Algorithm 2 with the input {Zm)m Let Pu be another group of i..dd stochastic context sets following the distribution (which also independent from
(Za) m ). Let Yu be independently sampled from (Z.) for each u. E 2,,....,77 n), and let
A u=1 YuYn. Let L > 0 be constant. With probability (1 35), we have that
KI) x, VI
(
so
d
md K
dvL
md
E ExwD
min
max T(A+ mEX
In
m
m
K
Due to space constraints, we postpone the full proof of Theorem and Lemma
2
tloo Appendix
B
5 CONCLUSION
In this paper, we study the batch linear contextual linear bandit problem with stochastic context. When the number of batches limited by M, for any T and d, achieve matching upper and lower

---

Published as a conference paper at ICLR 2025
Algorithm 2 Exp- Policy
1: Input: (2.)==1 L;
2: Initialization: R 7 Ug mI: 7) 1, Fn. 0, W, Up:
3: for i 1,,,...,. do
4: Ti f- Ta (i}:
5: Choose 2, Zz to maximize 2; -.-W-1a
2, - min { {v [/(2,] WT 21),
6:
Z Us <- U2-1 + 8
7:
if (U;) > 2 (W,) then 1/ Ty t 0, Wn t Usi
8:
9: end if
10:
end for
11:
return such that π (X) = arg max x W x with probability [ryl/m for j E [n]]-
bounds for the regret (up to logarithmic factors) both context-blind and context-aware settings. In the algorithm design and analysis, highlight two key techniques: the scaled-and-cllpped update rule and the matrix concentration inequality with dynamic upper bounds. We believe these techniques could help design and analyze batch algorithms for other online learning and decision-making problems with linear reward structures (e.g., the linear Markov Decision Processes).
ACKNOWLEDGMENTS
This work was supported in part by the National Natural Science Foundation of China Grant 52494974.
REFERENCES
Yasin Abbasi- Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24:2312-2320, 2011.
Naoki Abe and Philip M Long- Associative reinforcement learning using linear probabilistic concepts. In Proceedings of the Sixteenth International Conference Machine Learning, pp. 3-11, 1999.
Naoki Abe, Alan W Biermann, and Philip M Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37(4):263-29) 2003.
Peter Auer, Nicolo Cesa- BaaacBB,nchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-22 256, 2002.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208 214. JMLR Workshop and Conference Proceedings, 2011.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. Conference on Learning Theory. 2008.
Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. Regret bounds for 2019.
batched bandits. arXiv preprint
Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. Regret bounds for batched bandits. Proceedings of the AAAI Conference Artificial Intelligence, 3588):734--7348,
May 2021.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou, Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32:503-513, 2019.
Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye. Se- quential batch learning in finite-action linear contextual bandits, arXiv preprint arXiv:2004.06321,, 2020.
10

---

Published as a conference paper at ICLR 2025
Osama Hanna, Lin Yang, and Christina Fragouli. Efficient batched algorithm for contextual linear bandits with large action space via soft elimination. Thirty-seventh Conference on Neural Information Processing Systems, 2023a.
Osama A Hanna, Lin Yang, and Christina Fragouli. Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1791-1821, 2023b.
Tianyuan Jin, Jing Tang. Pan Xu, Keke Huang, Xiaokui Xiao, and Quanquan Gu. Almost optimal anytime algorithm for batched multi-armed bandits. In International Conference Machine Learning, pp. 5065-5073, PMLR, 2021a.
Tianyuan Jin, Pan Xu, Xiaokui Xiao, and Quanquan Gu. Double explore-then-commi) Asymptotic PMLR, 2021b.
optimality and beyond. In Conference Learning Theory, pp.
Tianyuan Jin, Yu Yang. Jing Tang. Xiaokui Xiao, and Pan Xu. Optimal batched best arm identification. arXiv preprint arXiv:2310. 141229 2023.
Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 22,66,3366, 1960.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th International conference World Wide Web, pp. 661-670, 2010.
Yingkai Li, Yining Wang, and Yuan Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pp- 2173-2174. PMLR, 2019.
Elliott H Lieb. Convex trace functions and the wigner-yyanse-dyson conjecture. Les rencontres mathhicenssm de Strasbourg-RCP25, 19:0-35, 1973.
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg, et al. Batched bandit problems. Annals of Statistics, 44(2):660-681, 2016.
Dénes Petz. A survey of certain trace inequalities. Banach Center Publications, 30(1):287-298, 1994.
Xuanfei Ren, Tianyuan Jin, and Pan Xu. Optimal batched linear bandits. orXiv:2406.041337, 2024.
arXiv preprint
Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 74 87, 2021.
Joel A Tropp. Freedman's inequality for matrix martingales. Electronic Communications in Proba- bility, 16:262-2D 270, 2011.
Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389-434, 2012.
Andrea Zanette, Kefan Dong. Jonathan Lee, and Emma Brunskill. Design of experiments for stochastic contextual linear bandits. Advances in Neural Information Processing Systems, 34: 22720-22731, 2021.
11

---

Published as a conference paper at ICLR 2025
A
TECHNICAL LEMMAS
Lemma 6 (General Equivalence Theorem in (Kieler & Wolfowitz I960). For any bounded subset X Rd, there exists a distribution K(X) supported on X, such that for any holds that
max x (el + Ey- I) a S d. =EX
Furthermore, there exists a mapping Tº, which maps a context X to a distribution over such that
max x (eI Ex-x(x)(V3 () I) S 2d.
(10)
xEX
In particular, when supp( X) has a finite size, TO (X) could be implemented within poly (Isupp[) X))) time.
Lemma 7. Let DKL QP) denote the KL-divergence between P and Q. Let Di(P.Q) P denote the Ln distance between P and Q. For any two distribution P, Q and a random variable X
bounded by [ [-N, N). NN, we have that
E X Eo[x]] N.
S DI(P.Q)N
(2kkL
(11)
Proof.
The second inequality is the famous Pinsker's inequality. For the first inequality, we have that
Ep X] - [X][ = / x(dP(s) - -(QP())-dQ())) SN aalllaee /laP(e) - (p(()) (D)(P..). (12)
Lemma 8. Let X1, X2,.. be sequence of random variables taking value in [0, Define Fx. (X1, X2,..., xx-1) and Yx F[[x]FFa) for k 2 1. For any 0, we have that
3n,
XR
S 3 Σ
Yv (1((1
2
k=1
k=1
P
3n,
Y4 >
X4 + (I((18)
<
k=1
#=1
Proof. Lett E [0, 1/[] be fixed. Consider to bound Zμ cxp(( =x (X 3Y By definition,
we have that
k-1
7 = exp(t
Σ
(Nw- - 38x) -3xe)
W=1
< exp(t
Σ
(Xv - -Ykx)) exp() E[1 + tXx + xx1
1-1
S exp(1
Σ
(Xw: exxx)) E[1 + 31Xx]
==1
K-1
= exp(t
Σ
(Xw - 3Y exp(-33300 (1+ 3/Y))
W=1
I exp(t Σ (Xx 3Yx))
7k-15
where the second line is by the fact that e" - 1 1 x 2x for x E [0, 1]. Define Zn =
Then (Zk)a20 is super-martingale with respect to {Fe)a21- Let be the smallest such that
12

---

Published as a conference paper at ICLR 2025
Σx=1 Xx -3 3E== Y3 /lm(1/ It easy to verify that (r.a) (exp(t/In(11/) +t)) < co.
Choose = 1/l. By the optimal stopping time theorem, we have that
in N,
X
Yk + 1 (1((1)))
R=1
k=1
P IT S S
(m.n(7.N)) 2 exp(tl
E| miZming,,N1
exp(tlln(1/6))
Letting N - 00, we have that
m
Σ
X 53
Σ
Y 21n(11))) 56.
k=1
k=1
Considering W₂ Etexp(t Σ =1= (Yx/3 xx)){, using similar arguments and choosing & 1/(31). we have that
En,
Σ
Yk 2 Σ X 11(11/8)
S 8.
k=1
The proof is completed.
A.1 STATEMENT AND PROOF OF THE ELLIPTICAL POTENTIAL LEMMA (LEMMA 9
Lemma 9, Let æ1, ,2,...,, be a sequence of vectors in IRd such that ||0l|l S 1. Ler Ag = be
positively definite matrix and A, = Ao + Σj=1 2, If x A S ffrr all s i < n, it then holds that
x A x 2ln /dt((An))
Σ
det(An)
Proof. Note that det(AA+1) = det(A;)(1 + 2 A, to:41) Since In(1 + 2 have that
when 0 S x S
1
In(det(Ar+1)) - In(det(A:)) 2
2 A kiti.
which implies that
x A x 21n dde((An)
det(Ap)
B THE REGRET ANALYSIS: PROOF OF THEOREM
Given T and d, define d = dln(TKd/))) In the case d < T S dl (K(()), the regret bound is exactly ((T'), and in the case dnn(K) < T < d, the regret lower bound 2(d In(K) and the upper bound at most OTT) <
Therefore, the case d S d, the trivial upper bound (TT) optimal up to logarithmic factors in T and d. Below we assume T > d.
We first define the following desired event where all the confidence intervals contains their estimation targets.
To T [ 0 + ay xT A Va Xx, Vt (1,2,..., T7 vk (1,2..... ...., M)
Eg.
13

---

Published as a conference paper at ICLR 2025
We then let E 1 be the whole confidence event.
By the amalysis of the ridge regression (Lemmal [5] stated and proved Appendix B.5 and the fact that a 2 vl((Kd/0) + Xv d, via a union bound we have that Pr[E] 2 MT6. When E holds, we know that the optimal arm any time step will never be eliminated by the elimination procedure E. Let I[E] be the indicator variable which takes value 1 when E holds and value 0 otherwise. We have the following upper bound for the expected regret of the algorithm.
[00
RT
E
I[
max fsr wEd:
0} 03-2..0) 27 Pr[E]
1=
t=
1=
71-1+1
{x To + 2MM28.
E
I[E
max (x
min x
(13)
=E
1=
Lemma 10. For any time step during any batch (k: 2 3), define X(#-1 E(Xr: Adi and we have that
!
[[ max (a 00 min #EX(()
$ min
4a max =Ex!!)
V A x.
(14)
xxx,()
Proof. When E happens, for any u, E (k) TO Oz + a u uuTTa A u0) and v To
[0 Ok + av UT _ v). We then have that
[ ( 0 vTT T))
u Og -1 + aay
Suluuul TTTTA A
- Ar- -
On aq u A
v T + +ay A
20 uuuT Tu 200 0 A
20 u A + 20r/
T AA
1
(15)
< 4a max =Ex(
a TTTAA A < 4a
max mEX(
x A 1
where the equation 15 is because survived from the elimination based on (As-1, 0x-1). and the
last inequality is because x((a) C X (((-1))
Letting arg max
mex!") ( {a LoT)) 0} and arg min mex!1) s fx TO} and noting that u 0, v e
[-1, 1]. we have that
[[
max fxr 0} min for 0} =EX("))
< min 4a max =Ex("-1)
T 82
(16)
x
Taking the expectation over equation
16 we prove the lemma.
B.1 REGRET THE FIRST AND SECOND BATCHES
The regret in the first batch bounded by Ti trivially. For the second batch, we have the lemma below.
Lemma 11. With probability 1 - 8, it holds that
<0 (v
Ti + In(TT//))
Ex-D
max ()
V /minf TaaeTTAT1 AT xe, 2}
dln
x
14

---

Published as a conference paper at ICLR 2025
Proof. Recall the definition of y: and r, in line 1 Algorithm I $ 71/2. By the Elliptical Potential Lemma (Lemma) have that
Let W denote AI+ AI+E,= Yr y- for stated and proved in Appendix A.I).
T1/2 Σ
min W 1.-...11 s 0
Ti A dln
)
By Corollary 22
with = 2, we further have that with probability 6, holds that
Ti/2
Ti/2
Σ
Ex-DEyyrtt min(y T W y, 1) 2
Σ
min yb W Vr. 1) + 56 (nln(T1/))
1=1
(Ti (Tr
+ on)
S
d
(17)
Noting that W,- & W. for 1 S L Ti and A = W /2, by equation 17 we have that
TxEx~D Byn min(y" AT y.y. 1] s O dln
Ti
+ In(TT//))
(18)
X
Lemma 12. For any PSD matrix W and context X, we have that
minfmax(( (x ( W] 1) I min K, d (x) min W 1.
(19)
m
Proof. By Lemma 6 have that
max "w-'x) S min (K, (y)r W-1 y.
(20)
xEX
In the case max W- I 1, we have that y W- y for any y E X. then holds that
max
min (x W W x, 1} < min K, d d min(y W w Wy'y, 1}. y.
xEX
In the case m x 1] 2 1, it is trivial that
W- x > 1, we analyze as below. When min K, Pr Pr yx) T W-
min K, By min T 1) 1.
Otherwise, we have that (d min 1 'y
min(K K, d) (x)) W y min K, Pry W-1 1] x To - 1) xE
2 max x: aeX
W- x min K, d Pr y w y >
[mmxx x T W x - 1) (21)
xEX
min K, Prywn W yy ( WW 1)
ØEX
> 1.
Here equation 21 holds by Lemma 6 The lemma is proved.
Setting W- in Lemma 12 we have that
min K, d}
-0 (din
T [h) x
+ mn(T:/))
Ex-D max min AJ x, 1) < xex
(22)
T1
Therefore,
VminfxIAç² 2
EX-D
max (EE(X.(A,,01)
- x,, 13 5o (1
min{KK d)
Ti (5] (dIn
ExnD
max
Ln(Ti/0)
#EX
Ti
finish the proof of Lemma 11
15

---

Published as a conference paper at ICLR 2025
By Lemma
10 and 11
and
the regret in the second batch is bounded by
o T2ar
min{K, K, djd
(T'
In
+ T8.
(23)
T1
B.2 REGRET GENERAL BATCHES
Let
: == 200 (Td//6))
and K := T
(24)
be the parameters to be used by Exp Policy.
For the k-thh batch (k 2 3), we invoke Lemma
with m T {Zu)m
(x( TT=Th T 2/2+1" T [Z=]a=1 (x! (k-1) To 2 1/2 and D Dk-1,
we have that with probability (1 35), holds that
Th-athh-122 Σ
Tx-1 kI Tk-2
E DD
min
x
yoy.
VL.
1=
(yelm (Te-2d) (1
VL
.0 (dln
Th Tk-2d
0
+
(25)
Th-1
k
Tx-2
K
Ty. Note that Ta-1 k < X and therefore
(ETh- Tk-2+TT-112 To 2+1
ye
+
Th-1
xT)
T
x A
Therefore equa-
tion 25 implies that with probability (1 36),
Ex=De-1
min { maxx A Ar
( mEX
VL
5
1
o
(Valn(Ta)
+
VL
O In (Td)).
Th-1
Tk-2
(26)
In other words, for each time step f during the k-th batch, we have that
max x AA k-1 vL] xcx(" 1)
1 s $1 Th
o (VaIn(Ta)
VI.
min
+ Th-2
O (d (Td) + 38.
(27)
16

---

Published as a conference paper at ICLR 2025
B.3 PUTTING ALL TOGETHER
Combining equation
13 Lemma
TO and Lemma T1
the total regret is bounded by
2 min K, dddll
Ry $ 271 + 272 min av
Tj
M +
TE
min
4a
max =e (x(6-1)
V x
A 22 22
x- + +MM22
k=3
2 min K, dddln
x 2Ti + 27p min av
Ao
T
min
max
T A VL
+ 2MT2
x
km
(28)
2 min| K, dj ( 16
< 27 + 27, min av
Ti
4aT,
min
max x(
A
VI)
VL
+ 2MT
(29)
Here equation 28 because of 2 < 4avL.
Let d = (TdK/6)) ( Combining equation 29 and equation 27 (for k 2 3), we have that
T Xx min K, ddd
Rr S 2Ti + 2T2 min a
Ti
+ 4ox >
M
Tk
0 (Vdln(Td)
+
T&VL
o (dln + +375 + 2MT2
/Tk-1
T
k=3
2min K, d]dln
M
T T& Vd
< 2T' + 2Tp min
a
16
+ 0 + x
Ti
1
M
Ted
+0
In (Td) (T
+ O(MT²8)
Tk-2
k=
2min K, dtd Ti
TiVa
Tid
< 27 + 2T2 min
+ (ln(Td))
O(MT20)
Tk-1
k=3
(30)
When T is small (i.e., d < T d), Theorem 2 trivially holds because the regret is at most O(d).
which is further bounded by
I- M+2 T M7 (dln(K)
2- (dIn(K))
2 M1l1
}):
O poly In(Td) min
2-2 2-2 arr T MII
8-2 MrT min ( K, d) 8-2 3
Suppose T 2 d. Let h min{K, K, d). We discuss the following two cases to design the batch schedule.
17

---

Published as a conference paper at ICLR 2025
-1-2-Mr+2
Case I: d T S dh2-2-
In this case, we define 7 T2 2-2442 d2 2-3422 d.
We let
( 43 S k M. Vd
T =
T2 = ==
(31)
Then for < k - M. by the iteration rule we have that T. = 2-2 x d-1+2 k42 It is easy to verify that Σx=1 Tu 2 TM = T.
Now verify that the regret for each batch is bounded by O())- Firstly have that Tı, T2 S Y- For k = 3, we have that Tsvā and have that
Tad TI = =add I 7. For s S M, noting that d 2 we
VT2
Tavd
Txd
g2 -- 2 I)
7,
Sr.
(32)
TR-1
Tx-2
Therefore, the total regret in this case is bounded by
o T 1 de 2 MTT
M42
log log(TT) +T
(33)
Case 11: I > 2h2-2-M+2 In this case, we define == 2'2-2 MTT
d
M++1
MT
h2-2 MIT > d. Let
2 2-
Mi11
VTi
Tg Th-1
T =
To 7
v & M.
(34)
Vāh
Vd
By the iteration rule, we have that Ta = 72
2 k1 J- +1 h 2 kil
In particular, Σ T3 2
Tas 2-2 Mil J-142 M h Mi1
T.
By definition, we have that Ti S and T2 dhh
S n. For 3, we have that
vT.
Tdvd d
Tyd
Ti = y d 57
VT2
For M, have that
T Vd
T-- Y
Tgd
613 2
111 2-11
_
71+2
51
+11 211
k-1 h2 k+ 2 #11
d
"h
(35)
Th-2
d
So suffices to verify dh S 7. In fact we have that
2-2----- M+1
-2 M+1 M+1 2 1641
2 --22- M+1
1 2--2-M4222
M+242 181
> 2-2 25 1 2841)
(36)
which implies that d 7. Therefore, the total regret in this case is bounded by
o Ta Ta a-tt 22-2-244 M44 h 2- M++1 log log(T) MT28) o
1-2 MIl
3-1111
(37)
We now finish the discuss about the two and combine the two regret upper bounds equation and equation 37 Noting that T
33
2-2-2 M+2
implies that
T2-2-M+2
82-2-M
-1-2-14 M42
T 2-2 I
2-2- M+1 2 -2---
M+1 h h-2---M4
(38)
18

---

Published as a conference paper at ICLR 2025
have that
Rr 50 min T2- - d2-2-ar42 22-2-
2122
d2-2-M++ h2-2-2447
11-2-881 11-2
Mall 2-
log logg(())))))))))))()) MT22)
Setting 8 = 1/10, we obtain that
Rr s so (oloy poly In(Td) min { (T' 2 2r (d(n(()) M112
1-2 M+2
1-2-M+: M++
M111 min K, d} 2-2--- M+3
})
T2-2 (d'n(K) 2-2- M+:
Theorem is proven.
B.4 ANALYSIS: PROOF OF LEMMA 5
Lemma (restated), Let (Z.) u= be m i.idd stochastic context sets following a distribution D. Let be the output by running Exp Policy with the input {Zy, Im Ju=1 Let (u be another group of
Li.. stochastic context sets following the distribution D (which also independent from {Zu, 1m 1)-
Let yu be independently sampled from x (w.) for each u E {1, 21. n., and A E yo
With probability (1 35), we have that
n KI) I., VI
S 1.10
(v
md
VL m
md
Ex-D
min
max T mEX
(A
Iddn
+
dln
m
As stated in Section 3 the proof of Lemmaā]utilizze similar ideas in the proof of Theorem 5 in (Ruan al. 2021). The major difference that their information matrix starts with (2(1) I when executing the output policy, while our information matrix could start with sI with T As a result, it is harder for to recover the information matrix Um.
Let D be the distribution defined in the statement of Lemma With probability (1 8), it holds that
we first prove the following lemma.
Lemma 13.
mEx-D min max x U x. L} < O(dln(md/ss).
(39)
Proof. Let 77s denote the index 17 such that i Ty. Note that Ty implies that dct(U,-1) s de,,,,)) which further implies that det (W,)) S 2. Because U--1 > W,, we have that (W,, " T > I. Therefore, the maximal eigenvalue of (W,, (W, I x I is at most 2, where it follows that U:-1 < 2W,
Since Um > W,, for all 17 2 we have that
X min mmxx T U xz L} xeX
< Σ Ex-D min fmax x T W 1x, L} xEx
(40)
Invoking Corollary
22 with
and noting that Elmin W W 2; L}]
ni Ex~D [min (maxmmxxxxx W ar, L}] when conditioned on the first Algorithm
1) iterations in
we have with probability (1 8), holds that
E EX-D min fimmmmxx xf WW x,, L}
2 min 2 W z., L} + 20L 20L (n160).
(41)
19

---

Published as a conference paper at ICLR 2025
By the definition of E, further have that
Σ min W 2, 1} = Σ 2 W 2,
Σ i=1
2 U. S ((dl)mmd//k)),
(42)
where the second last inequality is by the fact that - < 2W n. and the last inequality is by direct
application of the Elliptical Potential Lemma (Lemma 9 stated and proved in Appendix AA.1 and the
fact that 0 < L < 1. Combining equation 40 equation 41
equation 42 and the definition of L,
prove the lemma.
To proceed, we have the lemma below.
Lemma 14. Define V == Ex=D,ivaXX)
min
L
1 u.
With probability 1 8,
a. Um m.
1
V
U m
KI.
(43)
6m
3m
Proof. Recall that Fm o(1 X2,,,X2, Xy,..., X 1). By the definition of æ, and noting that Um 2
W n. implies that 1. 2
1.
for u S m, we have that
2: Um
a;
8:
Way 21
mV
Runda 2T.io [F]]
Noting that =T,;, W Zu,i. I L implies Zu,s, Zi, S LW S LUm by Lemma 20 with Zm LUm and c = 2, with probability (1 - 8), we have that
m
100L In(Td/))
mV b Lu,ia uuto
Fu] 7
Zusj uuib
Um
3
1
Zu,i Zu,i.
T
Un
6
1
U
m
3
1
RI,
and the conclusion follows by dividing both sides of the inequality.
Recall that A >nm yu Let
1 } yn y Um yu
A = Σ min
By definition we have that A A.
Noting that for any S u S n,
E min and min 1 8,
uI U..Umuy yu 1 Buyl = -xx_D.xx7x)) min x Um! x;
1 2 = V
L VI. V.uumbn ; Bull $ LUm, by Corollary 22 with LUm and c 3. with probability
68L Um.
> V
By Lemma 14 we further have that
A A A V
68I
U
V
Un
(Lum
(1 Un
1 RI
1
U..
Un
71 9m
KI.
3m 6
3
6
36m
Therefore, A
a KI Um.
20

---

Published as a conference paper at ICLR 2025
In the case 2 m, have that
//maxa ao! (A + m =x1 2i vL
EX-D
min
36m
min { max a Un ais v Ln/m
E Ex=D
n
36m
EX-D min { max on Um ass vT.J
36m
Ln
[max a; Um 2z 2 T.
+
V m
Prx
36m
VT.
(md"
ExnD min max x. Um Lz. L
+
o
dln
md
VL o
md
dd
dd
n
m
k
Here the second last inequality and last inequality are by Lemma 13 and the fact that
Prx-D max a. Um' xx I.] EX-D min x Un x; L.
1 m
0
dln
md
K
In the case n < m, with similar arguments we have that
EX-D
min
max
(A + - xI
Dis vL
36m
Ex-D min (V max æ Um xi, v Ln/m
36m
EXwD min
{v max ai Um xc v
36m
ExND min (maxx; Um xi, 1
I
o
(V d
md
V n
k
(v) dln
(nd)
+ VL. -
md
o
ddnn
The proof is completed.
B.5 STATEMENT AND PROOF OF LEMMA 15
The following lemma is a similar version of Lemma 31 in Ruan et al., 2021 that analyzes the size of the confidence interval by the ridge regression. Note that since only assume ||0||oo instead of the upper bound on the Euclidean norm, the calculation is slightly different.
Lemma 15. Given 0, T1, I2,..., In E Rd such that |0]| < for all E [n]. let r; = x 0 + e; where {c)) independent sub-Gaussian random variable with variance proxy 1. Let A
II E D and θ A-1 E T434, For any x E Ed and any q O, we have that
Pr a T (0 0)- > (r VaN)VZA-12 -1 $ 2e =.-
21

---

Published as a conference paper at ICLR 2025
Proof. Direct computation gives that
x
T (0
0)1
=
x
T
A
2 0 +
x
A
2 + A 1 - 1I10 0)
x
A
Σ
DíC; 10
$ A A 0 +
Σ x: T A m0;
h=1
For the first term, by Cauchy-Schwarz and noting that A & AI, we have that For the second term, by sub-Gaussian concentration inequalities, we have that
A a A S Xvd AA I Vdaa la
(44)
Pr
Σ
x T
x,6i > VV A
S 2e 7
(45)
i=1
The conclusion follows by combining equation 44 and equation 45
C REGRET LOWER BOUND FOR CONTEXT-BLIND BATCH LEARNING
In this section, we prove Lemma 16 which implies the regret lower bound theorem (Theorem first sketch the high-level idea below.
4 We
High-level idea. To construct the lower bound instances, we first construct M mutually independent sub-problems with dimension d/M. At each time step, a uniform random problem (i.e., its context set) is selected and presented to the learner. To analyze the regret performance of any batch learning algorithm, we divide the time horizon T into M consecutive stages with properly chosen lengths (T& } k= for each stage. We will show that, for each k E {1, 2...... M). during the k-th stage, if the learner does not start a new batch and update its policy, then a large regret would incur for the k-th sub- aub-problem in this stage.
Our construction for the sub-problems is as follows. For each E (1,3,4,5,... M). we choose the sub-problem to be the hard instance for the K- Kaareed linear contextual linear bandit problem with burn-in time (TT--))) In other words, we construct the k-th sub- sub-problem that it is hard for the learner to find a good policy for the k-th problem during the first Σigk-1 Ti time steps.
The most interesting sub-problem design is for k = 2, which takes the advantage of the context-bling setting to force the learner incur more regret. In this sub-problem, we consider a linear contextual bandit problem d/M arms (assuming that K 2 d/M). However, during each time step, only (d/(2M + 1) arms are presented to the learner. In particular, frequent arms that always appear in the context set. For the rest d/(2M) infrequent arms, we choose one of them uniformly randomly and include the chosen one in the context set at each time step. The best exploration strategy for the learner is to play the infrequent arm with a higher probability, e.g., 1 and play the frequent arms with probability M However, due to the context-blind setting, the learner can not tell whether an arm is frequent or infrequent with insufficient information, and his best strategy to play the arms with the same probability. As result, the infrequent arms are insufficiently explored, which leads to an extra ((vd) factor in the regret.
set the first d/(2M) arms to be the
Lemma 16. For any algorithm G with batch complexity M, assuming T 2 d dlgg (K), the minimax regret is at least
M+1
T MIT (dlog, 1 M+1
(min{K, K, df (K)
M-Z-M-T
1 min poly In(Td)
MTT
Ω
M
T2 T 2-122-422 M+2 (d
(
22

---

Published as a conference paper at ICLR 2025
Proof. Define d d/M and h min d].
Define d
d dloRg (K)
d (Kg 1 d and
M Iu(dM)
12-21 M+2
h
h (K)
When d s T < dh
define Y T2-2-M-- d
MT2
When T >
2--2-- M++1
h2-2 M+2
define == T MTII d² 31 h MII 2 d. Given y, we further define Ti = 7
T2 = max (7,
In(dM) dh
and Tk = V
MTk-1 Iu(ddd) for any 3 S S M. Let e1 = 100
(Ro
6 min
1
da
and ck 100 V
................................ M. dlogz!K) for k MT lu(dM)
100
T. In(dM)
Fix the algorithm G. Below we assume the randomness of G is considered in the expectation operator E|- and probability operator Pr[.]. Let Regret (T) be the expected regret under & with hidden parameter and context distribution as D. We aim design D and 0 such that Regret,, (7) is large enough.
Without loss of generality, we assume d/M an integer. In the construction below, we divide Rd into M subspaces, where for each subspace we construct a hard case. We let R 1 where U is the subspace spanned by { In each round the noise is set to be Gaussian { M
4/M
with variance 1. The hidden parameter = {0* Ji=1 is chosen from the space y = MM = The context distribution D is given by the average of { first sample u, Uniform(11 M), ...., M
LM /i=1- That is, in the t-th round, the environment and then sample X according to D... In words, divide the original problem into M independent sub-problems. For the k-th sub-problem d/M, the dimension is d/M, the parameter space is )* and the context distribution is Dj-
We now define y* and Dx. Let d/M. We have two cases: Case I: = 2; and Case II: t = 1 or 3 < k < M. Below respectively define the parameter space 4hth for 6 and the context distribution D₁-
Case I: k = 2. Define y²2 = (-,,,0,,2) Recall that h = 1/ min K, d}. For V c [2h] with
[V] = h we define the context distribution D2(V) by letting Prx-D,(V) [ = {(e))ee U (e:)) 1
τ-n for any i [d]/V. In words, the sub-problem for the second batch contextual bandit problem with à arms. Among the arms, there are h arms which appear in each round, and the left arms appears with equal probability as -ー
In the case K >> h + 1, we simply repeat the first arm for K - -h + 1) times to construct the K-armed linear bandit problem. Without loss of generality, we still use Dz(V) to denote this context. For fixed and & E {-1, 1]d, we further define (2())E) by setting (V, E) = 0 for E and ()(),E) Eve2 for E [d]/V.
contextual bandit problem, we could view context X as a subset of [d]. Given permutation o S22 and a context X [d], define the context vector o(X) (o(1)) With slight abuse of notations,
Since the sub-problem
use D2(a) as the shorthand for D2(0((1, 2, ....., hl)).
Let the policy Ti be the policy for the first batch. Clearly, मं is independent of the context distribution. Let the distribution of mi be II, We then claim the following lemma.
Lemma 17.
min En,ell, Ex-D(o) [ & (2),)) dES,
$ h+1
Proof. Let A be the set of subsets of [d] with size h + 1. Let Z, (1,2,... + i} for
1 1 i < d -- h. Note that for any < i E d d- hh and S3 =(((Z)) & (2) , (f))
23

---

Published as a conference paper at ICLR 2025
implies that (X) a(h + t). Then have that
Σ oESa
1 d
Ex
(x) (2))),
Σ
16 (X) = 2iIBm.m. [ = o + :]]
dld i1) XEArES; 1=1
d-h
1
Bx
Σ
(x) 2x) o(h+
dl((d - h)) XEA
:=1 dES2
d1 Σ
1
Σ
ExpIl
(X) TI x, o(h + 1)
aiid -1-hh, h1)
XEA
d-h
1
E
Pr (x( =x]
Ilo I1oo
Z,, =o
dddd -1--h, 11) XEAIEX
0ES i=1
hl(d- - h- 16-11 1)!
Σ
Pramil (X) x]
d!
XEA.EX
hi(d - h-- - 1)!
Σ
d!
XEA
h!(dd h 1)!
|Al
(46)
h+11"
Then the conclusion follows easily.
Without loss of generality, we suppose that the identical permutation satisfies the condition in Lemma 17 i.e.,
E Em Ex=Dx(1) (X) & (1, ..] h
(47)
Define J {i= 2 h 1I,,,I,, EXxDII(X) d 1 (h+1)(d-h) }. then by equation 47 we have
2
that [J] > d d-h 2
Without loss of generality, we assume J = (h + 1, 2 h+ where & 2 d-h
the size of J. Then the context distribution is fixed as D2 (2(l))).
Case II: k 1 3 k <. M. We consider to construct the hard case for K-armed linear contextual bandit problem. We assume a minglog, (K), d} and b = d/a are both integers. Define 4 = 111, The context distribution D* is defined as the uniform distribution over X 0 (x x; = 0, Vi & ((i-1)a++) 1, ia], x, E {-1, 1), vi e [(i-1)a + 1, ia]} for S i b.
Now we start to analyze the minimax lower bound over all 0 y and the context distribution D described above. Let (t be the time schedule by running the algorithm G. Then there Ejes tj, where define
exists 1 < i < M such that ビ Eソ5r-1 T, < Ey<,T, To tg 0. Denote be the event where is the smallest number such that Ejge Ejss T
Ejs1t1 T++1 < Ejs44 441. Then holds that ΣM 1[8 1. To proceed, we have the lemma as below.
24

---

Published as a conference paper at ICLR 2025
Lemma 18. Let T be the policy for the k-th batch and T(x) be the policy for the t-th step. Fix
j [h 1, + fl. For V, we define
(0) = = ={{
d-h 2 T++1
T++T2 E a (b)n(++5)) [T[ 1. < <0] I| + j. > 0]] c2.
k == 2;
E
t= Tc-it1 a (x1.11/11)
[T[2,03 < 0]] Ck.
3: or 3 < M.
(48)
and R²(0)= = km Rt (0). Then for any h + iss si h
l, we have that
Σ
R2( 2 8(M + 1)
min
min kE[M),
TecK
T262 8d
y
d
PEY
With Lemma i8 in hand, noting that 2 d- 2 E. we obtain that
1
Σ
h+t
Σ ())
min
min [
Tack:
T2e2
D
32(M+
8
j=
dEy
Noting that the expected regret under parameter 0 is at least Regret (T) 2 > learn that
Eitt h+t j==
R2( we
h+t
1 D
Regret, ppp (T) 2 Σ
1
Σ
(200)2((/M))
(49)
D
PEY
j=h+1 BEY
Then there exists some 0* E y such that Regrelg. (T) 2 O(7/M). The proof is completed by definition of 7.
remains to prove Lemma 18
Proof of Lemma
18 Recall the definition of & for s k S M. We further define Hl as below.
H1 Ωt where Ω is the entire probability space:
KJM 6 (IddM) Yh + +1 S S h h++ [], where ny denotes the number of times the j-th arm is taken in the first batch;
Hz = {ng S max
6T
Hr = [nt < max 6MT 6 Indd)), V1 < i S b} for 3 S k < M, where n.
Σ Th _[X, = xk i.c. the number of times when the context is X.
Since the 7 independent of 0, then (He 1M is also independent 0. Using Lemma g it is easy to show that Pr, He) 2 1 10M7 for any S & M and any y.
Let p/ (0) E.g x~ n (X+t1//-)) [[ < E n Ha for = 1 or 3 S M. For = 2, we define p.: (0) E. ((M [[x = j. 03 < 0] [[ + j.03 > 01 N2].
Recall that F; denotes the event field over the first steps. For fixed V, we denote 03 be the vector in )' by reflecting the j-th dimension of 0h Using Pinsker's inequality (Lemma 7). and noting that &g n H4 are measurable with respect to FTE
()) + +/ > 1 (PTT--118 n Hd), Pr Tw-1 1 [E. n Hl.)
25

---

Published as a conference paper at ICLR 2025
for k or R l I M, where Pr'[-] denotes probability distribution over the first t steps. By definition of & and Hk. we have that
DKL. (Prg* Th [11& Hu], Prag As result, we have that
"( (( Hal) S max
6MTT-1
4 61n(aa))
S
a²
8
3
p)( + (f()))
2
(50)
4
Using similar arguments, and noting that nj S max (h+1)dd-h)Mb we have that
67,
(ln(dMM) conditioned on H2.
v DKL.
+)(0)+ 1}(00)
PKL.
(Pr (KI.(PrT))
[-H22 0
02
n E2), Pr Pr, 1122 n&))) ( 2 4'
Dy.07
(51)
Let CR- = 7 TREk for k = 1 or A M and 62
86 T262.
By the definition of R2( and noting
that 8 d 8 we have that
M
(0) 2
ProlEn n Halpp
k=
M
(6))
Σ Proy [& n (elpp (1)p))(0))). (c))).
using Pinsker's inequality (Lemma) 7, for any 1 S ks S M, it holds that
Profes n Hz] - Preg 1Ex n Hall
$V V/ DDx (Pr--1118 11 n Hx), Pr Proy
To-
- n nHxk)
[E
s 2M
Therefore, we have that
M
M
3 Pro(Ex
1
(0) Σ R
max
E& n Ho.
0
Ca 2
min Cc-
(52)
4
2M
8
k
k=1
k=1
Taking sum over V, we have that
1
1
Profe n (oDp
min Ck.
8(M + 1)
The proof is completed.
D A NEW MATRIX CONCENTRATION INEQUALITY WITH DYNAMIC UPPER BOUNDS
Existing matrix concentration inequalities (see, e.g., Tropp
2012h) play an important role in recent
works batch linear contextual bandits (Ruan al. 2021 Zanette al. 2021). For example, the proof techniques of Theorem 5.1 in (Tropp) 2012) may yield the following concentration bound in Proposition 19 (and the upper bound on Σn k X may be similarly derived). Special cases of
Proposition 19 (Taking W = I and = const.) includes Lemma 21 in (Ruan et al. 2021) and
Lemmas 11 12 in (Zanette al. 2021).
Proposition 19. Consider a sequence of independent PSD (positive semi-definite) matrices X1, X2...., X, IRaxd such that X₁ & W for fixed PSD matrix W and all 1 & k S There exists a universal constant e >> O such that for every 8 > 0 and e E (0, 1), it holds that
clu(d/8)
Pr
Xx x (1+6)
[[Xx]+
W
2 8;
(53)
6
cln(d/8)
Pr
Σ
Xx > (1 c) Σ E[XA]
W
2 1 - 5.
(54)
26

---

Published as a conference paper at ICLR 2025
However, achieve the optimal batch-regret tradeoff in the context-blind setting, need stronger version of Proposition| 19 where the uniform upper bound matrix W may be stochastic. In particular, we prove the following lemma crucial technical tool in algorithm analysis (especially for the Exp-Pol i cy procedure).
Lemma 20. Consider a sequence of stochastic PSD matrices W1, X1, W2, X2,....... Wn. Xn Rdxd
Let F& = (1W,,X1, X2..... Wk-1,- and Fo X1, N2,........ for each k (1,2.....n) Suppose We is PSD and increasing in k (with respect to the semidefinite order) and Xx & Wn for each k. For every ö O and E (0,1), letting E(8,e) 42+2))))2 In (n+1)d) Wn we have that
Wk) be the natural filtration and Ys = [[
Pr
Xx < (1+c)
Σ
Y2 + c(),c)
2 1
(55)
k=1
Pr X > (1
Σ Y c(
2 1 8
(56)
A=1
In Lemma 20 the stochastic matrix W,, upper bounds all matrices in {X1, .,,.... X,). When is fixed, the lemma reduces to Proposition 19 There are also few Freedman's 's inequalities for matrix martingales (see, e.g., (Tropp) T). However, in these inequalities, while the quadratic variation |[ becomes dynamic, the uniform upper bound W. is still fixed.
We note that if an extra poly factor were allowed in the + 4(c2+2e+2) In((n + 1)d/5) terms, the lemma would easily follow from Proposition [9 and an e-net argument. However, reducing these (oly factors is crucial to the full parameter range optimality analysis of our batch algorithm.
High-level intuition. One simple approach prove Lemma 20 to assume the upper bound matrix W, (correspondingly U in equation O were fixed, apply the ordinary matrix concentration inequality and finally take a union bound over an e-net of W.. However, such an approach would introduce extra poly(d) factors in the bound and lead to sub-optimal regret bound for our batch learning al algorithm. Our proof of Lemma follows the classical exponential moment method. However, we analyze the To
(E (X, (1 (1+ bound the trace of this exponential moment, we resort some deep analysis about Lieb's theorem on convex trace functions (Theorem 24 and Lemma 23). Besides, we also make the critical observation that the function Tr (exp (UT AU)) is bounded by Tr(exp(A)) A)) with an additive error at most d for any U such that U < I and any symmetric A (Lemma 28
exponential moment of a specially chosen matrix, namely W'. W; "
Before start the proof. introduce some basic properties of PSD matrices below, whose proof is deferred to Appendix D.4
Fact 21. For any two PD matrices A and B. A is equivalent to each of the following inequalities,
B-1 $ 1
(57)
1//2 1/2 & I,
(58)
B-1/2 1/2 & I.
(59)
We now start to prove Lemma 20 while the two helpful technical lemmas (Lemma 23 and Lemma 26 deferred to Section/D.. and Section D.2
Proof of Lemma 20
We first prove Equation equation 55 For each k E 1,,,, n.. let 2x =
+(c2+2222) WE and
Z 1/2 ))
Es = Tr
cxp
1/2
Z 1/2
Σ
[x,
-x+
2/1/2
Indeed, lose additional In(n + 1) term in the In(d/5) terms in Proposition 19 and we do not know if this compromise necessary.
27

---

Published as a conference paper at ICLR 2025
By Lemma 23
have that E[E,] I (n + 1)d. Therefore, by Markov inequality,
Pr
Amax
1/2
Σ - -1++
Zn 20
i=1
E(x; (1 (1 (1+ (// )
E Em ec
$
Pr
Tr
exp
1/2
(n + 1)de
ii=
which (by Fact 21
means that
Pr
Σ - < Czn
2 1 - (n+ + 1)de -
4(c2+2c+2)
Choosing C' = In((n 1)d/5) and recalling that Zn
Wn. we prove Equation equa-
tion 55
We then prove Equation equation 56 First we define
z 2x122) ))
Fy =
Tr
exp
Z 1/2
Σ ((1 ((1-))); c)8, - xi)
-xi)
Similarly, by Lemma 26
we have that [E[E,]
(n 1)d and
n
Pr
Amax
7z
Σ ((1 c),- - X1)
1/2 z
(60)
Zn 1/1 )
BLE ec
< Pr
Tr
exp
1/2
Σ ((1 e)8; -)){-)) Xii
S (n + 1)de C
which means that
Pr
Σ
c) X1) & CZn
(n+ + 1)de
Choosing C In((n 1)d/5) we finish the proof.
Corollary 22. Given sequence of stochastic random variables X1, X2,..., Xn such that 0 S X, S
W for any S S n with probability 1. Let Fx = o(1,, X2, X2,... Xa-1) 1) and Ys = E[ Fx For every 8 > 0 and O, have that
4(e2 + 22 2
Pr
Xx S (1+E)
Σ
Yv
In((n + 1)/0JW
2 21-60 6;
k=1
4(62 + 2r + 2)
Pr
X 2 6)
Σ Yk
In((n + 1)/8JW
> 8.
k=1
Proof.
Letting d = 1 and W₁ W for < n, by Lemma 20 we finish the proof.
D. STATEMENT AND PROOF OF LEMMA 23
Lemma 23. For each k E (1,
n... we have that
E [[x[FF] < E [[t]]
+ d.
Proof. Firstly, we introduce deep theorem from Lieb (Theorem 6, (Lib 1973)), which provides theoretical basis for series of concentration inequalities on self-adjoim matrices.
Theorem 24. Fix d dimensional symmetric matrix H. The function f(A) = Tr(exp(log(A)+ +H))
concave the d-dimensional positive definite cone.
28

---

Published as a conference paper at ICLR 2025
Based on Theorem 24
Tropp 2012) derived the corollary below.
Corollary 25. Fix a self-adjoint matrix H. Let X be stochastic symmetric matrix
E (exp( + H))] & Tr (exp (log Elex H)).
(61)
we continue the analysis below. Note that E [Eat is deterministic value. Throughout this proof, we will condition on F We calculate that
Given Corollary 25
E
[Ex]
k
2x 1/2 })
Tr
exp
4
1/2
Σ
(X, - +1)))
k-1
-11+ ))
E
Tr
exp
7
1/1
1/2
[(; - (1 (1+
7x 7/112
%//%" 1/2 (Xx: - 1x2
1=1
Tr
exp
Z 1/2
Σ(x; (X;
(Xi-(1++)()) (1++)
Ze 1-12 In
E exp 1/2112(xx x (1+ ()+,))+)Zz 1/2
1)
(62)
k-1
Zz v2 ))
Tt
exp
1/2 k
Σ (X; -X,-(11 -(1+))13)
[x;
(63)
k-1 - -xx=-(1+0)))
Tr
exp
2x 1/2 1/2
z 1-1 k-
k-1
2/1
1/2 2- 1/2 2=
k- 11125-1
2z
(x+)=()+))X))) (arl ) +
TTr
exp
2T-12
1/2
(64)
EA-1 + d.
Here equation 62 is by Corollary 25 equation 63 is by Lemma 27 (stated and proved in Section D
and the monotonicity of trace exponential with respect the semidefinite order (see (Petz) 1994..
$2.2), and equation is is by Lemma 28 (stated and proved in Section D.3 letting U 7 - 1 7
and
A by Fact
112 k-1
Ekn(x (X: (1 (1+))
Z
1/2 and one can verify that U 2 Z z 1/2
Similarly, we may establish the following lemma, whose proof is deferred to Appendix D.5
Lemma 26. For each {1,2,...., ..,,,..,n,, have that
[[E S SE +d.
D.2 STATEMENT AND PROOF OF LEMMA 27
Lemma 27. For each k E (1, ,n,, we have that
E exp 1/2 - (1 e)) 1/2) 112) [
$I I.
Proof. Throughout this proof, we will condition on F Let Un == 1/2 1/,," and V4 =
7-- -1/2y, 7 1/2 By the assumption in Lemma 20 and definition for Zk. have that 0 / Up x
29

---

Published as a conference paper at ICLR 2025
4(c++2+22) I and B[Ux] Vy. Therefore, 0 5 V4 4(2222+2)) I. We now compute that
exp 2 1/2 (X, (1+ (1+)) !
E exp (Ux - (1 + VV)]l
I+ (Un - + +)v( + (U (1+) Σ
1 (Ux - (1+ e)\22
=E
(65)
123
1
1
E
1+ (U - c)+
2 (U) (1 + v)V222
(UB (1 + +)
(66)
123
E
I+ (Uk (1+ + 2U: (1 + [
E
I + (Uk - (1++) + 10 4(1 + v)
(67)
4c
4(1 + 4(1+ c)
< E
I+ (U* (1+ + 4(E² + 2e + 2)
Uk +
Vi
(68)
4(c2 + 2E + +)
Here, equation 65 is by Taylor series expansion, equation 66 is by the fact that -I < (U; z v)
and X X² X - I)X 0 for 1 2 2 and -I x X x I. equation 67
because 2 + 4(1 + V22 - 2U - (1 +e)V = 2(Ux + (1++) y 0, and equation 68 is by
the fact that a(e² 4(c2-20+2) U? UR = U1/2 diee +2c+)) Uk - 1) U x and a(e² +(c2+2)22 V? V4
1/2 k
41c2 ((62+20+2) V/= 1) V/l 1/2 O.
D.3 STATEMENT AND PROOF OF LEMMA 28
Lemma 28. Let A be real symmetric matrix. For any U such that UTU x I, it holds that Tr(exp(U AU)) < Tr(exp(A)) + d.
(69)
Proof. We can assume without loss of generality that A diag ()1, Ag..... )1) and Ad S Ad-1 S A < 0 S x S ... S A1.
Let us write UT Q L to be its QR decomposition where Q is orthogonal and L L is an upper triangular matrix (and therefore L is lower triangular matrix). We claim that
x I, U I
(70)
where we define I == diag(O.... ... 0, 0.1....1 to be a rank j matrix. Note that U I
Q LL LQ. Therefore, to prove the claim, it suffices to show that L 1, x Ij. Since U TU X I, also have that L L QU QUTQQ' & I. Note that for any vector x, it holds that x (LI,) (LI,) )ar (Iy=)" T T.T T.TTTLI, T([aar)) < Jar. Therefore we conclude that T. I, (II,) (II,)) x I,, where the first equality holds because L is a lower triangular matrix.
Let d = >; - A > 0 for each i E f1, (1,,,..., e- 1}. d = de 2 0, and Z5 = 0 for each
jE (e + 1, d]. By equation 70 we then have that
UT AU
EAJU & Σi
j=1
By the monotonicity of trace exponential with respect to the semidefinite order (see, e.g. (Petz 1994) $2.2), we have that
4 Σ
Frouo))
TU AU)) < Tr
exp
1=1
exp
Σ Rx
Σ
exp(As) + +d= -Treexp(A) + d.
F=1
30

---

Published as a conference paper at ICLR 2025
D.4 PROOF OF FACT 21
Proof. We first show that A < B implies equation 58 By A < B, we have that B-A & O. Therefore, A 4-1/2Ba BA 1/2 - I= A- 1/2 ( A) A//2-1/2 is PSD, which means that A-1/2 BA--BA-111 > I. We then have B-1 1//2 < I. This is because we let M = A 1/2 + for convenience, for every vector 2; holds that
x' A/ B- 1 = xTM x (00-1//)T(MM1111 s (M-1/2x) 1(M-1123) = =
This proves equation 58 assuming A B.
We then show that equation 58 implies equation 57 Note that B 1/2 - -I क implies that B A-1 A ( 1/2 1)A-1 1/2 0, which leads to B-1 A-1
By symmetry, we can also prove that equation 57 implies A B, and therefore establishing the equivalence condition for both equation 57 and equation 58
Finally, A - B < 0 is equivalent to that B 1/2 AB 1/2 = B 1 A) 1/2 is PSD, which
is also equivalent to that B 1/1122 A00/2//B1// 1/2 & I, proving the equivalence for equation 59
D.5 PROOF OF LEMMA 26
Proof. Following the arguments in the proof of Lemma 23 suffices to prove that
E exp z 1/2 e)
Xk Zz) 1/2)
F - I
holds for each S n. Recall the definition Uj and V2 Lemma 27 In the analysis below,
we will conditioned on F By the same arguments in the proof of Lemma 27 and noting that
-I (1 V UR * we have that
E exp % 1/2 ((1 <)8r xz) 11
E exp
((1 V) Uk)
I ((1 c)V2 -Ua) ==1 c)Vis Un)²
1
1 ((1 e)V₁ -Ux)'
< E I ((1-c)V, - U.) 5 (11 - <)Ve - U2) Σ 1!
1
c)V, -Ua)²
* E
I+ ((1((1 cV Uk) 2((1 V) u
E
I+ ((1 - - Uk) 4U2 + 4(1 V/2
4e
4(1 c)2c V/
E
c)Vi - Uk) + 4(c² + 2 2) I+ ((1 ((1-)V
Uk +
4(e + 2e 2)
I I.
The proof is completed.
31


Reviews:
[{"review_id": "rDnRZVTmf2", "reviewer": "Reviewer_kW9Y", "summary": "The paper addresses the problem of batch linear contextual bandits, a type of online learning model where decisions are made sequentially, balancing exploration and exploitation. The authors design algorithms for both context-blind and context-aware settings of the batch linear contextual bandit problem. In the context-blind setting, the learner cannot use current batch information to make decisions, while in the context-aware setting, the learner can observe the context in the current batch, allowing potentially more adaptive decisions.", "questions": "1. The algorithms are based on restarting Lin-UCB at every epoch. How does this relate to designing forgetting-based episodic RL algorithms?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The contributions are: \n1. **Regret Bounds and Tradeoffs:** They analyze the regret, or performance loss, for different batch numbers and prove that their algorithms achieve nearly optimal regret bounds (up to logarithmic factors) across varying batch sizes. For instance, they demonstrate that as few as \\(O(\\log \\log T)\\) batches suffice to achieve nearly the minimax-optimal regret without constraints.\n\n2. **Simplification of Algorithms:** Compared to prior work, such as Ruan et al. (2021), the authors propose a simpler algorithm that is more practical to implement and works for all time horizons \\(T\\) as long as \\(T \\geq d\\) (where \\(d\\) is the context dimension). This represents an improvement over previous methods, which required large polynomial relations between \\(T\\) and \\(d\\).\n\n3. **Matrix Concentration Inequality:** A significant technical contribution is a new **matrix concentration inequality** that depends dynamically on upper bounds, which is useful for the algorithm’s exploration policy. This inequality could be valuable for other research areas in machine learning due to its novel structure.\n\n4. **Context-Aware Performance Gains:** In the context-aware setting, they show that observing the context allows the learning algorithm to achieve better regret bounds by taking advantage of additional information in each batch, demonstrating that optimal regret can be further improved compared to the context-blind setting.", "weaknesses": "1. I believe $m$ and $n$ represent the same quantities (albeit separated by batch index). So I don’t see how this is an improvement over Zanette 2021. See lines~276-281.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eSNp0Ot25I", "reviewer": "Reviewer_XcK9", "summary": "The paper studies the number of batches vs regret tradeoff for contextual linear bandits. The authors propose an algorithm that achieves nearly optimal regret for a given number of batches M.", "questions": "Could the authors include the computational complexity of the proposed algorithms as a function of K, d, T, M?\nCould the authors add motivation for stochastic contexts as this is the main setting in the paper? e.g., what applications would satisfy the stochastic i.i.d. context assumption?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper considers batch learning in stochastic contextual linear bandits which I believe is an important problem. It proves upper and lower bounds on the regret given number of batches M.\nExp-Policy (algorithm 2) is introduced to solve the distributional optimal design problem needed to design the policy in each batch. The algorithm is novel and simple unlike algorithms proposed in Ruan et al.\nTo the best of my knowledge multiple of the analysis techniques proposed are novel including the matrix concentration inequality in Lemma 20. \nThe regret upper and lower bounds are nearly matching.\n\nOverall, the paper introduces important algorithms and analysis techniques for contextual linear bandits, as well as being the first to prove the optimal regret bound dependency on the number of batches.", "weaknesses": "The computational complexity of the algorithms scale linearly with the number of actions which can be very large. However, this is justifiable since this is a challenging problem even without the batch learning constraints.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fAGZAeov3n", "reviewer": "Reviewer_sv76", "summary": "This research explores batched linear bandits, in which the learner decides the number of arms to pull in each batch, with rewards for the selected arms revealed only at the end of the batch.\n\nThe proposed algorithm functions within a predefined maximum number of batches denoted as $M$. It aims to minimize regret. Theorem 2 illustrates the balance between regret and $M$, indicating that the trade-off approaches a near-optimal order, as shown by Theorem 4. The findings suggest that $M = O(\\log \\log T)$ batches suffice to achieve asymptotically minimax optimal regret.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The theoretical strengths of the paper include providing a tight bound on the expected maximum width, $\\mathcal{W}(m,n)$. This enhancement builds upon the results of Zanette et al. (2021) and mitigates the limitations identified in Ruan et al. (2021). Additionally, the matrix concentration inequality presented may be of independent interest.", "weaknesses": "1: Theorem 4 is compared with Gao et al. (2019), yet the more pertinent lower bound by Han et al. (2020) might provide a more relevant comparison. It is unclear why this comparison was omitted.\n\n2: The paper overlooks several significant works on batched multi-armed bandits and linear bandits for asymptotic $T$. \n\n3: The paper often neglects to condition on $F_k$ throughout many parts of the proof. \n\nAdditionally, a minor notational correction is recommended: \"$\\epsilon + t$\" described as an independent sub-Gaussian noise with zero mean should be correctly noted as \"$\\epsilon_t$\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uhNhKaEgE2", "reviewer": "Reviewer_DVV4", "summary": "This paper studies the batch linear contextual bandits with stochastic contexts. They design some batch learning algorithms and prove that they achieve the optimal regret bounds up to some logarithmic factors for any batch number, number of actions, time horizon, and dimension. They also develop some new techniques which may be of independent interest.", "questions": "- Could the authors consider including additional experiments in this section? Additionally, what would be the key challenges in implementing this algorithm?\n- Could the authors provide more detail on the hidden constants in the upper and lower bounds? Specifically, what are their magnitudes, and what parameters do they depend on?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The paper presents near-optimal results for this type of bandit problem, with matching upper and lower bounds that may represent a definitive solution in this area. Additionally, the authors introduce a novel concentration inequality tailored to this problem, which has the potential to be valuable for addressing other bandit problems as well.", "weaknesses": "It would be better if some numerical experiments were included.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)