Constrained Two-step Look-Ahead Bayesian Optimization
Authors: Duke Zhang
Xiangyu Zhang
Peter I. Frazier
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian optimization
Non-myopic
Gaussian processes
Derivative-free optimization

Abstract: Recent advances in computationally efficient non-myopic Bayesian optimization offer improved query efficiency over traditional myopic methods like expected improvement, with only a modest increase in computational cost. These advances have been largely limited to unconstrained BO methods with only a few exceptions which require heavy computation. For instance, one existing multi-step lookahead constrained BO method (Lam & Willcox, 2017) relies on computationally expensive unreliable brute force derivative-free optimization of a Monte Carlo rollout acquisition function. Methods that use the reparameterization trick for more efficient derivative-based optimization of non-myopic acquisition functions in the unconstrained setting, like sample average approximation and infinitesimal perturbation analysis, do not extend: constraints introduce discontinuities in the sampled acquisition function surface. Moreover, we argue here that being non-myopic is even more important in constrained problems because fear of violating constraints pushes myopic methods away from sampling the boundary between feasible and infeasible regions, slowing the discovery of optimal solutions with tight constraints. In this paper, we propose a computationally efficient two-step lookahead constrained Bayesian optimization acquisition function (2-OPT-C) supporting both sequential and batch settings. To enable fast acquisition function optimization, we develop a novel likelihood ratio-based unbiased estimator of the gradient of the two-step optimal acquisition function that does not use the reparameterization trick. In numerical experiments, 2-OPT-C typically improves query efficiency by 2x or more over previous methods, and in some cases by 10x or more.

