# Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design

arXiv: https://arxiv.org/abs/2409.18582 · HTML: https://mlsanity.com/paper/2409.18582/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 62 references that are in the map.
- First posted on arXiv 27 Sep 2024.

## Builds on (most cited first, 29 of 29)

- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Neural Architecture Search with Bayesian Optimisation and Optimal Transport](https://mlsanity.com/paper/1802.07191/) (2018)
- [Sample-Efficient Optimization in the Latent Space of Deep Generative Models via Weighted Retraining](https://mlsanity.com/paper/2006.09191/) (2020)
- [Accelerating Bayesian Optimization for Biological Sequence Design with Denoising Autoencoders](https://mlsanity.com/paper/2203.12742/) (2022)
- [Bayesian optimization for materials design](https://mlsanity.com/paper/1506.01349/) (2015)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Local Latent Space Bayesian Optimization over Structured Inputs](https://mlsanity.com/paper/2201.11872/) (2022)
- [ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations](https://mlsanity.com/paper/1908.01425/) (2019)
- [Dealing with Integer-valued Variables in Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1706.03673/) (2017)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [BOSS: Bayesian Optimization over String Spaces](https://mlsanity.com/paper/2010.00979/) (2020)
- [Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces](https://mlsanity.com/paper/2111.01186/) (2021)
- [Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization](https://mlsanity.com/paper/2210.10199/) (2022)
- [Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos](https://mlsanity.com/paper/1703.01138/) (2017)
- [Population-Based Black-Box Optimization for Biological Sequence Design](https://mlsanity.com/paper/2006.03227/) (2020)
- [Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spaces](https://mlsanity.com/paper/2307.00618/) (2023)
- [Mercer Features for Efficient Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2012.07762/) (2020)
- [Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings](https://mlsanity.com/paper/2303.01774/) (2023)
- [Bayesian Optimization over Hybrid Spaces](https://mlsanity.com/paper/2106.04682/) (2021)
- [No-Regret Learning in Unknown Games with Correlated Payoffs](https://mlsanity.com/paper/1909.08540/) (2019)
- [Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimization](https://mlsanity.com/paper/2306.09803/) (2023)
- [Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation](https://mlsanity.com/paper/2203.07322/) (2022)
- [Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework](https://mlsanity.com/paper/2012.07320/) (2020)
- [Combinatorial Black-Box Optimization with Expert Advice](https://mlsanity.com/paper/2006.03963/) (2020)
- [Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation](https://mlsanity.com/paper/2307.13371/) (2023)
- [Bounding Inefficiency of Equilibria in Continuous Actions Games using Submodularity and Curvature](https://mlsanity.com/paper/1903.00950/) (2019)
- [ODBO: Bayesian Optimization with Search Space Prescreening for Directed Protein Evolution](https://mlsanity.com/paper/2205.09548/) (2022)
- [No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes](https://mlsanity.com/paper/2405.08318/) (2024)

## Built on by (most cited first, 4 of 4)

- [Steering Generative Models with Experimental Data for Protein Fitness Optimization](https://mlsanity.com/paper/2505.15093/) (2025)
- [Thompson Sampling via Fine-Tuning of LLMs](https://mlsanity.com/paper/2510.13328/) (2025)
- [Robust Bayesian Decision Making under Adversarial Uncertainty](https://mlsanity.com/paper/2607.08590/) (2026)
- [Feedback-Calibrated Protein Optimization with Batch-Aligned Tail Arbitration](https://mlsanity.com/paper/2609.37808/) (2026)

## Abstract (arXiv)

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 textitcombinatorial 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 a cooperative game between the different optimization variables, and selects points that are game textitequilibria 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 textitprotein design problem and validate its performance on four real-world protein datasets. Each protein can take up to 20X 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.