MINTS: Minimalist Thompson Sampling

Kaizheng Wang

Abstract

The Bayesian paradigm offers principled tools for sequential decision-making under uncertainty, but its reliance on a probabilistic model for all parameters can hinder the incorporation of complex structural constraints. We introduce a minimalist Bayesian framework that places a prior only on the location of the optimum, while eliminating nuisance parameters through profile likelihood. This yields a generalized posterior that naturally accommodates structural constraints. As a direct instantiation, we develop MINimalist Thompson Sampling (MINTS). For multi-armed bandits with mean constraints, we establish near-optimal non-asymptotic regret guarantees and sharp almost-sure asymptotic regret characterizations. In particular, MINTS attains the classical Lai--Robbins constant in the unstructured setting and automatically adapts to unimodal structure, achieving the sharp constant determined only by the immediate neighbors of the optimal arm.
BibTeX
@inproceedings{wang2025mints,
  author = {Kaizheng Wang},
  title = {{MINTS: Minimalist Thompson Sampling}},
  booktitle = {MLxOR @ NeurIPS},
  year = {2025},
  url = {https://openreview.net/forum?id=bdU4TXlg35},
}

Loading related content...

Figure