Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updates
Authors: Guangchen Lan
Han Wang
James Anderson
Christopher Brinton
Vaneet Aggarwal
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement learning
federated learning
TL;DR: We propose a federated reinforcement learning method based on ADMM. The communication complexity of each agent is reduced from $O(d^2)$ to $O(d)$, where $d$ is the number of model parameters.

Abstract: Federated reinforcement learning (FedRL) enables agents to collaboratively train a global policy without sharing their individual data. However, high communication overhead remains a critical bottleneck, particularly for natural policy gradient (NPG) methods, which are second-order. To address this issue, we propose the FedNPG-ADMM framework, which leverages the alternating direction method of multipliers (ADMM) to approximate global NPG directions efficiently. We theoretically demonstrate that using ADMM-based gradient updates reduces communication complexity from $\mathcal{O}({d^{2}})$ to $\mathcal{O}({d})$ at each iteration, where $d$ is the number of model parameters. Furthermore, we show that achieving an $\epsilon$-error stationary convergence requires $\mathcal{O}(\frac{1}{(1-\gamma)^{2}{\epsilon}})$ iterations for discount factor $\gamma$, demonstrating that FedNPG-ADMM maintains the same convergence rate as standard FedNPG. Through evaluation of the proposed algorithms in MuJoCo environments, we demonstrate that FedNPG-ADMM maintains the reward performance of standard FedNPG, and that its convergence rate improves when the number of federated agents increases.

Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updates
Guangchen Lan Purdue University West Lafayette, IN 47907 1an440purdue edu
Han Wang Columbia University
New York, NY 10027 hw27860columbia. edu
James Anderson
Christopher Brinton Purdue University West Lafayette, IN 47907 cgb@purdue.edu
Vaneet Aggarwal Purdue University West Lafayette, 47907
Columbia University
New York, NY 10027
andersonGee columbia. edu
vaneet@purdue.com edu
Abstract
Federated reinforcement learning (FedRL) enables agents to collaboratively train a global policy without sharing their individual data. However, high communication overhead remains critical bottleneck, particularly for natural policy gradient (NPG) methods, which are second-order. To address this issue, we propose the FedNPG-ADMM framework, which leverages the alternating direction method of multipliers (ADMM) to approximate global NPG directions efficiently. We theoretically demonstrate that using ADMM- gradient updates reduces com- munication complexity from (dd) (d) at each iteration, where d the number of model parameters. Furthermore, we show that achieving an e-error stationary convergence requires ( ((T-Tp))) iterations
discount factor y, demonstrating that FedNPG-ADMM maintains the same convergence rate as the standard Fed- NPG. Through evaluation of the proposed algorithms in MuJoCo environments, we demonstrate that FedNPG-ADMM maintains the reward performance of standard FedNPG, and that its convergence improves when the number of federated agents increases.
Introduction
Policy gradient methods are commonly used to solve reinforcement learning (RL) problems in various applications, with recent popular examples being InstructGPT (30 and ChatGPT (GPT-4
291). Although first-order methods, such as Policy Gradient (PG) and Proximal Policy Optimization
(PPO)
40 favored for their simplicity, second-order methods, such Natural Policy Gradient
(NPG)
16 36 and its practical version Trust Region Policy Optimization (TRPO) [38 are often
exhibit superior convergence behavior, e.g., on the Swimmer 400 and Humanoid 10 tasks
in MuJoCo environments [4]. Furthermore, recent works have demonstrated that the convergence guarantees NPG with Kullback-Leibler (KL) divergence constraints (second-orde methods) are superior to those of PG (first-order methods) [21 23), motivating closer inspection for practical use.
Many contemporary RL applications large-scale and rely high volumes of data for model training 20 22 33
conventional approach to enabling training on massive data is transmitting data collected locally by different agents central server, which then be used for policy learning. However, this is not always feasible real-world systems where communication bandwidth
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

is limited and long delays are not acceptable [9 28 such as in edge devices [9, Internet of Things
[ 27], autonomous driving [4T. and vehicle transportation [T] Moreover, sharing individual
data collected by agents raises privacy and legal issues 13 26
Federated learning (FI.) T2 25 offers a promising solution the challenges posed by data central- ization, where agents communicate locally trained models rather than raw datasets. However, FL typically applied to supervised learning problems. Recent work has expanded the scope of FL to federated reinforcement learning (FedRL), where N agents collaboratively learn global strategy without sharing the trajectories they collected during agent-environment interaction 14
50
Federated reinforcement learning has been studied in tabular RL [2] 14, 17), control tasks 48
and for funcciin based algorithms [46] [50], where linear speedup has been demonstrated.
For roolicy-gradien based algorithms. we note that linear speedup is easy to see as the trajectories
collected by each agent could be parallelized.
Efficient state-of-the-art guarantees for federated policy gradient based approaches can be achieved by Federated NPG (FedNPG), which is a second-order method. However, sharing second-order information increases the communication complexity, which is one of the fundamental challenges in Newton-Star/Leam [K] and FedNew 7 have been recently proposed to reduce the communication complexity of second-order methods, typically by approximating Hessian matrices for convex or strongly convex problems. However, federated second-order reinforcement learning has not been investigated. which provides the key motivation for our work. The key question that this paper aims to address is:
FL
2 37. In supervised FL, works including FedNL 337, BL
Can we reduce the communication complexity for second-order federated natural policy gradient approach while maintaining performance guarantees?
We answer this question in the affirmative by introducing FedNPG-ADMM, an algorithm that estimates global NPG directions using alternating direction method of multipliers (ADMM) 8 9 This estimation reduces the communication complexity from ((d)) to (d), where is the number of model parameters. However, it is non-trivial to whether FedNPG-ADD ADMM will maintain similar convergence guarantees as FedNPG. We show in this work that FeMMPG-ADMM indeed does maintain these guarantees, and provides speedup with the number of agents. The key contributions that we make are summarized as follows:
We propose a novel federated NPG algorithm, FedNPG-ADMM, where the global NPG directions are estimated through ADMM.
2. Using the ADMM-based global direction estimation, we demonstrated that the communication complexity reduces by ((d) as compared to transmitting the second-order information (standard FedNPG).
3. We prove the FedNPG-ADMM method achieves an c-error stationary convergence with ( (T- iterations for discount factor y. Thus, achieves the same convergence rate as the standard FedNPG.
Experimental evaluations in MuJoCo environments demonstrate that FedNPG-ADMM maintains the convergence performance of FedNPG. We also show improved performance more federated agents engage in collecting trajectories.
2 Background
Markoy Decision Process: We consider the Markov decision process (MDP) as a tuple (S, A, P, R. 7), where S is the state space, A is a finite action space, P S x A S + IR is a Markov kernel that determines transition probabilities, R x A -> a reward function, and 7 (0, 1) is discount factor. At each time step t, the agent executes an action a, A from the current state s; S, following a stochastic policy म, i.c., at ~ T T-]s;).. For on policy म, state value function is defined
8 Σ 1=0
V*(8)=
E
(1)
(1)
((1pa)))
2

---

Similarly, state-action value function (Q (Q-function) is defined as
Qx( =
E
Σ =
75((,, ax)]00 =8, a0 = a
An advantage function is then define as (s = policy is parametrized by 0 E IR and then the policy referred as Te (Deep RL. parametrizes Ty by deep neural networks). A state-action visitation measure induced by is given as
With continuous states, the
Pay (8. 7)
P's(s = dz a|so, mB)
sampp
t=
where starting state so is drawn from a distribution p. The goal of an agent is to maximize the expected discounted return defined
((0)
E [V (s)]
(4)
s~p
The gradient of (() can be written as
39
Va log To (rxa(1)))) Amp (se, ai)
(0J
E
(5)
where r = (So, ao 81, "1, a trajectory induced by policy wy. We denote the policy gradient by for short. In practice, we can sample (s, oot and obtain the unbiased estimate Arga. (8, a) using Algorithm in [
Natural Policy Gradient (NPG): At the k-th iteration, natural policy methods with trust region
38
update policy parameters as follows
(a(s)) Tax (a|s)
g++1 arg mag E
An (s,
8,0
(6)
s.t. DK <
where
D(0110") E D Toz (-1s))
(7)
D(-) the KL-divergence operation, and 8 > is the radius of the trust region. Practically, using the first-order Taylor expansion for the target value and the second-orde Taylor expansion for the divergence constraint, (6) is expanded as follows
g++1 arg max g T 10-00 (0-04)
s.t. 2 ( 8h) H 8²) I 8,
where H ViDIOI E Rdxd and the individual elements are given by H,j
B0 B0y E. [D(TT( |) ( (-(ss] 0=0i" Using Lagrangian duality, the iterates of NPG ascent are expressed as
g++1 gh
H H
H g.
Federated NPG: FedNPG is paradigm in that N agents collaboratively train common global policy with parameters 0 as illustrated in Figure [ (a). During the training process, each agent computes gradients (and second-order matrices) using its local data; then, the gradients of all agents are transmitted to a central server. In particular, one FedNPG training iteration consists of the following three steps:
3

---

Downlink Transmission: The server broadcasts the current global policy parameters E R to all
N agents.
Collecting its own local data D; based the common policy иæ, each agent i computes its local gradient gi E Rd and second-order matrix H; E Rdxd Then, sends g and
Uplink Transmission:
H; back to the server.
Global Update: The server averages local gradients and second-order matrices to get the global gradient and matrix as follows:
N g
H H;
Σ
gi.
(10)
The server then updates global policy parameters
28
0 A
H g
g.
(11)
H
use [D;] to denote the size of collected data set D. Without loss of generality, we take [D] = |Dxl for simplicity. As proven in [4], gradient update methods are immune to whether
collected data is ii.d., or not.
Update 0
Update
Server
Server
0
0
y1
yN
g1
gN
N
D1
local compute
DN
D
local compute
Dy
(a) FedNPG
(b) FedNPG-ADMM
Figure 1: An illustration of federated learning based on second-order methods with N agents. (a) FedNPG via standard average. In the uplink, transmitting the matrix H, brings (dd)) communication complexity. (b) FedNPG-ADMM in this paper with only ((d) communication complexity.
Bottleneck of Federated NPG:
As shown in Figure each iteration, the server collects (H, E Rddd gi E RRIN from N agents and updates global policy parameters as follows
N
2No
0 0+
(12)
(EN g:) ) (E H.
E
call this method standard average FedNPG. The uplink communication complexity from each agent is (dd)) in each iteration round. As the uplink is highly limited 43 practical when d is large.
applying T2) is not
In the next section. we introduce our ADMM-based approach as shown in Figure I (b), which reduces the communication complexity to (d)) at each iteration and meanwhile keeps convergence performances.
3 FedNPG via ADMM
To minimize the communication overhead in each round of communication, we begin by formulating quadratic problem. The solution to this problem provides the updating direction in (22 follows:

---

N
N
N
arg min
J
gi.
(13)
2
:=1
1=1
1=1
This minimization problem is equivalent
N Σ
min si 1=1
2 H.y y, gi + lly; yll²) s.t. y Yss
(14)
.,,
where 0 is penalty constant and denotes the Euclidean norm. This equivalence transforms the original quadratic problem into a distributed manner and is the key process efficient FedNPG.
Remark: This approach does not aim to approximate the Hessian from each agent, but approximates the global direction (Σi=1 work mentioned in the introduction.
-i= g. directly. Note that this differentiates our approach from
The Lagrangian function associated to optimization problem 14) is
Cly, ( (A. Σ Gy. G.. H.y y. g: + Gll. ly, yll2 (A..i (15)
where {Ax Rdj Ji=1 are dual variables. Next, solve the distributed optimization problem through the alternating direction method of multipliers (ADMM) one-step ADMM given in Algo.
4 The policy update of FedNPG via
Algorithm 1 FedNPG-ADMM
Input: MDP (S,A, R.y) 7); Number of timesteps T; Penalty constant p; Step size 17; Initial 8g E Rdd y E Rd [y. p (Ai e Rd)
1: for 1 K do
2:
Server broadeast
3: Broadcast = and 0k-1 to N agents.
4: Agent update
5:
for each agent E (N) } do in parallel
6:
x + x; + ply
g - D. ΣTED, En (V log T8p (1) (arl)))) Arpe (se, az)
7:
8:
y - (H) + pI)- lg X py*
9:
Transmit y Rd and g E Rd to the server.
10:
end for
11:
Server update
y ΣN
0 c 0k- 1
2N8 8.) y k
end for Output: 0K
Agent computes H, and g: based on locally collected data. At step of ADMM, agent updates
y; line 8 as follows
y H.y yTg: + GIx. - y + A 12) p
y; arg min
(16)
(H. + -l - X; + py),
where IRdxd the identity matrix. In practical implementation, conjugate gradient methods can be used to compute y, for efficiency (Appendix C in (38).
5

---

In line 12, after receiving y; and gi from all N agents, the server updates the global search direction follows
y arg min
Iy,
y/12
(As: Ne yy)
2
(17)
N
12
N Yi-
Dual variables in line 6 are updated by each agent as follows
A + d + ply; - y), i i= "y, N.
(18)
Combining 17 and 18) we have Σ A; = 0.
In line 13 of Algo. D after the ADMM process, the updates global policy parameters, where E (0, 1) is the step size. The server then broadcasts the updated parameters to all N agents at the next iteration.
In every communication round, agent i only transmits y; and gi, with a communication complexity of (dd). In contrast, the standard average approach in (12) requires transmitting H, and gi, with communication complexity of (dd). This efficient communication approach allows second-order methods scalable large-scale systems.
Convergence Analysis
In this section, we derive the convergence rate of FedNPG based on ADMM. In order to derive the guarantees, we make the following standard assumptions 23 31 51 policy gradients, second-order matrices, and rewards.
Assumption 4.1.
1. The score function is bounded as V/ log no(a 8)]l S G, for all E IRd, & E S, and a E A.
2. Policy gradient is M-Lipschitz continuous. In other words, v0,, 0j Rd, E S; and A. have
Ve, log me, (a s) Ve, log me, (a 8) < M |00 0j|1
(19)
3. The reward function is bounded as r(s,a) a) E R), for all s E S, and E AA Assumption 4.2. For all Rd,, the Fisher information matrix induced by policy and initial state distribution p positive definite as
F(0)=
E (s,0)~Vag
[Vo log ma(a s) log (a [] > pr
(20)
for some constant μr > For any two symmetric matrices with the same dimension, &> B denotes the eigenvalues of A B are greater or equal to zero.
Theorem 4.3. For target error of stationary-point convergence, each agent samples O [1 (1-2)=Ne) )
trajectories, and the server obtains the update direction y at each iteration. Choose 1) =
22 (66G and
K (J+ ()= + 16)² + 28G (56G² + L, 56G pr )
0 (
1
(1-11-))) (1-7)pc)
(21)
We have:
K E
VJ (8+) cc
(22)

---

Proof sketch. The main idea in our proof is to show that the approximation error between the updating direction given by FedNPG-ADMM and NPG geometrically decreases up some additional term, which depends on the statistical error. This term appears since we do not have access to the exact gradient. However, it decays at rate proportional to sample size. As a result, FedNPG-ADMM achieves the same convergence rate as NPG as shown by constructing an appropriate Lyapunov function. The complete proof of Theorem 4.3 is given in Appendix
By the definition of stationary points, we need to find a parameter 0 such that E V (0)) < c, for all E >> O. The result in 2 achieves the stationary-poin convergence for policy gradient methods as provided in [5T]. Our approach keeps the sample complexity as that in the NPG method [23] and thanks to the federated scenario we consider, enjoys a much lower communication complexity.
Table 1: Complexity comparison in each agent.
NPG 23
FedNPG
FedNPG-ADMM
Sample complexity
(1-
Ne
[1 7--
Communication complexity
11-7
(1-))=)
We summarize the complexity improvement in Table I Recall in 55) that the estimated gradient
g an average over collected trajectories. The total trajectories Σi=1 [D;] are collected by N agents equally using the common global policy Te at each iteration. Each agent i samples [D,] O (--))-e) at each iteration and enjoys a federated sampling benefit compared to a single agent
with [Dal = O ())))))) During the whole training process, each agent has K KiD = (a-))
sample complexity and K 2d -(1--)7)) communication complexity to achieve stationary convergence.
5 Simulations
Setup: We consider three MuJoCo tasks [4] with the MIT License, which have continuous state spaces. Specifically, a Swimmer-y4 task with small state and action spaces, a Hopper-v4 task with middle state and action spaces, and a Humanoid-v4 task with large state and action spaces are considered as described in Table 3 Policies are parameterized by fully connected multi-layer perceptions (MLPs) with settings in Table 4 We follow the practical settings in TRPO with line search (38], and in stable-haselinest (35] with generalized advantage estimation (0.95) 39 and
the Adam optimizer [18) in our implementation. Convergence performances are measured over 10 runs with random seeds from 0 to 9. The solid lines in Figure 2 and are averaged results, and the shadowed areas are confidence intervals with 95% confidence level. We use Py PoTcc [32] to implement deep neural networks and RL algorithms. The tasks are trained on NVIDIA RTX 3080 GPU with 10 GB of memory.
Performance metrics: We consider performance metrics as follows:
1. Communication overhead: the data size transmitted from each agent;
Rewards: the average trajectory rewards across the batch collected at each iteration;
3. Convergence: rewards versus itcrations during the training process.
We first evaluate the influence of the number of federated agents. In Figure 2, with different numbers of agents, we test the convergence performances of standard average FedNPG in ([2) with (dd) communication complexity and FcdNPG-ADMM in Algo. I with (dd) communication complexity at each iteration. The x-axis denotes the number of iterations in federated learning. Both algorithms converge faster, have lower variance, and achieve higher final rewards when more agents are engaged to collect trajectories. Compared to the standard average FedNPG, FedNPG-ADMA does not only reduce communication complexity, but also keeps convergence performances. The hyperparameter and MIP settings are described in Table 4 We summarize the final reward results with standard deviations in Table 2 FedNPG-ADMM achieves similar final rewards compared to the standard average FedNPG. It also works with slightly high variance when only one agent is engaged.
7

---

In Figure 3 we compare the performances of the standard average FedNPG, FedNPG-ADMM, and first-order FedPPO algorithms. The number of federated agents N is fixed PPO clipping parameter is set 0.2. FedNPG methods outperform FedPPO in these tasks with faster convergence and higher final rewards. is noticeable that FedNPG-ADMM has similar convergence rates and achieves slightly higher final rewards than the standard average FedNPG for the Swimmer-ve v4 task, while it becomes slightly lower for the Humanoid-v4 task. Generally, there is no significant difference in convergence rates after ADMM approximation. The communication overhead is measured by the number of transmitted parameters with double precision in each agent. FedNPG-ADMM keeps the communication overhead as the first-order methods, while FedNPG has much higher costs. The ADMM method reduces the cost by 4 orders magnitude in the Swimmer- v4 task and about 6 orders of magnitude in the Humanoid- v4 task.
120
120
100
Rewards
80
Rewards
60
agent
60
agent
N
40
N
N 4
N
N 8
N 8
0
0.0
0.2
0.1
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
# Iterations
1e3
Iterations
(a) FedNPG (Swimmer-v4)
(b) FedNPG-ADMM (Swimmer-v4)
3000
3000
agent
2500
N
2500
2000
N
2000
Rewards
Rewards
N
1500
1500
500
500
0
0.0
0.5
2.0
0.5
1.0 # Iterations
# Iterations
1u5
1u3
FedNPG (Hopper-v4)
(d) FcdNPG-ADMM (Hopper-v4)
Figure 2: Reward performances of standard average FedNPG and FedNPG-ADMM MuloCo tasks, where N the number federated agents. Top: Swimmer-v4, Bottom: Hopper-v4. Left: FedNPG with O(d)) communication complexity, Right: FedNPG-ADMM with O(d) communica- tion complexity.
Table 2: Final rewards in federated settings.
# Agents
2
8
FedNPG
111.9 5.4
119.5 1 3.4
122.1 + 3.6
124.8 + 2,4
Swimmer-v4
FedNPG-ADMM
109.4 5.9
123.6 10.3
127.2
2.2
128.5 1.9
FedNPPG
1644 = 396
2468 426
2458 = 171
2736 = 158
Hopper-v4
FedNPG-ADMM
1473 + 383
2384 371
2507 230
2719 + 173

