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

Authors: tong  yang
shicong  cmu
  cen
cmu  yuting
wei ‡ upenn
yuxin  chen
upenn  yuejie
chi ¶ cmu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 01:56:26

Abstract: Federated reinforcement learning (RL) enables collaborative decision making of multiple distributed agents without sharing local data trajectories. In this work, we consider a multi-task setting, in which each agent has its own private reward function corresponding to different tasks, while sharing the same transition kernel of the environment. Focusing on infinite-horizon Markov decision processes, the goal is to learn a globally optimal policy that maximizes the sum of the discounted total rewards of all the agents in a decentralized manner, where each agent only communicates with its neighbors over some prescribed graph topology.

We develop federated vanilla and entropy-regularized natural policy gradient (NPG) methods in the tabular setting under softmax parameterization, where gradient tracking is applied to estimate the global Q-function to mitigate the impact of imperfect information sharing. We establish non-asymptotic global convergence guarantees under exact policy evaluation, where the rates are nearly independent of the size of the state-action space and illuminate the impacts of network size and connectivity. To the best of our knowledge, this is the first time that global convergence is established for federated multi-task RL using policy optimization. We further go beyond the tabular setting by proposing a federated natural actor critic (NAC) method for multi-task RL with function approximation, and establish its finite-time sample complexity taking the errors of function approximation into account.

Main paper: 
 introduction: 
 Federated reinforcement learning (FRL) is an emerging paradigm that combines the advantages of federated learning (FL) and reinforcement learning (RL) [QZLZ21, ZFL + 19], allowing multiple agents to learn a shared policy from local experiences, without exposing their private data to a central server nor other agents. FRL is poised to enable collaborative and efficient decision making in scenarios where data is distributed, heterogeneous, and sensitive, which arise frequently in applications such as edge computing, smart cities, and healthcare [WHM + 23, WKNL20, ZFL + 19], to name just a few. As has been observed [LZZ + 17], decentralized training can lead to performance improvements in FL by avoiding communication congestions at busy nodes such as the server, especially under high-latency scenarios. This motivates us to design algorithms for the fully decentralized setting, a scenario where the agents can only communicate with their local neighbors over a prescribed network topology. 6In this work, we study the problem of federated multi-task RL [AR21, QZLZ21, YLS + 20], where each agent collects its own reward -possibly unknown to other agents -corresponding to the local task at hand, while having access to the same dynamics (i.e., transition kernel) of the environment. The collective goal is to learn a shared policy that maximizes the total rewards accumulated from all the agents; in other words, one seeks a policy that performs well in terms of overall benefits, rather than biasing towards any individual task, achieving the Pareto frontier in a multi-objective context. There is no shortage of application scenarios where federated multi-task RL becomes highly relevant. For instance, in healthcare [ZBW + 20], different hospitals may be interested in finding an optimal treatment for all patients without disclosing private data, where the effectiveness of the treatment can vary across different hospitals due to demographical differences. See Appendix B.1 for more application scenarios of our setting.Nonetheless, despite the promise, provably efficient algorithms for federated multi-task RL remain substantially under-explored, especially in the fully decentralized setting. The heterogeneity of local tasks leads to a higher degree of disagreements between the global value function and local value functions of individual agents. 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. To the best of our knowledge, very few algorithms are currently available to find the global optimal policy with non-asymptotic convergence guarantees even for tabular infinite-horizon Markov decision processes.Motivated by the connection with decentralized optimization, it is tempting to take a policy optimization perspective to tackle this challenge. Policy gradient (PG) methods, which seek to learn the policy of interest via first-order optimization methods, play an eminent role in RL due to their simplicity and scalability. In particular, natural policy gradient (NPG) methods [Ama98, Kak01] are among the most popular variants of PG methods, underpinning default methods used in practice such as trust region policy optimization (TRPO) [SLA + 15] and proximal policy optimization (PPO) [SWD + 17]. On the theoretical side, it has also been established recently that the NPG method enjoys fast global convergence to the optimal policy in an almost dimension-free manner [AKLM21, CWC21] , where the iteration complexity is nearly independent of the size of the state-action space. These benefits can be translated to their sample-based counterparts such as the natural actor critic (NAC) method [BSGL09, XWL20, KDRM22] , where the policies are evaluated via stochastic samples. It is natural to ask:Can we develop federated NPG and NAC methods with non-asymptotic global convergence guarantees for multi-task RL in the fully decentralized setting?1.1 Our contributions Focusing on infinite-horizon Markov decision processes (MDPs), we provide an affirmative answer to the above question, by developing federated NPG (FedNPG) methods for solving both the vanilla and entropy-regularized multi-task RL problems with finite-time global convergence guarantees. While entropy regularization is often incorporated as an effective strategy to encourage exploration during policy learning, solving the entropy-regularized RL problem is of interest in its own right, as the optimal regularized policy possesses desirable robust properties with respect to reward perturbations [EL21, MP95] . Due to the multiplicative update nature of NPG methods under softmax parameterization, it is more convenient to work with the logarithms of local policies in the decentralized setting.In each iteration of the proposed FedNPG method, the logarithms of local policies are updated by a weighted linear combination of two terms (up to normalization): a gossip mixing [NO09] of the logarithms of neighboring local policies, and a local estimate of the global Q-function tracked via the technique of dynamic average consensus [ZM10] , a prevalent idea in decentralized optimization that allows for the use of large constant learning rates [DLS16, NOS17, QL17] to accelerate convergence. We further develop sample-efficient federated NAC (FedNAC) methods that allow for both stochastic policy evaluation and function approximation. Our contributions are as follows.• We propose FedNPG methods for both the vanilla and entropy-regularized multi-task RL problems, where each agent only communicates with its neighbors and performs local computation using its own reward or task information.setting algorithms iteration complexity optimality criteria unregularized NPG [AKLM21] O1 (1-γ) 2 ε + log |A| ηε V ⋆ -V π (t) ≤ ε FedNPG (ours) O σ √ N log |A| (1-γ) 9 2 (1-σ)ε 3 2 + 1 (1-γ) 2 ε 1 T T -1 t=0 V ⋆ -V π (t) ≤ ε regularized NPG [CWC21] O 1 τ η log 1 ε V ⋆ τ -V π (t) τ ≤ ε FedNPG (ours) O max 1 τ η , 1 1-σ log 1 ε V ⋆ τ -V π (t) τ ≤ εTable 1 : Iteration complexities of NPG and FedNPG (ours) methods to reach ε-accuracy of the vanilla and entropy-regularized problems, where we assume exact gradient evaluation, and only keep the dominant terms w.r.t. ε. The policy estimates in the t-iteration are π (t) and π(t) for NPG and FedNPG, respectively, where T is the number of iterations. Here, N is the number of agents, τ ≤ 1 is the regularization parameter, σ ∈ [0, 1] is the spectral radius of the network, γ ∈ [0, 1) is the discount factor, |A| is the size of the action space, and η > 0 is the learning rate. The iteration complexities of FedNPG reduce to their centralized counterparts when σ = 0. For vanilla FedNPG, the learning rateis set as η = η 1 = O (1-γ) 9 (1-σ) 2 log |A| T N σ 1/3; for entropy-regularized FedNPG, the learning rate satisfies 0 < η < η 0 = O (1-γ) 7 (1-σ) 2 τ σN .• Assuming access to exact policy evaluation, we establish that the average iterate of vanilla FedNPG converges globally at a rate of O(1/T 2/3 ) in terms of the sub-optimality gap for the multi-task RL problem, and that the last iterate of entropy-regularized FedNPG converges globally at a linear rate to the regularized optimal policy. Our convergence theory highlights the impacts of all salient problem parameters (see Table 1 for details), such as the size and connectivity of the communication network. In particular, the iteration complexities of FedNPG are again almost independent of the size of the state-action space, which recover prior results on the centralized NPG methods when the network is fully connected. • We further demonstrate the stability of the proposed FedNPG methods when policy evaluations are only available in an inexact manner. To be specific, we prove that their convergence rates remain unchanged as long as the approximation errors are sufficiently small in the ℓ ∞ sense. • We go beyond the tabular setting and black-box policy evaluation by proposing FedNAC-a federated actor critic method for multi-task RL with function approximation and stochastic policy evaluation -and establish a finite-sample sample complexity on the order of O(1/ε 7/2 ) for each agent in terms of the expected sub-optimality gap for the fully decentralized setting. To the best of our knowledge, the proposed federated NPG and NAC methods are the first policy optimization methods for multi-task RL that achieve near dimension-free global convergence guarantees in terms of iteration and sample complexities, allowing for fully decentralized communication without any need to share local reward/task information. We conduct numerical experiments in a multi-task GridWorld environment to corroborate the efficacy of the proposed methods (see Appendix H). We defer the readers to Appendix A for more related work, and Appendix B.2 for additional discussions on our theoretical contributions.Notation. Boldface small and capital letters denote vectors and matrices, respectively. Sets are denoted with curly capital letters, e.g., S, A. We let (R d , ∥•∥) denote the d-dimensional real coordinate space equipped with norm ∥•∥. The ℓ p -norm of v is denoted by ∥v∥ p , where 1 ≤ p ≤ ∞, and the spectral norm and the Frobenius norm of a matrix M are denoted by ∥M ∥ 2 and ∥M ∥ F , resp. We let [N ] denote {1, . . . , N }, use 1 N to represent the all-one vector of length N , and denote by 0 a vector or a matrix consisting of all 0's. We allow the application of functions such as log(•) and exp(•) to vectors or matrices, with the understanding that they are applied in an element-wise manner. 
