Generalized Regret Analysis of Thompson Sampling using Fractional
  Posteriors
Prateek Jaiswal Debdeep Pati Anirban Bhattacharya Bani K. Mallick
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
($\alpha\in(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 $\mathcal{O}\left(\sum_{k \neq i^*}
\Delta_k\left(\frac{\log(T)}{C(\alpha)\Delta_k^2} + \frac{1}{2} \right)\right)$
and instance-independent $\mathcal{O}(\sqrt{KT\log 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 just require its density
to be 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 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.