# Tree Search-Based Evolutionary Bandits for Protein Sequence Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 53 references that are in the map.
- First posted on arXiv 8 Jan 2024.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Evaluating Protein Transfer Learning with TAPE](https://mlsanity.com/paper/1906.08230/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [ProGen2: Exploring the Boundaries of Protein Language Models](https://mlsanity.com/paper/2206.13517/) (2022)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Conditioning by adaptive sampling for robust design](https://mlsanity.com/paper/1901.10060/) (2019)
- [Accelerating Bayesian Optimization for Biological Sequence Design with Denoising Autoencoders](https://mlsanity.com/paper/2203.12742/) (2022)
- [Neural Contextual Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2012.01780/) (2020)
- [AdaLead: A simple and robust adaptive greedy search algorithm for sequence design](https://mlsanity.com/paper/2010.02141/) (2020)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Autofocused oracles for model-based design](https://mlsanity.com/paper/2006.08052/) (2020)
- [Design by adaptive sampling](https://mlsanity.com/paper/1810.03714/) (2018)
- [Communication Efficient Distributed Learning for Kernelized Contextual Bandits](https://mlsanity.com/paper/2206.04835/) (2022)
- [Rarely-switching linear bandits: optimization of causal effects for the real world](https://mlsanity.com/paper/1905.13121/) (2019)
- [Bandit Theory and Thompson Sampling-Guided Directed Evolution for Sequence Optimization](https://mlsanity.com/paper/2206.02092/) (2022)

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

- [PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs](https://mlsanity.com/paper/2601.20539/) (2026)
- [Boosting In-Silicon Directed Evolution with Fine-Tuned Protein Language Model and Tree Search](https://mlsanity.com/paper/2511.09900/) (2025)
- [Instance-dependent Stochastic Lipschitz bandit](https://mlsanity.com/paper/2605.29748/) (2026)

## Abstract (arXiv)

While modern biotechnologies allow synthesizing new proteins and function measurements at scale, efficiently exploring a protein sequence space and engineering it remains a daunting task due to the vast sequence space of any given protein. Protein engineering is typically conducted through an iterative process of adding mutations to the wild-type or lead sequences, recombination of mutations, and running new rounds of screening. To enhance the efficiency of such a process, we propose a tree search-based bandit learning method, which expands a tree starting from the initial sequence with the guidance of a bandit machine learning model. Under simplified assumptions and a Gaussian Process prior, we provide theoretical analysis and a Bayesian regret bound, demonstrating that the combination of local search and bandit learning method can efficiently discover a near-optimal design. The full algorithm is compatible with a suite of randomized tree search heuristics, machine learning models, pre-trained embeddings, and bandit techniques. We test various instances of the algorithm across benchmark protein datasets using simulated screens. Experiment results demonstrate that the algorithm is both sample-efficient and able to find top designs using reasonably small mutation counts.