An asymptotically optimal policy for finite support models in the multiarmed bandit problem
An asymptotically optimal policy for finite support models in the multiarmed bandit problem
复制标题
DOI：
10.1007/s10994-011-5257-4
复制
发表时间：
2011-12-01
期刊：
影响因子：
7.5
通讯作者：
Takemura, Akimichi
中科院分区：
文献类型：
--
作者：
Honda, Junya;Takemura, Akimichi
在多臂强盗问题中，强化学习中探索和剥削之间的困境被表达为一个赌徒玩多臂老虎机的模型。一个策略在每一轮中选择一个手臂，以便最小化具有次优预期奖励的手臂被拉动的次数。我们提出了最小经验分歧（MED）政策，并推导出一个上界的有限时间后悔满足的情况下，有限支持模型的渐近界。在类似于我们的设置，Burnetas和Katehakis已经提出了一个渐近最优的政策。然而，我们不假设任何知识的支持，除了其上限和下限。此外，选择手臂的标准，最小的经验分歧，可以很容易地通过凸优化技术计算。我们通过模拟证实，MED政策在有限时间内表现出良好的性能相比，其他目前流行的政策。
In the multiarmed bandit problem the dilemma between exploration and exploitation in reinforcement learning is expressed as a model of a gambler playing a slot machine with multiple arms. A policy chooses an arm in each round so as to minimize the number of times that arms with suboptimal expected rewards are pulled. We propose the minimum empirical divergence (MED) policy and derive an upper bound on the finite-time regret which meets the asymptotic bound for the case of finite support models. In a setting similar to ours, Burnetas and Katehakis have already proposed an asymptotically optimal policy. However, we do not assume any knowledge of the support except for its upper and lower bounds. Furthermore, the criterion for choosing an arm, minimum empirical divergence, can be computed easily by a convex optimization technique. We confirm by simulations that the MED policy demonstrates good performance in finite time in comparison to other currently popular policies.