Batched Bayesian optimization with correlated candidate uncertainties

Authors: Jenna Fromer, Runzhong Wang, Mrunali Manjrekar, Austin Tripp, José Miguel Hernández-Lobato, Connor W. Coley
Primary area: applications to physical sciences (physics, chemistry, biology, etc.)
Keywords: Bayesian optimization, molecular design, molecular discovery, uncertainty, model-guided optimization

Abstract:
Batched Bayesian optimization (BO) can accelerate molecular design by efficiently identifying top-performing compounds from a large chemical library. Existing acquisition strategies for batch design in BO aim to balance exploration and exploitation. This often involves optimizing non-additive batch acquisition functions, necessitating approximation via myopic construction and/or diversity heuristics. In this work, we propose an acquisition strategy for discrete optimization that is motivated by pure exploitation, qPO (multipoint Probability of Optimality). qPO maximizes the probability that the batch includes the true optimum, which is expressible as the sum over individual acquisition scores and thereby circumvents the combinatorial challenge of optimizing a batch acquisition function. We differentiate the proposed strategy from parallel Thompson sampling and discuss how it implicitly captures diversity. Finally, we apply our method to the model-guided exploration of large chemical libraries and provide empirical evidence that it performs better than or on par with state-of-the-art methods in batched Bayesian optimization.

Decision: reject
Reviewer scores: 5, 5, 3, 3

Reviews and discussion:
<thread>
creation date:
1729787358878

thread_type:
official_review

<thread_object>
creator: reviewer_8r9v

<content>
summary:
This paper proposes a new batch acquisition function (qPO) for bayesian optimization in discrete search space. qPO is a purely exploitative approach, and its objective is to maximize the probability that the true optimum exists within the selected batch. qPO has nice property that it can be decomposed into a sum of scores over candidates, which allows naive parallelization in batch setting and simplifies the implementation.

The authors evaluate qPO on two molecular optimization tasks and show empirically that qPO performs comparably to or better than state-of-the-art batch acquisition method like q-TS, q-EI and UCB.

strengths:
Originality
1. The formulation of batch acquisition function is novel, and its unique decomposition property where the batch acquisition function equals sum of individual probabilities is useful
2. Achieving batch diversity through formulation towards exploitation is creative

Quality
1. Mathematical formulation and derivation of qPO is clear and sound.

Clarity
1. Visualization of batch diversity in Figure 3 showing both network structure and similarity distributions is great.
2. The 3-point example in Section 3.2 helps illustrate key properties of the acquisition function

Significance
1. Introduces a simpler alternative to complex batch construction strategies
2. The decomposition property makes the method computationally tractable for moderated sized search space

weaknesses:
1. There is no theoretical justification for why maximizing probability of optimality leads to better sample efficiency (compared with other existing batch acquisition functions like q-EI, q-PI, etc.), and convergence analysis is also absent
2. The diversity property is not unique to qPO as similar property exists in q-PI and other joint probability based methods, but the paper does not provide discussion for this
3. The empirical study is not sufficient:
    1. Missing standard BO benchmarks like synthetic functions
    2. No ablation studies to analyze impact of batch size, effect of pre-filtering threshold, sensitivity to number of MC samples, etc.
    3. There is no comparison to existing joint probability based methods like q-PI, as they are most similar to qPO
4. The pre-filtering strategy may miss promising candidates, therefore, there should be robustness analysis of this method

questions:
1. Estimation of qPO through MC sampling seems computational expensive, can you provide runtime comparisons with other batch acquisition methods?
2. How robust is the method to model poor initial training data?
3. Does the pre-filtering step risk overlooking promising candidates in the regions with high uncertainty?
</content>
</thread_object>

</thread>
<thread>
creation date:
1729839909846

thread_type:
official_review

<thread_object>
creator: reviewer_gd5x

<content>
summary:
This paper investigates a novel acquisition function (qPO) for enhancing batch diversity in Thompson sampling. The approach shares conceptual similarities with entropy-search-based methods, as it leverages numerous Thompson sampling trials to estimate the posterior belief of the global optima, due to the non-closed-form nature of this distribution. The estimated function is then maximized to guide selection. While the proposed method relies on several approximation techniques to accelerate computation—whose statistical consistency and bias have yet to be thoroughly validated—it demonstrates superior performance over three baseline methods, which were not specifically designed for diversified batch sampling.

