acceptodds
Under review as a conference paper at ICLR 2027

Online Thompson Sampling for Generalized Linear Bandits

Abstract

Applying Thompson sampling (TS) to generalized linear bandits (GLBs) is computationally challenging because exact posterior updates are generally intractable. Existing GLB algorithms with strong regret guarantees typically rely on batch estimators built from accumulated data, while computationally efficient one-pass methods often require problem-dependent quantities, such as an upper bound on the context norm and a radius of a ball containing the true parameter, as explicit inputs to their implementation. We propose OnlineTS, an online TS algorithm for GLBs based on Bayesian one-pass online learning. Our method uses a Gaussian approximation induced by a local quadratic expansion of the log-likelihood, leading to a recursive posterior update that depends only on the current estimator and the current observation. We show that this Bayesian online one-pass estimator admits a high probability concentration bound in the bandit setting, which yields a frequentist regret bound of for OnlineTS over horizon . Thus, OnlineTS combines strong statistical performance with computational efficiency without requiring such problem-dependent quantities as inputs to its implementation. Through numerical experiments, we demonstrate that OnlineTS achieves regret competitive with the existing GLB methods at substantially lower computational cost.

Primary area:
reinforcement learning
Keywords:
Contextual bandit, Generalized linear bandit, Thompson sampling, Online learning, One-pass

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_dfBbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes OnlineTS for generalized linear bandits by combining an existing Bayesian one-pass estimator with Thompson sampling. The algorithm starts with batch MAP and Laplace updates, then switches to recursive Gaussian updates based on a local quadratic approximation of the likelihood. The main theoretical contribution is a high-probability concentration analysis under adaptive data collection, leading to a claimed O~(T)\widetilde O(\sqrt T) regret bound under a cumulative-curvature assumption. Experiments on synthetic logistic and Poisson bandits compare regret and runtime with existing GLB algorithms and examine sensitivity to the warm-start length and misspecified norm bounds.

Critical strengths
  1. Simple and efficient online updates. After the warm-start phase, OnlineTS updates its Gaussian approximation using only the current observation, with O(d2)O(d^2) computation and memory. The update does not require a known parameter norm bound or curvature lower bound. This offers a useful practical approach to approximate Thompson sampling for GLBs.

  2. Promising empirical performance. Experiments cover both logistic and Poisson rewards and show competitive regret at substantially lower runtime than batch-based randomized methods. The appendix also includes comparisons with correctly specified baseline parameters, supporting the practical value beyond robustness to misspecified bounds.

Critical weaknesses
  1. Limited theoretical improvement over GLB-OMD. OnlineTS requires the additional information-growth assumption A3, while its regret bound contains a leading C1−1/2dTC_1^{-1/2}\sqrt{dT} term that retains dependence on worst-case local curvature. GLB-OMD does not require A3 and confines worst-case curvature dependence to lower-order terms. Thus, the shared O~(T)\widetilde O(\sqrt T) rate obscures substantial differences in the guarantees.

  2. Limited experimental validation. The evaluation focuses on small synthetic settings without real-world datasets. Figure 6 also appears to show OnlineTS running slightly slower than GLB-OMD, leaving its practical computational advantage unclear. Since only OnlineTS receives batch initialization, the comparisons do not isolate the contribution of warm-starting from that of the subsequent online method.

Questions for authors
  1. Clarification of theoretical dependencies. Could you make the dependence hidden in C(λ,τ,S,L,R,R∗)C(\lambda,\tau,S,L,R,R^*) and the warm-start threshold M0M_0 explicit? Under the truncated Gaussian design, C1=c0/(g(τ)κlocald)C_1=c_0/(g(\tau)\kappa_{\mathrm{local}}d) introduces worst-case local curvature into the leading regret term. How should Table 1’s comparison with GLB-OMD be interpreted given this dependence and the additional assumption A3?

  2. Clarification of the claim about implementation without problem-dependent constants. Although the updates do not explicitly require constants such as SS and LL, the theoretically sufficient warm-start length depends on them through M0M_0. Does the method therefore avoid specifying these constants only in the updates, while still requiring their knowledge to select a provably valid t0t_0? Please clarify this distinction. Without an implementable adaptive stopping rule or an instance-independent tuning guarantee, the practical claim appears stronger than what the theory establishes.

  3. Clarification of runtime measurements. Appendix I.3 reports t0=45t_0=45. Does Figure 6 include all batch initialization costs? What fraction of OnlineTS’s runtime comes from warm-starting, posterior updates, and sampling/action selection? This breakdown would help explain why OnlineTS appears slightly slower than GLB-OMD despite its lower stated estimator-update complexity.

  4. Additional validation of the warm-start contribution. Does OnlineTS retain its regret advantage when GLB-OMD and other applicable baselines receive a comparable warm-up? It seems that in Figure 2, the warm start can be critical to the performance of OnlineTS, especially in the Poisson bandit case. GLB-OMD paper also discusses warm-up strategies in Sections 3.3 and 6, making this comparison particularly relevant. So is it possible to add warm-up to other baselines like GLB-OMD for fair comparison?

  5. Additional validation of scalability and applicability. Could you provide results across larger dimensions and parameter norms, together with a real-world benchmark such as Covertype? These would materially strengthen the evidence for computational scalability and performance beyond the current synthetic settings.

