Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors

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 α-TS, where we use a fractional or α-posterior (α∈(0,1)) instead of the standard posterior distribution. To compute an α-posterior, the likelihood in the definition of the standard posterior is tempered with a factor α. For α-TS we obtain both instance-dependent Oleft(sumk neq i^* Deltakleft(fraclog(T)C(α)Deltak2 + frac12 right)right) and instance-independent O(√KTlog K) frequentist regret bounds under very mild conditions on the prior and reward distributions, where Deltak is the gap between the true mean rewards of the kth and the best arms, and C(α) 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 α-posterior distribution. Moreover, our analysis does not require additional structural properties such as closed-form posteriors or conjugate priors.