Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update
Authors: Yu-Jie Zhang
Sheng-An Xu
Peng Zhao
Masashi Sugiyama
Venue: NeurIPS 2025 poster ()
Keywords: Generalized Linear Bandits; Online Mirror Descent; Computational Efficiency; Regret Analysis
Primary area: theory

Abstract: We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function, thereby modeling a broad class of reward distributions such as Bernoulli and Poisson. While GLBs are widely applicable to real-world scenarios, their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency. Existing methods typically trade off between two objectives, either incurring high per-round costs for optimal regret guarantees or compromising statistical efficiency to enable constant-time updates. In this paper, we propose a jointly efficient algorithm that attains a nearly optimal regret bound with $\mathcal{O}(1)$ time and space complexities per round. The core of our method is a tight confidence set for the online mirror descent (OMD) estimator, which is derived through a novel analysis that leverages the notion of mix loss from online prediction. The analysis shows that our OMD estimator, even with its one-pass updates, achieves statistical efficiency comparable to maximum likelihood estimation, thereby leading to a jointly efficient optimistic method.

Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update
Yu-Jie Zhang's Sheng-An Xu?.3, Peng Zhao?.3, Masashi Sugiyama 1,4
RIKEN AIP, Tokyo, Japan
National Key Laboratory for Novel Software Technology, Nanjing University, China School of Artificial Intelligence, Nanjing University, China
4 The University of Tokyo, Chiba, Japan
Abstract
We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non- linear link function, thereby modeling broad class of reward distributions such Bernoulli and Poisson. While GLBs are widely applicable to real-world scenarios, their non-linear nature introduces sigmificant challenges in achieving both com- putational and statistical efficiency. Existing methods typically trade off between two objectives, either incurring high per-round costs for optimal regret guarantees or compromising statistical efficiency to enable constant- time updates. In this paper, we propose a jointly efficient algorithm that attains a nearly optimal regret bound with ((1) time and space complexities per round. The core of our method is a tight confidence set for the online mirror descent (OMD) estimator, which derived through a novel analysis that leverages the notion of mix loss from online prediction. The analysis shows that our OMD estimator, even with its one-pass up- dates, achieves statistical efficiency comparable to maximum likelihood estimation, thereby leading to a jointly efficient optimistic method.
Introduction
Stochastic multi-armed bandits [Robbins, 1952] represent a fundamental class of sequential decision- making problems where a learner interacts with environments by selecting actions (or arms) and receiving feedback the form of rewards. In this paper, we study the contextual multi-armed bandit problem under the framework of generalized linear models (GLMs). In this setting, each action is characterized by a contextual feature vector x E X C. IRd, where the arm set X, may vary over time. More specifically, the learning process can be environments: at each round f, the learner selects an action X, E X, and then observes a stochastic reward r. R generated according to GLM (see Definition 2.1). The goal of the learner is to maximize the cumulative expected reward obtained over the time horizon T. Under the GLM model, the expectation of the reward satisfies E(r, X,] ,xX,T f_), where μ R IR is non-linear link determined by the GLM model and known to the learner. The unknown part is the underlying parameter 0, E d which needs be estimated from the observed action-reward pairs.
T round game between the learner and
Compared with the classical linear case Abbaasi-Yadkori (GLB) framework allows for richer class of reward distributions, including Gaussian, Bernoulli, and Poisson distributions. This flexibility enables the modeling of various real-world tasks, such as recommendation systems [Li al., 2010] and personalized medicine [Tewari and Murphy, 2017], where the feedback is binary (Bernoulli) or count-based (Poisson) and inherently non-linear. Besides
Yadkori et al., 2011], 1], the generalized linear bandit
"Correspondence: Peng Zhao @chaop@lamda.jju.cee lamda.nju.edu.cn>
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparison of regret guarantees and computational complexity per round for GLBs. Here, K., 1/ Σi_ μ 0x). is the slope at the optimal action Xr.. = arg e 1((x 6.), with Ri I K (sec Section 2 for details). f indicates the amortized time complexity, i.c., average per-round cost over T rounds.
Method
Regret
Time per Round
Memory
Jointly Efficient
GLM-UCB [Filippi el al., 2010]
O(K(lugT)á
O(1)
O(1)
x
GLOC [Jun et al., 2017]
O(klog TVT)
O(I)
x ((1)
OFUGLB [Lee et al., 2024, Liu et al., 2024]
(lug T TT/R.
O())
O(I)
X
RS- RS-GLinnBB [Sawami et al., 2024]
Olog MlogTVTHi T/KK)
((logg
O(t) X
GLB-OMD (Theorem 2 of this paper)
Olog T (T/R)
O(1) 0(1)
its practical appeal, the study of GLB lays theoretical foundations for other sequential decision- making problems, such as function approximation in RL [Wang et al., 2021, Li et al., 2024], safe exploration [Wachi et al., 2021], and dynamic pricing [Chen et al., 2022, Xu and Wang, 2021].
The non-linearity of the link function raises significant concerns regarding both computational and statistical efficiency in GLBs. A canonical solution to GLB is the GLM-UCB algorithm [Filippi et al., 2010], which belongs to the family of UCB-typp -type methods [Agrawal, 1995, Auer, 2002]. At each iteration & E [T]. the algorithm estimates the true parameter 0. using maximum likelihood estimation (MLE) based on the historical data {xx, r&) }== and yields an estimator 0r, which is further used for constructing the upper confidence bound for arm selection. As shown in Table 1, GLM-UCB achieves nearly optimal regret bound in terms of the dependence on T. However, its reliance on MLE incurs a computational burden: it requires storing all historical data with ((t) space complexity and solving an optimization problem with (tt) time complexity at each round t. Besides, in terms of the statistical efficiency, the non- linearia of the link function introduces a notorious constant K = 1/ inl xeux_ x, ,,e px(x" 0) into the regret bound of GL.MUCB (see Section 2 for details). where jí' denotes the derivative of μ. In several applications of GLBs, such as logistic bandits (m(z) 1/(1 + e =))) and Poisson bandits (ę(2) )²), the term can grow exponentially with the norm of the parameter ||0~112. severely affecting the theoretical performance.
Over the past decade, extensive efforts have been devoted to enhancing the computational or statistical efficiency of GLBs. However, as summarized in Table 1, how to develop jointly efficient method that achieves both low computation cost and strong statistical guarantees remains unclear. For GLBs, Jun et al. [2017] developed computationally efficient algorithms with one pass update, but their regret bound scales linearly with the potentially large constant K. More recently, by leveraging the self- leff-concordance of the loss, several works [Lee et al., 2024, Sawarni et al., 2024, Liu et al., 2024, Clerico et al., 2025] proposed statistically efficient methods that achieve improved dependence on k; however, these approaches are still based on the MLE, which has high computation cost.
Our Results. This paper proposes a jointly efficient algorithm for GLBs that achieves an improved regret bound in terms of к with constant time and space complexities per round as shown in Table 1. This advance roots in the construction of tight confidence set for the online mirror descent (OMD) estimator used for performing the UCB-base exploration. We show that the OMD estimator, even though updated in a one-pass fashion, can still match the statistical efficiency of the MLE by carefully addressing the non-linearity of the link function. Here, "one-pass" refers to processing each data point only once, without storing past data. We also note that OMD-based online estimators have been used to develop jointly efficient algorithms in the logistic bandit setting [Faury et al., 2022, Zhang and Sugiyama, 2023, Lee and Oh, 2024], a special case of GLBs with Bernoulli rewards. However, their analyses of the confidence set rely heavily on the specific structure of the logistic link function (=))= = 1/(1 (1(1ee +e +),,, which limits their applicability to the more general GLB setting.
Technical Contribution. Our main technical contribution is a new analy- sis of the estimation error of the OMD estimator. The analysis is based on the
Table 2: Jointly efficient methods for logistic bandits.
Method
Regret
Time
Memory
(adn)-OFU-ECOLog [Faury et al., 2022]
OllogT (T//a)
O(lg!)
O(1)
concept of the mix loss, which has been used in full-information online learn- ing to achieve fast-rate regret minimiza- tion [Vovk, 2001]. Here, we show that it provides a natural way to bridge the
OFUL-MLogB
O(loog ( VTTK..
0(1)
O(1)
[Zhang Sugiyama, 2023]
GLB-OMD (Theorem 2)
Olog Toog/T//n vT/K.)
0(1)
0(1)
2

---

gap between the OMD estimator and the true parameter 6., thereby enabling the construction of tight confidence sets for bandit online learning. Our new analysis not only generalizes the OMD-based approach to the broader GL.Bs but also improves upon the state-of-the-ar for logistic bandits. As shown in Table 2, the jointly efficient method [Faury et al., 2022] requires Olog 1) time per round and an adaptive warm-up strategy to achieve optimal regret. Zhang and Sugiyama [2023] reduces the time complexity to (1)) but incurs an extra (V T') factor in the regret. In contrast, our refined analysis yields tighter error bound for the OMD estimator, allowing our method to achieve improved regret and low computation cost without warm-up rounds. Details are provided in Section 4.
We were made aware that mix-loss boseless-based analyses have been independently developed in two very recent concurrent works for constructing tight confidence sets. Specifically, Kirschner et al. [2025] developed confidence sets based on the sequential likelihood ratios mixing technique, and Clerico et al. [2025] proposed several confidence sets for Mss. While conceptually related, these works focus on the batch setting, where all historical data are repeatedly accessed, leading to substantial computational overhead. In contrast, our confidence set is based on the OMD estimator with a one-pass update. This difference leads to distinct formulation of the mix loss and tailored analysis to quantify its gap relative to the time-varying OMD estimator. Details are provided in Section 4.2.
2 Preliminary
This section provides background on the GLB problem, including its formulation, underlying as- sumptions, and closely related previous research. In the rest of the paper, for positive semi-definite matrix H E Rdxd and vector x E IR4, we define ||x[|иı vx T Hx and ||x|| as the Euclidean norm. For the function f IR-- + R, its first and second derivatives are denoted by f' and f", respectively.
2.1 Problem Formulation and GLM-UCB [Filippi et al., 2010]
The GLB problem considers a T'rounn sequential interaction between a learner and the environment. At each round 1 E [T] _ .I,...,77 T). the learner selects an action X, X C Rd from the feasible domain and then receives a stochastic reward ry E IR. We use the notation X'l to indicate that the arm set may vary over time, capturing many practical scenarios where available options change dynamically. For instance, in product recommendation systems, items can be added or removed, requiring the algorithm to adapt accordingly. Besides, we denote the learner's action by X₂ to emphasize its stochastic nature, which may depend on past data captured by the filtration Fi = (X1, ri,..., X₁-1, 11))). In GLBs, conditioned on Fi, the reward r, follows a canonical exponential family distribution with the natural parameter given by the linear model z₁ = X, O..
Pr [r. 2 = x, 0_ Fi]
exp
Trzz
m((z)) + h(rr:)))
(1)
g(7)
Here, 9. E IRd is d-dimensional vector unknown to the learner. The function h(r,T) is the base measure, which provides the intrinsic weighting of the variable r, while m(2) is twice continuously differentiable function used for normalizing the distribution. Besides, g R + R is the dispersion function controlling the variability of the distribution and T
is a known parameter. The expectation and variance of the exponential family distribution can be calculated as E(r 2] = ==())==0-00))))))))))) - m'(z) and Var(r | 2) = (z) [Wainwright and Jordan, 2008, Proposition 3.1]. Common examples of (1) include Gaussian, Bernoulli, and Poisson distributions. The goal of the learner is to maximize the cumulative expected reward, which is equivalent to minimizing the regret,
REGT Σ Ex(xT,0.) - Eu(XTO.). 0.),
where Xx,. arg minxex; x; nxx T 0.) is the optimal action. Besides, we have the following standard boundness assumptions used in the GLB literature [Filippi et al., 2010].
Assumption (bounded domain). The set Uterry X, is bounded such that ||x||2 for all x Xr. t E [T] and the parameter 0. satisfies ||0,112 S S for some constant S > 0 known to the learner. Assumption 2 (bounded link function). The link function is twice differentiable over its feasible domain. Moreover, there exist constants Gr > O and T,,. > 0 such that C₁ S v²(=) S I, for all
E S, S). Consequently, the function is strictly convex and a is strictly increasing.
3

---

