{"id":"895c541e-1c7b-4dc5-a041-0888cf87acf8","arxiv_id":"2601.21523","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A dependence-graph policy gradient that truncates each agent's contribution at the first time it influences another agent, with a learned graph estimator, improves cooperative MARL over local- and global-reward baselines.","lead":"This paper gives MARL agents a way to use their own local rewards while still cooperating: it cuts off reward terms that cannot causally reach an agent, using a learned graph of who depends on whom. The method trains faster than global-reward baselines on foraging tasks and avoids the miscoordination of pure local rewards.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The exactness of Proposition 5.1 does not transfer to the implemented estimator, which drops state mutual information and may miss true edges, biasing the truncated gradient.","rationale":"The reader's weakest assumption is the observability of parent sets in the networked-MDP factorization, which is indeed load-bearing. My concern sharpens this: even when parent sets are observable in principle, the implemented graph estimator's two simplifications (dropping state MI and using (s_i,a_i) as parent proxy) can produce a graph G′ with missing edges. Missing edges make t′ too late, so the truncation removes non-zero gradient terms and the estimator is biased. The paper itself flags the unknown effect of dropping state MI. This is not an internal inconsistency in Proposition 5.1, but a gap between the theory and the algorithm. The empirical ablation (Fig. 6) shows the learned graph performs comparably to an oracle on vanilla LBF, but that environment may not exercise the problematic state-dependence regime; the paper's own Appendix A.3 provides a concrete failure mode. Since the concern is empirical and addressable, a conditional verdict is appropriate; I do not see grounds to reject outright. The reader's conditional verdict already captures this, so no verdict change is needed.","tokens_in":25288,"tokens_out":5186,"duration_ms":55824,"concrete_test":"Use a synthetic networked MDP with known true parent sets, where transitions depend on a neighbor's state variable (not just its action). Learn G′ with the proposed estimator, then compare (a) edge recall against the true graph and (b) the dependency-graph policy gradient computed with G′ versus the oracle-graph gradient from Proposition 5.1. If recall is low or the gradient bias is nonzero, the central exactness claim fails for the implemented method. Alternatively, on a modified LBF where outside agents can enter another agent's observation, compare full method vs oracle-graph method; a significant performance drop would confirm the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central theoretical claim (Proposition 5.1) is that, given the true dependence graph, cross-agent gradient terms before causal influence are exactly zero, so truncation is not an approximation. The implemented method, however, replaces the true graph with an approximate graph G′ learned via a reverse world model using two explicit simplifications: (i) dropping I(S_i′;S_j) from the mutual information in Eq. (4), and (ii) conditioning on (s_i,a_i) rather than the full parent set. The Limitations section (Appendix A.2) concedes that the effect of ignoring state MI is unknown and expects failure when transitions depend heavily on agents' states. If G′ omits genuine edges, the meeting time t′ is later than the true first influence time, so the truncated gradient drops non-zero terms and becomes biased. Lemma 5.2 bounds error only when the graph mismatch is measured by total variation to an approximating kernel, not under the heuristic threshold c=0.9, and inequality (4) provides an expectation bound, not the uniform sup bound Lemma 5.2 requires. The GAE-style aggregation (Algorithm 1) downweights rather than corrects missing edges, so it cannot restore exactness—it only trades variance for bias. Thus, the headline property of exact truncation is not established for the actual algorithm, and the experimental gains over local/global rewards may reflect a heuristic that lacks the claimed guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a dependence-graph policy gradient for cooperative MARL. Under a networked-MDP factorization in which each agent's next substate depends only on the states and actions of a state-dependent parent set, Proposition 5.1 claims that the cross-agent policy-gradient term ∇_{π^j} J^i(π) can be exactly truncated: only rewards received after the first time t' at which a path in the dependence graph connects (s_0,j) to (s_t',i) contribute. It then introduces a practical method for approximating the graph with reverse world models and a mutual-information surrogate, and a GAE-style estimator that aggregates over multiple estimated meeting times. Experiments on LBF and SMAClite with MAPPO and IPPO backbones compare the method with local-reward and global-reward baselines, and an ablation compares the learned graph with random and oracle graphs. The paper is supported by an appendix containing proofs and additional experimental detail.","tokens_in":25641,"tokens_out":10594,"duration_ms":112202,"significance":"If the central claims held as stated, the paper would make a useful contribution: it identifies a time-dimension truncation of policy gradients that is exact for an oracle dependence graph, complements existing spatial k-hop approximations, and is accompanied by public code and a reasonably careful evaluation protocol (IQM, ablations, multiple scenarios). The formal framework is self-contained given the networked-MDP axioms, and the authors are candid about several limitations. However, the headline exactness property is established only for a true, observable dependence graph, and the bridge from that result to the implemented approximate-graph algorithm is incomplete. In particular, the proof of Lemma 5.2 has a gap, and the practical graph estimator uses heuristics that are not covered by the lemma's assumptions. These issues are load-bearing for the paper's claimed theory, so the manuscript requires substantive revision.","major_comments":[{"comment":"The displayed equation for Q_{P,G'}^{i,j}(s,a) - Q_{P',G'}^{i,j}(s,a) is not bounded correctly. The first term contains P(s'|s,a) Q_{P,G'}(s',a') minus P'(s'|s,a) Q_{P',G'}(s',a'); after adding and subtracting P'(s'|s,a) Q_{P,G'}(s',a'), one obtains γ Σ(P-P') E Q_{P,G'} plus γ E_{P',π}[Q_{P,G'} - Q_{P',G'}]. The second of these is a recursive term that cannot be ignored. The proof bounds the first term solely by γ ε R_max/(1−γ), which yields the stated O(γ ε/(1−γ)^2) only if the recursive term is also handled. As written, the proof of the T2 bound is incomplete. A correct argument via the augmented-state simulation lemma may be possible, but it must be supplied explicitly.","section":"Appendix A.5, proof of Lemma 5.2"},{"comment":"The connection between Lemma 5.2 and the implemented graph estimator is not established. Lemma 5.2 requires a uniform sup-norm TV bound ε on the transition kernels. Inequality (4) provides only an expectation bound under some state-action distribution. Moreover, Section 5.3 introduces two further simplifications — dropping I(S_i';S_j) and replacing parent sets by (s_i,a_i) — and then applies a heuristic threshold c=0.9. No argument is given that the resulting graph G' satisfies the hypothesis of Lemma 5.2, or even a distributional analogue with explicit ε. Thus the exactness of Proposition 5.1 does not transfer to the algorithm whose results are reported; the practical method is best described as a heuristic. The authors should either weaken the theoretical claims accordingly or provide conditions, and ideally measurements, showing that the learned graph yields small TV error.","section":"§5.2–5.3, Eq. (4) and Algorithm 2"},{"comment":"The displayed identity is incorrect. For conditional mutual information, I(S_i'; A_j | S_i, A_i, S_j) = H(A_j | S_i, A_i, S_j) − H(A_j | S_i, A_i, S_j, S_i'), not H(A_j | S_j) − H(A_j | S_i, S_j, S_i'). The equality as written would require additional conditional independence assumptions that are not stated and do not follow from the networked-MDP setup. Relatedly, Algorithm 2 compares H(q_φ(z_i,t)) with H(q_ψ(z_i,t, z_j,t, z_j,t+1)); this compares entropies of agent i's action predictions conditioned on different inputs, which does not match the edge direction implied by Eq. (5) (which concerns agent j's action). The information-theoretic justification for the learned edges therefore needs to be restated and reconciled with the algorithm.","section":"§5.3, Eq. (5)"},{"comment":"The paper's fundamental assumption is that an agent can infer its parent set Pa_i(s_i) from its local observation. Appendix A.3 concedes that this is 'difficult to meet in practice' and gives an example in which an outside agent can enter the observation at the next time step. When parent sets are not observable, the learned graph G' is miscalibrated and the meeting time t' used in Proposition 5.1 is not well-defined for the implemented estimator. This is not merely an implementation detail: it means the exact-truncation statement is conditional on an assumption that is acknowledged to be violated in realistic settings. The paper should state this as a formal condition of the main theorem and discuss the failure mode more concretely, rather than relegating it to a short limitations paragraph.","section":"§3 and Appendix A.3"}],"minor_comments":[{"comment":"In line 8, the notation λ1(H_{ji}>0) + (1−λ) is a compact but hard-to-parse combination of indicator and GAE weight. A short derivation or a comment would help readers connect it to the Appendix A.4 derivation.","section":"Algorithm 1"},{"comment":"The claim that every proper dependence graph has a unique collection of agent-dependence sets is used later but not proved. A brief proof or counterexample discussion would improve confidence.","section":"Definition 3.2"},{"comment":"Minor typographical issue: 'Böhler' appears as 'B\\\"ohmer'; also, the self-citation Le & Ta (2025) is mentioned in related work but is not central to the comparison, so ensure it is cited in context only.","section":"References"},{"comment":"The oracle graph is defined by an L1-distance threshold, but the random-graph ablation varies p without showing variance over random graph draws. Reporting confidence bands or multiple seeds for the random graphs would strengthen the message that the learned graph outperforms random structures.","section":"Figure 6"}],"recommendation":"major_revision","confidential_remarks":"The gap in the proof of Lemma 5.2 is the most serious technical issue and should be the first thing the authors address. If the gap can be repaired with an augmented-state simulation-lemma argument, the paper may still be publishable after reframing the practical claims as heuristic. If not, the theoretical contribution is substantially weaker than advertised and the manuscript may need to be reduced to an empirical study of a heuristic graph-based credit assignment method."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague —\n\nThe paper is a serious effort, and the central idea is better than the packaging suggests. Proposition 5.1 gives a clean exact identity: for a factored networked MDP with observable parent sets, the cross-agent policy gradient is zero until the first time a path exists in the dependence graph from the acting agent to the rewarded agent. That is a neat formalization of \"credit starts to flow when influence can flow,\" and the proof is straightforward and readable. The GAE-style aggregation over meeting times is a sensible way to make the estimate robust to noisy graphs, and the reverse-world-model edge estimator is a practical way to get the graph from data. The LBF experiments show consistent gains over both local and global reward baselines; the SMAClite numbers are honestly reported as mostly comparable.\n\nThe soft spots are real but not fatal. The biggest one is the gap between the exact theory and the implemented estimator. Proposition 5.1 is exact only for the true graph; the algorithm uses a learned graph with two explicit approximations (dropping the state mutual information, conditioning on (s_i,a_i) instead of the full parent set) and a threshold c=0.9 with no sensitivity analysis. The error lemma (Lemma 5.2) is stated for a kernel satisfying a uniform total variation bound, but the bound actually derived in inequality (4) is in expectation, so the formal guarantee does not carry over to the heuristic graph. The appendix's own limitation note says the effect of ignoring state MI is unknown and may fail when transitions depend heavily on states. None of this makes the paper incoherent—the authors admit the limitations explicitly—but it does mean the headline \"exact truncation\" belongs to the idealized setting, not the code.\n\nThe experiments would be stronger with confidence intervals and seed counts; Figure 4 gives aggregated metrics but no error bars. That is an addressable issue.\n\nWho should read it: anyone working on MARL credit assignment or factored MDPs. The theory section alone is worth a look.\n\nVerdict: worth a serious peer review. Not a desk reject. A good referee will push the authors to close the gap between the exact result and the practical estimator, and to be precise about what the experiments actually show.\n\nBest,\n[Your name]","headline":"A genuinely novel policy-gradient truncation result on dependence graphs that deserves a serious look, though the practical estimator does not inherit the exactness of the theory.","tokens_in":26149,"tokens_out":2842,"would_cite":true,"duration_ms":30073,"reading_group":"maybe","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 in cooperative multi-agent reinforcement learning, cross-agent policy-gradient terms before the first causal path in a dependence graph are exactly zero, making truncation exact rather than approximate.","keywords":["multi-agent reinforcement learning","credit assignment","policy gradient","dependence graph","networked MDP","local rewards","generalized advantage estimation","reverse world model"],"falsifier":"Construct a minimal two-agent MDP where one agent's next state depends on another agent's action only when an external flag flips at the same time, so that the influencing agent is in the true parent set only intermittently and cannot be inferred from the affected agent's substate alone; then compare the exact cross-agent gradient to the paper's estimator. A nonzero difference before the estimated meeting timestep would falsify the claimed exactness for the implemented estimator.","tokens_in":25126,"feed_emoji":"🕸️","tokens_out":6138,"duration_ms":61667,"temperature":0.7,"pith_summary":"Cooperative multi-agent reinforcement learning usually forces a choice: give every agent the same global reward and struggle to assign credit, or give each agent its own local reward and risk selfish, myopic behavior. This paper tries to combine both by using a state dependence graph that tracks which agents can actually influence which other agents over time. The central claim is that an agent's policy gradient with respect to another agent's return only needs reward terms that arrive after the first timestep at which a causal path exists between them in the graph; before that, the cross-agent gradient is exactly zero. Truncating those terms is therefore not an approximation, and it removes the variance that global reward scalarization injects. The paper also gives a practical way to learn the graph from data and shows empirically that the approach beats both extreme reward settings on cooperative benchmarks.","feed_headline":"Cross-agent gradients vanish until a causal path exists","feed_subtitle":"For cooperative MARL, reward terms that cannot be causally influenced are exactly zero, cutting credit-assignment variance.","key_machinery":"The central object is the state dependence graph of a networked MDP: a directed graph whose vertices are (state, agent) pairs and whose edges record which agents' states and actions can affect which other agents' next substates. The theorem that carries the argument is the k-hop-parent expansion: the set of agents that can have influenced agent i by time t grows monotonically, so the first meeting timestep t′ partitions the reward stream into zero and nonzero contributions. The practical machinery is a reverse world model that predicts one agent's action from another agent's state and next state; the entropy drop produced by conditioning on the second agent is thresholded to add an edge, and","core_discovery":"On the paper's own terms, the discovery is Proposition 5.1: fix any joint policy and any pair of agents i and j, and define t′ as the first timestep at which a directed path exists in the state dependence graph from (s0, j) to (s_{t′}, i). Then the policy gradient of agent j's policy with respect to agent i's cumulative return is the expectation of ∇logπ_j(a_0^j|s_0^j) times the expected discounted sum of i's rewards from t′ onward. Before t′, all cross-agent gradient contributions vanish exactly; if no such path ever exists, the cross-agent gradient is zero. The paper further shows that using an approximate graph with model error ε yields a gradient error bounded by O(B_j γ ε R_max/(1−γ)^2)","pith_inferences":["Editorial inference: the same truncation principle should transfer to off-policy and value-based learners, since the zero-gradient result is about the MDP structure rather than the policy-gradient estimator; a value-based analogue would replace reward truncation with a first-meeting value function.","Editorial inference: if the dependence graph is sparse and stable across states, the sample complexity of cooperative credit assignment could scale with the size of interaction neighborhoods rather than the total number of agents, weakening the known many-agents scalability barrier.","Editorial inference: the learned reverse-world-model graph could serve as a diagnostic for interaction structure, but the paper's own simplification (dropping state-state mutual information) suggests it will under-report edges in environments where transitions are driven by states rather than actions.","Editorial inference: the assumption that parent sets can be inferred from current substates is the main practical gap; in partially observable settings, using a recurrent policy or an observation-history encoder could recover the missing outsider influences that the one-step graph misses."],"forward_implications":["If the true dependence graph is known, the dependency-graph policy gradient is unbiased and lower variance than the vanilla global-reward gradient, because it discards reward terms that cannot be causally influenced.","For sparse interaction graphs, cross-agent gradient contributions effectively vanish until the meeting timestep, so the method interpolates between local-reward learning (empty graph) and global-reward learning (fully connected graph).","When only an approximate graph is available, the error bound in Lemma 5.2 gives a principled target: learn a transition model with small total variation error ε, and the gradient bias stays O(ε/(1−γ)^2).","The proposed graph-estimation method makes the framework applicable when no hand-designed graph exists; empirically it performs close to an oracle graph on the tested cooperative foraging tasks."],"fun_headline_variants":["Exact zero cross-agent gradients until a causal path appears","No gradient flow between agents without a dependence path","Cross-agent gradients vanish before graph connectivity","Zero credit assignment prior to causal link","Gradient vanishes until dependence graph connects"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire exactness result rests on the assumption that each agent's current substate is enough to identify which other agents' states and actions can influence its next substate; if that one-step locality fails, the learned graph and the meeting timesteps no longer align with true causal influence.","fun_headline_variants_meta":{"raw":{"variants":["Exact zero cross-agent gradients until a causal path appears","No gradient flow between agents without a dependence path","Cross-agent gradients vanish before graph connectivity","Zero credit assignment prior to causal link","Gradient vanishes until dependence graph connects"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000258,"raw_usage":{"total_tokens":1410,"prompt_tokens":727,"completion_tokens":683,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":471,"completion_tokens_details":{"reasoning_tokens":616}},"tokens_in":471,"tokens_out":683,"duration_ms":7014,"temperature":1.0,"reasoning_tokens":616,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T06:55:45.368255+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a minimal two-agent MDP where one agent's next state depends on another agent's action only when an external flag flips at the same time, so that the influencing agent is in the true parent set only intermittently and cannot be inferred from the affected agent's substate alone; then compare the exact cross-agent gradient to the paper's estimator. A nonzero difference before the estimated meeting timestep would falsify the claimed exactness for the implemented estimator.","supporting_citations":[],"review_version":1}