acceptodds
Under review as a conference paper at ICLR 2027

Nearly Optimal Best-of-Both-Worlds Guarantees for Delayed Multi-Armed Bandits.

10 views

Abstract

We study multi-armed bandits with delayed feedback. Our goal is to provide best-of-both-worlds regret guarantees, which is to say, guarantee optimal performance in both stochastic and adversarial environments. To this end, we propose a new version of Follow-the-Regularized-Leader (FTRL) with a time-varying hybrid regularizer combining Tsallis entropy and KL divergence. The novelty of the algorithm is in the learning rate for the KL divergence, which tracks the drift of the iterates of the algorithm. This allows the amount of regularization to respond directly to the drift induced by delayed observations. In the stochastic setting, our algorithm guarantees a regret of where denotes the suboptimality gap of arm , is the number of rounds, is the maximum delay, and is the number of actions. On the other hand, in the adversarial setting, the same algorithm guarantees a regret of , where is the total delay. The algorithm requires neither prior knowledge of the total delay nor knowledge of whether the environment is stochastic or adversarial. In both the stochastic and adversarial settings, these guarantees are optimal up to the term. Additionally, we compare our new algorithm with prior state-of-the-art algorithms through synthetic experiments.

Primary area:
reinforcement learning
Keywords:
bandits, delayed feedback, best-of-both-worlds

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_CeCEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work studies best-of-both-worlds multi-armed bandits (MABs) with delayed feedback. The main contribution is that the authors develop a purely follow-the-regularized-leader (FTRL)-based algorithm to obtain a BOBW guarantee with O(∑i≠i⋆log⁡TΔ(i)+dmax⁡K)O\left(\sum_{i \neq i^{\star}} \frac{\log T}{\Delta(i)}+d_{\max } \sqrt{K}\right) regret in the stochastic regime. The significance of this regret is that it eliminates the σmax⁡/Δi\sigma_{\max}/\Delta_i term, which is suffered by all the previous FTRL-based approaches for BOBW delayed MAB and is only eliminated by the more complicated detect-and-switch-based method in [1]. That said, the downside of the main result is that a dmax⁡Kd_{\max}\sqrt{K} term remains in the regret for stochastic and adversarial regimes. This term can be much larger than the Kσmax⁡K\sigma_{\max} term in the previous FTRL-based BOBW result for delayed MAB in [2]. Further, the previous detect-and-switch-based BOBW result for delayed MAB in [1] doesn't have any such remainder. Besides, the tuning of the learning rate for this algorithm requires the knowledge of dmax⁡d_{\max}, which is not required by the previous FTRL-based BOBW algorithm in [2].

Critical strengths
  1. Result: The proposed FTRL-based BOBW algorithm for delayed MAB eliminates the σmax⁡/Δi\sigma_{\max}/\Delta_i term in the regret for the stochastic regime of previous FTRL-based approaches. Prior to this work, such refinement was only known to be achievable for the detect-and-switch-based BOBW algorithm for delayed MAB in [1], yet this kind of method is less adaptive compared to the FTRL-based approach, as it requires explicit environment detection and switching, and its analysis is often more complicated than the FTRL-based ones.
Critical weaknesses
  1. Result: Though a remainder of σmax⁡/Δi\sigma_{\max}/\Delta_i in the regret for stochastic regime is eliminated. Several other concerns arise. Specifically,

    • Such a kind of improvement has already been shown to be achieved by the method in [1], though it is a detect-and-switch-based one. In light of this, the significance of the result is somewhat limited.
    • More importantly, an additional remainder of dmax⁡Kd_{\max}\sqrt{K} appears in both the regret for stochastic and adversarial regimes. The downside of this term is that it might be much worse than the corresponding remainder in the previous FTRL-based BOBW algorithm in [2], and there is not even any such kind of term in the result of the detect-and-switch-based algorithm in [1]. Given this, this somewhat makes people feel that the improvement comes at the cost of introducing a dependence on a worse remainder, which thus again limits the significance of the result.
  2. Position and Presentation: Overall, this work is well written. Nevertheless, I personally feel that the title doesn't seem to be very appropriate. In particular, at first glance, this title makes people feel that this work attains the SOTA result. However, as discussed above, the regret in the stochastic regime in this work is inferior to the result of [1]. In the adversarial regime, the leading term in the regret of this work indeed shaves off a multiplicative log⁡T\log T factor compared to that in [1], yet it additionally has a remainder of dmax⁡Kd_{\max}\sqrt{K}. Therefore, it is also hard to say that the regret in the adversarial regime in this work truly improves upon that in [1]. Collectively, the title doesn't seem to really reflect the position of this work against existing work. In other words, if the result in this work is 'nearly optimal' as claimed in the title, then [1] can also be called 'nearly optimal'. Thus, I think this title is not so informative, and it is actually a bit misleading.

    In the BOBW literature, it is rather challenging to obtain regret upper bounds that fully match the lower bounds, and thus it is kind of a convention in the literature to call such results 'nearly optimal', which I think is understandable and acceptable. However, this still doesn't contradict what I said above, since if there are already some papers on BOBW delayed MABs and yet the latest paper claims to be 'nearly optimal', there is an implication in the title that the result in this latest paper truly improves on the results in previous works. However, this is not the case, given the results in [1].

  3. Knowledge of dmax⁡d_{\max}: The proposed algorithm requires the knowledge of dmax⁡d_{\max}, which is not required by some FTRL-based approaches (say, [2]) and the detect-and-switch-based approach in [1].


[1] Schlisselberg et al. Improved best-of- both-worlds regret for bandits with delayed feedback. NeurIPS, 25.

[2] Masoudian et al. A best-of-both-worlds algorithm for bandits with delayed feedback with robustness to excessive delays. NeurIPS, 24.

Questions for authors

Please see the weakness part above.

3 comments

We address some of your concerns in a general comment. In short: Schlisselberg et. al. (2026) require knowledge of TT. Without this knowledge their bound is of order ∑i≠i⋆(log⁡(T)2Δ(i)+σmax⁡KΔ(i))\sum_{i \neq i^\star} (\frac{\log(T)^2}{\Delta(i)} + \frac{\sigma_{\max}}{K}\Delta(i)) in the stochastic setting and consequently their result is asymptotically suboptimal in both the adversarial and stochastic setting. We have added a standard idea to improve the dependence on dmax⁡d_{\max}.

About the title. We indeed adopted the convention that is standard in the literature. For the new version we opted for a more descriptive title: Tracking the Drift: Improved Best-of-Both-Worlds FTRL for Delayed Bandits.

I thank the authors for their responses, and I would like to maintain my rating for this paper. Also, I'm sorry for the missing references in my original review; I have now added them.

Thank you for the quick response. No problem for the missing references, we could guess from the context what you were referring to.

Just to learn: do you consider the new title and positioning an improvement?

Reviewer_EuFSOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3(+1)
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper studies best-of-both-worlds regret guarantees for multi-armed bandits with delayed feedback. The authors propose Adaptive Tsallis-KL FTRL, which combines Tsallis entropy and KL regularization. The key idea is to adjust the KL regularization coefficient according to the observed drift between delayed and clairvoyant FTRL iterates. The authors establish a stochastic regret bound of O(∑i≠i⋆log⁡T/Δ(i)+dmax⁡K)O(\sum_{i\ne i^\star}\log T/\Delta(i)+d_{\max}\sqrt K) and an adversarial regret bound of O(KT+Dlog⁡K+dmax⁡K)O(\sqrt{KT}+\sqrt{D\log K}+d_{\max}\sqrt K). These bounds improve previous best-of-both-worlds results up to the additive dmax⁡Kd_{\max}\sqrt K term. The paper also presents synthetic experiments comparing the proposed algorithm with existing methods.

Critical strengths
  • Theorem 1 improves previous best-of-both-worlds regret bounds for delayed multi-armed bandits. In particular, it removes the additional σmax⁡/Δ(i)\sigma_{\max}/\Delta(i) terms in previous FTRL algorithms while retaining the optimal leading terms in the adversarial setting.
  • The idea of adapting KL regularization according to the observed drift is interesting. The analysis also involves nontrivial arguments to control the stability of FTRL iterates under delayed feedback.
Critical weaknesses
  • The proof of Lemma 11 appears to overlook drift terms that become computable only after earlier pending feedback arrives (lines 1171–1174). This leaves a gap in the stability analysis used to prove the main regret bounds.
  • The proof of Lemma 5 does not appear to correctly account for when drift terms become available (lines 2092–2095). Moreover, a double sum is replaced by a single sum without accounting for repeated terms (lines 2108–2115). These issues leave a gap in the proof of the adversarial regret bound.
  • The experiments use different tuning constants from those specified in Algorithm 1. It would be helpful to evaluate the algorithm with the theoretical parameter choices.
Questions for authors
  • In Lemma 11, how do the authors justify the bound on the change in the KL regularization coefficient? The proof appears to overlook drift terms that become computable only after earlier pending observations arrive. Does the claimed stability bound still hold?
  • In Lemma 5, could the authors provide a more rigorous derivation of the bound on the KL regularization coefficient? In particular, the treatment of drift terms in lines 2092–2095 and the summation in lines 2108–2115 appear to be incorrect. Can the authors establish the claimed bound despite these issues?
5 comments

About Lemma 11: thank you for catching this. In the new version we fixed this (the Lemma is now Lemma 17).

We defined the set of indices whose drift is computable before round tt: Et:={q<t:max⁡r≤q(r+dr)<t}\mathcal E_t := \Big\lbrace q < t : \max_{r \le q} (r + d_r) < t \Big\rbrace. For this set, St=∑q∈EtXqS_t = \sum_{q \in \mathcal E_t} X_q holds exactly. Moreover, Et⊆Ot\mathcal E_t \subseteq \mathcal O_t, since q+dq<tq + d_q < t. Furthermore, Es⊆Et\mathcal E_s \subseteq \mathcal E_t for s≤ts \le t, because the indicator is monotone in tt. This monotonicity implies Sr−Ss≤∑q∈Et∖Es(Xq)+S_r - S_s \le \sum_{q \in \mathcal E_t \setminus \mathcal E_s} (X_q)^+ for all s≤r≤ts \le r \le t. For the running maximum, this yields the correct inequality λt−λs≤1log⁡K∑q∈Et∖Es(Xq)+\lambda_t - \lambda_s \le \frac{1}{\log K} \sum_{q \in \mathcal E_t \setminus \mathcal E_s} (X_q)^+. If q<s−dmax⁡q < s - d_{\max}, then r+dr≤q+dmax⁡<sr + d_r \le q + d_{\max} < s for all r≤qr \le q, so q∈Esq \in \mathcal E_s. It follows that Et∖Es⊆{s−dmax⁡,…,t−1},∣Et∖Es∣≤(t−s)+dmax⁡≤2dmax⁡.\mathcal E_t \setminus \mathcal E_s \subseteq \lbrace s - d_{\max}, \dots, t - 1 \rbrace, \qquad |\mathcal E_t \setminus \mathcal E_s| \le (t - s) + d_{\max} \le 2 d_{\max}. This only requires bounded delays; Lemma 9 (the bound on ∣Ps∣|\mathcal P_s|) is no longer needed.

About Lemma 5 (still Lemma 5): thank you, we have rewritten the proof. The statement and its constants are unchanged. The drift XsX_s becomes available exactly at the end of round t=max⁡s′≤s(s′+ds′)t = \max_{s' \leq s}(s' + d_{s'}). In the old proof the corresponding indicator was attached to the wrong index inside ZtZ_t. We now define Zt=∑i=1Kpt(i)∑s∈Ptℓ^s(i)ℓ^t(i)≥0Z_t = \sum_{i=1}^K p_t(i) \sum_{s \in P_t} \widehat\ell_s(i)\widehat\ell_t(i) \geq 0 without an indicator, so that Xt≤λt−1ZtX_t \leq \lambda_t^{-1} Z_t, and keep the indicator on the round whose drift is added, which gives λt+12−λt2≤4log⁡(K)∑s=1tZs1[max⁡s′≤s(s′+ds′)=t].\lambda_{t+1}^2 - \lambda_t^2 \leq \frac{4}{\log(K)} \sum_{s=1}^{t} Z_s \mathbf{1}\big[\max_{s' \leq s}(s' + d_{s'}) = t\big]. Since s≤max⁡s′≤s(s′+ds′)≤s+dmax⁡s \leq \max_{s' \leq s}(s' + d_{s'}) \leq s + d_{\max}, for every s≤Ts \leq T there is exactly one t∈{s,…,T+dmax⁡}t \in \lbrace s, \ldots, T + d_{\max} \rbrace with max⁡s′≤s(s′+ds′)=t\max_{s' \leq s}(s' + d_{s'}) = t, so summing over t=1,…,T+dmax⁡t = 1, \ldots, T + d_{\max} gives the single sum ∑s=1TZs\sum_{s=1}^{T} Z_s with no repeated terms. Finally, for s∈Pts \in P_t, the iterate ptp_t does not depend on IsI_s because of the delay, so E[Zt]≤∣Pt∣\mathbb{E}[Z_t] \leq |P_t|, and ∑t=1T∣Pt∣≤∑s=1Tds=D\sum_{t=1}^T |P_t| \leq \sum_{s=1}^T d_s = D.

Thank you for the detailed response and revisions. The paper is well written, and I like the idea of using observed drift to adapt KL regularization. The revised proofs address my concerns about Lemmas 5 and 11, and the addition of Algorithm 2 further strengthens the paper. I will raise my score to 3.

Thank you again for the revisions. I have one remaining concern about the experimental parameter choices. I saw your response to RCJZ that the theoretical constants lead to poor empirical performance. Could you provide some quantitative results or further clarification on this point?

Reviewer_RCJZOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Adaptive Tsallis-KL FTRL for multi-armed bandits with delayed feedback. By adapting the KL regularization parameter to the observed drift, the algorithm achieves nearly optimal regret guarantees in both stochastic and adversarial environments.

Critical strengths
  1. The drift-adaptive learning-rate mechanism is technically interesting.

  2. The algorithm provides a relatively simple FTRL-based approach to delayed best-of-both-worlds learning.

  3. The theoretical analysis is substantial and the presentation is generally clear.

Critical weaknesses
  1. The additional dmax⁡Kd_{\max}\sqrt{K} term prevents optimality and reduces robustness to large delays.

  2. The significance of obtaining these guarantees within FTRL is not sufficiently justified.

  3. The experiments omit Schlisselberg et al. (2025), the most relevant baseline, and do not evaluate genuinely adversarial environments.

Questions for authors
  1. Can the authors clarify the parameter regimes in which the improved adversarial bound outweighs the weaker stochastic delay dependence, and discuss the significance of this tradeoff?

  2. Your adversarial bound contains Masoudian et al.'s dmax⁡K1/3log⁡Kd_{\max}K^{1/3}\log K term plus an extra dmax⁡Kd_{\max}\sqrt{K}. Is it ever better than theirs?

  3. Can you add a truly adversarial experiment (for example, with a switching best arm) and a comparison with Schlisselberg et al.?

  4. How does the algorithm perform with the theoretical constants instead of constants set to 1?

3 comments

We address questions 1 and 2 in the general comment. But a short recap: we provide a second algorithm so that there no longer is a trade-off and clarify the results of Schlisselberg et. al. (2026).

Question 3: you will not find any truly adversarial experiment anywhere in the literature. It is generally not known how to generate adversarial losses and they are like to be specific for a given algorithm. We therefore opted to use the set of experiments designed by Zimmert and Seldin (2020) to test BOBW algorithms.

Question 4: not great due to the large constants in the parameters. We deliberately did not optimize the constants to maintain a readable analysis. Tracking all the constants without bounding them leads to a horrible analysis which makes it harder for anyone to extract the useful ideas, which is why we opted to not optimize the constants.

Thank you for the response and for adding Algorithm 2. However, my main concern remains. With known TT, the stochastic delay term of Schlisselberg et al. is σmaxK∑i≠i⋆Δ(i)≤σmax≤dmax\frac{\sigma_{max}}{K}\sum_{i \neq i^\star} \Delta(i) \leq \sigma_{max} \leq d_{max}, which is still smaller than the dmaxlog⁡Kd_{max}\log K term of Algorithm 2 (Table 1). So the stochastic bound is still weaker than theirs, and the tradeoff is not fully removed. Also, the review didn't solve my concerns on practical sides. For these reasons, I keep my score.

Thank you for your prompt response.

To clarify: the trade-off does not exist in the practically most relevant scenario, which is where we do not know TT or \dmax\dmax. For suitably large TT, in that case the stochastic bound of Schlisselberg et.al. (2025b) is worse than any of the FTRL algorithms, irrespective of lower order terms. In the adversarial setting the bound of Schlisselberg et.al. (2025b) contains the suboptimal log(T) term, which makes it asymptotically suboptimal regardless of knowledge of TT.

Furthermore, as you can tell from the experiments, even with known TT, the algorithm of Schlisselberg et.al. (2025b). Is somewhat lacking in performance. Note that we made more effort to tune this algorithm than all the others. We did a grid search to tune this algorithm, which led to the results you can find in the appendix. All the other algorithms just work out of the box with all constants set to 1.

Would adding the unknown TT result of Schlisselberg et.al. (2025b) to Table 1 help in the comparison?

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the reviewers for their careful reading of the paper. Here we address some comments that were shared between the reviewers.

Dependence on dmax⁡d_{\max}. Indeed, the term dmax⁡Kd_{\max}\sqrt{K} is suboptimal. In the updated submission we address this: we present a second algorithm with three relatively simple and somewhat standard modifications compared to the original algorithm. In the adversarial setting this new algorithm has a regret bound of order KT+Dlog⁡(K)\sqrt{KT} + \sqrt{D\log(K)}. In the stochastic setting this algorithm has a regret bound of order ∑i≠i⋆log⁡(T)Δ(i)+min⁡{σmax+δlog⁡(K)+Nδ,Dlog⁡(K)}\sum_{i \neq i^\star} \frac{\log(T)}{\Delta(i)} + \min\{\sigma_{max} + \delta\log(K) + N_\delta, \sqrt{D\log(K)}\}, where NδN_\delta is the number of rounds with delays that are bigger than δ\delta. In the worst case over delays, we have that min⁡{σmax+δlog⁡(K)+Nδ,Dlog⁡(K)}≤min⁡{3dmax⁡log⁡(K),Dlog⁡(K)}\min\{\sigma_{max} + \delta\log(K) + N_\delta, \sqrt{D\log(K)}\} \leq \min\{3d_{\max}\log(K), \sqrt{D\log(K)}\}, and so this bound is exponentially better in KK compared to our prior result and likewise exponentially better than the dmax⁡K1/3log⁡(K)d_{\max} K^{1/3} \log(K) terms present in prior FTRL analyses.

Even though the second algorithm has better guarantees, we still decided to keep the original algorithm in the paper. The original algorithm and analysis allow us to isolate what we think of as the main new ingredient in its simplest form: a KL learning rate that tracks the observed drift. Its analysis is correspondingly simple and shows that this ingredient, together with the self-bounding and AdaHedge-type arguments that control it, suffice to obtain improved guarantees for FTRL algorithms. We want to emphasize that the reviewers unanimously recognized the value of this idea and unanimously agree that the paper is clear and easy to follow. Algorithm 2 uses the same learning rate without modification; its skipping serves only to keep the iterates multiplicatively stable without knowledge of dmax⁡d_{\max} and follow from relatively standard ideas. Compared to the original algorithm, removing knowledge of dmax⁡d_{\max} comes at the price of a more involved algorithm and significantly more involved analysis. We highly value the simplicity of the original analysis and idea because of what it may teach to the reader and have thus decided to keep it in the paper as our main contribution.

Comparison with Schlisselberg et. al. (2026). The algorithm of Schlisselberg et. al. (2026) requires knowledge of TT. Without this knowledge, it requires a doubling trick which leads to a regret bound of order ∑i≠i⋆(log⁡(T)2Δ(i)+σmax⁡Δ(i))\sum_{i \neq i^\star} (\frac{\log(T)^2}{\Delta(i)} + \sigma_{\max}\Delta(i)) in the stochastic setting, which makes this algorithm asymptotically (in TT) suboptimal, which is not the case for any of the FTRL algorithms. The log⁡(T)2\log(T)^2 was not described in the first version of our paper, but we have added it in the updated version. We have added the results for the algorithm of Schlisselberg et. al. (2026) to the experiments in the appendix, but like we said in the original, we could not get this algorithm to perform as well as the FTRL algorithms. We would like to add that it is somewhat common knowledge in the BOBW community that these detect and switch type algorithms don't perform well in experiments, which is likely the reason for a lack of experiments in papers that employ this type of algorithms.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.