---

120
1000
100
Rewards
Rewards
600
80
40
FedPPO
FedPPO
20
FedNPG
200
FecNPG
FedNPG-ADMM
FecNPG-ADMM
0.0
0.2
0.4
0.6
0.8
1.0
2
Iterations
1u5
Iteerations
1e3
(a) Swimmer-y4 Rewards
(b) Humanoid-v4 Rewards
10
Communication overhead
Communicalion overhead
10
10
10
10
10
FedPPO
FocPPO
FedNPG
10
FedNPG
FedNPG-ADMM
FecNPG-ADMM
0.0
0.2
0.1
0.6
0.8
1.0
0.0
0.5
1.0
1.5
2.0
2.5
3,0
lterations
1e3
Iterations
(c) Swimmer-v4 Overhead
(d) Humanoid-v4 Overhead
Figure 3:
Comparisons of FedPPO, standard average FedNPG, and FedNPG-ADMM on MuJoCo
tasks, where the number of federated agents N is and the communication overhead is measured by the transmitted bytes in each agent. Left: Swimmer-y4 task, Right: Humanoid-V v4 task, Top: Reward performances, Bottom: Communication overhead.
Table 3: Description of the MuloCo environment.
Tasks
Agent
Action Dimension
State Dimension
Swimmer-ve v4 Hopper-v4
Three-link swimming robot
2
two-dimensional one-legged robot
3
11
Humanoid-v4
Three-dimensional bipedal robot
17
376
Table 4: Hyperparameter and MI.P settings.
Hyperparameter
Setting
Task
Swimmer-v4
Hopper-v4
Humanoid-ve
MLP
64 x 64
128 x
512 x 512
512
Activation function
ReLU Tanh
ReLU Tanh
ReLU Tanh
Output function
Penalty (p)
0.1
0.1
0.01
Radius (d)
0.01
0.01
0.01
Discount (7)
0.99
0.99
0.99
Timesteps (T)
2048
1024
512
Iterations (K)
10
2 1
3 10
Learning rate
x 10
3 10-4
1 x 10-5

