Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes that Thompson sampling is at most 2-competitive in terms of the expected number of mistakes made when selecting suboptimal arms in Bayesian bandit models. This finding confirms a 2014 conjecture by Guha and Munagala, demonstrating that the factor of 2 is optimal under the specified conditions. The analysis is applicable to stochastic bandits with independent arm processes and various weighting schemes, reinforcing the robustness of Thompson sampling in decision-making scenarios.
Thompson sampling's mistake rate is provably optimal, making it a critical strategy in Bayesian bandit problems.
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 $2$ is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.