# An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling

arXiv: https://arxiv.org/abs/2006.04012 · HTML: https://mlsanity.com/paper/2006.04012/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2020.

## Built on by (most cited first, 30 of 30)

- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks](https://mlsanity.com/paper/2106.02978/) (2021)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Doubly robust Thompson sampling for linear payoffs](https://mlsanity.com/paper/2102.01229/) (2021)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Multi-channel Autobidding with Budget and ROI Constraints](https://mlsanity.com/paper/2302.01523/) (2023)
- [Communication Efficient Federated Learning for Generalized Linear Bandits](https://mlsanity.com/paper/2202.01087/) (2022)
- [Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2310.18701/) (2023)
- [Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms](https://mlsanity.com/paper/2106.02979/) (2021)
- [Anti-Concentrated Confidence Bonuses for Scalable Exploration](https://mlsanity.com/paper/2110.11202/) (2021)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Does Sparsity Help in Learning Misspecified Linear Bandits?](https://mlsanity.com/paper/2303.16998/) (2023)
- [Learning to Identify Top Elo Ratings: A Dueling Bandits Approach](https://mlsanity.com/paper/2201.04480/) (2022)
- [Thompson sampling for zero-inflated count outcomes with an application to the Drink Less mobile health study](https://mlsanity.com/paper/2311.14359/) (2023)
- [Federated Linear Dueling Bandits](https://mlsanity.com/paper/2502.01085/) (2025)
- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)
- [Truncated LinUCB for Stochastic Linear Bandits](https://mlsanity.com/paper/2202.11735/) (2022)
- [On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Bandits](https://mlsanity.com/paper/2206.08111/) (2022)
- [Ranking In Generalized Linear Bandits](https://mlsanity.com/paper/2207.00109/) (2022)
- [Risk-aware linear bandits with convex loss](https://mlsanity.com/paper/2209.07154/) (2022)
- [Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2302.09440/) (2023)
- [ε-Neural Thompson Sampling of Deep Brain Stimulation for Parkinson Disease Treatment](https://mlsanity.com/paper/2403.06814/) (2024)
- [OLR-WA: Online Weighted Average Linear Regression in Multivariate Data Streams](https://mlsanity.com/paper/2512.14892/) (2025)
- [Learning in Distributed Contextual Linear Bandits Without Sharing the Context](https://mlsanity.com/paper/2206.04180/) (2022)
- [OLR-WAA: Adaptive and Drift-Resilient Online Regression with Dynamic Weighted Averaging](https://mlsanity.com/paper/2512.12779/) (2025)
- [Unveiling Statistical Significance of Online Regression over Multiple Datasets](https://mlsanity.com/paper/2512.12787/) (2025)
- [Combinatorial Allocation Bandits with Nonlinear Arm Utility](https://mlsanity.com/paper/2603.07005/) (2026)
- [Online Survival Analysis: A Bandit Approach under Cox PH Model](https://mlsanity.com/paper/2604.20296/) (2026)
- [Efficient Multinomial Logistic Bandit via Frequent Directions](https://mlsanity.com/paper/2606.11968/) (2026)

## Abstract (arXiv)

We consider the contextual bandit problem, where a player sequentially makes decisions based on past observations to maximize the cumulative reward. Although many algorithms have been proposed for contextual bandit, most of them rely on finding the maximum likelihood estimator at each iteration, which requires O(t) time at the t-th iteration and are memory inefficient. A natural way to resolve this problem is to apply online stochastic gradient descent (SGD) so that the per-step time and memory complexity can be reduced to constant with respect to t, but a contextual bandit policy based on online SGD updates that balances exploration and exploitation has remained elusive. In this work, we show that online SGD can be applied to the generalized linear bandit problem. The proposed SGD-TS algorithm, which uses a single-step SGD update to exploit past information and uses Thompson Sampling for exploration, achieves tildeO(√T) regret with the total time complexity that scales linearly in T and d, where T is the total number of rounds and d is the number of features. Experimental results show that SGD-TS consistently outperforms existing algorithms on both synthetic and real datasets.