Thompson Sampling for Contextual Bandits with Linear Payoffs

Abstract

Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state-of-the-art methods. However, many questions regarding its theoretical performance remained open. In this paper, we design and analyze a generalization of Thompson Sampling algorithm for the stochastic contextual multi-armed bandit problem with linear payoff functions, when the contexts are provided by an adaptive adversary. This is among the most important and widely studied versions of the contextual bandits problem. We provide the first theoretical guarantees for the contextual version of Thompson Sampling. We prove a high probability regret bound of $\tilde{O}(d^{3/2}\sqrt{T})$ (or $\tilde{O}(d\sqrt{T\log (N)})$), which is the best regret bound achieved by any computationally efficient algorithm available for this problem in the current literature, and is within a factor of $\sqrt{d}$ (or $\sqrt{\log (N)}$) of the information-theoretic lower bound for this problem.

Improvements from previous version: (1) dependence on d improved from d^2 to d^{3/2} (2) Simpler and more modular proof techniques (3) bounds in terms of log(N) added

References in corpus (3)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Further Optimal Regret Bounds for Thompson Sampling
• Learning to Optimize Via Posterior Sampling

Cited by in corpus (205)

• Further Optimal Regret Bounds for Thompson Sampling
• (More) Efficient Reinforcement Learning via Posterior Sampling
• Online Learning: A Comprehensive Survey
• An Efficient Bandit Algorithm for Realtime Multivariate Optimization
• A Survey on Practical Applications of Multi-Armed and Contextual Bandits
• Distributed Clustering of Linear Bandits in Peer to Peer Networks
• Optimal Best Arm Identification with Fixed Confidence
• A Survey on Contextual Multi-armed Bandits
• Cascading Bandits for Large-Scale Recommendation Problems
• Minimal Exploration in Structured Stochastic Bandits
• Making Contextual Decisions with Low Technical Debt
• Thompson Sampling for 1-Dimensional Exponential Family Bandits
• Online Interactive Collaborative Filtering Using Multi-Armed Bandit with Dependent Arms
• Bayesian Multi-Scale Optimistic Optimization
• An Information-Theoretic Analysis of Thompson Sampling
• A Contextual Bandit Bake-off
• Efficient Learning in Large-Scale Combinatorial Semi-Bandits
• An Actor-Critic Contextual Bandit Algorithm for Personalized Mobile Health Interventions
• A Tutorial on Thompson Sampling
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Bayesian policy gradient and actor-critic algorithms
• Neural Thompson Sampling
• Scalable Generalized Linear Bandits: Online Computation and Hashing
• Statistical Inference for Online Decision-Making: In a Contextual Bandit Setting
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits
• Latent Contextual Bandits and their Application to Personalized Recommendations for New Users
• Dynamic Assortment Optimization with Changing Contextual Information
• On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials
• Thompson Sampling for Learning Parameterized Markov Decision Processes
• Meta Dynamic Pricing: Transfer Learning Across Experiments
• Bootstrapping Upper Confidence Bound
• Interpretable Multi-Objective Reinforcement Learning through Policy Orchestration
• Doubly-Robust Lasso Bandit
• Personalized HeartSteps: A Reinforcement Learning Algorithm for Optimizing Physical Activity
• On Kernelized Multi-armed Bandits
• Thompson Sampling for the MNL-Bandit
• Streaming kernel regression with provably adaptive mean, variance, and regularization
• A Practical Method for Solving Contextual Bandit Problems Using Decision Trees
• Unified Models of Human Behavioral Agents in Bandits, Contextual Bandits and RL
• Adversarial Attacks on Linear Contextual Bandits
• Statistical Inference for Online Decision Making via Stochastic Gradient Descent
• Stochastic Bandits with Context Distributions
• Generalized Thompson Sampling for Contextual Bandits
• Unbounded Bayesian Optimization via Regularization
• High-Dimensional Sparse Linear Bandits
• Optimal No-regret Learning in Repeated First-price Auctions
• Power Constrained Bandits
• Stochastic Contextual Bandits with Known Reward Functions
• Federated Linear Contextual Bandits
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions
• Variational inference for the multi-armed contextual bandit
• Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
• Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback
• Non-Stationary Bandits with Habituation and Recovery Dynamics
• Semiparametric Contextual Bandits
• A Bandit Approach to Posterior Dialog Orchestration Under a Budget
• Randomized Exploration in Generalized Linear Bandits
• Latent Bandits Revisited
• New Insights into Bootstrapping for Bandits
• Speaker Diarization as a Fully Online Learning Problem in MiniVox
• Asymptotically Optimal Information-Directed Sampling
• Deep Neural Linear Bandits: Overcoming Catastrophic Forgetting through Likelihood Matching
• Cuttlefish: A Lightweight Primitive for Adaptive Query Processing
• EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits
• Online learning with Corrupted context: Corrupted Contextual Bandits
• A Neural Networks Committee for the Contextual Bandit Problem
• Thompson Sampling for Complex Bandit Problems
• Exploiting correlation and budget constraints in Bayesian multi-armed bandit optimization
• Deep Contextual Multi-armed Bandits
• Contextual Multi-Armed Bandits for Causal Marketing
• Using Adaptive Bandit Experiments to Increase and Investigate Engagement in Mental Health
• contextual: Evaluating Contextual Multi-Armed Bandit Problems in R
• Cold-start Problems in Recommendation Systems via Contextual-bandit Algorithms
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling
• Information Directed Sampling for Linear Partial Monitoring
• The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
• Stochastic Bandits with Linear Constraints
• Getting too personal(ized): The importance of feature choice in online adaptive algorithms
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime
• Online Semi-Supervised Learning with Bandit Feedback
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Stochastic Linear Bandits Robust to Adversarial Attacks
• Perturbed-History Exploration in Stochastic Linear Bandits
• Empirical Bayes Regret Minimization
• Bayesian bandits: balancing the exploration-exploitation tradeoff via double sampling
• Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits
• Reinforcement Learning for Dynamic Bidding in Truckload Markets: an Application to Large-Scale Fleet Management with Advance Commitments
• Adaptive Exploration in Linear Contextual Bandit
• Reward Biased Maximum Likelihood Estimation for Reinforcement Learning
• On Thompson Sampling with Langevin Algorithms
• Stage-wise Conservative Linear Bandits
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis
• Causal Bandits with Unknown Graph Structure
• Differentiable Bandit Exploration
• On the Prior Sensitivity of Thompson Sampling
• Offline Contextual Bayesian Optimization for Nuclear Fusion
• Meta-Learning Bandit Policies by Gradient Ascent
• Conversational Contextual Bandit: Algorithm and Application
• Parallelizing Thompson Sampling
• Thompson Sampling for Contextual Bandit Problems with Auxiliary Safety Constraints
• Dynamic Learning of Sequential Choice Bandit Problem under Marketing Fatigue
• Group Fairness in Bandit Arm Selection
• Contextual Bandit with Missing Rewards
• Differentiable Linear Bandit Algorithm
• Nonparametric Stochastic Contextual Bandits
• Hyper-parameter Tuning for the Contextual Bandit
• Sparsity-Agnostic Lasso Bandit
• Adaptive Rate of Convergence of Thompson Sampling for Gaussian Process Optimization
• Multi-facet Contextual Bandits: A Neural Network Perspective
• Nonparametric Contextual Bandits in an Unknown Metric Space
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
• Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• Scalable Thompson Sampling using Sparse Gaussian Process Models
• Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks
• Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems
• Efficient Online Bayesian Inference for Neural Bandits
• Doubly robust Thompson sampling for linear payoffs
• Non-Stationary Latent Bandits
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits
• Balanced Linear Contextual Bandits
• Thompson Sampling with a Mixture Prior
• Reinforcement Mechanism Design for e-commerce
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Hierarchical Bayesian Bandits
• Deep Bayesian Bandits: Exploring in Online Personalized Recommendations
• Max-Utility Based Arm Selection Strategy For Sequential Query Recommendations
• Tractable contextual bandits beyond realizability
• Multinomial Logit Bandit with Linear Utility Functions
• Exploration vs. Exploitation in the Information Filtering Problem
• Old Dog Learns New Tricks: Randomized UCB for Bandit Problems
• Information Directed Sampling for Sparse Linear Bandits
• Contextual Bandits with Side-Observations
• Learning to Route Efficiently with End-to-End Feedback: The Value of Networked Structure
• Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning
• Online Preselection with Context Information under the Plackett-Luce Model
• Online Learning and Decision-Making under Generalized Linear Model with High-Dimensional Data
• Partially Observable Online Change Detection via Smooth-Sparse Decomposition
• Personalized Advertisement Recommendation: A Ranking Approach to Address the Ubiquitous Click Sparsity Problem
• Reward-Biased Maximum Likelihood Estimation for Linear Stochastic Bandits
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
• TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits
• Linear Bandit Algorithms with Sublinear Time Complexity
• Randomized Exploration for Non-Stationary Stochastic Linear Bandits
• Show Me the Whole World: Towards Entire Item Space Exploration for Interactive Personalized Recommendations
• Global Bandits with Holder Continuity
• Online Limited Memory Neural-Linear Bandits with Likelihood Matching
• Thompson Sampling for Noncompliant Bandits
• A Hybrid Bandit Model with Visual Priors for Creative Ranking in Display Advertising
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization
• Incentivizing Exploration in Linear Bandits under Information Gap
• Bandits Under The Influence (Extended Version)
• Inverse Contextual Bandits: Learning How Behavior Evolves over Time
• Counterfactual Contextual Multi-Armed Bandit: a Real-World Application to Diagnose Apple Diseases
• An Active Learning Framework for Efficient Robust Policy Search
• An Arm-Wise Randomization Approach to Combinatorial Linear Semi-Bandits
• Constrained Contextual Bandit Learning for Adaptive Radar Waveform Selection
• Robust Generalization of Quadratic Neural Networks via Function Identification
• Distribution-free Contextual Dynamic Pricing
• Efficient Optimal Selection for Composited Advertising Creatives with Tree Structure
• Contextual-Bandit Based Personalized Recommendation with Time-Varying User Interests
• BanditMF: Multi-Armed Bandit Based Matrix Factorization Recommender System
• Thompson Sampling Algorithms for Cascading Bandits
• Action Centered Contextual Bandits
• Self-Supervised Contextual Bandits in Computer Vision
• When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution
• Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms
• Joint Online Learning and Decision-making via Dual Mirror Descent
• Lipschitz Bandit Optimization with Improved Efficiency
• Maximum entropy exploration in contextual bandits with neural networks and energy based models
• A Novel Confidence-Based Algorithm for Structured Bandits
• Approximation Theory Based Methods for RKHS Bandits
• Doubly Robust Interval Estimation for Optimal Policy Evaluation in Online Learning
• Metric-Free Individual Fairness with Cooperative Contextual Bandits
• Confidence-Budget Matching for Sequential Budgeted Learning
• Efficient Multivariate Bandit Algorithm with Path Planning
• Combining Online Learning and Offline Learning for Contextual Bandits with Deficient Support
• Freshness-Aware Thompson Sampling
• Solving Multi-Arm Bandit Using a Few Bits of Communication
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
• Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits
• High-dimensional near-optimal experiment design for drug discovery via Bayesian sparse sampling
• Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification
• Online Semi-Supervised Learning in Contextual Bandits with Episodic Reward
• The Adaptive Doubly Robust Estimator for Policy Evaluation in Adaptive Experiments and a Paradox Concerning Logging Policy
• Recurrent Neural-Linear Posterior Sampling for Nonstationary Contextual Bandits
• The Use of Bandit Algorithms in Intelligent Interactive Recommender Systems
• A Map of Bandits for E-commerce
• Thompson Sampling via Local Uncertainty
• Can A User Anticipate What Her Followers Want?
• Sequential Estimation under Multiple Resources: a Bandit Point of View
• Learning Orthogonal Projections in Linear Bandits
• Etat de l'art sur l'application des bandits multi-bras
• You Only Compress Once: Optimal Data Compression for Estimating Linear Models
• Robust Bandit Learning with Imperfect Context
• New Heuristics for Parallel and Scalable Bayesian Optimization
• A Smoothed Analysis of Online Lasso for the Sparse Linear Contextual Bandit Problem
• Automatic Ensemble Learning for Online Influence Maximization
• CBA: Contextual Quality Adaptation for Adaptive Bitrate Video Streaming (Extended Version)
• TSEB: More Efficient Thompson Sampling for Policy Learning
• Parallel Contextual Bandits in Wireless Handover Optimization
• Random Forest for the Contextual Bandit Problem - extended version
• Metalearning Linear Bandits by Prior Update