Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning

Response to Reviewer vHsi

Thank you for your time in reviewing our paper. We appreciate your positive feedback. Below We address your points. If our responses adequately address your concerns, we would be grateful if you could consider increasing your current score. And we are happy to answer your additional questions.

(W1) regarding the name "multi-task RL"

We understand your concern about the potential confusion between "multi-task RL" and the cooperative nature of our setting. However, we believe that "multi-task RL" and "cooperative RL" are not mutually exclusive terms, as they describe different aspects of the problem:

1. "Multi-task RL" refers to the fact that each agent has a different reward function, corresponding to different tasks or objectives within the same environment.
2. "Cooperative" describes the agents' willingness to work together towards a common goal, in this case maximizing the averaged reward

We have explicitly specified in our paper that we are considering a cooperative setting within the multi-task framework. This approach is consistent with existing literature in the field. For example, [1] and [2] consider respectively the cooperative and adversarial settings within multi-task RL, demonstrating that the term "multi-task" does not inherently imply either cooperation or competition.

(W2) The convergence rate of federated NAC seems to be much worse (especially in terms of the dependence on $1/(1-\gamma)$) compared with that of federated Q-learning. Is there a fundamental reason behind it?

We want to clarify that our setting is different that of Federated Q-learning (e.g, Woo et al. 2023). Woo et al. 2023 considers the server-client setting, where all the agents share the same environment (both transition kernel and reward function), so the local value functions are in fact the same and no environment heterogeneity is tackled.

Suppose that we do not change the goal (which is to have global optimality with respect to the original model not the regularized one) but use regularization as a means for algorithm design. By letting $\tau$ go to zero at an appropriate rate, or choosing $\tau$ based on the required accuracy, what is the iteration and sample complexity of entropy-regularized NAC? Do we get $\varepsilon^{-2}$ or something worse?

Thank you for your question. Setting $\tau=\frac{(1-\gamma)\varepsilon}{4\log |A|}$ guarantees $V^\star_\tau=V^\star$ and ensures we do not change the goal (see (25) in [3]). Here we adopt this choice of $\tau$ and let $\eta=\eta_0$ defined in Theorem 3.6. Then similar as in Remark D.1 in our paper, by employing fresh samples for the policy evaluation of each agent at every iteration, set $\varepsilon_q$ in Theorem 3.8 to be $\varepsilon_q = \mathcal{O}\left(\frac{\tau^2\varepsilon}{\gamma^2N\sigma^2+(1-\sigma)^2\tau^2(1-\gamma)^6}\right),$ and invoke the union bound over the iteration complexity $\widetilde{\mathcal{O}} \left(\frac{N\sigma^2}{\tau^2}+\frac{1}{1-\gamma}\right)$, we could give a loose upper bound of sample complexity of entropy-regularized FedNPG as $\widetilde{\mathcal{O}} \left(\frac{N(N\sigma^2+\tau^2)^2}{\tau^4\varepsilon^2}\left(\frac{N\sigma^2}{\tau^2}+\frac{1}{1-\gamma}\right)\right).$

Here we only highlight $\varepsilon$-dependency to simplify the expressions.

• When $\sigma=0$ (the server-client setting), the above complexity becomes $\widetilde{\mathcal{O}} \left(\varepsilon^{-2}\right)$, recovering that of single-agent entropy-regularized NPG ([3]).

• When $\sigma$ is close to 1, the above complexity becomes $\widetilde{\mathcal{O}} \left(\varepsilon^{-8}\right)$, which is worse than the bound for inexact vanilla FedNPG $\widetilde{\mathcal{O}} \left(\varepsilon^{-3.5}\right)$ presented in (19). Therefore, FedNAC focused on unregularized case as it has better rates when the goal is to solve the unregulairzed problem.

• The reason why the bound for the entropy-regularized case is worse may be due to proof artifacts as we need to address the complicated interplay between consensus errors and optimization errors (recall that simiar to the single-agent case, in our federated setting, vanilla FedNPG and entropy-regularzied FedNPG also require different proof frameworks), and we leave tightening the bound for future work.

---

[1] S Zeng et al. (2021) A Decentralized Policy Gradient Approach to Multi-Task Reinforcement Learning.

[2] A Anwar and A Raychowdhury (2021). Multi-task federated reinforcement learning with adversaries.

[3] S Cen et al. (2023). Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization.

Response to Reviewer LgxC

