Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design

Authors: Melis Ilayda Bal, Pier Giuseppe Sessa, Mojmir Mutny, Andreas Krause
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords: Combinatorial Bayesian Optimization, Game Theory, Gaussian Processes, Protein Design

Abstract:
Bayesian optimization (BO) is a powerful framework to optimize black-box expensive-to-evaluate functions via sequential interactions. In several important problems (e.g. drug discovery, circuit design, neural architecture search, etc.), though, such functions are defined over large $\textit{combinatorial and unstructured}$ spaces. This makes existing BO algorithms not feasible due to the intractable maximization of the acquisition function over these domains. To address this issue, we propose $\textbf{GameOpt}$, a novel game-theoretical approach to combinatorial BO. $\textbf{GameOpt}$ establishes a cooperative game between the different optimization variables, and selects points that are game $\textit{equilibria}$ of an upper confidence bound acquisition function. These are stable configurations from which no variable has an incentive to deviate$-$ analog to local optima in continuous domains. Crucially, this allows us to efficiently break down the complexity of the combinatorial domain into individual decision sets, making $\textbf{GameOpt}$ scalable to large combinatorial spaces. We demonstrate the application of $\textbf{GameOpt}$ to the challenging $\textit{protein design}$ problem and validate its performance on four real-world protein datasets. Each protein can take up to $20^{X}$ possible configurations, where $X$ is the length of a protein, making standard BO methods infeasible. Instead, our approach iteratively selects informative protein configurations and very quickly discovers highly active protein variants compared to other baselines.

Decision: accept (poster)
Reviewer scores: 8, 8, 3, 3

Reviews and discussion:
<thread>
creation date:
1729674179011

thread_type:
official_review

<thread_object>
creator: reviewer_xu81

<content>
summary:
This paper tackles scalability challenges in combinatorial black-box optimization tasks, specifically when each dimension contains the same number of discrete points. While this assumption is not universally applicable in combinatorial Bayesian optimization, it is relevant in specific domains, such as protein engineering. The authors introduce GameOpt, a novel approach that leverages the uniform structure of the discrete search space. By reframing the combinatorial optimization problem as an $n$-player cooperative game, the method aims to identify an $\epsilon$-Nash equilibrium at each iteration. This transformation enables the application of scalable solvers and polynomial-time equilibrium-finding techniques from game theory, offering a computationally efficient strategy for optimizing the acquisition function, particularly GP-UCB.

strengths:
- Large-scale combinatorial optimization is an important challenge, though Bayesian optimization (BO) may not be the most typical approach for tackling it.
- While theoretical analysis is provided for the convergence rate to an $\epsilon$-Nash equilibrium. However, it does not necessarily equate to finding the global optimum of the objective function, and the results are not significantly different from known results for existing game-theoretic BO literature.

weaknesses:
- **Clarity**
The weakest part of this paper is definitely the clarity, particularly in math. There are so many uncommon, unexplained, and undefined symbols, that make me frustrated. Detailed below:

**Problem Statement**.  What exactly is $x$? I initially understood it as a $d \times n$-dimensional variable. However, in Line 107, the statement "f(x) corresponds to --- the amino acid sequence $x$, and each $x$ can take $20^n$". I've lost. Is $x$ meant to be a $d$-dimensional variable or a  $d \times n$-dimensional variable? I also can’t interpret the meaning of "each $x$ can take $20^n$". Shouldn't $d = 20$ in this case? Additionally, the definition of the fitness function $f(x)$ is unclear. Is $f(x)$ defined for each discrete variable, or is it applied to the entire variable set? For example, if $x$ is assumed to be $d$-dimensional, does our objective function take the form $\prod_{i=1}^n f(x^{(i)})$? Or is $x$ actually $d \times n$-dimensional, and thus $f(x)$ refers to something else? I’ll proceed under the assumption that $x$ is $d \times n$-dimensional.

