Abstract:We consider the framework of Sequential Hypothesis Testing (SHT), in which a decision maker (DM) selects actions that generate samples from known, action-dependent distributions, while the realized distribution is determined by an unknown true hypothesis. To identify this hypothesis, we adopt the elimination perspective and propose three deterministic, adaptive, multi-iteration algorithms with a common structure, termed $\Phi$, $\Phi$-$\Delta$, and $I$. In each iteration, the DM selects an action and repeatedly applies it to collect samples, after which hypotheses inconsistent with the observed data are eliminated. The algorithms differ in the criterion used to terminate each iteration: $\Phi$ continues until one hypothesis dominates all others; $\Phi$-$\Delta$ first clusters hypotheses whose per-action distributions are close in total variation and then proceeds in the spirit of $\Phi$; $I$ continues until one hypothesis can be safely discarded.
We analyze our algorithms, establishing: (i) controlled error-rates, (ii) controlled sample complexity, (iii) asymptotic optimality, (iv) computational complexity, and (v) NP-hardness of the optimal action-sequence selection for minimal sample complexity.
From: George Vershinin [view email]
[v1]
Tue, 30 Sep 2025 07:52:46 UTC (379 KB)
[v2]
Tue, 30 Jun 2026 13:13:42 UTC (419 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。