model and backgrounds: 
 Markov decision processes. We consider an infinite-horizon discounted Markov decision process (MDP) denoted by M = (S, A, P, r, γ), where S and A denote the state space and the action space, respectively, γ ∈ [0, 1) indicates the discount factor, P : S × A → ∆(S) is the transition kernel, and r : S × A → [0, 1] stands for the reward function. To be more specific, for each state-action pair (s, a) ∈ S × A and any state s ′ ∈ S, we denote by P (s ′ |s, a) the transition probability from state s to state s ′ when action a is taken, and r(s, a) the instantaneous reward received in state s when action a is taken. Furthermore, a policy π : S → ∆(A) specifies an action selection rule, where π(a|s) specifies the probability of taking action a in state s for each (s, a) ∈ S × A.For any given policy π, we denote by V π : S → R the corresponding value function, which is the expected discounted cumulative reward with an initial state s 0 = s, given by ∀s ∈ S : V π (s) := E ∞ t=0 γ t r(s t , a t )|s 0 = s ,where the randomness is over the trajectory generated following the policy a t ∼ π(•|s t ) and the MDP dynamic s t+1 ∼ P (•|s t , a t ). We also overload the notation V π (ρ) to indicate the expected value function of policy π when the initial state follows a distribution ρ over S, namely, V π (ρ) := E s∼ρ [V π (s)]. Similarly, the Q-function Q π : S × A → R of policy π is defined byEQUATIONfor all (s, a) ∈ S ×A, which measures the expected discounted cumulative reward with an initial state s 0 = s and an initial action a 0 = a, with expectation taken over the randomness of the trajectory. The optimal policy π ⋆ refers to the policy that maximizes the value function V π (s) for all states s ∈ S, which is guaranteed to exist [Put14] . The corresponding optimal value function and Q-function are denoted as V ⋆ and Q ⋆ , respectively.Entropy-regularized RL. Entropy regularization [WP91, ALRNS19] is a popular technique in practice that encourages stochasticity of the policy to promote exploration, as well as robustness against reward uncertainties. Mathematically, this can be viewed as adjusting the instantaneous reward based the current policy in use as ∀(s, a) ∈ S × A : r τ (s, a) := r(s, a) -τ log π(a|s) ,where τ ≥ 0 denotes the regularization parameter. Typically, τ should not be too large to outweigh the actual rewards; for ease of presentation, we assume τ ≤ min 1, 1 log |A| [CCDX22] . Equivalently, this amounts to the entropy-regularized (also known as "soft") value function, defined as ∀s ∈ S : V π τ (s) := V π (s) + τ H(s, π),whereEQUATIONAnalogously, for all (s, a) ∈ S × A, the regularized (or soft) Q-function Q π τ of policy π is related to the soft value function V π τ (s) asEQUATIONThe optimal regularized policy, the optimal regularized value function, and the Q-function are denoted by π ⋆ τ , V ⋆ τ , and Q ⋆ τ , respectively. Natural policy gradient methods. Natural policy gradient (NPG) methods lie at the heart of policy optimization, serving as the backbone of popular heuristics such as TRPO [SLA + 15] and PPO [SWD + 17]. Instead of directly optimizing the policy over the probability simplex, one often adopts the softmax parameterization, which parameterizes the policy as π θ := softmax(θ) or π θ (a|s) := exp θ(s, a)EQUATIONfor any θ: S × A → R and (s, a) ∈ S × A.In the tabular setting, the update rule of vanilla NPG at the t-th iteration can be concisely represented asEQUATIONTurning to the regularized problem, we note that the update rule of entropy-regularized NPG becomesEQUATIONwhere η ∈ (0, 1-γ τ ] is the learning rate, andQ (t) τ = Q π (t)τ is the soft Q-function of policy π (t) .3 Federated NPG methods for multi-task RLIn this paper, we consider the federated multi-task RL setting, where a set of agents learn collaboratively a single policy that maximizes its average performance over all the tasks using only local computation and communication.Multi-task RL. Each agent n ∈ [N ] has its own private reward function r n (s, a) -corresponding to different tasks -while sharing the same transition kernel of the environment. The goal is to collectively learn a single policy π that maximizes the global value function given by V π (s) =1 N N n=1 V π n (s), where V π n is the value function of agent n ∈ [N ], defined by V π n (s) := E ∞ t=0 γ t r n (s t , a t )|s 0 = s .Clearly, the global value function corresponds to using the average reward of all agents r(s, a) =1 N N n=1 r n (s, a). The global Q-function Q π (s, a) and the agent Q-functions Q π n (s, a) can be defined in a similar manner obeying Q π (s, a) = 1 N N n=1 Q π n (s, a).In parallel, we are interested in the entropy-regularized setting, where each agent n ∈ [N ] is equipped with a regularized reward function given by r τ,n (s, a) := r n (s, a) -τ log π(a|s). And we define similarly the regularized value functions asEQUATIONand the global soft Q-function is given byEQUATIONs, a). Federated policy optimization in the fully decentralized setting. We consider a federated setting with fully decentralized communication, that is, all the agents are synchronized to perform information exchange over some prescribed network topology denoted by an undirected weighted graph G([N ], E).Here, E stands for the edge set of the graph with N nodes -each corresponding to an agentand two agents can communicate with each other if and only if there is an edge connecting them. The information sharing over the graph is best described by a mixing matrix [NO09] , denoted byW = [w ij ] ∈ [0, 1] N ×N, where w ij is a positive number if (i, j) ∈ E and 0 otherwise. We also make the following standard assumptions on the mixing matrix. Assumption 3.1 (double stochasticity). The mixing matrix W= [w ij ] ∈ [0, 1] N ×N is symmetric (i.e., W ⊤ = W ) and doubly stochastic (i.e., W 1 N = 1 N , 1 ⊤ N W = 1 ⊤ N ).The following standard metric measures how fast information propagates over the graph. Definition 3.2 (spectral radius). The spectral radius of W is given asσ := ∥W -1 N 1 N 1 ⊤ N ∥ 2 ∈ [0, 1).The spectral radius σ determines how fast information propagate over the network. For instance, in a fully-connected network, we can achieve σ = 0 by settingW = 1 N 1 N 1 ⊤ N .For control of 1/(1 -σ) regarding different graphs, we refer the readers to [NOR18] . In an Erdös-Rényi random graph, as long as the graph is connected, one has with high probability σ ≍ 1. Another immediate consequence is that for any x ∈ R N , letting x = 1 N 1 ⊤ N x be its average, we haveEQUATIONwhere the consensus error contracts by a factor of σ.Algorithm 1 Federated NPG (FedNPG)1: Input: learning rate η > 0, iteration number T ∈ N + , mixing matrix W ∈ R N ×N . 2: Initialize:π (0) , T (0) = Q (0) . 3: for t = 0, 1, • • • T -1 do 4:Update the policy for each (s, a) ∈ S × A:EQUATIONwherez (t) (s) = a ′ ∈A exp W log π (t) (a ′ |s) + η 1-γ T (t) (s, a ′ ) . 5:Evaluate Q (t+1) .Update the global Q-function estimate for each (s, a) ∈ S × A:EQUATION)7: end for 3.1 Proposed federated NPG algorithms Assuming softmax parameterization, the problem can be formulated as decentralized optimization,EQUATIONEQUATIONwhere π θ := softmax(θ) subject to communication constraints. Motivated by the success of NPG methods, we aim to develop federated NPG methods to achieve our goal. For notational convenience, let π (t) := π(t) 1 , • • • , π (t) N⊤ be the collection of policy estimates at all agents in the t-th iteration.LetEQUATIONwhich satisfies that π (t) (a|s)∝ N n=1 π (t) n (a|s) 1/N for each (s, a) ∈ S × A. Therefore, π (t)could be seen as the normalized geometric mean of {π(t) n } n∈[N ] . Define the collection of Q-function estimates as Q (t) := Q π (t) 1 1 , • • • , Q π (t) N N ⊤ and Q (t) τ := Q π (t) 1 τ,1 , • • • , Q π (t) N τ,N. We shall often abuse the notation and treat π (t) , Qτ as matrices in R N ×|S||A| , and treat π (t) (a|s), Qτ (a|s) as vectors in R N , for all (s, a) ∈ S × A.To motivate the algorithm development, observe that the NPG method (cf. (8)) applied to (12) adopts the update rule π (t+1) (a|s) ∝π (t) (a|s) exp η N n=1 Q π (t) n (s,a) N (1-γ)for all (s, a) ∈ S × A. Two challenges arise when executing this update rule: the policy estimates are maintained locally without consensus, and the global Q-function are unavailable in the decentralized setting. To address these challenges, we apply the idea of dynamic average consensus [ZM10] , where each agent maintains its own estimate T (t) n (s, a) of the global Q-function, which are collected as vectorT (t) = T (t) 1 , • • • , T (t) N ⊤ .At each iteration, each agent updates its policy estimates based on its neighbors' information via gossip mixing, in addition to a correction term that tracks the difference Qπ (t+1) n n (s, a) -Q π (t)n n (s, a) of the local Q-functions between consecutive policy updates. Note that the mixing is applied linearly to the logarithms of local policies, which translates into a multiplicative mixing of the local policies. Algorithm 1 summarizes the detailed procedure of the proposed algorithm written in a compact matrix form, which we dub as federated NPG (FedNPG). Note that the agents do not need to share their reward functions with others, and agent n ∈ [N ] will only be responsible to evaluate the local policy π (t) n using the local reward r n .Entropy-regularized federated NPG methods. Moving onto the entropy regularized case, we adopt similar algorithmic ideas to decentralize (9), and propose the federated NPG (FedNPG) method with entropy regularization, summarized in Algorithm 2 (see Appendix C.1). Clearly, the entropyregularized FedNPG method reduces to vanilla FedNPG in the absence of the regularization (i.e., when τ = 0).For any policy π, we let d π s0 denote the discounted state visitation distribution of π given an initial state s 0 ∈ S, i.e., ∀s ∈ S :EQUATION)For a distribution ρ ∈ ∆(S), we defined π ρ (s) = E s0∼ρ [d π s0 (s)].We also define the state-action visitation distribution dπ ρ asEQUATIONFurthermore, we extend the definition of dπ ρ by specifying the initial state-action distribution ν ∈ ∆(S × A) and defineEQUATION)Our proposed federated NAC method FedNAC could be seen as a decentralized version of Q-NPG method [AKLM21, YDG + 22], which we briefly review as follows.Q-NPG method. Q-NPG is a sample version of NPG with function approximation which is suitable for the case where S or A is large or infinite. We consider the policy with function approximation under softmax parameterization (24).Given an approximate solution w (t) for minimizing the function approximation errorℓ(w, Q f ξ (t) , df ξ (t) ν) (see ( 25)), the Q-NPG update rule ξ (t+1) = ξ (t) + αw (t) , when plugged in parameterization (24), results in the following policy update rule when we set α = η/(1 -γ):EQUATIONwhich could be seen as the function approximation version of the update rule (8) of vanilla NPG method.Federated NAC method. FedNAC (describe in Section 4) is presented in Algorithm 3, whose subroutines are written in Algorithm 4, 5. In each iteration t of FedNAC, each agent n updates the critic parameter w(t)n locally using Algorithm 4, which aims to minimize ℓ(w, Qn , d(t) n ) by stochastic gradient descent. Note that since we don't know the Q-functionQ (t)n in the gradients, we need to invoke Algorithm 5 [YDG + 22, Algorithm 3] to give an unbiased estimateQ (t) n (s, a), where (s, a) is sampled from d(t) n (cf. Theorem E.1). As a consequence, in line 4 of Algorithm 4, we haveEQUATIONIn each actor iteration, agents share with their neighbors actor and critic parameters, where the tracking scheme is also used.Algorithm 3 Federated Natural Actor-Critic (FedNAC) 1: Input: number of actor iterations T , number of critic iterations K, actor learning rate α, critic learning rate β, discounted factor γ ∈ [0, 1) 2: Initialization: initial state-action distribution ν, actor parameter ξ (0) = (ξ(0)⊤ 1 , • • • , ξ (0)⊤ N ) ⊤ ∈ R N ×p , h (-1) = w (-1) = 0 ∈ R N ×p 3: for t = 0, • • • , T -1 do 4: Critic update: w (t) n = Critic(K, ν, ξ (t) n , γ, β, r n ), n ∈ [N ] (Algorithm 4) 5:Update the critic parameter for estimating the global Q-function:EQUATIONActor update:EQUATION7: end for Algorithm 4 Critic(K, ν, ξ, γ, β, r): sample-based regression solver to minimize ℓ(w, Q(t) n , d(t) n ) 1: Initialize: critic parameter w 0 ∈ R p 2: for k = 0, • • • , K -1 do 3: Sampling: (s k , a k ), Q π (s k , a k ) =Q-Sampler(ν, f ξ , γ, r) (Algorithm 5) 4:Compute the stochastic gradient estimator of L Q :EQUATIONCritic Update:w k+1 = w k -β ∇ w ℓ( w k , Q π , df ξ ) 6: end for 7: Output: w out = 1 K K k=1 w k 
theoretical guarantees: 
 Global convergence of FedNPG with exact policy evaluation. We begin with the global convergence of FedNPG (cf. Algorithm 1), stated in the following theorem. The formal statement and proof can be found in Appendix D.3, and see Appendix B.2 for discussions on the technical challenges.EQUATIONEQUATION)Theorem 3.3 characterizes the average-iterate convergence of the average policy π (t) (cf. ( 14)) across the agents, which depends logarithmically on the size of the action space, and independently on the size of the state space. Theorem 3.3 indicates that in the server-client setting with σ = 0, the convergence rate of FedNPG recovers the O(1/T ) rate, matching that of the centralized NPG established in [AKLM21] ; on the other end, in the decentralized setting where σ > 0, FedNPG slows down and eventually converges at the slower O(1/T 2/3 ) rate.We state the iteration complexity in Corollary 3.4.To reach1 T T -1 t=0 V ⋆ (ρ) - V π (t) (ρ) ≤ ε, the iteration complexity of FedNPG is at most O σ (1-γ) 9/2 (1-σ)ε 3/2 + σ 2 (1-σ) 4 √ N log |A| + 1 ε(1-γ) 2 .Global convergence of FedNPG with inexact policy evaluation. In practice, the policies need to be evaluated using samples collected by the agents, where the Q-functions are only estimated approximately. We are interested in gauging how the approximation error impacts the performance of FedNPG, as demonstrated in the following theorem. The formal statement, detailed discussions, and proof of this result is given in Appendix D.4. Theorem 3.5 (Global sublinear convergence of inexact FedNPG (informal)). Suppose that an estimateq π (t) n n are used in replace of Q π (t) n nin Algorithm 1. Under the assumptions of Theorem 3.3, whenT ≳ √ N log |A|σ 4 (1-σ) 4 and η = (1-γ) 9 (1-σ) 2 log |A| 32T N σ 2 1/3, we haveEQUATION)Equipped with existing sample complexity bounds on policy evaluation, e.g. using a simulator as in [LWCC23a] , this immediate leads to the sample complexity per state-action pair at each agent to find an ε-optimal policy is at mostO √ N (1 -γ) 11.5 (1 -σ)ε 3.5 (19)for sufficiently small ε.Global convergence of entropy-regularized FedNPG with exact policy evaluation. Next, we present our global convergence guarantee of entropy-regularized FedNPG with exact policy evaluation (cf. Algorithm 2). Theorem 3.6 (Global linear convergence of exact entropy-regularized FedNPG (informal)). For any γ ∈ (0, 1) and 0 < τ ≤ 1, there existsη 0 = min 1-γ τ , O (1-γ) 7 (1-σ) 2 τ σ 2 N, such that if 0 < η ≤ η 0 , then we haveEQUATIONwhere  and C 1 is some problem-dependent constant. Furthermore, the consensus error satisfiesQ (t) τ := Q π (t) τ , ρ(η) ≤ max{1 -τ η 2 , 3+σ 4 } < 1,EQUATION)The exact expressions of C 1 and η 0 are specified in Appendix D.1. Theorem 3.6 confirms that entropy-regularized FedNPG converges at a linear rate to the optimal regularized policy, which is almost independent of the size of the state-action space, highlighting the positive role of entropy regularization in federated policy optimization. When the network is fully connected, i.e. σ = 0, the iteration complexity of entropy-regularized FedNPG reduces to O 1 ητ log 1 ε , matching that of the centralized entropy-regularized NPG established in [CWC21] . When the network is less connected, one needs to be more conservative in the choice of learning rates, leading to a higher iteration complexity, as described in the following corollary. Corollary 3.7 (Iteration complexity of exact entropy-regularized FedNPG). To reach log π ⋆ τ -log π (t) ∞ ≤ ε, the iteration complexity of entropy-regularized FedNPG is at mostEQUATION)up to logarithmic factors. Especially, when η = η 0 , the best iteration complexity becomesO N σ 2 (1-γ) 7 (1-σ) 2 τ 2 + 1 1-γ log 1 τ ε .Global convergence of entropy-regularized FedNPG with inexact policy evaluation. Last but not the least, we present the informal convergence results of entropy-regularized FedNPG with inexact policy evaluation, whose formal version can be found in Appendix D.2. Theorem 3.8 (Global linear convergence of inexact entropy-regularized FedNPG (informal)). Suppose that an estimate qπ (t) n τ,n are used in replace of Q π (t)n τ,n in Algorithm 2. Under the assumptions of Theorem 3.6, we haveEQUATION)whereQ (t) τ := Q π (t) τ , ε q := max n∈[N ],t∈[T ] Q π (t) n τ,n -q π (t) n τ,n ∞ , ρ(η) ≤ max{1 -τ η 2 , 3+σ 4 } < 1, and C 1 , C 2 are problem-dependent constants. 
