Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design
Authors: Melis Ilayda Bal
Pier Giuseppe Sessa
Mojmir Mutny
Andreas Krause
Venue: ICLR 2025 Poster (2025)
Keywords: Combinatorial Bayesian Optimization
Game Theory
Gaussian Processes
Protein Design
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

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.

Published as a conference paper at ICLR 2025
OPTIMISTIC GAMES FOR COMBINATORIAL BAYESIAN OPTIMIZATION WITH A APPLICATION TO PROTEIN DESIGN
Melis layda Bal 1 Pier Giuseppe Sessa", Mojmír Mutny", Andreas Krause
1 Max Planck Institute for Intelligent Systems, Tübingen, Germany
Google DeepMind 'ETH Zürich
mbal@tuebingen mpg. , de, piergs@google.com
mmutny@inf wtw... ch, krausealethz..co
ABSTRACT
Bayesian optimization (BO) 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 funetions are defined over large 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 GAMEOPT, a novel game-theoretical approach to combinatorial BO. GAMEOPT establishes cooperative game between the different optimization variables, and selects points that are game 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 GAMEOPT scalable to large combinatorial spaces. We demonstrate the application of GAMEOPT to the challenging protein design problem and validate its performance four woal-world protein datasets. Each protein can take up to 20 possible configurations, where X is the length a protein, making standard BO methods infeasible. Instead, our approach iteratively selects informative protein configurations and very quickly discovers highly active protein variants compared other baselines.
INTRODUCTION
Many scientific and engineering problems such as drug discovery (Negoescu et al., 2011), neural architecture search (Kandasamy et al., 2018), or circuit design (Lyu et al., 2018) require optimization of expensive-to-eealluate black-box functions over combinatorial unstructured spaces involving binary, integer-valued, and categorical variables. As a concrete example, consider the protein design problem, i.e., finding the optimal amino acid sequence to maximize the functional capacity (fitness) of the protein. Such fitness functions are highly complex, one can, in most cases, only be elucidated from real-world protein synthesis experiments. Moreover, exhaustive exploration is infeasible for both traditional lab methods and computational techniques (Romero et al., 2013) due to combinatorial explosion: a typical protein has 300 amino acid sites, each to be filled with one of twenty natural amino acids, yielding 20300 candidate variants.
Bayesian optimization (BO) an established framework for optimizing black-box functions with the goal of minimizing the number of evaluations needed to certify optimality (Mockus, 1974). BO constructs a probabilistic surrogate model as a representation of the underlying black-box function, e.g., using Gaussian Processes (GPs) (Rasmussen et al., 2006). Then, it iteratively selects the next evaluations typically by maximizing a designated acquisition function. The BO franework has proven to be very powerful and successful in variety of real-world problems including material discovery (Frazier& & Wang, 2015), adaptive experimental design (Greenhill et al., 2020), or drug
"Corresponding author. Code is available httpt::///// //gi::///ite httpg/gtubbcco/////// i aadabal ganeopt.

---

Published as a conference paper at ICLR 2025
EQUILIBRIUM
ROUNDS
k- K.K
Player2
4ayer
GAME
X EQUILIBRIUM
Figure 1: Illustration of GAMEOPT. GAMEOPT defines a game among the decision variables, where game rewards are represented by the upper confidence bound (UCB) function. This decouples the combinatorial decision space into individual decision sets and allows GAMEOPT to tractably compute game equilibria. These can be thought of as local optima of the AF in unstructured domains.
discovery (Korovina al., 2020; Stanton al., 2022). When considering combinatorial domains, however, standard BO methods are intractable since maximizing the acquisition function requires an exhaustive search over the whole combinatorial space (e.g. of size 20300 in the context of proteins) without further assumptions.
To address this challenge, we propose GAMEÔPT, novel game-theoretical framework for combina- torial BO. To circumvent the intractable maximization of an acquisition function, GAMEOPT defines cooperative game between the discrete domain variables and, at each interaction round, selects informative points to be game equilibria of the acquisition function. These are stable configurations from which no player (variable) has the incentive deviate. They can be thought of a formalization of notion of local optima of the acquisition function in unstructured domains (i.e., domains lacking a lattice structure). Crucially, these can be computed employing well-known equilibrium finding subroutines, effectively simulating a repeated game among the players. In this work, we utilize the Upper Confidence Bound (UCB) acquisition function, which represents an optimistic estimate the underlying objective and was shown efficiently balance exploration with exploitation (Srinivas et al., 2009). For an overview of the method, see Figure 1.
Contributions We make the following main contributions:
We propose GAMEOPT, novel chne-thhoretical BO framework for large combinatorial and unstructured search spaces. GAMEOPT computes informative evaluation points as the equilibria (i.e., local optima) of cooperative game between the discrete variables. This overcomes the scalability issues of maximizing acquisition functions over combinatorial domains and provides a tractable optimization. GAMEOPT is flexible procedure where the resulting per-iteration game can be solved by any readily available game strategy or solver.
Under common kernel regularity assumptions, quantifying the gap between the computed equilibria (of the surrogate UCB function) and those of the underlying unknown objective. Given target accuracy level c, GAMEOPT returns e-approximate equilibria after T = M(TTE" iterations, where "T is the kemeeldeeendent maximum information gain (Srinivas et al., 2009).
bound the sample complexity of GAMEOPT,
We apply GAMEOPT to the challenging protein design problem, involving search spaces of categorical inputs. There, GAMBOPT advances the protein design process by mimicking natural evolution via game between protein sites. We experimentally validate its performance several world protein design problems based on human binding protein GB1 (Wu et al., 2016; Olson al., 2014), iron-dependent halogenase (Büchler al., 2022) and freen-fluorescent protein (Prasher et al., 1992; Biswas et al., 2021). GAMEOPT converges consistently faster, iee., requires fewer BO iterations to identify highly binding protein variants compared to baseline methods such as classical directed evolution.
2 PROBLEM STATEMENT AND BACKGROUND
Problem statement We consider the problem of optimizing -oselltt--evaluate, black-box function f: X + IR over a combinatorial unstructured space X' without a lattice form. Suppose each element X can be represented by n discrete variables (x x² ....,." x") (n-dimensional), where each oe takes values from set (4) this makes the domain of 2 1 variables X' (1) (m))
2

---

Published as a conference paper at ICLR 2025
Algorithm 1 GAMBOPT
1: Input: GP prior GPD (mo, k).,)), initial data Do = {(21,)) y/ = fxx) + c)}. batch size N.
M E N > B, parameter B.
2: for iteration t = 1, .2....,' do
3: Construct game with reward function UCB(GP'-1 B,
-T= X - R
4: Compute M equilibria { of the above.
*/ Equilibrium grquiibbrummfinding subroutine */ Filtering
5: Select batch of top B equilibria ( according to UCB(GP'-1, ,,,)).
6: Obtain evaluations Vt, = f(F,,) Er, Vi I...., B
7: Update D. + D U {(Tr. Ve.5),
8: Posterior update of model GP with Dz.
9: end for
Assuming | = d, Vi, the size of the combinatorial space X' is d However, the proposed
GAMEOPT framework can also operate under varying [x()) sizes, as we detail in Appendix E.7.
As concrete motivating example, consider the protein design problem (Section 5). There, f(x) represents the fitmess value of the designed protein sequence æ. The search space size is | = 20",
with n protein sites and [x](0] = 20 amino acid choices per site. Moreover, a (noisy) evaluation fx) a labor-intensive process, requiring extensive efforts and specialized laboratory equipment.
Gaussian Processes (GPs) Bayesian Optimization (Mockus, 1974) is a versatile framework for optimizing complex, noisy, and expensive-to-evaluate functions. BO leverages Bayesian inference to model the underlying function with surrogate, e.g. a Gaussian Process (GP) and iteratively selects evaluation points that are the most informative in terms reducing uncertainty or enhancing model performance.
Formally, Gaussian Process (P(u(-),k(:))) over domain X' is specified by a prior mean function p(z) X R and covariance function k(x,, x') X' x X - IR, denoted by f(x) ~ GP(p(z), (,,,,,((, x'), where f(x) represents the function value at input x.
Given set of observed data points X, up iteration t and their corresponding vector of noisy observations Yú f(x)) + e with Gaussian noise G, ~ [N0,, of), and a GP prior defined by GP(u (1),, (x,,, the posterior distribution of the GP at iteration [ + 1 given new observa- tions X₁ is again Gaussian p(f++1 X,, X,, Y,) = N(u+1,, of41) with posterior mean and variance (Rasmussen al., 2006).
Bayesian Optimization (BO) To maximize f. BO algorithms iteratively select evaluation points so as to balance exploration and exploitation. At each iteration the method selects the maximizer of an acquisitiin function, for example, the widely-adopted Upper-Confidenee Bound (UCB) (Srinivas et al., 2009) function. Given GP model at iteration f, the UCB function is defined as
UCB .)) = (x) + (z)r(x),
where uxx) and (2) are the posterior mean and standard deviation at point æ according to GP, and 3e a confidence parameter influencing the width of the set that can be selected to ensure the validity of the confidence set. The UCB function defines an optimistic estimate of the underlying objective f. and can effectively balance exploration (i.e., favoring points with large uncertainty (1))) with exploitation (i.e., selecting points with large posterior mean μ4 (x)).
While standard BO methods can efficiently optimize UCB(GP.-) in efficiently enumerable or continuous domains, they become very soon intractable in the case of combinatorial unstructured domains, such as the space of possible amino acid sequences. In the next section, we propose GAMEOPT, novel BO approach that circumvents such prohibitive difficulty.
GAMEOPT ALGORITHM
In a nutshell, the proposed GAMEOPT (Optimistic Games) approach circumvents the combinatorial optimization of the UCB function by defining cooperative game among the input variables and computes the associated equilibria as candidate evaluation points. Formally, at each iteration GAMEOPT defines cooperative game (Fudenberg & Tirole, 1991) involving A =1,...,,1)
3

---