GLM-UCB Method and Potentially Large Constant. The canonical algorithm for the GLB problem is GLM UCB [Filippi et al., 2010], which resolves the intorattio-exploitattoon trade-off with an pnper-confidencebouure strategy [Agrawal, 1995]. Under Assumptions 1, 2 and an additional condition that the reward rt is non-negative and almost surely bounded for all E [7]. GL.M-UCH achieves the regret of (valog T) VT), where the ((.) -not-tttaioon is used to highlight the dependence on and time horizon T. The dependence on the horizon T matches that of the linear case, where the (V))) rate is nearly optimal [Dani et al., 2008]. The bottleneck lies in its linear dependence on the constant Ki, which is defined by
1 Cy
K
inf im) 1e (x)
and
Air A
Ii=1 (0)
where θ = (0 E Rdd 101l I 8) and Xir Urelmy X. In the above we also define K, to reflects the local curvature at the optimal actions. The linear dependence on in GLM-UCB is generally undesirable, as x can prohibitively large in practice. Notable examples include the Bernoulli distribution with uuz) = 1/(1 e)²) and the Poisson distribution with puz) e², for which 6 = O(E²), growing exponentially with the parameter- norm bound S.
2.2 New Progress with Coneodoncere
The undesirable linear dependence on k has motivated the development of algorithms with improved theoretical guarantees. By leveraging the self-concordance of the loss, rooted convex optimization and later used in the analysis of logistic regression [Bach, 2010], recent studies [Russac et al., 2021. Lee al., 2024, Sawarni et al., 2024] have derived regret bounds with substantially reduced dependence on x for GLB. Following this line, we also adopt the ceff-concordance assumption here.
Assumption
Concordance. The link function satisfies [=" S R y²(2) for all x R.
Assumption 3 holds for many widely used GLMs. For GLMs where the reward is almost surely bounded in [0, Ri the link function satisfies Assumption 3 with coefficient I [Sawarni et al., 2024]. For example, the Bernoulli distribution is l-self-concordaat. Many unbounded GLMs also satisfy self-coneordance, including the Gaussian distribution (R 0), Poisson distribution
(R = 1), and Exponential distribution (R = 0). Leveraging seff-concordance, Lee et al. [2024] and Sawarni et al.
[2024] established improved regret bounds of order Ö(VT/K.). In these results, the potentially large constant K. appears at the denominator, which largely improves the ((K/T) bound by Filippi et al. [2010]. However, their methods incur still (tt) time and space complexities per round. Our goal is to design a method with low computation cost while maintaining strong regret guarantees.
Remark (Unbounded GLMs).. Our GLM assumptions are aligned with the recent work [Lee et al., 2024], which are more general than the canonical GLM formulation introduced in Filippi al. [2010] and later adopted in Sawarni et al. [2024]. Besides Assumptions I and 2, Filippi et al. [2010] further requires the rewards be almost surely bounded, which automatically implies self-concordance and thus satisfies Assumption 3 as shown by Sawarni et al. [2024, Lemma 2.2]. Beyond bounded distributions, our GLM formulation accommodates unbounded ones, such as Gaussian or Poisson.
3 Proposed Method
This section presents our method for GLBS based on the principle of optimism in the face uncertainty (OFU) [Agrawal, 1995]. The core of our approach is tight confidence set built on online estimator. We begin with review of the OFU principle and then introduce our method.
3.1 OFU Principle and Computational Challenge
OFU Principle. The OFU principle provides principle way to balance exploration and exploitation in bandits. At each iteration t, this approach maintains a confidence set (,) C Rdd to account for the uncertainty arising from the stochasticity of the historical data, ensuring it contains 8, with high probability. Using the confidence set, one can construct a UCB for each action x E X, as UCB(X)= = maxsec, (8) 1x(x 0) and select the arm by X; = arg maxxex, UCB(x). A key ingredient of OFU-based methods the design of the confidence set, as the regret bound typically scales with the "radius" of the set. A tighter confidence set generally leads to a stronger regret guarantee.

---

Computational Challenge. To the best of our knowledge, most existing OFU-based methods for GLBs rely on maximum likelihood estimation (MLE) estimate 8, and construct the confidence set. Specifically, the estimator is computed as
0N = arg min
Σ (.) +1 BE
(2)
where (0()) A (m: ()/9(() is the loss function and À > is the regularizer parameter. The MLE was first used in the classical solution [Filippi et al., 2010], yet the regret bound exhibited linear dependence on x. due to loose analysis. Subsequent work [Lee et al., 2024, Sawarni et al., 2024, Liu et al., 2024] provided refined analyses showing that MLE statistically efficient, with its estimation error relative to 8_ heing independent of к. This property enables the construction of confidence set (6) with k-free diameter, yielding the improved regret bound.
However, despite the statistical efficiency of the MLE, it has high computation cost. The existing methods mentioned above use different choices of the feasible domain O', but in all cases, solving the optimization problem requires access to the entire historical dataset, resulting in O(t) space complexity. Moreover, there is generally no closed-form solution for (2); the problem is typically solved using gradient-based methods such projected gradient descent or Newton's 's method, where each gradient computation requires least (1) time per iteration [Filippi et al., 2010]. Consequently, both the time and space complexities of the MLE grow linearly with the number of rounds f, making
unfavorable for online settings. addition, Sawarni al. [2024] set O' Rd (2) and required
an additional projection step ensure that 0 lies within the desired domain. This projection involves solving non-convex optimization problem, which is even more time-consuming.
3.2 Jointly Efficient Method
The main contribution of this paper is a statistically efficient confidence set (8) constructed based on an online estimator 0,, which has s-freee estimation error with respect to the true parameter 0, and can be computed with (1)) time and space complexities per round.
Online Estimator, Drawing inspiration from the study for logistic bandits [Faury et al., 2022, Zhang and Sugiyama, 2023], initialize 0₁ E O as any point in θ and set H1 = >la. For time I. 2 1, we update the model by
the online mirror descent to learn the parameter 0.. For t
0.+1 = arg min (0)) + ||0 02 12
(3)
dee
2m
where θ {0 E Rd
||01| < 8} is d-dimensional ball with radius S. In the above, we defined
(()) 2 (V), 0 0,) + 2 110-01132a.00 and H, Ala + EVe
(4)
The above two components play important roles in achieving low computation cost while maintaining statistical efficiency. The loss function (0) serves as a second-order approximation of the original loss, which preserves the curvature information of the current loss function while ensures that the resulting optimization problem can be solved efficiently. The local matrix can also be expressed as
H, = AIa + Σ [X," 0s+1)/g(7)) X,X,, where X, E Rd is the action selected by the learner. The matrix explicitly captures the non-linearity of the link function by y'(X] 0,+1) and retains the curvature information of historical loss functions until time - 1. Since the optimization problem (3) is quadratic optimization over an Euclidean ball, it can be solved with a computation cost of (de)) independent of time t. Further details on solving (3) are provided in Appendix A.3.
Confidence Set Construction. Then, we can construct tight confidence set based on the online estimator by carefully configuring the parameters as the following theorem.
Theorem Let 8 E (0, 1]. Set the step size to n = 1+ RS and the regularization parameter to À max(14dnII Gn (/{()) For each & E [2']. define the confidence set as
(o e {0) ||0
0, m. 3,(5)).
(5)
5

---

Algorithm GLB-OMD
Input: Self-concordant constant R. Lipchitz constant Ly, parameter radius S, confidence level 6.
1: Initialize 0, E Q == (0 E Rd |00| 2 - 5} and H1 = Ala-
2: for 1 to T do
3: Construct the confidence set (6) according to (5).
4: Select the arm X, according rule (6) and receive the reward rt.
5: Update the online estimator 0z+1 by (3) and set H4+1 H, + V2 (0++11))
6: end for
where O, is the online estimator (3) and the radius Be(6) is given by
B.(6) = 4X5² + +n d(6r)2 + +n)) n))n(1 ) -0 SR d 52R ( (eR+tnn))
Tup >g(T)
Then, under Assumptions 1, 2, and 3, we have Pr Vt 2 1, 0, E (,( 21 5. Besides, the time complexity for solving (3) is Odd)) and the space complexity is (
Theorem shows that an ellipsoidal confidence set (6) can be constructed to quantify the uncertainty of the online estimator Og with both statistical and computational efficiency. From a computational perspective, constructing the confidence relies only on the online estimator, which with (11) time and space complexities. From a statistical view, the radius of the confidence set is independent of K, which crucial for achieving the improved regret bound, as detailed next.
be updated
Remark (Comparison with Logistic Bandits Literature). We note that OMD has been used in logistic bandits for constructing confidence sets [Faury et al., 2022, Zhang and Sugiyama, 2023, Lee and Oh, 2024]. However, existing methods are not fully jointly efficient compared with our result. Specifically, Faury al. [2022] required optimization over the original loss at each round, incurring an additional (log t) computation cost and relying on a warm-up strategy to maintain statistical efficiency. In later work, Zhang and Sugiyama [2023] and Lee and Oh [2024] achieved constant per-round cost but their regret bounds have an extra O ( /log t) multiplicative factor. More importantly, as will discuss in detail in Section 4, the analyses in these works depend the specific structure of the logistic model and do not naturally extend to the GLB setting. Our key contribution is to introduce mixx-los-bbsee technique into the confidence set analysis, which not only enables the application OMD to the broader GLB framework but also improves both statistical and computational efficiency previous methods for logistic bandits.
Arm Selection and Regret Bound. Based on the ellipsoidal confidence set, one can employ a variety of exploration strategies, not limited to OFU-based methods but also including randomized approaches such as Thompson sampling [Abeille and Lazaric, 2017] for action selection. Here, we adopt the classical OFU-based strategy, where the action X, is selected by solving the bilevel optimization problem X, = arg maxxex, maxsec, (6) ((x 0). Since is an increasing function and (ō) is an ellipsoid, the OFU-based action selection rule is equivalent to
X, arg max max x To arg max 0, + [,(0)|[x|1,, xEX,
xEX, (EC,(8)
which allows to avoid solving the inner optimization problem explicitly. The overall implementa- tion of the algorithm is summarized Algorithm and we have the following regret guarantee.
Theorem 2. Let 8 E (0, 1]. Under Assumptions 1, 2, and 3, with probability at least Algorithm I with parameter 1) + RS and X max mnax(14dmIe (nRSL,,/g(T) ensures
Tlog T + kd S2 R log T(S² log K+
REGT S dSR S2R log T
where S is used to hide constant independence of d, K. S, R and

---

Theorem 2 shows that our method achieves an ((d/T/K.. regret. improving upon the (Rdy'T) bound of Filippi et al. [2010]. From a computational perspective, our OMD estimator can be updated in ((1) time and memory per round, in the same spirit as the least-squares estimator in linear bandits. Consequently, the computation cost of our algorithm matches that of LinUCB [Abbasi-Yadkori et al., 201 IJ, indicating that the nonlinearity of the link function does not necessarily make GLBBs more computationally demanding. In the finite-arm setting, our algorithm enjoys a constant per-round computational cost of Odd + df l). independent of T. In the infinite-arm case, the arm-sclection step (6) could become the main computational bottleneck (once the computational issue of MLE is resolved). Our estimator remains broadly useful as a plug-in component that can be integrated into other exploration strategies, e.g., Thompson Sampling [Faury et al., 2022, Appendix D.2] where the arm-selection step reduces to convex optimization problem for convex arm sets.
Since logistic bandits are a special case of GLBB, Theorem 2 also advances sfate-of-the-art results of logistic bandits by either reducing the (llog i) time complexity of Faury et al. [2022] to (11), or achieving an (Vllog T) improvement in the regret bound over Zhang and Sugiyama [2023].
Comparison with Sawarni et al. [2024]. We note that Sawarni al. [2024] also pursued computa- tional efficiency, but their approach is conceptually orthogonal to ours. They reduce the computation cost by employing a rare-update strategy that limits the frequency of parameter updates. However, their method remains MLE-based and requires storing all historical data, resulting in memory cost of (t). Moreover, although the rare-update strategy yields an amortized per-round time complexity of Olog t)² over I'" rounds, it still incurs a worst-case time complexity of (tt) in certain rounds. In contrast, our method performs one-pass update with (1) time and space complexities per round.
Discussion with Lee and Oh [2025a]. The work [Lee and Oh, 2025a] (v3 version, the latest one available before the NeurlPS submitted date) builds the framework of Zhang and Sugiyama [2023] and also reports an ((vlog 7) improvement in multinomial logit (MNL) bandits, a different problem that nonetheless shares certain technical connections with GLBs. Their technique could potentially be adapted logistic bandits for an (log T' /T/K.) bound with (L) cost. However, we identify potential technical issues in the analysis. The argument relies on a condition for the normalization factor of the truncated Gaussian distribution (see (C.15)) of their paper, also restated in (43)), an assumption that warrants further examination. We provide a detailed discussions in Appendix D.
3.3 More Discussions and Limitations
Dependence on T, and d. For the dominant term, our regret bound matches the best-known results for GLBs using the MLE [Lee et al., 2024, Sawarni et al., 2024], with respect to its dependence on T, k, and In terms of the non-leading term, Sawarni et al. [2024] achieved slightly tighter bound, as it scales with Kx = 1/ inf inf x (x(x") 0.), a quantity that can be smaller than k. In the logistic bandit case, the non-leading term is further improved to be geometry-aware. adapting more precisely to the structure of the action set [Abeille et al., 2021]. J. We conjecture that similar improvements in the non-leading term, matching the Kx dependence, might be achievable by incorporating warm-up strategy, such as Procedure in [Faury et al., 2022] or Algorithm in Sawarni et al. [2024] to shift the curvature term from μí (X, 0c) to yl' (X, 0.). However, it remains unclear whether geometry- aware bounds, akin to those in Abeille et al. [2021], can be obtained for GLBs without using the MLE.
Dependence on S and R. The MLE-based method completely remove the dependence on S and R in the leading term [Lee et al., 2024], whereas our method still exhibits an S2 -e-deeenee due to the requirement of one-pass updates. For MNL bandits, I Lee and Oh [2025a] showed that one can achieved improved dependence on S by incorporating an adaptive warm-up procedure. It may be possible to extend their warm-up technique to GLBBs for a similar improvement on S.
4 Analysis
This section sketches the proof of Theorem 1 and highlights the key technical contributions.
4.1
A General Recipe for OMD
To prove Theorem 1, it suffices to show that the estimation error 104+1-0.111, S (.). The analysis begins with the following lemma, which is commonly used for the convergence regret analysis for
7

---

the OMD- type update [Chen and Teboulle, 1993, Orabona, 2019, Zhao et al., 2024]. Here, we show it can serve as a general recipe for analyzing the estimation error of the OMD estimator.
convex set G and A IRaxd be symmetric positive definite matrix. Then, the update 02+1 1 = arg mingee [() + 2n 00 0.l13 satisfies
Lemma 1. Let f : θ + R be convex function
-0+1- < 2n 2n(Vv[(0+1))
0c+1) + |0, - 1 - 1| 0 Ila, for all u u (7)
The above lemma provides a pathway to relate the estimation error to the so-called "inverse regret". In particular, under our configuration where f(0) = (o). A H₁, and 6., and with a suitable choice of parameters, Lemma in Appendix A shows that the estimator by (3) satisfies
10: 0.1. S 21) Σ (o.) - E Ee(00tt))
3 00
2
Σ s=1
1-1
0. 0. 1l, + 1|0 -0.1 -0.12 (8)
inversa regrat
We note that, although the above inequality has also been shown in the logistic bandits literature (Faury et al., 2022, Zhang and Sugiyama, 2023, Lee and Oh, 2024], the proof of (8) via Lemma has not been explicitly discussed. We fill this gap by explicitly establishing the connection in our analysis.
4.2 Analysis for the Inverse Regret
Main Challenge. The main challenge and technical contribution of this paper lies in upper bounding the inverse regret term. Although previous works [Faury et al., 2022, Zhang and Sugiyama, 2023] have provided valuable insights, their techniques are challenging to extend to the GLB setting and remain suboptimal even for logistic bandits. The main technical difficulty in bounding the inverse regret is that 0,+1 is itself a function of the past losses la, which prevents the direct application of standard martingale concentration inequalities. A common strategy in prior work is to introduce an intermediate term by virtually running a full-information online learning algorithm, whose estimator 0, only depends on information up to time s 1, allowing the inverse regret to be decomposed as
inverse regret
(0.) Σ (..))
(0.) Σ (0a+1)
(9)
torm (a)
term (b)
Here, the intermediate term E
(,.) can be chosen as the cumulative loss of any online algorithm. In the case of logistic bandits, it is natural to leverage algorithms developed for online logistic regression, a well-studied problem with many established methods. For example, Faury et al. [2022] adopted the ALLIO algorithm [Jézéquel et al., 2020], while Zhang and Sugiyama [2023] built on the method proposed by Foster et al. [2018] and required the mixbaility property of the logistic loss. In contrast, for the GLB setting, the structure of the link function μ varies significantly across models, and it remains unclear how to design a unified intermediate algorithm. Moreover, even in the logistic bandit setting, existing analyses remain suboptimal. Specifically, Faury al. [2022, Eq. (7)) required an online warm-up phase to shrink the feasible domain in order to bound term (b). Later, Zhang and Sugiyama [2023] avoided this warm-up up step but instead relies on clipping the online estimator (see Eq. (35) in their paper), which incurs an additional ( Vogg? T)) term in the estimation error bound.
Our Solution. Instead of introducing intermediate term via virtually running online algorithm, we propose an alternative decomposition based on the mix loss, which defined as
(P.).) = - In (Eo-p. [o- (e-2.101):
(10)
where P3 is a probability distribution over IRdd whose specific form will be chosen later. In general, several choices of P. are possible, and select the one that best fits our algorithmic design. The mix loss has played a central role in the analysis of exponentially weighted methods in full-information online learning [Vovk, 2001, van der Hoeven al., 2018]. In our analysis, the mix loss is instrumental in analyzing the inverse regret defined in (9). In particular, the decomposition based on the mix loss m. (P.) offers a more general and analytically versatile formulation than (0,) used in (9). The former reduces to the latter when P. is chosen as Dirac distribution. We have the following lemma to upper bound the inverse regret under this mix-loss mix-loss-based decomposition.
8

---

Lemma 2 (informal). Let {P&) be stochastic process such that P. is a distribution over R. and only relies on information collected until time Then, for any E (0, 1), we have
1-1 Pr Vt 2 1, Σ (O.)
1-1 Σ mP.).) 2 log ]
11
2 1 1--6 6.
Lemma 2 follows from Ville's inequality [Ville, 1939], also known as "no- thto-hypercomprssiionn in- equality [Grünwald, 2007, Chapter 3]. It implies that term (a) in (9) is upper-bounded by log(1 (1/5) when the mix loss is used an intermediate term, significantly smaller than the O((log ()3) bound in Zhang and Sugiyama [2023, Lemma 12] that employs the online logistic regression method [Foster al., 2018). Notably, Lemma 2 allows flexible choices of P., enabling us tailor P. closely track the OMD estimator's behavior. The formal statement is provided in Lemma 5 of Appendix A.
To bound term (b), need to select P. -N.0..3n 3nfl,
Gaussian distribution centered at 8g with covariance , to approximate the OMD estimator (3). We have the following lemma.
Lemma (informal). Under Assumptions 1, 2, and 3, and with a suitable choice of X, we have
2 Σ m. (.0+0)))) 3n - 0sl1ir. d(3 2 In (1 1+
1
Iup
Ag(T)
where P. 30,,,,111," a Gaussian distribution.
Lemma 3 establishes connection between the mix loss and the the cumulative loss of the "look- ahead" OMD estimator, where the loss of 0z+1 is measured over the L,. A similar result for the logistic loss can be extracted from the proof of Lemma 14 in Zhang and Sugiyama [2023]. Here, we generalize this result to the GLB setting. Moreover, our proof simplifies the analysis in [Zhang and Sugiyama, 2023] by noticing that the mix loss can be interpreted as the convex conjugate of the KL divergence. The formal statement and complete proof are provided in Lemma 6 in Appendix A.
More Technical Comparisons. Our analysis of the inverse regret is closely connected to prior work that bounds the cumulative negative log likelihood (..) Σ (f.) using Ville's inequality, technique that traces back to Robbins [1970]. Most existing approaches aim to bound (0.) with the loss of the MLE estimator, whereas our analysis focuses on the OMD estimator. This fundamental difference leads to a distinct construction of the intermediate term used in the decomposition.
In the context of GLB, our Lemma 2 resembles Lemma 3.3 of Lee et al. [2024), as both apply Ville's inequality. However, their intermediate term Eg-r, [O)) is built upon a distribution P. that is fixed across all individual functions {L, [(,) making it naturally aligned with the MLE estimator but does not readily adapt to changing estimator: In contrast, our OMD estimator evolves with each individual function. Defining the intermediate term as the mix loss with time-varying Pa thus provides the flexibility needed to track this changing comparator. Very recently, two concurrent works [Kirschner et al., 2025, Clerico et al., 2025] have also employed the mix loss to derive confidence sets. Our Lemma 2 corresponds to Proposition 2.1 of Clerico et al. [2025], and the mix loss aligns with the sequential likelihood mixing technique of Kirschner et al. [2025]. While their analyses are already applicable to GLBs, key difference is that we an cllipsoidal confidence set centered at the OMD estimator to ensure computational efficiency, whereas both works [Kirschner et al., 2025, Clerico al., 2025] primarily analyze the negative bog-likelihood-baseee set, which are tighter but substantially more computationally demanding for GLBs This difference leads to a different specification of the mix loss and requires a tailored analysis. Specifically, in their setting, P, defined as the output of continuous Hedge method to track the MLE estimator (or any fixed comparator). In contrast, our analysis must dynamically track the OMD estimator, which motivates our choice of P, Gaussian distribution with the evolving OMD estimators as its mean. Lemma 3 is then used to quantify the gap.
5
Experiment
This section evaluates the proposed method on two representative GLB problems: logistic bandits (n(=) = 1/(1 + e-²)) with bounded rewards, and Poisson bandits (n(=) = e²), which pose distinct challenge as an unbounded GLB setting. We also conduct experiments on real data from the Covertype dataset [Blackard, 1998], with more detailed results provided in Appendix E.

---

10
Coader 2013
(c) Running time for Logistic Ban-
(a) Logistic Bandit (5 = 3)
(b) Logistic Bandit (S 5)
dit
Figure Regret and running time comparison of different algorithms on logistic bandits.
20000
73 CAEE por
80000
2.A orEEthrieeed G00C sanad 24/1
10:
Gan 2014
Regret
15000
2013
Regnot
10000
40000
10
5000
20000
107
10
1000
2000
3000
0
1000
2000
3000
Deeratons
Ieeaaiions
28.3 [Late]
137.2 (Hedium)
(a) Poisson Bandit (S = 3)
(b) Poisson Bandit (S 5)
(c) Running time for Poisson Bandit
Figure 2: Regret and running time comparison of diffcrent algorithms on Poisson bandits.
Compared Methods. Four GLBs algorithms compared, including GLM-UCB [Filippi et al., 2010], GLOC [Jun et al., 2017], RS-GLinCB [Sawarni et al., 2024], and OFUGLB [Lee et al., 2024]. For logistic bandits, further include specialized algorithms: an MLE-based method with nearly optimal regret OFULog-r [Abeille et al., 2021], and a jointly efficient method ECOLog [Faury et al., 2022]. We do not include OFUL-MLogB [Zhang and Sugiyama, 2023] since its confidence is larger than that of ours, hence has larger regret bound. More details of the baselines are provided Appendix E. All experiments are conducted over 10 trials, and we report the average regret and running time.
Results on Logistic Bandits. We conduct experiments under different contigurations of S. The under- lying parameter 0, is sampled from a d-dimensional sphere with radius $ = {3, 5, 5). corresponding to ς = 21, 137, and 963, respectively. Figure 1 reports the results. Among all methods, GLOC is the fastest but exhibits relatively large regret. OFUGLB attains the lowest regret due to its improved dependence on i and S, but as an MLE-based method, it incurs the highest computation cost. Our method strikes favorable balance. Compared to OFUGLB, it achieves substantial cost savings with only a modest degradation regret. Compared with ECOLog and RS-GLinCB, our method achieves comparable and slightly better performance with improved computation cost. Moreover, it maintains a constant per-round cost across all regimes K, whereas the cost of RS-CLinCB increases with K, as its rare-update strategy results an update frequency that scales with K.
Results on Poisson Bandits. We set the norm of the true parameter as S E {3, 5, 7}, corresponding to 18, 127 and 882. Poisson bandits have unbounded rewards, whereas GLM-UCB and RS- GS-GLinCB require a predefined upper bound on the maximum reward as a parameter. We set it as 100, assuming rewards are effectively bounded with high probability. As shown in Figure 2, our method reduces the computational cost of OFUGLB by roughly 1000 times, with only a modest increase in regret.
6 Conclusion
This paper proposed a new method for the GLB problem that achieves a nearly optimal regret bound of Oloog T /T/RR. with (11) time and space complexities per round. Our approach builds on a novel analysis of the OMD estimator using the mix loss, enabling a tight confidence set construction for arm selection. A natural extension is to incorporate warm-up strategy, as in prior work, to improve dependence on S and obtaín -bx-d bounds. also remains open whether geometry-aware bounds for GL.Bs can be achieved similar to those in logistic bandits [Abeille et al., 2021]. Other directions include relaxing the self-concordance assumption toward weaker conditions [Liu et al., 2024], or improving d-dependence in the finite-arm setting [Jun et al., 2021, Mason et al., 2022].
10

---

Acknowledgments and Disclosure of Funding
Peng Zhao was supported by NSFC (62206125) and the Xiaomi Foundation. MS was supported by the Institute for Al and Beyond, UTokyo. The authors thank the reviewers for their valuable feedback and for bringing our attention the recent works [Kirschner al., 2025, Clerico al., 2025].
References
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24 (NeurIPS), pages 2312-2330, 2011.
Marc Abeille and Alessandro Lazaric. Linear Thompson sampling revisited. In Proceedings of the 20th International Conference Artificial Intelligence and Statisties (AISTATS), pages 176-184, 2017.
Marc Abeille, Louis Faury, and Clément Calauzènes. mnstance-wise minimax-optimal algorithms for logistic bandits. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pages
2021.
Rajeev Agrawal. Sample mean based index policies by (log n) regret for the multi-armed bandit problem. Advances in applied probability. 2754): 1995.
Peter Auer. Using confidence bounds for exploitation-eexllraiion trade-offs. Journal of Machine Learning Research, 3:397-422, 2002.
Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4: 384-414, 2010.
Jock Blackard. Covertype. UCI Machine Learning Repository, 1998.
Gong Chen and Marc Teboulle. Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):538-543, 1993.
Xi Chen, David Simchi-Levi, and Yining Wang. Privacy-preserving dynamic personalized prieing with demand learning. Management Science, 68(7))4878-453 4898, 2022.
Eugenio Clerico, Hamish Flynn, Wojeiech Kotlowski, and Gergely Neu. Confidence sequences for generalized linear models via regret analysis. ArXiv preprint, arXiv:2504.16555 2025.
Varsha Dani, Thomas Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Annual Conference Learning Theory (COLT), pages 355-366, 2008.
Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 3052-3060. PMLR, 2020.
Louis Faury, Mare Abeille, Kwang-Sung Jun, and Clément Calauzênes. Jointly efficient and optimal algorithmss for logistic bandits. In Proceedings of the 25th International Conference on Artificial Intelligence and Statisticc (AISTATS), pages 546-580, 2022.
Sarah Filippi, Olivier Cappé, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems 23 (NeurIPS), pages 586-594, 2010.
Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic regression: The importance of being improper. In Proceedings of the 31st Conference Learning Theory (COLT), pages 167-208, 2018.
Peter D Grünwald. The Minimum Description Length Principle. MIT press, 2007.
Shunsuke Ihara. Information Theory for Continuous Systems. World Scientifie, 1993.

---

Rémi Jézéquel, Pierre Gaillard, and Alessandro Rudi. Efficient improper learning for online logistic regression. In Proceedings of the 33rd Conference on Learning Theory (COLT), pages 2085-2108, 2020.
Kwang-Sung Jun, Aniruddha Bhargava, Robert D. Nowak, and Rebecca Willett. Scalable generalized linear bandits: Online computation and hashing. In Advances in Neural Information Processing Systems 30 (NeurIPS), pages 99-109, 2017.
Twang-Sung Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved confidence bounds for the linear logistic model and applications to bandits. In Proceedings of the 38th International Conference Machine Learning (ICML), pages 5148-5157, 2021.
Johannes Kirschner, Andreas Krause, Michele Meziu, and Mojmir Mutny, Confidence estimation via sequential likelihood mixing. ArXiv preprint, arXiv:2502.1 14689, 2025.
Tor Lattimore and Csaha Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Joongkyu Lee and Min-hwan Oh. Nearly minimax optimal regret for multinomial logistic bandit. In Advances in Neural Information Processing Systems 37 (NeurIPS), 2024.
Joongkyu Lee and Min-hwan Oh. Improved online confidence bounds for multinomial logistic bandits. ArXiv preprint, arXiv: 2502.10020, 2025a. Version v3 posted 7 Mar 2025.
Joongkyu Lee and Min-hwan Oh. Improved online confidence bounds for multinomial logistic bandits. ArXiv preprint, arXiv: 2502. 10020, 2025b. Version v5 posted 16 June 2025.
Junghyun Lee, Se- Young Yun, and Kwang-Sung Jun. unified confidence sequence for generalized linear models, with applications to bandits. In Advances in Neural Information Processing Systems 37 (NeurIPS), 2024.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web (WWW), pages 661-670, 2010.
Long-Fei Li, Yu-Jie Zhang, Peng Zhao, and Zhi-Hua Zhou, Provably efficient reinforcement learning with multinomial logit function approximation. In Advances in Neural Information Processing Systems 37 (NeurIPS), pages 58539-58573, 2024.
Shuai Liu, Alex Ayoub, Flore Sentenac, Xiaoqi Tan, and Csaba Szepesvári. Almost free: Self- concordance in natural exponential families and an application to bandits. In Advances in Neural Information Processing Systems 37 (NeurIPS), 2024.
Blake Mason, Kwang-Sung Jun, and Lalit Jain. An experimental design approach for regret mini- mization in logistic bandits. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 7736-7743, 2022.
Zakaria Mhammedi, Wouter M. Koolen, and Tim van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT), pages 2490-2511, 2019.
Francesco Orabona. A modern introduction to online learning, arXiv preprint, arX.vv 2019.
Mark D. Reid, Rafael M. Frongillo, Robert C. Williamson, and Nishant Mehta. Generalized mixability via entropic duality. In Proceedings of the 28th Conference on Learning Theory (COLT), pages 1501- 2015.
Herbert Robbins Some aspects of the sequential design of experiments. Bulletin American Mathe- matical Society, 55:527-535, 1952.
Herbert Robbins. Statistical methods related the law of the iterated logarithm. Annals of Mathe- matical Statistics, 11(55:1397-1409, 1970.
12

---

Yoan Russac, Louis Faury, Olivier Cappé, and Aurélien Garivier. Self-concordant analysis of generalized linear bandits with forgetting. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 658 6686666 2021.
Ayush Sawarni, Nirjhar Das, Siddharth Barman, and Gaurav Sinha. Generalized linear bandits with limited adaptivity. Advances in Neural Information Processing Systems 37 (NeurIPS), 2024.
Ambuj Tewari and Susan A. Murphy. From ads to interventions: Contextual bandits in mobile health. In Mobile Health Sensors, Analytic Methods, and Applications, pages 495-517. 2017.
Dirk van der Hoeven, Tim van Erven, and Wojciech Kotlowski. The many faces of exponential weights in online learning, In Proceedings of the 31st Conference on Learning Theory (COLT), pages 2067-2092, 2018.
Jean Ville. Énude critique de la notion de collectif. Number 3 in Monographies des Probabilités. Gauthier- Villars, Paris, 1939.
Vladimir Vovk. Competitive on-line statistics. International Statistical Review, 69(2):213-245 2001.
Akifumi Wachi, Yunyue Wei, and Yanan Sui. Safe policy optimization with local generalized linear function approximations. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 20759 20779,, 2021.
Martin J. Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1-2):1-305 2008
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy, Optimism in rein- forcement learning with generalized linear function approximation. In Proceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
Jianyu Xu and Yu-Xiang Wang. Logarithmic regret in feature-based dynamic pricing. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 13898-13910, 2021.
Yu-Jic Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. Advances in Neural Information Processing Systems 36 (NeurIPS), pages 29741-29782 2023.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou, Adaptivity and non-stationarity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 52, 2024.
13

---

A Proof of Theorem 1
This section presents the proof of Theorem 1. We first provide the main proof, followed by the key lemmas used in the proof.
A.1 Main Proof
Proof of Theurem I. This part provides the proof of Theorem By Lemma 4, when setting "/
1 + RS, we can upper bound the estimation error of the online estimator by the "inverse regret":
10 0.1121 S 2n
Σ (0.) Σ (00+tt) 4A.2
inverse regret
2nRSL
10, 0x+1
Σ 100 1.t1l1i.
(11)
Then, we can further decompose the "inverse regret term" into two parts:
Σ E(O.) Σ (0.+1) Σ (0.) Σ m (Px) Σ (P.) Σ (0.+1)).
(12)
torn (a)
torn (b)
In the above, we define P. NO2,, " as d-dimensional multivariate Gaussian distribution with mean O, Rd and covariance matrix cH, E Raxd where 0 is constant to be specified latter. The function m, P + R that maps the distribution to real number value is defined by
m. (PP) - (Eo~P, exp (- (O))))
We refer to the function m, as the "mix loss" because it mixes the loss with respect to the distribution P.. This mixing has been found useful for achieving fast rates in prediction with expert advice and online optimization problems [Vovk, 2001]. Here, we show that the mix loss plays a crucial role in obtaining a jointly efficient online confidence set.
Given P. is Gaussian distribution with mean O, and aH, it J. meassuraale.. Then, Lemma implies that for any å E (0, 1], we have
!
term (a) log
(13)
with probability at least 1 8. Next, we proceed to analyze term (b). Under the condition that R4, Lemma with a 3 shows that
0.41 0,133, d(3n + 1 2 (1 1+
Tnp >g(7))
term (b) S 3n Σ
(14)
Plugging (12), (13), (14) into (11), we obtain
10++1 0,11%, S 4XS² + 2n (1) dn(6n 1) 1+ Lut
>g(T)
2n
10 ast1
Σ
10, 00-111
g(T)
3
Lut
42.2 + 2n log
dny(6n + 1)In
(1+
>g(())
where the last inequality holds due to the condition A 6nRSL,./(T))
14

---

A.2 Useful Lemmas
This section presents several key lemmas used in the proof of Theorem 1.
Lemma 4. Under Assumption I and 3 and setting "i + RS, then for any X > 0, the online estimator returned by (3) satisfies
1 Σ (000)))
10 - -0 S (2+2
Σ 4(0.)-
+ 4AS²
==1
==1
+ L + 2RS)
100 0st1ll2
Σ 100 1,11l
g(T)
8=1
Furthermore, if X 2 65Lg can further have
8 Σ ((0tt))
1 Σ 10, 0,11 4252
|0e+1 - -1.1 S
Σ ((().)
Proof of Lemma 4. We begin by using the integral formulation of Taylor's expansion. Since μ is twice differentiable, we have
(0.++)) (.()0) (Ve,(0+t1), 0.-1 0.) - 1 -011
(15)
where N. = f - 1) 22 (0.+1 + v(0. - 0s+1)) du. By the definition of the loss function in (4),
can further express the Hessian
h a(0s41,0 Oo, Xx)
X,X,,
g(T)
where ã(0,, f1 - v)
(x_0 01 + uUX. (02 - 01)) de.
Next, under Assumption 3, we have | (2) < R')x(2) for all E S. Consequently, Lemma in Appendix C implies that for any 0. E θ {0 Rd |101| - S).
p p'(XT 0x+1)
a(6 0,, 00,
2 2 + 2RS
This inequality shows that
h > 2 2RS
(16)
indicating that the Hessian hg is bounded from below by 242RS nite order. Substituting (16) into (15) yields
(2E.(0 in the positive semidefi-
1 10.+1 0- (0
(0(0.+1) - (.( < (VL.(0.+1), -0)) 2 2RS
(17)
(0.11)
Since 1,41 is the optimal solution of (3), Lemma with u 8, implies
(Vt.().)1) 0s+1 - -0,)
(V(,(0.+1) vi.(0.+1). (006+11),0000 a211 0.)) + (Vi.(0.+1), -O,)
3 (V+,(0,+1) vi.(0.+1),0 -0,)
1
+ 2m
[10. 0. 11,r, 110,41 - -0.1 11 0s+1 111t.)
(18)
15

---

We can further express the first term on the right-hand hand side of (18) as
(Ve,(0s+1) - (i,(0++2), 0,+1 0-) (Ve.(00+1) - (e,(0.) -
0.01 -O.)
G(T) (u(x]0+++) X, - -x((x,0) Xx [X] 0z) x, (0.t1 -0.), 0.)1 - 0.)
E.) - -0.+-11111,x (0,+1 - -8.)
2g(T)
R
2g(T) -100 - 0000 -10,-00411 (x+111/(XTT))xxxx x, (0x+1 0.)
< 0, - 02+1 -0++1l(7t..(E.)
< RSL 110, 0.+1l12
(19)
g(T)
where & E θ lies on the line connecting 0g and 0.+1- The first equality follows from the definition of (0.+1) and the Taylor expansion with Lagrange's 's remainder. The first inequality uses the self-concordance property of the loss function, which ensures that (=)=) S (z) and (z) S Lp
for all 2 [- S). The last inequality is due ||2 and ||0, 0.+1ll2 S 2S.
Combining (18), (19) with (17), setting = + RS and taking the summation over t E [T] yield
Σ (0+11) Ees(0.) (0.)
$
1
||61 0. 11 110 0. 1
Σ11 110 0 00t11111
RSL |0, 0,+1l12. g(T)
2 2RS
We complete the proof by rearranging the terms and noticing 110, 10--0. 0-1121, 4XiS2.
Let (Pe) be stochastic process such that the random variable P, is distribution over TR. and is F.-messurable. Moreover, assume that the loss function &, defined by (4) is F++1- ffal-measurable. For any 2 1, define
Lemma 5. Let (F be filtration defined by Fc
Ec((O)) and F; = Σ In EB-P, P. (o (c-2100)) 1=1
L,(0.)
Then, for any 6 E (0, 1). we have
1 Pr v 2 1M S F. log
Proof of Lemma 5. Let Mo = 1 and for any 2 1, we define
Mf (f.) Ft).
To prove the lemma, it suffices to show that the sequence {Mr is a non-negative (super)- martingale; then, the maximum inequality Lattimore and Szepesvári [2020, Theorem 3.9] can be applied to obtain the desired result. To verify that {M]] is a (super)martingale, we begin by defining the density function of the natural exponential family distribution as follows:
rz m(2)
+ M(T.T))
p(rlz) = exp
g(T)
where the function m, y and l share the same formulation those in (1). Then, for each time 2 1, we can rewrite the expression of M, as
Mr I P, [exp(-(,(0)) M exp (-fx()))
Eg-p, (exp(-(((0)) M.-1 EB-r, [p(re|XXT 8))
IT: exp (o.)
p(r,X 0.)
(20)
16

---

where the final equality holds because the loss function in (4) is the negative log- log-likelihood of an exponential family distribution; that is, for any 0 E IR
X, m (XX p(rr 0) exp h(re, r)).
exp (-4((0) exp
g(T)
Then, by taking the conditional expectation with respect to the randomness in Tt given Fr on both sides, we obtain:
Be-p,ll(ri,, Ft
E FF M E
p(re|X, 0.)
- /
(p(])1 0)1
p(r|[x] 0.)dr
p(r|X, 0.)
-Mi-1 / (EoweiD((rx) 0)]rr
| p(rxx 0)dr
=Mi-1 Benp
= =M-1,
where the first equality follows from the fact that Mc-1 is Fe-measurable. The second inequality holds because the reward is sampled from the exponential family distribution (1). The final equality is a consequence of the tower property of conditional expectation. We have thus shown that {M, 100 is martingale, and therefore a super-martingale. Then, by applying the maximum inequality Lattimore and Szepesvári [2020, Theorem 3.9], restating as Lemma Appendix C, we have
1
Pr sup L,(,) F, 2 log tEN
s 6Mo 5,
which completes the proof.
Lemma 6. Under Assumption 2 and 3, let P, NN aH, be a Gaussian distribution with mean 0g and covariance matrix aH, where H, = Ala + Σi=l 2 (0++1) and is any positive constant. We denote by 0g the model returned by (3). Then, setting X 2 64dcil? /7 we have
Σ (P.) S (c(00+))) + 2a a=1
110.. Bellir, + +((2 + _ In 1+
2Lnt )g(T))
sml
where the mix loss is defined as mP.P.) = In (BewP, [exp ( (0)))
Proof of Lemma 6. Our analysis begin with the observation that the mix loss convex conjugate of the KL divergence function. Then Lemma 12 in Appendix C shows that
m, (Ps) - -log (Ea-P,le (c-00))) = 1.0.2.16000 + KL(Q. - KL(QuIIP:) (21)
term (a)
tarm (b)
for any distribution Q, defined over R4, where (0) x P.) e e. for all 0 E Rd. Here, we choose Q. = (( aH; ) as a Gaussian distribution with mean 0,+1 and covariance aHH
Analysis of Term (a). Since Q, is symmetric around 0,+1, we can express term (a) as
term (a) Ea-q, 1t. (0.+1) + (0.+() 0 0 0s+1)l Ea- [Dz, 0+10
= (.(0s+1) + (D,, (0, 0s+1)l
< (o(0s+1) + 2a log (H.)))HH++)))))))) - log det(())).))
(22)
(. where D,, (0.0.+1) = -
(Ve. (0.-1)))) 0++1) the Bregman divergence of l, between 0 and Ost1. In the above, the second equality follows from the definition of Q.. The last line follows from Lemma 7 in Appendix C, since f, is self-concordant and the condition 2 R4doR holds.
17

