Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors

Junya Honda, Akimichi TakemuraAISTATS 2014 · OpenReview

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 algorithm in multi-parameter models has been limited. This paper investigates Gaussian bandits with unknown means and variances, revealing that the choice of prior distribution is critical for achieving asymptotic optimality. While conservative uniform priors achieve the theoretical lower bound, popular non-informative priors like the Jeffreys prior can lead to catastrophic polynomial regret.

Introduction

In the multi-armed bandit problem, an agent must balance exploration (trying new actions) and exploitation (sticking with the best-known action) to maximize cumulative rewards. The efficiency of an algorithm is typically measured by its "regret"—the difference between the reward from the optimal action and the reward actually obtained. For one-parameter models, Thompson Sampling (TS) is known to be asymptotically optimal. However, real-world scenarios often involve Gaussian distributions where both the mean ($\mu$) and variance ($\sigma^2$) are unknown. This paper investigates whether TS can maintain its optimality in this two-parameter setting and how the choice of prior distribution influences performance.

Methodology

The authors analyze a Gaussian bandit model where each arm $i$ follows a distribution $N(\mu_i, \sigma_i^2)$. They evaluate a class of priors defined by the density: $$\pi(\mu_i, \sigma_i^2) \propto (\sigma_i^2)^{-1-\alpha}$$ This class encompasses several standard statistical priors based on the value of $\alpha$:

  • $\alpha = -1$ or $-1/2$: Uniform priors, which are relatively conservative.
  • $\alpha = 0$: The Reference prior.
  • $\alpha = 1/2$: The Jeffreys prior, a common "non-informative" choice in statistics.

The study employs mathematical proofs to derive regret bounds and uses synthetic simulations to validate these theoretical results. The simulation setup involves a two-armed bandit where Arm 1 is superior ($\mu_1=1, \sigma_1=3.0$) and Arm 2 is inferior ($\mu_2=0, \sigma_2=0.3$).

The Optimism Trap: Why Priors Matter

A key insight of the paper is the "optimism trap" inherent in certain priors. Non-informative priors like the Jeffreys prior ($\alpha = 1/2$) are excessively optimistic about the potential of suboptimal arms. They assign significant probability mass to the possibility that a poorly performing arm might have a very large variance, which could eventually yield high rewards. This tricks the algorithm into over-exploring bad arms, a behavior that persists even as data accumulates.

Unlike many Bayesian problems where the influence of the prior diminishes with more data, the bandit setting makes the prior's choice permanent and critical. A "bad" prior can fundamentally degrade the regret growth from logarithmic (efficient) to polynomial (inefficient).

Results and Empirical Validation

The theoretical analysis yields two primary findings:

  1. Optimality: For $\alpha < 0$ (e.g., uniform priors), Thompson Sampling is asymptotically optimal, matching the theoretical lower bound for regret as the number of rounds $T$ goes to infinity.
  2. Failure: For $\alpha \ge 0$ (e.g., Reference or Jeffreys priors), TS fails to reach the theoretical bound. Specifically, for the Jeffreys prior, regret grows at a polynomial rate $T^p$.
Regret of Thompson Sampling for different priors compared to the asymptotic bound.

As shown in Figure 1, the simulation results confirm these findings. The regret curve for the uniform prior ($\alpha = -1/2$) closely follows the asymptotic lower bound. In contrast, the curves for the Reference ($\alpha = 0$) and Jeffreys ($\alpha = 1/2$) priors diverge significantly, with the Jeffreys prior showing a sharp upward trajectory indicative of polynomial growth.

Conclusion

This research establishes that Thompson Sampling can be asymptotically optimal for Gaussian bandits with unknown variance, provided a conservative prior is used. It highlights a significant risk in using standard non-informative priors in reinforcement learning contexts. While the proofs are specific to Gaussian models, they suggest that similar sensitivities might exist in other multi-parameter distributions. Future work may explore these effects in other models and investigate performance within the "Probably Approximately Correct" (PAC) framework, where Jeffreys prior might still show utility despite its poor expected regret.

Summary updated

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 th...
BibTeX
@inproceedings{honda2014optimality,
  author = {Junya Honda and Akimichi Takemura},
  title = {{Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2014},
  url = {https://openreview.net/forum?id=Gc3PVC7Za0S},
}
Figure