Analysis of Thompson Sampling for the multi-armed bandit problem

Abstract

The multi-armed bandit problem is a popular model for studying exploration/exploitation trade-off in sequential decision problems. Many algorithms are now available for this well-studied problem. One of the earliest algorithms, given by W. R. Thompson, dates back to 1933. This algorithm, referred to as Thompson Sampling, is a natural Bayesian algorithm. The basic idea is to choose an arm to play according to its probability of being the best arm. Thompson Sampling algorithm has experimentally been shown to be close to optimal. In addition, it is efficient to implement and exhibits several desirable properties such as small regret for delayed feedback. However, theoretical understanding of this algorithm was quite limited. In this paper, for the first time, we show that Thompson Sampling algorithm achieves logarithmic expected regret for the multi-armed bandit problem. More precisely, for the two-armed bandit problem, the expected regret in time $T$ is $O(\frac{\ln T}{\Delta }+\frac{1}{{\Delta }^3})$. And, for the $N$-armed bandit problem, the expected regret in time $T$ is $O([({\sum }_{i=2}^N\frac{1}{{\Delta }_i^2}{)}^2]\ln T)$. Our bounds are optimal but for the dependence on ${\Delta }_i$ and the constant factors in big-Oh.

This version corrects some minor errors, and reorganizes some content

References in corpus (1)

• A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences

Cited by in corpus (209)

• Weight Uncertainty in Neural Networks
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Further Optimal Regret Bounds for Thompson Sampling
• Online Learning: A Comprehensive Survey
• Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
• Online Influence Maximization (Extended Version)
• An Efficient Bandit Algorithm for Realtime Multivariate Optimization
• Spectrum Access In Cognitive Radio Using A Two Stage Reinforcement Learning Approach
• Bayesian Optimization for Likelihood-Free Inference of Simulator-Based Statistical Models
• Bounded Regret for Finite-Armed Structured Bandits
• Cascading Bandits for Large-Scale Recommendation Problems
• Thompson Sampling for 1-Dimensional Exponential Family Bandits
• An Information-Theoretic Analysis of Thompson Sampling
• Combinatorial Cascading Bandits
• What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
• Taming Non-stationary Bandits: A Bayesian Approach
• Mid-Level Visual Representations Improve Generalization and Sample Efficiency for Learning Visuomotor Policies
• Efficient Learning in Large-Scale Combinatorial Semi-Bandits
• Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem
• Thompson Sampling for Combinatorial Semi-Bandits
• Effective Diversity in Population Based Reinforcement Learning
• Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
• Differentially-Private Federated Linear Bandits
• A Tutorial on Thompson Sampling
• Thompson Sampling: An Asymptotically Optimal Finite Time Analysis
• Online Hyperparameter Optimization for Class-Incremental Learning
• Bayesian policy gradient and actor-critic algorithms
• Thompson Sampling for Budgeted Multi-armed Bandits
• Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem
• Adaptive Grey-Box Fuzz-Testing with Thompson Sampling
• Optimally Confident UCB: Improved Regret for Finite-Armed Bandits
• Multi-Armed Bandits with Local Differential Privacy
• Bandit-Based Model Selection for Deformable Object Manipulation
• On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials
• Exploration in Interactive Personalized Music Recommendation: A Reinforcement Learning Approach
• Thompson Sampling for Learning Parameterized Markov Decision Processes
• On Kernelized Multi-armed Bandits
• Nonparametric Pricing Analytics with Customer Covariates
• Job Dispatching Policies for Queueing Systems with Unknown Service Rates
• Achieving Fairness in the Stochastic Multi-armed Bandit Problem
• Unified Models of Human Behavioral Agents in Bandits, Contextual Bandits and RL
• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• Cover Tree Bayesian Reinforcement Learning
• Multi-Agent Thompson Sampling for Bandit Applications with Sparse Neighbourhood Structures
• Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs
• Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits
• Generalized Thompson Sampling for Contextual Bandits
• A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem
• Federated Linear Contextual Bandits
• Simple Regret Minimization for Contextual Bandits
• Variational inference for the multi-armed contextual bandit
• Thompson Sampling Algorithms for Mean-Variance Bandits
• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
• Hedging using reinforcement learning: Contextual $k$-Armed Bandit versus $Q$-learning
• A sequential Monte Carlo approach to Thompson sampling for Bayesian optimization
• Learning to Optimize Via Posterior Sampling
• Correlated Multiarmed Bandit Problem: Bayesian Algorithms and Regret Analysis
• Online learning with Corrupted context: Corrupted Contextual Bandits
• QuickMMCTest - Quick Multiple Monte Carlo Testing
• The Finite-Horizon Two-Armed Bandit Problem with Binary Responses: A Multidisciplinary Survey of the History, State of the Art, and Myths
• Thompson Sampling for Complex Bandit Problems
• Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
• An ADMM Based Framework for AutoML Pipeline Configuration
• The Pareto Regret Frontier for Bandits
• Bayesian decision-making under misspecified priors with applications to meta-learning
• Cuttlefish: A Lightweight Primitive for Adaptive Query Processing
• Generating Music using an LSTM Network
• Adaptive Monte Carlo via Bandit Allocation
• Restless Bandits with Many Arms: Beating the Central Limit Theorem
• Multi-Armed Bandit Strategies for Non-Stationary Reward Distributions and Delayed Feedback Processes
• Logarithmic regret bounds for Bandits with Knapsacks
• contextual: Evaluating Contextual Multi-Armed Bandit Problems in R
• An Analysis of the Value of Information when Exploring Stochastic, Discrete Multi-Armed Bandits
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling
• MOTS: Minimax Optimal Thompson Sampling
• Guaranteed satisficing and finite regret: Analysis of a cognitive satisficing value function
• Online Learning of Energy Consumption for Navigation of Electric Vehicles
• Combinatorial Pure Exploration of Dueling Bandit
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime
• Kernel Methods for Cooperative Multi-Agent Contextual Bandits
• Empirical Bayes Regret Minimization
• Corralling a Band of Bandit Algorithms
• Getting too personal(ized): The importance of feature choice in online adaptive algorithms
• Learning to Act Greedily: Polymatroid Semi-Bandits
• Bandit Algorithms for Precision Medicine
• Learning the distribution with largest mean: two bandit frameworks
• Bayesian bandits: balancing the exploration-exploitation tradeoff via double sampling
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms
• Sequential Monte Carlo Bandits
• Causal Bandits with Unknown Graph Structure
• Regret Analysis of Bandit Problems with Causal Background Knowledge
• On Thompson Sampling with Langevin Algorithms
• Meta-Learning Bandit Policies by Gradient Ascent
• Inference Trees: Adaptive Inference with Exploration
• On the Prior Sensitivity of Thompson Sampling
• Differentiable Bandit Exploration
• Parallelizing Thompson Sampling
• Diversifying Database Activity Monitoring with Bandits
• A Survey of Exploration Methods in Reinforcement Learning
• Hyper-parameter Tuning for the Contextual Bandit
• Group Fairness in Bandit Arm Selection
• Risk-Constrained Thompson Sampling for CVaR Bandits
• Cooperative Multi-Agent Bandits with Heavy Tails
• Combining Offline Causal Inference and Online Bandit Learning for Data Driven Decision
• Meta-Thompson Sampling
• Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewards
• A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits
• Racing Thompson: an Efficient Algorithm for Thompson Sampling with Non-conjugate Priors
• Rapidly Personalizing Mobile Health Treatment Policies with Limited Data
• The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms
• Bandit Models of Human Behavior: Reward Processing in Mental Disorders
• Adaptive Rate of Convergence of Thompson Sampling for Gaussian Process Optimization
• Randomized Value Functions via Posterior State-Abstraction Sampling
• Reinforcement Learning algorithms for regret minimization in structured Markov Decision Processes
• Thompson Sampling for a Fatigue-aware Online Recommendation System
• Balanced Linear Contextual Bandits
• Stochastic Linear Contextual Bandits with Diverse Contexts
• On Thompson Sampling for Smoother-than-Lipschitz Bandits
• Regret Minimization in Heavy-Tailed Bandits
• Hierarchical Bayesian Bandits
• Thompson Sampling with a Mixture Prior
• Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning
• Explore-Exploit: A Framework for Interactive and Online Learning
• On Exploration, Exploitation and Learning in Adaptive Importance Sampling
• Infinite Arms Bandit: Optimality via Confidence Bounds
• Multinomial Logit Bandit with Linear Utility Functions
• Contextual Bandits with Stochastic Experts
• Better Optimism By Bayes: Adaptive Planning with Rich Models
• Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits
• Thompson sampling for linear quadratic mean-field teams
• Exploration Through Reward Biasing: Reward-Biased Maximum Likelihood Estimation for Stochastic Multi-Armed Bandits
• Thompson Sampling for Noncompliant Bandits
• Be Greedy in Multi-Armed Bandits
• On conditional versus marginal bias in multi-armed bandits
• Accelerated learning from recommender systems using multi-armed bandit
• Regret bounds for Narendra-Shapiro bandit algorithms
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits
• TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation
• Matching while Learning
• Contextual Bandit with Adaptive Feature Extraction
• Global Bandits with Holder Continuity
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
• Maximum a Posteriori Estimation by Search in Probabilistic Programs
• Partially Observable Online Change Detection via Smooth-Sparse Decomposition
• Regret Bounds for Gaussian-Process Optimization in Large Domains
• (Almost) Free Incentivized Exploration from Decentralized Learning Agents
• Ballooning Multi-Armed Bandits
• Regret Minimization in Stochastic Contextual Dueling Bandits
• On Limited-Memory Subsampling Strategies for Bandits
• Combinatorial Pure Exploration with Bottleneck Reward Function
• Smooth Sequential Optimisation with Delayed Feedback
• Multi-Armed Bandits on Partially Revealed Unit Interval Graphs
• Continuous Mean-Covariance Bandits
• Value Directed Exploration in Multi-Armed Bandits with Structured Priors
• Confidence-Budget Matching for Sequential Budgeted Learning
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
• Continuous-Time Birth-Death MCMC for Bayesian Regression Tree Models
• Thompson Sampling Algorithms for Cascading Bandits
• State-Aware Variational Thompson Sampling for Deep Q-Networks
• Compliance-Aware Bandits
• Convolutional Monte Carlo Rollouts in Go
• Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms
• No Regrets for Learning the Prior in Bandits
• Rate-optimal Bayesian Simple Regret in Best Arm Identification
• Solving Multi-Arm Bandit Using a Few Bits of Communication
• Contextual-Bandit Based Personalized Recommendation with Time-Varying User Interests
• Deciding What to Learn: A Rate-Distortion Approach
• The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks
• Shrinking the Upper Confidence Bound: A Dynamic Product Selection Problem for Urban Warehouses
• Lipschitz Bandit Optimization with Improved Efficiency
• Efficient Inference Without Trading-off Regret in Bandits: An Allocation Probability Test for Thompson Sampling
• Adaptive Pricing in Insurance: Generalized Linear Models and Gaussian Process Regression Approaches
• Dueling Bandits with Adversarial Sleeping
• Exploring Offline Policy Evaluation for the Continuous-Armed Bandit Problem
• Variable Selection via Thompson Sampling
• Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
• Scalable K-Medoids via True Error Bound and Familywise Bandits
• DART: aDaptive Accept RejecT for non-linear top-K subset identification
• Distributed Thompson Sampling
• Stochastic Multi-Armed Bandits with Control Variates
• An Optimal Bayesian Network Based Solution Scheme for the Constrained Stochastic On-line Equi-Partitioning Problem
• Random Effect Bandits
• Thompson Sampling Guided Stochastic Searching on the Line for Deceptive Environments with Applications to Root-Finding Problems
• Deep Upper Confidence Bound Algorithm for Contextual Bandit Ranking of Information Selection
• Scenario Approach for Robust Blackbox Optimization in the Bandit Setting
• Meeting of Mobile Nodes Based on RSS Measurements in Wireless Ad Hoc Networks
• Asymptotically Optimal Bandits under Weighted Information
• Sleeping Combinatorial Bandits
• Enhancing Evolutionary Conversion Rate Optimization via Multi-armed Bandit Algorithms
• Thompson Sampling via Local Uncertainty
• Batched Thompson Sampling for Multi-Armed Bandits
• Vaccine allocation policy optimization and budget sharing mechanism using Thompson sampling
• Adaptive Combinatorial Allocation
• A Dominant Strategy Truthful, Deterministic Multi-Armed Bandit Mechanism with Logarithmic Regret
• Streaming Algorithms for Stochastic Multi-armed Bandits
• Etat de l'art sur l'application des bandits multi-bras
• Robust Bandit Learning with Imperfect Context
• TSEB: More Efficient Thompson Sampling for Policy Learning
• Thompson Sampling for Unsupervised Sequential Selection
• Automatic Ensemble Learning for Online Influence Maximization
• Better Boosting with Bandits for Online Learning
• Odds-Ratio Thompson Sampling to Control for Time-Varying Effect
• Reinforcement Learning for Optimal Load Distribution Sequencing in Resource-Sharing System
• GNU Radio Implementation of MALIN: "Multi-Armed bandits Learning for Internet-of-things Networks"
• Simple Algorithms for Dueling Bandits
• Near-optimal Bayesian Solution For Unknown Discrete Markov Decision Process
• Parameterized Indexed Value Function for Efficient Exploration in Reinforcement Learning
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards