REVIEW 4 major objections 3 minor 38 references
Single-Loop Federated Actor-Critic across Heterogeneous Environments
T0 review · 4 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read Single-loop federated actor-critic provably converges to a near-stationary point of the average return, with a linear speedup in the number of agents and a residual error proportional to environment heterogeneity.
desk verdict A real gap in the FRL literature tackled with a sensible algorithm, but the critic contraction proof rests on an unproven and likely mis-stated Lemma 1, so the main theorem is not yet supported. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Two objects carry the argument. The first is the average-MSPBE gradient identity. For linear value approximation with features $\phi(s)$, the global critic objective is the average mean-squared projected Bellman error, and its gradient can be written as a single TD gradient $g(\omega) = \frac{1}{N}\sum_i \left[\Phi^T D_i(\gamma P_i-I)\Phi\omega + \Phi^T D_i R_i\right] = \Phi^T D_*(\gamma P_*-I)\Phi\omega + \Phi^T D_* R_*$, with $D_*$ and $P_*$ weighted averages of the agents' stationary distributions and transition kernels (Lemma 1). This identity makes a biasing term in the inner-product decomposition (13) cancel, removing a non-vanishing bias that earlier federated TD analyses had to carry. The second is the five-term decomposition of the actor's gradient bias: lower-level critic error, local Markovian variance, gradient heterogeneity, smoothness of the drifting critic fixed point, and critic approximation error. These are assembled into the Lyapunov function $V_k = -J(\theta_k) + \|\omega_k-\omega^*_k\|^2$, whose decrease over one outer round yields the theorem.
What would settle it
Take a small two-agent tabular MDP with different transition kernels and features, form $\phi(s)$, $D_i$, $P_i$, and test Assumption 4 by computing the eigenvalues of the averaged TD matrix $\Phi^T D_*(\gamma P_*-I)\Phi$; if any eigenvalue has positive real part, the averaged gradient is not attracting and the recursion in Proposition 1 would not contract. Running FedC on that instance and observing the critic error fail to decrease at the predicted rate would falsify the theorem's reach as stated, unless the instance violates an assumed condition. A synthetic search over random heterogeneous MDPs for such an eigenvalue would settle whether Assumption 4 follows from Assumptions 1–3.
Extended reading notes
Core claim
The paper establishes that SFAC converges to a near-stationary point of the mixture-environment objective. Theorem 1 states that with step sizes $\alpha_k, \beta_k = O(\sqrt{N/K})$, the average squared gradient norm satisfies $\frac{1}{K}\sum_{k=1}^K E\|\nabla J(\theta_k)\|^2 \le O(1/\sqrt{NK}) + O(H^2/M) + O(\kappa^2) + O(\xi_{\mathrm{critic}})$, where $H^2/M$ is the variance from Markovian mini-batch gradient estimates, $\kappa^2$ is the environment-heterogeneity constant from Assumption 1, and $\xi_{\mathrm{critic}}$ is the critics' approximation error. The critic's lower-level error is not removed by decoupling: the proof tracks the drift of the critic fixed point as the policy changes and shows the biased term cancels in the actor update through the global gradient of the average mean-squared projected Bellman error. Proposition 1 gives the per-round contraction of the federated critic, with a noise term scaled by $1/N$ that produces the linear speedup. The residual bias is asymptotically proportional to the heterogeneity constant $\kappa^2$ and vanishes in identical environments.
Load-bearing premise
The load-bearing premise, introduced only in the supplementary material as Assumption 4, is that the averaged critic objective satisfies $\langle g(\omega), \omega-\omega^*\rangle \le -\frac{\lambda}{2}\|\omega-\omega^*\|^2$ for some $\lambda>0$—in plain terms, it attracts every iterate toward the shared optimum with a force proportional to the distance from it—so if the averaged heterogeneous TD problem lacks that attraction, the critic contraction in Proposition 1 and the smoothness lemmas used in Theorem 1 fail, and the convergence bound collapses.
Editorial extensions
If this is right
- With identical environments ($\kappa=0$), reaching gradient norm $\epsilon$ needs $K \approx 1/(N\epsilon^2)$ outer rounds, so $N$ agents reduce the number of rounds by a factor $N$.
- In heterogeneous environments, the asymptotic error floor $O(\kappa^2)+O(\xi_{\mathrm{critic}})$ means that no amount of federation can drive the shared policy to an exact stationary point; the floor is set by environment differences and critic approximation power.
- The bound holds under Markovian sampling directly: the $H^2/M$ variance term is controlled by the actor mini-batch size $M$, and the proof does not require independent and identically distributed samples.
- The single-loop structure removes the double-loop requirement of an accurately converged critic at each policy; instead, the critic's memory carries over, and the bias from the moving critic target is bounded by the analysis.
Reading between the lines
- Editorial inference: the same five-term bias decomposition should carry over to natural-actor-critic or entropy-regularized variants, because the cancellation of the lower-level bias uses only the average-MSPBE gradient identity, not the specific policy parameterization.
- Editorial inference: client selection in federated reinforcement learning could be guided by the heterogeneity constant $\kappa^2$; the theorem suggests that admitting an environment far from the current average directly raises the asymptotic bias, so distributional distance of transition and reward models should inform participation.
- Editorial inference: a sharper version of the bound may exist in which $\kappa^2$ is replaced by the sum of per-agent deviations from the mean TD operator, which would predict how the bias interpolates between the homogeneous case and the fully heterogeneous case.
- Editorial inference: whether the $O(\kappa^2)$ floor is tight can be tested numerically by comparing the theorem's heterogeneity term with the empirical eigenvalue spread of the averaged TD matrix on random MDPs; a loose $\kappa^2$ would suggest the heterogeneity bias is an artifact of Assumption 1's coarse constant.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes SFAC, a single-loop federated actor-critic algorithm for learning a shared policy across heterogeneous environments. Federated critics (FedC) run local TD updates with multiple local iterations and are aggregated after each communication round; federated actors (FedA) use the aggregated critic to estimate policy gradients, which are then averaged by a server. The authors claim a finite-time bound on the average squared norm of the mixture-environment policy gradient, of order O(1/sqrt(NK)) plus terms depending on environment heterogeneity, and a linear speedup in the number of agents. The proofs rely on an average-MSPBE formulation of the critic, a contraction property of the averaged TD gradient, and Lipschitz continuity of the critic fixed point, and the analysis uses a five-term decomposition of the actor gradient bias. Experiments on Lunar Lander and Cartpole compare SFAC with A3C.
Significance. If the main theorem were correct, this would be the first finite-time convergence result for federated actor-critic with heterogeneous environments, Markovian sampling, and multiple local updates, and the claimed linear speedup would be both theoretically and practically notable. The algorithm is clearly described, and the proof strategy of decomposing the gradient bias into five terms in Eq. (12) is a reasonable way to address the two-level coupling. However, the central claim is not supported by the proof as written: the key condition on the averaged TD gradient (Assumption 4) is introduced only in the supplementary, and its only justification (Lemma 1) is invalid. Because Proposition 1, Theorem 1, and the smoothness lemmas all depend on this condition, the main convergence result remains unproven.
major comments (4)
- [Supplementary Materials, Lemma 1 and Assumption 4] The construction of the averaged Markov chain in Lemma 1 is invalid. With D* = (1/N) sum_i D_i and P* = (sum_i D_i)^{-1} sum_i D_i P_i, one obtains D*P* = (1/N) sum_i D_i P_i, which is not equal to D* unless sum_i D_i P_i = sum_i D_i. Thus D* is not the stationary distribution of P* in general, so the identity g(omega) = Phi^T D* R* + Phi^T D* (gamma P* - I) Phi omega is not justified by any sampling process. Consequently, Assumption 4, which asserts that the averaged gradient satisfies <g(omega), omega - omega*> <= -(lambda/2)||omega - omega*||^2, is an unverified ad hoc condition. Since Proposition 1 and Theorem 1 depend on lambda from Assumption 4, this gap is load-bearing and not a matter of constant tuning.
- [Proposition 1 and Theorem 1] Proposition 1 is stated under Assumptions 1 and 3 only, but the proof in the supplementary invokes Assumption 4 to obtain the contraction factor (1 - beta upsilon lambda / 4). Because Assumption 4 is not among the main-text assumptions and is not stated as an assumption of Proposition 1, the proposition is not derived from its stated hypotheses. The same issue affects Theorem 1, which lists only Assumptions 1-3 even though its proof relies on the same condition. Either the theorem must include the new condition explicitly, or a contraction must be proven without it.
- [Proof of Theorem 1, Lemmas 5-6] The Lipschitz continuity of the critic fixed point omega*(theta) and its Jacobian in Lemmas 5 and 6 of the supplementary are imported from Chen et al. (2021) under exactly the same Assumption 4. Because Assumption 4 has no valid derivation for the averaged heterogeneous TD problem, the bounds on J21, J22, and J3 in the proof of Theorem 1, which control the cancellation of the critic bias in the actor update, are not established. Thus the final O(1/sqrt(NK)) rate is unsupported.
- [Supplementary Materials, Proof of Proposition 1] The supplementary proof of Proposition 1 ends with a recursion of the form E||omega_t - omega*||^2 <= (1 - lambda beta bar-upsilon / 4)^t E||omega_0 - omega*||^2 + C1 beta^3 + C2 chi^2 + C3 beta / N + C4 beta, whereas the main text states a one-step contraction with error terms C1 beta^4 + C2 beta^3 + C3 beta^2 / N + C4 beta^2. The powers of beta do not match, and no mapping from the supplementary constants to the stated C1-C4 is given. As a result, the supplementary material does not establish Proposition 1 as stated in the main text.
minor comments (3)
- [Eq. (13)] The label 'decent direction' should be 'descent direction'.
- [Experiments] The comparison baseline is described as 'A3C (Shen et al. 2023)', which is ambiguous because Shen et al. is an analysis of asynchronous advantage actor-critic rather than the original A3C algorithm; the experimental setup should clarify which implementation and variant is used.
- [Figures 1-2] The figures would benefit from full axis labels and error bars; the current captions are minimal and do not state the number of seeds or the variance across runs.
Circularity Check
No circular derivation: the theorem is an independent finite-time bound; the only self-citation is a related-work reference and is not load-bearing.
full rationale
SFAC's convergence proof does not fit parameters and then predict them, and it does not define its target in terms of its outputs. The critic bound (Proposition 1) is derived from Assumptions 1 and 3 together with the supplementary Assumption 4; the actor bound (Theorem 1) follows from a five-term variance decomposition and imported external lemmas (Chen-Sun-Yin, Xu-Wang-Liang, Bhandari-Russo-Singal). The only self-citation (Zhu and Gong 2023) appears in the related-work enumeration and is not used to justify the main convergence result. Several correctness gaps exist: Assumption 4 is not listed with Assumptions 1-3 in the main text; Lemma 1's averaged-transition matrix P* is only asserted to be irreducible and is not shown to have D* as its stationary distribution; and some constants (Li, L_lambda, etc.) are not fully specified. These are unproved or missing assumptions, however, not circular reductions of the conclusion into the hypotheses. No equation in the derivation is equal to the claimed rate by construction, and no fitted quantity is renamed as a prediction.
Assumptions & free parameters
assumptions (8)
- domain assumption Assumption 1: bounded gradient heterogeneity with constants chi^2 >= 1, kappa^2 >= 0
- domain assumption Assumption 2: score function and policy are Lipschitz and bounded
- domain assumption Assumption 3: Markov chains induced by each policy and environment are aperiodic and irreducible with geometric mixing
- domain assumption Assumption 4 (unstated in main text): <g(omega), omega - omega*> <= -lambda/2 ||omega - omega*||^2 for the average MSPBE gradient
- standard math Existence and Lipschitz continuity of omega*(theta) and gradient of omega*(theta) (Lemmas 5,6 from Chen et al. 2021)
- domain assumption J_i(theta) is smooth (Lemma 4)
- domain assumption The projection set H contains all optimal critic parameters omega*, and the initial critic error is bounded
- standard math Feature vectors satisfy ||phi(s)|| <= 1 and columns of Phi are linearly independent
Cite this review
Pith. "Pith review of Single-Loop Federated Actor-Critic across Heterogeneous Environments." pith.science (2026). https://pith.science/paper/5ITGTNJD
@misc{pith2026241214555,
author = {Pith},
title = {Pith review of: Single-Loop Federated Actor-Critic across Heterogeneous Environments},
year = {2026},
howpublished = {\url{https://pith.science/paper/5ITGTNJD}},
note = {Machine review of arXiv:2412.14555}
}
read the original abstract
Federated reinforcement learning (FRL) has emerged as a promising paradigm, enabling multiple agents to collaborate and learn a shared policy adaptable across heterogeneous environments. Among the various reinforcement learning (RL) algorithms, the actor-critic (AC) algorithm stands out for its low variance and high sample efficiency. However, little to nothing is known theoretically about AC in a federated manner, especially each agent interacts with a potentially different environment. The lack of such results is attributed to various technical challenges: a two-level structure illustrating the coupling effect between the actor and the critic, heterogeneous environments, Markovian sampling and multiple local updates. In response, we study \textit{Single-loop Federated Actor Critic} (SFAC) where agents perform actor-critic learning in a two-level federated manner while interacting with heterogeneous environments. We then provide bounds on the convergence error of SFAC. The results show that the convergence error asymptotically converges to a near-stationary point, with the extent proportional to environment heterogeneity. Moreover, the sample complexity exhibits a linear speed-up through the federation of agents. We evaluate the performance of SFAC through numerical experiments using common RL benchmarks, which demonstrate its effectiveness.
Figures
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
Bhandari, J.; Russo, D.; and Singal, R. 2018. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory (COLT)
work page 2018
-
[4]
Chen, T.; Sun, Y.; and Yin, W. 2021. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34: 25294--25307
work page 2021
-
[5]
Chen, X.; and Zhao, L. 2024. Finite-time analysis of single-timescale actor-critic. Advances in Neural Information Processing Systems, 36
work page 2024
-
[6]
Doan, T.; Maguluri, S.; and Romberg, J. 2019. Finite-time analysis of distributed TD (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning, 1626--1635. PMLR
work page 2019
-
[7]
Doya, K. 2000. Reinforcement learning in continuous time and space. Neural Computation, 12(1): 219--245
work page 2000
-
[8]
Fan, X.; Ma, Y.; Dai, Z.; Jing, W.; Tan, C.; and Low, B. K. H. 2021. Fault-tolerant federated reinforcement learning with theoretical guarantee. In Advances in Neural Information Processing Systems, 1007--1021
work page 2021
Show all 38 references
-
[9]
Ghadimi, S.; and Wang, M. 2018. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246
2018 arXiv
-
[10]
Hong, M.; Wai, H.-T.; Wang, Z.; and Yang, Z. 2023. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1): 147--180
2023
-
[11]
Huang, M.; Zhang, D.; and Ji, K. 2023. Achieving linear speedup in non-iid federated bilevel learning. In International Conference on Machine Learning, 14039--14059. PMLR
2023
-
[12]
Jin, H.; Peng, Y.; Yang, W.; Wang, S.; and Zhang, Z. 2022. Federated reinforcement learning with environment heterogeneity. In International Conference on Artificial Intelligence and Statistics, 18--37. PMLR
2022
-
[13]
Khodadadian, S.; Sharma, P.; Joshi, G.; and Maguluri, S. T. 2022. Federated reinforcement learning: Linear speedup under markovian sampling. In International Conference on Machine Learning, 10997--11057. PMLR
2022
-
[14]
R.; Sobh, I.; Talpaert, V.; Mannion, P.; Al Sallab, A
Kiran, B. R.; Sobh, I.; Talpaert, V.; Mannion, P.; Al Sallab, A. A.; Yogamani, S.; and P \'e rez, P. 2021. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 23(6): 4909--4926
2021
-
[15]
R.; and Borkar, V
Konda, V. R.; and Borkar, V. S. 1999. Actor-critic--type learning algorithms for Markov decision processes. SIAM Journal on Control and Optimization, 38(1): 94--123
1999
-
[16]
Kumar, H.; Koppel, A.; and Ribeiro, A. 2023. On the sample complexity of actor-critic method for reinforcement learning with function approximation. Machine Learning, 112(7): 2433--2467
2023
-
[17]
A.; and Peres, Y
Levin, D. A.; and Peres, Y. 2017. Markov chains and mixing times, volume 107. American Mathematical Soc
2017
-
[18]
Qiu, S.; Yang, Z.; Ye, J.; and Wang, Z. 2021. On finite-time convergence of actor-critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2): 652--664
2021
-
[19]
Shalev-Shwartz, S.; Shammah, S.; and Shashua, A. 2016. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295
2016 arXiv
-
[20]
Shen, H.; Zhang, K.; Hong, M.; and Chen, T. 2023. Towards understanding asynchronous advantage actor-critic: Convergence and linear speedup. IEEE Transactions on Signal Processing, 71: 2579--2594
2023
-
[21]
Srikant, R.; and Ying, L. 2019. Finite-time error bounds for linear stochastic approximation andtd learning. In Conference on Learning Theory (COLT)
2019
-
[22]
B.; Yang, Q.; and Yang, Z
Sun, J.; Wang, G.; Giannakis, G. B.; Yang, Q.; and Yang, Z. 2020. Finite-time analysis of decentralized temporal-difference learning with linear function approximation. In International Conference on Artificial Intelligence and Statistics (AISTATS)
2020
-
[23]
S.; McAllester, D
Sutton, R. S.; McAllester, D. A.; Singh, S. P.; and Mansour, Y. 1999. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, 1057--1063
1999
-
[24]
A.; Li, M.; Thrampoulidis, C.; and Oymak, S
Tarzanagh, D. A.; Li, M.; Thrampoulidis, C.; and Oymak, S. 2022. Fednest: Federated bilevel, minimax, and compositional optimization. In International Conference on Machine Learning, 21146--21179. PMLR
2022
-
[25]
J.; and Anderson, J
Wang, H.; Mitra, A.; Hassani, H.; Pappas, G. J.; and Anderson, J. 2023. Federated temporal difference learning with linear function approximation under environmental heterogeneity. arXiv preprint arXiv:2302.02212
2023 arXiv
-
[26]
Wang, J.; Liu, Q.; Liang, H.; Joshi, G.; and Poor, H. V. 2020. Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization. In Advances in Neural Information Processing Systems (NIPS)
2020
-
[27]
Wang, L.; Cai, Q.; Yang, Z.; and Wang, Z. 2019. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01150
2019 arXiv
-
[28]
Williams, R. J. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8: 229--256
1992
-
[29]
Xie, Z.; and Song, S. 2023. FedKL: Tackling data heterogeneity in federated reinforcement learning by penalizing KL divergence. IEEE Journal on Selected Areas in Communications, 41(4): 1227--1242
2023
-
[30]
Xu, T.; Wang, Z.; and Liang, Y. 2020. Improving sample complexity bounds for (natural) actor-critic algorithms. Advances in Neural Information Processing Systems (NeurIPS)
2020
-
[31]
Yang, Y.; Xiao, P.; and Ji, K. 2024. Simfbo: Towards simple, flexible and communication-efficient federated bilevel learning. Advances in Neural Information Processing Systems, 36
2024
-
[32]
Y.; and Juang, B.-H
Ye, H.; Li, G. Y.; and Juang, B.-H. F. 2019. Deep reinforcement learning based resource allocation for V2V communications. IEEE Transactions on Vehicular Technology, 68(4): 3163--3173
2019
-
[33]
Yu, S.; Chen, X.; Zhou, Z.; Gong, X.; and Wu, D. 2020. When deep reinforcement learning meets federated learning: Intelligent multitimescale resource management for multiaccess edge computing in 5G ultradense network. IEEE Internet of Things Journal, 8(4): 2238--2251
2020
-
[34]
A.; Doan, T
Zeng, S.; Anwar, M. A.; Doan, T. T.; Raychowdhury, A.; and Romberg, J. 2021. A decentralized policy gradient approach to multi-task reinforcement learning. In Uncertainty in Artificial Intelligence (UAI), 1002--1012. PMLR
2021
-
[35]
Zhang, C.; Wang, H.; Mitra, A.; and Anderson, J. 2024. Federated temporal difference learning with linear function approximation under environmental heterogeneity. In International Conference on Learning Representations (ICLR)
2024
-
[36]
Zhang, K.; Yang, Z.; and Ba s ar, T. 2021. Decentralized multi-agent reinforcement learning with networked agents: Recent advances. Frontiers of Information Technology & Electronic Engineering, 22(6): 802--814
2021
-
[37]
Zhang, K.; Yang, Z.; Liu, H.; Zhang, T.; and Basar, T. 2018. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference on Machine Learning (ICML), 5872--5881. PMLR
2018
-
[38]
Zhu, Y.; and Gong, X. 2023. Distributed policy gradient with heterogeneous computations for federated reinforcement learning. In 2023 57th Annual Conference on Information Sciences and Systems (CISS), 1--6. IEEE
2023
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.