{"id":"93e8ac75-a26e-4910-a606-e48bb34b49b8","arxiv_id":"2411.08167","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"DRAA is a fully distributed, corruption-robust algorithm for heterogeneous multi-agent bandits with regret O((L/Lmin)C + log T * K/Delta_min).","lead":"This paper designs a distributed algorithm, DRAA, for multiple agents learning which options are best when each agent sees only a subset of options and part of the reward feedback is corrupted by an adversary. Its regret bound grows only with the corruption budget C and the standard no-corruption regret, and it improves earlier bounds in single-agent and homogeneous cases.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Lemma 2 — the concentration bound defining event E and underwriting every later regret bound — contains a reversed Freedman inequality and inconsistent constants, so Theorem 1 is not established as written.","rationale":"The reader's weakest_assumption identifies the global-knowledge input requirement, which is a genuine limitation but is explicitly part of Algorithm 2's input and does not threaten the truth of Theorem 1 under that condition. The more load-bearing concern is internal to the proof: the keystone concentration lemma, Lemma 2, has a reversed inequality and inconsistent constants, making the proof of Theorem 1 unusable as written. This is not a matter of disagreeing with the paper's conclusions; rather, the exact steps that produce event E are unverified, and every subsequent bound conditions on E. The concern is concrete and checkable: one can re-derive the Freedman bound and test Eq. (12) numerically. If the constants are misstated rather than the strategy being wrong, the fix is likely a larger λ and corrected exponents, which would preserve the claimed O((L/Lmin)C) bound; this is why the verdict remains CONDITIONAL rather than REJECT. The reader's rationale already mentions index mismatches and unexplained constants; this attack sharpens that observation to a specific unverified inequality in the central lemma, so agreement is partial rather than full.","tokens_in":28644,"tokens_out":29713,"duration_ms":274970,"concrete_test":"Independently re-derive Lemma 2 with the definition of w^m given just before Eq. (8), substituting λ = 224 log(8KL log(T)/δ), T^m = λK2^{2(m-1)}/Lmin, and β = δ/(2K log T), and verify whether Eq. (12) (w^m_{k,ℓ}L_kT^m ≥ 2^10 ln(4/β)) and the two-sided bound leading to Eq. (15) actually hold. If Eq. (12) fails, test whether increasing λ to a larger constant, e.g., λ = 2^14 log(8KL log(T)/δ), restores event E with probability 1−δ while preserving the stated O() regret and communication bounds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1 rests on event E in Eq. (6): every step in Lemmas 3–5 and the regret decomposition in Section A.2 conditions on E. The proof of Lemma 2 does not currently verify E. Three concrete problems appear there. First, after applying the Freedman inequality to the martingale {X_t'}, the text asserts B^m_{k,ℓ}/(w^m_{k,ℓ}L_kT^m) ≥ ... with probability β/4, but the one-sided tail gives ΣX_t' ≤ V/b + b ln(4/β), i.e., B^m/(wL_kT^m) ≤ ..., not ≥; the two-sided bound needed for Eq. (15) is not written. Second, the claim |X_t'| ≤ 1 uses 2^{-2m-13} when bounding bad arms, while w^m is defined just before Eq. (8) with 2^{-2m-7}; with the stated definition, |X_t'| can be as large as (Δ^{m+1}_{k,ℓ})^{-2} ≤ 64, not 1. Third, the crucial lower bound in Eq. (12), w^m_{k,ℓ}L_kT^m ≥ 2^10 ln(4/β), appears numerically false: substituting λ = 224 log(8KL log(T)/δ), T^m = λK2^{2(m-1)}/Lmin, and w^m_{k,ℓ} = 2^{-2m-7}Lmin/(L_kK)(Δ^{m+1}_{k,ℓ})^{-2} gives w^m_{k,ℓ}L_kT^m = λ(Δ)^{-2}/512, which is at most about 28 ln(4/β), not ≥ 1024 ln(4/β). Consequently the claimed error Δ^m_{k,ℓ}/16 in Lemma 2 — and hence event E — is not supported. Because Lemmas 3–5 and the Case 1–3 regret analysis all invoke E, the additive O((L/Lmin)C) bound and Theorem 1 are not proven as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies L-agent K-arm stochastic bandits with adversarial corruption in a heterogeneous setting where each agent has its own local arm set. It proposes DRAA, a fully distributed, epoch-based algorithm in which each agent classifies its local arms as active or bad, assigns pull probabilities based on inverse estimated gaps, broadcasts observed reward sums at epoch boundaries, and forms estimates with a weighted estimator that reweights other agents' observations by inverse pull probabilities. The main result, Theorem 1, claims that with probability at least 1-δ the regret is O((L/Lmin)C + log(KL/δ log T) log T K/Δmin) and the communication cost is O(L log(T log((8K/δ) log T))), where C is the total adversarial corruption budget. The appendix derives the regret through a concentration lemma (Lemma 2), gap-estimate lemmas (Lemmas 3-5), and a three-case regret decomposition, and then specializes the bound to single-agent and homogeneous multi-agent settings, claiming to remove the K and L factors from the corruption term in those cases.","tokens_in":29099,"tokens_out":13877,"duration_ms":163371,"significance":"If the claimed bounds were correct, this would be a valuable first algorithm for heterogeneous multi-agent bandits with adversarial corruption, and the additive O((L/Lmin)C) corruption dependence is an attractive target. The claimed improvements over BARBAR in the single-agent case and over Liu et al. in the homogeneous multi-agent case are also significant, as is the explicit comparison between the weighted and naive estimators. The paper has a clear high-level proof strategy and the algorithm is reasonably described. However, the proof of Lemma 2, which is the cornerstone of every subsequent regret bound, contains several concrete and load-bearing errors: a reversed Freedman tail direction, an invalid |X_t'|≤1 bound, a numerically false lower bound relating the epoch length to the confidence parameter, and a mismatch between the event E that is stated and the event that is actually proved. The significance of the paper is therefore conditional on a corrected analysis.","major_comments":[{"comment":"Event E in Eq. (6) is defined with |r^m_{k,ℓ} - μ_k| ≤ 2C^m/(Lmin T^m) + Δ^{m-1}_{k,ℓ}/16, and Lemmas 3-5 and the regret decomposition in Section A.2 all condition on this event. However, the proof of Lemma 2 concludes with Eq. (17), which bounds the same deviation by 2C^m/(Lmin T^m) + Δ^m_{k,ℓ}/16. Since Δ^m_{k,ℓ} and Δ^{m-1}_{k,ℓ} are different random variables, the event actually proved is not the event used later. The proof must be modified to establish E as stated, or the subsequent lemmas must be reworked to use the event that is actually proved.","section":"A.1, Eq. (6) and Eq. (17)"},{"comment":"The Freedman bound displayed immediately before Eq. (10) is a one-sided upper tail: Pr(Σ_t X_t' ≥ V/b + b ln(4/β)) ≤ β/4. The text then asserts, with probability β/4, a lower bound B^m/(w^m L_k T^m) ≥ 2 w^m Σ|c|/(w^m L_k T^m) + sqrt(...). The upper tail gives the opposite inequality for this direction. A two-sided bound, for instance by applying the same Freedman inequality to {-X_t'}, is required to justify Eq. (15), and it is not written. This is a sign error in the central concentration argument.","section":"A.1, Eqs. (10)-(15)"},{"comment":"The bound |X_t'|≤1 is obtained by replacing the factor 2^{-2m-7} in the stated definition w^m_{k,ℓ}=2^{-2m-7} Lmin/(Lk K) (Δ^{m+1}_{k,ℓ})^{-2} with 2^{-2m-13}. With the definition as written, for k∈B^m_{ℓ'} one can only conclude |X_t'| ≤ (Δ^{m+1}_{k,ℓ})^{-2} ≤ 64, because Δ≥2^{-3} by Line 15 of Algorithm 2, not the claimed value 1. The Freedman inequality with b=1 is therefore not applicable as stated. The definition of w^m and the bounding argument must be made consistent.","section":"A.1, paragraph 'Upper bounding |X_t'|'"},{"comment":"The lower bound w^m_{k,ℓ} L_k T^m ≥ 2^{10} ln(4/β) is numerically false with the announced constants. Substituting T^m=λK2^{2(m-1)}/Lmin and w^m_{k,ℓ}=2^{-2m-7}Lmin/(LkK)(Δ^{m+1}_{k,ℓ})^{-2} gives w^m_{k,ℓ}L_kT^m = λ(Δ^{m+1}_{k,ℓ})^{-2}/512. With λ=224 ln(8KL log T/δ) and β=δ/(2KL log T), this is approximately 0.4375 ln(4/β)(Δ^{m+1}_{k,ℓ})^{-2}, which is at most about 28 ln(4/β). The claimed factor 2^{10} ln(4/β) is off by more than an order of magnitude. Consequently the bound sqrt(4 ln(4/β)/(w^m L_k T^m)) ≤ Δ^m/16 does not follow, and Lemma 2 is not established.","section":"A.1, Eq. (12)"},{"comment":"In Case 3 the text states 'if k∈B^{m-1}_ℓ' and then bounds RegB,3 by summing over k∈B^m_ℓ. These are different sets, and the proof does not explain why a bound for B^{m-1}_ℓ can be summed over B^m_ℓ. Given that Case 2 explicitly argued membership in B^m_ℓ, the Case 3 argument needs a matching membership statement for its corruption case. As written this part of the regret decomposition is not rigorous.","section":"A.2, Case 3 and Eqs. (41), (48)"}],"minor_comments":[{"comment":"The algorithm requires every agent to know the full arm set K and every other agent's local arm set in order to compute Lmin and the epoch lengths. This is a strong global-knowledge assumption for a 'fully distributed' algorithm; it should be stated explicitly and discussed, especially because the epoch boundaries and pull probabilities depend on it.","section":"Algorithm 2, Input"},{"comment":"Lemma 6 is stated with no assertion, and Eq. (33) refers to 'Lemma ??'. The proof of Remark 1 is therefore incomplete as presented.","section":"Appendix B, Lemma 6"},{"comment":"The sentence 'the leading term in both cases remains 1/Δ_min' is misleading, since O(K/Δ_min) can be a factor K larger than O(Σ_{k≠k*} 1/Δ_k) when many gaps are near Δ_min. The comparison should be made precise or removed.","section":"Section 4, paragraph 'Regret Tightness'"},{"comment":"There are frequent typos and OCR-style artifacts, including duplicated words ('if set too high or too low,if set too high or too low'), malformed inequality symbols ('/greaterorequalslant'), and inconsistent subscripts such as Δ^m_{k',ell}. These should be cleaned up before resubmission.","section":"Throughout"},{"comment":"The communication cost is stated without a proof or a precise definition of M, the number of epochs. The authors should specify M = min{m : T^m ≥ T} and prove the O(L log M) communication bound explicitly, since the epoch length depends on λ.","section":"Theorem 1"}],"recommendation":"major_revision","confidential_remarks":"The reader's report and my own reading agree on the central problem: the algorithm and the claimed bounds are plausible and interesting, but Lemma 2 is the cornerstone of the proof and it is not valid as written. The concrete issues (reversed Freedman tail, inconsistent w factor, numerically false inequality (12), and the E-event mismatch) are localized to the concentration proof and constants, so I believe a major revision rather than rejection is appropriate. However, if the authors cannot repair Eq. (12) and the associated concentration argument, the main theorem should not be accepted. The global-knowledge assumption in Algorithm 2 also deserves a more careful discussion, as it weakens the 'fully distributed' claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague:\n\nThe contribution is real; the proof is not. This is the first paper I know of that handles heterogeneous MA2B under adversarial corruption, and the weighted estimator is a legitimately useful idea. If the regret bound stands, it also answers two open questions: it removes the K factor in the single-agent corruption term from BARBAR and the L factor in the homogeneous multi-agent term from Liu et al. The logarithmic communication cost is a practical plus.\n\nNow the soft spots, and they are central. Lemma 2 is the concentration lemma that defines the event E, and every later regret bound conditions on E. The proof of Lemma 2 as written does not establish E. Three concrete problems:\n\n1. The Freedman inequality is applied to the martingale Σ X'_t = B^m − w^m Σ c. The cited inequality gives an upper tail: with probability 1−β/4, Σ X'_t ≤ V/b + b ln(4/β). The paper instead concludes B^m/(w^m L_k T^m) ≥ ... in Eq. (10). That is the wrong direction. The two-sided bound used later in Eq. (15) is never proved.\n\n2. The auxiliary weight w^m is defined with (Δ^{m+1})^{-2}, and later bounds use Δ^m and Δ^{m-1} interchangeably. With the definition as written, the claimed |X'_t| ≤ 1 bound fails.\n\n3. The purported lower bound w^m L_k T^m ≥ 2^10 ln(4/β) is numerically false. Substituting the stated λ, T^m, and w^m gives λ(Δ)^{-2}/512, which is around 28 ln(...), not 1024 ln(...). Eq. (12) cannot be right.\n\nThere is also an index mismatch between the event E in Eq. (6), which uses Δ^{m-1}/16, and the proof of Lemma 2, which concludes with Δ^m/16. Since Lemmas 3–5 all invoke E with Δ^{m-1}, the induction in Lemmas 4 and 5 does not line up.\n\nNone of this makes me think the algorithmic approach is wrong. The active/bad split, the synchronized doubling epochs, and the inverse-probability weighting are all sensible; the errors look fixable with a proper two-sided Bernstein/Freedman argument and more careful constants. A revision that repairs Lemma 2 and states the global-knowledge assumption explicitly (each agent needs K, all local arm sets, and Lmin to set epoch lengths) would make the paper sound.\n\nBottom line: this deserves a serious referee. The novelty is real, the subfield will care, and the proof issues should be caught before publication. Send it to review, but expect a major revision. I would want to re-check Lemma 2 line by line before trusting Theorem 1.","headline":"First heterogeneous multi-agent corruption-robust bandit paper with a genuinely useful weighted estimator, but the proof of Lemma 2 has a reversed Freedman inequality and false constants, so Theorem 1 is not established as written.","tokens_in":29627,"tokens_out":6787,"would_cite":false,"duration_ms":62337,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":null,"created_at":"2026-08-12T21:54:40.439803+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":null,"supporting_citations":[],"review_version":1}