Reviewer_iKLEOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes OnlineTS for finite-action generalized linear bandits. It initializes with batch MAP estimates and Gaussian Laplace approximations, then switches to a recursive Gaussian update obtained by replacing each new negative log-likelihood with its local quadratic approximation. Thompson sampling uses this approximate posterior throughout both phases. After initialization, posterior maintenance uses only the current mean, precision matrix, and new observation. The main claimed contribution is a uniform concentration result for the recursive estimator under adaptively collected bandit data. Combined with a persistent-information assumption, this yields a high-probability regret bound whose leading dependence on the horizon is O~(dT)\widetilde O(d\sqrt T) when C1−1=O(d)C_1^{-1}=O(d). Logistic and Poisson experiments examine initialization, sensitivity of competing methods to supplied norm bounds, and the regret-runtime trade-off.

Critical strengths
  1. The algorithm addresses a practical computational bottleneck with a particularly simple update. The precision receives a rank-one Hessian increment, and the mean takes a corresponding preconditioned gradient step. Sherman–Morrison therefore gives O(d2)O(d^2) posterior-update cost and O(d2)O(d^2) retained state after initialization. This removes the growing data storage and repeated full-history optimization of batch posterior approximations. The distinction between the initial batch phase and the subsequent one-pass phase is clearly stated. The update also avoids a projection radius or curvature lower bound as an input. These are meaningful implementation advantages, even though selecting a theoretically sufficient initialization time remains a separate issue.

  2. The analysis identifies the stability mechanism for this estimator. Lemma C.1 derives a recursion for VtV_t with a superlinear remainder. This explains why a good starting estimate matters: approximation errors can propagate through the recursion, whereas a sufficiently accurate initialization allows the accumulated remainder to be controlled. Establishing this framework for adaptive bandit observations would be a useful extension, rather than just another derivation of the update formula.

  3. The experiments test the proposed mechanism and include meaningful counterchecks. Figure 2 reports both regret and parameter error: the failure of immediate online updating in the Poisson setting, followed by much more stable performance after a short batch phase, is consistent with the stability motivation. The logistic results also show that initialization is not equally important in every model.

