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: The Prior Sensitivity Problem
In Multi-Armed Bandit (MAB) problems, Thompson Sampling (TS) is a cornerstone algorithm for balancing exploration and exploitation. While TS is robust in simple single-parameter models (like the Bernoulli distribution), its performance becomes highly sensitive to the choice of "noninformative" priors in multiparameter models, such as Gaussian or Uniform distributions where both mean and scale are unknown.
A significant issue identified in this research is the lack of invariance in common priors. For instance, a uniform prior that is optimal for a model parameterized by $(\mu, \sigma)$ may become suboptimal if the model is reparameterized using the rate $(\mu, 1/\sigma)$. This "prior hunting" makes it difficult to deploy TS reliably in complex, real-world scenarios without extensive theoretical tuning.
The "Bad Optimal" Problem and the Truncation Solution
The primary failure mode for TS in these models is the "Bad Optimal" (BO) scenario. This occurs when the posterior distribution of the optimal arm prematurely concentrates around a value lower than its true mean due to early random noise. Because the distribution is too "tight," the algorithm stops exploring the arm, leading to massive cumulative regret.
To resolve this, the authors propose Thompson Sampling with Truncation (TS-T). The core mechanism is an adaptive truncation procedure applied to the scale parameter. By truncating the scale estimator, the algorithm effectively "stretches" the posterior distribution during the early stages of learning.
As shown in the figure above, this stretching prevents the algorithm from becoming too certain too soon, encouraging sufficient exploration to overcome the BO problem without sacrificing long-term performance.
Theoretical Framework and Results
The researchers extended regret analysis to the Uniform model with unknown supports and demonstrated that TS-T achieves the asymptotic regret lower bound for both Uniform and Gaussian models. Crucially, TS-T allows the use of mathematically elegant, invariant priors—such as the Jeffreys prior or Reference prior—which typically cause vanilla TS to fail.
As summarized in the table, vanilla TS (O-T) frequently fails to reach optimality (indicated by crosses) when paired with standard invariant priors. In contrast, the TS-T policy (O-TT) consistently achieves asymptotic optimality across various parameterizations. Empirical simulations with 10,000 independent runs confirmed these findings, showing that TS-T remains stable and matches the performance of specialized, model-specific algorithms like CHK-UCB.
Conclusion
TS-T offers a robust "bronze bullet" for multiparameter bandit problems. By introducing a simple truncation step, researchers can utilize invariant priors that remain consistent across different model parameterizations, eliminating the need for manual prior tuning. Future work will look toward establishing minimax optimality and extending this truncation principle to the broader exponential family of reward distributions.
Summary updated