Bayesian optimization (BO) is a class of sample-efficient global optimization
methods, where a probabilistic model conditioned on previous observations is
used to determine future evaluations via the optimization of an acquisition
function. Most acquisition functions are myopic, meaning that they only
consider the impact of the next function evaluation. Non-myopic acquisition
functions consider the impact of the next $h$ function evaluations and are
typically computed through rollout, in which $h$ steps of BO are simulated.
These rollout acquisition functions are defined as $h$-dimensional integrals,
and are expensive to compute and optimize. We show that a combination of
quasi-Monte Carlo, common random numbers, and control variates significantly
reduce the computational burden of rollout. We then formulate a policy-search
based approach that removes the need to optimize the rollout acquisition
function. Finally, we discuss the qualitative behavior of rollout policies in
the setting of multi-modal objectives and model error.