Generalized Linear Bandits with Limited Adaptivity
Authors: Ayush Sawarni
Nirjhar Das
Siddharth Barman
Gaurav Sinha
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Contextual Bandits
Generalized Linear Contextual Bandits
Logistic Bandits
Optimal Design
Limited Adaptivity
Batched Bandits
Primary area: bandits

Abstract: We study the generalized linear contextual bandit problem within the constraints of limited adaptivity.  In this paper, we present two algorithms, B-GLinCB and RS-GLinCB, that address, respectively, two prevalent limited adaptivity settings. Given a budget $M$ on the number of policy updates, in the first setting, the algorithm needs to decide upfront $M$ rounds at which it will update its policy, while in the second setting it can adaptively perform $M$ policy updates during its course. For the first setting, we design an algorithm B-GLinCB, that incurs $\tilde{O}(\sqrt{T})$ regret when $M = \Omega( \log{\log T} )$ and the arm feature vectors are generated stochastically. For the second setting, we design an algorithm RS-GLinCB that updates its policy $\tilde{O}(\log^2 T)$ times and achieves a regret of $\tilde{O}(\sqrt{T})$ even when the arm feature vectors are adversarially generated. Notably, in these bounds, we manage to eliminate the dependence on a key instance dependent parameter $\kappa$, that captures non-linearity of the underlying reward model. Our novel approach for removing this dependence for generalized linear contextual bandits might be of independent interest.

