Greedy Approximation Algorithms for Active Sequential Hypothesis Testing
Year: 2022

Abstract:
In the problem of active sequential hypothesis testing (ASHT), a learner seeks to identify the 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 > 0, the goal is to sequentially select the fewest number of actions so as to identify the true hypothesis with probability at least 1 . 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.

heading: 1 Introduction
text: Consider the problem of learning the true hypothesis from among a (potentially large) set of candidate hypotheses H . Assume that the learner is 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 to 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 a 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 an 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-trivial multiplicative factor of the corresponding optimal costs. Most notably, these
⇤Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
approximation guarantees are independent of |A| (contrast this with the trivially-achievable guarantee of O(|A|)) and logarithmic in |H| (the optimal cost itself is often ⌦(|H|)). Our results rely on 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—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 a manner that would map directly to ASHT—this extension is among our contributions.
Related Work Our work is closely related to three streams of research. Table 1 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, a 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 to 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 algorithms for minimizing cover time are known in the noiseless setting [28, 1, 2]. When the outcome is stochastic, [21] proposed a framework for analyzing algorithms under the adaptive submodularity assumption. However, their assumption does not hold for many natural setups including ASHT. [13] considered a variant using ideas from the submodular 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.

heading: 2 Model
text: We begin by formally introducing the problem. Let H be a 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 a known prior distribution ⇡ over H .
Let A be the set of available actions. Selecting an action yields a random outcome drawn independently from a distribution within a given family D = {D✓}✓2⇥ of distributions parameterized by
⇥ ✓ R. We are given a function µ : H ⇥A! ⇥ such that if h 2 H is the underlying hypothesis and we select action a 2 A, then the random outcome is drawn independently from distribution Dµ(h,a).2
An instance of the active sequential hypothesis testing problem is then fully specified by a tuple: (H,A,⇡, µ,D). The goal is to sequentially select actions to 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 to the Bayesian prior and the random outcomes. The notion of sufficiently high confidence is encoded by a parameter 2 (0, 1), and requires that under any true h 2 H , the probability of erroneously identifying a different hypothesis is at most . An algorithm which satisfies this is said to have achieved -PAC-error. We focus on two important families of D✓’s: the Bernoulli distribution Ber(✓) and the Gaussian distribution N(✓, 2) where 2 is a known constant (with respect to ✓). By re-scaling, without loss of generality we may assume 2 = 1. We require two additional assumptions to state our guarantees. The first assumption is needed for relating the sub-gaussian norm to the KL-divergence, in the partially adaptive version. It ensures that the parameterization ⇥ is a meaningful one, in the sense that if ✓, ✓0 2 ⇥ are far apart, then the distributions D✓ and D✓0 are also “far” apart (as measured by KL divergence). Assumption 1 is satisfied for Ber(✓) when ✓ 2 [✓min, ✓max] for some constants 0 < ✓min < ✓max < 1, and for N(✓, 1) where ✓ lies in some bounded set in R. Assumption 1. There exist C1, C2 > 0 such that for any ✓, ✓0 2 ⇥, we have C1 ·KL(D✓, D✓0)  (✓ ✓0)2  C2 ·KL(D✓, D✓0), where KL(·, ·) 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 2 H where g 6= h, there exists a 2 A with µ(g, a) 6= µ(h, 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 µ(g, a) = µ(h, a). 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 2 H and any action a 2 A, define d(g, h; a) = KL
Dµ(g,a), Dµ(h,a) .
Definition 1 (s-separated instance). An ASHT instance is said to be s-separated, if for any a 2 A and g, h 2 H , d(g, h; a) is either 0 or at least s.
Note that in real-world applications, the parameter s 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 a decision tree,3 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 ( , T ) is specified by a fixed sequence of actions = ( 1, 2, ...), with each i 2 A, and a stopping time T . In particular, under any true hypothesis h⇤ 2 H and for any t 1, the event {T = t} is independent of the outcomes of actions t+1, t+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 is 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 are many scenarios (e.g., content recommendation and web search [6]) where it is desirable to 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 or fully adaptive. In both cases, our goal is to design fast approximation
2In this noisy setting, an action can (and often should) be played for multiple times. 3By approximating D✓’s with discrete distributions, we may assume each node has a finite number of
children.
algorithms—ones that are computable in polynomial4 time and that are guaranteed to incur expected costs at most within a 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 a number of well-known problems related to decision-making for learning including best-arm identification for multi-armed bandits [8, 19, 32], group testing [18], and causal inference [20], just to name a few.

heading: 3 Our Approximation Guarantees
text: We are now prepared to state our approximation guarantees (the corresponding greedy algorithms will be defined in the next two sections). Let OPTPA (resp. OPT FA
) denote the minimal expected cost of any partially adaptive (resp. fully adaptive) algorithm that achieves -PAC-error. Theorem 1. Given an s-separated instance and any 2 (0, 1/2), there exists a polynomial-time partially adaptive algorithm that achieves -PAC-error with expected cost O ⇣ s 1 ⇣ 1 + log1/ |H| ⌘ log s 1|H| log 1 ⌘ OPT PA .
To help parse this result, if is on the order of |H| c for some constant c, then the approximation factor becomes s 1(log s 1 + log |H|+ c log log |H|). Theorem 2. Given an s-separated instance and any 2 (0, 1/2), there exists a polynomial-time fully adaptive algorithm that achieves -PAC-error with expected cost O s 1 log |H| 1 log |H| OPT FA .
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 an approximation factor of O(|A|) is always trivially achievable (by cycling through the actions), instances where |A| is large are arguably the most interesting problems.
2. Dependence on |H|, and s: For fixed s and , these are the first polylog-approximations for both partially and fully adaptive versions. Further, for the partially adaptive version, the dependence of the approximation factor on is O(log log 1) when 1 is polynomial in |H|, improving upon the naive dependence O(log 1). This is crucial since is often needed to be tiny in practice.
3. Greedy runtime: While we have only stated in our formal results that our approximation algorithms can be computed in poly(|A|, |H|) time, the actual time is more attractive: O(|A||H|) for selecting each action. In contrast, the heuristic that we will compare against in the experiments requires solving multiple ⌦(|A||H|2)-sized linear programs.
Despite their similar appearances, Theorems 1 and 2 rely on fundamentally different algorithmic techniques and thus require different analyses. In Section 4, we propose an algorithm inspired by the submodular function ranking problem, which greedily chooses a sequence of actions according to a carefully chosen “greedy score.” We then sketch the proof of Theorem 1. In Section 5, we introduce our fully adaptive algorithm and sketch the proof of Theorem 2.
Finally, by proving a structural lemma (in Appendix D), we extend the above results to a special case 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 2 (0, 1/4), for both the partially and fully adaptive versions, there exist polynomial-time -total-error algorithms with expected cost O s 1 1 + |H| 2 log |H| 1 log |H| times the optimum.

heading: 4 Partially Adaptive Algorithm
text: This section describes our algorithm and guarantee for the partially adaptive problem. We first review necessary background from a related problem, and then state our algorithm (Algorithm 1). Finally, we
4Throughout this paper, polynomial time refers to polynomial in |H|, |A|, s 1, 1
sketch the proof of the following more general version of Theorem 1 (complete proof in Appendix B):
Proposition 1. Let 2 (0, 1 4 ] and consider finding the optimal -PAC error algorithm. Given any boosting intensity ↵ 1 and coverage saturation threshold B 2 (0, 1 2 log 1], RnB(B,↵) (as defined in Algorithm 1) produces a partially adaptive algorithm with error |H| exp ( ⌦ (↵B)) and expected cost O ⇣ ↵ s log |H|B s ⌘ OPT PA .
By setting ↵ = 1 + log1/ |H| and B = 12 log 1 , we immediately obtain Theorem 1.
Background: Submodular Function Ranking In the SFR problem, we are given a ground set U of N elements, a family F of non-decreasing submodular functions f : 2U ! [0, 1] with f(U) equaling 1 for every f 2 F , and a weight function w : F ! R+. For any permutation = (u1, ..., uN ) of U , the cover time of f is defined as CT(f, ) = min{t : f({u1, ..., ut}) = 1}. The goal is to find a permutation of U with minimal cover time P f2F w(f) · CT(f, ). We will use the following greedy algorithm, called GRE, in [5] as a subroutine. The sequence is initialized to be empty and is constructed iteratively. At each iteration, let S be the elements selected so far. GRE selects the element u with the maximal coverage, defined as Cov(u;S) :=P
f2F :f(S)<1 w(f) · (f(S [ {u}) f(S)) / (1 f(S)) .
Theorem 4 ([25]). For any SFR instance, GRE returns a sequence whose cost is O(log 1" ) times the optimum, where " := min f(S [ {u}) f(S) > 0 : S 2 2U , u 2 U, f 2 F .
Challenge. To motivate our algorithm, consider first the following simple idea: “boost” (or repeat) each action enough, and hence reduce the problem to a deterministic problem Pdet. We then show that the existing technique (submodular function ranking for partially adaptive and greedy analysis for ODT for fully-adaptive) returns a policy with cost O(log |H|) 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( 1s log |H| ). This analysis was in fact our first attempt. However, there are at least two issues that one runs into:
1. This analysis only compares the policy’s cost with the no-noise optimum, but our focus is the -noise optimum. In particular, the simpler analysis implicitly assumes that the -noise optimum is at least ⌦( 1s log |H| ) times the no-noise optimum, which is not necessarily true.
Moreover, it is challenging to analyze the gap between the no-noise optimum and the -noise optimum.
2. This simple analysis provides a weaker guarantee than ours in terms of : it yields a factor of log 1 , as opposed to the log log 1
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 assume each action is selected for at most M = M( , s, |H|) = O( |H| 2
s log |H| ) times. In fact,
Observation 1. Let eA be the (multi)-set obtained by creating M copies of each a 2 A. Then there exists a sequence of | eA| actions, such that h⇤, the true hypothesis, has the highest posterior with probability 1 after performing all actions in .
Thus, given eA, we define fBh : 2 eA ! [0, 1] for any coverage saturation level B > 0 and h 2 H as fBh (S) = 1 |H| 1 P g2H\{h} min{1, 1 B P a2S d(g, h; a)}. One can verify that fBh is monotone and submodular. Our algorithm computes a nearly optimal sequence of actions using the greedy algorithm for SFR, and creates a number of copies for each of them. Then we assign a timestamp to each h 2 H , and scan them one by one, terminating when the likelihood of one hypothesis is dominantly high.
Proof Sketch for Proposition 1. We sketch a proof and defer the details to Appendix B. The error analysis follows from standard concentration bounds, so we focus on the cost analysis. Suppose
Algorithm 1 Partially Adaptive Algorithm: RnB(B,↵) 1: Parameters: Coverage saturation level B > 0 and boosting intensity ↵ > 0. 2: Input: ASHT instance (H,A,⇡, µ,D) 3: Initialize: ;, ̃ ; % Store the selected of actions. 4: For t = 1, 2, ..., | eA| do % Rank: Compute a sequence of actions. 5: S { (1), ..., (t 1)}. % Actions selected so far. 6: For a 2 eA, % Compute scores for each action.
Score(a;S) X
h:fBh (S)<1
⇡(h) fBh (S [ {a}) fBh (S)
1 fBh (S) .
7: (t) argmax{Score(a;S) : a 2 eA\S}. % Select the greediest action. 8: For t = 1, 2, ..., |Ã|: % Boost: Repeat each action in for ↵ times. 9: For i = 1, 2, ...,↵:

heading: 10: ̃
text: ↵(t 1) + i
(t).
11: For t = 1, ...,↵|Ã|: 12: Select action ̃(t) and observe outcome yt. 13: If t = ↵ · CT(fBh , ) for some h 2 H: % If t is the timestamp for some h. 14: For g 2 H\{h}: 15: ⇤(h, g) Qt i=1 Ph,̃(i)(yi)/Pg,̃(i)(yi). % Compute the likelihood ratio. 16: If log⇤(h, g) ↵B/2 for all g 2 H\{h}, then Return h. % Hypothesis identified.
↵ > 0, 2 (0, 1 4 ), and B 2 (0, 1 2 log 1 ). Let ( ⇤, T ⇤) be any optimal partially adaptive algorithm, and let ( , 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: P h2H ⇡(h) · CT(fBh , )  O ⇣ log |H|B s ⌘P h2H ⇡(h) · CT(fBh , ⇤).
(B) The expected stopping time of our algorithm is not too much higher than the cover time of its submodular function: Eh[T ]  ↵ · CT(fBh , ), 8h 2 H. (C) The expected stopping time in ( ⇤, T ⇤) can be lower bounded in terms of the total cover time: Eh[T ⇤] ⌦(s) · CT(fBh , ⇤), 8h 2 H.
Proposition 1 follows by combining the above three steps. In fact, X
h2H ⇡(h) · Eh[T ]  ↵
X h2H ⇡(h) · CT(fBh , )  O
✓ ↵ log
|H|B s
◆ X
h2H ⇡(h) · CT(fBh , ⇤)
 O ✓ ↵
s log |H|B s
◆ X
h2H ⇡(h) · Eh[T ⇤],
where P h ⇡(h) · Eh[T ] is the expected cost of our algorithm, and P
h ⇡(h) · Eh[T ⇤] is the expected cost of the optimal partially adaptive algorithm, i.e. OPTPA .
At a high level, (A) can be showed by applying Theorem 4 and observing that the marginal positive increment of each fBh is ⌦( s |H|B ). Step (B) is obtained from the error analysis. In the key step (C) we fix an arbitrary -PAC-error partially adaptive algorithm ( , T ) and h 2 H . Denote CTh = CT (fBh , ), with B chosen to be 1 2 log 1. Our goal is to lower bound Eh[T ] in terms of CTh. To this aim, consider a linear program (LP). Given any d1, ..., dn, denote di = Pi j=1 dj . Consider
LP (d, t) : ( min z NX
i=1
i · zi
NX
i=1
dizi CTh 1X
i=1
di, NX
i=1
zi = 1, z 0. )
A feasible solution z can be viewed as a distribution of the stopping time. When di = d(g, h; ai), the first constraint says that the total KL-divergence “collected” at the stopping time has to reach a certain threshold. We show that zi = Ph[T = i] is feasible, and the objective value of z is exactly Eh[T ]. Hence Eh[T ] is upper bounded by the LP-optimum LP ⇤(d, t). Finally, we lower bound LP ⇤(d,CTh 1) by ⌦(s · CTh), and the proof follows.

heading: 5 Fully Adaptive Algorithm
text: 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 a set of hypotheses H with some known probability distribution ⇡. There is a set of known tests, each being a (deterministic) 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 a 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 is 0. Consider the following greedy algorithm GRE: let A be the alive hypotheses. Define Score(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 “bang-per-buck” Score(T )/c(T ). This algorithm is known to be an O(log |H|)-approximation. Theorem 5 ([10]). For any ODT instance with uniform prior, GRE returns a decision tree whose cost is O(log |H|) times the optimum.
Our Algorithm. We will analyze our greedy algorithm by relating to the above result. Consider the following ODT instance IODT for any given ASHT instance I. The hypotheses set and prior in IODT are the same as in I. For each action a 2 A, let ⌦a := {µ(h, a)|h 2 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 µ(h, a) when a is repeated for c(a) times. This motivates us to define a test Ta : H ! ⌦a s.t. Ta(h) = µ(h, a), with cost c(a) = ds(a) 1 log(|H|/ )e, where s(a) = min{d(g, h; a) > 0 : g, h 2 H} is the separation parameter under action a. Such a test corresponds to selecting a for c(a) times in a row.
For each ! 2 ⌦a, abusing the notation a bit, let T!a ✓ H denote the set of hypotheses whose outcome is ! when performing Ta, i.e., T!a = {h : µ(h, a) = !}. At each step, Algorithm 2 selects an action â using the greedy rule (Step 4) and then repeat â for c(â) times. Then we round the empirical mean of the observations to the closest element !̂ in ⌦a, ruling out inconsistent hypotheses, i.e., the h’s with µ(h, a) 6= !̂. We terminate when only one hypothesis remains alive.
Analysis We sketch a 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(|H|/ ) = 1 |H| it holds !̂ = µ(h⇤, â). Since in each iteration, |H| decreases by at least 1, there are at most |H| 1 iterations. Thus by union bound, the total error is at most .
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 c0 := ds 1 log(|H|/ )e, which does not depend on a. The definition of the ODT instance IODT remains the same except that each test has uniform cost c0 (as opposed to c(a)). Let c(T ) and c0(T ) be the costs of the greedy tree T returned by Algorithm 2 under c and c0 respectively. Then by Theorem 5, c0(T )  O(log |H|) ·ODT⇤. Note that c0  c(a) for each a since the separation parameter s is no larger than s(a) by definition. Hence,
GRE = c(T )  c0(T )  O(log |H|) ·ODT⇤. (1)
We relate ODT⇤ to OPTFA using the following result (see proof in Appendix C):
Proposition 2. ODT⇤  O( 1s log |H| ) ·OPT FA .
The above is established by showing how to convert a -PAC-error fully adaptive algorithm to a valid decision tree, using only tests in {Ta}, and inflating the cost by a factor of O( 1s log |H| ). Combining Proposition 2 with Equation (1), we obtain GRE  O( 1s log |H| log |H|) ·OPT FA .
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 as a special case. One may
Algorithm 2 Fully Adaptive Algorithm 1: Input: ASHT instance (H,A,⇡, µ,D) and error 2 (0, 1/2). 2: Halive H . % Alive hypotheses. 3: while |Halive| 2 do 4: ba argmaxa2A n min!2⌦a |Halive\T!a | o . % Greedy step.
5: c(â) ds(â) 1 log(|H|/ )e. % # times to boost for sufficient confidence. 6: Select â for c(â) times consecutively and observe outcomes X1, ..., Xc(â). 7: µ̂ Pc(â) i=1 Xi. % Mean outcome. 8: !̂ argmin{|µ̂ !| : ! 2 ⌦a}. % Round µ̂ to the closest !. 9: Halive Halive \ T !̂â . % Update the alive hypotheses.
10: end while
easily verify that the main theorem in [35] implies that a (slightly different) greedy algorithm achieves O(log |H|)-approximation 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.

heading: 6 Experiments
text: Although our theoretic guarantees depend on the separability parameters s (which was introduced by the boosting steps), in this section, we numerically demonstrate that with small modifications our algorithms perform well when s is small on both synthetic and real-world data. Our primary benchmarks are a polynomial-time policy proposed by [34] (Policy 15) and a completely random policy. To our knowledge, the policy proposed by [34] is the state-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 6.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 a publicly-available dataset of genetic mutations for cancer—COSMIC [40, 16].
Algorithm Details In all algorithms, we start with a uniform prior, and update our prior distribution (over the hypotheses space) each time an observation is revealed. Unless otherwise mentioned, the algorithm terminates if the posterior probability of a hypothesis is above the threshold 1 . 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 a 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 is 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 over-boosts. Modification b) controls the error probability when we decrease the amount of boosting. Modification c) handles small s without increasing the boosting factor. We formally describe this modified algorithm in Appendix F.
NJ Algorithm. NJ Adaptive [34] is a two-phase algorithm that solves a relaxed version of our problem, where the objective is to minimize a weighted sum of the expected number of tests and the likelihood of identifying the wrong hypothesis, i.e., minE(T ) +Le, where T is the termination time, L is the penalty for a wrong declaration, and e is the probability of making that wrong declaration. The problem was formulated as a Markov decision process whose state space is the posterior distribution over the hypotheses. In Phase 1, which lasts as long as the posterior probability of all hypotheses is below a carefully chosen threshold, the action is sampled according to a distribution that is selected
5Policy 2 in [34] does not have asymptotic guarantees and so is not considered in our experiments.
to maximize the minimum expected KL divergence among all pairs of outcome variables. In Phase 2, when one of the hypotheses has posterior probability above the chosen threshold, r, 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 real-world experiments. The algorithm stops if the posterior of a hypothesis is above the threshold 1 L 1. NJ Partially Adaptive contains only the Phase 1 policy.

heading: 6.1 Synthetic Experiments
text: 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 µ(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 is 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 was set to be 0.1. Indeed, we observe that NJ Adaptive outperforms NJ Partially Adaptive. In Figure 1 (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 1 middle and left.

heading: 6.2 Real-World Experiments
text: Problem Setup Our real-world experiment is motivated by the design of DNA-based blood tests to detect cancer. In such a 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 in a 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 in the human genome), and other tests have had similar scale (e.g., [38, 11, 37]). Thus, one promising approach to the ultimate goal of a cost-effective test is adaptivity.
Our experiments are a close reproduction of the setup used by [15] to identify their 4,500 addresses. We use 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 “ground-truth” table of mutation probabilities containing the likelihood of a mutation in 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 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, r, in NJ Adaptive was set to be 0.3. Since Phase 1 policy is less efficient than Phase 2 policy, we observe that the performance of NJ Adaptive is convex with respect to r—when r is small, the algorithm is more likely to alternate between Phases 1 and 2 policies and when r is large we spend more time in Phase 1 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 of the random baseline was very poor when compared with these of NJ Adaptive and Fully Adaptive and thus was 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.

heading: 7 Conclusions
text: In this work we 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 1 dependence on s in the approximation factors, since we have to boost each action for s 1 times to apply the concentration bounds. However, in our numerical experiments, by reducing the number of times for boosting, we achieved better performance when compared with existing heuristics.
Acknowledgments and Disclosure of Funding
We would like thank the anonymous reviewers for their careful reviews, and we declare no conflict of interests.

Review summaries:
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. 

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

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.