BILBO: BILevel Bayesian Optimization
Authors: Ruth Wan Theng Chew
Quoc Phong Nguyen
Bryan Kian Hsiang Low
Venue: ICML 2025 poster (2025)
Keywords: machine learning
Bayesian optimization
bilevel optimization
bilevel Bayesian optimization
Primary area: probabilistic_methods->bayesian_models_and_methods

Abstract: Bilevel optimization is characterized by a two-level optimization structure, where the upper-level problem is constrained by optimal lower-level solutions, and such structures are prevalent in real-world problems. The constraint by optimal lower-level solutions poses significant challenges, especially in noisy, constrained, and derivative-free settings, as repeating lower-level optimizations is sample inefficient and predicted lower-level solutions may be suboptimal. We present BILevel Bayesian Optimization (BILBO), a novel Bayesian optimization algorithm for general bilevel problems with blackbox functions, which optimizes both upper- and lower-level problems simultaneously, without the repeated lower-level optimization required by existing methods. BILBO samples from confidence-bounds based trusted sets, which bounds the suboptimality on the lower level. Moreover, BILBO selects only one function query per iteration, where the function query selection strategy incorporates the uncertainty of estimated lower-level solutions and includes a conditional reassignment of the query to encourage exploration of the lower-level objective. The performance of BILBO is theoretically guaranteed with a sublinear regret bound for commonly used kernels and is empirically evaluated on several synthetic and real-world problems.