strengths:
- Highly parallel Bayesian Optimization is an important challenge in real-world tasks, though numerous existing works have pursued similar approaches with clearer conceptual frameworks and stronger theoretical foundations.
- While real-world examples add interest, they rely solely on existing datasets, such as QM9, and thus do not introduce new applications. This work remains primarily an algorithm-focused paper.
- While I appreciate the authors’ effort in presenting Figure 1 to convey the intuition behind the method, I would have liked to see a more precise mathematical explanation.

weaknesses:
My primary reasons for recommending rejection are as follows: (1) issues with clarity, particularly in the mathematical exposition, (2) limited insights and contributions to the community, and (3) an unfair selection of baselines, which undermines the validity of the claimed empirical improvements.

- **Clarity**
One of the major issues in this paper is clarity, particularly regarding the mathematical exposition. I had a hard time to understand Eqs. (6)–(11). My detailed concerns are as follows:

**Eqs. (6)–(10):** What do the bold vectors $\textbf{x}$ and $\textbf{y}$ represent? Are they the observed points so far, or do they represent all candidates, where $|\textbf{x}| = N$? The former interpretation doesn’t make much sense, so I assume it’s the latter. In that case, this expression becomes a utility function for probability of improvement (PI) (see page 2 in [1]). Then $p(\textbf{y} \mid \textbf{x})$ in Eq. (9) would describe an ideal scenario where we have access to the entire domain $\textbf{x}$, $\textbf{y}$. However, this understanding conflicts with the textual explanations. Specifically, in lines 192–193, the reference to “myopic construction” isn’t clear. If this is indeed the PI utility function $u$, then it would follow that the resulting PI is myopic. Although $Pr(x^\star)$ is indeed the optimal acquisition function, it’s also not achievable in practice, since we could identify $x^\star$ in a single iteration if we had access to the “oracle acquisition function.” Thus, we use a surrogate model to estimate $x^\star$, resulting in an estimate $\hat{x}^\star$, not $x^\star$. Consequently, the myopicness originates from the belief model $f$, not the utility function $u$. Thus, the entire discussion is confusing.

**Eq. (11):** This equation is especially difficult to interpret. What do $y^{(m)}_i$ and $\textbf{y}^{(m)}$ represent? I assume $\textbf{y}^{(m)}$ is a sample function drawn from the GP posterior, with $\max \textbf{y}^{(m)}$ as its maximum, similar to Thompson sampling (TS). However, what is $y_i$? Is it the predictive mean $m(x_i)$? If my understanding is correct, then only one point should be true, with all others zeroed out in the indicator count $\textbf{1}$. Isn’t this an embarassingly inefficient Monte Carlo estimation? Even if we were to take a very large number of samples $M$, the belief model is not the true function. This would imply that the resulting estimate is the posterior belief of the optimum $Pr(\hat{x}^* = x_i)$. Why, then, would this recover the probability of the true optimum $x^*$? This is not strictly an approximation of Eq. (10); while it may be asymptotically convergent, further justification is required to establish this.

- **Unclear Benefits and Inaccurate Descriptions**
Due to clarity issues, I was unable to fully understand how this method differs from existing approaches, such as entropy-search-based methods [2] or other principled approaches in diversified parallel TS. First, the term "correlated candidate uncertainty" in the title is unclear, as it isn’t fully explained within the paper. If this refers to the diversification of the batch selection, there are many existing works. On line 320, the phrase “Deterministically maximize” is somewhat misleading. This statement would hold if Eq. (11) had a closed-form solution. However, since this algorithm relies on multiple approximations, it will not be deterministic due to numerical randomness, similar to TS. Additionally, the “diversity heuristics” mentioned on line 280 are inaccurately described. For instance, Nava et al. (2022) demonstrated a theoretical improvement in convergence rates over parallel TS, showing that these are not merely heuristics but instead clearly proven benefits. In contrast, this paper does not present any convergence analysis results, making it a heuristic approach. Could you clarify which aspects of the parallel TS convergence rate [3] qPO improves upon? Is such improvement better than recent work by Nava et al. (2022) and Ren & Li (2024), which proves tighter regret bounds via batch diversity? If this method (qPO) cannot achieve theoretical or empirical improvements over these methods, I see limited justification for adopting it over these established approaches.

