{"id":"475d92d4-76b3-48c4-8eff-4ced9cb307cf","arxiv_id":"2501.19239","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Claims O(M^(1-1/alpha) log T) and O(M log T) regret bounds for multi-agent bandits under heavy-tailed rewards and sparse heavy-tailed communication graphs.","lead":"This paper studies cooperative multi-agent bandits where both the communication graph and the reward distributions are heavy-tailed, and it claims regret bounds that are sublinear in the number of clients for homogeneous rewards. The analysis introduces hub-based variance reduction and new information delay bounds for sparse graphs, but the proofs contain algorithm modifications and estimator definitions that are not properly specified.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Heterogeneous estimator weights P'_t become negative for all M beyond a small constant, so Lemma C.5's concentration proof and Theorem 5.1's O(M log T) bound are unsupported.","rationale":"The reader's weakest_assumption was Assumption 2, but I do not think that is the most load-bearing issue: Assumption 2 is an explicit modeling condition excluding near-zero weights, and the graph lemmas use it in a standard way. The more serious problem is internal to the heterogeneous algorithm: the weights in Rule 2 are not nonnegative for large M, and the concentration proof in Appendix C.4 (Lemma C.5) depends on treating them as nonnegative probabilities. The negative-weight issue is not a disagreement with consensus or a matter of parameter tuning; it is a checkable algebraic inconsistency in the submitted formulas. The paper's abstract advertises an O(M log T) heterogeneous regret bound, so this concern directly attacks a central claim. I also note the homogeneous proofs contain algorithmic mismatches (the modified transmission in Theorem 4.2's proof is absent from Algorithm 1), which reinforce the rejection but are not the single test I would run first. The reader's rationale listed the negative weights as one of its reasons, though its formal 'weakest_assumption' field selected Assumption 2; hence my agreement is partial. The final verdict remains REJECT, so no change to the reader's verdict.","tokens_in":35588,"tokens_out":17243,"duration_ms":149034,"concrete_test":"Fix ε=1 (so N=13) and M=100, K=2. Step 1: evaluate P'_t=(13-100)/(13·100)=-87/1300<0 and d_{m,t}=1/13. Step 2: test Lemma C.5's induction at t=L+1 with all \\tilde μ_{i,j} errors equal to +B and all \\hat μ_{i,j} errors equal to -B; the resulting global-estimator error is M|P'_t-d_{m,t}|B=(100·187/1300)B≈14.4B, whereas the claimed concentration bound in Lemma C.5 has a coefficient independent of M (≈2 when ε=1). Step 3: if the bound is amended to include this M-dependent factor, recompute the regret bound in Theorem 5.1; the extra factor replaces O(M log T) with O(M^2 log T), contradicting the abstract. These three evaluations settle whether the negative weights are a typo or a genuine break in the argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Rule 2 defines P'_t = (N - M^{2/(1+ε)})/(M N^{2/(1+ε)}) with N = (12^{1/(1+ε)})^{(1+ε)/ε}+1, a constant independent of M (for ε=1, N=13). For every M > N^{(1+ε)/2}, the numerator is negative, so P'_t < 0; e.g., ε=1 gives P'_t=(13-M)/(13M)<0 for M>13. The global estimator in Rule 2, \\tilde μ_m^i(t+1)=∑_{j=1}^M P'_t \\tilde μ_{i,j}(t_{m,j}) + d_{m,t}∑_j \\hat μ_{i,j}(t_{m,j}) with d_{m,t}=1/M - P'_t, is then not a convex combination of the incoming estimators. Lemma C.5's induction step moves absolute values inside the sum and uses the displayed coefficients (N-M^{2/(1+ε)})/N^{2/(1+ε)} and 1-(N-M^{2/(1+ε)})/N^{2/(1+ε)} as if they were probabilities or at least nonnegative. For M>N^{(1+ε)/2}, that coefficient is negative, and the chain bounding by 2ρ^{1/(1+ε)}(2N c log t / min_m n_{m,i}(t))^{ε/(1+ε)} is invalid. The worst-case absolute error can grow with M (e.g., ε=1, M=100 gives M|P'_t|+M|d_{m,t}|≈14.4 times the per-estimator error), not a constant independent of M. Theorem 5.1's Cases 2 and 3 bounds use exactly this concentration inequality, so the advertised heterogeneous regret O(M log T) does not follow from the submitted proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies decentralized cooperative multi-agent multi-armed bandits under two simultaneous heavy-tailed sources: rewards with uniformly bounded (1+ε)-th central moments and sparse rank-1 inhomogeneous random graphs with power-law (regularly varying) attraction weights. For homogeneous rewards it proposes HT-HMUCB and claims a regret bound of order O(M^{1-1/α} log T); for heterogeneous rewards it proposes HT-HTUCB and claims a regret bound of order O(M log T). The analysis is built on graph-theoretic lemmas about hub sizes and information delay, followed by median-of-means based UCB concentration arguments.","tokens_in":35985,"tokens_out":9638,"duration_ms":92698,"significance":"The problem formulation is timely and the graph-theoretic part is the strongest section of the manuscript: the branching-process coupling in Lemma 3.3 and the extreme-value arguments in Lemmas 3.1 and 3.2 are substantive and appear largely sound. The paper is also transparent about its assumptions, notably the uniform lower bound in Assumption 2. However, the two central regret theorems are not proved as written. Theorem 4.2's proof relies on a hub-pausing modification that does not appear in Algorithm 1, and the heterogeneous estimator in Rule 2 has negative weights for moderate M, invalidating Lemma C.5 and hence Theorem 5.1. Because these are load-bearing for the advertised improvements over prior work, the manuscript cannot be accepted in its current form.","major_comments":[{"comment":"The proof of Theorem 4.2 introduces a modification that is absent from Algorithm 1 and Rule 1: it states that 'when S_t^0 < a ... the transmission between the hub and the non-hub is paused,' and then uses rwi_t ≥ a·n_{m,i}(τ) with a = M^{1/α-ζ}. No such pause appears in the pseudocode, and the non-center update in Rule 1 always uses the hub estimator at max_{j∈S0} t_{m,j}. Moreover, a is later identified with |S0|, but S0 in Lemma 3.1 is the deterministic hub neighborhood of size M^{2-α-ζ}, not the time-varying threshold M^{1/α-ζ}. Since the O(M^{1-1/α} log T) bound depends on this effective hub sample count, Theorem 4.2 is not established for the algorithm as stated.","section":"Appendix C.2, proof of Theorem 4.2"},{"comment":"The heterogeneous estimator is not a convex combination for typical values of M. Rule 2 defines P'_t = (N - M^{2/(1+ε)})/(M N^{2/(1+ε)}) with N = (12^{1/(1+ε)})^{(1+ε)/ε} + 1, a constant depending only on ε. Whenever M > N^{(1+ε)/2}, the numerator is negative; for example with ε=1, P'_t = (13-M)/(13M), which is negative for every M > 13. Lemma C.5's induction step moves absolute values inside the sum and treats the displayed coefficients as nonnegative probabilities, but under negative weights the worst-case error can grow with M (e.g., for ε=1, M=100 the total weight magnitude is roughly 14.4 times the per-estimator error). Consequently the concentration inequality that Theorem 5.1 uses in Cases 2 and 3 is not proved, and the claimed O(M log T) heterogeneous regret bound does not follow from the submitted proof.","section":"Algorithm 2, Rule 2; Lemma C.5; Theorem 5.1"},{"comment":"The proof of Lemma 3.3 defines q_h = 1 - ρ_h/(4+2ρ_h)·(1-exp(ρ_h)), which is larger than 1 because exp(ρ_h) > 1, contradicting the claimed q_h ∈ (0,1). The preceding Lemma B.7 provides a probability with factor (1-exp(-ρ_h)), so this appears to be a sign typo; as written, however, the geometric tail argument in Lemma 3.3 fails. Since Lemma 3.3 underpins the information-delay bounds used in every subsequent regret theorem, this must be corrected.","section":"Appendix B.2, proof of Lemma 3.3"}],"minor_comments":[{"comment":"The statement says 'given ζ∈(0,2-α)', but for α > 2 this interval is empty; the relevant range from Lemma 3.2 is ζ∈(0,1-1/α).","section":"Theorem 4.2"},{"comment":"The event A3_{ζ,δ} is written as {^i(m) ≠ ^i for some m∈[M]}, which is a failure event rather than a success event; presumably it should be the complement, and the success event should be that all clients identify the same hub.","section":"Theorem 4.1, event definitions"},{"comment":"There is a typo in 'non-emtpy' in the lemma statement, and the proof of Lemma 3.3 uses the notation t_M in two different senses (the infimum in (B.25) and a concrete O(log M) time), which makes the argument harder to follow.","section":"Lemma 3.3 statement"},{"comment":"The update rule in Algorithm 2 and the proof of Lemma C.5 use inconsistent timing notation: Rule 2 writes t_{m,j} everywhere, while the proof splits the second sum into terms with t and t_{m,j}; these should be reconciled.","section":"Rule 2 and Lemma C.5 notation"},{"comment":"The paper should clarify how essential Assumption 2 is to the O((log M)^2) delay result; without a uniform lower bound on h, the claimed 'fully heavy-tailed' graph setting could include clients with vanishing connection probability, for which Lemma 3.3 would not hold.","section":"Assumption 2 and scope"}],"recommendation":"reject","confidential_remarks":"The graph-theoretic lemmas are promising and could form the basis of a solid paper, but the two main regret theorems are not proved as written. The negative-weight issue in Rule 2 is a fundamental flaw in the proposed algorithm, not merely a missing proof detail, and the Theorem 4.2 proof departs from the stated algorithm. A substantially revised version—with a corrected heterogeneous estimator and a proof of Theorem 4.2 that matches Algorithm 1—might be worth considering, but the current submission does not meet the bar for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me give you my take on arXiv:2501.19239. The headline is that this paper attacks a real gap and has one genuinely nice idea, but the main theorems are not proven as written. I read the full text and agree with your concerns, especially the heterogeneous part.\n\nWhat is actually new: the combination of heavy-tailed rewards and sparse, heavy-tailed random graphs in cooperative MA-MAB. The hub-structure exploitation — using the heavy tail to get a large deterministic hub — is a clever idea, and the information delay bound for rank-1 inhomogeneous random graphs (Lemma 3.3 with the branching-process coupling in B.2) looks like a real contribution. The graph lemmas in Section 3 appear sound to me; the hub-size bound in Lemma 3.2 is plausible. The paper is also honest about Assumption 2 (the uniform lower bound on h) being needed; it is restrictive but not hidden.\n\nThe soft spots are serious. The heterogeneous estimator in Rule 2 defines P'_t = (N - M^{2/(1+ε)})/(M N^{2/(1+ε)}). Since N is a constant independent of M, for all M beyond a small constant (e.g., M > 13 for ε = 1) the numerator is negative, so P'_t < 0. The global estimator is then not a convex combination, and Lemma C.5's induction breaks exactly where it moves absolute values through the weighted sum. Theorem 5.1's advertised O(M log T) regret depends on that lemma, so that result is unsupported. This is a load-bearing flaw, not a minor typo.\n\nThe second gap is in Theorem 4.2. The proof introduces a modification: when the hub size is small, hub communication is paused. That modification is not in Algorithm 1, and the analysis relies on it to get the improved hub denominator. Without it, the claimed O(M^{1-1/α+ζ}) bound does not follow. The α ∈ (1,2) result in Theorem 4.1 has a plausible proof sketch, though with the usual case-splitting uncarefulness. There are also many typos and garbled equations, but that is secondary.\n\nWho is this for? Researchers working on decentralized multi-agent bandits, especially communication-efficient or heavy-tailed network models. The graph-side results and the hub idea are worth engaging with. But the current form is not close to being right.\n\nMy recommendation: reject in current form, but do not abandon the direction. I would still send a future revision to referees. The flaws are identifiable and possibly repairable; if the authors fix the estimator weights and align the algorithm with the proof, this could become a solid paper.","headline":"A genuinely new setting, but two load-bearing proof gaps; the heterogeneous regret bound is definitely broken as written, while the graph-side lemmas are worth salvaging.","tokens_in":36473,"tokens_out":3594,"would_cite":false,"duration_ms":31129,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","60G70","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Cooperative multi-agent bandits remain tractable when rewards have only $(1+\\epsilon)$-th moments and the communication graph is a sparse heavy-tailed random graph.","keywords":["multi-agent multi-armed bandits","heavy-tailed rewards","heavy-tailed random graphs","heterogeneous rewards","regret bounds","median-of-means","UCB","power-law degree distribution"],"falsifier":"Simulate $M$ clients with heavy-tailed rewards and sparse rank-1 random graphs, and let a positive fraction of clients have attraction weights drawn from a distribution whose lower tail reaches zero, violating the uniform lower bound; if the measured worst-case time for a message to reach all clients grows faster than a polynomial in $\\log M$, or if homogeneous regret becomes linear in $M$, the central claims are refuted.","tokens_in":35381,"feed_emoji":"🌐","tokens_out":9472,"duration_ms":82971,"temperature":0.7,"pith_summary":"This paper tries to establish that cooperative multi-agent multi-armed bandits remain tractable when both sides are heavy-tailed: rewards may have infinite variance, and the communication graph is redrawn each round from a sparse random-graph model whose degree distribution follows a power law with index $\\alpha>1$. It claims regret bounds of order (almost) $O(M^{1-1/\\alpha}\\log T)$ in the homogeneous-reward setting and $O(M\\log T)$ in the heterogeneous setting, both sublinear in the number of clients. These improve on prior work that required time-invariant connected graphs or dense light-tailed Erdős–Rényi dynamics, and they hold under only $O(M)$ total communication per round. The algorithms are UCB-style: homogeneous clients identify a hub and route aggregated median-of-means estimates through it, while heterogeneous clients exchange neighbor information and fall back to random sampling when synchronisation fails.","feed_headline":"Heavy-tailed sparse graphs still allow sublinear bandit regret","feed_subtitle":"Regret stays $O(M^{1-1/\\alpha} \\log T)$ for identical clients and $O(M\\log T)$ when rewards differ.","key_machinery":"The central object is the rank-1 inhomogeneous random graph with kernel $P(u,v)=\\min\\{1,uv/(\\theta M)\\}$ and regularly varying attraction weights $h_i$, a model that produces hubs. The argument is carried by three pieces: extreme-value-theory bounds showing that the hub is large and reappears within $O(\\log T)$ steps; a branching-process coupling that bounds information delay over the sparse graph by $O((\\log M)^2)$ time with probability at least $1-M^{-\\gamma}$; and a median-of-means concentration inequality for rewards with only $(1+\\epsilon)$-th moments. The hub estimator aggregates rewards across hub members, replacing the per-client sample count $n_{m,i}(t)$ in the UCB bonus by the hub size times $n_{m,i}(t)$, which is what converts a baseline $O(M\\log T)$ into the sublinear $O(M^{1-1/\\alpha}\\log T)$ regret.","core_discovery":"On its own terms, the paper's central discovery is that heavy-tailed degree heterogeneity creates a small set of hub clients that can act as information concentrators, and that this structure suffices for near-optimal regret on sparse graphs. It proves that under rank-1 inhomogeneous random graphs with regularly varying attraction weights of index $\\alpha>1$, the highest-degree client at time one is, with overwhelming probability, linked at all times to on the order of $M^{1/\\alpha}$ clients; these hubs aggregate rewards, and a median-of-means estimator run on the hub gives per-client sample complexity that scales with the reciprocal hub size. Summed over $M$ clients this yields $O(M^{1-1/\\alpha+\\zeta}\\log T)$ regret in the homogeneous setting, with $\\zeta$ arbitrarily small. In the heterogeneous setting the paper drops the hub construction and instead derives an $O((\\log M)^2)$ information-delay bound for sparse graphs via a branching-process coupling, then shows that a UCB index built from neighbour-aggregated heavy-tailed estimators, with random sampling when estimators desynchronize, incurs $O(M\\log T)$ regret. The heterogeneous theorem does not rely on the heavy-tail assumption on the graph, so it also covers light-tailed sparse graphs.","pith_inferences":["Testable extension: drop the uniform lower bound on attraction weights and allow a positive fraction of clients to have vanishing connectivity; the paper's delay and regret bounds should degrade, and locating where they break would draw the exact boundary of the result.","Extension: non-stationary graph weights would make the time-one hub stale, and re-running hub identification periodically would plausibly preserve the homogeneous bound at an extra $O((\\log M)^2)$ cost per re-run, which the paper does not analyze.","Extension: the heterogeneous estimator uses a weighted average of local estimators, and truncated-mean estimators would likely give the same bounds with smaller constants, but the paper does not study this alternative.","Extension: the branching-process delay bound appears to capture the true cost of sparsity, and a matching lower bound on delay under the same assumptions would show that routing alone cannot improve the heterogeneous $O(M\\log T)$ rate."],"forward_implications":["If the homogeneous bound is correct, a sparse network with total degree $O(M)$ can match the regret of much denser communication, so sparsity is not paid for in regret.","Because the slack $\\zeta$ can be taken arbitrarily close to zero, the regret exponent approaches $M^{1-1/\\alpha}\\log T$, interpolating between nearly $O(\\log T)$ for very heavy hubs as $\\alpha\\to 1^+$ and $O(M\\log T)$ as $\\alpha\\to\\infty$.","In the heterogeneous setting the $O(M\\log T)$ bound holds for any sparse random graph satisfying a uniform lower bound on attraction weights, including degree distributions that are light-tailed.","The $O((\\log M)^2)$ information-delay lemma implies that every client receives any broadcast message quickly even though the expected degree is $O(1)$.","Hub identification runs in $O((\\log M)^2)$ rounds and avoids the clique-search procedure used in earlier heavy-tailed cooperative algorithms."],"supporting_citations":[{"why":"Supplies the median-of-means concentration inequality (its Lemma 2) used to build estimators under rewards with only $(1+\\epsilon)$-th moments.","marker":"[4]"},{"why":"Baseline for cooperative heavy-tailed homogeneous bandits; the paper improves on its regret and removes its time-invariant connected graph and clique-search assumptions.","marker":"[10]"},{"why":"Establishes decentralized heterogeneous MA-MAB on Erdős–Rényi graphs; the paper extends this baseline to sparse heavy-tailed graphs and heavy-tailed rewards.","marker":"[26]"},{"why":"Introduces the class of correlated random networks with hidden variables, the origin of the rank-1 model used in the graph kernel.","marker":"[3]"},{"why":"Provides the rank-1 random graph model with given expected degrees used in equation (2.1).","marker":"[5]"},{"why":"Source for regular variation and Potter bounds used in the extreme-value arguments controlling the hub size.","marker":"[17]"},{"why":"Supplies the branching-process theorem used to bound information delay over sparse graphs.","marker":"[11]"},{"why":"Existing distributed MAB under connected or periodically connected graphs and sub-Gaussian rewards; the paper contrasts its weaker assumptions against this line.","marker":"[30]"}],"fun_headline_variants":["Heavy-tailed graphs turn hubs into information boosters for bandits","Sparse heavy-tailed networks still permit sublinear multi-agent regret","Hub clients beat heavy tails in multi-armed bandits","Heavy-tailed rewards and graphs: sublinear regret via hubs","Multi-agent bandits tame heavy tails with hub-based estimators"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every client's attraction weight is at least some fixed positive constant, so no client is effectively cut off from the network forever; without that, the $O((\\log M)^2)$ information-delay bound and both regret theorems lose their footing.","fun_headline_variants_meta":{"raw":{"variants":["Heavy-tailed graphs turn hubs into information boosters for bandits","Sparse heavy-tailed networks still permit sublinear multi-agent regret","Hub clients beat heavy tails in multi-armed bandits","Heavy-tailed rewards and graphs: sublinear regret via hubs","Multi-agent bandits tame heavy tails with hub-based estimators"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000566,"raw_usage":{"total_tokens":2725,"prompt_tokens":1033,"completion_tokens":1692,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":649,"completion_tokens_details":{"reasoning_tokens":1607}},"tokens_in":649,"tokens_out":1692,"duration_ms":10595,"temperature":1.0,"reasoning_tokens":1607,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T20:51:03.967959+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate $M$ clients with heavy-tailed rewards and sparse rank-1 random graphs, and let a positive fraction of clients have attraction weights drawn from a distribution whose lower tail reaches zero, violating the uniform lower bound; if the measured worst-case time for a message to reach all clients grows faster than a polynomial in $\\log M$, or if homogeneous regret becomes linear in $M$, the central claims are refuted.","supporting_citations":[{"cited_title":"Bubeck, N","cited_arxiv_id":null,"evidence_quote":"Supplies the median-of-means concentration inequality (its Lemma 2) used to build estimators under rewards with only $(1+\\epsilon)$-th moments."},{"cited_title":"Dubey and A","cited_arxiv_id":null,"evidence_quote":"Baseline for cooperative heavy-tailed homogeneous bandits; the paper improves on its regret and removes its time-invariant connected graph and clique-search assumptions."},{"cited_title":"Xu and D","cited_arxiv_id":null,"evidence_quote":"Establishes decentralized heterogeneous MA-MAB on Erdős–Rényi graphs; the paper extends this baseline to sparse heavy-tailed graphs and heavy-tailed rewards."},{"cited_title":"Bogun´ a and R","cited_arxiv_id":null,"evidence_quote":"Introduces the class of correlated random networks with hidden variables, the origin of the rank-1 model used in the graph kernel."},{"cited_title":"Chung and L","cited_arxiv_id":null,"evidence_quote":"Provides the rank-1 random graph model with given expected degrees used in equation (2.1)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source for regular variation and Potter bounds used in the extreme-value arguments controlling the hub size."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the branching-process theorem used to bound information delay over sparse graphs."},{"cited_title":"Zhu and J","cited_arxiv_id":null,"evidence_quote":"Existing distributed MAB under connected or periodically connected graphs and sub-Gaussian rewards; the paper contrasts its weaker assumptions against this line."}],"review_version":1}