A unified framework for bandit multiple testing
Authors: Ziyu Xu
Ruodu Wang
Aaditya Ramdas
Venue: NeurIPS 2021 Poster (2021)
Keywords: bandits
multiple testing

Abstract: In bandit multiple hypothesis testing, each arm corresponds to a different null hypothesis that we wish to test, and the goal is to design adaptive algorithms that correctly identify large set of interesting arms (true discoveries), while only mistakenly identifying a few uninteresting ones (false discoveries). One common metric in non-bandit multiple testing is the false discovery rate (FDR). We propose a unified, modular framework for bandit FDR control that emphasizes the decoupling of exploration and summarization of evidence. We utilize the powerful martingale-based concept of "e-processes" to ensure FDR control for arbitrary composite nulls, exploration rules and stopping times in generic problem settings. In particular, valid FDR control holds even if the reward distributions of the arms could be dependent, multiple arms may be queried simultaneously, and multiple (cooperating or competing) agents may be querying arms, covering combinatorial semi-bandit type settings as well. Prior work has considered in great detail the setting where each arm's reward distribution is independent and sub-Gaussian, and a single arm is queried at each step. Our framework recovers matching sample complexity guarantees in this special case, and performs comparably or better in practice. For other settings, sample complexities will depend on the finer details of the problem (composite nulls being tested, exploration algorithm, data dependence structure, stopping rule) and we do not explore these; our contribution is to show that the FDR guarantee is clean and entirely agnostic to these details. 

A unified framework for bandit multiple testing
Ziyu Xu Department of Statistics and Data Science Carnegie Mellon University, USA xzy@cmu.. edu
Ruodu Wang
Department of Statistics and Actuarial Science University of Waterloo, Canada
wangduxaterloo..c
Aaditya Ramdas
Department of Statistics and Data Science Machine Learning Department Carnegie Mellon University, USA aramdas@cmm edu
Abstract
In bandit multiple hypothesis testing, each arm corresponds different null hypothesis that we wish to test, and the goal is to design adaptive algorithms that correctly identify large set of interesting arms (true discoveries), while only mistakenly identifying a few uninteresting ones (false discoveries). One common metric in non-bandit multiple testing the false discovery rate (FDR). We propose unified, modular framework for bandit FDR control that emphasizes the decoupling of exploration and summarization of evidence. We utilize the powerful martingale-based concept of "c-processes" to ensure FDR control for arbitrary composite nulls, exploration rules and stopping times in generic problem settings. In particular, valid FDR control holds even if the reward distributions of the arms could be dependent, multiple arms may be queried simultaneously. and multiple (cooperating competing) agents may be querying arms, covering combinatorial semi-bandit type settings as well. Prior work has considered in great detail the setting where each arm's reward distribution is independent and nub-Gaussian, and a single arm is queried at each step. Our framework recovers matching sample complexity guarantees in this special case, and performs comparably better in practice. For other settings, sample complexities will depend on the finer details of the problem (composite nulls being tested, exploration algorithm, data dependence structure, stopping rule) and we do not explore these; our contribution is to show that the FDR guarantee is clean and entirely agnostic to these details.
Introduction to bandit multiple hypothesis testing
Scientific experimentation often a sequential process. To test single null hypothesis - with "null" capturing the setting of no scientific interest, and the alternative being scientifically interesting sci- entists typically collect an increasing amount of experimental data in order to gather sufficient evidence such that they potentially reject the null hypothesis (i.e. make scientific discovery) with high de- gree of statistical confidence. As long as the collected evidence remains thin, they do not reject the null hypothesis and do not proclaim discovery. Since executing each additional unit of data (stemming from an experiment or trial) has an associated cost (in the form of time, money, resources), the scientist would like to stop as soon as possible. This becomes increasingly prevalent when the scientist is testing multi- ple hypotheses at the same time, and investing resources into testing one means divesting it from another.
For example, consider the case of scientist at pharmaceutical company who wants to discover which of several drug candidates under consideration are truly effective (i.c. testing hypothesis of whether each candidate has greater than baseline effect) through an adaptive sequential assignment of drug candidates to participants. Performing follow up studies on each discovery is expensive, so the scientist does not want make many "false discoveries" i.e. drugs that did not have actual effect, but were proclaimed to have one by the scientist. To achieve these goals, one could imagine
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

the scientist collecting more data for candidates whose efficacy is unclear but appear promising (e.g. drugs with nontrivial but inconclusive evidence), and stop sampling candidates that have relatively clear results already (e.g. drugs that have clear and large effect, or seemingly no effect).
Past work. This problem combines the challenges of multiple hypothesis testing with multi-arm bandits (MABs). In a "doubly-sequential" version of the problem studied by Yang et al. [46], one encounters sequence of MAB problems over time. Each MAB was used test a single special placebo arm against several treatment arms, and if at least one treatment dominated the placebo, then they aimed to return the best treatment. Thus each MAB was itself a single adaptive sequentieinii sequential hypothesis test, and the authors aimed not to make too many false discoveries over the sequence of MAB instances.
This paper instead considers the formulation of Jamieson and Jain [19], henceforth called JJ, but our techniques apply equally well to the above setup. To avoid confusions, note that our setup is very different from the active classification work of the same authors [ [17]. To recap, JJ consider a single MAB instance without a placebo arm (or rather, leaving it implicit), and try to identify as many treatments that work better than chance as possible, without too many false identifications. To clarify, we associate each arm with one (potentially composite) null hypothesis - for example, the hypothesis that corresponding drug has no (significant) effect. A single observed reward when pulling an arm corresponds to statistic that summarizes the results of one experiment with the corresponding drug, and the average reward across many experiments could correspond to an estimate of the average treatment effect, which would be (at most) zero for null arms and positive for non-nulls. Thus, a strategy for quickly finding the arms with positive means corresponds to strategy for allocating trial patients to drug candidates that allows the scientists to rapidly find the effective drugs.
However, the above corresponds to only the simplest problem setting. In more complex settings, it may be possible to pull multiple arms in each round, and observe correlated rewards. Further, the arms may have some combinatorial structure that allows only certain subsets of arms to be pulled. There could be multiple agents (eg: hospitals) pulling the same set of arms and seeing independent rewards (eg: different patients) or dependent rewards (eg: patient overlap or interference.. Further, if some set of experiments by one scientist yielded suggestive but inconclusive evidence, another may want to follow up. but not start from scratch, instead picking up from where the first left off. Last, the MAB may be stopped for variety of reasons that may or may not be in the control of the scientist (eg: a faster usage of funding than expected, or additional funding secured). We dive in the details of these scenarios in Appendix D.3.
Our contribution. We introduce a modular meta-algorithm for bandit multiple testing with provable FDR control that utilizes "e-values" - or, more appropriately, their sequential analog, "c-processes" recently introduced alternative p-values (or p-processes) by Ramdas al. [32] for various testing problems, that are inherently related to martingales, gambling and betting [33, 14, 15, 444. This work the first carefully study e-processes in general MAB settings, building on prior work that studied a special case [44]. We also are the first to extend the bandit multiple testing problem to the combinatorial bandit setting - JJ had previously only analyzed the problem in the single-arm. independent reward setting. Utilizing proccesses provide our alga-iam with several benefits. (a) For composite nulls, it is typically easier to construct e- e-processes than p- D-processes; the same holds when data from single source is dependent. When combining evidence from disparate (independent or dependent) sources, it is also more straightforward to combine e-values than p- -alaue (see Appendix D.3). (b) The same multiple testing step applies in all bandit multiple testing problems, regardless of all the various details of the problem setup mentioned in the previous paragraph. Consequently, FDR control in our meta-algorithm is agnostic to much of problem setup and can be proved in a vast array of settings. This is not true when working for valuus.. In particular, the techniques for proving FDR control in JJ are highly reliant on the specific bandit setup in their paper. (c) The exploration step can be - but does not have to be - decoupled from the multiple testing (combining evidence) step. This results in a modular procedure that can be easily ported to new problem settings to yield transparent guarantees on FDR control.
By virtue of being a meta-algorithm, we do not (and cannot) provide "generic" sample complexity guarantees: these will depend on all of the finer problem details mentioned above, on the exploration algorithm employed, on which e-processes are constructed. Our emphasis is on the flexibility with which FDR control can be guaranteed in a vast variety of problem setups. Further research can pick up one problem at time and design sensible exploration strategies and stopping rules, developing sampling complexity bounds for each, and these bounds will be inherited by the meta-algorithm.
2

---

However, we do formulate some generic exploration algorithms in Appendix C based on best arm identification algorithms [1, 22, 11, 18, 23, 10, 20].
When instantiated to the particular problem setup studied by JJ (independent, sub-Gaussian rewards, one arm in each round, etc.), we get slightly different algorithm from them the exploration strategy can be inherited to stay the same, but the multiple testing part differs. JJ use p- p-processes for each arm to determine whether that arm should be added to the rejection set, and correct for testing multiple hypotheses by using the BH procedure [6] to ensure that the false discovery rate (FDR), i.e. the proportion of rejections that are false discoveries in expectation, is controlled at some fixed level 5. Adaptive sampling induces a peculiar form of dependence amongst the p- p-values, for which the BH procedure provides error control at an inflated level: in other words, one has use BH at more stringent level of approximately 9/log( 16/6) 6) to ensure that the FDR is less than 6. On the other hand, we use the e-BH procedure [44], an analogous procedure for e-values, which can ensure the FDR is less than 8 without any inflation, regardless of the dependence structure between the e- e-values of each arm. Our algorithm has improved sample efficiency in simulations and the same sample complexity theory.
Formal problem setup. We define the bandit as having k arms, and V/ as the (unknown) reward distribution for arm E [k] = k..... Every arm i associated with a null hypothesis, which is represented by a known, prespecified set of distributions P.. If |P 1, it is a 'point null hypothesis", and otherwise is 'composite null hypothesis'. Examples of the latter include "all [0.1]] -boundedd distributions with mean < 0.5" or "all 1-sub- Gaussian distributions with mean < 0" or "all distributions that are symmetric around 0" or "all distributions with median S 0". While we assume by default that all rewards from an arm are i.i.d., we also formulate tests for hypotheses on reward distributions that may violate this assumption in Appendix G. If v E Pi, then we say that the i-th null hypothesis is true and we call a null arm; else, we say i-th null hypothesis is false and we call it a non-null arm. Thus, the set of arms are partitioned into two disjoint sets: nulls Ho E [k] and non-nulls Hi := [A]] Hoo.
Let IC C 2| denote the subsets of arms that can be jointly queried in each round. At each time I, the algorithm chooses a subset of arms I2 E X. to sample jointly from. The special choice of K {{11).
{k}} recovers the standard bandit setup, but otherwise this setting is known as combinatorial bandits with semi mani-b feedback [12]. We also consider the special case of full-bandit feedback (the algorithm sees all rewards each time step) in Appendix D. We denote the reward sampled at time from arm E I, as X... Ti(t) denote the number of times arm i has been sampled by time f, and f (j) be the time of the jth sample from arm i.
We now define a canonical "filtration" for our bandit problem. A filtration (Fi) is a series of nested sigma-algebras that encapsulates what information is known time 1. (We drop the subscript and just write (Fe) for brevity, and drop the parentheses when just referring to a single sigma-algebra at time f.) Define the canonical filiration follows for N: F, aF;==((0 (UU (i,s,..,)) : S I,i E [.)) and we let Fo = or (L') where U is uniformly distributed on [0.1] and its bits capture all private randomness used by the bandit algorithm that are independent of all observed rewards. Let (Ac) be a sequence of random variables indexed by t E N. (Ax) is said to be predictable w.r.t. (F;) if X₂ is measurable w.r.t. Ft-1 i.e. X, is fully specified given the information in Fi-1- An N-valued random variable is a stopping time (or stopping rule) w.r.t. to (FF) if (T=t) E Fr in other words, at each time t, we know whether or not to stop collecting data. Let T denote the set of all possible stopping times/rules w.r.t. (FF,). potentially infinite. Technically, the algorithm must not just specify a strategy to select I, but also specify when sampling will stop. This is denoted by the stopping rule or stopping time 7" ET.
Once the algorithm halts at some time t, it produces a rejection set S. C [K)]. We consider two metrics w.r.t S: the FDR as discussed prior, and true positive rate (TPR), which is the proportion of non-nulls that are discovered in expectation. These two metrics are defined as follows:
FDR(S,) == E Honss 1] [s
TPR(S,) = E
[Hins,]] [H1
We consider algorithms that always satisfy FDR(S.) < for any number and configuration of nulls Ho and any choice of null and non-null distributions. In fact, our algorithm will produce a sequence of candidate rejection sets (S,) that satisfies FDR(S-) < 8. This is much stronger guarantee than the typical setting considered in the multiple testing literature. On the other hand, TPR is a measurement of the power of the algorithm i.e. how many of the non-null hypotheses does the algorithm discover. Our implicit goal in the multiple testing problem to maximize the number of true discoveries while not making too many mistakes i.c. keep the FDR controlled.
3

---

In hypothesis testing, the set of null distributions P. for each arm is known, because the user defines the null hypothesis they are interested in testing. When the mill hypothesis is false, the non-null distribution can be arbitrary. Consequently, we can prove results about FDR, but we cannot prove guarantees about TPR without several further assumptions on the non-null distributions, dependence across arms, etc. For particular setting where we make such a set of assumptions, we demonstrate in Section 4 that we can prove TPR guarantees for algorithms within our framework. Hence, our FDR controlling framework is not vacuous it includes powerful algorithms i.e. algorithms which make many true discoveries. However, our focus is primarily to show that the FDR control of our framework is robust to wide range of conditions.
Finally, note that in bandit multiple testing, one does not care about regret. The problem is more akin to pure exploration, where we aim to find S with FDR(S,.)) á and large TPR as quickly as possible.
Now that we have specified the problem we interested in, we can introduce our main technical tools for ensuring FDR control at stopping times: e-processes and p-processes.
2
Technical preliminaries
2.1 E-processes versus p-processes
An e-variable, E, a nonnegative random variable where E[E] < 1 when the null hypothesis is true. In contrast, the more commonly used p-variable, P. is defined to have support on (0,1) and satisfy (PP aa) I a for all a E (0.1) when the null hypothesis is true. To clearly delineate when we are discussing solely the properties of a random variable, we also use the terms "e-value" e and "p-value" p to refer to the realized values of e-variable E and a p-variable (their instantiations on a particular set of data). E-variables and p-variables are connected through Markov's 's inequality, which implies that 1/ is a p-variable (but 1/ not in general an e-variable). Rejecting null hypothesis usually based on observing a small p-value or large e- e-value. For example, to control the false positive rate at 0.05 for a single hypothesis test, we reject the null when p S 0.05 or when e 20.
Since bandit algorithms operate over time, we define sequential versions of p-variables and e-variables. p-process, denoted (P:)121, 1. is sequence of random variables such that SuprerP(PP. Sa) a for any a E (0, 1). In contrast, an e-process (E))121 must satisfy supreT E[E,] < 1 (let Exg- == limsuprre Eg and Px liminf These sequentially valid forms of p- p-aariables and e- e-variables are crucial since we allow the bandit algorithm to stop and output a rejection set in data-dependent manner. Thus, we must ensure the respective properties of p-variables and e-variables hold over all stopping times.
These concepts are intimately tied to sequential testing and sequential estimation using confidence sequences [31], but most importantly, nonnegative tion of efficient e-processes. To summarize, (a) for point nulls, all admissible e-processes are simply nonnegative martingales. and the safety property follows from the optional stopping theorem, (b) for composite nulls, admissible e-processes are either nonnegative martingales. or nonnegative super- martingales, or the infimum (over the distributions in the null) of nonnegative martingales. Associated connections to betting [45] are also important for the development of sample efficient algorithms and we discuss how we use betting ideas in Appendix F. We also discuss some useful equivalence properties of p- processes in Appendix I, while Appendix A.2 introduces supermartingales for the unfamiliar reader.
play a central role in the construc-
Why use e-processes over p-processes? Wang and Ramdas [44] describe a multitude of advantages outside of the bandit setting: these advantages also apply the bandit setting but we do not redescribe them here for brevity. However, we will describe multiple ways in which using e-variables instead of p-variables as a measure of evidence in the bandit setting allows for both better flexibility and sample complexity of the algorithm. While this question has been the focus of a recent line of work for hypothesis tests in general [33,4] 41, 14, 44], we will explore how the properties of e-variables allow us to consider novel bandit setups and algorithms. In particular, e-variables allow us to be robust to arbitrary dependencies between statisties computed for each arm without additional correction. Further, we explore how e- e-processes can be merged under different conditions in Appendix D.3 to facilitate incorporation of existing evidence and cooperation between multiple agents and present concrete ways to construct e e-processes in Appendices B.3 and F.
Since any non-trivial bandit algorithm will base its sampling choice on the rewards attained far for every arm, average rewards of each arm are biased and dependent on each other in complex ways even if the algorithm is stopped a fixed time (27,35, 36, 37]. Even under non-adaptive uniform sampling rule, an adaptive stopping rule can induce complex dependencies between reward statistics of each

---

arm When using both adaptive sampling and stopping, the dependence effects are only compounded. Nevertheless, e-variable based algorithms enable us to prove FDR guarantces without assumptions on the sampling method. In contrast, procedures involving p-variables, such as the ones used in JJ, require the test level of a be corrected by a factor of at least log(1/o) /a) when rewards are independent across arms, and a factor of logk otherwise. We expand on this in Section 2.2.
2.2 Multiple testing procedures with FDR control
We now introduce two multiple testing procedures that output a rejection set with provable FDR control. We will first describe the guarantees provided by the BH procedure [6], classic multiple testing procedure that operates on p-variables. Then, we will describe e-BH, the e-variable analog of BH. Our key message in this section is that classical BH will have looser or tighter control of the FDR based upon the dependence structure of the p-variables is operating on. On the other hand, e-BH provides consistent guarantee on the FDR even when the e-variables arbitrarily dependent. Both procedures take an input parameter a E (0,1) that controls the degree of FDR guarantee (i.e. test level).
Henjaminn-Hochheee (BH) requires corrections for dependence and seff-consistency. A set S of p-values is called c-seeff-consiseett [9] at level a iff:
max ps S S||a SES
The BH procedure with input PI...Ppk outputs the largest sself-consistent set w.r.t. the input. which denote
We must also define condition the joint distribution of Pi,-..Pks Pk. which is called positive regression dependence on subset (PRDS). A formal definition is provided in Benjamini and Yekutieli [7], and is sufficient for our purposes to think of this condition positive dependence between Pk. with independence being a special case. Now, we describe the FDR control of the BH procedure.
Fact 1 (BH FDR control. Benjamini and Hochberg [6], Benjamini and Yekutieli [7]). Let S= =-BH(a]((1...... P.k). If Pi are PRDS, then (DR(S) S a. Otherwise, under arbitrary depen- dence amongst Pi....Pk. the BH procedure ensures FDR(S) S Sal,, where l = 1 1/k logk.
Thus, in the case of arbitrary dependence, the FDR control of BH is larger by factor of la se logk. A larger FDR guarantee is provided for arbitrary p-self-consistent sets.
Fact 2 ---self-consistent FDR control. Su [38], Blanchard and Roquain [9], Wang and Ramdas [44]- If S is p-self-consistent at level a and Pi....,PP Pk satisfy PRDS, then FDR(S) <a(1 + log(1 fa)). Otherwise, when there is arbitrary dependence among PI.....PA Pk. FDR(S) S at (consequence of Proposition 2.7 from Blanchard and Roquain [9] and Proposition 5.2 from Wang and Ramdas [44]).
These two facts do not imply each other, the BH procedure outputs the largest self-consistent set and has stronger or equivalent error guarantee under either type dependence. While it may seem like we should always use BH and the guarantee from Fact to form a rejection set, elaborate in Section 3.1 on how we can use Fact to provide FDR control for BH when the p p-variables are not necessarily PRDS, and in settings where we may not directly use BH.
e-BH needs no correction for dependence or self-consistency. The e-BH procedure created by Wang and Ramdas [44] uses e-variables instead of p-variables and proceeds similarly to the BH procedure. In this case, let C& be the realized e-values for a set of e-vriiblles E,...., Ex. Define enj
to be the ith largest e-value for E [Mt). A set S is --sseff-ossssseer at level iff S satisfies the following:
& min 4 2 a|S iES
(2)
Thee-BH e-BH procedure outputs the largest e-self-comsistent set, which we denote by (BH[a] For e-variables, the same guarantee applies for all e-self-consistent sets and under all dependence structures.
Fact 3 (E-variable self consssnnn FDR control. Wang and Ramdas [44]). I is e-self--onnsisent at level a, then FDR(S) S a regardless of the dependence structure.
All FDR bounds discussed in Facts to 3 are optimal, in the sense that there exist e-variable/p-variiabe distributions with an FDR that is arbitrarily close or equivalent to the stated bound. Consequently. e- variaalle are more advantageous, since their FDR control does not change under different types of
Su [38] technically employs a slightly weaker condition which implies PRDS, and refers to self-consistency "compliance" (or, better said, compliance a special case of self-consistency).
5

---

dependence as opposed to the factor of (+log(1/aa) or logk p-variables pay on the FDR for different settings.
In the case where p-variables can only be constructed as P=1/h F,, where is an e-variable, the rejection sets output by BH and e-BH are identical. However, the e-self-consistency guarantee in Fact provides identical or tighter FDR control than the BH procedure guarantee in Fact or p-self- consistency guarantee Fact Thus, e-variables and e-BH offer degree of robustness against arbitrary dependence, since any algorithm using e-BH does not have to adjust a to guarantee the same level of FDR(S) I 8 for a fixed 6 under different dependence structures. We now provide a meta-al veea--lgorithm that utilizes censs--cnnistency and coneiscnsittency to guarantee FDR control in the bandit setting.
3 Decoupling exploration and evidence: a unified framework
We propose framework for bandit algorithms that separates each algorithm into an exploration component and an evidence component; Algorithm specifies a meta-algorithm combining the two.
Algorithm meta-algorithm for handit multiple testing that decouples exploration and evidence. The evidence component can track p-processes or e-processes for each arm and use BH or e- e-BH.
Input:
Exploration component (At), stopping rule r", Let (PI..)....(PP..) e) and (e1..)...((ee.)) denote the realized values of p- p-processes and e-processes, respectively. Let the desired level of FDR control be de (0.1). Let o' be the correction of 8 for BH based upon the dependencies of X1.t Set Do=0. (1.
for t in 1... do
I A(= [M]
Obtain rewards for each i EI, and update data D;:= D.==D.LUU(4AX..):EE)))
Update e-process or p-process for each queried arm (summarizing evidence against each null).
BH[8" (P1.tr--P..))
arbitrary p-self-consistent set (C1, or arbitrary seeff-consistent set
if using p-variables
S,
if using variibbles
T- then stop and return
end
Exploration component. This sequence of functions (A:), where A, : Fi-1 + KC specifies the queried arms Ze := Ai (D, and D. := {(i.j.X..) t,i Zj} } is the observed data. A, is "non-adaptive" it does not depend on the data, but only on some external randomness U. Regardless of how the exploration component (Ac) is constructed, our framework guarantees that FDR(S) 2 for fixed 8. Similarly, y" is adaptive if it depends on the data, and is not determined purely by U.
Evidence component. The FDR control provided by Algorithm is solely due to the formulation of the candidate rejection set, S. [.Clk [k), at each time I N in the evidence component. This construction is completely separate from (At). Critically, (S.) satisfies FDR(S,) < 5 for any stopping time r ET. This is accomplished by applying BH e-BH to p-processes or e-processes, respectively. At stopping time r, P..r is a p-variable when (P,,t) is a p-process, and similarly Ei, is an e-variable when (E,,) an e-process. Thus, S, is the result of applying BH to p-variables or e-BH variables.
Consequently, the aforementioned framework allows us to guarantee sup+ey FDR(S+) S in a way that is agnostic to the exploration component. For completeness, we do discuss some generic exploration strategies in Appendix C. In the next section, we will formalize these guarantees and discuss the benefits afforded by using e- e-ariaalles and e- e-BH in this framework instead of variables and BH.
3.1 FDR control under different dependence structures
In the general combinatorial bandit setting, different dependence structures affect the choice of 8' that ensures FDR control at ó in the p-variable and BH case. Table summarizes the guarantees and choices of 8' for each type of dependence. Prior work on hypothesis testing in the bandit setting by JJ has only considered the con-combinatorial bandit case where XX. are independent. Critically, JJ employ BH and p-variables in their algorithm, and the FDR guarantee of BH changes based on the dependencies between reward distributions. On the other hand, choosing a= 8 for e-BH is sufficient to guarantee F FDR control at level for any type of dependence between e-variables, but only sufficient for BH in the non-adaptive, PRDS XX. setting. We show that there is a wide range of dependence structures that require different degrees of correction for BH. Specifically, we will set an appropriate choice of 8' each of these situations such that Algorithm with p-variables can ensure FDR control level ö. We include proofs of all results in this section in Appendix I.

---

Table 1: FDR control for BH, and the 8' to ensure á control of FDR in Algorithm under different dependence structures and adaptivity of (At). Adaptivity and arbitrary dependence both require extra correction for BH, but any e-selff procedure provides FDR(8) or in all settings in the table.
Dependence of X XI.t.....RR. R.3
Adaptivity of (As) and
independent
arbitrarily dependent
SD 88=6
non-adaptive
FDR(S) S Sologk 8' 86lokk (Prop. 2)
adaptive
8' 8'=csV (Prop. 1)
Any e-self-consistent procedure ensures FDR(S) a in all settings and sets a a= Ö.
Adaptiv (Ar) and independent poapdenttxx,ttom XR.. JJ consider this case in the non conbiiibinatt bandit setting, but their insights and techniques also can be extended to the combinatorial setting, We give sketch of their proof here, and produce the full proof in Appendix B.1. In the language of self-consistency (not explicitly used in JJ), JJ make the key insight that running BH on the p-variables for each arm produces rejection set that is actually p-self- p-variables. Define Pf ,?...PP.. where P = inf P.., for each i E [K] i.e. each arm's 's p-variable in the infinite sample limit. Since (Pr..) is p-process for each arm i E [A:]. the corresponding P is p-variable (Proposition in Appendix A. Further, Pf.....PP Px are independent because XI, are independent. By definition of Pr ...... P P¹ S Pt, for any i E [k] and any E N. Thus, S,, is consss-on w.r.t. pi..... Pi. and has its FDR bounded by a(1+log(1/o) (aa)) due to Fact 2. At the same time, the arbitrary dependence guarantee from Fact I still applies. Combining these facts, we achieve the following guarantee:
with different set of independent
Proposition 1. When (At) is adaptive and X1,t;--. Xktt are independent, Algorithm I with p-processes and an arbitrary p-seeffconsistent set guarantees sup, FDR(E where for any E (0,1), define cs S 5 as the solution to cs + +log(1/c)))
Note that Proposition is valid for any p-self-consisten set since p-sseff-onnsitency is the only property required of the output set to prove the result. JJ prove a similar bound to Proposition 1. However, they used a larger FDR bound for p-self- p-self-consistent sets with worse constants (which was subsequently improved by Su [38] as presented earlier), and they only considered the non-combinatorial case. Proposition uses an optimal bound on p-self-consistent sets from Fact 2, and is valid in our combinatorial bandit setup.
Adaptive (At) and arbitrarily dependent X1.t In the general combinatorial bandit setting, where the algorithm chooses a subset of arms or "superarm" each time to jointly sample from, we will have multiple samples from multiple arms in the same time step, and X1...... k, can be arbitrarily dependent. Consequently, the p-variables corresponding to each arm can also be arbitrarily dependent. For example, a superarm could consist of all arms, and the sampling rule could be to just sample this superarm that encompasses all arms. Then, the p-variable distribution would directly depend on the reward distribution of the arms. Thus, we can provide the following guarantee by Fact I when using p-variables as a result of Fact 3.
Proposition 2. When (As) is adaptive and X XR, are dependent, Algorithm 1 with p-variables and BH guarantees FDR(E,FFDRRS))
if $6/04.
Finally, consider setting structured setting where we cannot output the rejection set of BH. Such a con- straint often occurs in directed acyclic graph (DAG) settings where there is a hierarchy among hypothe- ses that restricts which rejection sets are allowed [30, 25]. Instead, we would like to output the largest set that respects the structural constraints. By Fact 2, we get the following FDR control. Proposition 3. (A:) adaptive and Xx. are dependent, Algorithm I with p-variables that outputs an arbitrary p-self-consisneee consisten St guarantees sup,er FDR 8 Sca/Ee.
We explore the structured setting with greater depth in Appendix D.2. Unlike p-variables, e-variables do not need correction in any of the aforementioned settings.
Proposition 4. When (A.) is adaptive and X1, XI. i are dependent, Algorithm I with e-variables, which runs e- e-BH at level 8 or outputs a colfs-conssttentt set at level ô, guarantees suprer
Thus, running B- (or any e-self-consistent procedure) at level is valid for any choice of (A.)) and type of dependence. Now, we give an example where X1. might be arbitrarily dependent.
7

---

3.2 Illustrative examples to demonstrate flexibility of the framework
Below, we briefly describe of nontrivial illustrative examples showcase the flexibility of our framework. In most of the cases below, p-process approach would have to correct for dependence and/or self-consistency in different case-specific ways, rendering it more conservative and requiring careful arguments to justify FDR control. However, working with our unified framework is easy, handling both self-consistency and dependence issues in the same breath and without any changes to the algorithm or analysis. The data scientist can focus on designing powerful e-processes for each arm separately and let the modular framework correct for the multiplicity aspect.
Example: sampling nodes on a graph. A scenario where X1.t..... Xx. may naturally have dependence is when each arm corresponds to a node could be defined w.r.t. to a graph constraint e.g. "two nodes connected by an edge" or "a node and its neighbors". Graph bandits has been studied in the regret setting [26] and have many real world applications [39]. We could imagine a scenario where low power sensors in a sensor network can only communicate locally. A centralized algorithm tasked with querying the sensors find those with high activity. A sensor may only provide activity information about itself and nearby sensors, and this data can be arbitrarily dependent across the sensors. Figure 1 illustrates a superarm in this situation. In such setting, if Proposition 2 is used to guarantee FDR(S) < 6 with p-variables, it pays logk correction, while Proposition 4 can guarantee e-rrriables need no correction. We simulate this setting in Appendix E.2, and show these differences empirically. We also discuss some other examples in the appendix that we will summarize here.
graph. The superarms in this situation
10
Multiple agents (Appendix D.3): Consider the setting where multi- ple agents are operating on the same bandit, and we want to aggregate the evidence for rejection across agents. For e-processes, we present an algorithm for merging e-values that maintains FDR control.
Structured rejection sets (Appendix D.2): We illustrate the dif- ference between self- self-connistency guarantees for p-variables and e-variables when a DAG hierarchy is imposed upon the hypotheses.
Figure I: A superarm consists of a node and all its neighbors. The dotted line captures Ie, the superarm around node 1,
Multi-arm hypotheses (Appendix D.4) A hypothesis may concern the reward distributions of multiple arms e.g. are the means of two different arms equivalent? We provide FDR guarantees even when hypotheses and arms are not matched one-to-one.
Streaming data setting (Appendix D. Our methods also naturally extend to the streaming setting when the algorithm views the rewards of every at each time step.
Now that we have shown FDR is controlled using e-variables in a way that is robust to the underlying dependence structure, we analyze the sample complexity of achieving high TPR using variables when the rewards are independent and Lub-Gaussian,
4 E-process sample complexity guarantees for sub-Gaussian arms
We provide sample complexity guarantees for the sub-Gaussian setting that has been the focus of existing methodology by JJ in bandit multiple testing. We explicitly define e-processes and an exploration component (A.)) that will have sample complexity bounds matching those of the algorithm JJ, which uses p- variables. Specifically, we will consider the standard bandit setting where [T, and v4 is Gaub-Gassiin for each E [k]. Denote the means of each arm i E [k] as μ4; = +[..,
for all / N. The goal is to find many arms where 14; noo where we pin O to be the mean of a reward distribution under the null hypothesis. Thus, we define Ho = { E [b]] 1/4 < p0) and H, (i E [k] f4 > /o)- Our framework ensures that FDR(S) < 6, and achieve TPR(S) 2 1-1 1-8 with small sample complexity. Proofs of the results from this section are in Appendices B.2 and B.3. As an aside, we also discuss what hypotheses we can test when the reward distribution is not necessarily independent across t E N, but the conditional distribution of the rewards still satisfy certain Gaussinn guarantees in Appendix G.
also want to
Our e- e-process of choice is the discrete mixture e-process from Howard et al. [16]:
Proposition 5. EDM is an e-process when v is
and E Ho-
8

---

Denote A; p4 for i 11 and
A m A. When Ho. let
Ti(t)
A; Si /4i /40 = A (14=
Bit
DM
(MO) := Σ
weexp
-HO) -oo -o)-1 (3a)
(o). First, we recall time-uniform bound on the sample mean fiz-
E=
where de = ef45/2
2(e-1) for E EE and We = c(t+2)²
(3b)
Fact 4 (JJ, Kaufmann et al. [23]. Howard al. [16]). Let X1, X2... ... be i.i.d. draws from L-sub-Gaussian distribution with mean p.. Consider the boundaries defined in (4), Let up be one of these boundaries, Then, P( (lft=)))(((t)))) Só for any d (0,1) ef (ip) , and any ò (0,0.1) if
We will use yp to refer to an arbi- trary boundary from Fact All of the yp are time-uniform bound- aries that yield confidence se- quences for the mean. Note that sp" is generally larger than the use o as the default boundary in our proofs, and we explore how different choices of affect empirical performance in Appendix E.I. Now, we can define the algorithm from JJ in (5), which consists of an exploration policy based on an upper confidence bound (UCB) of the mean reward (specified by singleton set I2 = ( and a p-variable derived from Fact
(t,)))
(4a)
(1)(1))= V 2log( 14001000000000000000000440000000
(4b)
2. 2.8lloggog((22001)))22226646 4.283
other boundaries,
(1,0)
(4c)
In (5a), we denote the sample mean at time L of each arm i E [K] by Tis. Let ʃ S g denote f asymptotically dominates g i.e. there exist e> 0 that is independent of the problem parameters such that f eg. JJ prove the following sample complexity guarantee for their algorithm.
Fact 5 (From Let (As) oulput I, (1)), and let I, and Pt, be specified by Alg. 5 with x= Then, F TS E4=1, loologg, 2 A A. Plog(log - such that TPR(S;) 1-8 for allt>
Algorithmm will always
5. With least 1 1 probability, there will exist -2)
We show that we can match the sample com- plexity bounds of Fact 5 with e-variables.
1. 1- ar_
(5a)
Theorem 1. Let u; be asub-Gaussian
in. (0. -i. Hol (1.)))
(5b)
[k]. Set (A.) so As outputs {11} from (5a)
for all t & N and Ei,t to EDM Algorithm ensures sup FDR(S,) < 5 and, with at least 1 - 8
probability, there exists TS (E 2oglogA A, (og)))(k/))) A. ?log(log( A -2) such
that TPR(S.) 2- all 12T.
In addition to matching theoretical guarantees, we show in the following section that e-variables and c-BH perform empirically well or better than p-rrriables and BH through numerical simulations.
5 Numerical simulations
We perform simulations for the sub-Gause Satb-Gasssian setting discussed in Section 4 to demonstrate that our version of Algorithm I using e-variables is empirically as efficient as the algorithm of JJ, which uses p-variables (code available here). However, unlike JJ, our algorithm does not based upon the dependence assumptions among XI.,,....XR. to guarantee FDR is controlled at level We explore additional simulations of combinatorial semi-ber aini-bandit settings with dependent X1. in Appendix E that show the benefit of using e-variables over p p-rariables in our framework.
corrected level 8
Simulation setup Let 14 =W(u;, where 14 14u 0f E Ho and μæ 1/2 M4. We consider 3 setups, where set the number of non-null hypotheses to be [Hg = 2.logk, and Vk. to see the effect of different magnitudes of non-null hypotheses on the sample complexity of each method. We set ò 0.05 and compare 4 different methods. We compare the same two different exploration components for both e-variables and p-variables. The first exploration component we consider is simply uniform sampling across each arm (Uni). The second is the UCB sampling strategy described in (5a). When using BH, our formulation for p-variables (5b), which is the same as JJ. Like JJ, we set go = JJ our simulations. PMMH
When using e- -HH, we set our e-variables to E
( exp( (K.. p0) A.,,,.)/2)

---

(T))) which is the default choice of Ar suggested in Waudby-Smin and Ramdas [45]. We show that this is a valid e-process in Appendix F and maintains FDR control.
with As, V 2log (2/a)
Results We plot the relative performance of each method to e-BH with UCB sampling in Figure For uniform sampling, e-BH and e- e-variables seem to outperform BH and p-variables, although by decreasing margin for more arms, especially in the case where [7L | Vkl. For the UCB sampling algorithm, we see that e-variables and p-variables have relatively similar performance, with the gap narrowing the number of arms increase as well. Thus, e-variables and e-BH empirically perform on par or better than p-variables with regards to sample complexity. This shows that using e-variables does not require any sacrifice in performance in simple cases where p- variiables also work well. Further, variables do not require the same logk correction that p- p-variables need for situations where X1 LK.......R.. are arbitrarily dependent guarantee FDR control at the same level. Thus, e-variables are preferable to p-variables as they are more flexible w.r.t. assumptions.
UCB e-BH Uni e-BH
UCB BH Uni BH
Time
Time
3-
2
2-
2
1
10
102
10a
10a
10a
10a
Arms
Arms
Arms
(a) |Hi|= 2
(b) H | = [logk]
(c) |H = VE
Figure 2: Relative comparison of time t to obtain a rejection set, S,, that has a (P) and FDR(S;) s 5 where 6 = 0.05. This plot compares e- e-BH vs. BH for both uniform (Uni) and UCB sampling over different numbers of arms (choices of k)) and densities of non-null hypotheses (sizes of Hi). Time is reported a ratio to the time taken by UCB e-BH method. Note that the methods using e- e-variables perform on par or better than methods using p- p-variables for both sampling strategies.
6 Conclusion, limitations and broader impact
In this paper, we developed a unified framework for bandit multiple hypothesis testing. We demonstrated that applying the e-BH procedure to stopped e-processes guarantees FDR control without assumptions on the the dependency between 11,, exploration strategy, stopping time of the algorithm, ability to query multiple arms, etc. In contrast, existing algorithms using BH and p- p-variables have FDR guarantees that vary with the problem setting and dependence structure among the p- variables. We argued that control of the FDR with p- p-variables can blow up by a factor of logk, and any p p-self- control consistent algorithm must decrease its threshold for discovery correspondingly to maintain at the desired level. We provide more detailed explanations of these observations in Appendix D.2. In addition to demonstrating the generality of our meta-algorithm, we showed that in the standard sub-Ga Sab-Gaussian reward setting, the instantiated algorithm matches the sample complexity bounds of the o-variable algorithm by JJ for achieving high TPR, and has better practical performance than JJ's algorithm, despite the fact that we improve JJ's guarantees by invoking the self-consistency results of Su [38].
The appendices have additional examples of problem settings and simulations that show the utility of c-processes and our general framework. In fact, the null hypotheses do not have a one-to-one correspondence with the arms; in other words, despite the queries being at the arm-level, the hypotheses being tested could combine arms (for example, comparing different arms). We also discuss the multi-agent setting where there could be multiple agents that operate the same bandit. We avoided these scenarios in the main paper for simplicity of exposition, since there were enough generalizations to describe in the simpler setup already.
address
more general setting where
The main limitation of the work is that it does not develop instance optimal sampling algorithms for multiple testing problem in the described settings with more complicated dependence structures; we believe this is difficult open problem, requiring specialized techniques in each example. We do not foresee any negative socictal impact of this work; is aimed at reducing costs and improving reproducibility in scientific experimentation by controlling false discoveries in adaptive testing.
10

---

Acknowledgments RW acknowledges funding from NSERC SOPIN-20118 201---08888--33333 and RGPAS- 2018-522590. AR acknowledges funding from NSF DMS 1916320 and ARL IoBT REIGN. Research reported in this paper was sponsored in part by the DEVCOM Army Research Laboratory under Cooperative Agreement N911NFF17-2-011 in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
(ARL. loBTCRA). The views and conclusions contained
References
[1] J.-Y. Audibert and S. Bubeck. Best arm identification in multi-armed bandits, In Conference on Learning Theory, 2010.
[2] J. Bartroff. Multiple Hypothesis Tests Controlling Generalized Error Rates for Sequential Data. Statistica Sinica, 2017. ISSN 10170
[3] Bartroff and J. Song. Sequential tests of multiple hypotheses controlling type and II familywise error rates. Journal of Statistical Planning and Inference, 153:100-114, 2014. ISSN 0378-3758.
[4] J. Bartroff' and J. Song. A Rejection Principle for Sequential Tests of Multiple Hypotheses Controlling Familywise Error Rates. Scandinavian Journal of Statistics, 31(1)33-19, 2016. ISSN 0303-6898.
Journaa
[5] J. Bartroff and Song. Sequential Tests of Multiple Hypotheses Controlling False Discovery and Nondiscovery Rates. Sequential analysis, 39(1):65 91, 2020. ISSN 0747-4946.
[6] Y. Benjamini and Y. Hochberg. Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple Testing. Journal of the Royal Statistical Society. Series (Methodological), 57(1):289-300, 1995. ISSN 0035-9246.
[7] Y. Benjamiii and D. Yekutieli. The control of the false discovery rate in multiple testing under dependency. The Annals of Statistics, 29(4): 111111188888 2001. ISSN 0090-5364. 2168-8966.
[8] A. Birnbuu. Combining Independent Tests of Significance. Journal of the American Statistical Association,44((6)))555 49(26)):559- 554, 1954. ISSN 0162-1459.
[9] G. Blanchard and E. Roquain. Two simple sufficient conditions for FDR control. Electronic Journal of Statistics, 2:963-992, 2008. ISSN 1935-7524, 1935-7524.
[10] L. Chen, A. Gupta, J. Li, M. Qiao, and R. Wang. Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration. Conference on Learning Theory, 2017.
[11] S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen. Combinatorial pure exploration of multi-armed bandits. Neural Information Processing Systems,
[12] W. Chen, Y. Wang. Y. Yuan, and Q Wang. Combinatorial multi-armed bandit and its extension to probabilisticalyy triggered arms. Journal of Machine Learning Research, 17(50): 1-33, 2016
[13] R. Durrett. Probability: Theory and Examples. Cambridge University Press, 5a edition, 2017.
[14] P. Grünwald, R. de Heide, and W. Koolen. Safe Testing. arXivv/906.07801,
[15] S. R. Howard, A. Ramdas, J. McAuliffe, and Sekhon. Time-uniform chernoff bounds via
nonnegative supermartingales. Probability Surveys, 17:257-317, 2020.
[16] S. R. Howard, A. Ramdas, J. McAuliffe, and Sckhon. Time-uniform, nonparametric, nonasymp-
totic confidence sequences. The Annals of Statistics, 4952):0055-1080 2021.
[17] L. Jain and K. G. Jamieson. A new perspective on pool-based active classification and false- discovery control. In Neural Information Processing Systems, 2019. 2019..
[18] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. Lil' UCB An Optimal Exploration Algorithm for Multi-Armed Bandits. In Conference on Learning T'heory, 2014.
[19] K. G. Jamieson and L. Jain. A bandit approach to sequential experimental design with false discovery control. In Neural Information Processing Systems, volume 31, 2018.
[20] M. Jourdan, M. Mutný, J. Kirschner, and A. Krause. Efficient Pure Exploration for Combinatorial Bandits with Semi- Bandit Feedback. In Algorithmic Learning Theory, 2021.
11