- **Robustness Issues** 
Recent work [4,5] raises issues that contrast with the claims in this paper. While this paper argues that parallel TS is overly explorative and suggests an exploitative approach as a remedy, [4,5] contend that parallel TS lacks sufficient diversity and instead requires an explorative adjustment. Intuitively, one would expect an exploitative approach to reduce batch diversity rather than enhance it. Why, then, does this method claim that exploitation leads to diversification? Additionally, [4] and [5] underscore robustness issues in parallel TS-based methods, specifically regarding accurate sample drawing and model misspecification. For example, [4] shows that heuristic approximations, such as the greedy sampling used in this paper, introduce bias in approximating the probability distribution, proposing Matheron’s rule as a corrective approach. Furthermore, [5] demonstrates that if GP hyperparameters are misspecified (e.g., lengthscale), the Monte Carlo estimate in TS becomes biased, and they address this with a robust kernel quadrature approach. Both of these concerns are relevant to the tasks considered in this paper: the sampling approach does not utilize an exact Cholesky decomposition, and the Tanimoto kernel lacks a consistency guarantee for MLE-based hyperparameter estimation. More generally, hyperparameter estimation with MLE in GPs is theoretically ill-posed [8]. Since this paper does not address these robustness concerns, it is unclear what progress or insights it contributes, especially since both [4] and [5] achieve improved diversity akin to the results here.

- **Unfair Baselines**. It’s also worth noting that the baselines selected in this paper are outdated and do not reflect recent advancements. For instance, the qEI baseline should employ sample average approximation with quasi-Monte Carlo as in the original BoTorch paper [6], while UCB should ideally use DB-GP-UCB [7], which is a more theoretically grounded batch approach in UCB. Furthermore, for pTS, which is the main target of this work, a fair comparison would require recent theoretical contributions, such as those by Nava et al. (2022) and/or Ren & Li (2024), as well as empirical work from [4, 5]. Without these comparisons, it is difficult to gauge the practical utility of this method. Given the variety of heuristic and theoretical methods already available, if this approach is intended to be an improvement, a comprehensive empirical comparison with the aforementioned methods is essential. Alternatively, if the goal is to provide new insights, the paper should offer theoretical analysis and/or a clearer empirical study to identify scenarios where this method excels yet other state-of-the-art methods fail, making it more relevant to the community. While this method may have presented an improvement over parallel TS in 2017, it now appears outdated.

- **Minor points**. I also believe that [3] should be cited as a foundational reference for parallel TS, as it provides a clearer theoretical understanding of the method. While Hernández-Lobato et al. (2017) originally proposed it, [3] now serves as a key reference for the theoretical insights underpinning parallel TS.

- **Citations**
- [1] https://www.cse.wustl.edu/~garnett/cse515t/spring_2015/files/lecture_notes/12.pdf
- [2] Takeno, Shion et al., "Sequential and Parallel Constrained Max-value Entropy Search via Information Lower Bound", ICML 2023
- [3] Kandasamy, Kirthevasan, et al. "Parallelised Bayesian optimisation via Thompson sampling." AISTATS 2018
- [4] Wilson, James, et al. "Efficiently sampling functions from Gaussian process posteriors." *ICML 2020*
- [5] Adachi, Masaki, et al. "A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting." arXiv:2404.12219 (2024).
- [6] Balandat, Maximilian, et al. "BoTorch: A framework for efficient Monte-Carlo Bayesian optimization." NeurIPS (2020).
- [7] Daxberger, E. A. et al. "Distributed batch Gaussian process optimization". ICML (2017)
- [8] Karvonen, T. et al. "Maximum Likelihood Estimation in Gaussian Process Regression is Ill-Posed". JMLR (2023)

questions:
See the weakness section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730495673657

thread_type:
official_review

<thread_object>
creator: reviewer_tsqa

<content>
summary:
This paper proposes a batch acquisition function for Bayesian optimization on finite (and necessarily discrete) domains.
The acquisition function is the probability that the selected candidates contain the global optimum:
\\[
    \Pr(x^* \in \mathcal{X} _ {\text{selected candidates}}).
\\]
While it's quite challenging to compute this probability on continuous domains, it's easier to estimate this probability on discrete domains.
Indeed, the authors propose approximating this probability using Monte Carlo samples.
On antibiotic discovery and organic electronics design problems, the authors show that the proposed method outperform parallel Thomson sampling, multiple point EI, and UCB.

strengths:
- The method is intuitive and simple.
- The writing is overall good.
- The improvement over parallel Thompson sampling, qEI, and UCB seems to be consistent across several datasets.

weaknesses:
- This paper focuses on finite domains, which certainly simplifies the problem a lot.
This is reasonable.
However, if the primary application is molecule designs, I'd like to see comparisons with recent alternative Bayesian optimization methods that do not frame this problem as a finite discrete BO problem.

There are several immediate ideas worth considering. Without trying these ideas, the paper seems underdeveloped at this moment.
1. As noted by the authors, the probability \\(\Pr(x^* = x_i)\\) is an orthant normal probability, which can be handled by many existing Monte Carlo methods.
These methods are probably much more efficient and accurate than the proposed estimation method in this paper.
In particular, the method of Genz (1992), which is based on importance sampling, is not too hard to implement.
So employing better numerical methods estimating this normal probability is a nice plus.
2. The biggest improvement actually comes from filtering \\(10000\\) candidates using a greedy metric (which seems to be the posterior mean).
The authors argue that they do so due to the large computational cost of GP posterior sampling.
However, the experiments in Section 4.2 (\\(n = 39,312\\)) should be easily handle by modern GP packages, and the experiments in Section 4.3 (\\(n = 133,000\\)) should be easily handled by variational GPs.

- Also, in my opinion, the paper title is not reflective of the paper content.

questions:
- The authors mentioned multiple times that the proposed acquisition function is purely exploitative.
I am not sure if this statement is accurate.
On a high level, the method seeks candidates that are more likely to be the optimum.
Its spirit is similar to predictive entropy search in the continuous setting, which is not purely exploitative.

- While the writing is good overall, it's not clear what the candidates \\(\\mathbf{x}\\) are at line 180. (Also at Line 220 ALgorithm 1).
Based on the experiments, it seems that \\(\mathbf{x}\\) is a subset of the domain selected by the greedy strategy (based on posterior mean)?

- I am not sure how Equation (4) makes sense.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730955853287

thread_type:
official_review

<thread_object>
creator: reviewer_pfuf

<content>
summary:
The paper proposes an exploitive batched acquisition function that can be efficiently approximated as the sum of individual acquisitions. The method assumes a low-noise environment and explicitly encourages diversity in the queries. Due to the absence of an analytic form of the optimum, the acquisition function is implemented using Monte Carlo approximation. The paper demonstrates empirical evidence on real-world applications.

strengths:
1. The core idea of the algorithm—devising a batch acquisition function that is the sum of individual acquisitions to enhance computational tractability—is convincing.

2. The illustrative case studies, along with figures, effectively demonstrate the advantages of promoting diversity.

weaknesses:
1. The proposed algorithm resembles Predictive Thompson Sampling (pTS). Although the paper briefly discusses the differences between the proposed qPO and pTS and argues its advantages over existing methods, I find the argument not sufficiently convincing. There are two main reasons: First, pTS comes with convergence guarantees, whereas qPO only provides experimental results on unconventional metrics. Second, the randomness inherent in pTS and qEI is arguably the merit, offering robustness to model misspecification—which is common in real-world applications, as the paper also mentions. I hope the authors can elaborate more on the source of robustness in qPO, whether it arises from the sampling-based approximation or the deterministic acquisition that encourages diversity.

