Neural Design for Genetic Perturbation Experiments
Authors: Aldo Pacchiano
Drausin Wulsin
Robert A Barton
Luis Voloch
Venue: ICLR 2023 notable top 25% (2023)
Keywords: genetiic perturbation experiments
gene disco
optimism
neural optimism

Abstract: The problem of how to genetically modify cells in order to maximize a certain cellular phenotype has taken center stage in drug development over the last few years (with, for example, genetically edited CAR-T, CAR-NK, and CAR-NKT cells entering cancer clinical trials). Exhausting the search space for all possible genetic edits (perturbations) or combinations thereof is infeasible due to cost and experimental limitations. This work provides a theoretically sound framework for iteratively exploring the space of perturbations in pooled batches in order to maximize a target phenotype under an experimental budget. Inspired by this application domain, we study the problem of batch query bandit optimization and introduce the Optimistic Arm Elimination ($\mathrm{OAE}$) principle designed to find an almost optimal arm under different functional relationships between the queries (arms) and the outputs (rewards). We analyze the convergence properties of $\mathrm{OAE}$ by relating it to the Eluder dimension of the algorithm's function class and validate that $\mathrm{OAE}$ outperforms other strategies in finding optimal actions in experiments on simulated problems, public datasets well-studied in bandit contexts, and in genetic perturbation datasets when the regression model is a deep neural network. OAE also outperforms the benchmark algorithms in 3 of 4 datasets in the GeneDisco experimental planning challenge. 

