Practical Bayesian Algorithm Execution via Posterior Sampling
Authors: Chu Xin Cheng
Raul Astudillo
Thomas Desautels
Yisong Yue
Venue: NeurIPS 2024 poster (2024)
Keywords: Bayesian algorithm execution
Bayesian optimization
posterior sampling
probabilistic numerics
Primary area: probabilistic_methods
TL;DR: We propose a posterior sampling-based algorithm to efficiently estimate a target set of input points defined in terms of a function with expensive evaluations.

Abstract: We consider Bayesian algorithm execution (BAX), a framework for efficiently selecting evaluation points of an expensive function to infer a property of interest encoded as the output of a base algorithm. Since the base algorithm typically requires more evaluations than are feasible, it cannot be directly applied. Instead, BAX methods sequentially select evaluation points using a probabilistic numerical approach. Current BAX methods use expected information gain to guide this selection. However, this approach is computationally intensive.  Observing that, in many tasks, the property of interest corresponds to a target set of points defined by the function, we introduce PS-BAX, a simple, effective, and scalable BAX method based on posterior sampling. PS-BAX is applicable to a wide range of problems, including many optimization variants and level set estimation. Experiments across diverse tasks demonstrate that PS-BAX performs competitively with existing baselines while being significantly faster, simpler to implement, and easily parallelizable, setting a strong baseline for future research.  Additionally, we establish conditions under which PS-BAX is asymptotically convergent, offering new insights into posterior sampling as an algorithm design paradigm.

Practical Bayesian Algorithm Execution via Posterior Sampling
Chu Xin Cheng"
Raul Astudillo"
California Institute of Technology ccheng20caltech.c edu
California Institute of Technology
rastudil@caltech edu
Thomas Desautels
Yisong Yue California Institute of Technology yyueścaltech. edu
Lawrence Livermore National Laboratory desautels2011n1 gov
Abstract
We consider Bayesian algorithm execution (BAX), a framework for efficiently selecting evaluation points of expensive function to infer property of interest encoded as the output of a base algorithm. Since the base algorithm typically requires more evaluations than BAX methods sequentially select evaluation points using a probabilistic numer- ical approach. Current BAX methods use expected information gain to guide this selection. However, this approach is computationally intensive. Observing that, in many tasks, the property of interest corresponds target set of points defined by the function, we introduce PS-BAX, simple, effective, and scalable BAX method based on posterior sampling. PS-BAX is applicable a wide range of problems, including many optimization variants and level set estimation. Hx- periments across diverse tasks demonstrate that PS-BAX performs competitively with existing baselines while being significantly faster, simpler to implement, and easily parallclizable, setting a strong baseline for future research. Additionally, we establish conditions under which PS-BAX is asymptotically convergent, offering new insights into posterior sampling as an algorithm design paradigm.
feasible, it cannot be directly applied. Instead,
Introduction
Many real-world problems can be cast as estimating a property of black-box function with expensive evaluations. Bayesian optimization (BO) [I] has focused on the where the property of interest is the function's global optimum. Similarly. level set estimation [2] deals with the problem of estimating the subset of points above (or below) user-specified threshold.
In many cases, an algorithm to compute the property of interest is available, which we refer to as the base algorithm. However, this algorithm typically requires more evaluations than are feasible in practice and cannot be used directly. Instead, evaluation points must be carefully selected through other means. Similar to BO and level set estimation, the Bayesian algorithm execution (BAX) framework selects evaluation points using two key components: (1) a Bayesian probabilistic model of the function and (2) sequential sampling criterion that leverages this model to choose new points for evaluation
Existing approaches to BAX rely on expected information gain (EIG) as the criterion for selecting which points evaluate However, maximizing the EIG presents significant computational
Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

challenge, particularly in high- dimensional problems or when the property of interest is complex. As a result, heuristic approximations are frequently employed, which can lead to suboptimal performance and limit the applicability of BAX in real-world scenarios.
To address this challenge, we propose PS-BAX, simple yet effective and scalable approach based on posterior sampling. Our approach is built upon the key observation that many real-world BAX tasks aim find a target set. For instance, in BO, the goal is locate the function's global optimum, while in level set estimation, the objective is to find the points whose function value is above a specified threshold. PS-BAX only requires single base algorithm execution each iteration, making it much faster than EIG-based approaches, which require executing the base algorithm multiple times and optimizing over the input space. Despite its simple computation, we show that PS-BAX is competitive with existing baselines while being significantly faster. Additionally, we show that enjoys appealing theoretical guarantees. Specifically, we prove that PS-BAX is asymptotically convergent mild regularity conditions.
Our contributions are summarized follows:
We derive PS-BAX, a posterior sampling-base -aase BAX method applicable to a broad class of BAX problems, unlocking new applications and offering fresh perspective on the scope of posterior sampling algorithms.
We show that PS- PS-BAX is orders of magnitude faster to compute than the EIG-basod approach INFO-BAX (3] while remaining competitive with this and other specialized algorithms.
We prove that PS-BAX is asymptotically convergent under mild regularity conditions.
2
Related Work
Our work falls within the broader field of probabilistic numerics 4 which frames numerical problems, such as optimization or integration, as probabilistic inference tasks. This probabilistic perspective enables uncertainty quantification, which is particularly important settings with limited computational budgets, where budget allocation must be carefully planned, often adaptively. While much of the recent work in probabilistic numerics has focused on (Bayesian) optimization [T), there have also been efforts in other arcas, including integration (Bayesian quadrature) [688) level
set estimation 2 9]. and solving differential equations [T0] IT].
Recently, proposed INFO-BAX, an approach to estimate an arbitrary property of interest that could be computed by known base algorithm. Since the base algorithm requires a potentially large number of function evaluations, it cannot be applied directly. Instead, following the probabilistic numerics paradigm, a Bayesian probabilistic model the function is used to iteratively select new points to evaluate. At each iteration, the next evaluation point is chosen by maximizing the expected information gain (EIG) between the function's value at the point and the property of interest. Similar ElG-based approaches have been employed in statistical design of experiments 12 and BO [15] 17), often yielding excellent performance. However, these methods are computationally demanding due to the look-ahead nature of the EIG computation. Moreover, in most cases, the EIG cannot be computed in closed form and must be approximated via Monte Carlo sampling. As a result, EIG- approaches mainly useful in low-dimensional settings or when function evaluations are highly expensive, limiting their applicability in real-world problems.
In response to the limitations of ElG-based approaches, we explore alternative family of strategies known as posterior sampling or Thompson sampling [88 19 Posterior sampling algorithms have been widely used in BO 22. multi-armed bandits 2 and reinforcement learning (26- 28 .. In such settings, these approaches select a point at each iteration according to the posterior probability of being the optimum. To our knowledge, our work represents the first extension of posterior sampling beyond optimization settings, offering fresh insights into this algorithmic family. While the range of problems our approach can address is narrower than those that ElG-based methods can conceptually tackle, it still encompasses a substantial class. Notably, this includes the problems explored empirically by 3 and follow-up work [29), among others.
Our work aligns with recent efforts to broaden the applicability of BO to complex real-world problems. Many such problems deviate from classical optimization formulations, exhibiting diverse structures such as combinatorial [29], robust (30 3T or multi-level optimization [32). Traditional BO algorithms often fail to naturally accommodate these structures, limiting their practical utility. We

---

Algorithm PS-BAX
Require: p(f) (prior), Do (initial dataset), A (base algorithm), N (number of iterations).
1: for n== =
:11MM. do
2: Sample f.. from p(f 1Dn11)
3: Apply algorithm A on fn to obtain X,, =0A(fn)
4: Choose En E argmax (z) Dn-11 //Choose In E X,, with the highest uncertainty
5: Evaluate yn. - (a,) + en and set D,- = -n-1 ((
6: end for
7: return Estimate of OA(f) based on p(f DN). g/E. run on the final posterior mean
introduce a straightforward algorithm applicable to these diverse settings, providing a robust baseline for future exploration. Furthermore, our approach benefits from recent advances in probabilistic modeling tools 35 paving the way for applying these tools to a broader range of problems.
Bayesian Algorithm Execution via Posterior Sampling
Problem Setting Our work takes place within the Bayesian algorithm execution (BAX) framework introduced by [3]. The goal is to estimate Oa(f), the output of base algorithm A applied to function f + R. We assume that f is expensive to evaluate, which means that employing A directly on f is infeasible (as it would require evaluating f too many times). Instead, select the points at which f is evaluated sequentially, aided by a probabilistic model described below. We specifically focus problems where the property of interest which we term the targer ser. As we shall see later, our framework encompasses a wide range of problems, including BQ level-set estimation, shortest-path finding on graphs, and top-k estimation, with applications to topographic estimatiin and drug discovery.
be encoded by set OA(f) X,
Similar to many probabilistic numerical methods, our algorithm relies on probabilistic model encoded by a prior distribution over f. which we denote by p. Although our framework is more general and can be used with other priors, we assume for concreteness that follows Gaussian process (GP) prior [36]. Let Dn 1 { ys. )== denote the data collected after n - evaluations of f. We assume these evaluations are corrupted with i.i.d. Gaussian noise, i.e. yk f*xx + <g. where 61,-.., fn-1 i.i.d. with common distribution (0,00²) and o² is non-negative scalar. Under these assumptions, the posterior distribution over f given D denoted by p(f 1n-1). , is again GP whose mean and covariance functions can be computed closed form using the classical GP regression equations.
Probabilistic Model
INFO-BAX and its Shortcomings Before introducing our algorithm, we briefly comment on prior work based on the expected information gain (EIG) [3]. Succinetly, the IIFO-BAX approach pro- posed by 3 selects at each iteration the point that maximizes the expected entropy reduction between the function's 's value at the evaluated point and (J'). Evaluating expectation is generally difficult, and one often resorts Monte Carlo sampling. Moreover, computing the EIG specifically requires expensive calculations of conditional posterior distributions and entropy. These computational issues are also present in similar information-theeretic acquisition functions proposed in the classic BO setting. However, for BAX tasks, the computation burden of EIG can be much more pronounced if (Ox()) is large. This occurs, for example, the level set estimation setting, where OA(J) can be comprised of large number of points. We defer more detailed discussion of the computation of the EIG to Appendices and
To overcome the computational limitations of ElG-based approaches, introduce simple strategy based on posterior sampling, which we term PS-BAX. For ease of exposition, we only describe the fully sequential version of our algorithm and defer the batched (parallelized) version to Appendix C Our algorithm is summarized in Algorithm I PS-BAX BAX is comprised two steps, detailed below.
PS-BAX
"To reduce to standard BO, one can define the target set Ox(J) as the points E X that maximize f. i... Oa(f) argmax,ex (often singleton set).
3

---

2.0
1.5
0.5
-0.5
0.2
0.0
Céjedt Function
Thoeshold
Fontedoo Bishtarionn
Sample
Samp ed Srrpet
Fostedor Vertnne
Vext
Figure 1: Depiction of PS-BAX (Algorithm) D for the level-set estimation problem. We plot the objective function (black line), the current available data Dn (black points), the threshold (grey dashed line), the posterior distribution p(ʃ -1 (blue line and light blue region), sample from the posterior fn, p(f 1n (green line), the corresponding sampled target set X, = OA(Fa) (green region) (this the set of inputs where the green line is above the threshold), the variance of p(f Dn-1) (green line, bottom row), and the next point to evaluate selected by PSSBAX xn E X, (input marked by the vertical red line). The key step computing the target set X,, using the sampled function Sn. which generalizes posterior sampling for standard BO.
1. We sample a target set X,, C X according to the posterior probability that X,, = (A( (lines 2-3 in Algorithm [ This can be achieved by drawing sample from the posterior over f. denoted by Fn (line 2), and then setting X,, (f())) (line 3).
2. We select the point in the sampled target set X, with maximal uncertainty or en- tropy: In argmax Hx)(x)[D,, (line 4 in Algorithm I.. For a Gaussian pos- terior, In can be equivalently selected using the maximal posterior standard deviation:
In E argmax xe x, (z(z), where on (x) is the posterior standard deviation of fxx).
Note that the second step is unnecessary in standard BO, since X, is typically singleton.
Depiction for Level Set Estimation Figure I depicts iteration of PS-BAX for the level-set estimation problem, where (f(f) = fi E X F(x) > T}. for user-specified value of r. Line 3 of Algorithm I returns target set X, based on where the sampled function fn (green line in Figure above the threshold 5 (green region Figure [T]. Line of Algorithm [ then chooses the point In E Xx, that has maximal uncertainty (red line in Figure D In the standard BO setting where A is computing the maximizer of J, the target region X,, is simply singleton point where the sampled has highest value (and Line in Algorithm is not necessary).
Discussion We now provide an intuitive explanation of why one might expect PS-BAX to perform well. In the standard BO setting, posterior sampling is known deliver excellent performance 20 37 and enjoys strong theoretical guarantees [18] 20). Like in the BO setting, the intrinsic goal of posterior sampling our setting is to balance exploration and exploitation. In our case, this means selecting points for which, according to our probabilistic model, membership in the target set is still highly uncertain among the likely candidates. To achieve this, the first step PS-BAX selects random set Xn, according to the probability of this set being the target set, in the same vein as traditional posterior sampling in the BO setting (the set likely candidates). Unlike in BO, however, the target set is, in principle, comprised of several points, and thus, must come up with criterion to choose one. To overcome this, the second step simply selects the point with the highest uncertainty among points in X,,, which is standard strategy in the active learning literature 38
Computational Efficiency PS-BAX requires running A only once on single sample f. con- tributing to its practicality and scalability. Furthermore, similar to posterior sampling in the standard

---

BO setting, PS-BAX avoids the need to maximize an acquisition function over X, a process that computationally expensive because it involves calculating the expected value of quantities like information gain. As demonstrated in our experiments, this makes PS-BAX significantly faster than INFO-BAX 3 particularly in problems where either Oa(f) or X are large.
Convergence of PS-BAX A natural question is under which conditions is PS-BAX able to find the target set given enough evaluations. We address this question below. Before stating our results, we introduce a definition related to the characterization of problems where PS-BAX converges.
Definition 1. A target set estimated by an algorithm A is said be cumplement-indeeeddeer if. for any pair of functions f. f X + IR, it holds that Of()) = Oa(f') whenever there exists a set S such that Oa(f) ('A( C S and f(x) - [x) for all x E S.
Many target sets of interest, such as a function's optimum or level set, are complemen--indepedden Indeed, the value of f at points that are not the optimum or that do not lie in the level of interest do not influence these properties. Theorem I concentration, provided the target set of interest is complemenn-nndeeeddene
beloo shows that PS-BAX enjoys Bayesian posterior Intuitively, this result means that if f is drawn from the prior used by our algorithm (i.e., the prior is well-specifiedd) then, with probability one, the posterior will concentrate around the true target set. Corollary [ gives an asymptotically consistent estimator of the target set. Finally, we also show there are problems where the target set is not complement-nndeeendenn and PS-BAX is not asymptotically consistent in Theoremp 2 The proofs of these results can be found in Appendix [D]
Theorem 1. Suppose that X is finite and that the larget set estimated by A complemenn-nndependentt If the sequence of points (rn ] is chosen according to the PS-BAX algorithm, then, for each X C X. limn P.. (n((A()) = =X I[Ox(J) = X} almost surely for J drawn from the prior. Corollary 1. Suppose the assumptions of Theorem 7 hoold, and let Tn E PaaemaxxxPP(OAA.
X). Then, for f drawn from the prior, we have Tn =OA xf()) (ffffffr for all sufficiently large n almost surely.
Theorem There exists a problem instance (i.e., X. a Bayesian prior over f. and A) such that if the sequence of points {æn ===1 is chosen according to the PS-BAX algorithm, then there is a set X C X such that lim P, (O(f) X) 1/2 almost surely for f drawn from the prior.
4 Numerical Experiments
We evaluate the performance of PS-BAX on eight problems across four problem classes. For each problem class, specify the base algorithm used. We compare the performance of PS-BAX against INFO-BAX (3] and uniform random sampling over X (Random). When available, we also include an algorithm from the literature specifically designed for the problem class. Additional implementation details of the algorithms are described in Appendix E In all experiments, an initial dataset is generated by sampling 2(d + 1) inputs uniformly random from X, where dl denotes the dimensionality of X. Following this initialization, each algorithm sequentially selects additional batches of points. Unless stated otherwise, the batch size is set to q 1. The performance of each algorithm determined by applying A on An. the posterior mean of f given D,, and subsequently computing suitable performance metric on (H,.). Each experiment was replicated 30 times, with plots showing mean performance plus and minus 1.96 standard errors. Code to reproduce our experiments is available at https: gi thub. cwwm Aaw.Astudilll00 100////AO00//P
Summary of Findings Overall, we find that PS- WS-BAX is always competitive with and sometimes significantly outperforms INFO-BAX across all of our experiments. Additionally, as shown in Table T PS-BAX can be orders of magnitude faster in wall-clock runtime. PS-BAX outperforms INFO-BAX on five out of eight problems, offering particularly large improvements in the Local Optimization and DiscoBAX AX problem classes. Moreover, in the Local Optimization and Level Set Estimation problems, PS- PS-BAX also outperforms algorithms from the literature specifically designed for such problem classes. On the simpler problems, such as those in the Top-k problem class, PS-BAX is competitive with INFO-BAX while still being significantly faster.
4.1 Local Optimization
We explore the performance of our algorithm in the local optimization setting, where a classic optimization algorithm, i.c., algorithm designed for optimization problems where f (and potentially
5

---

Problem
PS-BAX Runtime (s)
INFO-BAX Runtime (s)
Local Optimization: Hartmann (6D)
0.37
7.64
Local Optimization: Ackley (10D)
3,36
29.31
Level Set Estimation: Himmelblau
0.57
14.97
Level Set Estimation: Volcano
0,49
289.91
Top-k: Rosenbrock (k: - 6)
0.92
18.31
Top-k: GB1 (k 10)
145.23
865.85
DiscoBAX: Tau Protein Assay
3.78
113.20
DiscoBAX:
Assay
3.95
97.03
Table 1: Average runtimes per iteration of PS-BAX and INFO-BAX across test problems. In all
of them, PS-BAX is between one and three orders of magnitude faster than INFO-BAX. We also note that the runtimes for both algorithms significantly longer the Top-10 GB1 problem due the use of a deep kernel GP model.
-4
-8
Random
INFO-BAX
PS-BAX (Ouns)
Random
INFO-BAX
PS-BAX (Ours)
Figure 2: Results for Local Optimization, showing the log10 inference regret achieved by the compared algorithms (lower values indicate better performance). The left and right panels present results for the Hartmann-6D and Ackley-101 1OD functions, respectively. On Hartmann-6D, PS-BAX and perform comparably, both outperforming INFO-BAX. On Ackley-1OD, PS-BAX achieves significantly better results than the rest of the algorithms.
its gradients) can evaluated large number of points. Examples such algorithms include evolutionary algorithms (39), trust-region methods [40], and many gradient-based optimization algorithms [4 42). This setting reduces to the classical BO setting if can recover the global optimum of f. In such case, the INFO-BAX reduces to the classical predictive entropy search acquisition function [16) when computed exactly and to the joint entropy search acquisition function 43 under the approximation proposed by 3 that reduces to the classical posterior sampling strategy used in BO (20). However, due to its practical relevance and the lack of empirical comparison between joint entropy search and posterior sampling, we still include this setting in our experiments. We also use this setting to illustrate nuances that arise when choosing a base algorithm.
in experiments. PS-BAX, in turn,
In our experiments, we use a pradient-based optimization method as a base algorithm instead of an evolutionary algorithm as pursued by [ Gradient-based methods typically exhibit faster convergence than their gradient-free counterparts. However, they are often infcasible gradients cannot be obtained analytically and instead are obtained, e.g., via finite differences. Since in most applications, analytic gradients are unavailable, directly applying such methods on is infeasible. However, PS-BAX and INFO-BAR -AX can make use of gradient-based methods thanks to the availability of gradients of most probabilistic models used in practice, including GPs.
We consider the Hartmann and Ackley functions, with input dimensions of 6 and 10, respectively. as test functions. Both functions have many local minima and are standard test functions in BO literature. For Ackley, we set the batch size to = 2. As a performance metric, we report the log inference regret, given by lo" f(;,,,, )), where 4 obtained by applying A on Mn. The results of these experiments are depicted in Figure 2 As baseline, we also include the

---

0.9
0.9
0.8
0.7
0.6
0.6
0.5
0.4
Itertion
llratton
Random
18E
INFO-BAX
PS-BAX (Ouns)
Rendom
USE
INFO-BAX
PS-BAX (Oun)
Figure 3: Results for Level Set Estimation, showing the Fl score (where higher is better). The left and right panels present results for the Himmelblau test function and the topographic mapping problem, respectively. In the former problem, all algorithms perform similarly, while in the latter, PS-BAX outperforms all baselines.
expected improvement (EI), arguably the most popular BO acquisition function. On Hartmann -.rt PS-BAX performs on pair with EI, and both algorithms outperform INFO-BAX. Notably, PS-BAX outperforms both INFO-BAX and El on Ackley-10D.
4.2 Level Set Estimation
Level set estimation involves finding all points in X with f(x) r. for user-specified threshold value r. This task arises in applications such as environmental monitoring, where a mobile sensing device detects regions with dangerous pollution levels [2), and topographic mapping, where the goal to infer the portion of a geographic area above a specified altitude using limited measurements (4)) For both problems considered in work, X is finite; therefore, the base algorithm A simply ranks all objective values and returns the points where the function value exceeds the threshold.
We evaluate the algorithms on a synthetic problem (the 2-dimensional Himmelblau function) and real-world topographic dataset, consisting of 87 x 61 height measurements from a large geographic area around Auckland's Maunga Whau volcano 4 The threshold is set to the 0.55 quantile of all function values the domain for both problems. problem over 100 iterations for both INFO-BAX and PS-B PS-BAX is shown in Figure 4
illustration of single runs on the topographic
The performance metric used is the Fl score, defined by
2TP
F1 2TP + FP FN
where FP, and FN represent true positives, false positives, and false negatives, respectively. The results of this experiment are shown in Figure B As additional baseline specifically designed for level set estimation, we include the popular LSE algorithm proposed by (2]. PS-BAX demonstrates strong performance, outperforming all benchmarks in the topographic mapping problem.
4.3 Top-k Estimation
We consider the top-k estimation setting, where a finite (but potentially large) set, and the goal is to identify the k points with the largest values of f(x). In this scenario, the base algorithm evaluates all points X and returns the l best points. Following 3 we use as performance metric the Jaccard distance between the estimated output S, = a and the ground truth optimal set S*, defined by
S, S*
d(Sn, =1
2
S., U
We consider two test problems. The first problem uses 3- d-dimensional Rosenbrock function, standard benchmark in the optimization literature. The input space is obtained by taking uniform grid of 1,000 points over 2]3. For this problem set 4.
The second problem is a real-world top-k (k 10) selection task in protein design, where the goal is to maximize stability fitness predictions for the Guanine nuclcotide-binde protein GBI,
7

---

10
08
08
02-0
02-
0/2
Sampied Points
Sampled Points
Figure Depiction of the INFO-BAX (left) and PS-BAX (right) algorithms on the topographic level set estimation problem described in Section 4.2 Each figure shows the ground truth super-level set (small black dots), the points evaluated after 100 iterations (green and blue dots for INFO-BAX and PS-BAX. respectively), and the estimated level set from the final posterior mean (red dots). PS-BAX provides an accurate estimate the level set, whereas INFO-BAX misses a significant portion.
given different sequence mutations in target region of 4 residues [45 GB1 is well-studied by biologists, and its domain is known to be highly rugged, dominated by "dead" variants with very low fitness scores [46] There are 20 possible combinations, with 20 amino acids and 4 positions, and we represent the input space as one-hot vectors in an 80-dimensional space. To avoid excessive runtimes, randomly sample 10,000 points from the original dataset. Due the high dimensionality, vast input space, and sparse fitness landscape, this dataset poses significant challenges for standard GP models. Therefore, use deep kernel GP [4 our probabilistic model. Given the dataset's size, we perform batched evaluations with batch size of 4 for both PS-BAX and INFO-BAX.
The results of these experiments shown in Figure In both problems, PS-BAX performs comparably to INFO-BAX, with both algorithms significantly outperforming Random.
1.0
0.
0.4
20
00
80
100
0
20
40
80
100
Random
ING--AAX
PS-RAX (Duns)
Random
I-FO-AXX
PS-BAX (Duns)
Figure 5: Results for Top-k Estimation, showing the Jaccard distance (where lower is better). The left panel presents results for the 3-dimensional Rosenbrock test function with 4, while the right panel shows results for the real-world protein design GB1 dataset with & = 10. In both problems, PS-BAX performs similarly INFO-BAX.
4.4 DiscoBAX: Drug Discovery Application
As final application, we consider the DiscoBAX problem setting from 29 in the context of drug discovery, where the task is to identify set of optimal genomic interventions determine suitable drug targets. Formally, let X represent pool of genetic interventions, and for each X, let f(x)

---

denote an in vitro phenotype measurement correlated with the effectiveness of genetic intervention The effectiveness of the intervention assumed to be f()) + n7(x,, where 7(x)) captures noise and other exogenous factors not reflected in the in vitro measurement. Following the setup in [29], we simulate y using GP with mean 0 and an RBF covariance function. The goal is to identify a small set of genomic interventions in X that maximize high expected change the target phenotype and high diversity to maximize success in subsequent stages of drug development. This is formalized in [29] the following optimization problem:
objective function balancing two characteristics:
max
Byy
max ((x) + n(x)) #ES
SCX|S8|
where & is the desired size of the intervention set. This problem aims to find set of interventions S such that the rest-performing intervention in S has the highest expected effectiveness (over 7i).
Solving Equation 3 exactly is challenging due its combinatorial nature, even if could evaluate many times, but computationally efficient approximation is possible by leveraging the submodularity
of the objective function. For more details on the base algorithm, we refer the reader to [2]]
Following [29] we use the tau protein assay 48 and interferon-gamma assay [49] datasets from
the Achilles project [50]. Originally, the gene embeddings in this dataset are represented 808- dimensional vectors, and Bayesian MLP is used as the probabilistic model instead of GP. To reduce dimensionality, we preprocess the dataset using Principal Component Analysis (PCA) and then fit GP to the diver-dimesiional representation. Additionally, we truncate the dataset to the 5000 genes with the highest intervention values to ensure computational feasibility in our experiments. The results of these experiments are shown in Figure 6 PS-BAX significantly outperforms INFO-BAX, whose performance only marginally better than that of Random.
5.6
0.76
50
4.5
0.65
40
0.60
3.
90
0.50
26
0.6
60
Beratio
beration
(Duns)
(Ouns)
Figure 6: Results for DiscoBAX [29] showing the regret between the solution found by applying greedy submodular optimization algorithm to the objective in Equation B and the solution obtained from applying the same algorithm over the posterior mean instead of the true function. Both problems are based on the Achilles dataset (50), with the left panel presenting results for the tau protein assay 48 and the right panel showing results for the interferon-gauee gamma assay. In both cases, PS PS-BAX significantly outperforms INFO-BAX, which performs only marginally better than Random.
5
Conclusion
Many real-world problems involve estimating the output base algorithm applied to a black-box function with costly evaluations. While the INFO-BAX algorithm proposed by 3 offers a solution, it faces practical limitations. In response, we introduced PS- PS-BAX, a novel posterior sampling strategy built upon the observation that, in many cases, the algorithm's 's output can be characterized as target set of input points. Our experiments demonstrate that PS-BAX is not only competitive with previous approaches but also significantly faster to compute. Moreover, established conditions under which PS-BAX is asymptotically convergent.
Looking ahead, our approach provides pathway to extend the success of Bayesian optimization to a broader range of problems, potentially unlocking new and impactful applications. Additionally, PS-BAX serves as robust baseline for future research aimed at developing tailored strategies for specific domains. Furthermore, our findings offer new perspectives on posterior sampling algorithms and their application scope, suggesting several promising avenues for future exploration in this area.

---

Acknowledgments and Disclosure of Funding
This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-ACS2-07NA22334. LLNI-CONN-864204, The GUIDE program executed by the Joint Program Executive Office for Chemical, Biological, Radiological and Nuclear Defense's s (JPEO-CBRND) Joint Project Lead for CBRND Enabling Biotechnologies (JPL CBRND EB) on behalf of the Department of Defense's 's Chemical and Biological Defense Program. This effort was in collaboration with the Defense Health Agency (DHA) COVID funding initiative. The views expressed this paper reflect the views of the authors and do not necessarily reflect the position of the Department of the Army, Department of Defense, nor the United States Government. References to non-federal entities do not constitute nor imply Department of Defense or Army endorsement of any company organization.
References
[1] Peter Frazier. A tutorial on Bayesian optimization. arXiv preprint arXiv: 022100 2018.
[2] Alkis Gotovos, Nathalie Casati, Gregory Hitz, and Andreas Krause. Active learning for level set estimation. In Proceedings of the Twenty-Thin Third International Joint Conference on Artificial Intelligence, pages
2013.
[3] Willie Neiswanger, Ke Alexander Wang, and Stefano Ermon. Bayesian algorithm execution: Estimating computable properties of black-box functions using mutual information. In Proceed- ings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8005-8015. PMLR, 2021.
[4] Philipp Hennig, Michael A Osborne, and Hans P Kersting. Probabilistic Numerics: Computation as Machine Learning. Cambridge University Press, 2022.
Numeriiss
[5] Roman Garnett. Bayesian optimization. Cambridge University Press, 2023.
[6] Anthony O'Hagan. Bayes-Hermite quadrature. Journal of Statistical Planning and Inference, 29(3):245-285 2600, 1991.
[7] Xiaoyue Xi, Saancois-Xavics Briol, and Mark Girolami. Bayesian quadrature for multiple related integrals. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5373-5382. PMLR, 2018.
[8] Masaki Adachi, Satoshi Hayakawa, Saad Hamid, Martin Jørgensen, Harald Oberhauser, and Micheal A Osborne. SOBER: Highly parallel Bayesian optimization and Bayesian quadrature over discrete and mixed spaces. arXiv preprint arXiv:2301. 1832, 2023.
[9] Xiong Lyu, Mickaël Binois, and Michael Ludkovski. Evaluating Gaussian process metamodels and sequential designs for noisy level set estimation. Statistics and Computing, 31 31))):33, 2021.
[10] Philipp Hennig and Søren Hauberg. Probabilistic solutions differential equations and their application to Riemannian statistics. In Proceedings of the Seventeenth International Confer- ence on Artificial Intelligence and Statistics, volume 33 of Proceedings of Machine Learning Research, pages 347-355. PMLR, 2014.
[11] Nicholas Krämer, Jonathan Schmidt, and Philipp Hennig. Probabilistic numerical method of lines for time- dmeedeeend partial differential equations. In Proceedings of The 25th International Conference on Artificial Intelligence and Statisties, volume 151 of Proceedings of Machine Learning Research, pages 625-639. PMLR, 2022.
[12] D. V. Lindley, On measure of the information provided by an experiment. The Annals of Mathematical Statistics, 27(4))986 1005, 1956.
[13] Toby J Mitchell. An algorithm for the construction of "D-optimal" experimental designs. Technometrics, 42(1):48 54, 2000.
[14] Thomas J Santner, Brian Williams, and William Notz. The Design and Analysis of Computer Experiments. Springer, 2003.
10

---

[15] Philipp Hennig and Christian J Schuler. Entropy search for information-efficien global opti- mization. Journal of Machine Learning Research, 13(6), 2012.
[16] José Miguel Hernández-Lobate Matthew W Hoffman, and Zoubin Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Advances Neural Information Processing Systems, volume 27, pages 918-926 Curran Associates, Inc., 2014.
[17] Zi Wang and Stefanic Jegelka. Max-value entropy search for efficient Bayesian optimization. In P Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3627-3635. PMLR, 2017.
[18] Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-1243, 2014.
[19] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on Thompson sampling. Foundations and Trends@ in Machine Learning, 1 11(1):1-96, 2018.
[20] Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabas Poczos. Par- allelised bayesian optimisation via thompson sampling. In Proceedings of the Twenty-Firss International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 133-142, PMLR, 2018.
[21] Zhongxiang Dai, Bryan Kian Hsiang Low. and Patrick Jaillet. Federated Bayesian optimization via Thompson sampling. In Advances in Neural Information Processing Systems, volume 33, pages 9687-9699. Curran Associates, Inc., 2020.
[22] Bahador Rashidi, Kerrick Johnstonbaugh, and Chao Gao. Cylindrical Thompson sampling for high-dimensional Bayesian optimization. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 3502-354 -3100. PMLR, 2024.
[23] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 127-135. PMLR, 2013.
[24] Shi Dong, Tengyu Ma, and Benjamin Van Roy. On the performance of Thompson sampling on logistic bandits. Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1158-1160. PMLR, 2019.
[25] Yueyang Liu, Benjamin Van Roy, and Kuang Xu. Nonstationary bandit learning via predictive sampling. In Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 6215-62444 PMLR, 2023.
[26] Ian Osband, Daniel Russo, and Benjamin Van Roy. (More) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[27] Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2701-2710. PMLR, 2017.
[28] Remo Sasso, Michelangelo Conserva, and Paulo Rauber. Posterior sampling for deep rein- forcement learning. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 30042-30061. PMLR, 2023.
[29] Clare Lyle, Arash Mehrjou, Pascal Notin, Andrew Jesson, Stefan Bauer, Yarin Gal, and Patrick Schwab. DiscoBAX: Discovery of optimal intervention sets in genomic experiment design. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 23170-23189, PMLR, 2023.
11

---

[30] Iija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with Gaussian processes. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[31] Sait Cakmak, Raul Astudillo Marban, Peter Frazier, and Enlu Zhou. Bayesian optimization of risk measures. Advances in Neurul Information Processing Systems, volume 33, pages 20130-20141. Curran Associates, Inc., 2020.
[32] Vedat Dogan and Steven Prestwich.
Bilevel optimization by conditional Bayesian optimization. In Machine Learning, Optimization, and Data Science, pages 243-258. Springer, 2024.
[33] Maximilian Balandat, Brian Karrer, Daniel Jiang. Samuel Daulton, Ben Letham, Andrew G Wilson, and Eytan Bakshy. BoTorrch A framework for efficient Monte-Carlo Bayesian optimiza- tion. In Advances in Neural Information Processing Systems, volume 33, pages 21524-21538. Curran Associates, Inc., 2020.
[34] Geoff Pleiss, Martin Jankowiak, David Eriksson, Anil Damle, and Jacob Gardner. Fast matrix square roots with applications to Gaussian processes and Bayesian optimization. In Advances in Neural Information Processing Systems, volume 33, pages 22268-22281 Curran Associates, Inc., 2020.
[35] James T. Wilson, Viacheslav Borovitskiy, Alexander Terenin, Peter Mostowsky, and Mare Peter Deisenroth. Pathwise conditioning of Gaussian processes. Journal of Machine Learning Research, 22(105): 2021.
[36] Carl Edward Rasmussen and Christopher K I Williams. Gaussian Processes for Machine Learning. MIT Press, 2006.
[37] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[38] Christoffer Riis, Francisco Antunes, Frederik Hüttel, Carlos Lima Azevedo, and Francisco Pereira. Bayesian active learning with fully Bayesian Gaussian processes. In Advances in Neural Information Processing Systems, volume 35, pages 12141-12153, Curran Associates, Inc., 2022.
[39] Thomas Bäck. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolu- tionary Programming, Genetic Algorithms. Oxford University Press, 1996.
[40] Andrew R Conn, Nicholas IM Gould, and Philippe I. Toint. Trust Region Methods. SIAM, 2000.
[41] Richard H Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu, A limited memory algorithm for bound constrained optimization. SIAM Journal scientific computing, 16(5):1190-120)) 1995.
[42] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[43] Carl Hvarfner, Frank Hutter, and Luigi Nardi. Joint entropy search for maximally-informet Bayesian optimization. In Advances in Neural Information Processing Systems, volume 35, pages 11494-11506. Curran Associates, Inc., 2022.
[44] Andrea Zanette, Junzi Zhang, and Mykel J. Kochenderfer. Robust super-level set estimation using Gaussian processes. In Machine Learning and Knowledge Discovery in Databases, pages 276-291. Springer, 2019.
[45] Nicholas C Wu, Lei Dai, C Anders Olson, James Lloyd-Smith, and Ren Sun. Adaptation in protein fitness landscapes is facilitated by indirect paths. eliffe, 5, 2016.
[46] Bruce J. Wittmann, Yisong Yue, and Frances H. Arnold. Informed training set design enables efficient machine learning-assistn directed protein evolution. Cell Systems, 12(11):1026- 1045.e7, 2021.
12

---

[47] Andrew Gordon Wilson, Zhiting Hu, Ruslan Salakhutdinov, and Eric P. Xing. Deep kernel learning. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 370-378. PMIR, 2016.
[48] Carlos G Sanchez, Christopher M Acker, Audrey Gray, Malini Varadarajan, Cheng Song, Nadire Cochran, Steven Paula, Alicia Lindeman, Shaojian An, Gregory McAllister, al. Genome-wide CRISPR screen identifies protein pathways modulating tau protein levels in Communications Biology, 4(1):736, 2021.
neurons.
[49] Ralf Schmidt, Zachary Steinhart, Madeline Layeghi, Jacob W. Freimer, Raymund Bueno, Vinh Q. Nguyen, Franziska Blaeschke, Chun Jimmie Ye, and Alexander Marson. CRISPR activation and interference screens decode stimulation responses in primary human T cells. Science, 375(6580), 2022.
[50] Joshua M. Dempster, Jordan Rossen, Mariya Kazachkova, Joshua Pan, Guillaume Kugener, David E. Root, and Aviad Tsherniak. Extracting biological insights from the project achilles genome-scale crispr screens cancer cell lines. bioRxiv, 2019.
[51] Julien Bect, François Bachoc, and David Ginsbourger. A supermartingale approach to Gaussian process based sequential design experiments. Bernoulli, 25(4A):2883-22) 2019.
[52] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
A Computation of the Expected Information Gain
Let E and H denote the expectation and (differential) entropy operators, respectively. At each iteration n, the expected information gain between the (f()) and new observation of f at æ, denoted by Yo, can be written as
EIG, (z) H Mu D, - Hy, OP.)) D,).
(4)
Under the probabilistic model established above, the conditional distribution of y/ given D, is Gaussian, allowing the analytical computation of H(y. D,). However, in most cases, H
Dn, (S) cannot be computed analytically. In particular, this true our setting, where (s) is a subset of X.
To address this challenge, introduced an approximation where Oa(f) is replaced by a of pairs fz=)) for inputs x' evaluated when A is applied on f. When Ox(f) is a subset of X, a natural choice is to take all inputs x' (f). This coincides with the approximation used by 3 in the optimization and top-k estimation settings. The corresponding approximation of EIG,, denoted by EIG,, is then given by
EIG,, (x) = H D2] - E Vu D., ((x', f(x))(()))))))))) : Oa(f)l D.).
(5)
Dn, ((a', f(x))) : r' (x(f)) can be The advantage of this approximation is that, again, yy computed analytically under Gaussian posterior.
The expectation [y Dn. (a', f(x')) I' (A(H) D.l still requires to be approximated
via Monte Carlo sampling. Concretely, this can be achieved by drawing L samples from the posterior over f given D,,, denoted by fu,1.... fn.L, and setting
1 L Hly Dn. ((x))(x²))) of OA(FOH..
EIG v H(ve
Da]
(6)
I 1=1
This is the approximation of FTG., that we use in our experiments Section 4 i.e., at each iteration, set Fy to be point that maximizes the expression in Equation
13

---

B Computational Complexity of PS-BAX and INFO-BAX
Given a Gaussian process posterior, we analyze the computational complexity of selecting the next evaluation point for both PS-BAX and INFO-BAX Our analysis excludes the cost of generating sample from the posterior. which is fixed and depends only on the number of Fourier features used. We also assume that the cost of evaluating such a sample at any given point 1, as the cost of evaluating the posterior mean and covariance. Additionally, we assume that the function domain X is discrete with [X| = N, the algorithm output has a fixed cardinality [f)( M, the number of execution paths to approximate the posterior entropy is L, and running the algorithm any input function requires P evaluations. As we show next, the computational cost of INFO-BAX can be significantly higher than that of PS-BAX when N, M, or L is large.
For PS-BAX, the complexity is O M), reflecting the cost of running the algorithm once on single function sample and maximizing the posterior variance over the sampled target set. For INFO-BAX, the complexity ((P + MM + N M²) L). For each function sample, we need to execute the algorithm (P), condition on M new points to compute the conditional entropy (M²), and evaluate the posterior variance of the fantasized model on N points (N M)). This process is repeated for L function samples.
C Batch Extensions of PS-BAX and INFO-BAX
In this section, we discuss extensions of the PS-BAX and INFO-BA -AX algorithms the batch setting, where at each iteration, we generate 9 new points for evaluation, denoted by In.1. Fnn.g These extensions are inspired by batch versions of the posterior sampling algorithm (20] and the joint entropy search acquisition function 43 from BO. Figure 7 illlustrates the performance of PS- under various batch sizes in two of our test problems.
Batch PS-BAX We extend PS-BAX to the batch setting, following the approach proposed by (20]. For a batch size of g, we draw & independent samples from the posterior on f. denoted by fi,..., Sq. and define the set X, U (ffr..). We then select the points ... FFn.g E X,, iteratively by choosing the point X, with the highest posterior entropy, conditioned on the previously selected points, as follows:
nn argmax & x,,,, H(f(x) Dr,):
Fn.g argmax H[f(z) Dr, U ".n,
Batch INFO-BAX INFO-BAX can be naturally extended to the batch setting by considering the EIG over batch of points. However, directly optimizing the EIG in this scenario involves optimizing over X9, which is usually computationally prohibitive. address this, we use a greedy optimization approach. Specifically, we select In. Tn.q iteratively by maximizing the EIG conditioned on the previously selected points, as follows:
In,1 argmax, FE
H [
Dx) - E[H yy
Dn, Oa()i Dz).
In.9 argmax EE H
Dn U (In.1..... En.
E Vu D, U {In,1,.... Zng- (A()] D, U "er.,:...,,,.--1
D Proofs of Theorems 1 and 2
We begin by introducing the following notation. Let F,, denote the o-algebra generated by D, and let Fox denote the minimal rallebra generated by the sequence [F We denote the conditional probability measures induced by F, and Foo P,, and Poc. respectively.
14

---

03
20
40
60
80
100
20
40
103
Iteration
Beration
INFO-BAX
INFC-BAX
INFO-RAX (q
INFO-RAX
INFORIXX
INFO-BAX 14 (q 44)
(q 1)
FS-BAX (q
(Q)1)
(q- 23
Figure Performance of PS-BAX and INFO-BAX under batch sizes q 1,2, on the local optimization Ackley-10D 10D problem (left) and the DiscoBAX ceerferon-gammen essay problem (right).
D.1 Proof of Theorem
Before proving Theorem 1, we establish auxiliary lemma. Both Lemma [ and Theorem assume the prior distribution and likelihood discussed in Section 3 In particular, this implies that for each X, the posterior distribution of f() given Fr, is Gaussian, with mean and standard deviation denoted by (x) and o,(x), respectively.
Lemma 1. Suppose that % is finite, and let Soo = =x 3X X s.t. IEX P X) > 0}. Then, both Soc and the image of f over this set are Foe-measurable
Proof. Clearly, the set Soe is Foc measurable. Thus, it suffices to show that for each x E Soe, f(x) F -measurable.
Let & E S.c. By definition, there exists subset X C X such that P (=x( standard martingale argument shows that nim, P (f)) X) = X) almost surely. Consequently. there exists > 0 such that (O,() X) > c for all sufficiently large n, implying that the event Xn, X occurs infinitely often.
Moreover,
is not hard to see that on (x) + as n + oo if æ is selected infinitely often. Furthermore, since 2n argmax nn (x'), X is finite, and X, = X occurs infinitely often, it follows that (xx))) + 0 as - co for each x' X, and in particular for By Proposition 2.9 in [51] it follows that (t, + f(x). Since (x) is Foo measurabbe for each n, it follows that f(x) Fx -eeasurrbbl for each E Soo.
Theorem Suppose that % is finite and that the target set estimated by i complement-indeeeeeeee If the sequence of points { {xn, 1:00 is chosen according to the PS PS-BAX algorithm,, then for each X C X,
lim (OA(f()) X) 1(0 X} almost surely for drawn from the prior.
Proof. Recall that lim P. (O to show that P Px. (Oa()) x) = 1(0A()= X) almost surely.
almost surely. Thus, remains
Let Soo be defined as in Lemma [ Since X finite, by the definition of S it follows that (O)(O c Sx)) 1. Moreover, by the law of iterated expectation, it also holds that P(OA(f) 1x)=
Since Oa(f) is Oa(f) Sx. By Lemma [ know that both So and the image of over this set are Foo- measurable. Therefore, for any fixed C X. we have (f) = X} n (f) C S. } E Foc. and hence, (J)) X, OA)) Sx)) (f) X)1
is fully determined by the values of f over Sox whenever
Sxx.
Finally, since (() c Sxx) (OAl) c Sxx) 1, we conclude that P P (OA(f) = X) 1[Ox(f) = X} almost surely.
O
15

---

D.2 Proof of Theorem 2
Theorem There exists a problem instance (i.e,, a Bayesian prior over f. and A) such that if the sequence of points {en ) n=1 is chosen according to the PS-BAX algorithm, then there is a set X C X such that lim, -00 P, (O) = X) = 1/2 almost surely for f drawn from the prior.
Proof. Let 0, 1}. and consider a GP prior over f such that f(-1)= and f(0) is a standard normal random variable. Define the algorithm A such that - f(0) and (a(s) {1} otherwise. Clearly, the target set defined by is not complemenntindeeeeddennt Moreover, under the PS-BAX algorithm, Iy is always either -1 or 1. Since the values of / at these
points are known, the posterior distribution over f any iteration remains equal the prior. Therefore, it follows that P, P,, (OA(f) = {-13) = (O = {1}) 1/2 for all n.
E Implementation Details
All our algorithms are implemented using BoTorch 33 SingleTaskGP class with its default settings for all GP models, except in the top-k GB1 problem, where we employ a deep kernel GP. To our GP models, we maximize the marginal log-likelihood. Approximate samples from the posterior f for both PS-BAX and INFO-BAX generated using 1000 random Fourier features [52]. Our implementations of PS-BAX and INFO-BAX support automatic gradient computation, enabling continuous optimization when X is continuous. For INFO-BAX, we use = 30 Monte Carlo samples to estimate the EIG across all problems.
Specifically, we use BoTorch's
NeurIPS paper checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes)
Justification: See Abstract and Sections and 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
See the discussion about the limitations of our theoretical result in Section 4.3.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well vell-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
16

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
See Section 4.3 and Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: thorough discussion of the details of our empirical evaluation can be found in Section and Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same datasct, provide access to the model. In general. releasing code and data is often
17

---

one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the code and data necessary to reproduce our experiments as a part of the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
ptblice/guides/CodeSuuubuu sor.eedeoabmmssssooooooooooye for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ praips.cc/uullcc/ee gwwiiii//gguieeeeeeeee http://gggudde/ooSSuuubiiiiiii wwwpbbmissiiooooooooiooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: These details are discussed in Section 5.
Guidelines:
18

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our performance plots include error bars reporting 11.9 standard errors across 30 trials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the average runtime for each algorithm across every test problem. Unfortunately, the exact details of the computing resources used not available.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httphh/tpppp..e.ep......caalahtp
Answer: [Yes]
19

---

We read this code and verified that our research was performed under such lineaments.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
20

---

12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsswipppsseeeeeeeeeeeee thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The dataset used in our simulated exoskeleton design is discussed in Section 5.3.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
21

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "Bs6NqU5Zh7", "reviewer": "Reviewer_qVHf", "summary": "This work proposes a posterior sampling algorithm for Bayesian algorithm execution, where the goal is to infer the output of an algorithm $O$ applied to an unknown function $f$.  The algorithm is simple to implement and computationally more efficient than previous works based on mutual information maximization.  The authors proved the algorithm is consistent with prior probability 1, and demonstrated empirically that it has comparable and sometimes better sample efficiency than previous work while being faster computationally.", "questions": "My main question is about the proof of Theroem 1, in particular the claim on L762 that $Z\\cap O_A(f)=\\emptyset$ \"by construction\".  I can see this may be true if we assume $P_\\infty(O_A(f))$ always assigns positive probability to some set $X\\subset \\mathcal{X}$, but what if this is not the case, for example, if $P_\\infty(O_A(f))$ is a distribution over bounded intervals $\\subset \\mathbb{R}=\\mathcal{X}$ and its marginal distributions for the endpoints are atom-less?  Clearly similar issues can happen if we have (for example) a GP prior with a continuous kernel and consider $P_n$ instead of $P_\\infty$.  There should be explanations on why the issue will not happen with $P_\\infty$, or why the reasoning of L762 is still valid in the presence of such issues.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The problem studied is interesting and practically relevant.\n- The proposed method is simple, computationally efficient and empirically effective, thereby providing a robust baseline for the problem.\n- The paper is mostly well-written.", "weaknesses": "- I am uncertain about the correctness of the consistency proof (see question section below).\n\n- A less important point is about a design choice in the algorithm: when the sampled target set has multiple point the algorithm selects the point $x$ with the highest entropy $H[f(x)]$. This does not appear to be a universally optimal choice, for example if we want to estimate a level set $\\\\{x: f(x)\\ge A\\\\}$ and there exists some $x_0\\in \\mathcal{X}$ for which the posterior $P(f(x_0)\\mid D_n)$ has a very large mean and also a large variance: in such cases $H(f(x_0))$ could be the largest among the sampled level set but there may be little uncertainty that $x_0$ lives in the true level set.  In addition, there may be scenarios where we need to focus on inferring the boundary of the level set instead of reducing the uncertainty about function values in the interior.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer qVHf,\n\nWe sincerely appreciate your feedback and questions. We are glad that you found the problem of study \"interesting and practically relevant,\" our method providing \"a robust baseline for the problem,\" and our paper \"well-written.\" Your major concern relates to the correctness of a specific claim in our proof of Theorem 1. Below, we explain that the claim holds true under an additional assumption (see A1) that we regrettably neglected to include in the statement of Theorem 1. Noticing your high scores for soundness, presentation, and contribution, we hope this clarification will lead you to consider raising your rating. We also address a minor concern related to the optimality of our algorithm in certain settings.\n\n**Q1.** *\"My main question is about the proof of Theorem 1, in particular the claim…\"*\n\n**A1.** Our proof of Theorem 1 assumes that $\\mathcal{X}$ is a finite set. As noted, without this assumption, $\\mathbf{P}(X=\\mathcal{O}_{\\mathcal{A}}(f))$ cannot be guaranteed to be positive for any subset $X \\subset \\mathcal{X}$. We conjecture that a suitable form of asymptotic consistency for PS-BAX holds even if $\\mathcal{X}$ has infinite cardinality. However, we expect such analysis to be significantly more challenging given that techniques commonly used in Bayesian optimization to extend convergence guarantees to continuous input spaces, such as carefully chosen discretizations and Lipschitz assumptions (e.g., Bull et al. 2011 and Srinivas et al. 2012), do not naturally translate to settings where performance cannot be summarized by objective function values. We believe this is the reason why most theoretical results in level set estimation assume that the input space is finite (see, e.g., Gotovos et al. 2013 and Mason et al. 2022). Despite this limitation, our theoretical guarantee still covers a broad range of real-world applications; in particular, the shortest path, top-K, and drug discovery problems explored in our experiments, which are inherently discrete.  We apologize for the confusion and hope this response alleviates any concerns regarding the validity of our theoretical result.\n\n**Q2.** *\"A less important point is about a design choice in the algorithm…\"*\n\n**A2.** PS-BAX comprises two steps: (1) drawing a sample from the posterior distribution on the target set and (2) selecting a point within the sampled target set. For the second step, we chose to select the point with the highest posterior variance within the sampled target set, which is a simple strategy that can ensure asymptotic consistency, inspired by active learning. Despite its simplicity, this strategy performs well across a broad range of tasks. However, we agree that other strategies tailored to specific applications could potentially improve performance further. We see this as a valuable direction for future research enabled by this work, and the demonstration that posterior sampling can be successfully applied to a broader range of tasks beyond optimization as our primary contribution.\n\n**References**\n\nGotovos, A., Casati, N., Hitz, G., & Krause, A. (2013). Active learning for level set estimation. In International Joint Conference on Artificial Intelligence.\n\nMason, B., Jain, L., Mukherjee, S., Camilleri, R., Jamieson, K., & Nowak, R. (2022). Nearly Optimal Algorithms for Level Set Estimation. In International Conference on Artificial Intelligence and Statistics.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8D6zaQ1hMA", "reviewer": "Reviewer_FDTf", "summary": "This paper utilizes the idea of Bayesian sampling in the Bayesian algorithm execution (BAX) framework. As claimed by the authors, this is the first extension of posterior sampling beyond the optimization setting. The idea is very simple and natural and the performance seems reasonable. While I am not familiar with the BAX literature, it seems that the theoretical justification is incorrect.", "questions": "Please see weakness.", "limitations": "The checklist mentions that it discusses the limitation in section 4.3, but I cannot find it.", "rating": 5, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "Overall, the paper is well structured and well written.", "weaknesses": "In terms of computation cost, if a Gaussian process is used, then the computation cost of posterior variance $\\sigma_n(x)$ involves the inversion of a high dimensional matrix. Can you please comment on it?\n\nIn terms of the theorem 1:\nThe notation is very confusing. On the LHS ($P_n(X=\\mathcal{O_ A}(f))$), $f$ is random with probability measure $P_n$. On the RHS ($1(X=\\mathcal{O_ A}(f))$), $f$ becomes fixed. I suppose the author means that on the LHS, $f$ refers to the random sample, and on the RHS, $f$ refers to the true function.\n\nThe proof of theorem 1 doesn't involve the prior specification or the true $f$ function, which seems incorrect.\nFor instance, (1) if the prior distribution is a Dirac measure, then the posterior is also a Dirac measure, and the algorithm never works as the sampling repeatedly returns the same $f_n$. But it won't affect theorem 1? (2) if $f$ contains a flat region of global optimal and $\\mathcal A$ aims to find optimums, (i.e., $\\mathcal{O_ A}(f)$ is an uncountable set) and the Gaussian process is used,  then with probability 1, $\\mathcal{O_ A}(\\tilde f_n)$ contains only one element for any $n$. The claimed convergence clearly doesn't hold.\n\nTheorem 2 claims that consistency fails in general, and Theorem 1 claims that consistency holds when we have the stable assumption. This implies that some restriction is necessary, and the stable assumption is a sufficient assumption, not a necessary assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer FDTf,\n\nWe sincerely thank you for your comments and questions. We are glad that you found our paper \"well structured and well written.\" You expressed concerns related to the notation and clarity of our theoretical results. We hope our response below addresses these concerns. Since no other major issues were raised, we kindly ask you to consider raising your rating.\n\n**Q1.** *\"In terms of Theorem 1: The notation is very confusing. On the LHS…\"*\n\n**A1.** Our statement of Theorem 1 is indeed mathematically correct and we hope to clarify any misunderstandings here. Under a Bayesian perspective, $f$ is a random function with a given prior probability distribution. On both sides of the equation \n$\\lim\\_{n\\rightarrow\\infty}\\mathbf{P}\\_n(X = \\mathcal{O}\\_{\\mathcal{A}}(f)) = \\mathbf{1}\\set{X = \\mathcal{O}\\_{\\mathcal{A}}(f)}$,\n$f$ refers to the same random function. Furthermore, we note that $\\mathbf{P}\\_n$ is a random probability measure due to its dependence on the dataset $\\set{(x_i, y_i)}\\_{i=1}^n$, which in turn depends on $f$. Thus, the claim that “$\\lim\\_{n\\rightarrow\\infty}\\mathbf{P}\\_n(X = \\mathcal{O}\\_{\\mathcal{A}}(f)) =\\mathbf{1}\\set{X = \\mathcal{O}\\_{\\mathcal{A}}(f)}$ almost surely” should be interpreted as follows: the sequence of random variables $\\set{\\mathbf{P}\\_n(X = \\mathcal{O}\\_{\\mathcal{A}}(f))}\\_{n=1}^\\infty$ converges almost surely to the random variable $\\mathbf{1}\\set{X = \\mathcal{O}\\_{\\mathcal{A}}(f)}$ under the probability measure induced by the prior on $f$. We will clarify this in the revised version of our manuscript.\n\nIn measure-theoretic terms, Theorem 1 simply states that the random variable $\\mathbf{1}\\set{X =  \\mathcal{O}\\_{\\mathcal{A}}(f)}$ is $\\mathcal{F}\\_\\infty$ -measurable, where $\\mathcal{F}\\_\\infty$ is the sigma-algebra generated by the sequence of observations $\\set{(x_n, y_n)}\\_{n=1}^\\infty$. Intuitively, this means that given the data $\\set{(x_n, y_n)}\\_{n=1}^\\infty$, we can perfectly determine if the statement “ $\\mathcal{O}\\_{\\mathcal{A}}(f)$ is equal to $X$” is true for any $X$. In particular, the following is a direct corollary of Theorem 1.\n\n*Corollary.* Let $\\widehat{X}\\_n = \\arg\\max\\_{X\\subset\\mathcal{X}} \\mathbf{P}\\_n(X =  \\mathcal{O}\\_{\\mathcal{A}}(f))$ be the time-$n$ maximum a posteriori estimator of $\\mathcal{O}_{\\mathcal{A}}(f)$. Then, $\\widehat{X}\\_n$ converges to $\\mathcal{O}\\_{\\mathcal{A}}(f)$ almost surely.\n\n**Q2.** \"The proof of Theorem 1 doesn't involve the prior specification or the true $f$ function…\"\n\n**A2.** We apologize for the confusion caused by our statement of Theorem 1. As discussed in A1, we follow a Bayesian perspective where $f$ is drawn from the prior distribution used by our algorithm. Our result assumes that the prior is well-specified. Such results are typical in the literature (see, e.g., Russo and Van Roy 2014, Bect et al. 2016, and Astudillo and Frazier 2021) and can be seen as the Bayesian counterpart of frequentist results, which typically assume that $f$ lies in the reproducing kernel Hilbert space of a user-specified kernel. Consistency in the case where the prior over $f$ is a Dirac measure does hold. Regarding the example where $f$ \"contains a flat region of global optimum and A aims to find optima… and the Gaussian process is used,\" we agree that consistency does not hold because the prior is not well-specified in this case. We will revise our statement of Theorem 1 to clarify that $f$ is assumed to be drawn from the prior distribution to avoid this confusion in the future.\n\n**Q3.** \"...the stable assumption is a sufficient assumption, not a necessary assumption.\"\n\n**A3.** We thank the reviewer for pointing this out. We will revise our usage of the word \"necessary\" in Line 168 to avoid this confusion. As noted, Theorem 1 shows that stability is a sufficient condition for asymptotic consistency, and Theorem 2 shows that asymptotic consistency cannot be guaranteed without stability.\n\n**Q4.** \"...the computation cost of posterior variance $\\sigma_n(x)$ involves the inversion of a high-dimensional matrix\"\n\n**A4.** The computation of the posterior variance scales as $n^3$, where $n$ is the number of training points. While this is seen as a computational bottleneck in other applications involving Gaussian processes, it is not the case in Bayesian optimization and Bayesian algorithm execution tasks, where the maximum number of evaluated points rarely surpasses 1000 due to the assumed high cost of such evaluations. In contrast, the computation of the expected information gain required by INFO-BAX scales as $(n+m)^3$, where $m$ is the size of the target set, also due to the need to compute the inverse of a matrix. Even if $n$ is small, $m$ can be very large in real-world applications such as shortest-path problems and level-set estimation tasks, making INFO-BAX extremely computationally demanding.\n\n**Q5.** \"The checklist mentions that it discusses the limitation in section 4.3…\"\n\n**A5.** We apologize for the confusion. We meant Section 3 instead of Section 4.3. Additionally, in Section 2 (Lines 77-78), we point out that the range of problems that can be tackled with our PS-BAX strategy is narrower than those that can be tackled with INFO-BAX.\n\n**References**\n\nAstudillo, R., & Frazier, P. (2021). Bayesian optimization of function networks. Advances in Neural Information Processing Systems, 34, 14463-14475.\n\nBect, J., Bachoc, F., & Ginsbourger, D. (2019). A supermartingale approach to Gaussian process based sequential design of experiments. Bernoulli, 25(4A), 2883-2919.\n\nRusso, D., & Van Roy, B. (2014). Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4), 1221-1243.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "11xNWjONgU", "reviewer": "Reviewer_Ta95", "summary": "This paper introduces a scalable posterior sampling algorithm (aka PS-BAX) in the framework of Bayesian algorithm execution (BAX). Its fundamental basis is built on a key observation that the property of interest for many tasks is a target set of points, which for many scenarios such as standard bayesian optimization and level set estimation is usually the subset of the domain of the function. The authors propose PS-BAX with two key steps at each iteration: first the algorithm computes the target set using a sampled function from a posterior of Gaussian process; then it chooses the point with highest posterior variance (or entropy). In comparison to prior work (mainly INFO-BAX) based on expected information gain (EIG), PS-BAX shows superior computational efficiency. The authors have also established the asymptotic consistency of PS-BAX assuming the target set is stable.", "questions": "1. The authors claim that PS-BAX is scalable to high dimensional problems. The experiments contain examples only up to 10 dimensions. In the gene embedding experiment, the authors applied PCA to reduce the data to 5 dimensions. I suspect the Gaussian process approximations might be problematic in high dimensions. Can you justify the feasibility of applying PS-BAX to high dimensional data in numerical experiments?\n\n2. INFO-BAX optimizes the mutual information over the entire domain X, whereas PS-BAX optimizes over a sampled target set X_n which is a subset of X. At each iteration (especially early iterations), one can imagine INFO-BAX should select a point that’s more informative on learning the task as it’s over the entire space. However, for some experiments (e.g. Figure 4), PS-BAX performs much better than INFO-BAX for early iterations. Can you provide more intuition on such phenomena?  \n\n3. The authors also claim that the PS-BAX method is easily parallelizable as one of the attractive contributions. However, as described in the main algorithm, PS-BAX is based on sequential computation of the posterior for the Gaussian process given samples selected from earlier iterations. Can you provide more details on how it can be parallelizable?", "limitations": "My major concern is that within the BAX framework minimizing the number of evaluations is of primary importance. However, PS-BAX seems to have a lower efficiency picking up points as compared to the INFO-BAX method given a limited number of iterations. The study of non-asymptotic results seems to be important to provide practical guidance as compared to asymptotic results.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and the algorithm is validated through extensive and broad classes of experiments with comparisons to other methods.", "weaknesses": "This paper is an incremental work on INFO-BAX, which provides an alternative method to get around the expensive EIG computations by limiting the optimization to a target set per iteration. The posterior sampling is intuitive, however, it lacks rigorous development on its connection to INFO-BAX.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Ta95,\n\nWe thank you for your feedback and questions. We are glad that you found our paper \"well-written\" and our empirical evaluation \"extensive.\" We hope to address your concerns in the following clarifications.\n\n**Q1.** *\"This paper is an incremental work on INFO-BAX… it lacks rigorous development on its connection to INFO-BAX\"*\n\n**A1.** We reiterate that PS-BAX offers superior computational efficiency and empirical performance compared to the state-of-the-art INFO-BAX. Furthermore, unlike INFO-BAX, PS-BAX enjoys a provable convergence guarantee. These facts alone demonstrate that our work is a substantial advancement.\n\nAdditionally, though both policies use posterior samples of the target set, the design principles of INFO-BAX and PS-BAX are fundamentally different. INFO-BAX uses them to approximate the expected information gain (EIG) over the target set and then chooses the point maximizing this quantity. In contrast, PS-BAX draws a single posterior sample to identify a region likely to be the target set and then chooses the point with the highest posterior uncertainty within this set. While PS-BAX’s second step is also related to the notion of entropy, the EIG calculation required by INFO-BAX is generally much more computationally demanding, as discussed in Appendix B. We hope this further clarifies the algorithmic difference and highlights the novelty of our work.\n\n**Q2.** *\"The authors claim that PS-BAX is scalable to high dimensional problems… I suspect the Gaussian process (GP) approximations might be problematic…\"*\n\n**A2.** As noted, GP models struggle in high-dimensional settings. However, this is a limitation of GPs - PS-BAX can easily be paired with other probabilistic models. To demonstrate this and alleviate concerns, we conducted an additional experiment involving a top-K protein optimization task with an 80-dimensional input space using the publicly available GB1 dataset. Instead of a traditional GP, in this experiment, we use a deep kernel GP (Wilson et al. 2015), which scales better to higher-dimensional settings. As shown in Figure 1 of the PDF attached to our rebuttal’s overall response, PS-BAX and INFO-BAX perform similarly (both outperforming Random significantly). However, like in other problems, PS-BAX is much faster to compute.\n\nIndeed, in our paper, we imply that PS-BAX scales better to high-dimensional settings than INFO-BAX. Here, we referred specifically to the computational cost of PS-BAX and INFO-BAX in problems of moderate-to-high dimension. Maximizing the EIG, as required by INFO-BAX, becomes prohibitively expensive in such settings. For instance, in the Ackley 10-D problem, each iteration of INFO-BAX takes over 6 minutes. In contrast, PS-BAX, with its lightweight computation, remains feasible in moderate dimensions (only 15 seconds for Ackley 10-D).\n\n**Q3.** *\"...for some experiments (e.g. Figure 4), PS-BAX performs much better than INFO-BAX for early iterations.\"*\n\n**A3.** The superior performance of PS-BAX over INFO-BAX is due to two key reasons.  First, PS-BAX inherits posterior sampling’s strong exploration capabilities due to the stochastic nature of its sampling choices, allowing it to escape incorrect posterior beliefs of the target set’s identity. This is particularly true in challenging problems, where uncertainty remains significant throughout the experimentation loop. In contrast, INFO-BAX myopically tries to minimize the target set’s posterior uncertainty as much as possible at each iteration, causing it to get stuck in a wrong belief of the true target’s identity. This behavior is observed in Figure 3  (corresponding to the performance plot shown in Figure 4), where INFO-BAX fails to find a portion of the target set due to its lack of exploration. The second reason is computational. As discussed above, maximizing the EIG over high-dimensional spaces is challenging, meaning that despite significant computational efforts, INFO-BAX is potentially choosing to evaluate a local maximum of the EIG instead of the global maximum, thus deteriorating its performance.\n\n**Q4.** *\"The authors claim that PS-BAX is easily parallelizable…\"*\nA4. We apologize for any confusion. By \"parallelizable,\" we mean that our algorithm can be generalized to the \"parallel\" or \"batch\" setting, where multiple points are selected at each iteration (Kandasamy et al. 2018). This generalization follows the approach of Kandasamy et al. (2018). Specifically, to select $q$ points at each iteration, we draw $q$ independent samples from the target set and then select the subset of $q$ points with the highest entropy. To demonstrate our algorithm's empirical performance in the batch setting, we include results for two test problems analyzing PS-BAX under three different batch sizes in Figures 2 and 3 of the PDF attached to our rebuttal’s overall response.\n\n**Q5.** *\"My major concern is that… PS-BAX seems to have a lower efficiency.. compared to INFO-BAX ... The study of non-asymptotic results seems to be important…\"*\n\n**A5.** We kindly ask the reviewer to consider that our empirical evaluation clearly shows the opposite: PS-BAX is more efficient than INFO-BAX, especially in challenging problems. In contrast, there is no evidence, theoretical or empirical, to substantiate that INFO-BAX is more efficient than PS-BAX. We agree that non-asymptotic results could provide guidance. However, this does not diminish the contributions of our work, which provides an algorithm with faster computation, significantly better empirical performance, and a convergence guarantee.\n\n**References**\n\nKandasamy, K., Krishnamurthy, A., Schneider, J., & Póczos, B. (2018). Parallelised Bayesian optimisation via Thompson sampling. In International Conference on Artificial Intelligence and Statistics.\n\nWilson, A. G., Hu, Z., Salakhutdinov, R., & Xing, E. P. (2016). Deep kernel learning. In International Conference on Artificial Intelligence and Statistics.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zX65TgGkOx", "reviewer": "Reviewer_BTqx", "summary": "This paper proposes a new method within the Bayesian algorithm execution framework, which enables finding a target set of points in a highly efficient manner.", "questions": "The word “posterior sampling” seems to mean something very specific in this paper. However, in the Bayesian literature, this term is used for a much wider set of problems, which may be confusing to some readers of this paper. I think the mention the alternative term “Thompson sampling”. Could this be a good alternative name to use in relevant places?", "limitations": "I think the authors could discuss more limitations of this method. Are there any major limitations beyond the fact that the method only works for base algorithms that have a set of points as target?", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The problem tackled in this paper is highly important. The proposed method is sound and shows strong improvements vs. relevant benchmarks, in particular with respect to speed and sometimes also in terms of accuracy.", "weaknesses": "I don’t see any noteworthy weaknesses, but I am also not an expert in BO and related tasks (only about Bayesian inference more generally).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer BTqx,\n\nWe sincerely appreciate your feedback and positive evaluation of our work. We have addressed your comments below and are ready to discuss any new questions or concerns that may arise during the discussion period. Additionally, given your positive assessment, we would deeply appreciate your support in championing our paper during the discussion period. Thank you in advance for your help!\n\n**Q1.** *\"The word 'posterior sampling' seems to mean something very specific in this paper. However, in the Bayesian literature, this term is used for a much wider set of problems… the alternative term 'Thompson sampling.' Could this be a good alternative name to use in relevant places?\"*\n\n**A1.** Thank you for pointing this out. We initially chose \"posterior sampling\" instead of \"Thompson sampling\" because we thought the latter might be too closely associated with optimization settings, whereas our work addresses a broader class of problems. However, in hindsight, we agree that \"posterior sampling\" may be too broad. We will revise our terminology accordingly in the final version.\n\n**Q2.** *\"I think the authors could discuss more limitations of this method. Are there any major limitations beyond the fact that the method only works for base algorithms that have a set of points as target?\"*\n\n**A2.** Our approach inherits several limitations from Bayesian optimization. Specifically, the good performance of PS-BAX depends on having a probabilistic model with reasonable predictive capabilities, which can be challenging in some applications. Since this limitation also applies to INFO-BAX and most probabilistic numerical methods, we did not initially highlight it. However, we will add a discussion on this in the revised manuscript. Additionally, as mentioned in Section 3, there is room for more sophisticated theoretical analyses of PS-BAX and INFO-BAX. While we see this as a future research direction enabled by our work rather than a limitation, we acknowledge the importance of developing novel theoretical tools to further analyze these methods.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers,

We sincerely thank you for your thoughtful comments and questions. We are pleased that you found our paper well-written (qVHf, FDTf, Ta95, BTqx), addressing an interesting and practically relevant problem (qVHf, BTqx), and proposing a sound algorithm (qVHf, FDTf, BTqx) with clear performance improvements demonstrated through extensive empirical evaluation (qVHf, FDTf, Ta95, BTqx).

Our paper's current ratings are as follows:
* **Reviewer BTqx** provided a high appraisal with a rating of 7.
* **Reviewers qVHf and Ta95** both assigned a rating of 4. Despite the moderate ratings, their comments are fairly positive, and their scores for soundness, presentation, and contribution are high. We believe we have addressed their concerns effectively and hope they will consider raising their ratings.
* **Reviewer FDTf** assigned a rating of 3. The only major concern raised was the correctness of our asymptotic consistency result. As we explained in our response, our theoretical result is correct, and the confusion arises from not explicitly stating that $f$ is assumed to be drawn from the prior distribution, a simple improvement we will include in the revised version of our manuscript. Since no other concerns were raised, we kindly ask this reviewer to consider raising their rating.

We have responded to each reviewer’s questions individually, aiming to provide sufficient detail. However, we would like to use this space to globally comment on a few points:

**Contributions of our work:** We introduce PS-BAX, a novel algorithm applicable to a wide range of real-world problems, offering superior computational efficiency and empirical performance compared to the state-of-the-art (INFO-BAX). Additionally, PS-BAX comes with a convergence guarantee (unlike INFO-BAX) and provides novel insights into posterior sampling methods. We believe these contributions are at least on par with the average NeurIPS paper, so we kindly ask reviewers to consider raising their ratings.

**Novelty and algorithm design choices:** PS-BAX is the first application of posterior (Thompson) sampling to the Bayesian algorithm execution setting. Indeed, PS-BAX reduces to posterior sampling when the algorithm is simply selecting the argmax. While there are many ways to extend posterior sampling, we chose a simple yet effective approach: selecting the point with the highest uncertainty among the candidate points returned by the posterior sampling step. Exploring other design choices would be a great direction for future research enabled by our work.

**Theoretical results:** We appreciate Reviewers qVHf and FDTf for requesting more clarification about our theoretical results. As detailed in our individual responses, the issues are minor and can be easily addressed.

Thank you again for your insightful feedback. We look forward to a fruitful and engaging discussion.

Sincerely,

The authors

Meta-review: This paper considers the Bayesian optimization execution framework, deriving a simple yet effective and scalable posterior sampling algorithm with both theoretical and empirical validation. All reviewers agreed that the proposed algorithm is interesting and valuable. In the meantime, we do received concerns in the soundness of the theory of this paper about the consistency proof and the boundedness assumption. After several rounds of interactions between reviewers and authors, the main concerns have been well addressed and so the consensus was made to accept this paper. 

In the final version of this paper, the authors are required to improve the clarity of this paper in 
- clearer notation definitions;
- explicitly present the boundedness assumption and discuss its limitation and necessarity of having this assumption
- clarify the consistency result in theorem 1.
Decision: Accept (poster)