# A Minimalist Bayesian Framework for Stochastic Optimization

arXiv: https://arxiv.org/abs/2509.07030 · HTML: https://mlsanity.com/paper/2509.07030/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 47 references that are in the map.
- First posted on arXiv 7 Sep 2025.

## Builds on (most cited first, 9 of 9)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [A General Framework for Updating Belief Distributions](https://mlsanity.com/paper/1306.6430/) (2013)
- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [A Survey of Constrained Gaussian Process Regression: Approaches and Implementation Challenges](https://mlsanity.com/paper/2006.09319/) (2020)
- [Optimal Learning for Structured Bandits](https://mlsanity.com/paper/2007.07302/) (2020)
- [Unimodal Thompson Sampling for Graph-Structured Arms](https://mlsanity.com/paper/1611.05724/) (2016)

## Abstract (arXiv)

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 component of interest, such as the location of the optimum. Nuisance parameters are eliminated via profile likelihood, which naturally handles constraints. As a direct instantiation, we develop a MINimalist Thompson Sampling (MINTS) algorithm. Our framework accommodates structured problems, including continuum-armed Lipschitz bandits and dynamic pricing. It also provides a probabilistic lens on classical convex optimization algorithms such as the center of gravity and ellipsoid methods. We further analyze MINTS for multi-armed bandits and establish near-optimal regret guarantees.