Thank you for your review and positive comments. Below we address you questions point-by-point. If our responses resolve your concerns, we'd appreciate your consideration of increasing your current score. Certainly, please also let us know if you have further questions.

regarding learning objective

While we appreciate the perspective that finding local optimal policies for different tasks could be an alternative objective, we believe the problem of finding a single global policy that maximizes the average performance across all tasks is also valuable and necessary in many scenarios, especially when the goal is to collectively maximize the global performance (e.g., for fairness). Please refer to Appendix B for details. We also provide a few examples here:

• The GridWorld experiment in our paper (Appendix H), where agents collectively learn to navigate a global map with partial information. This problem could be seen as a simplified version of the Unmanned Aerial Vehicle (UAV) Patrol Mission, each UAV patrols only in a specific area, and they need to collectively train a strategy utilizing information from the entire patrol range.

• Multi-task robot control, where a single robot needs to perform well across various tasks.

Note that our objective is well-established in the federated/decentralized RL literature, see [1-3] for example.

regarding technical novelty

We have a detailed discussion on our technical novelty in Appendix B.2. We also summarize our key points here to give you a better understanding of the technique difficulties we conquer:

One key difficulty is to estimate the global Q-functions using only neighboring information and local data. To address this issue, we invoke the "Q-tracking" step (see Algorithm 1,2), which is inspired by the gradient tracking method in decentralized optimization. Note that this generalization is highly non-trivial: to the best of our knowledge, the utility of gradient tracking has not been exploited in policy optimization, and the intrinsic nonconcavity issue, together with the use of natural gradients, prevents us from directly using the results from decentralized optimization. It is thus of great value to study if the combination of NPG and gradient tracking could lead to fast globally convergent algorithms as in the standard decentralized optimization literature despite the nonconcavity.

Besides, due to the lack of global information sharing, care needs to be taken to judiciously balance the use of neighboring information (to facilitate consensus) and local data (to facilitate learning) when updating the policy. Compared to the centralized version of our proposed algorithms, a much more delicate theoretical analysis is required to prove our convergence results. For example, the key step to establish the convergence rate of the single-agent exact entropy-regularized NPG is to form the 2nd-order linear system in Eq.(47) in Cen et al., 2021, while in our corresponding analysis, a 4th-order linear system in Lemma 1 is needed, where the inequality in each line is non-trivial and requires the introduction of some intricate and novel auxiliary lemmas, see appendix D.

---

[1] S Zeng et al. (2021) A Decentralized Policy Gradient Approach to Multi-Task Reinforcement Learning.

[2] K Zhang et al. (2018) Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents.

[3] T Chen et al. (2022) Communication-Efficient Policy Gradient Methods for Distributed Reinforcement Learning.

Dear Reviewer LgxC,

We've taken your initial feedback into careful consideration in our response. Could you kindly confirm whether our responses have appropriately addressed your concerns?

If you find that we have properly addressed your concerns, could you please kindly consider increasing your initial score accordingly? Please let us know if you have further comments.

Thank you for your time and effort in reviewing our work!

Many thanks, Authors

Response to Reviewer tByy

Thank you for your comments. Below we answer your questions point-by-point. If these clarifications address your primary concerns, we'd appreciate your consideration of increasing your score. Certainly, please don't hesitate to request any further clarification.

defer related work to the Supplementary Material

Thank you for your feedback. Our decision was driven by the page limitation and the extensive technical content in the main paper. We'll put the related work to the main paper if this work is accepted and an extra page is allowed.

regarding our claim: federated NPG and NAC methods are the first policy optimization methods for multi-task RL that achieve explicit non-asymptotic global convergence guarantees in terms of iteration and sample complexity.

• We thank the reviewer for bringing this up, and apologize for missing the early literature.

• We will adjust our claim to the following:

  the proposed federated NPG and NAC methods are the first natural policy gradient based methods for multi-task RL that achieve explicit non-asymptotic global convergence guarantees in terms of iteration and sample complexity.

• We want to point out that [ZAD+21] studied decentralized PG and did not provide sample complexity analysese, as they assume the advantage function is obtained by oracle. Besides, our entropy-regularized FedNPG has last-iterate convergece guarantee while their algorithm doesn't, even though they also use entropy regularization, and the iteration complexity of ours is better than [ZAD+21] as we leverage NPG-based updates. We'll add a brief comparison with [ZAD+21] in our paper to highlight the distinctions of our results.

You have $\sigma$ for a fully connected graph ... is "client-server" the best way to describe this?

• We appreciate your attention to this detail and will add the following clarification in our updated paper:

In our paper, we use the term "server-client" to refer to the centralized learning setting where there exists a central server that aggregates information from all agents (clients) and the distributes the aggregated information back to all agents. The mixing matrix $W$ of the server-client setting is $W=1/N \boldsymbol{1}_N\boldsymbol{1}_N^\top$ and by Definition 3.2, the spectral radius $\sigma$ is 0 for this case.

• The use of "server-client" to describe this centralized architecture is common in the decentralized learning literature ([1-3]).

points in Appendix B.1 not addressed

We want to clarify that our goal is to learn an optimal policy that maximizes the total values over all the agents, rather than hoping to maximize the individual value functions at each agent.

In line 575, by "accelerating learning and improving performance by leveraging experiences gained from one task to another," we mean that our federated approach allows agents to collectively learn a policy that performs well across all tasks, which would not be possible if agents learned independently.

concerns regarding the examples

We acknowledge that real-world scenarios are often more complex. Our model represents a meaningful simplification to enable rigorous mathematical analysis, while still capturing essential features of federated multi-task RL problems. While current practice of some applications we envisioned may not be completely aligned with the setting of our federated RL framework, we hope that our algorithm designs might inspire their future adoption into practice.

---

[1] J Ma et al. (2021). Adaptive distillation for decentralized learning from heterogeneous clients.

[2] R Gu et al. (2021). From server-based to client-based machine learning: A comprehensive survey.

[3] H Kasyap et al. (2021). Privacy-preserving decentralized learning framework for healthcare system.

Response to Reviewer bXwg

Thank you for your feedback. Below We address your concerns. If our responses resolve your questions, we'd appreciate your consideration in raising the score. For any remaining issues, please don't hesitate to let us know.

(Weaknesses) how to obtain the mixing matrix $W$ in practice

There are several standard designs for $W$, such as uniform weights (where each agent assigns equal weight to itself and all its neighbors), Metropolis-Hasting weights (based on the degree of each node) [1], and Laplacian-based weights [2], with the aim that the designed $W$ agrees with the graph topology while mixing fast. Some papers also propose optimization methods to find $W$, see [3] for example.

examples of the mixing matrix $W$

We are happy to provide the following examples:

• In the server-client setting, the mixing matrix is a rescaled all-one matrix.

• In our experiment we assume the commucation network is a standard ring graph whose corresponding mixing matrix is given in Eq.(304) in Appendix H.

• In the star network [2], one central agent communicates with all others and peripheral agents only communicate with the center. It's corresponding mixing matrix is given by [[1/4 1/4 1/4 1/4], [1/2 1/2 0 0], [1/2 0 1/2 0], [1/2 0 0 1/2]] where we assume $N=4$.

• In random network [1], the connections of the nodes are random.

regarding the aggregated policy $\bar \pi^{(t)}$

We want to clarify that in the formal version of all our theorems, we provide consensus error bounds which demonstrate the local policies converge to the aggregated policy $\bar \pi^{(t)}$, i.e., there is no need to construct the aggregated policy $\bar \pi^{(t)}$ in practice. Please see (47) (exact entropy-regularized FedNPG), (65) (inexact entropy-regularized FedNPG), (72) (exact vanilla FedNPG), (93) (inexact vanilla FedNPG) and (129) (FedNAC). They show that analyzing the convergence of $\bar \pi^{(t)}$ is meaningful and directly relevant to the behavior of the local policies in the decentralized setting.

The authors need to more clearly address the limitations on the required information of the proposed algorithms.

We speculate that the reviewer is inquiring about the specific information each agent needs to know and share for the algorithms to function properly. Please let us know if our interpretation is incorrect. To address this, we will clarify in the paper that each agent $i$ only needs to know its local reward function $r_i$, its neighbors and the corresponding weights $w_{ij}$. No global information or centralized computation is required during the algorithm execution, and agents only share local policy and Q-function estimates with neighbors.

---

Reference:

[1] Y Dandi et al. (2022). Data-heterogeneity-aware mixing for decentralized learning.

[2] CC Chiu et al. (2023). Laplacian matrix sampling for communication-efficient decentralized learning.

[3] L Xiao, S Boyd (2004). Fast linear iterations for distributed averaging.

[4] Qu G, Li N (2017). Harnessing smoothness to accelerate distributed optimization[J].

[5] Zhao et al (2022). BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression.