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_cc_2024_Conference
Published: 2024-05-14 22:59:16

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.

Main paper: 
 introduction: 
 Bayesian optimization is a framework for optimizing functions whose evaluation is time-consuming or expensive. It is widely used for hyperparameter tuning of machine learning algorithms [33] , robot control [27] , material design [42] , and other areas. Bayesian optimization works by forming a probabilistic model for the objective function, and then chooses where to sample via an acquisition function that balances the explore-exploit 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-principled cost-aware approaches [41, 23, 25, 3, 6] rely on multi-step lookahead computations that are computationally expensive and can be numerically brittle, limiting their applicability. Other approaches lack a 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 [33] , has recently been theoretically shown by Astudillo et al. [3] to perform arbitrarily-worse than the optimal policy. Thus, in the cost-aware setting, there is a need for theoretically-principled and computationally-straightforward acquisition functions with good empirical performance.In this work, we develop such an approach. To do so, we introduce a novel link between cost-aware Bayesian optimization and a discrete-space decision problem from economics called the Pandora's Box problem [39, 12, 32] . The Pandora's Box problem admits an explicit Bayesian-optimal solution. We show how this solution can be used to develop a novel acquisition function class for two costaware Bayesian optimization settings: (i) expected budget-constrained 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 sufficientlyeasy low-dimensional problems and too-difficult high-dimensional ones, performance is comparable to baselines. On most medium-hard problems of moderate dimension, however, the proposed acquisition function generally outperforms baselines, in the worst case approximately matching their performance. 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 [19] , a general framework for deriving optimal policies for a variety of bandit-like decision problems [38, 13, 21] which is widelyused in queueing theory and related areas [20, 1, 31] . 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 a variant of cost-aware Bayesian optimization over a discrete search space. Using this connection, we (ii) explore the use of Gittins indices, which are Bayesian-optimal 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 a variety of problems of moderate-to-high dimension, including the varying-cost problems it was designed for, as well as classical cost-unaware problems. 