Critical weaknesses
  1. The adaptive concentration argument used to initialize the recursion seems invalid. Lemma F.14 defines as=u⊤Ωˉt−1/2xsa_s=u^\top\bar\Omega_t^{-1/2}x_s and substitutes γ=ηas\gamma=\eta a_s into an MGF inequality conditional on Fs−1\mathcal F_{s-1} (page 56). Predictability of xsx_s does not make asa_s predictable: Ωˉt\bar\Omega_t includes future contexts, which may depend on the reward noise at time ss. Consequently, the conditional bound cannot be iterated as claimed. Fixing the terminal time tt does not remove this dependence. Conditioning on the final design would also require a new argument, because that design can reveal information about earlier noise. The subsequent use of Lemma F.13 additionally treats the random quantity ξt\xi_t as a fixed sub-exponential scale.

    There is a short exact counterexample to the displayed intermediate MGF inequality. Take d=1d=1, λ=1\lambda=1, νs−1=1/2\nu_{s-1}=1/2, independent standard Gaussian noises ϵ1,ϵ2\epsilon_1,\epsilon_2, x1=1x_1=1, and the predictable choice x2=1ϵ1<0x_2=\mathbf 1\\{\epsilon_1<0\\}. These noises satisfy the assumed conditional MGF bound. At the fixed time t=2t=2,

    \qquad \mathbb E Z_2 =\frac{1/\sqrt{1.5}-1/\sqrt2}{\sqrt{2\pi}}>0.$$ Thus $\mathbb E e^{\eta Z_2}\le e^{\eta^2}$ cannot hold for all sufficiently small positive $\eta$: its left-hand side has a positive linear term at zero, while its right-hand side does not. For example, the exact Gaussian calculation at $\eta=0.01$ gives approximately $1.000478>1.000100$. This establishes failure of the proof step, but it is not a counterexample to OnlineTS's regret guarantee.
  2. The localization argument changes the MAP regularizer inside an equality. Equation (E.40), page 43, defines ft(θ)=g(τ)−1∑sμ(xs⊤θ)xs+λθf_t(\theta)=g(\tau)^{-1}\sum_s\mu(x_s^\top\theta)x_s+\lambda\theta. Page 45 introduces an auxiliary λˉ\bar\lambda for Fisher-type normalization, explicitly retaining the original λ\lambda in the MAP estimator. Equation (E.46) nevertheless writes the difference ft(θ)−ft(θ∗)f_t(\theta)-f_t(\theta^*) with regularizer λˉ(θ−θ∗)\bar\lambda(\theta-\theta^*). With the stated definition of ftf_t, the correct identity is

    =F_t(\theta,\theta^*,\bar\lambda)(\theta-\theta^*) +(\lambda-\bar\lambda)(\theta-\theta^*).$$ The missing term matters because the auxiliary regularization is subsequently chosen as a function of $d+\log(1/\delta)$, rather than set equal to $\lambda$.
  3. Dimension and initialization dependence are lost in parts of the final bounds. Lemma E.4 states a threshold C2(dlog⁡d+log⁡(1/δ))C_2(d\log d+\log(1/\delta)) with C2C_2 depending only on K,L,σmin⁡,σmax⁡K,L,\sigma_{\min},\sigma_{\max}. Its proof sets c=c1/dc=c_1/d on page 33 and derives c4=min⁡c2/(8ν2),c/(4b)c_4=\min\\{c^2/(8\nu^2),c/(4b)\\}. The net and time-union bound on page 34 then requires controlling c5exp⁡!(dlog⁡(1+16L2/c)−c4t1).c_5\exp\\!\left(d\log(1+16L^2/c)-c_4t_1\right). Thus the resulting threshold contains c4−1c_4^{-1}, and c5c_5 itself depends on c4c_4. These dependencies pass through c6c_6 and c7c_7 but disappear when the proof declares C2C_2 independent of dd. Even setting aside truncation, the displayed choice c=c1/dc=c_1/d already matters. In addition, the stated ν\nu and bb contain log⁡(1/p0)\log(1/p_0), where p0p_0 is a Gaussian truncation probability that can depend strongly on dimension. Related dependence should also be retained when simplifying the regret bound.

  4. The theoretical comparison needs to distinguish persistent information from exploration supplied by TS. A3 is a substantive condition on the contexts selected by the policy, not just smoothness of the likelihood near θ∗\theta^*. It requires information to grow linearly in every direction. For fixed, independent arm directions with positive suboptimality gaps, obtaining that information can require linear sampling of suboptimal arms, so this is a substantial restriction relative to general GLB problems.

Questions for authors
  1. What valid adaptive concentration result replaces F.14? Please give the resulting score bound at t0t_0 and show whether it establishes B3 with the stated d+log⁡(1/δ)\sqrt{d+\log(1/\delta)} dependence.

  2. Can the localization proof be completed with the original MAP regularizer fixed?

  3. What are the corrected dimension and initialization dependencies? Please track c4,c5,c6c_4,c_5,c_6 and p0p_0 in Lemma E.4, or replace that derivation with one yielding the stated dimension-independent C2C_2.

  4. Can the main comparison state precisely what is guaranteed under A3 and what is supported by the practical default? In particular, please distinguish persistent information provided by the context process from any benefit of posterior sampling, and distinguish an implementable update from a certified choice of t0t_0.

Reviewer_wSCeOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes OnlineTS for generalized linear bandits. It begins with batch Laplace approximations during a warm-start phase and then switches to recursive Gaussian updates using individual observations. This avoids repeated optimization over the accumulated history. The paper presents estimator concentration and frequentist regret guarantees under local curvature and information-growth assumptions, together with experiments on logistic and Poisson bandits.

