Abstract
Bayesian optimization (BO) is a popular method for optimizing expensive-to-evaluate black-box functions. BO budgets are typically given in iterations, which implicitly assumes each evaluation has the same cost. However, in many real-world scenarios—from hyperparameter tuning to clinical trials—costs vary significantly across the search space. This paper addresses the limitations of standard "myopic" greedy strategies like Expected Improvement per unit cost (EIpu). We frame cost-constrained BO as a Constrained Markov Decision Process (CMDP) and propose a nonmyopic rollout-based policy that plans multiple steps ahead to maximize long-term improvement within a fixed budget.
Introduction
Bayesian Optimization (BO) has become the standard for optimizing black-box functions where evaluations are costly. Traditional BO frameworks typically operate under a fixed iteration budget, assuming uniform costs for all trials. In practice, however, costs—whether measured in time, money, or energy—are rarely constant. For instance, training a deep neural network with varying architectures or hyperparameters can result in runtimes that differ by orders of magnitude.
The standard approach to handling variable costs is the EIpu (Expected Improvement per unit cost) acquisition function. While intuitive, EIpu is inherently myopic. By prioritizing cheap evaluations, it risks exhausting the budget on low-information trials, potentially ignoring the global optimum if it resides in an expensive region of the search space.
The Challenge of Variable Costs
The motivation for a nonmyopic approach is rooted in the extreme variability of evaluation costs in real-world tasks. In hyperparameter optimization (HPO), the time required to evaluate a model can fluctuate significantly based on the chosen parameters.
As shown in the figure above, models like KNN or Random Forests exhibit a wide range of evaluation times. A greedy algorithm might spend its entire budget exploring the very fast (left-hand side) regions of these distributions, even if the best-performing configurations are found in the slower, more expensive regions.
Methodology: Nonmyopic Planning via Rollouts
To overcome myopia, the authors frame the optimization as a Constrained Markov Decision Process (CMDP). The goal is to find a sequence of evaluation points that maximizes the final improvement while ensuring the total cost remains under a budget $\tau$.
Since solving the CMDP exactly is intractable, the paper proposes a Rollout Approximation:
- Base Policy: A simple heuristic is defined to guide the lookahead. This policy uses EIpu for initial steps to gather cheap information and switches to standard EI for the final step to target high-value regions.
- Lookahead (Rollout): At each decision point, the algorithm simulates multiple future trajectories using the base policy. It evaluates the expected long-term performance of the current action based on these simulations.
- Feasibility Constraint: The rollout only considers paths that are expected to stay within the remaining budget, ensuring the algorithm doesn't overspend early on.
This approach effectively mimics a strategic human optimizer: "Try the quick ideas first to narrow things down, then invest the remaining budget in the most promising, albeit expensive, candidate."
Experimental Results
The researchers validated their approach across three distinct domains:
1. Synthetic "Trap" Problem
They designed a multimodal function where the global minimum is located in the most expensive region. Both standard EI and the greedy EIpu failed, getting stuck in cheaper local minima. The rollout method successfully identified the need to "save" budget for the expensive global optimum.
2. Hyperparameter Optimization
Using the OpenML w2a dataset, the rollout method was applied to tuning KNN, Decision Trees, and Random Forests. In the KNN task, the nonmyopic approach reached lower classification errors significantly faster in terms of wall-clock time compared to both standard EI and EIpu.
3. Sensor Set Selection
In a real-world application using UK Meteorological Office data, the goal was to minimize prediction error by moving physical sensors. The rollout approach consistently outperformed competitors, demonstrating its ability to manage complex cost-benefit trade-offs over a long "20-year" budget horizon.
Conclusion and Future Work
This work demonstrates that looking ahead is crucial when evaluation costs are non-uniform. By treating BO as a long-term planning problem rather than a series of independent greedy choices, the rollout method provides "insurance" against the pitfalls of cheap, low-value exploration.
Future research directions include addressing stochastic costs, where the exact cost of an evaluation is unknown beforehand, and extending the framework to batch BO, where multiple evaluations are performed in parallel.
Summary updated