Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs
Year: 2022

Abstract:
Bayesian optimization (BO) is a sample-efficient approach to optimizing costly-toevaluate 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. 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 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. Finally, we show that our acquisition function outperforms existing methods in a variety of synthetic and real problems.

text: Bayesian optimization (BO) is a sample-efficient approach to optimizing costly-toevaluate 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. 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 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. Finally, we show that our acquisition function outperforms existing methods in a variety of synthetic and real problems.

heading: 1 Introduction
text: Bayesian optimization (BO) (Shahriari et al., 2016; Frazier, 2018) is a family of algorithms for optimizing black-box functions that performs well when the number of evaluations is limited (Snoek et al., 2012; Calandra et al., 2016; Griffiths 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 is 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 1 illustrates heterogeneity in evaluation costs from benchmark problems used in this paper, which can vary by an order of magnitude. Failing to account for these heterogeneous evaluation costs can lead to evaluating an expensive point when another less expensive one would provide equal benefit towards finding the optimum.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We consider budgeted BO of a 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 a sequence of adaptively chosen points, where the total evaluation cost is subject to a budget constraint (this cost only affects evaluation, and not a 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; Poloczek et al., 2017; Wu et al., 2020; Lee et al., 2020b), or by rolling out a 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-exploitation trade-off. As we argue theoretically and demonstrate through experiments, this can lead to poor performance. A notable exception is the concurrent work of Lee et al. (2021), which introduces a budget-aware non-myopic acquisition function based on rollout of a 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 a principled approach to 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 a random time horizon (i.e., the last time before the budget is depleted), going beyond the fixed-horizon MDPs formulated in existing work on non-myopic BO.
• Budgeted multi-step expected improvement (B-MS-EI), a novel look-ahead acquisition function that generalizes classical expected improvement to the budgeted cost-heterogeneous setting. B-MS-EI can be seen as a principled approximation of the optimal policy of our MDP.
• We prove that expected improvement (EI) and its cost-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-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: In Section 2, we review related work. Our problem setup is formalized in Section 3. 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, we discuss directions of future work and conclude in Section 6.

heading: 2 Related Work
text: 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 a wide range of applications, such as hyperparameter tuning of machine learning algorithms (Snoek et al., 2012; Wu et al., 2020), materials design (Zhang et al., 2020), drug discovery (Griffiths and Hernández-Lobato, 2020), and robot locomotion (Calandra et al., 2016; Wang and Jegelka, 2017).
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-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), and Lee et al. (2021), which consider the single-fidelity setting.
Snoek et al. (2012) proposes the expected improvement per unit of cost (EI-PUC), i.e, EI(x)/c(x)1 where c(x) is the cost of evaluating the objective at x and EI(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). EI-PUC-CC is defined by EI(x)/c(x)ν , where ν is 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 ν ≈ 1) and accommodated as the budget is consumed and ν decreases to 0. However, neither EI-PUC nor EI-PUC-CC consider uncertainty in the cost or measure the budget-dependent value of information in a principled way.
Work concurrent to ours, Lee et al. (2021), also tackles budgeted BO with heterogeneous costs using a non-myopic strategy. However, our work differs in both the model and solution method. Lee et 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 Lee et al. (2021) 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. (2021) 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 is the number of look-ahead steps performed. The acquisition function is essentially a single step of policy improvement over the “EI-PUC followed by EI” 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 a knapsack to maximize the sum of the selected items’ values subject to a budget 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, 2011). However, this theoretical guarantee relies on the additive nature of value in the knapsack problem. In 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.
Heterogeneous evaluation costs have also been considered in the multi-armed bandits literature (Badanidiyuru et 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 is 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-myopic BO (Gonzalez et al., 2016; Lam et al., 2016; Yue and Kontar, 2020; Jiang et al., 2020a; Lee et al., 2020a; Jiang et al., 2020b; Lee et al., 2021), a class of acquisition functions that account for future evaluations when quantifying a point’s acquisition value. To the best of our knowledge, the work of Lee et al. (2021) discussed above is the only one among these that is able to handle heterogeneous evaluation costs.

heading: 3 Budgeted Bayesian Optimization with Unknown Evaluation Costs
text: We now formally state the problem of budgeted BO with unknown evaluation costs. Given a compact optimization domain X ⊂ Rd, our goal is to find a point x ∈ X with the largest possible objective value by querying the black-box objective function, f : X → R, at a sequence of points {xi}ni=1, subject to the constraint ∑n i=1 c(xi) ≤ B, where c(x) is the cost of evaluating f at x and B is the evaluation budget. The cost observation c(x) 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 a joint prior distribution, p. An observation in our setting is a triple (xi, yi, zi) ∈ X× R× R>0,
1This 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.
where yi is an observation of the objective f at xi, and zi is an observation of the cost c for evaluating f at xi.

heading: 3.1 MDP Formulation
text: The state of our MDP at step n is Dn, defined as the set of observations so far. These sets are defined recursively by Dn = Dn−1 ∪ (xn, yn, zn) for n ≥ 1, where D0 is a set of initial observations. The joint posterior distribution over f and c given Dn is denoted by p(· | Dn). The utility generated by a particular state Dn is defined as the maximum observed objective value u(Dn) = max(x,y,z)∈Dn 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 s(Dn) = ∑ (x,y,z)∈Dn z denote the total cost of observed points in Dn. The sets of observations D1,D2, . . . are random due to the yet unobserved values of the objective and cost functions. A policy π = {πk}∞k=1 is a sequence of functions, each mapping sets of observations to points in X, so that xk = πk(Dk−1). Given a set of observations D such that s(D) ≤ B (i.e., there is nonnegative remaining budget), the value function of a policy π is defined as V π(D) = Eπ [ u(DNB )− u(D0) | D0 = D ] , where the random stopping time NB = sup{k : s(Dk) ≤ B} is the largest time step k for which the budget constraint is still satisfied. The notation Eπ[ · ] indicates an expectation taken over sequences of observation sets D1,D2, . . . ,DNB selected by a policy π. For a set D where s(D) > B (i.e., budget is exhausted), we define V π(D) = 0. Our goal is to find a policy π that maximizes the increase in expected utility:
V ∗(D) = sup π∈Π V π(D), (1)
where Π is the set of all possible policies. The above problem is well-defined provided that NB <∞ for all policies π. This is the case, for example, when ln c follows a Gaussian process (GP) prior, a modeling choice that we make in our numerical experiments. Since the horizon NB is random, the formulation (1) can be viewed as a stochastic shortest path problem, rather than a standard finite or discounted infinite horizon dynamic program (Bertsekas and Tsitsiklis, 1991). Note that at time k, the set Dk 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 to 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 exploratory evaluation may be worthwhile in a 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.

heading: 3.2 Contrast with Value-to-Cost Ratio Methods
text: It is not surprising that cost-agnostic methods, such as expected improvement (EI), can perform poorly when the evaluation cost is heterogeneous. In particular, ignoring cost can lead to evaluating excessively high-cost points, depleting budget and limiting future evaluations. In an attempt to avoid this, past work has focused on using a value-to-cost ratio (Snoek et al., 2012; Swersky et al., 2013; Kandasamy et al., 2016, 2017; Poloczek et al., 2017; Song et al., 2019; Wu et al., 2020; Lee et al., 2020b).
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 lowvalue, leading to poor overall performance. In fact, the performance can be arbitrarily bad compared with an optimal policy. Theorem 1 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 EI and EI-PUC policies are unbounded. That is, for any arbitrarily large ρ > 0 and each policy π ∈ {EI,EI-PUC}, there exists a Bayesian optimization problem instance (a prior probability distribution over objective and cost functions, a budget, and a set of initial observations D0) where V ∗(D0) > ρV π(D0). Sketch of Proof. To show that EI-PUC has an unbounded approximation ratio, the detailed proof of Theorem 1 (provided in Section A of the supplementary material) constructs a problem instance
with a 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 a 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, EI (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-variance points.
EI-PUC spends its entire budget on these low-cost low-variance points, earning almost no 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 a 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, EI performs a single evaluation of 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 illustrates this phenomenon in a 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 (x < 0.5) with low-variance and a mean that is significantly below the best point observed. There is a higher-cost region on the right (x > 0.5) where the mean and variance are both larger. These means and variances are such that the global maximum of the function is likely to 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 on the right, finding values that are close to the global optimum.
In this example, EI-PUC encounters the same difficulty it faces in the proof of Theorem 1: It overvalues 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 a global maximum.

heading: 3.3 Decomposition and Truncation
text: We now discuss how we can additively decompose and then truncate the problem in (1) so that it is more amenable as a BO acquisition function. Let r(Dn−1,Dn) = u(Dn)− u(Dn−1) be the increase in utility between successive states. Using a telescoping sum and rewriting the summation as an infinite sum, we have
V ∗(D) = sup π∈Π Eπ [ ∞∑ n=1 r(Dn−1,Dn)1{n≤NB} ∣∣∣D0 = D]. (2)
A truncated version of (2) that is useful within our scenario tree optimization approach described in Section 4.2 is given by
VN (D) = sup π∈Π Eπ [ N∑ n=1 r(Dn−1,Dn)1{n≤NB} ∣∣∣D0 = D], (3)
where N is a fixed number of “look-ahead steps.” When for each c drawn from the prior, there exists a lower bound on c(x) over X so that (1) is well-defined, it follows that the truncation becomes more accurate when N becomes large: limN→∞ VN (D) = V ∗(D). This serves as the motivation for our acquisition function described below.

heading: 4 Budgeted Multi-Step Expected Improvement
text: We now derive the budgeted multi-step expected improvement (B-MS-EI) acquisition function, where the main idea is to solve the truncated problem given in (3). Accordingly, the acquisition function is parameterized by N , the maximum number of look-ahead steps. In Section 4.2, we
discuss how to approximately optimize this acquisition function using a scenario tree, leveraging the technique developed in Jiang et al. (2020b), and in Section 4.3, we discuss how to set the budget that defines our acquisition function when the actual remaining budget is too large to be meaningfully taken into account by a computationally feasible number of look-ahead steps.

heading: 4.1 Dynamic Programming on the Truncated Problem
text: Our derivation of B-MS-EI starts with applying Bellman recursion to (3). To this end, we define the one-step marginal value of a measurement at point x given an arbitrary set of observations D (i.e., a state-action value function, or Q-function) to be
Q1(x | D) = Ey,z [ r(D,D ∪ {(x, y, z)})1{s(D)+z≤B} ] = Ey,z [ (y − u(D))+ 1{s(D)+z≤B} ] .
Proposition 1 below shows that, when f and ln c are drawn from independent GPs, Q1 admits an analytic expression similar to the one of constrained expected improvement (Schonlau et 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 ln c follow independent Gaussian process prior distributions and that D is an arbitrary set of observations. Define µfD(x) = E[f(x) | D], µln cD (x) = E[ln c(x) | D], σfD(x) = Var[f(x) | D]1/2, and σln cD (x) = Var[ln c(x) | D]1/2. Then,
Q1(x | D) = EIf (x | D) Φ(ζ)1{s(D)≤B} where EIf is the classical expected improvement computed with respect to f , ζ = ( ln (B − s(D))−
µln cD (x) ) /σln cD (x), and Φ is the standard normal cdf.
In contrast with homogeneous-cost non-myopic formulations, the indicator 1{s(D)≤B} truncates our reward sequence at the random time before the budget is first depleted. Analogously, we can define the n-step value function evaluated at x, Qn(x | D), as the expected difference in utility after using the optimal policy to evaluate n additional points, among which x is the first of them. Using the Bellman recursion, one can write Qn(x | D) as
Qn(x | D) = Q1(x | D) + Ey,z [ max x∈X Qn−1 (x | D ∪ {(x, y, z)}) ] ,
which holds for all n. Our acquisition function B-MS-EI is defined as QN , meaning that at every step our sampling policy evaluates xn+1 ∈ argmaxx∈XQN (x | Dn).

heading: 4.2 Optimizing B-MS-EI via Budgeted One-Shot Multi-Step Trees
text: Maximizing our acquisition function is challenging as, in principle, this requires nested stochastic optimization over a continuous domain. We build upon the multi-step scenario tree approach of Jiang et al. (2020b) and devise an optimization method based on a sample average approximation of maxx∈XQN (x | Dn). 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 a higherdimensional domain instead of a sequence of nested stochastic optimization problems. We tackle the higher-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 recursion repeatedly, QN can be rewritten as
QN (x | D) = Q1(x | D) + Ey,z [ max x2 { Q1 (x2 | D1) + Ey,z [ max x3 { Q1 ( x3 | D2 ) + · · · }]}] .
Now we consider the Monte Carlo approximation of QN (x | D) given by Q̂N (x |D)
= Q1(x |D) + 1
m1 m1∑ j1 [ max x j1 2 { Q1(x j1 2 |Dj11 ) + 1 m2 m2∑ j2 [ max x j1j2 3 { Q1(x j1j2 3 |Dj1j22 )+· · · }]}] ,
where mi, i = 1, . . . , N − 1, is the number of samples used in step i, and the sets of observations are defined recursively by the equations Dj1i = D ∪ {( x, yj1i , z j1 i )} and
Dj1...jii = D j1...ji−1 i ∪ {( x j1...ji−1 i , y j1...ji i , z j1...ji i )} ,
Figure 3: An illustration of the scenario tree representation of our acquisition function forN = 5 stages, where (m1,m2,m3,m4) = (4, 2, 2, 1). Some paths down the tree stop accumulating value earlier than others due to the budget being exhausted, i.e., when s(Dj1...jii ) > B (ending in red circle nodes). Other paths may terminate due to the maximum look-ahead N before the budget is exhausted (ending in black square nodes), representing some approximation error due to the truncation.
xj12
<latexit sha1_base64="EvygJKMnRDPlVlGhJrxkl3FQUew=">AAAB8nicbVBNS8NAEN3Ur1q/qh69LLaCp5KUih4LXjxWsB+QxrDZbtq1m03YnYgl9Gd48aCIV3+NN/+N2zYHbX0w8Hhvhpl5QSK4Btv+tgpr6xubW8Xt0s7u3v5B+fCoo+NUUdamsYhVLyCaCS5ZGzgI1ksUI1EgWDcYX8/87iNTmsfyDiYJ8yIylDzklICR3OqTX7/PHnxnWvXLFbtmz4FXiZOTCsrR8stf/UFM04hJoIJo7Tp2Al5GFHAq2LTUTzVLCB2TIXMNlSRi2svmJ0/xmVEGOIyVKQl4rv6eyEik9SQKTGdEYKSXvZn4n+emEF55GZdJCkzSxaIwFRhiPPsfD7hiFMTEEEIVN7diOiKKUDAplUwIzvLLq6RTrzmN2sVtvdJs5HEU0Qk6RefIQZeoiW5QC7URRTF6Rq/ozQLrxXq3PhatBSufOUZ/YH3+ADH/kIE=</latexit>
xj1j23
<latexit sha1_base64="X51a3FS7oGsJDhGnG2HTmxNgEf0=">AAAB+HicbVDLTgJBEOzFF+KDVY9eJoKJJ7KLGD2SePGIiTwSWDezwywMzD4yM2vEDV/ixYPGePVTvPk3DrAHBSvppFLVne4uL+ZMKsv6NnJr6xubW/ntws7u3n7RPDhsySgRhDZJxCPR8bCknIW0qZjitBMLigOP07Y3vp757QcqJIvCOzWJqRPgQch8RrDSkmsWy4/u+X06cm00cqvTsmuWrIo1B1oldkZKkKHhml+9fkSSgIaKcCxl17Zi5aRYKEY4nRZ6iaQxJmM8oF1NQxxQ6aTzw6foVCt95EdCV6jQXP09keJAykng6c4Aq6Fc9mbif143Uf6Vk7IwThQNyWKRn3CkIjRLAfWZoETxiSaYCKZvRWSIBSZKZ1XQIdjLL6+SVrVi1yoXt9VSvZbFkYdjOIEzsOES6nADDWgCgQSe4RXejCfjxXg3PhatOSObOYI/MD5/APwCkfY=</latexit>
xj1j2j34
<latexit sha1_base64="XIFPjZJKN9TAR8ico7PQOYAR+VM=">AAAB/HicbVDLTgJBEOzFF+JrlaOXiWDiiewiRo8kXjxiIo8E1s3sMMDA7CMzs8bNBn/FiweN8eqHePNvHGAPClbSSaWqO91dXsSZVJb1beTW1jc2t/LbhZ3dvf0D8/CoJcNYENokIQ9Fx8OSchbQpmKK004kKPY9Ttve5Hrmtx+okCwM7lQSUcfHw4ANGMFKS65ZLD+6tft07Npo7FZ1nU/LrlmyKtYcaJXYGSlBhoZrfvX6IYl9GijCsZRd24qUk2KhGOF0WujFkkaYTPCQdjUNsE+lk86Pn6JTrfTRIBS6AoXm6u+JFPtSJr6nO32sRnLZm4n/ed1YDa6clAVRrGhAFosGMUcqRLMkUJ8JShRPNMFEMH0rIiMsMFE6r4IOwV5+eZW0qhW7Vrm4rZbqtSyOPBzDCZyBDZdQhxtoQBMIJPAMr/BmPBkvxrvxsWjNGdlMEf7A+PwBVPWTOw==</latexit>
xj1j2j3j45
<latexit sha1_base64="L3z9FTqQx6ogjkZ3ki8oLRL/LrQ=">AAACAHicbVC7TgJBFL3rE/G1amFhMxFMrMguQrQksbHERB4JrJvZYRYGZh+ZmTWSDY2/YmOhMbZ+hp1/4wBbKHiSk5ycc29m7vFizqSyrG9jZXVtfWMzt5Xf3tnd2zcPDpsySgShDRLxSLQ9LClnIW0opjhtx4LiwOO05Y2up3nrgQrJovBOjWPqBLgfMp8RrLTlmsfFR7d6nw5dGw3dsuaFZmVSdM2CVbJmQMvCzkQBMtRd86vbi0gS0FARjqXs2FasnBQLxQink3w3kTTGZIT7tKNliAMqnXR2wASdaaeH/EhohgrN3N8bKQ6kHAeengywGsjFbGr+l3US5V85KQvjRNGQzB/yE45UhKZtoB4TlCg+1gITwfRfERlggYnSneV1CfbiycuiWS7ZlVL1tlyoVbI6cnACp3AONlxCDW6gDg0gMIFneIU348l4Md6Nj/noipHtHMEfGJ8/s/eUgQ==</latexit>
x
<latexit sha1_base64="Yf0kmUCf0JynssW+4Z5po3ArBxE=">AAAB6nicbVA9TwJBEJ3DL8Qv1NJmI5hYkTuC0ZLExhKjIAlcyN4yBxv29i67e0ZC+Ak2Fhpj6y+y89+4wBUKvmSSl/dmMjMvSATXxnW/ndza+sbmVn67sLO7t39QPDxq6ThVDJssFrFqB1Sj4BKbhhuB7UQhjQKBD8HoeuY/PKLSPJb3ZpygH9GB5CFn1FjprvxU7hVLbsWdg6wSLyMlyNDoFb+6/ZilEUrDBNW647mJ8SdUGc4ETgvdVGNC2YgOsGOppBFqfzI/dUrOrNInYaxsSUPm6u+JCY20HkeB7YyoGeplbyb+53VSE175Ey6T1KBki0VhKoiJyexv0ucKmRFjSyhT3N5K2JAqyoxNp2BD8JZfXiWtasWrVS5uq6V6LYsjDydwCufgwSXU4QYa0AQGA3iGV3hzhPPivDsfi9ack80cwx84nz+btI1Q</latexit>
: n > NB
<latexit sha1_base64="sUxqNz+E/z5PRDWNinVenoHxWBk=">AAAB8nicbVBNSwMxEJ31s9avqkcvwVbwVHZLRfEgRS+epIL9gO1Ssmm2Dc0mS5IVSunP8OJBEa/+Gm/+G9N2D9r6YODx3gwz88KEM21c99tZWV1b39jMbeW3d3b39gsHh00tU0Vog0guVTvEmnImaMMww2k7URTHIaetcHg79VtPVGkmxaMZJTSIcV+wiBFsrORfoZJA1+i+e1PqFopu2Z0BLRMvI0XIUO8Wvjo9SdKYCkM41tr33MQEY6wMI5xO8p1U0wSTIe5T31KBY6qD8ezkCTq1Sg9FUtkSBs3U3xNjHGs9ikPbGWMz0IveVPzP81MTXQZjJpLUUEHmi6KUIyPR9H/UY4oSw0eWYKKYvRWRAVaYGJtS3obgLb68TJqVslctnz9UirVqFkcOjuEEzsCDC6jBHdShAQQkPMMrvDnGeXHenY9564qTzRzBHzifP3ECj10=</latexit>
: n  NB
<latexit sha1_base64="TaGw3HG1oE8xJwrAZAKVrSwy/5c=">AAAB9HicbVDLSgNBEOyNrxhfUY9eBhPBU9gNEcVT0IsniWAekCxhdtJJhszOrjOzgRDyHV48KOLVj/Hm3zh5HDSxoKGo6qa7K4gF18Z1v53U2vrG5lZ6O7Ozu7d/kD08qukoUQyrLBKRagRUo+ASq4YbgY1YIQ0DgfVgcDv160NUmkfy0Yxi9EPak7zLGTVW8q9JXpKWQHLfvsm3szm34M5AVom3IDlYoNLOfrU6EUtClIYJqnXTc2Pjj6kynAmcZFqJxpiyAe1h01JJQ9T+eHb0hJxZpUO6kbIlDZmpvyfGNNR6FAa2M6Smr5e9qfif10xM98ofcxknBiWbL+omgpiITBMgHa6QGTGyhDLF7a2E9amizNicMjYEb/nlVVIrFrxS4eKhmCuXFnGk4QRO4Rw8uIQy3EEFqsDgCZ7hFd6cofPivDsf89aUs5g5hj9wPn8ALTWQYA==</latexit>
: n = N
<latexit sha1_base64="vk72Sduily2DfnmKvMbu1LeRSo8=">AAAB8HicbVBNSwMxEJ2tX7V+VT16CbaCp7JbKoogFLx4kgq2VdqlZNNsG5pklyQrlKW/wosHRbz6c7z5b0zbPWjrg4HHezPMzAtizrRx3W8nt7K6tr6R3yxsbe/s7hX3D1o6ShShTRLxSD0EWFPOJG0aZjh9iBXFIuC0HYyup377iSrNInlvxjH1BR5IFjKCjZUeL1FZoit0W+4VS27FnQEtEy8jJcjQ6BW/uv2IJIJKQzjWuuO5sfFTrAwjnE4K3UTTGJMRHtCOpRILqv10dvAEnVilj8JI2ZIGzdTfEykWWo9FYDsFNkO96E3F/7xOYsILP2UyTgyVZL4oTDgyEZp+j/pMUWL42BJMFLO3IjLEChNjMyrYELzFl5dJq1rxapWzu2qpXsviyMMRHMMpeHAOdbiBBjSBgIBneIU3RzkvzrvzMW/NOdnMIfyB8/kDLQ6Opw==</latexit>
with fantasy samples (i.e., samples drawn from the model) (yj1...jii , z j1...ji i ) ∼ p(· | x j1...ji−1 i ,D j1...ji−1 i ) obtained via the reparametrization trick
2 (Kingma and Welling, 2013; Wilson et al., 2018).

heading: 4.3 Budget Scheduling via Rollout of Base Sampling Policy
text: Let Bn = B − ∑n i=1 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, Bn may be too large to be taken into account by our acquisition function in a meaningful way, especially during the first few evaluations (if the remaining budget is too large relative to the number of 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 a 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 theN 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 a 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 a new fantasy budget. The intuition behind this heuristic is that our 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 are better or at least as good as those of the base sampling policy. In our experiments, we use EI-PUC-CC as the base policy.

heading: 5 Experiments
text: 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 path variant (Jiang et al., 2020b), which is based on a degenerate tree with one fantasy sample per step. For each of these variants, we consider both N = 2 and N = 4 look-ahead steps. We denote the multi-step path variant with N steps as N -B-MS-EIp 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) (Snoek et al., 2012; Lee et al., 2020b), and expected improvement per unit of cost with cost cooling (EI-PUC-CC) (Lee et al., 2020b). EI-PUC and EI-PUC-CC are currently the de-facto standard approach to cost-aware BO. Since Lee et al. (2020b) assumes that the cost is 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
2Note that since we employ Monte Carlo sampling to approximate QN (x | Dn), the independence assumption between f and c in Proposition 1 is not necessary for our approach, and one can jointly model f and c (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.
these acquisition functions. Closed form analytical expressions for these acquisition functions can be found in Section C of the supplementary material.

heading: 5.1 Description of Benchmark Problems
text: Synthetic Test Problems. The first four problems use synthetic objective functions commonly found in the literature: Dropwave, Alpine1, Ackley, and Shekel5 (defined in Section D of the supplementary material). Each objective function is accompanied by a cost function of the form c(x) = exp [ α d ∑d i=1 cos ( β(xi − x∗i + γ) )] , where x∗ is the objective function’s maximizer. In each replication we use a different cost function, obtained by sampling α, β, and γ 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, α controls the magnitude of the difference between the minimum and maximum costs; β controls the variability of the cost; and γ controls the cost at the optimum. In particular, if γ = 0, then x∗ is the most expensive point, whereas if γ = π, then x∗ is the cheapest point. This family of cost functions emulates a wide range of possible scenarios.
AutoML Benchmarks. We consider three AutoML benchmark problems: LDA, CNN, and RFBoston. The LDA and CNN problems use publicly available data sets from the HPOLib (The HPOlib authors, 2014) and HPOLib1.5 (The HPOlib1.5 authors, 2017) hyperparameter optimization libraries. Following Eggensperger et al. (2018), we use surrogates of the underlying objective and cost functions to emulate the computationally 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 et al. (2010), 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 κ ∈ [0.5, 1.0] (controls speed at which information is forgotten) and τ0 ∈ [1, 1024] (on a log2 scale, downweights early iterations). These evaluations are expensive and heterogeneous, ranging from 2 to 10 hours each (see Figure 1).
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” ∈ [10−6, 1.0] (on a log10 scale), “batch size” ∈ [32, 512], and “number of units in layer k” ∈ [16, 256] (on a log2 scale), for k = 1, 2, 3. T Finally, the RF-Boston problem considers optimization of the 5-fold cross validation error when using a 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” ∈ [1, 256] (rounded to the nearest integer), “max_depth” ∈ [1, 64] (rounded to nearest integer), and “max_features” ∈ [0.1, 1] (on a log10 scale). The cost of each is evaluation is proportional to the
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 a robot pushes an object from its origin, winit = (0, 0), to a target wtarget ∈ R2. In the our version, we draw 20 different target locations uniformly at random over {(w1, w2) ∈ R2 : 1 < |w1|, |w2| < 5}, which are distributed equally across the replications performed. The parameters to be optimized are the location of the robot, z ∈ [−5, 5]2, and the duration of the push, t ∈ [1, 30]. The objective to minimize is the distance from the object’s location after being pushed, wpush(z, t), and the target location, i.e., f(z, t) = ‖wtarget −wpush(z, t)‖2. The cost function is given by c(z, t) = ‖wpush(z, t)‖+ , where is a constant, and represents the energy spent by the robot by pushing the object.

heading: 5.2 Results and Discussion
text: Figure 4 plots a 95% confidence interval on mean log-regret versus the budget used thus far. We perform experiments using a 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, we plot results over the range from 20% to 100% of this overall budget. The results for N = 2 look-ahead steps are deferred Section G to 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 can also be found in Section G of the supplementary material. An implementation of our algorithms and numerical experiments can be found at https://github.com/RaulAstudillo06/BudgetedBO.
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 valueto-cost ratio methods (EI-PUC or EI-PUC-CC) performs worst. B-MS-EI is more computationally intensive to optimize than the standard approaches. The average walltime per acquisition of 4-BMS-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 minutes3 are acceptable when the acquisition function is applied to real-world problems where the function evaluation often takes much longer (e.g., in Figure 1, 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.

heading: 6 Conclusion
text: 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 to account for uncertainty in the cost function as well as the presence of the budget constraint as part of the exploration-exploitation trade-off in a principled way, as we show in Theorem 1. In this work, we provided a dynamic programming formulation of this problem, along with a 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 to the multi-fidelity setting, where evaluation costs play an even larger role.
3These times are not unusual for advanced BO methods; see, e.g., Section 4 of Wu and Frazier (2019).

heading: Acknowledgments
text: Authors RA and PF were partially supported by AFOSR FA9550-19-1-0283 and FA9550-20-1-0351.

Review summaries:
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.

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.