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.
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.
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