MOTS: Minimax Optimal Thompson Sampling
This solves a long-standing theoretical gap in online decision-making for researchers and practitioners in bandit algorithms, though it is incremental as it modifies an existing method.
The paper tackles the open problem of whether Thompson sampling can achieve the minimax lower bound for K-armed bandit problems, and proposes MOTS, a variant that adaptively clips sampling instances to achieve the minimax optimal regret bound O(√KT) for finite time horizon T and asymptotic optimality for Gaussian rewards.
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 $Ω(\sqrt{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(\sqrt{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.