---
title: "MINTS Beats Thompson Sampling by Ditching Full Probabilistic Models"
subtitle: "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."
url: "https://alphasignal.ai/news/mints-beats-thompson-sampling-by-ditching-full-probabilistic-models"
author: "AlphaSignal Newsroom"
author_url: "https://alphasignal.ai/editorial-team"
company: "AlphaSignal"
company_url: "https://alphasignal.ai/company/alphasignal"
published: "2026-06-01T00:00:00.000Z"
updated: "2026-06-09T10:46:57.859Z"
type: "Paper"
topics:
  - "Reasoning"
  - "Benchmarks"
subtopics:
  - "Test Time Compute"
  - "Math Reasoning"
upvotes: 1870
source_url: "https://arxiv.org/abs/2606.01655"
comments: 0
truncated: true
---

# 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.

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](https://arxiv.org/abs/2606.01655), 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.

_Preview only. Full text requires an AlphaSignal Pro account._

## Sources

- [MINTS: Minimalist Thompson Sampling (arXiv 2606.01655)](https://arxiv.org/abs/2606.01655)
- [A Minimalist Bayesian Framework for Stochastic Optimization (arXiv 2509.07030)](https://arxiv.org/abs/2509.07030)
- [MINTS HTML paper (arXiv)](https://arxiv.org/html/2606.01655)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms (OSUB paper)](https://arxiv.org/abs/1405.5096)