- 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 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
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 -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 -dependence under directed graph feedback cannot be adapted to the delayed setting. Specifically, existing graph bandit literature uses two standard ways to achieve :
- To get an exploration set with size bounded by , 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 , this sum is bounded by . 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 -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 -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
where sums inverse gaps over the suboptimal arms with the smallest gaps. Thus we obtain an adversarial bound in terms of 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 to , and uniform exploration in the fallback.
1. Greedy exploration. We agree that greedy set cover produces an out-dominating set of size . 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 by preserves the original observation bounds, while the size of the exploration set becomes . Lemma 22 (Lines 2062–2076) establishes these properties.
2. Uniform exploration and delayed skipping. Your second suggestion applies directly. Mixing the exponential weights with the uniform distribution at weight gives , allowing the inequality of Alon et al. (2015, Lemma 5) to bound
The mixing adds at most one unit of expected regret per fallback run. Since , the stability analysis for exponential weights remains controlled by this bound, and the delayed skipping argument continues to yield (Lemma 24, Lines 2256–2263).
Comparison. The new adversarial bound has an extra factor compared with the directed bound without delays of Rouyer et al. (2022), while the stochastic complexities and 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 (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
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.
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).
Our main contribution is to retain the refined graph-dependent learning cost governed by HG while obtaining an additive delay cost ΔGσ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:
Unlike Delayed SAPO, which requires knowing T in advance, our algorithm adapts to unknown T and α. Retaining observation counts across epochs also allows the delay costs to be summed without an additional factor from the epoch schedule (Lemma 5).
Without delays, directed self-looped feedback graphs admit O(αT) adversarial guarantees (Alon et al., 2015; Rouyer et al., 2022, Theorem 2). Our directed extension depends instead on 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) (Theorem 7; App. A, Lines 810–821; Lemma 9; App. D). Existing α-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)