Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index
Authors: Qian Xie
Raul Astudillo
Peter I. Frazier
Ziv Scully
Alexander Terenin
Venue: NeurIPS 2024 poster (2024)
Keywords: Bayesian optimization
acquisition function
cost-per-sample
Gittins index
Pandora's box
Primary area: probabilistic_methods
TL;DR: We introduce a connection between cost-aware Bayesian optimization and the Pandora's Box problem from economics, and use it to derive a novel cost-aware acquisition function class with promising performance.

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

Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index
Qian Xie
Raul Astudillo?
Peter I. Frazier'
Ziv Scully' Caltech
Alexander Terenin'
Cornell University
Abstract
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 so, we develop previously-unexplored connection between cost-aware Bayesian optimization and the Pandora's s Box problem, a decision problem from economics. The Pandora's s Box problem admits aayesian-optinee solution based Gittins index, which can be reinterpreted as an acquisition function. We study the use of this acquisition function for cost-aware Bayesian optimization, and demon- strate empirically that it performs well, particularly in medium-higg -igh dimensions. We further show that this performance carries over to classical Bayesian optimiza- tion without explicit evaluation costs. Our work constitutes first step towards integrating techniques from Gittins index theory into Bayesian optimization.
expression called the
Introduction
Bayesian optimization is framework for optimizing functions whose evaluation is time-consuming or expensive. It is widely used for hyperparameter tuning of machine learning algorithms [38], robot control [29], material design [47], and other areas. Bayesian optimization works by forming probabilistic model for the objective function, and then chooses where sample via an acquisition function that balances the explore-exploi trade-offs arising from uncertainty in this model.
We study cost-aware Bayesian optimization, where one must pay a cost to acquire another sample and this cost may vary with where the function is evaluated. Costs are an important factor in practical scenarios. For instance, in hyperparameter tuning using GPUs rented from a cloud provider, training a neural network for twice as many epochs may carry twice the financial cost.
Despite its practical relevance, cost-aware Bayesian optimization is less studied than standard Bayesian optimization, where budgets are framed in terms of the number of function evaluations and costs are not explicitly considered. Many existing theoretically-pricippee cost-aware approaches [46, 24, 26, 4, 7] rely on multi-step lookahead computations that are computationally expensive and can be numerically brittle, limiting their applicability. Other approaches lack theoretical foundation and risk having poor performance on certain problems. For example, one of the most popular cost-aware acquisition functions used in practice, expected improvement per unit cost [38], has recently been theoretically shown by Astudillo et al. [4] to perform arbitrarily worse than the optimal policy. Thus, in the cost-aware setting, there need for eecoretically-princiii acquisition functions with good empirical performance.
and
In this work, develop such an approach. To do so, introduce novel link between cost-aware Bayesian optimization and discrete-space decision problem from economics called the Pandora's 's
38th Conference on Neural Information Processing Systems (NeurIPS 2024).
Code available wTTPS///THHHU...OOOOL/AAAAAAAAAP

---

Box problem [44, 13, 36]. The Pandora's Box problem admits an explicit Bayesian-optima solution. We show how this solution can be used to develop a novel acquisition function class for two cost- aware Bayesian optimization settings: (i) expected budgel-constrainee Bayesian optimization, where there is a constraint on the expected cost of the samples taken, and (ii) cost-per-sample Bayesian optimization where the total costs incurred are subtracted from the final objective function value. The resulting acquisition functions are closely connected to expected improvement variants, but incorporate costs in a different, non-multiplicative way.
We evaluate the proposed acquisition function, termed the Pandora's Box Gittins Index (PBGI), on a comprehensive set of experiments to understand its strengths and weaknesses. On both sufficiently- easy (ow-dimensional problems and too-difficllt high- nigh-dimensional ones, performance comparable to baselines. On most medium-hatt problems of moderate dimension, the proposed acquisition function either matches or outperforms the strongest baselines. Surprisingly, we find this performance carries over to the classical setting with uniform costs. We also discuss limitations, including behavior on problems where baselines are stronger.
The Pandora's Box Gittins Index is a version of the Gittins index [20], a general framework for deriving optimal policies for variety of bandit-like decision problems [43, 14, 22] which is widely- used in queueing theory and related areas [21, 1, 34j. Other versions of the Gittins index have recently been proposed for Bayesian optimization with an -hriiiee discounted cumulative regret objective [32]. Our Pandora's s- s-Box-based formulation is instead designed for the simple regret objective more commo n in the literature [18]. Our work thus opens a novel angle of attack for designing acquisition functions specialized to specific practical settings of interest.
Contributions. In this work, we (i) connect the Pandora's Box problem with variant of cost-aware Bayesian optimization over a discrete search space. Using this connection, we (ii) explore the use of Gittins indices, which are seyeesia--ppiman for the Pandora's Box problem, as an acquisition function for general cost-aware Bayesian optimization where data is incorporated via the posterior distribution. We (iii) demonstrate the resulting acquisition function has strong empirical performance on variety of problems of moderate-to-Ne to-hh dimension, including the varying-cost problems it was designed for, as well as classical cost-un problems.
2 Cost-aware Bayesian optimization
In black-box optimization, we are interested in finding the global optimum of an unknown (potentially stochastic) function f X + TR. defined on some compact domain, using pointwise function evaluations of f at locations æi. Øт E X that we select sequentially. We are interested in policies that achieve low simple regret-see Garnett [18], Sec. 10.1 10.1-namely
E sup fx) E max (xx) ISTST
=
where the expectation is taken over all sources of randomness in the function f and the policy, includ- ing the stopping time T and sequential selections Ti..., Zr. In our setup, obtaining new function evaluation at a point x carries a non-zero cost c(x) E RR,, assumed discussed otherwise. We consider settings that integrate costs into the problem in different ways:
unless
(a) In the expected allowed to exceed this budget in expectation.
setting, there a budget E R4, and the algorithm is not
(b) In the cost-per-sample setting, at each time the algorithm must choose whether to pay cost and obtain new function evaluation, or to stop and return some previously-obsery point. this setting, we add the total sum of costs at termination time to the regret.
Note that the cost function e : X + R2 can be constant, which we term uniform costs. In this case, (a) reduces to standard black-box optimization with finite time horizon, and (b) reduces to a variant of stopping aware Bayesian optimization. These are not the only possible settings: one can also consider other variants including the almost-sure conget-constrained setting where the algorithm is not allowed to exceed the budget in a strict manner. Since we are interested primarily in the role of costs rather than stopping times in this work, we mostly work with budget constraints throughout this paper, especially almost-sure budget constraints for our empirical results. We will use the cost-per- sam-le setting conceptual framework with which to study budget-constraineed settings.

---

2.1 Probabilistic models and acquisition functions
Bayesian optimization algorithms for solving various black-box optimization problems work by (i) building a probabilistic model of f- that is, probability distribution which quantifies what is known about given the data points (zt, ye) seen so far-where y/2 f(x)) are previous function evaluations-thhe (ii) using the model and its uncertainty to decide where to evaluate the unknown function next. For an introduction, see Frazier [16] and Garnett [18]. Following standard practice, we work with Gaussian process models [33]. Let f Fi:t, V1:t be the respective posterior distribution.
To decide where evaluate f next, one uses the model define a (potentially random) acquisition function 0 X + R, which quantifies how promising a particular location is given what is known so far. We then evaluate f at
Fe+1
arg max or (z), =eX
obtaining an additional data point that is used to reduce uncertainty and further improve the model.
2.2 Expected improvement per unit cost
The most popular cost-aware acquisition function is expected improvement per unit cost (EIPC) [38], defined via
El Alsa. (1; max1s+
EIPC (x)
(z: = E max((0, ((x) - y)
(3)
c(z)
where we have written a; (-IPC()) in terms of the general expected functionntt function Elg. defined with respect some random function v X - R, and comparator point y. With this notation, EIPC can be interpreted as the ratio of the expected improvement, with respect to the current posterior and using the best point seen far the comparator, to the cost.
In the uniform-cost case, where the costs c(x) = C E R+ are constant for all x, this acquisi- tion function reduces to the classical expected improvement (EI) acquisition function o. El 3 (2; max Sr yr). In turn, expected improvement can be derived by considering the setup where the unknown function f is randomly sampled from the model's prior. If we imagine that the optimization process continues for only one more time step before stopping, maximizing look-loo scenario.
expected improvement is the optimal strategy in this
Since EIPC reduces to El in the uniform-cost case where c(z) C. it follows that it chooses the same points whether C' = 0.0001 or C' = 1 000 000. This is somewhat peculiar: one might expect that a cost-aware acquisition function should more risk-averse if costs are high, and vice versa if they are low. Thus, EIPC is perhaps best suited to settings where heterogeneity of costs is the main factor at play: without heterogeneity, one can simply apply standard acquisition function variants [11]. However, even with heterogeneous costs, Astudillo et al. [4] show there exist reasonable problems where EIPC performs arbitrarily worse than the optimal policy in an approximation-rali sense, due to over-sampling low-value low-cost points. Analogous behavior can occur in multi-fidelig settings, which Wu et al. [45] argue can be especially undesirable in the presence of model-misspeciffee misssecifiication
In spite of this rather negative outlook, EIPC has been shown to work well on many practical problems, is computationally efficient and reliable, and is the standard cost-aware choice in BoTorch [5]. We therefore ask: can one develop a alternative with ce-eaatcoompaaalle empirical performance?
and
3 The Pandora's Box Gittins index for Bayesian optimization
To develop a cost-aware acquisition function, we study a simplified decision problem that captures key difficulties of the main problem but is tractable enough yield analytic insights. An analogous strategy is used classically to derive expected improvement, by exactly solving simplified one-step decision problem. We study a different simplified decision problem, which can also be solved exactly, but where the simplification is spatial rather than temporal in nature. Specifically, we connect Bayesian optimization with the Pandora's Box problem from economics. To do so, we describe Pandora's Box in Section 3.1 and its solution in Section 3.2, showing along the way how these ideas can be reinterpreted from the view of Bayesian optimization. We illustrate this in Figure! 1. Then, in Section 3.3, we use Pandora's 's Box to derive novel class of cost-aware acquisition functions.
3

---

Pandora's Box
Bayesian Optimization
add correlations and take continuum limit
[(x)
f(x)
<(>)
a²: Bayesian-optimal acquisition function
incorporate f 11... Ve
of PBGI; acquisition function proposed in this work
Figure 1: An illustration of this work's key idea. We view cost-aware Bayesian optimization as
extension of the Pandora's 's Box problem, and derive the cost-aware acquisition function a incorporating the posterior into the Bayesian-optimal Pandora's 'ss Box acquisition function a
PBGI by
3.1 The Pandora's Box problem
The Pandora's ss Box problem [44, 20] is sequential decision problem. It begins with finite set of boxes, which we collect into a set and label X = {L,..,N; Each box has a hidden reward, denoted by f*), and inspection cost, denoted by c(r)) The rewards are given by mutually independent random variables whose distributions are known and vary between different boxes.
The decision-making process starts with set of closed boxes, and proceeds in discrete time steps. At time I, one can choose do one two things:
1. Open box X. This incurs cost c(xr), but reveals the exact value f(x,) of the reward inside the box, which is drawn using the box's respective reward distribution.
2. Stop opening new boxes, and take the reward from the best opened box. This ends the decision- making process, and yields a terminal reward equal to the maximum value among the boxes opened far, with the convention that least one box must be opened.
The policy's 's goal is to maximize the expected net utility, which is the reward of the best open box minus the expected total costs of all boxes opened so far, and is written
T
E max ((x)) ISST
c(xx)
where T is random variable that denotes the number of opened boxes, indicating that the policy terminates at time 7 +++ 1.
If we subtract the objective (4) from I' supgex fxx, which is constant with respect to the policy, obtain the sum of the simple regret objective (1) defined Section 2 and expected total costs. The Pandora's Box problem is therefore equivalent specifically the post-per-sampl variant of Section 2, where (a) the domain X a finite set, and (b) the objective function is random, with independent f(x) and fzz' for x'. We will return to this point the sequel, but first study the Pandora's 's Box problem in more detail.
special case of cost-aware black-box optimization,
3.2 Optimally solving Pandora's Box
The Pandora's 's Box problem gives rise to explore-exploit tradeoff: a policy must balance the opportunity gained from learning the value of the reward contained inside the box with the cost of opening it. Since the reward distributions are known, this tradeoff is captured within Markov decision process (MDP). By general MDP theory, there exists an optimal policy describing which box, if any, one should open for given configuration-ww we call such a policy Bayesian-optimal
This MDP can be solved explicitly, with remarkably simple solution, first derived in an economics setting by Weitzman [44]. We start by associating with each box x E X a number a (α)) known as the Gittins index [20]. Define
(x)
where solves
El,(1; =((x)
(
where EI F v) previously defined in (3) of Section 2, the expected improvement of x relative to y- the same expression which appeared in the expected improvement acquisition function variants

---

El and of FIPC Note that, unlike in those cases, a* is not time-dependent due to the lack of correlations or conditioning. Since EI,( g) is strictly decreasing in g. the root-finding problem (5) admits unique solution for every value of c(z)).
ar
To understand what a (xx) represents, consider a single closed box J. and suppose there is second, open box with reward f*. Is opening box x better than taking the reward f from the open box? This amounts whether the expected improvement from opening x balances out the opening cost c(x): one can show that opening x is better if and only if [1 f*) > c(z). The value a" (x) tells us how large does the alternative reward f need to be, for stopping and taking to be least as good as opening box z-a a kind of fair value which makes different boxes directly comparable to one another.
If we decide which box to open via the aforementioned fair values, obtain the Gittins index policy, which proceeds as follows. At each time I, let Se = maxigrsi (x+=) be the maximum reward among all open boxes, and x. be the box of maximum Gittins index value a" (1)) among unopened boxes, with ties broken according to a given ordering. With this notation, using a tie-breaking rule that stops as early as possible- but noting that other tie-breaking rules, including stopping as late as possible, or stopping with some probability, are also valid-we get:
If ft az (zf), the policy opens box x².
. [f 2 a² (xt), the policy stops and receives terminal reward ft"
It turns out that opening boxes according to the order determined by their fair values, in the sense above, is not only a good idea, but outright Bayesian-optimal. We state this formally as follows. Theorem 1 (Weitzman [44]). Let X be finite set, let f: X + R be finite-mean random function for which fz) is independent of f fax) for x + x', and let e - B.,, without loss of generality, be deterministic. Then, for the cost-per-sample problem, the policy defined by maximizing the Gittins index acquisition function a with its associated stopping rule is Bayesian-optimal.
In the language of Bayesian optimization, this means that not only is there an explicit Bayesian- optimal policy for the Pandora's 's Box setting, but this policy also takes the form of maximizing an acquisition function. This gives an explicit solution for the cost-per-sample setting, thereby showing Pandora's Box fits our original goal of finding a simplified decision problem that sheds insights on cost-aware Bayesian optimization. For an alternative proof, see Kleinberg et al. [25], Theorem Using Lagrangian relaxation, we show that the obtained solution carries over the expected budget-constrained setting.
Theorem 2. Consider the expected
problem. with the assumptions of Theorem 1.
Assume the problem is feasible and the constraint is active, namely minzex c(x) < B < <x c(z). Then there exists a X > and a tie-breaking rule such that the policy defined by maximizing the Gittins index acquisition function oe (-), defined using costs Xe(x)), is Bayesian-optimal
A proof is given in Appendix B. This result extends special case of Aminian et al. [3], Theorem 1. Compared to that work, we consider only Pandora's Box, but allow general reward distributions- including those with infinite support, such Gaussian rewards. The optimal À depends on the budget constraint / implicitly via a convex optimization problem given in Appendix B. In gudget-constrainet problems, we therefore view À as a hyperparameter, which controls the degree to which the algorithm is risk-averse vs. risk-secking-precice
what we argued was missing from EIPC in Section 2.
One can intuitively understand À using a needle-in sorell-in-hhysseee haystackt metaphor. Suppose wants to find the best needle, but can only search a fraction of the haystack in expectation, represented by the budget B. The key phrase is in expectation: if the search is not promising, one can stop early and avoid wasting budget, otherwise one can search more of the haystack. This prompts the question: in what situations should one continue searching? The answer depends on the interplay between the budget B, costs e, and best value f"" seen so far, and is encoded by À in Theorem 2. Larger X-values correspond to smaller budgets B, incentivizing one to search less of the haystack. Crucially, the optimal acquisition function a behaves differently for different X-values, and therefore for different budgets: roughly, smaller budgets cause a* to explore less. We will return to this in Section 3.3.3 and Figure 3.
3.3
An acquisition function class for cost-aware Bayesian optimization
To adapt a* to the Bayesian optimization setting, we need to handle two differences: (i) X does not need to be discrete, and (ii) a general probabilistic model is used for f. Since Theorem I ostensibly
5

---

Prior Distribution
Cost Function
Log Regret
1
10
10
0
5
10
1
0
3
-5
-5
10
20
30
40
Expected Improvement Per Unit Cost
Pandora's 's Box Gittins Index
Figure 2: Bayesian optimization problem with varying costs on which LogEIPC-a numerically stable implementation of EIPC, see Section 4 and Appendix D.1 poor performance, inspired by Astudillo et al. [4], Section A. The domain X = [-500, 500]. which we visualize on the subinterval [-5,5]. 5]. Left: illustration of the non-uniform prior variance, which is given by Matérn-5/2 kernel scaled by a narrow bump function. Center: the cost function, which a narrow bump-shaped function. Right: median regret curves and quartiles for LogEIPC and PBGL. Legend refers only regret curves.
requires f() to be independent of (a') for all x * x', the key question how to incorporate data and spatial correlations into a*. We propose do so the simplest and most obvious way: namely, at each time i, we plug the posterior distribution f xx Li Vise in place of f. This yields three variants, depending on the precise cost-aware setting one is interested in:
1. Budget-constraing ai
define Pandora's 's Box Gittins index (PBGI) acquisition function
(6) 2. Cost-per-sample: we can directly apply PBGI in this setting as well, but now À is instead interpreted as unit-conversion factor which ensures costs and rewards have the same units, and the Pandora's Box stopping rule is used for deciding when to terminate the optimization procedure and return the best observed value.
aPBGI
2 =
where g solves
Elf (I; g) Ac(x))
and is a hyperparameter that should be tuned to match the evaluation budget B.
3. Adaptive decay: here, do not have pre-defined budget cost-based stopping rule. Define the Pandora's 's Box Gittins index with adaptive decay (PBCI-D) acquisition function a PRGI-D (z) analogously to a (x)) but with time-dependent X, schedule, set according the Pandora's 's Box stopping rule. Specifically, Ao is initialized to a given value, then set
A
if a PBGI (x;;
A++1
X
otherwise
where 3 > is decay factor that is used to decrease Xy at any time when the Pandora's Box stopping rule triggers. The advantage of this variant is that it can be more robust to different ranges of the policy hyperparameters: discuss this further in Appendix D.3.
To understand this acquisition function class, can think of it via the following approximation: for the general cost-aware Bayesian optimization problem, we (a) correctly incorporate observed data into the prior obtain the posterior, but then (b) pick new samples according to the rule that would have been Bayesian-optima if the posterior had no correlations. Said differently, a PBGI arises from exactly solving simplified dynamic program, where the simplification is of spatial nature, rather than the usual temporal lookahead. One can therefore expect this acquisition function to work best in situations where correlations are not the decisive factor for determining performance.
In what problems does this happen? In stationary kernels, correlations encode local dependence. Therefore,
expect a PECI to be approximately-optinne in settings where the key decisions involve choosing between different far-away data points. One can intuitively expect this to oceur more often in high-dimensional problems, where the volume of the search space is large and most points are far away from each other. We will examine this point empirically in the sequel.
3.3.1 Computation. To compute a PBGT efficiently, note that + EI y) is monotone. As result, the value g in (6) can be computed efficiently via bisection search. In Appendix B.2, we show that (i) the gradient of a. PBGI can be computed straightforwardly via an explicit analytical expression without any additional optimization, and (ii) the resulting computational costs are eloser to those of expected improvement than those of expensive multi-step-lookahead based approaches.

---

Expected
PBGI
PBGI
Log Regret
Improvement
10
X = 10-5
5-10"
À = 10-3
Std. Dev.
4
À 10-1
2
10
10
Dynamic
3
0
3
0
3
3
50
100
150
200
75th quantile
Mean
Cumulative Cost
Median
25th quantile
Figure 3: Left: contour plots showing how El (left) and PBGI (center-left, center-right) depend on the posterior mean and standard deviation given point (lighter colors indicate higher values). We see that PBGI values high standard deviation more than EI. Right: PBGI performance across values of X, under the setup of the Bayesian regret experiment of Section 4 with d = 8. We plot the median of set of samples using n = 256 random seeds, along with quartiles to show variability. We see that large X-values decrease regret sooner, but eventually lose out to smaller X-values.
3.3.2 Extension to stochastic and non-audomaffclll--dffeeeeee diffeeeetdiieeeeetabbblele costs. One can show that Theorem holds in the more general case where the cost function is random, as long as one substitutes c(x) with its mean. The same holds for Theorem 2, as shown in Appendix B.5. In this setting, therefore, stochasticity of c(z) affects performance, but does not change the optimal strategy. Building these observations, we propose extensions of a; PBGI the more general setting where costs are modeled using a log-normal process in Appendix B.4.
3.3.3 Qualitative behavior and comparisons. Compared cost-unaware acquisition functions such as EI. PBGI can be more risk-averse if costs are large or more risk-secking if costs are small. In varying-cost budgef-constrained settings, this tradeoff is mediated by A, and the obtained decisions can differ significantly from those of widely-used baselines such as EIPC. In particular, PBGI can make qualitatively different decisions on problems where there a high-variance point with large cost, among set of many low-variance low-cost points. In Figure 2, we adapt the construction of Astudillo et al. [4], Section into a one-dimensional Bayesian optimization problem with a non- stationary prior, and observe that EIPC-even in its numerically stable logarithmic form described in Section has substantially worse performance than PBGI.
The PBGI acquisition functions depends on f Fist, through its mean and standard deviation at each point. We plot this in Figure This shows for large that PBGI can resemble EI, whereas for small À it is nearly linear. Specifically, in the X - 0 limit, we have
oI(-) PBGI (-) 2 m)() + + 2 log Xc(.))
(8)
where He and o, the and standard deviation of f F1:t; V1a- This expression is similar to the upper confidence bound (UCB) acquisition function whose dependence is exactly linear,
with heterogeneous learning rate parameter set to = 2 An(m)) derivation is given in Appendix B.3. For small X, confidence parameter in a careful way depending on c(x)
0,(2]
thus view PBGI giving way automatically tune UCB's
4 Experiments
We now empirically evaluate the Gittins-index-bane acquisition function on cost-aware problems. We also evaluate on the same problems with a spatially-constant cost function, setting term uniform costs- this facilitates comparisons with classical, cost-unaware baselines. In both cases, mirroring practical settings, work with deterministic.
iniithnm-iddeeeddeet evaluation budget.
We implement all methods BoTorc [5] using Matérn Gaussian processes with smoothness v = 5/2. For Bayesian regret experiments where objectives are sampled from the prior, we fix the length scale to be x = 10-1 for both the prior and the posterior. For synthetic and empirical experiments, apply maximum marginal likelihood optimization to dynamically adjust the length scale every
7

---

d 8
d = 16
d = 32
Uniform-or cost "arying-cost
5-100
7-10%
9-10%
Log Regret
10
100
8-100
50
100
150
200
100
200
300
400
200
400 600
800
5-100
7-10"
10
100
2.100
3-10
0
100
200 300
400
0
200
400 600 800
0
200 400 600 800
Cumulative Cost
LPCE
(B)MSEI
(MF)MES
TS PBGI-D
UCB
75th quantile
Median
KG
LogEICC
PBGI
RS
25 quantile
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, well as MSEI for d = 8. However, for d = 32, all methods perform comparably to random search, with PBGL, PBGI-D, LogEI, and UCB having pear-identical median performance. See Figure 14 for an alternative visualization using mean and standard error.
iteration. To ensure that our results are not sensitive to these and other hyperparameter choices, all experiments were repeated with alternatives given in Appendix D.6. Each experiment repeated for 16 seeds to assess variability, unless stated otherwise. Experimental details are in Appendix C.
We evaluate both PBGI variants from Section 3.3, namely a PBGI with À = 10-4, and a PBGI-D with Ao = 10-1 and = 2. To assure ourselves that performance differences are not primarily due to tuning, we deliberately use the same X-values for PBGI and the same (No, -v-vulu for PBGI-D on all problems. Comparisons with other (Aa, -v-lue can be found in Appendix D.3.
For varying-cost problems-that that is, those with spatially non-constant cost-we we compare with (log) expected improvement per unit cost (LogEIPC) [37,38], 38], (log) expected improvement with cost cooling (LogEICC) [27], multi-fidelity max-value entropy search (MFMES) [40] and budgeted multi-step expected improvement (BMSEI), [4], which was shown in that work to have state-of-the-at cost-aware performance. For uniform-cost problems-that is, those with constant costs-we compare with log expected improvement (LogEI) [2], Thompson sampling (TS), upper confidence bound (UCB) [39], max-value entropy search (MES) [42], knowledge gradient (KG) [17], and multi-step expected improvement (MSEI) [24]. We choose these because (i) they are standard, and (ii) acquisition function optimization succeeds for them on our problems, reducing confounding. We work with logarithmic expected improvement variants (LogEl, LogEIPC, LogEICC), as they have recently been shown to have substantially better numerical and optimization properties than their traditional counterparts [2]-sce see Appendix D.I for details.
4.1 Bayesian regref
For our first experiment, we examine how well the proposed acquisition functions perform on random functions sampled from the prior. To quantify the effect of problem difficulty, we vary the dimension of the domain X = [0, 1]", and consider d E {8, 16, 32}. Results, in terms of empirical regret curves and their associated quartiles, are shown Figure demonstrating comparable performance between both PBGI variants and all baselines, as well as sensitivity comparisons involving the Gaussian process prior with varying kernel hyperparameters such different smoothness values and length scales, are included in Appendix C.
Additional results for =
8

---

Ackley
Levy
Rosenbrock
Uniform-cost
10a
10
10c
10-1
10
10
Log Regret
10s
40
80
120
160
40
80
120
160
40
80
120
160
4.100
10a
Varying-cost
10s
10
10
10
3-10-1
0
100
200
300
400
0
100
200
300 400
0
100
200
300 400
Cumulative Cost
LPC)
(B)MSEI
(MF)MES
TS
UCB
75th quantile
Median 25th quantile
KG
LogEICC
PBGI
PBGI-D
RS
Figure 5: Synthetic benchmark regret curves, shown using medians, well quartiles assess variability. All objective functions are defined with dimension = 16. We see in the cost-aware setting that PBGI, PBGI-D, LogEIPC, and LogEICC all perform similarly the heavily-multimoal Ackley function, matching or outperforming the non-myopic BMSEI baseline. On the Levy and Rosenbrock functions, PBGI-D matches-and -nd 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.
the low-dimensional case of 8, PBGI and LogEl variants achieve similar or better performance to the non-myopic MB) bascline. Once increase dimension d 16, see bigger differences, with PBGI variants, LogEl variants, and UCB now decisively outperforming (B (B)M.EL. Notably, the PBGI variants also competitive in the uniform-cost setting-in spite of being designed for cost-aware problems. This can be explained via the curse of dimensionality: as dimension increases, the problem begins to look more like the uncorrelated Pandora's Box problem where using Gittins index is Bayesian-optimal
Eventually, however, the problem becomes too difficult for meaningful progress to be made within our computational budget, seen for the uniform-cost problem with d = 32, where all deterministic methods perform near-identically and no method outperforms random search.
4.2 Synthetic benchmarks
Next, we consider standard synthetic global optimization benchmark functions. To represent a variety of geometric properties, examine the Ackley, Levy, and Rosenbrock functions. visualization of the two-dimensional versions these functions is given in Appendix A.
Figure 5 presents results for d = 16. Additional results for d (4, 8) showing that PBGI and all baselines perform similar, are given in Appendix C. We see that the behavior of different acquisition functions varies according the the function. On the Ackley function, PBGI outperforms PBGI-D and the basclines. contrast, on the Levy function, PBGI best in the uniform-cos cost setting, but PBGI-D, LogEIPC, and LogEICC are best in the varying-cos setting. We conclude that PBGI can in principle offer stronger performance than PBGI-D, as long as is not-too-suboptimal. while PBGI-D tends to be less-performant but is more robust this hyperparameter choice.
We also examine performance on the banana- -haped- Rosenbrock functiion which has a small number of local optima [35]. In this case, PBGI-D performs the strongest, matching the LogEl variants, while outperforming PBGI and (B)MSEI. This can intuitively be explained by the one-step optimality of expected improvement, which better-exploits the less-multimodal objective, while PBGI and multi-step-basee acquisition functions are more conservative and may therefore require different tuning to perform best. We conclude that PBGI-D may be better choice in settings where there is

---

Pest Control
Lunar Lander
Robot Pushing
300
112/1
Uniform-cost Varying -ost cost
- 14
Best Observed Value
15
200
1111/2
16
100
113/4
-17
25
50
75
100
50
100
150
200
0
50
100
150
200
-14
300
10
-55
200
11
-6
100
11
-17
200
400 600
800
1600
3200
0
200
400
600 800
Cumulative Cost
LPC)
(B)MSEI
(MF)MES
TS
UCB
75th quantile
Median
KG
LogEICC
PBGI
PBGI-D
RS
25th quantile
Figure 6: Empirical benchmark regret curves, shown using medians, well quartiles show variability. We see in both the varying-cost and uniform-cost settings that PBGI exhibits strong performance the Pest Control and Lunar Lander problems. On the Robot Pushing problem, LogEl 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.
potential mismatch between the objective and the prior in terms of degree of multimodality, this can be counteracted in part by its decay behavior, particularly compared to PBGI.
4.3 Empirical objectives
Finally, we benchmark PBGI policies on three empirical global optimization problems motivated by applied challenges: Pest Control where d = 25 [31], Lunar Lander where d = 12 [15], and Robot Pushing where d 14 [42]. Detailed descriptions of these problems and associated cost functions are in Appendix C. Note that, for Lunar Lander and Robot Pushing, the cost functions To handle this challenge and illustrate how our acquisition
used are not pooomattcally-dfffeeennic function can be used when the cost function is unknown, we apply unknown-cost PBGI and baseline variants, where the costs are modeled using second independent log Gaussian process: details on this unknown-cost PBGI variant, including its analytic form, are given in Appendix B.4.
From Figure 6, we see that the PBGI matches or outperforms baselines on Pest Control and Lunar Lander, in both the varying-cost and uniform-cost settings. On the other hand, PBGI performs poorly on Robot Pushing, where instead LogEl variants perform best and PBGI-D performs second-best, the non-myopic BMSEI baseline also performs poorly. This mirrors behavior previously seen on the Rosenbrock function, from which we suspect that a mismatch between prior and objective multimodality may be at play here as well. Note also that unlike in the Bayesian regret experiments, UCB's performance is far from strongest. This may be in part because we tune UCB using the schedule of Srinivas et al. [39], which is derived specifically for Bayesian regret, and may be less-ideal for other settings. comparison, PBGI-D works reasonably well on five of the six cases.
Conclusion
In this paper, we introduced a new acquisition function class for cost-aware Bayesian optimization, the Pandora's 's Box Gittins index, based on an unexplored connection between Bayesian optimization and the Pandora's Box problem from economies. We observed promising performance from two variants of this acquisition function class on both cost-aware problems which are the focus of this work, and, additionally, on classical uniform-cost problems. Performance gains tended to largest on dighee-dimmeniionll and multi-modal problems. Our work constitutes first step toward integrating ideas from Gittins index theory, including insights from generalizations Pandora's 's Box, and related areas such as queueing theory, into Bayesian optimization.
10

---

