MINTS Beats Thompson Sampling by Ditching Full Probabilistic Models
A new bandit algorithm skips full Bayesian modeling, placing a prior only on which arm is best — and still hits theoretical optimality bounds while adapting to structure automatically.
- MINTS is a new Thompson Sampling variant that places a prior only on which arm is optimal, not on all reward parameters — simplifying Bayesian bandit design.
- Structural constraints (e.g., unimodality) are handled automatically via profile likelihood, requiring no algorithm redesign per constraint type.
- MINTS provably attains the Lai-Robbins lower bound in the unstructured setting — the gold standard for bandit algorithm optimality.
- In unimodal bandits, MINTS achieves the sharper neighbor-only constant and shows tighter empirical concentration than OSUB, UTS, and OSSB.
- The framework extends to Lipschitz bandits, dynamic pricing, and offers probabilistic interpretations of classical convex optimization algorithms.
- No code is released yet; scalability to continuous/high-dimensional action spaces is flagged as an open problem.
Bayesian bandit algorithms are powerful, but they carry a hidden cost: to use them properly, you need a full probabilistic model over every unknown parameter in your problem. That works fine for simple cases, but the moment you want to enforce structural constraints , like "the reward function must be unimodal" , the standard Bayesian machinery starts to fight you. A new paper by Kaizheng Wang proposes a cleaner path forward.
The paper, titled MINTS: Minimalist Thompson Sampling, introduces a stripped-down Bayesian framework that sidesteps the full-model requirement entirely. The core idea is deceptively simple: instead of placing a prior over all the reward parameters, just place a prior over which arm is optimal. Everything else gets handled by a technique called profile likelihood, which eliminates the nuisance parameters , the reward distributions you don't really care about , by optimizing them out rather than modeling them.
The Problem with Standard Thompson Sampling
Thompson Sampling (TS) is one of the most popular algorithms for the multi-armed bandit problem , the classic explore-vs-exploit tradeoff where an agent repeatedly picks from a set of options ("arms") and tries to maximize cumulative reward. TS treats the bandit problem from a Bayesian perspective, maintaining a posterior distribution over the unknown parameter for each arm. At each round, it samples a plausible reward value from each arm's posterior and picks the arm that looks best under that sample.
This works well in the unstructured case. But the Bayesian paradigm's reliance on a probabilistic model for all parameters can hinder the incorporation of complex structural constraints. If you know your reward landscape is unimodal , rewards peak at one arm and decrease on either side , standard TS has no clean way to encode that. You'd need to redesign the prior and likelihood from scratch for every new constraint type.
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