---

Analysis of Term (b). Given Q. and Ps are both Gaussian distributions, Lemma 13 shows that
||0, 0s+1ll2, d)
term (b) -
log (e. log (H.) Tr [H,H
1
W8
(log det( (o+1) log det H.)) +
10 - -0+11 10
(23)
2a
Put All Together. Plugging (22) and (23) into (21) and summing over T rounds, we obtain
Σ (P.(P)) Σ (0.+t+)) +
1
Σ
0.+1 - 0xl + (2a + 2))nn (et(H)+1))
20
det(ATa)
==1 The determinant of the matrix H441 can further bounded by
==1
det (Ht(()+)1) = det (Ala Σ (2ea(0.t1)) s det ((A (A+ Lut/g(T)) - (a+ Lul/g(T))
dee((A
Then, we obtain
Σ mm.(P.) (0+0+) + 2a
1
Lut Σ 10+1 - 0s11ir. - d(2a 2) (1+
)g(T)
#=1
which completes the proof.
Lemma 7. Let (g) be the loss function of the maximun likelihood estimator and Q2 ((O aH aHgt1) be a Gaussian distribution with mean 0st1 and covariance matrix aH with H2 Aa Σデ= (Br41)) Under Assumption 1, and 3 and setting 2 64doRR /7, 77, for any constant a > 0, we have
Ea-q, De, (0, 0s+1)) s 2a llog (eddde((HH4 - log der (.)(.
Proof of Lemma 7. By the the integral formulation of Taylor's expansion and the definition & such that (0) = n (x, 0)/g(T) -xXX I for any 0 E Rd we have
Q [De, (0, 0++1)]1]]] EB 110 0 10t111 11.
where (0) = ft-o (1- /r (x] 0.+1 + ux_ (000))+)) de XaX_ /g(T). According to Lemma
in Appendix C and the condition X 1 < 1 by Assumption 1, we can bound the Hessian (,) by (0) 2 expp(111) 11+) (0.t().)).
(24)
Then, the approximation error between the linearized loss g, (0) and (0) is bounded by
[Dr, 0s+1)l S Eane, 11000++1111 110 0++ (e)))))))
Esnq, @2R01100 Eanq, 110 - 10-00tilitee
Banq. [[((21,(00+)))) -000))1)1)) V
4
(25)
The second inequality due to the Cauchy-Schwar inequality. The last inequality is due to Lemma 10 under the condition that Hl, x Ala and the setting À 2Ada/t2/1 /7. For the last term the right hand side of (25), the random variable (V2L,(0.+)) $ (0 0.t1) follows the same distribution as
a,, and x; ld ~
N(0,1), Vi ViE [d].
18

