# A Nonmyopic Approach to Cost-Constrained Bayesian Optimization

arXiv: https://arxiv.org/abs/2106.06079 · HTML: https://mlsanity.com/paper/2106.06079/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 10 Jun 2021.

## Builds on (most cited first, 14 of 14)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020](https://mlsanity.com/paper/2104.10201/) (2021)
- [Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets](https://mlsanity.com/paper/1605.07079/) (2016)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [Multi-Information Source Optimization](https://mlsanity.com/paper/1603.00389/) (2016)
- [Cost-aware Bayesian Optimization](https://mlsanity.com/paper/2003.10870/) (2020)
- [Efficient Nonmyopic Bayesian Optimization via One-Shot Multi-Step Trees](https://mlsanity.com/paper/2006.15779/) (2020)
- [Efficient Rollout Strategies for Bayesian Optimization](https://mlsanity.com/paper/2002.10539/) (2020)
- [Cost-aware Multi-objective Bayesian optimisation](https://mlsanity.com/paper/1909.03600/) (2019)
- [Pareto-efficient Acquisition Functions for Cost-Aware Bayesian Optimization](https://mlsanity.com/paper/2011.11456/) (2020)

## Built on by (most cited first, 19 of 19)

- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs](https://mlsanity.com/paper/2111.06537/) (2021)
- [Evolve Cost-aware Acquisition Functions Using Large Language Models](https://mlsanity.com/paper/2404.16906/) (2024)
- [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://mlsanity.com/paper/2406.20062/) (2024)
- [SnAKe: Bayesian Optimization with Pathwise Exploration](https://mlsanity.com/paper/2202.00060/) (2022)
- [Bayesian Optimization of Function Networks with Partial Evaluations](https://mlsanity.com/paper/2311.02146/) (2023)
- [Bayesian Optimization Over Iterative Learners with Structured Responses: A Budget-aware Planning Approach](https://mlsanity.com/paper/2206.12708/) (2022)
- [Transition Constrained Bayesian Optimization via Markov Decision Processes](https://mlsanity.com/paper/2402.08406/) (2024)
- [The Gittins Index: A Design Principle for Decision-Making Under Uncertainty](https://mlsanity.com/paper/2506.10872/) (2025)
- [Knowledge Gradient for Multi-Objective Bayesian Optimization with Decoupled Evaluations](https://mlsanity.com/paper/2302.01310/) (2023)
- [Rollout Algorithms and Approximate Dynamic Programming for Bayesian Optimization and Sequential Estimation](https://mlsanity.com/paper/2212.07998/) (2022)
- [Constrained Bayesian Experimental Design via Online Planning](https://mlsanity.com/paper/2605.26990/) (2026)
- [Learning Relevant Contextual Variables Within Bayesian Optimization](https://mlsanity.com/paper/2305.14120/) (2023)
- [An adaptive approach to Bayesian Optimization with switching costs](https://mlsanity.com/paper/2405.08973/) (2024)
- [The Traveling Bandit: A Framework for Bayesian Optimization with Movement Costs](https://mlsanity.com/paper/2410.14533/) (2024)
- [Nonmyopic Global Optimisation via Approximate Dynamic Programming](https://mlsanity.com/paper/2412.04882/) (2024)
- [Non-Myopic Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2412.08085/) (2024)
- [Neural Nonmyopic Bayesian Optimization in Dynamic Cost Settings](https://mlsanity.com/paper/2601.06505/) (2026)
- [Energy-aware frugal Bayesian optimization](https://mlsanity.com/paper/2609.31638/) (2026)

## Abstract (arXiv)

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.