The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models

Jongyeong Lee, Chao-Kai Chiang, Masashi Sugiyama

Abstract

Thompson sampling (TS) has been known for its outstanding empirical performance supported by theoretical guarantees across various reward models in the classical stochastic multi-armed bandit problems. Nonetheless, its optimality is often restricted to specific priors due to the common observation that TS is fairly insensitive to the choice of the prior when it comes to asymptotic regret bounds. However, when the model contains multiple parameters, the optimality of TS highly depends on the choice of priors, which casts doubt on the generalizability of previous findings to other models. To address this gap, this study explores the impact of selecting noninformative priors, offering insights into the performance of TS when dealing with new models that lack theoretical understanding. We first extend the regret analysis of TS to the model of uniform distributions with unknown supports, which would be the simplest non-regular model. Our findings reveal that changing noninformative priors can significantly affect the expected regret, aligning with previously known results in other multiparameter bandit models. Although the uniform prior is shown to be optimal, we highlight the inherent limitation of its optimality, which is limited to specific parameterizations and emphasizes the significance of the invariance property of priors. In light of this limitation, we propose a slightly modified TS-based policy, called TS with Truncation (TS-T), which can achieve the asymptotic optimality for the Gaussian models and the uniform models by using the reference prior and the Jeffreys prior that are invariant under one-to-one reparameterizations. This policy provides an alternative approach to achieving optimality by employing fine-tuned truncation, which would be much easier than hunting for optimal priors in practice.

Introduction

In the Multi-Armed Bandit (MAB) framework, Thompson Sampling (TS) is a cornerstone algorithm that balances exploration and exploitation by sampling from a posterior distribution. While its robustness is well-documented for single-parameter models like Bernoulli trials, its behavior in multiparameter settings—where rewards follow distributions like Gaussian or Uniform—is significantly more complex.

This paper investigates how the choice of "noninformative" priors affects the asymptotic regret of TS in these multiparameter models. We demonstrate that standard TS is highly sensitive to the prior choice and often fails to achieve theoretical lower bounds unless a specific, non-invariant prior is used. To resolve this, we introduce Thompson Sampling with Truncation (TS-T), a modified policy that ensures optimal exploration using invariant priors.

The Sensitivity of Thompson Sampling

A critical issue in multiparameter bandits is the lack of invariance in common priors. For instance, a uniform prior might be optimal for one parameterization (e.g., mean and scale) but suboptimal for another (e.g., mean and rate). This "reparameterization trap" makes it difficult for practitioners to choose a prior that guarantees performance across different mathematical descriptions of the same model.

Furthermore, vanilla TS can suffer from "narrow" posteriors early in the learning process. If the algorithm underestimates the variance of the optimal arm, it may stop exploring it prematurely, leading to high cumulative regret.

Proposed Method: Thompson Sampling with Truncation (TS-T)

To address these limitations, we propose TS-T. This policy combines two key elements:

  1. Invariant Priors: We utilize the Jeffreys prior or Reference prior, which remain consistent regardless of reparameterization.
  2. Adaptive Truncation (Stretching): TS-T employs a truncated version of the Maximum Likelihood Estimator (MLE) for the scale parameter. This effectively "stretches" the posterior distribution during the early stages of learning, forcing the algorithm to maintain adequate exploration even when data is scarce.
Figure 1: Comparison of standard posterior distributions (a) versus 'stretched' posteriors (b) in the TS-T algorithm, which prevents premature convergence.

As shown in the figure above, the stretching technique ensures that the sampled mean values for sub-optimal arms (like Arm 1) have a higher probability of exceeding the expected value of the currently perceived best arm, thereby sustaining exploration.

Theoretical Contributions and Results

Our research provides the first regret analysis for TS in uniform models with unknown supports. We prove that while vanilla TS with invariant priors is often suboptimal, TS-T successfully achieves the asymptotic regret lower bound for both Gaussian and Uniform models.

Table 1: Summary of asymptotic optimality for various models and priors. O-T refers to standard Thompson Sampling, while O-TT refers to the proposed TS-T policy.

The table above summarizes our findings. While standard TS (O-T) fails (marked with 'X') for many invariant priors like the Jeffreys prior ($\pi_j$) or Reference prior ($\pi_r$), our TS-T policy (O-TT) achieves optimality (marked with checkmarks) across these settings. Notably, for Pareto models, TS-T shows significant promise, though some theoretical gaps remain.

Conclusion

Choosing the right prior for Thompson Sampling in complex models is not trivial. By introducing TS-T, we provide a more robust, "site-ready" alternative to vanilla TS. By utilizing invariant priors and a simple truncation mechanism, TS-T avoids the pitfalls of reparameterization and ensures asymptotic optimality, making it a reliable baseline for practitioners dealing with multiparameter reward distributions.

Summary updated

Abstract

Thompson sampling (TS) has been known for its outstanding empirical performance supported by theoretical guarantees across various reward models in the classical stochastic multi-armed bandit problems. Nonetheless, its optimality is often restricted to specific priors due to the common observation that TS is fairly insensitive to the choice of the prior when it comes to asymptotic regret bounds. However, when the model contains multiple parameters, the optimality of TS highly depends on the choice of priors, which casts doubt on the generalizability of previous findings to other models. To address this gap, this study explores the impact of selecting noninformative priors, offering insights into the performance of TS when dealing with new models that lack theoretical understanding. We first extend the regret analysis of TS to the model of uniform distributions with unknown supports, which would be the simplest non-regular model. Our findings reveal that changing noninformative priors can significantly affect the expected regret, aligning with previously known results in other multiparameter bandit models. Although the uniform prior is shown to be optimal, we highlight the inherent limitation of its optimality, which is limited to specific parameterizations and emphasizes the significance of the invariance property of priors. In light of this limitation, we propose a slightly modified TS-based policy, called TS with Truncation (TS-T), which can achieve the asymptotic optimality for the Gaussian models and the uniform models by using the reference prior and the Jeffreys prior that are invariant under one-to-one reparameterizations. This policy provides an alternative approach to achieving optimality by employing fine-tuned truncation, which would be much easier than hunting for optimal priors in practice.
BibTeX
@inproceedings{lee2024choice,
  author = {Jongyeong Lee and Chao-Kai Chiang and Masashi Sugiyama},
  title = {{The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i12.29240},
}
Figure