Published as a conference paper at ICLR 2025
players, each player i taking actions in the discrete set X00 In such a game, the players' interests are aligned towards the goal of maximizing the function UCB(GP', GP' is the current GP estimate iteration t. Thus, it can be interpreted as optimistic game with respect to the true unknown f. In such a game, the goal of the players is to compute game (Nash) equilibria, defined follows.
IT= x²() - R, where
Definition 3.1 (Nash equilibrium (Nash, 1951)), Let r² X + R be the reward function of each player i, defined over joint configuration æ. A joint strategy profile Zeg = (zeq...., ( is a Nash equilibrium if, for every player i E .V, (" "ea") 2 r'(a", =ma), Va E x(10) where Feqq
(#éq- = and øzq is the joint equilibrium strategy of all players except
The existence of such equilibrium point(s) is guaranteed since players and actions finite (Fu- denberg & Tirole, 1991). Moreover, because players' reward functions are aligned and coincide with UCB(GP', efficient polynomial-tima equilibriun-fiddin methods can be employed, such as Iterative Best-Response (IBR), where players update their actions sequentially, or simultancous multiplicative weights updates such as the HEDGE (Freund & Schapire, 1997) algorithm. We report these two possible strategies in Algorithms 2 and 3 in Section 3.1. Intuitively, equilibria are computed by breaking down the complex decision space into individual decision sets, as illustrated in Figure 1. Mathematically, we refer to this operation as arg eq, returns the joint configuration(s) which form equílibria according to UCB,
Fey arg C200E UCB(GP', (1") (x"....,."")
Our overall approach is summarized in Algorithm 1. In practice, we compute M > equilibria and subselect a batch of top < M equilibria according to the UCB(GP', criterion. Subsequently, such batch is evaluated by f. the GP model is updated accordingly, and a new game with an updated reward function is defined at the next iteration based on the updated posterior.
A form of local optimality Within GAMEOPT, each player strategically selects actions to maximize their collective payoff, much like seeking local optima in continuous multi-dimensional function (see Figure 1). In continuous optimization, a local optimum is a point, where there is no direction that leads to an improvement, similarly, in our framework there is not player that can unilaterally improve the value of the collective pay-off. In essence, seeking equilibria is analogous to seeking local optima of continuous acquisition function, and game- based approach allows us to effectively pinpoint them within an unstructured combinatorial space. We remark that GAMEOPT computes equilibria of the current UCB(GP', function which, and better approximations of equílibria of the unknown objective ʃ.
show in Section 5, are better
Price of Anarchy But how good are equilibria compared to the global optimum? The quality of equilibria (also known as the efficiency of the game) can be quantified via the game-theoretic notion of Price of Anarchy (PoA) (Christodoulou & Koutsoupias, 2005), defined as the ratio between the worst equilibrium and the global optimum, i.e., PoA := minxer /xxx//mxx// f(x) where E is the set of all equílibria of f. PoA has been extensively studied for various classes of games and can sometimes be upper-bounded given further assumptions on f. As an example, in case f is a submodular function (over binary, integer, continuous domains), PoA is guaranteed to be at least 0.5 (Vetta, 2002; Sessa et al.. 2019b). Although such a PoA guarantee does not readily apply to our setting, we believe similar ones could be proved for the case of unstructured domains of our work. In practice, given an unknown function f (such as the protein's 's fitness function in our experiments of Section 5), not all equilibria may achieve high function values (i.e. Рoλ can be very low). Nevertheless, GAMBOPT computes multiple equilibria (M > 1) at each iteration and selects only the top B according their UCB value. We believe this is key form of robustness that can effectively filter out suboptimal equilibria and empower GAMEOPT's experimental performance.
though this is beyond the scope
3.1 EQUILIBRIUM FINDING SURROUTINES
We present set of established algorithms for finding an equilibrium of the game introduced in Eq. (2).
Iterative best responses One possible subroutine for Algorithm 1 is Iterative Best Response (IBR) procedure provided in Algorithm 2. Concretely, under the cooperative game setting outlined in Section 3 and given PP-predicted UCB function, each player iteratively selects the response that maximizes the value of the game given that the other players play the joint strategy from the previous
4

---

Published as a conference paper at ICLR 2025
Algorithm 2 Iterative Best Response (IBR)
Algorithm Simultancous HEDGE
1: Input: Domain X, payoff (reward) x + R. players N.
1: Imput: Domain X' = I 2:00 with | 22 |=
W, payoff r X + R. players NG parameter 7).
2: X f- raandom joint strategy, x E X.
2: Initialize weights w1 f- w ,..... 1] E R
3: for round k = l..... K do */ BR game
3: for round L..... do
*/ Compute CCE
4: A { (xthrr xx-1), ) such that
Sample 2 - wi, Vi E .
Set joint strategy Xx < {at (akiie $/ Players payoff
x xt.br arg max r(z, 2x 1,br zEN(O
i=1 5: Play xbr + arg max ( [r(xx)]
6:
for player i E do
7:
F, + [r( "
where
Ex
6: end for
Tk J. --- = HrEN x Set w wi exp(nex,))
7: return xbr
Equilibrium
8:
end for 10: end for
11: return Uniform xx)
*/ Equilibriu
round. Each player is sequentially selected to play their best response in a round-robin fashion. Because action space is finite, this procedure is guaranteed to converge to a local maximum of the UCB function i.e., an equilibrium of the underlying game (Fudenberg & Tirole, 1991).
Multiplicative weights updates Alternativlly, we can compute game equilibria letting players simultaneously act according to a multiplicative weights update algorithm such HEDGE (Freund & Schapire, 1997), see Algorithm We can cast equilibrium computation as an instance of adversarial online learning among multiple learners (Cesa-Bianch) & Lugosi, 2006). Here, each player selects a strategy based on their available options and, after observing the joint payoff, players' strategies re- re-weighted based on past performance. Through repeated rounds of play and re- weightingg, the empirical frequency of play forms a coarse correlated equilibrium (CCE) (a weaker notion of Nash equilibrium), see c.g. (Cesa-Bianchi & Lugosi, 2006), while convergence pure Nash equilibria is also guaranteed in some cases (Kleinberg et al., 2009; Palaiopanos et al., 2017).
3.2 RELATED WORK
While there exist rather few works in the area (Papenmeier et al., 2023), existing combinatorial BO methods either target surrogate modeling with discrete variables (Baptista & Poloczek, 2018; Oh al., 2019; Garrido-Merchán Hernández-Lood Lobato, 2020; Kim et al., 2021; Deshwal et al., 2023) or optimizing acquisition function within discrete spaces (Baptista & Poloczek, 2018; Deshwal et al., 2020; la;b;;;; Khan et al., 2023). However, they often require a parametric surrogate model with higher-order interaction specifications for combinatorial structures (Baptista & Poloczek, 2018) or domain-specifie knowledge (Deshwal et al., 2020). In contrast, GAMEOPT relies on a paramermttiic surrogate model, without the need for Nomain-speciff knowledge.
Closest to ours is (Daulton et al., 2022), which also targets optimizing the acquisition function in high-cardinality discrete/mixed search spaces via probabilistic reparameterization (PR) that maximizes the expectation of the acquisition function. However, PR fails at being tractable since requires evaluating the expectation over the joint distribution of all decision variables, requiring combinatorially many elements to be summed. An accurate estimate would require extensive sampling without special structural assumptions. In contrast, GAMEOPT treats each variable independently (potentially in parallel) within the game, keeping the values of the remaining variables fixed during each strategy update. We use PR as baseline evaluate our approach in Section 5, and demonstrate improved performance of our method on protein design problems.
Further, a body of research has focused on BO over continuous (latent) spaces (Gómez-Bombane et al., 2018: Eriksson et al., 2019; Tripp et al., 2020; Deshwal & Doppa, 2021; Maus et al., 2022; Stanton et al., 2022: Zhang et al., 2023). These methods learn continuous sequence embeddings and optimize with gradient-based techniques by utilizing deep generative models. However, the primary problem we address in our study is the intractable acquisition function optimization over large combinatorial search spaces, specifically tackling the challenge of exhaustive exploration. In line with this, we select our baselines accordingly and include a comparison with some latent space optimizers only additional experimental evaluation for insight.
5

---

Published as a conference paper at ICLR 2025
Recently, line of works has explored the interplay between BO & game theory (Sessa al., 2019a; Dadkhahi et al., 2020; Han et al., 2024), and coordinated exploration (Sessa et al., 2022; Bal et al., 2024) for various domains, but their connection with combinatorial BO is novel.
4 HAMPLE-COMPLEDT
GUARANTEES
In this section, we derive sample-complexity guarantees for GAMEOPT. Namely, we characterize the number of interaction rounds T required to reach approximate equilibria (/.e., local optima) of the true function f. For simplicity, we assume GAMEOPT is run with batch size B = 1, though our results can generalized to larger B.
The obtained guarantees are based on standard regret bounds of Bayesian optimization adapted to our equilibrium finding goal. These are characterized by the widely utilized notion of maximum information gain (Srinivas et al., 2009):
2 log + 1 [
This is a kernel-dependent (K;) quantity that quantifies the maximal uncertainty reduction about after t observations. Further, to characterize our sample complexity, we define the notion of e-approximate Nash equilibrium.
Definition 4.1 (e-approximate Nash equilibrium), A strategy profile Zog is e-approximate (Nash) equilibrium of f if, for each i N. 2 (()) Vx E 2(0)
In the next main theorem, we provide a lower bound on the number of iterations T to reach approxi- mate equilibria. After rounds, we assume GAMEOPT returns Z7. with:
T == arg min max [UCB(GP', xt (T))) LCB(GP' BE(T) 1,2
where LCB is the lower confidence bound function LCB x)) = (t( ( That is, among the selected points -1,-.., UT, TT is the that guarantees the minimum worst-case single-player deviation. The deviation above is computed according to the UCB and with respect to the LCB, thus representing an upper bound the actual deviation in terms of f. We can affirm the following.
Theorem 4.2 (Sample complexity of GAMBOPT). Assume f satisfies the regularity assumptions of Section 2, and GAMEOPT is run with confidence width B, 2n log (sUPLEN |X |
60 Then, with
probability at least 1 and for a given accuracy e 2 0, the strategy VT. returned by GAMEOPT is e-approximate Nash equilibrium when
BrTr
T2 Ω
An equivalent interpretation of the above result is as follows: After iterations, GAMEOPT returns an ap-apoooee Nash equilibrium ff with approximation factor éT S O à BTTT). Note that the latter bound is the typical rate of convergence of BO algorithms (Srinivas et al., 2009) to the global maximizer. Instead, our combinatorial BO setup -where global optimization is intractable- corresponds to the rate of convergence to equilibria. A more explicit convergence guarantee obtained by employing existing bounds for "r which are known for commonly used kernels (Srinivas al., 2009). E.g., for squared exponential kernels PT (l) where d is the dimension of each input space (0))) for each player i E.W, with [ n.
be
5 APPLICATION TO PROTEIN DESIGN
In this section, we specialize the GAMEOPT framework to protein design, problem defined over the space of possible amino acid sequences. Note that such domains are highly combinatorial (their size grows exponentially with the sequence length) and unstructured (i.e. they lack lattice structure). In this context, computing game equilibria follows the natural principle of promoting beneficial mutants and mirrors the proteins' mutation and selection process. In Algorithms 4 and (Appendix B), provide a detailed elaboration of GAMEOPT for protein design using cocllibrium-fiddiiie methods. We showcase its performance in four real-world protein datasets.

---

Published as a conference paper at ICLR 2025
In the protein design context, GAMEOPT establishes a cooperative game among the different protein sites E {l...., n). where n is the length of the protein sequence. Each site chooses an amino acid from the set with | x²() |= 20, where the switching between amino acid choices can be thought of as biological mutation. The joint objective of the players is to converge to highly rewarding protein sequence, as measured by the GP- -reprricceed optimistic score for the fitness function. This mirrors the selection phase in evolutionary search, providing a directed approach protein optimization. Below, we discuss related work in the area.
Related work on evolutionary search. A considerable line of works (Arnold, 1998; Hansen, 2006; Romero & Arnold, 2009; Yang et al., 2019; Deshwal et al., 2020: Cheng et al.. 2022; Low et al., 2023) centers around evolutionary search algorithms for optimizing black-box functions. Within combinatorial amino-acid sequence spaces, the highly regarded technique, directed evolution (Arolld, 1998; Romero & Arnold, 2009), draws inspiration from natural evolution and identifies local optima through a series of repeated random searches, characterized by controlled iterative cycles of mutation and selection. Expanding upon this, machine carring--gudeed variants (Yang et al., 2019; Wittmann et al., 2021; Romero et al., 2013; Angermueller et al., 2020) mitigate the sample-inefficiency and intractability concerns associated with directed evolution. In general, these methods not data-driven in the sense that they do not the whole extent of the past data and focus on the best variant found so far or a selection thereof and propose a random search from thereon. Alternatively, even if allowed adapt the past outcomes, they tend restrict themselves to very small search spaces (Büchler et al., 2022). Instead, our approach uses all past data to create UCB estimate of the fitness landscape and utilize it simulate a cooperative evolution in problems where even the whole sequence of the protein can be optimized. Moreover, compared to such methods, GAMEOPT mimics evolution within each interaction using the surrogate UCB function.
5.1 DATASETS
We empirically evaluate GAMEOPT on real-world protein design problems, specifically focusing on the following instances: protein G domain B1, GBI, binding affinity to an antibody IgG-FC (KA), examined on two distinct datasets, GBI(4) (Wu et al., 2016) and GB1(55) (Olson et al.. 2014), characterized by sequence lengths of 4 and 55, respectively; three critical amino acid positions in an
halogenase with sequence length (Büchler et al., 2022); and Aequorea victoria green-fluorescent protein (GFP) of length 238 (Prasher et al., 1992; Biswas et al.,
2021). The former GBI dataset is fully combinatorial, i.e., covering fitness measurements of 204 variants. Here, each protein site is treated including only 2-point mutations of GBI. Thus, an MLP having R = 0.93 on a test set is trained and treated the ground truth fitness for the fully combinatorial dataset. For GBI(55), we also consider a modified setup where "only" 10 sites can be mutated. Similarly, Halogenase and GFP are also non-exhaustive involving fitness measurements for 605 and 35, 584 unique variants, respectively. To obtain the complete protein fitness landscape, we once again construct oracles for these datasets, utilizing MLPs achieving Rt2 0.96 and Ri2 0.90 on their respective test sets. In the case of the Halogenase dataset, each protein site is treated as a player, while for the GFP dataset, 6 and 8 sites are designated as players. Further experimental details are in Appendix D.
player in the GAMEOPT. The latter is non-exhaustive,
5.2 EXPERIMENTAL SETUP
In all experiments, we use a GP surrogate with an RBF kernel for GP-based methods. The RBF specifies lengthscales for each input variable separately sometimes known as ARD kernels (Rasmussen al.. 2006). To handle categorical inputs the GP surrogate, we employ feature embeddings as representations for these inputs using the ESM-Iv transformer protein language model by (Meier et al., 2021). The prior mean for the GP is pre-defined as the average log fitness value over the whole dataset. Kernel hyperparameters are optimized prior to the start of optimization and remain fixed throughout the BO iterations; specifically, lengthscales are optimized over the training set at the start of each replication using Bayesian evidence, and the outputscale is fixed to the difference between the maximum fitness value observed in the dataset & mean. In other words, we also fit prior mean. A consistent observation noise of 0.0004 is maintained for each training example. Moreover, we use batch size B = 5. In Appendix D, we provide the (hyper)paramettr settings (see Table 1) and the detailed setup for the experiments.
7

---

Published as a conference paper at ICLR 2025
LogFiiness (best so lai)
LogFstness (best so far)
Log LogFllness (best so far)
23
2.
13
1.
0.
5.6
Iterations
Iterations
Rerations
(a) Halogenase, 3. 18 reps.
(b) GBI(4). 4, 18 reps.
(c) GFP, nI 6, 10 reps.
LogFiiness (best Iar)
Logeitness (best far)
Logeilness (best so far)
0.4
6.
5.4
3.5
Dterations
berations
[terations
(d) GFP, 10 reps.
GBI(55),
10, 10 reps.
(f) GBI(55), 55, 10 reps.
GameOpt-1BR
Hedeopt-Hodge
IBR-Fitoess
PR
GRUCR
Random
Best, strategy
Figure 2: Convergence speed methods in terms of log fitness value of the best-so-far protein across BO iterations, under batch size B = 5. Results are averaged over replications initiated with different training sets: 100 protein variants for Halogenase and GBI(4), and 1000 protein variants for other domains. Error bars interquartile ranges averaged over replications. In all experiments GAMEOPT with IBR and HEDGE subroutines discover better protein sequences at a much faster rate.
5.3 BASELINES
We benchmark GAMEOPT against the following baselines:
1. GP-UCB (Srinivas et al., 2009) selecting at each iteration- the best B points in terms of UCB value. Note that this is feasible (though computationally expensive) only for the GBI(4) and Halogenase datasets, while it is prohibitive for GB(55) and GFP
2. IBR-FITNESS, which mimics directed evolution (Arnold, 1998) through series of local searches on the fitness landscape, iteratively selecting the B best-responses based on log fitness criterion
3. PR (Daulton al., 2022), -fate-of-le the-art discrete/mixed BO approach picking B points using the expected UCB criterion
RANDOM baseline randomly sampling random sequences at each iteration.
Further details and pseudo codes of such baselines are in Appendix C.
We assess our method using two key metrics: convergence speed and sampled batch diversity w.r.t. past, (i.e., the degree of distinctiveness among newly acquired samples in comparison the original data point particularly in the context of the input space) for BO evaluation. The latter can also be regarded as the measure exploration. Convergence speed tracked by the log fitness value of the best-so-far discovered protein variant across BO iterations. We monitor the diversity of the sampled batch concerning the past across BO iterations through (1) the average Hamming distance between the executed variant and the proposed variant from the previous iteration (pairwise distance) and (2) the average Hamming distance of the executed variant from the nearest initial training point.
In Appendix E, we provide additional performance metrics such as the fraction of global optima discovered, the fraction discovered solutions above fitness threshold, cumulative maximum, and mean pairwise Hamming distances. Moreover, compare with discrete local search methods (Ba- landat et al., 2020) Appendix E.3 and report their respective runtimes in Appendix E.4.
5.4 RESULTS
GAMEOPT, with IBR and HEDGE equilibrium computation subroutines, consistently outperform baselines across all experiments, discovering higher fitness protein sequences faster (see Figure 2).
Results for Halogenase. While initially surpassed by FBR-FITNESS, PR, and GP-UCB, GAMEOPT variants converge faster to higher log fitness proteins than baselines. Notably, IBR-FITNESS performs
8

---

Published as a conference paper at ICLR 2025
Avg. Pairwise Hamming Distance
Avg. Pairwise Hamming Distance
Avg. Pairwise Hamming Distance
Tteratinns
Itonttons
Barations
(a) Halogenase, 18 reps.
(b) GBI(4), 4. 18 reps.
(c) GFP, 6, 10 reps.
Avg. Pairwise Hamming Distanoe
Avg. Pairwise Hamming Distanoe
Avg. Pairwise Hamming Distance
10
10
40
10
22
40
(d) GFP, n 8, 10 reps.
(c) GBI(55), n 10, 10 reps.
(f) GBI(55), n 55, 10 reps.
CameOpt-1BR
Hedeop
IBR-Fitess
GRUCB
Random
strategy
Figure 3: Sampled batch diversity relative to past, measured via mean Hamming distance between executed and proposed variants from the previous iteration (pairwise distance), under batch size B Results averaged over replications, and error bars show interquartile ranges. In all experiments GAMEOPT consistently samples a rather diverse batch of evaluation points w.r.t. past proposed variants. This enhanced exploration of the search space contributes its strong performance compared to the baseline methods.
best-responses on the true log fitness function, whereas GAMEOPT-IBR simulates best-response dynamics directly the UCB model, allowing to compute equilibria at each iteration. Additionally, although GP-UCB performs comparably. it incurs higher computational demands. Furthermore, PR and RANDOM perform poorly in the Halogenase setting.
Results for GBI(4). Similarly, GAMEOPT approaches steadily surpass PR and GP-UCB while exploring superior protein sequences efficiently. Initially trailing IBR-FITNESS, GAMEOPT approaches prove more adept at exploring and sampling diverse points (see Figure 4 in Appendix E).
The baseline PR is very competitive and also comes with higher computational demands. As highlighted in Section 3.2, PR relies on the expected UCB as the acquisition function, requiring expectation computation across players and amino acid choices. This makes its performance contingent on accurately estimating expected UCB through combinatorially many sequence samples. In contrast, GAMEOPT efficiently finds stable outcomes by breaking down the combinatorial search space into individual decision sets, resulting in a more manageable process.
Finally, of particular observation the subpar performance of GP-UCB and RANDOM. A detailed analysis of GP-UCB's 'ss performance is presented in Appendix E.2, where it is observed that the efficacy GP-UCB heavily relies on the quality the initial GP surrogate. contrast, GAMEOPT demonstrates robustness in overcoming the limitations of model initialized with limited amount of data, thereby enhancing its sample efficiency. Further discussion on the performance of methods can be found in Appendix E.
Results for GFP. The complexity the problem positively correlates with the performance gap between GAMEOPT and baselines. In the protein search space with 6 and 8 amino acid decisions, GAMEOPT with either subroutine excels in identifying high-log fitness protein sequences even from the start. Figure 3 further demonstrates GAMEOPT's consistent exploration of diverse batches and Figure in Appendix F. shows its high rate of exploration.
Results for GB1(55). In both versions of the most complex problem domain, GAMEOPT demonstrates superior performance. As the decision flexibility (i.e., the number of players) increases from 10 to 55, the performance gap against baselines widens. Furthermore, GAMEOPT achieves incomparable batch diversity concerning past, both with respect to the initial training and previously executed protein sequences, shown in Figures and 4 in Appendix E.

---

Published as a conference paper at ICLR 2025
5.5 FURTHER DISCUSSION AND LIMITATIONS
In our experiments, we compare to IBR- FITTISS which simulates currently employed strategies in the iterative protein optimization literature. This by no means the only methodology applied in this field, and comprehensive comparison is beyond the scope of this work.
Batch size. Similar to the previous point, in the experiments presented in Section 5.4, we use batch size of B = 5. While we acknowledge this a restrictive setup given the technological needs of common screenings, nevertheless, batch size which differs to each laboratory setting. To support this, we include batch size ablations, B {1, 3, 5, 10, 50), in Appendix E.8 (Figure 12), demonstrating that GAMEOPT variations consis- tently outperform baseline methods in discovering better protein sequences across various batch sizes.
results should be transferable and applicable irrespective of the
Learning rate. In Appendix E.9, we detail learning rate ablations for GAMEOPT-HEDGE.
Efficient vs better optimization of the acquisition function. The primary benefit of GAMEOPT is its ability to efficiently optimize the acquisition function by adopting a game-theoretical perspective. Unlike GP-UCB, our focus is on tractable optimization in large combinatorial spaces rather than improving optimization. This efficiency is vital for navigating such spaces, where GAMEOPT exploits game equilibria enhance exploration. Appendix E. 10 (see Figure 15) provides an analysis of UCB values over BO iterations. While GAMEOPT is initially outperformed by GP-UCB in collecting higher UCB-valued batches, its exploration strategy ultimately leads to more efficient optimization.
Different acquisition functions. We design the GAMEOPT framework using UCB as the acquisition function (also the game reward function), with its sample complexity derived accordingly. To assess broader applicability, we also evaluate GAMEOPT with alternative acquisition functions, such as expected improvement (Jones et al., 1998). As shown in Appendix E.11, Figure 16, our empirical comparison with GP-based methods reveals that GAMEOPT consistently outperforms these baselines across all performance metrics.
Comparison with latent space optimizers. In line with the primary focus of this study, compare GAMEOPT to baselines that employ acquisition function optimizers operating directly on large combinatorial search spaces (Dreczkowski et al.. 2024), addressing the challenge of exhaustive exploration. As discussed in Section 3.2, another line of work follows BO over continuous spaces by learning latent representation via deep generative models. While comprehensive comparison with these methods is beyond our scope, we provide additional insights in Appendix E. 12, where we empirically compare GAMEOPT against Naive LSBO-(L-BFGS) using second-order gradient-based optimizer, and LADDER (Deshwal & Doppa, 2021). The results highlight GAMEOPT's effectiveness- not only in finding higher-fitness sequences tractably but also in bypassing the limitations of latent space optimizers, particularly their dependency decoder.
(66mez-BBomaree et al., 2018),
Sequence-based kernels. To show the applicability of GAMEOPT under various kernel choices, we provide additional analysis using string kernels (Moss et al., 2020) in Appendix 12. Specifically, we consider structure-coupled kernel designed by combining an RBF kernel with a sub-sequence string kernel (Moss et al., 2020). In this setting, GAMEOPT demonstrates faster convergence to higher log fitness protein sequences, further emphasizing its adaptability across different kernel configurations.
6 CONCLUSIONS
We introduced GAMEOPT, novel tractable game-theoretical approach to combinatorial BO that leverages game equilibria of a cooperative game between discrete inputs of a costly-to-evallate black-box function to tractably optimize the acquisition function over combinatorial and unstructured spaces, and select informative points. Empirical analysis on challenging protein design problems showed that GAMEOPT surpassed baselines in terms of convergence speed, consistently identifying better protein variants more quickly, thereby being more resource-efficien GAMEOPT is versatile framework, allowing for exploration with different acquisition functions or mixed equilibrium concepts. As for future work, adaptive grouping of players could be further investigated.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
MIB acknowledges the support of the Max Planck Graduate Center for Computer and Information Science. The preliminary experiments made possible through the support of the Max Planck Institute for Software Systems compute cluster.
REFERENCES
Christof Angermueller, David Belanger, Andreea Gane, Zelda Mariet, David Dohan, Kevin Murphy, Lucy Colwell, and D Sculley. Population-based black-box optimization for biological sequence design. In International conference on machine learning, pp. 324-334, PMLR, 2020.
Frances H Arool. Design by directed evolution. Accounts of chemical research, 31(3):125-131 1998.
Melis Ilayda Bal, Cem lyigun, Faruk Polat, and Huseyin Aydin. Population-based exploration in reinforcement learning through repulsive reward shaping using eligibilitty traces. Annals of Operations Research, pp. 1-33, 2024.
Maximilian Balandat, Brian Karrer, Daniel R. Jiang, Samuel Daulton, Benjamin Letham, An- drew Gordon Wilson, and Eytan Bakshy. BoTorch: A Framework for Efficient Monte-Carie Carlo Bayesian Optimization. Advances in Neural Information Processing Systems 33, 2020.
Ricardo Baptista and Matthias Poloczek. Bayesian optimization of combinatorial structures. In International Conference Machine Learning, pp. 462 462-471. PMLR, 2018.
Surojit Biswas, Grigory Khimulya, Ethan C Alley, Kevin M Esvelt, and George M Church. Low-n protein engineering with data-efficient deep learning. Nature methods, 18(4):389-396, 2021.
Johannes Büchler, Sumire Honda Malca, David Patsch, Moritz Voss, Nicholas J Turner, Uwe T Bornscheuer, Oliver Allemann, Camille Le Chapelain, Alexandre Lumbroso, Olivier Loiseleur, et al. Algorithm-aided engineering of aliphatic halogenase welo5* for the asymmetric late-stage functionalization of soraphens. Nature Communicationss 13(1):371, 2022.
Nicolò Besa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. 01 2006.
Lixue Cheng, Ziyi Yang, Changyu Hsieh, Benben Liao, and Shengyu Zhang. Odbo: Bayesian optimization with search space prescreening for directed protein evolution. arXiv preprint arXiv:2205.09558, 2022.
George Christodoulou and Elias Koutsoupias. On the price of anarchy and stability of correlated equilibria of linear congestion games. In Gerth Stølting Brodal and Stefano Leonardi (eds.), Algorithms ESA 2005, 2005.
Hamid Dadkhahi, Karthikeyan Shanmugam, Jesus Rios, Payel Das, Samuel C Hoffman, Troy David Loeffler, and Subramanian Sankaranarayanan. Combinatorial black-box optimization with expert advice. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1918-1927, 2020.
Samuel Daulton, Xingchen Wan, David Eriksson, Maximilian Balandat, Michael A Osborne, and Eytan Bakshy. Bayesian optimization over discrete and mixed spaces via probabilistic reparame- terization. Advances in Neural Information Processing Systems, 011117660-27774 2022.
Aryan Deshwal and Jana Doppa. Combining latent space and structured kernels for bayesian optimization over combinatorial spaces. Advances in Neural Information Processing Systems, 34: 8185-8200, 2021.
Aryan Deshwal, Syrine Belakaria, Janardhan Doppa, and Alan Fern. Optimizing discrete spaces via expensive evaluations: A learning search framework. Proceedings of the AAAI Conference Artificial Intelligence, 34:3773-7780, 04 2020.
Aryan Deshwal, Syrine Belakaria, and Janardhan Rao Doppa. Bayesian optimization over hybrid spaces. In International Conference Machine Learning, pp. 8632-2643 PMLR, 2021a.

---

Published as a conference paper at ICLR 2025
Aryan Deshwal, Syrine Belakaria, and Janardhan Rao Doppa. Mercer features for efficient combina- torial bayesian optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8): 7210-7218, May 2021b.
Aryan Deshwal, Sebastian Ament, Maximilian Balandat, Eytan Bakshy, Janardhan Rao Doppa, and David Eriksson. Bayesian optimization over high-dimensional combinatorial spaces dictionary-basee embeddings. In International Conference on Artificial Intelligence and Statistics, pp. 7021-7039. PMLR, 2023.
Kamil Dreczkowski, Antoine Grosnit, and Haitham Bou Ammar. Framework and benchmarks for combinatorial and mixed-variable bayesian optimization. Advances in Neural Information Processing Systems, 36, 2024.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. Advances in neural information processing systems, 32, 2019.
Peter Frazier and Jialei Wang. Bayesian optimization for materials design. In Information science for materials discovery and design, pp. 45-75. Springer, 2015.
Yoav Freund and Robert E Schapire. A dheision-theoreticc generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
Drew Fudenberg and Jean Tirole. Game theory. MIT press, 1991.
Eduardo C Garrido-Merchán and Daniel Hlenández-Loohal Dealing with categorical and integer- valued variables in bayesian optimization with gaussian processes. Neurocomputing, 380:20-35, 2020.
Rafael BombarlBo Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lood Benjamín Sánchez-Lengeling Dennis Sheberla, Jorge paalllrr-pparaguirree Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven continuous representation of molecules. ACS central science, 4(2):268-22 276,, 2018.
Stewart Greenhill, Santu Rana, Sunil Gupta, Pratibha Vellanki, and Svetha Venkatesh. Bayesian optimization for adaptive experimental design: A review. IEEE access, 8:13937-13948, 2020.
Minbiao Han, Fengxue Zhang, and Yuxin Chen. No-regret learning of nash equilibrium for black- -bxx games via gaussian processes. arXiv preprint arXiv:2405.088 083/8, 2024.
Nikolaus Hansen. The ema evolution strategy: comparing review. Towards evolutionary computation: Advances in the estimation of distribution algorithms, pp. 75-102, 2006.
Donald Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13:455-499 492, 1998.
Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poezos, and Eric Xing. Neural architecture search with bayesian optimisation and optimal transport. Advances in Neural Information Processing Systems, 31, 2018.
Asif Khan, Alexander Cowen-Rivers, Antoine Grosnit, Philippe A Robert, Victor Greiff, Eva Smorodina, Puncet Rawat, Rahmad Akbar, Kamil Dreczkowski. Rasul Tutunov, et al. Toward real-world automated antibody design with combinatorial bayesian optimization. Cell Reports Methods, 3(1), 2023.
Jungtaek Kim, Michael McCourt, Tackgeun You. Sachoon Kim, and Seungjin Choi. Bayesian optimization with approximate set kernels. Machine Learning, 1 110:857-30 879, 2021.
Robert Kleinberg, Georgios Piliouras, and Éva Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. In Proceedings of the forty-first annual ACM symposium Theory of computing, pp. 533-542, 2009.
12

---

Published as a conference paper at ICLR 2025
Ksenia Korovina, Sailun Xu, Kirthevasan Kandasamy, Willie Neiswanger, Barnabas Poczos, Jeff Schneider, and Eric Xing. Chembo: Bayesian optimization small organic molecules with syn- thesizable recommendations. In International Conference Artificial Intelligence and Statistics, pp. 1993-3403. PMLR, 2020.
Andre KY Low, Flore Mekki-Berrada, Aleksandr Ostudin, Jiaxun Xie, Eleonore Vissol-Gaudin, Yee-Fun Lim, Abhishek Gupta, Qianxiao Li, Yew Soon Ong, Saif A Khan, et al. Evolution- guideed bayesian optimization for constrained multi-objective optimization in self-driving labs. ChemRxiv, 2023.
Wenlong Lyu, Fan Yang, Changhao Yan. Dian Zhou, and Xuan Zeng. Batch bayesian optimization via multi-objective acquisition ensemble for automated analog circuit design. In International Conference Machine Learning, pp. 1300-33144 PMLR, 2018.
Natalic Maus, Haydn Jones, Juston Moore, Matt J Kusner, John Bradshaw, and Jacob Gardner. Local latent space bayesian optimization over structured inputs. Advances in Neural Information Processing Systems, 55:34505-345155 2022.
Joshua Meier, Roshan Rao, Robert Verkuil, Jason Liu, Tom Sercu, and Alex Rives. Language models enable zero-shot prediction the effects mutations on protein function. Advances in Neural Information Processing Systems, 34:29287-29301. 2021.
Jonas Mockus. On bayesian methods for seeking the extremum. In Optimization Techniques, 1974.
Henry Moss, David Leslie, Daniel Beck, Javier Gonzalez, and Paul Rayson. Boss: Bayesian optimization over string spaces. Advances in Neural Information Processing Systems, 33:15476- 15486, 2020.
J.F. Nash. Non-cooperative games. Annals of Mathematics, 54(2):286-295, 1951.
Diana Negoescu, Peter Frazier, and Warren B Powell. The sequencing experiments in drug discovery. INFORMS Journal Computing, 23(3):346-363) 2011.
gradient algorithm for
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.
Anders Olson, Nicholas Wu, and Ren Sun. A comprehensive biophysical description of pairwise epistasis throughout an entire protein domain. Current biology, (1422))2643-26511 2014.
Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size congestion games: Convergence, limit cycles and chaos. Advances in Neural Information Processing Systems, 30, 2017.
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: 16:1764-1793, 2023.
Patrick C Phillips. Epistasis the essential role of gene interactions in the structure and evolution of genetic systems. Nature Reviews Genetics, 911 (11)):555-4 867, 2008
Douglas Prasher, Virginia K Eckenrode, William W Ward, Frank G Prendergast, and Milton J Cormier. Primary structure of the aequorea victoria green- green-fluorese fluorescent protein. Gene, 111(2): 229-233, 1992.
Carl Edward Rasmussen, Christopher KI Williams, al. Gaussian processes for machine learning. volume 1. Springer, 2006.
Philip A. Romero and Frances H. Arnold. Exploring protein fitness landscapes by directed evolution. Nature Reviews Molecular Cell Biology, 10:866-876, 2009.
Philip A Romero, Andreas Krause, and Frances H Amold. Navigating the protein fitness landscape with gaussian processes. Proceedings of the National Academy of Sciences, 11033) 2013.
13

---

Published as a conference paper at ICLR 2025
Pier Giuseppe Sessa, Ilija Bogunovie, Maryam Kamgarpour, and Andreas Krause. No-regret learning in unknown games with correlated payoffs. Advances in Neural Information Processing Systems, 32, 2019a.
Pier Giuseppe Sessa, Maryam Kamgarpour, and Andreas Krause. Bounding inefficiency of equilibria in continuous actions games using submodularity and curvature. In International Conference on Artificial Intelligence and Statistics, pp. 2017-2027. PMLR, 2019b.
Pier Giuseppe Sessa, Maryam Kamgarpour, and Andreas Krause. Efficient model- multi-agent reinforcement learning via optimistic equilibrium computation. In International Conference Machine Learning, pp. 19580-19597. PMLR, 2022.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.39955 2009.
Samuel Stanton, Wesley Maddox. Nate Gruver, Phillip Maffettone, Emily Delaney, Peyton Greenside, and Andrew Gordon Wilson. Accelerating bayesian optimization for biological sequence design with denoising autoencoders. In International Conference on Machine Learning, pp. (0459-204477 PMLR, 2022.
Austin Tripp. Erik Daxberger, and José Miguel Hernández-Lobato. Sample-efficient optimization in the latent space of deep generative models via weighted retraining. Advances in Neural Information Processing Systems, 13:11229-11272, 2020.
Adrian Vetta. Nash equilibria in competitive socicties, with applications to facility location, traffic routing and auctions. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp. 416 425. IEEE, 2002.
Bruce J Wittmann, Kadina E. Johnston, Zachary Wu, and Frances H Arnold. Advances in machine learning for directed evolution. Current opinion structural biology, 69: 19:11-18, 2021.
Nicholas C. Wu, Lei Dai, Anders Olson, James O. Lloyd-Smine and Ren Sun. Adaptation in protein fitness landscapes facilitated by indirect paths. el.ife, 5, 2016.
Zachary Wu, S. B. Jennifer Kan, Russell D. Lewis, Bruce Wittmann, and Frances H. Amoll. assisted directed protein evolution with combinatorial libraries. Proceedings of
Machine lessnin--sssisted the National Academy of Sciences, 116(18):8852 8858, 2019.
Kevin K Yang, Zachary Wu, and Frances H Aroold Machine-leaming-gutne directed evolution for protein engineering. Nature methods, 16(8):687669, 2019.
Fengxue Zhang, Jialin Song, James C Bowden, Alexander Ladd, Yisong Yue, Thomas Desautels, and Yuxin Chen. Learning regions of interest for bayesian optimization with adaptive level-set estimation. In International Conference Machine Learning, pp. 41579-41595. PMLR, 2023,
14

---

Published as a conference paper at ICLR 2025
Appendix
Table of Contents
A Proof of Theorem 4.2
16
B OF for Protein Design
16
C Baselines
16
D Experiment Details
17
E Additional Experimental Results
20
E.1 Sample batch diversity...
20
E.2 Comparison with GP-UCB
21
E.3 Comparison with Discrete Local Search methods
21
E,4
Computational costs
22
E.S
Additional analyses
22
Exploring players' grouping
26
Exploring players' with different action sizes (dimensions)
(diennins).................
26
E.8
Batch size ablations
27
E.9
Learning rate (1)) ablations for GAMEOPT-HEDOG
28
E,10
UCB values of the sampled batches
29
E.11
Expected Improvement acquisition function
29
E.12
Comparison with latent space optimizers
29
15

---

Published as a conference paper at ICLR 2025
We gather here the technical proofs, the details GAMEOPT's appiiaatta to protein design, and additional experiment results complementnng the main paper.
A PROOF OF THEOREM 4.2
The proof relies on the main confidence lemma (Srinivas et al., 2009, Lemma 5.1) which states that, when the confidence width is set 3t 2n log (supretn] [X] (x22 then with probability at least (1 - 8).
2 log (IIT X, 2x3
66
(=(x) 3,01(z)= f(x) S (e(x) (10((2),
(5)
In other words, UCB(GP',-) and LCB(GP'.) are upper and lower bound functions with high probability. For simplicity, we will use the notation UCB.() and LCB,()) for UCB(GP',) and LCB(GP', ;)). respectively.
Next, we show that after T iterations the strategy reported by GAMEOPT: øT, with T arg min m UCB,(#', ,x.") (z,), is a er-approximate Nash equilibrium of f with er I OT VPr). The theorem statement then follows by simple inversion of the aforemen- tioned bound.
By definition, 27- is er-approximate Nash equilibrium of f when = m [(" (T-) (#rr.), ), i.e. er upper bounds all possible single-player deviations. We can bound the worst-case single-player deviation with probability (1 ó) by the following chain of inequalities:
CT = max f(x", f() -f(xr.) S max UCB 3,2*
xz()) UCB
LCBr-(rT-)
(6)
max (C' LC,,(r))
(7)
1,
2
max UCB, (C, +
3,0
(xa)
T
T
1,
1=1
(8)
2
T Σ (x, S O(T BrTT).
(9)
The first inequality follows from the confidence lemma (5). The second one, by the fact that mf UCBT (x*, (x',)=)) (CBr-(ET-) S max; UCB,(x', "x (C,, Vi, by definition T The last inequality holds because, at each iteration t, Iy is an equilibrium of the UCB, function. Finally, the last inequality is from (Srinivas et al., 2009, Lemma 5.4).
B GAMEÖPT FOR PROTEIN DESIGN
The core concept of the GAMEOPT framework is inspired by the principles of natural evolution. In protein design, achieving equilibrium of a cooperative game over protein sites mirrors the iterative mutation and selection process in evolution. Where it converges beneficial mutant sequences, can be thought of as equilibrium of the game. Given that protein search spaces align well with the domain GAMEOPT works on, introduce specialized version of GAMEOPT, tailored for protein design applications.
C BASELINES
In Section 5, we empirically evaluate GAMEOPT against existing baselines which we detail next. These include BRR-FINESSS inspired by directed evolution (Algorithm 6). RANDOM (Algorithm 7), which samples evaluation points randomly, and PR, an optimizer of expected UCB (Daulton et al., 2022). We further compared GAMEOPT with discrete local search methods in Appendix E.3.
16

---

Published as a conference paper at ICLR 2025
Algorithm 4 GAMEOPT-IBR for Protein Design
1: Input: GP prior GP" (Ho. k):,))), initial data Do = {( y/ = f(x;) + + protein sites N,
batch size B E N, M N >> B, parameter B.
2: for iteration f = 1, ..2......
do
3: Construct game with reward function UCB(GP'-1, B,,)): II: X26 - R
4: for m = 1, , M do
5: XD raandom starting protein sequence, xf] X
6: for round k = 1, 2, K do
// BR game
7: Ax + { (xttbr x such that z = arg ma UCB(2, iibr
i=1
8:
Play x +- arg maxx [UCB(r+)]
9: end for
10: Collect equilibrium protein sequence 2t, < xx
11:
end for
12:
Select batch of top B equilibrium protein sequences { according to UCB UCB(GPt-1,8.) #/ Filtering
13:
Obtain fitness evaluations Ve, = f(z(() + Et,é. vi I,...,B
14:
Update D, + D U (e
15:
Posterior update of model GP with D.
end for
Algorithm 5 GAMEOPT-HEDGGE for Protein Design
1: Input: GP prior GP (uo, .). initial data Do {(ri y/i f(x)) + +e) protein sites M,
batch size B E MM > B, parameters 3, 7z.
2: for iteration ( 1,2, .... ,
3: Construct game with reward function UCB(CP' ,,,)) : 20 +R
4: for = 1.2..... M do
5: Initialize weights w1 + 1
(I....,, TRINI
W
6: for round 1, 2....... K do
*/ Simultaneous Hedge
7:
Sample 2 ~ wi, Vi E Set joint strategy X2 + fatheN for player e N do
8:
9:
*/ Players' payoff
10:
l (u(a) (-(o where r =i= (rieene Vj 20) Set w x wt exp(ne,;))
11:
12:
end for end for
14:
Collect equilibrium protein sequence Zi,m + XX
15:
end for
16:
Select batch of top B equilibrium protein sequences { according to UCB 1,
#/ Filtering
17:
Obtain fitness evaluations Vt,, f(z1,) Et,i, Vi I....,B
18:
Update D, + D:-1 U ( =
19:
Posterior update of model GP with D.
20: end for
D EXPERIMENT DETAILS
We set the (hyper)paramettrs for the experiments as in Table
GBI(4) The dataset (Wu et al., 2016) is fully combinatorial, i.e., encompassing fitness measurements of 20 variants with sites. In this context, each protein site is treated player in the cooperative game of GAMEOPT, with = (1....,44 4}. Additionally, we also analyzed the effect of player grouping inspired by epistasis phenomenon in protein design and provided the analysis in Appendix E.
17

---

Published as a conference paper at ICLR 2025
Algorithm 6 ITERATIVE BEST RESPONSE-FITNESS (IBR-FITNESS)
1: Input: Domain X, fitness function
X R, players N, initial data Do { Y/
f(z;) + +)), batch size B E N.
2: x0 f- random joint strategy, x8" X
3: for iteration / = ........ do
4: Randomly selected / players E N generates BRs { w.r.t. x based on f(-)
5: Obtain evaluations Ve, = f + Er,
Vi = 1,...,
6: Update D, + 11-1 U {(Tr, Ne. J
7: Play xbr t- arg max E Vt,5
8: end for
9: return Xj < arg max(e !/
*/ Best-so-far
Algorithm 7 RANDOM
1: Input: Domain X, X + R. initial data Do {( V/ fxx) <)), batch size B N.
2: for iteration f = 1, 1.2..... T do
3: Randomly generate batch of B points (ft,i)i=11 Var,i i X
4: Obtain evaluations Wt,i f( Er,i,
Vi 1,, 1,..., B
5: Update Dr + D U [(TI. Wes))
6: end for
7:
return Xi < arg maX(x
*/ Best-so-far
We train the GP surrogate by utilizing small portion of the dataset, specifically 0.0625%. consisting of 100 protein variants. Since existing literature does not provide common ground feature embeddings as representations for the GBI(4) variants, we use chemical descriptors (Wu et al., 2019) extract 60 feature embeddings using training set of size 1000 protein variants with LASSO method. We apply k-fold cross-vale vols-valliotiion with evaluate the performance of our approach over 18 replications. In each replication, we initialize the GP surrogate-bar based baseline methods with the same initial GP model as our approach. We also use the same initial protein sequence for comparison within that replicate but employ different initial points across replications. We set the starting joint strategy as the protein sequence having the highest log fitness value in the training set. The prior mean of the GP is fixed at 1.0162. For the kernel hyperparameters, 60 lengthscales are defined for each feature dimension and optimized offline at the beginning of replication; outputscale is 0.02169.
different train/test dataset partitions. Following this, we
GBI(55) We experiment on the non-exhaustive dataset GBI that only includes 2-point mutations throughout the entire 55 residues of the GB/ protein resulting in 535, 917 variants (Olson et al., 2014) and consider two settings: and 10 number players.
GB1(55) with 55 Players In this context, we treat each protein site as a player in the GAMEOPT, thus, N -5,...,,55. 55).
As the dataset is not completely combinatorial, we do not have access to measured fitness values for all 2055 variants. overcome this, we employ Deep Neural Network- based (DNN) oracle to predict fitness scores using feature embeddings associated with the protein sequences. We again opt feature embeddings as the representation for categorical input of GP surrogate. Unlike GBI(4), we utilize the ESM-1v protein language model from e.mm introduced by Meier et al. (2021), specifically designed for predicting protein variant effects and can be used to extract embeddings. With ESM 1v, represent sequence through 1280 dimensional feature embedding vector. We train the oracle with supervised learning, using the training set having (477 854 x 1280, 477 854) feature & label pairs. Obtaining the exhaustive version of the GB1(55) dataset, train the GP surrogate using ESM-1v feature embeddings 1000 randomly generated protein variants and corresponding pracle-predicee fitness scores for 10 replications.
18

---

Published as a conference paper at ICLR 2025
Table Hyperparameler values.
Symbol
Hyperparameter
Value
T
The number of active learning (BO) itcrations
50
number game rounds
for for Halogenase GBI(55), and for GB1(4):
50 for GAMEOPT IBR in GBI(S5) & = 10 dumain
GAMFOPT-IRR GB1(55) for Halogenase, for GBI(4), 6 and for GFP. 10 and 55 for GB1)55)
N1
The number of players
samples in training
Halogenase GRT(4), 1000 Optimized over the 10.1, 0,5,0,9.,. 1.0, 2.0]
and GRI(55)
Learning rate
Observation noise each training example
0,0004
RBF kernel lengthscale
Optimized oflliee
The UCB tuning parameter
B
Batch per BO iteration
GBI(55) with 10 players further analyze the performance GAMEOPT compared to the other baselines, we consider the setting where among the 55 sites, only 10 most significant protein sites can be mutated.
We employ the protein language model for embeddings and oracle predict fitness scores. However, the choice of 10 players among (10) possibilities is a strategic decision that affects the design performance. For this, we define the significance of protein site considering the use Algorithm 8 and select N = {21, 24, 35, 39, 41, 45, 46, 47, 48, 50) sites as the players. We treat the rest the protein sequence, i.e., sites that do not correspond to players fixed.
average variation in the fitness scores in the dataset. Concretely,
Algorithm 8 COMPUTEMOSTSIGNIICANSTTTT
1: Input: Dataset D (I,, v) players K, protein sequence length L, amino acids set A.
2: Initialize players 0, site_score, 0 and site_var* 0, vk E {1,..., L}. E A
3: for each pair (I,, 34) E ' do
4: for each site & {1, (I...., do
5: Set amino acid in site h as t at
6: Append site scte_sscree & site cate_scoret" U {3:}
7: end for
8: end for
9: site_ site_score" + {site_scoreeeee score Vk {l,.... ... L}
10: site_var" +- stdev(site (site_scoreee) vk E {l..... ... L}
11: return K sites having highest site_score as players
Halogenase Halogenase is non-exhaustive dataset involving fitness measurements for 605 unique variants. To obtain the complete protein fitness landscape, we again construct an oracle, Le,, an MLP having R 0.96 test set and experiment setting where each protein site is player.
GFP with 6 players The Aequorea victoria green-fluoresee protein dataset only includes fitness measurements of 35, 584 variants corresponding to mixed mutations of some positions on 238 length sequence. For the fully combinatorial protein fitness landscape, we construct an oracle, i.e., an MLP with test R² 0.90 and choose 6 positions: N {10, 18, 22, 37, 67, 78) that have the largest number of mutations in the original dataset as the players of the GAMEOPT.
GFP with 8 players To set the players in this setting, we identified positions that have the largest number of mutations in the original dataset: N (10, 18, 22, 37, 67, 78, 196, 112).
19

---

Published as a conference paper at ICLR 2025
E ADDITIONAL EXPERIMENTAL RESULTS
E.1 SAMPLE BATCH DIVERSITY
We also evaluate method against baselines in terms of performance metric: sampled batch diversity concerning the past. It is measured via the mean Hamming distance of executed points at each BO iteration the (1) closest initial training point and (2) the proposed point the previous iteration (pairwise distance).
The results depicted in Figure 4 underscore that GAMEOPT explores faster compared to baselines except for RANDOM. Notably, even in the initial iterations, GAMEOPT demonstrates the capability discover points beyond the trust region of its GP prior. Furthermore, it consistently upholds the sampled batch diversity compared to previously executed strategies. As also illustrated in Figure 3, GAMEOPT explores effectively at the beginning and gradually converges region conducive to exploitation. This enhanced exploration across the search space contributes to its outperforming performance in identifying high siness-valued protein sequences.
On the other hand, the exploration strategy employed by RANDOM relies on the generation of B best responses through random selection, a method that does not consistently ensure a diverse sampled batch in the input space. Furthermore, IBR-FIITI FITNESS shows moderate sampled batch diversity concerning the past, attributed to its more exploitative nature-spectin cature--peciffiallly. the sampling of B best responses based true log fitness values in comparison to other baseline methods. While PR manages to maintain a diverse sampled batch concerning the past in the context of GBI(4), its performance falters when applied to other settings. Additionally, the sampling process of PR involves computing the expected UCB across all potential strategy combinations of players, making its performance, and consequently its sampled batch diversity, highly reliant on an accurate estimate of this expectation.
Avg. Hamminn Distance went Initial Point
Avg. Hamming Distance wet Initial Point
Arg. Hamming Distance wet Initial Point
3.0
0
25 Iteraions
(a) Halogenase, 3, 18 reps.
(b) GBI(4), 4, 18 reps.
(c) GFP, nI = 6, 10 reps.
Aug. Hamminng Distance Initial Point
Avg. Hamming Distance Initial Point
Hamming Distance Initial Point
Derations
Reratioea
Rerations
(d) GFP, 10 reps.
GBI(
10, 10 reps.
(f) GBI(55),
55, 10 reps.
GameOpt-19R
Hedee
Pitees
PR
GPUCU
Random
Best strategy
Figure Performance results for the sampled batch diversity w.r.t past measured via mean Hamming distance between the executed variant and the closest initial point from the training set, under batch size B = Each point on each line is the average of multiple replications initiated with different training sets having 100 variants for GB1(4) & Halogenase and 1000 for GBI(55) & GFP. Similarly, error bars are interquartile ranges averaged over replications. all experiments, GAMEOPT explores significantly faster than the baseline methods.
20

---

Published as a conference paper at ICLR 2025
E.2 COMPARISON WITH GP-UCB
We further analyzed the saturating behavior exhibited by GP-UCB in the GBI(4) setting. As depicted in Figure 5, our investigation focused the influence of the initial GP surrogate model, considering different training set sizes, specifically with 100 and 500 training points.
Our findings underscore that the efficacy of GP-UCB heavily relies on the quality of the initial GP surrogate model. Particularly, an initial GP surrogate trained with only 100 data points proves insuffi- cient for GP-UCB effectively identify high-log fitness protein sequences. Given that GP-UCI optimizes the UCB globally and selects the B best points in each iteration, the limited informativeness of sampled batch points under this GP surrogate constrains the algorithm. Therefore, GP-UCB ends up converging point where further improvement is impeded. In contrast, employing potentially more informative GP model with 500 training points enables GP-UCB to perform comparably to GAMEOPT, Our proposed approach, however, exhibits robustness by overcoming the constraints associated with a model initialized with limited data. Through computing evaluation points as the equilibria of cooperative plae-p,aying, it consistently gathers diverse and informative batches to guide the GP, thereby enhancing sample efficiency.
Log Pitness (best Far)
Log Fitness (best far)
0.5
0.1
Berations
Derratinns
(a) 100 training points.
(b) training points.
GameOpt-IBR
HadeOpt-Hedge
IBR-Fitaes
PR
GPUCB
Random
Best strategy
Figure 5: The effect of training set size on the performance under setting GBI(4), n = 4, 18 reps. GP-UCB mitigates saturating behavior when leveraging more informative initial GP surrogate model. In contrast, GAMEOPT showcases resilience in overcoming the limitations associated with a GP model trained with limited amount of data.
E.3 COMPARISON WITH DISCRETE LOCAL SEARCH METHODS
We further compared GAMEOPT against Discrete Local Search baselines DLS and DLS_ BEST (Balandat et al., 2020) that perform discrete local search by exploring k-Hamming distance neigh- borhood. While DI.S employs random initialization, DISS_BEST BEST starts the local search from the best-discovered sequence. In our experiments, we set their neighborhood size as 2-Hamming distance and let the baselines greedily select B sequences each iteration. For fair comparison against DLS DLS_BEST, we also run the best-discovered sequence initialization version of our approach, called GAMEOPT-IBR BEST
We remark that DLS and DLS BEST can be seen as constrained versions of GAMBOPT that require prior definition of the neighborhood (thus, unlike our approach, they require a notion of distance too). Moreover, being centralized, they are subject to higher computational complexity which grows exponentially with the neighborhood size. For a sequence of length n (players) with x = d many amino acid choices, GAMEOPT reduces the intractable optimization of acquisition function (i.e.. O(d")) 1) to ((nd) complexity. Instead, DLS & DLS _EST search over k-distance neighborhoods yielding OCC(n, ((C(n)))dd) complexity, where denotes the combination operation and k is the Hamming distance. We observe GAMEOPT performs comparably to DLS baselines (see Figures 6, 7, 8, and additional analyses below), but requiring significantly lower compute cost, as shown in Appendix E.4.
21

---

Published as a conference paper at ICLR 2025
E.4 COMPUTATIONAL COSTS
We report the total compute amount (measured in hours) for the experiments with T = 50 BO iterations in Table 2. We conduct the experiments on an internal compute cluster equipped with NVIDIA A A00 80 GB tensor-core GPUs. For smaller domains (with short protein sequences), we were able to execute replications concureentyy without encountering memory errors. However, in configurations necessitating the generation of embeddings for numerous evaluation points with longer protein sequences each iteration, parallel execution was not feasible, thus necessitating per-replication computation time report. Specifically, we present the total compute amount for all replications across domains Halogenase, GBI(4), and GFP; whereas we report per replication compute amount accompanied by its standard deviation for the two largest GBI(55) domains.
Referring to Table GAMEOPT variations provide tractable acquisition function optimization. Their computational demand predominantly hinges on the number of sequences they evaluate per BO iteration. This is also influenced by the number of game rounds-which we intentionally set to a higher value to guarantee convergence to game equilibrium (sce Table for the exact values). Nevertheless, our observations reveal that game equilibrium is often reached well before the rounds are completed. Consequently, the computational times reported for GAMEOPT can be considered to be within the worst-case scenario.
Table 2:
Total compute amount (in hours) required for experiments with T' = 50 BO iterations. Each entry with + represents the average per-replication computation time, accompanied by their standard deviation, whereas the others show the total compute time for all replications. We run 18 replications for Halogenase, GB)(4), and 10 replications for the other domains. In all domains, particularly for the larger search spaces, GAMEOPT provides tractable acquisition function optimization.
Domain
Method
Halogenase
GBI(4)
GFP, =
GFP. =
GBT(55), 10
GBI(55). n 55
GAMEOPT-IBR
0.19
0.30
1.02
2.74
1.61 + 0.46
11.25
3,19
GAMEOrT-HEDGR
2.44
1.95
2.05
+0.02
2.60 +:009
3.85 +0.39
20.13 1.04
GP-UCB
0.63
29.56
DLS
0.29
1.10
2.90
+0.33
4.94 +0.24
4.10 +2.36
102.86 +27.42
E.5 ADDITIONAL ANALYSES
We performed further analyses to assess the effectiveness of our GAMEOPT framework against baselines in terms of: (1) fraction of global optima discovered, (2) fraction of solutions found above fitness threshold, (3) cumulative maximum for sequences proposed and (4) mean pairwise Hamming distance between proposed sequences.
We evaluated the fraction of global optima discovered under the GBI(4) setting, as depicted in Table 3. For this fully combinatorial dataset, we identify the global optimizer sequence by exhaustive search. Our findings revealed that GAMEOPT-IBR successfully identified the global optimum sequence in 33.33% of cases out of 18 replications, highlighting its superior convergence against baselines.
Additionally, given the difficulty of identifying global optima in non-fully combinatorial datasets, we examined the fraction of optima found above a fitness threshold, fr 0.8. Table 4 demonstrates that across all problem domains (excluding best cumbersome initialization versions), the GAMEOPT framework consistently samples batches containing higher number of optimal sequences compared to baseline methods. Its effectiveness is highlighted more as the search space size gets higher. In the most complex domain, GB1(55) with 55 players, its best cumbersome initialization version performs comparably to DIS__BEST. BEST. However, it is essential to also acknowledge the comparison w.r.t the computational complexity associated with that configuration as discussed in Appendix F.4.
Regarding the cumulative maximum for proposed sequences (see Table 5), our framework demon- strates notable performance by consistently proposing protein variants with higher fitness values. Moreover, its superior convergence speed, illustrated in Figure 6, underscores its effectiveness against baselines including DLS. The discrete local search with best initialization, DLS _EETT, converges relatively slower, particularly in small domains, yet performs comparably against GAMEOPT BEST in finding high log fitness valued variants. However, it does not provide tractable optimization as detailed in Appendix E.4.
22

---

Published as a conference paper at ICLR 2025
Furthermore, analyzed the performance of methods considering the mean pairwise Hamming distance between the sequences proposed at each BО iteration (see Table and Figure 7) which is an indicator for sampled batch diversity. The results indicate that GAMEOPT explores moderately, however, it balances exploration and exploitation to prevent over-exploring seen in RANDOM and DLS, as well over-exploiting observed in GAMEOPT BEST, DL.S_ BEST and PR.
Lastly, the mean Hamming distance between the proposed variant and the closest initial point from the training set (see Figure 8) showcases that GAMEOPT explores the solution space faster than the baseline methods, except for RANDOM and DLS.
Table 3: Fraction of global optima found for the GBI(4) dataset. Each entry is the average of 18 replications. GAMEÔPT variations are able to sample global optimum sequence (AHCA) more frequently compared to other baselines. Entries of the outperforming methods are denoted in bold. The results show that GAMEOPT-IBE converges the best strategy more frequently compared to the baselines.
Method
% best strategy (AHCA) found
GAMEOPT-IBR
33.33
GAMEOPT-HEDGE
16.67
IBR-FITNESS
16.67
PR
0.00
GP-UCB
0.00
RANDOM
0.00
DLS
0.00
DLS BEST
11.11
GAMEOPT-IBR BEST
11.11
Table 4: Percentage of computed candidates that above threshold of J. 0.8*(maximum fitness value). Each entry is the average of 18 replications for Halogenase and GBI(4) settings, and 10 replications for the others. Entries the outperforming methods are denoted in bold. Results indicate the effectiveness of GAMEOPT variations on sampling more optima than the baseline methods.
Domain
Method
Halogenase
GB]
GFP,
GFP, =
GBI((55), 10
GB GBT(S5),
50
GAMEOPT-IBR
100.00
21.20
28.52
50.96
11.60
1.96
GAMEOPT-HEDGE
94.44
14.62
26.68
61.72
9.48
2.12
TBR-FIENESS
72.22
7.46
18.96
35.32
0.36
0.00
38.89
2.05
15.96
15.32
0.00
0.04
GP-UCB
72.22
4.82
RANDOM
0.00
0.29
0.76
1.60
0.00
0.00
DLS
94.44
7.46
22,60
36.48
0.16
0.00
DLS_BEST
88.89
19.88
16,80
45,92
2,64
52.24
GAMEOPT-IBR, BEST
44.44
17.40
12.32
42.64
1.68
48.64
Table 5: Cumulative maximum for sequences proposed at the end of the BO iterations. Each entry is
the average of 18 replications for Halogenase and GBI(4) settings, and 10 replications for the others. Entries of the outperforming methods are denoted in bold. GAMEOPT variations show superior performance in proposing higher fitnessvalued protein variants.
Domain
Method
Halogenase
GBI(4)
GFP. n
GFP n
GB1(55) n
10
GBI(55), n
50
GAMEOPT-IBE
3.51
0.93
6.37
1.94
4.72
GAMEOPT-
3.45
6.34
1.69
4.66
IBR-PITNESS
3.10
0.86
6.08
6.21
0.97
2.99
PR
2,08
0.81
6.06
6.07
0.90
1.18
GP-UCB
2.98
0.82
RANDOM
1.15
0.68
5.92
5.97
-0.08
-0.66
DI.S
3,51
0.89
6.14
1.70
1.35
BEST
2.11
7.87
GAMEOPT-IBR BEST
2.28
0.93
6.14
6.33
1.91
7.25
23

---

Published as a conference paper at ICLR 2025
Table Mean pairwise Hamming distance between the sequences proposed each iteration. Each entry is the average of 18 replications for Halogenase and GBI(4) settings, and 10 replications for the others. all problem domains, RANDOM baseline consistently samples rather diverse batch of evaluation points w.r.t. past proposed variants. Although this shows enhanced exploration, one drawback lack exploitation. Hence, as illustrated in Figure 3, GAMEOPT balances these two successfully and shows a moderate sampled batch diversity.
Domain GFP,
Method
Halogenase
GBI(4)
GFP,
GBI(53),
GBI(55),
GAMEOPT-IBR
1.40
2.94
3.08
4.11
7.32
50.93
GAMEOPT-HEInE
2.13
2.91
2.93
4.23
3.98
45.89
IBR-FITNESS
0.86
0.88
0.85
0.89
0.86
0.89
PR
1.61
1.61
1.67
1.69
1.60
GP-UCB
0.77
2.41
RANDOM
2.85
3.8
5.69
7.64
9.51
52.34
DLS
1.13
3.36
5.13
7.13
9.38
52.19
DLS BEST
0.68
2.56
1.18
2.36
1.55
3,57
GAMEOPT-IBR BEST
0.33
2.64
1.48
2.78
0.57
3.12
LogFitness (best far)
LogFitness (best far)
LogFitness (best far)
3.0
0.5
0.2
0.5
Berations
Merations
Berations
(a) Halogenase, 18 reps.
(b) GBI(G), reps.
(c) GFP, n 6, reps.
LogFitness (best so far)
LogPitness (best so far)
LogFitnoss (best so far)
6.2
63
5.8
20
lterations
Berstions
Iterations
(d) GFP, 8, 10 reps.
(e) GBI(55), 10, 10 reps.
(f) GBI(55), 55, 10 reps.
GBR GameOpt-Hledge
IBR-eitness
GRUCB
GameOpt-IBR
PR
Random
DLS Best
Best strategy
Figure 6: Convergence speed of methods in terms of log fitness value of the best-so-far protein throughout BO iterations, under batch size B = Each point is the average of multiple replications initiated with different training sets having 100 protein variants for Halogenase and GBI(4), and 1000 protein variants for the rest the problem domains. Similarly, emrr bars are interquartile ranges averaged over replications.
24

---

Published as a conference paper at ICLR 2025
Avg. Pairwise Hamming Distance
Avg. Pairwise Hamming Distance
Avg. Pairwise Hamming Distance
Tteration Leratinns
Iorattons
Itrrtions
(a) Halogenase, 18 reps.
(b) GBI(4), 18 reps.
(c) GFP, 6, 10 reps.
Avg. Pairwise Hamming Distanoe
Avg. Pairwise Hamming Distanoe
Avg. Pairwise Hamming Distance
10
10
(d) GFP, 12 8, 10 reps.
(c) GBI(55), n 10, 10 reps.
(f) GBI(55), n 55, 10 reps.
CameOpt-1BR CameOpt-Hedge
IBR-Fitness
GP-UC
DLS
GameOpt-IBR Best
PR
Random
DLS Best
Best siraiegy
Figure 7: Sampled batch diversity w.r.t past measured via mean Hamming distance between the exccuted variant and the proposed variant from the previous iteration (pairwise distance), under batch size B = 5. Each point on each line is the average of multiple replications initiated with different training sets having 100 variants for GBI(4) & Halogenase and 1000 for GBI(55) & GFP. Similarly, error bars are interquartile ranges averaged over replications. In all experiments GAMEOPT consistently samples a rather diverse batch of evaluation points w.rt. past proposed variants. This enhanced exploration of the search space contributes to its strong performance compared to the baseline methods.
Avg. Hemming Distance w.r. Initial Point
Avg. Hamming Distance w.rk Initial Point
Avg. Hamming Distance w.rl Initial Point
35
Ttar Terations
Eterations
Ptarations
(a) Halogenase, 18 reps.
(b) GBI(4), 4, 18 reps.
(c) GFP, 6, 10 reps.
Avg. Hamming Distance wen Initial Point
Avg. Hamming Distance wet Initial Point
Avg. Hamming Distance wit Initial Point
30
10
10
15
80
35
60
10
25
40
45
10
15
25
39
Herations
(d) GFP, 8, 10 reps.
(c) GBI(55), n 10, 10 reps.
(f) GBI(55), 7 55, 10 reps.
GameOpt-IBR
IBR-Fitness
GRUUB
GameOpt-IBR
GameOpt Hedge
PR
Random
DLS Best
Best strategy
Figure 8: Performance results for the sampled batch diversity w.r.t past measured via mean Hamming distance between the executed variant and the closest initial point from the training set, under batch size B 5. Each point each line is the average of multiple replications initiated with different training sets having 100 variants for GBI(4) & Halogenase and 1000 for GBI(55) & GFP. Similarly, bars interquartile ranges averaged
replications. In all experiments, GAMEOPT explores faster than the baseline methods, except for RANDOM and DLS.
25

---

Published as a conference paper at ICLR 2025
E.6 EXPLORING PLAYERS' GROUPING
Until this juncture, we have exclusively examined scenarios where a GAMEOPT player is responsible for only a single site within the protein sequence. In light of the epistasis (Phillips, 2008) phenomenon in protein design, which underscores how the effect of a mutation on fitness can be influenced by the presence of other mutations within the same protein, we now explore the concept of grouping protein sites together, Le., having players being responsible for protein sites independently may yield different fitness outcomes than finding equilibria among groups of several sites. To this end, conduct a preliminary investigation into whether this phenomenon alters GAMEOPT's performance.
than one site. This is because modeling
We experiment on GBI(4) with 1, 2, protein sites and W {1,2} players, considering possible player & site groupings: {(11, 23), (02, 13), (03, 12) For instance, setting (01, means that the first player responsible for sites {0, 1) and the other one for {2.3}.
Our evaluations with GAMEOPT-IBR and GAMEOPT-HEDGE using the same performance measures (Figures 9 and 10) showed that there is no significant performance difference between individual players and grouping settings as they all discover the high log fitness valued protein variants at a similar rate while collecting batches of diverse evaluation points. Nevertheless, an in-depth examination of this phenomenon on larger datasets remains subject for future investigation.
LogFitness (best so far)
Avg. Hamming Distance Point
Avg. Pairwise Hamming Distance
1.0
2.5
0.8
1.5
Nerations
(a) Convergence speed
(b) Sample diversity w.r.t (1)
(c) Sample diversity w.r.t (2)
Figure 9: GAMEOPT-IRE performance for player grouping, under GBI(4) setting, 18 reps. There is no significant performance difference between individual players and player grouping settings under this domain.
LogeiLness
Avg. llamming Distance wet Initial Point
Arg. Pairwise lamming Distance
0.8
0.0
0.4
Terations
Itrations
Iterations
(a) Convergence speed
Sample diversity wint (1)
Sample diversity w.n. (2)
Carasdge Bodgy
Govengee liedgr (233)
Gureeige Elddye www.gettttt.ccccoooooooo. 2.1.
Gora-Oos Hedge groepe (40, (0.32
OPEIC
Test crotoyy
Figure 10: GAMEOPT-HEDOS performance for player grouping, under GBI(4) setting, 18 reps. No significant performance difference exists between individual players and player grouping settings under this domain.
E.7 EXPLORING PLAYERS' WITH DIFFERENT ACTION SET SIZES (DIMENSIONS)
In our main experiments presented in Section 5.4, as well as the grouping of players explored in Appendix E.6, we exclusively examined scenarios where GAMEOPT players have equal number of actions, i.c. x are same for all In the context of protein design, this corresponds to the setting where players are responsible for an equal number of sites. However, GAMEOPT can also be applied to the setting where players have different numbers of actions, i.e. x0() differ among players.
26

---

Published as a conference paper at ICLR 2025
To demonstrate the generalizability of GAMEOPT to such settings, further experiment settings with player groupings, where each group is responsible for different number of protein sites. Particularly, consider site groupings: {(0, 12), (1, 02), (2, 01)} for the Halogenase problem domain. Whereas we consider groupings: {(0, 123), (1, 023), (2, 013), (3. 012) for the GBT(4) domain. For instance, the setting (0, 12) means that the first player is responsible for site {0) and the other one for (1, which makes their action size x 20, x 20
The experiment results presented in Figure 11 show that there no significant performance difference between individual players and player grouping settings with varying action sizes, however, in most of the settings GAMEOPT groupings outperform GP-UCB baseline. This clearly demonstrates the applicability GPMEOPT framework under problem domains with unequal action set sizes.
LogFitness (best so far)
Finess (best so far)
0.8
0.3
0.6
Itorations
Iterations
(a) GAMEOPT-HEDGH GBI(4).
(b) GAMEOPT-IBR GBI(4).
Coneerpeieelge 39.150
Oareerpi Hadge.
Guncetge Heedgn, 0131
Caeneray Hadge FR 6..00
GPACO
Best strdtgy
LogFitness (best so far)
Log LogFitness (best so far)
1.0
0.3
Teerations
lterations
(c) GAMEOPT- HEDGGE on Halogenase. (d) GAMEOPT- Halogenase.
CumeegttHHol Hedge
Cammops-Heege (0. 12)
Gammopp-Heedge 11. 92)
Gamsopt-SSedge ( 01)
GRUCS
CameOpt-IBR
Qutssppi-1BR
GameOpt-BBR
GP-UCB
Figure 11: GAMEOPT-HEERE and GAMEOPT-IBR performance under player groupings with differ- ent action sizes, on GBI(4) and Halogenase domains, 18 reps. There no significant performance difference between individual players and player grouping settings, however, in most of the settings GAMEOPT groupings outperform the GP-UCB baseline. The results support that GAMEOPT is also effective under problem settings with varying action (dimension) sizes.
E.8 BATCH SIZE ABLATIONS
We present additional results on the GB1(4) dataset using higher batch sizes, B 10 and 50. The results in Figure 12 show that GAMEOPT variations still outperform baselines by discovering higher log fitness-valued protein sequences at faster rate due to sampling diverse sets of batches. When batch size increases, HAMEOOT--EDGG becomes dominant in discovering the best protein sequence. This shows that irrespective of the batch size, GAMEOPT is effective in large combinatorial BO settings.
We further present additional analysis using more restrictive batch sizes, B = 1 and B = 3 on the GBI(4) and Halogenase datasets. The results in Figure 13 demonstrate that under more restricted setting on both problem domains, GAMEOPT variations achieve superior performance compared to the baselines. Although initially surpassed by GP-UCB under batch size B 1,
27

---

Published as a conference paper at ICLR 2025
LogFiiness (best so far)
LogFitness (best s0 far)
Iteratons
Lterations
(a) B 10.
(b) B 50.
1ameOpt-18R
Cameopt-Hedge
FBR-Fitees
CRUCC
Random
strategy
Figure 12: Performance comparison on the GB)(4) dataset using batch sizes B 10 and B 50.
GAMEOPT's better exploration compared to the GP-UCB's exploitative behavior avoids ending up at points with lower fitness values. As the batch size increases, GAMEOPT's optimistic game approach benefits from parallelism and collects diverse local optima, hence, GAMEOPT performs significantly better against baselines.
LogFitness (best lar)
Logeitness (best far)
Lineesssss (best far)
2.5
13
1.0
0.5
0.5
Iteratoon
Rerations
Berations
(a) Halogenase, B 1.
(b) Halogenase, B 3.
(c) Halogenase, B 5.
LogFitness
Lignes
Lignetness (best so far)
1.2
1.0
1.0
0.1
0..
0.0
0.5
0.4
45
50
10
15
35
40
45
30
10
25
(d) GB1(4), B
(c) GBI(4),
3.
(f) GBI(4),
CameOpt-1BR
GameOOpt-Hedge
Fittes
PR
GRUCB
Random
Best strategy
Figure 13: Performance comparison on the Halogenase and GBI(4) datasets using batch sizes B = [1,3,5), 5J. The results show that GAMEOPT outperforms baselines even under more restrictive batch size settings. Although initially surpassed by GP-UCB under batch size B 1, GAMEOPT's better exploration compared to the GP-UCB's exploitative behavior avoids ending up at points with lower fitness values.
E.9 LEARNING RATE (T) ABLATIONS FOR GAMEOPT-HEDGE
To select the learning rate (1)) hyperparameter for the GAMEOPT-HEDGE algorithm, we performed hyperparameter sweep and tuned it accordingly. Figure 14 illustrates this process, showcasing the impact different !) values on the game convergence. Based on this, we selected the optimal performing value. In particular, Figure 14b shows how varying 17 influences the convergence to different equilibria at BO iteration t. The results demonstrate that the chosen facilitates equilibrium convergence within finite number of rounds, ensuring practical game convergence.
28

---

Published as a conference paper at ICLR 2025
Logees (best so far)
UCB Values vs Game Rouads
1.5
16
0.
3/0
Ntertions
Rounds
(a) LogFitness (BSF).
(b) Convergence of games.
CunnOpt Beige.io.. 1ro.1
GameGyt Hedge
Canndyy kt..
GandGyl Modge 1r1.5
CumeCyy Bedge
GaneCyy Hkdge
Figure 14: Performance of GAME HEDGE under different learning rate (1) values. The final value is set to ensure equilibrium convergence within a given number of rounds. As an example, we show in (14b) the convergence of different games to equilibria when 7) = 2.0.
E.10 UCB VALUES THE SAMPLED BATCHES
As discussed in Sections and 5.5, the novel insight and the main cause of benefit of the GAMEOPT framework lies in its ability to provide efficient (Iractable) acquisition function optimization by adopting game-theoretical perspective.
When comparing the methods based on the UCB values over BO iterations the GBI(4) domain, as demonstrated in Figure 15, we observe that GAMEOPT initially selects points with lower UCB values compared to GP-UCB. However, in later iterations, GAMEOPT identifies points with higher UCB values. This improvement is driven by the framework's leverage of equilibrium points, leading to superior exploration of the search space and ultimately more efficient optimization.
of Executed Points
Discovered Points
1:00
1.30
125
1.25
110
1.20
0.75
0.50
0.30
025
(a) Executed points.
(b) BSF logfitness valued point.
GameOpt-IBR
GameOpt-Hedge
PR
GP-UCB
Figure 15: UCB value of the (a): executed point (max UCB), and (b): best-so-far (BSF) logtitness
valued point over iterations under GBI(4) domain. Although initially GAMEOPT variations executed points with smaller UCB values compared to GP-UCB, its better exploration helps identify higher UCB valued points quickly.
E.11 EXPECTED IMPROVEMENT ACQUISITION FUNCTION
Although GAMEOPT is designed using the UCB acquisition function with sample complexity guarantee, we provide further empirical analysis across GP-based methods using a different acquisition function: expected improvement (EI) (Jones al., 1998). As demonstrated by the results on the GBI(4) dataset in Figure 16, GAMEOPT variations show superior performance compared to other GP-based baselines. They sample more diverse batches, as given in plots for (16c) sample batch diversity with respect to past and (16d) previously executed points.
E.12 COMPARISON WITH LATENT SPACE OPTIMIZERS
Our baselines involve acquisition function optimizers which directly operate large combinatorial search spaces. While there is a body of work employing latent space optimizers Koomez-Bombarelll al., 2018; Tripp et al., 2020: Deshwal & Doppa, 2021; Maus et al., 2022; Stanton al., 2022),
29

---

Published as a conference paper at ICLR 2025
Figees (best so far)
E1 of Executed Points
175
0.3
1.50
1.30
0.75
0.50
Hteraions
Berations
(a) Convergence speed (BSF).
(b) El of executed points.
Avg. Hamming Distance wet Initial Point
Avg. Pairwise Hamming Distance
Rtrations
[terations
(c) Batch diversity (w.rt. past).
(d) Batch diversity (pairwise).
GameOpt-IIB
GameOpt-Hedge
PR
GP-EI
Figure 16: Performance comparison of GP-based methods on the GBI(4) dataset using expected improvement (EI) acquisition function and batch size B In all experiments GAMEOPT with IBR and HEDGE subroutines discover better and more diverse protein sequences at much faster rate.
primary focus in this study is to tractably optimize the acquisition function directly on combinatorial search spaces, addressing the challenge of exhaustive exploration.
However, to provide insight, we compare GAMEOPT against Naive LSBO-(L-BFGS-B B) with second- order gradient-based optimizer (Gómez-Bombarelli al., 2018) and LADDER (Deshwal & Doppa, 2021) methods. The comparison, presented in Figure 17, performed using the (17a, 17c) RBF kernel and (17b,17d) structure-coupled kernel. The structure-coupled kernel is designed using an RBF kernel and a sub-sequence string kernel (Moss et al., 2020). Results indicate that GAMEOPT variations perform significantly better than the considered latent space optimizers. A notable limitation of latent space optimizers is their dependence on decoder. In our experiments, we trained a transformer- decoder using ESM-Iv feature embeddings (Meier et al., 2021), employing beam search for sequence generation. In contrast, our GAMFOPT approach does not require such an additional decoder and directly optimizes over the sequence space efficiently.
30

---

Published as a conference paper at ICLR 2025
LogFitness (best so far)
LogFitness (best so far)
0.8
Berattons
Berattios
(a) RBF kernel.
(b) Structure-coupled kernel.
Avg. Hamming Distance wet Point
Avg. Hamming Distance wrt Point
Tterations
Tberations
RBF kernel.
(d) crructure-coupled kernel.
CameOge-TBR
Gamei@tt-Fedde
Nolww-L.BO
TADDER
Best strobegy
Figure 17: Performance comparison of GAMEOPT against latent space optimizers: Naïve LSBO- (L-BFGS-BB B) (o6mez-Bombarde et al., 2018) and LADDER (Deshwal & Doppa, 2021) methods under GBI(4) domain with batch size B using kernels: RBF and structure-coupled kernel (Moss et al., 2020). Latent space optimizers perform poorly mainly because they rely on a decoder, which GAMEOPT variations eliminate and directly (tractably) optimize over combinatorial space.
31


Reviews:
[{"review_id": "J59lpu12a9", "reviewer": "Reviewer_VxGg", "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.", "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.\n\n- ***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.\n\np.s. Due to my limited domain expertise, I am not confident in assessing the novelty of the problem formulation in this specific application.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n- ***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.\n- ***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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "cWXWQSvFI5", "reviewer": "Reviewer_3y4p", "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.", "questions": "1.\tDoes this algorithm work without assumption $|\\mathcal{X}^{(i)}|=d$? It means that in this case the numbers of possible decision variables are different.\n2.\tWhat is the v function in Algorithm 2? Is that the r function defined in Definition 3.1?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.\tCombinatorial 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.\n2.\tSample complexity guarantees are provided to show the algorithm’s ability to achieve approximate Nash equilibrium.\n3.\tExperiments on protein design are comprehensive and ablation studies are provided.", "weaknesses": "1.\tTo 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.\n2.\tI 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "9L1e2CzpKe", "reviewer": "Reviewer_mcjS", "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.", "questions": "1. Is there any consideration of balance of exploration and exploitation? How is the data-efficiency guaranteed?\n2. What is the influence of batch size B? In what case may the algorithm perform worse?\n3. Why not compared baselines using tree-based surrogate models. As far as I know, the tree model is a suitable choice for protein design.\n4. How to prove that solving equation (2) is more tractable than solving other acquisition functions?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The discrete black-box optimization problems are important, and the proposed game-theoretical solution seems novel.\n2. The protein design is vital in drug discovery and healthcare.\n3. 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. \n2. 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].\n3. 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.\n4. 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. \n5. The literature review is insufficient. More baseline algorithms in combinatorial Bayesian optimization and general optimizers should be considered.\n\n[1] David Eriksson, et al.: Scalable Global Optimization via Local Bayesian Optimization. NeurIPS 2019.\n\n[2] Shuang Li, et al.: \"Why Not Looking backward?\" A Robust Two-Step Method to Automatically Terminate Bayesian Optimization. NeurIPS 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "TTyjrLq1Y7", "reviewer": "Reviewer_XU81", "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.", "questions": "See the weakness section.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Large-scale combinatorial optimization is an important challenge, though Bayesian optimization (BO) may not be the most typical approach for tackling it.\n- 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**\nThe 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:\n\n**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.\n\n**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. \n\nI’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).\n\n- **Lack of Critical Guarantee**\nIs 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.\n- **Limited Evaluation to Assess Practicality**\nHeuristic 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.\n- **Limited Novelty**\nThe 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.\n- **Missing Limitation**\nI 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.\n\n- **Citation**\n- [1] Daulton, Samuel, et al. \"Bayesian optimization over discrete and mixed spaces via probabilistic reparameterization.\"NeurIPS 2022\n- [2] Papenmeier, Leonard, et al., \"Bounce: reliable high-dimensional Bayesian optimization for combinatorial and mixed spaces.\" NeurIPS 2023\n- [3] Gruver, Nate, et al. \"Protein design with guided discrete diffusion.\" NeurIPS 2023\n- [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).\n- [5] Han, Minbiao, et al., \"No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes.\" UAI 2024.\n- [6] Chau, Siu Lun, et al., \"Explaining the uncertain: Stochastic shapley values for gaussian process models.\" NeurIPS 2023\n- [7] Kandasamy, Kirthevasan, et al., \"High dimensional Bayesian optimisation and bandits via additive models.\" ICML 2015.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)