Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes a global optimization method for black-box functions, where an evaluation budget is restricted and an evaluation cost is also unknown. By applying a lookahead strategy, the authors introduce a new acquisition function, a budgeted multi-step expected improvement (B-MS-EI). It is based on a popular acquisition function, expected improvement, and it solves an optimization problem under the setting of heterogeneous and unknown evaluation costs in a non-myopic manner. Finally, the authors demonstrate that the proposed method outperforms the baseline, EI-PUC in various experimental circumstances.
main_review: This paper solves a very practical scenarios in Bayesian optimization. Most optimization problems are affected by the evaluation costs we do not often know the form of cost function. Thus, this problem setup is interesting and has not developed much yet. However, I have some concerns on the details of algorithm and numerical results. Please see the comments described below and provide a response for them in the rebuttal.

Pros

+ Interesting topic.
+ Well-organized paper.
+ Novel proposed algorithm.

Cons

- Some missing details.
- Weak numerical experiments.

Detailed Comments

1. I would like to see the intuitive explanation of the equation shown in Line 207 (Please add a counter for all equations).
2. Is there any specific way to determine the number of look-ahead steps? As described in Section 5, it is a crucial hyperparameter for the proposed acquisition function. It has to describe in detail.
3. I would like to ask quantitative results on the computational cost of B-MS-EI, compared to other baseline. As described in Section 5.4 as well as the main sections, the computational cost seems like a big burden. It needs to specify in the article.
4. The number of iterations for each Bayesian optimization round is too small; for example, the experiments described in Figure 4 attempt to find a global optimum for 10, 40, 60, or 80 iterations.
5. How many times did you repeat each experiment? I cannot find it in the paper.

Minor issues

* In Line 46, nonmyopic -> non-myopic.
* In Line 96, $\sum_{i = 1}^n c(x_n)$ -> $\sum_{i = 1}^n c(x_i)$.
* In Line 256, Fig 4 -> Fig. 4.
limitations_and_societal_impact: I do not have any comments on limitations and societal impact. Please see "Main Review" for the detailed reviews.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper aims to develop a BO approach that can handle cost heterogeneity of evaluations while having a budget constraint on the total evaluation cost. The proposed acquisition function follows the MDP setting and extends the general Expected Improvement to a budgeted cost-heterogeneous approach.
main_review: The proposed algorithm is theoretically sound. The experiments are sufficient and the results are promising. 

Detailed comments:
1.	How effective is the heuristic of budget scheduling via rollout when the modelling of cost function (and accordingly those $N$ fantasy costs) is not reasonably accurate? Let us assume that we are at the start of the optimisation (n<10) and $B_n$ is fairly large. So in that case the heuristic mainly depends on the priors that are used in the GP that models the cost function. Please elaborate on this point.

2.	In Line 218, the $\nu_N$ is written as: $\nu_N(.)=\nu_1(.)+E[..\nu_{1}]$, but I kind of missed the concept of dynamic programming here. I assumed the $\nu$ inside the expectation $E_{y,z}[.]$  should be  $\nu_{n-1}$  (given the equation in line 207). Please correct me if I am wrong. Also, it would be useful to have labels ($ \label{...}$) for these 2 equations.

3.	I assume the $\alpha$ in Theorem 1 is not related to Line 70 (the ratio between the remaining budget and the total budget). In that case, I suggest using a different notation in Theorem 1. 

4.	I am a bit confused with the intuition of Theorem 1. Specifically, when $0 < \alpha \leq 1$, what is our takeaway from this Theorem?

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an MDP-style problem formulation for budgeted cost-aware Bayesian optimization and corresponding solutions to solve it. The authors also presented empirical results showing that the proposed method works well in practice.
main_review: This is a well-written paper. The problem formulation is well thought through, quite reasonable and straightforward to understand. The proposed methods based on dynamic programing and Monte Carlo tree search only seem obvious when the problem formulation is given. The authors did a very good job introducing the problem.

That being said, there are a couple of places that can be further improved to make this paper stronger and help readability.

1, In Theorem 1, only EI related approaches are considered. Is it because EI's acquisition function value is bounded? How does this theorem work for other policies like PI, PI-PUC, UCB, UCB-PUC?

2, In Figure 2, I think it would be helpful to show the acquisition function value in (a) or the corresponding Q function in (b). Right now, it is unclear how either method makes the decision on where to evaluate. Please add this figure in the rebuttal.