---

In Figure 4 we test performances with agent selection. In the Swimmer task, we randomly select 75% and 50% of agents each iteration, and the performances only drop slightly (final rewards drop less than 6%). Thus, our proposed method is robust for agents with disconnection in practice.
100
Rewards
80
60
selection
40
60%
20
75%
100%
0.0
# Iterations
1e3
Figure 4: Reward performances of FedNPG-ADMM on the Swimmer-ve v4 task with agent selection. In each iteration, the server randomly selects 100%, 75%, and 50% of agents for the aggregation.
6 Conclusion & Discussion
In this paper, we proposed a novel federated natural policy gradient (NPG) algorithm that estimates global directions using ADMM (FedNPG-ADMM) Our ADMM-based gradient updates significantly reduce communication complexity from (ad) (d), where is the number of model parameters. thus enables second-order policy gradient methods to be used for large-scale federated reinforcement learning problems. We proved that our FedNPG-ANe ADMM algorithm achieves stationary convergence without requiring more samples as compared standard FedNPG. Furthermore, we empirically showed the improved performances of FedNPG-ADMM in the MuJoCo environments compared to FedNPG and the first order methods.
Overall, our proposed FedNPG-ADMM algorithm provides a scalable and efficient solution for large-scale federated reinforcement learning problems. Our contributions include a novel direction on policy-based FedRL, new algorithm, reduced communication complexity, and convergence analysis. We believe that our approach can have a significant impact on wide range of real-world applications, where large-scale distributed reinforcement learning with communication and privacy constraints is critical.
Limitations: (1) While the communication complexity improvement is loosely tied to the privacy advantage, exploring deep connections with differential privacy improvement is open. (2) Partial agent participation is not studied under this framework, in which communication complexity can be further reduced. (3) In experiments, would be more persuasive to extend the number of federated agents to larger scale.
Acknowledgments
We thank all reviewers for their invaluable feedback that helped us significantly strengthen the work. C. Brinton acknowledges financial support from NSF CNS-2146171 and DARPA 0022P00168-00 Han Wang and James Anderson acknowledge financial support from NSF grants ECCS-2144634 and ECCS-2231350.
References
[1] Agarwal, A., Kakade, S.M., Lee, J.D., Mahajan, G.: On the theory of policy gradient methods: Optimality, approximation, and distribution shift, Journal of Machine Learning Research 22(1), 4431-4506 (2021)
10

---

[2] Agarwal, M., Ganguly, B., Aggarwal, V: Communication efficient parallel reinforcement learning. In: Uncertainty Artificial Intelligence (2021)
[3] Al-Abbasi, A.O., Ghosh, A., Aggarwal, V.: DeepPool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems 20()2), 4714 4727 (2019)
[4] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., et al.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ Machine learning 3(1), 1-122 (2011)
[5] Chen, T., Giannakis, G.B.: Bandit convex optimization for scalable and dynamic iot manage- ment. IEEE Internet of Things Journal 6(1), 1276-1286 (2018)
[6] Ding, D., Zhang, K., Basar, T., Jovanovic, M.: Natural policy gradient primal-dual method for constrained Markov decision processes. In: Advances in Neural Information Processing Systems (2020)
[7] Elgabli, A., Issaid, C.B., Bedi, A.S., Rajawat, K., Bennis, M.. Aggarwal, V:: FedNew: A communication-effiiaa. and privacy-preservie Newton-type method for federated learning. In: International Conference on Machine Learning (2022)
[8] Elgabli, A., Park, J., Bedi, A.S., Bennis, M., Aggarwal, V:: GADMM: Fast and communication efficient framework for distributed machine learning. Journal of Machine Learning Research 21(76), 1-39 (2020)
[9] Elgabli, A., Park, J., Bedi, A.S., Issaid, C.B., Bennis, M., Aggarwal, V. Q-GADMM: Quantized group ADMM for communication efficient decentralized machine learning. IEEE Transactions on Communications 69(1), 164-181 (2020)
[10] Engstrom, L., Ilyas, A., Santurkar, S., Tsipras, D.., Janoos, F., Rudolph, L., Madry. A.: Imple- mentation matters in deep RL: A case study on PPO and TRPO. In: International Conference on Learning Representations (2020)
[11] Haliem, M., Mani, G., Aggarwal, V., Bhargava, B.: A distributed model-free ride-sharing approach for joint matching, pricing, and dispatching using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems 22( 12), 7931-7942 (2021)
[12] Hosseinalipour, S., Brinton, C.G., Aggarwal, V., Dai, H., Chiang, M.: From federated to fog learning: Distributed machine learning over heterogeneous wireless networks. IEEE Communi- cations Magazine 58(12), 41-47 (2020)
[13] Islamov, R., Qian, X., Richtarik, P.: Distributed second order methods with fast rates and compressed communication. In: Proceedings of the 38th International Conference on Machine Learning (2021)
[14] Jin, H., Peng, Y., Yang, W., Wang. S., Zhang, Z. Federated reinforcement learning with environment heterogeneity. In: International Conference on Artificial Intelligence and Statistics (2022)
[15) Kairouz, P., McMahan, H.B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A.N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., D'Oliveira, R.G.L., Eichner, H., Rouayheb, S.E., Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, P.B., Gruteser, M., Harchaoui, Z. He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konecný, J.. Korolova, A., Koushanfar, F., Koyejo. S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Qi, H., Ramage, D., Raskar, R., Raykova, M., Song. D., Song, W., Stich, S.U., Sun, 7., Suresh, A.T. Tramèr, F., Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q. Yu. F.X., Yu, H. Zhao, S.: Advances and open problems in federated learning, Foundations and Trends@ in Machine Learning 14(1-2), 1-210 (2021)
[16] Kakade, S.M.: natural policy gradient. In: Advances in Neural Information Processing Systems (2001)

---

[17] Khodadadian, S., Sharma, P., Joshi, G., Maguluri. S.T.: Federated reinforcement learning: Linear speedup under Markovian sampling, In: International Conference Machine Learning (2022)
[18] Kingma, D.P., Ba, J.: Adam: method for stochastic optimization. arXiv preprint arXiv:1412.69R8 (2014)
[19] Lan, G., Liu, X.Y., Zhang, Y., Wang, X.: Communication-efficient federated learning for resource-constrained edge devices. IEEE Transactions on Machine Learning in Communications and Networking 1, 210-224 (2023)
[20] Li, X., Li, Y., Zhan, Y., Liu, X.Y.: Optimistic bull or pessimistic bear: Adaptive deep reinforce- ment learning for stock portfolio allocation. In: International Conference on Machine Learning Workshop on Applications and Infrastructure for Multi Learning (2019)
[21] Liu, B., Cai, Q.. Yang, Z., Wang, Z.: Neural trust region/proximal policy optimization attains globally optimal policy, In: Advances in Neural Information Processing Systems (2019)
[22] Liu, X.Y., Li, Z., Yang. Z., Zheng. J., Wang. Z., Walid, A., Guo, J., Jordan, M.I.: ElegantRL- Podracer: Scalable and clastic library for cloud-native deep reinforcement learning. In: Ad- vances in Neural Information Processing Systems Workshop on Deep Reinforcement Learning (2021)
[23] Liu, Y., Zhang, K., Basar, T., Yin, W.: An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. In: Advances in Neural Information Processing Systems (2020)
[24] Makhdoumi, A., Ozdaglar, A.: Convergence rate of distributed ADMM over networks. IEEE Transactions on Automatic Control 62(10), 5082-5095 (2017)
[25] McMahan, B., Moore, E., Ramage, D., Hampson, S., y Arcas, B.A.: Communication--fficee learning of deep networks from decentralized data. In: International Conference on Artificial Intelligence and Statisties (2017)
[26] Mothukuri, V., Parizi, R.M., Pouriyeh, S., Huang, Y., Dehghantanha, A., Srivastava, G.: A survey on security and privacy of federated learning. Future Generation Computer Systems 115, 619-640 (2021)
[27] Nguyen, D.C., Ding, M., Pathirana, P.N., Seneviratne, A., Li, J., Poor, H.V.: Federated learning for internet of things: A comprehensive survey. IEEE Communications Surveys & Tutorials 23(3), 1622-1658 (2021)
[28] Niknam, S.. Dhillon, H.S., Reed, J.H.: Federated learning for wireless communications: Moti- vation, opportunities, and challenges. IEEE Communications Magazine 58(6), 46-51 (2020)
[29] OpenAl: GPT-4 technical report. arXiv preprint arXiv:2303.08774 (2023)
[30] Ouyang, L., Wu, J., Jiang. X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Gray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A.,
Welinder, P., Christiano, P., Leike, J., Lowe, R.: Training language models follow instructions with human feedback. In: Advances in Neural Information Processing Systems (2022)
[31] Papini, M., Binaghi, D., Canonaco, G., Pirotta, M., Restelli, M.: Stochastic variance-reduced policy gradient. In: Proceedings of the 35th International Conference on Machine Learning (2018)
[32] Paszke, A., Gross, S., Massa, F,, Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z.,, Gimelshein, N., Antiga, I.,, et al.: PyTorch, An imperative style, high-performance deep learning library. In: Advances in Neural Information Processing Systems (2019)
[33] Provost, F., Fawcett, T: Data science and relationship to big data and data-driven decision making. Big Data 1(1), 51-59 (2013)
12

---

[34] Qian, X., Islamov, R., Safaryan, M., Richtarik, P:: Basis matters: Better communication efficient second order methods for federated learning. In: Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (2022)
[35] Raffin, A., Hill, A., Gleave, A., Kanervisto, A., Ernestus, M., Dormann, N.: Stable-baselines:: Reliable reinforcement learning implementations. Journal of Machine Learning Research 22(268), 1-8 (2021)
[36] Rajeswaran, A., Lowrey, K., Todorov, E.V., Kakade, S.M.: Towards generalization and simplic- ity in continuous control. Advances in Neural Information Processing Systems (2017)
[37] Safaryan, M.. Islamov, R., Qian, X., Richtarik, P.: FedNL: Making Newton-type methods
applicable federated learning. In: International Conference on Machine Learning (2022)
[38] Schulman, J., Levine, S., Moritz, P. Jordan, M.I., Abbeel, P.: Trust region policy optimization. arXiv preprint arXiv:1502.0542 (2017)
[39] Schulman, J., Moritz, P., Levine, S., Jordan, M., Abbeel, P:: High-dimensional continuous control using generalized advantage estimation. arXiv preprint
(2018)
[40] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization
algorithms. arXiv preprint Nt..Xiv1707..6335 (2017)
[41] Shalev-Shwartz, S., Shammah, S., Shashua, A.: Safe, multi-agent, reinforcement learning for (2016)
autonomous driving. arXiv preprint
[42] Shamir, O., Srebro, N., Zhang, T.: Communication-effcceen distributed optimization using an approximate Newton-type method. In: International Conference on Machine Learning (2014) 4)
[43] speedtest.net: Speedtest market report in the United States (2023), http://www... speedtest net/reports/united-eeo
[44] Todorov, E., Erez, T., Tassa, Y.: MuJoCo: A physics engine for model-based control. In:
IEEE/RSJ International Conference on Intelligent Robots and Systems (2012)
[45] Wang, H., Marella, S., Anderson, J.: FedADMM: A federated primal-dual algorithm allowing partial participation. In: IEEE 61st Conference on Decision and Control (2022)
[46) Wang, H., Mitra, A., Hassani, H., Pappas, G.J., Anderson, J.: Federated temporal difference learning with linear function approximation under environmental heterogeneity. arXiv preprint arXiv:2302.02212 (2023)
[47] Wang, H., Toso, L.F. Mitra, A., Anderson, J.: Model-free learning with heterogencous dynami- cal systems: A federated LQR approach. arXiv preprint arXiv:2308. (2023)
[48] Wang, H., Toso, L.F., Anderson, J.: FedSysID: A federated approach sample-efficient system identification. In: Learning for Dynamics and Control Conference. pp. 1308-1320. PMLR (2023)
[49] Woodworth, B.E., Patel, K.K., Srebro. N.:
Minibatch vs local SGD for heterogeneous distributed learning. In: Advances in Neural Information Processing Systems (2020)
[50] Xie, Z., Song, S.: FedKL: Tackling data heterogeneity in federated reinforcement learning by penalizing KL divergence. IEEE Journal on Selected Areas in Communications 41(4), 1227-1242 (2023)
[51] Xu, P.. Gao, F. Gu, Q.: Sample efficient policy gradient methods with recursive variance reduction. In: International Conference on Learning Representations (2020)
13


Reviews:
[{"review_id": "pp7UW8iIJC", "reviewer": "Reviewer_q8Jc", "summary": "The work proposed a new algorithm for federated policy optimization. The proposed work uses prima-dual update to replace the primal update of FedNPG, so that the communication cost reduces from $d^2$ to $d$. The proposed work enjoys same rate of convergence as FedNPG under certain assumptions, and numerical experiments were proposed to show the efficacy of the algorithm.", "questions": "Here are the my questions and suggestions:\n\n1. Concerns on the motivations: the idea of combining reinforcement learning and federated learning is interesting, which is also largely un-explored in the literature. It is good to see the exploration on this direction. An intriguing question is that can we consider existing works on reformulating the TRPO, such as the KL-penalitzed objective in [1], to federated setting? Since if we get rid of the constraint, we don’t need to communicate the Hessian in the first place (and FedAvg-type algorithm may also enjoys similar rate of convergence in theory). In summary, the authors propose to study the policy optimization in federated setting, but eventually ended up at a less significant improvement over FedNPG (and this improvement comes from essentially the constrained federated learning, not from RL or policy optimization), which makes me feel less confident about the contribution in the RL field;\n\n2. In terms of the assumptions for convergence analysis, the authors proposed bounded policy gradient and Lipschitz continuous (Assumption 4.1) and claimed that they are fairly standard in the existing literature. I’m actually not very sure about the boundedness of the policy gradient. Could the authors just include the specific assumptions in the existing literatures? Same question for Assumption 4.2.\n\n3. The penalty parameter $\\rho$ is the penalty to make sure that each local $y_i$ consensus with the global $y$. In the experiment $\\rho$ is simply a small number as 0.1 or 0.01. My concern is that during the update, is $y_i - y\\rightarrow 0$ true or not? The authors could also plot the consensus errors.\n\n4. In the experiments, for example Figure 2 and 3, FedNPG-ADMM seems not better than FedNPG in terms of the rewards. It would be interesting to see why this is the case. I know that the main claim of FedNPG-ADMM is its commutation efficiency, and I think the authors could also plot the curves wrt the CPU times.\n\nReferences:\n\n[1] Schulman, John, et al. \"Proximal policy optimization algorithms.\" arXiv preprint arXiv:1707.06347 (2017).", "limitations": "The limitation is well stated in weakness and question sections. The authors also include the discussions in limitations at the end of the work.\n\nI’m not aware of any potential negative social impact of this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-rounded and the presentation is clear. The proposed method clearly enjoys the supremacy in terms of communication error. The numerical experiments were proposed to show the efficacy of the algorithm. ", "weaknesses": "(Please reply to the Questions section directly) The motivation of the proposed algorithm seems a bit less significant. Moreover, the convergence theory requires policy gradient bounded, which seems quite strong. In the numerical experiments, more results could be included to further show the efficiency of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**. This is a thoughtful suggestion. We had the same thought at the beginning. However, local updates in the FedAvg-type might not bring advantages compared to gradient aggregation [46, 43]. On the other hand, unlike supervised learning, local updates in RL bring different **local policies**. We do not think it is a good idea to use **on-policy** algorithms for samples collected by different local policies.\n\nSecond, although the soft penalty approach has simpler forms, it might bring worse performances than the constraint methods, e.g., on the Swimmer [37] and Humanoid [10] tasks in MuJoCo environments. With a hard constraint, the NPG enjoys stable training performances and has solid theoretical guarantees [2, 22]. In Figure 3, our experiments also verify that FedPPO has worse performances.\n\nThird, as for the first-order PG, [22] thoroughly compares the convergence performances of PG and NPG. Furthermore, recent works have demonstrated that the convergence guarantees of NPG with KL divergence constraints are superior to those of PG [20, 22], motivating closer inspection for practical use. \n\nIn summary, this work makes the second-order methods have the same communication complexities as the first-order methods per iteration, and achieve stable and higher rewards in the federated setting.\n\n**Q2**. The bounded score function assumption is used in Assumption 4.1 [47], Assumption 5.1 [48], Assumption 4.1 [45], Assumption 4.2 [22], and Assumption 3 [49]. The positive definite assumption is used in Assumption 2.1 [22]. The continuity assumption is used in Assumption 4.1 [47], Assumption 5.1 [48], Assumption 4.1 [45], Assumption 4.2 [22], Assumption 2 [49], and Assumption 6.4 [2] (and the following lemmas). The above assumptions are verified for simple policy parameterizations such as Gaussian policies [47, 50, 51].\n\n**Q3**. True. We test the averaged differences $\\frac{\\sum_{i=1}^{N}\\lVert y_i - y \\rVert^2}{N}$ with respect to the number of iterations. The differences gradually decrease to $0$. Over the course of training, policies are more deterministic and less random. It is not surprising that $y_i - y \\rightarrow 0$ as policies become stable.\n\n**Q4**. In the experiments, we run each task ten times with random seeds from $0$ to $9$. Sometimes FedNPG-ADMM achieves higher rewards than FedNPG, while the averaged results slightly drop in the Humanoid task. As the ADMM approach is, in fact, an approximation of the exact aggregation, it is not surprising that the ADMM approach sometimes drops a little. In any way, they generally have the same convergence rate and similar performances in these tasks. We thank the reviewer for the computing time suggestion. However, communication time dominates the cost in federated learning [3, 15, 52]. To make the comparisons more clear, with reference to the comments of two other reviewers, we add the communication overhead of each method in Figure 4. The communication time (byte transmission) is reduced by $4$ orders of magnitude in the Swimmer-v4 task and about $6$ orders of magnitude in the Humanoid-v4 task."}, {"review_id": "YurdiGxIyL", "reviewer": "Reviewer_GLbD", "summary": "This paper applies the ADMM technique to the Fed-NPG algorithm in reinforcement learning and reduces the communication cost from $O(d^2)$ to $O(d)$ where $d$ is the number of parameters, which nearly maintains the convergence results of Fed-NPG. Empirical results verify the theoretical analysis.", "questions": "See the weakness section.", "limitations": "n/a", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The communication cost reduction is impressive since in the federated learning setting, the communication cost is one of the bottlenecks, and the convergence results are nearly the same as Fed-NPG. The idea to combine natural policy gradient with ADMM style methods (or the penalty functions) is interesting (and at least novel to me).", "weaknesses": "I am not very familiar with reinforcement learning, and thus may not find potential weaknesses. However, I suggest comparing with the original policy gradient methods in the empirical section and even in the main content (show that Fed-NPG-ADMM converges much fast than the policy gradient variation in federated learning) and plotting all the communication cost for Fed-NPG, Fed-NPG-ADMM, and policy gradients.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**. Thank you for these constructive suggestions.  We will add PG in the main content and communication comparisons are added in Figure 4 (see added pdf), where communication overhead is measured by the number of transmitted parameters with double precision in each agent. FedNPG-ADMM keeps the communication overhead as the first-order methods, while FedNPG has much higher costs. The ADMM method reduces the cost by $4$ orders of magnitude in the Swimmer-v4 task and about $6$ orders of magnitude in the Humanoid-v4 task."}, {"review_id": "y4B7DUSn0R", "reviewer": "Reviewer_pYuC", "summary": "The paper studies how to train a global policy using distributed data in reinforcement learning. The authors propose a distributed natural policy gradient method by employing ADMM to approximately compute a natural policy gradient direction. The communication complexity is linear in the dimension of policy parameters. The authors also prove the sublinear iteration complexity for achieving a stationary point. The effectiveness of the proposed method is finally verified in MuJoCo experiments. ", "questions": "\nSome questions are raised in Weaknesses. Here are some other questions. \n\n- Can the authors provide robustness or fault-tolerance guarantees?  \n\n- Can ADMM-based update be applied to other policy gradient methods? It is useful to discuss generalizability. \n\n- Since the global convergence exists in many policy gradient methods, can the authors strengthen the convergence guarantees? \n\n- Can the authors compare the proposed method with other baselines, e.g., Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**originality**\n\nHigh communication complexity is a bottleneck for implementing many RL algorithms in federated training. I believe the novelty of this work lies in a new application of ADMM to a popular RL algorithm: natural policy gradient. This method achieves better communication complexity than one for the naive method. I am not aware of this method in the literature.  \n\n**quality**\n\n- The authors provide the stationary-point analysis of the proposed method in a distributed training setting.\n\n- The authors verify the use of the proposed method in experiments. \n\n**clarity**\n\nThe proposed method and theory are clearly explained.\n\n**significance**\n\n- The distributed training algorithm is important for applying RL in distributed systems. \n\n- The stationary-point convergence guarantee is provided. ", "weaknesses": "- The naive method of fererated natural policy gradient only has quadratic communication complexity with respect to the dimension of policy parameter. This does not seem to be a real bottleneck.\n\n- Directly extending centralized RL algorithms is not very significant, since fault-tolerance and robustness issues are more important to distributed systems. \n\n- It is important to compare communication complexity with the literature, e.g., Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee. \n\n- Some assumptions can be strong in practice, e.g., the invertibility of Hessian. It is useful to provide examples when Hessian is invertible. \n\n- The provided convergence property can be arbitrarily sub-optimal, and it is not clear how to check all assumptions. The stationary-point analysis has a gap with the convergence rate analysis of natural policy gradient in the literature. \n\n- The experimental setting is artificial since it is not originally designed for federated learning. There are no comparable baselines in experiments. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1**. This is actually an important bottleneck for the following reasons. Generally, if one method can reach a large scale, it means that its complexity is at most $O(n)$ [53]. Thus, the $O(n^2)$ complexity in the naive method is not acceptable in large-scale FL. In DRL, a policy is approximated by NNs, and the sizes of NNs are generally large. For toy tasks in MuJoCo [54] or language agents [55], the parameter sizes can reach $10^6$ level, and the sizes of Hessains are ${12}$ orders. In practice, the sizes of NNs in RL are getting larger and larger. With transformers, parameter sizes reach $2.2\\times 10^{10}$ [56], and its square is $4.8\\times 10^{20}$ ($4$ zettabyte with double-precision). Transmitting these large amounts of data from each agent in each iteration is not realistic.\n\n**W2&Q1**. First, our paper is not a direct extension of central RL. Compared to the central setting, the first critical bottleneck is a limited communication budget in FL [17, 52]. It is necessary to design FedRL that leverages communication costs and learning performances. Our FedNPG-ADMM utilizes the 2nd-order information but only requires its approximation without sending Hessians. As NPG (2nd-order) is more stable and converges faster than PG (1st-order), we rigorously prove the convergence of FedNPG-ADMM.\n\nSecond, we agree that fault tolerance is important in distributed systems. However, FedRL is a new and emerging field with a limited number of theoretical publications at this moment. The adaptation of centralized RL algorithms to FL while achieving a balance between communication cost and learning efficiency remains a challenging task, and it is the first step. Our paper thoroughly solved this problem. The fault-tolerance theory is a good direction for the next step. Noticeably, our method is orthogonal to several malicious detection methods, e.g., the attack stealth [57]. To expand our work, we add experiments with agent selection in Figure 5. In the Swimmer task, we randomly select $75\\%$ and $50\\%$ of agents in each iteration, and the performances only drop slightly (final rewards drop less than $6\\%$). Thus, our proposed method is robust for agents with disconnection in practice.\n\n**W3&Q4**. We thank the reviewer for pointing out the valuable work (FedBR) [58], and will add it to our introduction. However, this approach is designed for Byzantine attacks, while we focus on reducing communication costs while maintaining performance.\n\nFirst, our algorithm converges *faster* than FedBR. FedBR focuses on PG (1st-order). Our work is NPG (2nd-order). [22] thoroughly compare the convergence performances of PG and NPG. If measured in the same metric, our convergence rate is ${O}(1/\\epsilon N)$, while ${O}(1/\\epsilon^{\\frac{5}{3}}N^{\\frac{2}{3}})$ in FedBR. Further, our method improves the communication cost in FedBR by $O(d\\epsilon^{\\frac{2}{3}}/N^{\\frac{1}{3}})$. Second, FedBR does not show the sample complexity of FedRL can be scaled linearly by the number of agents, i.e., $\\alpha =0$ in Table 1 [58]. In contrast, our paper shows that *the sample complexity is scaled linearly* by $N$, which comes from the benefit of collaboration, and in Figure 2, a thorough comparison is given to support it.\n\nIn summary, NPG updates policies according to the Riemannian metric and enjoys stable on-policy explorations. We do not think it is suitable to directly compare them, though.\n\n**W4**. In practical computation, if take an $n\\times n$ symmetric matrix with uniformly distributed entries, it will almost certainly be invertible.\n\nThe inverse expression is widely used in the original NPG (Theorem 1) [16] and TRPO (Appendix C) [35]. It can be replaced by the MP-pseudoinverse in [2, 35]. It is worth mentioning that in practice, it is expensive to solve $Ax=b$ by computing $A^{-1}$ in both space and computation. A conjugate gradient method is used in DRL to approximate the result [33].\n\n**W5&Q3**. Our assumptions are widely used and verified in previous works. See Q2 in Reviewer1 q8Jc for details.\n\nThe convergence of FedNPG-ADMM is fixed-point optimality, and our work is NPG instead of vanilla PG. In FL, even without ADMM, it is still challenging to provide a global guarantee for NPG without additional strong assumptions. The global guarantee of NPG attributes to the gradient domination property [2]. Without it, the convergence can only be assured to local optimums instead of a global one in the nonconvex setting. However, this property is limited to the centralized setting with $N=1$, which is *the reason that lots of global guarantees are established in the centralized setting*. If each function $\\\\{f_i\\\\}^N_{i=1}$ satisfies the property, the sum $\\sum_{i=1}^N f_i$ might not. We recognize the importance of a global guarantee for the ADMM approach. Finding sufficient (and then necessary) assumptions for FedNPG (even without ADMM) is a direction for future works. Practically, we verify the performances by experiments, and it shows that the FedNPG-ADMM achieves the same convergence as FedNPG.\n\n**W6**. First, we follow the standard setting in FL. In the original FL work [24], the classical image and language tasks are used. In FL research, we usually make classical tasks federated instead of designing new tasks [15, 52].\n\nSecond, FedRL is a new field and has not formed experimental baselines. There are datasets published last year for labeled images [59] and health images [60], but they are not for RL and have not formed baselines. We are more than happy to see there are open-source tasks or baselines designed for FL and widely accepted by the community. It would be better if they are designed for FedRL.\n\n**Q2**. Any 2nd-order PG can apply the ADMM method. Regarding other 2nd-order methods, there is a Hessian-aided PG attempt [61], but its conclusion still claims NPG achieves better performances. NPG itself forms a basic approach for several variants [2, 22, 35]."}, {"review_id": "nTW5QiLfQo", "reviewer": "Reviewer_ZDkh", "summary": "This paper proposes a communication-efficient algorithm, FedNPG-ADMM, for federated natural policy gradient by using a reformulation of quadratic problem. It reduces the communication complexity from $\\mathcal{O}(d^2)$ to $\\mathcal{O}(d)$. The convergence analysis is provided accordingly.", "questions": "see above", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and clearly presented.\n2. The reformulation of the original quadratic problem into a distributed manner (eq 14) is a smart move.\n3. Using ADMM-based global direction estimation to reduce the communication complexity by $\\mathcal{O}(d)$.\n4. Stationary convergence in non-convex case is provided, which is the same order as the standard FedNPG.", "weaknesses": "As it is in the federated learning (FL) setting, I am curious about main difference between the FL setting considered in this paper and the classic distributed learning.\n1. data heterogeneity is one of the key features in FL, but how it impact the model performance does not clearly discussed in the paper, neither in theory or in experiments. \n2. To reduce the communication costs, local updates are often used within each agent for FL algorithms. But in the FedNPG-ADMM algorithm proposed in this paper, there is no local update step for each agent. Could local steps be directly applied in the FedNPG-ADMM and further reduce the communication cost while maintaining the same convergence?\nGiven above, to be precise, the setting for this paper is a distributed learning setting, rather than FL with data heterogeneity and local update.\n\nThe major contribution is the communication reduction as claimed in the paper, so I expect the experiments could have more comparison of direct communication costs.\n1. Directly comparison in terms of the communication cost should be given. In other words, the results with communication cost as the x-axis are also desired.\n2. Appreciate it if other baselines could be included other than FedNPG. I am curious about the actual communication costs among first-order methods, second-order methods (FedNPG), and approximated version of second-order methods (FedNPG-ADMM). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1.a**. Yes, data heterogeneity is a key issue in FL. However, this issue only exists in model aggregation methods (with local updates). As proven in [43], gradient aggregation methods are *immune* to whether collected data is i.i.d., or not. In summary, data heterogeneity will not influence our results, as they are based on gradient aggregation.\n\n**Q1.b**. This can be taken as the same question in Q1.a. FL is a problem and it can be solved in several ways. The key difference between distributed learning and centralized federated learning is the star network [52] in federated learning, where there is a parameter server that collects the updates and broadcasts information to all agents. In the classical distributed learning, clients usually can communicate with each other, while they cannot in the federated setting. \n\nLocal updates (FedAvg [24]) are proposed for model aggregation methods.  The argument between local updates and gradient aggregations (called local SGD and minibatch SGD, respectively, in the distributed optimization community) has been going on for years. Proven in [43], gradient aggregation methods are *immune* to whether collected data is i.i.d., or not. [46] also compares the convergence rates between these two paradigms, and the local SGD is actually not better. As the gradient aggregation method is not generally worse than the local update method and is immune to data heterogeneity, we decide to use it. This paper does not aim to argue the differences between them, but to find an efficient way for gradient aggregation in RL.\n\nIt is worthwhile to mention that these well-known FL algorithms FedNL [34] and FedPD [62] also use one-step updates. Our algorithm can be extended to multiple local steps. However, multiple local steps may slow down the convergence, as mentioned in the standard FL literature [52]. In this case, it becomes unclear whether FedNPG-ADMM can further reduce the communication cost while maintaining the same convergence. This is a good question and could be future work.\n\n**Q2**. Our original figures follow the conventional settings with the number of iterations as the x-axis. We thank the reviewer for the valuable suggestion. It is indeed better if we have direct communication comparisons as they are the main contributions. Thus, communication comparisons are added in Figure 4 (see added pdf), where communication overhead is measured by the number of transmitted parameters with double precision in each agent. FedNPG-ADMM keeps the communication overhead as the first-order methods, while FedNPG has much larger costs. The ADMM method reduces the cost by $4$ orders of magnitude in the Swimmer-v4 task and about $6$ orders of magnitude in the Humanoid-v4 task."}]

Author rebuttal:
Dear Area Chairs and Reviewers,

We appreciate your organization and valuable feedback.

In the one-page pdf, we add communication costs in Figure 4 and agent selection in Figure 5.

In the rebuttals, references [1-45] are from the main paper, and references [46-62] are listed as follows:

---
[46] Woodworth, B., Patel, K.K., Stich, S., Dai, Z., Bullins, B., Mcmahan, B., Shamir, O., Srebro, N.: Is local SGD better than minibatch SGD? ICML (2020)

[47] Papini, M., Binaghi, D., Canonaco, G., Pirotta, M., Restelli, M.: Stochastic variance-reduced policy gradient. ICML (2018)

[48] Xu, P., Gao, F., Gu, Q.: An improved convergence analysis of stochastic variance-reduced policy gradient. In: Proceedings of The 35th Uncertainty in Artificial Intelligence Conference (2020)

[49] Ding, D., Zhang, K., Basar, T., Jovanovic, M.: Natural policy gradient primal-dual method for constrained Markov decision processes. NeurIPS (2020)

[50] Cortes, C., Mansour, Y., Mohri, M.: Learning bounds for importance weighting. NeurIPS (2010)

[51] Pirotta, M., Restelli, M., Bascetta, L.: Adaptive step-size for policy gradient methods. NeurIPS (2013)

