Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards
Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards
复制标题
一种新的半有界奖励老虎机算法的非渐近分析
DOI：
--
复制
发表时间：
2015
影响因子：
6
通讯作者：
A. Takemura
中科院分区：
文献类型：
--
作者：
J. Honda;A. Takemura
本文考虑随机多臂强盗问题。在这个问题中，已知确定性最小经验发散（DMED）策略实现了模型的渐近理论界，其中每个奖励分布都支持在已知的有界区间内，比如[0; 1]。然而，DMED的遗憾界是以渐近形式描述的，在有限时间内的性能一直是未知的。我们修改这一政策，并得出一个有限的时间后悔的新政策，指数最小经验分歧（IMED），通过精炼大偏差概率到一个简单的非渐近形式。此外，精细的分析表明，有限时间的遗憾界是有效的，即使在情况下，奖励是没有界的从下面。因此，我们的有限时间结果适用于最小回报（即最大损失）未知或无界的情况。我们还提出了一些模拟结果表明，IMED大大提高DMED和执行竞争力的其他国家的最先进的政策。
In this paper we consider a stochastic multiarmed bandit problem. It is known in this problem that Deterministic Minimum Empirical Divergence (DMED) policy achieves the asymptotic theoretical bound for the model where each reward distribution is supported in a known bounded interval, say [0; 1]. However, the regret bound of DMED is described in an asymptotic form and the performance in finite time has been unknown. We modify this policy and derive a finite-time regret bound for the new policy, Indexed Minimum Empirical Divergence (IMED), by refining large deviation probabilities to a simple nonasymptotic form. Further, the refined analysis reveals that the finite-time regret bound is valid even in the case that the reward is not bounded from below. Therefore, our finite-time result applies to the case that the minimum reward (that is, the maximum loss) is unknown or unbounded. We also present some simulation results which shows that IMED much improves DMED and performs competitively to other state-of-the-art policies.