Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents an algorithmic framework for bandit multiple hypothesis setting that decouples exploration with summarization of evidence - where the summarization is done using either e-values or p-values. The main contribution is to show that the algorithm with e-values has some nice properties for controlling FDR, even when samples are dependent.

main_review: Novelty of contribution:
I am not convinced by the significance of the “unified framework” presented here. The authors present an algorithm with a specific notation that decouples the exploration criteria with evidence summarization. However, the results presented are still based on specific exploration criteria (UCB) and specific summarization method - p value or e-value based. I am not sure if the insights provided by the so-called unified framework are significant.

The main contribution seems to be the use of e-value instead of p-values in JJ, and Theorem 1 that demonstrates e-values can achieve cleaner control on FDR under dependence while giving similar performance in terms of TDR. However, there is some loss in sample complexity for achieving required TDR guarantees for the e-value based algorithm (Theorem 1 compared to Fact 4). It is not clear if that is an artifact of analysis technique or due to some fundamental shortcoming of using e-values compared to p-values. 
Some discussion on this aspect would be useful.

Presentation

Overall, the paper is well written and easy to read. Since the framework is claimed to be an important contribution by the authors, one aspect of the problem setting that may be presented better is the performance criteria. For a large part of the paper (until Section 6), FDR seems to be the sole performance measure.  However, the guarantee $FDR \le \delta$ does not seem meaningful without a corresponding guarantee on how large TDR is. (One can always achieve small FDR by producing very small rejection sets). It will be good to introduce the objective of algorithm design in the beginning as : $FDR \le \delta$ and $TDR  \ge 1-\delta’$ with as small sample complexity as possible. 

More concretely, when comparing procedures based on p-values and e-values in section 3, when the rejection sets produced are not identical for the two methods, ideally there should be some discussion on how large the corresponding rejection sets may be. Some guarantees are provided later in Section 6, but some conceptual discussion on TDR and sample complexity could be included in section 3 while discussing the impact on FDR.

Minor editorial comments:

On top of page 3, in definition of $H_1$ : ${\cal H}_1= [k]\backslash {\cal H}_0$

Theorem 1: “there will exist with T<..” Remove the extra word “with”

Summary:

Overall, the paper makes an interesting contribution to bandit multiple hypothesis testing using e-values instead of p-values. The guarantees achieved by the algorithm using e-values is better in terms of FDR but falls a bit short in terms of sample complexity to achieve required TDR. The significance of the unified framework is not clear.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a general framework for multiple hypothesis testing with data generated from bandit algorithms. In particular, the paper proposes a new e-value-based multiple testing method that 1) has a tighter FDR bound and 2) applies to more general settings, compared with previous p-valued-based methods (Jamieson and Jain, 2018). In a special case, the paper investigates the efficiency of its proposed algorithm and shows that the sample complexity needed for the TPR to be above the pre-specified threshold matches that of previous work (Jamieson and Jain, 2018). Additionally, the paper improves the FDR bound of the p-value-based method (Jamieson and Jain, 2018) by leveraging results from Su (2018).
main_review: 1. Conceptually, bringing the e-values (and the e-BH) to the bandit setting is quite a novel and natural idea, as one of the advantages of the e-value is that it deals with dependency well. On the technical side, it is not that surprising to see the FDR control established by leveraging the proof of e-BH.  I find the main technical difficulty here to be constructing (efficient) e-values---in general, it is not hard to construct valid e-values (since it is only required that its expectation is bounded by one) but it is non-trivial to obtain efficient e-values (it is possible that a valid e-value by construction can never be as large as 20).  In this paper, the authors provide an e-value constructing method based on Waudby-Smith and Ramdas (2021) that is proved to be efficient in a special case and appears to be efficient in numerical experiments.

2. In the paper, the authors describe their method as a meta-algorithm, while I tend to understand it as an inference method for data generated from bandit algorithms---it can be carried out post hoc since it does not interact with the data-collecting/arm-pulling process. Along this line, is it possible to inform decision-making with the e-values (in some special cases)? For example, in the case studied in Section 6, is it possible to design (based on e-values) a stopping time $\tau$, such that the output set $S_{\tau}$ achieves both FDR and TPR threshold (with $\tau$ being as small as possible). This should be similar to best arm identification, except that instead of finding the best arm, the aim is to quickly find a set of (mostly) non-trivial arms.

3. The exposition of the paper is in general clear, although I find some parts to be repetitive (e.g., p-BH requires independent structure).

4. Minor issues:
 - On page 2, in “...a strategy for for quickly...” there is an extra for. 
 - On page 3, defining the canonical filtration, the notation (i,j,X_{i,j}) is a bit confusing as the reader might think of j as another arm. Maybe use s instead.
 - On page 4, “...but most important for is the...”, is there a typo?
 - Also page 4, what is an “admissible e-process”? Is it defined somewhere?
 - “This is *in* contrast with procedures involving p-variables”?
 - On page 5, the footnote mark 1 should be after the comma.
 - The paragraph under fact 2, it is not very clear what “these dependence structures” refer to. 
 - On page 8, is there anything missing? why otherwise?


limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors give a unified framework for bandit multiple testing in terms of e-values. This framework is more flexible than prior work, allowing for dependencies between random variables and adaptive algorithm without corrections required in prior work, most notably JJ. The authors apply this result in a setting studied previouly where each arm is sub-gaussian and independent, and a single arm is queried at each step. They give sample complexity bounds matching prior state-of-the-art and show comparable performance in experiments.
main_review: The framework of e-processes seems quite useful for bandit multiple testing and this observation seems very important. 