**Section 3**. I understand the reward $r^{(i)}$ here is the UCB defined for $x$ as a $d \times n$-dimensional input, and each player $i$ corresponds to one of the discrete variables. However, since UCB is defined on the entire $d \times n$-dimensional space, how can we apply UCB as $r^{(i)}$ then? How do you select the other $n-1$ variables? Or does $r^{(i)}: \mathcal{X} \rightarrow \mathbb{R}$ imply that each player takes a $d \times n$-dimensional input and $r^{(i)}$ = UCB for all $i$? If that is the case, and all players share the same utility function, why do equilibria arise? Wouldn't this reduce to the same optimal points for all players? Additionally, in Definition 3.1, $r^{(i)}$ takes two arguments, but this is supposed to be UCB. Why does UCB take two arguments? What is arg eq? What exactly does Eq (2) represent? I'm also confused by the explanation on Lines 172-173: "Intuitively, equilibria are computed by breaking down the complex decision space into individual decision sets." Could you precisely explain this process before jumping into the intuition? How is finding a Nash equilibrium equivalent to maximizing UCB? What is the payoff $v$ in Algorithms 2 and 3? I've lost again. 

I’ll stop pointing out specific issues here, but I want to note that the same level of confusion persists throughout the remaining sections (although the introduction was quite smooth).

- **Lack of Critical Guarantee**
Is finding a Nash equilibrium mathematically equivalent to maximizing the objective function $f$? If I understand correctly, this process is more akin to constructing a Pareto frontier, which contains the global maximum, making it more aligned with finding the set of local maxima. How, then, does this algorithm guarantee global convergence? If the goal of this work is local optimization or a heuristic approach, this should be clearly stated in the title or assumptions. Approximations can be valuable, but only if they provide some guarantee that they can recover the original problem under some conditions. Existing work, such as [1], provides such guarantees. I am not surprised that a local optimization algorithm finds local optima (as this work does) faster than a global optimizer (like [1]) in certain experiments, as they target different objectives. Even with these results, I wouldn’t choose this method for global optimization. When the function query is highly expensive, the computational overhead of the acquisition function becomes comparable. Moreover, [1] is not exactly state-of-the-art as it dates to 2022. There are likely more recent studies, such as [2], though performing a literature search is not my role here.
- **Limited Evaluation to Assess Practicality**
Heuristic approaches are completely acceptable if they prove useful in real-world applications. However, in that case, we expect the algorithm to be genuinely practical and perform best among existing heuristics. In the context of protein optimization, chemists would most likely start with deep learning-based approaches, especially diffusion-based methods, which are already well-established. There is a plethora of scalable and sample-efficient work in this area, such as [3, 4]. These methods seem like a more natural choice than using deep learning embeddings as features, as done in this work. Even with embeddings, the GP has no prior data on the objective function, meaning BO must start without a pretrained dataset. Alternatively, why not reduce the dimensionality of the embedding features to make them more tractable for the naïve GP-UCB? This could be achieved by adding just one additional layer to the transformer. In doing so, standard GP-UCB would likely perform just fine like popular latent BO doing. Since this paper does not compare its method against these popular alternatives or simpler alternatives, I cannot properly evaluate whether it represents a good heuristic. What I gather from this work is that it performs better than outdated methods on the limited tasks provided, but that alone does not demonstrate its superiority or practicality compared to modern approaches.
- **Limited Novelty**
The equation on line 295 appears nearly identical to the existing optimistic game-theoretic approach presented in [5], but it is not cited. Additionally, the idea of treating each discrete variable as a player is not particularly novel. For instance, Shapley value GP [6] and additive kernels [7] can be seen as variants of this concept (although they treat dimensions as players). While the specific combination of game theory, combinatorial optimization, and Bayesian optimization may be novel, it ultimately feels like a straightforward combination of existing approaches.
- **Missing Limitation**
I understand that this method leverages the problem structure where each dimension contains the same number of discrete variables, $n$. However, in typical combinatorial Bayesian Optimization, the goal is hyperparameter optimization, where each dimension may have a different number of categorical values, and the space can sometimes be a mixture of continuous and discrete variables. This method is not applicable to such cases. In mixed-variable scenarios, the existence of a Nash equilibrium cannot be guaranteed.

