# Efficient Nonmyopic Bayesian Optimization via One-Shot Multi-Step Trees

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2020.

## Built on by (most cited first, 30 of 41)

- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [Accelerating Bayesian Optimization for Biological Sequence Design with Denoising Autoencoders](https://mlsanity.com/paper/2203.12742/) (2022)
- [Preference Exploration for Efficient Bayesian Optimization with Multiple Outcomes](https://mlsanity.com/paper/2203.11382/) (2022)
- [Bayesian Optimization with High-Dimensional Outputs](https://mlsanity.com/paper/2106.12997/) (2021)
- [Thinking inside the box: A tutorial on grey-box Bayesian optimization](https://mlsanity.com/paper/2201.00272/) (2022)
- [Reinforced Few-Shot Acquisition Function Learning for Bayesian Optimization](https://mlsanity.com/paper/2106.04335/) (2021)
- [Conditioning Sparse Variational Gaussian Processes for Online Decision-making](https://mlsanity.com/paper/2110.15172/) (2021)
- [A Nonmyopic Approach to Cost-Constrained Bayesian Optimization](https://mlsanity.com/paper/2106.06079/) (2021)
- [Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs](https://mlsanity.com/paper/2111.06537/) (2021)
- [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://mlsanity.com/paper/2406.20062/) (2024)
- [A Bayesian Optimization Framework for Finding Local Optima in Expensive Multi-Modal Functions](https://mlsanity.com/paper/2210.06635/) (2022)
- [Bayesian Optimization of Function Networks with Partial Evaluations](https://mlsanity.com/paper/2311.02146/) (2023)
- [Exploring Exploration in Bayesian Optimization](https://mlsanity.com/paper/2502.08208/) (2025)
- [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)
- [Adaptive Elicitation of Latent Information Using Natural Language](https://mlsanity.com/paper/2504.04204/) (2025)
- [Look-Ahead Acquisition Functions for Bernoulli Level Set Estimation](https://mlsanity.com/paper/2203.09751/) (2022)
- [MONGOOSE: Path-wise Smooth Bayesian Optimisation via Meta-learning](https://mlsanity.com/paper/2302.11533/) (2023)
- [Two-step Lookahead Bayesian Optimization with Inequality Constraints](https://mlsanity.com/paper/2112.02833/) (2021)
- [Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need](https://mlsanity.com/paper/2402.02111/) (2024)
- [Sample-Efficient Optimisation with Probabilistic Transformer Surrogates](https://mlsanity.com/paper/2205.13902/) (2022)
- [Rollout Algorithms and Approximate Dynamic Programming for Bayesian Optimization and Sequential Estimation](https://mlsanity.com/paper/2212.07998/) (2022)
- [Multi-step Planning for Automated Hyperparameter Optimization with OptFormer](https://mlsanity.com/paper/2210.04971/) (2022)
- [Scalable Bayesian optimization with high-dimensional outputs using randomized prior networks](https://mlsanity.com/paper/2302.07260/) (2023)
- [Adaptive Experimentation at Scale: A Computational Framework for Flexible Batches](https://mlsanity.com/paper/2303.11582/) (2023)
- [BatchGFN: Generative Flow Networks for Batch Active Learning](https://mlsanity.com/paper/2306.15058/) (2023)
- [Optimal Initialization of Batch Bayesian Optimization](https://mlsanity.com/paper/2404.17997/) (2024)
- [Batched Energy-Entropy acquisition for Bayesian Optimization](https://mlsanity.com/paper/2410.08804/) (2024)
- [Constrained Bayesian Experimental Design via Online Planning](https://mlsanity.com/paper/2605.26990/) (2026)
- [Differentiating Policies for Non-Myopic Bayesian Optimization](https://mlsanity.com/paper/2408.07812/) (2024)

## Abstract (arXiv)

Bayesian optimization is a sequential decision making framework for optimizing expensive-to-evaluate black-box functions. Computing a full lookahead policy amounts to solving a highly intractable stochastic dynamic program. Myopic approaches, such as expected improvement, are often adopted in practice, but they ignore the long-term impact of the immediate decision. Existing nonmyopic approaches are mostly heuristic and/or computationally expensive. In this paper, we provide the first efficient implementation of general multi-step lookahead Bayesian optimization, formulated as a sequence of nested optimization problems within a multi-step scenario tree. Instead of solving these problems in a nested way, we equivalently optimize all decision variables in the full tree jointly, in a ``one-shot'' fashion. Combining this with an efficient method for implementing multi-step Gaussian process ``fantasization,'' we demonstrate that multi-step expected improvement is computationally tractable and exhibits performance superior to existing methods on a wide range of benchmarks.