A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits

Authors: jungyhun  lee
se-young  yun
kwang-sung  jun
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:37:44

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.

Main paper: 
 introduction: 
 One paramount task in statistics and machine learning is to 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 t, the learner chooses an action x t from an available set of actions X t and observes reward or outcome r t that is modeled as a distribution whose mean is an unknown function f * of x t ; i.e., r t ∼ p(•|x t ; f * ). One popular choice of such a model is the generalized linear model (GLM; McCullagh and Nelder (1989) ) that extends exponential family distributions to have a linear structure in its natural parameter as ⟨x, θ ⋆ ⟩, where θ ⋆ is an unknown parameter. In other words, the mean function is f * (x) = µ(⟨x, θ ⋆ ⟩) for some inverse link function µ. This encompasses a wide range of distributions, which in turn makes it ubiquitous in various real-world applications, such as news recommendations (Bernoulli; Li et al. (2010 Li et al. ( , 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 θ ⋆ at each time step t ≥ 1, given observations {(x s , r s )} t-1 s=1 , to make wise decisions. One popular and useful way to capture the uncertainty is via a time-uniform confidence sequence (CS) {C t (δ)} ∞ t=1 , which takes the form of P[∃t ≥ 1 : θ ⋆ ̸ ∈ C t (δ)] ≤ δ. Recently, CS has been described as 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) .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-Yadkori et al., 2011; Flynn et al., 2023) and Bernoulli (Abeille et al., 2021; Faury et al., 2020 Faury et al., , 2022;; Lee et al., 2024) . Especially for Bernoulli, all the existing CSs suffer from poly(S) factor in the radius, where S is the norm of the unknown parameter θ ⋆ . 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 S ).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 GLMs, 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 on 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 a 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-Yadkori et al., 2011; Auer, 2002) . We show that OFUGLB achieves the state-of-the-art 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)-free regret for logistic bandits in that OFUGLB does not involve an explicit warmup phase and only involves convex optimization subroutines. Our other significant main technical contribution is the analysis of OFUGLB, as 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 self-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.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 obtain state-of-the-art regrets Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
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 asEQUATIONwhere τ is the dispersion parameter, and ν is some known base measure (e.g., Lebesgue, counting). We assume the following: Assumption 1. θ ⋆ ∈ Θ ⊆ B d (S) := {θ ∈ R d : ∥θ∥ 2 ≤ S} for some known S > 0. Also, Θ is nonempty, compact, and convex with intrinsic dimension1 d. Assumption 2. The domain X for arm (context) x satisfies X ⊆ B d (1). Assumption 3. m is three times differentiable and convex, i.e., m ′′′ exists and μ := m ′′ ≥ 0.In the generalized linear bandit (GLB) problem, at each time t ∈ [T ], the learner observes a time-varying, arbitrary (adversarial) arm-set X t ⊆ X, chooses a x t ∈ X t , and receives a reward r t ∼ p(•|x t , θ ⋆ ). Let X [T ] := ∪ T t=1 X t and Σ t+1 := σ(Σ t , r t , x t+1 ) with Σ 0 = σ(x 1 ) be the filtration in the canonical bandit model (Lattimore and Szepesvári, 2020, Chapter 4.6) . From wellknown properties of GLMs (McCullagh and Nelder, 1989) , we have that E[r t |Σ t ] = m ′ (⟨x t , θ ⋆ ⟩) ≜ µ(⟨x t , θ ⋆ ⟩) and Var[r t |Σ t ] = g(τ ) μ(⟨x t , θ ⋆ ⟩), where µ is the inverse link function. We also define the following quantity describing the maximum slope of µ: R μ := max x∈X [T ] ,θ∈Θ μ(⟨x, θ⟩).Note that many common distributions, such as Gaussian (µ(z) = z, R μ = 1), Poisson (µ(z) = e z , R μ = e S ), and Bernoulli (µ(z) = (1 + e -z ) -1 , R μ = 1/4), fall under the umbrella of GLM.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Several limitations are posited in the main text, as well as in Appendix B.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
unified likelihood ratio-based confidence sequence for glms: 
 The learner's goal is to output a time-uniform confidence sequence (CS) for θ ⋆ , P[∃t ≥ 1 : θ ⋆ ̸ ∈ C t (δ)] ≤ δ, where P is w.r.t. the randomness of the confidence sets C t (δ). In this work, we are particularly interested in the log-likelihood-based confidence set "centered" at the norm-constrained, batch maximum likelihood estimator (MLE):EQUATION)where β t (δ) 2 is the "radius" of the CS that we will define later, L t (θ) is the negative log-likelihood of θ w.r.t. data collected up to t -1, and θ t is the corresponding MLE:L t (θ) := t-1 s=1 ℓ s (θ) ≜ -r s ⟨x s , θ⟩ + m(⟨x s , θ⟩) g(τ ), θ t := arg min θ∈Θ L t (θ).(3)Note that h(r s , τ ) is omitted as it plays no role in the confidence set nor the MLE.The form of the confidence set is the same as Lee et al. (2024) and convex relaxation of Abeille et al. (2021) , all of which utilizes a single, cumulative & constrained MLE θ t ∈ Θ to compute the loss at time t. Other approaches include using a single regularized MLE θ t that may lie outside of Θ (Abbasi-Yadkori et al., 2011), using a sequence of MLEs { θ s } t s=1 to compute the loss at time t (Abbasi-Yadkori et al., 2012; Emmenegger et al., 2023; Faury et al., 2022; Jun et al., 2017; Wasserman et 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 of the CS resembles the last approach: we also start from an expectation of loss over a prior distribution of θ without committing to an estimator. Yet, we introduce a single estimator θ t to avoid the computational difficulty of evaluating the expectation.Our first main contribution is the following unified confidence sequence for any GLMs, regardless of whether it is bounded or not, as long as the corresponding log-likelihood loss is Lipschitz: Theorem 3.1 (Unified CS for GLMs). Let L t := max θ∈Θ ∇L t (θ) 2 be the Lipschitz constant a of L t (•) that may depend on {(x s , r s )} t-1 s=1 . Then, we haveP[∃t ≥ 1 : θ ⋆ ̸ ∈ C t (δ)] ≤ δ, where β t (δ) 2 = log 1 δ + inf c∈(0,1] d log 1 c + 2SL t c ≤ log 1 δ + d log e ∨ 2eSL t d ,where the last inequality follows from the choice c = 1 ∧ d 2SLt .a Rademacher's theorem (Federer, 1996, Theorem 3.1.6 ): for a differentiable function L : Θ → R, inf L ≥ 0 : |L(θ) -L(θ ′ )| ≤ L θ -θ ′ 2 , ∀θ, θ ′ ∈ Θ = max θ∈Θ ∇L(θ) 2 .-µ(⟨x, θ ⋆ ⟩)| ≤ M < ∞. GLM Upper bounds for L t Proof Bounded by M (M + 2SR μ)(t -1)/g(τ ) Appendix C.1 Bernoulli (1 + S/2)(t -1) M = 1, R μ = 1/4 σ-subGaussian * σ -2 St + σ t log d δ Appendix C.2Poisson Lee et al. (2024) . Later in Section 4, we show that this improvement is significant, both theoretically and numerically.We now provide an ellipsoidal relaxation of Theorem 3.1 for the following class of GLMs: Assumption 4 (Russac et al. ( 2021)). GLM is (generalized) self-concordant, i.e., the following quantity is well-defined (finite):R s := inf R ≥ 0 : |μ(⟨x, θ⟩)| ≤ R μ(⟨x, θ⟩), ∀x ∈ X, θ ∈ Θ .For instance, Bernoulli satisfies this with R s = 1, and more generally, GLM bounded by R a.s. satisfy this assumption with R s = R (Sawarni et al., 2024, Lemma 2.1) . Many unbounded GLMs also satisfy this assumption, such as Gaussian (R s = 0), Poisson (R s = 1), and Exponential (R s = 0).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 λ ≥ 0,P[∃t ≥ 1 : θ ⋆ ̸ ∈ E t (δ, λ)] ≤ δ, where E t (δ, λ) := θ ∈ R d : θ -θ t 2 ∇ 2 Lt( θt)+λI d ≤ γ t (δ) ≜ 2(1 + SR s )(4S 2 λ + β t (δ) 2 ) .Let us denote A ≲ B if A ≤ cB for some absolute constant c > 0. Note that the relaxation is order-wise strict only when R s > 0. For instance, for Gaussian where R s = 0, the ellipsoidal relaxation does not introduce additional S-dependency when we choose λ = Θ 1 S 2 . We then have that 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 X t :∇ 2 L t ( θ t ) = 1 σ 2 t-1 s=1 x s x ⊤ s =: 1 σ 2 V t ,EQUATIONi.e., there is no need to solve a convex optimization for each arm. In the high-dimensional scenario where t = o(d), one can compute (∇ 2 L t ( θ t ) + λI d ) -1 with a time complexity of O(td 2 ) per round via the Sherman-Morrison formula (Sherman and Morrison, 1950) , which is more efficient than the naïve matrix inversion that takes O(d 3 ) time complexity.We consider M t (θ) := exp L t (θ ⋆ ) -L t (θ) , the likelihood ratio between the (estimated) distribution corresponding to θ and the true distribution corresponding to θ ⋆ . This has been the subject of study for over 50 years (Darling and Robbins, 1967a,b; 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 et al., 2020) .We follow the usual recipes for deriving time-uniform PAC-Bayesian bound (Alquier, 2024; Chugg et al., 2023) . We start with the following time-uniform property: Lemma 3.1. Let δ ∈ (0, 1). For any data-independent probability measure Q on Θ, we have:EQUATION)where P is over the randomness of the data (and thus randomness of L t 's).Proof. First, it is easy to see that M t (θ) = E[M t (θ)|Σ t-1 ] = M t-1 (θ)E dp(r t |x t ; θ) dp(r t |x t ; θ ⋆ ) Σ t-1 = M t-1 (θ) R dp(r|x t ; θ) dp(r|x t ; θ ⋆ ) dp(r|x t ; θ ⋆ ) =1 ,where R is the support of the GLM. (Note that this holds for any distributions.)Now consider the random variable E θ∼Q [M t (θ)], which is adapted to Σ t . This is a martingale, asE[E θ∼Q [M t (θ)]|Σ t-1 ] ( * ) = E θ∼Q [E[M t (θ)|Σ t-1 ]] = E θ∼Q [M t-1 (θ)]where ( * ) follows from Tonelli's theorem. We conclude by Ville's inequality (Ville, 1939) .We recall the variational representation of the KL divergence: Lemma 3.2 (Theorem 2.1 of Donsker and Varadhan (1983) ). For two probability measures P, Q over Θ, we have the following: θ) ].D KL (P||Q) = sup g:Θ→R E θ∼P [g(θ)] -log E θ∼Q [e g(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) {P t }, the following holds: for any δ ∈ (0, 1),EQUATIONProof. Note thatlog E θ∼Q [M t (θ)] -L t (θ ⋆ ) = log E θ∼Q [exp -L t (θ) ] ( * ) ≥ E θ∼Pt [-L t (θ)] -D KL (P t ||Q),where ( * ) follows from Lemma 3.2 with g(•) = -L t (•). By Lemma 3.1, we have thatP ∃t ≥ 1 : log 1 δ ≤ log E θ∼Q [M t (θ)] ≤ δ.Rearranging gives the desired statement. Remark 1 (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-known in the PAC-Bayes literature. Our main technical novelty lies in how to choose Q and P t , which is as follows: for c ∈ (0, 1] to be determined later, we setEQUATIONwhere Unif(•) is the uniform distribution and a + Θ = {a + θ : θ ∈ Θ} for a vector a ∈ R d .Then, denoting vol(•) as the (Lebesgue) volume in R d , we have Pull the arm x t and receive a reward r t ;D KL (P t ||Q) = log vol(Θ) vol( Θ) = log vol(Θ) vol (1 -c) θ t + cΘ = log vol(Θ) vol(cΘ) = log vol(Θ) c d vol(Θ) = d log 1 c .We also have thatE θ∼Pt [L t (θ)] = L t ( θ t ) + E θ∼Pt [L t (θ) -L t ( θ t )] ≤ L t ( θ t ) + 2SL t c,where the last inequality follows from the Lipschitzness of L t (•) and the observation that for θ = (1c)θ t + c θ ∈ Θ t , θ -θ t 2 = c θ -θ t 2 ≤ 2Sc.We conclude by minimizing over c ∈ (0, 1].Behind the Proof of Theorem 3.1Constrained MLE and Uniform Prior/Poster. As we consider constrained MLE, we know that θ t ∈ Θ, i.e., our "belief" on our MLE is precisely the prior Q = Unif(Θ). Then, as we want the true parameter θ ⋆ to be close to θ t , we want to show that a sufficiently large "posterior volume" is near θ t , formalized as P t = Unif (1 -c) θ t + cΘ for some shrinkage factor c ∈ (0, 1]. We later appropriately choose c to optimize the PAC-Bayesian bound.We remark that the uniform prior/posterior has been previously considered in universal portfolios (Blum and Kalai, 1999 , Theorem 1) and fast rates in online learning (Foster et al., 2018; Hazan et al., 2007) ; see Appendix A for discussions on relations to fast rates literature. To our knowledge, we are the first to use such uniform prior/posterior in the (time-uniform) PAC-Bayes context. Remark 2 (Use of Regularized MLE?). When one uses regularized MLE instead of constrained, as it is not guaranteed to be in Θ, one cannot directly use the same uniform prior/posterior. 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 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 appropriate prior/posterior whose supports are the entire R d (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 P t (•) over the parameter W ∈ W (see their Algorithm 1) and use η-mixability of the logistic loss to obtain an inequality involving the negative-log-integral termW exp -η t ℓ(W x t , y t ) dW . They define S = θW ⋆ + (1 -θ)W ⊆ W, where W ⋆ is the ground-truth optimal parameter and θ ∈ [0, 1) is to be determined later. The proof concludes by chaining W ≥ S with the ℓ ∞ -Lipschitzness of the logistic loss and expanding the integral.Our proof is inspired by the above, with some key differences. While the negative-log-integral also arises in our scenario, we adopt a more compact, streamlined PAC-Bayes approach. In our case, a similar quantity E θ∼Q [exp(-L t (θ))] arises from our Donsker-Varadhan representation (Lemma 3.2). We then apply Ville's inequality to obtain the time-uniform PAC-Bayes bound (Lemma 3.1), and our choices of prior/posterior resemble their choice of S. Our Lipschitzness argument at the end also resembles their ℓ ∞ -Lipschitzness argument.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
ofuglb: a generic ucb algorithm for self-concordant glbs: 
 As a direct application of our CS, we consider self-concordant GLB (Filippi et al., 2010; Janz et al., 2024) , where at each time t, the learner chooses a x t ∈ X t dependent on the history {(x s , r s )} t-1 s=1 and receives r t ∼ p(•|x t , θ ⋆ ). The learner's goal is to minimize the (pseudo-)regret, Reg(T ) := T t=1 µ(⟨x t,⋆ , θ ⋆ ⟩) -µ(⟨x t , θ ⋆ ⟩) , where x t,⋆ := arg max x∈Xt µ(⟨x, θ ⋆ ⟩).Inspired by the optimism principle (Abbasi-Yadkori et al., 2011; Auer, 2002) , based on our new, improved confidence sequence (Theorem 3.1), we propose OFUGLB (Algorithm 1), a generic UCBtype algorithm that applies to any instantiations of GLB. Through a new proof technique that allows us to circumvent κand poly(S)-dependencies in the leading term, our unified algorithm attains or improves the known state-of-the-art 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; 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 thatX [T ] = t∈[T ] X t , κ ⋆ (T ) := 1 1 T t∈[T ] μ(⟨x t,⋆ , θ ⋆ ⟩), κ(T ) := maxEQUATION)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 our new analysis, the leading term of the regret scales inversely with κ ⋆ (T ), and the transient term scales linearly with κ(T ).We now present the unified & state-of-the-art regret guarantee for self-concordant GLBs:Theorem 4.1 (OFUGLB for Self-Concordant GLB). OFUGLB attains the following regret bound for self-concordant GLB with probability at least 1 -δ:Reg(T ) ≲ d g(τ )T κ ⋆ (T ) log SL T d log R μST d leading term + d 2 R s R μ g(τ )κ(T ) log 1 + ST dg(τ )κ(T ) transient term, where L T is as defined in Theorem 3.1 and we assume thatlog 1 δ = O d log SL T d . 4.1 Proof Sketch of Theorem 4.1 -Regret Analysis of OFUGLBWe first emphasize that even though we have a tight CS (Theorem 3.1), naïvely 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-Schwartz inequality w.r.t. the (regularized) Hessian H t (θ ⋆ ) = λI + t-1 s=1 μs (θ ⋆ )x s x ⊤ s with μs (•) := μ(⟨x s , •⟩), which forces the use of self-concordant lemma (Abeille et al., 2021, Lemma 8) . This results in a CS of the form ∥θ ⋆ -θ t ∥ Ht(θ⋆) = O(Sβ t (δ)). Then, using the same regret decomposition of Abeille et al. (2021) and the optimism principle, the leading term of the regret is bounded ast μt (θ ⋆ )⟨x t,⋆ -x t , θ ⋆ ⟩ ≲ Sβ t (δ) t μt (θ ⋆ ) ≤ √ T /κ⋆(T ) t μt (θ ⋆ )x t 2 Ht(θ⋆) -1elliptical potential lemma (Abbasi-Yadkori et al., 2011) .Our proof begins by applying Cauchy-Schwartz w.r.t. G t ( θ t ), derived from the integral remainder in first-order Taylor expansion of L t (•) at θ t . With this, we have that ∥θ⋆ -θ t ∥ Gt( θt) = O(β t (δ)) (Lemma E.6), avoiding the extra S. However, as G t ( θ t ) = t-1 s=1 ξ(x s , θ t )x s x ⊤s for some welldefined scalar function ξ s , the elliptical potential lemma (as done above) is not applicable due to the explicit dependency on θ t ! This difficulty is analogous to the analysis of Logistic-UCB-2 in Faury et al. (2020) , where a similar difficulty arose because their improved bonus ϵ t,2 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.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 (Eqn. ( 21)). We develop many other intriguing results, such as a novel self-concordance lemma that bounds the difference of μ's with that of µ's times R s (Lemma E.3). We provide the full proof in Appendix E. Here, "R-Bounded" means |r t | ≤ R a.s..Our regret bound Prior state-of-the-art R-Bounded d T κ⋆(T ) + d 2 RR μκ(T ) d T κ⋆(T ) + d 2 R 5 S 2 κ X (T ) (Sawarni et al., 2024, Theorem 4.2) Logistic d T κ⋆(T ) + d 2 κ(T ) d T κ⋆(T ) + d 2 S 2 κ X (T ) (Sawarni etIn Table 2 , we instantiate Theorem 4.1 for various self-concordant GLBs. It can be seen that our OFUGLB attains state-of-the-art regret guarantees in all considered scenarios, either by achieving (linear) or improving upon (bounded, logistic) the known regret bounds! Note that the instantiation for (sub-)Gaussian linear bandits is meant to be a sanity check because tighter confidence sets are available in Flynn et al. (2023) and Chowdhury et al. (2023, Appendix F) .To our knowledge, only a 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 κ ⋆ (T ) in the leading term. 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-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 et 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 κ X (T ) while ours scales as κ(T ), but we have a much better dependency on R (R vs. R 5 ). Despite this seeming gap, as RS-GLinCB relies on an explicit warm-up scheme, our OFUGLB is expected to have superior numerical performance as it avoids excessive exploration in the early phase. We will elaborate more on this issue in Section 5. Also, it should be noted that Sawarni et al. (2024) requires a nonconvex 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 Ω(log2 T ) switches while we require Ω(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 et al., 2010 (Li et al., , 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 a regret bound of O(d √ T + d 2 κ(T )) (up to some dependencies on S) that is κ-free in the leading term. Subsequently, a local minimax regret lower bound of Ω((d/S) T /κ ⋆ (T )) was proven (Abeille et al., 2021 , Theorem 2) 2 , suggesting that more nonlinearity helps, and several works have focused on 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 a tight convex CS for logistic losses, which then directly gives an OFUL-type algorithm. Abeille et al. (2021) first proposed a likelihood ratio-based CS, albeit somewhat loose in S. Lee et al. (2024) proposed a new framework for converting an achievable online learning algorithm to a tighter CS and proposed a UCB algorithm that attains the prior (to this work) state-ofthe-art regret bound of O(dS T /κ ⋆ (T ) + R X (T )) with R X (T ) being arm-set geometry-dependent transient term3 From a computational perspective, Faury et al. (2022) proposed an online Newton stepbased algorithms that attain the regret bound of O(dS T /κ ⋆ (T ) + d 2 S 6 κ(T )) using only O(log t) computational cost and O(1) storage per time step; the computational cost was later improved to O(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 to the explicit warmup, both attain regret with poly(S)-free leading term, e.g., O(d T /κ ⋆ (T ) + d 2 S 2 κ X (T )) by Sawarni et al. (2024) . However, the explicit warmup typically lasts for Ω(κ(T )) or Ω(κ X (T )) time steps, resulting in potentially very large initial regret. This is later verified in our logistic bandits experiments. Our OFUGLB is the first purely optimism-based UCB algorithm (no explicit warmup) that attains a poly(S)-free leading term in the regret.Poisson Bandits. Despite its potential to 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-based algorithms (May et al., 2012) , but without any regret guarantees. To our knowledge, our Theorem 4.1 provides the first regret bound for the (finite-dimensional) 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. 
experiments in logistic bandits: 
 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 4 , which is based upon the previous GitHub repository 5 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 of the considered algorithms and additional experimental results for fixed arm-sets.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 ada-OFU-ECOLog (Faury et al., 2022) . Note that the last two are specific to logistic bandits, 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 is known to perform well in practice (Chapelle and Li, 2011; Russo et al., 2018) , we use a single, untuned hyperparameter guess for EVILL rather than its proposed theoretical value (see Appendix E of their work). For the experimental setup in this section, we set T = 10000, d = 2, and δ = 0.05. We consider time-varying arm-set: at each t ∈ [T ], an arm-setA t ⊂ B d (1) of size |A t | = 20 is uniformly sampled. We set θ ⋆ = S-1 √ d 1 for S ∈ {4, 6, 8, 10}. Lastly, we consider 10 independent repeats per setting for statistical significance.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 OFUGLB, 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. One interesting observation is that even though OFULog+ achieves a 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 to future work. Another is that RS-GLinCB with the exact theoretical hyperparameters (Sawarni et al., 2024) performs the worst, even worse than ada-OFU-ECOLog. We believe this is because their theoretical hyperparameters are not numerically tight, forcing the algorithm to explore throughout the entire duration, probably as their Switching Criterion I (line 4 of their Algorithm 2) is always true. To use RS-GLinCB in practice, one must tune6 the hyperparameters to explicitly control the degree of exploration, which is not the case for our OFUGLB, making ours a viable, practical algorithm with a provable guarantee as well. Lastly, note how the likelihood-based CS, {θ ∈ Θ : L t (θ) ≤ c t } for c t = Θ(log t), resembles an ellipsoid. This is because the "normalized" sublevel value c t /t (as there are t summands in the LHS) gets smaller, making the second-order Taylor expansion more accurate. 
conclusion: 
 This paper introduces a novel and unified likelihood ratio-based CS for generic (convex) GLMs, encompassing widely-used models such as 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 a uniform prior/posterior. We then propose OFUGLB, a generic UCB algorithm applicable to any GLBs, achieving state-of-the-art regret bounds across all self-concordant GLBs. The proof involves novel regret decomposition and maximally avoiding the self-concordance control lemma (Faury et al., 2020, Lemma 9) , which may be of independent interest. Notably, for logistic bandits, OFUGLB is the first pure-optimism-based algorithm that achieves poly(S)-free leading term in the theoretical regret, which is numerically verified to perform best. This work opens up various future directions, which we discuss in detail in Appendix B. et al., 2004; Kaufmann and Koolen, 2021) , which resembles our PAC-Bayesian approach that utilizes a mixture of log-likelihood functions. One drawback is that their main result (Chowdhury et al., 2023, Theorem 3) is instantiated for scalar parameters (e.g., µ ∈ [0, 1] for Bernoulli without observed feature vectors), and not for GLMs. 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 (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 mention in passing that their CS for Gaussian Fast Rates in Statistical Learning. Our goal is to obtain a tight CS for θ ⋆ , which is quite different from that of statistical learning, which is to obtain the optimal decay rate of the ERM. Although it is not immediately clear, we believe they have a connection. To illustrate our suspicion, we recall Example 10 of Grünwald and Mehta (2020) . By taking a uniform prior over a function space F7 and taking the posterior to be randomly sampling from ϵ-ball centered at f , the KL term becomes the metric entropy of F, log N (F, ϵ). Combining this with the Bernstein condition with exponent β, the ERM obtains the minimax rate of O(n -1/(2-β) ), which interpolates between the slow rate O(n -1/2 ) and the fast rate O(1/n), 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 t resembles improper learning and the v-central condition (Foster et al., 2018; van Erven et al., 2015) , which also outputs a mixture of predictors to obtain fast rates.Randomized Exploration for GLBs. Somewhat orthogonal to 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) et al., 2020, Theorem 3 & 5) . Recently, Janz et al. (2024) proposed EVILL, which linearly perturbs the (regularized) log-likelihood loss that achieves a frequentist regret bound8 of O(d 3/2 T /κ ⋆ (T )) for infinite arm-set (Janz et al., 2024, Theorem 1) . In all cases, the extra factor of √ d in the regret (due to posterior variance inflation) is shared across the randomized exploration-based 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 of Li et al. (2024) ; Zhang (2022) or TS-UCB of Baek and Farias (2023) ) to improve randomized exploration for GLBs. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper is purely theoretical.Guidelines:• The answer NA means that the paper poses no 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 a best faith effort.12. Licenses for existing assets Question: 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? 2024), who has a 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: 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 x and unknown θ ⋆ are elements of some function space F. Indeed, by exploiting the inner product structure of GLMs, in the case where F = H k is an RKHS with reproducing kernel k (Paulsen and Raghupathi, 2016) , the inner product ⟨x, θ ⋆ ⟩ can be replaced with k(x, θ ⋆ ). In statistics literature, this is referred to as 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 infinite-dimensional generalization of linear bandits.However, extending our CS to RKHS raises several issues, all related to the fact that the usual properties of finite-dimensional spaces often fail in infinite dimensions (Bogachev, 1998; Da Prato and Zabczyk, 2014) . For instance, it is well-known that there exists no translation-invariant, locally finite, non-trivial Borel measure on infinite-dimensional Banach space (Oxtoby, 1946 , Theorem 1). Then, it is entirely unclear how to extend our current PAC-Bayesian proof of Theorem 3.1 to infinite dimensions, as there is no uniform distribution or likelihood.One promising alternate approach based on 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 (e.g., better dependency onS ′ := ∥θ ⋆ ∥ k ) is non-trivial.Optimality of CS Radius (Theorem 3.1). Another interesting question is 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-theoretic lower bound of Ω log log t t on the estimation error. It would be interesting to use a similar technique to show an information-theoretic 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, κ ⋆ (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/S, indicating a 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 d T /κ ⋆ (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 Bernoulli), 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 isR X (T ) := T t=1 µ(⟨x t,⋆ , θ ⋆ ⟩)1[x t ∈ X -(t)],where X -(t) is the set of detrimental arms with a large reward gap and little information (small conditional variance). R X (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-based algorithms (Faury et al., 2022; Mason et al., 2022; Sawarni et al., 2024) , the transient term always scale with κ, which is not adaptive to the arm-set geometry. Abeille et al. (2021) showed that via an arm-set geometry-dependent analysis for UCB, such κ-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-dependent analysis, and we leave to future work for obtaining both characteristics (poly(S)-free leading term, arm-set geometry-dependent transient term) for logistic bandits and GLBs in general.The reason for being incompatible is as follows. Even when using our new CS (Theorem 3.1 in the regret analysis of Lee et al. (2024) , one still obtains O(dS T /κ ⋆ (T ) + R X (T )), the same as Lee et al. (2024) . This is because in their proof of Lemma 6, which involves deriving an ellipsoidal CS of the form ∥θ -θ ⋆ ∥ Ht ≤ γ t (δ), the covering argument introduces a term in γ t (δ) that always scales as dS 2 log St d , regardless of the likelihood-ratio CS radius. This is unavoidable due to the use of previous self-concordance control (Abeille et al., 2021, Lemma 8) , which gives an extra factor of S, and the use of anytime Freedman's inequality (Lee et al., 2024, Lemma 3) , which results in a multiplicative factor of 1/η for some η ≤ 1/2S. In other words, attaining the best of both worlds may require thinking of an entirely new regret analysis technique. Remark 3 (Detrimental arms for GLBs.). In Abeille et al. (2021) , one key component for allowing such transient term that is adaptive to arm-set geometry is that there exists a Z µ ⊆ R such that sup z∈Zµ μ(z) ≤ 0; e.g., for logistic bandits (µ(z) = (1 + e -z ) -1 ), Z = (-∞, 0]. For general µ, we can define the set of detrimental arms as X -(t) := {x ∈ X t : ⟨x, θ ⋆ ⟩ ∈ Z µ }. Of course, the scaling of R X (T ) depends on various factors, whose precise characterization for µ'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), it is computationally heavy, especially the UCB maximization (line 6 of Algorithm 1). Our ellipsoidal CS is computationally efficient, but it incurs additional factors of S 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 if our new CS may lead to any improvements in algorithms for GLBs beyond OFU, e.g., information-directed 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-efficient RLHF (Das et al., 2024; Shi et al., 2024) . -µ(⟨x, θ ⋆ )| ≤ M < ∞.Then, we have that for any θ ∈ Θ,∇L(θ) = 1 g(τ ) t-1 s=1 -r s + µ(⟨x s , θ⟩) x s 2 ≤ 1 g(τ ) t-1 s=1 r s -µ(⟨x s , θ⟩) ∥x s ∥ 2 ≤ 1 g(τ ) t-1 s=1 r s -µ(⟨x s , θ ⋆ ⟩) + µ(⟨x s , θ ⋆ ⟩) -µ(⟨x s , θ⟩) ≤ 1 g(τ ) t-1 s=1 M + R μ|⟨x s , θ ⋆ -θ⟩| ≤ (M + 2SR μ)(t -1) g(τ ).We first recall some definitions:Definition C.1. A random variable X ∈ R is σ-subGaussian, if P( X -E[X] ≥ t) ≤ 2 exp -t 2 2σ 2 , ∀t ∈ R. Definition C.2 (Definition 3 of Jin et al. (2019)). A random vector X ∈ R d is σ-norm-subGaussian, if P( X -E[X] 2 ≥ t) ≤ 2 exp -t 2 2σ 2 , ∀t ∈ R.Here is the full statement: Proposition C.1. Suppose the GLM is σ-subGaussian. Then, for any δ ∈ (0, 1),EQUATIONProof. Here, as max x∈X ,θ∈Θ | μ(⟨x, θ⟩)| ≤ R μ, we have thatL t = 1 g(τ ) max θ∈Θ t-1 s=1 (r s -µ(⟨x s , θ⟩))x s 2 ≤ 1 g(τ ) max θ∈Θ t-1 s=1 (µ(⟨x s , θ⟩) -µ(⟨x s , θ ⋆ ⟩))x s 2 + 1 g(τ ) t-1 s=1 (r s -µ(⟨x s , θ ⋆ ⟩))x s ≜ys 2 ≤ 2R μS(t -1) g(τ ) + 1 g(τ ) t-1 s=1 y s 2 .We now utilize subGaussian concentrations from Jin et al. (2019) . First note that y s is a martingale difference sequence adapted to Σ s and is norm-subGaussian with (conditional) variance σ 2 be given.Then, by Corollary 7 of Jin et al. (2019) , we have thatEQUATIONThe exact constant 4π is not available in Jin et al. (2019) , as all the constants are hidden under c. This is not useful, especially for practitioners wanting to use the concentration directly. Thus, we tracked the constant from their Corollary 7, the details of which we provide in Lemma C.1.We then conclude by replacing δ with δ/t 2 and applying union bound over t ≥ 1, which yields the Basel sum.Lemma C.1 (Lemma 2 of Jin et al. (2019) ; originally Lemma 5.5 of Vershynin ( 2010)). For any σ-norm-subGaussian random vector X, we have thatsup p∈N p -1/2 E[∥X∥ p ] 1/p ≤ √ πσ.Proof. This follows from brute-force computation. First, we have thatE[∥X∥ p ] = ∞ 0 P[∥X∥ p ≥ t]dt = p ∞ 0 P[∥X∥ ≥ t]t p-1 dt ≤ 2p ∞ 0 t p-1 exp - t 2 2σ 2 dt = 2 p-1 2 σ p pΓ p 2 . Let us denote f (p) := p -1/2 E[∥X∥ p ] 1/p for p ∈ N.Then, using well-known properties of the Gamma function, we have thatf (2p) = σ2 2p-1 4p (2p) 1 2p -1 2 (p -1)! 1 2p = σ p -1 √ 2p! 1 p and f (2p-1) = σ2 2p-2 2(2p-1) (2p-1) 1 2p-1 -1 2 √ π (2p -3)!! 2 p-1 1 2p-1 = σ(2p-1) 1 2p-1 -1 2 √ π(2p -3)!! 1 2p-1 ,where we define (-1)!! := 1.Then, we have thatf (2p) (i) < σ p -1 ( √ 2p p ) 1 p = σ2 1 4p ≤ σ2 1 4, where (i) follows from p! < p p . We also have thatf (2p -1) (i) < σ(2p -1) 1 2p-1 -1 2 √ π(2p -1) p 1 2p-1 (ii) < σ √ π(2p -1) 1 2p-1 (iii) < σ √ π,where (i) follows from (2p-3)!! < (2p-1) p , (ii) follows from p 2p-1 > 1 2 , and (iii) follows from the observations that for z ≥ e, f (z) = ( √ πz) 1/z is decreasing 9 , andf (1) = √ π > f (3) = (3 √ π) 1/3 .Finally, as 2 1/4 < √ π, we have that sup p∈N f (p) ≤ √ πσ.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 δ ∈ (0, 1): when S > 1,EQUATION) 9 d dz log f (z) = √ π 1-log z z 2 ≤ 0, ∀z ≥ e.where C(S) := 1 4 (1 -2e -S )(e S + 2S + 2 log 2(1-2e -S ) e) + 2Se S . When S ≤ 1,EQUATIONwhere C(S) := 1 16 e S + 4S + 4 log(8 + 2e S ) + 2Se S .Proof. Proceeding similarly as in the previous subsection, we first have thatEQUATION)where y s = (r s -e ⟨xs,θ⋆⟩ )x s is the martingale difference sequence satisfyingE[y s |Σ s ] = 0 as r s |Σ s ∼ Poi(⟨x s , θ ⋆ ⟩).We now modify the proof of Corollary 7 of Jin et al. (2019) (which is based upon the celebrated Chernoff-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 x ∈ B d (1), r ∼ Poi(λ), and λ > 0. Then, for the Hermitian dilation (Tropp, 2015, Definition 2.1.5) of y, Y := 0 y ⊤ y 0 , we have that Ee θY ⪯ exp F (θ, λ)I d+1 for |θ| < 1 2 , where F (θ, λ) := λ|θ| + log(2|θ|) + log e -λ 2 1 2 -|θ| + λ .We also recall the Lieb's trace inequality: E tr exp   -θ 2 I d+1 t-1 s=1 F (θ, λ s ) + θ t-1 s=1 Y s   = E     E t-1   tr exp   -θ 2 I d+1 t-1 s=1 F (θ, λ s ) + θ t-1 s=1 Y s          ≤ E   tr exp   -θ 2 I d+1 t-1 s=1 F (θ, λ s ) + θ t-2 s=1 Y s + log E t-1 e θYt-1      (Theorem C.3) ≤ E   tr exp   -θ 2 I d+1 t-1 s=1 F (θ, λ s ) + θ t-2 s=1 Y s + F (θ, λ t-1 )I d+1      (Lemma C.2, A ⪯ B ⇒ e C+A ⪯ e C+B ) ≤ E   tr exp   -θ 2 I d+1 t-2 s=1 F (θ, λ s ) + θ t-2 s=1 Y s      ≤ • • • ≤ tr exp(0I d+1 ) = d + 1.Thus, for any ρ ≥ 0,P    t-1 s=1 y s ≥ θ t-1 s=1 F (θ, λ s ) + ρ θ    = P    t-1 s=1 Y s ≥ θ t-1 s=1 F (θ, λ s ) + ρ θ    ( s Y s is a rank-2 matrix with eigenvalues ± s y s 2 ) = 2P   λmax   t-1 s=1 Y s   ≥ θ t-1 s=1 F (θ, λ s ) + ρ θ    (Y s 's are symmetric) = 2P     λ max   exp   θ t-1 s=1 Y s      ≥ exp   θ 2 t-1 s=1 F (θ, λ s ) + ρ       ≤ 2P   tr exp   θ t-1 s=1 Y s   ≥ exp   θ 2 t-1 s=1 F (θ, λ s ) + ρ      ≤ 2e -ρ E tr exp   -θ 2 t-1 s=1 F (θ, λ s ) + θ t-1 s=1 Y s   (Markov's inequality) ≤ 2(d + 1)e -ρ . (Lemma C.2)Finally, by reparametrizing, we have that for any δ ∈ (0, 1),EQUATIONwhere we recall that F (θ, λ) = λθ + log(2θ) + log e -λ 2 1 2 -θ + λ for θ > 0. First, when S > 1, let us choose θ = 1 2 -e -S , which is guaranteed to be positive. Noting that λ s = e ⟨xs,θ⋆⟩ ≤ e S , we haveF 1 2 -e -S , λ s ≤ e S 1 2 -e -S + log(1 -2e -S ) + log(2e S ) = 1 2 e S + S + log 2(1 -2e -S ) e .Thus, the RHS of Eqn. ( 15)EQUATION)For the case S ≤ 1, choosing θ = 1 4 , the RHS becomesEQUATION)Finally, we conclude by parametrizing δ as δ/t 2 , applying union bound over t ≥ 1, and using the Basel sum.Proof of Lemma C.2. We first have thatEe θY ( * ) = I d+1 + ∞ p=1 θ p EY 2p (2p)! ⪯ I d+1 + ∞ p=1 θ 2p E ∥y∥ 2p (2p)! I d+1 = E e θ∥y∥ + e -θ∥y∥ 2 I d+1 ⪯ E e |θ||r-λ| I d+1 ,where ( * ) follows from the observation that EY 2p+1 = 0. We now recall a concentration result for Poisson distribution:Lemma C.3 (Theorem 1 of the note by C. Canonne). P(|r λ+x) .-y| ≥ x) ≤ 2e -x 2 2(Then, we have thatE[e |θ||r-λ| ] = ∞ 0 P(e |θ||r-λ| > k)dk (dk is the Lebesgue measure) ≤ 1 + ∞ 1 P(e |θ||r-λ| ≥ k)dk ≤ 2 ∞ 1 e -(log k/|θ|) 2 2(λ+log k/|θ|) dk (Lemma C.3) = 2|θ| ∞ 0 e -u 2 2(λ+u) +|θ|u du = 2|θ| ∞ λ e -u 2 2(λ+u) +|θ|u du + λ 0 e -u 2 2(λ+u) +|θ|u du ≤ 2|θ| ∞ λ e -( 1 2 -|θ|)u du + λe |θ|λ ( u 2 2(λ+u) ≥ 1 2 u for u ≥ λ) ≤ 2|θ| 1 1 2 -|θ| e -( 1 2 -|θ|)λ + λe |θ|λ = exp   F (θ, λ) ≜ λ|θ| + log(2|θ|) + log e -λ 2 1 2 -|θ| + λ   .First, similarly to prior works on logistic bandits (Abeille et al., 2021; Lee et al., 2024) , let us define the following quantities:G t (θ, ν) := 1 g(τ ) t-1 s=1 αs (θ, ν)x s x ⊤ s , αs (θ, ν) := 1 0 (1 -v) μ ⟨x s , θ + v(ν -θ)⟩ dv.(We will later come back to these quantities in the regret analysis.)Then, by Taylor's theorem with integral remainder and first-order optimality condition for convex constrained optimization10 , we have that for any λ ≥ 0,β t (δ) 2 ≥ L t (θ) -L t ( θ t ) = ⟨∇L t ( θ t ), θ -θ t ⟩ ≥0 + θ -θ t 2 Gt( θt,θ) ≥ θ -θ t 2 Gt( θt,θ)+λI d -λ θ -θ t 2 2 ≥ θ -θ t 2 Gt( θt,θ)+λI d -4S 2 λ.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 µ be increasing ( μ ≥ 0, which is basically Assumption 3) and self-concordant with constant R s (as in Assumption 4). Let Z ⊂ R be bounded. Then, the following holds for any z 1 , z 2 ∈ Z:1 0 (1 -v) μ(z 1 + v(z 2 -z 1 ))dv ≥ μ(z 1 ) 2 + R s |z 1 -z 2 | .This then implies that G t (θ, ν) ⪰ E.1 Key Ideas of the ProofWe will first expand upon the proof sketch provided in Section 4.1 of the main text. Recall the UCB strategy: (x t , θ t ) ← arg max x∈Xt,θ∈Ct ⟨x, θ⟩.Why Prior Proof Technique Fails. We first show that even though we have a tight CS (Theorem 3.1), naïvely 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. To see this, let us first recall the existing analyses.The prior proof starts by bounding the regret by T t=1 ⟨ μt (θ ⋆ )x t , θ t -θ ⋆ ⟩ (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. the (regularized) HessianH t (θ ⋆ ) = λI + ∇ 2 L t (θ ⋆ ) = λI + t-1 s=1 μs (θ ⋆ )x s x ⊤ s , each summand is bounded as μt (θ ⋆ )⟨x t , θ t -θ ⋆ ⟩ ≤ μt (θ ⋆ ) ∥x t ∥ Ht(θ⋆) -1 ∥θ t -θ t ∥ Ht(θ⋆) + ∥θ ⋆ -θ t ∥ Ht(θ⋆) .The prior proof then uses Taylor expansion (again) and self-concordant control (Abeille et al., 2021, Lemma 8) to obtain ∥θ t -θ t ∥ Ht(θ⋆) = O Sβ T (δ) 2 from the likelihood-based confidence set L t (θ t ) -L t ( θ t ) ≤ β T (δ) 2 ,which introduces a factor of S. This then leads tot μt (θ ⋆ )⟨x t,⋆ -x t , θ ⋆ ⟩ ≲ Sβ T (δ) 2 t μt (θ ⋆ ) ≤ √ T /κ⋆(T ) t μt (θ ⋆ )x t 2 Ht(θ⋆) -1elliptical potential lemma (Abbasi-Yadkori et al., 2011) , resulting in a regret whose leading term is not poly(S)-free.Towards Our Approach. To obtain a poly(S)-free leading term in the regret, we maximally avoid the self-concordance lemma (Abeille et al., 2021, Lemma 8) . To do this, our proof begins by obtaining an elliptical CS w.r.t. G t ( θ t ), derived from the first-order Taylor expansion of L t (•) at θ t . With this, we have that ∥θ ⋆ -θ t ∥ Gt( θt) = O(β T (δ) 2 ) (Lemma E.6), avoiding the extra S compared to the prior proof that derives an elliptical CS w.r.t. H t (θ ⋆ ).However, the main difficulty of the proof is that G t ( θ t ) is not in a suitable form for elliptical potential arguments. To see this clearly, consider the following natural optimistic upper-bound of the instantaneous regret: µ(⟨x t,⋆ , θ ⋆ ⟩) -µ t (θ ⋆ ) ≤ µ t (θ t ) -µ t (θ ⋆ ) (Optimism) = µ t (θ t ) -µ t ( θ t ) -µ t ( θ t ) + µ t (θ ⋆ ) ≤ 2|µ t (θ ′ t ) -µ t ( θ t )| ≲ μt ( θ t )|⟨x t , θ ′ t -θ t ⟩|( θ t )|⟨x t , θ ′ t -θ t ⟩| ≤ μt ( θ t ) ∥x t ∥ Gt( θt) -1 ∥θ t -θ t ∥ Gt( θt) ≲ μt ( θ t )β T (δ) ∥x t ∥ G -1 t ( θt). This successfully avoids using previous self-concordant control (Abeille et al., 2021, Lemma 8) , and thus seemingly getting closer to obtaining a poly(S)-free regret. Omitting details, the final step is to sum the above over t ∈ [T ] and apply the elliptical potential lemma (EPL; Abbasi-Yadkori et al. ( 2011)). EPL is applicable only when G t ( θ t ) can be written as λI + t-1 s=1 μs ( θ s )x s x ⊤ s for some λ > 0. However, as G t ( θ t ) = t-1 s=1 ξ(x s , θ t )x s x ⊤ s for some scalar function ξ s , the EPL is not applicable due to the explicit dependency on θ t , not on { θ s } s∈[t-1] . 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.Our Approach. The key insight is that if we could designate a "worst-case" θ s for each time step s such that G t ( θ t ) ⪰ λI + t-1 s=1 μ(θ s )x s x ⊤ s =: Q t , then we can perform the following:μt ( θ t )|⟨x t , θ ′ t -θ t ⟩| ≤ μt (θ t )|⟨x t , θ ′ t -θ t ⟩| + | μt ( θ t ) -μt (θ t )||⟨x t , θ ′ t -θ t ⟩|where the first term is now be bounded byO μt (θ t )β T (δ)∥x t ∥ Q -1 t .We can now apply the EPL when summing over t ∈ [T ], thanks to the form of Q t . The second term turns out to be a lower order term via our new self-concordant control that doesn't give additional S-dependency (Lemma E.3).We note that this is analogous to the analysis of Logistic-UCB-2 in Faury et al. (2020) , where a similar difficulty arose because their improved bonus ϵ t,2 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 a confidence set defined as an intersection over all the confidence sets used so far, or by using an additional constraint set W t 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:µ(⟨x t,⋆ , θ ⋆ ⟩) -µ t (θ ⋆ ) ≤ µ t (θ t ) -µ t (θ ⋆ ) ≤ 2|µ t (ν t ) -µ t ( θ b(t) )|,where we define (b(t),ν t ) := arg max b∈[t,T ],θ∈C b |µ t (θ) -µ t ( θ b )|.That is, we are bounding the instantaneous regret by how large the difference can be from the current confidence set and how large the difference can be from the future confidence sets. With this, we can then define θt := arg min θ∈ b∈[t,T ] C b μt (θ), 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 a novel self-concordance lemma that bounds the difference of μ's with that of µ's times R s (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.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 λ > 0 to be chosen later,EQUATIONEQUATIONandαt (θ, ν) := 1 0 (1 -v) μt θ + v(ν -θ) dv, G t (θ, ν) := λI + 1 g(τ ) t-1 s=1 αs (θ, ν)x s x ⊤ s . (21)θt 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 on poly(S) and κ 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 {∀t ≥ 1, θ ⋆ ∈ C t } holds, which is with probability at least 1 -δ by Theorem 3.1.Regret Decomposition. Define the set of timesteps satisfying the "warmup conditions":EQUATION)Then we have the following regret decomposition:Reg(T ) = t∈I T µ(⟨x t,⋆ , θ ⋆ ⟩) -µ(⟨x t , θ ⋆ ⟩) + t̸ ∈I T µ(⟨x t,⋆ , θ ⋆ ⟩) -µ(⟨x t , θ ⋆ ⟩) ≜ Reg I (T ) ≤ 2R µ,⋆ |I T | + Reg I (T ) ≤ 2R µ,⋆ t∈[T ] 1 μt ( θt )x t H-1 t ≥ 1 + 2R µ,⋆ t∈[T ] 1 ∥x t ∥ V -1 t ≥ 1 + Reg I (T ) (Definition of I T ) ≤ 4dR µ,⋆ log 2 log 1 + R μ 2λg(τ ) log 2 + log 1 + 1 2κ(T )λg(τ ) log 2 + Reg I (T ).(EPCL (Lemma E.1))We now focus on bounding the last term:Reg I (T ) = t̸ ∈I T µ t,⋆ (θ ⋆ ) -µ t ( θ t ) + t̸ ∈I T µ t ( θ t ) -µ t (θ ⋆ ) (µ t (•) := µ(⟨x t , •⟩), µ t,⋆ (•) := µ(⟨x t,⋆ , •⟩)) ≤ t̸ ∈I T µ t (θ t ) -µ t ( θ t ) + t̸ ∈I T µ t ( θ t ) -µ t (θ ⋆ ) (optimism -line 7 of Algorithm 1) ≤ 2 t̸ ∈I T max b∈[t,T ] max θ∈C b µ t (θ) -µ t ( θ b ) = 2 t̸ ∈I T µ t (ν t ) -µ t ( θ b(t) ) . (Eqn. (19))Using Taylor's theorem with integral remainder form, we have that for t ̸ ∈ I T ,µ t (ν t ) -µ t ( θ b(t) ) = μt ( θ b(t) )⟨x t , ν t -θ b(t) ⟩ + µt(νt) µt( θ b(t) ) (µ t (ν t ) -z)μ t (z)dz ≤ μt ( θ b(t) ) ⟨x t , ν t -θ b(t) ⟩ + ⟨x t , ν t -θ b(t) ⟩ 2 1 0 (1 -v) μt θ b(t) + v(ν t -θ b(t) ) dv (triangle inequality, reparametrization) ≤ μt ( θ b(t) ) ⟨x t , ν t -θ b(t) ⟩ + R s ⟨x t , ν t -θ b(t) ⟩ 2 1 0 (1 -v) μt θ b(t) + v(ν t -θ b(t) ) dv = αb(t) ( θ b(t) ,νt) (Assumption 4) ≤ μt ( θt ) ⟨x t , ν t -θ b(t) ⟩ + μt ( θt ) -μt ( θ b(t) ) ⟨x t , ν t -θ b(t) ⟩ + R s ⟨x t , ν t -θ b(t) ⟩ 2 αb(t) ( θ b(t) , ν t ) ≤ μt ( θt ) ∥x t ∥ G b(t) ( θ b(t) ,νt) -1 ν t -θ b(t) G b(t) ( θ b(t) ,νt) ≜At + μt ( θt ) -μt ( θ b(t) ) ∥x t ∥ G b(t) ( θ b(t) ,νt) -1 ν t -θ b(t) G b(t) ( θ b(t) ,νt) ≜Bt + R s ν t -θ b(t) 2 G b(t) ( θ b(t) ,νt) αb(t) ( θ b(t) , ν t ) ∥x t ∥ 2 G b(t) ( θ b(t) ,νt) -1 ≜Ct , (Cauchy-Schwartz inequality)where G is as defined in Eqn. ( 21). As one will see soon, t A t is the leading term, and t (B t +C t ) is the transient term.We bound each sum separately:Bounding t A t . t̸ ∈I T A t = t̸ ∈I T μt ( θt ) ∥x t ∥ G b(t) ( θ b(t) ,νt) -1 ν t -θ b(t) G b(t) ( θ b(t) ,νt) ≤ 4λS 2 + β T (δ) 2 t̸ ∈I T μt ( θt ) ∥x t ∥ G b(t) ( θ b(t) ,νt) -1 (ν t ∈ C b(t) , Lemma E.6 (i)) ≤ 4λS 2 + β T (δ) 2 t̸ ∈I T μt ( θt ) t̸ ∈I T μt ( θt ) ∥x t ∥ 2 G b(t) ( θ b(t) ,νt) -1(Cauchy-Schwartz inequality)≤ 4λS 2 + β T (δ) 2 t̸ ∈I T μt ( θt ) 2g(τ ) t̸ ∈I T μt ( θt ) ∥x t ∥ 2 H-1 t (Lemma E.5) ≤ 2g(τ ) 4λS 2 + β T (δ) 2 t̸ ∈I T μt ( θt ) t∈[T ] min 1, μt ( θt ) ∥x t ∥ 2 H-1 t .(Definition of I T )Note that now, Ht is of the form such that we can use the EPL with μt ( θt )x t :t̸ ∈I T A t ≤ 2 dg(τ )(4λS 2 + β T (δ) 2 ) log 1 + R μT dλ t̸ ∈I T μt ( θt ). (EPL (Lemma E.2)) ≤ 2 dg(τ )(4λS 2 + β T (δ) 2 ) log 1 + R μT dλ t∈[T ] μt,⋆ (θ ⋆ ) + t̸ ∈I T μt ( θt ) -μt,⋆ (θ ⋆ ) (µ t,⋆ (•) := µ(⟨x t,⋆ , •⟩)) = 2 dg(τ )(4λS 2 + β T (δ) 2 ) log 1 + R μT dλ T κ ⋆ (T ) + t̸ ∈I T μt ( θt ) -μt,⋆ (θ ⋆ ) .The last term in the square root is bounded as follows:t̸ ∈I T μt ( θt ) -μt,⋆ (θ ⋆ ) = t̸ ∈I T μt ( θt ) -μt (θ ⋆ ) + t̸ ∈I T μt (θ ⋆ ) -μt,⋆ (θ ⋆ ) ≤ R s    t̸ ∈I T µ t ( θt ) -µ t (θ ⋆ ) + t̸ ∈I T µ t (θ ⋆ ) -µ t,⋆ (θ ⋆ )    (Lemma E.3) ≤ R s    t̸ ∈I T µ t (ν t ) -µ t (θ ⋆ ) + t̸ ∈I T µ t,⋆ (θ ⋆ ) -µ t (θ ⋆ )    ≤ R s    t̸ ∈I T µ t (ν t ) -µ t ( θ t ) + t̸ ∈I T µ t (θ ⋆ ) -µ t ( θ t ) + Reg I (T )    ≤ 4R s t̸ ∈I T µ t (ν t ) -µ t ( θ b(t) ) . (Definition of (ν t , b(t)) Bounding t B t . t̸ ∈I T B t = t̸ ∈I T μt ( θt ) -μt ( θ b(t) ) ∥x t ∥ G b(t) ( θ b(t) ,νt) -1 ν t -θ b(t) G b(t) ( θ b(t) ,νt) ≤ 4λS 2 + β T (δ) 2 t̸ ∈I T μt ( θt ) -μt ( θ b(t) ) ∥x t ∥ G -1 b(t) ( θ b(t) ,νt) (ν t ∈ C b(t) , Lemma E.6 (i)) ≤ R s 4λS 2 + β T (δ) 2 t̸ ∈I T µ t ( θt ) -µ t ( θ b(t) ) ∥x t ∥ G -1 b(t) ( θ b(t) ,νt) .(Lemma E.3)We then inevitably introduce a κ(T ) dependency to use the elliptical potential arguments w.r.t. V t :t̸ ∈I T B t ≤ R s 4λS 2 + β T (δ) 2 2g(τ )κ(T ) t̸ ∈I T µ t ( θt ) -µ t ( θ b(t) ) ∥x t ∥ V -1 t (Lemma E.4, b(t) ≥ t) ≤ R s 4λS 2 + β T (δ) 2 2g(τ )κ(T ) t̸ ∈I T µ t (ν t ) -µ t ( θ b(t) ) ∥x t ∥ V -1 t (Definition of ν t (Eqn. (19))) ≤ 4R s R μκ(T )(4λS 2 + β T (δ) 2 ) g(τ ) t̸ ∈I T ∥x t ∥ 2 V -1 t (ν t , θ b(t) ∈ C b(t) , Lemma E.6 (ii)) ≤ 4R s R μκ(T )(4λS 2 + β T (δ) 2 ) g(τ ) t∈[T ] min 1, ∥x t ∥ 2 V -1 t (Definition of I T ) ≤ 8dR s R μκ(T )(4λS 2 + β T (δ) 2 ) g(τ ) log 1 + T 2dg(τ )κ(T )λ . (EPL (Lemma E.2))Bounding t C t . We proceed similarly as bounding t B t :t̸ ∈I T C t ≤ R s 4λS 2 + β T (δ) 2 t̸ ∈I T αb(t) ( θ b(t) , ν t ) ∥x t ∥ 2 G b(t) ( θ b(t) ,νt) -1 (ν t ∈ C b(t) , Lemma E.6 (i)) ≤ R s R μg(τ )κ(T ) 4λS 2 + β T (δ) 2 t̸ ∈I T ∥x t ∥ 2 V -1 t (Lemma E.4, b(t) ≥ t) ≤ R s R μg(τ )κ(T ) 4λS 2 + β T (δ) 2 t∈[T ] min 1, ∥x t ∥ 2 V -1 t (Definition of I T ) ≤ 2dR s R μg(τ )κ(T ) 4λS 2 + β T (δ) 2 log 1 + T 2dg(τ )κ(T )λ (EPL (Lemma E.2))Wrapping Up. Let us choose λ = 1 4S 2 , and let us denote A ≲ B if A ≤ cB for some absolute constant c > 0. Then, combining everything, we have:t̸ ∈I T µ t (ν t ) -µ t ( θ b(t) ) ≤ t̸ ∈I T A t + t̸ ∈I T B t + t̸ ∈I T C t ≲ β T (δ) dg(τ ) log 1 + R μST d T κ ⋆ (T ) + R s t̸ ∈I T µ t (ν t ) -µ t ( θ b(t) ) + dR s R μκ(T )β T (δ) g(τ ) log 1 + ST dg(τ )κ(T ) ,as the upper bound for t C t is asymptotically negligible compared to that of t B t . This is of the formX ≲ A √ B + R s X + C with X := t̸ ∈I T µ t (ν t ) -µ t ( θ b(t) ) , which then implies X ≲ A √ B + A √ R s + Cthanks to an 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.The following are the elliptical potential arguments, which we state without proof:Lemma E.1 (Elliptical Potential Count Lemma; EPCL 11 ). For X, L > 0, let x 1 , • • • , x T ∈ B d (X) be a sequence of vectors, V t := λI + t-1 s=1 x s x ⊺s , and let us define the following:EQUATION)Lemma E.2 (Elliptical Potential Lemma; EPL12 ). Let x 1 , • • • , x T ∈ B d (X) be a sequence of vectors and V t := λI + t-1 s=1 x s x ⊺ s . Then, we have thatEQUATION)The following is a "self-bounding" property of self-concordant function:Lemma E.3. For θ, ν ∈ R d , | μt (θ) -μt (ν)| ≤ R s |µ t (θ) -µ t (ν)|Proof. This follows from direct computation:| μt (θ) -μt (ν)| = ⟨x t , θ -ν⟩ 1 0 μt (ν + v(θ -ν)dv ≤ ⟨x t , θ -ν⟩ 1 0 μt (ν + v(θ -ν) dv ≤ R s ⟨x t , θ -ν⟩ 1 0 μt (ν + v(θ -ν) dv (Assumption 4)F Alternate CS via Discrete Uniform Prior and Covering ArgumentIn 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 a discrete uniform prior. This is a 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 t := max θ∈Θ ∇L t (θ) 2 be the Lipschitz constant of L t (•) that may depend on {(x s , r s )} t-1 s=1 . Then, we have P[∃t ≥ 1 :θ ⋆ ̸ ∈ C t (δ)] ≤ δ, where β t (δ) 2 = log π 2 t 2 6δ + inf c∈(0,5S] d log 5S c + cL t ≤ log π 2 t 2 6δ + d log(1 ∨ 5SL t ) + 1,where the last inequality follows from the choice c = 5S ∧ 1 Lt .Proof. Consider p = U({θ i } i∈[N ] ), where the θ i 's will be determined later. In that case, we have:EQUATIONFrom the proof of Lemma 3.1, one can see that E[M t (θ)|θ] = 1 where E is w.r.t. the randomness of the sequential data (i.e., of L t (•)). Then, by Markov's inequality, for any δ ∈ (0, 1),EQUATIONwhere again, P is w.r.t. the randomness of L t (•). Then, we have thatEQUATION))Combining this with Eqn. (25), we have thatP L t (θ ⋆ ) -min i∈[N ] L t (θ i ) ≤ log N δ ≥ 1 -δ, ∀t ≥ 1.By reparametrizing δ as δ t 2 and taking the union bound over t ≥ 1, we have that by the Basel sum,EQUATIONThus, the following holds with probability at least 1 -δ: for all t ≥ 1,L t (θ ⋆ ) -min θ∈Θ L t (θ) ≤ log π 2 t 2 6δ + log N + min i∈[N ] L t (θ i ) -min θ∈Θ L t (θ) ≤ log π 2 t 2 6δ + log N + L t min i∈[N ] θ i -θ t 2 , ( θ t = arg min θ∈Θ L t (θ))where we recall that L t is the Lipschitz constant of L t (•).We choose {θ i } to be a c-net of Θ for c ∈ (0, 5S]. For time-varying arm-sets, the randomness of the arm-sets is shared across all the algorithms, i.e., at each time-step t, 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 SciPy (Virtanen et al., 2020) for computing the norm-constrained MLE. This minimizes the effect of optimization errors whenever possible, allowing us to compare the algorithms clearly from a statistical perspective. For OFUGLB, EMK, RS-GLinCB, and OFULog+, SLSQP is utilized to compute the UCB index as well. Lastly, we use the same implementation of ada-OFU-ECOLog and RS-GLinCB as in the publicly available GitHub repository of Faury et al. (2022) 13 and Sawarni et al. (2024) 14 , respectively. For RS-GLinCB, we use the exact theoretical hyperparameters as provided in Sawarni et al. (2024) . For EVILL, we use τ = K = 20 for the initial warmup period for collecting prior observations (each arm is pulled once in a round-robin fashion), λ = 1 for the ℓ 2 -regularization coefficient for the MLE, and a = 1 for the perturbation scale. Results and Discussions. The results are shown in Figure 2 . There are some common characteristics compared to the plots for time-varying arm-sets (Figure 1 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 RS-GLinCB still performs the worst. Also, OFUGLB, 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 at S ∈ {8, 10}. In our settings, T = 10000 is still in a transient phase of all the algorithms and, thus, yet to reach the asymptotic regime. To see the logarithmic-looking 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 S = 10, it seems that OFUGLB-e 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 at 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 a close look at S ∈ {6, 8}, note that there is a phase at which OFUGLB-e seems to perform the best in the beginning, but in the end its regret increases well beyond other well-performing baselines: OFUGLB, EMK, and EVILL. Remark 4. Although our current implementation always uses SLSQP for all the optimization procedures (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 is possible as the arm-set is fixed); see Section 3.3 of Kveton et al.(2020) and the original implementation15 of EVILL using IRLS.NeurIPS Paper Checklistthe linear-algebraic dimension (minimum number of basis vectors spanning it) of the affine span of Θ in R d .In their statement, dependency on S is ignored. By tracking their lower bound proof, one can see that it leads to an extra factor of 1/S.One may wonder why our Theorem4.1's transient term always scales as κ(T ). See Appendix B for further discussions on this interesting difference. 4 https://github.com/nick-jhlee/logistic_bandit 5 https://github.com/criteo-research/logistic_banditThis is the case in their GitHub implementation, where heuristic values were used for their experiments. Additionally, their algorithm requires the knowledge of κ⋆.satisfying some regularity conditions including Lipschitzness and boundednessAlthough they considered fixed arm-set, their proof can be easily extended to time-varying arm-sets, the only difference being the length of their warm-up period τ now being dependent on the arm-set distribution.Let Θ be convex and f : Θ → R be convex and differentiable. Then, θ * ∈ arg min θ∈Θ f (θ) if and only if ⟨∇f (θ * ), ν -θ * ⟩ ≥ 0, ∀ν ∈ Θ(Boyd and Vandenberghe, 2004, Section 4.2.3).This is a generalization of Exercise 19.3 ofLattimore and Szepesvári (2020), presented (in parallel) at Lemma 7 ofGales et al. (2022) and Lemma 4 ofKim et al. (2022).Lemma 11 of Abbasi-Yadkori et al. (2011).https://github.com/louisfaury/logistic_bandithttps://github.com/nirjhar-das/GLBandit_Limited_Adaptivityhttps://github.com/DavidJanz/EVILL-code 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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).

Regarding 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.
questions: 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.

* 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?

* Can you elaborate on the connection with Theorem 3 of Foster et al. on Section 3.2?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: I think improving dependency on $S$ gains significant relevance, once it yields a practical algorithm. 
If 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.

- 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)$.

- 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).

- 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).


