A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits
Authors: Junghyun Lee
Se-Young Yun
Kwang-Sung Jun
Venue: NeurIPS 2024 poster (2024)
Keywords: generalized linear model
bandit
UCB
anytime-valid
time-uniform
confidence sequence
PAC-Bayes
Primary area: bandits

Abstract: We present a unified likelihood ratio-based confidence sequence (CS) for *any* (self-concordant) generalized linear model (GLM) that is guaranteed to be convex and numerically tight. We show that this is on par or improves upon known CSs for various GLMs, including Gaussian, Bernoulli, and Poisson. In particular, for the first time, our CS for Bernoulli has a $\mathrm{poly}(S)$-free radius where $S$ is the norm of the unknown parameter. Our first technical novelty is its derivation, which utilizes a time-uniform PAC-Bayesian bound with a uniform prior/posterior, despite the latter being a rather unpopular choice for deriving CSs. As a direct application of our new CS, we propose a simple and natural optimistic algorithm called **OFUGLB**, applicable to *any* generalized linear bandits (**GLB**; Filippi et al. (2010)). Our analysis shows that the celebrated optimistic approach simultaneously attains state-of-the-art regrets for various self-concordant (not necessarily bounded) **GLB**s, and even $\mathrm{poly}(S)$-free for bounded **GLB**s, including logistic bandits. The regret analysis, our second technical novelty, follows from combining our new CS with a new proof technique that completely avoids the previously widely used self-concordant control lemma (Faury et al., 2020, Lemma 9). Numerically, **OFUGLB** outperforms or is at par with prior algorithms for logistic bandits.