Critical strengths
  1. Relevant computational motivation. Repeated batch estimation is a practical bottleneck for approximate Thompson sampling in generalized linear bandits. The proposed one-pass updates directly address this issue by avoiding repeated access to the full observation history after initialization.

  2. Simple and interpretable algorithm. OnlineTS maintains a parameter estimate and a precision matrix through straightforward updates. The modification is conceptually simple, yet the reported performance gains are striking in the tested settings. This makes the approach potentially useful for practical sequential decision-making.

  3. Promising empirical results and an informative warm-start ablation. OnlineTS performs well against the main baselines, including comparisons with correctly specified norm bounds. Comparisons with batch randomized methods also suggest a favorable regret–runtime trade-off. Figure 2 demonstrates the practical importance of initialization for Poisson rewards. The successful warm-start settings use only 23–89 observations out of 10,000 rounds, which is particularly encouraging.

Critical weaknesses
  1. Lemma F.14 uses an invalid concentration argument for adaptive data. The proof defines as=u⊤Ωt−1/2xsa_s=u^\top\Omega_t^{-1/2}x_s, where Ωt\Omega_t depends on the entire trajectory up to time tt. These coefficients are generally not Fs−1\mathcal F_{s-1}-measurable, because future selected contexts can depend on the current reward. The conditional moment-generating-function assumption therefore cannot be applied with γ=ηas\gamma=\eta a_s as done in the proof. Fixing the terminal time tt does not resolve this dependence. A valid self-normalized concentration argument for adaptive observations is needed.

  2. The localization derivation in Appendix E.4 does not consistently distinguish λ\lambda from λˉ\bar\lambda. The batch MAP estimator and score map are defined using λ\lambda, but Equation (E.46) introduces the auxiliary λˉ\bar\lambda into the corresponding Taylor identity. Changing the matrix used to measure a norm does not justify changing the score map. If the score map is redefined using λˉ\bar\lambda, evaluating it at the original MAP estimator introduces a correction involving (λˉ−λ)(θ^tMAP−θ⋆)(\bar\lambda-\lambda)(\widehat\theta_t^{\mathrm{MAP}}-\theta^\star). This requires a corrected derivation, beyond stating that MM should be sufficiently large.

  3. The current appendix does not establish the main concentration and regret guarantees as stated. The preceding issues affect the warm-start concentration and localization arguments used to initialize the subsequent stability analysis. The regret analysis then relies on the resulting estimator guarantee. Consequently, these are substantive gaps in the justification of the main results, rather than isolated presentation errors. This does not establish that the main theorems are false, but the authors need to provide valid replacements and track any resulting changes to the rates and constants.

  4. The justification of Assumption A3 needs more careful treatment of dimension dependence. In Lemma E.4, the directional covariance lower bound scales as c=c1/dc=c_1/d, while the concentration exponent involves c4=min⁡{c2/(8ν2),c/(4b)}c_4=\min\{c^2/(8\nu^2),c/(4b)\}. The resulting sample-size threshold retains dependence through c4−1c_4^{-1}. This dependence needs to be propagated explicitly rather than absorbed into constants whose stated dependencies omit the dimension. As written, the argument does not establish the advertised threshold with the stated constants.

  5. The practical warm-start choice is not connected to a usable sufficient threshold. The requirement M≥M0M\geq M_0 depends on unknown problem quantities, including the local information-growth constants. Algorithm 1 switches at a predetermined time, and the analysis does not certify that the experimental choice of MM satisfies the theoretical requirement. Figure 2 provides useful evidence that a short warm-start works on the tested instance, but does not establish how the required duration changes with dimension, parameter norm, regularization, or context conditioning.

  6. Several experimental environments fall outside the theorem's assumptions or their supplied justification. The untruncated Gaussian contexts violate the bounded-context assumption A1. The singular Gaussian design is not covered by the positive-definite covariance conditions used in the A3 justification. In the deterministic basis setting with one arm per coordinate and suboptimal arms, A3 would require a linear number of observations in every coordinate, forcing linear regret. These experiments remain valuable, but their successful performance requires an explanation beyond the current theoretical results.

Questions for authors
  1. Can the authors provide an adaptive-data-valid replacement for Lemma F.14 and a corrected localization argument in Appendix E.4 that consistently distinguishes λ\lambda and λˉ\bar\lambda? Do these corrections change the warm-start or regret rates?

  2. Can the authors explicitly track the dimension dependence of the constants in the A3 justification, particularly through c4c_4 in Lemma E.4, and clarify which experimental environments are covered by the resulting assumptions?

  3. What guidance can be provided for selecting MM on a new instance? How does the successful warm-start duration change with dimension, parameter norm, and regularization?

  4. Which OFUGLB variant was implemented, and what exact confidence radii, regularization, initialization, and exploration scales were used for each baseline? In particular, how were the GLM-TSL/FPL settings adapted to Poisson rewards, and does the batch TS comparison match OnlineTS in all components other than the estimator update?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.