Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal

Authors: juliusz  ziomek
masaki  adachi
michael a osborne
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-07 16:16:48

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.

Main paper: 
 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, 18, 23] . As a model-based optimisation technique, BO constructs a surrogate model of the black box function, which is typically a Gaussian Process (GP) [40] . However, to 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 is reflected in the selection of an appropriate length scale value for the kernel function. Selecting smaller length scales allows us to 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 is neither too short nor too long. [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 a suboptimal value of x = 1, the optimiser with the optimal length scale can spot the hidden peak leading to finding the maximum at x * = 0.3.Appropriate selection of the length scale parameter can be challenging. Typical practice is to fit the length scale value by maximum likelihood estimation (MLE) on the observed data we have collected thus far. However, it is entirely possible that the function changes less smoothly in the regions we have not explored yet, as shown in Figure 1 . 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] approached this issue by progressively decreasing the length scale value, and as such increasing the class of functions considered by the optimiser.As a consequence, at some point, it must contain the black-box function we are trying to optimise. 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.A-GP-UCB is suboptimal because it never returns to previously trialled, longer length scales. Observe that if trying a 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 a 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 to balance exploration and exploitation. Within the literature of multi-armed bandit problems, a number of rules for aggregating base algorithms have been proposed [1, 3, 33] , 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-balancing, to handle infinitely many learners, so that it could tackle the problem of BO with unknown hyperparameters. We propose an algorithm called Length scale Balancing GP-UCB (LB-GP-UCB), which aggregates a number of base optimisers with different length scale values and gradually introduces new base optimisers, equipped with smaller length scales. Instead of permanently decreasing the length scale value, as done by A-GP-UCB, LB-GP-UCB occasionally introduces new base learners with smaller length scale values, while still maintaining 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 g(T ), we show that LB-GP-UCB is only log g(T ) away from oracle 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-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 2 . θ⋆ represents an estimate of optimal length scale value on this problem (see §5 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 our contributions below.• We propose LB-GP-UCB and show that compared to A-GP-UCB its regret bound is logarithmically 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. 
problem statement and preliminaries: 
 We consider the problem of maximising an unknown black-box function f : X → R on some compact set X ⊂ R d . At each time step t, we are allowed to query a function at a selected point x t ∈ X and observe noisy feedback y t = f (x t ) + ϵ t , where ϵ t ∼ SubGauss(σ 2 N ). We wish to find the optimum x ⋆ = max x∈X f (x). We define the instantaneous regret to be r t = f (x ⋆ ) -f (x t ) and cumulative regret as R T = T t=1 r t , and we wish to minimise it. We assume we are given some kernel functionk θ (x, x ′ ) = k( x θ , x ′ θ )parametrised by a length scale value θ ∈ R + and we denote its associated Reproducing Kernel Hilbert Space (RKHS) as H(k θ ). We assume that at least for certain values of θ, the black-box function f belongs to this RKHS, i.e. ∃ θ∈R + f ∈ H(k θ ). Concretely, we will consider two popular types of kernels: RBF and ν-Matérn, defined below for completeness:k θ RBF (x, x ′ ) = exp - ∥x -x ′ ∥ 2 2 θ 2 k θ ν-Matérn (x, x ′ ) = 2 1-ν Γ(ν) √ 2ν ∥x -x ′ ∥ θ ν K ν √ 2ν ∥x -x ′ ∥ θ ,where Γ(•) is the Gamma function and K ν (•) is the modified Bessel function of the second kind of order ν. Without the loss of generality, we assume k θ (•, •) ≤ 1 for all θ ∈ R + . 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 k θ (x, x ′ ) to the data so far, D t-1 = {(x τ , y τ )} t-1 τ =1 , we obtain the following mean µ θ t-1 (x) and variance (σ θ t-1 ) 2 (x) functions:  and σ 2 N is the regulariser factor [11] with identity matrix I. If we were to use any length scale value such that f ∈ H k θ , then we can obtain certain guarantees about the predictions made by the GP model, as stated next.µ θ t-1 (x) = k θ t-1 (x) T (K θ t-1 + σ 2 N I) -1 y t-1 (σ θ t-1 ) 2 (x) = k θ (x, x) -k θ t-1 (x) T (K θ t-1 + σ 2 N I) -1 k θ t-1 (x), where y t-1 ∈ R t-1 with elements (y) i = y i , k θ (x) ∈ R t-1 with elements k θ (x) i = k θ (x, x i ) and similarily K θ t-1 ∈ R t-1×t-1 with entries (K θ t-1 ) i,j = k θ (x i , x j ),Theorem 2.1 (Theorem 2 of [11]). Let f ∈ H k θ , such that ∥f ∥ k θ ≤ B and set β θ,B t = B + σ N 2(I t-1 (k θ ) + 1 + ln(1/δ A )), where I T (k θ ) is an upper bound 1 2 log|I + σ -2 N K θ ⋆ T | ≤ I T (k θ), which depends on the kernel and length scale choice. Then, with probability at least 1 -δ A , for all x ∈ X and t = 1, . . . , T :f (x) -µ θ t-1 (x) ≤ β θ,B t σ θ t-1 (x).Note that the Theorem 2.1 relies on the quantity I T (k θ ), also called maximum information gain (MIG). The next proposition, proven in Appendix A, provides bounds on I T (k θ ) for RBF and ν-Matérn kernel and shows the explicit dependence on length scale hyperparameter θ.Proposition 2.2. We have thatI T (k θ ) ≤ O γ T (k θ ) : • For an RBF kernel γ T (k θ ) = 1 θ d log(T ) d+1 • For ν-Matérn kernel γ T (k θ ) = 1 θ d T d(d+1) 2ν+d(d+1) log(T ) 2ν 2ν+dBased on the GP model, a typical BO algorithm constructs an acquisition function, which tells us how 'promising' a given point is to try next. We will focus on the commonly used Upper Confidence Bound (UCB), defined as UCB θ,B t (x) = µ θ t-1 (x) + β θ,B t σ θ t-1 (x). The GP-UCB algorithm [36, 11 ] fits a GP model and utilises the UCB criterion to select new points to query. Such an algorithm admits a high-probability regret bound as stated by the next Theorem. Theorem 2.3 (Theorem 2 in [11] ). Let us run a GP-UCB utilising a GP with a kernel k θ and the exploration bonus ofβ θ,B t = B + σ N 2(I T (k θ )) + 1 + ln(1/δ A )) on a black-box function f ∈ H(k θ ) such that ∥f ∥ k θ ≤ B.Then, with probability at least 1-δ A , it admits the following boundon its cumulative regret R T ≤ O R θ,B (T ) , where R θ,B (T ) = √ T B γ T (k θ ) + γ T (k θ ) .In our notation, note the distinction between the regret of an algorithm R T and the scaling of its bound R θ,B (T ). As the maximum regret we can possibly suffer at any time step, while optimising a function with property ∥f ∥ k θ ≤ B, is bounded as r t ≤ 2B , B ⋆ = arg min θ,B∈R + R θ,B (T ) such that ∥f ∥ k θ ⋆ ≤ B ⋆ .We assume we are given some initial θ 0 ≥ θ ⋆ and B 0 ≤ B ⋆ . As explained in the introduction, in practice, those initial values could be found by maximising the marginal likelihood for a small number of initial data points. We now notice one interesting property. In the case of RBF and ν-Matérn kernels, if we change the length scale value from θ 0 to θ and the norm bound from B 0 to B, we get that the regret bound with those new hyperparameters scales as follows:norms in the form of B(θ, N ) = ( θ0 θ ) d/2 N , where N is the norm bound under θ 0 and becomes the new hyperparameter we wish to select, instead of B. The optimal values of hyperparameters under this new parameterization are thus θ⋆ , N ⋆ = arg min R θ,B(θ,N ) (T ) subject to ∥f ∥ k θ ⋆ ≤ B(θ ⋆ , N ⋆ ).Notice that min θ∈(0,θ0] B(θ, N ⋆ ) = N ⋆ and as such it does not make sense to try values of N smaller than B 0 . Using this new parameterization brings an important benefit, as stated next. Lemma 2.1 (Consequence of Lemma 4 in [9] ). In case of RBF and Matérn kernels, for any θ < θ ⋆ and N > N ⋆ , we have that ∥f ∥ k θ ≤ B(θ, N ).We will thus refer to any pair (θ, N ), such that θ ≤ θ ⋆ and N ≥ N ⋆ , as well-specified hyperparameters, 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 θ ⋆ . We will thus be writingβ θ t = β θ,B(θ,N ⋆ ) t , UCB θ t (•) = UCB θ,B(θ,N ⋆ ) t (•) and R θ (•) = R θ,B(θ,N ⋆ ) (•). However, we would like to 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. 
