We thank the reviewer for their thoughtful and detailed feedback. Below we address the reviewer’s questions and concerns.

Notation:

We acknowledge the clarity issues and will fix all incorrect references, inconsistent notation, and missing initializations in the final version.

Lack of numerical evaluation:

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

Large constants in regret bounds:

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

Giving improved leading constants may be a challenging future work.

The use of UCB/LCB monotonicity:

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

The use of log(T) in BSC's second check:

The $\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.

Lemma C.3:

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

We thank the reviewer for their thoughtful evaluation and positive feedback. We address the reviewer’s comments and questions below.

Observability of delays:

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

Adversarial corruptions as future work:

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

We thank the reviewer for their positive and constructive feedback. We address the reviewer’s comments and questions below.

“It would be interesting to see if the optimal guarantees presented here are achievable by a simpler algorithm.”

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

On Footnote 1 (capitalization):

Thank you for pointing this out. We will fix the capitalization issue in the final version.

The term $\Phi^*$ in Masoudian et al. [2024]:

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

On the intuition behind the update rule (Procedure 4):

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

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

We thank the reviewer for their thoughtful and constructive feedback. Below we address the reviewer’s specific concerns and questions.

On the lack of empirical evaluation and practical considerations:

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

On non-adversarial delay models (e.g.,stochastic delays):

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

On the “slight modification” in Appendix F:

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

On the role of ALG in the algorithm:

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

We will revise the presentation to make these assumptions and their roles in the analysis more explicit and easier to follow.

On the “general trick” for handling delay dependence (Lines 246–250):

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