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.

本文考虑在延迟反馈下的敌对多臂老虎机问题，并分析了一些通过仅使用决策时可用的信息 (关于损失和延迟) 来调整步长的 Exp3 算法变体，从而获得适应观察到的 (而不是最坏情况下的) 延迟和 / 或损失序列的遗憾保证。最后，我们介绍了 AdaGrad 风格的版本的算法，该算法通过观察到的 (延迟的) 损失进行适应，而不仅仅是适应于累积延迟 (该算法要求先验上限）。