# Maillard Sampling: Boltzmann Exploration Done Optimally

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 34 references that are in the map.
- First posted on arXiv 5 Nov 2021.

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

- [Boltzmann Exploration Done Right](https://mlsanity.com/paper/1705.10257/) (2017)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017)
- [Online Stochastic Linear Optimization under One-bit Feedback](https://mlsanity.com/paper/1509.07728/) (2015)
- [Perturbed-History Exploration in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1902.10089/) (2019)
- [Optimally Confident UCB: Improved Regret for Finite-Armed Bandits](https://mlsanity.com/paper/1507.07880/) (2015)

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

- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms](https://mlsanity.com/paper/2303.06058/) (2023)
- [Regret Analysis of Retry-Based Bandits](https://mlsanity.com/paper/2605.20854/) (2026)
- [Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards](https://mlsanity.com/paper/2304.14989/) (2023)
- [Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits](https://mlsanity.com/paper/2405.15200/) (2024)
- [Overcoming Prior Misspecification in Online Learning to Rank](https://mlsanity.com/paper/2301.10651/) (2023)
- [QuACK: A Multipurpose Queuing Algorithm for Cooperative k-Armed Bandits](https://mlsanity.com/paper/2410.23867/) (2024)
- [Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling](https://mlsanity.com/paper/2502.14379/) (2025)
- [The Confusing Instance Principle for Online Linear Quadratic Control](https://mlsanity.com/paper/2510.19531/) (2025)
- [Allocating Divisible Resources on Arms with Unknown and Random Rewards](https://mlsanity.com/paper/2306.16578/) (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)
- [Audit, Alignment, and Optimization of LM-Powered Subroutines with Application to Public Comment Processing](https://mlsanity.com/paper/2507.08109/) (2025)

## Abstract (arXiv)

The PhD thesis of Maillard (2013) presents a rather obscure algorithm for the K-armed bandit problem. This less-known algorithm, which we call Maillard sampling (MS), computes the probability of choosing each arm in a textitclosed form, which is not true for Thompson sampling, a widely-adopted bandit algorithm in the industry. This means that the bandit-logged data from running MS can be readily used for counterfactual evaluation, unlike Thompson sampling. Motivated by such merit, we revisit MS and perform an improved analysis to show that it achieves both the asymptotical optimality and √KTlogT minimax regret bound where T is the time horizon, which matches the known bounds for asymptotically optimal UCB. %'s performance. We then propose a variant of MS called MS^+ that improves its minimax bound to √KTlogK. MS^+ can also be tuned to be aggressive (i.e., less exploration) without losing the asymptotic optimality, a unique feature unavailable from existing bandit algorithms. Our numerical evaluation shows the effectiveness of MS^+.