{"id":"5fcb7d54-dffa-463b-bc77-aaf4e52edbc1","arxiv_id":"2505.18433","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"Claims the first O(1/T) global optimality guarantee for deep neural actor-critic methods in decentralized multi-agent reinforcement learning, but the central proof conflates Q-function TD errors with advantage functions.","lead":"The paper proposes a decentralized multi-agent actor-critic algorithm with deep neural networks and claims a finite-time global optimality convergence rate of O(1/T). A generalist might read it because it targets a recognized gap between the empirical success of deep multi-agent reinforcement learning and the available theoretical guarantees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (30) conflates the Q-function TD-error with the advantage function; since the TD-error has conditional mean zero when the critic is accurate, Algorithm 1's update direction is not a policy-gradient estimate and Theorem 5.10 does not follow.","rationale":"I read the paper as trying to prove a finite-time global optimality guarantee for decentralized deep actor-critic via a pseudo-centralized analysis. The central load-bearing step is bounding the actor update error ∥d_t−∇J(θ_t)∥, decomposed in Eq. (15). Step 2(c) is the hinge: it must show the empirical TD-error direction approximates the advantage-weighted policy gradient. The paper asserts this in Eq. (30), but the assertion is false under its own definitions: the Q-function TD error has conditional mean zero whenever the critic is close to Qθ, while the advantage is a nonzero centered quantity. This is not an issue of looseness or missing constants; the mean structure of the update direction is wrong. Consequently, the descent lemma in Eq. (9), the induction in Eq. (11), and the final bound in Eq. (37) all rely on an invalid bound on ∥d_t−∇J(θ_t)∥. The experimental section, including the claim that TD-error outperforms Q-values, does not repair this, because the theorem concerns the algorithm as written, not a heuristic variant. I appreciate the novelty of the pseudo-centralized technique and the careful handling of consensus weights; those are genuine contributions, but they do not bridge the missing identification. The reader's weakest assumption identifies exactly this step, and I agree with the rejection; my concern confirms, rather than moves, the reader's verdict.","tokens_in":31562,"tokens_out":8868,"duration_ms":79524,"concrete_test":"Re-derive Eq. (30) from the definitions in Section 3.2 and Algorithm 1: compute E[δ_{t,l}(W*_t)ψ | F_{t,l1}] by conditioning first on (s_{t,l},a_{t,l}), applying the Bellman operator (3), and substituting W*_t satisfying Fact C.3 and Assumption 5.9. The resulting expression is E[(Tπ Qhat−Qhat)ψ | F_{t,l1}], not E[Adv_hat ψ | F_{t,l1}], and it is identically zero when Qhat = Qθ. If this check reproduces the gap, Theorem 5.10 is unsupported. A numerical companion: in a small MDP with known Qθ, replace the critic by the exact Qθ and estimate d_t = M^{-1}Σδψ over large M; the empirical inner product with ∇J(θ) will be near zero, contrary to what Eq. (30) requires.","verdict_should_be":"REJECT","load_bearing_attack":"The central induction in Appendix C bounds ∥d_t−∇J(θ_t)∥ via the chain in Eq. (15). The last link, Step 2(c), requires E[δ_{t,l}(W*_t) ψ | F_{t,l1}] = E[Adv_hat(s_{t,l},a_{t,l};W*_t) ψ | F_{t,l1}] (Eq. (30), with δ defined in Algorithm 1 Line 9 and in the text preceding Eq. (26)). This is not an approximation error: it is an identity that is false under the paper's own Bellman definitions. For any state-action pair, E[r+γQ(s',a';W*) | s,a] = (Tπ Q)(s,a). Hence the conditional expectation of δ = Q−r−γQ' is (Tπ Q−Q)(s,a), which vanishes when W* is the accurately fitted critic asserted by Assumption 5.9 and Fact C.3. The advantage Adv = Q−E_{a∼π}Q is generically nonzero. Thus Eq. (30) replaces a zero-mean quantity by a nonzero one. Because the actor's direction d_t is a normalized average of δ ψ (Algorithm 1 Lines 12–17), all bounds in Eqs. (29)–(36) are built on this identification, and the O(1/T) global-optimality conclusion of Theorem 5.10 collapses. Using the TD target r+γQ' or a V-function TD error would be different and could estimate Q or the advantage, but the paper uses the current-minus-target Q-form consistently, so the proof's Step 2(c) equality is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a deep neural actor-critic algorithm for fully decentralized multi-agent reinforcement learning, in which both the actor and the critic are neural networks and the agents communicate through gossiping/consensus. The main theoretical claim, Theorem 5.10, is that under Assumptions 5.1-5.9, with suitable hyperparameters, Algorithm 1 converges to a neighborhood of the global optimum of the cooperative MARL objective at rate O(1/T), up to terms involving an advantage-compatibility bias epsilon_bias, a critic approximation error epsilon_critic, batch size, consensus iterations, network width, and network depth. The paper also reports ablation experiments on a modified Simple Spread environment and a multi-agent RLHF experiment with LLMs.","tokens_in":31893,"tokens_out":7979,"duration_ms":60606,"significance":"If the main theorem were correct, this would be a significant contribution: it would be, to my knowledge, the first finite-time global-optimality guarantee for decentralized MARL actor-critic methods with nonlinear function approximation, and the pseudo-centralized parameter technique in Remark 6 is a genuinely interesting idea for handling the non-commutativity of nonlinear updates and consensus. The manuscript also deserves credit for attempting to treat Markovian sampling and for conducting experiments beyond toy benchmarks. However, the central proof step is invalid under the paper's own definitions, and this invalidates the main theorem. The experiments, while suggestive, are qualitative and do not directly test the claimed O(1/T) convergence rate, so the contribution currently rests entirely on the theoretical result, which is not established.","major_comments":[{"comment":"The proof replaces the conditional expectation of the TD-error with the advantage function: E[delta_{t,l2}(W*_t) psi | F_{t,l1}] is set equal to E[Adv_hat(s_{t,l2},a_{t,l2};W*_t) psi | F_{t,l1}]. Under the paper's own definitions, delta = Q_hat(s,a;W) - r - gamma Q_hat(s',a';W), so for a critic satisfying Assumption 5.9 the conditional mean of delta is (Q - T^pi Q)(s,a), which is approximately zero by the Bellman equation, while the advantage Q(s,a) - E_{a'~pi}Q(s,a') is generically nonzero. Thus Eq. (30) is not an approximation error but a false identity. Since Algorithm 1's actor direction is built precisely from this TD-error (Algorithm 1, Lines 9-16) and Eq. (30) is the pivotal step converting the Markovian-noise term into a stationary-distribution error, the bounds in Eqs. (32)-(33) and hence Theorem 5.10's O(1/T) global-optimality conclusion do not follow.","section":"Appendix C, Step 2(c), Eq. (30)"},{"comment":"The bound in Eq. (29) concludes that E|delta_{t,l}(W*_t)|^2 = O(epsilon_critic^2) from the pointwise bound |delta| <= ((1+gamma)/(1-gamma)+1) rmax + 2 epsilon_critic. This conclusion is algebraically incorrect: the displayed upper bound contains the constant rmax, so its square is of order rmax^2 and cannot be O(epsilon_critic^2) unless rmax is assumed to scale with epsilon_critic. Moreover, even for the exact Q-function, the TD target r + gamma Q(s',a') has nonzero conditional variance, so E|delta|^2 does not vanish as epsilon_critic -> 0. This invalidates the first term in Eq. (28) and the O(N epsilon_critic^2/M) term in Eq. (33).","section":"Appendix C, Step 2(c), Eq. (29)"},{"comment":"In bounding |Q_hat(s,a;W_bar_t) - Q_hat(s,a;V_bar_t)|, the proof asserts |Q_hat(W_bar_t) - Q_hat(V_bar_t)| <= L_W ||W_bar_t - V_bar_t|| <= L_W O(BD^{1/2}) by appealing to the convexity of B(B). Convexity only implies that both W_bar_t and V_bar_t lie in B(B); it does not imply that their difference is O(BD^{1/2}). The paper never establishes a quantitative closeness between the gossip-averaged pseudo-centralized parameter W_bar_t and the centralized critic output V_bar_t, despite this being one of the paper's central technical claims (Remark 6). Consequently, the O(N B^2 D) term in Eq. (25) and the corresponding terms in Theorem 5.10 are not justified.","section":"Appendix C, Step 2(a), Eqs. (21)-(22)"}],"minor_comments":[{"comment":"There is an extra comma in the displayed formula for delta_k: it reads \"Q_hat(s_k,, a_k; W^i(k))\" and should be corrected.","section":"Algorithm 2, Line 6"},{"comment":"The quantity Adv_hat(s,a;W) is used before being defined; it should be defined explicitly, for example as Q_hat(s,a;W) - E_{a'~pi_theta}Q_hat(s,a';W).","section":"Appendix C, Eq. (30)"},{"comment":"The same symbol W* is used for the stationary point of the locally linearized MSPBE in Fact C.3 and for the parameter achieving uniform approximation in Assumption 5.9; the relationship between these two objects is not proved, and they should at least be distinguished notationally.","section":"Fact C.3 and Assumption 5.9"},{"comment":"The statement uses the proportionality symbol \"proportional to\" without specifying the constant; since the subsequent theorem requires quantitative gradient bounds, the constant (1-gamma)^{-1} should be stated explicitly.","section":"Lemma 4.3"},{"comment":"The theorem statement omits logarithmic factors that appear in the proof, such as log^3 m log K in Eq. (36); the authors should either use big-O-tilde notation consistently or include the full expressions.","section":"Theorem 5.10"}],"recommendation":"reject","confidential_remarks":"The central proof error in Appendix C, Step 2(c), Eq. (30), is decisive: the algorithm's update direction is defined through a TD-error whose conditional mean is zero for an accurate critic, and the proof identifies this with a generically nonzero advantage function. This cannot be repaired by local edits because the actor update direction in Algorithm 1 would need to be changed. The additional variance error in Eq. (29) reinforces that the proof's error terms are not controlled as claimed. The manuscript's claimed first global-convergence result for deep decentralized MARL actor-critic is therefore not established, and I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper is aiming at a real gap: finite-time global optimality for deep neural actor-critic in decentralized MARL. The algorithm is a natural combination of existing pieces—TD-learning with a neural critic, gossiping for consensus, and an actor updated with the consensual TD-error—and the pseudo-centralized parameter trick (Algorithm 3) is an interesting way to decouple consensus from the nonlinear critic update. The authors are also honest about the two embedded error terms, epsilon_bias and epsilon_critic, in the final bound.\n\nUnfortunately the central proof does not go through. In Step 2(c) of Appendix C, Eq. (30), they replace the conditional expectation of the Q-function TD-error delta = Qhat(s,a) - r - gamma*Qhat(s',a') by the expectation of the estimated advantage. Under their own Bellman definitions, when the critic is accurate (their Assumption 5.9), E[delta | s,a] = 0, while the advantage is generically nonzero. So the actor's direction d_t, which is a normalized average of delta times the score function, has zero conditional mean in the accurate-critic limit—it is not a policy-gradient estimate. The entire bound on ||d_t - grad J(theta_t)||, and hence Theorem 5.10, collapses.\n\nThis is not a small technical gap; it is the load-bearing identity. The confusion may stem from the text saying \"advantage functions ... represent the expectation of TD-errors\"—that is true only for the V-function TD error, not for the current-minus-target Q-form used here.\n\nThe experiments are supportive but not decisive: no code or data are released, and the LLM-RLHF plot has no baselines or error bars. The small-scale ablations do match the claimed trends, which is nice.\n\nWho should read this? Anyone working on MARL theory with neural approximation will find the question important and the pseudo-centralized trick worth knowing, but the main result should not be cited as proven. A serious referee would need to see Step 2(c) fixed, likely by redefining the update to use a proper advantage estimator or a V-function TD error, before the claim can stand.\n\nMy recommendation: send it to peer review if the venue is theory-oriented, because the topic is important and the error is subtle; but the verdict will be reject or major revision until the proof is repaired.","headline":"The main theorem rests on a false identification of the Q-function TD-error with the advantage function, so the paper's central claim does not follow; the question is important and the pseudo-centralized idea is worth a look, but the proof needs a major repair.","tokens_in":32525,"tokens_out":4875,"would_cite":false,"duration_ms":36946,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","90C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A decentralized actor-critic method with neural critics converges to a globally optimal joint policy at rate $O(1/T)$ up to fixed approximation biases, matching the rate previously available only for linear function approximation.","keywords":["decentralized multi-agent reinforcement learning","actor-critic","deep neural networks","global optimality","finite-time convergence","consensus gossip","temporal-difference learning","sample complexity"],"falsifier":"On a small two-agent MDP where the exact policy gradient can be computed, train the critic to its stationary point under the projection ball of Fact C.3 and measure the angle between $\\mathbb{E}[\\delta \\psi]$ and $\\mathbb{E}[\\mathrm{Adv}_{\\theta}(s,a)\\psi]$; if the cosine is not close to 1 at the stated width $m = \\Omega(d^3 D^{-11/2})$, the identification inside Step 2(c) fails and the advertised rate needs an extra assumption.","tokens_in":31272,"feed_emoji":"🤖","tokens_out":8507,"duration_ms":65694,"temperature":0.7,"pith_summary":"This paper claims that a fully decentralized multi-agent actor-critic method, where both the policy and the critic are deep neural networks, converges to a globally optimal joint policy at a finite-time rate $O(1/T)$ up to fixed approximation biases, matching the rate previously available only for linear function approximation. The authors argue this closes a gap between practice, where neural-network critics are standard, and theory, where decentralized MARL guarantees had reached only stationarity. They identify the central difficulty as the failure of nonlinear TD updates to commute with consensus averaging, and they control the resulting bias by maintaining a pseudo-centralized parameter used only for analysis. If the claim is right, decentralized neural actor-critic training carries a global, not merely local, convergence guarantee, with sample complexity $O(N^2/\\epsilon^3)$ to reach $\\epsilon$ accuracy.","feed_headline":"Decentralized deep actor-critic hits global optimum at O(1/T)","feed_subtitle":"Finite-time proof matches linear-approximation rates, with sample complexity O(N^2/epsilon^3).","key_machinery":"Three objects carry the proof. First, a pseudo-centralized parameter $\\bar V_t$, updated as if a central agent saw all rewards, bridges the averaged decentralized output $\\bar W_t$ to the stationary point $W^*_t$, because the order of nonlinear TD updates and consensus averaging cannot be interchanged. Second, the gossip-averaged TD-error $\\tilde\\delta^i_{t,l}$ supplies the actor update direction, replacing the unavailable global advantage function through consensus. Third, Lemma 5.7, together with Assumptions 5.5 and 5.6, turns a bound on the update-direction error into a bound on the global suboptimality gap, which is what upgrades stationarity to global optimality. The restart kernel makes the stationary state distribution proportional to the discounted visitation measure, simplifying the policy gradient theorem to an expectation under $\\nu(\\theta)$.","core_discovery":"The paper's central claim is Theorem 5.10: under bounded rewards, a mixing Markov chain, Fisher-non-degenerate policy parameterization, an advantage-compatibility bias $\\epsilon_{bias}$, Lipschitz smoothness, and a universal-approximation critic error $\\epsilon_{critic}$, Algorithm 1 satisfies $\\mathbb{E}[J(\\theta^*)-J(\\theta_T)] = O(T^{-1}) + O(\\sqrt{\\epsilon_{bias}}) + O(\\epsilon_{critic}) + O(N^{1/2} M^{-1/2})$ plus lower-order network and consensus terms, with probability at least $1 - \\exp(-\\Omega(\\log^2 m))$. The proof converts the usual descent lemma, which bounds only $\\|\\nabla J(\\theta_t)\\|$, into a bound on the global optimality gap through Lemma 5.7, $\\sqrt{\\mu}(J(\\theta^*)-J(\\theta)) \\le \\epsilon' + \\|\\nabla J(\\theta)\\|$. The intermediate machinery bounds the distance between the gossip-averaged TD-error direction and the true policy gradient by comparing with a stationary critic parameter $W^*_t$ and a pseudo-centralized parameter $\\bar V_t$.","pith_inferences":["Editorial: Step 2(c) of the proof identifies the conditional expectation of the TD-error with the estimated advantage function; this holds exactly at a Bellman fixed point, but for a finite-width projected network the identification is an additional assumption, so the rate's validity in practice depends on how close that equality is.","Editorial: If the advantage-compatibility assumption (Assumption 5.6) is relaxed or replaced by a natural-policy-gradient objective, the same pseudo-centralized analysis could transfer the result to natural actor-critic and off-policy MARL variants.","Editorial: The multi-agent RLHF experiment fixes the prompt and uses K = M = 1; a natural stress test is to randomize prompts and lengthen dialogues and check whether rewards still increase and whether the gossip exponent predicts the performance gap.","Editorial: The theoretical prediction of weak width dependence and strong depth dependence can be tested directly by sweeping m and D on a small MARL benchmark and comparing reward trajectories to the predicted scaling."],"forward_implications":["With $T = \\Omega(\\epsilon^{-1})$, $M = \\Omega(N \\epsilon^{-2})$, and $K = \\Omega(N^{1/2}\\epsilon^{-1})$, Algorithm 1 reaches $\\epsilon$ global optimality up to the fixed biases with sample complexity $O(N^2/\\epsilon^3)$ and communication complexity $O(\\epsilon^{-1} \\log(N^{3/2}/\\epsilon))$.","The $O(1/T)$ rate matches the linear-approximation decentralized actor-critic baseline, so replacing linear critics with neural networks does not slow the convergence rate in the bound.","In the leading error terms the network depth $D$ appears with negative exponents while the width $m$ appears with tiny exponents $m^{1/32}$ and $m^{-1/24}$, predicting that depth, not width, is the effective accuracy lever.","Increasing gossip rounds shrinks consensus error geometrically, so a finite communication budget keeps the consensus contribution lower-order in the total error.","The consensual TD-error version learns in the Simple Spread experiments, while the Q-value variant does not, confirming the design choice empirically."],"supporting_citations":[{"why":"supplies the neural TD-learning convergence rate used to bound the gap between the pseudo-centralized critic output and the stationary critic parameter.","marker":"(Cai et al., 2019)"},{"why":"supplies the policy-gradient global-optimality lemma that converts gradient norm into suboptimality gap under advantage-score compatibility.","marker":"(Agarwal et al., 2021)"},{"why":"supplies the single-agent DNN actor-critic global convergence analysis and the step-size schedule alpha_t = alpha/t used in Algorithm 1.","marker":"(Gaur et al., 2024)"},{"why":"supplies the linear-approximation decentralized actor-critic with global convergence that this work extends to nonlinear critics.","marker":"(Chen et al., 2022)"},{"why":"supplies decentralized actor-critic stationary-convergence analysis and the consensus-error machinery used as baseline and technical source.","marker":"(Hairi et al., 2022)"},{"why":"supplies the geometric gossip convergence bound behind the consensus terms.","marker":"(Nedic and Ozdaglar, 2009)"},{"why":"supports Assumption 5.5 by showing Fisher-non-degenerate policy parameterizations arise in many settings.","marker":"(Fatkhullin et al., 2023)"},{"why":"supplies the policy gradient theorem and score-function direction used in Lemma 4.3.","marker":"(Sutton et al., 1999)"}],"fun_headline_variants":["Deep actor-critic MARL: first global optimum at O(1/T)","Non-linear actor-critic reaches global optimum in MARL","First O(1/T) global convergence for deep decentralized MARL","Decentralized actor-critic: global optimality in finite time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the gossip-averaged TD-error of the learned critic, used as the actor's descent direction, points in the same direction as the true advantage-based policy gradient; this is exactly true for the true Q-function by the Bellman equation, but for a finite-width projected neural critic it is an unproven identification.","fun_headline_variants_meta":{"raw":{"variants":["Deep actor-critic MARL: first global optimum at O(1/T)","Non-linear actor-critic reaches global optimum in MARL","First O(1/T) global convergence for deep decentralized MARL","Decentralized actor-critic: global optimality in finite time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000543,"raw_usage":{"total_tokens":2616,"prompt_tokens":977,"completion_tokens":1639,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":593,"completion_tokens_details":{"reasoning_tokens":1564}},"tokens_in":593,"tokens_out":1639,"duration_ms":10343,"temperature":1.0,"reasoning_tokens":1564,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:32:23.588549+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small two-agent MDP where the exact policy gradient can be computed, train the critic to its stationary point under the projection ball of Fact C.3 and measure the angle between $\\mathbb{E}[\\delta \\psi]$ and $\\mathbb{E}[\\mathrm{Adv}_{\\theta}(s,a)\\psi]$; if the cosine is not close to 1 at the stated width $m = \\Omega(d^3 D^{-11/2})$, the identification inside Step 2(c) fails and the advertised rate needs an extra assumption.","supporting_citations":[],"review_version":1}