Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design

We thank the reviewer for their detailed feedback. We address your concerns and questions below.

• [Problem Statement Clarification]: As we clearly state in line 103 that $x$ consists of $n$ discrete variables, hence $x=(x^1, \dots, x^n)$, which makes it $n$-dimensional. If each component of $x$, namely $x^i$ has $d$ possible values (or you can think of it as categories), then $x$ can take $d^n$ many configurations, that is the number of all possible values that $x$ can take. Within the protein design context, each discrete variable (protein site) $x^i$ can take $20$ possible (aminoacid) choices, hence, all possible values that the protein $x$ can take is $20^n$, where $n$ is the number of protein sites (discrete variables) and this makes $d=20$. Note line 102 that we already define $f$ over domain $\mathcal{X}$, which means over the possible values of $x$. Also note that $\mathcal{X}=\mathcal{X}^{(1)} \times \dots \times \mathcal{X}^{(n)}$. However, we cannot say that the objective function is of the form that the reviewer describes. Because $f$ is defined over the joint configuration $x$, not decomposable to individual discrete variables.

• [Clarification on the reward function]: The reward $r^i$ is defined over the joint configuration $x$ and takes one argument which is $x$. We state, as the reviewer calls, two inputs “$x^i, x^{-i}$”, to show the joint configuration made by the strategy of player $i$ and the strategy of the rest of the players (denoted with $^{-i}$ notation). "arg eq" is an operator that returns the joint configuration(s) such that it forms an equilibrium according to UCB, hence equation (2) is a mathematical expression to show equilibria. The payoff function $v$ is the reward function in Definition 3.1. We have only used the conventional symbols from game theory in defining equilibrium finding subroutines. Finally, the equilibria are computed by breaking down the complex decision space into individual decision sets, because as we show in equilibrium finding subroutines (e.g. IBR), in each round the players select a strategy (action) by fixing the others’ strategies. Hence, this decomposes the global search over all possible configurations for $x$ to search over individual decision sets for $x^{(i)}$.

• [Guarantee]: Finding the Nash equilibrium is not equivalent to maximizing the objective function $f$. We explained in Section 3 (line 181) that GameOpt leverages local optima. In Section 4, we provided a sample complexity analysis for GameOpt to reach an approximate equilibrium of the true objective function $f$. Section 4 clearly explains that GameOpt provides an approximation. We disagree with the statement that “global optimization…the computational overhead of the acquisition function becomes comparable”. The global optimization (GP-UCB baseline) is intractable with $O(d^n)$ complexity, assuming that each dimension is of size $d$. Whereas, with e.g. GameOpt-IBR in which each player generates the best response w.r.t the previous joint strategy has the total complexity of $O(nd)$ assuming that each $\mid \mathcal{X}^{(i)} \mid = d$ for players $i=1,...,n$. Further, as we discuss the computational complexity in Appendix E4 and E3, our results show that in all domains, particularly for the larger spaces, GameOpt provides tractable acquisition function optimization with less compute amount required.

