A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays
Authors: Saeed Masoudian
Julian Zimmert
Yevgeny Seldin
Venue: NeurIPS 2024 poster (2024)
Keywords: Best-of-both-worlds
delayed bandit feedback
Primary area: bandits
TL;DR: We propose a new best-of-both-worlds algorithm for bandits with variably delayed feedback that is robust to excessive delays

Abstract: 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_{\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).

A Best-of-both-worldd Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays
Saeed Masoudian Churney ApS, Denmark saeed@churney.
Julian Zimmert Google Research zimmert@google..om
Yevgeny Seldin University of Copenhagen seldin@di. ku. dk
Abstract
We propose new best-of-both. sot-of-booth-oordds algorithm for bandits with variably delayed feedback. In contrast to prior work, which required prior knowledge of the maximal delay dmax and had a linear dependence of the regret on it, our algorithm can tolerate arbitrary excessive delays up order I (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- ofrblds-worlds setting. (2) We introduce the first control of distribution drift that does not rely boundedness of delays. The control is based the implicit exploration scheme and adaptive skipping of observations with excessive delays. (3) We introduce 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- woohds 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).
Introduction
Delayed feedback is ubiquitous challenge in real-world applications. Study of multi-armed bandits with delayed feedback has started at least four decades ago in the context of adaptive clinical trials (Simon 1977 [ick] 1988), the same problem that has earlier motivated introduction of the bandit model itself (Thompson) 1933). We focus on robustness to delay outliers and to the loss generation mechanism. In practice occasional delay outliers common (e.g., observations that never arrive). Robustness to the loss generation mechanism implies that the algorithm does not need to know whether the losses are stochastic or adversarial, but still provides regret bounds that match the optimal stochastic rates if the losses happen to be stochastic, while guaranteeing the adversarial rates if they are not (so-called best-of-both- worlds regret bounds). Such algorithms are important from a practical viewpoint, because the loss generation mechanism can rarely assumed to be stochastic, but it is still desirable have tighter regret bounds happens to be. From the theoretical perspective both forms of robustness are interesting and challenging, requiring novel analysis tools and yielding better understanding of the problems.
Joulani et al. (0133) have studied multi-armed bandits with delayed feedback under the as- sumption that the rewards are stochastic and the delays sampled from fixed distribution.
"The work was done during SM's employment the University of Copenhagen.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparison to state-of-the-art, The following notation is used: T is the time horizon, K is the number of arms, indexes the arms, A; is the suboptimality gap or arm i, max is the maximal number of outstanding observations, D = Ei= de is the total delay, S S [T] is set of skipped rounds, S [T] S is the set of non-skipped rounds, Ds = Eies de is the total delay in the non-skipped rounds, and dmax is the maximal delay. We have ming (IS) + /Ds)) S vD and
3 max E dmax. and in some cases ming (IS) + VDs) < VD and maxx & dmax-
Paper
Key results
Joulani et al. (013)
Stochastic bound:
EEidiso
log A.
+ o A.)
Zimmert and Seldin (2020)
Adversarial bound
without skipping: O KT + log K
with skipping: o KT + mins (iS + Ds log K)
Masoudian et al. (2022) provide matching lower bound)
Masoudian et al. (2022)
West-of-both-weer bound, stochastic part
Σ it
T +
2. log + dmax dmmax K2/3 log K)
dmax
A.
The results assume oracle
cest-ofbooth-worlee bound, adversarial part
knowledge of dmax
O
<TK VD K + dmax log K
Our paper
bound, stochastic part
0
Eittr
log A.
+
A.
A.
Amax log K
+ K Kamax + S*) where
|S| D3K log K ))
S O min ddmax K log K, mins
ofst-of-both-worlde bound, adversarial part
( (VKT + mins {IS] + /Ds log K} + St + Ko
They provided a modification of the UCB1 algorithm for stochastic bandits with non-delayed feedback (Auer et al.) (002). They have shown that the regret of the modified algorithm is
A. + Tmax where indexes the arms, A; is the suboptimality gap of arm i, T is the time horizon (unknown to the algorithm), and max is the maximal number of outstanding observations. (An observation is counted outstanding at round if originates from round or carlier, but due to delay it was not revealed to the algorithm by the end of round t. The number of outstanding observations or at round / is the number of actions that have already been played, but their outcome was not observed yet. We also call o₂ the [running] count of outstanding observations. The maximal number of outstanding observations max is the maximal value that d takes and is unknown to the algorithm.) The result implies that in the stochastic setting the delays introduce an additive term in the regret bound, proportional to the maximal number of outstanding observation.
O [EnA,so
In the adversarial setting, multi- bandits with delayed feedback were first analyzed under the assumption of uniform delays (Neu et al.) 2010 2014). For this setting CCes-BBianchi Bianchi et al.) (2019) have shown Q KT /dl log K) lower bound and almost matching upper bound, where K is the number of arms and d is a fixed delay. The algorithm of [Ceea-Biannhi et al. is modification of the EXP3 algorithm of Auer et al. (2002b). Cesa-Bianchi al. used fixed learning rate that tuned based on the knowledge of d. The analysis is based on control of the drift of the distribution over arms round + d. Thune et al. (2019) and Bistritz et al. (2019)
played by the algorithm from round provided algorithms for variable ad adversarial delays, but under the assumption that the delays are known "at action time", meaning that the delay d, known at time t, when the action is taken, rather that at time & + d, when the observation arrives. The advanced knowledge of delays was used to tune the learning rate and control the drift of played distribution from round when an action is played, to round + de, when the observation arrives. Alternatively, an advance knowledge of the cumulative delay up to the end of the game could be used for the same purpose. Finally, Zimmert and Seldin (2020) derived an algorithm for the adversarial setting that required no advance knowledge of delays and matched the lower bound of Cesa-Bianchi analysis of Zimmert and Seldin avoid explicit control of the distribution drift and are parameterized
Bianchi et al. (2019) within constants. The algorithm and

---

by running counts of the number of outstanding observations or, which is an empirical quantity that observed at time t ("at the time of action").
Masoudian et al. (022)) attempted to extend the algorithm of Zimmert and Seldin (2000) to the best-of-both-worldd setting. The stochastic part of the analysis of Masoudian al. based
direct control of the distribution drift. The control is achieved by damping the learning rate to make sure that the played distribution on arms is not changing too much from round t. when an action is played, to round t + d, when the loss is observed. Highly varying delays cannot be treated with this approach, because fast learning rates limit the range de for which the drift is under control, while slow learning rates prevent learning. Therefore, Masoudian et al. had to reintroduce the assumption that that the maximal delay dmax is known, and used it to tune the learning rate. Unfortunately, damping of the learning rate to control the drift over dmax rounds made dmax show up additively in the bound, meaning that potential presence of even a single delay of order T made both the stochastic and the adversarial bounds linear in the time horizon. We emphasise that the linear dependence of the regret on dmax is real and not an artefact of the analysis, because it comes from damped learning rate.
We introduce a different (2020) that is fully parameterized by the running count of outstanding observations and requires no advance knowledge of delays or the maximal delay diaxx. Our algorithm is based on a careful augmentation of the algorithm of Zimmert and Seldin with implicit exploration (described below), followed by application of a skipping technique (also described below) as tool to limit the time span over which we need to control the distribution shift.
modification of the algorithm of Zimmert and Seldin
Implicit exploration was introduced by Neu (2055) to control the variance of importance-weighted loss estimates in adversarial bandits. But the exploration parameters add up linearly to the regret bound, making it highly challenging to design a scheme for best-of-both-worte
setting. The implicit exploration schedule of Neu leads to (VVT) regret bound and, therefore, unsuitable for that. Jin et al. 2022) introduced a different schedule for adversarial Markov decision processes with delayed feedback. However, it is unknown whether their schedule can work in stochastic analysis. We introduce a novel schedule and show that it works in sost-of-both-wotte setting.
Skipping was introduced by Thune et al. (2019) as a way to limit the dependence of an algorithm on small number of excessively large delays. The idea is that it is "cheaper" to skip a round with an excessively large delay and bound the regret in the corresponding round by 1, than to include it in the core analysis. Thune et al. have assumed prior knowledge of delays, but Zimmert and Seldin (2020) have perfected the technique by basing it on a running count of outstanding observations. In both works skipping was an optional add-on aimed to improve regret bounds in case of highly unbalanced delays. In our work skipping becomes an indispensable part of the algorithm, because, apart from making the algorithm robust a few excessively large delays, it also limits the time span over which the control of distribution drift is needed.
In Table T we compare results to state of the art In a nutshell, we replace terms dependent on duax by terms dependent on maxx, and terms dependent on the square root of the total cumulative delay D = ET= de, by terms dependent on the number of skipped rounds |S] and a square root of the cumulative delay D3 = Eies de in the non-skipped rounds S (those with the smaller delay). This yields robustness excessive delays, because neither Tmax nor mins (15) + v Ds) depend on the magnitude of delay outliers. By contrast, both the stochastic and the adversarial regret bounds of Masoudian et al. (002) become linear in T in presence of a single delay of order T.
There are also additional benefits. It has been shown that mmax S dinax: and in some cases mmax < dmax (Joulani et al.] 2013) Masoudian et al., (022). For example, if the first observation has delay T. and the remaining observations have zero delay, then dmax = T. but maax = 1. We also have that ming (IS) + /Ds) S VD, because S = Ø is part of the minimization on the left, and in some cases mins (IS) + vD3) < VD. For example, if the delays in the first /T rounds are of
order T, and the delays in the remaining rounds are zero, then mins (18) + vDs) O (VT) but
vD = (T3/1) Thhuee et al. 2019). Therefore, bounds that exploit skipping are preferable over bounds that do not, and for some problem instances the improvement is significant. In Appendix F we show that bounds with an additive term dmax- including the results of Masoudian et al. (022)) cannot benefit from skipping, in contrast to ours.
3

---

The following list highlights our main contributions.
1. We provide the first robust to delay outliers. It improves both the stochastic and the adversarial regret bounds relative to the work of Masoudian et al. (2022), which lacks such robustness. For some problem instances the improvement is dramatic, e.g., in presence of single delay of order T both the stochastic and the adversarial regret bounds of Masoudian et al. are of order T, whereas our bounds are unaffected.
algorithm for bandits with delayed feedback that is
2. We provide an efficient technique control the distribution drift under highly varying delays.
3. We provide the first implicit exploration scheme that works in best-of-bothhworldds setting,
4. We provide a procedure relating drifted regret to normal regret in presence of delay outliers.
5. the conceptual level, we show that best-of- sit--of-oot--te both-worldds regret depends on the amount of information missing at the time of decision making (the number of outstanding observations) rather than the time that the information missing (the delays). It was shown to be the case for the stochastic and adversarial regimes in isolation (Joulani et al. 2013 Zimmert and Seldin 2020), but we are the first to show that it is also the case for best-of-both-worldd.
2 Problem setting
We study the problem of multi-armed bandit with variable delays. In each round / 1,2,.... ..,,,.. the learner picks an action I from a set of K arms and immediately incurs a loss &,,1, from loss vector & E [o, _]K However, the incurred loss is observed by the learner only after a delay of de. the end of round + de. The delays are arbitrary and chosen by the environment. We use of to denote the number of outstanding observations at time t defined as o₁ = E.st 1l(s (s + de > t) and max = maxtejr] or to be the maximal number of outstanding observations. We consider two regimes for generation of losses by the environment: oblivious adversarial and stochastic.
We use pscudo-regret to compare the expected total loss of the learner's strategy to that of the best fixed action in hindsight. Specifically, the pseudo-regret is defined as:
REgT E
Σ
Ce.
min E (E(K)
Σ
E
(1,5) (,sh
where i = min E le,i is the best action in hindsight. In the oblivious adversarial setting, the losses are assumed to be deterministic and independent of the actions taken by the algorithm. As a result, the expectation in the definition of i can be omitted and the pseudo-regre definition coincides with the expected regret. Throughout the paper we assume that i unique. This is a common simplifying assumption in best-of-both-wortd Tools for elimination of this assumption can be found in Ito (202T).
analysis (Zimmert and Seldin 2021).
Algorithm
The algorithm is a best-of-both-wolle modification of the adversarial FTRL algorithm with hybrid regularizer by /Zimert and Seldin (2020). It is provided in Algorithm| display. The modification includes biased loss estimators (implicit exploration) and adjusted skipping threshold. The algorithm maintains a set of skipped rounds S, (initially empty), a cumulative count of "active" outstanding observations (those that have not been skipped yet), and vector of cumulative observed loss estimates L from non- ann-sipped rounds. At round t the algorithm constructs an FTRL distribution x, over arms using regularizer F, defined in equation (2) below, and samples an arm according to .z.- Then receives the observations that arrive at round i, except those that come from the skipped rounds, and updates the vector Lhh of cumulative loss estimates. The loss estimates L2 are defined below in equation O Then it counts the number of "active" outstanding observations o, (those that belong to non-skipped rounds), updates the cumulative count of outstanding observations D,, and computes
the skipping threshold d: d'
49 27 log R. Finally, it adds rounds s for which the observation
4

---

Algorithm 1: Best-of--ooth-wordds algorithm for bandits with delayed feedback
Initialize Su = 2, Du and Lghe O, where is the vector in R
2 for t === 1, J...... do
// Playing
and receiving observations (except from skipped rounds) Set rt = arg min (Iohe (1 x) + (t(
I/ Fg is defined in
Sample 1 ~ ~ee
for (s dg t) $ 1
Observe (8, k
I - +
H&,, is defined in
I/ Counting "active" outstanding observations and updating the skipping threshold
10
Set or = - [s + dg >() 1)
11
Update Di = D.-1 + oz
Set d'max= = -/Da/ Da/ (49K' log K)
13
I/ Skipping observations with excessive delays (by Lemma 20 at most one is skipped at time) for s E ft 1] St-1 do
14
15
if min (d.. / 2 de
max then
16
S. S {s}
// If the waiting time - exceeds dmaas then is skipped
17
else
18
S. S
has not arrived yet and the waiting time (t s) exceeds the skipping threshold d' max to the set of skipped rounds Sz. Lemma 20) which is an adaptation of Zimmert and Seldin (2020) Lemma 5) to our skipping rule, shows that at most one round is skipped at a time (at most one index satisfies the if-condition for skipping in Line 15 the algorithm for given ().
use implicit exploration to control sepportance-weigheee loss estimates. The idea of using implicit exploration is inspired by the works of Neu (2015) and Jin et al. (2022). but its parametrization and purpose are different from prior work. To the best of our knowledge, it is the first time implicit exploration is used for best-of-bothh both-oorldss bounds. For any s, E [T] with S t we define implicit
exploration terms A., D. Our biased importance-weigheee loss estimators defined by
(T,
Ee,1 max Tt X \,,
(1)
where d, min (dg, min {(t s) the observation from round It is the minimum of the delay d., and the time (1 -5)) s) to the first round when the waiting time exceeds the skipping threshold dt d
d denotes the time that the algorithm waits for
We hybrid regularizer based on combination of the negative Tsallis entropy and the negative entropy, with separate learning rates,
K +
K
Fz(x) = -2
Σ
V
Σ
x log 24
(2)
where the learning rates are '7," V and 7
491 The regularizer the same as the log K
one used by Zimmert and Seldin (2020). By inheriting their regularizer inherit their adversarial regret bound, which is minimax optimal, with just minor adjustment due to introduction implicit exploration and slight change in the learning rates and skipping threshold. The main contribution of our work is carrying out the stochastic analysis while staying within the algorithmic framework of Zimmert and Seldin and keeping the adversarial regret bound almost unscathed.
The update rule for Zt
V (-i = arg min (Lo (x)e, + F((x),
(3)
TEAK-
5

---

where - E d, < t)1(s & St-1) is the cumulative importance-weighte loss
estimate of observations that have arrived by time and have been skipped. We use S ST to denote the final set of skipped rounds at time T.
4 Regret Bounds
The following theorem provides best-of-both-worlde regret bounds for Algorithm I provided in Section 5 and a bound on S* can be found in Appendix H
A proof is
Theorem 1. The pseudo-regrer of Algorithm for any sequence of delays and losses satisfies
Regt =
-O(VKT (VKT+++ KT + min SE(T]
{1s) VDs /Ds log K + + Kōmmx)
where max maX (ōt) is the maximal number of outstanding observations after skipping and
S" =0 min (0max 1/3 1//g///////// log K
min
|ss V V log K
x))
SE.T)
Furthermore, if the losses are stochastic, the pseudo-regrer also satisfies
log
max l,
Regr =
+ Kō + 55t
A
inti
Masoudian et al. (2022) provide an Ω KT + minscry {ist + DDs log {)) regret lower bound for adversarial environments with variable delays, which is matched within constants by the algorithm of (Zimmert and Seldin 2020) for adversarial environments. Our algorithm matches the lower bound within a multiplicative factor of K3s on the delay-dependent term, which is the price we pay sest-offbothhworlld guarantee. The price comes from reduction of the skipping threshold of Zimmert and Seldin (2020) that we had to make to control the distribution drift that is due to the loss shift (see Appendix B.22j. It is an open question whether this factor can be reduced.
for obtaining
In the stochastic regime, assuming that the delays in the first max rounds are of order T, and that the losses come from Bernoulli distributions with bias close to trivial regret lower bound is Eigin A.
Q Fmax K + Eigr log ( This bound almost matched by the algorithm of Joulani et al.
(201)) for the stochastic regime only. Our bound has some extra terms, most notably Σ
Omax
iigt 2. log K
and S* It is an open question whether these terms are inevitable or can be reduced.
Theorem T provides three major improvements relative the results of Masoudia et al. (002]): (1) requires no advance knowledge of duaxi (2) it replaces terms dependent on dmax by terms dependent on Fmax. which never exceeds d'axx and in some cases may be significantly smaller; and (3) it makes
skipping possible and beneficial, making the algorithm robust to a small number of excessively large
| / VD2K& log K }. which is never much
delays and replacing lolog K term with minsgrn larger, but in some cases significantly smaller.
5
Analysis
In this section, we present a proof of Theorem [ We begin with the stochastic part of the bound in Section 5.1 followed by the adversarial part in Section 5.2
5.1 Stochastic Analysis
start by defining the drifted regret Regt
drift
Σ
1=1 (1rt, Tohor - Tobs -
)
where Zooe
1,07
Σ'= 2,1(s d, (s & St) is the cumulative vector of losses received at time t. Lemma is -rift
the first major contribution establishing relationship between Regt and the actual regret Regr.

---

Lemma 2 (Drift of the Drifted Regret), Let mmax max fo.). Then
Regr
Regdrise drift
1
Regr
2K Σ (Aeeta A
O maax
S
where S" is the total number of rounds skipped by the algorithm.
The core of Lemma 2 is based controlling the distribution drift using implicit exploration and drift
skipping. In prior work on bounded delays the relation between Regr Regriif and Regr was achieved by shifting all the arrivals by dmaxx leading unbounded delays, because a single delay of order prevents shifting and leads to linear regret. We address the challenge by introducing procedure to rearrange the arrivals (Algorithm 2 below) and advanced control of the drift (Lemma below). A proof of Lemma is provided at the end of the section.
additive term of order dmax- This approach fails for
Algorithm 2: Greedy Rearrangement
Initialize wfew 0 for all = 1,..., T + d do
for / for 8 . Find the first round π (s) E [t, t daaxd such that (=(3) =
d, do
Move the arrival from round to round r(s) and update new
x(x)
The drift control lemma (Lemma 3) is the second major contribution of the paper. Prior work on bounded delays controlled the drift by slowing the learning rate in accordance with dmax- This does not work for highly varying delays, because slow learning rates prevent learning, whereas fast learning rates fail to control the drift. Lemma relies on implicit exploration terms in the loss estimators in equation ① and on skipping of excessive delays, leaving the learning rates intact.
Lemma 3 (Drift Control Lemma). Let d'maxx be the skipping threshold at time t. Then, for any i [K] and s, t E [T], where s S and S d'maxe we have It, S 4 max(2 X2,1).
The proof is based on introduction of an intermediate variable T, (- which is based on the regularizer from round s and the loss estimate from round exploits the implicit exploration term As,t to show that 31,1 A.. S and skipping to show that Z, < 2. The latter implies that x,,
max(2x.s < 2, and in combination with the former completes the proof. The details of the two steps provided in Appendix B
max("irdd..))
Given Lemmas 2 and Lemma
we apply standard FTRL analysis, similar to Masoudian et al. (002)).
drift
to obtain upper bound for Regr
Specifically, in Appendix A we show that
RegT
drift
1/2 m
+
Σ
Σ
7 (V 1) A
K
oe log (1/21,))
log
t=1
1=1 1
+0
K t=1
1,4d
(4)
=t) is the number of arrivals time t (if a round s skipped at time it counts as an "empty" arrival with loss estimate set to zero). By combining 4 with Lemma 2 we obtain
where a, c 2 0 are constants and (s-
7ota. (Ve4d. 1) 2c Tena log(1 1/x,,))
RegT
E
2a
1/2 Mea
2b
Σ Fgbl
log K
1=1
T
+ 0
K
(Nut4ā, + -
maxx + )
(5)
1=1

---

Then we apply a self-bounding analysis, similar to Masoudian et al. (2022). and get
Regr - 0
Σ
log (T) +
O mmax
+ max + K
Σ ( + A t + +
A log K
Eppi
The details of the self-bounding analysis provided in Appendix C
The stochastic analysis is completed by the following lemma, which bounds the sum of implicit exploration terms above. It constitutes the third key result of the paper and shows that the bias from implicit exploration does not deteriorate neither the stochastic nor the adversarial bound. The proof is based on careful study of the evolution of D, throughout the game, and is deferred to Appendix D
Lemma (Summation Bound), For all E [T], let D3 = Ei= or and As,t e: 2.-5, then
Σ (Aett * (
Proof of (emmmaa(rrit of the Drifted Regret)
We start with the definition of the drifted regret.
K
Regr
drift
Σ
Pote (.,5
max { do,e)
max { (Za doat)
e+ i=1 sgS.
K
E
la Re,i
max (Ir,er do,t3
tm
s+td =t sgS,
K
Σ
E
l 1o.
- S"
max (Te do.e
1=1
(6)
Note that when taking the expectation, rely on the fact that Z2 with + d does not affect ot. If max (I As,t} = Fx.i, then L,.i otherwise
la te (do,e xe.s)
LatiTe. 4Mar xe.e)
= Eo,
2 La 4ha,t (7)
Aaa
da,t
where the first inequality 24,1 S 4 max((x. )o,1) 4raa by Lemma and Luss 1, and the second inequality follows by Fg.s 2 0. Plugging
into (6) gives
T
Arift Regr
(lasste - 4hatt losg
1=1
s+d,=
1=1
T
K
T
A
4K
Σ
E [
55
(8)
1=1
stdd
R
suffices to give a lower bound for Ry terms of the actual regret Regr. The difference between
Ry and Regr is that Regr E
Er EK ArTe.s whereas in Ry the ΣK A,T is
multiplied by the number of arrivals 2s = Ei=1 1 (s d. = =t) at time f, and is might be larger than one zero due to delays.
8

---

Our main idea here is to leverage the drift control lemma to provide a lower bound for Ry in terms of RegT- Specifically, by Lemma 3 for all r E [o, dmax we have max At,t4r) 2 F44nb which
implies Ft,i 2 Fetrr A,,+r. Thus, we obtain the following bound for any r E [0, maxl
K
K
A KALTT
(9)
1=1
In Algorithm| 2 we provide greedy procedure to rearrange the arrivals by postponing some arrivals to future rounds to create hypothetical rearranged sequence with at most one arrival at each round. Colliding arrivals are postponed to the first available (unoccupied) slot in the future. In Lemma S below we show that arrival originally received at time t stays in the [t, + max) interval (note that Fuax I dmax). When observation from round is postponed from arriving at round t arriving round t r for E [0, d'aax by (9) is equivalent to replacing Σ A,T by E A,Titni KAt,r in Rr. Note that Algorithm may push an arrival to round larger than T. which equivalent replacing Σi=1 A,Te, by zero.
Let wnew for all t [T + dmaax] be the total arrivals at time t after the rearrangement, and let (t) be the round to which we have mapped round for all t E [T]. Then for any rearrangement
RT E
2
E
new
E
CAT K
(L((()
(10)
The following lemma provides properties of the rearrangement procedure.
Lemma Let d'maxx = maxşe|t| {ā,}- Then Algorithm
2 ensures for any E [T' + drasd that
2x E =(0,1} Furthermore, for any round E [T] keeps all the arrivals time in the interval [t,t+ + m such that Vs tt: 8 d, = 1 = T()) - S dhaxx
We provide a proof of the lemma in Appendix E As a corollary, after the Greedy Rearrangement (Algorithm 2 the number of rounds with arrivals is most o This is because there will
be no arrivals after T + of and Eitomux wf
Σt= 1/ T, which implies there most arrival. Therefore
max arrivals as each round receives
T
K
T
K
DEW
A = Regr -
= 0)
Σ
A
1=1
i=1
1=1
1=1
Regr
E
Σ
0)
Regr
E
max
Regr
Tmaxs
(11)
where the first equality uses the definition of RegT = BIST veew E 1).
T ΣK A and that Vt [T]
Since Vt E [T] T()) s t de + onace we have (e, S A Together with
10
and 8 it completes the proof.
5.2 Adversarial Analysis
The adversarial analysis is similar to the analysis of Zimmert and Seldin 2000 Theorem 2). In Appendix G we show that
Regr O
KT
min {is] DDz log K S* + K X X1,4
SEi
where the first two terms originate from the analysis oimment and Seldin to structural similarity of the algorithm, S* is due to adjusted skipping threshold, and Ei=1 >,,+ is due to implicit exploration bias and is bounded by Lemma The proof is completed by the following bound on S*, which is shown in Appendix H
Lemma 6. We have S = min dmax log K. minsc {1s)+ + V DDSK log K }))

---

Discussion
We have successfully addressed the challenge of handling varying and potentially unbounded delays in west-of-both-worldd setting. The success was based on three technical innovations, which may be interesting their own right: (1) relation between the drifted and the standard regret under unbounded delays (given by Lemma 2 Algorithm [ and Lemma (2) A novel control of distribution drift based on implicit exploration and skipping that does not alter the learning rates and exhibits efficiency under highly varying delays (Lemma] 3); and (3) An implicit exploration scheme applicable in best-of-both-- fit-ohhhwwordds setting (Lemma 4
The work leads to several directions for future research. One question is whether the best-of-bothh worlds bounds could be improved further. In particular, whether the K term in the adversarial regret bound could be reduced or eliminated. The term arose due the need to decrease the skipping threshold of Zimmert and Seldin (2020) to control the distribution drift. It would also be valuable to Emax
explore whether possible reduce the S term and reduce or eliminate the Eijs A. log K term in the stochastic bound, or to derive lower bounds showing that these terms are unavoidable. Another interesting direction is to find more applications for implicit exploration and skipping in the context of best-of-both-world bounds.
Acknowledgments and Disclosure of Funding
SM and YS acknowledge partial support by the Independent Research Fund Denmark, grant number 9040-00361B.
References
Jacob Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with new kind of smoothness. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47, 2002.
Peter Auer, Nicolò Cesa Desa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing. 32, 2002b.
llii Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, and Jose Blanchet. Online exp3 learning in adversarial bandits with delayed feedback. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Nicolo Cesa-Bianchi, Claudio Gentile, and Yishay Mansour. Delay and cooperation in nonstochastic bandits. Journal of Machine Learning Research, 20:1 2019.
Stephen G. Fick. The two-armed bandit with delayed responses. The Annals of Statistics, 1988.
Shinji Ito. Parameter- free multi-armed bandit algorithms with hybrid data data-depeddent regret bounds. In Proceedings of the Conference on Learning Theory (COLT), 2021.
Tiancheng Jin, Tal Lancewicki, Haipeng Luo, Yishay Mansour, and Aviv Rosenberg. Near-optimal regret for adversarial MDP with delayed bandit feedback. In Advances Neural Information Processing Systems (NeurIPS), 2022.
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvari. Online learning under delayed feedback. In Proceedings of the International Conference on Machine Learning (ICMI.), 2013.
Saeed Masoudian, Julian Zimmert, and Yevgeny Seldin. A best-of-bothh-worlds algorithm for bandits with delayed feedback. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. In Advances in Neural Information Processing Systems, 2015.
Gergely Neu, András György, Csaba Szepesvári, and András Antos. Online markov decision processes under bandit feedback. In Advances in Neural Information Processing Systems, 2010.
10

---

Gergely Neu, András György, Csaba Szepesvári, and András Antos. Online markov decision processes under bandit feedback. IEEE Transactions on Automatic Control, 59:676 691, 2014.
Francesco Orabona. A modern introduction to online learning, 2022.
1912. 13213
Richard Simon. Adaptive treatment assignment methods and clinical trials. Biometrics, 33, 1977.
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25, 1933.
Tobias Sommer Thune, Nicolò Cesa-Bianchi and Yevgeny Seldin. Nonstochastic multiarmed bandits with unrestricted delays. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In Proceedings the International Conference Artificial Intelligence and Statistics (AISTATS), 2020.
Julian Zimmert and Yevgeny Seldin. Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 2021.

---

A Details of the Drifted Regret Analysis
In this section we prove the bound on drifted regret in equation 4 The derivation is same as the one by Masoudian et al. (2022), however, for the sake of completeness we reproduce it here. The analysis follows the standard FTRL approach, decomposing the drifted pseudo-regret into penalty and stability terms as
T
drift RegT
tT
Pohay + --((-114)) F-
+E
Σ
P-
obs
F. (-I444 E2.5g
1=1
stability
penalty
The penalty term is bounded by the following inequality, derived by Abeernehyy et al. (2015)
T (F (F)) P.(x))) + Fr(e;;) (i(2))
penolly S
(12)
where exp represents the unit vector in RK with the i7 element being one and zero elsewhere. This leads the following bound for penalty term
T
K
om log (1/
penalty So
Σ t= if
Thi
(13)
log K
where we substitute the explicit form of the regularizer into 12 and exploit the properties f/
7-1 On)), 7, - O(arn/ log K), and i 1 0.
For the stability term, following similar analysis presented by Masoudian et al. 2022 Lemma 5), but incorporating implicit exploration terms, for any a < 7t. we obtain
stability
2f (IL.) 1 (Cthe a,)
Let A, = ssst:s f
d. =t then due to the choice of skipping threshold, ar = E.EA, Is
XK f. (ma.))
22,
H. ( Thus have Σx S. (w).))-1
satisfies the condition at 7t where lu,
ΣE St (o).)))
T K
2
stabilily S
25 (1).)-1
Σ
Eais -las Pais
BEA
K
2ft (2r,)) (Paji -Past
2
eEA,
S1
K
Σ
(or)) (Dart - Ea.)) (Ers-
S2
12

---

For brevity we define 21, = fz (Ir.s) - and m max f A / for any S t and i E [K]. We
begin bounding S₁ by replacing definition of loss estimators from ① and get
B[S]] ΣΣ
Σ
23
Zz,t
(1, =i)
21,1b
m
m Σ==1 20.3
SEA,
27
1(1 =
Tt,
2B
Zt,i
m
m 2-j=1 Reti
1=1
BEAL
2'
K
2r,,, (I, 1)
Σ
Σ
E
Zt,b
m 2
m =1==1 20,3
SEA,
2,8
5
Zt,1,
2t,,, 2r,i (Ig =
Σ 1=1 =EA:
2E
m
5=== 2t.j)
K
m m 2===1 2t,h
87
Where the first inequality uses la.1, expectation w.r.t. Is as the following
S 1. We show that Sf has negative contribution to Si by taking
T
K
K
Σ
E
Σ
= 0
A
m
2t,s)
m 5,i
=== 2t.j
Thus only need to bound Si, for which we take expectation w.r.t. Is and separate i* from the other arms to get
K
1(1,
=
2L,, 10, = 1)
s
20,6
m²
2
m m s.L.
m
Ex= ==== 24.1
6,5
22 Ts.
E
+ E
m
my
m, j= Zent
1/2
Dz.5"
21,5
E
417:20 0.a
+ E
X Et.s"
m
2
2j=1 20,8
K
13/2
1/2
Fz,5"
3/2
I2,2"
ig
4E
1 8,5
+
m 2
x n.
1-
(1 F4,5 33/2
F,,5"
3/2
4E
1/2
+ E
11. 1,5
3/2
(1 - I 33/2
ml
2-1/2
4E
T 5.
+ E
4v 217 Σ Iz,b
4E
11 8,
+ E
16v 2 Σ
(xosr + Xa,e)
$
0
1/
x
1/2
+ KK Xar1)
where the second inequality uses 24,1 the third inequality is due the fact that 24,1'
1/ (2 < MaiLs along Tt, S m from Lemma
3/2
1-
21:0
an increasing function in terms
13

---

3/2 and Ej Rt S EEfr 1 of both 2,,"" and Σ -e ot, and we substitute 2,,-" S 1,
3/2 S
me(1 - 21,5*) )8/2, the fourth inequality is due to (1-a)0/2 + 22/2 I 2 2-11/2 1/2 the fifth and the sixth
1/2 inequalities rely Lemma 3 and finally the last inequality is followed by Vi Fzsi S Fe,t and that R S 7/s- Combining bounds for s and 5f gives the following bound for Si
T Σ
T
E[S So
B
1/2 E, +
Σ
KX
(14)
1961"
1=1
For S2, we take expectation with respect to Les Iy.. and randomness of losses, all separately to get
B[Sa| =
2E
2
(Esi (fs,--1,
Eb) (Brs- [oo) 2,)
t=1 im T K t=l
HiJos
E/= 21.H4 m's
E1=1 21, 21. Σラ= 1 20,5
2E
m
Σラm 1 26,
(15)
For simplicity we define c = p4 following bounds
for any s S t and any i E [K]. for which we have the
Aea
m
We then continue from 15 and bound it as the following
B[S²]
T
K
Σ
j=1 2t5
K
Σ K
s=1 2
Σ 21
Σj= 20,
2E
2
- 6',, +
ps
ΣØ=1 2n,
- +
Σj=1 2nd
R
1=1
t=1
== 20.1
f== 21,5
A,
T
K
Σ 11 Z1,ltyj
2
EEK 2e,1 (
(E K
Σ
2E
2z,
11i
Σ Σj=1 Fen)
K
2n Gh + 22, + tgr))
Σ 22,4
1=1
T,aEA:
8
52
(16)
where the inequality holds because we ignore the negative terms after multiplication and that [144
ΣK 20,3
)1 S 1. We need to bound each part from
(6). We start with Sy
ΣK u.,
K
Σ
K j=1 24. My
2
$
2z,
14
K
i=
1= Fen
> 1==1 26,5
2
K
i=l Zz,s
Σ iiml 2t,5
2t,i
- 24,6
K
(12 - 122-)
$
Σ
(17)
14

---

We bound S2 as
K
$
21,50 + 22,l + t,,)
cx,1 + t.s
220, G.))
tt,i
i=1
Ze,dda
+
mra
K % (hatt + )r,e),
(18)
2
where the last inequality holds because 2,, S i and that 24,1 S 4m, 4m,,, from Lemma 3 remains give upper bound for S2 as
(h 1= 21, ", ( 2(,))
Σ Z1,1
2im1 K
Pe, /m, 12,,
mi 24, andde//m/.
E 22,6
Knuldo, dr,e),
(19)
where the second inequality rely žt,i Me du,t S m a.i Xr,t mh, and Fa, S 4m Ia, 4mh. from Lemma
S 3 suffices to plug bounds in [7 and (99
to obtain
T
T
E[S2]
< Σ
Σ
4Am - 1) + Σ
K (1 1)A 1,44.
T
Σ
4A Ao,d(e 1) +
K7 (V 1)
ifft* SEA,
Σ
Σ
2z. 1) 10 Σ K K44a (Ve+ 1)
17f1 SEA,
50
ΣΣ 7 A - 1) + K
(20)
1= 1zpl""
t=1
where the third inequality Lemma 3 and the last inequality holds because of the skipping that ensures a (Ve+7,
1) < 1. Now, it is sufficient to combine the bounds for S₁ and S₂ in (14) and
(20) and get
E E[stability] 5
Σ
Σ ieft"
1/2 + Σ BB
Σ
74a Blrc,
1) + K Σ
(21)
Combining the stability bound from 21 and the penalty bound from 13) concludes the proof.
B Proof of the Drift Control Lemma
In this section we provide a proof of Lemma We start with a few auxiliary results, and then prove the lemma.
B.1 Auxiliary results for the proof of the key lemma
For the proof we two facts and a lemma from Masoudian et al. (2022) and new lemma. Recall that f(( -2m -1 V + 7 log
15

---

Fact 7. Masoudian et al.
2022
Fact 15) fz is a concave finction..
1 Lemma 17) Fix and a with Z s, and assume that there exists a, such that Tt,i a max )s,t) for all i E [K], and let f(x) (-21, Vx 7/8 log z) then we have the following inequality
Fact 8.
Masoudian et al.
2022
Fact 16) ft. (x)=+ is a convex function.
Lemma 9. (Masoudian et al.
2022
( (BLL)- S 2n(K - 1)
Ex= (Z1
Lemma 10. Ift > and (1 -6-) S d'aaxo then
dinxx S V2d
which is equivalent to Dr S 2D..
Proof.
It suffices to prove that D; S 2D,, which is equivalent to proving that (D.-D.) S Dr. We
have:
Dt
D: DD
Σ の St s)dmmx I (dimax)) 49K $ log K
S
2
r=++1
where the first inequality holds because due to skipping, for all r S t we have o, S d and (t s)
di dmaxx
B.2 Proof of the Drift Control Lemma
Now ready provide proof of Lemma 3 Similar to the analysis of Masoudian et al. (2022)
the proof relics on induction on valid pairs (t, s), where a pair (t, is considered valid if S and (t s) S dmaxx- The induction step for pair (t) involves proving that 24,i S 4 max( As.t) for all i E [K] To establish this, we use the induction assumption for all valid pairs (t', s') such that s', < t, well all valid pairs (t', s'), such that t' t and s' S t. The induction base encompasses all pairs (t', t') for all E [T], where the statement Zy. I 4ry holds trivially.
To control ( we first introduce an auxiliary variable ã = (- We then address the problem of drift control by breaking down into two sub-problemm:,
1. max (mr A.,e)
Zi,1
< 2: the drift due to change of regularizer.
2. 3g the drift due to loss shift.
Deviation induced by the change of regularizer
The regularizer at round r defined as
K
K
Fx(x) = Σ fz(z)) = Σ
(-2m, 1012m_1/// Vxa + +,,,,, log x:)
1=1
We have F- -ppha and T-- (- According to the KKT conditions, there exist Lagrange multipliers i and μi, such that for all i:
S(())) = I---1,5 + 14,
( - -Tob 11.
We also know that there exists an index j. such that F. 2 Ft.j. This leads to the following inequality:
-ipha + = (((s)) < f( < f. (5,) = - -oob -1-11 + FT
16

---

where the first inequality holds because the learning rates are decreasing, and the second inequality is due to the fact that (x) is increasing. This implies that - jú, which gives us the following inequality for all
(F1))
1
log(
log(T:)
= (())).
To VoV Ti log((Fe.)))
7s
log(E.)
Thus, we have two cases, either
Ttc
74
Case i: If
holds, then we have
He.l
On the other hand, we have
Vo V2
ΣN= o K3/2 log
f2/2
de max
K log K
where the second inequality holds because trivially ã, S This implies that 21. S 2.
Case ii: If log(se.d)
log(ā.) implies that Zt,z S x Using 34 S max((Ts, )s,t), we get
S
7t
7a
Tt, S max(
max A,,e) max
X
S max( X.
A
VD--VD,
max( )s,))
V
max )..t)
V
(a, ) x e elv Pit
max(ai Aad) xe vVE s max(Ti, daat) x2.
Therefore, in both cases we obtain
Ft S 2 max(";, A,,t).
(22)
Deviation Induced by the Loss Shift
The initial steps of the proof of this part the same in Masoudian et al. (202). However, for the sake of completeness, we restate them here.
Since we have Ig = (z Σm= fas).. For brevity, drop from fx)) By the KKT conditions 3p, s.t. Vi:
and = V (- bghy), they both share the same regularizer
(( = - -igha + 11
I (Tx)) Topha ft.
Let 8= = Igba - Jabs
----1 then by the concavity of f (x) from Fact 7 we have
(Ix,) (oa,--Z)) (Ia,e) of (xaa)
(3x) (a o.) (Tx).
(23)
# n-
Since f" (I.,)) 2 O, from the left side of 23 we get æ., - 2; S f" (x,,)) 1 Taking summation over all and using the fact that both vectors v, and t are probability vectors, we have
k
K
Ezii F.) <
(Ix. (M- E.)
>K f (1s.))
Ι p <
(24)
Σk ("((a,))~
17

---

Combining the right hand sides of 23 and 24 gives
25=1 1 (1as))
3 2. 2.,)s
(Te)
Σ 2j=11 I (Is.i)
and by rearrangement we get
k f (zas)
i S Nz,i + (1;t x
Σ 1" (1x
Σラ f (Iea) 10g
S F + Vi
(25)
Σラ=1 1" (1),)) )
where the last inequality holds because ("(3:)- 11/85
11-1--30 3/2
2
7
17 17,
x/.
The next
step for bounding 3y is to bound ΣK 1 (0,,))1E, 2 1 (#ar)-1
in
25 where Eg Erea Ers and
:r:ss 2 =t.
If there exists E A, such that and 4 max(3raa > (.ttā)) Fs,i then combining it with the induction assumption for (r + d), r), where we have ",dd,, max( X A.r+a,) leads to ,,,d, S Tz.i. On the other hand, by the induction assumption for pair (r + dr, t), have
21,5 S
So using ",+3,.; S Ta and a, S Ae, we can derive 21, I 4 4mxx(F.,4 Aa,1). This inequality satisfies the condition we wanted to prove in the drift lemma. Therefore, we assume that for all r E A we have either r I Fz,i I 4 max( A Ar.+a.)) ). If S 8, using the the induction assumption for (s, r) together with the fact that λr, S 2. results in Fs,i S max(xr,,, Ar,s). Consequently, in either case, the following inequality holds for all E
Dz.i < 4 max (Fr xr,
(26)
Thus, inequality in 26 satisfies the condition of Lemma 9 and for all r E we get:
Σx (far)- f < <8KK -1)
(27)
K ("
We proceed by summing both sides of the inequality ΣK f" (m..)) - Σx (5x5)~1 < 4|A((K 1)3. Now it suffices to plug this result into 25
27 over all E A and obtain
H; S 2s,i + 8|A/7,77, 1) =
ã 2,,1 x
(28)
8|Alys(K - 1//33
< 0z,i
24yadin (K 1311/3
1
S Dz,i X
2.r
(29)
1 1/2
where the third inequality uses |A| < dinax + Lemma 10, and for the last inequality we use the definitions of 7, and de
de d'ax d and that d'aax 2d fax by
Combining 229 and (22) completes the induction step.
18

---

C Self-Bounding Analysis
In this section show the details of how apply self-bounding analysis to bound the right hand side of (5).
We start from
5
and decompose it as follows
T
T
T K
ox mir 1og(1/2ag
RegT
a
1/2 ts
+b
n+ (vitd. - 1) +c
log K
2m1
+
K
(ueetd + Axettdtttuue + max + S
[m1
We rewrite the pseudo-regret as Regr above we have
AlleTT 3Regr, and then based on the decomposition
Regr S E [4aA - Regr] E [4bB Regr] + E [4cC Regr] 4D.
(30)
Masoudian et al. (202) provide the following three lemmas that give the bounds for the first three terms in (30). Although the algorithm of Masoudian al. differs from ours, their bounds remain
applicable, because they are based on the worst-case choice of Zt,6, which is algorithm-indeeendent.
Lemma 11.
(Masoudian et al.
2022
Lemma For any 2 have:
4a log T +1)
4aA
Regr
(31)
Lemma 12.
Masoudian et al.
2022 Lemma 7) Let Umax = maX Us. then for any 2 0:
4bB Regr < umb log K.
(32)
is evident that Umaz S 0max so the bound Lemma 12 is dominated by O(K term in the regret bound.
Lemma 13.
(Masoudian et
2022 Lemma 8) For any e 2
128c
4cC RegT S
(33)
A, log K
By plugging
31
32
33 into
30
we get the desired bound.
D A Proof of Lemma 4
First we provide two facts and two auxiliary lemmas.
Lemma 14. For any we have
2D, N dg.
s=1
Proof. We show that for any E [T] we have E d, DD
-D, S De
2
Σ d - D. =
Σ 6.)
1=1
(est))lotd,00))
Σ
d,
(s5t))(s+d(,2))
D.
< (dmaxx²²
$ Dr.
49 log
19

---

where the second inequality holds because de S dimax and the total number of steps that satisfy (s I t) (s d, t) is less than the skipping threshold time i, which is again dmaxx Rearranging the inequality completes the proof.
Lemma 15 OOrabon 2022 Lemma 4.13)). Let do 2 0 and f [0; +00) + [0; (0;+ be
nonincreasing function. Then
T Σ
Eiso
af
ag
+
Σ ai
S
f(x)dx.
00
Fact 16. For any x 2 0, we have e e S z'
Fact 17. For any 1, we have e 1
x (x)
Proof of Lemma
We have two summations as
D Pll thae +āg
where we show upper bound of mfx for each of them.
Bounding the First Summation: Let To be the time satisfying DDd,
a then using
K173 (og(K))
Facts 16 and have
Σe
T
To D
rtd.
Dr
Σ
T
D Detā. -Di
D e+
t= To+1 D De+ā.
log"
Dethe
1=1
1=1
Dit2, - D.
B
For A we give the following bound
i+de
T.
G.1 + de 2) D D44ă.
A
Σ
D
Detd.
s=1+1
To 03
D,
#=1
62 D. D.
K1/3 log KYD,
t K1/3 log K VDz
Dro
50 0
max
K K1/3 log(K))
K2//3 log" (K)
where the second equality is by swapping the summations, the first incquality holds because D D.td 2 Dz, the third inequality uses G. S di S
k173 log K and the last inequality uses Lemma 15
DD.
20

