# MINTS: Minimalist Thompson Sampling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 57 references that are in the map.
- First posted on arXiv 1 Jun 2026.

## Builds on (most cited first, 20 of 20)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [A General Framework for Updating Belief Distributions](https://mlsanity.com/paper/1306.6430/) (2013)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Mirrored Langevin Dynamics](https://mlsanity.com/paper/1802.10174/) (2018)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [A Survey of Constrained Gaussian Process Regression: Approaches and Implementation Challenges](https://mlsanity.com/paper/2006.09319/) (2020)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo](https://mlsanity.com/paper/1705.08964/) (2017)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [Structure Adaptive Algorithms for Stochastic Bandits](https://mlsanity.com/paper/2007.00969/) (2020)
- [UCB algorithms for multi-armed bandits: Precise regret and adaptive inference](https://mlsanity.com/paper/2412.06126/) (2024)
- [The Fragility of Optimized Bandit Algorithms](https://mlsanity.com/paper/2109.13595/) (2021)
- [Optimal Learning for Structured Bandits](https://mlsanity.com/paper/2007.07302/) (2020)
- [The Typical Behavior of Bandit Algorithms](https://mlsanity.com/paper/2210.05660/) (2022)
- [Unimodal Thompson Sampling for Graph-Structured Arms](https://mlsanity.com/paper/1611.05724/) (2016)
- [Thompson sampling: Precise arm-pull dynamics and adaptive inference](https://mlsanity.com/paper/2601.21131/) (2026)

## Abstract (arXiv)

The Bayesian paradigm offers principled tools for sequential decision-making under uncertainty, but its reliance on a probabilistic model for all parameters can hinder the incorporation of complex structural constraints. We introduce a minimalist Bayesian framework that places a prior only on the location of the optimum, while eliminating nuisance parameters through profile likelihood. This yields a generalized posterior that naturally accommodates structural constraints. As a direct instantiation, we develop MINimalist Thompson Sampling (MINTS). For multi-armed bandits with mean constraints, we establish near-optimal non-asymptotic regret guarantees and sharp almost-sure asymptotic regret characterizations. In particular, MINTS attains the classical Lai--Robbins constant in the unstructured setting and automatically adapts to unimodal structure, achieving the sharp constant determined only by the immediate neighbors of the optimal arm.