- **Citation**
- [1] Daulton, Samuel, et al. "Bayesian optimization over discrete and mixed spaces via probabilistic reparameterization."NeurIPS 2022
- [2] Papenmeier, Leonard, et al., "Bounce: reliable high-dimensional Bayesian optimization for combinatorial and mixed spaces." NeurIPS 2023
- [3] Gruver, Nate, et al. "Protein design with guided discrete diffusion." NeurIPS 2023
- [4] Campbell, Andrew, et al. "Generative flows on discrete state-spaces: Enabling multimodal flows with applications to protein co-design." arXiv preprint arXiv:2402.04997 (2024).
- [5] Han, Minbiao, et al., "No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes." UAI 2024.
- [6] Chau, Siu Lun, et al., "Explaining the uncertain: Stochastic shapley values for gaussian process models." NeurIPS 2023
- [7] Kandasamy, Kirthevasan, et al., "High dimensional Bayesian optimisation and bandits via additive models." ICML 2015.

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

</thread>
<thread>
creation date:
1730521750877

thread_type:
official_review

<thread_object>
creator: reviewer_mcjs

<content>
summary:
This paper studied the combinatorial Bayesian optimization in the discrete search space. Based on the theory of cooperative games and upper confidence bound of Gaussian processes (GPs), a new acquisition function that seeks to find the local equilibria of players was proposed. Based on batch and parallel computation, the proposed method achieved better scalability. The effectiveness and competitiveness were demonstrated in the application of computational protein design.

strengths:
1. The discrete black-box optimization problems are important, and the proposed game-theoretical solution seems novel.
2. The protein design is vital in drug discovery and healthcare.
3. The presentation is clear and the idea is easy-to-follow.

weaknesses:
1. There is no mechanism to avoid or mitigate stucking in local optimality. At the same time, as a Bayesian optimization method, the exploration-exploitation balance is not considered. As a preliminary solution, random restarts can be introduced into the search process, similar to what the trust-region Bayesian optimization algorithm does [1], to ensure exploration and global search ability. 
2. As local optima, the regret bound is not insightful enough to show the superiority. Currently, the regret is similar to what the original GP-UCB is, but only local optima are guarenteed. While the GP-UCB ensures global search and convergence. In my opinion, assuming convexity in the local region containing equilibria may help improve the theoretical results [2].
3. The testing benchmark problems are not diverse enough. Some well-known synthetic problems are required for fair comparison, espectially that employed in the state-of-the-art work.
4. The influence of hyper-parameters, especially the batch size B, is not clear. The baseline algorithms, especially the GP-UCB, are not tailored for batch optimization. It is recommended to consider smaller B, such as B=1, first. 
5. The literature review is insufficient. More baseline algorithms in combinatorial Bayesian optimization and general optimizers should be considered.

[1] David Eriksson, et al.: Scalable Global Optimization via Local Bayesian Optimization. NeurIPS 2019.

[2] Shuang Li, et al.: "Why Not Looking backward?" A Robust Two-Step Method to Automatically Terminate Bayesian Optimization. NeurIPS 2023.

questions:
1. Is there any consideration of balance of exploration and exploitation? How is the data-efficiency guaranteed?
2. What is the influence of batch size B? In what case may the algorithm perform worse?
3. Why not compared baselines using tree-based surrogate models. As far as I know, the tree model is a suitable choice for protein design.
4. How to prove that solving equation (2) is more tractable than solving other acquisition functions?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730665881860

thread_type:
official_review

<thread_object>
creator: reviewer_3y4p

<content>
summary:
This paper studies how to solve the combinatorial Bayesian optimization problem, which has many important potential applications like protein design. The key idea of this work is introducing the Nash equilibrium to Bayesian optimization, where a game is carefully designed for domain variables to play and the decision making is driven by equilibrium finding algorithms. It’s good to see substantial experiments in protein design in the end.