federated nac with function approximation and stochastic evaluation: 
 In this section, motivated by the design and analysis of FedNPG, we go beyond the tabular setting and exact policy evaluation, by proposing a federated natural actor-critic (FedNAC) method with function approximation and stochastic policy evaluation. Specifically, we consider the policy with function approximation under softmax parameterization is of the following form:EQUATIONfor all (s, a) ∈ S × A and ξ ∈ R p , where ϕ : S × A → R p is a known feature map. We assume ϕ is bounded over S × A, i.e., there exists C ϕ > 0 such that ∥ϕ(s, a)∥ 2 ≤ C ϕ holds for all (s, a) ∈ S × A.Following [AKLM21, YDG + 22], given any w ∈ R p , Q : S × A → R and probability distribution ζ ∈ ∆(S × A) over the state-action space, we define the function approximation error ℓ(w, Q, ζ) as follows:EQUATION)By searching for w that minimizes ℓ(w, Q, ζ), it approximates Q(s, a) using the feature map ϕ with respect to the distribution ζ.Algorithm design. Let us now discuss the high-level design of FedNAC, which is presented in Algorithm 3, with more details provided in Appendix C.2. At the t-th iteration (t = 0, . . . , T -1), denote the actor (concerning the policies) parameters of all agents as ξ (t) = (ξEQUATIONN ) ⊤ ∈ R N ×p , and the critic parameters of all agents as w (t) = (w(t) 1 , . . . , w (t) N ) ⊤ ∈ R N ×p (concerning the local Q-values) and h (t) = (h (t) 1 , . . . , h (t) N ) ⊤ ∈ R N ×p (concerning the global Q-values).• First, the critic parameter w (t) n is locally updated at each agent by aiming to minimize ℓ(w, Q EQUATIONQ (t)n is not directly available, it needs to be estimated from samples. Therefore, the critic update takes K steps of stochastic gradient descent with critic learning rate β, given byw k+1 = w k -β w ⊤ k ϕ(s k , a k ) -Q ξ (s k , a k ) ϕ(s k , a k ), for k = 0, . . . , K -1, where (s k , a k ) is sampled on the local policy f ξ (t) n, and Q ξ (s k , a k ) is a careful estimate of the Q-value using a trajectory with expected length 1/(1 -γ) (see Algorithm 5 in Appendix C.2 adopted from [YDG + 22, Lemma 4]), and w 0 = 0 for simplicity. The final critic is updated as w(t) n = 1 K K k=1 w k .The total sample complexity of the critic update per iteration is then on the order of K/(1 -γ).• Next, the critic parameter h (t) n for estimating the global Q-function can then be estimated by averaging with the neighbors with the Q-tracking term, given by h (t) = W h (t-1) + w (t) -w (t-1) .• Finally, the actor parameter ξ (t) n can be updated via averaging with the neighbors along with the policy gradient informed by h (t) n , given by ξ (t+1) = W ξ (t) + αh (t) , where α is the learning rate of the actor.Note that the sample complexity of FedNAC is on the order of KT /(1 -γ). An important aspect of the FedNAC method is that the policy is updated using trajectory data collected via executing the learned policy, which is closer to practice and more challenging to learn than using the generative model.Theoretical guarantees. We first state the assumptions that are needed to guarantee the convergence of Algorithm 3, which are all commonly used in the literature, e.g., [YDG + 22, AKLM21]. To begin, we require the covariance matrix of the feature map induced by the initial state-action distribution ν satisfies the following assumption to guarantee the convergence of the critic. Assumption 4.1 (PSD of the covariance matrix of the feature map). There exists µ > 0 such that E (s,a)∼ν ϕ(s, a)ϕ ⊤ (s, a) = Σ ν ≥ µI.We also need to ensure that the Q-values can be well approximated by the linear function approximation using feature map ϕ(s, a), which is captured next. Assumption 4.2 (Bounded approximation error). For each n ∈ [N ], there exists ε n approx ≥ 0 such that for all t ∈ N, it holds that E ℓ w Note that if we choose ν(s, a) > 0 for all (s, a) ∈ S × A, then Assumption 4.3 is guaranteed to hold true (see Lemma E.4 in Appendix E). We are now ready to state the convergence guarantee, whose formal version and proof could be found in Appendix E.EQUATIONTheorem 4.4 (Convergence rate of Algorithm 3 (informal)). Let ξ(0) 1 = • • • = ξ (0) N in FedNAC. Denoting ξ(t) := 1 N N n=1 ξ (t)n , and f (t) := fξ(t) as the average policy. Then under Assumption 3.1, 4.1, 4.2 and 4.3, with appropriately chosen learning rates α and β, as long as the number of actor iterations satisfiesT ≳ max σ ε 3/2 (1 -γ) 17/4 (1 -σ) 3/2 , 1 ε(1 -γ) , σ 1/4 ε 3/4 (1 -σ) 3/8 (1 -γ) 7/8 N 3/8 , σ 4 (1 -γ) 2 (1 -σ) 6and the number of critic iterations satisfiesEQUATION)In the server-client setting when σ = 0, to reach (26), it suffices to chooseT = O 1 (1-γ)ε and K = O 1 (1-γ) 6 ε 2 , leading to a total sample complexity of KT /(1 -γ) = O 1 (1-γ) 8 ε 3 per agent, and T = O 1 (1-γ)ε rounds of communication.The sample complexity matches that of (centralized) Q-NPG established in [YDG + 22] with a single agent. On the other end, in the fully decentralized setting when σ is not close to 0, FedNAC requires O 1 (1-γ) 45/4 ε 7/2 (1-σ) 3/2 samples for each agent and O 1 ε 3/2 (1-γ) 17/4 (1-σ) 3/2 rounds of communication to reach (26), for sufficiently small ε. Encouragingly, the dependency on the accuracy level ε -the dominating factor -in the sample complexity matches that of FedNPG given in (19) when assuming access to the generative model, which allows query of arbitrary state-action pairs. In contrast, FedNAC only collects on-policy samples, and therefore is much more challenging to guarantee its convergence. 
