Adaptive Sampling for Discovery
Authors: Ziping Xu
Eunjae Shim
Ambuj Tewari
Paul Zimmerman
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bandit
Discovery
Chemistry

Abstract: In this paper, we study a sequential decision-making problem, called Adaptive Sampling for Discovery (ASD). Starting with a large unlabeled dataset, algorithms for ASD adaptively label the points with the goal to maximize the sum of responses.

This problem has wide applications to real-world discovery problems, for example drug discovery with the help of machine learning models. ASD algorithms face the well-known exploration-exploitation dilemma. The algorithm needs to choose points that yield information to improve model estimates but it also needs to exploit the model. We rigorously formulate the problem and propose a general information-directed sampling (IDS) algorithm. We provide theoretical guarantees for the performance of IDS in linear, graph and low-rank models. The benefits of IDS are shown in both simulation experiments and real-data experiments for discovering chemical reaction conditions.

Adaptive Sampling for Discovery
Ziping Xu Department of Statistics University of Michigan zi zipingxuGumic ch, edu
Eunjae Shim Department of Chemistry University of Michigan eun j ae ch. edu
Ambuj Tewari Department Statistics University of Michigan tewar inraria@umi ch, edu
Paul Zimmerman
Department of Chemistry University of Michigan paulzim@umich ch. edu
Abstract
In this paper, we study a sequential decision-making problem, called Adaptive Sampling for Discovery (ASD). Starting with a large unlabeled dataset, algorithms for ASD adaptively label the points with the goal to maximize the sum of responses. This problem has wide applications to real-world discovery problems, for example drug discovery with the help of machine learning models. ASD algorithms face the well-known points that yield information to improve model estimates but it also needs to exploit the model. We rigorously formulate the problem and propose general information-directed sampling (IDS) algorithm. We provide theoretical guarantees for the performance of IDS in linear, graph and low-rank models. The benefits of IDS are shown in both simulation experiments and real-data experiments for discovering chemical reaction conditions.
exppotttincellliaittioonnoo dilemma. The algorithm needs to choose
1 Introduction
Machine Learning (ML) models are becoming increasingly popular for discovery problems in various areas like drug discovery (40 5 388 and scientific discoveries [13 23 19]. Despite its success in real-data applications, the theoretical aspects of the problem are not fully understood in the machine learning literature. this paper, we consider a particular case of discovery and formalize problem that we call Adaptive Sampling for Discovery (ASD). In ASD, an algorithm sequentially picks T samples
out of size-n unlabeled dataset S (T < n) and obtains their labels YI...., Yr with the goal to maximize the sum Σ Yr. The labels correspond to the quality of discoveries, which can be continuous ordered categorical variables depending the types of discoveries. As a sequential decision- makiin problem, we find it substantially connected to the existing literature Multi-arm Bandit (MAB) and other related decision maddiinn-making problems, which we briefly review in the rest of this section.
Multi-arm bandit. MAB is a decision crdision-making problem that maximizes the total rewards by sequentially pulling and each corresponds to reward distribution (27). MAB faces the well-known exploration-exploiattioo trade-off dilemma. ASD has to deal with the same exploration-
exploitation dilemma if one treats each arm as an unlabeled point. The major difference between ASD and MAB is that each arm after being pulled once can still be pulled for infinite number of times, while we can only label a sample once ASD, This is because discovery can only be made once: one receives no credit making the same discovery twice.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In fact, as we will show later, ASD can be an MAB when each unique value in S" has larger than T' repeated samples and n < T Moreover, a variant of MAB called Sleeping Expert [22 24] can be seen as more general problem setup of ASD. One can intuitively interpret Sleeping Expert as the bandit problem where the set of available arms varies. More generally, bandit algorithms that allows adversarial choice of the action set can be used to solve the ASD problem. However, due to its generality, the regret bounds developed in [24) are loose or vacuous in our setup. Detailed discussions are deferred to Section 2
Due to the similarities between bandits and ASD, we adopt the same performance measurement, regret, from bandit literature. Regret is the highest sum of labels that could have been achieved minus the actual sum of labels.
There is a long line of work in the bandit literature on solving the sxploration-exploitaiiii tradeoff. Popular methods includes UCB (upper confidence bound), TS (Thompson sampling). UCB keeps an optimistic view on the uncertain model 4 (26]. which encourages the algorithm to select arms with higher uncertainty. TS [ adapts a Bayesian framework, which samples a reward vector from its posterior distribution and select arms accordingly. In this paper, we adopt another family of methods called coormationndirectedd Sampling (IDS). IDS [3]] balances between the expected information gain on the unknown model and instant regret with respect to the posterior distribution under a Bayesian framework. IDS has been shown to outperform UCB in problem with rich structural information, e.g. sparse linear bandit [14]. As we show below (Proposition [ the ASD problem is not interesting in the unstructured case which means we have use structural assumptions. That makes IDS a natural choice.
Traditional MAB algorithms designed for finite-armed bandits are not applicable ASD since the number of unlabeled samples n can be much larger than horizon I', There are works considering infinite-armed bandits by assuming structural information across arms. For instance, linear bandit assumes a linear model for the reward generation (27). [41] assumes Lipschizz-ontinuity and [42 considers neural network model for reward generation. However, there are few works studying sleeping expert with structure across arms beyond linear structure.
Other related literature. With a similar adaptive sampling procedure, Active Learning (AL) aims at achieving a better model accuracy with limited number of labels. As the reader may have noticed, the goal of AL aligns with ASD in the early stage when the model has high uncertainty and the predictions are high unreliable, while in the later stage ASD aims at better discovery performance. Indeed, there are active learning algorithms based on the idea of maximum information gain [3) (99 applies the idea to the matrix completion problem, which significantly improves the prediction accuracy from random selection. Other works with a similar goal go by the name sequential exploration 66 7 [7]. Their works lack a theoretical justification and the algorithms are not generally applicable.
more relevant setup in the active learning literature is Active Search (AS). Active search an active learning setting with the goal of identifying as many members of a given class as possible under a labeling budget. AS concerns the Bayesian optimal methods named Efficient Nonmyopic Search (ENS) 21 20 32). which is not computationally efficient. Their approximate algorithms for the Bayesian optimal method do not provide strong theoretical guarantee. A more detailed comparison between our proposed approach and ENS is given in Appendix
Main contributions. In this paper, we formulate the adaptive sampling for discovery problem and propose an generic algorithm using information-direct sampling (IDS) strategy. We theoretically analyze the regret of IDS under generalized linear model, low-rank matrix model and graph model assumptions. Indeed, the analysis for linear model are directly from IDS for linear bandit. The regret analysis for low-rank model and graph model are new even in the bandit literature. The results are complemented by simulation studies. We apply the algorithms to the real-world problems in reaction condition discovery, where our algorithm can discover about 20% more plausible reaction conditions than random policies and other simple baseline policies adapted from the bandit literature.
2 Formulation
In this section, we formally formulate ASD and rigorously discuss its connections to MAB.
2

---

Notations. We first introduce some notations that are repeatedly used in this puper. For any finite set S, we let ((S) be the set of all the distributions over the set. For any positive integer n, we let [n] = ( ..... :.). We use the standard O(-) and (?(-) notation to hide universal constant factors. We also use S b and a 2 b to indicate a = (b) and a (()).. ASD is sequential decision-making problem over discrete time steps. In general, we let F, be the observations up to decision step t. We adapt a Bayesian framework and let LE [-] = 1B|- Fi] be the conditional expectation given the history up to t. Let Pr, be the probability measure of posterior distribution.
Adaptive sampling for discovery. We formulate ASD problem as follows. Consider a problem with the covariate space X' Rd and label space y c [0, 1]. For categorical discoveries, the labels are ordered such that higher labels reflects better discoveries. Given a imput I E X. its label is generated from distribution Dola over 3' parametrized by unknown parameters 0. We adopt a Bayesian framework and denote the prior distribution of by Φ. Given a sequence of - 1 is denoted by d(. FF). We also let fo(x) = By- YY] be the expected label of input under model 0.
observations F, - {(x,, 1= the posterior distribution
ASD starts with an unlabeled dataset S C X' with n samples. Our goal to adaptively label T samples (X X7) C S to maximize the sum of labels Σ/= Y,- The discovered set is removed from available unlabeled set, i.e. each arm can only be pulled once. At each step t, an algorithm chooses an input X, from ST == Sn Y, Døjx.
The environment returns the label
To measure the performance of any algorithm, we borrow the definition of Bayesian regret from bandit literature [27]. Note that the regret definition is also used in Sleeping Expert (22). which is a more general framework than ASD. With respect to any chosen random sequence (X (X1,..., Xr), we define regret by
T
T Σ fo(X.). t=1
RT
max Fy ESH
Eo(aa)
(1)
Let ST = S"h [XI,...,X,_] be the remaining unlabeled set at the start of step t. An algorithm A is sequence of policies (T πT). Let D(ST) p=-t-1 be the set of all the distributions over ST that are denoted as n - -- D(ST) over Sp. The Bayesian Regret w.r.t. an algorithm is
- 1 vectors. Each ne is mapping from history Fe to distribution
BR( ERT,
where the expectation is taken over the randomness in the choice of input X,, the labeling Y, and over the prior distribution on 0. Let Xi...., Xi be the sequence that realizes the maximum in (T. Note that X .i..... Xi are random variables depending on 0. In general, the goal the algorithm is to achieve a sublinear regret upper bound.
Connections to bandit problem. This problem degenerates to classical bandit problem when X' discrete and 5th has infinite number of unlabeled samples for each unique value in X. In the bandit literature some frequentist results are available. The problem has the minimax regret rate / //T.T However, in our problem, we generally consider large unlabeled set (n >> T). In fact, when [X' is larger than 22, Proposition] shows that a linear regret is unavoidable without a structural assumption. Therefore, we discuss different types of structural information that allows information sharing across different inputs.
Proposition 1 (Lower bound for nonstructural case). Consider the following set of ASD problems. Let n = 2 St = [n] and Do (1 1) for [n] and 0 E [0, 1l". For any algorithm A, there exists some prior distribution over the set of ASDs described above such that BR A) Z T.
Compared with sleeping expert. Sleeping expert considers a generalized bandit framework where the available (awake) action set At are changing. It is the same as ASD except for that the changes of the unlabeled dataset (or awake action set) follow certain dynamic. That is whenever an input is labeled, it is taken out of the unlabeled dataset. However, sleep expert normally assumes stochastic distribution on A, or adversarial changes 124. 9. which makes their regret bound loose. To be specific, (22) derives regret bounds for unstructured bandits, which leads to vacuous regret bound
of VnI. For structured case, [24] derives the same regret bound in this paper, due to the strong
3

---

structure assumption for linear model. There are few literature for sleeping bandits with complicated structures beyond linear model. The regret bounds in the bandit literature for the other two models, graph and low-rank matrix models, are not applicable both resulting a S2(T) regret bound, which assures the necessity of studying ASD problem by itself.
3 Information-directer Sampling and Generic Regret Bound
In this section, we introduce strategy called Information- Dirrecttd Sampling and develop generic regret bound. IDS runs by evaluating the information gain the indices of the top T inputs with respect to the labeling of a certain input æ. balances between obtaining low expected regret in the current step and acquiring high information about the inputs that are worth labeling. We first introduce entropy and information gain.
Definition 1 (Entropy and information gain). For any random variable X E X with a density function F. its entropy is defined ( = =- -Srex P(x) log( ((x))). Let H(X Z) be the conditional entropy of given Z. The mutual information between any two random variables Y and X can be defined as I():Y) H(X) H(X Y). Conditional mutual information is I(X;Y Y Z) = H(X Z) - H(X Z) Furthermore, we use He and le for the entropy and mutual information under the posterior distribution up to step t.
For IDS, we let Ax(r) E, [maxx/es; Est fe(x') - fa(x)] be the expected instant regret. Let the information gain of selecting x at the step be (x()) = (X;,,. Xi1 Ye Fi X² = x),
where (X (Xi,)...., .....,,,irii xir-+t1
= (T x, E fo(x)) 2... 2o(TT-H+1)
1o(o")
max
xt 2
are the random variable for the top - t + unlabeled points. Note that (XE,,..., xx--411 C .... [i).. Intuitively, 9r (x) captures the amount of information on the indices of the top T T-t+1 points gained by labeling x.
IDS minimizes the following ratio
IDS E arg min (T)(T)= = (A) x) Te
T
for some constant À >>>> O,
(ED(
where A, E RR--++1 and 9t E R2-r+1 are the corresponding vectors for the expected single-step regret and information gain. Constant ratio here weighs between instant regret and information gain. higher prefers points with lower instant regrets. An abstract algorithm is given Algorithm |
Algorithm 1 IDS (Information-Directee Sampling) for Discovery
Input: Unlabeled dataset S"h prior distribution e, total number of steps T, constant X.
Initialize history Fo = (}. ST = S
fort to T do
Calculate (x) and g. (x) for each x E ST using posterior 66- Fr Sample X, arg max, Vr.A(T) and receive label from Døjx. Update history F. F U {(X,, Y))} and unlabeled dataset S7+1 ST \ (Xe). end for
We can show that the following generic Bayesian regret upper bound holds. Lemma 1. Suppose IIDSS_ (mz) (E()) and V (T+)) & V.,, Then we have IDS using constant X has the following regret bound
BR(T, BR(T,IDS) S (V., J
X7)TA-1111A.
As the case in the bandit problem, the regret bound depends on the worst-case information ratio bound and the entropy of the random variables for the top unlabeled points. Now we will discuss how to bound information ratios under various structural information assumptions.

---

Bounding Information Ratio under Structural Assumptions
In this section, we study three cases with different structural information.
4.1 Generalized linear model.
In this subsection, we discuss a generalized regression model, which includes logistic regression, corresponding to natural binary discovery problem. Consider d-dimensional generalized linear regression problem. The label Y given an input X is generated by
Y u (X) +e,
where l is usually referred as link function. We assume that Y is uniformly bounded in [0, 1]. In addition, we assume an upper bound on the derivatives of μ.
Assumption 1. The first order derivatives of p. are upper-bounded by Ly- Theorem 1. Under Assumption
we have V. S Lyd/2, which gives the Bayesian regret bound 7
BR(T, IDS) E ( L.
naive bound for (Xi X;) in 33 does not apply here because introduces a log(n) dependency. Instead, we notice that Xi .f...... XG is deterministic function of I and S We can bound the entropy of f instead. Assuming a Gaussian prior on 0, (0) S d dllo(d))
Indeed, the regret in ( is analogous to the regret bound in linear bandit (33 27 Theoretically, IDS does not show an advantage. This is partly because carefully designed algorithms for linear model sufficiently utilizing the structural information efficiently. [14] has shown that IDS achieves much tighter lower bound for sparse linear bandit compared to UCB-type algorithms and Thompson sampling algorithms. We show the Appendix Ghat IDS enjoys a regret bound of (sT22/3 in the discovery setting with sparse linear structure, with being the sparsity.
4.2 Low-rank matrix
In this subsection, we discuss novel problem setup: low-rank matrix discovery. Low-rank matrix completion problem has been extensively studied in the literature (25] 18 31.. However, most of the algorithms select entries with a uniform random distribution. In many applications, appropriately identifying a subset of missing entries in an incomplete matrix is of paramount practical importance. For example, we can encourage users to rate certain movies for movie rating matrix recovery. While selecting the users that reveal more information is important, it is also important to push the movies aligning with users tastes. Active matrix completion has long been studied in the literature R 29 [5].
As far as we know, no work has considered discovery setup, where the goal of adaptive sampling is not only to get a better recovery accuracy but also to maximize the sum observed entries.
Formulation. Consider an unknown matrix Y E Rm1xxa, whose entries (i,j) E [mn] x [m2] are sampled in the following manner:
Yr e Mr,e,, + E.j for e., being the noise for entry i,j,
where M E mm Xms is the unknown rank-r matrix and r < minfmm1, m2}. The matrix M admits SVD, i.c. M UDV", where U E mm xr and V e Rx are orthogonal matrix and D e Rrxr For simplicity, we let mi = m2 m. Our analysis can be easily extended to the case m, * m2.
Note that this setup is closely connected to the low-rank bandit problem except for that the actions are standard basis and can only be selected once. The best results in the literature (28) achieve a regret bound of 3/m3/2 /rT). Since in our case, T' m² the regret bound becomes vacuous. This finding implies that we need some further assumptions on the structure of the matrix. A common assumption the matrix completion is incoherence, an important concept that measures how the subspace aligns with the standard basis.
Definition 2 (Coherence). The coherence of subspace U with respect to the standard i-th basis vecior e; is defined as pa (U) [P 1 where Pt the orthogonal projection onto the subset defined by
U. Note that (U) = | e. as well.
5

---

Assumption 2 (Incoherence). There exists some constant > O. such that the unknown matrix M is incoherent, i.e max M4 (u(U) S v/r/m and maXiem (z(V) S Vrr/mm
To introduce our results, we further define some constants.
Remark 1. Let d be the maximum singular value of the unknown matrix M. We have
M S max p4 (u(U) & 7r3/2d/m B. max 1.3
Theorem 2. Under the low-rank matrix model with Assumption 2 the worst-case information ratio can be bounded by W.,3 S <BB(B² + ? which gives regret bound of
2 H(M))3)) 1/3
BT IDS) 2
The entropy term HMM depends on the distribution of M. To give an example, let M UVT where U, VT mg and each element in U and V are sampled independently from standard Gaussian. Then (M) I H(U,, V)) = (H(U) + (V) S mr log(mr). In general, the regret bound is still sublinear when mr* T < m².
4.3 Graph
We consider the discovery problem with graph feedback. Specifically, we are given graph (S") E), where the unlabeled set S is the node set. By labeling node E S", we receive noisy outcomes for all the nodes connecting to æ. Let the side information at step
O,(X,) = {Y (xt("""xxx where Y x' + ew' for ex being the zero-mean noise given r being selected. In addition to the side information, we also receive the label for X,, which is sampled in the same manner. This setup is also studied in the sleeping expert literature [9] [9] gives a regret bound depending EIΣ, z /u] where T2 is the total number of visits action and Qu is the total number of observations for action x. The ratio can be low when the algorithms tend to select nodes with high degrees and their algorithms are not designed for that purpose. Therefore, the structure not sufficiently exploited and the regret bound can be loose.
To measure the complexity of graph, introduce the following two definitions.
Definition 3 (Maximal independent set). An independent set is set of vertices in graph such that no two of which are adjacent. A maximal independent set (MIS) is an independent set that is not a subset of any other independent set. We denote the cardinality of the smallest maximum independent set of a graph G by (()).
Definition 4 (Clique cover number). A Clique of a graph G = (K,, E) is a subset $ C K. such that the sub-gre graph formed by S and & is a complete graph. A Clique cover of graph G (K, E) is partition of K. denoted by Q. such that Q is a clique for each Q E Q. The cardinality of the smallest clique cover is called the clique cover number, which is denoted by x(G).
Clique cover number is guaranteed to be larger than the cardinality of the smallest maximal independent set, i.e. C(G) S XG)).
Remark 2.
Since the nodes in the graph are diminishing, we further define a stable version of MIS. Definition 5. Let (G) he the set of all subgraphs of G with N - L nodes and define (G) ma C(G,).
Assumption 3. We assume that x + ce S B almost surely for all S and some constant B
Theorem 3. Under Assumption 3. the Bayesian regret of the IDS with X 2 can be upper bounded by
BR IDS) & min((BC (XXT))
Let us discuss certain graphs where the regret bound can be low, First, if the graph can be decomposed into K & T complete subgraphs, then XG) < K and we have a regret bound of / KT. An example, which C(G) is low while (G) is high, a star-shaped graph, with a set of nodes the center of the graph connecting all the other nodes. See Figure i in the Appendix for an illustration.

---

4.4 A generic results for models with structural information
As shown in sections 4.2 and 4.3 a T2/3 regret upper bound with a small coefficient can derived when the model has certain structural information. We give the following generic result, stating that as long as there exists policy μs, whose information gain can be lower bounded by the instant regret of Thompson sampling policy upper bound for V. 3,3 can be derived.
Proposition Assume that there exists a policy is such that gr p. Z a(A, " )² where mt the Thompson sampling policy at the step t. for some constant & and assume that the instant regrets are uniformly bounded by B. Then 3.3 S 2B/ o, which gives regret bound of ((BTH (0)/))))))
5
Experiments
We start with simulation studies on the three problems: (generalized) linear model, low-rank matrix and graph model. Since information gain can be hard to calculate in some problems, introduce sampling-bass approximate algorithms, which generate random samples from the posterior distribu- tion and evaluate variance term instead of the original information gain. We will also introduce general Thompson Sampling algorithms for all the three problem setups.
5.1 Approximate algorithms
may not be efficient to evaluate the information gain in certain problem setups. For example, one way to generate random low-rank matrix is to generate its row and column spaces from Gaussian distribution. We do not have a closed form for the posterior distribution of the resulting matrix. Neither can we evaluate the information gain. To that end, we follow approximate algorithmic design in [33]. which replaces the information gain with a conditional variance ey (xx) = Var, (E(Y, a. X X, x)), which will be evaluated under random samples from posterior distribution using MCMC. The conditional variance a lower bound of the information gain. An approximate algorithm
given by Algorithm 2 in Appendix H
Proposition 3. The following lower bound for information gain holds, (x) or (2))
Compared algorithms. For the rest of section, we compare IDS (the approximate algorithm), TS, UCB (if the bandit version is available) and random policy. As a method that closely connected to IDS, Thompson sampling (also referred as posterior sampling) is also compared in our experiments. Thompson sampling 36 at each round samples a Og from its posterior distribution and then selects the input with lowest instant regret w.r.t to 0j. TS does not account for the amount of information gain, thus can be insufficient in utilizing the structural information. UCB is an important algorithm design in bandit literature. Though it is not specifically designed for ASD, we apply UCB to (generalized) linear ASD by manually removing arms that have been selected.
5.2 Simulation studies
Linear and logistic regression model. The data generating distribution specified below. Unla- beled dataset is sampled from (O o.) and the prior distribution of 6 is A (O oz). The noise e is sampled from (0, a²). We study the effects regression model. The posterior distribution for 0 in simple linear regression is also Gaussian. For logistic regression, we used Laplace approximation for the posterior distribution [6]. We use the GLM-UCB [2] for logistic regression.
= 20, 50, 100. The same setup is used for logistic
Graph model. We consider different types of graphs. For each graph, the node values are sampled from standard Gaussian distribution and the noise are sampled from Gaussian with zero mean and of variance. We tested of 0.1, 1.0, 10. We experiment on graphs with N = 900. For a better demonstration of the early stage performance, we only show the first 50 steps. We experiment the following types of graphs. 1) Random connections: any node has a probability of p (= 0.01) to be connected: 2) Complete graph: every pair of nodes has an edge; 3) Star graph: 2/3 of nodes are randomly connected with probability of p (= 0.01). And the rest of 1/3 nodes are connected to all the nodes. Note that an example of star graph given in Figure 2 Since, no node complete graph provides more information than others, we expect TS and IDS perform the same. We expect IDS
7

---

outperforms TS more significantly in star graphs than it does in random graphs as there are more nodes gaining global information.
Low-rank matrix We sample each entry of U E Rdxr and V E Rdxr from (0, og) and let the unknown matrix = UV +, with each entry of from N o²). Since we do not have a closed form for the posterior distribution, posterior samples are generated from MCMC algorithm. In the experiment, we let m = 30, which gives us 900 steps at maximum. For a better demonstration the early stage, show the cumulative regrets in the first 100 steps.
Results. Figure shows the simulations results for the four models above. IDS has lower cumulative regrets over all the steps linear model, logistic model, graph random and graph star model. TS and IDS always outperform random policy and UCB (if available), showing benefit of developing algorithms for ASD. In the graph experiments, IDS and TS performs almost the same for complete graph because any imput gains information of the full graph. IDS has slightly lower regrets than TS in random graph because the weak structural information. It has significantly lower regrets than TS and random because of the stronger structural information. As shown in (b, d). the cumulative regrets steo 100 grows linearly with A higher noise also leads to a higher regret as shown (f, h, j. 1). IDS performs better in different levels of d for linear models and different levels of for graph random, graph star, matrix.
Linear model
Logistic model
(a)
(b) Regret 100
(c) d
(d) Regret
100
Graph (complete)
Graph (random)
oe) = 0.1
(f) Regret T 50
o 0.1
(h) Regret at T = 50
Graph (star)
Matrix
0) 0.1
(i) Regret at
50
(k) o. 0.1
(I) Regret at T 100
Figure Cumulative regret curves for linear regression (a, b), logistic regression (c. d), random graph, complete graph, star graph (e-j) and low-rank matrix (k, l). Columns and 3 are the cumulative regret curves for different models. Columns 2 and are cumulative regret at an early step for different hyperparameters. For linear and logistic regression model, d ranges in (20. 50, 100). For graph model, of ranges in 10.1, 1, 1.0, 10). For low-rank matrix, o? ranges (0.1,0.5. 1.0).
5.3 Reaction condition discovery
To further test the usefulness of IDS and for ASD in real-world problems, we consider reaction condition discovery problem in organic chemistry.
Background and dataset. In the chemical literature, single reaction condition that gives the highest yield for one set of reacting molecules is often demonstrated on couple dozen analogous

---

molecules. However, for molecules with structures that significantly differ from this baseline, one needs rediscover working reaction conditions. This provides a significant challenge as the number of plausible reaction conditions can grow rapidly, due to factors such as the many combinations of individual reagents, varying concentrations of the reagents, and temperature. Therefore, strategies that can identify many high-yielding reaction conditions as early possible would greatly facilitate the preparation of functional molecules. Similar reaction condition discovery problem is studied under a transfer learning framework (30 37
The IDS algorithms may therefore be highly useful in examining experimental data compared UCB, TS and random policies. Two experimental datasets reactions that form carbon- surbon-nitrogen bonds, which are high importance for synthesizing drug molecules, were therefore selected as specific test cases. The first dataset, named Photoredox Nickel Dual- Sual-Catallsiis (PNDC) []], comes from reaction that involves two types of catalysts (a photocatalyst and nickel catalyst) that work together to form carbon-nitroge the dataset are the identity of photocatalysts, relative catalyst concentration, and relative substrate concentration, totaling 80 reaction conditions. The second C-N Cross-Couplics
bonds. It has n 80 reaction conditions for discovery. The variables in
with Isoxazoles (CNCCI) dataset 2 comes from a collection of a croslicg reactions in the presence of an additive. This dataset was designed to test the reaction's 's tolerance to the additíve (isoxazole) and includes 330 candidate reactions. Both datasets have continuous response variables (reaction yield).
Results. Table demonstrated the results of linear IDS, TS, UCB for PNDC and CNCCI We tuned hyperparameters for all three algorithms. Details are given in Appendix H Over 17 steps, IDS showed a dominant performance all molecules tested in PNDC with an average of 1.58 more discoveries than random policy. Either IDS or TS performs the best in the 9 combinations of catalyst and base tested in CNCCI dataset. Over 66 steps, IDS discovers 14.1 more plausible reaction conditions on average than random.
Table Summary of cumulative regrets at 20% of total number of steps. Each column corresponds to target molecule. The regrets are averages of 10 independent runs, whose standard deviation are given in the brackets. Best algorithm for each column is marked in red. (-) denote that the algorithms are deterministic. The columns are the indices for target molecules, whose details are provided in
Appendix H
Molecules
X2
X3
X4
X5
X6
X8
Algorithms
Random
8.77 (1.44)
7.74 (0.75)
2.12 (0.20)
1.70 (0.15)
4.96 (0.72)
9.90 (1.47)
IDS
6.53 (0.20)
5.70 (0.52)
1.56 (0.06)
0.81 (0.01)
3.44 (0.81)
9.35 (0.96)
TS
7.64 (1.11)
6.67 (1.09)
2.15 (0.48)
1.22 (0.38)
4.07 (1.30)
9.78 (1.69)
UCB
9.63 (-)
(-)
2.58 (-)
(-)
5.26
10.43 (-)
XI1
X12
X13
X14
X15
Random
7.15 (1.21)
5.27 (0.92)
4.44
5,72 (0.35)
2.65 (0.47)
IDS
2.40 (0.12)
3.95 (0.19)
3.22 (0.21)
4.94 (0.07)
1.09 (0.03)
TS
2,90 (1.76)
4.42 (0.90)
4.79 (1.17)
5.39 (0.64)
1.35 (0.43)
UCB
3.58 (-)
5.28
4.53 (-)
5.86 (-)
(-)
(a) Results for PNDC
Catalyst and Base
LI+BI
L2+BI
L3+B1
L4+B1
LI+B2
Algorithms
Random
25.65 (2.11)
23.08 (1.98)
19.90 (1.19)
15.96 (0.83)
29.59 (1.26)
IDS
15.55 (1.52)
7.90 (0.28)
10.03 (0.88)
10.81 (0.79)
10.76 (0.51)
TS
11.84 (1.04)
9.82 (2.23)
11.58 (4.31)
10.39 (0.81)
12,49 (1.10)
UCB
13.63 (-)
10.08 (-)
12.00
11.98
17.41 (-)
L4+B2
L1+B3
L3+B3
L4+B3
Random
28.78 (2.59)
19.84 (0.81)
29.03 (2.22)
27.08 (2.51)
IDS
10.51 (1.32)
8.63 (0.97)
8.76 (0.32)
9,44 (0.52)
TS
12.68 (2.33)
10.61 (0.99)
12.44 (7.39)
9.80 (2.39)
UCB
15.60 (-)
12.42 (-)
11.49 (-)
12.32 (-)
(b) Results for CNCCI

---

Discussion
In this paper, we posed and comprehensively studied the Adaptive Sampling for Discovery problem and proposed the Information-directed sampling algorithm along with its regret analysis. The results are complemented with both simulation and real-data experiments. There are few open directions following the results in the paper. First, although our paper shows bandit-like regret bounds, ASD problem by nature different from bandit in the way that the unlabeled set is diminishing, which may further reduce the complexity of the problem. For example, in the linear model, all the unlabeled points may fall on a lower dimensional hyperplane, which would reduce the dependence on Second, frequentist regret may be studied instead of adopting a Bayesian framework. More practical algorithms e.g. random forests and neural network may be considered the future work. Sampling from posterior can be slow for certain models. A fast and generalizable algorithm using IDS for more complicated and larger scale real-data applications may be considered.
Acknowledgement
We acknowledge the support of National Science Foundation via grant IIS-2007055 and CHE- 1551994.
References
[1] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[2] Derek T Ahneman, Jesús G Estrada, Shishi Lin, Spencer D Dreher, and Abigail G Doyle. Predict- ing reaction performance in c-n cross-coupling using machine learning. Science, 360(6385):186 190. 2018.
[3] Kasra Arnavaz, Aasa Feragen, Oswin Krause, and Marco Loog. Bayesian active learning for maximal information gain on model parameters. In 2020 25th International Conference on Pattern Recognition (ICPR), pages 10524-10531. IEEE, 2021.
[4] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[5] Jürgen Bajorath, Steven Kearnes, W Patrick Walters, Nicholas A Meanwell, Gunda Georg, and Shaomeng Wang. Artificial intelligence in drug discovery: into the great wide open, 2020.
[6] J Eric Bickel and James E Smith. Optimal sequential exploration: A binary learning model. Decision Analysis, 3(1):16 16)32,63,22000 2006.
[7] David B Brown and James E Smith. Optimal sequential exploration: Bandits, clairvoyants, and wildeats. Operations research, 61(3):644 665, 2013.
[8] Shayok Chakraborty, Jiayu Zhou, Vineeth Balasubramanian, Sethuraman Panchanathan, Ian Davidson, and Jieping Yc. Active matrix completion. In 2013 IEEE 13th international conference data mining, pages 81-90. IEEE, 2013.
[9] Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang, Online learning with sleeping experts and feedback graphs. In International Conference on Machine Learning, pages 1370-1378. PMLR. 2019.
[10] Shi Dong and Benjamin Van Roy. An information-theoretic analysis for thompson sampling with many actions. Advances in Neural Information Processing Systems, 31, 2018
[11] Spencer Dreher and Shane W Krska. Chemistry informer libraries: Conception, early experi- ence, and role in the future of cheminformatics. Accounts of Chemical Research, 54(7):1586 1596, 2021.
[12] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems, 23, 2010.
10

---

[13] Yolanda Gil, Mark Greaves, James Hendler. and Haym Hirsh. Amplify scientific discovery with artificial intelligence. Science, 346(6206):111-122 2014.
[14] Botao Hao, Tor Lattimore, and Wei Deng. Information directed sampling for sparse linear bandits. Advances in Neural Information Processing Systems, 34, 2021.
[15] Zichang He, Bo Zhao, and Zheng Zhang. Active sampling for accelerated mri with low-rank tensors. arXiv preprint arXiv:2012.12249, 2020.
[16] Tommi S Jaakkola and Michael I Jordan, variational approach bayesian logistic regression models and their extensions. In Sixth International Workshop on Artificial Intelligence and Statistics, pages 283-294, PMLR, 1997.
[17] Babak Jafarizadeh and Reidar Bratvold. The two-factor price process in optimal sequential exploration. Journal of the Operational Research Society, 1377)11677-1477 2021.
[18] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fifth annual ACM symposium Theory of computing, pages 665-674, 2013.
[19] Xiaowei Jia, Jared Willard, Anuj Karpaine, Jordan S Read, Jacob A Zwart, Michael Steinbach, and Vipin Kumar. Physics-guidee machine learning for scientific discovery: An application in simulating lake temperature profiles. ACM/MMS Transactions on Data Science, 2(3):1-26, 2021.
[20] Shali Jiang, Gustavo Malkomes, Matthew Abbott, Benjamin Moseley, and Roman Garnett. Efficient nonmyopic batch active search, Advances in Neural Information Processing Systems, 31, 2018.
[21] Shali Jiang, Gustavo Malkomes, Geoff Converse, Alyssa Shofner, Benjamin Moseley, and Roman Garnett. Efficient nonmyopic active search. In International Conference on Machine Learning, pages 1714-1723. PMLR, 2017.
[22] Varun Kanade, H Brendan McMahan, and Brent Bryan. Sleeping experts and bandits with stochastic action availability and adversarial rewards. In Artificial Intelligence and Statistics, pages 272-2792 PMLR, 2009.
[23] Anuj Karpatne, Gowtham Atluri, James H Faghmous, Michael Steinbach, Arindam Banerjee, Auroop Ganguly, Shashi Shekhar, Nagiza Samatova, and Vipin Kumar. Theory-guided data science: A new paradigm for scientific discovery from data. IEEE Transactions on knowledge and data engineering, 29(10))218823333 2017.
[24] Robert Kleinberg, Alexandru Niculescu- Mizil, and Yogeshwer Sharma. Regret bounds for sleeping experts and bandits. Machine learning, 80(2):245 272,, 2010.
[25] Vladimir Koltchinskii, Karim Lounici, and Alexandre B Tsybakov. Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. The Annals of Statistics, 39(5):2302- 2329, 2011.
[26] Tor Lattimore. Optimally confident ucb: Improved regret for finite-armed bandits. arXiv preprint 1rXiv:1507.07889 2015.
[27] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[28) Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Low-rank generalized linear bandit problems. In International Conference on Artificial Intelligence and Statistics, pages 460-468. PMLR, 2021.
[29] Simon Mak, Henry Shaowu Yushi, and Yao Xie. Information-guidee sampling for low-rank matrix completion. arXiv preprint 17X6vv/706.08037 2017.
[30] Gregory McInnes, Rachel Dalton, Katrin Sangkuhl, Michelle Whirl-Carrillo, Seung-been Lee, Philip Tsao, Andrea Gaedigk, Russ B Altman, and Erica I. Woodahl. Transfer learning enables prediction of cyp2d6 haplotype function. PLoS Computational Biology. 16 16(1I):c100839, 2020.
11

---

[31] Luong Trung Nguyen, Junhan Kim, and Byonghyo Shim. Low-rank matrix completion: A contemporary survey. IEEE Access, 7:94215-94233 2019.
[32] Quan Nguyen and Roman Garnett. Nonmyopic multiclass active search for diverse discovery. arXiv preprini arXiv:2202.03593, 2022.
[33] Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directe sampling. Advances in Neural Information Processing Systems, 27, 2014.
[34] Daniel Russo and Benjamin Van Roy. An information- theorretc analysis of thompson sampling. The Journal of Machine Learning Research, 17(1):2442-244 2471, 2016.
[35] Daniel Russo and Benjamin Van Roy. Learning optimize via information-directed sampling. Operations Research, 66(1):230-25,, 2018.
[36] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, lan Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[37] Eunjae Shim, Joshua Kammeraad, Ziping Xu, Ambuj Tewari, Tim Cernak, and Paul Zimmerman. Predicting reaction conditions from limited data through active transfer learning. Chem. Sci., pages 2022.
[38] Thomas J Struble, Juan C Alvarez, Scott P Brown, Milan Chytil, Justin Cisar, Renee DesJarlais, Ola Engkvist, Scott A Frank, Daniel R Greve, Daniel J Griffin, et al. Current and future roles of artificial intelligence in medicinal chemistry synthesis. Journal of medicinal chemistry, 63(16):8667-8682 2020.
[39] Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Statistically and computationally efficient linear meta-representatioon learning. Advances in Neural Information Processing Systems, 34, 2021.
[40] Jessica Vamathevan, Dominic Clark, Paul Czodrowski, Ian Dunham, Edgardo Ferran, George Lee, Bin Li, Anant Madabhushi, Parantu Shah, Michaela Spitzer, et al. Applications of machine learning in drug discovery and development. Nature reviews Drug discovery, 18(6)463-4777 2019.
[41] Yizao Wang, Jean- Yves Audibert, and Rémi Munos. Algorithms for infinitely many-armed bandits. Advances in Neural Information Processing Systems, 21, 2008.
[42] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 1492-115022, PMLR, 2020.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes], [No] or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Supplementary material.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license the code and datasets? [N/]]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
12

---

(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations are discussed in the Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Depending on the area of application, the impact can be different. The potential impact of reaction discovery is in/6
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof' of all theoretical results? [Yes] The proof' are given in Appendix
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL.)? [Yes] The codes and dataset are in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] They are provided along with code
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Figure I and Table
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] They given in Appendix H
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
We include our code in the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] The data are realised with their publications.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] The data does not have personally identifiable information or offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "xRmuwcIaF9z", "reviewer": "Reviewer_uuVE", "summary": "This paper presents an adaptive sampling strategy for labeling in the finite sample region (without replacement in contrast to MultiArmed Bandit (MAB) scenario) with the overall objective to maximize the sum of label values of sampled points. The proposed algorithm (IDS) uses  information gain (objective being ratio of regret and information gain at that time step) in order to sample the next point to label. The authors show leveraging model structure leads to improved regret bounds for low-rank matrix and feedback graph models. Finally, the authors present real-world application of IDS to the problem of reaction discovery. \n", "questions": "- On the feedback graph model [https://arxiv.org/pdf/1106.2436.pdf], would it be correct to say that the setup in this paper can be modeled by considering at each point, the previously sampled point is removed from $G_t$ (the next feedback graph). If so, would the algorithms for sleeping expert setting be comparable? For example, the empirical evaluations in [9] are not directly comparable per my reading - if so, this can be mentioned explicitly in the text. \n", "limitations": "- Line 94. \"each arm can be be pulled twice\" -- per my understanding this should read \"each arm {\\em cannot} be pulled twice\" \n- Definition 1 Line 134. Request to define $H(X | Z)$ for completeness. \n- Line 146. \"A higher  $\\lambda$ weigh\" - double line. \n- Line 177. Define $e_i$ (basis vector) before using it. Its' defined later in Line 187.  \n- Line 201. \"given $x$ being selected\", I understood this as $X_t = x$ (at time t, node $x$ selected for labelling which gives its value and noisy values for all its labels). Can this be clarified in writing? \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n+ Good survey of related work and putting their results in context. \n+ Application of IDS to linear model, low-rank matrix model and graph model.\n+ Interesting real-world application (Reaction Condition Discovery)\n\n\n### Weaknesses\nThe writing could be made a bit clearer.\n\n- I am a bit fuzzy on the real-world application which could be better explained in the supplementary material if not the main text. Per my understanding, the dataset has been taken - PDNC or CNCCI (https://doyle.chem.ucla.edu/wp-content/uploads/2020/07/43-Predicting-Reaction-Performance-in-C-N-Cross-Coupling-Using-Machine-Learning.pdf), but the final result is not comparable to cited papers. For example, Shim etal. (https://pubs.rsc.org/en/content/articlelanding/2022/sc/d1sc06932b original ref [34]) - I would have expected to see something like Figure 3 (if comparing the IDS in the Active Learning setup). {\\em Else it should be clarified that a contrived subtask has been taken to evaluate the problem and show a possible future application.} I understand this is not the main focus of the paper so that clarification would be sufficient. \n\n- For clarity and completeness, please add a section in supplementary material explicitly describing the PDNC and CNCCI datasets (tied to the data available in this upload, namely, Informer.xlsx and doyle_matrix.xlsx),  and, how this translates to the problem setting. \n\n- The parameter $\\lambda$ controlling the ratio between instant regret and information gain is also used in the approximate algorithm (supplementary material H). However, its value is not clarified and the sensitivity of empirical results depending on its choice is unclear to me (or I missed it)? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Lc95sE0Q8Hx", "reviewer": "Reviewer_A6az", "summary": "This paper introduces a sequential decision-making problem where the goal is to select a few samples and the reward is the sum of the responses from the samples. We want to maximize the reward (or minimize the regret), and we want to choose the samples adaptively, in an exploration-exploitation fashion. This is achieved by using information gain to determine the next element to sample. A number of heuristics/variants are proposed for when the information gain cannot be computed easily. An experimental evaluation, and a realistic case study, complete the paper, showing the performance of the proposed method.", "questions": "* In the pseudocode for the algorithm (Algorithm 1), the computation of $\\Delta_t(x)$ and $g_t(x)$ is vaguely described as being done \"using posterior $\\phi(\\cdot \\mid \\mathcal{F}_{t-1})$. It is very unclear to me how that would happen, even if we had complete knowledge of the posterior and could easily draw samples or compute any probability according to the posterior. I guess my issue or maybe my question is whether, in the definitions of $\\Delta_t(x)$ and $g_t(x)$, the expectations are taken also w.r.t. the posterior (and if so, why is that correct). I think that, if that is the case (or whatever is the case), this aspect should be better clarified (perhaps right now is mentioned on lines 83-84, but perhaps it should be repeated closer to the definitions above.\n\n* On line 94, I think that \"be be\" should be changed to \"not be\".", "limitations": "I do miss a discussion of the limitations of the proposed approach and/or of the proposed problem. It is hard to predict negative societal impact, but one could assume that such an  algorithm could be used to target individuals on the bases of some reward that could be obtained by having them perform some action, which one has to wonder whether would negatively affect underserved populations and minorities.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* The presentation is quite clear. The discussion of the relation with MAB and related problem is commendable in terms of clarity. The one issue in clarity is a single but crucial aspect about the use of the posterior. See the question below. \n* The proposed problem is quite interesting, and relevant to areas outside \"core\" machine learning.\n* The proposed algorithm, with its use of information gain to minimize Bayesian regret, makes sense and it is described well. The \"instatiations\" of the algorithm under different knowledge of the model are also interesting and make the paper a bit more concrete. \n* The evaluation is pretty convincing.\n* Additional discussion of the limitations of the proposed approach would have well completed the work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "135ZTfnaikU", "reviewer": "Reviewer_LiPB", "summary": "The paper tackles an active learning/bandit problem in which utility is defined to be the sum of the observed labels.\nThe proposed policy minimizes the ratio between the expected instant regret and the expected gain in information about the labels of the top unlabeled points (the number of these top unlabeled points matches the remaining budget).\nIn some settings where exact computation is intractable, the policy falls back to MCMC posterior sampling.\nThe authors then present theoretical results about the regret bound for their policy under specific settings such as linear models, low-rank matrix, and graph problems, and discuss situations in which we can obtain a low regret.\nThe paper also includes extensive experiment results showing that their method is competitive against popular baselines like UCB and Thompson sampling.", "questions": "It would be great if the authors could elaborate on their contributions with respect to the AS literature.\nI would be interested to see a comparison between IDS and the policies in [2] and [3], which are specifically designed for AS and should serve as stronger baselines than UCB and Thompson sampling.\nIn particular, the policy in [3] maximizes the expected value of the sum of labels of the top unlabeled points, which should have the same computational cost as IDS but is more utility-centric.\nAlong the same lines, there could be variant of IDS where the numerator of the acquisition function is the _cumulative regret_, as opposed to the instant regret.\nI think this would have the same cost as IDS, since you would have to pick out the top unlabeled points anyway.\nI would be interested to see how this variant performs.\n\nI would also like to see a couple of things added to the presentation of the experiment results.\n- What is the interpretation for the sharp turns in the first row of Figure 1 (in the middle of Figure 1c, for example)?\n- UCB is missing from some of the plots.\n- The authors could consider adding information about whether results in Table 1 are statistically significant.\n\nMiscellaneous:\n- The authors could consider making the plot axis labels larger and use a larger, shared legend.\n- Line 86: missing dot before \"For categorical\"\n- Line 94: I believe the authors meant \"each arm can only be pulled once.\"\n- Line 146: Redundant \"A higher lambda\"", "limitations": "Yes, the paper mentions its limitations in the Discussion section in the form of future directions.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and clear.\nThe structure of the exposition is good, and both the problems and proposed policy are well-motivated.\nThe authors did a good job connecting this problem to multi-armed bandit, and I enjoyed reading about the special settings like low-rank matrix and graph problems.\nIt is clear from their experiment results that their policy consistently performs well across many tasks compared to other benchmarks in the bandit literature.\n\nIn terms of weaknesses, I believe the authors have missed a particularly relevant line of research on the \"active search\" problem [1, 2, 3].\nThere seem to be significant similarities between ASD and AS: utility being the sum of observed labels, large amount of unlabeled data, limited labeling budget, etc.\nAs of now, I am not sure whether this setting is any different from those studied in the references above.\nFurther, although the information-theoretic approach is a common heuristic, it is not clear to me whether it actually brings additional value, compared to a variant of the policy that aims to minimize the expected _cumulative_ regret (which should roughly have the same cost as the proposed policy).\nMore details are included in the Questions section.\n\nOverall, the submission addresses an important problem and the proposed solution seems to work well on the inspected settings.\nThe theoretical results are also interesting.\nHowever, this work would benefit from a closer look at the AS problem and highlighting why their approach of optimizing their acquisition function is novel and beneficial.\nThis would help situate the paper in the literature better and clarify its contributions.\n\n[1] Garnett et al. Bayesian Optimal Active Search and Surveying. ICML 2012.\n\n[2] Vanchinathan et al. Discovering valuable items from massive data. KDD 2015.\n\n[3] Jiang et al. Efficient Nonmyopic Active Search. ICML 2017.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept