A Minimalist Bayesian Framework for Stochastic Optimization

2025/09/07 by Wang, Kaizheng
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2509.07030

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

Citations

• Optimal Learning for Structured Bandits
• Bandit Algorithms
• Unimodal Thompson Sampling for Graph-Structured Arms
• Explore First, Exploit Next: The True Shape of Regret in Bandit Problems
• Predictive Entropy Search for Efficient Global Optimization of Black-box\n Functions
• Learning to Optimize via Information-Directed Sampling
• Entropy Search for Information-Efficient Global Optimization
• Multi-Armed Bandits in Metric Spaces
• An informational approach to the global optimization of expensive-to-evaluate functions
• Expectation Propagation for approximate Bayesian inference
• Asymptotically efficient adaptive allocation rules
• Taking the Human Out of the Loop: A Review of Bayesian Optimization

Related

• Stopping Bayesian Optimization with Probabilistic Regret Bounds
• Warm Starting Bayesian Optimization
• Respecting the limit:Bayesian optimization with a bound on the optimal value
• Multi-Step Bayesian Optimization for One-Dimensional Feasibility Determination
• Variational Bayesian Optimistic Sampling