Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors

arXiv:2309.06349v2 Announce Type: replace-cross Abstract: Thompson sampling (TS) is one of the most popular and earliest algorithms to solve stochastic multi-armed bandit problems. We consider a variant of TS, named alpha-TS, where we use a fractional or alpha-posterior (alphain(0,1)) instead of the standard posterior distribution. To compute an alpha-posterior, the likelihood in the definition of the standard posterior is tempered with a factor alpha. For alpha-TS we obtain both instance-dependent Oleft(sum_{k neq i^*} Delta_kleft(frac{log(T)}{C(alpha)Delta_k^2} + frac{1}{2} right)right) and instance-independent O(sqrt{KTlog K}) frequentist regret bounds under very mild conditions on the prior and reward distributions, where Delta_k is the gap between the true mean rewards of the k^{th} and the best arms, and C(alpha) is a known constant. Both the sub-Gaussian and exponential family models satisfy our general conditions on the reward distribution. Our conditions on the prior distribution can be easily satisfied by a density that is positive, continuous, and bounded. We also establish another instance-dependent regret upper bound that matches (up to constants) to that of improved UCB [Auer and Ortner, 2010]. Our regret analysis carefully adapts and combines recent theoretical developments in the non-asymptotic concentration analysis and Bernstein-von Mises type results for the alpha-posterior distribution. Moreover, our analysis does not require additional structural properties such as closed-form posteriors or conjugate priors.

Source: arXiv cs.LG | 2026-09-03