# Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits

arXiv: https://arxiv.org/abs/1902.00197 · HTML: https://mlsanity.com/paper/1902.00197/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2019.

## Built on by (most cited first, 6 of 6)

- [Approximate Function Evaluation via Multi-Armed Bandits](https://mlsanity.com/paper/2203.10124/) (2022)
- [MABSplit: Faster Forest Training Using Multi-Armed Bandits](https://mlsanity.com/paper/2212.07473/) (2022)
- [Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits](https://mlsanity.com/paper/2211.01743/) (2022)
- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [Adaptive Data Depth via Multi-Armed Bandits](https://mlsanity.com/paper/2211.03985/) (2022)
- [Finite Resources False Discovery Rate Control in Structured Hypothesis Spaces](https://mlsanity.com/paper/2606.15393/) (2026)

## Abstract (arXiv)

Monte Carlo (MC) permutation test is considered the gold standard for statistical hypothesis testing, especially when standard parametric assumptions are not clear or likely to fail. However, in modern data science settings where a large number of hypothesis tests need to be performed simultaneously, it is rarely used due to its prohibitive computational cost. In genome-wide association studies, for example, the number of hypothesis tests m is around 106 while the number of MC samples n for each test could be greater than 108, totaling more than nm=1014 samples. In this paper, we propose Adaptive MC multiple Testing (AMT) to estimate MC p-values and control false discovery rate in multiple testing. The algorithm outputs the same result as the standard full MC approach with high probability while requiring only tildeO(√nm) samples. This sample complexity is shown to be optimal. On a Parkinson GWAS dataset, the algorithm reduces the running time from 2 months for full MC to an hour. The AMT algorithm is derived based on the theory of multi-armed bandits.