# Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors

arXiv: https://arxiv.org/abs/2309.06349 · HTML: https://mlsanity.com/paper/2309.06349/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 53 references that are in the map.
- First posted on arXiv 12 Sep 2023.

## Builds on (most cited first, 12 of 12)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Concentration of tempered posteriors and of their variational approximations](https://mlsanity.com/paper/1706.09293/) (2017)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [MOTS: Minimax Optimal Thompson Sampling](https://mlsanity.com/paper/2003.01803/) (2020)
- [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017)
- [Effective Evaluation using Logged Bandit Feedback from Multiple Loggers](https://mlsanity.com/paper/1703.06180/) (2017)
- [Thompson Sampling with a Mixture Prior](https://mlsanity.com/paper/2106.05608/) (2021)
- [Diffusion Approximations for Thompson Sampling in the Small Gap Regime](https://mlsanity.com/paper/2105.09232/) (2021)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [α-Variational Inference with Statistical Guarantees](https://mlsanity.com/paper/1710.03266/) (2017)

## Abstract (arXiv)

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.