acceptodds
Under review as a conference paper at ICLR 2027

A Best-of-Both-Worlds Algorithm for Bandits with Delayed Graph Feedback

Abstract

We study best-of-both-worlds (BoBW) online learning with delayed graph feedback, where an action reveals the losses of related actions only after a delay. Existing BoBW algorithms handle either feedback graphs or delays, but not both. We present the first BoBW algorithm for this setting. It requires no knowledge of the horizon, the suboptimality gaps, the delays, or the independence number. For undirected graphs, its regret is against an oblivious adversary and in the stochastic regime, where is the independence number, is a delay term in which excessively delayed rounds may be skipped, is the total delay, is the largest sum of inverse gaps over independent sets of suboptimal arms, and is the maximum number of rounds whose feedback is pending at the same time. The delay thus enters only additively, and in the stochastic regime its coefficient is a gap rather than an inverse gap. Under bandit and full-information feedback this coefficient improves to the average gap .

Primary area:
learning theory
Keywords:
Online Learning, Bandits, Feedback Graphs, Delayed Feedback, Best of Both Worlds, Follow-the-Regularized-Leader

Reviews

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

This paper proposes and primarily analyzes a best-of-both-world algorithm for the bandits with graph feedback and delays. The algorithm is an elimination-based one coupled with a stochasticity test, and followed by a fallback to the adversarial setting when the test fails. It achieves the independence-number dependence under an undirected graph. To handle unknown horizon, the paper uses an anytime scheduling with squaring epochs, so the contribution except for the last epoch is sublinear and thereby dominated. To handle unknown independence number of the graph, it uses an algorithm-intrinsic quantity which remains upper bounded by the actual underlying independence number. Finally, it gives an impossibility result to illustrate the barrier of the average gap term in the graph setting.

Critical strengths
  • Fill in a gap. This paper closes the gap on best-of-both-world algorithms under graph feedback and delay in the literature. It also provides a lower bound for the delay term under graph feedback.
  • New elimination. The elimination threshold used in this paper is new to my knowledge.
Critical weaknesses
  • Poor presentation. The current presentation of this paper is poor. In the main text, it heavily refers to statements or results in the appendices or focuses on computational details without sufficient explanation. A ready-to-publish theory paper should distill the core statements as theorems or lemmata in the main text, together with balanced explanation and computation, while leaving additional details to the appendices, not the opposite.
  • Limited novelty. While the elimination threshold is new, as commented above, the algorithm framework follows Schlisselberg et al. (2025) that couples an elimination-based part for the stochastic regime and falls back to the adversarial regime conditional on a test. The novelty of this work thus seems limited, and the challenges specific to this graph setting are not highlighted in the text, making the core contribution less convincing. Also, the extension from known-horizon to unknown-horizon is standard in the bandit literature.
Questions for authors
  • Could the authors explain why the independence-number only holds under undirected graphs? What makes it challenging to handle directed graphs? In the literature, the arm elimination algorithm does achieve αT\sqrt{\alpha T} even under directed graphs, whereas this paper only claims the max acyclic subgraph number.
  • What is the core technical challenge that makes the graph setting harder than the bandit setting, under the presence of delay?
  • Can the authors explain more about the novelty of the proposed algorithm, compared to the Delayed SAPO in the prior work in Schlisselberg et al. (2025)?
4 comments

Thank you for your constructive feedback. We address your concerns below; line numbers refer to the revised manuscript, with key additions highlighted in dark teal.

W1: Presentation and Main-Text Proofs

Section 1 now identifies the two graph-specific obstacles and explains their solutions in a Technical Overview (Lines 80–115). Section 2 collects the model definitions and main guarantees, while Section 4 provides a proof roadmap and five intermediate lemmas (Lemmas 2–6). In particular, Lemma 4 is now proved in full in the main text (Sec. 4.2, Lines 410–449), making the delayed-summation argument directly verifiable without consulting the appendix. The appendix opens with a dependency map of the supporting proofs (Lines 756–773).

W2, Q2 & Q3: Technical Challenges Under Delayed Graph Feedback and Novelty Relative to Delayed SAPO

Our main contribution is to retain the refined graph-dependent learning cost governed by HGH_G while obtaining an additive delay cost ΔGσmax⁡\Delta_G\sigma_{\max} without inverse-gap dependence. We build on Delayed SAPO (Schlisselberg et al., 2025) and the exploration sets of Rouyer et al. (2022), but their existing analyses do not directly yield this guarantee for two reasons:

  • Unequal observation rates (Q2–Q3). Delayed SAPO samples active arms uniformly, keeping their observation counts comparable and supporting elimination roughly in decreasing gap order. Under graph feedback, side observations make these rates unequal, while uniform sampling fails to exploit the graph structure needed for the refined HGH_G dependence. Our greedy exploration set contains ktk_t active arms, and the sampling rule guarantees every active arm observation probability at least (2kt)−1(2k_t)^{-1} while controlling importance weights across all arms. Separately, a common confidence radius restores gap ordering: on the confidence event, every active gap is at most twice every eliminated gap (Sec. 3.1–3.2; Lemmas 8–9).
  • Shared delayed observations (Q2–Q3). Under delayed graph feedback, a pending round delays feedback from all arms in the played arm's neighborhood. Counting missing observations separately for each arm can therefore charge the same waiting round multiple times, while ignoring side observations loses the refined graph-dependent learning cost. We instead aggregate the common observation lower bound (2ks)−1(2k_s)^{-1} over received rounds to obtain a nonincreasing bound btb_t on the per-round regret from active arms. The key relation ks≤2HGbs−1k_s \le 2H_G b_{s-1} (while at least two arms are active) links graph exploration directly to this bound. Lemma 4 then separates the O(HGλlog⁡n)O(H_G\lambda\log n) learning cost from an additive O(B(1+σmax⁡))O(B(1+\sigma_{\max})) waiting cost, where B≤2ΔGB \le 2\Delta_G, charging each pending round only once (Sec. 4.1–4.2).

Unlike Delayed SAPO, which requires knowing TT in advance, our algorithm adapts to unknown TT and α\alpha. Retaining observation counts across epochs also allows the delay costs to be summed without an additional factor from the epoch schedule (Lemma 5).

Q1: Directed Feedback Graphs and mas⁡(G)\operatorname{mas}(G) vs. α\alpha

Without delays, directed self-looped feedback graphs admit O~(αT)\widetilde{O}(\sqrt{\alpha T}) adversarial guarantees (Alon et al., 2015; Rouyer et al., 2022, Theorem 2). Our directed extension depends instead on mas⁡(G)\operatorname{mas}(G) because the greedy exploration set need only induce an acyclic subgraph rather than an independent set, and our fallback uses ∑ipi/Qi(p)≤mas⁡(G)\sum_i p_i/Q_i(p) \le \operatorname{mas}(G) (Theorem 7; App. A, Lines 810–821; Lemma 9; App. D). Existing α\alpha-dependent analyses instead use different exploration schemes and logarithmic variance bounds (Alon et al., 2015, Lemma 5; Rouyer et al., 2022, Theorem 2), and adapting them to our delayed exploration and skipping fallback remains open.

References

[1] N. Alon, N. Cesa-Bianchi, O. Dekel, and T. Koren. Online learning with feedback graphs: Beyond bandits. In COLT, 2015. (Theorem 2, Lemma 5)

[2] N. Alon, N. Cesa-Bianchi, C. Gentile, S. Mannor, Y. Mansour, and O. Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, 46(6):1785–1826, 2017. (Lemma 10)

[3] C. Rouyer, D. van der Hoeven, N. Cesa-Bianchi, and Y. Seldin. A near-optimal best-of-both-worlds algorithm for online learning with feedback graphs. In NeurIPS, 2022. (Algorithm 2, Proposition 1, Theorem 2)

[4] O. Schlisselberg, T. Lancewicki, P. Auer, and Y. Mansour. Improved best-of-both-worlds regret for bandits with delayed feedback. In NeurIPS, 2025. (Algorithm 2, Theorem 4.1, Corollary 5.4, Lemma 4.2)

I appreciate the authors' efforts in revising the submission and replying. My concern about the presentation is alleviated, but this level of massive revision (much of the unhighlighted text is also different from the original submission) might require every reviewer to review it from scratch, for the sake of fairness and rigor.

My concern about directed graphs remains. I acknowledge that the revised Appendix A provides an extension with mas(G)\mathrm{mas}(G)-dependence, and that the rebuttal briefly mentions alternative exploration schemes and logarithmic variance bounds. However, I am still not convinced that the authors have adequately explained why existing techniques for achieving α\alpha-dependence under directed graph feedback cannot be adapted to the delayed setting. Specifically, existing graph bandit literature uses two standard ways to achieve α\alpha:

  • To get an exploration set with size bounded by α\alpha, they use a greedy construction. The difference between this simple construction and the authors' Section 3.2 is that they scan by degree order. Why is it challenging to adapt this method?
  • The sum of probability fractions is indeed only bounded by MAS. But the literature shows that, if each probability is lower bounded ϵ\epsilon, this sum is bounded by αlog⁡(1/ϵ)\alpha\log(1/\epsilon). Why is it challenging to adapt this method (e.g. adding a tiny exploration)? In particular, the adversarial fallback already uses exponential weights with an adaptive learning rate. Could the authors explain why the α\alpha-dependent variance analysis of Alon et al. (2015), as adopted in Rouyer et al. (2022, Theorem 4), cannot be combined with the delayed skipping analysis, possibly with additional logarithmic factors?

Given that both techniques are relatively standard, I would appreciate a more concrete explanation of the obstacles to combining them with the proposed algorithm. I am not suggesting that a full α\alpha-dependent extension to directed graphs is necessary for this work. Rather, clarifying why the existing approaches are insufficient (if they indeed cannot be adapted) would make the technical contributions and the scope of the results more convincing.

Thank you for your reply and for suggesting these two concrete approaches. Following up on your comment, we explored both directions and found that both techniques can indeed be adapted to delayed feedback. Your suggestions have led us to strengthen our extension to directed graphs.

New result. We have added Appendix I (Lines 1939–2339; Proposition 21, Table 3, and Lemmas 22–25), which establishes

RTadv=O(αTlog⁡(eK) log⁡(eKT)+ΨT),RTsto=O(Srlog⁡(eKT)log⁡(eT)+ΔGσmax⁡),R_T^{\mathrm{adv}} = O\bigl(\sqrt{\alpha T\log(eK)}\,\log(eKT) + \Psi_T\bigr), \qquad R_T^{\mathrm{sto}} = O\bigl(S_r\log(eKT)\log(eT) + \Delta_G\sigma_{\max}\bigr),

where SrS_r sums inverse gaps over the r=min⁡(K−1,⌈12αlog⁡(eK)⌉)r = \min(K-1, \lceil 12\alpha\log(eK)\rceil) suboptimal arms with the smallest gaps. Thus we obtain an adversarial bound in terms of α\alpha while retaining additive delay terms in both regimes. The variant makes three changes to Algorithm 1 (Lines 1962–1984): staged greedy exploration, changing the sampling constant from 6464 to 256256, and uniform exploration in the fallback.

1. Greedy exploration. We agree that greedy set cover produces an out-dominating set of size O(αlog⁡K)O(\alpha\log K). The obstacle to using it directly in our elimination phase is that the consistency test needs observation probabilities tailored to the gap estimates, not just a small exploration set. A global greedy choice can cover an active arm or an arm with a small gap estimate using an eliminated arm with a large gap estimate, whose low sampling probability may fail to satisfy the observation bound required by the test.

Following your suggestion, we instead apply greedy set cover within dyadic gap classes, processing active arms first and then eliminated classes in increasing order of their gap estimates. Every arm is then observed by a selected arm whose gap estimate is at most twice its own. Replacing 6464 by 256=4⋅64256 = 4\cdot 64 preserves the original observation bounds, while the size of the exploration set becomes O(αlog⁡(eK)log⁡(eN))O(\alpha\log(eK)\log(eN)). Lemma 22 (Lines 2062–2076) establishes these properties.

2. Uniform exploration and delayed skipping. Your second suggestion applies directly. Mixing the exponential weights qq with the uniform distribution at weight 1/N1/N gives pi≥1/(KN)p_i \ge 1/(KN), allowing the inequality of Alon et al. (2015, Lemma 5) to bound

∑ipiQi(p)≤8αlog⁡(eKN).\sum_i \frac{p_i}{Q_i(p)} \le 8\alpha\log(eKN).

The mixing adds at most one unit of expected regret per fallback run. Since q≤43pq \le \frac{4}{3}p, the stability analysis for exponential weights remains controlled by this bound, and the delayed skipping argument continues to yield ΨT\Psi_T (Lemma 24, Lines 2256–2263).

