Maillard Sampling: Boltzmann Exploration Done Optimally
This work addresses the bandit problem for researchers and practitioners by improving algorithm performance with concrete bounds, though it is incremental as it builds on prior work.
The paper revisits Maillard sampling, an obscure bandit algorithm, showing it achieves asymptotic optimality and a minimax regret bound of √(KT log T), matching known bounds, and proposes MS⁺ with improved √(KT log K) bound and tunable aggressiveness while maintaining optimality.
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 \textit{closed 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 $\sqrt{KT\log{T}}$ 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 $\sqrt{KT\log{K}}$. 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$^+$.