Optimizing Conditional Value-At-Risk of Black-Box Functions
Authors: Quoc Phong Nguyen
Zhongxiang Dai
Bryan Kian Hsiang Low
Patrick Jaillet
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian optimization
conditional value-at-risk
CVaR
UCB
Thompson sampling

Abstract: This paper presents two Bayesian optimization (BO) algorithms with theoretical performance guarantee to maximize the conditional value-at-risk (CVaR) of a black-box function: CV-UCB and CV-TS which are based on the well-established principle of optimism in the face of uncertainty and Thompson sampling, respectively. To achieve this, we develop an upper confidence bound of CVaR and prove the no-regret guarantee of CV-UCB by utilizing an interesting connection between CVaR and value-at-risk (VaR). For CV-TS, though it is straightforwardly performed with Thompson sampling, bounding its Bayesian regret is non-trivial because it requires a tail expectation bound for the distribution of CVaR of a black-box function, which has not been shown in the literature. The performances of both CV-UCB and CV-TS are empirically evaluated in optimizing CVaR of synthetic benchmark functions and simulated real-world optimization problems.

Optimizing Conditional Value-At-Risk of Black-Box Functions
Quoe Phong Nguyen, Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet' Dept. of Computer Science, National University of Singapore, Republic of Singapore Dept. of Electrical Engineering and Computer Science, MIT, USA! {qphong, daizhongxxaagg 1 wwwwww@ooom nus. edu.sg, jaillet@mit. edu
Abstract
This paper presents Bayesian optimization (BO) algorithms with theoretical performance guarantee to maximize the conditional value-at-risk (CVaR) of a black-box function: CV-UCB and CV-TS which based on the well-established principle of optimism in the face of uncertainty and Thompson sampling, respec- tively. To achieve this, develop an upper confidence bound of CVaR and prove the no-regret guarantee of CV-UCB by utilizing an interesting connection between CVaR and valte-at-risk (VaR). For CV-TS, though it is straightforwardly performed with Thompson sampling, bounding its Bayesian regret is non-trivial because it re- quires a tail expectation bound for the distribution of CVaR a black-bor function, which has not been shown in the literature. The performances of both CV-UCB and CV-TS are empirically evaluated optimizing CVaR of synthetic benehmark functions and simulated real-world optimization problems.
Introduction
A wide range of applications from Auto-MI. [15] to chemistry 6 and drug design 3 require
optimizing a black-box objective function (i.c., its closed-form expression, gradient, and convexity are unknown) through observing noisy function evaluations. To resolve this problem, an efficient class of algorithms, called Bayesian optimization (BO) 2 20), has seen rapid development lately.
One of the recent developments of BO considers searching for the optimization variable x, that maximizes the objective function f W)] []. Different from the classical BO, there exists an environmental random variable W that cannot be controlled, which happens frequently in real world problems. For example, to maximize the crop yield (i.e., f(x, W)) by controlling the amount of fertilizer (i.e., x), there various uncontrollable weather conditions such as the temperature, lighting, and rainfall (i.e., W) [33 Thus, even though an amount of fertilizer x increases the crop yield most of the time, there exists risk/chance that under certain weather conditions (realizations of W), the same amount of fertilizer leads to low crop yield (an undesirable realization of the random variable fxx W)). This issue renders the optimization of f(x, W) futile, the work of proposes to optimize a risk measure, denoted as p. of f(x, W) such as value-at-risk (VaR) and conditional VaR (CVaR). However, its approach suffers from two main shortcomings: the computational cost of nested optimization procedure and the lack of theoretical performance guarantee. Although these drawbacks are addressed in the work of [3], its proposed algorithm only works for optimizing VaR of a black-box function. Hence, efficient algorithm with theoretical performance guarantee for optimizing CVaR of a black-box function remains an open question.
Nonetheless, optimizing CVaR of black-box function is desirable, especially when the effect of optimizing CVaR cannot be obtained by optimizing VaR. A prominent property of CVaR is its sensitivity to values at the extreme tails of the random variable f(x, W), which VaR does not exhibit 99 Let us consider two portfolio allocation schemes: one scheme has unacceptable
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