Acknowledgments
We thank James I. Wilson for his suggestions, which helped us significantly improve the paper's presentation. AT is grateful to Anastasios Angelopoulos for hosting him at UC Berkeley on November 17th, 2022: though the visit and planned talk that day had to be cancelled last-minute due labor strikes, the cancellation ultimately resulted in an unexpected chain of events that, months later, led to AT and ZS exchanging ideas about Gaussian processes and Gittins index theory, which ultimately led to this work. PF was partially supported by AFSOR FA9550-20-1-D53 NSF under grant numbers CMMI-2307008, DMS DMM-2023528, and DMS-2022448. AT was supported by Coreell University, jointly via the Center for Data Science for Enterprise and Society, the College of Engineering, and the Ann S. Bowers College of Computing and Information Science.
ZS was supported by the
References
[1] S. Aalto, U. Ayesta, and Righter. On the Gittins Index in the M/G/1 Queue. Queueing Systems, 2009. Cited on page 2.
[2] S. Ament, S. Daulton, D. Eriksson, M. Balandat, and E. Bakshy. Unexpected Improvements to Expected Improvement for Bayesian Optimization. Advances in Neural Information Processing Systems, 2023. Cited on pages 8, 28, 29.
[3] M. Aminian, V. Manshadi, and R. Niazadeh. Markovian Search with Socially Aware Constraints. Management Science, 2024. Cited on pages 5, 23.
[4] R. Astudillo, D. Jiang, M. Balandat, F. Bakshy, and P. I. Frazier. Multi-step Budgeted Bayesian Optimization with Unknown Evaluation Costs. Advances in Neural Information Processing
Systems, 2021. Cited pages 1, 3, 6-8, 15, 17, 26, 28, 30.
[5] M. Balandat, B. Karrer, D. Jiang, S. Daulton, BoTTorc:: A Framework for Efficient Monte-Carlo Bayesian Optimization. Advances in Neural Information Processing Systems, 2020. Cited on pages 3, 7, 26.
Letham, A. G. Wilson, and E. Bakshy.
[6] T. Başar and Bernhard. H -optimall Control and Related Minimax Design Problems: Dynamic Game Approach. Springer, 2008. Cited on page 25.
[7] S. Belakaria, J. R. Doppa, N. Fusi, and R. Sheth. Bayesian Optimization over Iterative Learners with Structured Responses: A Budget-aware Planning Approach. Artificial Intelligence and Statistics, 2023. Cited page 1.
[8] D. Bertsekas. Nonlinear Programming. Athena Scientifie, 1999. Cited on page 25,
[9] J. Bonnans and A. Shapiro. Perturbation Analysis of Optimization Problems. Springer, 2013. Cited page 25.
[10] S. P. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Cited on page 24.
[11] S. R. Chowdhury and A. Gopalan. On Kernelized Multi-armed Bandits. International Confer-
ence on Machine Learning, 2017. Cited on page 3.
[12] J. M. Danskin. The Theory of Max-min and its Application to Weapons Allocation Problems.
Springer, 1967. Cited on page 25.
[13] L. Doval. Whether or Not Open Pandora's Box. Journal of Economic Theory, 2018. Cited
on page 2.
[14] I. Dumitriu, P. Tetali, and P. Winkler. On Playing Golf with Two Balls. SIAM Journal on Discrete Mathematics, 2003. Cited on page 2.
[15] D. Eriksson, M. Pearce, J. R. Gardner, R. D. Turner, and M. Poloczek. Scalable Global Optimization via Local Bayesian Optimization. Advances in Neural Information Processing Systems, 2019. Cited on pages 10, 27.
[16] P. I. Frazier. Bayesian Optimization, Recent Advances in Optimization and Modeling of Contemporary Problems. 2018. Cited on page 3.
[17] P. L. Frazier, W. Powell, and Dayanik. The wwwllede-grrddeee Policy for Correlated Normal Beliefs. INFORMS Journal Computing, 2009. Cited page 8.
[18] R. Garnett. Bayesian Optimization. 2023. Cited pages 2, 3.
[19] J. C. Gittins. Bandit Processes and Dynamic Allocation Indices. Journal of the Royal Statistical
Society, Series B: Statistical Methodology, 1979. Cited on page 16.

---

[20] J. C. Gittins, K. D. Glazebrook, and R. R. Weber. Multi-armet Bandit Allocation Indices. Wiley, 2011. Cited on pages 2,
[21] D. Glazebrook and J. Niño-Mora. Parallel Scheduling of Multiclass M/M/m Queues: Ap- proximate and Heavy-Traffic Optimization of Achievable Performance. Operations Research,
2001. Cited on page 2.
[22] A. Gupta, H. Jiang. Z. Scully, and S. Singla. The Markovian Price of Information. Integer
Programming and Combinatorial Optimization, 2019. Cited on page 2.
[23] J. M. Hernández-Lobato, M. W. Hoffman, and Z. Ghahramani. Predictive Entropy Search for Efficient Global Optimization of Black-box Functions. Advances in Neural Information Processing Systems, 2014. Cited on page 26.
[24] S. Jiang. D. Jiang, M. Balandat, B. Karrer, R. Gardner, and R. Garnett. Efficient Nonmy- opic Bayesian Optimization via One-shot Multi-step Trees. Advances in Neural Information Processing Systems, 2020. Cited on pages 1, 8, 26.
[25] R. Kleinberg, B. Waggoner, and E. G. Weyl. Descending Price Optimally Coordinates Search. Economics and Computation, 2016. Cited on pages 5, 20, 21.
[26] E. H. Lee, D. Eriksson, V. Perrone, and M. Seeger. A Nonmyopic Approach to Cost-constrained
Bayesian Optimization. Uncertainty in Artificial Intelligence, 2021. Cited on page I.
[27] E. H. Lee, V. Perrone, C. Archambeau, and M. Seeger. Cost-aware Bayesian optimization. Automated Machine Learning, 2020. Cited pages 8, 26.
ICML Workshop
[28] Y. L. Li, T. G. J. Rudner, and A. G. Wilson. A Study of Bayesian Neural Network Surrogates for Bayesian Optimization. International Conference on Learning Representations, 2024.
Cited pages 28.
[29] R. Martinez-Cantin. Bayesian Optimization with Adaptive Kernlls for Robot Control. Interna- tional Conference on Robotics and Automation, 2017. Cited on page 1. [30] P. Milgrom and I. Segal. Envelope Theorems for Arbitrary Choice Sets. Econometrica, 2002.
Cited on pages 23, 24.
[31] C. Oh, J. Tomezak, E. Gavves, and M. Welling. Combinatorial Bayesian Optimization using the Graph Cartesian Product. Advances in Neural Information Processing Systems, 2019. Cited on pages 10,27.
[32] E. Persky. Exploration and Exploitation: From Bandits to Bayesian Optimisation. MPhil Thesis, University of Cambridge, 2021. Cited on page 2.
[33] C. E. Rasmussen and C. K. Williams. Gaussian Processes for Machine Learning. MIT Press,
2006. Cited on pages 3, 30.
[34] Z. Scully, I. Grosof, and M. Marchol-Balter The Gittins Policy is Nearly Optimal in the
M/G/k under Extremely General Conditions. Measurement and Analysis of Computing Systems, 2020. Cited on page 2.
[35] Y.W. Shang and Y.HH. Qiu. A note on the extended Rosenbrock function. Evolutionary Computation, 2006. Cited on page 9.
[36] S. Singla. The Price of Information in Combinatorial Optimization. Symposium on Discrete Algorithms, 2018. Cited on page 2.
[37] E. Snelson, Z. Ghahramani, and C. Rasmussen. Warped Gaussian Processes. Advances in Neural Information Processing Systems, 2003. Cited on page
[38] J. Snock, H. Larochelle, and R. Adams. Practical Bayesian Optimization of Machine Learning Algorithms. Advances in Neural Information Processing Systems, 2012. Cited on pages 1, 3, 8. [39] N. Srinivas. A. Krause, S. M. Kakade, and M. Seeger. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. International Conference on Machine Learning. 2010. Cited on pages 8, 10, 26.
[40] S. Takeno, H. Fukuoka, Y. Tsukada, T. Koyama, M. Shiga, I. Takeuchi, and M. Karasuyama. Multi-fidelity Bayesian Optimization with Max-value Entropy Search and its Parallelization. International Conference on Machine Learning, 2020. Cited on page 8
[41] A. Terenin. Gaussian Processes and Statistical Decision-making in Non-Euclidean Spaces.
PhD Thesis. Imperial College London, 2022. Cited on page 14.
[42] Z. Wang and S. Jegelka. Max-value Entropy Search for Efficient Bayesian Optimization.
International Conference on Machine Learning, 2017. Cited on pages 8, 10, 28.
[43] R. R. Weber. On the Gittins Index for Multiarmed Bandits. Annals of Applied Probability, 1992. Cited on page 2.
12

---

[44] M. L. Weitzman. Optimal Search for the Best Alternative. Econometrica, 1979. Cited on pages 2, 16, 17, 20.
[45] J. Wu, S. Toscano-Palmerin, P. I. Frazier, and A. G. Wilson. Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning. Uncertainty in Artificial Intelligence, 2020. Cited
on page 3.
[46] X. Yue and R. A. Kontar. Why Non-myopic Bayesian Optimization is Promising and How Far Should We Look-ahead? A Study via Rollout, Artificial Intelligence and Statistics, 2020. Cited on page 1.
[47] Y. Zhang, D. W. Apley, and W. Chen. Bayesian Optimization for Materials Design with Mixed Quantitative and Qualitative Variables. Scientific Reports, 2020. Cited on page 1.
13

---

(a) Ackley
(b) Levy
(c) Rosenbrock
Figure 7: An illustration of the two-dimensional Ackley, Levy, and Rosenbrock functions.' 1 From the visual, one can see that these functions differ in terms of multimodality and ridge-regions within the optimization landscape.
A
Illustrations
Here we provide set of additional illustrations to aid understanding of our results.
A.1
Visualization synthetic benchmark functions
To better understand how the behavior of Bayesian optimization algorithms on the three different synthetic benchmark functions might be affected by their geometric shape, Figure provides visual illustration of their two-dimensional variants.' This allows us to visually see the multimodality of the Ackley function, multimodality and ridge-like regions
Levy function, and banana shape Rosenbrock function. While use nigher-dimensiona. versions of these in our experiments, this illustration provides some intuition for what the resulting the optimization landscape might look like, helping contextualize results.
A.2 Comparison of behaviors between EI and PBGI
In Figure 8, we see that El's maximum occurs at point near 0.365, which is located closer to the observed data and is fairly close to the maximum of the posterior mean. Similarly, large- PBGI's maximum occurs a similar point near x 0.358, indicating that the algorithm makes similar decisions in spite of the fact that the acquisition function's shape is different. In contrast, small-A PBGI's maximum occurs point near 0.86: favors riskier approach, preferring location where the mean is smaller, but the variance is larger.
Expected Improvement
Large- PBGI
Small-À PBGI
5
Posterior
3
-1
-1
Acquisition
0.9
9
0.4
4
-0.1
-1
0.25
0.5
0.75
0 0.25 0.5
0.75
1
0.25 0.5 0.75
Figure Comparison between three acquisition functions, namely Expected Improvement (EI), Pandora's Box Gittins Index (PBGI) with a large X-value of À = 10", and Pandora's ''s Box Gittins Index with small X-value of À 10-5 All three are computed using the same posterior distribution with four data points. The maximum is shown as large dot.
TThi visual originally appeared in Terenin [41], and reproduced here with permission.
14

---