Two-step lookahead Bayesian optimization with inequality constraints
Yunxiang Zhang Cornell University y22547@cornel1.cm edu
Xiangyu Zhang Comell University x25560cornel1.edd
Peter I. Frazier Coreell University
pf98@cornel1. edu
Abstract
Recent advances in computationally efficient non-myopic Bayesian optimization offer improved query efficiency over traditional myopic methods like expected improvement, with only a modest increase computational cost. These advances have been largely limited to unconstrained BO methods with only few exceptions which require heavy computation. For instance, one existing multi-step lookahead constrained BO method [1] relies computationally expensive unreliable brute- optimization Monte Carlo rollout acquisition function.
force derivative-Fi Methods that use the reparameterization trick for more efficient derivative- optimization of non-myopic acquisition functions in the unconstrained setting, like sample average approximation and infinitesimal perturbation analysis, do not extend: constraints introduce discontinuities in the sampled acquisition function surface. Moreover, argue here that being non-myopic even more important constrained problems because fear of violating constraints pushes myopic methods away from sampling the boundary between feasible and infeasible regions, slowing the discovery of optimal solutions with tight constraints. In this paper, we propose a computationally efficient two-step lookahead constrained Bayesian optimization acquisition function (2-OPT-C) supporting both sequential and batch settings. To enable fast acquisition function optimization, we develop novel likelihood- aatio-based unbiased estimator of the gradient of the two-step optimal acquisition function that does not use the reparameterization trick. In numerical experiments, 2-OPT-C typically improves query efficiency by 2x more over previous methods, and in some cases by 10x or more.
Introduction
We consider constrained optimization of continuous black-box function f under continuous black- box constraints y., minzes. / (xx) subject to yi (x) < 1,. within the compact design space A CCR We suppose both f (xx and g: (x(x) are derivative-free, noise-free. Such problems arise, for example, in tuning hyperparameters of machine learning models subject to runtime or fairness constraints and policy optimization in reinforcement learning with safety constraints. For instance, neural networks deployed on mobile phones must be accurate but may also have limited computation available while needing to respond to users in real time, creating constraint how long the model takes predict test time (2]. Another example, from [3], is predicting recidivism risk in the criminal justice system with a faimesss constraint ensuring that false positive rates equal across racial and ethnic groups Other applications arise in drug discovery and aircraft design
and also
Bayesian optimization (BO) has proven successful at solving black-box optimization problems with expensive objectives 6 7) including constrained problems of the form above. BO methods for constrained problems include constrained expected improvement (EIC in [8) rediscovered
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

by 191, constrained BO with stepwise uncertainty reduction [10], predictive entropy search with
unknown constraints [M. Alternating Direction Method of Multipliers Bayesian optimizattion [[2]. constrained BO with max-value entropy search [3], and augmented I Lagrangian techniques that convert constrained problems into a sequence of unconstrained ones [14. It also includes methods designed specifically for equality and mixed constraints [5]. for batch observations [6] and for
problems with high dimensions [17].
All of these existing methods, however, for constrained Bayesian optimization (CBO), are myopic, in the sense that they only consider the immediate improvement in solution quality resulting from a function evaluation and ignore later improvements in solution quality enabled by this evaluation. (Notable exceptions are [ 18, discussed below.) This greedy behavior may hinder an algorithm's ability to find good solutions efficiently. While a recent flurry of activity is addressing this issue for unconstrained problems [19 20 22 23 and the performance improvements provided by these non-myopic algorithms for unconstrained BO suggest that non-myopic BO is promising for constraints as well, substantial non-myopic development has not reached the constrained setting.
Moreover, we argue in detail below that being non-myopic provides even more value in constrained settings than it does in unconstrained ones. To find a global optimum under constraints quickly, an algorithm benefits by efficiently learning the boundary between the feasible region where the constraint is satisfied and the infeasible region where it is not. This is facilitated by sampling points likely to be close to this boundary. Myopic methods. however, such as EIC, undervalue sampling such points because they have substantial probability of being infeasible and because infeasible points do not directly improve solution quality. Non-myopic methods, on the other hand, understand that learning about the boundary's ' location will provide future benefits, allowing them to value this information more appropriately. Localizing the boundary efficiently is especially important when the global optimum lies on this boundary, as it often does in constrained optimization when the objective (e.g., the quality of product) is negatively correlated with a constraint (e.g., the cost required to produce it). We illustrate this via simple example in $3 and our numerical experiments in $6, which show several-fold improvement over the Nfte-of-the-art in some problems.
One existing non-my non-myopic constrained BO method T first formulates CBO as a dynamic program (DP). However, this DP is intractable. To mitigate the issue, rollout, an approximate DP technique, is used. Nevertheless, this approach requires an extremely large amount of computation to approximate the multi-step lookahead policy well, especially in problems with more than a few dimensions, in part because it relies on computationally expensive derivative-free optimization, and because its acquisition function is computed via Monte Carlo, further increasing the computation required. This limits its applicability.
The constrained multi-information source BO method recently proposed by 18] is also non-myopic. It focuses on the multi-informationn source setting and assumes that the objective and constraint are evaluated in a decoupled fashion. In contrast, our applications of interest often compute the objective and constraints simultaneously. For example, when tuning ML hyperparameters to maximize accuracy subject to model execution time constraint, the marginal cost of evaluating accuracy is negligible once we evaluate model execution time and incur the training cost. Thus, a method that evaluates the objective and constraints in a decoupled way discards information in such settings.
Our Contributions. We provide novel non-myopic computationally efficient method for batch CBO. It substantially outperforms myopic CBO methods. In relation to [ it requires substantially less computation decide where to sample. Its query efficiency is substantially better in relatively higher-dimensional problems and is at least as good in lower liwer-dimensional ones.
The key to our approach is a new method for optimizing stochastic acquisition functions, leveraging the likelihood ratio method [24]. Standard efficient approaches to optimizing stochastic non-myopic acquisition functions, such infinitesimal perturbation analysis (IPA) (25) or the one-shot method 26 (also called sample average approximation or SAA), rely on a sampled acquisition function surface created using the reparameterization trick. In CBO, however, this surface is discontinuous, preventing the efficient use of these methods. Our novel approach is potentially generalizable to other settings where such discontinuities prevent the use of IPA and one-shot optimization.
Our work builds on the unconstrained two-step optimal method (21), overcoming substantial com- putational difficulties created by constraints' inherent discontinuities. These difficulties require abandoning the IPA approach used in [21] and instead developing a new likelihood- ceteooddrrrttt-b-bsseee based
2

---

approach. The likelihood ratio method that we use here to estimate the gradient of the acquisition function relies on change of measure of the same type used within importance sampling. [2T coincidentally also uses importance sampling, but in a fundamentally different way: as a variance reduction technique, and not for gradient estimation.
2
Background
We briefly review the literature on myopic CBO. Then we summarize standard results needed later on Gaussian processes and the widely used myopic method EIC as well as its batch version.
2.1 Myopic Constrained Bayesian Optimization
This work builds on the larger literature on myopic CBO. We review this literature here, giving more details than in $1. [9] proposes constrained expected improvement, a weeghte expected improvement acquisition function which multiplies the expected improvement with the probability
of feasibility associated with each constraint, rediscovering an approach due [. (27 proposes
an approach in which the point to sample is found by maximizing EIC and then a decision is made
whether to evaluate the objective or the constraint based on the information gain.
[10] proposes
stepwise uncertainty reduction method in which the acquisition function aims to maximally decrease our uncertainty on the location the optimizer with a single evaluation. Predictive entropy search with constraints (PESC) [ an extension of predictive entropy search [28 is another information- gain based approach. It chooses the point to evaluate by approximating the expected information gain on the value of the constrained minimizer. [14] proposes hybrid approach combining the expected improvement with an augmented Lagrangian framework. [I5] extends this technique by introducing an alternative slack variable formulation that handles equality and mixed constraints. Integrated expected conditional improvement (IECI) [29] proposes a new acquisition function that integrates conditional improvement with respect to reference point the design space. [16] develops quasi-Mone Carlo approximation of expected improvement under batch optimization with noisy observations and noisy constraints. [13] modifies the mutual information criterion of max-value entropy search (30] and extends to the constrained setting with the ability to handle both continuous and binary constraints. [12] leverages the ADMM framework convert constrained problems into multiple unconstrained subproblems by introducing auxiliary variables for each constraint, then solves the subproblems using standard BO. Similar TuRBO (31), [17] proposes an acquisition function for constrained optimization that scales to high dimensions by maintaining and adjusting trust regions.
2.2 Gaussian Processes
BO makes productive use of Gaussian processes (GPs) (32]. We put a GP prior on the objective function f. which is specified by mean function pd-) and kernel function (-,-). After observing
the data points D = (1) (2) (2), ,..., _a))) } and their corresponding function values J(D) (f(x))) f(x(3)) ..... f....,((((())) (x) the GP prior over is updated by:
(()) ~ N (m(a; D), ox; D))
where plz; D) is the posterior mean and (I;; D) is the posterior standard deviation. μ(D) is the set of values of the prior mean function evaluated at points in D.
While support multiple constraints, focus single constraint g for ease of presentation. We use (-) and (-(..)) to denote the mean function and the kernel of the independent GP prior on respectively, and j (2; D) and (x;; D) denote the mean and standard deviation of the posterior. We refer readers to the supplement for multiple constraints.
2.3 Constrained Expected Improvement
We briefly review constrained expected improvement (EIC) 9 8 introducing notation used later. Suppose we have independent GP priors on f and g and observations S(D) = {f(x) : E D} and g(D) = (g(x) x e D} collection of datapoints D. Let f be the best point observed so far

---

subject to our constraints, f min f(z). The constrained expected improvement at r is:
EIC(#) = BB [(=) (g(x)) - 0)] B - f(a)]* + B()(o(a) < 0}} = Bl(a)) PF(x),
(1)
where [[[] the expectation taken with respect to the posterior given D. J(D,, and gDD). EI(x)) and PF(x)) are the expected improvement and the probability of feasibility at respectively, and both have analytic forms. Here, we assume the prior on and g are independent as in [9] We refer readers to (33 and [9] for more details.
We now define EIC the batch setting, building on the first discussion of which we are aware [16 Let X (æ(n+1) (x(+2) (n(++)) } be the batch of candidate points that consider evaluating next. Then the constrained multi- tallii-poins expected improvement EIC(X) (C) is,
EIC(X)
max x
(f (f=)
1 s =0]
The details of the derivation of (X) are provided in the supplement.
3 Constrained Two-step Acquisition Function
In this section, we first show that why being non non-m non-myopic is important in CBO. Then we formally define the novel acquisition function 2-OPT-C that is at the heart of our method.
3.1 The Importance of Being Non-Myopic in CBO
Figure I: EIC and 2-OPT-C optimizing a 1-d synthetic function. The first three graphs of each row the posterior on f. the posterior g, and the acquisition function under EIC, and the last three graphs are the corresponding quantities under 2-OPT-C. Each row shows one iteration, proceeding from the first iteration at the top to the last iteration at the bottom. In the plots of the posterior on and g. "x" denotes infeasible points and square denotes feasible points. The constraint threshold (0) plotted as red line. The red dot the point newly sampled in the current iteration. 2-OPT-C explores potentially infeasible points more aggressively and discovers a better feasible point.
Before presenting out non-myopic acquisition function, 2-OPT-C, we give intuition for why being non-myopic even more important constrained problems than it unconstrained ones. Suppose the constraint function value of the (unobserved) best feasible point is equal or close to the constraint threshold. To find this point with as few function evaluations as possible, the algorithms need to efficiently learn the feasible region's 's boundaries. This happens most quickly when evaluating points close to this boundary. Since the boundary is uncertain, this requires an algorithm to be willing to evaluate points that may be infeasible. However, the value of such points to myopic CBO algorithms like EIC significantly reduced because the probability of infeasibility is high - typically near 50%, lowering the PF(x) term in T). Thus, myopic CBO algorithms may insufficiently explore the boundary, instead sticking well inside the feasible region.
Figure lusttraess this with an example. On the first iteration, EIC evaluates point in region around an existing feasible point that likely feasible, getting a small one-step improvement but little information f and g for future evaluations. However, 2- 2-PPT-C (defined below) explores more

---

aggressively. The point it evaluates is not feasible but provides a significant amount of information about the boundary between the feasible and infeasible region. As a result, after progressing two steps, 2-OPT-C locates a new feasible point (g(x)) = -0.02) with much lower objective function value while EIC remains stuck near the previous feasible point.
3.2 Definition of 2-OPT-C
We define our two-step optimal acquisition function for CBO, called 2-OPT-C, for both sequential and batch settings, and then discuss its computational optimization in $7 As in other CBO methods, we sequentially evaluate f and g next at the point that maximizes our acquisition function. This point optimal measure now assuming we will be able to measure one additional point before being awarded the maximum value found over the two new measurements and in our previously collected data. In other words, 2-OPT-C looks two steps ahead instead of the ene-step ahead considered by myopic methods. For clarity, we assume a single constraint and treat multiple constraints in the supplement.
In the batch setting, we find the batch of q points to measure next assuming we will then measure one additional point before being awarded the best value found. We assume only one additional point rather than a full additional batch for computational tractability. We argue that even the single additional point allows 2-OPT-C to think non-myopically and to value information about the feasible region that will only be acted on later.
We first define notation. We use subscripts {0, 2, to denote stages. Stage O is the current stage when we will evaluate a batch of points. In stage I, we will evaluate one additional point based on the results of stage and then in stage 2 will be judged based on the best of these points evaluated. We put independent GP priors on f and g. Let D be the collection of data points that we have observed so far. Then given the information in D and their corresponding objective f(D) and constraint g( D) values, the posterior distribution on the objective f is a Gaussian process with a mean function μo and kernel Ku. Similarly, the posterior distribution on the constraint g is also Gaussian process with a mean function ' and kernel KG. Eg denotes taking the expectation with respect to the posterior distributions given D.
Let fö be the best evaluated point satisfying the constraint so far, i.e. fö min ((x). Let X1 be the set of candidate points that consider evaluating at the first stage and let Y {f(x) : x E {1} and Y, = {g(x) I E {1} be the sets of corresponding objective function values and constraint values respectively. We let M1. ff and K1, Kí denote the mean function and kernel for the posterior distributions of f and g respectively given D) and X1. Let (ar) / (x, x) and of(x) = v Kf(x, 2). Let E, indicate the expectation with respect to the corresponding Gaussian processes given both D and X,. Finally, we use x2 to denote single point to be evaluated in the second stage, based on the results of the first.
Let ff and ft be the best evaluated feasible point by the end of the first and second stage respectively, ft = min min)ex; fz)) and fi = min (ft. (x2)) if g( S and f2 = ft not.
Following the principle of dynamic programming, our goal is to choose X, to minimize the overall expected objective (fā) This is done under the assumption that 22 will be chosen optimally leveraging observations of X₁. Equivalently, our goal is to maximize
Eo max Is -22 = Eo -i-st max - [2] 22
over X1 chosen in the first stage. Efffi - fi] depends implicitly on the information obtained from X1, which is Yy and Yg. and is included in the posterior over which E, is taken.
Thus, we define the constrained two-step acquisition function:
2-PTT-C(X)) = Eo fō - fi max E, [fi fā1
P2 A(6)
where A(8) is compact subset of A consisting of points at least 5 away from sampled points in DUX, X1. With 0, A A(8). We introduce the parameter 8 2 0 purely to overcome a technical hurdle in our theoretical analysis: that the standard deviation of the posterior distribution is not smooth at sampled points. We believe can be set to 0 in practice. Indeed, the theoretical analysis (Theorem I allows setting 8 at any arbitrary small positive value.
5

---

For use in $4 we derive a more directly computable expression for 2-OPT-C(X1). We rewrite
2- 2-OPT-C(X;) Eo
max (2EA(()
f
f
B1 fi
Eo
max a a(X1, x y) (cEA(())
where Y = (Y,, Yg) ~ X1) and p(u: X1) is the distribution of Y given f(D) and 9
specified explicitly as
P(y: = -(( x (16(X))
[X)
X1(
0 K8(X1, 1)
(3)
Then, a2, Y) can be written in closed form:
a(X1, #2, Y) = So fT+EI(Si - (1(22), where Em v) mm mmmmm////////mmmmmm VV) + Vop(mm/ vV) and PF(m*, 09) 1 (-m²) poml/vo>)
4 Optimizing 2-OPT-C Using Likelihood Ratios
Evaluating 2-OPT-C(Xi) requires performing a simulation where each replication samples Y and then evaluates mäX22 E A(8)a(( 22, Y). Averaging these replications gives Monte Carlo estimate of 2-OPT-C(X Optimizing 2-OPT-C(Xi) using such Monte Carlo estimates is difficult because of noise from simulation and because there
straightforward way to obtain derivatives.
Indeed, we show in the supplement that the two widely used approaches to efficiently optimizing Monte Carlo acquisition functions, IPA and SAA, fail to optimize 2-OPT-C well because constraints cause discontinuities in the surface they sample using the reparameterization trick.
Here, we develop novel approach for optimizing Monte Carlo acquisition functions like 2-OPT-C without using the reparameterization trick, overcoming the challenges created by these discontinuities. This approach uses the likelihood ratio method to derive unbiased estimator of the gradient for 2-OPT-C. We then use this novel estimator in multistart stochastic gradient ascent to maximize 2-OPT-C. (For details multistart stochastic gradient ascent for maximizing Monte Carlo acquisition function, see [34.) To the best of our knowledge, we are the first to demonstrate the benefits of the likelihood ratio method for acquisition function gradient estimation in BO.
4.1 Background on the Likelihood Ratio Method
We first give background on the likelihood ratio method using generic notation before describing how we use it in our setting. Given generic random variable ((x) whose distribution depends on a control vector x with density p(0; .²) and function Vax, (z)). our goal solve max, E[V (a,, ((z)). To do this, we estimate the gradient of [V[(x, ((x)) ] for use within multistart stochastic gradient.
To provide this gradient estimator, which {0 p(0,2) x) > 0} C {0 p(0) > 0} for all æ. Using this density, we construct the likelihood ratio, L(0; x) p(0;)))0000)) x((() We then have that
first choose density f(0) that does depend and for
(IV,,,(()))) / V(x,0) p(0:z) do f V(z, L(0; x)p(0) d8.
This is referred as importance sampling and is referred as the importance sampling distribution. The likelihood ratio method uses this expression to construct gradient estimator. Under regularity conditions (35) exchange the gradient operator and integration,
V [[ V. / V(s, 0) L(0: (0)) d0 / V.V(2, I(0:)))))
From this create unbiased estimator of the gradient of EVV ((x)) by sampling from the density p(0) and returning as our estimator Vz, L(;
A natural choice for the importance sampling distribution suggested in 224 is to take p(0) p0 .)) when estimating VV (<))) at x = We make this choice when designing an unbiased gradient estimator for 2-OPT-C, We discuss this in detail later in $42

---

4.2 Optimizing 2-OPT-C
To apply the likelihood ratio method develop gradient estimator for 2-OPT-C, we begin by rewriting the expression to be differentiated using importance sampling.
Mapping the notation of our generic discussion of importance sampling onto specific problem, our control a is the batch of points 11, our random variable Y (whose distribution depends on X1), and V (zz, 0) maX,2 a(X1, 42, ). Y a multivariate normal random variable whose density we write ply: X1), noting that its mean and covariance matrix are determined by X1, We let p(y: X1) be our importance sampling density for Y. for some fixed point X1 X, is arbitrary for now but is specified below. Our likelihood ratio then L(y: X1, = p(y; X1) p)(();(())))
As discussed above, the key step in the likelihood ratio method is to interchange the integral and gradient operator. This is justified our setting by Theorem[[bel The proof is provided in the supplement. As result, we have
Vx, 2-PT-C((1)) - P..
(4)
where
T(X1, X1,1, :
L X1, xi)
max (2EA(6)
=[Vx,a(X1 22 Y)] Lyy X1, X1) + (X1,, Y) [V,, Xi)l /ply: X1)
with z E arg ma a(X,, Y). The last equality is by the envelope theorem [66, i.e., max 22, Y) can be differentiated with respect X1 by first optimizing over 222 given X1, then holding zł fixed while differentiating with respect to X1. From now on, we will drop the subscript of the differential operator V for simplicity.
By (4 T(X1, XI, Y) an unbiased estimator of V 2-OPT-C(Xi) when Y is drawn according to ply; X1). With this stochastic gradient estimator, we then can use stochastic gradient ascent [37] with multiple restarts to find a collection of stationary values for X1. Then we use simulation to evaluate 2-OPT-C(A ((X; at these values and select the one with the highest estimated 2-OPT-C. This then provides a computationally efficient algorithm for optimizing 2-OPT-C. Pseudocode for using 2-OPT-C is provided the supplement.
As discussed above, the key step to developing our unbiased estimator is to interchange the integral and gradient operator, which is justified by Theorem ( heeow. The proof is provided in the supplement. Although Theorem I Jassumes > O, in practice, we choose 8 = 0 in our stochastic gradient estimator.
Theorem 1. We assume:
1. The prior on the objective function f is Gaussian Process f f~ (P( and the prior on the constraints g is another Gaussian Process GP K K,), (z,x²)) These Gaussian processes are independent.
2. μj and Pg continuously differentiable with z.
3. (z)xxx") and (z(2,²²) x') is continuously differentiable with and x'.
4. Given different points X (21, ..,, the matrix Ky X) and Kg(X,X) are of full rank.
Then 2-OPT-C(Xi)'s partial derivatives exist almost everywhere for any > 0. When 2-OPT-C(Xi) is differentiable.
V2-OPT-C(X.)= X(,,,
Choice of Importance Sampling Distribution We have constructed an estimator of the gradient V2-OPT-C at X1. This estimator was constructed using an importance sampling distribution parameterized by X1. We are free to choose this X₁ wish. We recommend setting X, equal

---

to X1, as our gradient estimator takes particularly simple form and offers robust performance. In particular, when X1 X1, Lyy; X1, X1) 1, our gradient estimator is
T(X1, X1, =- al X1, 22, v) Vvly; X1)) /plu: /pllss Xi) + VV((X1,22.10
where zá E arg max,, al a(X1, 22, v).
5 Numerical Experiments
This section numerically investigates our algorithms problems widely used as benchmarks in the constrained BO literature. Benchmarks demonstrate that 2-OPT-C usually provides significant improvements in query efficiency over state-of-the-ar methods. In the main paper, we focus on query efficiency for the sequential setting. The supplement includes additional experiments and discussions of batch evaluations and 2-OPT-C's computational overhead.
The benchmark problems include three synthetic problems from 0. named P1, P2, and P3, and two real-world problems, portfolio optimization and robot pushing. Detailed descriptions are in the supplement. We use these five problems in comparisons with myopic methods in $5.2 In $5.3 we compare with the non-myopic method from []]. Since code for [ was not available, we compare 2-OPT-C against the results previously published in that paper, consisting only of P1, P2, and P3.
5.1 Experiment Setup
Evaluation Metries We follow [1] in our evaluation methodology- Along with each evaluation n each algorithm makes a "recomendation", which the point we would evaluate if it were our last evaluation before being scored by the best point evaluated. From this recommended point, compute a score / for this algorithm in this timestep n. If the recommended point feasible, then fü is its objective function value. If not, ft"" is the best observed feasible value so far before the recommended point. Following [II. the point recommended is the one with the lowest posterior mean objective value, among those whose probability of satisfying each constraint is 0.975 or better. We then report the utility gap, e, = lfft f*1. which is the difference between this score and the global constrained optimum f We report the log 10 median utility gaps for P1, P2, P3, and the robot pushing problem in the main paper. Mean utility gap results are provided in the supplement. In the portfolio optimization problem, the optimum is unknown rate instead of the utility gap.
report the mean annualized return
Setup for $5. The 2-OPT-C implementation uses GPs with constant zero-mean prior and ARD square-exponential kernels for both objectives and constraints. GP hyperparameters are obtained by maximizing the marginal likelihood using GPy 38 SAA+CMA ES implemented similarly to 2-OPT-C and all the hyperparameters are the same or obtained in the same way as 2-OPT-C.
For all three synthetic problems (P1, P2, and P3), run 150 experiment replications for all algorithms. For the two real-world problems (portfolio optimization and robot pushing). we run 50 experiment replications. For the initialization of each experiment, with at least one feasible point from a Latin hypercube design. We run N = 40 function evaluations for Pl and P2. N 60 for P3, N 30 for portfolio optimization problem, and N 50 for robot pushing problem. We use batch size of 1 for all five experiments.
randomly sample three points
Setup for $5.
The setup for $5.3 is nearly the same as for 5.2 with three key differences. These arose from the need to replicate the experimental setup from
First, we run 500 experiment replications. Second, rather than initial points per problem, we use 1. Third, the evaluation method differs slightly. If the recommended point is infcasible, then rather than setting frr to the value of the best previously observed feasible point, we set it to the maximum of the objective function over all points in the domain, thus enforcing substantial penalty.
5.2 Comparison with Myopic Methods
Figure first compares the myopic methods ADMMBO 12]. BO_Slack 15
NEI 16 EIC 9
and PESC | on three synthetic problems. In general, O-PT offers significantly lower median
8

---

Figure 2: Log10 median utility gap Random Search, ADMMBO, BO Slack, NEL, EIC, PESC, CMAES, and 2-OPT-C with 95% confidence intervals for problems P1, P2, and P3.
FORTSE COR
Figure 3: Real-world experiment results on Random Search, NEI, EIC, PESC, and 2-OPT-C. We report the mean annualized return rate for portfolio optimization problem and log10 median utility gap for robot pushing problem.
utility gaps than the myopic methods across all three problems. For example, in P1, 2-OPT-C quickly converges to a utility gap 10-5 (in 27 evaluations), while the best of the other benchmarks (EIC) has utility gap of 10 at this many evaluations. There is only one method and problem, ADMMBO on problem P3, in which myopic method achieves an optimality gap comparable to 2-OPT-C, but 2-OPT-C reaches this optimality gap in fewer iterations.
Figure additionally compares with an SAA implementation of 2-OPT-C that uses CMA-ES 39 to optimize the SAA to the acquisition function on Pl, P2, and P3, denoted as SAA CMAES. We see that SAA CMAES generally perform better than myopic policies on all three problems (except EIC on PI), supporting the value of two-step lookahead for CBO over myopic approaches. However, due the discontinuity introduced by SAA, underperforms 2-OPT-C on all three synthetic problems. It also underperforms EIC in P1 and ADMMBO in P3. In addition, it requires substantially more computation. This is because, as we note in the supplement, discontinuities the SAA to the acquisition function make it extremely difficult to optimize. We provide additional experiments to illustrate this in the supplement.
Figure 3 compares 2-OPT-C with the mostly widely-used myopic methods, NEI, PESC, and EIC, on real-world problems. As in the synthetic problems, 2-OPT-C outperforms --OPT-Couperfomms the competing benchmarks. In portfolio optimization, 2-OPT-C provides roughly 0.5% more annualized return than the best myopic method (EIC). robot pushing, 2-OPT-C outperforms EIC and NEI over the full range of function evaluations; PESC eventually matches 2-OPT-C but there is range of function evaluations where 2-OPT-C performs strictly better.
5.3 Comparison with the Non-myopic Method
We compare 2-0PT-C with the non non-myopic rollout algorithm of [ on the three synthetic problems based on the results reported in their paper. We use the terms Rollout-1, Rollout-2, and Rollout-3 to denote this algorithm with horizons of 1, and respectively.
To compare with the rollout algorithm, we extract experimental data from I and replicate their experimental setup, adding 2-OPT-C's results their Figures 2 and 3.
Figure Figure(4report reports the results of these comparisons. shows that 2-OPT-C provides query efficiency that is at least good as the non-myopic rollout methods with different horizons all three problems and is sometimes substantially better. detail, for P1, 2-OPT-C increases solution quality by more than factor of 2 (10 (10-1.59) /10-1192 compared to the best rollout strategies, i.c., Rollout-1. For P3,

---

3.0
2.4
Log33 Modan USKY Cap
22
-24
Logis
20 on Evals
Function Evols
Function Evals
Figure 4: Log10 median utility gap of 2-OPT-C and the existing non-myopic constrained BO algorithm with different rollout horizons on PI, P2, and P3. The three lines of the rollout algorithm extracted from Figure 3 in [1. Additional information is provided in Table 1 in the supplement.
2-OPT-C is able to improve solution quality the best competing rollout method by roughly factor when the evaluation budget is tight (after 30 function evaluations).
2-OPT-C also uses less computation than the rollout algorithm [] publicly available, we refer to discussion in (21) the computational time of an unconstrained version of the rollout algorithm, which we understand from private communication has similar cost to M This states that the unconstrained rollout strategies require from 10 minutes to hour to evaluate a single point even since we need separate GP to model the constraint function. 2-OPT-C CC is more computationally efficient. On P3, for instance, 2-OPT-C optimizes batch of points in 25-30 minutes.
Since the code from [ is not
low-dimensional problem. This may be even larger in constrained settings,
R actually attempting to optimize the same theoretical acquisition function used by 2-OPT-C. Indeed, [1] uses EIC as its rollout strategy, which is optimal over horizon of h = 1. Rollout-1 then trying to identify the point to evaluate now that would be optimal if one additional point were evaluated after using EIC. If this point could be found exactly, it would be 2-step optimal.
Despite attempting to optimize an acquisition function that is conceptually the same as 2-OPT-C, -C, the performance of Rollout- is substantially worse (the utility gap is roughly 2x larger over all budgets), despite requiring more than double the computation. This because [I] optimizes this two-step acquisition function without the type of derivative estimates provided by our likelihood ratio method.
6
Conclusion
This paper presents non-myopic CBO algorithm, supporting both batch and sequential settings, that substantially improves both query efficiency and computation time over the one previous method focused on this class of problems for both sequential and batch settings.
While our method offers significant improvements in query efficiency compared to the state-of-the-ar that more than offset computational expense, there are likely more opportunities for reducing its computational cost. This, well as further theoretical investigation regarding our method providing such significant improvements in query efficiency compared to other methods, presents valuable directions for future work.
Faster constrained optimization of fime-consuming-t--vvaaee functions with our methodology enables creation of new engincering systems, better supervised learning methods, and lower-cost business operations. While we believe technological innovation is on balance good, new technology created using our methods also has the potential for negative effects. Understanding the societal effects of improved optimization capabilities is an important area for future research.
Acknowledgements
The authors were partially supported by AFOSR FA9550-19- 19-2-2 and FA9550-20-1-0351.
10

---

References
[1] Remi Lam and Karen Willcox. Lookahead bayesian optimization with inequality constraints.
I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 1890-1900. Curran Associates, Inc., 2017.
[2] Scott Clark and Patrick Hayes. Sigopt web page. https://sigopt..om.
[3] Valerio Perrone, Michele Donini, Muhammad Bilal Zafar, Robin Schmucker, Krishnaram Kenthapadi, and Cédric Archambeau. Fair bayesian optimization, 2021.
[4] John D. Trawick and Christophe H. Schilling. Use of constraint-based modeling for the prediction and validation of antimicrobial targets. Biochemical Pharmacology, 71(7):1026 1035, 2006. Special Issue on Antibacterials.
[5] Berk Ozturk and Ali Saab. Optimal aircraft design deicions under uncertainty via robust signomial programming. In AIAA Aviation 2019 Forum, page 3351, 2019.
[6] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advunces in Neural Information Processing Systems, volume 25, pages 2951-2959, Curran Associates, Inc., 2012.
[7] Peter Frazier. A tutorial bayesian optimization. arXiv preprint arXiv: 1807.02811, 2018.
[8] Matthias Schonlau, William Welch, and Donald R. Jones. Global versus local search in constrained optimization of computer models. Lecture Notes-Monograph Series, 34:11-25, 1998.
[9] Jacob R. Gardner, Matt J. Kusner, Zhixiang Xu, Kilian Q. Weinberger. and John P. Cunningham. Bayesian optimization with inequality constraints. In Proceedings of the 31st International Conference International Conference Machine Learning Volume 32, ICML' 14, pages 11-937-1--945. JMLR.org, 2014.
[10] Victor Picheny. A Stepwise uncertainty reduction approach constrained global optimization. In Samuel Kaski and Jukka Corander, editors, Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statisfies, volume 33 of Proceedings of Machine Learning Research, pages 787-795, Reykjavik, Iceland, 22-25 Apr 2014. PMLR.
[11] Jose Miguel Hernandez- Michael Gelbart, Matthew Hoffman, Ryan Adams, and Zoubin Ghahramani. Predictive entropy search for bayesian optimization with unknown constraints. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1699-1707, Lille, France, 07-09 Jul 2015. PMLR.
[12] Setareh Ariafar, Jaume Coll-Font, Dana Brooks, and Jennifer Dy. Admmbo: Bayesian op- timization with unknown constraints using admm. Journal of Machine Learning Research, 20(123):1-26, 2019.
[13] Valerio Perrone, Iaroslav Shcherbatyi, Rodolphe Jenatton, Cedric Archambeau, and Matthias Seeger. Constrained bayesian optimization with max-value entropy search. arXiv preprint 111.001910.07003, 2019.
[14] Robert B Gramacy, Genetha A Gray, Sébastien Le Digabel, Herbert KH Lee, Pritam Ranjan, Garth Wells, and Stefan M Wild. Modeling an augmented lagrangian for blackbox constrained optimization. Technometrics, 58(1): 2016.
[15] Victor Picheny, Robert B Gramacy, Stefan Wild, and Sebastien Le Digabel. Bayesian op- timization under mixed constraints with a slack-variabl augmented lagrangian. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, pages 1435-1443. Curran Associates, Inc., 2016.

---

[16] Benjamin Letham, Brian Karrer, Guilherme Ottoni, Eytan Bakshy, et al. Constrained bayesian optimization with noisy experiments. Bayesian Analysis, 14(2):495-51, 2019.
[17] David Eriksson and Matthias Poloczek. Scalable constrained bayesian optimization. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 730-738. PMLR, 13-15 Apr 2021.
[18] Seyede Fatemeh Ghoreishi and Douglas Allaire. Multi-information source constrained bayesian optimization. Structural and Multidisciplinary Optimization, 59(3)977-991,, 2019.
[19] Remi Lam, Karen Willcox, and David Wolpert. Bayesian optimization with a finite bud- get: An approximate dynamic programming approach. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances Neural Information Processing Systems, vol- ume 29, pages 883-891. Curran Associates, Inc., 2016.
[20] Javier Gonzalez, Michael Osborne, and Neil Lawrence. Glasses: Relieving the myopia of bayesian optimisation. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the I 19th International Conference Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 790-799, Cadiz, Spain, 09-11 May 2016. PMLR.
[21] Jian Wu and Peter Frazier. Practical two-step lookahead bayesian optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Gamettt editors, Advances in Neural Information Processing Systems 32, pages 9810-9820. Curran Associates, Inc., 2019.
[22] Shali Jiang, Henry Chai, Javier Gonzalez, and Roman Garnett. BINOCULARS for efficient, nonmyopic sequential experimental design. In Hal Daumé III and Aarti Singh, editors, Proceed- ings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4794 4803. PMLR, 13-18 Jul 2020.
[23] Shali Jiang. Daniel Jiang, Maximilian Balandat, Brian Karrer, Jacob Gardner, and Roman Garnett. Efficient nonmyopic bayesian optimization via one-shot multi-step trees. Advances in Neural Information Processing Systems, 33, 2020.
[24] Søren Asmussen and Peter W. Glynn. Stochastic simulation algorithms and analysis. In Stochastic modeling and applied probability, 2007.
[25] Philip Heidelherger, Xi-Ren Cao, Michael Zazanis, and Rajan Suri. Convergence properties of infinitesimal perturbation analysis estimates. Management Science, 34: 14:12-1-3 11 1988.
[26) Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Benjamin Letham, An- drew Gordon Wilson, and Eytan Bakshy. Botorch: A framework for efficient monte-carlo bayesian optimization. arXiv preprint arXiv:1910.08 064000,,6633 2019.
[27] Michael A Gelbart, Jasper Snoek, and Ryan Adams. Bayesian optimization with unknown constraints. arXiv preprint arXiv: 2014.
[28] José Miguel Hernández-Lobato, Matthew W Hoffman, and Zoubin Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. pages 918 918-926. Curran Associates, Inc., 2014.
[29] Robert B. Gramacy and Herbert K. H. Lee. Optimization under unknown constraints. Bayesian Statistics 9 (2011), no. 9, 229. eds.
[30] Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient Bayesian optimization. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3627-3635. PMLR, 06-11 Aug 2017.
[31] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Mathias Poloczek. Scalable global optimization via local bayesian optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, Aluhé-BBu,, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
12

---

[32] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005.
[33] J. Mockus, On bayesian methods for seeking the extremum. In Marchuk, editor, Optimiza- fion Techniques IFIP Technical Conference Novosibirsk, July 1-7, 1974, pages 400-404, Berlin, Heidelberg, 1975. Springer Berlin Heidelberg.
[34] Jialei Wang, Scott Clark, Eric Liu, and Peter Frazier. Parallel bayesian global optimization of expensive functions. Operations Research, 68(6): (600):1850-00 1850-1865, 2020.
[35] Pierre L'Ecuyer. unified view of the ipa, sf, and gradient estimation techniques. Management Science, 36(1 1):1364-1383, 1990.
[36] Paul Milgrom and Ilya Segal. Envelope theorems for arbitrary choice sets. Econometrica. 70(2):583-601, 2002.
[37] Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003.
[38] GPy. GPy: A gaussian process framework in python. http://ggchuu..com//hhffllll GPy since 2012.
[39] Nikolaus Hansen. The ema evolution strategy: comparing review. Towards a new evolutionary computation, pages 75-102, 2006.
13


Reviews:
[{"review_id": "X6H5onfBi7R", "reviewer": "Reviewer_8KpE", "summary": "This paper proposes a 2-step lookahead variant of constrained EI [4,5] and builds on the unconstrained 2-step method of [17]. The introduction of constraints causes discontinuity to the acquisition function surface, which requires a novel treatment based on likelihood ratio and a main contribution of this work.\n\nOn the flip side, the empirical evaluation can be considerably improved: \n(1) Given that there are already several constrained BO algorithms proposed in the literature, one would naturally expect real-world experiments to be appropriately motivated and performed instead of simply numerical experiments; this will allow us to know whether the proposed constrained BO method can perform well on real-world optimization tasks. \n(2) Related to point 1, how can we tell whether the performance difference is significant in practice?\n(3) In lines 166-182, the authors have described the importance of being non-myopic in CBO. How can we know whether the better empirical performance of their proposed approach is due to exactly this reason?\n\nThe argument on the importance of being non-myopic in constrained BO is not particularly motivating and requires further clarification:\n(1) In terms of empirical validation, see point 3 above. \n(2) Isn't it possible to modify PF in EIC to explore infeasible points more aggressively? \n(3) On the other hand, supposing that the cost of sampling infeasible points is much higher (e.g., violation of safety or penalty for recommending infeasible points (line 295)), does this make 2-OPT-C less desirable than EIC? \n\nCan the authors discuss how they would scale up to multi-step lookahead instead of simply two?\n\nMy other comments and concerns are detailed below.", "questions": "", "limitations": "", "rating": 5, "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": "POST-REBUTTAL FEEDBACK\n\nI like to thank the authors for their clarifications, some of which should be incorporated into the revised paper to ease readability. I have the follow-up questions on their response, but I am not expecting the authors to answer them with the limited time remaining. The authors can consider them for their revised paper.\n\nA1 : For the portfolio optimization problem, what exactly is the constraint that you have imposed on the portfolio's risk (i.e., standard deviation of the return)? How would the results vary by relaxing/tightening this constraint, depending on the risk attitude of the investor? \nAlso, I understand that there are a number of works that have considered this problem in their experiments, such as the following work considering value at risk and variants in Bayesian optimization and the references therein:\n\nBayesian optimization of risk measures. NeurIPS 2020.\n\nIt is not clear why the proposed approach would be qualitatively and quantitatively better than the existing approaches like the above in this problem involving risk. The authors can consider expounding on this, which will help in the motivation of their work.\n\nA3 : The authors say that \"While one could design a heuristic acquisition function that puts extra weight on exploring infeasible points, this has not been previously proposed in the literature.\" Would this be a trivial modification? If so, the authors are encouraged to perform empirical comparison in this regard.\n\nA4 : The authors say that \"Our paper focuses on problems where the costs of sampling do not vary significantly across the domain.\" Can the authors provide the motivation of their problem in this regard? For example, why does the portfolio optimization problem adhere to this assumption?\n\nA6 : I would encourage the authors to add this assumption to their problem setting so that a reader knows when to prefer their proposed approach.\n\nA12: But delta remains strictly positive based on your proposed sequence. Wouldn't it miss sampling the global optimum then?\n\nPRIOR FEEDBACK\n\nLines 50-52: The authors say that \"This approach [1] requires an extremely large amount of computation to approximate the multi-step lookahead policy well, especially in problems with more than a few dimensions. This limits its applicability.\" This argument appears problematic in three ways: (1) What specific real-world applications have the authors motivated and performed in their experiments requiring higher computational efficiency, considering that the function evaluations in BO problems are typically costly? (2) Would the approach of [1] still be expensive if it is reduced to the context of 2-step lookahead? (3) Does the approach of [1] not trade off well between optimization performance and computational efficiency?\n\nHow can the proposed method be extended to one that is a truly batch mode where the second stage involves a batch of also q points to be evaluated?\n\nIt would be preferable that the authors specify exactly the form of the posterior distributions for E_0 and E_1 in the equation after line 152 to ease understanding. For example, the E_0's on the LHS and RHS do not appear to correspond to the same posterior distribution, albeit conditioned on D.\n\nPage 4: Can the authors explain why do the formulations for constructing 2-OPT-C(X_1) not consider (...)^+ like that of EI? \n\nLine 157: By setting delta > 0 in the theoretical analysis, isn't it possible that the proposed acquisition function would miss sampling the global optimum?\n\nCan the authors provide a time complexity analysis for optimizing 2-POT-C?\n\nSection 6: There is a lack of description of the three benchmark problems: Do the unconstrained conventional and non-myopic BO algorithms perform poorly in them?\n\nSection 6.1: Can the authors give the mathematical expression of the median utility gap? \n\nLines 293-296: Do the authors mean that they follow the setup of [1] by penalizing infeasibility of recommended point?\n\n\nThe following references on conventional and batch BO with multi-step lookahead are missing:\n\nSequential Bayesian optimisation for spatial-temporal monitoring. UAI 2014.\n\nGaussian process planning with Lipschitz continuous reward functions: Towards unifying Bayesian optimization, active learning, and beyond. AAAI 2016.\n\nNonmyopic Gaussian process optimization with macro-actions. AISTATS 2020.\n\n\n\nMinor issues\n\nLine 75: difficulties requiring created by\n\nLine 147: italicize D", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the summary for the limitations of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~6"}, "extra_text": {}}, {"review_id": "Q5EXI0A3OT", "reviewer": "Reviewer_HPhn", "summary": "This paper deals with non-myopic BO under inequality constraints. In particular, recent results on the efficient approximation and optimization of the two-step expected improvement criterion are revisited in the considered constrained case, leading to an efficient gradient estimation scheme relying both on importance sampling and on a clever application of the envelope theorem. Experimental results confirm that the developed method with the proposed importance distribution perform better than baseline approaches on the considered examples. ", "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 very neat work. While I think it deserves to be published as it adequately addresses an important class of BO problems, my main reservation would be that it is relatively incremental with respect to „Practical two-step lookahead Bayesian optimization“ (Wu and Frazier, Neurips 2019). Indeed both key ingredients of a) the clever use of the envelope theorem, and b) the use of importance sampling in a related context of acquisition function evaluation/differentiation are already presented there, yet in an unconstrained setting. Considering this, the current paper, while being excellent in several regards, somehow feels like a nice extension of the former paper. Spending less room on the basics (that can be found in the 2019 paper or that amount to routine calculations to be placed for instance in appendix) and more on the actual novelties (that could be further developed, e.g. choices regarding importance sampling) could help making this nice paper an outstanding one. Also, relations to some more developments in this very active field of research could be further explored, for instance with the approach of „Efficient Nonmyopic Bayesian Optimization via One-Shot Multi-Step Trees“ (Jiang et al., Neurips 2020) and the strategies of „Efficient Rollout Strategies for Bayesian Optimization“ (Lee et al.. UAI 2020).\n\nPost response from the authors: increased my score by one unit. Congrats on the convincing responses and promising test case results. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Ok", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "2GCi-NIL_A", "reviewer": "Reviewer_uDRU", "summary": "The paper proposes a method for nonmyopic BO with inequality constraints. The method leverages on 2-step expected improvement with constraints and utilizes reparameterization trick to optimize the acquisition function.", "questions": "", "limitations": "", "rating": 6, "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 clarity and the structure of the paper could be greatly improved. The problem setting is not well defined which makes assessing the contributions of the paper challenging. The key concepts and methods are either not not formally introduced (nonmyopic problems,IPA and SAA methods),  introduced in different papers (problem settings for experiments) or introduced in Appendix (Assumption 1 in Theorem 1). Therefore, I believe the paper requires significant re-writing and cannot be accepted in the current form.\n\nA few questions to the authors:\n\nline 138. what kernel is used in the problem?\n\nLine 147. x_2 is a single point or a batch of points? The first stage selects a batch of q points, but the second one seems to select a single point.\n\nLine 149 - best with respect to what?\n\nLine 152 shouldn’t f_1* be a random variable? Then how it is moved out of expectation?\n\nThe acquisition function 2-OPT-C doesn’t involve constraint function g at all, so how are the constraints evaluated?\n\nLine 169. What does “tight” mean in this context?\n\nLine 174 - how is the value of 50% obtained?\n\nLine 190 Am I right  that the authors consider noise-free case of BO?\n\nLine 255. Putting Assumption 1 to appendix makes the submission not self-sufficient.\n\nLine 269. The experimental settings are not well-defined.\n\nLine 277. What is the utility gap?\n\nLine 292. Is such comparison with Rollout fair?\n\n\n-- Post-rebuttal\n\n\nI would like to thank the authors for answering my questions in their response. I am quite impressed by the amount of work authors have completed during the rebuttal phase in order to improve their paper, and I will increase my score to 6. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "-YIEf-q8pht", "reviewer": "Reviewer_Strq", "summary": "\nThis paper introduces a two-step look-ahead expected improvement policy for Bayesian optimization with inequality constraints. The authors argue that infinitesimal perturbation analysis and sample average approximation methods create discontinuities during the acquisition function maximization of two-step expected improvement for BO with inequalities. The authors propose a solution based on a likelihood ratio approach that computes an unbiased estimator for the gradient of two-step expected improvement with constraints (Theorem 1). Empirical results show that the proposed method is effective and outperforms baselines.", "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": "**Strengths**\n\nBayesian optimization with constraints is an important topic for the NeurIPS community.  The authors justify the importance of the paper by describing the limitation of the standard approach (Figure 2). The construction of the unbiases estimator is a little bit hard to follow, but I think I understood the overall idea.\n\n**Weakness**\n\nThis paper would be more substantial if the authors tested their method on more practical functions. Experiments were conducted over only three functions. Why not test on the Reacting flow problem (P4) too [1]? \n\n**After rebuttal**\nThanks for the response. I think adding this example to the paper would make it considerably strongger.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript considers the development of nonmyopic Bayesian optimization policies for constrained optimization. Although nonmyopic policies have repeatedly shown success in unconstrained settings, there are several challenges to overcome in the constrained setting.

Over the course of the discussion phase, the reviewers came to the consensus that this paper was notable, offered a significant contribution, was of interest to the NeurIPS community, and could serve as a springboard for future work.

In preparing the final version of the manuscript, I strongly suggest that the authors take the reviewers' suggestions into account. Further, the reviewers agree that the the portfolio optimization example from the discussion should be incorporated into the paper, as it was both relevant and convincing.
Decision: Accept (Poster)