Safety
Thompson Sampling Is 2-Competitive for Mistakes
arXiv:2607.12389v1 Announce Type: cross Abstract: We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal ar
arXiv:2607.12389v1 Announce Type: cross 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 2 is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.
Related
- PFN-TS: Thompson Sampling for Contextual Bandits via Prior-Data Fitted Networks
- Contextual Scalarisation Thompson Sampling for multi-objective decisions in public media
- Design Experiments to Compare Multi-armed Bandit Algorithms
Source: arXiv cs.LG | 2026-07-15