Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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.
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. 

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

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

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

Overall, 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. 
limitations_and_societal_impact: The work does not pose potential negative societal impact. The authors addressed the main limitations in the final section.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
main_review: ## Comments after response

I thank the Authors for their response. I read it carefully, as I did the comments from other Reviewers and the responses to them. 
I'm keeping my score as it is, but I think the paper should be accepted, even if it just marginally above the threshold.

## Original Review

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

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

## Other comments

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

Line 185: when the reader gets here, they have no idea of what is meant by "boosting".

Line 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

377: "approximationfactors" -> "approximation factors"
limitations_and_societal_impact: The Authors do a pretty good job at assessing the *algorithmic* limitations of the work.

This Reviewer does not see any potential negative societal impact that is *specific* to this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
main_review: Things that I like about the paper:
1) The problem considered in this paper is generic and captures a number of well-known problems; I find this generalization interesting.
2) The paper is well written and the authors do a good job in placing their contribution with respect to the related work.
3) 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.


Few concerns/suggestions:
1) Why is assumption 1 needed in general? Some intuition on why is it hard to overcome assumption 1 would be helpful.
2) 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.
3) 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.
4) If possible, mention approximation ratios (instead of just No and Yes) in Table 1.
5) Consider other benchmarks in the experiments or explain why you don't include them.
6) 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.
limitations_and_societal_impact: The authors do a sufficient job of addressing the limitations of their work.
review_title: null

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)