提出更高效算法解决主动假设检验问题，理论表现接近最优。
Towards minimax optimal algorithms for Active Simple Hypothesis Testing
- 用微分博弈与偏微分方程构建上界新框架
- 新算法数值表现逼近最优指数，计算效率显著提升
- 适合关注最优性与计算效率平衡的研究者
我们研究主动简单假设检验（ASHT）问题，这是固定预算最优臂识别问题的一个简化版本。本文提出了该问题上界的新博弈论形式化方法，使我们能够借助微分博弈和偏微分方程工具，设计出一种在计算上可处理的近似最优算法。然而，该最优算法仍受维数灾难影响；为此，我们建立与布莱克韦尔可实现性的新联系，提出一种计算效率更高的算法。虽然尚未证明其最优性，但该算法在所有ASHT实例中均优于静态策略，且在多个实例中数值表现达到最优指数。
原文摘要 · Abstract (English)
We study the Active Simple Hypothesis Testing (ASHT) problem, a simpler variant of the Fixed Budget Best Arm Identification problem. In this work, we provide novel game theoretic formulation of the upper bounds of the ASHT problem. This formulation allows us to leverage tools of differential games and Partial Differential Equations (PDEs) to propose an approximately optimal algorithm that is computationally tractable compared to prior work. However, the optimal algorithm still suffers from a curse of dimensionality and instead we use a novel link to Blackwell Approachability to propose an algorithm that is far more efficient computationally. We show that this new algorithm, although not proven to be optimal, is always better than static algorithms in all instances of ASHT and is numerically observed to attain the optimal exponent in various instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。