3, It would be nice to point out what the reward, state and action mean for the MDP. I think there are some notations that can be improved once this question is sorted out. It seems to me D_n would be the state and x_n the action. But it's unclear to me what reward is. It doesn't seem necessary to introduce an additional D since Eq (1) can just be written as V*(D_0) = sup_\pi E_\pi [...] which also avoids the ambiguity on the variable that the expectation is taken over. Similar for the V functions following that. 

4, It would be helpful to write down what V*(D_n) is for any n \in \{1, ..., N\} in addition to just defining V*(D_0). In particular, is there an iterative update rule for V*(D_n) such that it can be computed from V*(D_{n+1})? What would the Q function be in the MDP the authors defined?

5, All the equations in Sec 3.3 look confusing to me not only because of what I mentioned above (unclear definition of V*(D_N) since only V*(D_0) was defined), but also the unnecessary notations like r_N or V_N. I don't think those equations add any clarity. Basically, if I'm understanding correctly, the authors are trying to say they do finite step look ahead but just didn't say it clearly enough. I suggest the authors reword section 3.3 and make the point clear, remove unnecessary equations and follow a concise set of equations.

6, In section 4, it seems to me all the "value functions" actually mean Q functions. 



limitations_and_societal_impact: A key limitation I didn't see mentioned is that users need to select the GP prior for objective and cost functions. Cost function's GP is also much less intuitive given it's in log space.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of limited budget Bayesian optimization when the cost of each experiment is unknown and must be estimated by running the experiment. This is an interesting problem introduced in the BO community recently. This paper improves upon previous approaches by treating the problem as a constrained MDP. At each step, the method performs a look-ahead and chooses the next point that maximizes a N-step reward within a budget constraint. The experiments show improved performance over the baselines.
main_review: This is an interesting paper providing a method to tackle Bayesian optimization with non-uniform experimental costs. Traditional BO methods treat the experimental cost as a constant for all input designs, however in practice the experimental cost may vary. Previous approaches are myopic in nature, and do not consider the remaining budget. This paper introduces a principled approach to this problem using an MDP formulation and optimize the proposed acquisition function using recently proposed multi-step trees. This approach of incorporating the cost constraints with multi-step trees seems novel. The paper is very well written and the approach is clear.

Pros:
- The problem tackled seems interesting and worthwhile to study. Traditional BO approaches do not consider the true experimental cost, although it may be relevant in certain practical scenarios.
- The approach is principled, using MDPs to model a non-myopic acquisition function, while also constraining the evaluation budget. This is an ideal way of incorporating the cost budget into the decision making process. This is in contrast to previous heuristic approaches that simply divide the original acquisition function by the cost. In particular, the connection to constrained EI looks interesting.
- Experimental results show improved performance over previous state of the art baselines. While there are a few other recently proposed baselines that take the cost into account, they do not work better that the baselines used in the paper.

Cons:
- As described in section 4.3, when the remaining budget is large, the evaluation cost does not affect the optimization. This raises a concern about the practical effectiveness of the method under a large budget (or equivalently, when each experiment incurs a small cost).
- A concise description of the whole approach as an algorithm is missing from the main text.

Some missing references:
- Guinet et. al. Pareto-efficient Acquisition Functions for Cost-Aware Bayesian Optimization
- Abdolshah et. al. Cost-aware Multi-objective Bayesian optimisation
- Paria et. al. Cost-Aware Bayesian Optimization via Information Directed Sampling

Questions:
- Consider a scenario where the budget is high, so a large number of experiments can be performed. Will standard methods (such as EI) outperform in this setting?
- How sensitive is the performance to the parameters of EI-PUC-CC? Were these parameters fixed beforehand for all the experiments?
limitations_and_societal_impact: A current limitation is the effectiveness of this method on real large scale optimization problems. The current experiments are on synthetic experiments or relatively small benchmarks. A large scale evaluation on more real world problems is necessary to understand the importance of modeling the evaluation cost in BO. Furthermore, It is understandable that the authors may leave this to future work due to huge computational requirements. However, a discussion about this may be added to the main text.
review_title: null

Meta-review: The paper studied a variant of the Bayesian optimization problem with additional twists of unknown costs and a budget constraint. All reviewers agree that the problem studied in this paper is practically relevant, the solution (based on dynamic programming and Monte Carlo tree search) is intuitive with rigorous theoretical justifications. Empirical results on several practical (both synthetic and realistic) tasks seem promising.
 
The authors provided effective feedback during the discussion phase, which helped clarify several concerns (e.g., empirical behavior under large-scale problems under a large budget constraint). The authors are encouraged to take into account the reviews, in particular, to further strengthen the empirical analysis and clarity of the presentation if possible, when preparing a revision.

Decision: Accept (Poster)