Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls
Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls
复制标题
通过批量手臂拉动进行多臂强盗中的上臂识别
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Xiaojin Zhu
中科院分区：
文献类型：
--
作者：
Kwang;Kevin G. Jamieson;R. Nowak;Xiaojin Zhu
我们介绍了一个新的多军匪徒（MAB）问题，其中必须分批对武器进行采样，而不是一次。这是由社交媒体监测和生物学实验中的应用自然出现的。本文为固定的置信度和固定的预算设置开发和分析了批次mAB和顶部识别算法。我们的主要理论结果表明，与无约束的mAB算法相比，批处理约束并未显着影响顶臂识别的样品复杂性。另外，如果人们将批次视为基本抽样单元，则可以将结果解释为表明批处理mAb的样本复杂性可能比传统mab明显少得多。我们在两个有趣的现实世界应用中演示了新的批处理mAb算法：（i）用于识别在病毒复制中很重要的基因的微孔阵列实验，以及（ii）在特定主题中找到Twitter中最活跃的用户。
We introduce a new multi-armed bandit (MAB) problem in which arms must be sampled in batches, rather than one at a time. This is motivated by applications in social media monitoring and biological experimentation where such batch constraints naturally arise. This paper develops and analyzes algorithms for batch MABs and top arm identification, for both fixed confidence and fixed budget settings. Our main theoretical results show that the batch constraint does not significantly affect the sample complexity of top arm identification compared to unconstrained MAB algorithms. Alternatively, if one views a batch as the fundamental sampling unit, then the results can be interpreted as showing that the sample complexity of batch MABs can be significantly less than traditional MABs. We demonstrate the new batch MAB algorithms with simulations and in two interesting real-world applications: (i) microwell array experiments for identifying genes that are important in virus replication and (ii) finding the most active users in Twitter on a specific topic.