  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.
