  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.
