Research map / Probabilistic and scientific modeling / Bayesian optimization
Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GameOpt, which selects batches of points as Nash equilibria of a cooperative game over discrete variables with a UCB reward, making GP-based Bayesian optimization tractable on combinatorial protein design spaces.
Problem
Bayesian optimization over large combinatorial, unstructured spaces (e.g., protein sequences with 20^n variants) is intractable because maximizing the acquisition function requires exhaustive search.
Approach
Define a cooperative game where each discrete variable (protein site) is a player choosing among its values, with rewards given by the GP-UCB function; compute game equilibria (via iterative best response or Hedge) as candidate evaluation points, decoupling the combinatorial decision space, with a sample-complexity bound to approximate Nash equilibria of the true function.
Key results
- GameOpt with IBR and Hedge subroutines consistently discovers higher-fitness protein sequences faster than GP-UCB, IBR-Fitness, PR and Random across all four protein datasets.
- GameOpt reduces acquisition optimization cost from O(d^n) to O(nd) per the paper's analysis.
- Theorem: GameOpt returns an epsilon-approximate Nash equilibrium after T = Omega(beta_T gamma_T / epsilon^2) iterations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GameOpt-Ibr instead of IBR-Fitness, PR, GP-UCB, or Random | Protein design optimization · Halogenase | best-so-far log fitness | Helped |
| Use GameOpt instead of PR or GP-UCB | Protein design optimization · GB1(4) | best-so-far log fitness | Helped |
| Use GameOpt instead of IBR-Fitness | Protein design optimization · GB1(4) | sampled batch diversity | Helped |
| Use GameOpt-Ibr or GameOpt-Hedge instead of baselines | Protein design optimization · GFP, 6 and 8 players | best-so-far log fitness | Helped |
| Use GameOpt-Ibr or GameOpt-Hedge instead of baselines | Protein design optimization · GB1(55), 10 players | best-so-far log fitness | Helped |
| Use GameOpt-Ibr or GameOpt-Hedge instead of baselines | Protein design optimization · GB1(55), 55 players | best-so-far log fitness | Helped |
| Increase GP-UCB initial training set from 100 to 500 points (ablation) | GP-UCB · GB1(4) | best-so-far log fitness | Helped |
| Vary batch size across B={1,3,5,10,50} (ablation) | GameOpt variants · Protein design datasets | best-so-far protein fitness | No clear effect |
| Use expected improvement instead of UCB as the acquisition function (ablation) | GameOpt · Protein design experiments | performance across reported metrics | Helped |
| Use a structure-coupled RBF and subsequence string kernel instead of the standard RBF kernel (ablation) | GameOpt · Protein design experiments | convergence to high log fitness | Helped |
Surprising findings
- GP-UCB, which globally optimizes UCB where feasible, saturates when its initial GP is trained on only 100 points, while GameOpt remains robust.
- PR and Random perform poorly on Halogenase, and PR is not competitive even though it is the closest prior BO method.
Limitations
- GP-UCB achieves higher UCB values early on; GameOpt trades acquisition optimality for tractability.
- Experiments use an oracle MLP trained on non-exhaustive data as ground truth, and a batch size of 5 that the authors acknowledge is restrictive.
- Price of anarchy guarantees for unstructured domains are not established.
Experimental setup
Datasets: GB1(4) GB1(55) Halogenase GFP
Benchmarks: GB1(4) GB1(55) Halogenase GFP
Metrics: log fitness of best-so-far batch diversity (Hamming distance) fraction of global optima discovered
Baselines: GP-UCB IBR-Fitness PR Random DLS DLS_Best Naive LSBO-(L-BFGS-B) LADDER
Builds on: GP-UCB Hedge probabilistic reparameterization
Closest papers by meaning
- A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences (NeurIPS 2024 · similarity 0.87)
- Improving protein optimization with smoothed fitness landscapes (ICLR 2024 · similarity 0.87)
- ProteinOPD: Towards Effective and Efficient Preference Alignment for Protein Design (NeurIPS 2026 · similarity 0.86)
- Tree Search-Based Evolutionary Bandits for Protein Sequence Optimization (AAAI 2024 · similarity 0.86)
- Bayesian Optimization of Functions over Node Subsets in Graphs (NeurIPS 2024 · similarity 0.86)
- Bayesian Optimization of Antibodies Informed by a Generative Model of Evolving Sequences (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.