Exploring and Exploiting Model Uncertainty in Bayesian Optimization
Authors: Zishi Zhang
Tao Ren
Yijie Peng
Venue: NeurIPS 2025 poster ()
Keywords: Gaussian Process
Bayesian Optimization
Uncertainty Quantification
Primary area: probabilistic_methods
TL;DR: We propose the infinite-Gaussian process model, enabling efficient Bayesian optimization under complex, non-stationary, and heavy-tailed reward landscapes.

Abstract: In this work, we consider the problem of Bayesian Optimization (BO) under reward model uncertainty—that is, when the underlying distribution type of the reward is unknown and potentially intractable to specify. 
This challenge is particularly evident in many modern applications, where the reward distribution is highly ill-behaved, often non-stationary, multi-modal, or heavy-tailed.
In such settings, classical Gaussian Process (GP)-based BO methods often fail due to their strong modeling assumptions. 
To address this challenge, we propose a novel surrogate model, the infinity-Gaussian Process ($\infty$-GP), which represents a sequential spatial Dirichlet Process mixture with a GP baseline. The $\infty$-GP quantifies both value uncertainty and model uncertainty, enabling more flexible modeling of complex reward structures. Combined with Thompson Sampling, the $\infty$-GP facilitates principled exploration and exploitation in the distributional space of reward models. Theoretically, we prove that the $\infty$-GP surrogate model can approximate a broad class of reward distributions by effectively exploring the distribution space, achieving near-minimax-optimal posterior contraction rates. Empirically, our method outperforms state-of-the-art approaches in various challenging scenarios, including highly non-stationary and heavy-tailed reward settings where classical GP-based BO often fails.

Exploring and Exploiting Model Uncertainty in Bayesian Optimization
Zishi Zhang', Tao Ren'; Yijie Pengl.2t 1.2
Guanghua School of Management, Peking University
2 Xiangjjang Laboratory fzishizhang, otteemm edu. cn, pengyijie@pku.e edu.
Abstract
In this work, we consider the problem of Bayesian Optimization (BO) under reward model uncertainty- that is, when the underlying distribution type of the reward is unknown and potentially intractable to specify. This challenge is particularly evident in many modern applications, where the reward distribution is highly ill-behaved, often non-stationary, multi-modal, or heavy-tailed. In such settings, classical Gaussian Process (GP)-based BO methods often fail due to their strong modeling assumptions. To address this challenge, we propose a novel surrogate model, the infinity-Gause Gaussian Process (oc-GP), which represents sequential spatial Dirichlet Process mixture with a GP baseline. The oo-GP quantifies both value uncertainty and model uncertainty, enabling more flexible modeling of complex reward structures. Combined with Thompson Sampling, the co-GP facilitates principled exploration and exploitation in the distributional space of reward models. Theoretically, we prove that the xc-G surrogate model can approximate a broad class of reward distributions by effectively exploring the distribution space, achiev- ing near-minimax -pttimalll posterior contraction rates. Empirically, our method outperforms state-of-the-ee approaches in various challenging scenarios, including highly non-stationary and heavy-tailed reward settings where classical GP-based BO often fails.
Introduction
Bayesian Optimization (BO) Frazier 2018 is a powerful framework for optimizing expensive-to- evaluate black-box functions and has found broad applications in hyperparameter tuning for machine learning models (Snoek et al. 2012). robotics [Berkenkamp et al.) 2023). biology [Amin et al., 2024 J and reinforcement learning [Brochu et al. 2010]. BO typically proceeds by fitting surrogate model the observed reward collected so far, and then using an acquisition policy to guide the selection of the next location to query. The surrogate model plays central role in both learning and exploration.
In almost all BO applications, Gaussian Processes (GPs) are used the default surrogate model. This practice assumes that the deterministic objective function jO" (x) and the noise e' e'(x) satisfy strong structural conditions, essentially requiring the true objective "resemble" GP. Specifically, μ (z
is often assumed to be sample path drawn from GP Russo and Van Roy 2014 Wang et al. 2025
or lie in a reproducing kernel Hilbert space (RKHS) with known bounded norm Srinivas et al. 2010
2012, Chowdhury and Gopalan 2017] (the connection between GP regression and RKHS regression
detailed Kanagawa al. 2018]) and c (a:) is assumed be independent and (sub-) Gaussian or even noiseless [Chen and Lam 2023]. These assumptions are critical for theoretical guarantees,
These authors contributed equally work. Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

but are rarely verified in practice. GP-based BO can fail when these assumptions are violated. For instance, GP surrogates struggle to model non con-stationary rewards, which are commonly observed in applying BO in machine learning hyperparameter tuning (Snoek et al. 2014), and are inadequate for handling heavy-tailed noise, which frequently arises in financial and real-world BO tasks [Chowdhury and Gopalan 2019 Cakmak et al. 2020]. Moreover, prompt optimization for large language models (LLMs) is another representative application (Sabbatella et al. 2024] where the reward model is of unknown and complex form. The reward typically involves multiple stages-such as combining with inputs, querying a black-box LLM, and interpreting outpuls- each introducing variation and instability. The resulting reward landscape is highly unstable and non-stationary (Deng et al. 2022 as even slight variations in prompt formulation can lead to dramatically different outputs.
In this paper, we consider BO under reward model uncertainty- that is, the decision-maker is uncertain not only about the parameters of the reward distribution, but also about its underlying distributional type. While classical GP-based BO can effectively quantify value uncertainty under a fixed model, fails to capture model uncertainty. Our goal is to develop a surrogate modeling and mrtisiin-making framework that remains robust under reward model uncertainty. To this end, we propose a novel surrogate model, the so-Gaussian Process (oc-GP), which represents an infinite mixture of Gaussian processes implemented via sequential spatial Dirichlet process prior with GP baseline. When combined with Thompson Sampling, this model automatically facilitates a principled exploration exploration-exploiatiie exploitation trade-off in the distributional space, and can effectively converge toward wide range of reward models.
Related Work. To address non-stationarity in BO, prior works have proposed various modifications, such warping the input space of standard GP kernels (Snock et al. 2014), replacing the surrogate model with neural networks (Li et al. 2023 or employing non ntn-stationary kernels [Higdon et al. 2022 Seeger 2004). To handle heavy- tailed noise, substantial body of work has been developed in the context of multi armed bandits, i.e., problems with a finite decision space [Bubeck et al.
2013 Medina and Yang 2016). However, for BO with continuous decision space, the available methods are much more limited. One notable exception is the work of Chowdhury and Gopalan 2019), who propose a truncation-based modification to the GP-UCB algorithm to handle heavy-tailed noises. Misspecified BO [Wynne et al., 2021 Bogunovic and Krause 2021] addresses limited forms of model mismatch (e.g., incorrect smoothness) within fixed model classes such GPs RKHS functions, rather than accounting for distributional uncertainty over the entire distributional space. fixture-of--experts GP models [Rasmussen and Ghahramani 2001 Meeds and Osindero, 2005 also construct infinite GP mixtures using Dirichlet processes. However, they rely on global DP to partition the input space, assigning each input to a single GP expert. In contrast, our model employs a spatial DP prior, allowing each location to mix over infinitely many GP surfaces. This leads to a fundamentally different formulation that offers a richer, nonparametric representation of model uncertainty and enables convergence over a broad class of reward distributions. |Barllttoo and Ho (024) also considers combining nonparametric Bayesian models, such as DP, with BO, However, their focus is on distributionally robust optimization, and the integration is carried out fundamentally differently from ours.
Our Contributions
The main contributions of this work are as follows:
A novel oP surrogate model. We propose a new surrogate model for BO, the oc- Gaussian Process (oo-GP), which quantifies both model uncertainty and value uncertainry. Combined with Thompson Sampling, it enables principled and efficient exploration and exploitation in the distributional space of the reward.
Theoretical guarantees. We establish posterior convergence guarantees for the co-GP model, showing that it can approximate a broad class of reward distributions at a near- optimal minimax rate.
Strong empirical performance. We demonstrate the effectiveness of our method on both synthetic benchmarks and real-world tasks where standard GP-based BO particclall in scenarios involving heavy-tailed noise and non-stationary reward structures.

---

2 Preliminaries
Bayesian Optimization (BO). We consider the problem of maximizing an -tpeesuvett--evaluate black-box function μ² over a compact domain A' C R At each iteration, the decision maker selects a point x; E X' and observes noisy reward y(z;) = p² (a.) + +e" (æ;). where e* (1r denotes stochastic noise. Since querying the function is costly, the goal is to identify the maximizer of "² (x) using as few evaluations as possible. BO tackles this problem by maintaining a probabilistic model-called surrogate model over the unknown objective. This surrogate is updated after each evaluation and serves as a cheap proxy for the reward. Based on the surrogate, an acquisition policy is used to determine the next query location. The policy aims to balance exploration (sampling uncertain regions) and exploitation (focusing on areas with high predicted values), thereby efficiently searching for the global optimum. Common acquisition strategies include Expected Improvement (ED, Upper Confidence Bound (UCB), Knowledge Gradient (KG), and Thompson Sampling (TS), which draws& random sample from the posterior and selects the maximizer.
Gaussian Process Surrogate Modeling and Kriging. Standard BO methods adopt a Gaus- sian Process (GP) as the surrogate model. The observed reward is modeled as ((z)) = m(x;) + E(x,) + Ei, Ei G (N(,0 where m(x) = =BT denotes the deterministic mean trend, and & ~ GP(O, pΦ) is a zero-mean stationary GP over X' with squared exponential kernel
Po (0(xx,x') exp (- -i (x(()))) - -))))))).....)))))) Φ ($1,..., ,a),
(xx11, .... ..)))). The
combined term m(x) + (xx) acts as probabilistic surrogate for the true reward function μ (x)). A key advantage of GP models lies in their closed-form posterior inference: given realized histor- ical data {(11.)) (5(x1), {(x,)) at evaluated locations 2i.n (z1..... . Ir,), the posterior distribution of the entire function E(-) remains a GP. This is known as Kriging (or GP regression):
[E(+) ((x1..)) ~ (P())(),
(x(()) = Co(,, xim 200 (Tim Tim (((1))
(2)
(.) = 0² - -o Fim ) (x1ms Fim Co
(3)
Here, the kernel is En(x,, x²) == d²pp (2r, x'). The matrix Eo (2 Tima) Bnxn denotes the covariance matrix with entries [Colis Co (z, 2z), and (2, E gixn is the row vector of covariances between x and each observed input zi-
Value Uncertainty vs. Model Uncertainty Another key strength of GP in BO is their ability to quantify uncertainty through the posterior variance. This enables principled pnplloration-xplotatttii (E&E) trade-offs, as in the UCB strategy, which directly uses the variance guide exploration. However, the uncertainty quantified by GP is inherently limited to value uncertainty- that is, uncertainty about the response value at a given location under fixed reward distribution model. This overlooks a more fundamental source of uncertainty: whether the GP itself is an appropriate surrogate model for the underlying reward. We refer to this model uncertainty, which captures the decision maker's 's uncertainty belief about the type or complexity of the true reward distribution. Consequently, standard GP-based BO requires strong assumptions for convergence, and GPs fail capture complex reward models, such as those that are non-stationary or contaminated with heavy-tailed noises.
3 GP Surrogate Modeling
In this section, develop novel surrogate model called the (Gaussian--roeeee (oc-GP), formally referred to as the sequential spatial Dirichlet Process mixture with a Gaussian Process baseline. The observed reward is modeled
v(x)) m(x:)) + E(x:) + +G, N(O,
E(x)) Ind G.y.
(4)
where the deterministic mean term m(::) is the same classic GP model and the stochastic process Ç A [[(x) E R explore the space of reward distributions, we do not fix the distribution {G. x E X) as a GP. Instead, assume that the distribution (G, : x E X} is itself random and follows sequential Spatial Dirichlet Process (SDP) prior, which places a prior over the space of distributions:
X' follows distribution {G. x E X). To capture model uncertainty and
{G2 : x X} SDP(pGo).
(5)
3

---

Therefore, each reward g(24)) is generated via the following hierarchical process: (i) the nature draws a stochastic process {G, x E } from the distribution space under SDP prior. (ii) in the i-th iteration, after determining the location z; to evaluate, sample {(x;) is generated from distribution Gz.-
The SDP(>Go) is characterized by two key quantities: a scalar precision parameter V > 0, and baseline distribution Gg. In this work, we specify a stationary Gaussian Process (P o² ( +)) over X' as the baseline distribution. Specifically, a distribution (or stochastic process) arising from SDP(vGa) is almost surely discrete and admits the representation
8
G
(x) Vr E X,
(6)
where each surface ς() A (x) : x E } is a sample path independently drawn from the baseline GP(O, o² :)) and the weights {un ) admits the traditional "stick breaking" construction of
V.I (1-111),,, V,), V. Beta(1, v). Notably, our approach directly models the distribution of the observed reward y(r), rather than jr" (1)). this context, the additive noise term 6 72) in model (4) is not intended to impose Gaussian assumption on the true observation noise. Instead, it solely introduced for modeling purposes to mix with the discrete-distributed {(z) and produce a continuous reward distribution.
Dirichlet process, i.e..u; V1,
As defined in (6) each realized distribution {Gz }3 from the SDP is a discrete measure over an infinite collection of surfaces ( At any location 24, there a positive probability that ((x:) <(1) (x;) for some I, meaning that a draw {(x+) ~ Ga, can be realized on any of the surfaces in the collection. To identify which surface x; lies on, we introduce a latent variable 21:1 = { -- such that 2; I if {(x:) = g(9) (ara) and thus g(=:) is the surface on which observation is realized. Note that for any surface g(i) on which the observation at 2; is not realized, the corresponding value (ax)) remains latent and must also be inferred. As illustrated in Figure 1 solid dots (e.g.. g(2) (xs)) indicate that the observation at Py is realized on surface g(2), while hollow dots (e.g.. (xx)) indicate that the observation at æ3 is not realized on surface (()), Since multiple observations may be realized on the same surface, the number of realized surfaces, denoted by Kn. typically grows slowly with n. Let fi. (5("),.. ...... ((K)), denote the collection of realized surfaces up to iteration n, and let n, denote the number of locations within {Ii," , Fn) that are realized surface g()) ie., n = # (1: : = j}. j = 1, 1,.... .K,
It is important to note that the SDP was initially introduced in the spatial statistics and geostatistics literature [Gelfand et al., 2005 Quintana et al., 2022]. Our oc-GP model incorporates two key modifications to adapt SDP for the sequential nature of BO. First, instead of assuming fixed set of locations, we allow observations to be collected sequentially at arbitrary locations. Second, unlike the original SDP, where observations across all locations in each replication are drawn from the same surface, our model permits each observation to be realized on potentially different surface, enabling greater ficxibility.
Model Uncertainty Quantification It is important to understand the two quantities that characterize the SDP: the baseline distribution Go and the concentration parameter v. For any measurable set B, if G ~ SDP(vGo). then B[G (B)] = Go B)), meaning that Go serves as the mean measure. The parameter y can be interpreted as the "variance" in the distribution space, controlling the variability of G around Go: Var(G(B)) = Go(B)( GG(()) In practice, updating the posterior of i with data allows dynamic quantification of model uncertainty: the higher the 1/ the more confident we are that the true reward distribution follows Go- In contrast, a small implies significant model uncertainty, in which case the model relies primarily on empirical distributions (detailed in the next section). Notably, although the baseline Go is stationary GP, a sample path drawn from the oc-GP can be non-stationary and exhibit different smoothness. This highlights the enhanced modeling flexibility of the cp-GP surrogate.
1+v
Full Bayesian Treatment of Hyperparameters Following the seminal work Snoek et al. 2012
we adopt a fully Bayesian approach for the hyperparameters θ {3, v, o. Φ} (OIT ( where the first-layer parameters are (1) [B, ) and the second-layer layer parameters are (())

---

{(x)
exploring distribution
((3)
exploiting the empirical distribution
(x))
(
((1)
Noww
Figure I: Illustration of the proposed oo-GP model as mixture over infinitely many GP surfaces. Each observation may be realized any surface-sof solid dots indicate assignments the correspond- ing surface, while hollow dots represent latent observations not realized on that surface. The red dot denotes new input location Jnew. which may either be assigned existing surface initiate new one drawn from the base measure.
{v, " Φ). Instead of relying on frequentist estimators such as MLE, we place prior distributions on all components of θ and update them via posterior inference. Details of the prior specifications deferred to the Appendix.
Oo Thompson Sampling: E&E in Distributional Space
Although the surrogate modeling in the previous section is performed the noisy observed reward
y(x), the goal in BO is to maximize the expected reward 1u" (x:) == Ely(z)]. The corresponding
Thompson Sampling (TS) acquisition policy proceeds by drawing sample from the posterior
distribution of μ² (x) given data Hn ((1)) ... (In, ((x))), and selecting its maximizer the next query point, i.e.
Ja+1 arg max fi" (x), ft" p(p" Hn).
#EX
In our hierarchical Bayesian model, at the (n + 1)-th step, for any unobserved location In+1 E X, the posterior distribution μ² (2n+1) H. is implicitly induced by the joint posterior over latent components O' (g(#n+1) (Ix+1), ((1),, where g(+n+1) denotes the surface which Ex+1 is realized and (!1) = {3, 7... Specifically, the posterior distribution of y( is given by (see Appendix for proof):
f(y(x=-1) Hn) = / [1((1411) 00) /(0') HH.dd'
- -/1 N(xT4113 (
(Za4z), ((((a++))(xxt))) (((2) Z1m)) Eir, Zi:n Hn)
)(0()H))
(glen+1)(ant))) (d(+))d(0E, Eisns 21.n)
(8)
where f(-) denotes the probability density. According to this decomposition, given O', the distribution of (( Gaussian: y(#n+1) (O' ~ NN B+ c(zn+1) (x (In41), 72). Therefore, the (conditional) expected reward is 4 (#n+1))@' x__1 + (==mt)) (Zn+1).
Thompson Sampling Implementation. Therefore, the Thompson Sampling acquisition policy, as defined in Eq. is implemented as follows:
(i) Draw a posterior sample é' f(O') (H,)) and (ii) Select the next location to evaluate:
Zn-1 arg max ji" (x) O' arg max x. 3 ((
(9)
ZE

---

where the quantities with hat (e.g., B, Kn; ( denote posterior samples. The core challenge lies in drawing posterior sample from s(e') Hn), particularly in sampling path ( (5(#n-1)
a E } from the posterior distribution. As shown Eq. (8), we can achieve this by (i) first sampling a Ô Ei:: &1mm from the joint posterior f(O, Si:: 21:n H4,) using a Gibbs sampler (see Appendix for details). (ii) Next, given Ô, fim. &1:n. we sample path from the conditional posterior É1:..
distribution (g((m+1)())) (I)), 2} , 21:n- According to the Chinese restaurant process (CRP), a constructive representation of the Dirichlet process, new upcoming data point either lies on one of the previously realized surfaces (5(0 (+) Rr, initiates new surface drawn from the baseline distribution Go (as shown in the red dots in Figure Based on this, we derive the following conditional distribution (see Appendix for proof):
Kriging g())
K
f(g(t41)()) (66)))(())))) 16(2), E1.. 2mm) Plo GO
(10)
Exploration
Exploitation
where p!(0) & D+n and p! A, Each term GP(ph)) ())) corresponds to performing
(
D4n Kriging on an existing surface g.)(.), using past values ((,) (x1m.) (Z1),, (x)(x,) (xx))
realized on that surface. This follows the same calculation in Eq. with ((Tis) replaced by
(z)m) Efficient sampling from GP posterior GP (px (-), 0.. (-)). (). as required here, has been
widely explored in recent literature; see Wilson et al. [2020] Lin et al. [2023] Zhou 2025 The
pseudo code of our proposed co-GP-TS is shown in Al Algorith
Exploration and Exploitation in Distributional Space. As illustrated in Figure 1 Eq. 10) be viewed as structured tradc-off between exploration and exploitation in the distributional space:
D+n the new input In+1 assigned an existing surface (-). In this case, the model performs Kriging inference using observations previously associated with that surface. This corresponds to exploiting empirical knowledge, resulting in conservative updates confined to the empirical distribution. Notably, the assign- ment probability proportional to the number of observations ńj already associated with surface j. The more observations are assigned to surface, the more likely it will be reused.
Exploitation: With probability P!() f2
Exploration:
With probability p! = D4nn new surface is instantiated from the base GP prior Go. Since no observations have been made on this surface, represents functional- level exploration-exxttee expanding the surrogate model by admitting novel structures beyond those already observed.
As the number of observations increases, the exploration weight p.0 naturally diminishes, gradually shifting focus from exploration toward exploitation of well-supported surfaces. This hierarchical Bayesian mechanism thus equips Thompson Sampling with principled way to adaptively balance exploration of new functional hypotheses and exploitation of learned structures, effectively broadening the surrogate model's support within the distribution space.
Algorithm 1 Thompson Sampling with cc-GP Surrogate Model (oo-GP-TS)
Input: Ho. the total number of iterations N.
for to N do
Step 1: Sample {Ô, E1..) from the posterior f(O, E1.n. H,,) using Gibbs sampling (see the
Appendix for details).
Step 2: Sample surface g(#m41) from 10
Step 3: Evaluate the reward at the next candidate location Fn+1 = arg max T
(lzn+1) (x). Observe the response y(*,++1) and update Hn41 = H. U (#n+1. Bn+1)
Step 4:
Continue to the next iteration 1.
end for

---

5 Theoretical Analysis: Efficient Exploration in the Distributional Space
In this section, we show that by exploring the space of reward distributions, the proposed oc-GP model can approximate a wide range of true reward models and achieve a near-minimaxx-opimall rate. Since the noisy reward is a stochastic process over X' it is standard to characterize it in terms of its finite- dimensional distributions. Specifically, for any finite set of input locations D1:D { ... .DD C X' with D E N*, we denote the corresponding D D-dimensional joint density of the true reward values by ( #1:D)- Let k- = (k1,....) kD) E No be multi-index. Define the corresponding mixed partial derivative operator of a function fyl. , MDD as f(k) := t f/0y]
Oyfr For any a 0, λo 2 0, and any non-negative function L RD Rzo. we define the locally Hölder class Ca.L.do (BP) as the set of all functions f :R R that satisfy:(i) f(k) is finite for all multi- indices &s such that |k] == Ebn la & [a]; (ii) for every 2; y E RR, and such that |k| = [ar] ((k) + (x) S L(x) edollvil" ||y||--Lo]_
Assumption The true density f (+(ma)) E Co for some a 1
> 0. Ao 2 0 and a non-
negative function on IR and satisfy (y-ro))))))))
EP ki
< oc for any k E No
("
satisfying Σb K2 S [a] and By T(WLD. there are positive constant 01 02 03 such that
oo for some > 0. Additionally,
(vl S a1exp(-a221 |2 ||v/l > az.
(1I)
Assumption T Timposes mild regularity conditions on the true reward distribution. Apart from the tail condition in I the remaining smoothness assumptions relatively weak. This assumption is satisfied by broad class of distributions, including Weibull (with shape k > 1), Gaussian, Laplace, Gamma, and exponential distributions, as well as their finite mixtures of the form Σ wi(x) th (0)), where each 4/ belongs to one of the aforementioned distribution families.
Theorem (Posterior Convergence of cc-GP Model) Let (" æI:D) be the true reward distri- bution satisfying Assumption 7 IT be the oc-GP prior as defined in Eq. (4)-6)) and let IT.( FIDD) denote the posterior distribution based on n i.idd evaluations locations DA:D. Then there exists sequence = n aa(2a- D) (log n)' for some constant t > 0, such that for any M > O,
lim II, (If llf f2 Mc.1 (IDD) +0 almost surely under f" 1L-000
This result demonstrates that by efficiently exploring the distribution space, the posterior distribution of the oc-GP model can contract around a broad class of true reward distributions at near-minimax- optimal rate in L1 distance. In contrast to classical GP regression, which requires strictly stronger functional class assumptions [Kanagawa et al. 2018 Theorem 5. than our method and assumes Gaussian noise, our framework allows much broader modeling flexibility.
Empirical Evaluation
We evaluate our method ten benchmark tasks, including six synthetic functions, three real-world problems, and one LLM prompt optimization task. We particularly focus on BO tasks characterized by non-stationary, complex reward landscapes and heavy-tailed observation noise. Extensive results and ablations are provided in the Appendix.
Synthetic Benchmarks. We consider three popular synthetic test functions: Ackley, Rosenbrock, and StybTang [uu al. 2024]. To introduce more challenging scenarios, we consider non-stationary and heavy-tailed variants of these functions. In the heavy-tailed (HT) cases, all the functions are noises. In the non-stationary (NS) setting, the base test functions are modulated by a rigonometric-exponeee term of the form fNs(x) = (1 + a sin(z))" f(x), which introduces non-stationarity across the domain.
corrupted by
Real-world Benchmarks. We consider three real-world benchmarks.
7

---

m- -P-TSS
GP-TS
GR-UCB
GP-EI
GP-KG
76
-22
60-
-35
26-
18-
16:
ASMeysS
Nosemb
Stabiing
76-
-29
A
52-
-22
50
-10-
f
-25
-12
36-
-30
Figure 2: Results of synthetic benchmarks. The suffix HT stands for the function with heavy-tailed noises and NS stands for the non-stationary scenarios.
HroBerch
NASBunch
12
70-
7E-
+
50
Figure 3: Results of real-world benchmarks.
Portfolio CCakmak al.) 20200 is benchmark of tuning the hyperparameters of trading strategy to maximize returns. The stock data with heavy-tailed nature is generated from realistic financial simulator, CVXPortfolio.
HPOBench (Eggensperger et al. 2021] provides standard hyperparameter tuning tasks for
ML models, and we use the MLP task in the HPOBench in our experiment.
NASBench201 [Dong and Yang 2020 is neural network search task on CIFARI00.
The search space of hyperparameters and model architecture is considered non-stationary. Therefore, we use these tasks for our evaluation of real-world non non-stationary cases.
Prompt optimization for language understanding. We conduct prefix prompt optimization for seven language understanding datasets, including sentiment classification (SST-2 [Socher et al. 2013]), SST-5 [Socher et al.) 2013), MR (Pang and Lee| 2005), CR (Hu and Liu 2004)). ), topic classification (AG's News Zhang et al., 2015), PRECI and Tice (0000) and subjectivity classification (Subj [Pang and Leel 2004)). We use the Alpaca-7B model Taori et al. 2023) as frozen language model, and optimize continuous prefix embeddings guide the model toward better task performance. Due to the high dimensions the decision variable, we use Uniform Manifold Approximation and Projection (UMAP) [McInnes et al. 2018 to reduce the dimension.

---

Method
SST-2
CR
MR
SST-5
AG's News
TREC
Subj
Avg.
GP-TS
93.87
91.44
89.85
49.91
72.81
45.29
65.18
72.61
GP-UCB
92.68
90.20
89.98
49.86
71.76
43.27
62.70
71.49
GP-EI
91.82
89.75
87.69
48.26
60.83
42.09
59.70
68.59
GP-KG
90.05
88.38
85.90
42.89
45.98
36.20
49.75
62.74
co-GP-TS
96.57
92.52
91.51
52.58
75.34
46.23
68.55
74.76
Table I: Performance comparison on seven language understanding datasets.
Baselines. We compare our methods with the following baselines based on GP surrogate model.
GP-TS [Chowdhury and Gopalan 2017]: Following the TS policy defined in Eq. 77. except that the posterior is constructed under a standard GP model for p (ar). GP-UCB [Srinivas et al. 2009 : Selects
the location In+1 arg c X Mhn (a:) + 3 o..(x), where 3,, is time-dependent exploration
parameter. GP-EI Ament et al. 2023 : Selects 2n+1 arg max E |max(0, μ p²(r) y
where the expectation is taken under the posterior distribution of (x)). GP-KG [Wu and Frazier 2016): Selects the point whose evaluation is expected most improve the posterior estimate of the maximum value of μ (z). Non-stationary GP-UCB/TS/EI/GG: In non-stationary tasks and the Prompt optimization task, all baseline methods adopt input warping techniques in [Snoek et (2014) to mitigate GP misspecification. Truncated-GP-UCC In heavy-tailed noise tasks, GP-UCB adopts the truncation technique Chowdhury and Gopalan 2019].
Performance. We report the final optimization outcome of the synthetic and real-world experiment in Figure 2 and respectively (runtime regret results are provided in the Appendix). The result of each task is reported from 10 repetitive runs with different seeds. In the synthetic experiment, oc-GP consistently outperforms the baselines in heavy-tailes and non- -tn-stationary settings. The GP-TS and GP-UCB have similar performance against each other. The GP-EI performs poorly in both scenarios. The GP-KG has the worst results, and the final performance fluctuates heavily.
In the portfolio task, we report the returns of the strategy. Stock prices often exhibit sharp fluctuations, making portfolio optimization suitable testhed for evaluating performance under heavy-tailed environments. Our method achieves the highest return among others, while the GP-EI has the second-best return. In the HPOBench and the NASBench, the performance gap between our method and baselines is close, but our method has a smaller fluctuation with different seeds, showing better robustness than others.
The language model in the prompt op- timization task is Alphaca-7b. Table T reports the average final accuracy across three independent runs. The proposed oc-GP outperforms all GP- based baselines on average, achiev- ing the highest mean accuracy (74.76), and ranking first on every dataset. Figure 4: Compared to GP-TS and GP-UCB, co-GP offers notable gains on complex tasks such as SST-5 and Subj, where the reward land- scape is highly non-stationary. GP-EI and GP-KG perform significantly worse, consistent with their known sensitivity noisy or irregular reward signals. These results demonstrate the robustness of oo-GP in prompt optimization tasks under distributional uncertainty.
Searched prompls by GPPat accuracy
AG's News Your lask identify the poimrry lopic the article and chouse from World, Sports, Businees and Texch.
7602
Subj
Produce ingut- outzut pairs that Illustrate the subj ectivity of reviews opinlôns.
9660
SST-2
this lask are sentences from movie reviews. The lask to classtt senlence positive or negolive.
0872
Qualitative examples of best searched prompts
7 Discussion
This work introduces the co-GP model and its integration with TS, providing a principled mechanism to automatically balance exploration and exploitation in the space of reward distributions. Empirically, the proposed method demonstrates strong performance in a wide range challenging settings where classical Ga-based BÔ methods often fail. Nonetheless, we do not systematically evaluate the performance oc-GP high-dimensional BO tasks. That said, as shown Eq. 10) and Algorithm approach can be interpreted as finite mixture of traditional GP-TS. This structure is orthogonal to many recent advances in high-dimensional GP-based BO, and hence, those techniques can be readily incorporated into our framework. We leave the exploration of such extensions to future work.

---

References
Peter I Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv: 2018.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Felix Berkenkamp, Andreas Krause, and Angela P Schoellig. Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics. Machine Learning, 112(10):3713- 3747, 2023.
Alan Nawzad Amin, Nate Gruver, Yilun Kuang, Lily Li, Hunter Elliott, Calvin McCarter, Aniruddh Raghu, Peyton Greenside, and Andrew Gordon Wilson. Bayesian optimization of antibodies informed by a generative model of evolving sequences. arXiv preprint arXiv:2412.07763, 2024.
Eric Brochu, Vlad M Cora, and Nando De Freitas. A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv: 1012,2599, 2010.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 321)):22 2014.
Jingyi Wang, Haowei Wang, Cosmin G Petra, and Yuan Chiang. On the convergence of noisy bayesian optimization with expected improvement. arXiv preprint arXiv:2501.09262 2025.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, pages 1022. Omnipress, 2010.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias W Seeger. Information-theoredt
regret bounds for gaussian process optimization in the bandit setting. IEEE transactions information theory, 5855):325--3255, 2012.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pages 844-853, PMLR, 2017.
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur. Gaus- sian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv: /807.02580 2018.
Haoxian Chen and Henry Lam. Pseudo-bayesian optimization. arXiv preprint arXiv:3310009766 2023.
Jasper Snock, Kevin Swersky, Rich Zemel, and Ryan Adams. Input warping for bayesian optimization of non-stationary functions. In International conference on machine learning, pages 1674-1682. PMLR, 2014.
Sayak Ray Chowdhury and Aditya Gopalan. Bayesian optimization under heavy-tailed payoffs. Advances in Neural Information Processing Systems, 32, 2019.
Sait Cakmak, Raul Astudillo Marban, Peter Frazier, and Enlu Zhou. Bayesian optimization of risk measures. Advances in Neural Information Processing Systems, 33:201 20-2014,, 2020.
Antonio Sabbatella, Andrea Ponti, Ilaria Giordani, Antonio Candelieri, and Francesco Archetti. Prompt optimization in large language models. Mathematics, 12(6):929, 2024.
Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric P Xing, and Zhiting Hu. Riprompt: Optimizing discrete text prompts with reinforcement learning. arXiv preprint 2rXiv:2205.12549 2022.
Yucen Lily Li, Tim GJ Rudner, and Andrew Gordon Wilson. A study of bayesian neural network surrogates for bayesian optimization. arXiv preprint arXiv:2305.20026 2023.
Dave Higdon, Jenise Swall, and John Kern. Non-stationary spatial modeling. arXiv preprint arXiv:2212.08043, 2022.
10

---

Matthias Seeger. Gaussian processes for machine learning. International journal of neural systems, 14(02):69-106, 2004.
Sébastien Bubeck, Nicolo Cesa- Desa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Transac- tions on Information Theory, 59(11):711--7717, 2013.
Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed linear bandits. In International Conference on Machine Learning, pages 1642-1650. PMLR, 2016.
George Wynne, Lrançoi-Xavvies Briol, and Mark Girolami. Convergence guarantees for gaussian process means with misspecified likelihoods and smoothness. Journal of Machine Learning Research, 22(1)3): 2021.
Ilija Bogunovic and Andreas Krause. Misspecified gaussian process bandit optimization. Advances in neural information processing systems, 34:3004-3011 2021.
Carl Rasmussen and Zoubin Ghahramani. Infinite mixtures of gaussian process experts. Advances in neural information processing systems, 14, 2001.
Edward Meeds and Simon Osindero. An alternative infinite mixture of gaussian process experts. Advances in neural information processing systems, 18, 2005.
Nicola Bariletto and Nhat Ho. Bayesian nonparametrics meets data-driven distributionally robust optimization. arXiv preprint arXiv:2401.15771, 2024.
Alan E Gelfand, Athanasios Kottas, and Steven MacEachern. Bayesian nonparametric spatial modeling with dirichlet process mixing. Journal of the American Statistical Association, 100(471): 1021-1035, 2005.
Fernando A Quintana, Peter Müller, Alejandro Jara, and Steven N MacEachern. The dependent dirichlet process and related models. Statistical Science, 37(1):24-444 2022.
James Wilson, Viacheslav Borovitskiy, Alexander Terenin. Peter Mostowsky, and Mare Deisenroth. Efficiently sampling functions from gaussian process posteriors. In International Conference on Machine Learning, pages 10292-10302. PMLR, 2020.
Jihao Andreas Lin, Javier Antorán, Shreyas Padhy, David Janz, José Miguel Hernández-Lobato and Alexander Terenin. Sampling from gaussian process posteriors using stochastic gradient descent. Advances in Neural Information Processing Systems, 36:36886-3611 2023.
Zhihao Zhou. Accelerating posterior sampling for scalable gaussian process model. arXiv preprint arXiv:2505.02000 02000. 2025.
Zhitong Xu, Haitao Wang, Jeff Phillips, and Shandian Zhe. Standard gaussian process all you need for high-dimensional bayesian optimization. In The Thirteenth International Conference on Learning Representations, 2024.
Katharina Eggensperger, Philipp Müller, Neeratyoy Mallik, Matthias Feurer, René Sass, Aaron Klein, Noor Awad, Marius Lindauer, and Frank Hutter. Hpobench: A collection of reproducible multi-fidelity benchmark problems for hpo. arXiv preprint (00iv:21090066 2021.
Xuanyi Dong and Yi Yang. Nas-bench-20 201: Extending the scope of reproducible neural architecture search. arXiv preprint wrXiv:2001.0mm 000326, 2020.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference empirical methods in natural language processing, pages 1631-1642, 2013.
Bo Pang and Lillian Lee. Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. arXiv preprint cs/0506075, 2005.
Minqing Hu and Bing Liu. Mining and summarizing customer reviews. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 168-177, 2004.
11

---

Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28, 2015.
Ellen M Voorhees and Dawn Tice. Building question answering test collection. Proceedings of the 23rd annual international ACM SIGIR conference Research and development in information retrieval, pages 200-207, 2000.
Bo Pang and Lillian Lee. sentimental education: Sentiment analysis using subjectivity summariza- tion based minimum cuts. arXiv preprint cs/0409058, 2004.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. Stanford alpaca: An instruction-folloiin llama model, 2023.
Leland McInnes. John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv: 1802.03422 2018.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995. 2009.
Sebastian Ament, Samuel Daulton, David Eriksson, Maximilian Balandat, and Eytan Bakshy. Unex- pected improvements expected improvement for bayesian optimization. Advances in Neural Information Processing Systems, 36:20577-20612, 2023.
Jian Wu and Peter Frazier. The parallel knowledge gradient method for batch bayesian optimization. Advances in neural information processing systems, 29, 2016.
Alan Gelfand and Adrian FM Smith. Sampling-based approaches to calculating marginal densities. Journal of the American statistical association, 85(410):398 409, 1990.
David Blackwell and James B MacQueen. Ferguson distributions via polya um schemes. The annals of statistics, 355-35,,,,, 1973.
Subhashis Ghosal and Aad van der Vaart. Posterior convergence rates of dirichlet mixtures at smooth densities. The Annals of Statistics, 35(2):697-723, 2007.
Weining Shen, Surya T Tokdar, and Subhashis Ghosal. Adaptive bayesian multivariate density estimation with dirichlet mixtures, Biometrika, 100(3):623-666 2013.
12

---

A Proofs
A.1
Proof of Eq. (8) and Eq. (10)
We adopt the bracket notation system used in Gelfand and Smith (1990], where [Y [X] denotes the conditional density of Y given X, and [Y] denotes the marginal density of Y.
The predictive reward distribution for any unexplored solution Ex+1 is given by
/ [y( [v(=n+))(( glzm +1) () (In+1)) ()(1, ((( gg (1n
[y(2n+1))
A: Gaussian
B+C
=/ [((nn1))l0 g(en (wn+ () 1) ( (d1::)) Zi:no (
(12)
A: Gaussian
(1.mm(011m) Z1:n|Ha
Notice that, when performing computations involving stochastic processes over X, in practice, we are working with their fimite-dimensional distributions, i.e., the joint distribution over finite subset of X'. Therefore, the term fi.,, becomes f1:n(Z1.0 (21:.) = (g(0 hi=1... j=1.-..KK, which represents the Kn, X n table of values on the realized surfaces corresponding to the observed locations Ti:n-
In the first line of Eq. 12). conditioned the surface
and first-layer hy- is (I
per parameter ((1) (B, the distribution ()(
((*n 1) (In++)), 72), according to Eq. (4). The remaining Term "B+C" [x,] In the second line of Eq. (12). the posterior distribution [((1))((=x++) H.n]. i.c. the Term "B+C". is decomposed into Term B and Term C. Term C represents the posterior distribution of the hyperparameters and realized surfaces, which requires inference through Gibbs sampling. The proof of Eq. (8) is now complete.
g(*x++)
We next proceed to establish Eq. (10) The Term B represents the prediction of the new surface g(#n+1) based on the previously realized surfaces &1.. (g( ((Kw)) and their associated assignment labels Z1:n- Conditioned on &1.m = (g(1), ..... ( and 21:n- and marginalizing out the random measure (Gz
X). the distribution of the latent surface index 2n+1 follows the um scheme of the Dirichlet process [Blackwell and MacQueen 1973]. Specifically, the new point either reuses one the existing surfaces (solid lines Figure or initiates a new surface drawn from the base
measure Go = GP(O,, o² 00 (.))) (dashed lines in Figure I.. Formally:
(3
E 1:m Z1:m: (2)
Um scheme
[e( Ei:m, Zim, (2)) [G]
(13)
Gu
Σ
nj
8g(n).
V n+n
v v n
where ny denotes the number of data points currently assigned to surface gbi) The more points are assigned to surface, the more likely it to be reused. Then, after determining which surface ((#n+1) the new location Fn+1 will be realized on, we perform Kriging on that surface to predict ((fn11)(x using previously realized values EI. (11.)). Therefore, the Term B can be decomposed as
()) ( E1s (x1m,) 2im ((2)
= g(tn (1) (In+ 1) (In 1), Zi:n, (22) [ Eimn (In41 ) (1 (
(14)
Step (a): Umn scheme
Step (b): kriging
where the urn scheme term follows 13 by evaluating g(an and t at location In+1. The Kriging
term is given by (recall that Êi.. [ [ k
(e()) (# ) EIsh (#1:)) ((2) ~ GP( (xn+1), (z
(15)
kriging
13

---

where ( (xn+1) = Eo(En+1: Fi. Eo(#1 Fimm and (xx+1) is given by Eq. 33)
Therefore, combing Eq. (14) and Eq. 15 have
Kriging on e
(g((nta) ()| 6(2), Eim, 8im)
Pi Go
p
(),
(16)
Exploration
Exploiation
which concludes the proof.
A.2 Proof of Theorem 1
For any finite set input locations 21:D = ......., [ C X' with D E No, we consider the corresponding D D-dimensional joint density of the true reward values by f* F1.D).
Notice that, focusing on fixed Fi.D. the oc-GP model can be viewed as DP location mixture of normals prior ТI, which is the distribution of random distribution &D = db - Pa or the normal density with mean zero and covariance baseline distribution G, which is D-dimension Gaussian distribution, with squared exponential
DPG Dirichlet process with
kernel (= x') = exp Ed k= 1 (x - x/((1)2) (i.e. the kernel of baseline co-GP) and zero
mean. In our model, we assume the covariance matrix D E IR DxD to be diagonal with independent gwerre-gamma priors on each variance component:
0
0
12
0
E
D
with 7² ~ Inv-Gamma(ar,bb by) independently for i 1..... D.
Let |G| = G(RPP and = G/[G). Let eig, be the j-th eigenvalue. We first present the following lemma.
A.2.1
Lemma
Lemma
There exist positive constants a1 a1-0-.
1- 1-G([-2,x10 a₁ exp(- exp(-az201)
(17)
and
P(E: eig (E 2 x) < as exep((a5r00)
(18)
for sufficiently large x > 0, and
P(Σ: : eig ( < x)) S a7
(19)
for sufficiently small x > O. Moreover, there exist ag such that for any < 81 S .... sp and t 10,
:(::;; eig, ei < (1, ... ags exp(-01288).
(20)
Proof: Equation
17 follows from the exponential tail behavior of the Gaussian base measure G. To
prove Equation
18 recall that Σ = diag(r? .7, and hence (2-=)=1) max,
-
Since
7, ~ Inv- wwn-GGmma(o... 6,), we use the left-tail bound for riverse-gammn random variables:
PP ( !) C1 exp(-C2ar),
-
Applying a union bound over 1,... D, obtain:
P (eign(( 2 x) < D- C1 exp(-C2x) as expp(_ax2")
14

---

For Equation
19
we use the right-tail tail of the inverse-gant gamma distribution:
1
P ( ( )
S x S Cz as - 0*
7
Therefore,
1 < z for some i) D C3x"t ayx
(eig:
E (2-1)
P
Finally, for the lower bound in Equation 20 note that due to the independence of r/², the eigenvalues of E-1 also independent. Thus, for each j. we consider the event:
cig, (x E [sg, 8 +1+10 t)}.
which translates to r3 (5(1+t))
The inverse-gant -arsm- distribution has continuous, strictly positive density compact intervals bounded away from zero. Therefore, for each
1 E m
P
[sg 1 (1++
cj8j
for some constants Cj. b, > Multiplying across j 1,..., D, we get:
IP (eig, (Σ-1) (5( () Vj) ags1 y exp(-a128D);
where we used the fact that inverse-gamen densities decay exponentially on the left (i.c., for small TJ), which leads to the exp(-A128) term.
A.2.2
Lemma 2
Lemma
Ghosal and van der Vaart [2007]]
lim 11, (Lf || f" > ME, } LI.D) + 0 almost surely under f
n-000
whenever there exist positive constants C1, C22 Cas Ca. a sequence of positive numbers (Zn)n2) with &n S Cn and limm-+oc nē? co, and a sequence of compact subsets (Fr)n21 of probability densities satisfying
log, NN Fn, S cine,
(21)
((F))) S C3e (e2+1)mE
(22)
[T K(F (n) S 22, cee canec, then the posterior contracts at the rate en around fo in the metric p.
(23)
Here, K(J", ,e) is the Kullback-Leine ball around f of size En defined
K(S", .)) r: (:: 1 log (f) < |Mlog"
(f) <<
(en, Fr, p) is the e, -ooerrng number of Fn under metric
A.2.3 Proof of Theorem
Now prove Theorem by verifying conditions sieve
21
22 and 23 respectively. We construct
DPc E5 w)dg,(n () (-a, a) for j < J; | 5 M
M,,e) & IDPaND:
Σn>, Wj < c eig, (E) of
Vj 1, .....
Then, according to Shen et al. 2013 Theorem 5] and Lemma conditions and 22 hold for
ne. en = (logn)' En n-y (logn)* '0 J Lo M a² when fixing 7 E (0, 1/2) and
t> to
D+1 2
15

---

To verify condition 23 we follow the prior thickness argument in Shen et al. [013]] Theorem 4]. Under Assumption I the true density f belongs to locally Hölder smooth class with exponential tail decay. Theorem guarantees that there exists discrete mixture density præ: such that both the Kullback-Leibler divergence and its second moment between f* and PF,E are bounded by Ce², for some constant C' O. Moreover, the Dirichlet process prior assigns exponentially non-negligible mass to such mixtures via partitioning and stick- breaking construction. The prior on the covariance matrix E, as discussed in Lemma [ also places sufficient mass on the eigenvalue shell corresponding the mixture approximation. Combining these results, let 2 n-aa/2a+ (log n)), for any
D(1+1/>41/a)+1 according Shen et al. 2013 Theorem 4], we obtain 2+
t tz
II mL KI((()
Vary. log
Cse -ann
for some constants c22 > 0, thus verifying condition 23 Finally, according to Lemma 2 the proof is concluded.
B
Gibbs Sampling Algorithm
B.1 Prior Specification
We adopt a Sally-Baysiian treatment for hyperparameters @ = (B,
,6 = (e(1) e
where the fist-layer parameters @(") = {3,T) and the second-layed parameters ( = (v, ,6) given by
Specifically, the priors hyperparameters
8,7² N (Po. Eg) x IGamma(ar,br),
(24)
a² IGamma(aa: ba),
(25)
Φ ~ ((0,bol*)) bol"),
(26)
V Gammalay, by),
(27)
where B has Gaussian prior, 72 and o² have inverse Gamma prior, á has uniform prior (0, by] and y has a Gamma prior.
Selection of Hyperparameters in the Prior set ar 0g 2 and thus the mean of the prior is b, and b,- Therefore, prior information about the variance (for example, rough estimation of the variance and the mean) can be incorporated.
d: e has uniform prior on (0, bg). If the distance between two locations 21 and 22, ||ar x22 a their correlation will decrease to less than 0.05. Therefore, set by d max|| 22ll with small d (e.g. 0.01).
So and Σg: we set 8o = [1, .1, E IRd and set Σg = Idxd-
B.2 Gibbs Sampling
To perform posterior inference under our fully-Ban Bayysian model, employ the Gibbs sampling algorithm. Gibbs sampling is Markov Chain Monte Carlo (MCMC) method designed to sample from complex joint posterior distribution by iteratively sampling from each of its full conditional distributions. This approach is particularly well-suited for our hierarchical oc-GP model, where the full conditionals of most parameters have closed-form expressions To ensure computational tractability, we adopt a truncation approximation to the stick breaking representation of the Dirichlet process. Specifically, fix the number of mixture components finite value L.
be easily computed.
16

---

Algorithm 2 Gibbs Sampling for (θ, f1m (Fin))
1: Input: Initialization value of (O, Eimm (1imm))))) data Hy, MCMC iteration number B, truncation
number L
2: Output: Samples of [e, E1:m (1Tmm) H.]] including Eisn (F1m)) (Wir..., wL), (Z1.... 2n). and
θ = 9, T,, Φ).
3: for each iteration b 1..... do
4: Step 1: Sampling E1n (Z1m):
5: for each / = L..... do
6:
Compute (= diag("(s ((x==)))))
7:
Sample (x(m)))) from the distribution (Z1:m) N (3AAT (J(FIm) - =T ,A))
where A' -2- +r +r-2z") and 2o (²
8:
end for
9:
Step 2: Sampling Weights (w (Wi,...,WL)? WL):
10:
for each | 1,.... do
11:
Draw Vi ~ Beta(1 + M + "j=++1 Mj). where M, = #(i:2; 2;=;2,1 =
12:
Compute weights by w1 = V1, wy = (1 - vi)(1 - V2) -V. wy = 1
1=1 W/ end for
13:
14:
Step 3: Sampling Latent Labels (21,....; 2n): for each observation r; do
15:
Sample 2; from {I,...; L} with probabilities proportional to
P(z: j) x wy exp {
1
27 (y(z²) x {xx))
17:
end for
18:
Step 4: Sampling Hlype-Paarameter θ = 113, 1,, o²)
19:
(4a) Sampling Gamma (a,
1,b, log(wl))
20:
(4b) Sampling 3:
~~ NN -3)
-1
where 23
Eg + T 2x N1m
. Σg
Exg 30 r - 2X "IIn(( and 7(x.))
((x;) - c(ei) (x:). (4c) Sampling 2
21:
T² ~ InvGamma(d", b7)
where a" = a
a 21
6 = b, + 2 Σ (f(x;) - x 3)
22:
(4d) Sampling 22:
o² IGamma (6 8%5)
where - 2
b br + 3 E (Ei( Psb - (2 Fiam (((1))))
23:
(4e) Sampling Φz o is sampled from grid of values (0), 02, ......, (bM) with probabilities proportional to
P(dm) &
exp
Σ (E((21))))
pon (Zims Fisn EI (T1mL)
[det(po... (I IImm) )))
20
24: end for
17

---

C Experimental Details, More Experiment Results and Ablations
C.1 More Experiment Results
In this subsection, we provide additional plots that visualize the evolution of instant regret over time for benchmark tasks, where instant regret is defined as the gap between the reward obtained and the global optimum. These plots offer clearer comparison of the performance dynamics across different algorithms.
C.1.1 Synthetic Benchmarks
Ackley-HT
Rosenbrock-HHT
Styblang-HI
80
-20
-10
-40
-15
Roward
Roward
-60
-25
-GP-TS
T5
-G-TS
..GTTS
UCB
UC3
-35
20
00
100
100
Stey
Ackley NS
Rosenbrock-N5
Stybllang NS
-20
50
-10
-40
15
Roward
Rewerd
-60
-25
-25
GG-75
GPP
H-GITS
-30
UCB
UCB
-75
-120
20
60
80
100
20
40
60
80
100
Stop
Stop
Figure 5: Cumulative regret in synthetic benchmarks
Figure shows the evolution of instant regret over time across various synthetic benchmark functions. The compared methods-TS -T, UCB, EI, and KG-ar are all implemented using standard Gaussian Process surrogate models. Overall, we observe that oo-GP-TS achieves the best performance in settings with nonstationary or heavy-tailed reward structures, significantly outperforming classical GP-based approaches. In the early iterations (e.g., the first 10 steps), the performance oo-GP-TS is initially lower due to its stronger exploration behavior. However, it quickly adapts and achieves lower regret as the optimization progresses, demonstrating its ability to efficiently learn complex reward landscapes.
C.1.2 Real-world Benchmark
Tigurr/sshow the runtime performance (instant regret) on three real-world benchmarks: Portfolio, HPOBench, and NASBench. Across all tasks, NBO consistently outperforms other methods, achiev- ing faster convergence and lower regret. the Portfolio task, NBO quickly surpasses baselines; in HPOBench and NASBench, it maintains clear lead throughout the optimization process. These results highlight NBO's s strong generalization ability and its effectiveness complex, real-world settings.
C.2 More Experiment Details
In this subsection, we present more experiment details, including the synthetic benchmarks, real- world benchmarks and the prompt optimization problem.
18

---

Portfolio
HPObench
NASBench
70
10.0
7.5
60
Roward
50
Roward
-55
25
-00
0.0
DIGPTT
=PGPTT
e-EPTS
UCB
30
UCB
UCB
5.0
-7.5
90
20
46
80
100
20
40
60
80
100
40
60
100
Step
Step
Step
Figure 6: Cumulative regret in real-world benchmarks
C.2.1 Benchmark Function Definitions
We consider three popular synthetic test functions commonly used global optimization benchmarks: the Ackley function, the Rosenbrock function, and the Styblinski-Tang (StybTang) function. These functions are defined over d-dimensional input vector (#1,..., Td) RR
Ackley Function.
d
fAckley(Z) aa exp
b
Σ x
exp
7
Σ
cos(ez:) + a + exp(1), 1=1
with default parameters 20, b = 0.2, and c 2n.
Rosenbrock Function.
d-1
R (x:) Σ
10011:11-55 (x: 1)²]
Styblinski-Tang Function.
1 2
fsr(E)
Σ i=1
[1) 16x7 + 5.mz)
To introduce more challenging and realistic scenarios, further consider the following two variants of these base functions: Heavy-tailed (HT) variant: We add random noise to the function outputs, where the noise is sampled from a Weibull distribution. Non-stationary (NS) variant: We modulate each base function by a apatiall--varying multiplicative factor:
fNs(2) = (1 + a sin(z)e") f(x).
where 0 controls the magnitude of non-stationarity. This formulation introduces location- dependent amplitude variations, breaking the stationarity assumption often made kernel-based methods.
C.2.2 Real-world Benchmark Details
Portfolio [Cakmak et al. 2020 We tune three hyperparameters of a trading strategy: risk aversion [0.1, 1000], trade aversion 55, 8). and holding cost multiplier [0.1, 100). The environment includes two random variables: bid-ask spread 44[10-4 10 and borrowing cost ~ 24(10++ 10-3). The objective is to maximize the VaRa. of the average daily return over four years. To reduce cost, build GP surrogate model using 3000 evaluations selected via Sobol sampling, as in Cakmak et al.) 2020
HPOBench Eggensperger et al. 2021 provides standard hyperparameter tuning tasks for MI.
models, and we use the MLP task in the HPOBench in experiment.
19

---

NASBench201 [Dong and Yang 2020 is neural network search task on CIFAR-100, Each architecture is represented by a 4-node directed acyclic graph with operations selected from fixed set of 5 choices (e.g., conv, skip, zero). The total search space includes 15,625 architectures. Each architecture has been trained multiple times with fixed hyperparameters and its validation/test accuracy and training cost are pre-recorded. For our experiments, we query the test accuracy of selected architecture based on its index as the ground-trum touunhttruth objective.
C.2.3 Prompt Optimization Experiment Details
We conduct prefix prompt optimization experiments seven language understanding datasets. All experiments are performed using the Alpaca-7B model (Taori et al., 2023], which remains frozen throughout. The decision variable is continuous prefix embedding prepended to each input; its quality is evaluated based on downstream task performance (e.g,, accuracy). Due to the high dimensionality of the prompt embedding space, apply Uniform Manifold Approximation and Projection (UMAP) [Melnnes et al. 2018 to project the original space into a lower-dimensional latent space.
SST-2 and SST-5 are sentiment classification tasks based on the Stanford Sentiment Treebank (Socher al. 2013). SST-2 is binary classification task where each sentence is labeled as either positive or negative. SST-5 is more challenging 5-class variant with labels: very negative, negative, neutral, positive, and very positive. Both tasks are derived from movie review sentences and are standard benchmarks for evaluating natural language understanding.
MR [Pang and Lee 2005 is a sentiment classification dataset composed of full movie reviews with hidden star ratings. The authors constructed both three-class (negative, neutral, positive) and four-class versions of the dataset by removing explicit rating indicators and grouping documents by rating level.
2004 is a sentiment classification dataset constructed from customer CR (Hu and Liu
reviews of various electronic products collected from Amazon and CNET. Each review is labeled as either positive or negative at the sentence level.
AG's News [Zhang et al. 2015 is a topic classification dataset consisting of news articles categorized into classes: World, Sports, Business, and Science/Technology. Each sample includes the article's title and short description. The dataset contains 120,000 training samples and 7,600 test samples, and commonly used to benchmark text classification models. We treat this a 4-class supervised learning task using the full text (title + description) as input.
TREC (Voorhees and Tice. 2000 is a question classification dataset designed for evaluating systems that categorize natural language questions into broad types. The standard setup includes 6 coarse-grained classes (e.g., Person, Location, Numeric) and 50 fine-grained subclasses. We use the 6-way classification task with 5,452 training and 500 test examples.
Subj [Pang and Lee 2004 is sentence-level subjectivity classification dataset consisting of 10,000 sentences: 5,000 subjective snippets from movie review sites and 5,000 objective sentences from plot summaries on IMDb. Each sentence is labeled as either subjective or objective.
GP-TS
GP-UCB
GP-EI
GP-KG
X0-GPTS
Time(second)
2773
2649
3017
3388
2813
Table Computation time (s) for five GP-based algorithms.
20

---

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 clearly state the contributions and scope of this paper.
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: See 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]
21

---

Justification:
See Assumption
1 and Theorem !
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 the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to 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: The information needed to reproduce the experiment is provided in Section and the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer 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 to 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 is a specific model and empirical evaluation, it may be necessary to either make 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 are 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) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
22

---

Answer: [Yes]
Justification: All datasets used are publicly available. Code, configuration files, and instruc- tions for reproducing experiments will be released publicly upon publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
public/guidest htwps///ooooduabsssssooooooooo
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https http://ooooSuuissssooeee
//nips.cc/pp wwcppbblccguuiicuceccccccoeooopp
Stt.SSbbbiiiiooooiiiii.oo for more details.
The authors should provide instructions 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Section and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
See Section
6 Figure 2 and Figure
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
23

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. 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 range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section 6 and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs 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 it 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 httpgs///eerrpp..ccppbl/////iiie
Answer: [Yes]
Justification:
This research conforms with the NeurlPS Code of Ethics.
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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a 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]
This work is theoretical study focused on the development and analysis of BO algorithms. Therefore, we believe this research does not raise direct societal impact concerns.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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 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 is being used 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 a system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
This paper does not release any pretrained models, scraped datasets, generative components that pose a risk of misuse or dual-use. The work is theoretical and does not involve the development deployment of models or data with potential for harm. Therefore, safeguards for responsible release are not applicable.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse 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 challenging, and many papers do not 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: All third-party assets used in this work, including publicly available datasets and code libraries, are properly credited in the main paper
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include 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 (c.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 package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
25

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
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 release a new codebase to support the implementation of our proposed method. The code is fully documented and includes usage instructions, dependencies, and example scripts reproduce all main results. anonymized version of the code is included in the supplementary materials for review.
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 obtained from people whose asset 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. Crowdsoureing 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: the paper does not involve crowdsourcing
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 to the NeurlPS 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: This work does not involve human subjects, crowdsourcing, or any form of user study.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
26

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This research does not use LLM as part of its core methods, experiments, or contributions. LLMs were not involved in any component that affects the originality.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hatp:e///eaatps..cooooofrrreree for what should or should not be described.
27


Reviews:
[{"review_id": "oD4LVOal0H", "reviewer": "Reviewer_v6ga", "summary": "1. This paper tackles the challenge of Bayesian Optimization when the reward distribution is unknown or complex (e.g., multi-modal or heavy-tailed). \n\n2. the authors propose a novel surrogate model $\\infty$-GP, which explicitly handles both uncertainty about the reward's value and uncertainty about its underlying distribution type. \n\n3. The authors provide theoretical proof that their method can approximate a wide class of reward distributions and show empirically that it outperforms SOTA in difficult optimization scenarios.", "questions": "Overall, this is a strong paper with compelling contributions. The idea of quantifying model uncertainty by placing a prior over Gaussian Processes (GPs) is natural and well-motivated, and the proposed approach represents a meaningful extension of mixture-of-experts (MOE) GPs. I think this work is a nicely-executed work. I have a few questions and comments below:\n\nQ1: The paper would be significantly strengthened by including a time complexity analysis. A formal analysis comparing the proposed method to the other baselines would be invaluable. Furthermore, reporting empirical runtime comparisons in the experiments would provide practical insight into the method's efficiency.\n\nQ2: Can the authors provide theoretical guarantees or further discussion on how the model uncertainty depends on the Spatial Dirichlet Process prior, $\\operatorname{SDP}(\\nu G_0)$? Specifically, I am curious about the sensitivity of the resulting uncertainty estimates to the choice of hyperparameters $\\nu$ and $G_0$, and how strongly this prior influences the posterior. How robust is the method to different human-specified priors?\n\nQ3: Regarding your main theoretical contribution (Theorem 1), could you provide more discussion on how your results compare to existing work? While you briefly mention that your assumptions are weaker than those in [Kanagawa et al., 2018], it would be helpful to elaborate on this point. Specifically, could you clarify what aspects of the assumptions are relaxed, and how your theoretical results—such as convergence rates—compare quantitatively or qualitatively with prior work?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written. It clearly presents the problem domain, thoroughly reviews related work, and precisely outlines its core contributions.\n\n2. The proposed $\\infty$-GP model is rigorously tested across a wide range of synthetic and real-world experiments. The results consistently show that the method outperforms state-of-the-art baselines, particularly in challenging scenarios.\n\n3. A significant strength of this work is the inclusion of theoretical guarantees for the $\\infty$-GP model. These guarantees are established under mild, reasonable assumptions, providing a solid theoretical foundation for the method's strong empirical performance.\n\nWeakness:\n\n1. To address the limitations of Gaussian Processes (GPs) in modeling complex reward functions, the paper introduces a Spatial Dirichlet Process (SDP) prior, $\\operatorname{SDP}(\\nu G_0)$, placed on the GP to improve model uncertainty estimation. However, the resulting uncertainty estimates are sensitive to the choice of hyperparameters $G_0$ and $\\nu$. The paper does not provide a theoretical or empirical analysis of how the model uncertainty depends on these hyperparameters, nor does it assess the sensitivity of the results to their variation. This lack of discussion raises concerns about the robustness and reproducibility of the proposed method, particularly in settings where appropriate values for $G_0$ and $\\nu$ are difficult to determine a priori.\n\n2. In Thompson Sampling, Gibbs sampling is required to draw samples from the posterior. However, Gibbs sampling can become computationally expensive as the dimensionality of the parameter space increases. The paper does not provide any discussion or analysis of the time complexity or scalability of the method. I am concerned about whether the proposed approach can be implemented efficiently and remain practical in high-dimensional settings.\n\n3. [Minor]. While the appendix provides experimental details, the main paper could be improved by more explicitly defining the performance metrics used in the plots and their corresponding discussions. Clearly stating what each axis and value represents directly in the captions or main text would enhance readability.", "was_revised": true, "final_justification": "The paper presents a well-rounded study of $\\infty$-GP, offering both strong theoretical guarantees and extensive experimental validation. My initial concerns about hyperparameters sensitivity have been thoroughly addressed by the authors during the rebuttal period. \n\nWith this point clarified, I will remain my positive evaluation and support the paper's acceptance.", "rebuttal": "We sincerely thank the reviewers for their thoughtful comments. We have carefully addressed all the questions and concerns raised.\n>* [W1 & Q2] Sensitivity analysis to hyperparameter choices in the prior\n\nThank you for the helpful comments. We have now included a sensitivity analysis to examine how the hyperparameters in the prior influence the performance. The prior hyperparameters include $a_\\nu, b_\\nu,a_\\tau, b_\\tau,a_\\sigma,b_\\sigma,b_\\phi$, and their settings are already provided in the appendix. We note that, **except for $b_\\phi$, the results are *not sensitive* to these prior hyperparameters**. See the sensitivity analysis table below, where we report the best-found objective values (optimal value=0) under different hyperparameter configurations on Ackley-HT-NS.\n\n| HyperParam | 0.5 | 1 | 1.5 | 2 |\n|------|-----|------|------|------|\n| $a_\\nu$   | -0.09 | -0.08 | -0.11 | -0.06 |\n| $b_\\nu$   | -0.13 | -0.08 | -0.08 | -0.09 |\n\n| HyperParam | 1   | 1.5 | 2    | 2.5 | 3   |\n|--------------|-----|-----|------|-----|-----|\n| $a_\\tau$     | -0.10 | -0.13 | -0.08 | -0.08 | -0.10 |\n| $b_\\tau$     | -0.10 | -0.11 | -0.08 | -0.14 | -0.07 |\n| $a_\\sigma$   | -0.06 | -0.10 | -0.08 | -0.08 |-0.14  |\n| $b_\\sigma$   | -0.19 | -0.06 | -0.08 | -0.12 |-0.12  |\n\n\n| HyperParam | 1    | 10   | 20   | 30   | 50   |\n|----------|------|------|------|------|------|\n|      $b_\\phi$    | -0.99 | -0.63 | -0.08 | -1.13 | -0.42 |\n\n\n**There are two main reasons why the performance is insensitive to the choice of $a_\\nu,b_\\nu,a_\\tau, b_\\tau,a_\\sigma,b_\\sigma$**: First, as shown in Lines 19, 21, and 22 of Algorithm 2, the posteriors of $\\nu$, $\\sigma$, and $\\tau$ all follow distributions with parameters of the form $(a_\\ast + \\mathcal{O}(n),\\ b_\\ast + \\mathcal{O}(n))$, where $a_\\ast$ and $b_\\ast$ refer to $a_\\nu, b_\\nu, a_\\tau, b_\\tau, a_\\sigma, b_\\sigma$. The only exception is the second parameter in the posterior of $\\nu$, but it can still be written as $b_\\nu$ plus a very large term $-\\log(w_L)$. $a_\\ast$ and $b_\\ast$ are typically set within the range 0–3. Therefore, as $n$ increases, the influence of these prior hyperparameters $(a_\\ast,b_\\ast)$ becomes negligible. They mainly act as initialization values and quickly fade in importance once $n$ is moderately large. Second, using TS policy, each decision step is based on only one sample from the posterior, which introduces significant randomness. This further reduces the influence of the initial hyperparameter values on the overall performance.\n\n\nBut the choice of $b_\\phi$ is critical, as it sets the range over which $\\phi$ can vary. We have already included guidance on setting $b_\\phi$ in the appendix. In general, this value is set to be quite large (since we use a very small $d$, e.g., 0.01), which ensures a sufficiently wide range for $\\phi$ to explore. In practice, we also use an adaptive strategy: we start with a very large $b_\\phi$, run a few initialization steps to observe the typical scale of $\\phi$, and then adjust $b_\\phi$ accordingly. This approach helps set $b_\\phi$ in a task-specific way.\n\n\n>* [W2&Q1] Regarding time complexity analysis.\n\nThanks for your helpful comments. We will include time complexity analysis in the updated version of this paper, and show that, by using a $L$-truncation technique (see Algorithm 2), **the complexity of our method is $\\mathcal{O}(n^3)$, which is equal to that of strandard GP-based BO.** \n\nIn short，the complexity is governed by two main components. (i) The computational complexity of Kriging, which is mainly govern by computing the inverse $\\Sigma_0(x_{1:n}, x_{1:n})^{-1}$, incurring $\\mathcal{O}(n^3)$ cost.  However, the $\\infty$-GP model enjoys the advantage that all surfaces share the same $\\Sigma_0(x_{1:n}, x_{1:n})^{-1}$, allowing this expensive matrix inversion to be computed only once. (ii) The complexity of Gibbs sampling. By truncating the maximum number of surface to $L$, one can sample the $\\xi_l(x_{1:n})$ jointly and thus the complexity is $\\mathcal{O}(n^3)$. In summary, the total complexity of $\\infty$-GP is $\\mathcal{O}(n^3)$.\n\n**The computational efficiency is supported by the following wall-clock time results (in seconds)**. Its runtime is comparable to that of GP-based baselines. This is because, although $\\infty$-GP requires expensive Gibbs sampling, the baseline methods also involve hyperparameter inference either through fully Bayesian MCMC or through MLE that relies on gradient-based optimization, both of which incur comparable computational complexity. Notably, $\\infty$-GP-TS performs only a single Gibbs sampling run in each optimization iteration, which significantly reduces its overall computational burden.\n\n| Objective       | GP-TS | GP-UCB | GP-EI | GP-KG | $\\infty$-GP-TS |\n|----------------|--------|--------|--------|--------|----------------|\n| Ackley-HT      | 2773   | 2649   | 3017   | 3388   | 2813           |\n| Ackley-NS      | 2798   | 2535   | 3001   | 3450   | 2912           |\n| Rosenbrock-HT  | 2782   | 2737   | 3210   | 3309   | 2858           |\n| Rosenbrock-NS  | 2689   | 2712   | 2803   | 3383   | 2853           |\n| StybTang-HT    | 2790   | 2619   | 3107   | 3007   | 2901           |\n| StybTang-NS    | 2805   | 2720   | 3030   | 3378   | 3098           |\n\n>* [Q3] Theoretical contribution compared with existing works. \n\nWe would like to clarify our theoretical contribution. In short, while the convergence of classic GP-based methods typically relies on restrictive and often opaque assumptions, **our results substantially relax these conditions**. To provide a clearer comparison, we rewrite the observed reward $y(x)$ as a deterministic component $\\mu^\\ast(x)$ plus a noise term $\\epsilon^\\ast(x)$.\n\n\n* In the classic GP literature, $\\mu^\\ast$ is assumed either to be a sample path drawn from a GP, or to lie in a RKHS associate with certain kernel and have a known RHKS norm bound (e.g. [1,2]), which is difficult to compute in practice. These assumptions are rarely verifiable in practice. For the noise term $\\epsilon^\\ast(x)$, to utilize concentration results, it is assumed to be independent and (sub-)Gaussian, or even noiseless in some formulations. \n\n* In our result, regarding the noise $\\epsilon^\\ast(x)$, our framework accommodates a significantly broader class of distributions. For example, Assumption 1 is satisfied by noise of the form $\\sum_{l=1}^L w_l(x)\\psi_l$, where each $\\psi_l$ belongs to distribution families such as Weibull (with shape $k > 1$), Gaussian, Laplace, Gamma, or exponential. Regarding the $\\mu^\\ast$, our result in Theorem 1 does not require any RKHS assumptions or GP sample path assumption as in the classic GP literature. But we note that, different from existing literature, Theorem 1 assumes a finite decision set. To handle the continuous case, a standard discretization argument (as in [2]) is required. Consequently, we need an additional assumption that $\\mu^*(x)$ is Lipschitz continuous, which is still much weaker than the assumptions typically made in the GP literature (those assumptions themselves imply Lipschitz continuity). \n\n\n[1] Russo D, Van Roy B. Learning to optimize via posterior sampling[J]. Mathematics of Operations Research, 2014, 39(4): 1221-1243.\n\n[2] Srinivas N, Krause A, Kakade S M, et al. Gaussian process optimization in the bandit setting: No regret and experimental design[J]. arXiv preprint arXiv:0912.3995, 2009.\n\n>*  [W3] Clarification of performance metrics and plot axes\n\nThe y-axis in Figure 2 and 3 denote the 'best-found' objective value. All the synthetic benchmarks show the original test function value in the y-axis. The y-axis for the portfolio task denote the portfolio return. The y-axis on both HPOBench and NASBench denote the accuracy on the validation set."}, {"review_id": "gBWsTBgRxM", "reviewer": "Reviewer_BoMR", "summary": "This paper introduces a novel surrogate model for Bayesian Optimization (BO), the infinity-Gaussian Process ($\\infty$-GP), designed to address challenges where the reward distribution is complex, non-stationary, or heavy-tailed. The $\\infty$-GP is formulated as a sequential spatial Dirichlet Process mixture with a Gaussian Process (GP) baseline. This approach allows the model to quantify not just value uncertainty but also *model uncertainty*—uncertainty about the underlying distributional form of the reward. The authors provide a theoretical analysis demonstrating that the $\\infty$-GP posterior can approximate a broad class of reward distributions with a near-minimax optimal posterior contraction rate. Empirically, the proposed $\\infty$-GP combined with Thompson Sampling ($\\infty$-GP-TS) is shown to outperform standard GP-based BO methods on various challenging synthetic and real-world benchmarks, including a prompt optimization task.", "questions": "1.  What is the conceptual relationship between the proposed $\\infty$-GP model and the **spectral mixture kernel**? Both are designed to model complex, non-stationary functions. Does $\\infty$-GP offer any distinct advantages over using a highly flexible kernel within a standard GP framework?\n\n2.  Could the authors further elaborate on the statement in lines 143-145 regarding the role of the noise term $\\epsilon_i$? The authors state it is introduced for \"modeling purposes to mix with the discrete-distributed $\\xi(x)$ and produce a continuous reward distribution\".\n\n3.  Could you provide more specific details for the empirical studies to improve reproducibility? Specifically:\n    * **HPOBench:** What is the specific task ID for the MLP experiment from the benchmark suite?\n    * **Prompt Engineering:** How was the UMAP projection configured (e.g., number of components, neighbors)? Were other dimensionality reduction techniques considered?\n    * **General:** How many MCMC iterations (B) and mixture components (L) were used in the Gibbs sampler (Algorithm 2) for the experiments?", "limitations": "Not discussed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "#### **Strengths**\n\n- **Novelty and Significance:** The paper proposes a novel and principled approach ($\\infty$-GP) to handle model misspecification in BO, which is a significant and practical problem. Standard GP-based methods often fail when their strong modeling assumptions are violated, and the $\\infty$-GP offers a flexible alternative by creating an infinite mixture of GP surfaces.\n- **Theoretical Justification:** A solid theoretical contribution supports the work. Theorem 1 establishes posterior convergence guarantees for the $\\infty$-GP model, demonstrating its ability to approximate a broad class of reward distributions at a near-minimax-optimal rate. This provides confidence in the model's robustness, extending beyond its empirical performance.\n- **Empirical Validation:** The experimental evaluation is comprehensive, covering synthetic benchmarks with non-stationary and heavy-tailed properties, real-world tasks like portfolio optimization and neural architecture search, and a modern application in LLM prompt optimization. The results consistently show the superiority of $\\infty$-GP-TS over standard GP baselines in these challenging settings.\n\n\n**Weaknesses**\n\n1.  **Limited Literature Review on Model Uncertainty:** The concept of \"model uncertainty\" is framed as a key motivator, yet the literature review on this topic feels incomplete. This issue has been previously addressed under the umbrella of hyperparameter learning for surrogate models. A relevant and missing work is \"Self-Correcting Bayesian Optimization through Bayesian Active Learning\" by Hvarfner et al. (2024), which also actively manages model uncertainty. The current related work section could be strengthened by positioning the $\\infty$-GP in the context of these alternative approaches.\n\n2.  **Missing State-of-the-Art Baselines:** The paper compares $\\infty$-GP-TS against four standard academic baselines: GP-TS, GP-UCB, GP-EI, and GP-KG. While these are foundational, the comparison lacks more recent, powerful, and industrially relevant baselines. For instance, HEBO, which explicitly handles heteroscedastic and non-stationary rewards via input and output warping, has demonstrated state-of-the-art performance. The recent Vizier report (2024) also highlights robust methods for these scenarios. Including a comparison to at least one such advanced baseline would provide a more convincing measure of the proposed method's practical utility.\n\n3.  **Lack of Regret Analysis:** While the paper provides a posterior convergence guarantee (Theorem 1), it does not offer a theoretical analysis of the cumulative regret for the proposed $\\infty$-GP-TS algorithm. Regret bounds are a standard way to characterize the sample efficiency of a BO algorithm. Without this analysis, the theoretical understanding of the algorithm's exploration-exploitation trade-off remains incomplete.\n\n4. **Insufficient Experimental Details:** Although the empirical studies are broad, they lack key details necessary for full reproducibility.\n    * For **HPOBench**, the paper states it uses the \"MLP task\" but does not specify the task ID or the number of training epochs, making it difficult to replicate the results.\n    * The **prompt optimization** section is missing comparisons to domain-specific BO baselines. The setup could also be clarified further regarding the construction of the UMAP search space.\n    * The hyperparameter choices for each experiment are not explicitly discussed.\n\n\nReference:\n- Hvarfner, Carl, Erik Hellsten, Frank Hutter, and Luigi Nardi. \"Self-correcting bayesian optimization through bayesian active learning.\" Advances in Neural Information Processing Systems 36 (2023): 79173-79199.\n\n- Cowen-Rivers, Alexander I., Wenlong Lyu, Rasul Tutunov, Zhi Wang, Antoine Grosnit, Ryan Rhys Griffiths, Alexandre Max Maraval et al. \"Hebo: Pushing the limits of sample-efficient hyper-parameter optimisation.\" Journal of Artificial Intelligence Research 74 (2022): 1269-1349.\n\n- Song, Xingyou, Qiuyi Zhang, Chansoo Lee, Emily Fertig, Tzu-Kuo Huang, Lior Belenki, Greg Kochanski et al. \"The vizier gaussian process bandit algorithm.\" arXiv preprint arXiv:2408.11527 (2024).", "was_revised": true, "final_justification": "Despite having issues connecting the currently presented results to the canonical cumulative regret bound, I believe the novel theoretical insight on the convergence of the simple regret, and the empirical results showing improvement on some well-known tasks qualify as acceptance.", "rebuttal": "We sincerely thank the reviewers for their thoughtful comments and constructive feedback. We have carefully addressed all the questions and concerns raised, and have made corresponding revisions or clarifications as detailed below.\n\n>* [W1]:Missing discussion on existing literature on model uncertainty in hyperparameter learning\n\nThank you. We will revise the last paragraph of the “Related Work” section to explicitly contrast our $\\infty$-GP framework with prior work on model uncertainty in hyperparameter learning and related areas, including Hvarfner et al. (2024) and other relevant studies such as [1,2]. Specifically, we will clarify that **those approaches manage model uncertainty within a fixed model class (e.g., GPs with uncertain kernel design), whereas our $\\infty$-GP addresses uncertainty *over* model classes** by placing a prior over the distributional space of reward models, offering greater modeling flexibility.\n\n[1] Malkomes G, Garnett R. Automating Bayesian optimization with Bayesian optimization[J]. Advances in Neural Information Processing Systems, 2018, 31.\n\n[2] Malkomes G, Schaff C, Garnett R. Bayesian optimization for automated model selection[J]. Advances in neural information processing systems, 2016, 29.\n\n>* [W2] Missing comparison with state-of-the-art industrially relevant methods such as HEBO.\n\nThanks for your helpful comments. In response, **we have included HEBO as an additional baseline in our updated experiments** (see the table below, which reports the best-found performance after 100 iterations). Our method consistently outperforms HEBO in Portfolio task, HPOBench and NASBench.\n\n| method | Portfolio | HPOBench | NASBench |\n|-|-|-|-|\n| HEBO | 10.4 | 67.3 | 69.2 |\n| $\\infty$-GP-TS | 11.4 | 68.7 | 70.5 |\n\nFirst, while HEBO incorporates input and output warping to address non-stationarity (in fact, in our experiments, all baselines for nonstationary tasks already adopt input warping techniques by default), it still relies on a single GP model as the surrogate. As such, the model class that a single GP can represent remains limited, and it cannot handle heavy-tailed noises. Our results show that warping alone is insufficient. Second, HEBO ensembles multiple base acquisition functions (e.g., EI, UCB) to improve search efficiency. However, as our results demonstrate, in highly complex reward landscapes involving model misspecification, the choice of a more expressive surrogate model (such as $\\infty$-GP) is often more critical than acquisition efficiency. Importantly, the complex structure of our $\\infty$-GP surrogate is learned directly from data, rather than hand-crafted through warping techniques.\n\n>* [W3] Lack of Regret Analysis\n\nThanks for your helpful comment. We will include regret analysis in the updated version of the paper. In fact, we **only need one additional step** from our established Theorem 1 to derive a regret bound. The instantaneous regret at step $n$ satisfies: $$r_n\\leq\\int |\\mu^\\ast(x)||\\pi_{f_n}(x)-\\pi_{f^\\ast}(x)|dx\\leq2\\mu^\\ast(x_\\ast)\\delta(\\pi_{f_n},\\pi_{f^\\ast})\\leq2\\mu^\\ast(x_\\ast)\\delta(f_n,f^\\ast),$$ where $\\delta$ is total variation distance (TVD), $\\pi_{f_n}$ and $\\pi_{f^\\ast}$ is the TS policy distribution induced by surrogate posterior $f_n=f(y(x_n)|\\mathcal{H}_n)$ (defined in Eq.(8)) and true reward $f^\\ast$, respectively. The last inequality follows from the *data processing inequality*. The convergence $\\delta(f_n,f^\\ast)\\to 0$ has already been established in Theorem 1 (noting that L1 norm= 2TVD). **Therefore, we obtain $r_n\\to 0$, implying so-called no-regret or sublinear cumulative regret.**\n\nMoreover, the concrete regret rate can be made explicit by leveraging the posterior contraction result in Theorem 1, requiring only a standard discretization argument (e.g., from [3]) to handle the continuous decision space.\n\n[3] Srinivas N, Krause A, Kakade S M, et al. Gaussian process optimization in the bandit setting: No regret and experimental design[J]. arXiv preprint arXiv:0912.3995, 2009.\n\n>* [W4&Q3] Regarding Experimental Details: \n\n**(1)HPObench details:** We would like to clarify that we used the \"kc1\" dataset for the MLP task, which is widely adopted in the AutoML and HPO benchmark community. The OpenML task ID for kc1 is 3917. This dataset consists of 2,109 training instances and 22 features (after preprocessing), and it originates from a real-world software defect prediction task. \n\n**(2)Prompt optimization details:** We apply UMAP to compress high-dimensional prompt embeddings into a 10-dimensional manifold-preserving latent space. The specific UMAP configuration is as follows: we set the number of components to 10 (i.e., n_components=10), and the number of neighbors to 15 (n_neighbors=15). We also used the 'cosine' distance metric, as it is more suitable for semantic embeddings than the default Euclidean metric. The minimum distance parameter was set to 0.0 to encourage tighter clusters in the projected space. Other dimensionality reduction techniques such as PCA and t-SNE were considered, but we chose UMAP because it preserves both local and global structure, is computationally efficient for large text collections, and allows flexible adjustment of clustering granularity via the n_neighbors parameter.\n\n\nRegarding the comment on “missing comparisons to domain-specific BO baselines,” to the best of our knowledge, there is no established class of BO algorithms specifically tailored for prompt optimization that fundamentally differs from general-purpose BO methods. Notable works, including [4] and [5], all rely on standard BO algorithms such as GP-UCB or GP-EI. Compared with our implementation, their main difference lies in the way they embed or reduce the dimensionality of the prompt space. To ensure a fair comparison focused on the BO algorithm itself rather than the embedding method, we adopt UMAP across all methods.\n\n**(3) Hyperparameter setting:** In our experiments, we set the number of MCMC iterations to B = 500 and the truncation number of mixture components to L = 8.\n\n[4] Chen L, Chen J, Goldstein T, et al. Instructzero: Efficient instruction optimization for black-box large language models[J]. arXiv preprint arXiv:2306.03082, 2023.\n\n[5] Sabbatella A, Ponti A, Giordani I, et al. Prompt optimization in large language models[J]. Mathematics, 2024, 12(6): 929.\n\n>* [Q1] Clarify difference between $\\infty$-GP and spectral mixture kernel: \n\nThe spectral mixture kernel (SMK) enhances the expressiveness of a **single GP** by constructing flexible kernels through spectral mixtures. However, these methods still assume the reward process lies within the GP family, thus limiting their modeling flexibility. In contrast, $\\infty$-GP places a prior over the space of reward distributions, allowing us to model rewards that are not themselves GPs. This enables model uncertainty over function classes, rather than within a fixed class. **Compared to using a highly flexible kernel within a standard GP (e.g., SMK), the $\\infty$-GP offers several distinct advantages**.  \n* First, it provides greater modeling flexibility and accommodates not only non-stationary rewards, but also heavy-tailed, heteroskedastic, and other non-Gaussian noise structures, as supported by our theoretical guarantee in Theorem 1. \n* Second, **SMK can be directly incorporated into $\\infty$-GP framework** by replacing the base kernel. Since $\\infty$-GP is a mixture over infinitely many GPs, it is compatible with any GP extensions, including custom kernel designs and other architectural improvements. \n* Third, unlike standard GPs, $\\infty$-GP quantifies not only value uncertainty but also model uncertainty.\n\n>* [Q2] question regarding the role of the noise term\n\nLet us further explain the role of the noise term $\\epsilon$. As defined in Eq. (6), $\\xi$ is discretely distributed (though with infinite support), so it cannot directly model a continuous reward distribution. By mixing $\\xi$ with a Gaussian $\\epsilon$, the resulting distribution of $y(x)=\\xi(x)+\\epsilon(x)$ becomes continuous. Here, the term $\\epsilon$ does not mean that we impose a Gaussian assumption on the true measurement noise, as we directly model the overall distribution of the observation $y$ via Eq. (4), rather than modeling the expectation and measurement noise separately as in classic GP-based BO. Therefore, we say the term $\\epsilon$ is introduced solely for “modeling purposes”, without real physical meaning."}, {"review_id": "HZi5wen8gU", "reviewer": "Reviewer_JUCH", "summary": "- Traditional Gaussian Process (GP) surrogate-based Bayesian Optimisation (BO) struggles with non-stationary, multi-modal, and heavy-tailed objective function distributions $f(x)$ due to strong structural assumptions. Most of the standard GPs capture value uncertainty but not model uncertainty, leading to poor performance when the underlying Gaussian structural assumptions are violated.\n\n- This paper introduces a $\\infty-$Gaussian Process ($\\infty-$GP), a novel surrogate that constructs the reward function or the objective function as an infinite mixture of GP surfaces via a spatial Dirichlet Process (SDP). The proposed $\\infty-$GP is paired with the Thompson Sampling (TS) strategy that samples a surrogate function from the posterior and maximises it to select the next candidate for function evaluation. Additionally, they also balance between exploring the unknown search surfaces and exploiting the known search surfaces to find the optima. \n\n- The empirical results provided outperform GP-based BO methods on both synthetic and real-world tasks, especially in non-stationary and heavy-tailed noise settings. Authors have also demonstrated the applicability of their proposed method in complex tasks like LLM prompt tuning.", "questions": "- How is the scalar precision parameter $\\nu$ determined? While its prior distribution is mentioned as a Gamma distribution in Appendix B.1 (Equation 27), the specific values or settings for the hyperparameters $a_\\nu$ and $b_\\nu$ are not clearly stated. Clarification on these parameters would be helpful.\n\n- How sensitive are the hyperparameters priors used in the posterior inference procedure (Gibbs Sampling)?\n\n- Is there a specific statistic/metric that quantifies the reuse of latent surfaces across iterations to support the claims about exploitation behaviour of the proposed approach (discussed in Lines 221–223)? \n\n- What is the theoretical order of the regret for the proposed method? Does it maintain sub-linear regret, similar to standard Thompson Sampling-based BO? If so, what are the key theoretical differences due to operating in the distributional space, and would they affect regret bound?\n\n- How does the proposed approach compare with existing BO methods that exploit additive structures of the objective function [1]? Given that the $\\infty-$GP uses multiple latent GP surfaces, does it implicitly capture the additive nature of the objective function, or are there fundamental differences?\n\n- While the authors address non-stationarity via input warping, several BO methods use explicitly non-stationary kernels or model heteroskedastic noise directly. Why were such approaches not included in the comparisons? A direct evaluation against BO methods with non-stationary kernels would provide a more thorough benchmark and further strengthen the benefits of the proposed approach.\n\n\n\n - **Minor Questions**\n \t- What does the y-axis represent in Figure 2? Would normalisation or standardisation of the reward values impact the performance or stability of the proposed method?\n   - What is the number of input dimensions used in the synthetic function benchmarks? Including this detail would help assess the scalability and complexity of the evaluation tasks.", "limitations": "Although the authors acknowledge the issue of scalability of the proposed approach to high dimensions, there are a few other important limitations that are not mentioned in the manuscript. \n\n- The method relies on Gibbs sampling for posterior inference over multiple GP surfaces, which is computationally intensive, especially for large datasets.\n\n- The performance of the $\\infty-$GP model is highly dependent on the careful selection of hyperparameter priors and these priors are often domain-specific and may not generalise well across different tasks.\n\n- The paper does not provide formal regret bounds for the proposed BO strategy, thereby limiting its theoretical interpretability and comparability to standard BO methods (backed by known sub-linear regret guarantees).", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths** \n\n- In this paper authors bring in the notion of _Model Uncertainty_ aspects of the BO Process, in contrast to the _value uncertainty_ generally considered in the Bayesian optimisation literature. \n\n- Inspired by the prior literature on infinite mixture of GPs, authors have devised a novel approach $\\infty-$GP, that models the objective function as an infinite mixture of GP surfaces via a spatial Dirichlet Process (SDP). \n\n- The proposed $\\infty-$GP accounts for uncertainty in the choice of surrogate model itself (model uncertainty), not just the output values (value uncertainty), by allowing each input location to probabilistically mix over infinite GP surfaces.\n\n- Authors have combined $\\infty-$GP surrogate model with Thompson Sampling (TS) acquisition function to effectively balance between the exploration of the unknown regions and exploitation of the known regions/solutions. \n\n- In contrast to exploration-exploitation in the traditional TS-based BO methods, the proposed approach discusses the exploration-exploitation tradeoff in the distributional space wherein the exploitation refers to probabilistic selection of the existing surfaces and exploration refers to introducing a new GP surface for realising the candidate points.\n\n\n**Weaknesses** \n\n- The authors have performed posterior inference using a Gibbs sampling strategy under a fully Bayesian model. In general, Gibbs sampling over infinite (or many) GP surfaces and posterior inference can be computationally intensive, especially for large datasets. Authors have also mentioned that the number of mixture components is set to a finite value $L$ (Line 571 in B.2 of Appendix), contradicting the motivation to use an infinite mixture of GP surfaces. Further, the performance may degrade if $L$ is not chosen appropriately. \n\n- The success of the proposed sampling strategy and thus the overall BO procedure relies heavily on the prior specification of the hyperparameters (Equations 24 to 27 in Appendix B.1), including kernel width, noise variance, and the Dirichlet process concentration parameter. These priors are often highly domain-specific and task-sensitive, which may limit the method’s generalizability without some tuning efforts.\n\n- In the ablation results, the authors concluded that the reward space can be effectively modelled as a mixture of multiple latent GP surfaces. However, the paper does not discuss the existing BO literature that leverages the additive structure of the objective function. Incorporating a discussion of such approaches could provide some context and help understand the advantages of the proposed method.\n\n- Although the empirical analyses demonstrate improved performance over classical GP-based BO methods, it does not include comparisons against state-of-the-art approaches specifically designed to address non-stationarity [1,2] or exploit additive structure [3] in the objective function space, including such baselines would provide a comprehensive evaluation of the proposed method’s strengths and limitations. \n\n- In the manuscript, the authors do not discuss the implications of the sampling strategy on the regret bounds of the overall Bayesian optimisation process. Discussing the regret bounds of the proposed approach could be highly beneficial to compare with other state-of-the-art methods that generally discuss the space/time complexities and the regret bounds.\n\n**References** \n\n[1] Ruben Martinez-Cantin. Funneled Bayesian optimisation for design, tuning and control of autonomous systems. IEEE Transactions on Cybernetics, 49(4):1489– 1500, 2019. \n\n[2] Remes, Sami, Markus Heinonen, and Samuel Kaski. \"Non-stationary spectral kernels.\" Advances in neural information processing systems 30 (2017).\n\n[3] Gardner, Jacob, Chuan Guo, Kilian Weinberger, Roman Garnett, and Roger Grosse. \"Discovering and exploiting additive structure for Bayesian optimisation.\" In Artificial Intelligence and Statistics, pp. 1311-1319. PMLR, 2017.", "was_revised": true, "final_justification": "After reading the author's rebuttal and engaging in a discussion with them, I am keeping my final score as \"Borderline Accept.\"", "rebuttal": "We sincerely thank the reviewers for their thoughtful comments. We have carefully addressed all the questions and concerns raised.\n>* [W1] Regarding the computational complexity of Gibbs sampling and the choice of truncation number $L$\n\nFirst, we use a truncation technique in Gibbs sampling, i.e. setting the maximum number of mixture component to fixed $L$. By doing so, the complexity of truncated Gibbs sampling is $\\mathcal{O}(n^3)$, which is exactly **equal to traditional GP** (for more details, please refer to our response to W5&Q3). \n\nSecond, despite using a finite truncation, we must note that **we are not \"contradicting the motivation to use an infinite mixture of GP surfaces\", and our model is still theoretically an infinite mixture of GPs**. This is because, as shown in Eq. (10), when we actually perform posterior prediction using the $\\infty$-GP, we do not use infinitely many surfaces, but rather $K_n+1$ surfaces. The truncation level $L$ essentially imposes an upper bound on $K_n$, and in our experiments, we set $L=8$. In practice, this upper bound is rarely reached, and thus the performance is largely insensitive to the choice of $L$. This observation is supported both theoretically and empirically. **Theoretically**, as shown in Equation (2.6) of [1], the number of active surfaces $K_n$ in a Dirichlet Process grows very slowly with $n$, at a rate of $\\log n$. **Empirically**, the table below reports the best found values (optimal = 0) for the Ackley-HT-NS task under different values of $L$. The performance is not sensitive to $L$. This is because, by the 100th iteration, we observe that only 2–3 surfaces have non-negligible weights in the posterior distribution. The remaining layers are essentially unused, so When $L$ is 6 or greater, changing it has little impact on the result.\n\n\n| $L$   | 6     | 7     | 8     | 9     | 10    |\n|-------|-------|-------|-------|-------|-------|\n| Best Found Value | -0.10 | -0.09 | -0.08 | -0.11 | -0.09 |\n\n[1] Bayesian nonparametrics[M]. Cambridge University Press, 2010.\n\n>* [W2 & Q1 & Q2] Prior specification and sensitivity to hyperparameter choices. \n\nThanks for the questions. The prior specification involves two parts: (i) choosing the prior distribution families, and (ii) setting the hyperparameters for those priors. We explain the two parts one by one below.\n\n(i) We use conjugate priors for $\\sigma^2$, $\\tau$ and $\\nu$ to allow efficient Gibbs sampling with analytical posterior updates. These choices are quite standard and make the inference much easier in practice. For $\\phi$, we follow the recommendation from [2] and use a uniform prior, which is shown in their paper to work well and be numerically stable.\n\n\n(ii) The prior hyperparameters include $a_\\nu, b_\\nu, a_\\tau, b_\\tau, a_\\sigma, b_\\sigma, b_\\phi$. We did not include the precision prior hyperparameter $(a_\\nu, b_\\nu)$ in the appendix, but in our experiments, we simply set it to $(1,1)$. The settings for the other hyperparameters are already listed. We note that, **except for $b_\\phi$, the results are not sensitive to these prior hyperparameters**. Please refer to our response to **[W1 & Q2] of Reviewer v6ga** for a detailed sensitivity analysis of the prior hyperparameters, where we provide both empirical results and theoretical justifications. We also provide guidance on how to choose the $b_\\phi$.\n\n[2] Gelfand A E, Kottas A, MacEachern S N. Bayesian nonparametric spatial modeling with Dirichlet process mixing[J]. Journal of the American Statistical Association, 2005, 100(471): 1021-1035.\n\n>* [W3 & W4 & Q5 & Q6] Comparison to additive GP and non-stationary kernel baselines\n\nThank you for these insightful suggestions. We will include relevant comparisons to BO methods that exploit additive structure and use explicitly non-stationary kernels  in the revised version. We would like to clarify that **the proposed $\\infty$-GP is fundamentally different from additive GP models**. Additive BO are designed for high-dimensional problems by partitioning the input dimensions and assigning a single GP surrogate to each subset of dimensions. The resulting model is still a single GP but with an additive kernel. In contrast, our $\\infty$-GP framework models the entire input space globally as a mixture of infinitely many GP surfaces. The resulting model is no longer a GP, and can represent reward models that lie far beyond the GP function class. By the way, **additive BO can be seamlessly integrated into the $\\infty$-GP framework** by replacing the standard GP in each surface with an additive GP.\n \nAs recommended, we will include the following experimental results comparing our method with TS using additive GP in [4] and non-stationary spectral kernel GPs in [3]. Both alternatives underperform our method. This is because both baselines still operate within the single-GP framework, which is limited in its ability to model complex rewards.\n|  | Portfolio | HPOBench | NASBench |\n|-|-|-|-|\n| Additive-TS | 9.0 | 67.3 | 65.0 | \n| Nonstationary-TS | 10.4 | 65.2 | 68.5 | \n| $\\infty$-GP-TS | 11.4 | 68.7 | 70.5 |\n\n[3] Remes, Sami, Markus Heinonen, and Samuel Kaski. \"Non-stationary spectral kernels.\" Advances in neural information processing systems 30 (2017).\n\n[4] Gardner, Jacob, Chuan Guo, Kilian Weinberger, Roman Garnett, and Roger Grosse. \"Discovering and exploiting additive structure for Bayesian optimisation.\" In Artificial Intelligence and Statistics, pp. 1311-1319. PMLR, 2017.\n\n\n>* [W5 & Q4] Regarding regret analysis and time complexity analysis\n\n\nThanks for your helpful comment. We will include regret and time complexity analysis in the updated version of the paper. \n\n* Regret: **The $\\infty$-GP-TS indeed maintains sub-linear regret.** In fact, we only need one additional step from our established Theorem 1 to derive a regret bound. The instantaneous regret at step $n$ satisfies: $r_n\\leq\\int |\\mu^\\ast(x)||\\pi_{f_n}(x)-\\pi_{f^\\ast}(x)|dx\\leq2\\mu^\\ast(x_\\ast)\\delta(\\pi_{f_n},\\pi_{f^\\ast})\\leq2\\mu^\\ast(x_\\ast)\\delta(f_n,f^\\ast)$, where $\\delta$ is total variation distance (TVD), $\\pi_{f_n}$ and $\\pi_{f^\\ast}$ is the TS policy distribution induced by surrogate posterior $f_n$ (defined in Eq.(8)) and true reward $f^\\ast$, respectively.\n The last inequality follows from the *data processing inequality*. The convergence $\\delta(f_n,f^\\ast)\\to 0$ has already been established in Theorem 1 (noting that L1 norm= 2TVD). Therefore, we obtain $r_n\\to 0$, implying sublinear cumulative regret. Moreover, the concrete regret rate can be made explicit by leveraging the posterior contraction result in Theorem 1.\nRegarding the question about \"the key theoretical differences due to operating in the distributional space,\" we would like to clarify the following: First, our model indeed defines a prior over the distributional space (i.e., $G$ is drawn from an SDP). However, as shown in Eq. (13), we marginalize out the random distribution $G$ over the SDP when computing the posterior predictive distribution. As such, the actual $\\infty$-GP-TS algorithm does not explicitly operate over the distributional space. Second, the theoretical difference is as follows: Traditional GP-TS analyzes regret by studying how the posterior predictive mean concentrates around the true function. In contrast, in $\\infty$-GP-TS, as shown in Theorem 1 and the above analysis, we bound the regret in terms of the contraction rate of the posterior over the distributional space toward the true reward distribution.\n\n\n \n* Time Complexity: By using a truncation technique (see Algorithm 2), **the complexity of our method is $\\mathcal{O}(n^3)$, which is equal to that of strandard GP-based BO.** In short，the complexity is governed by two main components. (i) The computational complexity of Kriging, which is mainly govern by computing the inverse $\\Sigma_0(x_{1:n}, x_{1:n})^{-1}$, incurring $\\mathcal{O}(n^3)$ cost.  However, the $\\infty$-GP model enjoys the advantage that all surfaces share the same $\\Sigma_0(x_{1:n}, x_{1:n})^{-1}$, allowing this expensive matrix inversion to be computed only once. (ii) The complexity of Gibbs sampling. By truncating the maximum number of surface to $L$, one can sample the $\\xi_l(x_{1:n})$ jointly and thus the complexity is $\\mathcal{O}(n^3)$. In summary, the total complexity of $\\infty$-GP is $\\mathcal{O}(n^3)$. The time complexity analysis is supported by the following wall-clock time results (in seconds). \n\n|    Objective    | GP-TS | GP-UCB | GP-EI | GP-KG | $\\infty$-GP-TS |\n|----------------|-------|--------|-------|--------|----------------|\n| Ackley-HT      | 2773  | 2649   | 3017  | 3388   | 2813           |\n\n\n>* [Q3] Question about metric that quantifies the reuse of latent surfaces\n\n Thank you for this insightful question. The reuse of latent surfaces can indeed be quantified with the following quantities. First, $n_j$ quantifies how many times the surface $j$ has been reused in past iterations. Second, the posterior of $\\nu$ characterizes the decision maker’s model uncertainty and governs the trade-off between introducing new surfaces (exploration) versus reusing existing ones (exploitation). Smaller values of $\\nu$ encourage more reuse. Third, the ratio $\\frac{{n}_j}{\\nu + n}$ quantifies the probability of reusing surface $j$ in the upcoming new iteration.\n\n>* [Q7] Minor questions\n\nThe y-axis in Figure 2 denote the original value of the test function. In our experiments, all methods—including both the baseline BO approaches and our $\\infty$-GP-TS use sklearn.MinMaxScaler to linearly map observed rewards into the fixed interval $[-5,5]$ before fitting the surrogate. It is a common practice for BO to ensure numerical stability. And all methods use the same affine transform to ensure fair comparisons. After fitting the surrogate, we use the inverse transform to show the final result in the paper. The dimensions for the synthetic function is 20."}, {"review_id": "g9kFXz4gsg", "reviewer": "Reviewer_44us", "summary": "This paper considers Bayesian optimization where there is not only uncertainty in the reward model parameters but also in the reward model itself. They propose a new GP-based BO method to facilitate Bayesian optimization under this relaxed modeling assumption. The authors prove theoretical approximation guarantees and empirical results on synthetic experiments and LLM experiments.", "questions": "1. Could the authors elaborate more on the extension to high-dimensional BO problems, which were not included in the empirical valuation? \n2. Could the authors describe in more detail how their setting differs from mis-specified BO?\n3. Does equation (5) just expand the model class, and hence, allow one to avoid specifying a specific GP prior? To what extent is this broader class able to capture arbitrary reward models? (Apologies, I am not very familiar with SDP in this context.)", "limitations": "Yes", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n- the paper seems to tackle an important problem, which in my view is well-motivated by the discussion of model uncertainty in the introduction\n- the paper includes both theoretical and empirical results, and the theoretical results match the minimax optimal rate, which is a strength \n- it seems that the problem of model uncertainty has not directly been studied in the research previously \n\nWeaknesses\n- as someone who does not have a Bayesian optimization background (but still an ml/optimization theory background), I found the paper quite difficult to follow; this could be because I am not familiar with the landscape of the literature or because the writing lacks clarity. to be more specific, it was a bit difficult for me to understand how this paper sits in the related work, and I think that section in particular could be explained in a way that better explains the topic to a nonexpert in this specific subfield. \n- on many of the experiments, it seems that confidence bars between the new method overlap. \n- it is not clear to me how much the extension to capture model uncertainty constitutes as a", "was_revised": true, "final_justification": "I thank the reviewers, authors, and ACs for their time. I will generally maintain my score of 3 due to remaining unconvinced about the technical novelty as raised in my initial review and my lack of familiarity with topic area. My main concern is \n- I'm not sure how interesting / novel it is to extend existing frameworks to incorporate these new reward models, possibly because I am not a Bayesian optimization researcher.\n- There is an absence of certain theoretical guarantees such as the regret bounds in the original manuscript. Although the authors claim it is easy to derive, I feel like I don't understand the main theoretical contribution still \nI defer to other reviewers and the AC, as I am not an expert in this field.", "rebuttal": "We thank Reviewer 44us for the valuable feedback. We have addressed all concerns.\n\n>* [W1] Clarify the paper’s positioning in related work for non-BO experts.\n\nThanks for the suggestion. To make the paper more accessible to non-experts, we will revise Section 2 to clearly highlight the two key components of BO, namely the acquisition policy and the surrogate model, and clarify that our contribution lies in proposing a new, more powerful surrogate. We will also revise the second paragraph of the Introduction and the paragraph of Related Work to better position our $\\infty$-GP model as a replacement and enhancement of the standard GP, which serves as a fundamental backbone for BO and many uncertainty quantification tasks.\n\n**Here is a brief overview of our contribution. GP is the foundational surrogate model in BO. We propose an enhancement of this backbone**: the $\\infty$-GP model, which defines an infinite mixture of GPs while remaining tractable in practice. This enables modeling a much richer class of complex reward distributions. The intuition is similar to the universal approximation theorem: one can approximate a complex function using an infinite sum of simple base functions. At the same time, $\\infty$-GP inherits the nice properties of standard GPs, such as closed-form updates and extensibility.\n\n>* [W2] Concern regarding overlapping confidence bars:\n \nWhile our method’s confidence intervals partially overlap with those of some baselines, the overlap is minor, and our method consistently achieves significantly better mean performance. BTW, we believe this overlapping phenomenon is fairly common and expected in BO (e.g., as also observed in [1]). One reason for the overlap is that BO algorithms typically encourage exploration, which introduces more randomness and can lead to wider confidence intervals. \n\n[1] Xu, Zhitong, et al. \"Standard Gaussian Process is All You Need for High-Dimensional Bayesian Optimization.\" The Thirteenth International Conference on Learning Representations.\n\n>* [Q1] Question regarding the extension to high-dimensional BO:\n \nSince the $\\infty$-GP model is defined as a mixture over infinitely many GPs, each layer corresponds to a standard GP. By modifying the base GP in each layer, **our framework can seamlessly incorporate any existing GP extensions, including those designed for high-dimensional settings**. For example, sparse GPs, Gaussian Markov random fields, additive GPs, GP with low-dimensional subspace embeddings, and high-dimensional BO methods utilizing deep learning.\n\nIndeed, **our experiment on the prompt optimization task already provides some empirical evidence on how the $\\infty$-GP framework can be extended to high-dimensional settings**. In this task, we use UMAP for dimensionality reduction, which can be viewed as a low-dimensional embedding-based BO method, and observe strong empirical performance under this setting.\n\n>* [Q2] Clarify how the proposed setting differs from mis-specified BO:\n \nThanks for the question. Existing mis-specified BO methods typically handle limited types of model mismatch, such as incorrect smoothness assumptions, within a fixed model class like GPs. In contrast, our $\\infty$-GP model places a prior over the entire space of reward distributions, allowing us to capture model uncertainty *across* different function classes and providing much greater flexibility.\n\n\n>* [Q3] Clarify whether Eq. (5) simply expands the model class and how expressive it is: \n\nThanks for the question. Your understanding of Eq.(5) is essentially correct, but more precisely, **we are not simply expanding the model class; instead, we let the reward model (which is a distribution) itself be random and place a prior over the space of reward distributions**. Regarding “to what extent is this broader class able to capture arbitrary reward models,” the discussion following Assumption 1 rigorously characterizes the class of reward distributions that can be approximated by our $\\infty$-GP model, and shows that it is significantly broader than that of standard GP model. We also note that our paper does not require the reader to have prior knowledge of SDP, as we clearly define the SDP and provide intuitive explanations to aid understanding.\n\n>[W3] \n\nThe comment in Weakness 3 appears incomplete. We would appreciate it if the reviewer could kindly clarify or complete the sentence, so we can provide a proper and constructive response."}]

Author rebuttal:

Meta-review: This paper introduces the infinity-Gaussian Process, a new surrogate model designed to address limitations of classical Gaussian Process models when dealing with complex, non-stationary, or heavy-tailed reward environments.
The paper offers good theoretical guarantees of the proposed inf-GP-TS, including proven posterior contraction rates, which lend credibility to handle a variety of complex reward distributions.
The full Bayesian setup of hyperparameters is not deeply discussed in the main text, which could be critical since the method relies on several prior specifications. Comparisons with other recent BO approaches, beyond a brief mention, could strengthen the claims.
The authors and 3/4 reviewers had sufficient discussions. AC agree with the majority of the reviewers that this paper passed the borderline of NeurIPS acceptance.
Decision: Accept (poster)