BriefGPT.xyz
Jun, 2019
具有无限制延迟的非随机多臂赌博机
Nonstochastic Multiarmed Bandits with Unrestricted Delays
HTML
PDF
Tobias Sommer Thune, Nicolò Cesa-Bianchi, Yevgeny Seldin
TL;DR
本文研究带有延迟反馈的多臂老虎机问题,证明了先前的算法在延迟是变量但有上界的情况下具有较好的表现,提出了一种新算法通过一个跳过具有过度大延迟的步骤的 wrapper 来降低了对上界的要求,同时构造了一种新的加倍方案,从而放宽了对时间和延迟知识的要求。提出的算法解决了丰富的应用场景问题并达到了合理的预期表现。
Abstract
We investigate
multiarmed bandits
with
delayed feedback
, where the delays need neither be identical nor bounded. We first prove that the "delayed" Exp3 achieves the $O(\sqrt{(KT + D)\ln K})$
→