# Greedy Approximation Algorithms for Active Sequential Hypothesis Testing

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 45 references that are in the map.
- First posted on arXiv 7 Mar 2021.

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

- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing](https://mlsanity.com/paper/1807.06168/) (2018)
- [Causal Inference With Selectively Deconfounded Data](https://mlsanity.com/paper/2002.11096/) (2020)

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

- [Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models](https://mlsanity.com/paper/2405.14496/) (2024)
- [Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes](https://mlsanity.com/paper/2312.15357/) (2023)
- [Online Learning of Optimal Sequential Testing Policies](https://mlsanity.com/paper/2509.03707/) (2025)
- [On Cost-Aware Designs for Sequential Hypothesis Testing](https://mlsanity.com/paper/2512.19067/) (2025)
- [Finite-Sample Analysis of Elimination in Active Hypothesis Testing](https://mlsanity.com/paper/2605.01039/) (2026)

## Abstract (arXiv)

In the problem of active sequential hypothesis testing (ASHT), a learner seeks to identify the true hypothesis from among a known set of hypotheses. The learner is given a set of actions and knows the random distribution of the outcome of any action under any true hypothesis. Given a target error δ>0, the goal is to sequentially select the fewest number of actions so as to identify the true hypothesis with probability at least 1 - δ. Motivated by applications in which the number of hypotheses or actions is massive (e.g., genomics-based cancer detection), we propose efficient (greedy, in fact) algorithms and provide the first approximation guarantees for ASHT, under two types of adaptivity. Both of our guarantees are independent of the number of actions and logarithmic in the number of hypotheses. We numerically evaluate the performance of our algorithms using both synthetic and real-world DNA mutation data, demonstrating that our algorithms outperform previously proposed heuristic policies by large margins.