Prior Distribution
Cost Function
Log Regret
1
10
4-10"
0
5
10"
0
2-10-
10
20
30
40
Log Expected Improvement (cost (casa-unaware)
Pandora's ' Box Gittins Index
Figure 9: A Bayesian optimization problem with varying costs which LogEI, numerically stable implementation of EI EI-which by construction ignores costs-has poor performance. See Section and Appendix D.I 1.1 for additional details. Like Figure 2, this construction also mirrors Astudillo et al. [4], Section A. The domain is = [-500, 500]. which we visualize on the subinterval [-5, 5]. Left: illustration of the non-uniform prior variance, which is given by Matérn-5/2 kernel scaled by narrow bump function, plus a constant. Center: the cost function, which a narrow bump-shaped function. Right: regret curves, shown medians and quartiles.
This example shows potential differences in behavior between El and PBGI, and illustrates how these differences mediated by the parameter X.
A.3
An example where expected improvement underperforms
In Section 3.3.3, we showed cost-aware Bayesian optimization problem on which the logarithmic form of expected improvement per unit cost (LogEIPC) has poor performance. Here, we show that this problem can be modified so that the logarithmic form of ordinary expected improvement (LogED, which ignores the cost function, also has poor performance-4 somewhat obvious, but nonetheless important sanity check that we make to ensure that costs play a iefticientlyiimportee role in problems of this class merit their consideration. This is shown in Figure 9. It is not hard construct coss-vsualizzationiiie friendll variant of these problems on which both expected improvement per unit cost and ordinary expected improvement perform poorly, by considering cost functions which pppropriately-weightee. sums of bump functions.
B Theory and calculations
Below, we provide additional ideas help understand the Pandora's Box problem and acquisition function that results from its considerations.
B.1 Additional intuition on Pandora's Box
In what follows, we sketch viewpoint from which holds. Rather than considering the full Pandora's Box problem with a general set of open and closed boxes, consider first the case where there is exactly one closed and one open box. To slightly simplify notation, let f denote the random reward inside the closed box, let e denote the cost of opening the closed box, assumed deterministie, and let g denote the visible reward of the open box. Our possible actions are as follows:
see the key idea behind why Theorem I
1. Open the closed box. In this case, pay cost of c, but subsequently get choose between taking the realized value f. or instead taking from the box that was originally open. In expectation, the total value obtained by taking this action is E[max(] ()) c.
2. Take the reward from the open box. The total value obtained is g.
We can therefore analytically solve for the optimal policy of this respective Markov decision process: we open the closed box if E(max(f.g)) E(max(ffg))
2 9. and take the reward from the open box if S g. with both actions optimal in the case of equality. As consequence, if is such that both actions are optimal, the same value is obtained no matter whether one chooses to open the box or not. Rewriting the preceding expressions slightly, this occurs when
E max(f 9, 0)
(9)
15

---

where in the case of multiple boxes the feft-hand-sie becomes the expected improvement function. The insight of Weitzman [44]-and and indeed of Gittins [19] in a much more general setting-is that one can modify the Pandora's 's Box Markov decision process by replacing closed boxes with open boxes whose value g satisfies (9) without changing the optimal policy. As a consequence, the optimal policy is precisely the Gittins index policy of Theorem 1.
As final point, note that the assumption that is deterministic made without loss of generality: if is instead stochastic but has finite expectation, the same reasoning applies, but with the value in (9) replaced with its expected value. We will make use of this in Appendix B.4.
B.2 Gradient of the PBGI acquisition function
In most Bayesian optimization setups, gradient-based methods including multi-start stochastic gradient descent, BFGS, and L-BFGS-B, are used to effectively optimize analytical acquisition functions, such as El and UCB. These methods can also be used to optimize the PBGI acquisition function. To facilitate this, we provide the gradient formula for the PBGI acquisition function. In what follows, mirroring the preceding and following sections, costs are stochastic then c(z) should be replaced with its respective mean. We also omit time subscripts to ease notation.
Proposition 3 (Gradient of PBGI). Let f(x)) and a (x) be the mean and standard deviation of the posterior Gaussian process (f F1:ts (2)) With this notation, the gradient of the acquisition function a (x) is given by
p(a) PBGI (m)
Vo(x)) - -Ve(e)))(())
Va Va PBGI (x)= = Vv(()) +
(
(10)
p(x) (LC)--PBGILA (B)
(()
where e and & denote the density and cumulative distribution function of a standard normal distribu- tion, respectively.
Proof. Recall that when (xx) ~ (((())),(())) is Gaussian, the expected improvement with respect to the comparator y given as
Elg (z: y) (p(z) - y) [((x) - y
o(x) ((60))0)
) + =z))
u(x) - y
(11)
o(x)
Next, note by definition of PBGI, we have
El fl (z; a PBGT (z)) = Ac(x).
(12)
Differentiating this with respect on both sides gives
El El (z; a (BGI(())) AVc(z).
(13)
Applying the product and chain rule to the left-hand-side gives
V El fa (z; PBGI (x)) = (V)(z)- - V PBGI PBG) ((x) -a (BG
(14)
+ (m(x) a PBGI (x)) u(x) (a)))))B V m(x) a (x)
(B)
(15)
(lx)
(x))
(1(x) a PBGI
+ Vo(z)
(16)
olx)
((xx) (BGI
p(x)) - a PBG (ar)
+
(17)
alz)
(xx)
Recall the identity for the derivative of the Gaussian density. namely
o'(x) =26(x).
(18)
Applying this identity to (17) gives
o (x) ( [(xx) - a PBG1 (x:
u(x)) a PBGI (x)
(19)
(ax)
(xx)
(1(x)= - a (PGGI (x)
4 (4(3r) - a PBGI (x)
= =-(((x)) a PBGI (TBGI(r)))
(20)
(xx)
o (xx)
16

---

which is equal to the negation of (15), hence (15) and (17) cancel: we get
[u(z) - a PBGI xx) Vo(z)
((x)) - a PP (x)
(Vμ(z)) - Va (x))
\Vc(x). (21)
o ((z)
Rearranging this gives the expression the claim.
B.3 Small-cost limit of PBGI acquisition function
We now derive the small-X limiting expression for PBGI which was presented in Section 3.3.3.
According to (11) and (12), have
at where 14 and og are the mean and the standard deviation of f 31a, Ui.t, and u(-) is the solution of
. pa(+) (-)(()(-)
(22)
u(:) + ((u(.)) Ao(-)
(23)
When A- 0, the solution satisfies u(-) + -o. This implies that both 2(u(-)) and dbu(-)) +
0. Since ((u(-)) dominates ((u(-)), we can approximate the solution uu.) by <(u(.)) ~ Ac(-)
o.() By
substituting the probability density function of a standard normal distribution for o we obtain
ax(+) xc(-)
u(.) -
2 log
(24)
Thus, we can conclude that the limit
+ O, the Gittins index becomes
(<((1)) (x((x))
PBGI at
(x; A) = (x(x) (0)))
2
(25)
As consequence, we expect PBGI-D, whose X-parameter eventually decays to zero, to potentially inherit consistency and other properties known for UCB. Specifically, since PBGI-D decreases the value of À to zero over time by dividing it with a constant every time the Gittins stopping rule triggers, its behavior should eventually be well-described by the above limit. As result of this limit, unexplored regions where (x) >> 0 should eventually have acquisition values that are larger than regions where a (x) O. We believe this should hold regardless of whether the costs are known-our main focus or unknown, especially if the cost function c(z) is uniformly bounded above and below.
This because (25)'s dominant term in the À - 0 limit is ar (1x) log X. which does not depend on the cost c(x).
B.4 Closed-form expression for the PBGI unknown-cost variant
In the Lunar Lander and Robot Pushing empirical examples of Section 4, the cost function does not admit an analytic, manner. To handle this, we model the logarithm of the costs as Gaussian process, and condition this process on the costs observed locations evaluated so far. This mirrors how unknown costs are handled in Astudillo et al. [4] for other acquisition functions, such as EIPC and BMSEI.
aoaomattcally-diffeeenttll form, and can only be evaluated in a black-box
From the viewpoint of the Pandora's 's Box problem, stochastic costs make little difference: following the discussion in Appendix I. the optimality results of Weitzman [44] continue to hold even costs stochastie, so long as the costs in the formula for a* are replaced with expected costs. Mirroring this, if we plug in the mean of log-normal random variable into the definition of a PBGI we obtain the following acquisition function.
Definition 4. Let c(x) be log-normal for all x. For a dataset (I1,31), v1...., (IA, ye), let Pin and o be the posterior mean and posterior standard deviation of the log-costs. Define the UNKNOWN-COST PANDORA'S Box GITTINS INDEX ACQUISITION FUNCTION by
El (1; = >eepp (Min(()) + On (2)(
PRGLU (B) (x)=9 =g where 9 solves af
(26)
2
The interpretation of X, namely hyperparameter that determines the expected budget the algorithm will use before reaching its respective stopping time, is the same as the known-cost setting. One can define cost-per-sample and decay variants in the same manner well.
17

---

B.5 Relationship between expected budget-constrained and cost-per-sample problems
We now prove Theorem 2. In what follows, recall that the assumptions of Theorem are (i) X is discrete, (ii) [[(()] < do for all x. (iii) fx) and f'xx') are independent for x + x', and (iv) the budget satisfies B min c(r). Further, Theorem was stated for deterministic costs: more generally, allow for stochastic costs satisfying 0 < Ec(x) < oc, and in such cases instead define a" using the expected costs.
We begin by defining the Markov decision process (MDP) under study and stating the properties of it that we will use. Define:
1. States: let S S U aS be the union of two disjoint sets, namely the set 8 of non-terminal states and set as of terminal states. These are described below:
(a) Non-terminal states: let S consist of all finite sequences of length X taking values in {ø}, where numbers represent the reward inside an open box, and & represents closed box, along with terminal states described below.
(b) Terminal states: let 08 IR represent the reward of the box chosen by the learner.
2. Actions: let = X, where actions represent either opening a closed box, or taking a reward from an open box.
3. Costs: define the non-terminal cost function e: S A + R by c(8, a) c(a).
4. Rewards: define the terminal reward function Ör as R by 0r(8) =
5. Transition kernel: define a Markov transition kernel such that for a non-terminal state and an action a:
(a) If box is closed, that is, s, X, and corresponds opening this closed box, then the MDP transitions to a new state s', where s/ represents a random draw of the value box i and all other components s', for # remains the same as sj;
(b) box is open, that is, 8; E IR, and a corresponds taking the reward 8; from this open box, then the MDP deterministically transitions to terminal state s' =
This defines a class of time-homogeneous undiscounted Markov decision processes, parameterized by the reward distribution f, of bounded expected value, and cost funetion c. We consider Markov policies, which are probability kernels mapping states to probability measures over actions. For this class of MDPs, all such policies are guaranteed terminate in finite time, because at most one can open all the boxes before being forced to select one and thereby enter terminal state. As consequence, by standard MDP theory:
1. The value function ((T,)) S R well-defined, where the superscripts denote the policy and the cost with respect to which the MDP is defined.
2. The optimal value function (++.)) + also well-defined.
3. There exists an optimal policy (+:0) which achieves the optimal value V((.e).
4. The map R
X IR. defined by ((r.e) is affine for all π.
5. The map R
X IR defined by c + (+,c) convex, since it is supremum of affine functions.
We immediately note that this formulation extends cover two variations of interest:
1. Stochastic costs. One can handle this by replacing e with a probability kernel. In this case, letting m be the mean costs, we have V(a,e) = (().)) Using this, we henceforth work with deterministic costs without loss of generality.
2. Simple regret as terminal reward. One can also consider an MDP with stochastic terminal reward which subtracts the best-it- term supze f(x from the terminal rewards Ör given above-this gives an objective equal to simple regret up to a minus sign. Since this only changes the rewards up to random constant which is independent of the chosen actions, by linearity of expectation, the value function of this modified MDP equal to those of our MDP up to constant. We therefore omit this term without loss of generality.
18

---

The expected budget-constrained setting does not directly incorporate costs into the MDP itself: more precisely, takes c(s, a) within the MDP formulation, which means the value function of this modified MDP is ((a.0), Instead, costs are incorporated as a constraint set on the policy class one considers. With this notation, the values of the optimization problems for Bayesian-optima policy in the expected conget-constrained and cost-per-sampe problems are ebe
v(*e)
sup (T,00) = g
V(+.e) = sup V(T.e)
(27)
te
where IT is the set of all Markov policies, and the feasible set for the expected budget-constrained problem is
T(x) c(z))
T :I:l: E
T
S B
(28)
[=1
and (T*) is policy x's stopping time, that is
as} which is bounded above by [ < oc. This defines the optimization problems under study. Define the set of maximizers
T(*) inf
(29)
I
{ II (=.e))
v(*0} }
(30)
which is non-empty, since, as said above, by MDP theory the supremum defining (((.)) is achieved. Define also the of feasible policies which satisfy the constraints in tight manner, namely
T
II
(c) B,eq
II
(c)
E
Σ 1=1
c(x)) B
(31)
We are now ready to prove the claim question. For this, we employ a Lagrangian duality argument: loosely speaking. this will reveal the cost-per-sample À to be the Lagrange multipliers associated with the expected budget constraint. We prove the main claim via a series of lemmas, starting from handling the Lagrange-
Lagrange-multiplier multimlier-ppiii part of the argument.
Lemma 5. Define the function
A: 10, 00) + R
A(A) V((.cc) + AB.
(32)
Suppose that the infinum of A is achieved, and denote by XB E oo). Suppose further that there exists an optimal policy for the cost-per-sample MDP for which the expected budget constraint is tight, namely ă E [1(=)2g)) (1(())
B,aq Then we have
(R,c) ehc
v(+cc) ebc
(33)
Proof. We start by expressing the expected budget-constraaneed optimization problem in uncon- strained form via Lagrange multipliers, obtaining
((t.c) ebc
sup ((x00) sup inf =c
(
A
c(x,) - B
(34)
=Ill A20
1=1
T((m)
inf sup
(T.0)
>
E Σ c(xx) -
(35)
A20 rell
inf (p(tdc) + +BB A20
= inf A(A) X
(36)
where the second line follows from the Lemma 10 since the respective Lagrangian equals (= up constant, and the third line follows by definition of ((+,e)) is by definition the terminal reward minus the cumulative costs.
19

---

Now, suppose the infimum of A is achieved, and let X E [0, oo) be any minimizer. Then ((+. ebe
((tage) + BB Using this, and the fact that the policy मे by assumption achieves the supremum over supren V(xAze) and satisfies 7 E E we get
sup v(a,0) sup ((x.) + >BB= sup V(n + XBB.. sell
(37)
r
re
Thus, the optimization objectives, defining the expected budget-constrained problem and the cost-per- sample problem with costs ABc are equal up to a constant. Therefore, their minimizer sets coincide, and the claim follows.
Lemma 5 reveals that as long as the optimization problems arising from Lagrange multipliers are achieved, and the resulting policy ă is feasible, the expected budget-constrained problem will admit the same optimum as its associated cost-per-sample problem. By MDP theory, we know the supremum over 1I achieved: we now show the infimum involving is achieved as well, which essentially amounts to ruling out arbitrarily large À values.
Lemma 6. The map A is convex. Moreover, the infimum inf A(A) is achieved.
Proof. First, note that convexity follows straightforwardly from convexity of e + V(+ce) and the fact that the sum of convex functions is convex. Next, since the feasible set is À [0, oo) and the objective is convex, either the infimum is achieved, or the objective is non-increasing. We prove the latter property cannot hold. For this, first consider the policy n' that deterministically opens some box x' E X whose cost is c(x²) < B-note that our assumptions guarantee the existence of at least one such box-and selects the value in it. Therefore if we define (A) (= + AB, we have
A((A) V(K Ae) + XB V(+.e)) + AB A(A).
(38)
At the same time, we have ( Ae) = E fxx) - Ac(x') therefore
= E = (c(x') B)
(39)
negative
which means the map A'' is affine and strictly increasing with respect to A. Thus, the map A is lower-bounded by strictly increasing affine function, and therefore cannot be non-increasing. We conclude that the infimum is achieved.
The next part to show that the optimal cost-per-sample policy is feasible for the expected budget- constrained problem. Then to do so, we need to verify a certain convergence criterion, given below. In the following, note that X-which can be negative-is never used in the definition of any optimal policy, only to compute the value of a given policy, which still makes sense even with negative costs.
Lemma 7. For any monotone sequence An + where Xn > and X > and any X E RR there exist policies nă E ((())n))) and x² E (=((.cc) such that
v(raiee) - v(T
(40)
Proof. First, note that
T
V(r =V( Ae) +(()))+(+- An)
Σ c(xx).
(41)
Using this, by passing limits through the respective sums and products, it suffices to prove convergence of (a) and (b) separately, with the same sequence choice x; in both cases. By Weitzman [44] see Kleinberg et al. [25], Theorem 1, for an alternative proof-any any policies T T which maximize the respective Gittins indices o,,, a are optimal: we will therefore choose x; x² from this set of policies. This choice is not unique due to the possibility of ties, both in terms of which boxes to open, and when to stop: we will show that breaking choices do not affect convergence of (a), and will make suitable choice of bie-breaking rules, depending on the sequence Xn in the claim's assumptions, to prove convergence of (b).
20

---

Part I: convergence of (a). Define (x) = (z) and define k analogously. By Kleinberg al. [25]. Theorem 1, we have
v Anc) =
E max mnax,,(le (z)
(42)
=eX
and analogously for X, a", and s. We now argue that az + a' monotonically pointwise. Since An + À converges monotonically, consider
(I -xn(())
(43)
Recall that (1, g) continuous and strictly decreasing in gi hence, its inverse in g exists and is also strictly decreasing and continuous. We conclude that a + a² monotonically pointwise. From this, convergence of the respective expectations E max (z), and therefore convergence of (a), follows by the Monotone Convergence Theorem.
Part II: convergence (b). We will need an identity involving the order in which boxes are opened: for this, we first prove that once tie-breaking rule is chosen, for large enough xx and x' open boxes in the same order. Since the number of hoxes is finite, and of - a" monotonically pointwise from (a): it follows for large enough that, if there are no ties in a (ar), then ny opens boxes in the same order as π If there are ties in a², we choose a tie-breaking rule so that T and x open boxes in the same order. It follows that, once this choice is made, for large enough, all policies open boxes in the same order Ti, ",,,,,11j;; with different Tn and x possibly stopping at different times.
The identity we seek will differ depending on how tie- hiebbrek rules regarding when to stop are handled: recall that ties can occur when opening the box 24 E X at time t, we have a (z+) f? where fž is the best observed value up to time t. We adopt the following tie- biebbrakkng rule for stopping, depending on whether or not An an increasing or decreasing sequence:
If Xn is increasing: let nt . be the policy that opens the best closed box in the event of tie.
If Xn is decreasing: let n = n" be the policy that stops in the event of a tie.
Note also that An is both increasing and decreasing, it is constant, and the claim we want to prove holds: therefore, we suppose it is not, which makes the choice between म. and π- uniquely determined. We make the same tie-breaking choices for nH letting n and ग be the respective policies. Let x.x denote boxes in the order they are opened. Then the expected total costs are
X
X
E
c(aa)
p()())22)())) ()(x))
ii
P(f
S a" (2)), (((())
(44)
t=1
|X| 1-1
(iv)
ΣI
(45)
where (i) follows by writing the probability as an expectation of an appropriate indicator, (ii) follows by noting that under the policy wi. the event T(+1) 2 i occurs if and only if at each time j 1, ... i, the best observed value fÿ is not higher than the Gittins index of zy, (iii) follows by expanding the maximum which defines fÿ and using monotonicity of of (æz) in j to simplify the resulting events, and (iv) follows by independence of f(xx)) and f(xy)) ) for j + jr. Using this, it suffices to show
P(f(x,) S ( ((f(z))))(())))))))))) <a (z:))
if = -ी, and i =-- n
(46)
P(f(#,) < (z,)) P(f(z)) < (z:)))
(47)
The former equals the cumulative distribution function of f(xz), which is right-continnous, evaluated at a (I:). The latter is similar but is instead left-continuous. For Th. since A, is increasing, we have that ar (x) is decreasing, and the claim follows by right-continuity. For ,;,- since X is decreasing, we have that o,, (x) is increasing, and the claim follows by left-continuity.
We are now ready prove the key property needed apply Lemma 5.
Lemma 8. If N/g > O, then there exists ât e 11(t)Ab)) n (c)
B.eq
21

---

Proof. By the Envelope Theorem specifically,, Lemma 13 we have for À E [0, oo) that
).A(A)) 0, (2 (((,de)) + +AB)
(48)
T(
0, sup TETl
((T,0)
- E Σ dxa)
B
(49)
Oy
E
c(xi)
B
(50)
a r')
1=1
T(m)
vB- min TElI
c(21)
(51)
where all Gâteaux derivatives-see Definition are taken with respect to À and exist by convexity, and the pointwise convergence condition of Lemma 13 follows by first noting that
T
V(a.0) - Σ
c(xx) B = v(a,de) +AB
(52)
t=1
and applying Lemma 7. By the first-order optimality conditions, we have
0g.A(A)) 2 0.
(53)
Combining this with the above, we conclude
T(x) c(x,) vB.
min -A
V
(54)
t=1
Since AB 0, this expression holds for equal to +1: plugging this in, get
T(+)
T(
min A A2
E c(.))
B
E c(x,). c(x.) A
max
(55)
Now, let f_ be a policy from the minimizer set, and let R4 be a policy from the maximizer set. Define third policy R. which randomizes between the two, choosing f with probability and R. with probability - a. Since 7.+ and f_ are optimal, they achieve the same value, so by convexity n. also achieves the same value: therefore, 7. E (T(,e On the other hand, the expected total costs of f.a convex combination of the expected costs of f_ and 7. since the former lower-bounds B and the latter upper-bounds B, there exists an a E [0, 1] for which the costs of Ta are exactly B. Taking ãे n. for this value of a, obtain मे E (T()) and the claim follows.
|1
B,og
To complete the proof, we show the minimizer set of A does not contain zero. Lemma 9, Let X₂ E [0, oo) be any minimizer of A, then X; > 0.
Proof. From the derivative calculation used in proof of Lemma 8, plugging in 1 into the respective Gâtcaux derivative, we obtain
T(
d
A(A)= = B min
E
c(x)).
(56)
AA
If A = O, then the costs are zero: thus, any policy that opens every box, then selects the highest reward among opened boxes, is optimal. Therefore, we have T( = |X], and every optimal policy's cost equal the total cost of all the boxes. This gives
d Yd
A(O) B Σ (z) <0
(57)
ZEX
where the inequality follows by the assumption that the expected budget constraint active. The claim follows.
D
22

---

With these results at hand, we are now ready to prove the main claim. Theorem Consider the expected
problem, with the assumptions of Theorem 1. Assume the problem is feasible and the constraint is active, namely minlex c(x) < B < <> L c(z). Then there exists a À > and a tie-breaking rule such that the policy defined by maximizing the Gittins index acquisition function ox" (-), defined using costs Xe(x), is Bayesian-opiimal
Proof. Combine Lemma 5 with Lemmas 6, 8 and
We conclude by comparing this claim and proof with the results of Aminian et al. [3]:
1.
The objective of their expected budget-constrained problem is more general: while we focus on minimizing simple regret, Aminian et al. [3] study how to maximize utility, which is defined in a broader context- one example being the difference between the best observed value and cumulative costs, which we study here. Our expected budget constraint is similarly a special case, which, in their terminology. takes all weights on indicators denoting inspection to be identical, and takes all selection weights to be zero.
2. We do not assume that fax has finite support for all æ. This results in significant technical difference: we must apply sharp envelope theorem with an explicit supremum to conclude that the expected budget constraint is satisfied. More-straightforwardd results such as those presented by Milgrom and Segal [30], or their ceddifferentialffommllee
analogues in the proof of Aminian et al. [3], Proposition (iii), would not suffice: due to an explicit functions, without suitable structure,
found
counterexample involving one cannot conclude that the supremum is achieved and the resulting inequality is tight. As an alternative our approach, one could instead appeal finiteness of the class of deterministic policies- which Aminian et al. [3] assume, leading to piecewise-lineal value functions. We avoid these assumptions, leading to a more technical but more general argument.
We conclude by noting that one can also consider variants of the problems we have studied under an almost-sure budget constraint, for instance
pds)
11
(c) B,as
E II:
c())) B =1
V(a.c) asbe
sup
(v.0)) (58)
T B
For this problem, this optimal value is upper-bounded by the optimal value of the expected budget- constrained -itizattion-sccifccallll. asbe s v((..). since [](c]
((t..)
Cu [c)
B,as
B.6 Auxillary results from optimization theory
Below we state and prove three results from optimization theory: Lagrange Multiplier Theorem for optimization problems with inequality constraints, and two Envelope Theorems. These results are not new, but are difficult to find at the level of generality we need them at: most references begin by assuming the domain of optimization is Rd or, if not that, that it is Banach space, whereas we need results that hold when the domain of optimization is an arbitrary set, without linear structure or a topology. In light of this, we have found it easier to simply prove the claims we need.
Lemma 10. Let X be an arbitrary set, let f X -
IR and let X + R.
Then defining
f(x, X) f())= >(g(x) - v) for X 2 O. we have
sup f(x) sup inf L(x, A).
(59)
xe g(x)5y
=EX X20
Moreover, suppose there exist xt X which satisfy L(x", X²) = inf supzex L(I, A) and g(x*) Then we have
sup inf C(x, A) = inf sup L(x, A).
(60)
xex A20
X20 xEx
Proof. First, we show that for all x, we have
[xxx)
g(x) S y
inf L(x, A)
(61)
X
-o0 g(x) y.
23

---

To show this, suppose first that g(x) S y. Then M(g(x) y) - 0, hence its negation is non- non-negative, and minimized = Now, suppose the converse. Then {(g(z) y) > 0, so its negation is negative, and the objective can be made arbitrarily close to -xo by scaling A. Using this, write
sup inf C(x, A) max re
sup inf ((x, A), sup inf C(x, A) Fex X20 g(x)
(62)
=ex X20
g(z)>g
max
f(x), -00 g())SV
sup FE
= sup f(z). xx
(63)
g
We now argue that, under the claim's additional assumption, one can swap the order of the supremum and infimum. Letx", X" be pair for which the constraints are tight. Then
inf sup ((a, A se g<2)
@
sup aEX (
[(x, X²) i
sup C(x,A-)
(64)
TEX (x)==y
(i
sup
inf L(x, A)
(iv)
sup inf L(x,
(65)
DE A
=ex X
(<)==v
g(z)sy
where (i) follows by definition of X", (ii) follows by the fact that x² achieves the supremum and satisfies g(x*) =y y, (iii) follows by the fact that, when restricted to the set (x E X : g(x) = y).
C(x, A) is constant in À for all v-values, hence the infimum is taken over constant functions, (iv)
follows by making the feasible set larger. Combining this with the sup-inf inequality [10]
sup inl L(x, A) inf sup f(x, A)
(66)
rex A20 g
X20 zex
s(z)Sv
gives the claim.
easy to see that this argument holds even if one lets y take values in an infinie-diimensionll vector space, as long as X takes values within convex cone which is suitably paired with the aforementioned vector space, but we will not need this level of generality. The arguments we employ will be cleanest if we work with directional derivatives in the sense of Gâteaux, as opposed to left-derivatives and right-derivatives of real-valued functions, which in our setting are equivalent but require more management of minus signs. For this, we adopt the following notation.
Definition 11. Let X be topological vector space, let X C X, and let f X R be a function. The GÂTEAUX DERIVATIVE (x) E IR of function I at a point x E X in the direction X. if it exists, is defined as
f(x + +w)+ f(x)
0.f(x) = lim c+0+
(67)
Note that we require no properties of our Gâteaux derivatives: in particular, fx) can be non-linear in v, though one can easily see that it will always satisfy fax)(())= = a for 2 0. If f is convex function, one can show by monotonicity of finite differences that fx) always exists in the non-extended-valuee
sense defined above-as the relative interior of the effective domain of f.
Our arguments need an appropriate Envelope Theorem. The first statement we need is essentially equivalent to Milgrom and Segal [30], Theorem 1, which is formulated in the language of left- derivatives and right-derivatives: Milgrom and Segal [30] state in footnote that their claim also holds in general normed vector space, provided one works with directional differentiation. In fact, the claim is even more general than that, and does not require a norm. Since we find this variant to be particularly clean, elegant, and instructive, we prove the claim in full generality below.
Lemma 12. Let θ be subset of a topological vector space, and let X be an arbitrary set. Let f: x θ + R be bounded above in its first argument, and define V to be
(0) sup f(x,,)
(68)
xEX
24

---

Suppose that, for every I E G the supremumm is achieved, and let X (0) be the maximizer set. For any v, suppose that the Gâteaux derivatives (0) and (x, 8) exist and are finite-valud, with the convention that the Gâteaux derivative of f is taken in its second argument. Then
sup 0, 0) s O.V(
(69)
x (0)
Proof. Fix 9 E θ, and let (0) E (0) be an arbitrary maximizer. Note that, for all 0' E and all r ((') X (6"), by optimality we have
f(= 0') S ((x000)), V(0")
(70)
with equality for 0' 0. Letting& > be sufficiently small, taking O' EU, subtracting f()*(0), 0) ((0) from both sides, and dividing by we get
(0), + sv) ((x((0),)) V(O ev) V(0)
(71)
E
E
thus taking limits as E + gives
(x - (,V(
(72)
This holds for all choices x²) E Xx (8), and the claim follows.
For our arguments go through, we need sharper version of this result, with the inequality replaced with an equality. Results like this go back at least to Danskin [12]. and are proven by Bonnans and Shapiro [9], Proposition 4.12. Başar and Bernhard [6]. Theorem 10.1, 1, and Bertsekas [8]: however, all of their claims require topological assumptions on the domain of optimization. Moreover, it easy to see- see-for instance by considering an envelope made up of upside-down absolute value functions, where V(()) is constant but far 0) is not-that the inequality cannot be tight without similar assumptions. Below, we show that being affine in and a certain convergence criterion suffice, even if X is an arbitrary set. The argument is similar to that of the aforementioned references.
Lemma 13. With the assumptions and notations in Lemma 12, suppose further that far 0) is affine in for all x, and that for any monotone On - there exist x" (0n.) E (0,) and x (0) E (0) such that [xx (0n), + (0), Then we have
sup x*)x-(0)
0xf(x" ,0) max x (x)
0, 0.f(2 -,
(73)
Proof. For any e, note that
((0 + æv) V(0)
f(x Ev), + Ev) f(x
(74)
8
8
f(x ev), + Ev) s(x (0)
(75)
negative
f(x" (0 +ev). 0) ((x)
(76)
[(x + ev), 0 +v) [(x (0 (0)) ev),
(77)
E
f(x + Ev), v)
(78)
where the respective term is negative because f(x (0 ev), S (0))0),)) which holds by optimality of x (0). Taking limits gives
( < ((= fz (0)
(79)
where the final equality follows from the expression for the Gâteaux derivative of linear function. Combining this expression with the Lemma 12 shows that the respective supremum is achieved, and gives the claim.
25

---

C Experimental setup
We implement all experiments in BOTORCH Following standard practice, we initialize each optimization algorithm with 2(d + 1) values drawn using a quasirandom Sobol sequence, where d is the dimension of the domain. All computations were run on CPU, with individual experiments ran in parallel on various nodes of the Cornell G2 cluster, each allocated up to 4GB of memory, except for certain exceptions. These exceptions include KG, MSEI, and BMSEI for higher dimensions, which required substantially more memory, up to 32GB. Most individual runs took several minutes at most, with exception of the more-cxpensive KG, MSEI and BMSEI baselines: more information with a direct runtime comparison is given in Appendix D.2.
Gaussian process models. In the Bayesian regret experiments shown in Figure 4, we use Matérn nnmely both the Gaussian process prior used to sample the objective function, and the Gaussian process used for Bayesian optimization. To maintain consistency, we do not standardize data in this variant. For the synthetic and empirical experiments shown in Figure 5 and Figure 6, we use Matérn kernels with smoothness 5/2 and length scales learned from data via maximum marginal likelihood optimization, and standardize input variables to be in [0, 1] along with output variables to be zero-mean and unit-variance, following BoTorch defaults. In the unknown-cost experiments, we model the objective and the logarithm of the cost function using independent Gaussian processes. Additional Bayesian regret experiment results. showing the effect of varying the kernel smoothness and length scale hyperparameters, are provided in Appendix D.6.
kernels with identical fixed hyperparameters -nmelyy smoothness 5/2 and length scale 10-1-for for
Acquisition function optimization. This is done as follows. We begin by computing acquisition values at 200d points spread across the domain X, where is the dimension of X. For all acquisition functions except MSEI and BMSEI, which use modification described below, the initial 200d points are generated using Sobol sequence design. From these, 10d points are selected according to the initialization heuristic used by BoTTorc,, detailed in Balandat et al. [5], Appendix F.I. We then use multi-start L-BFGGSB B to optimize the acquisition function from each selected point. The point with highest acquisition value among the 10d optimized points chosen the next evaluation point.
We now detail the modified strategy used for MSEI and BMSEI: here, the initial 200d points are selected using the warm-start initialization strategy described in Jiang et al. [24], Appendix D and Astudillo et al. [4], Appendix F. This strategy uses the optimal solution from the previous iteration, targeting the branch that originates from the tree's root and whose fantasy sample most closely matches the actual observed value of the previously suggested candidate on the true function. This modification favors MSEI and BMSEI, slightly disadvantaging PBGI and other baselines.
Acquisition function hyperparameters. For PBGI, we choose the constant hyperparameter to be = 10-4 For PBGI-D, we choose the initial value be λu = 10-1 and the constant decay factor 3 = 2. For both variants, we compute the Gittins indices using 100 iterations of bisection search without any early stopping or other performance and reliability optimizations.
For LogEICC, we follow Lee et al. [27] to use Or B as the cost exponent where B is set to be the cumulative cost cap shown on our plots. For UCB, we follow the schedule of Srinivas et [39] given by Nt- = 2 log(dt" ddt² //))), where d is the dimension. We also adopt the choice of ò = 10-1 and a scale-down factor of 5, as used in that work's experiments. For MSEI and BMSEI, we use lookahead steps, each with batch size of I and single fantasy point.
B-t
Omitted baselines. We omit MSEI from the Bayesian regret plots for d = 16 with k = 10 and for d = 32 with all length scale choices because we were unable to get it to work reliably in these settings: the implementation of Jiang et al. [24] results in frequent crashes due to running out of memory and related issues when used higher-difficuly problems. We also omit KG from = 32, BMSEI from the cost-aware Pest Control and Robot Pushing experiments, and MES from the Bayesian regret experiment with d 32, for the same reasons.
In addition to the baselines mentioned in Section 4, we also implemented the predictive entropy seurch (PES) acquisition function of Hernández-Lobate et al. [23], but could not get its computations to run reliably an automatie-differentittioo based environment without resulting in NaN gradients. Hemández- Lobatto et al. [23] document this behavior, and suggest using fmite-differencing in situa-
26

---

tions where it occurs: however, from initial examination, we found this to decrease performance on nigher-dimensional problems. We therefore opted restrict ourselves to automatically caaaticcllly--fffenntableeee baselines and omit PES, to ensure that performance differences seen can reliably be attributed to the acquisition functions used, and not to gradient computation.
Objective functions: Bayesian regret. For Bayesian regret, this is straightforward: the objective is simply draw from a Fourier feature approximation of the respective Gaussian process prior, drawn in such way that different baselines with the same random number seed share the same objective, but objectives for different seeds are different draws from the same prior. We use a total of 1024 Fourier features.
Objective fuuccioon: synthetic benchmarks. The synthetic benchmark functions we use are as follows. We use variants with dimension d = 4, 8, 16 in our experiments. Ackley: this is
fA(21, .., rd) 20 20 exp
-0.2,
1
Σ i=1
x
exp
1
Σ i=1
cos (2T.3s))
te
(80)
d
with search domain X = []1
Levy: this is ft 100ft where
d-1
(x Id) = 81 + Σ (wy 1)² + 10 sin + 1)²) + (wa - 1) + sin(2 (81)
with = 1+ - and 81 sin(Tw)) )² and search domain X = [-10, 10
Rosenbrock: this is fn 10 fn where
fa
10002111-22)) x2)² (x= 1)2)
(82)
with search domain X = [-5, 10
Cost function. In the cost-aware Bayesian regret and synthetic benchmark experiments, we the cost function
<(x) 20) +
(83)
where S is an affine map used to standardize the input domain: specifically, S(x) = Ax + b where A a diagonal matrix and & is vector, both chosen so that the image of X under is [0, 1jd
Objective functions: empirical.
We now detail the empirical objective functions.
Pest Control (d 25). The pest control problem, as described Oh al. [31] aims minimize the spread of pests as well as the costs of prevention treatment. We adopt the experiment setup from Li al. [28], framing this as a categorical optimization problem with 25 variables. each representing stage of intervention with 5 values reflecting different treatments. The objective function combines the spread of pests and the costs of prevention.
In our cost-aware experiment, we use the cost of prevention as the cost function. This can be computed in an diloomatically-diffeentttt manner, thus this problem is known-cost problem.
Lunar Lander (d = 12). Following the setup in Eriksson et al. [15], we consider reinforcement learning problem optimizing controller for the lunar lander as implemented in OpenAl Gym, which includes continuous input dimensions for engine throttle adjustments. The state space captures the lander's 's position, angle, time derivatives, and leg contact status. The controller's actions allow for directional booster firings or inaction. The objective is to maximize the average final reward over 50 randomly generated environments.
For cost-aware experimentation, we choose the cost to be the average number of simulation time steps, assuming batch processing in groups of 16. This assumption is based on the implementation
27

---

Bayesian Regret
7-10"
Unst. El
Log Regret
Log(Unst. EI)
Exp(LogEI)
LogEl
PBGI
10
S-PBGI
75th quantile
100
200
300
400
Median
25 quantile
Cumulative Cost
Figure 10: Experimental results comparing the impact of log-scaling and numerical stability on the performance of El 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 PBGL. However, Log(Unst. El) improves significantly over EI, and LogEl improves even more.
found in the code associated with Li et al. [28]. Note that this objective involves the number of actual simulation steps used, and is therefore not automatically-diffeenntaab we thus consider this problem to be an unknown-cost problem.
Robot Pushing (d 14). In this work, we adapt one of the three versions of the robot pushing problem designed by Wang and Jegelka [42], where two robots work to push two objects to their specified targets. The problem's s complexity is captured through 14 control parameters, including each robot's initial placement and motion settings. The objective minimizes the sum of the distances from the final position of each object to its respective target.
In our cost-aware experiments, we test both known-cost and unknown-cost variants. The known-cost variant is the maximum of the two robots' operational duration representing the evaluation time, and the unknown-cost variant is the sum of their traversal distances representing the total energy use, similar the cost function used for energy-aware robot pushing benchmark of Astudillo et al. [4], but with one modification: we use the distance traversed by the robot arms instead of the distance the objects are moved. To understand the effect this difference, we include the results for both the unknown-cost and known-cost versions in Appendix D.4.
D Additional experimental results
Here, provide additional experimental results to better understand performance differences and other aspects of policy behavior, including the effect of various problem hyperparameters.
D.1 Impact of log-scaling and numerical stability on El and PBGI
Ament et al. [2] introduce the LogEl variant of Expected Improvement (EI), which is equal to the logarithm of El but incorporates improved numerical properties. Their work demonstrates that LogEl significantly outperforms EI in practice. In this appendíx, we aim to investigate two key questions:
1. What specific properties of LogEl contribute its improved performance over ordinary EI?
2. Can the stable numerical primitives proposed by Ament et al. [2] also benefit PBGI?
The LogEl acquisition function, denoted as a LogEl())) (x)), is defined as the logarithm of the acquisition function, a (x)), ). but is computed using numerical helper function log h designed to provide better numerical stability. This introduces two potential sources of improvement for LogEl over EI: (a) the enhanced numerical stability due to the use of log_h, and (b) the effect of logarithmic scaling, which alters the gradients of the acquisition function and may lead to more effective optimization of a LogFi (x). To disentangle these two factors, we compare not only LogEl and ordinary EI- latter of which we refer to as unstable (Unst. ET) this section for disambiguation--uut also two additional variants: Log(Unst, El), which directly applies logarithmic transformation to unstable El (log(a (I))) without using log_h or other numerical stability tricks, and Exp(LogEF) (exp(a LogEll which applies the numerical helper function from LogEl, but then undoes the
28

---

d = 4
d =
8
16
300
600
1,200
Runtime
200
400
800
100
200
400
0
0
0
10
20
30
40
20
40
60
80
40
80
120
160
Cumulative Cost
75th quantile
LogEl
MSEI
PBGI
KG
Median
25th quantile
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 LogEl and TS, but faster than KG and MSEI.
logarithmic transformation. For Log(Unst. EI), we compute log(a + 10-6) to avoid infinite floating-point evaluations.
To test whether PBGI can benefit from the improved numerical stability, we also test PBGI and the following variant, which we call stable PBGI (S-PBGI), which uses the following gradient formula:
V S-PBCI (x) VoH(x)+ V,o(z) (xx) V,, c(x) log h h²(2) (a)())
(84)
log ((z)
where bog_(22 ) is given by (9) of Ament et al. [2]. We do not consider logarithmic scaling of the PBGI acquisition function value because can be negative.
From Figure 10 we see that the improved performance of LogEl over EI appears to be mostly attributable the log-scaling, though the numerically stable computation provides significant benefit, too. In contrast, there appears to be little-to-no difference between PBGI and S-PBGI.
D.2 Runtime comparison
Here, we provide a runtime comparison between PBGI with 100 bisection iterations and various baselines, including inexpensive baselines such as LogEl and TS, and expensive ones such as MSEI. We do so in the Ackley function setting, using the same hyperparameter settings as the main experiments. We do not perform any explicit caching in computing μ or their gradients, and simply rely on standard BoTorrc routines to obtain these at each iteration. We measure the CPU time (in seconds) to compute and optimize the acquisition function.
Results are in Figure 11. faster than either KG MSEI, though the runtime of the latter decreases substantially as it accumu- lates more data. Overall, we conclude that PBGI's 's runtime is closer to that of classical acquisition functions than sophisticated lookahead-basee variants. If necessary, PBGI's runtime can potentially be reduced further by optimizing the computation of V and Vo, or using fewer bisection iterations.
We see that PBGI is slightly slower than LogEl and TS, but significantly
D.3 Hyperparameter choice for PBGI-D
Next, we examine the behavior different hyperparameter choices for Ào and 3 in PBGI-D. Recall that this variant sets X, 3
A_ at times when the Gittins stopping rule triggers, and X = A at all other times. To understand this, we examine regret curves in the Bayesian regret setting of Section with d 8 under different choices. Results are in Figure 12. We see that behavior of different valuue is qualitatively similar to that of different X-values in PBGI, but with substantially smaller differences between variants, which are detectable primarily due to the relatively-large number of seeds in each experiment, Smaller values of Åo tend to lead to very slightly higher regret on small time scales, but very slightly lower regret on larger time scales. Behavior for / is similar: larger values lead to more gradual decay of X, but with minimal overall impact on performance, especially in
29

---

Log Regret
Log Ay
Xo
8
5-10"
10 1
2
10-2
10
10
10
100
10
10 1
2
100
10-8
10
10
10
100
50
100
150
200
50
100 150
200
75th quantilc
Cumulative Cost
Median
25th quantile
Figure 12: Behavior of PBGI-D under different choices of the initial value Ao. and the coefficient of
decay 3, 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 Àg-values act similarly to the behavior seen in Figure 3 for PBGI, trading off risk-seeking vs. risk-averse behavior, but with substantially smaller gap between the two variants. Larger 3-values lead to more-ate abrrpt decay curves for X, with effect qualitatively similar to λu- In both cases, though our relatively sample size allows us to see small differences between methods, their overall impact performance is cuse-to-nonexiise
the scale of variability.
comparison to between-seed variability. We conclude that, in terms of regret, PBGI-D is less sensitive to hyperparameter choice compared to PBGI, whose behavior was previously shown in Figure
D.4 Effect of unknown costs
The Robot Pushing empirical benchmark involves two cost functions: known-cost variant based on the maximum operational duration, reflecting the evaluation time, and an unknown-cost variant based on the total distance traversed, proxy for energy
similar to the variant considered by Astudillo et al. [4]. One can therefore ask: is the resulting algorithm behavior similar these two settings? Figure 13 shows that the answer is yes: for both the known-cost and the unknown-cost settings, LogEIPC, LogEICC, and PBGI-D outperform MEMES and the non-myopic BMSEI baseline.
D.5 Alternative visualization of experimental results: means and standard errors
Figure 14 gives alternative version of Figures 4 6: instead of showing the median and quartiles, shows the mean and standard error under 95% confidence, without Bonferroni correction. This can be used, for instance, to assess the influence of the number of random seeds used on results.
D.6 Kernel and problem hyperparameters
To check whether our results are sensitive to the kernel used for the Gaussian process model, replicated the Bayesian regret experiments with Matém kernels with smoothness parameters / = 3/2,5/2 as well as the squared exponential kernel, which is the limit of Matérn kernels - [33].
Choice of kernel.
Similar to the original results of Figure 4, we can clearly see from Figure 15 and Figure 16 that behavior splits into three regimes:
1. Easy: d sufficiently-small, most policies achieve similar performance.
2. Medium-hard moderateeto-large both PBGI variants match or outperform baselines.
3. Very hard: sufficiently large, no policy outperforms random search.
We also see that d 32 lands in the very-hard regime for the uniform-cost but not for the cost-aware case: intuitively, this occurs because costs can reduce the effective volume of the search space, since high-cost regions without promising points can be excluded from search.
This behavior is consistent among different kernels, but where the exact threshold which regimes switch differs. In particular, for the squared exponential kernel, the separation between the medium
30

---

Best Observed Value
Known Costs
Unknown Costs
LogEIPC
LogEICC
10.5
BMSEI
-11
MFMES
-1.55
PBGI
-12
PBGI-D
RS
0
150
300
450
600
200
400
600
800
75th quantile
Median
Cumulative Cost
25th quantile
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 performing best in both cases.
and the hard regime appears earlier than for the other variants: all policies there have similar performance to random search when d = 16.
Choice of length scale. To check whether our results are sensitive to the Gaussian process model's length scale, we compare y = 10 with к = 5 10-1 and k = 10". From Figure 17 and Figure 18, which show uniform-cost and cost-aware results, respectively, we can see that PBGI variants' performance tends to improve relative to most baselines as dimension increases in both scenarios. Since к 10 and uniform-cost case under d = 32, these two length scales land into the medium-han regime rather than the very-hard regime.
10-1 result in easier problems than 10-1, in the
Synthetic benchmark dimension. To better understand the effect of problem dimension in settings outside Bayesian regret, we repeat the synthetic benchmark experiments with d 4, and d = 16. Results in Figure 20. Since d = 4 and = 8 are less-difficult, PBGI-D usually performs comparably to baselines, while PBGI either under-performs or over-performs, depending on the objective. This behavior might be explainable by PBGI's sensitivity to hyperparameters in comparison with PBGI-D, whose performance more-uniform.
31

---

d =
d = 16
d = 32
Uniform-oo cost
5-100
7-10"
9-10"
Log Mean Regret
100
10
8-100
50
100
150
200
0
100
200
300
400
0
200
400
600 800
5-10%
7-10"
10
Varying-oo cost
10
2-109
3-100
0
100
200
300
400
0
200
400 600 800
0
200
400
600
800
Cumulative Cost
Ackley
Levy
Rosenbrock
Uniform-cost
10a
100
10
Log Mean Regret
10-1
10
104
10a
40
80
120
160
40
80
120
160
40
80
120
160
4-100
10a
Varying-cov coot
105
100
10
104
3-10-1
100
200
300
400
100
200 300
400
100
200
300
400
Cumulative Cost
Pest Control
Lunar Lander
Robot Pushing
300
-111/4
Uniform-cost
-14
Best Observed Value
-15
200
-111/2
-66
100
-113/4
-17
12
25
50
75
100
50
100
150
200
0
50
100
150
200
Varying-cost
-14
300
101/2
-15
200
11
16
100
111/2
-17
12
200
400 600
800
1600
3200
0
200
400
600 800
Cumulative Cost
LogEI(PC)
(B)MSEI
(MF)MES
TS
UCB
+2-Std. Err.
Mean
KG
LogEICC
PBGI
PBGI-D
R$
Std. Err.
Figure 14: Regret curves for the Bayesian regret and synthetic benchmark experiments, as well as best observed values for the empirical experiments, showing using means (solid lines) and two times standard errors (shaded regions). See Figures 4 to 6 for details.
32

---

Matérn-3/2
Matérn-51
Sq. Exp.
4-10"
109
10
25
50
75
100
50
75
100
20
40
80
5-100
100
06
Log Regret
5-10-1
50
100
150
200
50
100
150
200
0
40
80
120
160
7-100
?
11 =
100
100
200
300
400
100
200
300
400
0
80
160
240
320
10a
28
7-100
0
200
400
600
800
200
400
600
800
160
320
480
640
Cumulative Cost
LogEl
MSEI
PBGI
PBGI-D
75th quantile
Median
MES
TS
UCB
KG
RS
25th quantile
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.
33

---

Matérn-3/2
Matérn-5//
Sq. Exp.
4-10"
10"
]
50
100
150
200
0
50
100
150
200
50
100
150
200
5-100
Log Regret
10"
100
200
300
400
0
100
200
300
400
100
200
300
400
7-100
16
2-10"
200
400
600
800
0
200
400
600
800
200
400
600
800
10a
13
3-100
200
400
600
800
0
200
400
600
800
200
400
600
800
Cumulative Cost
LogEIPC
LogEICC
BMSEI
75th quantile
Median
MFMES
PBGI
PBGI-D
RS
25th quantile
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 x 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.
34

---

== 10-1
== 5-10-1
100
4-10%
10
10
10
10
10-2
10
10
10-3
10
10-4
10
3-10
10
25
50
75
100
0
15
45
60
10
20
30
40
5-10"
10
10
10
10-1
10
10 10-2
Log Regret
109
10
10
3
50
100
150
200
0
30
60
90
120
20
40
60
80
7-10%
7-100
5-100
2
10
96
100
100
2-10-
100
200
300
400
0
60
120
180
240
40
80
120
160
10a
9-10"
8-10"
32
7-10%
10
100
200 400 600 800
0
120 240 360 480
80
160
240 320
Cumulative Cost
LogEl
MSEI
PBG1
PBGI-D
75th quantile
Median
MES
TS
UCB
KG
RS
25th quantile
Figure 17: Comparison of Bayesian regret across different length scales and dimensions, with Matérn-5/2 kernel, in the uniform-cost setting. We see similar overall behavior, but each example switches between the easy, medium-har hard, and very hard regimes different precise thresholds.
35

---

= 10-1
5-10-1
K
100
4-10"
10
100
10
10
10
10-2
100
0
50
100
150
200
40
80
120
160
0
100
5-100
4-109
100
10
Log Regret
100
5-10
10
0
100
200
300
400
80
160
240
320
0
50
100
150
200
7-100
6-100
4-100
2-100
2-100
100
200
400
600
800
160
320
480 640
0
100
200
300
400
10a
9-10%
8-100
23
3-100
3-100
3-100
0 200 400 600 800
200 400 600 800
0 200 400 600 800
Cumulative Cost
LogEIPC MFMES
LogEICC
BMSEI PBGI-D
75th quantile
Median
PBGI
RS
25th quantile
Figure 18: Comparison of Bayesian regret across different length scales and dimensions, with Matérn-5/2 kernel, in the cost-aware setting. We see similar overall behavior, but each example switches between the easy, medium-hard hard, and very hard regimes different precise thresholds.
36

---

d
= 8
16
10
Ackley
10
10
10a
Log Regret
10a
Levy
10
10
105
Rosenbrock
10
103
10
20
30
40
40
60
80
40
80
120
160
Number of Function Evaluations
LogEl MES
MSEI
PBGI
PBGI-D
75th quantile
Median
TS
UCB
KG
RS
25th quantile
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 4, with differences between the most-competitive methods emerging as dimension increases to d = 8 and d = 16.
37

---

d = 4
8
11
4-100
Ackley
10
2-10
10a
Log Regret
Levy
10a
10
:01
Rosenbrock
101
10
25
50
75
100
50
100
150
200
100
200
300
400
Cumulative Cost
LogEIPC
LogEICC
BMSEI
75th quantile
Median 25th quantile
MFMES
PBGI
PBGI-D
RS
Figure 20: Comparison of regret for synthetic benchmark functions under different dimensions, in the cost-aware setting. We that most methods perform similarly for d with differences between the most-competitive methods emerging as dimension increases to and = 16.
38

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: We have reviewed all claims made and checked that they accurately reflect the contributions and scope.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification: We describe explicit limitations throughout the work, and in particular in the experimental section.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
Justification: All claims are precise, and are either refereneed, or proven in the appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose the information needed to reproduce the main experimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes].
Justification: Yes, include experimental appendix documenting this.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes].
Justification: Code is provided supplementary material.
6. Experimental Setting/etails
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparame- ters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes].
Justification: The experiment details are fully described in the appendix.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes].
Justification: Yes, all experiments include quartiles and sample sizes to assess variability.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes].
This paper only studies relatively small-scale problems compared to other machine learning areas, and each individual experiment can ordinary laptop.
Justification:
9. Code Of Ethics
39

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics HTTPS//AAUurSSCCC/....ECCCCCCCCD
Question:
Answer: [Yes].
Justification:
We have checked and believe that we conform to the guidelines.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: This is a theory-add-methoos--ocusss paper with no explicit societal applica- tion impact.
11. Safeguards
Does the paper descrihe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA].
Justification: We do not release a dataset or model.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes].
Justification: We do not use any assets except publicly-vvilabbl Python packages, which are documented as dependencies for our code, and their companion papers are cited.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: We do not introduce any assets.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Question:
Answer: [NA].
Justification: There are no human subjects.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements your country or institution) were obtained?
Answer: [NA].
Justification: There are no human subjects.
40