cost-aware bayesian optimization: 
 In black-box optimization, we are interested in finding the global optimum of an unknown (potentially stochastic) function f : X → R defined on some compact domain, using pointwise function evaluations of f at locations x 1 , .., x T ∈ X that we select sequentially. We are interested in policies that achieve low simple regret-see Garnett [17] , Sec. 10.1-namelyEQUATIONwhere the expectation is taken over all sources of randomness in the function f and the policy, including the stopping time T and sequential selections x 1 , .., x T . In our setup, obtaining a new function evaluation at a point x carries a non-zero cost c(x) ∈ R + , assumed automatically-differentiable unless discussed otherwise. We consider settings that integrate costs into the problem in different ways:(a) In the expected budget-constrained setting, there is a budget B ∈ R + , and the algorithm is not allowed to exceed this budget in expectation.(b) In the cost-per-sample setting, at each time the algorithm must choose whether to pay a cost and obtain a new function evaluation, or to stop and return some previously-observed point. In this setting, we add the total sum of costs at termination time to the regret.Note that the cost function c : X → R + can be constant, which we term uniform costs. In this case, (a) reduces to standard black-box optimization with a 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 budget-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-sample setting as a conceptual framework with which to study budget-constrained settings.Bayesian optimization algorithms for solving various black-box optimization problems work by (i) building a probabilistic model of f -that is, a probability distribution which quantifies what is known about f given the data points (x t , y t ) T t=1 seen so far-where y t = f (x t ) are previous function evaluations-then (ii) using the model and its uncertainty to decide where to evaluate the unknown function next. For an introduction, see Frazier [15] and Garnett [17] . Following standard practice, we work with Gaussian process models [30] . Let f | x 1:t , y 1:t be the respective posterior distribution.To decide where to evaluate f next, one uses the model to define a (potentially random) acquisition function α t : X → R, which quantifies how promising a particular location is given what is known so far. We then evaluate f atEQUATIONobtaining an additional data point that is used to reduce uncertainty and further improve the model.The most popular cost-aware acquisition function is expected improvement per unit cost (EIPC) [33] , defined viaEQUATIONwhere we have written α EIPC t (•) in terms of the general expected improvement function EI ψ , defined with respect to some random function ψ : X → R, and a 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 so far as the comparator, to the cost.In the uniform-cost case, where the costs c(x) = C ∈ R + are constant for all x, this acquisition function reduces to the classical expected improvement (EI) acquisition function α EI t (x) = EI f |x1:t,y1:t (x; max 1≤τ ≤t y τ ). 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 expected improvement is the optimal strategy in this one-step-lookahead scenario.Since EIPC reduces to EI in the uniform-cost case where c(x) = 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 be 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 [10] . However, even with heterogeneous costs, Astudillo et al. [3] show there exist reasonable problems where EIPC performs arbitrarily worse than the optimal policy in an approximation-ratio sense, due to over-sampling low-value low-cost points. Analogous behavior can occur in multi-fidelity settings, which Wu et al. [40] argue can be especially undesirable in the presence of model-misspecification.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 [4] . We therefore ask: can one develop a technically-principled and computationally-straightforward alternative with at-least-comparable empirical performance? 
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 to yield analytic insights. An analogous strategy is used classically to derive expected improvement, by exactly solving a 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 The Pandora's Box problem [39, 19] is a sequential decision-making problem. It begins with a finite set of boxes, which we collect into a set and label X = {1, .., N }. Each box has a hidden reward, denoted by f (x), and an inspection cost, denoted by c(x). The rewards are given by mutually independent random variables whose distributions are known and vary between different boxes.The decision-making process starts with a set of closed boxes, and proceeds in discrete time steps. At time t, one can choose to do one of two things:1. Open a box x t ∈ X. This incurs cost c(x t ), but reveals the exact value f (x t ) 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 decisionmaking process, and yields a terminal reward equal to the maximum value among the boxes opened so far, with the convention that at least one box must be opened.The policy'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 writtenEQUATIONwhere T is a random variable that denotes the number of opened boxes, indicating that the policy terminates at time T + 1.If we subtract the objective (4) from E sup x∈X f (x), which is constant with respect to the policy, we obtain the sum of the simple regret objective (1) defined in Section 2 and expected total costs. The Pandora's Box problem is therefore equivalent to a special case of cost-aware black-box optimization, specifically the cost-per-sample variant of Section 2, where (a) the domain X is a finite set, and (b) the objective function f is random, with independent f (x) and f (x ′ ) for x ̸ = x ′ . We will return to this point in the sequel, but first study the Pandora's Box problem in more detail.The Pandora's Box problem gives rise to an 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 a Markov decision process (MDP). By general MDP theory, there exists an optimal policy describing which box, if any, one should open for a given configuration-we call such a policy Bayesian-optimal.This MDP can be solved explicitly, with a remarkably simple solution, first derived in an economics setting by Weitzman [39] . We start by associating with each box x ∈ X a number α ⋆ (x) known as the Gittins index [19] . DefineEQUATIONwhere EI f (x; y), previously defined in (3) of Section 2, is the expected improvement of x relative to y-the same expression which appeared in the expected improvement acquisition function variants α EI t and α EIPC t . Note that, unlike in those cases, α ⋆ is not time-dependent due to the lack of correlations or conditioning. Since EI f (x; g) is strictly decreasing in g, the root-finding problem (5) admits a unique solution for every value of c(x).To understand what α ⋆ (x) represents, consider a single closed box x, and suppose there is a second, open box with reward f * . Is opening box x better than taking the reward f * from the open box? This amounts to 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 EI f (x; f * ) > c(x). The value α ⋆ (x) tells us how large does the alternative reward f * need to be, for stopping and taking it to be at least as good as opening box x-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, we obtain the Gittins index policy, which proceeds as follows. At each time t, let f * t = max 1≤τ ≤t f (x τ ) be the maximum reward among all open boxes, and let x * t be the box of maximum Gittins index value α ⋆ (x) 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 f * t < α ⋆ (x * t ), the policy opens box x * . • If f * t ≥ α ⋆ (x * t ), the policy stops and receives terminal reward f * t . 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 is outright Bayesian-optimal. We state this formally as follows.Theorem 1 (Weitzman [39] ). Let X be a finite set, let f : X → R be a finite-mean random function for which f (x) is independent of f (x ′ ) for x ̸ = x ′ , and let c : X → R + , without loss of generality, be deterministic. Then, for the cost-per-sample problem, the policy defined by maximizing the Gittins index acquisition function α ⋆ with its associated stopping rule is Bayesian-optimal.In the language of Bayesian optimization, this means that not only is there an explicit Bayesianoptimal policy for the Pandora'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. [24] , Theorem 1. Using Lagrangian relaxation, we show that the obtained solution carries over to the expected budget-constrained setting.Theorem 2. Consider the expected budget-constrained problem, with the assumptions of Theorem 1. Assume the problem is feasible and the constraint is active, namely min x∈X c(x) < B < x∈X c(x). Then there exists a λ > 0 and a tie-breaking rule such that the policy defined by maximizing the Gittins index acquisition function α ⋆ (•), defined using costs λc(x), is Bayesian-optimal.A proof is given in Appendix B. This result extends a special case of Aminian et al. [2] , Theorem 1. Compared to that work, we consider only Pandora's Box, but allow general reward distributionsincluding those with infinite support, such as Gaussian rewards. The optimal λ depends on the budget constraint B implicitly via a convex optimization problem given in Appendix B. In budget-constrained problems, we therefore view λ as a hyperparameter, which controls the degree to which the algorithm is risk-averse vs. risk-seeking-precisely what we argued was missing from EIPC in Section 2.One can intuitively understand λ using a needle-in-haystack metaphor. Suppose one 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 c, and best value f * t seen so far, and is encoded by λ in Theorem 2. Larger λ-values correspond to smaller budgets B, incentivizing one to search less of the haystack. Crucially, the optimal acquisition function α ⋆ behaves differently for different λ-values, and therefore for different budgets: roughly, smaller budgets cause α * to explore less. We will return to this in Section 3.3.3 and Figure 3 .To adapt α ⋆ 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 1 ostensibly requires f (x) to be independent of f (x ′ ) for all x ̸ = x ′ , the key question is how to incorporate data and spatial correlations into α ⋆ . We propose to do so in the simplest and most obvious way: namely, at each time t, we plug the posterior distribution f | x 1:t , y 1:t in place of f . This yields three variants, depending on the precise cost-aware setting one is interested in: and λ is a hyperparameter that should be tuned to match the evaluation budget B. 2. Cost-per-sample: we can directly apply α PBGI t 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. 3. Adaptive decay: here, we do not have a pre-defined budget or cost-based stopping rule. Define the Pandora's Box Gittins index with adaptive decay (PBGI-D) acquisition function α PBGI-D (x) analogously to α PBGI (x), but with a time-dependent λ t schedule, set according to the Pandora's Box stopping rule. Specifically, λ 0 is initialized to a given value, then setEQUATIONwhere β > 1 is a decay factor that is used to decrease λ τ 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: we discuss this further in Appendix D.2.To understand this acquisition function class, one 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 to obtain the posterior, but then (b) pick new samples according to the rule that would have been Bayesian-optimal if the posterior had no correlations. Said differently, α PBGI arises from exactly solving a simplified dynamic program, where the simplification is of a 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, one can expect α PBGI to be approximately-optimal in settings where the key decisions involve choosing between different far-away data points. One can intuitively expect this to occur 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.To compute α PBGI efficiently, note that y → EI ψ (x; y) is monotone. As a result, the value g in ( 6) can be computed efficiently via a bisection search. In Appendix B.2, we show that (i) its gradient can be computed straightforwardly via an explicit analytical expression without any additional optimization, and (ii) the resulting computational costs are much closer to those of expected improvement than those of expensive multi-step-lookahead-based approaches. Theorem 1 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(x) affects performance, but does not change the optimal strategy. Building on these observations, we propose extensions of α PBGI t to the more general setting where costs are modeled using a log-normal process in Appendix B.4.Compared to cost-unaware acquisition functions such as EI, PBGI can be more risk-averse if costs are large or more risk-seeking if costs are small. In varying-cost budget-constrained settings, this tradeoff is mediated by λ, 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 is a high-variance point with a large cost, among a set of many low-variance low-cost points. In Figure 2 , we adapt the construction of Astudillo et al. [3] , Section A into a one-dimensional Bayesian optimization problem with a non-stationary prior, and observe that EIPC indeed has substantially worse performance than PBGI.The PBGI acquisition functions depends on f | x 1:t , y 1:t through its mean and standard deviation at each point. We plot this in Figure 3 . This shows for large λ that PBGI can resemble EI, whereas for small λ it is nearly linear. Specifically, in the λ → 0 limit, we haveEQUATIONwhere µ t and σ t are the mean and standard deviation of f | x 1:t , y 1:t . This expression is similar to the upper confidence bound (UCB) acquisition function whose dependence is exactly linear, with heterogeneous learning rate parameter set to η t = 2 log σt(x) λc(x) . A derivation is given in Appendix B.3. For small λ, one can thus view PBGI as giving a way to automatically tune UCB's confidence parameter in a careful way depending on c(x). 
experiments: 
 We now empirically evaluate the Gittins-index-based acquisition function on cost-aware problems. We also evaluate on the same problems with a spatially-constant cost function, a setting we term uniform costs-this facilitates comparisons with classical, cost-unaware baselines. In both cases, mirroring practical settings, we work with a deterministic, algorithm-independent evaluation budget.We implement all methods in BoTorch [4] using Matérn Gaussian processes with smoothness ν = 5/2. For Bayesian regret experiments where objectives are sampled from the prior, we fix the length scale to be κ = 10 -1 for both the prior and the posterior. For synthetic and empirical experiments, we apply maximum marginal likelihood optimization to dynamically adjust the length scale every iteration. To ensure that our results are not sensitive to these and other hyperparameter choices, all We evaluate both PBGI variants from Section 3.3, namely α PBGI with λ = 10 -4 , and α PBGI-D with λ 0 = 10 -1 and β = 2. To assure ourselves that performance differences are not primarily due to tuning, we deliberately use the same λ-values for PBGI and the same (λ 0 , β)-values for PBGI-D on all problems. Comparisons with other (λ 0 , β)-values can be found in Appendix D.2.For varying-cost problems-that is, those with spatially non-constant cost-we compare with expected improvement per unit cost (EIPC), multi-fidelity max-value entropy search (MFMES) [35] and budgeted multi-step expected improvement (BMSEI), which was proposed by Astudillo et al. [3] and has state-of-the-art cost-aware performance. For uniform-cost problems-that is, those with constant costs-we compare with expected improvement (EI), Thompson sampling (TS), upper confidence bound (UCB) with a time-dependent schedule [34] , max-value entropy search (MES) [37] , knowledge gradient (KG) [16] , and multi-step expected improvement (MSEI) [23] . We choose these because (i) they are standard, and (ii) acquisition function optimization succeeds for them on our problems, reducing confounding.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] d , and consider d ∈ {8, 16, 32}. Results, in terms of empirical regret curves and their associated quartiles, are shown in Figure 4 . Additional results for d = 4, 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 as different smoothness values and length scales, are included in Appendix C.In the low-dimensional case of d = 8, most uniform-cost and cost-aware approaches achieve similar performance. Once we increase dimension to d = 16, we see bigger differences: here, both PBGI variants achieve a modest improvement compared to expected improvement per unit cost. Strikingly, both PBGI variants are 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, as seen for the uniform-cost problem with d = 32, where no method outperforms random search.Next, we consider standard synthetic global optimization benchmark functions. To represent a variety of geometric properties, we examine the Ackley, Levy, and Rosenbrock functions. A visualization of the two-dimensional versions of 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 in Appendix C. We see that the behavior of different acquisition functions varies according to the the function. On the Ackley function, PBGI and PBGI-D outperform most baselines, except for the non-myopic BMSEI policy in the cost-aware setting. In contrast, on the Levy function, PBGI-D only outperforms the EIPC baseline on small-enough cost horizons, and PBGI is worse than PBGI-D on cost-aware problems: the same also holds for the BMSEI baseline, indicating that using multi-step lookahead actually reduces performance here-we will return to this momentarily in the context of the Rosenbrock function. 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 to this hyperparameter choice.We also examine performance on the unimodal, banana-shaped Rosenbrock-function. In this case, PBGI-D performs the strongest, matching expected improvement variants, while outperforming PBGI and multi-step lookahead baselines. This can intuitively be explained by the one-step optimality of expected improvement, which better-exploits the unimodal objective, while PBGI and multi-stepbased acquisition functions are more conservative and therefore require different λ-tuning to perform best. We conclude that PBGI-D may be a better choice in settings where there is a potential mismatch between the objective and the prior in terms of unimodality, as this can be counteracted in part by its decay behavior, particularly when compared to PBGI. 5 .Finally, we benchmark PBGI policies on three empirical global optimization problems motivated by applied challenges: Pest Control where d = 25 [29] , Lunar Lander where d = 12 [14] , and Robot Pushing where d = 14 [37] . Detailed descriptions of these problems and associated cost functions are in Appendix C. Note that, for Lunar Lander and Robot Pushing, the cost functions used are not automatically-differentiable. To avoid this challenge and illustrate how our acquisition function can be used when the cost function is unknown, we apply unknown-cost PBGI and baseline variants, where the costs are modeled using a 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 outperforms baselines on Pest Control and Lunar Lander, in both the cost-aware and uniform-cost settings. On the other hand, PBGI performs poorly on Robot Pushing, where instead expected improvement and PBGI-D perform best, and the non-myopic BMSEI baseline performs poorly. This mirrors behavior previously seen on the unimodal Rosenbrock function, from which we suspect unimodality-like behavior may be at play here as well. Note also that the performance gap between PBGI and UCB is substantially bigger here than on the Bayesian regret or synthetic problems: this may be in part because we tune UCB using the schedule of Srinivas et al. [34] , which is explicitly designed for the Bayesian regret setting, and may be less-ideal for other objectives.In comparison, PBGI's tuning works reasonably well on all three problem classes simultaneously.∂S → R by ∂r(s) = s.R |X| + → R defined by c → V (π,c) is affine for all π. 5. The map R |X| + → R defined by c → V ( * ,c) is convex, since it is a supremum of affine functions. We immediately note that this formulation extends to cover two variations of interest:1. Stochastic costs. One can handle this by replacing c with a probability kernel. In this case, letting m be the mean costs, we have V (π,c) = V (π,m) . Using this, we henceforth work with deterministic costs without loss of generality.2. Simple regret as a terminal reward. One can also consider an MDP with a stochastic terminal reward which subtracts the best-in-hindsight term sup x∈X 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 a random constant which is independent of the chosen actions, by linearity of expectation, the value function of this modified MDP is equal to those of our MDP up to a constant. We therefore omit this term without loss of generality.The expected budget-constrained setting does not directly incorporate costs into the MDP itself: more precisely, it takes c(s, a) = 0 within the MDP formulation, which means the value function of this modified MDP is V (π,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-optimal policy in the expected budget-constrained and cost-per-sample problems areEQUATION)where Π is the set of all Markov policies, and the feasible set for the expected budget-constrained problem isEQUATION)and T (π) is policy π's stopping time, that isEQUATION)which is bounded above by |X| < ∞. This defines the optimization problems under study. Define the set of maximizersEQUATIONwhich is non-empty, since, as said above, by MDP theory the supremum defining V ( * ,c) is achieved. Define also the set of feasible policies which satisfy the constraints in a tight manner, namelyEQUATIONWe are now ready to prove the claim in 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-multiplier-part of the argument. 
conclusion: 
 In this paper, we introduced a new acquisition function class for cost-aware Bayesian optimization, the Pandora's Box Gittins index, based on an unexplored connection between Bayesian optimization and the Pandora's Box problem from economics. 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 be largest on higher-dimensional and multi-modal problems. Our work constitutes a first step toward integrating ideas from Gittins index theory, including insights from generalizations of Pandora's Box, and related areas such as queueing theory, into Bayesian optimization. 1 From the visual, one can see that these functions differ in terms of multimodality and ridge-regions within the optimization landscape. 
 
 Appendix: Here we provide a set of additional illustrations to aid understanding of our results.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 7 provides a visual illustration of their two-dimensional variants. 1 This allows us to visually see the multimodality of the Ackley function, multimodality and ridge-like regions in the Levy function, and unimodality of the Rosenbrock function. While we use higher-dimensional versions of these in our experiments, this illustration provides some intuition for what the resulting the optimization landscape might look like, helping contextualize results.In Figure 8 , we see that EI's maximum occurs at a point near x ≈ 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 at 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-λ PBGI's maximum occurs at a point near x ≈ 0.86: it favors a riskier approach, preferring a location where the mean is smaller, but the variance is larger. This example shows potential differences in behavior between EI and PBGI, and illustrates how these differences are mediated by the parameter λ.In Section 3.3.3, we showed a cost-aware Bayesian optimization problem on which expected improvement per unit cost (EIPC) has poor performance. Here, we show that this problem can be modified so that ordinary expected improvement (EI), which ignores the cost function, also has poor performance-a somewhat obvious, but nonetheless important sanity check that we make to ensure that costs play a sufficiently-important role in problems of this class to merit their consideration. This is shown in Figure 9 . It is not hard to construct a less-visualization-friendly variant of these problems on which both expected improvement per unit cost and ordinary expected improvement perform poorly, by considering cost functions which are appropriately-weighted sums of bump functions.Below, we provide additional ideas to help understand the Pandora's Box problem and acquisition function that results from its considerations.In what follows, we sketch a viewpoint from which one can see the key idea behind why 1. Open the closed box. In this case, we pay a cost of c, but subsequently get to choose between taking the realized value f , or instead taking g from the box that was originally open. In expectation, the total value obtained by taking this action is E(max(f, g))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))c ≥ g, and take the reward from the open box if E(max(f, g))c ≤ g, with both actions optimal in the case of equality. As consequence, if g 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 whenE max(f -g, 0) = c (9)where in the case of multiple boxes the left-hand-side becomes the expected improvement function.The insight of Weitzman [39] -and indeed of Gittins [18] in a much more general setting-is that one can modify the Pandora'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 a final point, note that the assumption that c is deterministic is made without loss of generality: if c is instead stochastic but has finite expectation, the same reasoning applies, but with the value c in (9) replaced with its expected value. We will make use of this in Appendix B.4.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 EI 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, if costs are stochastic then c(x) should be replaced with its respective mean. We also omit time subscripts to ease notation.Proposition 3 (Gradient of PBGI). Let µ(x) and σ(x) be the mean and standard deviation of the posterior Gaussian process (f | x 1:t , y 1:t )(x). With this notation, the gradient of the acquisition function α PBGI (x) is given byEQUATIONwhere ϕ and Φ denote the density and cumulative distribution function of a standard normal distribution, respectively.Proof. Recall that when ψ(x) ∼ N(µ(x), σ(x)) is Gaussian, the expected improvement with respect to the comparator y is given asEQUATIONNext, note by definition of α PBGI , we haveEQUATIONDifferentiating this with respect to x on both sides givesEQUATIONApplying the product and chain rule to the left-hand-side givesEQUATIONEQUATIONEQUATIONEQUATION)Recall the identity for the derivative of the Gaussian density, namelyEQUATIONApplying this identity to (17) givesEQUATIONwhich is equal to the negation of (15), hence ( 15) and ( 17) cancel: we getEQUATION)Rearranging this gives the expression in the claim.We now derive the small-λ limiting expression for PBGI which was presented in Section 3.3.3.According to (11) and ( 12), we haveEQUATIONwhere µ t and σ t are the mean and the standard deviation of f | x 1:t , y 1:t , and u(•) is the solution ofEQUATION)When λ → 0, the solution satisfies u(•) → -∞. This implies that both Φ(u(•)) → 0 and ϕ(u(•)) → 0. Since ϕ(u(•)) dominates Φ(u(•)), we can approximate the solution u(•) by ϕ(u(•)) ≈ λc(•) σt(•) . By substituting the probability density function of a standard normal distribution for ϕ, we obtainEQUATIONThus, we can conclude that in the limit λ → 0, the Gittins index becomesEQUATIONAs consequence, we expect PBGI-D, whose λ-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 a result of this limit, unexplored regions where σ(x) ≫ 0 should eventually have acquisition values that are larger than regions where σ(x) ≈ 0. We believe this should hold regardless of whether the costs are known-our main focus-or unknown, especially if the cost function c(x) is uniformly bounded above and below.This because (25)'s dominant term in the λ → 0 limit is σ(x) 2 log 1 λ , which does not depend on the cost c(x).In the Lunar Lander and Robot Pushing empirical examples of Section 4, the cost function does not admit an analytic, automatically-differentiable form, and can only be evaluated in a black-box manner. To handle this, we model the logarithm of the costs as a Gaussian process, and condition this process on the costs observed at locations evaluated so far. This mirrors how unknown costs are handled in other acquisition functions, such as the budgeted multi-step expected improvement acquisition function of Astudillo et al. [3] .From the viewpoint of the Pandora's Box problem, stochastic costs make little difference: following the discussion in Appendix B.1, the optimality results of Weitzman [39] continue to hold even if costs are stochastic, so long as the costs in the formula for α ⋆ are replaced with expected costs. Mirroring this, if we plug in the mean of a log-normal random variable into the definition of α PBGI , we obtain the following acquisition function. Definition 4. Let c(x) be log-normal for all x. For a dataset (x 1 , y 1 ), .., (x t , y t ), let µ ln c and σ ln c be the posterior mean and posterior standard deviation of the log-costs. Define the unknown-cost Pandora's Box Gittins index acquisition function byEQUATIONThe interpretation of λ, namely as a hyperparameter that determines the expected budget the algorithm will use before reaching its respective stopping time, is the same as in the known-cost setting. One can define cost-per-sample and decay variants in the same manner as well.We now prove Theorem 2. In what follows, recall that the assumptions of Theorem 1 are (i) X is discrete, (ii) E |f (x)| < ∞ for all x, (iii) f (x) and f (x ′ ) are independent for x ̸ = x ′ , and (iv) the budget satisfies B > min x∈X c(x). Further, Theorem 1 was stated for deterministic costs: more generally, we allow for stochastic costs satisfying 0 < E c(x) < ∞, and in such cases instead define α ⋆ 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 • ∪ ∂S be the union of two disjoint sets, namely the set S • of non-terminal states and set ∂S of terminal states. These are described below: Transition kernel: define a Markov transition kernel such that for a non-terminal state s and an action a: 1. The value function V (π,c) : S → R is well-defined, where the superscripts denote the policy and the cost with respect to which the MDP is defined.(a) If box i is closed, that is, s i = ⊠,2. The optimal value function V ( * ,c) : S → R is also well-defined.3. There exists an optimal policy π ( * ,c) which achieves the optimal value V ( * ,c) .EQUATION)Suppose that the infimum of A is achieved, and denote it by λ * B ∈ [0, ∞). Suppose further that there exists an optimal policy for the cost-per-sample MDP for which the expected budget constraint is tight, namely π ∈ Π ( * ,λ * B c) ∩ Π (c) B,eq . Then we haveEQUATIONProof. We start by expressing the expected budget-constrained optimization problem in an unconstrained form via Lagrange multipliers, obtainingEQUATIONwhere the second line follows from the Lemma 10 since the respective Lagrangian equals V (π,λc) up to a constant, and the third line follows by definition of V ( * ,λc) is by definition the terminal reward minus the cumulative costs.Part I: convergence of (a). Define κ n (x) = min(f (x), α * n (x)), and define κ analogously. By Kleinberg et al. [24] , Theorem 1, we haveEQUATIONand analogously for λ, α * , and κ. We now argue that α * n → α * monotonically pointwise. Since λ n → λ converges monotonically, considerEQUATION)Recall that EI f (x, g) is continuous and strictly decreasing in g: hence, its inverse in g exists and is also strictly decreasing and continuous. We conclude that α * n → α * monotonically pointwise. From this, convergence of the respective expectations E max x∈X κ n (x), and therefore convergence of (a), follows by the Monotone Convergence Theorem.Part II: convergence of (b). We will need an identity involving the order in which boxes are opened: for this, we first prove that once a tie-breaking rule is chosen, for large enough n, π * n and π * open boxes in the same order. Since the number of boxes is finite, and α * n → α * monotonically pointwise from (a): it follows for n large enough that, if there are no ties in α * (x), then π * n opens boxes in the same order as π * . If there are ties in α * , we choose a tie-breaking rule so that π * n and π * open boxes in the same order. It follows that, once this choice is made, for n large enough, all policies open boxes in the same order x 1 , .., x |X| , with different π n and π * possibly stopping at different times.The identity we seek will differ depending on how tie-breaking rules regarding when to stop are handled: recall that ties can occur when opening the box x t ∈ X at time t, we have α * (x t ) = f * t , where f * t is the best observed value up to time t. We adopt the following tie-breaking rule for stopping, depending on whether or not λ n is an increasing or decreasing sequence:• If λ n is increasing: let π * = π * + be the policy that opens the best closed box in the event of a tie. • If λ n is decreasing: let π * = π * -be the policy that stops in the event of a tie.Note also that if λ n 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 π * n , letting π * n,+ and π * n,-be the respective policies. Let x 1 , .., x |X| denote boxes in the order they are opened. Then the expected total costs areEQUATION) (iii) = |X| i=1 P(f (x j ) ≤ α * (x i ), 1 ≤ j ≤ i)c(x i ) (iv) = |X| i=1 i-1 j=1 P(f (x j ) ≤ α * (x i ))c(x i ) (45)where (i) follows by writing the probability as an expectation of an appropriate indicator, (ii) follows by noting that under the policy π * + , the event T (π * + ) ≥ i occurs if and only if at each time j = 1, .., i, the best observed value f * j is not higher than the Gittins index of x j , (iii) follows by expanding the maximum which defines f * j and using monotonicity of α * (x j ) in j to simplify the resulting events, and (iv) follows by independence of f (x j ) and f (x j ′ ) for j ̸ = j ′ . Using this, it suffices to showEQUATIONEQUATION)The former equals the cumulative distribution function of f (x j ), which is right-continuous, evaluated at α * n (x i ). The latter is similar but is instead left-continuous. For π * n,+ , since λ n is increasing, we have that α n (x) is decreasing, and the claim follows by right-continuity. For π * n,-since λ n is decreasing, we have that α n (x) is increasing, and the claim follows by left-continuity.We are now ready to prove the key property needed to apply Lemma 5. Proof. By the Envelope Theorem-specifically, Lemma 13-we have for λ ∈ [0, ∞) thatEQUATIONwhere all Gâteaux derivatives-see Definition 11-are taken with respect to λ and exist by convexity, and the pointwise convergence condition of Lemma 13 follows by first noting thatEQUATIONand applying Lemma 7. By the first-order optimality conditions, we haveEQUATIONCombining this with the above, we concludeEQUATIONSince λ * B > 0, this expression holds for v equal to ±1: plugging this in, we getEQUATIONNow, let π -be a policy from the minimizer set, and let π + be a policy from the maximizer set. Define a third policy π α which randomizes between the two, choosing π -with probability α and π + with probability 1α. Since π + and π -are optimal, they achieve the same value, so by convexity π α also achieves the same value: therefore, π α ∈ Π ( * ,λ B c) . On the other hand, the expected total costs of π α are a convex combination of the expected costs of π -and π + : since the former lower-bounds B and the latter upper-bounds B, there exists an α ∈ [0, 1] for which the costs of π α are exactly B.Taking π = π α for this value of α, we obtain π ∈ ΠB,eq and the claim follows.To complete the proof, we show the minimizer set of A does not contain zero.Lemma 9. Let λ * B ∈ [0, ∞) be any minimizer of A, then λ * B > 0.Proof. From the derivative calculation used in proof of Lemma 8, plugging in v = 1 into the respective Gâteaux derivative, we obtainEQUATIONIf λ = 0, 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 is equal to the total cost of all the boxes. This givesEQUATIONwhere the inequality follows by the assumption that the expected budget constraint is active. The claim follows.With these results at hand, we are now ready to prove the main claim.Theorem 2. Consider the expected budget-constrained problem, with the assumptions of Theorem 1.Assume the problem is feasible and the constraint is active, namely min x∈X c(x) < B < x∈X c(x).Then there exists a λ > 0 and a tie-breaking rule such that the policy defined by maximizing the Gittins index acquisition function α ⋆ (•), defined using costs λc(x), is Bayesian-optimal.Proof. Combine Lemma 5 with Lemmas 6, 8 and 9.We conclude by comparing this claim and proof with the results of Aminian et al. [2] :1. The objective of their expected budget-constrained problem is more general: while we focus on minimizing simple regret, Aminian et al. [2] 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 f (x) has finite support for all x. This results in a significant technical difference: we must apply a sharp envelope theorem with an explicit supremum to conclude that the expected budget constraint is satisfied. More-straightforward results such as those presented by Milgrom and Segal [28] , or their subdifferential-formulated analogues as found in the proof of Aminian et al. [2] , Proposition 1 (iii), would not suffice: due to an explicit counterexample involving upside-down-absolute-value functions, without suitable structure, one cannot conclude that the supremum is achieved and the resulting inequality is tight. As an alternative to our approach, one could instead appeal to finiteness of the class of deterministic policies-which Aminian et al. [2] assume, leading to piecewise-linear 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 instanceEQUATIONFor this problem, this optimal value is upper-bounded by the optimal value of the expected budgetconstrained optimization-specifically, V( * ,c) asbc ≤ V ( * ,c) ebc , since Π (c) B,as ⊆ Π (c) B .Below we state and prove three results from optimization theory: a 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 R d , or, if not that, that it is a Banach space, whereas we need results that hold when the domain of optimization is an arbitrary set, without a 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 → R and let g :EQUATIONMoreover, suppose there exist x * , λ * which satisfy L(x * , λ * ) = inf λ≥0 sup x∈X L(x, λ) and g(x * ) = y. Then we have supEQUATIONProof. First, we show that for all x, we haveEQUATIONTo show this, suppose first that g(x) ≤ y. Then λ(g(x)y) ≤ 0, hence its negation is non-negative, and minimized at λ = 0. Now, suppose the converse. Then λ(g(x)y) > 0, so its negation is negative, and the objective can be made arbitrarily close to -∞ by scaling λ. Using this, writeEQUATIONWe now argue that, under the claim's additional assumption, one can swap the order of the supremum and infimum. Let x * , λ * be a pair for which the constraints are tight. ThenEQUATION= supEQUATIONwhere (i) follows by definition of λ * , (ii) follows by the fact that x * achieves the supremum and satisfies g(x * ) = y, (iii) follows by the fact that, when restricted to the set {x ∈ X : g(x) = y}, L(x, λ) is constant in λ for all x-values, hence the infimum is taken over constant functions, (iv) follows by making the feasible set larger. Combining this with the sup-inf inequality [9] supEQUATIONgives the claim.It is easy to see that this argument holds even if one lets y take values in an infinite-dimensional vector space, as long as λ takes values within a 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 a topological vector space, let X ⊆ X , and let f : X → R be a function.The Gâteaux derivative ∂ v f (x) ∈ R of a function f at a point x ∈ X in the direction v ∈ X , if it exists, is defined asEQUATIONNote that we require no properties of our Gâteaux derivatives: in particular, ∂ v f (x) can be non-linear in v, though one can easily see that it will always satisfy ∂ αv f (x) = α∂ v f (x) for α ≥ 0. If f is a convex function, one can show by monotonicity of finite differences that ∂ v f (x) always exists-in the non-extended-valued sense defined above-on 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 [28] , Theorem 1, which is formulated in the language of leftderivatives and right-derivatives: Milgrom and Segal [28] state in a footnote that their claim also holds in a 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 a 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 beEQUATIONSuppose that, for every θ ∈ Θ, the supremum is achieved, and let X * (θ) be the maximizer set. For any v, suppose that the Gâteaux derivatives ∂ v V(θ) and ∂ v f (x, θ) exist and are finite-valued, with the convention that the Gâteaux derivative of f is taken in its second argument. ThenEQUATIONProof. Fix θ ∈ Θ, and let x * (θ) ∈ X * (θ) be an arbitrary maximizer. Note that, for all θ ′ ∈ Θ and all x * (θ ′ ) ∈ X * (θ ′ ), by optimality we haveEQUATIONwith equality for θ ′ = θ. Letting ε > 0 be sufficiently small, taking θ ′ = θ + εv, subtracting f (x * (θ), θ) = V(θ) from both sides, and dividing by ε, we getEQUATIONthus taking limits as ε → 0 givesEQUATIONThis holds for all choices x * (θ) ∈ X * (θ), and the claim follows.For our arguments to go through, we need a sharper version of this result, with the inequality replaced with an equality. Results like this go back at least to Danskin [11] , and are proven by Bonnans and Shapiro [8] , Proposition 4.12, Başar and Bernhard [5] , Theorem 10.1, and Bertsekas [7] : however, all of their claims require topological assumptions on the domain of optimization. Moreover, it is easy to see-for instance by considering an envelope made up of upside-down absolute value functions, where V(θ) is constant but f (x, θ) 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 f (x, θ) is affine in θ for all x, and that for any monotone θ n → θ there exist x * (θ n ) ∈ X * (θ n ) and x * (θ) ∈ X * (θ) such that f (x * (θ n ), v) → f (x * (θ), v). Then we haveEQUATIONProof. For any ε, note thatEQUATIONwhere the respective term is negative because f (x * (θ + εv), θ) ≤ f (x * (θ), θ), which holds by optimality of x * (θ). Taking limits givesEQUATIONwhere the final equality follows from the expression for the Gâteaux derivative of a linear function.Combining this expression with the Lemma 12 shows that the respective supremum is achieved, and gives the claim.We implement all experiments in BOTORCH [4] . 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. 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-expensive KG, MSEI and BMSEI baselines: more information with a direct runtime comparison is given in Appendix D.1.Gaussian process models. In the Bayesian regret experiments shown in Figure 4 , we use Matérn kernels with identical fixed hyperparameters-namely smoothness 5/2 and length scale 10 -1 -for 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] d 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.4.Acquisition function optimization. This is done as follows. We begin by computing acquisition values at 200d points spread across the domain X, where d is the dimension of X. For all acquisition functions except MSEI and BMSEI, which use a modification described below, the initial 200d points are generated using a Sobol sequence design. From these, 10d points are selected according to the initialization heuristic used by BoTorch, detailed in Balandat et al. [4] , Appendix F.1. We then use multi-start L-BFGS-B to optimize the acquisition function from each selected point. The point with highest acquisition value among the 10d optimized points is chosen as 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. [23] , Appendix D and Astudillo et al. [3] , 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 to be λ 0 = 0.1 and the constant decay factor β = 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 UCB, we follow the schedule in Srinivas et al. [34] , Theorem 1 given by η t = 2 log(dt 2 π 2 /6δ), 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 4 lookahead steps, each with a batch size of 1 and a single fantasy point.Omitted baselines. We omit MSEI from the Bayesian regret plots for d = 16 with κ = 10 -1 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. [23] results in frequent crashes due to running out of memory and related issues when used on higher-difficulty problems. We also omit KG from d = 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 search (PES) acquisition function of Hernández-Lobato et al. [22] , but could not get its computations to run reliably in an automatic-differentiation-based environment without resulting in NaN gradients. Hernández-Lobato et al. [22] document this behavior, and suggest using finite-differencing in situations where it occurs: however, from initial examination, we found this to decrease performance on higher-dimensional problems. We therefore opted to restrict ourselves to automatically-differentiable 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 a draw from a Fourier feature approximation of the respective Gaussian process prior, drawn in such a 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 functions: 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 isEQUATIONand s 1 = sin(πw 1 ) 2 , and search domain X = [-10, 10] d . EQUATIONwhere S is an affine map used to standardize the input domain: specifically, S(x) = Ax + b where A is a diagonal matrix and b is a vector, both chosen so that the image of X under S is [0, 1] d .Objective functions: empirical. We now detail the empirical objective functions.Pest Control (d = 25). The pest control problem, as described in Oh et al. [29] aims to minimize the spread of pests as well as the costs of prevention treatment. We adopt the experiment setup from Li et al. [26] , framing this as a categorical optimization problem with 25 variables, each representing a 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 automatically-differentiable manner, thus this problem is a known-cost problem.Lunar Lander (d = 12). Following the setup in Eriksson et al. [14] , we consider a reinforcement learning problem optimizing a controller for the lunar lander as implemented in OpenAI Gym, which includes 12 continuous input dimensions for engine throttle adjustments. The state space captures the lander'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 found in the code associated with Li et al. [26] . Note that this objective involves the number of actual ). We see that runtime of PBGI is slightly slower than EI and TS, but significantly faster than KG and MSEI.simulation steps used, and is therefore not automatically-differentiable: and 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 [37] , where two robots work to push two objects to their specified targets. The problem'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 and the unknown-cost variants variant is the sum of their traversal distances representing the total energy use, similar to the cost function used for energy-aware robot pushing benchmark of Astudillo et al. [3] , but with one modification: we use the distance traversed by the robot arms instead of the distance the objects being moved.To understand the effect of this difference, we include the results for both the unknown-cost and known-cost versions in Appendix D.3.Here, we provide additional experimental results to better understand performance differences and other aspects of policy behavior, including the effect of various problem hyperparameters.Here, we provide a runtime comparison between PBGI and various baselines, including inexpensive baselines such as EI and TS, and expensive ones such as MSEI. We do so in the Ackley synthetic benchmark setting, using the same hyperparameter settings as the main experiments. We measure the time to compute and optimize the acquisition function.Results can be seen in Figure 10 . We see that PBGI is slightly slower than EI and TS, but significantly faster than either KG or MSEI, though the runtime of the latter decreases substantially as it accumulates more data. Overall, we conclude that PBGI's runtime is closer to that of classical acquisition functions than sophisticated lookahead-based variants.Next, we examine the behavior of different hyperparameter choices for λ 0 and β in PBGI-D. Recall that this variant sets λ t = λt-1 β at times when the Gittins stopping rule triggers, and λ t = λ t-1 at all other times. To understand this, we examined regret curves in the Bayesian regret setting of Section 4 with d = 8 under different choices. Results can be seen in Figure 11 . We see that behavior of different λ 0 -values is qualitatively similar to that of different λ-values in PBGI, but with substantially smaller differences between variants, which are detectable primarily due to the relatively-large number of We see that smaller λ 0 -values act similarly to the behavior seen in Figure 3 for PBGI, trading off risk-seeking vs. risk-averse behavior, but with a substantially smaller gap between the two variants.Larger β-values lead to more-abrupt decay curves for λ, with an effect qualitatively similar to λ 0 . In both cases, though our relatively-large sample size allows us to see small differences between methods, their overall impact on performance is close-to-nonexistent on the scale of variability.seeds used in each experiment. Smaller values of λ 0 tend to lead to very slightly to higher regret on small time scales, but very slightly lower regret on larger time scales. Behavior for β is similar: larger values lead to a more gradual decay of λ, but with minimal overall impact on performance, especially in comparison to between-seed variability. We conclude that, in terms of regret, PBGI-D is less sensitive to hyperparameter choice compared to PBGI.The Robot Pushing empirical benchmark involves two cost functions: a known-cost variant representing total operational duration, and an known-cost variant representing total distance traversed, a proxy for energy use similar to the variant considered by Astudillo et al. [3] . One can therefore ask: how different is the resulting algorithm behavior in these two settings? Figure 12 shows this: it reveals that for the known-cost variant, EIPC and PBGI-D perform similarly, whereas for the unknown-cost variant, PBGI-D achieves the best performance on all except the shortest time horizons, where EIPC is instead competitive. Other baselines, most notably BMSEI, substantially underperform EIPC and PBGI-D, behaving similarly in both settings.Choice of kernel. To check whether our results are sensitive to the kernel used for the Gaussian process model, we replicated the Bayesian regret experiments with Matérn kernels with smoothness parameters ν = 3/2, 5/2, as well as the squared exponential kernel, which is the limit of Matérn kernels as ν → ∞ [30] .Similar to the original results of Figure 4 , we can clearly see from Figure 13 and Figure 14 that behavior splits into three regimes:1. Easy: d sufficiently-small, most policies achieve similar performance. 2. Medium-hard: d moderate-to-large, both PBGI variants perform better than baselines.3. Very hard: d sufficiently large, no policy outperforms random search.We also see that d = 32 lands in the very-hard regime for the uniform-cost case 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 at which regimes switch differs. In particular, for the squared exponential kernel, the separation between the medium and the hard regime appears earlier than for the other variants: all policies there have similar performance to random search when d = 16. Figure 12 : Experimental results for the Robot Pushing empirical benchmark, with the known-cost variant (left) and unknown-cost variant (right). We see that performance overall is similar, with EIPC and PBGI-D performing strongest. Their relative performance is similar in the known-cost variant, whereas in the unknown-cost variant PBGI-D outperforms EIPC on sufficiently-large horizons, and vice-versa on sufficiently small horizons.Choice of length scale. To check whether our results are sensitive to the Gaussian process model's length scale, we compare κ = 10 -1 with κ = 5 • 10 -1 and κ = 10 0 . From Figure 15 and Figure 16 , which show uniform-cost and cost-aware results, respectively, we can see that PBGI variants also have much better performances as the dimension increases in both scenarios. Since κ = 10 0 and κ = 5 × 10 -1 result in easier problems than κ = 10 -1 , in the uniform-cost case d = 32 lands into the medium-hard regime rather than the very-hard regime. This visual originally appeared in Terenin[36], and is reproduced here with permission. 


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - Some parts of this work are not clear.
- Experimental results seem not promising.
- Writing can be improved more.
questions: 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.
- Line 111, for "is in widespread use," can it be a real reason?
- For the Pandora's boxes, do you assume that there exist infinite boxes? or, there exist a finite number of boxes?
- Line 152, a period is missing.
- How did you optimize Equations (5) and (6) in practice?
- Figures 2, 3, and 4: which function is used to be optimized for each figure?
- Figure 3: I don't understand the effect of $\lambda$. According to Figure 3, it should be as small as possible.
- For dynamic decay, it is just constant decay, right? $\beta$ is a constant.
- Line 248, how did you choose $\lambda$ and $\beta$? Is there any guidance for these selections?
- Line 250: for "even though per-problem tuning could be advantageous," is it guaranteed? Is there any evidence for this?
limitations: limitations: I don't think that there are any particular societal limitations of this work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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$. 

3. 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.

Reference: 
- 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.
questions: questions: 1. What are the expectations in (4) with respect to?
2. Could the author clarify the discussion in line 104 to line 109. I'm not sure if the context assumes constant cost or not.
3. Could the author clarify the optimality claimed in line 103? I'm not aware that EI bears the tightest BCR or BSR bound.
limitations: limitations: Discussed above.
paper_summary: paper_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.
strength_weakness: strength_weakness: **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.

**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.

**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.

**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.

**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)\\}$.
questions: 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.

(1) Why not use MLE to find the appropriate lengthscale for each experiment?

(2) Have you studied the relation between $\kappa$ and the dimensionality of the function domain $d$ w.r.t. PBGI performance?

(3) Do you have any insights on how to calibrate $\lambda$ and $\beta$?

(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: limitations: Yes they did, and I believe the discussion period will shed even more light on the limitations of PBGI.
paper_summary: paper_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.
strength_weakness: strength_weakness: __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.

__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? 

__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.

__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.

With that said, I believe these weaknesses are what separates a currently good paper from a very good one.
questions: 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?

__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: Limitations have been properly addressed.

Comments: title: Acknowledgement
Response to Rebuttal
Rebuttal Ack
comment: I sincerely appreciate the expedited response by the authors. I apologize for finding it difficult to understand the sketch proof fully. Here are my questions about this proof. 

1. The proof claims that MES/cost favors the high-value arms. I, in general, understand that the intention is to dilute the mutual information of high-value arms slower through the slow decrease of $\epsilon$ and a fast increase of $M$. Yet the exact rate is unclear to me. The mutual information for both sets is strictly positive unless $M \rightarrow \inf$ for the lower value set and $\epsilon\rightarrow\inf$. I prefer that the authors offer the exact rate as the feasibility of directing MES/cost to the high-value arms is not obvious, especially when the 1/2 distribution for each arm in the lower-value set makes the arms actually attractive to MES. In addition, when $\epsilon\rightarrow\inf$, the mutual information also goes to zero for the higher value set. If the $\epsilon$ does not go to $\inf$, I don't think the MES/cost is arbitrarily worse. Instead, the higher value set is arguably more favorable with a sufficient budget, though the expected reward could possibly be lower.

2.  The unit cost actually regresses the scenario to standard BO. In this case, the analysis of MES reveals an order optimally simple regret bound, yet the results seemingly contradict that.  Could the author comment on it?
# Theory sketch: counterexample for MES

**Here is a proof sketch showing that MES or MES/cost can have arbitrarily poor performance compared to the optimal policy.**
This proof sketch is inspired by the Astudillo et al. 2021, though the construction is slightly different and takes specific advantage of the characteristics of MES. 
While this example is discrete and uses binary-valued arms for simplicity of understanding, **we believe that these ideas can be extended to construct a smooth counterexample where MES variants (with or without cost)** will perform poorly when used with Gaussian processes.

The example has two groups of arms:

* Group 1: $N$ independent arms ("high-value arms")
  * Cost is $1$
  * Value is $1$ with probability $\epsilon$ and 0 with probability $1-\epsilon$.

* Group 2: $M$ additional independent arms ("lower-value arms")
  * Cost is $1$
  * Value is $1-\delta$ with probability $1/2$ and $0$ with probability $1/2$

The probability distribution over the maximum is:
* $\max = 1$, with probability $p(N)$, where $p(N) = 1-(1-\epsilon)^N$
* $\max = 1-\delta$, with probability $(1-p(N))(1-2^{-M})$
* $\max = 0$, otherwise

We send $M$ to infinity so that these probabilities become:
- $\max = 1$ has probability $p(N) = 1-(1-\epsilon)^N$
- $\max = 1-\delta$ has probability $1-p(N)$
- $\max = 0$ does not happen

Here, $\epsilon$ and $\delta$ are strictly positive values.

The information gain is:
* Strictly positive for pulling a high-value arm (this can be seen via direct computation of the expected entropy or via an argument based on mutual information)
* Goes to zero as $M$ goes to infinity for pulling a lower-value arm (since pulling the arm does not change the distribution of the max, in the limit as $M$ goes to infinity)

First, observe the following, holding $\epsilon$ and $\delta$ fixed.
Suppose we have a budget $B$ less than $N$.
* For sufficiently small $\delta>0$, it is optimal to pull the lower-value arm repeatedly until one gives value $1-\delta$, after which it is optimal to pull a higher-value arm. This gives value at least $(1-\delta)(1-2^{-B})$, where $B$ is the budget.
This problem meets the assumptions of the expected budget constrained Pandora's box setting and so, for an appropriately chosen $\lambda$, by optimality, the Gittins index policy chooses this optimal arm.
* But MES/cost continually pulls the higher-value arm, and obtains value $1-(1-\epsilon)^B$.

Then, we send $\epsilon$ to $0$ (we must ensure that $M$ goes to $\infty$ at a sufficiently fast rate relative to $\epsilon$).
Under this change, MES/cost obtains value converging to $0$,
while the value of the optimal policy remains strictly positive and bounded below by $(1-\delta)(1-2^{-B})$.

Thus, the value of MES/cost divided by the value of the optimal policy converges to $0$.

**We will incorporate this argument - together with a Bayesian optimization example in the spirit of Figure 2 - in the next manuscript version. We will also add MES and MF-MES as baselines to all our experiments in the next manuscript version.**
Thank you for your prompt response.  Indeed I was confused about some points, which have been already resolved.

Because most of my concerns are answered, I will raise my score to 5.

Please update your manuscript considering all the comments provided by reviewers.
Thank you again! Your specific comments on individual phrases in our manuscript have been very helpful.

**(1)** We have had an extended discussion of the phrase "EIPC ... is in widespread use" on line 111 of our manuscript. We understand your viewpoint. We propose to replace "is in widespread use" with the text below.

* _Several factors point to EIPC's continued use: it is the default in the BoTorch software package, it has been used in a recent studies (for instance, Pricopie et al. 2024), and the paper that proposed it continues to receive high citation counts (1588 in 2023 alone)._
* Reference: _Pricopie, Stefan, et al. "Bayesian Optimization with Setup Switching Cost." Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2024._

**(2)** Regarding our discussion about per-problem tuning, your original comment was:

* _"Line 250: for "[...] per-problem tuning could be advantageous," [...] evidence for this?"_

The full sentence to which you referred is:

* _"To ensure that performance differences are not primarily due to tuning, we deliberately use the same $\lambda$-and-$\beta$-values on all problems, even though per-problem tuning could be advantageous."_

On basis re-examining your comments, we will simply remove the phrase "even though per-problem tuning could be advantageous." This is not central to our point.

**(3)** You gave several useful pieces of detailed feedback on improving the following: figure captions, clearly explaining the motivation for using the word "dynamic" in the name PBGI-D, and more clearly explaining that the boxes themselves do not change (our updated appendix now includes a formal mathematical presentation, as needed to handle the updated Theorem 2).

We will make these updates to the text in our revision. While we previously offered detailed answers to your questions, we now understand that you were not trying to tell us that you were confused about those points, and were simply drawing attention to opportunities to improve the clarity of the manuscript. Thank you for these suggestions.
Thank you for your response.

> Proving widespread use of EIPC is not relevant to our contributions

This is my point. The authors cannot prove this and it might not be a real reason. I would like to say that the authors used this sentence in the submission and I just asked if it can be a real reason. Then, the authors' answer was it is because of the default setting of BoTorch, which is not relevant to this proof. Now, the authors stated that it does not prove that it is in widespread use.  I simply recommend to remove this sentence if you cannot prove this.

> Finally, it is absolutely standard to discuss strenghs and weaknesses of a key baseline

No, you wrote the weaknesses you cannot prove. It is not absolutely standard.

> Answer for "I don't understand these sentences. I think that they are not in the captions (you also mentioned that you intentionally defer most details). I think it is a minor thing. You can point where the details are described more specifically"

I don't understand why the authors explicitly explain them to me. My point is that I (including potential readers) cannot know which functions are exactly used based on their captions. You have to improve the presentation of the figures.  I don't matter if their details are described in the appendices or the captions. You need to exactly indicate where they are described, when you prepare for a revision.

> In the Pandora's Box problem, the indices, values, and costs of the boxes are part of the definition and are therefore fixed. The only change throughout the decision process is the replacement of the reward distribution with the actual value inside once a box is opened. This is described in full on lines 125-135.

No, Lines 125-135 don't explain whether boxes are updated or not. Thus, I was curious about it.

> We chose to use "dynamic" in the name because the times at which decay occurs are dynamic: that is, the decay times depend on the data observed by the algorithm. This is clarified on Lines 205–206 in the same sentence that introduces the decay parameter $\beta$.

In Lines 205-206, there is no description why it is dynamic.

> This claim is supported by Figure 3, which shows direct numerical evidence that tuning $\lambda$ according to the evaluation budget is advantageous.

It is only for a single function and also there are no confidence intervals.  It is not enough for the numerical evidence of how we can choose $\lambda$ and $\beta$.

I was just curious about the missing details of the submission, which can be added to improve this work.  The authors didn't want to clarify them, and just mentioned the unclear sentences the details are missing.  I still think that this manuscript should be improved more.
I appreciate the authors' responses to my concerns over the literature and experiments. From my perspective, MES (and multi-fidelity MES, which is the cost-aware variant) alleviates the problem of optimizing the PES acquisition function and shows better performance than PES, as was reported in the MES paper. They are widely available as part of the Botorch standard library and are easy to implement. One tutorial is available at the following link: https://botorch.org/tutorials/max_value_entropy. Most importantly, the mutual information-based method bears better theoretical interpretation than EIPC in both the asymptotic and finite-budget scenarios. I don't foresee the problem of EIPC being extended to MF-MES unless the author offers corresponding proof or empirical evidence. Then, I would be pleased to increase my score and trust that the authors could amend the corresponding results in the camera-ready version.
Thank you for your feedback. Let us clarify further the points raised in your comment.

> I don't agree with your statement. How does the fact that the default setting of BoTorch is EIPC support this sentence "In spite of this rather negative theoretical outlook, EIPC is in widespread use"? Do the potential users of BoTorch use this algorithm despite of the negative theoretical outlook? I believe that scientific writing should be humble and respectful to other previous work.

**This comment took us by surprise.** Let us quote the relevant lines in full rather than in part:

* _"In spite of this rather negative theoretical outlook, EIPC has been shown to work well on many practical problems, is computationally efficient and reliable, and is in widespread use. We therefore ask: can one develop a technically-principled and computationally-straightforward alternative with at-least-comparable empirical performance?"_

We acknowledge that EIPC being the default setting in BoTorch does not _prove_ that it is in widespread use, however much this may suggest it. The theoretical limitations of EIPC are from rather recent work (Astudillo et al., 2021), so it is possible that the community is not yet aware of them. With this said, **proving widespread use of EIPC is not relevant to our contributions**.

Finally, **it is absolutely standard to discuss strenghs and weaknesses of a key baseline**, especially in the context of motivating the ideas introduced in a paper. We firmly believe our discussion (quoted above) of EIPC's strengths and weaknesses is fair and respectful.

> I don't understand these sentences. I think that they are not in the captions (you also mentioned that you intentionally defer most details). I think it is a minor thing. You can point where the details are described more specifically.

For Figure 2, the prior distribution from which the objective functions are sampled and the cost function are **explicitly displayed in the left and middle column of that figure.**

For Figure 4, these are **given in lines 261 and 499-501:** these state that the objective functions are random functions sampled from a Gaussian process prior using a Matérn-5/2 kernel.

To avoid any omissions, **we will ensure detailed versions of the points below are added to the updated experiment description appendix:**

* Figure 2: The probability density function of the prior distribution and the cost function are both scaled Gaussian densities plus a constant.

* Figure 3: We believe the question refers to the right plot. The objective functions are the same as those for the $d=8$ uniform-cost plot in Figure 4 (see below).

* Figure 4: The objective functions are drawn from the respective Gaussian process prior, drawn in such a 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. (To be fully precise: sample paths are computed up to a negligible approximation using 1024 Fourier features - this technique is standard, see Section 4 of "Pathwise Conditioning ..." by Wilson et al. JMLR 2020 for a description.)

> Do you update a set of boxes? If so, when is it updated?

In the Pandora's Box problem, the indices, values, and costs of the boxes are part of the definition and are therefore fixed. **The only change throughout the decision process is the replacement of the reward distribution with the actual value inside once a box is opened.** This is described in full on lines 125-135.

> I don't think it is dynamic because a decay rate is constant. Imagine learning rate decay. We don't call it dynamic decay if a decay rate is constant. But, if you want to call it dynamic decay, you need to clarify this.

We chose to use "dynamic" in the name because **the times at which decay occurs are dynamic:** that is, the decay times depend on the data observed by the algorithm. This is clarified on Lines 205–206 in the same sentence that introduces the decay parameter $\beta$.

> I trust the authors' argument that a non-optimally-tuned value is used. However, it [the claim that problem-specific tuning is advantageous] should be supported by scientific and numerical evidence.

**This claim is supported by Figure 3, which shows direct numerical evidence that tuning $\lambda$ according to the evaluation budget is advantageous**. This is because the color of the curve with the smallest regret value depends on the time point.

> It should be also supported by numerical results.

Please see our response to the previous point.
Thank you for making us aware of this variant of Thompson sampling that allows for an exploration / learning rate parameter! We will add this to our references, and we will feature UCB and Thompson sampling our discussion on Lines 104-109 accordingly.

We appreciate the suggestion to compare against an information-theoretic acquisition function. In the time since submission, we've benchmarked against predictive entropy search (PES). **Our results indicate that on uniform-cost problems, the performance of PES is significantly worse than other baselines, such as UCB.** We believe this may be in part due to the difficulty of optimizing the PES acquisition function, which requires a Monte Carlo scheme for handling gradients. Given that Takeno et al. (2020) provides a similar acquisition function using the max-value entropy search (MES) divided by the cost (i.e., it is "MES per unit cost"), we believe it would suffer from similar difficulties. Moreover, we expect this acquisition function to suffer from issues similar to those of EIPC.
I appreciate the follow-up by the authors regarding the problem formulation and the comparison to existing methods. I'd like to conclude my evaluation with the following. 

I believe that all reviewers appreciate the idea of this work, which brings a novel perspective to the cost-aware BO. And I also think that this one-step optimal algorithm could possibly bear a strong performance. 

On the other side, though the high-level idea is conveyed well, I believe the details in the presentation, especially the problem formulation, the scope of the work, and the analysis of the consistency and Bayesian optimality, require non-trivial revision to qualify it for acceptance, from my perspective. Nevertheless, I trust the author on this part.

I'm also concerned about the experiments. Regarding the UCB and TS questions I raised in my previous comments. I want to bring the paper by Chowdhury and Gopalan (2017) to the author's attention as TS should also allow applying a $\beta_t$. My previous comments mentioning the discussion in lines 104 to line 109 are intended to say that if there exists theoretical analysis on dealing with different constant costs, it could be misleading. At least to me, the discussion in lines 104 to line 109 leaves an impression that there is no such solution in literature, not limited to EI. In addition, the information-theoretic method is missing in the baselines. Despite the authors' argument that the formulation differentiates from the multi-fidelity setting, the known cost scenarios could naturally be handled by the existing SOTA entropy-based method (MF)BO algorithm, e.g., MF-MES by Takeno et al. (2020). Such an algorithm could efficiently approximate the acquisition using MC estimation while the known cost problem regresses to a special case discussed by the corresponding work. Since the author argues that known cost is the primary focus of the paper, missing such baselines could downgrade the significance of the empirical strength, which is one important merit of the paper, given that the regret rate is not available.


***References***

- Chowdhury, Sayak Ray, and Aditya Gopalan. "On kernelized multi-armed bandits." In International Conference on Machine Learning, pp. 844-853. PMLR, 2017.

- Takeno, Shion, Hitoshi Fukuoka, Yuhki Tsukada, Toshiyuki Koyama, Motoki Shiga, Ichiro Takeuchi, and Masayuki Karasuyama. "Multi-fidelity Bayesian optimization with max-value entropy search and its parallelization." In International Conference on Machine Learning, pp. 9334-9345. PMLR, 2020.
Thank you for your detailed response.

> We would be delighted to hear pointers to specific paragraphs so that we can improve our work.

This comment is the summary of my review. I have already described specific things in Questions and you have answered them.

> Could 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.

I don't agree with your statement. How does the fact that the default setting of BoTorch is EPIC support this sentence "In spite of this rather negative theoretical outlook, EIPC is in widespread use"? Do the potential users of BoTorch use this algorithm despite of the negative theoretical outlook? I believe that scientific writing should be humble and respectful to other previous work.

> These 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.

I don't understand these sentences. I think that they are not in the captions (you also mentioned that you intentionally defer most details). I think it is a minor thing. You can point where the details are described more specifically.

> In the Pandora's Box problem, the number of boxes $|X|$ is finite: this is given on line 126.

Do you update a set of boxes? If so, when is it updated?

> The times when the multiplier is applied are dynamic.

I don't think it is dynamic because a decay rate is constant. Imagine learning rate decay. We don't call it dynamic decay if a decay rate is constant. But, if you want to call it dynamic decay, you need to clarify this.

> In 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.

I trust the authors' argument that a non-optimally-tuned value is used. However, it should be supported by scientific and numerical evidence.

> Yes, 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.

It should be also supported by numerical results.
Thank you very much for your prior responses! We very much appreciate your engagement with our submission and your follow-up questions.

We were wondering if our replies have adequately addressed some or all of your most significant concerns, both from your original review and your follow-up comment. If there are major concerns you feel have not been sufficiently addressed, could you please highlight them?

And, if there are major concerns we have addressed, we would appreciate it if you were willing to reconsider your score, in light of these clarifications and improvements.
# Consistency in the unknown-cost setting
> I appreciate the authors' comprehensive response [...] several remaining concerns.

Thank you very much for your comments! **While we do promise to discuss consistency of PBGI-D, given the above reasoning and aforementioned sketch - which amounts to reasonably-standard theory - we are confident we can do it.** Let us address your remaining concerns below.

> [...] unknown cost [...] similar property to the known cost [..] analyzing the consistency. [...] costs are arbitrarily close to zero due to observation noise [...] extreme values only trouble the multi-fidelity [...] what differentiates the assumption of cost in multi-fidelity BO and the paper's assumptions [...]?

The key property of single-fidelity Bayesian optimization is that for practical cost functions, **the infimum of costs of inspecting any point is strictly positive**.
This is assumed implicitly in our consistency sketch from the previous reply: we regret, in light of space, that we had omitted saying this. The specific way this assumption is used is to ensure $\frac{1}{\lambda c(x)}$ approaches $\infty$ uniformly in $x$ as $\lambda \to 0$.

In contrast, **the assumption of a strictly positive minimum cost need not hold in the continuous-fidelity variant of the multi-fidelity setting**. There may be a spectrum of fidelity levels whose costs converge to zero at the low-fidelity end of the spectrum - this is studied by Wu et al. (2020).

You raise a good point about unknown costs: here is the extent to which our proof sketch covers them. **Our consistency sketch requires that the $c(x)$ values being plugged into our algorithm have a strictly positive minimum value.** We believe this should hold, as long as the true costs have a positive minimum and match the smoothness properties of the lognormal cost model's kernel, but other assumptions might work too. For what it's worth, we believe a global lower bound on the cost of an inspection - which need not be tight - is generally known in practice, arising for instance from the minimum amount of time to run an experiment.

Your point about noisy observations of costs possibly complicating this picture is well taken, but **noisy observations - whether of data or of costs - are outside the scope of our work**. Our work shows that building Gittins index machinery that handles observation noise is a promising future direction, but **handling noise properly requires non-trivial technical development on the Gittins index side (see [this official comment's second heading](https://openreview.net/forum?id=Ouc1F0Sfb7&noteId=la5dFZIeR7))**.

# Cost-awareness of UCB and TS
> Second is the experiment; in the uniform cost setting with a finite budget, UCB and TS reduce to their non-asymptotic version, where the  controlling the exploration-exploitation trade-off could be much smaller than the asymptotic version, achieving the exact cost-awareness as is discussed in line 104 to line 109. Though it is limited to the uniform cost setting, such straightforward solutions to make UCB and TS cost-aware should not be omitted in both the discussion and experiments. Otherwise, it could be partially misleading.

We appreciate your suggestion to extend the discussion of the limitations of EI and EIPC to UCB and TS, and we will include this in the next version of our manuscript. However, we have two points of confusion that we hope you can clarify:
1. **Thompson sampling is by definition not a cost-aware algorithm, and includes no tuning parameters (and, in particular, no learning rates) that make it naturally extend to a tunable cost-aware algorithm.** Moreover, (a) we are not aware of any papers proposing cost-aware extensions of Thompson sampling, and (b) we are not sure what you mean by "asymptotic version of Thompson sampling" as this algorithm has no parameters to tune that could be chosen in an asymptotic or non-asymptotic way. As consequence, could you please clarify precisely how you are thinking about making Thompson sampling into a cost-aware algorithm, so that the notions above make sense?
2. On the other hand, since the uniform-cost setting is equivalent to the finite-horizon setting studied in bandits, **UCB can be extended naturally to a uniform-cost-only cost-aware algorithm** by tuning the learning rate appropriately. Using this correspondence, **non-asymptotic tuning (that is, tuning which yields a regret bound valid for any finite T) for controlling explore-exploit tradeoffs is given by Srinivas et al. (2009) - we are already using their higher-performing empirical tuning in our experiments**. While this tuning might not be perfect due to gaps in the analysis of Srinivas et al. (2009), **our tuning of lambda is deliberately set to be imperfect to demonstrate some degree of robustness** and therefore indicating that our improved performance - particularly outside the Bayesian regret setting where we improve significantly on UCB - is not due to superior tuning.
Thanks to the authors for their further response, The responses make sense so me, I appreciate the clarification.
I appreciate the authors' comprehensive response, especially in answering my questions about the scope of the paper, focusing on known cost settings and the consistency of the proposed algorithm. The authors actually promise much beyond the current presentation to be available in future revisions, and I place my trust in most of the points. Yet there are several remaining concerns.

First is the claim that the unknown cost setting would bear similar property to the known cost setting when analyzing the consistency. This is not immediately clear to me, as for an unknown cost, I'm not sure what would happen if the model suggests that specific candidates' costs are arbitrarily close to zero due to observation noise, and the assumption is that cost has to be above 0. It seems necessary to truncate the scope of the model for the cost function with an additional assumption that is not typical in BO. This also resonates with my remaining concern over the problem formulation. The author claims that the extreme values only trouble the multi-fidelity setting, so what differentiates the assumption of cost in multi-fidelity BO and the paper's assumptions on the cost?

Second is the experiment; in the uniform cost setting with a finite budget, UCB and TS reduce to their non-asymptotic version, where the $\beta_t$ controlling the exploration-exploitation trade-off could be much smaller than the asymptotic version, achieving the exact cost-awareness as is discussed in line 104 to line 109. Though it is limited to the uniform cost setting, such straightforward solutions to make UCB and TS cost-aware should not be omitted in both the discussion and experiments. Otherwise, it could be partially misleading.
We sincerely appreciate your thoughtful and encouraging feedback! We are delighted to hear that you find our method novel and appreciate your interest in potential follow-up work! Below, we aim to clarify further the points raised in your review. Thank you once again for your valuable feedback and support.



# Similarities between PBGI and the rarely-used EI
Thanks for bringing up this point. The $\xi$ parameter in the variant of EI you mention is different from but related to the Gittins index. In particular, for the uniform-cost maximization problem, **the Gittins index should be [the value of $\xi$ such that the threshold-adjusted EI equals $\lambda$] - [the current best observed value]**. For the minimization problem which the EI in your reference link is used for, the minus sign should be replaced with a plus sign. 

However, **$\xi$ and $\lambda$ exhibit similarity in monotonicity when controlling the exploration vs exploitation trade-off** -- both larger $\xi$ and larger $\lambda$ imply higher exploitation. This can be illustrated using a toy Pandora's Box example involving a choice between a closed box and an open box with the current best-observed value inside: as $\xi$ increases, you are more likely to take the open box, which is a sign of exploitation. Similarly, as $\lambda$ (representing the cost to open the closed box in this setting) increases, you are also more likely to take the open box. **Note that this similarity is only qualitative, not quantitative!**


# Normalization and Constant Cost
You are correct that our algorithm relies on the output range of the objective function when the costs are not scaled. To clarify, we normalize the outputs not merely to adhere to standard practice, but primarily for two reasons. First, theoretically, for a fixed GP prior, a fixed budget, and fixed costs, the best value of $\lambda$ should be consistent across problems, assuming a well matched prior. Second, in practice, normalization allows us to treat different problems, such as Rosenbrock and Ackely, which may have varied output ranges, as if they are drawn from the same fixed GP prior. This approach enables us to apply the same $\lambda$ value across different problems: normalization makes using such a value at least reasonable. The above reasoning also applies to the uniform-cost setting.
# Automatically Tuning Lambda

Thank you very much for your response! In our response, we had originally included an idea for how to automatically tune $\lambda$ in a setting where we can run Bayesian optimization multiple times, but this got cut due to rebuttal space limitations. We expand on this below.

Our automatic tuning idea below **applies in settings where evaluating the true objective function is the key computational bottleneck** (for example, running a large physics simulation, training a large neural network). In this setting, it is (a) important to choose $\lambda$ well to ensure high-quality acquisitions, and (b) worthwhile to spend some degree of computation on choosing $\lambda$.

The key to our proposal comes from Figure 3 (which is an 8-dimensional Bayesian regret experiment), from which we can make two observations:

* **As one varies $\lambda$, PBGI's regret curve varies in a qualitatively predictable way.** Specifically, large-$\lambda$ regret curves first drop sharply, then flatten out, whereas small-$\lambda$ regret curves drop less-sharply, but eventually reach a better value.
* **Testing a relatively small number of $\lambda$ values is sufficient to find a good choice.** Figure 3 uses a small number of geometrically spread $\lambda$ values, namely $10^{-n}$ for $n \in $ {$2, 3, 4, 5$}.

Motivated by this - and by theoretical considerations given below - we propose the following tuning scheme: every few iterations, **run a Bayesian regret experiment comparing PBGI across a range of geometrically spread $\lambda$ values, then set $\lambda$ to the one with best performance at the desired budget**. For the prior GP in the Bayesian regret experiments, use the current posterior GP from the "real" Bayesian optimization loop, and draw the objective function for the experiment from that same GP. For an expensive-enough true objective function, running such as experiment can be computationally viable, and it outputs a $\lambda$ value that is very likely to be good, if not optimal, for the real experiment.

**This approach is theoretically principled**, in the following sense.
One of the lemmas used in our analysis of Theorem 2 shows that **the optimal $\lambda$-value in Pandora's Box satisfies an optimization problem whose gradient relates the Gittins index policy's expected costs with the budget.** Setting this gradient to zero, we obtain an equation which balances the two terms, which the scheme above directly targets.

Furthermore, **using PBGI-D with initial value set to the tuned $\lambda$-value for the real selections provides an additional layer of safety against getting stuck with a too-large $\lambda$-value**. When PBGI-D decides to decrease $\lambda$, one could use that as a signal that another Bayesian regret experiment to tune $\lambda$ is warrented: this may be more efficient than simply running the Bayesian regret experiments every few iterations.

In summary: **the above idea gives a clean and principled way to automatically tune $\lambda$**. One can also apply a similar Bayesian-regret-based scheme to automatically tune $\beta$, but **our empirical results reveal that performance is not very sensitive to the $\beta$ parameter**. Thank you for bringing this point back to our attention! We will add these ideas to the next manuscript draft.


# Noisy Observations

Let us also expand on what happens in the noisy observation case, to provide **justification for why this should be out of scope of the current work**.

The optimality claim in Pandora's Box arises by comparing one closed box with one open box.
In the case where we have observations with noise, including the ability to repeat observations to reduce the effect of noise, the one-closed-one-open box model now consists of a **Nested Pandora's Box** - a Pandora's Box which contains another Pandora's Box inside of it, repeated recursively.
Modulo certain technical details, we think that one could show using abstract Gittins-index-theoretic machinery that (in the discrete case) this setup also admits an optimal Gittins index policy.

The key technical question becomes: **what is the objective of the convex optimization problem defining the Gittins index policy?** In the Pandora's Box case, this is analytic, given by expected improvement. In the nested analog of Pandora's Box, **we cannot expect an analytic formula, and would need to rely on novel numerical methods yet to be developed** to compute the respective optimization objective function.
We therefore believe that this situation, while - as you say - extremely relevant, important, and interesting, would be **too complex to describe within the 9-page NeurIPS limit and would therefore best be presented in a follow-up paper.**
Thanks to the authors for their effort in producing a nice rebuttal. Having read the other reivewers' reviews, I feel more confident in my my own. The algorithm is novel, addresses an important niche and is well-supported both theoretically and empirically. Moreover, it is carefully presented. 
While there is certainly room for relevant follow-up (i.e. setting $\lambda$, noise treatment), that in itself suggests that the paper can be impactful. Moreover, I am personally curious about its application in a multi-fidelity context.
____________
## Why does the algorithm work well?
Thank you, this is exactly the type of plot I think the paper needs. To me, it explain what the purpose of the algorithm is, and combined with the haystack argument, captures the essence of it nicely. 

On this topic, it would seem like PBGI achieves a very similar trade-off to the rarely used improvement threshold in EI, e.g. https://automl.github.io/SMAC3/main/_modules/smac/acquisition/function/expected_improvement.html#EI (see the xi hyperparameter). Are the authors aware of any similarities between the two?

__Note:__ I do _not_ think this restricts the novelty of the method.

## Normalization and Constant Cost
Thanks for the clarification. I still do not perfectly grasp this, as values in [0, 10] are not exactly conventional, either (rather, standardizing the current set of observations). As such, it does still seem to me like the algorithm is dependent on the output range of the function, and perhaps this is unavoidable in the cost-aware setting.

______
I strongly feel that this paper should be accepted. As such, I will happily vouch for it.
Thank you for the detailed rebuttal and interesting discussions.

I'm glad to see the lengthscales are optimized with MLE. I am positive about the paper, but I still believe finding an automatic way to calibrate $\lambda$ and $\beta$ would strengthen the contribution.

Furthermore, taking noise into account is quite important as many (most) applications of BO do involve a noisy objective function.

I've increased my score to 5.
# Reviewer iB7T - follow up comment regarding posterior dynamics

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

We wanted to start by thanking Reviewer iB7T again for these insightful questions about soundness.

In our view, the most important soundness properties are performance bounds - that is, bounds on simple or cumulative regret. **We view regret bounds as an important direction for follow up work, but we expect it to be a hard enough analysis to be outside the scope of the present paper.**

Nevertheless, the comment inspired us to think about **(a) whether there are weaker soundness properties which we could investigate** in our current submission, such as consistency; and **(b) whether or not the type of example you describe could occur**, with PBGI getting "trapped", and how to mitigate if so. This led to two outcomes:

* **We now have a proof sketch that our PBGI-D algorithm is consistent.** We plan to incorporate this into our next revision - either as a fully fleshed out proof, or as a high-level discussion motivating PBGI-D, or possibly both.
* **We now believe that one might be able to achieve performance comparable to the better between our two algorithms** - namely, that of PBGI with constant $\lambda = 1/10000$, and PBGI-D with initial $\lambda = 1/10$ and $\beta = 1/2$ - by simply using PBGI-D with initial $\lambda = 1/10000$ (and still $\beta = 1/2$). We will evaluate this hypothesis as soon as it is feasible for us to do so comprehensively.

Below, we discuss these in more detail. We note that **the reasoning throughout is similar for known and unknown costs**, so we focus mainly on the known-cost case of primary interest in our paper.

## Achieving the best of both PBGI and PBGI-D

We believe that **for large time horizons, decreasing $\lambda$ as the algorithm proceeds is important**. Otherwise, at time points which occurs sufficiently-long after the Gittins stopping rule triggers, without decreasing $\lambda$ the algorithm might become too-greedy.

The **purpose of the fixed-$\lambda$ PBGI is to do well in the setting where we know we will eventually stop**: this setting is by definition finite-time, so one need not expect good asymptotic behavior without modifications such as decay.

In our experiments, we examined PBGI-D with large initial values of $\lambda$, while we examined PBGI for a broader range of values. From thinking carefully about your comments, **we suspect PBGI-D with small initial values of $\lambda$ may in some cases outperform PBGI with constant $\lambda$**, particularly if the initial value and constant are set equal.
* The intuition here is that, from Figure 3, the regret of PBGI with any constant value of $\lambda$ eventually levels off, causing PBGI-D to later catch up in performance.
* Since, before the first $\lambda$-decrease, PBGI-D and PBGI make the same decisions and achieve the same regret, it might be possiboe **achieve the best of both worlds by mimicking PBGI on short horizons, but removing the eventually-level-off behavior via $\lambda$-decrease** as in PBGI-D. We will run comprehensive experiments to evaluate this possibility for the next manuscript version.

## Consistency of PBGI-D

**We believe that PBGI-D is consistent**. Recall that every time the Gittins stopping rule triggers, the algorithm decreases $\lambda$. This causes it to eventually explore more in a manner similar to other acquisition functions. **We believe this holds regardless of whether the costs are known - our main focus - or they are unknown.**

Our preliminary calculations show that for small $\lambda$, point $x$'s Gittins index is $\approx \mu(x) + \sigma(x) \sqrt{2\log \frac{\sigma(x)}{\lambda c(x)}}$, where $\mu(x)$ and $\sigma(x)$ are the mean and standard deviation of the objective model, and $c(x)$ either the known cost or, if unknown, the expected value of the cost model's mean. This should prevent any open neighborhood of the domain from being ignored by PBGI-D, because **for sufficiently small $\lambda$, unexplored regions where $\sigma(x) \gg 0$ will always have better Gittins index than explored regions where $\sigma(x) \approx 0$, thus implying consistency**.
Even unknown costs do not pose a great obstacle, because as $\lambda \to 0$, the dominant term is $\sigma(x) \sqrt{2\log\frac{1}{\lambda}}$, which is independent of the cost.