A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback
Authors: Saeed Masoudian
Julian Zimmert
Yevgeny Seldin
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-armed bandit
Delayed Bandit
Best-of-both-worlds

Abstract: We present a modified tuning of the algorithm of  Zimmert and Seldin [2020] for adversarial multiarmed bandits with delayed feedback, which in addition to the minimax optimal adversarial regret guarantee shown by Zimmert and Seldin [2020] simultaneously achieves a near-optimal regret guarantee in the stochastic setting with fixed delays. Specifically, the adversarial regret guarantee is $\mathcal{O}(\sqrt{TK} + \sqrt{dT\log K})$, where $T$ is the time horizon, $K$ is the number of arms, and $d$ is the fixed delay, whereas the stochastic regret guarantee is $\mathcal{O}\left(\sum_{i \neq i^*}(\frac{1}{\Delta_i} \log(T) + \frac{d}{\Delta_{i}}) + d K^{1/3}\log K\right)$, where $\Delta_i$ are the suboptimality gaps. We also present an extension of the algorithm to the case of arbitrary delays, which is based on an oracle knowledge of the maximal delay $d_{max}$ and achieves $\mathcal{O}(\sqrt{TK} + \sqrt{D\log K} + d_{max}K^{1/3} \log K)$ regret in the adversarial regime, where $D$ is the total delay, and $\mathcal{O}\left(\sum_{i \neq i^*}(\frac{1}{\Delta_i} \log(T) + \frac{\sigma_{max}}{\Delta_{i}}) + d_{max}K^{1/3}\log K\right)$ regret in the stochastic regime, where $\sigma_{max}$ is the maximal number of outstanding observations. Finally, we present a lower bound that matches regret upper bound achieved by the skipping technique of  Zimmert and Seldin [2020] in the adversarial setting.

A Best-of-Both- -orool Algorithm for Bandits with Delayed Feedback
Saeed Masoudian University of Copenhagen saeed. masoudi anōdi tu
Julian Zimmert Google Research zimmert@google. com
Yevgeny Seldin University of Copenhagen seldin@di.. ku. dk
Abstract
We present modified tuning of the algorithm of Zimmert and Seldin [2020) for adversarial multiarmed bandits with delayed feedback, which in addi- tion to the minimax optimal adversarial regret guarantee shown by Zim mert and Seldin simultaneously achieves a near-optimal regret guarantee the stochastic setting with fixed delays. Specifically, the adversarial gret guarantee is O(vTK vdT log K), where T is the time horizon, K is the number of arms, and d is the fixed delay, whereas the stochastic regret guarantee O (Eipe (1, log(T) + A. logg dK1/3 log K). where A are the suboptimality gaps. We also present extension of the algo- rithm to the case of arbitrary delays, which is based on an oracle knowl- edge of the maximal delay dmaz and achieves O(VTK + Volog K + aman K 1/33 log K) regret in the adversarial regime, where is the total delay, and O (ittr( log(T) + omar d log K) regret in the stochas- log
tic regime, where omar is the maximal number of outstanding observations. Finally, we present lower bound that matches the refined adversarial regret upper bound achieved by the skipping technique of Zimmert and Seldin (2000) in the adversarial setting.
Introduction
Delayed feedback is common challenge in many online learning problems, including multi-armed bandits. The literature studying multi-armed bandit games with delayed feedback builds on prior work bandit problems with delays. The researchers have traditionally separated the study of bandit games in stochastic environments [Thompson] 1933] Robbins, 1952| Lai and Robbins
1985 Auer et al., 2002] and in adversarial environments Auer al. 2002b). However, in practice the environments are rarely purely stochastic, whereas they may not be fully adversarial either. Furthermore, the exact nature of an environment is not always known in practice. Therefore, in recent
years there has been an increasing interest in algorithms that perform well in both regimes with no
prior knowledge of the regime (Bubeck and Slivkins 2012 Seldin and Slivkins 2014 Auer and
Chiang 2016, Seldin and Lugosi] 2017] Wei and Luo 2018]. The quest for cest-of-both. botthf-bott-worldds algorithms for no-delay setting culminated with the Tsallis-NN INF algorithm proposed by Zimmert
and Seldin [2019), which achieves the optimal regret bounds in both stochastic and adversarial
environments. The algorithm and analysis were further improved by Zimmert and Seldin [202T] and
Masoudian and Seldin (22T], who, in particular, derived improved regret bounds for intermediate
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

regimes between stochastic and adversarial, while Ito [021]] removed an assumption on uniqueness of the best arm, which was used in the early works.
Our goal is to extend So far the literature multi-armed bandits with delayed feedback has followed the traditional
results to multi-armed bandits with delayed feedback.
separation into stochastic and adversarial. In the stochastic regime Doulani et al. 2013) showed that if the delays are random (generated i.i.d), then compared the non-delayed stochastic multi-armed bandit setting, the regret only increases additively by a factor that is proportional to the expected delay. In the adversarial setting Desaa-iaachi al. [2019] have studied the case of uniform delays
d. They derived a lower bound [(max( KT. /dT log K') and an almost matching upper bound OVVKT log K + VdT log K). Thune et al. [2019) and Bistritz et al. [2019] extended the results to
arbitrary delays, achieving O( KKTlog K VDDlog log regret bounds based on oracle knowledge of the total delay D and time horizon T. Thune et al. [2019] also proposed a skipping technique based on advance knowledge of the delays "at action time". which allowed to exclude excessively large delays from D. Finally, Zimmert and Seldin [2020] introduced an FTRL algorithm with a hybrid regularizer that achieved O + VDlog K) regret bound, matching the lower bound in the case of uniform delays and requiring no prior knowledge of D or T. The regularizer used by Zimmert and Seldin was mix of the negative Tsallis entropy regularizer used in the Tsallis-INF algorithm for bandits and the negative entropy regularizer used in the Hedge algorithm for full information games, mixed with separate learning rates:
K
K Σ (logx; x; 100.-11). 1)
Fi(z) 2
+ 7/ -1
Zimmert and Seldin (0200) also improved the skipping technique and achieved refined regret bound D(VKT + ming + v Dg log K)), where S is a set of skipped rounds and Dş is the total delay in non-skipped rounds. The refined skipping technique requires no advance knowledge of the delays. Their key step toward elimination of the need of advance knowledge of delays was to base the analysis on the count of the number of outstanding observations rather than the delays. The great advantage of skipping is that a few rounds with excessively large or potentially even infinite delays have very limited impact on the regret bound. One of our contributions in this paper a lower bound for the case of non-uniform delays, which matches the refined regret upper bound achieved by skipping.
Even though the hybrid regularizer used by Zimmert and Seldin (2020) was sharing the Tsallis entropy part with their best-of-both. both-worlds Tsallis algorithm from Zimmert and Seldin [2021), and even though the adversarial analysis was partly similar to the analysis of the Tsallis- algorithm, Zimmert and Seldin 2020) did not manage to derive a regret bound for their algorithm in the stochastic setting with delayed feedback and left it as an open problem. The stochastic analysis of the isallis-INF algorithm is based on the self-bounding technique (Zimmert and Seldin 202T]. Application of this technique in the no delay setting is relatively straightforward, but in presence of delays it requires control of the drift of the playing distribution from the moment an action is played to the moment the feedback arrives. [esa-Bianchi et al. (019 have bounded the drift of the playing distribution of the EXP3 algorithm in the uniform delays setting with a fixed learning rate. But tost-of-bohhwoon algorithms require decreasing learning rates [Mourtada and Gaïffas 2019, which makes the drift control much more challenging. The problem gets even more challenging in the case of arbitrary delays, because it requires drift control over arbitrary long periods of time.
We apply an FTRL algorithm with the same hybrid regularizer as the one used by Zimmert and Seldn (2020. but with different tuning of the learning rates. The new tuning has minor effect on the adversarial regret bound, but allows us to make progress with the stochastic analysis. For the stochastic analysis we use the self-bounding technique. One of our key contributions is a general lemma that bounds the drift of the playing distribution derived from the time-varying hybrid regularizer over arbitrary delays. Using this lemma we derive near-optimal regret guarantees for the case of fixed delays. But even with the lemma at hand, application of the self-bounding technique in presence of arbitrary delays still much more challenging than in the no delays or fixed delay setting. Therefore, we resort to introducing an assumption of oracle knowledge of the maximal delay, which limits the maximal period of time over which we need to keep control over the drift. Our contributions are summarized below. To keep the presentation simple we assume uniqueness of the best arm throughout the paper. Tools for eliminating the uniqueness of the best arm assumption were proposed by Ito 2021
2

---

assume that all the outstanding 1. We show that in the arbitrary delays setting with an oracle knowledge of the maximal delay dmnax our algorithm achieves ((VKT= + VD log K + d-maa K1/3 log K) regret bound in the adversarial regime simultaneously with O (Eizso (10g + 3, -ouee dinas K K1/3 log K' regret bound in the stochastic regime, where maz is the maximal number of outstanding observations. We note that maa I dmaxs but it may potentially be much smaller. For example, if the first observation has delay of T' and all the remaining observations have zero delay, then dmmer = T, but O mar 1.
(logT
2. In the case of uniform delays the above bounds simplify to O(VKT VdT K d
dK'1/3 log K) in the adversarial in the stochastic case. For T 2 dK2/3 log K the last term in the adversarial re- gret bound is dominated by the middle term, which leads to the minimax optimal OVVKT + VdT K) adversarial regret. The stochastic regret lower bound is triv-
A; + A. log dK /3/ log K) and O (Eifi- loggT
ially (mmin Livin Eidss 3: 1) 22dd Zizi A. K
log and, therefore, our Σ Ligt-
K
stochastic regret upper bound is near-optimal.
3. We present an SS (VKT + mins( + VDs log K) regret lower bound for adversarial multi-armed bandits with non-uniformly delayed feedback, which matches the refined regret upper bound achieved by the skipping technique of Zimmert and Seldin 2220
2 Problem setting
We study the multi- bandit with delays problem. in which at time t 1, ... the learner chooses an arm Le among a set of K arms and instantancously suffers a loss f,, from a loss vector le E [o, 1J generated by the environment, but &,1, not observed by the learner immediately. After delay of d, at the end of round t + de, the learner observes the pair (t, l,,,,,, namely, the loss and the index the game round the loss is coming from. The sequence of delays d1, d2.... is selected arbitrarily by the environment. Without loss of generality observations are revealed at the end of the game, i.e., t + de S T for all t, where T is the time horizon, unknown the learner. We consider two regimes, oblivious adversarial and stochastic. The performance of the learner is evaluated using pseudo-regret, which is defined as
REST E
Σ
Ce.
min E (E(K]
Σ Eeei
E
Σ (le,, - -bxst)
where i7. E argminge(x]) ET Lea) a best arm in hindsight in expectation over the loss generation model and the randomness of the learner. In the oblivious adversarial setting the losses are independent of the actions taken by the algorithm and considered to be deterministic, and the pseudo-regret is equal to the expected regret.
Additional Notation: We use A" to denote the probability simplex over n + 1 points. The characteristic function of a closed convex set A is denoted by Ix(z) and satisfies I Ix(x) 0 for E A and (z) = oo otherwise. The convex conjugate of a function f R - R is defined by f (y) = suPreR= {1x y)
f())). We also use bar to denote that the function domain restricted to (x),, if E A
A", e.g. ((x) = 00, otherwise
We denote the indicator function of an event & by (() and
use (i) shorthand for 1 1[; = i). The probability distribution over arms that is played by the learner at round denoted by z, A K-1
3 Algorithm
The algorithm is based on Follow The Regularized Leader (FTRL) algorithm with the hybrid regularizer used by Zimmert and Seldin [020). stated in equation [ At each time step let
a, = Dt= 1(s d, 2 t) be the number of outstanding observations and D. Et= de be the
3

---

cumulative number of outstanding observations, then the learning rates are defined as
Σ s=1 Ox 7V log
7 Vt 17.
(2)
where 17 10d + maaz/ (K1/3 1/ log( K))² and Yo 24 dma 22/3 log (K) The update rule for the distribution over actions played by the learner is
v F ( t = arg min (fg x) + F.(x)) zEAR
(3)
where L.ght = E (s d, < t) is the cumulative importance-weighted observed loss and é, is an importance weighted estimate of the loss vector Eg defined by
b,, f (1,
Fe,
At the beginning of round f the algorithm calculates the cumulative number of outstanding observa- tions Dr and uses it to define the learning rate "/o Next, it uses the FTRL update rule defined in (3) to
define a distribution over actions xı from which to draw action I.. Finally, at the end of round
receives the delayed observations and updates the cumulative loss estimation vector accordingly. y, so that Lohs
Lobs + E.= é. (s + dg = t). The complete algorithm is provided Algorithm
Algorithm 1: FTRL with advance tuning for delayed bandit
Initialize Do and La 0x (where Og is zero vector in I
2 for f = 1, 1....,n do
Set o; = = +
Update =0=DDy Di=+
Set. = arg mill (i x) +
I1 Fe is defined in ① and and y in
Sample Ie Ft
Observe (s, L. for all that satisfy + de
Lobe Live + f.1 d,
4 Best-of-both-worldds regret bounds for Algorithm 1
In this section provide cett-of-bothwoollde regret bounds for Algorithm First, in Theorem we provide regret bounds for an arbitrary delay setting, where we assume an oracle access to d Then, in Corollary 2 we specialize the result fixed delay setting.
Theorem 1. Assume that Algorithm is given an oracle knowledge of dmax- Then its pseudo-regret for any sequence of delays and losses satisfies
Regr OVVTK + / D DDlog K ddmaz 11/3 K). Furthermore, in the stochastic regime the pseudo-regret additionally satisfies
Regr o
log(T")
A log dmaw K
Omax
K1/3 1/3 log K
sketch of the proof provided in Section 5 and detailed constants are worked out Appendix C For fixed delays Theorem gives the following corollary.
Corollary 2. If the delays are fixed and equal to d, and T 2 d/3/3 log K, then the pseudo-regret of Algorithm Nalways satisfies
Regr = O + dl log K) and in the stochastic setting it additionally satisfies
Regr O
(Tg(T) +
A, log K ) + dK'/33 log K

---

In the adversarial regime with fixed delays d, regret lower bound is Q (VKT VdT'log K
whereas in the stochastic regime with fixed delays the regret lower bound is trivially 2id Ei di Eigs- A. Thus, in the adversarial regime the corollary yields the minimax optimal regret bound and in the stochastic regime it is near-optimal. More explicitly, it is optimal within a multiplicative in front d.
factor of Lizi 1. K + K-/8 log Eip.. 4,
If we fix total delay budget D, then uniform delays d D/T is a special case, and in this sense Theorem D is also optimal in the adversarial regime and near-optimal in the stochastic regime, although for non-uniform delays improved regret bounds can potentially be achieved by skipping. We also note that having the dependence on man in the middle term of the stochastic regret bound in Theorem is better than having a dependence dimaz since mear S dynar, and in some cases it can be significantly smaller, as shown in the example in the Introduction and quantified by the following lemma.
Lemma 3. Let dmna((S) = maX dg. where S - [1,....,T} is a subset of rounds. Let =
{1. T} \ S be the remaining rounds. Then
Oman
min Sc SEQm...))
{IS) dmaz {
proof of Lemma S is provided in Appendix A
Finally, we note that the result in Theorem D is easily extendable to the corrupted regime, because the proof relies the same seff-bounding technique as the one used by Zimmert and Seldin [202T]. If we denote by B the regret upper bound in the stochastic regime in Theorem and by C the total
corruption budget, then in the corrupted regime the regret would be O (BBttoch
V Bytoch C*). The proof is straightforward, following the lines of Zimmert and Seldin [021 and, therefore, left out.
5 A proof sketch of Theorem
In this section we provide a sketch of proof of Theorem 1
We provide a proof sketch for the
stochastic bound in Section 5.1 Afterwards, in Section 5.2) we show how the analysis of Zimmert
and Seldin 2020 gives the adversarial bound stated in Theorem
5.1 Stochastic Bound
We start by providing a key lemma (Lemma 4 that controls the drift of the playing distribution derived from the time-varying hybrid regularizer over arbitrary delays. We then introduce drifted version of the pseudo-regret defined in (4) for which we use the key lemma to show that the drifted version of the pseudo-regret is close the actual one. As a result, it is sufficient bound the drifted version. The analysis of the drifted pseudo-regret follows by the standard analysis of the FTRL algorithm [Lattimore and Szepesvári 2020 that decomposes the pseudo-regret (drifted pseudo-regret in our case) into stability and penalty terms. Thereafter, we proceed by using Lemma A again,, this time to bound the stability term in order to apply the self-bounding technique [Zimmert and Seldin 2019). which yields logarithmic regret in the stochastic setting. Our key lemma is the following.
Lemma 4 (The Key Lemma). For any i [K] and s,t E [T], where S t and s S dmaz have
Ft.s S 2x
A detailed proof of the lemma is provided in Appendix B Below we explain the high level idea behind the proof.
Proof sketch. We know that x, VF and x, (- so we introduce (- as an auxiliary variable to bridge between x, and r,. The analysis consists of two key steps and is based on induction on (t, s).
Deviation Induced by the Loss Shift: This step controls the drift when we fix the learning rates and
shift the cumulative loss. We prove the following inequality:
3
5
2 Fz.s.
5

---

Note that this step uses the induction assumption for ( d,) for all r < <s:-+< d, = Deviation Induced by the Change of Regularizer: In this step we bound the drift when the cumulative loss vector is fixed and we change the regularizer. We show that
31,4
Combining these two steps gives us the desired bound. A proof of these steps is provided in Appendix
We use Lemma 4 to relate the drifted pseudo-regret to the actual pseudo-regred Let A {s {s: I and 8 d2 = t be the set of rounds for which feedback arrives at round t. We define the observed loss vector at time t as bobs = EeEA. &g and the drifted pseudo-regret as
drift REgT
EE
(ares Robey
pobss (,/57
We rewrite the drifted regret
drift
(Ke, Ra) - Rartt)
Regr
E
1=1
SEA
T
K
Elor, - Poiig)l
SEA,
1=1
T
2
E
JA
Σ> d
where when taking the expectation we use the facts that & has no impact on the determination of and that the loss estimators are unbiased. Using Lemma 4 we make connection between pseudo-regret and the drifted version:
T
--dmax
K
drift RegT
E Fe4d. 1A
E Fr ae A
K
E E
t=dmaa +1
dmna Regr
dmax
where the first inequality follows by Lemma 4 and the second inequality uses Edmur E[Ir, S drijt
drift
dmaz- As result, we have Regr < 2Terr dmaz and it suffices to upper bound RegT We follow the standard analysis of FTRL, which decomposes the drifted pseudo-regret into stabiltiy and penalty terms as
T
Regr
drift
(1e johs) Fi(-
(-iabs (-1.44) FC t,pbo)
+E
F.
j
F- be.
stability
penalty
For the penalty term we have the following bound by Abernethy et al. 2015
penalty
(Fr) F.(x,)) (T Fi(z)),

---

where ei₁ denotes the unit vector in R with the i7-th element being one and zero elsewhere. By replacing the closed form of the regularizer in this bound and using the facts that T 1 n
(11.).
V1 - ---1 (ornt/ log K), and "i,07 S 0, we obtain
K ΣΣ
Te (0g(1/2),)) log K
penolly S O
Σ 2 Spft"
+
2 Mo(K-11 + vo log K.
2 2m1
(5)
In order to control the stability term derive Lemma
Lemma 5 (Stability). Let U2 = |Ar For any 0a S 7
we have
T K
stability <
2f. (I(,)) 2
( Gobe a,)2.
- (x(,))+1 Σx 1" (((2,))-
Furthermore, a;
satisfies an I vo- and yields
T Σ
E Elstability)
Σ
27e 1)u,
2n, Bn, x5. 22,1).. (6)
3/2
[=1 igles
A proof of the stability lemma is provided in Appendix A.3 We apply Lemma
to 66) to give bounds 23/2 1/2 (1 F.,i). Moreover, in
U Exe,, Ft,i 2 SE,,,, F. and Lt,t 3 (1-xa.)
3/2
1/2 order remove the best arm from the summation the later bound use xz, (1 x,,e) S
Eijs Fss S Eigso Fa summations and that each belongs exactly one As, gives the following stability bound
1/2 These bounds together with the facts that we can change the order of the
T Σ
E stability) =0
Σ
E
+
Σ
Σ in
n4a (Vi4d. - 1)E
(7)
1=1
dreef
drift
By combining
5 and the fact that Regr
< 2Regr
+ dmaz, show that there exist
constants a, b, c 0. such that
T
T
T K ox or log(1 xx..
Regr < E
a
Th
t,
1/2
+6
n+d (Ue+d. 1) +c
log K
1=1
1=
1=1
B
+ 4V
1) + 2 70 log K + dmaz.
Self bounding analysis: We use the self-bounde self-bounding technique write Regr 4RegT and then based on B we have
3Regr.
Regr < E 4aA Regr] + [4b Regrl + [4cC Regrl +4D.
For D we can substitute the values of 7 and no and get
D Odmaa (K- 1)1/3 log K).
(10)
Upper bounding A, B, and C' requires separate and elaborate analysis, which we do in Lemmas and respectively. Proofs of these lemmas are provided in Appendix A.2
5
Lemma (A bound for AaA Regr). We have the following bound for any 0:
4a²
4aA - -RegT
log(T/m +1) +)+
(II)
A
7

---

Lemma contributes the logarithmic (in T') term to the regret bound.
Lemma (A bound for 4bB Regr)) Let Umaz m Ut, then for any b 2 0:
4bB Regt I 644 log K.
(12)
is evident that Umax I maax S dmaas so the bound Lemma contributes an (dmas log K) term to the regret bound.
Lemma 8 (A bound for 4cC - RegT). For any 2 0:
128c
4cC - Regr S
(13)
D log K
Part of the pseudo-regret bound that corresponds to Lemma comes from the penalty term related to the negative entropy part of the regularizer. In this part, despite the fact that 0 maz can be much mmaz smaller than dmaa (Lemma 3 the Σipr- A; log K term could be very large when the suboptimality
gaps small. In Appendix D we show how asymmetric oracle learning rate Tr /t/v/ for the negative entropy regularizer can be used to remove the Eigi- 1/4, factor in front of dmaz. The possibility of removing this factor without the oracle knowledge is left as an open question. Finally, by plugging
10
13 into
p
we obtain the desired regret bound.
5.2 Adversarial bound
For the adversarial regime we use the final bound of Zimmert and Seldin non-increasing learning rates:
2021 which holds for any
T K +
REgT S
Σ 1 PAVK-
Nor + 2n V + + log K.
suffices to substitute the values of the learning rates and use Lemma for function v
T
K
I Fovlog K
Regr $
DD: + 70 + +2 +2/KT KT + Kno + /llgg/()))))) to log(K)
=
KT
Vog Dr + dmaz K 1/3 /1/3 K.
6 Refined lower bound
In this section, we prove a tight lower bound for adversarial regret with arbitrary delays, Thune et al. [2019] have proposed skipping technique achieve refined regret upper bounds in the adversarial regime with non-uniform delays. The technique was improved by Zimmert and Seldin [2020), but remained unknown whether the refined regret bounds for regimes with non-uniform delays are tight. We answer this question positively by showing that the regret bound of Zimmert and Seldin (2200 is not improvable without additional assumptions. We first derive refined lower bound for full-information games with variable loss ranges, which might be of independent interest. A proof is provided in Appendix
Theorem 9. Let L1 2 L2 LT > 0 be non-increasing sequence of positive reals and assume that there exists a permutation p [T] + [T], such that the losses at time are bounded in [0. Loggy)K K The minimax regret Reg" in the corresponding adversarial full-information game satisfies
Doog (K)]
Reg"
max
Lts 32
L log(K) (K))
Σ
2
From here we can directly obtain a lower bound for the full-information game with variable delays. This implies the same lower bound for bandits, since we have strictly less information available.

---

Corollary 10. Let (do) be a sequence of non-increasing delays, such that de ST+1- - t and let an oblivious adversary select all loss vectors (L+)T=1 [0, 1] before the start of the game. The minimax regret of the full-information game is bounded from below by
Reg" 52
min |S| + v D3 log(K) where D3 SCIT
E de-
LETTINS
Proof. We divide the time horizon greedily into M buckets, such that the actions for all timesteps inside bucket have to be chosen before the first feedback from any timestep inside the bucket is received. In other words, let bucket Bm = {bm. 0m+1 1]. then Vt E Bm t > bm+1 -
while 3e E Bm de bm+1. This division of buckets has the following properties:
(i) monotonically decreasing sizes: [Bi| 2 [Ba] 2 2 |B
(ii) upper bound the of delays: Vm E [M 1] |Bm
Exe de-
Both properties follow directly from the non-decreasing nature of the delays.
Bml bm+1 bm bm + da... bm do...
Bml min {de + - bm3 2 dim BE
min {t - bm3 2 dbm11-1.
LE
Hence
[Bml 2
dim di-m11-1 domi1 |Bm+1l,
En 1m de [Bm+1] dbmi1 S |Bm+1] |Bml
|Bm 12
(K)) Set S" = =
Bm and let the adversary set all losses within bucket to the same value, then
the game reduces to a full information game over M rounds with loss ranges |Bi [Bl..... ..l...., B
Applying Theorem 3 yields
Loog [R)
Reg
max
[mll
Σ
BBm 12 log(K)
32
m= 10 (K)J
max
1
Σ
de log(K)
= Ω
min [S| SC(T]
Σ rES
de log(K)
32
LES"
7 Discussion
We have presented a best-of- bothowoodssssd analysis of slightly modified version of the algorithm of Zimmert and Seldin (020) for bandits with delayed feedback. The key novelty of our analysis is the control of the drift of the playing distribution over arbitrary, but bounded, time intervals when the learning rate is changing over time. This control is necessary for boot-of-bothworldds guarantees, but it is much more challenging than the drift control over fixed time intervals with fixed learning rate that appeared in prior work.
We also presented adversarial regret lower bound matching the skipping- skipping-based refined regret upper bound of Zimmert and Seldin 2020 within constants.
Our work leads to several exciting open questions. The main one is whether skipping can be used to eliminate the need in oracle knowledge of dmaz- If possible, this would remedy the deterioration of the adversarial bound by the additive factor of dmazz because the skipping threshold would be dominated by / Dg log K. Another open question is whether the amaz term can be eliminated from A, the stochastic bound. Yet another open question is whether the dmaz factor in the stochastic bound can be reduced to Tmaz and whether the multiplicative terms dependent on K can be eliminated. An extension of the results to first order bounds, that depend on the cunulative loss of the best action rather than T. and extension to arm dependent delays are also open questions. For now it was only done in the adversarial setting (Googy and Joulani 202
Van Der Hoeven and Cesa- Bianchi 2022

---

Acknowledgments and Disclosure of Funding
This project has received funding from European Union's Horizon 2020 research and innovation programme under the Marie Skiodowska-Curts grant agreement No 801 199. YS acknowledges partial support by the Independent Research Fund Denmark, grant number 9040-00361B.
References
Jacob D Abemethy, Chansoo Lec, and Ambuj Tewari. Fighting bandits with new kind of smoothness. In Advances Neural Information Processing Systems (NeurIPS). 2015.
Peter Auer and Chao-Kai Chiang. algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. Proceedings of the Conference on Learning Theory (COL.T) 2016.
Peter Auer, Nicolò Aasa-Bincchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47, 2002.
Peter Auer, Nicolò Cesa- Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal Computing, 32, 2002b.
Ilai 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.
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In
Proceedings of the Conference on Learning Theory (COLT), 2012.
Nicol'o Cesa- Besa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora. Delay and cooperation in nonstochastic bandits. In Journul of Machine Learning Research, 2019.
Andras Gyorgy and Pooria Joulani. Adapting to delays and data adversarial multi-armed bandits. In Proceedings of the International Conference on Machine Learning (ICML), 2021.
Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Proceedings of the Conference on Learning Theory (COLT), 2021.
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvari. Online learning under delayed feedback. Proceedings of the International Conference on Machine Learning (ICML), 2013.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Saced Masoudian and Yevgeny Seldin. Improved analysis of the tsallis-inf algorithm in stochastically constrained adversarial bandits and stochastic bandits with adversarial corruptions. In Proceedings of the Conference on Learning Theory (COLT), 2021.
Jaouad Mourtada and Stéphane Gaiffas. On the optimality of the hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20, 2019.
Francesco Orabona. A modern introduction to online learning. Setts://arxisn beexxivv.org/aaie att///aa/1199 1921113331.1113 2019.
Herbert Robbins. Some aspects the sequential design experiments. Bulletin of the American Mathematical Society, 58, 1952.
Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits. Proceedings of the Conference on Learning Theory (COLT), 2017.
Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In Proceedings of the International Conference on Machine Learning (ICML), 2014.
William R. Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25, 1933.
Tobias Sommer Thune. Nicolò Cesa- Misa-Bianchi, and Yevgeny Seldin. Nonstochastic multiarmed bandits with unrestricted delays. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Dirk Van Der Hoeven and Nicolò
Nonstochastic bandits and experts with arm arm- dependent delays. In Proceedings the International Conference on Artificial Intelligence and Statistics (AISTATS), 2022. 2022.
10

---

Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the Conference on Learning Theory (COLT), 2018.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In Proceedings on the International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In Proceedings on the International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Julian Zimmert and Yevgeny Seldin. Tsallis-INF: An optimal algorithm for stochastic and adversarial handits. Journal of Machine Learning Research, 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] All assumptions stated in the statements of the theorems.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The main applica- tions of our work are in theoretical and guarantees for Multi-armed bandit setting with delays. Multi-armed bandit is a very fundamental problem in sequential decision making which basc for many online learning problem. So this is not relevant issue in our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs all thcoretical results? [Yes]
3. If you experiments...
(a) Did you include code, data, and instructions needed to reproduce main experimental results (cither in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 'r us-
ing/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
1f you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]


Reviews:
[{"review_id": "DYotiTsIirL", "reviewer": "Reviewer_vDeQ", "summary": "This paper present an algorithm which achieves the best of both worlds guarantee with delayed feedback between the adversarial world and stochastic world. More specifically, the authors consider two delay settings (fix delay and arbitrary uniform delay) of multi-armed bandit problem, and propose two algorithms that achieve  $\\widetilde{O}(log K + K^{1/3} )$ (the ideal stochastic bound should be $\\widetilde{O}(log K)$) regret within stochastic setting where the loss are sampled i.i.d from a fixed distribution, while ensuring $\\widetilde{O}(\\sqrt{K})$ in the worst case. The algorithms applies the FTRL framework with specific hybrid regularizers and careful learning rate scheduling, which is similar to those from previous works. However, with the novel analysis technique (Lemma 4), the authors show that the proposed algorithms actually achieve the best of both worlds. ", "questions": "1. Is it able to achieve Lemma 4 with episodic MDPs? \n\n2. Is it possible to improve the $d_{max} K^{1/3} \\log K$ and $d K^{1/3} \\log K$  terms in the regret bounds for the stochastic setting? What's the main difficulty in removing such terms from the regret bounds? Is it possible to use SAPO or EXP3++ approaches to avoid these terms? \n\n3. Is it possible to achieve similar results with arbitrary delays with respect to the total delay $D = \\sum_{t=1}^{T} d_t$? \n\n4. Any corruption result? ", "limitations": "None. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Unlike the original multi-arm bandit problem which receives the feedback immediately after playing an arm, the delayed feedback setting is much more complicated as the learner has to maintain sufficient robustness with missing information, which may lead to drastic different strategy. Moreover, it is even harder to achieve best of both worlds results in this setting, which requires the learner to carefully balance the exploration and exploitation. \n\nTo the best of my knowledge, this is the first best of both world results of multi-armed bandit problem with the delayed feedbacks. The analysis is quite different from the approach (and \"cheating-regret\"-\"drift\" decomposition) from $Gy\\ddot{o}rgy$ and Joulani (2021)  and the other approach of Zimmert and Seldin (2020), with the help of the powerful Lemma 4 which controls the drift of the playing distribution by the time-varying hybrid regularizer to handle the arbitrary delays (arbitrary uniform or fixed). Besides, the proof of Lemma 4 is very interesting and may be applied in many related problems. \n\nThis paper does not have any specific weakness point. Overall, the writing is clean and well-organized. ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4A75f3SHlu8", "reviewer": "Reviewer_BKkg", "summary": "This study considers the multi-armed bandit problem with delayed feedback.\nFor this problem, the authors propose a best-of-both-worlds algorithm that achieves minimax optimal regret for adversarial regimes as well as logarithmic regret for stochastic regimes.\nThis result is achieved by modifying the update rules for learning rates of an existing algorithm proposed by [Zimmert and Seldin, 2020].\nThe proposed approach works even for problems with arbitrary (round-dependent) delays.", "questions": "- Are there any known lower bounds for stochastic settings with delayed feedback?\n\n- Can the proposed algorithm handle stochastic regimes with adversarial corruption or adversarial regimes with self-bounding constraint given in [Zimmert and Seldin, 2021]?\nSince the analysis is based on this technique, it appears to be easily extendable.\nIf not, I would like to know why.", "limitations": "The limitations are adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper makes solid contributions to important problems.\n- The paper is well structured and easy to read.\n- The proposed approach appears simple and practical.\n\nWeaknesses:\n\n- Novelty in algorithms and analysis techniques is somewhat limited.\n\nComments:\n\nDelayed feedback and best-of-both-worlds algorithms are both topics of practical importance.\nI consider this paper to be of high importance because it provides a solid contribution to these two topics.\n\nThe proposed algorithm and analysis techniques are based on existing ones and have limited novelty.\nHowever, there are several nontrivial steps in the analysis that require delicate attention, which the authors address in a sophisticated manner.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "40D6jRAyjOP", "reviewer": "Reviewer_Rykq", "summary": "This paper studied the problem of multi-armed bandits problem with delayed feedback. Most of the traditional algorithms focus on either stochastic or oblivious adversary settings, thus in the case where the setting is unknown, these algorithms can not achieve optimal pseudo-regret bound. In order to overcome this problem, this paper provided a slight modification version of Zimmert and Seldin [2020]'s algorithm (adding a constant term $\\eta_0$ and $\\gamma_0$ to the learning rate). By doing that, it can achieve near-optimal regret in both stochastic and oblivious adversary settings.", "questions": "Can the authors comment on the existing lower bound regret in the stochastic setting if they exist one?", "limitations": "There is no potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like the overall idea of the paper to extend the best-of-both-worlds algorithm into a delayed feedback setting. However, I have a few concerns over the contribution of this paper.\n\nAs the algorithm is very similar to Zimmert and Seldin [2020]'s algorithm, the first regret bound analysis against oblivious adversary is also very similar to the analysis in Zimmert and Seldin [2020]'s paper. Furthermore, due to the modification, the newly derived regret suffers another term, $d_{max} K^{1/3} \\log(K)$ compared to the regret of the original algorithm. \n\nThe second regret bound against stochastic setting is interesting and novel as it provides a new feature for the Zimmert and Seldin [2020]'s algorithm (it also requires a new technique of controlling drift of the playing distribution over arbitrary time intervals). \n\nThe third contribution about adversarial regret lower bound, although novel is in my opinion not well connected to current paper since Algorithm 1 does not consider skipping-based refined regret or achieves any regret bound that matches the new lower bound. \n\nTherefore, the main contribution of the paper is to provide a regret bound for a modification of Zimmert and Seldin [2020]'s algorithm against a stochastic setting with a small sacrifice in the regret against an oblivious adversary.  Even though I think this is new and novel, I am unsure whether it is significant enough for publication in Neurips. \n\nminors: There are a few terms mentioned in the paper that I can not find the definition (e.g., uniform delays, minimax regret).\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept