Greedy Approximation Algorithms for Active Sequential Hypothesis Testing
Authors: Kyra Gan
Su Jia
Andrew A Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: Approximation Guarantee
Active Learning
Sequential Hypothesis Testing
Greedy Aglorithm
Cancer Detection

Abstract: In the problem of \emph{active sequential hypothesis testing} (ASHT), a learner seeks to identify the \emph{true} hypothesis from among a known set of hypotheses. The learner is given a set of actions and knows the random distribution of the outcome of any action under any true hypothesis. Given a target error $\delta>0$, the goal is to sequentially select the fewest number of actions so as to identify the true hypothesis with probability at least $1 - \delta$. Motivated by applications in which the number of hypotheses or actions is massive (e.g., genomics-based cancer detection), we propose efficient (greedy, in fact) algorithms and provide the first approximation guarantees for ASHT, under two types of adaptivity. Both of our guarantees are independent of the number of actions and logarithmic in the number of hypotheses. We numerically evaluate the performance of our algorithms using both synthetic and real-world DNA mutation data, demonstrating that our algorithms outperform previously proposed heuristic policies by large margins.

Greedy Approximation Algorithms for Active Sequential Hypothesis Testing
Kyra Gan", Su Jia, Andrew A. Li Carnegie Mellon University Pittsburgh, PA 15213 (kyragan, aali))mmm edu
Abstract
In the problem of active sequential hypothesis testing (ASHT), learner seeks identify the true hypothesis from among a known set of hypotheses. The learner is given set of actions and knows the random distribution of the outcome of any action under any true hypothesis. Given target error ò >> 0, the goal is to sequentially select the fewest number of actions so identify the true hypothesis with probability at least 1 - 8. Motivated by applications in which the number of hypotheses or actions is massive (c.g.. genomics basedd cancer detection), we propose efficient (greedy, in fact) algorithms and provide the first approximation guarantees for ASHT, under two types of adaptivity. Both of our guarantees are independent of the number of actions and logarithmic in the number of hypotheses. We numerically evaluate the performance of our algorithms using both synthetic and real-worls DNA mutation data, demonstrating that our algorithms outperform previously proposed heuristic policies by large margins.
1 Introduction
Consider the problem of learning the true hypothesis from among a (potentially large) set of candidate hypotheses H. Assume that the learner given a (potentially large) set of actions A, and knows the distribution of the noisy outcome of each action, under each potential hypothesis. The learner incurs a fixed cost each time an action is selected, and seeks identify the true hypothesis with sufficient confidence, at minimum total cost. Finally, and most importantly, the learner is allowed to select actions adaptively.
This well-studied problem is referred to as active sequential hypothesis testing, and as we will describe momentarily, there exists broad set of results that tightly characterizes the optimal achievable cost under various notions of adaptivity. Unfortunately, the corresponding optimal policies are typically only characterized as the optimal policy to a Markov decision process (MDP) thus, they remain computationally hard to compute when one requires a policy in practice. This deficiency becomes particularly apparent in modern applications where both the set of hypotheses and set of actions are large. As a concrete example, we will describe later on application to cancer blood testing that has tens of hypotheses and billions of tests at full scale. Thus motivated, we provide the first approximation algorithms for ASHT.
We study ASHT under two types of adaptivity: partial and full, where partial adaptivity requires the sequence of actions to be decided upfront (with adaptively chosen stopping time), and full adaptivity allows the choice of action to depend on previous outcomes. For both problems, we propose greedy algorithms that run in O([A] H|) time, and prove that their expected costs are upper bounded by a non-trine non-trivial multiplicative factor of the corresponding optimal costs. Most notably, these
Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Noise
Approximation Ratio
Objective
Adaptivity Type
[34]
Yes
No
Average
Both
[36]
Yes
No
Worst-case
Fully adaptive
[25]
No
Yes
Both
Partially adaptive
[28, 10]
No
Yes
Both
Fully adaptive
[26]
Semi*
No
Both
Both
This Work
Yes
Yes
Both
Both
Table 1: Summary of related work.
*Semi refers restrictive special case.
approximation guarantees are independent of | (contrast this with the trivially-achievable guarantee of A() and logarithmic in |H] (the optimal cost itself is often 2())
Our results rely drawing connections to two existing problems: submodular function ranking (SFR) [5] and the optimal decision tree (ODT) problem [30]. These connections allow us to tackle what is arguably the primary challenge in achieving approximation results for ASHT, which is its inherent combinatorial nature. We will argue that existing heuristics from statistical learning fail precisely because they disregard this combinatorial difficulty fffficulty-indeed, they largely amount to solving the completely non-adaptive version of the problem. At the same time, existing results for SFR and ODT fail to account for noise in manner that would map directly to ASHT extension is among our contributions.
Related Work Our work is closely related to three streams of research. Table I highlights the key differences between our contributions and those of the most relevant previous works.
(a) Hypothesis Testing and Asymptotic Performance: In the classical binary sequential hypothesis testing problem, decision maker is provided with one action whose outcome is stochastic [42, 3, 31], and the goal is to use the minimum expected number of samples to identify the true hypothesis subject to some given error probability. The ASHT problem, first studied in [14], generalizes this problem to multiple actions. Most related to our work is [34], who formulated a similar problem as an MDP. We will postpone describing and contrasting their work until the experiments section.
(b) Active Learning and Sample Complexity:
In active learning, the learner is given access to a pool of unlabeled samples (cheaply obtainable) and is allowed to request the label of any sample (expensive) from that pool. The goal is learn an accurate classifier while requesting as few labels as possible. Some nice surveys include [23] and [39]. Our model extends the classical discrete active learning model [17] in which outcomes are noiseless (deterministic) for any pair of hypothesis and unlabeled sample. When outcomes are noisy, the majority of provable guarantees are provided via sample complexity. [9] showed tight minimax classification error rates for a broad class of distributions. Other sample complexity results on noisy active learning include [43, 36, 7, 4, 24].
(C) Approximation Algorithms for Decision Trees: Nearly all optimal approximation al- gorithms for minimizing cover time are known in the noiseless setting [28, 1, 2]. When the outcome is stochastic, [21] proposed framework for analyzing algorithms under the adaptive submodularity assumption. However, their assumption does not hold for many natural setups including ASHT. [13] considered variant using ideas from the submodu- lar max-coverage problem, and provided a constant factor approximation to the problem. Other works based on submodular function covering include [35, 22, 29]. [26] provided approximation ratios under the constraint that the algorithm may only terminate when it is completely confident about the outcome.
2 Model
We begin by formally introducing the problem. Let H be finite set of hypotheses, among which exactly one is the (unknown) true hypothesis that we seek to identify. In this paper, we study the Bayesian setting, wherein this true hypothesis is drawn from known prior distribution over H.
Let A be the set of available actions. Selecting an action yields random outcome drawn indepen- dently from distribution within a given family D {Do Jece of distributions parameterized by

---

θ S R. We are given a function j:: H x A - θ such that if h E H is the underlying hypothesis and we select action a E A, then the random outcome is drawn independently from distribution Dp(h.a).
An instance of the active sequential hypothesis testing problem is then fully specified by a tuple: (H, A, n. D). The goal is to sequentially select actions identify the true hypothesis with "sufficiently high" confidence, at minimal expected cost, where cost is measured as the number of actions, and the expectation is with respect the Bayesian prior and the random outcomes. The notion of sufficiently high confidence is encoded by a parameter å E (0, 1), and requires that under any true h E H. the probability of erroneously identifying a different hypothesis is at most d. An algorithm which satisfies this is said to have achieved 6-PAC-
We focus on two important families of Dø's s: the Bernuuli distribution Ber(f) and the Gaussian distribution N(0, o²) where x² is a known constant (with respect to 0). By re-scaling, without loss of generality we may assume x² = 1. We require two additional assumptions to state our guarantees. The first assumption is needed for relating the sub-gaussian norm to the KI--divergence, in the partially adaptive version. ensures that the parameterization θ is meaningful one, in the sense that if 0, 0' E θ are far apart, then the distributions Dg and Dr are also "far" apart (as measured by KL divergence). Assumption I is satisfied for Ber(O) when 0 E [mmin maax] for some constants O <<< Omin < Omax < 1, and for (0,, 1) where 0 lies in some bounded set in I.
Assumption 1. There exist C1, C2 > O such that for any 9, 0' E O. we have C1 . KL((D,, S - ()- S C2 (L(,D, Dør), ), where (L(..-) is the Kullback-Leibler divergence.
Our second major assumption simply ensures the existence of a valid algorithm, by assuming that every hypothesis is distinguishable via some action.
Assumption 2 (Validity). For all g, h E H where g + h, there exists A with p(g,a) # jah, a).
In particular, we do not preclude the possibility that for a given action a, there exist (potentially many) pairs of hypotheses g, h such that p(g,,) a) = p(h,,), In fact, eliminating such possibilities would effectively wash out any meaningful combinatorial dimension to this problem. On the other hand, any approximation guarantee should be parameterized by some notion of separation (when it exists). For any two hypotheses g. h E H and any action a E A. define d(g, h;; a) = KL (Dugga)) D (i(h.a)) Definition (s- (s-separated instance). An ASHT instance is said to be s-separated, if for any a E A and g, h E H, d(g. h; a) is either 0 or at least
Note that in real-world applications, the parameter & could be arbitrarily small, and we introduce the notion of s-separability for the sake of proofs. We will show in Section 6 how our algorithms can easily be modified to handle small s values. In this work, we will study two classes of algorithms that differ in the extent to which adaptivity is allowed.
Definition 2. A fully adaptive algorithm is decision tree, each of whose interior nodes is labeled with some action, and each of whose edges corresponds to an outcome. Each leaf is labeled with a hypothesis, corresponding to the output when the algorithm terminates.
Definition 3. A partially adaptive algorithm (a, T) is specified by fixed sequence of actions a (01, 22,,... ...). with each o, E A. and a stopping time T'. In particular, under any true hypothesis ht H and for any t 2 1, the event {T' t} is independent of the outcomes of actions d 0t+2, (At the stopping time, the choice of which hypothesis to identify is trivial in our Bayesian setting it is simply the one with the highest "posterior" probability).
Note that a partially adaptive algorithm can be viewed as a special type of fully adaptive algorithm: it a decision tree with the additional restriction that the actions at each depth are the same. Therefore, a fully adaptive algorithm may be far cheaper than any partially adaptive algorithm. However, there many scenarios (e.g., content recommendation and web search [6]) where it is desirable fix the sequence of actions in advance. Furthermore, in many problems the theoretical analysis of partially adaptive algorithms turns out to be challenging (e.g.. [27, 12]).
Thus, given an ASHT instance, there are two problems that we will consider, depending on whether the algorithms are partially fully adaptive. In both cases, our goal is to design fast approximation
In this noisy setting, an action can (and often should) be played for multiple times. By approximating De's with discrete distributions, we may assume each node has a finite number of children.
3

---

algorithms ones that are computable in polynomial* time and that are guaranteed to incur expected costs at most within multiplicative factor of the optimum. In the coming sections, we will describe our algorithms and approximation guarantees. Before moving on to this, it is worth noting that our problem setup is extremely generic and captures number of well-known problems related to cedision-maknng for learning including best-arm identification for multi-armed bandits [8, 19, 32], group testing [18], and causal inference [20], just to name few.
3 Our Approximation Guarantees
We are now prepared to state our approximation guarantees (the corresponding greedy algorithms will be defined in the next two sections). Let OPT (resp. OPT denote the minimal expected cost of any partially adaptive (resp. fully adaptive) algorithm that achieves 5-PAC-error.
Theorem Given an s-separated instance and any E =0,01/11 1/2), there exists polynomial-tine partially adaptive algorithm that achieves 6-PAC-error with expected cost O (8- [1+1og1/4 [H] log (* 1ogg log.-)) OPT5A.
To help parse this result, if 8 on the order of [||-c for some constant c, then the approximation factor becomes s (log -- + +oo clog log H)). s-separated instance and any 5 (0,1/2), there exists polynomial-time fully adaptive algorithm that achieves 5-PAC-error with expected cost
Theorem 2. Given
O (s log (1H)6-1) log H|) OPT
A few observations might clarify the significance of these approximation guarantees:
1. Dependence on action space: Both guarantees are independent of the number of actions A]. This is extremely important since, as described in the Introduction, there exist many applications where the the action space is massive. Moreover, since approximation factor of ([Al) is always trivially achievable (by cycling through the actions), instances where |A| is large are arguably the most interesting problems.
2. Dependence on 1, 5 and s: For fixed s and 6, these are the first polylog-approximatio for both partially and fully adaptive versions. Further, for the partially adaptive version, p
the dependence of the approximation factor on Olog log 5-11 when 8-1 is polynomial in |/], improving upon the naive dependence Ollog 8 )) This is crucial since ô is often needed to be tiny in practice.
3. Greedy runtime: While have only stated in our formal results that approximation algorithms can be computed in poly( H)) time, the actual time is more attractive: ([A|] H) for selecting each action. In contrast, the heuristic that we will compare against in the experiments requires solving multiple [) linear programs.
Despite their similar appearances, Theorems 1 and 2 rely on fundamentally different algorithmic techniques and thus require different analyses. Section 4, we propose an algorithm inspired by the submodular function ranking problem, which greedily chooses sequence of actions according to carefully chosen "greedy score." " We then sketch the proof of Theorem In Section 5, we introduce our fully adaptive algorithm and sketch the proof of Theorem 2.
Finally, by proving structural lemma (in Appendix D), we extend the above results to special of the total-error version (i.e., averaging the error over the prior π) where the prior is uniform. With ô-total-error formally defined in Appendix D:
Theorem 3. Given an s-separated instance with uniform prior π and any 8 E (o, 1/4), for both the partially and fully adaptive versions, there exist polynomial-tine S-total-error algorithms with expected cost O (1+ H ()) log (1H18-1 log H) times the optimum.
Partially Adaptive Algorithm
This section describes our algorithm and guarantee for the partially adaptive problem. We first review necessary background from related problem, and then state our algorithm (Algorithm 1). Finally, we
'Throughout this paper, polynomial time refers polynomial in (1H1), [A], st,o-1)))

---

sketch the proof of the following more general version of Theorem 1 (complete proof in Appendix B):
Proposition 1. Let 8 E (0. _] and consider finding the optimal 8-PAC error algorithm. Given any boosting intensity a 2 and coverage saturation threshold B (0, 2 logó 6- (nB(BBo) a) (as defined in Algorithm 1) produces partially adaptive algorithm with error |H| exp (-52 (aB) and expected cost O _ log [ OPT!A.
By setting
/ [ and B 2 log 8. we immediately obtain Theorem 1.
Background: Submodular Function Ranking In the SFR problem, we are given ground
set U of N elements, a family F of non-decreasing submodular functions f 2 2 f(U) equaling 1 for every f F, and a weight function w + R+ For any permutation = (u,, .... uN) of U, the cover time of f is defined as CT(f,o) min(t: f(fu, f(fu) u = 1}. The goal to find permutation a of U with minimal cover time Σ5EF w(f) CT(f.o). We will use the following greedy algorithm, called GRE, in [5] subroutine. The sequence is initialized to be empty and constructed iteratively. At each iteration, let S be the elements selected far. GRE selects the element with the maximal coverage, defined as Cov(u: Σ)eF((S) w(f) (f U {u}) f(S)) /(1))//11111111 f1))
- [0, 1] with
Theorem ([25)). For any SFR instance, GRE returns sequence whose cost is Ollog !) times the optimum, where g := min { U {u)) - f(S) > 0: S E 2", U. E F}.
Challenge. To motivate our algorithm, consider first the following simple idea: "boost" (or repeat) each action enough, and hence reduce the problem to deterministic problem Pdes- We then show that the existing technique (submodular function ranking for partially adaptive and greedy analysis for ODT for fully-adaptive) returns policy with cost Olog HI) times the no-noise optimum, and finally show that this no-noise policy can be converted to a noisy version by losing anther factor of O log [#| one runs into:
This analysis was in fact our first attempt. However, there are at least two issues that
1. This analysis only compares the policy's cost with the no-noise optimum, but focus is the d-noise optimum. In particular, the simpler analysis implicitly assumes that the 5-noise optimum is at least ? log 8 times the no-noise optimum, which is not necessarily true. Moreover, challenging to analyze the gap between the no-noise optimum and the 8-noise optimum.
|H|
2. This simple analysis provides weaker guarantee than ours in terms of 5: it yields factor of log 1. as opposed to the log log &/ in our analysis. This distinction is nontrivial, particularly in applications where the error is required to be exponentially small in |H].
Rank and Boost (RnB) Algorithm Our RnB algorithm (Algorithm 1) circumvents the issues above by drawing a connection between ASHT and SFR. First, we observe that although an action is allowed to be selected for multiple times, we may assumne each action is selected for at most M ((, s, | 0
! log ( times. fact,
Observation Let Ā be the (multi)-set obtained by creating M copies of each E A. Then there exists a sequence a of [A| actions, such that h², the true hypothesis, has the highest posterior with probability 1 - 8 after performing all actions in a.
Thus, given A, we define f 2 + [0, 1] for any coverage saturation level B > 0 and h E H as (F) - EgEH((N) min (1, 1 Eaes d(g, h;; a)}. One can verify that f is monotone and submodular. Our algorithm computes a nearly optimal sequence of actions using the greedy algorithm for SFR, and creates number of copies for each of them. Then we assign timestamp to each h e HI, and scan them one by one, terminating when the likelihood of one hypothesis is dominantly high.
Proof Sketch for Proposition 1. analysis follows from standard concentration bounds, we focus the cost analysis. Suppose
We sketch proof and defer the details to Appendix B. The error
5

---

Algorithm 1 Partially Adaptive Algorithm: RnB(B,a)
Coverage saturation level and boosting intensity 0. 2: Input: ASHT instance (H, A, J, M,
Parameters:
3: Initialize: a + 0, +-
% Store selected actions.
4: For = 1, A do
% Rank: Compute a sequence of actions. % Actions selected so far.
5: St [o((), ..., (t 1)}.
6: For A.
% Compute scores for each action.
USU {a)) (S) (R)
Score(a; S) +
Σ
T(h)
(8)<(
7: af) t arg max a) AA5).
% Select the greediest action.
8: For - 1.,...., A|:
% Boost: Repeat each action in for times.
9:
For .....
10:
a(a(t- - 1) +i) + ot).
11:
For F a/Al:
12:
Select action ē(L) and observe outcome ye.
If a CT( 1/ .) for some H:
% If is the timestamp for some h.
14:
For g E H (h):
15:
A(h,9 g) II 11) (v.)/PP (
% Compute the likelihood ratio. % Hypothesis identified.
16:
If A ((h,g) g) 2 aB/2 for all g H then Return h.
> 0, 6 E (0, 4), and B E (0, log 2. Let (a',7" be any optimal partially adaptive algorithm, and let (o, T') be the policy returned by RnB. Our analysis consists of the following steps:
(A)
The sequence does well in covering the submodular functions, in terms of the total cover time: ΣnEH (h) CT o)
[log | EneH <(h) CT(fR ,a))
(B) The expected stopping time of our algorithm not too much higher than the cover time of its submodular function: E, [T]
-CT(ff o)) Vh H.
(C) The expected stopping time in (a", (T) can be lower bounded in terms the total cover time: [,[""] 2 (ss) CT( o²), Vh H.
Proposition
follows by combining the above three steps. In fact,
HB
Σ heM
r(h)
Σ
(h)
CT B σ) s O a log
Σ
x(h) CTTfh
hEHf
heff
B
0 log
Σ
[T')),
S
REH
where En (h)- E,, is the expected cost of our algorithm, and Σn (h) [x[T"] is the expected cost of the optimal partially adaptive algorithm, i.c. OPT5A.
At a high level, (A) can be showed by applying Theorem 4 and observing that the marginal positive
increment of each f is S2( ( )- Step (B) is obtained from the error analysis. In the key step (C)
we fix an arbitrary 6-PAC-error partially adaptive algorithm (a,T)) and E H. Denote CT₁ = CT o), with B chosen to be 3 log 8-1, Our goal is to lower bound E, [2'] in terms of CT,, To
this aim, consider a linear program (LP). Given any d ..., dns denote d' = Σj= dy. Consider
CT
N
LP(d,t):
min Σ 1i
d'
Σ
2 = 1,
A feasible solution & can be viewed as distribution of the stopping time. When d: d(g. h; a.). the first constraint says that the total KL-divergence "collected" at the stopping time has to reach certain threshold. We show that = PA i is feasible, and the objective value of is exactly EA [T). Hence E. [T] upper bounded by the I.P-optimum I, (d, 1). Finally, we lower bound LP (d, CT 1) by Q(s CTr)), and the proof follows.

---

5 Fully Adaptive Algorithm
For ease of presentation we only consider the uniform prior version here (though our guarantees do hold for general priors). Our analysis is based on a reduction to the classical ODT problem.
Background: Optimal Decision Trees In the ODT problem, an unknown true hypothesis h" is drawn from set of hypotheses H with some known probability distribution т. There is set of known rests, each being (deterministie) mapping from H to a finite outcome space set O. Thus, when performing a test, we can rule out the hypotheses that are inconsistent with the observed outcome, hence reducing the number of alive hypotheses. Moreover, the cost c(T) of each test T is known, and the cost of a decision tree is defined to be the expected total cost of the tests selected until one hypothesis remains alive, in which case we say the true hypothesis is identified. The goal is to find valid decision tree with minimal expected cost.
Note that the ODT problem can be viewed as a special case of the fully adaptive version of our problem where there is no noise and 8 is O. Consider the following greedy algorithm GRE: let A be the alive hypotheses. Define Score(T) (T)) for each test T to be the minimal (over all possible outcomes) number of alive hypotheses that it rules out in A. Then, we select the test T with the highest thang--pr-buuee Score(T)/c(T).. This algorithm is known to be an (log apppappproiiatooon. Theorem 5 ([10)). For any ODT instance with uniform prior, GRE returns decision tree whose cost is Ollo [[) times the optimum.
Our Algorithm. We will analyze our greedy algorithm by relating to the above result. Consider the following ODT instance TODT for any given ASHT instance I. The hypotheses set and prior in IODT are the same as in I. For each action E A, let Q2 == {u(h, a)Ih H} be the mean outcomes. By Chernoff bound, we can show that when h is the true hypothesis, with high probability the mean outcome is "close" to j(h, a) when a is repeated for c(a) times. This motivates us to define a test T, H + Ω2 s.t. Ta (h) = juh, a), with cost c(a) = [s(a) log({ ]. where s(a) = min(dlgy It; a) > 0 g, E H} is the separation parameter under action a. Such a test corresponds to selecting for e(a) times in row.
For each w E Sg. abusing the notation bit, let T S denote the set of hypotheses whose outcome is w when performing To. i.c., TV = [h: p(h, a) = w}. At each step, Algorithm 2 selects an action using the greedy rule (Step 4) and then repeat for c(ā) times. Then we round the empirical mean of the observations to the closest element w in Ω2 ruling out inconsistent hypotheses, i.e., the h's with p(h, a) o w. We terminate when only one hypothesis remains alive.
Analysis We sketch proof for Theorem 2 and defer the details to Appendix C. Let h be the true hypothesis. By Hoeffding's inequality, in each iteration, with probability 1 - e log(1H)/8) = [ holds ك = ,ah", a). Since in each iteration, |H| decreases by least 1, there most | iterations. Thus by union bound, the total error is at most 6.
5
Next we analyze the cost. Let GRE be the cost of Algorithm 2 and ODT* be the optimum of the ODT instance IODT. For the sake of analysis, we consider a "fake" cost := -= log([H]/8)], which does not depend on The definition of the ODT instance IODT remains the same except that each test has uniform cost c' (as opposed to c(a)). Let e(T') and c' (T) be the costs of the greedy tree T returned by Algorithm 2 under and c' respectively. Then by Theorem 5, c'(T) I O(log HH) ODT". Note that c' < c(a) for each a since the separation parameter s is no larger than s(a) by definition. Hence,
GRE = e(T) s (T) S Olog H)) ODT".
We relate ODT* to O using the following result (see proof in Appendix C): Proposition 2. ODT* < 0 log |#l) A
The above is established by showing how to convert 8-PAC-error fully adaptive algorithm to valid
decision tree, using only tests in {Ta), and inflating the cost by a factor of O log ).ft). Combining Proposition 2 with Equation (1), we obtain GRE < O log [ log H]) OPT
Finally we remark that this analysis can easily be extended to general priors by reduction to the adaptive submodular ranking (ASR) problem [35], which captures ODT special case. One may
7

