Thompson sampling chooses an action by drawing one plausible model from the posterior and acting as if that draw were true. It is an elegant exploration rule—until the posterior becomes so concentrated that an optimistic draw is vanishingly unlikely in many dimensions.
Jaiswal, Pati, Bhattacharya, and Mallick explain a familiar theoretical fix as coherent Bayesian machinery. Raise every likelihood contribution to a power α below one. The posterior then learns more cautiously and keeps sampling unexplored possibilities. The paper's sharpest lesson is also its least plug-and-play one: α must shrink with dimension, and the proof only starts after a dimension-scale warm-up.
One exponent turns data into softer evidence
A fractional posterior replaces the usual likelihood L(θ) with L(θ)α. For Gaussian linear regression, this multiplies every observation's precision contribution by α. The same sufficient statistics are used; only their strength changes.
def fractional_gaussian_posterior(prior_mean, prior_precision, noise_variance, sum_x2, sum_xy, alpha):
scaled_precision = alpha / noise_variance
precision = prior_precision + scaled_precision * sum_x2
mean = (prior_precision * prior_mean + scaled_precision * sum_xy) / precision
variance = 1.0 / precision
return mean, varianceIn a weak-prior, large-sample regime, covariance is multiplied by 1/α and standard deviation by 1/√α. With d = 16, the recommended α is 0.0625: asymptotically 16× the covariance and 4× the posterior standard deviation.
Wider uncertainty means more optimistic draws
In a linear bandit, each action is a feature vector and expected reward is its dot product with an unknown coefficient vector. Regret is the reward lost by choosing something other than the oracle's best action. Thompson sampling explores only when its random coefficient draw makes an uncertain action look best.
Tempering does not make the observed mean better. It makes the learner less certain that the mean is settled. That distinction matters: variance inflation buys exploration, not evidence.
Dimension sets the temperature—and the tax
| Paper statement | Form | Interpretation |
|---|---|---|
| Tempered likelihood | L(θ)^α, 0 < α < 1 | Likelihood information is deliberately discounted |
| Posterior covariance | inflated by α⁻¹ | Posterior draws explore a wider parameter region |
| Dimension-aware choice | α = d⁻¹ | Keeps the optimism term from decaying exponentially in d |
| Upper bound | O(d³ᐟ² √T log T) | Matches the best known LinTS rate under stated conditions |
| Constructed lower bound | Ω(d³ᐟ² √T) | The extra √d is unavoidable for this algorithm class |
Why not temper even more? The contraction term scales roughly as d/α, so choosing α = d−(1+ε) widens the upper bound to O(d3/2+ε/2 √T log T). Why not temper less? Terms involving αd reintroduce exponential dimension dependence. The proof's balance point is therefore α = 1/d, not a free tuning suggestion.
| Proof condition | What it narrows |
|---|---|
| Warm-up | t₁ = Ω(d), sufficiently large for the approximation error |
| Action space | Compact subset of ℝᵈ; the analysis targets linear bandit geometry |
| Prior | Positive, continuous, bounded density; sub-Gaussian tails elsewhere |
| Exponential family | Variance bounded above and away from zero on the parameter domain |
| Sub-Gaussian family | Bounded noise plus additional smoothness of the error density |
| Not covered | Misspecification, non-stationarity, and infinite-dimensional models |
What a practical reproduction should probe
- Compare α = 1, 1/√d, and 1/d on the same seeded bandit instances, reporting early and late regret separately.
- Vary the number and design of warm-up actions instead of treating t₁ = Ω(d) as a sufficient recipe.
- Stress misspecified rewards and non-stationary coefficients, which the paper lists as open extensions.
- Measure posterior-sampling cost for nonconjugate generalized linear models; the theorem does not make those samples computationally cheap.
- Report simple regret and estimation quality as well as cumulative regret, because extra exploration can help one objective and hurt another.
The linear regression page gives the Gaussian update behind the exact core above, while logistic regression is the most familiar generalized-linear case. The durable insight is that posterior variance is part of the decision policy: cool the likelihood and the learner searches longer—but the right amount of cooling depends on geometry, not taste.
References
- Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya, Bani K. Mallick (2026). Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling. arXiv preprint
- Shipra Agrawal, Navin Goyal (2013). Thompson Sampling for Contextual Bandits with Linear Payoffs. Proceedings of ICML, PMLR 28