BILBO: BILevel Bayesian Optimization

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.

(1) Many real-world problems involve hierarchical decision-making with two levels of optimization, such as pricing strategies and toll setting. Bilevel optimization can model such hierarchical structures, but many existing methods require inefficient, repeated optimizations at the lower level. (2) We proposed BILevel Bayesian Optimization (BILBO), a novel algorithm that optimizes for both levels simultaneously. We do this by maintaining a trusted set of probable solutions, and encouraging exploration of the lower level via conditional reassignment. (3) Our method is applicable to general bilevel problems, with no assumptions on the availability of gradients, unlike many existing methods. We also provided theoretical guarantees and presented empirical results to show the potential of enabling applications to complex real-world bilevel problems.