A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits
Jungyhun Lee, Se-Young Yun
Kwang-Sung Jun Department of Computer Science
Kim Jaechul Graduate School of Al
KAIST
University of Arizona Tucson, AZ, USA kjundcs arizona. edu
Seoul, Republic of Korea
{jh_lee00, yunseyoung> wwaisnggkkkattt... ac.
Abstract
We present unified likelihood ratio-based confidence sequence (CS) for any (self- concordant) generalized linear model (GLM) that is guaranteed to be convex and numerically tight. We show that this is on par improves upon known CSs for various GLMs, including Gaussian, Bernoulli, and Poisson. In particular, for the first time, our CS for Bernoulli has a poly(S)-ffte the unknown parameter. Our first technical novelty is its derivation, which utilizes time-uniform PAC-Bayesian bound with a uniform prior/posterior. despite the latter being rather unpopular choice for deriving CSs. As direct application of our new CS, we propose a simple and natural optimistic algorithm called OFUGLB, applicable to any generalized linear bandits (GLB; Filippi et al. (2010)). Our analysis shows that the celebrated optimistic approach simultaneously attains state- of-the-art regrets for various self-concordant (not necessarily bounded) GLBs, and even poly(S)-free for bounded GLBs, including logistic bandits. The regret analysis, our second technical novelty, follows from combining our new CS with a new proof technique that completely avoids the previously widely used self- concordant control lemma (Faury et al., 2020, Lemma 9). Numerically, OFUGLB outperforms or is at par with prior algorithms for logistic bandits.
radius where S is the norm of
Introduction
One paramount task in statistics and machine learning estimate the uncertainty of the underlying model from (possibly noisy) observations. For example, in interactive machine learning scenarios such as bandits (Lattimore and Szepesvári, 2020; Robbins, 1952; Thompson, 1933) and recently reinforcement learning with human feedback (RLHF: Christiano et al. (2017); Ouyang et al. (2022)), at each time step 1, the learner chooses an action æ; from an available set of actions X, and observes reward outcome Tt that is modeled as distribution whose mean is unknown function f of æ;; ie., Tt ~ p(- p(-|æ;; f)). One popular choice such a model is the generalized linear model (GLM; McCullagh and Nelder (1989)) that extends exponential family distributions have linear structure in its natural parameter as (xx, 0_), where 0, is an unknown parameter. other words, the mean function is f=) (((x: 0.)) for some inverse link function μ. This encompasses wide range of distributions, which in turn makes it ubiquitous in various real- worl-world applications, such as news recommendations (Bernoulli; Li et al. (2010, 2012)), social network influence maximization (Poisson; Gisselbrecht et al. (2015); Lage et al. (2013)), and more. In such tasks, the learner must estimate the uncertainty about 0, at each time step t 2 1, given observations { ((x., t=) to make wise decisions. One popular and useful way capture the uncertainty via a time-uniform confidence sequence (CS) (6) which takes the form of P[3t 2 1: 0, & (,) S 8. Recently, CS has been described one of the key components for safe anytime-valid inference (SAVI) that can ensure the validity/safeness of sequentially adaptive statistical inference (Ramdas et al., 2023).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Existing CSs for GLMs, however, are far from ideal. Much of the prior works focus on obtaining CS for specific instantiations of GLMs, such as Gaussian (Abbasi-
al., 2011; Flymn et al.. 2023) and Bernoulli (Abeille et al., 2021; Faury et al., 2020, 2022; Lee et al., 2024). Especially for Bernoulli, all the existing CSs suffer from poly(5) factor in the radius, where is the norm of the unknown parameter 0.. Emmenegger et al. (2023); Jun et al. (2017); Li et al. (2017) proposed generic CSs that work for any convex GLMs, but their radii all suffer from a globally worst-case curvature of μ. which is detrimental in many cases (e.g., for Bernoulli, it scales as e²).
Contributions. First, we propose a unified construction of likelihood ratio-based CS for any convex GLMs (Theorem 3.1) and then instantiate it as an ellipsoidal CS for self-concordant GL.,s including Bernoulli, Gaussian, and Poisson distributions (Theorem 3.2). Notably, we keep track of all the constants so that any practitioner can directly implement it without trouble. The proof uses ingredients from time-uniform PAC-Bayesian bounds (Chugg et al., 2023) martingale Donsker- Varadhan representation of KL + Ville's inequality. The main technical novelty lies in using uniform prior/posterior for the analysis, inspired by various literature portfolios (Blum and Kalai, 1999) and fast rates in statistical/online learning (Foster et al., 2018; Grünwald and Mehta, 2020; Hazan et al., 2007; van Erven et al., 2015).
Secondly, we apply our novel CSs to contextual generalized linear bandits (GLB; Filippi et al. (2010) with changing (and adversarial) arm-sets, and propose new algorithm called Optimism in the Face of Uncertainty for Generalized Linear Bandits (OFUGLB). OFUGLB employs the simple and standard optimistic approach, choosing an arm that maximizes the upper confidence bound (UCB) computed by our CS (Abbasi-Yadie) et al., 2011; I; Auer, 2002). We show that OFUGLB achieves the state-of-the-an regret bounds for self-concordant (possibly unbounded) GLB (Theorem 4.1.. This is the first time a computationally tractable, purely optimistic strategy attains such poly(S)-frre) -fre regret for logistic bandits in that OFUGLB does not involve explicit warmup phase and only involves convex optimization subroutines. Our other significant main technical contribution is the analysis of OFUGLB, naïvely applying existing analysis techniques for optimistic algorithms (Abeille et al., 2021; Lee et al., 2024) yields a regret bound whose leading term scales with poly(S). We identify the key reason for such additional dependency as the use of seff-concordance control lemma (Faury et al., 2020, Lemma 9), and provide an alternate analysis that completely bypasses it, which may be of independent interest in the bandits community and beyond.
2 Problem Setting
We consider the realizable (online) regression with the generalized linear model (GLM; McCullagh and Nelder (1989)) whose conditional probability measure of r is given
rxx 0.) m((x, 0.)) + h(r, dv, g(T)
dp(r x; 0.) = exp
(1)
where 7 is the dispersion parameter, and y is some known base measure (e.g., Lebesgue, counting). We assume the following:
Assumption 1. 0, E E C (B) = (0 E Te 101|2 S S} for some known S >> 0. Also, θ is nonempty, compact, and convex with intrinsic dimension' d.
Assumption 2. The domain X for arm (context) x satisfies X C (1). Assumption 3. m is three times differentiable and convex, i.e., m" exists and ja m" 2 0.
In the generalized linear bandit (GLB) problem, at each time E [T]. the learner observes a time-varying, arbitrary (adversarial) arm-set X, C X, chooses a C, E X, and receives a reward re ~ p( [ar,, 0.). Let Xpr == - and Σx+1 == oEE, Te. T.+1) with En = a (ax) be the filtration in the canonical bandit model (Lattimore and Szepesvári, 2020, Chapter 4.6). From well- known properties of GLMs (McCullagh and Nelder, 1989), we have that E[r:|E.] = m'((x,, 0.)) e u((x,, 0.)) and Var[r: = g()) (ax, 0.)). where μ is the inverse link function. We also define the following quantity describing the maximum slope of μ: R2 == max ( 0ee ju( 0)).
Note that many common distributions, such as Gaussian (1x(2)=
R2 = 1), Poisson (1(2)= = 6², R2 = )²), and Bernoulli (u(=)= = (1 ++ - R2 = 1/4), fall under the umbrella of GLM.
the algebrai dimension (minimum number of basis vectors spanning it) of the affine span of θ in Rd.

---

Unified Likelihood Ratio-based Confidence Sequence for GLMs
The learner's goal is output time-uniform confidence sequence (CS) for 0., P 0. & [r) < 6, where I is w.r.t. the randomness of the confidence sets (,)). In this work, we are particularly interested in the log ligeliielihood based confidence set "centered" the norm-constrained, batch maximum likelihood estimator (MLE):
C( = { o: ( (.) S B(())
where B()))² is the "radius" of the CS that we will define later, L,(0) is the negative log- ooglliieidood of 0 w.r.t. data collected up to - 1, and 0, the corresponding MLE:
C,(0):= : Σ (0) a Ts (2., 0) m( (xx 01)
0, == arg min ()).
(3)
g(T)
oge
Note that 7();;T) is omitted it plays no role in the confidence set nor the MLE.
The form of the confidence set the same as Lee et (2024) and convex relaxation of Abeille et al. (2021), all of which utilizes a single, cumulative & constrained MLE 0: E 2 to compute the loss at time t. Other approaches include using a single regularized MLE 0, that may lie outside of ④ YAbkori-Yadkori et al., 2011), using sequence of MLEs {0+) to compute the loss at time (Abbasi- Yadkori et al., 2012; Emmenegger et al., 2023; Faury et al., 2022; Jun et al., 2017: Wasserman al., 2020), and computing the expected loss over some distribution (e.g., Gaussian) without committing to point estimators (Flynn et al., 2023). As one can see later, our derivation the CS resembles the last approach: also start from expectation of loss over prior distribution of without committing to estimator. Yet, we introduce single estimator O, avoid the computational difficulty of evaluating the expectation.
Our first main contribution is the following unified confidence sequence for any GLMs, regardless of whether is bounded or not, as long as the corresponding log- liglleillooodd loss Lipschitz:
Theorem 3.1 (Unified CS for GLMs). Let L, be the Lipschitz constant" of Lel-) that may depend on {()2, )=) Then, we have P 2 1 0. Cc(o)] 6, where
1 + inf 8
1 dlog +2SLia } s log dlog (ev 205L,
1
3() log
cE(0..1
Ct
where the last inequality follows from the choice at EST.
"If L, is differentiable, could apply the Rademacher's theorem (Federer. 1996, Theorem 3.1.6): L = inf [. 2 0: (0) (o)) S L 0 0'11,. V0.0' E )) maxøee [0)l2))
Remark 1 (Generality of our Unfied CS). The above holds for any distribution any Polish space, although (ō) is convex if and only if Le is convex. For GLMM, convexity guaranteed.
Practically, the computation of L involves a potentially non-concave maximization over a convex set, which is NP-hard in general (Murty and Kabadi, 1987). In Table 1, provide closed-form (up to absolute constants), high-probbbiiltyy upper bounds for I 's for various GLMss Note that for the leamnrr implement the CS, she also needs to know S, or its upper bound.
Comparisons to Prior Works. Lai (1976) derived the first generic CS for the exponential family based on a generalized likelihood ratio, but is only applicable for θ C R and is hard to instantiate. Recently, several works have provided CSs for either generic GLMs (Emmenegger et al., 2023; Jun et al., 2017; Li et al., 2017) or specific GLMs (linear: Abbasi-Yadkori et al. (201 1); Flynn et al. (2023), logistic: Abeille et al. (2021): Faury al. (2020); Lee et al. (2024)). The generic CSs are generally not tight as the "radius" often scales with k == max X,eee (x, 0))) which scales exponentially in S for Bernoulli (Faury et al., 2020). For instance, Theorem of Jun et al. (2017) and Theorem of Li et al. (2017) propose ellipsoidal CSs that provably satisfy |00 12, & (1, with Ç1 always scaling with k. Emmenegger et al. (2023) proposed weighted sequential likelihood

---

Table 1: Instantiations of Ls for various GLMs. "Bounded by M means for any a E X and
1' ~ p( æ 0.), the following holds almost surely: r - -m((ar 0+))l S M oo.
GLM Bounded by M Bernoulli
Upper bounds for Le
Proof
(M 2,R 1)/9(T)
Appendix C.I
(1 + (/2)
M = 1, R2 = 1/4
o-subGaussian"
o 2 St + σ |loog %z
Appendix C.2
Poisson"
e
Appendix C.3
The omitted absolute constants can he found in the respective proofs.
besting-based CS W, and showed its efficacy empirically. Theoretically, they showed that 0 E W satisfies D 0.) < (21,,) for some Bregman divergence -):-)) and (2 always scaling with as well. We believe their relaxation is not tight enough to warrant a fair comparison and leave to future work theoretically comparing our CS to theirs. Chowdhury al. (2023) proposed Bregman divergence- CSs for generic exponential families, which are quite closely related to our CS; see Appendix A for further discussions. On the other hand, the CSs for specific GLMs are inapplicable to GLM models beyond what they are designed for and may not even be sufficiently tight. The prior state-of-the (likelihood ratio-based) CS radius for Bernoulli is O (og)(1)65) + d (og((t/d)) of Lee et al. (2024), while our theorem gives us O (log(1/8) + d dolog( (StgtS///o/ (St/d)). Note that we completely remove the (ey((S)ddeeeddngg from the radius, resolving an open problem posited by Lee et al. (2024). Later in Section 4, we show this is significant, both theoretically and numerically.
3.1 Ellipsoidal Confidence Sequence for Self-Concordant GLMS
We now provide an ellipsoidal relaxation of Theorem 3.1 for the following class of GLMs: Assumption 4 (Russac et al. (2021)). GLM (generalized) self-concordant, ie., the following quantity is well-defined (finite): Rg == inf R 2 0 (ū 0)) S Rj((z, 0)), Vx E X, E 6}.
For instance, Bernoulli satisfies this with R, this assumption with R. = R (Sawarni et al., 2024, Lemma 2.1). Many unbounded GLMS also satisfy this assumption, such as Gaussian (R, 0). Poisson (R, 1), and Exponential (R2 = 0).
and more generally, GLM bounded by R a.s. satisfy
For such self-concordant GLMs, we have the following slightly relaxed ellipsoidal CS, whose proof is deferred to Appendix D:
Theorem 3.2 (Ellipsoidal CS for Self-Concordant GLMs). With the same notations as Theorem 3.1, we have that for any À 2 0, P| 2 1 : 0, & &g < 6, where
A( = O R 0 0
V.C, S (6()) A 2(1 - S
Let us denote A S Af < cB for some absolute constant c > 0. Note that the relaxation is order-wise strict only when R. > 0. For instance, for Gaussian where R. = 0. the ellipsoidal relaxation does not introduce additional S-dependency when we choose
O (}²)) We then have that V (0.) = - x. =: J V,, and I,, S St. with high probability (Proposition C. Combining everything, we have ||e 0 1... S o² (log(t/5) + d dloo(St/d)) which completely matches the prior state-of-the-art radius as in Lemma D.10 of Flynn et al. (2023) with = o²5²
In bandits, the ellipsoidal CS allows one to equivalently rewrite the optimistic optimization in the UCB algorithm (Auer et al., 2002) as a closed form bonus-based optimization over the arm-set Xy:
arg max xEX.
(z, 0)
arg max (z. 0.) + vx(6) x (V=C.(6))
(4)
me.X.
i.., there is no need to solve a convex optimization for each arm. In the high-dimensional scenario where / = o(d), one can compute LV*L, (0.) + >1 with time complexity of O(ld2) per round via the Sherman-Morrison formula (Sherman and Morrison, 1950), which more efficient than the naive matrix inversion that takes (dd)) time complexity.

---

3.2 Proof of Theorem 3.1 PAC-Bayes Approach with Uniform Prior
We consider (0) = exp (C,().) - the likelihood ratio between the (estimated) distribu- tion corresponding to 0 and the true distribution corresponding to 0.. This has been the subject of study for over 50 years (Darling and Robbins, 1967a,;; Lai, 1976; Robbins and Siegmund, 1972) and recently revisited by statistics and machine learning communities (Emmenegger et al., 2023; Flynn et al., 2023; Ramdas et al., 2023; Wasserman al., 2020).
We follow the usual recipes for deriving time-uniform PAC-Bayesian bound (Alquier, 2024; Chugg al., 2023). We start with the following time-uniform property:
Lemma 3.1. Let 8 E (0, 1). For any data-independent probability measure Q on Q we have:
3t 2 1: (211:ooc(M((0))
(5)
where IP is over the randomness of the data (and thus randomness of Le 's).
Proof. First, is easy see that M. II
dp(r_lan,0)) dp(r.lae;0..)
nonnegative martingale w.r.t. E,
dp(ra/ae;; 0)
dp(r|ær; 0) dp(r|ar; 0.)
B[M,(0)EE:-]] = M, (O)E
dp(r: mz; 0+) Ex-1 [e-1 M2-1(0)
dp(rlaas 0.).
Now consider the random variable (M)), which is adapted to E,. This is martingale, as [ (+) Eo-elE[M,, = (e-q(MM)1(0)
where (+) follows from Tonelli's theorem. We conclude by Ville's inequality (Ville, 1939).
We recall the variational representation of the KI. divergence:
Lemma 3.2 (Theorem 2.1 of Donsker and Varadhan (1983)). For two probability measures P., Q over O we have the following: DKL. (PI S Ee-r(g(0)] log Ea-2(e9101)
We then have the following:
Lemma 3.3. For any data-independent prior Q and any sequence of adapted posterior distributions (possibly learned from the data) {IP,), the following holds; for any ō (0,1).
1 3 (. - Eg-r, [C)( log 5 + (PPII2) - 6.
P
Proof. Note that
log Ee Ee L.. log Ea~elexp (-), ( Eo-p,1-C((0)) DKI.
where (*) follows from Lemma 3.2 with g(-) = -.,()) By Lemma 3.1, we have that - 5. Rearranging gives the desired statement.
P (3t 2 1: log < log
Remark (Choice of KL). One can replace KL with other divergences with similar variational formulations (Ohnishi and Honorio, 2021). As we will show later, KL suffices for our purpose.
Up to now, it is well- knoln the PAC-Bayes literature. Our main technical novelty lies in how to choose Q and F., which is follows: for & (0, 1] to be determined later, set
Un) IP Üni A c. c,)0, +g0))
(7)
where Unif(.) is the uniform distribution and + O (a + 0 0 Q) for vector E Rd.
Then, denoting vol(-) as the (Lebesgue) volume in gdd we have vol(@)
e v vol (11 0, + G
vol(@) -log vol(O) vol(ct
DRL. (PrxI()) log
log
log
dllog
vvvo((
Ct
5

---

Algorithm 1: OFUGLB
for f 1, ....... do
2 Compute the norm-constrn norm-constrained MLE: 0g k arg ma ()))); Update the confidence set C, specified in Theorem 3.1; (xt 0);
4 UCB step: (2t,, 0,) < arg
Pull the arm 2 and receive a reward rt;
We also have that
Eg [c, (.( Eg (
C.( (0((00))250 2S
where follows from the Lipschitzness of L.(-) and the fact that for 0 = (1 -c)0; + c,0 E G.
c2 0 0.11 < 2Scr. We conclude by minimizing over E (0, 1].
0 0:
3.3 Intuitions Behind the Proof of Theorem 3.1
Constrained MLE and Uniform Prior/Poster. As we consider constrained MLE, we know that 0, O, i.e., our "belief" our MLE is precisely the prior Q Uni Then, we want the true parameter 0, to close to dr, we want to show that a sufficiently large "posterior volume" is near 0,, formalized F = Unif (1 ce 0. + a for some time-dependent shrinkage factor ot (0, 1]. We later appropriately choose to optimize the PAC-Bayesian bound.
We remark that the uniform prior/posterior has been previously considered in universal portfo- lios (Blum and Kalai, 1999, Theorem 1) and fast rates in online learning (Foster et al., 2018; Hazan al., 2007); see Appendix A for discussions on relations fast rates literature. To our knowledge, we are the first to use such uniform prior/posterior in the (tiee-unifrm)) PAC-Bayes context.
Remark (Use of Regularized MLE?). When one uses regularized MLE instead of constrained, as it is not guaranteed to be in θ, one cannot directly the same uniform prior/posterion. One approach may be to appropriately project the regularized MLE onto θ (e.g.. Eqn. (9) of Faury et al. (2020)). However, the previously considered projections that goattggane guarantee the tightness of the resulting CS involve a nonconvex optimization and are, thus, computationally intractable. One could also consider using high regularization, which may result in additional dependencies on S in the final CS radius. We conjecture that similarly tight guarantees can be recovered with regularized MLE if one uses other uppropriate prior/posterior whose supports are the entire Rd (e.g., Gaussian).
Relations to Theorem 3 of Foster et al. (2018). Let us first briefly recall its proof. The authors first consider a distribution Pt(-) over the parameter W W (see their Algorithm 1) and use q-mixability of the logistic loss to obtain an inequality involving the negative-log-ing integral term OW* (1 O)W C W, where W* is the ground-truth optimal parameter and [0, 1) is to be determined later. The proof concludes by chaining Sw 2 Ss with the foo -iiscchhhssss of the logistic loss and expanding the integral.
Sw exp (-1) 1) E, ((Wa,, 3t)) dW. They define
Our proof is inspired by the above, with some key differences. While the paattive-loginnteeee also arises in our scenario, we adopt a more compact, streamlined PAC- PAC-Bayes approach. In our case, a similar quantity Eę~q (exp(_L.(0)) arises from Donsker- Varadhan representation (Lemma 3.2). We then apply Ville's inequality to obtain the time-uniform PAC-Bayes bound (Lemma 3.1) 1),, and our choices of prior/posterior resemble their choice of S. Our Lipschitzness argument the end also resembles their loc -ischhitzesss argument.
4 OFUGLB: A Generic UCB Algorithm for Self-Concordant GLBs
As direct application of our CS, we consider self-concordant GLB (Filippi al., 2010; Janz et al.. 2024), where at each time t, the learner chooses æ, E X, dependent on the history {(x,, [ and receives rt ~ p(, 0.). The learner's goal is to minimize the (pseudo-)rese bregret, Reg(?) := Σx (M((x).., 0.)) p( 0.))} where Tt,, == arg ma p((x, 0.)).

---

Inspired by the optimism principle (Abbasi-Yadkori Yadkori et al., 2011; Auer, 2002), based on our new, improved confidence sequence (Theorem 3.1), we propose OFUGLE (Algorithm 1), a generic UCB- type algorithm that applies to any instantiations of GL.B. Through a new proof technique that allows us to circumvent K- and poly(S) -ddpeenenneesiss in the leading term, our unified algorithm attains or improves the known tfte-of-the-ait regret bound for the class of self-concordant GLB, which encompasses a zoo of well-studied stochastic bandits such as linear (Abbasi- Yadkori et al., 2011 I; Auer, 2002), Poisson (Gisselbrecht et al., 2015), logistic (Abeille et al., 2021; Faury et al., 2020), etc.
We define the following problem difficulty quantities: recalling that Xry
Uie(7 X,
R.
T Eeer (i( 0.))* x(T) =EXTT, 0EB
max
(8)
ju (ax 0))
These may scale exponentially in S, e.g., for logistic bandits (Faury et al., 2020; Filippi et al., 2010), but we will later show that through with N2 (T), and the transient term scales linearly with k(T).
analysis, the leading term of the regret scales inversely
We now present the unified & state-oftthe-arl regret guarantee for self-concordant GLBs:
Theorem 4.1 (OFUGLB for Self-Concordant GLB). OFUGLB attains the following regret bound for self-concorlami GLB with probability at least 1 5:
g(T)T (T)
SLT RAST + + RoR g(T))((())))))))))))))))(( log 1+
ST
Reg (T) S d
log
log
d
dg(T))((T)
leading terme
transient
where Lr is defined in Theorem 3.1 and we assume that log 1 = o
0 (dlog star)
4.1 Proof Sketch of Theorem 4.1- Regret Analysis of OFUGLB
We first emphasize that even though we have a tight CS (Theorem 3.1), naively combining it with existing regret analyses of logistic bandits (Abeille et al., 2021: Lee et al., 2024) still results in an extra factor of S in the leading term. The prior proof applies the Cauchy-Schwand inequality w.r.t the (regularized) Hessian H,().) ) = AI + + ea (0. D with (.).) == p((x,. -)). which forces the of self-concordant lemma (Abeille al., 2021, Lemma 8). This results in CS of the form |10. (..)). (6). Then, using the same regret decomposition of Abeille et al. (2021)
and the optimism principle, the leading term of the regret is bounded as
Σ (e((,) Iz, 0.) S SBr(8)
Σ (c().)
Σ (i((0.) (.))))-
SVTTK,(T)
elliptical pocential (Abbasi- Yadkori al., 2011)
Our proof begins by applying Cauchy-Schwae Schwartz w.r.t. (,, derived from the integral remainder in first-order Taylor expansion of L-(-) Ø, With this, we have that |0. 10.---llaa. 0.lla.(0)) ())
(Lemma E.6), avoiding the extra S. However, as (θ.) E {(x,, xz for some well- defined scalar function Es. the elliptical potential lemma (as done above) is not applicable due to the explicit dependency on 0.! This difficulty is analogous the analysis of Logistic-UGB-2 in Faury et al. (2020), where a similar difficulty arose because their improved bonus ft, depends on the current estimate of the parameter well (see their Lemma 4). They circumvent this issue by explicitly modifying the UCB algorithm to incorporate additional constraints on the "admissible log-odds." which leads to computationally inefficient algorithm.
Notably, we show via a new proof technique that the vanilla UCB can implicitly handle those constraints by designating a "worst-case" parameter over all future iterations (Fqn. (21)). We develop many other intriguing results, such as a novel self-concordance lemma that bounds the difference of ii's is with that of j²'s times R, (Lemma E.3). We provide the full proof in Appendix E.
7

---

Table 2: Regret bounds of OFUGLB for various self-concordant GLBs. Logarithmic factors are omitted to avoid a cognitive overload. Let (T) = max (m,)). Here, RR-Boudded" means |rel I R a.s..
1 and g(r) O(1).
GLB
Our regret bound
Prior state-of-the-art
aV (.( + RR xxx(T))
R-Bounded
dv k.(T) + &dRRA((T)
(Sawarni al., 2024, Theorem 4.2)
d ViniiTy T (T(T) + +dR((T)
T dv (.(7) + d22 (=xxxxx(77)) (T)
Logistic
(Sawarni et al.. 2024, Theorem 4.2)
odvT (Flynn et al., 2023, Lemma D.10)
Linear
odvT
d3/2 V x.(I)
T
Poisson
dS
T (T) + df de225((7
(Janz et al., 2024, Theorem 1)*
choose o² S² Lemma D.10 Flynn et al. (2023).
Here, we omit the dependencies on S and the transient term from explicit warmup.
4.2 Instantiations and Discussions Theorem 4.1
In Table 2, we instantiate Theorem 4.1 for various self-concordant GLBs. It can be seen that our OFUGLB attains state-of-the-arr regret guarantees in all considered scenarios, either by achieving (linear) or improving upon (bounded, logistic) the known regret bounds! Note that the instantiation for Guu-))ausssian linear bandits meant be sanity check because tighter confidence sets are available in Flynn et al. (2023) and Chowdhury et al. (2023, Appendix F).
To knowledge, only few works deal with generic, (possibly unbounded) self-concordant GLBs. Jun et al. (2017) proposed UCB-style GLOC and its variants, which, however, incur regret bounds scaling with k. (2)) the leading term. Concurrent with our work, Liu al. (2024) prove that all GLBs with light-tailed base distribution are self-concordant, and propose OFU-GLB with regret of O(d/T/K,,TT) (T) + (T). Another line of works (Abeille and Lazaric, 2017: Dong et al., 2019; Janz et al., 2024; Kim et al., 2023; Kveton et al., 2020) considers randomized exploration-bai -based algorithms, including Thompson sampling, which we discuss further in Appendix A.
Below, we discuss our results for bounded GLB, logistic, and Poisson bandits in-depth.
Bounded GLB. The only prior work applicable to general bounded GLB is Sawarni al. (2024), where the authors propose RS-GLinCB with regret as in Table 2. Compared to our regret, they are slightly better as their transient term scales as (T) while ours scales as k(T), but we have much better dependency on R (R vs. R³). Despite this seeming gap, RS-GLinCB relies on an explicit warm-up scheme, our OFUGLB expected to have superior numerical performance as avoids excessive exploration in the early phase. We will elaborate more on this issue in Section 5. Also, it should be noted that Sawarni al. (2024) requires nonconver optimization as a subroutine to obtain poly(S)-free regret (see their Appendix E). Still, RS-GLinCB has its advantages in that it only requires O(log" T)) switches while require ?2(T") switches; it is an interesting open problem whether a lazy variant of OFUGLB with same (or better) regret guarantee is possible.
Logistic Bandits. Although the logistic bandit is a special case of the bounded GLB, the number of prior works and its practical applicability to recommender systems (Li al., 2010, 2012) and recently RLHF (Das et al., 2024) makes it deserving of separate discussions. We first review the prior works on logistic bandits. Faury et al. (2020) was the first to obtain regret bound of +d' (up to some dependencies on S) that is k-free in the leading term. Subsequently, a local minimax regret lower bound S2( (d((d))) VT/ (T)) was proven (Abeille et al., 2021, Theorem 2)², suggesting that more nonlinearity helps, and several works have focused proposing and analyzing algorithms with matching upper bounds. One line of works (Abeille et al., 2021: Lee et al., 2024). including this work, focuses on getting tight convex CS for logistic losses, which then directly gives OFUL-type algorithm. Abeille et al. (2021) first proposed a likelihood ratio-based CS, albeit somewhat loose
'In their statement, dependency on S is ignored. By tracking their lower bound proof, one can see that it leads to extra factor of 1/S.
8

---

in S. Lee et al. (2024) proposed a new framework for converting an achievable online learning algorithm to a tighter CS and proposed UCB algorithm that attains the prior (to this work) state-of- the-art regret bound of O(S / TT/K, (T) + Rx (T)) with (x')) being arm-set geometry-dependeen transient term' From a computational perspective, Faury et al. (2022) proposed an online Newton step- based algorithms that attain the regret bound of (dS ([dS///Kaa /T/K, + d0 (T)) using only (log t) computational cost and (11) storage per time step: the computational cost was later improved to ((1) in Zhang and Sugiyama (2023). Another line of works (Mason et al., 2022; Sawarni et al., 2024) proposed algorithms that perform an explicit warm-up in the early stages, Thanks the explicit warmup, both attain regret with poly(S)-free leading term, e.g., ((d/T//mm + xx
xx (T)) by
Sawarni et al. (2024). However, the explicit warmup typically lasts for (T)) or (T)x((T) time steps. resulting potentially very large initial regret. This is later verified in our logistic bandits experiments. Our OFUGLB is the first purely optinism-based UCB algorithm (no explicit warmup) that attains a poly(S)-frre leading term in the regret.
Poisson Bandits. Despite its potential model various real-world problems involving count feedback, Poisson bandits have not been studied often in the literature. Gisselbrecht et al. (2015) was the first to consider contextual Poisson bandits and proposed UCB and optimistic Bayesian- algorithms (May et al., 2012), but without any regret guarantees. To our knowledge, our Theorem 4.1 provides the first regret bound for the dimensoammnsional) contextual Poisson bandits without reward boundedness assumption. On a related note, Mutný and Krause (2021) consider Poisson bandits with the intensity function in an RKHS. Their linear RKHS formulation is, however, incompatible with our log-linear formulation; see their Appendix A.1 for further discussions.
5 Experiments
We perform experiments on logistic bandits to complement the theoretical improvement in our regret bounds and CS. The codes are available in our GitHub repository forked from the previous repository" of Faury et al. (2022). Our GitHub provides the unified implementations of all considered algorithms, which we hope will be helpful in future research and benchmarking of logistic bandits. In Appendix G. we provide the missing implementation details and additional experimental results.
Baselines and Setting. We compare our OFUGLB (likelihood ratio-based CS: Theorem 3.1) and OFUGLB-e (ellipsoidal CS; Theorem 3.2) to the following five baselines: EMK (Emmenegger et al., 2023), EVILL (Janz et al., 2024), RS-GLinCB (Sawarni et al., 2024), OFULog+ (Lee et al., 2024), and Eda-OFF-EECLLLC and RS-GLinCB is specific to bounded GLBs. We emphasize that when implementing OFUGLB and OFUGLB-e, we use the precise theoretical hyperparameters as given in our theorem statements without further tuning. To highlight the practical effectiveness of our theoretical algorithms in comparison to randomized exploration, which known to perform well in practice (Chapelle and Li, 2011; Russo et al.. 2018), we use a single, untuned hyperparameter for EVILL". For the experimental setup in this section, we set = 10000, d = 2, and 8 0.05. We consider time-varying arm-set: at each t E [7], an arm-set A C (1) of size (Arl = 20 is uniformly sampled. We set 0. = S-1 1 for E [4, 6, 8, 10). Lastly, we consider 10 independent repeats per setting for statistical significance.
(Faury al., 2022). Note that the last two are specific logistic bandits,
v
Results and Discussions. The results are shown in Figure 1. Note that in all considered settings, OFUGLB, EMK, and EVILL outperform every other baseline, both in terms of regret and numerical tightness of the CS. Moreover, for S {8, 10), our OFUGLB seems to achieve the best performance, although more comprehensive numerical studies would shed more light on this matter. As for our OFUGLB-e, despite having worse performance than OFUGLE, EMK, and EVILL, it always attains better numerical performance than the remaining algorithms. Notably, OFUGLB and EMK achieve at par or better numerical regret compared to EVILL with heuristic hyperparameter. This highlights the effectiveness of our theoretical results even compared to heuristically tuned randomized exploration.
Onn may wonder why our Theorem 4.1's transient term always scales <(T)). See Appendix B for further discussions on this interesting difference.
"nttps://gither http://githhu..ccm/iik.k com/nick- Beeccc-jhheeeeeee shlee//ogistic_blll bandit
$ hattps://itthu com/crites resear ch/ coogiticcbbandeee
"We remark that in Appendix G, we provide additional results (for K = 10), where EVILL with its theoretical
hyperparameters performs either worst second-wort

---

OFUGLB
EMK
EVILL
RS GLinCB
OFULog+
ada OFU-ECOLog
300
4-4
200
5-6
300
5-8
400
S
250
250
250
350
300
200
200
200
250
Regret
150.
150
150
200
200
100
100
150
100
50
50-
50-
50-
0
2500
5000
7500
12000
0
2500
5000
7500
10000
2500
5000
7550
10000
25.00
5500
7500
16050
400
25
25
16-
33
14.
Magnifted reght
330
20-
12.
25.
10-
20-
155
1.
5-
0
2500
5000
7500
13600
0
0
2500
5000
7500
10000
2500
5000
7500
10000
0
2500
5000
7500
16050
10.0
7.5
Confideng
2.5
4-
0.0
1.5-
22.5
Figure 1: Time-varying arm-sets. (First row) Regret plots of all considered algorithms. (Second row) Magnified regret plots. (Third row) Confidence set plots at the final time / 10000 when applicable. Each column represents a different logistic bandit instance for (4, 6, 8, 103.
One interesting observation is that even though OFULog+ achieves much tighter CS at the end, its regret is much worse than OFUGLB-e. We posit that this is related to the interplay between the CS and arm set geometries, and we leave further study of such discrepancy future work. Another is that RS-GLL DS-GLinCB with the exact theoretical hyperparameters (Sawarni al., 2024) performs the worst, We believe this is because their theoretical hyperparameters
worse than not numerically tight, forcing the algorithm to explore throughout the entire duration, probably as their Switching Criterion (line 4 of their Algorithm 2) is always true. To use RS OS-GLinCB in practice, one must tune' the hyperparameters to explicitly control the degree of exploration, which not the case for our OFUGLB, making ours viable, practical algorithm with a provable guarantee as well, Lastly, note how the likelihood-basse CS, (0 E θ (0) < cr) for a O(log l). resembles an ellipsoid. This is because the "normalized" sublevel value e/ (as there I summands in the LHS) gets smaller, making the second-ords -oder Taylor expansion more accurate.
6 Conclusion
This paper introduces a novel and unified likelihood ratio-based for generic (convex) GLMs, encompassing widely-used models such Gaussian, Bernoulli, and Poisson. Our CS is equipped with exact constants for various scenarios, making it suitable for any practitioner. The proof involves leveraging key techniques from PAC-Bayes bounds with uniform prior/posterior. We then propose OFUGLB, a generic UCB algorithm applicable to any GLBs, achieving ffate-of-the-ad regret bounds across all seff-concordant GLBs. The proof involves novel regret decomposition and maximally avoiding the self-conccrdance control lemma (Faury et al., 2020, Lemma 9), which may be of independent interest. Notably, for logistic bandits, OFUGLB is the first pure-optimism-baase bhased algorithm that achieves poly(S) -fryeeee leading term in the theoretical regret, which is numerically verified to perform best. This work opens up various future directions, which discuss in detail in Appendix B.
"This is the case in their GitHub implementation, where heuristic values were used for their experiments. Additionally, their algorithm requires the knowledge of K..
10

---

Acknowledgments and Disclosure of Funding
J. Lee thanks Gergely Neu for hosting him a wonderful workswor after AISTATS '24 UPF, during which many insightful discussions inspired the current PAC-Bayesian proof. J. Lee also thanks Branislav Kveton for suggesting trying a randomized algorithm for logistic bandits experiments. Tim van Erven for insightful discussions regarding the fast rates in statistical learning, and Aaditya Ramdas for insightful comments on the prior- poor-posterior martingale, all during AISTATS '24. Lee also thanks Jaeyoung Cha for suggesting WolframlAAphe The authors thank the anonymous reviewers of the ICML '24 ARLET Workshop and NeurlPS 24 for insightful questions and suggestions that helped us significantly improve the paper.
elementary proof for Lemma C.I that does not rely on
Lee and S.-Y. Yun were supported in part by the Institute of Information Communications Technology Planning & Evaluation (IITP) grant funded by the Korean government (MSIT) (No. RS-2022-1220311 Development of Goal-Oriented Reinforcement Learning Techniques for Contact- Rich Robotic Manipulation of Everyday Objects and No. RS-2019 2019-10911111 90075 Artificial Intelligence Graduate School Program (KAIST)) and the National Research Foundation of Korea(NRF) grant funded by the Korean government (MSIT) (No. RS- RS-2019-NR040055 Stochastic Analysis and Application Research Center (SAARC)). K.-S. Jun was supported in part by the National Science Foundation under grant CCF-2327013.
References
Yasin Yadksi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved Algorithms for Linear Stochastic Bandits. In Advances in Neural Information Processing Systems, volume 24, pages 2312-2320. Curran Associates, Inc., 2011. URL betps://siter ualberta.cal caabbrraacaa"szzpessa/aaaaaaaaee -
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Caline-to-Confidenee and Application to Sparse Stochastic Bandits. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statisties, volume 22 of Proceedings of Machine Learning Research, pages 1-9. PMLR, 21-23 Apr 2012. URL https: pppppeedoeegnsss .mm.innns.........mmmmmmm..mmm.. wwwssseesvvv abbasi-yadkori 2html
Conversions
Mare Abeille and Alessandro Lazaric. Linear Thompson sampling revisited. Electronic Journal of Statistics, 11(2):5165 5197, 2017. doi: 10.1214/17-ESS1441SS) URL https:://doo.. org/10.
1214/17-EJS1341SI.
Mare Abeille, Louis Faury, and Clément Calauzěnes. Sittacee-Wise Minimax-Optimal Algorithms for Logistic Bandits. In Proceedings The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3691-3699. PMLR, 13-15 Apr 2021. URL https:
mlr www.rpresssvvvee wttasss/vv//// hbtp//eeeellleleeeaea html.
Pierre Alquier. User- frienfriy Introduction to PAC-Bayes Bounds. Foundations and Trends@ in
Machine Learning. 17(2):174-300) 2024. ISSN 1935-8237. doi: 10.1561//2000000000, URL
http://dz doi. org/ wttp:////.....//.... 156112200000010000
Peter Auer. Using Confidence Bounds for Exploitation-EExlorraoo Trade-offs. Journal of Machine Learning Research, 3:397-422, Nov 2002. URL httpp:////jl...com csail. meail.mit. mit edu/ wdw.papersssseeeee s/v3/
auer02a. html.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2):235-256, May 2002. ISSN 1573-0565. doi: 10.1023/A: 1013689704352. URL attps://dol org/10 10. A: (013//A:1136889704555
Mohammad Javad Azizi, Branislav Kveton, and Mohammad Ghavamzadeh. Fixed-Budget Best- Arm Identification in Structured Bandits. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 2798-2806 International Joint Conferences on Artificial Intelligence Organization, 7 2022. doi: 10. 10.24963/ijcai.20222333 URL https:
//doi. //doi.org/11 org/10. 10. 24963/1 2022/388. Main Track.
Jackie Baek and Vivek Farias. TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation. In Proceedings of The 26th International Conference Artificial
11

---

Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 11132- 11148. PMLR, 25-27 Apr 2023. URL httpss://proceedinggs... mlr. html.
Avrim Blum and Adam Kalai. Universal Portfolios With and Without Transaction Costs. Machine Learning, 35(3):193-200 Jun 1999. ISSN 1573-0565. doi: 10.102/A:100075307277444 URL 100.00100002011000377777888 100753078878..
https://doi.org: orgg 1023/0222111// A
Vladimir Igorevich Bogachev. Gaussian Measures. Number 62 in Mathematical Surveys and Monographs, American Mathematical Society, 1998.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Gavin C. Cawley, Gareth J. Janacek, and Nicola L. C. Talbot. Generalised Kernel Machines. In 2007 International Joint Conference on Neural Networks, pages 1720-1725, 2007. doi: 10.1 10.1109/ 2007.4371217. URL https: //tieexxpoooreeeeeeeoo ieee. httg//documet/447110
Olivier Chapelle and Lihong Li. An Empirical Evaluation of Thompson Sampling. In Ad- vances in Neural Information Processing Systems, volume 24, pages 2249-224555 Curran As- sociates, Inc., 2011. URL
nips. wwtppper_fiiiieeeeeeee faarsr_fllllpppppp htilee//apper/211/haaaaa Abstract htmml.
Sayak Ray Chowdhury and Aditya Gopalan. On Kemelized Multi-armed Bandits. In Proceedings of the 34th International Conference on Machine Learning. volume 70 Proceedings of Machine Learning Research, pages 844-853. PMLR, 06-11 Aug 2017. URL http::: http:::///occeddneg.e mlr. wat..reessvv.. htt.:/howooorloocco/ html.
Sayak Ray Chowdhury, Patrick Saux, Odalric Maillard, and Aditya Gopalan. Bregman Deviations of Generic Exponential Families. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 394 449. PMLR, 12-15 Jul 2023. URL https:
/tttps::/prroo http://///occeee..../oo.. mlr. atress/v995/ c195//hhwdhury28.. html.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep Reinforcement Learning from Human Preferences. In Advances in Neu- ral Information Processing Systems, volume 30, pages 4302-4310. Curran Associates, neurips.cc. pec/paper_fille filessfiee//eeeeeee sateerfflleepppper//e /aper//0117/file Inc., 2017. URL https::/proceediiiie Paper ..p.r.pdf. abb220acaabbcee111111e440ddeeeee
Ben Chugg, Hongjian Wang, and Aaditya Ramdas. Unified Recipe for Deriving (aine-nnifomm PAC-Bayes Bounds. Journal of Machine Learning Research, 24(372):1-61 2023. httphttp:
html.
Giuseppe Da Prato and Jerzy Zabezyk. Stochastic Equations in Infinite Dimensions. Number 152 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition, 2014.
D. A. Darling and Herbert Robbins. Confidence Sequences for Mean, Variance, and Median. Proceedings of the National Academy of Sciences, 58(1):66-68, 1967a. doi: 10. (0.1073/pnas.5..11 URL https: / //ww. pnas org/ htgg//o///e /ttp//bs///0/// 20000//p/s..// 1.66.
D. A. Darling and Herbert Robbins. Iterated Logarithm Inequalities. Proceedings of the National Academy of Sciences, 57(5):1188 189-119,, 1967b. doi: 10. 00.1073/pma..5.55.1188. URL https:
// pnas wwtpppaw..........p..pppp htt://do/abss////// 107300073pa htt.//nas..... 57.5...... 5188..
Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury, Active Preference Optimization for Sample Efficient RLHF, arXiv preprini 10X5v.2402.10500, 2024. URL https:
// //arxivv.o. org/ 2402 10500.
Victor H. de Peña, Michael Klass, and Tze Leung Lai. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. The Annals of Probubility, 32(3): 1902 - 1933, 2004. doi: 01122144001119944000000 URL. https://doi.. org/10..11000
009117904000000397.
12

---

Shi Dong, Tengyu Ma, and Benjamin Van Roy. On the Performance of Thompson Sampling on Logistic Bandits. In Proceedings of the Shirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1 1158-1160. PMLR, 25-28 Jun 2019. URL httpps:/prroceedings mmlr httpaiinnns.....ess/eeeeeee httg///nggggg html.
M. D. Donsker and S. R. S. Varadhan. Asymptotic Evaluation of Certain Markov Process Expectations for Large Time. IV. Communications on Pure and Applied Mathematics, 36(2):1832112 1983. doi: http:///oo..rrg/11...0//////..// httpp///....00///g...66666660000
URL attps://onllieeeeee wwrprrrrrrrrllllllleeeleeeeeeeee wiley com/
John Duchi and Saminul Haque. An information-theoredt lower bound in time-uniform estimation. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1486-1500. PMLR, 30 Jun-03 Jul 2024. URL https:
// //proceedings. mlr. wwtppp/eee///ueeeeepeeppp http:///i22//ccccaaaaaa httml..hhhaaaa..........mm.a
Nicolas Emmenegger, Mojmír Mutný, and Andreas Krause. Likelihood Ratio Confidence Sets for Sequential Decision Making. In Advances in Neural Information Processing Systems, volume 36.
Curran Associates, Inc., 2023. URL https::////// http:///pppeeeeeeeeeeee wttp://oooooiidddaaarraaaaa
Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved Optimistic Algorithms for Logistic Bandits. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5052-3060. PMLR, 13-18 Jul 2020. URL https: / / wmw.eeddddnnnn..............m... mlr /ttp///eedeaaan.aa..eee/////////
html.
Louis Faury, Marc Abeille, Swang-Sung Jun, and Clément Calauzènes. Jointly Efficient and Optimal Algorithms for Logistic Bandits. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 546- 580. PMLR, 28-30 Mar 2022. URL https: http:///oooceeeeeeee//e// .ll wwwpppresssseee vatass//11////ar22223 html.
Herbert Federer. Geometric Measure Theory. Classics in Mathematics. Springer Berlin, Heidelberg, 1996.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric Bandits: The Generalized Linear Case. In Advances in Neural Information Processing Systems, volume 23, pages 586-594. Curran Associates, Inc., 2010. URL https: https::/prooeedingss neurips cc/ pdf.
paper_filedt http:///ppppp.////////////oeeeee
Hamish Flynn, David Reeb, Melih Kandemir, and Jan Peters. Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures. In Advances in Neural Information Processing Systems, volume 36. Curran Associates, Inc., 2023. URL https: /pw.revepp.re.ee..e//eeeee net met//forumidd-TooZuUyyy
Dylan Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic The Importance of Being Improper. In Proceedings of the 31st Conference On Learning Theory, volume of Proceedings of Machine Learning Research, pages 167-208. PMLR, 06-09 Jul 2018. URL https: htttps://proceedingg. mlr grress/v75/fosterrlee html.
Regression:
Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logisties Quarterly, 3(1-2):95-110,, 1956. doi: http:://ooo.orr/10.0002aaa3303.0 httpps//ooninnelirre
URL
wiley. com/doi/ /wdd///abbba/e ha///bb/////0 wtwp://0/....3000000000000
Spencer B. Gales, Sunder Sethuraman, and Kwang-Sung Jun. Norm-Agnostic Linear Bandits. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 73-91. PMLR, 28-30 Mar 2022. URL nttps://proceediin
mlr ptwss/v1ss//eeppppptpppppppasptt gales22a, html.
Thibault Gisselbrecht, Sylvain Lamprier, and Patrick Gallinari. Policies for Contextual Bandit Problems with Count Payoffs. In 2015 JEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI), pages 542-549, 2015. doi: 10.1109/CCTA..20155.88 URL. https://
ieeexplore ieee. atg/documentt/33221.1..
13

---

Peter D. Grünwald and Nishant A. Mehta. Fast Rates for General Unbounded Loss Functions: From ERM to Generalized Bayes. Journal of Machine Learning Research, 21(56):1 2020. URL
http://jmlr org/ pttppppss//1111-449550 html.
Nima Hamidi and Mohsen Bayati. On Frequentist Regret of Linear Thompson Sampling, arXiv preprint arXiv:2006. 06790, 2020. URL htttt:://aaate httppp///aaaaiv.rr//abab//////// wwtp:////////a/////eee// 06790.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):19--192, Dec 2007. ISSN 1573-0565. doi: 10.1007/
$10994-007-5016-8 URL attps:///oli. org 11t1://0000000110000000000000000 http://///o////o...////////////.
David Janz, Shuai Liu, Alex Ayoub, and Csaba Szepesvári. Exploration via linearly perturbed loss minimisation. In Proceedings The 27th International Conference on Artificial Intelligence and Statisties, volume 238 of Proceedings of Machine Learning Research, pages 721-729. PMLR, 02-04 May 2024. URL https: http:///ooceeddeee mlr. ppress/v338 jan224/an224a. anz24a.. html.
Rémi Jézéquel, Pieme Gaillard, and Alessandro Rudi. Efficient improper learning for online logistic regression. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2085-2108. PMLR, 09-12 Jul 2020. URL ittps://prooceedings mlr wtwpsppees/////e jttps/eeeeeeeeeeeeeea html.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan. A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm. arXiv preprint arXiv:1902.0377 2019. URL https://taaatee http://aarw..oraaaaa/a/aaaaa
Kwang-Sung Jun Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scal- able Generalized Linear Bandits: Online Computation and Hashing. In Advances in Neural Information Processing Systems, volume 30, pages 98-108. Curran Associates, Inc., 2017. URL https: http::////ooooee.e....eee.eeeeee 0hal227955e666454400000000000000 Paper pdf.
Kwang-Sung Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5148-5157. PMLR, 18-24 Jul 2021. URL https //pppp////c/cc/gs...... mlr aalr.pesss/vv9/ jun21a.
Emilie Kaufmann and Wouter M. Koolen. Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals. Journal of Machine Learning Research, 22(246): 2021. URL htth::tpt:::llll org/ wwrggpapprs/v22// 1tt/v///////////22/ html.
Abbas Kazerouni and Lawrence M. Wein. Best arm identification in generalized linear bandits. Operations Research Letters, 49(3):36--37,, 2021. ISSN 0167-6377. doi: https://doi.org org/ 10166j.or.20221.3..01 URL http://wwww..ciineeeeeettttt ccmm/sciencce/aticcll/p..... 50167637721000525.
Wonyoung Kim, Kyungbok Lee, and Myunghee Cho Paik. Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 37(7):8300-83 Jun. 2023. doi: (6t9//aai.3377..22222.. URL
aaai..rg/iia.aaa.......... https://ojs. aaai org/ index.iddxxx/// php/
Yeoneung Kim, Insoon Yang, and Kwang-Sung Jun. Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs. In Advances in Neural Information Processing Systems, volume 35, pages 1060-1072. Curran Associates, Inc., 2022. URL https: www.torrurrmeeeeee patormmmi=:l] iir-dd-_____ No__PSEEyN22s.
//openreview. wwwpeeeewwwwwwweefrfeeeeeeee
Johannes Kirschner and Andreas Krause. Information Directed Sampling and Bandits with Het- eroscedastic Noise. In Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 358-384. PMLR, 06-09 Jul 2018. URL htt..ppps////////iccerrr......
https: h/tp:s::///cceeinggs mlr. wwwpss/ve55. hwtrs//iisccheeeeeeeeee 18a.ttm............ html.
14

---

Dieter Kraft. A Software Package for Sequential Quadratic Programming. Technical Report DFVLR- FB 88-28, Deutsche Forschungs und Versuchsanstalt für Luft- und Raumfahrt Institut für Dynamik der Flugsysteme, Köln, Deutschland, 1988. URL htttp:://degnneratccoii com/ aploads/2018) O3/DFVLR_ _B________________ pdff.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvári, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized Exploration in Generalized Linear Bandits. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2066-2076. PMLR, 26-28 Aug 2020. URL attpp://ppee htttss//proceedding.. mlr. wae.r.pees///ee wwwppp/eeseseseeepeepepeeeeeeeee v108/vvetoo000. html.
Ricardo Lage, Ludovic Denoyer, Patrick Gallinari, and Peter Dolog, Choosing which message to publish on social networks: A contextual bandit approach. In 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013), pages 620- 627, 2013. doi: 10.11445/442217724425554 URL URLhttps::/ieeexpp.oo ieee. org/ document/ 6785767.
Tze Leung Lai. On Confidence Sequences. The Anmals of Statistics, 4(2):265 - 280, 1976. doi: 10.1214/aos/1 176343406 URL https://doi.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Junghyun Lee, Se-Young Yun, and Kwang-Sung Jun. Improved Regret Bounds of (Multi- nomial) Logistic Bandits via Pegree-to-Confiddnnce
Conversion. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Pro- ceedings of Machine Learning Research, pages 4474 4482. PMLR, 02-04 May 2024. URL 2ets///33//eee22 leeleeee2dddee html.
attps://pet http::///proceddngss mlr prwss/
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A Personalized News Article Recommendation. In Proceedings of the 19th International Conference on World Wide Web, WWW '10, page 661-670, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 9781605587998. doi: 10. 10.1145/1772690.1777 1772758. URL https: o00/ 1145/1772690 1772758.
Approach to
Lihong Li, Wei Chu, John Langford, Taesup Moon, and Xuanhui Wang. An Unbiased Offline Evaluation of Contextual Bandit Algorithms with Generalized Linear Models. In Proceedings of the Workshop on On-line Trading of Exploration and Exploitation 2, volume of Proceedings of Machine Learning Research, pages 19-36, Bellevue, Washington, USA, 02 Jul 2012. PMLR. URL https: http:///eccceee.....mmm mlr. wil.rppres//ve masess/v22611 v26/1i12a...aa..a html.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably Optimal Algorithms for Generalized Linear Contextual Bandits. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2071-2080. PMLR, 06-11 Aug 2017. URL https:// tttt:ee//proceeiiggs .mr..ns.m.......mm..........m... ppess/v70/11 https//////111..hh.h.ee html.
Xuheng Li, Heyang Zhao, and Quanquan Gu. Feel-Good Thompson Sampling for Contextual Dueling Bandits. In Proceedings of the 41 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 29406-29422 PMLR, 21-27 Jul 2024. URL https: / http://edno/g......///// mlr prwsppresssssseeep vvs///225////// 1i24co...... html.
Elliott H Lieb. Convex trace functions and the Beaner-Yanase-Dyson conjecture. Advances in Mathematies, 11(3):267-288, 1973. ISSN 0001-8708. doi: https://doi.org 1016/ 0001--8708(73)90011-X URL https: www.w/..inne..ree.......mmm htwp:/acneedrreettooc/ccccaeeeee httm:/ccinnc/artileee/// 000187087390011X.
Shuai Liu, Alex Ayoub, Flore Sentenac, Xiaoqi Tan, and Csaba Szepesvári. Almost Free: Self- concordance in Natural Exponential Families and an Application to Bandits. In Advances in Neural Information Processing Systems, volume 37. Curran Associates, Inc., 2024. URL https: //openreview wtw.seewwwweet.eeemmmeeee www.rrrmmmmmmiwwiiweeeeee.ee
Blake Mason, Kwang-Sung Jun, and Lalit Jain. An Experimental Design Approach for Regret Minimization in Logistic Bandits. Proceedings the AAAI Conference on Artificial Intelligence, 36(7):7736-7743, Jun. 2022. doi: 10. 161699aaai.33377.077444 URL. https: / //jjs./....///// majjsaase aaai org/
indez. httpp//AAA/artiilla/aaaaaaaaaaa/
15

---

Benedict C. May, Nathan Korda, Anthony Lee, and David S. Leslie. Optimistic Bayesian Sampling in Contextual-Bandis Problems. Journal of Machine Learning Research, 13(67):2069-2106 2012. URL ptctt://jmil http://rrrorrrrrr/./////rr/ pttpppapppaaa/a/aaeeeepaa mammayyla 12. html.
Peter McCullagh and John A. Nelder. Generalized Linear Models. Monographs on Statistics and Applied Probability. Chapman & Hall/CRC, 2 edition, 1989.
Hans-Geore Müller and Ulrich Stadtmüller. Generalized functional linear models. The Annals of Statistics, 33(2):774 - 805, 2005. doi: 10.1 101221400905364440000111111 156. URL https://doi. org/ 10. 001111440099955000000000000
Katta G. Murty and Santosh N. Kabadi. Some NP-complete problmms in quadratic and nonlinear programming. Mathematical Programming, 39(2):117-129, Jun 1987. ISSN 1436-4646. doi: 10. 10.10077/BF02592948. URL httpps:///bl
10. http//0000000//225222200
Marco Mussi, Simone Drago, and Alberto Maria Metelli. Open Problem: Tight Bounds for Kernelized Multi-Armed Bandits with Bernoulli Rewards. arXiv preprint arXiv:2407.06321, 2024. URL
https://arxiv. owgeeiiivrrgggge wwwg//////aaa.. 2207 06321.
Mojmír Mutný and Andreas Krause. No-regret Algorithms for Capturing Events in Poisson Point Processes. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7894-7904. PMLR, 18-24 Jul 2021. URL attps://ptrs /ttp:////ccccec....//oo.. mlr wwwpppeesssssse ppress/v19//muty//// html.
Willie Neiswanger and Aaditya Ramdas. Uncertainty quantification using martingales for misspecified Gaussian processes. In Proceedings of the 32nd International Conference Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 963-982. PMLR, 16-19 Mar 2021.
URL https://
mlr www.ssressvveee http//v12///// wtt.:////iiswaaneee1e111 html.
Yuki Ohnishi and Jean Honorio. Novel Change of Mcasure Inequalities with Applications to PAC-Bayesian Bounds and Monte Carlo Estimation. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1711-1719. PMLR, 13-15 Apr 2021. URL http:: //ppoe/dg/....ssiggs.. mlr. war.press/vi33 wwwishiiniii html.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, volume 35, pages 27730-21 27744. Curran Associates, Inc., 2022. URL https: /ttp::::///ppeevviieeeee nett/foruun.d--TTK.CEEE
John C. Oxtoby. Invariant Measures in Groups Which Are Not Locally Compact. Transac- lions of the American Mathematical Society, 60:215-237, 1946. doi: https://oi.org///// 1090/ 194--001194--0188888888888 URL https://www: ams org/journals/trreseeee watpaaassstaaaa19/-eea 060-00/ S0002 9947 1946-0018188-
Vern I. Paulsen and Mrinal Raghupathi. An Introduction to the Theory of Reproducing Kernel Hilbert Spaces. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2016.
Friedrich Pukelsheim. Optimal Design of Experiments, volume 50 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), 2006.
Aaditya Ramdas, Peter Grünwald, Vladimir Vovk, and Glenn Shafer. Game-Theoretic Statistics and Safe Vaytime-Valid Inference. Statistical Science, 38(4):576 2023. doi: 10.1214/23-STSS8 URL https: : //tpi.//iia///////o org/10. 10. 21144/33-SSBBB
Herbert Robbins. Some Aspects of the Sequential Design of Experiments. Bulletin of the American Mathematical Society, 58(5):527 - 535, 1952. URL /Rt.ttpse//ppooecceccdddaaa org/
www.eeaiaataaaaaaaaaaaaaaaaaaeee http://www....caaccooooo.oa.aaaa Some- aspects--etsseeee the htt.a:/eec...............oeoeaaa
full.
16

---

Herbert Robbins and David Siegmund. A Class of Stopping Rules for Testing Parametric Hypotheses. Proceedings of the Sixth Berkeley Symposium on Mathematicaal Statistics and Probability Volume
4: Biology and Health, 6(4):37-41, 1972. /Rtp.//pps///pprggtttaaaa...d...
Shapter/A-clssee http:e//---ccass--sssooooooneeee for for- pwwp--eeettnnaaaaarrrr-----oooeo bamsp/12005 100sp/1200514544.
Yoan Russac, Louis Faury, Olivier Cappé, and Aurélien Garivier. Self- Coff-Concordat Analysis of Generalized Linear Bandits with Forgetting. In Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 658-666. PMLR, 13-15 Apr 2021. URL https::/prroceee russac21a.hie html.
mlr wwtpssmw.........1331.1 press/v130/
Daniel Russo and Benjamin Van Roy. Learning to Optimize via Iitormation-Directtee Sampling. Operations Research, 66(1 (6(1)):30-252, 2018. doi: 00.1287/pre.2017.1665 URL https://aoi. org/10. 1287 1287/opro /opre........ 2017 1663.
Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A Tutorial on Thompson Sampling. Foundations and Trends@ in Machine Learning, 11(1): 2018. ISSN -237. doi: 10. 10.1561/2200000000. URL http: / dx. doi org/10. 106115111222 155112200000070.
Ayush Sawarni, Nirjhar Das, Siddharth Barman, and Gaurav Sinha. Generalized Linear Bandits with Limited Adaptivity. In Advances in Neural Information Processing Systems, volume 37. Curran Associates, Inc., 2024. URL https: openreview net pet/forwe http://rrmmi--PPPPPTTPTP
Jack Sherman and Winifred J. Morrison, Adjustment of an Inverse Matrix Corresponding to a Change in One Element of Given Matrix. The Annals of Mathematical Statistics, 21(1):124 127, 1950. doi: 10. /0.121//amm/1111
177729893. 1 URL https: //op:s://ddd doi. org/ 10. 1e14/2212oaaa aoms/ 117777999979
Chengshuai Shi, Kun Yang, Zihan Chen, Jundong Li, Jing Yang, and Cong Shen. Efficient Prompt Optimization Through the Lens of Best Arm Identification. In Advances in Neural Information Processing Systems, volume 37. Curran Associates, Inc., 2024. URL https: oppnrevien. met//forum?:d=FLIMnIBBCC.
Niranjan Srinivas, Andreas Krause. Sham Kakade, and Matthias Seeger. Gaussian Process Op- timization the Bandit Setting: No Regret and Experimental Design. Proceedings of The 27th International Conference Machine Learning, pages 1015-1022, 2010. URL
https:/ /ttpas:///rxvv..e/e www.xii.org//bbaa... wtwg//as//1........
William R. Thompson. On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3/4))285-294 1933. ISSN 00063444. URL
http:://wwe http://wwwjjtt.rrrooo////
Joel A. Tropp. An Introduction to Matrix Concentration Inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230, 2015. ISSN 1935-8237. doi: 10.1561/22000000488 URL http:/ http::/xxxxdooooooooo org/ 1ttp://....1111/11111 /5611/2000004488.
Tim van Erven, Peter D. Grünwald, Nishant A. Mchta, Mark D. Reid, and Robert C. Williamson. Fast Rates in Statistical and Online Learning. Journal of Machine Learning Research, 16(54): 1793-1861, 2015. URL. // jmlr httpmmoorrpopaaee..e..eeeeeeeee. httg:/ppper///////rrreeeellll html.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010. URL https: org/ 0tt//111..000
Roman Vershynin. Digh--Dimessioal Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Jean Ville. Étude critique de notion de collectif. Monographies des Probabilités, Paris: Gauthier- Villars, 1939. URL http:// : eudml. www.////////.........
17

---

Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland. Tyler Reddy, David Couraaeea,, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, Iihan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, lan Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272. 2020, doi: 00010388/41132--0---66--- URL https: //www. nature....... com/ awwaaarttilssaar wwwrrriclllsse111--e1111 001111/00//11112--0996666666
Larry Wasserman, Aaditya Ramdas, and Sivaraman Balakrishnan. Universal inference. Proceedings of the National Academy of Sciences, 117(29): 2020. doi: 10. 10.1033/psas. 117.3//a...12224411111 1922664117,
URL https: /www. pnas wtt.:paas...p.pppae. http////////bbba/0..1/////////// 19t.66411.226
R. Wolke and H. Schwetlick. Iteratively Reweighted Least Squares: Algorithms, Convergence Analysis, and Numerical Comparisons. SIAM Journal on Scientific and Statistical Computing, 9 (5):907-922) -21, 1988. doi: 10.1137/090906.. URL https: //toi. org/oog/////o 10. 1137 /0909062.
Tong Zhang. Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning. SIAM Journal on Mathematics of Data Science, 4(2):834 857, 2022. doi: 10. 10.1137//1M140094X
URL bttps://dok: org/10. 1111111111111 /2M14444X4
Yu-Jie Zhang and Masashi Sugiyama. Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost. In Advances in Neural Information Processing Systems, volume 36.
Curran Associates, Inc., 2023. URL ht atttps:// httpss///pppeeeeeeeee nnt.
18

---

Contents
Introduction
2 Problem Setting
3 Unified Likelihood Ratio-based Confidence Sequence for GLMs
3.1 Ellipsoidal Confidence Sequence for Self-Concordant GLMs
3.2 Proof of Theorem 3.1 PAC-Bayes Approach with Uniform Prior
3.3
Intuitions Behind the Proof of Theorem 3.1
4
DFUGLB: A Generic UCB Algorithm for Self-Concordant GLBs
4.1
Proof Sketch of Theorem 4.1 Regret Analysis of OFUGLB
4.2
Instantiations and Discussions of Theorem 4.1
5
Experiments
Conclusion
10
A Additional Related Works
20
Future Works
21
C Missing Proofs from Table 1 - Bounding L,'s
23
C.I GLMs that Bounded by M
23
C,2 r-subGaussian GLMs
23
C,3 Poisson Distribution
24
Proof of Theorem 3.2 Ellipsoidal Confidence Sequence
28
E Proof of Theorem 4.1 - Reegret Bound of OFUGLB
29
E.1 Key Ideas of the Proof
................................
29
E.2 Main Proof
30
E.3 Supporting Lemmas
34
F Alternate CS via Discrete Uniform Prior and Covering Argument
36
G Deferred Experimental Details and Results from Section 5
38
G.I Implementation Details
38
G.2 Additional Results for Logistic Bandits with Fixed Arm-Set..
38
G.3 Additional Results for Logistic Bandits with [ = 10, with Some Updates
39
19

---

A Additional Related Works
Relations to Chowdhury et al. (2023). Recently, Chowdhury et al. (2023) proposed two generic CSs for exponential family, one for i.i.d. samples and one for adaptively collected samples. Both CSs are expressed in the local Bregman geometry induced by the log- rog-pattition function. The proof relies on the method of mixtures (de la Peña et al., 2004; Kaufmann and Koolen, 2021), which resembles our PAC-Bayesian approach that utilizes mixture of log-likelihood functions. One drawback is that their main result for i.i.d. samples (Chowdhury et al., 2023, Theorem 3) is instantiated for scalar parameters (e.g., JA E [0, 1] for Bernoulli without observed feature vectors), and not for GL.Ms. While one can attempt to instantiate it to GLMs, we speculate that the resulting confidence set may not be convex since the prior itself is centered at the true parameter, unlike our choice of the prior. While we believe their second method for adaptively collected samples (Chowdhury et al., 2023, Theorem 7) results in a convex set when instantiated to GLMs, the authors do not provide any computationally efficient way to evaluate the integral over the unknown parameter except for the Gaussian GLM. We also mention that contrary to our work, they allow for θ = Rd by introducing a strictly convex (xp(-Zo(0)) (0)) < cc. Still, theoretically, it is open whose CS (ours regularizer Zu such that Se exp( Zo
or theirs) is tighter when e C B (S). We mention in passing that their CS for Gaussian (Chowdhury et al., 2023, Appendix F) improves upon Abbasi-Yadkori et al. (201 1) in the same manner (i.e., results in / a + b instead of Va + /b) that Flynn et al. (2023) and ours do.
Fast Rates in Statistical Learning. Our goal is to obtain a tight CS for 0., which is quite different from that of statistical learning, which is to obtain the optimal decay rate of the ERM. Although is not immediately clear, we believe they have connection. To illustrate our suspicion, we recall Example 10 of Grünwald and Mehta (2020). By taking a uniform prior over a function space J and taking the posterior to be randomly sampling from e-ball centered at f. the KL term becomes the metric entropy of F, log (FF,A(FF,),, Combining this with the Bernstein condition with exponent (3, the ERM obtains the minimax rate of (0n21/(2-9)) which interpolates between the slow rate Ö( and the fast rate (1/nn,, where n is the number of samples. This is similar to what we obtain by considering discrete uniform prior in our proof; see Appendix F for more details. We also remark that our proof of taking a prior over L, resembles improper learning and the v-central condition (Foster al., 2018; van Erven al., 2015), which also outputs a mixture of predictors obtain fast rates.
Randomized Exploration for GLBs. Somewhat orthogonal UCB-based approaches (including ours), another line of works for GLBs (Abeille and Lazaric, 2017; Dong et al., 2019; Janz et al., 2024; Kim et al., 2023; Kveton et al., 2020) focuses on randomized exploration-basee approaches. Kveton et al. (2020) proposed Thompson sampling and randomly perturbed history-based algorithms, both of which achieved a frequentist regret bound of (ddssTToo Tog K) for finite arm-set of size K (Kveton et al., 2020, Theorem 3 & 5). Recently, Janz et al. (2024) proposed EVILL, which linearly perturbs the (regularized) log- likeliioohodd loss that achieves a frequentist regret bound of (dd3/2 /TT/2//T/// n. (T)) for infinite arm-set (Janz. et al., 2024, Theorem 1). In all cases, the extra factor of v in the regret (due to posterior variance inflation) is shared across the randomized exploration-basee approaches to GLBs (Abeille and Lazaric, 2017: Dong et al., 2019; Janz et al., 2024; Kim et al., 2023; Kveton et al., 2020) and is known to be unavoidable for linear Thompson sampling (Hamidi and Bayati, 2020), An interesting question is whether the intuitions from our PAC-Bayesian-derived CS can be combined with aggressive variants of Thompson sampling (e.g.. Feel-Good Thompson Sampling ing of Li et al. (2024); Zhang (2022) or TS-UCB of Back and Farias (2023)) to improve randomized exploration for GLBs.
'satisfying some regularity conditions including Lipschitzness and boundedness Althoughh they considered fixed arm-set, their proof can be easily extended to time-varying sets, the only difference being the length of their warm-up period being dependent on the arm-set distribution.
20

---

B Future Works
Extending our CS (Theorem 3.1) to RKHS. One may wonder if the framework in this paper can be extended to infinite dimensions, in which the covariate a and unknown 0, are elements of some function space F. Indeed, by exploiting the inner product structure of GLMs, in the case where F= H2 is an RKHS with reproducing kernel & (Paulsen and Raghupathi, 2016), the inner product (ar, P..) can be replaced with (ar, 0-). In statistics literature, this is referred to the kernelized or functional GLM (Cawley et al., 2007; Müller and Stadtmüller, 2005), and in bandits literature, this has been extensively studied under the name kernelized bandits (Chowdhury and Gopalan, 2017; Srinivas et al., 2010) as an infiniteddimensional generalization of linear bandits. Mussi et al. (2024) recently posited the kernelized logistic bandit (e.g., T2 Bernoulli[faa with f X + [0, 1] satisfying f E H2) as an important open problem in the bandits and online learning community.
Extending our CS to RKHS, however, raises several issues, all related to the fact that the usual properties of finite-dimensionl spaces often fail in infinite dimensions (Bogachev, 1998; Da Prato and Zabczyk, 2014). For instance, it is well-known that there exists no translationinvaariant, locally finite, non-trivial Borel measure on infinite-dimession Banach space (Oxtoby, 1946, Theorem 1). Then, it is entirely unclear how to extend our current PAC-Bayesian proof of Theorem 3.1 infinite dimensions, as there is no uniform distribution or likelihood.
One promising alternate approach based the Gaussian Process has been recently proposed by Neiswanger and Ramdas (2021), where the authors proposed a CS to quantify the uncertainty of GPs. The important point is that the CS is statistically valid even when the prior is misspecified. Still, in our context, choosing the mean and covariance to obtain similar guarantees (c.g., better dependency on S" == ||0. ||x)) is non-trivial.
Optimality of CS Radius (Theorem 3.1). Another interesting question whether our CS radius in Theorem 3.1 is optimal. For general time-uniform estimation with i.i.d. samples, Duchi and Haque
(2024) recently showed an information-theoreee lower bound of Ω log log t on the estimation
error. It would be interesting use similar technique show information-theoreet lower bound on our CS radius for (self-concordant) GLMs, especially w.r.t. S.
Regret Lower Bound for GLBs. One important open question here is the optimality of our obtained regret bound. As discussed in the Logistic Bandits paragraph of Section 4, the leading term of our regret bound for logistic bandits is (locally) minimax optimal in d, T, K. (T) relative to the lower bound of Abeille et al. (2021). A closer look into their proof shows that their lower bound additionally scales as 1 1/S, indicating gap of S between the lower and upper bounds. To the best of our knowledge, there is no generic regret lower bound for self-concordant GLBs, and we suspect that a similar (TKx,(T)) lower bound holds. One could adapt the proof of Abeille et al. (2021) )) by modifying parts specific to Bernoulli (e.g., their relative entropy decomposition lemma (Lemma 6) relies on the fact that the reward distribution is Bernouli),, or come up with something new
Arm-Set Geometry-Dependent Regret Analyses of OFUGLB. For the prior OFUL-type algorithms (Abeille et al., 2021; Lee et al., 2024), the transient term is Rx(T) = Σi ((( [2: E (O), where X1(() is the set of detrimental arms with a large re- ward gap and little information (small conditional variance). Rx(T)) is adaptive to the arm-set geometry and can be completely independent of for certain arm geometries (Abeille et al., 2021, Proposition 2). For the warmup-base based algorithms (Faury et al., 2022; Mason ct al., 2022: Sawarni et al., 2024), the transient term always scale with which is not adaptive to the arm-set geometry.
Abeille al. (2021) showed that via an arm-set geometry- dependent analysis for UCB, such x-scaling transient term can be potentially avoided. However, as our regret analysis utilizes "implicit warmup", our transient term scales with (T)) which is not adaptive to the arm-set geometry. Thus, the natural question is whether a similar, arm-set geometry adaptive transient term is attainable for logistic bandits, while keeping the optimal poly(S)-free leading term. Currently, it seems that the regret decomposition used in our analysis is incompatible with the arm-set geometry-dependee and we leave to future work for obtaining both characteristics (poly (S) (S)-free leading term, arm-set gcometry-dependeee transient term) for logistic bandits and GLBs in general.
analysis,
21

---

The reason for being incompatible is as follows. Even when using our new CS (Theorem 3.1 in the regret analysis of Lee al. (2024), one still obtains OdS TT/K, (T) + (x)))), the same Lee et al. (2024). This is because in their proof Lemma 6, which involves deriving an ellipsoidal CS of the form || 0- IH,, (,), the covering argument introduces term in (6) that always scales as d52h log St previous self-concordance control (Abeille et al., 2021, Lemma 8), which gives an extra factor of S, and the use of anytime Freedman's 's incquality (Lee et al., 2024, Lemma 3), which results in multiplicative factor of 1/1 for some 1) S 1/28. In other words, attaining the best both worlds may require thinking of entirely new regret analysis technique.
z regardless of the likelihood-ratio CS radius. This is unavoidable due to the use of
Remark 4 (Detrimental arms for G.Bs.). In Abeille et al. (2021), one key component for allowing such transient term that is adaptive to arm-set geometry that there exists a Z C I such that
su, ji=)) < O; e.g,, for logistic bandits (μ(z) (1+e-)) Z (-50, 0j. For general p. we can define the set of detrimental arms as X- (t) == fo E (2r, (.) E 2n). Of course, the scaling of (T) depends on various factors, whose precise characterization for j's beyond the logistic function is left for future work.
Jointly Efficient and Optimal Algorithm for GLBs. Despite the statistical superiority of our CS (Theorem 3.1) and our regret bound (Theorem 4.1), is computationally heavy, especially the UCB maximization (line 6 of Algorithm 1). Our ellipsoidal CS is computationally efficient, but incurs additional factors of in the final regret bound. Then the question remains whether one could achieve order-wise the same regret guarantee for GLBs (e.g., poly(S))-free for logistic bandits) while significantly improving the computational efficiency. One may, for instance, draw inspiration from recent progress in designing computationally efficient & statistically optimal algorithms for (multinomial) logistic bandits via online Newton steps (Faury et al., 2022: Zhang and Sugiyama, 2023).
Other Applications. It would be interesting to see our new CS may lead to any improvements in algorithms for GLBs beyond OFU, e.g., cormmation-directe sampling (Kirschner and Krause, 2018; Russo and Van Roy, 2018). best arm identification in GLBs (Azizi et al., 2022; Jun et al., 2021; Kazerouni and Wein, 2021), and even sample-efficien RLHF (Das et al., 2024; Shi et al., 2024).
22

---

Missing Proofs from Table Bounding L,"s
C.1 GLMs that are Bounded by M
Recall that the GLM is bounded by M if for any x E X and r ~ p(1|ar, 0x), the following holds almost surely: |r - p((ar, 0.)l M co.
Then, we have that for any o,
W AA
+ 11(2,, 0) xs
r. 1 0/>||1/>||2
(1s u((a 0.)) + |u(( 0.)) - (x.x
(M + Ra 0, 071)
g(T)
(M 2S
g(T)
C.2 o-subGaussian GLMs
We first recall some definitions:
Definition C.1. random variable X E is o-subGaussian, if P([[X - E[X]| 2 t) S
2 eexp
Vt E R.
Definition C.2 (Definition 3 of Jin et al. (2019)). A random vector X E Rd is c-norm-subGaussian
ifP(() X [|]]] 2 1) S exx (-
12 VI E.
Here is the full statement: Proposition C.1. Suppose the GLM is o-subGaussian. Then, for any E (0, 1).
2 g(F)
38 )
P
3 1:21:11
RaS(( - 1) 2TTV (t 1) log
5.
(9)
Proof. Here, as max (2( 0i)1 S Ra. we have that
max BEe
(r. p((x,, 0)))
g(T)
max
(2((2,, 0)) pl(er, 0 0x))
1
Σ (Tx p ((x.. 0,)))
g(T) 00
g(T)
2
< 2R SRt -1) g(T)
y
g(T)
We now utilize subGaussian concentrations from Jin et al. (2019). First note that ys a martingale difference sequence adapted to E, and is norm-subGauussan with (conditional) variance 22 be given.
23

---

Then, by Corollary 7 of Jin et al. (2019), we have that
:-1 Σ
S 4 (t- log
2d
P
y
2 21-6; 6, AE
(10)
The exact constant 4x is not available in Jin al. (2019), all the constants are hidden under This not useful, especially for practitioners wanting to use the concentration directly. Thus, we tracked the constant from their Corollary 7, the details of which provide in Lemma C.1.
We then conclude by replacing 8 with 8/t² and applying union bound over t 2 1, which yields the Basel sum.
Lemma C.1 (Lemma of Jin et al. (2019); originally Lemma 5.5 of Vershynin (2010)). For any 1/p
c-norm-subbGassiaan random vector X, we have that suppen p 1/2 (I"I) S Vio.
Proof. This follows from Drute-force computation. First, we have that
X = / P|| fdl = / P|| 2 d0- di S 2p
/00 1
t2
1x=1exp
exp
20
= 2 = ppp
p
2
Let us denote f(p) == p-ppp1111 1/2 (|I])
1/p for p E N.
Then, using well-known properties of the Gamma function, we have that
f(2p) = o2 10
(2p) + à/2 ((p - 1)t) "p oo p-1 (v2pl)
and
2p-2 f(2p-1) = 222 2[क
(2p (2p-1)
(v=(22- 3)!!
20-1
= 12 1) 1) 3 33!!! क
20-1
where we define (-1)!! == 1.
Then, we have that
(3)
f(p)) < (V =2 <022,
where (i) follows from p! p". We also have that
1) opp 1) 1/2 (Vr(2p 1)P)
(6)
(1)) (VT(2p 1)) क (11))
oVT,
where (1) follows from (2p 3) < (2p - 1)", (di) follows from p > 2. and (iii) follows from the observations that for 2 e, f(z) (VTz) is decreasing" and f(1) / f(3) 1/3
2p-1
Finally, as 2/4 < VT, we have that suppen fp) S ViO.
C.3 Poisson Distribution
We have the following result for Poisson, which may be of independent interest (to our knowledge, this is the first explicit martingale concentration for Poisson in the GLM form):
Proposition C.2. For the Poisson distribution, we have that for any E (0, 1): when S > 1,
2 22 + 1)t²
L. < C(S)( 1- -
log
2 1 1 8,
A4 2 1,
(11)
38
10 log f(z)
V --lg -, V> e..
24

---

where C(S) = ] -e 2--20- (e +2 21og 2(1-2c $)
+ +See. When S
2² + 1)t
P 1 s C(S) 1) + 4log
21 - 8,
vt 2
(12)
38
where Č(S)= to (e + 45 + log(8 + 22 2
Proof. Proceeding similarly as in the previous subsection, we first have that
L 2Se +)+
Σ
y
(13)
where ys (r's 0.),, )ar, is the martingale difference sequence satisfying Elys E.] rs Ei ~ PPi(((r.. 0.)).
0 as
We now modify the proof of Corollary of Jin et al. (2019) (which is based upon the celebrated Cramér method) for the Poisson martingale vectors, details of which we provide here for completeness.
First, we consider the following MGF bound of the Poisson distribution whose proof is deferred to the end of this subsection:
Lemma C.2. Suppose that the random vector y is of the form y (r >)x for some fixed (1), Poi(A), and X > O. Then, for the Hermitian dilation (Tropp, 2015, Definition 2.1.5) of y. Y =
0 y
we have that By 3 exxp (F(O, A)) la-1 for 10| 4.2 where F(O, X)
X + log (2 + log + +
We also recall the Lieb's trace inequality:
Theorem C.3 (Theorem 6 of Lieb (1973)). Let A be a fixed symmetric matrix, and let Y be random symmetric matrix. Then,
Eir(exp(A A + Y)) < trexp( A + log Be
(14)
Now let 0 < < 1 be fixed, and let us denote X == 0.) and E.1-] = E|- for s S t 1. We
start by noting that
1-1 Σ F(0,
E exee
+0 Dr.
E
E
trexp
102 Σ
F(0, + Er.
< E
tr exp
88 1241
F(0, + > Y, + log E- (
(Theorem C.3)
s=1
#=1
1-2 Y, + (0,,
< E
tr exp
8 18+1
F(0,A.) + Σ
#=1
==1
(Lemma C.2, A 3 B = e C+A CBCB
2
1-2 F(0, + DY.
< E
txexp
I
==1
25

---

.... S trexp((0 = 1d
Thus, for any p 2 0.
P
7
4
F(0, 2a)
P
Σ
Y
2 8
F(O, As) +
Cx Y, is rank-2 matrix with eigenvalues + 1|E. Uo (2)
2P
Amax
Σ Y,
8
F(0, xx)
P
(Y, are symmetric)
0
F(O, F(0.)))+)) o
2P
Amax
exp
8 2 Y,
z exp
0 Σ
1-1 Y. 8 E
8² x ((0,A)))))
< 2P
trexp
2 exp
s=1
< 2e PPE Ir trexp
-02 ((0, Y
(Markov's inequality)
$ 2(d + (ld++1)e-
(Lemma C.2)
Finally, by reparametrizing, we have that for any 8 E (0, 1),
8 Σ F(O, Ao) + log 2d 1
1
P
Σ
y
inf (E(1.1/2)
/ 1
(15)
0
- - x) for 8 > 0.
where we recall that F(0, A) = 00 + log(20) + log
5, which guaranteed to be positive. Noting that First, when > 1. let us choose A 1 5-
A₂ = 0.) S e, we have
log(2e 1 e SS log 2(1 5) (5-e-s) +log(1 -e S) -)
F
8 ,, s e
2
2
e
Thus, the RHS of Eqn. (15)
(1-2e 2e (E + 2S + 2 log
2(1 2c
2(d 1)
1)+ +
1 - log
(16)
4
For the case $ < 1, choosing
1 the RHS becomes
4.
s + 4S + log(8 + 20=5)
2(d + 1) 14-1)
(t
(17)
16
Finally, we conclude by parametrizing as 8/12, applying union bound over 2 1, and using the Basel sum.
D
26

---

Proof of Lemma C.2. We first have that
Re OY
(4)
18+1
AEY 2p (2p)! 1
I0+1
E y (2p)
2p
Ta+1
edlllll
e
Oller
Idt1
2
p=1
I8
1011
A
I4+1,
where (+) follows from the observation that EY =0. We now recall a concentration result for Poisson distribution:
Lemma C.3 (Theorem of the note by C. Canonne). P((rr yl 2 x)) S 2e 2(A
Then, we have that
Ele 0||r [l]l-~1]=
/
P(e k)dk
(dk is the Lebesgue measure)
P(el011r-11 2 k)dk
1 +
2
e
21A dk
(Lemma C.3)
2
2(1 +10 du
2/0|
e
2 a(A-1) +10 du +
e 2(ato +10 du
2|0|
(
12-1013u du Acloia
((dtt) 2 2u u for A)
2
11-1012 de 011
1/4
10
+ x1 ) 2 10
c
F(O, A) A 1 log(2(0)) + log
exp
27

---

D Proof of Theorem 3.2 Ellipsoidal Confidence Sequence
First, similarly to prior works logistic bandits (Abeille al., 2021; Lee al., 2024), let define the following quantities:
G.(0, v) = g(T) Σ a. v.),,,), (,(0 == [[( (1- v) (1x,, 0 v(v 0))) dv.
(We will later come back to these quantities in the regret analysis.)
Then, by Taylor's 's theorem with integral remainder and first-order optimality condition for convex constrained optimization" ", we have that for any À z 0,
O, 1 (0.00)
B.(5)² 2 () (..
V L+ 0.), 0
0.)
+
>
0,
2
- 1 0,
(0,
0
1
(0,00))
We conclude by using the self-concordance control for G (Abeille et al., 2021, Lemma 8), which we recall here:
Lemma D.1 (A slight extension of Lemma 8 of Abeille et al. (2021)), Let p be increasing (j 2 0, which is basically Assumption 3) and self-concordant with constant R2 (as in Assumption 4). Let Z C T. be bounded. Then, the following holds for any E 2:
f.0- (0--0)/(2 + 0(22 =1))du 2 RS 21 22
This then implies that (0, Z 2-28H V2L,
L'Let e be convex and f: θ + R be convex and differentiable. Then, 0* arg m f(0) if and only if (V)(0'), -0)--))- 00200 0, Ae E O (Boyd and Vandenberghe, 2004, Section 4.2.3).
28

---

E Proof of Theorem 4.1 - Regret Bound of OFUGLB
Let us denote pe(+) pa and [a, b] {a, a + 1,.... ,63 for two integers b. We recall the following quantities:
R = max I (a, 0.))l, RØ == max (1 0)). ac =EX,0Ee
(18)
mex
E.1 Key Ideas of the Proof
We will first expand upon the proof sketch provided in Section 4.1 of the main text. Recall the UCB strategy: (I,, 0t) <- arg max (z. 0)
Why Prior Proof Technique Fails. We first show that even though we have tight CS (Theo- rem 3.1), naïvely combining it with existing regret analyses of logistic bandits (Abeille et al., 2021; Lee al., 2024) still results in an extra factor of the leading term. To see this, let us first recall the existing analyses.
The prior proof starts by bounding the regret by Et= (it, (0.), 0, 0_) (which follows from optimism and first-order Taylor expansion), plus a lower-order term that is easy to control. The first term becomes the leading regret we will now focus on. Using the Cauchy-Schwartz inequality w.r.t. each summand
the (regularized) Hessian (.().) AI (0.) AI > bounded as
jux (0.) O2 - 0.) - j4 (0.) 2 H.(0.) - (10²- -
-0:0--1ll (..) + 100, -Oell
The prior proof then uses Taylor expansion (again) and self-concordant control (Abeille et al., 2021, Lemma 8) to obtain |10- - 0el (O.) = o (5)) from the likelihood-baase confidence set (,)))) - (.)) s (r()) which introduces a factor of S. This then leads to
2 H.(0.)-
Σ (..0)) - xn, 0.) (4)35530 (B)
(.)
olliptical potential lemma (Abbasi- Yadaiii al., 2011)
resulting in regret whose leading term is not poly(S)-free.
Towards Our Approach. To obtain a poly the ceff-concordance lemma (Abeille et al., 2021, Lemma 8). To do this, proof begins by obtaining an elliptical CS w.r.t. (O,), derived from the first-order Taylor expansion of C-(-) Oz. With this, we have that ||0, - 0, ( = (8)) (Lemma E.6), avoiding the extra S compared to the prior proof that derives elliptical CS w.r.t H..).).
leading term in the regret, we maximally avoid
However, the main difficulty of the proof is that (.,) is not in suitable form for elliptical potential arguments. To see this clearly, consider the following natural optimistic upper-bound the instantaneous regret:
p((zt,,, - (((0.) S (i,))) (0.))
(Optimism)
= (0.) - (0.) - (r.))) (O.) S (0,) me()))l
I (r. ([ 02 0.) lower order terms,
(Taylor's theorem)
arg maxoec, (p)(0) ur (0.) One can then apply the aforementioned Cauchy-Schwarz where 02 arg w.r.t. G.) to obtain
de (Z) 0f 0.1 (..) |x,
( [2: 0. 0 a. S (i,(0.)77 ||: lla, !(0.)
This successfully avoids using previous self-concordant control (Abeille al., 2021, Lemma 8), and thus seemingly getting closer to obtaining poly (S) regret. Omitting details, the final step is
29

---

to sum the above over E [T] and apply the elliptical potential lemma (EPL; Abbasi- Yadkori et al. (2011)). EPL is applicable only when (0,) can be written as XI Ex= Mi (0,)ar, for some > 0. However, as (..).) = E E( 0(.r,,0))ar.. applicable due to the explicit dependency on 0., not on (0=)) The most challenging part of our proof development is making EPL applicable to the summation resulting from some decomposition of the (instantaneous) regret while avoiding extra S-dependencies.
for some scalar function É., the EPL. is not
I].
Our Approach. The key insight is that if we could designate "worst-case" O, for each time step 8 such that G, (,) = AT - (0
((0,)),z3 2 =: Qt. then we can perform the following:
0.31 ie (m), 0% 0.11 S ju, (.)) - + (0.) (0.)) (z,, 0 0.)l
We can now apply the EPL when summing over E [T]. thanks to the form of Q.. The second term turns out to be a lower order term via our new self-concordant control that doesn't I give additional S-dependency (Lemma E.3).
where the first term is now be bounded by O (ite (.)
We note that this analogous to the analysis of Logistic-UCB-2 in Faury al. (2020), where similar difficulty arose because their improved bonus 6t2 depends on the current estimate of the parameter as well (see their Lemma 4). They circumvent this issue by explicitly modifying the UCB algorithm to incorporate additional constraints on the "admissible log-odds," which leads to a computationally inefficient algorithm. Indeed, initially, we took a similar approach by either using confidence set defined as an intersection over all the confidence sets used so far, or by using an additional constraint set W; as defined in Logistic-UCB-2 of Faury et al. (2020). However, either approach significantly increases the computational complexity.
We later discovered that we could resolve the issue without changing the confidence set through an alternate analysis, which is the current proof. Specifically, we consider the following decomposition of the instantaneous regret:
(((ar,,, 0-)) (0.) S (0.) - (p.(0.) - 2/xe(1i)) - pee (e((0cc))l
where we define (b(1), v1) == arg maxbeit.T]ee..m (0) - 14 (O)) That is, we are bounding the instantaneous regret by how large the difference be from the current confidence set and how large the difference can be from the future confidence sets. With this, we can then define 0, := arg minlge C, (O), which satisfies the aforementioned desired property. This is our main technical novelty that allows for us to bypass all the aforementioned difficulties.
Among the omitted details, we consider a slightly more intricate regret decomposition by considering timesteps in which the "warmup conditions" are satisfied and the remaining term, and we derive novel self- ceffoconcode lemma that bounds the difference of j with that of n's times Rg (Lemma E.3) that does not incur additional S-dependencies. We then utilize the elliptical potential count lemma (EPCL; Gales et al. (2022)) for the terms that do not satisfy such conditions, and the remaining terms follow the reasoning as detailed above.
E.2
Main Proof
We defer the statements and proofs of the supporting lemmas to Appendix E.3, although we will provide relevant context when using those lemmas for the proof's duration. We first define the following crucial quantities that we have discussed in the proof sketch: for X > 0 to be chosen later,
0, = arg min (0), (b(t),
== arg max
(0) -me(O))
(19)
oEUsCIL. Co
DE(C
H. 2g(T)A1 (..0.) :=:=20(7)
Σ 2
(20)
and
v.. = J (1 r) (0 v(w-0) - du, G.(0,)) -
1'
Σ
1-1
ā, (,,0, (21)
g(7)
30

---

0, in the union of future confidence sets, combined with the "warmup conditions" allows for the elliptical potential lemma (EPL; Lemma E.2) and elliptical potential count lemma (EPCL; Lemma E.1) to be directly applicable, avoiding dependencies (Sl and x. in the leading term; refer to the expanded proof sketch above for a more detailed explanation of the intuition.
Throughout, let us assume that the event {vt 2 1, 0, E J holds, which is with probability at least 1- by Theorem 3.1.
Regret Decomposition. Define the set of timesteps satisfying the "warmup conditions".
21) v (|leolly-221) IT = (iEm: (IValo))a) A.
(22)
Then we have the following regret decomposition:
Reg(T) = Σ
(u((ar,,: 0.)) - (l(((((,, 0.))) +
E
Eulfare; 0.)) - 0.))}
LEIT
EEIr
Regz(T)
< 1R + (T)
< 2R Σ
1
1
+ 2R
Σ NE(T]
1
|| 2 + Regz (T)
SE[T]
H,
(Definition of Ir)
4d
Rí
log
1+ 2)g(T) log2
+ +log
(1+ (g((T) log
Reg.(T).
log 2
(EPCL (Lemma E.1))
We now focus on bounding the last term:
Regz(T) = Σ { (e.. (0.) - -m( + Σ (m(0.) (ue(0.)-10 -m((0))
IEIT
LEI,
(+)(+) == ul :),, (e) == μa (Zx))))))
(u(0))) -m.(0)) + Σ
Me ( me((.))
1EI7
(optimism line of Algorithm 1)
2 2
max max (i(0) - -4e (+))
be(t,]] DECs
[EIT
2
Σ
pe((s)) - (0(0)
(Eqn. (19))
Using Taylor's theorem with integral remainder form, we have that for of Ir.
pe(v)) -Me(Oce))
(ueler)
= ((000 -o(s)) (ni@has) (pe(ve) =))d
$ (Q(e)))))) (Be. - + (20, - @uce)s ((' (1 11-w) v) jis (Øeco + u(u, - -Owe)) de (triangle inequality, reparametrization)
- <pe(Ou)))) (0..V:-0bc)))) -bccoil + R. -
0o(o)) [ (1 (1-e) (Dec) + v(vr - @m(e)) dv
=āaco
(Assumption 4)
31

---

S (e(( (oer vr Ouce)) pur(0.) - (ir(Occ))) (or,ee -
+ Ro U 0uco)) (āsce) U1)
S (0.) ||ee lanco (1)) ||le 0oco) (Osss))))))
2A.
+ (((())) - jus (((occ)) |10ell (000000 |ss Oace)
Bc
+ Rs - Obces
abce) abco) (Doc)) vs) || (2)-
Gaeo (Bace) (4)
C
CCauchy-Schwane incquality)
where G is as defined Eqn. (21). As one will see soon, E, Ae is the leading term, and >, - Ct) is the transient term.
We bound each sum separately:
Bounding Ee Ar-
Σ A = Σ jur( (0:) (zoll |re - @ocos Beeplaww Baco (uwn
IETT
TTTT
S V 4XS + (0)
Σ (0,)
|| (axc)))))
(ur E Cose), Lemma E.6 (i))
I&IT
S 4XS2 + (8}2
Σ (r().))
Σ (e.) | (an (va))
UEIr
EgIr
Schwartz inequality)
S 44X82 (8)2
Σ (o.(
2g(T))
Σ (o().) |
(Lemma E.5)
V
NETT
2gTT
$ 22)(T) (4X8² + BT(()²)
Σ (..)
Σ
min [, jie (O.) | | 1l
EEIT
:E(T
(Definition of Ir))
Note that now, H, is of the form such that we can use the EPL with / (0,)a:
Σ A s 2/ dg(7) (8)
1 dA
RAT
Σ (L.).))
(EPL (Lemma E.2))
EEIT
LIIT
R₂T
$ // (g()) + (7-()))) (1
Σ (0.) + Σ (pr((0.) (0.))
dd
(E(T)]
1EIT
(N),(+) := (((
1 R&T
= 2/ d (8)
+ Σ (0, - f4,, (0.)).
Kr (T)
E6I
The last term in the square root is bounded as follows:
Σ (pr(0.)) (0.))
Σ (ir((.) (0)(0.) + Σ (ir(0.)) (0))
EEIT
EgIT
EgIT
32

---

Rs
Σ ( mx(00)] +
Σ
(mr(O.) (o.
1gTT
(Lemma E.3)
R
[u((e)) - vc((0))
+ Σ
(0) vo(O.))
IIIT
BKIr
I R
Σ pu(vi) - ( Σ
(e(O.) - me(Oi) + Regz(T)
1gTT
1
< 4R,
Σ
(e(vi)-Ho(00 - Hm((0co)
(Definition of (v,, b(t))
Bounding E, By.
Σ Br = Σ (0.) - jin (0(())) | (000))
p. - Ooco)
Gaey (Onc)))))
14IT
Tg
I 44x52 (T(
Σ
(i((O)) (1((0))))) ||a0 l anb (m)))
(ui E Cu(e), Lemma E,6 (i))
< R& R 4A8" + (r)
(rr(O)) mc(Ooto))
||ee llalll ( (8(c)))4)) (Lemmaa E.3)
We then inevitably introduce a (T) dependency to use elliptical potential arguments w.r.t. Vy:
Σ Br S R4
+ (
(r)) (g(T)
Σ
(.(O.) 14x (O(())))) |
1EZT
(Lemma E.4, 2 t)
< RA
2g(T) Σ
(ul(es) - ue (m))) ||<:||
IEIT
(Definition of v (Eqn. (19)))
< <RR, + +82(6))VoOT)
Σ
|
ET
(u, Ōuce E Co(e). Lemma E.6 (ii)
< (ARARA + + Σ AE[T]
min {1, 11,112ell }
(Definition of Ir)
T
< (TRAAA + (3((8)) log 1+ (ddg(T)s(T)))
(EPL (Lemma E.2))
Bounding E. Cr. We proceed similarly as bounding E, By:
Σ S. s Rg 4AS2 + Br())
Σ
(uce)(O(t)) vi) || || || ((
1EIT
EEIT
(vr E Co(t). Lemma E.6 (i))
< (RBRgoT))(()) 4X52 + (0)
x 1l li
(Lemma E.4, b(t) 2 t)
EgT
< <RaBaol))s(T) 4452 + (T)
Σ
min (1, ||
(Definition of Ir)
[E|T]
T
<248, 3 log
1+ 2dg(T)x<(T}
(EPL (Lemma E.2))
33

---

Wrapping Up. Let us choose À = 1 and let us denote A S B A < cB for some absolute
constant e 0. Then, combining everything, we have:
Σ
po(vi) (1(()()))
S Σ Act Σ BB+ Σc.
1II
tIIr
tEIr
R&ST
T
2 /r(0)/ (g((T) log
log 1+
+ R. Σ
- -m:()c))))
d
(T)
19IT
V log (1+
ST
dR,
dg(())<(T))
as the upper bound for Ee Ce is asymptotically negligible compared to that of E, Br.
This is of the form X I A/B + R.X + C with == Eigir (u(())) - ue (0cco) which then
implies X S AVB+ AV C' thanks to elementary polynomial inequality (Abeille et al., 2021, Proposition 7). We then conclude by combining the above inequality with the regret decomposition done at the beginning.
E.3 Supporting Lemmas
The following are the elliptical potential arguments, which we state without proof: Lemma E.1 (Elliptical Potential Count Lemma; E2 For X, L O, let "1... Ør (X)
be sequence of vectors, V. AI + E:= 2, and let us define the following: Hr
{ E [T] | > J Then, we have that
2d
X2
Hrl log + L2) log 1+
(23)
A Alg + L2)
Lemma E.2 (Elliptical Potential Lemma; !) Let 20, vectors and V == =-I Ex1 x.20.. Then, we have that
or E (X) be a sequence of
( 1+
X²I
Σ min 11, [e < 2d
(24)
d.
The following a "self- boif-bounding" property of self-concordant function: Lemma E.3. For 0, Rd. (0) (=)) s Relm((0) me()))
Proof. This follows from direct computation:
(0) (v((1)] (x,,, 0 v) L' pelu+ v 10--01 v)de
< (or, 0 - wil /'' litlu+ + v(0- - (v)]-(] de
< R2 (m,, 0 - will /'' lit(l + v(0 [0) du
(Assumption 4)
12This generalization Exercise 19.3 of Lattimore and Szepesvári (2020), presented (in parallel) at Lemma Gales et al. (2022) and Lemma Kim et al. (2022). Lemma 11 of Abbasi- Yadkori et al. (2011).
34

---

Rs (2t, 0 -vv) L. iuslv + v(0
(m is convex, and thus ji m" 2 0)
R& (x( me())
This self-concordant result distinct from the original self-concordance control lemma (Faury et al., 2020, Lemma 9) and does not incur any dependency on S. We also remark that the above self-bounding lemma has been independently proven and used for regret analyses of GLBs two concurrent works (Janz al., 2024, Claim 14) (Liu et al., 2024, Lemma 31).
The following properties are crucial in allowing for the application of EP(C)L:
Lemma E.4. for any 0, v E Rd, 2x(T) S ( v) S
Ru 2
and thus, 2g(F)<(T) V 3 G.(0, v).
Proof. Follows from straightforward computation.
In the following two lemmas, b(t) is as defined in Eqn. (19).
Lemma E.5. Go(e) (0x(), v.) ž zolr H..
Proof. For each 8 S b(L).
(+) ã. (0()),, u1) = 1 (1jr) (Oocer + olu: - -mxx)) du 2 (..) ((1--))o== 1
2 (0.) (0.);
where (x) follows from the observations that vi, ivco E Coco) and Csce) is convex. We then conclude by noting that b(t) 2 t, and thus Hb()) ł H.. Lemma E. For any t Z and 0, v Cosey, we have the following:
(i) v 0nce)
( I +
(it) pc(v)= (c(0)] 2R + (T)2) k(T)
Proof. (i) follows from Taylor's theorem with integral remainder, first-order condition for convex constrained optimization (see footnote 10 in Appendix D), and the fact that Coie) S (S)::
(V (ooo)) @uco) | 0oco) 2
(6) Lu()(() (..)
Goce M))
20
p Ooce) (men)(
-2522
(ii) follows from (i) and similar arguments:
(2 0) S i.(0 + ())do
(v(v) (0)
} || 00
$ Rí -|00- ||-- @oce) (uen)(ren) + 110
Toce) lla (sco,
Mauchy-Schwarce & triangle incqualities)
$2R 2 (1152 + Br())) K x(T) || v-1
((i), Lemma E.4)
600
s 2Rp 2 - x(T) |,
(b(t) >
35

---

F Alternate CS via Discrete Uniform Prior and Covering Argument
In this Appendix, instead of the PAC-Bayes with a continuous uniform prior/posterior as in the main text, we explore an alternate derivation of CS using discrete uniform prior. This is supplementary discussion for the "Fast Rates in Statistical Learning" paragraph in Appendix A.
We present the alternate CS, which is strictly looser than our Theorem 3.1 but more "elementary":
Theorem F.1 (Slightly Looser, Unified CS for GLMs). Let L == maxoge [Vr(0))12 be the Lipsehitz constant of Ci(-) that may depend on (2)x:r)))== Then, we have P[at 2 0. & (r)) S 6, where
Be(8)² log
π 2t2
inf
dlog
58 + cLo } log
x²t² + d V 5SL,) + 1,
66
cE(0,55]
68
where the last inequality follows from the choice 55 A E
Proof.
Consider p = U((OO)iE(N))) where the 0, 's will be determined later. In that case, we have:
log Eaup [M, (0.) ) + log Ee (exp (-C,
(0) log
exp cxp (-C
N
1
(..) + log
max exp (-C, (E[N]
N
1 N
L.,)) - min (.(O,) + log
(25)
iE[N]
From the proof of Lemma 3.1, one can see that (0)( = where E is w.r.t. the randomness of the sequential data (i.e., of (.)-).. Then, by Markov's 's inequality, for any 5 E (0, 1),
N
P M(())) 2
Vi E (N),
(26)
8 N
where again, is w.r.t. the randomness of (-))). Then, have that
Ea [Mc
Σ Mc(O.) 2
1 8
SP
max M(
2
N
N
iE(N
8
dE[N]
Σ
IP
Mc)),)
N
N
(union bound)
8
KE [N]
5
8.
(Eqn. (26))
N
N[[N]
Combining this with Eqn. (25), we have that
.
PP (0.) min (0,) S log 2 1 - 5,
[E(N]
By reparametrizing 5 as and taking the union bound over / 2 1, we have that by the Basel sum,
2212
P (
min (,))) 2 log
log
26
(27)
[E[N]
66
36

---

Thus, the following holds with probability at least 1 - 8: for all 2 1,
T²
L.(O.) min (0) 0-8
S log
+ log N + min (r():)
min Lx(0)
66
*E[N]
2
log
log N Ta min
|0: kE[N]
0.11
(0. arg mingee ())
66
where recall that L, is the Lipschitz constant of Le(-).
We choose {0:} to be a e-net of à for E (0,55), Then, min |0:
0. 8.11 S by definition,
and as θ _ (S), N <
(Vershynin, 2018, Corollary 4.2.13). Combining everything and taking mi,5c gives the desired statement.
58
37

---

G Deferred Experimental Details and Results from Section 5
G.1 Implementation Details
For time-varying arm-sets, the randomness of the arm-sets is shared across all the algorithms, i.e., each time-step f, all the algorithms see the same arm-set. Thus, the only randomness is from the reward distributions. Whenever applicable, we utilize the Sequential Least SQuares Programming (SLSQP; Kraft (1988)) implemented in SeiPy (Virtanen al., 2020) for computing the norm- constrained MLE. This minimizes the effect of optimization errors whenever possible, allowing us compare the algorithms clearly from statistical perspective. For OFUGLB, EMK, RS-GLinCB, and OFULog+, SLSQP is utiliized to compute the UCB index as well. We use the same implementation of Cada-OFU-ECOLOO and RS-GLinCB as in the publicly available GitHub repository of Faury et al. (2022) 14 and Sawarni et al. (2024) 1, respectively. As mentioned in the main text, we utilize the exact theoretical hyperparameters for RS-GLinCB as provided Algorithm of Sawarni et al. (2024).
G.2 Additional Results for Logistic Bandits with Fixed Arm-Set
ORUGLB
OFUGLB-e
EMK
EVILL
RS-GLinC8
OFULog+
ada-OFU-ECOLog
250
5-4
175
5
80
S
40
5 1-10
150
70-
35-
Regretploss
125
50
30
50
25
100
20
200
30
15
50
20
10
50
10
25000
5000
7500
10000
2500
5000
7500
10000
0-
2500
5000
7500
10000
2500
5000
7300
10000
70-
40
30-
35
25
30
25
20
19
20
15
Magn
20
15
19
10
5-
0
2500
5000
7500
30000
2500
5000
7500
19000
2500
5000
7500
19000
01
2500)
500
7500
10000
3.5
5.0
3.00
25
2
0.0
0-
2.0
1.5
0
5.0
7.5
0.1
-30
30
Figure Fixed arm-set. (First row) Regret plots of all considered algorithms. (Second row) Magnified regret plots. (Third row) Confidence set plots at the final time t = 10000 when applicable. Each column represents a different logistic bandit instance for S (4, 6, 8, 10).
Results and Discussions. The results shown in Figure 2. There are some common characteristics compared to the plots for time-varying arm-sets (Figure in the main text). There is still a discrepancy between the tightness of the CSs and the actual regret for OFULog+ vs. OFUGLB-e, and oS-GLinCB still performs the worst. Also, OFUGLE, EMK, and EVILL are still the best-performing algorithms, at least eventually. Let us now highlight some key qualitative differences from time-varying arm-set plots as well as relevant discussions.
First, the regret curves seem linearly increasing overall, especially S (8, 10). In our settings, = 10000 is still a transient phase of all the algorithms and, thus, yet to reach the asymptotic
" "nttpe://github.
httppp///shhhaaaocom/////usttrtp bandit
"https://githuu wwtp:/ccc//nnrrrieeeee wtwpe/jaaaarra/aaaiiiiaaae latpaandddiiimimimeeeeeeee Litett_mmmmmeeddd_e_ee_ee_ hatpaaadddt_tnnitttetoeaettttttt Adaptivity
38

---

regime. To see the logarithmic-loode lookiing regret curve and to numerically compare the "numerical asymptotic regret" of the algorithms, we plan to run the experiments for much longer timesteps, e.g..
T= 50000.
Second, for = 10, it seems that O is the best performing algorithm. We suspect that this is because the OFUGLB-e happens to exploit a "good" direction in the beginning, and In other words, we believe that if the experiments are run with much more iterations, then the end, due to its design, OFUGLB-e will have to explore other unexplored directions, causing an increase in the regret. Indeed, if one takes close look at S E {6, 8). note that there is phase at which OFUGLB- seems to perform the best in the beginning, but in the end its regret increases well beyond other well perforrmng baselines: OFUGLB, EMK, and EVILL.
Remark 5. Although our current implementation always uses SLSQP for all the optimization proce- dures (for MLE and UCB index computations), when the arm-set is fixed, the overall implementations of all the algorithms can be made more computationally efficient. One approach is to utilize the iterative reweighted least squares (IRLS; Wolke and Schwetlick ( (1988)) and keep track of the number of pulls of each arm vector, which possible as the arm-set is fixed); see Section 3.3 of Kveton et al. (2020) and the original implementation" 16 of EVILL using IRLS.
G.3 Additional Results for Logistic Bandits with [Acl = 10, with Some Updates
Here, provide additional results for |A,| 10, for both vime-ig and fixed arm-sets. These results were obtained as a test run of the significantly refactored codes in our GitHub repository (see the commits in Jan 2025). Compared to the experimental details presented far, there are two main updates.
Notable Updates. One is that we utilize the exact theoretical hyperparameters for EVILL as provided in Appendix E of Janz al. (2024). To be faithful to the theoretical results presented in Janz et al. (2024), for the fixed arm-set setting, we implement the warm-up phase of EVILL via the G-optimal design (Pukelsheim, 2006), which is in turn implemented using Wolle iterations (Frank and Wolfe, 1956); see Appendix B of Janz et al. (2024) and references therein for more discussions. Another is that for the implementation of EMK (Emmenegger et al., 2023), we utilize the Vovk-Azoury- -armmuhh forecaster type regularizer due to AIOLI of Jézéquel et al. (2020) instead of the log- pog-partition-- based regularizer as suggested by Emmenegger et al. (2023).
Results and Discussions. The results are shown in Figure and There are several notable observations to be made. One is that with the theoretical hyperparameter, EVILL performs worst or second-worst, suggesting that despite its practical efficacy (Chapelle and Li, 2011; Russo et al., 2018), there is still big theory-practice gap, at least for logistic bandits. Second observation is that our OFUGLB performs worse than EMK. We believe this is due to the change in the arm set size, [Ate]. Still, the trend suggests that 8 gets larger, our OFUGLB may perform better than EMK. This is expected, considering how our theories focus on removing the S-dependency, which is significant only when S is large. We should, however, emphasize that Emmenegger et al. (2023) does not provide right theoretical (regret) guarantee for EMK, while ours do. Also, in the time-varying arm-set setting, our OFUGLB's CS is tighter than EMK's. s. Lastly, in the fixed arm-set setting, OFUGLB-e e behaves quite unstably as S increases. We believe this is due to our theoretical choice of X (5*(+)
decaying
with S, possibly making V (O.) + Al ill- ill-conditioned. In practice one could tune À for a good and stable performance.
39

---

EMK
RS GLinCB
EVILL
ada OFU ECOLog
OFUGLB
OFUGLB
OFULog+
500
$=4.0
6.6.0
5= 8.0
200
5 10.0
350
400
Regietplets
200
250
200
350
75-
23-
2500
5000
7500
10000
2500
7500
10000
5200
7500
10000
2500
5000
7500
10000
25
20.0
30-
17.5
15
Magnifted
1.5
7500
10000
7500
Conficence sets
Figure 3: Time-varying arm-sets with [Ag] = 10.
ade OFUELCLULOO
OFULog+
EVILL
RS AS-GGinCB
EMK
OFUGLB-e
OFUGLB
500
4.0
500
S 6.0
5 8.0
5.00
5 10.0
40D
400
400
400
Regret plets
200
300
300
300
2500
5000
7500
13000
2500
5000
7520
10000
5000
7500
10000
25000
5000
7500
10000
600
40-
Magnifeed pegret
50
30-
50-
20-
10
7500
10000
2500
7500
Confidence sets
Figure 4: Fixed arm-set with |A| = 10.
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction accurately reflect the paper's contributions and scope by introducing the new CS for GLMs and applying it to GLBs to obtaín state-of-the-art regrets
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
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 of the work performed by the authors?
Answer: [Yes]
Justification:
Several limitations are posited the main text, as well as Appendix
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 a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn 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 on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in 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.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
41

---

Answer: [Yes]
Justification: All the assumptions are detailed the main text, and the proofs for all the statements are provided either in the main text or in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' 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 encouraged 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 be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results 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 not)?
Question:
Answer: [Yes]
Justification: The experiments are simple enough to be reproduced, and we additionally present the GitHub repository containing the codes for reproducing the experiments.
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 be 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 to 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, it may be necessary to 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, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS 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 it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
42

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
See our GitHub repository:
https://github. cow.:o/ci//ciiiihheeeeeeee
Logistic_bandit
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / ctttpp..cc/ubbiceec gwwp//ui//////eeee//oo
/eeddddee//oobnbiiiicc CooeeSummis ssi iesionPolicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments 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 is permitted.
6. Experimental Setting/Details
Question: 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?
Answer: [Yes]
Justification: This is detailed in the experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The experiments are averaged over 10 runs, and the standard deviations are marked in the regret plots (Figure 1).
Guidelines:
The answer NA means that the paper does not include experiments.
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).
43

---

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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It 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 figures symmetric error bars that would yield results that are out range (c.g. negative emror 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 on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification:
The experiments are very simple and can be run on normal CPUs.
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, 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 in the paper (e.g., preliminary or failed experiments that NeurIPS Code of Ethics https: httpr//eerppp.eeeeee/eee/ee cc htc//pulcc/tttiiieeeeeeeeeeeeeee httppp/blc//hhiiicuueeeeeeeeeeee
didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: This is purely theoretical.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or 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: [NA]
Justification:
This is purely thcoretical and thus have no negative impact.
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 no societal 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.
44

---

The conference expects that many papers will be foundational research and not tied 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, it is not needed to point out that a 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 as 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 or unintentional) misuse of the technology.
If there 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 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 paper is purely theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a 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 to 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 we 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: We cite Abeille et al. (2021); Faury et al. (2022); Janz et al. (2024); Lee et al. (2024); Sawarni al. (2024), who has public GitHub repository for the experimental setting that we follow in our paper.
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.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thwode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
45

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is 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 is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part 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. Crowdsoureing 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: No humans were involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 the main paper.
According the NeurIPS Code of Ethics, 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: no humans involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 we expect authors to adhere to 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.
46


Reviews:
[{"review_id": "OyODLVy71f", "reviewer": "Reviewer_TTTd", "summary": "This work considers generalized linear models where the distribution of observations, conditionally on a context vector $x$ and an unknown parameter $\\theta^\\star$, are generated from a (known) exponential family of distribution. Their main contribution is a new confidence sequence for online estimates of $\\theta^\\star$, leading to improved regret in the context of Generalized Linear Bandits when used to calibrate a UCB algorithm corresponding to the model for the observations.", "questions": "* The main novel arguments seem to be located in l.153-167. My understanding of the results (please correct me) is that the goal is to use Lemma 3.3 with a nice choice of prior/posterior distributions such as to make the KL divergence as small as possible. However, in Eq. (9) l.159 I fail to see why $P_t$ is a valid posterior given the prior and empirical data. Again, I am not a specialist of the PAC-Bayes literature so I'm sorry if the answer is obvious.\n\n* In the bandit part, bounds are established for Self-Concordant GLM. Does the constant $R$ need to be known by the algorithm or is it just involved in the analysis?\n\n* Can you elaborate on the connection with Theorem 3 of Foster et al. on Section 3.2?", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written and easy to follow, and the presentation of the technical arguments is very pedagogical. The literature review seems extensive, and the authors carefully separated the literature that inspired the design of the confidence sequence and the literature related to GLM and bandits. The results are also well presented, with explicit constants so that it is not difficult to reproduce the results from the paper. In that regard, I appreciated how the authors cared about facilitating future implementation of their approach. I also appreciated the precise derivations proposed for some specific families of distributions, that are good illustrations of the results.", "weaknesses": "I am not very familiar with a large part of the literature invoked by the authors, basically the literature presented in Section 3.3. Hence, it is quite difficult for me to assess the technical contribution of the paper (not a weakness, but I'm using this space to say it). For a non-expert reader, Section 3.2 is a bit hard to follow. In particular, I did not see the connection between the result and Theorem 3 of Foster et al. (2018).\n\nRegarding the bandit part, it might be beneficial to extend the \"proof sketch\" part to establish the main arguments that are different from previous works. In particular, l. 215 the authors say \"one needs extra care in the analysis to ensure that the regret bound is also tight\", but after that it seems that all arguments are standard. It might be interesting to provide more details or to remove that sentence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review, for recognizing the significance of our technical contributions, and for providing valuable feedback.\n\n**W1. Writing and paper organization + Regret Analysis**\n\nThank you for your suggestions. Indeed, Section 3.2 implicitly assumes that the reader is familiar with PAC-Bayesian analysis. Due to space constraints, we could not provide more details and instead referenced two standard sources [9,10]. In the revision, we will ensure Section 3.2 is easier to follow.\n\nAdditionally, as the reviewer noted, the proof sketch of the regret bound can be improved. We will address this in the revision. Allow us to elaborate on the main technical novelty of our regret analysis, which will be included in the revised version.\n\nThe existing proof relies on the original self-concordance lemma [11, Lemma 9], which allows the appearance of $\\nabla^2 \\mathcal{L}_t(\\theta\\_{*})$ (related to the matrix $H\\_t(\\\\theta\\_\\*)$ in [11]). Consequently, it allows for one to use the elliptical potential lemma (Lemma B.1), with $x_s$ replaced by $\\sqrt{\\dot{\\mu}(\\langle \\theta\\_\\star, x_s \\rangle)} x_s$. However, as described in our proof sketch, the self-concordance lemma introduces an additional factor of $S$.\nTo avoid this and at the same time to use our confidence sequence (Theorem 3.1), we utilize the Cauchy-Schwartz w.r.t. $\\widetilde{G}_t(\\widehat{\\theta}_t, \\nu_t) = \\lambda \\mathbf{I} + \\frac{1}{g(\\tau)} \\sum\\_{s=1}^{t-1} \\tilde{\\alpha}_s(\\widehat{\\theta}_t, \\nu_t) x_s x_s^\\top$ (see Eqn. (26) in Appendix B.1). $\\widetilde{G}_t$ arises naturally when one performs second-order Taylor expansion of $\\mathcal{L}_t(\\cdot)$ around its minimum $\\widehat{\\theta}_t$; in particular the confidence set can be rewritten as a quadratic form involving $\\widetilde{G}_t$ (Lemma B.6). However, now note that the elliptical arguments are no longer applicable to $\\sum_t \\lVert x_t \\rVert\\_{\\tilde{G}_t(\\hat{\\theta}_t, \\nu_t)^{-1}}^2$. Our main technical novelty is designating the \"worst-case $\\theta$\" over all future confidence sets from time $s$ to $T$ (see $\\bar{\\theta}_s$ in Eqn. (24) of Appendix B.1). With this, we can follow an alternate chain of inequalities to obtain $\\sum_t \\lVert x_t \\rVert\\_{\\bar{H}_t^{-1}}^2$, where $\\bar{H}_t = 2 g(\\tau) \\lambda \\mathbf{I} + \\sum\\_{s=1}^{t-1} \\dot{\\mu}(\\langle \\bar{\\theta}_s, x_s \\rangle) x_s x_s^\\top$ (see Eqn. (26) in Appendix B.1).\nThen the elliptical potential lemma is applicable with $x_s$ replaced by $\\sqrt{\\dot{\\mu}(\\langle \\bar{\\theta}_s, x_s \\rangle)} x_s$, concluding our proof.\nNote that there are other details we are omitting here, but they are relatively minor manipulation of adding and subtracting the desired quantities to get to the place where we can apply the elliptical potential lemma as we stated above.\n\n**Q1. Why $P_t$ is a valid posterior?**\n\nThe terms \"prior\" and \"posterior\" are somewhat misleading in PAC-Bayes, as they need not strictly be the Bayesian prior and posterior. Instead, \"prior\" should be interpreted as any data-free distribution. and \"posterior\" as any data- and prior-dependent distribution, providing more flexibility in choosing them. The reviewer is correct that one should choose the \"prior\" and \"posterior\" such that their KL divergence is not too large. Simultaneously, in our context, the posterior should be chosen so that the Lipschitz inequality is not too loose (see line 164). We refer the reviewer to the excellent introduction to PAC-Bayes by P. Alquier [9] and a survey on PAC-Bayes time-uniform bounds by Chugg et al. [10]. There is no need to apologize; we also found it challenging to adapt to PAC-Bayes terminologies while writing the paper.\n\n**Q2. Does the learner require the knowledge of $R_\\mu$?**\n\nThank you for highlighting this point. Indeed, the learner needs to know $R_{\\dot{\\mu}}$ or its upper bound. This requirement arises because the bandit algorithm relies on our new confidence sequence (Theorem 3.1), which in turn depends on the Lipschitz constant $L_t$ of the GLM negative log-likelihood, which depends on $R_{\\dot{\\mu}}$; see Table 1 and Appendix A of our submission. We will clarify this in the revision.\n\n**Q3. Elaborating on the connection of Theorem 3 of Foster et al. (2018) with our Section 3.2**\n\nTo recall the proof of Theorem 3 of [12], they first consider a distribution $P_t(\\cdot)$ over the parameter $W$ (see their Algorithm 1) and use $\\eta$-mixability of the logistic loss to obtain an inequality involving the negative-log-integral term $\\int_{\\mathcal{W}} \\exp\\left( -\\eta \\sum_t \\ell(Wx_t, y_t) \\right) dW$. They define $S = \\theta W^\\star + (1 - \\theta) \\mathcal{W} \\subseteq \\mathcal{W}$, where $W^\\star$ is the ground-truth optimal parameter and $\\theta \\in [0, 1)$ is to be determined later. The proof concludes by chaining the inequality $\\int_{\\mathcal{W}} \\geq \\int_S$ with the Lipschitzness of the logistic loss and expanding the integral.\n\nOur Section 3.2 follows a similar approach with some key differences. While their negative-log-integral also arises in our scenario, we adopt a more compact, streamlined PAC-Bayes approach. In our case, a similar quantity $\\mathbb{E}\\_{\\theta \\sim \\mathbb{Q}}[\\exp(-\\mathcal{L}_t(\\theta))]$ arises from our Donsker-Varadhan representation (Lemma 3.2), where $\\mathbb{Q}$ is our prior. We then apply Ville’s inequality to obtain the time-uniform PAC-Bayes bound (Lemma 3.3), and our choices of prior/posterior resemble their choice of $S$. Our Lipschitzness arguments also resemble their $\\ell\\_{\\infty}$ Lipschitzness argument (see their pg. 17 in the PMLR proceeding version).\n\nWe will provide a more detailed explanation of the proof in the revision. Thank you for bringing this to our attention.", "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": "6GkkWYwqKb", "reviewer": "Reviewer_q1y1", "summary": "This paper proposes Likelihood ratio based confidence sequences for generalized linear inference, who's width only depends logarithmically on $S$, the bound on norm of the parameter vector. This is achieved by utilizing a pac-bayesian change of measure inequality, with the prior and posterior distributions chosen very carefully. Tightness of the bounds are compared with some prior work and a small numerical experiment is provided to demonstrate potential benefits of the confidence bounds, for the application of logistic bandits.", "questions": "### Questions:\n1) For equation (3), I did not understand why this is a batched estimator and not a sequential one. Can you clarify your terminology of batched vs sequential estimator?\n2) Is there theoretical benefit/necessity to solving the constrained problem rather than regularizing? I realize that for validity of the CS, we require $\\hat \\theta_t$ to also lie within $\\Theta$, but is there any other reason why we consider the MLE rather than generalized ridge loss? Asking because from a practical perspective, the latter is better/more stable.\n3) What is the dependency of Theorem 3.2 on $S$? Mainly, do the ellipsoid sets blow up for logistic bandits? \n4) Can you comment on the computational complexity of calculating the CS of Theorem 3.1 and Theorem 3.2? My feeling is that both are computationally tough to calculated (e.g. due to the lipschitz constant, or the matrix norm wrt the hessian matrix). \n5) Do you see a clear kernelized extension? In particular, is there a choice of prior-posterior for which the KL divergence is bounded and allows for a similar rate?\n6) Is Theorem 4.1 minimax optimal, e.g. wrt the lower-bound of Abeille 2021?\n7) In Fig 1-(c), is the logistic CS is automatically an ellipsoid, or is it just resembling one?\n8) Are you using the theoretical $\\beta_t(\\delta)$ for Fig (1-a) and (1-b)? \n_____\n### Small typos & Suggestions\n\n- [Lines 57, 67, 69] space before parenthesis missing\n- [Line 72] notation for derivates isn't coherent. Both $\\dot{}$ and ${}^\\prime$ are used.\n- [Line 73] would make more sense to write for $t \\geq 1$, since all statements are anytime.\n- [Line 95] The sentence does not have a verb. Perhaps instead of \"Despite\" authors meant \"Exists\".\n- [Line 100] First time I read \"unbounded GML\" I was confused. Would be good to mention that this refers to values o $\\mu$.\n- [Theorem 3.1] Second line should be $\\mathcal L_t$, the subscript is missing.\n- [Line 156] It is not clear what \"it\" refers to. Perhaps swap it out for \"the analysis\".\n- [Line 161] Would be good to include a reference for the first equality in the equation. Does this hold in equality or is it an upper bound? Is this common knowledge? I did not know it.\n- [Line 173] This line reads vaguely and informally, \"even\" is used twice. It's best if the justification is made rigorous or removed entirely. \n- [Fig 1] To demonstrate the robustness of the algorithm to $S$ you could've chosen a much larger value and still significantly outperform the baseline. Would be nice to see the effect of S = 10**{1, 2, 3, 4}.", "limitations": "The proof technique might be limited to linear setting, with in my opinion can be viewed as a limitation, if one of the contribution points of the paper is the proof technique. \n\nPractical limitations and applicability are not adequately addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- Key contribution is reducing the $\\mathrm{poly}(S)$ dependency of the width of the confidence sets to $\\log S$. Practitioners typically do not use state-of-the-art CS prescribed by theory because 1) they are tough to compute 2) depend on unknown parameter. This paper takes a step towards mending this gap by addressing the second issue.\nSince dependence of the width on $S$ is logarithmically, then the practitioner can choose a conservatively large upper bound on $||\\theta_\\star||$ and not suffer from loose/uninformative CS.\n- The work benefits from versatility of LR-based CS and automatically gives results that are applicable to multiple data/noise models.\n- Gives convex CS for logistic bandits that have rate optimal dependence on $\\kappa$ parameter. I might be wrong, but as far as I know, prior work with such dependency on $\\kappa$ resort on non-convex sets [Faury 2022]. *I am not aware of the latest results, particularly [Lee 2024].*\n- The proof is light and combines simple ideas from not-so-connected areas. Compared to prior work on parallel topics (on GLM, logistic, or poisson models), this seems like a more elegant approach to prove anytime validity of confidence sequences.", "weaknesses": "I think improving dependency on $S$ gains significant relevance, once it yields a practical algorithm. \nIf there is no computationally efficient/stable way of calculating the confidence sets, then the relevance of the results is limited to a subset of the bandit theory community. Maximising the UCB on the proposed sets (Thm 3.1 and Thm 3.2) does not seem to be a computationally feasible task, particularly for higher dimensions. Further, I'm afraid that practical relaxations/approximations, would blow up the width, and loosing the current theoretical edge.\n\n- The ellipsoid sets are proposed as a easy-to-implement alternative (which actually might not be the case, due to the hessian in the norm). But it is not clear to me if they are similarly tight. Depending on the parameter $R_s$, these sets may again scale with $\\mathrm{poly}(S)$.\n\n- While the paper makes a valuable theoretical contribution, I think it would need more experiments to appeal to a broader community. For instance, a proper benchmarking of the CS against practically common choices (vanilla GP-based CS based on a very loose Linear regression model that uses a sub-Gaussian noise with a large variance) and showing that the statistical gains are worth the computational effort by reporting the regret, and the computational efficiency (e.g. number of flops).\n\n- Experiments do lack comparison with relevant baselines and are only in the logistic case. In particular, Emmenegger 2023 and Faury 2022 are two algorithms that should be compared to. IIRC, Emmenegger 2023 does not work well for logistic bandits, so this would help strengthen the message of the paper. However, Faury 2022 seems to make a strong case on the joint computational and statistical efficiency of their algorithm (for logistic bandits).\n\n\nThis is not a weakness, but I should mention that I am not personally aware of the common rates and parameter dependencies in LR-based confidence sequences. Therefore, I *could not* verify the dependence of the width on certain parameters, so I don't know if everything is optimal, or we are sacrificing something else on the path to $\\log S$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for several enlightening questions and suggestions that will certainly improve our paper.\n\n**W1. & Q3. Statistical issues with ellipsoidal relaxation**\n\nIndeed, the ellipsoidal CS introduces an additional factor of $S$, as it uses the self-concordance control (Lemma A.4). For logistic bandits, the blowup is only by a factor of $S$, as $R_s = 1$ for Bernoulli distribution. Among the *ellipsoidal* CSs available for linear and logistic bandits, our ellipsoidal CS’s width is theoretically the tightest, ignoring absolute constants. Indeed, we believe that our ellipsoidal CS-based UCB algorithm attains $\\mathcal{O}(d \\sqrt{ST / \\kappa_\\star(T)})$ regret, which is strictly better than many baselines' regret guarantees, e.g., **ada-OFU-ECOLog**. Also, the complexity of computing the Hessian $H_t = \\sum_{s=1}^t \\dot{\\mu}(\\langle x_s, \\hat{\\theta}_t \\rangle) x_s x_s^\\top$ is similar to that of the design matrix in linear bandits, making our ellipsoidal CS practical.\n\n**W2. & W3. Lacking experiments**\n\nPlease refer to our Global Response #1, where we address many of the reviewer’s suggestions and concerns about the experiments. As measuring the number of flops for constrained nonlinear convex optimization was unclear, in SPDF, we report the algorithms' runtimes (sec), measured by Python’s time module.\n\n**Q0. Are we sacrificing something for $\\log S$?**\n\nYes, obtaining $\\log S$ requires more computational power (e.g., norm-constrained MLE). Please refer to our above response to W1 & W3.\n\n**Q1. Batched vs. sequential estimator?**\n\nWe apologize for the confusion. These terms distinguish between $\\mathcal{L}_t(\\hat{\\theta}_t)$, which uses a single MLE to compute the loss at $t$, and $\\mathcal{L}_t(\\\\{\\hat{\\theta}_s\\\\}\\_{s=1}^t)$, which uses all the MLEs computed to far to compute the loss at $t$ as in weighted likelihood ratio testing [4]. We will clarify this in the revision.\n\n**Q2. Why constrained MLE?**\n\nIf we stick to the uniform prior, then we are not aware of any way to allow the regularized MLE since then we cannot ensure that there is a sufficient prior probability mass around the regularized MLE (the regularized MLE can be far outside of the support of the uniform prior). Constrained MLE ensures that the estimator falls in the support of the uniform prior, so one can find a sufficient probability mass around it. \n\nBut then one may wonder why uniform prior? We made this choice since we found that the KL divergence between uniform prior and posterior has a closed form and that it provides us with much easier control of under-approximating the integral w.r.t. the posterior. Alternatively, one can consider, e.g., Gaussian prior, and attempt to make the regularized MLE work, but we found that terms are much harder to control. We have not done an exhaustive attempt on this, so we believe it is an interesting future direction!\n\n**Q4. & W1. Computational complexity of calculating the CS?**\n\nFirst, the radii in Theorem 3.1 and 3.2 can be explicitly computed using the Lipschitz constants for various GLMs provided in Table 1. Also, the complexity for computing the matrix norm w.r.t. the Hessian matrix $H_t = \\sum_{s=1}^t \\dot{\\mu}(\\langle x_s, \\hat{\\theta}_t \\rangle) x_s x_s^\\top$ isn’t too much, considering how its computation is composed of matrix-vector products. Please refer to our Global Response #2 for the computational issues in the UCB. \n\n**Q5. A clear kernelized extension?**\n\nNo, extending to the RKHS setup seems non-trivial. The primary issue is that no translation-invariant Lebesgue measure exists in infinite-dimensional function space (e.g., RKHS), i.e., no uniform distribution and no concept of likelihood, among many counterintuitive issues. Indeed, the usual properties that hold in finite dimensions may fail in infinite dimensions (see, e.g., [13]), and one must be very careful when transferring the current PAC-Bayes proof to infinite dimensions. For instance, for the KL between two Gaussian measures to be well-defined, one measure must be absolutely continuous against another, which holds under certain nontrivial conditions on mean and covariance operators (Feldman–Hájek theorem). One could consider using the well-studied Gaussian Process prior/posteriors (as hinted at in our answer to **Q2**), but choosing the mean and kernel to obtain similar guarantees is non-trivial.\n\n**Q6. Is Thm 4.1 minimax optimal?**\n\nSomewhat yes. As elaborated in lines 250-272, the leading term of our regret bound for *logistic bandits* is indeed (locally) minimax optimal in $d, T, \\kappa_\\star(T)$ relative to the lower bound of [2]. Moreover, a closer look into their proof shows that their lower bound scales as $1 / S$, indicating a gap of $S$ between the lower and upper bounds. To the best of our knowledge, there isn’t any generic regret lower bound that holds simultaneously for all **GLB**s. We suspect a similar $d\\sqrt{T / \\kappa_\\star(T)}$ lower bound would hold for **GLB**s. One could either carefully modify the proof of [2] for GLMs (e.g., their relative entropy decomposition lemma (Lemma 6) relies on the fact that the reward distribution is Bernoulli) or come up with something new. We leave this as future work.\n\n**Q7. Is Fig 1(c) ellipsoid?**\n\nNo, our CS at each time $t$ is a level set of the negative log-likelihood loss $\\mathcal{L}_t(\\cdot)$, which isn’t precisely an ellipsoid. But, as the CS tightens, it more closely resembles an ellipsoid, as the second-order Taylor approximation (an ellipsoid as shown in our Theorem 3.2) gets tighter. We will elaborate on this in the revision.\n\n**Q8. Are you using theoretical $\\beta_t(\\delta)$ for experiments?**\n\nYes, we use the precise theoretical $\\beta_t(\\delta)$ in all of our experiments, including additional ones in the supplementary pdf.", "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": "HF8QxOTr6X", "reviewer": "Reviewer_HLad", "summary": "Confidence intervals for GLMs using a PAC-Bayes approach.", "questions": "See weaknesses section.", "limitations": ".", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Confidence sequences and bandit algorithms for GLMs are a hot topic, and the authors contribution to that topic is solid, both because of the strength of the result itself, and because the proof itself is very simple and easy to verify---something that cannot be said about some of the previous work on the topic.", "weaknesses": "The paper is written in a style that might be described as \"being written for the reviewers\". It contains misleading and inaccurate claims which are meant to, presumably, impress the reader with the quality of the results. I give some examples shortly. Its unfortunate, because the ideas in the paper are good, and if only the authors had simply written about their work in a neutral, descriptive manner, I would absolutely recommend that the paper is accepted. However, I do not believe the overclaiming to be some sort of an accident---which if it were, the authors might fix upon my pointing it out---and so without any system for \"revise and resubmit\", must recommend rejection.\n\nSome examples of problematic claims (emphasis mine in all quotes):\n1) Lines 1-2, the authors claim that \"[...] for any generalised linear models (GLMs) that is guaranteed to be convex and numerically tight\". To my understanding, the authors have no guarantee that their result is numerically tight for every GLM, and thus the first sentence of the abstract is false (is there even a guarantee in the paper that there exists a single GLM for which it is numerically tight?).\n2) Line 53, \"Our main novely lies in __cleverly__ using [...]\"; whether the approach is clever or not is perhaps something for readers to judge, not for the authors to proclaim.\n3) Line 107, \"we completely remove the poly(S)-dependency from the radius, resolving one of the __open problems__ posited by Lee et al. (__2024__).\" An open problem is an well-known unsolved problem in a field (that is, a problem that numerous other researchers have attempted and failed to solve). Your \"open problem\" is not that. Rather, it is a single sentence in the middle of a paper published at a conference that took place less than 3 weeks before this paper was submitted that simply states that the authors leave it for future work. \n4) Line 111-112 authors claim that \"perhaps more importantly, [ellipsoidal confidence sequences allow] one to equivalently rewrite the optimistic optimization in the UCB algorithm as a closed-form bonus-based UCB algorithm\". Is this true? The claim appears to be that, if $\\mathcal{X}$ is a subset of the unit ball and $\\Theta$ is an ellipsoid, then the quantity $b(\\Theta) = \\\\max_{x \\in \\mathcal{X}} \\max_{\\theta \\in \\Theta} \\langle x, \\theta \\rangle$ has a closed form expression. Could the authors state the closed form expression they have in mind for, say, $\\mathcal{X}$ being an irregular polytope with $2^d$-many vertices? And if the resulting expression requires $O(2^d)$ time to evaluate... then the statement is trivial, and ellipsoidal form of the confidence sequences is unimportant. (and of course, fit a spline to those 2^d vertices, and now you cannot even write the solution as a sum over the vertices!).\n5) Lines 307-308: in the conclusion, the authors state that \"[their algorithm] is numerically verified to be the best performing algorithm.\" The authors compared against __one baseline__ on a __single experiment__ varying only __one experimental parameter__ between __two values__, and the experiment was __two dimensional__. *Really?* \n\nOther than that, section 3.3 seems like it could contain interesting insight, but I'm worried that the way it is written, the only persons that might be able to understand it are either the authors themselves, or someone that has spent just as much time poring over the paper as the authors have done. I would suggest that the authors either expand on it and explain it better, or cut it.\n\nSome minor typos:\n- Line 312-313 you talk of \"Bayesian randomized (exploration) algorithms for GLM bandits\", but then cite 5 papers for these algorithms, out of which the four I am familiar with are frequentist algorithms, not Bayesian.\n- Line 95-97, second half of sentence seems to be missing\n- Line 129, the definition looks like the likelihood ratio, not the log-likelihood ratio as claimed\n- Theorem 3.2, second line\n- Line 82, the set in probability is wrong\n- Line 75 rewards should be in filtration", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer’s valuable reviews and comments.\n\n**W1. “Numerically tightness” of CS**\n\nWe intended \"numerically tight\" to mean numerically tighter than previously known and non-vacuous, a phrase often used in prior works on PAC-Bayes. We will clarify this sentence in the revised manuscript.\n\n**W2. “Cleverly”**\n\nWe concur with the reviewer that the novelty of the approach should be left to the reader's judgment. Accordingly, we will remove this word.\n\n**W3. Open problem should be well-known that numerous other people should’ve tackled and fail**\n\nWe start by pointing out that obtaining a tight (hopefully optimal) regret bound for generalized linear bandits, including logistic bandits, has been a long unresolved open problem in bandits, starting from the seminal work of Filippi et al. (2010) and tackled by numerous researchers. Although we cited Lee et al. (2024) [1] as the source of the open problem, this is to emphasize the dependency of $S$ that has been ignored for quite sometime before [1]. We will fix the references to the original reference and provide more context into the importance of our open problem.\n\nWe also highlight that Lee et al. (2024) [1] has been available on arXiv since October 2023. In our submission, we cited it using the BibTeX of its most recent conference version in 2024.\n\n**W4. Importance of ellipsoidal confidence set**\n\nThank you for pointing this out. We would like to clarify that our original statement did not imply that the solution to the UCB $\\max_{x \\in X} \\max_{\\theta \\in \\mathcal{C}_t(\\delta)} \\mu(\\langle x, \\theta \\rangle)$ has a closed solution. Upon further reflection, we acknowledge that the current wording may lead to misunderstanding, and we appreciate the reviewer for highlighting this. In Global Response #2, we elaborate on our intended meaning and how it can be corrected. We assure the reviewer that these corrections will be reflected in the revised manuscript. Additionally, as the reviewer mentioned, if the arm set is of combinatorial size, e.g., $2^d$, then we are indeed bound to incur at least $\\Omega(2^d)$ computational cost. However, we demonstrate in Global Response #2 that if the CS is precisely an ellipsoid, the computational cost is $O(2^d)$, which is significantly more efficient than solving a convex optimization for each arm.\n\n**W5. Weak experiments**\n\nPlease refer to Global Response #1.\n\n**Regarding Section 3.3**\n\nThank you for your suggestion. We will make sure to explain the relationships more clearly or consider removing this section from the revision.\n\n**Typos**\n\nWe apologize for the typographical errors and will commit to correcting them in the revision. We sincerely thank the reviewer for taking the time to point them out.\n\nTo ensure clarity, we address each typo as follows:\n- Lines 312-313: The reviewer is correct. We will correct it to “randomized (exploration) algorithms.”\n- Lines 95-97: We will revise this sentence appropriately.\n- Line 129: It should indeed be the likelihood ratio.\nTheorem 3.2, second line: We will correct it to $\\mathbb{P}(\\exists t \\geq 1 : \\theta_\\star \\not\\in \\mathcal{E}_t(\\delta)) \\leq \\delta$.\n- Line 82: We will correct it to $\\mathbb{P}(\\exists t \\geq 1 : \\theta_\\star \\not\\in \\mathcal{C}_t(\\delta)) \\leq \\delta$.\n- Line 75: The rewards should indeed be in the filtration.\n\n\nWe hope that our response has properly addressed the reviewer’s concerns and that the reviewer would reconsider the score. Thank you.", "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": "xo5UCWVLiY", "reviewer": "Reviewer_aQNL", "summary": "The paper derives a new   time-independent inequality for likelihood ratios in the Generalized Linear Model. The proof is based on a PAC-Bayesian approach with a well-chosen prior. The result is applied to GLM bandit models, improving a variant of GLM-UCB. The resulting regret bound removes a exponential dependency in the norm of the unknown parameter.\nSeveral examples of GLM are discussed, and minimal numerical experiments are reported. The comparison with OFULLog+ is convincingly exposed, both in theory and in practice.", "questions": "How smaller can \\beta_t(\\delta) be for a confidence region valid only for a given t>0 (instead of all t>0)? This might be worth writing in the paper", "limitations": "This section does not really seem relevant to this mostly theoretical submission", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Overall, I consider that the submission is technically sound, somewhat incremental, but will be of interest to the community.", "weaknesses": "The submission is correctly written, but with a number of clumsinesses (some are listed below). \nThe main text contains not much more than the statement of the results and the (unsurprising) description of GLM-UCB+, while the supplementary material is written a collection of appendices that are not very well presented. For example, the first appendix is called \"Missing Results\", which is pretty unspecific. I did not check all the details, but the main lines look correct.\n\nl.69 undefined notation \\mathcal{B}^d(1)\nl.77 give a reference\nl.80 could you precise what is R_\\mu in those examples?\nl.95 the sentence is grammatically wrong, something is missing\nThm. 3.1: replace \"where\" by \"for the choice\"\nl.129 it is not the log-likelihood but the likelihood\nl.583 is it not possible to suggest a proof instead of a reference to \"WoframAlpha\" (to a plot?)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable feedback and suggestions, and for recognizing our paper's technical soundness and contributions.\n\n**Number of clumsinesses, Typos, Organization issues**\n\nWe apologize for the typographical errors and the organizational issues identified in the manuscript. We are committed to correcting these in the revised version, including re-organizing the appendices as suggested by the reviewer. We sincerely appreciate the reviewer's effort in pointing out these issues.\n\nTo ensure clarity, we address each typo as follows:\n- Line 69. $\\mathcal{B}^d(1)$ is the ball of radius 1 centered at the origin in R^d.\n- Line 77. The mentioned properties of GLM are provided in [14], which we will add as reference\n- Line 80. Of course. For Gaussian, $R_{\\dot{\\mu}} = 1$; for Poisson, $R_{\\dot{\\mu}} = e^S$; for Bernoulli, $R_{\\dot{\\mu}} = \\frac{1}{4}$. Thank you for this suggestion, which would make our presentation clearer.\n- Line 95. Yes. We will appropriately change the sentence.\n- Line 129. Yes, it should be the likelihood ratio.\n- Line. 583. We sincerely apologize for this mishap. Due to the pressing time, we forgot to replace this with rigorous proof. Below, we provide rigorous proof of this result, which will, of course, be reflected in the revision:\n\nLet us denote $f(p) := p^{-1/2} \\left( \\mathbb{E}[{X}^p] \\right)^{1/p}$ for $p \\in \\mathbb{N}$.\n\nThen, using well-known properties of the Gamma function, we have that\n\\begin{equation*}\n    f(2p) = \\sigma 2^{\\frac{2p-1}{4p}} (2p)^{\\frac{1}{2p} - \\frac{1}{2}} \\left( (p-1)! \\right)^{\\frac{1}{2p}}\n    = \\sigma \\sqrt{ p^{-1} \\left( \\sqrt{2} p! \\right)^{\\frac{1}{p}} }\n\\end{equation*}\nand \n\\begin{equation*}\n    f(2p - 1) = \\sigma 2^{\\frac{2p - 2}{2(2p - 1)}} (2p - 1)^{\\frac{1}{2p - 1} - \\frac{1}{2}} \\left( \\sqrt{\\pi} \\frac{(2p - 3)!!}{2^{p - 1}} \\right)^{\\frac{1}{2p - 1}}\n    = \\sigma (2p - 1)^{\\frac{1}{2p - 1} - \\frac{1}{2}} \\left( \\sqrt{\\pi} (2p - 3)!! \\right)^{\\frac{1}{2p-1}},\n\\end{equation*}\nwhere we define $(-1)!! := 1$.\n\nThen, we have that\n\\begin{equation*}\n    f(2p) \\overset{(i)}{<} \\sigma \\sqrt{p^{-1} (\\sqrt{2} p^p)^{\\frac{1}{p}}}\n    = \\sigma 2^{\\frac{1}{4p}}\n    \\leq \\sigma 2^{\\frac{1}{4}},\n\\end{equation*}\nwhere $(i)$ follows from $p! < p^p$.\nWe also have that \n\\begin{equation*}\n    f(2p-1) \\overset{(i)}{<} \\sigma (2p - 1)^{\\frac{1}{2p - 1} - \\frac{1}{2}} \\left( \\sqrt{\\pi} (2p - 1)^p \\right)^{\\frac{1}{2p-1}}\n    \\overset{(ii)}{<} \\sigma \\left( \\sqrt{\\pi} (2p - 1)  \\right)^{\\frac{1}{2p-1}}\n    \\overset{(iii)}{<} \\sigma \\sqrt{\\pi},\n\\end{equation*}\nwhere $(i)$ follows from $(2p - 3)!! < (2p - 1)^p$, $(ii)$ follows from $\\frac{p}{2p - 1} > \\frac{1}{2}$, and $(iii)$ follows from the observations that for $z \\geq e$, $f(z) = (\\sqrt{\\pi} z)^{1/z}$ is decreasing, and $f(1) = \\sqrt{\\pi} > f(3) = (3 \\sqrt{\\pi})^{1/3}$. The first observation can be easily verified as follows: $\\frac{d}{dz} \\log f(z) = \\sqrt{\\pi} \\frac{1 - \\log z}{z^2} \\leq 0, \\quad \\forall z \\geq e.$\n\nFinally, as $2^{1/4} < \\sqrt{\\pi}$, we have that $\\sup_{p \\in \\mathbb{N}} f(p) \\leq \\sqrt{\\pi} \\sigma.$\n\n----\n\n\n**How small can $\\beta_t(\\delta)$ be when we don’t require the confidence region to be time-uniform?**\n\nThis is an interesting question, and thank you for bringing this up. First, we note that the mixture of martingale-type arguments (e.g., our PAC-Bayesian time-uniform guarantees) usually gives an anytime-valid guarantee *for free*.\n\nIf the reviewer is asking about the optimal $\\beta_t(\\delta)$ when the data $\\mathcal{D}_t =  \\\\{ (x_s, r_s) \\\\}\\_{s \\in [t]}$ can be adaptively collected for a given $t$, we don't have a definitive answer. This resembles the fixed-budget best-arm identification in bandits [15], which may be a good starting point for this direction.\n\nWhen the data $\\mathcal{D}_t$ is collected independently, the problem reduces to the fixed-design setup. For the linear case, one has the confidence region of the following form [Eqn. (20.2) of 16]: for any fixed $x \\in \\mathcal{B}^d(1)$, \n\n\\begin{equation}\n\\mathbb{P}\\left( \\langle x, \\hat{\\theta}_t - \\theta\\_{\\star} \\rangle \\leq \\mathcal{O}\\left( \\lVert x \\rVert\\_{V_t^{-1}} \\sqrt{\\log\\frac{1}{\\delta}} \\right) \\right) \\geq 1 - \\delta,\n\\end{equation}\n\nwhere $V_t = \\sum_{s=1}^t x_s x_s^\\top$ is the design matrix that we assume to be invertible for now.\n\nFor the logistic model, we have the following [Theorem 1, 17]:\n\n\\begin{equation*}\n\\mathbb{P}\\left( \\langle x, \\hat{\\theta}_t - \\theta\\_{\\star} \\rangle \\leq \\mathcal{O}\\left( \\lVert x \\rVert\\_{H_t^{-1}} \\sqrt{\\log\\frac{t\\_{eff}}{\\delta}} \\right) \\right) \\geq 1 - \\delta,\n\\end{equation*}\n\nwhere $t\\_{eff}$ is the number of distinct vectors in $\\\\{x_s\\\\}\\_{s \\in [t]}$ and $H_t = \\sum_{s=1}^t \\dot{\\mu}(\\langle \\widehat{\\theta}_t, x \\rangle) x_s x_s^\\top$ is the Fisher information matrix that we assume to be invertible for now.\nIn both cases, the confidence width is dimension-independent and asymptotically optimal with respect to the Cramér-Rao lower bound. Thus, for each fixed $t$, we indeed have a tighter $\\beta_t(\\delta)$.", "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:
We sincerely thank all the reviewers for providing detailed and insightful reviews. We are especially encouraged to see that the reviewers recognize the simple yet effective proof ideas (q1y1, HLaD), technically solid contribution in reducing $poly(S)$ to $\log S$ in the CS width (q1y1, HLaD, aQNL), easy-to-follow and pedagogical exposition (TTTd), thorough literature review (TTTd), and the importance of providing explicit constants for practitioners (TTTd). Here, we address two issues raised by multiple reviewers. In each reviewer's reply, we answer the remaining reviewers' comments point-by-point. We also attach a supplementary PDF (SPDF) containing additional experimental results.
# 1. Lack of experimental verifications (q1y1, HLaD)
Our experiments are meant to show that the theoretical improvement in $S$ for the logistic bandits is also numerically meaningful, as done in [1]. Still, we agree that our paper can benefit from more experiments to appeal to a broader community. SPDF provides additional experimental results for logistic bandits (Figure 1). We will make the codes publicly available.

We expand upon the considered settings by varying $S\in\\{5, 7, 9, 11\\}$. We tried $S\in\\{10^2, 10^3\\}$, but we could not handle the numerical instability from the optimization problems in time. We will *continue to try* to get the higher $S$ to work as well. We fix $d = 2$ due to the lack of time and space in SPDF, and also because only then can the complete confidence sets be fully visualized without any projection. We will *continuously work* to include additional experimental results for other values of $d$ in the revision. Also, as suggested by both reviewers, we will work to extend our codebase to linear/Poisson bandits and include the results in the revision.

Notably, we increased the number of baselines to eight, two of which are ours: **OFUGLB**, **OFUGLB-e** (ellipsoid CS), **EMK** [4], **RS-GLinB** [5], **OFULog+** [1], and **ada-OFU-ECOLog** [3]. **EMK** has been included as a practically common choice, as it performs better than other CS-based UCB algorithms, including GP-based CS [6]. For consistent experiments, we use the same setting as in our submission.

The results show that even against the additional baselines, our **OFUGLB** attains the best numerical regret. Compared to **EMK**, note that for small $S$, ours performs slightly worse. Still, for large $S$, the trend suggests that **OFUGLB** eventually attains smaller regret than **EMK**, suggesting that the theoretical regret of **EMK** may be looser than ours in terms of $S$. Also, we emphasize that *we provide a rigorous, state-of-the-art regret guarantee* for **OFUGLB**, while their theoretical guarantee scales with $\kappa$. The ellipsoidal version **OFUGLB-e** is also shown to have reasonable performance and even outperforms **ada-OFU-ECOLog** for small values of $S$. Of all considered algorithms, **RS-GLinCB** seems to have the highest regret, even though it also has $poly(S)$-free regret. We believe this significant difference is from the fact that **RS-GLinCB** involves an explicit warmup stage, while ours doesn’t. Indeed, in [5], the authors considered $20000$ rounds for logistic bandits, where **RS-GLinCB** is shown to eventually outperform **ada-OFU-ECOLog**, while we only considered $4000$. We will run the additional experiments with increased rounds for the revision for a fair comparison. 

In SPDF's Table 1, we additionally report the runtime (sec) of a single run of each algorithm (measured via Python’s time module) for the logistic bandit instances. Note that **OFUGLB-e** is generally faster than **OFUGLB** by roughly 6 minutes. Also, **EMK** is generally slower than **OFUGLB**, as it needs to keep track of the entire sequence of estimators.
# 2. Computational feasibility of UCB (q1y1, HLaD)
Here, computational feasibility is being implementable using (efficient) convex solvers as subroutines, which is relatively standard in bandit literature [1,4,7]. While writing the response, we realized that the Theorem 3.2 should be $\mathcal{E}_t(\delta)=\left\\{\theta\in\mathbb{R}^d : \lVert\theta-\hat{\theta}_t\rVert\_{H_t}\leq\gamma_t(\delta)\right\\}$. We apologize for the confusion.

With this, let us assume that the arm set $X$ is finite. Then, it is easy to see that the UCB using the ellipsoidal CS $\mathcal{E}_t(\delta)$ is computationally efficient, as it reduces the following closed-form *objective*:

$$
\mathrm{argmax}\_{x \in X}\langle x,\hat{\theta}_t\rangle + \sqrt{\gamma_t(\delta)}\lVert x\rVert\_{H_t^{-1}}.
$$

In other words, there is no need to solve a convex optimization at each time $t$ and each arm $x \in X$.
In this case, the computational complexity of performing UCB at time $t$ is $\mathcal{O}(T\_{MLE}(t) + d^3)$, where $T\_{MLE}(t)$ is the complexity of computing the MLE at time $t$ and $d^3$ is the complexity of involved matrix computations, including computing $H_t^{-1}$.

Using the likelihood ratio-based CS $\mathcal{C}_t(\delta)$ still results in a convex optimization problem, albeit a bit less efficiently solvable than using $\mathcal{E}_t(\delta)$ due to lack of structure. We also remark that computational issues in high dimensions are present in many prior approaches to linear and logistic bandits [1,4,7], and our approach doesn’t introduce additional complexity relative to them.

We emphasize that we primarily focus on achieving the tightest regret guarantee for **GLB**s while being computationally *tractable*. We agree with the reviewers that obtaining jointly statistically tight and computationally *efficient* algorithms (e.g., [3]) is an important future direction but outside this paper’s scope.

Meta-review: The paper proposes a new way to obtain anytime sequential confidence regions for the parameters of generalized linear models (GLM) with application to UCB-style algorithms in GLM bandits. It's a topic that has received a renewed interest recently, with novel ideas, based notably on the self-concordant property (in particular for logistic models). This paper provides a new construction of independent interest -with an ellipsoidal region around the nom-constrained MLE, whose coverage is guaranteed through arguments based on PAC Bayesian ideas- as well as an improved regret bound for GLM bandits.

Most reviewers evaluated the contribution positively while making a number of important remarks, which I hope the authors will take into account in their revision: better organization of the paper, more careful wording of the contributions, improved experimental part, more clearly highlighting important issues such as Rebuttal.2, TTTd.Q2, q1y1.Q0 and Q2, aQNL typos and missing proof.

Both the technical content and the potential of the method in GLM bandit applications are interesting and justify acceptance for the conference.
Decision: Accept (poster)