---

where X is the i-th largest cigenvalue of the matrix ( (0s+1)) (F set of orthogonal basis. Then, we have
and e, is
R (V (00))))))(000))]]((()))))))
Ex,~V(1.1)
( Eoxix?)
a Xx
varTr ( (
(26)
where Tr(A) denotes the trace of matrix A. In the above, the last inequality is due to the fact that E
3. The last inequality due trace(AA)) trace(BA) for matrix
A, E Raxd Recall that Ha+1 = Ml + Ei= & (0,+1)-
Tr H ( & Tr (H Ho)) = TT HaH
-Tr(I-H,HHTt)
I log det( Hs+1) - log det H.)
(27)
Combining (26) and (27) with (25) yields the desired result.
A.3 Computational Cost Discussion
This part discusses the time and space complexity of solving the optimization problem (3). Proposition 1. The time complexity for solving (3) is Odd)), and the space complexity is (dd)).
Proof of Proposition 1. We begin with the analysis on the time complexity, followed by the discussion on the space complexity.
Time Complexity. According to Theorem 6.23 of Orabona [2019]. the update rule of online mirror descent (3) can be equivalently expressed as
S++1 = 0, -
(28a)
0.11 = arg min| S++1l H.
(28b)
d=e
where H. H, + (f.)). In this formulation, the first step (28a) a gradient update, whose main computational cost lies in computing the inverse of the Hessian matrix. Since (0,) = μ' (X, 0.)g((r) X,X, is a rank-1 matrix, the Morrann-orrison formula can be applied to efficiently compute the inverse of He as
H,X, + X, X
(i, ((++))-((00)11 = H
g(T)
(x
which reduces the computational complexity to (dd) per iteration, assuming H is available. Since H, H + (0))), H can also be updated by the Sherman-Morrison formula in Odd) time per round based on H- Therefore, the total computational cost of (28a) is (d2). In the second step (28b), as He is positive semi-definite, the optimization problem can be solved Odd) time (see Section 4.1 of [Mhammedi et al., 2019] for details). Overall, the total time complexity for solving (3) is (dd)).
Space Complexity. Regarding space complexity, it suffices to store the current model 0,, the gradient Vl, (0.), the inverse Hessian matrix H, and A7 throughout the optimization process, resulting in total space complexity of O(d))
19