It is not clear to me what the technical contributions of the current paper are over prior work on e-processes (e.g., Wang and Rambdas, 2020, and Waudby-Smith and Ramdas, 2021). Is the main contribution the usefulness of this framework to bandit multiple testing? Or, are there other technical challenges that had to be overcome to apply this framework to bandit multiple testing?

It seems that the algorithm in Section 6 using e-processes requires knowledge of Delta through the parameter R, which is often not known in practice. Is knowledge of Delta required to use this algorithm? If it is, then this would make the approach less practical. It may be that some sort of doubling method can be applied, but in that case would the guarantee still match the prior-state-of-the-art and would the algorithm perform as well in practice? 

The authors write that the Theorem 1 can likely be generalized to the setting where the Delta_i have very different values. Given the use of the warm-start to make \hat{\mu}_{i,t} a good estimate of \mu_i, I don't see what this algorithm would look like. It would be helpful to elaborate on this point since if it is difficult to prove bounds depending on Delta_i in this framework, that would make it less theoretically appealing.

The authors compare against BH in the setting where Delta_i = Delta for all i. It would be useful to see a comparison for the setting where the Delta_i's do not vary. Thus, we could at least get a sense of the performance of e-BH in this setting. Since this setting is common, it would be relevant to practice.

I think that it would be useful to move some of the other problem settings simulations from the appendix to the main paper. This would help clarify the advantage of flexibility of UCB e-BH over UCB BH and make the algorithms more concrete. 

After discussion: after reading the authors' responses and the other reviews, I maintain my score.

limitations_and_societal_impact: I do not see any potential negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the problem of Bandit Approach to Multiple Testing.

It shows the advantage of e-variables against p-variables in the use of multiple testing by proposing the following:
- extends the original problem to a combinatorial problem where a player can pull multiple arms
- a meta algorithm, adapted for both p-variables and e-variables
- comparing the confidence levels to use for both methods to reach an FDR < alpha
- comparing more specifically the performances of the original instance of multi-armed bandits (non-combinatorial)
main_review: I have read the other reviews and authors' answers. The authors did not totally dismiss my concerns. In particular, it seems that the use of e-processes is mostly beneficial in the specific case of combinatorial sampling (with dependent arms), which is too quickly mentioned in the paper (not counting the appendix). I think this aspect should be more showcased in the general structure of the paper to nicely illustrate the advantage of e-processes over p-processes with bandits.

--------------------------------------------------

This paper shows the interest of using e-variables against p-variables in multiple testing (with a bandits approach). I think this is a nice problematic to consider and that it indeed brings improvements to the current used schemes (in a black box manner).
Although, the paper seems poorly written overall and I think it requires to be rewritten in a more comprehensive/concise/accurate way.

The paper introduces a combinatorial version of the bandits hypothesis testing problem and the presented results (see eg Fact 2) seem to insist on the benefits of e-variables for this specific case. Yet the theoretical results of Section 6 and the experiments of Section 7 only consider the original single arm bandit (although there are expe for combinatorial in appendix), which limits the improvements brought by the use of e-variables. I think the paper should either focus on the sole problem of a single pull per round or the combinatorial case for clarity and simplicity. This will also lighten the writing, since it is overall very dense: we feel that the authors struggled to fit the 9 pages limit (see for example the page 8 with equations in the middle of the text). 
Moreover, there is no mention of the literature on combinatorial bandits, which would provide first insights on the exploration rules to use in these cases.

When claiming the Facts 1,2,3: we do not know if the difference in the used levels of confidence come from the analysis (that might not be tight), or if we indeed have examples where you cannot use smaller levels. In particular for the Fact 2, do we have an example of dependencies where we indeed have FDR(S) of order alpha(1+log(1/alpha))log(k) ?

Although the improvement of the e-variables is well illustrated by the different levels of confidence used, it seems that it will only imply a reduction by a constant factor in the sample complexity of the used processes. Indeed, note that the dependence in delta is often ln(1/delta) and changing delta by delta/ln(1/delta) will not considerably change this value in the end. This largely limits the interest of e-variables as it will only reduce the sample complexity by a constant factor. Moreover, this factor seems to reduce to 1 when the number of arms grows as can be shown by the experiments. 
Because of this, removing the constant terms in the Theorems (eg Thm 1) hides the real improvement of e-variable: it actually seems that there is no theoretical improvement at all.

In section 6, the UCB exploration in multiple testing seems incorrect: JJ does not take the argmax over [K] but over [K]\S_t
Moreover, the use of the parameter R does not seem really fair when comparing with the algo of JJ that does not use it. Especially, the authors need to know Delta to correctly tune R to then get their bound. Moreover, R leads to a uniform exploration instead of an adaptive one (which is why we have k /Delta^2 instead of sum 1/Delta_i^2 in the sample complexity given by Theorem 1.
Thus, I do not understand the interest of R at all, as I would have expected the algorithm to work even with R=0.
Because of this additional R, it even becomes unclear what algorithms are exactly compared in Figure 2. Does UCB BH corresponds to equation (3) and UCB e-BH to equation (4)? Then these are not the same exploration rules, so this is not a fair comparison as explained above.

------ minor comments ------

There are also many typos.

The notation k for the number of arms is not really the best (for example you have a contradicting notation in Appendix E because of this).
limitations_and_societal_impact: See above for the limitations

Societal impact: not concerned
review_title: null

Meta-review: This is a borderline paper. As the reviewers point out there are some valuable contributions but also various shortcomings. For instance, it is not fully obvious what the benefit of the unified framework is, the objective of the algorithm design is not stated clearly, and the paper could be improved significantly in a revision with regard to the presentation. Despite these shortcomings I believe that the contributions are valuable and I recommend to accept the paper.
Decision: Accept (Poster)