strengths:
1.	Combinatorial Bayesian optimization (CBO) is a very important subfield in Bayesian optimization. While Bayesian optimization has been successfully applied to many areas, studying CBO helps us solve even more practical application problems, like protein design.
2.	Sample complexity guarantees are provided to show the algorithm’s ability to achieve approximate Nash equilibrium.
3.	Experiments on protein design are comprehensive and ablation studies are provided.

weaknesses:
1.	To be honest, as a ML researcher, I have limited background in Nash equilibrium and I think it could be beneficial for this paper to provide more information on introducing Nash equilibrium since this is an ICLR submission. Although locally optimal, why and how does Nah equilibrium help in CBO setting? Could you provide a brief comparison between the local optimality of Nash equilibria and global optimality in the context of CBO. Can we design some globally optimal CBO algorithms or are the authors aware of such algorithms? Also, it might be hard to theoretically investigate the performance difference between GameOPT and the global optimal solution, it is feasible to investigate it in experiments where a small finite decision space is used. That would greatly provide valuable insights into the method's effectiveness.
2.	I have concerns on the computational efficiency of Step 5 of Algorithm 1. Because the GP is assumed on function f which is now defined on the combinatorial space, how do you find the top B equilibria according to UCB? Could you provide more details on how to implement this step efficiently, discuss the computational complexity of this step compared to the overall algorithm, and explain any approximations or heuristics that may be used if an exact solution is computationally infeasible?

questions:
1.	Does this algorithm work without assumption $|\mathcal{X}^{(i)}|=d$? It means that in this case the numbers of possible decision variables are different.
2.	What is the v function in Algorithm 2? Is that the r function defined in Definition 3.1?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730891073760

thread_type:
official_review

<thread_object>
creator: reviewer_vxgg

<content>
summary:
The paper proposes a novel method that frames the protein design task as an optimization problem of finding a Nash Equilibrium (NE) with unknown utility functions. It provides sample efficiency guarantees, and empirical results using multiple NE solvers suggest promising improvements over existing baselines.

strengths:
- ***Innovative Formulation***: The paper introduces an interesting formulation by shifting the focus from kernel design for protein structures to an objective that reflects the insight that multiple separate contributing factors exist within protein design tasks.

- ***Sample Efficiency Guarantee***: The algorithm comes with a sample efficiency guarantee, which is valuable for practical scientific experimental design tasks where data collection can be costly and demand a principled optimization solution.

weaknesses:
- ***Limited Novelty in BO Guarantees***: The Bayesian Optimization (BO) component naturally inherits the guarantees of the Upper Confidence Bound (UCB) algorithm. There doesn't appear to be a significant difference or improvement, especially considering that the method does not address specific challenges unique to protein design.
- ***Lack of Comparison with High-Dimensional BO Methods***: BO methods tackling protein design typically involve specific treatments for high-dimensional spaces. Including comparisons against these methods would strengthen the paper, especially when ESM embedding allows the direct application of such methods.

questions:
- ***Challenges in Finding Nash Equilibrium***: Given that finding a Nash Equilibrium is PPAD-complete and challenging even with state-of-the-art solvers, could the authors provide more insight and detailed discussion on optimizing the equilibrium for protein applications, especially in high-dimensional cases? The paper could better illustrate why the benefits of introducing the equilibrium outweigh the additional challenges rather than implying that solvers are guaranteed to find the NE. This clarification would prevent confusion among readers not familiar with the literature, especially since multiple NE solvers are discussed while claiming guarantees of finding local optima.

- ***Price of Anarchy Discussion***: The discussion of the price of anarchy briefly addresses the motivation for the problem formulation but is not sufficiently convincing. Providing more details and insights specific to protein design tasks could improve the presentation and strengthen the argument.

p.s. Due to my limited domain expertise, I am not confident in assessing the novelty of the problem formulation in this specific application.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732536507611

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We appreciate the reviewers' time, positive feedback, and constructive comments.

