Thompson Sampling for 1-Dimensional Exponential Family Bandits

Abstract

Thompson Sampling has been demonstrated in many complex bandit models, however the theoretical guarantees available for the parametric multi-armed bandit are still limited to the Bernoulli case. Here we extend them by proving asymptotic optimality of the algorithm using the Jeffreys prior for 1-dimensional exponential family bandits. Our proof builds on previous work, but also makes extensive use of closed forms for Kullback-Leibler divergence and Fisher information (and thus Jeffreys prior) available in an exponential family. This allow us to give a finite time exponential concentration inequality for posterior distributions on exponential families that may be of interest in its own right. Moreover our analysis covers some distributions for which no optimistic algorithm has yet been proposed, including heavy-tailed exponential families.

References in corpus (3)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Further Optimal Regret Bounds for Thompson Sampling

Cited by in corpus (29)

• Bounded Regret for Finite-Armed Structured Bandits
• Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
• Bootstrapping Upper Confidence Bound
• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• Variational inference for the multi-armed contextual bandit
• KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints
• Thompson Sampling for Complex Bandit Problems
• Cuttlefish: A Lightweight Primitive for Adaptive Query Processing
• Optimal Thompson Sampling strategies for support-aware CVaR bandits
• The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
• Double Explore-then-Commit: Asymptotic Optimality and Beyond
• Cooperative Multi-Agent Bandits with Heavy Tails
• No-Regret Reinforcement Learning with Heavy-Tailed Rewards
• Infinite Arms Bandit: Optimality via Confidence Bounds
• On Thompson Sampling for Smoother-than-Lipschitz Bandits
• The Fragility of Optimized Bandit Algorithms
• The Survival Bandit Problem
• Non-Stationary Delayed Bandits with Intermediate Observations
• Exploration Through Reward Biasing: Reward-Biased Maximum Likelihood Estimation for Stochastic Multi-Armed Bandits
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
• Optimality of Thompson Sampling with Noninformative Priors for Pareto Bandits
• Bregman Deviations of Generic Exponential Families
• Optimal UCB Adjustments for Large Arm Sizes
• Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits
• Note on Thompson sampling for large decision problems
• Better Boosting with Bandits for Online Learning
• Maillard Sampling: Boltzmann Exploration Done Optimally
• Automatic Ensemble Learning for Online Influence Maximization
• Stochastic Bandits with Vector Losses: Minimizing ${\ell }^{\infty }$-Norm of Relative Losses