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] O
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 rate
; 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.
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 by
for 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
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
where
Analogously, for all (s, a) ∈ S × A, the regularized (or soft) Q-function Q π τ of policy π is related to the soft value function V π τ (s) as
The 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)
for 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 as
Turning to the regularized problem, we note that the update rule of entropy-regularized NPG becomes
where η ∈ (0, 1-γ τ ] is the learning rate, and
τ is the soft Q-function of policy π (t) .
3 Federated NPG methods for multi-task RL
In 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) =
Clearly, the global value function corresponds to using the average reward of all agents r(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 as
and the global soft Q-function is given by
s, 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 by
, 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
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
The spectral radius σ determines how fast information propagate over the network. For instance, in a fully-connected network, we can achieve σ = 0 by setting
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 have
where 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:
Update the policy for each (s, a) ∈ S × A:
where
Evaluate Q (t+1) .
Update the global Q-function estimate for each (s, a) ∈ S × A:
7: end for 3.1 Proposed federated NPG algorithms Assuming softmax parameterization, the problem can be formulated as decentralized optimization,
where π θ := 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) := π
⊤ be the collection of policy estimates at all agents in the t-th iteration.
Let
which satisfies that π (t) (a|s)
could be seen as the normalized geometric mean of {π
. 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) ∝
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 vector
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
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).
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.
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 reach
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 estimate q
in Algorithm 1. Under the assumptions of Theorem 3.3, when
, we have
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 most
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
, such that if 0 < η ≤ η 0 , then we have
where and C 1 is some problem-dependent constant. Furthermore, the consensus error satisfies
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 most
up to logarithmic factors. Especially, when η = η 0 , the best iteration complexity becomes
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
n τ,n in Algorithm 2. Under the assumptions of Theorem 3.6, we have
where
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:
for 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:
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) = (ξ
N ) ⊤ ∈ R N ×p , and the critic parameters of all agents as w (t) = (w
• First, the critic parameter w (t) n is locally updated at each agent by aiming to minimize ℓ(w, Q
)) with gradient descent, where Q (t) n is the local Q-function of the local policy f ξ (t) n , and d(t) n is the state-action visitation distribution induced by the local policy f ξ (t) n and an initial state-action distribution ν (determined from the data sampling mechanism, cf. (30)). However, since
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 by
, 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
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
) n ≤ ε n approx , where w (t) ⋆,n := arg min w ℓ w (t) ⋆,n , Q (t) n , d(t) n . We denote the average approximation error as εapprox = 1 N N n=1 ε n approx . Similar as [YDG + 22], we need the following assumption that bounds the transfer errors due to distribution shifts. Assumption 4.3 (Bounded transfer error). There exists C ν > 0 such that for all n ∈ [N ] and t ∈ N, it holds that E (s,a)∼ d(t) n h π (s,a) d(t) n (s,a) 2 ≤ C ν , where h π (s, a) is the state-action visitation distribution induced by any policy π from initial state distribution ρ.
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.
Theorem 4.4 (Convergence rate of Algorithm 3 (informal)). Let ξ
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 satisfies
and the number of critic iterations satisfies
In the server-client setting when σ = 0, to reach (26), it suffices to choose
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.
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.
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 regularization
We record the entropy-regularized FedNPG method in Algorithm 2 here due to space limits.
Algorithm 2 Federated NPG (FedNPG) with entropy regularization
Update the policy for each (s, a) ∈ S × A:
Update the global Q-function estimate for each (s, a) ∈ S × A:
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 :
For a distribution ρ ∈ ∆(S), we define
We also define the state-action visitation distribution dπ ρ as
Furthermore, we extend the definition of dπ ρ by specifying the initial state-action distribution ν ∈ ∆(S × A) and define
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
) (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γ):
which 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
n locally using Algorithm 4, which aims to minimize ℓ(w, Q
n , d(t) n ) by stochastic gradient descent. Note that since we don't know the Q-function
n in the gradients, we need to invoke Algorithm 5 [YDG + 22, Algorithm 3] to give an unbiased estimate
). As a consequence, in line 4 of Algorithm 4, we have
In 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) = (ξ
Update the critic parameter for estimating the global Q-function:
Actor update:
7: end for Algorithm 4 Critic(K, ν, ξ, γ, β, r): sample-based regression solver to minimize ℓ(w, Q
Compute the stochastic gradient estimator of L Q :
Critic Update:
For technical convenience, we present first the analysis for entropy-regularized FedNPG and then for vanilla FedNPG.
Algorithm 5 Q-Sampler(ν, π, γ, r)
To facilitate analysis, we introduce several notation below. For all t ≥ 0, we recall π (t) as the normalized geometric mean of {π
from which we can easily see that for each (s, a)
τ,1
. . .
In addition, we define
For notational convenience, we also denote
Following [CCC + 22b], we introduce the following auxiliary sequence {ξ (t) = (ξ
where T (t) (s, a) is updated via (16). Similarly, we introduce an averaged auxiliary sequence {ξ
We introduces four error metrics defined as
where u (t) , v (t) ∈ R |S||A| are defined as
We collect the error metrics above in a vector Ω (t) ∈ R 4 :
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 satisfy
Moreover, the consensus errors satisfy:
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:
where we let
and
In addition, it holds for all t ≥ 0 that
Proof. See Appendix F.1.
Let ρ(η) denote the spectral norm of A(η). As Ω (t) ≥ 0, it is immediate from (49) that
2 , and therefore we have
2 . It remains to bound the spectral radius ρ(η), which is achieved by the following lemma. Lemma D.3 (Bounding the spectral norm of A(η)). Let
where
Proof. See Appendix F.2.
We define the collection of inexact Q-function estimates as
and then the update rule (U T ) should be understood as
in the inexact setting. For notational simplicity, we define e n ∈ R as
and let e = (e
τ , the approximation of
With slight abuse of notation, we adapt the auxiliary sequence {ξ (t) } t=0,••• to the inexact updates as
In addition, we define
where
We let Ω (t) be
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
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 have
Moreover, the consensus errors satisfy:
then inexact entropy-regularized FedNPG could still achieve 2ε-accuracy (i.e.
Remark D.5. When η = η 0 (cf. ( 54) and ( 53)) and τ ≤ 1, the RHS of (67) is of the order
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:
where A(η) is provided in Lemma D.2. In addition, it holds for all t ≥ 0 that
Proof. See Appendix F.3.
By (68), we have
which gives
Here, (71
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. When
we have
for any fixed state distribution ρ. Furthermore, we have
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) :
In addition, similar to (38), we define
Following the same strategy in the analysis of entropy-regularized FedNPG, we introduce the auxiliary sequence {ξ (t) = (ξ
as well as the averaged auxiliary sequence {ξ (t) ∈ R |S||A| }:
As usual, we collect the consensus errors in a vector
, where u (t) , v (t) ∈ R |S||A| are defined as:
Step 1: establishing the error recursion. The next key lemma establishes the error recursion of Algorithm 1. Lemma D.8. The updates of FedNPG satisfy
for all t ≥ 0, where
In addition, we have
where
Moreover, when η ≤ η 1 , we have
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:
the rationale for this choice will be made clear momentarily. We define the following Lyapunov function
which satisfies
Here, the second inequality follows from (82). One can verify that the second term vanishes due to the choice of p(η):
Therefore, we conclude that
.
Step 3: simplifying the expression. We first upper bound the first term in the RHS of (89). Assuming uniform initialization for all π (0)
Therefore, putting together relations (86) and ( 221) we have
To continue, we upper bound the second term in the RHS of (89). Note that
Thus we have
where the first inequality follows from (91) and the second inequality follows from the definition of η 1 and J. By (92), we deduce
) 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
we have
for any fixed state distribution ρ.
Furthermore, we have
We next outline the proof of Theorem D.9. With slight abuse of notation, we again define e n ∈ R as
and let e = (e 1 , • • • , e n ) ⊤ . We define the collection of inexact Q-function estimates as
and then the update rule (16) should be understood as
in the inexact setting. Define q (t) , the approximation of Q (t) as
we adapt the averaged auxiliary sequence {ξ (t) ∈ R |S||A| } to the inexact updates as follows:
As usual, we define the consensus error vector as
The following lemma characterizes the dynamics of the error vector Ω (t) , perturbed by additional approximation error.
Lemma D.10. The updates of inexact FedNPG satisfy
In addition, we have
where ϕ (t) (η) is defined in (83).
Moreover, when η ≤ η 1 , we have
Proof. See Appendix F.5. Similar to (87), we can recursively bound Φ (t) (η) (defined in (86)) as
From the above expression we know that
via telescoping. Combining the above expression with (90), ( 92) and (93), we have
which 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 denote
, and define d
n and d(t) n analogously. We also let
and assume ϑ ρ < ∞.
We also introduce a weighted KL divergence given by
where
Given a state distribution ρ and an optimal policy π ⋆ , we define a state-action measure d⋆ as
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.
To present the convergence results of FedNAC, we further introduce the following notation, where t ∈ N represents the iteration step in FedNAC:
⋆,n ∈ arg min
For 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 have
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 have
where 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 have
Proof. We only need to note that
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 have
Proof. (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 have
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 have
Proof. See Appendix G.6.
For each iteration step t in Algorithm 3, we let ξ(t
We let
and define δ (t) := V ⋆ -V (t) (ρ), where V (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 have
Proof. See Appendix G.7.
Lemma E.9 (linear system). For any t ∈ N, we let
2 ) ⊤ . Then for any ζ > 0, we have Ω (t+1) ≤ CΩ (t) + s, (124) where
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 ξ
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 satisfies
where L Q is defined in Lemma E.7, we have
Moreover, the consensus errors could be upper bounded by
where
Remark E.11 (Sample and communication complexity). When σ > 0 and
Consequently, we need
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 O
On the other end, when σ = 0, (128) becomes:
Consequently, for any fixed α > 0, when σ = 0 or close to 0, with
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 that
where √ • is exerted element-wise.
In addition, taking expectation on both sides of (123) and using the act that
we have
We define the Lyapunov function Φ (t) as follows:
where
It's straightforward to verify that when ζ = 1-σ 2 2 , we have the entries in C (cf. (125)) satisfies
we deduce
which gives
which together with (140) and the fact
indicates q 1 , q 2 > 0 and that
Thus by ( 133) and (134) we have
which gives
Summing the above inequality over t = 0, 1, • • • , T -1 and divide both sides by T , we have
Since
and
By Theorem E.3 we know that √ εstat could be upper bounded as follows:
(128) follows from plugging (149) into (148) and noting that when ξ
where the third inequality uses (138), (139), and the fourth inequality uses (127).
Therefore, similar to (230), when α ≤ α 1 , we have
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.
Consider the stochastic gradient recursion
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 by
from which we deduce E Q ξ (s, a)ϕ(s, a)
Furthermore, we introduce the residual
then from Lemma 7 in [YDG + 22] we know that
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 that
from which we deduce
The above expression implies
Therefore, (iv) is verified.
Thus by (267), with stepsize β = 1 2C 2 ϕ , initialization w 0 = 0 and K steps of critic updates, we have
which gives (113).
F.1 Proof of Lemma D.2
Before 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.,
2. For any t ≥ 0, log ξ (t) keeps track of the average of log ξ (t) , i.e.,
It follows that ∀s ∈ S, t ≥ 0 :
Lemma F.2 ([CCC + 22b, Appendix. A.2]). For any vector θ = [θ a ] a∈A ∈ R |A| , we denote by
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 have
where 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) -
(s, a)1 N 2 . By (U T ) we have
where the penultimate step uses property (11), and the last step is due to
Step 3: bound
∞ . We decompose the term of interest as
which gives
The last step is due to log ξ
n (s, a)log ξ (t) (s, a) ≤ u (t) (s, a), while the penultimate step results from writing
and applying the following lemma.
Plugging ( 169) into (168) gives
Step 4: bound
Let w (t) : S × A → R be defined as
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 that
and consequently
It boils down to control w (t) ∞ . To do so, we first note that for each (s, a) ∈ S × A, we have
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:
Here, the first step results from the following relation established in [NNXS17]:
which also leads to
by Lemma F.2. For the remaining terms in (176), we have
and
where 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 at
Using previous display, we can write (174) as
Combining (167) with the above expression (181), we get
Step 5: bound
For any state-action pair (s, a) ∈ S × A, we observe that
where 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]:
To continue, note that by ( 162) and (41b) we have
Plugging ( 185) into ( 183) and ( 181) establishes the bounds on
for any (s, a) ∈ S × A. In view of property (164), the first term on the right-hand side of (186) can be bounded by
Plugging the above expression into (186), we have
which gives
(187) Plugging the above inequality into (171) and (182) establishes the bounds on Ω (t+1) 3
and Ω (t+1) 2 in (49), respectively. Step 6: boundmin 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 has
Proof. See Appendix G.3.
Using (189), we have
which gives
This establishes the bounds on Ω (t+1) 4
in (49).
Let f (λ) denote the characteristic function. In view of some direct calculations, we obtain
where, for the notation simplicity, we let
Note that among all these new notation we introduce, S, d are dependent of η. To decouple the dependence, we give their upper bounds as follows
where (194) follows from η ≤ (1γ)/τ , and (195) uses the fact that α ≤ 1 and 1α ≤ 1.
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 have
and from λ ⋆ ≥ 1+(1-α)γ+α 2 we deduce
which gives
Combining ( 200), ( 197), (198), we have that
To continue, we upper bound f 1 (λ ⋆ ) as follows.
Plugging ( 201),( 202) into (192) and using (199), we have
where the penultimate inequality uses 1 2σ ≤ 1-σ 2 , and the last inequality follows from the definition of ζ (cf. (53)).
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
Similar to (167) we have
Step 3: bound
∞ . In the context of inexact updates, (168) writes
For the last term, following a similar argument in (169) leads to
Combining the above two inequalities, we obtain
Step 4: bound Q
. We remark that the bound established in (174) still holds in the inexact setting, with the same definition for w (t) :
To deal with the approximation error, we rewrite (176) as
where the second term can be upper-bounded by
Combining ( 207), (206) and the established bounds in (175), ( 178), (180) leads to
Combining the above inequality with (205) and (203) gives
Step 5: bound
. It is straightforward to verify that (187) applies to the inexact updates as well:
Plugging the above inequality into (204) and ( 208) establishes the bounds on Ω (t+1) 3
and Ω (t+1) 2 in (68), respectively.
Step 6: boundmin 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 error
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 has
Using (210), we have
F.4 Proof of Lemma D.8
Step 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 have
or equivalently
Step 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 have
The term Q (t+1) (s, a) -Q (t) (s, a) 2 can be bounded in a similar way in (174):
where the coefficient (1+γ)γ (1-γ) 2 comes from M in Lemma F.3 when τ = 0, and w
It remains to bound w (t) 0
∞ . Towards this end, we rewrite (175) as w
Note that it holds for all (s, a) ∈ S × A:
. This along with (218) gives
Combining the above inequality with (216) and (215), we arrive at
Step 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 satisfy
where
It remains to control the term Q
∞ . Similar to (169), for all t ≥ 0, we have
where (a) invokes Lemma F.3 with τ = 0 and (b) stems from the definition of u (t) . This along with (220) gives
Step 4: bound the consensus error. To bound the consensus error log π
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(η)).
which gives
Note that when η ≤ η 1 , we have (recall that J = 2(1+γ)γ
(1-γ) 2 √ N ):
Plugging the above two expressions into (223) yields
Therefore, when η ≤ η 1 , we have
Combining the above inequality with the following fact:
where 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.
Step
. From (96), we have
) Note that (216) still holds for inexact FedNPG:
0 is defined in (217). We rewrite (218), the bound on w (t) 0 (s, a), as w
With the following bound
Putting all pieces together, we obtain
Step 2: establish the descent equation. Note that Lemma F.6 directly applies by replacing Q (t) with q (t) :
To bound the middle term, for all t ≥ 0, we have
Hence, ( 102) is established by combining the above two inequalities.
Step 4: bound the consensus error. Similar as ( 224), here we have
n is the normalization term (cf. line 5, Algorithm 2) and {c
n (s)} are some constants. To prove the second claim, ∀t ≥ 0, ∀(s, a) ∈ S × A, let
Taking inner product with 1 N 1 for both sides of (U T ) and using the double stochasticity property of W , we get
By the choice of T (0) (line 2 of Algorithm 2), we have T
τ and hence by induction ∀t ≥ 0 : T
Therefore, to prove (161), it suffices to verify the claim for t = 0:
By taking logarithm over both sides of the definition of π (t+1) (cf. ( 27)), we get
for 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 let
and Q π θ τ , respectively. From (6a) we immediately know that to bound
, it suffices to control V θ τ (s) -V θ ′ τ (s) for each s ∈ S. By (4) we have
so 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 let
and let h (t) ∈ R |S| be ∀s ∈ S :
Note that h (t) ∞ ≤ log |A|. We also denote H (t) : S → R |A|×|A| by: ∀s ∈ S :
then we have ∀s ∈ S :
where ∂h (t) (s) ∂θ (t) (•|s) stands for ∂h (t) (s) ∂θ(•|s) θ=θ (t) . The first term in (239) is further upper bounded as
By Lagrange mean value theorem, there exists t ∈ (0, 1) such that
where the inequality follows from (239) and the above inequality. Combining (5) with the above inequality, we arrive at
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 by
which can be represented in a matrix-vector form as
where e s ∈ R |S| is a one-hot vector whose s-th entry is 1,
with P t ∈ R |S|×|S| denoting the induced state transition matrix by π θ (t) P t (s, s ′ ) = a∈A π θ (t) (a|s)P(s ′ |s, a) , (243) and r t ∈ R |S| is given by ∀s ∈ S : r t (s) := a∈A π θ (t) (a|s)r(s, a) . (244) Taking derivative w.r.t. t in (241), we obtain [PP08] dV θ (t) (s) dt = γ • e ⊤ s M t dP t dt M t r t + e ⊤ s M t dr t dt .
We now calculate each term respectively.
• For the first term, it follows that
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.
• For the second term, it follows that
where the first inequality follows again from ∥M t ∥ 1 ≤ 1/(1γ), and the second inequality follows from
Plugging the above two inequalities into (245) and using Lagrange mean value theorem, we have
Step 3: sum up. Combining (250), ( 240) and (235), we have
Combining ( 251) and (6a), (170) immediately follows.
Proof of (246). For any vector x ∈ R |S| , we have
t dt x s = s ′ ∈S a∈A dπ θ (t) (a|s) dt P(s ′ |s, a)x(s ′ ) , from which we can bound the l ∞ norm as dP t dt x ∞ ≤ max s a∈A s ′ ∈S P(s ′ |s, a) dπ θ (t) (a|s) dt ∥x∥ ∞ = max s a∈A
as desired, where the last line follows from the following fact:
To simplify the notation, we denote
We first rearrange the terms of (234) and obtain
(254) This in turn allows us to express V (t) τ (s 0 ) for any s 0 ∈ S as follows
where 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 reach
-τ log π (t+1) (a 0 |s 0 ) + r(s 0 , a 0 ) + γV
Note that for any (s 0 , a 0 ) ∈ S × A, we have
To finish up, applying (256) recursively to expand V (t) τ (s i ), i ≥ 1 and making use of (257), we arrive at
where 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 have
For all t ≥ 0, we define the advantage function A (t) as:
Then for Alg. 1, the update rule of π (Eq. ( 234)) can be written as
where δ (t) is defined in (253) and
where 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:
from which we can see that
where we use (263), and that
which follows from
For any fixed ρ, we use d ⋆ as shorthand for d π ⋆ ρ . By the performance difference lemma (Lemma G.1),
where we use (262) in the second equality.
By applying (265) with µ = d ⋆ as the initial state distribution, we have
Plugging the above equation into (266), we obtain
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.
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).
Proof of Theorem E.3. We let a k and b k in Theorem G.2 be ϕ(s, a) and Q ξ ϕ(s, a) in Algorithm 4, respectively. And we let ∥
Let H be the length of trajectory for estimating Q ξ (s, a). Then Q ξ (s, a) 2 is bounded by
Furthermore, we introduce the residual
then from [YDG + 22, Lemma 7] we know that E
To verify (iv), we let
from which we deduce
The above expression implies
Therefore, (iv) is verified.
Thus by (267), with stepsize β = 1 2C 2 ϕ , initialization w 0 = 0 and K steps of critic updates, we have
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. Define
then we have ∂f ξ (a|s) ∂ξ = f ξ (a|s) φξ (s, a) .
Analogous to (252), we have
where the last line follows is due to
Same as (245) in Lemma F.3, we have
And similar to (249), we deduce
which gives
Following the same steps in (247), we deduce
Combining the above two expressions (277) and ( 278) with (276), we deduce
which implies
Proof of Lemma E.8. By the update rule (114) and the parameterization (24) we know know that
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:
where Φ(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
Rearranging terms and dividing both sides by -α, we obtain
Let q = f (t) (•|s) and π ⋆ (•|s),resp., we have the following two inequalities:
Taking expectation w.r.t. distribution d ⋆ on both sides of (285), we arrive at
To simplify the notation we let Q(t) and V (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:
where 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:
Applying again Lemma G.1, we deduce the equivalent form of the second expectation in (286) as follows:
where the second term of the last line could be decomposed into the following terms:
Plugging (288), (290) into (287) and (289), resp., and making use of (286), we have
where 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.
Plugging ( 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 that
we reach the conclusion (123).
G.8 Proof of Lemma E.9
Proof of Lemma E.9. For any ζ > 0, by the actor update rule (34) and (114) we have that
where the last line follows from Young's inequality (116) and (11). By the gradient tracking step (33) , Young's inequality (116) and (11), we have h (t+1) -1 ŵ(t+1)⊤ 2 F = W (h (t) + w (t+1)w (t) ) -1 ŵ(t)⊤ + 1( ŵ(t)⊤ŵ(t+1)⊤ ) 2 F = W h (t) -1 ŵ(t)⊤ + W (w (t+1)w (t) ) -1( ŵ(t+1)⊤ŵ(t)⊤ ) + w (t)w
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 have
where 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 deduce
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.
• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA] Justification: the results are irrelevant to the compute resources.
Guidelines:
• The answer NA means that the paper does not include experiments.
• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?
Justification: the research conducted in the paper conforms with the NeurIPS Code of Ethics.
Guidelines:
• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA] Justification: this is a theoretical paper and it has no societal impact.
Guidelines:
• The answer NA means that there is no societal impact of the work performed.
• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
• 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).
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.
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 .
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