Published as a conference paper at ICLR 2023
NEURAL DESIGN FOR GENETIC PERTURBATION EXPER- IMENTS
Aldo Pacchiano Microsoft Research NYC
Drausin Wulsin & Robert A. Barton & Luis Voloch
Immunai
apacch ano@mi wrwsoft. www.aaiioooooot.coommm com
(drausin, robert.bbrter. luis] [ss communaiin ..omm
ABSTRACT
The problem of how to genetically modify cells in order to maximize a certain cellular phenotype has taken center stage in drug development over the last few years (with, for example, genetically edited CAR-T, CAR-NK, and CAR-NKT cells entering cancer clinical trials). Exhausting the search space for all possible genetic edits (perturbations) or combinations thereof is infeasible due to cost and experimental limitations. This work provides theoretically sound framework for iteratively exploring the space of perturbations in pooled batches order maximize target phenotype under experimental budget. Inspired by this application domain, we study the problem of batch query bandit optimization and introduce the Optimistic Arm Elimination (OAE) principle designed find an almost optimal arm under different functional relationships between the queries (arms) and the outputs (rewards). We analyze the convergence properties of OAE by relating it to the Eluder dimension of the algorithm's 's function class and validate that OAE outperforms other strategies finding optimal actions experiments on simulated problems. public datasets well-studied in bandit contexts, and in genetic perturbation datasets when the regression model a deep neural network. OAE also outperforms the benchmark algorithms in 3 of 4 datasets in the GeneDisco experimental planning challenge.
INTRODUCTION
We are inspired by the problem of finding the genetic perturbations that maximize given function of cell (a particular biological pathway mechanism, for example the proliferation or exhaustion of particular immune cells) while performing the least number of perturbations required. particular, are interested in prioritizing the set of genetic knockouts (via shRNA or CRISPR) to perform on cells that would optimize particular scalar cellular phenotype. Since the space of possible perturbations is very large (with roughly 20K human protein-coding genes) and each knockout is expensive, we would like to order the perturbations strategically so that we find one that optimizes the particular phenotype interest in fewer total perturbations than, say, just brute-force applying all possible knockouts. In this work we consider only single-gene knockout perturbations since they the most common, but multi-gene perturbations are also possible (though considerably more technically complex to perform at scale). While multi-gen multi-gene perturbation may be trivially represented as distinct (combined) perturbation in our framework, we leave for future work the more interesting extension of embedding, predicting, and planning these multi-gene perturbations using previously observed single-gene perturbations.
With this objective in mind we propose simple method for improving a cellular phenotype under limited budget of genetic perturbation experiments. Although this work is inspired by this concrete biological problem, our results and algorithms are applicable in much more generality to the setting of experimental design with neural network models. We develop and evaluate a family of algorithms for the zero noise batch query bandit problem based the Optimistic Arm Elimination principle (OAE). We focus on developing tractable versions of these algorithms compatible with neural network function approximation.

---

Published as a conference paper at ICLR 2023
During each time-step OAE fits reward model on the observed responses seen far while the same time maximizing the reward on all the arms yet to be pulled. The algorithm then queries the batch of arms whose predicted reward is maximal among the arms that have not been tried out.
We conduct a series of experiments on synthetic and public data from the DCl & Grafi (2017) database and show that OAE is able find the optimal "arm" using fewer batch queries than other algorithms such as greedy and random sampling. Our experimental evaluation covers both neurally realizable and not neurally realizable function landscapes. The performance of OAE against benchmarks is comparable in both settings, demonstrating that although our presentation of the OAE algorithm assumes realizability for the sake of clarity, is an assumption that not required in practice. In the setting where the function class is realizable i.e. the function class F used by OAE contains the function generating the rewards, and the evaluation is noiseless we show two query lower bounds for the class of linear and 1 L-pisshitz functions.
We validate OAE on the public CMAP dataset (Subraaanian et al. (2017). which contains tens of thousands of genetic shRNA knockout perturbations, and show that always outperforms baseline and almost always outperforms a simpler greedy algorithm in both convergence speed to an optimal perturbation and the associated phenotypic rewards. These results illustrate how perturbational embeddings learned from one biological context can still be quite useful in a different biological context, even when the reward functions of these two contexts are different. Finally also benchmark our methods in the GeneDisco dataset and algorithm suite (see) Mehrjou et al. (201)) and show OAF to be competitive against benchmark algorithms in the task of maximizing HitRatios.
2 RELATED WORK
Bayesian Optimization The field of Bayesian optimization has long studied the problem of optimizing functions severely limited by time or cost Jones et al. (1998). For example, (Srinivas et al.
(2009) introduce the GP-UCB algorithm for optimizing unknown functions. Other approaches based on adaptive basis function regression have also been used to model the payoff function as in Snoek et al. (2015). These algorithms have been used in the drug discovery context. Mueller et al." (2017) applied Bayesian optimization to the problem of optimizing biological phenotypes. Very recently,
GeneDisco was released as benchmark suite for evaluating active learning algorithms for experiment design in drug discovery Mehrjou et al. (202T). Perhaps the most relevant to our setting are the
many works that study the batch acquisition setting in Bayesian active learning and optimization such as Kirsch et al. (011);; Kathuria et al. (016) and the GP - BUCB algorithm of Desautels this work we move beyond the typical parametric and Bayesian assumptions from these works towards algorithms that work in conjunction with neural network models. We provide guarantees for the no noise setting we study based on the Eluder dimension Russo & Van Roy (2013).
jet al.) (2014).
Parallel Bandits Despite its wide applicability in many scientific applications, batch learning has been studied relatively seldom in the bandit literature. Despite this, recent work (Chan et al. 2021 show that in the setting of contextual linear bandits (Abbasi-Yadkori Yadkori et al. 2011). the finite sample complexity of parallel learning matches that of sequential learning irrespective of the batch size provided the number of batches is large enough. Unfortunately, this is rarely the regime that matters in many practical applications such as drug development where the size of the experiment batch may be large but each experiment may be very time consuming, thus limiting their number. In this work we specifically address this setting in our experimental evaluation in Section
Structure Learning Prior work in experiment design tries to identify causal structures with a fixed budget of experiments Ghassami et al. (2018). Scherrer et al Scherrer et al. (2021) proposes a mechanism select intervention targets to enable more efficient causal structure learning. [Sussex et al. (202T) extend the amount of information contained in each experiment by simultaneously intervening on multiple variables. Causal matching, where an experimenter can perform a set of interventions aimed to transform the system to a desired state, is studied in Zhang al. (2021).
Neural Bandits Methods such as Neural UCB and Shallow Neural UCB Zhou et al. 2020): Xu et al. (2020) are designed to add an optimistic bonus to model predictions of nature that can be analy analyticall ytilllyy computed as is extremely reminiscent of the one used in linear bandits (Auer) 2002: Dani et al. 2008), thus their theoretical validity depends the 'linearizing' conditions to hold. More
2

---

Published as a conference paper at ICLR 2023
recently (Pacchiano et al. 2021b) have proposed the use of pseudo-label optimisim for the Bank Loan problem where they propose an algorithm that adds optimism to neural network predictions through the addition of fake data and is only analyzed in the classification setting. Our algorithms instead add optimism to their predictions. The later is achieved via two methods, either by explicitly encouraging it to fit model whose predictions are large in unseen data, or by computing uncertainties.
Active Learning Active learning is relatively well studied problem Settee 2009 Dasgupta (201)
Hanneke et al. (2014) particularly in the context of supervised learning. See for example Balcan
(2009), Dasgupta al. (2007), (Stttees] (2009). Hanneke et al. (2014). There is a vast amount of research on active learning for classification (see for example Agarwal (2013), Dekel et al. (2010)
and (Ces--Bianee et al. (2009) where the objective is to learn linearly parameterized response
model Flyl rr. Broadly speaking there are two main sample construction approaches, diversity [enner
& Savarese (2017); Geifman & Elnivn (2017); Gissin & Shalev-Shwartz/ (2019) and uncertainty
sampling Tong & Koller 20 & Cohn 2000); Balcan et al. (2009); et al. (2007),
successful in the large Guo & Schuurmans (2007; Wang & Ye 2015); Chen & Krause (2013); Wei
et al. (2015); Kirsch et al. (2019) and small batch sizes regimes respectively. Diversity sampling methods produce spread out samples to better cover the space while uncertainty-
methods estimate model uncertainty to select what points to label. Hybrid approaches are common as well. A common objective the active learning literature is to collect enough samples to produce a model that minimizes the population loss over the data distribution. This is in contrast with the objective we study in this work, which is to find a point in the dataset with a large response. There is a rich literature dedicated to the development of active learning algorithms for deep learning applications both in the batch and single sample settings SSttles et al. (207)): Ducoffe & Precioso (2018): Beluch eet al. (2018): Ash et al. (2021).
PROBLEM DEFINITION
Let y. : A + R be a response function over A Rd We assume access to a function class F C (An IR) where (An IR denotes the set of functions from A to IR. Following the typical online learning terminology we call A the set of arms. In this work we allow A to be infinite, although we only consider finite A in practice.
In our setting the experiment designer (henceforth called the learner) interacts with y, and A in a sequential manner. During the 1-th round of this interaction, aided by F and historical query and response information the learner is required to query a batch of b E N arms {a C A and observe noiseless responses {Mr, = y. (a,, (ar,)) after which these response values are added to the historical dataset De+1= = D. U {(ar.. )(,))
16
In this work we do not assume that y+ E F. Instead we allow the learner access to function class F to aid her in producing informative queries. This a common situation in the setting of neural experiment design, where we may want to use a DNN model to fit the historical responses and generate new query points without prior knowledge of whether it accurately captures y. Our objective is to develop procedure that can recover an 'almost optimal' arm E AA in the least number of arm pulls possible. We consider the following objective,
T- quantile optimality. Find an arm a, E AA belonging to the top quaamtild of {va (a)
Although 6 o-otimalliyy (find an arm a, E A such that (a.) + 2 max (a) for e 2 0) is the most common criterion considered in the optimization literature, for it to be meaningful it requires knowledge of the scale of m y. (a). In some scenarios this may be hard to know in advance. Thus in our experiments we focus on the setting of r -quantile optimality as a more relevant practical performance measure. This type of objective has been considered by many works in the bandit literature (see for example (Szorenyi et al. 2015); ZZang & Ong (202T)). Moreover, it is a measure of optimality better related to practical objectives used in experiment design evaluation, such hit ratio in the GeneDisco benchmark library |Mehroou et al. (202T) We show in Section [F] that our algorithms are successful at producing almost optimal arms under this criterion after a small number of queries. The main challenge we are required to overcome in this problem is designing a smart choice of batch
In the of infinite set A quantile optimality is defined with respect to measure over A.
3

---

Published as a conference paper at ICLR 2023
queries )= that balances the competing objectives of exploring regions of the arm space and zooming into others that have shown promising rewards.
In this work we focus on the case where the observed response values y, (a) of any arm E A are noiseless. In the setting of neural perturbation experiments the responses are the average of many expression values across population of cells, and thus it is safe to assume the observed response is almost noiseless. In contrast with the noisy setting, when the response noiseless, querying the same arm twice is never necessary. We leave the question on how design algorithms for noisy responses in the function approximation regime for future work. although note it can be reduced to our setting we set the exploitation round per data point sufficiently large.
Evaluation. After the queries U (a the learner will output a candidate approximate optimal arm å, among all the arms whose labels she has queried (all arms in Dz+1) by considering (âr, Dt) = arg (ax( EP++1 y, the point with the maximal observed reward so far. Given quantile value T we measure the performance of our algorithms by considering the first timestep firs where a r-quantile optimal point a, was proposed.
4 OPTIMISTIC ARM ELIMINATION
With these objectives in mind, we introduce a family of algorithms based on the Optimistic Arm Elimination Algorithm (OAE) principle. We call U4 the subset of arms yet be queried by our algorithm. At time any OAF algorithm produces a batch of query points of size from U4, Our algorithms start round t by fitting an appropriate response predictor ft U4 - IR based on the historical query points D. and their observed responses so far. Instead of only fitting the historical responses with a square loss and produce a prediction function ft, we encourage the predictions of fe to be optimistic on the yet-to-be-queried points of Ut.
We propose two tractable ways of achieving this. First by fitting a model (or an ensemble of models)
fo to the data in D, and explicitly computing a measure of uncertainty ūn :44 + R of its predictions on Ut We define the optimistic response predictor f((a) = (a) (a). Second, achieve this by defining J to be the approximate solution of constrained objective,
F E arg max (f JEF
S.L.
Σ (f(a) - y)² St (a.))ED.
(1)
where i possibly deme-dependent parameter satisfying T/ 0 and A(f.U) is acquisition objective tailored to produce an informative arm (or batch of arms) from Uc. We consider a couple of acquisition objectives Auvg (f, (in) Eaeus(a) (f. = (2|
1 Eaeu (max(0, f(a)))
for some > O and Asootmax (f.U) = log (E exp(f(a)) and Asum (f.u) = EnEu f(a). An important acquisition functions of theoretical interest, although hard to optimize practice are Amax (f) = maX f(a) and its batch version A (f,4) max EAEB f(a). Regardless of whether fi was computed via Equation Orr is an uncertainty aware objective of the form Je(a) [2 + (a), our algorithm then produces a query batch B, by solving
B, E arg max Aavy (Fr,
The principle of Optimism in the Face of Uncertainty (OFU) allows OAE algorithms to efficiently explore new regions of the space by acting greedily with respect model that fits the rewards of the arms in D, as accurately as possible but induces large responses from the arms she has not tried. If y. E F. and fi is computed by solving Equation it can be shown the optimistic model overestimates the true response values i.e. Enen. fe(a) Z Ene ya (a) where B.,-
arg maX = relevance of this observation.
181= Eaeg y. (a). Consult Appendix D.2 for a proof and an explanation of the
Acting greedily based on an optimistic model means the learner tries out the arms that may achieve the highest reward according to the current model plausibility set. After pulling these arms, the learner can successfully update the model plausibility set and repeat this procedure.
"The batch equals Ue when Ue < b.
4

---

Published as a conference paper at ICLR 2023
Algorithm Optimistic Arm Elimination Principle (OAE)
Input Action set A C I, num batches N, batch size b
Initialize Unpulled arms 24 A. Observed points and labels dataset D1 for f = 1........ do
If then:
Sample uniformly a size b batch B, ~ U1
Else:
Solve for ft and compute B, E arg mc [8]=b A B).
Observe batch rewards Y, = fy-(a) for a E B:}
Update D(+1 D, U {(B,, Y,)) and U,+1 U, B,,
4.1 TRACTABLE IMPLEMENTATIONS OF OAE
In this section we go over the algorithmic details behind the approximations that we have used when implementing the different OAF methods we have introduced in Section
4.1.1 OPTIMISTIC REGULARIZATION
In order to produce tractable implementation of the constrained problem | we approximate it with the optimism regularized objective.
fe E arg min
(f(a) - y) AregA(f.uu
JEF
Dr
(o.y)ED:
Optimism Regularizer
And define B, following Equation 2 Problem is compatible with DNN function approximation. In our experiments we set the acquisition function to Aavg. Aninge with p = and Asoftmax- The resulting methods are MeanOpt, HingelNNorin and MaxOpt. Throughout this work RandomBatch corresponds to uniform arm selection and Greedy to setting the optimism regularizer to 0.
4.1.2 ENSEMBLE METHODS
We consider two distinct methods (Ensemble and EnsembleNoise produce uncertainty estima- tions based on ensemble predictions. In both we fit models (ft L to Dj and define
(a) mi. (a) + min .M (a)
(a max (a) (a) i=1.-. M
2
So that Jo ūt We explore two distinct methods to produce different models ( AM fit to D, that differ in the origin of the model noise. Ensemble produces M models resulting of independent random initialization of their model parameters.
The EnsembleNoisey Y method injects 'label noise" into the dataset responses. For i (1..... .M3 we build a dataset D; = {a. y + {) for (a, y) E Di, ~ NO, 1)} where & is an i..d. zero mean M Gaussian random sample. The functions {ff Timl are defined as,
P
E arg min JEF
Σ (o.))E;;
(f(a) 2
In this the uncertainty of the ensemble predictions is the result of both the random parameter initialization the (.Ft M and the 'label noise'. This noise injection procedure draws inspiration
from methods such as RLSVI and NARL Russo (2019) and Pacchiano et al. a202aa).
4.2 DIVERSITY SEEKING VERSIONS OF OAE
In the case b > 1, the explore exploit trade-off is not the sole consideration selecting the arms that make up B, In this case, should also be concerned about selecting sufficiently diverse points within the batch B, to maximize the information gathering ability of the batch. In Section 4.2 show how extend A (hencefrtth referred vanilla OAF) to effectively induce
5

---

Published as a conference paper at ICLR 2023
query diversity. We introduce two versions OAE DvD and OAE Seq which we discuss in more detail below. A detailed description of tractable implementations of these algorithms can be found in Appendix C
4.2.1 DIVERSITY VIA DETERMINANTS
Inspired by diversity-seeking methods in the Determinantal Point Processes (DPPs) literature Kulesza & Taskar (2012), we introduce the OAE - DvD algorithm. Inspired by the DvD algorithm Parker Holder al. (2020) we propose augment the vanilla OAE objective with a diversity regularizer.
B₁ E arg max Asum (f. B) - Div(fi, 8g44
OAE DvD's Div regularizer is inspired by the theory of Determinantal Point Processes and equals a weighted log-determinant objective. OAE - DvD has access to kernel function IC:; IR x Rd + I and at the start of every time step E N it builds a kernel matrix K, E IR (4 x|ui],
K, [ j] = K(aa; az), Vi,j E Uu
For any subset B _ U, we define the OAF - DvD diversity-aware score as,
Di B) = Xdiv log (B,
(5)
Where B, B] corresponds to the submatrix of K, with columns (and rows) indexed by B and Xaiv is diversity regularizer. Since the resulting optimization problem in Equation 6 may prove to be extremely hard to solve, we design a greedy maximization algorithm to produce a surrogate solution.
The details can be found in Appendix B.1 OAE DvD induces diversity leveraging the geometry of the action space.
4.2.2 SEQUENTIAL BATCH SELECTION RULES
In this section we introduce OAE Seq generalization of the OAE algorithm designed to produce in batch diversity. OAE Seq produces query batch by solving a sequence of b optimization problems. The first element ar,1 of batch B; is chosen as the arm in 24; achieving the most optimistic prediction over plausible models (following objective and any of the tractable implementations defined in Section C either optimistic regularization or ensemble methods). To produce the second point 0,,2 in the batch (provided b > 1) we temporarily add the pair (ar,1; It,1) to the data buffer D., where It. is virtual reward estimator for ur,1. Using this 'fake labels' augmented data-set we select 0,2 following the same optimistic selection method used for a,,1 Although other choices are possible in practice the value of y- (ar,1) The name OAF Seq derives from the 'sequential' way in which the batch is produced. If OAE Seq selected arm be in the batch, and this arm has non-optimistic virtual reward v(a that is low relative to the optimistic values of other arms, then OAE - Seq will not select in the same batch. OAE Seq induces diversity not through the geometry
set Vt, mid-poin between an optimistic and pessimistic prediction of
too many arms close of the arm space but in a way that is intimately related to the plausible arm values in the function class. similar technique of adding hallucinated values induce diversity has been proposed before, for example in the GP - BUCB algorithm of Desautels et al. (2014). Ours is the first time this general idea has been tested in conjunction with scalable neural network function approximation algorithms. A detailed discussion of this algorithm can be found in Section B.I.I.
4.3 THE STATISTICAL COMPLEXITY OF ZERO NOISE BATCH LEARNING
In this section we present our main theoretical results regarding OAE with function approximation. In our results we use the Eluder dimension Russo& Van Roy (2033) to characterize the complexity of the function class F. This is appropriate because our algorithms make use of the optimism principle to produce their queries B., We show two novel results. First, we characterize the sample complexity of zero noise parallel optimistic learning with Eluder classes with dimension d. Perhaps surprisingly the regret of Vanilla OAE with batch size has the same regret profile the case b = 1 up to a constant burn in factor of order bd. Second, results holds under model misspecification, that is when y, & F at the cost of a linear dependence in the misspecification error. Although our results are for the noiseless setting (the subject of this work), we have laid the most important part of the groundwork

---

Published as a conference paper at ICLR 2023
to extend them to the case of noisy evaluation. We explain why in Appendix D.2 We relegate the formal definition of the Eluder to Appendix[D22
In this section measure the misspecification of y. via the || 2/ norm. We assume y, satisfies min Ilf - s= S w where |J - y- l = max If(a) V) Let y.- = arg min 11y. fl be the || Ilee projection of y, onto F. We analyze OAE where F computed by solving with '/ 2 (t 1 yow with acquisition objective Amax... We will measure the performance of OA via regret defined as,
Reg (T)
Σ
Σ BEB...
va(a)
Σ va)
REB.
Where B.,t maxBCu,118 =b EeEB (a). The main result in this section is,
Theorem 4.1. The regret of OAF with Amna acquisition function satisfies,
R O (dimg(F,ar)) + w (imp((,ar)TTb)
With az max (f2 inf falloo f1, F, f2]) and C max [f f(a'))
The proof of theorem 4.1 can be found in Appendix D.2 This result implies the regret is bounded by quantity that grows linearly with w, the amount of misspecificatioo but otherwise only with the scale of dim (FF, 0b) The misspecification part of the regret scales as the same rate as sequential algorithm running Tb batches of size 1. When w = O, the regret upper bounded by O [dim (r))d). For example, in the case of linear models, the authors of Russo & Van Roy (2013) show dimg(F,e) = O (dlog()/))) This shows that for example sequential OAE when achieves the lower bound of Lemma D.I up logarithmic factors. In the setting of linear models, the dependence in the rate above is unimprovable by vanilla OAE without diversity aware sample selection. This is because optimistic algorithm may choose to use all samples in each batch to explore single unexplored one dimensional direction. Theoretical analysis for OAE DvD and OAE Seq is left for future work. In Appendix D.I we also show lower bounds for the query complexity for linear and Lipshitz classes.
5 TRANSFER LEARNING ACROSS GENETIC PERTURBATION DATASETS
In order to show the effectiveness of OAE in the large batch small number of iterations regime we consider genetic perturba- tions from the CMAP dataset Subramanian et al. (2017), which contains 978-gene bulk expression readout from thousands of single-gens gene shRNA knockout perturbations across a number of cell lines.
We consider the setting in which we have observed the effect of knockouts in one biological context (i.e., cell line) and would like to use it to plan series of knockout experiments in another. Related applications may have different biological contexts, from differentt cell types experimental conditions. We use the level 5 CMAP observations, each of which contains of 978-gene transcriptional readout from an shRNA knockout of a particular gene particular cell line. our experiments, choose optimize a cellular proliferation phenotype, defined as a function the 978-gene expression space. See Appendix F for details.
1200 2900
Regression mean squared error loss for models that predict cell-line specific phenotypic rewards from VCAII-derived per- turbational features.
Figure
We the 4 cells lines with the most number genetic perturbations in common: VCAP (prostate cancer. n = 14602) ), HA1E (kidney epithelium, = 10487), MCF7 (breast cancer, = 6638), and A375 (melanoma, n 10033). We first learn 100-dimensional action (perturbation) embedding a; for each perturbation in VCAP with an autoencoder. The autoencoder has a 100-dimension
'The shRNA perturbations are just subset of the 1M+ total perturbations across different perturhation classes.
7

---

Published as a conference paper at ICLR 2023
Figure 3: Linear. T-quantile batch convergence of MeanOpt on genetic perturbation datasets.
bottleneck layer and two intermediate layers of 1500 and 300 ReLU units with dropout and batch normalization and is trained using the Adam optimizer mean squared reconstruction loss. We use these 100-dimensional perturbations embeddings as the features to train the ft functions for each of the other cell types. According to our OAE algorithm, we train a fresh feed-forward neural network with two intermediate layers (of 100 and 10 units) for after observing the phenotypic rewards for each batch of 50 gene (knockout) perturbations. Figure 6 summarizee this approach.
Figure shows the mean squared error loss of models trained to predict the cell-line specific phenotypic reward from the 100-dimensional VCAP- derived perturbational features. These models are trained on successive batches of perturbations sampled via RandomBatch and using the same NN 1500-300 hidden layer architec- ture of the decoder. Not surprisingly, the loss for the VCAP reward is one of the lowest, but that of two other cell lines (HA1E and MCF7) are also quite similar, showing the NN 1500- 300 neural net function class is flex- ible to learn the reward function in one context from the perturbational embedding in another.
A375 Quar turthim
Quanciles
Crack
17.5
Srear
12.5
Loddo Li
12.5
HAXE Quandies
HADE Quanttiee
Lemtt lifender
Lamdler 2. Mear
Quantiles 2N1
NC77 Quanties
MCFT Quanttiee
In all of experiments con- sider either linear or neural net- work function class with ReLU acti- vations. In all of them we consider a batch size b 50 and number of batches N = 20. Figure 2 shows the convergence and reward results for the 4 cell lines when the neu- ral network architecture equals NN 100-10. Since the perturbation action features were learned on the VCAP dataset (though agnostic to any phe- notypic reward), the optimal VCAP perturbations are found quite quickly by all versions of MeanOpt includ- ing Greedy. Interestingly, MeanOpt still outperforms RandomBatch in the HAIE and MCF7 cell lines but not on A375. When the neural network architecture equals NN 10-5, McanOpt is only competitive with RandomBatch on the VCAP and MCF7 datasets (see figure 37 in Appendix G.4). Moreover, when FF is class of linear functions, MeanOpt can beat RandomBatch only in VCAP. This can be explained by looking at the regression fit plots of figure 4 The baseline loss value is the highest for A375 even for NN 100-10, thus indicating this function class is too far from the true responses values for A375. The loss curves for NN 10-5 lie well above those for NN 100-10 for all datasets thus explaining the degradation in performance when switching from NN 100-10 to smaller capacity
Londo 5411
lifender
Chanrilee
VCAP Quarttiie
VCAP Quanttlin
dal the
201
06
12
0.5
Figure 2: NN 100-10 --quantile batch convergence ge- netic perturbation datasets of MeanOpt (left) and Ensemble, FnsembleNoise (right).
8

---

Published as a conference paper at ICLR 2023
of NN 10-5. Finally, the linear fit achieves very small loss for VCAP explaining why McanOpe still outperforms RandomBatch in VCAP with linear models. In all other datasets the linear fit is subpar to the NN 100-10, explaining why MeanOpt in NN 100-10 works better than in linear ones. We note that Fnnemble@ptimiist 100-10 architectures in 7 our of the 8 experiments we conducted. In Appendix (.44 the reader can find results for MaxOpt and HingeOpt. Both methods underperform in comparison with MeanOpt. In Appendix E.2.1 and E.2.2 the reader will find experiments using tractable versions of OAE DvD and OAE Seq. In Appendix [ and G we present extensive additional experiments and discussion of our findings over different network architectures (including linear), and over variety of synthetic and public datasets from the UCI database Dua & Grafi (0117
is competitive with RandomBatch in both NN 10-5 and NN
A778 Neprosker
IAGE Pe
MCT1 Segeossien
VCJ Eag eniion Pr
Figure 4:
Training set regression fit curves evolution over training for the suite of gene perturbation datasets. Each training batch contains 10 datapoints.
5.0.1 GENEDISCO EXPERIMENTAL PLANNING BENCHMARK
We test a Bayesian OAE algorithm against the GeneDisco benchmark Mehrjou et al. (202T). which assess the "Hit Rate" of different experimental planning algorithms over number of pooled CRISPR experiments. We assess our performance against the other acquisition functions provided in the public implementation that select batches based solely on uncertainty considerations. We use the public implementation of GeneDisco and do not change the neural network architecture provided corresponding to a Bayesian Neural Network with a hidden layer of size 32. We use the 808 dimensional Achilles treatment descriptors and built fe by adding the BNN's uncertainty to the model base predictions. We test our algorithm in the Schmidt et al. 2021 (IFNg), Schmidt et al. 2021 (II.2), Zhuang et al. 2019 (NK), and Zhu al. 2021 (SarsCov2) datasets and tested for performance using the Hit Ratio metric after collecting 50 batches of size 16. This is defined as the ratio of arm pulls lying in the top .05 quantile of genes with the largest absolute value. Our results are in Table 5 OAE outperforms the other algorithms by substantial margin in 3 out of the 4 datasets that we tested.
Dataset
UocUncertain
SoftUncertain
Bay-Baaesian
Schmidt et al. 2021 (IFNg)
0.057
0.046
0.062
Schmidt et al. 2021 (1L2)
0.083
0.081
0.107
Zhuang et al. 2019 (NK)
0.035
0.047
0.085
Zhu et al. 2021 (SarsCov2)
0.035
0.049
0.0411 1
Figure 5: Hit Ratio Results after 50 batches of size 16. BNN model trained with Achilles treatment descriptors. Final Hit Ratio average of 5 independent runs. TopUncertain selects the 16 points with the largest uncertainty values and SoftUncertain samples them using a softmax distribution.
6 CONCLUSION
In this work we introduce variety of algorithms inspired in the OAE principle for noiseless batch bandit optimization. We also show lower bounds for the query complexity for linear and Lipshitz classes as well as a novel regret upper bound in terms of the Eluder dimension of the query class. Our theoretical results hold under misspecification. Through a variety of experiments in synthetic, public and biological data we show that the different incarnations of OAE we propose in this work can quickly search through a space of actions for the almost optimal ones. This work focused in the case where the responses are noiseless. Extending our methods and experimental evaluation to the case where the responses are noisy is an exciting avenue for future work.
https:://ii thw.. wtw.bb/.com//eete gemmm/eeeddiiic sco/ gened//eedd sco- starter

---

Published as a conference paper at ICLR 2023
REFERENCES
Yasin Abbasi- Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24:2312-222 2320, 2011.
Alckh Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. In Interna- tional Conference on Machine Learning, pp. 1220-1228. PMLR, 2013.
Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Gone fishing: Neural active learning with fisher embeddings. Advances in Neural Information Processing Systems, 34:8927- 8939, 2021.
Auer. Using confidence bounds for exploitation-exxloraiion trade-offs. Journal of Machine Learning Research, 39Nov):397-422, 2002.
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-8, 2009.
William H Beluch, Tim Genewein, Andreas Nürnberger, and Jan M Köhler. The power of ensembles for active learning in image classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 9368-9377, 2018.
Erdem BIyIk, Kenneth Wang, Nima Anari, and Dorsa Sadigh. Batch active learning using determi- nantal point processes. arXiv preprint arXiv: arXiv:/906.07990 190699997677 2019.
Nicolo Cesa-Biandis Claudio Gentile, and Francesco Orabona. Robust bounds for classification via selective sampling. In Proceedings of the 26th annual international conference machine learning, pp. 121-128, 2009.
Jeffrey Chan, Aldo Pacchiano, Nilesh Tripuraneni, Yun S Song, Peter Bartlett, and Michael Jordan. Parallelizing contextual linear bandits. arXiv preprint arXiv:2105. 10590, 2021.
Yuxin Chen and Andreas Krause. Near-optimal batch mode active learning and adaptive submodular optimization. In International Conference on Machine Learning, pp. 160-168. PMLR, 2013.
V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. In COLT, pp. 355-366. Omnipress, 2008
Sanjoy Dasgupta. Two faces of active learning. Theoretical computer science, 1777191: 2011.
Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. Advances in neural information processing systems, 20, 2007.
Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Robust selective sampling from single and multiple teachers. In COLT, pp. 346-358, 2010.
Thomas Desautels, Andreas Krause, and Joel W. Burdick. Parallelizing exploration-exploitatoo tradeoffs in gaussian process bandit optimization. Journal of Machine Learning Research, 15(119); 4053-4103, 2014. URL jmmr:///mmr..... jmlr. http:///sss/s//////aaaaaaeaaaaa.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL /ttt/:t/t///hhh
ics. uci www.uuiiuu..uouuu ml
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. arXiv preprint arXiv: 1802.0940, 2018.
Yonatan Geifman and Ran El-Yaniv. Deep active learning over the long tail. arXiv preprint arXiv: 2017.
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted experiment design for causal structure learning. In International Conference on Machine Leamning pp. 1724-1733. PMLR, 2018
10

---

Published as a conference paper at ICLR 2023
Daniel Gissin and Shai Shalev-Shward arXiv:1907.06447, 2019.
Discriminative active learning.
arXiv preprint
Yuhong Guo and Dale Schuurmans. Discriminative batch mode active learning, Advances in neural information processing systems, 20, 2007.
Insu Han, Prabhanjan Kambadur, Kyoungsoo Park, and Jinwoo Shin. Faster greedy map inference for determinantal point processes. In International Conference Machine Learning, pp. 1384-1393. PMLR, 2017.
Ruth E Hanna and John Doench. Design and analysis of CRISPR-Cas CeissPR-aseepprrieeenss Nat. Biotechnol., 38(7):813 823, July 2020.
Steve Hanneke et al. Theory of disagroement-basee active learning. Foundations and Trends@ in Machine Learning, 7(2-3):131-39,, 2014.
Donald R Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13(4):455-492 1998.
Tarun Kathuria, Amit Deshpande, and Pushmeet Kohli. Batched gaussian process bandit optimization via determinantal point processes. Advances in Neural Information Processing Systems, 29: 4206-4214, 2016.
Andreas Kirsch, Joost Van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. Advances in neural information processing systems, 32:7026-7037, 2019.
Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. arXiv preprint 12X 2012.
Arash Mchrjou, Ashkan Soleymani, Andrew Jesson, Pascal Notin, Yarin Gal, Stefan Bauer, and Patrick Schwab. Genedisco: benchmark for experimental design in drug discovery. arXiv preprint
2021.
Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014.
Jonas Mueller, David Reshef, George Du, and Tommi Jaakkola. Learning optimal interventions. In Artificial Intelligence and Statistics, pp. 1039-1047. PMLR, 2017.
George Nemhauser, Laurence Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical progrumming, (4(1):265-2944 1978.
Aldo Pacchiano, Philip Ball, Jack Parker-Holder Krzysztof Choromanski, and Stephen Roberts. Towards tractable optimism in model-based reinforcement learning. In Uncertainty in Artificial Intelligence, pp. 1413-1420 PMLR, 2021a.
Aldo Pacchiano, Shaun Singh, Edward Chou, Alex Berg, and Jakob Foerster. Neural pseudo-label optimism for the bank loan problem. Advances in Neural Information Processing Systems, 34, 2021b.
Jack Parker-Holder. Aldo Pacchiano, Krzysztof M Choromanski, and Stephen J Roberts. Effective diversity in population based reinforcement learning. Advances in Neural Information Processing Systems, 15:18050-18065 2020.
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems, 32, 2019.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Newral Information Processing Systems, 26, 2013.
Nino Scherrer, Olexa Bilaniuk, Yashas Annadani, Anirudh Goyal, Patrick Schwab, Bernhard Schölkopf, Michael C Mozer, Yoshua Bengio, Stefan Bauer, and Nan Rosemary Ke. Learn ing neural causal models with active interventions. arXiv preprint 1092:2210,.00222, 2021.
11

---

Published as a conference paper at ICLR 2023
Greg Schohn and David Cohn. Less is more: Active learning with support vector machines. In ICML, volume 2, pp. 6. Citeseer, 2000.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv::708. 70088, 2017.
Burr Settles. 2009.
Burr Settles, Mark Craven, and Soumya Ray. Multiple-instance active learning. Advances in neural information processing systems, 20, 2007.
Jasper Snoek, Oren Rippel. Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable bayesian optimization using deep neural networks. In International conference on machine learning, pp. 2171-2180. PMLR, 2015.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
Aravind Subramanian, Rajiv Narayan, Steven M Corsello, David D Peck, Ted E Natoli, Xiaodong Lu, Joshua Gould, John F Davis, Andrew A Tubelli, Jacob K Asiedu, David L Lahr, Jodi E Hirschman, Zihan Liu, Melanie Donahue, Bina Julian, Mariya Khan, David Wadden, Ian C Smith, Daniel Lam, Arthur Liberzon, Courtney Toder, Mukta Bagul, Marek Orzechowski, Oana M Enache, Federica Piccioni, Sarah A Johnson, Nicholas Lyons, Alice H Berger, Alykhan F Shamji, Angela N Brooks, Anita Vreic, Corey Flynn, Jacqueline Rosains, David Y Takeda, Roger Hu, Desiree Davison, Justin Lamb, Kristin Ardlie, Larson Hogstrom, Peyton Greenside, Nathanael S Gray, Paul A Clemons, Serena Silver, Xiaoyun Wu, Wen-Ning Zhao, Willis Stephen J Haggarty, Lucienne V Ronco, Jesse S Boehm, Stuart L. Schreiber, John G Doench, Joshua Bittker, David Root, Bang Wong, and Todd R Golub. A next generation connectivity map: L1000 platform and the first 1,000,000 profiles. Cell, 17 17166):437-14552.1111 November 2017.
Xiaohua Wu,
Scott Sussex, Andreas Krause, and Caroline Uhler. Near-optimal multi multi--ertuuraaton experimental design for causal structure learning. arXiv preprint 1r11v:2105.14024, 2021.
Balazs Szorenyi, Róbert Busa-Fekete, Paul Weng, and Eyke Hüllermeier. Qualitative multi-armed bandits: A quantile-based approach. In International Conference on Machine Learning, pp. 1660-1668, PMLR, 2015.
Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. Journal of machine learning research, 2(Nov):45-66, 2001.
Martin J Wainwright. High- dighnssimesii statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode
active learning. ACM Transactions on Knowledge Discovery from Data (TKDD), 9(3):1223, 2015.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International conference machine learning, pp. 1954-1963. PMLR, 2015.
Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint 20 2020.
Mengyan Zhang and Cheng Soon Ong- Quantile bandits for best arms identification. In International Conference on Machine Learning, pp. 12513-12523. PMLR, 2021.
Vicky Zhang, Chandler Squires, and Caroline Uhler. Matching a desired causal state via shift interventions. Advances in Neural Information Processing Systems, 34, 2021.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration, 2020.
12

---

Published as a conference paper at ICLR 2023
CONTENTS
Introduction
Related Work
Problem Definition
4
Optimistic Arm Elimination
Tractable Implementations of OAE
4.1.1
Optimistic Regularization
2
Ensemble Methods
4.2
Diversity seeking versions of OAE
4.2.1
Diversity via Determinants
4.2.2
Sequential batch selection rules
The Statistical Complexity of Zero Noise Batch Learning
Transfer Learning Across Genetic Perturbation Datasets
5.0.1
GeneDisco Experimental Planning Benchmark
Conclusion
Transfer Learning Across Genetic Perturbation Datasets
14
B Complementary description of the methods
15
B.I Appendix Diversity via Determinants
15
B.1.1 Sequential batch selection rules
16
Tractable Implementations of OAE - DvD and OAE - Seg
17
C.0.1 Diversity via Determinants
17
C.0.2 Sequential Batch Selection Rules
17
Theoretical Results
18
D.I
Quantifying the Query Complexity of F.
18
D.2 Optimism and its properties
D.3 Noisy responses
25
Experiments
25
Vanilla QAE
26
E.1.1
Synthetic One Dimensional Datasets
26
E. E.1.2
Public Supervised Learning Datasets
................................
29
Experiments Diversity Seeking Objectives
30
F.2.1
OAE Dvl)
31
13

---

Published as a conference paper at ICLR 2023
E.2.2 OAE Seq
32
F
Cellular proliferation phenotype
34
G
Further Experiments
35
G.1
Synthetic Datasets
35
G.2
Regression Fitted Datasets
37
G.3 UCI public datasets
37
G.4
Transfer Learning Biological Datasets
38
A
TRANSFER LEARNING ACROSS GENETIC PERTURBATION DATASETS
In this section we have placed diagrammatic version of the data pipeline described in section
(e) Leern perturbasion action embedding space
Giological comeet
Select init perturtation
(c) Perform batched experimental
Idi Concarenzte observed perturbetions
Biological context
Lundtoooooh phonotyp
Solect perturbatian batch
Predict optim rewards unstavrrved persurbssiors
(e) phenstypir roward regression
Figure 6: Neural design for genetic perturbation experiments. (a) Learn perturbation action embedding space by training an autoencoder on the gene expression resulting from a large set of observed genetic perturbations in particular biological context (e.g., shRNA gene knockouts for particular cell line in CMAP). (b) Select an initial batch of B perturbation actions to perform in parallel within related (but different) biological context. Selection by prior information about the relationship between genes and the phenotype to be optimized. (c) Perform the current batch of experimental perturbations in vitro and observed their corresponding phenotypic rewards. (d) Concatenate the latest batch's 's features and observed rewards to those of previous batches to update the perturbation reward training set. (e) Train new perturbation reward regression (with some degree of pre-defined optimism) network on the observed perturbation rewards. (f) Use this regressor to predict the optimistic rewards for the currently unobserved perturbations. (g)
be random (uniform) influenced
Select the next batch from these unobserved perturbations with the highest optimistic reward.
14

---

Published as a conference paper at ICLR 2023
B COMPLEMENTARY DESCRIPTION OF THE METHODS
B.1 APPENDIX DIVERSITY VIA DETERMINANTS
Inspired by diversity-scekie methods in the Determinantal Point Processes (DPPs) literature Kulesza & Taskar (2012), we introduce the OAE DvD algorithm. Inspired by the DvD algorithm ?? we propose the
DPPs can be used to produces diverse subsets by sampling proportionally to the determinant of the kernel matrix of points within the subset. From geometric perspective, the determinant of the kemnll matrix represents the volume of a parallelepiped spanned by feature maps corresponding to the kernel choice. We seek to maximize this volume, effectively "filling" the feature space. Using determinant score to induce diversity has been proposed as a strategy in other domains, most notably in the form of the Diversity via Determinants (DvD) algorithm from Parker- Based Reinforcement Learning. It is from this work that we take inspiration to name our algorithm OAE DvD. The idea of using DPPs for diversity guided active learning has been explored by Biyık et al. (2019). In the active learning setting the objective function used to build the batch is purely driven by the diversity objective. The method works as follows. At time L, OAE - DvD constructs a regression estimator fi using the arms and responses in Dj (for example by solving problem l). Instead of using Equation our algorithm selects batch B, by optimizing diversity aware objective of the form,
al. (2020) for Population
B, E arg max Anam (Je. B) - Div (Ji, B). BC)+
(6)
OAE DvD's Div regularizer is inspired by the theory of Determinantal Point Processes and equals a weighted log-determinant objective. OAF DvD has access to kernel function IC IRd xR and at the start of every time step E N it builds a kernel matrix K, E RR 14, x|41,
IR
K, KC(a,, ay), Vi.j Ut.
For any subset B C U4 we define the OAE DvD diversity-aware score as, Div = Adiv log (Det(K,(B,B))
Where K, [B, B) corresponds to the submatrix of K, with columns (and rows) indexed by B and Aaiv a diversity regularizer. Since the resulting optimization problem in Equation (6 may prove to be extremely hard to solve, design greedy maximization algorithm to produce surrogate solution. We build the batch B, greedily. The first point a,, in the batch is selected to be the point in 24 that maximizes the response F.. For all i the point az in Ue is selected from U4 Mar.s)j Li-1 such that,
Agum (Fe, {a} (at.s 1 + Div(Fe, {a} U fau, 1/=))
max Mar. 16-1
Ma
Algorithm 2 Optimistic Arm Elimination DvD (OAE - DvD)
Input Action set A C Rd, num batches N, batch size b, Adiv Initialize Unpulled arms Ui = A. Observed points and labels dataset Dj for t 1,... .V do if' then Sample uniformly a size b batch B, ~ Ui.
else
Compute B, using the greedy procedure described above.
Observe batch rewards Y, = fv- for a E B.} Update D D, U [[B,, Y.)). Update Ui-1 = 2,).B,B B,
We define reward augmented kernel matrix (i.j) = (i((,.) exp (((()+ This matrix
satisfies K,,0(B, [] = diag (Voxp(Ti/Aac))
[B, B] K, B3) diag (Voxp(Fe/ /dee)) [B3
15

---

Published as a conference paper at ICLR 2023
for all B Ut. Since the determinant of product of matrices is the product of their determinants it follows that Det(K, [B, B]) exp Ener fe(a)/
Adae)) Det (K) Thus for all B C U..
equation 6 with diversity score can be rewritten as
Bt E arg max log (K, (B)) BC
Eoen F((o) + log (Be for all B C U4 It is Adir well known the degermeerminant set function for a positive semidefinite matrix is submodular (see for example section 2.2 Han et al. (2017)). It has long been established that the greedy algorithm achieves an approximation ratio of (1- - for the constrained submodular optimization problem (see Nembauser et (1978)). This justifies the choices we have made behind the greedy algorithm we use to select B,.
This is because log (Det (K; [B, B)))
B.1.1 SEQUENTIAL BATCH SELECTION RULES
In this section we introduce OAE Seq generalization of the OAE algorithm designed to produce in batch diversity. OAE Seq produces query batch by solving sequence of b optimization problems. OAE Seq uses first Di,0 DD the set of arms pulled so far well Uh,0 U (the set arms yet to be pulled) to produce a function f(,1 that determines the initial arm in the batch via the greedy choice 0,,1 arg max (a). The function ft, computed using the same method as any vanilla OAE procedure. Having chosen this arm, in the case when b > 1, virtual reward It.1 (possibly different from (z( )) is assigned to the query arm 0t,1, and datasets Dr,1 Dr () and U1 Ue \ {ar,1) } are defined. The same optimization procedure that produced fr,1 used to output fr. now with D and U4 as inputs. Arm a₁2 is defined as the greedy choice 0r,2 arg max (a). The remaining batch elements (if any) are determined by successive repetition of this process so that D.,- D.uf(ar. Vrs));=1 and U, U4 /ot, )/ The trace of this procedure leaves behind sequence of functions and datasets { U4 1) such that 0r arg max Fa)
Algorithm 3 Optimistic Arm Elimination Batch Sequential (OAE Seq)
Input Action set A C Rdd number of batches N, batch size b, pessimism-optimism balancing parameter a. Initialize Unpulled arms 24 = A. Observed points and labels dataset D1 for 1,... do if t then Sample uniformly size batch B, Ui.
else
Solve for ((,,), via the procedure described in the text. Compute
B. = {ar, E arg max (a)
(8)
aEU,,-.
Observe batch rewards Y, (f.(a) for a E B,} Update D D, U {(B,, Y.)) D. Update Ue-1 = B.
To determine the value of the virtual rewards Dr. we consider variety of options. We start by discussing the case when the fake reward Vr. = f((,,.) and the acquisition function equals Aram A (f,
16

---

Published as a conference paper at ICLR 2023
When " = 0, the fake reward satisfies Ve, f((sss) and y, F it follows that ft. fc independent of E [B] is a valid choice for the function ensemble (fr In this case the query batch B, can be computed by solving for Jt.
ft arg Σ f(a) JEF aeuls
Σ (f(a) - -)² =0. (a,y)EDs,
(9)
And defining the batch B, as
B
arg max
F((a)
BCU [B|=b dEB
The equivalence between this definition of B, and the sequential batch selection rule follows by noting the equality constraint from ensures that ft, Ft valid solution for each of the intermediate problems defining the sequence {(fe.i, k
OAE Seq is designed with more general batch selection rule that may yield distinct intermediate arm selection functions { In our experiments we compute the virtual reward Dt. as an average
of f
Toptimistic and t,t
Apessimisticc optimistic and a pessimistic estimators of the responses in U1
Epessimistic First when the computation We consider two mechanisms for computing Toptimistic and ft, Jr,
of Je.i based on producing an uncertainty function ū4,, and a base model Jū, we define Joptimistic Jea
ft. uu, and f /pessimistic Jí. Ur,i. Second, we define Lt,
joptimistic and f
ppessimistic the solutions
of the constrained objectives
joptimistir arg max A(f,4) ft,1
Epessimistic. = min A(f.4) Jt
and
JEFLi
JEF
Where = [ F.t. E(ay)ED (S(a) - -)² S 7.). In both cases we define the fictitious rewards weighted average of the pessimistic and optimistic predictors Ve., affs
Toptimistic (1
o where E [0, 1] is an optimism weighting parameter while we keep the functions used to define what points are part of the batch as Jr.i Jt, foptimistic The principle of adding hallucinated values to induce diversity has been proposed before for example in the GP BUCB algorithm of Desautels et al. (2014).
C TRACTABLE IMPLEMENTATIONS OF OAE - DvD AND OAE - Seq
In this section we go over the algorithmic details behind the approximations that we have used when implementing the different OAE methods we have introduced Section
C.O.1 DIVERSITY VIA DETERMINANTS
The OAE DvD algorithm differs from OAE only in the way in which the query batch B, is computed. OAE DvD uses equation instead equation 2 Solving for B, done via the greedy algorithm described in Section 4.2.1 The function fc can be computed via a regularized optimization objective using an ensemble. In our experimental evaluation we opt for defining fo via the regularization route as the result of solving problem 3 More experimental details including the type of kernel used are explained in Section E.2 In experimental evaluation we use the MeanOpt objective produce F and refer to the resulting method DetD.
C.0.2 SEQUENTIAL BATCH SELECTION RULES
We explore different ways of defining the functions {f. 1-1- Depending on what procedure we use to optimize and produce these functions we will obtain different versions of OAE Seq. We ioptimistic ) and
the name B denote the OAF Seq method that fits the functions (
17

---

Published as a conference paper at ICLR 2023
pessimistic 1
by solving the regularized objectives,
i==
Jt
poptimistic
arg min
1
Σ
(f(a) y)² (f.
JEF
Di,i-1l
(a.y)EDe,r-1
Epessimistic
arg min JEF
1
E
(f(a) +do
D2,1-1
(a.y)ED.,.-1
In experiments set the acquisition function to Aavg- For value of Areg zoptimistic and the virtual rewards as Vt.s The functions (f are defined as ft, = Jt.i
Poptimistic + (1 a) fti fpessimistic where a [0, 1] an gggimism-pessiming weighting param- aft.
eter. In our experimental evaluation we use = More experimental details are presented in Section [+
The functions joptimistic راا
Ji=1 and pressimistic j Tiz1 can be defined with the use of an ensemble.
Borrowing the definitions of Section 4.1.2
Poptimistic t,
-
ipessimistic
Po ug,5.
Where ff, and ie, computed by first fitting ensemble of models ( using dataset Di,i-1 In our experimental evaluation we explore the use of Ensemble and EnsembleNoisey optimization styles to fit the models ) In our experiments
the names Ensemble SeqB and Ensemble - SeqB YoiseY to denote the resulting sequential batch selection methods. More details of our implementation can be found in Section
D THEORETICAL RESULTS
D.1 QUANTIFYING THE QUERY COMPLEXITY OF F.
Let 2 0 and define (A,
be the first time-step when an o-otmmall point å is proposed by learner (possibly randomized) when interacting with arm set A C Rd and the pseudo rewards are noiseless evaluations (f(a)) with f E F. We define the query complexity of the A, pair as,
f) (A,
(*A, = min max E [V (A,
Alg /EF
Where the minimum iterates over all possible learning algorithms. We can lower bound of the problem complexity for several simple problem classes, Lemma D.1. When A = {|0|| < for x Rd] and
1. If F the class of linear functions defined by vectors the unit ball == |0|| < for 8 E Rdd then T (AA,) 2 d when e < and T (AA, F) 2 [d- ed otherwise.
= {i 0T
2. If F the class of -iipscchttz functioo
functions then T (A.F) Z (1)
Proof. As a consequence of Yao's principle, we can restrict ourselves to deterministic algorithms. Indeed,
min max [1 (A, = max min Ey-Dy [t (A, Dy DetAlg
Alg FEF
Thus, to prove the lower bound we are after enough to exhibit distribution D> over instances F and show lower bound for the expected (A, f) where the expectation is taken using Dyr.
With the objective of proving item 1 let DD be the uniform distribution over the sphere Unif, By symmetry easy to see that
Eg-.Unifa(r) [0.] O,
Vi E and Vr 2 0.
"As have pointed out in Section 4.2.2 setting Aveg reduces OAF Seg vanilla QAF.
18

---

Published as a conference paper at ICLR 2023
Thus,
Varg~Unifa(r) (0:) = Uni [09] 10 r2
(10)
d
Equality (i) follows because
En-Unita (rriii(11))
and because by symmetry for all i, E [d] the second moments agree,
un- unif
Finally,
En..Umitaa
uni Vd
(11)
Let Aet.Alg be the optimal deterministic algorithm for Dy and be its first action. Since Dy is the unofrm distribution over the sphere, inequality [T expected scale of the reward reward experienced upper bounded by V and furthermore, since |a = 1, the expected second moment of the reward
experienced (where expectations are taken over D>) equals 1
We now employ conditional argument, if DetAlg has played aj and observed reward ri,
We assume that up to time m algorithm DetAlg has played actions ",,"." Om and received rewards F1,"" Tm.
Given these outcomes, DetAlg can recover the component of 0 lying in span(ai,... ..m) Let am+1 be DetAlg's action time m+ 1. By assumption this is deterministic function of a1.-.- am and '*, .'m- Since 0 is drawn from Unifa(1), the expected squared dot product between the component of a Proj(am+1, span(( amm) 1) satisfies,
1 | 11?
a a+++1)
(1
|| | 112)
= d m
1 0 11
(12)
d m
where 8 Proj(O, (paa(a).. am))) The last inequality follows because the conditional distri- is a uniform distribution
bution of Proj(0, span(a1,""
(a1, ... am) given 01, am and Fi.
over the d - m dimensional sphere of radius /I |0 1|= the scale of a is v ||o || and
we have assumed the || | = 0. Thus, the agreement of a with Proj(O, span (01, am )
satisfies Equation IO.
We consider the expected square norm of the recovered 0 to time m. This is the random variable |10% 112 Σm= (aaatt where at Proj(a, span(a1." +t) Thus,
m
EanDy [110
BBnDD
0 a )²²
m
EanDy (a] 0= (00 ata
BBaDD
m
1
1000
EanDY
m
Equality (i) holds because of 12 Recall that by Equation 10
Ea-Dz [109]13]
d
19

---

Published as a conference paper at ICLR 2023
Thus by the above equalities,
1
1 1
2 d
DD D=
d
d
Unrolling these equalities further we conclude that
EE-DY [100 |1
m d
This implies the expected square agreement between the learner's 's virtual guess â is upper bounded by 7. Thus, when z. the expected number of queries required is at least d. When d, the expected number of queries instead satisfies lower bound of [d ed].
We now show shift our attention to Lipschitz functions. First we introduce the following simple construction of 1-Lipschitz function over small ball of radius e. We use this construction throughout our proof. Let Rd be an arbitrary vector, define [xx, c) as the ball centered around x of radius 2c under the ll2 norm and S(x, 2c) as the sphere (the surface of Bxx, 2c)) centered around x
Define the function f R R as,
( || - 22112 if E B(x, 2c)
(Z(z) (0
O.W.
It is easy to see that fx is Lipschitz. We consider three different cases,
1. If 21, 22 E Bxx 2 then 1/((21) - [z(22) = 0 < ||| 22|l. The result follows.
2. If E Bxx, 2c) but 22 E (xx, 2c Let be the intersection point in the line going from 31 to Z2 lying on S(x, 2c). Then [f(())) [2() = minlgee((.22)
||z| - z 1|2 S
2z] zs11 S Z1 z 112.
3. If 1 Zg (xx 2E). It is easy to see that (z) - [2(2)) |||
x||2 | x
x||2|
And therefore by the triangle inequality applied to x, Z1, Z2, that |||| - x||2 Iz x
|z| Z2 2- The result follows.
Let (B, 1), 2e) be 2E- 2e-packnng of the unit ball. For simplicity we'll use the notation N2.- [W(B(0, 1), 2e)l. Define the set of functions F = {ff for all x E (O, 1), 2c)} and define D) as the uniform distribution over F F. Similar to the case when F is the set of linear functions, we make use of Yao's principle. Let DetAlg be an optimal deterministic algorithm for Dyr
Let a, be DetAlg's i-th query point and r be the i-th reward it receives. If the ground truth was fc and the algorithm does not sample query point from inside B(x, 2c). it will receive a reward of 0 and thus would not have found opotiaal point. Thus topt (fx) first time to pull arm in B(x, 1). As a consequence of this fact,
1
EYzDD [1 ((x)2e))] N2c
Hence EsgnD= [1(a1 & B(x, 2c))
No. Therefore,
No. N2c -1
E [ppp
N₂. {++l 1
t=1
No./2
N2c
N2. +
N2
())
(1))
Since N2. 2 Covering( (0, 1).4c)
2 (1)2 where inequality (i) is consequence of Lemma 5.5
and inequality (ii) from Lema 5.7 in Wainwright 2019).
20

---

Published as a conference paper at ICLR 2023
Translating to Quantile Optimality The results of Lemma Lem can be interpreted in the langauge of quantile optimality by imposing a uniform measure over the sphere. In this case e-optimality is equivalent (approximately) to a 2 d-d(1-)) quantile.
The results of Lemma D.1 hold regardless of the batch size B. It thus impossible design an algorithm that can single out an e-optimal arm in less than T (AA.) queries for all problems defined by the pair A, simultaneously.
D.2 OPTIMISM AND ITS PROPERTIES
The objective of this section is to prove Theorem 4.1 which restart for the reader's convenience.
Theorem 4.1. The regret of OAE with Amaxxb acquisition function satisfies,
Reg y (T) = O (dimm(F, or)) + wv (imm:(F,r)))
With ar max (1. inf [I f2 f1, E F, fe)) and C maxxer,,,a' ([() f(a'))
Let's start by defining the e- e-Eluder dimension, a complexity measure introduced by Russo & Van Roy] (2013) to analyze optimistic algorithms. Throughout this section we'll use the notation 1 v /'.Es (a) denote the data norm of function g A - R.
Definition D.2. Let and 2 {a A be a sequence of arms.
1. An action a is e depeedeent Z with respect to F if any f. E F satisfying (f(a)(a)) (a())) < also satisfies [f(a) fa)) e.
2. An action is e-nndependent of Z with respect F if
dependent on Z.
3. The e-eluder dimension dimg(F,e e) of function class F the length of the longest sequence of elements in A such that for some e' 2 e, every element is é' independden of its predecessors.
S w where || = max,ez Ig(a)), Let Lemma D.3. Let's assume ys satisfies minfer - fl 11y+-1l
V. arg min llv. - floo be the || oloe projection of onto F. If fo is computed by solving ! with 7 2 (t - b)w² with acquisition objective Amax.b the response predictions of ft over values B satisfyy
Σ (a)a) < bwi aEB...
Σ (.(a) S bw + F((a).
a.B..
aEB.
where Ba,t max Eoen
Proof. Let F, be the subset of F satisfying f E E(an)e (f(x) - 1)² S (t - 1-)== S n. By
definition Je E Ft. Substituting the definition A into Equation 1
Fe
E((o).
arg max max SEF, (B|=b aEB
Since J. E Fr,
ΣS(b
Σ f((a)z Σ T.(a) Σ (a). RE
max JEF.
=b
aEB
ac B.,
BE
Where B., max Ener Baeey,(o) (a) and B., 18) EBER Uo (a). Finally, for all
E A. we have T. (a) + 2 (a). This finalizes the proof. m
Since (a) + 2 y+ (a). for A. Lemma D.3 implies,
Σ (.) Σ (a) B,
< 2btw +
ΣΣ F((a) (a)
(13)
1
at B.
a
21

---

Published as a conference paper at ICLR 2023
We define the width of a subset f S F at action E A by,
r = sup J.f'E
If(a) - fa))).
And use the shorthand notation re(a) to denote r.F (a) where Fi= (ff (faa)
y)² S 7e.. Equation
13 implies,
Σ .EB...
va(a) Σ va) BE
S 2blw Σ Σ rr(a)
(14)
t=1
(=1 BEB.
In order to bound the contribution of the sum Ei= EBEB, re(a) we use a similar technique as in Russo & Van Roy (2013). First we prove generalization of Proposition 3 ofsso & Van Roy (2013) to the case of parallel feedback.
Proposition D.4. If (+r 2 Olt E N) is a nondecreasing sequence and F = {s E F (OWWED (f(a) y)² S 7t then,
I(m(a)>>> So nd
( + bdd b
aEB,
Where d = ddimg(F,e)
Proof. We will start by upper bounding the number of disjoint sequences in D;-1 that an action E Be can be e-dependent on when (a) >
rr (a) > e there exist f. E F, such that f(a) - f(a) e. By definition if B, is dependeent
on a sequence 5 _ [/=] Br = D, then f fll's > 22 (since otherwise |l - --ll < e² would imply
to be c inddepeendent of Dz). Thus if dependeen on K disjoint sequences S1, ... SK S D,,
then |f - f1l 2 Kr?. By the triangle inequality,
II fllo, S || J.llo. +II U.llD, S 2-
Thus follows that evK < and therefore
4
K
(15)
Next we prove a lower bound for K. order to do so we prove a slightly more general statement. Consider a batched sequence of arms {āe, Jee,),e Hejj)eetr) where for the sake of the argument āg,a is not necessarily meant to be dz We use the notation B, {ār, hej to denote the f-th batch in (er,))ve)))Me(1) and D, = =
Let E N and define K as the largest integer such that Kd + 6 rb. We show there is batch number L' < t and in-batch index i' such that ar is dedepndenn on subset of disjoint sequences of size at least 5 of set of K disjoint sequences 51, ... SR C Dz-1-
First let's start building the S, sequences by setting 5, =the i-th element in iic,stie ordered lexicographically. This will involve elements of up to batch ||
Since are going apply the same argument recursively in our proof, let's denote the 'current' batch index in the construction of .., 5 as f, this is, we set SI....,55 Sg C Dr. At the start of the argument غ [K/b].
there is an arm a B such that a dependeent on at least K /2 of the (3.) sequences, the result would follow. Otherwise, must be the case that for all E B841 there are at least i sequences in & which is inddepeendn...
22

---

Published as a conference paper at ICLR 2023
Let's consider bipartite graph with edge sets B&-1 and {S:) We draw an edge between E Bi+1 and S3 E {5 if i inddeependen on Sy. If for all a E B2+1 there are at least R sequences in {S:) fi-1 of size at least min( K g
?
R on which a is c- e-independent, Lemma D.5 implies the existence of a matching
b) between elements in B and the sequences in {5.)
The case min(
K
b) K can only occur when (--18 8
< b and therefore when 7b S 8bd + b.
8d
In case min( K b) b. If we reach f it must be the case that at least (r 1)b points could be accommodated into the K sequences. By definition of K it must be the case that each sub-sequence St satisfies |S.] 2 d. Since each element of subsequence S. is E e-independent of its predecesors, |S|| = d. this case we would conclude there an element in B, that is dependent on K and
therefore at least K = (r-1)b subsequences. If rb 87.d 2d b then K
47r- + 1. 22
= 2d + 2b + 8hd then there a batch index l' [r] such that there is an arm äge E By that is e dependent of at K least 3 + disjoint sequences contained in De.
Combining the results of the two last paragraphs we conclude that if rb 2
Let's apply the previous result to the sequence of o4,i for E [b] and I. E IR such that re re(().)) > An immediate consequence of the previous results is that if E 1-1 Enen, ne ((re(a) > c) 2 8ygd 2b 8bd there must exist an arm in B, such that it is c < dependent on at least 12- +1 disjoint sequences
5 + 2d +
of Dr. Nonetheless, Equation 15 implies this is impossible. Thus, Σi=1 E.EB, (rx(a) > E) S
8x.d + 2d + 2b + 8bd < &n. + 12bd. The result follows.
Finally, the RHS of equation 14 can be upper bounded using a modified version of Lemma 2 of Russo & Van Roy (2013) (which can be found in Appendix D.2] yielding,
Σ va(a)= a.
Σ (a) a
S - T
1 +0 (min (dim:(F, + v dimp(F, at (WTTT)
Where a2 = max (2. (nl falloo faa)). The quantity the left is known as regret. This result implies the regret bounded by a quantity that grows linearly with w, the amount of misspecification but otherwise only with the scale of dimg(F ar )6. Our result is not equivalent to splitting the datapoints in parts and adding b independent upper bounds. The resulting upper bound in the later case will have in term of the form
FF fe)) and C max (f(a)
O (b dFmg(F, ar)wT) whereas in our analysis this term does not depend on b. When = 0. the regret is upper bounded by O (dimg(F, (F, .d). For example, in the case of linear models, the O (llo((/c)). This shows that for example sequential OAE when b = achieves the lower bound of Lemma D.I uup to logarithmic factors. In the setting of linear models, the b dependence in the rate above is unimprovable by vanilla OAE without diversity aware sample selection. This is because an optimistic algorithm may choose to use all samples in each batch to explore explore a single unexplored one dimensional direction. Theoretical analysis for OAE DvD and OAE Seq is left for future work.
authors of Russo & Van Roy (2013) show dimg(F,ar))
Lemma D.5. Let be a bipartite graph with node set A U B such that |A| K and B b. ffr all nodes v E B it follows that N 2 then,
1. 11 2 2 b there exists perfect matching between the nodes in B and the ones in A.
2. If instead < b there exists a subset of K. nodes in A with a perfect matching to B.
Proof. The first item follows immediately from Hall's marriage theorem. Notice that in this case the neighboring set of any subset of nodes in B has a cardinality of at least K and therefore it is at least the size of B. The conditions of Hall's theorem are satisfied thus implying the existence of a perfect matching between the nodes in B to the nodes in A.
23

---

Published as a conference paper at ICLR 2023
In the second scenario, let's first prove there exists subset A' of A of size at least K such that every element in A' has at least & neighbors in B. We prove this condition by the way contradiction. There are at least 4K edges in the graph. Suppose there were at most vertices A with degree 2 greater or equal to 3. This value of must satisfy the inequality.
Lb+ (K- (
bk
Lb+
2
This is because the maximum number of edges vertex in A can have equals b. Thus, L> 4 1. b All nodes in L have degree at least 1 If we restrict ourselves to subset T. of T. of size K in this scenario K < 4. Hall's stable marriage theorem implies there is perfect matching between The result follows.
and since
g
Lemma 2 of Russo & Van Roy (2013) adapted notation of OAE.
Lemma D.6. If {yt 2 0it E N) is a nondecreasing sequence and Ft = {s E F s.l. E(aNEED (f(a) y)² S w then with probability 1 for all T N.
Σ
Σ
re(a)= S (dim, w (ydimg(F,or))))
dEB:
Where a4 max 1 inf f2lloo f2 E F, fe1) and C max (f(aa- s(a').
Proof.
The proof of lemma D.6 the proof template as that of Lemma 2 in Russo & Van Roy (013). We reproduce it here for completeness.
For ease of notation we use = dimp(F We first re-order the sequence
(r (1)())))) ;ri(a1,)," ... (T(())))) rh 5... Stre We have,
(1) 1+ Σ Σ r4 Σ 1(r,, aT)r, + + 1(r, > aT) aT)ri
Tb
Σ Σ .E
(r(a)
1(r,
at)r
5=1
Where inequality (i) holds by definition of ar noting that
Σ
1(r, S ST)r = 0, if or = in inf - S21lxx : $2).
1=1
and
Tb Σ
uri S aT)ri, S1, if oT Tb 1=1
Proposition D.4 (since d dimm(FFe) for all 2 aT) implies that for all iz with rú, or, bound j as
'rd
js
Σ 1(re(a) 50
+ bd
ri
24

---

Published as a conference paper at ICLR 2023
Algorithm 4 Noisy Batch Selection Principle (OAE)
Input Action set A C I& num batches N, batch size b Initialize Observed points and labels dataset D1 for t == =. 1...... do
If = 1 then:
Sample uniformly a size b batch B₁ ~ Ui
Else:
Solve for ft and compute B, E arg maXBCu. [8|=b ((e, B).
Observe batch rewards Y, (v)(a) for a E B:}
Update D(+1 D, U {(B,, Y,)) and U,+1 U, B,
So there a constant 0 such that ri, So (V O (bd) since the radii ri all of constant size. We conclude that,
vrd (--bbd++
For all j ebd notice that Σj=1 Tip
rrd ebd)+
Σ T4
0
bd Σ
(j
j=ebd+1
Tb-oba
0 bd + Vrrd
Vidk
1=1
=0 (d + vyrdTb).
Substituting "T w2Tb we conclude,
Σ ri =0 @bddd
Thus finalizing the result.
Combining the result of Lemma [.6 Equation
14 finalizes the proof Theorem 4.1
D.3 NOISY RESPONSES
In this section we describe how our results imply improved bounds for the setting with noisy responses. In this case assume that Vt,i y, + Er, where Ét, is conditionally zero mean.
We consider the following optimistic least squares algorithm,
E EXPERIMENTS
We demonstrate the effectiveness of our OAE algorithm in several problem settings across public and synthetic datasets. We evaluate the algorithmic implementations described in Section 4.1 by setting the acquisition function to Aave (f,l) and the batch selection rule as in Equation 2 for the vanilla OAF methods and as Equations 6 for OAF's diversity inducing versions OAE DvD and OAE Seq respectively. All neural network architectures use ReLU activations. All ensemble methods use an ensemble size of M = 10 and xavier parameter initialization.
Small vs Large Batch Regimes. Oftentimes the large batch small number of iterations regime
the most interesting scenario from practical perspective Hanna Doench (020). In scientific settings like pooled genetic perturbations, each experiment may take long time (many weeks or months) to conclude, but it is possible to conduct a batch of experiments parallel together. We study this regime in Section 5
25

---

Published as a conference paper at ICLR 2023
Figure 7: (top row) Synthetic dimensional datasets (bottom) Evolution of MeanOpt. in the MultiValley ValleyOneDimHHole dataset using Areg = 0.001. From left to right: Iterations 5, 13, 25, 45.
E.1 VANILLA OAE
We test MeanOpt, HingePNorm, MaxOpt, Ensemble and EnsembleNoiseY performance (see Section T for detailed description of each of these algorithms) over different values of the regularization parameter Areg. including the 'greedy' choice of Aveg = O, henceforth referred to as Greedy. We compare these algorithms to the baseline method that selects points Br by selecting a uniformly random batch of size from the set U4, henceforth referred to as RandomBatch and against each other.
We conduct experiments on three kind of datasets. First in Section we capture the behavior of OAE in a of synthetic one dimensional datasets specifically designed to showcase different landscapes for y/, ranging from uni-modal to multi-modal with missing values. In Section E. 1.2 we conduct similar experiments
public datasets from the UCI database Dua & Graff (2017) In both sections E.I.I and E.1.2 all of our experiments have batch size of 3, time horizon of N = 150 and over two types of network architectures. In Section 3 we consider the setting in which we have observed the effect of knockouts in one biological context (i.e., cell line) and would like to use it to plan a series of knockout experiments in another. We test OAE in this context by showing the effectiveness of the Mcan HingePNore Norm, MaxOpt, Ensemble and EnsembleNoisey methods successfully leveraging the learned features from a source cell line in the optimization particular cellular proliferation phenotype for several target cell lines.
All of our vanilla OAF methods show that better expressivity of the underlying model class F allows for better performance (as measured by the number of trials it requires to find response within a particular response quantile from the optimum). Low capacity (in our experiments ReLU neural networks with two layers of sizes of 10 and 5) models have harder time competing against Random Batch than larger ones (ReLU neural networks with two layers sizes 100 and 10). We also present results for linear and 'very high' capacity models (two layer of sizes 300 and 100).
E.1.1 SYNTHETIC ONE DIMENSIONAL DATASETS
Figure 7 shows different one dimensional synthetic datasets that used validate our methods. The leftmost, the VallliilValleeOneeDiii
dataset consists of 1000 arms uniformly sampled from the interval [-10, 10). The responses y are unimodal. The learner's goal to find the arm with r-coordinate value equals to 3 as it is the one achieving the largest response. We use the dataset OneHiilValleyynee DimmmHoole to for OAE's ability find the maximum when the surrounding points are not present in the dataset.
The remaining two datasets MultiValley OnneeeOollnnnn and MultiValleyOnell problem of multimodal optimization in mind. Each of these datasets have 4 local maxima. We use MuutiiaallyyOneDii to test the OAE's ability to avoid getting stuck in local optima. The second dataset mimics the construction of the OneHiill ValeiiiVlillyyOeiiiittte OneDimHole dataset and on top of testing the algorithm's 's ability to escape local optima, it also is meant to test what happens when the global optimum's 's neighborhood isn't present in the dataset. Since one of the algorithms test is the greedy algorithm (corresponding to = 0), the 'Hole' datasets are meant to present a challenging situation for this class of algorithms.
are built with the
26

---

Published as a conference paper at ICLR 2023
173
115
113
Lumile kult Mourte
Let Morlar
1.0
115
1:0
Liibicar Monddl
531 FAROO
154 1M
VA
Figure 8: NN 10-5, T-quantile batch convergence (left) and corresponding rewards over batches (right) on the OneHiilValleyOnee (easier) and MuliiValleyOneDim (harder), OneHillVVlleyOnne imHole and Multi CalleyOneDimienn synthetic datasets show how the OAE algorithm achieve higher reward faster than BaandomBatchh or Greedy. The neural network architecture has two hidden layers of sizes 10 and 5. www.isabepee.20
$2.40
Ca
325
1.0
1.0
Mandat
Figure 9: NN 100-10. r-quantile batch convergence (left) and corresponding rewards over batches (right) on the suite of synthetic datasets when the neural network architecture has two hidden layers of sizes 100 and 10.
We test several neural network architectures across all experiments. In all these cases we use ReLU activation functions trained for 5000 steps via the Adam optimizer using batches of size 10. In our tests we use a batch size B 3, a number of batches N 150 and repeat each experiment a total of 25 times, reporting average results with standard error bars at each time step.
First we compare the MeanOpt version of OAE with a simple RandomBatch strategy that selects a random batch of size B from the dataset points that have not been queried yet and Greedy algorithm corresponding to Mean with Areg = 0. Figures 8 9 and 10 show representative results for McanOpt with (Areg = 0.001, 0.01, 0.1) accross three different neural network architectures, NN 10-5, NN 100-10, and NN 300-100. In all cases, the high optimism versions of MeanOpt perform substantially better than RandomBatch. In both multimodal datasets Greedy underperforms with respect to the versions of McanOpt with Areg > O. This points to the usefulness of optimism when facing multimodal optimization landscapes. We also note that for example NN 10-5 is the best performing architecture for MeanOpt with Areg = 0.001 despite the regression loss of fitting the MultiValles OneDim's 's responses with a NN 10-5 architecture not reaching zero (see Figure [3). This indicates the function class F need not contain y, for MeanOpt to achieve good performance.
Oratt Bie KyCroD Qardin
Oriil Wwrikyyydeerritt Duantiic
MuttfcheCCedl Opend
MulF/ille Oww.ealyyOOdddeeee wnderiiea Dus
X50 po Awnial
0.4
04
05
Casd
Figure 10: NN 300-100. 7-quantile batch convergence on the suite of synthetic datasets when the network architecture has two hidden layers of sizes 300 and 100.
27

---

Published as a conference paper at ICLR 2023
Moreover, it also indicates the use of higher capacity models, despite being able to achieve better regression fit may not perform better than lower capacity ones in the task of finding a good performing arm. We leave the task of designing smart strategies to select the optimal network architecture for future work. It suffices to note all of the architectures used in our experimental evaluation performed better than more naive strategies such as HandomBatehl
Second, in Figures 11 and 12 we evaluate McanOpt vs ensemble implementations of OAE across the two neural network architectures NN 10-5 and NN 100-10. We observe that Ensemble performs competitively with all other methods in the one dimensional datasets and outperforms all in the aneeilllalleyyOneeeineee
In the multi dimensional datasets, MeanOpt performs better than Ensemble, EnsembleNoisey and Greedy. In this case the most optimistic version of Mean (Areg = .1) is the best performing of all. This may indicate that in multi modal environments the optimism injected by the random initialization of the ensemble models in Ensemble or the reward noise in EnsembleNoisey do not induce an exploration strategy as effective as the explicit optimistic fit of MeanOpt. In unimodal datasets, the opposite is true, MeanOpt with large regularizer (Areg = 0.1) underperforms Ensemble, EnsembleNoise Y and Greedy. In Appendix G.I the reader may find similar results for MaxOpt and HingeOpt. Similar results hold in that case.
Queetiee
Queel
Figure 11: NN 10-5. 7-quantile batch convergence of MeanOptimism vs EnsembleOptimism vs YnsembleNoise
Figure 12: NN 100-10. q-qunttlle batch convergence of MeanOptimmsmm vs EnsembleOptimism vs EnsembleNoiseY.
Onell CeelliNalteOO bablrrr Recustio
Ovell /twe://eeeeeiiioooo Sypuster
Figure 13: Training set regression fit curves evolution over training for the suite of synthetic datasets. Each training batch contains 10 datapoints.
28

---

Published as a conference paper at ICLR 2023
SESETAA SEpEengge CUNTRR
Figure 15: NN 10-5. ququnttlle batch convergence on the Adult and BikeSharingDay datasets with regression-fitted response values.
E.1.2 PUBLIC SUPERVISED LEARNING DATASETS
We test our methods on public binary classification (Adult, Bank) and regression (BikeSharingDay, BikeSharingHour, BlogFeedback) datasets from the UCI repository (Dual & Grrfft (017). In our implemen- tation, the versions of the UCI datasets we use have the following characteristics. Due to our internal data processing that splits the data into train, test and validation sets the number of datapoints we consider may be different from the size of their public versions. Our code converts the datasets categorical attributes into numerical ones using one hot encodings. That explains the discrepancy between the number of attributes listed in the public description of these datasets and ours (see https://archive ics The BikeSharingDay dataset consists of 658 datapoints each with 13 attributes. The BikesharingHour dataset con- sists of 15642 datapoints each with 13 attributes. The BlogFeedback dataset consists of 52396 datapoints each with 280 attributes. The Adult dataset consists of 32561 datapoints each with 119 attributes. The Bank dataset (Moro et al. 2014) consists of 32950 datapoints each with 60 attributes. To evaluate our algorithm we assume the response (regression target or binary classification label) values are noiseless. We consider each observation i in dataset to represent discrete action, each of which has features a, and reward y, (a;) from the response. In all of our experiments we use batch size of 3 and evaluate over 25 independent runs each with 150 batches.
DaaGhantnggay Quamile
BeadnaringSay Quantivs
Oward lrs
Blkesttringhoou Quertille
SlaeShor Hogioou Quarttlle
Ouart No (h)
BlocFredterkk Quantille
Brggenecaatk Quentiles
123
10
5.
Ooard
Duansils
Figure 14: NN 100-10. q-qunntlle batch convergence (left) BikeSharingDay BikeSharingHour and BlogFeedback datasets with original response values.
We first use all 5 public datasets to test OAE in the setting when the true function class F is known (in this case, a neural network) is known contain the function OAE learns over the course of the batches. We train a neural network under simple mean squared error regression fit to the binary responses (for the binary classification datasets) or real-valued responses (for the regression datasets). This regression neural network consists of a neural network with two hidden layers. In Figure [5] we present results where the neural network layers have sizes 10 and 5 and the responses are fit to the Adult classification dataset and the regression dataset BikeSharingDay, In Appendix G.2 and Figure 32 we present results where we fit two layer neural network model of dimensions 100 and 10 to the responses of the Bank classification dataset and the BikeSharingHour regression dataset. In each case we train the regression fitted responses the provided datasets using 5, 000 batch gradient
29

---

Published as a conference paper at ICLR 2023
BieeShoinggaa Regrassion
Biessioningguur Regression
BlogFoesback Reg rnsiionionn
5M 22-5
25-3
5M 28-2
175-10
Figure 16: Training set regression fit curves evolution over training for the UCI datasets. Each training batch contains 10 datapoints.
WochhrrnnCCa Quarttees
Bichhhaing Quantlics
BlogFoodback Quontlees
170
Serelanch
100
a./0 Muar
300
2/00 Muar
Roa Muan
Seggied Catchen
60
Hear
60
60
60
Ouantiee
Quantiliu
Quanties
Figure 17: Linear. T-quantile batch convergence on the BikeSharingDay, BikeSharingHour and BlogFeedback datasets.
steps (with batch size of 10). During test time we use the real-valued response predicted by our regression model as the reward for the corresponding action. This ensures the dataset's true reward response model has the same architecture as the reward model used by OAE
We use the same experimental parameters and comparison algorithms as in the synthetic dataset experi- ments. Figure[[]sshww shows the results on the binary classification Adult and regression Bikeehariingar, datasets using these fitted responses. We observe the MeanOpt. algorithm handily outperforms HandomBatoh on both datasets. Appendix G.2 shows similar results for BikeSharingHour and Bank. We also compare the performance of MeanOpt, Ensemble and EnsembleNoisey Y in the Adult and BikeSharingDay datasets. In both cases, ensemble methods achieved better performance than MeanOpt. It remains an exciting open question to verify whether these observations translates into a general advantage for ensemble methods in the case when y, E F.
Given OAE's strong performance when the true and learned reward functions are members of the same function class F, we next explore the performance when they not necessarily in the same class by revising the problem on the regression datasets to use their original, real-world responses. Figure 14 shows results for the BikeSharingDay, BikeSharingHour and Beedback datasets. In this case Ensemble outperforms both KandomBatch B r-quantile convergence time. In all of these plots we observe that high optimism approaches underperform compared with low optimism ones. Ensemble and Greedy (the degenerate version Areg 0 of McanOpt) achieve the best performance across all three datasets. We observe the same phenomenon take place even when F is a class of linear functions (see figure [8). Just as we observed in the case of the suite of synthetic datasets, setting to be a class of linear models MeanOpt still achieves substantial performance gains w.r.t RandomBated (see figure 17 despite its regression fit loss never reaching absolute zero (see figure [6). In Appendix G.3, figure 33 we compare the performance of MaxOpt and HingeOpt with RandomBatch when F is class of neural networks with hidden layers of sizes 100 and 10. We observe the performance of MaxOpt, although beats Random Batch suboptimal in comparison with McanOpt. In contrast HingeOpt has similar performance McanOpt.
E.2 EXPERIMENTS DIVERSITY SEEKING OBJECTIVES
In this section we explore how diversity inducing objectives can sometimes result in better performing variants of OAE. We implement and test DetD, SeqB, Ensemble SeqB and
30

---

Published as a conference paper at ICLR 2023
Biy Ouartles
Hiar Quantlies
Blogfoodback Quanti
10
Croedty
Seguiec Battae
OuAntRos 1911
Quantiiis 1911
Quanties
Figure 18: Linear. quaantile batch convergence on the BikeSSaringDay, Bike and BlogFeedback datasets.
312
05
6.2
0.3
Figure 20: NN qu-annl batch convergence performance of DetD vs RandomBatch in the suite of synthetic datasets.
NoiseY. In all the experiments we have conducted we kept the batch size b and the number of batches N for each dataset equal to the settings used in Section E. The neural network architectures are the same we have considered before, two layer networks with ReLU activations.
Ensemble SeqB
E.2.1 OAE - DvD
We implemented and tested the DetD algorithm described in Section C.O.1 In our experiments set Adiv 1 and set Ja to be the result of solving the MeanOpt. objective (see problem 3 for different values of Aveg- We set K. to satisfy.
K K(a1, a2) =exp (-1 a1 |ail]
02 |a2ll
Figure 19: NN 100-10. T-quantile batch convergence performance of DetD vs RandomBatch in the BikeSharingDay dataset.
We see that across the suite of synthetic datasets and ar- chitectures (NN 10-5 and NN 100-10) the performance of MeanOpt degrades when diversity is enforced (see fig- ures ures[20 and 21 and compare with figures 8 and 9.. A sim- ilar phenomenon is observed in the suite of UCT datasets (see figure 19 for DetD results on the BikeSharing dataset
and figure 14 for comparison).
In contrast, we note that DetD beats the performance of RandomBatch in the A373, MCF7 and HA1E datasets and over the two neural architectures NN 10-5 and NN 100-10. Nonetheless, the DetD is not able to beat RandomBate objective that relies only on the geometry of the arm space and does not take into account the response values may be beneficial when y. & F but could lead to deterioration in performance when y. E F. The algorithm designer should be careful when balancing diversity objectives and purely optimism driven exploration strategies, since the optimal combination depends the nature of the dataset. It remains an interesting avenue for future research to design strategies that diagnose in advance the appropriate diversity/optimiss balance for OAE DvD.
in the VCAP dataset. These results indicate that a diversity
31

---

Published as a conference paper at ICLR 2023
Dnc Vallyrr SOwEmi Conddl
Figure 21: NN 100-10. quanttile batch convergence performance of DetD vs RandomBatch in the suite of synthetic datasets.
A375 Cuardine
Oui voheo
YOA Carrd
115
Figure 22: NN 10-5. T-quantile batch convergence performance of DetD vs RandomBatch in the suite of genetic perturbation datasets.
E.2.2 OAE 1 Seq
In this section we present our experimental evaluation of the three tractable implementations of OAE - Seq we described in Section C.0.2 In our experiments we set the pptimism-pessimisn weighting parameter a 1/2 and the acquisition function to Aavz, We are primarily concerned with answering whether 'augmenting' the MeanOpt, Ensemble and EnsembleNoisee methods with a sequential in batch selection mechanism leads to an improved performance for OAE. We answer this question in the affirmative. In our experimental results we show that across datasets and neural network architectures adding in batch sequential optimism either improves or leads to no substantial degradation in the number of batches OAE requires to arrive at good arm.
Figure 24: NN 100-10.
T-qunntlee batch convergence performance of (left) McanOpt
vs SeqB, (center) Ensemble vs Ensemble - SeqB and (right) Ensemble - Noise vs Ensemble SeqB- NoiseY on the suite of synthetic datasets.
103
02
65
25
Figure 23: NN 100-10. quaantile batch convergence performance of Det. RandomBaich in the suite of genetic perturbation datasets.
32

---

Published as a conference paper at ICLR 2023
ChantivalleyOnoOmm
OnsHiinalayCnaammm Quantlics
Graec
502
Essee on
Sxsen Cerd
dockk tobe!
cestionne and
60-
60-
Quantille Tha
Quartine (96)
Quantibe (56)
10
Locse on
Decuieed Daroree
50
Quantiles Ill
Quantiie (%)
Quantibe (%)
NuttvalicyCneekm
MNJDVallcyOnaDmm
M4LEVallyOOnaDmm Quantilez
Groedy
on Dosentie Coundde-eechh Sobel
Dxsen DosmniieGed Cerd
Levian DN WC-4
Macuired Daltres
Lesscoons sed
10
Quantille Tha
Quantille (5))
Quentile (50)
Crieddy
Cooetible
boleet
Dequiied faRcree
Decuied
-0
20
Quantiee PN1
Quentilee (1))
Quentile (1s)
Figure 26: NN 10-5. quaantlee batch convergence performance of (left) MeanOpt Beq (center) Ensemble vs Ensemble SeqB and (right) Ensemble Noise vs Ensemble SeqB NoiseY on the suite synthetic datasets.
02
02
Figure 25: NN 100-10. r-quantile batch convergence performance of MeanOpt SeqB the gene perturbation datasets.
More precisely in figures 26 and 24 we show that in the set of synthetic datasets adding a sequential in batch selection rule improves performance of OAE across the board for (almost) all datasets and all methods McanOpt, Ensemble and EnsembleNoisey and two neural architectures NN 10-5 and NN 100-10. Similar gains are observed when incorporating sequential batch selection rule to OAE in the BikeSharingDay and BikeSharinggHour datasets when F' corresponds to the class NN 100-10 (see figure 27). Finally, we observe the performance OAE Seq either did not degrade or slightly improved that of McanOpt, Ensemble and EnsembleNoise" in the BlogFeedback and the genetic perturbation datasets (see figures 34 25 and 38). We conclude that incorporating a sequential batch decision rule, although it may be computationally expensive, is desirable strategy adopt.
33

---

Published as a conference paper at ICLR 2023
BluSharingDay
BiieStaringbay
hiresharin
Graed
baser on
Exurdi Cord
Cerrrreeeecch Sobel
20
Lesoconnes and
Quattile 1h61
Quartine (5))
Quartibe (56)
301
Soleet
Quanties 1s1
Quantiie (h)
Quenties (1)
7-quantile batch convergence performance of (left) MeanOpt VS SeqB, (center) Ensemble vs Ensemble - SeqB and (right) Ensemble NoiseY vs Ensemble SeqB NoiseY the BikeSharingDay and BikeSharingHHour datasets.
Figure 27:
NN 100-10.
interesting to note that in contrast with DetD the diversity induced by SeqB did not alleviate the subpar performance of MeanOpt in the set of genetic perturbation datasets. This can be explained by SeqB induces query diversity by fitting fake responses and therefore may be limited by the expressiveness F. The DetD instead injects diversity by using the geometry of the arm space and may bypass the limitations of exploration strategies induced by F. Unfortunately DetD may result in suboptimal performance when y/ F.
F CELLULAR PROLIFERATION PHENOTYPE
Let be the list of genes present in CMAP also associated with proliferation phenotype according to the Seurat cell cycle signature, and let Fig9 represent the level 5 gene expression of perturbation a; for gene g G. We define the proliferation reward for perturbation a; as the average expression of the genes in G.
ppolif (a.)
=
Ti.
G
gEg
For convenience, G [AURKB, BIRC5, CCNB2, CCNE2, CDC20, CDC45, CDK1, CENPE GMNN, KIF2C, LBR, NUSAPI, PSRCI, RFC2, RPA2, SMC4, STMNI, TOP2A, UBE2C, UBR7, USP1).
34

---

Published as a conference paper at ICLR 2023
G FURTHER EXPERIMENTS
G.1 SYNTHETIC DATASETS
Oheylii-ilee Quanbles
Onelli Valeyynneiiiiiice Quantles
120
100
Dready
Macall
Angrnd Bateban
40-
lest
Quaent
Multt-Wiileyrrettlim Quantiles
Multh Vis Deytreemmmtiii Quantilles
160
Greeds
Greedy
Hedded Haxdep
Meddet
Batchan
Hexdet
Quentiiee
Quantiie
Figure 28: datasets.
NN 10-5. MaxOptimism comparison RandomBatch over the suite of synthetic
Wewetilllllleeeeeiiinn Quantiles
OreHi Saailly@r-Diiiiiii Quantiles
190
100
Lnneaao shaical
Recuiin Banches
dideit Mtadta
Recuere Bonches
daduii bractal
30
Do Du.nnfee Pitt
Quant les 196
MultViallyOrreae Quartiles
MultiValeyC-n Det.:a/leeyCrrmiiieieee
Bondorlaatis
100
Hender lata
50
setiica 201 Mextige
Liaitia 2mn Mexiig
Recatree sardhie
Mardly
Eandaaa Mardge
Quaethee 590
Quaethee (4)
Figure 29: NN 100-10. MaxOptimism comparison vs RandomBatch over the suite of synthetic datasets.
35

---

Published as a conference paper at ICLR 2023
Indiedst
120
undeuudoon revedde
Repured Batches
Poosiees batches
40
02
2.8
0.2
Di Ouonnlles 1911
Quaend los 196)
Rumberticion
Furder Sitl
Lynteon rice 300 moadet
Landdadd 300 Hagede
Bocutee Balches
macuthel
0.5 Quretiies
Oupetiies
Figure 30: datasets.
NN 10-5. HingePNorm comparison vs RandomBalch over the suite of synthetic
Crile Quantiles
SeaallyyrrDDiiieee Quantiles
130
100
Recuire Bonches
diduii be
30
Do Duaand
Quant les (96
MultiVallyyrrree wiih Quartiles
Sondorllatis
100
Fender lata
Recadred Barches
Quanthee 590
Quaethee (4)
Figure 31: datasets.
NN 100-10. HingePNorm comparison vs RandomBatch over the suite of synthetic
36

---

Published as a conference paper at ICLR 2023
G.2
REGRESSION FITTED DATASETS
Biveshernnglsorreppssssi Quanties
www.hheeinggoouuuogggoooooo Rewerds
Recsting Mec Bocworth
Tandendetch
crcedy
ambde
0.8
0.5
0.2
125
150
BarkRegression Quantliis
BenkRogression Rewerds
Gebelity
mosuting Mou Moronts
Rundor
deedyy
Lamida- 001
Limitb 0.
0.5
25
90
25
100
125
350
Figure 32: NN 100-10. BikeSharingHour and Bank Regression Fitted Datasets. Our algorithms
perform substantially better than HandomBatch. Optimistic approaches are better than Greedy in the Bank dataset.
G.3 UCI PUBLIC DATASETS
BikeSharingDay Quantiles
Bikesharingaay Quantiles
Aeound BITchee
aanddaacii mavdee
Acoired BXTChe
80
Linolaode rapecok
0.8
6.5
0.2
0.2
BlkkShheinggoou Quantiles
tikgoor Quantiees
1.0
120
Sequred Batchee
aanodaoii mavoge
Seq/red Bntcee
aanossooe rnpecot
6.5
0.2
3:9
0.2
BlogFeedback Quantiles
BlogFoedback Quentiles
320
120
Labilty
100
Linoree 3i Mustoo
1.0
Lumboa 31 Heggsde
80
0.5
0.5
Figure 33:
NN 100-10. MaxOptimism and HingePNormOOtinnin comparison vs RandomBate in the BikeSharingDay, BikeSharingHour and BlogFeedback datasets.
37

---

Published as a conference paper at ICLR 2023
Blogfeedback
Slogfecbbckk Quanblez Downbee-Sdd
Creec Meliii siaario cut
Downtle Seat-oae
Brc Reclleed Batevs
Recuited RatcIee
Quenties 1M
Quentiee (N1)
Quenties (N6)
Figure 34:
NN 100-10. T-quantile batch convergence performance of (left) McanOpt
VS B, (center) Ensemble vs Ensemble - SeqB and (right) Ensemble Noise vs
Ensemble SeqB NoiseY the BlogFeedback dataset.
G.4 TRANSFER LEARNING BIOLOGICAL DATASETS
.ancduc Martat
Jinddoou01 liguite Lnndeco rengedge
Quand Eh1
Quaen les (11
Quancless
Laniddud Masdae
Lambdooou0 lineudes Lmbeeod Hengede:
Landdeed Murioe
Quant hes 1%1
Quaen les (51
Quantiles
Nencondaact
Leneaksson rengens uaooeeci Hingedg:
Zi hes 1%1
Quant les (%1
BondorBaitc
Lecrice mexoie
6-
solo reggaso Lemoste engeggg
Londoee Hardge
Sargired
0.5 Quantive do
Quentree do0
Figure 35: NN 10-5. MaxOptimism and Hinge NormOptimism comparison vs Random Batch.
38

---

Published as a conference paper at ICLR 2023
Sestin
Len aeredtud on Muntae Mtarte
2.8
0.2
Quard 1961
Nomain dlacc
Mtarta
0.2
0.2
Di anbilees 1911
Quant 1961
Mtarta
0.2
2.8
0.2
Di anblles 1f11
Quant 196)
201 Hexitee
Lonntiia 200 Haga masuetall
Pecutrec Bandie
Marche
Decudee: faedeer
0.5
0.5 Quridies
Ousitties
Figure 36:
NN 100-10.
MaxOptimism
and TinngeNoormOpimissn comparison vs
RancomBatch..
39

---

Published as a conference paper at ICLR 2023
VCAP Duartties
VC&P Quantees
Leverige
JPMBBe Merdee
Ouartiles
Ouart
ADP5 Quantille
A375 Quantless
05
4.2
Hesache
05
Quantilin
Quartilles
Creees
Quarr
Figure 37: NN 10-5. T-quantile batch convergence of MeanOpt (left), Ensemble and EnsembleNoiseY (right) on genetic perturbation datasets.
40

---

Published as a conference paper at ICLR 2023
Creece
and
Quantiees
Quantiis 196)
Cuantilee 196)
HATF Quaetiles
HALE Quantiee
HA1E Quantiee
14.
Groecc
Esser devii an
10
02 Quantille
Quantile (96)
Cuantibe
MCFT Quantliee
MCFF Ouantiees
MMCF2 Ouantles
Lomie 0200 Srals
Quantiies
Quantile 196)
Cuintilles
QuanPiles
Graeds
Creembe
Cheembi Aodael
Lom D00a-M0 Harnde
1.55
AUGEE loall
1.00
Quentibee
Quentiie
Quentiiee
Figure 38: NN 10-5. quantille batch convergence performance of (left) McanOpt vs SeqB, (center) Ensemble vs Ensemble- SeqB and (right) Ensemble Noise vs Ensemble SeqB NoiseY on genetic perturbation datasets.
41


Reviews:
[{"review_id": "rysX0_0yp0i", "reviewer": "Reviewer_sSRW", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Motivated by the genetic perturbations problem in biology, the authors reformulate this problem as a batched regret minimization problem with a large action space.  Specifically, they assume the feedback is noiseless and prior-known a potential function class that outputs the score of a given action (a perturbation) but this function class can be misspecified. \n\nBased on this setting, they propose the Optimistic Arm Elimination (OAE) framework, which can be adapted to various optimistic predictors. Under this framework, they give a theoretical regret guarantee in terms of the Eluder dimension of the function, the misspecification level, and the batch size. Then they test their framework on various experiments by choosing the regression model as deep neural net and get SOTA in 3 of 4 datasets.", "summary_of_the_review": "While I believe it is practical and meaningful based on those experimental results. It is a bit unclear to me whether its novelty on theoretical contributions or algorithm design contributions. I am not experienced in doing experiments so it is hard to judge the overall contributions.\n\nAlso, given this is an ml for a science paper. I am willing to raise my score if people familiar with this area endorse it.", "strength_and_weaknesses": "Strong: This is a well-motivated real-world problem. The author gives a meaningful formulation of this problem and shows promising experimental results.\n\nWeaknesses:\n1\\ The proposed framework in the main paper, although high-level and flexible, seems just a very standard optimism-based framework that incorporates various existing heuristic methods  (Section 4.1, 4.2)\n\n2\\ Under the noiseless assumption, the proposed predictor in Eqn.(1) and the corresponding Theorem 4.1 seems not surprising to me -- If there is no misspecification then this is just a standard passive learning problem. If there is some misspecification, then it is linear in misspecification. Also this predictor is not parameter-free because you need to choose tolerance $\\gamma$ based on misspecifcation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ehHyR7i1Lp", "reviewer": "Reviewer_bZbX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors define new methods to select batches of perturbations of cells that are most likely to inform and optimize on a phenotypic metric of interest.", "summary_of_the_review": "I think that the problem the authors are trying to solve is very interesting, and I applaud them on their work. However, I found that this paper lacked focus and refinement–important points should fit into the main text. Moreover, I found there to be a number of arbitrary design decisions with VAEs and uncertainty estimate models that detracted from the core contributions stated by the author.", "strength_and_weaknesses": "Very interesting problem, and not a lot of others in this space–great to define this problem concretely!\n\nA wide array of related work is outlined and organized, not only with section headings, but also citations.\n\nMy difficulty with theory-heavy biology paper lies in statements like this: “the learner is required to query a batch of ..arms…and observe noiseless responses…In the setting of neural perturbation experiments the responses are the average of many expression values across a population of cells, and thus it is safe to assume the observed response is almost noiseless.” As someone who has analyzed dozens of these datasets, this is most certainly not true. In real world “shRNA and CRISPR” experiments, there is always variability, minimally in knock-down or edit level, phenotypic response, experimental design, etc. Though a population of cells is sampled, there will always be variability. Since you have datasets, can you characterize the experimental noise of a given knockout? If you don’t have this data, you cannot make this assumption.\n\nTo what extent can the uncertainty estimates for your model be used? How were they calibrated, and how much poor calibration can you tolerate? For proper uncertainty estimates, why not Gaussian Processes as a baseline, or maybe even Bayesian Neural Networks? Why are only Ensemble methods described in Section 4.1.2 as the only method to create uncertainty, but then Bayesian Neural Networks are used in Section 5.0.1? Why were those not described in Section 4?\n\nIn Figure 1, and that associated analysis, to what extent do we care about cross-cell-line variability? I think showing this generalization is useful. However, how much do we generalize across perturbations?\n\nThe use of a VAE to represent sequences is concerning to me. Why don’t just input raw data into a neural network? By using the VAE representations, you are implicity assuming you can reasonably represent all variability in expression. If a series of genes, or gene networks, were removed during training of the VAE, and projected with a learned model, how are they represented? If these KOs are incorporated into both the VAE and neural net training, can you still generalize to those predictions?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QldpefoAmN", "reviewer": "Reviewer_s1ZP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper introduces a novel bandit / active learning method tailored to the problem of single-gene interventions in cell biology experiments, where we can have batches of parallel interventions and only a few rounds of active learning are feasible. The new bandit method (Optimistic Arm Elimination or OAE) is based on either an existing uncertainty estimator or a novel optimization objective for the reward predictor that trades-off between fitting the data and maximizing the predictions. A diversity regularizer can be added to regularize each batch to be somewhat diverse. A large set of experiments to compare the different variants under study is performed, along with one comparative experiment (on 4 datasets) on the GeneDisco benchmark (using the public implementation of GeneDisco).\n", "summary_of_the_review": "This paper is clear and describes a strong, novel and well-thought out work on bandit methods in cases where very few rounds of batched interventions are possible. It could be stronger with more points of comparison, i.e., against more of the existing state-of-the-art methods.\n\n", "strength_and_weaknesses": "The paper is generally well-written (a few minor English errors should be easy to fix) and clear. The proposed method appears novel (although inspired by much previous work, and an extensive set of relevant papers are cited) and the results appear promising. The paper also includes a bandit theoretical results bounding the regret.\n\nIt is clear that the authors have thought carefully about many issues arising in the context of their targeted application (such as diversity within each batch, how to evaluate performance).\n\nThe main weakness is that there should have been more comparisons against existing methods rather than against a single strawman (the GeneDisco public implementation). \n\nThe paper focuses on the single-intervention case and the algorithms would not scale to compositions of interventions (e.g. multi-gene interventions) because the different actions must be enumerated and scored separately. See the recent work on GFlowNets (NeurIPS 2021, ICML 2022) as a possible way to train a policy to generate actions in a way that favors a diversity of candidates in each batch, as an alternative to explicit screening of all the possible actions.\n\nI am concerned with the use of the inf-norm in 4.3 because a hugely diverse set of \\tilde{y}* could minimize it.\n\nI would like to see something added to explain how to select lambda_reg (which controls the trade-off between fitting the data and maximizing predictions, i.e., the weight uncertainty in the acquisition function) and how to do it without cheating (e.g. to get the results in Fig. 5), i.e., without using the downstream results of the active learning iterations.\n\nMore references should be added regarding the related work in uncertainty estimation without an explicit Gaussian posterior (such as available with GPs), i.e., with neural networks. See e.g. DEUP (Lahlou et al 2021).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "MouPVJBH41", "reviewer": "Reviewer_UfWC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors investigate the problem of predicting how to perturb cells via genetic manipulations in order to shape their phenotype in a desired way. Their approach to this problem is to rely on a novel form of batch query bandit optimization, their Optimistic Arm Elimination (OAE) principle. They use their OAE to show that they can often plan effective experiments in fewer tries than baseline methods.\n", "summary_of_the_review": "The problem setting is incredibly interesting and exciting but I thought the paper was difficult to read and the results not all that compelling. I am also worried that the key assumption of no-noise is fundamentally flawed for biological data, so I'm curious what the authors and other reviewers think about that. I think there's great potential here, however, as it stands, I am leaning towards reject but still open to changing my review during the discussion period. ", "strength_and_weaknesses": "\n\nSummary\nThe authors investigate the problem of predicting how to perturb cells via genetic manipulations in order to shape their phenotype in a desired way. Their approach to this problem is to rely on a novel form of batch query bandit optimization, their Optimistic Arm Elimination (OAE) principle. They use their OAE to show that they can often plan effective experiments in fewer tries than baseline methods.\n\n\nStrengths\n- The problem setting is extremely interesting, and I believe holds huge potential for drug discovery. Also, this is a problem that I believe has been under studied because it is so difficult to model.\n- The authors test their method on a variety of datasets.\n\nWeaknesses\n- I'm not sure what the purpose of Figure 1 is. It's showing regression loss of different models trained on a few cell lines. The model hasn't converged. There's no test performance. What should we take from this.\n- What motivated the model designs? The authors switch between NN 1500-300 to NN100-10 to NN10-5 without much explanation. What's going on here?\n- Figure 3 is above figure 2 — confusing.\n- Results are extremely sparse and confusing. MeanOpt sometimes requires fewer batches than random or greedy and sometimes doesn't. On the GeneDisco experiments it looks like the author's models work the best on 3/4 conditions but I have no idea of effect size.\n- The authors acknowledge that they assume noiseless responses and that they will focus on noisy responses in the future. For biological applications -- and especially for any kind of sequencing -- I'm worried that the noiseless assumption is overly optimistic even when operating on populations. I'd like to hear more from the authors on why an assumption of no noise is OK here.\n\nMinor\n\n- The citations in text do not always appear correctly (I think you should be using \\citep sometimes when you are not).\n- The model names are very confusing. A figure might help? Also easier to grok names? They're all the same type of model with different widths (right?), so something like narrow, baseline, wide might help.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%