Title: MINTS: Minimalist Thompson Sampling

Abstract:

While the Bayesian framework provides rigorous methods for sequential decision-making under uncertainty, its standard practice of assigning probabilistic models to every parameter can complicate the integration of complex structural constraints. To address this, we propose a minimalist Bayesian approach that restricts priors solely to the location of the optimum, effectively removing nuisance parameters via profile likelihood. This strategy produces a generalized posterior distribution that inherently supports structural constraints. As a specific application, we present MINimalist Thompson Sampling (MINTS). For multi-armed bandit problems involving mean constraints, we demonstrate near-optimal non-asymptotic regret bounds and precise almost-sure asymptotic regret descriptions. Specifically, in unstructured environments, MINTS achieves the well-known Lai–Robbins constant, while in unimodal settings, it automatically adapts to achieve a sharp constant determined exclusively by the arms adjacent to the optimum.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC