  We propose a new best-of-both-worlds algorithm for bandits with variably
delayed feedback. In contrast to prior work, which required prior knowledge of
the maximal delay $d_{\mathrm{max}}$ and had a linear dependence of the regret
on it, our algorithm can tolerate arbitrary excessive delays up to order $T$
(where $T$ is the time horizon). The algorithm is based on three technical
innovations, which may all be of independent interest: (1) We introduce the
first implicit exploration scheme that works in best-of-both-worlds setting.
(2) We introduce the first control of distribution drift that does not rely on
boundedness of delays. The control is based on the implicit exploration scheme
and adaptive skipping of observations with excessive delays. (3) We introduce a
procedure relating standard regret with drifted regret that does not rely on
boundedness of delays. At the conceptual level, we demonstrate that complexity
of best-of-both-worlds bandits with delayed feedback is characterized by the
amount of information missing at the time of decision making (measured by the
number of outstanding observations) rather than the time that the information
is missing (measured by the delays).
