{"id":"2bb02ed1-ee11-4d52-8916-7b248c46c1d1","arxiv_id":"2502.08003","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A cluster-aware multi-agent bandit algorithm achieves O((C/M) log T) regret by aggregating information within clusters and communicating only between clusters, improving on the O(M^2 log T) bound of fully heterogeneous prior work.","lead":"This paper studies cooperative bandit learning where agents sit in clusters that shape both who they can talk to and how similar their rewards are. The authors propose an algorithm whose regret scales with the number of clusters rather than the number of agents, which matters for large distributed systems with natural groupings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Connectivity proof in Theorems 7–8 has an exponent error: the stated edge-probability threshold is too weak by a factorial power, so l-periodic connectivity is not guaranteed and the O((C/M)logT) bound is unsupported as written.","rationale":"The central claim is that under SBM-induced clusters, UCB-SBM attains per-agent regret O((C/M)logT). The mechanism that produces the C/M improvement is cluster-level consensus, which in Theorems 7–8 rests entirely on l-periodic connectivity of the cluster subgraph. I therefore looked for the weakest point in that consensus argument. The reader identified the connectivity assumption as the weakest assumption, which is the right region, but the more precise problem is an internal derivation error in Proposition 20: the proof requires p >= factorial^(1/l), while the theorem states p >= factorial. This is not a disagreement with the community consensus or a missing lower bound; it is a concrete algebraic mismatch inside the proof. The error directly controls whether the advertised relaxed edge-probability assumption is sufficient. Under the stated assumption with l=2 and C=100, the composition graph is essentially always disconnected, so the key event A'_3 cannot hold with the claimed probability. The same defect propagates into Theorem 8 and Corollary 11. I do not think this invalidates the overall approach: replacing the factorial factor by its l-th root repairs the argument and still gives a threshold bounded away from 1, so the correct verdict remains conditional rather than reject. The experimental inconsistency (e.g., Fig. 1a using C=M=10 and p=q=0.5, where no cluster homogeneity exists) is real but secondary to the theoretical claim. My recommendation is to retain a conditional verdict, with the explicit condition that Proposition 20's threshold be corrected and Theorems 7–8 restated accordingly.","tokens_in":51005,"tokens_out":13954,"duration_ms":114548,"concrete_test":"Analytically re-derive Proposition 20 for l=2, C=100. Let the cluster-level edge probability p be exactly (C-3)!/(C-2)! * sqrt(3/4) = (1/98)*sqrt(3/4) ≈ 0.00884, the value allowed by Theorem 7 after Lemma 6. The expected number of length-2 paths between a fixed cluster pair is (C-2)p^2 ≈ 0.0076, so the composition graph has expected degree ≈ 0.76 and is disconnected with overwhelming probability. A Monte-Carlo simulation over 1000 independent draws of two consecutive G^C_t graphs will confirm that the composition is connected in essentially none of the trials, contradicting the l-periodic connectivity claim in Proposition 20. This settles that the stated threshold is insufficient; equivalently, the proof should use [(C-l-1)!/(C-2)!]^(1/l) rather than (C-l-1)!/(C-2)!.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The decisive step is Proposition 20 in Appendix E.5, which is used by Theorems 7 and 8 (and hence by Corollary 11). To prove that the cluster subgraph is l-periodically connected, the proof needs the composition edge probability p_l = P(edge between two clusters in the composition of l consecutive graphs) to be large. The proof writes p_l = A p^l, with A = (C-2)!/(C-l-1)! and p the cluster-level edge probability, and then requires A p^l >= 3/4. This implies p >= A^{-1/l}(3/4)^{1/l} = [(C-l-1)!/(C-2)!]^{1/l}(3/4)^{1/l}. However, the assumption in Theorem 7, after applying Lemma 6, gives only p >= [(C-l-1)!/(C-2)!](3/4)^{1/l}; the factorial is not raised to the power 1/l. Substituting yields A p^l >= [(C-l-1)!/(C-2)!]^{l-1}(3/4), which is <= 3/4 and tends to 0 as C grows. For l=2 and C=100, this is 3/(4*98) ≈ 0.0076, whereas the proof needs ≥ 0.75. The expected degree in the composition graph is then (C-1)A p^l ≈ 0.76, far below the (C-1)/2 = 49.5 threshold used in the Chebyshev argument, so the graph is not connected with high probability. The same factorial-power issue appears in the within-cluster part of Theorem 8. Thus the relaxed-assumption version of the O((C/M)logT) claim is not established as stated. The fix is likely to replace the factorial factor by its l-th root, which would preserve a threshold bounded away from 1; this is a proof repair, not a rejection of the algorithmic idea.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a heterogeneous multi-agent multi-armed bandit model on stochastic block models, where cluster structure determines both graph edge probabilities and reward means. It proposes UCB-SBM, an algorithm with a burn-in period and cluster-level information aggregation, and claims instance-dependent regret upper bounds of order O((C/M) log T) for known and unknown cluster settings, with edge-probability assumptions bounded away from 1. The main theoretical results are Theorem 7 and Theorem 8 (and the unknown-cluster extension Corollary 11), supported by a consensus/connectivity analysis of cluster-level subgraphs. Numerical experiments compare the algorithm against several baselines.","tokens_in":51442,"tokens_out":9785,"duration_ms":85914,"significance":"If the theoretical claims are correct, the paper makes a useful conceptual advance: it unifies homogeneous and fully heterogeneous cooperative bandits, exposes the degree of heterogeneity through the C/M factor, and relaxes the near-1 edge-probability assumptions of prior work. The algorithmic idea of aggregating at the cluster level is natural and the experimental section suggests clear practical gains. The paper is not self-contained, however, and the central relaxed-assumption theorem currently has a load-bearing proof error, so the main claims are not yet established as written.","major_comments":[{"comment":"Several load-bearing steps are asserted rather than proved. Theorem 2 says the proof parallels Theorem 2 of [58] and lists Propositions 1–6 as following from [58]; Lemma 16 cites Lemma 3 of [64]; Lemmas 18 and 20 cite Lemma 10 of [64] without stating the referenced result or its assumptions. Because the graph model here is an SBM rather than an Erdős–Rényi graph, the reduction to [58] needs an explicit verification that the connectivity, transmission-gap, unbiasedness, and concentration propositions remain valid under agent-dependent edge probabilities. Please include the adapted proofs, or state precisely which statements in [58]/[64] are reused and why they apply to the present setting.","section":"Sections 6.2 and Appendix E.2–E.6"}],"minor_comments":[{"comment":"The heading \"Burn-in Peirod\" contains a typo; it should read \"Burn-in Period.\"","section":"Appendix A.1"},{"comment":"The name \"Erdos-Renyi\" should be typeset as \"Erdős–Rényi.\"","section":"Throughout"},{"comment":"The phrase \"the lower bound on the edge probability in our case can be at most ...\" is confusing: the requirement is an upper bound on the minimal allowed edge probability, not a lower bound on p. Please rephrase.","section":"Section 1.1"},{"comment":"Table 1 contains broken entries, including \"N /A\" in the C=1 row and unclear superscript/footnote symbols; the table should be regenerated for readability.","section":"Table 1"},{"comment":"The notation |c_M| is used interchangeably with c_M and |c_m|; please define explicitly that c_M = M/C and |c_m| is the size of cluster m, and use the notations consistently.","section":"Theorem 8"},{"comment":"In the discussion of Fig. 1d, the text states that UCB-SBM and DrFed-UCB \"achieve the same regret\" when C=M=10; since the paper's headline claim is an improvement, please clarify whether this is an expected consistency or a limitation of the algorithm.","section":"Section 8"}],"recommendation":"major_revision","confidential_remarks":"The manuscript leans heavily on the first author's prior work [58] and on [64]. This is not circular, but it means the present paper cannot currently be evaluated as a self-contained contribution. The exponent error in Proposition 20 is the decisive technical problem; it is localized and appears repairable by changing the factorial power in the assumptions. The missing lower bound also makes the \"optimal\" wording unsafe. If the authors repair the connectivity threshold, correct the summation in Theorem 8's proof, and either add a lower bound or temper the optimality claim, the paper would be a solid contribution for this venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the first MA-MAB paper I've seen that ties reward heterogeneity to SBM cluster structure, and the C/M dependency in the regret bound is a genuinely useful refinement of the heterogeneous setting. I'd send it to review, but only after the authors fix a specific gap in the proof of Theorems 7 and 8.\n\nWhat's new: the model is natural and well motivated. Edge probabilities and reward means both follow the same cluster partition, so you interpolate between homogeneous and fully heterogeneous. The Rule-2 cluster-level aggregation is a real algorithmic idea, and the resulting bound O((C/M) log T) is a clear improvement over the M^2 log T of [58]. The unknown-cluster extension is a nice plug-in.\n\nWhere it's soft: the stress-test note is right. In Proposition 20, the proof needs the composition edge probability A p^l to be at least 3/4, with A = (C-2)!/(C-l-1)!. But the assumed lower bound on p is F (3/4)^{1/l} where F = (C-l-1)!/(C-2)!, not F^{1/l}(3/4)^{1/l}. Substituting gives A p^l <= F^{l-1}(3/4), which goes to 0 with C. So l-periodic connectivity is not established under the stated assumption. This is load-bearing for Theorems 7, 8, and Corollary 11. The fix is to raise the factorial to the power 1/l; then the threshold stays bounded away from 1. This is a repair, not a rewrite, but as written the main relaxed-assumption claim is unsupported.\n\nTwo more concerns, both secondary. The word 'optimal' in the abstract is not justified: no matching lower bound is given. And the proof leans heavily on [58] and [64] by reference; for the flagship result, you'd want the key argument self-contained.\n\nThere's also a small experimental inconsistency: the synthetic benchmark in Fig 1a sets C=M=10 and p=q=0.5, which is the fully heterogeneous uniform-Erdos-Renyi case rather than an SBM regime; and the abstract's 68.69% improvement appears as 68.79% in the text. Minor, but it should be cleaned up.\n\nBottom line: the problem formulation and algorithmic direction are solid and worth the field's attention. The theoretical claim needs the fix above before it is credible. A serious referee should engage; recommend major revision.","headline":"Fresh problem formulation with a plausible C/M regret improvement, but the main relaxed-edge-probability theorem has a correctable exponent error in its connectivity proof.","tokens_in":51989,"tokens_out":3756,"would_cite":true,"duration_ms":31389,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62L05","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"A cooperative bandit algorithm on stochastic block models achieves instance-dependent regret of order (C/M) log T, where C is the number of clusters and M the number of agents.","keywords":["multi-agent multi-armed bandits","stochastic block models","heterogeneous rewards","regret bounds","random communication graphs","consensus","cluster detection","UCB"],"falsifier":"Run UCB-SBM in a two-cluster system with M=40 agents, K=2 arms, sub-Gaussian rewards with known gaps Δ, and choose the inter-cluster edge probability q below the Theorem 8 lower bound while keeping the within-cluster probability high enough to make each cluster internally connected. If the measured per-agent regret still behaves as (C/M)·(4C₁ log T/Δ²), the connectivity assumption is sufficient but not necessary; if the regret jumps to order M log T, the assumption is load-bearing.","tokens_in":50820,"feed_emoji":"🎰","tokens_out":5603,"duration_ms":48894,"temperature":0.7,"pith_summary":"This paper studies multi-agent multi-armed bandits in which both the communication graph and the reward distributions inherit a cluster structure: agents within a cluster share the same reward means and denser edges, while agents in different clusters differ. The authors propose an algorithm, UCB-SBM, that aggregates rewards at the cluster level and exchanges only cluster-level statistics, and they prove that its regret is O((C/M) log T), where C is the number of clusters and M the number of agents, under sub-Gaussian rewards. This is the first bound to exhibit dependence on the degree of heterogeneity, C/M, interpolating between the fully homogeneous case (C=1) and the fully heterogeneous case (C=M), and it improves on the prior O($M^{2}$ log T) bound while requiring much weaker lower bounds on edge probabilities. The same guarantee holds when the cluster assignment is unknown, at the price of a cluster-detection step and an extra additive O(M) burn-in cost.","feed_headline":"Cluster structure cuts bandit regret to O(C/M log T)","feed_subtitle":"UCB-SBM shows regret depends on the number of clusters, not agents, and relaxes edge-probability assumptions.","key_machinery":"The load-bearing object is the cluster-level subgraph G^C_t, whose vertices are clusters and whose edges indicate whether any agent pair across two clusters communicated at time t. Lemma 6 shows the cluster-edge probability satisfies p(c_m,c_n) ≥ (1-1/e) min{1, (M²/C²)p(m,n)}, which makes the cluster graph much denser than the original graph; this is what lets the consensus argument run under edge probabilities bounded away from 1. Information flows through a three-layer estimator: local means computed at the burn-in, cluster means obtained by averaging within a cluster, and a global estimator formed by a weighted combination of cluster means from other clusters together with the local cluster information. The l-periodic connectivity condition, defined via composition of l consecutive graphs, guarantees that within l time steps every cluster hears from every other, and the consensus lemmas turn this into a bound on the realized sample counts.","core_discovery":"The paper claims that the system-wide per-agent regret of a cooperative multi-armed bandit on a stochastic block model can be made to grow as O((C/M) log T) rather than scaling with the number of agents M. Concretely, Theorem 8 states that with probability at least 1-7ε, the conditional expected regret is at most L plus a sum over suboptimal arms of Δ_i times the maximum of (C/M)(4C₁ log T/Δ_i²) and 2(K²+MK), plus additive constants; the coefficient C/M is exactly the degree of heterogeneity h = C/M. The authors support this with an algorithm that builds three layers of estimators — local, cluster, and global — and that only requires the cluster-level graph and the within-cluster subgraph to be l-periodically connected with high probability, a condition met when inter- and intra-cluster edge probabilities exceed factorial lower bounds that stay strictly below 1 as T grows.","pith_inferences":["The C/M coefficient suggests a direct statistical economy of scale: if cluster sizes are balanced, doubling the number of agents within each cluster while keeping C fixed halves the per-agent regret, so homogeneity is a resource that substitutes for exploration.","Because the analysis only needs l-periodic connectivity rather than instantaneous connectivity, the proof plausibly carries over to other random graph processes with similar mixing properties, such as temporally correlated stochastic block models.","For unbalanced clusters the paper suggests using the minimum cluster size; an alternative weighting by actual cluster sizes would yield a regret bound depending on the harmonic mean of cluster sizes, which the paper does not analyze.","The experimental finding that regret first rises then falls with p and q suggests an intermediate regime where confidence terms and connectivity trade off; formalizing the dependence of C₁ on p and q is a natural next step."],"forward_implications":["Per-agent regret coefficient becomes C/M, so in large systems with few clusters the log T term is essentially independent of the number of agents; total regret grows with C, not M.","Setting C=1 recovers the homogeneous case with O(log T / M) per-agent regret, and C=M recovers the fully heterogeneous setting, so the bound continuously interpolates between the two regimes.","The edge-probability lower bounds are strictly below 1 even as T→∞, unlike prior work whose requirement approaches 1; in particular the inter-cluster bound involves e/(e-1) times (C²/M²) times a factorial decay factor.","With unknown clusters, the same O((C/M) log T) regret holds with probability 1 - 7ε - 1/poly(M), provided the burn-in is extended by O(M) steps and cluster detection succeeds under a signal-to-noise condition.","Choosing the periodic-connectivity window l optimally between 2 and C-1 gives the weakest edge-probability assumption; Theorem 8 extends this to intra-cluster edges, so even within clusters the graph need not be complete."],"supporting_citations":[{"why":"Provides the fully-heterogeneous baseline algorithm and the O(M² log T) bound that UCB-SBM improves on, plus the structure of the burn-in period.","marker":"[58]"},{"why":"Supplies the consensus and transmission-gap lemmas that bound information delay under periodic connectivity and are reused as Lemma 16 and Lemma 18.","marker":"[64]"},{"why":"Gives the iterative clustering algorithm used to recover unknown cluster assignments with high-probability exact recovery.","marker":"[12]"},{"why":"Provides the cooperative UCB analysis for suboptimal-arm pull counts that the homogeneous warm-up theorem rests on.","marker":"[54]"},{"why":"Defines the homogeneous cooperative setting with near-optimal individual regret that the paper treats as the C=1 extreme.","marker":"[53]"}],"fun_headline_variants":["Bandit regret scales with cluster count, not agent count","Heterogeneous multi-agent bandits: O(C/M log T) regret","Cluster structure in SBM cuts multi-agent bandit regret","New bound: per-agent regret depends on clusters, not agents"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the bound to hold, the random graph must stay l-periodically connected with high probability at every time, meaning the edge probabilities both within and across clusters must exceed the factorial lower bounds stated in Theorem 8 and every cluster must contain enough agents for those expressions to be defined; if the graph is too sparse, information cannot propagate and the O((C/M) log T) regret no longer follows.","fun_headline_variants_meta":{"raw":{"variants":["Bandit regret scales with cluster count, not agent count","Heterogeneous multi-agent bandits: O(C/M log T) regret","Cluster structure in SBM cuts multi-agent bandit regret","New bound: per-agent regret depends on clusters, not agents"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000224,"raw_usage":{"total_tokens":1506,"prompt_tokens":1035,"completion_tokens":471,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":651,"completion_tokens_details":{"reasoning_tokens":399}},"tokens_in":651,"tokens_out":471,"duration_ms":5305,"temperature":1.0,"reasoning_tokens":399,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:10:37.915893+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run UCB-SBM in a two-cluster system with M=40 agents, K=2 arms, sub-Gaussian rewards with known gaps Δ, and choose the inter-cluster edge probability q below the Theorem 8 lower bound while keeping the within-cluster probability high enough to make each cluster internally connected. If the measured per-agent regret still behaves as (C/M)·(4C₁ log T/Δ²), the connectivity assumption is sufficient but not necessary; if the regret jumps to order M log T, the assumption is load-bearing.","supporting_citations":[{"cited_title":"Xu and D","cited_arxiv_id":null,"evidence_quote":"Provides the fully-heterogeneous baseline algorithm and the O(M² log T) bound that UCB-SBM improves on, plus the structure of the burn-in period."},{"cited_title":"Zhu and J","cited_arxiv_id":null,"evidence_quote":"Supplies the consensus and transmission-gap lemmas that bound information delay under periodic connectivity and are reused as Lemma 16 and Lemma 18."},{"cited_title":"Braun, H","cited_arxiv_id":null,"evidence_quote":"Gives the iterative clustering algorithm used to recover unknown cluster assignments with high-probability exact recovery."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the cooperative UCB analysis for suboptimal-arm pull counts that the homogeneous warm-up theorem rests on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the homogeneous cooperative setting with near-optimal individual regret that the paper treats as the C=1 extreme."}],"review_version":1}