Batch Bayesian Optimization For Replicable Experimental Design
Authors: Zhongxiang Dai
Quoc Phong Nguyen
Sebastian Shenghong Tay
Daisuke Urano
Richalynn Leong
Bryan Kian Hsiang Low
Patrick Jaillet
Venue: NeurIPS 2023 poster (2023)
Keywords: Bayesian optimization
Gaussian processes
AI4Science
TL;DR: Our methods, aimed at experimental design problems with (a) batch evaluations and (b) large and heterogeneous noise, adaptively assign more replications to an input with a larger noise variance and is theoretically grounded and practically effective.

Abstract: Many real-world experimental design problems (a) evaluate multiple experimental conditions in parallel and (b) replicate each condition multiple times due to large and heteroscedastic observation noise. Given a fixed total budget, this naturally induces a trade-off between evaluating more unique conditions while replicating each of them fewer times vs. evaluating fewer unique conditions and replicating each more times. Moreover, in these problems, practitioners may be risk-averse and hence prefer an input with both good average performance and small variability. To tackle both challenges, we propose the Batch Thompson Sampling for Replicable Experimental Design (BTS-RED) framework, which encompasses three algorithms. Our BTS-RED-Known and BTS-RED-Unknown algorithms, for, respectively, known and unknown noise variance, choose the number of replications adaptively rather than deterministically such that an input with a larger noise variance is replicated more times. As a result, despite the noise heteroscedasticity, both algorithms enjoy a theoretical guarantee and are asymptotically no-regret. Our Mean-Var-BTS-RED algorithm aims at risk-averse optimization and is also asymptotically no-regret. We also show the effectiveness of our algorithms in two practical real-world applications: precision agriculture and AutoML.

Batch Bayesian Optimization for Replicable Experimental Design
Zhongxiang Dai', Quoc Phong Nguyen', Sebastian Shenghong Tay
Daisuke Urano Richalynn Leong', Bryan Kian Hsiang Low*, Patrick Jaillet
*Department of Computer Science, National University of Singapore
LIDS and $EECS, Massachusetts Institute of Technology IInstittee for Infocomm Research (I2R), A*STAR, Singapore
Temasek Life Sciences Laboratory, Singapore dzxčnus edu. sg, qphongmp@gmail. com, sebastian. tayču eayeu.nus.ee nus,edu,
{daisuke, richalyun)@t11. org.gg, lowkh@comp.. nus edu..g..gg adu.sg, jaillet@mit.ed
Abstract
Many real-world experimental design problems (a) evaluate multiple experimental conditions parallel and (b) replicate each condition multiple times due large and heteroscedastic observation noise. Given fixed total budget, this naturally induces trade-off between evaluating more unique conditions while replicating each of them fewer times vs. evaluating fewer unique conditions and replicating each more times. Moreover, in these problems, practitioners may be risk-averse and hence prefer an input with both good average performance and small vari- ability. To tackle both challenges, we propose the Batch Thompson Sampling for Replicable Experimental Design (BTS-REC RED) framework, which encompasses three algorithms. Our SIS-RED-Knows and STS-RED-UUknowI algorithms, for, respectively, known and unknown noise variance, choose the number of replica- tions adaptively rather than deterministically such that an input with a larger noise variance is replicated more times. As result, despite the noise heteroscedasticity, both algorithms enjoy a theoretical guarantee and are asymptotically no-regret. Our Mean-Var- -a-------------- algorithm aims risk-averse optimization and is also asymptotically no-regret. We also show the effectiveness of our algorithms in two practical real-world applications: precision agriculture and AutoML.
1 Introduction
Bayesian optimization (BO), which is sequential algorithm for optimizing black-box and expensive- to-evaluate functions [14 15), has found application in a wide range of experimental design prob- lems [2T] Many such applications which use BO to accelerate the scientific discovery process 27 fall under the umbrella of AI for science (Al4Science). Many real-world experimental design problems, such as precision agriculture, share two inherent characteristics: (a) multiple experimental conditions are usually evaluated parallel to take full advantage of the available experimental budget; (b) the evaluation of every experimental condition is usually replicated multiple times 31 because
every experiment may be associated with a large and heteroscedastic (i.e., input-dependent) obser- vation noise, in which case replication usually leads to better performances 22 33 43 Replicating each evaluated experimental condition also natural choice experimental design problems in which it incurs considerable setup costs to test every new experimental condition. This naturally induces an interesting challenge regarding the trade-off between input selection and replication: in every iteration of BO where are given fixed total experimental budget, should we evaluate more unique experimental conditions and replicate each of them fewer times or evaluate fewer unique conditions and replicate each more times? Interestingly, this trade-off is also commonly found in
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