Comparison. The new adversarial bound has an extra log⁡(eKT)\sqrt{\log(eKT)} factor compared with the directed bound without delays of Rouyer et al. (2022), while the stochastic complexities SrS_r and HGacH_G^{\mathrm{ac}} in Theorem 7 are generally incomparable.

Revision scope. We also appreciate your concern about the extent of the revisions. Much of the unhighlighted rewriting reflects the reorganization and notation changes made to address presentation concerns across the reviews. These changes do not alter the original algorithms or theorem guarantees. The new result for directed graphs is isolated in Appendix I, without modifying Theorems 1 and 7 or their proofs. Section I.1 (Lines 1939–1997) and the pointers to Appendix I are highlighted in dark teal, while the proofs in Sections I.2–I.7 remain in black for readability. Table 3 (Lines 2005–2013) identifies the steps reused from Theorem 7 and the new arguments, making the additional result easier to assess without rereading the entire manuscript.

Thank you again for these suggestions, which helped us obtain a concrete adaptation of both techniques while clarifying how they interact with elimination and delayed feedback.

Dear Reviewer bTqy,

Thank you for your time and thoughtful engagement with our work. We understand that your schedule may be demanding, and we appreciate your constructive feedback throughout this discussion.

As the discussion deadline is approaching, we kindly ask if you could take a moment to look at our latest response above. Following the two concrete directions you suggested, we obtained a new guarantee for directed graphs in terms of α\alpha (Proposition 21, Appendix I), and we would like to check whether this addresses your remaining concern. If you have any additional questions, we would be more than happy to discuss them further before the discussion period closes.

Once again, thank you for your insightful suggestions and consideration. We look forward to hearing your thoughts.

Best regards,

The Authors

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

The paper studies online learning with a feedback graph under delayed feedback and gives a single algorithm that is near-optimal for both i.i.d. and adversarial losses, where prior work handled graphs and delays separately and naive interleaving inflates stochastic regret by a factor of the delay. Following the Delayed SAPO template, it eliminates arms against a common threshold, plays a randomly rebuilt independent dominating set each round, uses one consistency test that on failure switches to delay-adaptive exponential weights, and reseeds confidence intervals across squared-length epochs so the delay cost is paid once. For undirected graphs, given only the graph, the adversarial bound matches the known delay-free rate up to the delay term, and the stochastic bound is gap-dependent with an additive delay cost. The key technical pieces are a delayed-summation lemma that charges delay per round to the observed arm’s gap rather than per arm, and a refined gap coefficient that reduces to twice the average gap under bandit and full-information feedback, with a matching lower bound showing the average gap itself is unattainable uniformly over connected graphs.

Critical strengths

A complete answer for an important problem: The answer is essentially complete for undirected graphs, and it is more than two templates glued together: the per-round accounting is needed for a real reason, the random tie-breaking is what brings the coefficient down from Delta_max on a clique (the Section 3.2 example makes this concrete), and the Section 5 lower bound explains why the natural first target, Delta_avg sigma_max, is not the right one on general graphs.

Nothing is assumed known—not T, the gaps, the delays, or alpha—and alpha in particular is handled well: the test uses the observed size of the exploration set, which is an independent set.

Critical weaknesses

The delay coefficient is the paper’s central novelty, and it is not pinned down from either side. Nobody can compute this quantity for a given graph, and outside the two extremes handled by Proposition 3 (bandit and full information, where it collapses to 2Δ_avg) a reader cannot even estimate it. The paper acknowledges the gap in one sentence; I think it deserves more. A worked example on a path or a star, and a plainer statement in Section 5 of how the lower-bound family depends on T, would both help.

The stochastic guarantee is obtained through an explicit consistency test, not through a self-bounding argument, and so the paper offers nothing in the corrupted or intermediate regime that the BoBW results it compares itself to handle as a matter of course. Appendix A explains why the reduction of Dann et al. is unavailable here: no base algorithm with a local self-bounding guarantee is known under delayed graph feedback, and the existing self-bounding analyses of delayed FTRL yield inverse-gap delay terms. The explanation is convincing, but it marks a limit of the technique rather than of the presentation, and the result is best of two worlds rather than best of all.

Questions for authors

See weaknesses especially for the delay coefficient.

Q1. Is the log factor inherent or could another schedule remove it?

