Efficient Batched Algorithm for Contextual Linear Bandits with Large Action Space via Soft Elimination
Authors: Osama Hanna
Lin Yang
Christina Fragouli
Venue: NeurIPS 2023 poster (2023)
Keywords: efficient bandit algorithms
contextual linear bandits
TL;DR: We provide the first batched algorithm for contextual linear bandits with large action spaces achieving: regret bound $\tilde{O}(\sqrt{T})$; $O(\log\log T)$ batches; polynomial time complexity in $d,T$.

Abstract: In this paper, we provide the first efficient batched algorithm for contextual linear bandits with large action spaces. Unlike existing batched algorithms that rely on action elimination, which are not implementable for large action sets, our algorithm only uses a linear optimization oracle over the action set to design the policy. The proposed algorithm achieves a regret upper bound $\tilde{O}(\sqrt{T})$ with high probability,  and uses $O(\log\log T)$ batches, matching the lower bound on the number of batches (Gao et al., 2019). When specialized to linear bandits, our algorithm can achieve a high probability gap-dependent regret bound of $\tilde{O}(1/\Delta_{\min})$ with the optimal  $\log T$ number of batches, where $\Delta_{\min}$ is the minimum reward gap between a suboptimal arm and the optimal. Our result is achieved via a novel soft elimination approach, that entails $\text{``}$shaping$\text{"}$ the action sets at each batch so that we can efficiently identify (near) optimal actions.

Efficient Batched Algorithm for Contextual Linear Bandits with Large Action Space via Soft Elimination
Osama Hanna
Lin Yang
University of California, Los Angeles ohannaducla.ed.
University of California, Los Angeles linyangducla. edu
Christina Fragouli
University of California, Los Angeles christina. fratioul.. cecsouulicca..... Sucla. edu
Abstract
In this paper, we provide the first efficient batched algorithm for contextual linear bandits with large action spaces. Unlike existing batched algorithms that rely on action climination, which are not implementable for large action sets, our algorithm only uses linear optimization oracle over the action set to design the policy. The proposed algorithm achieves regret upper bound Ö(VT) with high probability, and uses O(log log I') batches, matching the lower bound on the number of batches [ When specialized linear bandits, our algorithm can achieve a high probability gap-dependent regret bound of Ó(1/Amin) with the optimal log T number of batches, where Amin is the minimum reward gap between suboptimal arm and the optimal. Our result is achieved via novel soft elimination approach, that entails "shaping" the action sets at each batch that we can efficiently identify (near) optimal actions.
Introduction
In contextual linear bandits, a learner interacts with an environment over T rounds: in each round t the learner observes a (possibly different due to context change) set of actions A, RRd plays one of them, and receives reward that follows a noisy linear function parametrized by an unknown minimize regret how much reward loses over the T
vector in IRd. The objective of the learner rounds by not always playing the "highest reward" (optimal) action. To achieve this, the learner at each round updates policy (its method select what action play) based on what it has learned from all past actions played and rewards observed. Linear bandits form the special case where the action set always the same, i.e., A. = for all rounds Contextual linear and linear bandits have been widely investigated due to their significance in both theory and practice (eg., see (24).
Batched Setting. In numerous real-world policy a limited (small) number of times. constraint may stem from factors such as computation or communication considerations, or may be imposed by the nature of the application, as is the case in multi-stage clinical trials or online marketing campaigns with high response rates, where it is not feasible update the policy after each response. Similarly, the use of crowdsoureing platforms the need to conduct consuminn simulations in reinforcement learning may require policies with limited adaptivity. As result, there has been significant interest designing algorithms that can achieve the optimal regret with limited policy switches (30 3 31 13 12
cases, the learner may be restricted to change the
32 [6] This setup is known as the batched contextual linear bandit problem: the T rounds are partitioned into batches, and the learner can collect rewards and update the action selection policy only at the end of each batch.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Large Action Space. Contextual linear bandit applications frequently need to explore an extremely large (even continuous) set of actions, e.g., millions of products to be recommended. As other examples, in the classical bandit problem of clinical trials, each decision involves selecting a treatment option from a potentially infinite set of mixed treatments [[5]. In manufacturing problems, the goal is often to maximize revenue by selecting from a very large set of decisions, with the revenue associated with each decision being unknown [36] Additionally, in applications where actions correspond to images in database or high-dimensional embeddings of complex documents like webpages, the set of actions can be vast [26 51. As a result, there is a strong interest in algorithms that can be efficiently implemented when the action space is large infinite
39 41
While paputaationll--fffiiice
batched algorithms exist for contextual linear bandits with small action sets, and efficient ones that are not batched exist for contextual linear bandits with large action sets, to date, there are no efficient batched algorithms that can handle large action spaces. Existing batched algorithms for contextual linear bandits 32 16 rely on action elimination that requires linear scan of the action set; while efficient non-batched algorithms for large action spaces do not extend to the batched setting 22 16
(see related work in the following for more details).
Our Contributions. In this paper, we provide the first efficient batched algorithm for contextual linear bandits with nearly optimal regret upper bound of O(d with high probability, while using Olog log batches, which matches the lower bound on the number of batches required to achieve -typeee regret bounds [3.. For linear bandits, our algorithm can attain a high probability
gap-dependent regret bound of Ôid Amin) with the optimal log T number of batches [3, where Amin represents the minimum reward gap between suboptimal arm and the optimal.
Our algorithm for linear bandits, that we term SoftBatch, builds on form of "soft elimination". Our observation is that, a good algorithm should be able to approximate the gap A(a) between each action a E A and the optimal one with (a)) accuracy; and if we can do that, then we can use this knowledge to limit the number of times we play suboptimal actions, as well as use this knowledge to select which actions we want to play at all. As essentially all batched algorithms do, at each batch we select and play (a small number of) actions that enable to estimate well the unknown parameter vector without incurring large regret. In particular, for each batch, we choose a set of well-behaved basis actions (e.g.. a barycentric spanner 77, established by calling optimization oracle polynomial times. However, instead of selecting at batch m, vectors from the "true" action set A, we consider virtual "weighted" sets Am, where each action's 's magnitude is weighted inversely proportional to the estimated gap Maa) and select vectors guided by these weighted action sets. Then we play each basis action a number of times inversely proportional to the square of the estimated gap A(a) to preserve small regret. This in return provides us an accurate estimator for the optimal parameter by the benign properties of the basis actions. Thus our approach implements a form of soft elimination (shaping) of the action set, where the actions closest the optimal become increasingly dominant. A crucial part in our design is that we never actually calculate the gaps A(a) for all actions a E A (only for the basis actions). The exploration policy we propose uses solely a linear optimization oracle applied to the original action set.
Our contextual bandit algorithm utilizes recent reduction technique 18 to transform the problem into a linear bandit problem. We incorporate the reduction into our batched linear bandit algorithm, by constructing an efficient linear optimization oracle for the exponentially large action set in the reduced problem using a linear optimization oracle for the original action sets (contexts).
Our proof techniques may be of independent interest. We develop a novel approach to bound regret in linear bandits, we design an efficient exploration policy using inverse squared gap weighting, and a simple method to handle the case where the action set does not span IR,, where d is the problem dimension. Our approach avoids the necessity of imposing assumptions, such as the one in [4], which entails having a subset of d actions forming a matrix with determinant at least nd for constant r. These assumptions can be strong, particularly when dealing with changing action sets, and may not hold after modifying the action set, for instance, by climinating or weighting actions.
Related Work. Contextual linear and linear bandits have had significant impact both in theory and practice N I 28 27 24
26 37
[0]. The best performing algorithms achieve a regret bound
Ö(dVT) Σ. matching the regret lower bound ((dvT) 24! The same algorithms achieve a
1Ô hides log factors.

---

nearly optimal regret upper bound Ō of by Amin. However, the resulting policies require updates at every time step and involve solving
Amii if the minimum gap of suboptimal arms is lower bounded
non-convex optimization problem, which not practical for large action spaces 33 |
Batched algorithms. Existing batched algorithms for contextual linear bandits 62
16
[8]
have
achieved nearly optimal regret upper bounds of O(dvT). However, these algorithms rely on action elimination, which involves either performing a linear scan on the action set or solving an optimization problem over the non-convex set of good (not eliminated) actions to design and implement the policy at each time step. Similarly, batched algorithms for linear bandits 25 12] also rely on action elimination. Although, unlike contextual bandits, the elimination constraint in linear bandits can be linear, which can be exploited to efficiently compute the policy (under certain assumptions) [ resulting in an (dd4/3/T) regret upper bound, it requires solving an optimization problem over the action set with elimination constraint. This can be much harder than solving the optimization problem over the action set without additional constraints for some sets, such as the non-convex set resulting from the reduction of contextual to linear bandits [
Efficient algorithms for large action spaces. There is a long line of work on efficient algorithms for linear bandits that only rely linear optimization oracle over the action set However, these algorithms cannot be extended to the batched setting without extra assumptions on the action set, and more importantly, they do not extend to the batched contextual setting. Existing efficient algorithms for contextual linear bandits 6 41 I can achieve O(d9/2 regret bound, but it remains unclear if they can be extended to the batched setting, particularly given the challenge posed by changing action sets. Another line of work attempts to design efficient algorithms using bashing-based methods to approximate the maximum inner product [39, 22], but these methods result in complexity that is sublinear but still polynomial in the number of actions.
19 20
Table 2 in App. A summarizes how our results position w.r.t. related work.
2 Model and Notation
Notation. We use [n] for a natural number n to denote the set {1,.... n): 1(E), for an event E, to denote the indicator function which returns 1 if E holds and 0 otherwise; B, fa E RdI|aa|2 S r} to denote the ball of center 0 and radius S, = {a RBI||a||2 r to denote the sphere of center 0 and radius r; and ||allv Va Va denote the matrix norm of a vector E Id with respect to positive semi-definite matrix V. Table in App. summarizes our notation.
Contextual Linear Bandits. We consider contextual linear bandit problem over horizon of length T, where at each round t E [T]. the learner receives a set of actions Ar S TRd sampled from an unknown distribution D independently from other rounds. The learner plays action a E A and receives reward Ft- = (ac, 0.) + Te. where 0, is an unknown system parameter vector with 0, E Rd, and ny is noise that is zero mean conditioned on the filtration of historic information (A1, "1, Ae. a.). The learner adopts a policy that maps the history (A1, 01, Fi,'.. .A)) to distribution over the action set A,, with the objective of minimizing the pseudo regret defined as
T
RT Σ sup (a- a,, 0.)-
t=1 dEA.
For simplicity, we assume that Ar is compact for all E [T] almost surely, which ensures the existence of an action ag E A, that attains the supremum supaE,A, (a, 0). Non-compact sets can be handled using sufficiently small approximations. We also adopt the following standard assumption [4]
Assumption 1. (Boundedness.) 0. E B1, A, S B1, and Irel S almost surely Vt E (T).
Changing the action set over time enables to model contextual information. If the action space fixed, namely, A, AA for for all E [T], the problem known as Linear Bandits. For Linear Bandits, we denote an optimal action by a" arg max.eA (a, 0,) and define the gap A (a* a, 0.) for all actions a A.
Linear Bandits.
Batched Setting. In a batched setting, the learner is only allowed to change the policy at M pre- chosen rounds, where M is the number of batches. Batch includes Tm rounds, m [M], with ΣM= T.,. = T. In each batch, the learner adopts a policy æ that takes as input the action set A, along with all the previous history except for rewards observed in the current batch, and outputs
3

---

distribution over the action set A.. In particular, the rewards of the actions pulled in the current batch are utilized solely update the policy the end of the batch.
Regularized least squares. Let (a,, ri) be a sequence of n. pulled actions and observed rewards over n rounds. The regularized least squares estimate 9 of f, based on this action-reward sequence can be calculated as
-= 0=V-
ri0
where +I+ ata]" and is the regularization parameter.
Goal, Our goal is to design efficient batched algorithms for Contextual Linear and Linear Bandits with large (even infinite) action spaces that achieve (nearly) optimal regret.
We will do so by making use of the linear optimization oracles defined next.
Definition 1. A linear optimization oracle for set A is function (AA:-) which takes input 0 E B, and outputs ()A;0) E A with (O(A: 0), 0) = suPac,A (a, 0). An approximate linear optimization oracle with additive error at most for the set A a function (A4;;) B, A that satisfies (Or (AA: 0). 0) 2 A (a, 0) -e, -e, A0 E B₁. An approximate linear optimization oracle with multiplicative error a for the A function O (A:.) B A that satisfies (Ox (A; 0) 2 (1 a) s (a, 0), 40 B1.
Assumption 2. (Linear optimization oracle.) We assume that we can access a linear optimization oracle O(Ac; for each set of actions As with running lime at most Top and space complexity Mopt
We note that assuming a linear optimization oracle over A, is natural even if the learner perfectly learns the unknown parameter vector 0., the learner still needs to solve SuPsEA, (a.0.) to minimize the regret in
since
Efficient Soft Elimination Algorithm for Linear Bandits
In this section we propose and analyze an algorithm (which we call SoftBach and describe in Algorithm M for linear bandits, that is, when Ar A.
3.1
Main Result
The following two theorems, proved in App. D and respectively, formally state that Algorithm J achieves (nearly) optimal regret using M [log log T +1 batches with sample and time complexities
polynomial in d and linear in T. We provide the algorithm description in Section 3.2 and proof outline in Section 3.3
Theorem 1. Consider a linear bandit instance with action set A C Rd and horizon T. There exists a universal constant C and choice for the batch lengths such that Algorithm Minishes in at most M [log log T + batches with regret bounded
RT S &CyTTlog log T with probability at least 1
where y 8d / CD (log(1/8) + log CL = ed and i is parameter. Moreover, if A with A. we have Aa 2 Amin then there exists a choice of batch lengths so that Algorithm finishes in at most M log, I' batches with regret bounded
22
Rr S C
log T with probability at least 1 8.
(4)
Amin
Our regret bounds achieve nearly optimal dependency on T, and match the best known regret bounds of ((d3/2 for (unbatched) efficient contextual linear bandit algorithms 66
while losing
a v factor when compared to the ((dvT) lower bound [24. This extra v factor is due to relying on the best known method design a notion of spanner of the set of actions (as we explain in section 3.2 with radius VCL O(vd) using linear optimization oracles. Any future improvement that reduces the radius from ((vi) to O(1) will immediately result nearly optimal regret bounds for Algorithm II The following result upper bounds the time and space complexity.

---

Algorithm 1 [SoftBatch] A Batched Algorithm for Linear Bandits
Input: action set C F4, horizon T, number of batches M, batch lengths (Tm JM confidence parameter 8.
2: Let A'' - AU B1/r; =
= edd, 7 /dy /Cl/CL/ (log (log + log
3: Initialize: 0, = 0, af is random action in A. A (a) = 1 Va E A', and To =
4: for m = 1 : M do
5: Calculate {#1,.... aa) = LWS 7m (T (Tm-1/(87), am 0m)
6: For the set {a....., aP) assign (i)) d:
Vi E [d].
7:
for i d do
8:
If a; & Birr, calculate (m( m8))Tm/8
(a a;, 0m) and pull it nm
times. go to step 10 if the number of pulls in the current batch (1+ Tm-immm (m. ((,))
reaches Tm. Terminate Algorithm ii the total number of pulls reaches T.
9:
Pull action dn on for max (0,T,,,,,, Tm Ei= n.. (7)) times.
10:
Compute the regularized (with À = 1) least squares estimator Vn = I+ Tm " and V Tm r:ū;, and ã; is the action pulled in i-th round of the batch.
0m+1
Update m J (A: 6m+1). 11:
Theorem 2. Algorithm I finishes in Ö(T dt + d' + Tape M) runtime and uses Ö Mom) memory, where Topt, Mopt are the time and space complexity of the linear optimization oracle.
We observe that unlike algorithms that require a linear scan on the action set, our space and time complexities are polynomial in the parameters d, T, and Tapt-
3.2 SoftBatch (Algorithm D Description
Intuition. The main intuition behind SoftBatch that, we do not need to necessarily eliminate suboptimal actions; it suffices to be able to select and play small set of unique actions C. in each batch m, that allows to estimate increasingly well the parameter vector 0, and the best action at while playing suboptimal actions for small number of times. Our algorithm proposes novel way to select such sets C.m efficiently, through a form of "action set shaping" that we will describe in this section. Additionally, to learn 6, while achieving (nearly) optimal regret, SoftBatch plays each action a E C. a number of times x 1/42, where Aa = (a. a, 0.) is the gap for action a (i.c., we play the suboptimal actions in C. for small number of times as not accumulate regret). SoftBatch enables to estimate the gap A, within a constant factor for any action a (yet only does so for limited number of actions in each batch), and essentially uses the gaps A. guide which actions to play and for how many rounds each.
Steps. SoftBatch (Algorithm 1) takes as input the action set A C Rd the horizon T, the number of batches M, and the batch lengths (Tm) MM and operates as follows
In batch m, the algorithm starts with a current estimate of the parameter vector 0., which we call On. and an estimate of the optimal action a* which call at note that given these, we are able to estimate for any action a E A the gap (a) = (a,, a, Om (but we will only do so for the actions the algorithm actually plays). The algorithm then calls LWS, a Linear Weighted Spanner subroutine (described in Algorithm 2), that it feeds with an augmented action space A'' A U Bi/T for reasons we will explain later. LWS selects dl actions C. = {ar, ...)) to play in batch m (note that some of these may belong to Bi/T and will in this case not be played). Each of these actions a; is pulled nmm (i) X A,, [r times, where TT.) is uniform exploration distribution with value 1/d for a(t)
all the d actions. We show in the proof of Theorem I that Σí n (i) < Tm. Vm [M], with high probability. To guarantee that the length of the batch is Tm, the algorithm pulls of for the remaining rounds, if needed. At the end of the batch, the algorithm updates its estimate 0 41 of the unknown parameter vector using regularized least squares.
We discuss how to select A1 and (I'm } in App.
5

---

The remaining core part of the algorithm to discuss is the subroutine LWS, and we do so next. We start by providing our reasoning behind the LWS design.
The LWS A Algorithm. Recall that we want LWS at each batch m to select vectors {as} S A' such create least-squares estimate 0 of O. that allows an accurate estimate of the product (a, 0.) for all E A.. It is well-known (see (241) that the error in estimating (a, 0.) is proportional to ||al|v=,,, where Vm. = -I+
that, by playing each n. (i) times,
Ti aga; is the least squares matrix ++E Di=1
used to estimate mm+1- Thus, essentially want LWS to select d vectors {a:) that maintain small ||a lv for all actions a E 1 We can do so using what is called a G-optimal design 23
Definition 2. (G-optimal design) For any set A C R subset S S A, together with a distribution t over S is said to be C-approximate optimal design for A if for any a E A
||a| S Cd,,
(5)
where V, -ares (i)a,a When C this is referred to as G-optimal design.
Notice that if we were to play each action a, for (i( times, then V, would be (approximately) a normalized least squares matrix since V, + I/n V/n, and hence, |||| S
<|a|| 1/n.
It is well-known that for any compact set, there exists a 1-approximate optimal design
with
|S] = d. However, computing an 1-approximate optimal design is NP-hard in general 14 35 even
for small action sets. Computing a 2-approximate optimal design can be done in polynomial time 38 but the complexity scales linearly with the size of the action set. Instead, we adopt an approach introduced in 771 which efficiently constructs an O / ((vd) -/ppppoxxiimattee optimal design using only a linear optimization oracle. This relies on the concept of a barycentric spanner, which we define next.
Definition 3. (Barycentric spanner) For any set AA C TRo,, subset S = {aj,".. (di,"""aaa)) .az) S. A is said to be a C-approximate barycentric spanner for A if any combination of vectors in S with coeficients in [-C,C]
can be expressed as a linear
It is easy to see that C-approximate barycentric spanner together with uniform distribution π(i) = 1/d results in CVV d-appoxximate optimal design [19 41) And importantly, C-approximate barycentric spanner for a set A can be constructed using at most Odd logo d) calls of a linear optimization oracle over the set A [99]
However, this is still not sufficient for us. Even though we can efficiently construct Cydaapproi optimal design for A, we do not want to pull these arms according to uniform distribution; we want to pull action a; with estimated gap (a,)) for (im = [T(i)Tm/(1 + (Tm-1Am (a) (8 times to control the regret (which can be thought of as using weighted distributior But if we do not use the uniform distribution, the resulting least squares matrix Vm may not satisfy that ||lll=.. is sufficiently small for all actions a.
To account for this, instead of finding C-approximate barycentric spanner for the set A, each batch consider virtual action set An, which we define as
Am = (om E A), dm (a) = 1 + mm Am)
a
where 7m (Tm-1/(87) and find actions {ai,.... aa) A such that (a:)) forms C-approximate barycentric spanner for Am. The least squares matrix batch m can be bounded as
+ 7m Am (ar) a.a = Σ T() Tmm om (am(aa)mmma))
m(i)Tm/8
V m = II
7m (i)a,a
(7)
with high probability
F where (1) is the number of times action a; is played in batch m and ag o That is, playing actions {ai,... .a)) A for (i) times each, can equivalently
'Adiin reward samples from the estimated best action a', can only improve the least squares estimator. *This summation assumes finiteness of the set which suffices for our application.
'The technique of inverse gap weighting was employed in 4I albeit with a different weighting approach using inverse gap instead of squared inverse gap, as utilized in our proposed schemes.
"We show in the proof of Theorem I that Ed, (i) < T.m Vm E [M] with high probability, hence, all the required n. (i) action pulls can be finished within the batch.

---

Algorithm 2 Linear Weighted Spanner (LWS) Algorithm
1: Input: set of actions A, parameter estimated best action â, estimated parameter Cis where e; is the i-th basis vector of dimension d. Let A [01, 0d]
2: Initialize:
3: Let C' (1), (aa) (ā a. a.6). ((a) a/(1 n)(a))
4: for i= L.... .d do
5: Find with (0, a) = det(ā, A-i,, Vā E R.d.
6: at = LWWAArgax(AA 110 17, a 0) a = LWW-ArgMxxAA; [10]2 n, 0).
7:
a arg maxbelat a- ((((), 03|. ā. = x(aa).
8:
9:
for = 1, d do
10:
Find 0 with (0, a) = det(ā, A-i, Vā E Rdd
11:
A at = LW-ArgMax (A; T '1, 0).a) LW-ArgMax(A;
T0p a 0).
a= arg maggaxbe
(b(b), 0\|-
if (d))( A A-1)
C' [A]] then
14:
0: a, a = ②(a). go to line Return: d1," .. Odd
16:
be thought of as playing actions fó(a1). ,((a)))),,,(aa)) E An for aii[Im times each; and since {ó(a1), ... (((a)) form an approximate optimal design (through a barycentric spanner) for the set Am, the resulting least squares matrix will lead to small |m (a)llv=. values. In our proofs we show that a small enough [[om(a)) v... implies ||a|ly.. O(A,) result of the scaling in ø(a). We prove in Lemma 5 in App. D that this allows to estimate A. within constant factor, which is all we need.
Intuitively, the virtual set A. weighs the actions inversely proportional to the estimated gap Am (a) and batch length VT--1: the larger the gap and Tm-1. the smaller magnitude the corresponding action has; this implements form of soft elimination (shaping) of the action set, where the actions closest to the optimal become increasingly dominant as the batch length increases while the remaining fade out to zero. As result, as m increases, the span of the optimal design focuses on the space where actions have small gaps, allowing to better distinguish among them.
To complete SoftBach (Algorithm I), one last step is missing. LWS (Algorithm follows standard steps (in Algorithm 2 see 7 for detailed explanation) to calculate the C-approximate barycentric spanner for Am. But to follow these steps, requires the ability to solve the non-linear optimization problem sup,e 4 (pm (a), 8), since Φm (a) = a/(1 + 1mm (8))(87) nonlinear in a. To do so, we will use an approximate oracle with multiplicative error, that we term LW-ArgMax and describe next.
LW-ArgMax Algorithm. LW-ArgMax (Algorithm 3 constructs an approximate oracle with (1 - a multiplicative error for the optimization supa (0m (a), 0). This is sufficient: we show in Lemma that Algorithm 2 can use LW-ArgMax compute C/o-approximate barycentric spanner for An
Recall that, before providing the action set to Algorithm SoftBatch extends to A' = AAUBI
This guarantees that: A'' spans Rdd (required to find a barycentric spanner (7),, and supas,A (a.0) 0) 1/T for all 0 with |0]]| = 1 which implies that any approximate optimization oracle with additive error less than 1/(2T)) has multiplicative eттor of at most 1/2. The extension of the set A results in the barycentric spanner possibly containing points not in A. However, we show that removing these points only affects s v-llv-1 by constant factor, since B /r has small radius. Extending the
"A related problem was faced in 41 but with a different function hence, the resulting strategy does not apply in our case. Both 21 and our solution use the standard idea of line search, albeit with different steps and different number of iterations. The proof that our line search provides approximate optimization oracle turns out to be much more involved than that of [4]].
'The linear optimization problem max (a, 0) can be solved by comparing max.gA (a, 0) and max (a,0) = 1/T.
7

---

Algorithm 3 LW-ArgMax Algorithm
1: Input: set of actions A, E St, parameter 7/ estimated best action á, estimate 0, horizon T.
2: Let A(a) = (ā a, 0), x(a) = a/(1 + m)(a)).
3: Let W = 3log T. N = 36W log" (T),
1/6 log T, = -xx((1)))127772220g
4: Initialize 2 2W
5: for = 1,. .N W+L do
6:
(1 + 1/ + +2 1 n
7: 0; 03 (A; // /|00
8:
t 28.
9:
Return: arg max aata ().
set A A' also handles the case where the span of AA is smaller than Rd that was typically handled in literature by constructing basis of A which can be complicated for some sets.
LW-ArgMax then builds the following observation (proved part of the proof of Lemma
aEA'' arg max (p(a), ()(a,))())))))))))) 0)) arg max sup L=(a),
(8)
aEA' =20
where (a)a) 2-(1+1/W)
1+/ (L+T))))) and A(a) = suPbE.A (b 0.) Va E A
By choosing W to be large enough, the left hand side of becomes good approximation for (o(a), 0). For a fixed 2, the supremum on the right hand side of 8 reduces to linear optimization over the set A' (that we solve using an approximate linear optimization oracle). Although the optimal value of z is not known, it can be bounded (see equation
(25) in App. B); thus Ma-Argaax scans between upper and lower bounds on the optimal z with constant multiplicative step. The pseudo-code is provided in Algorithm S
3.3 Proof Outline for Theorem 1
We start by proving that LW-ArgMat is approximate linear optimization oracle for the set À with 1 - eexp(-3) multiplicative error. The result is stated in Lemma I and proved in App.
BT be given parameters, and A be given set. Let A(a), é(a) denote A(a) (ā aa-a,00, d(a) a/(1 + na))). If Biyr S A C B1, In| S T and
Lemma 1. Let T 2 3,7 E i, E Rd
1/2 S + (a))) < T Va A. then for any St, LW-ArgMax outputs element E A such that
(o(a),0) 2 exp(-3)
sup (((()))))))
(b,0).
The conditions of Lemma I are easy to verify for all batches m; namely, B AAC B, holds as we extend the set of actions by adding B1/T before feeding it into Algorithm and the condition 1/2 < + (a) < T Va A is proved in Theorem for all the inputs fed into Algorithm S
Given the result of Lemma I we next show that Algorithm finds a C/o-approximate barycentric spanner of the set Am, Vm E [M]. This done by slightly adapting the proof of Proposition 2.5 in 7 to work with approximate linear optimization oracles instead of exact oracles. The result is stated the following theorem and the proof is provided App. C for completeness.
Lemma 2. Let T R. Rdd E Rdd be given parameters, and A be a given set. Let A(a), ((a)
denote A(a) (a a. 0), <baa) a/(1 + m))))). Suppose that (o(LN-ArgMax(()), 0) > a supaEA (o(a), 0), then Algorithm 2 computes C/o-approximate barycentric spanner for the set Ā {o(a)]a E A} with at most Od (ogo(//a)) calls to LW-ArgMax.
To build our regret bounds, essentially prove that number of pulls of -(1)
J for action a
enables to estimate the gap (., (a:) within constant factor of the real gap A.,- To do so, we start by providing an error bound for estimating (a), 0.) using standard sub-Gauses inequalities. Then, through mathematical induction, we extend this bound to the error of the action mean estimates (a, 8m.) Intuitively, if we believe that (a, 6m) is good estimate of (a, 0.) for all
concentration

---

actions, which implies (m is a good estimate of A. at batch m, then even though the scale in mm+1 by (m)a), this property will continue to hold batch m + 1. The constants multiplying Am (a) in @m are carefully designed to enable this. Finally, we show that the inverse squared gap weighting of the distribution enables to tightly upper bound the regret.
Algorithm for Contextual Linear Bandits
Our algorithm for contextual linear bandits is based on technique proposed in [8 which reduces the contextual linear to a linear bandit setting. However, we cannot directly apply the reduction from [ in Algorithm 1 as the reduction is not necessarily computationally efficient. Instead, we build a new algorithm (see Algorithm 4 in App. G that incorporates reduction steps from [18] within One challenge we encounter is the introduction of large, non-convex action set through
Algorithm|] | the reduction process. To address this, we construct a linear optimization oracle over the new action set in order to ensure the efficiency of Algorithm El Additionally, the reduction requires estimating the expected value of a function (explained next and in App. G). and we carefully design the batch lengths to perform this estimation effectively. The following theorem describes our main result.
Theorem 3. Consider contexiual linear bandit instance with A, generated from an unknown distribution D. There exists universal constant C and choice for batch lengths such that Algorithm finishes in (log log T) batches with regret upper bounded
Ry S CyVTToo log log
with probability at least 1 -8, 8, where y= 10 CLd(1og(16M//) + 57dlog (6T)). Moreover, the running time and space complexity are Ō(d + T)) O + Map) respectively.
We next briefly review the reduction and refer the reader to 18 for a detailed description. The basic idea in [88 is to establish a linear bandit action for each possible parameter vector @ of the contextual bandit instance. This is achieved through the use of the function g : Rdd + RR which computes the expected best action under the context distribution D with respect to the parameter 0: g() = (O O)) where O is an optimization oracle (see Definition D A key insight, as stated in Theorem of [ that if a, ( 6,) for some 0₂ E 12 then the reward generated by the contextual bandit instance can be expressed as r, = (g)). 0_) + 7/6- where of is noise with zero mean conditioned on the history. Consequently, the reward can be viewed as generated by pulling action g(f,) in a linear bandit instance with an action set X' = {0)()) θ). Moreover, the same theorem demonstrates that if a linear bandit algorithm employed to choose g(o,) E X' round R/1 = Ö(VT) with high probability, where R7. = Eim supaee (g(0) g(O,), 0.) is the regret of the algorithm on the linear bandit instance.
t and thus play action a, = O 02), then [
To estimate g. which depends on the unknown context distribution D, [8]] proposes using con- texts observed in previous batches. Specifically, the function g is replaced by g ()m)) TH... Eiehm O(A,;)) 8) for all 0 e O', where Hn, is the set of indices for rounds in batch m and
e' = 10],10 e is a discretization of o, [0], = glovd d/l////////// /////////dd and 9 is the discretization parameter. The action set at batch m is correspondingly modified as Xm = (0)()) E O'). It is also shown in [88 that ((m) is a good estimate of for all 0 E O' with high probability.
To leverage this reduction, we modify Algorithm by adapting the action set in each batch based on the estimate of g. i.c., the set Xm (note that we do not need to explicitly calculate the sets issue arises where the estimate of 0, at batch depends the approximate
Xm).. However, optimal design from batch m - 1, which employs the action set Xm estimated from the contexts of batch 2. In the proof of Theorem 3 we demonstrate that this leads regret proportional to Tm/ /Tm- If the batch lengths grow rapidly, significant regret may occur. To mitigate this, reduce the growth rate of batch lengths by allowing them to increase only when m is odd (a similar technique was employed in (8).. The pseudo-code is in Algorithm !
To implement Algorithm f fefficiently we need: (i) an approximate linear optimization oracle for
the set X,m with additive error at most c = (1 - (1)) (1277 Ty: we show in Lemma
in App. that g ((()) (101,) can be used as our approximate oracle for S c/2; and (ii) an inverse of the function (m) to find 0, associated with (( ((,) to play the action ar = ( 0z): we observe

---

that all actions played by our algorithms (Algorithm and are the output of the approximate optimization oracle for some 0; namely, for Algorithm any pulled action is of the form g g(m) (10),) for some input to the approximate oracle 6. Hence, the inversion of g(m) for the actions pulled by Algorithm 4 can be performed by storing (0), whenever the action g (r ((0),) is stored. This increases both the space and time complexity only by constant factor.
Gap-dependent regret bounds for contextual linear bandits. The main difficulty in extending the gap-dependent regret bounds in Theorem to the contextual case is that a large minimum action gap in the original action sets Ar does not imply large gap in the reduced action set X. As a simple example consider d 1, 0- 1, and two action sets A1 {-1. 1.. and A2 {-1}. At each iteration the learner receives the action set A1 with probability p and A2 with probability 1 independently from other iterations. Recall that the action set in the reduced instance X' {g(()] E 1]}, where g(0) EA aarg m (a, 0)}. For 0 2 0 we have that g(0) = p(1 + p) (-1) 2p 1, Therefore, the 2p which can be arbitrarily small depending on p. Note that in the original contextual bandit instance, the minimum gap is at least 2 for both
while for 0 < 0 we have ( p0-ppp1)))))) -1) suboptimality gap is min = (2p - 1) action sets.
-1 Then X' =
While it may be possible to provide gap dependent regret bounds for our algorithm in the contextual case, this will require more sophisticated regret analysis that does not only rely on the reduced linear bandit instance.
Numerical results. In App. D we provide a numerical example to compare the computational complexity of computing the exploration policy of our algorithm versus the complexity of computing the policy in 40
Conclusion
In this paper, we proposed the first efficient batched algorithm for contextual linear bandits with large action spaces. Our algorithm achieves high-probabille regret upper bound of Ö(VT), uses Ollo log T) batches, and has computational complexity that is linear in T and polynomial in d.
Acknowledgments
This work was partially supported by the NSF grants #2007714 and #2221871, the DARPA grant #HR00112190130 and by the Army Research Laboratory under the Cooperative Agreement W911NF-I1-2-0196.
References
[1] Y. Abbasi-Yaduas Yadkori, D. Pál, and Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] N. Abe and P. M. Long. Associative reinforcement learning using linear probabilistic concepts.
In ICML, pages 3-11. Citeseer, 1999.
[3] A. Agarwal, S. Agarwal, S. Assadi, and S. Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. Conference on Learning Theory, pages 39-75. PMLR, 2017.
[4] A. Agarwal, S. Bird, M. Cozowicz, L. Hoang, J. Langford, S. Lee, J. Li, D. Melamed, G. Oshri, O. Ribas, et al. Making contextual decisions with low technical debt. arXiv preprint 2016.
[5] D. Agarwal, B.-C. Chen, P. Elango, N. Motgi, S.-T. Park, R. Ramakrishnan, S. Roy, and J. Zachariah. Online models for content optimization. Advances in Neural Information Process- ing Systems, 21, 2008
[6] Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference machine learning, pages 127-135. PMLR, 2013.
10

---

[7] B. Awerbuch and R. Kleinberg. Online linear optimization and adaptive routing, Journal of Computer and System Sciences, 74(1):97-114, 2008.
[8] D. Bouneffouf, A. Bouzeghoub, and A. L. Gançarski. A contextull-bandit algorithm for mobile context-aware recommender system. In Neural Information Processing: 19th International Conference, ICONIP 2012. Doha, Qatar, November 12-15, 2012, Proceedings, Part III 19, pages 324-331. Springer, 2012.
[9] S. Bubeck, N. Cesa-Bianchi, and S. M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference Learning Theory, pages 41-1. JMLR Workshop and Conference Proceedings, 2012.
[10] W. Cai, J. Grossman, Z. J. Lin, H. Sheng. J. T.-Z. Wei, J. Williams, and S. Goel. Bandit algorithms to personalize educational chatbots. Machine Learning, 110(9))2389-244 2418, 2021.
[1] V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. 2008.
[12] H. Esfandiari, A. Karbasi, A. Mehrabian, and V. Mirrokni. Regret bounds for batched bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7340-7348, 2021.
[13] Z. Gao, Y. Han, Z. Ren, and Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
[14] M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimiza- fion, volume 2. Springer Science & Business Media, 2012.
[15] I. S. T. C. Group al. The international stroke trial (ist): randomised trial of aspirin, subcutaneous heparin, both, or neither among 19 435 patients with acute ischaemic stroke. The Lancer, 15699 1581, 1997.
[16] Y. Han, Zhou, Z. Zhou, J. Blanchet, W. Glynn, and Y. Ye. Sequential batch learning in finite-action linear contextual bandits. arXiv preprint 20Xiv:2004.06321, 2020.
[17] O. Hanna, L. Yang, and C. Fragouli. Learning from distributed users in contextual linear bandits without sharing the context. Advances in Neural Information Processing Systems, 35:1 1049-110060 2022.
[18] O. A. Hanna, L. F. Yang. and C. Fragouli. Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. arXiv preprint arXiv:2211.00 1.05622, 2022.
[19] E. Hazan and Z. Karnin. Volumetric spanners: an efficient exploration basis for learning. Journal of Machine Learning Research, 2016.
[20] Ito, D. Hatano, H. Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K.-L. Kawarabayashi. Oracle-efficient algorithms for online linear optimization with bandit feedback. Advances in Neural Information Processing Systems, 32, 2019.
[21] T. Jin, P. Xu, X. Xiao, and Q Gu. Double explore-then-commi Asymptotic optimality and beyond. In Conference on Learning Theory, pages 2584-2633. PMLR, 2021.
[22] K.-S. Jun, A. Bhargava, R. Nowak, and R. Willett, Scalable generalized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems, 30, 2017.
[23] J. Kiefer and J. Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
[24] Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[25] T. Lattimore, C. Szepesvari, and G. Weisz. Learning with good feature representations in bandits and with generative model. In International Conference on Machine Learning, pages 5662-5670. PMLR, 2020.

---

[26] Li, W. Chu, J. Langford. and R. E. Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[27] Y. Li, Y. Wang, X. Chen, and Y. Zhou. Tight regret bounds for infinite-armed linear contextual bandits. In International Conference on Artificial Intelligence and Statistics, pages 370-378. PMLR, 2021.
[28] Y. Li, Y. Wang, and Y. Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pages 2173-2174. PMLR, 2019.
[29] C. D. Meyer. Matrix analysis and applied linear algebra, volume 71. Siam, 2000.
[30] V. Perchet, P. Rigollet, S. Chassang, and E. Snowberg. Batched bandit problems. The Annals of Statistics, pages 660-681, 2016.
[31] C. Pike-Burke, S. Agrawal, C. Szepesvari, and S. Grunewalder. Bandits with delayed, aggregated anonymous feedback. In International Conference Machine Learning, pages 4105-4113 PMLR, 2018
[32] Y. Ruan, J. Yang, and Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 74-87, 2021.
[33] S. Sahni. Computationally related problems. SIAM Journal on computing, 3(4):262-279, 1974.
[34] J. Sherman and W. J. Morrison. Adjustment of an inverse matrix corresponding to change in one element of given matrix. The Annals of Mathematical Statistics, 21(1):124-127, 1950.
[35] M. D. Summa, F. Eisenbrand, Y. Faenza, and C. Moldenhauer. On largest volume simplices and uub-determinants. In Proceedings of the twenty-sixth annual ACM-SIAM symposium Discrete algorithums, pages 315-323. SIAM, 2014.
[36] K. T. Talluri, G. Van Ryzin, and G. Van Ryzin. The theory and practice of revenue management, volume 1. Springer, 2004.
[37] A. Tewari and S. Murphy. From ads interventions: Contextual bandits in mobile health. Mobile Health: Sensors, Analytic Methods, and Applications, pages 495-517 2017.
[38] M. J. Todd. Minimum-volume ellipsoids: Theory and algorithms. SIAM, 2016.
[39] S. Yang, T. Ren, S. Shakkottai, E. Price, I. S. Dhillon, and S. Sanghavi. Linear bandit algorithms with sublinear time complexity. In International Conference on Machine Learning, pages 25241-25260 PMLR. 2022.
[40] Z. Zhang, X. Ji, and Y. Zhou, Almost optimal batch-regret tradeoff for batch linear contextual bandits. arXiv preprini arXiv:21
2021.
[41] Y. Zhu, D. Foster, J. Langford, and P. Mineiro. Contextual bandits with large action spaces: Made practical. In International Conference on Machine Learning, pages 17448-27453. PMLR, 2022.
12


Reviews:
[{"review_id": "ace8f0004u", "reviewer": "Reviewer_vkke", "summary": "This paper studies batched online learning for linear bandits and linear contextual bandits in large action space. It shows that the learner can use $O(\\log \\log T)$ batches (in each of which the sampling distribution over actions remain the same) to achieve near-optimal regret. Compared to previous work, the main contribution is to introduce an oracle efficient algorithm which only requires linear optimization over the action set, and thus can handle large action space. The regret bound is a $d$ factor worse than the tight bound. ", "questions": "See the weakness section. ", "limitations": "There is no societal impact. ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper studies an important question for linear (contextual) bandits where the action space is large and the number of policy switch is limited. The proposed algorithm is natural and easy to understand. The regret bound (just a $d$ factor sub-optimal) is the best we can hope for under the computational constraint. \n- There are some other algorithmic ideas developed, which could be of independent interest. For example, adding a little ball around the origin to make the action space full rank, and the \"action set shaping\" technique that balance exploitation and exploration when finding the solution of the approximate G-optimal design. ", "weaknesses": "- Though I'm not entirely familiar with the literature, I feel that the contribution might be a bit incremental. The reason is that in batched online learning, ways to achieve optimal performance using $O(\\log \\log T)$ batches has already been established. The main contribution of this work is about using barycentric spanner to efficiently explore. The related technique has been extensively studied in [Zhu et al.], though not for the batched setting. I can see a lot of similarity between the LW-ArgMax in this paper and the IGW-ArgMax in [Zhu et al.], but no technical comparison is provided. The LWS procedure is also closely related to the ReweightedSpanner procedure in [Zhu et al.]. To be fair, the two are still slightly different because this paper uses inverse square gap weighting while theirs is inverse gap weighting, but I think there still needs to be some comparison. \n\n- The proposed algorithm operate on the extended action set $\\mathcal{A}'$, which seems to require a linear optimization oracle over $\\mathcal{A}'$. I don't think it is explained what if the learner only has an oracle for the original action set $\\mathcal{A}$. It is unclear whether an oracle for $\\mathcal{A}'$ can be straightforwardly constructed from that for $\\mathcal{A}$. \n\n- Similarly, in the contextual setting, the algorithm operates over a very artificial action set $g^{(m)}([\\theta]_q)$. It is totally unclear how to leverage the linear optimization oracle for the original action set $\\mathcal{A}_t$ to implement the algorithm. \n\n- Since a inverse square gap weighting is used, maybe it's possible to show an refined bound like in [Lattimore and Szepesvari, 2016]. Now only a $\\Delta_{\\min}$ dependent instance-dependent bound is shown, which can be highly sub-optimal. \n\n\n[Zhu et al., 2022] Zhu, Foster, Langford, Mineiro. Contextual bandits with large action spaces: made practical.  \n\n[Lattimore and Szepesvari, 2016] The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and valuable comments.\n\n* **[Distinction from existing algorithms]** We respectfully disagree that the contributions in our work are incremental with respect to previous work. Our work provides the first efficient batched algorithms, both for linear and contextual bandits, that we believe can be of significant practical interest, and that required the development of new algorithms and proof techniques for their analysis.\\\n\\\nWhile batched algorithms for contextual linear bandits that use $O(\\log \\log T)$ batches indeed exist [Ruan et al., 2021], these algorithms are not computationally-efficient, and it is not a direct extension making them so. These algorithms use a G-optimal design, as we also do. However, while using a Barycentric spanner to get the G-optimal design is already used in the literature [Awerbuch et al., 2004], this cannot make existing algorithms computationally efficient. The reason is that, these algorithms require a G-optimal design over a good set of actions (since they use action elimination) that is represented by non-convex constraints. Hence, finding a Barycentric spanner requires solving a non-convex (non-trivial) optimization problem. To deal with this, our paper proposes a novel algorithm that does not use \"hard arm elimination\" (Algorithm 1); instead, we use a form of \"soft arm elimination\" through inverse squared gap weighting. Due to the less frequent updates of the estimated gaps (only $O(\\log \\log T)$ times), analyzing the effect of the inverse squared gap weighting on the concentration of estimated action means becomes challenging. Due to space limitations, we are happy to provide more details about this in the comments if the reviewer is interested. We next provide more details in distinction from specific works.\n* **[Distinction from [Zhu et al., 2022]]** While constructing a linear optimization oracle with inverse gap weighting is a related problem, as we also mention in footnote 7 of our submission, the resulting strategy (Algorithm IGW-ArgMax in [Zhu et al., 2022]) is not applicable when inverse squared gap weighting is used. Our technique and the scheme of [Zhu et al., 2022] both use the standard idea of line search; the technical challenge is how to construct the function and step of the line search. In particular, for inverse gap weighting calling the optimization oracle by doing a line search with $N=O(\\log T)$ steps for the function $z \\theta + z^2.C. \\Delta(a)$ provides an output with sufficiently small approximation error. However, for inverse squared gap weighting we do a line search with $N=O(\\log^2 T)$ steps for the function $z (1+1/W)\\theta + z^{1+1/W}.C. \\Delta(a)$ with $W=3\\log T$. The proof that this line search provides an approximate optimization oracle is much more involved than the inverse gap weighting case (please see App. B for details of the proof). We are happy to add a detailed technical comparison in our appendices.\n* **[LWS vs ReweightedSpanner of [Zhu et al., 2022]]** Indeed, the LWS algorithm and ReweightedSpanner in [Zhu et al., 2022] are similar since this is a standard method, proposed in [Awerbuch et al., 2004], to construct a Barycentric spanner using a linear optimzation oracle. The main challenges are: (i) in designing an algorithm that requires Barycentric spanners over sets that admit an efficient optimization oracle, and (ii) constructing a linear optimization oracle to use in the LWS algorithm.\\\n\\\nIn addition to the distinctions above, the work in [Zhu et al., 2022] does not face the challenge of less frequent updates of the estimated gaps due to the batch constraints. As a result, the regret analysis of our algorithms and [Zhu et al., 2022] use very different techniques. The less frequent updates of the estimated gaps also pose a difficulty in directly analyzing the regret for contextual bandits. This is the main reason that, unlike [Zhu et al., 2022], our analysis is done for linear bandits and carried out to the contextual bandit case using the reduction in [Hanna et al., 2022].\\\n\\\nIn summary, our proposed algorithm, method of constructing a linear optimization oracle over the weighted action set, and regret analysis cannot be easily obtained from existing work in the literature.\n\n* **[Optimization oracle over $A'$]** Since $A'=A\\cup B_{1/T}$, the linear optimization problem $\\max_{a\\in A'}\\langle a, \\theta \\rangle $ can be solved by comparing $\\max_{a\\in A}\\langle a, \\theta \\rangle $ and $\\max_{a\\in B_{1/T}}\\langle a, \\theta \\rangle = 1/T$ (note that $\\arg\\max_{a\\in B_{1/T}}\\langle a, \\theta \\rangle = (1/T) \\theta /{\\|\\theta\\|_2}$). Indeed, in our paper we only assume an optimization oracle over the original action set $A$. We are happy to clarify this in the next version.\n\n* **[Optimization oracle over the reduced set $X_m$]** We do provide an efficient optimization oracle over the artificial action set $X_m$. As mentioned in page 9 (line 343), the function $g^{(m)}([\\theta]_q)$ for $q\\leq \\epsilon/2$ serves as our (approximate) linear optimization oracle. This function can be computed by calling the linear optimization oracle for the original action set $A_t$ at most $T$ times. The formal proof is provided in App. F.\n\n* **[Tighter instance dependent regret bounds]** We would like to highlight that ours is the first result to achieve nearly optimal gap dependent regret of $\\tilde{O}(1/\\Delta_{\\min})$ using an efficient batched algorithm. General instance-dependent bounds can be a future direction of our work. [Lattimore and Szepesvari, 2016] considers the asymptotic regret analysis, while in our submission we focus on the finite time regret analysis. It might be possible for us to get similar bounds as in [Lattimore and Szepesvari, 2016], but we leave it as a future work as well."}, {"review_id": "AuKQrVClyX", "reviewer": "Reviewer_azE5", "summary": "This paper proposes a new batched contextual linear bandits algorithm that achieves $\\widehat{O}(\\sqrt{T})$ regret while using $O(\\log\\log T)$ batches. The algorithm combines various techniques from previous work including approximate barycentric spanner computation and reduction from contextual linear bandits to linear bandits. Meanwhile, the algorithm is also computationally efficiently.", "questions": "- Why the regret bound based on the minimum gap is not applicable for contextual linear bandits?\n- A better G-optimal design approximation can be obtained when $\\mathcal{A}_t$ is discrete and finite. Will this give better theoretical guarantee?", "limitations": "The theoretical limitations are well-addressed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The algorithm intuition and application of prior techniques of approximate barycentric spanner computation and reduction from contextual linear bandits to linear bandits are considered to be novel.\n- The algorithm is shown to be computationally efficient while maintaining moderately good regret and low number of batches.", "weaknesses": "Although it is proven that the proposed algorithm has good computational complexity, it will be better if we can empirically see its computational efficiency is superior over other algorithms listed in Table 1. In particular, it seems that implementing the contextual version of the algorithm (Algorithm 3) is not very trivial. Can we see some empirical comparisons of regret and computational efficiency among Algorithm 3 and some other algorithms listed in Table 1?\n\n### Suggestions on Writing\n- It can be better if specific lemmas are referred when the arguments in main context use any results from the appendix. For example, the arguments in line 248 and 277.\n- It may be better to define $\\Delta(a)$ clearly after defining $L_z(a)$ in line 273.\n- For self-containedness, it will be better to have a brief explanation of how Algorithm 2 works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their input and for appreciating our contribution.\n\n* **[Empirical results]** Indeed, as the reviewer notes, in this work we focused on the theoretical understanding of efficient batch learning in contextual bandits, where we show a batched bandit algorithm that provably achieves computational efficiency while maintaining near-optimal regret bound. \nTo illustrate this, let us consider a $d$-dimensional linear bandit problem with $T^d$ actions. \nOur algorithm takes only $\\mathrm{poly}(dT)$ time per batch whereas previous batched algorithms can take $\\Omega(T^d)$ time, exponential in $d$.\\\n\\\nHaving said that, following the reviewer's suggestion, we have done a small experiment to compare the computational complexity of computing the exploration policy of our algorithm versus the complexity of computing the policy in [Zhang et al., 2021] (complexity of one batch). We do not consider other batched algorithms such as [Ruan et al., 2021] since they are not feasible to implement even for a small number of arms. We used $d=5$ dimensions and a batch of size $100$ iterations. For simplicity we use a fixed action set (unit sphere), however, this knowledge is not revealed to the algorithms, i.e., the algorithms assume that the action set may change over time. \nAs the policy of [Zhang et al., 2021] requires to solve a non-convex optimization problem, it is not feasible to implement it for infinite number of arms. Instead, we solve the optimization problem over a finite subset of $k$ arms sampled uniformly at random from the action set. In contrast, our algorithm can be directly applied for the infinite action set, hence, the computational complexity will not depend on $k$. In the figure attached to the common rebuttal, we plot the time complexity versus the sampled number of arms (on Intel(R) Xeon(R) CPU @ 2.20GHz, 56MB cache). We observe that for moderately large number of arms, our algorithm achieves significant savings in computational complexity as compared to the scheme of [Zhang et al., 2021].\\\n\\\nWe note again that theoretically we have proved the same order regret bounds; but we will be happy to add numerical evaluation in the next version.\n* **[Writing]** Thank you. We will incorporate the suggested changes above, as well as the response to the questions of the reviewer in the next version.\n* **[Gap-dependent regret bounds for contextual linear bandits]** Thank you for this very good question. The main reason is that a large minimum action gap in the original action sets $A_t$ does not imply a large gap in the reduced action set $X$. As a simple example consider $d=1$, $\\theta_\\star = 1$, and two action sets $A_1=\\\\{-1,1\\\\}$, and $A_2=\\\\{-1\\\\}$. At each iteration the learner receives the action set $A_1$ with probability $p$ and $A_2$ with probability $1-p$ independently from other iterations. Recall that the action set in the reduced instance $X=\\\\{g(\\theta)|\\theta \\in [-1,1]\\\\}$, where $g(\\theta)= E_{A\\sim D}[\\arg\\max_{a\\in A} a^\\top \\theta]$. For $\\theta \\geq 0$ we have that $g(\\theta)=p(1)+(1-p)(-1)=2p-1$, while for $\\theta < 0$ we have $g(\\theta)=p(-1)+(1-p)(-1)=-1$. Then $X=\\\\{-1,2p-1\\\\}$. Therefore, the suboptimality gap is $\\Delta_{\\min}=(2p-1)(1)-(-1)(1)=2p$ which can be arbitrarily small depending on $p$. Note that in the original contextual bandit instance, the minimum gap is at least $2$ for both action sets.\\\n\\\nWhile it may be possible to provide gap dependent regret bounds for our algorithm in the contextual case, this will require more sophisticated regret analysis that does not solely rely on the reduced linear bandit instance.\nWe are happy to include this discussion in the next version of our paper.\n* **[Discrete and finite sets of actions]** Indeed, a better G-optimal design will directly translate to better regret bounds for our algorithms. However, the analysis may become  more involved in the contextual case. Moreover, to the best of our knowledge, these results are obtained for small action sets while we focus in this work on large action spaces."}, {"review_id": "R4bQltVQhe", "reviewer": "Reviewer_DZuy", "summary": "This paper proposes an algorithm for the batched (contextual) linear bandit problem with a large action space. The proposed algorithm has low time and space complexity. The proposed algorithm for the batched linear bandit problem selects arms in each batch according to a G-optimal design based on a modified action set and chooses them a number of times, dependent on the estimated sub-optimality gap. As a result, it achieves efficient time and computational complexity, even when the number of actions is large, unlike the existing elimination algorithms. The extension to contextual linear bandits is achieved by modifying part of the existing reduction for linear bandits. The proposed algorithm achieves a near-optimal regret with the optimal number of batches. Although there is a gap between the upper and lower regret bounds concerning the dimension $d$ of the feature vectors, it is due to the inheritance of the approximation ratio of the G-optimal design with a barycentric spanner from existing studies.", "questions": "#### Questions\n- No specific questions.\n\n#### Comments\n- Overall, I believe this is a high-quality paper.\n- In my opinion, this paper should include in the main body the choice of batch size and how it is derived (or citations) if space allows.\n\n#### Minor Comments\n- Line 201: an uniform -> a uniform\n- Line 287: $B_1$ -> $B_{1/T}$", "limitations": "- In this paper, limitations are well discussed (e.g., assumptions for the problem).\n- While societal impacts are not discussed in this paper, it could be considered a paper with little direct impact on society since it is a theoretical paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper proposes a novel and impactful algorithm.\n- The design and motivation of the proposed algorithm are clearly explained.\n- A well-summarized proof sketch is provided in the main body.", "weaknesses": "- The regret upper bound of the proposed algorithm is not optimal for the dimension $d$ of the feature vectors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their input and for appreciating our contribution.\n* **[Regret dependency on $d$]** We would like to highlight that our regret bounds match the best known regret bounds for state-of-the-art (unbatched) efficient contextual linear bandit algorithms [Agrawal et al., 2013; Zhu et al., 2022; Dani et al., 2008].\\\n\\\nOur worst-case regret bound loses a $\\sqrt{d}$ factor as compared to the $\\Omega(d\\sqrt{T})$ lower bound, however it is not clear that $\\tilde{O}(d\\sqrt{T})$ regret bound is achievable with an oracle-efficient algorithm.\\\n\\\nThe reason we lose this factor is as follows. \nIn our algorithm, a critical step is to find a small subset of actions (spanner actions) that form good bases of the entire action space.\nWe use linear optimization oracles to achieve this computationally efficiently. \nHowever, this method can only produce spanner actions with a $V^{-1}$-norm (defined in (5) of the paper) bounded by $O(\\sqrt{d})$, which gives the corresponding factor in the regret bound. Any future improvement that reduces the norm from $O(\\sqrt{d})$  to $O(1)$ will immediately result in nearly optimal regret bounds for our algorithms.\n* **[Writing]** Thank you for pointing out these typos. We have corrected these in our updated version. "}, {"review_id": "B4HjlGGwgs", "reviewer": "Reviewer_6gSX", "summary": "This paper proposes the first efficient batch algorithm for (contextual) linear bandits. Instead of relying on the classical elimination-based algorithmic design, this paper adopts a linear optimization oracle over the large action set. The proposed algorithm achieves $\\tilde{O}(\\sqrt{}T)$ regret with the number of batches matching the lower bound. The specific algorithm for contextual linear bandit is built upon a reduction technique which reduces contextual linear bandits to bandits. Directly applying this reduction incurs high computational cost. To circumvent this, an approximated linear optimization oracle is designed. ", "questions": "1. I am unclear about what are the major technical novelty/contributions in the reduction discussed in section 4. It seems to me that most ideas follow directly from [18], except for the tuning of the batch length. It would be great if the authors can further elaborate. \n\n2. It is mentioned in line 76 that novel approaches are proposed to bound the regret of the algorithm. Could the authors emphasize/summarize the approaches? The current section 3.2 is quite overwhelming to readers. \n", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Meaningful theoretical contribution: the first efficient batch algorithm for contextual linear bandits is proposed and analyzed. The number of batches matches the lower bound. \n\n2. Novel idea in algorithmic design: instead of classical design based on hard elimination, this paper uses an interesting ‘soft’ elimination which eliminates candidates for the unknown model parameters in each batch, incurring low regret. \n", "weaknesses": "I did not detect any major weakness in this paper. However, I do believe this paper would benefit from adding some simple numerical simulation. I understand this is a theoretical paper. But due to the complexity of the theoretical analysis and technical algorithmic design, it would be easier to evaluate the performance of the algorithm via numerical simulations on contextual linear bandits. Specifically, it would be better if it can be demonstrated that the number of batches is indeed of the order $\\log \\log (T)$. It would also be interesting to compare with some benchmark algorithms for contextual linear bandits not subject to the batch constraint, and see whether the proposed algorithm has inferior regret due to the batch constraint. Simple numerical simulations suffice. \nI also have some questions. Please see the Questions section.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their input and for appreciating our contribution.\n\n* **[Numerical simulations]** Indeed, as the reviewer notes, in this work we focused on the theoretical understanding of efficient batch learning in contextual bandits, where we show a batched bandit algorithm that provably achieves computational efficiency while maintaining near-optimal regret bound. \nTo illustrate this, let us consider a $d$-dimensional linear bandit problem with $T^d$ actions. \nOur algorithm takes only $\\mathrm{poly}(dT)$ time per batch whereas previous batched algorithms can take $\\Omega(T^d)$ time, exponential in $d$.\\\n\\\nHaving said that, following the reviewer's suggestion, we have done a small experiment to compare the computational complexity of computing the exploration policy of our algorithm versus the complexity of computing the policy in [Zhang et al., 2021] (complexity of one batch). We do not consider other batched algorithms such as [Ruan et al., 2021] since they are not feasible to implement even for a small number of arms. We used $d=5$ dimensions and a batch of size $100$ iterations. For simplicity we use a fixed action set (unit sphere), however, this knowledge is not revealed to the algorithms, i.e., the algorithms assume that the action set may change over time. \nAs the policy of [Zhang et al., 2021] requires to solve a non-convex optimization problem, it is not feasible to implement it for infinite number of arms. Instead, we solve the optimization problem over a finite subset of $k$ arms sampled uniformly at random from the action set. In contrast, our algorithm can be directly applied for the infinite action set, hence, the computational complexity will not depend on $k$. In the figure attached to the common rebuttal, we plot the time complexity versus the sampled number of arms (on Intel(R) Xeon(R) CPU @ 2.20GHz, 56MB cache). We observe that for moderately large number of arms, our algorithm achieves significant savings in computational complexity as compared to the scheme of [Zhang et al., 2021].\\\n\\\nWe note again that theoretically we have proved the same order regret bounds; but we will be happy to add numerical evaluation as well in the next version.\n\n* **[Number of batches]** Regarding simulations to calculate the number of batches, we note that by construction of our algorithm, and in particular the choice of batch lengths in equation (90) in Appendix D, the number of batches  our algorithms use is always bounded by $2\\log\\log T + 1$.\n* **[Novelty in the reduction]** Thank you for this question. Please refer to the paragraph with title ``Novelty in the reduction\" in the common rebuttal for the answer to this question.\n\n* **[Approach to bound the regret]** We provide a summary of the novelty of our algorithm and analysis in the common rebuttal. Please refer to the paragraph with title ``Novelty in bounding the regret\". If the reviewer are interested, we highly encourage you to dig more into the details of the algorithm, and we are happy to address any additional questions you may have."}]

Author rebuttal:
We thank all the reviewer for their input and for appreciating our contribution.  This common part is devoted to summarizing the novelty of our proposed schemes. Detailed responses on the reviewers questions  are provided as a response to each reviewer. We also attach a figure with preliminary simulation results to reference in our comments.
* **[Novelty in the reduction (Question from Reviewer 6gSX)]**  Section 4 of our submission is devoted to establishing an efficient batched algorithm for contextual bandits. The core idea is to leverage the oracle-efficient batched linear-bandit algorithm in Section 3 and the reduction ideas established in [18]. However, the reduction in [18] is not focusing on time efficiency and a straightforward application does not result in a desirable (in terms of efficiency) algorithm. Moreover, when the context distribution is unknown, the reduction in [18] uses different batch lengths to estimate the reduction function $g$ -- this makes it incompatible with our batched linear bandit algorithm. The core novelty in this section lies in the solution of the above two issues.\
\
Indeed, to resolve the incompatible batch length problem,  we tune the batch lengths to have sufficiently good estimates of $g$ while only increasing the number of batches by a factor of $2$ as compared to the linear bandit case.\
\
However, solving the efficiency issue requires much more effort. In particular, we establish an efficient approximate linear optimization oracle on the reduced action set with the optimization oracle over the original context.
This new optimization oracle can then be applied with Algorithm 1 to solve the reduced linear bandit instance. Note that this is highly non-trivial as the size of the reduced action set can grow as $T^{Cd}$ for some constant $C$. Additional computation issues arise from the computation of the inverse of the reduction function $g$ (defined in line 321) as required in the reduction in [18]. We provide an efficient solution to it with an approximate optimization oracle constructed by the original optimization oracle (see Assumption 2).



* **[Novelty in bounding the regret (Question from Reviewer 6gSX)]** We here provide a summary of the novelty in our approach  in Section 3.2. The core idea of the algorithms consists of two steps. For each batch, $m$, the first step is identify a small set of actions $C_m$ (a barycentric spanner) so that pulling these actions can give a better estimator of the parameter $\theta^*$ than the previous batch;
the second step is to ensure that for each arm $a\in C_m$, it is pulled for a number of times  $\propto 1/\Delta_a^2$, where  $\Delta_a=(a_\star-a)^\top \theta_\star$ is the gap for action $a$. 
As such, the overall regret for this batch is at most $\propto \sum_{a\in C_m} 1/\Delta_a$, a form close to the optimal regret formulation. Hence, if these two steps are possible, then the overall algorithm would have a small regret. However, the above steps appear to be conflicting to each other. For instance, if we use the existing approach to establish barycentric spanners on the action set, then pulling each $a$ a number of times $\propto 1/\Delta_a^2$ does not give a good estimator to $\theta^*$ (the existing barycentric spanner proof actually requires that each $a$ needs to be pulled a equal number of times, regardless of the gaps). We resolve this by performing a careful weighting on the actions and find a barycentric spanner on the weighted actions. Then we show that pulling $\propto 1/\Delta_a^2$ times on the barycentric spanner of the weighted actions can give a good estimator -- resolving the conflicts.\
\
We also would like to highlight that the weighting on the actions are also highly non-trivial as the weights depend on the gaps of the actions, which are unknown in the first place. Our approach cleverly avoids the estimation of the gaps for all actions but only these actions that are called by the optimization oracle.

Meta-review: This paper considers the linear contextual bandit setting. The main novelty of this paper is achieving a sqrt(d^3 T) regret bound using just loglog(T) rounds of adaptivity. This is an improvement of the log(T) rounds that exists in the literature. The regret bound does not match the minimax optimal rate of sqrt(d^2 T), but the authors point out that this may be the price of computational efficiency, as prior works also achieve this rate using the argmax oracle. In summary, achieving a regret bound that scales as sqrt(T) with just loglog(T) rounds of adaptivity and being computational efficient is a significant advance. As reviewers, we also thank the authors for the experimental evaluation given in the rebuttal phase, despite this being a theoretical paper.
Decision: Accept (poster)