Further Optimal Regret Bounds for Thompson Sampling

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. In this paper, we provide a novel regret analysis for Thompson Sampling that simultaneously proves both the optimal problem-dependent bound of $(1+\epsilon ){\sum }_i\frac{\ln T}{{\Delta }_i}+O(\frac{N}{{\epsilon }^2})$ and the first near-optimal problem-independent bound of $O(\sqrt{NT\ln T})$ on the expected regret of this algorithm. Our near-optimal problem-independent bound solves a COLT 2012 open problem of Chapelle and Li. The optimal problem-dependent regret bound for this problem was first proven recently by Kaufmann et al. [ALT 2012]. Our novel martingale-based analysis techniques are conceptually simple, easily extend to distributions other than the Beta distribution, and also extend to the more general contextual bandits setting [Manuscript, Agrawal and Goyal, 2012].

arXiv admin note: substantial text overlap with arXiv:1111.1797

References in corpus (3)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences

Cited by in corpus (118)

• Weight Uncertainty in Neural Networks
• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Bayesian Reinforcement Learning: A Survey
• Bao: Learning to Steer Query Optimizers
• A Survey on Contextual Multi-armed Bandits
• Bounded Regret for Finite-Armed Structured Bandits
• Generalization and Exploration via Randomized Value Functions
• Thompson Sampling for 1-Dimensional Exponential Family Bandits
• Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
• Bootstrapped Thompson Sampling and Deep Exploration
• Meta reinforcement learning as task inference
• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
• An Information-Theoretic Analysis of Thompson Sampling
• Test & Roll: Profit-Maximizing A/B Tests
• Potential and Pitfalls of Multi-Armed Bandits for Decentralized Spatial Reuse in WLANs
• RecSim: A Configurable Simulation Platform for Recommender Systems
• Taming Non-stationary Bandits: A Bayesian Approach
• Thompson Sampling for Combinatorial Semi-Bandits
• Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
• Differentially-Private Federated Linear Bandits
• A Tutorial on Thompson Sampling
• Bayesian policy gradient and actor-critic algorithms
• Thompson Sampling for Budgeted Multi-armed Bandits
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits
• Optimally Confident UCB: Improved Regret for Finite-Armed Bandits
• On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials
• Bootstrapping Upper Confidence Bound
• Preference-based Online Learning with Dueling Bandits: A Survey
• Thompson Sampling for the MNL-Bandit
• Concurrent Decentralized Channel Allocation and Access Point Selection using Multi-Armed Bandits in multi BSS WLANs
• Multi-Agent Thompson Sampling for Bandit Applications with Sparse Neighbourhood Structures
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• Generalized Thompson Sampling for Contextual Bandits
• Multi-Agent Multi-Armed Bandits with Limited Communication
• Federated Linear Contextual Bandits
• Optimal No-regret Learning in Repeated First-price Auctions
• Variational inference for the multi-armed contextual bandit
• Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
• On the Complexity of A/B Testing
• Learning to Optimize Via Posterior Sampling
• Randomized Exploration in Generalized Linear Bandits
• Exploratory Grasping: Asymptotically Optimal Algorithms for Grasping Challenging Polyhedral Objects
• New Insights into Bootstrapping for Bandits
• The Pareto Regret Frontier for Bandits
• Cuttlefish: A Lightweight Primitive for Adaptive Query Processing
• Thompson Sampling with Approximate Inference
• Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling
• Optimal Best-Arm Identification Methods for Tail-Risk Measures
• Long-Term Visitation Value for Deep Exploration in Sparse Reward Reinforcement Learning
• Optimal Thompson Sampling strategies for support-aware CVaR bandits
• MOTS: Minimax Optimal Thompson Sampling
• Empirical Bayes Regret Minimization
• Stochastic Bandits with Linear Constraints
• Perturbed-History Exploration in Stochastic Linear Bandits
• Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models
• Causal Bandits with Unknown Graph Structure
• Learning the distribution with largest mean: two bandit frameworks
• On Thompson Sampling with Langevin Algorithms
• Bandit Algorithms for Precision Medicine
• Residual Bootstrap Exploration for Bandit Algorithms
• On the Prior Sensitivity of Thompson Sampling
• Parallelizing Thompson Sampling
• Adaptive Rate of Convergence of Thompson Sampling for Gaussian Process Optimization
• A Bit Better? Quantifying Information for Bandit Learning
• Constrained Thompson Sampling for Wireless Link Optimization
• Stochastic Linear Contextual Bandits with Diverse Contexts
• Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits
• Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning
• Randomized Value Functions via Posterior State-Abstraction Sampling
• On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems
• Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards
• Learning Modular Safe Policies in the Bandit Setting with Application to Adaptive Clinical Trials
• Algorithms for slate bandits with non-separable reward functions
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
• TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation
• Lifelong Learning in Multi-Armed Bandits
• Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits
• Thompson Sampling with Information Relaxation Penalties
• Thompson Sampling for Noncompliant Bandits
• Bayesian Optimization for Categorical and Category-Specific Continuous Inputs
• Posterior sampling for reinforcement learning: worst-case regret bounds
• CORe: Capitalizing On Rewards in Bandit Exploration
• Fundamental Limits of Online Network-Caching
• Deciding What to Learn: A Rate-Distortion Approach
• An Arm-Wise Randomization Approach to Combinatorial Linear Semi-Bandits
• Solving Multi-Arm Bandit Using a Few Bits of Communication
• Multi-armed Bandit Requiring Monotone Arm Sequences
• On Limited-Memory Subsampling Strategies for Bandits
• Efficient Inference Without Trading-off Regret in Bandits: An Allocation Probability Test for Thompson Sampling
• Thompson Sampling Algorithms for Cascading Bandits
• Aging Bandits: Regret Analysis and Order-Optimal Learning Algorithm for Wireless Networks with Stochastic Arrivals
• State-Aware Variational Thompson Sampling for Deep Q-Networks
• Multi-Armed Bandits on Partially Revealed Unit Interval Graphs
• Incentivized Exploration for Multi-Armed Bandits under Reward Drift
• Mining Hidden Populations through Attributed Search
• Adaptive Pricing in Insurance: Generalized Linear Models and Gaussian Process Regression Approaches
• Sequential Matrix Completion
• Asymptotically Optimal Bandits under Weighted Information
• Distributed Thompson Sampling
• Blind Exploration and Exploitation of Stochastic Experts
• Maillard Sampling: Boltzmann Exploration Done Optimally
• Thompson Sampling for Linearly Constrained Bandits
• Thompson Sampling for Unsupervised Sequential Selection
• Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification
• Can A User Anticipate What Her Followers Want?
• Estimating Quality in Multi-Objective Bandits Optimization
• Simple Algorithms for Dueling Bandits
• Random Effect Bandits
• A Note on Information-Directed Sampling and Thompson Sampling
• The Value of Information When Deciding What to Learn
• Parallel Contextual Bandits in Wireless Handover Optimization
• Stochastic Multi-Armed Bandits with Control Variates
• New Heuristics for Parallel and Scalable Bayesian Optimization
• Towards Intelligent Reconfigurable Wireless Physical Layer (PHY)
• Memory Bounded Open-Loop Planning in Large POMDPs using Thompson Sampling
• Thompson Sampling for Unimodal Bandits
• Stochastic Bandits with Vector Losses: Minimizing ${\ell }^{\infty }$-Norm of Relative Losses