Thompson Sampling Is 2-Competitive for Mistakes
arXiv:2607.12389
The paper proves that Thompson sampling incurs at most twice the expected number of suboptimal arm selections as any other policy in Bayesian bandit settings, under independent arm processes and various weighting schemes.
Abstract
We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our analysis applies as long as the latent arm processes are independent and each arm evolves only when played. For stochastic bandits with best arm defined via mean reward, this confirms a conjecture of Guha and Munagala from 2014, where the factor is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.
10 pages