Bayesian Optimization with Cost-varying Variable Subsets
Authors: Sebastian Shenghong Tay
Chuan-Sheng Foo
Daisuke Urano
Richalynn Leong
Bryan Kian Hsiang Low
Venue: NeurIPS 2023 poster (2023)
Keywords: Bayesian optimization
Gaussian processes
TL;DR: Bayesian optimization where the learner chooses a subset of query variables and specifies their values while the rest are randomly sampled, and each subset comes with a cost.

Abstract: We introduce the problem of Bayesian optimization with cost-varying variable subsets (BOCVS) where in each iteration, the learner chooses a subset of query variables and specifies their values while the rest are randomly sampled. Each chosen subset has an associated cost. This presents the learner with the novel challenge of balancing between choosing more informative subsets for more directed learning versus leaving some variables to be randomly sampled to reduce incurred costs. This paper presents a novel Gaussian process upper confidence bound-based algorithm for solving the BOCVS problem that is provably no-regret. We analyze how the availability of cheaper control sets helps in exploration and reduces overall regret. We empirically show that our proposed algorithm can find significantly better solutions than comparable baselines with the same budget.

Bayesian Optimization with Cost-varying Variable Subsets
Sebastian Shenghong Tay'? Chuan Sheng Foo23, Daisuke Urano", Richalynn Chiu Xian Leong', Bryan Kian Hsiang Low! DDppartmen of Computer Science, National University of Singapore
Institute for Infocomm Research (I2R), A A*STAR, Singapore *Centre for Frontier AI Research (CFAR), A*STAR, Singapore
'Temasek Life Sciences Laboratory, Singapore sebastian, tayēu. mus. edu, foo_ srto_chhan_sshee sheng@iir aaaggiirr.-ssarar a-star edu, sg,
daisuke@t11.org orr.eeet.....rr....... sg, richalynn@tll www.:etl....r......... sg, loukh@comp nus edu.sg sg
Abstract
We introduce the problem of Bayesian optimization with cost-varying variable subsets (BOCVS) where each iteration, the learner chooses a subset of query variables and specifies their values while the rest are randomly sampled. Each chosen subset has an associated cost. This presents the learner with the novel chal- lenge of balancing between choosing more informative subsets for more directed learning versus leaving some variables to be randomly sampled to reduce incurred costs. This paper presents novel Gaussian process upper confidence bound-based algorithm for solving the BOCVS problem that provably no-regret. We analyze how the availability of cheaper control sets helps in exploration and reduces overall regret. We empirically show that our proposed algorithm can find significantly better solutions than comparable baselines with the same budget.
Introduction
Bayesian optimization (BO) is powerful framework for the cample-efficiee optimization of costly-to evaluate black-box objective functions [1] and has been successfully applied to many experimental design problems of significance such as hyperparameter optimization (6] 39], chemical synthesis (30), and particle accelerator control [29]. among others. Conventional BO assumes that the learner has full control over all query variables (i.e., all variables in the input the objective function). However, in many real-world optimization problems, some of the query variables may be subject to randomness affecting their values. some cases, the randomness affecting specific variable can be eliminated (by allowing the learner to select its value), but at a cost. We illustrate with few concrete scenarios: In precision agriculture, consider farm aiming to find the optimal conditions for largest crop yield where the query variables are set of soil nutrient concentrations (c.g., Ca, B, NH2, K) and pH. The farm may rely on the naturally-occurinn quantities will be randomly sampled. Alternatively. they may control some subset of these quantities (via manufactured soil and fertilizers) at a higher cost. In advanced manufacturing where random variation occurs in every operation 34 certain specifications of a product may be left unspecified revenue
quantities of these nutrients the available soil, but these
by the manufacturer and randomly determined, or specified but at a higher cost. maximization or crowdsourcing where information is gathered from large number of individuals via ad platforms or crowdsourcing platforms such as Amazon Mechanical Turk, suppose that the query variables describe the demographics of the individual, such country of origin income level. The learner may allow the platform to randomly assign the task to any individuals, or the learner may demand a specific subgroup of individuals at higher cost. In all these practical scenarios, the goal is to find the maximizer with as little incurred cost as possible. At each query iteration, the learner is
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

faced with the non-trivial problem of deciding which variables to specify (for more directed learning) vs. which variables to allow to be randomly sampled (to reduce incurred costs), in addition to the usual BO problem of deciding the specified variables' values.
To the best of our knowledge, there are no existing works that tackle this problem precisely. The work of Hayashi et al. [13] introduced the problem of BO with partially specified queries (BOPSQ) in which the subset of deterministically selected variables (control set) and randomly sampled variables (random set) can also be chosen by the learner, but it does not consider the costs incurred by such choices. This is non-trivial limitation as the presence of costs can significantly alter the learner's s decisions. Under such formulation, if control set is strict subset of another, then the former will never be chosen as there is no benefit to having variable values be randomly sampled instead of chosen by the learner. Consequently, if there exists control set that includes all the variables in a query, then all other control sets will not be used and the problem reduces to conventional BO. In practice, however, the availability of other control sets confers an advantage if these other control sets are cheaper. Having access to cheaper but more random control sets allows the learner to explore the query space cheaply and then use costlier but more deterministic control sets to exploit high-value regions. BOPSQ in its current formulation excludes the analysis of such strategies and is akin to multi-fidelity BO [I5] but without modeling the costs of the different information sources: In this case, the learner would simply choose the highest-fideligy information source all the time, thus making the problem setting trivial.
This paper introduces the problem of BO with cost-varying variable subsets (BOCVS) that explicitly models the cost of each control set and is more useful in practical scenarios. Our work generalizes BOPSQ and argues that BOCVS problems are much richer when analyzed from a similar perspective as multi-fidelity BO, and the various control sets are treated as information sources with different levels of usefulness and costs. By using cheap control sets for exploration and expensive control sets for exploitation, we show that with an appropriately designed algorithm, learner can find significantly better solutions with a lower cost expenditure. To achieve this, we leverage the Gaussian process upper confidence bound (GP-UCB) acquisition function 7 32 to design a novel no-regret algorithm. i... its incurred simple regret tends to 0 as the number of iterations tends to infinity, and the algorithm's 's best chosen query converges to the optimal solution. We additionally analyze the impact of the availability of cheaper control sets on the regret incurred by the most expensive control set. We observe that our algorithm generally outperforms the non-cost-aware baselines, while simple extensions based on Thompson sampling, maximizing UCB or expected improvement-bant acquisition scores per unit cost [31 Sec. 3.2] either fail to converge or fail to utilize cheap control sets effectively. Concretely, the contributions of our work in this paper include the following:
We introduce the BOCVS problem (Sec. 4 and solve it by designing novel UCB-based algorithm (Sec. with a theoretical analysis of its properties, including the conditions under which is provably no-regret and the impact of the availability of cheaper control sets the regret incurred by the most expensive control set, and discuss the practical considerations (Sec. (.2c.
We empirically evaluate the performance of our proposed algorithm against the baselines under several experimental settings with synthetic and real-world datasets (Sec. 5), including a plant growth dataset and an airfoil self-noise dataset corresponding, respectively, to the precision agriculture and advanced manufacturing use cases motivated earlier in this section.
2 Related Work
The work of Hayashi et al. 13 introduced BO with partially specified queries (BOPSQ) and tackled the problem with Thompson sampling. However, it fails to consider the relative costs of control sets, which hinders the learner's ability to take advantage of all control sets even in the presence of more deterministic control sets. The work of Oliveira et al. (25) proposed BO with uncertain inputs in which the executed query sampled from a probability distribution depending on the proposed query. Though related, its problem setting is motivated more by uncertainty in the input query even post-observation and does not involve variable subset selection. These two works are part of a line of research investigating BO in situations where the learner may not have full control over all variables in a query, which includes BO for expected values [38], risk-averse BO 21 22), and distributionally robust BO
17 24 37 These works also do not consider variable subset selection. Our treatment of the BOCVS problem is inspired by multi-fidelity BO in which the learner has access
to cheap, low-fidelity surrogates of the true objective function [5 27 35 36). In such works (and in
2

---

ours), modeling costs is crucial as the learner would simply choose the highest-fidelin information source (in ours, the maximally deterministic control set) otherwise. While the general idea of paying less for potentially less informative queries is similar, our problem setting is fundamentally different: The lack of informativeness comes from the uncertainty of the executed query as opposed to bias in the observed function values.
The BOCVS setting may be viewed as special case of causal BO as formulated by Aglietti et al. M and continued in several works [2] 4 Specifically, our setting is a case in which there are no nnn non-manpuulative variables and the causal DAG is such that all imput variables have no parents and are parents of the output variable. Nevertheless, we believe our focus on this special case has value as it allows us to derive useful theoretical results such as algorithm regret bounds that, to the best of our knowledge, do not exist for the completely general causal BO setting at the time of writing. The work of Sussex et 33 includes a regret bound, but also a special case of [1. and has little overlap with our work as it does not consider costs of control sets or explicit probability distributions over input variables. We believe that our work is sufficiently general to be useful for practical scenarios (where the full causal BO apparatus may be unnecessary), and is also stepping stone towards theory for the general case.
3 BO and Gaussian Processes
We will first give a brief review of conventional BO [T] Given query set X' and an objective function f X + IR, a learner wishes to find the maximizing query x == argmaxxex* f(x). However, f is black-box (i.e., not available in closed form) and can only be learned by submitting a query x, E X' in each iteration t for function evaluation and receiving a noisy observation Yt fx,) + & where each & is i..d. sub-Gaussian noise with zero mean. Each function evaluation is assumed to be expensive in some way, such as in terms of money or time spent. So, the learner must be sample-efficient and find x" in as few iterations possible. BO achieves sample efficiency by leveraging a Bayesian model to represent a probabilistic belief of the function values at unobserved regions of X' in a principled manner. While any Bayesian model may be used for BO, Gaussian processes (GPs) 42 are a common choice as they enable exact posterior inference: The GP posterior belief of f at any query X after iterations a Gaussian with posterior mean and variance given by
(x(x) = (x)xx (K₁ + yye
(x(x) (K, + AT) -X)-
(1)
where y: = (0:) E TR', k is positive semidefinite kernel (covariance function), k, = (k(x, Xz) x,)) R R K, = (x(x,,x,))),.=== )), E Rtxt, and À is an algorithm parameter; if the noise a Gaussian with variance o², then the true posterior is recovered with X = o². The kernel k is an important modeling choice as the GP posterior mean will reside in the reproducing kernel Hilbert space (RKHS) associated with k. For simplicity, we assume w.l.o.g. that k(x, x') S for any pair of queries x, x' E X. Kernel l affects the maximum information gain (MIG) defined as
x5
(x)
max (x, 1
0.5 I+ KT
The MIG characterizes the statistical complexity of problem and plays an integral role in the theoretical analysis. For the commonly used squared exponential kernel, TT()) D(logT))4t)
while for the Matérn kernel with v > 1, (2') = O) (log T)) [32. Importantly,
yr (2) is increasing in the volume of X' 32 Theorem 8].
4 BO with Cost-varying Variable Subsets (BOCVS)
The BOCVS problem consists of a compact query set X' C Rd and an objective function f X - R in the RKHS of k with the RKHS norm upper bounded by B. For simplicity, assume w.l.ogg. that
X = [0. 1]d Let [d] == {1. 2,.,, .....), d}. The learner is given collection I C 2/4 of control sets indexed by 1, 2, ......... m = []. Each control set E [m], denoted by I, S [d], indicates the variables in a query with values that can be chosen by the learner. The complement I, := [d] \ Z of I4 is the corresponding random set indicating the variables in query with values that will be randomly sampled from some distribution. A query x E X can be represented by a combination of partial queries [x', x "1 comprising the control partial query x² == (ZE)LEI, (i.c., x' collects the variables
3

---

I= (1.)
Iteratinn tt
Iteration (
i ==1
2++1 2
x" ="=(an ((
x (#(41,1,76122) - ic4 (Xx+1.3)
x (X4,2,
Ft,1
1t+1,1
11+1,
Figure 1: Two iterations in BOCVS problem setting. The grey boxes are isometric views of a query set N' C R The blue regions depict the probability densities of random vectors [x* X and [xfi,, X -.111. In iteration t. the learner chooses the control set in
and specifies the value (of the first variable xt,1) in control partial query x", while the last two variables X1,,,Xx, in random partial query X will be randomly sampled. In iteration t + 1, the learner chooses the control set 4++1 = 2 and specifies the values (of the first two variables 1 22,2) in control partial query x while the last variable X1,3 in random partial query X - will be randomly sampled.
indexed by I,) and the random partial query x (Ix)eEI, where ze denotes the é-th variable in the query vector x. Note that [x", x] is not simple vector concatenation the variables may need to be reordered according to their indices. Furthermore, let X == {x* x E X
In iteration I, the learner chooses control set ie E I and specifies the values in control partial query x The random partial query x= will then be randomly sampled from the environment. For example, if d values in x* (i.e.. the 1st and 3rd variables) but not those in x= (i.e., the 2nd and 4th variables). (zr,e))e(d)- Each observed variable Ft,e for -
and I, (1. 3). then I, {2, 4] and the learner will be able to choose the
The full query in iteration t then x; [x", x x=]
É E I, is realization of a random variable Xt, ~ Pe. The observed x is then realization of the random vector X - == (X,,))eZ,, ~ IP- where P- the product measure X Pe. In other words, each variable in random partial query is independently sampled from probability distribution that governs that variable. All distributions are assumed to be known. The learner then observes V/+ fx+) & where each is i.i.d. r-sub-Gaussiag noise with illustrates two iterations in a BOCVS problem setting.
mean. Fig. 1
The learner wishes find the optimal control set i* and specified values in control partial query x" that maximize the expected value of f([x', X-1)) where the expectation is w.r.t. X- ~ Ppt:
argmax [[J([x', x DD]
(i.x ((mx))
The learner has an initial budget C' + and every control set I, has an associated cost e, > 0 for all i [m]] Let the control set indices be defined such that C₁ 02
Cm
In every iteration t, the learner pays Cr2- The learning procedure ends after iterations when C - -Et= Cs < Cir+i i.e., the learner has not enough budget left to pay for the chosen control set. T will now be a random variable depending the algorithm and the random outcomes of the learning procedure. The cost-varying cumulative regret is defined as
:T=-TT ci (E[]((x', X DD [[[((x' , "I)))
The regret incurred by choosing sub-optimal control set and specifying sub-optimal values in the control partial query is weighted by the cost of that control set. This naturally incorporates the notion that the penalty for sub-optimal plays is lower if the play was cheap, while also penalizing using the entire budget on sub-optimal plays, regardless of whether those plays are cheap or expensive. Intuitively, to minimize the cost-varying regret, a learner would attempt to use the cheap control sets (i.e., low C, low E f([x' X XDD) to explore the query space, and use the expensive control sets (i.e., high c, high E. [[x(xx, X DD to exploit control partial queries with high expected function values When all e = 1, we recover the BOPSQ problem 13], and is simply the number of iterations
While our problem definition does not require that G C3 + max [[f((x'x'*) < max [[x( x "D]. one might reasonably expect this to be the case in real-world problems, i.c.. "better" control sets cost more specify. This also implies that I, C Ij ci S Cj.

---

Algorithm UCB-CVS
Input: GP with kernel k budget C, control sets Z, costs (c: ( e-schedule (er)i=1
2: for iteration f = to co do
3: 9t =- (ax) Blue-1((** [xx X x-1]
4: S = {i E [m] maxxiex E uu-1 ((x², X x=]] + et 2 gc}
5: S2 = {i E S G = minjes, 9j}
6: (in,"*) = argmax (xx))
f[1411( ( X [1]]
7: break if C - r== - Gr < ca.
8: Observe x drawn from P
9: Observe y/1 = f(xi) + &
10: Dj = -(x+; Vr) (=))
11: end for
12:
return D.
in the learning trajectory. In fact, BOPSQ reduces a simpler problem if there exists full query control set that allows the learner to choose the values of all d variables. If [d] E II then Z-- = [d]
maXxex (x) since expectations of a function are never greater than the maximum value of the function. In other words, the full query control set is guaranteed to be the
and E [[x([x", X X]]
optimal control set and the BOPSQ problem reduces to one of conventional BO. In general, under
BOPSQ, any control set that is strict subset of another will never be chosen.
4.1 UCB-CVS
Alg. I describes our UCB-CVS algorithm for solving the BOCVS problem. In iteration f, uses the GP posterior belief of f' to construct upper confidence bound (UCB) u4-1 of f:
U4-1 (x) (x) (,0,-1(x)
where the sequence (12 is an algorithm parameter that controls the tradeoff between exploration and exploitation. UCB-based algorithm design is a classic strategy in the stochastic bandits [19 Ch. 7] and BO literature 7 32 and makes use of the "optimism in the face of uncertainty" (OFU) principle [18] Queries with large posterior standard deviation (i.e., high uncertainty) are given high acquisition scores as the function values at those queries may be potentially high. UCB-CVS adapts this strategy by taking the expectation of the UCB as part of the acquisition process. Due to the monotonicity of expectation, if u is an upper bound of f (i.e., 14-1(x) 2 f(x) for any x E X), then EE [ X X-]] is also an upper bound of EE [[x((x,, X x-1] for any E [m], x E X
UCB-CVS also takes as input an e-schedule (et) where 2 0 for all l. To choose the control set in iteration first computes 9: which is the expected UCB of the best control set and specified values in the control partial query (Step It then collects every control set i that fulfills the condition ma E [i ([x', X "])] + e, 2 Sr into a set S (Step 4). It further reduces this set S to S₂ by retaining only the control sets with the lowest cost 5) Finally, it chooses the control set from S2 with the largest expected UCB value (Step 6.. Each e, thus serves as a relaxation that enables exploration with cheaper control sets. Choosing many c, to be large results in many iterations of choosing cheaper control sets; conversely, choosing e = 0 for all t ignores all costs.
Our first result upper bounds the cost-varying cumulative regret incurred by UCB-CVS. Define the feasible set X;
lo bi] for each control set such that af 0, bj if E I,, and a} = sup(a E =0,, 1] (a(a) = 0}. bj = in e [0, 1] Fe(6) = 1} otherwise, where Fe is the CDF of X₂ ~ Pe. & is subset of X' in which any query chosen with control set must reside. Define Tç as the total number of iterations in which control set i chosen.
Theorem 4.1. With probability at least 1 - 6, UCB-CVS (Alg. 7 incurs cost-varying cumulative regret bounded by
Rr so( ((B+
7x)( + -log 8
m +1
Σ
(TTm + log 8
m +1
1) C...
T
by setting Br = B + t (0-1((1)(2)) + 1+ log (m + 1)/5)).
5

---

For any appropriately chosen kernel such that (x() < (VVT) (e.g., commonly used squared exponential kernel, see Sec. 3) and e-schedule such that Σ ct is sublinear in T, the cumulative regret incurred will be sublmear in T: limy--se Rr/TT = 0. Since the mean of a sequence is
no less than the minimum, and all Ci > 0, this further implies the desired no-regret property: 0, i..., the best control set and specified values in control partial query in the algorithm's 's choices eventually converge to the optimal solution. The proof of Theorem 4.1 relies choosing an appropriate sequence of 3, such that
limy--co gin (E [f([x" X
- D]] [[f([x',,X x xD]]
(4-1(x) 2 f(x) for any x E X,
with high probability T Theorem 2]. The cumulative regret is bounded by a sum of expectations of posterior standard deviations, which can then be bounded by a sum of posterior standard deviations plus some additional terms [16] Lemma 3] and in turn bounded in terms of the MIG 77 Lemma 4]. The proofs of all results in this paper are provided in Appendix [A]
Since each "r, (X;) is increasing in the volume of X; Theorem 4.1 states that control sets with smaller feasible sets will incur less regret. If the size of a feasible set is taken to be a reasonable surrogate for the diffuseness of the probability distributions involved, Theorem [4.] then suggests that control sets with corresponding random sets whose probability distributions are less diffuse will Theorem 4.1 also informs us that one sufficient condition on the e-schedule for
incur less regret P the cost-varying regret to be sublinear in T that Σi= Et is sublinear in T. Our next proposition provides an alternative condition (neither is more general than the other):
Proposition 4.2. If there exists a ē > O s.I. for all i * i", Gt S [[[([x" [[[(xx",x~'1)
m [f X X-1] - eeventually (i.e., the inequality holds for all t 2 q for some q 3 1), and (x)) < (VTT), then, with probability at least 1 - 6, lim T//T = 0 for all i + it and UCB-CVS incurs a cost-varying cumulative regret that is sublinear in T by setting
3. = B a /2
+ +1+ log((m + 1)/0).
The above results have shown that with an appropriately chosen c-schedule, UCB-CVS satisfies the no-regret property. However, ignoring all costs by setting = O for all also achieves no-regret. This begs the question: In what way does a good e-schedule improve UCB- CCC? Supposing the most expensive control set is the full query control set, the presence of queries chosen with cheaper control sets should reduce the cost-varying regret incurred by the full query control set by ruling out low function value regions and directing the full queries towards high function value regions. Additionally, it is reasonable to conjecture that the more diffuse each variable's (indexed by E) probability distribution P: is, the more the cheaper control sets would explore the query space and thus, the lower the cost-varying regret incurred by the full query control set. To derive such a result, the plan of attack is to relate the variances (i.e., notion of diffuseness) of the probability distributions to the distances between queries chosen with the cheaper control sets, followed by analyzing the effect of these distances and the number of times cheaper control sets were played on the MIG term of the most expensive control set. Our next result relates the distance between pairs of queries chosen with control set to the variance V[Xe) of every probability distribution Pe for l EE I,:
Lemma 4.3. Suppose that for each control set i, the random variable Y; = -|100 X has a median M, s.1. RY > M.] S M2M, for some hy > O where X X,, p-s With probability at least 1 1-6 6, there will be at least N; non-overlapping pairs of queries and x' chosen
[0, X,,
by UCB-CVS (Alg. 7 with control set i s.I. ||x x11² 2 M, where
N (T. - 1)/4 V (og//))og(1//)
and M, 2 (4/(h; + +1) EiET, EI) V[Xa].
(2)
From 2 the higher the variances of the distributions that govern the variables in the random set, the larger the lower bound M; on the squared distance between at least N, pairs of queries chosen with control set As expected, the number N, of pairs increases with T; (i.e., the total number of iterations in which control set i is chosen). The assumption on Y, is mild: As long as Y, has at least 1 non-zero median, it will hold. The assumption excludes the case in which Pe for all E I, are degenerate with all probability mass on single point. With Lemma 4.3) we now derive an alternative regret bound that depends on the variances of the distributions and the number of plays of cheaper control sets:
'The feasible set of control set is defined in a worst-case manner, which may be too conservative to be a good surrogate for diffuseness, especially for concentrated probability distributions with non-zero density everywhere. Nevertheless. it facilitates the corst-case analysis of the regret bounds.

---

Theorem 4.4. Suppose that the following hold:
Assumption of Lemma 4.3 holds;
x'x is isotropic kernel which only depends on distance between x & x' and can be written as k[[xx - x' x(I);;
There exists an iteration r s.t. for all t S r, ie S m 1, and for all t r, d = m.
Then, with probability at least 1 - 5, UCB-CVS (Alg. bounded by
incurs a cost-varying cumulative regret
Ri S so
((B
(B+ B V (2(())++ log 8
2m
2m (VTrx(X) L log
Cm
8
m
2m 1))
T
(Vin,, (2:) + log
+
c
+ Cm
1=1
L x=
log (V, 2k( M.) - 1: M(MM))² + W
by setting 3, = B a
+1 (0g where N, and Mj are previously defined in Lemma 4.3 and Vi and W are residual terms defined in Appendix
+
Theorem shows that the MIG term pertaining to the most expensive control set m is reduced by f. which increases as N₂ increases, which turn increases as T, increases. This suggests that an e-schedule that increases the number of times cheaper control sets are played can reduce the MIG term. L also increases as k( Mi) decreases. For common kernels such as the squared exponential or Matérn kernel with v (which satisfy the second assumption on isotropic kernel), k M,) decreases as M. increases, from which we may conclude that higher variance probability distributions governing each X₂ lead to a larger L due to (2) and hence a larger decrease on the MIG term. In cases where C. >> for all jf m, carefully chosen e-schedule can thus lead to a large decrease in the regret bound via C. The third assumption is (informally) approximately true in practice due to the design of UCB-CV sub-optimal control sets at the start. After e, has decreased past a certain value, the algorithm will only choose the optimal (and likely most expensive) control set. The proof sketch upper bounds the sum of posterior standard deviations of queries chosen with control set m with the MIG term minus the sum of posterior standard deviations of queries chosen with all other control sets. This latter sum is then lower bounded by a log determinant of the prior covariance matrix which is then decomposed into a sum of log determinants of pairs of queries. The dependence on the distances between the pairs can be made explicit in this form. Neither Theorems 4.1 nor 4.4 is more general than the other.
If decreasing e-schedule is used, the algorithm will choose the cheaper but
4.2 Practical Considerations
UCB-CVS is presented with the e-schedule formulation for generality and ease of theoretical analysis. In practice, however, the e-schedule is hyperparameter that is difficult to interpret and choose. We propose simple explore-then-commii (ETC) variant with which the learner only chooses the number of plays of each cost group (i.e., defined collection of control sets with the same cost that is not the maximum cost). In each iteration, the algorithm will choose the cost group with the lowest cost and non-zero remaining plays, and then choose the control set within that cost group with the largest expected UCB (similar to Step 6 in Alg. []. Once all cost groups have zero remaining plays, the algorithm chooses the control set with the largest expected UCB among all control sets. This algorithm is highly interpretable and is equivalent to UCB-CVS with a specific sublinear c- schedule (that cannot be known priorí). Furthermore, the learner should choose the number of plays adaptively depending on the cost of each cost group. On computational considerations. UCB-CVS may be computationally expensive if the number i of control sets is large (e.g., if every subset of variables is available as a control set and = 2d) as each control set requires maximization of the expected UCB (which can be approximated with Monte Carlo sampling). such cases, the learner has the option to simply ignore any number of control sets to reduce m, as long as i" is not ignored.
7

---

GP SAMPLE
HARTMANN
DNS. COAA
Vodorde CIVO,
nAt cods, sptaeced Eepertar 0e', Sr Exprrcke CKds Latpaced
Typeraive cests, veter teponht OOt,, aatancedd eperstee.cott witrrosb0
C
C
Cudget
0x
Bu5get
PLANT
AIRFOIL
20derope0..22 COS, aeten crub.
Opersieecodt wararon 5002 Exparke cads, vecaace Eazesske COOL VS S52E 200
Drenske cosbs ver arquetd
Eeprovee oob. eatorcend D4 Exersike cosb, 10
Save mum
0200e
0udge
Sadgec
Dudget
Figure 2: Mean and standard error (over 10 RNG seeds) of the simple regret (lower is better) incurred against cost spent (budget) C' by TS-PSQ, UCB-PSQ, ETC-50, ETC-100, and ETC-Ada with varying objective functions, cost sets, and variances of distributions. A diamond indicates the average budget after which an algorithm only chooses the optimal control set.
8

---

5 Experiments and Discussion
This section empirically evaluates the performance of the tested algorithms with objective functions: (a) function samples from GP prior (3-D), (b) the Hartmann synthetic function (3-D), (c) plant growth simulator built from real-world data where the variables are nutrients such as NH3 and pH (5- D), and (d) a simulator built from the airfoil self-noise dataset (5-D) from the UCI Machine Learning Repository [2]. For the first 2 objective functions, the control sets are all possible subsets of the 3 variables except the empty set, which leads 7 control sets. For the plant growth objective function, we pick 7 control sets including the full query control set. For the airfoil self-noise objective function, similar to that of [3]. we pick 7 control sets of 2 variables each that are not subsets of each other. We use 3 different sets of costs for the 7 control sets: cheap (f0.01, 0.01, 0.01, 0.1, 0.1, 0.1, 1)). moderate ((0.1, 0.1, 0.1, 0.2, 0.2, 0.2, 1)), and expensive (f0.6, 0.6, 0.6, 0.8, 0.8, 0.8, 1J). Using these sets of costs, the control sets are ordered such that C2 < Cj + max [[[([x', x-)] S
max E [[([x) [D]] These cost sets have fixed the optimal (i.e., last) control set to have cost of 1. While these cost sets may (at first glance) seem arbitrary, it is the algorithms' relative performance across these cost sets rather than the absolute performance on a single cost set that allows us to understand the conditions under which particular algorithms perform better or worse. Real-world applications (unlike the experiments conducted here) will come with their own cost sets defined by real-world constraints. If the real costs can also be categorized in similar relative way like the above cheap, moderate, and expensive cost sets, then the results are expected to be similar. Every probability distribution Pe is truncated normal distribution with mean 0.5 and the same variance which is one of 0.02, 0.04, and 0.08 (the uniform distribution on [0, 1] has variance 1/12).
We compare the performance of our algorithm against that of the baseline Thompson sampling (TS-PSQ) algorithm developed 13. We test UCB-PSQ (e-schedule with 6, = 0 for all t) along with the ETC variant of UCB-CVS (Sec. 4.2) with 3 sets of hyperparameters: 50 plays per cost group (ETC-50), 100 plays per cost group (ET and a cost-adaptive version with 4/c, plays per cost group where Cj is the cost of the control sets in that cost group (ETC-Ada). We also investigated simple extensions of TS-PSQ. UCB-PSQ, and expected improvement (adapted for BOPSQ) for the BOCVS problem by dividing the acquisition score of control set by its cost in a manner similar to that in [1 Sec. 3.2]. We observed that these naive methods generally do not work well; we defer the results and discussion of these methods to Appendix [ Refer to Appendix for full descriptions of all experimental settings and algorithm hyperparameters. The code for the experiments may be found at httttt::////tiiiii
com/ sebtsh/bocyy
Fig. 2 shows the mean and standard error (over 10 RNG seeds) of the simple regret min <EST(C) [[x((x" X x-] - E {[((xxxxx"11) (lower is better) incurred against cost spent (budget) C by each algorithm with varying objective functions, cost sets, and variances of distributions where T(C) denotes the maximum iteration reached after spending C. The simple regret encodes the value of the best solution an algorithm has chosen within a certain budget and is measure of cost efficiency. We report the salient observations below:
(1) UCB-CVS variants outperform TS-PSQ and UCB-PSQ under cheap/mmoerate costs when the full query control set is available. With the GP sample, Hartmann, and plant growth objective functions, the full query control set is available. TS-PSQ and UCB-PSQ only choose the full query control set in every iteration and are very cost inefficient under cheap and moderate costs, while UCB-CVS variants are able to use the cheaper control sets for exploration, followed by using the full query control set for exploitation, and find much better solutions with the same budget. As expected, their performance advantage reduces as the costs increase and Cm gets closer to for all i + m.
(2) Cost-adaptive UCB-CVS (ETC-Ada) can maintain competitive performance under expensive costs. The non-cost-adaptive variants, ETC-50 and ETC-100, perform worse than TS-PSQ and UCB- PSQ under expensive costs. In contrast, it can be observed that ETC-Ada generally performs well under all costs by tuning the number of plays of suboptimal cost groups according to their costs. We recommend practitioners use adaptive algorithms to achieve good performance under any cost set. In particular, the results suggest that O(c-') threshold is likely to work well across different sets of costs and is a robust choice for practitioners that keeps the number of hyperparameters to a minimum.
(3) TS-PSQ and UCB-PSQ perform relatively well when the control sets are not subsets of each other. With the airfoil self-noise objective function, TS-PSQ and UCB-PSQ perform better as the

---

control sets with this objective function are not subsets of each other and thus, they can also use the cheaper control sets during learning, while the UCB-CVS variants suffer worse performance here due to artificially selecting suboptimal control sets and queries with the e-relaxations. This worse performance encoded in Theorems 4.1 and 4.4 as the sum of e terms.
(4) Increasing the variance of the probability distributions has competing effects on the simple regret. Of the 42 experimental settings (combinations of objective function, cost set, and algorithm) in which the variance makes a difference (excluding TS-PSQ and UCB-PSQ for all objective functions except airfoil), the settings with variance 0.02, 0.04, and 0.08 achieved the lowest mean simple regret by the end 11, 6, and 25 times, respectively. This generally supports Theorem 4.4 prediction that higher variances decrease the upper bound on regret. However, due to the looseness of the bound, this effect is not guaranteed and there are still cases where lower variances lead to lower regret, as suggested by the argument about feasible sets when discussing Theorem 4.1 note that the same MIGs of the feasible sets for control sets 1 to effects and conclude that the effect of increasing variance is problem- and
appear in Theorem 4.4 We observe competing
While higher variances may lead to more exploration, they may also result in too much smoothing of
function values which may hinder the learner's 's ability to focus on high-value query regions.
Conclusion
This paper introduces the BOCVS problem and describes the UCB-CVS algorithm that is provably no-regret in solving this problem. We show that our algorithm performs well across several different experimental settings and achieves the desired goal of finding significantly better solutions within the same budget. This work opens up avenues of future research: particular, an entropy search-bases based algorithm [14] [3] 4I that chooses control sets and queries based on expected information gain per unit cost a non-trivial and promising direction for alternative methods of solving BOCVS.
Acknowledgements and Disclosure of Funding
This research/project is supported by the Agency for Science, Technology and Research, Singapore (A (A*STAR), under its RIE2020 Advanced Manufacturing and Engineering (AME) Programmatic Funds (Award A20H6b0151) and its RIE2020 Advanced Manufacturing and Engineering (AME) Industry Alignment Fund- - Pre Positioning (IAF-PP) (Award A19E4a0101). Sebastian Shenghong Tay is supported by A STAR.
References
[1] V. Aglietti, X. Lu, A. Paleyes, and J. González. Causal Bayesian optimization. In Proc. AISTATS, pages 3155-3164. PMLR, 2020.
[2] V. Aglietti, N. Dhir, J. González, and T. Damoulas. Dynamic causal Bayesian optimization. In Proc. NeurIPS, volume 34, pages 10549-10560, 2021.
[3] M. Balandat, B. Karrer, D. R. Jiang, S. Daulton, B. Letham, A. G. Wilson, and E. Bakshy.
BoTorch: A framework for efficient Monte-Carlo Bayesian optimization. Proc. NeurIPS, pages 21524-21538, 2020.
[4] N. Branchini, V. Aglietti, N. Dhir, and T. Damoulas. Causal entropy optimization. In Proc. AISTATS, pages 8586 8605. PMLR, 2023.
[5] S. Cakmak, R. Astudillo Marban, P. Frazier, and E. Zhou. Bayesian optimization of risk measures. In Proc. NeurIPS, pages 20130-20141, 2020.
[6] Y. Chen, A. Huang, Z. Wang. I. Antonoglou, J. Schritwieser, D. Silver, and N. de Freitas. Bayesian optimization in AlphaGo. arXiv: 112.06655, 2018
[7] S. R. Chowdhury and A. Gopalan. On kernelized multi-armed bandits. In Proc. ICML., pages 844-853, 2017."
[8] D. E. Crabtree and E. V. Haynsworth. An identity for the Schur complement of a matrix. Proceedings of the American Mathematical Society, 22(2):364-366, 1969.
[9] D. Dua and C. Graff. UCI machine learning repository, 2017. URL. http: htttt:://acciee...... uci. edu/ml
10

---

[10] J. Gardner, G. Pleiss, K. Q. Weinberger, D. Bindel, and A. G. Wilson. GPyTorch: Blackbox matrix-matrix Gaussian process inference with GPU acceleration. Proc. NeurIPS, pages 7587-7597, 2018.
[11] R. Gamett. Bayesian Optimization. Cambridge University Press, 2023. To appear.
[12] C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-362, 2020.
[13] S. Hayashi, J. Honda, and H. Kashima. Bayesian optimization with partially specified queries. Machine Learning, 11 (3):1019-1048; 2022.
[14] J. M. Hernández-Lobato. M. W. Hoffmann, and Z. Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Proc. NeurIPS, pages 918-926, 2014.
[15] K. Kandasamy, G. Dasarathy, B. Oliva, Schneider, and Póczos. Gaussian process bandit optimisation with multi-fideligg evaluations. In Proc. NeurlPS, pages 1000~1008, 2016.
[16] J. Kirschner and A. Krause. Information directed sampling and bandits with heteroscedastic noise. In Proc. COLT, pages 358-384, 2018.
[17] J. Kirschner, I. Bogunovic, S. Jegelka, and A. Krause. Distributionally robust Bayesian optimization. In Proc. AISTATS, pages 2174-2184, 2020.
[18] T. L. Lai, H. Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22 1985.
[19] T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[20] Mockus, V. Tiešis, and A. Zilinskas. The application of Bayesian methods for seeking the extremum. In L. C. W. Dixon and G. P. Szegö, editors, Towards Global Optimization 2, pages 117-129. North-Holland Publishing Company, 1978.
[21] Q. P. Nguyen, Z. Dai, B. K. H. Low, and P. Jaillet. Optimizing conditional value-at-risk of black- box functions. In Proc. NeurlPS, pages 4170-4180, 2021.
[22] Q Nguyen, Z. Dai, B. K. H. Low, and Jaillet. Value-at-risk optimization with Gaussian processes. In Proc. ICML, pages 8063-8072, 2021.
[23] Q. P. Nguyen, Z. Wu, B. K. H. Low, and P. Jaillet. Trusted-maximizen entropy search for efficient Bayesian optimization. In Proc. UAI, pages 1486-1495, 2021.
[24] T. Nguyen, S. Gupta, H. Ha, S. Rana, and S. Venkatesh. Distributionally robust Bayesian quadrature optimization. In Proc. AISTATS, pages 1921-1931, 2020.
[25] R. Oliveira, L. Ott, and F. Ramos. Bayesian optimisation under uncertain inputs. In Proc. AISTATS, pages 1177-1184 2019.
[26] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin,
N. Gimelshein, L. Antiga, et al. PyTorch: An imperative style, high high-peeffrrance deep learning 2019.
library. In Proc. NeurlPS, pages
[27] M. Poloczek, J. Wang, and P. Frazier. Multi-information source optimization. In Proc. NeurIPS, pages 4288-4295 2017.
[28] A. Rahimi and Recht. Random features for large-scale kernel machines. In Proc. NeurIPS, pages 1177-1184, 2007.
[29] R. Shalloo, S. Dann, J.-N. Gruse, et al. Automation and control of laser wakefield accelerators using Bayesian optimization. Nature Communications, 11(1):1-8, 2020.
[30] B. J. Shields, J. Stevens, Li, M. Parasram, F. Damani, J. I. M. Alvarado, J. M. Janey, R. P. Adams, and A. G. Doyle. Bayesian reaction optimization as a tool for chemical synthesis. Nature, 590(7844):89-99) 2021.
[31] J. Snock, H. Larochelle, and R. P. Adams. Practical Bayesian optimization of machine learning algorithms. Proc. NewrIPS, pages 2951-2959, 2012.
[32] N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: regret and experimental design. In Proc. ICML, pages 1015-1022, 2010.
11

---

[33] S. Sussex, A. Makarova, and A. Krause, Model-based causal Bayesian optimization. In Proc. ICLR, 2023.
[34] M. Swamidass. Encyclopedia of production and manufacturing management. Springer Science & Business Media, 2000.
[35] K. Swersky, J. Snock, and R. P. Adams. Multi-task Bayesian optimization. In Proc. NeurIPS,
pages 2004-2012 2013.
[36] S. Takeno, H. Fukuoka, Y. Tsukada, T. Koyama, M. Shiga, I. Takeuchi, and M. Karasuyama. Multi-fidelity Bayesian optimization with max-value entropy search and its parallelization. In Proc. ICML, pages 9334-9345, 2020.
[37] S. S. Tay, C. Foo, U. Daisuke, R. Leong, and B. K. H. Low. Efficient distributionally robust Bayesian optimization with worst-case sensitivity. In Proc. ICMI,, pages 21 180-21204, 2022.
[38] S. Toscano- Palmerin and P. I. Frazier. Bayesian optimization with expensive integrands. SIAM Journal on Optimization, 32(2):417-444 2022.
[39] R. Turner, D. Eriksson, M. McCourt, J. Kiili, E. Laaksonen, Z. Xu, and Guyon. Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Anal- ysis of the black-box optimization challenge 2020. Proc. NeurIPS 2020 Competition and Demonstration Track, pages 3-26, 2021.
[40] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, Peterson, W. Weekesser, J. Bright, S. van der Walt, M. Brett, J. Wilson, K. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, I. Polat, Y. Feng, Laxalde, Perktold, R. Cimrman, I. Henriksen, A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing Python. Nature
E. W. Moore, J. VanderPlas,
Methods, 17:261-272, 2020.
[41] Z. Wang and S. Jegelka. Max-value entropy search for efficient Bayesian optimization. In Proc. ICML, pages 3627-3635, 2017.
[42] C. K. Williams and C. E. Rasmussen. Gaussian Processes for Machine Learning. MIT Press, Cambridge, MA, 2006.
12

---

A Proofs
A.1 Proof of Theorem 4.1
Theorem 4.1
With probability at least - 6, UCB-CVS (Alg.
incurs a cost-varying cumulative
regret bounded by
Rr 0 ((B+ (x(2) + log + 1
m
(VTTT,(2)) (2.)) log 1) Gm
Σ Ci
by setting &t = B + 2 + log( + 1)/0)).
Proof.
RT
Ci. E
f([x" xx(xx"==1')))) 13 [f(((x") x D!)
C/ E 11-11(x* (1x x []] B[S([x' x x-)
(B) Ur ([x*) [D] - E[S([x* , +
x-]]
Ci.
T
(E
U/
x |)| - [[(( X (1)] + Cm
(3)
t=1
T
Ci. (E (1-1 x "I) f((x* X *D]) + Cm
E1
1=1
1=1
T
[ x "1) f(1xtt, x [i]]
Cm
ET
t=1
(28r)
E2 10001( x x1] + Cm
rET.
[=1
+ 8 (log(4) -111 1)
(66)
(2
2 Σ
(x-) + +log m +1
cm Σ c1
(4)
1=1
(1))
(2
22 2 ((T, + 2)TT, (22) + log
m 1
+ 8ogg(4) ((44)))) +1)
+ Cm
Ct
0
Σ 4BT
(Virm, + log m +
))
Cm
Σe
T
(5)
t=1
T
0
(B+ (T((X) log 8
m 11
Σ
(ViTm
(2)) + log
m +
8 + Cm
where T; is the ordered sequence iterations at which control set is chosen, (i) follows from the algorithm's 's choice of x (ii) follows from Lemma A.4 with probability 5/(m 1), (fii) follows from Lemma A.1 with probability 5/(m + 1) applied once for each control set i, and (fr) follows
from Lemma A.3 and the definition of X; as the feasible set for control set i. A union bound over the m + 1 events comprising the m applications of Lemma A. and single application of Lemma A.4 yields the desired å probability bound.
13

---

A.2 Proof of Lemma A.1
Lemma A.1. Let k(x. and let T, be the ordered sequence of iterations which control set i is chosen by UCB-CVS. For any i E [ml), with probability at least 1 6,
Σ EB x DD] 2 Σ ox-1(xx) LET.
4 4log + log 4 + 1.
BE
Proof. For this proof, define a probability space (9t, P) and a filtration F = x x " ye), the uygma-aleebra generated by all the random variables in the BO procedure known by the end of iteration t.
(Fi) where
Fi (11, x²1 x x", 1/. i2. x"2 ,x' xxx*, .2 ...: de, x",
In advance of proving this result, it should be clarified that, in the main paper and all proofs excluding that of this lemma, E [ ((x",, x]]] denotes the quantity obtained by treating Ø-11 and x as deterministic and treating X- as a random vector distributed according to the probability distribution P-*,, This is for ease of exposition. In the following proof, however, when using the
formalism of random processes, what was previously referred to as EE (0 (,=",xxxx"" x)]] is actually
E(o:-1(X;) F.- The meaning is equivalent since dt-1, 4,, and x are FF F-predictable, and the only uncertainty about 1x-1(x;) arises from the lack of knowledge about x
Now we begin the proof proper. Define m stochastic processes (x (x!2)
(x[m)))e J where, using 1 [A] to denote the indicator function that is equal to when the event A is
true and otherwise,
x ox.) 1/1, =
Since each x is F, F.mmeuuurall,, each stochastic process is adapted to F. Next, define
m (4) = E x (6) F
= 1i
live
e) Fi-1l
1/. | Fi-1l
where the last equality uses the pull-through property since is Fi-1 measurable. Using Lemma A.5 with b, = since k(x, x) = 1, with probability at least 5, for any T 2 1,
m
(2)
2
X (1) + 4 log
1 + 8llogg 4 +
8
t=1
(=1
σ (xx) 1/: = i) + 4 1
ll. i E|o (x:) F(-1] < 2 Σ
+8log +
1 + 8 18ogg 4 +1
B(a--((x)) (x)) [i-1] < Σ
(x,) + log x
IET:
*
which completes the proof.
A.3
Proof of Proposition
4.2
Proposition
4.2
!fthere exists a > O.s.. for all i it,
4 S R [ x x-1
max [[f([x', X x-] xieXi
eventually (i.e.. the inequality holds for all t 2 for some 2 1), and (x()) < O(VT). then, with probability at least 6, 1om TT 0 for all + i and UCB-CVS incurs a cost-varying cumulative regret that is sublinear by setting 3, = B 2 (X') + log((m + 1)/8)}.
Proof. Define
xj
argmax E 14 (xx |)} and je
[r m E (l ([x* X -[]. Using [[A] to denote the indicator function
14

---

that is equal to 1 when the event A is true and 0 otherwise.
T
T
[[x
x DD t 2 E' ( x-1]
[l x 1)} + E 11-1(xx x
Blu ((x x [|] + 2 B M(x x X-
1 [ x [>] 2 18 f([x , x- cr]
T
$9 1+
E 22- [x] x [D] 2 E f((x" x] E1)
t=y
11-14 + Σ
1
[1]] 2
max
E
[[[[xx] x +
X
t=g
16 14 + Σ
EE
X
T)] [[
t=y
T
- 1 +
EE U1 [x] -
[[
t=g
5 1 +
U1 (x) X DD] -[ x 1)]]
l=q
(M))
-9-1+0- (T - q a+4 B (BVT-oot(X)) .T (7--++(22)) mo--+(())))
where (i) follows since control set i is only played when the condition on the RHS is true, (it) follows from the definitions of Jr and x!", and (iti) follows from the steps from (3) to ( in the proof of Theorem 4.1 and O denotes suppressing logarithmic factors. Now dividing both sides by and taking the limit as T goes to infinity,
T lim q (9-1+0- ( 9+1 B (B + -T- +r--+1((7) (x))
lim T-x T T T
which follows from YT (X) < (VV)) and completes the proof that, if the conditions in the proposi- tion are fulfilled, suboptimal control sets will only be played a number of times that is sublinear in T. The proof that Rr will then also be sublinear in T is straightforward Assuming without loss of generality that i" m,
T
Rr =
Σ
Ci
(B
x - x DD])
[[[[[x
Ci E f(xx" x x=] D] - [[x((xt x (1])
1=1 tET.
< m-1
Tic
[ [B[ xxx
min E Elx( x DD
x'Exi
Σ (B[ x-1) [[][((('xx))))
[[s((x++ x x-1
+ Cm
T
15

---

m
Σ T,C+ + Cm
Σ
E [(x , 1) B [f((t, x 111
( m-
Σ T.C+0 Cm
B B (+)))(2) + +log m + 8
(Vi (Zm) + log 5
m + 1
where T. is the ordered sequence of iterations at which control set i is chosen and C2 (B] []] minxiigs [[x( (x-())))) and (i) follows from the steps in the proof of Theorem penoorem/.1bbu but only for control set m and without accounting for the e-schedule. Since each T; is sublinear in T. dividing both sides by T, using the fact that (xt) < O(VT), and taking the limit as - oc yields the desired result and completes the proof.
A.4 Proof of Lemma
Lemma Assume that, for each control set i, the random variable Y; == (TO) 0,, x,
has median M; such that EY > M,] S h,Ms for some h; > O, where X X P With probability at least 1 - 6, there will be at least N; non-overlapping pairs of queries x and x' chosen by UCB-CVS (Alg. with control set such that ||x x11 2 Mo where
1
T, log 1
N₂
(T: 1)
4
8
4 V[X.].
M2 2 ha EE
Proof. Consider two queries x = only selects x' and x" while x and x' are sampled from the environment. Before they are sampled, the queries may be considered themselves random vectors composed of one deterministic partial query and one random partial query. Denote these random vectors X =(x', X and
== x x and x' = [x" x chosen with control set i. The learner
X [x" X ||
X'1 is therefore a random variable as well. Observe that
X - X
XXXI12
Σ
(x 24)) + Σ (Xe x
JET,
EEI.
> Σ (Xe x1)²
tεT,
||0, X X,
-Y
where Y is a random variable that is i.i.d. with Y. Therefore, any |X- - 2X112 can be treated as a random variable equal to some Y/ that is i.i.d. with Y, plus some non-negative term. The rest of this proof will use lower bounds on random variables i.i.d. with Y,, which will turn imply lower bounds on X - ?
E| = E
Σ
(Xe- - X2)²
Σ
E
[(xe - -x,- - -(x} - x(
E
Σ
E
((Xe - Xz) - (X-- - -x,))
EET.
Σ
E (Xe - x,)² - -( XX(X -
EE
16

---

Σ
18 (Xx Xx)a E =E((Xe Xx) x3)] + E (X2 (x)-
EEI
Σ
[ - x + - x3)9
EEI,
Σ 2V[X
(6)
EEI
We will now construct a lower bound for median Y, denoted M,.
[[K] = B[Y,J, < M.] P(Y; < M,) B[K|Y; M.] P(Y, = M.) + BYY > M,j P(Y, > M,)
< M, P(Y; 2 M,) + BY > M.] P(Y > M.)
(0)
$ M, P(Y, & + P(Y > M))
(10 1
1
M, + (hg M,)
2
h4 + M4
2
where (i) follows from our assumption on the median M, and (ii) follows from the definition of
median: P(V, S M,) 2 1/2. Substituting in (6 completes our construction of the lower bound for
M₁:
2
M Z
E
h, +1
4
V[X.].
h4 +1
EET.
Now consider the [T:/2] non-overlapping pairs of queries chosen with control set i Associate each pair with a random variable Y,, such that we have [T:/2] i.i.d. random variables Yı, Yiz.... Y, / From the definition of median, P(Y; 2 M,) 1/2. Without loss of generality, assume the worst- case such that P(Y: 2 M,) 1/2. We can now construct [T:/2] i.i.d. Bernoulli random variables Z1, Zz..... Zn. n [T/22], with p 1/2 where success (Z, = 1) corresponds to Yi M, and failure (Z, 0) corresponds to Yı < M, Further define the random variable Z = - Zj.
Applying Hoeffding's s inequality,
P
> j=1
(Z - S -t -
S (-2nt²)
1 5 -1) 11
eexp (-2nt²)
P(Z < n - t)) S eexp (-2nt²).
Choosing == p a/n for some constant a,
P < exp
22n (p -p-
)))
a 2) n
For P P(Z
exp -2n p a) 21 ) 8
'While we technically have (T) (overlapping) pairs, the squared distances between each such pair will be identically distributed but not independent. For example, if 1; 2 3 and we knew that (Ti) of the squared distances were equal to 0 (i.e., all the queries are exactly the same), the last squared distance must also be equal O.
17

---

12
1
=
np
2
log
8
1
T;
T
1 8
log
2
2
2
1
(T)
1)
Ti log
8
a (T, 1) V 4
Ti log
Therefore, with probability more than 6, N; = [TT 1)
/ HT, log i.e., the number
of non-overlapping pairs with squared distance greater than M, is at least N;, which completes the proof.
A.5 Proof of Theorem 4.4
Theorem
If the following assumptions hold:
1. The assumption of Lemma 4.3 holds;
2. The kernel x') is isotropic kernel (which only depends distance and can be written as ki[[x - x\I));;
3. There exists an iteration such that for all t rr S m - and all t > r,4 = m,
then with probability at least - 8, UCB-CVS (Alg. 7 incurs a cost-varying cumulative regret bounded by
RT S Ea ca+0l
T
((
VT((2) log 8
2m
)
( cm
(cmn (VTrr(2) L. + log 2mn 5
(Trrn log 8
2m
Ci
i=1
m-1
C C= A
Σ
No log V--2k (vM,) Ms
k
(vM))²
M. 2) W
by setting 3t B + 0 (1--1(X) +++++++ log (2m) /8)) where N and M, are defined as in Lemma 4.3 and V; and W are residual terms defined in (10).
Proof. We first construct lower bound the sum of posterior standard deviations of the queries up to iteration i.e. the queries that were chosen with any control set except the last.
Σ (x)) 2
Σ (xi)
1=1
x
1 2
log(1 -11
(80)
Alog I T
= Alog () IKI + K,l)
= -A(-r log A + log XI + K,I)
(10)
2 >(log |I + K,, - 2)
18

---

where (i) follows from the assumption that k(z,2) 2) which implies ox-1(x) S 1 for all x X and all 2 (ii) follows since log(1 +z) I x for all x > -1, (iti) follows from Lemma A.2 and
(iv) follows from A= + (Lemma A.4 noting that T 2 and taking lim,-xx -r log X.
From Lemma 4.3 with probability 5/ (2m), there will be least N₂ pairs of queries chosen with control set with squared distance at least M,, where
2m 8
N =
( 1) log
4
M, h4
V[X1]
BET.
N; queries in an ordered sequence S and keep paired queries adjacent to each other. The sequence should be ordered such that, for any control sets and j. if then queries chosen with should appear in the sequence before queries chosen with Denote T the ordered sequence of iterations at which each of these queries were chosen by the learner where the order corresoonds the order in S. Using and column swaps K,, construct new Gram matrix K, such that, for all j, l Σ mn-1 No.
Gather these 2 2
K.IJe K 7,
In other words, have simply reordered the underlying queries that result in the Gram matrix K, to produce a new Gram matrix K, such that the first 2 Σ N, rows (and columns) correspond the 2NN; queries, and paired queries (that have at least M, squared distance between them) are kept in adjacent rows (and columns). Note that
[AI K = [AK K,Jje
i.e., the
and column swap operations AI K, result in AI + K,- Note that swapping the positions of two queries corresponds to row swap and column swap in the Gram matrix. We
can thus conclude that
[II + K, = +I+
(8)
since determinants are invariant under even number of row or column swaps.
Write [AI K2|
A B1 Ci D1
AI + K.
where A is 2 2 matrix. Since A₁ invertible,
|AI + K. A CiA CIA,'BI
where D1 C1A, B, is the Schur complement of A₁. Observe that
D CIA, B AI K k 2K, + AI) 22,5-2
AI + K,-2
where K2 and K,-2 are the prior covariance matrices of the first queries and last queries
respectively, k2,--2 is the prior covariance between the first 2 queries and the last r 2 queries, and K2-2 is the posterior covariance matrix of the last queries conditioned observations the first 2 queries. We can repeat this decomposition:
A² Bg
AI + K
C2 D2
AI K = A2 D2 C2A, B
D2 - C2A,1 D2 B2 AI K.-4
where K the posterior covariance matrix of the last r queries conditioned on observations
at the first 4 queries, by the quotient property of the Schur complement S Define = -E N; Performing this decomposition N times yields
AI + K,
I j=1
A IK
K.-2N
19

---

where each A is the 2 x 2 posterior covariance matrix of pair of queries chosen with some control set that have least M, squared distance between them conditioned on observations the first 2(j -1) 1) queries in the sequence, plus AI. From and
N
Σ (x)) 2 A 1=1
log A,1 + log AI + K2-2N -
(9)
Let xj and X refer to the pair of queries associated with A and ky to the posterior covariance function conditioned on observations at the first 2(j - 1) queries in the sequence. Define k, and kj as the R22()-1) vectors of the prior covariance between the first 2(j 1) queries in the sequence and xj and 83 respectively. Further define M, == K2 + AI. Use (u, v)M to denote u Mv, and ||ul| AN to denote /(u. u) Each | can be lower bounded as
ررyl = (8), &2) + (kss (8 x3) + X) R3 (8,, x3)2
= ( 2yy Je, (K4, xK.) + Ake (xx, x3)) + Ahy (Kt) x/) ) + x2 (k,())
1 - k I|m )) 1 - | 115liim 1 )
+ > (1 - ||k| [|K5||iM, :) + x (1 (1- -115(1(m,1)) ) + X2
2
[M{}, 83) (ks k3} Mj
(1 |ky| (lllw ) (1 (1- ||| 11 (14,') )
+ +2 (1 (1-1|k, ||k] +*x(1_1kk]lnn) [|Ks/1hm711
> (1-11<]1(a3)) + x2
A(R,, 2,)2 (2x X3) (kj, Ki) Ki)M,²' - (kg, k/)/a,,
'M,"
(1)
|ky 1kyll17; llar. ) (1 (1-11K3) || lInr:)) ) + A (1-11Kslirr; -111k]ll/ )+ x (1-113]lmnz)) ) + x2
M(x,, x2)3 -2k((2), x2) [|Ks)|| ||Ks/ll0,= ||K5 1MM."" - ||k, -11k, lla, ||2/)lmm=
-1- [|k]|| M, || 11::: + > (1-11KslRag + > (1 +1-11113311a (1111//lba==)) :) + X2
K(x,, x2)² 2k, 83) ||K)||11,1 ||Ks] lang"'
(0))
||||| (M... ||K]|| |k3] + X (1-111111 (1-111kslhn + > +x(1-118]11g)
) +
2
M5²
k(8,, x,)²² - 22 X3)
X2 - 1 (A + 1) (1 |k/ |1ks lirr + (2 + 1)
1 [1-1ks]1pp [B5//lnn: -2((8,, -
- x2)
=x- - 1+ (A (1+ (K,( ky (8), x3)) 22k(2,, 83)) - 2,)
where (i) follows from our assumption that k(x, x) 1, (ii) follows from the Cauchy-Schwarz inequality, and (iii follows since - |kk, M < and [K|l|2, 1.
Define S = Ei Nr and ē. = mins, ++1555 (k; x2) + ky K,)). Substituting this result into
(A 1)+1) (R.(2), x2) + (x5, 22(x), x3)) Σ (xx) X Σ log -12-1-2 - 1
+ log
AI+ + R, -2
log (1² (x²-1+ 1 (A+1) (A+1))(((()) (,((, - (x)
X
j=
20

---

x22)
log AI K
2N -2
m-1
8:
Σ
log (12 1 + 2(A + 1)ū, (,(), 1(x,,,)) x()
i= j=Si-1t
+ log
AI + K3- -2)
m
8,
log 12- 1+ + 2(A + 1)0, 21 (VM.) -b (Vari) ))
Σ
j= 1+1
AI + K3- -2)
+ log
12 + 2(A 1)0 2h (VM.) -o (V. ))
>
log
II + K k -2)
+ log
m-1
Nglog V/--20 2k (VM.) k (VM.) W
(10)
=: C
(11)
where V; X2 + 2(A + 1)0, and W := log AI + K - 2, (1) follows from our assumption
that the kernel & stationary and can be written single argument form k[[x [||xx\xx] k(x, and the fact that every pair of queries in S chosen with control set i has squared distance at least M,.
Starting from 4 in the proof of Theorem except replacing the probabilities of all events with 2m/5.
m
2m T 0 (xx) + log Σ
8 + 8 8log(4) +1 111
Rr <
Σ (2BTT
+ Cm
Et
LET.
= 23r
Cm
2
Σ
) + 4
2m
+ 8lo((4) +1
TET
+ Σ
2 Σ
0 (x,) + 4lg
2m
+ 8 Blog(4) +
8log(4)+1) 1
+ Cm
5
1=1
TET:
2m
2 23r
Cm
2 Σ
0. (x + log
+ 8 8log(4) +1
5
teT..
+ Σg
m-1
ci
2/ 4(T:++2)22))) (Z))
4log
2m
-llog(4) + +11)
Cm
Et
x
(18)
2m
< 23T
Cm
2 4(T + (x)
T (x:) + 4 4log
+ 8log(4) +1
m- 1
2m
+ Σ
ci
2v 4(T; + +2)TT (22) + 4log
+ logg(4) +1)
+ +cm
E1
8
1=1
(si1)
2m
1 23r
Cm
2//(TT + (x) - 4
+ 8 log(4) +1
21

---

m-1
2m
+
Ci
2v A(1; + 2) (2i) + 4 log
+ +8log(4) +
+ Cm
Et
5
1=1
=0
2m
2m
=
V 1r (x)) + log 8
Cm
(TT((t) L - log
8
m--1
2m
T
+
(v TiTT, + log
+
8
1=1
(=1
where (i) follows from Lemma
A.3
(i1) follows from Lemma
A.3 again and the resulting inequality
Ei a (x+) + Et=r+ (x,) v 4(T7 + ())r( and (fiv) follows from substituting
in A union bound over the events of the single application of Lemma A.4 m applications of
Lemma A.5 and m applications of Lemma 4.3 yields the desired probability bound, which
completes the proof.
A.6 Other Lemmas
Lemma A.2 (77 Lemma 3). Let (x+)i=1 be sequence queries selected by some algorithm. Then, the mutual information 1y firr) between the noisy observations y yIT and the function values foT the queries is given by
NY log I+ -I+ K.
Σ log(1 + 12-10-_(xx))
Lemma A.3 (77 Lemma 4), Let (x:)²=1 be sequence of queries selected by some algorithm. Then
Σ Ox)((x) ()7())
log(1/8)) where B is the upper bound of the RKHS norm of f. With probability at least 6, for all x E and 1,
Lemma A.4 (77) Theorem 2). Let B = B 2
[pt-1(x)- f(x) s
(
where 14-1 and 0t-1 are defined in (1 with À 1 1) and nj 2/T.
Lemma A.5 (16) Lemma 3). Let X, be any non-negative stochastic process adapted to filtration {F.). and define m. = F(-)- Further assume that X, S by for a fixed, non-decreasing sequence (bx) br 1, with probability at least 1 - 6, for any T 2 1,
Σ m 2
Σ
X, + 4by log shr log(4br) (bT) +
B Comparison to Naive Baselines
We investigated simple extensions of TS-PSQ, UCB-PSQ, and EI-PSQ (i.e., the classic expected improvement algorithm 20 adapted for BOPSQ, see Appendix [foo details) for the cost-varying problem by dividing the acquisition score of a control set by its cost in a manner similar to Snoek al. [3 Sec. 3.2]. Fig. 3 shows the mean and standard error of the simple regret incurred over 10 RNG seeds for one set of experiments. We found that these naive methods generally do not work well. For TS per unit cost and UCB-PSQ per unit cost, if suboptimal control set is very cheap, its acquisition score may remain artificially high throughout, and the algorithm fails to converge. El per unit cost was slightly more promising, but suffered from the inverse problem: the suboptimal control sets had 0 expected improvement very quickly and dividing by the cost had no effect. This algorithm thus fails to encourage exploration with cheaper control sets. Furthermore, the EI algorithm was computationally expensive due to the double Monte Carlo expectation computation. In general, we see that the UCB-CVS algorithm is able to use the cheaper control sets much more effectively for exploration and hence find better solutions.
22

---

Moderate costs vartarcew
Woderate costs varience-o.0
Moderata cost, vertince-
15 UCB PSi
UCB PSQ
UCB PSO
TSP5O per ood
TS-P5Q per cost UCB PSO per cost taMt
TS-F5Q coet UCB PSO per 00d
UCB PSQ per cosT
per
ETC
ETC Ada
Budget
Figure 3: Mean and standard error (over 10 RNG seeds) of the simple regret (lower is better) incurred against cost spent (budget) C. by all algorithms including TS- TS-PSQ per unit cost, UCB-PSQ per unit cost, and El per unit cost, with samples from the GP prior as the objective function, moderate cost set, and all variances. A diamond indicates the average budget after which algorithm only chooses the optimal control set.
C Experimental Details
All experiments use a squared exponential kernel with ARD lengthscales that depend on the objective function, k(x, x') 1, Gaussian observation noise with 0.01, and initial query-observation pairs with queries drawn uniformly random. All expectations are approximated with Monte Carlo sampling with 1024 samples. All acquisition maximizations are performed with L-BFGS-B B with random restarts. All query sets are [0, 1]
C.1 Objective functions
The control sets described here are given in an order corresponding to their costs given in Sec. For example, for the GP samples objective, under the cheap cost set, control set {1} has cost 0.01, control set {1, 2} has cost 0.1, and control set {1,2,3} has cost 1.
Samples from GP prior (3-D); We use samples from the same kernel h used to model the GP posteriors during learning. We use a kernel lengthscale of 0.1 and control sets ((1. (3), (1,2), (1,3), (2,3), (1,
Hartmann (3-D): We use kernel lengthscale of 0.1 and control
sets
(3), 21, (1,3), (2,3), (1,
Plant growth simulator (5-D): The plant growth simulator is GP built from private data collected on the maximum leaf area achieved by Marchantia plants depending on imput variables Ca, B, NHg. K, and pH. We use min-max feature scaling to scale all input variables to [0, 1] and standardize the output values. We use the posterior mean of the GP as the objective function. We use a kernel lengthscale of 0.2 and control sets {(1, (3, 4), (4,5), (1, 2,),,, (2,3,4) 4), (3, 53, (1, 3,4,5)
Airfoil self-noise (5-D): We use the airfoil self-noise dataset from the UCI Machine Learning Repository [9]. To scale all input variables to [0, 1]. we first take the natural logarithu of vari- ables 1 and 5, then do min-max feature scaling on all input variables. We also standardize the output values. We then feed the data into a default SingleTaskGPP from BoTorch and use the posterior mean as the objective function.
use a kernel lengthscale of 0.2 and control sets [14,5), {2. 5), (1, (2, (3,5), [1.2), (3,4]).
C.2 Algorithms
UCB-PSQ and UCB-CVS: For the experiments, we 3r for all I.
TS-PSQ: Following [13], we use random Fourier features (RFF) 28 to approximately sample from
GP posterior. We use RFF with 1024 features.
23

---

EI-PSQ: We adapt the BoTorch acquisition Noieyxepeeednmnroeeeenn to the BOPSQ problem setting. To evaluate the acquisition score of partial query, we first sample 32 fantasy models of from the GP posterior. For each fantasy model, we compute the expected value of the partial query and take the best value as the value of the best observation so far (assuming the full query control set is available). We then compute the improvement score as the expected value minus the best value, and then average the improvement score over all fantasy models.
C.3
Implementation
The experiments were implemented in Python. The major libraries used were NumPy [12), SciPy [40], PyTorch [26]. GPyTorch [00 and BoTorch [3] For more details, please refer the code repository.
C.4 Compute
The following CPU times in seconds were collected on a server running Ubuntu 20.04.4 LTS with 2x Intel(R) Xeon(R) Gold 6326 CPU @ 2.90GHz and 256 GB of RAM. We measure the CPU time for iteration of TS-PSQ and UCB-CVS with a dataset of 100 observations. In general, none of the algorithms in the settings tested in this paper require significant amount of compute.
GP sample
Hartmann
Plant
Airfoil
TS-PSQ
6.27
4.14
8.96
232.27
UCB-CVS 37.92
52.34
61.96
87.09
D Limitations
A limitation of our work is that the theoretical guarantees of UCB-CVS rely on a few assumptions that may not hold in practice. For example, the regularity assumption that assumes the objective function f resides in some RKHS may not be true in some problems. The kernel corresponding to this RKHS may not known either. The work also assumes that the probability distributions governing each variable are independent and fixed. In practice, these assumptions may be violated, if the probability distributions have some dependence on one another, or may change over time.
24


Reviews:
[{"review_id": "iOU6CoVPne", "reviewer": "Reviewer_mBSK", "summary": "The authors study the problem of Bayesian optimization with cost-varying variable subsets (BOCVS) where in each iteration, the learner chooses a subset of query variables and specifies their values while the rest are randomly sampled. Each chosen subset has an associated cost. The authors analyze how the availability of cheaper control sets helps in exploration and reduces overall regret.", "questions": "\n1. How to choose the control set? How to choose their values?\n\n2. The examples in the experiment section are based on simulators. A real-world example could strengthen the paper. ", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is with good structures and is well-written. The problem is interesting and potentially has wide applications. The authors provide a profound theoretical analysis. The experimental results show the benefits of the proposed method. ", "weaknesses": "Experimental results on a real-world application could make the paper stronger. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time spent reading our paper and writing this review.\n\n**Questions**:\n \n1. As part of the problem specification in Sec. 4, the learner is given a collection $\\mathcal I \\subseteq 2^{[d]}$ of control sets indexed by 1,2, ..., $m \\coloneqq |\\mathcal I|$. These are the control sets of which the learner is required to pick one at each iteration in the BO process. As described in Sec. 4.1, Algorithm 1's procedure to choose a control set and the partial query at each iteration is as follows:\n    1. Compute $g_t \\coloneqq \\max_{(i, \\mathbf x^i)  \\in [m]\\times \\mathcal X^i} \\mathbb E[u_{t-1}([\\mathbf x^i, \\mathbf X^{-i}])]$, i.e., the expected UCB of the best control set and best partial query given that control set. Practically speaking, this expectation and all expectations are approximated to arbitrary accuracy using Monte Carlo sampling. All acquisition maximizations are performed with L-BFGS-B with random restarts as is standard for BO acquisition maximization.\n    2. Collect every control set $i$ that fulfills the condition $\\max_{\\mathbf x^i \\in \\mathcal X^i} \\mathbb E[u_{t-1}([\\mathbf x^i, \\mathbf X^{-i}])] + \\epsilon_t \\geq g_t$ into a set $\\mathcal S_1$. These are the control sets whose best expected UCB are $\\epsilon_t$-close to the best value $g_t$.\n    3. Further reduce this set $\\mathcal S_1$ to $\\mathcal S_2$ by retaining only the control sets with the lowest cost. This step ensures that Algorithm 1 uses cheap control sets when available.\n    4. Finally, it chooses the control set from $\\mathcal S_2$ with the largest expected UCB. This step ensures that, in the case of multiple control sets having the same cost after Step 3, Algorithm 1 chooses the 'best' among them. The partial query is then the one that maximizes the expected UCB given this control set.\n\n2. We wish to point out that the plant and airfoil experiments are based on real-world datasets. The simulators are built on these real-world datasets in an attempt to be as close to a real-world experiment as reasonably possible. Unfortunately, we do not have the means (e.g., equipment, budget, domain experts, etc) to conduct real-world experiments. We hope you will understand the limitations we work with.\n\nWe hope we have answered your questions satisfactorily. If you have any other questions that you wish for us to address, please let us know and we will be glad to respond further. "}, {"review_id": "fBoyYBhMO6", "reviewer": "Reviewer_aGSh", "summary": "This work introduces a new black-box function optimization setting where only a collection of the subsets of variables can be optimized while the values of the complement variables for each set are randomly sampled. The authors propose a new BO framework based on GP-UCB, called UCB-CVS, to solve this optimization setting. ", "questions": "1.\tUCB formula below line 161, why the subscript of $u$, $\\mu$ and $\\sigma$ is $t-1$ while $\\beta$ is $t$?\n2.\tProposition 4.2, is this result true with high probability or always true? \n3.\tEquation (2), is $M_i$ here the same as $M_i$ in Lemma 4.3? \n", "limitations": "The authors don't specifically discuss the limitations of this work. The authors can add a paragraph in their manuscript to discuss the limitations of their work based on the reviewers' feedback.\n\nNo significant negative societal impact of this work.\n", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1.\tThe problem setting is new and hasn’t been fully investigated before. \n2.\tThe algorithm proposed in this work is clearly described and the authors also provide theoretical guarantees. \n3.\tExperimental results show good performance of this new method. \n", "weaknesses": "1.\tThe extent of the problem setting's relevance and interest to the Bayesian Optimization (BO) community is not apparent to me in this work, despite its novelty. The authors evaluate their methods using two real-world datasets, namely plant growth and airfoil self-noise. However, the control sets, cost values, and probability distributions are still simulated by the authors themselves. Consequently, they have not demonstrated the application of real-world problems that can be effectively addressed within this setting using the new UCB-CVS algorithm.\n2.\tIt is not so convincing to me that the terms in the cumulative regret $R_{T}$ should be multiplied by the cost $c_{i_t}$. The objective function presented in line 138 does not incorporate the cost coefficient, and it seems natural for the cumulative regret $R_{T}$ to also exclude the cost coefficient. Moreover, this approach would align better with the single regret mentioned in line 190. The cost information is already encompassed within the value of $T$, namely, for a fixed budget $C$, if we consistently select high-cost sets, $T$ would be small, resulting in insufficient observations. Conversely, if we consistently choose low-cost sets, although $T$ would be large, the optimization procedure is more likely to converge to sub-optimal solutions. Therefore, there is no necessity to introduce an additional cost coefficient for penalization purposes.\n3.\tThe font size of Figure 2 is too small to be read. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and review our paper. Let us address some of your concerns:\n\n**Weakness 1, on application to real-world problems**:  We have attempted to demonstrate the general applicability of our algorithm by using multiple cost sets. As explained in Sec. 5, while these cost sets may (at first glance) seem arbitrary, it is the algorithms’ relative performance across these cost sets rather than the absolute performance on a single cost set that allows us to understand the conditions under which particular algorithms perform better or worse. Real-world problems will come with their own cost sets defined by real-world constraints. If the real costs can also be categorized in a similar relative way like the above cheap, moderate, and expensive cost sets, then the results are expected to be similar. \n\nUnfortunately, we do not have the means (e.g., equipment, budget, domain experts, etc) to conduct real-world experiments and obtain these problem-dependent quantities that correspond exactly to some real-world problem. We hope you will understand the limitations we work with.\n\n**Weakness 2, on cost term in cumulative regret**: We believe that this is a difference of perspective: our perspective of the cumulative regret $R_T$ is that an algorithm should try to minimize the bound on $R_T$ for any given value of $T$, which is the original definition of regret in conventional BO that we have tried to adhere to for familiarity. Your redefinition prescribes the following: an algorithm should try to minimize the bound on the average regret $R_T/T$ for any given value of budget $C$. Since the average regret is an upper bound on the simple regret $\\min_{t\\leq T} r_t$, this definition is perfectly valid as well, though the analysis required to reach the conclusions of this work regarding the impact of different costs may be significantly different from ours and may be more difficult. We believe that our regret notion is more amenable to analysis. Furthermore, even though the objective below line 138 does not incorporate costs, the maximizer (i.e., $\\mathbf x^{i_t}$ s.t. $r_t = 0$) coincides for both our regret notion and your proposed regret notion, hence our regret notion is also a suitable choice given that objective.\n\nWe opted to make the cost terms explicit in $R_T$ also in order to avoid misinterpretations such as the following:  suppose that 1) the regret incurred in a single iteration were defined as $r_t = \\mathbb E[{f([\\mathbf x^{i^*}, \\mathbf X^{-i^*}])}] -\\mathbb E[{f([\\mathbf x^{i_t}, \\mathbf X^{-i_t}])}]$ without the cost term; 2) there are two control sets $j$ and $k$ such that $j$ is much cheaper than $k$, i.e., $c_j \\ll c_k$; and 3) that the learner is in the initial exploration stage in the BO procedure such that the partial queries $\\mathbf x^{j}$ and $\\mathbf x^{k}$ at each iteration are more or less random and $\\mathbb E[{f([\\mathbf x^{j}, \\mathbf X^{-j}])}] \\approx  \\mathbb E[{f([\\mathbf x^{k}, \\mathbf X^{-k}])}]$. Then, under the above redefinition of regret, the cumulative regret incurred in this exploration stage is the same whether the learner exclusively used control set $j$ or control set $k$. However, clearly, the learner is well-advised to use $j$ for exploration rather than $k$. Under the traditional interpretation that $r_t$ is a measure of how 'bad' the decision taken at iteration $t$ is, making the cost terms explicit naturally incorporates the notion that the penalty for sub-optimal plays is lower if the play was cheap, while also penalizing using the entire budget on sub-optimal plays, regardless of whether those plays are cheap or expensive.\n\n**Questions**:\n1. We adopt the notation from Chowdhury and Gopalan (2017). The reasoning is that, at iteration $t$, before deciding the control set and partial query, the learner only has access to the dataset of observations up to time $t-1$. $\\mu_{t-1}$ and $\\sigma_{t-1}$ are the GP posterior mean and standard deviation given the dataset up to time $t-1$. The sequence $\\\\{\\beta_t\\\\}_{t=1}^T$ is an algorithm parameter and is fully known at all iterations.\n2. Thank you for pointing out this omission, the result is true with high probability. We will correct the proposition to include this in the final paper.\n3. Yes, there may be some confusion here as Equation (2) is part of Lemma 4.3. Equation (2) puts a lower bound on $M_i$ that depends on the variances of the probability distributions involved.\n\n**Limitations**:\nWe have a section discussing limitations in the Appendix.\n\nWe hope our response above has adequately addressed your concerns. Please reach out to us if you have any further questions."}, {"review_id": "xAzIX5A1Ya", "reviewer": "Reviewer_xcAB", "summary": "The submission studies the problem of Bayesian optimization (BayesOpt) where we can choose to control a subset of the decision vector while the other variables are randomly selected.\nUnlike previous works on contextual BayesOpt and BayesOpt with uncertain input, this paper leaves the choice of which variables are set to the user, and accounts for the associated cost of controlling a given set of variables.\nAs far as I know, this is the first work to tackle this problem.\nThe authors then proposed an Upper Confidence Bound (UCB) style algorithm that seeks the subset of variables that yields the highest expected upper bound on the objective function's value while incurring the lowest cost.\nTheoretical guarantees are derived for the proposed algorithm, showing the algorithm achieves sub-linear cumulative regret.\nNumerical experiments show that variants of the proposed algorithm perform competitively against two baseline policies.", "questions": "- The work assumes that the uncontrolled variables are independently sampled from their respective distributions, but I imagine there are scenarios in which the decision variables aren't conditionally independent. Could the proposed approach tackle this scenario too? Perhaps the correlations between known dependent variables could be modeled somehow.\n- My understanding is that we assume the costs $c_i$ associated with controlling given subsets are known _a priori_. Do the authors have any comment on how much relaxing this assumption would complicate what we have? I imagine Line 5 in Algorithm 1 might be harder to implement.\n- How was $4$ chosen in the **ETC-Ada** variant's $4/c_j$ threshold? Should this be the same constant in all settings?", "limitations": "The authors discuss the difficulty of setting the $\\varepsilon$-schedule in Sec. 4.3 and recommend an explore-then-commit strategy.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The submission tackles an original problem that is motivated by many real-world scenarios.\nThe paper is well-written, and the exposition is clear.\nThe theoretical results are explained well and are shown to be helpful in interpreting results from numerical experiments.\nNumerical experiments on the other hand show strong performance from the proposed algorithm.", "weaknesses": "I don't have many complaints about the paper.\nThe authors can consider including the other baselines shown in Appendix B in Sec. 5 instead of simply referring to them.\nThe authors can also consider including a simple baseline that randomly selects the subset of variables to control for at each iteration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time and effort spent writing this review. We answer your questions below:\n\n**Questions**:\n1. Certainly, as long as the joint distributions are known and induce conditional expectations that can be computed or approximated via Monte Carlo sampling. Algorithm 1 will likely work well under such conditions. The only parts that will be affected are the theoretical results Lemma 4.3 and Theorem 4.4 as they assume independence in order to relate the variance of the individual distributions governing each variable to the regret bound. Some more involved analysis will be required to say something useful in the general case when the distributions may not be independent.\n2. You are correct that Algorithm 1 cannot be used effectively if the costs are not known. For example, Algorithm 1 would never play a control set $i$ if there was another control set $j$ that was both cheaper (i.e., $c_j < c_i$) and had a higher expected UCB score (i.e., $\\mathbb E[u_{t-1}([\\mathbf x^i, \\mathbf X^{-i}])] < \\mathbb E[u_{t-1}([\\mathbf x^j, \\mathbf X^{-j}])] $). Without knowing the costs, such comparisons between control sets cannot be made. Fortunately, this assumption of known costs is mild as they are problem-specific constants usually known in practical scenarios, or at least can be found with little difficulty.\n3. $4$ was an arbitrarily chosen constant. In general, we wished to convey that an $\\mathcal O(c_j^{-1})$ threshold is likely to work well across different sets of costs and is a robust choice for practitioners that keeps the number of hyperparameters to a minimum. We will make this clearer in the final version of our paper.\n\nIf you have any further questions, please let us know and we will be happy to answer them."}, {"review_id": "VLHLRL2SQT", "reviewer": "Reviewer_o8eg", "summary": "The paper introduces a novel Bayesian Optimization algorithm for the case where we select a subset of variables to query at each iteration. Furthermore, each subset will incur a different _cost_. Examples of this include: control of soil nutrients in farming, advanced manufacturing, and targeting specific subgroups for ad revenue. Previous work has focused on optimizing across subsets, but does not consider the cost. Due to the method being based on Thompson Sampling, it is not simple to extend to the cost-variable setting.\n\nThe problem setting considers the case where we can choose a subset of inputs (a control set) and its corresponding values, then the remaining inputs are samples randomly from a _known_ distribution. This setting differs from multi-fidelity problems because lack of information comes from randomness in the choice of inputs when they are not selected as part of the control set, not from querying a cheaper approximation. Our objective is to find the control set and its corresponding values that maximize the expected value of the function (with respect to the randomness in the remaining inputs). \n\nThe algorithm is based on the upper confidence bound (UCB) acquisition function, and mainly works in four stages:\n \n(a) We find the maximum expected UCB across all valid input subsets\n\n(b) We build a set of possible control sets that have a maximum value $\\epsilon_t$ close to the maximum from (a)\n\n(c) We build a set of that includes all the control sets with minimal cost from (b)\n\n(d) Finally, from the remaining possible control sets, we choose the set with the maximum expected UCB to query\n\nNote that an important hyper-parameter sequence, $\\{ \\epsilon_t \\}$ as been introduced. Then four theoretical results are presented. Theorem 4.1 shows that the algorithm is no-regret for appropriately chosen $\\beta_t$ and a sub-linear $\\sum_{t = 1}^T \\epsilon_t$. Proposition 4.2 shows that provides an alternative condition for which the no-regret property hold. Then Lemma 4.3 and Theorem 4.4 show that the bound depends on the variance of the input distributions, with larger variance allowing for more efficient exploration. They further show that by choosing an $\\epsilon$-schedule that increases the number of times cheaper controls are played, we can make the bound tighter. The $\\epsilon$-schedule was useful for theoretical analysis, but in practice it is dropped instead for a simpler idea, which focuses on fixing the number of plays for each cost-group, choosing the lowest possible cost group that still has plays at each iteration when all cost groups have been explored, the algorithm reverts to the standard version with $\\epsilon_t = 0$.\n\nExperiments are carried out in four benchmarks: a 3D GP sample, Hartmann3D, a plant growth simulator, and a simulator built from the airfoil self-noise data-set. Experiment show that when there are subsets with small or moderate costs, the algorithms give an advantage to the Thompson Sampling baseline. When costs are expensive, algorithm performance drops when cost-group sizes are fixed, but if made adaptive the performance is still competitive. In addition, the simple baselines perform well when the control sets are not subsets of each other (and therefore they are not constantly querying the most expensive one). Finally, the results show that having a larger variance for the random inputs tends to give better regret, but also appears to be problem and algorithm dependent. ", "questions": "- I saw in the appendix that you included some obvious naive baselines, in particular EI-PSQ-per-cost seemed to give stronger results than the baselines compared against in the main paper. Why was it not included?\n\n- We are seeking to maximize the expected value of the function under randomness from the non-control inputs, can you imagine a scenario where low variance would also be important? If so, would would the method be compatible with a simple scalarazation (ie. $i^*, x^* = \\arg\\max \\left[ E(f(x)) + \\alpha Var(f(x)) \\right]) $ to solve the problem?\n\n- The algorithm's performance seems to be very sensible to the choice of the $\\epsilon$-schedule. Is there any more guidance on how to choose it? Indeed, the ETC variants appear to perform very differently depending on the task. ", "limitations": "Limitations are addressed in the appendix: the theoretical assumptions may not hold in practice, and the assumption that the input probability distributions are independent and fixed may be violated (this is considered by Causal BO). The authors also mention poor scaling when the number of control sets is large.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Originality: The author propose an algorithm that tackles a problem not fully considered in Bayesian Optimization, where there are subsets of inputs that can be queried and each subset has a different cost. They also include a thorough theoretical analysis of the regret of the algorithm, and show empirical evidence of its effectiveness. Although I have not seen this specific problem solved before, there are other works could perhaps tackle the problem (see more later).\n\nQuality: The algorithm proposed is sound, combining known Bayesian Optimization ideas that are known to work well. The theoretical analysis is very good and complete, exploring the effect of different aspects of the problem (e.g. $\\epsilon$-schedule and variance). The empirical analysis is perhaps limited to a few examples, but they provide a varied number of costs and variances which is important.\n\nClarity: Generally the paper is very clear, and well written. Important equations are well explained, and the implications of all theoretical results made clear. Figure 1 is very good at explaining the problem setting, and helping understand notation. Empirical results are explained and analyzed thoroughly and clearly. Perhaps a few paragraphs of the paper could be rewritten, and result exposition improved (see later).\n\nSignificance: The problem is significant to the wider scientific community, and relevant examples are given. Although it seems limited by certain assumptions and perhaps giving more detail on the examples would be better (see later).", "weaknesses": "- The paper seems highly relevant to Causal Bayesian Optimization [1, 2, 3], where they (a) choose a subset of inputs and the rest are observed from the environment, and (b) they consider the cost of the varying subsets. In particular, they do not assume that the input distributions are known but that they instead follow an unknown causal structure which appears to be a more general of a case. Indeed it could be argued that all motivating examples mentioned by the paper fall under this umbrella (i.e. there is an underlying causal structure). Empirical comparison against their baselines would be very strong, but at least a discussion of where the settings differ should be included.\n\n- Following to the previous point, the assumption that the input distributions are known and independent of the chosen values for the control set appears to be very restrictive and limits the application of UCB-CVS. I assume the distribution could be estimated from data, so perhaps there are extensions for the proposed method when this is the case. Based on this, the significance of the proposed paper appears to be far more restrictive than claimed as it only applies when the distributions are known.\n\n- The theoretical analysis is perhaps the strongest part of the paper, however in the end the authors opted for for a rather arbitrary way of selecting which subsets to query (i.e. by defining cost groups and selecting an allocation for each). The link between the theoretical results and the new heuristic should be made clearer, in addition, the heuristic appears to me to be sub-optimal especially in the case where an expensive subset leads to clearly sub-optimal observations but we keep querying it anyway due to the requirement to query each cost group a certain number of times. \n\nMinor weaknesses:\n\n- I found the first paragraphs of section 4 (lines 115 to 138) to be a little convoluted and difficult to read. I understand there is a lot of notation to introduce, but perhaps it would benefit from a small re-write. Figure 1 does make an excellent job of summarizing it all and was very helpful.\n\n- I found the plots in Figure 2 to be a little difficult to read, the plots are small and pixelated, and the font sizes could be made bigger (there seems to be a lot of repetition in the titles so perhaps things could be condensed to use less words and make space for larger fonts). \n\n- Only using 10 runs per example seems a little bit low, would be better to use more. \n\n[1] Aglietti, Virginia, et al. \"Causal bayesian optimization.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020.\n\n[2] Branchini, Nicola, et al. \"Causal entropy optimization.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n\n[3] Tigas, Panagiotis, et al. \"Differentiable Multi-Target Causal Bayesian Experimental Design.\" ICML, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort spent writing this highly detailed and insightful review. Allow us to answer some your concerns:\n\n**Weakness 1: relation to Causal BO.** You are correct in pointing out that Causal BO as formulated in Aglietti et al. (2020) is a more general case. Specifically, our setting is a case in which there are no 'non-manipulative' variables and the causal DAG is such that all input variables have no parents and are parents of the output variable. Nevertheless, we believe our focus on this special case has value as it allows us to derive useful theoretical results that do not exist thus far for the completely general setting. To the best of our knowledge, the three works you cited and many other Causal BO works do not have regret bounds, with the exception of \"Model-based Causal Bayesian Optimization\" (Sussex et al., 2023). This work is also a special case of Aglietti et al. (2020), and has little overlap with our work as it does not consider costs of control sets or explicit probability distributions over input variables. This work and our work are products of the general principle that focusing on special cases enables the derivation of non-trivial theoretical results which may be very difficult to derive for the general case (supported by the lack of theory for the general case thus far). We believe that our work is sufficiently general to be useful for practical scenarios (where the full Causal BO apparatus may be unnecessary), and is also a stepping stone towards theory for the general case. We agree with you that the relation of our work to the Causal BO literature should be discussed and will certainly include this discussion in the final paper.\n\n**Weakness 2: assumption of known distributions.** We think this assumption is a reasonable one for three reasons:\n1. There are many scenarios in real life in which the distribution of some random variable of interest is known or at least can be estimated accurately from historical data. For instance, in our example of ad revenue maximization or crowdsourcing, where the query variables describe human demographics such as country of origin or income level, the platform being used would have access to a large amount of user demographics data.\n2. This is a standard assumption made in this line of work due to the difficulty of saying or doing anything useful with too little assumptions. Many prior BO works that cater to uncontrollable random variables make this or similar assumptions; for instance, the cited Causal BO work (Aglietti et al., 2020) assumes the presence of a dataset from an observational study. Other works that make the assumption of known distributions include BO for expected values (Toscano-Palmarin & Frazier, 2022), risk-averse BO (Cakmak et al., 2020; Nguyen et al., 2021a;b), and distributionally robust BO (Kirschner et al., 2020; Nguyen et al., 2020; Tay et al., 2022).\n3. As you have intuited, it is possible to modify the setting to one in which the distributions are not known _a priori_ but are estimated in the course of the optimization process. Previous BO works that have done this include the 'data-driven' setting  (Hayashi et al., 2022; Kirschner et al., 2020). Since the extension has already been developed in the literature, accounting for this procedure in our algorithm and theory within the constraints of a conference paper incurs additional complications that distract from our work's primary conclusions for little novelty. We will include a discussion on this extension along with references to these previous works in the final paper.\n\n**Weakness 3: choice of heuristic.** The heuristic was chosen based on the interpretation of Theorem 4.4 that an $𝜖$-schedule that increases the number of times cheaper control sets are played can reduce the MIG term of the most expensive control set $m$, which implies that if $c_i≪c_m$ for all $i$, we can reduce overall regret by playing cheaper control sets a greater number of times. The ETC heuristic is a method of enforcing these plays, whereas trying to define an $𝜖$-schedule may result in cheaper control sets not being played at all if the chosen values of $𝜖$ are too small, and knowing the range of good values of $𝜖$ _a priori_ is impossible since $f$ is unknown. We agree with you that the heuristic (with a fixed no. of plays for each control set) is sub-optimal if there is an expensive sub-optimal control set, and Theorem 4.4 reflects that as well: taking $m$ to be optimal, if there is a sub-optimal $i$   such that $c_i ≈ c_m$, then the decrease in the overall regret is not as large as if $c_i≪c_m$ for all $i$. To overcome this, instead of a fixed number of plays for each control set, we suggest in the paper to choose the number of plays adaptive to the cost, and our ETC-Ada variant in the experiments suggests that an $\\mathcal O(c_i^{-1})$ number of plays for each control set $i$ generally performs well across many different settings and is a robust choice for practitioners. We will make this justification clearer in the final paper.\n\n**Questions:**\n1. We did not plan to include these obvious naive baselines in the main paper as we hypothesized that they would not work well due to the reasons explained in Appendix B, and they were not required to arrive at our main conclusions in the Experiments sections. We agree it would be interesting to see how EI-PSQ-per-cost performs in all settings. We will run this baseline in all settings and include the results in the main body in the final paper.\n2. Certainly, there have been many BO works that aim to maximize some risk-sensitive objective such as mean-variance as you mentioned (Iwazaki et al., 2021), or others such as VaR/CVaR (Nguyen et al., 2021a;b). We suspect it will not be too difficult to replace the expected value in our proposed method with these alternate objectives.\n3. See discussion on ETC-Ada in Weakness 3.\n\nWe hope the clarifications above can improve your opinion of our work."}]

Author rebuttal:

Meta-review: This manuscript introduces an interesting twist on the types of problems typically considered in Bayesian optimization wherein the experimenter may choose to fix a chosen subset of the input variables -- for a cost that depends on the subset chosen -- with the remaining variables being sampled randomly. The authors provide a UCB-style algorithm for this setting and an accompanying regret bound.

The reviewers universally agreed that this setting and the presented algorithm and analysis were of interest to the NeurIPS community, and that the developments in this manuscript are correct and were presented clearly. On this basis, it would be a valuable addition to the conference program.

The response and discussion period proved useful in clarifying some issues, and I strongly recommend that the authors take this discussion into account while updating their manuscript.
Decision: Accept (poster)