Q2. The delays are fixed in advance. If they are instead drawn i.i.d., independently of the losses and of the learner’s randomness, does the stochastic bound go through by conditioning, with E[sigma_max] in place of sigma_max, or does the deterministic mask used in Lemma 9 become a problem?

Q3. Why does the abstract state the stochastic delay term with Delta_max rather than Delta_G? As written, the abstract undersells Theorem 1.

Q4. Is there a graph family on which Delta_G^pi is strictly between Delta_avg and Delta_max and the bound is known to be tight?

3 comments

Thank you for your constructive feedback. We address your concerns below; line numbers refer to the revised manuscript, with key additions highlighted in dark teal.

W1 & Q4: Interpretability, Bounds, Worked Examples, and Tightness of the Delay Coefficient

Theorem 1 now states the stochastic guarantee explicitly in terms of ΔG\Delta_G, the maximum average gap over maximal independent sets (Sec. 2, Lines 145–152, 171), and Proposition 12 refines it to the random-order coefficient ΔGπ≤min⁡1,2ΔG\Delta_G^\pi \le \min\\{1, 2\Delta_G\\} (Sec. 2, Lines 191–196; App. C.3, Lines 1213–1218). Neither coefficient needs to be computed by the algorithm.

  • Lower bound and coefficient comparisons. Under constant delay dd, no feedback arrives during the first min⁡T,d+1\min\\{T,d+1\\} rounds. Permuting any fixed gap multiset uniformly at random across vertices gives a lower bound of Δavgmin⁡T,d+1\Delta_{\mathrm{avg}}\min\\{T,d+1\\} on some assignment (Proposition 20, App. G, Lines 1895–1904). For comparison, ΔG≤(K/i(G))Δavg\Delta_G \le (K/i(G))\Delta_{\mathrm{avg}}, where i(G)i(G) is the minimum size of a maximal independent set, though this bound can be loose. On bandits, complete graphs, and disjoint unions of equal-size cliques, the random-order coefficient satisfies ΔGπ≤2Δavg\Delta_G^\pi \le 2\Delta_{\mathrm{avg}} (Corollary 14, App. C.4, Lines 1303–1310), matching the order of this initial waiting lower bound in the delay coefficient on these graph families.
  • Worked examples and remaining optimality gap (W1, Q4). Following your suggestion, Appendix C.4 (Lines 1327–1337) evaluates a four-vertex star with an optimal center and leaf gaps (κ,2κ,2κ)(\kappa,2\kappa,2\kappa): Δavg=54κ<ΔGπ=43κ<ΔG=53κ<Δmax⁡=2κ.\Delta_{\mathrm{avg}}=\frac{5}{4}\kappa < \Delta_G^\pi=\frac{4}{3}\kappa < \Delta_G=\frac{5}{3}\kappa < \Delta_{\max}=2\kappa. A second family satisfies ΔGπ=Δavg≪ΔG\Delta_G^\pi=\Delta_{\mathrm{avg}}\ll\Delta_G (Lines 1339–1349). These examples illustrate the role of graph structure and random exploration order, but do not establish tightness. In particular, we do not know a family with Δavg<ΔGπ<Δmax⁡\Delta_{\mathrm{avg}} < \Delta_G^\pi < \Delta_{\max} for which ΔGπ\Delta_G^\pi is proved optimal, and characterizing the optimal delay coefficient on general graphs remains open (Sec. 6, Lines 537–538).

Our main guarantee separates the graph-dependent learning cost governed by HGH_G from an additive delay cost without inverse-gap dependence.

Q1: Is the log⁡T\log T factor inherent or could another schedule remove it?

The extra logarithm arises within each epoch of our current analysis rather than from summing over epochs. Specifically, one logarithm comes from the confidence parameter, and the second from integrating shared observations and summing the 1/t1/t monitoring rates within each epoch (Sec. 2, Lines 182–186; Lemmas 3–4). Our squared schedule Nm+1=Nm2N_{m+1}=N_m^2 already avoids an additional logarithmic loss across epochs while retaining the anytime adversarial guarantee (Sec. 3.5, Lines 346–350), so changing our restart schedule alone would not remove this factor. Meanwhile, Delayed SAPO (Schlisselberg et al., 2025) achieves a single-logarithm learning term under bandit feedback using a known horizon TT, and standard black-box restart wrappers cannot simultaneously preserve a single-logarithm stochastic bound and an O(T)O(\sqrt{T}) adversarial bound (Besson & Kaufmann, 2018). Whether an anytime algorithm beyond black-box restarts can remove this extra logarithm remains open (Sec. 6, Lines 537–539).

