Skip to main content
Back

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.

Paper, Full Access
  • 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.