This 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$.
questions: questions: ### Questions:
1) 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?
2) 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.
3) What is the dependency of Theorem 3.2 on $S$? Mainly, do the ellipsoid sets blow up for logistic bandits? 
4) 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). 
5) 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?
6) Is Theorem 4.1 minimax optimal, e.g. wrt the lower-bound of Abeille 2021?
7) In Fig 1-(c), is the logistic CS is automatically an ellipsoid, or is it just resembling one?
8) Are you using the theoretical $\beta_t(\delta)$ for Fig (1-a) and (1-b)? 
_____
### Small typos & Suggestions

- [Lines 57, 67, 69] space before parenthesis missing
- [Line 72] notation for derivates isn't coherent. Both $\dot{}$ and ${}^\prime$ are used.
- [Line 73] would make more sense to write for $t \geq 1$, since all statements are anytime.
- [Line 95] The sentence does not have a verb. Perhaps instead of "Despite" authors meant "Exists".
- [Line 100] First time I read "unbounded GML" I was confused. Would be good to mention that this refers to values o $\mu$.
- [Theorem 3.1] Second line should be $\mathcal L_t$, the subscript is missing.
- [Line 156] It is not clear what "it" refers to. Perhaps swap it out for "the analysis".
- [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.
- [Line 173] This line reads vaguely and informally, "even" is used twice. It's best if the justification is made rigorous or removed entirely. 
- [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: 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. 

Practical limitations and applicability are not adequately addressed.
paper_summary: paper_summary: Confidence intervals for GLMs using a PAC-Bayes approach.
strength_weakness: strength_weakness: 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.

Some examples of problematic claims (emphasis mine in all quotes):
1) 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?).
2) 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.
3) 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. 
4) 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!).
5) 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?* 

