{"id":"b741e3bd-557c-46ad-b97f-358843f5ac77","arxiv_id":"1908.02805","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A distributed homotopy primal-dual algorithm for multi-agent TD learning is proved to converge at O(log^2 T / T) under Markovian sampling, improving on the prior O(1/sqrt(T)) bound for GTD-type methods.","lead":"This paper designs a distributed algorithm that lets a network of agents estimate how good a shared policy is, using only local data and neighbor messages. It proves the algorithm converges faster than earlier methods, even though the data samples arrive in a correlated, Markovian stream.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is not established as stated: Lemma 9 requires a product condition on η1T1, and the proof's final constants absorb K and T1 factors that can add an extra logarithm to the claimed rate.","rationale":"The paper's high-level construction is plausible: the Fenchel-dual saddle formulation, distributed dual averaging, mixing-time analysis, and homotopy restarts are standard and the lemmas move in a credible direction. The most load-bearing issue is not the plausibility of strong convexity but that Theorem 1 as printed is not a consequence of the supplied proof. Lemma 9's hypothesis is on ηkTk; because ηkTk is constant across rounds, this is a product condition on η1T1, while the theorem states separate conditions on η1 and T1. The proof's own derivation invokes a much larger η1 and still does not state the T1 condition. Moreover, the final order-of-magnitude step suppresses K and η1T1 factors; for the natural choice T1 ≈ τ, the network error contributes one more logarithmic factor than the displayed O(log^2 T/T). This is a serious correctness gap, but it is repairable: a corrected theorem with an explicit product condition, explicit constants, and a careful accounting of τ and K may still deliver a 1/T-type rate. I therefore keep the reader's CONDITIONAL verdict rather than moving to REJECT or ACCEPT. Agreement with the reader is partial: they noticed the η1 inconsistency in their rationale, but their 'weakest assumption' emphasizes the practical verification of ρx, whereas I would locate the decisive issue in the restart condition and the missing log factors in the final constants.","tokens_in":25575,"tokens_out":18130,"duration_ms":198869,"concrete_test":"Set ρx = ρy = R = G = L = 1, take Γ = 1 and |log ρ| = 1 so τ = ceil(log2 T)+1, and choose T = 2^20. Verify whether the theorem's displayed hypotheses (η1 = 1/6, T1 = τ, K = log2(1+T/T1)) satisfy Lemma 9's condition ρxη1T1 ≥ 16; they do not. Then repeat the unrolling of (24) with the same parameters using the proof's actual requirement η1 = 64/ρy + 32/ρx, and carry the Kη1T1/TK contribution from Lemma 2 explicitly through to the final bound. If that contribution is not absorbed into C1·log^2(T√N)/(T(1−σ2(W))) with C1 independent of T1 and K, the theorem statement should be amended to include the product condition and the extra logarithmic factors.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 9 (Section IV-B) requires ρx ηk Tk ≥ 16 in every round. Because Algorithm 1 sets Tk = 2^{k-1}T1 and ηk = η1/2^{k-1}, this is exactly the product condition ρx η1 T1 ≥ 16. The theorem, however, states only η1 ≥ 1/(4/ρy + 2/ρx) and T1 ≥ τ, with no condition on the product. For ρx = ρy = 1, the displayed η1 lower bound is 1/6, while τ ≈ log T; for T = 10^6 this gives ρx η1 T1 ≈ 0.17 · 14 ≈ 2.4, well below 16. Thus Lemma 9, the engine of the proof, is not in force for the stated parameter regime. The proof tries to repair this by using η1 ≥ 4/ρ′ = 64/ρy + 32/ρx (Section IV-C), which is more than 500 times larger for unit parameters, and it still omits T1 from the theorem's hypothesis. Separately, the final unrolling of recurrence (24) replaces round-dependent terms by E_K and then calls the constants absolute. Since T1 ≥ τ ≥ log T and K ≈ log(T/T1), the network term in Lemma 2 contains Kη1T1/TK; after multiplying by the log/(1−σ2(W)) factor this contributes G(RL+G)log^3 T/(T(1−σ2(W))) for the natural choice T1 ≈ τ, not the displayed log^2 term. The claimed O(log^2 T/T) order therefore needs to be re-derived with explicit dependence on T1, K, and η1 before Theorem 1 can be accepted as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed policy evaluation in multi-agent reinforcement learning with linear function approximation and Markovian state sampling. It formulates the MSPBE minimization as a distributed stochastic saddle point problem via Fenchel duality, and proposes the Distributed Homotopy Primal-Dual (DHPD) algorithm, which combines distributed dual averaging with homotopy-style restarting (halving the stepsize and doubling the horizon in each round). The main result, Theorem 1, claims an expected optimality-gap bound of order C1 G(RL+G) log^2(T sqrt(N)) / (T(1-sigma_2(W))) + C2 G(G+RL)(1+T1)/T for the final averaged iterates, under Assumptions 1-6, provided eta_1 >= 1/(4/rho_y + 2/rho_x) and T1 >= tau = Theta(log T). This is presented as improving the prior O(1/sqrt(T)) rate for distributed GTD. The paper also reports Mountain Car experiments for N=1 and N=100.","tokens_in":25969,"tokens_out":9620,"duration_ms":93131,"significance":"If Theorem 1 were established as stated, the paper would make a meaningful contribution: it combines homotopy restarting with distributed primal-dual methods, gives an explicit dependence on the network spectral gap, and handles Markovian sampling without an i.i.d. assumption. The paper is self-contained, with clearly stated assumptions and a proof assembled from lemmas; the algorithm is simple and the experiments support the qualitative benefit of the homotopy schedule. However, the main theorem as stated is not supported by the proof: the proof requires stronger parameter conditions, and the final rate derivation omits extra logarithmic factors introduced by the restart schedule. These issues are potentially repairable, but they require a careful re-derivation and a corrected theorem statement.","major_comments":[{"comment":"The theorem states the bound for any eta_1 >= 1/(4/rho_y + 2/rho_x) and T1 >= tau, but the proof of the recurrence for the averaged surrogate gap requires eta_1 >= 4/rho' = 64/rho_y + 32/rho_x, as explicitly used in the sentence after Eq. (23) ('Since eta_1 >= 4/rho' ...'). Moreover, Lemma 9 requires rho_x eta_k T_k >= 16 in every round k. Because eta_k T_k = eta_1 T_1 is constant across rounds, this is a product condition rho_x eta_1 T_1 >= 16 that is absent from the theorem's hypotheses. For instance, with rho_x = rho_y = 1, T = 10^6, and T1 = tau ~ 14, the theorem's lower bound eta_1 >= 1/6 gives rho_x eta_1 T1 ~ 2.3 < 16, so Lemma 9 does not apply. Thus Theorem 1 is not established as stated; the parameter conditions in the theorem and the proof must be reconciled.","section":"Section III-C, Theorem 1 vs Section IV-C"},{"comment":"The final displayed bound in the proof of Theorem 1 claims the order C1 G(RL+G) log^2(T sqrt(N)) / (T(1-sigma_2(W))) + C2 G(G+RL)(1+T1)/T. However, the network term inherited from Lemma 2 contains (G/T_K) * (sum_{l=1}^K eta_l T_l) * log(sqrt(N) T_K) / (1-sigma_2(W)) = G K eta_1 T_1 log(...) / (T_K (1-sigma_2(W))). Since T_K >= T/2, K <= 1 + log(T/T1), and T1 >= tau = Theta(log T), this term is Theta(G log^3 T / (T(1-sigma_2(W)))) for the natural choice T1 = tau recommended in Remark 4. The proof's step 'K <= 1 + log(T/T1)' and the subsequent absorption of factors into the constants C1 and C2 do not resolve this, because C1 and C2 are claimed to be independent of T. The stated O(log^2 T / T) rate is therefore not derived; the proof yields an extra logarithmic factor unless T1 is O(1), which is incompatible with T1 >= tau. The rate needs to be re-derived with explicit dependence on T1, K, and eta_1.","section":"Section IV-C, unrolling of recurrence (24)"}],"minor_comments":[{"comment":"The abstract and the introduction claim an O(1/T) convergence rate, whereas Theorem 1 states a bound of order log^2(T sqrt(N))/T. Please align the abstract and the claimed rate with the precise theorem statement.","section":"Abstract and Section I-B"},{"comment":"Remark 4 recommends choosing T1 = tau and claims this gives O(log^2(T sqrt(N))/T). In view of Major Comment 2, this choice makes the network term of order O(log^3 T / T) as the proof currently stands; the remark is not justified by the proof.","section":"Remark 4"},{"comment":"The sentence 'Since eta_1 >= 4/rho' and T1 >= 1, we have rho' eta_k T_k >= 4 ... Clearly, the assumption rho_x eta_k T_k >= 16 holds' introduces a condition on eta_1 that is not stated in Theorem 1. The theorem and the proof should state the same condition on eta_1, and the role of the product condition rho_x eta_1 T_1 >= 16 should be made explicit in both places.","section":"Section IV-C, parameter consistency"},{"comment":"The strong convexity parameter rho_x of the local MSPBE is load-bearing for the restart schedule through the condition rho_x eta_k T_k >= 16. The paper does not discuss how rho_x can be verified or estimated in practice, nor the behavior when features are redundant or ill-conditioned so that rho_x is zero or tiny. A remark on this limitation would help the reader assess the applicability of the result.","section":"Assumption 4 / Section III-B"}],"recommendation":"major_revision","confidential_remarks":"The mismatch between the theorem's hypotheses and the proof's actual requirements is substantial: the stated bound is not derived under the stated conditions, and the claimed logarithmic order appears to be off by one factor. The authors should carefully re-derive the convergence rate with explicit dependence on T1, K, and eta_1, and restate Theorem 1 accordingly. The paper is otherwise well structured and the algorithmic idea is sound, so I see the issues as repairable within the manuscript's scope rather than grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper is worth taking seriously, but not as written: the main theorem is not proven under the stated parameter conditions, and the proof's own rate has an extra logarithmic factor that the display hides.\n\nWhat's actually new: a homotopy-restart distributed primal-dual algorithm for MSPBE minimization with Markovian sampling, aiming for O(log^2 T/T). That is a real step beyond the O(1/sqrt(T)) GTD results in [13], [48]. The Fenchel-dual saddle-point formulation is clean; the network averaging and ergodic mixing analysis are worked through in detail. The paper is self-contained: the rate is derived from Assumptions 1-6, not fitted. Credit where due: the homotopy plus distributed dual averaging synthesis is non-obvious, and the Markov-chain treatment is careful.\n\nThe first soft spot is load-bearing. Theorem 1 states eta1 >= 1/(4/rho_y+2/rho_x) and T1 >= tau. Lemma 9, the core of the proof, requires rho_x * eta_k * T_k >= 16 in every round, which (given eta_k = eta1/2^{k-1} and T_k = 2^{k-1}T1) is exactly rho_x * eta1 * T1 >= 16. The theorem never states that product condition, and the proof switches to the much stronger guarantee eta1 >= 4/rho' = 64/rho_y + 32/rho_x (for unit parameters, 96 instead of 1/6). As stated, Lemma 9 may not be in force for parameters satisfying the theorem. This is repairable by adding the product condition, but it must be fixed.\n\nThe second issue is the final rate. The unrolling in Section IV-C contains sum_{l=1}^K eta_l T_l = K * eta1 * T1, and with T1 ~ tau ~ log T and K ~ log T, the network term in Lemma 2 contributes log^3 T / (T(1-sigma_2(W))) to the displayed bound, not the log^2 term. The proof's \"order\" claim hides this. Again repairable, either by tracking the extra log or by a sharper bound, but the displayed theorem is misleading.\n\nMinor: the abstract says O(1/T) while the theorem itself has log^2; the experiments are illustrative only (no code, no error bars); and the strong convexity parameter rho_x is assumed known with no guidance on estimating it.\n\nWho this is for: people working on distributed TD/GTD and primal-dual RL theory. The paper deserves a serious referee after a revision that reconciles Theorem 1 with the proof and states the rate honestly. Send it to review, but expect a major revision.","headline":"A genuinely promising homotopy primal-dual algorithm for distributed GTD, but Theorem 1 as stated is not proven: the key lemma's product condition is missing and the displayed log^2 rate hides an extra log.","tokens_in":26509,"tokens_out":4677,"would_cite":false,"duration_ms":47454,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"A distributed homotopy primal-dual algorithm achieves an O(log^2 T / T) optimality gap for multi-agent TD learning.","keywords":["multi-agent reinforcement learning","temporal-difference learning","mean-square projected Bellman error","stochastic primal-dual method","homotopy method","Markovian sampling","distributed optimization","policy evaluation"],"falsifier":"Run DHPD on a fixed policy-evaluation problem with a feature dictionary chosen so that $A^T C^{-1} A$ has a known small or zero smallest eigenvalue, and compare the empirical optimality gap to $1/T$ and $1/\\sqrt{T}$ curves. If the gap still decays as roughly $1/T$ when $\\rho_x$ is zero, the strong-convexity assumption is not load-bearing; if the decay slows visibly as $\\rho_x$ shrinks, that confirms Theorem 1's rate is tied to Assumption 4 rather than to the algorithm's averaging structure.","tokens_in":25398,"feed_emoji":"🤖","tokens_out":11617,"duration_ms":105034,"temperature":0.7,"pith_summary":"The paper develops a distributed algorithm for multi-agent temporal-difference learning in which agents share observed states but keep local actions and rewards private, and it proves a finite-time guarantee for minimizing the mean-square projected Bellman error (MSPBE) under Markovian, not i.i.d., sampling. The central claim is that the proposed distributed homotopy primal-dual (DHPD) algorithm attains an expected optimality gap of $O(\\log^2 T / T)$ after $T$ total iterations, improving the previous best $O(1/\\sqrt{T})$ for distributed gradient temporal-difference methods. This matters because policy evaluation is the inner loop of many multi-agent reinforcement learning systems: a faster rate means the same number of samples buys a more accurate value-function estimate, with the cost of network size and topology made explicit.","feed_headline":"Distributed TD learning now converges in O(log^2 T / T)","feed_subtitle":"A homotopy primal-dual schedule lets networked agents evaluate policies faster than the old O(1/sqrt(T)) bound.","key_machinery":"The central object is the MSPBE objective $f(x) = \\tfrac{1}{2}\\|Ax - b\\|^2_{C^{-1}}$ together with its Fenchel-dual saddle point reformulation, in which each local cost $f_j(x) = \\max_{y_j \\in Y}\\, [ y_j^T(Ax - b_j) - \\tfrac{1}{2} y_j^T C y_j ]$. This reformulation is what makes the problem amenable to stochastic gradient sampling, because products and inverses of expectations become linear in the samples. The proof is carried by three mechanisms: a doubly stochastic mixing matrix $W$ that performs consensus averaging in the primal updates; distributed dual averaging that controls the network disagreement term; and a homotopy restart schedule ($\\eta_{k+1} = \\eta_k/2$, $T_{k+1} = 2T_k$) that, combined with strong convexity in $x$ and strong concavity in $y$, turns the $O(1/\\sqrt{T})$ primal-dual gap into an $O(1/T)$ gap. The Markovian part of the analysis splits each inner loop into a stationary segment and a short mixing tail of length $\\tau$, leveraging a total-variation mixing-time bound.","core_discovery":"The paper claims that minimizing the mean-square projected Bellman error over a connected network can be recast, via Fenchel duality, as a decentralized stochastic saddle point problem whose objective is convex in the parameter $x$ and strongly concave in the dual variables $y_j$. The DHPD algorithm solves this problem with distributed dual averaging for the primal update, local dual updates, and a homotopy schedule that halves the learning rate and doubles the inner horizon after each round. Its Theorem 1 bounds the averaged expected optimality gap by $C_1 G(RL+G)\\log^2(T\\sqrt{N})/(T(1-\\sigma_2(W))) + C_2 G(G+RL)(1+T_1)/T$, giving $O(\\log^2 T / T)$ when the initial horizon is constant. This is the paper's advertised improvement over the $O(1/\\sqrt{T})$ rate of prior distributed GTD algorithms, and it holds with samples drawn from a causal on-policy Markov trajectory rather than from the stationary distribution directly.","pith_inferences":["A testable consequence the paper does not draw: on feature dictionaries that are redundant or ill-conditioned, $\\rho_x$ is small, and the observed convergence should degrade from roughly $1/T$ toward $1/\\sqrt{T}$; whitening the features before running DHPD would directly test whether strong convexity is the operative mechanism.","The homotopy restart schedule is portable: any distributed stochastic saddle point problem with a strongly convex primal and strongly concave dual could inherit the $O(1/T)$ rate, and the same schedule could be tuned to the spectral gap of the network rather than to a worst-case mixing time.","The paper's assumption of a doubly stochastic mixing matrix excludes directed or time-varying networks; for those, the consensus error term changes, and the rate would likely slow unless the restart schedule is adapted.","An empirical diagnostic not reported: plotting the optimality gap against $1/T$ for different values of $\\rho_x$ would show a phase transition that separates the regime where Theorem 1 applies from the regime where the old $O(1/\\sqrt{T})$ bound is the best available description."],"forward_implications":["For a single agent, DHPD reduces to a fast GTD-type method whose $O(\\log^2 T / T)$ bound improves the earlier $O(1/\\sqrt{T})$ finite-sample guarantees in the Markov setting.","On a ring network the bound scales as $O(N^2 \\log^2 T / T)$, so the price of decentralization is explicit: the same accuracy needs roughly a factor $N^2$ more iterations as the number of agents grows.","The rate matches, up to logarithms, the optimal $O(1/T)$ for stochastic convex optimization, indicating that further gains would require new structure rather than parameter tuning.","The per-iteration cost is $O(d N^2)$ ($O(d)$ per agent), so the faster convergence is not purchased at the price of prohibitive communication or computation.","Because the guarantee covers Markovian on-policy sampling, the algorithm applies directly to online data streams where agents cannot resample from the stationary distribution."],"supporting_citations":[{"why":"It casts MSPBE as a convex-concave saddle point objective, which is the starting reformulation the paper extends to a decentralized setting.","marker":"[33]"},{"why":"It supplies the robust stochastic approximation analysis and the online gradient descent lemma used for the primal-dual gap.","marker":"[34]"},{"why":"It provides the finite-sample GTD analysis in the Markov setting that DHPD generalizes to distributed agents.","marker":"[35]"},{"why":"It is the distributed GTD algorithm with $O(1/\\sqrt{T})$ rate that Theorem 1 improves upon.","marker":"[13]"},{"why":"It gives the distributed dual averaging method and the network disagreement bound used in Lemma 2.","marker":"[45]"},{"why":"It provides the homotopy restart technique that inspired the learning-rate and horizon schedule.","marker":"[46]"},{"why":"It supplies the ergodic mirror descent framework used to handle Markovian samples and mixing times.","marker":"[49]"}],"fun_headline_variants":["Multi-agent TD learning hits O(log^2 T / T) rate","Homotopy primal-dual method accelerates distributed TD","Networked agents evaluate policies at O(1/T) speed","Distributed TD breaks O(1/√T) barrier with homotopy","Faster policy evaluation: O(1/T) for multi-agent TD"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof requires each local cost $f_j(x)$ to be strongly convex with a known curvature $\\rho_x > 0$, which holds only when the feature matrix $A$ is full column rank and $A^T C^{-1} A$ is positive definite; with redundant or ill-conditioned features, $\\rho_x$ is zero or tiny, and the $O(\\log^2 T / T)$ rate is not delivered.","fun_headline_variants_meta":{"raw":{"variants":["Multi-agent TD learning hits O(log^2 T / T) rate","Homotopy primal-dual method accelerates distributed TD","Networked agents evaluate policies at O(1/T) speed","Distributed TD breaks O(1/√T) barrier with homotopy","Faster policy evaluation: O(1/T) for multi-agent TD"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000236,"raw_usage":{"total_tokens":1507,"prompt_tokens":953,"completion_tokens":554,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":569,"completion_tokens_details":{"reasoning_tokens":462}},"tokens_in":569,"tokens_out":554,"duration_ms":5738,"temperature":1.0,"reasoning_tokens":462,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:34:34.499520+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DHPD on a fixed policy-evaluation problem with a feature dictionary chosen so that $A^T C^{-1} A$ has a known small or zero smallest eigenvalue, and compare the empirical optimality gap to $1/T$ and $1/\\sqrt{T}$ curves. If the gap still decays as roughly $1/T$ when $\\rho_x$ is zero, the strong-convexity assumption is not load-bearing; if the decay slows visibly as $\\rho_x$ shrinks, that confirms Theorem 1's rate is tied to Assumption 4 rather than to the algorithm's averaging structure.","supporting_citations":[{"cited_title":"Finite-sample analysis of proximal gradient TD algorithms,","cited_arxiv_id":null,"evidence_quote":"It casts MSPBE as a convex-concave saddle point objective, which is the starting reformulation the paper extends to a decentralized setting."},{"cited_title":"Robust stochastic approximation approach to stochastic programming,","cited_arxiv_id":null,"evidence_quote":"It supplies the robust stochastic approximation analysis and the online gradient descent lemma used for the primal-dual gap."},{"cited_title":"Finite sample analysis of the GTD policy evaluation algorithms in Markov setting,","cited_arxiv_id":null,"evidence_quote":"It provides the finite-sample GTD analysis in the Markov setting that DHPD generalizes to distributed agents."},{"cited_title":"Primal-dual algorithm for distributed reinforcement learning: distributed GTD,","cited_arxiv_id":null,"evidence_quote":"It is the distributed GTD algorithm with $O(1/\\sqrt{T})$ rate that Theorem 1 improves upon."},{"cited_title":"Dual averaging for distributed optimization: Convergence analysis and network scaling,","cited_arxiv_id":null,"evidence_quote":"It gives the distributed dual averaging method and the network disagreement bound used in Lemma 2."},{"cited_title":"A proximal-gradient homotopy method for the sparse least-squares problem,","cited_arxiv_id":null,"evidence_quote":"It provides the homotopy restart technique that inspired the learning-rate and horizon schedule."},{"cited_title":"Ergodic mirror descent,","cited_arxiv_id":null,"evidence_quote":"It supplies the ergodic mirror descent framework used to handle Markovian samples and mixing times."}],"review_version":1}