Provable Optimal Algorithms for Generalized Linear Contextual Bandits

By Lihong Li, Yu Lu, Dengyong Zhou. 2017

86 citations recorded by the source corpus.

Contextual bandits are widely used in Internet services from news recommendation to advertising. Generalized linear models (logistical regression in particular) have demonstrated stronger performance than linear models in many applications. 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 $\tilde{O}(\sqrt{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 $\sqrt{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 the certain cases.

Subfields: Computational Mechanics, Computer Networks and Communications, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “In particular, we assume s(·) is an (unknown) linear function of the trajectory-feature φ(τ) ∈ Rd, and the link-function σ is the sigmoid Li et al. (2017).”
Optimal Algorithms for Stochastic Contextual Preference Bandits (2021, methodology): “Sequential decision-making problems with side information (in the form of features or attributes), have been popular in machine learning as contextual bandits [16, 13, 26].”
Online Learning: A Comprehensive Survey (2018, background): “The idea is to incorporate the given transaction cost into the optimization objective (Ormos and Urbán, 2013; Huang et al., 2015; Li et al., 2017a).”
Offline Multi-Action Policy Learning: Generalization and Optimization (2018, background): “The very recent work Li et al. (2017) has further extended to generalized linear contextual bandits.”