---

[21] K.-S. Jun, F. Orabona, S. Wright, and R. Willett. Online learning for changing environments using coin betting. Electronic Journal of Statistics, 11(2):5222-5310, 2017. ISSN 1935-7524, 1935-7524.
[22] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone. PAC subset selection in stochastic multi- armed bandits. In International Conference on Machine Learning, 2012.
[23] E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in multi- armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016. ISSN 1532-4435.
[24] I.. Kelly. A new interpretation of information rate. The Bell System Technical Journal, 35(4): 917-926, 1956.
[25] I.. Lei, A. Ramdas, and W. Fithian. A general interactive framework for false discovery rate control under structural constraints. Biometrika, 2020. ISSN 0006-3444.
[26] S. Mannor and O. Shamir. From bandits to experts: On the value of side-observations. In Neural Information Processing Systems, 2011.
[27] X. Nie, X. Tian, J. Taylor, and J. Zou. Why adaptively collected data have negative bias and how to correct for it. International Conference on Artificial Intelligence and Statistics, 2018.
[28] Orabona and D. Pál. Coin betting and parameter- online learning. In Neural Information
Processing Systems, 2016.
[29] F. Orabona and T. Tommasi. Training Deep Networks without Learning Rates Through Coin Betting. In Neural Information Processing Systems, 2017.
[30] A. Ramdas, J. Chen, M.J. Wainwright, and M. Jordan. A sequential algorithm for false discovery rate control on directed acyclic graphs. Biometrika, 106:69-86, 86, 2019. ISSN 0006-3444.
[31] A. Ramdas, J. Ruf, M. Larsson, and W. Koolen. Admissible anytime-valit sequential inference must rely on nonnegative martingales. arXiv:2009. 20l::2009903167, 2020.
[32] A. Ramdas, J. Ruf, M. Larsson, and W. M. Koolen. Testing exchangeability: corv-ctoy,xitt,
supermartingales and e-processes. International Journal of Approximate Reasoning, 2021. ISSN 0888-613X.
[33] G. Shafer. Testing by betting: strategy for statistical and scientific communication. Journal of the Royal Statistical Society: Series A (Statistics in Society), (84(2)447-4411,00)) ISSN 1467-985X.
[34] G. Shafer and V. Vovk. Game-Theoretic Foundations for Probability and Finance. John Wiley Sons, Ltd, first edition, 2019. ISBN 778--1-118-54003--
[35] J. Shin, A. Ramdas, and A. Rinaldo. Are sample means in multi-armed bandits positively or negatively biased? Neural Information Processing Systems, 2019.
[36] J. Shin, A. Ramdas, and A. Rinaldo. On conditional versus marginal bias in multi-armed bandits. In International Conference on Machine Learning, 2020.
[37] Shin, A. Ramdas, and A. Rinaldo. On the bias, risk and consistency of sample means in multi-armed bandits. SIAM Journal on the Mathematics of Data Science, 2021.
[38] W. Su. The FDR-Linking Theorem. arXiv: 1812,88925. 2018.
[39] M. Valko. Bandits on Graphs and Structures. HdR Thesis, Ecole normale supérieure de Paris-
Saclay, Paris-Saclay France, 2016.
[40] V. Vovk. Testing randomness online. Statistical Science, 2021.
[41] V. Vovk and R. Wang. E-values: Calibration, combination, and applications. Annals of Statistics,
2021.
[42] V. Vovk, I. Petej. I. Nouretdinov, E. Ahlberg. L. Carlsson, and A. Gammerman. Retrain or not retrain: Conformal test martingales for change-point detection. Symposium on Conformal and Probabilistic Prediction and Applications. 2021.
[43] V. Vovk, B. Wang, and R. Wang. Admissible ways of merging p p-values under arbitrary dependence. The Annals of Statistics (forthcoming), 2021.
[44] R. Wang and A. Ramdas. False discovery rate control with e-values. urXiv:2009.02824. 2020.
12

