Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysis

Thank you for reading the paper carefully! If there are any other concerns, we would be happy to answer them.

W1. Section 4.

We have added more explanation of $d_{k-1}$ and $\theta_{k-1}$, and reconstructed our algorithms (Algorithm 1 and 2) to clearly show the process. We keep all notations unchanged in the theoretical analysis.

We have added literature explanations in the Introduction.

For trajectory sampling, it is indeed not practical to sample the whole trajectory. However, with the discount factor $\gamma$, the variance is exponentially small in the horizon [1,2]. The truncation does not influence the convergence results, and thus, the infinite horizon setting [3] is widely used in the recent analysis.

W2. Section 5.

Thank you for the remainder! Though the equations are correct in the theorems in the appendix, we had a typo in its simplified version in equation 10. We have fixed the typo in the main paper.

We have added the derivation with details in Appendix A.1. The line 394 could be well explained according to Appendix A.1.

W3. Appendix B.

Thanks for the suggestion! We have added the explanations of the conventional notations in Appendix B.1.

We have added the exact positions of the cited lemmas (Lemma B.7 and B.8).

We have fixed all typos with more rounds of proofreading.

[1] On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift. Journal of Machine Learning Research 2021.

[2] An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods. NeurIPS 2020.

[3] Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes. AISTATS 2024.

Thank you for bringing the valuable work in the synchronous setting! We hope that we have addressed your concerns. If there are any other questions, we would be happy to answer them.

W1. We are the first work to analyze federated policy gradient methods with General Policy Parameterization, e.g., neural networks (Deep RL), for a Global Convergence, and achieve the SOTA results.

Even without the asynchronous setting, there is no previous FedPG work that achieves a global convergence with general policy parameterization with the SOTA rates.

Beyond that, we design the asynchronous method and further improve the performances, which is the main improvement and contribution in this paper.

We also list 4 points in W2, which makes the novelty more clear and easy to understand. If there are any other concerns, we would be happy to answer them.

W2. Thank you for bringing this synchronous work! It is indeed valuable and has several contributions to theoretical analysis. We have cited it in the updated version as it improves the results in FedRL. However, except in the synchronous setting, there are several main differences in terms of completeness and methodology:

1. We achieve a Global Convergence with the SOTA rate, while that work (FedM for short) only focuses on stationary point convergence. It seems that FedM cannot go through the global convergence analysis without new techniques.

2. We have General Function Parameterization, e.g., neural networks (Deep RL), results in both theory and experiments. That paper does not analyze the influence of general function parametrization, e.g., Deep RL, in theory. The general function approximation might bring higher sample complexity, especially for the global convergence.

3. In their setting, the local policies will not be in different steps (Fixed to the hyperparameter $K$ in their paper). In our asynchronous setting, we do not require that each agent is in the same step, which brings the second-order error term in equation 31 and unbounded variance. Thus, we design the lookahead mechanism to cancel the second-order errors, normalized updates to bound the variance, and thus, secure the convergence. This technique is new and unique.

4. Their momentum design is NOT the delay-adaptive lookahead method in our paper.

   • The momentum is used for gradient estimation (not sampling) at Step 5 in Algorithm 1. We did not state this momentum part is a novelty in our method. Our delay-adaptive lookahead method is at Step 8 in Algorithm 1 for trajectory ''sampling'' at Step 2 in Algorithm 2. This is new and has never been used before in any FedRL works.

   • On the other hand, the orders are different. In momentum methods, the momented point is ''between'' the old ($k-1$)-th and the new $k$-th points. In our delay-adaptive lookahead method, the new point $k$-th is ''between'' the old ($k-1$)-th and the momented point. This is the reason that we call it ''lookahead''.

   • Roughly speaking, we have two momentums, but unlike the definition of the momentum gradient descent, the sampling one is not a conventional momentum.

W1. Thank you so much for this suggestion! The communication overhead was not the target of this paper. However, after we accepted your valuable advice and dived deep into the analysis, we found that AFedPG actually has advantages compared to FedPG. We added communication overhead results in Appendix A.3, and answered Q3. We hope this could address your concerns.

W2. Thank you! We have fixed the typos with another round of proofreading.