Reviews:
[{"review_id": "zHozA9PbRe", "reviewer": "Reviewer_ykvm", "summary": "This work tackles cost-aware Bayesian optimization using the Pandora's box Gittins index. In particular, in this paper, the authors focus on expected budget-constrained cost-aware Bayesian optimization and cost-per-sample cost-aware Bayesian optimization. Then, they provide some evidence of the proposed method in order to show the validity of their method. Finally, several experimental results are demonstrated to show the performance of the proposed method.", "questions": "- For \"Thus, EIPC is perhaps best suited to settings where heterogeneity is the main factor at play,\" what is heterogeneity here? I think it is not clear.\n- Line 111, for \"is in widespread use,\" can it be a real reason?\n- For the Pandora's boxes, do you assume that there exist infinite boxes? or, there exist a finite number of boxes?\n- Line 152, a period is missing.\n- How did you optimize Equations (5) and (6) in practice?\n- Figures 2, 3, and 4: which function is used to be optimized for each figure?\n- Figure 3: I don't understand the effect of $\\lambda$. According to Figure 3, it should be as small as possible.\n- For dynamic decay, it is just constant decay, right? $\\beta$ is a constant.\n- Line 248, how did you choose $\\lambda$ and $\\beta$? Is there any guidance for these selections?\n- Line 250: for \"even though per-problem tuning could be advantageous,\" is it guaranteed? Is there any evidence for this?", "limitations": "I don't think that there are any particular societal limitations of this work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Cost-aware Bayesian optimization is an important research topic in Bayesian optimization.\n- The method proposed in this work provides a new perspective on cost-aware Bayesian optimization.", "weaknesses": "- Some parts of this work are not clear.\n- Experimental results seem not promising.\n- Writing can be improved more.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Strengths:\n> [...] important research topic [...]\n> [...] new perspective [...]\n\nThank you for your review! We are delighted the key strengths - (a) **the importance of the topic**, and (b) **novelty, specifically a brand-new technical perspective on Bayesian optimization** - are recognized. We would like to draw your attention to these points: **we think our strengths have significant merit**, and that they may outweigh some weaknesses and points of improvement, particularly given clarifications below. We would like to gently ask you to reconsider your score on this basis.\n\n> Weaknesses:\n> Some parts [...] not clear.\n\nWe would be delighted to hear pointers to specific paragraphs so that we can improve our work.\n\n> Experimental results seem not promising.\n\n**We respectfully disagree.** Bayesian optimization is reasonably mature, along with the algorithmic ideas underlying state-of-the-art baselines. **Introducing a simple new algorithmic idea that on most benchmarks matches or outperforms these baselines - sometimes significantly - is, we believe, promising progress.** For instance, our results show strong performance on cost-aware Bayesian regret (objective functions sampled from the prior) in $d=16$ and $d=32$, where both Gittins variants are **significantly better than every competitor**, including the non-myopic and significantly more elaborate MSEI/BMSEI acquisition function. This performance is repeated on synthetic examples (Ackley and Levy) and empircal ones (Pest Control, Lunar Lander), where Gittins variants come out on top, with a small set of exceptions for which we discuss limitations.\n\nFinally, _note that our plots display quartiles, not standard error_. One can thus expect overlap in the interquartile regions even for large sample sizes, and cases where ranges do not overlap - such as the cost-aware variants mentioned above - are especially significant.\n\n> Writing [...]\n\nWe plan to clarify the answers to your and other reviewers' questions (see below). We'd be delighted to hear other specific suggestions regarding clarity.\n\n> Questions:\n> For \"Thus, EIPC [...] settings where heterogeneity is the main factor [...]\" what is heterogeneity here? [...]\n\n_Heterogeneity_ refers to a non-constant cost function $c(x)$. We have edited this to explicitly state that this refers to heterogeneity of costs.\n\n> Line 111, for \"is in widespread use,\" can it be a real reason?\n\nCould you please clarify this? Here we say EIPC is in widespread use in the cost-aware setting. Given that this acquisition function is default in BoTorch, we believe this correct to our best understanding.\n\n> [...] do you assume that there exist infinite boxes? [...]\n\nIn the Pandora's Box problem, the number of boxes $|X|$ is finite: this is given on line 126.\nIn general cost-aware Bayesian optimization, we allow general compact domains $X$, but no longer refer to it as a \"set of boxes\".\n\n> Line 152 [...]\n\nThank you for pointing out this typo!\n\n> How did you optimize Equations (5) and (6) [...]?\n\nThis is given in the *Computation* paragraph on Line 220-224, which also refers to Appendix A.1. In short: we solve the one-dimensional convex optimization problem via bisection search, then apply an analytic gradient formula that does not require solving any additional optimization problems.\n\n> Figures 2, 3, and 4: which function is used [...]?\n\nThese are in the captions. For Figures 2 and 3, we intentionally defer most details in the appendix as these figures serve primarily as visual illustrations. In Figure 2, the objective and cost are scaled squared exponentials, plus a small constant. For Figures 3 and 4, the objectives are drawn from a Fourier feature approximation of the prior, where Figure 3 is the same as the $d=8$ case of Figure 4.\n\n> Figure 3: I don't understand the effect of $\\lambda$. According to Figure 3, it should be as small as possible.\n\nNot necessarily: from the right-hand-side plot of Figure 3, we see that **large $\\lambda$-values perform better if the time horizon is small**. For instance, $\\lambda = 0.01$ performs best for time horizons less than 50, whereas smaller values perform better on longer horizons. Therefore, we view $\\lambda$ as a parameter which controls risk-seeking vs. risk-averse behavior in the algorithm, with larger $\\lambda$-values being more suitable for smaller budgets and smaller $\\lambda$-values better for larger budgets. This is stated in the caption: \"We see that large $\\lambda$-values decrease regret sooner, but eventually lose out to smaller $\\lambda$-values.\"\n\n> For dynamic decay, it is just constant decay, right? $\\beta$ is a constant.\n\nWhile the _decay multiplier_ is a constant $\\beta$, the _times when the multiplier is applied_ are dynamic. Specifically, the dynamic decay variant update $\\lambda$ to $\\beta \\lambda$ every time the Gittins index stopping rule triggers - that is, when every point's expected improvement is worse than its inspection cost. This is described formally in the list item of Line 202 which introduces it.\n\n> Line 248, how did you choose $\\lambda$ and $\\beta$? [...]\n\nIn contrast with what is done in many other works, we **deliberately chose a non-optimally-tuned value** in order to demonstrate that our algorithm can achieve good performance _even if these parameters are not explicitly tuned, especially on a per-problem basis_. This is important, since some of our baselines such as EIPC contain no hyperparameters. We chose a relatively small $\\lambda$ based on the observation from the right-hand-side plot in Figure 3, where PBGI with large $\\lambda$-values initially decrease regret faster, but eventually lose out to PBGI with smaller $\\lambda$-values.\n\n> Line 250: for \"[...] per-problem tuning could be advantageous,\" [...] evidence for this?\n\nYes, this is shown in the right-hand-side of Figure 3: there, picking $\\lambda$ to match the intended time horizon well is shown to result in stronger performance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "kmElmlxJ2J", "reviewer": "Reviewer_iB7T", "summary": "The paper introduces the Gittins index, a novel perspective from the pandora box problem, to address the cost-aware optimization problem on unknown rewards. It offers a theoretical justification for adapting the Gittins index as an acquisition function and offers empirical results against previous works, demonstrating the effectiveness of the proposed method.", "questions": "1. What are the expectations in (4) with respect to?\n2. Could the author clarify the discussion in line 104 to line 109. I'm not sure if the context assumes constant cost or not.\n3. Could the author clarify the optimality claimed in line 103? I'm not aware that EI bears the tightest BCR or BSR bound.", "limitations": "Discussed above.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. A novel perspective connecting previously independent works on different types of cost-aware optimization problems.\n2. The figures help illustrate the connection between the pandora box problem and cost-aware BO. \n3. The performance seems robust in various tasks. And it makes sense that a myopic cost-aware acquisition behaves well when only aiming at minimizing simple regret.", "weaknesses": "1. The justification for the algorithm poses a major concern. The conversion to BO lacks sufficient discussion, especially when the c(x) surrogate could be constantly updated. One potential problem with the adopted conversion is that the original Gittins index ignores posterior dynamics. When the cost function is unknown, the noisy rewards and noisy costs let the posterior converge to the underlying functions at the picked candidate. Then the PBGI at that location could remain superior when the cost functions posterior converge much faster relatively, meaning the acquisition is trapped locally. I believe more discussion is crucial for the soundness of the proposed method.\n\n2. There are several problems with clarity. Most outstanding is the availability of the cost function. It seems that most of the paper regards the cost function as given, while in the experiment section and some of the appendix, the cost function is unknown and extracted from another Gaussian process in some cases. This could be confusing, especially given that the unknown cost function typically requires corresponding treatment, and it differentiates from the original Pandora's box problem. The discussion should highlight the differences from the beginning. Also, the paper lacks discussion over the connection to previous work, especially on how the proposed acquisition function avoids arbitrary performance deterioration, as shown in Astudillo et al. [3].  Another problem lies in the Bayesian optimality. Is that defined with respect to formula (4)? Then how is that connected to the optimality in cost-aware Bayesian optimization? The optimality in cost-aware Bayesian optimization should be agnostic to the choice of $\\lambda$. \n\n3. There are also known practical concerns (Wu et al. 2020) that different magnitudes of costs could amplify the misspecification in GP, which has not been discussed, at least in the related work section.\n\nReference: \n- Wu, Jian, Saul Toscano-Palmerin, Peter I. Frazier, and Andrew Gordon Wilson. \"Practical multi-fidelity Bayesian optimization for hyperparameter tuning.\" In Uncertainty in Artificial Intelligence, pp. 788-798. PMLR, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Strengths:\n> [...] novel perspective [...]\n> [...] figures [...]\n> [...] performance seems robust [...]\n\nThank you very much for your review! We are delighted that these key strengths - including **novelty, specifically a brand-new technical perspective on Bayesian optimization** - are recognized.\nWe would like to draw your attention to these points: **we think our strengths have significant merit**, and that they may outweigh some of the weaknesses and points of improvement discussed below.\nWe would thus like to gently ask you to reconsider your score.\n\n> 1. The justification for the algorithm poses a major concern. [...] I believe more discussion is crucial for the soundness of the proposed method.\n\nThank you very much for this insightful comment, which has led us to **carefully think about consistency properties and related phenomena in a new way**. In short: the finite-$\\lambda$ version of our algorithm is designed for finite budgets. Asymptotic consistency requires one to think about cases where the budget is infinite. We think PBGI-D may be a better algorithm for this setting, and your comment has led us to make some preliminary theoretical investigations here that we describe in more detail in the **follow-on comment that we will post as soon as this is enabled on OpenReview.**\n\n> 2. [...] availability of the cost function. [...] most of the paper regards the cost function as given, while in experiment section and some of the appendix, the cost function is unknown [...]\n\nThank you for pointing this out! We will clarify that:\n* We consider both known and unknown costs.\n* **The primary focus of our work, and the default assumption throughout, is known costs**.\n* When needed, we model unknown costs as log-normal processes, and show how this integrates into our algorithms.\n* Potential limitations of our strategy for handling unknown costs.\n\nOur motivation for focusing on known deterministic costs is that, given we develop novel techniques, **it makes sense to thoroughly understand the simpler case first**. Thoroughly understanding how to handle unknown costs, as well as theoretical analysis (such as regret bounds), are a promising direction for future work that our work opens the door to.\n\n> [...] previous work [...] avoids arbitrary performance deterioration [...] Astudillo et al. [3].\n\n**The key is in Figure 2**: in this example, there is a high-variance high-cost point, and many low-variance low-cost points. The **correct decision (in terms of simple regret) is to pick the high-variance high-cost point**: PBGI does this, while EIPC does not. We discuss this in the paragraph titled *Qualitative behavior and comparisons* on lines 225-233. We also discuss a similar example regarding EI in Figure 8, and have added discussion on these points to the appendix.\n\n> [...] Bayesian optimality. Is that defined with respect to formula (4)? [...] optimality [...] should be agnostic to the choice of $\\lambda$.\n\nYou're (mostly) correct: Bayesian-optimality in the **cost-per-sample setting, where there is no $\\lambda$**, is defined with respect to (4). Bayesian-optimality in the **expected budget-constrained setting**, which requires a choice of $\\lambda$ given budget $B$, is defined in Section 2 using the same objective as (4) but with two modifications: (i) costs are not part of the objective, and (ii) only policies whose sum of costs does not exceed some budget $B$ *in expectation* are allowed. The relationship between the two settings, particularly the existence of an optimal $\\lambda$, is given by Proposition 2.\nWe have **clarified this relationship in full detail in an updated technical appendix** which has been substantially reworked and expanded in the time since this work's submission. \n\n> 3. [...] practical concerns (Wu et al. 2020) that different magnitudes of costs could amplify the misspecification in GP [...] related work [...]\n\nAs requested, we'll discuss Wu et al. 2020 in the related work. **The concern in that paper (see their Section 2.4) is specific to the multi-fidelity setting with continuously-varying fidelity**, where one can measure fidelities with near-zero value at near-zero cost. This concern does not typically arise in the single-fidelity setting we study.\n\n\n> Questions:\n> What are the expectations in (4) with respect to?\n\nThese are as follows:\n* The random function values $f(1), \\dots, f(N)$ for each of the $N$ points in the discrete domain.\n* Choices made by the algorithm, namely the stopping time $T$ and the inspected points $x_1, \\dots, x_T \\in$ {$1, \\dots, N$}. These choices can depend on function values observed so far, and they may also depend on external randomness (though, by standard MDP theory, external randomness is not necessary to solve the problem optimally). Specifically, after inspecting at time $t$, the algorithm chooses whether to stop and, if not, the next point to inspect $x_{t + 1}$, based on the data $\\mathcal{D}_t = \\{(x_1, f(x_1)), \\dots, (x_t, f(x_t))\\}$.\n\nWe will clarify these details in the next revision.\n\n> [...] clarify the discussion in line 104 to line 109. [...] assumes constant cost or not.\n\nThis discussion assumes constant cost, but an analogous discussion could be made for heterogeneous costs too. In particular, the discussion also applies to ordinary EI, not just EIPC. We will reorganize the discussion so that its scope is clearer, and expand on appropriate details, such as the idea behind the counterexample of Astudillo et al. (2021).\n\n> Could the author clarify the optimality claimed in line 103? [...]\n\nWe mean EI is the one-step-lookahead greedy algorithm.\nThat is, if we consider an arbitrary set of data observed so far $\\mathcal{D} = \\{(x_1, f(x_1)), \\dots, (x_t, f(x_t))\\}$, then EI chooses the point $x_{t+1}$ maximizing $\\mathbb{E}(\\max(f(x_1), \\dots, f(x_t), f(x_{t + 1})) \\mid \\mathcal{D})$. \nOne can thus view EI as optimal for a one-step-truncation of the original problem. \nWe will clarify this in the next revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "2zdUbxLBGn", "reviewer": "Reviewer_7Tfe", "summary": "This paper draws connections between cost-aware Bayesian Optimization (BO) and a problem from the economics literature, called the Pandora's Box problem. Based on these connections, the paper proposes a new cost-aware acquisition function, called Pandora's Box Gittins Index (PBGI). Numerical experiments show that PBGI achieves competitive performance against usual acquisition functions.", "questions": "Here are some questions to spark the discussion with the authors. My reservations are mainly about the experimental part of the paper, I will be happy to increase my score if these are addressed during the discussion period.\n\n(1) Why not use MLE to find the appropriate lengthscale for each experiment?\n\n(2) Have you studied the relation between $\\kappa$ and the dimensionality of the function domain $d$ w.r.t. PBGI performance?\n\n(3) Do you have any insights on how to calibrate $\\lambda$ and $\\beta$?\n\n(4) Do you consider noise in your experiments? If not, do you have any insights on the behavior of PBGI in a noisy setting?", "limitations": "Yes they did, and I believe the discussion period will shed even more light on the limitations of PBGI.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Viewing cost-aware BO under the lens of the Pandora's box problem is interesting. This work suggests that promising solutions might lie at the intersection between economics and black-box optimization.\n\nThe paper is also well-written.", "weaknesses": "**Impact of the lengthscale $\\kappa$ (1)**. In the experiments, the hyperparameter $\\kappa$ is fixed arbitrarily. Although an ablation study about $\\kappa$ is given in Appendix C, it seems unlikely that a GP with an arbitrary lengthscale will properly fit to the observed data. Because it is difficult to compare the performance of optimization algorithms when they use models that are unfit to the observed data, I think this weakens the experimental part of the paper.\n\n**Impact of the lengthscale $\\kappa$ (2)**. Furthermore, as far as I understand the paper, the performance of PBGI seems to heavily rely on a trade-off between the magnitude of $\\kappa$ and the dimensionality of the function domain. Roughly speaking, PBGI should also have good performance on low-dimensional spaces if $\\kappa$ is low enough. Conversely, it should perform poorly on high-dimensional spaces if $\\kappa$ is large enough. Studying the relation between $\\kappa$ and $d$ would strengthen the contribution.\n\n**Calibration of $\\lambda$ and $\\beta$**. In the numerical experiments, $\\lambda$ and $\\beta$ are also set arbitrarily. I understand that calibrating them is less obvious than calibrating $\\kappa$, but it is nevertheless a crucial part of the PBGI. As far as I know, the paper does not provide a principled way to calibrate these parameters. I believe providing one would strengthen the contribution.\n\n**Noisy setting**. The experiments seem to have been conducted in a noiseless setting. However, in zeroth-order optimization tasks, objective black-boxes often cannot be observed without an observational noise. Therefore, it would have been interesting to evaluate PBGI's performance within a noisy setting. The results, including the ranking of the acquisition functions, may differ.\n\n**Notation**. The notation for the posterior distribution $f | y_1, \\cdots, y_t$ is incorrect and should be replaced by $f | \\mathcal{D}$, with $\\mathcal{D} = \\\\{(x_1, y_1), \\cdots, (x_t, y_t)\\\\}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Strengths:\n> [...] interesting. [...]\n> [...] well-written.\n\nThank you very much for your review! We are delighted that key strengths - specifically, **novelty, via a brand-new technical perspective on Bayesian optimization** - are recognized. We would like to draw your attention to these points: **we think our strengths have significant merit**, and that they may outweigh some of the weaknesses and points of improvement discussed below. In light of a certain unfortunate typo, we also believe that our manuscript already addresses at least some of your concerns about the length scale mismatch (see below), though we will make additional effort to make this clearer in the next draft. On these bases, we would like to gently ask you to reconsider your score.\n\n> Weaknesses:\n> Impact of the lengthscale $\\kappa$ (1). In the experiments, the hyperparameter $\\kappa$ is fixed arbitrarily. Although an ablation study about $\\kappa$ is given in Appendix C, it seems unlikely that a GP with an arbitrary lengthscale will properly fit to the observed data. [...]\n\nThere was a typo in the paper on Line 245: please let us apologize and clarify how our experiments treate length scales:\n* In the Bayesian regret experiments (Sec. 4.1), **the objective function is drawn from the prior, which has a fixed length scale,** and all of the algorithms use a kernel with this same lengthscale.\n* In other experiments, all kernel hyperparameters - including length scales - are **learned using max marginal likelihood**.\n\nWe believe that this concern is primarily a result of this typo. In both types of experiments, each algorithm's GP either **has the correct lengthscale from the beginning or learns the correct lengthscale from data**.\n\n\n> Impact of the lengthscale $\\kappa$ (2). [...] relation between $\\kappa$ and $d$ [...]\n\nThis is a good point: what seems to matter is the \"number of effective boxes\" induced by $\\kappa$, $d$, and the volume of $X$. We include results on this in the appendix. We suspect the best way to get a more precise picture would be to prove a suitable regret bound. While we are **extremely interested in studying this question**, doing so is likely to **involve enough new theoretical machinery for a whole separate paper**, so we prefer to defer it to a follow-up work. \n\n> Calibration of $\\lambda$ and $\\beta$. [...]\n\nWe agree: studying how to set these parameters automatically is a great research question! In principle, proving a regret bound and setting these parameters to minimize the bound could provide for an avenue by which to do so. For the same reasons as in the prior answer, we believe this would make for **a great follow-up to our work**.\n\n\n> Noisy setting. [...]\n\nThe primary reason we don't study this is that **in the presence of noise, the analog of the Pandora's Box model and Gittins index machinery is significantly more complicated**. One needs to create a \"noisy Pandora's box\" model, but this requires one to potentially inspect a noisy Pandora's box multiple times to better estimate its value. There is Gittins index machinery that can handle this type of multi-step inspection in principle, but computation becomes significantly harder because one will not obtain an analytic, expected-improvement-like optimization objective. One must also consider how to translate to the Bayesian optimization setting, for instance by inspecting many nearby points instead of reinspecting the same point many times. We believe this is one of several interesting potential extensions that our work opens the door to.\n\n> Notation. [...]\n\nThank you for drawing our attention to this point. While it is reasonably-standard in the Gaussian process literature to omit dependence on $x$-values (for example, the paper *Efficiently Sampling Functions from Gaussian Process Posteriors*, Wilson et al., ICML 2020, also does this), in retrospect we agree that it could be made clearer and will examine this in the next manuscript draft.\n\n> Questions:\n> [...]\n> (1) Why not use MLE to find the appropriate lengthscale [...]\n\n**We do this:** our synthetic and empirical experiments include length scale optimization. We apologize again for the typo which incorrectly stated this was absent.\n\n> (2) [...] relation between $\\kappa$ and the dimensionality $d$ [...] w.r.t. PBGI performance?\n\n**In short: yes, our Apdx. C5 and C6** study this, but developing a more principled evaluation would make for a well-motivated follow-up paper. Please see the preceding answers on length scales.\n\n> (3) [...] how to calibrate $\\lambda$ and $\\beta$?\n\n**We deliberately did not tune these parameters for each problem in order to make our claims stronger: we get good performance even if they are not set optimally**. Theorem 2 and the right-hand-side plot in Figure 3 tell us that $\\lambda$ should be tuned to match the expected budget: a natural way to do so is to (a) run the algorithm, (b) look at whether the regret first quickly goes down, then levels-off too soon, and if so, (c) make $\\lambda$ smaller. Our PBGI-D variant is a first attempt at doing this automatically, though it introduces the problem of calibrating $\\beta$). We believe there is more to explore regarding calibrating the parameters, e.g. through a theoretical regret analysis, but doing so is beyond the scope of this work.\n\n> (4) Do you consider noise [...]\n\nNo, our experiments are all noise-free. As we discussed in a previous answer, we have ideas about how one could create a Pandora's box model and Gittins index that handles noise, but it would require enough novel technical development that it could well be a follow-up paper in its own right.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "tJcXRLKwVA", "reviewer": "Reviewer_q648", "summary": "The paper proposes the Pandora's Box Gittens Index, a cost-aware acquisition function. Moreover, it questions the behavior of previous cost-aware acquisition functions, and motivates the behavior of PBGI, through connections to the Pandora's Box problem and the behavior under different, uniform costs. Theoretical results are presented to support the claims that are made. Results under both uniform and cost-varying setups display strong performance.", "questions": "__Details on cost__: For unknown costs, the cost is modeled as a GP. Is the mean cost used for acquisition computation, and why do the authors consider the log cost? While I am aware that $\\log c$ is convention, I would have thought that the authors' framework did not need transformations of the metrics to work well. Why is log cost the right metric to consider?\n\n__Lack of normalization__: The examples that are considered in the plots do not normalize the input space. Is this meaningful for the behavior of the algorithm?", "limitations": "Limitations have been properly addressed.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "Firstly, I am generally positive towards the paper. However, I believe the presentation is in part a substantial strength of the paper, but also its biggest drawback (see \"Why does it work well?\" and \"Constant Cost Experiments\"). I will provide the specifics under each section.\n\n__Presentation__: The connection to the Pandora's Box problem is handled very nicely. As someone unfamiliar to the problem, the introduction to it, the connection to BO, and the resulting algorithms were clear, pedagogical and had the right level of detail. I appreciate the effort on the authors' end to do this, specifically in 3.1 and 3.2.\n\n__Relevant Problem(s)__: Both cost-aware and budgeted BO are highly relevant and practical problems, that are commonly treated as distinct. An acquisition function which accounts for both is enticing. Moreover, the obvious flaws in existing methods enhances the relevance further.\n\n__Thorough Experimental Evaluation__: Experimental results are provided on a wide range of tasks, from highly controlled to real-world. The benchmarked algorithms appear to be the relevant ones. Some experiments would do well with additional replications to reduce the error bar widths, but this is a _very_ minor remark.\n\n__Theoretical Results__: Meaningful theoretical results on the behavior of the algorithm are presented.\n\n__Visuals__: The plots are mostly very well made.", "weaknesses": "__Why does the algorithm work well?__ This is mostly related to 3.3, and the results section. After reading up until 3.3, I believe I have understand what I need to know up until that point. However, I am still left wondering how the algorithm will behave, and why this is beneficial (specifically for fixed-cost). PBGI appears to be a more exploratory variant of EI (which I believe is desperately needed, but only from anecdotal evidence). It should be visualized more precisely what PBGI will do compared to EI for a simple, either 1 or 2D example to see the differences - ideally under different costs or budgets.\n\n__Constant Cost Experiments__: If we are effectively tuning the exploratory behavior of EI or UCB (the latter is perfectly tunable as-is) by making up a constant cost objective on Ackley or Levy, what is there to learn? Are we saying that EI should intrinsically be more exploratory? Can we equally well find costs that are highly detrimental to PBGI? Should we only local search if costs are consistently high? Do we get drastically different behavior if we  multiply all Ackley output by 100, and if so, why is this sensible? \n\n__Acquisition Computation Details__: The acquisition computation requires a solve for $\\alpha^*$ involving the cost and EI. This seems like a rather tedious excercise, so is it computationally expensive? 3.3 provides explanation, but it would be nice to see empirical evaluation on this, too. Moreover, can gradients still be computed through autodiff? How does this affect acquisition optimization? Since there is no longer a simple forward pass, this should be expanded on.\n\n__Normalization of cost__: How are costs and objective value normalized in PBGI? Ackley ranges from 0 to 24 (if in the -32 to 32 range) whereas Rosenbrock ranges from 0 to $10^6$, roughly. Does that mean that PBGI is vastly more exploratory for Rosenbrock, since the cost would be way lower relative to the objective? Since I found this to (unfortunately) be rather important and not clear, I am putting it as a weakness.\n\nWith that said, I believe these weaknesses are what separates a currently good paper from a very good one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Strengths:\n> [...]\n> Presentation: [...]\n> Relevant Problem(s): [...]\n> Thorough Experimental Evaluation: [...]\n> Theoretical Results: [...]\n> Visuals: [...]\n\nThank you for the kind feedback - we're glad you appreciated the paper!\n\n> Weaknesses:\n> Why does the algorithm work well?  [...] wondering how the algorithm will behave, and why this is beneficial [...] It should be visualized more precisely what PBGI will do [...]\n\nThis is a great idea! **Please see Figure A of the PDF attached to the main response, which includes an additional visual** that we will add to the appendix in the next draft.\n\n> Constant Cost Experiments: [...] what is there to learn? [...] EI should intrinsically be more exploratory? Can we [...] find costs [...] detrimental to PBGI? [...] Should we only local search [...]? [...] behavior if we multiply all Ackley output by 100 [...]?\n\nWe largely agree, but the devil is in the details. In our view, a good way to think about this is via a \"needles-in-haystacks\" metaphor: some haystacks might have better needles than others, but **exploring a large haystack is only worth it if one expects to actually find the needle in it before running out of budget**. In the discrete expected-budget-constrained problem, Proposition 2 tells us that tuning a risk-seeking-vs.-risk-averse parameter is necessary to handle this tradeoff optimally for each budget, and EI includes no such parameter. In the correlated case, we expect such tradeoffs to loosely map to local-vs.-global tradeoffs, but we believe mainly that **it is the \"haystack-size\" that matters, not locality** in the sense of whether that haystack comes from a nearby or far-away location.\n\nWe have **not yet been able to find costs that are detrimental to PBGI**, though some objective functions - such as the unimodel Rosenbrock objective - can be detrimental. We think because other acquisition functions' behavior - which otherwise serve as a weakness - in this specific case counterbalance model mismatch. \n\nSince **multiplying outputs is equivalent to scaling costs and normalizing**, and our examples do use normalization (see below), we expect this behavior to be **comparable to that shown in Figure 3** which studies the effect of varying $\\lambda$: we expect large-$\\lambda$ values to reach better objective values faster at first, but eventually lose-out to small-$\\lambda$ values which start off slow but eventually find a better location.\n\n> Acquisition Computation Details: [...] is it computationally expensive? [...] can gradients still be computed through autodiff? [...] Since there is no longer a simple forward pass, this should be expanded on.\n\nThis involves solving a one-dimensional convex optimization problem: we do so very efficiently using bisection search. Moreover, Appendix A2 shows that **no additional optimization is needed to compute gradients using autodiff - one forward pass is enough**, in contrast with other situations. Finally, **Figure 9 in Appendix C provides a runtime comparison** which shows that the solution is a little bit more expensive than EI, but significantly less expensive than non-myopic and other more-computationally-expensive baselines.\n\n> Normalization of cost: [...]\n\nThis is an extremely important question: we accidentally omitted certain details regarding normalization from our appendix, which we have now added. In short, **we normalize our inputs and outputs using standard practices** in all cases where this makes sense. Specifically:\n* We **always normalize input values to be in $[0,1]^d$**, except for the illustration of the EIPC counterexample in Figure 2, where this is omitted in order to present easier-to-visualize numbers. There, normalization is equivalent to changing the length scale, so this change does not affect algorithmic behavior.\n* We **normalize output values** in all cases except where the objective functions are sampled from the prior (Bayesian regret), for exactly the reasons you mentioned. For synthetic benchmark functions specifically, we scale the Ackley, Levy, and Rosenbrock functions by constants given in the script `synthetic.py`. This results in **objective values roughly in $[0,10]$** which matches the prior's scale in most regions of space, except a small volume of outlier-regions the algorithms learn to avoid.\n* For Bayesian regret, we omit normalization because **this particular setting by definition has no normalization-mismatch**, as the prior and objective come from the same distribution, with the same kernel, amplitude and length scale parameters.\n* To empirically test the effect of scaling on Rosenbrock, where our scaling constant was perhaps not ideally chosen, we **include an additional plot in Figure B attached to the PDF of our main referee response**. These show slight improvement for PBGI and PBGI-D, with the latter now competitive with the best baselines.\n* Very regrettably, we accidentally forgot to document normalization details in the submission manuscript draft, though it can be seen in our code. We have **added the normalization information in full detail in an updated appendix** in the current manuscript draft.\n\n> Questions:\n> Details on cost: [...] why do the authors consider the log cost? [...]\n\nWe consider log-costs because **this ensures that costs are positive**. If negative costs are allowed, they can create undesired behavior where the algorithm repeatedly evaluates a location with negative costs over and over again, because the costs are effectively interpreted as a deterministic reward.\n\n> Lack of normalization: [...] plots do not normalize the input space. [...]\n\nThis is a critically important question: we **do normalize the input space to be $[0,1]^d$** in all cases where it makes sense, which can be seen in the code in but was accidentally omitted from the manuscript draft's appendix. This has been explained in detail in the current version. Please see the preceding answer with bullet-points for more details on normalization.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
# Summary

We thank all reviewers and the area chair for their time and thoughtful feedback and evaluating this work!
We are delighted that **all four reviewers recognized the work's key strengths**, including: 
* **Importance of the topic (Reviewer ykvm)**.
* **Novelty in the form of a brand-new technical perspective on Bayesian optimization (all reviewers)**.
* **Clarify of presentation (Reviewer 7Tfe)**, with some exceptions that we have identified and fixed thanks to the feedback.
* **Thorough experimental evaluation (Reviewer q648)**.

We believe these strengths rank favorably relative to the standard for accepted papers at NeurIPS. 

We'd also like to draw all readers to the text content of the reviews, which were quite positive - based on the text alone, we would have predicted scores of weak accept. Many of the reviewer concerns focus on small suggestions for improving clarity. Other questions about the technical aspects of our paper and its significance were smaller in scope and we believe are largely addressed by our detailed response. 

We look forward to engaging with the reviewers in discussion. Once the reviewers have a chance to review our response and discuss any remaining concerns they might have, we hope that scores can be changed to be consistent with the text of the reviews. 

## Key Reviewer Concerns

*Reviewer ykvm*:
* Reviewer ykvm states that our empirical results seem "not promising" but does not offer further explanation or detail. We point out that our empirical results show us **matching or outperforming a comprehensive set of baselines**, including a pair of state-of-the-art non-myopic acquisition functions (MSEI, BMSEI), on problems of large-enough dimension. Given the importance of Bayesian optimization and the maturity of its literature, we believe introducing a new algorithm with such results is a significant contribution. Also, Reviewers iB7T and q648 listed our algorithm's performance as a strength.

*Reviewer iB7T*:
* Reviewer iB7T notes aspects of our presentation that could be made clearer, particularly on whether the cost function is known or unknown. We appreciate the feedback, and will clarify this in revision. 
* Reviewer iB7T also asks technical questions about our algorithm's behavior, involving posterior dynamics and consistency properties, especially in the unknown-cost setting. **Our primary focus is the known-cost setting, and the fact that the Pandora's Box Gittins index performs well here is our main empirical finding.** Still, we found that thinking about the aforementioned unknown-cost setting and consistency properties significantly helped us better understand our algorithm's behavior, potential limitations, and avenues for improvement. We have therefore included an **extended discussion on these points in an OpenReview comment** - which we will post once review comments are enabled - and view theoretical analysis thereof as a **promising direction for follow-up work prompted by our results and Reviewer iB7T's comment.**

*Reviewer 7Tfe*:
* Reviewer 7Tfe is worried that our results might be influenced by situations where the prior's length scale does not match well with the objective. This discrepancy is primarily caused by a certain unfortunate typo: *in the Bayesian regret experiments, the objective function is sampled from the prior with the same length scale*, ensuring perfect match between length scales in that setting. In contrast, our *synthetic benchmark and empirical experiments address the setting of learned length scales*. Taken together, our results demonstrate **good performance with both perfectly-matched and learned length scales**.
* In addition, Reviewer 7Tfe raises a number of interesting technical questions one could study in follow-up, such as calibrating our algorithms' parameters and accounting for noisy observations. Since we deliberately avoid using carefully-tuned hyperparameters for our method, **our results show performance improvement even if these parameters are not perfectly calibrated**. Handling noisy observations properly is an interesting question, but involves handling non-trivial technical details on the side of Gittins index theory: we discuss this in our response. For noise observations, therefore, we see the **opportunity to study interesting but non-obvious follow-up questions as strength rather than weaknesses**, since the creation of well-motivated technical questions is itself a significant source of research impact.

*Reviewer q648*:
* Reviewer q648, who rated our work the highest, asks about normalization and says this is the major reason preventing an even higher score. In short: we **already normalize the way Reviewer q648 wants us to** in all settings where this makes technical sense - namely, all except Bayesian regret. However, our submission **forgot to precisely document this in the appendix**, which we regret and have now fixed.
* Two figures requested by Reviewer q648 is available as PDF attached to this post.

## Additional contribution: Theorem 2

Our submission did not claim Proposition 2 - now called Theorem 2 - which relates the expected budget-constrained and cost-per-sample problems, as a contribution. We discovered Theorem 2 independently, then during literature review discovered the work of Aminian et al. (2024), which appeared before we were able to submit our work. This work contains a related result that we thought at time of submission might imply our Theorem 2. Since submission, we have determined that our paper's Theorem 2 is not implied by Theorem 1 of Aminian et al. (2024) due to differences in assumptions. We therefore now believe that **Theorem 2 with non-discrete-support reward distributions (for instance, Gaussian rewards) is an original contribution of our work**. Our updated manuscript now has a complete proof, which we will reproduce here if requested. We are also happy to comment on detailed technical differences with Aminian et al. (2024) on request.

Meta-review: This manuscript takes a new approach to cost-aware Bayesian optimization by drawing a connection to the so-called Pandora's box problem from economics, a connection the authors exploit to derive a new acquisition function for this setting.

The reviewers were somewhat split in their assessment of this work during their initial reviews, although the rebuttal and author-reviewer discussion periods helped address some of the issues identified. There was a vigorous discussion regarding the work during the ensuing discussion period, where a champion emerged to support the paper in favor of acceptance on the strength of its theoretical and practical contributions. 

Some reviewers continued to push for the authors to continue to clarify some issues in the manuscript brought up during the review process. The authors appear willing to address these issues, and I strongly encourage them to do so.
Decision: Accept (poster)