Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
​
The 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.
​
It 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.  
​
Nonetheless, 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.  
​
The 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.
​
A 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.
strengths_and_weaknesses: ## Strengths 
​
1. 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.
2. The paper's structure and organization was thoughtful and easy to follow, with key contributions highlighted and more technical steps relegated to the appendix.  
3. 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.
4. The main result, that TS-DE achieves optimal Bayesian regret at least with respect to population size and number of generations, is strong.
5. Simulations show TS-DE outperforms DE handily - though this result is not surprising, it was worthwhile to confirm this through a demonstration.
​
​## Weaknesses
​
1. 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
​
2. 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.

3. 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). 
​
4. 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.
​
5. 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 
​
6. The paper claims that the resulting regret bound is optimal in M and T, and this is remarked upon, but not proven or cited.
​
7. 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.
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
​
- 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. 
​
- 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). 
​
Minor 
 Some grammatical issues: 

1. 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.  

2. 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."
  
3. 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.  

4. 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.
​
​
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths
----------
- I like the formalization attempt of the experimental pipeline authors are using and designing an algorithm for it
- Its nice this found a real-world application and improved over classical evolutionary approaches 

Weakness
---------
- 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. 

- 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. 

- 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.

- I have significant doubts about the proof of Theorem 5.2
  - namely the sudden emergence of modulus of concentration? Which I have no clue about.
  - the term H2, should be bounded by d\sqrt{TM} not the other exponent as authors propose
  - Also one hast to explicitly state that this is for linear objective supported on unit 
hypercube. 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) 

- 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.
- 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. 

questions: - Module 1, Line 6, x' should be z, right?
- How do you select the population of sequences S? Do you apply any diversity there?
- What is basic DE in your opinion?
- What is this modulus of contraction?
- Figure 6.1, what is the message the graph implies when we consider \mu?
- Can you explain 6.2 left better, I did not get it.

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. 
- 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). 
- The paper lacks an algorithmically meaningful baseline, which could be executed synthetically.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: # strengths
1. The problem is interesting.
2. The paper gives a theoretical understanding of bandit problem with directed Evolution.

# weaknesses
1. 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.
2. 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.
questions: stated in weaknesses.
limitations: empty
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
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.
questions: * In the Simulation Experiment in Section 6.1: How was the utility f chosen?
* 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.
review_title: null

Meta-review: metareview: The initial round of reviews for the submitted manuscript was mostly positive in tone, but this enthusiasm was tempered by a number of deep technical issues -- and some more philosophical issues regarding the presentation and framing of the results -- raised by the reviewers. Fortunately, the author rebuttal and author--reviewer discussion phases went a long way toward clearing up some initial confusion and clarifying the contributions of the authors, which swayed the prevailing opinion of the reviewers toward acceptance.

I want to commend the authors for their enlightening contributions to that discussion, which assuaged most of the reviewers' initial complaints.

However, I would also like to stress that it is critical that the fruits of this discussion (especially with reviewers X52n and fbLu) be incorporated into a revised version of this manuscript. The reviewers are unanimous in this opinion.
confidence: Certain
Decision: Accept