BILBO: BILevel Bayesian Optimization
Ruth Wan Theng Chew
Quoe Phong Nguyen?
Bryan Kian Hsiang Low
Abstract
soluriems (x)
aolelaioon [x
Bilevel optimization is characterized by a two- level optimization structure, where the upper- level problem is constrained by optimal lower- level solutions, and such structures are preva- lent in real-world problems. The constraint by optimal lower-level solutions poses significant challenges, especially noisy, constrained, and derivative-free settings, as repeating lower-level optimizations is sample inefficient and predicted lever-level solutions may be suboptimal. We present BlLevel Bayesian Optimization (BILBO), novel Bayesian optimization algorithm for gen- eral bilevel problems with blackbox functions, which optimizes both upper- and lower-level prob- lems simultaneously, without the repeated lower- level optimization required by existing methods. BILBO samples from confidence-bounds based trusted sets, which bounds the suboptimality on the lower level. Moreover, BILBO selects only one function query per iteration, where the func- tion query selection strategy incorporates the un- certainty of estimated lower-level solutions and includes a conditional reassignment of the query to encourage exploration of the lower-level objec- tive. The performance of BILBO is theoretically guaranteed with sublinear regret bound for com- monly used kernels and is empirically evaluated on several synthetic and real-world problems.
telovel solts Ix x non-slievel soin
Upper-level objective
(b) Lower-level objective
Example of bilevel optimization with upper-level variable x and lower-level variable z. The bilevel solution (blue cross) is constrained by lower-level (LL) solutions (yellow line) and differs from the non-bilevel solution (red cross).
Figure I:
chical structures, enabling analysis of these interdependent problems. A simple example of bilevel optimization is in Figure 1. Applications of bilevel optimization range from machine learning (c.g.. hyperparameter optimization, meta- learning) to economic problems (e.g.. pricing strategies, toll setting) (Beck & Schmidt, 2021). In energy management, energy providers determine optimal pricing strategies for electricity (upper level) while consumers optimize their elec- tricity demands based on the pricing (lower level). Similarly, in investment, brokers set fees on different asset classes to maximize their revenues (upper level), while investors op- timize their portfolios for expected returns and risk (lower level). Bilevel optimization has been applied in both cases (Shu et al., 2018; Leal et al., 2020), typically using a nested framework with linear solvers at the lower level. This ap- proach may limit practical effectiveness but it is due to the inherent complexity of bilevel optimization. Even with only linear constraints and objective functions, the set of feasible solutions can be non-convex and non-continuous (Klein- al., 2021). Lower-level solutions that are e-feasible w.r.t. non-linear constraints may also lead to solution arbi- trarily far from the bilevel solution (Beck et al., 2023).
1. Introduction
Many real-world problems involve hierarchical decision- making with two levels of optimization. Decisions made at the upper level affect lower-level optimization, while opti- mal lever-level solutions constrain decisions at the upper level. Bilevel optimization effectively models such hierar-
'Institute of Data Science, National University of Singapore, Singapore Amazon, Australia Department of Computer Science, National University Singapore, Singapore. Correspondence to: Ruth Wan Theng Chew <ruthchew @ edu.sgd
Classical approaches (Bard & Falk, 1982; Bard & Moore, 1990) rely on simplifying linear or convex assumptions. More recently, meta-modeling methods employ surrogate models, such as BLEAQ (Sinha et al., 2013) which uses
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

BILBO: BILevel Bayesian Optimization
quadratic approximations map upper-level points lower- level solutions. We focus meta-modeling methods over gradient-based ones to tackle general bilevel problems which may contain noisy observations, derivative-free func- tions at both levels, constraints and discrete variables.
gradient information estimate or refine lower-level so- lutions, making them unsuitable for derivative-free bilevel problems. Fu et al. (2024) provided theoretical guarantees for a nested bilevel framework with stochastic gradient de- scent at the lower level and BO at the upper level. The reliance on lower-level gradients means the analysis does not extend to general derivative-free bilevel problems as well. In contrast, our proposed method capable of han- dling blackbox, derivative-free bilevel problems, and our theoretical analysis is applicable to these settings.
Bayesian optimization (BO), a popular meta-modeling method, has been employed in a nested framework for bilevel optimization (Kieffer et al., 2017). The nested frame- work optimizes the upper level via BO while separately optimizing the lower level at each upper-level query point. However, these repeated lower-level optimizations are sam- ple inefficient and often assume the presence of gradients.
An exception to the nested framework is very recent paral- lel work by Ekmekcioglu et al. (2024) on arXiv. However, it has no theoretical guarantees and cannot handle constraints, unlike our proposed algorithm.
Contributions. We propose BlLevel Bayesian Optimization (BILBO), a novel BO algorithm for general bilevel problems with blackbox functions and constraints, where both levels optimized simultaneously unlike existing nested bilevel BO frameworks. This adds new complexities, such as the potential lower-level suboptimality of the query and the uncertainty of estimated lower-level solutions. To tackle these challenges, we introduce key components of BILBO:
Constrained Bayesian optimization. Several constrained BO algorithms have been proposed (Gardner et al., 2014; Gelbart et al., 2014; Hernández-Lobate et al., 2016; Eriks- son & Poloczek, 2021; Takeno et al., 2022). In particular, Xu et al. (2023) and Nguyen et al. (2023) both introduced confidence-bowe bound based optimistic estimations of the feasi- ble set, with the former providing an infeasibility declaration scheme and the latter including a function query strategy for decoupled settings. These feasible set estimations guide sampling toward probable feasible points, improving sample efficiency. Compared to constrained optimization, bilevel op- timization presents additional challenges due to the need to optimize a separate lower-level problem, where the optimal solutions are unknown and often estimated suboptimally.
Confidence-bounte based trusted sets reduce search space with theoretical guarantees. In particular, sam- pling our trusted set of lower-level solutions bounds lower-level objective regret, effectively bounding lower-level suboptimality for upper-level optimization.
Function query strategy that includes the uncertainty of the estimated lower-level solution and a conditional re- assigmment of the query point for more effective lower- level objective evaluation. This balances exploiting estimated lower-level solutions with exploring to refine these estimates. We show that our strategy leads to instantaneous regret bound on the query.
Comparison to other optimization problems. While some optimization problems, such robust optimization (Bo- gunovic et al., 2018; Kirschner et al., 2020) and compos- ite objectives optimization (Astudillo & Frazier, 2019; Li & Scarlett, 2024), respectively involve an additional ran- dom variable and composite objective function, they re- main single-level problems. In contrast, bilevel optimiza- tion involves two-level hierarchical structure, where the upper-level is constrained by lower-level solutions, making it fundamentally different from these other settings.
We further show that BILBO has sublinear cumulative and simple regret bounds for commonly used kernels, and demonstrate its effectiveness empirically on several syn- thetic and real-world problems. The code is provided in https: / / gi thub. com/ chwwwt/bil bo/, and no- tation table is in Appendix A.
3. Preliminaries
Bilevel optimization. Let F and f, respectively be the upper- and lower-level black-box objective function, where F X x Z - IR. Let Cup- Cia. respectively be the set of upper- and lower-level black-box constraints where X x 2 - RR Vc E Cup UCI.. The upper-level variable is denoted x E X' and lower-level variable as z E Z, where X' C Rdx and Z C IR are assumed to be finite. We consider a general bilevel optimization problem with constraints as
2. Related Work
Bilevel Bayesian optimization. Most existing bilevel Bayesian optimization methods, as mentioned in the in- troduction, apply BO only to the upper-level problem and rely on repeated lower-level optimizations at each upper- level query (Kieffer et al., 2017; Islam et al., 2018; Wang et al., 2021). Dogan & Prestwich (2023) introduced an ac- quisition function that conditions on lower-level solutions during upper-level optimization for information flow be- tween both levels. However, these nested methods require
max xEXxxE((x)
F(x,2)
(3.1)
S.t.
C(x,z) z) 2 0, VC E Cup,
(3.2)
2

---

BILBO: BILevel Bayesian Optimization
where P(x) is the set of optimal lower-level solutions the upper-level variable x,
instantaneous objective regrets are defined, respectively, as TF(X;, Ze) _ max(0, F(x", z²) Fxx,, 2i)),
(3.5)
P(x)= A (arg max c(x,z) x) 2 0, Vc Co (3.3)
Ty (x,,,, 2x) _ f(x,, 2 (xx)) [xe, zz),
(3.6)
and the instantaneous constraint regrets as
Let (x", x²) denote the optimal bilevel solution, and
Ve E Cup U re(xt, 2x) - max(0, -c(x,, ze)). (3.7)
(x, z² (x)) denote the optimal lower-level solution w.r.t. x, where z" - (xx).. We define the set of functions F A {F.S) U Cup U Go- At each step 1 2 1, we se- lect a query point (xe, z4) and obtain noisy observations yn (x,, 2,)= _ l((x,; ze) + where e ~ ((0,oo)) Ah E F. In a decoupled setting, a function query h E iss selected and only yh, (x,, 24) is observed. Observations mulated into Dr,,t Dh1,s-1 U (yn, (x,, 2 and Dn,o is the set of initial observations for function h. (x,, 2x) is commonly used to estimate the optimal solution (x",z").
Note that Te is usually known as constraint violation and we have incorporated them into the bilevel regret for a more representative estimate of the optimality of a point. An algo- rithm that is no-regret will have all objective function regrets and constraint violations converge to O. If the constraints and objective functions have different ranges, normalization can ensure a fairer representation of the overall regret.
accu-
4. Bilevel Bayesian optimization
Gaussian process. Each function h E F is modelled with a Gaussian process (GP). Let xz be a concatenation of x and z. A GPP (mz((z) kn (xz, xz')) is specified by a mean function m2 (xz) - E[h(xz)] and covariance function my (xx))( my (xz')) (Williams & Rasmussen, 2006). At iteration i, given query inputs - and noisy observations I1,t-1, the predictive distribution for h is Gaussian: h(xz) | Yhc.-1 ~ N ((mn,e11xx)) ( More Gaussian process de- tails can be found in Appendix B.
Our method, called BILevel Bayesian Optimization (BILBO), optimizes both upper- and lower-level simulta- neously, via sampling from trusted sets and conditional reassigmment to explore the lower-level objective. We avoid the repeated lower-level optimization found in most exist- ing bilevel BO literature, as points in our trusted sets are sufficiently good for upper-level optimization directly. This is supported theoretically as we show that points in the trusted sets have upper-bounded instantancous regrets on constraints and the lower-level objective. We also introduce function query strategy based on estimated regrets, where we incorporate the uncertainty of estimated lower-level so- lutions and a conditional reassignment for exploration of the lower-level objective, to address challenges posed by the optimal lower-level solutions constraint. This results in an instantaneous regret bound on the query point, and leads a sublinear cumulative and simple regret bound for commonly used kernels. The key components are illustrated in Figure 2 and the pseudocode is in Algorithm 1.
kn xx')= - (
Bayesian optimization. Given a prior distribution P(h) and likelihood function P(Dr,,,eli) [h), the posterior distribution P(h(Dr..t) can be calculated via Bayes" theorem. The prior distribution is often represented by a GP and the likelihood function is defined by the choice of GP kernel and hyper- parameters. The posterior distribution is also a surrogate model for h. The point which maximizes an acquisition function a (xz) is selected the next point to evaluate function a at (Brochu et al., 2010; Frazier, 2018; Garnett, 2023). Popular acquisition strategies include information- theoretic ones (Hennig& & Schuler, 2012; Vernández-Looatt et al., 2014; Wang & Jegelka, 2017) and upper confidence bounds (Srinivas et al., 2010).
The trusted sets are defined in Definitions 4.3 and 4.5, and Lemmas 4.4 and 4.6 provide instantancous regret bounds on points in the trusted sets. Definition 4.7 defines the function query selection and Lemma 4.8 presents a instantaneous regret bound on the query. The cumulative regret bound is in Theorem 4.9 and the simple regret bound in Lemma 10..
Regrets. Regret is defined as the loss in reward from not se- lecting the optimal point. Instantaneous regret ra measures this loss at time 1, while cumulative regret Rt A Σt= I't is the sum of instantaneous regrets over T rounds. An algo- rithm is no-regret if lim RT /T = 0 where cumulative regret is sublinear and convergence to the optimal point is guaranteed with a large enough? T.
First, we define the confidence bounds on which we use to build the trusted sets. Functions are bounded by the confidence bounds with high probability by Corollary 4.2. Definition 4.1 (Confidence bounds). For a function h e F modelled by Gaussian process (GP), Vx E X, 2 E 2, and > 1, let the upper and lower confidence bounds of 11(x 2) be denoted, respectively. as
We define the instantaneous bilevel regret as
rt max.% (xx,) Zz), hEF
(3.4)
Un, 2) - 14h (x, 2) + 37122 Th, (x, 2);
(4.1)
(x,((x,2) z) _ 1 z) - /2 / Th (x, (4.2)
where F A (F, Cup U Cr. The upper- and lower-level
3

---

BILBO: BILevel Bayesian Optimization
Algorithm BBLBOO
original query, (6.
sotutions
estimated LL solutions 2000
Require: X, X, 2, (Dr.ohee
X
original rqueeyy (u.
X
resssigedll reudggedliuuuryy eryy 04, AiMAl
1: Update GP posterior beliefs: {(uh,0 Th,o))er
2: Update trusted sets S, Pt
// Defs. 4.3 and 4.5
3: for t +- to T do
4: if S, = 0 then
5: Declare infeasibility
end
Xx. Ze +- arg max, (x.)) (F,(x, // Eq. 4.6
(a) Query point selection
(b) Conditional reassignment
8:
h1 f- arg maxkeF (x,, (x)
I/ Def. 4.7
9:
if h4 = f then
Figure 2: Key components of BILBO, where pink shaded ar- eas represent trusted sets S nP;t (a) Query point selection
10:
2, <- arg argmax,es 2E5,, (xx) U (x,,(Xx;
Eq. 4.5
11:
if o 107f.-11xx0 (x,,, > of ff 1,,0-((x0 Zi) then
within trusted sets following Equation 4.6. (b) Conditional
12:
2t
// [q.. 4.8
reassignment following Equation 4.8, where lower-level
13:
end if
query 2, may reassigned to estimated lower-level solu-
14:
end if'
tion z, (xx) lower-level objective is selected for query.
15:
Dre,t f- Dh..t11 U (3n, (xr, 2r)
16: Update GP posterior belief: phe,e Tbe.
17: Update trusted sets S P,t // Defs. 4.3 and 4.5
where (x,,-1(xx z) and o,,--1(x, z) are the GP's poste- rior mean and standard deviation at (x, 2), and Bg & 2 [ (((6)))))))
18:
end for
Corollary 4.2. For some small ó > O, with probability at least 8, Vx E X, 2,h F, and 2
Note the trusted feasible set extends the constraint regret bounds of constrained BO methods in Xu et al. (2023) and Nguyen et al. (2023) to all points in the trusted set compared to only on the query point, so as to facilitate combination with the trusted set of optimal lower-level solutions for bilevel optimization with constraints.
2(x,z) [n,,(x,)) z), (x, z)].
This is derived from Lemmn 5.1 of Srinivas et al. (2010) by applying union bound over h E
4.1. Trusted set of optimal lower-level solutions
Next, we introduce a trusted set of feasible solutions by approximating the unknown feasible regions using the upper confidence bound and show that points in this trusted set have constraint regret bounds.
We define another trusted set approximate the unknown set of optimal lower-level solutions, using confidence bounds and estimated optimal lower-level solutions. Points in this trusted set have lower-level objective regret bounds, allowing us to quantify possible lower-level suboptimality. Definition 4.5 (Trusted set of optimal lower-level solutions). Let the trusted set of optimal lower-level solutions be
Definition 4.3 (Trusted set of feasible solutions). Let the trusted set of feasible solutions be defined
St A 2(x,2) E X E Ux,e(x,2) z) 2 O Vc E Cup U.,s (4.3) where Cup Co is the set of all constraints, and the upper confidence bound We,t is defined in Definition 4.1. For convenience, let S (x) A {z (x,z)= E S
P {xx z) S/
u 2) 2 (x, (x)), (4.4)
where Stt, A {(x,2) 2) X Z (x, 2) > Ve Go is the trusted set of feasible solutions w.r.t. lower-level constraints, and
Lemma 4.4. Let 8 E 1), with probability at least 1 - 6, v(x, E St C Cup the constraint regrets are upper bounded,
Z zx(x) e arg max (f,(x, 2), (x)
(4.5)
(x(x z) s 2/3//2 (x.))(x,z).
is the estimated optimal lower-level solution at x.
The proof is provided in Appendix C.I. Sampling from S ensures that the instantaneous constraint regret of the chosen point is upper bounded, and highly infeasible points are outside the trusted set. An empty trusted feasible set would imply an infeasible bilevel problem, and our algo- rithm would make an infeasibility declaration.
Lemma 4.6. Let E (0, 1), with probability at least 1 V(x,z) z) E Pt.. the lower-level objective regret upper bounded.
(x,( 2) (x))2,(x) 1 2x(x))
+ /2 1

---

BILBO: BILevel Bayesian Optimization
The proof is given in Appendix C.2. Sampling from Pi'' guarantees an upper-bounded soper-bounded lower-level objective regret, and points outside of the trusted set Pf are highly unlikely to be lower-level optimal.
The estimated lower-level objective regret ff (x,, 2,) has additional term, fft- (xx)), compared other regret components. This additional term increases f when the estimated lower-level solution is highly uncertain, cor- responding to the intuitive need for more frequent queries of the lower-level objective, especially since most existing bilevel BO methods rely on global optimization of the lower level.
The trusted set Pi* allows multiple lower-level solutions to correspond to an upper-level variable, effectively managing multiple lower-level solutions and noisy observations. More- over, we can handle infeasible lower-level problems as the trusted set Pt+ filters out highly probable infeasible points via the set Sh. which can eliminate upper-level points that are infeasible at the lower-level, ensuring only probable feasible solutions are considered during optimization.
Conditional reassignment of z, for lower-level objective query. When the lower-level objective function / is selected for query, we want to reduce lower-level objective regret effectively. Thus, as in Figure 2b, the lower-level variable to query, 2,, has to be reassigned on the following condition,
c-optimal lower-level solutions. In some scenarios, it may be desirable to consider e-optimal lower-level so- lutions feasible, as is common for real-world agents to operate suboptimally. This allows us to account for practical limitations where perfect lower-level optimiza- tion may not be achievable, for example, due to noise or the cost of querying. In this case, we can relax the condition in Definition 4.5 to allow e-optimal lower- level solutions to remain in the trusted set by defining Pi A {(x,2) z) | (x,,(xx2) z) + 2 (x, 2, (x)), and ex- tending the regret bound in Lemma 4.6 to 2),(x,2) I
If h1 = f and f (x,, Z, (xx)) 2 of,t- (x,, Zt); Z1 <- (xx).
(4.8)
Without reassignment, ff will only be queried (x,, 2,) and the term ofa- (x,, z, (xx)) would remain large even after repeated queries to f. This reassignment encourages explo- ration of the lower-level objective, replacing the repeated lower-level optimization required by existing methods.
Lemma 4.8. Let 5 E (0, 1), with probability at least 1 - 5, following the function query selection in Definition 4.7 and reassignment of query point in Equation 4.8, the instanta- neous regret for the query point (x1, 2i) at time t 2 is upper bounded by.
e + (x) f---1(x,
(x)) + 28, o 0
4.2. Query point selection
We reduce the search space to SF+ n P.t. Points in this search space have upper-bounded instantaneous regrets on constraints and lower-level objective with high probabil- ity, according to Lemmas 4.4 and 4.6. The query point at time t is sampled from the reduced search space and cho- sen w.r.t. the upper confidence bound of the upper-level objective u, shown in Figure 2a and defined as,
S /8 max 1 Zt). REF
The proof is in Appendix C.3. By Lemma C.4, we also see maxker (x,, 2,) 2 Tr. Thus, maXker Fh, (x,, 2,) is the upper regret bound at query point (x,,z)), where a large estimated regret Fa., ze) suggests that function affects it significantly. Since Th.t comprises of a,e-1 selecting the arg m Fh, in Definition 4.7 can also be seen as selecting the most uncertain function at (x,, z,) to query.
X1, 21 A arg max (xx))st not (F,((x,2)
(4.6)
4.3. Function query
4.4. Regret bound
In the decoupled case, function query he is selected at each timestep é for evaluation. We follow the function query
The cumulative regret bound of Algorithm is shown in Theorem 4.9 and proven in Appendix C.4 using Lemma 4.8.
selection in Definition 4.7, and Lemma 4.8 provides an instantaneous regret bound on the query 2.).
Theorem 4.9. Let 8 E (0,1) and B. P
Definition 4.7 (Function query). Let the function query h selected at each timestep f. be
2 [==]] /65). With probability of at least - 8, Algorithm has a cumulative regret bound of
hg
A arg max (x,, Z,), hEF
(4.7)
RT S
|4T Flis max C.TITT DEF
where F A (F. Cup U Cr- The estimated regrets are defined using confidence intervals and 2; from Equation 4.5,
where On A 8/log(1 + or and WhT is the maxi- mum information gain from noisy observations of h at (xe, 2:), VL E [T].
Fx,,(Xe, ze) 2 /3 ow.--1(x,, 2z), Wh' E F/U}, (x), 21) A 1x,
/2 0 1 Ze (x,)) + 2,3/ 12
The regret bound is related to the maximum information gain across all functions in F. Our regret bound has a larger
0 10/01111111000 (x:,
5

---

BILBO: BILevel Bayesian Optimization
constant than the regret bound for constrained Bayesian opti- mization in Nguyen et al. (2023), the lower-level objective regret has larger upper bound than constraint regret. This highlights the increased difficulties of optimizing bilevel problems, where suboptimal lower-level solutions can hin- der upper-level optimization, making bilevel optimization more challenging than standard constrained optimization.
discretize the search space using uniformly-spaced grid to facilitate representation of trusted sets. BILBO queries only one function per iteration, while TrudtedRand queries all function at each iteration. For comparison, the estimator is chosen as arg max (xa) (r,,(X, 2) for BILBO and Taud and arg maXxex (x;((x) for Nested. Addi- tional implementation details are in Appendix D.2.
The cumulative regret bound of BILBO sublinear as 7 is sublinear for common kernels including Squared Expo- nential and Matérn kernels (Srinivas et al., 2010). The sublinear cumulative regret guarantees convergence to the optimal solution as RT/ /T + 0 as T + oo.
Results are averaged over 5 runs and performance is com- pared by examining the instantaneous regret against query count with 95% confidence intervals. The instantancous regret this section is calculated as the sum of each func- tion's instantaneous regret Qher (hh,)) provide intuitive comparison across different methods. Initial observations are included in the number of queries, indicated by a small gap in the regret plots before estimations begin.
Lemma 40 gives a simple regret bound for the estimator,
ST, 2T - arg (x. ((
min
max GEF
The (x,, zt)-
(4.9)
5.1. Synthetic problems
Lemma 4.10. Let 5 E (0, 1), with probubility at least 1 8, T 2 L, and 3T 2 2 (0 (Kx, 2r), defined in Equation 4.9, has a simple regret bound of
The synthetic problems were selected to cover a variety of scenarios, including conflicting interactions, convex or multimodal functions, and active constraints.
the estimator
BraninHoo-GGddsteeePiicc has the Branin-Hoo function as upper-level objective F and the Goldstein function as the lower-level objective (Picheny et al., 2013). Both functions are non-convex and multimodal. The dimensions dx and dz are both 1, which facilitates visualization of the models and queries. Both dimensions were discretized into 100 points. The Branin-Hoo function has 3 optimal points, but there is only optimal bilevel solution when constrained by lower-level Goldstein Price optimal solutions.
FT S /4 max C.T.T/T. hEF
This follows the simple regret of 2x) is upper bounded by the average regret bound in Lemma 4.8 across timesteps. The detailed proof is in Appendix C.5.
5. Experiments
BILBO outperforms the other two methods by substantial margin, as seen in Figure 4a where it converges to the opti- mal bilevel solution within 150 queries. Nested and Truste- dRand converge equally slowly. For Nested, the predicted lower-level solutions may be suboptimal because the lower- level solver cannot handle multimodal functions and noisy observations effectively. For TrustedRand, random queries might have led to uninformative points being sampled. The challenging multimodal characteristic of the functions also means that sampling in informative areas is integral for this problem, which BILBO successfully manages to do.
We evaluate the performance of BILBO on synthetic and 2 real-world problems. We introduce 2 baselines for compari- son: "TrustedRand" and "Nested". TrustedRand randomly samples query points from trusted sets to assess the trusted set's contribution to the overall performance of BILBO. Nested optimizes the upper- and lower-level problems sep- arately and serves as a baseline for nested BO approaches like in Kieffer et al. (2017), approximating lower-level gra- dients. More details on TrustedRand and Nested are in Appendix D.I. Note Nested cannot handle constraints and is not compared in experiments with constraints (SMD12 and Chemical). The very recent parallel work by Ekmek- cioglu et al. (2024) is not compared as code is not provided.
Figures 3a and 3b show the upper- and lower-level objective function respectively, with optimal lower-level solutions (yellow dots), and Figures 3c 3f show BILBO's inner workings BILBO converged to the optimal solution, and the surrogate models effectively captured the overall landscape of both functions in Figures 3c and 3d, where predicted lower-level solutions (yellow crosses) are close to optimal lower-level solutions, especially in regions where upper- level objective value is high. Queries selected over iterations from the upper- and lower-level objective functions are in Figures 3e and 3f respectively, with darker colors indicating
A Algorithms are implemented using Gpy (Gardner et al., 2018). All experiments. except Nested, are initialized with 3 observations on each function. Nested requires more ini- tial observations of lower-level functions as the upper-level objective is only evaluated at the estimated lower-level solu- tion. We allow for this to enable comparisons, which also highlights the sample inefficiency of nested methods. All observations are noisy with on = 0.01, and outputs are normalized to have mean and standard deviation 1. We
6

---

BILBO: BILevel Bayesian Optimization
optimal pt
pred pt
optimal LL
predicted LL
sample points (darker means earlier iterations)
(a)
F
(b) f
(c) PFT
(d) PTT
(e) F queries
(1) ʃ queries
Figure 3: ConninnHoo-GoldsteiinPPiii experiment details. LL refers to lower-level. (a) Upper-level objective, Branin-Hoo.
(b) Lower-level objective, Goldstein-Prins Price. (c) BILBOO's upper-level estimate. (d) BILBO's lower-level estimate. (e-f) BILBO's iterative queries.
10
10
10
10*
Instebbrenuu regiet
Instanterenn rntennarreuss..oo regret
Prstantarenure regret
10
Nested
3000
Insfentarerus
18
10-1
10-4
BILBO
BILIO
Tdaad
20
TustedRand
BILBO
Nested
Nested
10"2
TrustedRand
50
100
150
200
250
300
0
50
100
150
200
250
50
100
150
200
250
0
50
100
150
200
250
300
number of quarioe
number of quer
number of queris
number of queries
(a) BraninHoo-Colldseinnnin
(b) SMD2
(c) SMD6
(d) SMD12
Figure 4: Instantaneous regrets (log-scale) over number of queries, averaged over 5 runs, for synthetic experiments.
samples from earlier iterations, and they mostly clustered around two probable optimal solutions. BILBO sampled the objective functions the top-left region until it ascertained the absence of optimal solutions and converged on the actual optimal solution, demonstrating its effectiveness.
at the start, its rate of decrease diminishes over time, likely because random queries are initially informative but become less effective as the process continues. For SMD6, BILBO has the smallest regret after around 250 steps. Nested is unable handle multiple lower-level optimal solutions, as it predicts only one lower-level solution for each upper-level point. In comparison, the trusted sets allow multiple optimal lower-level estimates for both BILBO and TrustedRand. For SMD12, BILBO converges faster than TrustedRand. With functions in the SMD12 problem, the decoupled setting becomes more crucial for sample efficiency. The faster convergence of BILBO demonstrates the effectiveness of our function query strategy in selecting more informative functions to query. The presence of active constraints did not appear to pose any difficulties for BILBO as well.
SMD2, SMD6, and SMD12 are adapted from the SMD suite of test problems for bilevel optimization (Sinha et al., 2014). Details of implementation are Appendix D.3. The input dimension of the test problems being 2 and dz being The difficulty increases in the order of SMD2, SMD6, SMD12. SMD2 has convex functions and confficting interactions, where improving the lower-level estimate worsens the upper-level objective value. This re- quires the algorithm to predict lower-level optimal solutions accurately to obtain the optimal bilevel solution. SMD6 also has convex functions and conflicting interactions, but with multiple lower-level optimal solutions each upper-level point (i.e.. convex valley). An algorithm must concurrently estimate multiple lower-level optimal solutions and identify the point that optimizes the upper-level objective. Finally, SMD12 is the most challenging problem from the SMD suite, with both levels having active constraints, where the optimal solution is on the boundary the constraints. There are also multiple optimal solutions at the lower level.
5, with dx
5.2. Real-world problems
Energy. We simulated bilevel energy market problem, where energy providers bid to supply an amount of electric- ity at the upper level to maximize profits over three time periods. At lower level, they optimize their operations, considering costs, demand responses prices, and their ability meet changing demands. There are 2 upper-level variables: price and quantity of electricity to bid, and 2 lower-level variables: the ramp limit for one power plant and the maximum power output at each period for another power plant. Lower-level variables affect overall optimal
Results of the SMD experiments shown in Figures 4b to 4d. For SMD2, BILBO outperforms both TrustedRand and Nested. While TrustedRand's 'ss regret decreased quickly

---

BILBO: BILevel Bayesian Optimization
100
201
$1.30 Trustedhand Nedded
81,00 Trustedhand
20F
109
X2
22
20
10-1
x1
number of quaress
Fumber quaries
(a) Fxx, z (x))
(b) f(x', .)) (c) (x,
(d) |yr(x*,,
(e) Energy experiment
(f) Chemical experiment
Figure 5: Real-world experiments. (a-b) Functions from energy experiment and (c-d) BILBO outputs, with optimal solution
(red dot) and predicted solution (blue cross). (e-f) Regret plots in log-scale for energy and chemical experiments respectively.
dispatch of electricity and the dispatching of three power plants was simulated using PyPSA (Brown et al., 2018). We formulated the lower-level objective as a function of simula- tion outputs, to seek the lowest cost of electricity generation while incorporating penalties to reduce wear and tear or other auxiliary concerns. More details in Appendix D.4.
to produce Methyl Acetate in a reactor. Additionally, an upper-level constraint is included to ensure suitable tem- perature range for chemicals be in their correct states, There is I upper-level variable: the number of levels in the distillation column, and 3 lower-level variables: temperature of the reactor, number of heating tubes, and the diameter of heating tubes. More details are in Appendix D.5. Results are in Figure 5f where BILBO outperforms TrustedRand, highlighting the potential efficiency and effectiveness of BILBO optimizing complex industrial operations.
Figure 5e shows BILBO outperforms the other methods, with its regret decreasing the fastest. Refer to Figures Se and 5d for surrogate models learned after one run BILBO. Figures 5a and Sc, respectively, show the upper-level objec- tive F' at optimal lower-level solutions and the estimated upper-level objective μFT at estimated lower-level solu- tions. μЕт approximates F well, especially at regions with high values, and correctly predicted the optimal bilevel solution. Figures 5b and 5d, respectively, show the lower- level objective f and the estimated lower-level objective MJ, the optimal upper-level variable. At this upper-level variable, fr captures the general trend of f, where optimal points are on the right. However, the optimal lower-level solution is at a boundary with high discontinuity. The surro- gate model was unable to model this large step and predicted a suboptimal lower-level solution, resulting in an empirical asymptotic regret bound in Figure 5e, compounded by noisy observations. This may be mitigated by adding a constraint function to represent the discontinuity in the lower-level ob- jective, as BILBO has shown the capability to handle active constraints effectively in previous synthetic experiments.
Additional discussions the computational complexity and time efficiency of BILBO can be found in Appendix E.
6. Future Work
We have shown theoretically and empirically that BILBO is a regret-bounded, sample efficient algorithm for noisy, constrained, and derivative-fret bilevel optimization. A key direction for future work is improving scalability to high- dimensional spaces, which is a common challenge in BO.
We currently model upper-level objective over X' x 2, but this can be memory inefficient as many lower-level variables are suboptimal and irrelevant. A more efficient approach could involve directly modeling F'(x, z (x)). reducing the dimension of the surrogate model from dx x d2 to dx. This poses another challenge: incorporating the uncertainty associated with the optimality of the lower-level solution into the uncertainty of the upper-level objective value.
Chemical. Chemical processes in industries such as phar- maceuticals, petrochemicals, and food production often in- volve multiple stages, each requiring parameter optimiza- tion. Bilevel optimization simplifies this by dividing the overall process into smaller, more manageable problems, while still accounting for the interactions between different stages. We used COCO simulator to simulate carbonylation of Di-Methyl Ether (DME) to Methyl Acetate, adapted from the flowsheet provided by ChemSep. The upper-level prob- lem focuses on maximizing the yield of Methyl Acetate at 99.9% purity through a distillation column, which takes in reaction mixture comprising Methyl Acetate, unreacted DME, and by-products. These are outputs from the lower- level optimization, which involves carbonylation of DME
Adaptive discretization (Shekhar & Javidi, 2018) may also reduce computational complexity by reducing the effective dimension of the explored space. Discretization strategies could be integrated with trusted sets, for example concentrat- ing the discretizations within the trusted sets. Approximate surrogate models (Calandriello et al., 2019) is another pos- sible direction for scalability while preserving confidence bound estimates. The theoretical work presented in this paper could be extended to approximate surrogate models.
The representation of trusted sets will need to scale effec- tively to higher dimensions well. Possible approaches could be via sampling strategies like Latin Hypercube Sam-
8

---

BILBO: BILevel Bayesian Optimization
pling (McKay al., 2000) for efficient point representation in high-dimensional spaces using hyperrectangles rep- resent the trusted set efficiently (Eriksson et al., 2019).
for the bilevel programming problem. SIAM Journal on Scientific and Statistical Computing, 11(2):211292,, 1990.
Future work can extend our discretized implementation to continuous domains, which should be feasible with a scal- able trusted set representation. Our theoretical results can also generalize to continuous settings with minor modifica- tions to Br and additional assumptions, following Chowd- hury & Gopalan (2017).
Beck, Y. and Schmidt, M. A gentle and incomplete intro- duction to bilevel optimization. 2021.
Beck, Y., Bienstock, D., Schmidt, M., and Thürauf, J. On a computationally ill-behaved bilevel problem with a con- tinuous and nonconvex lower level. Journal of Optimiza- lion Theory and Applications, pp- 1-20, 2023.
7. Conclusion
Bogunovie, I., Scarlett. J., Jegelka, S., and Cevher, V. Ad- versarially robust optimization with Gaussian processes. Advances in neural information processing systems, 31, 2018.
We introduced BILBO, a novel bilevel BO algorithm that op- timizes the upper- and lower-levels simultaneously. BILBO samples from confidence-bound; based trusted sets bound lower-level suboptimality, and encourages lower-level explo- ration via conditional reassignment of the query, replacing the repeated lower-level optimizations required by existing methods. We show theoretically that BILBO has a sublin- car regret bound, and our experiments demonstrate empir- ically that BILBO outperforms other bilevel optimization baselines, especially in problems with many non-convex functions. BILBO is a significant step towards general bilevel solver, which will enable applications to complex real-world bilevel problems involving blackbox functions.
Brochu, E., Cora, V. M., and De Freitas, N. 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.
Brown, T., Hörsch, J., and Schlachtberger, D. PyPSA:
Python for Power System Analysis. Journal of Open Research Software, 6(4), 2018. doi: 10.5334/jors.188 188. URL https: //doi////oo.////////// org/ 5334/ jors 188.
Acknowledgments
Calandriello, D., Carratino, L., Lazaric, A., Valko, M., and Rosasco, L. Gaussian process optimization with adaptive sketching: Scalable and regret. In Conference Learning Theory, pp. 533-557 PMLR, 2019.
This research is supported by the National Research Foun- dation (NRF), Prime Minister's Office, Singapore, under its Campus for Research Excellence and Technological En- terprise (CREATE) programme. The Mens, Manus, and Machina (M3S) is an interdisciplinary research group (IRG) of the Singapore MIT Alliance for Research and Technology (SMART) centre.
ChemSep. chemsep.org. http: http::/www.w. www.scpeepepp.. org/ [Accessed 30-09-2024).
Chowdhury, S. R. and Gopalan, A. On kernelized multi-
armed bandits. International Conference on Machine Learning, pp. 844-853. PMLR, 2017.
Impact Statement
COCO. COCO the CAPE-OPEN CAPE-OPEN
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
simulator cocosimulator.org. https: //ww///wwww//./o/////////../// cocos i www.amm...rooooooooooooooo [Accessed 30-09-2024).
Dogan, V. and Prestwich, S. Bilevel optimization by condi- tional Bayesian optimization. In International Conference on Machine Learning, Optimization, and Data Science, pp. 243-258. Springer, 2023.
References
Astudillo, R. and Frazier, P. Bayesian optimization of com- posite functions. In International Conference on Machine Learning, pp. 354 -63. PMLR, 2019.
Ekmekcioglu, O., Aydin, N., and Branke, Bayesian optimization of bilevel problems. arXiv preprint 1rXiv:2412.185144 2024.
Bard, J. F. and Falk, J. E. An explicit solution to the multi- level programming problem. Computers & Operations Research, 91):77-100, 1982.
Eriksson, D. and Poloczek, M. Scalable constrained bayesian optimization. In International conference on artificial intelligence and statistics, pp. 730-738, PMLR, 2021.
Bard, J. F. and Moore, J. T. branch and bound algorithm

---

BILBO: BILevel Bayesian Optimization
Briksson, D., Pearce, M., Gardner, J., Tumnrr R. D., and Poloczek, M. Scalable global optimization via local Bayesian optimization. Advances in neural information processing systems, 32, 2019.
Kleinert, T., Labbé, M., Ljubić, I., and Schmidt, M. A vey on mixed-integer programming techniques in bilevel optimization. EURO Journal Computational Opti- mization, 9:100007, 2021.
Frazier, I. A tutorial on bayesian optimization. arXiv preprint arXiv: 02011.0..11.... 2018.
Leal, M., Ponce, D., and Puerto, J. Portfolio problems with two levels pacision-mmkers Optimal portfolio selection with pricing decisions on transaction costs. European Journal of Operational Research, 284(2:712--277, 2020.
Fu. S., He. F., Tian, X., and Tao, D. Convergence of Bayesian bilevel optimization. In The Twelfth Interna- tional Conference on Learning Representations, 2024.
Li, Z. and Scarlett, J. Regret bounds for noise-free cascaded kerneiized bandits. Transactions on Machine Learning Research, 2024.
Gardner, J., Pleiss, G., Weinberger, K. Q., Bindel, D., and Wilson, A. G. Gpytorch: Blackbox matrix-matrix Gaus- sian process inference with gpu acceleration. Advances in neural information processing systems, 31, 2018.
McKay, M. D., Beckman, R. J., and Conover, W. J.
comparison of three methods for selecting values of input variables the analysis of output from a computer code. Technometrics, 42(1):55-61, 2000.
Gardner, R., Kusner, M. J., Xu, Z. E., Weinberger, K. Q., and Cunningham, J. P. Bayesian optimization with in- equality constraints. In ICML, volume 2014, pp. 937-945, 2014.
Nguyen, Q. P., Chew, W. R., Song, L.,, Low, B. K. H., and Jaillet, P. Optimistic Bayesian optimization with unknown constraints. In The Twelfth International Con- ference on Learning Representations, 2023.
Garnett, Bayesian optimization. Cambridge University Press, 2023.
Gelbart, M. A., Snock, J., and Adams, R. P. Bayesian optimization with unknown constraints. In Uncertainty in Artificial Intelligence, 2014.
Picheny, V., Wagner, T., and Ginsbourger, D. A bench- mark of kriging-based infill criteria for noisy optimiza- tion. Structural and multidisciplinary optimization, 48: 607-626, 2013.
Hennig, P. and Schuler, J. Entropy search for information- efficient global optimization. Journal of Machine Learn- ing Research, 13(6). 2012.
Shekhar, S. and Javidi, T. Gaussian process bandits with adaptive discretization. Electronic journal of statistics, 12(2), 2018
Hernández-Lobato J. M.. Hoffman, M. W., and Ghahra- mani, Z. Predictive entropy search for efficient global optimization of black-box functions. Advances in neural information processing systems, 27, 2014.
Shu, J., Guan, R., Wu, L., and Han, B. A bi-level approach for determining optimal dynamic retail electricity pric- ing of large industrial eustomers. IEEE Transactions on Smart Grid, 10(2):2267-2217 2018.
Hernández-Lobato, J. M., Gelbart, M. A., Adams, R. P., Hoffman, M. W., and Ghahramani, Z. general framework for constrained Bayesian optimization using information-basee search. Journal of Machine Learning Research, 17(160): 1-53, 2016.
Sinha, A., Malo, P., and Deb, K. Efficient evolutionary algorithm for single-objective bilevel optimization. arXiv preprint arXiv: 2013.
Sinha, A., Malo, P., and Deb, Test problem construction for single-objective bilevel optimization. Evolutionary computation, 2293):439-477, 2014.
Islam, M. M., Singh, H. K., and Ray, Efficient global op- timization for solving computationally expensive bilevel optimization problems. In 2018 IEEE congress on evolu- fionary computation (CEC), pp. 1-8. IEEE, 2018.
Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. Gaussian process optimization in the bandit setting: No regret and experimental design. In International Confer- ence on Machine Learning, 2010.
Kieffer, E., Danoy, G., Bouvry, P., and Nagih, A. Bayesian optimization approach general bi-level problems. Proceedings of the Genetic and Evolutionary Computa- tion Conference Companion, pp. 1614-1621, 2017.
Takeno, S., Tamura, T., Shitara, K., and Karasuyama, M. Sequential and parallel constrained max-value entropy search via information lower bound. International Con- ference on Machine Learning, pp. 20960-20986 PMLR, 2022.
Kirschner, J., Bogunovic, I., Jegelka, S., and Krause, A. Distributionally robust Bayesian optimization. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 2174-2184 PMLR, R, 2020.
10

---

BILBO: BILevel Bayesian Optimization
Vakili, S., Khezeli, K., and Picheny, V. On information gain and regret bounds in Gaussian process bandits. In International Conference Artificial Intelligence and Statistics, pp. 82-90. PMLR, 2021.
Wang, B., Singh, H. K., and Ray, T. Comparing expected improvement and kriging believer for expensive bilevel optimization. In 2021 IEEE Congress Evolutionary Computation (CEC), Pp. 1642. IEEE, 2021.
Wang, Z. and Jegelka, Max-value entropy search for effi- cient Bayesian optimization. In International Conference on Machine Learning, pp. 3627-3635. PMLR, 2017.
Williams, C. K. and Rasmussen, C. E. Gaussian processes for machine learning, volume MIT press Cambridge, MA, 2006.
Xu, W., Jiang, Y., Svetozarevic, B., and Jones, C. Con- strained efficient global optimization of expensive black- box functions. In International Conference on Machine Learning, pp. 38485-38498. PMLR, 2023.

---

BILBO: BILevel Bayesian Optimization
A. Table of Notations
Bilevel definitions
Upper-level
Lower-level
x
Upper-level variable
2
Lower-level variable
X
Domain x
Domain
dx
Dimension
d2
Dimension of
F
Upper-level objective function
f
Lower-level objective function
Cup
Set of upper-level constraint functions
Go
Set of lower-level constraint functions
X
Selected upper-level variable to query at time /
Zt
Selected lower-level variable to query at time
Estimated optimal upper-level variable at time T
2t
Estimated optimal lower-level variable time T
F
Set of functions in bilevel problem {F, Cup U Arbitrary function in JF
(x, z)
GP posterior mean (x, z) for function h at time t
(x,()
GP posterior standard deviation (x, 2) for function h time
rx(x,2) z)
Instantaneous regret of function h at (x,
Instantaneous bilevel regret at time t on query point (X,, zi)
Rr
Cumulative regret at time
rr
Simple bilevel regret at time T based on (Se; 2e)
BILBO notations
(x, z)
Upper confidence bound function h at (x, z) (Defn. 4.1)
(x,( z)
Lower confidence bound of function h at (x, z) (Defn. 4.1)
St
Trusted set of feasible solutions (Defn. 4.3)
Stt,t
Trusted set of feasible solutions w.r.t. only lower-level constraints (Defn. 4.5)
ptt
Trusted set of optimal lower-level solutions (Defn. 4.5)
zx(x)
Estimated optimal lower-level solution at x at timestep (Defn. 4.5)
h
Selected function query (Defn. 4.7)
Fhat
Estimated regret for function h (Defn. 4.7)
12

---

BILBO: BILevel Bayesian Optimization
B. More preliminaries details
B.1. Closed-form posteriors Gaussian Processes
For a GP defined as GP (mPa(mmmx)) ky (xz, xz')) for a function The closed-form posterior mean is ph,t (xz) -
mi (xz) + ki,z-((xz)) (xz) (Ki,t-1 + + mi,--1) and variance hh (xz) - ky (xz, - k [ +
I²I) k h111 where m
mm (x, z) X (xx) (xz,, xx') bex' Ex and K -
[Ki xz, xz 22))] Ex,x
B.2. Maximum information gain
Maximum information gain, Th,t on function h, where d a dx + dz and T(h) contains the timesteps when function was selected for query, from Vakili al. (2021):
Squared Exponential kernel: Ollog" d11 (T(h)))
Matérn kernels with 112 O(T auta log 20-4 (T))))
C. Proofs
C.1. Proof of Lemma 4.4
Proof. Vc E Cup Cts (x, z) E S
(x 2) A max(0, -c(x, 2))
from Equation 3.7
s max -le, (x,
from Corollary 4.2
max(0. (0, Ue,t (x, 2) l,,r (x,
from (x, z) S
$ 2/ de,t-1 (x,,
from Definition 4.1
C.2. Proof of Lemma 4.6 Lemma C.1. Vx E (x (x,z) P,,},
(x,(xx,2(( 2 Ux,,(x, (x)),
(C.1)
where (x(x) A arg max sest (x) (x,r(x 2) is the estimated optimal lower-level solution at x, and x² (x) is the actual optimal lower-level solution at x.
Proof. By definition of (x), v(x, z) E S/ (x,,(x, 2x(x)) 2 (x,,
Let St A {(x, z) c(x z) Vc E C be the unknown set of feasible solutions w.r.t lower-level constraints, Then, (x, 2" (x))"(x)) S because (x, x" (x)) E Spo by definition and Sio St from Corollary 4.2.
Finally, by Definition 4.5 of p,t, P.+ C S
Main proof for instantaneous regret bound on f in Lemma 4.6.
Proof. v(x, 2) P...
(x, z) = f(x,22 z" (x)) f(x, z)
from Equation 3.6
S (x 2 2'(x)) 1x,) < (x, (x)) (5.1(x,2) 2).
from Corollary 4.2
from Lemma C.
13

---

BILBO: BILevel Bayesian Optimization
For (x)).
Tf,(x,2) z) S (,,,((x, Ze (x)) - 1f,1(x, (x))
=2 0s (x, (x())
from Definition 4.1
and for z # (x)).
(x, S (x (x)) 1,,((,, z)
I ( 2x(x)) u/,1(x, 2) + -/, 01,0-1(x.2))
from Definition 4.1
S Uf (x(x) (x, 2x(x)) 2,8 f 2)
from (x.z) E P,
28: fft-1 (x,
1
from Definition 4.1
Combining both cases, we get the instantaneous regret for lower-level objective function as
(x, < 1xx2,(x)28 (x, (3. + 23 o. (x,,
C.3. Proof of Lemma 4.8
Lemma C.2.
(x*,2) npt,
where (x", ,2") is the optimal bilevel solution.
Proof. Let the unknown feasible set be a f(x, z) c(xx 2 0 Vo E Cup U Since (x', z²) E by definition and C S by Corollary 4.2, have (x", x²) E STT
Let unknown feasible set w.r.t lower-level constraints be Soo {(xx z) c(x, 2 0 Ve E Go). Similarly, have (x",z) z²) Sjo S S Since (x, z²) 2 f(x",""xxxxx z²) 2 f(x" 2x(x)) 2 11,1(x", (xx))),, we have (x'zz)) P,t.
(x",z") E St and (x", E Pt = (x",2") E et npt
Lemma C.3. For some small 8 0, with probability least 5, the instantaneous upper-level objective regret is upper bounded the query point,
rr(x,, 2,) < / 1
Proof.
TF Xxx 21) max F(x", - F(x,, 2z)) max(0, u (x", x²) - F1.1 (x1, 2c)) (F,((x, 2) (x,, zt)
from Equation 3.5
from Corollary 4.2
max (x.2)es] npf
from Lemma C.2
-F 2i) 1F, zz)
from xx, 2, A arg max s7 npt U.F.t
-23 2 0
from Definition 4.1
Lemma C.4. Given the estimated regret of the selected function query hy at the query point by Definition 4.7, the instantaneous regret T2 is upper bounded,
Tt. S (xa, 24).
14

---

BILBO: BILevel Bayesian Optimization
Proof. Given Definition 4.7, Lemma C.3, Lemma 4.4, and Lemma 4.6, vh F, we that Fh (x,, 21) 2 rn (x(x; 21). Then,
Ft
_ max (x,; ze)
from Equation 3.4
keF
S max Th, (Xt, 2r) hef
Fhi, (x,, 21)-
Main proof for instantaneous regret bound in Lemma 4.8
Proof. By Lemma C.4, if h1 = S.
S F,,e(,, Zt)
= (xx 2 11 (x(x)) + 23 1 2i)
from Definition 4.7
S 48 max( (x,, 2, (xx)) , (x,
f2- = 2 (x, 2,),
where the last line holds because we reassign 2, (x(xx) if 1f 2 01,-1((x, 21) as in Equation 4.8.
Else if h4 F/(f).
Tt S (Xi, 2t)
2/ Th1, (x,,
S </3//2 (xt, Z1).
Combining, we obtain
S 4/3,/2 oh 1 (x1, 21))
< 43 1/2 max Th, r-1 (Xe,, Zz). hET
C.4. Proof of Theorem 4.9 Proof. From Lemma 4.8 and by Cauchy-Schward inequality, we derive the cumulative regret
T
R$
< T
2
t=1
T Σ
163 max oh (Xt, 24) hEFF
1=1
< 4T
Σ
40 10 (x,, 2t)
hEF (ET(K)
< 4T Σ CHTITI())
hEF
< 4T Σ CHTITTT
hEF
< 47 max CAM.TY hEFF
15

---

BILBO: BILevel Bayesian Optimization
experiment
length scale prior
dx
dz
discrete points per dimension
PraninHoo+Collssciniiice
0.2
100
SMD2
0.7
2
25
SMD6
0.2
2
25
SMD12
0.4
2
16
Energy
0,4
2
2
15
Chemical
0.8
1
10
Table Experiment parameters
where Th) contains the timesteps where function h was queried, so (T()) S Yr, and
Rr S AT
FT Br max CA ChTITT
bEF
where Cд e lo +0 o and "h. is the maximum information gain from noisy observations of h at (x,, 2.), V E [T]. The proof methodology follows Srinivas al. (2010).
C.5. Proof of Lemma 4.10
Proof.
rT S
min
max Th, (x,, 2t) heF
from Equation 4.9 and Lemma C.4
(1x
max (Xt, zi)
1
max Th, 1 21) //
from Appendix C.3
T
hef
V
/4 BT max CITATT/T.
from Appendix C.4
KEF
D. Experiment details
D.1. Baseline details
TrustedRand implements a vanilla variant the trusted sets St and Pi+,, where mean y4 is used instead of upper confidence bound u. Query points are then randomly sampled from the trusted set variants.
Nested uses the sequential least squares programming (SLSQP) optimizer for lower-level optimization, following Kieffer et al. (2017) and Dogan& & Prestwich (2023), and BO with upper confidence bound acquisition function (Srinivas et al., 2010) at the upper level. The lower-level problem is solved to convergence at each upper-level query. Note that gradients are approximated for SLSQP, which can only work on continuous functions.
D.2. Implementation details
GP with Matérn 5/2 kernel was used, and the GP hyperparameters were automatically tuned at each iteration using maximum likelihood estimation on the past observations. The hyperparameters include length scale and prior mean. The prior mean initialized to 0 for all experiments since the output already normalized. The initial length scale and other parameters for each experiment are set according to Table 1. For SMD2, energy, and chemical experiment, we sampled from P. e ((x, (x)) Vx X) instead of P as it was empirically found be better.
16

---

BILBO: BILevel Bayesian Optimization
D.3. Edits to SMD2, SMD6, SMD12
The selected SMD problems were adapted the imput ranges from 0 to and the outputs have mean and standard deviation of 1, for parameters p 1, 1, 2, while ensuring that their characteristics and optimal points remain the same. The upper- and lower-level objective functions of SMD each have 3 components. The following only records edits to the original SMD problems. Refer to Sinha et al. (2014) for the original SMD problems.
Let x = [uu,, Sm2] and z = [iz,, R12). x, z E [0, 1]".
SMD2. To bound the output for the given domain, we set
F3 -
(1
Σ (1l,2 - log (0.9 o/s 0.01))
log(0.99 2/2 0.01)² f3 u2
where uu _ (Iu1 + 1)/3, 222
- (2u2 + 5)/6, 2.1 & (œ11 + 1)/3, and 212 a xm/e..
SMD6. The different functions have imbalanced ranges. To balance the different functions in f, we set
fi _ ft/d
f2 f2/d²
fs - fa/d,
where d = 3, and use f fs as the lower-level objective function. 2.6 - (x6 + 1)/3, for xs E (ruI, on, 112).
SMD12. To bound the outputs in the domain, we set
F3 A
(ri2 - 2)² +
tanh [ - -E (x/22 tanh x/2)
1=1
f3 4
(1'2 - tanh x/22²
We also edited the first upper level constraint to 2:y2 tanh 4/2 2 1, Vi {1, r), it becomes an active constraint.
One of the lower level constraint was also edited bound its output range: 2/ normalize 2.1 A (I.. 5)/1/5 2.2 & (I,2 1)/2,66 ft & (xn +5//15, and 2 (212 + x/2)/TT
2 0 Vjj E (1, (1,...)). q). We
After the following adaptations, we take the mean over input dimensions to ensure that function values do not increase with dimensions. Finally, we normalize the outputs.
D.4. Energy market
Let x A X2), where denotes price to bid and X2 denotes a quantity in MW to supply at bid price. (0.01, 0.5), X2 E 5000, We simulate a network with 3 generators that has to fulfill an estimated demand schedule for 3 periods. The generators' parameters are given in Table 2, where z [21, 22] are the lower-level variables. z E (0.0, 0.2), 2g E (0.5, 1.5). These two variables were selected as a proxy for auxiliary concerns such as efficiency and maintenance costs, on top of operational costs.
The lower-level objective function is denoted
f(x, z) - cost(x, 2) 2.5 * w. (21) - 1.5 * w.n (Z2),
where cost(x, z) is the operational cost of producing z MW of power, simulated by PyPSA. w, (zı) & exp(5 21) 1 and W., (z₂) - (log( 0.77 22 + 1.15) - (-0.75 * 2, + 1.15)) - 0.797, where w, and w., are different nonlinear weighting functions applied to z. If dispatch not feasible at point, we set the lower-level objective value with an arbitrary large negative number, and the upper-level objective value at
17

---

BILBO: BILevel Bayesian Optimization
type
nominal power
marginal cost
quadratic marginal cost
ramp limit
max p factor
coal
200
0.005
0.0005
21
gas
100
0.015
0.0005
0.5
wind
60
0.02
0.005
Z2
Table 2: Parameters input into PyPSA generator. 'max p factor' refer to "p_max_pu', the maximum power at snapshot given fraction of nominal power.
Carsonylation of DiMethlEtheerb to Methyl Acetate
Cocyright (c) 2020 ChemSep.om org
CO
262.5 kmolh CO 98%
Purger
5 8m
Purge2
Feed GO
Mostly CO
V-101
DME
R-101
E-102
250 300 K
E-101
MeOH 0.1%
32 stm
16
MeAce
C101
MeOH 0.1%
Figure 6: Flowsheet of chemical process. R-101 the reactor, and C101 is the distillation column.
The upper-level objective function measures profit as
F(x,z) z) x22 df(x:) cost(x, z),
where df(x;) A min(1, cxp(-10x; + 0.25)) returns factor that simulates the demand response of consumers. This implies disincentive for providers to bid at high prices, because consumers might choose to reduce their electricity usage or look for alternative providers.
We discretized the input space into 15 at each dimension.
D.5. Chemical process
The flowsheet used is shown in Figure 6, where the output of reactor R101 contains mix of Methyl Acetate, unreacted DME, and other by- by-orudus,s, and the distillation column C101 separates these products to obtain high purity Methyl Acetate. The flowsheet was adapted from ChemSep, where the recycle streams have been removed to simplify the process. CO and DME are fed in fixed flow and concentration for all experiments, indicated in the figure. The distillation feed is always at level 2, and we fixed the output concentration of Methyl Acetate 99.9%. Note that we can simulate the reactor R101 without the column C101.
The upper- and lower-level parameters to be optimized are defined in Table 3. We discretized the input space into 10 at each dimension, and the variables are normalized to j0, 1].
Let sim (x, z) be the simulated mass flow of Methyl Acetate (kg/s) at the output of the reactor R101, and simeio1 (x, z) be the simulated mass flow of Methyl Acetate (kg/s) at the MeAce output of the column C101.
18

---

BILBO: BILevel Bayesian Optimization
name
min
max
normalized symbol
Number of levels in distillation column
23
Xg E
[0, 1]
Temperature of reactor (K)
455
500
8o E
[0, 1
Number of heating tubes in reactor
600
1500
21 E 0,
Diameter of heating tubes (m)
0.02
0.065
Z2 E [0
Table 3: Parameters of the chemical experiment.
The lower-level objective function denoted as
f(x, z) simgior (x, z) 1e-3 zi:
where the second term is a penalty on higher temperatures to account for energy costs. The upper-level objective function then denoted as
f(x, x) - simcror (x, z) le-4 * Xi:
where the second term is penalty on more levels in the distillation column as associated with higher costs. The higher costs could be due maintenance, energy consumption equipment cost.
D.6. Computational resources
The experiments in this paper were done on a computer with AMD Ryzen 7 5700X 8-Core Processor and GB RAM, unless otherwise specified.
E. Complexity and efficiency of BILBO
E.1. Computational complexity of BILBO
For discretized implementation, the computational complexity of BILBO is affected by the computational complexity of:
Gaussian processes, Onn²),
Updating trusted sets, O c).
Selecting function query, ([F)c).
Optimizing the acquisition function, Occ).
where n is the number of observations, is the number of discretized points, and [F] is the number of blackbox functions.
In uniform grid discretization, which is used in our implementation, if each dimension is divided into points, then the cardinality is c = m² where is the number of dimensions. Thus, dimensionality d exponentially affects computational complexity when using uniform grid discretization. Adaptive discretization may be able to mitigate the exponential factor of dimensionality, where effective dimension der & d.
E.2. Time efficiency of BILBO
While our experiments have shown that BILBO is more sample efficient than nested methods, BILBO does require more computational cost to update trusted sets and select function queries and query points. the presence of inexpensive lower-level evaluations, BILBO's time efficiency can be lower than that of nested method. However, do note that BILBO's motivation is for settings with expensive blackbox evaluations, where evaluations can be real-world experiments simulators that are costly or slow.
In addition, BILBO has advantages in scenarios with noisy observations or multiple lower-level solutions. Nested methods only solve for one solution each lower-level optimization, and it can be suboptimal in these scenarios. On the other hand, BILBO manages the uncertainty of lower-level estimates in a principled way and allows for multiple lower-level estimates, possibly providing better lower-level estimates reduce regret more effectively even if each iteration takes more time.
19

---

BILBO: BILevel Bayesian Optimization
10
instantaneous regret
10a
10-1
10-4
10-3
BILBO
TrustedRand
10-4
Nested
10-5
10
20
30
40
time elapsed (sec)
Figure 7: Regret against wall-clock time for the BraiinHoo--olldseeiiiiiic experiment
In terms of wall-clock time, Mac Studio with M2 Ultra over 5 runs and 40 seconds total runtime, for the 2-dimensional experiment, the average time per BILBO iteration is 0.131s, which is about 1.5 times slower than TrustedRand and about 26 times slower than Nested. Figure 7 shows how regret decreases over wall-clock time. We observed that while the regret for Nested smaller than BILBO in the initial seconds, Nested's regret quickly plateaus due to suboptimal lower-level estimates the multimodal lower-level objective. BILBO outperforms Nested subsequently as BILBO converges to more optimal solution.
20


Reviews:
[{"review_id": "X0gXtMhjD4", "reviewer": "Reviewer_GE3e", "summary": "This paper introduces BILBO, a Bayesian optimization method for bilevel problems with noisy, constrained black-box objectives. It jointly optimizes both levels using trusted sets from Gaussian process confidence bounds. BILBO provides theoretical regret guarantees and outperforms baselines in empirical evaluations.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review, and for recognizing the importance and practicality of our bilevel problem, clear and first theoretical guarantees in this setting, and good empirical support. We would like to address the questions raised.\n\n>Could you concisely highlight which specific aspects of BILBO are technically novel, beyond standard Bayesian optimization techniques (GP, confidence bounds)?\n\nBILBO contains the following novel contributions to tackle unique challenges in bilevel Bayesian optimization where the upper-level optimization is constrained by lower-level solutions:\n\n1. Formulation of the trusted set of optimal lower-level solutions $\\mathcal{P}^+_t$ based on lower-level estimates, where we showed that points in the set have lower-level objective regret bound. This reduces the search space and is a key step towards the derivation of regret bound for BILBO.\n\n2. Function query selection strategy with conditional reassignment of query point. Our function query strategy includes a term for the uncertainty of lower-level estimates, which corresponds to the additional difficulty from lower-level optimization that is not present in standard optimization. We also introduced the conditional reassignment as a way to explore the lower-level objective without the repeated lower-level optimization found in many bilevel Bayesian optimization methods.\n\n>How does BILBO practically handle scalability to higher-dimensional problems, given the reliance on discretization?\n\nOne way is via adaptive discretization, which can reduce the effective dimension.\n\nAlso, while we had discretized the problems in our experiments, BILBO does not require discretization of continuous inputs. A scalable BILBO implementation for continuous problems could contain a continuous representation of the trusted sets, e.g. with hyperrectangles, and use L-BFGS or SLSQP to optimize the acquisition function, similar to TorchBO.\n\nWe hope our clarifications on the novel aspects of our work and scalability discussions addressed your questions and will improve your opinion of our paper.", "claims_and_evidence": "The results are theoretical in nature, and proofs are provided. The results are sound.", "methods_and_evaluation_criteria": "I believe this is not applicable due to the theoretical nature of the paper.", "theoretical_claims": "While I did not check all details, the proofs appear generally sound and reasonable.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The paper uses existing methods from Bayesian optimization and extends them to bilevel optimization.", "essential_references_not_discussed": "Not aware of any.", "other_strengths_and_weaknesses": "Strengths:\n\n- Addresses an important, practical problem (efficient bilevel Bayesian optimization).\n- Provides clear theoretical guarantees (sublinear regret bound), an important first in this setting.\nTrusted set approach effectively reduces expensive lower-level evaluations.\n-Good empirical support via both synthetic and real-world experiments.\nWeaknesses:\n\n- Limited technical novelty; methods (GP modeling, confidence bounds) are mostly standard.\n- Scalability issues due to discretization, especially in higher-dimensional cases.\n- Clarity could improve—some definitions and assumptions initially confusing.", "other_comments_or_suggestions": "Overall, the paper is sound and clear. The technical novelty however seems quite limited as most technical tools are based on standard GP confidence intervals. The paper benefits from a discussion on technical novelty.", "questions_for_authors": "Could you concisely highlight which specific aspects of BILBO are technically novel, beyond standard Bayesian optimization techniques (GP, confidence bounds)?\n\nHow does BILBO practically handle scalability to higher-dimensional problems, given the reliance on discretization?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "Not applicable!"}}, {"review_id": "gHeM7EqulF", "reviewer": "Reviewer_zVpo", "summary": "The paper proposes a UCB based method for bilevel Bayesian optimization. The proposed method, called BILBO, selects a next point by the upper bound based surrogate model bilevel optimization. The authors provide a regret analysis based on an approach of the well-known GP-UCB analysis.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and for appreciating the potential of our problem. We would like to address some questions and concerns raised.\n\n>1. Many lemmas (e.g., Lemma 4.4 and 4.6) should be a probabilistic bound because most of them depend on Corollary 4.2, but is often shown as a deterministic bound. Why? Just omitted?\n\nThe lemmas are all probabilistic bounds, which were omitted for brevity. We will clarify this in the next version of the paper.\n\n>2. Corollary 4.2 is for simultaneously holding on all possible x, z, h, and t? If so, it should be explicitly written.\n\nYes, we omitted it for brevity as it was already stated in the directly preceding Definition 4.1. We can add this in the next version of the paper.\n\n>3. In the experiments, \\sum_h \\in F r_h,t is used for the evaluation, but r_F,t can be negative according to (3.5). Is it correct?\n\nYour interpretation is correct and (3.5) should be $r_F(\\mathbf{x}_t, \\mathbf{z}_t) ≜ \\max(0, F(\\mathbf{x}^*, \\mathbf{z}^*) - F(\\mathbf{x}_t, \\mathbf{z}_t))$, which is what we had implemented in our experiments to avoid negating other regret components. Thank you for pointing this out, and we will update (3.5) in the next version of the paper. Lemma C.3. will still hold with minor edits to the proof.\n\n>4. How is the maximization of (4.6) solved?\n\nIn our experiments, we discretized the search space so the arg max over all the discrete points can be easily found.\n\nFor continuous domains, we can use a continuous representation for the trusted sets, e.g. with hyperrectangles, and use L-BFGS or SLSQP to optimize the acquisition function, similar to TorchBO.\n\n>The paper seems only discusses the discrete input setting. It should have been explicitly stated in the main text.\n\nWhile we discretized the inputs in our experiments implementation, our theoretical analysis holds for continuous inputs, and it is possible to implement BILBO for continuous inputs in practical settings as discussed above.\n\n>W: Most of theoretical techniques are directly from well-known Srinivas et al (2010).\n\nWe would like to clarify that our theoretical techniques are not derived directly from Srinivas et al (2010), but only utilizes an adapted confidence bound in Corollary 4.2. We tackle bilevel challenges that differ from the single-objective, unconstrained optimization in Srinivas et al (2010).\n\nIn particular, we introduced a function query selection strategy with conditional reassignment, to select a function query for the decoupled setting, while accounting for the uncertainty of lower-level estimates. The conditional reassignment is also crucial for the exploration of the lower-level objective without repeated lower-level optimizations. These novel components address challenges associated with the lower-level optimization of bilevel problems, and are integral to the derivation of a sublinear regret bound for BILBO.\n\n>The abbreviation 'LL' is used in some figures, but not defined.\n\n'LL' refers to lower-level. We will define this in the next version of the paper.\n\nWe hope our clarifications have addressed your questions and improved your opinion of our paper.", "claims_and_evidence": "Since baselines are not well-known methods, efficiency is somewhat difficult to evaluate though I am not sure there does not exist other appropriate existing methods.", "methods_and_evaluation_criteria": "Results on four benchmark functions and two real-word functions are reported. I think the amount of evaluation is sufficient.", "theoretical_claims": "I couldn't fully follow the proof.", "experimental_designs_or_analyses": "The experimental settings are seemingly reasonable.", "relation_to_broader_scientific_literature": "Bilevel optimization seemingly often occurs in various scientific fields, and so, I think the topic has a potential importance.", "essential_references_not_discussed": "I don't have any suggestion.", "other_strengths_and_weaknesses": "S: The topic seemingly has a potential importance, though it has not been widely studied.\n\nW: Significance of performance improvement is somewhat difficult to evaluate because the baseline methods are not popular approach. I guess the Thompson sampling might have been a good baseline.\n\nW: Most of theoretical techniques are directly from well-known Srinivas et al (2010).", "other_comments_or_suggestions": "The abbreviation 'LL' is used in some figures, but not defined.\n\nThe paper seems only discusses the discrete input setting. It should have been explicitly stated in the main text.", "questions_for_authors": "1) Many lemmas (e.g., Lemma 4.4 and 4.6) should be a probabilistic bound because most of them depend on Corollary 4.2, but is often shown as a deterministic bound. Why? Just omitted?\n\n2) Corollary 4.2 is for simultaneously holding on all possible x, z, h, and t? If so, it should be explicitly written. \n\n3) In the experiments, \\sum_h \\in F r_h,t is used for the evaluation, but r_F,t can be negative according to (3.5). Is it correct?\n\n4) How is the maximization of (4.6) solved?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aGheQm2FDS", "reviewer": "Reviewer_xBiD", "summary": "This paper introduces BILBO (BILevel Bayesian Optimization), a BO (Bayesian Optimization) algorithm used to address constrained bilevel optimization problems where the constraints, the upper objective and the lower objective are all black boxes and assumed expensive to evaluate. BILBO distinguishes itself from the state-of-the-art of derivative-free bilevel BO by its ability to simultaneously optimize the objectives (both upper and lower) and discover the unknown constraints.\n\nThe performance of BILBO is studied both theoretically and empirically.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review, and for recognizing our sublinear cumulative regret and sample efficiency when both upper- and lower-level objectives are expensive blackboxes.\n>1. Have you studied the performance of BILBO when the trusted spaces are built on discretized versions of continuous search spaces? If yes, what additional assumption do you need to ensure a sublinear regret bound? If no, do you have any intuition about it?\n\nThis is an interesting future research direction that we have not studied. One possible factor on the performance of discretized problems will be the difference between the best discretized point and the optimal point in the continuous domain. This difference may be bounded with respect to the granularity of the discretization, with Lipschitz continuity assumptions. As discretization becomes finer, the performance should converge to that of continuous search spaces.\n>3. What is the computational complexity of BILBO as a function of the dimensionality of the search spaces? As a function of the cardinality of the uniform grid used for discretization?\n\nFor a discretized implementation, the computational complexity of BILBO is affected by computational complexity of :\n- Gaussian processes $\\mathcal{O}(n^3)$\n- Updating trusted sets $\\mathcal{O}(|\\mathcal{F}|c)$\n- Selecting function query $\\mathcal{O}(|\\mathcal{F}|c)$\n- Optimizing the acquisition function $\\mathcal{O}(c)$,\n\nwhere $n$ is the number of observations at an iteration, $c$ is the number of discrete points, and $|\\mathcal{F}|$ is the number of blackbox functions. In uniform grid discretization, if each dimension is divided into $m$ points, then the cardinality is $c=m^d$, where $d$ is the number of dimensions. Thus, dimensionality $d$ exponentially affects computational complexity when using uniform grid discretization. \n\nAdaptive discretization may be able to mitigate the exponential factor of dimensionality, where effective dimension $d_\\text{eff}\\ll d$. However, high dimensionality leads to common challenges that go beyond computational complexity (of BILBO). For example, it is also known to reduce the effectiveness of Gaussian processes as observations become increasingly sparse. \n>4. How would you integrate unknown hard constraints in your framework? How would they impact the performance of BILBO?\n\nWe can use variational inference to approximate the Gaussian process posteriors while accounting for infeasible observations, e.g. approximating $p(c(x^*)\\mid y(\\mathbf{x}_1),c(\\mathbf{x}_2)<0)$, where $y(\\mathbf{x}_1)$ are noisy feasible observations and $\\mathbf{x}_2$ are the observed infeasible points. While $c(\\mathbf{x}_2)$ is not observed directly, we can condition on the information that $c(\\mathbf{x}_2)<0$ since $\\mathbf{x}_2$ is infeasible.\n\nMore observations might be required to model constraint boundaries accurately as infeasible observations become less informative. Nevertheless, we can still apply BILBO with the primary adaptation being in the estimation of the posterior belief, while further investigation is needed to assess the effectiveness for hard constraints in practice.\n>5. Do you agree that BILBO could be less efficient than other bilevel BO solutions such as [1, 2] if the lower objective is inexpensive to evaluate? If yes, can you comment on that? If no, can you justify?\n\nThe efficiency (in terms of wall-clock time) would depend on the computational cost of each iteration of BILBO versus the cost of evaluating the lower objective, as well as the optimality of lower-level estimates for nested methods such as [1, 2].\n\nWhile it is possible for BILBO's computational cost to outweigh an inexpensive lower-level objective evaluation, BILBO still has advantages in scenarios with noisy observations or multiple lower-level solutions, which may be more common. Nested methods only solve for one solution for each lower-level optimization, and it can be suboptimal in these scenarios. On the other hand, BILBO manages the uncertainty of lower-level estimates in a principled way and allows for multiple lower-level estimates, possibly providing better lower-level estimates to reduce regret more effectively even if each iteration takes more time.\n>2. How does the immediate regret of BILBO evolves as a function of the wall-clock time?\n\nOn a Mac Studio with M2 Ultra, for the 2D BraninHoo+GoldsteinPrice experiment, the average time per BILBO iteration is 0.132s, which is 2x slower than TrustedRand and ~50x slower than Nested.\n\nHowever, while the regret for Nested decreases faster than BILBO in the initial (~5) seconds, Nested's regret quickly plateaus due to suboptimal lower-level estimates of the multimodal lower-level objective. BILBO outperforms Nested subsequently as BILBO converges to a more optimal solution, supporting our point in the previous question above.\n\nWe hope these discussions on the efficiency, complexity and possible extensions of BILBO addressed your questions and will improve your opinion of our work.", "claims_and_evidence": "The claims of the paper are the following:\n\n(i) BILBO simultaneously discovers the constraints and optimizes the upper and lower objectives instead of requiring the optimization of the lower objective at each iteration.\n\n(ii) BILBO has a sublinear cumulative regret.\n\n(iii) BILBO performs empirically better than other bilevel optimization methods *in the particular setting considered in the paper*.\n\nOverall, I think the claims are adequately supported. Claim (i) is verified by the definition of BILBO (see Algorithm 1), Claim (ii) is supported by Theorem 4.9 and Claim (iii) is backed up by numerical experiments on low-dimensional problems (see more comments on this particular point below).", "methods_and_evaluation_criteria": "Because BILBO addresses bilevel optimization in a very particular setting (expensive black-box objectives, expensive black-box constraints), there is no other bilevel optimization method that could directly compete with BILBO (as far as I know). Nevertheless, the paper introduces two benchmarks:\n\n(i) **TrustedRand**: randomly selects queries from trusted sets defined in the paper and observes all the constraints/objectives at once,\n\n(ii) **Nested**: applies BO to the upper objective only, the lower objective is optimized with Sequential Least-Squares Programming (SLQP) at each query.\n\nThese two methods are compared against BILBO on synthetic and real-world experiments that make sense for the problem considered in this paper.", "theoretical_claims": "The main theoretical claim is that BILBO has a sublinear cumulative regret. This is backed up by common proof techniques in BO asymptotic analysis and hold with high probability and as long as the search space is compact.\n\nBecause the trusted sets are built on discretized search spaces, studying the behavior of BILBO given a discretization would have been a nice addition to the paper.", "experimental_designs_or_analyses": "The experiments are all low-dimensional (at most 5 dimensions for the SMD synthetic experiments, with 2 and 3 dimensions for the upper and lower objectives, respectively) and the continuous search spaces are discretized with a uniform grid. I believe this is a limitation of the approach, since BILBO requires scanning the whole search space for building trusted sets and solving up to two non-trivial optimization problems at each iteration. I don't think such an expensive process could scale nicely with the search spaces dimensions or with a finer discretization of the search spaces.\n\nTo better study the limitations of BILBO, I would have liked to see other numerical results and analyses, such as:\n* the immediate regret plotted against wall-clock time for the considered methods,\n* the computational complexity of BILBO, especially in terms of the dimensionality of the search spaces and/or the granularity of the discretization,\n* the performance of BILBO on bilevel optimization tasks where the lower objective is not expensive, to study how it performs against other bilevel BO solutions that make more restrictive assumptions such as [1, 2].\n\n**References**\n\n[1] Kieffer, E., Danoy, G., Bouvry, P., and Nagih, A. Bayesian optimization approach of general bi-level problems. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 1614–1621, 2017.\n\n[2] Wang, B., Singh, H. K., and Ray, T. Comparing expected improvement and kriging believer for expensive bilevel optimization. In 2021 IEEE Congress on Evolutionary Computation (CEC), pp. 1635–1642. IEEE, 2021.", "relation_to_broader_scientific_literature": "As far as I know, there is no other bilevel optimization method able to discover and optimize the constraints and the objectives when all these functions are expensive black boxes. Although I have some concerns about its scalability, BILBO is useful to solve a bilevel optimization problem under a minimal set of assumptions.", "essential_references_not_discussed": "The very recent work [1] is discussed by the authors but ignored in the numerical experiments. Although comparing BILBO to this solution in numerical experiments would have been a nice addition to the paper, [1] falls under the ICML Concurrent Work policy.\n\n**References**\n\n[1] Ekmekcioglu, O., Aydin, N., & Branke, J. (2024). Bayesian Optimization of Bilevel Problems. arXiv preprint arXiv:2412.18518.", "other_strengths_and_weaknesses": "As far as I understand the paper, BILBO is efficient when the objectives and the constraints are expensive black boxes. I have two comments about this:\n\n* Although this is not a concept introduced by the authors, I think considering expensive black-box constraints is of little interest. In most applications, the constraints are known to the user beforehand and are not expensive to evaluate. Moreover, discovering the constraints during the optimization implies that the constraints are soft (i.e., they can be violated by the optimizer). Including unknown hard constraints (i.e., no measurement can be made if at least one constraint is violated) seems not trivial in your framework.\n\n* Although the sample efficiency of BILBO is definitely one of its strengths, the particular setting within which BILBO is efficient could be seen as a restriction. In fact, as far as I know, most authors justify the use of BO for the upper objective precisely because they require, at each query, an expensive optimization of an inexpensive-to-evaluate lower objective. Given that a significant fraction of bilevel optimization problems occur in this setting, it should be clearly stated in the paper that BILBO can be less efficient (e.g., when comparing the instantaneous regrets w.r.t. the wall-clock times) than other bilevel BO methods when the lower objective is inexpensive to evaluate.", "other_comments_or_suggestions": "The paper contains many forward pointers (i.e., it refers to Lemmas or Definitions that are introduced later in the paper). I suggest to replace/remove them wherever possible to make reading the paper more pleasant.", "questions_for_authors": "Here are some questions (labelled for future reference) to spark the discussion with the authors:\n\n1. Have you studied the performance of BILBO when the trusted spaces are built on discretized versions of continuous search spaces? If yes, what additional assumption do you need to ensure a sublinear regret bound? If no, do you have any intuition about it?\n\n2. How does the immediate regret of BILBO evolves as a function of the wall-clock time?\n\n3. What is the computational complexity of BILBO as a function of the dimensionality of the search spaces? As a function of the cardinality of the uniform grid used for discretization?\n\n4. How would you integrate unknown hard constraints in your framework? How would they impact the performance of BILBO?\n\n5. Do you agree that BILBO could be less efficient than other bilevel BO solutions such as [1, 2] if the lower objective is inexpensive to evaluate? If yes, can you comment on that? If no, can you justify?\n\n**References**\n\n[1] Kieffer, E., Danoy, G., Bouvry, P., and Nagih, A. Bayesian optimization approach of general bi-level problems. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 1614–1621, 2017.\n\n[2] Wang, B., Singh, H. K., and Ray, T. Comparing expected improvement and kriging believer for expensive bilevel optimization. In 2021 IEEE Congress on Evolutionary Computation (CEC), pp. 1635–1642. IEEE, 2021.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UWZLcEV8PB", "reviewer": "Reviewer_kdcy", "summary": "This paper proposes a bi-level Bayesian optimization algorithm for black-box functions. By optimizing both upper- and lower-level problems simultaneously, it improves the sample efficiency. Theoretically, BILBO achieves a sublinear regret bound for common kernels. It also demonstrates strong empirical performance on synthetic and real-world problems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review, and for appreciating our novel approach to a significant problem, sample efficiency of our method, sublinear regret bound, and effective experimental results. We would like to clarify the following points.\n\n>One issue is that some of the results shown in the experimental section seem to be non-complete, such as the green curves in the Fig. 4 (a, b, c).\n\nThe green curves represent Nested's number of queries over regret. There is an obvious gap at the start of each green curve as the Nested method requires more initial observations of lower-level functions to optimize the lower-level problems separately before estimations begin, compared to BILBO and TrustedRand.\n\n>What if the lower-level problem is a white-box problem that can be solved via a nonlinear programming solver? Can similar idea work for this case?\n\nWhite-box problems are often inexpensive to compute. We can still apply our algorithm, evaluate the white-box problem at every step and reduce the confidence interval to a point, since there are no noisy observations. If the nonlinear programming solver for the lower-level is preferred (e.g. for computational efficiency), we can also reduce BILBO to a special case where Bayesian optimization is carried out only on the upper-level. However, we would also like to point out that BILBO's advantages are in settings with expensive blackbox evaluations and noisy observations, both of which are not present in this scenario.\n\nWe hope these clarifications answer your questions and improve your opinion of our paper.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked the key steps for the proof of the main theoretical results, but not all the details. As far as I know, the proofs are correct.", "experimental_designs_or_analyses": "Yes. I checked the experimental results, and they are mostly sound to me. One issue is that some of the results shown in the experimental section seem to be non-complete, such as the green curves in the Fig. 4 (a, b, c).", "relation_to_broader_scientific_literature": "Confidence-bound algorithms are extended to bi-level constrained problem, which could be of general interest to Bayesian optimization, bi-level optimization, and multi-armed bandits research.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "1. This work addresses a significant problem and introduces a novel approach to bilevel Bayesian optimization. \n2. Unlike existing methods that requires full lower-level optimization for each upper-level query, the proposed algorithm optimizes both levels concurrently, significantly improving sample efficiency. \n3. It also incorporates an infeasibility declaration method and achieves a theoretical sublinear regret bound, extending the classic bound from single-level to bilevel problems. \n4. Experimental results demonstrate its effectiveness.", "other_comments_or_suggestions": "This approach maintains a set of nearly optimal solutions for the lower-level problem. While discretization is feasible in low-dimensional cases, scaling to even moderately high-dimensional problems is likely challenging.", "questions_for_authors": "What if the lower-level problem is a white-box problem that can be solved via a nonlinear programming solver? Can similar idea work for this case?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper has largely positive reviews. Reviewers find the setting relevant, the approach new and interesting, and believe the key claims are supported. Reviewers found both the empirical and theoretical contributions valuable, and the writing was described as clear. The main weaknesses raised came down to various technical details involving constraints and how certain discretizations affect performance. 

The main issue I am concerned about is the use of search domain discretization in the empirical evaluations, since this can make Bayesian optimization methods perform very badly. Unless I have misunderstood reviews and a quick read of the authors' experiment section, the authors appear to not have evaluated their method with hyperrectangle-based trust sets, which they propose as an alternative for cases where discretization doesn't work. This leaves me worried, but reviewers - some of whom are seasoned experts - thought other aspects of the paper were strong-enough to justify high scores in spite of this issue. Hence, I am going to go with reviewer consensus, and conclude that this weakness, while significant, is not significant enough to warrant outright rejection in light of the work's overall contributions.

In the discussion phase, reviewers suggested the paper should be classified as "weak accept" on balance of the issues. Given the above points, I concur.
Decision: Accept (poster)