Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback
Authors: Ofir Schlisselberg
Tal Lancewicki
Peter Auer
Yishay Mansour
Venue: NeurIPS 2025 poster ()
Keywords: Bandits
Delayed Feedback
multi-armed bandit
Best-of-Both-Worlds
regret minimization
Primary area: theory
TL;DR: We propose the first Best-of-Both-Worlds algorithm for multi-armed bandits with adversarial delays that matches lower bounds in both stochastic and adversarial settings, significantly improving previous results.

Abstract: We study the multi-armed bandit problem with adversarially chosen delays in the Best-of-Both-Worlds (BoBW) framework, which aims to achieve near-optimal performance in both stochastic and adversarial environments. While prior work has made progress toward this goal, existing algorithms suffer from significant gaps to the known lower bounds, especially in the stochastic settings. Our main contribution is a new algorithm that, up to logarithmic factors, matches the known lower bounds in each setting individually. 

In the adversarial case, our algorithm achieves regret of $\widetilde{O}(\sqrt{KT} + \sqrt{D})$, which is optimal up to logarithmic terms, where $T$ is the number of rounds, $K$ is the number of arms, and $D$ is the cumulative delay. In the stochastic case, we provide a regret bound which scale as $\sum_{i:\Delta_i>0}(\log T/\Delta_i) + \frac{1}{K}\sum \Delta_i \sigma_{max}$, where $\Delta_i$ is the suboptimality gap of arm $i$ and $\sigma_{\max}$ is the maximum number of missing observations. 

To the best of our knowledge, this is the first BoBW algorithm to simultaneously match the lower bounds in both stochastic and adversarial regimes. Moreover, even beyond the BoBW setting, our stochastic regret bound is the first to match the known lower bound under adversarial delays, improving the second term over the best known result by a factor of $K$.

Improved Best-of-Both-Worit Regret for Bandits with Delayed Feedback
Ofir Schlisselberg Tel Aviv University of firs40mail. tau.ac.
Tal Lancewicki
Tel Aviv University
lancewicki0man cmaiil11..mmm..mmm.. tau. ac
Peter Auer
Yishay Mansour
Technical University of Leoben auer@unileoben.c ac
Tel Aviv University and Google Research
mansour maansorryishay@gane yishayyggaaalll...... com
Abstract
We study the multi-armed bandit problem with adversarially chosen delays in the Best-of-Both- Worlds (BoBW) framework, which aims to achieve near-optimal performance in both stochastic and adversarial environments. While prior work has made progress toward this goal, existing algorithms suffer from significant gaps to the known lower bounds, especially the stochastic settings. Our main contribution a new algorithm that, up to logarithmic factors, matches the known lower bounds in each setting individually.
In the adversarial case, algorithm achieves regret of Ö(VKT VD), which is optimal up to logarithmic terms, where is the number of rounds, K is the number of arms, and D is the cumulative delay. In the stochastic case, provide a regret bound which scale as Σr (log (7))A,) + 1 Σ A,Tmarr where A is the sub-optimality gap of arm and max the maximum number of missing observations.
K
To the best of our knowledge, this is the first BoBW algorithm to simultaneously match the lower bounds in both stochastic vironment. Moreover, even beyond the BoBW setting, our stochastic regret bound is the first to match the known lower bound under adversarial delays, improving the second term over the best known result by factor of K.
adversarial regimes delayed en-
Introduction
Delayed feedback presents a significant challenge that sequential decision-making algorithms en- counter in many real-world applications. Notably, delays often inherent part of environments involving sequential decision-making, such as in healthcare, finance, and recommendation systems. As central challenge in Online Learning, delays have been extensively explored in various texts within Multi-armed Bandits (MAB), both in stochastic settings, where losses are generated i..dd from a fixed underlying distribution [18, 23, 38, 34, 35, 5, 12, 19, 36, 15, 29, 25] and adversar- ial settings, where the losses are chosen arbitrarily by an adversary [24, 4, 30, 2, 40, 16, 13, 32, 33].
Roughly speaking, under stochastic losses, delays contribute an additive regret term that does not scale with the time horizon (but with the number of missing observations), whereas under the adversarial losses, delays introduce an additive term that does scale with the horizon. More specifically, for an arbitrary sequence of delays, the best-known regret under stochastic losses is log (T) Kamaz (Joulani al. [18) where the number of rounds, K the number of Es.30 A.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparison of regret bounds (up constants and log (K) factors) to the previous state-of-
the-art regret both under stochastic and adversarial losses under adversarial delays.
Algorithm
Regime
Regret
Joulani et al. [18]
stochastic
Σs (Tg(T) A: + mmaz
(T)
Thune et al. [30]
Zimmert and Seldin [40]
adversarial
VTK + +VD
Gyorgy and Joulani [13]²
stochastic
E End,oo log + Smax +
Masoudian et al. [22]
adversarial
VTK VD 40 +Ko KKmax
4' o'=min min dmnan K2/3, VDK2/3
stochastic
E EnA, log + Omaw K TK log (T) + VD
Our paper
adversarial
Lower Bound
Lancewicki et al. [19] (constant delay)
stochastic
LEd, (0g + +maan 4
Masoudian al. [21]
adversarial
VTK+V
arms, A; is the sub-optimality gap of arm and max is the maximal number of missing observa- tions. Under adversarial losses, the optimal bound is of the order vTK + VD (Thune et al. [30], and later Zimmert and Seldin [40] and Gyorgy and Joulani [13] ), where the sum of the delays.
Remark The VD term in the optimal regret corresponds to the worst-case delay. As shown, for example, in Zimmert and Seldin [40], Masoudian et al. [21, 22], Gyorgy and Joulani [14], this can be replaced with minscrr {]S] + v /Dg), where D3 the total delay of the steps not in S. This can be significantly lighter for some delay values. For simplicity of presentation, we present all bounds in the paper in the worst-case form DD, and note that our bound can also attain the tighter delay dependence in the adversarial case (see Corollary 5.4).
While the regret bounds of delayed Multi-armed Bandit under stochastic losses and under ad adversarial losses are well understood separately, the following question remains open:
Is there single algorithm that, without knowing the nature of the losses a-priori in delayed environment, can achieve the optimal regret bounds in both regimes simultaneously?
Such algorithm is often referred as soatt-ff-bothwworllle algorithm. Masoudian et al. [21. 22] have made significant progress toward answering this question. Their regret bound is O(VTK +
+ क- in the stochastic regime, where x* min(dmaaz'' K2/3 VDK2/3.. However, these bounds are still not optimal.'
VD + Ko Komar + +*) in the adversarial regime and O (Ess.so
log (T)
Omaz + log (K)A;
Our contributions. In this work, we affirmatively answer the above question and present new best-of-botte both- algorithm for Multi-armed Bandits (MAB) with delayed feedback that simul- taneously achieves the near-optimal regret bounds under both stochastic and adversarial losses. Specifically:
In the adversarial regime our algorithm guarantees optimal δ Ō(VTK + VD) regret.
(T) + marr regret. In the stochastic regime algorithm guarantees optimal O iigs
log
A.
In the adversarial regime, compared to Masoudian al. [22] we have an extra logarithmic factor in the VTK term, which independent of the delay. However, we eliminate the additive $* in their
An additional benefit of Masoudian al. [21, 22] is that they are any time algorithms, that do need to
know the horizon I' in advance.
In these papers the vD is actually minsc |r] { [|S] + /Ds}. where Dg is the total delay of the steps not in S. We wrote the worst-case for the simplicity of the table.

---

bound, which is significant when dmaz is very large; even a single large delay causes the regret to scale as VD3//3 rather than our vD delay term, which is tight to the lower bound of Masoudian et al. [21].
Even more significantly, in the stochastic regime, our bound improves the OiE; Z. log (K)
Omaz +*)
term from the bound of [22] O( x Σ; Tman At). That is, for each term in the summation, we achieve an improvement by a factor of A log (K). This is significant improvement. For example, consider the simple case of fixed delay d, which implies oaar = d, and constant number of actions. For any sub- sub-optimality gaps our regret is at most vT + d while there is setting where the regret of [22] is at least VdT. Moreover, if the maximum delay is large, & can be as large as vD, offering no improvement over the additive delay term in the adversarial setting.
Our bound in the stochastic regime represents an improvement even compared to sfate-of-the-arr re- sults for algorithms specifically designed for the stochastic case, Specifically, Joulani et al. [18] pro- vides the best-known result for stochastic losses with adversarial delays where their bound includes an additive term of Engi maz A;, which we improve by factor of ((K). While Lancewicki et al. [19] reduce this dependence on K. their result applies only to the case of stochastic delays. Moreover, their regret bound scales with the maximal sub-optimality gap, rather than the average. For example, in the simple case of a fixed delay d, their additive term is d max; A,, whereas ours is d
R Σ, A; offering a strictly better dependence on the problem parameters in many scenarios.
1.1 Additional Related work
Delayed MAB with stochastic losses. The problem was first addressed by Dudik et al. [9]. who analyzed the case of constant delays and established a regret bound with linear dependence on the delay. This line of work was extended by Joulani et al. [18], who allowed the delays to change through time. Subsequent work introduced several important refinements: Zhou et al. [38] distin- guished between arm-dependent and arm-independent delays; Pike-Burke et al. [23] introduced an aggregated rewards model where only the sum of rewards that arrive at the same round is observed; and Lancewicki et al. [19] studied delays in the contexts of reward-dependent or reward-independen delays. More recently, Tang et al. [29], Schlisselberg et al. [25] and Zhang et al. [37] studied settings in which the delay is equal to the payoff.
Delayed MAB with adversarial losses. Delayed feedback have also been explored in adversarial settings, where both rewards and delays can be chosen adversarially. Quanrud and Khashabi [24] studied this problem in the full-information setting. The bandit setting was first addressed by Cesa- Bianchi et al. [6], who analyzed the case of constant delay. This line of work was extended by Thune et al. [30] who considered general adversarial delays under the assumption that the delay known at the time the arm is pulled, Subsequently, Gyorgy and Joulani [13] and Zimmert and Seldin [40] removed this assumption and analyzed the case where the delay is unknown at the time of the action. Finally, Van Der Hoeven and Cesa- Biannci [32] extended the setting to allow for arm arm-dependent delays.
"Best of Both Worlds" without delays. The "Best of Both Worlds" framework in multi-armed bandits was introduced by Bubeck et al. [3], who proposed an algorithm that initially follows a stochastic-style strategy but switches to standard adversarial algorithm upon detecting signs of adversarial losses. This adaptive approach was further developed by Auer and Chiang [1]. An alter- algorithm and prove that it achieves instance-
native perspective is to start with an adversarial-sty dependent regret bounds in stochastic settings as well. In this direction, Seldin and Slivkins [27] and Seldin and Lugosi [26] adapted the EXP3 algorithm to perform well in both regimes, while Zimmert and Seldin [39], Dann et al. [8], Ito et al. [17] extended this idea to Follow- The- Regulaaglr Leader (FTRL), achieving optimal performance across both adversarial and stochastic settings.
'A similar result appeared in Bistritz et al. [2], however, there are some issues in their analysis for further details footnote in Gyorgy and Joulani [13].
3

---

Protocol
Delayed MAB
for E [T'] do
2:
Agent picks action de E [
3:
Agent incurs loss (az) and observes feedback ((L,(a)),d)) it d.).
Settings
We study the Multi-armed Bandit (MAB) problem with delayed feedback, summarized in Protocol 1. In each round 1, 2,2,.... 7, an agent chooses an arm ag E [K] and suffers loss (((a),, where ((()) E [0, 1 can be either stochastic or adversarial. Under the stochastic regime for each i E [K], {4(0))7=1 iddd D, where D; is some distribution with expectation μt, Under the adversarial regime the loss sequence { are chosen arbitrarily by an oblivious adversary. Unlike the standard MAB setting, the agent does not immediately observe (a(a)) at the end of round f; rather, only after de rounds (namely, the end of round de) the tuple (t, (a:)) is received as feedback. The delays {de) are chosen by an oblivious adversary and are unknown at action time.
The performance of the agent is measured as usual by the the difference between the algorithm's cumulative expected loss and the best possible total expected reward of any fixed arm:
T
R
E
(aa))
min E
Σ (1)
In the stochastic case the regret also be written as,
T
T
RT = E
Moi
Tu- = E
A
t=1
where i' denotes the optimal arm and A; 14 pe- for all i [K].
Additional notation. We denote the total delay by D = DI t= de and the maximal delay by dmax (ax d, The amount missing feedback at time is defined by (t) = |[ T S t, + d, > *HI and the maximum over (t)) is denoted by maa m (t). The rounds observed before and available at round t are denoted by B(t) {s + d, < t}. For X R, [X] denotes the set of all positive integers I X.
Notation for the algorithms. Let denotes a sequence of rounds that the algorithm pro- cess. S.n is the first elements in S and S.n. is S except for the last n elements. (S() is the number of pulls of arm i in the rounds of S, (s( = (.(S) Exss., (s)
the empirical mean over and wi) = min {1, V 2log (T) a.(S) } is a confidence width. (S) min {Ā= + width, uc.;(S.-1))} and Icb,(S) max {Ø; width (Sb, are upper and lower confidence bounds with respect to the empirical average. The algo- rithm also maintains confidence bounds around an average importance sampling estimator. Let I,(S) = E.es 10,=5()((s) be the sum the estimators over rounds in S, and TT(S)
(=(s)
1ST T.,)S) be the average. We also define width(S) min (1, 2K log (7) S
Icb((S)
max (M:(S) Icb and (S) = -min (u,()) + width uch, (S.-1)) Fi- nally, we define ucb"(S) (S) min; (ueb,(S), (S)).
3 Algorithm
Our algorithm, sketched in Algorithm 2 and formally described Algorithm 5, builds on the SAPO algorithm of Auer and Chiang [1]. The main idea is to integrate external algorithm for adversarial settings, ALG. Our algorithm initially follows a stochastic-like strategy while monitoring whether the environment exhibits stochastic behavior. If this assumption is violated, it switches to ALG.

---

At its core, the algorithm is based on successive elimination (SE) framework [11], maintaining of active arms played with equal probability. It tracks a confidence bound, width, which defines upper and lower estimates for each arm's mean. When arm is found to be non-optimal, it is eliminated. However, unlike standard SE methods, the algorithm continues to play eliminated arms but with reduced probability. This accounts for the possibility that losses are adversarial an arm that appears suboptimal at one point may later turn out to be optimal. To verify the stochastic nature of arms, the algorithm employs the BSC procedure assess the nature of active arms, and a more advanced procedure EAP for assessing and determining the sampling probability of non-active arms.
Algorithm Sketch of Delayed SAPO Algorithm
Require: Number of arms K, number of rounds T K, Algorithm ALG. 1: Initialize active arms A (1,..., K}. S =
2: for trtt = 1, 2,
do
3: for E (tt) S do
Iterating newly received feedback
4:
=
5: not SS) then
Non-stochastic behavior on active arms (Procedure 3)
6:
Switch to ALG.
7:
fi A A (S) (S) > ucb"(S)}
Elimination
8:
for Each eliminated arm do OF: 2 0 Vj [log (T))
9:
E, 0,
10:
for
TE [[K] A) do
11:
pt(t), err = (A)( & Get the reduced probability for the non-active arm (Procedure 4) if err then
12:
b. -oonsttochsttic behavior on nonactive arms
13:
Switch to ALG.
VEEA (1) = (1 ()-E)E((())AC)) P,(() /|A(O) EEqual probability for active arms
14:
15:
Sample a2 p(t), observe feedback and update variables
Basic Stochastic Checks (BSC) Subroutine. This procedure performs two checks. The first ensures that an unbiased estimate of the mean of each arm remains within its confidence interval, expanded by an additional radius. In the stochastic regime, using standard concentration bounds we have that with high probability,
lcb;(S) 14 S (S()) + width(S);
T&,S)) width(S) S μ. ucb,(S).
Thus, in line of Procedure 3, we check that the above conditions are met.
The second check in BSC constructs a lower bound on the regret and verifies that it is indeed smaller than the expected regret in the stochastic regime, which can be shown to be Ō(vTK + mazz) under stochastic losses. To define this lower bound, we use the fact that, with high probability, μ² < ucb" ucb"(S). Thus, Eves (s') - (S)) is lower bound on the regret, which forms the condition line 3 of the procedure.
Procedure 3 Basic Stochastic Checks (BSC) Subroutine
Require: Series of processed pulls 5
1: if 3i E A (S) [lcb.(S) width USb width(S)) then
2: return False
if Ev's (sa, (S)) 272 KT log (T) + 10 log (K) then
4: return False
return True
Eliminated Arms Processing (EAP) Subroutine. Since we do not know advance whether we are in the stochastic or adversarial regime, we cannot completely eliminate an arm - if we did, the adversary could assign losses of 0 after elimination of an arm, and we would never detect this. Therefore, we maintain positive sampling probability even for eliminated actions. EAP maintains these probabilities for eliminated arms and checks whether the estimated loss significantly smaller than the empirical mean at elimination. Intuitively, if we are in the stochastic regime, we want the probability of playing an eliminated arm decrease over time. Conversely, we suspect the loss after climination is significantly smaller than the empirical mean the elimination time, increase
5

---

Procedure 4 Sketch of Eliminated Arms Processing (EAP) Subroutine
Note: The variables Es, rs, and CT are initialized Algorithm and updated through multiple calls of this procedure.
Require: Arm i
1: p :-=-p p ju is the empirical average the elimination time of
2: Let B3 be observed rounds after elimination in which was played and the sampling probability
was p
3: while B C * do
4:
for B C do
5:
C C. [s}
6:
Let S. be the samples processes so far in phase r;
7:
! F4 - ((())) 2 A then
D phase error
8:
E = Eg + 1, M max (N 22 J. p. = min {p!, 2p. ).r +
9:
if E; 2 3 log (7") then return 0, True
Do Switch to adversarial algorithm
break
11:
if ST
[ then No+11 2N7; pit 2P ri =
b phase ended
12:
break
14:
15:
return P." False
that arm's probability to monitor it more closely. If there is sufficient confidence that the arm does not behave stochastically, we switch to the adversarial algorithm.
In more detail, the probability of playing an eliminated arm is updated in discrete phases. Let S be the set of processed rounds at the time climination of arm i. We denote A, Swidth, (8.), ie the width at elimination time. As we'll later see in the analysis, A; is indeed good estimate of the sub-optimality gap of arm in the stochastic case (see Lemma D. Each phase has maximum length NY
(p/ where P is the sample probability of arm in its rth phase and y 2K + m.(S;) This value is always 92 / K), but can be high uniform probability over the active arms at the time of climination. we reach the maximum length NT, then we have acquired additional pf = 0 samples from arm i. In this case, we can safely halve the sampling probability of arm and start new phase with doubled maximum length (line 1 11). During the phase, we monitor whether the average importance sampling estimate the loss ju(ST) is smaller than ã4 = (S;) by more than NT I) where ST is the sequence of processed rounds in phase If this condition is met, referred as "phase error", in means that the observed losses appear slightly non non-stochastic. Thus, we terminate the phase but now double the sampling probability of arm and halve the maximum phase length accordingly (line 6).
27
In the stochastic regime, phase errors with constant probability, but the probability that they will happen O(log (I")) times is negligible. In such cases, we transition to the ad adversarial algorithm.
During a phase with sampling probability p. we process only the observed rounds after elimination in which arm i was played and the sampling probability different sampling probability p', is stored in a "probability bank" which we denote by By" and processed only if to utilize most samples, even they are observed after their respective phases end, and play an important role in removing factor of the number of phases (O(log (T))) from the delay term in the regret.
p. If sample is observed with
phase is initiated with probability p'. The probability banks allow us
We note that the initial probability assigned in the first phase differs from that Auer Chiang [1], and crucial for obtaining adversarial regret bound that scales with / KT instead of K / achieved in [1].

---

Stochastic analysis
Theorem 4.1 The regret in the stochastie settings is bounded by:
K
log (T)
Roto S 5O
Σ
+ Omar Aang log (K)
A
The first term above the optimal MAB regret under stochastic losses without delays. The second term is the additional regret due delay and, in general, cannot be poproved-excepp for the log (K) factor, due to the lower bound for constant delays (see Table 1). We note that with a more involved algorithm and analysis, We are able to eliminate the log (K) factor and match this lower bound. For simplicity of presentation, the full details are deferred to Appendix F. The dependence [22] in the stochastic regime by factor of
maz
improves upon the BoBW result of Masoudian ((K/A?) for each i. Moreover, it is tighter by a factor of K compared to the best previous known algorithm that specifically designed for this regime (Joulani et al. [18]).
Proof sketch: The total regret can be decomposed as,
Roto
Σ [E[K]
(T)
Σ m,(T:) + Σ (m,(T) mi(T:)) [E|K]
[E[K]
where mt(() is the number of pulls of arm i, up to time and Tı is the elimination time of arm i. The first term above is the regret up elimination and second term is the regret after elimination. (Recall that we need to keep sampling eliminated arms.)
Regret up to elimination. The regret before elimination analysis largely follows standard Stochastic Elimination (SE) with delayed feedback arguments. However, achieving dependence on Aavg rather than A necessitates a new algorithmic component and technical argument. We start by further decomposing the regret up elimination:
Σ m)(Ti)A KE[K]
Σ n((T))i+ + Σ (m)(t))-((T))) - mi(T)))).
iе[K]
RE[K]
where n. (t) is the number of observed samples from arm i. Similar standard non-delayed SE analysis, we can show that with high probability, each suboptimal arm is eliminated whenever O log (T) samples from arm have been observed. Thus, (T, = A.
(T) For the second term above, recall that the number of missing feedback is bounded by mmazi but only fraction of the missing feedback is from arm i. Loosely speaking. if pmmer = max (t)) is the maximal probability of sampling i before elimination, then the number of missing feedback from arm at time 7i is roughly bounded by (1, - (T,),) S manpp Ma of active arms at the time of elimination then p. bounded by
A
max Further note that if n; is the number
Overall, the total regret up to elimination
log (T)
Σ Umaz
A
Fi
For the second term, each A, can be trivially bounded by Amaz. and 1/ S E 14 log (K), resulting in E, aman A; < O(FmazAmon log (K)). In order to have dependency with Xt respect Aong instead Aman a more detailed argument is required. Unlike regular SE algorithms, an arm isn't eliminated when the ueb of some other arm is lower than its lcb. Instead, the algorithm climinates when there are multiple widths between the two (see line 7 in algorithm 2). This stricter condition ensures that arms roughly climinated in decreasing order of A, Specifically, we show the following lemma:
Lemma 4.2 arm i was eliminated before is then, A., S 20A
We note that this is relatively general trick that may be used other regimes; see remark 2.
For the first half of eliminated arms where Ks 2 K/2, the additive delay term at most order of Ein,3/22 Zmnn Ri A I Omoz Aweg- Using the above lemma show that for second half of
7

---

eliminated arms A; = O(Aavy) yielding an additive delay term of at most ( Aoeg log ()). Overall we get that the regret up to elimination is bounded by EiE[K] (; A S maax log (K).
Σ A;
log (T)
+
Regret after elimination. For the regret after elimination, we break the number of pulls of arm i after elimination for pulls that where processed by algorithm and pulls that where not processed by the algorithm (either because the feedback had not returned or the samples remained in the probability bank):
log (7)
mT(T) mm((T) ms(s +
Σ 3
nc(M
where is the total number of phases of arm i, S are the samples processes at phase r and M," denotes the post-elimination rounds where the probability of pulling arm i was p, but these were not processed by the algorithm (either because the feedback was not observed or the rounds remained unprocessed in the probability bank).
Recall that the maximum length of phase r is NY = ((1/(p; (,)). Additionally, the fact that arms are only eliminated when the empirical average exceeds ueb" by more than multiple widths allows to show that Å, se A, (see Lemma D.10). Using standard concentration bounds, (,(())) R N. ~ 1/4,. To bound the number of phases, note that the maximum phase length can be either doubled or halved. The number of times it is halved in the stochastic regime is at most 3 log (T) with high probability (see Lemmas D.5 and D.19), where in case of failure event, we switch to the adversarial algorithm. Since the number of times it halved bounded by Olog (T)), we can also bound the number of times it is doubled before reaching the time horizon T. Formally, Lemma C.4, we bound the total number of phases by 7 log (T). Therefore the first term in Equa- tion (2) is bounded by O log? and the regret from these rounds is O (oggT). A?
For the second term of eq. (2), note that the size of M.! is most maaz but only small fraction of those rounds belongs to arm i. Since the probability pulling arm these rounds was 2-2-3 we have that n:MMfi2 O(mmazt)). Recall that p] 1 + ma(5)) pulling arm before elimination is at most 1/M,, where Ke is the number of active arms at the time of elimination, n, (T:) I nı(TT)) (T:T///TT S 1/Ks. That is, pt < (11/k.). We get that the total regret after climination from unprocessed pulls (multiplying the second term in eq. (2) by A and summing over is of order Σ; Zwaz A, Again, leveraging the fact that arms eliminated roughly in decreasing Ki order of their sub-optimality gaps, we can bound the last sum by Tmax Aavg log (K).
0manp]2 Summing over this geometric series gives
us Elog(T (T) (=(
27 Since the probability of
Remark 2 As mentioned in the proof sketch, our algorithm adds additional width the elimina- tion inequality, which makes the eliminated arms to be in descending order of their sub-optimality gap. We stress that this is a general trick that be applied in any SE-based algorithm. Specifi- cally, for every SE-based algorithm for feedback term be dependent on Davg instead of Amaz-
feedback (e.g (20, 251), this will make their additive
5 Adversarial Analysis
Theorem 5.1 Assume that ALG has a regret guarantee of RALG in terms Tf K, D and possibly dmaz and a Tmna- Then, the regret in the adversarial setting is bounded by:
Rado S o <0VKKTlon (T) + log (K)omax + RALG
The log (K) factor can be removed with slight algorithm modification. We deferred the details to Appendix F to reduce the complexity of the already intricate main algorithm.
Proof sketch: Fix action i E [K]. Let T be the time the algorithm switches to ALG. Clearly, the regret after the switch is bounded by RALG, we focus the regret up to time T. First,
8

---

decompose it to the following three terms:
T
E
Lo (t) ucb (5)]
lucb' [4)+
lucb" (ac)(()) (S)- [())
(4)
where S is the value of S when the algorithm switches to ALG and т; is the elimination time of arm i. Term (3) is bounded by O( //TTJ log (T) log (K))) due to the second check of BSC. To bound term (4), note that L, is an unbiased estimator of L,. By Wald's equation, EE [(.))
E (S.) E [ [..)]. where S, the of rounds in which arm i was observed before elimination. Now, since we have not switched to ALG yet, by the first check of BSC we know that for every realization S of 5;
(5( lcb.(5) (S) 2 ucb;(S) - 3width(S) 2 ucb' (S) 3wwdth(S),
where the second inequality we used the fact that ucb;(S) Icb;(S) - 2wi for any S and the last inequality is by definition of ucb". Multiplying both sides above by |S|| gives us
E
4(1)
> E |S./ucbb
-3)333/21331 log (T)
> E |S: (S) - 3 22/2/KIN log (T) log
-00)-32200
S
Rearranging the terms above get that E E (ucb"(5) [[t)]] s / log (T). Hence,
(4) E
Σ [ucb" (ucb"(S) (())] LIES,
E
Σ
[ucb" ([)]]
3 2TK STKolog (T) + Omar
where we've used the fact that ueb decreases over time and ||7. 1|\3;| S 0 maaz
The core difficulty in the adversarial analysis is bounding (5) ensuring that an eliminated arm doesn't 't become much better than the active arms, before switching to ALG. Let us further decompose (5) the phases of arm
T
(T)
E
Jucb" " (S) - [(t]
E
[ucb' (S) - 4()) = E
Σ
(IS) |ucb" (5) L.(s))
r=1
EEST
The main tool to upper bound the optimality of eliminated arm is the check in Line 9 of EAP. This checks that the estimated loss (using an importance sampling estimator) isn' much higher than the loss observed when the arm was active. Using the condition in Line 9 of EAP and by bounding the difference between the loss estimator of the phase and the actual cost in terms of N and A show the following lemma (the proof is deferred to the appendix see Lemma E.2):
Lemma 5.2 For every arm i and phase have:
E |ST lucb" (3:) L
3 A.NT 9 A
where EG is the expectation conditioned on the observed history by the beginning of the rth phase of arm i.
Note that the difference between ucb" and the expected loss depends on relationship between |ST| and NY. If the phase finished successfully (IST) N(",, the expected loss exceeds ucb". If the phase was erroneous, then we may have SST NJ. and the expected loss can better than ucb". Specifically:
|S| Jubb (S) B[L((S)) < 3 ANNT
Finished phase:
Erroneous phase:
[ucb" (S5) E(L((S))
< x AA.N
3

---

The trick for bounding the sum of these bounds over the phases is that every successfully finished phase compensate for the erroneous phases after it, since the coefficient of A under finished phases is twice as the coefficient for error phases. Since the algorithm halves NI after an error, even O(log (T)) erroneous phases are eventually covered by the last successful phase. The precise argument by induction and is rather technical. For full details, see the appendix Lemma E.3.
To conclude the proof we use the following lemma (proof deferred the appendix):
Lemma 5.3 Oma I (mingerrr) {IS]+ + vDs)).
Corollary 5.4 Using ALG as the algorithm from Zimmert and Seldin [40], we have:
Radv ò (VKTTWW KT log (T) + min
{is) VDs)
SE(T]
The first term in the regret bound is nearly optimal-up to the log (T) factor, it matches the worst- case regret for MAB without delays. The second term, which accounts for the delays, is also tight in general due to the lower bound of Masoudian et al. [21]. Our bound eliminates altogether the o" term that appears in the BoBW bound of Masoudian et al. [22] for the adversarial regime (see Table 1). This is especially significant whenever dmax is very large (i.e., even if a single delay is large), in which case ox = 2D32/3 while our delay term only scales with vD in the worst case.
Discussion
We presented a novel algorithm for the delayed-BoBW problem that achieves near-optimal re- gret bound simultaneously for both stochastic and adversarial losses. Additionally, our bounds in the stochastic regime improve even compared to algorithms specifically designed for the stochastic case. As mentioned, our algorithm follows the "adaptive approach" for BoBW- begins with an al- gorithm that achieves optimal bounds in the stochastic setting. and upon identifying non-stochastic losses, it switches to an optimal algorithm for the adversarial setting. The alternative perspective Masoudian et al. [21, 22] offers simpler algorithm but results in weaker bounds. It remains an open question whether algorithms of the latter type can achieve optimality in the delayed scenario. Apart from the simplicity of these type of algorithms, we also note that they typically have any- any-time guarantee, whereas ours either requires knowing T in advance or incurs an additional logarithmic factor. Additionally, while we considered worst-case adversarial delays, future research could ex- plore delays with additional structure (such as i.i.d. or payoff-dependent delays), potentially yielding improved regret bounds.
Acknowledgments
OS, TL and YM are supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation and the Yandex Initiative for Machine Learning at Tel Aviv University and by grant from the Tel Aviv University Center for Al and Data Science (TAD).
10

---

References
[1] Auer and C.-K. Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits, 2016. URL https://arxii. http:/iwww.rgaab///eeoooe / .
[2] Bistritz, Z. Zhou, X. Chen, N. Bambos, and J. Blanchet. Online exp3 learning in adversarial bandits with delayed feedback. In Advances in Neural Information Processing Systems, pages 11349-11355 1358, 2019.
[3] Bubeck, N. neaa-Bianhhi, and S. M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference Learning Theory, pages 41-1. JMLR Workshop and Conference Proceedings, 2012.
[4] N. Cesa-Bianchi, C. Gentile, Mansour, and A. Minora. Delay and cooperation in non- stochastic bandits. In Conference on Learning Theory, pages 605-622, 2016.
[5] N. Cesa-Bianchi, C. Gentile, and Y. Mansour. Nonstochastic bandits with composite anony- mous feedback. In Conference On Learning Theory, pages 750-773, 2018.
[6] N. Cesa-Biand Bianchi, C. Gentile, and Y. Mansour. Delay and cooperation in nonstochastic bandits. The Journal of Machine Learning Research, 20(1):613-650, 2019.
[7] C. Dann, Lattimore, and Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
[8] C. Dann, C.-Y. Wei, and Zimmert. blackbox approach to best of both worlds in bandits and beyond. In G. Neu and L. Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5503- 5570. PMLR, 12-15 Jul 2023. URL https::/ppocceddiiii html.
mlr www.ppresssvv//ee dann23a.
[9] M. Dudik, D. Hsu, S. Kale, N. Karampatziakis, J. Langford, L. Reyzin, and T. Zhang. Efficient optimal learning for contextual bandits. In Proceedings of the Svenny-Seventh Conference Uncertainty in Artificial Intelligence, pages 169-178, 2011.
[10] Y. Efroni, N. Merlis, A. Saha, and S. Mannor. Confidence-budget matching for sequential budgeted learning. In M. Meila and T. Zhang, editors, Proceedings of the 38th Interna- tional Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2937-2947, PMLR, 18-24 Jul 2021. URL https://proceedings mml. mtsss/v139/efron2221 html.
[11] E. Even--eDaa S. Mannor, Y. Mansour, and S. Mahadevan. Action elimination and stopping con- ditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
[12] M. A. Gael, C. Vernade, A. Carpentier, and M. Valko. Stochastic bandits with arm-dependent delays. In International Conference on Machine Learning, pages 3348-3356. PMLR, 2020.
[13] A. Gyorgy and P. Joulani. Adapting to delays and data adversarial multi-armed bandits. In International Conference Machine Learning, pages 3988-3997. PMLR, 2021.
[14] A. Gyorgy and P. Joulani. Adapting delays and data in adversarial multi-armed bandits. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Ma- chine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3988-3997. PMLR, 18-24 Jul 2021. URL / //pppo/eeiing...c///e//e mlr. h.t..prees/v1//// wtees//v33/yyorry2l... gyorgy21a.
html.
[15] B. Howson, C. Pike-Burke, and S. Filippi. Delayed feedback in generalised linear bandits revisited. arXiv preprint arXiv:2207. 10786, 2022.
[16] S. Ito, D. Hatano, H. Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K.-I. Kawarabayashi. Delay and cooperation nonstochastic linear bandits. Advances Neural Information Processing Systems, 33:4872-4883, 2020.

---

[17] S. Ito, T. Tsuchiya, and J. Honda. Adaptive learning rate for Competitive analysis and pest-of-bothh world. In S. Agrawal and A. Roth, editors, Pro- ceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 2522-2563. PMIR, 30 Jun-03 Jul 2024. URL https: mmrl //proceedings. mlr. press/v247/ ito24a.. html.
rehhlereguarizd--eeee leader::
[18] Joulani, A. Gyorgy, and C. Szepesvári. Online learning under delayed feedback. In Interna- tional Conference Machine Learning, pages 1453-1455 1461, 2013.
[19] T. Lancewicki, S. Segal, T. Koren, and Y. Mansour. Stochastic multi-armed bandits with unre- stricted delay distributions. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, pages 3969-5978 PMLR, 2021.
[20] T. Lancewicki, A. Rosenberg, and Y. Mansour. Learning adversarial markov decision processes with delayed feedback. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 7281-7289, 2022.
[21] S. Masoudian, J. Zimmert, and Y. Seldin. A bestoof-both-worlds algorithm for bandits with delayed feedback. arXiv preprint arXiv:2206. 14906, 2022.
[22] Masoudian, J. Zimmert, and Seldin. A best-of-both-worldd algorithm for bandits with delayed feedback with robustness to excessive delays. Advances in Neural Information Pro- cessing Systems, 37:141071-141 102, 2024.
[23] C. Pike-Burke, S. Agrawal, C. Szepesvari, and S. Grunewalder. Bandits with delayed, aggre- gated anonymous feedback. In International Conference on Machine Learning, pages 4105- 4113. PMLR, 2018
[24] K. Quanrud and D. Khashabi. Online learning with adversarial delays. Advances in neural information processing systems, 18:1270-1278, 2015.
[25] O. Schlisselberg. I. Cohen, T. Lancewicki, and Y. Mansour. Delay payoff in mab. Proceed- ings of the AAAI Conference on Artificial Intelligence, 39(19)20310-00317, Apr. 2025. doi: 10. 10.1609/aaii.vo http://aaiiiv999...33.. v39119.34237. URL https://ojs. aaai wtgg/idee....orroooooooo http://neex.ppp///aaaeaa php/AAAT/arttclll././ view/34237.
[26] Y. Seldin and G. Lugosi. An improved parametrization and analysis of the EXP3++ algo- rithm for stochastic and adversarial bandits. In S. Kale and O. Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1743-1759. PMLR, 07-10 Jul 2017. URL https: http///oeedng...... mml... mlr. press/v65/seldnn/e html.
[27] Y. Seldin and A. Slivkins. One practical algorithm for both stochastic and adversarial bandits. In E. P. Xing and T. Jebara, editors, Proceedings of the 31st International Conference on Ma- chine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1287-1295, Bejing, China, 22-24 Jun 2014. PMLR. URL attps://pptt sttpss//pprcceedings www.eeeddiinn............m.em..e www..m.s./....1. seldinb14. html.
[28] A. Slivkins. Introduction to multi-armed bandits, 2024. URL httttp:://axxvvor//// abs/ 1904.07272.
[29] Y. Tang, Y. Wang, and Z. Zheng, Stochastic multi-armed bandits with strongly reward- dependent delays. International Conference on Artificial Intelligence and Statistics, pages PMLR, 2024.
[30] T. S. Thune, N. Cesa-Bianchi, and Y. Seldin. Nonstochastic multiarmed bandits with unre- stricted delays. In Advances in Neural Information Processing Systems, pages 6541-6550, 2019.
[31] A. Tropp. Freedman's 's inequality for matrix martingales, 2011. URL URL httttttst///axi org/ abs/1101 1039.
12

---

[32] D. Van Der Hoeven and N. Cesa-Bianchi. Nonstochastic bandits and experts with amm- dependent delays. In International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
[33] D. van der Hoeven, L. Zierahn, T. Lancewicki, A. Rosenberg, and N. Cesa-Bianchi. A unified analysis of nonstochastic delayed feedback for combinatorial semi-bandits. linear bandits, and mdps. In The Thirty Sixth Annual Conference Learning Theory, pages 1285-1321, PMLR, 2023.
[34] C. Vernade, O. Cappé, and V. Perchet. Stochastic bandit models for delayed conversions. In Conference Uncertainty Artificial Intelligence, 2017.
[35] C. Vernade, Carpentier, T. Lattimore, G. Zappella, B. Ermis, and M. Brueckner. Linear bandits with stochastic delayed feedback. In International Conference on Machine Learning, pages 9712-97199 1121.. PMLR, 2020.
[36] H. Wu and S. Wager. Thompson sampling with unrestricted delays. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 937-955, 2022.
[37] M. Zhang, Y. Wang, and H. Luo. Contextual linear bandits with delay as payoff. arXiv preprint 12x2:2502.12558,, 2025.
[38] Z. Zhou, R. Xu, and J. Blanchet. Learning in generalized linear contextual bandits with stochastic delays. In Advances in Neural Information Processing Systems, pages 5197-5208, 2019.
[39] J. Zimmert and Y. Seldin. An optimal algorithm for stochastic and adversarial bandits. In K. Chaudhuri and M. Sugiyama, editors, Proceedings of the Twenty-Second International Con- ference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learn- ing Research, pages 467-475. PMLR, 16-18 Apr 2019. URL htttpss:/ppooceeiiiiii .mr. press/v888 zimmertiiiieemeeemmmmm.emme..eee 19a. html.
[40] J. Zimmert and Y. Seldin. An optimal algorithm for adversarial bandits with arbitrary de- lays. In S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third Interna- tional Conference
Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3285-3294. PMLR, 26-28 Aug 2020. URL https: //proceedings. mlr, gress/v108) zimmert 20a, html.
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract reflect the paper's content and the paper contains proof' for the claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitations and our assumptions throughout the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create 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-specificattin, asymptotic approximations only holding locally). The au- thors should reflect 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, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because 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 ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [es]]
14

---

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

---

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

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard emror of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: btttps::/neuuu
Answer:
[Yes]
Justification:
We followed NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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:
We did not find any direct societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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 spe- cific groups), privacy considerations, and security considerations.
17

---

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

---

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

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
that the method development in this research does involve LLMs as any important, original, or non-standard components.
The answer NA
Please refer to our LLM policy ftttp::/neuurpss / for what should or should be described.
20

---

A
Notations
For series S, we denote S. to be the first k elements of it. Additionally, S; is the series without the last element.
Additionally, for every variable defined inside the algorithm, in the analysis will add (t) to indicate that we refer to the value of this variable at the end of time For example, re(() is the value of r, the end of time t.
at
chosen arm at step loss of arm i step delay at step f (stochastic) mean loss of switch to algorithm ALG point number pulls of arm in S number of pulls of arm until time sample estimator for the loss of arm in step total loss of arm in set
(t)
de
Pa
T
(i(S)
8 S ag =
(((()
8 11
((t))
4(1) 10i=
Pil3)
L,(S)
Exes 4((8)
T,(S)
sample estimator for the loss of arm w.r.t the steps in S average loss of arm w.r.t the steps in S sample estimator average loss of arm w.r.t the steps in S
pES [((s)
is(S)
B.S Σ EeES
4(())
(.)S)
Li(S)
S
(S)
average confidence width arm i w.rt steps S
log (2)
Th: (S)
(i
estimator confidence width w.r. the steps in S
min
1. 2K
[3]
(S)
average lower confidence bound of arm w.r.t set S average upper confidence bound of arm w.nt set S estimator lower confidence bound of arm w.r.t set S estimator upper confidence bound of arm w.n. set 5
max [ā, width, lcb
ucb,(S (S)
min { (R4 + width, (S), ucb, (S.1))
(S)
max (T,( - width (S), lcb, (S. min {m:(S) width (S), (S...)
ueb, (S)
ucb" (S)
min; {uc us), (S))
mar (t1, (1)
maximum pull probability of arm i in the interval minimum pull probability of arm in the interval
max,, (t)
pain (41, 12)
min, <tetz (t(()
D mar
maz (0,
prein(() (1)
prasn (0.
B())
Set of the steps whose feedhack was observed Set of observed inactive steps that were pulled with prob. p Set of inactive steps to time that were pulled with prob.
{8: + dg <
(t)
{ B(t) :p(ss) pp())=
(f)
{T. S St: $t:::((ss =p
21

---

B Algorithm
Algorithm Delayed SAPO Algorithm
Require: Number of arms K, number of rounds 2 K, Algorithm ALG.
I: Initialize active arms A {1. ................................ K}
2: for t= 1, ...,, do
3:
for E do
4:
= + (8)
5: not BSC(S) (Procedure 7) then
6:
Switch to ALG.
7:
((() = EiE A: (S( 9width; ucb' (S)}
Elimination
8:
A=A\U for i do
9:
> Initialization for eliminated arms
10:
Set Ti = p, 2K + 1.(S)
S = =5=S. j4 = (s,()). A, = Swidth, N3 =
2T
1280 (p: (7), E, = =,, O. 0 = 0 vjj E [log (2))
for
T [[K] A) do
12:
(t( err = (1) (Procedure 6)
if then
14:
Switch to ALG.
15:
Vi E
(t( = (1 Σ (()) P,(()) /IA(O))
16:
Observe feedback and update variables
Procedure 6 Eliminated Arms Processing (EAP) Subroutine
Require: Arm i
1: p == D
2: while BP C * do
3: for E B C do
4:
S = S + (s), CC
5:
if 1 b - (()))
> 1 then
-phase error (),
6:
E, E, 1,
max {N] 1 }. p git min (p: }
S. S
= +1
7:
E, 2 3log (T) then return 0, True break
Switch to adversarial algorithm
8:
9:
S
[ then
D phuse ended
10:
N 7 = 2N p 1etl 1ppp" S -0. -
11:
break
12:
= P
return " False
Procedure 7 Basic Stochastic Checks (BSC) Subroutine
Require: Series of processed pulls S
1: if 3i A: (S) ([cb;(S) width S) (S) + wi)th(S)) then
2: L return False
3: if Eves (la,,(')) ucb" ucb" (S)) 2 KTlog (T) + 100 (t) log (K) then
4: return False
return True
C General Lemmas
Lemma C.1 (Freedman's Inequality, Theorem 1.1 in Tropp [31]) Let {Xelaz1 be real valued
martingale difference sequence adapted to a filtraiion (Fihro- If Xx. S R a.s. Then, for all t
22

---

and 8² 2 0,
k
t²
Pr 3k 2 0: Σ
2 2
and
E. F & o²
s exp
20 + 2R1/3
1=1
Lemma C.2 (Lemma F.4 in Dann et al. [7]) Let {Xt)e= be sequence of Bernoulli random and a filtration F1 S F2 S Fr. with P(X, = 1| Fi) = Pt Pt is F--measurable and Xt Fit1" measurable. Then, for all t E [T] simultaneously, with probability 1- 8.
Σ Xx Xx
1 3
Px log
R=1
Lemma C.3 (Consequence of Freedman's Inequality, e.gr, Lemma 27 in Efroni et al. [10] Let [Xi)ez be a sequence of random variables, supported in [0, R.. and adapted to a filtration Fi F2 S Fr. For any T, with probability 8.
4R :
Xx
Σ
B[x, IF]
t=1
Lemma C.4 For every amm i, (T(T) 7 (T)
Proof: Every phase must finish with Line or Line 11. Let 71 the number of phases finished
with Line 6. We have:
N [ (T) 2 N/22"117loR(T) (T)
N7 2og (T)
From Line 7, S 3log (T). Thus:
N Ilog (T)
2 N!T2T
If the log (T)'s round is reached and finished, then the horizon has arrived. Else, the algorithm will switch.
Lemma C.5 Let some arm, and S series of steps. Denote Pmain = min (s()). Then, if
log (?) w.p 1 - 8:
|S|
Pmin
S log (1)
max Ls. Ls.. 2
Pmin
S log (t) Priin
max Ls. LS.. S $21
b
Proof:
(Z(1))² 21)) Pt(t) (((t) (t)²
1 Pt(t)
E
Thus, for every l the variance is bounded by:
S Pmin
S
(Ls.. Ls..)
Pinin
Using Lemma C. with x² |S| and Pmin
Pmnnn
1)
|S] log (+)
S log (2)
4
log
Pr max Ls,, - Lsa 2 22
Pmin
pmin
2 9
+
[S] log (2) Pmii
3
23

---

log (t)
Since |S|
Prrén
|9| log (+)
S log (t)
1 8
log
Pr
max Ls., - -Ls 21
Pmnin
- log
Pmin
2 |8
[8
Prnen
Which means that w.p 8:
S log (t)
max Ls. Ls.. 52
Pmin
Which is exactly the first inequality in the lemma. The second has the same proof.
D Stochastic
D.1
Good Event
Definition D.1 Let Gsto be the event that:
E [K], - S
[M (.(S.n)) (S.th,
E [K],n n [5:
114 (s,(s width(S...)
Vi E [K], < / (((5)) } [
E (((()))})
Σ p((s) - 3log (T) S (n( 2 22
p((s) + 12 (7)
SES
sES
W [K]
(T) S [[F + vilog (7)
VS Σ Mo, (s) - lo (s) E
Σ Mo (s) -
(a- (-- $ <3/Tlog (T)
SES
SES
If the delays are stochastic, also:
Omaz S 2EE[d] + 8log (T))
Lemma D.2 For every state of S and arm i, w.p z.
lpa (.(S)) < (S)th:(S)
Proof: Directly from Equation 1.6 of Slivkins [28].
2. T. For every arm and n S [3.]:
Lemma D.3 With probability
(T,(S..) Mal S width(
Proof: Denote S S., for brevity.
[S] 3K log (T) then width(S) and the bound is trivial.
Notice that since n < [. for s E we have (s)) 2 3. If 2 3K log (T), w.p
7 from
Lemma C.5:
(S m4l S 22/3K/6 log (T)
3K log (T))
(a(1) - m1 s 2/V
S
Union bound on all arms and 5 | we get the desired results.
24

---

Lemma D.4 With probabillty 1- - /
ViE [], (((5)) }) v (STreen)))
2 SES
1 ΣE p(((s) 3log (T) S n((S) S Σ pi(s) 12 (T)
SES
Proof:
Notice that (S) is of bernoulli variables. Fix S and i, from Lemmas C.2 and C.3,
w.p 2
1 p(s) 3og (T) n,(t) 2 Σ pi(s) log (2)
2
Union bound for all the options for S and gives the desired results.
Lemma D.5 For every arm, w.p +:
E. (T) s B E + Volo (T)
Proof: Using Hoeffding, with probability y=::
= + V (T2)
From Lemma C.4:
E,(T) SE + 77 (T)
Union bound for all arms concludes the proof.
Lemma D.6 For every state of S, w.p 1 7:
- E Iu. -a- [o-
Σ
Ia. - (s)
S / (T)
SES
L
Proof:
From Lemma C.I, with 0² = T and R = 1:
97 log (T)
Pr
SS Ela, ((()))40 la (5)] Ela, Ua, -s) -
(s) 2 T (T)
S exp
2T + 2 T log (T)
1
$ cepp(- log (T)
T
Lemma D.7 If the delays are stochastic, with probability 1 +: 2E[[ + 8 Blog (T")
Omoz
Proof: For every t $ T:
E[o(t)] = Σ Pr(d > s]
==1
Pr[d= = s]
im s+1
<
irrld = i]
i=1
= E(d]
Fix some & < T. From Lemma C.3, w.p tt:
(t) < 2F(d] + 8 log (T)
Union bound for all concludes the proof.
Corollary D.8 Gsto happens w.p
Proof: Union bound of Lemmas D.2 to D.7
25

---

D.2 Regret Analysis
Lemma D.9 Assume Gst the optimal arm i' will not be evicted.
Proof: Assume by contradiction that arm i" was evicted. Namely, there is S such that: (S) j... (5) 9width, (5)
From Gsto:
ucb" (S) < A4- (S) 9width (S) < p
From the definition of ucb" and Gstnr there is arm i such that:
14 S ucb" ucb"(u)) (S) < ,
Which contradicts the fact that 1" is optimal.
Lemma D.10 Assume Gstor For every two arms i1, i2 and series n S min {|s. Bizl
width; (S..) I 10width;; (S...)
Additionally, for every arm i:
Á S A, S 2I,
Proof:
Denote S S. for brevity.
Since i was not eliminated:
Pa, (S) 9width, (S) S uob"(() S ucbb(() Lubb;, (S) S (S) + width,, (S)
From Gstoi
μ4 10width; (S) S n² 2width:,
An S 10width,, (S) 2width (S)
Notice that since 1 and i2 not evicted in the steps of S, we have E Emn, (S) E[n;, (S)). Thus: ni, (8) s 2 [n,, (S) log (T)
1
E E(m; (S)) >
2 Thi (S) 6 log (T)
ni, (S) 2 E n; (S)] log (T) 2
TE] mn (S) < 2n; (5) + 6 6log (T)
1
2 T4, (S) 6log (7) < 2m; (S) 6 log (T)
The, TT (S) 24 (T) < nig (S)
(S((S) 2 192 log (T):
4 T4 (S)
Mii (S) S nig (S)
n1, (S) S mis (S)
nia (S) 531 2 2og (S)
log (T)
n;, (S)
width;, (S) < 3width;; (S)
4, S 16width; (S)
26

---

If (S) & 192 log (T):
width;;(S) 2 2 log (T)
2 10
192 log (7)
4 Σ 1 v 10width, (S)
width;; (S) S - 10width; (5)
In both cases:
4 I 16width, (S) S 16width; (5s,) 2
Additionally, from Gstoi
Pa Swidth; (in) Mr, (5a)) 9width (5 > ucb" (3a) w
A,, Swidth (S..) A.,
Lemma D.11 Let N be over R with average μ.. Then, at most half of N are greater than 2p.
Proof: Let X be a r.v sampled from N with uniform distribution. Easy to see that [[[] .4. From
Markov inequality:
1
Pr[X 2 2n| <
2p
2
Lemma D.12 (restatement Lemma 4.2) If arm in was eliminated before i2 then,
D, S 20A;
Proof: Let i and ig be two arms such that i was evicted before iz. From Lemma D.10:
A < 16width (Stz) s 16width:2 (5,, < 160width,, (5.)) 204,,
Lemma D.13 Assume Gstor we huve:
Σ p mar (Tr) Amax log (K)
Σ P max (T)) S 424ang log (K)
Proof:
Let A' be the state A such that |A| (namely, the last half active arms). We show that:
ViE A S 404 avg
If A, < 2Davg it is trivial. Otherwise, from Lemma D.11 there is arm j & A' such that
A, I 2Azvg- From Lemma D.12, A, < 20A, S 40A
Notice that arm was the jth evicted arm, we have:
max (T:) S
27

---

Which means:
Σ pi
mas (Ti)ai = Σ
may
(Ti),
+
Σ
man (Ti)a,
iEA
YEA'
40Aavg
K
A
j=1
v 24 avg + 400 log (K)
Lemma D.14 Assume Gstor then for any arm i and step < T₁!
m,(t),, 515log (T) + 20 (t) mar (T,)
A
Proof: Let be the set of observed pulls at time From Lemma D.10:
2 log (T)
A - 16
n2(S)
(s(S) v 512 log (T')
A
At step there are ot)) missing pulls. When those missing pulls were pull, the probability arm was bounded by y; (T: 1) (as it is its general maximum probability). Thus, from Gston we have:
mt(t)= S (s(S) + (0(()) maz (T: 1) + 3 3log (T)
Thus:
(t)A, S 515log (T) (t)p; (T.)A,
Lemma D.15 Assume Geto and that K <
T
then for any arm i and step T < TT:
12 (7)
71728 log (7)
(m²(l) mT(T:)) <
+ Spmea (Ti)0 (1)A:
A:
Proof: From the algorithm defintion we have:
(t(
log (T)
mt(t) mT:):)) = Σ ns(S)) +
Σ
nx(M (t) c (t))
(6)
j=0
From Gsto. for every i and every phase ry:
1280
B(a,(S?)) = = pd N?
A
From Lemma C.4 and Gsto:
1280 A
8960 log (T)
E
n4. (ST)
< 7og (T)
A
(((()
17920 log (T')
17923 log (T')
Σ n.(ST)=
<
+ 3 log (T) <
A?
A?
28

---

Let < t be the last pull of a phase w.p which means that (s) \ Cf(ss
0, so
IM (t) (t] (s) (s) I (s) S maa (t). Then:
(M Cf) - po
log (I)
log (T)
E
(M 2- cp Σ
p oma (t) S 2p; man (t)
j=0
j=0
log (T)
mM
'1 C ') S 4p. o max (t) + 3 3og (T)
(G
Thus, from Equation (6):
17926 log (T)
m²(t) mT(TT) S
4p, omar (t)
A
From Gsto and the assumption that K v
12 12 (T)
Pi
M (Ti)
K
(T:) + T
(S,) 2 S pi pm (T:)
12log (T) s 2Tp, pmpa
3T (0 (T))
K
ni().)
P (Taa((T:)
3p
(Ti)
p| = 2K +
+
2p, (T;)
2T
2
17932 log (T)
(f(t) - (T, <
+ 8p,ar (Tu)omar(t)
A
From Lemma D.10:
71728 log (T)
mi(t) -m;(Ti) S
+ Sp, mar (Ti)o (t)
A
71728 log (T)
(m;(1)-m;(f) - -m;(T:))A;
Spm (Ti) (1)
A
Corollary D.16 Assume G for every t < T:
72243 log (T)
(l) 5
100 (1) log (K)
A;
K
72243 log (T)
A (1) 5
A; + 4200 mar an) log (K)
Proof: If < 12log (Ty+ it follows directly from Lemmas D.13 D.15. Else, we have:
K
K 12 log (T)
(t) ST < 12K log (T) S
1=1 A
D.3
With high probability the algorithm doesn't switch
Lemma D.17 Assume Gstor for every arm i and S C S.:: (T(SS) E [Icb,(S) width(S) (cb((s))) + width(S))
29

---

Proof: From Gsto:
lcb S 14 S (5((S) + width(S)
ucb;(S) 2 14 2 (.(S) (idth(()
Lemma D.18 Assume for every state of S at time t:
Σ la (6) ucb" (S)] & 272 KT (T) 300 (t) log (K)
Proof: From Corollary D.16:
72243 log (T)
Ua. (s) La- (s]]
300 mao (t)
A
T Tlog (T)
72243 log (T)
E
269
E
300 (t)
K
A
ist $2000
lug (T) RT
lox (T) ist A,200
RT
S 269
KT log (T) + 300 max (f) log (K)
From Gstor for every state S:
1la,,s - uscb ucb" <
No, (s) - La (s) < 272 KTlog (T) + 300 (t) log (K)
SES
SES
Lemma D.19 Assume Geto for every arm i, ET) log (T).
Proof:
Fix phase r. We will show that w.p 32
1 ANT -
| S AA,N7 this is trivial. Otherwise, means that:
|ST| > A,NT
N!
A
P.
1 A
1280
320
P A
40
(Å, 5
P
Now can Lemma C.5, w.p the inequality |S||
31
log (32)
is satisfied. We have:
P5
5NT PT
- S V
5N. A
21
1280
N/ A
(7)
30

---

Additionally, from Gsto:
A. - S width; 5:)
(Gsto)
8
| | - A |
S AN
8
| I AN
(Equation (7))
All of the above is true to all states throughout the phase (since Lemma C.5 is true for max;).
This means that in every phase Line happens w.p 32 Thus:
E ([E,(T) = (T)
32
7log (7)
(Lemma C.4)
32
From Gsto:
ET(T) S (T)) + 1 (1) - 3 (T)
Corollary D.20 Assume Goto, T = T.
Proof: Directly from Lemmas D.17 to D.19
D.4 Conclusion
Theorem D.21 For adversarial delays:
log (T)
Rsto S
0
omar Aang log (K)
A
For stochastic delays we can also say:
K
log (T)
Reto 50
Eld Aayg log (K)
A
Proof: Assume Gstor from Corollaries D.16 and D.20, The above is true with probability 1 7.
From Corollary D.8, this is asymptotically even without the assumption of Gsto-
E Adversarial
Lemma E.1 Let be a random variable such that for every x 2 there is some a > 0 such that:
(x 2 1
c =//a 2/a
Then:
X < a
Proof: We use the CDF representation of the expectation:
(1 F(x))dz [" F(x)dr
E =
(1 F(x))dxx
s/adx
<
2/a
0C
10
31

---

Lemma E.2 (restatement of Lemma 5.2) Let Hi be the history (i.e., chosen actions) of rounds that are observed by the begining of the r phase of amm Denote ET E1- H.] and [r Pr|: H.]. For every arm i and phase r we have:
E 1s ucb" (5.)
(a(S))
1 N
(AESS 8
8
Proof: Let S be the sequence of No¹ observed rounds starting from the beginning of r phase of arm so that the first |S|] rounds in S are exactly S Let also XI..., lidd Bernoull((p)). From we have for every m > conditioned on the history H4, with probability
Lemma C.5, if N m P
of at least m
Σ LES
X14 P5
1(())
22
mN
m.V
2
N!
A
m
21
1280
m.NT Å
/320
Now, note that for = 1 Eies, X.4+ conditioned on the history H4, with probability of least em::
(()] distributes exactly like L((S)) - L.(S)). Thus,
Pf
mNT A
L,(S)) L((5)) |ST|
V320
If NT S m
T.(S)) T.((S) S NT
S P
MNT
PI N!N!
mNT A
1280
m.N Å
(Å, s 8)
160
MNT Å
V V320
From Lemma E.1:
N A
- <
< N.
V320
Notice that if the phase not finished it means that S L < ANT. Given that we have:
32

---

B | "S/lucb" (1:)
+ 9 | 8
B [|sT]| ucb" (3.) + 9width, (5:) - L.)
B [[S] i [S))
(Elimination inequality)
- A
Combining the above with Equation (8) completes the proof.
Lemma E.3 For every arm and phase T,
Ti(
uch" (5.) - In(SX)) |
E
Σ
S
3(r((T) -r 2) N + 4
AA..
3
8
Proof:
We will prove using reverse induction on r.
For r = rT) (namely, after all phases) we have:
(2))
E
Σ
S ucb" - (5.) - -L," =0
('=)(T))
3(0-2) A + 7 A
3(0 (00-2 2)
A + A =0
8
8
Assume true for r + 1, we prove for r.
If Line 11 was triggered it means that |S = No and No+1
2NT. We have:
Eg S ucb" (S:) E
x
3
N
A
(Lemma E.2)
8
8
(
(T(
St ucb" (s.) L.(s'')
Sy ucb" - L((5)') (5.)-1((ST)) ||
+ 188 [|ST (3.)-14) Li
B
r=++1
((r((T) - -r-3) Á + AA
-4 _..NT
8
((m,(T) - - 2) Á.N! Â.N. - - -A.N
8
((r((T) - -r Á + ANN.
8
If Line 6 was triggered and No- A N2 it means that N NY. We have:
E S
ucb* * (S:) E
< A
3
(Lemma E.2)
8
(T(
B
S ueb" (s:) - Ls(''')
EE
Σ
Sy ucb' (3.) - L((ST')
+ 1 |ST//ubb Jubb (3.) -
-=++1
3(r((T)) - -r A N + AA,N++1 +
3 -AANTT
8
3(r((T) -T - 2) N Â.Ny + -.A.N
3
8
3(ri(T) -r 2) N + ANNY
8
33

---

If N = N it means that Ni+!! = NY. We have:
E S ueb - (8:) L
= 8
3
N,
(Lemma E.2)
(T(
S ucb" (s:) - (s( |]
S ucb" (5)) - Lx(st') b]
+ +Rg [1st Jubb (3: Lij
E
E
M=++1
3(r:(T) - -r-3) Á, + 3 ANNT+
+ 8
8
3(r((T) -T- 2) Á + 2 A.N
8
Lemma E.4 For every arm i:
E
Σ
Jucb" (5) (5) [(t)]
$ 594v KT log (T)
Proof: Lemma E.3 with r = 1 gives:
Σ
ST
ucb" % (5.) - 1((8)) ||
1 3(r,(T) 3) A,N? + 3 AAN: S 3r,(1)
A
8
8
From Lemma C.4:
(T)
S ucb" (5.) L((55')
21 log (T) A,N
E
(9)
8
If n.
(3t)
R
n7 S$
2 log (T)
1 A >
8
2T
The S.
ny (Se
32l (T)
T
T
332 log (T)
KT
If a. (S.)
< k
2 log (T)
1 A >
2K
8
32 log (T")
K
Knn 8:
32 log (T) KT
In any case:
log (T)
p 3 2
(10)
KT
34

---

Since for every i, Sg is sub-series of S, we have ucb" (3:) 2 ucb" ucb" From Equations (9)
and (10):
E
ucb' (S) - 4(t)]
S E
ucb (s.) ((tt)
21 log (T) N
3360 log (T)
p. A
594 KT log (T)
Theorem E.5
Rado S 0 KT (T) + log (K) 1K)maa + RALc
Proof: From Line 3:
la, (8) -ucbbu)) - 272 log (T) + 100 log (K)
s68
T
Σ
(t)] Tucb" (5) 272 KT log (T) + 110maz log (K)
(11)
1=1
From Wald's equation and Line 1, for every arm i:
E
Σ
400)
E
S. P [.)]
E
S
Icb (5.)
width [5:]
E
5.
ucb, (s.) 3width [s.)]
$ ucb* (3.) (3.)-3 -3 2K log (T)
2 E
S
2 E 5. ucb" (S) 3 32 log (T)
Adding the missing pulls we get:
TC-1
E S ucb' (cb"(s)
(5)
Σ L(t)
<3 <3/2KTlog (T) + t 1)
(12)
From Equations (11) and (12) and lemma E.4, for every arm d:
E
La, (t) 4(1)
Na. (t) Tueb" (5)
7--
+
(nr - 1)ucb" (8)
Σ 1=1
4(1)
+
[ueb* x (5) - [,(1]] (5)-1;(1]
< 869 / KT log (T) + 120 max log (K)
35

---

Since after T the algorithm switches to ALG, we have:
Σ
(1.(1)
1:(1))
S RALO
t=
Which concludes the proof.
Lemma E.6 (Restatement of Lemma 5.3)
Omax
S 0
min SE(T]
{ist + v VDs)
Proof: Let S be the set that minimizes
|S| DDz. If |8 m it concludes the proof.
Continuing with the case that |S 2 70 maaz
Let be the step such that (t) = Oman- Since |S*| < T0azz after skipping there are at least 3 non-skipped missing steps at time L. Let $1:-..: S be the series of those {() missing steps, ordered in descending order of when they were pulled. Namely, is the most recent pull the series and $ (1) is the oldest pull.
Since there are at least 1-1 1 missing pulls that were pulled after 8;, we have t 8; 2 Additionally,
since s; is missing, we have s; + des > t. Combining both we have da, > Thus:
{(((()
ft((t)
(20(1)) (1)
Dg.
da.
Σ
Removing the log (K) factor
We show that a simple modification of the algorithm can eliminate the log (K) factor from the additive delay in both the adversarial and stochastic settings (Theorems D.21 and E.5). To avoid adding complexity to the already intricate algorithm, we present this modification separately optional, opt-in feature.
Algorithm 8 Delayed SAPO Algorithm with reduced log (K)
Require: Number of arms K, number of rounds T 2 K, Algorithm ALG. 1: Initialize active arms AA = (I. K}, S = () 1, G 0
2: for 1, ..., T do
3: for E B S do
4:
S (s)
5: not BSC(S) (Procedure 7) then
6:
Switch to ALG.
7:
U(I) (iE A: (S( 9width; > ucb" ucb'(S))
GGhsttng
8:
G-GUU
9:
for U do
Initialization for phases variables
Setpl 2k
n.(S)
2T 55 S. - Å. Swidth; N == 1280 (p) A?),
=
E, =, r; 11 = (). ().C 0.. = 01 Vj E [log (T))
11:
min, (i)th,()) 2 (
then
Elimination point
12:
for G do
13:
- S = S 5, A= G.G 0. h +
14:
15:
for
([K] AA do
16:
pi(t), = EAP(i) (Procedure 6)
17:
err then
18:
Switch ALG.
vie A pt(t) E)-E)E(KK)())
(1-Eaa- (t)))) /IA(t)
20:
Observe feedback and update variables
36

---

Procedure 9 Basic Stochastic Checks (BSC) Subroutine with reduced log (K)
Require: Series of processed pulls 5
1: if Di EA: (T, [lcb:(S) width(S), (S) width(S)) then
2: return False
3: if Ex's (la,, (s') ucb"(s)) > C KT log (T) + Imaz(t) (t)) then
4: return False
return True
The key change involves introducing elimination points, where lith elimination point is when confidence width of at least one arm falls below 2-* When arm is eliminated under the current algorithm, it enters ghost period-a phase during which it remains practically active (receiving the same pull probability as active arms) and is then formally eliminated at the next climination point. Additionally, we modify the threshold in BSC's Line 3 by removing the log (K) term from its additive component.
We first show that the leading term in the stochastic regret remains asymptotically unchanged, since the number of pulls during the ghost period is asymptotically smaller than the number of pulls during the active period (Lemma F.1). We then prove variant of Lemma D.13 without the log (K) factor (Lemma F.3), which the original source of this term the regret bound. With these changes, the updated version of BSC's Line 3 (with an appropriate choice of the constant () still doesn't 't triggers a switch in the stochastic settings.
The log (K) factor is also removed from the adversarial regret, without affecting the asymptotic behavior. The main contribution to adversarial regret comes from the check in BSC's s Line 3, where we removed the log (K) term. We also need to verify that the relation between the losses and uch" given in Equation (12) still holds. This is indeed the case, since the check in BSC's Line continues be valid during the ghost period (as E still holds).
Lemma F.1 Assume Sto have:
n( n(S))= = (n:
Proof: Assume i is eliminated in the hth elimination point and denote S₁, to be S at that time. Let in be the arm whose width crossed 2-h in the hth elimination point. From the definition of width, we still have that its width is greater then 2 Thus:
width; 2 width, (Sh) 2 2 2-1
width,(SA-) < 10width;, (Sh-1) 10-20-111 2-+11 -0 2-h
(Lemma D.10)
log (T)
2 log (T)
40
2 V (S
(Sx)
16.0n,(5.) Z 1600m, 1600m,(Sn-1) 2 (S,) 2 n2(S,)
Lemma F22 Assume Gstor. every [d] that is eliminated at the hth elimination point have:
8 2 < A. < 320-2
Proof: Let Sy. be S the time of hth elimination point. From Lemma D.10:
width;(S,) 2-h
width;(S,-1) < 1 --h+1 h++1 20 --h
Since |Sh-1/ < S, < SSal:
2 2-h << width; (5. < 20 2-
37

---

Again from Lemma D.10:
8 8.2 2 A, S 320 2-
Lemma F.3 Assume Geto- we have:
Σ Ps A O(Aavg)
maz
Proof: In the same way as Lemma D.13, we denote A' to be the state of A such that |A| the same way we have that vi E A'' A, S 40Aavg and:
K 2 In
A Dorg
Σ P maz
I
Σ
P
maz A
2
SEA
Fix climination point h, denote In to be the set of arms eliminated at that point. By definition, we have for every In that puar
From Lemma F.2:
TTl
Σ KEI
maz A
S
1
320 2-
-220
[m
EE
Let hy be the first elimination point in which arms from A' are eliminated. Again from Lemma F.2, we have for some E A':
8.2 #1 < A S 40
2 h1 < 5 5aagg avg
This concludes to:
Σ iEAL
P4
maz A,
Σ
Σ
P4 A < Σ
320 2 640 2 hi < <3200Anr ang
h=hi iEda
b=b
38


Reviews:
[{"review_id": "Em4JrnXwJN", "reviewer": "Reviewer_9pBg", "summary": "This paper presents a new algorithm for the multi-armed bandit problem with adversarially chosen delays. The authors achieve optimal performance in both stochastic and adversarial settings and advance the Best-of-Both-Worlds (BoBW) framework. The proposed algorithm adapts between regimes by starting with a stochastic strategy and switching to an adversarial one when non-stochastic behavior is detected. The regret bounds matches the known lower bounds up to log factors. They improve on prior BoBW approaches and and outperform existing stochastic-specific algorithms by reducing delay-related regret terms.", "questions": "1) I do not get Line 253 and Appendix F. Either integrate the \"slight modification\" from Appendix F into the main algorithm and results to present the stronger bounds without the $\\log(K)$ factor, or provide a clearer justification in the main body why it is given only in the appendix.\n\n2) What is ALG? The core algorithm, Delayed SAPO (Algorithm 2 and 5), integrates an \"external algorithm for adversarial settings, ALG\". While Zimmert and Seldin is mentioned as an example (Line 289, Corollary 5.4), the paper does not explicitly detail the properties or assumptions required for ALG (e.g., its specific regret bounds, whether it must handle unknown delays, its computational overhead, or specific feedback requirements) for the overall theoretical guarantees (Theorem 5.1) to hold. Explicitly state the necessary properties or assumptions required of the external ALG algorithm (e.g., its regret performance in delayed feedback) in the main paper to make the algorithm's dependencies clear.\n\n3) I think you can elevate the \"Remark\" about the \"general trick\" for $\\Delta_{avg}$ dependence (instead of $\\Delta_{max}$) in Lines 246-250 from the proof sketch to a more prominent section to emphasize it since it seems as a broader methodological contribution.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strengths\n\n1) The regret bounds are tight in both the stochastic and adversarial settings with adversarial delays, matching known lower bounds up to logarithmic factors.\n\n2) It improves upon prior best-of-both-worlds (BoBW) and stochastic-specific algorithms by tightening the delay-dependent term in the stochastic regime, achieving a regret bound with improved dependence.\n\n3) The algorithm dynamically switches between stochastic and adversarial strategies based on observed feedback, and performs across a wide range of environments without prior knowledge of the regime.\n\n4) The design introduces refined elimination criteria and a novel subroutine for managing eliminated arms (EAP).\n\n5) The theoretical analysis is comprehensive.\n\n# Weaknesses\n\n1) No empirical evaluation. The absence of experiments makes it difficult to assess and validate the algorithm’s practical performance, robustness, and computational efficiency.\n\n2) The introduced techniques increase implementation complexity and may pose challenges in practice despite their theoretical justification.\n\n3) The paper focuses on theory with minimal consideeration to practical deployment (such as runtime cost, ease of use, or hyperparameter tuning).\n\n4) The work assumes fully adversarial delays and does not explore common settings like i.i.d. or bounded delays, which might lead to stronger results.", "was_revised": true, "final_justification": "I am keeping my score, which remains positive.\n\nAuthors clarified the placement of the stronger bound in Appendix for simplicity and will revise for clarity. Authors confirmed ALG is an external adversarial algorithm, and its properties do not impose specific restrictions beyond its own guarantees, allowing any equivalent ALG. Authors will highlight the \"General trick\" technique more prominently.\n\nLack of empirical evaluation, implementation complexity, and practical deployment remains an absence, but it's an accepted limitation for a primarily theoretical paper focused on fundamental regret bounds and optimality. This practical exploration is deemed future work. Exploration of non-adversarial delay models is acknowledged as interesting for future research, but outside the scope of this theoretical work. \n\nThe core theoretical contribution of matching lower bounds is extremely strong and heavily weighted. While practical considerations are important, their absence is appropriate for the paper's theoretical scope.", "rebuttal": "**We thank the reviewer for their thoughtful and constructive feedback. Below we address the reviewer’s specific concerns and questions.**\n\n**On the lack of empirical evaluation and practical considerations:**\n\nThis paper is intentionally theoretical in nature, with a focus on advancing the fundamental understanding of the optimal regret for best-of-both-worlds learning under adversarial delays. While implementation complexity and practical deployment are important directions, our goal here is to resolve core open questions regarding regret bounds and optimality. We believe that understanding the theoretical regret bounds is an important step toward guiding future algorithmic and empirical work.\n\n**On non-adversarial delay models (e.g.,stochastic delays):**\n\nWe agree that other structured delay models, such as i.i.d. or bounded delays, are of interest. In fact, we explicitly mention this (i.i.d. or payoff-dependent delays) as a direction for future work in the paper.\n\n**On the “slight modification” in Appendix F:**\n\nWe placed the stronger bound in Appendix F to reduce the complexity of the already intricate main algorithm. This rationale is explained at the first point of reference (Line 186), but we acknowledge that it is not reiterated at the second mention (Line 253), which may have caused confusion. We will revise the manuscript to ensure that the motivation is clearly communicated at both points of reference.\n\n**On the role of ALG in the algorithm:**\n\nThe core algorithm is defined in terms of an external adversarial algorithm, ALG, and we do not impose any restrictions on ALG in the algorithm itself. In Theorem 5.1, we assume only that ALG achieves some regret bound R_{ALG}​ in terms of T, K, D and possibly d_max and sigma_max, when handling unknown delays.  We later instantiate ALG with a specific algorithm in Corollary 5.4 to derive an explicit regret bound. We view our ability to incorporate any ALG as a benefit of our approach.\n\nWe will revise the presentation to make these assumptions and their roles in the analysis more explicit and easier to follow.\n\n**On the “general trick” for handling delay dependence (Lines 246–250):**\n\nWe appreciate the suggestion to highlight this technique more prominently. It already appears as a standalone “Remark” block in the proof sketch to emphasize its generality, but we agree it is a broadly useful idea and will revise the presentation to make this clearer and more visible."}, {"review_id": "auOBzPYfGv", "reviewer": "Reviewer_AA8g", "summary": "The paper studies BoBW (stochastic + adversarial) algorithms for bandits with delayed feedback. The authors propose an algorithm that achieves $O(\\sqrt{KT}+\\sqrt{D})$ regret in the adversarial case (up to log-factors) and $\\sum_{i\\neq i^\\star}log(T)/\\Delta_i+\\Delta_i/K\\sigma_{max}$ for the stochastic case. These rates match the lower bounds for the two settings. The algorithm is active in the sense that it assumes that the algorithm is stochastic while checking if the hypothesis is true; if false, then the algorithm switches to an adversarial algorithm (similarly to the SAPO and SAO algorithms for (non-delayed) MABs).\nAs a stochastic algorithm, the authors employ a successive-elimination-like algorithm, but instead of eliminating arms, the probability is decreased (in some very specific way) to allow checking whether those arms become adversarial.", "questions": "1. Footnote 1: There is a capital letter missing\n2. The main contribution of the paper is to drop the term $\\Phi^*$ from the upper bounds compared to Masoudian et al. [2024]. Where does this term come from in their analysis?\n3. What is the intuition behind the update of the probabilities (Procedure 4)? Lines 173-179 seem to discuss this, but I think the discussion could be improved.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I think this is a good paper that has non-trivial results and interesting techniques, improving on the result of Masoudian et al. [2024]. While the improvement is very technical, I think the techniques used here could be employed for similar problems.\nThe resulting algorithm/analysis is very technical, while prior works have simpler algorithms and analyses. It would be interesting to see if the optimal guarantees presented here are achievable by a simpler algorithm.", "was_revised": true, "final_justification": "After the rebuttals, I still find this a good theory paper that should be accepted at NeurIPS.", "rebuttal": "**We thank the reviewer for their positive and constructive feedback. We address the reviewer’s comments and questions below.**\n\n**“It would be interesting to see if the optimal guarantees presented here are achievable by a simpler algorithm.”**\n\nAchieving optimal regret in both stochastic and adversarial regimes under delayed feedback introduces significant algorithmic and regret analysis challenges. That said, as noted in the paper, we believe that obtaining similar guarantees with a simpler algorithm is an important direction for future work.\n\n**On Footnote 1 (capitalization):**\n\nThank you for pointing this out. We will fix the capitalization issue in the final version.\n\n\n**The term  $\\Phi^*$ in Masoudian et al. [2024]:**\n\nIn their work, Masoudian et al. use an explicit skipping heuristic—i.e., their algorithm actively decides to skip pulling arms in certain rounds, and the term $\\Phi^*$ appears as an upper bound on the number of such skipped pulls. In contrast, once our algorithm detects that the losses are adversarial, it switches to an adversarial algorithm that handles delayed feedback, thereby avoiding the need for explicit skipping. If needed, we would be glad to expand more during the author-reviewer discussion period.\n\n**On the intuition behind the update rule (Procedure 4):**\n\nIn brief, the idea is as follows: if an arm does not “behave stochastic”—that is, its observed losses appear slightly non-stochastic—we increase its probability to monitor it more closely. If the arm behaves stochastically throughout a phase, we can safely reduce its probability. This adaptive adjustment enables the algorithm to maintain control over regret in both stochastic and adversarial regimes.\n\nWe agree that the current discussion can be improved and convey better the intuition behind the update mechanism. While Lines 158–170 describe the update rule, the actual motivation becomes more apparent only in the analysis of the adversarial case (Lines 282–286). We will revise the earlier section to make this intuition explicit."}, {"review_id": "VKa5KgUBOZ", "reviewer": "Reviewer_pLNX", "summary": "The paper studies bandits with delayed feedback. The feedback delays are oblivious and (to my understanding) not known to the player until the feedback arrives. The goal is a \"best of both words\" guarantee with log(T) regret in the stochastic case and sqrt(T) in the worst case. The paper achieves essentially optimal bounds.", "questions": "Maybe it makes sense to mention the interpolating setting of bandits with adversarial corruptions, which could be a natural next step for this line of work.\n\nAlso can you please clarify if the delay lengths are observed in any way before the delayed feedback arrives?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper gets optimal bounds using a non-trivial algorithm. The \"adversarial\" setting with delays was solved optimally using FTRL with a carefully tailored regularizer. The algorithm used here is identical once it has been decided that the environment is non-stochastic. Thus the main challenge is to get low regret in the stochastic case until this decision has been made. The algorithm proceeds in phases where the sampling rate of an arm is halved/doubled, to gradually decrease the visibility of seemingly suboptimal arms while not discarding them entirely. \n\nI didn't read the appendix proofs in any detail but the claimed result is a significant improvement over previous (already high-quality) work and essentially optimal, and the analysis is fairly intricate, so it seems like a clear accept to me.", "was_revised": true, "final_justification": "My positive opinion of the paper did not change.", "rebuttal": "**We thank the reviewer for their thoughtful evaluation and positive feedback. We address the reviewer’s comments and questions below.**\n\n**Observability of delays:**\n\nAs the reviewer correctly inferred, the delays are not revealed to the learner until the corresponding feedback arrives. That is, the learner observes the loss of an action only when its loss  is revealed, without prior knowledge of the delay length. We will clarify this point more explicitly in the paper to avoid confusion.\n\n**Adversarial corruptions as future work:**\n\nWe agree that the setting of adversarial corruptions presents a natural and compelling extension of this line of work. It would be interesting to explore whether the techniques developed here—especially the monitoring and adaptive switching mechanisms—can be adapted to handle adversarial corruption while preserving BoBW guarantees."}, {"review_id": "r7S4lV4ox8", "reviewer": "Reviewer_ouSR", "summary": "This paper proposes a best-of-both-worlds (BOBW) policy for multi-armed bandit problems with adversarial delays. The proposed policy, which switches from a sequential elimination algorithm to an external adversarial algorithm, achieves a BOBW guarantee that significantly improves upon the results obtained by the simpler algorithm in [21].", "questions": "1. In the current choice of ucb (lcb), it is designed to be monotonically decreasing (increasing). Could the authors point out where this monotonicity property is specifically utilized in the analysis or the algorithm's design?\n2. In BSC subroutine, the confidence radius includes a $\\sqrt{KT\\log T}$ term. Could the authors elaborate on what would happen if this term were replaced by $\\sqrt{KT}$ (that possibly remove $\\log T$ term due to (3) and (4))? Which part is the essential point that introduces $\\log T$ dependency?\n3. RHS of Lemma C.3 includes the dependency on $t$. Should this expression include a summation over $t$? \n4. The leading terms in the regret bounds appear to have quite large constant factors. Do the authors believe that these constants can be further tightened through a more refined analysis in some parts of the proof? Any thoughts on where such improvements might be possible would be appreciated.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strength\n\nThe proposed policy achieves a significantly improved regret guarantee compared to previous approaches, particularly in the stochastic loss setting. Unlike the simple sequential elimination algorithm, which can perform poorly in adversarial environments, the proposed method maintains a non-zero selection probability for all arms, including those eliminated by the sequential elimination phase. By carefully designing this switching mechanism and incorporating additional procedures, the authors successfully obtain an improved BOBW regret bound. This theoretical advancement is the main contribution of the paper.\n\n### Weakness\n\n* Clarity issue due to incorrect links and notation.\n  * $\\bar{\\cdot}$ is used both to denote empirical estimates (e.g., $\\bar{\\mu}$) and complement of sets in Line 8 of Algorithm 2, which is confusing.\n  * Many internal references to algorithm steps and procedures appear to be incorrect. For example, Line 147 and Line 767. Please use precise hyperlinks or explicitly state the target (e.g., \"line 3 of Procedure 3\").\n  * In Procedure 4, the initialization of $C_i^p$ and $E_i$ is missing (I guess the empty set and 0?). Additionally, $E_i=3\\log (T)$ cannot be satisfied since $E_i$ would be natural number so that appropriate rounding using ceiling or floor functions is needed.\n  * In Theorem 4.1 and throughout the manuscript (e.g., Line 236), the notation should consistently use $\\log$ instead of $log$.\n\n* Lack of numerical evaluations.\n\nAlthough I understand that theoretical regret guarantees are typically the primary focus in BOBW research, and personally I do not consider the absence of experiments as a critical flaw, it would still be valuable to include empirical evaluations. This is especially important because several components of the proposed policy appear to be carefully designed to achieve tight theoretical bounds, which may introduce practical inefficiencies. A comparison with the simpler policy from [21], which has looser theoretical guarantees but may perform well in practice, would provide useful empirical insight.\n\n* Large coefficients in regret bounds\n\nThe regret guarantees, while theoretically sound, involve very large constant factors in the leading terms, which may limit their practical relevance. A brief discussion on whether these constants can be reduced or mitigated in practice would strengthen the paper.", "was_revised": true, "final_justification": "I understand that the main contribution of this paper lies in establishing a BOBW guarantee under adversarial delays, with a primary focus on asymptotic regret where the order is the main target. However, the given regret bound involves sufficiently large constants, which raises concerns about its practical performance in the finite-time regime, an issue I pointed out. While the authors seem unwilling to provide empirical validation, I acknowledge that the paper is positioned as a theoretical contribution. Taking this into account, I will maintain my initial score.", "rebuttal": "**We thank the reviewer for their thoughtful and detailed feedback. Below we address the reviewer’s questions and concerns.**\n\n**Notation:**\n\nWe acknowledge the clarity issues and will fix all incorrect references, inconsistent notation, and missing initializations in the final version.\n\n**Lack of numerical evaluation:**\n\nThis paper is intentionally theoretical in nature, with a focus on advancing the fundamental understanding of best-of-both-worlds learning under adversarial delays. While implementation complexity and practical deployment are important directions, our goal here is to resolve core open questions regarding regret bounds and optimality. We believe that solidifying the theoretical limits is an important step toward guiding future algorithmic and empirical work.\n\n**Large constants in regret bounds:**\n\nWe agree that the constants in our regret bounds are not optimal. Our main focus was on the asymptotic regret bounds, where we are near optimal.\n\nGiving improved leading constants may be a challenging future work.\n\n**The use of UCB/LCB monotonicity:**\n\nWe do use the monotonicity of UCB and LCB in the analysis, specifically in line 917 and in the last inequality of line 921. These steps rely on the fact that UCBs decrease over time.\n\n**The use of log(T) in BSC's second check:**\n\nThe $\\log T$ term is essential to ensure that the lower bound estimate used in the BSC check stays below the actual regret in the stochastic regime. In particular, under stochastic losses, the regret can scale as $\\sqrt{KT \\log T}$, both in our case and more generally in Successive Elimination. For instance, setting $\\Delta = \\sqrt{K \\log T / T}$ in the standard SE bound yields this scaling.\n\n**Lemma C.3:**\n\nWe thank the reviewer for noticing this issue. The right-hand side of the lemma should indeed include a summation over $t$, and we will correct this in the final version. We stress, however, that in all places where the lemma is applied, the summation was already present and used correctly."}]

Author rebuttal:

Meta-review: This paper proposes a best-of-both-worlds (BoBW) algorithm for multi-armed bandits with adversarial delays. As proved by the authors, this algorithm can achieve near-optimal regret bounds in both the stochastic and adversarial settings (about the distribution of loss functions, instead of the delay), which is better than the existing best BoBW algorithm in Masoudian et al. [21].

All reviewers agree that this paper provides a strong theoretical contribution for multi-armed bandits with adversarial delays, and give positive scores before and after the rebuttal period. There also exist some weaknesses, including the lack of empirical evaluation, questions about implementation complexity, and large constants in the regret bounds. Nonetheless, the theoretical advances are substantial and impactful. Thus, I recommend accepting this paper.
Decision: Accept (poster)