Bandit Theory and Thompson Sampling-Guided Directed Evolution for Sequence Optimization
Authors: Hui Yuan
Chengzhuo Ni
Huazheng Wang
Xuezhou Zhang
Le Cong
Csaba Szepesvari
Mengdi Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: optimization
evolution
bandit
regret
Thompson sampling

Abstract: Directed Evolution (DE), a landmark wet-lab method originated in 1960s, enables discovery of novel protein designs via evolving a population of candidate sequences. Recent advances in biotechnology has made it possible to collect high-throughput data, allowing the use of machine learning to map out a protein's sequence-to-function relation. There is a growing interest in machine learning-assisted DE for accelerating protein optimization. Yet the theoretical understanding of DE, as well as the use of machine learning in DE, remains limited.
In this paper, we connect DE with the bandit learning theory and make a first attempt to study regret minimization in DE. We propose a Thompson Sampling-guided Directed Evolution (TS-DE) framework for sequence optimization, where the sequence-to-function mapping is unknown and querying a single value is subject to costly and noisy measurements. TS-DE updates a posterior of the function based on collected measurements. It uses a posterior-sampled function estimate to guide the crossover recombination and mutation steps in DE. In the case of a linear model, we show that TS-DE enjoys a Bayesian regret of order $\tilde O(d^{2}\sqrt{MT})$, where $d$ is feature dimension, $M$ is population size and $T$ is number of rounds. This regret bound is nearly optimal, confirming that bandit learning can provably accelerate DE. It may have implications for more general sequence optimization and evolutionary algorithms. 

