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

Summary

This paper studies RL in the federated setting, where each agent only receives a local reward and communicates with other agents in a networked graph. The authors develop federated natural actor-critic in the tabular setting and the linear function approximation setting, with exact and inexact policy evaluation. In all cases, convergence rate guarantees are provided.

Strengths

The presentation is mostly clear. The theoretical results are solid and seem to be the first in the federated setting.

Weaknesses

(1) Calling the setting "multi-task RL" is a bit confusing. Since each agent has its own reward function, which can be misaligned with other agents' reward functions, assuming that all agents are willing to collaborate to reach a common goal (maximizing the averaged reward) can be unreasonable. For example, suppose there are only three agents, and $r_1=r_2=-r_3$. In this case, the optimal policy for the averaged reward is the same as the local optimal policy for agents 1 and 2, but it is the exact opposite of what agent 3 wants. Therefore, there is no reason to assume that agent 3 is willing to collaborate. Perhaps directly calling the setting "cooperative RL" is more suitable. (2) 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? (3) 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 $\epsilon^{-2}$ or something worse?

Questions

See the section above.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

Summary

This paper studied federated multi-task reinforcement learning (RL), where multiple learning agents interact with different RL problems (different rewards) and communicate through an arbitrary communication graph. This paper proposed a federated natural policy gradient algorithm and a federated natural actor-critic algorithm. Both methods are proved to converge to a global optimum with favorable convergence rate.

Strengths

1. The paper is technically sound. 2. The studied problem is well-motivated 4. The results are solid and provide insightful relationship between the number of tasks and convergence rate.

Weaknesses

1. The learning objective function is less general. When the rewards are different, a better learning goal is to find local optimal policies for different tasks (agents). 2. The technical novelty is less clear. For example, compared to the single task counterpart (Cen et al, 2021), is there any technical difficulties? Cen et al., Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization, 2021

Questions

Please see the weaknesses part.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

No further limitations to be addressed.

Summary

A decentralized policy-gradient algorithm is introduced. The setting is that multiple agents are operating in environments with identical states, actions, and dynamics but different reward functions; the goal is for the agents to collaboratively find a common policy that maximimzes the aggregate value across all tasks. Convergence results are presented both with and without entropy regularization.

Strengths

The convergence results are strong in that the dependence on $T$ is reasonable and the dependence on the sizes of the state and action spaces is weak. I appreciate the high-level discussion in Appendix B and the over-arching research goal of trying to understand multi-task learning from a mathematical point of view.

Weaknesses

The decision to defer a careful comparison to related work to the Supplementary Material is questionable. Lines 100-101: "To the best of our knowledge, the proposed federated NPG and NAC methods are the first policy 101 optimization methods for multi-task RL that achieve explicit non-asymptotic global convergence 102 guarantees in terms of iteration and sample complexities, allowing for fully decentralized communi- 103 cation without any need to share local reward/task information." I am not sure that I agree with this statement. Theorem 2 in [ZAD+21] seems to do exactly this. The algorithm is different (but still fully decentralized) and the results are not quite as strong, but it does provide non-asymptotic global convergence guarantees in terms of iteration and sample complexities. Line 215: You have $\sigma=0$ for a fully connected graph ... is "client-server" the best way to describe this? While I really do appreciate the discussion in Appendix B.1, none of the points brought up there are addressed by the results in the paper. Nothing in the theoretical results shows that the agents learn any faster because they are communicating then they would just learning their own tasks independently; nothing in the results speaks to the generalization of the common policy learned to a new task; there may be something to scalability here, but that would be the same for any federated learning setting. Also, let me just nitpick the way a few of the examples relate to the paper: It is unclear why healthcare providers or people training large ChatGPT models would be restricting themselves to communicating on a mesh network. The problem of UAVs patrolling different areas then combining their results is probably more appropriately modeled as different state spaces with the same reward functions, rather than same state space with different rewards. It is hard to imagine that having a common policy across different characters in a video game captures the spirit of learning to play video games; many times the whole point of having different characters is that they have different optimal control policies.

Questions

None,

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

None.

Summary

The paper studies the federated multi-task reinforcement learning in a decentralized setting. In the problem, the agents share the same transition kernel but have different reward functions. The communications of agents are defined on a prescribed graph topology. The authors first consider tabular setting and develop a federated natural policy gradient (FedNPG) to solve the problem and prove the sublinear convergence. Besides, the authors extend FedNPG to function approximation setting and propose a federated natural actor critic with its theoretical convergence guarantee. The proposed algorithms are evaluated on a $K\times K$ GridWorld problem.

Strengths

The strengths of the paper are summarized as below. + The paper considers federated reinforcement learning in a decentralized setting, which is challenging and closely related to the concerns of the community. + The paper develops algorithms for different cases with tabular settings and function approximation settings. + The paper gives the first rigorous analysis on the convergence rate of the FedNPG and FedNAC, which illustrates some insights including the impact of the spectral radius $\sigma$ on the performance.

Weaknesses

The proposed algorithm aggregates the neighborhood information by a mixing matrix $W$. However, it is unclear how to obtain the matrix $W$ in the practical decentralized setting. It would be better to have more explanations on this.

Questions

In the considered setting, the agents learn their own policies in an online decentralized manner while the convergence analysis is about the aggregated policy $\bar{\pi}^t$. The calculation of $\bar{\pi}^t$ needs the results of all $N$ policies. This seems to be contradictory with the decentralized setting. Can the authors give some examples about the mixing matrix $W$ and show how to obtain the matrix $W$? I am happy to change the score according to the answers.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

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

Rebuttal Feedback

Thank the authors for the response. I have raised my score. W1: I could not find the word "cooperative" in the paper. Please make it explicit in the paper. W2: The authors address my concerns. W3: Out of curiosity, do the authors expect the $O(1/\epsilon^{-2})$ sample complexity to be achievable for federated Q-learning and NAC?