Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs
Authors: Raul Astudillo
Daniel R. Jiang
Maximilian Balandat
Eytan Bakshy
Peter I. Frazier
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian
optimization
cost
non-myopic
budgeted

Abstract: Bayesian optimization (BO) is a sample-efficient approach to optimizing costly-to-evaluate black-box functions. Most BO methods ignore how evaluation costs may vary over the optimization domain. However, these costs can be highly heterogeneous and are often unknown in advance in many practical settings, such as hyperparameter tuning of machine learning algorithms or physics-based simulation optimization. Moreover, those few existing methods that acknowledge cost heterogeneity do not naturally accommodate a budget constraint on the total evaluation cost. This combination of unknown costs and a budget constraint introduces a new dimension to the exploration-exploitation trade-off, where learning about the cost incurs a cost itself. Existing methods do not reason about the various trade-offs of this problem in a principled way, leading often to poor performance. We formalize this claim by proving that the expected improvement and the expected improvement per unit of cost, arguably the two most widely used acquisition functions in practice, can be arbitrarily inferior with respect to the optimal non-myopic policy. To overcome the shortcomings of existing approaches,  we propose the budgeted multi-step expected improvement, a non-myopic acquisition function that generalizes classical expected improvement to the setting of heterogeneous and unknown evaluation costs. We show that our acquisition function outperforms existing methods in a variety of synthetic and real problems.

Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs
Raul Astudillo Cornell University ra5980corne11 edu
Daniel R. Jiang Facebook drjiang@fb. com
Maximilian Balandat Facebook balandat@fb.com com
Eytan Bakshy Facebook ebakshy@fb.com com com
Peter I. Frazier
Cornell University
pf98@cornell. edu
Abstract
Bayesian optimization (BO) sample-efficiens approach optimizing costly-to evaluate black-box functions. Most BO methods ignore how evaluation costs may vary over the optimization domain. However, these costs can highly heteroge- neous and are often unknown in advance. This occurs in many practical settings, such as hyperparameter tuning of machine learning algorithms or physics- based simulation optimization. Moreover, those few existing methods that acknowledge cost heterogeneity do not naturally accommodate budget constraint on the total evaluation cost. This combination of unknown costs and a budget constraint intro- duces a new dimension to the exploration citiiion-xxloiiattinn trade-off, where learning about the cost incurs cost itself. Existing methods do not reason about the various trade-offs of this problem in a principled way, leading often to poor performance. We formalize this claim by proving that the expected improvement and the expected improvement per unit of cost, arguably the two most widely used acquisition func- tions in practice, can be arbitrarily inferior with respect the optimal non-myopic policy. To overcome the shortcomings of existing approaches, we propose the budgeted multi-step expected improvement, non-myopic acquisition function that generalizes classical expected improvement to the setting of heterogeneous and unknown evaluation costs. Finally, we show that our acquisition function outperforms existing methods in variety of synthetic and real problems.
1 Introduction
Bayesian optimization (BO) Shahriarii al. 2016 Frazier 2018 is family of algorithms for opti- mizing black-box functions that performs well when the number of evaluations is limited (Snok et al.) 2012 Calandra et al. 2016; Grifiths and Hernández-Lobato, 2020). However, most BO algorithms ignore the fact that the cost of evaluating the black-box objective function may vary substantially across the optimization domain and often unknown. Problems with this feature arise commonly in practice. For instance, in the context of hyperparameter optimization of machine learning algorithms (Swersky et al. 2013) Wu et al., 2020), certain values of hyperparameters such as the learning rate may yield longer training times. Similarly, in materials design and robotics, simulation experiments can take longer for certain parameter configurations (Field 1999). Figure [ Iillustrasts heterogeneity in evaluation costs from benchmark problems used in this paper, which can vary by an order of magni- tude. Failing to account for these heterogeneous evaluation costs can lead to evaluating an expensive point when another less expensive would provide equal benefit towards finding the optimum.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

0.30
0.20
0.06
dersity
dersity
0.20
0.04
0.10
0.02
0.10
0.00
0.00
0.00
10
10
15
20
2
cost (evallaaiin time)
(evalluation time)
cost (energy)
Figure 1: Evaluation times of the latent Dirichlet allocation, random forest, and energy-aware robot
pushing benchmark problems (described later in Section 5.1).
We consider budgeted BO of black-box objective function, whose evaluation costs are unknown and possibly heterogeneous across the domain. The goal is to find a point with the largest possible objective value by querying the objective function at sequence of adaptively chosen points, where the total evaluation cost is subject to a budget constraint (this cost only affects evaluation, and not point's quality upon implementation).
While some existing approaches do address heterogeneous evaluation costs, all do so heuristically, e.g. by maximizing a traditional cost- agnostic acquisition function divided by the cost of evaluation (Snoek et al., 2012 Poloezek al. 2017 Wu al., 2020 Lee et al. 2020b), by rolling out heuristic base policy (Lee et al. 2021 ). Importantly, most of these approaches accommodate neither budget constraints nor uncertainty about the cost function as part of the exploration-exploiaaiiie trade-off. As we argue theoretically and demonstrate through experiments, this can lead to poor performance. notable exception is the concurrent work Lee et al. (202I), which introduces budget-aware non-myopic acquisition function based on rollout of heuristic base policy. This work appeared while the present paper was under review.
Main Contributions. Motivated by the above shortcomings in existing work, we provide principled approach budgeted BO with unknown and potentially heterogeneous evaluation costs. Our main contributions are:
We propose a Markov decision process (MDP) formulation of the budgeted BO problem with unknown and heterogeneous evaluation costs. Our formulation allows for random time horizon (i.e., the last time before the budget depleted), going beyond the fixed-horizon MDPs formulated in existing work on non non-my BO.
Budgeted multi-step expected improvement that generalizes classical expected improvement to the budgeted hostrhetrrggeeouu setting. B B-MS-ER EI can be seen as principled approximation of the optimal policy of our MDP.
-E), novel look-ahead acquisition function
We prove that expected improvement (EI) and its nost-normalized variant, two popular existing approaches, can be arbitrarily inferior with respect to the optimal non-myopic policy.
An empirical evaluation on a number of synthetic and real-world experiments demonstrates that B B-MS-EI performs favorably with respect to other acquisition functions that are widely-used in settings with heterogeneous costs.
The remainder of this work is organized as follows: Section 2 we review related work. Our problem setup is formalized in Section In Section 4 we introduce B-MS-EI and discuss its efficient maximization via one-shot multi-step Monte Carlo trees. Numerical experiments are presented in Section 5 Finally, discuss directions of future work and conclude in Section
2 Related Work
Our work falls within the BO framework (Frazier 2018), whose origins date back to the seminal work of Kushner (1964). BO has been successful in wide range of applications, such as hyperparameter
tuning of machine learning algorithms (Snoek et al. 2012 Wu et al. (020), materials design (Zhang
al. 2020), drug discovery (Griffiths and Bermandez-Lobato Lobato 2020). and robot locomotion (Calandra
et al.
2016 Wang and Jegelka (017)).
Within the BO literature, the works most closely related to ours are those that acknowledge the existence of costs for evaluating the objective function that are heterogeneous across the search space and aim to devise algorithms that are cost-aware. Much of this work has occurred in the multi multi-fidelity

---

setting (Swersky et al. 2013: Kandasamy et al., 2016 2017 Poloczek et al. 2017 Song et al. 2019
Wu et al., 2020). . I.e., where cheaper approximations of the objective function are available. The only exceptions known to us are [Snoek et al. (2012), Lee et al. (2020b), Ledeee
Lee et al. (022)) which
consider the single-fidelity setting.
Snoek et al. 2012) proposes the expected improvement per unit of cost (EI-PUC), i.e, El(x)/c(a)) where c(x) is the cost of evaluating the objective at and El(x) is the expected improvement. Lee et al. (2020b) proposes a simple variation called the expected improvement per unit of cost with cost cooling (EI-PUC-CC). EL-PUC-CC is defined by Hl(z)/c(z)". where V the ratio between the current remaining and initial budgets. The intuition behind the cost exponent is that evaluating points with high cost should be discouraged early in the BO loop (when V = 1) and accommodated as the budget is consumed and y/ decreases to O. However, neither EI-PUC nor EI-PUC-CC consider uncertainty in the cost or measure the budget-dependent value of information in principled way.
Work concurrent to ours, Lee et al. 2021), also tackles budgeted BO with heterogeneous costs using non-myopic strategy. However, our work differs in both the model and solution method. [Lee] iet al. (2021) uses a finite-horizon constrained MDP, while our model is an MDP with a random horizon. We argue that the random horizon formulation is more natural: the formulation of Le et al. (22T requires the addition of a zero reward, zero cost state to accommodate trajectories with a small number of evaluations. Within this formulation, Lee et al. (202T) proposes a rollout acquisition function with a particular heuristic base policy: h- 1 steps of EI-PUC followed by a last step of EI, where h the number of look-ahead steps performed. The acquisition function essentially single step of policy improvement over the "FI-PUC followed by El" heuristic (Sutton and Barto 2018). In contrast, our acquisition function aims to directly approximate the optimal policy.
The approach of dividing a cost-agnostic acquisition function by some cost term is widely used in practice for addressing heterogeneity in costs, and is closely related to the use of "value divided by cost" in knapsack problems (Badanidiyuru et al., 2013). In the knapsack problem, one selects items to include into knapsack constraint on the sum of the items' costs. In this setting, myopically adding items to the knapsack that maximize value divided by cost has strong theoretical guarantees: this algorithm provides at least 1/2 the optimal value (Williamson and Shmoys, 201I). However, this theoretical guarantee relies on the additive nature of value in the knapsack problem. contrast, in BO, the value obtained from multiple evaluations is the maximum of the values of the evaluations, not their sum. Indeed, we show that in this setting the "value divided by cost" approach can perform arbitrarily worse than the optimal policy.
maximize the sum of the selected items' values subject to a budget
Heterogeneous evaluation costs have also been considered in the multi-armed bandits literature (Badanidiyuru al. 2013 Xia et al., 2015 2016). These works develop algorithms based on optimistic policies that maximize some form of reward-to-cost ratio. As mentioned above, this type of policy sensible when the measure of performance is the cumulative regret but is not appropriate in an optimization or "best-arm identification" " setting.
Our work is also closely related to non non-myopic BO (Gonzalez et al., 2016 Lam al. 2016 Yue and
Kontar 2020; Jiang et al.) 2020a Lee et al. 2020a Jiang et al. [0200b] Lee et al. (021). a class of
acquisition functions that account for future evaluations when quantifying point's s acquisition value.
To the best of our knowledge, the work of Lee et al. (202T) discussed above is the only one among these that able to handle heterogeneous evaluation costs.
3 Budgeted Bayesian Optimization with Unknown Evaluation Costs
We now formally state the problem of budgeted BO with unknown evaluation costs. Given compact optimization domain X C IRd, our goal is to find a point I E X with the largest possible objective value by querying the black-box objective function, f X + IR at sequence of points {z; ) subject to the constraint Ein c(x;)= < B, where c(x) is the cost of evaluating f at æ and B is the evaluation budget. The cost observation c(z) is revealed immediately after the evaluation of f(x) is performed. However, the actual cost function c is unknown. As is typical in BO, we endow f and c with joint prior distribution, p. An observation in our setting is triple (I,, yi, 24) E X x R x Ryo.
1 'This expression is for the case when c(x) is known. When c(x) is unknown and learned, then either the expectation is taken over the distribution of improvement to cost ratios (as we do in our experiments) or the denominator is replaced by the mean cost.
3

---

where ys is an observation of the objective of at T3, and 24 is an observation of the cost for evaluating at Z4.
3.1 MDP Formulation
The state of our MDP at step n is 2n, defined as the set of observations so far. These sets are defined recursively by D,, Dn (æn, Un. 2n) for 2 1, where Do is a set of initial observations. The joint posterior distribution over f and c given D,, is denoted by p(- Dn)). The utility generated by particular state D, is defined the maximum observed objective value u u(D,). max(x.9 y- Note that this utility function encodes the fact that after evaluation, a point with maximum objective value is desired regardless of its cost. We also let sDD,) Σ (a.,.))D denote the total cost of observed points in D,.-
The sets of observations D1, D2....... ...... are random due to the yet unobserved values of the objective and cost functions. A policy to points in X, so that Ią = T (D Given a set of observations D such that sD) < B (i.e., there is nonnegative remaining budget), the value function of policy is defined as V=(D) ET (u(DNg)= u(Do) Do = D]. where the random stopping time Ng sup(k s(P)) S B} is the largest time step & for which the budget constraint is still satisfied. The notation [=[-] indicates an expectation taken over sequences of observation sets D1, D2...., DN, selected by policy æ.
{ (T ) is sequence of functions, each mapping sets of observations
For set DD where s(D) > B (i.e., budget is exhausted), we define (DD O. Our goal is to find a policy π that maximizes the increase in expected utility:
V*(D)= = sup V VT(D),
sell
where IT is the set of all possible policies. The above problem is well-defined provided that NB < oo for all policies æ. This is the case, for example, when In follows a Gaussian process (GP) prior, modeling choice that we make in our numerical experiments. Since the horizon Ng is random, the formulation (I) can be viewed as stochastic shortest path problem, rather than a standard finite or discounted infinite horizon dynamic program (Bertsekas and Tsitsiklis) [991). Note that at time k. the set Dj contains all past observed costs and fully captures the remaining budget. This formulation is capable of the following:
1. Through multi-step planning, it can navigate the trade-off of how sequence high-cost and low-cost evaluations in order to make the best use of the given budget.
2. It can reason about uncertainty when planning optimal cost-learning. For example, an ex- ploratory evaluation may be worthwhile in region with moderate estimated cost and high model uncertainty: the evaluation may reveal the cost is lower than estimated, allowing us to explore the region more fully for low cost.
3.2 Contrast with Value-to-Cost Ratio Methods
is not surprising that cost-agnostic methods, such expected improvement (EI), can perform poorly when the evaluation cost is heterogeneous. In particular, ignoring cost can lead to evaluating exces- sively high-cost points, depleting budget and limiting future evaluations. In an attempt to avoid this. past work has focused on using value-to-cost ratio (Snock et al. 2012)] Swersky et al. 2013 Kan
dasamy et al. 2016 2017 Poloczek et al. 2017 Song et al. 2019: Wu al. 2020 Lee et al. (020b).
We show here, however, that value-to-cost acquisition functions exhibit a complementary kind of undesirable behavior: they may repeatedly measure excessively low-cost points that are also low- value, leading to poor overall performance. In fact, the performance can be arbitrarily bad compared with an optimal policy. Theorem [ demonstrates this formally for the most widely-used of these policies: measuring at the point that maximizes the expected improvement per unit of cost (EI-PUC), and also for cost-agnostic expected improvement (EI).
Theorem 1. The approximation ratios provided by the El and EI-PUC policies are unbounded. That is. for any arbitrarily large p >> 0 and each policy π E (EI, EI-PUC), there exists a Bayesian optimization problem instance (a prior probability distribution over objective and cost functions, budget, and a set of initial observations Do) where V*(D)) > pV (Do).
Sketch of Proof. To show that EI-PUC has an unbounded approximation ratio, the detailed proof of Theorem I provideed in Section of the supplementary material) constructs problem instance

---

with prior that is independent across a discrete domain with a known cost function. There are two kinds of points: high-cost points with large prior variance; and low-cost points with low variance. To support analysis, all points have the same mean.
The variance of the low-cost points is low enough that spending the entire budget on evaluating them earns only fraction of the value, in expectation, earned by evaluating a single high cost point. The acquisition function EI-PUC, however, does not understand this. Its greedy nature leads it to overvalue these points. Indeed, El (the numerator of EI-PUC's acquisition function) greedily values improvement relative to the status quo, even though the status quo will likely be surpassed by other later evaluations. This overvalues small improvements like those that result from low- ww-variance points.
EI-PUC spends its entire budget on these low-cost low-variance points, earning almost value. In contrast, the optimal policy spends its entire budget on a single evaluation of the high-cost point, obtaining substantially more value in expectation.
For the case of EI, we construct similar example, with the change that the low-cost points now have variance only slightly smaller than that of the high-cost points, while still being significantly cheaper. Here, El performs a single evaluation the high-cost point and runs out of budget. On the other hand, repeatedly measuring low-cost points is far superior to EI in expectation.
Figure 2 iillustaatss this phenomenon in continuous one-dimensional setting with a Gaussian process prior. Under the posterior in the first time slice, there is a lower-cost region on the left (æ < 0.5) with low-variance and mean that is significantly below the best point observed. There is higher-cost region on the right (æ >> 0.5) where the mean and variance are both larger. These means and variances such that the global maximum of the function is likely be in the right-hand region. In its first two measurements, the EI-PUC strategy measures at two low-cost points, which results in reduction of variance in this region but (as expected) no values that contend with the likely value of the global maximum on the right. In contrast, in its first two measurements, our multi-step B-MS-EI strategy evaluates the right, finding values that are close the global optimum.
In this example, EI-PUC encounters the same difficulty it faces in the proof of Theorem 1 ues low-cost points that improve relative to the status quo but not relative to where we hope to be near the end of the budget. While some budget remains to evaluate on the right after these evaluations, the evaluations on the left are likely unproductive toward the goal of finding global maximum.
It overval-
3.3 Decomposition and Truncation
We now discuss how we can additively decompose and then truncate the problem in T so that is more amenable as BO acquisition function. Let r(D,-1, D..) =(D,,) uu(,,-1) be the increase in utility between successive states. Using telescoping sum and rewriting the summation as an infinite sum, we have
x Σ ===1
VD(D) = sup Ex nell
r(Dn-1,Da) (ngNn) Do =
(2)
truncated version of (2) that is useful within our scenario tree optimization approach described in Section 4.2 is given by
N r r(D,-1, Dx) (m Do = D
Vv (D) = sup E" TET
Σ
where N is a fixed number of "look-ahead steps." When for each e drawn from the prior, there exists lower bound on e(x) over X that [1) is well-defined, it follows that the truncation becomes more accurate when N becomes large: lim +00 VN = (D). This serves as the motivation for our acquisition function described below.
Budgeted Multi-Step Expected Improvement
We now derive the budgeted multi-step expected improvement (B (B-MS-EI) acquisition function, where the main idea to solve the truncated problem given (3) Accordingly, the acquisition function is parameterized by N, the maximum number of look-ahead steps. In Section 4.2
5

---

2.0
ougetiid functinn
ostirum
2.0
latest absenee volue
2.0
latst ussereed wile
poste oo Fron onserved val-es
1.0
1.0
1.0
0.0
0.0
0.2
0.4
3.6
0.8
1.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
cost findtion
roma ning budjet
romaiiiny ning budget lstest abservee ue
remath no budget
istest obserwed volue
postector meen
21-UC
C-P.C
0.00
opsmum
0.08
rot
0.08
rpt mum
BIPUCC
BIPAUCC
0.06
0.06
0.06
0.04
0.04
0.04
(a) EI-PUC
2.0
not mum
eijective Ranction
2.9
latest abserved value
lstest coserved value
pouss oor mhou uoxd rid valuta
1.0
1.0
1.0
0.5
0.9
0.2
0.4
0.8
1.0
0.0
0.0
0.2
0.4
0.8
1.0
0.0
0.0
0.2
0.4
0.8
1.0
cost fandtion
roma ming budget
remal ning pudpet
rumaih budge:
lalos) obser wod value
lalast obuerved va
pooto or mean obsceved uus
96% CI
0.4
0.6
B-S-E E m0/mum
BMS-21
BIS-21
oot mun
oct mum
0.20
0.20
0.20
0.30
0.10
0.30
0.25
0.05
0.05
B-MS-EI
The top six panels show the EI-PUC strategy and the bottom six show our B-MS-B strategy. In each group, the top and middle rows show the posterior on the objective and cost, respectively, and the bottom right, where the first column shows the initial posteriors, and the second and third columns show the posteriors after and two evaluations. EI-PUC evaluates low-variance, low-mean points that low-cost but unlikely to reveal values near the global optimum. In contrast, B-MS-EI discovers a point near this global optimum within budget after two evaluations. While the remaining budget of EI-PUC after two evaluations is still relatively large, we include additional plots in Section[Goo the supplementary material showing that indeed B-MS-EI achieves better objective value within budget.
Figure 2:
shows the implied acquisition function. Time moves from left to

---

discuss how to approximately optimize this acquisition function using scenario tree, leveraging the technique developed Jiang et al. (2020b). and Section 4.3 we discuss how the budget that defines our acquisition function when the actual remaining budget is too large to be meaningfully taken into account by computationally feasible number of look- steps.
4.1 Dynamic Programming the Truncated Problem
Our derivation of B-MS-EJ starts with applying Bellman recursion to (3) To this end, we define the one-step marginal value of a measurement at point æ given an arbitrary set of observations DD (i.e., state-action value function, or Q-function) to be
Q1 D) = Ey.s [r, DU {(2, y, 2) (G()) = Ey, [(v - u(D) (s(D))=an)
Proposition [ below shows that, when and In e are drawn from independent GPs. Qi admits an analytic expression similar to the one of constrained expected improvement (Schonlau al. 1998
Gardner et al. 2014). The proof of this result can be found in Section B of the supplementary material.
Proposition 1. Suppose that f and In follow independent Gaussian process prior distributions and that D is an arbitrary set of observations. Define ( = E[f(x) D). (b = ElIn c(x) D)
of (x) = [ar DD]22, and D (x) Var[ln c(x) [D] Then,
Q1(z D) = =EI D) (() 1 (x(D)BB)
where EI the classical expected improvement computed with respect to f. 5 (In (B s(D)) u (x)) (x), and is the standard normal edf.
In contrast with homogeneous-cost non myopic formulations, the indicator 1 (s truncates our reward sequence at the random time before the budget is first depleted. Analogously. we can define the nt-teep value function evaluated at æ, Qu (z DD), as the expected difference in utility after using the optimal policy evaluate additional points, among which r is the first of them. Using the Bellman recursion, one can write Qn, (D) as
Qn D) Q1(x D) + By, max Qn- (æ) (DU ( ((x,,,,))) v,)))) LEE
which holds for all n. Our acquisition function B-MS- EI is defined as QN. meaning that at every step our sampling policy evaluates 2n+1 argmax QN(x) D,)).
4.2 Optimizing B-MS-EI via Budgeted One-Shot Multi-Step Trees
Maximizing our acquisition function challenging as, in principle, this requires nested stochastic optimization over continuous domain. We build upon the multi-step scenario tree approach of Jiang et al. (2020b) and devise an optimization method based on sample average approximation of max QN(a (ar D.). In our approach, each scenario is associated with its own decision variable, allowing the problem to be cast as a single deterministic optimization problem over higher- dimensional domain instead of sequence of nested stochastic optimization problems. We tackle the digher-dimensional problem using modern tools of automatic differentiation and batched linear algebra operations (Balandat et al. 2020). We begin by noting that, if we apply Bellman's 's recursion repeatedly, QN can be rewritten as
QN (a D) = Q (x D) + Ey
max ( Q1 (x2 Di) + Ey max Q (Ia D2) + +... }1}] 22
23
Now consider the Monte Carlo approximation of (N (D) given by (x
mi Σ J1
}}}
(x(x +
max Q
D(')
+
Σ
max
(
(x I
mi
m2
L
da
where m,, i= 1,..,, N 1, is the number of samples used in step i, and the sets of observations ( (z, wa" x²")} and
are defined recursively by the equations D DU
Di D. b1 U ( y "en"i,zf-" zf:-))))
7

---

Figure 3: An illustration of the scenario tree representa- tion of our acquisition function for N 5 stages, where (m), 122, Ma, m4) ) = (4, 2, 2, 1). Some paths down the tree stop accumulating value earlier than others due to the budget being exhausted, i.c., when s(D/...+ (ending in red circle nodes). Other paths may terminate due to the maximum look-ahead N before the budget exhausted (ending in black square nodes), representing some approximation error due to the truncation.
N
S. Ni
Cr Nir
B
with fantasy samples (i.e., samples drawn from the model) (oii _ - Ji-1 D D obtained via the reparametrization trick" Kingma and Welling, 2013
pl
Wil
son et al. 2018).
4.3 Budget Scheduling via Rollout of Base Sampling Policy
Let B, BB zi be the remaining budget at time n. Since the number of look-ahead steps, N, that can be performed in practice is relatively small due to computational limits, B, may be too large to be taken into account by our acquisition function in meaningful way, especially during the first few evaluations (if the remaining budget is too large relative to the number of look look-ahead steps, then the evaluation costs have little effect in our sampling decisions). Therefore, instead of using the actual remaining budget at step n, our acquisition function uses a fantasy budget set by a heuristic rule.
We propose heuristic budgeting rule based on the use of a base sampling policy that can be computed quickly. We fantasize N sequential evaluations under this base sampling policy. More specifically, for each of the N steps, we draw fantasy objective and cost values at the point recommended by this policy using the (joint) posterior distribution, then we update the posterior distribution by incorporating these fantasy evaluations, and repeat. The sum of the resulting N fantasy costs determines cumulative cost incurred by the base sampling policy. Our acquisition function then sets the budget to be the minimum between this cumulative cost and the true remaining budget. This budget is used by our method as if it were the actual budget until depletion, and then the heuristic rule is used again to compute new fantasy budget. The intuition behind this heuristic is that acquisition function will try to find the best non-myopic decision using the same budget as the base sampling policy, and thus should perform evaluations that better at least as good those of the base sampling policy. In our experiments, we use EI-PUC-CC as the base policy.
5 Experiments
We demonstrate the efficacy of B-MS-EI on four synthetic and four real-world experiments. We report the performance of two variants of our acquisition function, the main variant that uses multiple fantasy samples per step, and the multi-step puth variant (Jiang et al., 2020b), which based on a degenerate tree with one fantasy sample per step. For each of these variants, we consider both N = 2 and = 4 look-ahead steps. We denote the multi-step path variant with N steps as N-B-MS-EI, and the former simply as N-B-MS-EI.
In addition, we report the performance of three baseline acquisition functions from the literature: expected improvement (EI), expected improvement per unit of cost (EI-PUC) (Snock et al. 2012, Lec al. 2020b). and expected improvement per unit of cost with cost cooling (EI-PUC-CC) (Lee et al.
2020b). EU-PUC and EI-PUC-CC are currently the de-facto standard approach to cost-aware BO. Since Lee et al. (2000b) assumes that the cost known (while our experiments are run in the setting of unknown costs), we also integrate with respect to the uncertainty on the cost when computing
NNote that since employ Monte Carlo sampling to approximate Q D.)). the independence assump- tion between and e Proposition is not necessary for our approach, and one can jointly model f and e (e.g. with a multi-task GP) if there is reason to believe that these functions are correlated, as is often the case in practice. For instance, randomness in training jobs based on variations in test train splits or weight initialization may interact with adaptive learning rate scheduling and thus affect both model performance and training time.
8

---

-0.3
dropasve
aloine
sckley
stece
-0.4
0.00
-0.5
0.8
-0.5
-0.25
-0.6
-0.50
-1.0
0.7
-1.00
-0.73
-1.5
-0.8
ELPUC
-0.9
-2.0
0.0
-1.0
-1.75
-0.2
20
40 cumulation cost
20
cUmTuletio cost
cumulativ
cumulative
ida
onn
rhoston
mintipush
-1.9
-1.37
-2.0
0.8
-211
-1.39
Frogeet
0.7
2.3
-.2
logu
-1.40
-1.0
-1.2
-1.42
-25
-1,4
-2.6
cumullatrve cost
cumulative cost
cumulaatrre cost
cumulaative cost
Figure 4: Log-regret of our non-myopic budget-aware BO method (4-B-MS-EI) compared with baseline acquisition functions on a range of problems.
these acquisition functions. Closed form analytical expressions for these acquisition functions can be found in Section Ço the supplementary material.
5.1 Description of Benchmark Problems
Synthetic Test Problems. The first four problems use synthetic objective functions commonly found in the literature: Dropwave, Alpinel, Ackley, and Shekel5 (defined in Section D of the supplementary material). Each objective function is accompanied by cost function of the form c(z) exp [ 1 (3s x; + +))]. where x² is the objective function's maximizer. In each replication we use a different cost function, obtained by sampling a, B, and 7 uniformly at random over appropriate intervals. Our results thus average over a variety of cost functions. As these parameters vary, cost functions with different characteristics arise. More concretely, a controls the magnitude of the difference between the minimum and maximum costs; /3 controls the variability of the cost; and y controls the cost at the optimum. In particular, if = O, then x" is the most expensive point, whereas if y = म,, then x² is the cheapest point. This family of cost functions emulates a wide range of possible scenarios.
AutoML Benchmarks. We consider three AutoMI. benchmark problems: LDA, CNN, and RF- Boston. The LDA and CNN problems use publicly available data sets from the HPOLib (The HPOlib authors 2014) and HPOLibl.5 (The HPOlibI.5 authors (017) hyperparameter optimization libraries. Following Eggensperger et al. (2088), we use surrogates of the underlying objective and cost functions to emulate the computationally ly expensive process of training the corresponding models. Details on the construction of the surrogates can be found in Section E of the supplementary material.
The first data set, originally introduced by Hoffman al. (200)), was obtained by evaluating an online latent Dirichlet allocation algorithm for topic modeling with 3 hyperparameters: mini-batch size S [1, 16384) (on a log2 scale), and learning rate parameters E [0.5, 1.0) (controls speed at which information is forgotten) and To E [1, 1024] (on a log2 scale, downweights early iterations). These evaluations are expensive and heterogeneous, ranging from 10 hours each (see Figure I
The second data set was obtained by training a 3-layer convolutional neural network on the CIFAR-10 dataset with 5 hyperparameters: "initial learning rate" e [10-5 1.0] (on logl0 scale), "batch size" E [32, 512], and "number of units in layer k²" E [16, 256] (on a log2 scale), for = 3,2,3. T
Finally, the RF- RF-Boston problem considers optimization of the 5-fold cross validation error when using random forest (RF) regressor on the Boston dataset, both of which are from sklearn (Pedregosa et al. 2011). We tune the following hyperparameters of the RF regressor: "n_estimators" " E [5,66] (rounded to the nearest integer), "max_ "eaxx_"ephh" [1, 64] (rounded to nearest integer), and "max features""" [0.1, (on log10 scale). The cost of each is evaluation is proportional to the
9

---

training time of the model under the evaluated set of hyperparameters (we scale it by training time of a single initial evaluation).
Energy-Aware Robot Pushing, We consider a version of the robot pushing problem introduced by Wang and Jegelka 2017), where robot pushes an object from its origin, Winit (0,0), to target Wtanget E I In the our version, we draw 20 different target locations uniformly at random over {(W1, W22 E R2 : 1 < |w1,, |wyl < 5}. which are distributed equally across the replications performed. The parameters to be optimized are the location of the robot, E [-5,5] and the duration of the push, t E [1. 30]. The objective to minimize is the distance from the object's location after being pushed, Wpush( f), and the target location, i.e., [(2, I) Wrarget Wpuush (z, ()]l2. The
cost function is given by c(z, 1) = |[upussh (2, I) + where e is a constant, and represents the energy spent by the robot by pushing the object.
5.2 Results and Discussion
Figure plots a 95% confidence interval on mean log-regret versus the budget used thus far. We perform experiments using single budget in each problem; the goal is to minimize regret at the point when the budget is fully exhausted at the right-hand edge of each plot. To focus attention on these budgets,
plot results over the range from 20% to 100% of this overall budget. The results for N = 2 look-ahead steps are deferred Section Gito the supplementary material to improve readability and also because they are outperformed by the N 4 counterparts for most problems. All implementations use BoTorch (Balandat et al. 2020). The objective and log-cost functions are modeled using independent GPs. Additional details and runtimes also be found in Section Go the supplementary material. An implementation of our algorithms and numerical experiments can be found at sattps://githnn
B-MS-EI (red and purple lines) performs favorably compared to existing methods. In some cases (Dropwave and CNN) EI performs worst, while in other cases (Alpine, Shekel, LDA), one of the value- to-cost ratio methods (EI-PUC or EI-PUC-CC) performs worst. B-MS-E: MISSEEIIA is more computationally intensive optimize than the standard approaches. The average walltime per acquisition of 4-B- MS-EI, the most expensive variant of our algorithm, ranges from 42 seconds to 7 minutes across the problems, whereas the average walltimes for EI, EI-PUC, and EI-PUC-CC, range from 1 to 30 seconds. However, optimization times on the order of minute are acceptable when the acquisition function is applied to real-world problems where the function evaluation often takes much longer (c.g., in Figure | LDA evaluations require up to 10 hours). In such settings, extra computational time spent optimizing the acquisition function more than pays for itself with improved query efficiency and the savings in objective function evaluation time that results. Nevertheless, there are opportunities to reduce the computational requirements of B-MS-EI; possibilities include re-using the optimized tree for multiple steps or devising better initial conditions for optimization. We leave these for future work.
6 Conclusion
We introduced the problem of budgeted BO under unknown and potentially heterogeneous evaluation costs. This arises in a wide range of practical settings where BO is applied. However, the most common paradigm for cost-aware BO, the value-to-cost ratio, fails account for uncertainty in the cost function as well as the presence of the budget constraint as part of the trade-off in principled way, we show in Theorem 1. In this work, we provided dynamic pro- gramming formulation of this problem, along with non-myopic acquisition function that addresses the shortcomings of the existing methods. Our acquisition function is derived by truncating the aforementioned dynamic program, and is approximately maximized following a one-shot multi-step tree approach. Our experiments show that our acquisition function outperforms existing methods on a number of synthetic and real-world examples that exhibit heterogeneity in evaluation costs. In the future, we hope to extend our approach the multi-fidelity setting, where evaluation costs play an even larger role.
These times are not unusual for advanced BO methods; see, e.g., Section 4 of Wu and Frazier 2019
10

---

Acknowledgments
Authors RA and PF were partially supported by AFOSR FA9550-19-1-0283 and FA9550-20-1-0351.
References
Badanidiyuru, A., Kleinberg, R., and Slivkins, A. (2013). Bandits with knapsacks. In 2013 IEEE 54th Anmual Symposium on Foundations of Computer Science, pages 207-216. IEEE.
Balandat, M., Karrer, B.. Jiang. D., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E. (2020). Botorch: A framework for efficient monte-carlo bayesian optimization. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 21524-21538, Curran Associates, Inc.
Bertsekas, D. P. and Tsitsiklis, J. N. (1991). An analysis of stochastic shortest path problems. Mathematics of Operations Research, 16(3):580-595.
Calandra, R., Seyfarth, A., Peters, J., and Deisenroth, M. P. (2016). Bayesian optimization for learning gaits under uncertainty. Annals of Mathematics and Artificial Intelligence, 76(1):5-23,
Eggensperger, K., Lindauer, M., Hoos, H. H., Hutter, F., and Leyton-Browe Brown, K. (2018). Effi cient benchmarking of algorithm configurators via model-based surrogates. Machine Learning, 107(1):15-41.
Field, M. J. (1999). A practical introduction to the simulation of molecular systems. Cambridge University Press.
Frazier, P. I. (2018). A tutorial on Bayesian optimization. arXiv preprint arXiv: A.Xiv:807.0081111
Gardner, J., Kusner, M., Xu, Z., Weinberger. K., and Cunningham, J. (2014). Bayesian optimiza- tion with inequality constraints. In Xing. E. P. and Jebara, T., editors, Proceedings of the 31st International Conference Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 937-945, Bejing, China. PMLR.
Gonzalez, Osborne, M., and Lawrence, (2016). GLASSES: Relieving the myopia of Bayesian optimisation. In Gretton, A. and Robert, C. C., editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statisties, volume 51 of Proceedings of Machine Learning Research, pages 790-799, Cadiz, Spain. PMLR.
Griffiths, R.-R. and Hernández-Lobato, J. M. (2020). Constrained Bayesian optimization for automatic chemical design using variational autoencoders. Chemical science, 11(2):777-866
Hoffman, M., Bach, F., and Blei, D. (2010). Online learning for latent Dirichlet allocation. In Lafferty, J., Williams, C., ShaworTaylor, J., Zemel, R., and Culotta, A., editors, Advances Neural Information Processing Systems, volume 23, pages 156-864. Curran Associates, Inc
Jiang, S.. Chai, H., Gonzalez, J., and Garnett, R. (2020a), BINOCULARS for efficient, nonmyopic sequential experimental design. In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4794 4803. PMLR.
Jiang, S., Jiang, D., Balandat, M., Karrer, B., Gardner, J., and Garnett, R. (2020b). Efficient nonmyopic Bayesian optimization via one-shot multi-step trees. Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 18039-18049 Curran Associates, Inc.
Kandasamy, K., Dasarathy, G., Oliva, B., Schneider, J., and Poezos, B. (2016). Gaussian process bandit optimisation with multi-fidelity evaluations. In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I,, and Garnett, R., editors, Advances Neural Information Processing Systems, volume 29, pages 992-1000. Curran Associates, Inc.

---

Kandasamy, K., Dasarathy, G., Schneider. J., and Póczos, B. (2017). Multi Multi-fidelity Bayesian optimisation with continuous approximations. In Precup. D. and Teh, Y. W., editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1799-1808. PMLR.
Kingma, D. and Welling, M. (2013). Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114
Kushner, H. J. (1964), A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of Basic Engineering, 86(1):97-106.
Lam, R., Willcox, K., and Wolpert, D. H. (2016). Bayesian optimization with finite budget: An approximate dynamic programming approach. In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 29, pages 883-891. Curran Associates, Inc.
Lee, E., Eriksson, D., Bindel, D., Cheng, B., and Mccourt, M. (2020a). Efficient rollout strategies for Bayesian optimization. In Peters, J. and Sontag, D., editors, Proceedings of the 36th Conference Uncertainty in Artificial Intelligence, volume 124 of Proceedings of Machine Learning Research, pages 260-269. PMLR.
Lee, E. H., Eriksson, D., Perrone, V., and Seeger, M. (2021). A nonmyopic approach to cost- constrained Bayesian optimization. Conference on Uncertainty in Artificial Intelligence.
Lee, E. H., Perrone, V., Archambeau, C., and Seeger, M. (2020b). Cost-aware bayesian optimization. arXiv preprint wixxi:0003.10870
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Édouard Duchesnay (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 2285522285..883.
Poloczek, M., Wang, J., and Frazier, P. I. (2017). Multi-information source optimization. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems, pages 4289-4299 Curran Associates, Inc.
Schonlau, M., Welch, W. J., and Jones, D. R. (1998). Global versus local search in constrained optimization of computer models. Lecture Notes-Monograph Series, 34:1 1--2..
Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and de Freitas, N. (2016). Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1):148-175.
Snoek, J., Larochelle, H., and Adams, P. (2012). Practical Bayesian optimization of machine learn- ing algorithms. In Pereira, F., Burges, J. C., Bottou, I.., and Weinberger, K. Q. editors, Advances in Neural Information Processing Systems, volume 25, pages 2951-2955 Curran Associates, Inc
Song, J., Chen, Y., and Yue, Y. (2019). general framework for multi multi-fidelity Bayesian optimization with Gaussian processes. In Chaudhuri, K. and Sugiyama. M.. editors, Proceedings of the Twenty- Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 3158-3167 PMLR.
Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
Swersky, K., Snoek, J., and Adams, R. P. (2013). Multi-task Bayesian optimization. In Burges, C. C., Bottou, L., Welling. M., Ghahramani. Z., and Weinberger, K. Q. editors, Advances in Neural Information Processing Systems, volume 26, pages 2004-2012, Curran Associates, Inc
The HPOlib authors (2014). HPOlib. Available at: /tttps///ithhbb comub...om/aaaa httpbb/ooo/uuttom/H/ooee
The HP authors (2017). HPOlib1.5. Available at: https://github.coo com/ www../////aama/coooooooooo..oo.e automl/ HPO11b1.5
Wang, Z. and Jegelka, S. (2017). Max-value entropy search for efficient Bayesian optimization. In
Precup, and Teh, Y. W., editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3627-3635. PMLR.
12

---

Williamson, D. P. and Shmoys, D. B. (2011). The design of approximation algorithms. Cambridge university press.
Wilson, J., Hutter, F,, and Deisenroth, M. (2018). Maximizing acquisition functions for Bayesian optimization. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31, pages 9884-9895. Curran Associates, Inc.
Wu, J. and Frazier, P. (2019). Practical two-step lookahead Bayesian optimization. In Wallach, H., Larochelle, H., Beygelzimer, A., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32, pages 9813-9823. Curran Associates, Inc.
Wu, J., Toscano-Palmerrnn S., Frazier, and Wilson, A. (2020). Practical multi-fidelity Bayesian optimization for hyperparameter tuning. In Adams, R. P. and Gogate, V., editors. Proceedings of The 35th Uncertainty Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 788-798. PMLR.
Xia, Y., Ding, W., Zhang, X.-D., Yu, N., and Qin, T. (2016). Budgeted bandit problems with continuous random costs, In Holmes, and Liu, T.-Y., editors, Asian Conference on Machine Learning, volume 45 of Proceedings of Machine Learning Research, pages 317-332, Hong Kong. PMLR.
Xia, Y., Li, H., Qin, Yu, N., and Liu, T.-.. (2015). Thompson sampling for budgeted multi-armed bandits. In Proceedings of the 24th International Joint Conference Artificial Intelligence, pages 3960-3966.
Yue, X. and Kontar, R. A. (2020). Why non-myopic Bayesian optimization is promising and how far should we look-ahead? A study via rollout. In Chiappa, S. and Calandra, R., editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2808 28188 PMLR.
Zhang, Y., Apley, D. W., and Chen, W. (2020). Bayesian optimization for materials design with mixed quantitative and qualitative variables. Scientific reports, 10(1):1-13.
13


Reviews:
[{"review_id": "pGh9-P8oGTJ", "reviewer": "Reviewer_eGMU", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed algorithm is theoretically sound. The experiments are sufficient and the results are promising. \n\nDetailed comments:\n1.\tHow 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.\n\n2.\tIn 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.\n\n3.\tI 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. \n\n4.\tI am a bit confused with the intuition of Theorem 1. Specifically, when $0 < \\alpha \\leq 1$, what is our takeaway from this Theorem?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "CSeAghOH4Yw", "reviewer": "Reviewer_spuC", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nPros\n\n+ Interesting topic.\n+ Well-organized paper.\n+ Novel proposed algorithm.\n\nCons\n\n- Some missing details.\n- Weak numerical experiments.\n\nDetailed Comments\n\n1. I would like to see the intuitive explanation of the equation shown in Line 207 (Please add a counter for all equations).\n2. 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.\n3. 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.\n4. 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.\n5. How many times did you repeat each experiment? I cannot find it in the paper.\n\nMinor issues\n\n* In Line 46, nonmyopic -> non-myopic.\n* In Line 96, $\\sum_{i = 1}^n c(x_n)$ -> $\\sum_{i = 1}^n c(x_i)$.\n* In Line 256, Fig 4 -> Fig. 4.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not have any comments on limitations and societal impact. Please see \"Main Review\" for the detailed reviews.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "9bjiUaJVbKX", "reviewer": "Reviewer_tCi1", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThat being said, there are a couple of places that can be further improved to make this paper stronger and help readability.\n\n1, 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?\n\n2, 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.\n\n3, 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. \n\n4, 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?\n\n5, 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.\n\n6, In section 4, it seems to me all the \"value functions\" actually mean Q functions. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "5HglJ0LH90", "reviewer": "Reviewer_AFWF", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nPros:\n- 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.\n- 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.\n- 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.\n\nCons:\n- 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).\n- A concise description of the whole approach as an algorithm is missing from the main text.\n\nSome missing references:\n- Guinet et. al. Pareto-efficient Acquisition Functions for Cost-Aware Bayesian Optimization\n- Abdolshah et. al. Cost-aware Multi-objective Bayesian optimisation\n- Paria et. al. Cost-Aware Bayesian Optimization via Information Directed Sampling\n\nQuestions:\n- 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?\n- How sensitive is the performance to the parameters of EI-PUC-CC? Were these parameters fixed beforehand for all the experiments?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)