---

Algorithm 2 Fully Adaptive Algorithm
1: Input: ASHT instance A, H, D) and error å E (0, 1/2).
2: Halive +- H.
% Alive hypotheses.
3: while |Haivll= 2 2 do
4: ā arg Da minwen. allve \Ta| }.
% Greedy step.
5:
c(a) t [s(ā)= (
% # times to boost for sufficient confidence. Select à for c(ā) times consecutively and observe outcomes XI....,. Xc(a)-
6:
7:
A D Xi.
Mean outcome. % Round ja to the closest w.
8:
3 - arg migginnlă - w| w E I.).
9:
Halive + Halive nTa.
% Update the alive hypotheses.
end while
easily verify that the main theorem in [35] implies that (slightly different) greedy algorithm achieves Ollog aapproximmato for the ODT problem with general prior, test costs, and an arbitrary number of branches in each test. Thus for general prior, the same analysis goes through if we first reduce ASHT to ASR, and then replace the greedy step (Step 4 in Algorithm 2) with the greedy criterion for ASR.
6 Experiments
Although our theoretic guarantees depend on the separability parameters s (which was introduced by the boosting steps), this section, we numerically demonstrate that with small modifications our algorithms perform well when is small on both synthetic and real-world data. Our primary benchmarks are a polynomial-time policy proposed by [34] (Policy 1") and a completely random policy. To our knowledge, the policy proposed by [34] is the sfate-of-art algorithm (with theoretical guarantees) that can be applied to our problem setup. The rest of this section is organized as follows: first, we describe the benchmark policies and the implementation of our own policies. Then in Section 1, we describe the setup and results of our synthetic experiments, Finally, in Section 6.2, we test the performance of our fully adaptive algorithm on publicly-availabl dataset of genetic mutations for cancer-COSME [40, 16].
In all algorithms, we start with a uniform prior, and update our prior distribution (over the hypotheses space) each time an observation revealed. Unless otherwise mentioned, the algorithm terminates if the posterior probability of hypothesis is above the threshold 1 6.
Algorithm Details
Random Baseline At each step, an action was uniformly chosen from the set of all actions.
Partially Adaptive We implement the partially adaptive algorithm described in Section 4, with the modifications that 1) the amount of boosting is now built-in feature of the algorithm, and 2) breaking ties according to some heuristic. We describe the modified algorithm in Appendix E.
Fully Adaptive We implement our algorithm described in Section 5, with the modifications that 1) the amount of boosting is considered as a tunable parameter, 2) a hypothesis only considered to be ruled out when we are deciding which action to perform, 3) we do not boost if no action can further distinguish any hypotheses in the alive set, 4) we break ties according to some heuristic. In particular, Modification 1) addresses the issues that our fully adaptive algorithm in Section 5 boosts. Modification b) controls the error probability when we decrease the amount of boosting. Modification handles small without increasing the boosting factor. We formally describe this modified algorithm in Appendix F.
NJ Algorithm. NJ Adaptive [34] is two-phase algorithm that solves a relaxed version of our minimize a weighted sum of the expected number of tests and the
problem, where the objective likelihood of identifying the wrong hypothesis, i.e., min B(T) + Le, where T is the termination time, the penalty for wrong declaration, and e the probability of making that wrong declaration. The problem was formulated as Markov decision process whose state space is the posterior distribution over the hypotheses. In Phase I, which lasts as long as the posterior probability of all hypotheses is below carefully chosen threshold, the action is sampled according distribution that is selected
Policy 2 in [34] does not have asymptotic guarantees and not considered in our experiments.

---

5035
Average Numiber of Samples
Average Number Sammpees
Under Partalty Adsptie
00
Average Number di Samplee
Uinder Fully Adajevv
80
70%
83 1..0%
60
09 00.0%
50%
55
40%
50.056
30%
0.70
0.75
0.50 0.85 Accuracy
0.50
0.95
Average Number Samples Under Ng Partially Adaptive
Number Samples Under Nj Adaptive
Figure 1: Comparison of our fully and partially adaptive algorithms with NJ Adaptive, NJ Partially Adaptive and Random Baseline on synthetic data. The average number of samples is normalized with respect to the largest number of sample required in Random Baseline. Left: each dot corresponds to the average performance of 100 randomly generated instances each averaged over 2,000 replications. Middle and Right: contains the same 100 instances in the left figure. Each dot corresponds to one instance and each averaged over 2,000 replications. Middle and Right: the average accuracies of those 100 instances in all algorithms equal to 0.97.
to maximize the minimum expected KL divergence among all pairs of outcome variables. Phase 2, when one of the hypotheses has posterior probability above the chosen threshold, the action is sampled according to a distribution selected to maximize the minimum expected KL divergence between the outcome of this hypothesis and the outcomes of all other hypotheses. This threshold was optimized over in both synthetic and roal-world experiments. The algorithm stops if the posterior of hypothesis is above the threshold L NJ Partially Adaptive contains only the Phase policy.
6.1 Synthetic Experiments
Parameter Generation and Setup Figure 1 summarizes the results of our partially and fully adaptive experiments on synthetic data. Both figures were generated with 100 instances: each with 25 hypotheses and 40 actions. The outcome of each action under each hypothesis is binary, i.e., the D)(h.a)s are the Bernoulli distributions, where p(a, h) were uniformly sampled from the [0.1] interval. Each instance was then averaged over 2,000 replications, where a "ground truth" hypothesis was randomly drawn. The prior distribution, æ,, was initialized to be uniform for all runs. On the horizontal axis, the accuracies of both algorithms were averaged over these 100 instances, where the accuracy calculated as the percentage of correctly identified hypotheses among the 2,000 replications. On the vertical axis, the number of samples used by the algorithm is first averaged over the 2,000 replications and then averaged over the 100 instances.
Results In Figure 1 (left). we observe that 1) the performance of our fully adaptive algorithm dominates those of all other algorithms, 2) our partially adaptive algorithm outperforms all other partially adaptive algorithms, and 3) the performance of adaptive algorithms outperform those of partially adaptive algorithms. The threshold for entering Phase 2 policy in NJ Adaptive set to be 0.1. Indeed, we observe that NJ Adaptive outperforms NJ Partially Adaptive. In Figure (middle), equals to 0.05 for both NJ Partially Adaptive and Partially Adaptive. We observe that our partially and fully adaptive algorithms outperform NJ Partially Adaptive and NJ Adaptive instance wise by large margins respectively in Figure middle and left.
6.2 Real- World Experiments
Problem Setup Our real-world experiment is motivated by the design of DNA-based blood tests to detect cancer. In such test, genetic mutations serve as potential signals for various cancer types, but DNA sequencing is, even today, expensive enough that the 'amount' of DNA that can be sequenced single test is limited if the test is to remain cost-effective. For example, one of the most-recent versions of these tests [15] involved sequencing just 4,500 addresses (from among 3 billion total addresses the human genome), and other tests have had similar scale (e.g., [38, 11, 37J). Thus, one promising approach to the ultimate goal of cost-effective test is adaptivity.

---

-3- NJ Partally Adagtin Portady Adaptiive
20
Average Number Samples
300
Aceppiive
Scnsitiity
Specfiiity
bresat
1266
26
0
0.9717
0.9963
lung
1130
0.9492
0 0.9963
250
True label
co rocttal
0.9767
9968
1055
0.8792
0.9933
200
1195
0
0,9959
0.9983
stomach
33
1161
0.9842
0. 0.9908
liver
1171
0.9758
0.9993
250
evary
Intast
colon rectal
aesoptagess
menomaa
ctomach
owary
Accuracy
Predicted
Figure 2: Comparison of our partially and fully adaptive algorithms with those of NJ's on real- world data COSMIC. Left: each point is averaged over 9,600 replications. The error bars are the 95 percentage confidence intervals for the estimated means. Middle: the confusion matrix of Fully Adaptive where the algorithm accuracy equals to 0.97, and each row sums up to I 1,200. Left: the sensitivity and specificity our algorithm (middle) for each cancer type.
Our experiments are a close reproduction of the setup used by [15] to identify their 4,500 addresses. We genetic mutation data from real cancer patients: the publicly-available catalogue of somatic mutations in cancer (COSMIC) [40, 16], which includes the de-identified gene-screening panels for 1,350,015 patients. We treated 8 different types of cancer (as indicated in [15]) as the 8 hypotheses, and identified 1,875,408 potentially mutated genetic addresses. To extract the tests, we grouped the the genetic addresses within an interval of 45 (see [15] for the biochemical reasons behind this choice), resulting in 581,754 potential tests. We then removed duplicated tests (i.e., the tests that share the same outcome distribution for all 8 cancer types), resulting in 23,135 final tests that we consider in our experiments. Note that the duplicated tests can be removed here since they are exchangeable in our problem setting. However, the set of final tests might be different for a different set of ground-truth cancer types. From the data, we extracted a " gground-truth' table of mutation probabilities containing the likelihood of mutation any of the 23, 135 genetic address intervals being found in patients with any of the 8 cancer types. This served as the instance for our experiment. The majority of the mutation probabilities in our instances was either zero or some small positive number. To calculate the KL divergence between these probabilities, we replace zero with the number 10-10 10 in our instance.
Results. Although in reality, all patients have different priors for having different cancers, in our experiments, we assume that the truth hypothesis (cancer type) was drawn uniformly, and we initialize uniform priors for all algorithms. Similar to Figure 1. in Figure 2 (left) we observe that 1) the performance of our algorithm dominates those to the rest algorithms, and 2) our partially adaptive algorithm outperforms NJ Partially Adaptive. However, unlike Figure 1, we observe that NJ Adaptive underperforms Partially Adaptive when the accuracies are low on this instance. The threshold for entering Phase 2 policy, in NJ Adaptive was set to be 0.3. Since Phase policy is less efficient than Phase 2 policy, we observe that the performance of NJ Adaptive is convex with respect to r r-when is small, the algorithm is more likely to alternate between Phases I and 2 policies and when is large we spend more time in Phase I policy. As a result, we observe that variance of NJ Adaptive is relatively high when compared with those of other algorithms. Note that due to the nature of the sparsity of our instance, the performance the random baseline was very poor when compared with these of NJ Adaptive and Fully Adaptive and thus excluded. Figure 2 (middle) is the confusion matrix corresponding to our fully adaptive algorithm where the algorithm accuracy equals to 0.97, and Figure 2 (right) corresponds to the sensitivity and specificity of our algorithm for each cancer type (in the same ordering as) in the middle figure.
7 Conclusions
In this work provided the first approximation guarantees for the ASHT problem and demonstrated the efficiency of the proposed algorithms through numerical experiments on genetic mutation data. Under the current framework, it is challenging to improve the s dependence on in the approxi- mation factors, since we have to boost each action for - times to apply the concentration bounds. However, in our numerical experiments, by reducing the number of times for boosting, achieved better performance when compared with existing heuristics.
10

---

Acknowledgments and Disclosure of Funding
We would like thank the anonymous reviewers for their careful reviews, and we declare no conflict of interests.
References
[1] M. Adler and B. Heeringa. Approximating optimal binary decision trees. In Approximation, Ran- domization and Combinatorial Optimization. Algorithms and Techniques, pages 1-9. Springer, 2008.
[2] E. M. Arkin, H. Meijer, J. S. Mitchell, D. Rappaport, and S. S. Skiena. Decision trees for geometric models. International Journal of Computational Geometry & &Applications, 8(03):343- 363, 1998.
[3] Armitage. Sequential analysis with more than two alternative hypotheses, and its relation to discriminant function analysis. Journal of the Royal Statistical Society. Series B (Methodologi- cal), 12(1):137-144, 1950.
[4] Awasthi, M. F. Balcan, and P. M. Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017
[5] Y. Azar and I. Gamzu. Ranking with submodular valuations. In Proceedings of the twenty- second anmual ACM-SIAM symposium on Discrete Algoritimss, pages 1070-1079. SIAM, 2011.
[6] Y. Azar, I. Gamzu, and X. Yin. Multiple intents re-ranking. In Proceedings of the forty-first anmual ACM symposium on Theory of computing, pages 669-678. ACM, 2009.
[7] M. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning, In Machine Learning, Proceedings of the Twenty-Third International Conference (ICML 2006), Pittsburgh, Pennsylva- nia, USA, June 25-29, 2006, pages 65-72, 2006.
[8] S. Bubeck, R. Munos, and G. Stoltz. Pure exploration in multi-armed bandits problems. In International conference on Algorithmic learning theory, pages 23-37. Springer, 2009.
[9] R. M. Castro and R. D. Nowak. Minimax bounds for active learning. In International Conference on Computational Learning Theory, pages 5-19. Springer, 2007.
[10] V. T. Chakaravarthy, V. Pandit, Roy, and Sabharwal. Approximating decision trees with multiway branches. In International Colloquium on Automata, Languages, and Programming, pages 210-221. Springer, 2009.
[11] K. A. Chan, J. K. Woo, A. King, B. C. Zee, W. J. Lam, S. L.. Chan, S. W. Chu, C. Mak, O. Tse, S. Y. Leung, al. Analysis of plasma epstein- barr virus dna to screen for nasopharyngeal cancer. New England Journal of Medicine, 531-5522 2017.
[12] S. Chawla, E. Gergatsouli, Y. Teng, C. Tzamos, and R. Zhang. Learning optimal search algorithms from data, arXiv preprint arXiv: 1.0011631.,,,,.... 2019.
[13] Y. Chen, S. H. Hassani, A. Karbasi, and A. Krause. Sequential information maximization: When is greedy netrmoptimal? In Conference on Learning Theory, pages 338-300 088-363,42 2015.
[14] H. Chernoff. Sequential design of experiments. The Annals of Mathematical Statisties, 30(3):755-77) 7700 1959.
[15] J. D. Cohen, L. Li, Y. Wang, C. Thoburn, B. Afsari, L. Danilova, C. Douville, A. A. Javed, Wong, A. Mattox, et al. Detection and localization of surgically resectable cancers with multi-analyte blood test. Science, 339(6378) 9300 2018.
[16] Cosmic, Cosmic catalogue of somatic mutations in cancer, Sep 2019.
[17] Dasgupta. Analysis greedy active learning strategy. In Advances in neural information processing systems, pages 337-344, 2005.

---

[18] D. Du, F. K. Hwang, and F. Hwang. Combinatorial group testing and its applications, volume 12. World Scientific, 2000.
[19] E. Even-Dar, S. Mannor, and Y. Mansour. Pac bounds for multi-armed bandit and markov decision processes. In International Conference Computational Learning Theory, pages 255-270. Springer, 2002.
[20] K. Gan, A. A. Li, C. Lipton, and S. Tayur. Causal inference with selectively deconfounded data. arXiv preprint arXiv:2002.11096 2020.
[21] D. Golovin and A. Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res., 42:427-45 --27,486,440 2011.
[22] A. Guillory and J. A. Bilmes. Simultaneous learning and covering with adversarial noise. In ICML. 2011.
[23] S. Hanneke et al. Theory of disagreemeent-based active learning. Foundations and Trends R in Machine Learning, 7(2-3):111-309, 2014.
[24] S. Hanneke and L. Yang. Minimax analysis of active learning. The Journal of Machine Learning Research, 3343:3337336 2015.
[25] Im, V. Nagarajan, and R. V. D. Zwaan. Minimum latency submodular cover. ACM Transac- tions on Algorithuss (TALG), 13(1):13, 2016.
[26] S. Jia, F. Navidi, V. Nagarajan, and R. Ravi. Optimal decision tree with noisy outcomes. Advances in neural information processing systems, 2019.
[27] G. Kamath and C. Tzamos. Anaconda: A non-adaptive conditional sampling algorithm for distribution testing. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 679-693. SIAM, 2019.
[28] S. Kosaraju, T. M. Przytycka, and R. Borgstrom. On an optimal split tree problem. In Workshop on Algorithms and Data Structures, pages 157-168. Springer, 1999.
[29] A. Krause, H. B. McMahan, C. Guestrin, and A. Gupta. Robust submodular observation selection. Journal of Machine Learning Research, 9(Dcc):2761-2801 2008.
[30] H. Laurent and R. L. Rivest. Constructing optimal binary decision trees is np-complete. Information processing letters, 5(1):15-17, 1976.
[31] G. Lorden. Nearly-optimal sequential tests for finitely many parameter values. The Annals of Statistics, pages 1-21, 1977.
[32] S. Mannor and J. N. Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623-64,, 2004.
[33] M. Mitzenmacher and E. Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
[34] M. Naghshvar and T. Javidi. Active sequential hypothesis testing. The Annals of Statistics, (1(6):773-27388 2013.
[35] Navidi, Kambadur, and V. Nagarajan. Adaptive submodular ranking and routing. Operations Research, 2020.
[36] R. D. Nowak. Noisy generalized binary search. In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009, Pro- ceedings of meeting held 7-10 December 2009, Vancouver, British Columbia, Canada., pages 1366-1374 2009.
[37] J. Phallen, M. Sausen, V. Adleff, A. Leal, C. Hruban, J. White, V. Anagnostou, J. Fiksel, Cristiano, Papp, et al. Direct detection of early-stage cancers using circulating tumor dna. Science translational medicine, 9(00), 2017.
12

---

[38] P. Razavi, B. T. Li, W. Abida, A. Aravanis, B. Jung, R. Shen, C. Hou, I. De Bruijn, S. Gnerre, R. S. Lim, al. Performance high-intensity 508-gene circulating-uume dna (ctdna) assay in patients with metastatic breast, lung, and prostate cancer. J. Clin. Oncol, 35, 2017.
[39] B. Settles. Active learning literature survey. Technical report, University of Masconsin-Madison Department of Computer Sciences, 2009.
[40] G. Tate, S. Bamford, H. C. Jubb, Z. Sondka, D. M. Beare, N. Bindal, H. Boutselakis, C. G. Cole, C. Creatore, E. Dawson, et al. Cosmic: the catalogue of somatic mutations in cancer. Nucleic acids research, 470D1):9911-D947, 2019.
[41] R. Vershynin. High-diieensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[42] A. Wald. Sequential tests of statistical hypotheses. The annals of mathematical statistics, 1662):17--18, 1945.
[43] Y. Wang and A. Singh. Noise-adaptive margin-based based active learning and lower bounds under tsybakov noise condition. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 30, 2016.
13