conclusions: 
 This work proposes the first provably efficient federated NPG (FedNPG) methods for solving vanilla and entropy-regularized multi-task RL problems in the fully decentralized setting. The established finite-time global convergence guarantees are almost independent of the size of the state-action space up to some logarithmic factor, and illuminate the impacts of the size and connectivity of the network. Furthermore, the proposed FedNPG methods are provably robust vis-a-vis inexactness of local policy evaluations. Last but not least, we also propose FedNAC, which can be viewed as an extension of FedNPG with function approximation and stochastic policy evaluation, and establish its finite-time sample complexity. Future directions include generalizing the framework of federated policy optimization to allow personalized policy learning in a shared environment. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: the paper aims to provide a better understanding on existing algorithms and thus poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: the paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Global convergence of NPG methods for tabular MDPs. [AKLM21] first establishes a O(1/T ) last-iterate convergence rate of the NPG method under softmax parameterization with constant step size, assuming access to exact policy evaluation. When entropy regularization is in place, [CWC21] establishes a global linear convergence to the optimal regularized policy for the entire range of admissible constant learning rates using softmax parameterization and exact policy evaluation, which is further shown to be stable in the presence of ℓ ∞ policy evaluation errors. The iteration complexity of NPG methods is nearly independent with the size of the state-action space, which is in sharp contrast to softmax policy gradient methods that may take exponential time to converge [LWCC23b, MXSS20] . [Lan23] proposed a more general framework through the lens of mirror descent for regularized RL with global linear convergence guarantees, which is further generalized in [ZCH + 23, LLZ23]. Earlier analysis of regularized MDPs can be found in [SEM20] . Besides, [Xia22] proves that vanilla NPG also achieves linear convergence when geometrically increasing learning rates are used; see also [KJVM21, BR21] . [ZLK + 22] developed an anchor-changing NPG method for multi-task RL under various optimality criteria in the centralized setting.Convergence and sample complexity results of NAC. The convergence and sample complexity of a variety of natural actor-critic methods (NACs) are extensively studied in the literature [BSGL09, WCYW19, KDRM22, AKLM21, YDG + 22]. More pertinent to our work, [AKLM21] introduced Q-NPG-a sample version of the NPG method with function approximation under softmax parameterization -and obtained a convergence rate of O(1/ √ T ). [YDG + 22] weakens some of its assumptions and improves the convergence rate to O(1/T ) and gives the O(1/ε 3 ) sample complexity using a constant actor learning rate. The FedNAC method we propose in this paper can be seen as a decentralized version of Q-NPG, and in the server-client setting where the network is fully connected, our convergence rate and sample complexity match those in [YDG + 22].Distributed and federated RL. There have been a variety of settings being set forth for distributed and federated RL. [MBM + 16, ESM + 18, ARB + 19, KSJM22, WJC23] focused on developing federated versions of RL algorithms to accelerate training, assuming all agents share the same transition kernel and reward function; in particular, [KSJM22, WJC23, WSJC24] established the provable benefits of federated learning in terms of linear speedup. More pertinent to our work, [ZRY + 23, AR21] considered the federated multi-task framework, allowing different agents having private reward functions. [ZRY + 23] proposed an empirically probabilistic algorithm that can seek an optimal policy under the server-client setting, while [AR21] developed new attack methods in the presence of adversarial agents. Recently [LWA + 23] discussed how to avoid transmitting the Hessian matrix during communication in the server-client setting where all agents share the same reward function. Different from the FRL framework, [CZGB21, CZC21, OPA + 17, KMP12, CFGW22, ZAD + 21] considered the distributed multi-agent RL setting where the agents interact with a dynamic environment through a multi-agent Markov decision process, where each agent can have their own state or action spaces.[ZAD + 21] developed a decentralized policy gradient method where different agents have different MDPs, where a special case of their setting recovers ours. However, the convergence rate developed in [ZAD + 21] has rather pessimistic dependencies with the size of the state-action space, together with other parameters, without leveraging natural policy gradients and gradient tracking techniques.Decentralized first-order optimization algorithms. Early work of consensus-based first-order optimization algorithms for the fully decentralized setting include but are not limited to [LO08, NO09, DAW11]. Gradient tracking, which leverages the idea of dynamic average consensus [ZM10] to track the gradient of the global objective function, is a popular method to improve the convergence speed [QL17, NOS17, DLS16, PN21, LCCC20].In this section, we elaborate more on our motivation and the application scenarios where federated multi-task RL becomes highly relevant.We first provide some key motivations for our federated multi-task RL setting as follows.• Efficient knowledge transfer: multi-task RL enables agents to transfer knowledge across related tasks, accelerating learning and improving performance by leveraging experiences gained from one task to another. For instance, in our healthcare example in Section 1, by learning across hospitals with varying demographics, the agent can identify treatment strategies that are effective across diverse patient populations without directly accessing sensitive patient information.• Generalization and adaptability: agents trained with multi-task RL can generalize their learned policies, adapt to new tasks, and handle diverse environments more effectively, enhancing their robustness and adaptability. In the healthcare example, an optimal treatment over different hospitals better adapts to variations in patient characteristics.• Resource optimization: training a single policy for multiple tasks optimizes resource usage compared to training separate policies for each task, making it more efficient in scenarios with limited data or computational resources. In the healthcare example, the collaborative approach enhances learning efficiency and scalability while preserving data privacy, particularly in settings where each hospital has limited access to patient information.Below we provide more application scenarios of our setting.1. To enhance ChatGPT's performance across different tasks or domains [MA22, RTR + 23], one might consult domain experts to chat and rate ChatGPT's outputs for solving different tasks, and train ChatGPT in a federated manner without exposing private data or feedback of each expert.2. Our setting is especially suitable for the multi-task problems where each agent only have partial access of the "global" task. There are a lot of such problems.• An example is the problem we consider in our experiments (see Appendix H), where we distributedly train the agents to learn a shared policy to follow a predetermined trajectory while each agent only has partial information of this trajectory. • The above problem could be seen as a simplified version of the Unmanned Aerial Vehicle (UAV) Patrol Mission, each unmanned aerial vehicle (UAV) patrols only in a specific area, and they need to collectively train a strategy utilizing information from the entire patrol range. • In the game setting, different agents aim to train a character to perform well in multiple tasks, and each agent trains on one task.Despite the promise, provably efficient algorithms for federated multi-task RL remain substantially under-explored, especially in the fully decentralized setting. Our work is the first to provide efficient algorithms with global convergence guarantees for federated multi-task RL.In this section, we stress that while our work is built upon the algorithmic ideas in the distributed learning, reinforcement learning and optimization literature, it is not a strightforward combination and the theoretical analysis is by no means trivial.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. ( 46) in [CCC + 22a], while in our corresponding analysis, a 4th-order linear system in Eq. ( 49) 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.C.1 Federated NPG (FedNPG) with entropy regularizationWe record the entropy-regularized FedNPG method in Algorithm 2 here due to space limits.Algorithm 2 Federated NPG (FedNPG) with entropy regularization1: Input: learning rate η > 0, iteration number T ∈ N + , mixing matrix W ∈ R N ×N , regulariza- tion coefficient τ > 0. 2: Initialize: π (0) , T (0) = Q (0) τ . 3: for t = 0, 1, • • • do 4:Update the policy for each (s, a) ∈ S × A:EQUATION) where z (t) (s) = a ′ ∈A exp W 1 -ητ 1-γ log π (t) (a ′ |s) + η 1-γ T (t) (s, a ′ ) . 5: Evaluate Q (t+1) τ . 6:Update the global Q-function estimate for each (s, a) ∈ S × A:T (t+1) (s, a) = W T (t) (s, a) + Q (t+1) τ (s, a) -Q (t) τ (s, a) Q-tracking . (U T ) 7: end for C.For technical convenience, we present first the analysis for entropy-regularized FedNPG and then for vanilla FedNPG.Algorithm 5 Q-Sampler(ν, π, γ, r)1: Initialize: (s 0 , a 0 ) ∼ ν, time step h, t = 0, variable X ∼ Bernoulli(γ) 2: while X = 1 do 3: Sample s h+1 ∼ P (•|s h , a h ) 4: Sample a h+1 ∼ π(•|s h+1 ) 5: h ← h + 1 6: X ∼ Bernoulli(γ) 7: end while 8: Set xc(s h , a h ) = r(s h , a h ), X ∼ Bernoulli(γ), t = h 9: while X = 1 do 10: Sample s t+1 ∼ P (•|s t , a t ) 11: Sample a t+1 ∼ π(•|s t+1 ) 12: Q π (s h , a h ) ← Q π (s h , a h ) + r(s t+1 , a t+1 ) 13: t ← t + 1 14: X ∼ Bernoulli(γ) 15: end while 16: Output: (s h , a h ) and Q π (s h , a h )To facilitate analysis, we introduce several notation below. For all t ≥ 0, we recall π (t) as the normalized geometric mean of {πEQUATIONfrom which we can easily see that for each (s, a)∈ S × A, π (t) (a|s) ∝ N n=1 π (t) n (a|s) 1 N . We denote the soft Q-functions of π (t) by Q (t) τ : Q (t) τ :=     Q π (t)τ,1. . .EQUATIONIn addition, we defineEQUATIONEQUATIONEQUATIONFor notational convenience, we also denoteEQUATION)Following [CCC + 22b], we introduce the following auxiliary sequence {ξ (t) = (ξEQUATIONEQUATIONwhere T (t) (s, a) is updated via (16). Similarly, we introduce an averaged auxiliary sequence {ξEQUATIONWe introduces four error metrics defined asEQUATIONEQUATIONEQUATIONEQUATIONwhere u (t) , v (t) ∈ R |S||A| are defined asEQUATIONEQUATION)We collect the error metrics above in a vector Ω (t) ∈ R 4 :EQUATION)With the above preparation, we are ready to state the convergence guarantee of Algorithm 2 in Theorem D.1 below, which is the formal version of Theorem 3.6. Theorem D.1. For any N ∈ N + , τ > 0, γ ∈ (0, 1), there exists η 0 > 0 which depends only on N, γ, τ, σ, |A|, such that if 0 < η ≤ η 0 and 1 -σ > 0, then the updates of Algorithm 2 satisfyEQUATION)EQUATION)where ρ(η) ≤ max 1 - τ η 2 , 3 + σ 4 < 1 .Moreover, the consensus errors satisfy:EQUATION)The dependency of η 0 on N, γ, τ, σ, |A| is made clear in Lemma D.3 that will be presented momentarily in this section. The rest of this section is dedicated to the proof of Theorem D.1. We first state a key lemma that tracks the error recursion of Algorithm 2. Lemma D.2. The following linear system holds for all t ≥ 0:EQUATIONwhere we letEQUATIONandM := 1 + γ + 2τ (1 -γ) log |A| (1 -γ) 2 • γ .In addition, it holds for all t ≥ 0 thatEQUATIONEQUATIONProof. See Appendix F.1.Let ρ(η) denote the spectral norm of A(η). As Ω (t) ≥ 0, it is immediate from (49) thatΩ (t) 2 ≤ ρ(η) t Ω (0)2 , and therefore we haveQ (t) τ -Q ⋆ τ ∞ ≤ 2γ Ω (t) ∞ ≤ 2γρ(η) t Ω (0) 2 , and log π (t) -log π ⋆ τ ∞ ≤ 2 τ Ω (t) ∞ ≤ 2 τ ρ(η) t Ω (0)2 . It remains to bound the spectral radius ρ(η), which is achieved by the following lemma. Lemma D.3 (Bounding the spectral norm of A(η)). LetEQUATION)whereEQUATIONthen we haveEQUATION)Proof. See Appendix F.2.We define the collection of inexact Q-function estimates asq (t) τ := q π (t) 1 τ,1 , • • • , q π (t) N τ,N ⊤ ,and then the update rule (U T ) should be understood asEQUATIONin the inexact setting. For notational simplicity, we define e n ∈ R asEQUATIONand let e = (e1 , • • • , e n ) ⊤ . Define q (t)τ , the approximation ofEQUATIONWith slight abuse of notation, we adapt the auxiliary sequence {ξ (t) } t=0,••• to the inexact updates asEQUATIONEQUATIONIn addition, we defineEQUATIONEQUATIONEQUATIONEQUATIONwhereEQUATIONEQUATION)We let Ω (t) beEQUATION)With the above preparation, we are ready to state the inexact convergence guarantee of Algorithm 2 in Theorem D.4 below, which is the formal version of Theorem 3.8.Theorem D.4. Suppose that qπ (t) n τ,n are used in replace of Q π (t)n τ,n in Algorithm 2. For any N ∈ N + , τ > 0, γ ∈ (0, 1), there exists η 0 > 0 which depends only on N, γ, τ, σ, |A|, such that if 0 < η ≤ η 0 and 1 -σ > 0, we haveEQUATION)EQUATIONMoreover, the consensus errors satisfy:EQUATIONwhere ρ(η) ≤ max{1 -τ η 2 , 3+σ 4 } < 1 is the same as in Theorem D.1, andC 2 := σ √ N (2(1-γ)+M √ N η)+2γ 2 +ητ (1-γ)(1-ρ(η)).From Theorem D.4, we can conclude that ifEQUATIONthen inexact entropy-regularized FedNPG could still achieve 2ε-accuracy (i.e.Q (t) τ -Q ⋆ τ ∞ ≤ 2ε) within max 2 τ η , 4 1-σ log 2γ∥Ω (0) ∥ 2 ε iterations.Remark D.5. When η = η 0 (cf. ( 54) and ( 53)) and τ ≤ 1, the RHS of (67) is of the orderO (1 -γ)τ η 0 ε γ(γ 2 + σ √ N (1 -γ)) = O (1 -γ) 8 τ 2 (1 -σ) 2 ε γ(γ 2 + σ √ N (1 -γ))(γ 2 N σ 2 + (1 -σ) 2 τ 2 (1 -γ) 6 ) ,which can be translated into a crude sample complexity bound when using fresh samples to estimate the soft Q-functions in each iteration.The rest of this section outlines the proof of Theorem D.4. We first state a key lemma that tracks the error recursion of Algorithm 2 with inexact policy evaluation, which is a modified version of Lemma D.2.Lemma D.6. The following linear system holds for all t ≥ 0:EQUATIONwhere A(η) is provided in Lemma D.2. In addition, it holds for all t ≥ 0 thatEQUATIONEQUATIONProof. See Appendix F.3.By (68), we have∀t ∈ N + : Ω (t) ≤ A(η) t Ω (0) + t s=1 A(η) t-s b(η) ,which givesEQUATIONHere, (71) follows from ∥b(η)∥ 2 ≤ ∥b(η)∥ 1 = σ √ N (2(1-γ)+M √ N η)+2γ 2 +ητ 1-γ ∥e∥ ∞ and t s=1 ρ(η) t-s ≤ 1/(1 -ρ(η)).Recall that the bound on ρ(η) has already been established in Lemma D.3. Therefore we complete the proof of Theorem D.4 by combining the above inequality with (69) and (70) in a similar fashion as before. We omit further details for conciseness.We state the formal version of Theorem 3.3 below. Theorem D.7. Suppose all π (0) n in Algorithm 1 are initialized as uniform distribution. When0 < η ≤ η 1 := (1 -σ) 2 (1 -γ) 3 8(1 + γ)γ √ N σ 2 ,we have1 T T -1 t=0 V ⋆ (ρ) -V π (t) (ρ) ≤ V ⋆ (d π ⋆ ρ ) (1 -γ)T + log |A| ηT + 8(1 + γ) 2 γ 2 N σ 2 (1 -γ) 9 (1 -σ) 2 η 2 (72)for any fixed state distribution ρ. Furthermore, we haveEQUATION)The rest of this section is dedicated to prove Theorem D.7. Similar to (37), we denote the Q-functions of π (t) by Q (t) :EQUATIONIn addition, similar to (38), we defineEQUATIONEQUATIONEQUATION)Following the same strategy in the analysis of entropy-regularized FedNPG, we introduce the auxiliary sequence {ξ (t) = (ξEQUATIONEQUATIONas well as the averaged auxiliary sequence {ξ (t) ∈ R |S||A| }:EQUATIONEQUATIONAs usual, we collect the consensus errors in a vectorΩ (t) = ( u (t) ∞ , v (t) ∞ ) ⊤, where u (t) , v (t) ∈ R |S||A| are defined as:EQUATIONEQUATION)Step 1: establishing the error recursion. The next key lemma establishes the error recursion of Algorithm 1. Lemma D.8. The updates of FedNPG satisfyEQUATIONfor all t ≥ 0, whereEQUATIONIn addition, we haveEQUATIONwhereEQUATION)Moreover, when η ≤ η 1 , we haveEQUATION)Proof. See Appendix F.4.Note that when all π (0)n in Algorithm 1 are initialized as uniform distribution, Ω (0) = 0 and (84) indicates (73) in Theorem D.7.Step 2: bounding the value functions. Let p ∈ R 2 be defined as:EQUATIONthe rationale for this choice will be made clear momentarily. We define the following Lyapunov functionEQUATIONwhich satisfiesEQUATIONHere, the second inequality follows from (82). One can verify that the second term vanishes due to the choice of p(η):EQUATIONTherefore, we conclude thatV ⋆ (ρ) -V (t) (ρ) ≤ Φ (t) (η) -Φ (t+1) (η) η + p 2 (η) (1 + γ)γN σ (1 -γ) 4.EQUATION)Step 3: simplifying the expression. We first upper bound the first term in the RHS of (89). Assuming uniform initialization for all π (0)EQUATIONE s∼d π ⋆ ρ KL π ⋆ (•|s) ∥ π (0) (•|s) ≤ log |A|.Therefore, putting together relations (86) and ( 221) we haveEQUATIONTo continue, we upper bound the second term in the RHS of (89). Note thatEQUATION)Thus we haveEQUATIONwhere the first inequality follows from (91) and the second inequality follows from the definition of η 1 and J. By (92), we deduceEQUATION) and our advertised bound (72) thus follows from plugging (90) and ( 93) into (89).We state the formal version of Theorem 3.5 below.Theorem D.9. Suppose that qπ (t) n n are used in replace of Q π (t) n n in Algorithm 1. Suppose all π (0) n in Algorithm 1 set to uniform distribution. Let 0 < η ≤ η 1 := (1 -σ) 2 (1 -γ) 3 8(1 + γ)γ √ N σ 2 ,we have1 T T -1 t=0 V ⋆ (ρ) -V π (t) (ρ) ≤ V ⋆ (d π ⋆ ρ ) (1 -γ)T + log |A| ηT + 8(1 + γ) 2 γ 2 N σ 2 (1 -γ) 9 (1 -σ) 2 η 2 + 8(1 + γ)γ (1 -γ) 5 (1 -σ) 2 √ N ση (1 + γ)γη √ N (1 -γ) 3 + 2 + 2 (1 -γ) 2 max n∈[N ],t∈[T ] Q π (t) n n -q π (t) n n ∞for any fixed state distribution ρ.Furthermore, we haveEQUATION)We next outline the proof of Theorem D.9. With slight abuse of notation, we again define e n ∈ R asEQUATIONand let e = (e 1 , • • • , e n ) ⊤ . We define the collection of inexact Q-function estimates asq (t) := q π (t) 1 1 , • • • , q π (t) N N ⊤ ,and then the update rule (16) should be understood asEQUATIONin the inexact setting. Define q (t) , the approximation of Q (t) asEQUATIONwe adapt the averaged auxiliary sequence {ξ (t) ∈ R |S||A| } to the inexact updates as follows:EQUATIONEQUATIONAs usual, we define the consensus error vector asEQUATIONEQUATION)The following lemma characterizes the dynamics of the error vector Ω (t) , perturbed by additional approximation error.Lemma D.10. The updates of inexact FedNPG satisfyEQUATION)In addition, we haveEQUATIONwhere ϕ (t) (η) is defined in (83).Moreover, when η ≤ η 1 , we haveEQUATION)Proof. See Appendix F.5. Similar to (87), we can recursively bound Φ (t) (η) (defined in (86)) asEQUATION)From the above expression we know thatEQUATION)via telescoping. Combining the above expression with (90), ( 92) and (93), we haveEQUATIONwhich establishes (94).Let π ⋆ be an optimal policy and does not need to belong to the log-linear policy class. Fix a state distribution ρ ∈ ∆(S) and a state-action distribution ν. To simplify the notation, we denoted π ⋆ ρ as d ⋆ , d f ξ(t) as d (t) , d(t) n as df ξ (t) n ν, and define d(t)n and d(t) n analogously. We also letEQUATIONand assume ϑ ρ < ∞.We also introduce a weighted KL divergence given byEQUATIONwhereEQUATIONGiven a state distribution ρ and an optimal policy π ⋆ , we define a state-action measure d⋆ asEQUATION)The following theorem guarantees that for any fixed policy π and state-action distribution ν ∈ ∆(S × A), the Q-Sampler algorithm (cf. Algorithm 5) samples (s, a) from dπ ν and gives an unbiased estimate Q π (s, a) of Q π (s, a), whose proof can be found in [YDG + 22, Lemma 4].Lemma E.1 (Lemma 4 in [YDG + 22]). Consider the output (s h , a h ) and Q π (s h , a h ) of Algorithm 5.E[h + 1] = 1 1 -γ , P (s h = s, a h = a) = dπ ν (s, a) , E Q π (s h , a h )|s h , a h = Q π (s h , a h ) .To present the convergence results of FedNAC, we further introduce the following notation, where t ∈ N represents the iteration step in FedNAC:EQUATIONEQUATIONEQUATIONEQUATION⋆,n ∈ arg minEQUATIONEQUATIONFor convenience of narration, we introduce the following bounded statistical error assumption. Assumption E.2 (Bounded statistical error). For all n ∈ [N ], there exists ε n stat > 0 such that for all t ∈ N in Algorithm 3, we haveEQUATION)When solving the regression problem with sampling based approaches, we can expect ε n stat = O(1/K), where K is the iteration number of Algorithm 4. Theorem E.3 (Convergence rate of Critic (Algorithm 4)). For Algorithm 4, let w 0 = 0 and β = 1 2C ϕ . Then under Assumption 4.1, we haveEQUATIONwhere w ⋆ ∈ arg min w ℓ w, Q ξ , dξ .The proof of Theorem E.3 is postponed to Appendix G.5.The following lemma provide a (very pessimistic) upper bound of C ν in Assumption 4.3. Lemma E.4 (Upper bound of C ν ). If ν(s, a) > 0 for all state-action pairs (s, a) ∈ S × A, then we haveC ν ≤ 1 (1 -γ) 2 ν 2 min .Proof. We only need to note thatE (s.a)∼ d(t)   h (t) (s, a) d(t) n (s, a) 2   ≤ max (s,a)∈S×A h (t) (s, a) d(t) n (s, a) ≤ 1 (1 -γ)ν min ,where the last inequality follows from (??).We give some key lemmas which will be used in our proof of Theorem 4.4. Lemma E.5 (consensus properties). For all t ∈ N, we haveEQUATIONEQUATIONProof. (115) could be obtained directly by using mathematical induction and update rule (33) (note that 1 N 1 ⊤ h (-1) = ŵ(-1) = 0, see line 2 of Algorithm 3), and (114) could be obtained by averaging both sides of (34) and using (115).Lemma E.6 (Young's inequalities). Let {x 1 , • • • , x m } be a set of m vectors in R l . Then for any ζ > 0, we haveEQUATIONEQUATION)Lemma E.7 (Lipschitzness of Q-function with function approximation). Assume that r(s, a) ∈ [0, 1], ∀(s, a) ∈ S × A. For any ξ, ξ ′ ∈ R p , we haveEQUATION)Proof. See Appendix G.6.For each iteration step t in Algorithm 3, we let ξ(tEQUATIONEQUATIONWe letEQUATIONEQUATIONand define δ (t) := V ⋆ -V (t) (ρ), whereV (t) is shorthand for V f (t). We give the following performance improvement lemma. Lemma E.8 (Performance improvement of FedNAC). Fix a state distribution ρ, then we haveEQUATIONProof. See Appendix G.7.Lemma E.9 (linear system). For any t ∈ N, we letEQUATION2 ) ⊤ . Then for any ζ > 0, we haveEQUATIONEQUATION)EQUATION)Proof. See Appendix G.8. Now we are ready to give the formal version of Theorem 4.4 and its proof.Theorem E.10 (Convergence rate of FedNAC (formal)). Let ξ(0) 1 = • • • = ξ (0)N in FedNAC (Algorithm 3), let the w (0) = 0 and the critic stepsize β = 1 2C ϕ in Algorithm 4. Then under Assumptions 3.1, 4.1, 4.2 and 4.3, when the actor stepsize satisfiesEQUATION)where L Q is defined in Lemma E.7, we haveEQUATIONMoreover, the consensus errors could be upper bounded byEQUATIONwhereEQUATION) and εstat ≤ 4 (1 -γ) 4 K ( 2p + 1)C 2 ϕ + 2pµ(1 -γ) 2 .Remark E.11 (Sample and communication complexity). When σ > 0 andα = √ µ(D (0) ⋆ ) 1/3 6144 1/3 2 1/6 C 1/3 ν (1 + ϑ ρ ) 1/3 C ϕ • (1 -γ) 11/6 (1 -σ 2 ) T 1/3 σ 2/3, it follows from Theorem E.10 thatEQUATIONConsequently, we needT ≳ σ ε 3/2 (1 -γ) 17/4 (1 -σ 2 ) 3/2 , 1 ε(1 -γ) , σ 1/4 ε 3/4 (1 -σ 2 ) 3/8 (1 -γ) 7/8 N 3/8 , σ 4 (1 -γ) 2 (1 -γ 2 ) 6 and K = O 1 (1 -γ) 6 ε 2 such that V ⋆ (ρ) -1 T T -1 t=0 E V (t) (ρ) ≲ ε + εapprox 1-γ .In Algorithm 5, each trajectory has the expected length 1/(1 -γ). Consider only the term where ε dominates, FedNAC requires O 1 (1-γ) 45/4 ε 7/2 (1-σ 2 ) 3/2 samples for each agent and O1 ε 3/2 (1-γ) 17/4 (1-σ 2 ) 3/2 rounds of com- munication.On the other end, when σ = 0, (128) becomes:EQUATIONConsequently, for any fixed α > 0, when σ = 0 or close to 0, withT = O 1 (1-γ)ε and K = O 1 (1-γ) 6 ε 2 , FedNAC requires KT /(1 -γ) = O 1 (1-γ) 8 ε 3 samples for each agent and T = O 1 (1-γ)ε rounds of communication such that V ⋆ (ρ) -1 T T -1 t=0 E V (t) (ρ) ≲ ε + εapprox 1-γ .We suppose Assumptions 3.1, E.2, 4.1, 4.2 and 4.3 holds. By Lemma E.9 and nonnegativity of each entry of C, s and Ω (t) where t ∈ N, it's easy to see thatEQUATIONwhere √ • is exerted element-wise.In addition, taking expectation on both sides of (123) and using the act thatE   2 εapprox + L 2 Q N ξ (t) -1 N ξ(t)⊤ 2 F   ≤ 2ε approx + 2L 2 Q N Ω (t) 1 ,we haveEQUATION)We define the Lyapunov function Φ (t) as follows:EQUATIONwhereEQUATIONIt's straightforward to verify that when ζ = 1-σ 2 2 , we have the entries in C (cf. (125)) satisfiesEQUATIONc 12 ≤ 3σ 2 α 2 1 -σ 2 . (138) Moreover, from α ≤ √ (1-γ)µ(1-σ 2 ) 12 √ 2σL Qwe deduceEQUATIONwhich givesEQUATIONAlso note that α ≤ (1-σ 2 ) 3 √ (1-γ)µ 768 √ 6σ 2 L Q yields (1 + 1/ζ)c 21 σα ≤ (1 - √ 1 + ζσ)(1 - √ c 22 ) 2 .which together with (140) and the fact1 - √ 1 + ζσ ≥ 1-σ 2 4indicates q 1 , q 2 > 0 and thatEQUATIONEQUATIONThus by ( 133) and (134) we haveEQUATIONwhich givesEQUATION)Summing the above inequality over t = 0, 1, • • • , T -1 and divide both sides by T , we haveEQUATION)SinceEQUATION)andEQUATION)By Theorem E.3 we know that √ εstat could be upper bounded as follows:EQUATION(128) follows from plugging (149) into (148) and noting that when ξ EQUATIONEQUATIONwhere the third inequality uses (138), (139), and the fourth inequality uses (127).Therefore, similar to (230), when α ≤ α 1 , we haveEQUATION)Combining the above inequality with (146), and (149), we obtain (129).The proof of Theorem E.3 could be found in Appendix C.5 in [YDG + 22]. We present it for completeness. To prove Theorem E.3, we need the following Theorem G.2. Theorem E.12 (Theorem 1 in [BM13] ). Consider the following assumptions:(i) The observations (a k , b k ) ∈ R p × R p are independent and identically distributed.(ii) E ∥a k ∥ 2 7 and E ∥b k ∥ 2 are finite. The covariance E a k a ⊤ k is invertible. (iii) The global minimum of g(w) = 1 2 E ⟨w, a k ⟩ 2 -2⟨w, b k ⟩ is attained at a certain w ⋆ ∈ R p . Let ∆ k = b k -⟨w ⋆ , a k ⟩a k denote the residual. We have E[∆ k ] = 0. (iv) ∃R > 0 and σ > 0 such that E ∆ k ∆ ⊤ k ≤ σ 2 E a k a ⊤ k and E ∥a k ∥ 2 a k a ⊤ k ≤ R 2 E a k a ⊤ k .Consider the stochastic gradient recursionEQUATION)In the proof of Theorem E.3 we'll show that for Algorithm 4, the assumptions in Theorem G.2 are all satisfied and thus we can use the result (267). Let H be the length of trajectory for estimating Q ξ (s, a). Then Q ξ (s, a) 2 is bounded byEQUATION)from which we deduce E Q ξ (s, a)ϕ(s, a)2 2 ≤ C 2 ϕ E Q ξ (s, a) 2 is bounded. Thus (ii) holds.Furthermore, we introduce the residualEQUATIONthen from Lemma 7 in [YDG + 22] we know thatE[∆] = 1 2 ∇ w ℓ(w, Q ξ , d π ξ ν ) = 0, which gives (iii).To verify (iv), we let R = C ϕ in Theorem G.2, then E ∥ϕ(s, a)∥ 2 2 ϕ(s, a)ϕ(s, a) ⊤ ≤ C 2 ϕ E ϕ(s, a)ϕ(s, a) ⊤ . Also note thatEQUATIONfrom which we deduceEQUATIONEQUATION)The above expression impliesEQUATIONTherefore, (iv) is verified.Thus by (267), with stepsize β = 1 2C 2 ϕ , initialization w 0 = 0 and K steps of critic updates, we haveE ℓ w out , Q ξ , dξ -ℓ w ⋆ , Q ξ , dξ ≤ 4 K (σ √ p + C ϕ ∥w ⋆ ∥ 2 ) 2 ≤ 4 K √ 2p 1 -γ C 2 ϕ µ(1 -γ) + 1 + C 2 ϕ µ(1 -γ) 2 2 ,which gives (113).F.1 Proof of Lemma D.2Before proceeding, we summarize several useful properties of the auxiliary sequences (cf. ( 40) and (41)), whose proof is postponed to Appendix G.1.Lemma F.1 (Properties of auxiliary sequences {ξ (t) } and {ξ (t) }). {ξ (t) } and {ξ (t) } have the following properties:1. ξ (t) can be viewed as an unnormalized version of π (t) , i.e.,EQUATION2. For any t ≥ 0, log ξ (t) keeps track of the average of log ξ (t) , i.e.,EQUATIONIt follows that ∀s ∈ S, t ≥ 0 :EQUATION)Lemma F.2 ([CCC + 22b, Appendix. A.2]). For any vector θ = [θ a ] a∈A ∈ R |A| , we denote by π θ ∈ R |A| the softmax transform of θ such thatEQUATION)For any θ 1 , θ 2 ∈ R |A| , we haveEQUATIONEQUATION)Step 1: bound u (t+1) (s, a) = log ξ (t+1) (s, a) -log ξ (t+1) (s, a)1 N 2 . By (40b) and (41b) we haveEQUATIONwhere the penultimate step results from the averaging property of W (property (11)). Taking maximum over (s, a) ∈ S × A establishes the bound on Ω (t+1) 1 in (49).Step 2: bound v (t+1) (s, a) = T (t+1) (s, a) -Q (t+1) τ (s, a)1 N 2 . By (U T ) we haveEQUATIONwhere the penultimate step uses property (11), and the last step is due toQ (t+1) τ (s, a) -Q (t) τ (s, a) + Q (t) τ (s, a) -Q (t+1) τ (s, a) 1 N 2 2 = Q (t+1) τ (s, a) -Q (t) τ (s, a) 2 2 + N Q (t) τ (s, a) -Q (t+1) τ (s, a) 2 -2 N n=1 Q π (t+1) n τ,n (s, a) -Q π (t) n τ,n (s, a) Q (t+1) τ (s, a) -Q (t) τ (s, a) = Q (t+1) τ (s, a) -Q (t) τ (s, a) 2 2 -N Q (t) τ (s, a) -Q (t+1) τ (s, a) 2 ≤ Q (t+1) τ (s, a) -Q (t) τ (s, a) 2 2 .Step 3: boundEQUATION∞ . We decompose the term of interest asQ ⋆ τ -τ log ξ (t+1) = Q ⋆ τ -τ α log ξ (t) -(1 -α) Q (t) τ = α(Q ⋆ τ -τ log ξ (t) ) + (1 -α)(Q ⋆ τ -Q (t) τ ) + (1 -α)(Q (t) τ -Q (t) τ ),which givesEQUATIONThe last step is due to log ξ(t)n (s, a) -log ξ (t) (s, a) ≤ u (t) (s, a), while the penultimate step results from writingπ (t) (•|s) = softmax log ξ (t) (s, •) , π (t) n (•|s) = softmax log ξ (t) n (s, •) ,and applying the following lemma. Lemma F.3 (Lipschitz constant of soft Q-function). Assume that r(s, a) ∈ [0, 1], ∀(s, a) ∈ S × A and τ ≥ 0. For any θ, θ ′ ∈ R |S||A| , we haveEQUATIONPlugging (169) into (168) givesEQUATION)Step 4: boundQ (t+1) τ (s, a) -Q (t) τ (s, a) 2 .Let w (t) : S × A → R be defined as∀(s, a) ∈ S ×A : w (t) (s, a) := log ξ (t+1) (s, a)-log ξ (t) (s, a)-(1-α)V ⋆ τ (s)1 N /τ 2 . (172)Again, we treat w (t) as vectors in R |S||A| whenever it is clear from context. For any (s, a) ∈ S × A and n ∈ [N ], by Lemma F.3 it follows thatEQUATIONand consequentlyEQUATION)It boils down to control w (t) ∞ . To do so, we first note that for each (s, a) ∈ S × A, we havew (t) (s, a) = W α log ξ (t) (s, a) + (1 -α)T (t) (s, a)/τ -log ξ (t) (s, a) -(1 -α)V ⋆ τ (s)1 N /τ 2 (a) = α(W -I N ) log ξ (t) (s, a) -log ξ (t) (s, a)1 N + (1 -α) W T (t) (s, a)/τ -log ξ (t) (s, a) -V ⋆ τ (s)1 N /τ 2 (b) ≤ 2α log ξ (t) (s, a) -log ξ (t) (s, a)1 N 2 + 1 -α τ W T (t) (s, a) -τ log ξ (t) (s, a) -V ⋆ τ (s)1 N 2 (175)where (a) is due to the doubly stochasticity property of W and (b) is from the fact ∥W -I N ∥ 2 ≤ 2.We further bound the second term as follows:EQUATION)Here, the first step results from the following relation established in [NNXS17] :EQUATIONwhich also leads tolog π (t) -log π ⋆ τ ∞ ≤ 2 τ Q ⋆ τ -τ log ξ (t) ∞ (178)by Lemma F.2. For the remaining terms in (176), we haveEQUATIONandEQUATIONwhere the first inequality again results from Lemma F.2. Plugging (178), ( 179), ( 180) into (176) and using the definition of u (t) , v (t) , we arrive atw (t) (s, a) ≤ 2α + (1 -α) • √ 2N u (t) ∞ + 1 -α τ v (t) ∞ + 1 -α τ • √ N Q (t) τ -Q (t) τ ∞ + Q (t) τ -Q ⋆ τ ∞ + 1 -α τ • 2 √ N Q ⋆ τ -τ log ξ (t)∞ . Using previous display, we can write (174) asEQUATIONCombining (167) with the above expression (181), we getEQUATION)Step 5: boundQ (t+1) τ -Q ⋆ τ ∞ .For any state-action pair (s, a) ∈ S × A, we observe thatEQUATIONwhere the first step invokes the definition of Q τ (cf. (6a)), and the second step is due to the following expression of V ⋆ τ established in [NNXS17] :EQUATION)To continue, note that by ( 162) and (41b) we haveEQUATION)Plugging ( 185) into ( 183) and ( 181) establishes the bounds onEQUATIONfor any (s, a) ∈ S × A. In view of property (164), the first term on the right-hand side of (186) can be bounded byτ log exp Q ⋆ τ (s ′ , •) τ 1 -τ log ξ (t+1) (s ′ , •) 1 ≤ Q ⋆ τ -τ log ξ (t+1) ∞ .Plugging the above expression into (186), we have0 ≤ Q ⋆ τ (s, a)-Q (t+1) τ (s, a) ≤ γ Q ⋆ τ -τ log ξ (t+1) ∞ -γ min s,a Q (t+1) τ (s, a) -τ log ξ (t+1) (s, a) ,which givesQ ⋆ τ -Q (t+1) τ ∞ ≤ γ Q ⋆ τ -τ log ξ (t+1) ∞ +γ max 0, -min s,a Q (t+1) τ (s, a) -τ log ξ (t+1) (s, a) .(187) Plugging the above inequality into (171) and (182) establishes the bounds on Ω (t+1) 3and Ω (t+1) 2 in (49), respectively. Step 6: bound -min s,a Q (t+1) τ (s, a) -τ log ξ (t+1) (s, a) . We need the following lemma which is adapted from Lemma 1 in [CCC + 22b]: Lemma F.4 (Performance improvement of FedNPG with entropy regularization). Suppose 0 < η ≤ (1 -γ)/τ . For any state-action pair (s 0 , a 0 ) ∈ S × A, one hasEQUATIONEQUATION)Proof. See Appendix G.3.Using (189), we haveEQUATIONwhich givesEQUATION)This establishes the bounds on Ω (t+1) 4in (49).Let f (λ) denote the characteristic function. In view of some direct calculations, we obtainEQUATION)where, for the notation simplicity, we letEQUATIONEQUATIONEQUATION)Note that among all these new notation we introduce, S, d are dependent of η. To decouple the dependence, we give their upper bounds as followsEQUATIONEQUATIONwhere (194) follows from η ≤ (1 -γ)/τ , and (195) uses the fact that α ≤ 1 and 1 -α ≤ 1.LetEQUATION)Since A(ρ) is a nonnegative matrix, by Perron-Frobenius Theorem (see [HJ12] , Theorem 8.3.1), ρ(η) is an eigenvalue of A(ρ). So to verify (55), it suffices to show that f (λ) > 0 for any λ ∈ [λ ⋆ , ∞).To do so, in the following we first show that f (λ ⋆ ) > 0, and then we prove that f is non-decreasing on [λ ⋆ , ∞).• Showing f (λ ⋆ ) > 0. We first lower bound f 0 (λ ⋆ ). Since λ ⋆ ≥ 3+σ 4 , we haveEQUATIONand from λ ⋆ ≥ 1+(1-α)γ+α 2 we deduceEQUATION)which givesEQUATION)Combining ( 200), ( 197), (198), we have thatEQUATION)To continue, we upper bound f 1 (λ ⋆ ) as follows.EQUATIONPlugging ( 201),( 202) into (192) and using (199), we havef (λ ⋆ ) > 1 -α 2 f 0 (λ ⋆ ) - ησ 2 1 -γ f 1 (λ ⋆ ) - τ η 3 γ (1 -γ) 2 • 2cdM σ 2 ≥ τ η 2 2(1 -γ) 1 -σ 8 τ 1 -σ + (1 -α)(σ - 1 2 ) - ησ 2 1 -γ τ S + 2 + γ 1 -γ M cη + 5γcdM = τ η 2 2(1 -γ) (1 -σ) 2 8 τ - η 1 -γ Sτ σ 2 + 2 + γ 1 -γ M cσ 2 τ η + τ 2 1 2 -σ 2 • 1 -σ 8 + 5γcdM σ 2 ≥ τ η 2 2(1 -γ) (1 -σ) 2 8 τ - η 1 -γ S 0 τ σ 2 + (1 -σ) 2 16 τ 2 + (2 + γ + 5γd 0 ) cM σ 2 ≥ 0 ,where the penultimate inequality uses 1 2 -σ ≤ 1-σ 2 , and the last inequality follows from the definition of ζ (cf. ( 53)).• Proving f is non-decreasing on [λ ⋆ , ∞). Note that η ≤ ζ ≤ (1 -γ)(1 -σ) 2 8S 0 σ 2 , thus we have ∀λ ≥ λ ⋆ : f ′ 0 (λ) - ησ 2 1 -γ f ′ 1 (λ) ≥ (λ -σα)(λ -σ(1 + σbη)) - η 1 -γ Sσ 2 ≥ 0 , which indicates that f 0 -f 1 is non-decreasing on [λ ⋆ , ∞). Therefore, f is non-decreasing on [λ ⋆ , ∞).Note that bounding u (t+1) (s, a) is identical to the proof in Appendix F.1 and shall be omitted. The rest of the proof also follows closely that of Lemma D.2, and we only highlight the differences due to approximation error for simplicity.Step 2: bound v (t+1) (s, a) = T (t+1) (s, a) -q(t+1) τ (s, a)1 N 2 . Let q (t) τ := q π (t) 1 τ,1 , • • • , q π (t) N τ,N ⊤ .EQUATION)Step 3: boundQ ⋆ τ -τ log ξ (t+1)∞ . In the context of inexact updates, (168) writesQ ⋆ τ -τ log ξ (t+1) ∞ ≤ α Q ⋆ τ -τ log ξ (t) ∞ + (1 -α) Q ⋆ τ -Q (t) τ ∞ + (1 -α) Q (t) τ -q (t) τ ∞ .For the last term, following a similar argument in (169) leads toQ (t) τ -q (t) τ ∞ = 1 N N n=1 Q π (t) n τ,n - 1 N N n=1 Q π (t) τ,n ∞ + 1 N N n=1 Q π (t) n τ,n q π (t) n τ,n ∞ ≤ M • 1 N N n=1 log ξ (t) n -log ξ (t) ∞ + 1 N N n=1 e n ≤ M u (t) ∞ + ∥e∥ ∞ .Combining the above two inequalities, we obtainEQUATION)Step 4: boundQ (t+1) τ (s, a) -Q (t)τ (s, a). We remark that the bound established in (174) still holds in the inexact setting, with the same definition for w (t) :EQUATION)To deal with the approximation error, we rewrite (176) asEQUATION)where the second term can be upper-bounded byEQUATIONCombining ( 207), ( 206) and the established bounds in ( 175), ( 178), (180) leads tow (t) (s, a) ≤ 2α + (1 -α) • √ 2N u (t) ∞ + 1 -α τ v (t) ∞ + 1 -α τ • √ N Q (t) τ -Q (t) τ ∞ + Q (t) τ -Q ⋆ τ ∞ + ∥e∥ ∞ + 1 -α τ • 2 √ N Q ⋆ τ -τ log ξ (t) ∞ .Combining the above inequality with ( 205) and (203) givesEQUATION)Step 5: boundQ (t+1) τ -Q ⋆ τ ∞. It is straightforward to verify that (187) applies to the inexact updates as well:Q ⋆ τ -Q (t+1) τ ∞ ≤ γ Q ⋆ τ -τ log ξ (t+1) ∞ + γ -min s,a Q (t+1) τ (s, a) -τ log ξ (t+1) (s, a) .Plugging the above inequality into (204) and ( 208) establishes the bounds on Ω (t+1) 3and Ω (t+1) 2 in (68), respectively.Step 6: bound -min s,a Q(s, a)-τ log ξ (t+1) (s, a) . We obtain the following lemma by interpreting the approximation error e as part of the consensus errorQ (t) τ -Q (t) τ ∞in Lemma F.4. Lemma F.5 (inexact version of Lemma F.4). Suppose 0 < η ≤ (1 -γ)/τ . For any state-action pair (s 0 , a 0 ) ∈ S × A, one hasEQUATIONEQUATIONUsing (210), we haveEQUATIONEQUATIONF.4 Proof of Lemma D.8Step 1: bound u (t+1) (s, a) = log ξ (t+1) (s, a) -log ξ (t+1) (s, a)1 N. Following the same strategy in establishing (166), we haveEQUATIONor equivalentlyEQUATIONStep 2: bound v (t+1) (s, a) = T (t+1) (s, a) -Q (t+1) (s, a)1 N 2 . In the same vein of establishing (167), we haveEQUATIONThe term Q (t+1) (s, a) -Q (t) (s, a) 2 can be bounded in a similar way in (174):EQUATIONwhere the coefficient (1+γ)γ (1-γ) 2 comes from M in Lemma F.3 when τ = 0, and wEQUATIONIt remains to bound w (t) 0∞ . Towards this end, we rewrite (175) as wEQUATIONNote that it holds for all (s, a) ∈ S × A:Q (t) (s, a) -V ⋆ (s) ≤ 1 1 -γ since Q (t) (s, a) and V ⋆ (s) are both in [0, 1/(1 -γ)]. This along with (218) givesw (t) 0 (s, a) ≤ 2 u (t) ∞ + η 1 -γ v (t) ∞ + η √ N (1 -γ) 2 .Combining the above inequality with (216) and (215), we arrive atEQUATIONStep 3: establish the descent equation. The following lemma characterizes the improvement in ϕ (t) (η) for every iteration of Algorithm 1, with the proof postponed to Appendix G.4. Lemma F.6 (Performance improvement of exact FedNPG). For all starting state distribution ρ ∈ ∆(S), we have the iterates of FedNPG satisfyEQUATIONwhereEQUATIONIt remains to control the term Q(t) -Q (t)∞ . Similar to (169), for all t ≥ 0, we haveEQUATIONwhere (a) invokes Lemma F.3 with τ = 0 and (b) stems from the definition of u (t) . This along with (220) givesϕ (t+1) (η) ≤ ϕ (t) (η) + 2(1 + γ)γ (1 -γ) 4 η u (t) ∞ -η V ⋆ (ρ) -V (t) (ρ) .Step 4: bound the consensus error. To bound the consensus error log π(t) n -log π(t) ∞ for all n ∈ [N ],we first upper bound the spectral norm of B(η) which we denote as ρ(B(η)). Since B(η) is a nonnegative matrix, by Perron-Frobenius Theorem, ρ(B(η)) is an eigenvalue of B(η). So we only need to upper bound the eigenvalue of ρ(B(η)).The characteristic polynomial of B(η) isf (λ) =(λ -σ) λ -σ 1 + (1 + γ)γ √ N η (1 -γ) 3 σ - ηJ 1 -γ σ 2 =λ 2 -2 + (1 + γ)γ √ N η (1 -γ) 3 σ σλ + 1 + (1 + γ)γ √ N η (1 -γ) 3 σ - ηJ 1 -γ σ 2 .which givesEQUATION)Note that when η ≤ η 1 , we have (recall that J = 2(1+γ)γ(1-γ) 2 √ N ):(1 + γ)γ √ N η (1 -γ) 3 σ ≤ (1 -σ) 2 8 , and ηJ 1 -γ ≤ (1 -σ) 2 4σ .Plugging the above two expressions into (223) yieldsρ(B(η)) ≤σ 1 + (1 -σ) 2 /8 + (1 -σ)/(2 √ σ) ≤σ (1 + (1 -σ)/(8σ) + (1 -σ)/(2σ)) = 3 8 σ + 5 8 < 1 .Therefore, when η ≤ η 1 , we haveEQUATIONCombining the above inequality with the following fact:∀n ∈ [N ] : log π (t) n -log π(t) ∞ ≤ 2 log ξ (t) n -log ξ(t) ∞ ≤ Ω (t) 1 ≤ Ω (t) 2where the first inequality uses (165), we obtain (84).The bound on u (t+1) (s, a) is already established in Step 1 in Appendix F.1 and shall be omitted. As usual we only highlight the key differences with the proof of Lemma D.8 due to approximation error.Step1: bound v (t+1) (s, a) = T (t+1) (s, a) -q (t+1) (s, a)1 N 2 . Let q (t) := q π (t) 1 1 , • • • , q π (t) N N ⊤. From (96), we haveEQUATION) Note that (216) still holds for inexact FedNPG:EQUATION0 is defined in (217). We rewrite (218), the bound on w (t) 0 (s, a), as wEQUATION)With the following bound∀(s, a) ∈ S × A : q (t) (s, a) -V ⋆ (s) ≤ q (t) -Q (t) ∞ + 1 1 -γ in mind, we write (218) as w (t) 0 (s, a) ≤ 2 u (t) ∞ + ησ 1 -γ v (t) ∞ + η 1 -γ • √ N q (t) -q (t) ∞ + 1 1 -γ .Putting all pieces together, we obtainEQUATIONStep 2: establish the descent equation. Note that Lemma F.6 directly applies by replacing Q (t) with q (t) :ϕ (t+1) (η) ≤ ϕ (t) (η) + 2η (1 -γ) 2 q (t) -Q (t) ∞ -η V ⋆ (ρ) -V (t) (ρ) .To bound the middle term, for all t ≥ 0, we haveEQUATIONHence, (102) is established by combining the above two inequalities.Step 4: bound the consensus error. Similar as ( 224), here we haveEQUATIONwhich indicates 103.G.1 Proof of Lemma F.1The first claim is easily verified as log ξ(t) n (s, •) always deviate from log π (t)n (•|s) by a global constant shift, as long as it holds for t = 0:log ξ (t+1) n (s, •) = N n ′ =1 [W ] n,n ′ α log ξ (t) n ′ (s, •) + (1 -α)T (t) n (s, •)/τ = α N n ′ =1 [W ] n,n ′ α log π (t) n ′ (s, •) + c (t) n ′ (s)1 |A| + (1 -α)T (t) n (s, •)/τ = α N n ′ =1 [W ] n,n ′ α log π (t) n ′ (s, •) + (1 -α)T (t) n (s, •)/τ -log z (t) n (s)1 |A| + c (t+1) n (s)1 |A| = log π (t+1) n (•|s) + c (t+1) n (s)1 |A| , where z (t)n is the normalization term (cf. line 5, Algorithm 2) and {c(t)n (s)} are some constants. To prove the second claim, ∀t ≥ 0, ∀(s, a) ∈ S × A, letEQUATIONTaking inner product with 1 N 1 for both sides of (U T ) and using the double stochasticity property of W , we getEQUATIONBy the choice of T (0) (line 2 of Algorithm 2), we have T(0) = Q (0)τ and hence by induction ∀t ≥ 0 :T (t) = Q (t) τ . (233) This implies log ξ (t+1) (s, a) -α log ξ (t) (s, a) = (1 -α) Q (t) τ (s, a)/τ = (1 -α)T (t) (s, a)/τ = 1 N 1 ⊤ log ξ (t+1) (s, a) -α 1 N 1 ⊤ log ξ (t) (s, a).Therefore, to prove (161), it suffices to verify the claim for t = 0:1 N 1 ⊤ log ξ (0) (s, a) = log ∥exp (Q ⋆ τ (s, •)/τ )∥ 1 + 1 N 1 ⊤ log π (0) (a|s) -log exp 1 N N n=1 log π (0) n (•|s) 1 = log ∥exp (Q ⋆ τ (s, •)/τ )∥ 1 + log π (0) (a|s) = log ξ (0) (s, a) .By taking logarithm over both sides of the definition of π (t+1) (cf. ( 27)), we getEQUATIONfor some constant z (t) (s), which deviate from the update rule of log ξ (t+1) by a global constant shift and hence verifies (162).For notational simplicity, we letQ θ ′ τ and Q θ τ denote Q π θ ′ τand Q π θ τ , respectively. From (6a) we immediately know that to boundQ θ ′ τ -Q θ τ ∞ , it suffices to control V θ τ (s) -V θ ′ τ (s)for each s ∈ S. By (4) we haveEQUATIONso in the following we bound both terms in the RHS of (235).Step 1: bounding H(s, π θ ) -H(s, π θ ′ ) . We first bound H(s, π θ ) -H(s, π θ ′ ) using the idea in the proof of Lemma 14 in [MXSS20] . We letEQUATIONand let h (t) ∈ R |S| be ∀s ∈ S :EQUATIONNote that h (t) ∞ ≤ log |A|. We also denote H (t) : S → R |A|×|A| by: ∀s ∈ S :EQUATIONthen we have ∀s ∈ S :EQUATIONwhere ∂h (t) (s) ∂θ (t) (•|s) stands for ∂h (t) (s) ∂θ(•|s) θ=θ (t) . The first term in (239) is further upper bounded asH (t) (s) log π θ (t) (•|s) 1 = a∈A π θ (t) (a|s) log π θ (t) (a|s) -π θ (t) (•|s) ⊤ log π θ (t) (•|s) ≤ a∈A π θ (t) (a|s) |log π θ (t) (a|s)| + π θ (t) (•|s) ⊤ log π θ (t) (•|s) = -2 a∈A π θ (t) (a, s) log π θ (t) (a|s) ≤ 2 log |A| .By Lagrange mean value theorem, there exists t ∈ (0, 1) such that|h 1 (s) -h 0 (s)| = dh (t) (s) dt ≤ 2 log |A| ∥θ ′ (s, •) -θ(s, •)∥ ∞ ,where the inequality follows from (239) and the above inequality. Combining (5) with the above inequality, we arrive atEQUATION)Step 2: bounding V θ (s) -V θ ′ (s) . Similar to the previous proof, we bound V θ (s) -V θ ′ (s) by bounding dV θ (t) dt (s) . By Bellman's consistency equation, the value function of π θ (t) is given byV θ (t) (s) = a∈A π θ (t) (a|s)r(s, a) + γ a π θα (a|s) s ′ ∈S P(s ′ |s, a)V θ (t) (s ′ ) ,which can be represented in a matrix-vector form asEQUATIONwhere e s ∈ R |S| is a one-hot vector whose s-th entry is 1, EQUATIONWe now calculate each term respectively.• For the first term, it follows thatEQUATION)where the second and fourth lines use the fact ∥M t ∥ 1 ≤ 1/(1 -γ) [LWCC23a, Lemma 10], and the last line follow from We defer the proof of (246) to the end of proof.∥r t ∥ ∞ = max• For the second term, it follows thatEQUATION)where the first inequality follows again from ∥M t ∥ 1 ≤ 1/(1 -γ), and the second inequality follows fromEQUATIONPlugging the above two inequalities into (245) and using Lagrange mean value theorem, we haveEQUATION)Step 3: sum up. Combining (250), ( 240) and (235), we haveEQUATIONCombining ( 251) and (6a), (170) immediately follows.Proof of (246). For any vector x ∈ R |S| , we have dPEQUATIONas desired, where the last line follows from the following fact:a∈A dπ θ (t) (a|s) dt = a∈A ∂π θ (t) (a|s) ∂θ (t) , θ ′ -θ = a∈A ∂π θ (t) (a|s) ∂θ (t) (s, •) , θ ′ (s, •) -θ(s, •) = a∈A π θ (t) (a|s) (θ ′ (s, a) -θ(s, a)) -π θ (t) (•|s) ⊤ (θ ′ (s, •) -θ(s, •)) ≤ max a |θ ′ (s, a) -θ(s, a)| + π θ (t) (•|s) ⊤ (θ ′ (s, •) -θ(s, •)) ≤ 2 ∥θ ′ -θ∥ ∞ .To simplify the notation, we denoteEQUATIONWe first rearrange the terms of (234) and obtain-τ log π (t) (a|s)+ Q (t) τ (s, a) + δ (t) (s, a) = 1 -γ η log π (t+1) (a|s) -log π (t) (a|s) + 1 -γ η z (t) (s) .(254) This in turn allows us to express V (t) τ (s 0 ) for any s 0 ∈ S as followsEQUATIONwhere the first identity makes use of (6b), the second line follows from (254). Invoking (6b) again to rewrite the z(s 0 ) appearing in the first term of (255), we reachV (t) τ (s 0 ) = E a0∼π (t+1) (•|s0) -τ log π (t+1) (a 0 |s 0 ) + Q (t) τ (s 0 , a 0 ) + τ - 1 -γ η log π (t+1) (a 0 |s 0 ) -log π (t) (a|s) - 1 -γ η KL π (t) (•|s 0 ) ∥ π (t+1) (•|s 0 ) - E a0∼π (t) (•|s0) δ (t) (s 0 , a 0 ) + E a0∼π (t+1) (•|s0) δ (t) (s 0 , a 0 ) = E a 0 ∼π (t+1) (•|s 0 ), s 1 ∼P (•|s 0 ,a 0 )-τ log π (t+1) (a 0 |s 0 ) + r(s 0 , a 0 ) + γVEQUATION)Note that for any (s 0 , a 0 ) ∈ S × A, we haveEQUATIONTo finish up, applying (256) recursively to expand V (t) τ (s i ), i ≥ 1 and making use of (257), we arrive atEQUATIONwhere the third line follows since V (t+1) τ can be viewed as the value function of π (t+1) with adjusted rewards r (t+1) (s, a) := r(s, a) -τ log π (t+1) (s|a). And (188) follows immediately from the above inequality (258). By (6a) we can easily see that (189) is a consequence of (188).We first introduce the famous performance difference lemma which will be used in our proof.Lemma G.1 (Performance difference lemma). For any policy π, π ′ ∈ ∆(A) S and ρ ∈ ∆(S), we haveEQUATIONEQUATION) Proof. See Lemma 3 in [YDG + 22].For all t ≥ 0, we define the advantage function A (t) as:EQUATIONThen for Alg. 1, the update rule of π (Eq. ( 234)) can be written asEQUATIONwhere δ (t) is defined in (253) andEQUATIONwhere the first inequality follows by Jensen's inequality on the concave function log x and the last equality uses a ′ ∈A π (t) (a ′ |s)A (t) (s, a ′ ) = 0.For all starting state distribution µ, we use d (t+1) as shorthand for d π (t+1) µ , the performance difference lemma (Lemma G.1) implies:V (t+1) (µ) -V (t) (µ) = 1 1 -γ E s∼d (t+1) a∈A π (t+1) (a|s) A (t) (s, a) + δ (t) (s, a) - 1 1 -γ E s∼d (t+1) E a∼π (t+1) (•|s) δ (t) (s, a) = 1 η E s∼d (t+1) a∈A π (t+1) (a|s) log π (t+1) (a|s) z (t) (s) π (t) (a|s) - 1 1 -γ E s∼d (t+1) E a∼π (t+1) (•|s) δ (t) (s, a) = 1 η E s∼d (t+1) KL π (t+1) (•|s) ∥ π (t) (•|s) + 1 η E s∼d (t+1) log z (t) (s) - 1 1 -γ E s∼d (t+1) E a∼π (t+1) (•|s) δ (t) (s, a) ≥ 1 η E s∼d (t+1) log z (t) (s) + η 1 -γ δ (t) ∞ - 2 1 -γ δ (t) ∞ ,from which we can see thatEQUATIONwhere we use (263), and thatEQUATIONwhich follows from d (t+1) = d π (t+1) µ ≥ (1 -γ)µ and the fact that log z (t) (s) + η 1-γ δ (t) ∞ ≥ 0 (by ( 263)).For any fixed ρ, we use d ⋆ as shorthand for d π ⋆ ρ . By the performance difference lemma (Lemma G.1),EQUATIONwhere we use (262) in the second equality.By applying (265) with µ = d ⋆ as the initial state distribution, we have1 η E s∼µ log z (t) (s) + η 1 -γ δ (t) ∞ ≤ 1 1 -γ V (t+1) (d ⋆ ) -V (t) (d ⋆ ) + 2 (1 -γ) 2 δ (t) ∞ .Plugging the above equation into (266), we obtainV ⋆ (ρ) -V (t) (ρ) ≤ 1 η E s∼d ⋆ KL π ⋆ (•|s) ∥ π (t) (•|s) -KL π ⋆ (•|s) ∥ π (t+1) (•|s) + 1 1 -γ V (t+1) (d ⋆ ) -V (t) (d ⋆ ) + 2 (1 -γ) 2 δ (t) ∞ ,which gives Lemma F.6.The proof of Theorem E.3 could be found in Appendix C.5 in [YDG + 22]. We present it for completeness. To prove Theorem E.3, we need the following Theorem G.2.Theorem G.2 (Theorem 1 in [BM13] ). Consider the following assaumptions:(i) The observations (a k , b k ) ∈ R p × R p are independent and identically distributed.(ii) E ∥a k ∥ 2 8 and E ∥b k ∥ 2 are finite. The covariance E a k a ⊤ k is invertible.(iii) The global minimum of g(w)EQUATION)In the proof of Theorem E.3 we'll show that for Algorithm 4, the assumptions in Theorem G.2 are all satisfied and thus we can use the result (267). EQUATIONfrom which we deduce E Q ξ (s, a)ϕ(s, a)2 2 ≤ C 2 ϕ E Q ξ (s, a) 2 is bounded. Thus (ii) holds.Furthermore, we introduce the residualEQUATIONthen from [YDG + 22, Lemma 7] we know thatE[∆] = 1 2 ∇ w ℓ(w ⋆ , Q ξ , d π ξ ν ) = 0, which gives (iii).To verify (iv), we let R = C ϕ in Theorem G.2, then E ∥ϕ(s, a)∥ from which we deduceEQUATION)The above expression impliesEQUATIONTherefore, (iv) is verified.Thus by (267), with stepsize β = 1 2C 2 ϕ , initialization w 0 = 0 and K steps of critic updates, we haveE ℓ w out , Q ξ , dξ -ℓ w ⋆ , Q ξ , dξ ≤ 4 K (σ √ p + C ϕ ∥w ⋆ ∥ 2 ) 2 ≤ 4 K √ 2p 1 -γ C 2 ϕ µ(1 -γ) + 1 + C 2 ϕ µ(1 -γ) 2 2 ,which gives (113).Proof of Lemma E.7. For notational simplicity we let V ξ , V ξ ′ denote V f ξ , V f ξ ′ , resp. Same as in Lemma F.3, We define ξ (t) = ξ + t(ξ ′ -ξ) and define P t , M t , r t by replacing π ξ (t) with f ξ (t) in (243),( 242) and (244), respectively. DefineEQUATIONAnalogous to (252), we havedP t dt x ∞ ≤ max s a∈A s ′ ∈S P(s ′ |s, a) dπ ξ (t) (a|s) dt ∥x∥ ∞ = max s a∈A dπ ξ (t) (a|s) dt ∥x∥ ∞ ≤ 2C ϕ ∥ξ ′ -ξ∥ 2 ∥x∥ ∞where the last line follows is due toa∈A df ξ (t) (a|s) dt = a∈A ∂f ξ (t) (a|s) ∂ξ (t) , ξ ′ -ξ = a∈A f ξ (t) (a|s) ⟨ φξ (s, a), ξ ′ -ξ⟩ ≤ a∈A f ξ (t) (a|s) φξ (s, a) 2 ∥ξ ′ -ξ∥ 2 ≤ 2C ϕ ∥ξ ′ -ξ∥ ∞ .Same as (245) in Lemma F.3, we haveEQUATIONAnd similar to (249), we deducedr t dt ∞ = max s∈S dr t (s) dt = max s∈S ∂f ξ (t) (•|s) ⊤ r(s, •) ∂ξ (t) , ξ ′ -ξ = ⟨ a∈A f ξ (a|s) φξ (s, a)r(s, a), ξ ′ -ξ⟩ = a∈A f ξ (a|s)r(s, a) ⟨ φξ (s, a), ξ ′ -ξ⟩ ≤ 2C ϕ ∥ξ ′ -ξ∥ 2 ,which givesEQUATIONFollowing the same steps in (247), we deduceEQUATION)Combining the above two expressions (277) and ( 278) with (276), we deduceEQUATIONwhich implies EQUATIONEQUATIONProof of Lemma E.8. By the update rule (114) and the parameterization (24) we know know that∀(s, a) ∈ S × A : f (t+1) (a|s) = 1 Z (t) (s) f (t) (a|s) exp αϕ ⊤ (s, a) ŵ(t) ,where Z (t) (s) is a normalization coefficient to ensure a∈A f (t+1) (s, a) = 1 for each s ∈ S. Note that the above π (t+1) could also be obtained by a mirror descent update:EQUATIONwhere Φ(s) ∈ R |A|×p is a matrix with rows ϕ ⊤ (s, a) ∈ R p for a ∈ A, and D(•, •) denotes the KL divergence defined in (109).We apply the three-point descent lemma-Lemma G.3 with C = ∆(A), f = -α⟨Φ(s) ŵ(t) , •⟩ and h : ∆(A) → R is the negative entropy with h(q) = a∈A q(a) log q(a) and deduce that for any q ∈ ∆(A), we have-α⟨Φ(s) ŵ(t) , f (t+1) (•|s)⟩+D f (t+1) (•|s), f (t) (•|s) ≤ -α⟨Φ(s) ŵ(t) , q⟩+D q, f (t) (•|s) -D q, f (t+1) (•|s) .Rearranging terms and dividing both sides by -α, we obtainEQUATIONLet q = f (t) (•|s) and π ⋆ (•|s),resp., we have the following two inequalities:EQUATIONEQUATIONTaking expectation w.r.t. distribution d ⋆ on both sides of (285), we arrive atEQUATIONTo simplify the notation we let Q(t) andV (t) denote Q f (t) and V f (t), respectively. Note that the first expectation in the above expression (286) could be upper bounded as follows:EQUATIONwhere the first inequality uses (??) and the definition of ϑ ρ (107) and the last line follows from (260) in Lemma G.1. We separate the second term of the last line into four terms as follows:EQUATIONApplying again Lemma G.1, we deduce the equivalent form of the second expectation in (286) as follows:EQUATIONwhere the second term of the last line could be decomposed into the following terms:EQUATIONPlugging (288), (290) into (287) and (289), resp., and making use of (286), we haveϑ ρ (1 -γ) V (t+1) (ρ) -V (t) (ρ) + (1 -γ) V (t) (ρ) -V π ⋆ (ρ) + ϑ ρ s∈S a∈A d f (t+1) (s) f (t+1) (a|s)ϕ ⊤ (s, a)( ŵ(t) - ŵ(t) ⋆ ) (I) + s∈S a∈A d f (t+1) (s) f (t+1) (a|s) ϕ ⊤ (s, a) ŵ(t) ⋆ -Q(t) (s, a) (II) + s∈S a∈A d f (t+1) (s) f (t) (a|s)ϕ ⊤ (s, a)( ŵ(t) ⋆ -ŵ(t) ) (III) + s∈S a∈A d f (t+1) (s) f (t) (a|s) Q(t) (s, a) -ϕ ⊤ (s, a) ŵ(t) ⋆ (IV ) + s∈S a∈A d ⋆ (s) f (t) (a|s)ϕ ⊤ (s, a)( ŵ(t) - ŵ(t) ⋆ ) (A) + s∈S a∈A d ⋆ (s) f (t) (a|s) ϕ ⊤ (s, a) ŵ(t) ⋆ -Q(t) (s, a) (B) + s∈S a∈A d ⋆ (s)π ⋆ (a|s)ϕ ⊤ (s, a)( ŵ(t) ⋆ -ŵ(t) )Below and we define EQUATIONEQUATIONEQUATIONwhere the third inequality follows from Assumption 4.3, the last inequality uses Jensen's inequality, and the penultimate inequality by Assumption E.2 and by noticing that for all w ∈ R p , we haveEQUATIONwhere the last line follows from the first-order optimality condition for the minimum point w EQUATIONEQUATIONwhere L Q is defined in Lemma E.7, the second line uses Cauchy-Schwartz's inequality and Young's inequality (117) and the last inequality uses Assumption 4.3 and Jensen's inequality. EQUATIONPlugging ( 296),( 298),( 299),(300) into (291) and dividing both sides by (1 -γ) yieldϑ ρ δ (t+1) -δ (t) +δ (t) ≤ D (t) ⋆ (1 -γ)α - D (t+1) ⋆ (1 -γ)α + 2 √ C ν (ϑ + 1) 1 -γ   ε(t) stat + 2 ε(t) approx + L 2 Q N ξ (t) -1( ξ(t) ) ⊤ 2 F   .Taking expectation on both sides of the above expression and making use of the simple fact thatE √ x ≤ E[x] ,we reach the conclusion (123).G.8 Proof of Lemma E.9Proof of Lemma E.9. For any ζ > 0, by the actor update rule (34) and (114) we have thatEQUATIONwhere the last line follows from Young's inequality (116) and (11). By the gradient tracking step (33) , Young's inequality (116) and (11), we haveEQUATIONAlso note that by Assumption E.2 and (304) we have ∀t ∈ N :EQUATIONTherefore, by (306) and (308) we haveEQUATION)where the first inequality uses Young's inequality (117).Note that by the update rule (34), the double stochasticity of the mixing matrix W and the consensus property (11) we haveEQUATIONwhere the penultimate line uses Jensen's inequality and the last line follows from (304), Assumption E.2 and (271).Combining (310) and (309) with (302), we deduceEQUATION)Finally, (124) follows from taking expectations on both sides of (301) and (311).Experimental setup. We study the empirical performance of FedNPG (Algorithm 1) and entropyregularized FedNPG (Algorithm 2) on a K × K GridWorld problem. To be specific, the collective goal of N agents is to learn a global optimal policy to follow a predetermined path which starts at the top left corner and ends at the bottom right corner. However, each agent only has access to partial information about the whole map: in figure 1 (where we take N = 3 and K = 9 as an example), agent n explores on map n, n ∈ [N ]. After taking an action, only when the agent is at the shaded positions can it get reward 1, otherwise it gets 0. We stipulate the action space of all agents to be A = {right, down}, i.e. movement is allowed only to the right or down. If an agent takes an action that will lead it out of the boarder of the map, we stipulate the agent's state doesn't change and receive reward 0. Each agent starts at the top left corner. To learn a shared policy to follow the path, we aim to maximize the average value function of all agents.Results. In the following we discuss the empirical results of our algorithms. In all the experiments, we fix the discounted factor γ = 0.99. In our experiments, we also don't require the mixing matrix to Here, W in (312) satisfies the double stochasticity assumption but is not symmetric. τ )/V ⋆ τ changing with the iteration number. We can see that both vanilla and entropyregularized NPG converges to the optimal value function in a few iterations, and the convergence speed is almost the same across different K. τ )/V ⋆ τ with respect to the iteration number. It can be seen that both vanilla and entropy-regularized NPG converge to the optimal value function in a few iterations, and the convergence speed is almost the same across different K, i.e. the impact of K on the convergence speed is minimal. We plot the curves of value functions changing with the iteration number. The green dashed line represents the optimal value. We can see that the convergence speed decreases as N increases. Same as before, the convergence speed is insensitive to the change of K.In Figure 3 , we study the performance of our algorithms when the number of agents N varies. We set K = 10, 20, 30, τ = 0.005, η = 0.1 and the communication graph to be the standard ring graph. We can see that the convergence speed decreases as N increases. Same as before, the convergence speed is insensitive to the change of K.In Figure 4 , we illustrate the effect of the communication network topology to our algorithms. To be specific, we change the number of neighbors of each agent (i.e., the number of non-zero entries in each row of W ) and (i) randomly generalize the weights of the graph such that each row of W sum up to 1, i.e.,W 1 = 1, see Figure 4 (a); (ii) set the non-zero entries in each row of W all to be 1 number of neighbors , see Figure 4 (b). We fix η = 0.1, K = 10, τ = 0.005. We plot the curves of value functions changing with the iteration number. The green dashed line represents the optimal value. For both 4(a) and 4(b), the convergence speed increase as number of neighbors of each agent increases. FedNPG performs better when using equal weights. 4 (a), we randomly generalize the weights of the graph such that each row of W sum up to 1; (ii) In Figure 4 (b), we set the non-zero entries in each row of W all to be 1 number of neighbors . We plot the curves of value functions changing with the iteration number. The green dashed line represents the optimal value. For both 4(a) and 4(b), the convergence speed increase as number of neighbors increases. FedNPG performs better when using equal weights.Note that even though there are many existing works in federated RL, none of the existing works, to the best of our knowledge, studies federated multi-tasks RL in the decentralized setting. Therefore, we are not able to compare our work with existing works. However, here we include a comparison between FedNPG and a naïve baseline without the Q-tracking technique (line 6 in Algorithm 1). For this plot, we use the standard ring graph (Eq. 312). We fix the size of the maze K = 30, learning rate η = 0.1, and regularity coefficient τ = 0.005. We experiment on different number of agents N and plot the curves of value function changing with the iteration number. The plot shows that while FedNPG converges within a few iterates, the algorithm without Q-tracking diverges, confirming the positive role of Q-tracking in ensuring convergence.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).Our work seamlessly handles the server-client setting as a special case, by assuming the network topology as a fully connected network.Here ∥•∥ could be any norm in R p .Here ∥•∥ could be any norm in R p .(C) + s∈S a∈A d ⋆ (s)π ⋆ (a|s) Q(t) (s, a) -ϕ ⊤ (s, a) ŵ(t) ⋆ (D) ≥ 1 α (D (t+1) ⋆ -D (t) ⋆ ).(291) 


Decision: This paper develops federated reinforcement learning algorithms for the setting where clients’ transition kernels are the same but their reward functions differ. The authors consider both the tabular and function approximation settings and derive (last iterate / consensus) convergence rates for natural policy gradient and actor critic approaches under general client connectivity conditions. In general, the reviewers found the analysis rigorous and comprehensive. Areas for improvement mostly lie in the motivations given for the problem setting (discussed in Appendix B.1) and the mismatch with developed theory:
- Optimizing for average reward: ideally, in a hospital setting, one would want a bespoke treatment for each patient, not a one-size-fits-all treatment. Reviewer vHsi gives an illustrative example of the impact of optimizing average reward on individuals in their weakness (1).
- Acceleration / knowledge transfer: the convergence rates do not reveal a dependence on the number of clients / tasks that implies speedup as is suggested by the authors’ references to  [KSJM22, WJC23] in the paragraph on *Distributed and federated RL*.

As a suggestion, the authors might better motivate the setting by assuming each client samples a reward function from the same reward distribution. One would like to learn a policy that is optimal w.r.t. the expected reward function, but a single client / agent only observes a single sampled reward function. In this setting, federated learning allows many clients to leverage each other's sampled reward functions to indirectly learn a policy that is individually optimal. Overall, the reviewers are generally positive about the contribution of the work, and so we recommend accepting this paper.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: The authors need to more clearly address the limitations on the required information of the proposed algorithms.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: None,
limitations: limitations: None.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: Please see the weaknesses part.
limitations: limitations: No further limitations to be addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: (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: questions: See the section above.
limitations: limitations: Yes.

Comments: title: Rebuttal Feedback
comment: Yes, thanks.  The response does address at least some of my concerns.  I will move the score up.
Dear Reviewer vHsi,

Thank you very much for raising the score! For W1, we'll make it clear that we consider the cooperative setting in our updated paper. Thank you for your suggestion. For W3, we currently don't know if $O(\epsilon^{-2})$ sample complexity is achievable in the fully decentralized multi-task setting we consider and will leave exploring it as future work. Thank you for your interests in this!

Many thanks, Authors
Thanks for the response and addressing my concerns. The newly provided examples seems reasonable. I decide to remain my score.
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?
Dear Reviewer bXwg,

Thank you very much for raising the score! We'll move the consensus error bounds to the main paper in our updated version.
Thank you for your responses which address my concerns. 

I believe that the convergence of the local policies to the aggregated policy is important to understand the results, so please consider to move the consensus error bounds to the main paper. 

I'm happy to increase the score.
Dear Reviewer vHsi,

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
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
Dear Reviewer tByy,

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
Dear Reviewer bXwg,

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