Other 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.

Some minor typos:
- 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.
- Line 95-97, second half of sentence seems to be missing
- Line 129, the definition looks like the likelihood ratio, not the log-likelihood ratio as claimed
- Theorem 3.2, second line
- Line 82, the set in probability is wrong
- Line 75 rewards should be in filtration
questions: questions: See weaknesses section.
limitations: limitations: .
paper_summary: paper_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.
Several examples of GLM are discussed, and minimal numerical experiments are reported. The comparison with OFULLog+ is convincingly exposed, both in theory and in practice.
strength_weakness: strength_weakness: The submission is correctly written, but with a number of clumsinesses (some are listed below). 
The 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.

l.69 undefined notation \mathcal{B}^d(1)
l.77 give a reference
l.80 could you precise what is R_\mu in those examples?
l.95 the sentence is grammatically wrong, something is missing
Thm. 3.1: replace "where" by "for the choice"
l.129 it is not the log-likelihood but the likelihood
l.583 is it not possible to suggest a proof instead of a reference to "WoframAlpha" (to a plot?)
questions: 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: limitations: This section does not really seem relevant to this mostly theoretical submission

Comments: title: Reviewer discussion
Review of the review
References for the rebuttal
comment: Thank you very much for your detailed response, I have no more questions for now.
Thank you for your response and the new benchmarks.