2. The paper omits a critical baseline: GIBBON (Moss et al., 2021), which shares the advantage of efficient batched acquisition calculation and is easy to implement with BoTorch.

3. Despite claiming that qPO is designed to be a computationally more efficient batched acquisition function, the paper includes no comparison of computational complexity, either analytically or empirically. This omission is problematic, especially since a Monte Carlo approximation is employed.

4. The metrics used in Section 4 are not the conventional cumulative regret or simple regret. Instead, the paper reports the retrieval of the top-k and the average reward of the top-k. It's unclear if these are valid choices without further justification.


***References***

- https://botorch.org/tutorials/GIBBON_for_efficient_batch_entropy_search

- Moss, Henry B., David S. Leslie, Javier Gonzalez, and Paul Rayson. "Gibbon: General-purpose information-based bayesian optimisation." Journal of Machine Learning Research 22, no. 235 (2021): 1-49.

questions:
1. I'm a bit confused by the discussion regarding the ensemble method as a surrogate model. It seems that the experimental section employed a Gaussian Process with a Tanimoto kernel. What is the role of the ensemble method in the paper, especially as shown in Figure 1?

2. Why is the equality between Equation (6) and Equation (7) valid? What are the assumptions about $f$ and $y$? It is confusing that the paper assumes $f$ is noise-free in line 87 while also assuming low but non-zero observation noise for the GP in line 168. Is there the assumption that $f$ follows a certain distribution, e.g., GP? If not, what is the distribution of $f$?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732058569823

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Responses to All Reviewers

comment:
We appreciate the valuable comments and suggestions provided by the reviewers. We have addressed each point and revised our manuscript accordingly. Below, we summarize the key changes and address common questions raised by the reviewers.

**Highlights of Changes**

1. **Expanded Baseline Comparisons**: We incorporated additional baselines into our evaluation, including GIBBON [1], TS-RSR [2], DPP-TS [3], batch UCB [4], and qPI, as suggested by reviewers. These updates provide a more comprehensive empirical comparison, which demonstrates the competitive performance of qPO. Furthermore, we provided empirical results for cumulative regret and wall time comparisons. 

2. **Improved Clarity of Mathematical Exposition**: We clarified the mathematical exposition, including the definitions of $\textbf{x}$, $f$, and $y$, and provided additional insights into how qPO differs from existing methods such as qPI and qEI. We revised Section 2.2 and Algorithm 1 for clarity and updated the paper title to reflect the primary contribution more accurately. 

**Key Insights and Contributions**

1. **Theoretical Convergence Analysis Omission**: Several reviewers highlighted the lack of theoretical convergence guarantees. While we acknowledge this as a limitation, we argue that it is adequate to judge qPO based on empirical results, because:
     - Convergence guarantees for other algorithms usually depend on idealized assumptions which may not hold in practice. For example, bounds derived for TS-RSR [2] and pTS [5] utilize bounds derived by Srinivas et al [6], which assume $f$ either is sampled from a known Gaussian process or has a bounded norm in a known RKHS.
    - Convergence guarantees are almost always upper bounds, which may not be tight
    - These bounds are usually quite loose for small numbers of iterations, which is the scenario targeted by qPO

2. **Novel Acquisition Function**: The qPO method introduces a principled approach to batched Bayesian optimization by maximizing the probability of including the optimum. Despite being motivated by exploitation, this acquisition strategy exhibits explorative behavior by promoting diversity, without requiring myopic batch construction.

3. **Application-Specific Relevance**: The use of qPO in finite discrete domains, such as chemical library exploration, addresses practical challenges in molecular design. By optimizing for top-k performance rather than regret metrics, qPO aligns with the objectives of real-world applications.

We thank the reviewers for their time and insightful input, which have been invaluable in refining our work. We hope that these changes have addressed the concerns and improved your assessment of our contributions.

**Citations**

[1] Moss, H. B.; Leslie, D. S.; González, J.; Rayson, P. GIBBON: General-Purpose Information-Based Bayesian Optimisation. J. Mach. Learn. Res. 2021, 22 (1), 235:10616-235:10664.

