{"id":"bd369cc7-a12f-45d0-8047-417d7284d75a","arxiv_id":"2608.06520","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper formalizes hidden Byzantine action overwrites in cooperative multi-agent RL, proves an exact rectangular robust-MDP reduction, shows linear security regret is unavoidable under uninformative attacks, and gives a stage-tied E2D learner with ~O(H^2 S sqrt(AK)) + E[D_K] regret.","lead":"Byzantine agents that secretly overwrite their own part of a multi-agent team's joint plan make online security learning fundamentally limited: the team can at best learn a statistical regret term plus an unavoidable response gap. The paper proves this lower bound and gives an algorithm whose security regret is near-optimal up to that unavoidable term.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main positive result is conditional on an unproven K^{-2}-approximate E2D oracle (Assumption 5.2); without it, the regret bound does not certify security.","rationale":"I read the paper's central claim as: security regret decomposes exactly, D_K is information-theoretically necessary, and under a standard E2D oracle the learner achieves O(H^2S sqrt(AK)) + E[D_K]. The decomposition (Prop 2.1) and lower bound (Thm 4.1) are solid. The stage-tied market proof (Thm 5.3) is long but internally consistent: calibration transport and supernormalization check out. The remaining weak point is Assumption 5.2. The paper is transparent about it, and the E2D framework in prior work also assumes decision oracles, so this is not a hidden flaw. However, the headline contribution is a conditional guarantee: if the oracle does not exist or is not measurable/implementable, the result does not establish security learning. The reader's conditional verdict is appropriate; my stress-test does not find an additional fatal gap. The one concrete check that would strengthen the paper is to either construct the oracle for the stage-tied class (e.g., via a finite epsilon-net or a convex-programming reduction) or prove that the discretized DEC suffices within the same regret bound.","tokens_in":39500,"tokens_out":18984,"duration_ms":164166,"concrete_test":"Take S=2, A=2, H=2, K=100, discretize the policy space Π and the certificate parameters (v,c) on a uniform grid of mesh K^{-2}, and solve the finite version of (16) by exhaustive enumeration. Compute the resulting return-regret trajectory and compare with C_K from Theorem 5.4. Independently, derive an upper bound on the discretization error |Q_k^grid(p) - Q_k(p)| for the Lipschitz halfspace losses; if the error cannot be made ≤ K^{-2} with O(poly(K)) grid points, Assumption 5.2 requires a genuinely continuous oracle and the paper's guarantee is not approximable by finite computation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim in Theorem 5.4 is E[Reg_sec] ≤ C_K + E[D_K] with C_K = O(H^2 S sqrt(A K)). This is only proven under Assumption 5.2, which postulates an F_{k-1}-measurable policy distribution p_k satisfying Q_k(p_k) ≤ inf_p Q_k(p) + K^{-2}. The paper does not construct this oracle, does not prove it can be implemented, and explicitly states in Section 5.4 that polynomial-time DEC minimization is not established. The local class H_k in (15) lives in a continuous certificate space (v,c in [0,H]^S), so the DEC in (16) is an infinite-dimensional optimization; the paper proves compactness and Borel measurability (Lemma F.12) but not that an approximate minimizer with the required measurability actually exists, let alone that it can be found. Because the lower bound (Theorem 4.1) shows D_K can be linear, the entire positive contribution reduces, without the oracle, to a bound on return regret that does not certify security. The oracle is therefore the linchpin of the paper's main claim, not a technical footnote.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online learning in a finite-horizon cooperative multi-agent system where an unknown, fixed subset of agents can overwrite their coordinates of the team's planned joint action after observing the plan. The learner observes planned actions, public rewards, and states, but not the overwrite or the executed action. The authors establish an exact reduction: if the attacker observes the planned action, the resulting public-outcome model is an (s,a)-rectangular robust MDP; if the attacker is blind, the model is s-rectangular. They introduce security regret, which compares each deployed policy's return to its worst-case overwrite value, and prove that security regret decomposes pathwise into return regret against the realized response plus a nonnegative cumulative response gap D_K. A lower bound (Theorem 4.1) constructs two horizon-one instances with identical public transcripts and zero return regret, yet security regret is linear in at least one, showing D_K is information-theoretically necessary. The main positive result (Theorem 5.4) is a stage-tied robust estimation-to-decisions (E2D) learner that, under an approximate decision oracle (Assumption 5.2), attains expected security regret O~(H^2 S sqrt(A K)) + E[D_K], with the estimation budget improved by a factor of sqrt(S) over a direct statewise approach. The paper also compares its benchmark and rates with uninformed Markov game results from prior work.","tokens_in":39732,"tokens_out":9252,"duration_ms":82305,"significance":"The decomposition in Proposition 2.1 and the lower bound in Theorem 4.1 are simple, self-contained, and correct; they cleanly identify the fundamental impediment to security learning from public feedback: the realized response's gap to worst-case behavior is unobservable and can be linear. The exact public-law reduction (Proposition 3.1) and the Markov sufficiency theorem (Theorem 3.2) are valuable structural contributions that clarify how the attacker's information geometry dictates the robust MDP class. The stage-tied estimator, if its proof is correct, provides a modest but concrete improvement over the direct statewise adaptation of Appel–Kosoy's E2D framework. However, the central positive result is conditional on Assumption 5.2, an oracle that is neither constructed nor shown to exist with the required measurability; the paper explicitly acknowledges in Section 5.4 that polynomial-time DEC minimization is not established. Since D_K can be linear, the positive bound without a feasible oracle does not yield a certification of security, making the oracle issue load-bearing rather than cosmetic.","major_comments":[{"comment":"The main positive guarantee (Theorem 5.4) is conditional on an approximate E2D decision oracle whose existence is merely assumed, not established. The authors state in Section 5.4 that they do not establish polynomial-time DEC minimization, and Assumption 5.2 only postulates the existence of an F_{k-1}-measurable pk satisfying (18). Because the local class H_k in (15) lives in a continuous certificate space (v,c ∈ [0,H]^S), the DEC in (16) is an infinite-dimensional optimization; Lemma F.12 proves compactness and Borel measurability of Q_k but does not prove that an approximate minimizer with the required measurability exists, let alone that it can be computed. Without this oracle, the bound E[Reg_sec] ≤ C_K + E[D_K] is not a constructive guarantee, and given that D_K can be linear (Theorem 4.1), the result reduces to a return-regret bound that does not certify security. I ask the authors to either (i) provide a proof of existence of a measurable approximate oracle, e.g., via standard measurable selection theorems after completion of the filtration, (ii) give a concrete oracle for a tractable subclass, or (iii) explicitly reframe the contribution as an oracle-based reduction and temper the claim of 'algorithmic foundations.'","section":"Section 5.4, Assumption 5.2, and Theorem 5.4"},{"comment":"The claimed sqrt(S) improvement rests on the stage-tied calibration argument, but the proof is far too compressed for verification. Lemma F.8 (supernormalization) and Lemma F.10 (one-layer calibration transport) are the critical steps that establish the layer-level rather than state-level charge, yet the derivations are only sketched, relying on a terse decomposition of bettor multipliers into outcome and action increments. I recommend that the authors expand the proofs of these two lemmas, isolating the exact telescoping identities and the convexity/inequality steps, so that the 'one certificate per layer' claim can be checked by an independent reader. At minimum, a high-level proof sketch describing where the sqrt(S) savings enters would substantially improve confidence in Theorem 5.3.","section":"Appendix F.4, Lemmas F.8 and F.10"},{"comment":"The paper's abstract and conclusion describe the work as providing 'comprehensive theoretical and algorithmic foundations,' but the only algorithmic component that is actually implemented and shown to run in finite time is the market-based estimator; the decision module is an assumed oracle that may not be realizable. I suggest that the authors calibrate the claims to distinguish between (a) the statistical estimation bound, which is their novel algorithmic contribution, and (b) the decision oracle, which is an imported abstraction. This will make the paper's actual scope transparent and avoid overstatement.","section":"Section 5.4 and Conclusion"}],"minor_comments":[{"comment":"The definition of C_K is written as `C_K := 114H^2S√(AKΛK(K−2))` with unbalanced parentheses; this should be clarified, e.g., `C_K := 114 H^2 S sqrt(A K Λ_K(K^{-2}))`.","section":"Theorem 5.4 statement"},{"comment":"The abstract uses 'Byzantine comprised'; this appears to be a typo for 'Byzantine compromised'.","section":"Abstract and Section 2.1"},{"comment":"The notation `N◦` for the analysis-only surrogate is not introduced before its first use in Proposition 5.1; a brief explanation of the superscript circle would improve readability.","section":"Section 5.1, Eq. (14)"},{"comment":"The notation `q emp,⋆` and the definition of `Cpost` are used without an explicit formal statement of the empirical comparator class; moving the definition of `Ωemp_K(B⋆)` earlier in that subsection would help the reader follow the comparison.","section":"Appendix B.3"}],"recommendation":"major_revision","confidential_remarks":"The lower bound and decomposition are the strongest parts of the paper and should be accepted as contributions in themselves. The positive result is an oracle-based reduction; whether that meets the journal's standard for an algorithmic guarantee is a judgment call, but the authors are transparent about the assumption. My main concern is that the oracle assumption may be unmet by any efficient procedure because of the infinite-dimensional continuous certificate space, and the paper does not even prove the existence of the required measurable selection. I would be more comfortable if the authors either prove the oracle is well-defined (e.g., via a measurable selection theorem) or explicitly downgrade the main theorem to a conditional statement and present the estimation bound as the primary algorithmic novelty. The paper is also extremely long (41 pages), with a dense appendix; tightening the presentation, especially around Assumption 5.2, would improve its accessibility."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The reader's report is fair, and the stress-test concern lands. This is a genuinely useful theory paper, but the headline security-regret bound is conditional on an oracle that is assumed, not constructed.\n\nWhat is actually new: the hidden action-overwrite threat model with public-only feedback, the exact rectangular geometry (insider gives (s,a)-rectangular, blind gives s-rectangular), and the security-regret decomposition into return regret plus the response gap D_K. The lower bound is the cleanest part: two horizon-one instances with identical public transcripts force linear security regret while return regret is zero, so D_K is information-theoretically unavoidable. The stage-tied E2D estimator is a real improvement, cutting the estimation budget from eO(HS^2) to eO(HS) and giving the sqrt(S) state-dependence gain. The paper is also honest: it explicitly says in Section 5.4 that polynomial-time DEC minimization is not established.\n\nThe soft spot is exactly what the stress-test says. Assumption 5.2 postulates a K^{-2}-approximate E2D decision oracle that returns an F_{k-1}-measurable policy distribution. No construction, no algorithm, no proof of existence for the infinite-dimensional DEC over the continuous certificate space. The paper proves compactness and Borel measurability but not that an approximate minimizer with the required measurability exists. Without that oracle, Theorem 5.4 degrades to a return-regret bound plus E[D_K], and since D_K can be linear, the security guarantee is not certified. The paper is transparent about this, but it is the linchpin, not a technical footnote.\n\nWhat holds up: the decomposition in Proposition 2.1 is an algebraic identity, the geometry theorems look correct, and the lower bound is convincing. The imported E2D machinery is heavy and hard to verify line-by-line, but the adaptation appears coherent. No experiments, which is fine for a theory paper of this type, though it means no empirical check on the estimator.\n\nWho this is for: researchers working in robust RL, Byzantine robustness, or multi-agent security. It deserves a serious referee; the ideas are new and the framework is likely to be influential even if the oracle gap is never closed. My recommendation: send to peer review, and let the reviewers push on the oracle. Conditional acceptance is the right call, with the paper's own transparency counting in its favor.","headline":"Solid theoretical contribution to Byzantine-robust MARL, but the main security-regret guarantee is conditional on an unproven oracle assumption that the paper itself acknowledges.","tokens_in":40222,"tokens_out":1546,"would_cite":true,"duration_ms":15648,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that security regret under hidden Byzantine attacks splits exactly into return regret plus a nonnegative response gap, that this gap makes linear regret unavoidable for any learner facing unrestricted realized attacks…","keywords":["Byzantine attacks","multi-agent reinforcement learning","robust Markov decision process","security regret","response gap","online learning","estimation-to-decisions","rectangularity"],"falsifier":"Run Algorithm 1 with an exhaustive-search implementation of the decision oracle on a small tabular instance whose responder is exactly worst case (so $D_K=0$); if the average security regret does not decrease at the claimed $\\widetilde O(H^2 S \\sqrt{A/K})$ rate as $K$ grows, the bound is contradicted. Alternatively, exhibit any learner that on the two horizon-one instances of Theorem 4.1 achieves $o(K)$ expected security regret on both, which would refute the lower-bound construction.","tokens_in":39311,"feed_emoji":"🛡️","tokens_out":7751,"duration_ms":61427,"temperature":0.7,"pith_summary":"This paper studies a finite-horizon cooperative team whose unknown, fixed subset of agents is Byzantine: after seeing the team's planned joint action, the compromised agents can overwrite their own coordinates before execution, and the learner sees only planned actions, public rewards, and public states. The paper's central claim is that this security problem is exactly a rectangular robust Markov decision process, and that the security regret, the gap between the optimal worst-case return and the deployed policy's worst-case return, splits into the return regret against the response that actually generated the data plus a nonnegative response gap $D_K$ measuring how far the realized attack is from worst case. Two indistinguishable one-horizon instances force $\\Omega(K)$ expected security regret even when return regret is zero, so no public-feedback algorithm can certify sublinear security regret against unrestricted realized attacks. On the positive side, a stage-tied estimation-to-decisions learner achieves expected security regret $\\widetilde O(H^2 S \\sqrt{AK}) + \\mathbb{E}[D_K]$ under a standard approximate decision-oracle assumption, improving the state dependence by $\\sqrt{S}$ over the direct statewise construction. This matters because it separates the statistical cost of learning from the information-theoretic cost of certifying security, and it shows exactly what public feedback can and cannot certify about hidden attacks.","feed_headline":"Security regret is return regret plus an unavoidable response gap","feed_subtitle":"Even identical public transcripts can conceal worst-case attacks, so the gap cannot be learned away.","key_machinery":"The load-bearing object is the exact public-law reduction: for a fixed Byzantine identity $B^\\star$, the set of attainable conditional public-outcome laws at each $(h,s,a)$ is the compact convex hull $\\Gamma_{h,s,a}^{B^\\star} = \\mathrm{conv}\\{P^{\\mathrm{phys}}_h(\\cdot \\mid s, a \\oplus_{B^\\star} u) : u \\in A^{B^\\star}\\}$, making the induced model $(s,a)$-rectangular. This reduction turns the operational worst-case value into ordinary rectangular robust dynamic programming while preserving exactness against full-history randomized overwrites. The second carrying mechanism is the stage-tied estimator: instead of maintaining a separate calibration process for every predecessor state, it shares one continuation vector per stage and pays the certificate entropy and calibration charge once per layer, which reduces the cumulative estimation budget from $\\widetilde O(HS^2)$ to $\\widetilde O(HS)$. Feeding this estimator into the robust estimation-to-decisions (E2D) framework yields the $\\sqrt{S}$ improvement and converts the estimation and optimism bounds into the stated security-regret bound.","core_discovery":"The central discovery is that Byzantine action overwrites with hidden identity and hidden execution induce an exact $(s,a)$-rectangular robust MDP: each state-action row is the convex hull of the public-outcome laws produced by all feasible overwrites, so deterministic nonstationary Markov team policies and deterministic Markov worst responses suffice. The paper further proves the exact identity $\\mathrm{Reg}^{\\mathrm{sec}}_K = \\mathrm{Reg}_K + D_K$, where $\\mathrm{Reg}_K$ is the return regret evaluated against the response that actually generated the data and $D_K \\ge 0$ is a cumulative response gap. Because the learner cannot observe overwrites or executed actions, $D_K$ is unidentifiable; the paper constructs two horizon-one instances with identical public transcripts in which return regret is zero but security regret is at least $K/2$ for one of them, making the $D_K$ dependence information-theoretically unavoidable. The algorithmic contribution is a stage-tied robust estimation-to-decisions learner that, under the framework's approximate decision oracle, attains expected security regret $\\mathbb{E}[\\mathrm{Reg}^{\\mathrm{sec}}_K] \\le \\min\\{HK,\\, C_K + \\mathbb{E}[D_K]\\}$ with $C_K = \\widetilde O(H^2 S\\sqrt{AK})$, using one continuation certificate and one occupancy-calibration witness per stage to cut the estimation budget from $\\widetilde O(HS^2)$ to $\\widetilde O(HS)$. The learner never identifies the compromised subset and never estimates the overwrites or executed actions.","pith_inferences":["If the $K^{-2}$-approximate decision oracle of Assumption 5.2 can be implemented in polynomial time for the stage-tied class, the bound would become algorithmic rather than conditional; the paper leaves this open.","The response-gap decomposition suggests a dual objective for practice: rather than maximizing factual return alone, a learner could deliberately query policies that force the attacker to reveal worst-case behavior, potentially trading a small return-regret increase for a large $D_K$ decrease.","The blind-attacker $s$-rectangular geometry, where randomized Markov policies can be essential, indicates that the information available to the attacker, not just the corruption, changes the learning problem; a separate stage-tied analysis for that model is a natural next step.","The two-instance lower bound exploits unrestricted realized responses; restricting attention to worst-case or $\\epsilon$-worst responders eliminates the obstruction, so the practical regime where $D_K$ is small is precisely where security learning is feasible."],"forward_implications":["If the realized response is an exact worst response against each deployed policy, $D_K=0$ and the security regret is bounded by $\\widetilde O(H^2 S\\sqrt{AK})$.","The lower bound means that an attacker who plays benignly but could have played worse is just as damaging to a security certificate as an attacker who actually plays worst case: public feedback alone cannot distinguish them.","The $\\sqrt{S}$ improvement shows that sharing a continuation vector across states in the estimator is strictly better than statewise certificate indexing, so state-dimension dependence in robust online reinforcement learning can be reduced without changing the decision class.","A guarantee of the form $C_K + \\mathbb{E}[D_K]$ gives a concrete research target: any exploration strategy that shrinks the response gap translates directly into a tighter security certificate.","Under the stage-tied learner, the Byzantine identity never has to be identified; the algorithm only needs the public-outcome laws relevant to robust decisions."],"supporting_citations":[{"why":"Supplies the robust estimation-to-decisions framework, the multivalued-model DEC bound, and the statewise market that the stage-tied estimator adapts.","marker":"[18]"},{"why":"Establishes the interactive decision-making template and the inexact-oracle extension that the paper's approximate-oracle analysis relies on.","marker":"[17]"},{"why":"Defines $(s,a)$-rectangular robust MDPs and the rectangular dynamic-programming identity that the exact public-law reduction invokes.","marker":"[16]"},{"why":"Supplies the robust-MDP dynamic-programming recursions used for robust value functions.","marker":"[34]"},{"why":"Provides the $s$-rectangular model and the fact that randomized Markov policies can be essential under $s$-rectangularity.","marker":"[35]"}],"fun_headline_variants":["Hidden Byzantine attacks force a security gap beyond return regret","Security regret is return regret plus an unlearnable response gap","Byzantine overwrites make the response gap information-theoretically unavoidable","Online security learning: the unidentifiable cost of hidden overwrites"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main regret guarantee rests on Assumption 5.2, which assumes an oracle that returns a $K^{-2}$-approximate policy distribution at every episode; the paper does not construct this oracle or prove that the underlying decision problem can be solved in polynomial time.","fun_headline_variants_meta":{"raw":{"variants":["Hidden Byzantine attacks force a security gap beyond return regret","Security regret is return regret plus an unlearnable response gap","Byzantine overwrites make the response gap information-theoretically unavoidable","Online security learning: the unidentifiable cost of hidden overwrites"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000274,"raw_usage":{"total_tokens":1727,"prompt_tokens":1120,"completion_tokens":607,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":736,"completion_tokens_details":{"reasoning_tokens":535}},"tokens_in":736,"tokens_out":607,"duration_ms":5767,"temperature":1.0,"reasoning_tokens":535,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:31:31.903120+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 with an exhaustive-search implementation of the decision oracle on a small tabular instance whose responder is exactly worst case (so $D_K=0$); if the average security regret does not decrease at the claimed $\\widetilde O(H^2 S \\sqrt{A/K})$ rate as $K$ grows, the bound is contradicted. Alternatively, exhibit any learner that on the two horizon-one instances of Theorem 4.1 achieves $o(K)$ expected security regret on both, which would refute the lower-bound construction.","supporting_citations":[{"cited_title":"Robust markov decision processes.Mathematics of Operations Research, 38(1):153–183, 2013","cited_arxiv_id":null,"evidence_quote":"Provides the $s$-rectangular model and the fact that randomized Markov policies can be essential under $s$-rectangularity."}],"review_version":2}