Q2: Random i.i.d. delays and the deterministic arrival mask

Yes, when the delay sequence d1,d2,…d_1, d_2, \dots is jointly independent of the losses and the learner's randomness. Conditioning on the delays fixes all arrival times, keeping the arrival indicators ws(t)=1s+ds≤tw_s(t)=\mathbf{1}\\{s+d_s\le t\\} in Lemma 10 (App. B.1, Line 953; submission Lemma 9) deterministic without altering the loss law or sampling distributions. Taking expectations over the delays gives Theorem 1 and Proposition 12 with E[σmax⁡]\mathbb{E}[\sigma_{\max}] and E[ΨT]\mathbb{E}[\Psi_T] in place of σmax⁡\sigma_{\max} and ΨT\Psi_T (App. F, Lines 1862–1872). For i.i.d. delays with mean dˉ<∞\bar{d} < \infty, E[σmax⁡]≤(e−1)dˉ+log⁡T\mathbb{E}[\sigma_{\max}]\le(e-1)\bar{d}+\log T, yielding an additive O(ΔGπdˉ)O(\Delta_G^\pi \bar{d}) stochastic delay term after absorbing ΔGπlog⁡T\Delta_G^\pi \log T into the learning term (Lines 1873–1889).

Q3: Delay term in the abstract

Thank you for catching this; the abstract now states the stochastic delay term with ΔGσmax⁡\Delta_G\sigma_{\max} (Lines 15–18).

References

[1] L. Besson and E. Kaufmann. What doubling tricks can and can't do for multi-armed bandits. arXiv:1803.06971, 2018.

[2] O. Schlisselberg, T. Lancewicki, P. Auer, and Y. Mansour. Improved best-of-both-worlds regret for bandits with delayed feedback. In NeurIPS, 2025. (Algorithm 2, Theorem 4.1, Corollary 5.4)

Thank you for your response. I have no further questions.

Thank you for taking the time to consider our response. We appreciate your constructive feedback, which has helped us improve the manuscript.

Reviewer_FYvVOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes a best-of-both-worlds algorithm, which achieves favorable regret guarantees in both stochastic and adversarial settings simultaneously, for online learning with feedback graphs under delayed feedback. The proposed algorithm combines exploration that exploits the graph structure with a consistency test to establish regret upper bounds in both settings. Under the assumption that every vertex has a self-loop, the algorithm simultaneously achieves several desirable types of regret bounds that depends on the independence number of the feedback graph, which is typical in online learning with feedback graphs, that ignore significant delays, which is known in the literature of bandits with delayed feedback.

Critical strengths

This paper addresses an important problem of online learning with feedback graphs under delayed feedback, which is of interest to the online learning community. In particular, considering graph feedback, delayed feedback, and best-of-both-worlds guarantees simultaneously is an important task in the community and improving the dependence on the delay by Rouyer et al. (2022) is an important contribution.

Critical weaknesses

The most significant weakness of this paper is its lack of clarity throughout the manuscript, particularly the insufficient explanations of key concepts and the proposed algorithm. To list some examples, Line 87 mentions fixed tie-breaking without explaining why tie-breaking is an issue in the first place. The explanation of Algorithm 1 is also highly insufficient in that concepts that have not been introduced earlier appear without explanation, and the correspondence between the descriptions in the main text and the individual steps in the pseudocode is unclear. The word delay-adaptive exponential-weights algorithm mentioned in Line 187 is not adequately explained, either in terms of its specific procedure. The description of the paragraph "Approach" in the introduction is also difficult to follow without reading the further details written in the later part of the paper. Furthermore, the manuscript frequently uses terminology that seems nonstandard or is not adequately explained, such as "immediate graph feedback" in Line 44 and "per-arm counting argument" in Line 84. Although the intended meanings of such expressions can sometimes be inferred, I feel that this writing style is inappropriate. There are also several instances where notation is used before being defined or is described informally and ambiguously. These issues significantly decrease the readability of the paper. I believe the manuscript requires substantial revisions to its overall structure and explanations, as well as thorough proofreading.

