# A Regret Perspective on Online Multiple Testing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 43 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 29 of 29)

- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Tracking the risk of a deployed model and detecting harmful distribution shifts](https://mlsanity.com/paper/2110.06177/) (2021)
- [Experimental Design in Two-Sided Platforms: An Analysis of Bias](https://mlsanity.com/paper/2002.05670/) (2020)
- [Online Rules for Control of False Discovery Rate and False Discovery Exceedance](https://mlsanity.com/paper/1603.09000/) (2016)
- [A framework for Multi-A(rmed)/B(andit) testing with online FDR control](https://mlsanity.com/paper/1706.05378/) (2017)
- [Online control of the false discovery rate with decaying memory](https://mlsanity.com/paper/1710.00499/) (2017)
- [SAFFRON: an adaptive algorithm for online control of the false discovery rate](https://mlsanity.com/paper/1802.09098/) (2018)
- [Online multiple testing with e-values](https://mlsanity.com/paper/2311.06412/) (2023)
- [CAP: A General Algorithm for Online Selective Conformal Prediction with FCR Control](https://mlsanity.com/paper/2403.07728/) (2024)
- [ADDIS: an adaptive discarding algorithm for online FDR control with conservative nulls](https://mlsanity.com/paper/1905.11465/) (2019)
- [Asynchronous Online Testing of Multiple Hypotheses](https://mlsanity.com/paper/1812.05068/) (2018)
- [A unified framework for bandit multiple testing](https://mlsanity.com/paper/2107.07322/) (2021)
- [Online control of the familywise error rate](https://mlsanity.com/paper/1910.04900/) (2019)
- [Contextual Online False Discovery Rate Control](https://mlsanity.com/paper/1902.02885/) (2019)
- [An online generalization of the (e-)Benjamini-Hochberg procedure](https://mlsanity.com/paper/2407.20683/) (2024)
- [Dynamic Algorithms for Online Multiple Testing](https://mlsanity.com/paper/2010.13953/) (2020)
- [Online multiple hypothesis testing](https://mlsanity.com/paper/2208.11418/) (2022)
- [More powerful multiple testing under dependence via randomization](https://mlsanity.com/paper/2305.11126/) (2023)
- [Lie to Me: Knowledge Graphs for Robust Hallucination Self-Detection in LLMs](https://mlsanity.com/paper/2512.23547/) (2025)
- [Online multiple testing with super-uniformity reward](https://mlsanity.com/paper/2110.01255/) (2021)
- [Structure-Adaptive Sequential Testing for Online False Discovery Rate Control](https://mlsanity.com/paper/2003.00113/) (2020)
- [The Online Closure Principle](https://mlsanity.com/paper/2211.11400/) (2022)
- [False Discovery Rate Control For Structured Multiple Testing: Asymmetric Rules And Conformal Q-values](https://mlsanity.com/paper/2311.15322/) (2023)
- [e-GAI: e-value-based Generalized α-Investing for Online False Discovery Rate Control](https://mlsanity.com/paper/2506.01452/) (2025)
- [SCORE: A Unified Framework for Overshoot Refund in Online FDR Control](https://mlsanity.com/paper/2601.20386/) (2026)
- [Synthetic-Powered Multiple Testing with FDR Control](https://mlsanity.com/paper/2602.16690/) (2026)

## Abstract (arXiv)

Online Multiple Testing (OMT), a fundamental pillar of sequential statistical inference, traditionally evaluates the False Discovery Rate (FDR) and statistical power in isolation, obscuring the highly asymmetric costs of false positives and false negatives in modern automated pipelines. To unify this evaluation, we introduce textitWeighted Regret. Under this metric, we prove the textitDuality of Regret Conservation: purely deterministic procedures ensuring strict FDR control inevitably incur an Omega(T) linear regret penalty, as threshold depletion during signal-sparse cold starts forces massive false negatives. Tailored for exogenous testing streams, we propose Decoupled-OMT (DOMT) as a baseline-agnostic meta-wrapper. By incorporating a history-decoupled, strictly non-negative random perturbation, DOMT rescues purely deterministic baselines from severe threshold depletion. Crucially, it preserves exact asymptotic safety in stationary environments and rigorously bounds finite-sample error inflation during cold-starts. Guaranteeing zero additional false negatives, it yields an order-optimal Omega(√T) regret reduction in bursty environments, with a derived ``Cold-Start Tax'' characterizing the exact phase transition of algorithmic superiority. Experiments validate that DOMT consistently curtails empirical weighted regret, achieving an order-optimal sublinear mitigation of threshold depletion to navigate the non-stationary Pareto frontier.