Movement Penalized Bayesian Optimization with Application to Wind Energy Systems
Authors: Shyam Sundhar Ramesh
Pier Giuseppe Sessa
Andreas Krause
Ilija Bogunovic
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bayesian Optimization
Metrical Task Systems

Abstract: Contextual Bayesian optimization (CBO) is a powerful framework for sequential decision-making given side information, with important applications, e.g., in wind energy systems. In this setting, the learner receives context (e.g., weather conditions) at each round, and has to choose an action (e.g., turbine parameters). Standard algorithms assume no cost for switching their decisions at every round. However, in many practical applications, there is a cost associated with such changes, which should be minimized. We introduce the episodic CBO with movement costs problem and, based on the online learning approach for metrical task systems of Coester and Lee (2019), propose a novel randomized mirror descent algorithm that makes use of Gaussian Process confidence bounds. We compare its performance with the offline optimal sequence for each episode and provide rigorous regret guarantees. We further demonstrate our approach on the important real-world application of altitude optimization for Airborne Wind Energy Systems. In the presence of substantial movement costs, our algorithm consistently outperforms standard CBO algorithms.

Movement Penalized Bayesian Optimization with Application to Wind Energy Systems
Shyam Sundhar Ramesh
Pier Giuseppe Sessa
ETH Zurich shramesh@ethz.ch ch
ETH Zurich sessap@ethz.
Andreas Krause
Ilija Bogunovic
ETH Zurich krauseaBethz.ch ch
University College London i bogunovicSucl. ac uk
Abstract
Contextual Bayesian optimization (CBO) a powerful framework for sequential decision-maken making given side information, with important applications, c.g., in wind energy systems. In this setting, the learner receives context (c.g., weather condi- tions) at each round, and has to choose an action (e.g.. turbine parameters). Standard algorithms assume no cost for switching their decisions at every round. However, in many practical applications, there is cost associated with such changes, which should be minimized. We introduce the episodic CBO with movement costs prob- lem and, based on the online learning approach for metrical task systems of Coester and Lee 19], propose a novel randomized mirror descent algorithm that makes use of Gaussian Process confidence bounds. We compare its performance with the of- fline optimal sequence for each episode and provide rigorous regret guarantees. We further demonstrate our approach on the important real-world application of altitude optimization for Airborne Wind Energy Systems. In the presence of substantial movement costs, our algorithm consistently outperforms standard CBO algorithms.
Introduction
Bayesian optimization (BO) is a well-established framework for sequential black-box function op- timization that relies Gaussian Process (GP) models [42 sequentially learn and optimize the unknown objective. In many practical scenarios, however, one wants to additionally use available contextual information when making decisions. In this setting, each round, the learner receives context from the environment and has to choose an action based upon it. Previous works have devel- oped contextual BO algorithms 32 16. 40), and applied them to various important applications, e.g., vaccine design, nuclear fusion, database tuning, crop recommender systems, etc.
A potential practical issue with these standard algorithms is that they assume no explicit costs for switching between their actions at every round. Frequent action changes can be extremely costly in many real-world applications. This work is motivated by the problem of real-time control of the altitude of an airborne wind energy (AWE) system In AWE systems, the wind speed often only measurable at the system's 's altitude, and determining the optimal operating altitude of an AWE system as the wind speed varies represents a challenging problem. Another fundamental challenge that additional energy is required for adjusting the altitude, which makes the frequent altitude changes costly. Consequently, this work is motivated by the following question: How can we efficiently learn
AWE system is a wind turbine with a rotor supported in the air without a tower that can benefit from the persistence of wind at different high altitudes [2]
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

