# Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 42 references that are in the map.
- First posted on arXiv 12 Nov 2021.

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

- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [Maximizing acquisition functions for Bayesian optimization](https://mlsanity.com/paper/1805.10196/) (2018)
- [Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning](https://mlsanity.com/paper/1903.04703/) (2019)
- [Multi-Information Source Optimization](https://mlsanity.com/paper/1603.00389/) (2016)
- [Bayesian Optimization for Materials Design with Mixed Quantitative and Qualitative Variables](https://mlsanity.com/paper/1910.01688/) (2019)
- [A General Framework for Multi-fidelity Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1811.00755/) (2018)
- [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)
- [GLASSES: Relieving The Myopia Of Bayesian Optimisation](https://mlsanity.com/paper/1510.06299/) (2015)
- [BINOCULARS for Efficient, Nonmyopic Sequential Experimental Design](https://mlsanity.com/paper/1909.04568/) (2019)
- [Thompson Sampling for Budgeted Multi-armed Bandits](https://mlsanity.com/paper/1505.00146/) (2015)
- [Why Non-myopic Bayesian Optimization is Promising and How Far Should We Look-ahead? A Study via Rollout](https://mlsanity.com/paper/1911.01004/) (2019)
- [Efficient Rollout Strategies for Bayesian Optimization](https://mlsanity.com/paper/2002.10539/) (2020)
- [A Nonmyopic Approach to Cost-Constrained Bayesian Optimization](https://mlsanity.com/paper/2106.06079/) (2021)

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

- [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://mlsanity.com/paper/2406.20062/) (2024)
- [Generalizing Bayesian Optimization with Decision-theoretic Entropies](https://mlsanity.com/paper/2210.01383/) (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)
- [Collaborative Bayesian Optimization via Wasserstein Barycenters](https://mlsanity.com/paper/2504.10770/) (2025)
- [Knowledge Gradient for Multi-Objective Bayesian Optimization with Decoupled Evaluations](https://mlsanity.com/paper/2302.01310/) (2023)
- [Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need](https://mlsanity.com/paper/2402.02111/) (2024)
- [Cost-aware Stopping for Bayesian Optimization](https://mlsanity.com/paper/2507.12453/) (2025)
- [Sample-Efficient Optimisation with Probabilistic Transformer Surrogates](https://mlsanity.com/paper/2205.13902/) (2022)
- [Adaptive Experimentation at Scale: A Computational Framework for Flexible Batches](https://mlsanity.com/paper/2303.11582/) (2023)
- [Constrained Bayesian Experimental Design via Online Planning](https://mlsanity.com/paper/2605.26990/) (2026)
- [Indirect Query Bayesian Optimization with Integrated Feedback](https://mlsanity.com/paper/2412.13559/) (2024)
- [Cost-Aware Recovery-Pathway Identification and Bayesian Optimization for Autonomous Materials Discovery](https://mlsanity.com/paper/2607.23896/) (2026)
- [Domain Invariant Learning for Gaussian Processes and Bayesian Exploration](https://mlsanity.com/paper/2312.11318/) (2023)
- [An adaptive approach to Bayesian Optimization with switching costs](https://mlsanity.com/paper/2405.08973/) (2024)
- [Neural Nonmyopic Bayesian Optimization in Dynamic Cost Settings](https://mlsanity.com/paper/2601.06505/) (2026)
- [Decision-Focused Active Learning for Scale-Aware Critical-Materials Recovery](https://mlsanity.com/paper/2609.09413/) (2026)

## Abstract (arXiv)

Bayesian optimization (BO) is a sample-efficient approach to optimizing costly-to-evaluate black-box functions. Most BO methods ignore how evaluation costs may vary over the optimization domain. However, these costs can be highly heterogeneous and are often unknown in advance. This occurs in many practical settings, such as hyperparameter tuning of machine learning algorithms or physics-based simulation optimization. Moreover, those few existing methods that acknowledge cost heterogeneity do not naturally accommodate a budget constraint on the total evaluation cost. This combination of unknown costs and a budget constraint introduces a new dimension to the exploration-exploitation trade-off, where learning about the cost incurs the cost itself. Existing methods do not reason about the various trade-offs of this problem in a principled way, leading often to poor performance. We formalize this claim by proving that the expected improvement and the expected improvement per unit of cost, arguably the two most widely used acquisition functions in practice, can be arbitrarily inferior with respect to the optimal non-myopic policy. To overcome the shortcomings of existing approaches, we propose the budgeted multi-step expected improvement, a non-myopic acquisition function that generalizes classical expected improvement to the setting of heterogeneous and unknown evaluation costs. Finally, we show that our acquisition function outperforms existing methods in a variety of synthetic and real problems.