[52] Li, T., et al: Federated learning: Challenges, methods, and future directions. IEEE signal processing magazine 37(3), 50–60 (2020)

[53] Bottou, L., et al: Optimization methods for large-scale machine learning. SIAM Review (2018)

[54] Liu, X.Y., et al: Stationary deep reinforcement learning with quantum k-spin Hamiltonian regularization. ICLR Workshop on Physics for Machine Learning (2023)

[55] Zhong, V., et al: Improving policy learning via language dynamics distillation. NeurIPS (2022)

[56] Dehghani, M., et al: Scaling vision transformers to 22 billion parameters. ICML (2023)

[57] Bhagoji, A.N., et al: Analyzing federated learning through an adversarial lens. ICML (2019)

[58] Fan, X., et al: Fault-tolerant federated reinforcement learning with theoretical guarantee. NeurIPS (2021)

[59] Song, C., et al: Federated learning annotated image repository. NeurIPS (2022)

[60] Ogier du Terrail, J., et al: Datasets and benchmarks for cross-silo federated learning in realistic healthcare settings. NeurIPS (2022)

[61] Shen, Z., et al: Hessian aided policy gradient. ICML (2019)

[62] Zhang, X., Hong, M., Dhople, S., Yin, W., Liu, Y.: FedPD: A federated learning framework with adaptivity to non-iid data. IEEE Transactions on Signal Processing 69, 6055–6070 (2021)

Meta-review: This paper studies a communication efficient approach for federated reinforcement learning. Overall the reviewers are impressed by the communication savings, but are requesting more extensive numerical results to demonstrate the benefits. Further, the work is a bit incremental since it is a direct extension to the centralized case, using ADMM, and it is sort of expected that such approach will work.
Decision: Accept (poster)