MOTS: Minimax Optimal Thompson Sampling

Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, Quanquan Gu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


Thompson sampling is one of the most widely used algorithms for many online decision problems, due to its simplicity in implementation and superior empirical performance over other state-of-the-art methods. Despite its popularity and empirical success, it has remained an open problem whether Thompson sampling can match the minimax lower bound Ω(KT−−−√) for K-armed bandit problems, where T is the total time horizon. In this paper, we solve this long open problem by proposing a variant of Thompson sampling called MOTS that adaptively clips the sampling instance of the chosen arm at each time step. We prove that this simple variant of Thompson sampling achieves the minimax optimal regret bound O(KT−−−√) for finite time horizon T, as well as the asymptotic optimal regret bound for Gaussian rewards when T approaches infinity. To our knowledge, MOTS is the first Thompson sampling type algorithm that achieves the minimax optimality for multi-armed bandit problems.
Original languageEnglish
Title of host publicationMOTS: Minimax Optimal Thompson Sampling
Place of PublicationInternational Conference on Machine Learning (ICML)
Number of pages27
Publication statusPublished - 2021


Dive into the research topics of 'MOTS: Minimax Optimal Thompson Sampling'. Together they form a unique fingerprint.

Cite this