---

The bound for B is as follows
3. 7K log (og(K)D
B=
Σ
D
Dith
1=
D L+..
log"
Ditd, -D:
t= s=t+1
t4d log?
mmax v Petde
T
0,1(t + dj 2
(2K\/S (oR(K)D 11
= T= 11
D P+ā log²
Bwna
3 G
T=
4D 4D++,, t+
log
2
49K log (K)D
Ø2 max
T
4D, log
49K2/3 2
D. (K)
s= Totl
max
4D, log²
49K3/3 log (KYD.
s=To+1
Dr
max
Dro
4r log?
19K2/3 log (K))
max
19/3/3 Jog (K))
=
4 4log(
02
Drr
where the first inequality follows by न, S max and our skipping procedure that ensures de S d S /P
R173 log K. the second equality is by swapping the summations, the second inequality follows by
D 1+ D., and Ei=l I de s) o. the last inequality follows by Lemma 15 and the last equality uses J (x/or dr Tog(=//>.>>>
Bound the Second Summation: The bound for the second summation follows the same approach, but it requires additional care due to existence of of in Let To be the time satisfying
/ Dro (K))
T then using Facts 16 and we have
D Pilefax p. P dd DD
To D
Ltoiav Dr
T
D Deoiis
Dr
D Ltohno +dl
D Detog +
T=T++1 Ltot iaa +d, log²
D. Petolux tā D.
B
For A we give the following bound
21

---

To
P Pto tdg
To D Uto
-D
A
D ++ ma thg D1
S
D
To 1t0 +dg
Ōe
Dto +
8=t+1
3 1 (t + J + de 2
Dg
To
(20 max + Ca-ar )os
D,
To
3vD,ō,
K1/3 log( K)D,,
37 , K1/3 log K ) v DD
VDro
max
0
O
K-/3 K1/3log(K3) log(K)
K22/ log (K)
where the first inequality is by [6c the second inequality holds by swapping the summations and that D (-o 2 D,, third inequality use the following derivation
1(t + of max
+d 5) < 1(t de 2 8) +)+1(s t+ 2 2 o
< 1l + 225) 22
+ 1(t E o $ - 1)) + 1(t < 8 - o ^t+ o
d, 266 s - o'ax))
(34)
the third equality is by swapping the summations, the third inequality uses G, S di S and finally the last inequality uses Lemma 15
DD. K1/ log K
22

---

The bound for B is as follows
Es=ttl
maxt 6,
max
B =
D Detehontth
1= To+1 D
etoomnat loy²
cts tu
1 +āz
7K1/3 log( ()) D e+ Do
tm + s=++1
D
eto mox +d. log²
2ō v Peteiinx** tdg
8, omxx + de 2
Σ
3K2/STng( ()) y P ctoo bnace tūg
s=bbt (=
D
to max tā log²
maax
40,1 + of
F + dr 2
Σ
9/2/3 (K (K)D (D)D+++ st max -4
s
1 11+1170 D 240 mux + log²
maa
4(20 max T Tg-apuux 16.
Dj log"
Too+1
40 may
T
120
Σ
<
max
D. log²
9/333 log log' (KYD, max
s=To+1
Dr
12
S 5max
Dro
log"
9K2/3 log (K)
max
Dr
12
max
( ((max)
log( #2
9/3 (o)
DDoo
where the first inequality due to our skipping procedure that ensures max { a max 7.p S dinax S
DD Ltoina -,. -2, the second equality is by swapping the summations, the second inequality follows
V
by D Ditā. 2 D. and B4 the last inequality follows by Lemma 15 and the last equality uses
dx log(ar/0 mmx)
E A proof of Lemma
Proof. We use the term free round to refer to round r such that vhew is zero. By applying induction on the time step arrivals, there exist U, free rounds in the interval [t. + o G + vy] to which the algorithm can push the arrivals. This ensures that the arrival from round 8, will be rearranged to round r(s) 2 s dg. such that (s)
show that if the algorithm is currently at time t and intends to rearrange the i
d < dinxx. To this end, assume the induction assumption holds for all r < 1, and then proceed with induction step for L.
Induction Base:
The induction base corresponds to the first arrival time, denoted as to. At this time step, all Vto arrivals can be rearranged the free rounds in the interval [fo, + uto 1], which is a subset of [to, to + ogg max - σ, + Uto - 1]. Therefore, the induction base holds.
Induction step:
Assume that we are at round I, and our aim is to rearrange the arrivals of round 4. We define 4 as the last occupied round, where 4, 2 1. So it suffices to prove ( / S of o G, We first note that since the algorithm is greedy, rounds 1, 1,...,4 must also occupied by some arrivals from the past.
23

---

Let to < f be the first round where one of its arrivals has been rearranged to t, and let vio be the number of arrivals at time to that are rearranged to some rounds before Then by induction assumption we know
to Σ n=1
t レ- to S. J -so + Vio +
o to
1(r+ dr 2 to) + U2 +1.
(35)
max
On the other hand, by the choice of to, each occupied round t 1,++,..... I...., 4 must be occupied by exactly one arrival among the arrivals of rounds to..... 1, except for the i, arrivals to that are rearranged to some rounds before t. So we have
4 1 S
1(6o S +
+ 4 1t-1) -14
Σ 1(to Sr st-
1)+ (tt= Σ
1(fo S <r+ St 1) - vioo
r=4g
1-1
Σ
to Σ
1(r d, 2t) -io0
r=
where the second equality holds because Er 1(r d, 2 to) = - to I to in the above inequality and get
We use 35 to bound
to
1--
1
t - - max
+
Σ 1(to Sr+ 1t st)
Σ
1(r + dr to) -
Σ
a 2t)
r=1
to
Σ 1 dh 21) Σ
(r + Jr 2(
max
t=
max
1(r+ Σ
d 2) S σ max v..
(36)
where the last inequality follows by the fact that (onax) rrerz is non-decreasing sequence. So if the algorithm rearranges the v arrivals at round to rounds i + l,...., i1 + Ut, then, using the inequality (36), we can conclude that these rounds fall within the interval [t, E + o ō, + ur).
F Adversarial bounds with dmax cannot benefit from skipping
In this section we show that adversarial regret bounds that involve terms that are linear in dmax such as the bounds of Masoudian et al. (2022), cannot benefit from skipping. We prove the following lemma.
Lemma 18.
VD < min ((s) + DDg) + dmax-
Proof. For any split of the rounds [T] into and S we have
D D3 Ds S Dg + Sldmax S DD++155 + 1S12 d
Thus
VD D3 + 182 dx S 1|S+ / DD + dmaxx
and since the above holds for any S, we obtain the statement of the lemma.
We remind that skipping allows to replace term of order vDby by term of order mins (IS) + Ds) (for simplicity we ignore factors dependent on K). Thus, it may potentially replace a bound of order vD + dmax by a bound of order ming (IS) + /Ds) + d but since by the lemma mins (IS) + /Dg) + dmax ((vD), this would not improve the order of the bound.
24

---

G Details of the Adversarial Analysis
The only difference between our algorithm and the algorithm of Zimmert and Seldin (2020) the implicit exploration and the slightly modified skipping rule. Let & be the original loss sequence, then the adversary can create an adaptive sequence & that forces the player to play according to the implicit exploration rule by simply nown-scaling all the losses by
rulu
la
max
Our regret bound decomposes now into
max E Regr
(ot Lx) leit
Gp
T
mzs le - 2i)
m
T4t Ee)
-Ee,s
+E
For the second term we have
T
K T
T
Te. l 2,
Tei
Dzs S K
Tti +
which can be controlled via Lemma
The first term is bounded by Zimmert and Seldin (020 algorithm on the modified loss sequence) by
Theorem 3) (since the player plays their
T
T
max E
Σ
(2 le) Lei
I <4VKT
KT
no. + 1 log K + S
t=1
T
log K Di
<V
+ +7vDr log K log
Dr
S*
+ +7 Dr log K S D, ----11
KV
log K
TvD.
t=1
2 2olog K
KT
DD - VD + 7 Dr log K S*
DD
7
51
4VKT
DDr log K S
7
51
min {is) + DDs log K + S*
S KT
7
SCIT
where the first equality uses the definition of 7h, the third inequality follows by Va, b> > 0: 2يb < 2(va Vb), and the last inequality uses the following lemma Lemma 19. The skipping technique guarantees the following bound
va
V Dr log K < min
(15 VD log K
SC
Combining the bounds the first and the second terms provides the regret bound in Section 5.2 only remains to provide proof for Lemma 19
Proof of Lemma 19 For any t [T] we have de s /DT/(49K's log(K)), therefore for any
R C [T]:
Σ V
d
d Dr RRy Dr/(49 log(K))
25

---

Hence we can dereive the following lower bound,
min RC
R +
Σ SE(T] R
d, d log(K)² 2
min
r V Dr log(K)- 7" / DD log(K)
r 0. 49D, k lo)(K)
Dr (K)(K),
where the second inequality uses the concavity in r.
H A Bound on S*
Next, we reason about the nature of skips. The following lemma is an adaptation of Zimmert and Seldin [2000 Lemma 5) to skipping threshold. To this end provide lemmas and then conclude then proof.
Lemma 20. Algorithm / Twill skip than I point at time.
Proof. We prove the lemma by contradiction. Assume that $1, 82 are both deactivated at time
1. W.l.o.g. let S 1. Skipping of 81 at time L means / 81 DD/ log (gg(K) >
V D ())) At the time assumed would have been deactivated at round t - or earlier.
82 2 81, which means that 82
Recall that de is the contribution of timestep to the Dr. Let (l1,-.r, (s-)) be indexing of S and 49K (o) We bound the number of skips by
S S 20d.g.
(37)
The above bound together with the fact that incurred delay di3 must be less than the the skipping threshold and the maximal delay dmax give us
S* s 0
K log Kdiz)
o min dinax K log K, V Dr log K x)) logk)
S
|S] + VDg log K }})
0 min duaa K log K, min SClT
where the last inequality follows by Lemma
Proof of bound 37
By Lemma
20 we skip at most outstanding observation per round. Thus,
we have that
m Var.
+
Ei ビi=1
d
drm 2
Dr tam Penttamm/
/02
d
Ve
By solving the quadratic inequality in de,. we obtain
1+ 4e m di
-
Now we prove by induction that de step we have
The induction base holds since de 1. For the inductive
20
1
+ 46 ΣmL Je.
1 + m(m - 1)
m
2
2c
2c
2c
Then the induction step satisfied.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We list all our contributions in the abstract and introduction, and included 548 literature review in the introduction to reflect the scope
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We present all our bounds in Table and discuss about the gap between our results and existing lower and upper bounds the introduction section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
27

---

Answer: [Yes]
Justification: Theorems state their assumptions explicitly. Proofs are provided concisely within the main body, with full details in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This work is based on theoretical analysis.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
28

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This work does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pippscc/puullc//uuu /utee//ggudddeeeedSuuuubmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This work does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This work does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This work does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp:////aurrss.ccc/oooo//hccee
Answer: [Yes]
Justification:
We confirm that we adhere to ethical standards where applicable, and we note that no experiments were conducted part of this research.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on theoretical foundations, and discussing potential societal impacts, positive or negative, beyond its scope.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
30

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "owB9CfTsXu", "reviewer": "Reviewer_2mU9", "summary": "The authors consider the multi-armed bandit problem with delayed feedback, where the loss of a chosen arm is observed several rounds later. In this setting, nearly optimal algorithms have been developed for both stochastic and adversarial environments, as well as best-of-both-worlds (BOBW) algorithms that perform well in both regimes. However, the regret upper bounds of existing BOBW algorithm by Masoudian et al. (2022) has gaps compared to the regret upper bounds of algorithms designed specifically for adversarial environments (Zimmert and Seldin, 2020) and stochastic environments (Joulani et al., 2013) and in particular the algorithm by Masoudian et al. require the prior knowledge of the maximal delay before the game starts.\nTo address this issue, the authors propose an algorithm that achieves a regret upper bound without knowing the maximal delay in advance.\nTo achieve this, the authors introduce a new framework of implicit exploration, demonstrating that this framework can be effectively combined with techniques that skip observations associated with excessive delays.", "questions": "The authors are expected to discuss to what extent the results from Zimmert and Seldin (2020) and Masoudian et al. (2022) can be used in their study.", "limitations": "not applicable", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The differences from existing research are thoroughly discussed. Technically, the introduction of the implicit exploration framework to achieve BOBW regret bounds without using the maximal delay is novel. Fine-tuned adjustments are made to achieve BOBW while employing implicit exploration. Additionally, how the parameter $\\lambda$ is utilized in the proof is clearly explained and discussed throughout the proof.", "weaknesses": "One concern is that the differences between this paper and existing research might not be sufficient. While the authors propose an algorithm that works in both adversarial and stochastic environments, the foundation for handling excessive delays seems to have been largely established by Zimmert and Seldin (2020) (and Masoudian (2022)).\n\nI was unable to check all the proofs in detail, but they appear to be generally correct. However, there seems to be large room for improvement in the overall explanation. Many explanations are not contextualized, making the proofs difficult to read.\nFor instance, Lemmas 11 to 13 are directly taken from Masoudian et al. (2022). However, the algorithm in Masoudian et al. (2022) differs from the one proposed by the authors, so it is unclear whether these results are directly applicable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Concerning the novelty of our approach to handling excessive delays:**  First, we want to emphasize that the work of Masoudian et al. (2022) is unable to cope with excessive delays, because even a single delay of order $T$ renders their regret bound linear in both stochastic and adversarial environments. The work of Zimmert and Seldin (2020) only copes with excessive delays in the adversarial regime. It is the only work on delayed feedback and adversarial losses known to us that is not using control of the distribution drift in the analysis, but it is unknown whether their analysis technique can be applied to stochastic losses to obtain BOBW results. The stochastic part of our analysis is based on the more broadly used approach based on control of the distribution drift (the ratio $x_{t+d_t, i} / x_{t,i}$ of the probability of playing action $i$ at round $t+d_t$, when the observation arrives, to the probability it had when it was played at round $t$). So far the only way to control the distribution drift was by damping the learning rate, but it only works when the maximal delay $d_{\\max}$, which corresponds to the control range, is known, and it adds $d_{\\max}$ linearly to the regret bound. Therefore, this technique fails in presence of delay outliers. We are the first to achieve control of the distribution drift in presence of delay outliers. In order to achieve it we introduced several important algorithmic and analytical tools:\n1. We are the first to control the distribution drift without altering the learning rate. Our control is based on a combination of implicit exploration, which is used to control the drift due to the change of regularizer, and skipping, which is used to control the drift due to the loss shift (Lemma 3).\n2. The challenge in designing a successful implicit exploration scheme is that implicit exploration has to be sufficiently large to control the ratio, but at the same time sufficiently small, because it adds up linearly to the bound. We have shown that the contribution of our implicit exploration to the bound, $\\sum_{t=1}^T \\lambda_{t,t+\\hat d_t}$, does not ruin neither the stochastic nor the adversarial bound (Lemma 4).\n3. We have also derived the first approach to relate drifted and non-drifted regret in presence of delay outliers (Lemma 2). Prior work has only allowed to relate the two when the delays were bounded by $d_{\\max}$, and it was adding $d_{\\max}$ linearly to the regret bound. Thus, it was failing in presence of even a single delay of order $T$.\n\nWe believe that all these tools will find additional applications in other learning settings.\n\n***\n**Clarification concerning the use of Lemmas 11 to 13, which were taken from Masoudian et al. (2022):** We recall that $\\overline{Reg}\\_T= \\sum_{t=1}^T x_{t,i}\\Delta_i$. Substitute this definition into the inequality in Line 435. Lemmas 11 to 13 are used to bound three parts of the inequality in Line 435 by finding the worst-case choice of $x_{t,i}$ for each of the parts. Since the worst-case choice of $x_{t,i}$ is algorithm-independent, the lemmas can be applied. We will add the clarification to the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "58qm7Vh8l8", "reviewer": "Reviewer_oEfL", "summary": "This paper studied the best of both world algorithms for arbitrary delayed feedback. The proposed algorithm does not require prior knowledge of maximum delay $d_{\\max}$ and avoids its linear dependence in the regret bound. To this end, they proposed the implicit exploration that works for the best-of-both-worlds guarantees. The key idea is to relate the number of outstanding observations $\\sigma_{\\max}$ so as not to rely on the boundness of delays.", "questions": "How can we interpret implicit exploration term $\\lambda_{s,t}$? (Is this inspired by controlling the bias term due to an implicit exploration scheme in order to make it applicable to a best-of-both-worlds setting?)", "limitations": "n.a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The first proposal of implicit exploration for BoBW settings. The algorithm is based on FTRL with a hybrid regularizer where a skipping technique is employed, which becomes crucial for the BoBW guarantee. \n\n- When the maximal number of outstanding observations $\\sigma_{\\max}$ is smaller than maximum delay $d_{\\max}$, the proposed method provided a much better bound than [Masoudian et al. 2022].", "weaknesses": "I only see it for writing.  \nThe current main paper more focus on the explanation of the result comparison with [Masoudian et al. 2022]. Although the authors detailed a summary of technical proof in the main text, a more intuitive, and higher-level explanation of algorithmic parts would be appreciated when introducing the proposed technical scheme. For example, the paper does not provide a detailed explanation of the selection of regularizers or learning rates intuitively. For example, what makes analysis challenging due to aiming BoBW bounds could be more highlighted. I guess the additional challenge for dealing with stochastic cases, from [Zimmer and Seldin, 2020] that already uses the FTRL algorithm with a hybrid regularizer, has already been addressed by [Masoudian et al. 2022], but by missing these explanations, it would be hard for readers to see the clear picture of inherently technical challenges of BoBW algorithm for delayed feedback.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**A detailed explanation of the selection of regularizers or learning rates:** The learning rates and regularizers were taken directly from Zimmert and Seldin (2020), because we had to have the adversarial regret guarantee. The intuition behind the choice of regularizers is that the adversarial regret bound, $\\sqrt{KT} + \\sqrt{dT\\log K}$ for fixed delays $d$, and the construction of the matching lower bound combine a lower bound for bandits to show the necessity of the $\\sqrt{KT}$ term, and a full information lower bound to show the necessity of the $\\sqrt{dT / logK}$ term. The negative Tsallis-entropy regularizer with power 1/2 is optimal in the bandit setting, and the negative entropy regularizer is optimal in the full information setting, and the combination achieves the optimal regret bound in the delayed feedback setting. The learning rate $\\eta_t$ is the standard learning rate for bandits, and the learning rate $\\gamma_t$ is the standard full information learning rate. We refer to Zimmert and Seldin (2020) for further details. The primary challenge addressed by our work is that these regularizers and learning rates also work in the stochastic setting. We make a small adjustment of $\\gamma_t$ by a constant due to adjusted skipping.\n\n***\n**What makes analysis challenging due to aiming BoBW bounds:** First, we want to emphasize that our focus is on BoBW analysis in presence of delay outliers, and that the work of Masoudian et al. (2022) cannot handle delay outliers, because even a single delay outlier of order $T$ renders both their stochastic and adversarial regret bound linear. Concerning analytical challenges: the stochastic part of our analysis is based on control of the distribution drift (the ratio $x_{t+d_t,i} / x_{t,i}$ of the probability of playing action $i$ at round $t+d_t$, when the observation arrives, to the probability it had when it was played at round $t$). Control of the distribution drift is the most commonly used approach in bandits with delayed feedback, also used by Masoudian et al. (2022). So far the only way to control the distribution drift was by damping the learning rate, but it only applies when the maximal delay $d_{\\max}$, which corresponds to the control range, is known, and it adds $d_{\\max}$ linearly to the regret bound. Therefore, this technique fails in presence of delay outliers. We are the first to achieve control of the distribution drift in presence of delay outliers. In order to achieve it we introduced several important algorithmic and analytical tools:\n1. We are the first to control the distribution drift without altering the learning rate. Our control is based on a combination of implicit exploration, which is used to control the drift due to the change of regularizer, and skipping, which is used to control the drift due to the loss shift (Lemma 3).\n2. The challenge in designing a successful implicit exploration scheme is that implicit exploration has to be sufficiently large to control the ratio, but at the same time sufficiently small, because it adds up linearly to the bound. We have shown that the contribution of our implicit exploration to the bound, $\\sum_{t=1}^T \\lambda_{t,t+\\hat d_t}$, does not ruin neither the stochastic nor the adversarial bound (Lemma 4).\n3. We have also derived the first approach to relate drifted and non-drifted regret in presence of delay outliers (Lemma 2). Prior work has only allowed to relate the two when the delays were bounded by $d_{\\max}$, and it was adding $d_{\\max}$ linearly to the regret bound. Thus, it was failing in presence of even a single delay of order $T$.\n\nWe believe that all these tools will find additional applications in other learning settings.\nFinally, we note that the analysis of Zimmert and Seldin (2020) only applies in the adversarial setting. It is unknown whether their analysis technique, which is not based on distribution drift, can be applied in the stochastic setting.\n***\n**Interpretation of implicit exploration terms $\\lambda_{s,t}$:** The role of $\\lambda_{s,t}$ is to control the distribution drift (the ratio $x_{t+d_t,i} / \\max(x_{t,i}, \\lambda_{t,t+d_t})$). To control the ratio it cannot be too small, but since $\\sum_{t=1}^T \\lambda_{t,t+\\hat d_t}$ adds up linearly to the bound, it cannot be too large either. Note that $\\lambda_{s,t}$ only depends on the delays, but not the losses.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "woZiMWoRZV", "reviewer": "Reviewer_9WBQ", "summary": "This paper proposes a new best-of-both-world algorithm for bandits with a delayed feedback model. The results simultaneously achieve the latest upper bounds for delayed feedback in stochastic and adversarial (up to a factor). The algorithm design utilizes an implicit exploration estimator and the skipping set. The analysis contains new technical methods for handling the relationship between drifted and standard regrets.", "questions": "1. The reviewer needs clarification on some proof steps. For example, by the definition of the drift regret, the benchmark is the estimated loss $\\hat \\ell_{i^*}$, but when it comes to the stability-penalty decomposition at the beginning of Appendix A, the benchmark becomes the actual loss $\\ell_{i^*}$, which looks inconsistent.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The reviewer thinks this paper is a nice piece of theoretical work. It has several strengths as follows, \n1. This paper's introduction concisely and clearly discusses this work and its relation (both result and theoretical tool aspects) to previous work. This is very helpful for readers to understand the research background and new contribution.\n2. The best-of-both-world theoretical results of this paper combine the known best stochastic and adversarial upper bounds (with a $K^{1/3}$) factor for bandits with delay and improve upon the latest results on the same topic.", "weaknesses": "The reviewer is uncertain whether this paper reaches the NeurIPS bar for the following weaknesses reasons: \n1. The algorithm design itself needs to be more novel. The only new component the reviewer notices is the implicit exploration estimator, which was also related to prior works in adversarial bandits.  \n2. The algorithm design is not optimized. For example, the skipping set $\\mathcal{S_{t}}$ is always expanding, which is counterintuitive: (1) As the threshold $d^t_{\\text{max}}$ is non-decreasing, there should exist observations, previous belongs to the skipping set, with delay less than the increased new threshold. Why does the algorithm design not add these skipped observations to the non-skipped set? (2) Even for observations belonging to the skipping set, when their observations are finally revealed, why does the algorithm not consider the kind of observations? If considered by the decision-making, both types of observations can help improve the algorithm's performance. Even if this modification cannot reduce the regret upper bound, it should be able to improve the algorithm's empirical performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The algorithm design itself needs to be more novel\n\nIt is very common for BOBW algorithms to bear close resemblance to the adversarial algorithms they are derived from, because it allows inheritance of the adversarial regret guarantees. For example, the EXP3++ algorithm (Seldin and Slivkins, 2014) only makes a small modification to the exploration distribution of the well-known EXP3 algorithm, and the Tsallis-INF algorithm (Zimmert and Seldin, 2021) is essentially identical to the INF algorithm designed by Audibert and Bubeck (2010) for adversarial bandits. The major contribution of many BOBW papers, including ours, is the stochastic analysis that stays within the predefined framework of the parent adversarial algorithm, which only allows minor algorithmic modifications due to the necessity to preserve the adversarial regret guarantees. The preservation of the algorithm design is, therefore, a desired feature. The value and technical sophistication of these contributions, including ours, should not be underestimated though. We introduced several important algorithmic and analytical tools:\n1. We are the first to control the distribution drift without altering the learning rates, by using implicit exploration and skipping (Lemma 3). Prior work controlled the drift by damping the learning rates using knowledge of $d_{\\max}$, but this technique adds $d_{\\max}$ linearly to the regret bound and fails in presence of just a single outlier of order $d_{\\max}$. \n2. Implicit exploration design is very delicate, because it has to be sufficiently large to control the drift, but at the same time sufficiently small, because it adds up linearly to the bound. We have designed an implicit exploration scheme that does not ruin neither the stochastic nor the adversarial bound (Lemma 4). Note that our implicit exploration scheme depends on the delays, but not the losses. Therefore, it has a great potential to be useful in other settings with delayed feedback.\n3. We have also derived the first approach to relate drifted and non-drifted regret in presence of delay outliers (Lemma 2). This contribution involves introduction of the greedy rearrangement algorithm (Algorithm 2) and drift control by Lemma 3. Prior work has only allowed to relate drifted regret and the actual regret, when the delays were bounded by $d_{\\max}$, and it was adding $d_{\\max}$ linearly to the regret bound. Thus, it was failing in presence of even a single delay of order $T$. \n\nWe believe that our contribution has the potential to bring a transformative effect to the field of BOBW learning with delayed feedback.\n\n***\n> The algorithm design is not optimized\n\n- **Concerning (1):** when an observation is processed at time $t$ it modifies the playing distribution $x_t$ at time $t$. If at time $t$ we would decide to go back to some old observations, the actual delay from the moment the action was played to the moment it is reconsidered would remain above the updated threshold, so it would not be possible to add it back. \n\n- **Concerning (2):** while it feels wasteful to drop observations, we note that the cardinality of the skipped set is smaller than the regret bound, which is in turn sublinear in the total number of observations. Processing of skipped observations would add a lot of pain in the analysis, but add nothing in terms of the bound (because of matching lower bounds), and almost nothing in terms of empirical performance, because of the small size of the skipped set relative to the total number of observations.\n\n***\n**Q1:** We are sorry, it is a typo. It should be $\\hat \\ell_{t, i_{T}^{*}}$ at the end of the display between Lines 328 and 329 in Appendix A.\n***\n**References**\nY. Seldin and A. Slivkins. One practical algorithm for both stochastic and adversarial bandits. ICML, 2014.\nJ-Y. Audibert and S. Bubeck. Regret bounds and minimax policies under partial monitoring. JMLR, 2010.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "baDU2CIlLy", "reviewer": "Reviewer_bmXx", "summary": "This paper studies the best-of-both-worlds (BOBW) algorithms for MAB with delayed feedback. Compared to previous results, it eliminates the need for prior knowledge on maximum delay $d_{\\text{max}}$, and the regret scales with the number of “outstanding observations” ($\\sigma_{\\text{max}}$) rather than with the delay length as in the previous works. Technique-wise, this is achieved through a new round skipping rule, a new implicit exploration loss estimator, and advanced analysis.", "questions": "1. Why do some citations have no year? E.g., “analysis of Zimmert and Seldin” in Line 58\n\n2. Is the word “outstanding observations” existing in the delayed-feedback literature or named for the first time by the authors? It is just the number of missing observations, right? If so, I personally just feel that the wording is not very informative/natural.\n\n3. Is the idea of “skipping” reflected only through the regret analysis, or both the algorithm design and analysis? From Algorithm 1, I think it is the latter, but Line 86-89 seems to mean the former.\n\n4. Since the BOBW guarantee is obtained through the self-bounding trick, can we directly obtain a regret bound for the intermediate $C$-corrupted regime?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The regret guarantee is significant in the sense that it scales with the number of missing information, rather than how much it is delayed as in previous work. In the latter case, even if there’s only one single delay, it incurs linear regret if this delay is $T$, which however is safeguarded by the regret guarantee in this paper. Such phenomenon has been achieved soly in either stochastic or adversarial regime before, but not in BOBW.  To achieve this, the authors propose new techniques in both algorithm design and regret analysis.", "weaknesses": "1. I feel that the words \"distribution drift/shift\" comes from nowhere in the introduction. Its meaning is not clear to me in the context of delayed bandits, but no sufficient explanation is provided. A reader may not figure it out until the Analysis Section.\n2. The authors use both “multiarm” and “multi-arm” inconsistently. The latter is commonly used.\n3. The contribution summary may need polishing. Points 2-4 (Line 118) seems too  detailed. Currently they are not informative, they could be merged, or not even necessarily included in the contribution summary in my opinion.\n4. The author may consider elaborating more on Line 181-183, i.e., why the additional $K^{1/3}$ factor is a price for BOBW guarantee (in the analysis). This could be an interesting point to BOBW researchers.\n5. When introducing Lemma 2 for the first time (around Line 202), it would be good to briefly talk about what are the key elements to achieve it, rather than let the readers figure it out in the long proof later. Is it due to the analysis (virtual rearrangement) only, or also the skipping rule and/or implicit exploration?\n6. These two works on feedback-delayed bandits should be relevant, but they are not discussed in this paper. One in stochastic regime [1] and the other in adversarial regime [2].\n\nReferences:\n\n[1] Yang, Yunchang, Han Zhong, Tianhao Wu, Bin Liu, Liwei Wang, and Simon Shaolei Du. \"A Reduction-based Framework for Sequential Decision Making with Delayed Feedback.\" In Thirty-seventh Conference on Neural Information Processing Systems. 2023.\n\n[2] van der Hoeven, Dirk, Lukas Zierahn, Tal Lancewicki, Aviv Rosenberg, and Nicoló Cesa-Bianchi. \"A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs.\" In The Thirty Sixth Annual Conference on Learning Theory, pp. 1285-1321. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses:**\n\n\n1. We will add a clarification around Lines 48-49, where the term is first used. Technically, the distribution drift is the ratio $x_{t+d_t,i} / x_{t,i}$ of the probability of playing action $i$ at round $t+d_t$, when the observation arrives, to the probability it had when it was played at round $t$.\n2. Thanks, we will fix it.\n\n3. Thanks for the suggestion.\n\n4. We had to decrease the skipping threshold of Zimmert and Seldin (2020) to control the distribution drift that is due to the loss shift (see Appendix B.2 in the supplementary material). More explicitly, $K^{1/3}$ comes from a bound on the weighted average of loss estimates in Equation (25) that is bounded in Lemma 9. For now we do not know how to remove this factor, but we expect that it might require a different analysis of the distribution drift.\n\n5. The core of Lemma 2, which relates drifted regret to the actual regret, is based on Lemma 3, which controls the distribution drift using implicit exploration and skipping. The factor of 1/4 in front of $\\overline{Reg}\\_T$ in Lemma 2 and the summation of implicit exploration terms come from Lemma 3. Virtual rearrangement of arrivals is needed in the proof of Lemma 2, because at the moment we have no other way to analyze multiple simultaneous arrivals. Lemma 5, which analyzes Algorithm 2 for virtual rearrangements, shows that the additional delay caused by the rearrangements is small (limited by $\\sigma_{\\max}^t$). \n\n6. Thanks for the references.\n***\n**Questions:**\n1. It is a common practice to use \\citeauthor{...} command on repeated mentions of the same paper within a short text span distance, whenever it does not lead to confusion which work is being mentioned. We hope it was not confusing in Line 58. We can add a year if necessary.\n\n2. The term “outstanding observations” was introduced by Zimmert and Seldin (2020). An observation is considered “outstanding” from the moment an action from which it originates is played to the moment it is revealed to the algorithm.\n\n3. Skipping is done both in the algorithm and in the analysis.\n\n4. Yes, it is straightforward to obtain a bound for $C$-corrupted regime.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers a version of multi-armed bandit problem with delays in both stochastic and adversarial settings. The largest contribution of this paper is its scaling against very large delays. All reviewers agree on the novelty, and I recommend acceptance. The authors are recommended to revise the paper based on reviewers' comments.
Decision: Accept (poster)