Optimization

Multi-Step Optimal Acquisition Functions

^ ^
We can view the act of solving problem (1) as a sequential decision-making problem (Ginsbourger and ^{Riche, 2010; Frazier, 2012), in which we sequentially choose x}n^{, and observe y}n ^{= f (x}n^{), with the choice of x}n ^{depending on all past observations. At the end of these observations, we then receive a reward} that might be equal to the value of the best point observed, max_m≤N f (x_m), as it was in the analysis of EI, or could be equal to the value f (x^∗) of the objective at some new point x^∗ chosen based on these observations as in the analysis of KG, or it could be the entropy of the posterior distribution on x^∗ as in ES or PES.
By construction, the EI, KG, ES, and PES acquisition functions are optimal when N = n + 1, in the sense of maximizing the expected reward under the posterior. However, they are no longer obviously optimal when N > n + 1. In principle, it is possible to compute a multi-step optimal acquisition function that would maximize expected reward for general N via stochastic dynamic programming (Dynkin and Yushkevich, 1979), but the so-called curse of dimensionality (Powell, 2007) makes it extremely challenging to compute this multi-step optimal acquisition function in practice.
Nevertheless, the literature has recently begun to deploy approximate methods for computing this so- lution, with attempts including Lam et al. (2016); Ginsbourger and Riche (2010); Gonz´alez et al. (2016). These methods do not yet seem to be in a state where they can be deployed broadly for practical prob- lems, because the error and extra cost introduced in solving stochastic dynamic programming problems approximately often overwhelms the benefit that considering multiple steps provides. Nevertheless, given concurrent advances in reinforcement learning and approximate dynamic programming, this represents a promising and exciting direction for Bayesian optimization.
In addition, there are other problem settings closely related to the one most commonly considered by Bayesian optimization where it is possible to compute multi-step optimal algorithms. For example, Cashore et al. (2016) and Xie and Frazier (2013) use problem structure to efficiently compute multi-step optimal algorithms for certain classes of Bayesian feasibility determination problems, where we wish to sample efficiently to determine whether f (x) is above or below a threshold for each x. Similarly, Waeber et al. (2013), building on Jedynak et al. (2012), computes the multi-step optimal algorithm for a one-dimensional stochastic root-finding problem with an entropy objective. While these optimal multi- step methods are only directly applicable to very specific settings, they offer an opportunity to study the improvement possible more generally by going from one-step optimal to multi-step optimal. Surprisingly, in these settings, existing acquisition functions perform almost as well as the multi-step optimal algorithm. For example, experiments conducted in Cashore et al. (2016) show the KG acquisition function is within 98% of optimal in the problems computed there, and Waeber et al. (2013) shows that the entropy search acquisition function is multi-step optimal in the setting considered there. Generalizing from these results, it could be that the one-step acquisition functions are close enough to optimal that further improvement is not practically meaningful, or it could be that multi-step optimal algorithms will provide substantially better performance in yet-to-be-identified practically important settings.

5.