A unified framework for bandit multiple testing
Year: 2021

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.

heading: 1 Introduction to bandit multiple hypothesis testing
text: Scientific experimentation is often a sequential process. To test a single null hypothesis — with “null” capturing the setting of no scientific interest, and the alternative being scientifically interesting — scientists typically collect an increasing amount of experimental data in order to gather sufficient evidence such that they can potentially reject the null hypothesis (i.e. make a scientific discovery) with a high degree of statistical confidence. As long as the collected evidence remains thin, they do not reject the null hypothesis and do not proclaim a 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 multiple hypotheses at the same time, and investing resources into testing one means divesting it from another.
For example, consider the case of a scientist at a pharmaceutical company who wants to discover which of several drug candidates under consideration are truly effective (i.e. testing a 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 to make many “false discoveries” i.e. drugs that did not have an 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 a 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 a sequence of MAB problems over time. Each MAB was used to 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 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 a 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 a 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 a 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 is 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, “e-processes” — a recently introduced alternative to p-values (or p-processes) by Ramdas et al. [32] for various testing problems, that are inherently related to martingales, gambling and betting [33, 14, 15, 44]. This work is the first to 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 e-processes provide our meta-algorithm with several benefits. (a) For composite nulls, it is typically easier to construct e-processes than p-processes; the same holds when data from a single source is dependent. When combining evidence from disparate (independent or dependent) sources, it is also more straightforward to combine e-values than p-values (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 p-values. 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 a 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.
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 a slightly different algorithm from them — the exploration strategy can be inherited to stay the same, but the multiple testing part differs. JJ use 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 𝛿. Adaptive sampling induces a peculiar form of dependence amongst the p-values, for which the BH procedure provides error control at an inflated level; in other words, one has to use BH at a more stringent level of approximately 𝛿/log(16/𝛿) to ensure that the FDR is less than 𝛿. 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 𝛿 without any inflation, regardless of the dependence structure between the e-values of each arm. Our algorithm has improved sample efficiency in simulations and the same sample complexity in theory.
Formal problem setup. We define the bandit as having 𝑘 arms, and 𝜈𝑖 as the (unknown) reward distribution for arm 𝑖 ∈ [𝑘] = {1,...,𝑘}. Every arm 𝑖 is associated with a null hypothesis, which is represented by a known, prespecified set of distributions 𝒫𝑖. If |𝒫𝑖|=1, it is a ‘point null hypothesis’, and otherwise it is a ‘composite null hypothesis’. Examples of the latter include “all [0,1]-bounded 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 ≤ 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 𝜈𝑖∈𝒫𝑖, then we say that the 𝑖-th null hypothesis is true and we call 𝑖 a null arm; else, we say 𝑖-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 ℋ0⊆ [𝑘] and non-nulls ℋ1 :=[𝑘]∖ℋ0.
Let 𝒦 ⊆ 2[𝑘] denote the subsets of arms that can be jointly queried in each round. At each time 𝑡, the algorithm chooses a subset of arms ℐ𝑡 ∈ 𝒦 to sample jointly from. The special choice of 𝒦 = {{1},{2}, ... ,{𝑘}} recovers the standard bandit setup, but otherwise this setting is known as combinatorial bandits with semi-bandit feedback [12]. We also consider the special case of full-bandit feedback (the algorithm sees all rewards at each time step) in Appendix D.1. We denote the reward sampled at time 𝑡 from arm 𝑖∈ℐ𝑡 as 𝑋𝑖,𝑡. Let 𝑇𝑖(𝑡) denote the number of times arm 𝑖 has been sampled by time 𝑡, and 𝑡𝑖(𝑗) be the time of the 𝑗th sample from arm 𝑖.
We now define a canonical “filtration” for our bandit problem. A filtration (ℱ𝑡)𝑡≥0 is a series of nested sigma-algebras that encapsulates what information is known at time 𝑡. (We drop the subscript and just write (ℱ𝑡) for brevity, and drop the parentheses when just referring to a single sigma-algebra at time 𝑡.) Define the canonical filtration as follows for 𝑡∈N: ℱ𝑡 :=𝜎(𝑈∪{(𝑖,𝑠,𝑋𝑖,𝑗) :𝑠≤ 𝑡,𝑖∈ℐ𝑠}) and we let ℱ0 :=𝜎(𝑈) where 𝑈 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 (𝜆𝑡) be a sequence of random variables indexed by 𝑡∈N. (𝜆𝑡) is said to be predictable w.r.t. (ℱ𝑡) if 𝜆𝑡 is measurable w.r.t. ℱ𝑡−1 i.e. 𝜆𝑡 is fully specified given the information in ℱ𝑡−1. An N-valued random variable 𝜏 is a stopping time (or stopping rule) w.r.t. to (ℱ𝑡) if {𝜏 = 𝑡}∈ℱ𝑡 — in other words, at each time 𝑡, we know whether or not to stop collecting data. Let 𝒯 denote the set of all possible stopping times/rules w.r.t. (ℱ𝑡), potentially infinite. Technically, the algorithm must not just specify a strategy to select ℐ𝑡, but also specify when sampling will stop. This is denoted by the stopping rule or stopping time 𝜏*∈𝒯 . Once the algorithm halts at some time 𝜏 , it produces a rejection set 𝒮𝜏 ⊆ [𝑘]. We consider two metrics w.r.t. 𝒮: 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(𝒮𝜏 ) := E [︁ |ℋ0∩𝒮𝜏 | |𝒮𝜏 |∨1 ]︁ , TPR(𝒮𝜏 ) := E [︁ |ℋ1∩𝒮𝜏 | |ℋ1| ]︁ .
We consider algorithms that always satisfy FDR(𝒮𝜏 )≤𝛿 for any number and configuration of nulls ℋ0 and any choice of null and non-null distributions. In fact, our algorithm will produce a sequence of candidate rejection sets (𝒮𝑡) that satisfies sup𝜏∈𝒯 FDR(𝒮𝜏 )≤𝛿. This is a 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 is to maximize the number of true discoveries while not making too many mistakes i.e. keep the FDR controlled.
In hypothesis testing, the set of null distributions 𝒫𝑖 for each arm 𝑖 is known, because the user defines the null hypothesis they are interested in testing. When the null 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 a 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 as 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 a 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 a 𝒮 with FDR(𝒮𝜏*)≤𝛿 and large TPR as quickly as possible. Now that we have specified the problem we are interested in, we can introduce our main technical tools for ensuring FDR control at stopping times: e-processes and p-processes.

heading: 2 Technical preliminaries

heading: 2.1 E-processes versus p-processes
text: An e-variable, 𝐸, is a nonnegative random variable where E[𝐸]≤1 when the null hypothesis is true. In contrast, the more commonly used p-variable, 𝑃 , is defined to have support on (0,1) and satisfy P(𝑃 ≤𝛼) ≤ 𝛼 for all 𝛼 ∈ (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” 𝑒 and “p-value” 𝑝 to refer to the realized values of a e-variable 𝐸 and a p-variable 𝑃 (their instantiations on a particular set of data). E-variables and p-variables are connected through Markov’s inequality, which implies that 1/𝐸 is a p-variable (but 1/𝑃 is not in general an e-variable). Rejecting a null hypothesis is usually based on observing a small p-value or a large e-value. For example, to control the false positive rate at 0.05 for a single hypothesis test, we reject the null when 𝑝≤0.05 or when 𝑒≥20. Since bandit algorithms operate over time, we define sequential versions of p-variables and e-variables. A p-process, denoted (𝑃𝑡)𝑡≥1, is a sequence of random variables such that sup𝜏∈𝒯 P(𝑃𝜏 ≤𝛼) ≤ 𝛼 for any 𝛼 ∈ (0, 1). In contrast, an e-process (𝐸𝑡)𝑡≥1 must satisfy sup𝜏∈𝒯 E[𝐸𝜏 ] ≤ 1 (let 𝐸∞ := limsup𝑡∈N𝐸𝑡 and 𝑃∞ := liminf𝑡∈N𝑃𝑡). These sequentially valid forms of p-variables and e-variables are crucial since we allow the bandit algorithm to stop and output a rejection set in a 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 (super)martingales play a central role in the construction 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 supermartingales, 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 pprocesses in Appendix A.1, while Appendix A.2 introduces supermartingales for the unfamiliar reader.
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 to 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, 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 statistics computed for each arm without additional correction. Further, we explore how 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-processes in Appendices B.3 and F.
Since any non-trivial bandit algorithm will base its sampling choice on the rewards attained so 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 at a fixed time [27, 35, 36, 37]. Even under a 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 guarantees without assumptions on the sampling method. In contrast, procedures involving p-variables, such as the ones used in JJ, require the test level of 𝛼 to be corrected by a factor of at least log(1/𝛼) when rewards are independent across arms, and a factor of log𝑘 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], a 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 it is operating on. On the other hand, e-BH provides a consistent guarantee on the FDR even when the e-variables are arbitrarily dependent. Both procedures take an input parameter 𝛼∈(0,1) that controls the degree of FDR guarantee (i.e. test level). Benjamini-Hochberg (BH) requires corrections for dependence and self-consistency. A set 𝒮 of p-values is called p-self-consistent [9] at level 𝛼 iff:
max 𝑖∈𝒮
𝑝𝑖≤ |𝒮|𝛼𝑘 . (1)
The BH procedure with input 𝑝1,...,𝑝𝑘 outputs the largest p-self-consistent set w.r.t. the input, which we denote BH[𝛼](𝑝1,...,𝑝𝑘). We must also define a condition on the joint distribution of 𝑃1,...,𝑃𝑘, which is called positive regression dependence on subset (PRDS). A formal definition is provided in Benjamini and Yekutieli [7], and it is sufficient for our purposes to think of this condition as positive dependence between 𝑃1,...,𝑃𝑘, 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 𝒮 = BH[𝛼](𝑝1,...,𝑝𝑘). If 𝑃1,...𝑃𝑘 are PRDS, then FDR(𝒮)≤𝛼. Otherwise, under arbitrary dependence amongst 𝑃1,...𝑃𝑘, the BH procedure ensures FDR(𝒮)≤𝛼ℓ𝑘, where ℓ𝑘≡ ∑︀𝑘 𝑖=11/𝑘≈ log𝑘.
Thus, in the case of arbitrary dependence, the FDR control of BH is larger by a factor of ℓ𝑘 ≈ log𝑘. A larger FDR guarantee is provided for arbitrary p-self-consistent sets.
Fact 2 (P-self-consistent FDR control. Su [38], Blanchard and Roquain [9], Wang and Ramdas [44]). If 𝒮 is p-self-consistent at level 𝛼 and 𝑃1,...,𝑃𝑘 satisfy PRDS, 1 then FDR(𝒮) ≤ 𝛼(1+ log(1/𝛼)). Otherwise, when there is arbitrary dependence among 𝑃1,...,𝑃𝑘, FDR(𝒮)≤𝛼ℓ𝑘 (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 a stronger or equivalent error guarantee under either type of dependence. While it may seem like we should always use BH and the guarantee from Fact 1 to form a rejection set, we elaborate in Section 3.1 on how we can use Fact 2 to provide FDR control for BH when the 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 𝑒1,...,𝑒𝑘 be the realized e-values for a set of e-variables𝐸1,...,𝐸𝑘. Define 𝑒[𝑖] to be the 𝑖th largest e-value for 𝑖∈ [𝑘]. A set 𝒮 is e-self-consistent at level 𝛼 iff 𝒮 satisfies the following:
min 𝑖∈𝒮
𝑒𝑖≥ 𝑘𝛼|𝒮| . (2)
The e-BH procedure outputs the largest e-self-consistent set, which we denote by eBH[𝛼](𝑒1,...,𝑒𝑘). For e-variables, the same guarantee applies for all e-self-consistent sets and under all dependence structures.
Fact 3 (E-variable self-consistency FDR control. Wang and Ramdas [44]). If 𝒮 is e-self-consistent at level 𝛼, then FDR(𝒮)≤𝛼 regardless of the dependence structure. All FDR bounds discussed in Facts 1 to 3 are optimal, in the sense that there exist e-variable/p-variable distributions with an FDR that is arbitrarily close or equivalent to the stated bound. Consequently, e-variables are more advantageous, since their FDR control does not change under different types of
1Su [38] technically employs a slightly weaker condition which implies PRDS, and refers to self-consistency as “compliance” (or, better said, compliance is a special case of self-consistency).
dependence as opposed to the factor of 1+log(1/𝛼) or log𝑘 p-variables pay on the FDR for different settings.
In the case where p-variables can only be constructed as 𝑃 = 1/𝐸, where 𝐸 is an e-variable, the rejection sets output by BH and e-BH are identical. However, the e-self-consistency guarantee in Fact 3 provides identical or tighter FDR control than the BH procedure guarantee in Fact 1 or p-selfconsistency guarantee in Fact 2. Thus, e-variables and e-BH offer a degree of robustness against arbitrary dependence, since any algorithm using e-BH does not have to adjust 𝛼 to guarantee the same level of FDR(𝒮)≤𝛿 for a fixed 𝛿 under different dependence structures. We now provide a meta-algorithm that utilizes p-self-consistency and e-self-consistency to guarantee FDR control in the bandit setting.

heading: 3 Decoupling exploration and evidence: a unified framework
text: We propose a framework for bandit algorithms that separates each algorithm into an exploration component and an evidence component; Algorithm 1 specifies a meta-algorithm combining the two.
Algorithm 1: A meta-algorithm for bandit 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-BH. Input: Exploration component (𝒜𝑡), stopping rule 𝜏*, Let (𝑝1,𝑡),...,(𝑝𝑘,𝑡) and (𝑒1,𝑡),...,(𝑒𝑘,𝑡)
denote the realized values of p-processes and e-processes, respectively. Let the desired level of FDR control be 𝛿∈(0,1). Let 𝛿′ be the correction of 𝛿 for BH based upon the dependencies of 𝑋1,𝑡,...,𝑋𝑘,𝑡. Set 𝐷0 =∅.
for 𝑡 in 1... do ℐ𝑡 :=𝒜𝑡(𝐷𝑡−1)⊆ [𝑘] Obtain rewards for each 𝑖∈ℐ𝑡, and update data 𝐷𝑡 :=𝐷𝑡−1∪{(𝑖,𝑡,𝑋𝑖,𝑡) : 𝑖∈ℐ𝑡}. Update e-process or p-process for each queried arm (summarizing evidence against each null).
𝒮𝑡 := {︂
BH[𝛿′](𝑝1,𝑡,...,𝑝𝑘,𝑡) or arbitrary p-self-consistent set if using p-variables eBH[𝛿](𝑒1,𝑡,...,𝑒𝑘,𝑡) or arbitrary e-self-consistent set if using e-variables
if 𝜏* = 𝑡 then stop and return 𝒮𝑡; end
Exploration component. This is a sequence of functions (𝒜𝑡), where 𝒜𝑡 : ℱ𝑡−1 ↦→ 𝒦 specifies the queried arms ℐ𝑡 := 𝒜𝑡(𝐷𝑡−1), and 𝐷𝑡 := {(𝑖,𝑗,𝑋𝑖,𝑗) : 𝑗 ≤ 𝑡,𝑖∈ ℐ𝑗} is the observed data. 𝒜𝑡 is “non-adaptive” if it does not depend on the data, but only on some external randomness 𝑈 . Regardless of how the exploration component (𝒜𝑡) is constructed, our framework guarantees that FDR(𝒮)≤𝛿 for a fixed 𝛿. Similarly, 𝜏* is adaptive if it depends on the data, and is not determined purely by 𝑈 .
Evidence component. The FDR control provided by Algorithm 1 is solely due to the formulation of the candidate rejection set, 𝒮𝑡⊆ [𝑘], at each time 𝑡∈N in the evidence component. This construction is completely separate from (𝒜𝑡). Critically, (𝒮𝑡) satisfies FDR(𝒮𝜏 )≤𝛿 for any stopping time 𝜏 ∈𝒯 . This is accomplished by applying BH or e-BH to p-processes or e-processes, respectively. At stopping time 𝜏 , 𝑃𝑖,𝜏 is a p-variable when (𝑃𝑖,𝑡) is a p-process, and similarly 𝐸𝑖,𝜏 is an e-variable when (𝐸𝑖,𝑡) is an e-process. Thus, 𝒮𝜏 is the result of applying BH to p-variables or e-BH to e-variables. Consequently, the aforementioned framework allows us to guarantee sup𝜏∈𝒯 FDR(𝒮𝜏 ) ≤ 𝛿 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-variables and e-BH in this framework instead of p-variables and BH.
3.1 FDR control under different dependence structures
In the general combinatorial bandit setting, different dependence structures affect the choice of 𝛿′ that ensures FDR control at 𝛿 in the p-variable and BH case. Table 1 summarizes the guarantees and choices of 𝛿′ for each type of dependence. Prior work on hypothesis testing in the bandit setting by JJ has only considered the non-combinatorial bandit case where 𝑋1,𝑡,...,𝑋𝑘,𝑡 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 𝛼=𝛿 for e-BH is sufficient to guarantee FDR control at level 𝛿 for any type of dependence between e-variables, but only sufficient for BH in the non-adaptive, PRDS 𝑋1,𝑡,...,𝑋𝑘,𝑡 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 𝛿′ in each of these situations such that Algorithm 1 with p-variables can ensure FDR control level 𝛿. We include proofs of all results in this section in Appendix B.1.
Adaptive (𝒜𝑡) and independent 𝑋1,𝑡,...,𝑋𝑘,𝑡. JJ consider this case in the non-combinatorial bandit setting, but their insights and techniques also can be extended to the combinatorial setting. We give a 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 a rejection set that is actually p-self-consistent with a different set of independent p-variables. Define 𝑃 *1 ,...,𝑃 * 𝑘 , where 𝑃 * 𝑖 = inf𝑡∈N𝑃𝑖,𝑡 for each 𝑖∈ [𝑘] i.e. each arm’s p-variable in the infinite sample limit. Since (𝑃𝑖,𝑡) is a p-process for each arm 𝑖∈ [𝑘], the corresponding 𝑃 *𝑖 is a p-variable (Proposition 6 in Appendix A.1). Further, 𝑃 *1 ,...,𝑃 * 𝑘 are independent because 𝑋1,𝑡,...,𝑋𝑘,𝑡 are independent. By definition of 𝑃 *1 ,...,𝑃 * 𝑘 , 𝑝 * 𝑖 ≤ 𝑝𝑖,𝑡 for any 𝑖 ∈ [𝑘] and any 𝑡 ∈ N. Thus, 𝒮𝜏* is p-self-consistent w.r.t. 𝑝*1,...,𝑝 * 𝑘, and has its FDR bounded by 𝛼(1+log(1/𝛼)) due to Fact 2. At the same time, the arbitrary dependence guarantee from Fact 1 still applies. Combining these facts, we achieve the following guarantee: Proposition 1. When (𝒜𝑡) is adaptive and 𝑋1,𝑡, ... , 𝑋𝑘,𝑡 are independent, Algorithm 1 with p-processes and an arbitrary p-self-consistent set guarantees sup𝜏∈𝒯 FDR(𝒮𝜏 )≤𝛿 if 𝛿′≤𝑐𝛿∨𝛿/ℓ𝑘, where for any 𝛿∈(0,1), define 𝑐𝛿≤𝛿 as the solution to 𝑐𝛿(1+log(1/𝑐𝛿))=𝛿. Note that Proposition 1 is valid for any p-self-consistent set since p-self-consistency 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-consistent sets with worse constants (which was subsequently improved by Su [38] as presented earlier), and they only considered the non-combinatorial case. Proposition 1 uses an optimal bound on p-self-consistent sets from Fact 2, and is valid in our combinatorial bandit setup.
Adaptive (𝒜𝑡) and arbitrarily dependent 𝑋1,𝑡,...,𝑋𝑘,𝑡. In the general combinatorial bandit setting, where the algorithm chooses a subset of arms or “superarm” at each time to jointly sample from, we will have multiple samples from multiple arms in the same time step, and 𝑋1,𝑡,...,𝑋𝑘,𝑡 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 1 when using p-variables as a result of Fact 3. Proposition 2. When (𝒜𝑡) is adaptive and 𝑋1,𝑡,...,𝑋𝑘,𝑡 are dependent, Algorithm 1 with p-variables and BH guarantees sup𝜏∈𝒯 FDR(𝒮𝜏 )≤𝛿 if 𝛿′≤𝛿/ℓ𝑘. Finally, consider a setting structured setting where we cannot output the rejection set of BH. Such a constraint often occurs in directed acyclic graph (DAG) settings where there is a hierarchy among hypotheses that restricts which rejection sets are allowed [30, 25]. Instead, we would like to output the largest self-consistent set that respects the structural constraints. By Fact 2, we get the following FDR control. Proposition 3. If (𝒜𝑡) is adaptive and 𝑋1,𝑡,...,𝑋𝑘,𝑡 are dependent, Algorithm 1 with p-variables that outputs an arbitrary p-self-consistent 𝒮𝑡 guarantees sup𝜏∈𝒯 FDR(𝒮𝜏 )≤𝛿 if 𝛿′≤𝑐𝛿/ℓ𝑘.
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 (𝒜𝑡) is adaptive and 𝑋1,𝑡,...,𝑋𝑘,𝑡 are dependent, Algorithm 1 with e-variables, which runs e-BH at level 𝛿 or outputs a e-self-consistent set at level 𝛿, guarantees sup𝜏∈𝒯 FDR(𝒮𝜏 )≤𝛿.
Thus, running e-BH (or any e-self-consistent procedure) at level 𝛿 is valid for any choice of (𝒜𝑡) and type of dependence. Now, we give an example where 𝑋1,𝑡,...,𝑋𝑘,𝑡 might be arbitrarily dependent.

heading: 3.2 Illustrative examples to demonstrate flexibility of the framework
text: Below, we briefly describe a set of nontrivial illustrative examples to showcase the flexibility of our framework. In most of the cases below, a 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 𝑋1,𝑡, ... , 𝑋𝑘,𝑡 may naturally have dependence is when each arm corresponds to a node on a graph. The superarms in this situation 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 is tasked with querying the sensors to 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 a setting, if Proposition 2 is used to guarantee FDR(𝒮)≤ 𝛿 with p-variables, it pays a log𝑘 correction, while Proposition 4 can guarantee e-variables 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.
• Multiple agents (Appendix D.3): Consider the setting where multiple 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 difference between self-consistency guarantees for p-variables and e-variables when a DAG hierarchy is imposed upon the hypotheses.
• 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.1) 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 a high TPR using e-variables when the rewards are independent and sub-Gaussian.

heading: 4 E-process sample complexity guarantees for sub-Gaussian arms
text: 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 (𝒜𝑡) that will have sample complexity bounds matching those of the algorithm in JJ, which uses p-variables. Specifically, we will consider the standard bandit setting where |ℐ𝑡|=1 and 𝜈𝑖 is 1-sub-Gaussian for each 𝑖 ∈ [𝑘]. Denote the means of each arm 𝑖 ∈ [𝑘] as 𝜇𝑖 = E[𝑋𝑖,𝑡] for all 𝑡 ∈ N. The goal is to find many arms where 𝜇𝑖 > 𝜇0, where we set 𝜇0 = 0 to be the mean of a reward distribution under the null hypothesis. Thus, we define ℋ0 = {𝑖 ∈ [𝑘] : 𝜇𝑖 ≤ 𝜇0} and ℋ1 = {𝑖 ∈ [𝑘] : 𝜇𝑖 > 𝜇0}. Our framework ensures that FDR(𝒮) ≤ 𝛿, and we also want to achieve TPR(𝒮)≥1−𝛿 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 𝑡∈N, but the conditional distribution of the rewards still satisfy certain sub-Gaussian guarantees in Appendix G.
Our e-process of choice is the discrete mixture e-process from Howard et al. [16]: Proposition 5. 𝐸DM𝑖,𝑡 is an e-process when 𝜈𝑖 is 1-sub-Gaussian and 𝑖∈ℋ0.
𝐸DM𝑖,𝑡 (𝜇0) := ∞∑︁ ℓ=0 𝑤ℓexp ⎛⎝𝑇𝑖(𝑡)∑︁ 𝑗=1 𝜆ℓ(𝑋𝑖,𝑡𝑖(𝑗)−𝜇0)−𝜆 2 ℓ/2 ⎞⎠, (3a) where 𝜆ℓ := 1𝑒ℓ+5/2 and 𝑤ℓ := 2(𝑒−1) 𝑒(ℓ+2)2 for ℓ∈N0. (3b) Denote ∆𝑖≡𝜇𝑖−𝜇0 for 𝑖∈ℋ1 and ∆≡min𝑖∈ℋ1∆𝑖. When 𝑖∈ℋ0, let ∆𝑖≡min𝑗∈ℋ1𝜇𝑖−𝜇0 =∆+(𝜇𝑖− 𝜇0). First, we recall a time-uniform bound on the sample mean ̂︀𝜇𝑡. Fact 4 (JJ, Kaufmann et al. [23], Howard et al. [16]). Let 𝑋1, 𝑋2, ... be i.i.d. draws from a 1-sub-Gaussian distribution with mean 𝜇. Consider the boundaries defined in (4). Let 𝜙 be one of these boundaries. Then, P(∃𝑡∈N : |̂︀𝜇𝑡−𝜇|>𝜙(𝑡,𝛿))≤𝛿 for any 𝛿∈(0,1) if 𝜙∈{𝜙0,𝜙IS} and any 𝛿∈(0,0.1] if 𝜙=𝜙JJ.
𝜙0(𝑡,𝛿) :=
√︁ 4log(log2(2𝑡)/𝛿)
𝑡 , (4a)
𝜙JJ(𝑡,𝛿) :=
√︁ 2log(1/𝛿)+6loglog(1/𝛿)+3log(log(𝑒𝑡/2))
𝑡 , (4b)
𝜙IS(𝑡,𝛿) :=
√︂ 2.89loglog(2.041𝑡)+2.065log( 4.983𝛿 )
𝑡 . (4c) We will use 𝜙 to refer to an arbitrary boundary from Fact 4. All of the𝜙 are time-uniform boundaries that yield confidence sequences for the mean. Note that 𝜙0 is generally larger than the other boundaries, so we use 𝜙0 as the default boundary in our proofs, and we explore how different choices of 𝜙 affect empirical performance in Appendix E.1. 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 a singleton set ℐ𝑡 ={𝐼𝑡}) and a p-variable derived from Fact 4. In (5a), we denote the sample mean at time 𝑡 of each arm 𝑖 ∈ [𝑘] by ̂︀𝜇𝑖,𝑡. Let 𝑓 . 𝑔 denote 𝑓 asymptotically dominates 𝑔 i.e. there exist 𝑐>0 that is independent of the problem parameters such that 𝑓≤𝑐𝑔. JJ prove the following sample complexity guarantee for their algorithm. Fact 5 (From JJ). Let (𝒜𝑡) output ℐ𝑡 ={𝐼𝑡}, and let 𝐼𝑡 and𝑃𝑖,𝑡 be specified by Alg. 5 with𝜙=𝜙0. Then, Algorithm 1 will always guarantee sup𝜏∈𝒯 FDR(𝒮𝜏 )≤𝛿. With at least 1−𝛿 probability, there will exist 𝑇 . (︁∑︀𝑘 𝑖=1∆ −2 𝑖 loglog∆ −2 𝑖 +∆ −2 𝑖 log(𝑘/𝛿) )︁ ∧𝑘∆−2log(log(∆−2)/𝛿) such that TPR(𝒮𝑡)≥1−𝛿 for all 𝑡≥𝑇 .
𝐼𝑡 =argmax𝑖∈[𝑘]∖𝒮𝑡−1̂︀𝜇𝑖,𝑡−1+𝜙(𝑇𝑖(𝑡−1),𝛿), (5a) 𝑃𝑖,𝑡≡ inf{𝜌∈ [0,1] : |̂︀𝜇𝑖,𝑡−𝜇0|>𝜙(𝑡,𝜌)}. (5b) We show that we can match the sample complexity bounds of Fact 5 with e-variables. Theorem 1. Let 𝜈𝑖 be 1-sub-Gaussian for 𝑖∈ [𝑘]. Set (𝒜𝑡) so 𝒜𝑡 outputs {𝐼𝑡} from (5a) for all 𝑡 ∈N and 𝐸𝑖,𝑡 to 𝐸DM𝑖,𝑡 . Algorithm 1 ensures sup𝜏∈𝒯 FDR(𝒮𝜏 ) ≤ 𝛿 and, with at least 1− 𝛿 probability, there exists 𝑇 . (︁∑︀𝑘 𝑖=1∆ −2 𝑖 loglog∆ −2 𝑖 +∆ −2 𝑖 log(𝑘/𝛿) )︁ ∧𝑘∆−2log(log(∆−2)/𝛿) such that TPR(𝒮𝑡)≥1−𝛿 for all 𝑡≥𝑇 .
In addition to matching theoretical guarantees, we show in the following section that e-variables and e-BH perform empirically as well or better than p-variables and BH through numerical simulations.

heading: 5 Numerical simulations
text: We perform simulations for the sub-Gaussian setting discussed in Section 4 to demonstrate that our version of Algorithm 1 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 use a corrected level 𝛿′ based upon the dependence assumptions among 𝑋1,𝑡,...,𝑋𝑘,𝑡 to guarantee FDR is controlled at level 𝛿. We explore additional simulations of combinatorial semi-bandit settings with dependent 𝑋1,𝑡,...,𝑋𝑘,𝑡 in Appendix E that show the benefit of using e-variables over p-variables in our framework.
Simulation setup Let 𝜈𝑖 =𝒩 (𝜇𝑖,1) where 𝜇𝑖 =𝜇0 =0 if 𝑖∈ℋ0 and 𝜇𝑖 =1/2 if 𝑖∈ℋ1. We consider 3 setups, where we set the number of non-null hypotheses to be |ℋ1|=2,log𝑘, and √ 𝑘, 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 is (5b), which is the same as JJ. Like JJ, we set 𝜙=𝜙JJ in our simulations. When using e-BH, we set our e-variables to 𝐸PM-H𝑖,𝑡 := ∏︀𝑇𝑖(𝑡) 𝑗=1 exp(𝜆𝑖,𝑡𝑖(𝑗)(𝑋𝑖,𝑡𝑖(𝑗)−𝜇0)−𝜆2𝑖,𝑡𝑖(𝑗)/2)
with 𝜆𝑖,𝑡 = √︁
2log(2/𝛼) 𝑇𝑖(𝑡)log(𝑇𝑖(𝑡)+1) , which is the default choice of 𝜆𝑖,𝑡 suggested in Waudby-Smith and Ramdas [45]. We show that this is a valid e-process in Appendix F and maintains FDR control.
Results We plot the relative performance of each method to e-BH with UCB sampling in Figure 2. For uniform sampling, e-BH and e-variables seem to outperform BH and p-variables, although by a decreasing margin for more arms, especially in the case where |ℋ1|=⌊ √ 𝑘⌋. For the UCB sampling algorithm, we see that e-variables and p-variables have relatively similar performance, with the gap narrowing as 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-variables also work well. Further, evariables do not require the same log𝑘 correction that p-variables need for situations where𝑋1,𝑡,...,𝑋𝑘,𝑡 are arbitrarily dependent to guarantee FDR control at the same level. Thus, e-variables are preferable to p-variables as they are more flexible w.r.t. assumptions.

heading: 6 Conclusion, limitations and broader impact
text: 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 𝑋1,𝑡,...,𝑋𝑘,𝑡, exploration strategy, stopping time of the algorithm, ability to query multiple arms, etc. In contrast, existing algorithms using BH and 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-variables can blow up by a factor of log𝑘, and any p-selfconsistent algorithm must decrease its threshold for discovery correspondingly to maintain FDR control 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-Gaussian reward setting, the instantiated algorithm matches the sample complexity bounds of the p-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 e-processes and our general framework. In fact, we can address an even more general setting where 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.
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 a difficult open problem, requiring specialized techniques in each example. We do not foresee any negative societal impact of this work; it is aimed at reducing costs and improving reproducibility in scientific experimentation by controlling false discoveries in adaptive testing.
Acknowledgments RW acknowledges funding from NSERC RGPIN-2018-03823 and RGPAS2018-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 W911NF-17-2-0196 (ARL IoBTCRA). The views and conclusions contained 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.

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

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