Exploring and Exploiting Model Uncertainty in Bayesian Optimization

In this work, we consider the problem of Bayesian Optimization (BO) under reward model uncertainty —that is, when the underlying distribution type of the reward is unknown and potentially intractable to specify. This challenge is particularly evident in many modern applications, where the reward distribution is highly ill-behaved, often non-stationary, multi-modal, or heavy-tailed. In such settings, classical Gaussian Process (GP)-based BO methods often fail due to their strong modeling assumptions. To address this challenge, we propose a novel surrogate model, the infinity-Gaussian Process ( ∞ -GP), which represents a sequential spatial Dirichlet Process mixture with a GP baseline. The ∞ -GP quantifies both value uncertainty and model uncertainty, enabling more flexible modeling of complex reward structures. Combined with Thompson Sampling, the ∞ -GP facilitates principled exploration and exploitation in the distributional space of reward models. Theoretically, we prove that the ∞ -GP surrogate model can approximate a broad class of reward distributions by effectively exploring the distribution space, achieving near-minimax-optimal posterior contraction rates. Empirically, our method outperforms state-of-the-art approaches in various challenging scenarios, including highly non-stationary and heavy-tailed reward settings where classical GP-based BO often fails.