{"id":"6b8edf50-c0d9-44ba-8360-b110c944e7b8","arxiv_id":"2502.04678","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper claims a near-optimal regret bound for cross-learning contextual bandits with graphical feedback, but the theorem as stated is not supported for graphs without self-loops, per the paper's own conclusion.","lead":"This paper proposes an algorithm for cross-learning contextual bandits with graphical feedback, claiming a regret bound of O~(sqrt(alpha T)) for stochastic contexts and oblivious adversarial losses. It aims to settle an open question from prior work, but the paper's own conclusion directly contradicts its abstract's claim about graphs without self-loops.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is stated for all strongly observable graphs, but the proof's graph inequality fails for no-self-loop arms, as the paper's own Conclusion concedes.","rationale":"The reader's weakest assumption is precisely the load-bearing flaw I find. The paper's own text contains a direct contradiction: the abstract and Theorem 1 advertise all strongly observable graphs, including arms without self-loops, while Section 5 states that the no-self-loops case is open and that Lemma 3 fails there. This is not a matter of external consensus or stylistic overclaim; it is an internal gap in the proof of the stated theorem. The formal proof of Theorem 1 relies on Lemma 3 to bound the inverse-observation-probability sums. For self-loop arms, the observation probability includes the played arm itself, so Lemma 3 applies naturally. For no-self-loop arms, the denominator loses the p_t(a) term, and the required inequality is no longer the one provided. The paper's conclusion confirms that the authors were unable to bridge this case. Since the advertised contribution is the removal of polynomial dependence on the number of contexts for all strongly observable graphs, and the proof does not cover the no-self-loop subset, the central claim as stated is not supported. The algorithm and analysis may still form a valid contribution for graphs with self-loops, and the paper could be repaired by restricting Theorem 1 accordingly, but as submitted the reader's REJECT verdict remains appropriate. I found no additional concern that changes this conclusion.","tokens_in":18937,"tokens_out":8405,"duration_ms":89024,"concrete_test":"Take the two-arm strongly observable graph without self-loops (edges 1 -> 2 and 2 -> 1, alpha = 1) and re-derive the final graph-sum bound of Appendix B in this instance. For this graph, w_e(a) = 1 - p_e(a) after marginalizing over contexts, so the relevant quantity is sum_a p_e(a)/(1 - p_e(a)), which is unbounded as p_e concentrates. Check whether any step in the proof of Theorem 1 prevents this term from exceeding O~(sqrt(T)); if no such step exists, Lemma 3 cannot be the controlling inequality and Theorem 1's 'all strongly observable graphs' claim is unsupported. Alternatively, inspect the linked Lean formalization's statement of Theorem 1: if it includes an explicit self-loop assumption on every arm, then the abstract overclaims the formalized result.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract and Theorem 1 claim the O~(sqrt(alpha T)) regret bound for every strongly observable feedback graph, explicitly 'including those with arms without self-loops.' The final step of the proof of Theorem 1 (Section B, 'Combining the pieces together') applies Lemma 3, the Alon et al. graph inequality bounding sum_i w_i/(w_i + sum_{j in N_in(i)} w_j), to the empirical observation probabilities. This lemma is the bridge that converts the algorithm's inverse-observation-probability terms into an O~(alpha T) bound. But for an arm without a self-loop, the observation probability at a round is w_t(a) = E_c[sum_{a' -> a} p_{t,c}(a')], which excludes the p_t(a) contribution that Lemma 3's denominator supplies. A frequently played no-self-loop arm can therefore have a vanishing observation probability, and the ratio p_t(a)/w_t(a) is not controlled by the lemma as stated. The paper's Conclusion (Section 5) says exactly this: 'The main problem is that Lemma 3 does not hold for the non-including self-loops case' and 'We leave the extension of our results to the case without self-loops as an interesting open question.' That is an internal contradiction with the claimed scope of Theorem 1. Unless the proof supplies a different replacement inequality for no-self-loop arms, the theorem as stated is not proven; at best it is proven for graphs in which every arm has a self-loop.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies cross-learning contextual bandits with graphical feedback (Han et al., 2024) under i.i.d. contexts and oblivious adversarial losses. Its main theorem claims that for every strongly observable feedback graph with independence number α, an FTRL-style algorithm with an epoch schedule and a rejection-sampling estimate of observation probabilities achieves expected regret O~(√(αT)), independent of the number of contexts. A shorter analysis for a known context distribution is followed by a longer analysis for unknown ν, with the proof decomposed into five bias/FTRL terms in Appendix B. The paper also reports controlled experiments and claims an end-to-end Lean formalization exceeding 100,000 lines.","tokens_in":19141,"tokens_out":13657,"duration_ms":138042,"significance":"If correct, the result is a significant resolution of an open problem posed by Han et al. (2024) and Wen et al. (2024): it would match the vanilla graphical-bandit rate O~(√(αT)) and remove the polynomial dependence on the number of contexts. The adaptation of the epoch/rejection-sampling technique of Schneider & Zimmert (2023) to graphical feedback is a plausible and interesting strategy, and the claimed Lean formalization and public artifact are notable strengths, provided they are verifiable. However, the paper contains an internal contradiction between the advertised scope and its own conclusion, and the proof has parameter-regime issues. After restricting the result to graphs with self-loops and repairing the parameter conditions, the remaining contribution would still be valuable, but the manuscript as written is not a correct proof of the stated theorem.","major_comments":[{"comment":"The abstract explicitly claims coverage of all strongly observable graphs, 'including those with arms without self-loops,' and Theorem 1 is stated for strongly observable graphs. Section 5 says, however, that 'The main problem is that Lemma 3 does not hold for the non-including self-loops case' and 'We leave the extension of our results to the case without self-loops as an interesting open question.' Lemma 3 is exactly the final step in Appendix B that converts the sum ∑_t∑_a p_t(a)/(w_e(a)+γ) into an O~(αT) bound. Therefore the main theorem as stated is not proved; the manuscript must either restrict its scope to graphs in which every arm has a self-loop or supply a replacement graph inequality for the no-self-loop case. This is a load-bearing inconsistency, not a presentation issue.","section":"Abstract and Section 5 (Conclusion)"},{"comment":"The parameter choices in Theorem 1 violate the hypothesis of Lemma 10. With L = sqrt(ι α T / log K), γ = 16ι/L, and η = γ/(2(2Lγ+ι)), one has Lγ = 16ι and hence η = 8/(33L), which is larger than (log 2)/(5L) ≈ 0.1386/L. Lemma 10, however, requires η ≤ log(2)/(5L) to conclude that q_t = p_t and that p_t,c(a) is within a constant factor of s_e,c(a) under the event Q. This conclusion is used in bounding bias1, bias3, bias4, and the ftrl term in Appendix B. The proof as written therefore has an invalid parameter regime; the choices of γ and η must be reconciled with Lemma 10.","section":"Theorem 1 and Lemma 10 (Appendix A)"},{"comment":"The reduction to Lemma 3 is not spelled out correctly. Section 3.2 claims that Lemma 3 shows ∑_t∑_a p_t(a)/w_t(a) = O~(αT), but Lemma 3 as printed bounds ∑_i w_i/(w_i + ∑_{j∈N_in(i)} w_j). Under the paper's definition N_in(a) = {v : v→a}, which includes a itself when a has a self-loop, the denominator in Lemma 3 would count w_i twice, so the two expressions are not the same. The reduction must be made precise, for example by defining the in-neighborhood in Lemma 3 to exclude the vertex itself and taking w_i = p_t(i); otherwise the known-distribution analysis and the final application in Appendix B are not rigorous as written.","section":"Section 3.2 and Lemma 3"}],"minor_comments":[{"comment":"The definition of strong observability allows arms without self-loops, while Section 5 speaks of 'the assumption that the graph G includes self-loops.' The formal assumptions of Theorem 1 should state explicitly whether self-loops are assumed, to match the proof and the conclusion.","section":"Section 1, footnote 2 and Section 5"},{"comment":"The pseudocode has several formatting errors: the line defining s_{e+1,c_tf}(Nin(a))/(2(L/2)) is difficult to parse, the Bernoulli sampling line is missing a closing parenthesis, and the role of 'RandPerm(t, t+1)' should be explained in the text or pseudocode.","section":"Algorithm 2 pseudocode"},{"comment":"The final display contains '98KTℓ/L', where ℓ should be ι, and a summation variable 'C' is used where 'M' for the number of contexts is intended elsewhere.","section":"Appendix B, final bounds"},{"comment":"The claim of an end-to-end Lean formalization exceeding 100,000 lines is not evidenced in the manuscript; the appendix does not describe the formalization, and a review artifact link alone is not enough for verification. Please provide a description of what is formalized, which theorem statement is checked, and how the artifact can be compiled.","section":"Abstract"},{"comment":"In Algorithm 1, the FTRL update writes '- η^{-1} F(x)' while the text defines F(p) = ∑ p_i log p_i; with this sign convention the negative entropy should appear with a plus sign in the argmin, or F should be defined as the negative entropy. The current notation is internally inconsistent.","section":"Section 3.2"}],"recommendation":"major_revision","confidential_remarks":"The contradiction between the abstract's no-self-loop claim and Section 5's open-question statement is stark and suggests the paper was assembled from different versions. I see no reason to doubt the authors' intention, but the advertised theorem is not the theorem proved. The result for self-loop graphs may well be correct after fixing the parameter regime, so I recommend a major revision rather than rejection: the authors should restate the theorem to match the proof, repair the constants in Lemma 10, and clarify the Lemma 3 reduction. If the no-self-loop case is kept in the abstract, a genuinely new argument is needed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's real content is an algorithm that achieves O~(sqrt(alpha T)) regret for cross-learning contextual bandits with graphical feedback when the feedback graph has a self-loop at every arm, under stochastic contexts and oblivious adversarial losses. That is a genuine step and would settle the open question for that case. The epoch-based importance estimation adapted from Schneider & Zimmert has plausible machinery, and the known-distribution warm-up is clean. I checked the importance-weighting equality that one reader flagged, and it is fine: conditional on the past, p_{t,c} is fixed, and the indicator's expectation marginalizes to w_t(a) when averaged over the context. So that concern is not real.\n\nThe problem is the stated scope. The abstract and Theorem 1 claim coverage of all strongly observable graphs, including arms without self-loops. The proof's final step applies Lemma 3, and the paper's own conclusion says that lemma does not hold for the no-self-loop case and leaves that extension as an open question. That is a direct contradiction. The theorem as stated is not proven; at best it holds for graphs where every arm has a self-loop. The abstract's mention of a 100,000-line Lean formalization and controlled synthetic experiments also has no corresponding section in the body, no repository contents, no commit hash, and no experiment methodology, so those claims are not verifiable from this preprint.\n\nI do not think this is a dishonest paper; the conclusion is candid about the limitation, which makes the abstract overreach more puzzling than malicious. But the mismatch is load-bearing because the no-self-loop case is exactly what the abstract advertises as new.\n\nWho is this for? People working on graphical bandits and cross-learning. The self-loop result itself is worth discussing. But as submitted, no one should cite Theorem 1 as covering no-self-loop graphs.\n\nRecommendation: send it to peer review, but the authors must either shrink the claim to the self-loop case or supply a proof for the missing case. The formalization and experiment claims need to be substantiated or dropped. With the scope corrected, this is a solid paper.","headline":"A plausible self-loop result, overclaimed as covering all strongly observable graphs; the proof's own conclusion contradicts the abstract.","tokens_in":19730,"tokens_out":3910,"would_cite":false,"duration_ms":33859,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Cross-learning bandit algorithm claims O~(sqrt(alpha T)) regret, independent of the number of contexts.","keywords":["cross-learning contextual bandits","graphical feedback","strongly observable graphs","independence number","adversarial bandits","regret bounds","first-price auctions","FTRL"],"falsifier":"Evaluate the key graph sum, sum over arms of w_i/(w_i + sum of in-neighbor weights), on a strongly observable digraph with no self-loops, such as a complete digraph without loops with a weight vector concentrated on one arm; if any instance violates the claimed O(alpha log(K/(alpha epsilon))) bound, the theorem as stated cannot follow from the paper's final step. Alternatively, run the algorithm on that no-self-loop graph and check whether empirical regret tracks O~(sqrt(alpha T)) or grows with the number of contexts.","tokens_in":18655,"feed_emoji":"🎯","tokens_out":10760,"duration_ms":93968,"temperature":0.7,"pith_summary":"The paper tries to settle an open question in cross-learning contextual bandits with graphical feedback: can regret be O~(sqrt(alpha T)), independent of the number of contexts, when contexts are drawn i.i.d. from a fixed distribution? It presents an epoch-based FTRL algorithm that estimates each arm's observation probability from snapshots, builds an importance-weighted loss estimator, and feeds it to a per-context follow-the-regularized-leader update. If correct, the bound matches the minimax regret of ordinary graphical bandits and removes the M-dependence that earlier algorithms could not avoid. The paper states the theorem for all strongly observable graphs, but its own conclusion records that the final graph inequality does not hold when arms lack self-loops and leaves that case open, so the proof as written supports only graphs where every arm is linked to itself.","feed_headline":"Bandit regret drops to O~(sqrt(alpha T)) regardless of context count","feed_subtitle":"Epoch-based estimator removes the context-count term and matches vanilla graphical bandits.","key_machinery":"The central machinery is an epoch-based importance-weighted estimator with paired time steps. Each epoch fixes a snapshot s_e of the FTRL distribution, defines a target observation probability w_e(a) for every arm, and plays from a mixture q_t that allows rejection sampling to realize w_e(a); half of each paired round estimates the sampling frequency and half estimates losses, producing conditional independence between the pseudo-estimator and the pseudo-distribution used in the analysis. The estimates feed a per-context FTRL subroutine with negative-entropy regularization, and the proof closes with Lemma 3 of Alon et al. (2015), which bounds the sum of w_i/(w_i + sum of in-neighbor weights) by O(alpha log(K/(alpha epsilon))) and is the step that requires self-loops.","core_discovery":"On the paper's own terms, the discovery is that adversarial-bandit techniques, run per context and coupled across contexts by the graphical feedback, are enough to remove the context-count dependence. The algorithm plays from a distribution produced by FTRL while a separate snapshot distribution controls how often each arm's loss can be observed; rejection sampling and paired time steps keep the observation indicator nearly independent of the estimator, and an epoch schedule lets the algorithm estimate the unknown context distribution's contribution to each arm's observability. The proof decomposes regret into five terms, bounds each with concentration inequalities, and closes with a graph-theoretic sum bound. The paper also claims the result holds for oblivious adversarial losses, so the stochastic-loss version follows as a corollary. The closing section states that the final graph inequality is not valid without self-loops, which means the full advertised graph class is not covered by the supplied proof.","pith_inferences":["Read strictly, the paper's own conclusion limits the proven result to graphs in which every arm has a self-loop; for no-self-loop strongly observable graphs the claimed rate is not established by this proof.","The paired-time-step decoupling of estimation from play is reusable for other partial-feedback structures, since the graph enters the argument mainly through the final inequality on observation probabilities.","For repeated first-price auctions, a direct corollary of the claimed bound would be that the number of private-value types is not a bottleneck at the minimax level, so fine discretization of values should not dominate regret.","A stress test on a no-self-loop strongly observable graph would separate a proof gap from a genuine obstacle: if regret there is empirically worse than O~(sqrt(alpha T)), the missing inequality is substantive."],"forward_implications":["If the theorem holds, the regret no longer depends on the number of contexts, so increasing context resolution does not change the leading-order bound.","Because the losses may be oblivious adversarial rather than stochastic, the stochastic-loss guarantee is a corollary and not the main content.","The O~(sqrt(alpha T)) rate matches the minimax rate for vanilla graphical bandits, so the contextual structure is asymptotically free in this model.","The only graph parameter that enters the bound is the independence number alpha, not the number of arms or contexts."],"supporting_citations":[{"why":"Supplies the graph inequality (the paper's Lemma 3) that closes the regret bound and the vanilla graphical-bandit minimax rate the result aims to match.","marker":"Alon et al. (2015)"},{"why":"Provides the epoch, snapshot, and paired-time-step schema for estimating observation probabilities despite dependence between contexts and play.","marker":"Schneider & Zimmert (2023)"},{"why":"Proposed the cross-learning contextual bandit with graphical feedback and gave the prior O~(sqrt(min(alpha M T, K T))) bound and an adversarial-context impossibility result.","marker":"Han et al. (2024)"},{"why":"Explicitly listed the stochastic-context O~(sqrt(alpha T)) question as open, setting the target this paper addresses.","marker":"Wen et al. (2024)"},{"why":"Provides high-probability bounds for no-self-loop graphical bandits; the paper reports it could not combine these with its algorithm, exposing the no-self-loop gap.","marker":"Luo et al. (2023)"},{"why":"Supplies the implicit-exploration and high-probability techniques used to stabilize the loss estimator.","marker":"Neu (2015)"}],"fun_headline_variants":["Context-free regret: O~(sqrt(alpha T)) for graphical bandits","Adversarial bandits beat context count via graph structure","Cross-learning with graphs: near-tight bound, but proof gap","Graph feedback removes context dependence in bandit regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof's last step assumes a known graph inequality holds for every strongly observable graph, but the paper's own conclusion says that inequality fails when arms may lack self-loops, so the proof as written covers only graphs whose arms observe themselves.","fun_headline_variants_meta":{"raw":{"variants":["Context-free regret: O~(sqrt(alpha T)) for graphical bandits","Adversarial bandits beat context count via graph structure","Cross-learning with graphs: near-tight bound, but proof gap","Graph feedback removes context dependence in bandit regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000378,"raw_usage":{"total_tokens":2044,"prompt_tokens":1015,"completion_tokens":1029,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":631,"completion_tokens_details":{"reasoning_tokens":958}},"tokens_in":631,"tokens_out":1029,"duration_ms":14927,"temperature":1.0,"reasoning_tokens":958,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T21:53:42.457312+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate the key graph sum, sum over arms of w_i/(w_i + sum of in-neighbor weights), on a strongly observable digraph with no self-loops, such as a complete digraph without loops with a weight vector concentrated on one arm; if any instance violates the claimed O(alpha log(K/(alpha epsilon))) bound, the theorem as stated cannot follow from the paper's final step. Alternatively, run the algorithm on that no-self-loop graph and check whether empirical regret tracks O~(sqrt(alpha T)) or grows with the number of contexts.","supporting_citations":[{"cited_title":"and Zimmert, J","cited_arxiv_id":null,"evidence_quote":"Provides the epoch, snapshot, and paired-time-step schema for estimating observation probabilities despite dependence between contexts and play."}],"review_version":1}