Bayesian Optimization with a Finite Budget: An Approximate Dynamic Programming Approach
We consider the problem of optimizing an expensive objective function when a finite budget of total evaluations is prescribed. In that context, the optimal solution strategy for Bayesian optimization can be formulated as a dynamic programming instance. This results in a complex problem with uncountable, dimension-increasing state space and an uncountable control space. We show how to approximate the solution of this dynamic programming problem using rollout, and propose rollout heuristics specifically designed for the Bayesian optimization setting. We present numerical experiments showing that the resulting algorithm for optimization with a finite budget outperforms several popular Bayesian optimization algorithms.
Bayesian Optimization algorithms for deterministic functions (possibly observed in noise) with continuous input domain have been intensively adressed in recent decades within the framework of Gaussian Process modelling. Here the authors focus on an important issue with most state-of-the-art strategies, namely that the acquisition function is often relying on one-step-lookahead considerations, and does not account for the information brought by candidate points regarding susceptible pay-offs in future iterations. This is known as the finite budget / time horizon set-up, and has inspired several of the papers referenced in the bibliography. The focus here is on transferring know-how and formalism from the world of Dynamic Programming (DP) to Bayesian Optimization (BO). In particular, it is recalled and formalized how the finite time BO problem can be cast as a DP one, and more centrally how an Approximate DP approach called Rollout can be adapted to it.  A finite time BO algorithm based on Rollout is proposed and tested on Gaussian Process realizations and four classical test functions. Empirical results suggest that the Rollout outperforms the considered state-of-the-art one-step-look-ahead criteria on GPs with fixed covariance parameters, while on test functions results are more mitigated and further highlight the importance of adequately choosing the Rollout horizon and discount factor. 
I enjoyed this paper where an effort has been made to transfer a relevant formalism and an appropriate technique from the world of Operations Research and Dynamic Programming to Bayesian Optimization. While this was partly done in previous work here it it seems to go one step further, and I am not aware of publications where the Rollout was adapted to this precise problem. The results look promising, especially on the GP realizations, but I really felt the absence of comparison to other strategies recently proposed to adress this very issue; GLASSES of [5] seems a natural competitor here (and maybe also the MCTS of [13]). Also I was wondering if further improvements could be reachable at reasonable research investment regarding the (currently rather simple) base policies. As for the empirical comparisons on functions, the way the models are set appears a bit contrived, and the conclusions would have more weight with some experiments in more realistic conditions.  Overall, I assess this work as good and promising, but I feel that it should be seriously improved before publication. Beyond the points mentioned above here are a few additional (essentially minor) remarks along the lines: * abstract, line 5: about `uncountable', isn't it the case already in most usual sequential settings (without the finite budget issue)? * lines 23-24 after the colon: this formulation sounds unclear to me.  * line 28: `optimal' with respect to which cost? * Equation 1 (and later, e.g. in Equation 5): why should there be unicity of the maximizer? Besides, what guarantees its existence unless assumptions such as continuous f and compact X are made?  * In Equations 3-4: noise appears at a sudden. But it was not really mentioned earlier (unless I oversaw it), nor the consequences for Bayesian optimization.  * Lines 99 and 103: the set Wk first depends on zk and uk then not anymore. As formalisation is an important part of this paper, I guess it should be all the more taken care of.  * In Equation 7: shouldn't wk be upper-cased here as it is a random variable with respect to which expectation is taken? Similar questions for further quantities at stake might be relevant.  * In equation (9): where are u{k+1} and w{k+1} now?  * The beginning of the sentence in line 118 seems somehow redundant.  * In line 212 (and/or around): is h typically assumed much smaller than N?  * In 6.1: how are the GP simulated? What is the discretization? (+The software used?)