# Provably Optimal Algorithms for Generalized Linear Contextual Bandits

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2017.

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

- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Delayed Feedback in Generalised Linear Bandits Revisited](https://mlsanity.com/paper/2207.10786/) (2022)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Multinomial Logit Contextual Bandits: Provable Optimality and Practicality](https://mlsanity.com/paper/2103.13929/) (2021)
- [Dynamic pricing and assortment under a contextual MNL demand](https://mlsanity.com/paper/2110.10018/) (2021)
- [Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning](https://mlsanity.com/paper/2202.10678/) (2022)
- [Survey on Fair Reinforcement Learning: Theory and Practice](https://mlsanity.com/paper/2205.10032/) (2022)
- [Mixed-Effect Thompson Sampling](https://mlsanity.com/paper/2205.15124/) (2022)
- [Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2209.06983/) (2022)
- [Regret Bounds for Generalized Linear Bandits under Parameter Drift](https://mlsanity.com/paper/2103.05750/) (2021)
- [UCB-based Algorithms for Multinomial Logistic Regression Bandits](https://mlsanity.com/paper/2103.11489/) (2021)
- [Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient](https://mlsanity.com/paper/2210.00750/) (2022)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)
- [Combinatorial Pure Exploration of Causal Bandits](https://mlsanity.com/paper/2206.07883/) (2022)
- [Stochastic Multi-Armed Bandits with Control Variates](https://mlsanity.com/paper/2105.03962/) (2021)
- [An Experimental Design Approach for Regret Minimization in Logistic Bandits](https://mlsanity.com/paper/2202.02407/) (2022)
- [Global Optimization with Parametric Function Approximation](https://mlsanity.com/paper/2211.09100/) (2022)
- [Combinatorial Causal Bandits without Graph Skeleton](https://mlsanity.com/paper/2301.13392/) (2023)
- [Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2405.20165/) (2024)
- [Top K Ranking for Multi-Armed Bandit with Noisy Evaluations](https://mlsanity.com/paper/2112.06517/) (2021)
- [Multiplier Bootstrap-based Exploration](https://mlsanity.com/paper/2302.01543/) (2023)
- [Learning Competitive Equilibria in Exchange Economies with Bandit Feedback](https://mlsanity.com/paper/2106.06616/) (2021)
- [Learning to Identify Top Elo Ratings: A Dueling Bandits Approach](https://mlsanity.com/paper/2201.04480/) (2022)
- [Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2406.13633/) (2024)
- [An Efficient Algorithm for Deep Stochastic Contextual Bandits](https://mlsanity.com/paper/2104.05613/) (2021)
- [Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback](https://mlsanity.com/paper/2109.06077/) (2021)

## Abstract (arXiv)

Contextual bandits are widely used in Internet services from news recommendation to advertising, and to Web search. Generalized linear models (logistical regression in particular) have demonstrated stronger performance than linear models in many applications where rewards are binary. However, most theoretical analyses on contextual bandits so far are on linear bandits. In this work, we propose an upper confidence bound based algorithm for generalized linear contextual bandits, which achieves an tildeO(√dT) regret over T rounds with d dimensional feature vectors. This regret matches the minimax lower bound, up to logarithmic terms, and improves on the best previous result by a √d factor, assuming the number of arms is fixed. A key component in our analysis is to establish a new, sharp finite-sample confidence bound for maximum-likelihood estimates in generalized linear models, which may be of independent interest. We also analyze a simpler upper confidence bound algorithm, which is useful in practice, and prove it to have optimal regret for certain cases.