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

Jongyeong Lee, Chao-Kai Chiang, Masashi Sugiyama

Abstract

Thompson Sampling (TS) is a cornerstone of reinforcement learning, yet its optimality in multiparameter models is highly sensitive to the choice of noninformative priors. This research identifies a fundamental fragility: standard TS can fail to achieve asymptotic optimality depending on how a model is parameterized. We propose Thompson Sampling with Truncation (TS-T), an adaptive modification that ensures exploration by "stretching" the posterior distribution. Our theoretical and empirical results demonstrate that TS-T achieves asymptotic optimality for Gaussian and uniform reward models using robust, invariant priors.

Introduction

In the Multi-Armed Bandit (MAB) framework, agents must balance exploration and exploitation to maximize cumulative rewards. Thompson Sampling addresses this by sampling from a Bayesian posterior. While well-understood for single-parameter models, multiparameter settings—where both mean and scale are unknown—introduce significant complexities. Specifically, the choice of "noninformative" priors becomes critical, as common choices like uniform priors are not invariant to reparameterization, potentially leading to suboptimal regret.

The Challenge of Multiparameter Models

A key issue identified is the lack of consistency in uniform priors. If a model is reparameterized (e.g., switching from "scale" to "rate"), a prior that was uniform in one system becomes non-uniform in the other. This inconsistency can cause the posterior of the optimal arm to shrink prematurely around a suboptimal value, leading the algorithm to cease exploration too early. This "parameterization trap" means that the perceived optimality of TS is often an artifact of specific mathematical framing rather than a robust property of the algorithm.

Thompson Sampling with Truncation (TS-T)

To address this, the authors introduce TS-T. The core innovation is an adaptive truncation of the scale parameter's Maximum Likelihood Estimator (MLE) during early rounds. This truncation effectively "stretches" the posterior distribution, preventing overconfidence and ensuring sufficient exploration until the agent has gathered enough data to be certain.

Comparison of the standard posterior distribution versus the 'stretched' posterior used in TS-T to ensure exploration.

By flattening the posterior, TS-T allows for the use of invariant priors, such as Jeffreys or reference priors, which are mathematically consistent across different parameterizations. This approach provides a "bronze bullet"—a policy that works consistently across different ways of modeling the same data, relieving practitioners of the need to hunt for the perfect prior.

Empirical Evaluation

The proposed method was evaluated on a 6-armed uniform bandit benchmark, a standard setup in bandit literature. The policies were tested over 10,000 independent runs to measure cumulative regret over 50,000 rounds. The simulations show that while vanilla TS with a reference prior can exhibit high regret, the TS-T modification successfully recovers optimal performance, matching the theoretical lower bound.

Regret performance of TS-T compared to standard benchmarks and the theoretical lower bound.

Conclusion

TS-T provides a robust framework for applying Thompson Sampling to multiparameter models. By decoupling optimality from specific parameterizations through adaptive truncation, the authors enable the use of invariant priors that practitioners can rely on without extensive manual tuning. While the current work focuses on Gaussian and uniform models, future research will explore extensions to heavy-tailed distributions and the challenge of achieving minimax optimality in these complex settings.

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