A unified framework for bandit multiple testing
A unified framework for bandit multiple testing
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Ziyu Xu;Ruodu Wang;Aaditya Ramdas
中科院分区：
文献类型：
--
作者：
Ziyu Xu;Ruodu Wang;Aaditya Ramdas
在bandit多重假设检验中，每个分支对应于我们希望测试的不同零假设，目标是设计自适应算法，正确识别大量有趣的分支（真正的发现），同时只错误地识别少数不感兴趣的分支（错误的发现）。非强盗多重测试中的一个常见度量是错误发现率（FDR）。我们提出了一个统一的，模块化的框架，强盗FDR控制，强调解耦的探索和总结的证据。我们利用强大的鞅为基础的概念，“e-过程”，以确保FDR控制任意复合空值，勘探规则和停止时间在一般的问题设置。特别是，有效的FDR控制保持，即使臂的奖励分布可能是依赖的，多个臂可以同时查询，并且多个（合作或竞争）代理可以查询臂，也覆盖组合半强盗类型设置。先前的工作已经非常详细地考虑了每个手臂的奖励分布是独立的和亚高斯的设置，并且在每个步骤中查询单个手臂。我们的框架恢复匹配样本的复杂性保证在这种特殊情况下，并在实践中表现更好。对于其他设置，样本复杂性将取决于问题的更精细的细节（测试的复合空值，探索算法，数据依赖结构，停止规则），我们不探索这些;我们的贡献是表明FDR保证是干净的，完全不可知的这些细节。
In bandit multiple hypothesis testing, each arm corresponds to a different null hypothesis that we wish to test, and the goal is to design adaptive algorithms that correctly identify large set of interesting arms (true discoveries), while only mistakenly identifying a few uninteresting ones (false discoveries). One common metric in non-bandit multiple testing is the false discovery rate (FDR). We propose a unified, modular framework for bandit FDR control that emphasizes the decoupling of exploration and summarization of evidence. We utilize the powerful martingale-based concept of"e-processes"to ensure FDR control for arbitrary composite nulls, exploration rules and stopping times in generic problem settings. In particular, valid FDR control holds even if the reward distributions of the arms could be dependent, multiple arms may be queried simultaneously, and multiple (cooperating or competing) agents may be querying arms, covering combinatorial semi-bandit type settings as well. Prior work has considered in great detail the setting where each arm's reward distribution is independent and sub-Gaussian, and a single arm is queried at each step. Our framework recovers matching sample complexity guarantees in this special case, and performs comparably or better in practice. For other settings, sample complexities will depend on the finer details of the problem (composite nulls being tested, exploration algorithm, data dependence structure, stopping rule) and we do not explore these; our contribution is to show that the FDR guarantee is clean and entirely agnostic to these details.