Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal
Authors: Juliusz Ziomek
Masaki Adachi
Michael A Osborne
Venue: NeurIPS 2024 poster (2024)
Keywords: Bayesian Optimisation; Unknown Hyperparameters; Regret Bounds
Primary area: probabilistic_methods

Abstract: Bayesian Optimization (BO) is widely used for optimising black-box functions but requires us to specify the length scale hyperparameter, which defines the smoothness of the functions the optimizer will consider. Most current BO algorithms choose this hyperparameter by maximizing the marginal likelihood of the observed data, albeit risking misspecification if the objective function is less smooth in regions we have not yet explored. The only prior solution addressing this problem with theoretical guarantees was A-GP-UCB, proposed by Berkenkamp et al. (2019). This algorithm progressively decreases the length scale, expanding the class of functions considered by the optimizer. However, A-GP-UCB lacks a stopping mechanism, leading to over-exploration and slow convergence. To overcome this, we introduce Length scale Balancing (LB) - a novel approach, aggregating multiple base surrogate models with varying length scales. LB intermittently adds smaller length scale candidate values while retaining longer scales, balancing exploration and exploitation. We formally derive a cumulative regret bound of LB and compare it with the regret of an oracle BO algorithm using the optimal length scale. Denoting the factor by which the regret bound of A-GP-UCB was away from oracle as $g(T)$,  we show that LB is only $\log g(T)$ away from oracle regret. We also empirically evaluate our algorithm on synthetic and real-world benchmarks and show it outperforms A-GP-UCB and maximum likelihood estimation.

Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal
Juliusz Ziomek Masaki Adachi Michael A. Osborne',
Machine Learning Research Group, University of Oxford
Toyota Motor Corporation
* Corresponding Author
(juliusz, masaki, mosb)@robots.com ox. ackk
Abstract
Bayesian Optimization (BO) is widely used for optimising black-box functions but requires us to specify the length scale hyperparameter, which defines the smooth- ness of the functions the optimizer will consider. Most current BO algorithms choose this hyperparameter by maximizing the marginal likelihood of the observed data, albeit risking misspecification if the objective function is less smooth regions we have not yet explored. The only prior solution addressing this problem with theoretical guarantees was A-GP-UCB, proposed by Berkenkamp This algorithm progressively decreases the length scale, expanding the class of functions considered by the optimizer. However, A-GP-UCB lacks a stopping mechanism, leading to over-exploration and slow convergence. To overcome this, we introduce Length scale Balancing (LB)-a novel approach, aggregating mul- tiple base surrogate models with varying length scales. LB intermittently adds smaller length scale candidate values while retaining longer scales, balancing ex- ploration and exploitation. We formally derive cumulative regret bound of LB and compare it with the regret of an oracle BO algorithm using the optimal length scale. Denoting the factor by which the regret bound of A-GP-UCB
(2019).
away from oracle as gT)), we show that LB is only log (T) away from oracle regret. We also empirically evaluate our algorithm on synthetic and real-world benchmarks and show outperforms A-GP-UCB, maximum likelihood estimation and MCMC.
Introduction
Bayesian Optimisation (BO) [16] has proven to be an efficient solution for black-box optimisation problems, finding applications across science, engineering and machine learning 12
IS 23] As
a model-based optimisation technique, BO constructs a surrogate model of the black box function, which is typically Gaussian Process (GP) 44) However, construct this surrogate, we need to specify our expectations about the smoothness of the black-box function. In the case of GP, the choice of smoothness reflected in the selection of an appropriate length scale value for the kernel function. Selecting smaller length scales allows us model less smooth functions and, as such, expands the class of all possible black- box functions the optimiser will consider. At the same time, it makes the convergence of the algorithm slower, due to an increase in the number of possible 'candidate" functions, the algorithm has to explore the space much more. As such, we wish to consider the smallest possible class of functions that still contains the black-box function we wish to solve. This translates to selecting some optimal length scale value, which neither too short nor too long.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Appropriate selection of the length scale param- eter can be challenging. Typical practice to fit the length scale value by maximum likeli- hood estimation (MI.) on the observed data we have collected thus far. However, it ís en- tirely possible that the function changes less smoothly in the regions we have not explored yet, as shown in Figure [ As such, we cannot guarantee that maximising the likelihood of the limited, observed data will find a length scale value such that the black-box function will lie in the space of considered functions. A previously proposed algorithm called A-GP-UCB [6] ap- proached this issue by progressively decreasing the length scale value, and as such increasing the class of functions considered by the optimiser. As consequence, at some point, it must con- tain the black-box function we are trying to opti- mise. However, the algorithm has no mechanism for stopping and as such the length scale value will decrease indefinitely, inexorably expanding the class of considered functions. This causes over-exploration, making the convergence much slower compared to an optimiser that knows the optimal length scale value.
True 0 = 0.1
MLE 0 - 0.3
UCB
UCB
0.0
0.5
1.0
0.0
0.5 X
1.0
X
Figure I: An objective function (proposed by (6] that illustrates the importance of length scales to BO. The blue line shows a GP fit with shaded regions representing one standard deviation. The length scale value was set to the optimal value on the left and was selected by MLE on the right, based on five points represented by dots. While the optimiser with the MLE of length scale persistently selects suboptimal value of x 1, the optimiser with the optimal length scale can spot the hidden peak leading to finding the maximum at xt 0.3.
A-GP-UCB is suboptimal because it never returns to previously trialled, longer length scales. Observe that if trying shorter length scale value does not improve function discovery, opting for a longer scale is a safer choice, preventing excessive exploration. To build an algorithm following this intuition, we could have a number of base optimisers. each utilising different length scale value, and aggregate them into a single 'master' optimiser. By knowing how explorative each of the base optimisers is, the 'master' optimiser could select the most suitable one at each iteration, so as balance exploration and exploitation. Within the literature of multi- multi-armed bandit problems, number of rules for aggregating base algorithms have been proposed [ل however, the performance of those 'master' algorithms worsens with the number of base algorithms. This prohibits us from directly applying 'master' algorithms to the unknown hyperparameter problem, as the length scale is a continuous parameter and has infinitely many possible values.
Within this work, we extend one such aggregation scheme, called regret- balanncllnnn to handle infinitely
many learners, so that could tackle the problem of BO with unknown hyperparameters. We propose an algorithm called Length scale Balancing GP-UCB
A-GP-UCB
Proportion
θ.
(LB-GP-UCB) which aggregates a number of base optimisers with different length scale values and grad- ually introduces new base optimisers, equipped with smaller length scales. Instead of permanently decreas- ing the length scale value, as done by A-GP-UCB, LB-GP-UCB occasionally introduces new base Iearn- with smaller length scale values, while still main- taining base learners with longer ones. As such, if one of the longer length scales is optimal, we will be able to recover performance close to the one of the oracle optimiser utilising that optimal length scale. Denoting the factor by which the regret bound of A- GP-UCB was away from oracle as (TT), we show that LB-GP-UCB is only gog)(T) away from ora- cle regret. We also conduct empirical evaluation and show LB-GP-UCB obtains improved regret results on a mix of synthetic and real-world benchmarks com-
0.1
LB-GP-UCB (Ours)
MLE
MCMC
0.1
0.2
Length scale
Figure 2: Histogram showing how often (as proportion of iterations) each algorithm se- lected a given length scale value while op- timising the Michalewicz function over ten seeds. 0- corresponds to an estimate of opti- mal length scale value. See $ for details.

---

pared to A-GP-UCB, MLE and MCMC. We show the histogram of length scale values selected by each method on one of the benchmark problems in Figure 0' represents an estimate of optimal length scale value on this problem (see $ for details). We can see that the length scale values selected by LB-GP-UCB are close to the estimated optimal value, whereas MLE and A-GP-UCB miss this value by respectively over and under-estimating, matching our predictions. We summarise contributions below.
We propose LB-GP-UCH and show that compared to A-GP-UCB its regret bound is loga- rithmically closer to the bound of an oracle optimiser knowing the optimal length scale.
We extend our algorithm to also handle the case of unknown output scale (function norm) alongside the length scale
We show the empirical superiority of our algorithm compared to MLE, MCMC and A-GP- UCB on a mix of synthetic and real-world problems, and conduct an ablation study showing increased robustness of our method.
2 Problem Statement and Preliminaries
We consider the problem of maximising an unknown black-box function f X R on some compact set X' c R.. At each time step t. we are allowed to query a function at selected point at E X' and observe noisy feedback yt = fax)) + c. where 6 SubGauss(oz). We wish to find the optimum x* = = (x) We define the instantaneous regret to be r; = f(x") (xx) and cumulative regret Rr 2t=1 Pts and wish minimise it. We assume
given some
parametrised by a length scale value E R and we denote its associated Reproducing Kernel Hilbert Space (RKHS) as H(K)). We assume that at least for certain values of 0, the black-box function f belongs to this RKHS, i.e. E f E H(*"). Concretely, we will consider two popular types of kernels: RBF and y-Matérn, defined below for completeness:
kernel function k. (xx, x') = le(
= #: s')
x 1
MRBF ar, x²) exp
82
22-v
V2v |/0 122yl10-a11
a''l
K, 122y x'l| 0
Matém (I, x²)
T(v)
where r'-) is the Gamma function and (-)
(.) is the modified Bessel function of the second kind of order v. Without the loss of generality, we assume (-)-)) < 1 for all IR+,, In the rest of the paper, if we do not specify the type of the kernel, it means the result is applicable to both types of kernels. If we fit GP model with a kernel 1. (x,x') ) to the data so far, D.-1 = ((x,, (+)]== we obtain the following mean 1 (x) and variance (ox)))((x) functions:
(x)( (
(K) 1-1 1
(0f_))(())) = k2 (x. bo_ (x:) (K)
(x),
where Vt-1 E R1-1 with elements (y); Ul, k2 (x) R with elements k2 kx(x;; k² k0(xx, xx) and similarily K. E - with entries (K?_ = kd0 (x;, m.)) and o² is the regulariser factor [TI with identity matrix I. If we were to any length scale value such that f H (k'), then can obtain certain guarantees about the predictions made by the GP model, as stated next.
Theorem 2.1 (Theorem 2 of (.). Let J E H (k²), such that || S B and set 8 B N / (k*) + 1+ In(1/8A)), where IT(k") ) is an upper bound 1 log I t K Ik which depends on the kernel and length scale choice. Then, with probability at least d for all x E X and = I,...,T:
ff(z) - (x) S B0 (z)
Note that the Theorem 2.1 relies on the quantity I, (R.9), also called maximum information gain (MIG). The next proposition, proven in Appendix A provides bounds on (1.0 for RBF and u-Matérn kernel and shows the explicit dependence on length scale hyperparameter 0.
3

---

Proposition 2.2, We have that Ir )= - O (k)):
For an RBF kernel "rr (rr(k)) = nu log(T)
1
For v-Matérn kernel yr (k=) = 6a T 2 log(T) wold
dia+
Based on the GP model, a typical BO algorithm constructs an acquisition function, which tells us how 'promising' given point is to try next. We will focus on the commonly used Upper Confidence
Bound (UCB), defined as UCB 8. (z) = ( + f -f The GP-UCB algorithm [36 [T] fits a GP model and utilises the UCB criterion to select new points to query. Such an algorithm admits high-probabllee probability regret bound as stated by the next Theorem.
Theorem 2.3 (Theorem 2 in M... Let us run a GP-UCB utilising a GP with a kernel k and the exploration bonus of B = B + ON (N(2((I(())) + (n(1/5A)) on a black-box function f E H(k)) such that IIffl I B. Then, with probability at least 1 - it admits the following bound
on its cumulative regret Ry S O (T)), where Ra.B
B (T) = vT (B (BVTr(kk)) + (TT((())))
In our notation, note the distinction between the regret of an algorithm ftr and the scaling of its bound R (T). As the maximum regret we can possibly suffer at any time step, while optimising function with property |f B, is bounded T 2B obeys the property R (t + 1) - R (t) < 2B for all t = 1...., T - 1, as otherwise the bound can be trivially improved.
going to assume the bound
In order for the bound of Theorem 2. to hold, we need to know the length scale and an upper bound on the RKHS norm B of the black-box function for the given kernel h. Inspecting the regret bound together with Proposition 2.2 we see that selecting the smallest B (i.e. the tightest bound) and the longest length scale results the smallest R (T). Note that the same function f().. can have different RKHS norms under kernels with different length scale values. As such, to obtain the optimal scaling of the regret bound, one needs to jointly optimise for 0 and B. The optimal hyperparameters are thus 0r, B* = arg ming, BERI R such that ||fl I B We assume we are given some initial Gg 2 8* and Bg S B*. As explained in the introduction, in practice, those initial values could be found by maximising the marginal likelihood for small number of initial data points. We now notice one interesting property. In the case of RBF and v-Matérn kernels, if we change the length scale value from Og to 0 and the norm bound from Bo to B, we get that the regret bound with those new hyperparameters scales as follows:
((1
B Bo
6o
d/2
C00) Boy (h(00) + (80 rT m((k))))
R (()
(T) =
VT VT
Since (rr)k" is increasing in T. for large enough T we have B < / (ke)) and any B < (0) d/2 Bo does not affect the bound's order dependence. As such, whenever we decrease lengthscale to 6, we can increase norm bound by (2x) 4/2 essentially "for free". As such, we are going to use d-dependent norms in the form of B(8, .N- = (e y4/2N, where N is the norm bound under 8g and becomes the new hyperparameter wish select, instead of B. The optimal values of hyperparameters under this new parameterization are thus 0*, ~ = arg min R (()) subject to || S B(0*, N*). Notice that minge (00, NN* = N and as such it does not make sense to try values of N smaller than Bo. Using this new parameterization brings important benefit, as stated next.
Lemma 2.1 (Consequence of Lemma in ()) In case of RBF and Matérn kernels, for any 0 < 0* and N > N we have that | B),
We will thus refer any pair (0, such that 0 0+ and N 2 N well-specified hyperparame- ters, as the GP-UCB admits a provable regret bound when they are used (albeit that bound might not be optimal). For simplicity, we are now going to assume that N is known and proceed with solving the problem of only one unknown hyperparameter 0*. We will thus be writing 88 = 3 ((0.N") (CB UCB, 8, (,B(P.N") BB().N)((.) and Rf(.) R (.).)))) However, we would like emphasise that the algorithm we will propose throughout this paper can be extended to the case when B is also an unknown hyperparameter, which we do in Appendix F
This is because f(x") f(x:) s l| & 2|] & 2B.

---

3 Length scale Balancing
Aggregation schemes describe set of rules that a master algorithm should follow while coordinating a number of base algorithms. One such scheme is regret-balancing with elimination [33] This scheme assumes each of the base algorithms comes with a suspected regret bound, which is high-probability bound on its regret that holds if the algorithm is well-specified for the given problem, but might not hold if the learner misspecified. The scheme always selects the base algorithm that currently has the smallest cumulative regret according to its suspected bound. This ensures that the regret of the master algorithm will not too far from the regret of the best well-specified candidate. also removes base algorithms that underperform, compared to others, by more than their suspected bound, as this means their bounds do not hold and, with a high probability, are misspecified.
Our idea is to use regret balancing with elimination while having each base algorithm be a GP-UCB algorithm with a different value of the length scale hyperparameter. Let us now discuss how to identify candidates for the length scale values. We propose the usage of a candidate-sugeen function q()) : N + R+ such that the ith candidate length scale value to consider given by q()).
Definition 3.1. Let us define the length scale candidate- function g(-) - R
mapping for each E N of form:
q
tue i/d
We want to ensure that one of the candidates we will eventually introduce will be close to l Let us denote 0 = arg max,eN =0())aa (()) to be the largest length scale suggested by our candidate- suggesting function that is still smaller than 0* Observe that || S B00 N+) and thus Ô is the largest well-specified length scale value among suggested candidates. As such, the regret bound of the best base learner is R (T) and we hope that the regret bound of a master algorithm aggregating this learner with others will be close to R (T). Comparing with the regret bound of the GP-UCB algorithm utilising the true optimal length scale value RO'(T) (T), we get the result stated by the following Lemma 3.1] proven in Appendix C
Lemma 3.1. In the case of both RBF and v-Matérn kernel, we have that:
R& (T) Rdd (T) = (1).
This Lemma shows that the regret bound of the best of our base algorithms is only a constant factor away from the bound of the algorithm using the optimal length scale value. However, as for any E N, we have q(i) > 0, and the candidate-sugga candidate-suggesting suggesting function g(-) introduces infinitely many candidates. As we can only aggregate a finite number of base algorithms, we thus propose to gradually introduce new optimisers equipped with new candidate length scale values. Observe that if we stopped our quantisation at some lower bound 0z, then we would create a maximum of q (0r, candidates, that is, d In( Bo ). However, this would require us to know a sure lower bound on the optimal length scale 0z
value. Since we do not have this knowledge, we could employ a mechanism similar to A-GP-UCB, where we progressively decrease the suspected lower bound value (t(t)
0g based on some
g(()*
growth function gt)). Observe that since In 80_ In(g(t)), the number of candidate values
grows only logarithmically with the growth function g((). Same as for A-GP-UCB, this growth function needs to be specified by the user, and we describe how this choice can be made $5) However, we would like to emphasise that, unlike A-GP-UCB which simply sets its length scale value to (t). we instead introduce new learners with shorter length scale values, while still keeping the old learners with longer values. This strategy is thus more robust to the choice of the growth function, which is reflected better scaling of the regret bound we derive later. In Algorithm [ we present -B-,, algorithm employing this mechanism. We now briefly explain the Togic behind its operations.
The algorithm starts in line T initialising the set of candidates to just the upper bound 6g. Later on, lines 14 16) new candidates are introduced using the candidate- suudiddttsuugestting function q(-) at a pace dictated by the growth function g()). Typically in aggregation schemes, each one of the base algorithms is run isolation. However, there is nothing preventing us from making them share the data and as such, selecting a base algorithm in our case simply amounts to choosing the length scale
5

---

Algorithm Length scale Balancing GP-UCB (LB-GP-UCB)
Require: initial length scale value d6: suspected regret bounds R
growth function 9(-); confidence parameters (4)]_ and {38) Tt=l
1: Set Do = 0, θ {On}. Sg = 0 for all 0 E θ length scale counter / =
2: for = 1, 1,... do
3: Select length scale 0g = arg mingge, [2 +
4: Select point query x; = arg max UCB =EX
5: Query the black-box yt f(x)) + Et
6: Update data buffer D, = D U (x,, 3t2
7: For each 0 E e set S. = {T = l....,t. t 0r = 0} Initialise length scales for new iteration O O
8:
9:
if Vace, | 7 0 then
10:
Define (.) = (15:) Eresp Ur
|s
[# Eliminate underperforming length scale values)
0.+1 = {0 E 0, (0) + T Eest 8200 (x,) maxg Le (0))
12:
13:
end if
14:
if
(l + 1) 5
0g
then
g(t)
15:
0 = 0441 U (g(l+ 1)} (# Add shorter length scales}
16:
[ 1=1++1
17:
end if
18:
end for
value we will use to fit the GP model at given time step I, which done in line This choice done by the regret-balancing rule 0, = arg mingee, Re 1), with Ro (-) defined as in Theorem 2.3 and Sf being the set of iterations before t at which length scale value 0 was chosen. Note that we only need know the scaling of the bound up to constant. This rule implies that lower length scale values will be selected less frequently than higher values, as their regret bounds grow faster. After that, in line 4, the algorithm utilises the acquisition rule dictated by a model fitted with the selected length scale value to find the point to query next, Zt. The idea is that, occasionally, O, will be set to one of the smaller values from O, and, that results in finding significantly better function values, then the rejection mechanism in lines 12 will remove longer length scales from the set of considered values, θ, Otherwise, we will keep all of the length scales and try again after some number of iterations. We now proceed to derive regret bound for our developed algorithm.
4 Regret Bound and Proof Sketch
We now state the formal regret bound of the proposed algorithm, provide brief sketch of the proof and discuss the result.
Theorem 4.1. Let us use confidence parameters of & = 20 log (d))ng(())==+()) log 35 and +N 2212222/11 + 1+ In(20)), then with probability at least 1 8, the cumulative regret RT of the Algorithm 7 admits the following bound:
3. = B(,, +
(10 RT O ((10+ (10++))B 1-0((t++))))
(16 (T) (T)+ +
((0=)
Og d
+ )
0
where to = g- (c-1//gg)))) and i = d (T))
Proof. (sketch) We provide sketch of the result here and defer the proof to Appendix D
Let us denote by to the iteration at which the first well-specified length scale < 8*) is added to the candidate set in line 15 This will happen at the first iteration after g 1- where the condition in line 14 will trigger. Given the ratios between consecutive candidates suggested by g(-). we get that

---

Table 1: Comparison of optimality for A-GP-UCB and LB-GP-UCB for fixed functions g(-) and b(-). R (T) refers to the scaling of the regret bound of an oracle optimiser, knowing the optimal hyperparameters. See Appendix H for more details.
Algorithm
Optimality (T)R
Unknown 0
Unknown and B
A-GP-UCB 6
((g(T))) ((dlng(T)
O(b(T)g(TT))) ((dIn
LB-GP-UCB L.NB-GP-UCC (ours)
to 1- 1//]]. On iterations up to, potentially suffer the highest possible, thus the cumulative regret can be bounded as:
RT Σ TE+
re 2B3 RT, t
Σ
where Rr the regret of the algorithm after to. Let define by T the set of iterations, where we reject at least one length scale value in line 12
We thus have:
1 Oo
2B RT = Σr= rs Σn ET
+ Σn
Σ Tb
TET
1ºT
where the second inequality comes from the fact that we cannot reject more candidates than we have introduced in total. The remaining thing to to bound Σigr Tz. This expression is the cumulative regret of the iterations, where no candidates are rejected and where at least one of the well-specified candidates has been introduced. We can bound this term using similar strategy as [3] First, we show that, with probability of at least 1 - 6, the well-specified candidate introduced at to will not be rejected. Second, since no other candidates are rejected at iterations & T. it means that the function values achieved at those iterations cannot be too different from the ones achieved when using 0. Using this fact, we arrive at a statement:
Σn F + TET T
Σ
S |S
(
10000
+
BEMMo
where Mo is the set of misspecified length scale values that were chosen at least once after to. The which can be done due to the selection rule in line 3
rest of the proof consists of bounding
Optimality In Appendix H we show that for a fixed choice of growth function, we get R (T)
(d (T)). This is an improvement compared to A-GP-UCB achieving RT RT/R" AR (T) As such the bound of our algorithm significantly closer to the optimal bound than the one of A-GP-UCB. The faster 9(-) is increasing, the quicker we will be able to find the first well-specified candidate, which will decrease the term B² in the bound. At the same time, will increase all the terms depending g(T), but as bound only scales with d log (T), are able to select much more aggressive growth functions than A-GP-UCB, whose bound scales with g (T)) In the Experiments section we compare the performance of LB-GP-UCB and A-GP-UCB using different growth functions gt) and show that the former algorithm is much more robust to the choice of g()).
(g)(T)d)
Extension unknown N As discussed before, LB-GP-UCB requires us know the initial RKHS norm N However, we can easily extend the algorithm to handle the case of unknown N*, which we do Appendix[F an algorithm, which in addition to having candidates for also maintains a number of candidates for
Algorithm we present Length scale and Bound Balancing (LNB)
N As such, it requires us to specify another growth function b(l) for exploring new norm values as well as the initial RKHS norm Bg. We prove its cumulative regret bound in Theorem F. We can similarly derive the suboptimality gap for our algorithm in this case. We display it in Table together with the gap of A G-G-UUBB We can that in this setting, we also achieve improvement.
7

---

Experiments
We now evaluate the performance of our algorithm multiple synthetic and real-world functions. To run experiments we used the compute resources listed in Appendix [.] and implemented based on the codebase of [2], which uses the BoTorc package 55] 34J. We open-source our code We used the UCB acquisition function and we compared different techniques for selecting the length scale value. For all experiments, we used isotropic v-Matémn kernel with 2.5. We standardise the observations before fitting the GP model and as such keep the kernel outputscale fixed to 1.0. The first baseline we compare against is MLE, where the length scale value is optimised using a multi-star start L-BFGS-B method [25] (the default BoTorch optimiser (5]) after each timestep by maximising the marginal likelihood for the data collected so far. The next baseline is MCMC, where we employ a fully Bayesian treatment of the unknown length scale value using the NUTS sampler [19, which we implemented using Pyro 77. We use BoTorch'ss 's default hyperprior (0 (33 6)) and to select a new point we optimise the expected acquisition function under the posterior samples as described by [3]. We also compare against A A-GP-UCB, To achieve a fair comparison, we used the same growth function g()) max(to. vt} for both LB-GP-UCB and A-GP-UCB across all experiments, where to was selected so that at least 5 candidates are generated for g(1). We study the impact of this choice in the ablation section. We used 10 initial points for each algorithm unless specified otherwise. To select upper bound Og for A-GP-UCB and LB-GP-UCB we fitted length scale to initial data points with MLE (and we did not use MLE after that). We present the results Figure 3 below. We show We now describe each benchmark problem in detail.
running times in Table 2 in Appendix L.2
Synthetic
Real-world
Berkenkamp
Michalewicz
AGNP
Crossedbarrel
0.12
Bost regret
0.08
0.1
0.04
2
Cumulative regret
800
1200
10
400
600
100 iteration
200
0
100
200
40
80
40
80
ileration
iteration
iteration
MLE
MCMC -.. A-GP-UCB
LB-GP-UCB (Ours)
Figure 3: Regret results of the proposed algorithm and baselines on synthetic and real-world tasks. We ran 20 seeds on Berkenkamp and AGNP and 10 seeds on Michalewicz and Crossedbarrel problems. Shaded areas correspond to standard errors.
Berkenkamp Toy Problem We start with a me--imensioonll toy problem proposed by the same paper that proposed the A-GP-UCB algorithm (6]. We showed plot of this one-dimensional function in Figure I On the right side of the domain, the function appears to be smoother than on the left side. In this problem, we only use three initial points, to benchmark the ability of algorithms to escape from the local optimum the right side of the domain. MLE and MCMC can be easily misled towards too-long length scale values, which causes them to get stuck in the local optimum. Both A-GP-UCB and LB-GP-UCK quickly find the optimal solution, however, due to over-exploration, the cumulative regret of A-GP-UCB grows faster than that of LB-GP-UCB.
Michalewicz Synthetic Function As next benchmark, we evaluate our algorithm on the five- dimensional Michalewiez synthetic function, which has been designed to be challenging while using MLE for fitting hyperparameters, because it exhibits different degrees of smoothness throughout its domain. In the histogram in Figure we compare the selected length scale value with an estimate of the optimal length scale 8-_ We produce this estimate by sampling ten thousand points uniformly through the domain and fitting a length scale value by maximum likelihood to the points with the

---

top 1% of objective values. In this way, we are able to capture the length scale value that produces a good model for the Michalewicz function around the optimum, where least smooth. We can see LB-GP-UCB selects lengthscale value closer to O" and as a result outperforms other baselines in terms of both cumulative and best regret metrics.
Material Design Problems We utilise material design tasks proposed by and 30 the dimensional CrossedBarrel and 5-dimensional AGNP tasks. At each time step, the algorithm can choose which material configuration try, and observe the objective value, which corresponds to a given material optimisation criterion. As material design problems are known to exhibit needle-in-at an-a-haystack behaviour [35], on both benchmarks MLE and MCMC get stuck at a suboptimal solution and their best regret does not fall beyond certain value. A-GP-UCB is able to quickly find low-regret solutions on the AGNP benchmark, but struggles on the Crossedbarrel problem and underperforms in terms of cumulative regret. On the contrary, LB-GP-UCB performs well across both benchmark problems and across both regret metrics.
Ablation on g(t) To test robustness of LLB-GP-UCH we evaluate it on Michalewicz function together with A- A--GP-U UCB for different choices of g(t). We try functions of form g max(to, t²) for E (0.25, 0.5, 0.75). In Figure 4 we plot the final performance of the algorithms after N = 250 steps as well as the distribution of selected length scale values. We see that A-GP-UCB very sensitive to the selection of growth function g(t), whereas our algorithm selects similar length scale values regardless (t). which results consistently good best regret results. We can also see that LB-GP-UCB typically selects values around 6 for different growth functions, whereas A-GP-UCB decreases its length scale beyond 0", resulting in slower convergence.
Length scale
Best regret
2
0.1
A-GP-UCB LB-GP-UCB
A-GP-UCB LB-GP-UCB
g()) = max(t, 12
g() max (4)
g(() g())mmx((,, (19)
Figure 4: Ablation study of the choice growth function g(t). to is chosen so that at least
candidates generated at 9(1). See beginning of for details.
Related Work
We already mentioned the work proposing A-GP-UCB 6), which far has been the only work providing the guarantees on BO with unknown hyperparameters, where only an upper bound on the optimal length scale value is known. The work of [39 addresses the problem, where, in addition, lower bound on the optimal length scale is known, however, the regret bound of the algorithm they propose scales with the vr(k%% of the smallest possible length scale 0,,, making it no better than naïve algorithm always selecting 0z. [8] studied the problem of solving BO, when the kernel function misspecified, however, provided no method for finding the well-speeified kernel function. [26) proved a lower bound on the algorithm's is regret in the case when the regularity of RKHS is unknown (which corresponds
an unknown hyperparameter in the case of Matérn kernel), compared to their work we focused on different unknown hyperparameters such as the length scale. There have also been number of works [3]
21 27 32] that tackled the problem of BO with unknown hyperparameters but did not provide a theoretical analysis of the used algorithm. Some of earlier viewed BO with unknown hyperparameters as meta-learning or transfer learning problem, where a large dataset is available for pre-training. In our problem setting, we do not assume access to any such pre-training data. Within this work, we considered frequentist problem setting, where the box function arbitrarily selected from some RKHS. While there are guarantees
works 15 38

---

for the consistency of MLE in such setting, if we were to assume a Bayesian setting and put GP
prior on the black box, statistical literature derived asymptotic consisteney results 22 24 28] for MLE of kernel hyperparameters, including length scale. Under such a Bayesian setting, 41 studied the problem of BO with unknown prior, when we are given a finite number of candidate priors. [TO] derived predictive guarantees for GP in a Bayesian setting with unknown hyperparameters, provided that hyperpriors on those hyperparameters are known. However, the authors do not provide any BO algorithm based on their results.
Conclusions
Within this work, we addressed the problem of BO with unknown hyperparameters. We proposed an algorithm with a cumulative regret bound logarithmically closer to optimal than the previous state of the art and showed that our algorithm can outperform existing baselines in practice. One limitation of our work is that we only showed how to handle the isotropic case, i.e. where the same length scale value is applied for every dimension. This limitation because our algorithm requires the knowledge of the regret bounds of optimiser utillsiig given length scale value, which in turn requires the knowledge of the bounds on MIG 7/2 (kk) for the used kernel. To the best of our knowledge, within work has yet derived those bounds in non-isotropic cases. However,
the existing literature, believe that if such bounds were obtained, one could easily extend our algorithm to the non-isotropic extended our base algorithm to handle unknown norm and length scale
case, in the same way simultaneously. This constitutes a promising direction of future work.
Another limitation of our work is the assumption of known noise magnitude ON- The problem of simultaneously not knowing kernel hyperparameters and noise magnitude extremely challenging. as large variations in observed function values can be result of either short lengthscale value or large noise magnitude. To the best our knowledge, previous work did not tackle this setting and remains an open problem.
Our algorithm relies on the standard GP model, which can result in poor scalability to large datasets and high-d dith-niiensional spaces. Extending our work to sparse GPs (29 31 and kernels specifically designed for a high number of dimensions 42 is another possible direction of future work.
Acknowledgments and Disclosure of Funding
We would like to thank Toni Karvonen for pointing out important properties of the y-Matérn kernel's RKHS, which were crucial to take into account in the proposed problem setting. We would also like to thank Ondrej Bajgar and the anonymous reviewers for their helpful comments about improving the paper. Juliusz Ziomek was supported by the Oxford DTP grant EP/W52431 1/1. Masaki Adachi was supported by the Clarendon Fund, the Oxford Kobe Scholarship, the Watanabe Foundation, and Toyota Motor Corporation.
Scholarship and EPSRC
References
[1] Yasin Abbasi- Yadkori, Aldo Pacchiano, and My Phan. Regret balancing for bandit and RL model selection. arXiv preprint arXiv:2006. 05491, 2020.
[2] Masaki Adachi, Satoshi Hayakawa, Martin Jørgensen, Saad Hamid, Harald Oberhauser, and Michael A Oshorne A quadrature approach for general-purpose batch bayesian optimization via probabilistic lifting. arXiv preprint arXiv:2404. /22/9, 2024.
[3] Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire, Corralling band of bandit algorithms. In Conference on Learning Theory, pages 12-38. PMLR, 2017.
[4] François Bachoc. Cross validation and maximum likelihood estimations of hyper-parameter of Gaussian processes with model misspecification. Computational Statistics & Data Analysis, 66:55-69, 2013.
[5] Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wil- son, and Eytan Bakshy. BoTorch: framework for efficient Monte-Carlo Bayesian optimization. Advances in neural information processing systems, 0421522421153 2020.
10

---

[6] Felix Berkenkamp, Angela P Schoellig, and Andreas Krause. No-regret Bayesian optimization with unknown hyperparameters. The Journal of Machine Learning Research, 20(1): 1891, 2019.
[7] Eli Bingham, Jonathan P Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, and Noah D Goodman. Pyro: Deep universal probabilistic programming. Journal of machine learning research, 20(28):1-6, 2019.
[8] Iliaa Bogunovic and Andreas Krause. Misspecified gaussian process bandit optimization. Advances in Neural Information Processing Systems, 34:3004-3015, 2021.
[9] Adam D Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Research, 12(10), 2011.
[10] Alexandre Capone, Armin Lederer, and Sandra Hirche. Gaussian process uniform ervor bounds with unknown hyperparameters for safety-critical applications. In International Conference on Machine Learning, pages 2609-2624. PMLR, 2022.
[11] Sayak Ray Chowdhury and Aditya Gopalan. On kemeliizdd multi-armed bandits. In International Conference Machine Learning, pages 844-853. PMLR, 2017.
[12] Alexander I Cowen-Rivers, Wenlong Lyu, Rasul Tutunov, Zhi Wang. Antoine Grosnit, Ryan Rhys Griffiths, Alexandre Max Maraval, Hao Jianye, Jun Wang. Jan Peters, et HEBO: Pushing the limits of sample-efficient hyper-parament Intelligence Research, 74: 1366991444 2022.
optimisation. Journal of Artificial
[13] George De Ath, Richard M Everson, and Jonathan E Fieldsend. How bayesian should bayesian optimisation be? In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 1860-1869, 2021.
[14] David Eriksson and Martin Jankowiak. High-dimensional bayesian optimization with sparse axis-aligned subspaces. In Uncertainty in Artificial Intelligence, pages 493-503. PMLR, 2021.
[15] Matthias Feurer, Jost Springenberg, and Frank Hutter. Initializing bayesian hyperparameter optimization via meta-learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[16] Roman Garnett. Bayesian optimization. Cambridge University Press, 2023.
[17]
Aldair E Gongora, Bowen Xu, Wyatt Perry, Chika Okoye, Patrick Riley, Kristofer G Reyes, Elise F Morgan, and Keith A Brown. A bayesian experimental autonomous researcher for mechanical design. Science advances, 6(15):eaaz170) 708. 2020.
[18] Antoine Grosnit, Cedric Malherbe, Rasul Tutunov, Xingchen Wan, Jun Wang, and Haitham Bou Ammar. BOiLS: Bayesian optimisation for logic synthesis. In 2022 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1193-1196. IEEE, 2022.
[19] Matthew D Hoffman, Andrew Gelman, et al. The no-u-turn sampler: adaptively setting path lengths in hamiltonian monte carlo. Journal of Machine Learning Research, 15(1):1593-1623 2014.
[20] Kihyuk Hong, Yuhang Li. and Ambuj Tewari. An optimization--ased algorithm for non- stationary kernel bandits without prior knowledge. In International Conference on Artificial Intelligence and Statisties, pages 3048-3085. PMLR, 2023.
[21] Carl Hvarfner, Erik Orm Hellsten, Frank Hutter, and Luigi Nardi. Self-correctig Bayesian opti- mization through Bayesian active learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[22] CG Kaufman and Benjamin Adam Shaby. The role of the range parameter for estimation and prediction in geostatistics. Biometrika, 100())473-444, 2013.
[23] Asif Khan, Alexander I Cowen-Rivers Antoine Grosnit, Philippe A Robert, Victor Greiff, Eva Smorodina, Puneet Rawat, Rahmad Akbar, Kamil Dreczkowski, Rasul Tutunov, al. Toward real-world automated antibody design with combinatorial Bayesian optimization. Cell Reports Methods, 3(1), 2023.
[24] Cheng Li. Bayesian fixed-domain asymptotics for covariance parameters in gaussian process model. The Annals of Statistics, 50(6):33343363, 2022.
[25] Dong Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimiza- tion. Mathematical programming, 45(1-3):503-528, 1989.

---

[26] Yusha Liu and Aarti Singh. Adaptation to misspecified kernel regularity in kernelised bandits. In International Conference on Artificial Intelligence and Statistics, pages 4963 4985. PMLR, 2023.
[27] Daniel James Lizotte. Practical bayesian optimization. PhD thesis, University of Alberta, Canada, CAN, 2008. AAINR46365.
[28] Kanti V Mardia and Roger J Marshall. Maximum likelihood estimation of models for residual covariance in spatial regression. Biometrika, 71(1):135-146, 1984.
[29] Mitchell McIntire, Daniel Ratner, and Stefano Ermon. Sparse gaussian processes for bayesian optimization. In UAI, volume 3, page 4, 2016.
[30] Flore Mekki-Berrada, Zekun Ren, Tan Huang, Wai Kuan Wong, Fang Zheng, Jiaxun Xie, Isaac Parker Siyu Tian, Senthilnath Jayavelu, Zackaria Mahfoud, Daniil Bash, al. Two-step machine learning enables optimized nanoparticle synthesis. npj Computational Materials, 7(1):1-10, 2021.
[31] Henry B Moss, Sebastian W Ober, and Victor Picheny. Inducing point allocation for sparse gaussian processes in high-throughput bayesian optimisation. In International Conference on Artificial Intelligence and Statistics, pages 5213-5230. PMLR, 2023.
[32] Michael A Osborne, Roman Garnett, and Stephen J Roberts. Gaussian processes for global optimization, 3rd International Conference on Learning and Intelligent Optimization (LION3), pages 1-13, 2009.
[33] Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett. Regret bound balancing and elimination for model selection in bandits and RL. arXiv preprint arXiv:2012.1 /3045, 2020.
[34] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, and Luca Antiga PyTorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[35] Alexander Siemenn, Zekun Ren, Qianxiao Li, and Tonio Buonassisi. Fast bayesian optimiza- tion of sarell-in---haystte problems using zooming memory- based initialization (zombi). npj Computational Materials, 91):799, 2023.
[36] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process op- timization in the bandit setting: No regret and experimental design. In International Conference on International Conference on Machine Learning, pages 1015-1022, 2010.
[37] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82-90. PMLR. 2021.
[38] Zi Wang, Beomjoon Kim, and Leslie P Kaelbling. Regret bounds for meta bayesian optimization with an unknown gaussian process prior. Advances in Neural Information Processing Systems,
31, 2018.
[39] Ziyu Wang and Nando de Freitas. Theoretical analysis of Bayesian optimisation with unknown Gaussian process syper-parameters. arXiv preprint arXiv:1406.774 2014.
[40] Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning.
volume 2. MIT press Cambridge, MA, 2006.
[41] Juliusz Ziomek, Masaki Adachi, and Michael A. Osborne. Time-varying gaussian process bandits with unknown prior, 2024.
[42] Juliusz Krzysztof Ziomek and Haitham Bou-Ammar. Are random decompositions all we need in high dimensional Bayesian optimisation? In International Conference on Machine Learning. pages 43347-43368. PMLR, 2023.
12

---

A Proof of Proposition 2.2
Proposition 2.2. have that (r:( - O (0(r((())
For an RBF kernel "rr (k() = güt log(T) d+1
1
dia+1) For v-Matérn kernel P/r (k.) T auta(a+)) log w0rd
Proof. The RBF case follows directly from Proposition 2 in [6]. The same Proposition also provides a bound for the y-Matérn case, but more recent results allow us to derive a tighter bound. Section B.2. in [6] proves that the y-Matérn kernel has the (Cp.8p) polynomial eigendecay: 3p (2v +d/+d)/a d) and
Cp (3) 2 according to the definition of polynomial eigendecay given by [37. Substituting
these values to Corollary 1 of (37] we get that p-Matérn case
z O (o) (CU/STT1//r log--1/Br (17)///1/1//// = =o (()
T (2v4))) log (r/
which finishes the proof.
B General Hyperparameter case
Lemma B.1
Theorem 2.1
Lemma B.2
Lemma B.3
Lemma B.4 B.4
Lemma B.5
Figure 5: Diagram of the relationship between Lemmas in this Section. An incoming arrow means that the Lemma relies the Lemma/ Theorem from which the arrow is outgoing. The final objective of this Section is to prove Lemma B.5
We first derive a general result for BO Algorithm utilising regret-balancing scheme, under hyperparameters of any form. We present the pseudo-code of that procedure in Algorithm 2 We now proceed the prove the general regret bound for this algorithm. We would like note that our proof closely follows the idea of [33]. We assume the unknown hyperparameter takes values in some set / and specifying this hyperparameter uniquely defines kernel function k= and the RKHS norm B" We say a hyperparameter value is well-specified if [ < Ba, Algorithm requires syperparameter-proooiiin function a(-) as one of the inputs, which optionally expands the set of considered hyperparameters, We will denote by A Ur a(t) the set of all hyperparameters
13

---

introduced by a(-) up to step T. We will also denote W to mean the set of all well-specified hyperparameters A and M A W denote the set of misspecified hyperparameters. Let ut be the first well-specified hyperparameter introduced. We will also write 'I to mean the set of all iterations after (and including) ig, where least one hyperparameter value was rejected, that is:
max Lo(u') } 1 E'EU
2 S
T = to..... ................................ T uEE, Le(u) +
Σ
8"0""
TEST
We also define Mo {u E M13326 u) to be the set of all misspecified hyperparameters that were selected at least once after to-
Algorithm 2 Hyperparameter Balancing GP-UCB
Require: suspected regret bounds R-(:):
syperparrameter-rrooosss
function a()); confidence parameters {Er)/= and (3
1: Set Dn = 0, U1 = a(0) SS for all u U1,
2: for /. = 1, ..... do
3: Select hyperparameter u, = arg min Rdd (1S 1)
4: Select point query æt = arg max UCB 1-11-110 (x)
#EX
5: Query the black-box
[x:))
6: Update data buffer D, = D.-1 (2,,
7:
For each u E U, set Sy = {T = 1, 1,..., uy = u} Initialise hyperparameter set for new iteration Ul+1 = Up
8:
9:
if VuEu, |S then
10:
Define [u( | Eresp
13
&
11: Ul+1 a U. L.(u) +
2 |s Eresp 870
max Lo(
12: end if
Optionally expand hyperparameter U441 U241 U (a(()))
14:
end for
We will first provide some auxiliary Lemmas that we will be required to prove the general result for Algorithm 2
We first recall result from existing literature on the concentration of noise.
Lemma B.1 (Lemma 5.1 in 41). For each u A and 1,..., T we have:
P
V
Σ iES
E
S SElS
2 1 - 11
|A|=2,2 6g
where & 2 log
The next result will need is the nigh-probability guarantee that the optimal hyperparameter u' will not be removed from the set of considered hyperparameters after it is introduced.
Lemma B.2. If the events of Theorem 2.1 and Lemma B. hhold then the optimal hyperparameter u" is never removed after it is introduced, i.e. u" E U, for all t to...., T, where to is the first iteration, where the optimal hyperparameter s" is introduced.
Proof. First, observe that under these events, the optimal hyperparameter u" will never be removed. To see this, observe that at any time set t such that us = u² the following holds:
f(x²) f(xx) S ui (a=" + By of (xx") 11, (xx) + 85 of (xx)
n (xx) + Br of (xx) 1t (xx) + By oy (x+)
23 or (æ:),
where the first inequality follows from the fact that the event of Theorem 2.1 holds and is well- specified, and the second incquality is because chose æ, to maximise the UCB. Using this
14

---

fact, we get that:
Σ
(f(x")
(ye ())
Σ
(f(x²) - f(x1)) v
2
Σ
3t of
(xx))
S
1
*EST
rESt"
rE
Rearranging, we get:
f(x²)
Σ
B of (zt)
c +
SEST
1EST
tEST"
S
Σ
Br t u.
(It) + V
&t
+
Σ
Vt
(I)
SS
|
SS
TEST"
tEST
where the second inequality is result of Lemma the following:
B.1 Now, for any E A and any t E S7, we have
f(x²) =
f(x")
f(x1)
Dt
LEST
EEST
&
SW
S
tEST
rEST
SE
where again second inequality comes from Lemma that for any u E A:
B.1
Thus combining Inequalities
and
we get
2 SST
ΣS
3t of'
(xI)
|S
&
+
V8
y/+ ST
V
& |
YEST"
tEST"
EEST
which means the if statement line 11 will always evaluate to true for u² and thus u² E U, for all t= 1,....,,
We now recall the balancing condition, which is satisfied by regret balancing algorithms as proven in Lemma 5.2 of [33]. This condition basically says that due the selection rule that chooses algorithm with current lower suspected regret, the regret of any two algorithms (that have not been rejected) must be "close" to each other. We prove slightly different statement than that in 33 in our case the set of base algorithms can be dynamically expanded.
Lemma B.3. Assume the event of Lemma holds. For any u E A that was selected in line 3 at least once after io and any time step to...., ., we must have that (IS))) I R= (1ST () + 2B"
Proof. We will prove the statement by contradiction. If the statement of the Lemma not true, would have:
R" (I((s)) R² (IS;" 1) +22"" 2 R² (IST" I+
where the second inequality comes from the assumption that the bounds are non-trivial. If has been selected at least once after uf was introduced (and by Lemma Bm2 u² could not have been excluded selected, u* must have been present in U, and as such selection
afterwards), then the last time of u such that R (IS! Rd (1St + would violate the selection rule in line 3.
Before we can prove the final result of this Section, we need one more auxiliary Lemma. This Lemma bounds the regret on all the iterations, where none of the hyperparameters was rejected (i.e. $ T), by using the rejection rule of line 11.
Lemma B.4. Assume the event of Lemma B.3 holds. Let us call by T the set of all iterations after to- where do not reject any of the candidates. We must have that for any A:
Σ S
S# S4
+1)
CR ((S) +)+ 2CB" +2
(
( S
+1)
VISH
15
MTT
TESH
15

---

Proof. Let t' be the smallest iteration after to. such that Sy ST and t' t' T. t' is the last iteration not in T when was played. Notice that since E' $ T, all hyperparameter values in Uy. must satisfy the if statement in line 11 when compared with any other hyperparameter value in Ug- Let us choose any hyperparameter value Up and compare with u* (which must be in Uv due to the event of Lemma B.3 that guarantees preservation of u .). For the if statement to evaluate to true, we must have:
2
&t
E SS
+
o (2t) +
y/c
SP
SSP
TET CES?
tEST
LEST
Multiplying both sides by -1 and adding f(x)), we get:
(f(x*) 91) Eey (x))
E1
Σ (f(x") - -ye) +
IS
S
SSp
T
EESY
FES?
Using the fact that yt = f(x)) + Et and Lemma
B.1 we get that:
2 EiESy (xx)
Et
-2
2
SW
|5
ETT rES?
Σ (f(x")-f(x;)) + 2
Ee
1p
15
tESH"
Rearranging and observing that r2 -(xx))
[(xx), we obtain:
Σ rh
$2 Σ
8 + 2/ /Syle +
S
r2 + 2| Σ LEST
E
SS
1S
IT
IESy
LESH
St 15
&
SCR + 2 S
CR
(1SH 1) +
2|%
V
S5
where we use the fact that E (x)) S (Sk) for some constant C > O. which follows
from the proof of Theorem 2 of [II on which we rely to obtain the suspected regret bounds. We also used the fact that due to u" being well-specified we have that Exesy' T1 S CR (1S7" I). We now apply Lemma B.3 to get that ((S(() < R" (IST') [] + 2B"". Substituting that to the bound developed above and noting that by definition sV Sy. we get:
Σ
Σ rr
SS S
CR" (1SH 1) + 2CB" +2 (V +1
Sy 1
+
/SS
t IEST
MT LES?
SH
1ST
+
CR (IS) 1) + 2CB" +2
+1
15
which finishes the proof.
We are now ready prove the final result of this Section.
Lemma B.5. Let us run Algorithm for T iterations with a given choice of the hyperparameter- proposing function hyperparameter is rejected by operation in line 11. If we set & = 20 log 66g
N + U. Let T be the set of all iterations after to. where at least one
n²t and Sy
Bd + ON / 2(1 +1 1 In(1/5A)), we then have that with probability least ōA 5p:
Σ rx 0 (1418"" (R"((T) TET 1T
SH
141 1)
Σ ME
SS
16

---

Proof. We will prove the bound assuming the events of Theorem 2.1 and Lemma B. hold. As this happens with probability at least have that:
ō^ SB, the bound also holds with the same probability. We
Ens GC
Σ
Σ
Σ "t
Tt
NEW H8T 1ES7
MEMo HI'T IEST
Σ NEW
CR (RSH)))) + Σ
MEMo EET 1EST
Σ CR" (189)) + +CBB")
+
+E TE
uEMo IET LEST
$ S| (CR" (T)+ +CCB
+ 3Σ Tt
(3)
ME FET IEST
where the first transition is due to all hyperparameters in W being well-specified and the second transition due to Lemma We now tackle the second term:
Σ KEMo
Σ 14T
S
Σ MEMo
| [S
+1
CR" (IST 1) + 2CB" +2
(1
+
s
14
1EST
|
|ST
Σ MuEMa
|MMol CR" CRS" 1) Mc B +2
|Mall
VTE,
SS
V
|SY
MuEMo
S4
+ [Mol] Rd ((ST" D) MM +
Σ
S
+ lMool
VTE,)
SS
where we used Lemma B.4 Cauchy-Schwar inequality and the fact that |SS| T for all A.
Observe, that suspected regret bounds in BO will be of form 18th (T) v 4 / 77 + \BO). Substituting this fact, we get:
Rd (IS 1)
Σ ME
ST 1S
Σ
SS
ST
BT
7
(V*** + (VTT.)
Sy
Σ
ST
St
ST
77
(V7# +VBB)))
SS
ueMo
Σ ME
Stu SS
R" (1S7))
0
Σ
R" (T)
SS
LEEM
We thus get
Σ Σr -O(M)BB' + RR" (T((T)) VTr
SS ssy
+ (mal))
Σ MeMo
ME GTT LESS
Substituting this back into Equation B yiells the following bound:
Σn so 0 |AAI" + RR" (T) + VTEr)
Σ WEMo
S SS
141
1TT
17

---

C Proof of Lemma 3.1
Lemma 3.1. the case of both RBF and v-Matérn kernel, we have that:
(T)
R00 (T) (1).
Proof.
TTT
V/9 B(O,N*)
R²(T)
q(1") d
= =2(e-1/a)= =(1),
=2
2
R0t (T)
TTh
(vi + BBO
a11 + +1)
where i" = maxfi E ((i) 2 } and as such we have q(i" + +) = 0 < 0r S q(i)).
D Proof of Theorem
Theorem 4.1. Let us use confidence parameters of & = 20 log (dIn(g()))*2(})) log 36 and
8 = B(0, N*) + ON 222 +1 In(2/6)), then with probability at least 1 5, the cumulative regret Rr of the Algorithm addmts the following bound:
((0))
0000
Oo gr :.1)
R7 Ry = (to (1to+))
R (T)
TET
dln
where to = g (e and dlngg())
Proof. We start with similar regret decomposition as in the proof of Theorem 1 in 66] Let to be the first iteration, where length scale value smaller or equal to 0* enters the hyperparameter set O,,- We will refer to that value as ô. Before this happens, all hyperparameters in the set are misspecified and such cannot guarantee anything about the regret of those iterations. As such, bound their regret by 2B*, which is the highest possible regret one can suffer at one iteration. We thus get:
Ra
Σ 1.....g
r
Σ
ri S + Rr
t= +I..,
We note that due how we add new length scales, we have that to S g ( and we defined Ry be the cumulative regret of all iterations after lg- Let us define the set 'I to be the set of all iterations, where least one hyperparameter was eliminated. We thus get the following regret bound:
Oo ((T)
RT Σn Ert Σ IET
2 tT
En ET
24
B
Σ Tr TT
where the last inequality comes from the fact that we cannot reject more hyperparameters than we have considered in total. We now rely Lemma B.5 which provides bound Eegr Tr with probability at least - E åg and we set 8 ÔB 8/2. In the notation of the Lemma. write A
U θ to mean the set of all length scale values introduced over the course of the T....TT
algorithm running and by Mo we mean all length scales longer than 9 that were selected at least once & and our optimal base learner is Ô. This gives us:
after to. We observe that |A| 5-1
9(?))
Σ T==0 ( T
Oo (0000 ((T)
B* + (TT TET
Σ
S
Go ((T)
+
S
MuEMo
To finish the proof we rely on the following Lemma, which prove in Appendix E
18

---

Lemma D.1. If the event of Lemma B.5 holds, then for any 0 E Mo and t 2 to we have that
0n
We thus get the following final bound:
Σn=o(r'
r-'
(6/
0o Ba (e(T))VTS) ( [Mo
(0r)
(00)²
Oo
0r
+ +9
T()))
T
We now observe that [Mal o (00)) o (dIn g.). We substitute the bound above to Equation 4 together with bound on |Mol to obtain:
RT 10
do Orelid
+1 1² + (R²(T) + TET)
((0))
00
d d In +1))
where d'nn (()). By Lemma above, which finishes the proof.
3.1 we know can just replace R (T) with R (T) in the bound
E Proof of Lemma D.1
Lemma D.1. If the event of Lemma B.5 holds, then for any 0 MM and 2 to we have that
18
Proof. If |S 2 |. the bound holds trivially. Thus we will assume |S < [S The suspected regret bounds are of the form:
R -
If the event on Lemma B.5 holds that means the event of Lemma B.3 holds well. Due to the regret balancing condition from Lemma B33 and the non-triviality of bounds, we have:
Rd (1S))) s Rd (159")
+2"" $2R" (1S))
Viser' (V.Reg B(0,,,N)
|S| |s(11
Visee (Vhise + BBO,
To finish the proof we consider the following two cases.
Case 1: Consider the case when Vissen
2 N*). We then have:
S
1s40
0
1881
d
<
2
2
2
2
S
Sspl
0+
1S81
0=
0
Case Consider the case when
0
< B( N*). We then have:
S
0 1s?
B(0,,
d/2
Psp
8
4/2
B(0,
<
5 2
|
/
B(0,
7sse
9
0"
BOO
0
d
0g
< 2
< 2
0
0
19

---

F
Unknown RKHS norm
Within this section, we show how our algorithm be extended to handle the case of known RKHS norm. Let us define the following candidate-suggestin function for the RKHS norm hyperparameter.
Definition F.1. Lets consider the following candidate-suggeestnng function ef-) N + IR to be mapping for each E IN of form:
0 (2) Noee.
For RKHS being selected by the candidate-suggestin function of Definition F.1 and length scale being selected by the one of Definition 3.1 we get:
Lemma F.1. In the case of both RBF and v-Matérn kernel, we have that:
R(B.B( R(0
B(O (NT)) (1).
Proof. Case 1: / > B)
T (V B(O
((O.B( B( B (T)
22 0"
gi +1) ) = 2e(c-11) -011)
g(it)
<
VT* (V + B(O,
where 1' max (()= 2 0²} and such we have q(i" + 1) 0 < 0r S q(())r.
Case 2: //4 s B(
VT (VA =(ON))
R(O (1.B(600))T (T)
2 N)
22 {2(_(()) g((t)
u(j" +1)
RlO (1)
TT (V B(0r,N+))
7 B(0,,
g(0 +1]
v(j*)
< 2 (e (e-1/)) e= 0(1)
where i* max (i N q(i) 2 0*) and j max(j N v()) N*3 as such have
q(i" + +1 = i < 0" s q(i*) and v(j" +1) = Ñ z N 2 v(j")
We can now prove the regret bound. Theorem F.1. Let us use confidence parameters of 20 log(d g (T) log (T)) - log(35)
and B..N (0,,N) + ON / 1 + 1+ ln(2/))) then Algorithm achieves with probability at least 1 - 8 the cumulative regret Rt of the algorithm admits the following bound:
Pr 0 (lo (1o+ B*+
B(O",BO',''(TT TEx) ((0)
d N
N Go In
No + +1))
d
No
6+
where to = max(g-1 (c-1/4g0/8"). (N* /No) and i = d (T) log b(T).
Proof. Similarly as in the proof of Theorem we look for to, such that at least well- specified hyperparameter value will enter the considered set. This happens after at most to = max ( (( b-t()()b( R e)}. Observe that the set all hyperparameters introduced by time step i Or x B,. We thus have:
Ry 2t + |A|B + Σ rt-
18
20

---

Algorithm 3 Length scale and Norm Balancing GP-UCB (LNB-GP-UCB)
Require:
suspected regret bounds (:)(:))
length scale growth function g()); norm growth function b(.); length scale candicate-proposing function g(-);
norm candidate- candidate-proposing function v(-);
initial length scale 0o; initial norm Bp:
confidence parameters {{=]=1 and {3,)
1: Set Du 0. U1 = {(b,, Bu)] S5 1 for all a U1
2: Set ; = { B1 = {Bo)
3: for 1,
do
4: Select hyperparameter uN = arg minuet, ([ +
5: Select point query a, arg max -- (3r)
6: Query the black-box Y1 fx:)
7: Update data buffer D2 = Dt-1 U (2,,
8:
For each E U. set Sy {T 1,...,t. u,, un
9:
Initialise hyperparameter sets for new iteration U2+1 = U., 0c41 = Or Br+1 = B.
10:
if Vueti |S then
11:
Define (u) [sP Eesh Vr
&
UC+1 { E U2 Le(u) + SSP
Dresp 1400-1(00,
max, Lo(u')
13:
end if
if q10p) +) < 9(1) then
15:
0.11 1 Ug( 1)
U++1 = U441 (1(1:)) 1) B41)
17:
end if
if v( + 1) < Bbb(t) then
19:
B = B.+1 Ue(BB +1)
20:
U++1 = U441 U (v( + 1) Oz+1)
21:
end if
22:
end for
We now apply Lemma B.5 to get:
Σ Enso
[A|B+ + RR" (T) + (Trr
T
|
Stn
M
where now |A| | ||T =q-
8y a(7) ( (Nob(T)) = dlog(g(T)) log(b(T)). We now derive
Lemma similar to Lemma D.I
Lemma F2. If the event of Lemma B.5 holds, then for any 0 E Ma and I 2 to we have that
S
0g d
N
S
g+
No
Plugging expression for [4], using Lemmas finishes the proof.
F.1 and F2
and the fact that [Mol = Old 0* 0 N*)
G Proof of Lemma E2
Lemma F2, If the event of Lemma B.5 holds, then for any 0 My and t 2 to we have that
S
80 d
N
SH"
0+
No
21

---

Proof. If ST 2 | the bound holds trivially. Thus we will assume |S < [SP]. The suspected regret bounds are of the form:
Rd (t) - VT (V
Due to the regret balancing condition (Lemmaa 5.2 of (33)
must have:
("((s) S 2R (1ST")
0 1ss''
( or
+ +B(0,,
11s"'
S |Ss"
2
V
WASS B(0,N)
Misri
Case 1: Consider the case when
2 3(0*,N")
We then have:
18:
(0) 0^
d
|571
00
d
N+
S
S
2
S
1
Ssr1
0
A-
No
Case Consider the case when
( BB*) We then have:
184'1
SH
1sT
B(0,NN*
d/2
Msy B(O", =
0r
(
d
N
2
2
Vsss B)O,N)
0+
Mssi
B(0, N)
0-
N
00
N
2
0+
No
H Derivation of optimality rates
To obtain rates for A-GP-UCB, we use Corrolary 3 of [6) While A-GP-UCB considered the case of unknown norm and bound simultaneously, to obtain the rate for unknown length scale only, we ignore the growth function used for the norm. Note that since, for A-GP-UCB Rt = (b((T) (TT) R² (T)) and in BO R" (T') = / ( B" //Tf.. if ( grows at least as fast as /TB, then bound on Ri grows least fast B" T and becomes trivial. Thus for the regret bound of A-GP-UCB be meaningful, we have assume ((T)) grows slower than VTB.
Inspecting the bounds of --B-GP-UCB and LNB-GP UCB-GG--CCB in Theorems 4.1 and F.I we see that the term with Rº (T)) or R!0 _B(0" (N')) will dominate the bound. This is because by the previous d. we get that OIn b(T)) di In g(T)) < (In(BT)) and VTG. O( log In b(T)dIn (T) = OooToo log TB) and in both RBF and v-Matérn cases regret bound grows least as fast as / VTlog Also the term (9:) N d 0g In No is a constant and will eventually get dominated by We thus get that the bound will become dominated by RR (T) or RR B(O",N ,N") (T) and the suboptimality just t.
assumption on the growth of (T))
No
22

---

I Experiments Details
We used the code of 20 for computations of maximum information gain.
I.1 Compute Resources
To run all experiments we used machine with AMD Ryzen Threadripper 3990X 64-Core Processor and 252 GB of RAM. No GPU was needed to the experiments. We were running multiple in parallel. To complete one run of each method we allocated four CPU cores. Individual runs lasted up seven minutes for each of the methods, except for MCMC runs, which could last up an hour (see Table()
1.2 Running times
Table 2:
Comparison of running types of different methods each test function/ benchmark. Values after are standard errors over seeds.
Function/ Benchmark
Method
Running Time (seconds)
MLE
438 + 0.66
A-GP-UCB
443 + 1.51
Berkenkamp Function
LB-GP-UCB
442 + 1.68
MCMC
1653 + 25.99
MLE
237 + 2.41
A-GP-UCB
167 = 0.88
Michalewicz Function
LB-GP-UCB
181 + 0.47
MCMC
3388 + 369.38
MLE
0.10
A-GP-UCB
48 + 0.40
Crossed Barrel Materials Experiment
LB-GP-UCB
48 + 0.50
MCMC
471 + 25.20
MLE
53 + 0.05
A-GP-UCB
49 + 0.18
AGNP Materials Experiment
LB-GP-UCB
49 0.16
MCMC
246 = 3.56
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction contain claims regarding the regret bound of the algorithm and empirical performance, which are addressed in Sections and respectively.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limiations are discussed in the Conclusions section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
Assumption are discussed in the Problem Statement Section, all proofs are either in main body or Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We describe what benchmark functions we use as well as provide details on the baselines and settings of algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
25

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide full code by an anonymised link in the Experiments section.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cipps.c/ppulli//guu /ot.e//Suudeeooeemuuummcciiiii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide the details on the choice of growth function g(t).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All plots have shaded areas corresponding to standard errors.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
26

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We list compute resources in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http::///harrpps..cccpppa//////t
Answer: [Yes]
Justification: The paper is concerned with foundational research and not tied to any particular application that can cause ethical concerns.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The research presented in the work is foundational and not tied to any particular application.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
27

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper is not accompanied by a release of any new data sets or pre- pre-trained models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We clearly cite the research papers that proposed the materials dataset
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
28

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We released our code and provided README.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Papers contains no experiments including crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "CvbYO7Qho7", "reviewer": "Reviewer_5KYZ", "summary": "This paper proposes an approach to deal with unknown hyper-parameters in Gaussian process upper confidence bound (GP-UCB) algorithms, a popular Bayesian optimisation (BO) strategy. The objective function is assumed to be a member of a reproducing kernel Hilbert space (RKHS) associated with a translation-invariant kernel class whose length-scale is unknown. Algorithms are proposed to adaptively estimate the unknown kernel length-scales and an upper bound on the RKHS norm of the objective function, which are common hyper-parameters for GP-UCB algorithms. Theoretical guarantees on the regret for the proposed algorithms are provided, which show that rate of the algorithm's cumulative regret to the regret of an algorithm with knowledge about the exact hyper-parameters are only logarithmic in contrast to previous approaches. Experimental results are presented comparing the regret of the proposed algorithms to typical hyper-parameter estimation strategies in the BO literature.", "questions": "* Another important hyper-parameter that might affect GP-UCB algorithms' performance is the sub-Gaussian noise parameter upper bound. However, the paper presents no discussion about the noise parameter. I was wondering if the authors have considered estimation strategies for that hyper-parameter as well.", "limitations": "Discussions on the main limitations of the theoretical analysis are presented, but there are no discussions on scalability issues, such as problems involving high-dimensional data or large datasets, which often require low-rank GP approximations. There are also no discussions on noise hyper-parameters (i.e., the sub-Gaussian noise parameter), another important hyper-parameter that might be unknown for some applications.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper builds well on existing theoretical results and a novel rigorous analysis.\n* Experimental results show improvements against existing popular hyper-parameter estimation strategies, bringing new insights.\n* Existing relevant literature seems well covered by related work section.\n* The text is well organised following a mostly clear structure.", "weaknesses": "* It is unclear how close the estimated length-scale and RKHS norm are to their true values at each iteration.\n* There are no (theoretical) convergence results on the algorithm’s estimates, only the regret bounds.\n* The proposed algorithms are only compared against other GP-UCB strategies. It’d be interesting to see how they compare to other methods which do not require explicitly knowledge of the RKHS norm bound, for example, such as expected improvement algorithms. There are also no comparisons against meta-learning BO strategies. Even though they require prior data, it’d be interesting to see how close (or better) the performance of the proposed algorithms can get to them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for reading our submission and for their appreciation for our theoretical analysis and empirical evaluation. We address each question/concern below.\n\n**Convergence of length-scales estimates**\nIn general, we consider the setting in which the function can arbitrarly change its smoothness throughout the domain. As such, it is impossible to guarantee correctness of the length scale estimation unless we cover the input space with an infinitely-dense grid---however, doing so would defeat the purpose of conducting sample-efficienct optimisation. Our algorithm side-steps the need for accurate length scale estimation by appriopriately balancing the regret. As such, we do not consider it a weakness that we do not solve the impossible task of precisely estimating length scales---instead, we propose an alternative approach that solves a practically-relevant problem.\n\nAlso, as shown in Figures 2 and 4, in practice, the length scale values typically selected by our algorithm are close to the estimates of optimal length scale value. As such, while we cannot guarantee the convergance of that estimator (which, as explained before, would be impossible in the considered setting), we observe reasonable convergence empirically.\n\n**Comparison to Exptected Improvement**\nWhile it is true that EI does not require knowledge of the RKHS norm to compute the acqusition function, in practice, EI still requires the specification of output scale value $c$ for the kernel $c k(x,x^\\prime)$. We have that $||f||_{ck} = \\frac{||f||_{k}}{c}$, so if we do not know the RKHS norm, we still have one more parameter to find. Additionally, EI still requires knowledge of the length scale. Our algorithm can be used to remedy these problems also in the case of EI, where each of the base learners could be an instance of GP-EI instead of GP-UCB.\n\n**Comparison to Meta-Learning strategies**\nThe only previous work of which we are aware that solves the problem of unknown hyperparameters via meta-learning is the work of , which we cite in the related work section. They assume the training and target function were sampled from the same Gaussian Process prior, which is a different setting from ours, were we do not impose any prior on the black-box function.\n\nWe did not compare against meta-learning baselines, as such approaches are only applicable where one can easily find functions that are highly \"similar\" to the target functions. For the benchmarks we considered, it is not clear how to find such similar functions.\n\n\n**Case of unknown noise**\nThe problem of simultaneously estimating noise magnitude and length scale value is ill-posed as, for example, pointed by [Karvonen and Oates, 2023]. An intuitive way to see that this problem is ill-posed is by observing that if the function values we observe change rapidly, we can never know for sure if the change is caused by the true function $f(\\cdot)$ changing rapidly (implying a short length scale value) or by the magnitude of noise being large and function changing slowly (implying long length scale value). As such, simultanous estimation of noise magnitude and kernel hyperparameters is likely impossible. However, we agree that we should comment on this, when discussing limitations. **We will update the paper to reflect that.**\n\n**Scalability Limitations**\nScalability to high-dimensional spaces and large datasets is a limitation of virtually all optimisation methods based on standard Gaussian Process models. These limitations are not particularly tied to the method we propose. **However, for clarity, we will update the script to clearly mention those issues** as a limitation of the standard Gaussian Process model and, by extension, a limitation of our algorithm, which relies on that model.\n\n\n**References**\nKarvonen, Toni, and Chris J. Oates. \"Maximum likelihood estimation in Gaussian process regression is ill-posed.\" Journal of Machine Learning Research 24.120 (2023): 1-47.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OV1z8e1U3B", "reviewer": "Reviewer_NyJf", "summary": "This paper introduces LB-GP-UCB (Lengthscale Balancing GP-UCB), a Bayesian Optimization (BO) algorithm that proposes a new tuning of the covariance function hyperparameters. A regret bound is derived, with logarithmic improvement over A-GP-UCB, the most similar solution in the literature. Some numerical experiments also show improvements in practice.", "questions": "Here are some questions to spark the discussion with the authors.\n\n(1) Have you compared LB-GP-UCB to any of the algorithms presented in [13, 20, 25, 28]? If not, on what ground have you discarded them for your empirical evaluation?\n\n(2) Why have you chosen these 4 benchmarks? I know that the rebuttal period is very short, but I believe more experimental results on a variety of problems (e.g., different smoothness of the objective function, different dimensionality...) should be considered to strengthen Section 5.\n\n(3) What were the dimensionality for the considered benchmarks? Do you have any insight on how LB-GP-UCB would react to higher-dimensional problems?\n\n(4) Do you have the precise wall-clock times for each solution and each experiment?", "limitations": "I believe the authors have properly addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "LB-GP-UCB is a significant improvement over A-GP-UCB, and constitutes an interesting step forward in the field of no-regret BO with unknown hyperparameters.", "weaknesses": "My concerns are mostly related to the experimental part of the paper.\n\n**Missing Baselines**. In Section 6, the authors seem to discard many solutions addressing the problem of BO with unknown hyperparameters because they do not provide any theoretical analysis for their algorithms (see [13, 20, 25, 28] in the main paper). Although I understand that LB-GP-UCB comes with an additional, reassuring theoretical guarantee, its empirical performance should still be compared against some empirical algorithms at least.\n\n**Missing Benchmarks**. Only four benchmarks were considered, I think that is not enough for a comprehensive study of LB-GP-UCB's empirical behavior. I believe additional experiments should be run.\n\n**Impact of the Dimension $d$**. The dimensionality of the objective function may have an important impact on the performance of LB-GP-UCB. However, the dimensionality of the problems was not specified in the main text nor in the Appendix E entitled \"Experimental Details\". \n\n**Wall-Clock Time Comparison**. In Appendix E, it is mentionned that all experiments for every method (except MCMC) took up to 4 minutes to run, but I would be interested in the precise wall-clock time for each solution and each experiment. This is important as online estimation of the hyperparameters brings a computational overhead to the BO algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for reading our submission and providing feedback on our paper. We address each question/concern below:\n\n(1) The methods used by [13] and [28] are equivalent to the MCMC baseline we compared against, where the hyperparameters are marginalised from the acqusition function using Monte Carlo samples (as we mention at the beginning of Section 5). [25] is an empirical study of robustness to misspecification of the prior on hyperparameters that does not provide any novel method of hyperparameter estimation. The codebase of [20] has been taken down from the web, and currently no publicly available implementation of their algorithm exists.\n\n(2) We chose benchmarks with differing smoothness throughout the domain (Berkenkamp, Michalewicz) or those that exhibit \"needle in a haystack\" behaviour (such as Material Design problems), as typically used methods such as maximum likelihood tend to struggle on these kinds of problems. Our benchmarks were chosen to showcase how our method can be used to tackle problems with which existing methods struggle. Of course, if one were to chose lesschallenging benchmarks with constant smoothness throughout the domain, it is entirely possible the improvement delivered by LB-GP-UCB over MLE and other baseline would be smaller. We do not claim that our method would provide universal improvement across all sorts of benchmarks, but rather that MLE and MCMC can perform poorly on a certain class of problems on which our algorithm performs well. We will add this comment to the limitation section.\n\nWe would also like to emphasise that the paper proposing A-GP-UCB (published in JMLR, 2019) included only two empirical benchmarks, so we would argue that our experimental evaluation of four benchmarks meets the standard for papers, whose main contribution is theoretical. In fact, Reviewer YCMG mentions \"Enough numerical evaluations are given (...)\". \n\n\n(3) The Berkenkamp function is a 1-dimensional synthetic function. We used a 5-dimensional version of the Michalewicz function. AGNP and CrossedBarrel are 5-dimensional and 4-dimensional real-world problems, respectively. We will amend the manuscript to include the dimensionality of each of the problems.\n\nAs we prove in the paper, LB-GP-UCB can recover performance \"close\" to the performance of GP-UCB optimiser with the oracle knowledge of the optimal length scale value. However, it is well-known that even the regret bound of this oracle optimiser would grow with the dimensionality of the problem and same is true for the LB-GP-UCB. To remedy that, one could enhance LB-GP-UCB optimiser in the same way as standard BO optimiser is being enhanced to perform well in high-dimensional spaces (e.g. by adding a Trust Region or decomposing the input space). These enhancements are orthogonal to our method.\n\n(4) Yes, we do have wallclock times for our experiments. We provide them below and **will update the script to include the exact wallclock times in the Appendix**. All the times below are seconds, values after +/- are standard errors from accross the seeds.\n\n**Berkenkamp Function:**\n\nMLE : 438 +/- 0.66\n\nA-GP-UCB : 443 +/- 1.51\n\nLB-GP-UCB : 442 +/- 1.68\n\nMCMC : 1653 +/- 25.99\n\n**Michalewicz Function:**\n\nMLE : 237 +/- 2.41\n\nA-GP-UCB : 167 +/- 0.88\n\nLB-GP-UCB : 181 +/- 0.47\n\nMCMC : 3388 +/- 369.38\n\n**Crossed Barrel Materials Experiment:**\n\nMLE : 55 +/- 0.1\n\nA-GP-UCB : 48 +/- 0.4\n\nLB-GP-UCB : 48 +/- 0.5\n\nMCMC : 471 +/- 25.2\n\n**AGNP Materials Experiment:**\n\nMLE : 53 +/- 0.05\n\nA-GP-UCB : 49 +/- 0.18\n\nLB-GP-UCB : 49 +/- 0.16\n\nMCMC : 246 +/- 3.56\n\nAs such, LB-GP-UCB is faster than MLE on all benchmarks except for Berkenkamp Function, where it is 4 seconds ($\\approx 1$ \\%)  slower. MCMC is significantly slower than any other baseline.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2f6AcDwv6m", "reviewer": "Reviewer_k1W2", "summary": "This paper proposes a novel Bayesian optimization algorithm for the setting with unknown kernel lengthscale. The proposed approach improves upon prior work by running a logarithmic array of algorithms on exponentially decreasing lengthscales in combination with a regret balancing scheme. The paper proves a regret guarantee with an exponential improvement compared to prior work in the ratio of the regret compared to the oracle algorithm that knows the optimal lengthscale. The experimental evaluation also shows substantial improvements compared to prior the prior work.", "questions": "N/A", "limitations": "The main limitation is that the approach so far only works for a scalar parameter that induces a natural nesting of Hilbert spaces.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Originality: This paper introduces a clever regret balancing scheme to obtain a improved regret bound for Bayesian optimization with unknown kernel lengthscale. While the individual ideas already appear in prior work (e.g. regret balancing, and decreasing the lengthscale), the combination in this setting is novel. \n\nQuality & Clarity: The paper is overall well written but could benefit from careful proof reading (some suggestions below). The main idea is easy to follow and there is an extensive comparison to the prior work. The regret bound is a significant improvement over prior work. The experimental evaluation shows that the proposed approach outperforms the prior work.\n\nSignificance: The findings are of high interest to the Bayesian optimization community (and users of Bayesian optimization) as selecting hyperparameter remains a major challenge. In particular, classical schemes (like marginal likelihood) tend to fail because there is too little data initially.", "weaknesses": "The paper could use some polishing for English and punctuation (e.g. many sentences are quite long). In addition, the authors could provide more intuition (e.g. why regret balancing works, and the elimination scheme) and try to make the paper more accessible to readers not familiar with the tools used.\n\n Minors:\n* line 110: punctuation\n* Algorithm 1, line 7: Is there a simpler notation for the set $S_t^\\theta$ ?\n* 209: Long sentence, unclear what \"their\" refers to.\n* 229: Wording/missing word \"highest ? as possible\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for reading our submission, and pointing out the issues with writing. **We will correct the writing errors pointed out by the reviewer and try to break long sentences into shorter ones.** We agree that the algorithm is quite complex and it would be good to give more intuition to the readers. **We plan to use the additional page in the camera-ready version to add a longer, more intuitive explanation of the regret balancing scheme with some easily-understandable figures.**\n\nWhen it comes to the definition of set $S_t^\\theta$, in the pseudocode, it would be possible to drop the iteration subscript $t$ and just redefine the set at each iteration. However, we explicitly wanted to index this set by the current timestep $t$ and the hyperparameter value $\\theta$, as this notation is very convienient later in the proofs.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0YNdDtDQSg", "reviewer": "Reviewer_YCMG", "summary": "This paper considers the Bayesian optimization (BO) problem under an unknown length scale and upper bound of the RKHS norm.\nThe proposed algorithm LB-GP-UCB is designed to select length scale \nfrom certain candidates set adaptively. Furthermore, the algorithm eliminates some candidate length scales if certain conditions are met. The validity of the proposed algorithm is given both empirically and theoretically. Specifically, the proposed algorithm has \na favorable property compared with the existing A-GP-UCB algorithm in the sense of regret optimality.", "questions": "- Is there a possibility of extending the algorithm to a case where length scale parameters are different among each coordinate?\n\n- In Proposition 2.3, can the author update the Berkenkamp's MIG upper bound of Mat\\'ern to $\\tilde{O}(T^{\\frac{d}{2\\nu + d}})$?\nThe recent result (Vakili et al., 2021) shows that the maximum information gain of Mat\\'ern kernel increases \nwith $\\tilde{O}(T^{\\frac{d}{2\\nu + d}})$. Their results do not provide explicit dependence \nof $\\theta$; however, by combining Theorem 3 of Vakili et al. and the eigendecay rate of the kernel with explicit dependence of $\\theta$, \nI guess that $\\gamma_T = \\tilde{O}(\\theta^{-2\\nu + d} T^{\\frac{d}{2\\nu + d}})$ can be obtained. \n    - Vakili, Sattar, Kia Khezeli, and Victor Picheny. \"On information gain and regret bounds in gaussian process bandits.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n- The exact upper bound of the MIG is obtained by relying on the uncertainty sampling as described in Section 5.1 of Srinivas's paper.\nDoes any problem occur with using Srinivas's results in the author's analysis?\n    - Srinivas, Niranjan, et al. \"Gaussian process optimization in the bandit setting: No regret and experimental design.\" arXiv preprint arXiv:0912.3995 (2009).", "limitations": "- The analysis is limited to the case where the length scale parameters are the same among each coordinate.\n- No potential negative societal impact is seen.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The motivation is well-discussed; specifically, I agree with the issue of \nthe A-GP-UCB algorithm described in the Introduction.\n- From my view, the comparison with A-GP-UCB in the sense of regret optimality is interesting and novel.\n- Enough numerical evaluations are given, and the author also provides the anonymized codes with an easily reproducible style.", "weaknesses": "- In contrast to the existing literature (Berkenkamp, 2019), the analysis is limited to where the length scale parameters are the same among each coordinate. This relates to the limitation of the practical applicability, and I think that the comparison with A-GP-UCB should be evaluated by noting this limitation. \n\n- The method how to calculate the quantity $R^{\\theta}$ (Line 3), which contains MIG we only \nknow the dependence of $T$ and $\\theta$ of its upper bound, is ambiguous. \nAs far as I see the proof of Lemma C.1 and the statement of Lemma 5.2 of Pacchiano et al.,\n$R^{\\theta}$ should be specified as the exact upper bound of regret; only the knowledge \nof the order of the regret upper bound is insufficient to specify $R^{\\theta}$. \nIf we cannot calculate the exact value or upper bound of $R^{\\theta}$, this part can become a limitation,\nand the author at least should add the discussion. As far as I see the anonymized code, the numerical experiments are done by\napproximating the upper bound of MIG with the numerically optimized version of MIG (Hong et al, 2023).\nEven if we follow Hong et al, 2023, I believe that the exact version of the upper bound of MIG can be computed only when the input space $\\mathcal{X}$ is finite and small.\n\n- To my understanding, the Ziomek's paper is closely related to your setting, and it seemed \nthat some parts of your paper (e.g., Lemma A.2) borrow their ideas; however, the relation \nand comparison with their paper are not described in Related Works.\n\nZiomek, Juliusz, Masaki Adachi, and Michael A. Osborne. \"Beyond Lengthscales: No-regret Bayesian Optimisation With Unknown Hyperparameters Of Any Type.\" arXiv preprint arXiv:2402.01632 (2024).\n\n\n[Minor]\n\n- L108 $x^{\\ast} = \\max_{x \\in \\mathcal{X}}$ -> $x^{\\ast} = \\max_{x \\in \\mathcal{X}} f(x)$.\n- L110 ... value $\\theta \\in \\mathbb{R}$ we denote -> ... value $\\theta \\in \\mathbb{R}$. We denote\n- L117 ... them below:: -> ... them below:\n- L119 $\\theta \\in \\\\{0, \\theta_0\\\\}$ -> $\\theta \\in (0, \\theta_0]$.\n- L129 $\\gamma(k^{\\theta})\\_{t-1}$ -> $\\gamma_{t-1}(k^{\\theta})$\n- L129 $\\frac{1}{2} \\ln |I + \\sigma_N^2 K_T^{\\theta^{\\ast}}|$ -> $\\frac{1}{2} \\ln |I + \\sigma_N^{-2} K_T^{\\theta}|$.\n- Footnote 1 and Lemma 4: This statement does not hold for any stationary kernel (see Assumption 2 in Bull [11]). \nI recommend the author explicitly assume RBF or Mat\\'ern kernel in these statements.\n- Liu et al., 2023 related to your setting. Although the unknown hyperparameter they consider is different from the setting \nof your paper, I recommend adding their paper as the related work.\n    - Liu, Yusha, and Aarti Singh. \"Adaptation to Misspecified Kernel Regularity in Kernelised Bandits.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for reading our paper and for mentioning relevant related work. We address each question/concern below.\n\n**Case of different length scales**\n\nThe method of Berkenkamp (2019) cannot really handle kernels with differing length scales across coordinates. While technically A-GP-UCB can be applied to non-isotropic kernels, it decreases the lengthscale value for each coordinate at the same pace (e.g. see eq. 9 in (Berkenkamp, 2019)). As such, unless the initial length scales $\\theta_0$ differ for each coordinate (which would imply strong some prior information on the relative importance of coordinates), A-GP-UCB utilises the same length scale value for each coordinate at each timestep, making it no better than an algorithm utilising the isotropic kernel. As such, our algorithm is not inferior to A-GP-UCB on that regard. \n\nAs we mention in Section 7, to the best of our knowledge, there have been no results in the literature deriving the MIG bounds for the non-isotropic kernels. If one were to obtain such bounds, we believe we could very easily extend our algorithm LB-GP-UCB to handle multiple unknown length scales, in the same way as we extended it to the case of simultaneously handling unknown norm and length scale. Such an algorithm would truly handle the non-isotropic case and would be able to potentially choose to fit a GP model with different length scale values, unlike A-GP-UCB.\n\n**Updating MIG bound**\n\nWe would like to thank the reviewer for mentioning that the improved MIG bounds exist, as we were not aware of that fact. **We will replace the MIG bounds with the improved ones in our Theorems.**\n \n**Relation to Ziomek et al, 2024**\n\nThe problem setting considered in (Ziomek et al, 2024) differs from ours, as they assumed there are a number of candidate hyperparameter values given to us at the start of the problem, making the problem much easier. Their proposed algorithm also scales with the MIG of the worst candidate and as such could be arbitrarly far from the optimal. **We will add this discussion to the Related Work section.**\n\n**Knowledge of Regret Bounds**\n\nOne do not need the exact form of the regret bounds---the knowledge up to a constant is sufficient. The fact that the algorithm selects hyperparameters by the rule in line 3 is only used in two places in the proof of the Theorem 4.1 The first place is Lemma C.1., where the constants $C$ in the regret bounds cancel out. The second place is in line 472 - 474 on page 14, where we assume that for the regret bounds we must have $R(t+1) < R(t) + 2B$, since $2B$ is the highest instantaneous regret we can possibly suffer. If the order dependence is known, one can always find such a constant $C$ such that this constraint is respected.\n\nWhile the lack of need for exact knowledge of $C$ might seem surprising at first glance, it is a direct result of the fact the regret bound for LB-GP-UCB is also derived up to a constant factor. Changing $C$ in the suspected regret bound does not affect the order dependence of the regret bound of LB-GP-UCB. This is a very interesting point and we are grateful to the reviewer for mentioning it. **We will add a short discussion in the paper to clarify this.**\n\n**Applicability of the MIG bounds from (Srinivas et al, 2009)**\n\nThe results from Srinivas et al (2009) rely on uncertainty sampling to derive a bound on the sum of predictive variances for **any** strategy (the MIG bound). In fact, Srinivas et al (2009) use this MIG bound to derive a regret bound for the GP-UCB algorithm. If each of the GP-UCB base algorithms were run in isolation, these bounds clearly hold. These bounds must therefore also hold in the case, where datapoints are shared between algorithms, as variance is a non-increasing function of the number of conditioning datapoints. \n\n**Minor points**\n\nWe would like to thank the reviewer for pointing out the typos and that Lemma 4 of [11] requires an additional assumption. **We will correct the typos and explicitly restrict the statement to RBF or Matern kernel.** We would also like to thank for pointing out more relevant, related work, **we will add it to the related work section**.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for taking time to read our submission and provide insightful feedback, as well as asking interesting question. We answer to each of the reviewers individually below.

Meta-review: The paper introduces LB-GP-UCB, a novel Bayesian Optimization algorithm designed to address the challenge of unknown hyperparameters, particularly the kernel length scale, in Gaussian Process models. The key contribution is a regret minimization approach that shows logarithmic improvement over existing methods, such as A-GP-UCB. The reviewers agree that the theoretical advancements are significant, and the empirical results, though limited, demonstrate the method's effectiveness on selected benchmarks.

The paper could benefit from clearer mathematical presentation and discussions on practical issues like scalability. Should the paper be accepted, the authors are encouraged to expand the experimental evaluation and refine the clarity of their presentation.
Decision: Accept (poster)