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 (α in(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 O (sum k not equal to i* Δ k ((T) over C(α)Δ k squared + 1 over 2)) and instance-independent O(sqrt KT K) frequentist regret bounds under very mild conditions on the prior and reward distributions, where Δ k is the gap between the true mean rewards of the k th 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.