corst-case value of the return and the other does not. It is possible that the two schemes have the same VaR of the return because VaR insensitive the extreme tails of the return (e.g.. the worst-case value of the return). On the other hand, CVaR is able to distinguish the risks of the two schemes. This advantage of CVaR is further clarified in Remark [
In this paper, we adopt the settings of 4 13 the distribution of W is given and we can control/select the realization w of W in the optimization procedure. In practice, the distribution of W can be estimated from data (e.g., weather historical data in the crop yield optimization example) and we can perform BO in a laboratory or using computer simulation where W is controlled 4 After the optimization, the optimal X can be used in the real-world environment with the uncontrollable W. Our main contribution is to propose two computationally efficient algorithms (Sec. 33 with theoretical performance guarantee (Sec. I for optimizing CVaR of a black-box function.
First, we propose CVaR optimization with upper confidence bound (CV-UCB) that is based on the well-established principle of optimism in the face of uncertainty. By exploiting the connection between CVaR and VaR, we are able develop a confidence bound of CVaR (Sec.3.1.I] and prove the no-regret guarantee of CV-UCB (Sec. (.1).
Second, we propose CVaR optimization with Thompson sampling (CV-TS) which can be naturally extended to handle batch queries (i.e., gathering observations at a batch of inputs in each BO iteration). The capability of gathering observations in batch simultaneously is often available and preferable in laboratory settings and computer simulations. Though CV-TS can be simply performed with the popular Thompson sampling (or posterior sampling) [8 (Sec. B.T.2), bounding its Bayesian regret is challenging as the distribution of CVaR in our problem has not been investigated before and its support is unbounded. Fortunately, expectation of CVaR to that of the function evaluation f(x, w) (Sec. 4.2). The latter follows a Gaussian distribution with known tail expectation, unlike that of CVaR.
able to relate the problem of bounding the tail
We empirically evaluate the performance of both CV-UCB and CV-TS in optimizing CVaR of synthetic benchmark functions, an optimization problem of the residuary resistance per unit weight of displacement of a yacht, a portfolio optimization problem, and a simulated robot task (Sec. (5)
Related works. Existing solutions to optimizing a black- box function f(x, W) with an environ- mental random variable W are different in the assumptions about W and the objective function. Other than the aforementioned works of 4 1 where we adopt the assumptions that the distribution of W is known and w can be selected during the optimization procedure, the work of 9 also proposes an efficient algorithm with theoretical performance guarantee under the same assumptions to maximize the probabilistic threshoid robustness measure. This measure requires a threshold of the desirable performance, instead of a risk level (i.e., the probability of undesirable performance) in CVaR and VaR. Another related work is adversarially robust BO [ which maximizes f(x, w) with the worst-case realization of W. It can be cast an optimization problem of VaR of a black- function [3]. The work of [00 assumes that the distribution of W is given, but W is sampled from its distribution during the optimization. Its objective is to balance between the mean and the variance of fx, W) from different perspectives: multi-task learning, multi-objective optimization, and constrained optimization. The work of (22) maximizes VaR and CVaR of a black-box function, yet, it assumes W is unobservable and its distribution is unknown. It suffers from an approximate posterior belief and the lack of theoretical performance guarantee, The works of [12 (namely, distributional robust BO) assume that the unknown distribution of W belongs to an uncertainty set of distributions. They maximize the mean of [xx W) under the worst-case realization of the unknown distribution of W in the uncertainty set.
2 Background
2.1
Conditional Value-at-Risk
Let the black-box function of interest be a real-valued function f(x, w) where x E X C " and w E W C _ Let W denote the environmental random variable whose probability distribution is specified by ( = w) for all w E W. Let fx, W) denote the random variable representing the function evaluation at x and a random realization of W. The conditional value-at-risk (CVaR) of fxx W) at risk level a E (0,1) 1) is defined as:
(x(x)) A [f f(x, W) ax(
(1)
2

---

which is the expectation of f(x, W) over function values that are at most the value-at-risk (VaR) at the same risk level a defined as (x; a.) & in P( W) s w) 2 a).
(x) W))
f(xo. W)
vy (x(x0; a)
cx(xo: a) [x] w)l f(xo, W) s vx(xo:a))
p(f(x1, W))
α
f(x1, W)
vy (x1;a)
(x (x1 W) f(x1, W) S ())x)
Figure 1: Plot of the lower tails of f(xp, W) and fx1, W) with their VaR and CVaR at risk level a. The shaded area is a. It is observed that vy (Xp; a) vy (X1: at) but ey (Xn;a) > ey (x);
Remark (CVaR VaR), While VaR at is interpreted as the a-percentile of f(x, W), CVaR is interpreted as the expectation of function values that are at most VaR. Therefore, CVaR is sensitive to the function values less than VaR, while VaR is not. Fig. shows example of function evaluations at Xg and X1 such that their VaR values (i.e., their ax-percentiles) are the same. We observe that VaR insensitive to the tails of f(x, W) which are different in this case (see the region around the black dot). In contrast, ey (Xx; at) > cx(; a) which conveys the idea that f(x,, W) has a lower risk of low function values as the probability density of function values less than VaR concentrates region nearer to VaR than that of f(x1, W). Thus, CVaR is more risk-aversed than VaR, especially when the distribution of fxx W) has a heavy lower tail, which makes it more suitable for critical applications. In the portfolio optimization problem, if the distribution of the portfolio's 's return has negative outliers (which are captured in CVaR), the average return in the long run can be negative even though the VaR of the return is positive.
In this work, assume that | is finite to simplify the theoretical analysis (described in Sec. 4 and the evaluation of CVaR. The latter requires the computation of the cumulative probability mass of fxx W) by enumerating all possible realizations of f(x, W) (described in [4].
2.2 Bayesian Optimization of CVaR and Gaussian Processes
BO of CVaR. In this paper, would like to maximize CVaR cy(x; a) ① of f(x, W) given the distribution (W) by iteratively gathering observations as noisy function evaluations y(x, w) & f(x, w) + Exx, w) where e(x, w) ~ [00,, a.). The gist of BO of CVaR is a strategy to select the input query (x,, wt) iteration such that the maximizer x. E argmaxxex cy a) is found as rapidly as possible. Note that while W is controllable in BO, after the optimization, the optimal x, have all observations at input queries in the previous - 1 iterations, denote as D,-1 = D.-2 U ((x--1, w.-1)) (()- (Do denotes the set of initial observed inputs). These observations yD.., A (y(x, w)) used to construct the posterior belief/distribution of the underlying black-box function f(x, w) which utilized in building the query selection strategy. Let us revisit Fig. [ (xox a) > ey (x1;a) implies that Xo is preferred to X1- It is because the risk/chance of getting low function values at smaller (see the region around the black dot). In contrast, VaR cannot differentiate the risk of (xo, W) and that of fx1, W) since their VaR values the same.
can be used in real-world settings where W uncontrollable. At iteration

---

Algorithm BO Algorithms for optimizing CVaR of a black-box function
1: Input: algo, X, W, initial observation YD.. prior μi 0, nn;
2: 1,2.... do
3: (Selecting x+
4: if algo CV-UCB then
5: Select X, E argmax Cu. ax:a) x
6: else if algo is CV-TS then
7: Sample function fi from the GP posterior belief given YD,
8: Select E argmax c/ (x:a)
9: end if
[Selecting We
11:
Find 0₁ E arg max Vne- (xx; Ul__, (xx:a) a'E(0,n]
12:
Given at, select W, as an LV w.r.t. Xt, 1t and 4-1 [Collecting data and updating GP)
13:
14:
Incorporate new observation at input query: YD, = YD. U U w:))
15:
Update the GP posterior belief given YD.
16:
end for
Gaussian process (GP). In order obtain the posterior belief of f(x, w) given noisy observations YD.-1 we model the black-box function f with a GP: every finite subset of [f(x, () follows multivariate Gaussian distribution [17. Thus, GP is fully specified by its prior mean which
assumed be zero and its covariance function/kernel k(x, w:x', w') & covl [x, w), f(x', w')l Given noisy observations YD.-, at iteration t, the posterior belief p w)lyD...) is a Gaussian specified by the following mean and variance:
1x-1(x, w) K AD..YD... o w)
A x(x,, w) D A KD.IIXW
where x(x, w) xx, W: w;X,w). w). Kx Wx.:D._. - (n(x, w:x', w (e KD..
KJ Kxw:D,,.' and AD. - (KD. D. I (I is the identity matrix and KD, DD, (s(x', w'x"", w")) (x). xxD...
Although f(x, w) follows Gaussian distribution, CVaR cx a)) (defined in I does not. Further- more, although [W] is finite, the distribution of CVaR is continuous because the black-box function evaluation is real-valued. Besides, the support of f(x, W) unhounded, CVaR. These points pose challenges in deriving the following 2 algorithms and their theoretical analyses.
BO Algorithms for Optimizing CVaR of a Black-Box Function
In this section, present two BO algorithms for optimizing CVaR of a black-box function f(x, W): CVaR optimization with upper confidence bound (CV-UCB) and CVaR optimization with Thompson sampling (CV-TS). These two algorithms
different in the way of handling the exploration- exploitation trade-off in the selection of x; to find argmaXxex Cy Ex( a) (Sec. (Sec. 3.1.II and Sec. 3.1.2). On the other hand, given the selected x,, selecting w, is only about reducing the uncertainty of CVaR Cy (xe; a.). Therefore, we would like to design single selection strategy of w, that works for both CV-UCB and CV-TS (Sec. 3.2)
3.1 Selection Strategy of X,
3.1.1 A UCB-based Approach Select x, in CV-UCB
In (T). CVaR ey (x; a) risk level a of f(x, W) defined as the expectation function values that are at most VaR at risk level [4]. While this definition (I) is interpretable, it is challenging to devise because (T) requires learning about not only (i) VaR (y(x;a) o:) but also (ii) the probabilities of function values less than (x(x;;) a)) Even though the former (i.e., VaR uy (x; ar) can be optimized using the V-UCB algorithm 13 remains a challenge to leam about the latter.
a no-regret BO algorithm based on (

---

Interestingly, in this section, we present an approach that does not resort to handling the above two problems (i) and (ii) separately. To achieve this, we employ an alternative definition of CVaR which is an expectation of VaR over the risk level:
fx(x;))=11 1 L1 "y(x; d'd' da'.
Although (1) is more interpretable and is often used to evaluate CVaR, the above definition 3 paves
the way selection strategy of x, in CV-UCB: by utilizing (3), are able to construct an upper confidence bound of CVaR relying on that of VaR. Recall that the work of [3] proposes a confidence bound of VaR at iteration t, denoted as (==1(y(x;a)) a()]:
(4) where vi,_, ax: and V (x: are VaR (due to the randomness in W) of 4x-1 W) and Ut-1 (x. W). respectively. At iteration t, for all (x, w) E X x W, (4-1(x, w), 14 (x, w) is
1x1l0y(x; a')] - [x; a'), Vue-, (x: [x) VX Vo' (0,1)
confidence bound of f(x, w) (due to the uncertainty in the unknown black-box function f) depending on an exploration parameter Be [3:
40-1(x, w)
& u1 (x, w) - 81/20 0--1, w) 14 14-1((x, (x, w) + 3//22 0x-1 w)
(5)
U/-1 (x, w)
where 14t-1(x, (x. w) and 1x-1 w) are defined in 2 The exploration parameter 3g is to balance between exploitation (based on the GP posterior mean (x, w)) and exploration (based the GP
posterior standard deviation 0; (x, w)). which is specified later in Lemma]] I From (3), a confidence bound 11-1cc (x; a)] of CVaR follows the confidence bound 1 (x: a']l of VaR 4
%- vi, (x;ax))))) da' [
1 = a 1-' Uu (x: (x, a') da
[x=1ey(xxaa] A [ch,, (x: a), Cu. a]] -
Given the above upper confidence bound Cu,-, (x; of CVaR, we select x2 its maximizer (line 5 of Algorithm []. The time complexity of the selection strategy of x, in CV-UCB is
O(Dr,11* + Twain [W]DD, + |W] log ()) where Mhain is the number of gradient descent steps to find argmaxx Cu, (x; a). O(D, (3) is to compute AD 1 in (2) O(WW)D, (2) is the
GP prediction time complexity, and (((P) log (W) is evaluate CVaR.
3.1.2 A Thompson Sampling Approach to Select x, in CV-TS
An alternative approach to select x; is based on Thompson sampling 18] X2 is selected as a sample of the maximizer x, of CVaR ef (x;a). Unlike the selection strategy of x, in CV-UCB that requires an exploration parameter 33 (Sec. 3.I.I.. the exploration-expllotatii trade-off in Thompson sampling naturally handled by the randomness in the sampling of the maximizer of cy(x; a). This approach can also be extended to handle a batch query at each BO iteration by drawing a batch of samples of the maximizer of Cy ax). While unexplored for BO of CVaR, batch queries are popular in BO 8 IT].
literature
A sample of the maximizer of cx a:) is obtained by the following 2 steps (lines 7-8 of Algorithm I First, we draw a function sample fi from the GP posterior belief by using random Fourier feature approximation [16] which is also employed in classical BO works 7 23 (line 7 of Algorithm
Second, given fi, we maximize CVaR Cf (x; o:) to obtain its maximizer. This is a sample of the
maximizer of ey (x; which is assigned to x, in CV-TS (line 8 of Algorithm 1}. The time complexity
of the selection strategy of in CV-TS is ((D.,1 13 + Ma (n + | log (W]) where Niteture is the number of random Fourier samples, Parain is the number of gradient descent steps to find argmaxx Cf, (x: a), ((Dr11l)) is to compute AD.., in @ (which dominates the time complexity to draw function fi from the GP posterior belief), On is the time complexity evaluate fi, and O [ log WI) is to evaluate CVaR.
3.2 Selection Strategy of w, Shared by Both CV-UCB & CV-TS
Given the selected x, at iteration 4, we would like to propose a single strategy of selecting w, to reduce the uncertainty of CVaR ey (xx:a) for both CV-UCB and CV-TS that still guarantees no-regret for both algorithms shown in Sec. 4
5

---

Our main idea is to prioritize learning about VaR at risk level a which has the highest uncertainty among VaR 0y(x; a') at risk levels a' E (0, a]. In turn, it reduces the uncertainty of CVaR from @
We quantify the uncertainty of VaR by the size of its confidence bound (4. Thus, is defined as (line 11 of Algorithm
Oe E arg max Un--1 (x;;0)) 1 (x4;a') a'E(0,a)
To reduce the uncertainty of vy (xe: quantified by the size of its confidence bound Vu, (Xx; oz) 2i,-, (xx; ar), let us view vy (Xx; at) as the at ay-percentile ae-eercentll of f(x,, W) if the set of w where f(,, w) is at most the au-quantile of f(,, W) (i.e., the lower tail of fxx,, W) upper bounded by its a; dp-peccentlle) remains unchanged under different realizations of especially its lower confidence bound 4-1 and its upper confidence bound u4-1 On the contrary, if there exists WLy that violates the above statement due to the uncertainty of f(x,, WLv) (due to the unknown f), would like to gather observation at (x,, WLv) reduce the uncertainty of its function evaluation. Such Wiy is formally defined as the lacing value (LV) which is shown to exist in [3]
f(x,, W). There is no uncertainty in the
Definition 1 (Lacing values [3] Lacing values (LV) with respect to E (0, 1), E X, 4-11 and u are WLV E W that satisfies 1 WLv) I 2/ " S Vu (x; I u4-1 (x, WLV). equivalently, I 11-111 (x; a)] C 111- WLV), 44 (X. WLv)]-
Thus, we select w, as an LV with the maximum probability p( W). It is a heuristic to improve the performance suggested by [13 For CV-TS, avoid repeating inputs in the batch query, we can select w, sample of the random variable W by restricting its support to the LVs (if there are multiple LVs).
Ctz, Xx, 4-1. and 1 If there are multiple LVs, we select the LV
4 Theoretical Analysis
This section presents our theoretical analyses of CV-UCB and CV-TS. We choose the exploration parameter Be in (5) following a lemma in 21 We assume a discrete domain X for simplicity (and
[ is finite).
Lemma (Lemma 5.1 in 21 Pick 5 E (0. 1) and set Br log X
W| /8)), where Σ1 me
1, n. 0. Then,
[f(x, w) /1- 14-1 w)l S 8//2 (x, V(x,
X
holds with probability 2 1-88 8.
Thus, given the above Sr, the function evaluation, VaR, and CVaR are their confidence bounds (in and (6), respectively) with probability 2 1 6.
4.1 CV-UCB
The performance of CV-UCB is measured by the cumulative regret adopted from existing BO works, e.g., in 13 Rr & Σ Ti which is the sum over instantaneous regrets, denoted as - (x.; 0) cy (x; a:) where x. E argmaxxex Cf (x; a)) is the optimal value of the optimization variable. this section, we would like show that the cumulative regret of CV-UCB is sublinear so that limy RT/T=
Since CV-UCB selects x, the maximizer of the upper confidence bound of CVaR (line 5 of Algorithm D. it can be shown in Appendix that the instantaneous regret is bounded by
S Cay (x:3a) a, -x;;(xx;; (x);a)
with probability 2 - 5. Then, by exploiting the relationship between CVaR and VaR in (3) and the fact that the average of set of values is at most the maximum value of the set, the bound on r; can be simplified to the size of a confidence bound of VaR at risk level ar 7 in Appendix
Tt S Uw (xx; ax))
0 (xx; ax))
(10)
Shrewd readers may notice a difference between the intuition and definition of LV (S vs. <). It is to handle the case when there is only 1 LV..

---

holds with probability 2 1- 8. Furthermore, utilizing the property of w, as an LV in Definition I it can be shown in Appendix that
Fr. S 2 0, (x,, wt)
(11)
with probability 2 1- 11-d 8. Then, we follow [21] to construct the following theorem which shows a sublinear regret bound for CV-UCB (detailed in Appendix B).
Theorem 1. By selecting X, as the maximizer of the upper confidence bound Cau-1 (x; o:) (line 5 of
Algorithm D and selecting W, as an LV w.r.t. at Xt. 41 and U (line 12 of Algorithm I
RT S V CiT3T7
(12)
holds with probability 2 1 - where C₁ 8/ log(1 1 on²), 22 is the maximum information gain about that can be obtained by observing any of T observations (which is bounded in [2]] for several commonly used kernels), 37 and d are defined in Lemma
4.2
CV-TS
The performance of CV-TS is measured by the Bayesian cumulative regret
18
Bayes A RT
E ( (x; where the expectation includes the randomness in the GP prior
Bayes - E(cr(x,;a) - cy(x; a:) yDb..l of f. the observation noise, and x,. Let us denote T1 where the expectation includes the randomness in the GP posterior of given VD.., and x,, then
Re =E -T Bayes In this section, we would like show that the Bayesian cumulative regret
of CV-TS sublinear so that lim (to ease the notation, we omit ;D
Reg Bayyes /T O. Following 18 we can decompose r; Bayes into
Bayes S E|A
(xx: a) E|A "pper (x,;a) + E(c,,,
Cl.-1 (Xx: a)]
(13)
where llower (x & max(O, o, (x;:a) cf(xx; a)) and A upper (x,;a) & max (x,iaa)
C a)) (shown in Appendix C..
From Appendix Car-1 (xx: -, (Xx; a)) is bounded by 2/21/2 o (x,, w.) provided that w; is an LV w.r.t. ag Xt, 4-1, and u (line 12 of Algorithm
Thus, we are able to obtain
bound on the last term of the decomposed r
Rayes
13):
B(cm,_, Cu- (x); s 20./2 0x-1 wt)
(14)
However, the challenge remains in bounding the first two terms (i.e., |[[Aooer(xss a)) and EJA.pe a)) of the decomposed Bayes [33 These terms are the expectations over the tails of CVaR. As suggested by the seminal work [88. bounding these terms may require CVaR to have a bounded support or strong tail decay. However, in our BO formulation where f is modelled with a GP, the support of CVaR unbounded. Thus, derive the bound of the tail expectation of the unfamiliar distribution of CVaR, our key idea is to relate it to the tail expectation of a Gaussian distribution through 3 steps: first, relating this tail expectation of CVaR to that of VaR in Lemma 2 second, relating the tail expectation of VaR to the tail probability of VaR in (16), and third, relating the tail probability of VaR to that of function evaluation f(x, w) in Lemma As f(x, w) follows a Gaussian distribution, can bound its tail expectation.
Lemma (From tail expectation of CVaR to that of VaR). For all x E X,
1 10 E ([Aloer(xx a') da'
E A lower (x: a)] <
(15)
where A Alowor
(x; a') A max (0, (1,,((;;a)) by (x(xxa)) (shown in Appendix D
Furthermore, as A lower( (x; a') is a non-negative random variable, its expectation expressed as an integration over the tail probabilities: Va' (0, 1), x E X.
15 can be
E A lower (ower(x;; az) = 6-00
000
P(A lower (x; a') > w) du 1 P(o (x; az) - By (x(x)a) > w) dw
(16)

---

Then, we are able to relate the tail probability P(o,,_, (x; a') of the function evaluation f(x, w) using our key observation on the relationship between the events: (a) VaR "y(x; a') falls below its lower confidence bound v (x; (x;a') by w 2 0 and (b) the function evaluation [(x w) falls below its lower confidence bound (x, w) by w the following lemma (proved in Appendix E.
(x ax))xa')) > w) to the tail probability
Lemma 3. Consider a realization fi of the black-box function f following the GP posterior belief given YD.., that satisfies
Vi, (x; USa (x: a')
for a' E (0,1), X. and w 2 Let Wh-1 A {w E W. 1xx, w) 2 vhe (x: Then,
3wo E W 4-1(x,, wo) fi(, wo) w.
As the tail expectation of the Gaussian random variable f(x, w) can be evaluated, we can utilize the above results ( (15). (16). and Lemma 3) to obtain a bound of E[Alower (x; (and similarly, a bound of E [x: a for all X. These bounds and (14) lead to the following theorem on the Bayesian cumulative regret bound (proved in Appendix
Theorem 2. Assuming a bounded GP prior standard deviation: <(x, w) S 1Vx, w) E W, by selecting X as sample of the maximizer of e (x; ax) (lines 7-8 of Algorithm I and selecting w, as an LV w.r.t. ar (7) Xx, 1e-1, and 4 (line 12 of Algorithm T.. then the Bayesian cumulative regret
is bounded by
Bayes 8v2
+ VITTBT
(17)
V
where C A 8/ log[1+ on "T the maximum information gain about f that can be obtained by observing any set of T observations, Br and ō are defined in Lemmal |
Remark 2. We can extend CV-TS select a batch query of size ic (instead of a single query) at each BO iteration by drawing ht samples of the maximizer of CVaR and finding their corresponding o, and LVs (detailed in Appendix G). We can also show that the difference between the average (over the number of observations) of the Bayesian cumulative regret bound of CV-TS with batch queries and that of CV-TS with single queries is small for a large number of observations (Appendix GG), which is similar to result in 11 for the classical BO with Thompson sampling. However, with larger batch size k more observations can be obtained given the same number of BO iterations. Thus, the use of CV-TS with large batch size k is advantageous if obtaining observations at the batch query is feasible, e.g., by running multiple simulations in parallel.
Remark 3. Our CV-TS algorithm and its theoretical analysis can be utilized to construct a BO algorithm to optimize VaR of black-box function. Like CV-TS, this algorithm is also capable of handling batch queries. Since it is beyond the scope of this work (which is about CVaR), we refer readers interested in optimizing VaR of black-box function to Appendix H
5 Experiments
We empirically evaluate the performance of CV-UCB and CV-TS by comparing them with the work of [4) To the best of our knowledge, it is the only existing work that optimizes CVaR of a black-box
function by selecting both x and w. In partieular, the pKG algorithm is selected as a baseline thanks to its time efficiency and competitive empirical performance as demonstrated in [4] There are 2 variants of CV-TS in the experiments: CV-7S k which selects I input query at each iteration and CV-TS k = 3 which selects 3 input queries at each iteration. Each experiment is repeated 10 times with different random seeds account for the randomness in the observation noise, the set of initial observations, and the sampling from the GP posterior belief. Both the average and the confidence interval of the logarithm of the inference regret (taken from 7 23 are reported. The hyperparameters of GP and the noise variance are learned from the observations using maximum Further details on the experiments are described Appendix |
likelihood estimation
Figs.pa-d show the results of optimizing CVaR of synthetic benchmark functions with low input dimensions (the dimension of m and of W n 1): Branin-Hoo and Goldstein-Priet and
'The code is available at /ttttt::////tt //gg::://ttttut www Nonm/pphong/Bayes0pst..
8

---

0.5
0.0
Regnot
-1-
brg10
-1
-1.0-
-3-
-3
1,5
Ineration
Dberation
Deeration
Ineration
(c) Hartmann-
(d) Hartmann 6D m =
(a) Branin-Hoo
(b) Goldstein-Price
m m== 5
0.50
-100
1,00
CV-UCB
0.25
0.75
lug 10Rgree
PKG
-1.5-
CV-TS
0.50
-0.25
3=
-20-
0.25
0.00
-0.75
Itenoon
Disration
Iterstion
(f) Portfolio
Robot pushing
(e) Yacht hydrodynamics
optimization
experiment
Plots of the regret against the BO iteration in (a-d) experiments that optimize CVaR of synthetic benchmark functions, (e-g) simulated real-world optimization problems.
Figure 2:
with moderate input dimensions (m = 5, n 1; and m = 1, n = 5): Hartmann-6D. The risk level a is set to 0.1. We observe that CV-UCB achieves comparable performance to the baseline pKG in the Branin-Hoo experiment, while it outperforms 5KG in the Goldstein-Price and Hartmann-6D (m = 5) experiments. It is because the evaluation of pKG is approximated with samples of and the nested optimization procedure involved in pKG is simplified. CV-TS & = does not perform well other algorithms do. It is because with few observations, CV-TS & 1 tends towards randomly exploring X so the maximizer is not accurately located. Furthermore, as the GP hyperparameters are assumed to be unknown in our experiments, they can be incorrectly estimated with few observations, which affects the performance of CV-TS k = 1. When we increase the size of the batch query to 3 in CV-TS k 3. the number of observations increases. In turn, the estimation of trade-off are improved. Thus, CV-TS k = 3
the GP hyperparameters and the exploration-exploiaae achieves superior performance. It suggests that CV-TS with large batch query should be preferred when multiple observations can be obtained, e.g., by running multiple simulations in parallel. In contrast, CV-UCB should be preferred if only one observation obtained at each BO iteration.
Figs. 2 show the results of optimizing CVaR in an optimization problem using the yatch hydrody- namics dataset (5), portfolio optimization problem 4 and simulated robot pushing experiment 23 In the experiment with the yacht hydrodynamics dataset, we would like to minimize the resid- uary resistance per unit weight of displacement of a yacht by searching for the optimal hull geometry coefficients of the yacht in the face of the uncertainty in the Froude number (the Froude number depends on the real-world environment and we assume that it can be simulated with computers during the optimization). The ground truth function is constructed using the yacht hydrodynamics data set [5) The dimension of the input variables x and W are m 5 and n 1 (the Froude number), respectively. The risk level of CVaR is set to a = 0.3. While CV-TS k = 3 outperforms the other algorithms significantly thanks to its batch queries, CV-UCB converges to a lower regret than pKG does. The portfolio optimization problem is taken from the work of [4] where the evolution of portfolio over 4 years is simulated and optimized using open-source market data. The optimization variables (i.e., x) include the risk, the trade aversion, and the holding cost multiplier, while the environmental random variables (i.e., W) include the bid-ask spread and the borrow cost 4.. The risk level of CVaR in this problem is set to 0.2. We observe that CV-UCB and CV-TS & = 3 achieve the best performance by converging to lower regret values than the other algorithms. The simulated robot pushing experiment is taken from [ whose task is to minmmize the distance of a pushed object to a fixed goal location by controlling the robot location and the pushing duration (i.c.. x). We adopt the setting of [1] to introduce random perturbations to the robot location (i.c.,

---

W). The risk level of CVaR is set to a = 0.1. While all algorithms converge to roughly the same value of the regret in this experiment, we observe that CV-TS k shows its advantage in acquiring more observations by converging faster than the others. Besides, CV-UCB also converges faster than pKG this experiment.
Conclusion
We propose two BO algorithms to optimize CVaR of black-box function with theoretical perfor- mance guarantee: CV-UCB and CV-TS by taking advantage of connection between CVaR and VaR and establishing link between the tail expectation of (non-Gaussian and unbounded support) CVaR and that of the of CV-UCB and CV-TS with batch queries are shown in optimizing CVaR of synthetic benchmark functions and simulated real-world optimization problems. These results recommend the use of CV-UCB to optimize CVaR of black-box function when only an observation is obtained each BO iteration and the use of CV-TS with large batch queries when multiple observations can be obtained each BO iteration.
function evaluation. The competitive empirical performance
Acknowledgments and Disclosure of Funding
This research is supported by SSTAR under its RIE2020 Advanced Manufacturing and Engineering (AME) Programmatic Funds (Award A20H6b0151).
References
[1] I. Bogunovicc, J. Scarlett, S. Jegelka, and V. Cevher. Adversarially robust optimization with Gaussian processes. Proc. NeurlPS, pages 5760-5770, 2018
[2] E. Brochu, T. Brochu, and N. de Freitas. A Bayesian interactive optimization approach to procedural animation design. In Proc. ACM SICGRAAPH//Enmgggggaahaa Symposium Computer Animation, pages 103-112, 2010.
[3] B. Burger, P. M. Maffettone, V. V. Gusev, M. Aitchison, Y. Bai, X. Wang. X. Li, B. M. Alston,
B. Li, R. Clowes, et al. A mobile robotic chemist. Nature, 583(7815) 2020.
[4] S. Cakmak, R. Astudillo, P. I. Frazier, and E. Zhou, Bayesian optimization of risk measures. In
Proc. NeurlPS, 2020.
[5] D. Dua and C. Graff. UCI machine learning repository, 2017.
[6] F. Häse, L. M. Roch, C. Kreisbeck, and A. Aspuru-Guzik. Phoenics: Bayesian optimizer for chemistry. ACS central science, 1(9):1134-116) 134-1145, 2018.
[7] J. M. HernándezzLobato, M. W. Hoffmann, and Z. Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Proc. NIPS, pages 918 926, 2014.
[8] J. M. Hernández-Lobato, J. Requeima, E. O. Pyzer-Knapp. and A. Aspuru-Guzik, Parallel and distributed Thompson sampling for large-scale accelerated exploration of chemical space. In Proc. ICML, pages 1470-1479, 2017.
[9] S. Iwazaki, Y. Inatsu, and I. Takeuchi. Bayesian quadrature optimization for probability threshold robustness measure. arXiv preprint arXiv:2006. 1986, 2020.
[10] S. Iwazaki, Y. Inatsu, and I. Takeuchi. Mean-variance analysis in Bayesian optimization under uncertainty. arXiv preprint arXiv:2009.088 20060006690006,...... 2020.
[11] K. Kandasamy, A. Krishnamurthy, J. Schneider, and B. Póczos. Parallelised Bayesian optimisa- tion via Thompson sampling. In Proc. AISTATS, pages 133- 2018.
[12] Kirschner, Bogunovic, S. Jegelka, and A. Krause. Distributionally robust Bayesian optimization. In Proc. AISTATS, 2020.
10

---

[13] Q. P. Nguyen, Z. Dai. B. K. H. Low, and P. Jaillet. Value-at-risk optimization with Gaussian processes. In Proc. ICML, pages 8072, 2021.
[14] T. Nguyen, Gupta, H. Ha, S. Rana, and S. Venkatesh. Distributionally robust Bayesian quadrature optimization. In Proc. AISTATS, 2020.
[15] V. Perrone, H. Shen, A. Zolic, I. Shcherbatyi, A. Ahmed, T. Bansal, M. Donini, F. Winkelmolen,
R. Jenatton, B. Faddoul, et al. Amazon SageMaker automatic model tuning: Scalable black-box optimization. arXiv preprint (eXix:2012.084400 2020.
[16] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In Proc. NIPS, pages 1177-1184, 2008.
[17] C. E. Rasmussen and C. K. I. Williams. Gaussian processes for machine learning. MIT Press, 2006.
[18] D. Russo and B. Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 1214):12 2014.
[19] S. Sarykalin, G. Serraino, and S. Uryasev. Value-at-risk conditional value-at-rie at-ris in risk management and optimization. In State-of-the-ar decision-making tools in the information- inlensive age, pages 270-294, Informs, 2008.
[20] B. Shahriari, K. Swersky, Z. Wang, R. Adams, and N. de Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 108(1):44--175, 2015.
[21] N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. Proc. ICML., pages 1015-1022, 2010.
[22] L. Torossian, V. Picheny, and Durrande. Bayesian quantile and expectile optimisation. arXiv preprint arXiv:2001.0488 2020.
[23] Z. Wang and S. Jegelka. Max-value entropy search for efficient Bayesian optimization. In Proc. ICML, pages 3627-3635, 2017.


Reviews:
[{"review_id": "wJxGzARpPX_", "reviewer": "Reviewer_3Pjv", "summary": "This paper proposes to methods to maximize the conditional value-at-risk (CVaR) of a black-box function: the CV-UCB (Upper confidence bound) and the CV-TS (Thompson sampling)\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- This paper is very relevant to reference [12], in which the Bayesian optimization algorithms for VaR has been considered. It is unclear to me why the CVaR objective may be *significantly* different or more difficult than the VaR objective. Both VaR and CVaR are risk measures, and from the theory side, one can use any other risk measures as an objective (spectral risk measure, distortion risk measure, etc.). The critical step in the UCB algorithm is to construct the confidence bound in equation (6), however, this bound can be easily generalizable as well by plugging in the corresponding formula of other risk measures. The regret bound also follows with minimal modification from Srinivas et al. (2010), and differs minimally from the VaR approach as in Lemma 3 of [12].\n\n- The batch extension for CV-TS is straightforward for Thompson sampling which naturally handles parallel evaluations. This idea was also used previously in [12]\n\n- The experimental results are limited and not convincing. No real-world application is considered, and the simulated robust pushing experiment does not look very promising. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "rd0PhZUCuac", "reviewer": "Reviewer_ySFq", "summary": "This paper proposes Bayesian Optimization (BO) approaches optimizing the conditional value-at-risk (CVaR) of the objective function distribution. Assuming the access to the objective function f(x, w) with full control of the environmental parameter w in the optimization time and assuming the prior distribution p(w) of the environmental parameter, the authors develop two algorithmic variants to optimize CVaR of  a given risk level. \n\nThe main contribution is the theoretical guarantee of the proposed variants. For the first variant, CV-UCB, the cumulative regret bound has been proved. For the second variant, CV-TS, the upper bound for the Bayesian cumulative regret has been proved. \n\nThe proposed approach has been tested on 3 synthetic benchmark problems and more realistic problems including portfolio optimization and simulated robot pushing experiment. The proposed approaches have been compared to an existing approach from [4], which can be applied to CVaR but not theoretical guarantee has been developed for. The results show competitive or superior performance.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is very well written. This research topic is an important direction. The theoretical results are strong. \n\nThe only weakness of the paper is in experimental evaluation. \n1. The tested problems are rather low dimensional problems, both in x and w. Especially for w, if I am not mistaken, the test problems are all of dimension no more than 2. I think this is a limitation. I recommend to add results on higher dimensional problems or to mention this limitation.\n2. Though the authors list the computational cost  as one of the shortcomings of the approach in [4], I couldn't find any comment on the computational time in this experiments. It is advised to mention the computational time for each approach on each experiments.\n3. It is interested to see how well the proposed approach works compared to other types of BO methods, such as the standard BO that simply optimize the expected value and the BO solving minimax optimization problems like [1], though they are not optimizing CVaR. It is often the case that minimizing the expectation contributes to minimizing the worst case, though not optimal. I strongly recommend to include the results of these baselines to enhance the empirical evaluation and revealing a possible limitation. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitation is not quite described. Please refer to the main review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ZyYM9XQHFEQ", "reviewer": "Reviewer_HzFE", "summary": "This paper considers a robust/risk-averse Bayesian optimization problem. In particular, the authors focus on maximizing conditional value at risk (CVaR), when the objective is unknown. \nThey propose two algorithms based on UCB and Thompson sampling strategies. Both algorithms are tested on synthetic datasets/tasks. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is clearly written and easy to understand. It contributes novel algorithms and tools (mostly, when it comes to the introduced TS strategy) for robust Bayesian optimization (BO). It builds upon previous robust BO works in which the goal is to optimize the unknown function subject to uncontrollable (at test time) covariate. In general, this problem is interesting and is of significant interest in practical applications. Different from the previous works, that study worst-case robust optimization, DRBO, mixed strategies, and VaR objectives, this work considers the CVaR objective.   \n\nAs a related work, I’d expect more comments on the relation between CVaR formulation and DRO problem (with particular ambiguity sets) and the fact that DRO models have an equivalent risk-averse optimization problem (see, e.g., Rahimian and Mehrotra, DRO review, Section 3).\nI’m wondering to what extent can we then utilize the existing DRBO algorithms? And, in such a case, wouldn’t they at least be proper baselines to compare against? \n\n162:166: I think that this paragraph needs to be more precise. Before this paragraph on time complexity, you haven’t specified the set X (later on, X is considered to be finite). N_train and gradient-based optimization of the acquisition function is not explained. If X is not finite, then we are talking non-convex continuous optimization (this is fine, since non-convex acquisition functions are standard in BO, and for the sake of theory we assume that we can optimize them). The sentence, “the number of gradient descent steps to find maximizer” sounds like you’re solving a concave problem. \n\nAt first selecting alpha_t in the algorithm given that alpha is fixed was strange to me, e.g., why learn at different levels of risk alpha if the learner knows the true parameter value. By following your regret derivation in the appendix, I could see why this is necessary for the analysis to work. Do you think that there is a way to directly select w_t as a function of alpha and x_t and not alpha_t? E.g., in the previous robust BO works, such as the one cited below or, e.g., [1], the second variable is selected to maximize the uncertainty given the previously selected x_t.    \n\nThe concept of lacing values is very important and crucial in the analysis. It’d be good perhaps to explain/summarize the proof of existence (perhaps, in the appendix) from [12] to improve the clarity of the paper.\n\nCan you comment on your analysis when X is not finite? For example, this assumption is used in the proof of Theorem 2. Also, having X being finite and having the main results expressed in terms of gamma_T, with the additional comment of gamma_T being sublinear for most of the kernels is a bit informal.  \n\nFigure 1 nicely explains the difference between VaR and CVaR. I like the joint pseudocode presentation of TS and UCB with the common selection of w_t. I find the performed experiments to be very standard (as in other BO and robust BO works) and not exciting.    \n\nSome minor comments: \n\n-- Abstract: “an interesting connection between CVaR and VaR”; Aren’t we only talking about one of the definitions of CVaR in terms of VaR? Can you clarify the “interesting connection”?\n\n-- It’d be interesting to also learn about the distribution of W simultaneously as was also considered in some of the robust BO papers. \n\n-- Another relevant robust BO work is: “Mixed Strategies for Robust Optimization of Unknown Objectives” from Sessa et al. where instead of selecting a single robust design as in your work, the authors seek to discover a robust distribution. \n\n-- 108: The considered noise model is homoscedastic, so perhaps avoid writing epsilon(x,w).\n\n-- Algorithm 1: alpha is an input. \n\n-- An interesting research question, is can you get similar regret guarantees and adapt in case the true alpha is unknown? \n\n-- Mathematical definition of the maximum information gain is missing.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "LbuewDX2dv1", "reviewer": "Reviewer_sLCu", "summary": "This paper considers Bayesian optimization (BO) of objective functions of the form $c_f(x;\\alpha) = \\mathrm{CVaR}_\\alpha(f(x, W))$, where $f$ is modeled as a Gaussian process (GP),, and $\\mathrm{CVaR}_\\alpha$ denotes the $\\alpha$-level conditional value-at-risk, which is computed with respect to the randomness over $W$. This work focuses on the simulation optimization setting, where it is possible to evaluate $f(x,w)$ for each $(x,w)\\in\\mathbb{X}\\times\\mathbb{W}$, and develops two acquisition functions to select the pairs $(x,w)$ at which to evaluate $f$, CV-UCB and CV-TS, which extend the classical UCB and Thompson sampling acquisition functions, respectively. These algorithms select the $x$ component of the pair and are complemented with a common strategy to select $w$. Given $x_t$, the $x$ component of the pair to be evaluated at time $t$, this strategy first chooses $\\alpha_t$ that maximizes the difference of the VaR of an upper confidence bound on $f(x_t, W)$, $u_t(x, W)$, and the VaR of a lower confidence bound on $f(x_t, W)$, $l_t(x, W)$. Finally, given $x_t$ and $\\alpha_t$, this strategy chooses $w_t$ so that   $[\\mathrm{VaR}_\\alpha (l_t(x, W)),  \\mathrm{VaR}_\\alpha (u_t(x, W))] \\subset [l_t(x_t, w_t), u_t(x_t, w_t)]$ (for $\\alpha= \\alpha_t$). A $w_t$ satisfying this condition is called a lacing value. The two resulting algorithms are shown to enjoy sublinear cumulative regrets when $\\mathbb{X}$ and $\\mathbb{W}$ are both finite. Finally, the empirical performance of these algorithms is evaluated in three synthetic experiments and two real-world experiments, showing favorable results.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The proposed algorithms are, to the best of my knowledge, novel, and are the first ones for GP-based optimization of CVaR that come with theoretical guarantees. However, these algorithms (including their theoretical analysis) heavily rely on the work of Nguyen et al. 2021. The algorithmic contributions of this paper are, therefore, somewhat limited. In this regard, the most novel aspect of this work is the CV-TS algorithm, which allows for batch evaluations. In addition, as acknowledged by the authors, the problem setup has been previously considered in the literature (see, e.g., Cakmak et al. 2020), and the test problems are the same (translated from VaR to CVaR) as those in Nguyen et al. 2021. As a consequence, the overall novelty of this work is limited.\n\nQuality: The proposed algorithms are technically sound. The proofs on the regret bounds seem to be correct (although did not check in detail some of the calculations).  With only three synthetic test problems and two realistic test problems, the empirical evaluation is somewhat limited. Moreover, claims about the computational efficiency of the proposed algorithms have not been properly backed up. For this, I would suggest the authors to include a table of the average running times of each algorithm in each problem.\n\nClarity: This paper is fairly well written and easy to follow. One suggestion is that the paper would benefit from a picture illustrating the behavior of the proposed algorithms.\n\nSignificance: Risk-averse Bayesian optimization is a problem of high practical relevance. Moreover, the only existing algorithms (for the CVaR setting), $\\rho$KG and its approximate variant, are fairly computationally expensive. Therefore, cheaper algorithms with good empirical performance are relevant and prone to be adopted by practitioners. The algorithms proposed in this paper seem to poses these characteristics. However, a more thorough empirical evaluation is required.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have implicitly discussed the limitations of their work. However, I it would be beneficial to summarize them and discuss them more explicitly in the conclusion. The societal impact of this work has not been discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses Bayesian optimization to search a maximizer of the CVaR of the black-box objective function. Two variants inspired by UCB and Thompson sampling are presented. For CV-UCB, the cumulative regret bound has been proved and for CV-TS, the upper bound for the Bayesian cumulative regret has been proved. The paper is well written and the topic is interesting. A few reviewers pointed out the weakness of empirical evaluations. The authors promised to include an additional experiment whose preliminary results are reported in the rebuttal.The rebuttal was not fully satisfactory but the efforts in providing preliminary results were appreciated. During the committee discussion period, two of reviewers raised the score. Some concerns in the limited novelty over previous work still remains. However, the paper presents a solid theoretical guarantee, which might not be obviously derived from known results. 


Decision: Accept (Poster)