Online Thompson Sampling for Generalized Linear Bandits

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 $\tilde{O}(\sqrt{T})$ for OnlineTS over horizon $T$. 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.