Reviews:
[{"review_id": "iqR-7w32hiZ", "reviewer": "Reviewer_ACVf", "summary": "The problem considered in the paper regards the identification of the \"correct one\" (or true) hypothesis, chosen from a set of candidate hypotheses according to some given prior distribution. The identification works by applying tests/actions taken from a given set. The test returns a probabilistic result, according to a distribution that depends on the test and the hypothesis. The problem is to choose the sequence of tests so that from the results the correct hypothesis can be identified with probability bounded by some given parameter delta. \nThe model is a variant of the more classical combinatorial identification problems, where the outcome of the tests is a deterministic value. In fact, as, admittedly, the authors pointed out the problem remains inherently combinatorial and the solution provided here are tightly connected to the known approximation solutions in the non-statistical variants. The basic strategy is to apply the latter and repeat each test enough time to identify a signle outcome that have statistical significance. Then, proceed according to the deterministic strategy. Standard and some new statistical analytical tools are effectively employed to guarantee that from the random outcome a deterministic result is chosen that guarantess the separation (in the fully adaptive case) or coverage (in the nonadaptive case) leading to the overall cost bound.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Originality: This is an interesting generalization of some well-studied problems (e.g. Active learning and Optimal Decision Trees) that are relevant to the NeurIPS community.  The ASHT variant considered here is well motivated by applications like the cancer/genomics-data biological scenario considered in the experiment section. The main contribution claimed by the authors is mainly of theoretical nature and consists in the first approximation bounds for this version of the problem, in both the adaptive and semi-adaptive case. \n\nStrength: The authors present approximation guarantees for the Active Sequential Hypothesis Testing Problem which depend logarithmically in |H| and the inverse of the separability parameter of the instance, a parameter that describes the minimum positive distance between distinct outcome distributions associated with some action. \n\nWeakness: There are some important issues with one of the main claims that should be clarified by the authors. Theorem 5 (which is taken from [Chakaravarthy et al. ICALP2009] does not appear to be used in the correct way in the present paper for a couple of reasons: (i) the ICALP result is about the variant of the ODT problem where tests have no costs, while in this paper costs appear to be necessary to model the number of times a test is used to achieve statistical significance; (ii) the authors claim that the result is for arbitrary distribution, but the part that leverage on the ICALP result cannot be extended without referring to different model, which might necessitate a different connection between  the ASHT and the \"average case - with variable test-costs\" variant of the ODT problem. \n\nClarity: In general the paper is clearly written. The only vague parts are those that concern the issue above. I think the authors should give further details to clarify how, besided the limitation of the ICALP paper, they manage to close the gaps between the model of ODT they need to support the simplified analysis of ASHT that is only based on [Chakaravarthy et al. ICALP2009] result. \n\nOverall, I consider the problem and the claimed result interesting. My evaluation is set just below acceptance because of the above doubts, that I hope the authors will be able to clarify. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work does not pose potential negative societal impact. The authors addressed the main limitations in the final section. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "aMkOhQKz1-n", "reviewer": "Reviewer_qxXc", "summary": "This work presents approximation algorithms for the problem of active sequential hypotheses testing. The proposed algorithms leverage a connection with submodular function ranking that is novel and interesting. Both \"fully adaptive\" and \"partially adaptive\" algorithms are given, with different features and guarantee. The experimental evaluation of (minor variants) of the proposed algorithms shows that they seem to outperform existing approaches. ", "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": "## Comments after response\n\nI thank the Authors for their response. I read it carefully, as I did the comments from other Reviewers and the responses to them. \nI'm keeping my score as it is, but I think the paper should be accepted, even if it just marginally above the threshold.\n\n## Original Review\n\nThis work is the first proposal of algorithms offering quality guarantees for the studied problem. While the guarantees are not particularly strong, and the computational complexity ($O(|A||H|)$) is quite high, the work seems solid and it opens a new direction. It also shows interesting connection with submodular function ranking and the existing approximation algorithms for it. The use of \"boosting\" (repeating an action multiple times) is also a nice touch, although it seems to be the point where theory and practice diverge the most. The experimental evaluation seems quite convincing, with the exception of an issue in the selection of tests to consider (detailed below).\n\nThe paper is generally well written. There is clearly an effort in carefully explaining the connections with other problems and the general intuition about the proposed approach. \n\n## Other comments\n\nLines 77-83: this part feels a bit too informal, given that it describes very important quantities such as the $\\delta$-PC-error and what is meant by \"sufficiently high\" confidence. While these concepts are explained in words, a mathematical expression may ground them better.\n\nLine 185: when the reader gets here, they have no idea of what is meant by \"boosting\".\n\nLine 347: why can one remove all these duplicated tests? They may share the same outcome distribution for all 8 cancer types on this data, but not in general, so it is unclear whether one can really filter them out. But maybe it is allowed (i.e., no guarantees whatsoever are lost). If so, it should be made quite clear\n\n377: \"approximationfactors\" -> \"approximation factors\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The Authors do a pretty good job at assessing the *algorithmic* limitations of the work.\n\nThis Reviewer does not see any potential negative societal impact that is *specific* to this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "Yes", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "EBwNvKCi2ec", "reviewer": "Reviewer_MCYe", "summary": "The authors consider the problem \"active sequential hypothesis testing\", where the learner finds the true hypothesis by observing the noisy outcomes of actions. In particular, they study the ASHT under two types of adaptivity: partial and full. For both these settings, they propose greedy algorithms that run efficiently and provide an approximate solution. ", "questions": "", "limitations": "", "rating": 7, "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": "Things that I like about the paper:\n1) The problem considered in this paper is generic and captures a number of well-known problems; I find this generalization interesting.\n2) The paper is well written and the authors do a good job in placing their contribution with respect to the related work.\n3) The paper is a nice mixture of both theory and practice. The experiments section is well done and I enjoyed reading the performance of the proposed algorithm on real data.\n\n\nFew concerns/suggestions:\n1) Why is assumption 1 needed in general? Some intuition on why is it hard to overcome assumption 1 would be helpful.\n2) One of the significances of the approximation ratios is that they are independent of the number of actions and in applications where the action space is massive the presented algorithms are useful. However, note that the algorithm runs in O(|A|) time (hiding other dependencies)  and therefore might be impractical in the aforementioned applications. I am aware that removing the dependency of O(|A|) in run time might not be possible but it would be interesting to replace the |A| term in the running time with some other structural property of A. For instance, with the term $O_{A}$, where $O_{A}$ is the time to perform a particular action on A and then mention that $O_{A}<=A$ in the worst case and provide examples/applications where $O_{A}$ would be much smaller.\n3) Talk about what is the value of $s$ (Definition 1) in typical applications. I see that the first few sentences in the experiments section handle this concern, it would be nice to add some of it when $s$-separation is defined.\n4) If possible, mention approximation ratios (instead of just No and Yes) in Table 1.\n5) Consider other benchmarks in the experiments or explain why you don't include them.\n6) When mentioning theory results, talk about the challenges faced in achieving these results. For instance, the difficulty in the analysis and how you improve previous works to overcome these difficulties. There are few sentences in the introduction that handle this concern, but I would like to see more sentences in the early stages of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do a sufficient job of addressing the limitations of their work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of active sequential hypothesis testing, where a sequence of actions are adaptively chosen to find the best hypothesis without testing all of them. The paper considers the important novel setting when the test returns a result that is stochastic, and proposes a greedy approach by linking the problem to submodular function ranking. Theoretical analysis and empirical results on the COSMIC cancer data are presented.

Three expert reviewers carefully considered the strengths and weaknesses of the paper. All reviewers agree that the problem setting is important, and the link to submodularity and the resulting greedy algorithm is interesting. They identified several issues with clarity and precision in the paper, which the authors tried to address during the rebuttal period, which the reviewers appreciated (and changed their scores). Post rebuttal, the reviewers had a brief discussion and agreed that the paper is a good one, and would be a valuable contribution to the NeurIPS program. The authors are strongly advised to take the reviewer feedback into account in the final version. I am pleased to be able to recommend this paper to be accepted to NeurIPS. Congratulations!
Decision: Accept (Poster)