Another major weakness of this paper is that the theoretical guarantees are not sufficiently strong. First, the analysis relies on the restrictive assumption that every vertex in the feedback graph has a self-loop. This imposes a significant restriction on the feedback structure. It is desirable to handle the more general strongly observable graphs, as considered in the existing literature. Moreover, despite the importance of this strong assumption, this is not sufficiently emphasized in the abstract or Table 1. Second, the paper does not provide sufficient discussion of the strength or optimality of the obtained regret upper bounds. It is unclear whether the dependence on HG(Δ)H_G(\Delta) in the stochastic regret bound is optimal for feedback graphs with self-loops. Furthermore, even in basic special cases, such as the full-information setting, the resulting regret upper bounds are substantially worse than known guarantees, which is very undesirable. Given that the analysis already imposes the strong assumption on the feedback graph, the resulting theoretical guarantees are still not sufficiently strong.

Questions for authors

Can the results be extended to general strongly observable graphs? What are the main technical difficulties in removing the assumption that every vertex has a self-loop?

5 comments

Thank you for your careful reading and constructive feedback. Sincerely, we would like to address your concerns as follows (all line numbers refer to the revised manuscript, where key additions are highlighted in dark teal).

W1: Presentation and clarity of key concepts, Algorithm 1, terminology, and proofs.

Thank you for highlighting these presentation issues. We have substantially reorganized and revised the manuscript to improve its readability and technical clarity.

First, for the overall organization and technical exposition, we replaced the original "Approach" paragraph with an explicit discussion of two graph-specific obstacles (Sec. 1, Lines 80–98) vand a Technical Overview explaining their solutions (Sec. 1, Lines 100–115). All model definitions and main results are now collected in Section 2.

Second, for the algorithm and notation, Section 3 now introduces the epoch structure (Lines 197–201) and indexing conventions (Lines 203–209) before Algorithm 1, whose steps carry explicit labels and cross-references to Sections 3.1–3.4 (Lines 216–235). The adversarial fallback is now described in the main text (Sec. 3.4, Lines 326–334), with its complete five-step procedure in Appendix D (Lines 1518–1542). We also standardized terminology (Sec. 1, Lines 44–46, 95–98), separated exploration ordering as a delay-coefficient refinement (Sec. 2, Lines 189–193; Sec. 3.2, Lines 263–266), and added a notation table (Table 2, App. A, Line 829).

Third, for the main-text proofs, Section 4 now opens with a proof roadmap (Lines 348–354), states the core intermediate lemmas (Lemmas 2–6) in the main text, and proves the delayed-summation lemma (Lemma 4) in full in Section 4.2 (Lines 417–449) rather than merely sketching it. The appendix also opens with a dependency map of the supporting proofs (Lines 756–773).

W2: Strength of the theoretical guarantees, the self-loop assumption, and optimality in special cases.

Regarding scope and the self-loop assumption, even without delays, BoBW bounds for general strongly observable graphs depend on α/Δmin⁡\alpha/\Delta_{\min} (Ito et al., 2022; Dann et al., 2023), whereas refined HGH_G bounds assume self-loops at all vertices (Rouyer et al., 2022). Since HGH_G can be much smaller than α/Δmin⁡\alpha/\Delta_{\min}, our bound preserves this finer complexity alongside an additive delay cost without inverse-gap dependence and an anytime O~(αT)\widetilde{O}(\sqrt{\alpha T}) adversarial guarantee. The self-loop assumption is now stated explicitly in the abstract (Lines 13–14), Table 1 (Lines 55–56), and Section 1 (Lines 85–86).

Regarding optimality and special cases, the HGH_G dependence of our learning term matches Rouyer et al. (2022) and is tight up to logarithms on bandits and disjoint unions of cliques, whereas exact complexity on general self-looped graphs is characterized by an allocation LP even without delays (Marinov et al., 2022; App. H, Lines 1908–1911). Section 2 (Lines 180–187) now explains the extra log⁡T\log T in our anytime bound relative to Delayed SAPO (Schlisselberg et al., 2025), which requires knowing TT in advance, and notes that our general-purpose bound does not recover specialized TT-independent regret under delay-free full information (Mourtada & Gaïffas, 2019). Under delayed full information, our random-order refinement still gives an O(Δavgσmax⁡)O(\Delta_{\mathrm{avg}}\sigma_{\max}) delay term (Corollary 14, Sec. 2, Lines 189–193; App. C.4, Lines 1303–1310).

Q1 & Q2: Can the results be extended to general strongly observable graphs? What are the main technical difficulties in removing the assumption that every vertex has a self-loop?

Our guarantees do not extend directly to graphs without self-loops. The difficulties go beyond replacing the graph parameter and require changes to the algorithm itself. Specifically, three technical difficulties arise: (1) independent-set exploration can assign zero observation probability to a selected arm lacking a self-loop, invalidating Lemma 9 (App. B, Lines 918–924); (2) the test statistic (9) (Sec. 3.3, Line 310) uses the played arm's loss, which may go unobserved without a self-loop; and (3) our parameter-free fallback analysis relies on ∑ipi/Qi(p)≤α\sum_i p_i/Q_i(p) \le \alpha for undirected self-looped graphs (Sec. 3.4, Line 331; App. D, Lines 1570–1572).

Thank you again for your detailed feedback, which has helped us substantially improve the clarity and positioning of the manuscript. Please let us know if you have any further questions.

References

[1] C. Dann, C.-Y. Wei, J. Zimmert. A Blackbox Approach to Best of Both Worlds in Bandits and Beyond. COLT 2023 (Corollary 15).

[2] S. Ito, T. Tsuchiya, J. Honda. Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs. NeurIPS 2022 (Theorem 4).

[3] T. V. Marinov, M. Mohri, J. Zimmert. Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality. NeurIPS 2022.

[4] J. Mourtada, S. Gaïffas. On the Optimality of the Hedge Algorithm in the Stochastic Regime. JMLR 20(83):1–28, 2019 (Theorem 2).

[5] C. Rouyer, D. van der Hoeven, N. Cesa-Bianchi, Y. Seldin. A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs. NeurIPS 2022 (Theorem 3, Corollary 1).

[6] O. Schlisselberg, T. Lancewicki, P. Auer, Y. Mansour. Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback. NeurIPS 2025 (Algorithm 2, Theorem 4.1, Corollary 5.4).

Dear Reviewer FYvV,

Thank you for your valuable time and thoughtful review of our work. We understand that your schedule may be demanding, and we appreciate your constructive feedback.

As the discussion deadline is approaching, we kindly ask if you could take a moment to review our response above to see whether it addresses your concerns. In addition, following suggestions from Reviewer bTqy during the discussion, we have added a new guarantee for directed graphs in terms of α\alpha (Proposition 21, Appendix I) that further strengthens our theoretical results. If you have any remaining questions, we would be glad to discuss them before the discussion period closes.

Thank you again for your helpful comments and consideration. We look forward to your feedback.

Best regards,

The Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response and Summary of Revisions

We thank the Area Chair and reviewers for their careful reading and constructive feedback. We have substantially revised the manuscript to address the reviews. Key changes are indicated in dark teal, with details provided in our individual responses. Line numbers refer to the revised PDF.

Main Contribution

We give an anytime best-of-both-worlds algorithm for delayed feedback on known undirected self-looped graphs, achieving O(HGlog⁡(eKT)log⁡(eT)+ΔGσmax⁡)O(H_G\log(eKT)\log(eT)+\Delta_G\sigma_{\max}) stochastic pseudo-regret and O(αTlog⁡(eKT)+ΨT)O(\sqrt{\alpha T\log(eKT)}+\Psi_T) adversarial pseudo-regret (Theorem 1). The delay cost enters additively, without multiplying the refined HGH_G learning term or introducing inverse-gap dependence. The two main technical challenges are gap-ordered elimination under unequal observation rates and accounting for shared delayed observations without repeatedly charging pending rounds. We resolve them using a common confidence radius and a new delayed-summation argument.

Main Revisions

  1. Presentation and algorithm. We reorganized the Introduction around the two graph-specific obstacles, added a Technical Overview, clarified Algorithm 1 and its fallback, and collected the main guarantees in Section 2 (Secs. 1–3).
  2. Main-text analysis. Section 4 now states five key intermediate lemmas and includes the complete proof of the central delayed-summation lemma (Lemma 4), previously only sketched in the main text.
  3. Scope and additional results. We clarified the self-loop assumption and regret comparisons, added worked examples of the delay coefficient, extended the analysis to independent random delays, and, following Reviewer bTqy's technical suggestions, developed a directed-graph variant with α\alpha-dependent adversarial regret (Sec. 2; Apps. C.4, F, and I).

We address each reviewer's specific concerns in our separate responses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.