---

B Proof of Theorem 2
Proof of Theorem 2. Let (X,, 0.)
((xx6x (T). We can bound the regret by
REGT Σ 1 [ 0.) Σ 0.) 0.)
T
1 (x,10) 0.)
Σ mxX; 0.)
T Σ
T
(x, 0.) (Ø. - 0.) + 2
Σ
ā(O,, 0, (x) (Ō, 0.))
(29)
(b)
where 02, So ")²" u + X, (02 0, )) du. In the above, the first inequality is
due to the arm selection rule (6) and the second equality by the integral formulation the Taylor's expansion. Then, we upper bound the terms respectively.
Analysis for term (a). For the first term, we have
term (a)
r (X, 0.) xX (0. 0o)
Σ pxx -111,11,,,-116 1l.
T
< Σ
Hl (xx (X,T0)) (,)6))())lXxlll....
1=1
T
< (8) 1=1
Σ
(XTT 0.) -1xxell
$ (0)(6)
Σ (x, 0.) |I + (3r Σ
(XXT [[eellm.* m
IE
TE
tern (a1)
term
(a2)
where the first inequality is due to the Hölder's inequality and the second inequality is by the fact ||0: 0.1 H, S 110 B,lla, + ||o, - 1,l,, $ (6). In the last inequality, we decompose the time horizon into T (1 E (T) (XTTo.) ((+1) and To TT/TT-
0c+1))
Analysis for Term (al): For the time steps in f Tı, the term (x, 0.) can be further bounded by
(x(x = ('(x) 0c+1) + S (X, 0.4 + uxx, (0, - 0(+1)) X, (0, - 0s+1)
0=0
(x, 0c+1) + R S 1x, 0c+1 + vX, (0. 0c+1))dv |XT (0. 0c+1)l
J
n (X. D2t1) + RL, || || 110, 0041lll..
< [X) 0c41) + (L,,8+4100) ||
(30)
where the first inequality is due the self-concordant property of μ.. The second inequality is by Assumption such that p=))) S T.p for [-S, S] and the Hölder's inequality. The last inequality is due to Theorem and the fact Het1 > Hi.
20

---

Then, let He = g(T)H, Ag(T)La + Ex 1 (X, 0 X and Vi = ^g(T)la -
E X,X, We can upper term (al) by
(0)
2RL 1RL1171110
term (a1) 5
Σ LE
u (x7
|exlll iT,1
Vg(T)
g(T)
(8)
Σ V 0.)
2RI (5)
Σ
+
Vg(T)
g(T)
IET1
IE
(8)(
Σ O.)
Vu 1c+1)Xx
2RL
Vg(TT
11,
g(T)
IET1
LET1
(31)
where the first inequality is by the condition [x, 8e41) S ('(XT0.) for t E Ti. The second inequality is due to the Cauchy-Schwand inequality and the fact that He V. Then, we can further bound (31) by elliptical potential lemma (Lemma in Appendix C) as:
Σ
(x((TTo0 LE
Σ RE(T)
S 2d(1 + L,) log (1+ Thn g(r)d)
S
(32)
by taking (X,, 1 in Lemma 11. The last term in (31) can also be bounded by
Σ 1 & Σ IE
1x < 4d (1+ g(())sdX)
(33)
1E
For notational simplicity, denote by
(1) = 20r YT'
(8) (8)
22d(1
log
(1+
The g(r)dr
(8) T),
Va(T)
(34)
(2) TT (8) Srd 82 (8)
log 1+ glr)xax
O (6T+1(6) log
g(T)
Then, plugging (32) and (33) into (31) yields
(1) (8), term (a1) S 7/
Σ
('(XTO.) 0.) + - =f) + R RE-G + 7/2 (35)
KE
where the last inequality can be obtained following the same arguments in the proof of [Abeille et al., 2021, Theorem l].
Analysis for Term (a2): As for the term (a2), we have
Σ v Vi((xTo.) 0.). V (oTTTTOtXXXX
term (a2) < (r)
Σ 1X, 0.) 1 S 3r())
LETs
TETa
H,
where the last inequality holds due to the condition arguments in bounding (31), we can obtain
p'(x, 0.) S p'(x 0c+1). Following the same
term (a2) < 7 (8) T/m. + R REGT.
Combining the upper bound for term (al) and term (a2), we have
term (a) s 2, (8) R REGT + 7/ (8))
(2) (8).
21

---

Analysis for term (b). As for the term by, we have
T
term (b) =
a(O, 0g (x, (0,-)
2
1=1
R T
p [X 0x -Ux (0e 0.)) do (X, (0, 0.))
[=1
R P
|10
0. 112. ||xellar.
T
Σ - S (t).
(36)
g(T)
where the first inequality is due the self-concordant property of μ. The second inequality is by Assumption and Cauchy-Schward inequality. The third inequality is due to the fact ||0, 1. < (8) and H, g(r).. The last line can be obtained following the same arguments in bounding (33).
Overall Regret Bound. Plugging (35) and (36) into (29) yields
REGT 21/ (0) (())/T// TTKK, + R REGT 27/7 (6).
Removing the above inequality and rearranging the terms yields
REGT s 272 + +22 + 2m
1/ R2 + 2y2 T/Ki.
2/2 + 27 + 2%1
(7+ + 2222 + TT/K,
272 42 271 v 222 R 2n T//K.
0
Br( dT log T/K. + Rd log T T37(1))
TlogT + ndl 52 R² log T(S R log log7))
0 dSRv + log T
where 71 = -// (8) and 72 7/ (2) (5) defined as (34). We have completed the proof of the regret.
Computational Complexity. As shown in Proposition 1 in Appendix A.3, the time complexity for updating the online estimator 9, Odd) (line 5 in Algorithm 1). Additionally, the inverse Hessian matrix H can be updated in (d2) time per round as shown in Appendix A.3. The remaining computational cost arises from the arm selection (6), which solves the optimization problem
X arg max 0, + (100)|lxl XEX,
Given 0, and H this optimization can be performed in (dd))&))) time at round t. Therefore, the total per-round computational complexity is O(d + d3 d'(.).).
C Technical Lemmas
Lemma 8 (Lemma 9 of Faury et al. [2020]). Let μ. IR. - R be a strictly increasing function
satisfying (z)) < (z) for all Z, where R is a fixed positive constant and Z 1. is
bounded interval. Then, for any 21, z2 E Z and E {21, 22), we have
[
k((z)
p'(z1 + 1(22 21))dv >
(37)
R
[21 Z2
22

---

and the weighted integral
(z)
[ Juzo
(1-
(1
(1
+ u122 =))dd I exp (R -221²) -z(2z) (38)
+ R 21 22
We include the proof here for self-containeddess.
Proof of Lemmas Without loss of generality, assume = =1 Let d(v) := يl + 1122 21))
and A = 22 21|. From Ip"(2) (z), we obtain the key differential inequality
[d((v) & RAØ(U) V [0
(39)
The solution (39) yields the exponential bounds
p μ'(z)ee RAV S <d(v) S / (21)e
(40)
Proof of (37): Using the lower bound in (40), we have
L. Øvvidv 2 1 (z1) {"' e e-RSy dv (((21) ER-
v((=))
RA
+ RA
where the last inequality uses e= x/(1 x) for 2 0.
Proof of LHS of (38); For the weighted integral, we have
S/ (1 v)o(v)de 2 (z)))
(1 - (1-v)e- --vue-Ruud
RaUdy
1
1 1-e
=(11))
RA (RA)²
(()))
2 RA
The final inequality follows from the fact that
Vz 2 0.
2
2 2
Proof of RHS of (38): Using the upper bound in (40), we have
S (1 v))o)())d s m21)))) / (1 RAv
RD RA
(RD)2 11(21)
$ ne
n² (21)..
where we used e 1 S 2 for x 2 0.
The case for 2 = 22 follows by symmetry.
Lemma 9 (Ville [1939]). Let ( be supermartingale with M, 0 almost surely for all t t O. Then, for any E > 0,
E X
Pr
sup M, 2 = LIEN
Lemma 10. Let P = N -H be a Gaussian distribution with mean Rd and covariance n.i-1 where H i Ala is positive definite matrix and 17 0. Then, if X 2 32dne/7 we have
Ea-p[ exp (c]10112) <
23

---

Proof of Lemma 10. Let 0 E R be random variable sampled from P. One can verify that it also follows the sample distribution as
MAA. and X; iid. NVOO,)), 1), Vi [d].
where {e:) is set of orthogonal base and A is the i-th largest eigenvalue of H-1 Then, we have
II exp (cnAix3)
- (Ex-No..) exp (enx² (onx9/11)
Eg-pl exp (cl(013) = ((..1
= [EZzxa exp
1 ( )]
S RE exp
(and ( 3)
3
where x² denotes the chi-squared distribution with degree of freedom 1. The first inequality is because max4e(d] A; I 1/X due to the condition H! -Pd- The last second equality is by the Jensen's inequality since xd a convex function with respect to x. The last inequality is due to the condition end// X < 7/32 and the fact that the moment -generttgnn function of the chi-squared distributionnlJexp(t [Z)] < (1 - 2 1/2 for t < 1/2.
Lemma 11 (Lemmna 9 of Faury et al. [2022]). Let X 2 1 and [2g] a sequence in H such that |z 2 S Z for all E N. For 2 define V, = Σ ZZZ + Ala- The following inequality holds
TZ²
Eleili S 2d(1 + Z²) log 1+
dA
Lemma 12. Let P be probability distribution defined over R. and A be the set of all measurable distributions. For any loss function f Rd + IR, we have
= Eg-P. [e(0)] + 1 KL(PP))P),
log Pe
(41)
where P. arg min Ba-P [e(0)] + (I.((P)IPP) is the optimal solution. Furthermore, for any
distribution defined over Rdd we have
log (Eapple (oorl(eat(0))) = [(0) KL(Q|)P) (LI
(42)
a
&
Proof of Lemma 12. To prove (41), one can check that the optimal solution to the optimization problem on the right-hand side of (41) is given by
P(O)e-aé(0)
(0) JOERS P(0)e=at(0)dd
Substituting P. back into the right-hand side yields the desired equality. Alternatively, (41) can be shown by noting that the mix loss the convex conjugate of the Kullhack-Leibler divergence [Reid et al., 2015]. By the definition of the convex conjugate, the equality holds.
To prove the second part of the lemma, namely (42), let Z = S P(f)e- -o(()) do. We then have
1 (L].P)) 1
PL
KL(PP.IP)
α
a
(0))))
1
P.(())
Ea-Q
In
= Egnp.
In
P(0))
P(0))
1
[mm
(
(e-a((0)
)
1 EawP.
(e-a((0)
Z )
EanQ
In
In
a
Z
a
P. [[(0]] - [(()))
where the second equality is due to the fact that P. (0))/((() E -al(0) /2 for all 0 E Rd. Then, rearranging the above displayed equation gives us
Eg P. [((0)] - KL(P.IIP) Ee ([(() KL(QII)) KL
a
a
which completes the proof by using (42).
24

---

Lemma 13 (Theorem 1.8.2 of Ihara [1993]). The Bullback-Leibler divergence between two d-
dimensional Gaussian distributions P Nup, Ep) and Q = (u, 2gg) is given by
1 2
p
TT(E + I| un u11l2p- d)
(L(QIIP)
In
D More Discussions on Lee and Oh [2025a]
For MNL bandits, [Lee and Oh, 2025a] (v3 version, the latest one available before the NeurIPS submitted date) claimed an OVVlog T') improvement in the regret bound, which could potentially be applied to logistic bandits to achieve an Oloog T TT]j=>) bound with (1)) computational cost. However, their analysis relies specific upper bound on the normalization factor of truncated Gaussian, which may not always hold. We elaborate on the main technical issue below in the context of the logistic bandit problem.
With slight abuse of notation, we define the logistic loss as (,(0) = rtX, 0 + 1og(1+ exp(X, 0)). where X₃ is the action selected by the learner and r, E {0, 1] is the observed reward. Specifically, building upon the framework of Zhang and Sugiyama [2023], the Lemma C.1 of Lee and Oh [2025a] shows that the estimation error of their estimator satisfies
10++1 - 0.11
(0.) Σ (.E))
Σ e. (0.+1),
torm
torm (b)
+ + log(1 + exp(:)) Lee and Oh [2025a]. the intermediate term is chosen as where (2(2) r2z
2,4 o+ (o,_,, 8)), where (12) 1/(1 + c=²) and (p) log( T
A key step of their analysis lies in the choice of Ps. which ensures that term (a) and term (b) can be bounded separately. In contrast to the Gaussian distribution used in Zhang and Sugiyama [2023], Lee and Oh [2025a] take Pe as a truncated Gaussian, thereby allowing the bound on term (a) to avoid the additional ((VT) factor incurred in Zhang and Sugiyama [2023]. However, when analyzing term (b), their argument relies on a condition for the normalization factor of the truncated Gaussian distribution, which does not holds in general (see Equ (C.15) in their paper).
For completeness, we restate below: there exists a constant C, 2 such that
J 11 587
de 1 d0 S
S 100 d0,
(43)
101
where 7; <>>0000000 0 are certain constants and H, is symmetrie positive-definite matrix. Condition (43) plays an important role in ensuring that the term log(Z./Z...) in Eq. (C.17) of the paper remains non-positive and does not affect the final bound of term(b). However, it is not evident how to select e. 2 1 to guarantee this property holds throughout, as the left-hand side integrates over a strictly larger region while the integrand decays more slowly. We also mention that this issue concurrently addressed by the authors in the later version [Lee and Oh, 2025b] (v5 version, posted June 2025), and the fixed technique is essentially similar the mixability- analysis in work.
also
E Additional Experimental Details
In this section, we provide additional experimental details and results.
E.1 Experimental Setup
Implementation Details. the experiments were conducted on Intel Xeon Gold 6242R processors (40 cores, 4.1GHz base frequency). The algorithms were implemented in Python, utilizing the scipy library for numerical computations, such as solving non-linear optimization problems and calculating vector norms, and employing mp. .linalg. pinv to compute the pseudo-inverse of matrices. The running time was measured using the time library. The shaded regions in the regret plots represent 99% confidence intervals, computed from 10 independent runs with different random seeds.
25

---

100
20-
25
5-
-25
-500
-10
-10
-20
-100
-10
-10
20
(a) d 2,5
300.
(b) d 2, 5, T
3000
(c) 2,
7,
300.
Figure 3: Confidence Region of Parameter Estimation.
330
E000
AM DI Slaee D0ee Cie Plureen
7000
38
Sece 301
36
5000
344
12
10
pecumeeer
(a) Logistic Bandit (S 7)
(b) Logistic Bandit (S
(c) Runtime vs S on Poisson Bandit
Figure 4: Regret and Running Time Dependence on S.
495
300
PLO VEDCI
Rucatoo ToastoTTuuogoo
454
Touning Tinee 50
104
La Ader alallees 201
200
10a
10a
3002
16:33
100
101
102
GLENMM
GRante
scatoy
unitag
200
100
6.0
50
200 Begent
250
500
Stop
(a) Regret for Cover Type Data
(b) Running time for Cover Type Data
Regret Running time
Figure 5: Performance comparison of different algorithms on Cover Type Data
Algorithm Configuration. Throughout our experiments, all algorithm parameters were configured according to their theoretical derivations without additional fine-tuning, with the sole exception of the regularization parameter A. To ensure a fair comparison, we adopted a unified approach for setting across different algorithm categories: we À d for all efficient online algorithms (including GLB-OMD, RS-GLine DS-GLinCB, ECOLog, and GLOC), while using X = d ( + t) for offline algorithms that require regularization. This distinction reflects the practical consideration that real-world scenarios often exhibit more favorable conditions than the worst-case assumptions.
E.2 More results on Synthetic Data
To visualize the accuracy of parameter estimation of the algorithms, plot the confidence region of the parameter estimation for each algorithm in Figure 3. For illustration purposes, we only plot the confidence regions of our algorithm GLB-OMD the theoretically optimal OFUGLB, and the classical GLM-UCB. We observe that both CLB-OMD and OFUGLB achieve a substantially smaller confidence region than GLM-UCB, indicating that our algorithm achieves accurate parameter estimation comparable to the statistically optimal.
To further investigate the impact of parameter S on algorithm performance, conduct additional experiments on logistic bandit tasks with larger values (Figures 4a and 4b) and analyze the computational time scaling for Poisson bandits (Figure 4c).
26

---

The regret curves in Figures 4a and 4b consistently demonstrate that our algorithm maintains its competitive performance regardless S variations, aligning with the trends observed our main results. Notably, the regret does not exhibit significant growth as S increases, suggesting the robustness of our approach to parameter scaling. We also note that the performance of RS-GLinCB is very sensitive to the parameter of S. This underperformance can be attributed to the fact that the warm-up period of RS-GLinCE is heavily dependent on the constant S and k [Sawarni et al., 2024, Lemma 4.1].
The runtime curves in Figure 4c reveals two key findings: First, our algorithm's 's running time remains stable (under second for T = 3000) across different S values in Poisson bandit tasks. Second, in contrast to this consistent performance, OFUGLB exhibits a pronounced computational overhead that scales with S (requiring 2783 seconds at S = 3 compared to 7568 seconds at S = 9). This divergence can be attributed to the confidence radius construction in OFUGLB:
C,(8) == { PpE (..))) - {
(44)
where 3e(8)² = log 1/2 + inf { dllo 1 + -2L,a - log 1/ + d dlog (e V 2:5S/1 For Poisson
bandits specifically. L, = e 2 + (d/). This results in increasing cost in the optimization steps during the arm selection X, arg maxxex, max x 0, as the algorithm needs to navigate a rapidly expanding nonconvex confidence region.
Overall, our algorithm demonstrates comparable statistical performance to the theoretically optimal OFUGLB while offering substantially improved computational efficiency.
E.3 Experiment on Forest Cover Type Data
In this experiment, we evaluate our proposed algorithm on the Forest Cover Type dataset from the UCI Machine Learning repository [Blackard, 1998]. This dataset comprises 581,012 labeled observations from different forest regions, with each label indicating the dominant tree species.
Following the preprocessing steps described in Filippi et al. [2010], we centered and standardized the 10 non-categorical features and appended a constant covariate. To enhance the diversity of the arm set and strengthen the experimental results, we partitioned the data into K = 60 clusters using unsupervised K K-means clustering, with the cluster centroids serving the contexts for each arm. For the logistic reward model, we binarized the rewards by assigning a reward of 1 to data points labeled as the second class ("Lodgepole Pine") and otherwise. The reward for each arm was then computed as the average reward of all data points within its corresponding cluster, yielding reward values ranging from 003 to 0.881.
For this task, we set the horizon to T = 1000 and the confidence parameter to = 0.01. After analyzing the data, set 6 and 200. We evaluated our algorithm against the same baselines used in the logistic bandit simulation experiment, running each method over 10 independent trials and averaging the results report the regret and the running time. The error bars in the figures denote 99% confidence intervals for both regret and runtime.
Compared to synthetic data, real-world datasets exhibit higher noise and complexity, demanding careful axploration-epllotaaii trade-offs. Thus, we shrank the estimated confidence set of all the algorithms in a comparable way achieve a better balance between exploration and exploitation in this real-world dataset. Traditional GLB algorithms are particularly sensitive to noise, often leading excessive exploration and higher regret.
Figure 5a presents the regret progression of different algorithms over time, while Figure 5b compares their computational efficiency. Figure 5c further illustrates the regret-time trade-off for method. The results demonstrate that our algorithm achieves significantly faster runtime without compromising robustness performance, even in noisy environments.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

We stated the assumptions in Section 2 and provided the complete proof in Appendix and
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Detailed discussion is done in Section 5 and Appendix E.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

Answer:
[No]
Justification:
The code and data are not released.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /niiss wwtppcccppppaaeeecccceeccccceeee /
siiissssiiiiiyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
See Section 5 and Appendix E.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We have shown the confidence intervals of the regret in the plots of various experiments in Section 5 and Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
30

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided the information on the computer resources needed to reproduce the experiments in Section and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: atttp::/neeurfi http://ccc.pppptttttcccccccteeee
Answer: [Yes]
Justification: have reviewed the NeurIPS Code of Ethics and we have followed the paper.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper presents theoretical work to advance Machine Learning. As it does not directly address applications, we do not identify specific societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The data and the experiments not related to the models that have high risk for misuse, but based on simulation and toy datasets.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make 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?
Answer: [Yes]
Justification: We have properly credited the creators of all assets and explicitly mentioned and respected their licenses and terms of use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode. thcode. com/ datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
32

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
We did introduce any new assets in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our research does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do involve any human subjects in our research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
33

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: We did not use any LLMs as any important, original, or non-standard compo- nents.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //terr//s.....eeeee ttt.urip..cc/ooofeeeeeeeeeeeeeee /20/////eeenee//2255////////// 20LL/LLM for what should or should be described.
34


Reviews:
[{"review_id": "T8ZsnS5CDu", "reviewer": "Reviewer_7rDn", "summary": "The paper studies the problem of generalized linear bandits, and proposes an algorithm which is jointly sample-efficient and computationally efficient. The proposed method relies on a new confidence set construction for generalized linear models, which is the main technical contribution of the paper. The new sequence of confidence sets is a sequence of ellipsoids, where each ellipsoid is centered at the estimate returned by online mirror descent (OMD), as opposed to the usual (regularized) maximum likelihood estimator (MLE). The proposed GLB-OMD method is evaluated in several experiments. In these experiments, it is found that the run time of GLB-OMB is a lot lower than that of the state-of-the-art OFUGLB method, yet the regret of GLB-OMD is not much worse than that of OFUGLB.", "questions": "By modifying the construction in this paper, would it be possible to construct even smaller confidence sets centered at OMD estimates which are not ellipsoids (perhaps by using a different regularizer/penalty in the OMD update)? For GLMs, restricting the confidence set to be an ellipsoid generally results in looser confidence sets.\n\nThe general technique of substituting the log-likelihood loss for the mix-loss to derive confidence sets has appeared in a couple of very recent works (Kirscher et al. 2025, Clerico et al. 2025). I don’t consider this to be a weakness, since these papers were released in close proximity to the submission deadline. Nevertheless, one could add a comment on this to the final version of the paper.\n\nKirschner, Johannes, et al. \"Confidence Estimation via Sequential Likelihood Mixing.\" arXiv preprint arXiv:2502.14689 (2025).\n\nClerico, Eugenio, et al. \"Confidence Sequences for Generalized Linear Models via Regret Analysis.\" arXiv preprint arXiv:2504.16555 (2025).", "limitations": "I understand that maximizing the upper confidence bound described in Section 3.1 is in general NP-hard. Indeed, in the linear case, the UCB is a convex function of the action, and convex maximization is in general NP-hard. Given that one of the main claims of the paper is about computational efficiency, it is a bit odd that this is never mentioned.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\nThe paper is generally well-written and the results are presented and explained well. In particular, I think that (for the most part) Section 4 does good job of explaining how the construction of the new confidence sequence works and how it differs to previous confidence sequence constructions.\n\nThe GLB-OMD method appears to be an effective solution to the problem described in the introduction. Namely, providing a generalized linear bandit algorithm with near-optimal regret and constant (w.r.t. $t$) time and space complexity per round.\n\n**Weaknesses:**\nMy biggest concern is with the significance of the problem being solved. I’m not sure that replacing a time complexity per round of order $t$ (or $\\log t$) with constant (w.r.t. $t$) time complexity is of great important when the time complexity of running the algorithm is largely determined by the cost of maximizing the UCB, unless the action set is finite and small. Moreover, as far as I can tell, the computational challenge of maximizing the UCB is not mentioned anywhere.\n\nI think that some of the claims made are not fully supported or slightly misleading. For instance, Remark 1 fails to mention that, for instance, the OFUGLB method also accommodates unbounded GLMs such as Gaussian or Poisson. On line 221, it is stated that “self-concordant GLBs are no more difficult than linear bandits”. This is true if $T$ is large enough to make the constant term in the regret bound negligible, but this constant term may be extremely large.\n\nSome relevant prior work is not cited. In particular, Proposition 2 is not a new result. For instance, in the book by Grünwald (2007), this result appears under the name “no-hypercompression inequality”.\n\nGrünwald, Peter D. The minimum description length principle. MIT press, 2007.", "was_revised": true, "final_justification": "The authors’ rebuttal has addressed the concerns raised in my review. I believe that the paper should be accepted, so I have raised my score.", "rebuttal": "We thank the reviewer for the insightful comments and for bringing the concurrent work to our attention. In the revision, we will include these works for discussion. Below, we address your concerns regarding the significance of the one-pass update and clarify several statements in the paper.\n\n---\n\n**Q1:** My biggest concern is with the significance of the problem being solved...the computational challenge of maximizing the UCB is not mentioned anywhere.\n\n**A1:** We understand that the computational cost of UCB-type algorithms stems from two components: parameter estimation and arm selection. We agree with the reviewers that identifying the arm that maximizes UCB is generally computationally challenging. Our main contribution is the development of **a one-pass estimator (and confidecne set) for the GLB problem**, which we believe is of both theoretical interest and practical value. \n\nIn the revision, we will (1) make the computaional challenge of the UCB maximization step clearly in the paper and (2) further highlight the significance of the development of one-pass estimator:\n\n- $\\underline{\\mbox{One-pass estimator for GLB as the linear bandits setting}}$: We note that our estimator operates in a one-pass fashion, which not only performs updates **in $O(1)$ time complexity** per round but also **requires no storage of historical data**, retaining only the current estimator $\\theta_t$ and Hessian $H_t$. In recent years, the design of one-pass estimators for GLB has attracted increasing attention [Zhang et al., 2016; Jun et al., 2017; Faury et al., 2022]. This direction is particularly compelling because, in the linear bandit setting, the least-squares estimator can be computed in a one-pass manner with O(1) time and memory per round. In contrast, the non-linearity of the link function in GLB introduces substantial computational challenges. *A natural question is whether it is possible to design GLB estimators that are as efficient as those in the linear case*, while still maintaining statistical efficiency. We provide an affirmative answer to this question.\n- $\\underline{\\mbox{Finite-arm case is common in practice}}$: From the practical side, our motivation for combining the one-pass estimator with the UCB strategy is that many real-world applications involve a finite number of arms. Examples include article recommendation tasks [1,2]. Moreover, many experimental evaluations of contextual bandits are also typically conducted in the finite-arm setting [3]. In such cases, training the estimator would become one of the major computational bottleneck.\n- $\\underline{\\mbox{Beyond LinUCB type method}}$: Finally, we would like to note that our one-pass estimator can serve as a versatile **plug-in component** applicable to a broad class of methods, not limited to LinUCB-type algorithms. For instance, following the same argument as  of Faury et al. (2022 Appendix D.2), the estimator can be applied to **Thompson Sampling**, where the arm selection step reduces to a convex optimization problem. \n\n[1] An Unbiased Offline Evaluation of Contextual Bandit Algorithms with\nGeneralized Linear Models. JMLR 2012.\n\n[2] A contextual-bandit approach to personalized news article recommendation. WWW 2010.\n\n[3] A Contextual Bandit Bake-off. JMLR 2018.\n\n---\n\n**Q2** : some of the claims made are not fully supported or slightly misleading.\n\n**A2:** We will clarify the statements as follows:\n\n> \"not noting that OFU‑GLB [Lee] also handles unbounded GLMs\" \n\nThank you for the comments. we will clearly mention this in the next version.\n\n> claiming self‑concordant GLBs are “no more difficult” than linear bandits without accounting for the potentially huge constant term\n\nYou are right, this expression is a bit sloppy as the second term contains the large constant $\\kappa$. We will revise the sentence as: \"...self-concordant GLBs **do not significantly exceed** the complexity of linear bandits, as our method achieves comparable regret and computational efficiency to OFUL for linear bandits **for sufficiently large $T$**\"\n\n---\n\n**Q3** : In particular, Proposition 2 is not a new result.\n\n**A3:** Thank you for letting us know. We believe the reviewer is referring to Lemma 2 in our paper. As noted by *Clerico et al., 2025* (in the paragraph following Proposition 2.1), this proposition can be traced back to *Ville (1939)* and is also known as the “no-hypercompression inequality.” We were not previously aware of the proposition’s historical depth and will make sure to clearly acknowledge this in the revised version.\n\n---\n\n**Q4** : Could the method yield tighter, non‑ellipsoidal confidence sets by changing the OMD regularizer, instead of restricting to (looser) ellipsoids?\n\n**A4**: Yes. Based on the analysis in Section 4, it is indeed possible to construct a tighter confidence set of the form\n\n$\\mathcal{C}\\_t = \\\\left\\\\{\\theta\\in \\mathbb{R}^d \\mid \\sum\\_{s=1}^{t-1} \\ell_s(\\theta) \\leq \\sum\\_{s=1}^{t-1} m_s(P_s) + \\log \\frac{1}{\\delta} \\\\right\\\\},$\n\nwhere $P_s$ denotes a Gaussian distribution with mean $\\theta_s$.\n\nThe primary motivation for using ellipsoidal confidence sets **lies in computational efficiency** as they allow for a closed-form expression to compute $\\mathrm{UCB}_t$ with a per-arm cost of $O(d^2)$. In contrast, constructing UCBs from non-ellipsoidal confidence sets requires solving a convex optimization problem for each arm with a computational cost of $O(t)$ per iteration.\n\nMoreover, ellipsoidal sets are more storage-efficient. They only require maintaining the mean and covariance, enabling one-pass updates. Non-ellipsoidal sets, on the other hand, typically require storing the full history of observations, with space complexity growing linearly in $T$.\n\n---\n\n**Q5 :** substituting the log-likelihood loss for the mix-loss to derive confidence sets has appeared in a couple of very recent works\n\n**A5:** Thank you for bringing these concurrent papers to our attention. After a quick review, we found that the mix loss is indeed used in Section 3.3 of *Kirschner et al., 2025* and *Clerico et al., 2025* to derive confidence sets. The main distinction lies in the choice of comparator: their confidence sets are derived **based on the MLE**, while ours are built around **the OMD estimator**.\n\nThis difference in objectives leads to distinct constructions of the distribution $P_s$ and subsequent analysis. Specifically, the prior works construct $P_s$ using exponential weights, whereas we take $P_s$ to be a Gaussian distribution. Naturally, the confidence sets in *Kirschner et al.* and *Clerico et al.* are tighter, but our ellipsoidal confidence sets based on the OMD framework offer better computational efficiency. We will properly highlight the similarities and differences with these concurrent works in the next revision."}, {"review_id": "6Mq0zt0FRX", "reviewer": "Reviewer_h1Sp", "summary": "The paper introduces a new, tight concentration bound for the online mirror descent (OMD)-based online estimator for generalized linear bandit (GLB) that takes $\\mathcal{O}(1)$ space/time complexity per round. The analysis involves appropriately using the notion of mix losses from online learning, which allows it to generalized to GLBs beyond prior works that were only applicable to logistic losses. The new concentration-based UCB algorithm is shown to achieve nearly tight (up to norm factors) regret bounds, and is validated empirically across logistic and Poisson bandits.", "questions": "1. How was the runtime computed? Did you use time or timeit?\n2. Can the authors plot the confidence regions as well? Also, in line 710-711, the authors state \"as the algorithm must navigate a rapidly expanding confidence region.\" Is it really expanding, though? Because at the end, $\\beta_t(\\delta) = \\Theta(\\log t)$ and the number of terms for the log-likelihood loss on the LHS increases linearly.\n3. If the arm-set is fixed, then could one hope for slightly better guarantee by any chance, e.g., [1]?\n\n\n[1] https://arxiv.org/abs/2202.02407", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- Well-written\n- Technically sound, and the proposed approach to building new concentration seems distinct from prior works.\n\n\n**Weaknesses**\n- Some of the lemmas are lacking the original references. For instance, Lemma 8 is originally Lemma 7 & 8 of Abeille et al. (2021), which in turn was originally proved in Lemma 9 of Faury et al., (2020). Also, the maximal inequality is actually originally known as Ville's inequality due to Ville (1939). Also, the whole idea of utilizing self-concordance is originally due to Bach (2010).\n- At the end, the proof proceeds similarly to \"regret-to-confidence-set\" conversion-type results [1,2] as well as the recent PAC-Bayes argument for GLBs [3]. Especially the overall proof flow of Theorem 1 (martingale, Ville's inequality, Donsker-Varadhan-type characterization of KL, use of KL closed-form) resembles [3], although there are indeed key differences, such as the choice of posterior ([3] chooses uniform while this paper chooses Gaussian? please correct me if I'm way off here). Anyhow, some discussions to such relevant literature would be nice.\n- Over the 10 independent trials, some sort of confidence/error interval would be nice addition on top of the average regret! Since 10 is a bit small, maybe bootstrapped confidence interval?\n- Later, I hope that the authors would release the codes :)\n\n**Typos**\n- Line 629: o $\\Rightarrow$ To\n\n\n[1] https://proceedings.mlr.press/v238/lee24d.html\n\n[2] https://arxiv.org/abs/2504.16555\n\n[3] https://openreview.net/forum?id=MDdOQayWTA", "was_revised": true, "final_justification": "Much of my concerns have been addressed. I maintain my score of 5.", "rebuttal": "Thank you for the appreciation of our work and for the constructive feedback! In the revision, we will add the original reference for the technical lemma and clarify the connection and differences with the previous papers on GLB. Below, we provide detailed responses to your questions.\n\n---\n\n**Q1** Some of the lemmas are lacking the original references.\n\n**A1:** Thank you for pointing this out. We will correct the citation in the future version. Specifically, we will make the following revision:\n\n- Lemma 8 --> Lemma 8 (Lemma 9 of Faury et al. [2020]); \n- Lemma 9 (Theorem 3.9 of Lattimore and Szepesv&aacute;ri [2020]). --> Lemma 9 (Ville [1939]).\n- Add: Bach [2010] first utilized self-concordance to analyze logistic regression.\n\n---\n\n**Q2:**  The proof proceeds similarly to ‘regret‑to‑confidence‑set’ conversion‑type results [1, 2] as well as the recent PAC‑Bayes argument for GLBs [3]\n\n**A2:** Thank you for the insightful comments. Indeed, our analysis follows a similar structure to the “regret-to-confidence-set” framework, but with several key distinctions. One major difference is that in [1,2,3], the confidence set is constructed **for the MLE estimator**, whereas our approach builds it for the **OMD estimator.** This fundamental distinction leads to a different construction of the virtual algorithm (or intermediate term) used in the decomposition. In the following, we provide a brief discussion of the differences compared to the work on GLB [2,3].\n\n- Comparison with [3]: Specifically, when comparing with [3], Lemma 3.1 in [3] upper bounds the cumulative loss $\\mathcal{L}\\_t(\\theta_*) := \\sum\\_{s=1}^t \\ell_s(\\theta_*)$ using the expected cumulative loss under a fixed uniform distribution $Q$, i.e., $\\mathbb{E}\\_{\\theta \\sim Q}[\\sum_{s=1}^t \\ell_s(\\theta)]$. In contrast, we upper bound $\\mathcal{L}\\_t(\\theta_*)$ via the mix loss constructed from a time-varying Gaussian distribution $P_s$. This use of the mix loss and the dynamic nature of $P_s$ is essential in tracking the time-varying OMD estimator throughout our analysis.\n\n- Comparison with [2]: During the rebuttal, we also became aware of a very recent paper [2] (posted on arXiv in April) that similarly uses a mixed loss for confidence set construction. The main difference lies in the design of the distribution $P_s$ for the mix loss: [2] builds $P_s$ based on the exponential weights method to track the MLE estimator, while our distribution $P_s$ is specifically tailored to follow the OMD estimator.\n\nIn the next version, we will include a more detailed technical comparison with related work, highlighting both the similarities and the key differences between our approach and prior or concurrent studies.\n\n---\n\n**Q3:** some sort of confidence/error interval would be nice addition on top of the average regret\n\n**A3**: In Figures (a), (b), (c), and (d), we use **shaded regions** to represent the error intervals.  In the Poisson bandit experiments (Figures (c) and (d)), the error bars are relatively small compared to the scale of the regret, making them nearly invisible. For the Covertype dataset experiments in the appendix, error bars are also included to illustrate variability.\n\nIn the revised version, we will include a more detailed explanation of the error bar configuration. Specifically, the shaded regions in the regret plots represent 99% confidence intervals, computed from 10 independent runs with different random seeds. In the Covertype Regret-vs-Time figure, the error bars also denote 99% confidence intervals for both regret and runtime. \n\n---\n\n**Q4:** Later, I hope that the authors would release the codes. How was the runtime computed? Did you use time or timeit?\n\n**A4:** Thank you for the interest! We will release the code along with the next version. We use \"time\" to record the running time. We will clarify this in the paper.\n\n---\n\n**Q5:**  Can the authors plot the confidence regions as well? Also \"as the algorithm must navigate a rapidly expanding confidence region.\" “Is it really expanding, though?\n\n**A5:** Thank you for your suggestions. In the original sentence, our intention was to convey that the confidence set expands **with increasing values of $S$**, rather than over time $t$. As shown in Figure 3(c) for Poisson Bandits, we observe that the running time of OFU-GLB increases with $S$. We attribute this to the fact that the confidence set (Equation 44) used by OFU-GLB grows with $S$, which in turn increases the computational cost of constructing the UCB for each arm. In contrast, the running times of OMD-GLB and GLOC are not affected by $S$, as they employ ellipsoidal confidence sets that allow for closed-form computation of the UCB.\n\nIn the next version, we will revise the sentence to: *\"...as the algorithm will navigate an expanding confidence region with respect to $S$\"*, and we will also include visualizations of the confidence regions for the different methods.  \n\n-------\n\n**Q6**: If the arm‑set is fixed, then could one hope for slightly better guarantee by any chance, e.g., [1]?\n\n**A6**: Thank you for the insightful questions. One of the main challenges in obtaining a bound with $O(\\sqrt{d})$ dependence on dimensionality appears to be the need for an OMD-based analogue of Lemma 1 from Mason et al., 2022, which itself is essentially derived from Theorem 1 in Jun et al., 2022. If a warm-up procedure is allowed, it may be possible to adapt the proof of [Theorem 1, Jun et al., 2022] to accommodate the OMD estimator. This is a promising and interesting direction for future work, and we will incorporate a discussion of it in the next version.\n\n**Ref:** Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits. Jun et al., ICML 2022."}, {"review_id": "dotFhQihMc", "reviewer": "Reviewer_JoLY", "summary": "The authors propose a new algorithm for the General Linearized Bandits setting which enjoys a balance of both computaional and statistical efficiency improvements over previous methods.\n\nSpecifically, they propose an OMD-based estimator for a confidence set for the latent parameter $\\theta_*$ which provides tighter confidence sets than previous approaches by leveraging self-concordance. They use this estimator to provide uncertainty sets for a UCB-style algorithm that, together with the estimator, has constant memory and time costs while achieving competitive regret performance with methods requiring orders of magnitude more compute. \n\nThey provide theoretical analysis and experiemntal results on synthetic tasks to demonstrate the gains assocaited with their approach.", "questions": "My primary concerns with this paper are in its writing clarity and organisation. Addressing the weaknesses outlined above are sufficient grounds for me to increase my clarity score.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "*Strengths:*\n- Generalizes OMD + UCB approach to the broader GLB setting\n- Improves SotA for logistic bandits across the regret, time, memory frontier\n- Regret analysis with impressive empirical results across both statsitical and computational fronts (1000x test time computational improvement)\n- Leveraging self-concordance for inproved confidence sets is elegant and general\n\n*Weaknesses*\n\n- Although the core contributions of this paper are strong, overall the paper reads as somewhat rushed in its organsation and preparation. For example, the introduction was harder to read than necessary, with many of the core definitions deferred to the preliminaries in a way that made it hard to appreciate what exactly was being estimated and how that estimate was being used within a UCB framework. This feels unneccessary since it ultimately is quite a simple quantity to describe in one or two sentences. Generally, assumptions in the first few pages of the paper felt scattered in the prose. For example, it wasn’t clear to me if the link function $\\mu$ was known to the agent, belonged to a family etc. until the preliminaries. I found it hard to apprecaite what the setting was exactly until multiple passes. In short, the full setting only became clear to me upon reading the preliminaries; the introduction felt confusing.\n- Some technical assumptions are made in the notation which never feature in the prose of the paper, e.g. the action sets $\\mathcal{X}_t$ appear to be non-stationary given the $t$ subscripts, yet there is no motivaiton for this consideration and no regard to it in the description of the setting. This felt disracting.\n- The paper contains some instances of vague expersions such as “non-linearity is beneficial” which made for a somewhat frustrating read.\n- Phrases like “bridging the loss gap” are unclear until deeper into the proof section and made for a confusing read.\n- Some sentences seem incomplete, e.g. “We also note that OMD-based online estimators have been used to develop jointly efficient algorithms in the logistic bandit setting … their analyses of the confidence set rely heavily on the specific structure of the logistic link function, limiting their applicability to more general GLB models.” lacks a bridge word such as “but” or “however”\n- Figures lack clarity, the shaded region should be well defined.\n- There are some notation inconsistencies, such as starting wth $\\mathbf{x}$ early in the paper for actions but then switching to $X_t$ later, and mentioning that the notation is due to actions being “random variables”, which didn’t help me apprecaite why earlier notation was different; also $\\tau$ is not defined anywhere in the paper yet appears in important definitions.\n- They say “This bound is nearly optimal in terms of the horizon $T$ up to logarithmic factors” but give no specific citation for this claim or substantiate it.", "was_revised": true, "final_justification": "This paper generalizes OMD + UCB to the broader GLB setting. They improve SotA for logistic bandits across the regret, time, memory frontier, and include regret analysis with impressive empirical results across both statistical and computational fronts. During the rebuttal period, the authors engaged with my questions and provided thoughtful feedback that improved the paper and addressed my concerns. For these reasons, I recommend acceptance.", "rebuttal": "Thank you for appreciating the technical contributions of our work and for the helpful comments! The main concerns raised relate to the clarity of (1) the problem setup and (2) the explanation of UCB in the introduction. In the revision, we will improve the introduction and refine several vague expressions throughout the paper. Below, we outline our detailed revision plans. \n\n---\n\n**Q1: Regarding the writing in the introduction section**\n\n> the core definitions deferred to the preliminaries ... what exactly was being estimated and how that estimate was being used within a UCB framework\n\n> if the link function was known to the agent, belonged to a family etc.\n\n**A1:** Thank you for the constructive feedback. We would revise the introduction to make the problem setup and issue of parameter estimation clearer. We plan to make the following revision:\n\n- Add more details about the problem setup and assumptions at the first paragraph\n\n$\\underline{\\mbox{[Revision for first paragraph]}}$: ...receiving feedback in the form of rewards. In this paper, we study the contextual multi-armed bandit problem under the framework of generalized linear models (GLMs). In this setting, each action is characterized by a contextual feature vector $\\mathbf{x} \\in \\mathcal{X}\\_t \\subset \\mathbb{R}^d$, **where the arm set $\\mathcal{X}_t$ can vary over time**. The learning process can be seen as a $T$ round game between the learner and the environment. For each round $t$, upon selecting an action $X_t\\in\\mathcal{X}\\_t$ , the learner receives a stochastic reward $r_t \\in \\mathbb{R}$, which is generated according to a GLM (see definition in Section 2.1).* The goal of the learner is to maximize the cumulative expected reward obtained over the time horizon $T$. Under the GLM model, the expectation of the reward satisfies $\\mathbb{E}[r_t\\,|\\,X_t] = \\mu(X_t^\\top \\theta_*)$, where $\\mu: \\mathbb{R} \\to \\mathbb{R}$ is a non-linear link determined by the GLM model and **is known to the learner**. The unknown part is the underlying parameter $\\theta_* \\in \\mathbb{R}^d$ , **which needs to be estimated by the learner from the observed action-reward pairs.**...\n\n[*footnote:*] $*$: To highlight its stochastic nature, we denote the action selected by the learner as $X_t$, in contrast to the deterministic case, for which we use $\\mathbf{x}$.\n\n- Add more details about the UCB method at the second paragraph\n\n$\\underline{\\mbox{[Revision for second paragraph]}}$: A canonical solution to the Generalized Linear Bandit (GLB) problem is the GLM-UCB algorithm [Filippi et al., 2010], which belongs to the family of UCB-type methods [Agrawal, 1995; Auer, 2002]. Specifically, at each iteration $t \\in [T]$, the algorithm **first estimates the true parameter $\\theta_*$** **using maximum likelihood estimation based on the historical data** $\\\\{(X_s, r_s)\\\\}\\_{s=1}^{t-1}$ and yields an estimator $\\theta_t$. Using $\\theta_t$, it then computes the empirical expected reward for each arm and constructs an upper confidence bound (UCB) to guide arm selection. The GLM-UCB algorithm achieves a regret bound of $\\mathcal{O}(\\kappa \\sqrt{T})$, where the constant $\\kappa = 1/\\inf_{\\mathbf{x}\\in\\cup_{t=1}^T\\mathcal{X}\\_t,\\theta\\in\\Theta} \\mu'(\\mathbf{x}^\\top\\theta)$ captures the non-linearity of the link function $\\mu$. While GLM-UCB is nearly optimal in its dependence on $T$, the non-linearity of the link function raises significant concerns regarding both computational and statistical efficiency...\n\n\n---\n\n**Q2: About the time-varying arm set $\\mathcal{X}_t$.**\n\n**A2:** Thank you for pointing this out. We use $\\mathcal{X}_t$ to indicate that we consider a setting where the arm set may change over time. A time-varying arm set is arguably one of the most general settings in the linear bandits literature, as it does not require any distributional assumptions on the action set. This setting aligns with many works on (generalized) linear bandits, such as [1,2,3]. In the revised version of the paper, we will make this dynamic action set assumption more explicit and clearly motivate it in the main text.\n\n$\\underline{\\mbox{[Revision at Section 2.1]}}$: ...A stochastic reward $r_t \\in \\mathbb{R}$. Here, we use the notation $\\mathcal{X}_t$ to indicate that the arm set can **change over time**. This modeling assumption allows us to capture many common scenarios in real-world applications. For example, in product recommendation systems, the items may be dynamically added or removed over time. This requires the algorithm to adapt to the current set of available options.\n\n[1] Improved algorithms for linear stochastic bandits. Abbasi-Yadkori et al., 2011\n\n[2] Improved optimistic algorithms for logistic bandits. Faury et al., 2020.\n\n[3] A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits. Lee et al., 2024.\n\n---\n\n**Q3: some instances of vague expersions**\n\nThank you for highlighting this. We will made the following revision:\n\n> line 132: \".. $\\kappa_*$ appears at the denominator, indicating that the non-linearity is beneficial to regret minimization\"\n\n-->\" $\\kappa_*$ appears at the denominator, **which largely improves the $O(\\kappa\\sqrt{T})$ bound by Filippi et al., [2010]**\"\n\n> Line 304 \"In our analysis this term is similarly instrumental in bridging the cumulative loss gap between..., thereby enabling a sharp bound for the estimation error.\"\n\n-->In our analysis, the mix loss is instrumental in analyzing the *inverse regret* defined in (9). In particular, the decomposition based on the mix loss $m_s(P_s)$ enables a more general and analytically versatile formulation than $\\ell_s(\\tilde{\\theta}_s)$ used in (9). The former reduces to the latter when $P_s$ is chosen as a Dirac distribution, while more carefully chosen distributions can lead to tighter bounds.\n\n---\n\n**Q4: Some sentences seem incomplete**\n\n**A4:** We will make the revision as follows:\n\n> line 58-60: \" ... with Bernoulli rewards, their analyses of the confidence set rely heavily on the specific structure of the logistic link function $\\mu(z) = 1/(1+e^{-z})$, limiting their applicability to more general GLB models.\"\n\n$\\underline{\\mbox{[Revision for Line 58-62]}}:$ We also note ..., a special case of GLB with Bernoulli rewards. **However,** their analyses of the confidence set rely heavily on the specific structure of the logistic link function $\\mu(z) = 1/(1+e^{-z})$, which limits their applicability to more general GLB models.\n\n---\n\n**Q5: Figures lack clarity, the shaded region should be well defined.**\n\n**A5:** We appreciate this suggestion. In the revised version, we will add detailed figure captions. Specifically, the shaded regions in the regret plots represent the 99% confidence intervals, based on 10 independent runs with different random seeds. In the Covertype Regret-vs-Time figure, the error bars represent the 99% confidence intervals for both regret and runtime; we visually scaled the error bars (×2 for regret, ×6 for runtime) to enhance visibility. This will be clearly stated in the figure descriptions.\n\n---\n\n**Q6**: Notations about $\\mathbf{x}$ and defiition of $\\tau$\n\n**A6:** We will add the definition of $\\tau$ as below:\n\n$\\underline{\\mbox{[Revision at Line 95-96 for the defnition of $\\tau$ ]:}}$ ...$g:\\mathbb{R}\\rightarrow\\mathbb{R}$ is the dispersion function controlling the variability of the distribution **and $\\tau\\in\\mathbb{R}$ is a parameter that governs the variability of the distribution**.\n\nAs for the notation of the action, we follow the convention used by Abbasi-Yadkori et al. (2011), where $X_t$ denotes the learner's action as it is a random variable, while $\\mathbf{x}$ represents a deterministic action. To prevent any confusion, we will include a footnote the first time $X_t$ appears to clarify this distinction.\n\n**Ref:** Improved Algorithms for Linear Stochastic Bandits. Abbasi-Yadkori et al., 2011.\n\n---\n\n**Q7**: “This bound is nearly optimal in terms of the horizon up to logarithmic factors” but give no specific citation for this claim or substantiate it.\n\n**A7:** Thank you for pointing this out. For the logistic bandits problem, Abeille et al. (2022) established a lower bound of $\\Theta(\\sqrt{T/\\kappa_*})$. Since logistic bandits are a special case of GLBs, this implies that the lower bound for GLBs is at least $\\Theta(\\sqrt{T/\\kappa_*})$. In this sense, the $O(\\kappa \\sqrt{T})$ upper bound by Filippi et al. (2010) is nearly optimal in terms of the dependence on $T$, but suboptimal with respect to the dependence on $\\kappa$. We will clarify this point in the next version.\n\n**Ref:** Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits. Abeille et al., 2022."}, {"review_id": "I17RnPhHY6", "reviewer": "Reviewer_fAEe", "summary": "In this paper, the authors study the GLB problem and propose the first algorithm with $O(1)$ per-round computational complexity, achieved by leveraging the OMD estimator.\nThe main technical contribution is an improvement of the regret bound by a factor of $\\sqrt{\\log t}$ over the prior result of Zhang and Sugiyama [2023].", "questions": "Please see the questions listed in the Weaknesses section above.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\nThis paper is overall well-organized and easy to follow. The main technical results are supported by adequate claims, and the empirical results further strengthen the theoretical guarantees.\n\n\n**Weaknesses**\n\n- The main technical contribution seems to be the improvement by a $\\sqrt{\\log t}$ factor compared to Zhang and Sugiyama [2023].\nAre there any additional technical challenges in adapting the OMD estimator from Zhang and Sugiyama [2023] to the GLM setting? \nSince the overall algorithm and analysis closely follow those in Zhang and Sugiyama [2023], I am not fully convinced that the $\\sqrt{\\log t}$ improvement alone constitutes a substantial contribution.\n\n- No code is provided.\n\n- In the experiments, why wasn’t the proposed algorithm compared with that of Zhang and Sugiyama [2023]?\n\n     In Figure 1(a) and 1(b), why does RS-GLinUCB underperform in the case of $S=3$ compared to $S=5$?\n\n     Although the values of $\\kappa$ are smaller in the Poisson bandit setting than in the logistic case, warm-up-based methods like RS-GLinUCB completely fail.  Why does this happen?", "was_revised": true, "final_justification": "Most of my concerns have been successfully addressed, particularly with respect to the technical contribution. I still have some questions about the significance of the $\\sqrt{\\log t}$ improvement; however, as it stands, I believe the technical contribution is reasonable to merit acceptance.\n\nAlthough the lack of code is somewhat disappointing, I understand that sharing it may not be feasible under this year’s NeurIPS policies. Therefore, I will maintain my positive score.", "rebuttal": "Thank you for the helpful comments! We will highlight the technical contributions in comparison with Zhang and Sugiyama, and provide additional details on the experimental comparisons. The detailed responses are provided below:\n\n---\n\n**Q1**: Are there any additional technical challenges in adapting the OMD estimator from Zhang and Sugiyama [2023] to the GLM setting?\n\n**A1:** Thank you for the comments. We would like to take this opportunity to further highlight the main technical contributions of our paper. We note that the analysis in Zhang and Sugiyama [2023] **is not applicable** to the GLB setting, even with the addition of an $O(\\sqrt{\\log t})$ term. This is because their construction of the intermediate term relies heavily on the specific structure of the logistic loss and builds upon results from online logistic regression [Foster et al., 2018]. In the GLB setting, however, it remains unclear whether a good online estimator exists.\n\nOne of our key contributions is the introduction of the **mix loss** (Equation (9)) as an intermediate term. This allows us not only to extend the analysis to the more general GLB setting, but also, as a byproduct, to improve the $O(\\sqrt{\\log T})$ factor in the logistic bandit setting compared to the result in Zhang and Sugiyama [2023]. When handling the decomposition based on the mix loss, we employ a different strategy: we analyze term (a) using Ville’s inequality, and we provide a simplified analysis for term (b), which avoids the lengthy calculations appearing in Zhang and Sugiyama’s analysis.\n\n---\n\n**Q2**: No code is provided.\n\n**A2:** Thank you for the interest! We will release the code along with the next version of the paper.\n\n---\n\n**Q3**: In the experiments, why wasn’t the proposed algorithm compared with that of Zhang and Sugiyama \\[2023]?\n\n**A3:** When applied to logistic bandit tasks, the primary difference between the two algorithms lies in the confidence set radius. Our proposed GLB-OMD algorithm achieves a tighter confidence bound of $O(\\log t)$, compared to the $O((\\log t)^{3/2})$ bound in Zhang and Sugiyama \\[2023]. Theoretically, $\\beta_t^{\\text{GLB-OMD}}(\\delta) < \\beta_t^{\\text{MLogB}}(\\delta)$, which ensures that the performance of GLB-OMD will be better. That is also why we exclude OFULog+ (Lee et al. 2023) from the benchmark. (OFULog+ is similarly constructed as OFUGLB and is theoretically worse than OFUGLB)\n\nTo highlight this, we conducted additional experiments comparing the regret performance of GLB-OMD (our method) and OFUL-MLogB (Zhang and Sugiyama, 2023). Furthermore, after the initial submission, we found that the step size $\\eta$ for GLB-OMD can be refined to $\\eta = 1 + RS$, replacing the original value $\\eta = 2(1 + RS)$ used in Theorem 1. This refinement results in a tighter confidence set and improves the regret bound by a constant factor. We also included the refined results in the comparison. Due to time constraints, these experiments were run for 3000 rounds across 10 trials and included only computationally efficient algorithms. The final-round regret of these efficient algorithms is reported below.\n\n| S    | GLB-OMD (Our work) | OFUL-MLogB (Zhang and Sugiyama, 2023) | ECOLog (Faury et al. 2022) | GLOC (Jun et al. 2017) | GLB-OMD (Refined $\\eta$) |\n| ---- | ------------------ | ------------------------------------- | -------------------------- | ---------------------- | ------------------------ |\n| 3    | 227.42             | 236.04                                | 229.30                     | 347.07                 | 105.78                   |\n| 5    | 146.44             | 169.84                                | 224.28                     | 708.92                 | 82.58                    |\n| 7    | 99.03              | 114.73                                | 201.06                     | 1291.06                | 56.67                    |\n| 9    | 81.60              | 92.82                                 | 191.68                     | 1459.46                | 40.06                    |\n\n---\n\n**Q4**: In Figure 1(a) and 1(b), why does RS-GLinUCB underperform when $S = 3$ compared to $S = 5$?\n\n**A4:** Thank you for the questions. The RS-GLinUCB method incorporates a warm-up procedure (Algorithm 2, lines 4–8). In the experiments, the warm-up condition is typically triggered during the early stages of the learning process. The number of warm-up iterations is on the order of $O(\\kappa S^3 (\\log T)^2)$ as shown in Sawani et al., 2024. As a result, when $S = 5$, the method performs worse than when $S = 3$ during the initial phase, since more iterations are spent on warm-up. However, in the later stage, after the warm-up is mostly complete, the regret of the method follows the theoretical bound of $O(\\sqrt{T/\\kappa_*})$. Given that $\\kappa_* \\propto e^S$, the RS-GLinUCB method with $S = 5$ will ultimately outperforms the case with $S = 3$ when $T$ is large enough.\n\n---\n\n**Q5**: Although the nonlinear values are smaller in the Poisson bandit setting than in the logistic case, warm-up-based methods like RS-GLinUCB completely fail. Why does this happen?\n\n**A5:** The theoretical guarantee of RS-GLinUCB holds only when the rewards are almost surely bounded by a constant $R_{\\mathrm{reward}}$ , which does not apply in the Poisson bandit setting as the reward can be unbounded. To empirically evaluate the method in our experiments, we set $R_{\\mathrm{reward}}$ to ensure that the randome rewards are bounded with high probability within $T = 3000$ rounds, and used this value in the algorithm’s parameter configuration.\n\nHowever, as shown in Theorem 4.2 of the RS-GLinUCB paper, the regret scales as $O(R_{\\mathrm{reward}} ^5)$. This high dependence on $R_{\\mathrm{reward}}$  leads to poor performance when the algorithm is applied to the unbounded Poisson bandit setting."}]

Author rebuttal:

Meta-review: The paper proposes a new, UCB-type generalized linear bandit algorithm that efficiently updates the estimate and confidence set of the unknown parameter via OMD. The authors leverage the self-concordance property of GLMs and introduce the mix-loss to decompose the inverse regret within the confidence radius, thereby establishing a tight confidence set and attaining nearly optimal regret. The proposed algorithm improves on the state of the art in at least one aspect, either by reducing computational complexity or by improving the regret bound.
Reviewers agree that the paper merits acceptance but suggest improvements in writing clarity and organization for the final version.
Decision: Accept (poster)