to optimize the AWE system's 's operating altitude despite varying wind conditions while minimizing
the energy cost associated with turbine altitude changes?
In this work, we formalize the movement penal-
Total Energy Generated
ized contextual BO problem. When the switch- ing cost is a metric (distance function), we pro-
GP MD
CGP-LCB Stationary
4000
pose novel algorithm that effectively combines
ideas from BO with the online learning strate-
3000
gies proposed in [19] for solving the so-called metrical task system (MTS) problem [II] Fur-
2000
thermore, our algorithm relies solely on noisy point evaluations (i.e., bandit feedback), allows for arbitrary context sequences, and besides the trade-off, it
1000
320
640
960
standard exploration-exploian also balances the movement costs. As a result, it outperforms the standard movement-cost- agnostic contextual BO algorithms as well as movemeent-conservatiee baselines (see Fig. [
Timesteps
Figure 1: Total energy generated by the AWE system when operated with GP-MD (proposed in this work), CGP-LCB [32] and stationary baseline. The stationary baseline employs no-learning and does not incur movement costs. GP-MD and CGP-LCB learn an operating strategy, but GP-MD outperforms CGP-LCB since it also considers movement costs.
Related Work. Bayesian optimization (BO) refers to sequential approach for optimizing an unknown objective (cost function) from noisy point evaluations. A great number of BO methods have been developed over the years (e.g.. [38 50 (7). While the focus of standard BO approaches mainly on optimizing the unknown ob- jective cost function, in this work, we additionally focus on penalizing frequent action changes. This problem makes the most sense in the contextual BO setting [32], where the main objective changes with the observed contextual information and the learner also seeks to minimize the cost associated with frequent changes of its actions. Several works have tried to incorporate such and similar cost functions in the BO setting. [35] explicitly consider switching costs based on how deep into the pipeline the change in variable occurs. But they do not consider the contextual setting that is essential for our wind energy application and hence our work is not directly comparable with theirs. Morcover, it assumes that the system of interest has a modular structure (as detailed in B5 Section-3]). In such modular setting, the cost at each round is the number of modules that has be changed rather than the amount of change of each variable. Other works include cost-aware and multi-objective sam- pling strategies in various settings such as batch [29 27). multi-fidelity [10 28 49), multi-objective
optimization [2] and dynamic programming [4 33 Finally, two recent works [24 [5] consider the problem of switching cost minimization in Bayesian optimization. They both consider the non-contextual setting, and while [24) lacks theoretical guarantees, [155 does not explicitly consider the cost the regret definition. Similarly, we consider movemen/switching costs, but unlike these previous work, we specifically focus on minimizing the movement costs in the contextual setting.
The Metrical Task Systems (MTS) problem ||| is a sequential decision- decision-making problem widely studied in the online learning literature. At each round, the learner observes a service cost function, chooses an action, and incurs the corresponding cost together with movement cost penalizing the distance (according to some metric) between the current action and the one chosen at the previous round. The MTS problem is directly related to our problem setting (see Section 2.2 After a long series of works, in [[4] and 19, an O ((log n -competiivee algorithm for MTS on any finite metric space was established. The approach of Coester and Lee [19 relies on a tree representation of the decision space and an action randomization scheme via a mirror descent procedure. In contrast to our setting, these works assume that the service costs are known (i.e., they assume the full-inforrmation feedback). Moreover, in the online optimization literature, other related works study the online convex optimization with switching costs [26 48 25 36) and convex body chasing problems [12] 5 43 [3]. We make no use of convexity and take a model-based (GP) approach to learn about the unknown service costs. (37] consider non-convex objective functions, however, they impose certain conditions on the objective that are not easily modeled via GP as done in our work.
The use of GP confidence bounds in online learning settings has been previously explored, e.g., in repeated multi-agent [44] 47) and sequential games [46), and to discover randomized max-min strate- gies 45). However, none of these works has considered movement costs in the objective. This makes our problem significantly different from the aforementioned ones, and requires a suitable action ran- domization scheme that can trade-off exploration. exploitation, and movement costs simultaneously.

---

Various works have applied Bayesian Optimization in the context of wind energy systems before. ! use BO techniques maximize the total energy yield in wind farm in cooperative or a closed-loop framework. [39] use it to tune the parameters of the wind turbine to learn the effective wind speed. [6] use BO for plant design (i.e., physical system design) of airborne wind energy systems. [51 apply BO and other regression techniques to predict short-term wind energy production to make informed production offers. Finally, [3] survey several different methods for efficient wind-power prediction using machine-learning methods including BO. Our problem formulation differs from the above mentioned works, since we explicitly consider movement energy loss caused by the altitude change of the system.
4
Contributions. We formally introduce Bayesian optimization with movement costs and propose a novel GP-MD algorithm (in Algorithm DT. GP-MD combines the online mirror descent (MD) algorithm with shrinking Gaussian Process (GP) confidence bound to decide on which point to evaluate next. In our theoretical analysis, we establish rigorous sublinear regret guarantees for our algorithm by combining techniques from Bayesian optimization and metrical task systems approaches [19]. Finally, we demonstrate that GP-MD is able to successfully outperform previous contextual Bayesian optimization approaches on both synthetic and real-world data in the presence of movement costs. In particular, we consider the application to airborne wind energy systems and demonstrate that GP-MD can effectively operate such a system by considering movement costs and varying environmental conditions.
2 Problem Statement
Let f x + RR,, be an unknown cost function defined over X' x & C RP, where X' is finite set of actions, i.e., |X| = n,, and & represents convex and compact space of contexts. We denote the known metric (i.e., distance function) of X' as d(-,)), and similarly
other works in Bayesian optimization (e.g.. [50 (7)) assume that the target cost function f belongs to reproducing kernel Hilbert space (RKHS) H₂ of functions (defined on X' E). that corresponds to a known kernel k : (X' x E) x (X' x E) + R+ with k((z, e), (z',e')) < 1 for any action-context pair. In particular, we assume that for some known > O, the target cost f has a bounded RKHS norm, i.e., f Fr {f E He: ||l I B}. Also, we assume that the diameter of X (maxz,x'ex d(z, x²) is bounded and denote it by v/.
We consider an episodic setting, wherein each episode runs over a finite time horizon H. Let the initial state of the system in the first episode correspond to action I E X, At the end of every episode, the system resets to new given initial action To.m E X' where m E {1, 2, ... Nep) denotes the episode index. In each episode m and at every time step h E 21. H}. the environment reveals the context ea.m E E to the learner. We make no assumptions on the context sequence provided by the environment (i.c., can be arbitrary and different across episodes). The learner then chooses Th,m E X and observes the noisy function value:
Mh.m = [3 h).m) Sn.m
where Sn.m NO, o²) with known a, and independence over time steps. The goal of the learner is to minimize the cost incurred over the rounds in every episode, but at the same time to minimize the distance between its subsequent decisions as measured by d( Tb,
Let Dm = {Ii,m Z2,m: ................................ HH.m. denote the set of actions chosen by the learner over H rounds in episode m. We recall that each action Fh.m E Dm is chosen after observing the corresponding context e.. The objective is to minimize the cumulative episodic cost for each episode m,
H
cost (Dm)
I [Fhmm Ch.m) ) +
drhhmm Th Jhm-1m))
1,m)
S Smn)
(P.))
where we refer to the two terms in Eq. 22) service cost S,, and movement cost M.
When ʃ is known, the problem can be seen as a MTS instance as detailed in Section 2.2 Even in such case, cannot hope to solve this problem optimally, and nearly- approximate algorithms were recently proposed (see Coester and Lee [19). Hence, the learner's performance in episode m is measured via (a, -ppppoxxiee regret:
a = costm (Dm) costm (Dm)) B,
(3)
3

---

where D == arg pcx, Hrl=i (D) is the offline optimal action sequence obtained as- suming the knowledge of the true sequence of contexts (eh,mJh- in advance, and a and approximation constants (independent of Nep). In contrast, in our setting, the learner only gets to see the current context when making decision and has knowledge about the future ones.
After Nep episodes, the total cumulative regret is defined as
Ney Σ
R Nop
na.3
(4)
We seek an algorithm whose total cumulative regret grows sublinearly in Neps so that lim
Ra. H.N.p /Nep = 0, for any set of initial states f Nep C X.
2.1 Gaussian Process Model
In standard Bayesian optimization, a surrogate Gaussian Process model is typically used to model the target cost function. A Gaussian Process GP(m(-),,k(- over the input domain X' x XE, is collection of random variables (J <))xex,,ee where every finite number of them (J e, )) _ n N. is jointly Gaussian with mean B[]()):) = [u(r,, eq) and covariance [[ e4) - ex) ((,,,))
(( }))] k((2,,)) e,)) for every 1 S i S n.
BO algorithms typically use zero-mean GP priors model uncertainty in i.e. GP(O, -)--.)). and Gaussian likelihood models for the observed data. As more data points are observed, GP (Bayesian) posterior updates are performed in which noise variables are assumed be drawn independently across t from (N A). Here, À is hyperparameter that might be different from the true noise variance o². More precisely, given sequence of previously queried points and their noisy observations the posterior is again Gaussian, with the posterior mean and variance given by:
(x c) ko( (Ke AY,
(5)
(z.e) = k((x,,() e), (z, c)) ke e) Mi))"k((xx,
(6)
where Y; : [91,-..; yo] denotes vector of observations, K, [k(((rs; es), (xx,, est e s is the corresponding kernel matrix, and (x e) [k((#1,)1) G1), (z. e))...., et), (z, e))l E R
Maximum Information Gain. In the standard Bayesian optimization, the main quantity that characterizes the complexity of optimizing the target cost function is the maximum information gain (50 defined at time as:
max (()))))))
I(Yr:))
where I(Y; f) denotes the mutual information between random observations Y, and GP model f. The mutual information for the GP model is given
T(Y: = log
(8)
This quantity is kernel-specific and for compact and convex domains "/ sublinear t for various classes of kernel functions (50) as well for kemel compositions (e.g., additive kernels in (32).
Confidence Bounds. We also use the following result (55 17) that frequently used in Bayesian optimization to provide confidence bounds around the unknown function.
Lemma 1. Assume the o-sub- Gaussian noise model as in Eq. [ and let f belong to Fv. Then, the following holds with probability at least simultaneously over all t 2 and x E X, e E:
(1, e) (xx e)l < (x,,(z,e),
where B: = a
XI72 2 (1 + 27 + B, and μ4t and as are defined in Eqs. and O with X > 0.
Based on the previous, we also define the lower confidence bound for every E X, E & as: Icb, (z, e) (1 e) (x,
(10)
We use lebm e) when it is computed based data collected before episode m.

---

Algorithm GP-MD
1: Require: Action space X, kemel function k(.,) -. metric d(-.-)
2: Run FRT(X, d(..)) and obtain r-HST (V. E) with leaves X'
3: for m = =1,...; Nep do
4: Receive To.m and initialize 20,m (Eq. 29 conditional prob. go = A 1-1(20,mm)) as in Eq. (15
5: for 1......... do
6: Observe context Ch.m and initialize costs: lcbm Ch,m) = 0, Ve E VVC
7: for u E (D(V) do
8: Update vertex prob. 9r from gh-11 and lcbm Ch,m) via Mirror Descent (Eq. 130)
9:
Update cost for vertex
Icbm (u, Ch.m) = (gh. ..l.bb ch,m)) =
Σ vEC(u)
th. Icbm (2; Ch.m)
end for
11:
Compute prob. vector 2h,m = A ((g)) (Eq. 15 and leaves' prob. 1( (Eq.
11
Estimate optimal coupling Ç4-1,h.m between i (2mm and ((2h.m) as Eq. 12
13: Sample action Th.m ~ Ih-1,h,m (- (-mm) and observe yh.m = [Thhm Ch,m
F Sh.m
end for
15:
Update Mm++ (m++(;;)) and am+ (1.)) as per Eq. 5 and Eq. (6)
16: end for
2.2 Relation to Metrical Task Systems (MTS)
When f is known, our optimization objective in Eq. (2) can be seen as a particular type of MTS problem, where f(, Ch.m) is the MTS service cost that changes for every h and m. Compared to a standard MTS (see Appendix AA). our problem formulation is more challenging since the learner only learn about f from previously observed data. The approach proposed in this paper builds on the algorithm by Coester and Lee [1] for standard MTS problems. However, to cope with the aforementioned challenge, our approach exploits the regularity assumptions regarding / and utilizes the constructed lower confidence bounds Eq. (10) to hallucinate information about the unavailable service cost each round. Before presenting our overall approach, describe preliminary
step proposed by [19] which consists of representing our metric space (X' d) by a Hierarchically Separated Tree (HST) metric space.
HST metric space. Consider a tree T= EV, with root r, leaves C V and non-negative weights We, for each E V. which non-increasing along root-leaf paths. Let d (t, denote distance metric between any two leaves 1, E L given as the sum of the encountered weights on the path from / to l' (see 4. d7) is HST metric space, and 7-HST metric space if the weights exponentially decreasing, i.e., Wa S w./T, with v being the parent of u.
Similarly to 19 FRT) to approximate the given metric space (X' by a r-HST one. particular, we use FRT in Algorithm| as computationally efficient preprocessing step to create tree T with leaves L corresponding to actions in X' distance metric dr, and root node r. We explain the intrinsic MTS motivation for this preprocessing step in Appendix B.T B.
the algorithm from 23 (which name via the authors' surnames as
and defer additional details to Appendix B.2
3 The GP-MD Algorithm
In this section, we introduce GP-MD, a novel algorithm for the contextual BO problem with movement costs defined in Section 2
At each episode m and round h, the state of GP-MD can be summarized by vector of probabilities Zn,m E Kr over the vertices of T, where Ky :=
R! 2, 1,
Σ
Vu V.C). and C(u) denotes the children of Each entry z
vEC(u)
represents the probability that the selected action Fh.m belongs to the leaves of the subtree rooted i.c., 2n PP E C(v)). Below, specify how 2h,m is computed at each round. Moreover,
5

---

given any E Kr, the vector
[= [2,, E C] E [0,1]",
(11)
defines probability distribution over the leaves L, and hence the actions X. As in [19), given probability vectors 21,m and 2m. GP-MD computes the minimal distance distribution
Sh 1m
arg inf (E 1.m ()
[e ((ddT(Uh-1,0)) (Un-1,m, Un,mm,
(12)
where 1n and Un are random variables having marginals 1(2h-1,m) and 1(2h,m respec- tively. Finally, action 2h,m sampled from the conditional minimal distance distribution 2h,m Sh-1,Amm (- (-mm)-1..)) (Line 13 in Algorithm D. At the end of each episode m, the newly observed data are then used update posterior mean and standard deviation about the cost function.
Finally, we describe how probability vectors 2h.m are computed at each round, a key step of GP-MD (Lines 8-12 in Algorithm IT. We follow the recursive Mirror Descent (MD) procedure proposed by [99 with the important difference that we are dealing with an unknown context- matexxt-eppndeett cost function. Hence, we make of the Gaussian process model and corresponding confidence estimates as defined Section 2.1
To obtain probabilities 2h,m. consider conditional probability vectors q QT. where QT is the set of valid conditional probabilities QT == {o R E =1 Vu E V.c............. For
vEC(a)
each vertex y with parent u, gu represents the conditional probability P( E [(v)[ E (())). Moreover, given Qh. QT define the vector (1()) (9h,r E C(u)] the conditional distribution over children of u, and let o(9²) be the set of all valid distributions ohh
In each episode m, conditional probability vector qh. for round f is obtained recursively, from leaves to root, as a function of Q4-1, the observed context Ch.m. and the current estimate about the cost associated to each particular vertex. More precisely, let OD(VL, be topological ordering of the internal vertices V so that every child T occurs before its parent. Then, for each u E (D(V)2) conditional probabilities (12) obtained via the Mirror Descent update:
4h pEo
(u) arg min ((w) (plaa (w) (p, (1,
(13)
Function (a) is the Bregman divergence with respect to suitable potential function (see Ap- pendix D. while leb("/ (-, eh,m) = [lcbm Ch,m), Vv C(u)] is lower confidence bound estimate of the costs corresponding to children of vertex u. For u E L, Icb, Ch.m) are obtained by the Gerressessoon techniques outlined in Section 2.1 while for internal vertices these are computed recursively from their children nodes as:
lcbm (u, Cl.m)
gh,uleb, ch,m)
(14)
vEC(u)
The movement cost is primarily controlled by this usage of Bregman divergence based mirror descent. Also, sampling from the conditional minimal distance distribution further restricts movement between alternate actions. Once the vector of conditional probabilities Qi E QT has been updated, we can obtain the corresponding probability vector 24,m via the mapping A Qr + Ky such that:
2
2u = Zule
Vu E VV, v u C(u).
(15)
3.1 Theoretical Guarantees
Our main theorem bounds the cumulative regret of GP-MD.
Theorem 1. Let X be represented by a T-HS space with T > 4 (Line 2 of Algorithm 7.. and set 5 E (0,1). Then, with probability least 1-5, the regret of GP-MD over Nep episodes is bounded by
Ra.3 Ney = - H + H log (1) H + +)) log Nap log log(Nop))
THN.,
5
with approximation factors a O n and 3 0()). Here, is the episodes' length, 18. is the confidence level from from Lemma and NH u is the maximum information gain defined in Eq.

---

Total Cost
Total Cost
Total Cost
0000
GP MD
GP
LGP
CSP-LCB
CGP-LCB
MixC-knoww
MinC-Known
Know-
4000
Stationary
Stationary
5000
Stationary
30.0
MD-Knoww
MiD-Known
5000
MD>Known
1000
2000
Timesteps
Timesteps
Timesteps
(a)
0.5
(b)
(c) ==
Movement Cost
Movement Cost
Total Cost
6000
GP
10000
CGP-LIC
MinC
MinC Known
5000
Stationary
Stationary
4000
Stationary
MinC-Knnown
MD Known
MD- KD-Known
3000
MD Known
2000
2000
4000
1000
1000
2000
Timesteps
300
100
Timesteos
200
Relative Service Cost Importance
(d) / 0.5
(c)
(f) Varying p
Figure 2: Total and movement cost performance of algorithms on synthetic functions for varying importance of movement/service cost (i.c., different values). GP-MD outperforms CGP-I.CB B in terms of total incurred cost, and its performance closely follows of the idcalized benchmark MD-K NOWN. GP-MD also minimizes the movement cost while CGP-LCB suffers from significant movements (Figs. 2 and Zeb. performance of GP-MD remains robust when the movement cost importance in the total cost objective diminishes (Fig.
For most of the popularly used kernels, Thm. can be made more explicit by substituting bounds on Nop (e.g., in the case of linear kernel and compact domain, have 7i Op log (), while for squared-exponential kernel holds 7/- O(log 1) [50]: also Section 2.1 In such cases, make the following two important observations regarding our result: i) The obtained regret bound is sublinear in the number of episodes Nep and hence li NN., /Nep = O; ii) The bound is independent of the input space size, i.e., the number of actions n (although the approximation factor depends logarithmically on n, similarly to (19).. These imply that GP-MD approaches a-competitive ratio performance of the MTS algorithm by [19], while learning about the service cost from noisy point evaluations (i.c., bandit feedback) only. Finally, in our analysis, we treat H as constant.
Proof of Thm. is detailed in Appendix E Next, we outline some main steps. We make use of the competitive ratio guarantees for the used Mirror Descent algorithm from [19 Corollary 4] to bound the expected hallucinated service cost Σn (leb,, (-, en.m), (()..)) Here, we use the fact that Icb, (:,-) does not change within an episode. Since this is not the actual service cost, we bound E (f(,, m), (2),,m) by Σm= (leb,s ()c.,,( (=zm.)) with an additional learning error. The sum of the learning eтrors over all episodes can be rewritten as Nep Σ/ (o (hhm),,((z (Zn, m))) We use the concentration of the conditional mean result from [30 Lemma 3] to upper bound by
m==1 the actual realizations Wer, Σne o2 (Ih,m m,,m), and use the result of [18] Lemma-2], to further
upper bound with the maximum information gain quantity H.
Finally, the movement cost can also be bounded similar to that of the previously mentioned expected
hallucinated service cost Σ (Icb,,( (:s m,,m, , (2),,) with an extra a = O O(log n1) factor using Corollary 4].
19
4
Experiments
This section provides numerical results on synthetic and real-world data. We compare the performance of our GP-MD algorithm with the following baselines:
STATIONARY selects the stationary strategy 2y = xi for all h,
CGP-LCB (22 neglects the movement cost and sets
arg min, lcb,, (ar, ex) for all h.
MINC- MINC-KNOWN assumes f(-) is known and chooses Th = arg min, [(x 6x), and
MD-KNOW KNOWN assumes f()) is known and runs mirror descent from [19 on f(,
7

---

MD-KNOWN and MINC- KNNWN unrealistically assume that f(-) is known and can be seen as upper-bound for the achievable performance of GP-MD and CGP-LCB, respectively. We use the same constant value B = 2.0 for the exploration parameter in both GP-MD and CGP-I.CB (since the theoretical worst-case bounds are found to be overly pessimistic and can impede performance (50)). We run the algorithms over single episode (as done in CGP-I.CB). We also discover that updating the confidence bounds after every timestep in GP-MD leads to better performance in practice.
Synthetic experiments. We consider synthetic experiments, where the objective function is random GP sample. The considered action space X' is a subset of [0, 1] consisting of 400 points that form the uniform grid, while the context space E consists of 40 contexts that are uniformly sampled from (0, 1). We sample objective function (i.e., actual cost) f X' & - IR from GO k), where k is a squared exponential kernel with lengthscale parameter set to I = 0.2. We use the Euclidean distance between the domain points as the movement cost, calculate the distance matrix (hetween every pair of points) and the average movement cost. We subtract the minimum value from f and scale it such that the aver- age function value is equal to the average movement cost. We also set the noise parameter to 1 1% of the function range. We introduce the trade-off parameter & {0.25, 0.5, 1, 2, 4} that only multiplies the service cost, i.e, pz e), but not the movement cost. This is to test the performance of the algorithms for varying importance of the service/movement costs. For each we sample 25 different functions and run the algorithms for 500 timesteps wherein at each step the contexts are randomly sampled.
In Fig. 2a Fig. 2e we show the total cumulative cost as function of timesteps for different values. Then, in Fig. 21] we show the performance of the algorithms (for known kernel parameters) when run for 800 timesteps for varying importance of the service and movement costs. In particular, we consider convex combination of the service and movement costs, where we set the respective coefficients multiplying these two objectives as p/( (1 + p) and 1/(1 + p).
As shown in Fig. 2a Fig. 2c the performance of GP-MD is generally close to the one of the idealized, unrealistic benchmark MD-KNOWN which, as expected, performs the best. The stationary baseline performs comparably when P is small, while its performance deteriorates for larger values. As expected, both MINC- KNOWN and CGP-LCB incur higher total costs than GP-MD when the movement cost is of the higher or same relative importance as the service cost (i.e., p E {0.5, 1.03). while the performance gap slowly decreases when the service cost becomes dominant (p 2.0). In Figs.2daand and 2e] we also show the corresponding movement costs, and observe that movement cost ignorant CGP-LCB incurs significant movement costs, while our GP-MD successfully minimizes the movement costs. Finally, in Fig. 21 we observe that the performance of GP-MD is robust, i.e., it clearly outperforms CGP-LCB whenever the movement cost dominates the total cost objective, while its performance remains comparable to the one of CGP-LCB (that is built to minimize service cost) when the movement cost becomes dominated by the service cost.
4.1 Altitude Optimization in AWE Systems
In airborne wind energy (AWE) systems, the turbine's operating altitude can be changed depending on the wind pattern. We follow the setup of Baheri et al. [7] that applied CGP-LCB 32 which ignores movement-costs, to learn this control task. In this section, we use dataset from 9 which contains wind-speed information over various locations in Europe for a period ranging from 2011 to 2017, and also includes measurements at different altitudes per location. We consider the wind speed data from the second half of 2016. Our goal is to maximize the generated energy, while taking into account the energy loss due to moving the turbine from one altitude to another.
We consider 25 different altitudes (ranging from 10m to 1 6000) as the action space and the context space to be hours in the day (i.e., 24 values). We define our unknown service objective function to be f(x, t) = max," (Fss (x', , t)) - Es(2, t) where Es(2, t) denotes the energy generated based on the windspeed at altitude x and time t. Based on the discrete-time power generation formula from Baheri et al. (7] (Eq. (10)), we have
Es(æ, 1) = (a (oc
(1,
(16)
Here Vn, (zc, 1) denotes the windspeed at altitude x and time i,, and V,- denotes the rated windspeed of the turbine. The constants e 0.0579 and c2 = 0.09 are system dependent. This corresponds to the energy generated at a particular altitude x for At time. Similarly to Baheri et al. [7], we use At = 60 since we consider intervals of one hour length. Next, we define the movement cost to be
8

---

Total Energy Generated
Average Total Energy
Service Cost
6000
5000
Siatimary VD UD-tnoww
GP ND
7.0
6.0
Stationary
KinC-Known
CGP LCB
GP MD
2000
1500
MinL-Known
CGP-LCB
GP MD
Stationary
MD-Known
MD-Known
4000
5.0
1000
4.5
3000
4.0
500
3.5
2000
200
200
800
200
100
600
800
0
Timesteps
Timesteps
(a) Lat. 53, Long. = - 10
(b) Total Energy (p = 4)
(c) Service Cost (p = 4)
Movement Cost
Movement Cost
Total Energy Generated
1400
1200
GP-MD MD
EGPLCC
GP
6000
COPLUCS
GP HD
1000
Stationary
MinC-Known
2500
Known
Stationary
5000
Knn-know M3-Erown
800
MD-Kroww
2000
MD-Krown
600
1500
4000
400
1000
200
500
3000
200
Timesteps
000
800
200
Timestees
400
600
800
2000
2
p 6 8 10
(d) Movement Cost (p 4)
(e) Movement Cost (p 1)
(f) Lat. 53, Long. -4
Figure 3: AWE altitude optimization task; Fig 3a Total energy generated for 960 hours based on the wind data at a single location (Latitude= 53 and Longitude- = - 10). GP-MD outperforms previously used CGP-LCB (that optimizes for service costs only) for a range of values that favor the service against the movement cost.
Fig. 3b The average total generated energy over 960 hours. Figs. 3c and 3d The service and movement costs
for P
4. Fig. 3e The movement costs for p = 1. The movement energy loss is slightly lower for GP-MD as
compared to o = 4 due to higher importance towards movement cost reduction. Fig. 3f Same as Fig. 3a albeit
by using wind data from a different location (Latitude= 53, Longitude= -4).
the energy lost in changing altitude (from to z'):
EM (2, a²) = eg V3V 1 r'/,
(17)
where c3 = 0.15 (see Appendix F for more details) |
We assume that a wind speed gauge is attached to the turbine, and the operator knows the wind speed at the current altitude. Hence, instead of directly learning fxx t). we learn (z, t) and use its confidence bounds to calculate the confidence bounds of fxx To learn Vu (z, we normalize the inputs, and fit GP with RBF kernel (lengthseale=3.61 outputscale=6.85 and noise parameter=2.73).
We the algorithms for different p for 960 timesteps, where again p is used to multiply E.g. For each p. the algorithms were initiated with every possible starting point (25 different altitudes), and ran for 3 iterations. Based on this we plot the total energy generated w.r.t. varying P in Fig. In Figs, 3a and 3f we show the performance of the algorithms at two different locations (we also consider additional locations and time periods in Appendix F). We use different values of p > 1 to show the robustness of our algorithm (as increases, the importance of the service cost w.r.t. the movement cost in the overall objective increases). Our algorithm outperforms CGP-LCB for range of p values. As keeps increasing, we observe that MINC- KNOWN closes the performance gap to MD-K DD-KNOWN, and the same is happening with CGP-LCB w.r.t. GP-MD. In Fig. 33b] we focus on a particular 4. and notice that GP-MD performs better than CGP-LCB and STATIONARY algorithm at this location. In Fig. we plot the service cost and observe that both learning algorithms GP-MD and CGP-L.BB have lower service cost than the STATIONARY baseline. We also note that due to the implicit service cost definition, the KNOWN baseline achieves zero service cost. In Figs. |3 and Bel we compare the movement energy loss for p 4 and p 1. As expected, p = 1 results in slightly lower GP-MD movement energy loss due to the tradeoff shifting towards the movement cost.
5 Conclusions
We have considered the problem of optimizing unknown cost function subject to time-van marring contextual information, as well as movement costs of changing the selected action from round to
2 AAcordding to the power equation from 7 our movement cost is based on a fixed metric and is independent of contexts. Hence, we simply approximate Vu (ar t) by Vr and consider indeeeedenn movement costs.
E' (z, x²) would depend on (x t), whereas, we assume

---

round. Our problem formulation is motivated by Airborne Wind Energy systems, where one seeks optimize the operating altitude of the wind turbine maximize the amount of generated energy. We propose novel algorithm, GP-MD, which makes use of GP confidence bounds and employs the mirror descent techniques from [99 for solving MTS problems. We analyze the theoretical performance of our algorithm by providing a rigorous regret bound. Moreover, we demonstrate its performance in synthetic experiments and on an AWE application by using real-world data. GP-MD carefully trades off service and movement costs while at the same time learning about the unknown objective function and yielding improved performance (i.e., generating more energy) compared to the considered baselines. Our setup and analysis open up multiple interesting directions for further exploration. For instance, an extension to continuous action spaces via discretization arguments is an immediate direction for future work. Another interesting direction is to analyze the single-episode setting and obtain general sublinear regret guarantees.
6 Acknowledgements
The authors would like to thank James R. Lee and Christian Coester for the various discussions regarding their paper [19] during the course of this work. This project has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme grant agreement No 815943.
References
[1] Abbasi-Yadkori. Online learning for linearly parametrized control problems. 2013.
[2] Majid Abdolshah, Alistair Shilton, Santu Rana, Sunil Gupta, and Svetha Venkatesh. Cost-aware multi-objective Bayesian optimisation. arXiv preprint arXiv:1909.03600 2019.
[3] Abdulelah Alkesaiberi, Fouzi Harrou, and Ying Sun. Efficient wind power prediction using machine learning methods: comparative study. Energies, 2022.
[4] Leif Erik Andersson and Lars Imsland. Real-time optimization of wind farms using modifier adaptation and machine learning. Wind Energy Science, 2020.
[5] CJ Argue, Anupam Gupta, Ziye Tang, and Guru Guruganesh. Chasing convex bodies with linear competitive ratio. Journal of the ACM (JACM), 2021.
[6] Ali Baheri and Chris Vermillion. Combined plant and controller design using batch bayesian optimization: a case study in airborne wind energy systems. Journal of Dynamic Systems, Measurement, and Control, 2019.
[7] Ali Baheri, Shamir Kin-m,rim, Alireza Bafandeh, and Christopher Vermillion. Real-time control using Bayesian optimization: A case study in airborne wind energy systems. Control Engineering Practice, 2017.
[8] Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. Proceedings of 37th Conference on Foundations of Computer Science, 1996.
[9] Philip Bechtle, Mark Schelbergen, Roland Schmehl, Udo Zillmann, and Simon Watson. Air- borne wind energy resource analysis. Renewable energy, 2019.
[10] Ilija Bogunovic, Jonathan Scarlett, Andreas Krause, and Volkan Cevher. Truncated variance reduction: A unified approach to Bayesian optimization and level-set estimation. Conference on Neural Information Processing Systems (NeurIPS), 2016.
[11] Allan Borodin, Nathan Linial, and Michael E Saks. An optimal on-line algorithm for metrical task system. Journal of the ACM (JACM), 1992.
[12] Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Competitively chasing convex bodies. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, 2019.
10

---

[13] Sébastien Bubeck, Bo' az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing nested convex bodies nearly optimally. In Proceedings of the Fourteenth Annual ACM-SIAM Sympo- sium on Discrete Algorithms. SIAM, 2020.
[14] Sébastien Bubeck, Michael Cohen, James R Lee, and Yin Tat Lee. Metrical task systems on trees via mirror descent and unfair gluing. SIAM Journal on Computing, 2021.
[15] Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Scaling Gaussian process optimization by evaluating a few unique candidates multiple times. arXiv preprint arXiv: 12909, 2022.
[16] Ian Char, Youngscog Chung, Willie Neiswanger, Kirthevasan Kandasamy, Andrew O Nelson, Mark Boyer, Egemen Kolemen, and Jeff Schneider. Offline contextual Bayesian optimization. Conference Neural Information Processing Systems (NeurIPS), 2019.
[17] Sayak Ray Chowdhury and Aditya Gopalan. On kemeliizdd multi-armed bandits. International Conference Machine Learning (ICML), 2017.
[18] Sayak Ray Chowdhury and Aditya Gopalan. Online learning in kernelized Markov decision processes, International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
[19] Christian Coester and James R Lee. Pure entropic regularization for metrical task systems. Conference on Learning Theory (COLT), 2019.
[20] Christian Coester and James R Lee. Pure entropic regularization for metrical task systems. arXiv preprint arXiv: 1906. 04270, 2019.
[21] Bart M Doekemeijer, Daan C Van Der Hoek, and Jan- Willem van Wingerden. Model-based closed-loop wind farm control for power maximization using bayesian optimization: a large eddy simulation study. In 2019 IEEE Conference on Control Technology and Applications (CCTA). IEEE, 2019.
[22] Dave Elliot. Flights of fancy: airborne wind turbines, 2014.
[23] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 2004.
[24] Jose Pablo Folch, Shiqiang Zhang, Robert M Lee, Behrang Shafei, David Walz, Calvin Tsay, Mark van der Wilk, and Ruth Misener. Snake: Bayesian optimization with pathwise exploration. arXiv preprint (Xxx:2202.00060 2022.
[25] Gautam Goel and Adam Wierman. An online algorithm for smoothed regression and lqr control. International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
[26] Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. Conference on Neural Information Processing Systems (NeurIPS), 2019.
[27] Javier González, Zhenwen Dai, Philipp Hennig, and Neil Lawrence. Batch Bayesian optimiza- tion via local penalization. International Conference on Artificial Intelligence and Statistics (AISTATS), 2016.
[28] Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, and Barnabás Póezos. Multi hulti-fidelity Bayesian optimisation with continuous approximations. International Conference on Machine Learning (ICML). 2017.
[29] Tarun Kathuria, Amit Deshpande, and Pushmeet Kohli. Batched Gaussian process bandit optimization via determinantal point processes. Conference on Neural Information Processing Systems (NeurIPS), 2016.
[30] Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with heteroscedastic noise. Conference On Learning Theory (COLT), 2018.
11

---

[31] Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[32] Andreas Krause and Cheng Soon Ong. Contextual Gaussian process bandit optimization. Conference on Neural Information Processing Systems (NeurIPS), 2011.
[33] Remi Lam and Karen Willcox. Lookahead Bayesian optimization with inequality constraints. Conference on Neural Information Processing Systems (NeurIPS), 2017.
[34] Remi Lam, Karen Willcox, and David H Wolpert. Bayesian optimization with a finite budget: An approximate dynamic programming approach. Conference on Neural Information Processing Systems (NeurIPS), 2016.
[35] Chi-Heng Lin, Joseph D Miano, and Eva I. Dyer. Bayesian optimization for modular black-box systems with switching costs. Uncertainty in Artificial Intelligence (UAI), 2021.
[36] Minghong Lin, Adam Wierman, Lachlan LH Andrew, and Eno Thereska. Dynamic right- for power- proportional data centers. JEEE/ACM Transactions on Networking, 2012.
[37] Yiheng Lin, Gautam Goel, and Adam Wierman. Online optimization with predictions and non-convex losses. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2020.
[38] Jonas Močkus. On Bayesian methods for seeking the extremum. In Optimization Techniques, 1975.
[39] Nikolaos Moustakis, Sebastiaan Paul Mulders, Jens Kober, and Jan-Willens Willem van Wingerden. A practical bayesian optimization approach for the optimal estimation of the rotor effective wind speed. In 2019 American Control Conference (ACC). IEEE, 2019.
[40] Jinkyoo Park. Contextual Bayesian optimization with trust region (cbotr) and its application to cooperative wind farm control in region 2. Sustainable Energy Technologies and Assessments, 2020.
[41] Jinkyoo Park and Kincho H Law. A bayesian optimization approach for wind farm power maximization. In Smart Sensor Phenomena, Technology, Networks, and Systems Integration 2015. International Society for Optics and Photonics, 2015.
[42] C. E. Rasmussen and C. K. Williams. Gaussian processes for machine learning. volume 1. MIT press Cambridge, 2006.
[43] Mark Sellke. Chasing convex bodies optimally. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithmss SIAM, 2020.
[44] Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause. No-regret learning in unknown games with correlated payoffs. Conference on Neural Information Pro- cessing Systems (NeurIPS), 2019.
[45] Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause. Mixed strategies for robust optimization of unknown objectives. International Conference Artificial Intelligence and Statistics (AISTATS), 2020.
[46] Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause. Learning to play sequential games versus unknown opponents. Conference Neural Information Processing Systems (NeurIPS), 2020.
[47] Pier Giuseppe Sessa, Ilija Bogunovic, Andreas Krause, and Maryam Kamgarpour. Contex- tual games: Multi-agent learning with side information. Conference on Neural Information Processing Systems (NeurIPS), 2020.
[48] Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. Conference on Neural Information Processing Systems (NeurIPS), 2020.
12

---

[49] Jialin Song, Yuxin Chen, and Yisong Yue. A general framework for multi-fidelity Bayesian optimization with Gaussian processes. International Conference on Artificial Intelligecce and Statistics (AISTATS), 2019.
[50] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. International Conference on Machine Learning (ICML), 2010.
[51] Kübra Yazici and Semra Boran. Short-term wind power prediction approach based on bayesian optimization and ensemble learning. Journal of Intelligent Systems: Theory and Applications.
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]
(b) Did you describe the limitations of your work? [Yes] See Section
(C) Did you discuss any potential negative societal impacts of your work? [N/A]
(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? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
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 URL)? [Yes] Added in supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Internal Cluster was used
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "UCtdSdt6zhI", "reviewer": "Reviewer_UfT3", "summary": "This paper provides an algorithm for the problem of episodic Contextual Bayesian optimization (CBO) under “switching costs” associated with the decision at each round. This problem formulation is motivated by the application of altitude optimization for Airborne Wind Energy (AWE) systems, in which a wind turbine’s operating altitude can be changed between episodes in order to maximize energy production, but where the changing of altitude itself uses energy. Noting that this problem setup is similar to that in metrical task systems (MTSes) except that the objective function is unknown, the authors propose a Gaussian Process-based variation of the mirror descent schemes used to address MTS problems. They provide a bound on the cumulative regret of their algorithm, and show in both synthetic experiments and experiments in the AWE setting that their algorithm outperforms algorithms that neglect switching costs. ", "questions": "* In the AWE experiments, in the real-world setting, is $f$ known or unknown? If it is known, what is the justification for the current problem setup? If unknown, how are the MinC-Known and MD-Known baselines run for this experiment?\n* What is the implication of assumptions such as the regularity assumptions on $f$, which are utilized to construct the proposed method? How does that affect in what settings (related to wind energy production or more broadly) the method may not be expected to work?\n* How computationally intensive is the method, and how does that affect what settings it can be used in and/or how well it might scale?", "limitations": "* No limitations are discussed. However, at minimum, limitations associated with the assumptions made in the paper as well as (e.g.) computational complexity considerations associated with using GPs should be discussed.\n* In the checklist, the authors choose “N/A” when asked to describe any potential negative societal impacts of their work. However, as the proposed GP-MD algorithm is relatively general, it is of course possible that it can have bad applications in addition to the good ones (AWE) focused on in the paper.\n", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n* The paper is very well presented. Even as someone who is outside this area, I was easily able to understand the broad strokes of the motivation and approach (even if not the details).\n* The problem formulation seems well-motivated by a problem of societal importance, and per the authors’ claim is not previously addressed in the literature (though I am not familiar enough with the literature to validate this claim).\n* The proposed method is a nice synthesis of ideas proposed separately in the CBO and MTS setting.\n* The experiments are thorough and convincing, demonstrating and validating the settings in which the proposed algorithm and baselines do/don’t do well.\n\nWeaknesses: \n* In Section 4.1 (AWE experiments), it is not clear to me how MinC-Known and MD-Known were run as baselines if $f$ is in reality not known. Alternatively, if $f$ is in reality known in the AWE setting, then it is not clear to me why the proposed method is needed. More clarity on this would be helpful in understanding whether the current approach is indeed needed and/or how the experiments were run. \n* The authors do not meaningfully discuss any limitations of their approach. However, at minimum, limitations associated with the assumptions made in the paper as well as (e.g.) computational complexity considerations associated with using GPs should be discussed.\n\nMinor points:\n* Would it be possible to add error bars to Figure 1?", "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": "K_KdY3qLg3l", "reviewer": "Reviewer_LNYH", "summary": "This paper proposes a contextual Bayesian optimization algorithm with penalisation for movement cost, which is motivated by the problem of tuning the altitude of wind turbines to maximize energy output while minimizing the altitude adjustment. That is, a movement cost is incurred which is larger if the difference between the actions selected in the current and the previous steps is larger. The proposed algorithm is based on the problem of metrical task systems, and combines lower confidence bound from Bayesian optimization with online mirror descent. The regret of the proposed algorithm is analysed, and the algorithm achieves competitive empirical performances in a real-world wind energy systems experiment.", "questions": "- Some of the questions have been listed under Weaknesses in \"Strengths And Weaknesses\" above.\n- Equation (3), and lines 128-129: I'm curious about the connection between the regret definition here and the usually adopted regret definition in contextual BO/contextual bandit (e.g., reference [30] in the paper). Does the \"offline optimal action sequence\" also have the knowledge of the groundtruth functions of f and d? If we let $\\alpha=1$ and $\\beta=0$, will equation (3) reduce to the same regret definition as that in contextual BO/contextual bandit?", "limitations": "I didn't find discussions of limitation. I can imagine that potential limitations could be the dependence on $H$ (which I discussed at length under Strengths and Weaknesses), and that the action space is required to be discrete. The paper has no negative societal impact that I can think of.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proposed problem of contextual BO with movement cost is well motivated, through the AWE systems. The experiment on AWE using real-world wind data is also a nice demonstration of the practicality of the proposed method.\n- The idea of using the confidence bounds often adopted in BO as a bridge to connect BO with online learning algorithms is a very interesting and promising idea.\n- The experiments are well designed, and the experimental results indeed show the advantage of the proposed method.\n- The paper is well written.\n\nWeaknesses:\n- Two recent works on BO with movement cost are missing:   \n[1] SnAKe: Bayesian Optimization with Pathwise Exploration, 2022.    \n[2] Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times, 2022.   \nThe methods in both of these papers are also motivated by the issue of movement cost (i.e., a larger cost is incurred if the selected inputs in two consecutive iterations have larger differences). Both papers were available in Jan 2022, and hence I believe they should have been discussed and compared with.\n- I have a major concern regarding the dependence of the regret bound (Theorem 1) on the episode horizon H. Normally, in BO and other bandit algorithms, we consider the regret in every step. That is, if there are in total $T$ iterations/steps, the final theoretical result is usually presented as an upper bound on the total cumulative regret **across all $T$ steps**. In the context of this paper, it will translate to the total cumulative regrets across all $H\\times N_{ep}$ steps. However, the regret bound in Theorem 1 has an undesirable dependence on H: for the squared-exponential kernel, both terms in the regret upper bound depend on $H$ linearly, which implies that the total regret in all $H\\times N_{ep}$ steps is linear in the number of steps ; for the Matern kernel, the dependence of the first term on H will be super-linear, implying super-linear total cumulative regret.\n- Related to the last point, lines 237-238 says that \"a similar dependence on H is also present in the batch Bayesian optimization results and analysis that we also build upon (see [19, Theorem 2])\". I understand what is meant here, but I think this statement is misleading. In [19], their regret bound has a dependence on $\\exp(\\gamma_H)$ ($H$ will correspond to the batch size in [19]) rather than $H \\times \\exp(\\gamma_H)$. Moreover, the regret bound depending on $\\exp(\\gamma_H)$ is only their intermediate results, and in their subsequent analysis, they had shown that by following a special initialization procedure, the dependence on $\\exp(\\gamma_H)$ can be replaced by a constant which is independent of $H$. Therefore, I think [19] should not be used to justify the dependence of the regret bound on $H$ in this paper. Please correct me if I had any misunderstanding here.\n- Also related to the point above regarding the dependence on $H$: lines 263-264 say that \"We run the algorithms over a single episode\" and that \"We also discover that updating the confidence bounds after every timestep in GP-MD leads to better performance in practice\". Therefore, it seems that in your practical implementation, you have entirely ignored the episodic setting and reverted back to the standard contextual BO setting. If I understand correctly, (if you ignore the heuristic of updating the confidence bounds after every timestep) in this setting, $H$ will be equal to $T$, and hence your regret bound will not be sub-linear anymore as I discussed above in the point on the dependence on $H$.\n- Given what I have discussed in the three points above, I think an explanation as to \"why the theoretical analysis follows the episodic setting\" is needed. Because for now, it seems to me that the episodic setting is only adopted so that the final regret upper bound can be sub-linear in the total number of episodes, while in practice, the episodic setting is not needed.\n- (minor) The paper is in general well written, including the method section of Section 3. The only place I think needs more explanations/intuitions is equation (12) and the paragraph following it.", "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": "JZwsK572unt", "reviewer": "Reviewer_htxZ", "summary": "The paper proposes and resolves the episodic contextual Bayesian optimization (BO) with movement costs by combining BO and an existing online learning solution to the metrical task system. The proposed algorithm, GP-MD, is proved to have a sublinear regret guarantee. Furthermore, GP-MD is empirically shown to outperform existing contextual BO in problems with movement costs, especially the real-world optimization problem for wind energy systems.", "questions": "Please clarify on the episodic setting in the experiments and scalability of the proposed approach mentioned above.", "limitations": "The authors could improve the discussion on the scability of the work with respect to the size of the action and context spaces.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The proposed problem of contextual BO with movement costs is new and significant in practice (e.g., with the applications to wind energy systems). Even though I have not thoroughly gone through the appendix, the proposed algorithm is sound and convincing. The empirical performance of GP-MD is shown in both synthetic and real-world optimization problems.\n\nOn the other hand, if I am not mistaken, the setting in the experiments is not episodic: in the algorithm and analysis, the GP posterior is updated after each episode, while in the experiments, the GP posterior is updated after every timestep and the experiments are performed in only 1 episode. To be consistent, the experiments should be performed in multiple episodes, or the algorithm and analysis should be done with GP posterior updated after every timestep. I am also curious about the real-world example where the episodic setting applies.\n\nHow is the proposed algorithm scalable to larger action and context space? When the dimension of the action and the context space is larger (e.g., 4 or 5), discretizing the space will result in a large number of points. Therefore, a discussion or the time complexity analysis of the proposed algorithm with respect to the size of the action and context spaces can be helpful.\n\nIn the real world experiment, the GP hyperparameters are assumed to be known (fixed), which is not very practical.\n\nThere is a minor typo: Ne -> Nep in line 132.\n", "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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "2HHdu2IKeR", "reviewer": "Reviewer_rb6B", "summary": "This paper studies the problem of contextual Bayesian optimization that considers the cost of switching decisions at each round. The main idea is incorporating the online learning for metrical task systems and introducing a randomized mirror descent algorithm. The paper provides regret guarantees and evaluate on altitude optimization for Airborne Wind Energy Systems. Empirically, the proposed approach consistently outperforms baseline CBO approaches.", "questions": "- Why does the paper only considers CBO with moving cost, not the vanilla BO with moving cost? If vanilla BO with moving cost, would the problem be reduced to  multi-objective BO?\n- Why does the experiment not compare to the method in paper \"Bayesian optimization for modular black-box systems with switching costs\"?\n\nI would like to hear more justifications on these questions from the authors.", "limitations": "- No mention on open-sourcing the code.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Study an important and novel problem in contextual Bayesian optimization that considers moving cost between configurations.\n- Good real-word case study.\n- Writing is easy to follow.\n\nWeaknesses:\n\n- Possible missing comparison to other baseline.\n- No code released.\n\nOriginality:\n\nThe originality of the paper is two folds. First, it proposes a new problem that has not been studied explicitly in the prior work. Second, it introduces a new method to solve this problem, although the majority of the proposed algorithm is derived from existing work by Coester and Lee.\n\nQuality:\n\nThe problem is well defined and the proposed method is complete. The algorithm is not complicated which makes the approach accessible to potentially wide audience.\n\nClarity:\n\nThe writing is clear and easy to follow.\n\nSignificance:\n\nThe paper studies a very important problem in contextual Bayesian optimization that considers moving cost between configurations.\n", "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