other upplications such as automated machine learning (AutoML), in which parallel evaluations are often adopted to exploit all available resources (2]] and heteroscedasticity a prevalent issue [[2]. Furthermore, these experimental design problems with large and heteroxcedastic noise are often faced with another recurring challenge: instead of an input experimental condition (e.g., a hyperparameter configuration for an MI. model) that produces good performance (e.g.. large validation accuracy) on average, some practitioners may be risk-averse and instead prefer an input that both yields good average performance and has small variability. As result, instead of only maximizing the mean of the black-box function, these risk-averse practitioners may instead look for inputs with both large mean function value and small noise variance 226 33
In this work, we provide solutions to both challenges in a principled way by proposing the framework of Batch Thompson Sampling for Replicable Experimental Design (BTS-RED) The first challenge regarding the trade-off between input selection and replication is tackled by the first two incarnations of our framework: the which are applicable to scenarios where the noise variance function is known or unknown, respectively. For batch selection, we adopt the Thompson sampling (TS) strategy because its inherent randomness makes it particularly simple to select a batch of inputs (28). Moreover, previous works on BO have shown that the use of TS both allows for the derivation of theoretical guarantees 16 28 and leads to
(Sec. I.T) and BTS-RED- REDD-Unnnownn (Sec. (32)) algorithms,
strong empirical performances [6 20). For replication selection, instead of the common practice of replicating every queried input fixed number of times, we choose the number of replications adaptively depending on the observation noise. Specifically, in every iteration, both algorithms repeat the following two steps until the total budget is exhausted: (a) choose an input query following the TS strategy, and then (b) adaptively choose the number of replications for the selected input such that an input with a larger noise variance is replicated more times. Of note, in spite of the noise heteroscedasticity, our principled approach to choosing the number of replications ensures that the effective noise variance R2 of every queried input is the same (Sec. 3.1.. This allows us to derive an upper bound on their cumulative regret and show that they are asymptotically no- regret. Our theoretical guarantee formalizes the impact of the properties of the experiments, i.e., our regret upper bound becomes better if the total budget is increased or if the overall noise level is reduced. Importantly, our theoretical result provides a guideline on the choice of the effective noise variance parameter R², which is achieved by minimizing the regret upper bound and allows R² to automatically adapt to the budgets and noise levels of different experiments (Sec. 3.1.2).
To handle the second challenge of risk-averse optimization, we propose the third variant of our (Sec.E) which is natural extension of BTS- aims to maximize the verannvriannce objective function, which weighted combination of the mean objective function and negative noise variance function (Sec. 2). We prove an upper bound on the mean-variance cumulative regret of (Sec. and show that it also asymptotically no-regret.
BTS-RED framework named Mean-Var-BTT RED-Unknown. Saan-Var-BT--RR
In addition to our theoretical contributions, we also demonstrate the practical efficacy of our algo- rithms in two real-world problems (Sec. 5). Firstly, in real-world precision agriculture experiments, plant biologists usually (a) evaluate multiple growing conditions in parallel, and (b) replicate each condition multiple times to get a reliable outcome (1 Moreover, plant biologists often prefer more replicable conditions, i.e., inputs with small noise variances. This is hence an ideal application for our algorithms. So, we conduct an experiment using real-world data on plant growths, to show the effectiveness of our algorithms in precision agriculture (Sec. 5.2).. Next, we also apply our algorithms to AutoML to find hyperparameter configuran configurations with competitive and reproducible results across different AutoML tasks (Sec. 5.3). The efficacy of our algorithms demonstrates their capability to improve the reproducibility of AutoML tasks which is an important issue in AutoML 225
2 Background
We denote by f X' + R the objective function we wish to maximize, and by 0² X IR+ the input-dependent noise variance function. We denote the minimum and maximum noise variance as o and 2 For simplicity, we assume that the domain X' is finite, since extension to compact domains can be easily achieved via suitable discretizations [5). After querying an input æ E X,
we observe a noisy output y = f(x) + e where e ~ A/ o² (x)). In every iteration f, we select
a batch of b. 2 inputs (a, (z("²) b........, and query every xt
(b) with n, 2 parallel processes.
We denote the total budget B such that Σhe mi < BB Vt 2 1. We model the function f
2

---

(P(p(-), ((.)),)((-)))) where p¹-) is mean function which we assume w.l.o.g. p(z) and k(-:)) is a kernel function for which we focus on the commonly used squared exponential (SE) kernel. In iteration I, we use the observation history in the first t iterations (batches) to calculate the GP posterior (P o ():)),
using Gaussian process (GP) 40
)), in which (4-1(-) and (f-)(-,)) represent the GP posterior mean and covariance functions (details Appendix Aj. For STS-RED-UnKnowd and Varn--Va-BTS--aa denoted as GP', to model -o² (Sec. 3.2 and denote its posterior as GP (1)-1())
(i.e., when (-) unknown), we use another GP,
In our theoretical analysis of BTS-RED-Knonnn f. we follow previous works on batch BO
where we aim to maximize I 18 35 and derive an upper bound on the batch
and PITS-RRE-Unknoon
Ma (6) }. in which x² arg = S (ar and we have used [bx] to denote (1.....b) by We show (Sec. B that both BTS-RED KnoDn and BTS-RED
cumulative regret Ry Σi= Et=miinng minog]o.)
Unknown enjoy a sub-linear upper bound on Rr. which suggests that as increases, a global optimum xx is guaranteed to be queried since the batch simple regret ST min min [f("))
)a < RT goes to O asymptotically. We analyze the batch cumulative regret because it allows us to show the benefit of batch evaluations, and our analysis can also be modified to give an upper on the sequential cumulative regret of RT- = - Ei=lf(("') - f(= (Appendix DJ Our Mean- Bara-Va--BTS-RE.. aims to maximize the mean-variance objective function (x)) (x)
(1- (x) = (xr) + (1 w)g(2), in which we have defined g(ar) - -o² Vo E X. The user-specified weight parameter E [0, 1] reflects our relative preference for larger mean function values or smaller noise variances. Define the mean- variance batch cumulative regret as RAY Σ minsg[be] (x=") haw (xx(") where x E arg h We also prove sub-linear upper bound on RNY for Mean-Var-BTe Var-BTS-RED (Sec. 4b.
3 BTS-RED-Known and BTS-RED-Unknown
Here, we firstly introduce ETS-RED-KON and its theoretical guarantees (Sec. 3.1 1. and then discuss how it can be extended to derive MED-Unknown (Sec. 3.2).
3.1 BTS-RED with Known Noise Variance Function
3.1.1 BTS-RED-Known
Algorithm BBTS-RED-KMnn
1: for L 1,2,....... ..., T do
2: b= 0. (0)
3: while Σt= nz < IB do
(8))
4:
b b- 6-b11 b+1
5: Sample function 1 from the GP posterior of (P 1 (),8oo (Sec. 2
6: Choose xz
arg max (b) (x) and ni (b) = (x (b)
1/122
7:
be = b
8: for E
a. (b) with ne (b) parallel processes
9: for E observe (v1)) ne( Calculate their empirical mean y (1/m(()
Σ En Ve.
(0)
10: Use (<x(") (b) v( JoETA to update posterior of GP
BTS-RED-Known (Algo. assumes that o²(-) known. In every iteration sequentially select every 2t and its corresponding ni we repeat the following process until the total number of replications has consumed the total budget TB (i.e., until Eb ne 2 BB, line 3 of Algo.
line 5: sample function f((") from GP(p) (8o (8, will be defined in Theorem 3.1
line 6: choose ab(") arg max (1.) (xx) by maximizing the sampled function p! and choose
n (b) = - (²) R2, where [-1 is the ceiling operator and R² is the effective noise variance. After the entire batch of b, inputs have been selected, every xx!) is queried with n! parallel
(8) (b) of these n, observations is calculated (line 9).
processes (line 8), and the empirical mean y/
3

---

)oE(b,) are used to update the posterior of GP (line 10). Of note, since the observation noise is assumed to be Gaussian-distne distributed with variance of (x) (Sec. after querying z.{) independently for ni
Finally, {(a)",, "("
(
(b) follows Gaussian distribution (b) times, the empirical mean y/
(h) by ni (h) = [o²(<)"))) ) (line 6). with noise variance (<x=""))"""" Next, since we select n4
guaranteed to be upper-bounder by R In other words, every observed empirical (a (b) /mb )/m,
mean (b) follows Gaussian distribution with a noise variance that is upper-bounded by the effective noise variance R², This is crucial for our theoretical analysis since it ensures that the effective noise variance is SassubGGussian and thus preserves the validity of the GP-based confidence bound [8].
In practice, since BTS RTS--RE--EE Known algorithm only aims to maximize the objective function (i.e., we are not concerned about learning the noise variance function), some replications may be wasted on undesirable input queries (i.e., those with small values of f (a=)) especially in the initial stage when our algorithm favours exploration. To take this into account, we adopt a simple heuristie: we impose maximum number of replications denoted as Timax and set Ammax IB/2 in the first T/2 iterations and maax = B afterwards. This corresponds to favouring exploration of more inputs (each with less replications) initially and preferring exploitation in later stages. This technique also used for BTS-RED- -UnD-nnn (Sec. 3.2) yet not adopted for Mean-Var-Ba -T---TTD-DDDDD (Sec. 4 since in mean-variame optimization, we also aim learn (and minimize) the noise variance function.
Due to our stopping criterion for batch selection (line 3), in practice, some budgets may be unused in iteration. E.g., when IB 50, if 26-1 =1 n4
(b') 43 after the first b - 1 selected queries and
the newly selected ny for the 6th query æ; is n2 (b) = 12, then the termination criterion is met (i.c., 74 (b') 2 B) and only 43/50 of the budgets are used. So, we adopt simple technique: in the example above, firstly evaluate the last selected xz!) for 7 times, and in the next iteration t + 1,
(6)
_
we start by completing the unfinished evaluation of (b) by allocating 12 - 7 = replications to x; (b) Next, we run iteration + with the remaining budget, i..., we let B 50 - 5 = 45 in iteration + 1.
3.1.2 Theoretical Analysis of BTS-RED-KnOwH
Following the common practice in BO (8), assume f lies in reproducing kernel Hilbert space (RKHS) induced by an SE kernel k: || Ht, < B for some B > O where ||-1| denotes the RKHS norm. Theorem 3.1 below gives a regret upper bound of BTS-RED-Known (proof in Appendix B).
Theorem 3.1 (BTS-RED-
Choose 8 (0. Define TL-1 & Ei= by, and define 3, é B / + +1+ log(2/8)) where Te.., denotes the maximum information gain about I from any T observations. With probability of at least 1 - 5 (Ö ignores all log factors),
R =r=((c R2/ [B/
T R² - 1)) VTTBEVC + vTrs))
C' is constant s.f. max ACX,|A|SEB II (A:VA & I IJ: is the informa- tion gain from observations A at inputs A, given observations y1a-- in the first t iterations.
has been shown by [19 that by running uncertainty sampling (i.e., choosing the initial in- puts by sequentially maximizing the GP posterior variance) as the initialization phase for finite number (independent of 2) of iterations, C' can be chosen to be a constant indepen- dent of B and T. As result, the regret upper bound from Theorem 3.1 can be simplified
into Rr Ō(V R2 (B/
22
mux 1)/TTr3(1 vTrs)). Therefore, for the SE kernel for R
which 1773 = (log d (TB)), our regret upper bound is sub-linear, which indicates that our BTS-RED- RE---RDD--onn is asymptotically no-regret. Moreover, the benefit of a larger total budget is also reflected from our regret upper bound since it depends on the total budget B via (logg*+(TT + log (d+1)/2 (2g(4+ /VB. which is decreasing as the total budget |B increases. In addition, the regret upper bound is decreased if o becomes smaller, which implies that the per- formance of our algorithm is improved if the overall noise level is reduced. Therefore, Theorem 3.] formalizes the impacts of the experimental properties (i.e., the total budget and the overall noise level) on the performance of BTS-REID ----RED--EE RED-REDD-ON.... Known.
Homoscedastic Noise. In the special case of homoscedastic noise, i.e., 0²(x) a Yx E X, then n, To R22 Reonst and b, [[B/Tcooss]] bo. Vt E [T]. That is, our algorithm reduces

---

to standard (synchronous) batch TS proposed in (28 where the batch size is bu and every query is replicated Reconst times. In this case, the regret upper bound becomes: Rt O J
bba TT.
(Trw,) (Appendix B.1
Theoretical Guideline on the Choice of R Theorem 3.1 also provides an interesting insight on the choice of the effective noise variance R². In particular. our regret upper bound depends By taking the derivative of this term w.r.t. 11,, we have shown (Appendix C that the value of R² that minimizes this term is obtained at R² = maxx (VB + 1)/(B- 1). In other words, R² should be chosen as fraction of o (assuming s.t. (vB B + I) -) 1) < 1). In this case, increasing the total budget naturally encourages more replications. Specifically, increasing B reduces (vB + L) - 1) and hence decreases the value of R2, which consequently encourages the use of larger ny 's (line 6 of Algo. [L) and allows every selected input to be replicated more times. For example, when the total budget is IB = 16, R? should be chosen R² o /iaxs/ when I8 100, then we have R o maxx /9. We will follow this theory-inspired choice of R in our experiments in Sec. 5 (with slight modifications).
on R2 through the term v R² [B/ (B/BBB/ooa (o R + 1)
Improvement over Uniform Sample Allocation. For the naive baseline of uniform sample allocation (i.e., replicating every input a fixed number no S B of times), the resulting effective observation noise would be (a (oo) / -uuu-Gassssan. This would result in a regret upper bound which can be
obtained by replacing the term (B/ p
1) (Theorem 3.1 1 by F Vno (for simplicity,
we have ignored the non-integer conditions, i.e., the ceiling operators). Also note that with our optimal
choice of R22 (the paragraph above), it can be easily verified that the term v (B/
Cau 1)
(Theorem 3.1 can be simplified to Tmax/ VB. Therefore, given that no S B, our regret upper bound (with the scaling of maxx VB) is guaranteed to be no worse than that of uniform sample allocation (with the scaling of maxx/ V T2a)-
3.2 RTS-RED with Unknown Noise Variance Function
Here we consider the more common scenario where the noise variance function o²()) is unknown by extending RED-Known while preserving its theoretical guarantee.
3.2.1 Modeling of Noise Variance Function
We use a separate GP (denoted as GP') to model the negative noise variance function g-) -0--022 (-)
and use it to build a bessh--bbbbblity upper bound U. (-) on the noise variance function 0-(-) After this, we can modify the criteria for selecting m! (i.e., line 6 of Algo. to be n
[0
(a) (b) //R²
which ensures that Up? (ax") //m (²) I RR. As a result, the condition of ax (b) satisfied (with high probability), which implies that the observed empirical mean every queried at is still R- sub- Gaussian (Sec. 3. and theoretical guarantee of Theorem 3.1 is preserved. To
//m I R2 still
(b)
(6)
construct gP', we use the (negated) unbiased empirical noise variance ((b) as the noisy observation:
glth -1/(nn 1)
Σ m==1
(b) (vi.n ye 10 g(x; +
(1)
where g( (b)) -
is the negative noise variance at (h) and e' is the noise. In BTS-RED- Unknown, we use pairs of {xx
(x) (b)
} to update the posterior of GP'. We impose a minimum number of replications Temin 2 2 for every queried input to ensure reliable estimations of ((
(b) (()))
3.2.2 Upper Bound on Noise Variance Function
Assumptions. Similar to Theorem 3.1 we assume that g lies an RKHS associated with an SE
kerne& k &':1|||] < B' for some B' > O, which intuitively assumes that the (negative) noise variance
'To simplify the derivations, we have replaced the term Tonnx// R²) by its upper bound / R²² + 1, after which the resulting regret upper bound is still valid.
2 "Here we have modeled (-) (instead of log (+)) as done by some previous works) because it allows us to naturally derive our theoretical guarantees, and as we show in our experiments (Sec.5). it indeed allows our algorithms to achieve compelling empirical performances. We will explore modelling log o (²) in future work see if it leads further empirical performance gains.
5

---

varies smoothly across the domain X. We also assume that the noise é' is --su-uuuusssnnnn and justify this below by showing that e' is bounded (with high probability).
is R' RR-sub-Gaussian. Since the empirical variance of a Gaussian distribution ① follows a Chi- squared distribution, probability of 2 1 a, é' is bounded within [ Ua]. where La = m (x (imin-1,a// (Main
can use the concentration of Chi-squared distributions to show that with
1) 1),
(x -,, 1...--1./// (Meinn - 1) 1). Here x² X denotes 17th -quantie of the (Mein
Chi-squared distribution with Amin - degrees of freedom (1) = a/2 or 1 - a -x/2). By choosing = 6/(4B) (ō is from Theorem 3.1) we can ensure that with probability of 2
8/4, e' is bounded within aL Ua] for all ";; In other words, with probability of 2 1 - 5/4, the noise e' in ① zero-mean and bounded within [L,, U. which indicates that é' is -lssub-Gaussian with R' (Un La) /22. More details are given in Appendix E Note that the value of It' derived here is expected to be overly pessimistic, so, we expect smaller values of R' to be applicable in practice.
Upper Bound Construction. With the assumptions of 1f - B' and é' is R' Gaussaan we can construct the upper bound U?? (-). Denote by - the maximum information gain about from any T--1 -ra by observations, define 8 a B' R² v /2(T + 1 + log(4/))). and represent the GP posterior mean and standard deviation for GP' as p1-1()) and o-). Then we have that (x) - ((x) S (z)) E
E
[T]
with probability of 2 1 - 5/2.. The error probabilities come from applying Theorem 2 of [ (6/4) and assuming that is -aausuaGa (6/4). This implies that -x) = g(x) 2 14-1 (x)
(2), and hence o² (xx) S -1411 (a) + 8, (2x), Va E X. E [T]. Therefore, we can choose the upper bound on the noise variance (Sec. 3.2.1 as Up (a) -14-1(0) + (ar)
BTS-RED-Unknown Algorithm. To summarize, we can obtain DIS-REE--UknnowE (Algo. Ap-
pendix by modifying the selection criterion of nh (line 6 of Algo. to be ni = [(- (x;
( RR.. As a result, BTS BEED-nnnowW enjoys the same regret upper bound as Theo- rem 3.1 (after replacing 8 in Theorem 3.1 by 5/2). Intuitively, using an upper bound U?." (zx in the selection of n4 implies that if we are uncertain about the noise variance at some input location x;
3,
(i.e., if (x= is large), choose to be conservative and use large number of replications n,,
Mean- Van- Var-BTT-RED
We extend BTS-RED Unknown (Sec. 3.2) to maximize the mean-variance objective function: hww (x) = wx(x) (1 (z) to introduce Mean-Var-BTT Var-BTS-RED (Algo. 2 In contrast to BTS
(b)
Mean-Vart Bur-BBS-RRE chooses every input query z by maximizing the
weighted combination of two functions sampled from, respectively, the posteriors of GP and GP' (lines 5-6 of Algo. (2). while n. is chosen (line 7 of Algo. 2 in the same way as This naturally induces a preference for inputs with both large values of f and small values of o²), and hence allows us to derive an upper bound on RMY (proof in Appendix G
Theorem 4.1 (Mean- Var- -a--).-- With probability of at least 6,
RMY (
VT
wR WRyTTe(VTTs + vO) + (1- W) V VT T voi)).
B/
C' is constant s.t. max maX y
C, MAXACx ( S
Note that I' and T' may differ since the SE kernels k and k', which are used model and g respectively, may be different. Similar to Theorem 3.I if we run uncertainty sampling for a finite number (independent of T) of initial iterations using either ie or ke' (depending on whose lengthscale is smaller), then C' can be chosen to be a constant independent of IB and T. Refer to Lemma G.6 G for more details. As a result, the regret upper bound in Theorem 4. also sub-linear since both ho and k are SE kernels and hence Trg- = Olog d+1 (T)) and Frg = (log"+1 ( (T)). The regret upper bound can be viewed as a weighted combination of the regrets associated with f and g. Intuitively, if w larger (i.e., if we place more emphasis on maximizing f than g), then a larger proportion of the regrets is incurred due to our attempt to maximize the function f.
(Appendix

---

Algorithm 2 Mean-Var-BTS--RR Var-BTS-ED...
1: for t 1,,,..... do
2: b= 0=0,m 0. (0)
3: while Σ "
(6')
<
IB do
4:
b - b+1
Sample f(()) from GP(M (f, (1
and gi from gP' (p 36 o 0f o
5:
(b)
arg max NEN W (a) (1 w)g (6) (x)]
6:
7:
nt
(b) (-H4-
(z0 ))/R R)
8:
b =
for E [be]. query xi with n4 (b) parallel processes
9:
for b [be], observe ( " Calculate their mean y ( and (negated) variance (M)
10:
Use ((x) (b) Ve (0)) ) [oE())) to update posterior gP, ((x, V. )e(t)) to update posterior GP
11:
5 Experiments
For BTS-RED-Known and BTS-RED--nKnowN which only aim to maximize the objective function f. we set Rmax - IB/2 in the first 7/2 iterations and mmmx - B subsequently (see Sec. 3.1.1 for more details), and set 7amax IB in all iterations for Mean- Var-BTS Ton-BTS-REDD We set ru unless specified otherwise, however, it is recommended to make Amni larger in experiments where the overall noise variance is large (e.g., we let Remin 5 in Sec. (.2).. We use random search select the initial inputs instead of the uncertainty sampling initialization method indicated by our theoretical results (Sec. 3.1.2) because previous work [28] and our empirical results show that they lead to similar performances (Fig. 8 in App.
H.1 We choose the effective noise variance R² by following our
theoretical guideline in Sec. 3.1.2 i.e., R22 o (V / (B-1) 1) which minimizes the regret upper bound in Theorem 3.1 5
However, in practice, this choice may not optimal because we derived it by minimizing upper bound which is potentially loose (e.g.. we have ignored all log factors).
So, we introduce tunable parameter > 0 and choose R² R Ro? (VB 1)/(BB 1). As result, we both enjoy the flexibility of tuning our preference for the overall number of replications (i.e., a smaller x leads to larger n, 's in general) and preserve the ability to automatically adapt to the total budget (via IB) and the overall noise level (via max)) When the noise variance unknown (i.e., of is unknown), and update our approximation after every iteration. To demonstrate the robustness of our methods, only use two values of 0.2 and 0.3 in all experiments. Of note, methods with k == 0.3 perform the best in almost all experiments (i.e., green curves in all figures), and k = 0.2 also consistently performs well.
approximate omax by the maximum observed empirical noise variance
32 35 we plot the (batch) simple regret or the best observed function value up to an iteration. In all experiments, we compare with the most natural baseline of batch TS with fixed number of replications. For mean optimization problems (i.e., maximize f), also compare with standard sequential BO algorithms such GP-UCB and GP-TS, but they are sigmificantly outperformed by both our algorithms and batch TS which are able to exploit batch evaluations (Secs. [. and (5.2). Therefore, achieve comparable performances to our algorithms due to their inability to exploit batch evaluations. For mean-variance optimization, we additionally compare with the recently introduced Risk-Averse Heteroscedastic BO (RAHBO) (3 (Sec. (6), which is the state-of-the-an method for risk-averse BO with replications. Some experimental details postponed Appendix H
Following the common practice of BO II 20 28
do not expect existing sequential algorithms to
5.1 Synthetic Experiments
We sample two functions from two different GPs with the SE kernel (defined on discrete 1-D domain within [o, 1)) and use them as f(-) and (-), respectively. We use B = 50.
Mean Optimization. The mean and noise variance functions used here are visualized in Fig. Th. This synthetic experiment is used to simulate real-world scenarios where practitioners are risk-neutral and hence only aim to select input with large mean function value. After every iteration (batch) an
For simplicity, we also follow this guideline from Sec. 3.1.2 choose H²² for Mean- Var BE---TS-RRE
7

---

Pake Sieker 6,00
0,15
10
0.5
2.044
Rata TE 31
0.4
2.30
0.
0.1
0.7
0.0
0.3
0.2
0.5
0.0
2.00
20
0.0
60 Berations
Input
(d) Figure 1: (a) Synthetic function for mean optimization (Sec. 5.1 (b) Average number of replications
(a)
(b)
c
n4 for WTS-RED-Unknown. Results for (c) mean and (d) mean-variance optimization.
algorithm reports the selected input with the largest empirical mean from its observation history, and we evaluate the simple regret at iteration f as the difference between the objective function values at the global maximum x: and at the reported input. To demonstrate the consistency of our performance, we also tested an alternative reporting criteria which reports the input with the larger LCB value in every iteration, and the results (Fig. 7p in Appendix(H.]] IH.T) are consistent with our main results (Fig. (Fi Fig. Dp plots the average ne (vertical axis) chosen by (horizontal axis), which shows that larger nt'S 's are selected for inputs with larger noise variances in general and that smaller 0.2 indeed increases our preference for larger n4 s.
BEDD-Unknown for every queried input
The results (simple regrets) are shown Fig. De. As can be seen from the figure, for Batch TS with a fixed ny, smaller values of n, such as ne = 5 usually lead to faster convergence initially due to the ability to quickly explore more unique inputs, however, their performances deteriorate significantly in the long run due to inaccurate estimations; in contrast, larger n, 's such as n4 = 20 result in slower convergence initially yet lead better performances (than small fixed n, 's) in later stages. Of note, Batch TS with n, = 1 (gray curve) represents standard batch TS (IB 50) without replications (28). which underperforms significantly and hence highlights the importance of replications in experiments with large noise variance. Moreover, our BTS-RED-KE
(especially with x = 0.3) consistently outperform Batch TS with fixed nt, We also demonstrate our robustness against in this experiment by showing that our performances are consistent for wide range of k's (Fig. 7 1 in App. H. In addition, we show that sequential BO algorithms (i.c., GP-TS, GP-UCB, and GP-UCB with heteroscedastic GP) which cannot exploit batch evaluations fail to achieve comparable performances to batch TS, RTS-RED and
and TTSSRRE-UUnKee
(Fig. 5 in App. H.I.
Mean-variance Optimization. Here we evaluate our Mean- Var--Va-BTTSS BTS-RED. We simulate this scenario with the synthetic function in Fig. 66 (App.HH.I). for which the global maximums of the mean and mean-variance (w = 0.3) objective functions are different (Fig.[6)) After every iteration (batch) t, we report the selected input with the largest empirical mean-variance value (i.e., weighted combination of the empirical mean and variance), and evaluate the mean-variance simple regret at iteration / as the difference between the values of the mean-variance objective function hhw at the the global maximum a and at the reported input. The results (Fig, Dtt) show that our Mcan- Var-BTS -i---BT--RDDD REDD (again especially with x = 0.3) outperforms other baselines. Since RAHBO is sequential and uses a fixed number of replications, we use B 50 replications for every query for a fair comparison. RAHBO underperforms here which is likely due to its inability to leverage batch evaluations.
5.2
Rorldworld Experiments on Precision Agriculture
Plant biologists often need to optimize the growing conditions of plants (e.g., the amount of different nutrients) to increase their yield. The common practice of manually tuning one nutrient a time is considerably inefficient and hence calls for the use of the sample-efficient method of BO. Unfortu- nately, plant growths are usually (a) time-consuming and (b) associated with large and heteroscedastic noise. So, according to plant biologists, in real lab experiments, (a) multiple growing conditions are usually tested in parallel and (b) every condition is replicated multiple times to get reliable outcome [31]. This naturally induces a trade-off' between evaluating more unigue growing conditions vs. replicating every condition more times, and is hence an ideal application for our algorithms. We tune the pH value (in [2.5, 6.5l) and ammonium concentration (denoted as NH3, in (0, 30000) uM). in order to maximize the leaf area and minimize the tipburn area after harvest. We perform real lab experiments using the input conditions from a regular grid within the 2-D domain, and then use the collected data to learn two separate heteroscedastic GPs for, respectively, leaf area and tipburn area. Each learned GP can output the predicted mean and variance (for leaf area or tipburn area) at every input in the 2-D domain, and can hence be used as the groundtruth mean f(.) and noise variance (-) functions. We perform two sets of experiments, with the goal of maximizing (a) the
8

---

142
117
140
Bath
130
106
20
45
50
100
20
60
ab
10
40
10
100
60
50
100
(b)
(c)
(d)
Figure 2: (a) Mean and (b) mean-variance optimization for the leaf area. (c) Mean and (d) mean- variance optimization for the weighted combination of leaf area and negative tipburn area.
0:03
0:10
0.02
0.04
0.0
0/01g
(c)
(d)
Figure 3: (a) Mean and (b) noise variance functions for leaf area, with some selected queries (stars) and their ne s. (c) Mean and (d) mean-variance optimization for hyper. tuning of SVM (Sec. 5.3).
leaf area and (b) weighted combination of the leaf area (x0.8) and negative tipbur area (x0.2). For both experiments, we run BTS-RED-Unknown and Mean- Var-BTS-RED to maximize the mean and mean-variance objectives (w 0.975), respectively. We set B 50, 7mmin 5 and 7mmax 50.
Fig. 2 shows the results for maximizing the Icaf area (a.b) and weighted combination of leaf area and negative tipburn area (c.d). Our STS-RED-Unknown and Mcan- Var- ------T--RDDD RED with k 0.2 and κ 0.3 consistently outperform Batch TS, as well as RAHBO in Figs. 22p and d. For mean optimization, we also compare with sequential BO methods (Fig. TO in Appendix (H.2), which again are unable to perform comparably with other algorithms that exploit batch evaluations. Figs.3j. and b visualize the groundtruth of some queried inputs (the selected inputs after every 4 iterations) and their corresponding n, 's. Similarly, Figs. Da and b (Appendix H.2 show the queried inputs and the n4 's of Mean-Var-BTTS
and noise variance functions for the leaf area, including the locations
(w = 0.975). illustrated on heat maps of the mean-variance objective (a) and noise variance functions (b). These figures demonstrate that most of our input queries fall into regions with large (either mean or mean-variance
objective function values (Figs. 3 and (h) and that 71 is in general larger at those input locations with larger noise variance (Figs. Bp and 9p). We have included GIF animations for Figs. and 9 in the supplementary material. Our results here showcase the capability of our algorithms to improve the efficiency of
experimental design problems.
5.3 Real-World Experiments on AutoML
Reproducibility is an important desiderata in AutoML problems such as hyperparameter tuning 25 because the performance of hyperparameter configuration may vary due to number of factors such as different datasets, parameter initializations, etc. For example, some practitioners may prefer hyperparameter configurations that consistently produce well-performing ML models for different datasets. We adopt the EMNIST dataset which is widely used in multi-task learning [00 [5] EMNIST consists of images of hand-written characters from different individuals, and each individual corresponds to a separate image classification task. Here we tune two SVM hyperparameters: the penalty and RBF kernel parameters, both within [0.0001,2] 2). We firstly construct a uniform 2-D grid of the two hycprparameters and then evaluate every input on the grid using 100 tasks (i.c., image classification for 100 different individuals) to record the observed mean and variance as the groundtruth mean and variance. Refer to Figs. Th. b and (Appendix H.3) for the constructed mean, variance and mean-variance (w = 0.2) functions. Fig. 33 and plot the results (B = 50) for mean (c) and mean- variance (d) optimization. Our ITT--RED-LUE Unknown and Mean- Mean-VVr-Bel BTS-RED with both = 0.2 and 0.3 perform competitively (again especially x = 0.3), which shows their potential to improve the efficiency and reproducibility of AutoMI. RAHBO underperforms significantly (hence omitted from Fig. (1). which likely due to the small noise variance (Fig. (Tb) which favors methods with small n2's 's. Specifically,, methods with small n2 's can obtain reliable estimations (due to small

---

noise variance) while enjoying the advantage of evaluating a large number b, of unique inputs in every iteration. This makes RAHBO unfavorable since it a sequential algorithm with b, = 1.
Experiments Using Different Budgets TB. Here we test the performances of our algorithms with different budgets (i.e., different from the IB = 50 used in the main experiments above) using the AutoML experiment. The results (Fig. 12 in App. H.3 show that the performance advantages of our algorithms (again especially with K 0.3) are still consistent with larger or smaller budget.
Additional Experiments with Bigeer-Dimmnsional Inputs. To further verify the practicality of our proposed algorithms, here adopt two additional experiments with dimensiimenii continuous input domains. Specifically, we tune = 12 and d = 14 parameters of a controller for a Lunar- Lander task and robot pushing task. respectively, and both experiments have widely used by previous works on high-dimensional BO 16 20 (more details in App.(H.4) In both experiments, the heteroscedastic noises arise from random environemntal factors. The results (Fig. 13 in App. (H.4) show that algorithms, again especially with A = 0.3, still consistently achieve compelling performances.
6 Related Works
The work of 28 proposed a simple batch TS method by exploiting the inherent randomness of TS. Interestingly, as we discussed in Sec. 3.1.2] the method from [28] is equivalent to a reduced version of our BTS- RED-Known with homoscedastic noise, and our Theorem 3.1 provides a theoretical guarantee on its frequentist regret (in contrast to the Bayesian regret analyzed in (28). The work of 2 aimed to adaptively choose whether to explore new query or to replicate a previous query. However, their method requires additional heuristic techniques to achieve replications and hence has no theoretical guarantees, in stark contrast to our simple and principled way for replication selection (Sec. 3). Moreover, their method does not support batch evaluations, and is unable to tackle risk- averse optimization. Recently, [43] proposed to select a batch of queries while balancing exploring new queries and replicating existing ones. However, unlike our simple and principled algorithms, their method requires complicated heuristic procedures for query/replication selection and batch construction, and hence does not have theoretical guarantees. Moreover, their method also only focuses on standard mean optimization and cannot be easily extended for risk-averse optimization.
BO has been extended to the batch setting in recent years 19
38
47
The work of 23 used heteroscedastic GP [29] the surrogate model for risk-averse optimization. 36 37, considered risk-averse BO, however, these works require the ability to observe and select an environmental variable, which usually either not explicitly defined or uncontrollable in practice (e.g., our experiments in Sec. 5.. The recent work of (33] modified BO to maximize the mean-variance objective and derived theoretical guarantees using results from (30). Their method uses a heteroscedastic GP as the surrogate model and employs another (homoscedastic) GP model the observation noise variance, in which the second GP is learned by replicating every query for a fixed predetermined number of times. Importantly, all of these works on risk-averse BO have focused only on the sequential setting without support for batch evaluations. Replicating the selected inputs in BO multiple times has also been adopted by the recent works of [ [3], which have shown that replication can lead to comparable or better theoretical and empirical performances of BO.
The works of 6 26
7 Conclusion
We have introduced the BTS-RED framework, which can trade-off between evaluating more unique conditions vs. replicating each condition more times and can perform risk-averse optimization. We derive theoretical guarantees for our methods show that they are no-regret, and verify their empirical effectiveness in walld precision agriculture and AutoML experiments. A potential limitation is that we use a heuristic (rather than principled) technique to handle unused budgets in an iteration (last paragraph of Sec. (.1.I). Another interesting future work is to incorporate our technique of using an adaptive number of replications (depending on the noise variance) into other batch BO algorithms 18 22 to further improve their performances. Moreover, it is also interesting to combine our method with the recent line of work on neural bandits [T6] 17]. which may expand the application of our method to more A14Science problems.
10

---

Acknowledgements and Disclosure of Funding
This research/project is supported by A$STAR under its RIE2020 Advanced Manufacturing and Engineering (AME) Programmatic Funds (Award A20H6b0151) and its RIE2020 Advanced Man- ufacturing and Engineering (AME) Industry Alignment Fund Pre Positioning (IAF-PP) (Award A19E4a0101).
References
[1] Berkenkamp, P. Schoellig, and A. Krause. No-regret Bayesian optimization with unknown hyperparameters. Journal of Machine Learning Research, 2019.
[2] M. Bínois, J. Huang, R. B. Gramacy, and M. Ludkovski. Replication or exploration? sequential
design for stochastic simulation experiments. Technometrics, 61(1):7-23, 2019.
[3] I. Bogumovic, J. Scarlett, S. Jegelka, and V. Cevher. Adversarially robust optimization with Gaussian processes. In Proc. NeulPS, 2018.
[4] G. Brockman, V. Cheung. L. Pettersson, Schneider, J. Schulman, Tang, and W. Zaremba. OpenAl Gym. 10Xiv:6666.014440 2016.
[5] X. Cai and J. Scarlett. On lower bounds for standard and robust Gaussian process bandit optimization. In Proc. ICML, pages 1216-1226. PMLR, 2021.
[6] S. Cakmak, R. Astudillo, P. Frazier, and E. Zhou. Bayesian optimization of risk measures. In Proc. NeurlPS, 2020.
[7] D. Calandriello, L. Carratino, A. Lazaric, M. Valko, and L. Rosasco. Scaling Gaussian process optimization by evaluating few unique candidates multiple times. In Proc. ICML,, pages 2521-2541. PMLR, 2022.
[8] Chowdhury and A. Gopalan. On kernelized multi-armes bandits. Proc. ICML, pages 844-853, 2017.
[9] S. R. Chowdhury and A. Gopalan. On batch Bayesian optimization. arXiv:1911.01000 2019.
[10] G. Cohen, S. Afshar, J. Tapson, and A. Van Schaik. EMNIST: Extending MNIST to handwritten
letters. In Proc. IJCNN, pages 2921-2926. IEEE, 2017.
[11] E. Contal, D. Buffoni, A. Robicquet, and N. Vayatis. Parallel Gaussian process optimization with upper confidence bound and pure exploration. In Proc. ECML/PKDD, pages 225-240, 2013.
[12] A. I. Cowen-Rivers, W. Lyu, R. Tutunov, Z. Wang, A. Grosnit, R. R. Griffiths, A. M. Maraval, H. Jianye, J. Wang, Peters, et al. An empirical study of assumptions in Bayesian optimisation. arXiv:2012.03826, 2020.
[13] Z. Dai, G. K. R. Lau, A. Verma, Y. Shu, B. K. H. Low, and P. Jaillet. Quantum Bayesian optimization. In Proc. NeurlPS, 2023.
[14] 7. Dai, B. K. H. Low, and P. Jaillet. Federated Bayesian optimization via Thompson sampling. In Proc. NeurlPS, 2020.
[15] Z. Dai, B. K. H. Low, and P. Jaillet. Differentially private federated Bayesian optimization with distributed exploration. In Proc. NeurIPS, volume 34, 2021.
[16] Z. Dai, Y. Shu, B. K. H. Low, and P. Jaillet. chpplle-the-oopimmiie batch neural Thompson sampling. In Proc. NeurIPS, 2022.
[17] Z. Dai, Y. Shu, A. Verma, F. X. Fan, B. K. H. Low, and P. Jaillet. Federated neural bandits. In Proc. ICI.R, 2023.
[18] E. A. Daxberger and B. K. H. Low. Distributed batch Gaussian process optimization. In Proc. ICML, pages 951-960, 2017.
[19] T. Desautels, A. Krause, and J. W. Burdick. Parallelizing exploration-exxloitttioi tradeoffss in Gaussian process bandit optimization. Journal of Machine Learning Research, 15:3873-3923, 2014.
[20] D. Eriksson, Pearce, J. Gardner, R. Turner, and M. Poloczek. Scalable global optimization via local Bayesian optimization. In Proc. NeurlPS, 2019.
11

---

[21] P. I. Frazier. A tutorial on Bayesian optimization. arXiv:1807.02811 2018.
[22] J. González, Z. Dai, P. Hennig, and N. Lawrence. Batch Bayesian optimization via local penalization. In Proc. AISTATS, pages 648-657. PMLR, 2016.
[23] R.-R. Griffiths, A. A. Aldrick, M. Garcia-Ortegon, V. Lalchand, et al. Achieving robustness to aleatoric uncertainty with heteroscedastic Bayesian optimisation. Machine Learning: Science
and Technology, 3(1):015004, 2021.
[24] M. W. Hoffman, B. Shahriari, and N. de Freitas. Exploiting correlation and budget constraints in Bayesian multi-armed bandit optimization. 1xXiv:1303.6744 2013.
[25] F. Hutter, L. Kotthoff, and Vanschoren. Automated machine learning: methods, systems, challenges. Springer Nature, 2019.
[26] S. Iwazaki, Y. Inatsu, and I. Takeuchi. Mean-varianee analysis in Bayesian optimization under uncertainty. In Proc. AISTATS, pages 973-981 PMLR, 2021.
[27] M. Jain, E. Bengio, A. Hernandez- J. Rector-Brook Brooks, B. F. Dossou, C. A. Ekbote, J. Fu, Zhang, M. Kilgour, D. Zhang, et al. Biological sequence design with gflownets. In proc.
ICML, pages
PMLR, 2022.
[28] K. Kandasamy, A. Krishnamurthy. J. Schneider, and B. Póczos. Parallelised Bayesian optimisa- tion via thompson sampling. Proc. AISTATS, pages 133-142. PMLR, 2018.
[29] K. Kersting, C. Plagemann, P. Pfaff, and W. Burgard. Most likely heteroscedastic Gaussian process regression. In Proc. ICMI, pages 393-400, 2007.
[30] J. Kirschner and A. Krause. Information directed sampling and bandits with heteroscedastic noise. In Proc. COLT, pages 358-384. PMLR, 2018.
[31] P. M. Kyveryga, T. A. Mueller, D. S. Mueller, D. Shannon, D. Clay, and N. Kitchen. On-farm replicated strip trials. Precis. Agric. Basics, pages 189-208, 2018.
[32] B. Letham, R. Calandra, A. Rai, and E. Bakshy. Re-examining linear embeddings for high- dimensional Bayesian optimization. In Proc. NeurlPS, volume 33, pages 1546-1558, 2020.
[33] A. Makarova, I. Usmanova, I. Bogunovic, and A. Krause. Risk-averse heteroscedastic Bayesian optimization. Proc. NeurIPS, 34, 2021.
[34] M. Mutný and A. Krause. Efficient high dimensional Bayesian optimization with additivity and quadrature Fourier features. In Proc. NeurIPS, pages 9005-9016. Curran, 2019.
[35] E. Nava, M. Mutny, and A. Krause. Diversified sampling for batched bayesian optimization with determinantal point processes. In Proc. AISTATS, pages 7031-7054. PMLR, 2022.
[36] Q. P. Nguyen. Z. Dai, B. K. H. Low, and P. Jaillet. Optimizing conditional value-at-risk of black-box functions. In Proc. NeurlPS, volume 34, 2021.
[37] Q P. Nguyen, Z. Dai, B. K. H. Low, and P. Jaillet. Value-at-risk optimization with Gaussian processes. In Proc. ICML,, 2021.
[38] V. Nguyen, S. Rana, K. Gupta, C. Li, and Venkatesh. Budgeted batch Bayesian optimization. In Proc. ICDM, pages 1107-1112. IEEE, 2016.
[39] A. Rahimi, B. Recht, et al. Random features for large-scale kernel machines. In Proc. NeurIPS, volume 3, page 5. Citeseer, 2007.
[40] C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006.
[41] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICMI., pages 1015-1022, 2010.
[42] S. S. Tay, C. S. Foo, U. Daisuke, R. Leong, and B. K. H. Low. Efficient distributionally robust Bayesian optimization with worst-case sensitivity. In Proc. ICML, pages 21180-21204, PMLR, 2022.
[43] A. van Beek, U. F. Ghumman, J. Munshi, S. Tao, T. Chien, G. Balasubramanian, M. Plumlee, D. Apley, and W. Chen. Scalable adaptive batch sampling in simulation-based design with heteroscedastic noise. Journal of Mechanical Design, 143(3):031709 2021.
[44] A. Verma, Dai, and B. K. Low. Bayesian optimization under stochastic delayed feedback. In Proc. ICML, pages 22145-22166 PMLR, 2022.
12

---

[45] Z. Wang, C. Gehring, P. Kohli, and S. Jegelka. Batched large-scale Bayesian optimization in high- sigh-dimnssionll spaces. Proc. AISTATS, pages 745-754. PMLR, 2018.
[46] Z. Wang and S. Jegelka. Max-value entropy search for efficient Bayesian optimization. In Proc. ICML, pages 3627-3635. PMLR, 2017.
[47] J. Wu and P. Frazier. The parallel knowledge gradient method for batch Bayesian optimization. In Proc. NeurIPS, volume 29, pages 3134, 2016.
13

---

A Expressions of GP Posterior
Following the notations in the main text (Sec. 2 we index every queried input at and observed output yt via an iteration index t and batch index b. Define - the collection of indices of the queried inputs in the first 1 iterations: I = {(t', (e)////(t,,M_MM.
[b]
Note that according to our notations in the main text, the cardinality I is [Zz-1l = TT-1 Eí'
=1-1 by. Then, the GP posterior for the objective function f in iteration t can be represented as ()) (0,,,,),,,)))) where
14-1 (x)) - 12-1(x) ( +11) +11 yr-1-
(3)
o (x, x') - k( (x)) [K,]) AI) k 1
in which 1x)) (1/nz²)
- [k x ITe b) y.-1 -
(u. Te in which ve
1bl Σ n Ve represents the empirical mean at the input z. calculated using the 1b replica- tions. K - (k(x// x
[6 16]
16] 18/ )(e,))zz, 1(("")))) 1 and X
a regularization parameter and will need be set to À 1 + 2/7 in order for our theoretical results hold (8).
B Proof of Theorem
Denote by 7--1 the total number of observations (input-output pairs) up and including iteration t 1: T--1 _ E by. This immediately implies that t 1 T--1 S B(t 1). We use Fi-1 to iteration - 1. Denote by b, the batch size
to denote the history of all π--1 observations in iteration I. Note that conditioned on Ft-1, b, is a random variable, which in contrast with standard batch BO in which the batch size is usually fixed. Here we use 14-1 (ar) and (z-1(x)) to denote the GP posterior mean and standard deviation conditioned on all 7 observations up to (and including) iteration t --1 1. Moreover, denote by 01-1,8 the GP posterior standard deviation after additionally conditioning on the first '' O,....,, b, - selected inputs in iteration Note that 0t-1)0(()) ot 1 (a:) according to our definitions. Define 3. a + 2 + log(2/8) and C. (. + /2 (og(((/)(t))
Lemma B.1. Ler (0. Define (t) as the event that (p(-1( f(x)) s (10 for all X. We have that TP (() 6/2 for all ' 1.
Lemma B. is consequence of Theorem 2 of the work of 8
Lemma B.2. Define E (t) as the event: |f, (x: (4-1(z)) S B 2og( 1 Vo E
X. E [b.]. We have that P [E (t) 2 1/t² for any possible filtration F,
Proof. According to Lemma B4 of [24] in iteration 6, for a particular and æ, we have that
(x) (-) s 3, 2 2log(1/5)0
(4)
with probability of 2 1- - 8. Replacing ó by 8/ (IB x1) and taking union bound over all x E X and all b E [be] gives us:
(x) pr (z)) < Be / log (B)x)//0000011100
Vo E X. [be].
(5)
which holds with probability 2 B| 1/t² completes the proof.
|b 2 8, because b, s B. Further replacing 5 by
Next, we define the set of saturated points.
Definition B.3. Define the set of saturated points at iteration t as
S, fxr X A(x) > (
in which A(x) f(x*) - f(x) and x" arg max fxx).
14

---

The next auxiliary lemma will be needed shortly to lower-bound the probability that an unsaturated point is selected. Lemma B.4. For any filtration Ft-1, conditioned on the events E (t), we have that Vaz E X, b E [bx]]
P [()]F-))) 2 p.
(6)
in which p 1Ev5'
Proof. For any E [bz], we have that
(x) (x) 11 14-1(x)
f(x) 14- (x)
PP (f f(z)|{=-1) = I
F
B10r (z)
1 (0)
fl (x:) 14-1 (x)
1f(z) p 11-1 Fi-1
2
B.0 (x)
1
(7)
[b] (x) M1-1(x)
P
> F
3,0 1 (x)
6
4/T π
The second last inequality results from Lemma B. and the last inequality follows because St (ax) follows a Gaussian distribution because f ~ GP ()) 3f02-1 Lastly, since all f00 's are sampled in the same way: f!² GP(H)11() (f the proof above holds for all b [bz]- D
The next lemma shows that the probability that an unsaturated input is selected can be lower-bounded. Lemma B.S. For any filtration Fi-1, conditioned the event E (t), have that
P
x1
M E X' St, F1,1 2P - 1/t²,
vb E {b..
Proof. For every b E [b,].
1 x PP E (X(((FF1) 2 (1. > (2), Ya S(FF-1)
(8) which holds vb E [b.]. The validity of the inequality above be seen by noting that x" is always unsaturated, because A(x*) = f(x') f(x²) = 0 < (0)=1()). As a result, if the event on the
right hand side holds (i.e., if f! (x*) (x) Vx E St), then the event on the left hand side is [b]
[b] selected by æ, = arg max max p(b) (x:) which ensures that an guaranteed to hold because x;
unsaturated input will be selected.
Next, we assume that both events E (1) and Ef(()) are true, which allows us to derive an upper bound on f! (ax) for all a E St and for all b E [ba]:
f! (w: I f(x) (x) < f(x) + A(x) f(w) + f(x") f()) f(x)) (9)
where the first inequality follows from Lemma B.J and Lemma B.2, and the second inequality results from Definition B.3 Therefore, ( implies that for every 6 E [b.]. if both both events E (t) and Ef((L) hold, we have that
(1. (x > (z), Va E S. P (x*) > f(xx))
(10)
Next, conditioning only on the event E (t), for every b [be]. we can show that
P x [b] X x S.
v WE > P (1")))²))))))))))()))))) > ,! (z)) Vax E SelFF-1)
IP (1("((1)) > f(x ((=)))F(1) -P (E)(t))FF)1)
(11)
p 1/22
which holds for all b e [bx].
15

---

Next, we use the following Lemma to connect the GP posterior standard deviation given all observa- tions the first iterations (i.e.. (-)) with the conditional information gain from the selected input queries in the 1th iteration (batch).
Lemma B.6. Define C2 Tog[I Denote all Tt-1 observations from iterations (batches) 1 to 1 as F14-1 and the b, observations in the 1th batch as yr- Then we have that
be
Σ (2)
(2)) se (C2bil(f:..l
b
Proof. Note that as has been described in the main text, the constant chosen such that:
(ffigAlaa-D) & C ACA,JAI
max
(12)
Denote by Dr.1 the first b observations within the hth batch, then for b 1,
0 (x)
exp [I(((x): y 11.1-11111111))
0t- 0t-1,b-1 (z)
exp
[If::V..0-11W1:c
exp
ACX;1A|/b-1 T(S:yal91--1
(13)
I(fiyaly1r-1)
exp
max ACX,
$ exp((C).
Also note that when 1, or- (2)-(20000--110111 = S exp(C)) Therefore, we have that
be
be <
b.
0z-1
(x]
|8
c
Oe- 1 (20 Se
o
be Σ o 1 (30 (0])
6=1
b=1
b=1
b
c
bi Σ
log 1+>-107 1 (z!
log(1 1 + x-11
(14)
b=1
be
c
C2bi
log 1+ 02 1000-02-10-110011
2
d=l
= = /C2ti (figely
The second inequality makes use of the Cauchy-Schwarz inequality, and the last equality follows from the definition of information gain.
The next Lemma gives an upper bound on the expected batch regret in iteration t: minse r2 [b]
mingepo. (rine)o.((((>))) (f(==))(())))))))))))(( (xx (b) ))-
Lemma B.7. For any filtration F,-1, conditioned on the event E (t), we have that
min .66 F(-1 S See (1+ nE(b.]
2B
E
(1+
E
Cal
+
1-1/12
b
12
in which !!! f(x") f
16

---

Proof. To begin with, we define ε as the unsaturated input at iteration t (after the first t - iterations)
with the smallest (posterior) standard deviation:
3t - arg R,A,
(15)
Following this definition, for any F such that (t) is true, vb E [be]] we have that
E (z
16 [
- a 16| 1 2 E
o. [6] --- 1 (he (p 1/1²),
[b] E X St IP a X selFe-1)
(16)
Now we condition on both events E (1) and E (1), and analyze the instantaneous regret as:
h,
by
[6]
(xz b
[(xe") ((t+)) + ((x,) - s [(x) (xx
min
RE(bg
bt
be b=1
b=1
b=1
b.
A + f! (x.) + (0.-1( (z:")) -000-1(2.0))
b=1
(17)
b,
c0 ( + ( + c.o0 100 + f!8 (T+) - . (cc
b=1
b.
(2(200_1((r)) + o b=1
in which the second inequality results from Lemma B.I and Lemma B.2 the third inequality follows [0] since De is unsaturated, and the last inequality follows from the policy in which x. is selected, i.e..
at arg max (z))
[b]
Now we separately consider the two cases where the event E (1) is true and false:
E
min ri [b] bE(b,]
F-11
1
c((20r-1(z.)
10 (0) F
+ 2BP
E5 (t)
b
E
1
20:
T
0 (2x + G.. 120
Fc-1
+ 2B
p
1/12
b=1
< <
1
2
E
1
(Z!
+
2B
p- 1/12
b 0=1
82
2
2B
[1 p- 1/t2
E
C2b1l (fiVelBue-1)
Fe-1
by
82
10 [
2B
S c
p
E
V
b
Cal
Fr
+ 12
(18)
where the second inequality follows from equation (6.. the fourth inequality results from Lemma and the last inequality follows since 2 10 p- 1/1/ p
B.6
Definition B.8. Define Yn = 0, and for all L = I,...,T.
F1 I1E (t)}
={(E(tt)
min [6]
r
be(be]
(1+ 10
2B t2
X, F, -
p V by
C2I (f:
Y, =
X.
==1
17

---

Lemma B.9. Conditioned on Lemma B.7 (t.e. with probability of 1 6/2), (Y: : =0..... T) is a super-martingen with respect the filtration Ft.
Proof.
E|y; - YY- = [[
10
CsT 1 (f:velaa)))))) [t-11]
1
2B
=E aee 1+
bi
(1+
(1+ 10)
2B
E Fi-1] - Bleee c
V (f + Fi-1l S 0.
22
(19)
When the event E (t) holds, then F. = min [b,] when ES (f) does not hold, F; and hence the inequality trivially holds.
_ and the inequality follows from Lemma
B.7
Lemma B.10. Define Co A
Given 8 E (0, 1), then with probability of at least
3/1 =/1-
10 Por S e 1+ (1+b) 1 er COCTTT +
BT²
+ 4B (AB +AB+ oTE (1+ VCCoOs
V 22oo(2/00)T.
3
Proof. To begin with, let's derive lower bound on b. Firstly, note that n4 S g 1. This implies
R
that b, 2 BB[ " 1. Next, we need derive upper bound |Y, Yy-1 which will be used when we apply the Azuma-Hoeffding' 's inequality:
|Y - Y-1l Xxl & Fel Ge
(1
10
C2I C21 (f: +
2B 12
be
p
2B ae c
(1+
10
CC2
+2B
(20)
V by
p
(1+
10
CC2
< 4B CEE c
p
b.
where the second inequality follows because
(J:9,1Bere-) S
max Sc
(U:YAVeH-)) S max
1(::AA S SCC 1.
ACX,
Next, we will need the following result connect the sum of condition information gains to the maximum information gain:
(f:
T (J: (T(: & VTTTE
(21)
in which the first inequality results from the Cauchy-Schwarl inequality, the second inequality follows from the chain rule of conditional information gain, and the last inequality makes use of the
18

---

fact that Tr - TB. Subsequently, we are ready to upper-bound the batch cumulative regret:
10
1 bt
2
aee
(1+p)
p
V
C2l (f:
+
Σ
t=1
2 1lgg(218)
Σ
4B 30+0ee aee
(1+
10
V
CC2
p
be
t=1
S c
1+ 10
CT
V
B
maa R
C2
Σ
T
+
Bx²
+
(1 10
CC2
4B + cre
1ogo((//8
p
V
IB/
manx R2
10 [1+ CT C,C2 TB +
Bx²
4B + Cre ) vCCOG, V2 1og(2/8T).
S 0e
3
(22)
The first inequality results from the Azuma-Hoeffdingg inequality, the second inequality makes use of the lower bound on by: b, 2 B R
and the last inequality follows from equation (2I)
Equation (22) holds with probability of 2 - 5/2 according to the Azuma-Hon couna--oefdding's inequality. Then, we also have that r; rt, Vt 2 with probability of 2 5/2 according to Lemma B. This completes the proof.
Note that et - (RRTTRRTTT which allows us to simplify the regret upper bound into an asymptotic expression:
RT = 3 C
1
TTTS
(VC+ VC++VI VTre)
(23)
B/
R
B.1 Simplified Regret Upper Bound for Constant Noise Variance
In the special case where the noise variance is fixed throughout the entire domain, i.e., when o² (x) o Lomat: Væ X. we have that n, I o R² = Tlconst and by = [B/Tconst = by Vt E [T'. this
case, instead of making use of the lower bound on be (i.e., by 2 B/T RE 1) as done the proof of Lemma B. 10 we can simply replace b, with by the proof.
result, the term of
/B
L, and hence regret the regret upper bound proved Lemma 10 can be simply replaced by The upper bound can be further simplified as:
RT - ( e
1 Tho ( (Vo+ VTTMa)
(24)
Vbo
As another special case where (²(x) = 2onst = R², every input æ will be evaluated only once (i.c., Toons 1) and 60 B. In this case, algorithm reduces to the standard batch TS with batch size of B, and the regret upper bound becomes
R = c
-
V
1
IT (VC+ vTrB)
(25)
C Choice of R2 by Minimizing the Regret Upper Bound in Theorem 3.1
The regret bound in Theorem 3.1
depends on the parameter R through the term g
4
B/loz B/(0 -1)--T in which we have replaced the term [o / R2 by 2 m R2 + such that
19

---

resulting regret upper bound is still valid and the subsequent derivations become simplified. Taking the derivative of w.r.t. R gives us
dg
[ 1)
-20" Rt o
max
max
(26)
dR
[(BB 1) )aax)) )
Setting the above derivative to we have that the value of R that minimizes g2 and g (hence minimizing the regret upper bound) is obtained at
VB+1
R
(27)
max B -
D Upper Bound on Sequential Cumulative Regret
E Confidence Bound for the Noise Variance Function
Here, as discussed in Sec. 3.2 in the main text, leverage the concentration of the Chi-squared distribution to show that we can interpret the unbiased estimate of the noise variance in equa- tion ( as a noisy observation corrupted by a sub-Gaussian noise. For every queried input, we use the unbiased empirical variance ( as the observation to update the GP posterior for the noise variance. First of all, when input at is queried, denote the unbiased empirical variance as (xx (b)) (xe))) + e', and we will show next that e' is (with high probability) a sub-Gaussian noise. Denote as n4 the number replications that
to query =!!! Since the unbiased em- pirical variance of Gaussian random variable follows Chi-squared distribution, we have that o "a )x2] xx2 Th
G2 (xx
(b)
xx= The n
with probability of 2 1 a. which 2 X,
6x - 1.1a/22 denotes the (a/2) th "h))"-qqumm qqantile ((1 - a/ th -uaantile)) the Chi-square distribution with
n degrees of freedom. This allows us to show that
2 Xm.-1a/22
X- 1,1 a//2
d'
E
o
(xx
1b
-1)
oz (x)
14 -
(28)
X 1,,//2
A -1,1-0/2 -11
E
o min
-1
o max
A [Las Ual,
Ammin
which holds with probability 2 1 Qmin the minimum number of repetitions we impose on every queried æı. Note that the discussion above the unbiasedness and boundedness of the noise
still holds after we negate the noise variance (i.e., g(-) = -o²(-) to analyze y! = g g( + e'.
Then the discussion in the main text (Sec. 3.2 follows.
F The BTS-RED- A Algorithm
Our BTS-RED Reee--DD-Unnonn algorithm is shown in Algorithm
G Proof of Theorem 4.1
Our proof here follows similar structure the proof in Appendix B but non-trivial changes need to be made to account for the change of objective function here. Here, for a given w, we at- tempt to upper-bound the mean-variance cumulative regret RMV Σ minsep,
hew (o: where hes
(x) + (1 w)g(x) = wf(x) - (1 - w))²(x) and xt E arg max [wf(x) + (1 - w)g(m)) Throughout the analysis here, we assumed pre-defined and hence omit any dependence on for simplicity. That is, we use place of at and use h(.)
to represent (.).
20

---

Algorithm 3 BTTS-RDD-Unnnown.
1: for t 1, do
2: b= 0. =0 (6')
3: while Σ8 n6
<
IB do
4: b
b
b+1
5: Sample f11)) from
6: Choose x [b]
arg max max x (z)
7: Choose ny (-14-1(00)
3,0 ()/
8: by =
for [6e]. query x; with n4 (b)
9:
parallel processes
10: for b E [be], observe (ve,n (6)
ne then calculate u (1/n, (b) Enm Vi, and 5t
11(mm (b)
- V/.n
(1)
1/2 (b)
11: Use ((x)) Vi } bE().] update posterior of GP
(b] (b)
12:
Use ((x) Ve ]be((b)] )
(b] ((6)
to update posterior of GP'
denote the function Me-1 and 0; to denote the GP posterior mean and standard deviation of the GP for f conditioned on all T--1 observations up to (and including) iteration
Here, same the main text, we use g:A. - IR
We use
1, and use 14/11 and oا_ to denote the GP posterior mean and standard deviation of the GP for the negative noise variance -² Denote hi (#) = w (x) + (1 - w)gg"' (z)) such that æ,"" E arg max xa, [b] of observed pairs of input and empirical noise variance up iteration
Denote by F/11 the history
Define 3r B + 2 r. - log(3/8)) and - Bc(1 + 22ogg x()) Also define & B' R', W 22(T Te-1 +1+ log(3/6)) and c - 3,(1 + (2)
Lemma G.1. Let ê E (0, 1). Define (1) as the event that (x) g(x) S (x) all x E X. We have that (t) 2 1- - 5 for all t 2 1.
The validity of Lemma G.1 follows from the discussion in Sec. 3.2 (i.e., equation G. after
replacing the error probability of 6/2 by 8/3. We also need Lemma B.1 to hold, and since we have replaced the error probability of 6/2 in 3, from Lemma B.] by 8/3 in our definition of B, above, we
have that the event E (t) in Lemma B.1 holds with probability of 2 8/3 here.
Lemma G.2. Define F (t) as the event: 1g: ()(()) 1/-1 (x)) / loggoo222 (11)'
4b [bo]. We have that P E (t) 2 1/(2t?) f any possible filtration F(
Similarly, will also need Lemma B.2 to hold, but replace the emror probability of 1/12 by 1 1/(2))). Of note, we have also correspondingly changed the value of e, from Appendix B by replacing 1 by 2t in our definition of o above.
The definition of saturated points also needs to be modified:
Definition G.3. Define the set of saturated points iteration as
S X' A(x) wo.0,- +1 ())
in which ((x) = f(x=)()(=))))))))r())) h(x) and x" E arg maX h(x).
The following lemma a counterpart to Lemma B.4 in Appendix and the proof here makes use of the same techniques.
Lemma G.4. For any Fl- conditioned on the events (t), we have that Vo E X, b [be].
bb P gt
(x)
g(x))([(11) 2 p.
(29)
in which p dev=
21

---

Proof. For any E [bc]. we have that
9i g (x) (x))
g(x)) - 14- (x)
P (g) (ar) s(x))]([11 =P
F1
B(00-110 (x)
1 (a) 14-)(a))
1g(x)) - 14-11
P
F
B/0 (x)
1/0
(30)
9r (a)) 14 (2))
F
2 P
Bi0 (z)
6
4V
The next Lemma is the counterpart to be carefully handled here.
I Lemma B.5 in Appendix B but additional challenges need to
Lemma G.5. For any Fi-1 and Fi-1, conditioned on the events E (t) and E we have that
P 2 bl E X S11F--1, 2 22 -211/11 1/1, 4b E [bx]-
Proof. For every b [b,].
P (1// E EX ER (1 2 (1." > h1 (x), Va E F11F
(31)
which holds vb E [be]- This inequality follows from noting that æ" is always unsaturated according
to Definition G.3 and that a! = arg max ( (x)) arg max (1 (w) + (1 w)9. (z)).
Next, we assume that the events (t), E (t), (t) and E all hold, which allows us to derive an upper bound on h (a)) for all æ E Sy and for all E [bx]:
1. M (a)
(1 (1 w)gg( [b]
(x)
S w (J(x) + (1 w) (g(ar) + (d)-1(1))
(f(()) + (1-w)g(a + wGg (ax) (1 w)
(32)
< h(x)) + +(z)
= h(()) + h((")) h(x)) = l(xx),
where the first inequality follows from Lemmas B.I B.2 G.I
and G.2 and the second incquality
makes use of the definition of ((x) as well as Definition G.3
Therefore, (32) implies that for every b [by], if the events E (t), Ef (+) and Et all hold, then we have that
P(M (M (xx) (x") 1111 (x) S.FF-1, FL11) P (n. (1("((=))))))))))))())))))))(( h(x 1 Fi-1)
PP wll (x*) (1 )) (10") wf(x")) (1 w)g(a=)) |[F
> IP 1!¹ (x*) f(x (nd")andghh)) gf g(x [
2 2
(33)
The second inequality results since the event in the third line implies the event in the line above, and the last inequality follows from Lemmas B.4 and G.4
22

---

Next, for every E [bx], we can show that
mt EX (
0 (x=)) > (x),,
Va Vo E -
2 h [ (x*) > h(x')) -P
2 p² 1/f.
(34)
which holds for all b E [6r]. The second inequality follows from considering the following
two events separately: Ef n (t) and E (t) (t), and the last inequality follows
since P E3 (B)
P (Eh(t))-- + Es (t) (t)
1/(2/)) 1/(()))
+
Next, we will need the following Lemma which is counterpart Lemma B.6
Lemma G.6. Define C2 + Denote all T--1 observed empirical means from iterations (batches) 1 to t 1 as Y1-t-1- and the b, observed empirical means in the thh batch Ye- Also denote all T--1 observed noise variances from iterations (batches) 1 to t t- 1 as y'a-1 and the by observed noise variances in the thh batch as y'- Choose C as an absolute constant such that max AC |A|SB (J:9 1191211) S C,Vi 2 1 and max AaXACx T. (g: I'Al''a-11) S C, VI 2
Then we have that
Σ (z) (1)) se (
b=1
and
b Σ 6
o 0
SEC Co (20
161)
Proof. Note that have assumed that both and g are associated with the SE kernels k and K, respectively. Denote the length scales for l and k by 0 and A' respectively. Note that the maximum information gain is decreasing in the length scale, i.e., smaller length scale leads to larger maximum information gain []. Therefore, we can run the initialization stage via uncertainty sampling observe Vinit using the kernel with smaller length scale.
For example, if 0 < 0', we use the kernel to run uncertainty sampling algorithm for Tin iterations collect the initial set of inputs Danns such that we can guarantee that
max I ((iyAllan-1) SC
S max Ali S C,
(35)
ACX.JA SB
where the first inequality follows from the submodularity of conditional information gain, and the second inequality
consequence of Lemma 4 of [19]. Note that given the same set of initial inputs Dinit, the maximum conditional information gains A Il (J; y Mmii) and max max ACX,AA|E II (g: ('it))) differ by only the lengthscales of the kernels i- and k', denoted as A and 0', respectively. Therefore, since we have assumed that < 0' in the discussion here, we have that
max I (gg ('A SC
max 1 yff:yAlyma) A
(36)
This further tells us that
max II (1: SCR
max I (gi AC (A <B
S
max ACX.JA|SR
(fiiallmmi S S,C. 2 1.
(37)
Subsequently, the proof is completed by applying the proof techniques of Lemma B.6 0 and 6'1 separately.
23

---

Lemma G.7. Define = wB + w) For any filtrations Fi-1 and F conditioned on the
events E (t) and Ea((), (t), have that
EB
min re [E,
16|
Fr-1
S se
(+
28 pd
wo,B by
Cabel (f
2B
+ (1 w)
V Cabel (1:0
+
b,
in which r!"" = hh(=)) h(m: 16
Proof. begin with, we define E. as the unsaturated input at iteration with the smallest weighted posterior standard deviation:
x = arg min min (w0)0e-1(2)) + (1 w)((o(
(38)
Following this definition, if both E (t) and (t) hold 4b [Dz], then we have that
E [[ (0)) (1 w)do F(r1 F(-
/0/ ) + (1 - w) (x. 1b| |F-1 Lt E x x s
b P
( x
2 [w (T+) + - w)do/-1 [x.) (p² - 1/12)
(39)
Now we condition on all events E1)1), (1), (1) and E9:(1), and analyze the instantaneous
regret as:
min Tt
[6]
[0]
(xt
1b
h(x*) 1((x))))) + h(x,) (axt!11)
bE(b,)
bt
b
bt
b=1
b,
+ (b) (xte) + (x + (1 - w))
A (.t)
b8
b=1
h/ (x,
181) (0100-110 16 + (1 - w/ w
WC (It (1 (1-w)
+ 1/( (I+:) ww: + - w)
1//0 (xx!
(0 18] + (1 (1-w1(c (2
b.
+ Wc2 2 + -0-1) + (1 w)oc of (x!
+ | (Tt)
11/" [ct[">]
b
WC2 (20,-1 (Zx, + o, (z( + (1 - w)o (20 ( oi (z
+ wo. 2 (w0) (1 -1-11111wo00o w)c(o(-)((1))
+ (1 w)d (2) }].
bc
(40)
in which the second inequality follows from Lemmas B.I results from Definition and the fact that IG is unsaturated, and the last inequality follows from the way in which x; is selected: z!" arg ma (z).
B.2 G. and G.2 the third inequality
24

---

min r2
[6]
F1-1, Fi
SR
2 (wo)or-1(ar)) + (1 ()cco(_1(x.))
bE(b:]
bt
+ (0 (
+(1 (1- - w)d (2, F1-1, + 2BP E
1 bi
12 1/12 (2) + (1 - w))c
$
bt b=
+ 11( ( + (1
- w)bok (2 Fr-1, F 2-1
+ 2B 1
t?
S wwm
28 1
R
1
ot
1
(8)
p2
b
b=1
+ (1 w)d
[1+
28 p²
E
(z (0) F1
2B
be
f2
28 p2
woge
(1
EE
C2br1 (1
28 p2
2B
+ (1 - w)dfe
1+
E
12
α [
28) p2
woGE 1
b, V C2b,I (f
(1 w) b,
V22
+
2B
(41)
The second inequality follows from equation 339 the third inequality follows since 1/622 1/82) 14/p², and the last inequality makes use of Lemma G.6
Definition G.8. Define Y, = 0, and for all t = I....,T.
F. EE) min Ti |b| bE(bc]
X, Tt - (1+
28 p2
Cabil (fiVelrra-)) + w)c 1 V Cahht (g: b,
2B
vilv'r-1)
wet
be
t2
Ye
X.
Following the proof of Lemma B.9 Now we are finally ready to prove an upper bound on the batch cumulative regret of our Mean- Mean-Var- BTS-RED:
we can easily show that (Y: : :. 7) is super-martingale.
Lemma G.9. Define Co
$
Given 8 (0, 1), then with probability of at least 8.
3/1
1-1
28 (1+ V2Con' VTT (1 w)c v T'rs
ReM S C
2
VC2Co wor + +(1 w)dr 1) Vllog(4/0)T,
BT² +
+
6B + vV
6B
(1+
3
25

---

in which PTe is the maximum information gain about f obtained from any set TB observations, and Tr the maximum information gain about g obtained from any set Tf observations.
Proof. To begin with, let's 's derive a lower bound on by. Firstly, note that n4 S [ [[ 1. This implies
that by 2 B/
max
1.
R
1 Y--1= - |xx1
[ 1
28)
+ec = -1rel + c²
1+ p²
(uci b,
C2b,T (f:
1
+ 2B
+(1 w)d
C2b,,I (g: (9i
V
be
(42)
28
C2C
C2C
S 2B +E
[+
way by
+(1 (1-w)dd
V
+ +2B
p²¹
by
28 p|
C2C
+ w)de |C2C
AB+c c
[+
wan by
bt
T
(ff S
T
(f:y.lbaaa)) (TI(f: S VTT...
(43)
Applying the Azuma- Hoefa--offfding's inequality using error probability of 8/3 leads to
T
T
T
28
Σ
E
c
+
w
C1
(1 C2ll (f: (fi + (1 (1-w)
Σ
d
C2ll (g: vil
p2
b
be
t=1
[=1
2
2
T
28
CoC
C2C
+
+
log
Σ
4B + e
(1
pr wCt
+ (1
w)d, (1--w)d be
1
be
28
C2
Set 0e0
1
VT
WCT v TTB + (1 - w))
T.B
p2
BB
1
R
woT + (1 - w)or/ )) V2log(3/8yT
B
4B + e VVC
1
28 p²
C2
3
BB/
mas 122
c
I+
28 p2
VC2COVT WCTVTIB + (1 (1-w1) w)d /T/8
1) v /log(///))
Ba² (B (BB vibteVo(1
2
28 12 VC2C
wer + (1 - ([-wee))
+ 3
+
(44)
The second inequality makes use of equation 43 and the lower bound on by: 6, 2 B R
Now, note that F, = rr, Vt > with probability of 2 - 5/3 - 8/3 because both events ES (1) and (L) hold with probability of > 6/3 respectively. As a result, taking into account the error probability of 8/3 from the Axuma-Hoeffdiin inequality, the regret upper bound holds with
probability of 2 1 - 8/3 8/3- 6/3 = 1- 6.
26

---

0.25
groundtruth var upper bound
0.20
0.15
0.10
0.05
0.00
0.0
0.2
0.4
0.6
0.8
1.0
input
Figure Groundtruth noise variance function and an estimated upper bound (Sec. 3.2
Finally, we simplify the regret upper bound from Lemma G.9 into asymptotic notation:
1
VT WRRTTT VC) + (1 (1-w)R' W) VTrrTTll TT + vOJ]
/
R
(45)
H
More Experimental Details
Since the theoretical value of Bt and 8 is usually too conservative 44 3 we follow the common practice and them to a constant: B. 33
In every experiment, we use the same set of initial inputs selected via random search for all methods to ensure fair comparison. For all methods based on TS (including
our methods), i.e., methods which require sampling functions from the GP posterior (e.g., line 5 of Algo. [T line 5 of Algo. 3 and line 5 of Algo. 2). we follow the common practice and sample the functions from the GP posterior through random Fourier features approximation [39 46 [34]. Again following the common practice in BO, optimize the GP hyperparameters by maximizing the marginal likelihood after every iterations. Our experiments computer server with 128 CPUs, with the AMD EPYC 7543 32-Core Processor. The server has 8 NVIDIA GeForce RTX 3080 GPUs.
H.1 Synthetic Experiments
In the synthetic experiments, for both mean and mean-variance optimization, we firstly use sampled function from a GP with the SE kernel (lengthscale= 0.04) as the objective function f (normalized into the range [0, 1)), and then sample another function from GP with the SE kernel (lengthscale= 0.15) as the noise variance function x² (normalized into the range [0.0001, 0.2)).
Fig. 4 shows an example of the upper bound U.² (x) = --4 + _ constructed by our BIS-RRDD-Unknown (Sec. 3.2 which is an effective approximation of the groundtruth o²(().
Here we also use the synthetic experiments to explore the impact of the uncertainty sampling (US) initialization, which is required by our theoretical results (Sec. 3.1.2), affects the empirical performance of our algorithms. The results in Fig. Fig.Baa show that using US and random search as the initialization method lead to similar performances. This provides an empirical justification for our choice of using the simpler random search as the initialization method in our main experiments.
H.2 Real-world Experiments on Plant Growth
As we have mentioned in the main text (Sec. [.2).. we perform real-world experiments using the input conditions from regular a 2-D grid within the 2-D domain. Specifically, the 2-D grid constructed using the pH values of (2.5, 3.0, 3.5, 4.0, 4.5, 5.5, 6.5) and NH3 concentrations of {0. 1.5, 5, 10, 15, 20, 25, 30) 1x00 uM). In other words, the size of the grid is 7 x 8 = 56. Every tested input condition replicated times. For every tested input condition, the leaf area and tipburn area after harvest are observed, both measured in the unit of mm? The resulting observations
27

---

Batthh In.-
Batch 15 (n: 5]
Rattch TS in 100
Simple Regret
Eatch T5 (i. 20)
(115-0k0--nntree (..3
ATS AT5-RED-tmtnoee (v
GP
0.15
0.10
0.05
0.00
20
40
60
Iterations
Figure 5: Results for the mean optimization problem for the synthetic experiment (Sec. 5. after adding comparisons with some sequential BO algorithms. Sequential BO algorithms are unable to perform competitively with other algorithms which leverage batch evaluations.
1.5
1.0
0.8
0.5
0.0
Objective
Objective
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Input
(a)
(b)
Figure 6: (a) The synthetic function used in the experiments for mean-variance optimization in Sec. 5.1 (b) The mean and varn-variance objective functions (w 0.3).
Different
0.12
BTS-RED Known Sr 2.21
ITS Known OK
Ran HII BTS ie
Ragees
0.06
0.05
0.04
8.00
60
70
Iterations
(a)
(b)
Figure 7: (a) Results using more values of for BTS-RED-Known in the synthetic experiment. (b) Results for the synthetic experiment using the LCB as the report metric.
Uncertainty Sampling
srs wit
Simple Regret
ot's #T1-400-00 MuD--nnnowwn 00
0.10
0.05
60
Iterations
Figure 8: Comparisons of results using uncertainty sampling (US) and random search as the initial- ization method.
28

---

Mean-Var Objective
Noise Variance
50
266
NHa (x1000)
NH3 10000
12
1.8
-50
18
24
24
10
-100
30 05
9g.
30
2.5
3.3
4.1
4.9
5.7
6.5
2.5
3.3
4.1
4.9
5.7
6.5
pH
(a)
(b)
Figure 9: Groundtruth (a) mnean-variance objective function and (b) noise variance functions for the leaf area, including some selected queries (white stars) and the corresponding n. s.
140
Leaf Area Tipburn Area
110
Leaf Area
135
105
130
100
Bacc T5 Us- 201
125
95
120
90
0
20
40
60
80
100
20
40
60
80
100
Iterations
Iterations
(a)
(b)
Figure 10: Mean optimization for (a) the leaf area and (b) the weighted combination of leaf area and negative tipburn area. The results for some sequential BO algorithms included here, i.e., GP-TS, GP-UCB and GP-UCB with a heteroscedastic GP. Similar to Fig- 5 for the synthetic experiment, sequential BO algorithms fail achieve competitive performances with other algorithms which able to exploit batch evaluations.
used to learn hetcroscedastic GP model from GPglow (https://gpflo readthedocs. www/en///nn develop/note htt.llopnootboooke//ooo wwtebiooi//ttaaacceeeeeeeeeeeeee
html), which is then used to produce the groundtruth mean and variance function used in our experiments.
H.3 Real-world Experiments on AutoML
In this experiment, we aim to tune two hyperparameters of SVM: the penalty parameter (denoted as C) and RBF kernel parameter (referred to gamma), both within the range of [0.0001, 2]. To obtain the groundtrugh mean and variance functions, we firstly construct a uniform 2-D grid of size 80 80 using the 2-D domain, and then evaluate every input hyperparameter configuration 100 different classification tasks (i.e., using the images of hand-written characters from 100 different individuals in the EMNIST dataset). The EMNIST dataset is under the CCO license. For every tested input hyperparameter configuration on the grid, we record the empirical mean and variance as the groundtruth mean and variance at the corresponding input location. As result, this completes our construction of the groundtruth mean and variance functions with the input domain being discrete with size of 80 80 6400.
the grid using
Figs. T and plot the constructed groundtruth mean and noise variance functions, including the locations of some selected inputs (the selected inputs after every iterations are included) well as their corresponding number replications n4's. Similarly, Figs. [Te and show the queried inputs and the n4's 's of Var--aa---RIII (w 0.2), shown on the heat maps of the mean-varinn variance objective (c) and noise variance functions (d). The figures show that similar to Fig. for the precision agriculture experiment, the majority of our input queries fall into regions with large (either mean
29

---

Mean
0.9
Noise Variance
0.09
0.00
0.8
0.08
0.7
0.07
0.48
0.48
0.6
gannaa
0.99
0.5
0.99
0.4
1.49
1.49
0.02
2.00
0.00
0.48
0.
1.49
2.00
0.00
0.48
0.99
1.49
2.00
0.01
C
(a)
(b)
Mean-Var Objective
Noise Varlance
0.00
0.16
0.80
85
0.14
0.07
0.06
gomeaa
0.99
0.99
0.05
0.04
1.49
0.06
1.49
0.03
0.04
0.02
2:00
0.00
0.48
0.99
1.49
2.00
0.02
2,00
0.00
0.48
0.99
1.49
2.00
0.01
C
(d)
Figure 11: Groundtruth (a) mean and (b) noise variance functions for hyperparameter tuning of SVM, including some selected queries (white stars) and the corresponding n, (c. d): The corresponding plots for mean-variance optimization (w = 0.2) for hyperparameter tuning of SVM.
Larger budget 100
Smaller budget
0.04
0.06
Batch T5 dixed 5)
Botch T5 ifxed 51
Baich 15 dloed n. 10]
Batch T5 dixed n 201
0.05
Batch 15 Iflaed -1-10)
Batch T5 ifieed n.u 15)
Simple Regret
0.03
Batch 15 dixed 40)
Simple Regret
BTS RED Uninowe (x30
BT5-ABr--Unicooee 0.2)
RED Uninown
0.02
0.03
0.02
0.01
0.01
0.00
20
40
60
20
40
60
Iterations
Iterations
Figure 12: AutoML experiment using different budgets B = 100 and B 30.
mean-variance) objective function values (Figs. II and c) and that the selected number of replications n, is generally larger those input locations with larger noise variance (Figs. ITp and d).
H.4 Additional Experiments with Higher-Dimennsional Inputs
The Lunar-Lande experiment requires tuning parameters of heuristic controller used to control the Lunar-Lander environment from OpenAl Gym 4 The controller can be found at https hraibuu..ccmmppeaai////////b/b// http:///......00000.000660666660
c/ggm//c smvs/boxxd//lmm lander 4447 The robot pushing task was introduced by [45). and we defer more detailed introduction experimental settings to the work of [45]. Both experiments
widely used benchmarks for tigh-dimensiioal BO experiments [[6] 20). In both experiments, for
30

---

12-dimensional
14-dimensional
Cumulative rewards
0.6
Curullative rewards
0.4
0.2
(o-+5)
Reesh 73 to-m 16:
Baith in m20
-0.2
STE-RED-Unowwnnn
20
Iterations
Iterations
(a) Lunar landing.
(b) Robot pushing.
Figure 13: Experiments with higher-dimensional input spaces.
every evaluated controller parameters (i.e., every evaluated input æ),, the observation (i.e., cumulative rewards) is noisy due random environmental factors. addition, the noise may heteroscedastic. For example, an effective set of parameters which can reliably and consistently control the robot likely induce small noise variance, whereas some ineffective radically varying behaviors and hence large noise variances. Therefore, these experiments are also suitable for the application of our algorithms. Since the domain continuous in these two experiments, here we maximize the acquisition function in every iteration via combination of random search and L-BFGS-B: B: in every iteration when need to maximize the acquisition function, we firstly randomly sample 10, 000 inputs/points in the entire domain and find the point with the largest acquisition function value, and then further refine the search via L-BFGS-B with 100 random starts.
of parameters may cause
31


Reviews:
[{"review_id": "BNusGc6tAk", "reviewer": "Reviewer_QJyu", "summary": "The authors propose three methods for Bayesian Optimization under the constraint of batch sampling and with significant heteroscedastic aleatoric uncertainty assumed. Their methods BTS-RED-Known assumes knowledge of the variance function, BTS-RED-Unknown does not assume the variance function is known and fits a GP to the negative variance function and Mean-Var-BTS-RED, also assumes no knowledge of the variance function but uses the learned variance function to enable risk averse BO by optimizing for a weighted combination of the mean function and the negative variance.\n\nThe authors prove their methods are asymptotically no-regret. The methods are tested on synthetic as well as real-world (precision agriculture and hyperparameter optimization) setups.", "questions": "- I was surprised to see that the second GP was used to model $- \\simga^2$. Is this correct? Why is the GP not used to model $log \\simga^2$ as is more standard in the literature as it can take on values on the full real-valued range?\n- I am not sure I fully understand the implementation of non-batch BO algorithms in the experimental section. It would seem to me that a non-batch algorithm should have an advantage in that they should sample 1 point, make an observation, update the function representation and sample again. Of course this may make them infeasible to apply to problems with batch structure e.g. precision agriculture. However in the experiments these methods are performing very poorly, so I am assuming they are not implemented as above. Are you using the non-batch methods in a batch-wise fashion? I assume this would mean that all these methods would in effect simply sample the exact same point many times per batch until the budget is used up? If my understanding is correct, I am not sure this is an interesting comparison and it would be interesting to evaluate these methods as they were intended to be used as a upper bound on performance compared to methods with the batch constraint.\n- Why is there a need to compute the empricial mean over the replications (line 9, algorithm 1)? It would seem to me that adding (x, y_1), ..., (x, y_n) data points to the training data would be a better use of the data as it would explicitly weight observations with more replications more highly. It seems to me that you are losing the weighting by the number of replications be computing the empirical mean of the observations and treating all such aggregated data points as equal (line 10)?\n- Do I understand correctly that in the various BTS-RED methods, the batch structure is only accounted for in the heuristic regarding replicating the same point too many times? Otherwise sample points are selected independently, with no cross-datapoint correlations accounted for and no knowledge of the prior points in batch? This would seem like a significant weakness of the method, and it seems feasible to modify the method to account for this, see for example \"BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning\" for a similar treatment in the related active learning space.", "limitations": "The authors address some limitations of the method e.g. the use of a heuristic to handle unused budget in the last iteration of the algorithm. However I would liked to have seen a more comprehensive discussion of other limitations:\n\n- The method is tested on discrete valued domains, it is claimed extension to the real-valued domain is feasible, however it is not clear to me that the heuristics introduced to ensure that the same point is not sampled repeatedly can be trivially extended to a real-valued domain where it would be possible to sample a very near by (essentially identical) point without adding to the count of the number of replications for the originally sampled point.\n- Heuristics are introduced to ensure the same point is not sampled too many times and the method introduces new hyperparameters which cannot all be set following apriori guidelines.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written and clear.\n- The BTS-RED methods are simple and intuitive, it would be easy to implement and apply them to new problems.\n- The method performs well on the limited (see below) empirical evaluation conducted.\n- The authors prove the BTS-RED methods are asymptotically no-regret.\n- The Mean-Var extension for risk averse BO is interesting.", "weaknesses": "- The method is developed for discrete valued domains, IMO extension to real-valued domains may not be trivial (see limitations section).\n- The experiments are all conducted on very low dimensional, discrete domains with small bounds. I would have liked to see evaluations on real-valued domains and higher dimensional problems e.g. hyperparameter tuning with 10-20 mixed type hyperparameters. Currently the empirical evaluation is quite limited as a result.\n- For the synthetic and precision agriculture experiments, the authors guarantee the ground truth function is of the heteroscedastic GP model class that their method assumes. This is not unreasonable, but given that there is only one further experiment in the paper which comes from a real-world unknown function (hyperparameter tuning experiment) this limits the robustness of the empirical evaluation as it gives the BTS-RED methods quite an advantage over competitor methods which do not have a heteroscedastic GP function representation. I would have liked to see further evaluated on more unknown ground truth functions.\n- Overall I am slightly concerned with the substantiveness of the contribution of the paper. The use of a heteroscedastic GP and Thompson sampling for BO is well established. The extension to batch sampling is interesting, but to what extent the BTS-RED methods interestingly integrate batch structure seems limited to me (see questions below). The Mean-Var extension is again interesting but fairly straightforward. All together the novelty and contribution seems somewhat limited compared to prior work e.g. [16].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for your valuable feedback.\n\n---\n\n**Clarification on Batch Selection and the Heuristic:**\n\n> ...the batch structure is only accounted for in the heuristic regarding replicating the same point too many times...\n\n> ...it is not clear to me that the heuristics introduced to ensure that the same point is not sampled repeatedly can be trivially extended to a real-valued domain...\n\n> ...to what extent the BTS-RED methods interestingly integrate batch structure...\n\nTo clarify, **our methods do not need additional heuristics to ensure that the same point is not sampled repeatedly**. Instead, the diversity of the selected points in a batch is achieved by **the inherent randomness of the Thompson sampling** (TS) strategy (lines 44-45). In fact, using the inherent randomness of TS for batch selection is a simple and well-established method in BO (e.g., see [13, 20]), which both allows for the derivation of theoretical guarantees [20] and leads to strong empirical performances (e.g., the TuRBO algorithm from [13]).\nMore importantly, we think that the strong theoretical guarantees of our algorithms (e.g., our algorithms are asymptotically no-regret, e.g., see line 157) indicate that our batch selection strategy is principled rather than heuristic.\n\nRegarding the heuristic you mentioned, if we understand correctly, we think you are referring to the heuristic of a maximum number of replications mentioned in lines 129-130. As a clarification, this heuristic is only needed **to further improve our empirical performance**, and is hence not an essential part of our algorithmic design. As a result, this heuristic **does not affect the ability of our algorithm to solve problems with continuous real-valued domains** (please see our next response).\n\n---\n\n> More real-world experiments with higher-dimensional, continuous domains.\n\nAs we've clarified above, applying our methods to continuous real-valued domains is indeed feasible and in fact trivial. **We have added two real-world experiments with high-dimensional continuous input domains** (see Fig. 1 in our global response above), with input dimensions of $d=12$ and $d=14$. Our methods still consistently achieve compelling performances (especially with $\\kappa=0.3$, which is consistent with our original experiments, see lines 258-261). These additional results are further demonstrations of the practicality and real-world potentials of our methods, and we'll add them to the paper after revision.\n\n---\n\n> Substantiveness of Our Contributions\n\nHere we clarify our novelty and contributions. In addition to the novelty of our algorithmic design (e.g., our adaptive selection of the number of replications depending on the noise variance), a major part of our novelty and contributions (compared with the previous works such as [16]) comes from our theoretical analysis. Specifically, we have shown that our algorithms are asymptotically no-regret, and are guaranteed to improve with a larger budget $\\mathbb{B}$ or smaller noise level. Moreover, our theoretical results have provided guidelines on the practical implementation of our algorithms (lines 171-181), which we have indeed followed in our experiments. Lastly, we have empirically evaluated our methods in real-world problems with large and heterscedastic noise (e.g., the experiment using real-world data from precision agriculture in Sec. 5.2) and shown that our methods achieve competitive performances.\nTherefore, we think that our algorithmic design, theoretical analysis and empirical experiments constitute important contributions.\n\n---\n\n> Using the second GP to model $-\\sigma^2$ (instead of $\\log\\sigma^2$).\n\nThis is because it allows us to naturally derive our theoretical guarantees. Moreover, this choice has indeed helped our algorithms achieve compelling empirical performances, as demonstrated by our experiments. We'll explore modelling $\\log\\sigma^2$ in future works to see if it leads to further performance gains.\n\n---\n\n> Implementation of non-batch BO algorithms\n\nThe reason why batch methods are favored in practice (over non-batch methods) is due to their ability to perform paralell evaluations. So, in our experiments, we have adopted a more realistic comparison, which allows the practical advantage of batch methods to be seen more clearly. Specifically, in our figures, every iteration represents 1 batch, and hence non-batch methods can be seen as having a batch size of 1.\n\n---\n\n> Why is there a need to compute the empricial mean over the replications (line 9, algorithm 1)? ... It seems to me that you are losing the weighting by the number of replications...\n\nThe use of the empirical means over replications is theoretically motivated, i.e., it allows all our observations to have the same effetive noise variance $R^2$ and hence serves as the foundation for our theoretical analyses. Moreover, the weighting by the number of replications is in fact implicitly accounted for by the effective noise variance $R^2$. This is because for every queried input, its number of replications is adaptively selected to ensure that the effective noise variance for its observation is upper-bounded by $R^2$ (see lines 116-125 for detailed explanations).\n\n---\n\n> Our hyperparameters.\n\nRegarding our hyperparameters, we have discussed how our hyperparameters are set (Sec. 5, first paragraph). Most of our hyperparameters are kept at the same values in all our experiments, and regarding our most important hyperparameter $\\kappa$, we have shown that the values of $\\kappa=0.2,0.3$ (especially $\\kappa=0.3$) consistently lead to competitive performances in all our experiments. So, we think our adopted hyperparameter values can serve as good recommendations for the practical deployment of our methods.\n\n---\n\nThank you again for your insightful comments. We hope our additional clarifications and experiments could improve your opinion of our paper.\n"}, {"review_id": "PlbcInFevQ", "reviewer": "Reviewer_4YBP", "summary": "The paper proposes a batched Bayesian optimization with heterodescadic noise and Thompson sampling. Further, it proposes an extension where not only function is minimized but also a robust variant objective which also incorporates observational noise variance. It provides some regret analysis relying on prior works and experimental comparison on real life benchmarks from agriculture. \n", "questions": "1. Why do you put heavy focus on the theory? Are the theoretical bounds important for your real-life experiments?\n2. You provide a outline how to choose R, but is this what you use in your real lab-experiments. \n3. In real experiment - do you use uncertainty sampling as in the theorems? \n\n\nI my opinion this provides limited novelty towards broader NeurIPS crowd. I think as a case study of Bayesian optimization with heteroscedasdic noise its very nice, and a paper more focused towards actual challenges with precision agriculture would be much more fitting. I think studying the problem where the repetitions are a constraint on the measurement scheme is much better motivation for this work. ", "limitations": "Authors adequately addressed the limitations and, if applicable, potential negative societal impact of their work. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Originality\n---------\nThe use of Thompson sampling with heteroscedastic noise is novel. \n\nSignificance\n-----------\n1. Authors test their algorithm in real-world settings. \n2. I think the pattern of trying to repeat measurements is indeed omnipresent in the life sciences, and methodologies which automatically incorporate it are of benefit to practitioners. \n\nClarity & Quality\n--------\nI was able to understand the paper, however the exposition is very dense.  ", "weaknesses": "The proof techniques used here are classical used in prior works mainly Chowbury & Gopalan 2017 and Desaultes et. al. 2014. Namely the RKHS proof of Gopalan and Batched version of it using the uncertainty sampling there. This work provides a Thompson sampling look at heteroscedastic bandits but the theoretical results are only of marginal interest to the community since they are straightforward extension of prior techniques. \n\nThe focus on Thompson sampling seems arbitrary. There are works which can address heteroscedastic as well as robust optimization but do not use Thompson sampling such as Kirschner & Krause 2018 and Makarova e.t al. 2021. Why Thompson sampling in particular is interesting remains unanswered. \n\nThe fact one performs repetitions is not theoretically motivated, but instead only practically motivated; or at least I took the liberty to make this conclusion. Information theoretically speaking, repeating the measurements might not be the best thing to do to decrease uncertainty overall. In fact probably optimizing an allocation over all points can lead to a better solution in long run (over multiple iterations). However, I think studying the problem where the repetitions are a constraint on the measurement scheme is much better motivation for this work, since life-sciences do have certain setup-costs per experiment. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for your insightful comments.\n\n---\n\n> The proof techniques used here are classical used in prior works... but the theoretical results are only of marginal interest to the community since they are straightforward extension of prior techniques.\n\nAlthough we have used some proof techniques from the previous works, we think that our analyses are in fact not straightforward extension of prior techniques. **Rigorously and coherently integrating the different components into our overall analytical framework required careful treatment and non-trivial efforts**. Therefore, we think that our technical theoretical contributions are in fact \"solid, non-trivial\" and \"strong\" (as commented by Reviewer 2mxf and Reviewer VcKK).\n\nMoreover, our algorithmic deisgns (e.g., our adaptive selection of the number of replications to guarantee a small effective noise level, lines 116-125), which are indispensable for our theoretical analyses to be hold, are also novel and can be of broader interest to the community. More importantly, in addition to our contributions from the pure theoretical perspective, **our theoretical results have also provided useful practical guidelines for our empirical implementation**. Specifically, our regret upper bound has provided us a natural and principled way to set the effective noise variance $R^2$ (lines 171-181), which we have indeed followed in our experiments (lines 249-256) and led to compelling empirical performances.\n\nIn addition, we have also performed empirical evaluations in real-world experiments for precision agriculture (using real-world data from precision agriculture) and AutoML, which we think constitute important empirical contributions and hence demonstrate the potential of our proposed methods in solving real-world problems.\n\n---\n\n> The focus on Thompson sampling seems arbitrary... Why Thompson sampling in particular is interesting remains unanswered.\n\nOur focus on Thompson sampling (TS) is in fact not arbitrary. Instead, we have adopted TS because its inherent randomness makes it particularly suitable for selecting a batch of inputs [20] in the batch setting we focus on (lines 44-45). In fact, using the inherent randomness of TS for batch selection is a simple and well-established method in BO (e.g., see [13, 20]), which both allows for the derivation of theoretical guarantees [20] and leads to strong empirical performances (e.g., the TuRBO algorithm from [13]). Thank you for pointing this out, and we'll clarify this after revison to avoid confusion.\n\n---\n\n> The fact one performs repetitions is not theoretically motivated, but instead only practically motivated... I think studying the problem where the repetitions are a constraint on the measurement scheme is much better motivation for this work, since life-sciences do have certain setup-costs per experiment.\n\nYou are correct that performing replications is mostly motivated from practical applications. Specifically, it is important to explicitly replicate each condition because in problems with large and heterogeneous observation noises, (1) replicating each input condition leads to more reliable observations and has indeed been repeatedly found [2,25,34] to improve the performances in such problems (lines 23-26), and (2) replicating each conditon is indeed what practitioners do in these real-world problems such as precision agriculture (according to the plant biologists we are collaborating with).\n\nWe agree that it will further strengthen our motivation by considering more real-world scenarios with motivations or requirements to perform replications, e.g., when performing new experiments with a different input condition requires expensive experimental setups as you suggested. We'll follow your suggestion and will revise the paper to discuss them as additional motivations. Furthermore, it is also an interesting topic to theoretically show the advantage of performing replications, which we'll also explore in future works.\n\nThank you very much for the suggestion.\n\n---\n\n> 1. Why do you put heavy focus on the theory? Are the theoretical bounds important for your real-life experiments?\n\n> 2. You provide a outline how to choose R, but is this what you use in your real lab-experiments.\n\nFirstly, our theoretical bounds can serve as assurance for practioners deploying our algorithms. For example, similar to many previous works on BO with theoretical guarantees, **the fact that our algorithms are asymptotically no-regret can serve as a hallmark indicating that our algorithms are well-behaved**.\nSecondly, our theoretical results have indeed provided us useful and practical guidelines on how to set the effective noise variance $R^2$, which is the most important parameter in our algorithm (lines 171-181). More importantly, **we have indeed followed this theoretical guideline to choose $R^2$ in our real-world experiments** (lines 249-256).\n\n---\n\n> 3. In real experiment - do you use uncertainty sampling as in the theorems?\n\nIn our experiments, we have used the simpler random search instead of uncertainty sampling as the initialization method. This is because it has been reported in previous works that uncertainty sampling is usually only a theoretical requirement and other initialization methods often lead to similar performances in practice [20]. To corroborate this, we have added an experiment using uncertainty sampling as initialization (Fig. 3 in the global response above), and the results show that it indeed leads to very similar empirical performances.\n\n---\n\nThank you again for your valuable comments. We hope our clarifications and additional results could improve your opinion of our paper."}, {"review_id": "vHde8YbWVX", "reviewer": "Reviewer_2mxf", "summary": "This paper introduces an algorithm for selecting both sampling locations and the number of replications in the context of heteroskedastic Bayesian Optimization. The authors propose to use Thompson sampling for batch candidate selection and a scheme for determining the number of replications for each element of the batch based on an effective noise variance. The authors propose three different variants of their algorithm, covering both the noiseless and noisy cases, as well as the mean-variance optimization case. They prove asymptotic regret bounds for each case (based on which they suggest the choice of effective noise variance). Finally, the paper empirically compares the proposed algorithm against baselines on synthetic and real-world problems.", "questions": "- Asymptotic no-regret:\n    - Wouldn't a uniform sampling strategy achieve the same? Are there any improved regret bound rates that we can get from the proposed approach vis-a-vis a uniform allocation?\n    - *Note*: I am not questioning the practical value of doing non-uniform allocation, but I wonder if the bound is more interesting - especially even with a uniform allocation I would assume that in a finite space you should asymptotically achieve similar rates (log(B)/sqrt(B)) in terms of the budget as if you used the proposed strategy. The non-asymptotic regime seems more interesting). Not that this is still with heteroskedastic noise, so this is somewhat different than comments on the homoskedastic noise case the authors make in l164.\n- What if the noise is heteroskedastic in the outcome value (rather than necessarily the input)? Can this be exploited in a different way?\n- What would a more principled approach for the n_max heuristic for avoiding samples on undesirable regions look like? Could this be handled in a more principled as part of the point generation?\n- For the unknown noise case, the GP modeling the empirical noise variance may produce negative predictions. How are you dealing with this? Have you considered modeling the log-variance with a GP instead (a common approach in other similar work)?\n- Finiteness of the domain: The discretization approach (\"we assume that the domain X is finite, since extension to compact domains can be easily achieved via suitable discretizations [4].\") is fine in theory (for regret bounds etc) but can become problematic in practice, especially in higher dimensions where the number of discrete points to sample needs to grow exponentially with the dimension to get similar coverage of the domain, which renders acquisition function optimization challenging. It seems reasonably straightforward to optimzie the acquisition fucniton using gradient-based optimization, maybe the authors may want to comment on that.\n- \"it is recommended to make nmin larger in experiments where the overall noise variance is large\" <- why is that recommended? It will make it easier to estimate the local noise variance, but it's not necessarily clear that this is going to result in better optimization performance.\n- \"When the noise variance is unknown [...] we approximate sigma_max^2 by the maximum observed empirical noise variance and update our approximation after every iteration\" <- This makes a lot of sense, but it feels like something is swept a bit under the rug here. Specifically, what does this do to the regret bound, which  depends on sigma_max^2? Is it still valid (just with an unknown factor)? Or is there additional work to show this?\n- The agriculture example is a nice real-world application and a good fit for the algorithm, however, I question the number of iterations that are being evaluated here. How long is a growing cycle until the leaf area and tipburn area can be evaluated? If this is on the order of months then 100 growth cycles seem a lot...\n- The regularization parameter lambda depends on the overall horizon T (and the appendix states that this is required for the theoretical results to hold) - however, in practice T may not be know if we are interested in anytime performance of the algorithm. How would one deal with this in practice?\n- Why are you optimizing the GP hyperparameters only after every 10 iterations and not after every iteration? \n- typo l97: \"upper on\"", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This is a well-motivated problem and of interest to the Bayesian Optimization research community as well as to practitioners.\n- While the basic ideas aren't novel, the specific approach taken is. It is also quite simple and easy to implement. \n- The theoretical results appear sound and are useful, especially the guidelines for how to choose the effective noise variance. The technical contributions are solid and non-trivial.\n- The paper is generally well written and the contributions are stated clearly.\n\n", "weaknesses": "- Theoretical results:\n    - While the results are interesting, it's not really clear to me to what extent the asymptotic rates from this approach differ from those that would be achieved by uniform sample allocation (see my questions below). This seems like a missing aspect to me that the authors should address.\n- Empirical results:\n    - It feels like the authors could have attempted harder to compare against other baselines.\n        - The comparison is only against sequential BO algorithms, which have a clear disadvantage in that they cannot, well, use batch evaluations (this includes RAHBO). While the authors acknowledge that, the obvious thing to do here would be to compare against parallel (batch) BO algorithms (using uniform budget allocation) such as qEI, qUCB, etc. that are readily available in the literature (and are implemented in many BO libraries). This would help better understand the performance of the proposed method in absolute terms (rather than solely in terms of improving over batch TS due to non-uniform allocation.\n        - Similarly, even though [34] may be heuristic, it would still be useful to compare against empirically (if that is reasonably straightforward to do).\n    - The improvements relative to a basic baseline such as simple batch TS do not strike me as particularly impressive.\n        - This may be due to the simple problems that were used. It would be helpful to see how the algorithm performs on higher dimensional problems (max dimension is 2) and what effect the dimension has on the significance of the ability to be able to allocate budget in a nonuniform fashion. \n        - Maybe these results are more impressive than I think, but if that's the case maybe the authors can try to explain this better?\n- Figures: The figures in the MT are tiny and extremely hard to read. I suggest moving some of the technical details from section 3 to the appendix and generally tighten up the writing and make some readable figures instead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for your detailed and insightful comments.\n\n---\n\n> Theoretical results: comparision with the theoretical regret bound achieved by uniform sample allocation.\n\nFor uniform sample allocation (i.e., we replicate every input a constant $n_0\\leq\\mathbb{B}$ number of times), the effective observation noise would be $(\\sigma_{\\max} / \\sqrt{n_0})$-sub-Gaussian, where $\\sigma_{\\max}$ is the maximum noise standard deviation. This would result in a regret bound which can be obtained by replacing the term $\\sqrt{R^2 / (\\mathbb{B} / \\lceil \\frac{\\sigma^2_{\\max}}{R^2} \\rceil  - 1)}$ in our regret bound (Theorem 3.1) by $\\sigma_{\\max} / \\sqrt{n_0}$. Here we ignore the non-integer conditions (e.g., ceiling operators) for simplicity. As a result, with our optimal choice of $R^2$ (lines 171-181), the above-mentioned term from our Theorem 3.1 can be simplified to $\\sigma_{\\max}/\\sqrt{\\mathbb{B}}$ (details omitted here), which is to be compared with the above-mentioned term $\\sigma_{\\max} / \\sqrt{n_0}$ from uniform sample allocation. Because $n_0 \\leq \\mathbb{B}$, **our regret bound** (with the scaling of $\\sigma_{\\max} / \\sqrt{\\mathbb{B}}$) **is guaranteed to be no worse than the regret of uniform sample allocation** (with the scaling of the $\\sigma_{\\max} / \\sqrt{n_0}$).\n\nThank you for pointing out this interesting comparison, we'll add the discussions here to the paper after revision.\n\n---\n\n> Empirical results:\n- Performance on more complex, higher-dimensional problems\n- Comparison against more baselines on batch BO\n\n**We've added two more complex real-world experiments with higher-dimensional input spaces** (Fig. 1 in our global response above), with input dimensions of $d=12$ and $d=14$. Our methods still consistently achieve compelling performances (especially with $\\kappa=0.3$, which is consistent with our original experiments, see lines 258-261).\n\nWe've compared with batch TS as the representative baseline batch BO algorithm because it's the most natural competitor to our algorithm, and batch TS is both simple and has been found to yield competitive empirical performances (e.g., the TuRBO algorithm [13], which showed impressive performances in various applications, also used batch TS for batch selection). As you suggested, we'll explore comparisons with additional baseline batch BO methods in future works.\n\n---\n\n> What if the noise is heteroskedastic in the outcome value (rather than necessarily the input)?\n\nTo clarify, in our setting, the noise variance $\\sigma^2(x)$ varies with the input $x$, and the realized noise $\\epsilon\\sim\\mathcal{N}(0,\\sigma^2(x))$ is added to the function value $f(x)$ to produce the outcome $y=f(x)+\\epsilon$. \n\n---\n\n> What would a more principled approach for the $n_{\\max}$ heuristic for avoiding samples on undesirable regions look like?\n\nA more principled approach for avoiding samples in undesirable regions would require taking into account the function value $f(x)$ at different $x$. Since the function is unknown, we may instead use the confidence bounds calculated by the GP which contains the function with high probability. We'll explore this in future works.\n\n---\n\n> The GP modeling the empirical noise variance may produce negative predictions.\n\nWe find that in practice, it's very rare for our **upper bound on the unknown noise variance** (line 218) to be negative. In practice, we clip this upper bound to account for such exceptions. This modelling choice is adopted since it naturally allows us to derive our theoretical guarantees, and it also leads to good empirical performances in our experiments. It's interesting to see if modelling the log-variance could further improve our performance.\n\n---\n\n> Finiteness of the domain: The discretization approach is fine in theory but in higher dimensions, it renders acquisition function optimization challenging.\n\nIt's indeed a generic challenge for BO to optimize the acquisition function in high-dimensional continuous input spaces, for which we can adopt commonly used techniques (e.g., L-BFGS-B) in BO. This is exactly what we've done in our added experiments with continuous high-dimensional input spaces (Fig. 1 in global response above).\n\n---\n\n> why is it recommended to make $n_{\\min}$ larger in experiments where the overall noise variance is large?\n\nWhen the overall noise variance is high, intuitively, an overall larger number $n_t$ of replications is needed. Hence, we recommend a larger number $n_{\\min}$ of minimum replications as a potentially useful heuristic.\n\n---\n\n> \"When the noise variance is unknown [...] we approximate $\\sigma^2_{\\max}$ by the maximum observed empirical noise variance...\". What does this do to the regret bound, which depends on $\\sigma_{\\max}^2$?\n\nWe in fact only need to approximate $\\sigma^2_{\\max}$ when we **choose the parameter $R^2$** by minimizing our derived regret bound (lines 171-181). So, our regret bounds (e.g., Theorem 3.1), which **hold for all values of $R^2$**, are still valid.\n\n---\n\n> I question the number of iterations in the agriculture example. How long is a growing cycle?\n\nThe growing cycle is around 1-2 weeks. Also note that our algorithms in fact already outperform the other methds before 100 iterations.\n\n---\n\n> The regularization parameter $\\lambda$ depends on the overall horizon T  - however, in practice T may not be known.\n\nIt's a common practice in BO to assume that the overall horizon $T$ is known [6,33]. When $T$ is not known, we can use the doubling trick commonly adopted in multi-armed bandits to obtain anytime algorithms, or simply use an estimation of $T$.\n\n---\n\n> Why are you optimizing the GP hyperparameters only after every 10 iterations?\n\nIt's a common practice to update the GP hyperparameters after multiple iterations, mainly to save computational cost.\n\n---\n\nThank you again for your valuable feedback. We hope our clarifications and additional results could improve your opinion of our paper.\n"}, {"review_id": "T7NA068gSW", "reviewer": "Reviewer_VcKK", "summary": "The paper introduces a batch Bayesian optimization method for the setting where experiments can be very noisy, and therefore it is common practice to repeat many experiments. The framework allows for both the selection of the experiment design and how often each experiment is replicated. The authors introduce three method: BTS-RED-Known (for the setting where the noise is known), BTS-RED-Unknown (for the setting where the noise is unknown), and Mean-Var-BTS-RED, for the setting where we want to trade-off finding the optimum while obtaining less noisy observations (called risk-averse optimization). \n\nIn every case the experiment designs are chosen using a variation of Thompson Sampling (with scaled variance). The number of replications is then chosen based on the noise level at the experiment design, an upper-bound is used when the noise is unknown. For risk-averse optimization, a linearized sum of the objective and the noise level is used. For every algorithm theoretical bounds are found on the regret, which are proven to be sub-linear. The number of repeated experiments depends on the hyper-parameters $R^2$, but a theoretical justification for its value is given. \n\nEmpirically, the method is shown to outperform other Bayesian Optimization algorithms in synthetic examples, and two real world examples: one in Precision Agriculture, and one in AutoML.", "questions": "- Does *asymptotically no regret*  simply mean that the method converges? Or that convergence is sub-linear?\n\n- Am I correct in assuming that the GPs that you are fitting when using BTS-RED are homoskedastic with a small noise level?\n\n- Is there an intuitive meaning to the variable $R^2$? Or is this a hyper-parameter to choose? I think it would be good to talk about it earlier, as it is often mentioned, but not discussed until page 5.\n\n- When doing Thompson Sampling for for BTS-RED, the variance of the GP is scaled (e.g. line 4 in algorithm 1). Is this done for theoretical guarantees or for some other reason?\n\n- I do not fully understand section 3.2.2 (Upper Bound on Noise Variance Function). If the posterior of $g$ is a GP is the result that $-\\mu_{t-1}'(x) + \\beta_t' \\sigma_{t-1}'(x)$ an upper-bound not obvious? If we talk about the general case where $\\epsilon'$ is not necessarily Gaussian, then the posterior is not necessarily a GP which could mean my confusion is just a typo in line 214.\n\nMinor formatting issues:\n- I found the figures and their font sizes to be too small and difficult to read.\n- In Theorem 3.1 $\\tau_{t-1}$ and $\\beta_t$ are defined and then not used in the Theorem\n\n\n\n", "limitations": "Limitations are mentioned in the Conclusion section. Other limitations I mentioned (e.g. lacking empirical evaluation) seem like they could be easily addressed by the authors in a single iteration of the paper. There is no obvious negative social impact.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Originality: To the best of my knowledge, the proposed algorithm is novel. While it combines simple ideas, it does so carefully and effectively. In particular, the theoretical analysis of the algorithms is very strong, providing a choice for the hyper-parameter $R^2$, and proving regret bounds for the algorithm.\n\nQuality: The algorithm is built up from proved and tested methods in the literature, and a strong theoretical justification is given for using them. Empirical evidence of the algorithm performance is given, but in a limited capacity. The creating of a data-set (for the agriculture example) based on real-life experiments makes the experiment particularly strong. \n\nClarity: The method is well explained, and the theoretical implications are clear. There is a good choice of figures, even if they are difficult to read. \n\nSignificance: The paper is well motivated, experiment replication due to noise is common in many areas of science and it is not usually taken into account by classical Bayesian optimization algorithms. Making BO more practical to the wider scientific community is very important, and papers like this one take a big step towards it.", "weaknesses": "While the motivation, and justification for the algorithms is clear, I find the empirical evidence to be lacking. My main concerns are:\n\n- The main framework seems to fit a _homoskedastic_ GP to the mean of the replicated data (which will, by design, have very small noise so it should not be a problem). Then, if needed, a second homoskedastic GP is used to model the variance. However, I would argue the most naive and natural solution is to simply use a heteroskedastic GP as the surrogate model in the first place. This is not a problem in itself, however, I believe for a fair comparison against Thompson Sampling a homoskedastic GP should be used. Otherwise the model misspecification could be problematic and lead to poor performance (maybe Figure 1d could be explained by this?). It is unclear from the paper if this is the case. In simpler terms, *it is unclear wether the empirical advantage of BTS-RED comes from a better algorithm, or a better model*. If a heterskedastic GP is used, then is should be clarified, otherwise the paper would benefit greatly from including it.\n\n- The extent of the experiments seems limited. Only a single 1d example is shown, and then both real world examples are 2d. It would be good to include more examples. Similarly, the budget is fixed to $\\mathbb{B} = 50$ for all experiments, it would be good to see how the algorithm performs for smaller (and perhaps larger) budgets. \n\nOther minor issues:\n\n- The novelty of Mean-Var-BTS-RED seems overstated, is it simply solving a multi-objective problem through linearization? \n\n- The heuristic for handling unused budget seems a little problematic. Given you get some observations (albeit noisy), if they clearly pointed to a sub-optimal design it seems wasteful to still evaluate the objective further at the specific location.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for your constructive feedback.\n\n---\n\n> - The main framework seems to fit a homoskedastic GP to the mean of the replicated data... (and) a second homoskedastic GP is used to model the variance. However, I would argue the most naive and natural solution is to simply use a heteroskedastic GP as the surrogate model in the first place. This is not a problem in itself, however, I believe for a fair comparison against Thompson Sampling a homoskedastic GP should be used... If a heterskedastic GP is used, then is should be clarified, otherwise the paper would benefit greatly from including it.\n\nYou are correct that our algorithms fit two homoskedastic GPs to model the mean and the variance, respectively. If we understand corretly, you are asking whether we have used a homoskedastic or heterskedastic GP for the baseline of batch Thompson sampling (TS) in our experiments: We have used a homoskedastic GP, which is consistent with the homoskedastic GP used in our algorithms and with the previous works on batch TS. As you suggested, we've added an experiment in which we replace the homoskedastic GP in batch TS by a heterskedastic GP. The results (Fig. 4 in our global response above) show that the use of heterskedastic GP leads to comparable (slightly better) performances for batch TS, but it is still consistently outperformed by our algorithms. Therefore, we think this can serve as additional evidence to justify that our empirical advantage comes from better algorithms.\n\nIn addition, to the best of our knowledge, using a single heteroskedastic GP as the surrogate model makes it difficult to perform theoretical analyses. In contrast, the use of two homoskedastic GPs in our methods has allowed us to derive strong theoretical guarantees.\n\n---\n\n> - The extent of the experiments seems limited. Only a single 1d example is shown, and then both real world examples are 2d. It would be good to include more examples.\nSimilarly, the budget is fixed to $\\mathbb{B}=50$ for all experiments, it would be good to see how the algorithm performs for smaller (and perhaps larger) budgets.\n\nAs you suggested, we've added more experiments (see our global response above).\nFirstly, we've added two experiments with **higher-dimensional continuous input spaces** (12d and 14d, see Fig. 1 in our global response). Our methods still consistently achieve compelling performances (especially with $\\kappa=0.3$, which is consistent with our original experiments, see lines 258-261).\nWe've also added two experiments with different values of the budget $\\mathbb{B}$: $\\mathbb{B}=100$ and $\\mathbb{B}=30$ (see Fig. 2 in our global response), in which the performance advantages of our methods (especially $\\kappa=0.3$) are consistent with those shown in our original paper (with $\\mathbb{B}=50$).\n\n---\n\n> - The novelty of Mean-Var-BTS-RED seems overstated, is it simply solving a multi-objective problem through linearization?\n\nWe have indeed designed our Mean-Var-BTS-RED algorithm based on the scalarization/linearization technique, which is a common technique for multi-objective optimization. However, our theoretical analysis for Mean-Var-BTS-RED are novel to the best of our knowledge, and they posed additional technical challenges compared with the analysis of our BTS-RED-Unknown.\n\n---\n\n> - The heuristic for handling unused budget seems a little problematic. Given you get some observations (albeit noisy), if they clearly pointed to a sub-optimal design it seems wasteful to still evaluate the objective further at the specific location.\n\nWhat you have suggested here is indeed an interesting potential extension. However, as you have also alluded to, the observations are likely very noisy due to the incomplete evaluations, and hence using these potentially noisy observations to decide whether to continue the unfinished experiment may lead to unreliable decisions. Therefore, this extension is likely to require new algorithmic designs, which we will explore in future works. Thank you for the suggestion.\n\n---\n\n> - Does asymptotically no regret simply mean that the method converges? Or that convergence is sub-linear?\n\nTo clarify, our methods being asymptotically no-regret means that our cumulative regret is sub-linear. This also implies that our simple regret asymptotically goes to 0; intuitively, this means that our methods are guaranteed to be able to query the global optimum asymptotically, in other words, our method is guaranteed to converge. Please see lines 90-104 for more details.\n\n---\n\n> - Is there an intuitive meaning to the variable $R^2$? Or is this a hyper-parameter to choose? I think it would be good to talk about it earlier, as it is often mentioned, but not discussed until page 5.\n\nThe parameter $R^2$ can be seen as the *effective noise variance* for every observations (lines 122-124). We have used our theoretical regret bound to derive a guideline on how to choose $R^2$ (lines 171-181), which we have indeed followed in our experiments (lines 249-256). To clarify, we had in fact already discussed about $R^2$ on page 3 (lines 118-124), and we'll revise this part to make the discussion clearer.\n\n---\n\n> - When doing Thompson Sampling for for BTS-RED, the variance of the GP is scaled. Is this done for theoretical guarantees?\n\nYes, this is done for the theoretical guarantees following the previous works [6].\n\n---\n\n> - I do not fully understand section 3.2.2 (Upper Bound on Noise Variance Function). If the posterior of $g$ is a GP, is the result that $-\\mu'\\_{t-1}(x)+\\beta'\\_t\\sigma'_{t-1}(x)$ is an upper-bound not obvious?\n\nThis upper bound naturally arises only given the assumption that the noise $\\epsilon'$ is sub-Gaussian. We think that it may not be obvious to see that this assumption is reasonable, and hence we have justified why this assumption is reasonable in lines 201-210.\n\n---\n\nThank you again for your insightful comments. We hope our additional clarifications and results could improve your opinion of our paper."}]

Author rebuttal:

We'd like to thank all reviewers for your insightful comments, and for acknowledging our contributions.

Specifically, we are encouraged to hear that our methods are "easy to implement" (Reviewer QJyu and Reviewer 2mxf) and hence practical, and that our contributions are "of interest to the Bayesian optimization research community as well as to practitioners" (Reviewer 4YBP and Reviewer 2mxf). Regarding our theoretical contributions, Reviewer 2mxf has commented that **"our technical contributions are solid and non-trivial"**, and Reviewer VcKK has mentioned that **"the theoretical analysis of the algorithms is very strong"**. Our empirical contributions have also been acknowledged, for example, Reviewer VcKK has commented that **"papers like this one take a big step towards making BO more practical to the wider scientific community"**.

Here we provide some important additional experimental results, and we'll address your individual questions in our separate responses below.

---

A common suggestion to further improve the empirical contributions of our paper is to add **real-world experiments with higher-dimensional continuous input spaces**. Therefore, following your suggestion, we have added two real-world experiments with 12-dimensional and 14-dimensional continuous input spaces, respectively:

- Lunar landing experiment: Here we tune $d=12$ parameters of a controller which is used to control a lunar lander in the OpenAI gym environment, in order to maximize the cumulative rewards in an episode.
- Robot pushing experiment: Here we tune $d=14$ parameters controlling a robot, in order to make it complete a task involving pushing objects. The goal is also to maximize the cumulative rewards.

Both experiments are commonly used benchmarks in the literature of high-dimensional Bayesian optimization [13]. More importantly, for every evaluated set of controller parameters in both experiments (i.e., every input $x$), the observation (i.e., cumulative rewards) is noisy due to random environmental factors. In addition, the noise may be heteroscedastic. For example, an effective set of parameters which can reliably and consistently control the robot is likely to induce small noise variance, whereas some ineffective sets of parameters may cause radically varying behaviors  and hence large noise variances. Therefore, these experiments are also suitable for the application of our algorithms.

The results are shown in Fig. 1 in the attached pdf, which demonstrate that **in these experiments with high-dimensional continuous input spaces, our algorithms still consistently achieve compelling performances** (especially with  𝜅=0.3 , which is consistent with our original experiments, see lines 258-261).

We think that these additional results serve as further evidence for the empirical effectiveness and robustness of our algorithms. We sincerely hope these results, together with our individual responses below, could improve your assessments of our paper.

Meta-review: This manuscript considers the problem of Bayesian optimization for batch experimental design. The authors focus on the question of replications, where the experimenter may wish to make multiple independent measurements for the same design in order to reduce uncertainty of the resulting estimate. In the presence of heteroskedastic noise, we might wish to use a variable/adaptive number of replications in different regions of the design space, which raises interesting questions regarding experimental design. The authors propose a novel algorithm for this setting and provide both theoretical convergence guarantees and a empirical investigation into its performance.

Overall, the reviewers agreed that the proposed algorithm, albeit simple, is well motivated and a valuable contribution that will be of interest to the NeurIPS community. The reviewers also generally agreed that the empirical study was well designed and that its findings provided convincing evidence of the algorithm's real-world performance.

I encourage the authors to reflect upon the reviews and discussion in updating their manuscript.
Decision: Accept (poster)