# MOTS: Minimax Optimal Thompson Sampling

arXiv: https://arxiv.org/abs/2003.01803 · HTML: https://mlsanity.com/paper/2003.01803/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2020.

## Built on by (most cited first, 28 of 28)

- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2401.11665/) (2024)
- [An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Bandits](https://mlsanity.com/paper/2311.05794/) (2023)
- [Constrained Exploration via Reflected Replica Exchange Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2405.07839/) (2024)
- [VITS : Variational Inference Thompson Sampling for contextual bandits](https://mlsanity.com/paper/2307.10167/) (2023)
- [Thompson Sampling for Robust Transfer in Multi-Task Bandits](https://mlsanity.com/paper/2206.08556/) (2022)
- [Efficient Online Set-valued Classification with Bandit Feedback](https://mlsanity.com/paper/2405.04393/) (2024)
- [Bandit Allocational Instability](https://mlsanity.com/paper/2602.07472/) (2026)
- [Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment](https://mlsanity.com/paper/2102.07929/) (2021)
- [Batched Thompson Sampling for Multi-Armed Bandits](https://mlsanity.com/paper/2108.06812/) (2021)
- [Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards](https://mlsanity.com/paper/2304.14989/) (2023)
- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)
- [Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2511.02123/) (2025)
- [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026)
- [Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2302.09440/) (2023)
- [Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention](https://mlsanity.com/paper/2402.15127/) (2024)
- [Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling](https://mlsanity.com/paper/2502.14379/) (2025)
- [Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective](https://mlsanity.com/paper/2510.05023/) (2025)
- [Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors](https://mlsanity.com/paper/2309.06349/) (2023)
- [Zero-Inflated Bandits](https://mlsanity.com/paper/2312.15595/) (2023)
- [Efficient and Adaptive Posterior Sampling Algorithms for Bandits](https://mlsanity.com/paper/2405.01010/) (2024)
- [Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret](https://mlsanity.com/paper/2505.02383/) (2025)
- [Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift](https://mlsanity.com/paper/2605.10289/) (2026)
- [Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set](https://mlsanity.com/paper/2607.23679/) (2026)

## Abstract (arXiv)

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(√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.