Thompson Sampling Is 2-Competitive for Mistakes

Mark Sellke, Gregory Valiant

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 an…