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

Conference on Neural Information Processing Systems (NeurIPS)


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.

Related Publications

All Publications

Human Interpretability Workshop at ICML - April 9, 2021

Investigating Effects of Saturation in Integrated Gradients

Vivek Miglani, Bilal Alsallakh, Narine Kokhlikyan, Orion Reblitz-Richardson

ICASSP - April 8, 2021

Multi-Channel Speech Enhancement Using Graph Neural Networks

Panagiotis Tzirakis, Anurag Kumar, Jacob Donley

JMLR - February 11, 2021

The Decoupled Extended Kalman Filter for Dynamic Exponential-Family Factorization Models

Carlos A. Gómez-Uribe, Brian Karrer

ICSE - March 5, 2021

Testing Web Enabled Simulation at Scale Using Metamorphic Testing

John Ahlgren, Maria Eugenia Berezin, Kinga Bojarczuk, Elena Dulskyte, Inna Dvortsova, Johann George, Natalija Gucevska, Mark Harman, Maria Lomeli, Erik Meijer, Silvia Sapora, Justin Spahr-Summers

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy