标题： 适应对抗性多臂老虎机中的延迟和数据 显示英文标题

标题： Adapting to Delays and Data in Adversarial Multi-Armed Bandits

摘要： 我们考虑在延迟反馈下的对抗性多臂老虎机问题。 我们分析了使用仅在决策时可用的信息（关于损失和延迟）来调整步长的Exp3算法变体，并获得了适应于观察到的（而非最坏情况的）延迟和/或损失序列的遗憾保证。 首先，通过一种令人惊讶的简单证明技术，我们表明，通过适当的步长调整，该算法在期望和高概率下都能达到最优（对数因子以外）的遗憾，其阶数为$\sqrt{\log(K)(TK + D)}$，其中$K$是手臂的数量，$T$是时间范围，$D$是累计延迟。 高概率版本的界限是文献中第一个高概率的延迟自适应界限，它关键地依赖于在估计损失时使用隐式探索。 然后，遵循 Zimmert 和 Seldin [2019]，我们扩展了这些结果，使算法能够“跳过”具有大延迟的回合，从而得到阶数为$\sqrt{TK\log(K)} + |R| + \sqrt{D_{\bar{R}}\log(K)}$的遗憾界限，其中$R$是任意一组被跳过的回合，$D_{\bar{R}}$是其他回合的反馈的累计延迟。 最后，我们提出了另一种数据自适应（AdaGrad风格）的算法，其遗憾可以适应观察到的（延迟）损失，而不仅仅是适应累计延迟（该算法需要对最大延迟的先验上界，或者在做出决策时提前知道每个决策的延迟）。 在温和的问题上，所得的界限可能小几个数量级，并且可以证明延迟仅通过最佳手臂的损失影响遗憾。 显示英文摘要

摘要： We consider the adversarial multi-armed bandit problem under delayed feedback. We analyze variants of the Exp3 algorithm that tune their step-size using only information (about the losses and delays) available at the time of the decisions, and obtain regret guarantees that adapt to the observed (rather than the worst-case) sequences of delays and/or losses. First, through a remarkably simple proof technique, we show that with proper tuning of the step size, the algorithm achieves an optimal (up to logarithmic factors) regret of order $\sqrt{\log(K)(TK + D)}$ both in expectation and in high probability, where $K$ is the number of arms, $T$ is the time horizon, and $D$ is the cumulative delay. The high-probability version of the bound, which is the first high-probability delay-adaptive bound in the literature, crucially depends on the use of implicit exploration in estimating the losses. Then, following Zimmert and Seldin [2019], we extend these results so that the algorithm can "skip" rounds with large delays, resulting in regret bounds of order $\sqrt{TK\log(K)} + |R| + \sqrt{D_{\bar{R}}\log(K)}$, where $R$ is an arbitrary set of rounds (which are skipped) and $D_{\bar{R}}$ is the cumulative delay of the feedback for other rounds. Finally, we present another, data-adaptive (AdaGrad-style) version of the algorithm for which the regret adapts to the observed (delayed) losses instead of only adapting to the cumulative delay (this algorithm requires an a priori upper bound on the maximum delay, or the advance knowledge of the delay for each decision when it is made). The resulting bound can be orders of magnitude smaller on benign problems, and it can be shown that the delay only affects the regret through the loss of the best arm.