Multi-armed bandit algorithms and empirical evaluation
Multi-armed bandit algorithms and empirical evaluation
复制标题
DOI：
10.1007/11564096_42
复制
发表时间：
2005-01-01
期刊：
影响因子：
--
通讯作者：
Mohri, M
中科院分区：
文献类型：
--
作者：
Vermorel, J;Mohri, M
对于一个赌徒来说，多手强盗问题是决定在一系列试验中拉动k -老虎机的哪只手以使他的总奖励最大化。许多现实世界的学习和优化问题都可以用这种方式建模。在过去的二十年里，已经提出了几种策略或算法来解决这个问题，但是，据我们所知，这些算法还没有共同的评估。本文对几种多臂强盗算法进行了初步的实证评价。本文还描述和分析了一种新的算法，扑克（知识价格和估计奖励），该算法在几个实验中表现优于其他现有算法。我们实验的一个显著结果是，最幼稚的方法，即E-greedy策略，往往被证明是难以击败的。
The multi-armed bandit problem for a gambler is to decide which arm of a K-slot machine to pull to maximize his total reward in a series of trials. Many real-world learning and optimization problems can be modeled in this way. Several strategies or algorithms have been proposed as a solution to this problem in the last two decades, but, to our knowledge, there has been no common evaluation of these algorithms.This paper provides a preliminary empirical evaluation of several multi-armed bandit algorithms. It also describes and analyzes a new algorithm, POKER (Price Of Knowledge and Estimated Reward) whose performance compares favorably to that of other existing algorithms in several experiments. One remarkable outcome of our experiments is that the most naive approach, the E-greedy strategy, proves to be often hard to beat.