Generalized Linear Bandits with Limited Adaptivity
Ayush Sawarni' Stanford University
Nirjhar Das
Indian Institute of Science Bangalore nir harjhadds@iiise wisddas@@iss..... ac in
ayushsaw@stanf edu
Siddharth Barman
Gaurav Sinha
Indian Institute of Science Bangalore barman@iisc. ic
Microsoft Research India gauravsinha@mi wrosoft.. com
Abstract
We study the generalized linear contextual bandit problem within the constraints of limited adaptivity. In this paper, we present two algorithms, B-GLinCB and RS-GLinCE that address, respectively, two prevalent limited adaptivity settings. Given a budget M on the number of policy updates, in the first setting, the algorithm needs to decide upfront M rounds at which it will update its policy, while in the second setting can adaptively perform M policy updates during course. For the first setting, we design an algorithm B-GLinCB, that incurs Ö(VT) regret when M = Ω (log log 7') and the arm feature vectors are generated stochastically. For the second setting, we design an algorithm RS RS-GLinCB that updates its policy Ólog" T) times and achieves a regret of ((VT) even when the arm feature vectors are adversarially generated. Notably, in these bounds, manage to eliminate the dependence on a key instance dependent parameter K, that captures non-linearity of the underlying reward model. Our novel approach for removing this dependence for generalized linear contextual bandits might be of independent interest.
Introduction
Contextual Bandits (CB) is archetypal framework that models sequential decision making in time-varying environments. this framework, the algorithm (decision maker) presented, each round, with set of arms (represented as d-dimensional feature vectors), and it needs to decide which arm to play. Once an arm is played, reward corresponding to the played arm is accrued. The regret of the round is defined as the difference between the maximum reward possible in that round and the reward of the played arm. The goal is to design policy for selecting arms that minimizes cumulative a specified number of rounds, T. In the last few
regret (referred as the regret of the algorithm) decades, much progress has been made designing algorithms for special classes of reward models, e.g. linear model [3, 1, 16], logistic model [6, 2, 28] and generalized linear models [8, 19].
However, despite this progress, there a key challenge that prevents deployment of CB algorithms in the real world. Practical situations often allow for very limited adaptivity, i.e., do not allow CB algorithms to update their policy involves administering medical treatments to cohort of patients, with medical outcomes observed and collected for the entire cohort at the conclusion of the trial. This data is then used to design the treatment for the next phase of the trial. Similarly, in online advertising [25] and recommendations [18), updating the policy after every iteration during deployment is often infeasible due to infras- tructural constraints. A recent line of work [23, 22, 11, 12, 21, 9, 26] tries to address this limitation
rounds. For example, in clinical trials [10], each trial
* Work done while author Microsoft Research India Work done while author was at Microsoft Research India
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

by developing algorithms that try to minimize cumulative regret while ensuring that only limited number of policy updates occur. Across these works, two settings (called Mi and M2 from here onwards) of limited adaptivity have been popular. Both M1, M2 provide a budget M to the algorithm, determining the number of times it can update its policy. M1 [23, 13], the algorithm is required to decide upfront a sub-sequence of M rounds where policy updates will occur. While in M2 [1, 23]), the algorithm is allowed to adaptively decide (during its course) when to update its policy.
Limited adaptivity algorithms were recently proposed for the CB problem with linear reward models under the M1 setting [23, 11], and optimal regret guarantees were obtained when the arm feature vectors were stochastically generated. Similarly, in their seminal work on linear bandits, [1] developed algorithms for the M2 setting and proved optimal regret guarantees with no restrictions on the arm vectors. While these results provide tight regret guarantees for linear reward models, extending them to generalized linear models is quite a challenge. Straightforward extensions lead to sub-optimal regret with significantly worse dependence on an instance dependent parameter x. (See Section 2 for definition) that captures non-linearity of the problem instance. In fact, to the best of our knowledge, developing optimal algorithms for the CB problem with generalized linear reward models under the limited adaptivity settings MI, M2, is an open research question. This is the main focus of our work. We make the following contributions.
1.1 Our Contributions
We propose B B-GLinCB, an algorithm that solves the CB problem for bounded (almost surely) generalized linear reward models (Definition 2.1) under the M1 setting of limited adaptivity. We prove that, when the arm feature vectors are generated stochastically, the regret of B-GLinCH at the end of T rounds is Ö(VT), when M = S2log log When M Olog T). we prove an O(T2MM1/((2))) -2) regret guarantee. While the algorithm bears slight resemblance to the one in [23], direct utilization of their key techniques (distributional optimal design) results in a regret guarantee that scales linearly with the instance dependent non-linearity k. On the other hand, the leading terms in our regret guarantee for B B-GLinCB have no dependence on K. To achieve this, we make novel modifications to the key technique of distributional optimal design in [23]. Along with this, the rounds for policy updates are also chosen more carefully (in a dependent fashion). leading to a stronger regret guarantee.
We propose RS-GLinCE, an algorithm that solves the CB problem for bounded (almost surely) gen- eralized linear reward models (Definition 2.1) under the M2 setting of limited adaptivity. RS-CLinCB builds similar algorithm in [1] by adding novel context-dependent criterion for determining if policy update is needed. This new criterion allows to prove optimal regret guarantee (Ö( (((T)) with only O (log² T) updates to the policy. It is quite crucial for the generalized linear reward settings since, without it, the resultant regret guarantees have a linear dependence on K.
Our work also resolves a conjecture in [17] by proving an optimal (Ö(VT)) regret guarantee (for the CB problem with logistic reward model) that does not depend polynomially on S (the known upper is, to our
bound on the size of the model parameters, i.e. |0' < S, See Section 2) 3. RS-GLiine knowledge, the first algorithm for generalized linear reward models that is both computationally efficient (amortized Ollog T') computation per round) and incurs optimal regret. We also perform experiments in Section 5 that validate its superiority both in terms of regret and computational efficiency in comparison to other baseline algorithms proposed in [14] and [6].
1.2 Important Remarks on Contributions and Comparison with Prior Work
Remark 1.1 (x-independence). For both B B-GLinCB and GLinC,nCB, our regret guarantees are free of x (in their leading term), an instance-dependent parameter that can be exponential in the size of the unknown parameter vector, i.c., ||0*]| (See Section 2 for definition). Our contribution in this regard two-fold. Not only do we prove k-independent regret guarantees under the limited adaptivity constraint, we also characterize a broad class of generalized linear reward models for which a k-independent regret guarantee can be achieved. Specifically, our results imply that the CB problem with generalized linear reward models originally proposed in [8] and subsequently studied in literature [19, 14, 24] admits a x-independent regret.
Thii requires non-convex projection. We discuss its convex relaxation in Appendix E.

---

Remark 1.2 (Computational efficiency). Efforts to reduce the total time complexity to be linear in T have been active in the CB literature with generealized linear rewards models. For e.g.. [14] recently devised computationally efficient algorithms but they suffer from regret dependence on Optimal (s-independent) guarantees were recently achieved for logistic reward models [6, 2], and the algorithms were subsequently made computationally efficient in [7, 28]. However, the techniques involved rely heavily on the structure of the logistic model and do not easily extend to more general models. To the best of our knowledge, ours is the first work that achieves optimal k-independent regret guarantees for bounded generalized linear reward models while remaining computationally efficient*.
Remark 1.3 (Self Concordance of bounded GLMs). In order to prove x-independent regret guar- antees, we prove key result about self concordance of bounded (almost surely) generalized linear models (Definition 2.1) in Lemma 2.2. This result was postulated in [8] for GLMs (with the same definition as ours), but no proof was provided. While [6, 7] partially tackled this issue for logistic reward models", in our work, we prove self concordance for much more general generalized linear models.
2 Notations and Preliminaries
Notations: A policy ι is a function that maps any given arm set X' to a probability distribution over the same set, i.e., (Xx) E A(X), where ( is the probability simplex supported on X. We will denote matrices in bold upper case (e.g. M). ||x]|| denotes the la norm of vector x. We write || to denote Vz Ma for positive semi-definite matrix M and vector æ. For any two real numbers and b, we denote by b the minimum of and b. Throughout, O(-) denotes big-O notation but suppresses log factors in all relevant parameters. For m, n E with m < n, we denote the set {I...., n by [ni] and (m,...,7) n by [m, n].
Definition 2.1 (GLM). A Generalized Linear Model or GLM with parameter vector E TRdd is real valued random variable r that belongs to the exponential family with density function
Prr w) exp (r (ar, 0*) - b ((r,, 0*)) + c(r)
Function (called the log-partition function) is assumed to twice differentiable and i is assumed to be monotone. Further, we assume that E [0, Rt almost surely for some known R E R.
Important properties of GLMs such as E/r detailed in Appendix C. We define the link function μs as (fr, 0*)) == E[r z]. Thus, μ is also monotone. We now present key Lemma on GLMs (see Appendix C for details) that enables to achieve optimal regret guarantees for our algorithms designed in Sections 3 and 4.
b((,,, (*)) and variance V[r x] = (((z, 0*)) are
Lemma 2.2 (Self- Concodacce of GLMs). For any GLM supported on [0, Rj almost surely, the link function p(-) satisfies [ix))) < Rj((2), for all 2 R.
Next we describe the two CB problems with GLM rewards that we address in this paper. Let T E N be the total number of rounds. At round & [T). we receive arms K |x and must select an arm 24 E Xz. Following this, we receive a reward r2 sampled from the GLM distribution PP zx) with unknown 0".
set X₁ C Rd with number of
Problem 1: In this problem we assume that at each round f, the set of arms X₁ C IR is drawn from an unknown distribution D. Further, we assume the constraints of limited adaptivity setting M1, i.e. the algorithm is given budget M E N and needs to decide upfront the M rounds at which it will update its policy. Let supp (D) denote the support distribution D. We want to design an algorithm that minimizes the expected cumulative regret given
T
RT E
I
max / (fx, (-), En((o, ZEN
'While RS-GLinCB and B- B-GLinCB have total running time of Ö(1), their per-round complexity can reach (I'). This stands in contrast to [7], which maintains efficiency both total and por-round time complexity. "In [5]. claim about independent regret for all generalized linear models with bounded 0* was made; however, construct counterexamples to this claim (see Appendix C. Remark C.5).
3

---

Here, the expectation is taken over the randomness of the algorithm, the distribution of rewards re+ and the distribution of the arm set D.
this problem we do not make any assumptions on the arm feature vectors, i.e., the arm vectors can be adversarially chosen. However, setting M2, i.e., the algorithm is given a budget M E N and needs to adaptively decide the M rounds which it will update its policy (during its course). We want to design an algorithm that minimizes the cumulative regret given as
Problem 2:
assume the constraints of limited adaptivity
Ry Σ max p ((x,0)) EEA
Σ (((,,
Finally, for both the problems, the Maximum Likelihood Estimator (MLE) of 0* can be calculated by minimizing the sum of the log-losses. The log-loss is defined for any given arm I, its (stochastic)
reward and vector 0 Rd (as the estimator of the true unknown (*) follows: E(O, 2, r) = -r
+o ((a.0) u(z)dz, After rounds, the MLE is computed as 0 = arg ming Σ E(0, I,, To).
(ar 0)
2.1 Instance Dependent Non-Linearity Parameters
As in prior works [6, 7], we define instance dependent parameters that capture non-linearity of the underlying instance and critically impact our algorithm design. The performance of Algorithm (B-GLinCE) that solves Problem 1, can be quantified using three such parameters that are defined using the derivative of the link function ji(-). Specifically, for any arm set X, write optimal arm xx arg xXx /4 ((z, 0*)) and define,
1 = [/ [ (())))))) (1)
K (E)) EE\ i ((2,6))
max X(Suup((D)
i ((x", (()),0)))
R X-D
Remark 2.3. These quantities feature prominently in our regret analysis of Algorithm In partieular, the dominant term in our regret bound scales as O ((TT/k)), We also note that k²; in fact, for specific distributions D. the gap between them can be significant. Hence, we also provide a regret upper bound of O (T)R). In this latter case, however, we incur worse dependence on d. Section 3 provides a quantified form of this trade-off.
Algorithm 2 (RS-GLinCB) that solves Problem 2, requires another such non-linearity parameter RO defined as,
1
== max
rEU je (z)
We note that, here, x defined considering the parameter vector 0* in contrast to prior work on logistic bandits [7], where its definition involved a maximization over all vectors 0 with ||0|| < S (known upper bound of [|@*]). Hence, A as defined here is potentially much smaller and can lead to lower regret, compared to prior works. Standard to the CB literature with GLM rewards, will assume that tight upper bounds on these parameters is known to the algorithms.
Assumption 2.4. We make the following additional assumptions which are standard for the CB problem with linear or GLM reward models.
For every round I E (T), and each arm E Xr || < 1
Let 0" be the unknown parameter of the GLM reward, then ||0*|| S for known constant S.
2.2 Optimal Design Policies
G-optimal Design Given an arm set X, the G-OPTIMAL DESIGN policy मa the solution of the
| ( where U(A) = Ex [rz J. Now consider the following optimization problem, also known as the D-optimal design problem: max x log Det(U(A)). This is concave maximization problem as opposed to the G-optimal
following optimization problem: arg minxe max,ex
design which is non-convex. We have the following equivalence theorem due to Kiefer and Wol- fowitz [15]:
'We overload the notation to match that in the literature. & in the context of Problem is defined via (1).
while in the context of Problem 2 by (2).

---

Algorithm 1 B-GLinCB: Batched Generalized Linear Bandits Algorithm
Input: Number of batches M and horizon of play T.
1: Initialize batches Ti...., TM, defined in equation (3), and set À == 20Rd log T.
2: for rounds & T1 do
3: Observe arm set Kg sample arm 2t Te (At), and observe reward ri.
4: Compute a = arg ming Ever, ((0, Ts; r') and matrix V +I EiEn, T.r..
5: Initialize policy as G-OPTIMAL DESIGN.
6: for batches k = 2 to .M do
7: for each round E Ty: do
8: Observe arm set Xg
9: j 1 to k 1 do
10:
Update arm set X₂ 4 X. \ far E R. (x) < max LCB)
11:
Scale X, as in (4), to obtain X, then sample 2i ~ TT-1 X1)
12:
Equally divide Ty into two sets A and B.
Define H AI EiEd (((x,D=)) ((x,) 2, and 0g ming E
[(0, (g, Fgz 14: Compute DISTRIBUTIONAL OPTIMAL DESIGN policy using the arm sets (ee ReJIBB
rs).
Lemma 2.5 Secifer-Wolfowitze Let X' C Rdd be any set of arms and W G be the expected design matrix, defined WG (xx)T(()) |xx²) |, with (x) as the solution the D-optimal design problem. Then, To (2) also solves the G-optimal design problem, and for all æ E X, | S d.
Distributional optimal design Notably, the upper bound on |ællw=- specified in Lemma 2.5 holds only for the arms x in X. When the arm set Xg varies from round to round, securing a guarantee analogous to Lemma 2.5 is generally challenging. Nonetheless, when the arm sets X; are drawn from a distribution, it is possible to extend the guarantee, albeit with a worse dependence on d; see Section A.5 in Appendix A. Improving this dependence motivates the need of studying DISTRIBUTIONAL OPTIMAL DESIGN and towards this we utilize the results of [23].
The distributional optimal design policy is defined using collection of tuples M {(,,, P Pn 2 0 and Σ, P; = 1}. wherein each M, is a d x d positive semi-definite matrix and 4d log d. The collection MM is detailed next. Let softmax,, (fs1, 8k)) denote the probability For a specific M
distribution where the tth element is sampled with probability Σ $3
((rt, M,)M and each i [n] write TM, (X) softmax, ( (f[|=]) as the G-OPTIMAL DESIGN policy (Section 2.2), we define the DISTRIBUTIONAL OPTIMAL DESIGN policy π as
M. x X)). Finally, with Tद
{ Ta (X)
with probability 1/2
(X)
(M, (X))
with probability px/2
Given collection of arm sets {.i,,.., Xx) (called core set) sampled from the distribution D, we utilize Algorithm 2 of [23] to find the collection M; see Algorithm 4 of [23]. Overall, the computed M induces policy x that upholds the following guarantee.
Lemma 2.6 (Theorem 5, (23]). Let be the DISTRIBUTIONAL OPTIMAL DESIGN policy that has been learnt from 8 independent samples XI,...X, K ~ D. Also, let W denote the expected design
malrix, W Ex-D [Ex))(X) [x:x] |x]]. Then,
max |klll--1 < ( } 21 21 (0 (d' d) -dd 12-12.2-16
P
E XND
ZEX
3 B-GLinCB
In this section, we present B-GLinCB (Algorithm 1) that solves Problem 1 described in Section 2, which enforces constraints of limited adaptivity setting M1. Given limited adaptivity budget M N. our algorithm first computes the batch length for each of the A batches (i.c., determine rounds where
5

---

the policy remains constant). We build upon the batch length construction in [9]: however, the first batch is chosen to be x dependent which crucially helps in removing from the leading term in the regret."
Batch Lengths: For each batch & E [M], let Ts denote all the rounds within the k batch. We will refer to the first batch Ti as the warm-up batch. The batch lengths 7 = [Ta], k E [M] are calculated
as follows:
VK c 2S
d2na
2/3
a
72 == a, T= a==aVTT-11 for ls E [3
(3)
S
where 7 = 30RS 3ORSvTlog and a = 20-02 MTT if M S log log 7 and a = 2 otherwise.
During the warm-up batch (Lines 2, 3), the algorithm follows the G-OPTIMAL DESIGN policy, TG.
At the end of the warm-up batch (Line 4), the algorithm computes the Maximum Likelihood Estimate (MLE), 0w.. of 0*9, and design matrix V == -EET, T.S. + AI, with parameter
20 2og T.
Now, for each batch A > 2 and every round t Tk. the algorithm updates X₂ by eliminating arms from using the confidence bounds (see Equation (7)) computed in the previous batches (Line 10).
The algorithm next computes Xr a scaled version of X,, as follows, with B(x) define in equation (5),
G = ((l((,,0)))/BB I: E
(4)
Finally, we use the distributional optimal design policy Th. on the scaled arm set Me to sample the next arm (Line 11). At the end of every batch, we equally divide the batch To into two sets A and B. We use samples from A compute the estimator 0g and the scaled design matrix H3. The rounds in B are used to compute πK+1, the distributional optimal design policy for the next batch. It important note while the policy T& is utilized each round (Line 11) to draw arms, it updated (to - only at the end of the batch. Hence, conforming to setting M1, the algorithm updates the selection policy at M rounds that were decided upfront.
Confidence Bounds: The scaled design matrix HA, an estimator of the Hessian, is computed at the end of each batch &s 2..... M (Line 13):
Hg (i((ar, /9(x)))))) 2ı AI, where B(z) = exp (R {2S, TV |F=ly .))
(5)
where A is the first half of Th Using this, we define the upper and lower confidence bounds (UCB: Bk and ICBB)) computed at the end of batch Tx:
Qm)) + T |
k = k > 1
UCBx(z)=
(6)
(I, 0k) + + +|||=11
(x, Qw)) ~> k=
LCBx(x)
(x, (x, - ||
k> 1
Remark 3.1. The confidence bounds employed by the algorithm exhibit a significant distinction between the first batch and subsequent batches. While the first batch's bounds are influenced by the parameter subsequent batches utilize k-independent bounds. This difference arises from the use of the standard design matrix V in the first batch and a scaled design matrix H2 (cquation 5) in later batches, leveraging the self-concordance property of GLM rewards to achieve x-independence. Notably, the first batch's ' confidence bounds influence the scaling factor (xx) ) in later batches, creating a trade-off (addressed in the regret analysis in Appendix A) where an inaccurate estimate of Q.. can exponentially increase the scaling factor and confidence bounds.
In Theorem 3.2 and Corollary 3.3, present our regret guarantee for B-GLinCB. Detailed proofs for both are provided in Appendix A. The computational efficiency of B-GLinCB is discussed in Appendix D.
We note that in case is unknown, any known upper bound on x suffices for the algorithm. $ RRcaal that R provides an upper bound on the stochastic rewards and S is an upper bound on the norm of 8*. In case the MLE lies outside the set {0- ||0*1| < S). apply the projection step detailed in Appendix E.

---

Algorithm 2 RS-GLinCB: Rarely-Switching GLM Bandit Algorithm and == 25RS v dlog (7)
1: Initialize: V = H - XI, To 0. T == 1, x==
2: for rounds f ... do
3: Observe arm set A4
4: if maxxex, ||01||
1/(7 n/)) then // Switching Criterion 5: Select = arg maxxxaxx2 ZE | -i and observe reward rt.
6:
Update To + To (t). V t V V+r and H t H.
Compute 0. = arg min, E.ET. f(0, Fzz Ts) 11012.
7:
8:
else
9:
(ee(HH,)) (.)) > 2 (H,) then
// Switching Criterion Set 7 = t and 0 t arg ming E { 2, + |1012 and
10:
11:
0, - Project (0).
(U).((()) E Select 2, = arg max UCB x. H,, 0,) and observe reward rt.
Update X;
fo
max,ex, (zB.
13:
Update Hz+1 H, ((( Ieal
Theorem 3.2. Algorithm I (B- (B-GLinCB) incurs regret RT S (Ri + R2) log TogT 10, where
^ T (1 log and
R: = RSd
R₂ =
(RS (RS a1 ai
Corollary 3.3. When the number of batches M log log T, Algorithm achieves regret bound of
Rr S ((VE dRSVT (S (52
Remark 3.4. Scaling the arm set (as in (4)) for optimal design a crucial aspect of our algorithm, allowing obtain tight estimates of ju ((x, 8*)) (see Lemma A.10). This result relies multiple novel ideas and techniques, including seff-concordance for GLMs, matrix concentration, Bernstein- type concentration for the canonical exponential family (Lemma A. and application of distributional optimal design on scaled arm set.
Remark 3.5. The x-dependent batch construction is crucial feature of our algorithm, enabling effective estimation of (a( 0*)) at the end of the first batch. Since the first batch incurs regret linear in its length, achieving a s--nndependent guarantee requires the first batch to be o( o(VT). We demonstrate that choosing = ( ) is sufficient for this purpose (see Appendix A).
4 RS-GLinCB
In this section we present RS-GLinGK (Algorithm 2) that solves Problem described in Section 2, which enforces constraints of limited adaptivity setting M2. This algorithm incorporates novel switching criterion (Line 4), extending the deterninant-doubbing approach of [1]. Additionally, we introduce an arm-elimination step (Line 12) to obtain tighter regret guarantees. Throughout this section, we set À = d (lgg(T/)) R2 and 7 = 25RS log (T/5).
At round 6, on receiving an arm set X, RS-GLinCB first checks the Switching Criterion I (Line 4). This criterion checks whether for any arm X, the quantity || is greater than carefully chosen x-dependent threshold. Here V is the design matrix corresponding to all arms that have been played in the rounds To (= the of rounds preceding round where Switching Criterion I was triggered). Under this criterion the arm that maximizes ||ø]|y-1 is played (call this arm 2,) and the corresponding reward is obtained. Subsequently Line 6, the set To is updated include f; the
Note that Ry is expected regret. See the 2.

---

design matrix V is updated as V + V + 2y and the scaled design matrix H1+1 is set to Hç. The MLE is computed (Line 7) based the data in the rounds in To to obtain 0.-
When Switching Criterion is not triggered, the algorithm first checks (Line 9) the Switching Criterion II. that is whether the determinant of the scaled design matrix H. has become more than double of that of H, (where T is the last round before / when Switching Criterion II was triggered). Switching Criterion II is triggered at round I, then in Line 10, the algorithm sets + L and recomputes the MLE over all the past rounds except those in To to obtain O. Then 0 is projected into an ellipsoid around 0, to obtain the estimate 0, via the following optimization problem".
min 0
Σ TET
(a ((22, 0)) p((xre: 81))
s.t.
0 Bolly STV..
(8)
H(0)
Here H()) == ExET, i ((r,: 0)) x.a.. After checking Switching Criterion II, the algorithm
performs an arm elimination step (Line 12) based on the parameter estimate 6, as follows: for every arm x E Xg we compute (C).(x) = (1, + TVK || and (C (a, 0o, - -V |= Then, Xe is updated by climinating from it the arms with (CB.() less than the highest (CB,(-). (-). For arms in the reduced arm set X2 RS-GLinCB computes the index UCB(Z, 0.) = (x. 0.) + 150 | d (T/5), and plays the arm 24 with the highest index (Line 13). After observing the subsequent reward r.y the algorithm updates the scaled design matrix H. (Line 14) follows:
HA+1 H, (i((2re; 0.)),, /e)arar.. With this, the round I ends and the algorithm moves to the next round. Next, in Lemma 4. and Theorem 4.2 we present the guarantees number of policy updates and regret, respectively, for RS-GLinCB. Detailed proofs for both are provided in Appendix B.
Lemma 4.1. RS- GS-GLinCB (Algorithm 2), during its entire execution, updates its policy at most S Rd2 log2 (T) times.
Theorem 4.2. Given 8 E (0, 1), with probability 2 1 8, the regret of RS-GLinCB (Algorithm 2) satisfies R - (d Exe(ry is (1xt, (1) log (RT/6) + rdl s² log" (T/6)).
Remark 4.3. Switching Criterion I is essential in delivering tight regret guarantees in the non-linear setting. Unlike existing literature [7], which relies on warm-up rounds based on observed rewards (hence heavily dependent on reward models), RS-GLinCB presents context-dependent criterion that implicitly checks whether the estimate (a 0o)) is within constant factor of ((x,8")) (see Lemmas B.3 and B.4). We show that the number of times Switching Criterion I is triggered is only (nd log (T)) (see Lemma B.1 I), hence incurring a small regret in these rounds.
Remark 4.4. Unlike [1], our deterninant-doubling Switching Criterion II uses the scaled design matrix H, instead of the unscaled version (similar to V). The matrix He, estimating the Hessian of the log-loss, is crucial for achieving optimal regret. This modification is crucial in extending algorithms satisfying limited adaptivity setting M2 for the CB problem with a linear reward model to more general GLM reward models.
Remark 4.5. The feasible set for the optimization stated in 8 is ellipsoid around o.. which contains 0" with high probability. Deviating from existing literature on GLM Bandits which projects the estimate into the ball set of radius S ([e ||0|| < S}). our projection step leads to tighter regret guarantees; notably, the leading /T term is free of parameters 5 (and R). This resolves the conjecture made in [17] regarding the possibility of obtaining S-free regret in the /T term in logistic bandits.
Remark 4.6. The regret guarantees of the logistic bandit algorithms in [2, 17] have a second-order term that is minimum of an arm-geometry dependent quantity (see Theorem of [17]) and dependent term similar to our regret guarantee. Although our analysis is not able to accommodate this arm-geometry dependent quantity, while the above works are not. In fact, to the best of our knowledge, the other known efficient algorithms for logistic bandits [7, 28] also do not achieve the arm-geometry dependent regret term. It can be interesting to design an efficient algorithm that is able to achieve the same guarantees in the second-order regret term in [2, 17].
underscore that algorithm is computationally efficient
"This optimization problem non-convex. However, a convex relation this optimization problem detailed Appendix F, which leads to slightly worse regret guarantees in poly( R, S). We note that in case is unknown, any known upper bound on x suffices for the algorithm.
8

---

Cumulative Regret vs # of Rounds
Cumulative Regret # of Rounds
3000
RS-GLinUCB (This work)
RS- DS--GinUCB (This work)
FCOLog (Raury 2022)
2000
GLM-UC8 (Filippi et
Cumulative Regret
2500
GLOC (jun et al. 2017)
Cumulative Regret
GLOC (jun al. 2017)
1,500
1000
500
500
7500 12500
# of Rounds
of Rounds
Logistic with T 20000, (avg of 20 trials)
Probit with T 20000, (avg of 20 trials)
45
RS-GUnUCB (This work
Guinuce (Ths world Gaocc IJun en al. 2017)
ECDLog Mhaury 2022)
35
Execution Time (s)
25
20
Execution
20
10
10
Low Kappa
High Kappa
Low Kappa
High Kappa
Figure 1: Top: Cumulative Regret vs. number of rounds for Logistic (left) and Probit (right) reward models. Bottom: (left) Execution times of ECOLog and RS-CLinCH for different values of x (low 9.3 and high x 141.6) for Logistic rewards. (right) Execution times of GLOC and RS-GLinCB for different values of & (low 17.6 and high x 202.3) for Probit rewards.
Experiments
tested the practicality our algorithm RS-GLinCB against various baselines for logistic and generalized linear bandits. For these experiments, we adjusted the Switching Criterion I threshold constant RS-GLinCE to 0.01 and used data from both Switching Criteria (I and II) rounds to estimate These modifications do not affect the overall efficiency as is calculated only O(log(T) times. The experiment code is available at https: /g thub. com/nirjhar Vass/GLBnddtt..... L_immn ted_ Adaptivity,,,.
Logistic. We compared RS-GLinCB against ECOLog [7] and GLOC [14], the only algorithms with overall time complexity Ö(T) for this setting. The dimension was set to d = 5, number of arms per round to K 20, and 0 was sampled from d-dimensional sphere of radius S 5. Arms were sampled uniformly from the d-dimensional unit ball. We ran simulations for T 20, 000 rounds, repeating them 10 times. RS- AS-GLinCB showed the smallest regret with flattened regret curve, in Fig. (top-left). Probit. For the probit reward model, compared DS-GLinCB against GLOC and GLM-UCB [8]. The dimension was set to 5 and number of arms per round to 20. 8" was sampled from a d-dimensional sphere of radius S 3. Arm features were generated similarly in the logistic bandit simulation. We ran simulations for T 5, 000 rounds, repeating them 10 times. RS-GLinCB outperformed both baselines, as shown in Fig. (top-right).
Comparing Execution Times. We compared the execution times RS-GLinCB and ECOLog. We created two logistic bandit instances with d 5 and K 20, and different x values. We ran both algorithms for T' = 20, 000 rounds, repeating each run 20 times. For low RS-GLinCB took about one-fifth of the time of ECOLog, and for high K, slightly more than one-third, as seen in Fig. (left- beft-bottom). This demonstrates that RS-CLinCE has significantly lower computational overhead compared ECOLog. We also compared the execution times of RS-GLinCB and GLOC under the probit reward model, creating two bandit instances with d = and K 20, but with differing k. We ran both algorithms for T = 20, 000 rounds, repeating each run 20 times. The result shown in Fig. I (bottom-right). We observe that for low k. RS CLSnLinCB takes less than half time of GLOC while for high H, it takes about two-third time of GLOC. more detailed discussion of these experiments provided in Appendix D.

---

Conclusion and Future Work
The Contextual Bandit problem with GLM rewards a ubiquitous framework for studying online decision-making with non-linear rewards. We study this problem with focus on limited adaptivity. In particular, we design algorithms B-GLinCB and RS-GLinCB that obtain optimal regret guarantees for two prevalant limited adaptivity settings M1 and M2 respectively. A key feature of our guarantees are that their leading terms are independent of an instance dependent parameter that captures non-linearity. To the best of our knowledge, our paper provides the first algorithms for the CB problem with GLM rewards under limited adaptivity (and otherwise) that achieve K- x-independent regret. The regret guarantee of RS-GLinCE, not only aligns with the best-known guarantees for Logistic Bandits but enhances them by removing the dependence on S (upper bound on | ) in the leading term of the regret and therefore resolves conjecture in [17]. The batch learning algorithm B-GLinCE,
for M = S2 (log T)), achieves a regret of Ô (RRS (Va/RA V1/K* VT) We believe that the dependence on along with the term is not tight and improving the dependence is relevant direction for future work.
Acknowledgments and Disclosure of Funding
Siddharth Barman gratefully acknowledges the support of the Walmart Center for Tech Excellence (CSR WMGT-23-0001) and a SERB Core research grant (CRG/2021/006165).
References
[1] Yasin Abbasi- Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24, 2011.
[2] Marc Abeille, Louis Faury, and Clément Calauzènes. Instance-wise mitima algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691-3699 PMLR, 2021.
[3] Peter Auer. Using confidence bounds for exploiaation-exploraiio trade-offs. Journal of Machine Learning Research, 3 (2ooo))))7-422, 2002.
[4] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Geoffrey Gordon, David Dunson, and Miroslav Dudfk, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statisties, volume 15 of Proceedings of Machine Learning Research, pages 208-214, Fort Lauderdale, FL. USA, 11-13 Apr 2011. PMLR.
[5] Louis Faury. Variance-sensitive confidence intervals for parametric and offline bandits. Theses, Institut Polytechnique de Paris, Oct 2021.
[6] Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. International Conference on Machine Leurning, pages 3052-3060. PMLR, 2020.
[7] Louis Faury, Mare Abeille, Swang-Sung Jun, and Clément Calauzènes. Jointly efficient and optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 546-580. PMLR, 2022.
[8] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in neural information processing systems, 23, 2010.
[9] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. Advances Neural Information Processing Systems, 32, 2019.
[10] International Stroke Trial Collaborative Group et al. The international stroke trial (ist): randomised trial of aspirin, subcutaneous heparin, both, or neither among 19 435 patients with acute ischammic stroke. The Lancet, 349(9065) 1997.
10

---

[11] Yanjun Han, Zhengqing Zhou. Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye. Sequential batch learning in finite-action linear contextual bandits. arXiv preprint MMKiv:000400633 2020.
[12] Osama Hanna, Lin Yang, and Christina Fragouli. Learning from distributed users in contextual linear bandits without sharing the context. In Alice Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[13] Osama Hanna, Lin Yang, and Christina Fragouli. Efficient batched algorithm for contextual linear bandits with large action space via soft elimination. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[14] Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable gen- eralized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems, 30, 2017.
[15] Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
[16] Tor Lattimore and Csaba Szepesvári. Bandit Algorithuss. Cambridge University Press, 2020.
[17] Junghyun Lee, Se- Young Yun, and Kwang-Sung Jun. Improved regret bounds of (multinomial) logistic bandits via regret-to- coo--oniddenc--see conversion. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, pages 1474-4482. PMLR, 02-04 May 2024.
[18] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[19] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
[20] Blake Mason, Kwang-Sung Jun, and Lalit Jain. An experimental design approach for regret min- imization logistic bandits. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7736-7743, 2022.
[21] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1456, Paris, France, 03-06 Jul 2015. PMLR.
[22] Zhimei Ren and Zhengyuan Zhou. Dynamic batch learning high-dimensional sparse linear contextual bandits. Management Science, 70(2):115-1342, 2024.
[23] 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, pages 74-87, 2021.
[24] Yoan Russac, Olivier Capp'e, e, and Aurélien Garivier. Algorithms for non-stationary generalized linear bandits. ArXiv, abs/2003. 10, 2020.
[25] Eric M Schwartz, Eric T Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500-522, 2017.
[26] David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 1944)1190411931, 2022.
[27] Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trendy@ in Machine Learning, 8(1-2):1-230, 2015.
[28] Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. In Teirty-seventh Conference on Neural Information Processing Systems, 2023.
11

---

Generalized Linear Bandits with Limited Adaptivity Appendix
Table of Contents
1
Introduction
1.1
Our Contributions
1.2
Important Remarks on Contributions and Comparison with Prior Work
2 Notations and Preliminaries
2.1
Instance Dependent Non- Von-Linnerrty Parameters
2.2
Optimal Design Policies
3 B-GLinCB
4 RS-GLinCB
7
5 Experiments
6 Conclusion and Future Work
10
A Regret Analysis of B-GLinCB
13
A.1
Additional Notation
13
A.2
Concentration Inequalities and Confidence Intervals
................................
13
A.3
Preliminary Lemmas
16
A.4
Proof of Theorem 3.2
19
A.5
Optimal Design Guarantees
20
Regret Analysis of RS-GLinCB
21
B.1
Confidence Sets for Switching Criterion rounds
................................
22
B.2
Confidence Sets for non-Switching Criterion rounds
................................
23
B.3
Bounding the instantaneous regret
25
B.4
Proof of Theorem 4.2
26
B.5
Bounding number of policy updates: of Lemma 
27
B.6
Some Useful Lemmas...
27
Useful Properties of GLMs
28
Computational Cost
31
E Projection
32
E.1
Convex Relaxation
33
12

---

A Regret Analysis of B-GLinCB
A.1 Additional Notation
We write e to denote absolute constant(s) that appears throughout our analysis. Our analysis also utilizes the following function
(A) 24RS (Vlog (T) +d+ R (log (T) + d) 2SVV.
VA
Note that (A) is a "parameterized" version of y (which was defined in section 3). In our proof, we present the arguments using this parameterized version. A direct minimization of the above expression in terms of would not suffice since we need À to be sufficiently large for certain matrix concentration lemmas to hold (see Section A.5). However, later we show that setting À equal to cRd T leads to the desired bounds.
We use ह to denote the scaled versions of the arms (see Line 11 of the algorithm); in particular,
jt (z, Buc)
T ==1
((x) a
(10)
Furthermore, to capture the non-linearity of the problem, we introduce the term ((A):
<(A) vk e 7(1)
Recall that the scaled data matrix H2 (for each batch k) was computed using Ow as follows
11 (1r Owi)
H
Dea + AI.
B(xz)
LET
Following the definition of H₃ and using the true vector l* we define
H
Σ j ((x, 1ET
maa + AI.
We will show that H, dominates Hद with high probability. Furthermore, we assume that the MLE
estimator 8* obtained by minimizing the log-loss objective always satisfies @ S. In case, that's
not true, one can use the non-convex projection described in Appendix E. The projected vector
satisfies the same guarantees as described in the subsequent lemmas up multiplicative factor of Hence, the assumption [
< S is non-limiting.
A.2 Concentration Inequalities and Confidence Intervals
Lemma A.1 (Bernstein's 's Inequality). Let Xi...., X, be a sequence of independent random vari- ables with [Xe- E [X,]| < b. Also, let sum S Er (X, E (Xi]) and v >m= Var [.]. Then, for any 8 E [0, 1]. we have
1
2b
P S2
2u 2o
+
log
5
8
3
8
Lemma A.2. Let X 121, T2...., I.J Rdd be set of vectors with | < 1, for all t [s]. and let scalar X 2 0. Also, let Tı, T2,,2,... r...... Ts E [0. R) be independent random variables distributed by the canonical exponential family; in particular, E [ra] = μ ((t,,, 0*)) for 6* E Rdd. Further, let ① arg ming Σt_ f(0, T.) be the maximum likelihood estimator of 0* and let matrix
H Σ ((( AI
13

---

Then, with probability at least than 1 1 T2, the following inequality holds
10- 01 S 24RS
(Vlog (T) d
R (log (T) + +d)
+ 25V
(I1)
VÁ
Proof. We first define the following quantities
a(x,0" 0) [ 1 (12,87 + 0(z, 00) de
G Σ alxx00 ",,000,00000 ;0)2, + 1 2RS
A
j=1
Using Lemma C.2 we have
G 7
+ 2RS H
(12)
Hence we write
00- 0 S Sv(1 ())S)
0
G
=V1 2RS
G 8 0) 8)1l
V1++++ 2RS
Σ (0 x3)) (0, x,) a(x, 0r,,,0,00000 0)z,
A
(0- 0)
+ 2RS
LV++ 2RS
Σ p ((0", 2z)1) - 1 (0, Ij
X
8" 0
vI + 2RS
G-1
G-1
$ /1 2RS
Σ (100 ((0",,,)) 1 (0.22)) zj
2SVV
G-1
(since > 142R5
and 10- s 25)
$ 3RS
Σ
p ((("",,))) - ((,,2)))) x2
+ 2SVÁ
1=1
H (Using (12) and assuming RSS 2 1)
Now by the optimality condition on we have Σÿ=1 1 ((z),0) xj = Ej= ry (see equation (3) [8]). Hence, we write
Σ ((0)x;;)))- (0. xz
Σ (,,)),,,))) - rr))
(13)
H-
H
Let B denote the unit ball in Rd,, We can write
Σ (n (10), ,x,)) - rr)) x
max
1/2 DEB
(,, H 1/2
(μ (10", ,z))) r3) xz))
5=1
==1
14

---

We construct an e-net for the unit ball, denoted as C.. For any E B, we define =
arg min || 8ll2. We can now write
Σ (a ,(11),)))))--)))))0))(((())))))) -b))
H--11
max FEB
Ve H 1/2
Σ (e (10", ,0,)),,)))))))),}} -1)))~1)) 2z)+ (ye. H 1/2 H-1111
Σ
(n 110
.xz)) ((00),z)))
rz) xz))
j=1
I max yEB
|V Vell2
Σ
((0,,,))) (N (10", xzح) - rz)
+ Wys. H
11/2
Σ
(10" ,10)),,}))) - 1z)) x3))
j=1
H--1
==1
S max yEB
( ((0,,,)) -r))
+ (ye H 1/2
(μ (((00,=))) r3) x3))
H--1
==1
Rearranging, we obtain
Σ (m - -rj) -r)))
1 We: H 1/2
1
Σ
(n(10) r2) mz))
Next, we use Lemma A.3 (stated below) with cel and union bound over all vectors in C..
We also observe that [Cal < (2)² Substituting = 1/2 and using Lemma A.3, we obtain that the following holds with probability greater than
T
4R 3v
(n (10", (2,0)
s 3 (T2 +
log (T
log (T)+d+ (log (T) + d)
Vx
Substituting in equations (13), get the desired inequality in the lemma statement.
Lemma A.3. Let be fixed vector with llvil < 1. Then, with the notation stated in Lemma A.2, the following inequality holds with probability least
2R 1 H 1/2 12 S / 2 + 3vX
Σ (1010 (((00)),))))00 - 1y)D - 1=1
log
3'
Proof. Let denote the jth term of the sum as Zy. Note that each random variable Z, has variance
Var(Z,) = ja (1z,, (1);,00) H -1/2xx1)) 2
Hence, we have
Var(2,) = Σ a (10", xz)) ( H - 1/2 112 )
j=1
1=1
= uy u 1.
Moreover, each 4j is at most 1, we have
R (since ||,
< 1, H' > AI and r E RD.. Now applying Lemma
8
2R
1
P
Zj 2 /
22og +
log
56.
3V
15

---

Corollary A.4. Let T2.2...... be the sequence of arms pulled during the warm-up up batch and let ow be the estimator of 0 computed the end of the batch. Then, for any vector and X 0 the following bound holds with probability greater than 7
Kr,, 0- 0w)l V | 7(2).
Proof. This result is derived directly from Lemma A.2 and the definition of (()) (see 9), By applying the lemma, we obtain
Kr, 0" 0w)) ||
100 0m
S ||
((A)
Considering the definition of K, we have jo ((x, 0*)) 2 x. This implies that H > 1 LV 13 which in turn leads to the inequality ||- S /n 1æl|y
A.3 Preliminary Lemmas
Lemma A.5. For each batch k 2 2 and the scaled data matrix Hç computed at the end of batch, the following bound holds with probability at least 72:
H 1 H
Proof. If the event stated in Lemma A.4 holds,
From Lemma C.2, we apply the multiplicative bound on já to obtain
ji (1r, Owi) S i ((x,0")) exp [2] (2, 0n. 0-31)
Via Corollary A.4 we have Kax 0w) - (1,, 00 S vk || 7(A). Additionally, given that i ||0'| s S and |||||| I 1 we also have (xx, Ow) (z. 8.) s 28. Hence, we write
(1r, Bwi) S ja ((x,, 0-)) exp (Rmin(vai ( 7(A), S ju ((x,0")) ((x)
Substituting these results into the definitions of H2 and Hद proves the lemma statement.
Claim A.6. The Algorithm runs for at most log log batches.
Proof. When M < log Iog T then the claim trivially holds. When M log log T + 1, define the length of the second batch, T2, 2. The length of the Mhh batch is
TM (2VT) #
2T T
2T T TloglogT 2 T.
(M 2 log log T + 1)
Corollary A.7. Let 9g be the estimator of 8* calculated at the end of the Eth batch. Then for any
vector x the following holds with probability greater than log log I for every batch k 2 2.
T2
{ 0- - 0201 S | |01| ((A) T(A)
For logistic rewards, note that instead of using the worst bound of one make use of upper bound on ||0|| as done in [20] That is, we lower bound j (xx,0") 0))) 2 ||=l]) and
H E, á (S |[xel) mea..
16

---

Proof. This result is direct consequence of Lemma A.2 and the definition of (AA) (see 9). According the lemma, we have
(0, 0" -aai S ||
80 0/
H
|| ((1)
Using Lemma A.5, we can further bound | ||, S ||=||| H. -I. Finally, a union bound over all
batches and considering the fact that there most log log batches (Claim A.6) we establish the corollary's claim.
Claim A.8. For any E (0, M) the following holds
e" S (c 1) 1)
+ 1.
M
Proof. The claim follows from the convexity of e.
Lemma A.9. Let E X be the selected in any round of batch k 2 2 in the algorithm, and let x" be the optimul arm in the arm set X, ie., x² = arg max l ((x, 0*)). With probubility greater than
1 log the following inequality holds-
T
((x', 00'''0')--0000000000))0 1 (1x, (x,00)) 07) S 66())
Σ
11 I 10HH, + (A(=) 0+)) (1 (1E'llE22, + | (1
yE(n.e"
(E(E
Proof. We begin by applying Taylor's theorem, which yields the following for some between (xr, )*)) and (xe", ,0*)
1 ((x", (((=",0)) 87)) 4 ((x, (1) M=)) (xx, 0-) (a, 0-)
(14)
((=)) (x",0") 0-) (x" Ōx-1) (x", .o-1) - fx, On-1) + (xr, On - (ar, 0->
s (a()) (((0) 00) (x", 0)0 )) |:2" (e-,0x-1) - (zc, 0a-1) (2,, 0x-)) (z, 00)
< 21(x)) (10" 7(A) + 11 7())
(via Corollary A.7)
8(x*)
B(x)
< 2(((=)((A)
12 || +
|| l
A (a0,, Bu))
A
(zx, Bwn)
(*=)){(²*))
i(=))((x)
22y(A) Axz))
|| H. + +2 (222((A)))
1
(15)
i (2,, ((x,
17

---

We now invoke Lemmas C.2 and A.4 to obtain
ii(z)
B(x) = / exp [iin
2S. /= (or, bwi)) 3(x)
j (x, Bue)
(by stated assumptions and Lemma C.2)
S. (xr 0*) - (2r, 2l + Kr,, 0*) =1 -11) v (((z)
I exp
min
2
S. (1r, 07) - (or, Ownil + Kr,, 0-) - (x= 03) (00,00) }) 33(x)
S
exp
min
(since E [(,, 0*), (x7, 07))
3/R |2 (A) + 2 1 llv- 7 min { S,
S exp
((x)
2
(using Lemma A.4 and the elimination criteria) (A) + v ||= 1 (A)})
S exp (min {25, 228,2v/llzrll 7
(substituting the definition of ((x))
Similarly, we also have
vx(z) S Vi(l"* ,,))) exp (min {8, VR | 7 (A) + VFl|="/lv- 7 (A))).
Further, we can simplify each term in equation (15) as
M)=)B(=*)
()))
1 H
it (1o Ow))
< 2/// (12", ((x,,-))) |13 leae.
exp (min 3, (A) (1 + || -v)]))))))
/ /1 0+)) is a5 7(2)
< 6
[1l="ll-- (I [I |3
+ +2)(A) es (1r 03) || 1| H (via Claim A.8)
S 6 , 7(A)
(1 + /ally 1) ||2'
+210))/ 0*)) || 11
(6/ū(lx ((0,((000)))000 ()(()) 1lv- [ 1 (22( 1 1 m
Finally, we substitute the above bound (15) to obtain
Il (()",0))) a ((2, 0')) s6 ((( (1="Ilv- llv-1 + I[lllv-)) 11a..
1 (
+2VB (0)) (10"llez)) + (
For Phase k. the distribution of the remaining arms after the elimination step (X' in line 10 of the Algorithm 1) is represented as Dj.
Lemma A.10. During any round in batch k of Algorithu 1, and for an absolute constant c, we have
o(A)d
7(A)
d
lo d
[| (1x", 00)) 1 (1x, 5c
V TK-1
R
18

---

Proof. The proof here invokes Lemma A.9. We begin by noting that
I1 18 S
EE X-DD
max
|x
v=llv=
max
H
XDDA
FEA
xEX
MC [ (3,3*)
4
max |
N-DD DEA
N~Dx
x
H
(via Jensen's 's inequality)
4
EE
max
|0
E XWDI
max xEX
X-D
ZEX
(via Claim A.11)
dc
d²
Sc
1
(using Lemma A.1
-
We also have
IR X-DDy
(V(((r000))
(175 H
+
||
< x-Dx
Vii(ter,0)) (+))
max
|||||
||
ZER
< min
Vk-
XnDD
E
max ZEx
|
V
E X-DD
J ((x
(0))
x-DD
E
|
(using the definition for the first bound and Jensen for the second)
sc
dlog d Tx-
d2 RTL-1
(using Lemma A.17)
Substituting the above bounds Lemma A.9 we obtained the stated inequality. This completes the proof.
A.4 Proof of Theorem 3.2
We trivially upper bound the regret incurred during the warm-up batch as Ti R: recall that R denotes the upper bound on the rewards and denotes the length of the first (warm-up) batch; see equation (5)).
For each batch & and an absolute constant c, Lemma A.10 gives us
o(A)d + 7(A)
d
d d x
E
Σ
# ((at, (*)) ((x,,
S c.
^
VTI Tk-1
VTh-1
VR
LIET
((A)d
d dlog
Sc
VT a
+
7())a)
(via (3))
x²
Since there are at most log log T batches, we can upper bound the regret
@(A)dt
A d d
RT Sc c
TR+
a+
7a)a
log log(T")
x*
((A)d&a 2/3
Setting
we get
(())da
2/3
d
dlog
R 5
^
2(2)a)
log log())(T))
R
Now with the choice of 20dR log T, we have
T(X) 5 where y 30RS d
19

---

Substituting a = 2 (r)
and ((A)
v/ c98 32
we get
RT $0
((rdt ea RST logT)
2/3
+
d
dlog d
RST 2 Vdlog
VR
n²
A.5 Optimal Design Guarantees
In this section, we study the optimal design policies utilized in different batches of the algorithm. Specifically, TG denotes the G-OPTIMAL DESIGN policy applied during the warm-up batch, while m refers to the DISTRIBUTIONAL OPTIMAL DESIGN policy calculated at the end of batch and used in the (k: 1 batch). Recall that the distribution of the remaining arms after the elimination step X' in line 10 of the Algorithm) is represented as Dr. We define expected design matrices for each policy:
WG = XND pontt
Fx
[
W = X--D
IT [X]
Recall, for all batches starting from the second batch (k 2 2), we employ the scaled arm set, denoted as X' for learning and action selection under the DISTRIBUTIONAL OPTIMAL DESIGN policy. However, during the initial warm-up batch, we utilize the original, unscaled arm set.
Claim A.11. The following holds for any positive semidefinite matrix A and any butch k-
E max ||~||| S I max | X~D, sE
Vj E [k: 1].
X~D,
ZEX
This is due to the fact that the set of surviving arms in batch & is always smaller set than the previous batches. Lemma A.12 (Lemma 4 [23]). The expected data matrix WG satisfies. We have
E
max TEX
|
de
Lemma A.13 (Theorem 5 [23]). Let the DISTRIBUTIONAL OPTIMAL DESIGN क which has been learnt from independent samples No ~ D and let W denote the expected data matrix,
W
Ex-D
E xx (x)x(x)
| We have
]
} 21 } -expexp (0 (d* log d) sd 1d-12.2-10 (16)
E X
max REX
| w
< O (Vdlog
Lemma A.14, Under the notation of Lemina A.13, we have
E
max
||]| 2df.
(17)
AND
PEA
Proof. Recall that the DISTRIBUTIONAL OPTIMAL DESIGN policy samples according to the no policy with half probability. Hence, we have
W
MoDD
(x))(
E rx ||
E XrDD
2 (x)
xxx |
=
We
Therefore,
max ZEX
||0
max NEX
| ||
$ 2d
X~D
XnD
Lemma A.15 (Matrix Chernoff [27, 23]). Let 1i, #3, .., In ~ be vectors, with ||ate| S 1, then we have
n
3enI+ +
Σ
n
ET T
2 12dexxppp
(-
En
8
1=1
20

---

Corollary A.16. In Algorithm the warm-up matrix V, with 2 16 log (Td), satisfies the following with probability greater than
7
E
T.
8 ADD
Similarly HR. with A 2 6 log (Td) satisfies the following for each batch k 2 2 with probability greater than 1 T2
H
E E
T.
8 (~DE
Proof. The results for both V and H2, are obtained directly by applying Lemma A.15 with log(T) and
m
log(T) respectively.
We note that the analysis of [23] gives an optimal guarantee (in expectation) on || but not on | We obtain such a bound here and use it in the analysis.
Lemma A.17. The following holds with probability greater than 1
7
de
E max X-D
|
0
(18)
ZE
T
d2
max
ã H S
Ak E [M]
(19)
XDD, ZEX
We also have that for sufficiently large T 2 O 2 27 2), the following holds with probability greater than 1 log
d
E max ZER
<0
vk E [M]
(20)
H
7k
Proof. First, note from Corollary A.16 that the following holds with high probability
8
|| I
|ællww"'
IV
lw
We obtain the first two inequalities, (18) and (19), by direct use Corollary A.16. For (20) we note that for every phase we have at least O(VT) samples for learning the DISTRIBUTIONAL OPTIMAL DESIGN policy (for any M). Since, T 2 d log27 27 the event stated Lemma A.13 holds with probability greater than T2-
B Regret Analysis of RS-GLinCE
Recall To denotes the of rounds when switching criterion is satisfied. We write to denote the size of the set T, = .To. We define the following (scaled) data matrix
H
Σ j
+ AI.
SET
We will specify the regularizer À later. We also define
T dlog 8
7 =
cRS
Below, state the main concentration bound used in the proof.
21

---

Lemma B.1 (Theorem 1 of [6]). Let {Fi)e=1 be a filtration. Let { be stochastic process in B, (d) such that 24 F, measurable. Let {neeen be martingale difference sequence such that ne is Fr measurable. Furthermore, assume we have (nel S 1 almost surely, and denote of = [..)FF)
Let > and for any t. 2 define:
1-1
St = Σ
H
Σ
0 2 + XI
==1
Then, for any ò E (0, 1].
A
2
det (H,)
2
P 32 1: |S 1
2 2
log
logg(2)
28
VA
Ad/28
VA
B.1 Confidence Sets for Switching Criterion rounds
Lemma B.2. At any round t, let 9, be the maximum likelihood estimate calculated using set of rewards observed in the rounds To With probability at least - 5 we have
10. 0- 1H 5.
Proof. Let us define the matrix G ESET. a(x, Hr 2 + AI. First, we note that by self-
concordance property of μ (Lemma C.2), G 2 I+28S H Hence,
10. 0" ||; < v1 2RS
0. GG
Gw 0 - -0*)
vI++ 2RS
VI + 2RS
Σ (0., σz) - -10" x0*, a(x, a(I,, 0) + +10 - 1,0
G=1
VI+ 2RS
Σ (M ((o. - -u (10 (10", x())) xs + +0= 110"
TETo
(Taylor's theorem)
$ (1 + 2RS)
Σ (1 ((66) ((0)),z))) .2.1)) Is 10. X0
TE
(G w 1-2RS H
Since 8, is the maximum likelihood estimate, by optimality condition, we have the following relation: EXET, l (0. Is 20 EOET, Tg Substituting this above, we get
10, - 0¹ 001 S (1 + 2RS)
Σ (r. - 10 ((00,, ;x,)), xs - 20
SET
H
< (1 + 2RS)
Σ
(rs - / ((00))))))))) Fs
+ A ||0*|| I
SETo
H
< (1 + 2RS)
Σ
71
+SV...
(H = A.I, 110 SS)
TTT
H
where n1 = (r. - μ (10", xz))).
We will now apply Lemma B.1 7) scaled by R. First note that E.ET. To notall
EOET. 3 ( 1 which, turn ensures that the noise variable upper bounded by
22

---

Applying B.1 we get
110 - 11 S3V
+ +1++2RS)
R
2d
log
1
To
2
log ( + VnEa
d dloo((2)
2
VR
R2
VR2A
Simplifying constants and setting VR = cydlog(T) + 1og(1/6), we have 10. -0-
H
cRS + log(1/6) edl (T/8).
B.2 Confidence Sets for non-Switching Criterion rounds
We define e be the event defined in Lemma B.2, that is, & = {100 0 11, S 5T). Lemma B.3. If in round the switching criteria I is not satisfied and the event En holds, have
1 10x, 0. - -0) S R
for all x E 24
Proof.
(2, 8 80)1 s || Al
110. 8* 1H:
(Cauchy-Schwarz (via Lemma B.2)
< || 1
- TV /K||=llv...
(V <H
S /VV VRewm?
(warm-up criteria is not satisfied)
1
R
Recall that H, is defined in line 14 of Algorithm 2. Further, we define
H Σ
ja (It,,0)) xxNI + AI
1|TT
Corollary B.4. Under event Ex.. H. < H 3 H
Proof. For a given s E [t - 1] To, let Ø: denote the value of 0, in that round. Then, for all x E X.. by Lemma C.2,
i (z) exp(-Rl 0: 0*))) S S ((x, sp e ((x, 0:)) exp(()(a, 0*))
Applying lemma B.3, gives e i (Ir S ((x, 0*)) S etip 0::)0) Thus,
H Σ e (1:z F. + IK
Σ
((1x,)0)) + = H;;
-E(t-1JTTo
E 1|oTo
Further, H; 3 ESE[t-IJNT 2
EzNI + 2 AI H
23

---

Recall that т is the round when the Switching Criterion II (Line 9) is satisfied. Now we define the following quantities:
(r)
Σ
1 (( 0)) + 2,0
sE(r-11VTo
Σ
A ((055 8)) x, AI
xc(r-1](To
(0:
0,
S T
0 = arg min BER
Σ (a,
sE(t-IIVT 1TTo
8 = ev dlog(T/)))
Moreover, recall the following definition 0-:
0, arg min oee
(-((0) (0)
(21)
(0)-1
0, 0- 00lly S 2/
Lemma B.5. Under event En
Proof. First, we observe from Lemma B.2 that
10.
0- H
S. Using 3 xH we can write
@. 0%-6-11, 801,, S.R.. This implies that 0" O. Now, θ by virtue of being feasible solution to the optimization in (21). Thus,
00 8r
0- 0, 0, 0" lv
S 0- 0o
+ 110 8"
(triangle inequality)
< k
Lemma B.6. Let E (0, 1). Then, under event E with probability - 6, 10_ -0"
S 8.
H
Proof. We have for all rounds
[T - 1] To.
Kx,, 0" - 0- S || lo -1 1
(Cauchy-Schwarl
| 1
(by Lemma B.5)
< 27/F RyVe
(warm up criterion not satisfied)
2
Also note that 0* ④ Hence,
00, - 0r
< 2 +
(-(0") - Σ TyT
(by Lemma E.
H;
-E/7-1]
S 6c (loglT)
(by Lemma B.
Let the event in lemma B.6 be denoted by E,, in other words, E, = (100, 0011H;; S B}.

---

B.3 Bounding the instantaneous regret
In this subsection, we will only consider rounds E [7] which does not satisfy Switching Criterion I. Let 24 Ng be the played arm defined via line 13 Algorithm 2. Further, let 2 E X be the best available arm in that round.
Corollary B.7. Under the event for all E X, we have, 1x, 0- -8") - B| H.
Proof.
1e, 6,
-0 < ||0| -: -10,1110,,- -0 11:;
Gauchy-Schwance (by Lemma B.6) (H, = H
|||2|| H.
Lemma B.8. Under event E (2z Iz, 0*) s 2/23 || l|;
Proof.
(0,,0) (10,0')
$ (at, σ.) + || (1piilla;=)))) - ( 0z) - 3 [|seella; )) (by Corollary B.7)
$ (Ze. 07) + (1000l1s0=))
(aTe 07) - -11 (|:)||l;=-)
(optimistic 2t, see line algo. 2)
23 ||rellaı--
$ 2/2 ||alllr
(Lemma B.13, det(H,") det(H, det(H,
det(H.)
S 2)
Lemma B.9. The arm set X; obtained after eliminating arms from Xe (line 12 Algorithm 2), under event Ew, satisfies: (a) xt E X2, (b) {z) 22, 6", S R
DEX, Proof. Suppose o' = arg max mxx, (C). Now, we have, for all x E Xx
1rx, 0. 00)1 $ ||
10.
0r H
(Cauchy-Schwand
S ||
(by Lemma B.2) 3 xH
s ~7
Thus, UCB,(=)) = (x) (x;;) LCB,(zz) where the second inequality is due to optimality of xt. Hence, x; is not eliminated, implying of E XY. This completes the proof of (a).
(x, 2 (5',0") 0*) 2 (.. /VR||=1/) ll
Since x, is also in X (by definition).
UCB.(x)) (xx, 0.) 7 | 2 (x' 0a) TVF lo'llv-
2 (1i 0o) - ~V/ |
(o' has max I.C..())
Again, using the fact that (xi 0o)
2
(2; - 7/1 | and (o,, 0.) $ (I,, +
T ||æelly~ we obtain,
(m),0") + 27 |arlll 2 (1i, - / |
which gives us (aj Fz, 0*) s 2y | 2/ -2illv-1
Finally, since Switching Criterion is not satisfied in this round, || Plugging this above,
Rie. for all X.
(x - Fz, 00) < R
25

---

B.4 Proof of Theorem 4.2
In this subsection, we complete the proof of the regret bound of RS- ASS-GinCB(Algoriim 2). We first restate Theoreom 4.2 and then prove it. For every round E [T') we use 24 Xr to denote the arm played by the algorithm and o; to denote the best available arm in that round.
Theorem B.10 (Theorem 4.2). Given 8 E (0, 1), with probability 2 1 ô, the regret of AS-GLinCB (Algorithm 2) satisfies Ry- = Od Evetry P (12t, 0*)) log (RT /ō) + kd ReS log (T/6)).
Proof. Firstly, will assume throughout the proof that NE holds, which happens with probability at least 1 - 6. Thus, regret of Algorithm 2 is upper bounded as:
Rx = Σ u ((xz,00)) - μ ((z,, 0*))
(E[7]
s RTo
Σ
a ((zi, (zx,,0))
(Upper bound of R for rounds in To)
TE
< cR. ky (Tg((T/)) +
E LEPINV
M(){a; - I2,0")
(some [rr, 0*), (at, 0*) lemma B.11)
Now, let RT) = = EigrrVT ((=)(x7 24, 8") Hereon, will slightly abuse notation H, to denote the H, matrix last updated before time for each time step i E [T). This will clear from the context as we will only use H, tirm-wise. With this, we upper bound Ri (T) as follows:
(T)
Σ
((=)28||z
(by Lemma B.8)
NE|TIVT
$ 228
Σ
A(z)2
21 |H."
(Lemmaa B.13, det(HH det(H.) det(H, det(H,
S 2)
EE
< 2223
Σ
A(z)e
(by Lemma B.4)
< 2B
Σ
(xxp))))) x4, (1,0
(
(by Lemma C.2)
< 2ev28
Σ
Vill,, 0)) ((x,, 0-))ee ||
(by Lemma B.9)
TE/TTTT.
V23
Σ
(1 8*)) 1o ((z,, 0-1) |
+E(T]VT,
V28
Σ
(1 03)) |
(++ Vi ((r,, 0-)),a))
EE[T]T
$ 228
Σ
Σ 1ELTIVT
|
(Cauchy-Schwarz)
HELTIYTO
5 2222V28
Σ
2d
1+
RT Xd
(Lemma B.12; | S R)
nE(TIiTo
< <odlog(RT(8)
Σ
i ((12,0+))
tE(TTTT
26

---

Putting things back,
Rr S ed Collog(R//)
Σ
(((22,00)
cR x
NE(TIVT.
B.5 Bounding number of policy updates: Proof of Lemma 4.1
We first obtain a bound on the number of rounds when Switching Criterion I is satisfied. Then we restate Lemma 4.1 and present its proof. Here, use To denote the collection of all rounds till T for which Switching Criterion I is satisfied.
Lemma B.11. Algorithm 2, during its entire execution, satisfies the Switching Criterion at most 2dR2xoy Roy² log (T) times.
Proof. Recall that Switching Criterion (Line 4) is satisfied, when ||]| > 1/(RR x)))))n)))))) for some E Xr. Let Vm be the sequence of V matrices (line 6 of Algorithm 2) for m E To. That is, V1 ΛI, Vm = E=Emm-Int 2z2 + AI. these rounds, by Line 5 of Algorithm 2, we have that the arm played z, is such that It = arg maxzex, || Therefore,
Σ LET
| 2
To
(22)
R2Ry
Furthermore, by the Elliptic Potential Lemma (Lemma B.12) have
Σ
| S 2d log (1
To
(23)
Ad
BT
Combining (23) and (22) we have
To S 2dR2 Nz? log (1 2dR2xy' log (T) s 2dRR2 k2? log (T/6)
Ad
Lemma (4.1). Algorithm S Ed log2(T) (T/8)) times.
during its entire execution, updates its policy most
Proof. Note that in Algorithm 2, policy changes happen only in the rounds when either of the Switching Criteria are triggered. The number of times Switching Criterion I triggered is bounded by Lemma B. 1. On the other hand, the number of times Switching Criterion II is triggered is equal to the number of times determinant of H, doubles, which is bounded by Lemma B.15. Thus in total, the number of policy changes in Algorithm upper bounded by 2d. ky (Tg()))) + edlog(T). L
B.6 Some Useful Lemmas
Lemma B.12 (Elliptic Potential Lemma (Lemma 10 [1])). Let 11, in nd and let ||æall2 I L for all E [t]. Further, let V. Em= Tm + Al. Suppose X 2 L?, Then,
... .2
be sequence of vectors
1 L
I.. 1 & 2d
(24)
Ad
Lemma B.13 (Lemma 12 of [1]). Let A z B > 0. Then
sup xT det(A)
Bx det(B)
=y0
Lemma B.14 (Lemma 10 [I). Let {x, ==1 be set of vectors. Define the sequence {Va)t Vt
V1 = AI V = V, + I. E 1t - 1]. Further, let | S L V E [t]. Then,
(V.) (A+ tL?
27

---

Lemma B.15. Let {I,} be set of vectors. Define the sequence (V ==s= as V1 VY. V V++1
V, Tzoly for E It 11. Further, let || - 4 E [t). Define the {1 T1, T2 ... Tm t such that: det(V the number of time doubling happens,i.e. m, most O (t))).)
2 ,,, but (V r=11-1) < 2 det ( for E (2,... m 1}. Then,
Proof. By Lemma B.14, det - (A +++12 /d) 4 But we have that from definition of det(V,) 2 det(V dem
2 2 det(V Tm
:
2 2m det(V,))
2m det(Vi)
2m-22
(Vi= = AD)
Thus, 2m $ (A+ (13/dd which implies that
IL? d
2m- $ 1
Ad
Hence, m S O(dlog())
C Useful Properties of GLMs
Recall that Generalized Linear Model is characterized by canonical exponential family, i.e., the random variable r has density function ps (r) exp (rz - b +
+ cr))), with parameter 2, log-partition function 6(-), and function c. Further, b(z) = nu(z) is also called the link function.
Hercon, we will assume that the random variable has bounded non-negative support, i.e., E [0, R] almost surely. Now, we state the following key Lemmas on GLMs
Lemma C.1 (Sell-Concordance for GLMs). For distributions in the exponential family the function u(-) satisfies that for all z E IR, [ī(z)] < Rj((z).
Proof. Indeed,
[x)] = [[(r E(r))(11
(Lemma C.3) (Jensen's 's inequality)
< E [[(r E|r)"
E [|r [[]] (r B[r]
s [[R(r E(r))
(r, [[] [0, R)
REE(( - E[r
RRŌ(2)
(Lemmaa C.3)
As consequence, we have the following simple modification of the self-concordance results of [6].
Lemma C.2. For an exponential distribution with log-partition function b(-), for all 21, E IR,
letting μzz) = b(z), following holds:
a221,22) = [
f (2)
i (21 + u 211) 2 1 R|21 222
for E (21,
(25)
0=0
(x(22)
< ja (21) 1 (22)
(26)
パ|
a(21, 22) = 1' (1 v) (21 + 0(22 2)) do 2 + R| Zz
11
(1(1))
(27)
v=0
28

---

Proof. Without loss of generality, assume that 22 2 21. Note that by property of integration St f(=)dd= Jn f(b a x d2, a(221, z2) a 21). Now, by proposition C.I, and the fact that
ū(=)= = b (2), we have for any v and 2 2 21
Rí(() <ū(00 Rj((u)
(Lemma C.1)
R 2 j0(
R R
((v)
M(e)
R du S
du
R du
M(()
(122
- -R( 2- =1) S log
R( 21)
(1(1
((z1) exp( exp(-R((2 =1)) Sa(=) S ji(zı) exp - 21))
Putting& = 22 establishes 26. To show 25, we further set 2 = 21 + u(22 - 21) for u E [0, (note
that 2 2 21) and integrate on
((21) / exp(-Rtu(zz -1))dd S L. ii(z) + u(22 - =1))du - / exp(Heu(z2 - exp(-R(e - 21)) 2a(21,22) S (((z))
=1)) -xp(Ru((2>=)))
exp(R(z2 21 -1
which gives ((21) R(22 21)
R(22 21)
Next, the fact that for x > e < (1+x))1 which rearranging gives (1 - =>///0 1/(1 + x). Applying this inequality to the LHS above finishes the proof. Note that similar exercise can be repeated with 22 S 21 to get the same result for 22.
For 27, we have, by application of 26, (1(2 + 0(22 - 21)) 2 (1(1)) exp(2|o(22 - 21))). Therefore,
6(21,22) 22)
(1 - w)i (21 0 21)) du
v=0
u)) exp( - M|(221 22
M2x1
(1- v) exp( Rul(21 (21 22)
(u E [0, 1)
1
exp( - R|21 22)) -1
-(11)
R| 22
R2 [1 - 221
ji(z)) + R|21 22
(Lemma 10 of (2))
Next we state some nice properties of the GLM family that is the key deriving Lemma C.I.
Lemma C.3 (Properties of GLMs). For any random variable that is distributed by a canonical exponential family, we have
1. EE [r] = (2) = (()
2. Virj E -r)) (2) -=)==((2)
3. E (r - E|r1)*] (()))
29

---

Proof. 1. Indeed, since (r) is a probability distribution, Px()dr = 1 which in turn
implies that b(z) = log (J, exp(rz + e(r))dr). Thus, taking derivative,
b(z) = J, explr= + crr) /.
1
2 oz exp(rz + d(r))dr
/ rexp(rz + crr))dr
-
I rexp(r= b(z) + c(r)) [[rr]
2. Let f(z) = J, rexp(rz + dr Thus, = exp(= Taking derivative on both sides,
6(2) exx())))) -xsp(bb))
E|r]² + exp( bbz)) exp(r2 c(r))dr
= -R(r]² + ,² exp(1z b(2) + c(r))dr
= -[[r] + Bir²] = V(rl
3. Again let f(2) = J, r² exp(r2 )r. Thus, B(2) - -op((()()))) Taking derivative on both sides,
6 (2()) 2b(2)b(2) exp( +xp(bb())))
-2b())((2) b(=) 1 + / exp(rz- +c)))
-/ - E(rl B/
Now, let us expand [[(r _[r))
[[( - 1[r)) = 15|r - [r 16
E|rr1 - 3 3|//)111+++3111 E/
E 2
BBr* [E[] 2 [[]]
Corollary C.4. For all exponential b(-) is a convex function..
Proof. Indeed, note that b(z) V[r] which is always non-negative. Thus, b(=) > 0 implying that b(-) is convex.
Remark C.5. In [5] Section 1.4.1, the author claims that if the GLM parameter lies in bounded set, then the GLM is self-concordant, i.c.. [ū()) < af((z), for some appropriate constant a over this bounded set. Thereafter the author notes that the techniques developed in [5] guarantees x-freee regret rates (in /T term) for such GLMs (i.e., all GLMs with bounded parameter). However, the claim regarding self-concordance of GLMs is not true in general. There are classes of GLMs whose parameters may be restricted the exponential distribution. The link function for exponential distribution is given as puz) -
bounded set, but for them no constant a exists. One such example
we allow to lie in the set (-c, 0) for some positive c, then we have μ==)) strictly increasing (satisfying our assumption on monotonicity of μ. thus valid example). However, for this GLM,
1
2
((()) =
(a(2)
22
3
30

---

Note that jı() is positive for the assumed support of 2. Suppose this GLM is self-concordant, then we must have some positive constant such that
2
1
[i(z]
23 S app(2) a 22
Simplifying, we obtain the following relation:
2
5 a
However, since & E (-c, 0), we have lim,- - + oC. Hence, constant is possible. By this counterexample it can be seen that bounded parameter set not enough to guarantee self-concordance of GLMs. In this work, we give characterization of self-concordance of GLMs with bounded support of the random variable. It will be interesting to understand complete characterization of self-concordance of GLMs.
D Computational Cost
Consider log-loss minimization oracle that returns the unconstrained MLE for given GLM class with a computational complexity of Capt n, when the log-loss is computed over n data points. Let the maximum number of arms available every round be K. Furher, let the computational cost of an oracle that solves the non-convex optimization 8 be NCopt-
Computational Cost of B-GLinCB: In the B-GLinCB algorithm, we employ the log-loss oracle the end of each batch. The estimator 0 calculated at the end of batch of length incurs computational cost of CoptT. Furthermore, this oracle is invoked for a maximum of . S log log T batches. Additionally, the computation of the distributional optimal design the end of each batch is efficient in d (poly(d)). Moreover, in every round, the algorithm solves the D/G Optimal Design problem (requiring Od d) computation) and runs elimination based on prior (at most log log T)) phases. Hence, the amortized cost per round of B-GLinCE is O(K log log T + d log d + Copt).
Computational Cost of RS-GLinCE: In the RS-GLinCB algorithm, the estimator 0g is computed each time Switching Criterion I is triggered. Additionally, during rounds when Switching Criterion is not triggered, the estimator O, is computed a maximum of O(log(T)) times. These computations involve utilizing both the log-loss oracle and the non-convex projection oracle. Furthermore, in each non-Switching Criterion round, the algorithm executes an elimination step. This yields an amortized time complexity of OCCops log (T) + NCopt log" (T) + K) per round.
Performance in Practice: As evident from Fig. 1, RS- AS-GLinCB has much better computational performance in practice. ran all the experiments on an Azure Data Science VM equipped with AMD EPYC 7V13 64-Core Processor (clock speed of 2.45 GHz) and Linux Ubuntu 20.04 LTS operating system. was ensured that no other application processes were running while we tested the performance. We implemented and tested using time. time () command. We allowed no operations for 10 seconds after every run to let the CPU temperature come back to normal, in case the execution heats up the CPU, thereby causing subsequent runs to slow down.
code in Python, and measured the execution times
Comparison with ECOLog [7] shows that execution time for RS-GLinCB is significantly smaller. We posit that this because RS-GLinCB solves a large convex optimization problem but less frequently, resulting into smaller overhead at the implementation level, while ECOLog solves smaller convex optimization problem, but does so every round. On an implementation level, this translates into more function calls and computation. Further, we observe that with increasing the execution time of RS S--G CLinCB increases, which is in accordance with Lemma 4.1 that quantifies the number of policy switches increasing function of k.
While comparing with GLOC [14], we observe that RS-GLinCB performs better than GLOC both high and low regimes. Since GLDC runs online convex optimization (online Newton step) algorithm to generate its confidence sets, the time taken by GLOC nearly constant with changing K. On the other hand, in accordance with Lemma 4.1, 1, the computational cost of RS-GLinCB increases with k. However, after a few initial rounds, when neither of the switching criteria are triggered, RS RS-GLinCB does not need to solve any computationally intensive optimization problem, hence these rounds execute very fast. practice, with typical data distribution, RS-GLinCB reaches this stage much before what the worst-case guarantees show, hence it perform better than GLOC.
31

---

E Projection
We describe the projection step used in Algorithms and 2. We present arguments similar to the ones made in Appendix B.3 of [6]. We write
H
Σ ((0,x.)) + AI
Recall, H H(0)). Let θ be the MLE estimator of #* calculated after the sequence arm pulls 31, 22..... 2t. Let r1, P2....... be the corresponding observed rewards. We project to a set é by solving the following optimization problem
0 arg min E
Σ (a ((tr, 10 ((E,,))) Joc,
(28)
[H(0)
Lemma E.1. Using the notations described above, if E O and maxiej (2,, 10, -0) S c/R. then have
| 0r H(O-)
s cc)
Σ (a (lz,, 0*)) rs)
H((
Proof. First, we note that by self-concordance property of ja (lemma C.2), for any E [4].
iu (1 8*))
a(x,,0,0))
+ Rl (x 8r) i (1 17))
(max (x Ø -- 0-) s c/R)
Ríc/ R)
j (10, 0*))
1+
(z..))
Similarly, have axx,; 0,0*)
ltc
Let us define the matrix G = ΣxE(t) (xx 0, 0 )x.I.. Using the above fact, we obtain the relation:
G = + H' and G 2 1
Itc H(0). Also define the vector g(0) = Exc(s) # (10, xx)) x... Now,
0r H-
S /1
0
0-
(H' 3 (v]+
G
=V1+c c
0"
= =I+
Σ
(1(x, 00 0r, (x,) Es
KELA
c
= vl+c
Σ 11 0). - 11 ((=00,00 xx
(Taylor's theorem)
KE|t]
G-1
Σ 1r ((0.2z)) 23) 2.)
)
-(x (10", xx)))
= =1+c
sElt)
SE(()
G-1
32

---

Let g(0) = Ex=1 1 ((25. 0)) x, for any 0. Therefore, we have,
- 10-0' 0-
- VI+c
((0) g(0)) G-
H
VI+c
(0)) - ((0) +0(0) -g(0") a-1
3 +1+c
(0000 (
+
|0(0) s(00) 1000)
(A inequality)
(1:00) - 9
H(O) |0100 g(00)
S (1 +
(H) = (VI+c)G-)
2 +
(()) -000))
(by (28))
H
= 2(1 +
g(0 Σ
Tg
SE g
H
( is the unconstrained MLE, g(0) Exeeg (olts.)
E.1 Convex Relaxation
The optimization problem in (28) is a non-convex optimization problem and therefore it is not clear what the computational complexity of the problem. However, it is possible substitute this optimization problem with a convex one, whose computational complexity can be better tractable. The process similar the one detailed in [2, section 6]. Here we briefly outline the steps.
Let (0) E.= 2(0, r2) and Ó be defined follows:
i = arg min (0)
(29)
8E
Note that when the set θ is convex set, then the above optimization problem is convex by property of the log-likelihood function of GLMs. Hence it can be solved efficiently. With this projected 6, have the following guarantee:
Lemma E.2. Suppose (9(0)) 9(0*)
S y and X R/ If 0" e O and max:e (2;,
0r)l & R/R, R, then we have
| 0"
Scv(2+c)RRS)
H(O))
Proof. First we note that by self-concordance property of μr, for any E [4]
j (x 0-))
a(z,,0',0 0',0)
(Lemma C.2)
+ R (x Ø 8r)
11 (1 (1 07))
2
(max;e(4) (Z.,, Ø 0*) < R))
+ R(c/R)
j (1x.. 0*))
2+
Let us define G(0 = Etm a(za, 0*, O)xra.J. Using the above fact, we obtain G .)) >
H.
33

---

We now follow closely the proof outlined in Appendix B.3 of [2] with minor changes. By second-orde -oddr Taylor's expansion, for any 6 R we can write
- (100---,0))~~(0000000---------00 = 110 0" 0'(
2 2 + 10 0-' l
Taking absolute value on both sides, and substituting 0= 0,
0 0" 2
(2+ (L.((0) (,000) [((0))+ 07)1)
(A-inequality)
$ (2+c) c) (14((0)
[(0))+ --
8- (m1).))
[C,(0) - -((0))+ + |0100-- Σ
= (2+c)
rgT
0 - 0"
H
=E|(
H
Recall that 0 is the unconstrained MIEE, therefore (O) = above and some algebraic manipulations (see Appendix B.3 of [2]), we have, for 0"
0. By similar Taylor expansion as
-107--1,0) ~ |0(00) -
c( ())=
R
|1(00) -9(0) 1 H.-1 + +1|000) -0()))(0)) H--1
VX
R 72
VX +
(Lemma B.1)
2R
(recall v VR²X 7/RS)
We also have, by definition of 0, whenever 0" 0, (.) < L(")), therefore have L. (0) S (,0)) - (0) < 2 Thus, we have,
| 0 | (2+ c) (118S + 7 0 0- (1
Using the inequality that for some
x² < by +c = x bb++ Vc, we have,
g 0r (2 (2+c)++ + 1(2 + c)4R88
=cv c2
34

---

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

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All details stated in Section 2 and the proofs are given in details in the Appendices A, B, C.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Detailed discussion is done in Section 5 and Appendix D. Code can be accessed at attps://githun com/ jirjharr has-sasra/a///aaaaaaaaaaaa /aLa/ddBandttt.. hilmited_Adappttiie
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
36

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Full code with documentation is provided at https: com/ http:///Baaatttiiieeeeeeeeeeeeee
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. ca/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /Ct////ooeeeeeeeeeeeeeeeeee
/ /nips. wttpcccpppppcc.eeecccc.ccccctttt Stot:p/iiiiiuuteeeeeeeStttttaiii
onPolicy))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Execution Time plots have errorbars, but Regret plots not as regret plots were observed to get cluttered although the variation was not significant.
Guidelines:
The answer NA means that the paper does not include experiments.
37

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: https://neett httpa///////uueeeeeeeeeeeer cttpp//p.e..ppbbleecccccccciiiee
Answer: [Yes]
Justification: There are no potential harms caused by the research process as is mainly theoretical and the experiments all in simulation. There might be Societal Impact of the algorithms developed here when applied in practical decision -making settings. The study of this beyond the scope of current work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
38

---

Justification: The problem studied is of a theoretical interest and we do not foresee any negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The data and models only toy data/fully simulated and therefore of no real impact.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All credits regarding code are given in the README.md file at https: das Bttp////BanittLmmiiiiaii L Ltd //github. wwtp.//nnnaannnaanlaaaaaaaee
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
39

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcodeccooee.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: All details are provided in the README.md of our codebase https:// gi thub. www/oior//aareeee..eooeoooaaaeee haeeehharrdaaaaaa das/GLBandia Limi ted Adaptivity.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work is mainly theoretical with only simple simulated experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does involve human participants.
Guidelines:
40

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
41


Reviews:
[{"review_id": "wKIvdbuiUd", "reviewer": "Reviewer_wYhM", "summary": "This paper considered regret minimization for a generalized linear reward model with limited adaptivity, in which the set of arms $\\mathcal{X}t$ is stochastically generated by unknown distribution $\\mathcal{D}$, and after pulling $x_t \\in \\mathcal{X}_t$ the learner receives a reward $r_t$ sampled from the GLM distribution $P(r|x_t)$ with unknown $\\theta^*$.\nIn the first setting M1, the algorithm is given a budget $M$ and is asked to decide upfront $M$ rounds to update its policy. For M1, B-GlinCB is proposed, whose regret depends on $\\sqrt{\\hat{\\kappa}^{-1}}$ or $\\sqrt{{\\kappa^*}^{-1}}$.  In the second setting M2, the algorithm is given a budget $M$ and needs to decide $M$ rounds to update its policy adaptively. \nFor RS-GlinCB, the authors provided regret bound where $\\kappa$-dependence only appears in $\\log^2T$ term. Experimental results are demonstrated to validate their algorithms.", "questions": "Please see questions in Weaknesses.\n\n\nTypo/minor comments:\n\n$x^*$ is dependent on arm set $\\mathcal{X}$, so other notation may be clearer such as $x^*_t$ for $\\mathcal{X}_t$.\n\nSince the def. of $\\kappa$ in Alg 1 and Alg 2 is different, why not introduce different notations?\n\nHow the scaling parameter $\\beta(x)$ is defined in (2)? Is this same value defined later in (3)?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The first attempt to study GKM with limited adaptivity. The algorithm removes the instance^dependent non-linearity parameter $\\kappa$ which can be exponentially large concerning $|| \\theta^*||$.", "weaknesses": "1. To compute the length of the warm-up batch in M1, the knowledge of $\\kappa$ which depends on the optimal parameter $\\theta^*$ is required. Also, UCB/LCB scores and $\\beta(x)$ also need this knowledge. In M2 setting, Switching Criterion I depends on $\\kappa$. In practice, how can we estimate $\\kappa$ parameterized by unknown $\\theta^*$?\n\n\n2. The reviewer could not understand how significant the benefit of removing $\\kappa$dependence compared with other $\\sqrt{\\hat{\\kappa}^{-1}}$ or $\\sqrt{{\\kappa^*}^{-1}}$ is while allowing the policy to update at most $O(\\kappa \\log^2 T)$ times that is $\\kappa$-dependent. Only when $\\kappa =o(\\log T)$, the amount of adaptivity is reasonable, but now the regret bound does not need to care about $\\kappa$-dependence in such cases. Conversely, when $\\kappa$ is large, removing such dependence from the regret bound is important but now the algorithm requires a large amount of updates.  Could authors discuss the benefits/trade-offs of this point more?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. We address the comments and questions below:\n\n**Regarding Weakness 1**.  \n*(1a) Unknown $\\kappa$*.  \nIt is relevant to note that an upper bound on $\\kappa$ suffices for the mentioned use cases. $\\kappa$ is an instance-dependent parameter that captures the non-linearity and quantifies the hardness of the GLM instance. \nThere is no cyclic dependency here between estimating $\\theta^*$ and $\\kappa$. In particular, it is standard in bandit literature (specifically, linear and generalized linear bandits) to assume an upper bound on $\\theta^*$. Such an upper bound directly translates into an applicable upper bound for \\kappa; see discussion below.  \n\n*(1b) Dependence of $\\kappa$ on* $\\theta^*$.  \nWe note that the inclusion of  $\\theta^*$ in the definition of $\\kappa$,  $\\left( \\kappa = \\max_{x \\in \\cup_{t=1}^T  {\\cal X}t} \\frac{1}{\\dot{\\mu} ( \\langle x, \\theta^* \\rangle )}  \\right)$ is beneficial. Prior works, such as [1],[2] use the following definition $$\\kappa = \\max_{\\lVert \\theta \\rVert \\leq S } \\max_{x \\in \\cup_{t=1}^T  {\\cal X}t} \\frac{1}{\\dot{\\mu} (\\langle x, \\theta \\rangle)} $$ which also appears in their regret expression. Our definition is much tighter, leading to potentially smaller regret.\n\n\n**Regarding Weakness 2**.   \nHere, it is best to not conflate $\\kappa$ and $T$. $\\kappa$ is an instance dependent parameter, which is potentially large, but fixed for the instance. The number of rounds, $T$, on the other hand, is a growing quantity. \n\n\n\n**Regarding the definition of $\\beta(x) and minor comments**.  \nYes, the understanding is correct. We will move this definition next to the first expression in the final version.  \nThank you for pointing out the minor typos. We will fix these in the updated version of the paper.\n\n[1] Filippi, Sarah, et al. \"Parametric bandits: The generalized linear case.\" Advances in neural information processing systems 23 (2010).  \n[2] Faury, Louis, et al. \"Jointly efficient and optimal algorithms for logistic bandits.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.", "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": "7I1ibAZRIh", "reviewer": "Reviewer_bRFJ", "summary": "The authors consider the problem of regret minimization in bounded generalized linear contextual bandits with limited adaptivity. Specifically, they consider two models of limited adaptivity: **M1** in which the update rounds must be chosen before the algorithm is run, and **M2** in which the algorithm can be adaptive as the algorithm proceeds. For **M1** the authors propose B-GLinCB that obtains $\\tilde{O}(dRS\\sqrt{T/\\kappa^*})$, and for **M2**, RS-GLinCB that obtains $\\tilde{O}(d \\sqrt{T/\\kappa^*})$. The efficacy of RS-GLinCB is shown numerically.", "questions": "- The authors mention that the optimization problem in Eqn. (6) is nonconvex, and a convex relaxation results in additional factors of $\\mathrm{poly(R, S)}$. Do the factors appear in the leading term as well?\n- Are the analyses and algorithms amenable to unbounded, generalized linear models that are self-concordant? For instance, Gaussian is self-concordant with a multiplicative factor of $1$ but is unbounded.\n- For the algorithms, the authors use l2-penalized MLE, then project it to the S-ball if necessary. Why not just do l2-constrained MLE, as done in [6]?\n- The authors used an optimal design based on $\\lVert \\cdot \\rVert_{V_t}$, thus incurring explicit dependency on $\\kappa$. Is there any way to make the warmup more efficient by considering geometry-dependent norm, e.g., $\\lVert \\cdot \\rVert_{H_t}$ as in [5]?\n- The authors stated that the ellipsoidal projection is the main technical novelty for obtaining $\\mathrm{poly}(S)$-free regret for RS-GLinCB. Can this then be combined with prior UCB-based algorithms for logistic bandits (or GLM bandits) to obtain similar improvements? Or is it the case that such ellipsoidal projection *combined* with some other techniques for the limited adaptivity allows for $\\mathrm{poly}(S)$-free regret?\n- (minor) Can the intuitions and ideas from kappa-dependent warmup be used for best arm identification, e.g., [7]?\n\n\n\n[6] https://proceedings.mlr.press/v238/lee24c.html\n\n[7] https://proceedings.mlr.press/v139/jun21a.html\n\n(If all my concerns are sufficiently addressed, I'm leaning towards further raising the score)", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Clearly and well-written\n- First $d \\sqrt{T/\\kappa}$-type regret that holds for generalized linear bandits *beyond* logistic bandits + $\\mathrm{poly}(S)$-free leading term for generalized linear bandits\n- Numerous interesting (and important) technical contributions were made to the algorithm design and the regret analysis.", "weaknesses": "- The numerical experiments could benefit from more comparators, namely, randomized algorithms: Thompson sampling [1] (and its follow-up works, e.g., [2]) and recently proposed EVILL [3]. I know (and appreciate) that the authors' algorithms are primarily for the limited adaptivity scenarios. Still, given how one of the main contributions of this paper is state-of-the-art regret analysis, it would be important to have these (practically performing well) randomized algorithms as comparators.\n- (Continuing from the first point) In the prior regret analyses of logistic bandits by [4], they obtained $\\tilde{O}(d\\sqrt{T/\\kappa^*} + \\kappa \\wedge R_-(T))$, where $R_-(T)$ is some arm-geometry-adaptive term that can be much smaller than $\\kappa$. As the algorithm here makes use of warmup, it must incur the worst-case geometry-dependent term. The authors should also compare with this algorithm for the sake of regret comparison.\n- The algorithms involve an explicit warmup stage, which in practice may be not so good. This is shown in the logistic bandits experiments, where although RS-GLinUCB is good eventually, its warmup (that scales with $\\kappa$) forces the algorithm to incur high regret in the beginning (til round ~10000).\n- Some references on logistic bandits missing, namely [5] where in fixed arm-set setting, they proposed a Hessian-based optimal design (H-optimality), then a warmup-based algorithm was proposed that obtains $\\tilde{O}(d \\sqrt{T/\\kappa^*})$ regret, which is $\\mathrm{poly}(S)$-free.\n- Although the regret of RS-GLinCB is indeed $\\mathrm{poly}(S)$-free, it mainly relies on a nonconvex optimization (Eqn. (6)), and it seems that the tractable convex relaxation again introduces factors of $S$ (and $R$) to the leading term. (please correct me here if I'm wrong) -- This point should be made precise in the introduction.\n\n\n\n[1] https://proceedings.mlr.press/v108/kveton20a.html\n\n[2] https://arxiv.org/abs/2209.06983\n\n[3] https://proceedings.mlr.press/v238/janz24a.html\n\n[4] https://proceedings.mlr.press/v130/abeille21a.html\n\n[5] https://arxiv.org/abs/2202.02407", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed and insightful review. \n\n**Regarding Weakness 1**: *Numerical comparisons with DDRTS-GLB and EVILL*.   \nThis is a useful suggestion. We will implement the additional empirical comparisons mentioned in the review.  \nOn the theoretical front, it is, however, relevant to note that DDRTS-GLB is an O(T^2) computation algorithm with non-optimal regret ($\\kappa$-dependence). EVILL is not comparable because that work deals with fixed arm sets, not contextual arms.\n\n**Regarding Weakness 2**: *Regarding arm-geometry-adaptive term*.   \nOur analysis is not tuned to the arm-geometry dependent $R_-(X)$ term as found in [2] and [17]. This is primarily because our algorithms require a warm-up (implicitly in RS-GLinUCB and explicitly in B-GLinUCB), during which there is no control over the regret, even in the analysis. This conforms with existing literature, for example, [7], where the second-order term is not able to accommodate the arm-geometry dependent $R_-(X)$ term. As future work, it will be interesting to investigate algorithms that are efficient while being able to accommodate arm-geometry dependent regret for GL Bandits.  \nWe appreciate this point and will highlight it in the updated version.\n\n**Regarding Weakness 3**: *Warm-up in RS-GLinCB*.    \nThe warm-up in RS-GLinCB is implicit and arm-geometry adaptive. The rounds in which warm-up occurs (i.e., when Switching Criterion I is triggered) are deterministic, based on the sequence of contexts  $\\\\{ X_t \\\\}_{t \\geq 1}$. This leads to warm-up only in certain rounds based on the geometry of the contexts, which is very different from warm-up in [7], where warm-up is decided based on the stochasticity of rewards as well. Therefore, in our experiments, we observe that after a few initial rounds, the regret is nearly constant, while other algorithms display a growing nature. For the logistic case, among the efficient algorithms available, RS-GLinUCB’s superiority is clearly established.\n\n**Regarding Weakness 4**: *Prior works*.   \nThank you for pointing out the relevant work of Mason et al. 2018. We will include it in our final version.\n\n**Regarding Weakness 5 and Question 1**: *Convex relaxation and dependence on S*.    \nThe reviewer is right that a convex relaxation leads to poly(S)-dependence in the first-order regret term. It would be interesting to design algorithms that require only convex optimizations but are still poly(S)-free. Thank you for the suggestion regarding non-convex optimization for poly(S)-free regret. We will clarify this in the introduction of our final version.\n\n**Regarding Question 2**: *Unbounded self-concordant GLMs*.   \nIndeed, it does seem that our analysis extends to unbounded, self-concordant GLMs as well. However, we expect to incur additional log factors ($\\log{T}$) in the regret. Taking Gaussian rewards as an example, the confidence interval would remain unchanged. We use the upper bound on the reward ($R$) in several places during the analysis (eg., in Lemma A.5) or in the algorithm (while defining $\\beta(x)$) – similar arguments can be made for Gaussian rewards as well. The analysis for Gaussian rewards follows from the fact that Gaussian random variables remain bounded with high probability, allowing for extensions of our analysis. \nWhile such extensions are interesting, the current work focuses on the GLM model proposed in [8] and addresses the challenges in the limited adaptivity setting.\n\n\n**Regarding Question 3**: *Regarding l2-penalized MLE*.  \nWe have intentionally separated the convex optimization part and the (non-convex) projection step. This separation ensures that certain properties can be obtained before and after the projection; see, e.g., equation (26), which would not hold if we included the projection into the considered convex optimization problem. Moreover, it is not clear how the non-convex optimization projection can be included as a constraint in the log-loss optimization, while ensuring that the desired properties hold. Appendix E provides additional details in this direction. \n\n**Regarding Question 4**: *Geometry-dependent norm for warm-up*.  \nWe thank the reviewer for this helpful suggestion. We will include this in the updated version of the paper. Indeed, while the worst-case regret guarantee remains unchanged, we can use the geometry-dependent norm during warmup. Also, the algorithms analysis remains essentially the same.  \n\n\n**Regarding Question 5**: *Ellipsoidal projection*.  \nThe reason why restricting optimization (6) to the ellipsoid around $\\theta_o$ leads to tighter regret is because for the Non-”Switching Criterion I” rounds, it is guaranteed that $\\lVert x \\rVert_{V^{-1}}  \\leq O(1/\\sqrt{\\kappa})$. Hence $\\langle x, \\theta^* - \\theta_o \\rangle \\leq ||x||_{V^{-1}} || \\theta^* - \\theta_o ||_V \\leq O(1/\\sqrt{\\kappa}) \\gamma \\sqrt{\\kappa}$. Therefore, the main idea is in the design of the Switching Criterion I and not just in the ellipsoidal projection. Whether one can combine this Switching Criterion with existing algorithms and obtain better guarantees is an interesting direction worth exploring.\n\n**Regarding Question 6**: *Best arm identification*.  \nThis is an interesting question that complements the paper’s goals. It is, however, worth noting that the current warm-up conditions are designed to address changing contexts. Applying them to static arm sets may be suboptimal. For static arm sets, one can simply allocate initial rounds for warmup, as in [7]. The switching criteria-based warmup is needed in the current work because we are dealing with adversarial contexts. Overall, it remains unclear as to what one would gain by using the criteria for static arm sets.\n\nNote: All reference numbers are same as in the submitted paper.", "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": "2b6KR2vuCM", "reviewer": "Reviewer_5bc4", "summary": "This paper addresses the generalized linear contextual bandit problem under limited adaptivity constraints. In a setting (M1) where the times for updating the agent's policy are predetermined, the first proposed algorithm B-GLinCB divides the entire timeline into batches, updating the policy at the end of each batch. B-GLinCB explores using a G-optimal design policy in the first batch and adjusts the arm set in subsequent batches based on estimated MLE parameters using samples obtained in the first batch. The algorithm guarantees a $\\tilde{O}(\\sqrt{T})$ regret when the number of policy updates is $\\Omega(\\log \\log T)$, independent of the problem-dependent instance $\\kappa$. In a setting (M2) where the agent can adaptively decide when to update the policy, the RS-GLinCB algorithm is proposed. RS-GLinCB uses two criteria to alter action selection: the first criterion allows a tighter estimation of the true parameter's derivative, and the second criterion achieves a $\\kappa$-independent regret bound. The theoretical results of the proposed algorithms were supported through comparisons with baseline algorithms in logistic bandit settings.", "questions": "1. In logistic bandits[2, 6, 7], algorithms achieve $\\kappa$-independent regret bounds by leveraging the self-concordance property of log-loss. What specific challenges were encountered when extending this to GLMs?\n\n2. In the experiments, it appears that ECOLog in [7] is a sub-algorithm for reward parameter estimation. If the comparison is with OFU-ECOLog, which also has a computational complexity of $O(\\log t)$, what might explain the significant difference in execution times between OFU-ECOLog and RS-GLinCB? \n3. Additionally, how does the execution time difference vary with increasing context dimensions?\n4. Why were different values for the upper bound of the reward parameter S used in experiments (S=3 for logistic and S=5 for probit)?\n\n- [Minor typos]\n    - The $\\kappa$ in line 137 and the $\\kappa$ in line 144 seem to refer to different concepts; should different symbols be used?\n    - Line 156: G-optimal design policy $\\pi_G = \\arg \\min_\\lambda \\min_x \\| x \\|^2_{U(\\lambda)^{-1}}$\n    - Algorithm 2, line 14: $\\hat{\\theta}_w\\) → \\(\\hat{\\theta}_o$\n    - Constraint in Eq. (6): $|| \\theta - \\hat{\\theta}_w ||_V \\le \\gamma \\sqrt{\\kappa}$ → $|| \\theta - \\hat{\\theta}_o ||_V \\le \\gamma \\sqrt{\\kappa}$", "limitations": "The authors have well-addressed the limitations and further research directions in Section 6.\n\nThe content discussed in this paper appears to have little to no negative societal impact.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The limited adaptivity constraint discussed in the proposed paper is crucial for many real-world decision-making problems. The authors extend results from linear reward models to non-linear reward models, with the proposed algorithms guaranteeing $\\tilde{O}(\\sqrt{T})$ regret under specific conditions.\n- Notably, the leading term of the regret bound for the proposed algorithms is independent of problem-dependent instances. This is, to my knowledge, the first result showing kappa-independent regret bounds for GLM reward models, excluding logistic bandits.\n- The proposed algorithms are computationally efficient since the number of samples used to estimate the reward parameter does not increase over time.", "weaknesses": "- Although the proposed algorithm achieves a $\\kappa$-independent regret bound, it requires prior knowledge of $\\kappa$. The MNL contextual bandit (Perivier & Goyal, 2022) achieved a $\\kappa$-independent regret bound without needing information about $\\kappa$, which might be useful here.\n- The proposed algorithm is computationally efficient concerning time $t$, but there is no explanation of its dependency on the dimension $d$. It lacks details on the computational complexity needed for calculating the optimal design and distributional optimal design at each time step.\n\n* * *\nPerivier & Goyal. \"Dynamic pricing and assortment under a contextual MNL demand.\" Advances in Neural Information Processing Systems 35 (2022): 3461-3474.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. We address the comments and questions below:\n\n\n**Regarding Weakness 1**: *Prior knowledge of $\\kappa$*.  \nWe note that [7], in fact, assumes the knowledge of an upper bound on $\\kappa$ in Procedure 1 for the non-contextual problem and while calculating $\\textbf{V}^\\mathcal{H}_s$ matrix for the contextual setting. We work under the constraint of limited adaptivity, and our algorithms use the value of $\\kappa$ during the warmup round of B-GLinCB and for the first switching criteria in RS-GLinCB. We believe a $\\kappa$-dependent warmup round is especially necessary for the batch algorithm.  \nAs mentioned in response (1a) for Review wYhM, access to an upper bound on $\\kappa$ suffices. In particular, as is standard in bandit literature (specifically, linear and generalized linear bandits), one can assume access to an upper bound on $\\theta*$. Such an upper bound directly translates into the required upper bound for $\\kappa$.  \n\nWe thank the reviewer for pointing us to the relevant work of Periviar & Goyal, which we will include in the final version of the paper.\n\n\n**Regarding Weakness 2**: *Dependence on context dimension $d$ in computational complexity*.   \nA detailed discussion on computational complexity is provided in Appendix D (lines 675-692).   \nOur results hold for GLMs, in general. Here, for any class of reward functions (e.g., logistic rewards) for which the specified convex optimization problem can be solved efficiently, we obtain a polynomial dependence on $d$. \n\n\n\n**Regarding Question 1**.  \nOur novel instantiation with respect to self concordance is detailed in Remark 1.3 (Lines 93-98).  \nOur overarching contribution is the development of GLM bandit algorithms with a key focus on limited adaptivity. This required new algorithmic techniques (e.g., the $\\kappa$ dependent exploration phase). To complement the algorithms’ design, the analysis required new ways to adapt the self-concordance property of the reward distribution (e.g. Lemma A.5, A.7). Further,  new technical ideas were required both on the technical (e.g., Lemmas A.16 A.17) and analytic fronts.  \n\n**Regarding Question 2**: *\"In the experiments, it appears that ECOLog in [7] is a sub-algorithm for reward parameter estimation\"*.  \nWe have discussed the superior empirical performance of RS-GLinCB in detail in Appendix D (lines 693-715).  \nThere seems to be a factual oversight here: we do not use ECOLog as a sub-algorithm. In fact, ECOLog and our algorithms solve notably different optimization problems for estimating $\\theta^*$.\n\nIn particular, ECOLog [7] estimates $\\theta^*$ by optimizing a second order approximation of the true log-loss while we optimize the true log-loss; however, we do it less frequently.  That is, RG-GLinCB solves a ‘larger’ convex optimization problem but less frequently. This results in a smaller overhead at the implementation level. By contrast, ECOLog solves a smaller optimization problem but does so every round. Moreover, ECOLog solves additional optimization problems every round for the adaptive warmup criteria (for estimating parameter ${\\theta}_t^0$, ${\\theta}_t^1$ and $\\bar{\\theta}_t$ in Algorithm 2). We, on the other hand, have a simpler warmup criteria (see Switching Criteria 1) that only relies on the arm geometry and does not require solving an optimization problem.\n\n**Regarding Question 3**.\nSpace permitting, we will extend the experiments to highlight the dependence of the execution times on $d$. \n\n**Regarding Question 4**: *Different values of $S$ for logistic and probit rewards*.  \nWe observe that the empirical performance of RS-GLinCB is consistently better in terms of both regret and computational performance compared to the previous best logistic and other GLM bandit algorithms. The choice of exact parameter value $S, \\kappa$ etc., is arbitrary. We will include a comparison with different values of $S$ in the updated version. \n\n\nWe thank the reviewer for pointing out the minor typos and will fix them.", "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:

Meta-review: The paper proposes novel algorithms for the contextual bandit problem with bounded glm rewards when the number of updates is limited. An algorithm which determines in advance the rounds at which the policy will be updated is proposed for the case where the contexts follow a stochastic distribution. Another algorithm which determines the udpate rounds in an adaptive manner is proposed for the case where the contexts can possibly be adversarial. Both algorithms are proven to achieve $\tilde{O}(\sqrt{T})$ regret with only $\Omega(loglogT)$ and $\tilde{O}(log^2T)$ updates respectively under the respective settings. As an additional contribution to the glm bandit literature, the authors manage to remove the $\kappa$ dependency in the regret bound, where $\kappa$ is an model dependent parameter that captures non-linearity of the reward model. This is achieved by a novel design component of the algorithm; utilizing a design matrix appropriately scaled via $\kappa$. 

The paper has numerous contributions to the glm bandit literature (achieving kappa independent regret for glms beyond logistic models, removing polynomial dependency on the norm of the parameter), and the proposed algorithms are of great practical use as they achieve tight regret bounds with limited number of udpate rounds. 

One weakness pointed out by multiple reviewers was that the knowledge of kappa is necessary to run the algorithm. Authors adequately addressed this point in their rebuttal by explaining that the upper bound of kappa is sufficient, and that the assumption that this upper bound is known is a standard assumption in the glm bandit literature.

Authors are stronlgy encouraged to incorporated suggestions of the reviewers in their final version of the paper

- They should add some baselines proposed by Reviewer bRFJ in their experiments
- Some missing reference on logistic bandits should be added 
- It should be stated that the poly(S)-independence relies on solving a nonconvex optimization problem
Decision: Accept (spotlight)