Finite-Sample Analysis of Elimination in Active Hypothesis Testing
Ziyuan Lin, Hoang Ngoc Nguyen, Jie Xu, Ivan Ruchkin · 2026
Read Finite-Sample Analysis of Elimination in Active Hypothesis Testing by Ziyuan Lin, Hoang Ngoc Nguyen, Jie Xu, Ivan Ruchkin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-01039.txt.
Description
Ziyuan Lin and three co-authors analyze how removing options affects active hypothesis testing, where a decision maker gathers evidence step by step to identify the true option with fixed confidence. Such problems arise in safety-critical settings. Their pruning-augmented Track-and-Stop algorithm prunes active opponent sets for each champion over time and reallocates sensing effort toward surviving alternatives.
The analysis gives a non-asymptotic upper bound on expected stopping time. Finite-sample gains from pruning appear in the non-leading term, through tighter tracking and concentration on the reduced set. An aggressiveness setting trades faster pruning against weaker confidence guarantees. Experiments on synthetic Gaussian instances confirm the theoretical predictions.
Catalog record
| CREATOR | Ziyuan Lin, Hoang Ngoc Nguyen, Jie Xu, Ivan Ruchkin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.01039