A Bandit Approach to Multiple Testing with False Discovery Control

Abstract

We propose an adaptive sampling approach for multiple testing which aims to maximize statistical power while ensuring anytime false discovery control. We consider $n$ distributions whose means are partitioned by whether they are below or equal to a baseline (nulls), versus above the baseline (actual positives). In addition, each distribution can be sequentially and repeatedly sampled. Inspired by the multi-armed bandit literature, we provide an algorithm that takes as few samples as possible to exceed a target true positive proportion (i.e. proportion of actual positives discovered) while giving anytime control of the false discovery proportion (nulls predicted as actual positives). Our sample complexity results match known information theoretic lower bounds and through simulations we show a substantial performance improvement over uniform sampling and an adaptive elimination style algorithm. Given the simplicity of the approach, and its sample efficiency, the method has promise for wide adoption in the biological sciences, clinical testing for drug discovery, and online A/B/n testing problems.

References in corpus (7)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• An optimal algorithm for the Thresholding Bandit Problem
• Always Valid Inference: Bringing Sequential Analysis to A/B Testing
• Towards Instance Optimal Bounds for Best Arm Identification
• Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime

Cited by in corpus (7)

• Time-uniform, nonparametric, nonasymptotic confidence sequences
• Asynchronous Online Testing of Multiple Hypotheses
• Comparing Sequential Forecasters
• Finding All ε-Good Arms in Stochastic Bandits
• The True Sample Complexity of Identifying Good Arms
• Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits
• Nearest Neighbor Search Under Uncertainty