Interesting to see how close EMK and OfUGLB perform (statistically and computationally). I still think that you might be able to demonstrate a bigger advantage, if you consider significantly larger values for $S$ in the experiments, or consider benchmarks in which the true $S$ is not known.
I wanted to voice that I find this review to be an unfair, if not adversarial, assessment of the work. The review makes some comments about writing style until line ~110 and then something about the conclusion. This makes me wonder, if the reviewer read the full paper with sufficient care and give it enough thought.

It has become common fashion to emphasize the paper's contributions in the introduction. Compared to the standard, I would **not** say that this paper is heavily exaggerating the results that follows. However, I realize that qualitative descriptions of the results can through-off a reader, e.g. them getting mad over the usage of a simple adjective ("cleverly").

I think the paper indeed makes non-trivial contributions, and has a fresh approach (combining Ville's with the change of measure technique in the proof) that I have not seen in this immediate area of work. 
In their rebuttal, the authors also provide a benchmark including the most related work, even reporting the runtimes. The benchmark is still for a synthetic dataset, with small values of $S$, but already gives some insight into the average case performance of the algorithms (as the bounds are worst-case wrt the reward class).

I think the review focuses on form/presentation, and misses out on the content. I am not sure how useful or reliable is this type of review, to make a fair assessment of soundness and relevance of the contributions.
Let us collect all the relevant references for our rebuttal below.


[1] Lee et al. “Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion.” AISTATS 2024.


[2] Abeille et al. “Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits.” AISTATS 2021.


[3] Faury et al. “Jointly Efficient and Optimal Algorithms for Logistic Bandits.” AISTATS 2022.


[4] Emmenegger et al., “Likelihood Ratio Confidence Sets for Sequential Decision Making.” NeurIPS 2023.


[5] Sawarni et al. “Generalized Linear Bandits with Limited Adaptivity.” arXiv preprint arXiv:2404.06831.


[6] Neiswanger & Ramdas. “Uncertainty quantification using martingales for misspecified Gaussian processes.” ALT 2021.


[7] Flynn et al. “Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures.” NeurIPS 2023


[8] Boyd & Vandenberghe. “Convex Optimization.” Cambridge University Press, 2004.


[9] Alquier. “User-friendly Introduction to PAC-Bayes Bounds.” Foundations and Trends in Machine Learning: Vol. 17: No. 2, pp 174-303, 2024.


[10] Chugg et al. “A Unified Recipe for Deriving (Time-Uniform) PAC-Bayes Bounds.” Journal of Machine Learning Research, 24(372):1-61, 2023.


[11] Faury et al. “Improved Optimistic Algorithms for Logistic Bandits.” ICML 2020.


[12] Foster et al. “Logistic Regression: The Importance of Being Improper.” COLT 2018.


[13] Gawarecki & Mandreka. “Stochastic Differential Equations in Infinite Dimensions with Applications to Stochastic Partial Differential Equations.” Springer Berlin, Heidelberg, 2010.


[14] McCullagh & Nelder. “Generalized Linear Models.” Chapman & Hall/CRC, 2 edition, 1989.


[15] Carpentier & Locatelli. “Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem.” COLT 2016.


[16] Lattimore & Szepesvari. “Bandit Algorithms.” Cambridge University Press, 2020.


[17] Jun et al. “Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits.” ICML 2021.