Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling

Thompson Sampling (TS) is a popular heuristic for balancing exploration and exploitation in bandit problems. While standard TS uses the exact Bayesian posterior, theoretical analyses often require inflating the posterior variance to achieve near-optimal regret bounds. This paper investigates whether this variance inflation can be formalized within a coherent statistical framework and how it affects the regret performance in generalized linear bandit problems.

The authors introduce alpha-TS, a variant of Thompson Sampling that replaces the standard posterior with a fractional or alpha-posterior. By tempering the likelihood with a parameter alpha in (0, 1), the algorithm naturally inflates the posterior covariance. The researchers develop a general regret analysis framework that does not rely on closed-form posterior approximations, instead utilizing first- and second-order posterior concentration theory, including a finite-sample Bernstein-von Mises theorem. They derive regret bounds for both sub-Gaussian and exponential family reward distributions under broad regularity conditions.

The study reveals that alpha-TS provides a principled interpretation of variance inflation as a form of posterior tempering. The authors prove that for the specific choice of alpha proportional to 1/d, the algorithm achieves a regret bound of O(d^{3/2}sqrt{T} log T), which matches the best-known rates for linear bandits. Furthermore, they provide an alpha-dependent lower bound showing that the regret constant depends on the product alpha*d, confirming that the d^{3/2} factor is unavoidable for this class of posterior-sampling algorithms when alpha is scaled to maintain a constant probability of optimism.

This work unifies ad hoc variance-inflation heuristics into a rigorous Bayesian framework. By moving away from the reliance on Gaussian conjugacy, the authors extend the theoretical guarantees of Thompson Sampling to a much wider class of generalized linear models, including the exponential family. This provides researchers with a more robust foundation for applying TS in complex, non-conjugate environments.