Provably Optimal Algorithms for Generalized Linear Contextual Bandits

Abstract

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 $\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 certain cases.

Published at ICML 2017

Cited by in corpus (60)

• Online Learning: A Comprehensive Survey
• Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Linear Stochastic Bandits Under Safety Constraints
• Model selection for contextual bandits
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Neural Thompson Sampling
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits
• A Simple Approach for Non-stationary Linear Bandits
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Dynamic Assortment Optimization with Changing Contextual Information
• Privacy-Preserving Dynamic Personalized Pricing with Demand Learning
• Model Selection in Contextual Stochastic Bandit Problems
• Improved Optimistic Algorithms for Logistic Bandits
• Neural Contextual Bandits with Deep Representation and Shallow Exploration
• Optimal No-regret Learning in Repeated First-price Auctions
• Locally Differentially Private (Contextual) Bandits Learning
• Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
• Semiparametric Contextual Bandits
• New Insights into Bootstrapping for Bandits
• Randomized Exploration in Generalized Linear Bandits
• Algorithms for Non-Stationary Generalized Linear Bandits
• Learning and Optimization with Seasonal Patterns
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling
• No-regret Exploration in Contextual Reinforcement Learning
• Tight Regret Bounds for Infinite-armed Linear Contextual Bandits
• Perturbed-History Exploration in Stochastic Linear Bandits
• Empirical Bayes Regret Minimization
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
• Stage-wise Conservative Linear Bandits
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Sparsity-Agnostic Lasso Bandit
• Deterministic Inequalities for Smooth M-estimators
• Impact of Representation Learning in Linear Bandits
• On the Performance of Thompson Sampling on Logistic Bandits
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
• Online Learning Demands in Max-min Fairness
• Old Dog Learns New Tricks: Randomized UCB for Bandit Problems
• Online Learning of Independent Cascade Models with Node-level Feedback
• Dueling RL: Reinforcement Learning with Trajectory Preferences
• Doubly robust Thompson sampling for linear payoffs
• Bandits Under The Influence (Extended Version)
• Reward-Biased Maximum Likelihood Estimation for Linear Stochastic Bandits
• Online Algorithm for Unsupervised Sequential Selection with Contextual Information
• Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits
• Regret Bounds for Generalized Linear Bandits under Parameter Drift
• UCB-based Algorithms for Multinomial Logistic Regression Bandits
• Self-Concordant Analysis of Generalized Linear Bandits with Forgetting
• Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms
• Regret Minimization in Stochastic Contextual Dueling Bandits
• Risk-aware linear bandits with convex loss
• CORe: Capitalizing On Rewards in Bandit Exploration
• Thompson sampling for zero-inflated count outcomes with an application to the Drink Less mobile health study
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
• $k\text{-experts}$ -- Online Policies and Fundamental Limits
• DART: aDaptive Accept RejecT for non-linear top-K subset identification
• Stochastic Multi-Armed Bandits with Control Variates
• Fatigue-aware Bandits for Dependent Click Models