Bayesian optimization is a technique for efficiently optimizing unknown functions in a black-box manner. To handle practical settings where gathering data requires use of finite resources, it is desirable to explicitly incorporate function evaluation costs into Bayesian optimization policies. To understand how to do so, we develop a previously-unexplored connection between cost-aware Bayesian optimization and the Pandora's Box problem, a decision problem from economics. The Pandora's Box problem admits a Bayesian-optimal solution based on an expression called the Gittins index, which can be reinterpreted as an acquisition function. We study the use of this acquisition function for cost-aware Bayesian optimization, and demonstrate empirically that it performs well, particularly in medium-high dimensions. We further show that this performance carries over to classical Bayesian optimization without explicit evaluation costs. Our work constitutes a first step towards integrating techniques from Gittins index theory into Bayesian optimization.
Figures & tables
Figure 1: An illustration of this work’s key idea. We view cost-aware Bayesian optimization as an extension of the Pandora’s Box problem, and derive the cost-aware acquisition function αtPBGI by incorporating the posterior into the Bayesian-optimal Pandora’s Box acquisition function α⋆ .
Figure 2: A Bayesian optimization problem with varying costs on which LogEIPC—a numerically stable implementation of EIPC, see Sections 4 and D.1 —has poor performance, inspired by [ 4 , Section A] . The domain is X=[−500,500] , which we visualize on the subinterval [−5,5] . Left: illustration of the non-uniform prior variance, which is given by a Matérn-5/2 kernel scaled by a narrow bump function. Center: the cost function, which is a narrow bump-shaped function. Right: median regret curves and quartiles for LogEIPC and PBGI. Legend refers only to regret curves.
Figure 3: Left: contour plots showing how EI (left) and PBGI (center-left, center-right) depend on the posterior mean and standard deviation at a given point (lighter colors indicate higher values). We see that PBGI values high standard deviation more than EI. Right: PBGI performance across values of λ , under the setup of the Bayesian regret experiment of Section 4 with d=8 . We plot the median of a set of samples using n=256 random seeds, along with quartiles to show variability. We see that large λ -values decrease regret sooner, but eventually lose out to smaller λ -values.
Figure 4: Regret curves for objective functions sampled from the prior, shown using medians, as well as quartiles to indicate experiment variability. We see in the cost-aware setting that both PBGI variants usually exhibit comparable performance to LogEIPC and LogEICC, with PBGI-D decisively outperforming other baselines. In the uniform-cost setting, the story is similar for d=8 and d=16 : PBGI and PBGI-D perform comparably to the best baselines, which are LogEI and UCB, as well as MSEI for d=8 . However, for d=32 , all methods perform comparably to random search, with PBGI, PBGI-D, LogEI, and UCB having near-identical median performance. See Figure 14 for an alternative visualization using mean and standard error.
Figure 5: Synthetic benchmark regret curves, shown using medians, as well as quartiles to assess variability. All objective functions are defined with dimension d=16 . We see in the cost-aware setting that PBGI, PBGI-D, LogEIPC, and LogEICC all perform similarly on the heavily-multimodal Ackley function, matching or outperforming the non-myopic BMSEI baseline. On the Levy and Rosenbrock functions, PBGI-D matches—and for some cost budgets outperforms—all baselines, including the non-myopic BMSEI. Under uniform costs, PBGI performs well on Ackley and Levy, but is outperformed by PBGI-D and most baselines on Rosenbrock. See Figure 14 for an alternative visualization using mean and standard error.
Figure 6: Empirical benchmark regret curves, shown using medians, as well as quartiles to show variability. We see in both the varying-cost and uniform-cost settings that PBGI exhibits strong performance on the Pest Control and Lunar Lander problems. On the Robot Pushing problem, LogEI variants perform strongest, with PBGI-D performing second-strongest and matching or outperforming all other baselines. See Figure 14 for an alternative visualization using mean and standard error.
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 7: An illustration of the two-dimensional Ackley, Levy, and Rosenbrock functions. 1 1 1 This visual originally appeared in [ 41 ] , and is reproduced here with permission. From the visual, one can see that these functions differ in terms of multimodality and ridge-regions within the optimization landscape.
Figure 8: Comparison between three acquisition functions, namely Expected Improvement (EI), Pandora’s Box Gittins Index (PBGI) with a large λ -value of λ=100 , and Pandora’s Box Gittins Index with a small λ -value of λ=10−5 . All three are computed using the same posterior distribution with four data points. The maximum is shown as a large dot.
Figure 9: A Bayesian optimization problem with varying costs on which LogEI, a numerically stable implementation of EI—which by construction ignores costs—has poor performance. See Sections 4 and D.1 for additional details. Like Figure 2 , this construction also mirrors [ 4 , Section A] . The domain is X=[−500,500] , which we visualize on the subinterval [−5,5] . Left: illustration of the non-uniform prior variance, which is given by a Matérn-5/2 kernel scaled by a narrow bump function, plus a constant. Center: the cost function, which is a narrow bump-shaped function. Right: regret curves, shown as medians and quartiles.
Figure 10: Experimental results comparing the impact of log-scaling and numerical stability on the performance of EI and PBGI, tested on Bayesian regret with d=16 and shown using quartiles. We see that Exp(LogEI) is close to Unst. EI, and similarly for S-PBGI vs PBGI. However, Log(Unst. EI) improves significantly over EI, and LogEI improves even more.
Figure 11: Runtime comparison of PBGI against baselines for computing the acquisition function on the Ackley benchmark across different dimensions ( d=4,8,16 ). We see that runtime of PBGI is slower than LogEI and TS, but faster than KG and MSEI.
Figure 12: Behavior of PBGI-D under different choices of the initial value λ0 , and the coefficient of decay β , on the Bayesian regret experiment with d=8 and other parameters set the same way as in Section 4 . We show medians under n=256 samples, along with quartiles to assess variability. We see that smaller λ0 -values act similarly to the behavior seen in Figure 3 for PBGI, trading off risk-seeking vs. risk-averse behavior, but with a substantially smaller gap between the two variants. Larger β -values lead to more-abrupt decay curves for λ , with an effect qualitatively similar to λ0 . In both cases, though our relatively-large sample size allows us to see small differences between methods, their overall impact on performance is close-to-nonexistent on the scale of variability.
Figure 13: Experimental results for the Robot Pushing empirical benchmark, with the known-cost variant (left) and unknown-cost variant (right). We see that LogEIPC, LogEICC, and PBGI-D perform best in both cases.
Figure 14: Regret curves for the Bayesian regret and synthetic benchmark experiments, as well as best observed values for the empirical experiments, shown using means (solid lines) and two times standard errors (shaded regions). See Figures 4 , 5 and 6 for details.
Figure 15: Comparison of Bayesian regret across Gaussian process priors with different kernels over different dimensions, in the uniform-cost setting. All length scales are κ=10−1 . We see that overall behavior is similar, but the precise thresholds at which each example switches between the easy, medium-hard, and very hard regimes differ.
Figure 16: Comparison of Bayesian regret across Gaussian process priors with different kernels over different dimensions, in the cost-aware setting. All length scales are κ=10−1 . We see that overall behavior is similar, but the precise thresholds at which each example switches between the easy, medium-hard, and very hard regimes differ.
Figure 17: Comparison of Bayesian regret across different length scales and dimensions, with a Matérn-5/2 kernel, in the uniform-cost setting. We see similar overall behavior, but each example switches between the easy, medium-hard, and very hard regimes at different precise thresholds.
Figure 18: Comparison of Bayesian regret across different length scales and dimensions, with a Matérn-5/2 kernel, in the cost-aware setting. We see similar overall behavior, but each example switches between the easy, medium-hard, and very hard regimes at different precise thresholds.
Figure 19: Comparison of regret for synthetic benchmark functions under different dimensions, in the uniform-cost setting. We see that most methods perform similarly for d=4 , with differences between the most-competitive methods emerging as dimension increases to d=8 and d=16 .
Figure 20: Comparison of regret for synthetic benchmark functions under different dimensions, in the cost-aware setting. We see that most methods perform similarly for d=4 , with differences between the most-competitive methods emerging as dimension increases to d=8 and d=16 .
A staged search must decide which candidate to advance next and when to stop. Some observations only inform later decisions; others can be kept as results. We formulate these choices as a staged Pandora's box with a designated set of collectable stages. For independent finite-stage candidates with bounded readings and positive bounded own-history costs, an exact covered-call recursion gives the reservation index, the optimal value and the loss of every advance or stop; advancing an index-maximal candidate while its index exceeds the incumbent is optimal. The representation recovers classical single-stage search, nested inspection and the all-collectable Markov setting, and prices changes in the problem: enlarging the collectable set or lowering costs raises the value by an explicit covered-call overshoot. Resumption can be valuable even when future reward laws do not change, but has no value for deterministic readings. With information sharing across candidates, no rule using only their separate remaining-reading laws is universally optimal, and making an intermediate reading collectable can change which candidate is inspected first. Under a coherent joint path law with own-history costs, an approximate-planning bound controls the recomputed index's regret by changes in untouched candidates' local values; a common-component specialization bounds those changes through predictive total-variation dispersion. Exact finite-law experiments check the representation, the loss accounting and the bounds.
Long Vu, Jongseong Brad Choi, Binoy Ravindran +1
State University of New York Korea · Virginia Tech · Stony Brook University
Bayesian optimization is a sequential method for minimizing objective functions that are expensive to evaluate and about which few assumptions can be made. By using all gathered data to train a Gaussian process model for the function and adaptively employing a mixture of global exploration and local exploitation, this method has been used for optimization in many fields including machine learning, automotive engineering and reinforcement learning. However, the standard method suffers from two problems: 1) with cubic computational complexity in the training-set size it eventually becomes computationally infeasible to train the model, and 2) globally modeling the objective function is not necessarily optimal given the local nature of minimization. Using flexible and recursive binary partitioning of the search space, we adapt both the modeling and acquisitive aspects of standard Bayesian optimization to work harmoniously with the partitioning scheme, thereby ameliorating both standard shortcomings. We compare our method against a commonly used Bayesian optimization library on seven challenging test functions, ranging in dimensionality from 6 to 124, and show that our method achieves superior optimization performance in all tests. In addition our method has linear computational complexity.
Jesse Schneider, William J. Welch
Department of Statistics, University of British Columbia, Vancouver, BC V6T 1Z4, Canada
Bayesian optimization (BO) is a popular technique for sample-efficient optimization of black-box functions. In many applications, the parameters being tuned come with a carefully engineered default configuration, and practitioners only want to deviate from this default when necessary. Standard BO, however, does not aim to minimize deviation from the default and, in practice, often pushes weakly relevant parameters to the boundary of the search space. This makes it difficult to distinguish between important and spurious changes and increases the burden of vetting recommendations when the optimization objective omits relevant operational considerations. We introduce BONSAI, a default-aware BO policy that prunes low-impact deviations from a default configuration while explicitly controlling the loss in acquisition value. BONSAI is compatible with a variety of acquisition functions, including expected improvement and upper confidence bound (GP-UCB). We theoretically bound the regret incurred by BONSAI, showing that, under appropriate conditions, it retains the no-regret property of vanilla GP-UCB and removes irrelevant changes. Across many real-world applications, we empirically find that BONSAI substantially reduces the number of non-default parameters in recommended configurations while maintaining competitive optimization performance with little effect on wall time. Its candidate-generation cost averages only 1.5× that of standard BO, compared with 7-34× for prior sparse-BO methods.
Samuel Daulton, David Eriksson, Maximilian Balandat +1