The reviewers highlighted the novelty of our approach (`“proposed game-theoretical solution seems novel”`and `“introduces an interesting formulation”` (VxGg, mcjS, XU81)), its computational efficiency (`“offering a computationally efficient strategy”` (XU81)), and the clarity of its presentation (`“presentation is clear and the idea is easy to follow”` (mcjS)). They also noted the sample efficiency analysis (`“algorithm comes with a sample efficiency guarantee”` (VxGg, 3y4p)) and extensive evaluations with ablation studies (`“comprehensive and ablation studies”` (3y4p)) on a critical real-world domain (`“protein design is vital”` (mcjS)).

In summary, our key contribution is GameOpt: a novel game-theoretical approach to combinatorial Bayesian optimization, enabling efficient and tractable acquisition function optimization in large combinatorial domains.

---
Considering the reviewer’s comments, we updated our manuscript (modified parts **highlighted in “red”**), with the following additions:
- **[Additional experiments with varying action set (dimension) sizes]:** GameOpt approach is applicable when each dimension $x^{(i)}$ (players) has  different action set ($\mathcal{X}^{(i)}$) sizes. To demonstrate this, we provide additional experiments in Appendix E12 on two problem domains. The results in Figure 17 clearly demonstrate the applicability and generalizability of GameOpt to problem domains with unequal action set (dimension) sizes.  We also modified our statement (line 104-105) in the main text to clarify this.

- **[Comparison with high-dimensional BO methods]:**  We further compare GameOpt against two high-dimensional BO methods [1,2] on a benchmark 25D-PestControl problem [3], with search space size 5^25. We provide this further analysis in Appendix E13 of the updated manuscript. This additional experiment clearly shows (see Figure 19) that GameOpt provides faster convergence to better solutions compared to these methods, supporting its integration with other high-dimensional methods and generalization to other combinatorial BO problem domains. 

- **[Additional problem domain]:** We further experiment on the benchmark 25D-PestControl problem [3], with search space size 5^25. As given in Appendix E13 of the updated manuscript, we apply the GameOpt approach to this additional problem domain, which clearly shows (see Figure 19) that GameOpt generalizes well to other problem domains, providing an outperforming performance. This further supports GameOpt's applicability in various combinatorial BO settings. 

- **[Batch size further ablations]:**  We also show the performance comparison under batch sizes $B=1$ and $B=3$ on Halogenase and GB1(4) domains, in Appendix-E7 of the updated manuscript. As shown in Figure-12, even under a more restricted setting on both problem domains, GameOpt variations achieve superior performance compared to the baselines. 

Once again, we sincerely thank all reviewers for their thoughtful and constructive comments, which have helped us improve the quality of our work.

---

> [1] Changyong Oh, Jakub Tomczak, Efstratios Gavves, and Max Welling. Combinatorial bayesian optimization using the graph cartesian product. Advances in Neural Information Processing Systems, 32, 2019.

> [2] Leonard Papenmeier, Luigi Nardi, and Matthias Poloczek. Bounce: Reliable high-dimensional bayesian optimization for combinatorial and mixed spaces. Advances in Neural Information Processing Systems, 36:1764–1793, 2023.

> [3] Aryan Deshwal, Sebastian Ament, Maximilian Balandat, Eytan Bakshy, Janardhan Rao Doppa, and David Eriksson. Bayesian optimization over high-dimensional combinatorial spaces via dictionary-based embeddings. In International Conference on Artificial Intelligence and Statistics, pp. 7021–7039. PMLR, 2023.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces GameOpt, a game-theoretical framework for combinatorial Bayesian optimization (CBO), with a focus on protein design. This work represents an innovative contribution by leveraging cooperative game theory to tackle scalability challenges in high-dimensional discrete optimization.

The main technical concerns from the reviewers revolves around the optimization gap between global/local optimum and Nash equilibrium, which I believe that the authors have addressed adequately. Some reviewers also noted the absence of comparisons with certain state-of-the-art methods, though the authors clarified the rationale behind their choice of baselines.

Overall, I believe this is a solid piece of work that could provide an alternative approach to the protein design community, and thus recommend acceptance.