Introduction
Standard Bayesian Optimization (BO) is designed to find both the maximum value of a black-box function and the exact input location where it occurs. However, in many real-world optimization tasks, we are not searching entirely in the dark—we already know the best possible outcome (the "what"), but we do not know the parameters to achieve it (the "where"). For instance, when tuning hyperparameters for a classifier, the maximum possible accuracy is strictly 100%. In Reinforcement Learning (RL), many benchmark environments have a known maximum reward.
Standard BO treats these scenarios like any other black-box function, ignoring this valuable prior knowledge. This oversight leads to wasted queries where the model explores regions that are mathematically impossible (e.g., predicting an accuracy of 110%) or fails to exploit the known target. This paper introduces a framework that bakes the known optimum value ($f^*$) directly into the surrogate model and the decision-making process, allowing the optimization to reach the optimum significantly faster.
Methodology
To bridge the gap between standard BO and known-optimum problems, the authors propose two major innovations: a Transformed Gaussian Process and novel acquisition functions.
Transformed Gaussian Process (TGP)
Standard Gaussian Processes (GPs) can predict values anywhere, often exceeding known logical limits. To enforce the constraint that the function never exceeds the known maximum $f^*$, the authors apply a mathematical transformation:
$$f(x) = f^* - \frac{1}{2}g^2(x)$$
where $g(x)$ is a standard GP. Because the squared term is always non-negative, $f(x)$ is strictly guaranteed to be $\leq f^*$. To keep the mathematics tractable—since squaring a GP makes it non-Gaussian—they utilize a Taylor expansion linearization trick to approximate the posterior as a Gaussian.
This transformation creates a "ceiling effect." The model lifts its predictions toward the known maximum in promising areas but strictly prevents the mean or confidence intervals from crossing that ceiling, resulting in a much more informative surrogate model.
New Acquisition Functions
With the TGP in place, the authors introduce two acquisition functions tailored for known optima:
- Confidence Bound Minimization (CBM): Inspired by the Upper Confidence Bound (UCB) algorithm, CBM flips the traditional logic. Instead of searching for the highest possible value, it searches for the location where the predicted mean is closest to $f^*$ and the uncertainty is low.
- Expected Regret Minimization (ERM): This is the known-optimum counterpart to Expected Improvement (EI). It calculates the expected difference between the known $f^*$ and the function value at a candidate point, choosing the point that minimizes this "regret." Crucially, ERM is parameter-free, making it highly robust.
Experiments and Key Results
The researchers evaluated their approach across synthetic benchmarks (Branin, Hartmann, Alpine1, gSobol) and real-world tasks, including XGBoost hyperparameter tuning on the Skin Segmentation dataset (target accuracy 100%) and Deep Reinforcement Learning tuning for CartPole-v0 (known maximum reward of 200).
Key Insights: * ERM Outperforms Baselines: Across almost all benchmarks, Expected Regret Minimization (ERM) outperformed standard BO methods (EI and UCB) and other recent methods designed to handle known optima (like MES). * Faster Convergence: In the XGBoost tuning task, ERM reached near-perfect accuracy in significantly fewer iterations. On the CartPole problem, the ERM approach reached the optimal reward of 200 within just 20 iterations, while standard methods continued to fluctuate at lower reward levels. * High-Dimensional Efficiency: The benefit of knowing $f^*$ becomes increasingly pronounced as problem dimensionality grows. In 10D synthetic problems, the proposed methods successfully found the optimum while standard BO struggled to gain traction. * Smarter Exploration:* Standard BO often over-explores because it doesn't know how close it is to the peak. By knowing $f^*$, ERM recognizes when it has likely found the optimum and stops wasting resources, or conversely, abandons regions where even the best-case prediction falls far below $f^*$.
Limitations and Future Work
While highly effective, the framework has limitations. The authors noted a sensitivity to misspecification: if an incorrect $f^*$ is provided, performance drops. Under-specifying the maximum is particularly dangerous, as the acquisition function can get "stuck" in a sub-optimal region, falsely believing it has reached the peak.
Future work could extend this approach to handle noisy observations or scenarios where the maximum is only known within a certain range. Additionally, extending the framework to "batch" BO—evaluating multiple points simultaneously—would be a valuable next step for parallel computing environments.
Summary updated