SnAKe: Bayesian Optimization with Pathwise Exploration
Authors: Jose Pablo Folch
Shiqiang Zhang
Robert Matthew Lee
Behrang Shafei
David Walz
Calvin Tsay
Mark van der Wilk
Ruth Misener
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bayesian Optimization
Path-based
Travelling Salesman
Chemistry Applications
Cost-aware

Abstract: "Bayesian Optimization is a very effective tool for optimizing expensive black-box functions. Inspired by applications developing and characterizing reaction chemistry using droplet microfluidic reactors, we consider a novel setting where the expense of evaluating the function can increase significantly when making large input changes between iterations. We further assume we are working asynchronously, meaning we have to decide on new queries before we finish evaluating previous experiments. This paper investigates the problem and introduces 'Sequential Bayesian Optimization via Adaptive Connecting Samples' (SnAKe), which provides a solution by considering large batches of queries and preemptively building optimization paths that minimize input costs. We investigate some convergence properties and empirically show that the algorithm is able to achieve regret similar to classical Bayesian Optimization algorithms in both the synchronous and asynchronous settings, while reducing the input costs significantly. We show the method is robust to the choice of its single hyper-parameter and provide a parameter-free alternative."

SnAKe: Bayesian Optimization via Pathwise Exploration
Jose Pablo Folch Imperial College London London, UK
Shiqiang Zhang Imperial College London London, UK
Robert M Lee BASF SE Ludwigshen, Germany
Behrang Shafei
David Walz
Calvin Tsay
BASF SE Ludwigshafen, Germany
BASF SE
Imperial College London London, UK
Ludwigshafen, Germany
Mark van der Wilk Imperial College London London, UK
Ruth Misener
Imperial College London London, UK
Abstract
Bayesian Optimization is a very effective tool for optimizing expensive black-box functions. Inspired by applications developing and characterizing reaction chem- istry using droplet microfluidic reactors, we consider a novel setting where the expense of evaluating the function can increase significantly when making large put changes between iterations. We further assume are working asynchronously, meaning we have to select new queries before evaluating previous experiments. This paper investigates the problem and introduces 'Sequential Bayesian Opti- mization via Adaptive Connecting Samples' (SnAKe), which provides a solution by considering large batches of queries and preemptively building optimization paths that minimize input costs. We investigate some convergence properties and empirically show that the algorithm is able to achieve regret similar classical Bayesian Optimization algorithms in both synchronous and asynchronous settings, while reducing input costs significantly. We show the method is robust to the choice of its single hyper-paramete and provide a parameter-free alternative.
Introduction
We introduce a method for black-box optimization that keeps step-wise input variations as small as possible. A black-box function is expensive to evaluate (with respect to time or resources), and we do not have access to gradients. Classically, black-box optimization finds an optimum by sequentially querying the function. We study variation of this problem, with two important differences. First, we introduce the idea that large changes in inputs, between iterations, cause the function to become more expensive evaluate. Second, we do not assume observations available immediately: delay between querying the function and getting result leads to asynchronous decision making.
As motivating example, consider a droplet microfluidic reactor 4 such a reactor, we can quickly pump in chemicals, expose them to certain conditions, and collect the results of our experiments as they exit. However, large changes in temperature mean that the reactor no longer steady-state, and this makes the evaluations unreliable until the system stabilizes.
(see Figure in Appendix). In
Corresponding author: jose. fww.h116iiiperial.l....m uk
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Smaller changes can maintain a "quasi-steady state", as the system is easier to stabilize. Further, we have wait for droplets to exit the reactor before obtaining observations.
More broadly, consider optimization requiring spatially continuous exploration. Black-box optimiza- tion has been investigated for optimal placement of pollution sensors [17], and machine learning methods for detecting the sources of pollution have been developed [30]. Mobile pollution readers, such as those used by AirQo [https: / / /www. airqo. wwt//eeutubt// would face similar challenges if black-box optimizers were used to track the pollution sources. Samaniego et al. [ show a more concrete example where autonomous vehicles use black-box optimizers to monitor and track water contamination sources in the Ypacarii lake in Paraguay.
Classical Bayesian Optimization (BO) 20 provides effective solutions black-box optimization; however, physics-based limitations are usually not taken into account (50) Typically BO follows a myopic approach, in that BO chooses the next query based only the current state of the surrogate
model. Classical BO reduces uncertainty in unexplored areas and then returns to promising areas
with no regard for the distance between consecutive query points. This means that BO will incur very high input costs.
However, having zero changes in input space is obviously not good solution. After all we want to explore the search space to find the optimum point. We seek an algorithm that preserves the essence of Bayesian Optimization. Consider scenario where we know a large number of inputs we want to query. In this case, we could simply order the queries to attain the smallest input cost. A good solution would simply require selecting large number of queries, creating an ordering, and then following the path defined by the ordering. Once we start obtaining new information, we could update our beliefs and update our optimization path.
This paper proposes Sequential Bayesian Optimization via Adaptive (K)Connecting Samples (SnAKe). Just as the snake grows by carefully eating items in the classic arcade game, SnAKe optimization path grows from carefully adding queries to the evaluation path.
2 Related Work
PProcess- constraiied Batch Bayesian Optimization' (51), is the closest analog to our setting of BO with input costs. Vellanki et al. [5T] navigate the physical limitations in changing the input space by fixing the complicated inputs for every batch. Rather than fixing the difficult-tochhange inputs, we penalize large input variations line with the costs (time and resources) of changing conditions. SnAKe decides when to make expensive input changes. Recently, Ramesh et al. [3 consider similar cost setting to ours, inspired by applications to wind energy systems. Waldron et al. [2 compare the use of transient variable ramps (small input changes in a pre-determined manner) against a full steady-state design of experiments approach for learning parameters of chemical kinetic models. They show that the transient approaches give less precise estimates, but much faster. SnAKe combines the best of both worlds, automatically designing experiments while keeping input changes small.
31 optimizes regret with respect to cost per iteration. These costs, which are fixed throughout the BO process, arise when some regions of the input domain are more expensive to evaluate than others. Similar ideas appear in Multi-fidelity BO 21 3 where cheap approximations for the objective function are used. Bogunovic et al. 6 combines cost-aware and level-set estimation approaches to solve environmental monitoring problems. Diverging from prior works, our setting does not assume that different regions incur different costs. Instead, SnAKe addresses the setting where the difference between adjacent inputs defines costs. The query order changes the cost, therefore we focus on optimization paths instead of optimization sets.
aCare Bayesian Optimization'
28
The baseline of Cost-aware BO, Expected Improvement per unit Cost (Elpu), defined as EI(x)/ /Cott (I(=))Cost((z) is not directly applicable to our setting because the cost of not changing inputs, i.e. choosing 2, = 11 is zero. We can instead use:
yElpu(z) = EI(x)/(7 + 22))(22
(1)
with no obvious way to choose it, (b) Eq. T effectively penalizes the acquisition function far away from the data, so near local optima we only penalize exploration and may over-exploit, (c) asynchronous extensions have a tendency to encourage batch diversity, so we introduce a new trade-off between penalizing locally and far away. As we shall see, SnAKe shows robust results with just one hyper-parameter.
Three main issues: (a) Eq. introduces new

---

Look ahead Bayesian Optimization [2 15 26 choice less myopic. We could use it to select the inputs to query, as we could simply -oead at what any classical BO would choose and then order the queries accordingly. However, one is only able to look ahead for few iterations, due the computational complexity looking far ahead into the future S [4]. For example, Lee et al. 29 combines Markov Decision Processes 38), look-ahead and cost-aware ideas, but is limited by the short time horizons rollout can handle. Reinforcement Learning
considers possible future queries to make the current
4 can be used, but it requires access to dedicated training environment. Mutný et al. show how similar ideas can be used for trajectory optimization in environmental monitoring.
A computationally cheaper alternative that allows us to select many inputs to query is Batch Bayesian Optimization (BBO) 2 I.. BBO is the setting where we are able parallelize function evaluations, and as such we want to select multiple queries simultaneously. González et al. [15] and Jiang et al. [9] link BBO with look-ahead BO, using a Local Penalization method [14] and Expected
Improvement (q-El) 13 respectively. Unfortunately, they restrict themselves to smaller batch sizes
(q S 15) due to computational expense. Asynchronous Bayesian Optimization 22 addresses the
problem of choosing queries while waiting for delayed observations.
3 Methods
3.1
Problem Set-up
We consider finding the maximum, x² = arg max,ex f(x) of a black-box function, f. where X' is a compact subset of Rdd We assume / is continuously differentiable and expensive to evaluate. We seek the optimum point while keeping the number of evaluations small. We evaluate the function sequentially, over a discrete and finite number of samples, t = 1..... T- For every query, It, we obtain noisy observation of the objective, 1/2 fxx,) + Te, where 7h NN(0, s2) is Gaussian noise.
We assume there is delay, Edeaays between choosing a query and getting an observation. So our data-set at iteration t is given by D, {(x;, i 1...., Ldeioy 1]. If we set ldelay 0, we revert to classical sequential Bayesian Optimization, otherwise we are in an asynchronous setting.
Finally, we assume there is known cost to changing the inputs to our evaluation, C(r,, Z(41). We use simple regret, SR, = fx=) - mI..= f*;) as the performance metric. We want to minimize regret, or equivalently, maximize f, for the smallest possible cumulative cost, Σ C(a,, It+1).
We note that the problem definition is invariant to cost scaling relative to the objective, because an optimal trajectory will be defined solely by the shape of the function. Current cost-aware methods not scale invariant, and shall see, SnAKe first chooses which points query and then finds the most cost-efficient way of selecting them, making the method invariant to scaling of the cost.
As is common in Bayesian Optimization, we will model the black-box function by putting Gaussian Process (GP) prior on f ~ GP oō). Since we have Gaussian noise, the posterior. D is also a GP, whose mean function, (e()), and covariance function, Kr(,, -), can be calculated analytically 40
3.2 General Approach
For our general approach, we will seek to create a large batch of queries that we want to evaluate, and then plan-ahead whole optimization path. This is useful for three reasons: (1) it allows us to order the queries in a way that reduces input cost. (2) It allows us to deal with any delay in getting observations, because we can pre-select future queries. (3) It remains computationally feasible to plan-ahead even for very large time horizons. We can follow this ordering or path until new information available, after which we will update our path.
While we will provide a specific way of creating, planning and updating the paths, we note that the general ideas can be extended suit different settings. For example, Appendix shows how to alter SnAKe to simultaneously optimize multiple, independent, black-box functions.
3.3 Creating Batch Through Thompson Sampling
We need to produce batches that are representative of the current state of the surrogate model. In addition, the method should allow for big batch sizes, since want to produce batches as big as our
3

---

budget (which is usually much larger than the batch size most methods consider). For example, in micro-reactor, we might be interested in batches that contain hundreds of points 49
Kandasamy et al. [22 offers a promising solution where every point in the batch is independent. The method is based on T'hompson Sampling, which uses the GP's inherent randomness create batch. Each batch point is chosen by drawing a realization of the GP, and optimizing it. The queries will fill the space, and they are more likely to be on promising, and unexplored areas. It should work very well in our context given we expect our initial batch sizes to be very large, so the sample should be representative of the current state our surrogate model.
3.4 Creating Path via the Travelling Salesman Problem
After selecting a batch of queries, Pt = into the batch, where the edge weights are the cost for changing imput to another. We then find the shortest path that visits every point, i.e., we solve the Travelling Salesman Problem (TSP) 4 Section 3.9 discusses the computational cost.
we order them. We do this by embedding a graph
Mathematically, we define the graph G (V, E. W), with V {i E I..... 2 Pt).
E' = ((i,)) j E I,... T. and W {wi = C(a, (())) (i.j) E E}, where is the number of batch samples. We solve the TSP in G to obtain our latest optimization path. A simple example would be to try to minimize the total distance travelled in input space, by selecting the Euclidean
norm as cost (z,,, 2 - 1++1/|
3.5 Naively Updating the Optimization Path
After updating the GP with new observations, we want to use this information to update our path. We propose updating our strategy by creating new batch of points.
At iteration I, the remaining budget has size T I. We first propose sampling - - queries through Thompson Sampling, and then solving the Travelling Salesman Problem. However, we show this leads to the algorithm getting 'stuck' in local optima. This is because every time we re-sample, we naturally include some exploitation in the batch, and this exploitation will always be the next point chosen by the TSP-we we will never reach the exploration algorithm steps. Figure la shows an example.
6 8
5.0
1.0
-15
Sandian mrea
6.2-fond Destion
-1.
mean
-10
Escace Prediction
00
022
0.4 16 0.
0.2
0.4
0.6
0.2
0.6
08
(a) Naively Resampling
(b) With Point Deletion
(c) Optimization paths.
Figure 1: Effect of Point Deletion for ordering- based BO. (a) and (b) show the maximization objective and the underlying surrogate model, with black crosses representing queries and observations. (c) shows the optimization paths. Naive resampling gets stuck in the local optimum (x 0.16) whereas Point Deletion escapes the local solution. We also show the predicted escape iteration, Tp (after estimating p 0.74 in Appendix D.I.) which accurately predicts the algorithm behavior in this simple example.
3.6
Escape Analysis
To try and solve the convergence problem introduced by naive resampling, we brieily analyze it. This analysis assumes receive noise-less observations. However, all sampling can be done in the presence of noise by calculating the corresponding posterior. We note that this section will provide intuition for the next step of the algorithm, however, we are not providing rigorous theoretical justification for the step or proving any type of regret bounds. We focus on Thompson Sampling.
Definition 3.1. (Thompson Sample) We say x is Thompson Sampled, and we write x! ~ Tt, if:
(8)
arg max f (x), where f! GP(m,, me Dt)

---

Note that the sampling distribution GP(M, Kel De) changes at each iteration.
One particular concern, diagrammed in Figure la is the possibility of the method being stuck in certain area. Let Ba(a) be a Euclidean d-ball centered at and assume that xt-1 E Ba(a). We further assume two more things: (a) we resample the batch at every iteration, and (b) the TSP solution, or any approximation, will always choose a point in (a)a) to be the next step, if there are any. These assumptions represent the worst-case scenario for trying to escape a local optima.
Definition 3.2. (Non-escape Probability) We define the non-escape probability, pt, at iteration 1, as the probability of a Thompson Sample falling into (s(a). That is, for xt (8) ~ Tp:
Pt- = P(x ()) E BB(a)) PP[I,, all S 56)
Let P.- = (x) (1) the sample, N₂ = IP& Ba(a)). We are guaranteed to escape if no sample falls in (a), so we say we have fully escaped if x, (f)
(T-() Tt i.i.d.. Of particular interest to us, is the number of 'non-escapes" in .... Jt
J.
& (a(a) vi.
Remark 3.3. Note that N₂- ~ Binomial(T -t, pt) as all the samples are mutually independent,
therefore the probability of fully escaping is IP(N, = 0) = (1 p.) ) This means we can only expect to fully escape if pr. is very small.
Therefore we are interested in the behavior of ps as we gain more information about f in Bs We now consider the cireumstances under which pt becomes very small:
Areas without stationary points: Consider the case when our objective f does not contain stationary point in B3(a), Then the maximum of f on the closure of the ball, Ba(a), must lie on the boundary of the ball. In particular, if we assume that our GP model has no error in (a), and assuming continuity of sample paths, then the non-escape probability must be zero, Pt 0.
Intuitively, the area itself contains enough information to ensure, with complete certainty, that the global optimum does not lie in the area. We hope that, as we collect information inside areas without stationary points, Pt + O. and we will eventually leave them with small probability of returning. Appendix D.2 shows an example of this happening very fast.
Areas with stationary points: Areas with stationary points pose much bigger problem. We will restrict our arguments to local maxima, since this is where we have observed the problem. Assume that f has a local optimum in (a), higher than any other have observed before. In this case, any sample taken from a Gaussian Process with no error in Bg(a) will have a local maximum inside (a) and therefore it is possible that this local maximum is the global solution.
As we increase the information inside the area, Pt is not guaranteed go down to zero This makes intuitive sense; the only way of knowing if a local optimum is not global optimum is by sampling away from therhereeore with limited information we will allocate a certain probability to the global optimum being inside (a). We include clear example where Pt p 0 in Appendix D.I
Sampling consistently in a promising area is not necessarily a bad thing, indeed we want to exploit near possible global optimum candidates. However, the question then becomes, how long will it take us to leave local optimum? Recall the probability of fully escaping (1 pt) pT)T-+ and therefore will be increasing as t increases, even if Pt is (almost) constant.
Remark 3.4. Assume that + p > O, and that we have a high escape probability after te iterations, i... (1-p)² "0)"'++ to large, leaving us T'- to iterations to explore the rest of the space. If we increase our budget from T to T', we will not have high probability of escape until (1 - p) T' -1-p)" i.e., / = 7" T + le. This leaves us with T' - (T" T + te) = T Le iterations to explore the rest of the space. Note that this is independent of T", meaning that increasing our budget does not increase our budget after leaving Bs(a)! Rather, it only means we will be stuck in (s(a) for longer time. This is very concerning as the method will be very myopic; if it finds a local optimum, it is likely that it will spend very large amount of the budget exploiting it.
3.7 Escaping with e-Point Deletion
Intuitively, the convergence problem stems from the constant resampling, because in every iteration resampling is reintroducing exploitative points. We seek way of making sure that the samples
5

