MOTS: Minimax Optimal Thompson Sampling
  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 $\Omega(\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.
