Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Chung-Wei Lee;Haipeng Luo;Chen-Yu Wei;Mengxiao Zhang
中科院分区：
文献类型：
--
作者：
Chung-Wei Lee;Haipeng Luo;Chen-Yu Wei;Mengxiao Zhang
我们开发了一种新的方法，以获得高概率的遗憾界的在线学习与强盗反馈对自适应对手。虽然现有的方法都需要仔细构建乐观和有偏的损失估计，我们的方法使用标准的无偏估计，并依赖于一个简单的学习率增加的时间表，连同帮助的congrammically同质的自我和谐的障碍和加强弗里德曼的不等式。除了它的简单性，我们的方法享有几个优点。首先，获得的高概率后悔界限是数据依赖的，可能比最坏情况下的界限小得多，这解决了Neu（2015）提出的一个开放问题。其次，解决Bartlett et al.（2008）和Abernethy and Rakhlin（2009）的另一个开放问题，我们的方法导致了第一个通用且有效的算法，具有对抗性线性强盗的高概率后悔界，而以前的方法要么效率低下，要么只适用于特定的动作集。最后，我们的方法也可以应用于学习对抗马尔可夫决策过程，并为这个问题提供了第一个具有高概率小损失界的算法。
We develop a new approach to obtaining high probability regret bounds for online learning with bandit feedback against an adaptive adversary. While existing approaches all require carefully constructing optimistic and biased loss estimators, our approach uses standard unbiased estimators and relies on a simple increasing learning rate schedule, together with the help of logarithmically homogeneous self-concordant barriers and a strengthened Freedman's inequality. Besides its simplicity, our approach enjoys several advantages. First, the obtained high-probability regret bounds are data-dependent and could be much smaller than the worst-case bounds, which resolves an open problem asked by Neu (2015). Second, resolving another open problem of Bartlett et al. (2008) and Abernethy and Rakhlin (2009), our approach leads to the first general and efficient algorithm with a high-probability regret bound for adversarial linear bandits, while previous methods are either inefficient or only applicable to specific action sets. Finally, our approach can also be applied to learning adversarial Markov Decision Processes and provides the first algorithm with a high-probability small-loss bound for this problem.