Q1. In the asynchronous setting, concurrency roughly means the number of machines that are computing. In the synchronous setting, the server waits until it receives policy gradients from all $N$ agents, while in the asynchronous setting, the server runs as soon as one policy gradient is received. In a continuous space (time), it has measure zero that two discrete time spots are the same. Thus, only one agent has the possibility to be applied on the server, while the others keep computing.

Q2. It takes a very long time to wait for them to converge to the optimal point, especially when the state and action spaces are large. We only use these experiments to show the benefit of more agents. To answer the question and verify this hypothesis, we test the result on the Swimmer-v4 task. They can converge to a similar reward, while the variance (shadow area) is larger. We assume the federated setting has the potential ability to reduce the variance when more agents engage, which could be an interesting direction for future study.

Q3. Thank you for the suggestion! We have added the analysis of experiments in Appendix A.3 to further enhance it. We briefly state the key points here.

In theory, the synchronous setting and asynchronous settings have the same cumulative communication cost as the sample complexities are the same, and each agent collects the same amount of samples in each update. Our analysis shows that the AFedPG could keep the SOTA sample complexity in policy gradient methods in RL in Table 1. Moreover, when we analyze the training process through the lens of fine-grained time, AFedPG shows several advantages.

On the server side, in FedPG, it is noticeable that the communication mainly happens in a short time window in the downlink process, which brings a heavy burden with a peak, especially in the resource constraint scenario. In AFedPG, the communication is more evenly distributed, which does not have a peak burden and has less requirement for communication resources.

On the agent side, in FedPG, all agents have the same communication burden. In AFedPG, the leader agent (fast) has more communication burden $\mathcal{O}(t_{\max})$, while the straggler agent (slow) has less communication burden $\mathcal{O}(t_{\min})$. This is a more rational allocation compared to the equality setting regardless of the heterogeneous computing resources. In practice, agents have heterogeneous resources, while FedPG does not consider this and evenly distributes the burden. The equal allocation could bring too much burden for the slow ones. In AFedPG, it shifts the burden to the fast ones naturally.

We hope this section could address your concerns.

Thank you for the suggestions in general. We sincerely apologize for the confusion. If there are any other questions, we would be happy to answer them.

W1. The average among local updates is a senario in the conventional synchronous setting. In the asynchronous setting, the agent sends the update to the server as soon as it finishes the computation. In most conventional federated learning works, only the synchronous setting is considered. We aim to extend the scope to the asynchronous setting.

W2. Thanks for the suggestion! We admit that the Actor-Critic (AC) method in [3] (not PG) contains novel contributions in theoretical analysis.

However, it only includes linear parametrization, which is a very weak and unpractical result (See W3). With a general function parametrization, e.g., neural networks (Deep RL), the SOTA result (even in the single-agent setting) of the AC method is $\mathcal{O}({\epsilon}^{-3})$ [4]. It is worse than the SOTA result in policy gradient, which is $\mathcal{O}({\epsilon}^{-2.5})$. We aim to compare with the best results, and thus, choose to analyze PG methods.

W3.

1. [3] only has Linear Parametrization (Deep RL is not included.), which is a very weak result with limited meaning. With a General Function Parametrization, e.g., neural networks (Deep RL), there is no such a result. We consider a general and practical setting with a General Function Parametrization.

   • Even in the single-agent setting (without federated agents), the SOTA result of the AC method is $\mathcal{O}({\epsilon}^{-3})$ [4] and the previous approach is $\mathcal{O}({\epsilon}^{-6})$ [5], which is still worse than our $\mathcal{O}({\epsilon}^{-2.5})$. In the federated setting, there is no result that achieves $\mathcal{O}({\epsilon}^{-3})$ for AC methods. Moreover, with a general function parameterization, we compare the performances of their A3C in Figure 4, which is much worse.

2. [3] relies on a strong and unpractical assumption, Assumption 2. It assumes that the largest delay is bounded by a constant $K_{0}$. However, in practice, the slowest agent may not communicate with the server, and thus, has an infinite delay. In our analysis, we do not require any boundary for the largest delay, because we only contain the average delay in the convergence rate, and the average delay is naturally bounded by the number of agents $N$ in Lemma B.10 (our corollary).

3. [3] is an AC method with extra value networks, which requires much more computation and memory cost compared to the pure policy gradient method. Thus, the fine-tuning of Gemini and GPT4 uses policy gradient methods instead of AC methods.