• [Novelty]: As stated by the reviewer, the provided references operate on continuous spaces. Whereas, we clearly state in our paper that “novel game-theoretical approach to combinatorial BO”. As also stated by the reviewer “While the specific combination of game theory, combinatorial optimization, and Bayesian optimization may be novel...”, since there is no study that specifically combines game theory and combinatorial BO by treating each discrete variable as a player, we still think that this makes GameOpt novel (also supported by the reviewers VxGg and mcjS).
• • [A clarification for the provided reference [5]]: [5] seems to be published after July 2024, counted as a ‘very recent work’ by the ICLR guide (https://iclr.cc/Conferences/2025/ReviewerGuide) (see the last Q&A). We were unaware of this work, however, we are happy to cite it in our paper.
• • While Shap and GameOpt both draw inspiration from game theory, their applications and objectives differ significantly. Shap is primarily used for interpretability and explanation by focusing on the contribution of individual dimensions to a prediction. In contrast, GameOpt leverages game theory to optimize a combinatorial space by finding equilibrium points of an acquisition function.

[5] Han, Minbiao, et al., "No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes." UAI 2024.

• [Additional Evaluation with Different Action/Dimension Sizes]: GameOpt approach is applicable when each dimension $x^i$ (players) has a different action set ($\mathcal{X}^{(i)}$) size. We provide additional experiments in Appendix E12 considering different action set sizes. The results in Figure 17 clearly demonstrate the applicability and generalizability of GameOpt to such problem domains. Further, there is no significant performance difference between individual players and player grouping settings with varying action set sizes. We also modified our statement (lines 104-105) in the main text.

• [Comparison with not relevant protein optimization methods]: As baselines, we considered the combinatorial BO methods that target efficient acquisition function optimization. One can find a vast amount of diverse approaches (from generative models to LLMs, etc.) to apply to the protein design problem. However, in our study, we propose GameOpt for combinatorial BO, with an application to an interesting real-world problem (which demonstrates its success and applicability in such a complex problem). Hence, comparisons against all other protein design approaches are beyond our scope.
• • “...why not reduce the dimensionality of the embedding features to make them more tractable for the naïve GP-UCB?”: In our paper, we address acquisition function optimization over large combinatorial search spaces. Even though we’d reduced the dimensionality of the embedding features for the GP surrogate, that would not change the searching over combinatorial space to sample evaluation points by optimizing the acquisition function. Hence, that would only help for the surrogate model fitting part, but not the main problem addressed in our study. We hope this clarifies the misunderstanding. We also want to highlight that the proposal to reduce dimensionality is not as trivial as the reviewer makes it appear. We need to explore regions where potentially no data is available and dimensionality reduction methods would most likely ignore this altogether.
• • [Outdated methods]: We identify appropriate baselines that target acquisition function optimization, as this is our main focused problem. Only to provide interesting insight, we further experiment on benchmark 25D-PestControl problem [1]. As given in Appendix-E13 of the updated manuscript, we compare our GameOpt approach against some high dimensional combinatorial BO methods [2,3], showing (see Figure 19) that GameOpt provides faster convergence to better solutions compared to these methods.
• • [Additional task]: We performed experiments on domains with different combinatorial search space sizes, from 20^3 to 20^55. Since the main problem we address is how to efficiently and strategically optimize the acquisition function over large combinatorial search spaces, we think that demonstrating the performance over a diverse size of search space is aligned with our addressed problem, and supports our empirical evaluation. However, to address your concern, we further experimented on the benchmark 25D-PestControl problem [1], with search space size 5^25, as explained above.

Overall, with the additional evaluations we provided, we showed the applicability of GameOpt under various problem domains with different tasks and domain structures, and against diverse methods. We hope that these points clarified your concerns. We are happy to expand them further if needed.

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

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

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

Dear Reviewer XU81,

As we approach the end of the discussion period, we would like to ask if there is any additional information we can provide that might influence your evaluation of the paper. We believe our previous response with extensive explanations and additional experiments conducted has effectively addressed your initial concerns and clarified some points that may have been overlooked.

Thank you once again for your consideration of our work.

We thank the reviewer for the follow-up comments, which we clarify them below:

1. Clear notation is provided in the main text

• We have re-iterated our rebuttal (which we provided to you) and made the necessary changes in the main text (see updated manuscript). For the payoff/reward function notation, we have updated our manuscript accordingly. However, we identified minor changes as we used the same notation and statements both in our explanation for rebuttal and the manuscript.

• Also note that all other reviewers found the presentation clear with a good score, stating that "The presentation is clear and the idea is easy-to-follow.". Hence, instead of a major revision, the minor editions we made in the updated manuscript have improved the clarity of our text.

2. Our claim is theoretically backed up for local optimality & a discussion on the global optimality challenge is already provided in the main text

• As noted by the reviewer, while presenting GameOpt, we state it as "A form of local optimality", given the discussion paragraph in Section 3. For a theoretical backup for this, we already provided a sample complexity analysis (Section 4).

• We already carefully addressed about global optimality with the "price of anarchy (PoA)" discussion in Section 3. We have explained how such PoA guarantees do not readily apply to our setting because of a lack of submodularity of the objective function. And theoretically bounding the suboptimality and steering players to the best equilibrium is an active and challenging area of research. We already provided a detailed discussion to justify why evaluating GameOpt solely as an optimization technique is challenging, and how GameOpt’s filtering-out suboptimal equilibria step contributes to its quality and robustness.

3. Comprehensive experiments with ablation studies

• We propose GameOpt for combinatorial Bayesian optimization with an application to protein design. As we stated in our paper (lines 17-20, 68-70, 82-84, etc), our main problem focus is tractable acquisition function optimization in BO over large combinatorial spaces.
• Considering this, we identified our baselines from related works on combinatorial BO which directly target acquisition function optimization. We have presented 6 main problem domains on which we evaluate our proposed method fairly against baselines under various combinatorial search space sizes. We consider real-world datasets and problem context, which further shows the applicability of our method on real-world important problems. We have provided many ablations, including computational complexity, batch size analyses and further comparisons to provide interesting insight.
• As also stated by Reviewer 3y4p (”It’s good to see substantial experiments…Experiments are comprehensive and ablation studies are provided”), our work includes extensive analysis with detailed ablations, providing in-depth insights into the performance and flexibility of our method.

We hope in the light of above clarifications, you could reconsider your evaluation.

We thank the reviewer for their feedback. We are happy that you recognize the novelty of our GameOpt framework, with clear idea and presentation on an important real-world problem application. We address your concerns and questions below, including additional experiments and paper edits inspired by your comments.

• [GameOpt balances exploration and exploitation & Q1]: In GameOpt, we indeed balance exploration and exploitation. Mainly, the UCB itself captures the exploration-exploitation tradeoff. GameOpt further has the following mechanisms, which help to address this:
• • (1): We introduce random restarts in the M equilibrium computation step. As given in Algorithm-4 in Appendix B, the M parallel games with random initializations collect M equilibria. As given in step 5, we start with a random protein sequence. As also stated in Algorithms 2 and 3 (step 2), each of these games starts with a random joint strategy.
• • (2): We implement filtering (see step 5 of Algorithm-1). We collect a larger amount of M equilibria, then select the top-B. We hope that this also clarifies your first question.

• [Theoretical results]: We thank the reviewer for their suggestion on assuming convexity. However, note that [1] operates on a continuous domain. Whereas, we are not sure how convexity directly can be applied to our combinatorial setting. Submodularity could have been leveraged, only if, the objective function were submodular. And this does not readily apply to our setting. The regret bound can be similar to GP-UCB, however, as we extensively demonstrate with our empirical evaluations GameOpt achieves a similar regret level with a tractable approach, which is important as the combinatorial search space scales up.

• [Additional problem domain]: We experimented on problem domains with different sizes of combinatorial search spaces, from 20^3 to 20^55. Since the main problem we address is how to efficiently optimize the acquisition function over large combinatorial search spaces, demonstrating the performance over a diverse size of search space is already aligned with our addressed problem.
• • However, to address your concern, we further experiment on the benchmark 25D-PestControl problem [2], with a search space size 5^25. As given in Appendix-E13 of the updated manuscript, we compare our GameOpt approach against some high dimensional combinatorial BO methods [3,4]. The additional analysis clearly supports (see Figure 19) that GameOpt generalizes well to other problem domains, providing an outperforming performance.

• [Batch size more ablations & Q2]: We now also show the performance comparison under batch sizes $B=1$ and $B=3$ on Halogenase and GB1(4) domains, in Appendix-E7 of the updated manuscript. As given in Figure-12, even under a more restricted setting on both problem domains, GameOpt achieves superior performance against baselines, although initially surpassed by GP-UCB under batch size 1. As the batch size increases, GameOpt’s optimistic game approach benefits from parallelism and collects diverse local optima, hence, GameOpt surpasses. We hope that this also clarifies your second question.

• [Related Work]: We would like to clarify that the provided references operate on continuous domains, whereas we focus on combinatorial domains. We nevertheless included the provided works in our related work section of the updated manuscript. Furthermore, we considered combinatorial BO approaches that are mainly categorized into two: (1) targeting the acquisition function optimization–which is our main focus, and (2) targeting the surrogate modeling with discrete variables. We added the provided references to the second category, for which we offer a general overview, as our primary emphasis remains on the first category.

• [Surrogate model choice & Q3]: For a fair comparison, we selected methods that target acquisition function optimization over large combinatorial domains (our main focus). Using some other type of surrogate modeling would not be fair as in our evaluation we fix the surrogate model for all BO methods and evaluate different acquisition function optimization methods. Please also see that in Appendix-E11 (Figure 16) we already provide additional experiments using surrogate models with different design choices. Specifically, we use GP defined with string kernels, which clearly demonstrates that GameOpt is effective under different surrogate model design choices.

• [Tractability of GameOpt]: With equation (2), we decouple the combinatorial search space into individual search (decision) sets (as illustrated in Figure-1). For instance, considering GameOpt-IBR, each player generates the best response w.r.t the previous joint strategy with the total complexity of $O(nd)$ assuming that each $\mid \mathcal{X}^{(i)} \mid = d$ for players $i=1,...,n$. Step 5 of Algorithm 2 finds the maximum valued element in a set with fixed size “n”, that is the number of players. Note that the global optimization which is performed by GP-UCB is intractable with $O(d^n)$ complexity. We provided a detailed discussion on the complexity and computational cost in Appendix E4 and E3.

Overall, with the additional evaluations we provided, we showed the applicability of GameOpt under various problem domains with different tasks and domain structures, and against diverse methods. We hope that these points clarify your concerns. We are happy to expand them further if needed.

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

[2] 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.

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

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

We thank the reviewer for the follow-up comments, which we clarify them below:

• [Appropriate baselines & fair comparison]: We highlight that our problem focus is: tractable acquisition function optimization in BO over large combinatorial spaces.
• 1. For a fair and meaningful comparison and evaluation of our proposed method, we considered “baselines” from the same problem focus. The mentioned methods (e.g. Bounce, BODi) are not directly comparable, because they address creating nested embeddings for the GP surrogate model. In our method, we fix the GP surrogate for the BO methods and compare the acquisition function optimizers. Hence, comparing against those methods directly would not provide a meaningful evaluation because they don’t target the same problem. We can only integrate our method into their framework’s acquisition function optimization, which we already did and showed in additional experiments presented in Appendix E13.
• 2. Bounce and BODi use local search to optimize the acquisition function, which we have already compared our GameOpt approach against in the protein design context.
• 3. As also stated by Reviewer 3y4p (”It’s good to see substantial experiments…Experiments are comprehensive and ablation studies are provided”), our work includes extensive analysis with detailed ablations, providing in-depth insights into the performance and flexibility of our method.
• 4. From an optimistic perspective, the relatively limited number of methods in the context of acquisition optimization highlights how underexplored this specific problem is. This further underscores the relevance and contribution of GameOpt in this context.

• [Additional analysis in Appendix E13]: As we explain above, additional methods are not GameOpt's baselines. To clarify, we only provide further analysis in Appendix E13 to show how GameOpt can also be integrated with other high-dimensional BO methods (to their acquisition function optimization). This analysis was already beyond our scope, nevertheless, supported GameOpt’s effectiveness even more & showed interesting insight & addressed your concern.

• 1. GP-UCB cannot be added because it is intractable, which we try to address this problem throughout our paper. The problem search space is 5^25 (much larger than the search spaces we had shown in GP-UCB results), and it is not computationally feasible to search for the optimal solution within this huge space in each BO iteration. Also note that, none of the high-dimensional BO methods that the reviewer is most concerned about, compare their methods against GP-UCB.
• 2. Showing how well the PR method integrates with other high-dimensional BO methods is not in our scope. Hence it is not included in Appendix E13. We have already shown with extensive experiments on various search space sizes and batch size settings that GameOpt outperforms PR by discovering better solutions much faster.
• 3. Lastly, Bounce and BODi use local search to optimize the acquisition function, which we have already compared our GameOpt against such local search methods in the protein design context, as presented in Appendix E3.

• We appreciate the statistical test suggestion, however, our results clearly demonstrate that GameOpt outperforms baselines. It converges much faster, to higher fitness-valued solutions. Further, how we evaluate the performance is already aligned with the considered related works. Note that, all previous works that the reviewer suggested, measure the performance by tracking the metric: best objective value observed throughout BO iterations. We, on the other hand, also provide additional metrics detailed in Section 5 and with further analyses in Appendix E.

We hope that these key points clarified your questions.

We thank the reviewer for their feedback and for supporting our paper! We are happy that you recognize the sample efficiency guarantee for the proposed GameOpt framework and our comprehensive empirical evaluation with ablation studies. We address your concerns and questions below.

• [Nash equilibrium insight]: (1) Our sample complexity analysis provides an insight into the solution obtained by the GameOpt and how it guarantees an approximation ($\epsilon$-approximate Nash equilibrium) of the underlying function $f$. (2) We have already shown with GB1(4) experiment results (see Figure-2(b)) how close the solutions obtained via GameOpt-IBR and GameOpt-Hedge to the “Best Solution”, that is the global optimal solution for the GB1(4) problem. Further, as shown in Appendix-E7 (Figure 11), when batch size is increased, GameOpt benefits from collecting more local optima and converges much faster to the global optimal solution compared to other baselines.

• [Computational efficiency of GameOpt - Step 5]: The steps 4 & 5 are the key steps that make GameOpt tractable compared to global optimizer (GP-UCB). For instance, considering GameOpt-IBR, the total complexity of generating equilibria is $O(nd)$ assuming that each $\mid \mathcal{X}^{(i)} \mid = d$ for players $i=1,...,n$. Note that the global optimization which is performed by GP-UCB is intractable with $O(d^n)$ complexity.

• [Q1 & Additional experiments with varying dimension (action set) sizes]: The GameOpt approach is applicable when each dimension $x^{(i)}$ (players) has a different action set ($\mathcal{X}^{(i)}$ ) size. Prompted by your feedback, we provide additional experiments in Appendix E12 considering different action set sizes. The results in Figure 17 clearly demonstrate the applicability and generalizability of GameOpt to problem domains with unequal action set sizes. Further, there is no significant performance difference between individual players and player grouping settings with varying action set sizes. To clarify this, we also modified our statement (lines 104-105) in the main text.

• [Reward function $v$]: Yes, the payoff function $v$ is the reward function $r$ in Definition 3.1. We have only used the conventional symbols from game theory in defining equilibrium finding subroutines.

Overall, with the additional evaluations we provided, we showed the applicability of GameOpt under various problem domains with different tasks and domain structures, and against diverse methods. We hope that these points clarify your concerns. We are happy to expand them further if needed.

We thank the reviewer for their feedback. We are happy that you recognize our GameOpt framework as interesting, and acknowledge its sample efficiency guarantee. We address your concerns and questions below.

• [BO guarantees]: The regret bound can be similar to the global optimizer GP-UCB, however, as we extensively demonstrate with our empirical evaluations that GameOpt achieves a similar regret level with a tractable approach compared to intractable GP-UCB, which is crucial as the combinatorial search space scales up.

• [Comparison with high-dimensional BO methods]: As we discussed in Section 3.2, the combinatorial BO methods can be categorized into two: (1) the methods directly focus on surrogate modeling with discrete variables, and (2) the methods addressing acquisition function optimization within discrete search spaces. Since our proposed approach GameOpt falls into the second category, we identified our baselines from those methods. Hence, in our evaluation, we fix the surrogate model the same for all BO methods and evaluate different acquisition function optimization methods, unlike other high-dimensional BO methods that operate on surrogate modeling. Hence, such suggested methods would not be appropriate “baselines” for GameOpt.
• • However, to address your concern, we further compare GameOpt against two high-dimensional BO methods [1,2] on a benchmark 25D-PestControl problem [3], with a search space size 5^25. We provide this further analysis in Appendix E13 of the updated manuscript. This additional experiment clearly shows (see Figure 19) that GameOpt provides faster convergence to better solutions compared to these methods, supporting its integration with other high-dimensional methods. Further, it shows that GameOpt generalizes well to other combinatorial BO problem domains.

• [Finding Nash equilibrium]: As we discuss in Section 3.1. (lines 234-235), we do not imply that solvers are always guaranteed to find the NE; This is true only under some conditions (line 236). In fact, we introduce Algorithm-3 by saying that it finds coarse correlated equilibrium only.

• [Price of Anarchy]: As we stated in Section 3 (lines 196-197), the provided PoA guarantee does not readily apply to our setting, because the underlying objective function (protein fitness function in the context of protein design) is not submodular. Further, bounding the suboptimality and steering players to the best equilibrium is an active and challenging area of research. We already provided a detailed discussion to justify why evaluating GameOpt solely as an optimization technique is challenging, and how GameOpt’s filtering-out suboptimal equilibria step contributes to its quality and robustness (lines 200-202).

Overall, with the additional evaluations we provided, we showed the applicability of GameOpt under various problem domains with different tasks and domain structures, and against diverse methods. We hope that these points clarify your concerns. We are happy to expand them further if needed.

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

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

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

Dear Reviewer VxGg,

As we approach the end of the discussion period, we would like to ask if there is any additional information we can provide that might influence your evaluation of the paper. We believe our previous response with additional experiments conducted has effectively addressed your initial concerns and clarified some points that may have been overlooked.

Thank you once again for your thoughtful consideration of our work.