---

[45] I. Waudby-Smith and A. Ramdas. Estimating means of bounded random variables by betting. arXiv:2010.09686 2021.
[46] F. Yang, A. Ramdas, K. Jamieson, and M.J. Wainwright. A framework for (ulti--(mmmdd)//aniiii)) testing with online FDR control. Neural Information Processing Systems, 2017.
13


Reviews:
[{"review_id": "xbAbv4_SXid", "reviewer": "Reviewer_MD8E", "summary": "This paper studies the problem of Bandit Approach to Multiple Testing.\n\nIt shows the advantage of e-variables against p-variables in the use of multiple testing by proposing the following:\n- extends the original problem to a combinatorial problem where a player can pull multiple arms\n- a meta algorithm, adapted for both p-variables and e-variables\n- comparing the confidence levels to use for both methods to reach an FDR < alpha\n- comparing more specifically the performances of the original instance of multi-armed bandits (non-combinatorial)", "questions": "", "limitations": "", "rating": 5, "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": "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.\n\n--------------------------------------------------\n\nThis 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).\nAlthough, the paper seems poorly written overall and I think it requires to be rewritten in a more comprehensive/concise/accurate way.\n\nThe 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). \nMoreover, there is no mention of the literature on combinatorial bandits, which would provide first insights on the exploration rules to use in these cases.\n\nWhen 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) ?\n\nAlthough 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. \nBecause 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.\n\nIn section 6, the UCB exploration in multiple testing seems incorrect: JJ does not take the argmax over [K] but over [K]\\S_t\nMoreover, 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.\nThus, I do not understand the interest of R at all, as I would have expected the algorithm to work even with R=0.\nBecause 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.\n\n------ minor comments ------\n\nThere are also many typos.\n\nThe 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).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above for the limitations\n\nSocietal impact: not concerned", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "_HL_T3Pat6W", "reviewer": "Reviewer_VJPB", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Novelty of contribution:\nI 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.\n\nThe 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. \nSome discussion on this aspect would be useful.\n\nPresentation\n\nOverall, 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. \n\nMore 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.\n\nMinor editorial comments:\n\nOn top of page 3, in definition of $H_1$ : ${\\cal H}_1= [k]\\backslash {\\cal H}_0$\n\nTheorem 1: “there will exist with T<..” Remove the extra word “with”\n\nSummary:\n\nOverall, 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5 hours"}, "extra_text": {}}, {"review_id": "MDeoMwb3-b", "reviewer": "Reviewer_7wSu", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "The framework of e-processes seems quite useful for bandit multiple testing and this observation seems very important. \n\nIt 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?\n\nIt 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? \n\nThe 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.\n\nThe 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.\n\nI 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. \n\nAfter discussion: after reading the authors' responses and the other reviews, I maintain my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any potential negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "88ojD_q5qcv", "reviewer": "Reviewer_1bLS", "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).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "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.\n\n2. 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.\n\n3. The exposition of the paper is in general clear, although I find some parts to be repetitive (e.g., p-BH requires independent structure).\n\n4. Minor issues:\n - On page 2, in “...a strategy for for quickly...” there is an extra for. \n - 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.\n - On page 4, “...but most important for is the...”, is there a typo?\n - Also page 4, what is an “admissible e-process”? Is it defined somewhere?\n - “This is *in* contrast with procedures involving p-variables”?\n - On page 5, the footnote mark 1 should be after the comma.\n - The paragraph under fact 2, it is not very clear what “these dependence structures” refer to. \n - On page 8, is there anything missing? why otherwise?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

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)