{"id":"35b28a18-c64b-448d-82f8-33b171950ac1","arxiv_id":"2506.04215","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A new class of closed-form decentralized policies is shown to be exponentially near-optimal in visibility for locally interdependent multi-agent MDPs.","lead":"This paper proposes the Extended Cutoff Policy Class, a family of partially observable policies for Locally Interdependent Multi-Agent MDPs, and proves they are exponentially close to optimal as visibility grows. It adds memory-based extraction methods that help in fixed small-visibility settings and extends the model to generalized transition and reward dependencies.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 rests on the unproved Appendix D assertion that optimal finite-horizon cutoff policies are Consistent Performance Policies; the 1-Step Displaced and Deconstructive inequalities are not immediate from optimality, so the exponential near-optimality guarantee is currently unsupported.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing gap: the proof of Theorem 2, and hence Theorem 1, depends on the four Consistent Performance Policy inequalities, yet the paper only states they are 'trivially satisfied' by the optimal finite-horizon policy, with no derivation. This is not a minor presentational omission. The 1-Step Displaced condition involves a horizon shift and an appended terminal policy; optimality of π over horizon c+η does not by itself bound a c+η+1-step tail evaluated at time 1. The Deconstructive condition involves a virtual coarser partition whose coordination across actually disconnected groups is not obviously value-decreasing. Both inequalities are used inside Lemma 6, which is then used in Lemma 9 and in the main proof of Theorem 2. Without a proof, the exponential visibility-dependent bound has no demonstrated foundation. My proposed test is deliberately small and exhaustive: it can either produce a counterexample to the 'trivially satisfied' claim or provide strong evidence that the claim is true and merely under-derived. Because this concern confirms rather than changes the reader's REJECT verdict, the recommended verdict is UNCHANGED.","tokens_in":995,"tokens_out":962,"duration_ms":108714,"concrete_test":"Run an exhaustive finite-state check. Enumerate all deterministic 2-agent LIM-MDP instances with, say, 2 positions per agent plus a dummy terminal state, R=0, V=1, c=1, η∈{0,1,2}, and all reward values in {−2,−1,0,1,2}; compute the optimal finite-horizon proper cutoff policy π^{ξ,η}_comp by full dynamic programming. For each instance, existentially search over appended stationary policies π_{H+1} and verify the four Appendix D inequalities for every P' finer than P and every state. Begin with the 1-Step Displaced condition, since a counterexample there would directly falsify the 'trivially satisfied' claim. If any instance violates all choices of π_{H+1}, the claim is false and Theorem 1 as stated is invalid; if no violation is found across the exhaustive grid, the gap is a missing proof and should be patched with a derivation before acceptance.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix D defines four 'Consistent Performance Policy' inequalities and asserts, without proof, that they are 'trivially satisfied' by the optimal finite-horizon policies π^{ξ,η}_comp. This assertion is the linchpin of Theorem 1: Theorem 2's proof applies Lemma 6, whose derivation uses these inequalities (see Eq. (10) in Lemma 6 and Corollary 7), and Theorem 1's step (1) applies Theorem 2 to π^{ξ,η}_comp. The problem is not merely a missing line. Optimality does not trivially imply the 1-Step Displaced condition [V^{π'}_{1,c+η+1}]_p(s,P) ≤ [V^π_0]_p(s,P): comparing a tail that runs for c+η+1 steps from time 1 against a c+η-step value from time 0 is an inequality about horizon extension, and the appendix gives no argument relating the appended stationary policy π_{c+η+1} to the optimality of π. Similarly, Deconstructive Improvement compares a virtual policy coordinating under the coarser P with an environment evolving under the finer P', and it requires proof that such 'forbidden' coordination cannot improve group-local value. Since Lemma 6 and hence Theorem 2 collapse if these inequalities fail, the central claim—exponential near-optimality for every policy in the Extended Cutoff Policy Class—is not established. I do not claim the inequalities are false; I claim they are nontrivial and currently unproved, and the paper's own text flags them as 'trivially satisfied' rather than deriving them.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an Extended Cutoff Policy Class for Locally Interdependent Multi-Agent MDPs, consisting of policies obtained by solving a Cutoff Multi-Agent MDP with an enlarged computational visibility and then extracting a group-decentralized policy through a belief-like extraction method. The central claim is Theorem 1: every policy in this class is within β γ^{c-1}/(1-γ) of the fully observable joint optimum, where c = floor((V_exec - R)/2), so performance improves exponentially as the execution visibility grows. The proof route is Theorem 2, a more general near-optimality bound for any 'Consistent Performance Policy', applied to the optimal finite-horizon cutoff policy π^{ξ,η}_comp. The paper also proposes a Generalized Locally Interdependent Multi-Agent MDP, claims the same bounds there, and presents simulations intended to show that Simple Memory Based Extraction improves behavior at small fixed visibility and can achieve full observability in deterministic settings.","tokens_in":39196,"tokens_out":8574,"duration_ms":81659,"significance":"If Theorem 1 is correct, the paper would establish a broad and useful class of closed-form partially observable policies that unify the earlier Amalgam, Cutoff, and First-Step policies, and it would extend the theory to a generalized model with transition and reward dependence. The explicit bound, the identification of the Extended Cutoff Policy Class, and the large-scale 100-agent simulation without deep learning are genuine strengths, as is the transparent effort to include negative empirical examples against the proposed method. However, the main theoretical result is currently conditional on an unproved set of inequalities, so the significance cannot be assessed until that gap is closed.","major_comments":[{"comment":"The four 'Consistent Performance Policy' inequalities are asserted, not proved. The text in Appendix D states only that 'these conditions are trivially satisfied by the optimal finite horizon policies π^{ξ,η}_comp', with no derivation. These inequalities are load-bearing: Lemma 6 uses the Constructive/Deconstructive inequalities in Equation (10), Corollary 7 and Lemma 8 use the 1-Step Displaced and 1-Step Contracted inequalities, and Theorem 2's Step 2 bounds the key Δ_t terms through Lemma 6. Since Theorem 1 applies Theorem 2 to the optimal policy π^{ξ,η}_comp, the exponential bound in Theorem 1 collapses if any of the four inequalities fails. The inequalities are not immediate consequences of finite-horizon optimality: for example, 1-Step Displaced Improvement compares the tail of an extended policy π′ (with an appended stationary policy π_{c+η+1}) against the full value of π starting one step earlier, and optimality of π for horizon c+η does not by itself constrain the value of the appended tail. Similarly, Deconstructive Improvement compares a policy that coordinates under a coarser partition than the environment actually uses, and it needs an argument rather than a 'trivial' assertion. A complete proof of the CPP conditions for π^{ξ,η}_comp, or a revised theorem that does not depend on them, is required before Theorem 1 is established.","section":"Appendix D and Lemma 6"},{"comment":"Proposition 3 claims that Simple Memory Based Extraction converges to the fully observable joint optimal solution as ξ, η → ∞ in any Locally Interdependent Multi-Agent MDP where all agents start within view. The paragraph preceding the proposition gives intuition about Algorithm 1, but no proof is supplied. A convergence claim of this form requires controlling both the error from the finite horizon c+η and the error from the memory-based belief extraction as ξ and η grow; neither is analyzed. Since this proposition underlies contribution (iii) and the Aisle Walk / Long Journey claims, it needs either a rigorous proof or a clear downgrade to an empirical observation.","section":"Section 3.2.2, Proposition 3"},{"comment":"The empirical claims about resolving Penalty Jittering and improving small-visibility performance are based on single rollouts without error bars, confidence intervals, or multiple random seeds, even in the stochastic example of Appendix A.9. The appendix does include adversarial examples where Simple Memory Based Extraction underperforms Trivial Extraction, which is honest, but the general claim that the class 'resolves' Penalty Jittering is stronger than what single trajectories can support. I view this as a presentation/evidence issue rather than a fatal flaw, but the wording should be softened or the experiments should be repeated.","section":"Appendix A (simulations)"}],"minor_comments":[{"comment":"The notation 'N one' appears in Algorithm 1 and its explanation; this appears to be a rendering of 'None' or 'null'. Also, the line 's_belief_next = argmax_{s'} P(s'|[s_belief]_z_belief, a_belief)' chooses a single most likely next state, which is not the same as the expected transition; this choice should be stated explicitly as a heuristic, since it affects the memory update.","section":"Algorithm 1, Appendix B"},{"comment":"The bound is stated with β defined in the theorem, but the proof of Theorem 1 in Appendix E.1.1 writes Equation (3) with an additional γ^{c′−c+1} term that comes from Theorem 10. This is internally consistent only if one notes c′ = floor((V_comp − R)/2); the presentation would benefit from explicitly writing the substitution, since a reader can otherwise mistake the constant factor.","section":"Section 3.2.1, Theorem 1 statement"},{"comment":"In Theorem 10, the equality of the first c′ rewards between the original trajectory and the cutoff trajectory is stated without a detailed proof in the standard (transition-independent) case; the generalized proof supplies the needed equivalence argument. I suggest moving that argument or citing it in the standard case for completeness.","section":"Appendix E.1.2, Equation (18)"},{"comment":"The definition of a trajectory π|P′_{s,P} uses P′ both as a partition and as the policy's assumed initial partition, while the actual partition is P; this is clear after careful reading, but the notation would be less confusing if the assumed partition were named differently, e.g., P_assume.","section":"Appendix D, notation"}],"recommendation":"major_revision","confidential_remarks":"The paper is built very directly on the authors' prior work, which is legitimate but makes the novelty assessment hinge on whether the Consistent Performance Policy conditions can actually be proved for optimal finite-horizon cutoff policies. The current 'trivially satisfied' assertion is not acceptable for a main theorem. If the authors can supply a rigorous proof or replace the CPP framework with a conditional theorem whose hypothesis is verified, the paper may become publishable; without it, Theorem 1 is unsupported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read the paper and I largely agree with the stress-test note. The central theorem currently rests on an unproved assertion, and that is the thing to fix before this can be taken as established.\n\nWhat is genuinely new: the Extended Cutoff Policy Class is a real generalization. It subsumes the three prior policies, adds the memory-based extraction mechanism, and gives a clean story of why remembering out-of-view agents can help in small-visibility settings. The generalized MDP with transition and reward dependence is also a meaningful extension, and the proof structure there is a faithful analogue of the standard case. The simulations, while informal, are honest: they include adversarially chosen cases where Simple Memory Based Extraction underperforms, and the 100-agent navigation result without collisions is a useful existence check.\n\nWhere the soft spot is: Appendix D defines four Consistent Performance Policy inequalities and says they are “trivially satisfied” by the optimal finite-horizon cutoff policy. I do not think that is trivial, and I think the stress-test note is right that the horizon-comparison inequalities are the suspicious ones. The 1-Step Displaced and 1-Step Contracted conditions compare value functions at different starting times and different horizons; optimality of a finite-horizon policy does not by itself say that its value from time 0 dominates a shifted tail, because the immediate reward at time 0 and the extra terminal reward at time c+eta+1 are not comparable without an argument. Lemma 6 and Lemma 8 use these conditions directly, and Theorem 2—hence Theorem 1—collapses if they fail. I am not claiming the inequalities are false; I am claiming they are nontrivial and unproved.\n\nThe rest of the proof, as far as I can see, is structurally coherent. The Dependence Time Lemma is sound, the decomposition in Theorem 2 is a reasonable strategy, and the generalized constants are consistent with the looser assumptions. The lack of error bars on single-rollout simulations is a minor issue compared to the Appendix D gap, but it means the empirical claims should be read as illustrative.\n\nWho this is for: someone working on theoretically grounded decentralized multi-agent control would want to engage with this, but only after the gap is closed. The paper deserves a serious referee; the right outcome of peer review would be a demand for a proof of the Consistent Performance Policy conditions, or a revision that states them as assumptions rather than consequences. As posted, the abstract overstates what is actually supported.","headline":"A genuinely new policy class and an honest but nontrivial gap: the main theorem rests on four 'Consistent Performance Policy' inequalities that are asserted, not proved.","tokens_in":39670,"tokens_out":2982,"would_cite":false,"duration_ms":33644,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40","68T42","93A16"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes a class of decentralized policies—built by solving an extended-visibility cutoff MDP and extracting a belief-based execution policy—whose performance gap to the fully observable joint optimum shrinks exponentially…","keywords":["Locally Interdependent Multi-Agent MDP","Dec-POMDP","partial observability","decentralized policies","cutoff policy","exponential near-optimality","Penalty Jittering","cooperative navigation"],"falsifier":"Enumerate the optimal finite-horizon cutoff policy for a small two-agent grid (for example $V=R+2$, $\\gamma=0.9$) and directly compute the four value differences in Appendix D: Constructive, Deconstructive, 1-Step Displaced, and 1-Step Contracted Improvement. A single violation of any of them would falsify the claimed exponential bound, because the proof of Theorem 1 is exactly the chain that converts those inequalities into the bound.","tokens_in":38638,"feed_emoji":"🧠","tokens_out":11657,"duration_ms":100762,"temperature":0.7,"pith_summary":"This paper addresses decentralized multi-agent problems such as cooperative navigation, obstacle avoidance, and formation control, where agents only see a local region and local interactions matter. It proposes the Extended Cutoff Policy Class: solve a 'cutoff' version of the problem with an enlarged computational visibility, then execute the first step of that solution using a belief about agents beyond the physical visibility. The main theorem states that every policy in this class has value within $\\beta \\gamma^{\\lfloor (V_{\\mathrm{exec}}-R)/2\\rfloor -1}/(1-\\gamma)$ of the fully observable joint optimum, so larger visibility buys exponential closeness to optimality; the same guarantee is proved when transitions and rewards also depend locally on other agents. The class contains and unifies three earlier closed-form policies and includes a memory-based extraction method that fixes a 'Penalty Jittering' failure mode and, in deterministic settings with all agents initially in view, converges to joint optimality. A sympathetic reader would care because this turns a NEXP-complete general problem into a tractable family of closed-form policies with provable performance and a tunable trade-off between computation and belief radius.","feed_headline":"Remembering beyond visibility makes decentralized policies near-optimal","feed_subtitle":"A thinking radius lets agents recall out-of-view agents, closing the gap to the full-observability optimum exponentially.","key_machinery":"The load-bearing construction is the Extended Cutoff Policy Class. To build a policy, one chooses an extended computational visibility $V_{\\mathrm{comp}}=V_{\\mathrm{exec}}+\\xi$ and horizon $c+\\eta$ with $c=\\lfloor (V_{\\mathrm{exec}}-R)/2\\rfloor$; the corresponding Cutoff Multi-Agent MDP, where disconnected groups never reconnect, is solved to that horizon, and the first-step policy is executed through an extraction method $\\rho$ that converts the current observation history into a belief state over out-of-view agents. Three extraction methods are described: Trivial, Aggregate, and Simple Memory Based. The proof that the policy class is near optimal rests on the Dependence Time Lemma, which uses the speed limit (agents move at most one unit per step) and $V>R$ to guarantee that agents in different visibility groups cannot affect each other's rewards or transitions for $c$ steps; this buffer lets local value comparisons be made with only exponentially small error. The paper also isolates four Consistent Performance Policy inequalities that allow the value of the computation phase to transfer to the execution phase, and asserts that the optimal finite-horizon cutoff policy satisfies them.","core_discovery":"The central claim is Theorem 1: for any (Generalized) Locally Interdependent Multi-Agent MDP with execution visibility $V_{\\mathrm{exec}}$, any policy in the Extended Cutoff Policy Class satisfies $V^*(s)-V^\\pi(s) \\le \\beta \\gamma^{\\lfloor (V_{\\mathrm{exec}}-R)/2\\rfloor-1}/(1-\\gamma)$, where $\\beta$ is a constant depending on $\\gamma$, the horizon parameter $\\eta$, and the gap between computation and execution visibility (and on $n$, the number of agents, in the generalized setting). The proof routes through Theorem 2: for any Consistent Performance Policy, the value of the extended cutoff computation and the value of the extracted execution policy differ by the same exponential-in-visibility term. The paper shows that the optimal finite-horizon extended cutoff policy is such a policy, and that the bound matches the known lower bound up to constants. The proposed framework therefore gives, as the authors state, the first non-trivial class of near-optimal closed-form partially observable policies for every Locally Interdependent Multi-Agent MDP, while subsuming the Amalgam, Cutoff, and First-Step policies as special cases.","pith_inferences":["Editorial extension: The trade-off suggests a practical tuning rule for deployment—choose $\\xi$ and $\\eta$ from a computational budget rather than the physical sensing range, since the theorem quantifies exactly how much suboptimality each unit of belief radius removes.","Editorial extension: Because only the Dependence Time buffer and the four consistency inequalities are used, the same exponential-transfer argument should carry over to other local-interaction models, such as factor graphs or communication-limited planners, provided a similar $V>R$ buffer exists.","Editorial extension: The memory-based extraction algorithm's failure cases in stochastic and out-of-view-agent simulations point to a testable improvement—keeping confidence-weighted or particle memories and dropping low-confidence estimates—and the paper notes that such variants remain valid extraction methods."],"forward_implications":["Every policy in the Extended Cutoff Policy Class is exponentially close to optimal: the gap $V^*(s)-V^\\pi(s)$ decays like $\\gamma^{\\lfloor (V_{\\mathrm{exec}}-R)/2\\rfloor}$, matching the existing lower bound up to constants.","The class unifies the Amalgam, Cutoff, and First-Step Finite Horizon Optimal policies as special cases of Trivial Extraction with different $\\xi$ and $\\eta$.","In the generalized setting with local transition dependence and extended reward dependence, the same exponential guarantee holds, with the constant depending on the number of agents.","Simple Memory Based Extraction resolves Penalty Jittering in the fixed-visibility regime; when the environment is deterministic and all agents start in view, increasing $\\xi$ and $\\eta$ makes the partially observable policy attain the fully observable joint optimum.","Once the extended cutoff solution is computed, any valid extraction method yields a new near-optimal policy without additional computation."],"supporting_citations":[{"why":"Defines the Locally Interdependent Multi-Agent MDP, the three previous closed-form policies, and the lower bound that the new class must match.","marker":"DeWeese and Qu [2024]"},{"why":"Gives the Dec-POMDP formulation whose NEXP-completeness motivates the structured subclass studied here.","marker":"Oliehoek [2012]"},{"why":"Provides the complexity categorization used to justify structural assumptions over general Dec-POMDPs.","marker":"Goldman and Zilberstein [2004]"},{"why":"Establishes NEXP-completeness of decentralized MDP control, the hardness baseline for the paper's tractability claim.","marker":"Bernstein et al. [2002]"},{"why":"The centralized-training/decentralized-execution idea whose fully centralized computation limit the Extended Cutoff Policy Class resembles.","marker":"Lowe et al. [2017]"},{"why":"An application with a small, fixed visibility regime that motivates the paper's small-visibility analysis.","marker":"Long et al. [2018]"},{"why":"A robot-navigation application with local observability, another motivating instance for the fixed-visibility regime.","marker":"Han et al. [2020]"}],"fun_headline_variants":["Extended cutoff policies think beyond visibility for near-optimal control","Near-optimal closed-form policies that remember out-of-view agents","First near-optimal policy class for locally interdependent MDPs","Closed-form policies that beat visibility limits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the four Consistent Performance Policy inequalities in Appendix D, which the paper asserts are trivially satisfied by the optimal finite-horizon cutoff policy without providing a proof; if any one of those inequalities fails, Lemma 6 no longer holds and the exponential closeness guarantee has no support.","fun_headline_variants_meta":{"raw":{"variants":["Extended cutoff policies think beyond visibility for near-optimal control","Near-optimal closed-form policies that remember out-of-view agents","First near-optimal policy class for locally interdependent MDPs","Closed-form policies that beat visibility limits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000867,"raw_usage":{"total_tokens":3822,"prompt_tokens":1075,"completion_tokens":2747,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":691,"completion_tokens_details":{"reasoning_tokens":2682}},"tokens_in":691,"tokens_out":2747,"duration_ms":18939,"temperature":1.0,"reasoning_tokens":2682,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:44:59.570998+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate the optimal finite-horizon cutoff policy for a small two-agent grid (for example $V=R+2$, $\\gamma=0.9$) and directly compute the four value differences in Appendix D: Constructive, Deconstructive, 1-Step Displaced, and 1-Step Contracted Improvement. A single violation of any of them would falsify the claimed exponential bound, because the proof of Theorem 1 is exactly the chain that converts those inequalities into the bound.","supporting_citations":[],"review_version":1}