---

used by the algorithm to create paths take into account the previously evaluated designs. Penalizing the samples via distances previous queries seems like simple solution, c.g., similar local penalization []4]. However, penalization introduces the need to carefully tune the strength of the penalization so that we can still exploit optima and remain cost-effective the parameterization
nontrivial.
Around a local maximum, if we assume that p: - p > then we can interpret p as the probability that the global maximum lies on the ball Bs(a), as such, we focus on a method that has the property of exploiting the promising area for Tp iterations (that is, the total budget weighted by the probability). To achieve this, we propose creating total of T samples, and then deleting batch points that are similar to previously-expee explored points (i.e., we remove excess exploitation introduced by resampling). Algorithm I which we term e-Point Deletion, still allows us to exploit local optima if we sample many points near them, however, should eventually move on.
Two points to note: (a) Point Deletion uses the Fuclidean norm, and it is independent of the cost function. This is because we are trying to escape local minima of simple regret. (b) After the deterministic removals, it is likely the batch size is still larger than our remaining budget, so we balance it by randomly removing points from the batch.
Algorithm 1 e-Point Deletion
input: New proposed batch P. (size T), set of already queried points Qe (size t), and deletion distance c
for E Q: do
d <- min || =x'l
if d < then
# find the closest point to the query x in the new batch
$ arg || |z==z/) x'|
else
# else pick random sample x + RRnddm (P,)
end if
# remove said point from the batch
P: < P. M+)
end for output: A batch Pt (size T f)
c-Point Deletion allows to escape local optima by directly increasing the probability of fully escaping without changing pt. Let qe be the number of previously queried points inside the ball, and set 26. Indeed, it follows that we will escape if N, ge. (as qi samples deleted due to previously queried points) which is much better than requiring N = 0.
guarantced to be
Due to over-sampling, the expected number of 'non-escapes' is given by E[N, P.T. Around local maximum, if we assume that P: -> p > O, and hence, p.T pT, then we can reasonably expect an escape when q: = pl', that is, we will exploit the local maximum for approximately pf iterations. This time we leave T - 4: = T(1 - p) extra iterations to explore the remaining space! Increasing the budget will benefit both the exploitation and the exploration instead of only the former (in contrast with Remark3.44.
Figure I gives an empirical example where we use Point Deletion, with e = 0.1, to escape local optimum. We observe the expected behavior from our brief analysis. For Point Deletion, we calculate the escape prediction as pT ~ 74, using P z 0.74, which we estimated in Appendix D.1 We can see that without Point Deletion, we remain stuck in the first local optimum.
3.8 SnAKe
Algorithm 2 which we dub 'Sequential Bayesian Optimization via Adaptive Connecting Samples' (SnAKe), combines the ideas of previous sections. Figure diagrams the most important steps of SnAKe. Section I develops an effective, parameter-free alternative the choice of e.

---

Note there is no requirement for data to be available immediately following querying. If tdlla > 0, we can simply stick to the latest path. It works without modification on the asynchronous setting. This is vital since we were inspired by chemical experiment design which can exhibit asynchronicity. We also note that the problem is invariant cost scaling, as the batch creation and point deletion steps are independent of the cost, and the solution to the Travelling Salesman Problem is also acale-invariant.
Algorithm 2 SnAKe
input: Optimization Budget, T. Deletion constant, e.
begin: Create initial batch, Pu. uniformly. Choose starting point zi-- Qo + } Create initial path, So. by solving TSP on Po.
for t = 1, 1,2.3, 3.., T.,
Check if any running evaluations are finished
if there are new observations then
Update surrogate model
Create batch of size using Thompson Sampling, Pt-1
Pa-1 c-Point Deletion(P:-1- Qt-1)
$ TSP(P,, source #x-1) M2²-13
S Qt-1 US
end if
Choose next query point from schedule: 2t +- St
Qi + Q--1 U {xz}
Evaluate (xx)
end for
0.4
actual optimization path
Thompson samples points to delete
optimization path deleted points
planned optimization path
2.0.
20.3
0.4
0.5 0.6
0.5 0.5
(a) Optimization path at 10 (b) Sampling & Deletion Step
(c) Optimization path f 11
Figure 2: Graphical example SnAKe behavior a full iteration if new information available.
The underlying function is Branin 2D. The feasible set is [0, 1]2
do not see all the samples or the complete path with this zoomed-in view. (a) The red line shows the already- path. The blue path shows our future plans. (b) For each query, we can see the e-ball under which the deletion step is deterministic. We plot the Thompson Samples as dots, the accepted ones black and the deleted ones in green. (c) The new path is in blue and the points ignored (due to Point Deletion) in green. Note the higher concentration of samples in what the model considers a promising area.
3.9 Computational Considerations
to efficiently sample the GP and optimize the samples using Adam [ The optimization step may be expensive, but it highly parallelizable if required. We heuristically solve the Travelling Salesman Problem with Simulated Annealing [24 and use an adaptive grid reduce the number of samples away from our current input. The grid consists of the closest N; samples to our current input; the remaining samples are assigned to one of N, points in a global grid. Coarsifying the placement of the far- far-away points effectively ignores detailed paths far away from our current input. These far-away points are not important to the problem, as long as we resample frequently enough. We introduce two hyper-parametert (N,, N₁), but they should not impact the solutions assuming N; is reasonably larger than any possible delay. With these modifications, we were able to comfortably run all experiments in a CPU (2.5 GHz Quad-Core Intel Core i7), where SnAKe shared wall-time similar to Local Penalization methods. Appendix E.T gives more details.
We use Wilson et al. 5
7

---

Experimental Results
For all experimental results we report the mean and the standard deviation over 25 experimental runs. We give the full implementation details and results in Appendix D and respectivvlly Classical BO methods are implemented using BoTorch t and GGyTorch I The code to replicate all results is
available online at httpps///github com/ cog- imper al SnAKe
In all experiments, we examine SnAKe for e 0, 0.1, and We further introduce a parameter- free alternative by adaptively selecting to be the smallest length scale from the GP's kernel, and denote Ł-SnAKe. SnAKe proves to be robust to non-zero choices of e. We conjecture this happens because of Thompson Sampling's exploitative nature K5] so all excess exploitation is concentrated on very small area. For e 0 we observe very low cost, at the expense of some regret.
Across all experiments we can see how SnAKe can traverse the search space effectively, constantly achieving good regret at low cost. While other cost-aware methods may also achieve good perfor- mance, they are very inconsistent, suggesting they require careful tuning. SnAKe achieves good, robust results with single syper-parameter We do highlight that SnAKe performs best when there are enough iterations for the samples to adequately fill the search space: this is highlighted by poor performance Perm10D and by ordinary performance in low-budget experiments (see Appendix where we include performance comparisons for different budget sizes, 7).
Senda
londom
1002
1-0 hakde
(ogiRt)
log Regrett
Uiuu
250
Cost
Ieeation
Iteration
(a) Evolution regret against input cost. We can see that SnAKe is able to achieve the best regret for low cost.
(b) Evolution regret with itera- tion number. SnAKe's final regret is
(c) Evolution input cost with iter- ation number. Low cost achieved by ElpuLP, SnAKe and the TSP. ordered Random optimization.
comparable with classic BO meth- ods, and better than ElpuLP.
Figure 3: Results experiments on the SnAr chemistry Benchmark. SnAKe achieves the best regret out of all low-cost methods. The bounds are created from + half the standard deviation of all runs. The best performer, E-SnAKe, is parameter-free.
4.1 Synthetic Functions
Sequential BO This section examines the performance of SnAKe against Classical BO algorithms.
We compare Expected Improvement (EI) B3], Upper Confidence Bound (UCB) 46), and Probability of Improvement (PI) (5 We compare against Expected Improvement per Unit Cost 44 (Elpu) as (TrEI). We also
introduced in Eq. T with y = 1, and with Truncated Expected Improvement 41
introduce simple baseline, where create random Sobol sample, and then arrange ordering by solving the TSP, and never update the path again. We do this for three classical benchmark functions, and six total in the Appendix F.I.I We set the cost function be the 2-norm distance between the inputs. Figure 4 shows the results in the top row.
Asynchronous BO We explore the asynchronous setting, comparing Local Penalisation with UCB (UCBwLP) I Thompson Sampling (TS) [22], and the same Random baseline from the sequential setting. We also test on Elpu with Local Penalisation (ElpuLP), with y 1. The results are shown in last two rows of Figure
4.2 Reaction Control on SnAr Benchmark
We test our method on a real-world, SnAr chemistry benchmark [S]
We control four variables; equivalents of pyrrolidine, concentration of 2,4 dinitrofluoroheeenze at reactor inlet, reactor tempera- ture, and residence time. We assume changing temperature, concentration and residence time incur an input cost, owing to the response time required for the reactor to reach steady state. We assume

---

3,8
UCB
og (Regret)
og (Heggeet)
(Hegrett
03
68
-05
-10
-22.5
Cost
Cost
Cost
(a) BraninnD
(b) Hartmann3D
(c) Hartmann6D
log (Regrets
log (Regret)
log (Regrett
7.5
-16-
20
Cost
Cost
Cost
(d) (astan)Ha
(e) (async)
(f) (async)Ackley4D
6.0
og (Regret)
og (Regret)
og (Regret)
-5.0
20
(g) (async))ichaclwiee21)
(h) (asynn)Hatmann33)
(i) (async)Hartmnn44D
Figure 4: Synthetic experimental results. The first row represents three of the synchronous bench- marks. The last two rows correspond to asynchronous experiments with ddelag = 25. We plot the average loggregret) achieved against the cost spent. For every experiment, T 250, and limit the æ-axii to the maximum cost achieved by SnAKe or Random. Ê-SnAKe is the parameter-free free version. SnAKe consistently achieves good regret against at cost. The bounds are half the standard deviation of 25 different runs.
the reactor as a first-order dynamic system, where the response to changes in input given by:
(x.)): = (2x); + (1 - -/am (/a))/())))))))) (Arz);
where s denotes the time after experiment x, is finished, (az); denotes the ith variable of the tth experiment, (Art); = (I++1); - (mt);, and a; is the system time constant. We define quasi-steady state using an absolute residual 8g i.e. ((x,); - (x S 3. For input changes smaller than 8, we assume a linear cost, defined by parameter %. Combining with the response time from 3
C, Te+1) 7/s min / ( 2.1) + max (0, as log (1A021/28.) xel/2:)
(4)
assume that we can change variables simultaneously, so total input cost is simply the longest response time within given set of input changes. That is, C( where Io is the index set of the control variables. We implement the simulation using the Summit package [0O. More details be found in Appendix [E.7.6] We set delay of tdelay 25, and optimize for T 100 iterations. The results the experiment can be seen Figure
maxier. C,(,,,I=11)
4.3 Finding Contamination Sources Ypacarai Lake
As second real-world example that exhibits costly input changes, we investigate an alternative to the case study introduced by Samaniego al. 41 Autonomous boats are used to monitor water quality in Ypacarai Lake in Paraguay. We consider three different objectives, illustrated in Figure [] created using the Schekel benchmark function (as in [41)). Each objective could correspond to measure of water quality, such pH, turbidity, CO2 levels, many more. We consider the problem

---

Objective 1
Objective 2
Objective 3
1.2
1.6
1.1
1.4
0.9
1.2
1.2
0.6
0.8
1.0
1.0
0.6
0.0
0.4
0.6
0.6
0.2
0.4
0.4
0.2
0.0
0.0
0.4
0.6
0.8
1.0
0.0
0.4
0.6
0.8
1.0
0.0
0.6
0.8
1.0
0.0
Figure 5: Visualization of Ypacarai Lake, and the objectives we optimize over. We show an example of Sn optimization path on the simultaneous optimization problem (see Appendix
Table I: Ypacarai results. We present the average regret from 10 runs + the standard deviation, multiplied by 10a O1, O2, 03 correspond to the different objectives. All runs are terminated after the cost exceeds 10 units (approximately 100 km). SnAKe is the best performer in 2 out of 3 objectives.
Regret 01
Regret O2
Regret O3
TrEi
0.475 0.596
0.118 0.100
0.076 0.050
Elpu
0.225
0.068 0.073
0.071 0.049
SnAKe
0.074 0.063
0.109 0.186
0.036 0.048
of finding the largest source of contamination in the lake by maximizing these objectíves. The cost between queries relates the boat physically moving from one place to another. We assume that the boats can travel 10 units, which corresponds to approximately 100km (fuel limitations), and no observation time delay. We run optimization runs on each objective and shows the results Table
Conclusion and Discussion
This paper introduces and proposes solution to the problem of optimizing black-box functions under costs to changes in inputs. We empirically show that the regret achieved by our method is comparable to those of classical Bayesian Optimization methods and we succeed at achieving considerably lower input costs, while being particularly well suited to asynchronous problems. Examples of further work include extending the algorithm multiple 'SnAKes' run in parallel, extending it to the classical multi-objective setting, c.g., using variations Thompson Sampling 77.
This setting, with input costs penalizing experimental changes, makes major step towards automating new reaction chemistry discovery, e.g., in line with the vision of Lazzari al. [27]. We substantially decrease experimental cost with respect to classical black-box optimization, e.g., as used by Fath al. [9] and McMullen and Jensen [2. the real-life SnAR benchmark, SnAKe spends 45-55%
of the cost while making similarly strong predictions to classical BO. The synthetic benchmarks and pacaraii Lake example offer similar advantages.
Acknowledgments & Disclosure of Funding
JPF is funded by EPSRC through the Modern Statistics and Statistical Machine Learning (StatML) CDT (grant no. EP/S0231 and by BASF SE, Ludwigshafen am Rhein. SZ was supported by an Imperial College Hans Rausing PhD Scholarship. The research Physical Sciences Research Council (EPSRC) Fellowships to RM and CT (grant no. EP/P016871/1 and 5P/T00157//1). CT also acknowledges support from an Imperial College Research Fellowship.
funded by Engineering &
We would like to thank the reviewers and meta-reviewers throughout the whole peer review process for their time, attention, and ideas, which led to many improvements in the paper. Discussions with colleagues the Imperial Department Computing led to the ideas of e-Point Deletion and the nonparametric &-SnAKe. Linden Schrecker improved our understanding of the chemistry application.
10

---

References
[1] A. Alvi, B. Ru, J.-P. Calliess, S. Roberts, and M. A. Osborne. Asynchronous Batch Bayesian Optimisation with Improved Local Penalisation. In Proceedings of the 36th International Conference on Machine Learning, pages 253-262, 09-15 Jun 2019.
[2] J. Azimi, A. Fern, and X. Z. Fern. Batch Bayesian Optimization via simulation matching, In Advances in Neural Information Processing Systems, pages 109-117. Citeseer, 2010.
[3] M. Balandat, B. Karrer, D. R. Jiang, S. Daulton, B. Letham, A. G. Wilson, and E. Bakshy. BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization. In Advances in Neural Information Processing Systems 33, 2020.
[4] R. Bellman. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM (JACM), 9(1):61-63 63, 1962.
[5] D. Bertsekas. Dynamic Programming and Optimal Control, volume 1. Athena Scientific, 2012.
[6] I. Bogunovic, J. Scarlett, A. Krause, and V. Cevher. Truncated variance reduction: A unified approach Bayesian optimization and level-set estimation. Advances in Neural Information Processing Systems, 29, 2016.
[7] E. Bradford, A. M. Schweidtmann, and A. Lapkin. Efficient multiobjective optimization employing Gaussian processes, spectral sampling and a genetic algorithm. Journal of global opfimization, 7 71(2):407-438, 2018.
[8] M. Dorigo and I.. M. Gambardella. Ant colonies for the travelling salesman problem. Biosystems, 43(2):73-81, 1997.
[9] V. Fath, P. Lau, C. Greve, P. Weller, N. Kockmann, and T. Röder. Simultancous self-optimisation of yield and purity through successive combination of inline FT-IR spectroscopy and online mass spectrometry in flow reactions. Journal of Flow Chemistry, 11(3):285-300 2021.
[10] K. Felton, J. Rittig, and A. Lapkin. Summit: Benchmarking Machine Learning Methods for Reaction Optimisation. Chemistry Methods, February 2021.
[11] J. Gardner, G. Pleiss, D. Bindel, K. Weinberger, and A. Wilson. Gpytorch: Blackbox matrix- matrix Gaussian Process inference with GPU acceleration. Advances in Neural Information
Processing Systems, pages 7576-7586, 2018.
[12] D. Ginsbourger and R. I.. Riche. Towards Gaussian process-based optimization with finite time horizon. In Advances in Model-Oriented Design and Analysis, pages 89-96. Springer, 2010.
[13] D. Ginsbourger, R. Le Riche, and L. Carraro. Kriging is well-suited to Parallelize Optimiza- tion. In Computational Intelligence in Expensive Optimization Problems, Springer series in Evolutionary Learning and Optimization, pages 131-162. 2010.
[14] J. González, Z. Dai, P. Hennig, and N. Lawrence. Batch Bayesian Optimization via Local Penalization. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pages 648 657, 09-11 11 May 2016.
[15) J. González, M. Osborne, and N. Lawrence. GLASSES: Relieving The Myopia Of Bayesian Optimisation. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pages 790-799, 09-11 May 2016.
[16] A. Hagherg, P. Swart, and D. Chult. Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Lab. (LANL), 2008.
[17] S. P. Hellan, C. G. Lucas, and N. H. Goddard. Bayesian Optimisation for Active Monitoring of Air Pollution. 36th AAAI Conference on Artificial Intelligence 2021.
[18] C. A. Hone, N. Holmes, G. R. Akien, R. A. Bourne, and F. L. Muller. Rapid multistep kinetic model generation from transient flow data. React. Chem. Eng., 2:103-108, 2017.
[19] S. Jiang, H. Chai, J. González, and R. Garnett. BINOCULARS for Efficient, Non-myopic Sequential Experimental Design. In Proceedings of the 37th International Conference on Machine Learning, pages 4794-4803, 13-18 Jul 2020.
[20] D. R. Jones, M. Schonlau, and W. J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13(4):455-49) 1998.

---

[21] K. Kandasamy, G. Dasarathy, J. B. Oliva, J. Schneider, and B. Póczos. Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations. Advances in Neural Information Processing Systems, 29, 2016.
[22] K. Kandasamy, A. Krishnamurthy, J. Schneider, and B. Poczos. Parallelised Bayesian Optimisa- tion via Thompson Sampling. In Proceedings of the Twenty- International Conference on Artificial Intelligence and Statistics, pages 133-142, 2018.
[23] D. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. International Conference on Learning Reprexentations, 12 2014.
[24] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science (0044598):7716680, 1983.
[25] H. J. Kushner. New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise. Journal of Basic Engineering, 86:97-106, 1964.
[26] R. Lam, K. Willcox, and D. H. Wolpert. Bayesian optimization with a finite budget: An approximate dynamic programming approach. Advances in Neural Information Processing Systems, 29:883-891, 2016.
[27] S. Lazzari, A. Lischewski, Y. Orlov, P. Degimann, A. Daiss, E. Schreiner, and H. Vale. Toward digital polymer reaction engineering, volume 56, pages 187-227. 01 2020.
[28] E. H. Lee, V. Perrone, C. Archambeau, and M. Seeger. Cost-aware Bayesian optimization. Proceedings of the 7th ICML Workshop on Automated Machine Learning, 2020.
[29] E. H. Lee, D. Eriksson, Perrone, and M. Seeger. Nonmyopic Approach to Cost-Constrained Bayesian Optimization. In Uncertainty in Artificial Intelligence, pages 568-577. PMLR, 2021.
[30] F.YY. Leu and J.-S. Ho. Air Pollution Source Identification by Using Neural Network with Bayesian Optimization. In International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, pages 514-524. Springer, 2019.
[31] P. Luong, D. Nguyen, S. Gupta, S. Rana, and S. Venkatesh. Adaptive cost-aware Bayesian optimization. Knowledge- Systems, 107481, 2021.
[32] J. P. McMullen and K. F. Jensen. Rapid Determination of Reaction Kinetics with an Automated Microfluidic System. Organic Process Research & Development, 15(2):398-407, 2011.
[33] Mockus, V. Tiesis, and A. Zilinskas. The application of Bayesian methods for seeking the extremum. Towards Global Optimization, 2:117-129, 09 2014.
[34] M. Mutný, T. Janik, and A. Krause, Active exploration via experiment design in Markov chains. arXiv preprint arXiv:2206.11m
2022.
[35] E. Nava, M. Mutny, and A. Krause. Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes. In International Conference on Artificial Intelligence and Statistics, pages 7031-7054, 2022.
[36] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang. Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang. J. Bai, and S. Chintala. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Curran Associates, Inc., 2019.
Systems 32, pages
[37] M. Poloczek, J. Wang, and P. Frazier. Multi-information source optimization. Advances In Neural Information Processing Systems, 30, 2017.
[38] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
[39] S. S. Ramesh, P. G. Sessa, A. Krause, and I. Bogunovic. Movement Penalized Bayesian Opti- mization with Application Wind Energy Systems. ICML, Workshop on Adaptive Experimental Design and Active Learning in the Real World, 2022.
[40] C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005.
[41] F. P. Samaniego, D. G. Reina, S. L. T. Marín, M. Arzamendia, and D. O. Greegor A Bayesian Optimization Approach for Water Resources Monitoring Through An Autonomous Surface Vehicle: The Ypacarai Lake Case Study. IEEE Access, 9:9163-9179, 2021.
12

---

[42] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas. Taking the Human Out of the Loop: Review of Bayesian Optimization. Proceedings of the IEEE, 104(1):148-17, 2016.
[43] E. Snelson and Z. Ghahramani. Sparse Gaussian Processes Using Pseudo-Inputs. In Advances in Neural Information Processing Systems, pages 1257-1264. MIT Press, 2005.
[44] J. Snock, H. Larochelle, and R. P. Adams. Practical bayesian optimization of machine learning algorithms. Advances Neural Information Processing Systems, 25, 2012.
[45] M. Sobol'. On the distribution of points cube and the approximate evaluation of integrals.
Zhurnal Vychislitel' noi Matemafiki i Matematicheskoi Fiziki, 7(4):784-802, 1967.
[46] N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 1015-1022, 2010.
[47] S. Surjanovic and D. Bingham. Virtual Library Simulation Experiments: Test Functions and Datasets. Available at http:://ww sfu. ca/"ssur ssurjano 2013.
[48] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[49] S.-Y. Teh, R. Lin, L.-H. Hung, and A. P. Lee. Droplet microfluidics. Lab Chip, 8:19--220, 2008.
[50] A. Thebelt, J. Wiebe, J. Kronqvist, C. Tsay, and R. Misener. Maximizing information from chemical engineering data sets: applications to machine learning. Chemical Engineering Science, 252:117469) 2022.
[51] P. Vellanki, S. Rana, S. Gupta, D. Rubin, A. Sutti, T. Dorin, M. Height, P. Sanders, and Venkatesh. Process-constrained Batch Bayesian Optimisation. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2017.
[52] C. Waldron, A. Pankajakshan, M. Quaglio, E. Cao, F. Galvanin, and A. Gavriilidis. An autonomous microreactor platform for the rapid identification of kinetic models. React. Chem. Eng., 1:66261663, 2019.
[53] Wilson, V. Borovitskiy, A. Terenin, P. Mostowsky, and M. Deisenroth. Efficiently Sam- pling Functions from Gaussian Process Posteriors. In Proceedings the 37th International Conference on Machine Learning, pages 10292-10302, 13-18 Jul 2020.
[54] X. Yue and R. A. Kontar. Why Non-myopic Bayesian Optimization is Promising and How Far Should We Look-ahead? A Study via Rollout. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pages 2808-2811 26-28 Aug 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We believe the claims the abstract are backed by the paper's 's content
(b) Did you describe the limitations your work? [Yes] See the last paragraph of Section s introduction.
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not believe there are any obvious negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A] See below.
(b) Did you include complete proofs of all theoretical results? [No] While we include
some mathematical analysis Sections 3.6 and 3.7 it is not fully rigorous and
only meant to illustrate the importance of the Point Deletion heuristic.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [Yes] The code is included the supplementary material, and will be made public after peer-review. We also give details about how the random seeds for each
chosen, in the appendix. (b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appendix
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Section 4
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Section 3.9
4. If you using existing assets (e.g., code, data, models) curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix E
(b) Did you mention the license of the assets? [No] The licenses be found in the documentation of each asset.
(c) Did you include any new assets either in the supplemental material or as a URL? [No] But the GitHub repository generate the paper's results can be found in the following link: https://githi:
com/ cog- (d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "nU2jwIqNrNo", "reviewer": "Reviewer_5kVY", "summary": "This work tackles the problem of cost-aware optimization of expensive-to-evaluate functions for which large changes in the input parameters between consecutive queries incurs large cost. The paper assumes the cost function, a function of the current parameters and parameters evaluated immediately before, is known a priori. The paper proposes a novel Bayesian optimization algorithm for this problem setting that plans a path of future designs. The method first generates a batch of new promising designs via Thompson sampling and then orders the points by formulating the problem as traveling salesperson problem (TSP) and approximately solving the TSP problem with simulated annealing. To reduce the issues of sampling points that are close to one another, the paper proposes to generate a larger than needed batch and delete the closest design to each previously evaluated point if the closest design is within a certain radius (a new hyperparameter) of a previously evaluated design--otherwise a random point is deleted. The method works for the asynchronous setting where the next design must be selected before some number of previous designs have returned.", "questions": "\n* Are there other compelling examples/demonstrations that can be included to illustrate other instances of this problem class?\n* What is the typical level of parallelism (asynchronicity)?\n  * The path ordering issue is relevant when designs are evaluated sequentially (as in the chemistry problem in Figure 6). This point should be highlighted upfront. Typically, in batch/async BO, it is assumed that designs are evaluated simultaneously, but the path ordering problem is only relevant when there is some sequence to the evaluations. Although the lake problem does have sequential evaluation (if you only have one boat), there does not seem to be motivation for asynchronous generation/scheduling, but certainly non-myopia is important. The question then becomes how does SNAKE compare with a non-myopic cost-aware BO method?\n* What is the wall time of SNAKE to generating a batch of points? Given that it is expensive, empirical time results should be included in the paper\n* The claim that SNAKE can optimize multiple objectives should be toned down. Typically, the goal in multi-objective optimization is to learn trade-offs between objectives, but this paper simply optimizes the sum of the objectives\n* Should the number of generated points for purposes of the TSP (non-myopic planning) potentially be different from the level of parallelism? It appears that the number of generated points is currently the level of parallelism, but this also means that the algorithm gets more myopic as the parallelism decreases. \n* L185: shouldn’t p_t on the RHS be p_{t_e}? The result doesn’t obviously hold in that case.\n* How does using epsilon-point deletion compare penalizing the objective based on the distance to previously evaluated or selected designs? Is the a reason to prefer one approach over another. If not, empirical justification for the choice seems warranted\n* L204: “may be approximately constant with time”. Can you elaborate on this? Currently this statement sounds hand-wavy\n\n  * How does the method change if there are multiple queues (for example multiple boats in the lake problem or multiple places to run experiments in the chemistry problem)?\n  * The level of parallelism should be stated clearly for all problems\n* L223: the adaptive grid is mentioned very briefly, but it warrants further motivation and discussion in the main text. It also appears to introduce new hyperparameters\n* 10 replications does not seem sufficient. The error bars of +/- one half of a standard deviation are not informative and raise questions about the soundness of the results\n* The clarity of the results section would benefit if the baselines were clearly described upfront. TREI is never defined in the paper. L252 mentions LPwUCB, but figures say UCBwLP. EIpuLP is not defined.\n* Why is no other cost-aware non-myopic BO method compared against? For example, Lee et al., 2021.\n* L144: I recommend moving Figure 1 up further in the paper. It is mentioned on page 4, but does not appear until page 6\n* L151: Why focus on a ball centered at `a` rather than x_{t-1} or the set of balls centered at each previous design (stating `a` is a previously evaluated design or design in the batch suffices)?\n* Figure 3: the methods should at least be described before the results\n\nLee et al., 2021. A Nonmyopic Approach to Cost-Constrained Bayesian Optimization.", "limitations": "In L240-241, some limitations of SNAKE are highlighted. Further discussion of SNAKE's limitations would be good. No societal impacts are discussed, but such discussion seems unnecessary.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* Optimizing sequences of designs (paths) is a neat idea and as far as I know, a novel formulation. \n* The paper is largely well written (aside from some undefined acronyms and minor comments listed below).\n* The chemistry problem is a great example\n\nWeaknesses\n* However, the prevalence of these problems appears limited, and therefore the contribution appears to be a highly nuanced class of problems (see discussion of sequential nature of evaluation below). \n  * The chemistry problem showcased in Figure 6  and included the experiments is a compelling example, but it does not seem that the other real-world inspired example problem (the lake problem ) fits this problem class. \n* In addition, the proposed technique for dealing with sampling nearby previously selected designs (of deleting nearby points) is not theoretically grounded. \n* The mathematical analysis in Sec 3.7 has weak insights.  \n* There are no significant theoretical results", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WxFX5D1oATX", "reviewer": "Reviewer_aedf", "summary": "The paper introduces a new variant of cost-aware BO: It is more expensive to evaluate two points one after the other if they are farther away from each other than if they are close to each other. A method (SnAKe) for this setting is suggest, that approaches the problem in the following way: In each iteration, a new batch is sampled, using Thompson seedling. The evaluation order of the points in the batch is formulated as a TSP and optimized. The method runs asynchronously, i.e. points are resampled after every new observation. However, this leads to too much exploitation, which is why sampled points epsilon-close to already evaluated points are not taken into account. The method shows a good performance on synthetic benchmarks and two real-world examples. ", "questions": "The optimized paths in Figure 4 all look the same, even though the objectives are different. Is there a reason or could this be a plotting error?", "limitations": "The authors address limitations: The method performs less well in higher-dimensional search spaces and low-budget settings. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The work is original, and I think it is an interesting question how to balance exploration with exploitation, when there are additional external factors (like costs), that influence the trade-off between the two. The setting is also signifiant for real-world applications of BO. \nThe experiments support the claims of the paper. The real-world experiments are nice. A strength of the method is that it seems to be robust to the choice of hyper parameter epsilon.\n\nThe writing could be improved in some aspects, e.g.:\n* In section 2 (line 68), the abbreviation \"EI\" is used without definition. It becomes clear from the context that it means \"Expected Improvement\", but I would mention this somewhere explicitly. \n* Maybe one could change the color-scale in Figure 2. It's a bit difficult to see the gradation. \n* I would suggest to have Section 3.3. as part of Section 3. One could also mention the definition of regret in Section 3.1\n* I am not a native English speaker, but the wording sometimes seems a bit informal to me. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SVZp6w3CljF", "reviewer": "Reviewer_UNKt", "summary": "The paper proposes an efficient algorithm for a novel optimization task where the distance of candidates to be evaluated incurs input costs. The algorithm penalizes the input variations on top of the traditional Bayesian Optimization algorithm while leveraging the batched Thompson sampling to diverge the candidate picks. Traveling salesman The problem is solved to create an efficient path for the batched query.", "questions": "1. For figure 3, does 3.a and 3.b share the legend in 3.c? If so, I would suggest putting the legend in a shared space instead.\n2. In equation (1), the \\gamma is mostly set to be 1 and could be problematic. For example, when the search space X is scaled up, the shape of the objective function remains the same while the behavior of the algorithm could change as the cost(x, x_{t-1}) is scaled up. Is there any normalization of X in the preprocessing? Could the author demonstrate the corresponding performance of different \\gamma?", "limitations": "The author addresses the concerns.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- ***Strengths***\n1.  The paper studies a novel distance-aware optimization setting motivated by real-world application.\n2.  The paper proposes a novel solution to penalize the input variations while avoiding being stuck in local areas in the optimization by the combination of batched Thompson sampling and the proposed $\\epsilon$-point deletion. The algorithm design is motivated by insights derived from the analysis of the desired escape from the local optimum.\n3. The algorithm empirically validated that the input cost dropped.\n\t\n- ***weaknesses***\n1.  The cost in this problem setting is not defined in a principled way. The paper attempts to minimize the regret within a certain number of iterations while minimizing the input variation cost. Essentially there is one optimization objective and two types of costs considered. One cost is the number of iterations, which is the typical BO cost given each evaluation is expensive, and the other cost is the input variation. The triplet structure of the problem incurs a challenge in performance measurement. Instead of merely comparing regret within a certain iteration as in the traditional BO setting, the triplet requires the additional comparison on costs, which make the performance of different algorithms less comparable. \nFor example, as shown in figure 3, EIpuLP achieves lower cost while bears higher regret compared to the proposed algorithm, it becomes unclear whether EIpuLP is better in figure 3. Similarly, when the same mixed performance appears for different hyperparameter settings, there lacks a principled way to pick the better hyperparameter. Unless there is a weighted sum of the two different costs where the weights reflect the importance of these costs in the application, it's hard to compare algorithms and hyperparameter choices. The corresponding algorithm design should also consider the weights. Otherwise, it's possible that there exists an algorithm that is significantly superior on one cost while lags on the other. Algorithms like Genetic algorithms that only conduct small variations in each step could potentially bear much lower input costs while incurring a much larger amount of iteration.\n2. As mentioned, Genetic algorithms could be included in the baselines.\n3. The paper argues that the $\\epsilon$-Point Deletion is robust to the hyperparameter choices and proposes to leverage the lengthscale of the kernel to adaptively pick the value of $\\epsilon$. The robustness is counter-intuitive as the local (sub)gradients of the objective function could be different even assuming a global smoothness guarantee for the objective function. Additional study on the $\\epsilon$-point deletion algorithm behavior might be necessary to explain the robustness, especially on the ratio of the random deletion among all deletions for each performance curve.\n4. The confidence intervals of the regret curves for experiments are large and potentially indicate the lack of statistical significance of the results. Could the author provide corresponding p-values?", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9natIRxUD0g", "reviewer": "Reviewer_V9c2", "summary": "This work presents a low-cost Bayesian optimization solution, which is inspired by real-world applications. The proposed method is analyzed mathematically in Section 3. Experimental results in Section 4 shows the effectiveness of the proposed method when compared with several state-of-the-art methods. Comprehensive experimental results are shown in the appendix. ", "questions": "Why does UCBwLP perform better in Figure 3(b) than the proposed method?\n\nAs the proposed method is claimed to be low-cost. Can the authors provide quantitative analysis of this work with other existing methods in terms of cost?\n\nWhat's the impact on the proposed work if the delay of observations varies?", "limitations": "Low-cost analysis of the proposed work is not provided.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The solution has a novel idea of optimizing sample paths while minimizing the input costs. The paper is well-written with understandable examples and mathematical formulation. The comprehensive experimental results support the effectiveness of the work. \n\nHowever, there are some minor drawbacks: 1) The notation used in formulation can be pre-defined so that readers understand them better; the paper would be self-contained if notation is well-defined. 2) Minor editing flaws: Figure 5 is mentioned before Figure 4; Fonts in figures can be enlarged for better readability.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept