Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits
This work provides a theoretical analysis for Thompson sampling in bandit problems with common reward distributions, which is incremental but offers strong guarantees for researchers and practitioners in reinforcement learning and decision-making.
The authors tackled the problem of analyzing the regret of Thompson sampling algorithms for exponential family multi-armed bandits, proposing ExpTS and ExpTS+ algorithms that achieve sub-UCB finite-time regret bounds, minimax optimality up to a factor of sqrt(log K), and asymptotic optimality for K-armed bandits over horizon T.
We study the regret of Thompson sampling (TS) algorithms for exponential family bandits, where the reward distribution is from a one-dimensional exponential family, which covers many common reward distributions including Bernoulli, Gaussian, Gamma, Exponential, etc. We propose a Thompson sampling algorithm, termed ExpTS, which uses a novel sampling distribution to avoid the under-estimation of the optimal arm. We provide a tight regret analysis for ExpTS, which simultaneously yields both the finite-time regret bound as well as the asymptotic regret bound. In particular, for a $K$-armed bandit with exponential family rewards, ExpTS over a horizon $T$ is sub-UCB (a strong criterion for the finite-time regret that is problem-dependent), minimax optimal up to a factor $\sqrt{\log K}$, and asymptotically optimal, for exponential family rewards. Moreover, we propose ExpTS$^+$, by adding a greedy exploitation step in addition to the sampling distribution used in ExpTS, to avoid the over-estimation of sub-optimal arms. ExpTS$^+$ is an anytime bandit algorithm and achieves the minimax optimality and asymptotic optimality simultaneously for exponential family reward distributions. Our proof techniques are general and conceptually simple and can be easily applied to analyze standard Thompson sampling with specific reward distributions.