[2] Ren, Z.; Li, N. TS-RSR: A Provably Efficient Approach for Batch Bayesian Optimization. arXiv 2024. arXiv:2403.04764.

[3] Nava, E.; Mutny, M.; Krause, A. Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics; PMLR, 2022; pp 7031–7054.

[4] Wilson, J. T.; Moriconi, R.; Hutter, F.; Deisenroth, M. P. The Reparameterization Trick for Acquisition Functions. arXiv. 2017. arXiv:1712.00424.

[5] Kandasamy, K.; Krishnamurthy, A.; Schneider, J.; Poczos, B. Parallelised Bayesian Optimisation via Thompson Sampling. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics; PMLR, 2018; pp 133–142.

[6] Srinivas, N.; Krause, A.; Kakade, S.; Seeger, M. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. In Proceedings of the 27th International Conference on International Conference on Machine Learning; ICML’10; Omnipress: Madison, WI, USA, 2010; pp 1015–1022.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Motivated by molecular design problems, where discrete designs (from some fixed database) can be evaluated in parallel, this work proposes an acquisition function for batch BO in discrete settings. Reviewers appreciate the simplicity of the approach, no reviewer advocated for acceptance, but provide encouraging remarks to revise and resubmit to another venue.

Some main areas of improvement include:

- Additional theoretical justification for the proposed AF. The authors pushed back in that such analysis would require assuming some particular known GP model classes, convergence would only be hold true asymptotically—whereas in BO we care about performance after a limited number of samples, etc. While I am personally not a fan of such proofs, such analysis is often expected by the community and can lead to insights.
- Clarity of exposition, motivation, and soundness of the proposed AF (see discussion with gD5x and concluding comments by PfuF)
- More conventional analysis. The authors consider only two test problems and empirical results on "unconventional metrics" (PfuF). While the authors note these are common to the molecule design community, the absence of simple regret wrt the best value found is missing. 
- Other real or synthetic benchmarks from the literature could also be included (8R9v; the authors argue that these problems are too lowD, but there are other common discrete optimization benchmarks out there). -More rigorous analysis of performance characteristics, such as how simple regret or top-k mean scales with batch size, and sensitivity to the number of MC samples (8R9v)

Reviewers provide numerous constructive critiques of the work, ideas on how to improve the algorithm, and relevant references. With these improvements, this work can be quite compelling.

A few notes from my own reading of the paper:

- The authors frequently use the term "myopic" or "non-additive" acquisition functions. [1] (the expanded version of the workshop paper by Wilson et. al cited throughout the work) shows how many AFs can be solved via a sequential greedy approach due to submodularity. It feels odd to refer to such greedy algorithms as myopic as they can be shown to approximate the full joint optimization problem. Adopting some more of that language could be helpful.
- Table 1 should report ± 1.96sem (the 95% interval). It would be helpful to highlight cases where methods provide the best result by putting them in bold (which may result in multiple methods being bold, if the difference is not stat sig, which is the case for a number of the methods for various metrics).
- Why is qEI missing from fig3? It appeared to be a top contender in Table 1.
- The authors should clearly define what "hallucination" means (as it is less commonly used)—essentially just sequentially conditioning on the mean value. It should be distinguished it from the use of "fantasies" in sequential greedy optimization MC variants of AFs, which is core to many of the results in [1]. This approach is utilized heavily in BoTorch's parallel AFs, including qPI and the various qEI variants. Such fantasization can also be used to implement smarter versions of TS (perhaps that is what pTS is?).
- In general it is unclear on whether the contribution of specific to discrete spaces, or would work for continuous or mixed spaces. -If the contribution is specific to discrete spaces, other discrete problems and choices of kernels could be helpful.
- [2] proposes an approach to solving similar problems that induces diversity in the input space. I have no idea how well it works in the smaller sample regime, but perhaps some of the baseline tasks or ways of reporting the results could be useful (and direct comparison could make the results more compelling)

[1] Maximizing acquisition functions for Bayesian optimization. Wilson, Hutter, Deisenroth, NeurIPS 2018.

[2] Discovering Many Diverse Solutions with Bayesian Optimization. Maus et al. AISTATS 2023.