length scale balancing: 
 Aggregation schemes describe a 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 a 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 is 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 be too far from the regret of the best well-specified candidate. It 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-suggesting function q(•) : N → R + , such that the ith candidate length scale value to consider is given by q(i). Definition 3.1. Let us define the length scale candidate-suggesting function q(•) : N → R + as a mapping for each i ∈ N of form:q(i) = θ 0 e -i/d .We want to ensure that one of the candidates we will eventually introduce will be close to θ ⋆ . Let us denote θ = arg max i∈N ; q(i)≤θ ⋆ q(i) to be the largest length scale suggested by our candidatesuggesting function that is still smaller than θ ⋆ . Observe that ∥f ∥ k θ ≤ B( θ, 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 R θ ⋆ (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 ν-Matérn kernel, we have that:R θ (T ) R θ ⋆ (T ) = O (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 i ∈ N, we have q(i) > 0, and the candidate-suggesting function q(•) 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 θ L , then we would create a maximum of q -1 (θ L ) candidates, that is, d ln( θ0 θ L ). However, this would require us to know a sure lower bound on the optimal length scale 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 θ L (t) = θ0 g(t) , based on some growth function g(t). Observe that since ln θ0 θ L (t) = ln(g(t)), the number of candidate values grows only logarithmically with the growth function g(t). 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 in §5. However, we would like to emphasise that, unlike A-GP-UCB which simply sets its length scale value to θ L (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 in better scaling of the regret bound we derive later. In Algorithm 1, we present LB-GP-UCB, an algorithm employing this mechanism. We now briefly explain the logic behind its operations.The algorithm starts in line 1 by initialising the set of candidates to just the upper bound θ 0 . Later on, in lines 14-16, new candidates are introduced using the candidate-suggesting function q(•) at a pace dictated by the growth function g(t). Typically in aggregation schemes, each one of the base algorithms is run in 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 scaleRequire: initial length scale value θ 0 ; suspected regret bounds R θ (•); growth function g(•); confidence parameters {ξ t } T t=1 and{β θ t } T t=1 1: Set D 0 = ∅, Θ 1 = {θ 0 }, S θ 0 = ∅ for all θ ∈ Θ, length scale counter l = 1 2: for t = 1, . . . , T do 3: Select length scale θ t = arg min θ∈Θt R θ (|S θ t-1 | + 1) 4:Select point to queryx t = arg max x∈X UCB θt t-1 (x) 5:Query the black-boxy t = f (x t ) + ϵ t 6:Update data bufferD t = D t-1 ∪ (x t , y t ) 7:For each θ ∈ Θ t , set S θ t = {τ = 1, . . . , t : θ τ = θ} 8:Initialise length scales set for new iterationΘ t+1 := Θ t 9: if ∀ θ∈Θt |S θ t | ̸ = 0 then 10: Define L t (θ) = 1 |S θ t | τ ∈S θ t y τ - ξt |S θ t | 11:{# Eliminate underperforming length scale} 12:Θ t+1 = θ ∈ Θ t : L t (θ) + 2 |S θ t | τ ∈S θ t β θ τ σ θ τ -1 (x τ ) ≥ max θ ′ ∈Θt L t (θ ′ ) 13:end ifif q(l + 1) ≤ θ0 g(t) then 15:Θ t+1 := Θ t+1 ∪ {q(l + 1)} {# Add shorter length scales} 16:l := l + 1 17:end if 18: end for value we will use to fit the GP model at a given time step t, which is done in line 3. This choice is done by the regret-balancing rule θ t = arg min θ∈Θt R θ (|S θ t | + 1), with R θ (•) defined as in Theorem 2.3 and S θ t being the set of iterations before t at which length scale value θ was chosen. Note that we only need to know the scaling of the bound up to a 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, x t . The idea is that, occasionally, θ t will be set to one of the smaller values from Θ t and, if that results in finding significantly better function values, then the rejection mechanism in lines 9-12 will remove longer length scales from the set of considered values, Θ t . Otherwise, we will keep all of the length scales and try again after some number of iterations. We now proceed to derive a regret bound for our developed algorithm. 
regret bound and proof sketch: 
 We now state the formal regret bound of the proposed algorithm, provide a brief sketch of the proof and discuss the result. Theorem 4.1. Let us use confidence parameters of ξ t = 2σ 2 N log d ln(g(t))π 2 t 2 -log 3δ andβ θ t = B(θ, N ⋆ ) + σ N 2(γ θ t-1 + 1 + ln(2/δ)), then Algorithm 1, achieves with probability at least 1 -δ, the cumulative regret R T of the algorithm admits the following bound:R T = O (t 0 + ι) B ⋆ + R θ ⋆ (T ) + T ξ T θ 0 θ ⋆ d d ln θ 0 θ ⋆ + ι ,where t 0 = g -1 e -1/d θ 0 /θ ⋆ and ι = d ln g(T ).Proof. (sketch) We provide a sketch of the result here and defer the proof to Appendix D.Let us denote by t 0 the iteration at which the first well-specified length scale ( θ ≤ θ ⋆ ) is added to the candidate set in line 15. This will happen at the first iteration after g -1 ( θ0 θ ⋆ ), where the condition in line 14 will trigger. Given the ratios between consecutive candidates suggested by q(•), 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.Optimality R T /R ⋆ (T )Unknown θ Unknown θ and B A-GP-UCB [6] O(g(T ) d ) O(b(T )g(T ) d ) LB-GP-UCB / LNB-GP-UCB (ours) O(d ln g(T )) O(d ln g(T ) ln b(T )) t 0 = ⌈g -1 ( θ0 θ ⋆ e -1/d )⌉.On iterations up to t 0 , we can potentially suffer the highest as possible, thus the cumulative regret can be bounded as:R T = t=1,...,t0-1 r t + t=t0,...,T r t ≤ 2B ⋆ t 0 + RT ,where RT is the regret of the algorithm after t 0 . Let us define by T the set of iterations, where we reject at least one length scale value in line 12. We thus have:RT = t∈T r t + t / ∈T r t ≤ 2B ⋆ |T | + t / ∈T r t ≤ 2B ⋆ q -1 ( θ 0 g(T ) ) + t / ∈T r 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 do is to bound t / ∈T r t . 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 a similar strategy as in [33] . First, we show that, with a probability of at least 1 -δ, the well-specified candidate introduced at t 0 will not be rejected. Second, since no other candidates are rejected at iterations t / ∈ T , it means that the function values achieved at those iterations cannot be too different from the ones achieved when using θ. Using this fact, we arrive at a statement:t / ∈T r t ≤ R θ (|S θ t |) + T ξ T θ∈M0 |S θ t | |S θ t | + q -1 θ 0 g(T ),where M 0 is the set of misspecified length scale values that were chosen at least once after t 0 . The rest of the proof consists of bounding|S θ t | |S θ t |, which can be done due to the selection rule in line 3.Optimality In Appendix H, we show that for a fixed choice of growth function, we getR T /R θ ⋆ (T ) = O(d ln g(T )). This is an improvement compared to A-GP-UCB achieving R T /R θ ⋆ (T ) = O(g(T ) d ).As such the bound of our algorithm is significantly closer to the optimal bound than the one of A-GP-UCB. The faster g(•) is increasing, the quicker we will be able to find the first well-specified candidate, which will decrease the term t 0 B ⋆ in the bound. At the same time, it will increase all the terms depending on g(T ), but as our bound only scales with d log g(T ), we are able to select much more aggressive growth functions than A-GP-UCB, whose bound scales with g(T ) d . In the Experiments section we compare the performance of LB-GP-UCB and A-GP-UCB using different growth functions g(t) and show that the former algorithm is much more robust to the choice of g(t).Extension to unknown N ⋆ As we discussed before, LB-GP-UCB requires us to know the initial RKHS norm N ⋆ . However, we can easily extend the algorithm to handle the case of unknown N ⋆ , which we do in Appendix F. In Algorithm 3 we present Length scale and Bound Balancing (LNB)an algorithm, which in addition to having candidates for θ also maintains a number of candidates for N ⋆ . As such, it requires us to specify another growth function b(t) for exploring new norm values as well as the initial RKHS norm B 0 . We prove its cumulative regret bound in Theorem F.1. We can similarly derive the suboptimality gap for our algorithm in this case. We display it in Table 1 together with the gap of A-GP-UCB. We can see that in this setting, we also achieve an improvement. 
experiments: 
 We now evaluate the performance of our algorithm on multiple synthetic and real-world functions.To run experiments we used the compute resources listed in Appendix I.1 and implemented based on the codebase of [2] , which uses the BoTorch package [5, 34] . We open-source our code2 . We used the UCB acquisition function and we compared different techniques for selecting the length scale value. For all experiments, we used isotropic ν-Matérn 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-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 [7] . We use BoTorch's default hyperprior (θ ∼ Γ (3, 6) ) and to select a new point we optimise the expected acquisition function under the posterior samples as described by [13] . We also compare against A-GP-UCB. To achieve a fair comparison, we used the same growth function g(t) = max{t 0 , √ t} for both LB-GP-UCB and A-GP-UCB across all experiments, where t 0 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 θ 0 for A-GP-UCB and LB-GP-UCB we fitted a length scale to initial data points with MLE (and we did not use MLE after that). We present the results in Figure 3 below. We show running times in Table 2 in Appendix I.2. We now describe each benchmark problem in detail. We start with a one-dimensional toy problem proposed by the same paper that proposed the A-GP-UCB algorithm [6] . We showed a plot of this one-dimensional function in Figure 1 . 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 on 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-UCB 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 a next benchmark, we evaluate our algorithm on the fivedimensional Michalewicz 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 2 , we compare the selected length scale value with an estimate of the optimal length scale θ * . 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 it is least smooth. We can see LB-GP-UCB selects lengthscale value closer to θ * 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 [17] and [30] -the 4dimensional CrossedBarrel and 5-dimensional AGNP tasks. At each time step, the algorithm can choose which material configuration to try, and observe the objective value, which corresponds to a given material optimisation criterion. As material design problems are known to exhibit a needle-in-a-haystack behaviour [35] , on both benchmarks MLE and MCMC get stuck at a suboptimal solution and their best regret does not fall beyond a 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.To test robustness of LB-GP-UCB, we evaluate it on Michalewicz function together with A-GP-UCB for different choices of g(t). We try functions of form g(t) = max(t 0 , t a ) for a ∈ (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 is very sensitive to the selection of growth function g(t), whereas our algorithm selects similar length scale values regardless of g(t), which results in consistently good best regret results. We can also see that LB-GP-UCB typically selects values around θ * for different growth functions, whereas A-GP-UCB decreases its length scale beyond θ * , resulting in slower convergence.g(t)=max(t 0 , t 1/4 ) g(t)=max(t 0 , t 3/4 ) g(t) = max(t 0 , t 1/2 )Length scale θ * 1 0 2 A-GP-UCB LB-GP-UCB 0 0.1Figure 4 : Ablation study of the choice of growth function g(t). t 0 is chosen so that at least 5 candidates are generated at g (1) . See beginning of §5 for details. 
related work: 
 We already mentioned the work proposing A-GP-UCB [6] , which so 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, a lower bound on the optimal length scale is known, however, the regret bound of the algorithm they propose scales with the γ T (k θ L ) of the smallest possible length scale θ L , making it no better than a naïve algorithm always selecting θ L . [8] studied the problem of solving BO, when the kernel function is misspecified, however, provided no method for finding the well-specified kernel function. [26] proved a lower bound on the algorithm's regret in the case when the regularity of RKHS is unknown (which corresponds to 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 a number of works [13, 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 works [15, 38] 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 a frequentist problem setting, where the black-box function is arbitrarily selected from some RKHS. While there are no guarantees for the consistency of MLE in such a setting, if we were to assume a Bayesian setting and put a GP prior on the black box, statistical literature derived asymptotic consistency results [4, 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. [10] 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 is because our algorithm requires the knowledge of the regret bounds of an optimiser utilising a given length scale value, which in turn requires the knowledge of the bounds on MIG γ T (k θ ) for the used kernel. To the best of our knowledge, within the existing literature, no work has yet derived those bounds in non-isotropic cases. However, we believe that if such bounds were obtained, one could easily extend our algorithm to the non-isotropic case, in the same way as we extended our base algorithm to handle unknown norm and length scale simultaneously. This constitutes a promising direction of future work.Another limitation of our work is the assumption of known noise magnitude σ N . The problem of simultaneously not knowing kernel hyperparameters and noise magnitude is extremely challenging, as large variations in observed function values can be a result of either short lengthscale value or large noise magnitude. To the best of our knowledge, previous work did not tackle this setting and it remains an open problem.Our algorithm relies on the standard GP model, which can result in poor scalability to large datasets and high-dimensional spaces. Extending our work to sparse GPs [29, 31] and kernels specifically designed for a high number of dimensions [14, 42] is another possible direction of future work.A Proof of Proposition 2.2 Proposition 2.2. We have that I T (k θ ) ≤ O γ T (k θ ) :• For an RBF kernel γ T (k θ ) = 1 θ d log(T ) d+1 • For ν-Matérn kernel γ T (k θ ) = 1 θ d T d(d+1) 2ν+d(d+1) log(T ) 2ν 2ν+dProof. The RBF case follows directly from Proposition 2 in [6] . The same Proposition also provides a bound for the ν-Matérn case, but more recent results allow us to derive a tighter bound. Section B.2. in [6] proves that the ν-Matérn kernel has the (C p ,β P ) polynomial eigendecay: β P = (2ν + d)/d and C p = 1 θ 2ν+d , according to the definition of polynomial eigendecay as given by [37] . Substituting these values to Corollary 1 of [37] , we get that in ν-Matérn caseI θ T = O C 1/β P p T 1/β P log 1-1/β P (T ) 1-1/β P = O 1 θ d T d/(2ν+d) log 2ν/(d+2ν) (T ) 2ν/(d+2ν) ,which finishes the proof. We first derive a general result for a BO Algorithm utilising a 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 to note that our proof closely follows the idea of [33] . We assume the unknown hyperparameter takes values in some set U and specifying this hyperparameter uniquely defines a kernel function k u (•, •) and the RKHS norm B u . We say a hyperparameter value is well-specified if |f | k u ≤ B u . Algorithm 2 requires hyperparameter-proposing function a(•) as one of the inputs, which optionally expands the set of considered hyperparameters. We will denote by A = t=0,...,T a(t) the set of all hyperparameters introduced by a(•) up to step T . We will also denote W to mean the set of all well-specified hyperparameters in A and M = A \ W to denote the set of misspecified hyperparameters. Let u ⋆ be the first well-specified hyperparameter introduced. We will also write T to mean the set of all iterations after (and including) t 0 , where at least one hyperparameter value was rejected, that is: 
safeguards: 
 Question: 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, or scraped datasets)?Answer: [NA]Justification: The paper is not accompanied by a release of any new data sets or pre-trained models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: We clearly cite the research papers that proposed the materials dataset we use.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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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 package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: T =    t = t 0 , . . . , T ∃ u∈Ut L t (u) + 2 |S u t | τ ∈S u t β u τ σ u τ -1 (x τ ) < max u ′ ∈Ut L t (u ′ )    .We also define M 0 = {u ∈ M|∃ t≥t0 u t = u} to be the set of all misspecified hyperparameters that were selected at least once after t 0 .Require: suspected regret bounds R u (•); hyperparameter-proposing function a(•); confidence parameters {ξ t } T t=1 and{β u t } T t=1 1: Set D 0 = ∅, U 1 = a(0) ,S u 0 = ∅ for all u ∈ U 1 , 2: for t = 1, . . . , T do 3: Select hyperparameter u t = arg min u∈Ut R u (|S u t-1 | + 1) 4:Select point to queryx t = arg max x∈X UCB ut t-1 (x) 5:Query the black-boxy t = f (x t ) 6:Update data bufferD t = D t-1 ∪ (x t , y t ) 7:For each u ∈ U t , set S u t = {τ = 1, . . . , t : u τ = u} 8:Initialise hyperparameter set for new iterationU t+1 := U t 9: if ∀ u∈Ut |S u t | ̸ = 0 then 10: Define L t (u) = 1 |S u t | τ ∈S u t y τ - ξt |S u t |11:U t+1 = u ∈ U t : L t (u) + 2 |S u t | τ ∈S u t β u τ σ u τ -1 (x τ ) ≥ max u ′ ∈Ut L t (u ′ ) 12:end ifOptionally expand hyperparameter set U t+1 := U t+1 ∪ {a(t))} 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 a result from existing literature on the concentration of noise. Lemma B.1 (Lemma 5.1 in [41] ). For each u ∈ A and t = 1, . . . , T we have:P   ∀ t=1,...,T ∀ u∈A i∈S u t ϵ i ≤ ξ t |S u t |   ≥ 1 -δ B ,whereξ t = 2σ 2 N log |A|π 2 t 2 6δ B .The next result we will need is the high-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.1 hold, then the optimal hyperparameter u ⋆ is never removed after it is introduced, i.e. u * ∈ U t for all t = t 0 , . . . , T , where t 0 is the first iteration, where the optimal hyperparameter u ⋆ 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 u t = u ⋆ the following holds:f (x * ) -f (x t ) ≤ µ u ⋆ t (x ⋆ ) + β u ⋆ t σ u ⋆ t (x ⋆ ) -µ u ⋆ t (x t ) + β u ⋆ t σ u ⋆ t (x t ) ≤ µ u ⋆ t (x t ) + β u ⋆ t σ u ⋆ t (x t ) -µ u ⋆ t (x t ) + β u ⋆ t σ u ⋆ t (x t ) = 2β u ⋆ t σ u ⋆ t (x t ), where the first inequality follows from the fact that the event of Theorem 2.1 holds and u ⋆ is wellspecified, and the second inequality is because we chose x t so as to maximise the UCB. Using this Proof. Let t ′ be the smallest iteration after t 0 , such that S u t ′ = S u T and t ′ / ∈ T , i.e. t ′ is the last iteration not in T when u was played. Notice that since t ′ / ∈ T , all hyperparameter values in U t ′ must satisfy the if statement in line 11 when compared with any other hyperparameter value in U t ′ . Let us choose any hyperparameter value in U t ′ and compare it with u ⋆ (which must be in U t ′ due to the event of Lemma B.3 that guarantees preservation of u ⋆ .). For the if statement to evaluate to true, we must have:1 |S u t ′ | t / ∈T t∈S u t ′ y t + 2 |S u t ′ | t∈S u t ′ β u t σ u t (x t ) + ξ t |S u t ′ | ≥ 1 |S u * t | t∈S u * t y t - ξ t |S u * t |.Multiplying both sides by -1 and adding f (x * ), we get:1 |S u t ′ | t / ∈T t∈S u t ′ (f (x * ) -y t ) - 2 t∈S u t ′ β u t σ u t (x t ) |S u t ′ | - ξ t |S u t ′ | ≤ 1 |S u ⋆ t ′ | t∈S u ⋆ t ′ (f (x * ) -y t ) + ξ t |S u ⋆ t ′ | .Using the fact that y t = f (x t ) + ϵ t and Lemma B.1 we get that:1 |S u t ′ | t / ∈T t∈S u t ′ (f (x * ) -f (x t )) - 2 t∈S u t ′ β u t σ u t (x t ) |S u t ′ | -2 ξ t |S u t ′ | ≤ 1 |S u ⋆ t ′ | t∈S u ⋆ t ′ (f (x * ) -f (x t )) + 2 ξ t |S u ⋆ t ′ | .Rearranging and observing that r t = f (x ⋆ ) -f (x t ), we obtain:t / ∈T t∈S u t ′ r t ≤2 t∈S u t ′ β u t σ u t (x t ) + 2 |S u t ′ |ξ t + |S u t ′ | |S u ⋆ t ′ | t∈S u ⋆ t ′ r t + 2|S u t ′ | ξ t |S u ⋆ t ′ | ≤CR u (|S u t ′ |) + 2 |S u t ′ |ξ t + |S u t ′ | |S u ⋆ t ′ | CR u ⋆ (|S u ⋆ t ′ |) + 2|S u t ′ | ξ t |S u ⋆ t ′ |, where we use the fact that 2 t∈S u t ′ β u t σ u t (x t ) ≤ CR u (S u t ′ ) for some constant C > 0, which follows from the proof of Theorem 2 of [11] on which we rely to obtain the suspected regret bounds. We also used the fact that due to u ⋆ being well-specified we have thatt∈S u ⋆ T r t ≤ CR u ⋆ (|S u ⋆ T |). We now apply Lemma B.3 to get that R u (|S u t |) ≤ R u ⋆ (|S u ⋆ t |) + 2B u ⋆. Substituting that to the bound developed above and noting that by definition S u t ′ = S u T , we get:t / ∈T t∈S u T r t = t / ∈T t∈S u t ′ r t ≤ |S u t ′ | |S u * t ′ | + 1 CR u ⋆ (|S u * t ′ |) + 2CB u ⋆ + 2 |S u t ′ | |S u * t ′ | + 1 |S u t ′ |ξ t = |S u T | |S u * T | + 1 CR u ⋆ (|S u * T |) + 2CB u ⋆ + 2 |S u T | |S u * T | + 1 |S u T |ξ t ,which finishes the proof.We are now ready to prove the final result of this Section. Lemma B.5. Let us run Algorithm 2 for T iterations with a given choice of the hyperparameterproposing function a : N → U. Let T be the set of all iterations after t 0 , where at least one hyperparameter is rejected by operation in line 11. If we setξ t = 2σ 2 N log |A|π 2 t 2 6δ B and β u t = B u + σ N 2(γ u t-1 + 1 + ln(1/δ A )), we then have that with probability as least 1 -δ A -δ B :t / ∈T r t = O |A|B u ⋆ + R u * (T ) + T ξ T u∈M0 |S u t | |S u ⋆ t ′ | + |A| .C Proof of Lemma 3.1 Lemma 3.1. In the case of both RBF and ν-Matérn kernel, we have that:R θ (T ) R θ ⋆ (T ) = O (1) . Proof. R θ (T ) R θ ⋆ (T ) = T γ θ T γ θ T + B( θ, N ⋆ ) T γ θ ⋆ T γ θ ⋆ T + B(θ ⋆ , N ⋆ ) = 2 θ ⋆ θ d ≤ 2 q(i ⋆ ) q(i ⋆ + 1) d = 2 e -1/d d = O(1),where i ⋆ = max{i ∈ N | q(i) ≥ θ ⋆ } and as such we have q(i ⋆ + 1) = θ ≤ θ ⋆ ≤ q(i ⋆ ). D Proof of Theorem 4.1 Theorem 4.1. Let us use confidence parameters of ξ t = 2σ 2 N log d ln(g(t))π 2 t 2 -log 3δ and β θ t = B(θ, N ⋆ ) + σ N 2(γ θ t-1 + 1 + ln(2/δ)), then Algorithm 1, achieves with probability at least 1 -δ, the cumulative regret R T of the algorithm admits the following bound:R T = O (t 0 + ι) B ⋆ + R θ ⋆ (T ) + T ξ T θ 0 θ ⋆ d d ln θ 0 θ ⋆ + ι ,where t 0 = g -1 e -1/d θ 0 /θ ⋆ and ι = d ln g(T ).Proof. We start with a similar regret decomposition as in the proof of Theorem 1 in [6] . Let t 0 be the first iteration, where a length scale value smaller or equal to θ ⋆ enters the hyperparameter set Θ t0 . We will refer to that value as θ. Before this happens, all hyperparameters in the set are misspecified and as such we cannot guarantee anything about the regret of those iterations. As such, we bound their regret by 2B ⋆ , which is the highest possible regret one can suffer at one iteration. We thus get:EQUATIONWe note that due to how we add new length scales, we have that t 0 ≤ g -1 ( θ0 θ ⋆ e 1/d ) and we defined RT be the cumulative regret of all iterations after t 0 . Let us define the set T to be the set of all iterations, where at least one hyperparameter was eliminated. We thus get the following regret bound:RT = t∈T r t + t / ∈T r t ≤ 2|T |B ⋆ + t / ∈T r t ≤ 2q -1 θ 0 g(T ) B ⋆ + t / ∈T r t ,where the last inequality comes from the fact that we cannot reject more hyperparameters than we have considered in total. We now rely on Lemma B.5, which provides a bound on t / ∈T r t with probability at least 1 -δ A -δ B and we set δ A = δ B = δ/2. In the notation of the Lemma, we can write A = t=1,...,T Θ t to mean the set of all length scale values introduced over the course of the algorithm running and by M 0 we mean all length scales longer than θ that were selected at least once after t 0 . We observe that |A| ≤ q -1 θ0 g(T ) and our optimal base learner is u ⋆ = θ. This gives us:t / ∈T r t = O q -1 θ 0 g(T ) B ⋆ + R θ (T ) + T ξ T u∈M0 |S u T | |S u * T | + q -1 θ 0 g(T )To finish the proof we rely on the following Lemma, which we prove in Appendix E.Within this section, we show how our algorithm can be extended to handle the case of an unknown RKHS norm. Let us define the following candidate-suggesting function for the RKHS norm hyperparameter. Definition F.1. Lets consider the following candidate-suggesting function v(•) : N → R + to be a mapping for each i ∈ N of form:v(i) = N 0 e i .For RKHS being selected by the candidate-suggesting 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 ν-Matérn kernel, we have that:R ( θ,B( θ, N )) (T ) R (θ ⋆ ,B(θ ⋆ ,N ⋆ )) (T ) = O (1) . Proof. Case 1: γ θ T > B( θ, N ) R ( θ,B( θ, N )) (T ) R (θ ⋆ ,B(θ ⋆ ,N ⋆ )) (T ) = T γ θ T γ θ T + B( θ, N ) T γ θ ⋆ T γ θ ⋆ T + B(θ ⋆ , N ⋆ ) ≤ 2 θ ⋆ θ d ≤ 2 q(i ⋆ ) q(i ⋆ + 1) d = 2 e -1/d d = O(1),where i ⋆ = max{i ∈ N | q(i) ≥ θ ⋆ } and as such we have q(i ⋆ + 1) = θ ≤ θ ⋆ ≤ q(i ⋆ )r.Case 2:γ θ T ≤ B( θ, N ) R ( θ,B( θ, N )) (T ) R (θ ⋆ ,B(θ ⋆ ,N ⋆ )) (T ) = T γ θ T γ θ T + B( θ, N ) T γ θ ⋆ T γ θ ⋆ T + B(θ ⋆ , N ⋆ ) ≤ 2 γ θ T B( θ, N ) γ θ ⋆ T B(θ ⋆ , N ⋆ ) ≤ 2 q(i ⋆ ) q(i ⋆ + 1) d v(j ⋆ + 1) v(j ⋆ ) ≤ 2 e -1/d d e = 2 = O(1)where i ⋆ = max{i ∈ N | q(i) ≥ θ ⋆ } and j ⋆ = max{j ∈ N | v(j) ≤ N ⋆ } as such we have q(i ⋆ + 1) = θ ≤ θ ⋆ ≤ q(i ⋆ ) and v(j⋆ + 1) = N ≥ N ⋆ ≥ v(j ⋆ ).We can now prove the regret bound. Theorem F.1. Let us use confidence parameters of ξ t = 2σ 2 N log(d ln g(T ) log b(T )π 2 t 2 ) -log(3δ) and β θ,N t = B(θ, N ) + σ N 2(γ θ t-1 + 1 + ln(2/δ)), then Algorithm 3 achieves with probability at least 1 -δ the cumulative regret R T of the algorithm admits the following bound:R T = O (t 0 + ι) B ⋆ + R (θ ⋆ ,B(θ ⋆ ,N ⋆ )) (T ) + T ξ T θ 0 θ ⋆ d N ⋆ N 0 d ln θ 0 θ ⋆ ln N ⋆ N 0 + ι ,where t 0 = max{g -1 e -1/d θ 0 /θ ⋆ , b -1 (N ⋆ /N 0 )} and ι = d ln g(T ) log b(T ).Proof. Similarly as in the proof of Theorem 4.1, we look for t 0 , such that at least one wellspecified hyperparameter value will enter the considered set. This happens after at most t 0 = max{g -1 ( θ0 θ ⋆ e 1/d ), b -1 ( B B0 e)}. Observe that the set of all hyperparameters introduced by time step T is A = Θ T × B t . We thus have:R T ≤ 2t 0 B + |A|B + t / ∈T r t .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 R N0 d ln θ0 θ ⋆ ln N ⋆ N0 is a constant and will eventually get dominated by ι. We thus get that the bound will become dominated by ιR θ ⋆ (T ) or ιR (θ ⋆ ,B(θ ⋆ ,N ⋆ )) (T ) and the suboptimality is just ι.T = O(b(T )g(T ) d R u ⋆ (T )) and in BO R u (T ) = T γ u T ( √ B u + γ u T ),We used the code of [20] for computations of maximum information gain.To run all experiments we used a machine with AMD Ryzen Threadripper 3990X 64-Core Processor and 252 GB of RAM. No GPU was needed to run the experiments. We were running multiple runs in parallel. To complete one run of each method we allocated four CPU cores. Individual runs lasted up to seven minutes for each of the methods, except for MCMC runs, which could last up to an hour (see Table 2 below). 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).This is because f (x ⋆ ) -f (xt) ≤2∥f ∥∞ ≤ 2∥f ∥ k θ ≤ 2B.https://github.com/JuliuszZiomek/LB-GP-UCB 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * It is unclear how close the estimated length-scale and RKHS norm are to their true values at each iteration.
* There are no (theoretical) convergence results on the algorithm’s estimates, only the regret bounds.
* 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.
questions: 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: My concerns are mostly related to the experimental part of the paper.

**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.

**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.

**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". 

**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.
questions: questions: Here are some questions to spark the discussion with the authors.

(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?

(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.

(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?

(4) Do you have the precise wall-clock times for each solution and each experiment?
limitations: limitations: I believe the authors have properly addressed the limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

 Minors:
* line 110: punctuation
* Algorithm 1, line 7: Is there a simpler notation for the set $S_t^\theta$ ?
* 209: Long sentence, unclear what "their" refers to.
* 229: Wording/missing word "highest ? as possible"
questions: questions: N/A
limitations: limitations: The main limitation is that the approach so far only works for a scalar parameter that induces a natural nesting of Hilbert spaces.
paper_summary: paper_summary: This paper considers the Bayesian optimization (BO) problem under an unknown length scale and upper bound of the RKHS norm.
The proposed algorithm LB-GP-UCB is designed to select length scale 
from 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 
a favorable property compared with the existing A-GP-UCB algorithm in the sense of regret optimality.
strength_weakness: strength_weakness: - 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. 

- The method how to calculate the quantity $R^{\theta}$ (Line 3), which contains MIG we only 
know the dependence of $T$ and $\theta$ of its upper bound, is ambiguous. 
As far as I see the proof of Lemma C.1 and the statement of Lemma 5.2 of Pacchiano et al.,
$R^{\theta}$ should be specified as the exact upper bound of regret; only the knowledge 
of the order of the regret upper bound is insufficient to specify $R^{\theta}$. 
If we cannot calculate the exact value or upper bound of $R^{\theta}$, this part can become a limitation,
and the author at least should add the discussion. As far as I see the anonymized code, the numerical experiments are done by
approximating the upper bound of MIG with the numerically optimized version of MIG (Hong et al, 2023).
Even 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.

- To my understanding, the Ziomek's paper is closely related to your setting, and it seemed 
that some parts of your paper (e.g., Lemma A.2) borrow their ideas; however, the relation 
and comparison with their paper are not described in Related Works.

Ziomek, 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).


[Minor]

- L108 $x^{\ast} = \max_{x \in \mathcal{X}}$ -> $x^{\ast} = \max_{x \in \mathcal{X}} f(x)$.
- L110 ... value $\theta \in \mathbb{R}$ we denote -> ... value $\theta \in \mathbb{R}$. We denote
- L117 ... them below:: -> ... them below:
- L119 $\theta \in \\{0, \theta_0\\}$ -> $\theta \in (0, \theta_0]$.
- L129 $\gamma(k^{\theta})\_{t-1}$ -> $\gamma_{t-1}(k^{\theta})$
- L129 $\frac{1}{2} \ln |I + \sigma_N^2 K_T^{\theta^{\ast}}|$ -> $\frac{1}{2} \ln |I + \sigma_N^{-2} K_T^{\theta}|$.
- Footnote 1 and Lemma 4: This statement does not hold for any stationary kernel (see Assumption 2 in Bull [11]). 
I recommend the author explicitly assume RBF or Mat\'ern kernel in these statements.
- Liu et al., 2023 related to your setting. Although the unknown hyperparameter they consider is different from the setting 
of your paper, I recommend adding their paper as the related work.
    - Liu, Yusha, and Aarti Singh. "Adaptation to Misspecified Kernel Regularity in Kernelised Bandits." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.
questions: questions: - Is there a possibility of extending the algorithm to a case where length scale parameters are different among each coordinate?

- 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}})$?
The recent result (Vakili et al., 2021) shows that the maximum information gain of Mat\'ern kernel increases 
with $\tilde{O}(T^{\frac{d}{2\nu + d}})$. Their results do not provide explicit dependence 
of $\theta$; however, by combining Theorem 3 of Vakili et al. and the eigendecay rate of the kernel with explicit dependence of $\theta$, 
I guess that $\gamma_T = \tilde{O}(\theta^{-2\nu + d} T^{\frac{d}{2\nu + d}})$ can be obtained. 
    - 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.

- 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.
Does any problem occur with using Srinivas's results in the author's analysis?
    - Srinivas, Niranjan, et al. "Gaussian process optimization in the bandit setting: No regret and experimental design." arXiv preprint arXiv:0912.3995 (2009).
limitations: limitations: - The analysis is limited to the case where the length scale parameters are the same among each coordinate.
- No potential negative societal impact is seen.

Comments: title: Rebuttal Ack
comment: Thank you very much for taking the time to review our paper and respond to us. We are glad to know you are satisfied with our clarifications.
Thank you very much for taking the time to review our paper and respond to us. We are glad to know our rebuttal addressed your concerns.
Thanks for addressing my concerns. I keep my vote for this paper to be accepted, as it brings an important contribution to the BO community.
I'd like to thank the authors for the response and clarifications. I read the reviews and rebuttal, and my evaluation remains positive.
Thank you very much for taking the time to review our paper and respond to us. We are glad to know you are satisfied with our rebuttal.
Thank you for taking the time to review the paper and to respond to us. We are glad to know that our rebuttal addressed your concerns.
I thank the reviewer for responding to my questions and correcting some of my misunderstandings. I have raised my score to 6.
Thank you for the clarifications.

I am now positive about the paper and I have increased my score to 6.