Finite-time analysis of the multiarmed bandit problem
Finite-time analysis of the multiarmed bandit problem
复制标题
DOI：
10.1023/a:1013689704352
复制
发表时间：
2002-01-01
期刊：
影响因子：
7.5
通讯作者：
Fischer, P
中科院分区：
文献类型：
--
作者：
Auer, P;Cesa-Bianchi, N;Fischer, P
强化学习策略面临探索与利用的困境，即在探索环境以找到有利可图的行动与尽可能多地采取经验最佳行动之间寻求平衡。衡量一项政策在解决这一困境方面是否成功的常用标准是“遗憾”，即由于没有始终遵循全局最优政策而造成的损失。关于探索/开发困境的一个最简单的例子便是多武装土匪问题。Lai和Robbins是第一个证明这个问题的遗憾至少在游戏数量上呈对数增长的人。从那时起，赖和罗宾斯以及其他许多人制定了逐步实现这一遗憾的政策。在这项工作中，我们证明了最优对数后悔也可以随着时间的推移统一实现，使用简单有效的策略，并且对于所有有界支持的奖励分布。
Reinforcement learning policies face the exploration versus exploitation dilemma, i.e. the search for a balance between exploring the environment to find profitable actions while taking the empirically best action as often as possible. A popular measure of a policy's success in addressing this dilemma is the regret, that is the loss due to the fact that the globally optimal policy is not followed all the times. One of the simplest examples of the exploration/exploitation dilemma is the multi-armed bandit problem. Lai and Robbins were the first ones to show that the regret for this problem has to grow at least logarithmically in the number of plays. Since then, policies which asymptotically achieve this regret have been devised by Lai and Robbins and many others. In this work we show that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.