A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays

Authors: saeed  masoudian
churney  aps
  denmark
julian  zimmert
yevgeny  seldin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-02 14:14:54

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).

Main paper: 
 introduction: 
 Delayed feedback is an 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 , Eick, 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 are 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 to have tighter regret bounds if it 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. (2013) have studied multi-armed bandits with delayed feedback under the assumption that the rewards are stochastic and the delays are sampled from a fixed distribution.Table 1 : Comparison to state-of-the-art. The following notation is used: T is the time horizon, K is the number of arms, i indexes the arms, ∆ i is the suboptimality gap or arm i, σ max is the maximal number of outstanding observations, D = T t=1 d t is the total delay, S ⊆ [T ] is a set of skipped rounds, S = [T ] \ S is the set of non-skipped rounds, D S = t∈ S d t is the total delay in the non-skipped rounds, and d max is the maximal delay. We They provided a modification of the UCB1 algorithm for stochastic bandits with non-delayed feedback (Auer et al., 2002) . They have shown that the regret of the modified algorithm is O i:∆i>0 log T ∆i + σ max ∆ i , where i indexes the arms, ∆ i 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 as outstanding at round t if it originates from round t or earlier, but due to delay it was not revealed to the algorithm by the end of round t. The number of outstanding observations σ t at round t is the number of actions that have already been played, but their outcome was not observed yet. We also call σ t the [running] count of outstanding observations. The maximal number of outstanding observations σ max is the maximal value that σ t 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.In the adversarial setting, multi-armed bandits with delayed feedback were first analyzed under the assumption of uniform delays (Neu et al., 2010 (Neu et al., , 2014)) . For this setting Cesa-Bianchi et al. (2019) have shown an Ω( √ KT + √ dT log K) lower bound and an almost matching upper bound, where K is the number of arms and d is a fixed delay. The algorithm of Cesa-Bianchi et al. is a modification of the EXP3 algorithm of Auer et al. (2002b) . Cesa-Bianchi et al. used a fixed learning rate that is tuned based on the knowledge of d. The analysis is based on control of the drift of the distribution over arms played by the algorithm from round t to round t + d. Thune et al. (2019) and Bistritz et al. (2019) provided algorithms for variable adversarial delays, but under the assumption that the delays are known "at action time", meaning that the delay d t is known at time t, when the action is taken, rather that at time t + d t , 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 t, when an action is played, to round t + d t , 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 et al. (2019) within constants. The algorithm and analysis of Zimmert and Seldin avoid explicit control of the distribution drift and are parameterized by running counts of the number of outstanding observations σ t , which is an empirical quantity that is observed at time t ("at the time of action"). Masoudian et al. (2022) attempted to extend the algorithm of Zimmert and Seldin (2020) to the best-of-both-worlds setting. The stochastic part of the analysis of Masoudian et al. is based on a 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 t , when the loss is observed. Highly varying delays cannot be treated with this approach, because fast learning rates limit the range d t 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 d max is known, and used it to tune the learning rate. Unfortunately, damping of the learning rate to control the drift over d max rounds made d max 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 d max is real and not an artefact of the analysis, because it comes from damped learning rate.We introduce a different best-of-both-worlds modification of the algorithm of Zimmert and Seldin (2020) that is fully parameterized by the running count of outstanding observations and requires no advance knowledge of delays or the maximal delay d max . 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 a tool to limit the time span over which we need to control the distribution shift.Implicit exploration was introduced by Neu (2015) 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-worlds setting. The implicit exploration schedule of Neu leads to Ω( √ T ) 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 a stochastic analysis. We introduce a novel schedule and show that it works in best-of-both-worlds setting.Skipping was introduced by Thune et al. (2019) as a way to limit the dependence of an algorithm on a 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 to a few excessively large delays, it also limits the time span over which the control of distribution drift is needed.In Table 1 we compare our results to state of the art. In a nutshell, we replace terms dependent on d max by terms dependent on σ max , and terms dependent on the square root of the total cumulative delay D = T t=1 d t , by terms dependent on the number of skipped rounds |S| and a square root of the cumulative delay D S = t∈ S d t in the non-skipped rounds S (those with the smaller delay). This yields robustness to excessive delays, because neither σ max nor min S |S| + D S depend on the magnitude of delay outliers. By contrast, both the stochastic and the adversarial regret bounds of Masoudian et al. (2022) become linear in T in presence of a single delay of order T .There are also additional benefits. It has been shown that σ max ≤ d max , and in some cases σ max ≪ d max (Joulani et al., 2013 , Masoudian et al., 2022) . For example, if the first observation has delay T , and the remaining observations have zero delay, then d max = T , but σ max = 1. We also have that min 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 d max , including the results of Masoudian et al. (2022) , cannot benefit from skipping, in contrast to ours.The following list highlights our main contributions.1. We provide the first best-of-both-worlds algorithm for bandits with delayed feedback that is 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 a 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.2. We provide an efficient technique to control the distribution drift under highly varying delays.3. We provide the first implicit exploration scheme that works in best-of-both-worlds setting.4. We provide a procedure relating drifted regret to normal regret in presence of delay outliers.. At the conceptual level, we show that best-of-both-worlds 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 is 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-worlds.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 a 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 in 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 as long as it is clear that these goals are not attained by the paper. 
problem setting: 
 We study the problem of multi-armed bandit with variable delays. In each round t = 1, 2, . . ., the learner picks an action I t from a set of K arms and immediately incurs a loss ℓ t,It from a loss vector ℓ t ∈ [0, 1] K . However, the incurred loss is observed by the learner only after a delay of d t , at the end of round t + d t . The delays are arbitrary and chosen by the environment. We use σ t to denote the number of outstanding observations at time t defined as σ t = s≤t 1(s + d s > t) and σ max = max t∈[T ] σ t 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 pseudo-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:Reg T = E T t=1 ℓ t,It -min i∈[K] E T t=1 ℓ t,i = E T t=1 ℓ t,It -ℓ t,i * T , where i * T = min i∈[K] E T t=1 ℓ t,iis 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 * T can be omitted and the pseudo-regret definition coincides with the expected regret. Throughout the paper we assume that i * T is unique. This is a common simplifying assumption in best-of-both-worlds analysis (Zimmert and Seldin, 2021) . Tools for elimination of this assumption can be found in Ito (2021) .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We present all our bounds in Table 1 and discuss about the gap between our results and existing lower and upper bounds in the introduction section.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
algorithm: 
 The algorithm is a best-of-both-worlds modification of the adversarial FTRL algorithm with hybrid regularizer by Zimmert and Seldin (2020) . It is provided in Algorithm 1 display. The modification includes biased loss estimators (implicit exploration) and adjusted skipping threshold. The algorithm maintains a set of skipped rounds S t (initially empty), a cumulative count of "active" outstanding observations (those that have not been skipped yet), and a vector of cumulative observed loss estimates L obs t from non-skipped rounds. At round t the algorithm constructs an FTRL distribution x t over arms using regularizer F t defined in equation (2) below, and samples an arm according to x t . Then it receives the observations that arrive at round t, except those that come from the skipped rounds, and updates the vector L obs t of cumulative loss estimates. The loss estimates ℓ t are defined below in equation (1). Then it counts the number of "active" outstanding observations σ t (those that belong to non-skipped rounds), updates the cumulative count of outstanding observations D t , and computes the skipping threshold d t max = Dt 49K 2/3 log K . Finally, it adds rounds s for which the observation Algorithm 1: Best-of-both-worlds algorithm for bandits with delayed feedbackInitialize S 0 = ∅, D 0 = 0, and L obs 0 = 0, where 0 is the zero vector in R K for t = 1, 2, . . . do // Playing an arm and receiving observations (except from skipped rounds)Set x t = arg min x∈∆ K-1 ⟨ L obs t-1 , x⟩ + F t (x) // F t is defined in (2) Sample I t ∼ x t for s : (s + d s = t) ∧ (s / ∈ S t-1 ) doObserve (s, ℓ s,Is )L obs t = L obs t-1 + ℓ s // ℓ s is defined in (1)// Counting "active" outstanding observations and updating the skipping threshold has not arrived yet and the waiting time (t -s) exceeds the skipping threshold d t max to the set of skipped rounds S t . Lemma 20, which is an adaptation of Zimmert and Seldin (2020, Lemma 5) to our skipping rule, shows that at most one round s is skipped at a time (at most one index s satisfies the if-condition for skipping in Line 15 of the algorithm for a given t).Set σ t = s∈[t-1]\St-1 1(s + d s > t) Update D t = D t-1 + σ t Set d t max = D t / 49K 2 3 log K //We use implicit exploration to control importance-weighted 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-both-worlds bounds. For any s, t ∈ [T ] with s ≤ t we define implicit exploration terms λ s,t = e -D t D t -Ds . Our biased importance-weighted loss estimators are defined byEQUATIONwhere d s = min d s , min {(t -s) : t -s ≥ d t max } denotes the time that the algorithm waits for the observation from round s. It is the minimum of the delay d s , and the time (t -s) to the first round when the waiting time exceeds the skipping threshold d t max . We use a hybrid regularizer based on a combination of the negative Tsallis entropy and the negative entropy, with separate learning rates,EQUATIONwhere the learning rates are η -1t = √ t and γ -1 t = 49Dt log K .The regularizer is the same as the one used by Zimmert and Seldin (2020) . By inheriting their regularizer we inherit their adversarial regret bound, which is minimax optimal, with just a minor adjustment due to introduction of implicit exploration and a 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 x t isEQUATIONwhereL obs t = t-1 s=1 ℓ s 1(s + d s < t)1(s / ∈ S t-1) is the cumulative importance-weighted loss estimate of observations that have arrived by time t and have not been skipped. We use S * = S T to denote the final set of skipped rounds at time T .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Justification: We confirm that we adhere to ethical standards where applicable, and we note that no experiments were conducted as 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 sure to preserve anonymity (e.g., if there is a special consideration 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, is 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
regret bounds: 
 The following theorem provides best-of-both-worlds regret bounds for Algorithm 1. A proof is provided in Section 5 and a bound on S * can be found in Appendix H. Theorem 1. The pseudo-regret of Algorithm 1 for any sequence of delays and losses satisfiesReg T = O √ KT + min S⊆[T ] |S| + D S log K + S * + K σ max ,where σ max = max t∈[T ] { σ t } is the maximal number of outstanding observations after skipping andS * = O min d max K 1/3 log K , min S⊆[T ] |S| + D S K 2 3 log K .Furthermore, if the losses are stochastic, the pseudo-regret also satisfiesReg T = O   i̸ =i * log T ∆ i + σ max ∆ i log K + K σ max + S *   . Masoudian et al. (2022) provide an Ω √ KT + min S⊂[T ]|S| + D S log K 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 K 1 3 on the delay-dependent term, which is the price we pay for obtaining a best-of-both-worlds guarantee. The price comes from a 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.2). It is an open question whether this factor can be reduced.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 1 2 , a trivial regret lower bound isΩ σ max i̸ =i * ∆i K + i̸ =i * log T ∆i. This bound is almost matched by the algorithm of Joulani et al. (2013) for the stochastic regime only. Our bound has some extra terms, most notably i̸ =i * σmax ∆i log K and S * . It is an open question whether these terms are inevitable or can be reduced.Theorem 1 provides three major improvements relative to the results of Masoudian et al. (2022) : (1) it requires no advance knowledge of d max ; (2) it replaces terms dependent on d max by terms dependent on σ max , which never exceeds d max , 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 delays and replacing√ D log K term with min S⊆[T ] |S| + D S K 2 3 log K , which is never muchlarger, but in some cases significantly smaller. 
analysis: 
 In this section, we present a proof of Theorem 1. We begin with the stochastic part of the bound in Section 5.1, followed by the adversarial part in Section 5.2.We start by defining the drifted regret Regdrif t T = E T t=1 ⟨x t , ℓ obs t ⟩ -ℓ obs t,i * T , where ℓ obs t = t s=1 ℓ s 1(s + d s = t)1(s / ∈ S t )is the cumulative vector of losses received at time t. Lemma 2 is the first major contribution establishing a relationship between Reg drif t T and the actual regret Reg T .Lemma 2 (Drift of the Drifted Regret).Let σ t max = max s∈[t] { σ s }. Then Reg drif t T ≥ 1 4 Reg T -2K T t=1 λ t,t+ dt + λ t,t+ dt+σ t max - σ max 4 -S * ,where S * is the total number of rounds skipped by the algorithm.The core of Lemma 2 is based on controlling the distribution drift using implicit exploration and skipping. In prior work on bounded delays the relation between Reg drif t Tand Reg T was achieved by shifting all the arrivals by d max , leading to an additive term of order d max . This approach fails for unbounded delays, because a single delay of order T prevents shifting and leads to linear regret. We address the challenge by introducing a procedure to rearrange the arrivals (Algorithm 2 below) and advanced control of the drift (Lemma 3 below). A proof of Lemma 2 is provided at the end of the section.Algorithm 2: Greedy RearrangementInitialize υ new t = 0 for all t = 1, . . . , T + d T max for t = 1, . . . , T do for s = 1, . . . , t : s + d s = t do Find the first round π(s) ∈ [t, t + d t max ] such that υ new π(s) = 0Move the arrival from round s to round π(s) and update υ new π(s) = 1The 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 d max . This does not work for highly varying delays, because slow learning rates prevent learning, whereas fast learning rates fail to control the drift. Lemma 3 relies on implicit exploration terms in the loss estimators in equation ( 1) and on skipping of excessive delays, leaving the learning rates intact. Lemma 3 (Drift Control Lemma). Let d t max be the skipping threshold at time t. Then, for any i ∈ [K] and s, t ∈ [T ], where s ≤ t and t -s ≤ d t max , we have x t,i ≤ 4 max(x s,i , λ s,t ).s = ∇ F * s (-L obs t-1), which is based on the regularizer from round s and the loss estimate from round t. It exploits the implicit exploration term λ s,t to show that Given Lemmas 2 and Lemma 3, we apply standard FTRL analysis, similar to Masoudian et al. (2022) , to obtain an upper bound for Reg drif t T. Specifically, in Appendix A we show thatEQUATIONwhere a, b, c ≥ 0 are constants and υ t = t s=1 1 s + d s = t is the number of arrivals at time t (if a round s is skipped at time t it counts as an "empty" arrival with loss estimate set to zero). By combining (4) with Lemma 2, we obtainEQUATIONThen we apply a self-bounding analysis, similar to Masoudian et al. (2022) , and getReg T = O i̸ =i * 1 ∆ i log(T ) + σ max ∆ i log K + σ max + K T t=1 λ t,t+ dt + λ t,t+ dt+σ t max + S * .The details of the self-bounding analysis are 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 a careful study of the evolution of D t throughout the game, and is deferred to Appendix D.Lemma 4 (Summation Bound). For all s ∈[T ], let D s = s r=1 σ r and λ s,t = e -D t D t -Ds , then T t=1 λ t,t+ dt + λ t,t+ dt+σ t max = O( σ max ).Proof of Lemma 2 (Drift of the Drifted Regret)We start with the definition of the drifted regret.EQUATIONNote that when taking the expectation, we rely on the fact that ℓ s with s + d s = t does not affect x t . If max {x s,i , λ s,t } = x s,i , then ⋆ = ℓ s,i x t,i , otherwiseEQUATIONwhere the first inequality uses x t,i ≤ 4 max(x s,i , λ s,t ) = 4λ s,t by Lemma 3, and ℓ s,i ≥ 1, and the second inequality follows by x s,i ≥ 0. Plugging ( 7) into (6) givesEQUATION)It suffices to give a lower bound for R T in terms of the actual regret Reg T . The difference between R T and Reg T is thatReg T = E T t=1 K i=1 ∆ i x t,i , whereas in R T the sum K i=1 ∆ i x t,iis multiplied by the number of arrivals υ t = t s=1 1 s + d s = t at time t, and υ t might be larger than one or zero due to delays.Our main idea here is to leverage the drift control lemma to provide a lower bound for R T in terms of Reg T . Specifically, by Lemma 3 for all r ∈ [0, d t max ], we have max(x t,i , λ t,t+r ) ≥ 1 4 x t+r,i , which implies x t,i ≥ 1 4 x t+r,i -λ t,t+r . Thus, we obtain the following bound for any r ∈ [0,EQUATIONIn Algorithm 2 we provide a greedy procedure to rearrange the arrivals by postponing some arrivals to future rounds to create a 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 5 below we show that arrival originally received at time t stays in the [t, t + σ t max ] interval (note that σ t max ≤ d t max ). When an observation from round s is postponed from arriving at round t to arriving at round t + r for r ∈ [0, d t max ], by ( 9) it is equivalent to replacingK i=1 ∆ i x t,i by 1 4 K i=1 ∆ i x t+r,i -Kλ t,t+r in R T .Note that Algorithm 2 may push an arrival to a round larger than T , which is equivalent to replacingK i=1 ∆ i x t,i by zero. Let υ new t for all t ∈ [T + d Tmax ] be the total arrivals at time t after the rearrangement, and let π(t) be the round to which we have mapped round t for all t ∈ [T ]. Then for any rearrangementEQUATIONThe following lemma provides properties of the rearrangement procedure.Lemma 5. Let σ t max = max s∈[t] { σ s }. Then Algorithm 2 ensures for any t ∈ [T + d T max ] that υ new t ∈ {0, 1}. Furthermore, for any round t ∈ [T ] it keeps all the arrivals at time t in the interval [t, t + σ t max ], such that ∀s ≤ t : s + d s = t ⇒ π(s) -t ≤ σ t max .We provide a proof of the lemma in Appendix E. As a corollary, after the Greedy Rearrangement (Algorithm 2) the number of rounds with zero arrivals is at most σ T max . This is because there will be no arrivals after T + σ T max andT +σ T max t=1 υ new t =T t=1 υ t = T , which implies there are at most σ T max zero arrivals as each round receives at most one arrival. ThereforeEQUATIONwhere the first equality uses the definition ofReg T = E[ T t=1 K i=1 ∆ i x t,i ] and that ∀t ∈ [T ] : υ new t ∈ {0, 1}. Since ∀t ∈ [T ] : π(t) ≤ t + d t + σ t max , we have λ t,π(t) ≤ λ t,t+ dt+σ t max .Together with ( 11), (10), and (8) it completes the proof.The adversarial analysis is similar to the analysis of Zimmert and Seldin (2020, Theorem 2) . In Appendix G we show thatReg T = O √ KT + min S⊆[T ] |S| + D S log K + S * + K T t=1 λ t,t+ dt ,where the first two terms originate from the analysis of Zimmert and Seldin due to structural similarity of the algorithm, S * is due to adjusted skipping threshold, and K T t=1 λ t,t+ dt is due to implicit exploration bias and is bounded by Lemma 4. The proof is completed by the following bound on S * , which is shown in Appendix H. Lemma 6. We haveS * = O min d max K 2 3 log K , min S⊆[T ] |S| + D S K 2 3 log K . 
discussion: 
 We have successfully addressed the challenge of handling varying and potentially unbounded delays in best-of-both-worlds setting. The success was based on three technical innovations, which may be interesting in their own right: (1) A relation between the drifted and the standard regret under unbounded delays (given by Lemma 2, Algorithm 2, and Lemma 5); (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-worlds setting (Lemma 4).The work leads to several directions for future research. One question is whether the best-of-bothworlds bounds could be improved further. In particular, whether the K 1 3 term in the adversarial regret bound could be reduced or eliminated. The term arose due to the need to decrease the skipping threshold of Zimmert and Seldin (2020) to control the distribution drift. It would also be valuable to explore whether it is possible to reduce the S * term and reduce or eliminate the i̸ =i * σmax ∆i 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-worlds bounds.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 asReg drif t T = E       T t=1 ⟨x t , ℓ obs t ⟩ + F * t (-L obs t+1 ) -F * t (-L obs t ) stability       +E       T t=1 F * t (-L obs t ) -F * t (-L obs t+1 ) -ℓ t,i * T penalty      .The penalty term is bounded by the following inequality, derived by Abernethy et al. ( 2015)EQUATIONwhere e i * T represents the unit vector in R K with the i * T -th element being one and zero elsewhere. This leads to the following bound for penalty termEQUATIONwhere we substitute the explicit form of the regularizer into (12) and exploit the propertiesη -1 t - η -1 t-1 = O(η t ), γ -1 t -γ -1 t-1 = O(σ t γ t / log K), and x 1 2 t,i * T -1 ≤ 0.For the stability term, following a similar analysis as presented by Masoudian et al. (2022, Lemma 5 ), but incorporating implicit exploration terms, for any α t ≤ γ -1 t we obtainstability ≤ T t=1 K i=1 2f ′′ t (x t,i ) -1 ( ℓ obs t,i -α t ) 2 .Let A t = s ≤ t : s + d s = t , then due to the choice of skipping threshold, α t = s∈At ls,tsatisfies the condition α t ≤ γ -1 t , where ls,t = K i=1 f ′′ t (xt,i) -1 ℓs,i K i=1 f ′′ t (xt,i) -1 = f ′′ t (x t,Is ) -1 ℓ s,Is K i=1 f ′′ t (xt,i) -1 . Thus we have stability ≤ T t=1 K i=1 2f ′′ t (x t,i ) -1 s∈At ℓ s,i -ls,t 2 = T t=1 K i=1 s∈At 2f ′′ t (x t,i ) -1 ℓ s,i -ls,t 2 S1 + T t=1 K i=1 r,s∈At,r̸ =s 2f ′′ t (x t,i ) -1 ℓ s,i -ls,t ℓ r,i -lr S2For brevity we define z t,i = f ′′ t (x t,i ) -1 and m t s,i = max {x s,i , λ s,t } for any s ≤ t and i ∈ [K]. We begin bounding S 1 by replacing definition of loss estimators from (1) and getE[S 1 ] = T t=1 K i=1 s∈At 2E   z t,i ℓ s,Is 1(I s = i) m t s,i - z t,Is ℓ s,Is m t s,Is K j=1 z t,j 2   ≤ T t=1 K i=1 s∈At 2E   z t,i 1(I s = i) m t s,i - z t,Is m t s,Is K j=1 z t,j 2   = T t=1 s∈At 2 K i=1 E z t,i 1(I s = i) m t s,i 2 - z t,Is 1(I s = i) m t s,i m t s,Is K j=1 z t,j S 1 1 + T t=1 s∈At 2 E z 2 t,Is m t s,Is 2 ( K j=1 z t,j ) - K i=1 z t,Is z t,i 1(I s = i) m t s,i m t s,Is K j=1 z t,j S 2 1Where the first inequality uses ℓ s,Is ≤ 1. We show that S 2 1 has negative contribution to S 1 by taking expectation w.r.t. I s as the followingS 2 1 = T t=1 s∈At E K i=1 z 2 t,i x s,i m t s,i 2 ( K j=1 z t,j ) - K i=1 z 2 t,i x s,i m t s,i 2 K j=1 z t,j = 0Thus we only need to bound S 1 1 , for which we take expectation w.r.t. I s and separate i * from the other arms to getS 1 1 = K i=1 E z t,i 1(I s = i) m t s,i 2 - z t,Is 1(I s = i) m t s,i m t s,Is K j=1 z t,j ≤ i̸ =i * E z t,i x s,i m t s,i 2 + E z t,i * x s,i * m t s,i * 2 - z 2 t,i * x s,i * m t s,i * 2 K j=1 z t,j ≤ i̸ =i * E 4η t x 1/2 s,i + E x s,i * m t s,i * 2 × z t,i * 1 - z t,i * K j=1 z t,j ≤ i̸ =i * 4E η t x 1/2 s,i + E x s,i * m t s,i * 2 × η t x 3/2 t,i * 1 - x 3/2 t,i * (1 -x t,i * ) 3/2 + x 3/2 t,i * ≤ i̸ =i * 4E η t x 1/2 s,i + E η t x s,i * x 3/2 t,i * m t s,i * 2 × (1 -x t,i * ) 3/2 2 -1/2 ≤ i̸ =i * 4E η t x 1/2 s,i + E   4 √ 2η t i̸ =i * x t,i   ≤ i̸ =i * 4E η t x 1/2 s,i + E   16 √ 2η t i̸ =i * (x s,i + λ s,t )   ≤ O   E   η s i̸ =i * x 1/2 s,i   + E [Kλ s,t ]   ,where the second inequality usesz t,i = f ′′ t (x t,i ) -1 ≤ η t x 3/2 t,i along x t,i ≤ m t s,i from Lemma3, the third inequality is due the fact that z t,i * 1 -z t,i * K j=1 zt,jis an increasing function in terms of both z t,i * and i̸ =i * z t,i and we substitute z t,i * ≤ η t x 3/2 t,i * and j̸ =i * z t,j ≤ j̸ =i * η t x 3/2 t,j ≤ η t (1 -x t,i * ) 3/2 , the fourth inequality is due to (1 -a) 3/2 + a 3/2 ≤ 2 -1/2 , the fifth and the sixth inequalities rely on Lemma 3, and finally the last inequality is followed by ∀i : x s,i ≤ x 1/2 s,i and that η t ≤ η s . Combining bounds for S 1 1 and S 2 1 gives the following bound for S 1EQUATIONFor S 2 , we take expectation with respect to I s , I r , and randomness of losses, all separately to getEQUATIONFor simplicity we define ϵ t s,i = µ i -µixs,i m t s,ifor any s ≤ t and any i ∈ [K], for which we have the following bounds0 ≤ ϵ t s,i ≤ λ s,t m t s,i.We then continue from 15 and bound it as the followingEQUATIONwhere the inequality holds because we ignore the negative terms after multiplication and that |(µ i -K j=1 zt,j µj K j=1 zt,j )| ≤ 1. We need to bound each part from (16). We start with S 1 2 ,S 1 2 = K i=1 z t,i µ i - K j=1 z t,j µ j K j=1 z t,j 2 = K i=1 z t,i µ 2 i - K i=1 z t,i µ i 2 K i=1 z t,i ≤ K i=1 z t,i µ 2 i - K i=1 z t,i µ i * 2 K i=1 z t,i ≤ K i=1 z t,i (µ 2 i -µ 2 i * ) ≤ i̸ =i * 2γ t x t,i ∆ i (17)We bound S 2 2 asEQUATIONwhere the last inequality holds because z t,i ≤ γ t x t,i and that x t,i ≤ 4m t s,i , 4m t r,i from Lemma 3. It remains to give upper bound for S 3 2 asEQUATIONwhere the second inequality rely on z t,i ≤ γ t x t,i , λ s,t ≤ m t s,i , λ r,t ≤ m t r,i , and x t,i ≤ 4m t s,i , x t,i ≤ 4m t r,i from Lemma 3. It is suffices to plug bounds in ( 17), ( 18), and ( 19) to obtainE[S 2 ] ≤ T t=1 i̸ =i * 4∆ i γ t E[x t,i ]υ t (υ t -1) + 6 T t=1 Kγ t+ dt (υ t+ dt -1)λ t,t+ dt ≤ T t=1 i̸ =i * s∈At 4∆ i γ t E[x s,i + λ s,t ](υ t -1) + 6 T t=1Kγ t+ dt (υ t+ dt -1)λ t,t+ dtEQUATIONwhere the third inequality uses Lemma 3 and the last inequality holds because of the skipping that ensures γ t+ dt (υ t+ dt -1) ≤ 1. Now, it is sufficient to combine the bounds for S 1 and S 2 in ( 14) and ( 20) and getE[stability] ≤ O   T t=1 i̸ =i * η t E[x 1/2 t,i ] + T t=1 i̸ =i * γ t+ dt E[x t,i ](υ t+ dt -1) + K T t=1 λ t,t+ dt   .(21) Combining the stability bound from (21) and the penalty bound from (13) concludes the proof.In this section we provide a proof of Lemma 3. We start with a few auxiliary results, and then prove the lemma.For the proof we use two facts and a lemma from Masoudian et al. (2022) , and a new lemma. Recall that f t (x) = -2η -1 t √x + γ -1 t x log x.Fact 7. (Masoudian et al., 2022, Fact 15 ) f ′ t (x) is a concave function. Fact 8. (Masoudian et al., 2022, Fact 16 ) f ′′ t (x) -1 is a convex function. Lemma 9. (Masoudian et al., 2022, Lemma 17 ) Fix t and s with t ≥ s, and assume that there exists α, such that x t,i ≤ α max(x s,i , λ s,t ) for all i ∈ [K], and let f (x) = -2η -1 t √x + γ -1 t x log x , then we have the following inequalityK j=1 f ′′ (x t,j ) -1 ℓ s,j K j=1 f ′′ (x t,j ) -1 ≤ 2α(K -1) 1 3 .Lemma 10. If t > s and (t -s) ≤ d t max , thend t max ≤ √ 2d s max , which is equivalent to D t ≤ 2D s .Proof. It suffices to prove that D t ≤ 2D s , which is equivalent to proving that (D t -D s ) ≤ 1 2 D t . We have:D t -D s = t r=s+1 σ r ≤ (t -s)d t max ≤ d t max 2 = D t 49K 2 3 log K ≤ D t 2 ,where the first inequality holds because due to skipping, for all r ≤ t we have σ r ≤ d t max , and (t -s) ≤ d t max .Now we are ready to provide a proof of Lemma 3. Similar to the analysis of Masoudian et al. (2022) , the proof relies on induction on valid pairs (t, s), where a pair (t, s) is considered valid if s ≤ t and (t -s) ≤ d t max . The induction step for pair (t, s) involves proving that x t,i ≤ 4 max(x s,i , λ s,t ) for all i ∈ [K]. To establish this, we use the induction assumption for all valid pairs (t ′ , s ′ ) such that s ′ , t ′ < t, as well as all valid pairs (t ′ , s ′ ), such that t ′ = t and s < s ′ ≤ t. The induction base encompasses all pairs (t ′ , t ′ ) for all t ′ ∈ [T ], where the statement x t ′ ,i ≤ 4x t ′ ,i holds trivially.xt,i max(xs,i,λs,t) we first introduce an auxiliary variable x = F * s (-L obs t-1 ). We then address the problem of drift control by breaking it down into two sub-problems:1.xt,i max( xi,λs,t) ≤ 2: the drift due to change of regularizer, 2. xi xs,i ≤ 2: the drift due to loss shift.The regularizer at round r is defined asF r (x) = K i=1 f r (x i ) = K i=1 -2η -1 r √ x i + γ -1 r x i log x i .We have x t = ∇ F * t (-L obs t-1 ) and x = ∇ F * s (-L obs t-1 ). According to the KKT conditions, there exist Lagrange multipliers µ and µ, such that for all i:f ′ s ( x i ) = -L obs t-1,i + µ, f ′ t (x t,i ) = -L obs t-1,i + µ.We also know that there exists an index j, such that x j ≥ x t,j . This leads to the following inequality:-L obs t-1,j + µ = f ′ t (x t,j ) ≤ f ′ s (x t,j ) ≤ f ′ s ( x j ) = -L obs t-1,j + µ,where the first inequality holds because the learning rates are decreasing, and the second inequality is due to the fact that f ′ s (x) is increasing. This implies that µ ≤ µ, which gives us the following inequality for all i:f ′ t (x t,i ) = - 1 η t √ x t,i + log(x t,i ) γ t ≤ - 1 η s √ x i + log( x i ) γ s = f ′ s ( x i ).Thus, we have two cases, either -1 ηt √ xt,i ≤ -1 ηs √ xi or log(xt,i) γt ≤ log( xi) γs . Case i: If -1 ηt √ xt,i ≤ -1 ηs √xi holds, then we havext,i xi ≤ η 2 s η 2 t = t s .On the other hand, we havet -s ≤ d t max = t r=1 σ r K 3/2 log K ≤ t 2 /2 K 3/2 log K ≤ t 2 ,where the second inequality holds because trivially σ r ≤ r. This implies thatxt,i xi ≤ 2.Case ii:If log(xt,i) γt ≤ log( xi) γs , it implies that x t,i ≤ x γ t γs i . Using x i ≤ max( x i , λ s,t ), we get x t,i ≤ max( x i , λ s,t ) γ t γs = max( x i , λ s,t ) × max( x i , λ s,t ) γ t γs -1 ≤ max( x i , λ s,t ) × λ γ t γs -1 s,t = max( x i , λ s,t ) × λ - √ D t - √ Ds √ D t s,t = max( x i , λ s,t ) × e D t D t -Ds × √ D t - √ Ds √ D t = max( x i , λ s,t ) × e √ D t ( √ D t + √ Ds) ≤ max( x i , λ s,t ) × e 1 1+ √ 1 2 ≤ max( x i , λ s,t ) × 2.Therefore, in both cases we obtainEQUATION)Deviation Induced by the Loss ShiftThe initial steps of the proof of this part are the same as in Masoudian et al. (2022) . However, for the sake of completeness, we restate them here.Since we have x s = ∇ F * s (-L obs s-1 ) and x = ∇ F * s (-L obs t-1 ), they both share the same regularizerF s (x) = K i=1 f s (x i ).For brevity, we drop s from f s (x). By the KKT conditions ∃µ, µ s.t. ∀i:f ′ (x s,i ) = -L obs s-1,i + µ, f ′ ( x i ) = -L obs t-1,i + µ.Let ℓ = L obs t-1 -L obs s-1 , then by the concavity of f ′ (x) from Fact 7, we haveEQUATION)Since f ′′ (x s,i ) ≥ 0, from the left side of ( 23) we get x s,i -x i ≤ f ′′ (x s,i ) -1 µ -µ + ℓ i . Takingsummation over all i and using the fact that both vectors x s and x are probability vectors, we haveEQUATION)Combining the right hand sides of ( 23) and ( 24) gives( x i -x s,i )f ′′ ( x i ) ≤ µ -µ -ℓ i ≤ K j=1 f ′′ (x s,j ) -1 ℓ j K j=1 , f ′′ (x s,j ) -1, and by rearrangement we getEQUATION)where the last inequality holds because f′′ ( x i ) -1 = η -1 s 1 2 x -3/2 i + γ -1 s x -1 i -1. The next step for bounding x i is to boundK j=1 f ′′ (xs,j ) -1 ℓj K j=1 f ′′ (xs,j ) -1in ( 25), where ℓ j = r∈A ℓ r,j andA = r : s ≤ r + d r < t .If there exists r ∈ A, such that r > s and 4 max(x r,i , λ r,r+ dr ) ≤ x s,i , then combining it with the induction assumption for (r + d r , r), where we have x r+ dr,i ≤ 4 max(x r,i , λ r,r+ dr ), leads tox r+ dr,i ≤ x s,i . On the other hand, by the induction assumption for pair (r + d r , t), we havex t,i ≤ 4 max(x r+ dr,i , λ r+ dr,t ).So using x r+ dr,i ≤ x s,i and λ r+ dr,t ≤ λ s,t we can derive x t,i ≤ 4 max(x s,i , λ s,t ). This inequality satisfies the condition we wanted to prove in the drift lemma. Therefore, we assume that for all r ∈ A we have either r ≤ s or x s,i ≤ 4 max(x r,i , λ r,r+ dr ). If r ≤ s, using the the induction assumption for (s, r) together with the fact that λ r,s ≤ λ r,r+ dr , results in x s,i ≤ 4 max(x r,i , λ r,s ). Consequently, in either case, the following inequality holds for all r ∈ A x s,i ≤ 4 max(x r,i , λ r,r+ dr ).(26) Thus, inequality in (26) satisfies the condition of Lemma 9, and for all r ∈ A we get:EQUATION)We proceed by summing both sides of the inequality ( 27) over all r ∈ A and obtainEQUATION3 . Now it suffices to plug this result into (25):EQUATIONwhere the third inequality uses |A| ≤ d s max + t -s ≤ d t max + d s max , and that d t max ≤ 2d s max by Lemma 10, and for the last inequality we use the definitions of γ s and d s max . Combining ( 29) and ( 22) completes the induction step.In this section we show the details of how to apply self-bounding analysis to bound the right hand side of (5).We start from ( 5) and decompose it as followsReg T ≤ E       a T t=1 i̸ =i * η t x 1/2 t,i A +b T t=1 i̸ =i * γ t+dt (υ t+dt -1)x t,i ∆ i B +c T t=2 K i=1 σ t γ t x t,i log(1/x t,i ) log K C       + O K T t=1 λ t,t+ dt + λ t,t+ dt+σ t max + σ max + S * D .We rewrite the pseudo-regret as Reg T = 4Reg T -3Reg T , and then based on the decomposition above we haveReg T ≤ E 4aA -Reg T + E 4bB -Reg T + E 4cC -Reg T + 4D.(30) Masoudian et al. (2022) provide the following three lemmas that give the bounds for the first three terms in (30). Although the algorithm of Masoudian et al. differs from ours, their bounds remain applicable, because they are based on the worst-case choice of x t,i , which is algorithm-independent. Lemma 11. (Masoudian et al., 2022, Lemma 6) For any a ≥ 0, we have:EQUATION)Lemma 12. (Masoudian et al., 2022, Lemma 7) LetEQUATION)It is evident that υ max ≤ σ max , so the bound in Lemma 12 is dominated by O(Kσ max ) term in the regret bound. Lemma 13. (Masoudian et al., 2022, Lemma 8) For any c ≥ 0:EQUATION)By plugging (31),( 32),( 33) into (30) we get the desired bound.First we provide two facts and two auxiliary lemmas. Lemma 14. For any t we have2D t ≥ t s=1 d s .Proof. We show that for any t ∈ [T ] we havet s=1 d s -D t ≤ D t : t s=1 d s -D t = (s≤t)∧(s+ ds>t) ( d s -σ s ) ≤ (s≤t)∧(s+ ds>t) d s ≤ d t max 2 = D t 49K 2 3 log K ≤ D t ,where the second inequality holds because d s ≤ d t max , and the total number of steps that satisfy (s ≤ t) ∧ (s + d s > t) is less than the skipping threshold at time t, which is again d t max . Rearranging the inequality completes the proof.Lemma 15 ( (Orabona, 2022, Lemma 4.13) ). Let a 0 ≥ 0 and f : [0; +∞) → [0; +∞) be a nonincreasing function. ThenT t=1 a t f a 0 + t i=1 a i ≤ T t=0 at a0 f (x)dx.Fact 16. For any x ≥ 0, we have e -x ≤ 1x . Fact 17. For any x ≥ 1, we have e -x ≤ 1 x log 2 (x) .Proof of Lemma 4. We have two summations asT t=1 e - D t+ d t D t+ d t -D t + T t=1 e - D t+σ t max + d t D t+σ t max + d t -D t ,where we show an upper bound of O( σ max ) for each of them.Bounding the First Summation: Let T 0 be the time satisfying D T0 = σmax K 1/3 log(K) , then using Facts 16 and 17 we have For A we give the following boundA = T0 t=1 t+ dt s=t+1 σ s D t+ dt = T0 s=1 s-1 t=0 σ s 1(t + d t ≥ s) D t+ dt ≤ T0 s=1 σ 2 s D s ≤ T0 s=1 σ s √ D s K 1/3 log(K)D s = T0 s=1 σ s K 1/3 log(K) √ D s ≤ O D T0 K 1/3 log(K) = O σ max K 2/3 log 2 (K) ,where the second equality is by swapping the summations, the first inequality holds because D t+ dt ≥ D s , the third inequality uses σ s ≤ d s max ≤K 1/3 log K , and the last inequality uses Lemma 15.The bound for B is as followsB = T t=T0+1 t+ dt s=t+1 σ s D t+ dt log 2 D t+ d t D t+ d t -Dt ≤ T t=T0+1 t+ dt s=t+1 σ s D t+ dt log 2 7K 1/3 log(K)D t+ d t σmax √ D t+ d t = T s=T0+1 s-1 t=T0+1 σ s 1(t + d t ≥ s) D t+ dt log 2 7K 1/3 log(K)D t+ d t σmax = T s=T0+1 s-1 t=T0+1 σ s 1(t + d t ≥ s) 4D t+ dt log 2 49K 2/3 log 2 (K)D t+ d t σ 2 max ≤ T s=T0+1 σ 2 s 4D s log 2 49K 2/3 log 2 (K) Ds σ 2 max ≤ σ max T s=T0+1 σ s 4D s log 2 49K 2/3 log 2 (K)Ds σ 2 max ≤ σ max D T D T 0 1 4x log 2 ( 49K 2/3 log 2 (K)x σ 2 max ) = σ max -1 4 log( 49K 2/3 log 2 (K)x σ 2 max ) D T D T 0 = O( σ max ),where the first inequality follows by σ s ≤ σ max and our skipping procedure that ensures d t ≤ d t max ≤ √ D t+ d t K 1/3 log K , the second equality is by swapping the summations, the second inequality follows by D t+ dt ≥ D s and s-1 t=1 1(t + d t ≥ s) = σ s , the last inequality follows by Lemma 15 , and the last equality uses1 x log 2 (x/ σ 2 max ) dx = -1 log(x/ σ 2 max ) .Bound the Second Summation: The bound for the second summation follows the same approach, but it requires additional care due to existence of σ t max in it. Let T 0 to be the time satisfying D T0 = σmax K 1/3 log(K) , then using Facts 16 and 17 we haveT t=1 e - D t+σ t max + d t D t+σ t max + d t -D t ≤ T0 t=1 D t+σ t max + dt -D t D t+σ t max + dt A + T t=T0+1 D t+σ t max + dt -D t D t+σ t max + dt log 2 D t+σ t max + d t D t+σ t max + d t -Dt B .For A we give the following boundA = T0 t=1 e - D t+σ t max + d t D t+σ t max + d t -D t ≤ T0 t=1 D t+σ t max + dt -D t D t+σ t max + dt = T0 t=1 t+σ t max + dt s=t+1 σ s D t+σ t max + dt ≤ T0 s=1 s-1 t=0 σ s 1(t + σ t max + d t ≥ s) D s ≤ T0 s=1 (2σ s max + σ s-σ s max ) σ s D s ≤ T0 s=1 3 √ D s σ s K 1/3 log(K)D s = T0 s=1 3 σ s K 1/3 log(K) √ D s ≤ O D T0 K 1/3 log(K) = O( σ max K 2/3 log 2 (K) ),where the first inequality is by Fact 16, the second inequality holds by swapping the summations and that D t+σ t max + dt ≥ D s , third inequality use the following derivationEQUATIONthe third equality is by swapping the summations, the third inequality uses σ s ≤ d s max ≤K 1/3 log K , and finally the last inequality uses Lemma 15.The bound for B is as followsB = T t=T0+1 t+σ t max + dt s=t+1 σ s D t+σ t max + dt log 2 D t+σ t max + d t t+σ t max + d t s=t+1 σs ≤ T t=T0+1 t+σ t max + dt s=t+1 σ s D t+σ t max + dt log 2 7K 1/3 log(K)D t+σ t max + d t 2 σmax D t+σ t max + d t = T s=T0+1 s-1 t=T0+1 σ s 1(t + σ t max + d t ≥ s) D t+σ t max + dt log 2 3K 1/3 log(K) D t+σ t max + d t σmax = T s=T0+1 s-1 t=T0+1 4 σ s 1(t + σ t max + d t ≥ s) D t+σ t max + dt log 2 9K 2/3 log 2 (K)D t+σ t max + d t σ 2 max ≤ T s=T0+1 4(2σ s max + σ s-σ s max ) σ s D s log 2 Ds 4 σ 2 max ≤ σ max T s=T0+1 12 σ s D s log 2 9K 2/3 log 2 (K)Ds σ 2 max ≤ σ max D T D T 0 12 x log 2 ( 9K 2/3 log 2 (K)x σ 2 max ) = σ max -12 log( 9K 2/3 log 2 (K)x σ 2 max ) D T D T 0 = O( σ max ),where the first inequality is due to our skipping procedure that ensures max σ t max , d t ≤ d t max ≤ D t+σ t max + dt , the second equality is by swapping the summations, the second inequality follows by D t+ dt ≥ D s and (34), the last inequality follows by Lemma 15, and the last equality uses1 x log 2 (x/ σ 2 max ) dx = -1 log(x/ σ 2 max ) .Proof. We use the term free round to refer to a round r such that υ new r is zero. By applying induction on the time step t, we show that if the algorithm is currently at time t and intends to rearrange the υ t arrivals, there exist υ t free rounds in the interval [t, t + σ t max -σ t + υ t ] to which the algorithm can push the arrivals. This ensures that the arrival from round s, will be rearranged to round π(s) ≥ s+ d s , such that π(s) -(s + d s ) ≤ σ t max . To this end, we assume the induction assumption holds for all r < t, and then proceed with induction step for t.The induction base corresponds to the first arrival time, denoted as t 0 . At this time step, all υ t0 arrivals can be rearranged to the free rounds in the interval [t 0 , t 0 + υ t0 -1], which is a subset of [t 0 , t 0 + σ t0 max -σ t0 + υ t0 -1]. Therefore, the induction base holds. Induction step: Assume that we are at round t, and our aim is to rearrange the arrivals of round t. We define t 1 as the last occupied round, where t 1 ≥ t. So it suffices to prove t 1 -t ≤ σ t max -σ t . We first note that since the algorithm is greedy, all rounds t, t + 1, . . . , t 1 -1 must also be occupied by some arrivals from the past.The only difference between our algorithm and the algorithm of Zimmert and Seldin (2020) is the implicit exploration and the slightly modified skipping rule. Let ℓ t be the original loss sequence, then the adversary can create an adaptive sequence ℓ t that forces the player to play according to the implicit exploration rule by simply down-scaling all the losses byℓ ti =x ti ℓ ti max x t,i , λ t,t+ dt .Our regret bound decomposes now intoReg T = max i * T E T t=1 ⟨x t , ℓ t ⟩ -ℓ t,i * T ≤ max i * T E T t=1 x t , ℓ t -ℓ t,i * T + E T t=1x t , ℓ t -ℓ t .For the second term we haveT t=1 x t , ℓ t -ℓ t ≤ K i=1 T t=1 (1 - x ti x ti + λ t,t+ dt )x ti ≤ K T t=1 λ t,t+ dt ,which can be controlled via Lemma 4.The first term is bounded by Zimmert and Seldin (2020, Theorem 3) (since the player plays their algorithm on the modified loss sequence) bymax i * T E T t=1 ⟨x t , ℓ t ⟩ -ℓ t,i * T ≤ 4 √ KT + T t=1 γ t σ t + γ -1 T log K + S * ≤ 4 √ KT + T t=1 σ t √ log K 7 √ D t + 7 D T log K + S * = 4 √ KT + log K T t=1 D t -D t-1 7 √ D t + 7 D T log K + S * ≤ 4 √ KT + 2 √ log K 7 T t=1 D t -D t-1 + 7 D T log K + S * = 4 √ KT + 51 7 D T log K + S * ≤ 4 √ KT + 51 7 min S⊆[T ] |S| + D S log K + S * ,where the first equality uses the definition of γ t , the third inequality follows by ∀a, b > 0 :a-b √ a ≤ 2( √ a - √ b), and the last inequality uses the following lemma Lemma 19. The skipping technique guarantees the following boundD T K 2 3 log K ≤ min S⊆[T ] |S| + D S K 2 3 log K .Combining the bounds on the first and the second terms provides the regret bound in Section 5. |R| + s∈[T ]\R d s K 2 3 log(K) ≥ min r∈ 0, 49D T K 2 3 log(K) r + D T K 2 3 log(K) - 1 7 r D T K 2 3 log(K) ≥ D T K 2 3 log(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 (2020, Lemma 5) to our skipping threshold. To this end we provide two lemmas and then conclude then proof.Lemma 20. Algorithm 1 will not skip more than 1 point at a time.Proof. We prove the lemma by contradiction. Assume that s 1 , s 2 are both deactivated at timet. W.l.o.g. let s 2 ≤ s 1 -1. Skipping of s 1 at time t means t -s 1 ≥ D t /(K 2 3 log(K)) ≥ D t-1 /(K 2 3 log(K)).At the same time we assumed t -1 -s 2 ≥ t -s 1 , which means that s 2 would have been deactivated at round t -1 or earlier.Recall that d t is the contribution of a timestep t to the sum D T . Let (t 1 , . . . , t S * ) be an indexing of S and c = 49K 2 3 log(K). We bound the number of skips byEQUATIONThe above bound together with the fact that incurred delay d t * S must be less than the the skipping threshold and the maximal delay d max give usS * ≤ O K 2 3 log K d t * S ≤ O min d max K 2 3 log K, D T K 2 3 log K ≤ O min d max K 2 3 log K, min S⊆[T ] |S| + D S K 2 3 log K ,where the last inequality follows by Lemma 19.Proof of bound (37). By Lemma 20 we skip at most one outstanding observation per round. Thus, we have thatd tm ≥ D tm+ dt m /c ≥ m i=1 d ti /c = d tm + m-1 i=1 d ti √ c .By solving the quadratic inequality in d tm we obtaind tm ≥ 1 + 1 + 4c m-1 i=1 d ti 2c.Now we prove by induction that d tm ≥ m 2c . The induction base holds since d t1 = 1. For the inductive step we haved tm ≥ 1 + 1 + 4c m-1 i=1 d ti 2c ≥ 1 + 1 + m(m -1) 2c ≥ m 2c .Then the induction step is satisfied.NeurIPS Paper Checklist 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification: This paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.log(K)) 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
To address this issue, the authors propose an algorithm that achieves a regret upper bound without knowing the maximal delay in advance.
To 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.
strength_weakness: strength_weakness: 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)).

I 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.
For 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.
questions: 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: limitations: not applicable
paper_summary: paper_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.
strength_weakness: strength_weakness: I only see it for writing.  
The 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.
questions: 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: limitations: n.a
paper_summary: paper_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.
strength_weakness: strength_weakness: The reviewer is uncertain whether this paper reaches the NeurIPS bar for the following weaknesses reasons: 
1. 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.  
2. 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.
questions: 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: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. The authors use both “multiarm” and “multi-arm” inconsistently. The latter is commonly used.
3. 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.
4. 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.
5. 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?
6. 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].

References:

[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.

[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.
questions: questions: 1. Why do some citations have no year? E.g., “analysis of Zimmert and Seldin” in Line 58

2. 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.

3. 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.

4. 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: limitations: Yes

Comments: title: Response
Response
comment: Thanks for raising the score. We will use input from all the reviewers to improve the writing.
I appreciate the authors' response. Since the authors addressed my concerns, I will raise the score from 5 to 6. However, as with bmXx, I expect improvements in the overall writing, particularly in the appendix.
Thank you for providing a detailed response. 
I have read the reviews and responses from the other reviewers as well, and then I will keep my score (leaning towards acceptance).
The reviewer thanks the authors for their responses. The reviewer will maintain their score for now.
We thank the reviewer for additional input, which we will incorporate in the final version.

A clarification concerning [2]: the work [2] focuses on adversarial setting only, and they assume that either the delays $d$ are fixed, or the total delay $D$ *and* the maximal delay $d_{\max}$ are known. The focus of our work is on BOBW bounds, on handling excessive delays with no prior knowledge of delays, and on eliminating the dependence on $d_{\max}$. So the challenges addressed by us are very different from theirs. We also note that [2] explicitly state in their Discussion that skipping cannot be applied with their approach, meaning that it is unable to handle delay outliers, and that their bounds depend on $d_{\max}^2$, meaning that even a single delay of order $\sqrt{T}$ would make their bounds linear in $T$.
I'd like to thank the authors for the response. For now, I do not have any other concerns, but I suggest that the authors could improve the writing in furture versions, including (but not limited to):

1. Clarifying "distribution drift/shift", as the meaning here is different from that in supervised learning (which is more well-known).
2. Improving the contribution summary.
3. Giving more details about the extra $K^{1/3}$ factor.
4. Overall, making a clearer roadmap about the analysis. Currently, it's a bit too dense in my opinion.
5. Including those two papers I mentioned, and some discussions (especially [2], the one for adversarial environment and hence is related to FTRL/OMD, why the analysis therein fails to obtain the guarantees here).

I keep my score unchanged as of now and lean towards acceptance.