Multi-armed Bandit Problems with History
Multi-armed Bandit Problems with History
复制标题
历史上的多臂强盗问题
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
T. Joachims
中科院分区：
文献类型：
--
作者：
Pannagadatta K. Shivaswamy;T. Joachims
本文研究随机多臂强盗问题。然而，与这个问题的传统版本不同，我们不假设算法从头开始。许多应用程序甚至在算法开始之前就提供了对（一些）手臂的观察。我们提出了三种新的多臂强盗算法，可以利用这些数据。在每种情况下，上界的遗憾。结果表明，对数数量的历史数据可以减少后悔从对数到常数。在一个大规模的恶意URL检测问题上证明了所提算法的有效性。
In this paper we consider the stochastic multi-armed bandit problem. However, unlike in the conventional version of this problem, we do not assume that the algorithm starts from scratch. Many applications offer observations of (some of) the arms even before the algorithm starts. We propose three novel multi-armed bandit algorithms that can exploit this data. An upper bound on the regret is derived in each case. The results show that a logarithmic amount of historic data can reduce regret from logarithmic to constant. The eectiveness of the proposed algorithms are demonstrated on a large-scale malicious URL detection problem.