Bandit Theory and Thompson Sampling-Guided Directed Evolution for Sequence Optimization
Hui Yuan Chengzhuo Ni?, Huazheng Wang', Xuezhou Zhang", Le Cong?, Csaba Szepesvári and Mengdi Wang
Department of Electrical and Computer Engineering. Princeton University School of Electrical Engineering and Computer Science, Oregon State University Department of Pathology and Department of Genetics, Stanford University
Department of Computing Science, University of Alberta DDeeMMind +
Abstract
Directed Evolution (DE), a landmark wet-lab method originated in 1960s, enables discovery of novel protein designs via evolving population of candidate sequences. Recent advances biotechnology has made it possible to collect tigh-thrrughhut data, allowing the use of machine learning map function relation. There is a growing interest in machine aasistee DE for accelerating protein optimization. Yet the theoretical understanding of DE, as well as the use of machine learning in DE, remains limited. In this paper, we connect DE with the bandit learning theory and make a first attempt study regret minimization in DE. We propose a Thompson Sampling-guided Directed Evolution (TS-DE) framework for sequence optimization, where the eqquence-to-functtin mapping is unknown and querying a single value is subject to costly and noisy measurements. TS-DE updates a posterior of the function based on collected measurements. It uses posterior-sampled function estimate to guide the crossover recombination and mutation steps DE. In the case of linear model, we show where feature
protein's sequence-to-
that TS-DE enjoys a Bayesian regret of order dimension, M is population size and T is number of rounds. This regret bound is nearly optimal, confirming that bandit learning can provably accelerate DE. It may have implications for more general sequence optimization and evolutionary algorithms.
Introduction
Protein engineering means design nucleic acids sequence for maximizing utility function that measures certain fitness or biochemical/enzymatii properties, i.e., stability, binding affinity, catalytic activity. Due the combinatorial sequence space and lack of knowledge about the sequence-to-function map, engineering and identifying optimal protein designs were a quite daunting task. It only until recently that synthesis of nucleic acid sequences and measurement of protein
AAuthors' emails are:
{huiyuan, cn10, x27392, /engdss//princeeon. edu,
huazheng. wang@oregonstata. edu, congle@stant ord. edu, szepesva@ualberta. ca.
'enngdi Wang acknowledges support NSF grants DMS- 1953666, IIS (S-22107 2107304, CMMI-1653435, and ONR grant 1006977. Le Cong acknowledges support by NIH grant 133--HG011 1316, Donald and Delia Baxter Foundation grant, and NSF grant
Csaba Szępesvári gratefully acknowledges the funding from Natural Sciences and Engineering Research Council (NSERC) of Canada, "Design.R Al-assisted CPS Design" (DARPA) project and the Canada CIFAR AI Chairs Program for Amii.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

function became reasonably scalable A1 57 allowing rational optimization or directed evolution of protein designs. Nonetheless, because of the complex landscape of protein functions and the bottleneck of wet-lab experimentation, this remains very difficult problem.
Directed evolution (DEE), one of the top molecular technology breakthroughs in the past century, demonstrates human's 's ability to engineer proteins at will. DE is method for exploring new protein designs with properties of interest and maximal utility, by mimicking the natural evolution. It works by artificially evolving a population of variants, via mutation and recombination, while constantly
selecting high-potential variants [ 2 33 25 49 41. The development of directed evolution
methods was honored in 2018 with the awarding of the Nobel Prize in Chemistry to Frances Amold
for evolution of enzymes, and George Smith and Gregory Winter for phage display 44 47 53
See
Figure 1.I for illustrations of mutation and crossover recombination.
DE practitioners' major considerations center cost and data quality. First, the ability to synthe- size and mutate new biological sequences have been exponentially improved thanks to synthetic chemistry advances. Second, given a popula- tion of sequences S, selecting and identifying the set of optimal sequences is straightforward, using low-cost parallel sequencing which works well with pooled selection assays. Third, us- ing pooled measurement to evaluate the average value of protein function (mean fitness) over population S is generally easy, as such bulk measurements is low-cost and high-quality. Fi- nally, querying (z) for given is often expen- sive and time-consuming, and the cost adds up quickly if many queries are needed. It can be de- sirable to perform this procedure in small-scall batches to optimize time and resource consump- tion.
Targeted sites
Original
Mutated seq.
Parents
Possible children
Figure 1.1: Illustration of mutation and crossover recombination. Mutating sequence means to re- place a targeted or random entry (site) by a ran- dom or designated value. Recombination involves two or multiple sequences. For example, parent sequences can crossover, exchange subsequences and generate children.
Such difficulties have motivated scientists to ap- ply machine learning approaches to accelerate DE, beginning with Fox et al. [16] and followed by many. Recent development of directed evolution have increasingly utilized in silico exploration
and machine learning beyond experimental approaches [57] 15 12, 45 18 50, 46). While these
attempts have proved to successful simulation and sometimes in real experiments, little is known about the statistical theory of DE.
In this paper. primary objective to bridge the directed evolution process with bandit learning theory. In particular, we want to express machine learning-assisted DE as a bandit optimization process, with theoretical justification. Further, we aim to understand how a machine learning model, as simple as linear, can accelerate DE and reduce the overall cost of evaluation. Specifically, we propose a Bayesian bandit model for DE, namely the Thompson Sampling-guiee guided Directed Evolution framework, which combines posterior model sampling with directed mutation and recombination. The theoretical analysis shows that the crossover selection mimics an optimization iteration, and the optimization progress is proportional to level of population diversity. In the case of the linear model, V /MT/ that depends polynomially on feature dimension d and optimally in batch size M and time steps T. We finally harmonize our theoretical analysis with set of simulation and real-world experiment.
establish Bayesian regret bound (d
The scope of this work is to provide simplified mathematical model and basic theoretical understanding of an evolutionary-bant process that is common directed evolution. We emphasize that our framework is theoretical simplification, assuming linear objective over a hy-
Important Remark
xŌ(+) ignores the logarithmic terms.
*Our TS-DS regret has two extra vd factors compared to the classic result that the optimal regret for lincar bandits of Õ MT). One vd comes from our problem setting where the norm of cach action is O 0(vā, /d). Another factor of Vd is due the evolutionary nature of DE. See the remark in $5.2 for more details.

---

percube. In real-world experimental systems, one needs to consider prior knowledge about the system and applying any machine learning method would require careful calibration and customization.
2 Related work
From a theoretical perspective, our analysis is related to the literature on evolutionary algorithms and linear bandits.
Evolutionary algorithm. The success of DE motivated large body of works evolutionary algo- rithms for optimization. Evolutionary algorithm (EA) [6] is a large class of randomized optimization algorithms, based on the heuristic of mimicking natural evolution. Despite many variants, a typical EA usually maintains a population of solutions and improves the solutions by alternating between reproduction step which produces evaluated by the objective function and only the good ones are saved to the next round. Theoretical understandings of EA are focusing specific EAs, among which the most well-studied setting is (1+ 1)-EA, with parent population size and offspring population size are both 1 to optimize linear objective function on the Boolean space {0, 133 see [4 27 28 35| [55]. EA analysis focuses on optimization and reducing the running time instead of minimizing total regret as in bandit theory. There are other results on population based EAs, such as (1 + A)-EA
offspring solutions, and selection step where solutions
[1] (1+ + EEA (54) and
the most general (/ + A)-E where μ and À represent the parent population size and the offspring population size respectively. However, this group of works only adopted mutation. The understanding of the role played by recombination in evolutionary algorithms was left blank in the (n + A)-EA framework, while our paper provides a population-based regret minimization analysis with both mutation and recombination.
There are a few works 30 29
studying EAs with recombination (which are also called genetic algorithms (GAs)). However, their algorithms and analysis are tailored to artificial test objectives and the results are not able to generalize even to linear objectives. Recently, the running time analysis of some natural EAs with recombination has been conducted [39 40), but still their results are constrained under specific objectives such as ONEMAX and JUMP. We refer readers to the book by [59] for more comprehensive review of EA.
51 32
Linear bandits. Bandit is powerful framework formulating the sequential decision making process under uncertainties. Under this framework, linear bandits is a central and fruitful branch where in each round learner makes her decision and receives noisy reward with its mean value modelled by a linear function of the decision, aiming to maximize her total reward (or minimize total regret equivalently) over multiple rounds [5] 36 with extension to sparse linear bandits 23 and linear MDP (58). In the same spirit, the process evolving a population of genetic sequences to maximize a linear utility over the evolution trajectory, while getting access to noisy utility values through evaluating sequences along the way, can be mathematically formulated from the perspective of linear bandits. One of the main solutions in linear bandits is the upper confidence hound-based (UCB) strategy represented by LinUCB [36]. where the learner makes decision according to upper confidence bounds of the estimated reward and the accumulated regret proven to be Ô (dvT)
A similar strategy is optimism in the face of uncertainty (OFU) principle in Abbasi- Yadkori et al. ( The other approach is the Thompson Sampling (TS) strategy, which randomizes actions on the basis of their probabilities to be optimal. Russo and Van Roy [43 proved the Bayesian regret of TS algorithm is also of order Ô (dvT). And there are more results on the regret of TS-llike) algorithms solving linear bandits in the frequentist view for delicate review of bandit theory.
3 We also refer readers to the book by 34
Non-evolutionary methods for protein sequence design. Though our framework applies to an evolution- based DE process, there exist many other methods that are not evolution- Protein engineering is a rich field and it is not restricted to methods that are based on mutagenesis and recombination. Protein sequence engineering constantly evolves as new bio-technologies keep emerging. For example, new biotechnology makes it possible to synthesize specific variants and operate on the combínatorial space likewise with high-throughput method, and this allows directly applying Gaussian process bandit algorithm 42.. See [57] for high-level survey of this active
3

---

area of research, and see [7, 7 for more examples. This active and exciting field brings many new opportunities for machine learning.
Remark. It is important to note that our problem is not multi-armed bandit problem. In bandits, one can choose actions freely from the full action set. However, biological experiments, is expensive to synthesize recombination are used to generate new designs easily at low cost. Thus our algorithm can only guide the selection step in the DE process. Its regret not directly comparable with the regret of multi-arm bandits. To the best of our knowledge, this is the first work that studies the bandit theory and regret bound of mutation and recombination-enable DE
protein design sequence out of thin air. Instead, mutation and
3 Bandit model for directed evolution
3.1 Process overview
We illustrate the Thompson Sampling-guiin gugided Directed Evolution (TS-DE) process in Figure 3.1 A population S, at time consists of M candidate sequences. It evolves via mutation, crossover recombination, selection, and function evaluation to the next generation S1+1- The mutation and crossover selection guided using learnt function fø.- in order filter unwanted candidates and keep only small batch for costly evaluation. Collected data are fed into Thompson Sampling module for posterior update fa. Full details of the mutation, crossover selection, and Thompson Sampling modules will be given in Section
Directed Mutation
Crossover Selection
M
S
S
S
Sā.
list mutation
R: recombination
selection
Thompson_Samplinngg Sampling
evaluation
Arrow list
Thompson Sampier
Posterior
hotogical
brolgica
Model
betch update
Dataser
Figure 3.1: Thompson sampling-guided directed evolution
3.2 Motif feature, utility model, recombination and mutation operators
A genetic sequence comprises of functional motifs, i.c. functional subsequences that may encode particular features of protein, also known as protein motifs (37, 48 10]. Such genetic motifs are known to be "evolutionarily conserved", in the sense that they tend to evolve units, under mutation and recombination.
Suppose genetic sequence seq is made up of d genetic motifs, given by seq (seq(1), seq(2), ... seq(a)) ). Machine learning models for protein utility prediction are often based on motif features [56, 10, 38). Let X' be the space of genetic sequences of interest. We assume that binary motif feature map given, defined as follows.
Definition 3.1 (Binary Motif Feature Embedding). Let & be the genetic motif feature map given by:
6: X + 13d, Φ(seg) = (δi (seq ... (a(seq()))
(3.1)
such that at each dimension i, (seq()) is a binary feature of motif seg())-

---

The binary motif feature provides a minimalist abstraction for evolutionary processes where 0, 1 correspond favorable and nonfavorable directions, respectively, for each motif. Theoretical analysis for evolutionary optimization algorithms made the same assumption and viewed binary sequence
optimization as a fundamental problem 14 24
27
28
35 55
Since a protein function is largely determined by its motif, is common to model the protein utility f: X R function of motif features, i.e., (sseg fe- (x), ((se)) Vseq E X, under
parameterization by 0* [[6 57 45 18.
In this work, we study the most elementary Bayesian linear model, where is linear model parameterized by H" with a Gaussian prior, given as follows.
Assumption 3.2. (Linear Bayesian Utility Model) Assume the utility Ja- is a linear function parame- terized by 0* E IR., which is sampled from Gaussian prior, i.e.
fer (x) = (f",)), x),
~ NO >>0.
(3.2)
Since motifs tend to mutate and recombine with one another in units, it often sufficient to focus on recombination and mutation the motif level, rather than on the entry level. Further, recombination that breaks a motif often result in insignificant low-fitness descendants. Therefore, it suffices to focus on motif-level directed evolution for simplicity of presentation and theory. For theoretical simplicity, we define recombination and mutation operators on the motif level:
Definition 3.3 (Directed Mutation Operator). Let x be the motif feature sequence, I C [d] be collection of targeted sites and μ E (0, 1) be a mutation rate. The mutation operator Mut (x. I. 11) generates a sequence x' such that while for vj ş I, Iyj, for vi E I, x² is independently induced be
((o, 1}), 24
w.p. 14
(3.3)
Wi,
otherwise.
Definition 3.4 (Recombination Operator). Let x, y be the motif features associated with two parental genetic sequences. The recombination operator Rcb(2, y) generates a child sequence 2 such that 2, independent and
2, =
Ii
w.p. w.p.
ViE [d]
(3.4)
y1
We remark that Definitions 3.3 3.4 are mathematical simplifications of their real-world counterparts. In real world, mutation and recombination can take various forms depending on the context. In our analysis, define them in minimalist-style to keep theory generalizable and interpretable.
3.3 Regret minimization problem formulation
Evaluating the protein function for design sequence v a most costly and time-consuming step in protein engineering. In the DE process, we consider that regret is incurred only when sequences are evaluated. We also assume that each evaluation is subject to a Gaussian noise with known variance.
Assumption 3.5. (Noisy Feedback) Upon querying the utility of x, we get an independent noisy evaluation given by
u(x) ~ N( (2)))))))))))
(3.5)
Our goal is to minimize the Bayesian regret, i.e., the cumulative sum of optimality gaps between evaluated sequences and the optimal.
Definition 3.6 (Bayesian Regret), Denote by fo- (x*) the optimal utility value over X, { the evaluated individuals in each iteration. Throughout T' iteration, the accumulated regret is defined as
L. are
T
M
Bayes M) = E
Σ
(So (x*) so- (cr.i))
where M number of sequences selected for evaluation per timestep, and taken over the prior of 0* and all randomness in the DE process.
5

---

Thompson compling-guidess directed evolution (TS-DE)
We restate our goal as to direct population of genetic sequence to evolve towards higher utility value, until its population-average converges to the optimum fs- (x*). Our knowledge of is to be learned from noisy evaluations of selected sequences along the way. In this section, by integrating biological technique directed evolution with Thompson Sampling, Bayesian bandit method, propose Thompson Sampling-gun -uidedd Directed Evolution algorithm (TS-DE) as shown Alg where in each round Thompson sampling gives estimate of 6*, based on which key operators of DE: mutation, recombination and selection are implemented.
4.1 Crossover-then-sellction and directed mutation
Pairwise crossover is most common type of recombination in natural evolution. Let I, y be random pair of parents, and let = Rcb(r, y) be a child. If given a utility function f. we select only if the child performs better than the parents' average. Module (foomulatss this procedure.
Module Crossover SerasoverrSSlecctoon/....
1: Inputs: utility function f(z) (0. x), population of sequences. S
2: Initialization: S' <
3: while |S|| < |5] do
4: Sample and from uniformly with replacement.
5: Recombination:
Rcb(,,, v) (Definition 3.4).
6: Selection: S' + f()) 2 f(x)+/(0)
7: end while
8: Output: S'
Next we turn to designing the strategy for adding directed mutation under a given f as guidance and propose Module 2 An ideal mutation will diversify the population while preserving its fitness level as much as possible. So we add directed mutation to sites where the single site fitness over the population is less than of a uniformly distributed sequence. Formally, we only add mutation to site i M Exes 0₂ 24 < T;, where T; is the mean of uniformly random Z;.-
Module 2 Directed Mutation(f.S.p) DirrecteLMutatiio(ff.....
1: Inputs: utility function f(x) = (0,z), a population of sequences S, mutation rate μ
2: Initialization: I + 0, +- 0
3: for E d) do
4: if Ezes 8, x4 S 0 F; then
5: IU (i}.
6: end if
7: end for
8: Directed Mutation: x' Mut(x, I, ()) (Definition 3.3 and S' + S" (x') for all S.
9: Output: S'
4.2 Full algorithm
Finally, we are ready to combine all modules and state the full algorithm in Algorithm [ At each time step a posterior distribution is first computed using the data collected history. Then sample a O, from the posterior and do the corresponding directed mutation and crossover selection using this sampled weight, and augment the dataset for the next iteration with the measurements of resulting new population. The procedure is repeated until the time limit T reached.
Main results
In this section, we analyze the performance of TS-DE (Algorithm Tp. will show that the crossover selection module essentially mimics optimization iteration that strictly improves the population's

---

Algorithm Thompson Sampling-Guidee Directed Evolution (TS-DE)
1: Inputs: number of rounds T, initial population Sg = { JM of size M, mutation rate μa, o
2: Initialization: dataset Du <- 0, 12-1= 0, Ug =0
3: for t= 1 to T do
4: Posterior update
Vi r 1-1 1 XI,
0== 0² V - U---
(4.1)
5: Thompson Sampling 0₂~ N(,. V,-1)
6: S Mirrected_Mutation J0. 1,),, (Module 2).
7: S. = Crossover Seteveeereeeeeeionnnoo 1)) (Module Dp.
8: Evaluation and data collection Evaluate the utilities of all individuals S. and
Dr DE-1 U (Ia, ((r,))) Update o, (0,-1: Fr,,)) Un
(UT (UL,, .M u(zrM))
9: 1 1+1+1.
10: end for
fitness along the designated direction. By using a Bayesian regret analysis, show the DE modules, when combined with posterior sampling, can effectively optimize towards the best protein design while learning 0*
5.1 Crossover selection as an optimization iteration
Let f by any utility function, and let F(S)) := avgzes f(x) denote the population average utility. Our first result states ascent property showing that Serestover.Selection strictly improves the population average.
Theorem 5.1 (Ascent Property of Recombinnarion--tee---eeeettti Let f(x) (0.x) and let S be set of sequences. Let S' ProssoverrSelectioonn
then it satisfies
E [||0 (a
y) III
E [[F(S') 2 F(S) +
F(S) +
Σ 10,1 Var;
(5.1)
2/2
2d
where (S): denotes the variance of x; when x is uniformly sampled from S.
Proof sketch. See Figure 5.T for illustration. Given x and y, Rcb(2, y) can be represented by Itw + z=" where the denotes the entrywise multiplication between two vectors and e = (e,,..,, (2) with e; 's being indepen- dent Rademacher variables. Then f(=) equals f(x)+ 2
x
(e)
V
Ei= (x; y:) eq. After the selection step, the expected amount by which f2) exceeds its parents' average is at least >dd
x+y 2
JE 1 0; (z; v:) ei which has a tight lower bound of
1 0 (x 3) according to Haagerup 20] The full proof
2
given in Appendix C.1
Figure 5.1:
Ascent property of crossover recombination
Remark on diversity. Analysis above reveals an intriguing observation: the optimization progress of Crossover Selection scales linearly with Σ, 6, (S), i... sum of per-motif variances across population respect direction 0. More diverse population would enjoy larger progress from crossover selection. This observation is consistent with the natural evolution theory that diversity key to the adaptability of population to cope with evolving environment where fitness traits essential [2]]
measures a level "diversity" of with

---

5.2 Regret bound of TS-DE
Our main result is a Bayesian regret bound for TS-DE. Recall from Definition 3.6 that
BayesRGT(T, M) = =E Σ (fe- (x*) - for (21,)))..
Theorem 5.2. Under Assumption 3.2 and 3.5 when the population size is sufficient s.t. M log(dT) Alg admits its Bayesian regret s.t.
( dVMTT
BT = Ō HNV
(5.2)
we let A = 1, 1/2, 1, the Bayesian regret simplifies to (d MT)).
Remark on regret bound. Regret bound of Theorem 5.2 is optimal in M, T. For comparison, the Bayesian regret of Gaussian linear model is ((dv T) update, the optimal regret is O(dv vd due to that the norm our feature vectors are vd. while linear bandit theory often assumes feature have norm 1. Another factor of vd due to the evolutionary nature of DE, i.e., TS-DE is not allowed to any possible action but have to select those from the evolving population.
31 also in contextual linear bandit with batch 221 Our TS-DS regret has two extra factors of Vd. One
5.3 Proof sketch
Main challenge. Classic bandit method/analysis does not apply to setting, because each round of DE is limited to actions that are reachable by mutation and recombination based on the current population. It means that cannot simply explore the optimistic actions that maximize each function estimate fg. This leads to an optimization gap that complicates the regret proof.
Denote by x² and zi the maximums of fe- and fö. Denote by Ft := fo. (xt) the maximum value of fg. and denote by (S) the average value of fū. over set S.
Step 1: Regret decomposition. With expectation taken over all stochasticity, posterior sampling guarantees BayesRGT(T, - Em- E fā. (xt) for (2 since conditioned data
D for (x*) and fö, (zt) are identically distributed. Then by breaking fū, (at) foe (It.)) down to the sum of fq. (at) fū, (Ir,,) and Jø, (3re,) fo- (2r,,), decompose the total regret into
T
M
BayesRGT(T, M) M E Σ F; F((S.))
+
E
O
0" ,4,,)
(5.3)
Step 2: Bounding H, using linear convergence. Hi is the accumulated optimization error under a time-varying objective fā.- After calling S/11 Directed Mutation(Sa, S,-1, and S, Crossover Selection fū. 1) at step t, the ascent property 5.1 together with property of
the mutation module yields linear convergence towards Fř, i.e., E Fi F((S.) 0 <
(F: (S))))) with a modulus of contraction 7 E (0,1) s.t. 1 1-7
Vd
follows that
F (S.) S 7 [F21 - ( + error terms + et where e martingale difference. Applying the above recursively H1, we get Hi
- Fi
Σ
F
F
+
(Fa(Sa) - Fo (Sk)
0 (
which is dominated by term x and M K < -
Σt-
M
( 0 8 Ft,s))
(
Step 3: Bounding Hy. H2 is the accumulated prediction error of 0, which is a classic term to bound
bandit literature and of Ō (1255, (B3SMT) by using a batched self neff-normalization bound.

---

25
population ovg regIET
DE. D.1.A.
1/s0rtt
D._0.5
DE, www.ndddnnmmmmm
TEDT,
fitmes
5000
step
Figure 6.1: Regret and fitness curves of TS-DE during evolution. Left: agpulation-averaged regret with varying population sizes M. Each curve is averaged over 100 trials. Right: Fitness curves of TS-DE with varying values of μ. compared with basic DE with varying mutation rates. (The purple curve plots basic DE without mutation, modified the initial population to be uniformly distributed this case to make non-trivial.)
Experiments
6.1
Simulation
We test the TS-DE by simulating the evolution of a population of sequences in {0, 13d. We set the initial population be all zeros, and À 1, σ
Regret and convergence results. Figure 6. shows regret curves and learning curves of TS-DE, with comparison to basic DE. In the left panel of 6. plot the population-averagee
Bayesian 10, T 100 and μ = 0.8. These results
regret TS-DE with various values of M, where confirm sublinear regret bounds. In the right panel of Figure 6.1 tested TS-DE using various mutation rates, and compared them with a basic DE approach The comparison shows that TS-DE converges significantly faster, while the convergence of DE much slower and very sensitive to mutation scheduling.
Visualizing the evolution of population. We visualize the evolution trajectory of population S, in one run TS-DE, with = 40. 20 and μ = 0.1. evolving high-dimensional population S, by mapping them to 2D (via PCA and KDE density contour plot). In the right panel of 6.2 we plot the fitness distribution each S. These plots illustrate how TS-DE balances the exploration-cxploitttio trade-off: It guides Se to "diversify" initially and then quickly approach and concentrate around a maximal solution.
left panel Fig 6.2] we visualize
6.2 Real-world experiment validation
Having demonstrated our approach with simulations, we use real-world experiments to showcase the validity and generalizability of our method. The TS-DE method is adapted to work with real-worile motif features (continuous-valuus instead of binary), linear model and multiple rounds of wet-lab experiments optimizing CRISPR design sequence. Our approach together with thgtthhruugh experiment identified a high-performing sequence with 30+ fold improvement in efficiency. Notably, the optimized CRISPR designs generated by our DE approach was experimentally validated in (26) and demonstrated the real-world utility of our method. This technology is used for ex-vivo high- thgoghhruughput single-cell barcoding with applications in genomics and drug discovery.
We postpone more details about this real-world validation to Appendix B. and Figure B.
'The basic DE approach does not employ any function estimate. does random mutation with a predefined mutation rate and random crossover recombination. It evaluates every candidate sequence and uses the noisy feedback in replace of fa for selection.

---

Riness f0O
Figure 6.2: Evolving population of TS-DE and fitness levels. Left panels: Visualization of population evolution projected in 2D shown, taken at 6 snapshots. Right panel: The population's fitness distribution shifts towards optimal during evolution. denotes the optimal solution.
References
[1] Yasin Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24:2312-2320, 2011.
[2] Marc Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-184. PMLR, 2017.
[3] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135. PMLR, 2013.
[4] Frances H Arnol. Design by directed evolution. Accounts of chemical research, 31(3):125-133 1998.
[5] Peter Auer. Using confidence bounds for exploitation-exxplrraiin trade-offs. Journal of Machine Learning Research, 3:397-422, 2002.
[6] Thomas Back. Evolutionary algorithms theory and practice: evolution strategies, evolution- ary programming, genetic algorithmss Oxford university press, 1996.
[7] Claire N Bedbrook, Kevin K Yang, Austin Rice, Viviana Gradinaru, and Frances H Aroold. Machine learning to design integral membrane channelrhodopsinn for efficient eukaryotic expression and plasma membrane localization. PLoS computational biology, 10050)) 2017.
[8] Keqin Chen and Frances H Arnold. Enzyme engineering for nonaqueous solvents: random mutagenesis enhance activity of subtilisin in polar organic media. Bio/Technology. 9(11): 1073-1077, 1991.
[9] Keqin Chen and Frances H Arnold. Tuning the activity of an enzyme for unusual environments: sequential random mutagenesis of subtilisin for catalysis dimethyyformamide. Proceedings of the National Academy Sciences, 90(12):5618 5622,, 1993.
[10] Joseph M Cunningham, Grigoriy Koytiger, Peter K Sorger, and Mohammed AlQuraishi Bio- physical prediction of protein-peptide interactions and signaling networks using machine learning. Nature methods, 1752) 2020.
[11] Benjamin Doerr and Marvin Künnemann. Optimizing linear functions with the (1+ A) evolu- tionary algorithm different asymptotic runtimes for different instances. Theoretical Computer Science, 561:3-25 23, 2015.
[12] Janardhan Rao Doppa. Adaptive experimental design for optimizing combinatorial structures. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), pages 4940-4945, 2021. 2021.
10

---

[13] Jennifer A Doudna and Emmanuelle Charpentier. The new frontier of genome engineering with crispr-cas9. Science, 346(6213):125006, 2014.
[14] Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (I+ 1) evolutionary algorithm. Theoretical Computer Science, 276(1-2):51-8) -1, 2002.
[15] Clara Fannjiang and Jennifer Listgarten. Autofocused oracles for model-based design. Advances in Neural Information Processing Systems, 33: 13:12955-12956, 2020.
[16] Richard Fox, Ajoy Roy, Sridhar Govindarajan, Jeremy Minshull, Claes Gustafsson, Jennifer T Jones, and Robin Emig. Optimizing the search algorithm for protein engineering by directed evolution. Protein engineering, 16(8):589-597 2003.
[17] Richard J Fox, S Christopher Davis, Emily C Mundorff, Lisa M Newman, Vesna Gavrilovic, Steven K Ma, Loleta Chung, Charlene Ching, Sarena Tam, Sheela Muley, et al. Improving catalytic function by prosar-driven enzyme evolution. Nature biotechnology. (5(3):338334- 2007.
[18) Chase R Freschlin, Sarah A Fahlberg, and Philip A Romero. Machine learning to navigate fitness landscapes for protein engineering. Current Opinion in Biotechnology, 75:102713, 2022.
[19] Christian Gießen and Carsten Witt. Optimal mutation rates for the (1+ X) ea on onemax. In Proceedings of the Genetic and Evolutionary Computation Conference 2016, pages 1147-1154, 2016.
[20] Uffe Haagerup. The best constants in the khintchine inequality. Studia Mathematica, 70: 231-283, 1981.
[21] Nima Hamidi and Mohsen Bayati. On worst-case regret of linear thompson sampling. arXiv preprint arXiv:2006.0677 06790, 2020.
[22] Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye. Sequential batch learning in finite-action linear contextual bandits. arXiv preprins (rXiv:2004.063// 2020.
[23] Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 15:10733-10763, 2020.
[24] Jun He and Xin Yao. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3(1):21-35, 2004.
[25] Edward G Hibbert and Paul A Dalby. Directed evolution strategies for improved enzymatic performance. Microbial Cell Factories. 4(1):1-6, 2005.
[26] Nicholas W Hughes, Yuanhao Qu, Jiaqi Zhang, Weijing Tang, Justin Pierce, Chengkun Wang, Aditi Agrawal, Maurizio Morri, Norma Neff, Monte M Winslow, et al. Machine-leamning: optimized casl2a 2a barcoding enables the recovery of single-cell lineages and transcriptional profiles. Molecular Cell, 82(16):1133-3118 2022.
[27] Jens Jägersküpper. A blend of markov-chain and drift analysis. In International Conference on Parallel Problem Solving from Nature, pages 41-51. Springer, 2008
[28] Jens Jägersküpper. Combining markov-chain analysis and drift analysis. Algorithmica, 59(3): 409 424, 2011.
[29] Thomas Jansen and Ingo Wegener. Real royal road cecttionsswheee crossover provably is essential. Discrete applied mathematics, 149(1-3): 11-125, 2005.
[30] Thomas Jansen, Ingo Wegener, et al. The analysis of evolutionary algorithms-a proof that crossover really can help. Algorithmica, 34(1):47-66, 2002.
[31] Cem Kalkanlı and Ayfer Özgür. An improved regret bound for thompson sampling in the gaussian linear bandit setting. 2020 IEFE International Symposium on Information Theory (ISIT), pages 2783-2788 IEEE, 2020.
11

---

[32] Timo Kötzing, Dirk Sudholt, and Madeleine Theile. How crossover helps in pseudo-boolean boolean optimization. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, pages 989-996, 2011.
[33] Olga Kuchner and Frances H Arnold. Directed evolution of enzyme catalysts. Trends in biotechnology, 15(12):523-530, 1997.
[34] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[35] Per Kristian Lehre and Carsten Witt. Black-box search by unbiased variation. Algorithmica, 64 (4):623-642, 2012.
[36] Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670. ACM, 2010.
[37] Dan Ofer and Michal Linial. Profet: Feature engineering captures high-level protein functions. Bioinformatics, 31(21): 1:3429-3436- 2015.
[38] Dan Ofer, Nadav Brandes, and Michal Linial. The language of proteins: Nlp, machine learning & protein sequences. Computational and Structural Biotechnology Journal, 19:1750-1758, 2021.
[39] Pietro S Oliveto and Carsten Witt. Improved time complexity analysis of the simple genetic algorithm. Theoretical Computer Science, 15:22-41, 2015.
[40] Pietro S Oliveto, Dirk Sudholt, and Carsten Witt. A tight lower bound on the expected runtime of standard steady state genetic algorithms. Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pages 1323-1331, 2020.
[41] Michael S Packer and David R Liu. Methods for the directed evolution of proteins. Nature Reviews Genetics, 16(7):379- 394, 2015.
[42] Philip A Romero, Andreas Krause, and Frances H Amoll. Navigating the protein fitness landscape with gaussian processes, Proceedings of the National Academy of Sciences, 110(3): E193-E201, 2013.
[43] Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 1224)112 2014.
[44] Ophir Shalem, Neville Sanjana, and Feng Zhang. High-throughhut functional genomics using crispr-cas9. Nature Reviews Genetics, 16(5):299-311, 2015.
[45] Jung-Fun Shin, Adam J Riesselman, Aaron W Kollasch, Conor McMahon, Elana Simon, Chris Sander, Aashish Manglik, Andrew C Kruse, and Debora S Marks. Protein design and variant prediction using autoregressive generative models. Nature communications, 12(1):1-11, 2021.
[46] Sam Sinai, Richard Wang, Alexander Whatley, Stewart Slocum, Elina Locane, and Eric D Kelsic. Adalead: simple and robust adaptive greedy search algorithm for sequence design. arXiv preprint anXiv:2010.02141, 2020.
[47] George P Smith and Valery A Petrenko. Phage display. Chemical reviews, 97(2)3911-410. 1997.
[48] Jérôme Tubiana, Simona Cocco, and Rémi Monasson. Learning protein constitutive motifs from sequence data. Elife, Ste39397,,011
[49] Nicholas J Turner. Directed evolution drives the next generation of biocatalysts. Nature chemical biology, 5(8):567-573, 2009.
[50] Chenyu Wang, Joseph Kim, Le Cong, and Mengdi Wang. Neural bandits for protein sequence optimization. In 2022 56th Annual Conference on Information Sciences and Systems (CISS), pages 188-193. IEEE, 2022.
12

---

[51] Richard A Watson and Thomas Jansen. A building- block royal road where crossover is provably essential. In Proceedings of the 9th annual conference on Genetic and evolutionary computation, pages 1452-1459, 2007.
[52] Robert H Whittaker. Evolution and measurement of species diversity, Taxon, 21(2-3) 1972.
[53] Greg Winter, Andrew D Griffiths, Robert E Hawkins, and Hennie R Hoogenboom. Making antibodies by phage display technology. Anmual review of immunology, 12(1):433-455, 1994.
[54] Carsten Witt. Runtime analysis of the (u+ 1) on simple pseudo-boolean functions. Evolu- tionary Computation, 14(1):65-86, 2006.
[55] Carsten Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability and Computing, 22(2):294-3) 3188, 2013.
[56] Bruce J Wittmann, Kadina E Johnston, Zachary Wu, and Frances Arnold. Advances in machine learning for directed evolution. Current opinion in structural biology, 69:1 1-18 2021.
[57] Kevin K Yang, Zachary Wu, and Frances H Arnold. Machine- Meaahing www---lngannnidddeeeee guided directed evolution for protein engineering. Nature methods, 16(8):687-694, 2019.
[58] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
[59] Zhi-Hua Zhou, Yang Yu, and Chao Qian. Evolutionary learning: Advances in theories and algorithms. Springer, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "feMA_wp_q0r", "reviewer": "Reviewer_qppa", "summary": "This paper study a cross domain problem for biological sequence optimization with bandit problem, and tries to provide theoretical understanding of directed evolution under bandit theory with Thompson sampling.", "questions": "stated in weaknesses.", "limitations": "empty", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# strengths\n1. The problem is interesting.\n2. The paper gives a theoretical understanding of bandit problem with directed Evolution.\n\n# weaknesses\n1. The linear setting is always a problem in real world application. I am not sure whether the linear bandit assumption suitable enough for real application.\n2. I do not go through the proof, while it may seems that the proof may directly follow the standard proof sketch of bandit theory. It will be much better if the authors provide a brief description about the proof difficulties during adopting the  typical TS bandit proof technique.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YTcaHzix-2L", "reviewer": "Reviewer_X52n", "summary": "This paper proposes a novel approach to biological sequence optimization that models the task as a linear bandit problem and uses Thompson Sampling to guide a Directed Evolution algorithm towards optimizing the linear fitness function.  The approach (\"TS-DE\") is a variation of DE that is demonstrated to outperform classical (random/blind) DE alone in simulation that achieves a Bayesian regret that is optimal in population size and number of generations.\n​\nThe DE and TS-DE algorithms are structurally the same, using crossover and point mutations to evolve a population of sequence variants over generations.  The difference is that TS-DE tracks a posterior of the fitness function between generations, and in each generation draws a fitness function estimate from this posterior, and (roughly speaking) limits the recombined variants and mutation positions to those which would see improvement under that fitness function estimate.  The result is more efficient convergence to optimal or near-optimal sequences.\n​\nIt is not surprising on its own that a method which takes advantage of side information in crossover and mutation steps should outperform a completely random mutation approach.  It is disappointing that the authors did not compare this approach to at least one baseline that also also uses this side-information, such as training and scoring a linear model on proposed sequences to use as a filter between rounds.  \n​\nNonetheless, a key strength to the paper is its mathematical rigor, and the \"main result\" of the paper, that proves that TS-DE achieves a Bayesian Regret of $\\tilde{O}(d^2\\sqrt{MT})$.  The proof summary in the body of the paper was helpful for intuition, and great care was taken in the appendix to support each step of the proof.  \n​\nThe main limitation/weakness of both this main result and the algorithm itself arises from the two necessarily assumptions: (3.2) which requires the true fitness function to be a linear function with weights drawn independently from Gaussian distributions, and (3.5) which restricts measured values to having homoskedastic, iid, Gaussian, additive noise.  Neither of these assumptions are likely to hold, or even approximately hold, in practice, and there is no discussion of the sensitivity of the method and results to violations of these assumptions.\n​\nA secondary limitation/weakness is in the applicability of this method and results to biological experiments, for two main reasons: the linear model, and biological feasibility of intervening to filter between generations.  While the authors claim in Appendix 2 that the linear model can be generalized somewhat beyond binary motifs, it is not explained how this is done, and the application seems to still be restricted to linear models.  The biological feasibility / utility here may be a bigger issue, and is discussed in the Weaknesses section below.", "questions": "- What is the population size and selection strength for the DE and DE-TS approaches? It seems to me that a more realistic DE module would be more competitive with the DE-TS approach presented here, see section 5 in Sinai and Kelsic 2020 (https://arxiv.org/abs/2010.10614) ", "limitations": "## Limitations\n​\n- The main limitations of this paper is it's reliance on strong and unlikely assumptions that the fitness landscape be linear and noise be iid Gaussian, and the questionable applicability in biological experiments identified in Weakness (7) - were not discussed in the paper.  Neither of these negate the contributions of the paper, but should be presented, and if possible, some discussion of the sensitivity of these results to violations in these assumptions should be added. I also think benchmarking against other sequence design work on more conventional challenges would strengthen the paper significantly. There is still a bit of a gap between the theoretical results and applicability that I'm not convinced this work would help close. \n​\n- It would be helpful if authors contrast their work with algorithms discussed by Sinai and Kelsic 2020 on model-guided sequence design, in particular discussion in section 5 (both with better DE modeling and contrasting with Algorithms like CbAS, Brookes et al 2019). \n​\nMinor \n Some grammatical issues: \n\n1. In second paragraph \"DE, one of the top molecular technology breakthrough in the past century, demonstrate human's ability to engineer proteins at will\": breakthrough -> breakthroughs, demonstrate -> demonstrates, human's -> humanity's.  \n\n2. The following paragraph was especially confusing, since the topic sentence claimed that DE \"remains expensive and time-consuming\" but the subsequent sentences all defend the opposite claim that DE is \"generally easy\" and has been \"exponentially improved.\"\n  \n3. There's also a small issue in Figure 1.1 in the recombination example, where a child with a dark gray motif 4 arises from parents without that motif.  \n\n4. The comment after Assumption 3.5, that \"Our goal is to maximize the Bayesian regret\" presumably was a mistake and the authors meant \"to minimize\" instead.\n​\n​", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths \n​\n1. The proposed Algorithm 1, to the reviewer's knowledge, is novel, though straightforward, and sufficient explanation has been provided for others to implement these ideas easily in simulation.\n2. The paper's structure and organization was thoughtful and easy to follow, with key contributions highlighted and more technical steps relegated to the appendix.  \n3. The mathematical rigor is high, with great care taken in the appendix to explain both the intuition and logic behind all mathematical claims.  The approach to combining DE and Bandit Theory overall was creative and carefully developed.\n4. The main result, that TS-DE achieves optimal Bayesian regret at least with respect to population size and number of generations, is strong.\n5. Simulations show TS-DE outperforms DE handily - though this result is not surprising, it was worthwhile to confirm this through a demonstration.\n​\n​## Weaknesses\n​\n1. Several major assumptions would appear to not hold in practice.  Primarily, the assumptions that the fitness function is linear in a known, relatively small basis of binary motifs.  That aside, there is also the issue of accurately estimating the \"known\" variance sigma, the assumption that that noise is uniform (while, in practice, heteroskedasticity is common).  The paper does not address the sensitivity of the performance of their approach or its bounds under minor violations of these assumptions.support on real data\n​\n2. An initial concern was that the linear motif assumption in the paper was not easily generalizable to realistic protein engineering settings.  In Appendix B the authors explain that, in real world applications, these assumptions were loosened, so that individual base pairs were considered for mutation, and features were scalar-valued (not binary-valued).  While more details on these extensions would have been appreciated, it is understandable that they may be saved for the other publication mentioned and/or remain proprietary.\n\n3. One way to alleviate these concerns is to actually show the performance of the algorithm on some simple but more realistic tasks, e.g. this package allows the authors to test their algorithms against some competing methods (https://github.com/samsinai/FLEXS). \n​\n4. Unclear how the mutation rate mu is chosen.  Presumably the choice of mu has some impact on the convergence of the algorithm if not bounds, yet this parameter does not appear in the analysis or experiments.\n​\n5. Novelty of the approach - while this exact formulation is novel, there are other recent examples in the literature that combine Thompson Sampling with Bandit problems, such as https://arxiv.org/pdf/2205.10113.pdf.  The method in this paper seems to be very similar to the paper under review, though it frames itself as a multi-armed bandit approach, and therefore compares itself against multi-armed bandit algorithms, including UCB methods.  Moreover, while the Thompson Sampling element of the algorithm is key to proving the main result (the bound on regret), in effect the algorithm (Alg 1) itself comes out as a fairly standard directed evolution approach \n​\n6. The paper claims that the resulting regret bound is optimal in M and T, and this is remarked upon, but not proven or cited.\n​\n7. A key argument for the linear bandit model is made in the Remark at the end of Section 2.  In short, it says that this problem is NOT a multi-armed bandit problem, primarily because we are not free to choose any action, but are limited by biology to mutation and recombination.  This is the reason why this method is not compared against multi-arm bandit methods in simulation, and why its regret is not compared to the regret of multi-arm bandits.  At first this seems entirely reasonable.  However, Algorithm 1 introduces crossover and mutation steps that involve sequence filtering based on calculating model scores, and intervening at this step.  This adds hugely significant cost to DE in a biological setting.  In classic/random DE, the crossover and mutation steps are random, not because of a lack of side-knowledge that could in theory be used to direct these steps, but because the biological steps of mutation and crossover naturally occur randomly.  While it is trivial \"in silico\" to intervene and filter out undesirable mutants according to side information, doing so in practice would require sequencing after evolutionary rounds to see what was produced, and then somehow separating out desirable and undesirable variants in the population before continuing.  Alliteratively, the whole mutation process could be done in silico, and then the populations $S_t$ could be constructed by hand from the in silico list of variants, but doing this completely negates the advantage of DE as an inexpensive process AND negatives the Remark at the end of Section 2 explaining why the model is limited to linear bandits.  If we are going to allow this level of filtering and/or individual construction of variants, we shouldn't have to limit ourselves to variants that could potentially arise from DE mutation and crossover steps.  Given the description in Appendix 2 of applying this model in practice, and the use of CRISPR technology in its implementation, it seems likely that the sequences were synthesized from an in silico selection step that could have easily been expanded to include sequences unobtainable through crossover or limited point mutations, again raising the question of whether the the assumption that \"this is not a multi-armed bandit problem\" is *really* a limitation of the biology or just a desirable limitation for the sake of the mathematical results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H437JvcAt28", "reviewer": "Reviewer_fbLu", "summary": "This paper focuses on a specific application **local** directed evolution. It starts with a set of candidate sequences and proposes an algorithm that performs two operations on the batch of sequences: recombination and common point mutation. The response function is modelled as a linear function of d protein motifs, where each motif can be or off. Authors analyze Bayesian regret of their procedure supported with comparison to classical evolutionary strategy.", "questions": "- Module 1, Line 6, x' should be z, right?\n- How do you select the population of sequences S? Do you apply any diversity there?\n- What is basic DE in your opinion?\n- What is this modulus of contraction?\n- Figure 6.1, what is the message the graph implies when we consider \\mu?\n- Can you explain 6.2 left better, I did not get it.\n", "limitations": "- The paper tries to give a very general introduction to directed evolution, however in 4 projects involving DE evolution never was the goal to change motifs of the protein and work in this greedy fashion. Instead enzymatic proportions were to be improved using a few selected mutations in the vicinity of the active site. I think the formulation authors have is fine and is probably motivated by their experimental setup, but this is **a form** of directed evolution not **the directed evolution**. I want to stress that this is an important point. If the goal of this paper is to introduce this problem to the broader ML community, we better do this carefully without over generalizing. I am fine with the setup, but one has to clearly say that this is a specific setup of DE. For example, in my opinion, this paper does not address  the major challenges in DE e.g. epistasis, combinatorial problems etc. \n- Lacking theoretical understanding. I am not sure the proof is correct, since there is a magic quantify appearing suddenly. This is my justification for a lower score. I think the theorem might be correct, but the way there is not clearly stated. Also, I see no reason why scaling in d^2 is necessary for such a simple objective (linear on a hypercube). \n- The paper lacks an algorithmically meaningful baseline, which could be executed synthetically. \n\n", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n----------\n- I like the formalization attempt of the experimental pipeline authors are using and designing an algorithm for it\n- Its nice this found a real-world application and improved over classical evolutionary approaches \n\nWeakness\n---------\n- The authors do not do justice to the field of directed evolution. There are evolutionary based methods which operate on a current batch of sequences and amend it as described here - more aligned with local (or evolutionary approaches). However, there are other approaches which can synthesise specific mutants and operate on the combinatorial space likewise with high-throughput methods. Perhaps an important citation from this line of work is the paper which for  the first time uses BO with Gaussian processes and has regret guarantee which appeared in PNAS 2013, by authors Romero, Krause and **Arnold**. This is a ripe field that falls under the directed evolution keyword as well. \n\n- Focus on regret minimization is a big minus. I see no reason why to focus on regret minimization. A more reasonable benchmark is to report the best variant so far. Thompson sampling often samples very greedy steps in order to achieve low regret, but in practice we do not want this at all, we want to explore given the uncertainty of $\\theta$. We want to be as diverse as possible to find meaningful new information and candidates. \n\n- There are two sub-methods introduced, first the operators are introduced in one order, explanation of them is in reversed order and they appear in the algorithm yet reversed.\n\n- I have significant doubts about the proof of Theorem 5.2\n  - namely the sudden emergence of modulus of concentration? Which I have no clue about.\n  - the term H2, should be bounded by d\\sqrt{TM} not the other exponent as authors propose\n  - Also one hast to explicitly state that this is for linear objective supported on unit \nhypercube. This proof does not work generally. A reader might be tempted to generalize to general linear bandits in general, but this is not true and it's not sufficiently clearly spelled out. However, due to the simplicity of the objective (hypercube + linear) I have no doubts that the algorithm would eventually converge since there is a random component due to $\\mu$. (One just needs to learn d components sufficiently fast) \n\n- The function in this case is the additive function of motifs, this is an extremely simplistic assumption for many practical applications where complex multi mutation epistasis occurs and is of interest to be modelled by data-driven methods.\n- There isn’t any meaningful baseline algorithm for example and algorithm that would try to estimate the effect of all pointwise mutations, i.e. S-> S_1, first mutation, S->S_2 second mutation etc. This would probably converge in O(d\\sqrt{TM}) steps as well and I believe even faster. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1sU4m940BDY", "reviewer": "Reviewer_WM9h", "summary": "The paper introduces a variant of a linear Bandits model for directed evolution (DE). DE is concerned with iteratively optimizing a population of individuals by selecting a subset of promising individuals for mutation and recombination in each step. The utility of individuals is modeled with a linear function parameterized by a parameter theta. Theta is refined via a new variant of Thompson sampling. The difference to classic Thompson sampling is that the one cannot directly sample individuals due to the stochasticity of mutation and recombination. The method has sublinear regret bounds, that were confirmed in a simulation experiment. It was successfully applied to the optimization of CRISPR sequences. ", "questions": "* In the Simulation Experiment in Section 6.1: How was the utility f chosen?\n* If I understood correctly, the main difference to existing linear Bandits is that one cannot choose actions freely from the full action set. How does this differ from Sleeping Bandits setting?", "limitations": "The authors do not address the potential negative societal impact of their work. Their main application -- gene editing -- is an exemplary case for an ethically controversial topic. I see that the entire debate on this issue cannot be addressed in a single ML paper, but one could have at least pointed out that it is an issue and referred to more detailed discussions of it. In particular, because such cases are specifically mentioned in the submission guidelines. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written. Even with no background on biotechnologies, one can read it in one go. The idea to include mutation and recombination into linear Bandits is new, as far as I know. The paper only mentions protein design optimization and gene editing, so I believe that its impact is mostly limited to biotechnology. I like that the paper not only claims that the method has real-world applications, but has already been able to show that the method has been successful in real-world applications. The results in the simulation experiment look promising too, however the baseline (the basic DE approach) seems to be rather simple. The theoretical claims are well supported.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept