AI Insight
This paper presents a theoretical analysis of alpha-Thompson Sampling, a variant of the classic Thompson Sampling algorithm for multi-armed bandit problems that uses fractional posteriors (alpha-posteriors with alpha between 0 and 1). The authors prove both instance-dependent and instance-independent regret bounds under mild conditions on prior and reward distributions, showing the algorithm achieves logarithmic regret that matches state-of-the-art methods without requiring restrictive assumptions like conjugate priors or closed-form posteriors.
Why it matters
This work provides theoretical guarantees for a more flexible version of Thompson Sampling that can be applied to a broader class of problems. The relaxed requirements on prior distributions and the elimination of conjugacy constraints make the algorithm more practically applicable while maintaining optimal theoretical performance.
Understand the Science
⚠️ Preprint – Noch nicht peer-reviewed
Dieser Artikel wurde noch nicht von unabhängigen Experten begutachtet. Die Ergebnisse sind vorläufig und sollten mit Vorsicht interpretiert werden.
-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 $mathcal{O}left(sum_{k neq i^*} Delta_kleft(frac{log(T)}{C(alpha)Delta_k^2} + frac{1}{2} right)right)$ and instance-independent $mathcal{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: Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors