A Nonmyopic Approach to Cost-Constrained Bayesian Optimization

Eric Hans Lee, David Eriksson, Valerio Perrone, Matthias W. Seeger

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. In fact, in many BO applications, evaluation costs vary significantly in different regions of the search space. In hyperparameter optimization, the time spent on neural network training increases with layer size; in clinical trials, the monetary cost of drug compounds vary; and in optimal control, control actions have differing complexities. Cost-constrained BO measures convergence with alternative cost metrics such as time, money, or energy, for which the sample efficiency of standard BO methods is ill-suited. For cost-constrained BO, cost efficiency is far more important than sample efficiency. In this paper, we formulate cost-constrained BO as a constrained Markov decision process (CMDP), and develop an efficient rollout approximation to the optimal CMDP policy that takes both the cost and future iterations into account. We validate our method on a collection of hyperparameter optimization problems as well as a sensor set selection application.

The Challenge of Non-Uniform Costs

Standard Bayesian Optimization (BO) is the go-to tool for optimizing "expensive" black-box functions, such as tuning hyperparameters or designing drug compounds. However, most BO algorithms measure their budget in iterations, implicitly assuming that every evaluation has a uniform cost.

In practice, costs are rarely uniform. For instance, in machine learning, training a model with 100 layers takes significantly longer than one with 10 layers. In robotics, certain control actions consume more energy or time than others. The "de-facto" solution has been a greedy approach known as EIpu (Expected Improvement per unit cost), which divides the expected gain by the cost. However, this approach is often too myopic; it becomes biased toward cheap, low-quality regions of the search space and may never "save up" enough budget to evaluate an expensive region where the true global optimum resides.

Distribution of evaluation times for various machine learning models on the w2a dataset, illustrating the significant variance in computational costs.

Methodology: From Myopic to Nonmyopic BO

To address the limitations of greedy strategies, this paper proposes a nonmyopic (far-sighted) approach that treats BO as a Constrained Markov Decision Process (CMDP). The goal is to maximize the cumulative improvement in the objective function while ensuring the total cost of all evaluations remains under a fixed budget $\tau$.

Rollout Approximation

Solving a CMDP exactly is computationally intractable for BO due to the infinite state space. The authors utilize a rollout strategy to simulate the future by looking $h$ steps ahead. To decide the next point to sample, the algorithm estimates the total value of sampling that point plus following a "base policy" for the remaining steps.

The Base Policy

A key contribution is the specific base policy design: it uses $h-1$ steps of $EIpu$ (to explore cheap areas) followed by a final step of standard EI (to exploit high-value areas). This "early exploration, late exploitation" heuristic ensures the algorithm accounts for the remaining budget. Additionally, a Gaussian Process (GP) is used to model the cost function $c(x)$ itself, allowing the optimizer to predict expenses before sampling.

Experimental Validation

The researchers evaluated their approach across three distinct problem types:

  1. Synthetic Benchmarks: A multimodal objective function where the global optimum is intentionally placed in the most expensive region to test for "greedy traps."
  2. Hyperparameter Optimization (HPO): Tuning models like $k$-nearest neighbors (KNN), Decision Trees, and Random Forests using the OpenML 'w2a' and 'a1a' datasets.
  3. Sensor Set Selection: A real-world application using weather data from the UK Meteorological Office (MIDAS), where the "cost" is the physical distance a sensor must be moved.

Key Insights and Results

  • Overcoming the Greedy Failure Mode: On the synthetic "trap" problem, $EIpu$ got stuck in cheap local minima. In contrast, the nonmyopic rollout successfully identified and "paid for" the expensive global optimum.
  • Superior Efficiency: In HPO tasks, the rollout approach (with horizons of 2 or 4) consistently achieved lower classification errors for the same time budget compared to both standard EI and the greedy EIpu.
  • Budget Awareness: By framing the problem as a CMDP, the algorithm "knows" when the budget is running out. It can choose to evaluate an expensive, high-reward point early before it becomes infeasible due to a dwindling budget.
  • Sequential Consistency: The authors provide theoretical backing (Theorem 1), showing that their rollout policy is guaranteed to perform at least as well as the base policy it mimics, provided the policy is "sequentially consistent."

Limitations and Future Work

While powerful, the primary drawback is the computational overhead of the optimizer. Running a rollout requires simulating many future paths, making this method best suited for "truly expensive" functions where an evaluation takes minutes or hours.

Future work may extend this framework to handle stochastic costs (e.g., fluctuating cloud computing prices) and batch BO, where multiple points are evaluated in parallel—a significant open challenge in cost-constrained settings.

Summary updated

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. In fact, in many BO applications, evaluation costs vary significantly in different regions of the search space. In hyperparameter optimization, the time spent on neural network training increases with layer size; in clinical trials, the monetary cost of drug compounds vary; and in optimal control, control actions have differing complexities. Cost-constrained BO measures convergence with alternative cost metrics such as time, money, or energy, for which the sample efficiency of standard BO methods is ill-suited. For cost-constrained BO, cost efficiency is far more important than sample efficiency. In this paper, we formulate cost-constrained BO as a constrained Markov decision process (CMDP), and develop an efficient rollout approximation to the optimal CMDP policy that takes both the cost and future iterations into account. We validate our method on a collection of hyperparameter optimization problems as well as a sensor set selection application.
BibTeX
@inproceedings{lee2021nonmyopic,
  author = {Eric Hans Lee and David Eriksson and Valerio Perrone and Matthias W. Seeger},
  title = {{A Nonmyopic Approach to Cost-Constrained Bayesian Optimization}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=dfDFgCK_2R},
}
Figure