Q4. We aim to train a global policy in FedRL. The theorems give the convergence rates for the policy model w.r.t. the number of global updates on the server. It has no relationship with the index of agents. We achieve a result that the global convergence rate is upper bounded by the average delay, and the average delay is bounded by the number of agents $N$. This is new in FedRL. If there are any other questions, we would be happy to answer them.

Q5. We are the first work to analyze federated policy gradient methods with General Policy Parameterization, e.g., neural networks (Deep RL), for a Global Convergence, and achieve the SOTA results.

Even without the asynchronous setting, there is NO previous FedPG work that achieves a Global Convergence with General Policy Parameterization (Deep RL) with the SOTA rates.

Beyond that, we design the asynchronous method and further improve the performances, which is the main contribution in this paper. Without our lookahead techniques, there is no global convergence rate in AFedPG with a general parameterization setting, because the second-order errors are hard to bound. We find that the asynchronous method (with our techniques) is not just as good, but better.

Q6. Thank you for the suggestion. We have changed the order in the main paper.

[4] Closing the Gap: Achieving Global Convergence (Last Iterate) of Actor-Critic under Markovian Sampling with Neural Network Parametrization. ICML 2024.

[5] Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy. ICLR 2021.

Thank you for reading the paper carefully! Hopefully, we have answered all your questions. If there are any other concerns, we would be happy to answer them.

W1. We are sorry about the confusion. In the original algorithms, the $k$ on the server and agent sides are not the same one. To avoid confusion, we have reconstructed the algorithm description (Algorithm 1 and 2), while keeping all notations unchanged in the theoretical analysis. In the new description, a simple plugin between the equations will lead to the theoretical results. We hope this could help.

W2. Thank you so much for bringing this! It is indeed a typo. It should be $d_{k-1-\delta_{k-1}}$ instead of $d_{\delta_{k-1}}$. We have fixed the typo, and it should be consistent now.

We have $e_{k} = d_{k - \delta_{k}} - \nabla J(\theta_{k})$ and $d_{k - \delta_{k}} = (1 - \alpha_{k - \delta_{k}}) d_{k-1 - \delta_{k-1}}$ $+ \alpha_{k - \delta_{k}}$ $g(\tau_{k - \delta_{k}}, \theta_{k - \delta_{k}})$. (It is unable to show \widetilde in $g(\cdot)$ here.)

Combining them, we have $e_{k} = (1 - \alpha_{k - \delta_{k}}) d_{k-1 - \delta_{k-1}} - \nabla J(\theta_{k}) + \alpha_{k - \delta_{k}}$ $g(\tau_{k - \delta_{k}}, \theta_{k - \delta_{k}})$. Then, we can have the result in equation 31, and construct the recursive form.

W3. In the worst case, the largest delay could be infinite (not communicate at all), while the average delay is upper bounded by $N$.

We have a very interesting result in AFedPG. We do not make any assumptions about the delay, and the largest delay is allowed to be infinite. If some agents do not communicate at all, we simply lose their computation resources. The convergence rate is upper bounded by the average delay $\bar{\delta}$, and the average delay is bounded by $N$ in Lemma B.10. In equation 37, the term with the average delay is much smaller than the dominated term $\mathcal{O}(K^{-2.5})$ ($K$ could reach an order of magnitude of six or even larger.), and thus, does not hurt the convergence rate.

W4. Thank you for the suggestion! We have added the explanation with detailed derivation in Appendix A.1. It should be very easy to understand.

W5. As the agent has the same computation requirement in each iteration (The number of collected samples is the same.), we assume that the time complexity in each iteration is the same. Sorry about the confusion. We have added this statement in line 392.

Dear Reviewer,

We have uploaded a new version with more results and improvements based on your valuable suggestions.

Here are the results that we have added, as suggested by you:

• Re-state the algorithms with clear explanations.
• Time complexity analysis and explanations in Appendix A.1.
• More explanations with details in the proof in Appendix B.

Some main results suggested by the others:

• Reward performances with long runs in Appendix A.3.
• Communication overhead analysis and comparisons between asynchronous and synchronous settings in Appendix A.3.

We hope this would answer your questions and address your concerns. We would truly appreciate it if you could re-evaluate the work accordingly.