Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors

Abstract

In stochastic bandit problems, a Bayesian policy called Thompson sampling (TS) has recently attracted much attention for its excellent empirical performance. However, the theoretical analysis of this policy is difficult and its asymptotic optimality is only proved for one-parameter models. In this paper we discuss the optimality of TS for the model of normal distributions with unknown means and variances as one of the most fundamental example of multiparameter models. First we prove that the expected regret of TS with the uniform prior achieves the theoretical bound, which is the first result to show that the asymptotic bound is achievable for the normal distribution model. Next we prove that TS with Jeffreys prior and reference prior cannot achieve the theoretical bound. Therefore the choice of priors is important for TS and non-informative priors are sometimes risky in cases of multiparameter models.

References in corpus (1)

• Further Optimal Regret Bounds for Thompson Sampling

Cited by in corpus (17)

• A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit
• A Tutorial on Thompson Sampling
• Meta Dynamic Pricing: Transfer Learning Across Experiments
• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• Multi-Agent Thompson Sampling for Bandit Applications with Sparse Neighbourhood Structures
• Cuttlefish: A Lightweight Primitive for Adaptive Query Processing
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime
• Asymptotic Behavior of Minimal-Exploration Allocation Policies: Almost Sure, Arbitrarily Slow Growing Regret
• On the Prior Sensitivity of Thompson Sampling
• Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning
• Thompson Sampling for Noncompliant Bandits
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
• A Note on KL-UCB+ Policy for the Stochastic Bandit
• Metalearning Linear Bandits by Prior Update
• Memory Bounded Open-Loop Planning in Large POMDPs using Thompson Sampling
• Asymptotically Optimal Bandits under Weighted Information