Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning
Authors: Tong Yang
Shicong Cen
Yuting Wei
Yuxin Chen
Yuejie Chi
Venue: NeurIPS 2024 poster (2024)
Keywords: federated RL
multi-task RL
natural policy gradient methods
entropy regularization
global convergence
sample complexity
Primary area: optimization

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.

Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning
Tong Yang" CMU
Shicong Cen CMU
Yuting Wei UPenn
Yuxin Chen UPenn
Yuejie Chi CMU
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 learn 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 natural policy gradient (NPG) methods
federated vanilla and 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, and further establish its robustness against inexact policy evaluation. We further propose a federated natural actor critic (NAC) method for multi-task RL with function approximation and stochastic policy evaluation, and establish its finite- time sample complexity taking the errors of function approximation into account. To the best of our knowledge, this is the first time that near dimension free global convergence is established for federated multi-tast RL using policy optimization.
Introduction
Federated reinforcement learning (FRL. an emerging paradigm that combines the advantages of federated learning (FL) and reinforcement learning (RL) [QZLZ211 ZFL*199 19], allowing multiple agents learn shared policy from local experiences, without exposing their private data central server nor other agents. FRL is poised to enable collaborative and efficient decision making in scenar- where data distributed, heterogeneous, and sensitive, which arise frequently applications such as edge computing, smart cities, and healthcare [WHM*22 23, WKNL20, ZFL 19]. to name just 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
Department of Electrical and Computer Engineering, Carnegie Mellon University; email:
tongyanglandrev.. cmu, edu.
Deppartment of Electrical and Computer Engineering, Carnegie Mellon University; email:
chigoondddrdr edu.
'Dpartment Statistics and Data Science, Wharton School, University of Pennsylvania; email: ytwei Owharton. upenn. edu.
Department Statistics Data Science, Wharton School, University of Pennsylvania; email:
yurinc@charton. udunn.edu.
Department of Electrical and Computer Engineering. Carnegie Mellon University; email: yuejiechi@cmu.eer edu.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

scenario where the agents can only communicate with their local neighbors over a prescribed network topology. 6
In this work, we study the problem of federated multi-task RL [AR21, Q71Z21, YLS+ 20], where each agent collects its own reward - possibly unknown other agents corresponding 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 shared policy that maximizes the total rewards accumulated from all the agents; in other words, one seeks policy that performs well in terms of overall benefits, rather culti-objective context. There is no shortage of application scenarios where federated multi-task RL becomes highly relevant. For instance, in healtheare [ZBW+20] 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. for more application scenarios of our setting.
than biasing towards any individual task, achieving the Pareto frontier
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 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- asymmtttmttii convergence guarantees even for tabular infinite-hrizon Markov decision processes.
Motivated by the connection with decentralized optimization, it is tempting to take a policy optimiza- tion 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 their simplicity and scalability. In particular, natural policy gradient (NPG) methods [Ama98, KakO1] 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, CWC21J, 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, XWL.20, 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 regulay-ee RL problem is of interest in its own right, as the optimal regularized policy possesses desirable robust properties with respect to reward perturbations [EL21,, MP95J. Due to the multiplicative update nature of NPG methods under softmax parameteri- zation, it 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 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. federated NAC (FedNAC) methods that allow for both stochastic
We further develop sample-efficier policy evaluation and function approximation. Our contributions are follows.
We propose FedNPG methods for both the vanilla and entropy-regulaaizen multi-task RL prob- lems, where each agent only communicates with its neighbors and performs local computation using its own reward or task information.
*Our work seamlessly handles the server-client setting as a special case, by assuming the network topology fully connected network.

---

setting
algorithms
iteration complexity
optimality criteria
NPG [AKLM21]
0 (1-
low LA1
r yxll Se
unregularized
FedNPG (ours)
ov log| a 18 wioc + (1-3)e))
1. Ei (V- - -voli) sc
NPG [CWC21]
o log log
V7 -.- S
regularized
FedNPG (ours)
max 1 log (t)
vi 5
Table I: Iteration complexities of NPG and FedNPG (ours) methods to reach E-accuracy of the vanilla and antropy-regularize problems, where assume exact gradient evaluation, and only keep the dominant terms w.r.t. e. The policy estimates in the I-iteration are x²() and (0)) for NPG and FedNPG, respectively, where T is the number of iterations. Here, N is the number of agents, T I 1 is the regularization parameter, E [0, 1 is the spectral radius of the network, 7 E [0, 1) is the discount factor, |A] is the size of the action space, and r) > 0 is the learning rate. The iteration complexities of FedNPG reduce to their centralized counterparts when 0. For vanilla FedNPG, the learning rate 1/3
is set as 1/1 = O (1~>)"(1-))
log LAI
for retropy-regularized FedNPG, the learning rate
TNo
satisfies 0 < < 170 O (1- (1-7)"11033
oN
Assuming access to exact policy evaluation, we establish that the average iterate of vanilla FedNPG converges globally rate of ((1/22/3) in terms of the sub-optimality gap for the multi-task RL problem, and that the last iterate of untropy-regularizer FedNPG converges globally at linear rate to the regularized optimal policy. Our convergence theory highlights the impacts of all salient problem parameters (see Table 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 foe sense.
We go beyond the tabular setting and black-box policy evaluation by proposing FedNAC- 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 (1/g7/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 opti- mization methods for multi-task RL that achieve near dimension 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 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, S, We let (I&d, II-I]) denote the d-dimensional real coordinate space equipped with norm ||- The nn-morm of a is denoted by ||e||,p where S S co, and the spectral norm and the Frobenius norm of a matrix M are denoted by || and || lp- resp. We let [N] denote {1. (I.....N) use 1 to represent the all-one vector of length N, and denote by 0 a vector or a matrix consisting of all O's. We allow the application of functions such as log(-) and exp(-) (-) to vectors or matrices, with the understanding that they are applied in element-wise manner.
2 Model and backgrounds
Markov decision processes. We consider an infinite discounted Markov decision process (MDP) denoted by M = AS, P,r,7), where S and denote the state space and the action space, respectively, 7 E [0. 1) indicates the discount factor, P S x A - A(S) is the transition kernel, and S:S - [0, 1] stands for the reward function. To be more specific, for each state-action pair (s,a) E S x A and any state s' S, we denote by P(s' [s, a) the transition probability from state
3

---

to state s' when action a is taken, and r(s, a) the instantaneous reward received in state when action is taken. Furthermore, policy т S - ((A) specifies an action selection rule, where (als) specifies the probability of taking action in state for each (, E 8 x A.
For any given policy x, we denote by V S - IR. the corresponding value function, which is the expected discounted cumulative reward with an initial state so 8, given by
SA S: (T())= = E
Σ 2 a:)
where the randomness is over the trajectory generated following the policy at <(1ss) and the MDP dynamic S1+11 ~ P(|ss,,;)) at). We also overload the notation (*(p) to indicate the expected value function of policy when the initial state follows distribution over S, namely, V"(p) =
Egpp [V*(s), (s)). Similarly, the Q-function Q" S x + of policy æ is defined by
Q"(s,a)== =
Σ 1'r(s,, 4s) 8, 40
(2)
for all (s, a) E S x.AA, which measures the expected discounted cumulative reward with an initial state 80 and an initial action do a, with expectation taken over the randomness of the trajectory. The optimal policy n refers to the policy that maximizes the value function (*(s) for all states s E S, which is guaranteed exist [Put14]. The corresponding optimal value function and Q-function denoted as V and Q", respectively.
Engroiy-regullrrized 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
a(s,a) E S x A: (r(s,)) = : a) T log (als),
(3)
where 0 denotes the regularization parameter. Typically, should not be too large to outweigh the actual rewards; for ease of presentation, we assume - S min 1, log LAT [CCDX22]. Equivalently, this amounts to the entropy- entropy-regullrized (also known "soft") value function, defined as
Vs S: (x) = =6)==V V*()) +H(,
(4)
where
H(8 m) == E
7" log ग. (a)ls:))
(5)
Analogously, for all as) S A, the regularized (or soft) Q-function Q, of policy related to the soft value function (17(s) as
Q a) r(s,a) + [V7 (T(s) En-r((1ss) (ass (s,
(6a)
(6b)
The optimal regularized policy, the optimal regularized value function, and the Q-function are denoted by n; Vi, 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 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 лy softmax(()
exp 0(, a)
Te (a(s) = Evee expo(s,0)
+ R and as S A. for any 0: S -
In the tabular setting, the update rule of vanilla NPG at the f-th iteration can be concisely represented
(t))))ss
((++)((ass) x ( (als) exp
(8)
1->

---

Turning to the regularized problem, we note that the update rule of entropy- regularze NPG becomes
(s,
(als) (T (als)) exp
(9)
1-7
where 1f (0, 7 is the learning rate, and Q!"² Q7 is the soft Q-function of policy x(0)
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 collabo- ratively a single policy that maximizes its average performance over all the tasks using only local computation and communication.
Multi-task RL. Each agent n E [N] has its own private reward function (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 > V (s), where Vi is the value function of agent E [N], defined by N
(8) E
Σ r'rn (8t, ax)) 80
Clearly, the global value function corresponds to using the average reward of all agents r(s, a) = N Em (s) The global Q-function Q* a) and the agent Q-fuctiions Q7 (s, a) can be defined in similar manner obeying (" a) = ,/4 Σx (7(s,a).
1
In parallel, we are interested in the entropy-regularized setting, where each agent E [N] is equipped with a regularized reward function given by Tr.n (s, == (n(s, log (als)) And define similarly the regularized value functions
V. (8) = E Σ
for all n E [N] and (s) =
1 N
Em
(s), Vs E S. The soft Q-function of agent n is given by V Tm
(s, = (n a) + 7 (.. (+))
(10)
and the global soft Q-function is given by (s, a) E 17,n
Federated policy optimization in the fully decentralized setting. We consider federated setting with fully decentralized communication, that is, all the agents synchronized to perform information exchange over some prescribed network topology denoted by an undirected weighted graph ([NN), E). Here, E stands for the edge set of the graph with N nodes each corresponding and two agents can communicate with each other 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 W -= [wegy] E [0, 1| xN where wij is a positive number if (i,j) E E and 0 otherwise. We also make the following standard assumptions on the mixing matrix.
agent
Assumption 3.1 (double stochasticity). The mixing matrix W = [wa]] E N is symmetric (i.e., W = W) and doubly stochastic (i.e., W1x = Iv, 1 W = 1.
The following standard metric measures how fast information propagates over the graph. Definition 3.2 (spectral radius). The spectral radius of W is given = | l E 10. 1).
The spectral radius a determines how fast information propagate over the network. For instance, in fully-connected network, we can achieve regarding different graphs, we refer the readers [NOR18]. In an Erdös-Rényí random graph, as long as the graph is connected, one has with high probability a x 1. Another immediate consequence that for any x E R letting N 1 x be its average, we have
by setting W 인 11 T. For control of 1/(1 - a)
WE #1 N 2 S a || alwll
(11)
where the consensus error contracts by factor of o.
5

---

Algorithm 1 Federated NPG (FedNPG)
1: Input: learning rate > 0, iteration number T N4, mixing matrix W RNNN
2: Initialize: π (0) ( = -)))
3: for /. 0, 1, ....
do
4: Update the policy for each (s, a) E S x A:
log π (als) = W log π 10 (als)
+ 1 1-
(s))))))) - log 2 21)
(15)
where Ema exp W (log ( (d'ls)
5: Evaluate ((++1).
6: Update the global Q-function estimate for each (s, a) E S x A:
TT++) = w (1) Q ((+)))(( (s. (s.
(16)
Q-tracking
7: end for
3.1 Proposed federated NPG algorithms
Assuming softmax parameterization. the problem can be formulated as decentralized optimization,
N
(unregularized)
max (s)
(s),
(12)
N
n
#=1
(regularized)
max W (s)
(s),
(13)
where Ty == softmax(0) subject to communication constraints. Motivated by the success of NPG methods, aim to develop federated NPG methods to achieve goal. For notational convenience, be the collection of policy estimates at all agents in the /-th iteration.
let (()) = (mi ,,) Let
(1)
(1) T
N
# (1) = softmax
log
T
(t)
(14)
N
==1
which satisfies that (als) & (IT An (1) (als)
1/N
for each (s) E 8 A. Therefore, T(t)
could be seen as the normalized geometric mean of { (1)
[NE[N]- Define the collection of Q-function
estimates (+))_ (QT*
and Q4 ( S.
We shall often abuse
the notation and treat π (1), @ as matrices in R [ and treat ग (als), Q (als) as vectors in N, for all (s) E S x
Vanilla federated NPG methods.
To motivate the algorithm development, observe that the NPG method (cf. (8)) applied to (12) adopts the update rule (a+)) oc
( (als) exp "EE Qz10) (x.o) for all (s, S A. Two challenges arise when executing N(1->)
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:(1) (s, a) of the
x At each iteration, each agent updates its policy estimates based on its neighbors' information via gossip mixing, in addition ((-())
global O-function, which are collected as vector (1)) (I(() .... ....
to correction term that tracks the difference Q7 (s. a) 27 (s. a) of the local Q-functions between consecutive policy updates. Note that mixing is applied linearly to the logarithms of local policies, which translates into a multiplicative mixing of the local policies. Algorithm summarizes the detailed procedure of the proposed algorithm written 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 E [N] will only be responsible to evaluate the local policy my. using the local reward Tn.
retropy-regullrizzed 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 entropy- regularized FedNPG method reduces to vanilla FedNPG in the absence of the regularization (i.e.. when 5 = 0).
3.2 Theoretical guarantees
Global convergence of FedNPG with exact policy evaluation. We begin with the global conver- gence of FedNPG (cf. Algorithm 1), stated 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.
(0) Theorem 3.3 (Global sublinear convergence of exact FedNPG (informal)). Suppose TT n E [N]] are
128 log LAkr* and 17
(1->)) (1-m) Ing LA] 1/3
set the uniform distribution. Then when T 2
(1-o)*
N27
we have
1
V*(p) - V= (0) - (d))")
N1/302/3
log IA) 2/3
(17a)
T
(1 - 7)T (1-7)3((1 - -0)2/3
N2/3g1/3
log [A]
1/3
log / - log +())
(17b)
71 -///33
T
Theorem 3.3 characterizes the average-iterate convergence of the average policy 7(1) (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 the convergence rate of FedNPG recovers the (1/"T) rate, matching that of the centralized NPG established [AKLM21]; on the other end, in the decentralized setting where a > FedNPG slows down and eventually converges the slower ((1 /T23 rate.
We state the iteration complexity in Corollary 3.4. Corollary
1 Et= (V*(p) 3.4 (Iteration complexity of exact FedNPG). To reach T 6, the iteration complexity of FedNPG is at most Volog [A| + ((1ン)))
VT(
S
O (7-))7((--)))) +
(I-o))
Global convergence of FedNPG with inexact policy evaluation. In practice, the policies need to 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
are used in replace of QT" =(1) in Algorithm 1. Under the assumptions of Theorem 3.3, when
VN /Nlog/Alo* and 11 (119)" (1-0)² log LA) 1/3 32
T
have
(I-a)*
T-1 v*()) VTl (0)
V' Vi(ag')
2//3
log |A|
2/3
S
p
T
T)
(1
31
0//33
T
|
=(0 On
max ne NE te
(18)
(1 7
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 find an e-optimal policy is at most
N
(19)
g33.
7

---

for sufficiently small E.
Global convergence of entropy-regularrized FedNPG with exact policy evaluation. Next, present our global convergence guarantee of retropy-regularized FedNPG with exact policy evaluation (cf. Algorithm 2).
Theorem 3.6 (Global linear convergence of exact entropy-reeullarized FedNPG (informal)). For (1->)" -0)rr
any > E (0, 1) and 0 < S 1, there exists 'oo = min 1=2
} such that if
o
1j S NJo, then we have
| - Q7 22)C1((T)
log -logm
201 S -P(n)'
(20)
where :,";===00 QT p(n) max Furthermore, the consensus error satisfies
=
7n 3+0
and C1 is some problem-dependent constant.
Vn E [N] || m. - log 11 S 201p(1)).
(21)
The exact expressions of C1 and ?j are specified in Appendix D.I. Theorem 3.6 confirms that regulazzee 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 tp +l matching that of the centralized entropy-regullarize NPG established in [CWC21]. When the network is less connected, one needs to be more conservative in the choice of learning rates, leading to higher iteration complexity, as described in the following corollary.
Corollary 3.7 (Iteration complexity of exact entropy- FedNPG). To reach |log क log (0 | I E, the iteration complexity of entropy FedNPG is at most
{2
maax
log
(22)
Tr
up logarithmic factors. Especially, when 1j 1lo. the best iteration complexity becomes O
(a--7 + log
No²
Global convergence of entropy- FedNPG with inexact policy evaluation. Last but not the least, present the informal convergence results of autrop-regulaarin FedNPG with inexact policy evaluation, whose formal version can be found in Appendix D.2.
Theorem 3.8 (Global linear convergence of inexact entropy-regularived FedNPG (informal)). Sup-
pose that an estimate 9rih are used replace of Q in Algorithm 2. Under the assumptions of Theorem 3.6, we have
(t))
1Q - Qi1l 2: (Cioln)) || क - log
2 = <C(((())) + +C2Ea), (23)
(0) where phth == QTT") Eg i= (Mer) 1|
ll p(n) S max(1
TM 3ta
1, and
2
Ci. C2 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 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:
exp(è ( (s. for (s, a) E S x and & RR,, where 6: bounded over S x A, i.c., there exists Cp > 0 such that [Ø(s, a)ll2 Co holds for all (s, a) e A
fe(als) Evre exp(0 (s, a')
(24)
RRP a known feature map. We assume

---

Following [AKLM21, YDG" YDG*22), given any w E R", R A R and probability distribution
E A(S x A) over the state-action space, we define the function approximation error E(w, Q, () as follows:
{(w, Q. = B(o,))s (w0
o(s Q(s,a))
(25)
By searching for un that minimizes E(ur, Q (), it approximates Q(8, a) using the feature map e 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 g()) = (5 ,..,,..., ) E
NN and the critic parameters of all agents as w(() (w/
w (1) T NNx (concerning the
local Q-values) and ht)) (h1 ..... ,...,,""'" ) NR (concerning the global Q-values).
First, the critic parameter ! is locally updated at each agent by aiming to minimize f(w, Q"",, (0t) (ef. (25)) with gradient descent, where Q!" is the local Q-function of the local policy fggo, and d( is the state-action visitation distribution induced by the local policy fee and an initial state-action distribution v (determined from the data sampling mechanism, cf. (30)). However, since Q! is not directly available, it needs to be estimated from samples. Therefore, the critic update takes K steps stochastic gradient descent with critic learning rate 3, given by
W = Wh [ ((sk; ax) - Qe(sk. (x)))((k)))))))))))))))))))) ax),
for ic = O...., - where (sk, ax)) is sampled on the local policy fee, and Q5( as) is careful estimate of the Q-value using trajectory with expected length 1/(1 -7) (see Algorithm 5 in Appendix C.2 adopted from [YDG+22, 22, Lemma 4)), and wh for simplicity. The final
critic is updated as wa 1 Σk= Ly. The total sample complexity of the critic update per K
iteration is then on the order of k/(1-7).
Next, the critic parameter ( for estimating the global Q-function can then be esti- mated by averaging with the neighbors with the Q-tracking term, given by (t) W (h(t-1) + wit) ((((!))) w((-
Finally, the actor parameter <!(h) can be updated via averaging with the neighbors along with the policy gradient informed by hn given by ((++1)= W (g(() + +ahl)) where is the learning rate the actor.
Note that the sample complexity of FedNAC is the order of KT/(1- 7).. An important aspect of the FedNAC method 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 22, AKLM21J. 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 the critic.
Assumption 4.1 (PSD of the covariance matrix of the feature map). There exists p > 0 such that E(e.a)~v [Ø(s, a) (s, a)] = Σ,, 2 μ.I.
We also need ensure that the Q-values can be well approximated by the linear function approxima- tion using feature map Φ(s, a). which is captured next.
Assumption 4.2 (Bounded approximation error). For each n [N], there exists Spprrox 2 such that for all t E N. it holds that E [e (w( m: arg min (w Q (00)
(w..) (t) 7(t) ]
< e
uuppoxx where with =
We denote the average approximation error as Eapprox N En= & 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 C2 > 0 such that for all E [M] and t E N,
27
it holds that E (1,))=a)))) induced by any policy from initial state distribution p.
h (s.a)
S Cs. where hº (s, a) is the state-action visitation distribution
du (s.a)
Note that if we choose v(s, a) > for all (s. a) E Sxx 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 (informal)). Let = E in FedNAC. Denoting g(() & E e and fit) = fuu as the average policy. Then under Assumption 3.1, 4.1, 4.2 and 4.3, with appropriately chosen learning rates and B, as long the number of actor iterations satisfies
2/4
0²
T Z max
33/2 - 7)177411 - 033/22 a(1 - 7) 53/4(1 - 01338(1 7)7/88338
(1 -1- 7) - σ)
and the number of critic iterations satisfies K = (1-bpe) ) it holds that
(p( T
Σ vp ft)
(p)
Eopprox
(26)
1-7
In the server-client setting when 0, to reach (26), it suffices to choose =0=0-
(T-7)e and
K ==0 <=0 leading to a total sample complexity of KT/(1 - 7) 0 (I--))-T)
per
agent, and T O (centralized) Q-NPG established in [YDG+22] with single agent. On the other end, in the fully decentralized setting when is not close to O, FedNAC requires O (1=1))774474(-00))7
(1~ン)E) rounds of communication. The sample complexity matches that of
samples rounds of communication reach (26), for sufficiently small e. 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.
for each agent and O (2001ー1))7/000)))
Conclusions
This work proposes the first provably efficient federated NPG (FedNPG) methods for solving vanilla and entropy-regularize 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.
Acknowledgments and Disclosure of Funding
The work of T. Yang, Cen and Y. Chi are supported in part by the grants ONR N00014-19-1-2404 NSF CCFF-1001 199, CCF-2106778, AFRL 248750--0-220504 and a CMU Cylab seed grant. The work of Y. Wei supported in part by the the NSF grants DMS-2147544/2015442 DMS-2143215, CCF-2 106778, and the Google Research Scholar Award. The work of Y. Chen is supported in part by the Alfred Sloan Research Fellowship, the Google Research Scholar Award, the AFOSR grant FA9550-22-1-011
CAREER award
the ONR grant (00014-22-1-2354 and the NSF grants CCF. 2221009 and CCF-1907661. S. Cen is also gratefully supported by Wei Shen and Xuehong Zhang Presidential Fellowship. Boeing Scholarship, and JP Morgan Chase PhD Fellowship.
10

---

References
[AKLM21] A. Agarwal, S. M. Kakade, D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431-4555 4450, 2021.
[ALRNS19] Z. Ahmed, N. Le Roux, M. Norouzi, and D. Schuurmans. Understanding the impact of entropy on policy optimization. International Conference on Machine Learning. pages 151-160, 2019.
[Ama98] S.-I. Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):251-217 1998.
[AR21] A. Anwar and A. Raychowdhury. Multi-task federated reinforcement learning with adversaries. arXiv preprint arXiv:2103.06477. 2021.
[ARB+19] 19] M. Assran, Romoff, N. Ballas, Pineau, and M. Rabbat. Gossip-based actor- learner architectures for deep reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
[BM13] F. Bach and Moulines. Non-stronglyycoonex smooth stochastic approximation with convergence rate o (1/n), Advances in neural information processing systems, 26, 2013,
[BR21] J. Bhandari and D. Russo. On the linear convergence of policy gradient methods for finite MDPs. In International Conference Artificial Intelligence and Statistics, pages 2386-2394. PMLR, 2021.
[BSGL09] S. Bhatnagar, R. S. Sutton, M. Ghavamzadeh, and M. Lee. Natural actor-critic algo- rithms. Automatica, 2447122242-2 2009.
22c)+ S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563 2552278888277 2022.
[CCC+22b) S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 7064):2533.2578 2022.
[CCDX22] S. Cen, Y. Chi, S. S. Du, and L. Xiao. Faster last-iterate convergence of policy optimization in zero-sum Markov games. In The Eleventh International Conference Learning Representations, 2022.
[CFGW22] J. Chen, J. Feng, W. Gao, and K. Wei. Decentralized natural policy gradient with variance reduction for collaborative multi-agent reinforcement learning. arXiv preprint urXhv:2209.02199 2022.
[CWC21] Cen, Y. Wei, and Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34:77952-27964 2021.
[CZC21] Z. Chen, Y. Zhou, and Chen. Multi-agent off-policy TDC with near-optimal sample and communication complexity. In 2021 55th Asilomar Conference on Signals, Systems, and Computers, pages 504-508. IEEE, 2021.
[CZGB21] T. Chen, K. Zhang, G. B. Giannakis, and T. Başar. Communication-effciieen policy gradient methods for distributed reinforcement learning. IEEE Transactions on Control of Network Systems, 9(2)9177922, 2021.
[DAW11] J. C. Duchi, A. Agarwal, and M. J. Wainwright. Dual averaging for distributed opti- mization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3):592 606, 2011.
[DLS16] P. Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120-136, 2016.

---

[EL21] B. Eysenbach and S. Levine. Maximum entropy RL (provably) solves some robust RL problems. In International Conference on Learning Representations, 2021.
[ESM+ 18] L. Espcholt, H. Soyer, Munos, K. Simonyan, V. Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, I. Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted leaorelearner architectures. In International conference on machine learning. pages 1407-1416. PMLR, 2018.
[HJ12] R. A. Horn and C. R. Johnson. Matrix analysis. Cambridge university press, 2012.
[KakO1] S. M. Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
[KDRM22] S. Khodadadian, T. T. Doan, J. Romberg, and S. T. Maguluri. Finite sample analysis of swo-time-scale natural actor-critic algorithm. IEEE Transactions on Automatic Control, 2022.
[KJVM21] S. Khodadadian, P. R. Jhunjhunwala, S. M. Varma, and S. T. Maguluri. On the linear convergence natural policy gradient algorithm. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 3794 3799. IEEE, 2021.
[KMP12] S. Kar, J. M. Moura, and H. V. Poor. Qd-lcarning: A collaborative distributed strategy for multi-agent reinforcement learning through consensus. arXiv preprint arXiv:1205.0047 2012.
[KSJM22] S. Khodadadian, P. Sharma, G. Joshi, and S. T. Maguluri. Federated reinforcement learning: Linear speedup under Markovian sampling. International Conference on Machine Learning, pages (0997-11057. PMLR, 2022.
[Lan23] G. Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 198(1):1059-110 2023.
[LCCC20] B. Li, S. Cen, Y. Chen, and Y. Chi. Communication-eficient distributed optimization in networks with gradient tracking and variance reduction. The Journal of Machine Learning Research, 21(1):7331-738
2020.
[LLZ23] G. Lan. Li, and T. Zhao. Block policy mirror descent. SIAM Journal on Optimization, 33(3):244122388. 2023.
[LO08] I. Lobel and A. Ozdaglar. Convergence analysis of distributed subgradient methods over random networks. In 2008 46th Anmual Allerton Conference on Communication, Control, and Computing, pages 353-360. IEEE, 2008
[LWA +23] G. Lan, H. Wang. J. Anderson, C. Brinton, and V. Aggarwal. Improved communication efficiency in federated natural policy gradient via admm-based gradient updates. arXiv preprint arXiv:23100 19807, 2023.
[LWCC23a] G. Li, Y. Wei, Y. Chi, and Y. Chen. Breaking the sample size barrier in model-based reinforcement learning with generative model. Operations Research, 2023.
[LWCC23b] G. Li, Y. Wei, Chi, and Y. Chen. Softmax policy gradient methods can take exponential time to converge. Mathematical Programming, pages 1-96, 2023.
[LZZ+17] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017.
[MA22] M. M Alshater.
Exploring the role of artificial intelligence in enhancing academic performance: A case study of chatgpt. Available at SSRN, 2022.
[MBM+16] V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and Kavukeuoglu. Asynchronous methods for deep reinforcement learning. In Interna- tional conference machine learning, pages 1928-1937 2016.
12

---

[MP95] R. D. McKelvey and T. R. Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38, 1995.
[MXSS20] J. Mei, C. Xiao, C. Szepesvari, and D. Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning. pages 0820-6829, PMLR, 2020.
[NNXS17] O. Nachum, M. Norouzi, K. Xu, and Schuurmans. Bridging the gap between value and policy based reinforcement learning, In Advances in Neural Information Processing Systems, pages 2775-2785, 2017.
[NO09] A. Nedic and A. Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions on Automatic Control, 54(1))48-61, 2009.
[NOR18] A. Nedić, A. Olshevsky, and M. G. Rabbat. Network topology and communication- computation tradeoff's in decentralized optimization. Proceedings of the IEEE, 106(5):953-97,, 2018.
[NOS17] A. Nedic, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed optimization over viry-ng graphs. SIAM Journal Optimization, 27(4))2597- 2633, 2017.
[OPA + 17] S. Omidshafici, J. Pazis, C. Amato, J. P. How, and J. Vian. Deep decentralized multi- task multi-agent reinforcement learning under partial observability. In International Conference on Machine Learning, pages 2681-2690. PMLR, 2017.
[PN21] S. Pu and A. Nedić. Distributed stochastic gradient tracking methods. Mathematical Programming, 187:409-453 4500099--552220 2021.
[PPO8] K. B. Petersen and M. S. Pedersen. The matrix cookbook. Technical University of
Denmark, 7155:5110, 2008
[Put14] M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[QL17] G. Qu and N. Li. Harnessing smoothness to accelerate distributed optimization. 1EEE Transactions on Control of Network Systems, 1455 2017.
[QZLZ21] J. Qi. Zhou, L. Lei, and K. Zheng. Federated reinforcement learning: Techniques, applications, and open challenges. arXiv preprint arXiv:2108. 2021.
[RTR+23] M. M. Rahman, H. J. Terano, M. N. Rahman, A. Salamzadeh, and M. S. Rahaman. Chatgpt and academic research: review and recommendations based practical examples. Rahman, M., Terano, HJR, Rahman, N., Salamzadeh, A., Rahaman, S.(2023). ChatGPT and Academic Research: A Review and Recommendations Based on Practical Examples. Journal of Education, Management and Development Studies, 3(1):1-12, 2023.
[SHM20) L. Shani, Y. Efroni, and S. Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized MDPs In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5668-5675, 2020.
[SLA+15] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897, 2015.
[SWD+ 17] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06344 2017.
[WCYW19] L. Wang, Q. Cai, Z. Yang, and Z. Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01150 2019.
[WHM+23] J. Wang, J. Hu, J. Mills, G. Min, M. Xia, and N. Georgalas. Federated ensemble model-based reinforcement learning edge computing. IEFE Transactions on Parallel and Distributed Systems, 2023.
13

---

[WJC23] J. Woo, G. Joshi, and Y. Chi. The blessing of heterogeneity in federated q-learning: Linear speedup and beyond. arXiv preprint arXiv:2305.106977 2023.
[WKNL20] Н. Wang, Z. Kaplan, D. Niu, and Li. Optimizing federated learning on non-iid data with reinforcement learning. In IEEE INFOCOM 2020-IEEE Conference Computer Communications, pages 1698-1707. IEEE, 2020.
[WP91] R. J. Williams and J. Peng. Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3):241-26) 1991.
[WSJC24] J. Woo, L. Shi, G. Joshi, and Chi. Federated offline reinforcement learning: Col- laborative single-policy coverage suffices. In Forty-first International Conference on Machine Learning, 2024.
[Xia22] Xiao. the convergence rates of policy gradient methods. The Journal of Machine Learning Research, 23()):1887-11222, 2022.
[XWL20] T. Xu, Z. Wang, and Y. Liang. Improving sample complexity bounds for actor-critic algorithms. arXiv preprint wrXiv:200.112956 2020.
[YDG+22] R. Yuan, S. S. Du, R. M. Gower, A. Lazaric, and L.. Xiao. Linear convergence of natural policy gradient methods with log-linear policies. arXiv preprint arXiv:2210.01444 2022.
[Y]S+20] T. Yu, T. Li, Y. Sun, S. Nanda, V. Smith, V. Sekar, and S. Seshan. Learning context- aware policies from multiple smart homes via federated multi-task learning. 2020 IEEE/ACM Fifth International Conference on Internet-og Cfrrnet-oo-Three of-Things Design and Implemen- tation (IoTDI), pages 104-115. IEEE, 2020.
[ZAD*21] S. Zeng, M. A. Anwar, T. T. Doan, A. Raychowdhury, and J. Romberg. decentralized policy gradient approach to multi-task reinforcement learning. In Uncertainty in Artificial Intelligence, pages 1002-1012. PMLR, 2021.
[ZBW+20] F. Zerka, S. Barakat, S. Walsh, M. Bogowicz, R. T. Leijenaar, A. Jochems, B. Miraglio, D. Townend, and P. Lambin. Systematic review of privacy-preserving distributed ma- chine learning from federated databases in health care. JCO clinical cancer informatics, 4:184-200, 2020.
[3CH+23] W. Zhan, S. Cen, Huang, Chen, J. D. Lee, and Y. Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. SIAM Journal on Optimization, 13(2):1061-109 2023.
[Z9 H. Zhuo, W. Feng, Y. Lin, Q. Xu, Q. Yang. Federated deep reinforcement learning, arXiv preprint arXiv: / /90100827, 2019.
[ZLK*22] R. Zhou, T. Liu, D. Kalathil, P. Kumar, and C. Tian. Anchor-changing regularized natural policy gradient for multi-objective reinforcement learning. Advances in Neural Information Processing Systems, 35:13584-13596 2022.
[ZM10] M. Zhu and Martínez. Discrete-time dynamic average consensus. Automatica, 46(2):322-329, 2010.
IZRY 23] F. Zhao, X. Ren, S. Yang, P. Zhao, R. Zhang, and X. Xu. Federated multi-objective reinforcement learning. Information Sciences, 624:811 1--811 2023.
14

---

A Related work
Global convergence of NPG methods for tabular MDPs. [AKLM21] first establishes (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 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 &o policy evaluation errors. The iteration complexity of NPG methods 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, MXSS20J. [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, 23, L.Z233. 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, BR21J. [ZLK 22] developed an anchor- chanhing 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 complex- ity of variety of natural actor-critic methods (NACs) are extensively studied in the litera- ture [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 convergence rate of / D()/VT). [YDG+22) weakens some of its assumptions and improves the convergence rate to O(1 and gives the ((1/s")) 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 variety of settings being set forth for distributed and federated RL. [MBM+ + 16, ESM 18, ARB * 19, KSJM22, WJC23] focused on developing feder- ated versions of RL algorithms accelerate training. assuming all agents share the same transition kernel and reward function; in particular, [KSJM22, WJC23, WSJC24) established the provable ben- efits of federated learning in terms of linear speedup. More pertinent to work, [ZRY+23, AR21] considered the federated multi-task framework, allowing different agents having private reward functions. [2RY+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 adver- sarial agents. Recently [LWA+223 discussed how 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 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 special case of their setting recovers ours. However, the convergence rate developed in 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. Farly 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] track the gradient of the global objective function, is popular method to improve the convergence speed [QL17, NOS17, DLS16, PN21, LCCC20).
B Additional Discussion
B.1 Application Related to Federated Multi-task RL
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 follows.
15

---

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. the healthcare example, an optimal treatment over different hospitals better adapts to variations in patient characteristics.
Resource optimization: training 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 collabora- tive approach enhances learning efficiency and scalability while preserving data privacy, particularly in settings where each hospital has limited access patient information.
Below we provide more application scenarios of our setting.
1. To enhance ChatGPT's performance across different tasks or domains [MA22, RTR 23R+ one might consult domain experts to chat and rate ChatGPT's outputs for solving different tasks, and train ChatGPT in 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 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 Acrial Vehicle (UAV) Patrol Mission, each unmanned acrial vehicle (UAV) patrols only in 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 character 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 provide efficient algorithms with global convergence guarantces for federated multi-task RL.
B.2 Theoretical Contribution
In this section, 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 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 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 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 in the standard decentralized optimization literature despite the nonconcavity.
Besides, due to the lack of global information sharing, care needs 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 entropy-regularized NPG is to form the 2nd-order linear system in Eq. (46) in [CCC+22al, while in corresponding analysis,
16

---

4theorder 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
C Omitted Algorithms
C.1 Federated NPG (FedNPG) with entropy regularization
We record the entropy-regularizze FedNPG method in Algorithm 2 here due to space limits.
Algorithm 2 Federated NPG (FedNPG) with entropy regularization
Input: learning rate 1) > 0, iteration number T E N,, mixing matrix W E N regulariza-
tion coefficient т > 0.
2: Initialize: π (0) T = Q
3: for 0, 11 do
4: Update the policy for each (8, a] E E A:
log π (als) w
(1-1--7)
7/7 -T)))
log TT (o
1-7 (1,0))))) - log ())
7
(1,
1-7)
(27)
where (m))= exp W ((1- log (" + - (T))
5: Evaluate Q.+11)
6: Update the global Q-function estimate for each (s, E S A:
((t w (s. ((+))))))))))) a) - Q. (s,
(UT)
Q-tracking
7: end for
C.2 Development of FedNAC
For any policy we let dh, denote the discounted state visitation distribution of π given an initial state so E i.e.,
20
S (s) = (1 (1-))
Σ
y P((s s s|so).
(28)
For distribution A(S), we define ds(s) Eop [d (s)]. We also define the state-action visitation distribution d7
(ss = =(1 -1))
Σ
/P = s,a, = alsu)
(29)
Furthermore, we extend the definition of d% by specifying the initial state-action distribution v A(S A) and define
d, =
E
P((ss a,a, al sol ao)
(30)
(80.0g) Ao
Our proposed federated NAC method FedNAC could be seen as a decentralized version of Q-NPG method [AKLM21, 22], which we briefly review follows.
Q-NPG method. Q-NPG is sample version of NPG with function approximation which 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 (t) for minimizing the function approximation error ((w, Q ) (see (25)), the Q-NPG update rule g(++1) {(() + (t) when plugged in
17

---

parameterization (24), results in the following policy update rule when we set a = 77/(1 - -)):
n T (s, ()))))
(als) x (als) exp
(31)
1-7
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 whose subroutines are written in Algorithm 4, 5. In each iteration t of FedNAC, each agent updates the critic parameter w! locally using Algorithm which aims minimize f(w, Q di by stochastic gradient descent. Note that since we don't know the Q-function Q! in the gradients, we need invoke Algorithm 5 [YDG+ 22, Algorithm 3] give unbiased estimate (s, a), where (s, a) is sampled from ) (ef. Theorem E. As a consequence, in line Algorithm 4, we have
E
ii Q", [bte]
Q aes).
(32)
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 3, discounted factor [0, 1)
2: Initialization: initial state- aateonction distribution v, actor parameter g()) ($) (0)T
(0)T
)
EN
RNXx, xp (-1) = w(11) = 0 E R Nxp
do 4: Critic update: wn. Critic(K, v. Eth 3, rn), n E [N] (Algorithm 4)
3: for 0
5: Update the critic parameter for estimating the global Q-function:
h W (nt (t-1) w(t) ((t-1))
(33)
6: Actor update:
(((+1) W (5 - azh
(34)
7: end for
Algorithm 4 Critic(K, n, E. 7, r): sample-based regression solver to minimize E(w, Q d(l))
Initialize: critic parameter Wh E R
2: for k = -.. ... K do
3: Sampling: (sk, (x). @a (sk, ax) =Q-Sampler(v, Je: r) (Algorithm 5)
4: Compute the stochastic gradient estimator LQ:
Villir QT, dds) = [ Ø(Sk, an) - Q7 (5M, ax)) 0(8,, ax)
(35)
5: Critic Update: Wh+1 = Wi u (( Q-,
6: end for
7: Output: Woul 1/2 > 20
D Convergence analysis of FedNPG
For technical convenience, we present first the analysis for entropy-regularizee FedNPG and then for vanilla FedNPG.
18

---

Algorithm 5 Q-Sampler(us, 7,
1: Initialize: (su. ao) ~ v, time step h, t = O, variable X Bernoulli(y)
2: while X = do
3: Sample S1+11 ~ P(1sshas))
4: Sample 01+1 (-188++1)
5: h+h++
6: X ~ Bernoulli())
7: end while
8: Set uo(ss,,))) r(sh, an), X Bernuul(ty), f
9: while X = do
Sample S1+1 P(-|s), at)
11: Sample ac+1 ~ ((+15(+1)
12:
("((Sh, ah) Qn (sh, an) a(44)1,
13:
++t+1
14:
X Bernouli(y))
15:
end while
Output: an) and Q3 (sh;an)
D.1 Analysis of regroii-re FedNPG with exact policy evaluation
To facilitate analysis, we introduce several notation below. For all 2 0, we recall ((1) as the normalized geometric mean of {mT)) (t) Ine[N]:
N log /T
(1)) softmax
(36)
n=
from which we can easily see that for each (s, E S x A. (als) x I (als)) We
Nh
denote the soft Q-functions of ((1) by !
Q
(37)
Q
In addition, we define Q
E
RIS|AA and
IR
SI
as follows
Q
(38a)
N
==
N
Q Q
(1)
(t)
Q
(38b)
N
==1
(
1
VTCC
(38c)
N
For notational convenience, we also denote
7/T
(39)
Following [CCC+22b), we introduce the following auxiliary sequence (E(t) = =E(()) [ I,,..,.... each recursively defined as
<(t))
|xpp (Q; 1/7)ll
((s.)) (0)) =
7 (a)(()))
(40a)
exp E log (0)
(-1s)
log logg((+t) ((++) = W (allog (1)) (8, + ())
(40b)
19

---

where T(0 (s, a) updated via (16). Similarly, we introduce an averaged auxiliary sequence RIS|IA] given by
(5"
Exx::
(s, [ (s.-)ll1 - (als) log " (s.a) log " (s,a) + (1 - (s.
(41a)
(s.a)/T.
(41b)
We introduces four error metrics defined
2 (t) = u (1)
10o.
(42a)
22 () ||/(0 || ao
(42b)
22 = || T log " 1l:0
(42c)
min 20 = max 00 0
(s,0) (8, - rloge ( (8,)))
(42d)
where (0)), v(0) E RISIA are defined as
(s, a) = | log
(8, (s) - asl2)2
"og
(43)
1 (s, a) = (s, @ (s,
(44)
We collect the error metries above in vector 12 Rt:
S2 (2 , .2!"
(45)
With the above preparation, we are ready to state the convergence guarantee of Algorithm 2 in Theorem D.I below, which is the formal version of Theorem 3.6.
Theorem D.1. For any N E N4, T > 0,7 E (0, 1), there exists > 0 which depends only on W,T,T,, T, [A), such that 0 < 1j S 170 and σ > then the updates of Algorithm satisfy
1 (1) 1: - 2>p(nn)(| 1000
(46)
log पF - log log 11 11,m S
(47)
where
Tn 3 0
p(n) S max
<1.
2 4
Moreover, the consensus errors satisfy:
Vn E [N]:
|| ||oog - log (1)||| 11.0 S 2pp(n)
2
(48)
The dependency of 7/u on N, 7, T. o, [A] made clear in Lemma D.3 that will be presented momen- tarily in this section. The rest of this section is dedicated to the proof of Theorem D.I. We first state key lemma that tracks the error recursion Algorithm 2.
Lemma D.2. The following linear system holds for all 2
na
O
0 TyaN 1-y a)
(1++1) <
So
(1
DM I-y
(2+7)rMN I-y
(49)
(1 M
(1 - 0.7 +
M
α
m:A(n)
where we let
1 - a VNM)
S MVN
2a 20
(50)
and
M 1 + 27 - log LAI -7.
(1-
20

---

In addition, it holds for all t 2 0 that
0 (t) Qi x
- 5
(1)
+
+70
(51)
2
|| log (1) - log mill _ (/
(52)
7
Proof. See Appendix F.I.
Let p(n) denote the spectral norm of A As (2) 2 0, it is immediate from (49) that
s2 |2 - p(n)' 12 12
and therefore we have
0 07 0:11a- 2 11 I 2yp(n)) | ||
and
log (1) log n; 11 S - ( I0 S =n 112-
remains bound the spectral radius p(1).. which is achieved by the following lemma.
Lemma D.3 (Bounding the spectral norm of A (n)). Let
(1 - 71 - o)²r
5 = ST + 10Mc -
(53)
7) + (1- (1-0)372/16)
where So = .VN 2+ V2N 2+ + MVN , c == MN/(11 - 7)). For any N E N+,7 0,y (0.
if
0 O< = min {
1 1-2 .s.
(54)
then we have
p(n) S max 33+a 1 (1 -1- o07 + } < 11.
(55)
2
Proof. See Appendix F.2.
D.2 Analysis of entropy-regullrized FedNPG with inexact policy evaluation
We define the collection of inexact Q-function estimates
and then the update rule (Ur) should be understood as
(s = w (s, a) + ( (s,a) - o (s,
(56)
in the inexact setting. For notational simplicity, we define en E IR as
Cn == max rE[T]
[N],
(57)
and let e = (e ,e,) Define z
the approximation of
Q as
TT.
(58)
With slight abuse of notation, adapt the auxiliary sequence {E Je-o... to the inexact updates 50 (s. = ||exp (s. (0) (als),
(59a)
(1+1) (8, a) = [(' exp (1 a) きt (9,
ES 120.
(59b)
21

---

In addition, we define
2 = (0
(60a)
2 = (0
(60b)
26 Q logg 6
(60c)
1000
2/ = max 0, - min (s, rlog?
logg 10 (s.0))
(60d)
where
(s,
log (5) as) log (s, (s,
(61)
(8, a) = T (s, (8, a) a))
(62)
We let (2) be
2 = (n 220 .292'
(63)
With the above preparation, we are ready to state the inexact convergence guarantee of Algorithm 2 Theorem D.4 below, which the formal version of Theorem 3.8.
x(t) Theorem D.4. Suppose that 9 are used in replace of Q in Algorithm 2. For any N NN+T > T. a. [A], such that if nl and
0,7 (0. there exists no 0 which depends only N.Y.T.
1 - σ > 0, we have
|0 (1) - 0+
27
p(n)*
(2(0)
+ C2
max
Q
qr,
(64)
ME(M)
|oog oे - log (1)
S
2
p(n)*
(0)
+ C2
max me (N),AEE
|
47.3 Ph
-0
(65)
Moreover, the consensus errors satisfy:
Vn E [N]: |olg (1(') log क
2
(p(n))
(200)
C2 max NE(N
1
(t)
(t)
(66)
where p(1)) S max
za
1 is the same as in Theorem D.I, and C2
2
oVN(2(17)4 MM 22)
(1-1)(1-(0)
From Theorem D.4, we can conclude that if
|
(1-7)(1 p(n))E
max [E
S
(67)
27 (oVN(2(1-)) + MvNn) + 222 + 1/7)
then inexact entropy-regularin FedNPG could still achieve 2s 2c-accuracy (i.c. - - Q²
25)
within max { 2 1
27 |
Tay I-o log
iterations.
Remark D.5. When 17 = T7o (cf. (54) and (53)) and 7 S 1, the RHS of (67) is of the order
o (1 (1-7)TTUE
(1 (7pp + - (1-7))>(1-03} - + (1
7(72+0 ( -
7)2 (1)))))
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.
22

---

Lemma D.6. The following linear system holds for all t 2 0:
ov N 2 2
MyNn
((+1) <A())
1-y
|elloo
(68)
=:b(n)
where A(1i) is provided in Lemma D.2. In addition, it holds for all b 2 0 that
Q - Q: 5 (1)
+ 7
(69)
2
|| log (+)) - log क. vil _ 22
(70)
Proof. See Appendix F.3.
By (68), we have
V 20 S A(n)'
Σ
which gives
12 S p(n)
(2:00
+ Σ p(n) 6- (b(1))2 lelloo
==1
S s(nn)
(2
OVN
N (2(1 - 7) M Nn) + 2y² + 11T |ee|
(71)
(1 - (1 - p(n))
Here, (71) follows from [|6(n)]22 -
[[b(n)]
= M
||ll and
Ei p())== < 1/(1 - p(n))- Recall that the bound on p(n) has already been established in Lemma D.3. Therefore 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.
D.3 Analysis of FedNPG with exact policy evaluation
We state the formal version of Theorem 3.3 below.
(0) Theorem D.7. Suppose all nn in Algorithm I are initialized uniform distribution. When
O<nsm= (1 (1-o)?(1-2)
8(1+ N(1+2)/NN0*
we have
T-1 Σ
v < (i
log |A|
8(1 ((1+7) ((1+))22N00²
(v())-
+
+
?
(72)
T t=
(1 7)T
n/
(1 (1-
for any fixed state distribution p. Furthermore, we have
Vn [N]
|og (0( log (0)
S
32No 3(1 - 7) - -a)
1)
(73)
The rest of this section is dedicated to prove Theorem D.7. Similar to (37), we denote the Quuuctioons of (+) by (1)
QT 0
(74)
Q (
N
23

---

In addition, similar to (38), we define Q
Q
RRISIAA
and p
E IR SI follows
(75a)
n=
N
1
Q
Q
(75b)
N
n=1
N
T =
V=
(75c)
N
==1
Following the same strategy in the analysis of regropyy-rguularized FedNPG, we introduce the auxiliary sequence (E(0) = (El", ... , E Nx| |AI} recursively:
< (s.a) =
(als),
(0)
(76a)
1 E log Tn 10) (115)
exp
N
log log ((t()) (s.a)) W ( (s. + "
1-7 (s,)a)
(76b)
as well as the averaged auxiliary sequence (5"h E RI
(s, = (als),
(77a)
log 7 ((t))) (s.a) log (s. 1 1-7
" (s,a). V(s,a) (
S A, t20.
(77b)
As usual, we collect the consensus errors in a vector ( = (1| (b100(000))0)))) where (0,,,(0) e R|SS|-4 are defined as:
u 19 (s, a)= = log (0) a) - log E (s,a)IN(12 1 (s, a) = (s, a) Tt (s,a)lll1
(78)
(79)
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
0
-
( <
Jo a (1
(It))rN
Nn
2000 +
(80)
(1-7)* 7)²
(I-7)* 11
=:B(n)
=dd(r)
for all t 2 O, where
J = 201 VN. 71-
(81)
In addition, we have
((+1)( S (n) +
2(1 7)7
// /||1|(0)|| - (v) - [''
(82)
(1 7)-
where
(n) E Bands
(-1s) (
- I-7 -
" r v'0)(())) (d)) 40
(83)
Moreover, when S 7h, we have
en [N]: |log m(()) log (())
3 5) (2000
+ 32Na
2 g
2 3(1 - 71 - o)"
?
(84)
Proof. See Appendix F.4.
24

---

Note that when all n.. indicates (73) in Theorem D.7.
(0) in Algorithm 1 are initialized as uniform distribution, 12() 0 and (84)
Step 2: bounding the value functions. Let petp5 E IR? be defined as:
<10-:000000000000000000001111111 (---0(1-- an (1-))) Jo
p(n) = (p)(m) (ptt))
= 2(1 + 7>y
(85)
7)
on² (H00000----000V\\><>>>>>>y>
the rationale for this choice will be made clear momentarily. We define the following Lyapunov function
( (n) = (1) (n) + p(n)
v2 0,
(86)
which satisfies
z (()) (((+1)()))
(1) + p()) (1(1+)
(1)) + 2(1 + 7)7
(1 18-7) 7)4 //| 11 - 17 (v-()))V''
- (0)) + +p(1) (B(1)2(() + +d(n)
= (n) + p(n) T (B(T) 1) + (2 7)7
(1 (1-))))00))
11 0) (2 - 17 (v*(p) - vo)
+ (1)
(87)
(1-7)1
Here, the second inequality follows from (82). One can verify that the second term vanishes due to the choice of p(n):
p(n) T (B(n) I) (2(1 (2(1+)) 7)7
(1- (1- n.0) = (0.
(88)
Therefore, we conclude that
(T(p) - -7() (p) (p)5 (n) (((+))())
+ p2((1) (1 + 77>No
7
(1 7)²
Averaging over = ... 1,
1
V (p) (p) - -V''
T
t=0
1 (n) - (n)
2(1 + 7)27 +
No²1²
rfT
(1 - 7)8
- o- - (utp
02J
(89)
Step 3: simplifying the expression. We first upper bound the first term in the RHS of (89). Assuming uniform initialization for all o in Algorithm 1, we have [x( Il.
(0)
||
0, and
[KL (T (-1s) || || (-1s)) S log |A|-
E Banay
Therefore, putting together relations (86) and (221) we have
(1)) (n)
(m)
log [A| 1 7 p(n) (p(n))z90) /n+ 1 1-7
v*
log |AI
(((5)) T(I 71) (90)
+
T/T Tn
Tn
To continue, we upper bound the second term in the RHS of (89). Note that
(1 (1-o)(1-3)) (1 73
2(1 2)+
which gives
(1 (1+7)/NN0²
1 o
<
(91)
(1 (1-7)3
2
25

---

Thus we have
(1--)(-------//Woood((11----- σ) - -Jo'n
- Jo
21 (11-))110)/44
(92)
where the first inequality follows from (91) and the second inequality follows from the definition of ?h and J. By (92), we deduce
2(1 + 7 (1 7) -1-7)) (1- - (1 (LL+)//Noon/CCC >1 Jo
2
8(1 + 7
(1 (1-7)9 o)2 n?,
(93)
and our advertised bound (72) thus follows from plugging (90) and (93) into (89).
D.4 Analysis of FedNPG with inexact policy evaluation
We state the formal version of Theorem 3.5 below.
=h Theorem D.9. Suppose that qu are used in replace of Qn" th in Algorithm Suppose all T in
(0)
Algorithm I set to uniform distribution. Let
(1 (1-0)²(1-7)) 7)
0 <<ns>=
8(1+ 7(1+7)NNNo2
we have
Σ (V
- p (o)
(d
log|A|
8(1+7) 7(1+
- (1- T/T
(1 7) - -0)2
+
8(1 + 7)r
Non
(1 + 1 +
max
Q
(1)
7)5(1 o)²
(1 - 7)3
(1 - 7)3
ne(N).tE(T]
for any fixed state distribution p. Furthermore, we have
( No
Vn E [N]:
log (1) - log (t)
3(1 ((1-o)
32
(1- VNo
TvVN (1 (1-
+1
nE(N))eE(2]
max
Q
(t)
9n
(t)
(94)
We next outline the proof of Theorem D.9. With slight abuse of notation, again define en, RR as
6n == max
n [N],
(95)
rE(T]
and let (ei,... ,,,) T. We define the collection of inexact Q-function estimates
(t)
01
IN
and then the update rule (16) should be understood as
( (s, a) = W (s. (+t (s, ((00))))))
(96)
the inexact setting. Define ((t), the approximation of Q19 as
N
g(t)) =
4n
(97)
N
n=
26

---

we adapt the averaged auxiliary sequence (c E IR A1 to the inexact updates as follows:
{s, ()) a) (alss,
(98a)
" (s, (s. exp exp
7 (1-
V(s,a) Ex 020.
(98b)
As usual, we define the consensus error vector as (2 = (1|=(()1| a0 (/,l//0))) 1o0) where u0)), ,(()))))))))))))))))))) RISIIA are given by
u 0 (s.a) = log 5 (0 (s, - -log 2 (s,
(99)
0 (s,a) ( a) (s,
(100)
The following lemma characterizes the dynamics of the error vector 22(9, perturbed by additional approximation error.
Lemma D.10. The updates of inexuct FedNPG sutisfy
(+++)) B( +d()) <B())(()+()))
(NNo (aLtghay + +2) |eel
(101)
c((n)
In addition, we have
((1+)) S (n) + 2(1 + 7)7 (1 11-7) 7) 9
(1 - 7)2 g) ||ello0 - 19 (V (V* (o)) (102)
27
oo
where (1)(1) is defined in (83). Moreover, when y S Th we have
o + 5)
[0: + 32
3(1 0) ( No
(1- VNo ( 1V/N
vn E [ log ( (1) log (())
2
(1- +1 +1 llellx)
8 8 2
(103)
Proof. See Appendix F.5.
Similar to (87), we can recursively bound (n))r) (defined in (86) as
((++D()) ((++)) (n) + p(n) (++1))
(102)
(n) + 2(1 +7)y
(1 7)4 7 (0(0
2n
|ell - (v(vv())-V")
(v(")) (0)
100 + (1 - 7)2
+ p(n) T ((())2(() + + + c(())
= + p(n)T T (B(n) - +)+ 22 + 7)7
(1- 17, m000
(0 - 17 (v - -v(((p)
(0.0) (88)
+ P2((1) (1 + 7 + Pa(n)VNo (1++))7V
2n
(1-7)3 +2 + (1 7)2
|lel
(1 - 7)a
(104)
From the above expression we know that
((())-(((())) (0) (1+) (n) (((+1((n)
(1+ +p2(1)
(1+ + Pe(n)V/No
2
+
+
|ell
7
(1 (1-
71-7)3
(1 7)
27

---

which gives
T-1
(n) (1))(1))
+ N2
Σ
(p)
p
nT
(1 7)4
+ pa(n)//No
(1+ (1 71-
+
+ (1 7)2
2
lella
(105)
via telescoping. Combining the above expression with (90), (92) and (93), we have
T Σ (1(0)~v'((0)
v log A
8(1+ + 7)
Tn
T(1 7) (1 (1-7)0(1-o))
8(1 7)7
+2 +2)
2
+
(1 - (1- - oo)2 VNo
||ll
(1 (1-7)3
(1 - 7)3 (106)
which establishes (94).
E
Convergence analysis of FedNAC
Let n- an optimal policy and does not need to belong to the log-linear policy class. Fix a state distribution p E A(S) and state-action distribution v. To simplify the notation, we denote df as
d., e'e as d d.ll as del" and define d!! and d!! analogously. We also let Q! denote Q
Define
d4 2 0p= 1 1
1
1 --7
(107)
100
and assume 0,- < co. We also introduce a weighted KL divergence given by
D Egnd, [LL(T [1 (+ss)
(108)
where (L(-1l-) RRAA x RI + R is the Kullback-Leibler (KL) divergence:
f(a) log (((a)
RlAg (L(fll9) = Σ
(109)
g(aa)
aEA
Given state distribution p and an optimal policy n², define state-action measure d"
(s. = ds))) Unifa(a)= d, (s) [A]
(110)
The following theorem guarantees that for any fixed policy ' and state-action distribution
ASS A), the Q-Sampler algorithm (cf. Algorithm 5) samples (s, a) from di and gives an unbiased
estimate Q (s, a) of Q a), whose proof can be found in [YDG+22. Lemma 4].
Lemma E.1 (Lemma 4 in TYDG+221) Consider the output (3h, an) and (= an) of Algorithm 5.
It follows that
1
Eih + =
1 -
P(sh s, a) d= a)
@
(sh, ah = Q" (sh. ap)
28

---

To present the convergence results of FedNAC, we further introduce the following notation, where t IN represents the iteration step in FedNAC:
N
(1 =
W
(111a)
N
n=1
( 1
(111b)
N
( = feC
(11lc)
( = (g
(111d)
Wx.n E arg min l (w, Q%0 d(
(111e)
N
(1)
(1110)
N
km
n=1
For convenience of narration, we introduce the following bounded statistical error assumption.
Assumption E.2 (Bounded statistical error). For all n E [M], there exists E > such that for all I N in Algorithm 3, have
e W Q. . - (w!.. Q Tb)]
(112)
When solving the regression problem with sampling based approaches, we can expect e (11/K). where K is the iteration number of Algorithm 4.
Theorem E.3 (Convergence rate of Critic (Algorithm 4)). For Algorithm 4, let wh 0 and 205'
Then under Assumption 4.1, we have
Wout, Qe, de)] e (w0 de S K
U2p
C2 11(1
Φ 7)
+1) + 111
C2
(113)
1-9 7
7)2
where w arg mig l (,, Q5, Q de).
The proof of Theorem E.3 is postponed to Appendix G.5.
The following lemma provide (very pessimistic) upper bound of C. in Assumption 4.3. Lemma E.4 (Upper bound of Cz). vfs a) for all state-action pairs (s, a) E A, then have
1
C₂ 5
11
2)2 min
Proof. We only need to note that
(
27
(s,
1
E B(
Zu. (s, a)
(s.0)ESxA d (s,
(1
where the last inequality follows from (??).
We give some key lemmas which will be used in our proof of Theorem 4.4.
Lemma E.S (consensus properties). For all E N, we have
(1+1) =
+ (t)
(114)
N
(1)
1
h
(0)
(115)
N
n=1
29

---

Proof. (115) could be obtained directly by using mathematical induction and update rule (33) (note that #1 h(11) = (-11) 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 (01,... [m be a set of m vectors in R., Then for any < > we have
| + xy
|| 11 (1+
(116)
Σ
m
(117)
Lemma E.7 (Lipschitzness of Q-function with function approximation). Assume that r(s, a) e
[0, ()) E 8 x A. For any E. E RR, we have
(Q'e(s,a) (s)(s, S 2C + +7) 71-
((s,))
I1 -El12
(118)
Le
Proof. See Appendix G.6.
For each iteration step in Algorithm let g(1) Σ N
En=1
c(1)
1 We define
2 = E ((0) INE (TT 2
(119)
2 = E 110) - 1 1 (1)T
(120)
We let
N
Estal ==
(121)
N
==1
Eapprox
a approx
(122)
and define 8(0) = V+ -*- (p), where (()) is shorthand for v We give the following perfor- mance improvement lemma.
Lemma E.8 (Performance improvement of FedNAC). Fix a state distribution p. then we have
D(--1) 0 (,8(14)) + (1 - 7) < 005(00
D.
5(0)
+ (1-
+ 2 2VCx(0, +1)
L ||E(0) 11 (()
VEstat +
2 Eapprix +
1-7
(123)
Proof. See Appendix G.7.
Lemma E.9 (linear system). For any E N, we ler (1) =(2(0) (2 have
Then for any Ç
(2(-1)) - C2 +
(124)
where
(1 (1+5)02
a2 1/5)02 +
C C= = -c,))== = (1+ 1/5) 960 L
d² (1 (1+ 5 (1 1/5) (1-9)H
2413a²
(125)
(1=))
and
-(1+1//)) 60? (I-7) (N(Esar + Co + 4L3
s
81
( Ne [1->)
a² ,2NC3
(126)
82
-(117)²))
30

---

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 5 = EX in FedNAC (Algo- rithm 3), let the w(() = O and the critic stepsize 3 = 20% in Algorithm 4. Then under Assumptions 3.1, 4.1, 4.2 and 4.3, when the actor stepsize satisfies
a a o2) /11-))1 (1))
(127)
768V60LQ
where LQ is defined in Lemma E.7, we have
T-1
()()) - 7
Σ
[o)
=
0 + onl p
1
1100 1)00
Vn!
+
T(1 a)a
T
(1 - 02)3/2(1 31
2VC
+1)
640 3072 3T2233CoCC.00
- +1)0aa
+
+ 11
1+ (1 71-7)'1
1-7
2
(1V2p+ 1)03 + 12pu(111)) -1)
(1 (1-))2K
202Cu(0p +1)
3072 Co + 1)02a
20 (0, + 1
+
Eapprox
1-7
(1- (1 - 7/7 VP
(1- 13/2 1// 02)3
(128)
Moreover, the consensus errors could be upper bounded by
E E I
49
15
E
(0)
1 (0)T (0)
640(a, K) 15(1 o2)
(129)
64
64
F
where
1802N
720² L3.N
8(a, K) (1 11-0% 02) - 7)14
(Esut + Capapp)
+
02) ((1 -- + C2) a²
(130)
and
Estat S [1-7)a (1V2p+ + 110% + 22pu(1-10 7))²
4
Remark E.11 (Sample and communication complexity). When o > and
) 61444/321/6 (1 + 0 2/32/300
(1 (1- 2// 02)
T1/3g2/3
follows from Theorem E. that
1 T T
(p)
Σ E
(p)
31/3, 229/6
(D 22/3 (1 1,30
0p 217/331/6 (1 8 2233 (T( D 2/3
T1 7) 17/0 022
(1 (1-
T4/3 - 02 7/6
2 2V 11)
33/2. 4C,213 (110)213311 02)²
237/6 37/6 // 1/6 + (,,
(0)
1-7 +
1+
4/31311 + 1,,)
(1 - o 2 - 7
(1 (1-a8 WKK (1/2p+
2
1)C + 22pu(1 - 7)
2 2/2C +1]
237/6 37/6 1//0 /6 (1) + +1)33884/333110 (()))
1-7
02 5/371/3
approxx
(131)
31

---

Consequently, we need
0² o2)6//2 5(1 - -7) - (1)1-- (1- () 22
1
/1/4
T
=97(111)17/11
and
K= 0 (1- 71
such that (p(p) T Σ (p) X 5 Euper 1-7
In Algorithm each trajectory has
the expected length 1/(1 7)- Consider only the term where e dominates, FedNAC requires
O (1-1)17447//111-1)77 samples for each agent and O (371119)77 rounds of com-
munication.
On the other end. when 0, (128) becomes:
T-1
D ad (U, (1)
(p) (p)
(1 VVR (1V2p+ 1)02 + 22p - -7)
- T(1 7)
20 +1
(132)
apprex
7
Consequently, for any fixed a > 0, when or close to with T o
( (1-1)e and K
FedNAC requires KT/(1- - 7) = [1-7] samples for each agent and
22
rounds of communication such that (²(p)) T Σto B (p)) S
I-y"
E.1 Proof of Theorem E.10
suppose Assumptions 3.1, E.2, 4.1, 4.2 and 4.3 holds. By Lemma E.9 and nonnegativity each entry of C, and (2) where N, it's easy see that
( S CVCV 2 + Vs.
(133)
where Vi is exerted element-wise. In addition, taking expectation on both sides of (123) and using the act that
L3 N
213
E
2
6 Capprox
+
|5500 In 1
2 approx
+ V
(0)
N
we have
BiD.+t11) (++
+ E(D(") (t)
1
+ - 7)a
E(
(1 7)a
2 2VC,(0, + 1)
213 (0
+ 1 1-7
V + 22 +
(134)
We define the Lyapunov function $ (1) as follows:
(1)
( = 0
+ (1-7)a + q V20
(135)
where
2Lov2Cu(00+1)
!1
(1-7)VN
1 1-VI+ /011()cn00/111//00
(136)
42)
2LoyI05(0,
VI+l/aa
(1-9)V
(I-TTF()) -V1+1/(eapa
32

---

It's straightforward to verify that when (= 1-d"
we have the entries in C' (cf. (125)) satisfies
C11 < + 0²
(137)
2
3
11 <
(138)
0²
y(--))(1--0") 12v/allq
Moreover, from I
we deduce
3 02
C22 S
(139)
4
which gives
3 02
1 0²
Vo22 2
2
(140)
4
8
Also note that a (I-a²)² /orr)""1(110) (1-2) yields
7 Lo
(1- ( 022
V(1 + 1/()e210a S
2
which together with (140) and the fact - V1 + 2 L-o indicates Q1 92 > 0 and that
S (1 (1-o²) - N
(141)
11oa
42 < 01-02)5/2(1 N
(142)
Thus by (133) and (134) we have
B ((+1))
g (x++1)
+
+ + V22
(1 -)a
D 1
S 1 +
11 + [VCVR2 + v8)
7)xx
2 2VD +1
2L3 (00)
VEEsmr + 22 V
1-7
N
(2 + +1) +11.0) 0)
= Φ +
q TVC-- +)+
S200
(1 11-
=(0,0)
2V +1)
+ +02282 (Vensl + *v 22
(143)
1-7
which gives
2/C +1) (Veani + 22 (pprro))) + 822
B < (0) (++1)
(144)
1-
Summing the above inequality over /. = .T - 1 and divide both sides by T, we have
T-1 (()) (()) (0, +1)
Σ
B(8(9)
(Vensl Estal + / 25 2 922822
(145)
T
1-7
Since
1
7200
82 5 (1 - [1) - =
(Estat + CpEappru)) +
(1 (1=7) - -02) ((1 ((1-7) + +C2) a², (146)
33

---

and
(0) x(t) <
1())
D
+
D 10
16 16V2LQvCo(0p +
( (Varo)
+ 8V
v1 o² (2
1-9 (1 7)a
(1 - (1-
(147)
we have (recall that Lg = 2C,s(1+2)
4C
(1-7)²
(1-7)
T-1
(*()) T 1=0
Σ
E
D + at
64v20 +1)
8y30a
(1- - 7) (2 + VI 0² 12
+
T(1 7)a
2 (0, +1)
N
512vBCo 1)00
1-7
01 - -7)4
(1-7)82211- - 02) (1
stat
2V2C. +1)
180
512v6CavCC(0/, +1
Eapprox
1-7
(1- -7)
(1 - 02)6/2111 - -
6144/222 (Cp + 1)
(148)
(1- (1/2)11/213/211 02)3
By Theorem E.3 know that V could be upper bounded as follows:
v Eetat I (1-7)VK ((V2p + 1)03 + / 22pp(1110) - -7).
(149)
(128) follows from plugging (149) into (148) and noting that when <
1 2
Bounding the consensus errors. Similar to Step in Appendix F.4, to bound the consensus error
log f((?) log f()) for all n e [N], we first upper bound the eigenvalue of the spectral
norm C.
The characteristic polynomial of is
S(A) (X ( A 022) C12021
= X² (c1 + C22) + C11 C12021,
which gives
P(C) < C11 + 022 + v (c11 + o2) 4(c11012 C12021
2
Cn + 022 + / (c22
c11)² + 4012021
2
Cn + O2 + 62
Cn1
+ 222e21
62 + Ve12021
3 oz
V3oa
12v2Loo
V1 -1-02 0²
v1 0² (1 7)4
3 3+0² 0²
o(1 02)2
64
49 + 15g2
64 <1,
(150)
where the third inequality uses (138), (139), and the fourth inequality uses (127).
Therefore, similar to (230), when S a1. have
<
49
15
(2
64s²
(151)
64
64
15(1 - 0²)
Combining the above inequality with (146), and (149), obtain (129).
34

---

E.2 Proof of Theorem E.3
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,,1 (Theorem in [BM13]). Consider the following assumptions:
(i) The observations (as, bb) Rº R2 are independent and identically distributed.
(ii) E [|ull"] and E [|bx|]]] are finite. The covariance EE [ is invertible.
(iii) The global minimum of (ww) [ ag)² 2 - 2(w, bx)] is attained at certain un"
RR..
Let A by= (w""ax)er aa)aa ag denote the residual. We have B[As] = O.
(iv) 3R and 0 such that E [ALA]]]
2 [arak] and E || I| asak [ S
R [
Consider the stochastic gradient recursion
Wk+11 = Wk 17 ((wk, ax)ax bk)
started from we E R.. Let Wont
= K Ek= Wk. When rj =
1 aR we have
E (WWar) - g( ) (ovT R ww - w= 11)
(152)
K
the proof 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 ag and by in Theorem G.2 Φ(s.a) and @5)(s,a) in Algo- rithm 4, respectively. And let ||-II I1-112 in Theorem G.2. Since the observations ()(s,a), Qe(s, ())s,))
Rd R2 are iid. (i) is satisfied.
As we assume (lo(s,a)ll Co. E [lo(s is finite. From Assumption 4.1 we know that E (o(s, ())(s, a| is invertible.
is bounded by Let H be the length of trajectory for estimating (s). Then (Qe(s,a)) a))
2
E (ōe(s.a))²
27
E (s.a)ndi
Pr(H T)
Σ r(su, ai)
H 7,80 =8,00
7=0
2
8 (1- - 7) Σ B
E
Σ r( at)
H T, =
T=0
$ E (r.a)dd
(1 (1-7) Σ
7 + 1)2
S (1 - 7
(153)
==0
from which we deduce E Furthermore, we introduce the residual
[ a)
$ C
Q a)2] is bounded. Thus (ii) holds.
(Qe(s,a)-ofe a(s,a) ()s. w' d(s,a),
(154)
then from Lemma 7 in [YDG-22] 22] know that E[ 1 Vwl(w Qe, d 0. which gives (iii).
Here || could be any norm in I
35

---

To verify (iv), we let R Cs in Theorem G.2, then E [ s C (6(s,))((s,a))) Also note that
w² (R (Biana)dd [0(s, ()(ss)))) B, (sa)mmnt [)((s,)))(s.1)
$ 1 1-y (B( [((s, (sa))a (e((),))((5.))
(155)
from which we deduce
B
|00 112 5
(156)
11(1 - 7)2
E
(Qg(3,.) a) -((3))))-6(3.))T="""")
w s.a = E
(Qe(s,
1s,a - -20ç(s, a)){))) w² + (d(s, a) a)'"a"
===)²
(157)
202
C
$ (1 7)²
+
+
111 7)3
12 7)
C3
2
S (1 7)2
+
(158)
1M(1 7)
The above expression implies
)²² (e((s,a) - a) w 2 o(s a) ()
E AAA ]
E (s,))=df
E [(ccss.) - o(s,a) wt 2 |s, o(s. {(5,0))(3,0)
E (s.a)ad
V2
C2
pul 7) +1)
a)(ss))
(159)
Therefore, (iv) is verified.
Thus by (267), with stepsize B initialization wn 0 and K steps of critic updates, have
207
E [ (Wours 2e de) - 6 (w', Qg, de)
S K
(ovp Co 1102212)
2
/2p
$ 1n(1 77) +11 + 111 7)
C2
S K
1 7
which gives (113).
F Proof of key lemmas
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 Appendix G.I.
Lemma F.1 (Properties of auxiliary sequences ( and (E (5()) and {g(t)) have the following properties:
1. {(i) can be viewed as an unnormalized version of (1), i.e.
20 (8. Vn [N], E...
7 (-1s)
(160)
|k (s, 111
36

---

2. For any 2 0, log keeps track of the average of loge") Le.,
1
I log (og logg (t))
(161)
N
follows that
(+) (s.
Ys E LES, (-1s) = ||=0) (s. 111
(162)
||=
Lemma F2 ((CCC+226) 22b, Appendix. A.2I). For any vector 0 = 10oJEEA E RIAI, denote by To E RlA the softmax transform of O such that
exp(Ua)
TT(a) EN'EA exp(Ox)) AEA.
(163)
For any 01,00 02 E -RI-AI, we have
[ox([exp((0))])) - Log((lexp((0))ll S |00 0211
(164)
||log To. log Te, 1o.0 S |0] 021lox
(165)
Step 1: bound u (s, = log 5 (1+11) (((+)) have
log ((+1) (s.a)IN] 11.2 By (40b) and (41b) we
((++)( (s.
= log 5 (++1)) (8, (8,a) log 5 (++1)
(8, (x,1)
= ||o W log g(t) (8, (8, a) - log [0g (8, a)
+ a) (ST - [s. /=//
< oal| log E ( (s, - log "0 (s, a (,,a)lN]] l12
+ a |T - as,
1 1- = 1loo'
<oal|u 10.0
(166)
where the penultimate step results from the averaging property of W (property (11)). Taking maximum over (s,a) e S x A establishes the bound on (2((+1) in (49).
Step 2: bound (((+)) = (s,a))) -( (s,a)Ix11 12. By (Ur) we have
T Ds, a) (s,
w (T.)) (+1) (8, 2. (s, - (s,
((WTT (s,, + W (q. (Q (s, - (s, + (x, - (s, IN
$ (s.) (s, 112 to (q. (Q (s,a) - (
(s, a)) + @t a) - -s.t a)) 1N
$ ( a) @ (s, a) 1n |12 + Q ( (s, (s,a)ll2
(167)
where the penultimate step uses property (11). and the last step is due to
(Q ( (s, a) - ( a)) + (Q.h a) (s, a) 1N 2
(s, Ω!0 (s. a) - N (Q (s) - 11+ (s,a)) 2
N
Q (s,a) - o ()) (Qt+t (s. - -Q (s.
m=1
= -||0 (s, 1 (s) N(O (s,a) - (s,
1|@ (s) o.
Step 3: bound ||Q; - -og ((11) 11 We decompose the term of interest as
Q; ー-r r log (1+1) Q; rax (()) (1 - Q)
a(Q; - =log (10) + (1 - -(,)) + -1-
37

---

which gives
- -olg (++1)
10 S <all - =log 50
-
1o
+(1
- +(1 -a) - -Q!0))
(168)
Note that we can upper bound ||
by
x
N
|: - @
1
N
rin
mm
R=1
N
Q
2 11
N
==1
M
log ((1) log 2 1l <MIl |00|
(169)
The last step is due to log (s, (8,a) a) log 5(1) (s, (s. S (s, a), while the penultimate step results from writing
(-Is) = softmax (s.-))
[" softmax (log 5/ (s.
and applying the following lemma.
Lemma F.3 (Lipsehitz constant of soft Q-function). Assume that r(s, E ((s.) ((s,) and r 2 0. For any 0, 0' E RISS|AA,, we have
2T - 7) log LA|
1| Q 1m
7 110' - -11
(170)
(1 7)2
M.
Plugging (169) into (168) gives
|0; -ogg-log 7 (++1)
S =a - -log (0))
11 (110)))0
+(1 +(1 (11-))Mlux\ (171)
Step 4: bound
| ( (s (s,
Let w(() : x A IR be defined as
a(s E S w (s, a) = || log
(172)
Again, treat (t() vectors in RISIIA whenever is clear from context. For any (s, E x A
and n E [N], by Lemma F.3 follows that
@ (t+1) (s, - Q (s, a)
< M max sE8
log log ((t+))(ss))))))))))))))) log e(*)) - (1.))((1-))
S M max max (s, - M || I|
(173)
SES aeA
and consequently
- (s. [[
(s.
S MvN [0(0)
11.
(174)
boils down to control
[10 lo. To do so, we first note that for each (s, ES A, we have
(t) (s,a)
(0)) W (alog (s, (s, +1 (1 a () log (s) - (1--)))
(a) |o(W- IN) ( ()) - log 11) (s, (s,a)IN) + (1 a) (WT (og (s.
(6)
< 2a| log E(() (s, - log (1) (s,a)1n 1|, + 1- a
- WT (3. - - log (1) - -Vss)\)
T
(175)
38

---

where (a) is due to the doubly stochasticity property of W and (b) is from the fact W - IN|l2 2. We further bound the second term as follows:
WT
(s. (s,
log E (d) (s. a) VN(()
2
WT (s, a) - log (s.
a) "
(Qt - log m (als)
WT a) Q+(s.))
+ - (0g - log (al
WTT (= ( -x
+= (s. - log ( (a|s)]ww] -gg]
=o (s, (s,a))x))) [ (7,
||| log (0 (s, a) log ( (als)1w||2 +rv log ( (als) log (als)
(176)
Here, the first step results from the following relation established in [NNXS17]:
((s ESXA: (s) = -T log (als) as)
(177)
which also leads to
log (1)) log ,, 11 < 2 - 11
(178)
by Lemma F.2. For the remaining terms in (176), we have
(0.9 (s)s s || :t"¹ (2) 11 + +1[0, 10
(179)
and
N log c(t)
log (3. - log क. (a|s)lxl
(5,a) (
log  (als)
N
2| log ((1)
-log 11
n=1
n
Σ
2 2||u(0)| 00
.2N
(2()) 1oo
(180)
where the first inequality again results from Lemma F22 Plugging (178), (179), (180) into (176) and using the definition of u(()),((t), we arrive at
S (2a- + (1 a)) V2N ||
1 - a
|1(00)
11
1-a
.N (1@0.) - -2/01 + 1 - -Q:lla.)
T
1-a 2v N Q T llg 1
Using previous display, we can write (174) as
|1Q (s,a) ()) a)
S <MVN (20 + (1 a) a) v2N) ||ut50|| 10 + 1- a
5
+ 1-a a VN (Melu(til| + +1(0!") - -Q; -Q:llbo) + 1-a
2 N Q: - log (0)
(181)
Combining (167) with the above expression (181), we get
|
MMVN
||000 + +OMNN
20 + (1 aa) V2N + 1-a vNN) ||
1
1 1-
1-a a VN -h0h -tll + 1-a
2/NN|Q - Flog 1ogg""11 (10
(182)
39

---

Step 5: bound
O01 For any state-action pair (s,a) E ES x A, we observe that
(+ - - (1+1)) (s)a)
as) +2
E
[V] - (((8,a) +
E s/m((s)s,))
(6))
s((p()))))
(7;(''))) :) 11)1
=Y s(-P(1(s,a)
E
T log
exp
?
E
p (s',a)- - log ग (++
(1(1)
(a'
P(..)) a a/w D3pe
(183)
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]:
(s) T log (|OSP (7(8,)
((b))))1))
)11)
(184)
T
To continue, note that by (162) and (41b) we have
log (a)s) = log _ (++1) a) - log (15 (s, (11)))
a log (0) (s.a) a) + (1 a) 2
(8, a) log (115"
(s. (s.)))l))
(185)
Plugging (185) into (183) and (181) establishes the bounds on (s, a) - - q (8.a) ( =
|eep (7((6))) 11) -Flog (5', (11)))))
E s()p())))))
T
rlg
T
((++1) (s', -
Q(tt)((,
alooo (s',
(s', + (1 a) 2t (s',
(s',"a"""" a²)
E Polaa) alwggt (1)a)
T
=log (loge (d',a')
(186)
for any (s, E S x A. In view of property (164), the first term on the right-hand side of (186) can be bounded by
[exp
(7(('))) (11))))1)1) - log (1((+))066 < ||Q; 1 -logg (1+1) 100
-
log
Plugging the above expression into (186), we have
s (+(s,)) (((+1) (s, s > log 5 (+11
11 min 8,0
(((+1) (s, - T log (0 (1++1 (s, (s,a))
which gives
QQ: 0 (1+1) 11.0 5>11Q==-loo
(((+1) 11 +y max (0, min ((++3) (8,a) a) - T -lg 5 (1++1)
(s, a
8,a
(187)
Plugging the above inequality into (171) and (182) establishes the bounds 2 and 2 (++1) in (49), respectively. Step 6: bound mins,a (Q, 1+1)
(8,a) 3, - log (t+1)
(t+))) (s) as))).. We need the
following lemma which is adapted from Lemma I in [CCC+22) 22b]:
Lemma E.4 (Performance improvement of FedNPG with entropy regularization). Suppose 0 < n (1 - 7/TT. For any state state-action pair (sp, au) E S x A. one has
V (((+1)((0) (so) - 1 (9o) 2 r
E smith smith (++1)
aKL ( (t+1)) (-150) (-Iso)) + KL(F() || (+))) (++1)))))
11 - -."" bl
(188)
Q (((+11) (s0, 00) - (s0 an) 2 1 7
(50,
2%
(10)
1.01 11.
(189)
40

---

Proof. See Appendix G.3,
Using (189), have
Q 1++ (s, a) - aalogg (1-)) @ (s.a)
(1-a)
2 (s, a) -7 |alogg (0) (8,
-Taalogg
(s, + (1 (1-a) a)
② (8, ())
27
(000
-
11
za (q (
10) (s, (s,
- rloge 40 (5.
2g + TTT
11
(1)
1000
(190)
1 7
which gives
min 8.0
(s, 0) log (1+1)
(s, 0)
s min e (s, a) - - rlog 10 (s. + 27 + 11T M (1(tt))
1 1-7
S aamax
0. min 8,0
e (8, a) - -loo (0 (s, ()) }
27 + 117
M|
(191)
1 -
This establishes the bounds on Ω (t+1) in (49).
F22 Proof of Lemma D.3
Let f(A) denote the characteristic function. In view of some direct calculations, we obtain
- of (A (A- o(1 + (A (1-
A(A) = (A (A-
(A((A
[S(1 (1- a0y redM (1- a2 2 + Men
(192)
=(((A)
T 2ed.Mo²
(1 7)2
where, for the notation simplicity, we let
MVN
(193a)
1-7
MN
C = 1-Y
V Nb,
(193b)
== 27 + T/T
(193c)
Note that among all these new notation we introduce, S, d are dependent of m. To decouple the dependence, we give their upper bounds as follows
1+1 7
dg
1-7 2 d.
(194)
MVN
S. = M.N 2+ V2N +
25,
(195)
where (194) follows from v) S (1 - 7)/T, and (195) uses the fact that a & and a S 1.
Let
X = max 3 13+0 1 (1 -1- (1-a)7+a)
(196)
2
Since A(p) is nonnegative matrix, by Perron-Frobenius Theorem (see [HJ12]. Theorem 8.3.1), p(n) is an eigenvalue of A(p). So to verify (55), it suffices to show that ʃ()) > 0 for any X E [X*, o0). To do so, in the following we first show that f(x*) > O, and then we prove that f is non-decreasing on [X*, co).
41

---

Showing f(X*) > O. We first lower bound fo(A*). Since \" 1²2 3-0
we have
1 1-o
- 001 + obn) 2
(197)
4
and from X = 1+(1-a)y+a we deduce
- (1 -0 (1-7) (1 a)
(198)
2
and
X 1+0
(199)
2
which gives
1 a 00.
X 00 2
(200)
Combining (200), (197), (198), we have that
fo(A*) 2 8 2
a
(1
1 + a
0a T1T.
(201)
To continue, we upper bound f((** as follows.
2 + cMTT2²
S1(A*) S STn + yodMn +
1
= n r S
2
Men)
+ +yddM)
(202)
1 1-
Plugging (201),(202) into (192) and using (199), we have
f(x*)
1 a
fo(2*)
1- fi f((xt)
Tmp"
2edMo²
2
(1 71-
7)3
217
1 1
aa) -11)
1-7 (T(s+ 2 7
10²
+ ByodMs]
1 0 + (1
Mon)
2(1 7)
8
1-7
TT?
- 0)²
"
STO² +
2 2+7 Mco T1 +
1
- 0²
1 - + syedMMo))
2(1 77)
8
1 1-7
1-
2
8
T1
(1 )
Sora²
(1 - 0)² 7² (2 7 + 5yy6) edM22
20,
2(1 7)
1 1-7
where the penultimate inequality uses
o <
1-a 2
and the last inequality follows from
the definition of Ç (cf. (53)).
Proving f is non-decreasing on [X* 20). Note that
7 5 (1 - (1- o)²
8.000
thus we have
x (A) n16
f((A) 2 (A - oa)(A a[1 + abr)) '1 So² 2 0, which indicates that fo fi is non-decreasing on (o), Therefore, f is non-decreasing
on [X*, o0).
F33 Proof of Lemma D.6
Note that bounding (1++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.
42

---

Step 2: bound (s, a) = =| (s,a)
Let q. =
(0)
(r,)
Similar to (167) we have
| (s, a) - (s.
oo (s /. (s, + o
( (s, (s.a) 1))l2 + to | (s, (s, 20 |lell-
S < /. (s. (s, a
(203)
Step 3: bound |0 log : (++1) 2| In the context of inexact updates, (168) writes
O 7 log (++1)
10 aall; - log log 11 (11 a -. 11 + +11-a) -1%- 11x
For the last term, following a similar argument (169) leads to
N
1
1
Q
(c) (c)
gr.h
N
N
N
8
N
N
M-
log e(l) 5n - log
N
N
n=1
S M
+
|elloo
Combining the above two inequalities, we obtain
1l s sallQ;- (lggg"++)))l
log 5 |lac +11-a)11Q;- 1 +(1-a)
(M
+ +Ieell<))
0
(204)
Step 4: bound | ( (s. a) Q."²) (s. a) We remark that the bound established in (174) still
holds in the inexact setting, with the same definition for w(!);
[oft (s. (0 s MVN (o(()) |
(205)
To deal with the approximation error, we rewrite (176) as
WT
(s, (s,
(o V (s)1.x)
(T T log log (d (s, ( (olg (al)))
-
( (8,a) a) a)<,,))Iy1111 (s. (og
WT (s, - (s. 1
+ +T log ( (s, - log +r log log==(
T (s, - /." (s, 1 + v (s.))
+ 110l (s, log (a) - - log log (a]ss)
(206)
where the second term can be upper-bounded by
(s,a) - (s, a)l < || - g.6 1.o0 + 1 (1) 2 1011| + / (s, - (s,
< ||0:00 क.6¹ 2 + Q""
(t)
Q; @:1l + ||e|lx..
(207)
Combining (207), (206) and the established bounds in (175), (178), (180) leads to
(1) a) < 2xx + (1 - aa) . .V2N |2(00
+ -
a
(0)
7
1 1- a VN (|@!!) -(00
+ 2
Q:
+
|Tell
+
1-a
2VN 1 - -1
43

---

Combining the above inequality with (205) and (203) gives
(1 1+ nM TMMN /N
|ultt 10 so
11000110 + +OMNNN
2a +1 V2N + 1-a vNM) ||00
7
7
+
1 l-a
VN (1कe - Oi + +
+ 1-a T
22/NlQQ: - I log log5"110 1100 + 20
lello
T
(208)
Step 5: bound
o (++1) -Q; It is straightforward to verify that (187) applies to the inexact
updates as well:
- S7 r log = (++1)
+7 (-min
(1+ (s, -log (logz(++) (s, a1) a1))
(s,
cc
Plugging the above inequality into (204) and (208) establishes the bounds on 52/ s2(++1) and 22/-t in (68), respectively. Step 6: bound - mins,a (Qr (++1) (s, a) T log ( ((++)) (s, a)). We obtain the follow-
ing lemma by interpreting the approximation error e as part of the consensus error in Lemma F.4
Lemma F. (inexact version of Lemma F.4.. Suppose 0 <n S (1 (1-11)))0 -///T. For any state-action pair (so, an) E x A. one has
(((+t)(s0)= - v2 (so) 2
E
aKL (AKL(T(+))((1)) || (+))s) + KL (-())))))))) (++2)) (-150))
snddr(t+1)
2
(1 - -Q,h1 + +l1ello0)
(209)
7
Φ (((11) (s0: ao) - -Q
1 (s0, ao) 2-
1 7 (1 - -Q.²) |1. + ||ell,0)
2%
(210)
Using (210), we have
a (olog55)(( + ()) 2 (8,a)
Q (14)) (s, a) -
2 t10² (s) a) - <allog ((),)) + (1 a))
(8,a)
- (s,a)
1-7 (1 - ---²
27
+|ell
00
2a (o."
(1) (s) 2 (s.0)) 27 + 177
|/000 -
1.
(1)
27
|el
(211)
1 1-
1 -
which gives
- min (o. (1+)) (8,
(o a) - log 2(++3) (s,a))
8aa
(212)
< aaa -am min Qt (s.a) - :loge (log("(((,,))) (s,a)
+ 2n 17T
[u()) |
2y |elooo
M
1 7-7
x 1-
F.4 Proof of Lemma D.8
Step I: bound u ((+1) a) = log (((+1) -log))-oog"" ((t1) (,,
Following the same strat-
egy in establishing (166), we have
log ((++1) (8, - log 5 (++
(8, (s,a)IN
W log (1) (s, (() - logg (0)(")())))) ())
(s,
+ 1 1-9
n
-V" 2
s (o (0) a) - log (1) (s,
1
(s, - (1)(s,))NN (213)
+
2
?
44

---

or equivalently
| 0 sallu\00| 10 + 1-7
+17 10
17
(214)
Step bound
((+1) (8, a) = ||T (s) - (s. In the same vein of establishing
(167), we have
(s a)
S a T (s,a) : (s.a)1w112 + + t ( (s.a) - (
(215)
The term
(sQ (s. a)](, can be bounded in a similar way in (174):
(1 (1+ 1N oo.
||Q (s, S
(216)
(1 7)2
where the coefficient as
(1+1)g [1-1}² comes from M in Lemma F.3 when T and wg E RISIIAA is defined
V(s,a) (5.
w (s, a) = log ((t (s,a) a) - log c (0 (s.
(0) a) - 1- V'(3)Ix (217)
"
It remains bound
(0) Jwo 11 Towards this end, we rewrite (175) as
m 6 (8)
= -| loge(" 1-9 T (s.a) logg - V*(sNNl12
1-7
= (W- - 1) (log (0g (s, a) - log t (s,a)IN) +
1-7 (TT(0(s, - (=))
"
< 2/1 log (0) - log 5 1 (s, [N 12 +
7
1-7
< 2| log 5 (0 (s) - lo (s,a)1N
+ n
WT (5. allll
2
? V - V*(s)
(218)
1-y
Note that it holds for all (s E S x A:
1
(s, (*)) S
T-
since (8,) a) and (s) are both in [0, 1/(1 7)]. This along with (218) gives
(4) w (s, a) < (0 I1.0 + 17 -1 + (1 7)2
Combining the above inequality with (216) and (215), we arrive at
[1(+2) 100 So 1+ (1+ (1+ (1+ 7)n/Nn ) |1:00/1000 + (1 (1-
(1+7)7
VNo 2/11(0
1100 + (1 7}-
1
N
(1 - 7)3
(219)
Step 3: establish the descent equation. The following lemma characterizes the improvement in ((t)(1 (n) for every iteration of Algorithm with the proof postponed to Appendix G.4. Lemma F6 (Performance improvement of exact FedNPG). For all starting state distribution e (SS), we have the iterates of FedNPG satisfy
(1++))(n) S (1)
(1 (1-1) 7)² 11110 -00-00
2m
-00--1111 10 - 17 (v -v vo)
(220)
where
(n) = Bendy KL( (-|s) (+(() - -ーーー v0) - W20
(221)
45

---

remains to control the term |
(0)
Similar to (169), for all 2 0, we have
N
N
10 ( - 1 N
Q
=
N
n=l
R=1
(4)
+ 7
N
log c(t)
log 10g550)
10
(1 7)2
==1
7
(222)
7)2
where (a) invokes Lemma F.3 with T 0 and (b) stems from the definition of (t) This along with (220) gives
dlt+) S (m) + 2(1 2(1+7)
(1- /| n||u(*)| - -1 (V
Step 4: bound the consensus error. To bound the consensus error
|log / (1)
log न (2)
for all
E [N], we first upper bound the spectral norm of (1) which we denote p (r))) Since (n) is a nonnegative matrix, by Perron-Frobenius Theorem, (()())) is an eigenvalue of B(1). So we only need to upper bound the eigenvalue of ((B())).
The characteristic polynomial of (11)) is
S(A) =(A - o) (1- A- (1+ (1 (1
.)
n 1 1-7 o²
(1 7)3
=x2- 22 (1+ 7)
1+ (1+
nJ
+ro
0²
- 71-
(1 - 7)3
which gives
2 (1 1
2+ 1 0)
4 4((1
(1 (
+ +4 7j
((B(T)) -
+1
1+
+ 1-7
(1-
(1 (1-71 7)3
2 (1 (1+7)) 1
(utzivN (1 7)
2
TJ
-/2
+ +41-7
(1 - 7)3
So 14 + (1 (1+7)7VN)
nJ 1-7
+
(223)
(1 7)3
Note that when 7) S 1/1 we have (recall that J
2(++)y VN):
(1-9)²
(1 1++)7VNN
(1-01 0
71-
and
n (1 - (1-
1-7 < 46
Plugging the above two expressions into (223) yields
B((in) So (11(-(1-00)/+81100//1000
3
5
+ (1 (11+((1)))(8))
--0 + 8
<
1.
8
46

---

Therefore, when S 771 we have
n Sp B(n))
|-- /||
+ d2(1))
t-1
(1 (1+7)7No
.... p
|200
Σ p² (B(r))
(1-7)* "
i=0
sp (2
2No
+
(1 - (1 (B(()))) 7
2
3 a + 5
16No
(0)
(11-9 3 21 - o) !1
(224)
8
Combining the above inequality with the following fact:
Vn E [N]
|log m/² - log
< log e/ - log (()
S = - |
20
where the first inequality uses (165), we obtain (84).
F.5
Proof of Lemma D.10
The bound on u (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 1: bound v(t+) a) -|I(( (s, 212 Let g0)) = (9 _14))
T
. 1.. 9NN
From (96), we have
T (s, gutt) (s,4)IN 2
w ( (s. + (1) (s,a) - (s. - g(ttt
(s, e))
[(TT)) (5. nT
(s. (s,o)1N) w (q (Q(t1) (s,a) 9d 0) + (s)) - (s, 1N
2
s -
+ +o
q (1)
(s,
10 (s.a) + (s.)) - (s, IN
< ( -s." (s +o
())
(8 - (s,
< (s.a) a) (s, +o ((41)) (s, Q (s) + 20 Noelll
(225)
Note that (216) still holds for inexact FedNPG:
| (s, a) (5))
|,
(1 [1+ VN 1 (t)
(226)
(1-7)²
where w is defined in (217). We rewrite (218), the bound on w/ (t) " (x,
(s, a),
2/| log (( (s,a) log (5, a) 1N
7 (s, 7(h (s) + 1-7
no
(NN - (s) (227)
With the following bound
((s,a) ES A:
(s) < 117(0 -²()
11000 + 1-
in mind, we write (218) as
w ( (s. a) < 21| (t)
11.0 +
00
+ 1-
+ 1 vN (1770) - 1000
1--7)
1
1-7
Putting all pieces together, we obtain
||(ttt11||0 so
1+ (1+ 1
0
1100011 11
(1 - 7)3
(1 7)7 VNo 2/ 2//1/0/
I N (1 (1-
+ n/N N
(228)
+
1 - ||eloo
7)-
20 N ||elloo
47

---

Step 2: establish the descent equation. Note that Lemma F.6 directly applies by replacing 2 with g0))
( (n) S (m) + (1 7)2
2n
11.0
-n
-v0))))())))))
To bound the middle term, for all 2 0, have
N
N Σ
N
|000 -
1
Qn
(1)
+ N
1
Σ
On
1
Q
N
N
n
==1
n=1
n==
(1 + ?)y
1
log (!)
log (t)
+
1
cn
(1 - 7)2
N
80
+ ?
[2(00
+ ||ell
(229)
(1 7)
Hence, (102) is established by combining the above two inequalities.
Step 4: bound the consensus error. Similar as (224), here we have
2 sp(((n)) (-(11) + (d2(1) + c2(1))
(1+7))Na + Σ (B(()))
(1 (1+ (1+ N
s.... (.(())(((()))))
12
a VNo
+2 I1elloo
(1 (1-9)) 7)4
(1 (1- 71
i=0
so'(B(n)) |2000
(1 (1- "1 + VNo
No
"VV
+1
||ell
1 - p( ((()))
(1 (1-
3 o 8
5) 2
16
No
nVN
12
+ 3(1 3))
(1-7)4 17 NNo
(I-7)3 +1
||e||
(230)
which indicates 103.
G Proof of auxiliary lemmas
G.1 Proof of Lemma F.1
The first claim is easily verified as log (s, always deviate from log a (-Is)) by global constant shift, as long as it holds for t = O:
log el e((+))
(s.
Σ Wh.. (aloge (s. (1 a)T (s. (s.
Whm, (a( [ogg (1) (s, 40 (3)1[A)) ) + (1 +1- (a))
N
W)nm (9 + (1 (s, log z (s) + +c ((+1)) (s)
0
n/ log m (+Is) + cf (s)
where 20 is the normalization term (cf. line 5, Algorithm 2) and (cll (s)) some constants. To prove the second claim, Vt 2 0, V(s, a) E S x A, let
T (s. a) = - 1 (TT)))
1
(231)
N
Taking inner product with 1 for both sides of (Ur) and using the double stochasticity property of W, we get
T (+(1)) ((tt)((s)))) (s,a) = (s, + + 2 2.0 (s.
(232)
48

---

By the choice of ( (line of Algorithm 2), we have T =Q and hence by induction
1 0: 71 = Q
(233)
This implies
log ((+1) 1 (s. a logg (s, " = (1 - (s. a)/T
(1 a)TT (s,a)/T
1
1 1 log & (s,
log ( (8, a)
N
N
Therefore, to prove (161), suffices to verify the claim for =
N
T log E (s, a) = log |xxp (Q)(())) +
N log न (0) (als) - log exp
Σ n=1
log T. (-18)
(0)
N
N
log |/exp (s.-))))))) + log न (0) = log 0) (s a).
By taking logarithm over both sides of the definition of (1+1) (cf. (27)), we get
log (+) (a|s) + (1 ( (s. a)/ (8) for some constant (00) (s). which deviate from the update rule of log (++1) and hence verifies (162).
log π. (++1) (als)
(234)
by global constant shift
G.2 Proof of Lemma F.3
For notational simplicity, we let Of and Of denote Q and 0 respectively. From (6a) we immediately know that to bound O Q suffices to control [V((s) V (s) for each
E S. By (4) we have
(+) - v (s) < (s) v (s) + +[([s,, ma) H(ss, TTr)
(235)
so in the following we bound both terms the RHS of (235).
Step 1: bounding Hs(s, πT) - H(s ) We first bound [H(s, TT) H(s, ma: using the idea in the proof of Lemma 14 in [MXSS20]. We let
g(t) 0 + t(0' -)) Vt R,
(236)
and let (1)) E R be
VsES: (s) =- Σ
Totes (als) log Taco (als).
(237)
aEA
Note that ||100/11 log IA].
We also denote 11()) 12ld1x Al by:
(-T(-18)
S (()
= diag(Toco (-1s)} Tgen (-1s) (-1))
(238)
00
0=0(e:
then we have
S
(s)
(01) ((.ss (s..)) -(s))))))())))))))))))
(s)
(s. -.,-))))(s))) 0
dt
(1 log To (+1s),
0ss
H1 log
gm (+1s) (s, .) 0ss, )lbo
(239)
where (a) (-36)
stands for (t)
The first term in (239) is further upper bounded as
(0[-10]
-=001)
H 0 (s)
log क n (-|s)
Σ
Taen (a|s) log Taco (als) Tge (-1s) log Tocn (-Is)
A
Toin (a|s) (llog Toco (als) + (-100111)) log Tgins (-|s)])
aEA
2
Toter (a, s) log Tge (als) S 2og [A].
aEA
49

---

By Lagrange mean value theorem, there exists E (0, 1) such that
(s) 14 (s) - ho(+))
S 2 log |A] 110' ((s,
dt
where the inequality follows from (239) and the above inequality. Combining (5) with the above inequality, arrive
2og [A] H(s mO) - H1, mT) < 1
100 - 001
(240)
Step 2: bounding (s) - vo (s){- Similar to the previous proof, we bound |V*(s) V (s)l by
dv-a(() dt (s)
bounding
By Bellman's 's consistency equation, the value function of Toce) is given by
Vola)
(8)
Σ
Tato (als)r(()) + Σ To (a|s)
Σ
(( (d),
BEA
E'ES
which can be represented in a matrix-vector form as
vo!0 (s) M
(241)
where 6g E R is one-hot vector whose s-th entry is
M, = (I - 7
(242)
with P. E S x|5] denoting the induced state transition matrix by Tat
P((s,s')== Σ Toco (s)s))(s'(s,,))
(243)
and r3 E &R| is given by
E (s) = Σ
Ta (s)))s))
(244)
aEA
Taking derivative w.r.t. i in (241), we obtain [PPO8]
ava
v. c. M. dP.
Mr. + eg Mr dr.
(245)
dt
dt
dt
We now calculate each term respectively.
For the first term, it follows that
e M dPP
dP. Mir
Mr
S7
M
dt
dt
1 7
dP: M
1 7
dt
27
5 1-2
M o1 110' - 01
(246)
2n
<
|Irelloo 110 - -B11.o
(1 7)2
27
< (1 7)2
110' B11
(247)
where the second and fourth lines use the fact ||M] S 1/(1 7) [LWCC23a, Lemma 10], and the last line follow from
Σ Tow $.
max
We defer the proof of (246) to the end of proof.
50

---

For the second term, it follows that
dr:
dr:
1
c M
S 1-7 116' 01
(248)
dt
7
dt
where the first inequality follows again from |Mell1 S 1/(11 - 7),, and the second inequality follows from
dr:
dre(s) dt
Orgin (1s))r((s))
(((6,))-((.))))) 0(0.)))
dt
max eE8
max eES
(8,
oc
Ora (-18) (0C0),, ((8,)) 110((s,)) -10
max sES
Σ Toco (a|s) (((8,)) a) Tow (-18) (r(s, (s,-)) 01, aEA
max eES
max max #ES aEd
(rss, a) Taw (-18) r(s, :) (s, - A(s ll
1 since r(s.a) 10.1]
max (s, ((s, 1o. = 110' - -0 1. sES
(249)
Plugging the above two inequalities into (245) and using Lagrange mean value theorem, we have
1 1+ 7)2 110' 01l
(8) v8 (s)l
S
(250)
Step 3: sum up. Combining (250), (240) and (235), have
Vs S:: (s) V. (s) 1 1+ 7 2T (1-1--1)0 log IA
|loo π log
(251)
(1 1 7)
Combining (251) and (6a), (170) immediately follows. Proof of (246), For any vector IR 11,
have
dPp
diTgees (als)
P( a))ss')
dt
dt
S'ES aEAA
from which we can bound the to norm as
dPP
di (a|s)
T
S
max
Σ Σ
P()'(s,a)
||:||oo
dt
dt
oEA EEES
dogrco (als)
||0||00
max
dt
aEA
< 2 116
0
||0||00
(252)
desired, where the last line follows from the following fact:
dm o (a|s)
Or ag(t)
0' _
-
dt
AE
asA
(alr))(as))
0ssss -((s.-)
(0
aeA
= Σ
Toco (a|s) (8'(ssa) - 0(s a)) - Toco (.1s) (0'(s,. - ((s, ))
asA
< max 0 ((s.a) a) 0s, a)l + T. (0'(s,.) 0(., ))
< 2 0' 01
51

---

G.3
Proof of Lemma F,4
To simplify the notation, we denote
800) @4 -- -
(253)
We first rearrange the terms of (234) and obtain
-olog (als) (s,a) + (s.a)) 1-7
(log (log)(+)))als)) log log
(als)) 1 1- (())
1) (254)
This in turn allows to express D( (5o) for any 8o S as follows
V (5o)
E
+ log (0) (80 + e (so, an)
(
1-7 2(0000(00)) (30)
1 1-2 (log (ao1s))))))))) - llog ((1) -log=(1))
(cols))) - 8600/ (80, ao)
+
E
ag
(-180)
1
ao~ (+140)
1
7 22(1) (so)
1 I (L(((()
(++1))
E
[ott) aoi)
7)
"
(1)00))))00)
1 (0)
_ ( (-1s0) (+(22)((110))
[oc)) 0oi
E (1155)
E ag a
7)
"
(255)
where the first identity makes use of (6b), the second line follows from (254). Invoking (6b) again to rewrite the 2(5o) appearing in the first term of (255), we reach
(5o)
-T log 1og=((+1)))) (++1) so) + e,a² (s))a0)+ + T (--1--) 1-)) (log ((++ (ogg -log ( (a|s)
E
ag - (+
"
1
KL (L( (-1s0) (+(+1)(1150)) (-150)
E
(80)
+
E
(80) ao)
"
=og (0)) r(500 ao) + +zD("0 (100)
E
ugres (log))
7
KL (L(T((+2)((115)) ||
(-(ss)))
_1-1 (KL()((())))) || x((+1)( (-1oo)
17
E
(50)
+
E
[8c) (s0
(256)
Note that for any (0) ao) E S x A. we have
[800 avi) +
(80) av)
E
E
og (-1oo)))))
c 7(++1) (aolso) - x1 (co(00)) (()) ao)
aoEA
(-100)))), 1|600| 22118(1)
(257)
52

---

To finish up, applying (256) recursively to expand | (8:), 8 2 and making use of (257), we arrive
at
(5o)
2
((())
+
E 2 (14))
Σ 7 (1((): a;) 7 log x (a:11s))
i=1
0
00
7
KL (1)) (-1ss) + kL KL (-1ss) || (1(()))))))) }
"
i=1
2
|
+ ( (sn)
1
E
- -
n
1-
KL (L( (+sss) + =KL(F(0-1ss) || (
s (2)3)
(258)
where the third line follows since (++1) can be viewed as the value function of (((+1) with adjusted rewards ((t+1((s, a) == r(s, a) - 7 log (s|a). And (188) follows immediately from the above inequality (258). By (6a) we can easily see that (189) is consequence of (188).
G.4 Proof of Lemma F.6
We first introduce the famous performance difference lemma which will be used in our proof.
Lemma G.1 (Performance difference lemma). For any policy ,| E A(A) and p A(S), we have
(=(()) - Vz (0) (=(
I B(saa)ar [ (s.00
(259)
1 Eand (0) - T(())
1
(260)
Proof. See Lemma 3 in [YDG+22].
For all t 2 0, we define the advantage function A as:
a() E A:
(s. = (s*
(261)
Then for Alg. 1, the update rule of गे (Eq. (234)) can be written as
log क +++ 1) (a|s) = log क (a|s) + 1-7 ( (s,a) + (s)
(s,a)
- log (s),
(262)
where g(t) is defined in (253) and
log g(t) (s) = log
Σ
(1)
(a'ls) exp
1-7 (A (s, (10) (3,00
17
a'EA
Σ
())
log
11 ( (s a') + 800 (s.
E'EA
(a'ss)
A'' + 800 (s,0')))))
a'EA
7(0 () (801s))000,s)))
- |00
7
(263)
a'EA
where the first inequality follows by Jensen's inequality on the concave function log x and the last cquality uses Ev'e (a'Is) (s, a') = 0.
53

---

For all starting state distribution μa, we use ((++1) as shorthand for di lemma (Lemma G.1) implies:
,the performance difference
(4) (((ti)
(4) (4)
1 y E Bendlctt)
1
Σ (als) (A + (s)))))))))
E Bondlete Bo
(an (s,)
-
aEA
1 E Boddlet1
क x((+)) (a|s) log T(1+)) (als)
Bendtet1) B BawT(H+)(11)) (s,0
E
17
(a|s)
1-7 7
acA
1 Egoddiics 11; (i (L(()(+))((111)) || o (1ss) +
E B 12) log (s)
1
snd 11) Bawail (111) (s.0)
1(13)
17
1 7
2 E Bedd
1
log (s)
+ 1 1- 11~1-180 11000/1 oc
17
1-
1- 11000
17
from which we can see that
b(l (m) (w)
(N) 2
1-7 -1160001 |00
2
(264)
9
where we use (263), and that
vittt(()) (w) - vV((() (w) 2 1 1 Eanyy log 31t)
+1++1110000 77
11 )
1 1- (265)
2
I
17
which follows from d((+1) dz (z(141) 2 (1 - 7)p and the fact that log (s) + 11(0 (by (263)).
2 0
00
For any fixed p. we use d' as shorthand for dz By the performance difference lemma (Lemma G.I),
(p) p40 (p)
1
E Bend' Σ (als) A (0) (s. a) + (s.
1-9 Band- Bond-Bantt (iior( (s.a))
1
1 Y
aEA
1
(a(sss (als)()))
1
(110) [6(0
Egad'
Eower (anrr
17
(als)
1 1-7- 7
aEA
1. E Eynnd
(KL(TT(11s) (1is) KL( (-16) || | (-1ss) log (5)
1
E Exwd E. Eawr (11)) (s.))
17
1- y
< Egand
1
(1(()(11s) || (1ss) - KL (1ss) ((+))))1s)) + log ()))
+ 1-
- 1|6000 oc
"
17
(266)
where we use (262) in the second equality.
By applying (265) with μ dt as the initial state distribution, we have
Exrp (Iog (s) + 1 -
" " |10)) S 1 - (7) - ( + (1- 7)2 |1,000
1
Plugging the above equation into (266), we obtain
V*(p)= T (p) S Eand (KL(TT (-1s) (-1(s) (-1s) (-(a((11s) || क (+1))
1
n 1 (drt
v-0 (d)) + (1 - 7)3 1
2
+
which gives Lemma F.6.
G.5 Proof of Theorem E.3
The proof of Theorem E.3 could be found in Appendix C.5 in [YDG+22]. We present for completeness. To prove Theorem E.3, we need the following Theorem G.2.
54

---

Theorem G.2 (Theorem in [BM13]), Consider the following assaumptions:
(i) The observations (as,, bu) Rº RP are independent and identically distributed.
(ii) E [|all]] and E [|bx|]]] finite. The covariance E [ is invertible.
(iii) The global minimum of ((w) = }E [(w, ag)² - 2(w, b&) is attained at a certain w² E R.. Let DR by- (w" ax)as denote the residual. We have E|As] = O.
(iv) 3R > and o > 0 such that E [A & OFE [ and ||ax Il aga
s
R& ]
Consider the stochastic gradient recursion
Wk++1 = Wk - ((wks as) bx)
started from wo E IR, Let Won K Σ K k=
Wk- When 17 4i2a. we have
2 K
E [g(( (wot)))) - g( (0w)))
lovp+ R ww w" 11)2
(267)
In the proof Theorem E.3 we'll show that for Algorithm 4, the assumptions in Theorem G.2 are all satisfied and thus
the result (267).
Proof of Theorem E.3. We let ag and by in Theorem G.2 be 6(s, a) and Qe)(s,a) in Algo- rithm 4, respectively. And we let ||-Il = Il-l12 Theorem G.2. Since the observations (o(s,a). Qe(s, a))(s,))) E R2 x R2 are iid. (i) is satisfied.
As we assume (b(ssa))l, S Co. E E [1)(())))13] is finite. From Assumption 4.1 we know that [ø(s, a)o(s, a) T] is invertible.
Let H be the length of trajectory for estimating (s(s, Then (Qe(s,a)) is bounded by
2
E (ōc(s.a)))
E (s.a)aafs
Pr(H 1 T)E
Σ r(se az)
T, S. s, ag
2
00
= E (s.a)ad
(1 - 7) Σ E
Σ
r(s ar)
H = = = -, = a
T=0
1=0
< E (s.))adts
(1- Σ
(T + 1)²
I (1 - (1-7)2
(268)
T=0
from which we deduce E (e(3,))0(s a)
$ C3B [c((s a) is bounded. Thus (ii holds.
Furthermore, we introduce the residual
A (Q)(s, a) w²) p(s.a),
(269)
then from 2YDG+22, Lemma 7] we know that E[A] = Vwe(ww" Qe, 0. which gives (iii).
To verify (iv), we let R = C in Theorem G.2, then E [10ss, ((1 s C a)(s,,))( Also note that
w² -B [éls, (((s,)) ( ( [2((3,))0(s.0]
1 (Braaja (Br ((s, B (na)aats [0c(s, (270)
1
'Here ||: could be any norm in P.
55

---

from which we deduce
B
2
112 x
(271)
uel - -7-
(Qe(3,.)) -o) "0')
1s,a a
E (@e(o,.)))
18,0
-2 w0 (o(s, a) "==²²²
(272)
2
20%
C
+
--
M1 7)3
1²21 7)
C 9
2
+ +11
(273)
(1 - (1-
(u(1 -7)
The above expression implies
E | (s.a)adT
(ee(s,a) -
-(s,aa)))(ss)))))))) a) w²) o(s, a(s, ) w0 2 1,,a ((.
E (De(3.a) - o(s -((,)) T
E (s(a)matt
V2
CZ p(1 -7) 1
(274)
y
Therefore, (iv) is verified.
1 Thus by (267), with stepsize B 20
initialization wo and K steps of critic updates, we have
E e Wouts Qs, de)] - (w", Qs. de
-
(ov + Co 1|20 12)2
K
4
22p
(M(1 +11 +
C²
C2 M(1 - 7)
K
1 1-7
which gives (113).
G.6 Proof of Lemma E.7
Proof of Lemma E.7. For notational simplicity we let V8, y denote Vls, Vle, resp. Same in Lemma E3, We define g(t) = = i(5' - {) and define Pt, Mr, Tt. by replacing Teto with Jeco in (243).(242) and (244), respectively. Define
(8(8,a) = ((s,a) - Earns (63,) (0(s,a)))
then we have
0fe(als)
= fe(als)de(s5a))
(275)
Analogous to (252), we have
dPp
(als)
<
max
Σ
Σ P(s'ls,
||0||
dt
dt
aEA K'ES
do (als)
max 8
Σ
||
dt
aEA
< 2C 1lg' - E112 ||
56

---

where the last line follows is due to
(als)
(fgio(aas) E -E 2E())
dt
AEAA
aEAA
Seco (als) ((0e)
(8, (), E)
BEA
Σ Seco (als) (8. 1)2 115 - Ellp
aEA
2c || =l
Same as (245) in Lemma F3, we have
dvs (8)
M. dP:
Mrn + eg M, dr:
7. e,
(276)
dt
dt
dt
And similar to (249), we deduce
dr:
ds)(s)
2 Sgga ( , E 5)
dt
dt
0E(1)
fe(ds))g(s.c))(s..))) E)
((()s))((s,0) E)
aEA
s 2C ||E' Ell2
which gives
Mj dr
dr:
2Cs 1|E' Ell
S
S 1 -
(277)
7
20
Following the same steps in (247), we deduce
dPP Mer. S (1 - 7)2 11''- -Ell2
27Cs
r. eg
M
di
71-
-
(278)
Combining the above two expressions (277) and (278) with (276), we deduce
2C
- - V (())) (1 71- I|E' El1p
(279)
which implies
((s.0) (Qf(s. Qf 2Co7 (1))
11E' Ell
(280)
(1 71-
G.7 Proof of Lemma E.8
This proof is inspired by the proof of [YDG+ 22, Theorem 1]. To give the proof, first introduce the following three-point descent lemma:
Lemma G.3 thine-point descent lemma Lemma 6 in [Xia22]). Suppose that C c R is a closed
convex set, g C + R is proper, closed, convex function, Dr(...) is the Bregman divergence generated by a function of Lengendre type and rint domh C + For any x E rintdomb, let
a arg min "Edombinc (f(u) (x(u,))),
then + E domh O and for any u E domh C,C, it holds that
f(x ) + Dz(x ,x) I f(u) + Dn(u,x) D Dn(uxtt)
(281)
57

---

Proof of Lemma E.8. By the update rule (114) and the parameterization (24) we know know that
Exx: (ass)
()) (als) exp (ao (oo6(s,.))bb))
where (s) is a normalization coefficient to ensure EeEA ( = 1 for each s E S. Note that the above or (1+1) could also be obtained by mirror descent update:
E S: (-Is) arg min gEA(A)
{ (D( .) + D(g. (() (()())))
(282)
where ((s) E R is a matrix with rows o (s, E R for a E A. and D(.,.) denotes the KL divergence defined in (109).
We apply the three-point descent lemma-Lemma G.3 with C A(A), f = - ( .) and ((A) + E is the negative entropy with h(q) = Eaed g(a) log q(a) and deduce that for any q E (AA, we have
(9))) (1s)) ((s),, & -a((())) +D (q. (1())))))) (9. (14))))1))
Rearranging terms and dividing both sides by aa, we obtain
(0))) (.+)) ((tt)) (-1s) 9) - (1)) 2 --D (q. -2 (1(5)) -
a (2. ((-))s)
a
(283)
Let q = (-1s) and xt( re(s).rccp. we have the following two inequalities:
(0()) (11)) f 2 n
+ (11),,,,, ( (1+1))))))
2 0.
a
(284)
( (0()) f(c+t) (-1ss) + (0()) (-1s) (()))))) T'' (-1s)
- D (tt
- (T ((-
(285)
Taking expectation w.r.t. distribution d' on both sides of (285), we arrive at
Egwd' ()()) (1)) EEandr ((0())00) (11s) - T" (-15))
2 _ (D(+tt)_(())
(286)
To simplify the notation we let ((t) and (() denote o and V f()) respectively. Note that the first expectation in the above expression (286) could be upper bounded as follows:
Ba ()))) Fit) - (116) Σ (s) f(tt)(11s) - (-1s))
SES
(s)s)
(6)0)))) (11) (+1s)
< 0, Σ
(- (-1s))
BES
=0,) Σd
(s) ((+1)) - F(((ss) + 0, Σ m (s) (0)0())00--"016 ((t)))))
(-Is) (-1ss)
SE8
= 0,(1 (1 (p(+t)(0) - p(( + Σ ( (s) ()) - F(tt)) - F()ss)
$ES
(287)
58

---

where the first inequality uses (??) and the definition of 0pp (107) and the last line follows from (260)
Lemma G.1. We separate the second term of the last line into four terms as follows:
E d put (s) (8) (s,
fitt)) (i(s) (-(s)
(8) (att) (s.a)(w()) -20 + ΣΣ d (af (o" -(:0
SESaEA
SESOEA
5 ( a) (als)
(1) (a)s) (Qt) - x0 as).))
(
-
RESREA
#EA
(IT
(MV)
(288)
Applying again Lemma G.I, we deduce the equivalent form of the second expectation in (286) as follows:
Band-
(-1ss) ((0 x" (-1s))
Land (Q(1) ((0 x' (+ls)
+ Eand' -0(()))00)0((((s)))))))))))))))) f() x x+1ss))
= (1 7)) (p) -V" (0)) + Eewa'
(T()) - (s) )) (-1ss) - (+1s)) (289)
where the second term of the last line could be decomposed into the following terms:
Bond-
(s, (-1s) (-1s))
E (1) (s, (16(()) -)!')) Σ Σ d' d's) (o (o (s,a) (s00)))))
sESaEA
(B)
d' (s) (als)ø ( (s,)) - -6()) d'(s)='(aas) (s,) asss
SESREA
RESREA
(D)
(290)
Plugging (288), (290) into (287) and (289), resp., and making of (286), have
(1(1 7) (p) (p) + 7) (p()(p) V=' (p)
+ 0, Σ (
(als) (s, () =
ΣΣ
(s) (o (s, (s)
SES
#ES
(
(In)
((++1
(s, (s, (s.0)((h!'- -w(())+++ + (als"
ΣΣ F((1+)) (s)s) (s. - (sss
RES
SESaEA
(1)
(1V)
ΣΣ
(a)s) (s, (s, z0("))
ΣΣ d' (s)) (6T (s, -((oo
aEA
SES aEA
(A)
(8)
(M)))*((ls)))) (oo))))@Tss,))(eeee
(s,a)( (1)+)
d' ds)x (Q") - Φt (s, a))!
aES
sES aE
(C)
(D)
[(D((t1)- -D!").
1
(291)
59

---

Below we upper bound ((I) and (A))-
For any E N and E [M]. we define matrix Egy E Rexp
Σ Eg = E (1 [o(s,a)o' (s.
(292)
and we define
(t) star,n = (t))) Q _i - (wiinn Q(1) : o(
(293)
w wx Q(1) d(t))
(0)
(294)
approx,n
then for all n E [N], by Assumption E.2 and Assumption 4.2 we have
E
st
stat >
and
E
approx,n
(t)
S
6 approxx
(295)
We let e(1) =
N N
2n=1
m and
(()
appprxx
N
En=l n. By Cauwhy-Schwartz's inequality
(2)
we have
df (als)) (s))))=((ss (s, w(th)
100)
(8x0)E8xA
(drutD (5)) 2 (alt))
du (s, a) (s) - 2
Σ (sa)ESxA
di (x,
(s,a)SSxA
(dfitt)) (5)) (altt))alas)
2
Σ
E
(s.a)/dl)))
w
ou (s.a)
Cv ||0!! (t) (t)
-w!
12
10
V Cuestan (t)
S V Cr
(296)
where 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 E RP, we have
w. Q!. M0
e w a.
Q.0 Z00 (
T (s, a)w o (ss, o (s) - - 27 - e (w. (t) (0220 227,
E
(2,0)~d0))
E
((aa)=a)))
O (8, - o ((s,,a 27
+ 2 (w (w- -ww-wll) T B ((an)
- (s, (s)
((s.a)
+ (w with) Vul (!i Q!0,d"))
w W..
w w (0) W.m
(297)
where the last line follows from the first-order optimality condition for the minimum point with arg min E w. Q(() )t!):
Vw E IR:
(w - w!!)
(w-w!..)
T Vanl (w 2 ((t1 , 2 0.
Analogous to bounding (()), by simply substituting F(++) with f()) or nt or substituting ((++) into d", we obtain the same upper bound for ((IT)), (A) and (C)), i.e.
(1II) (CC) v C
(298)
60

---

Now we upper bound (IT)) as follows:
N
1
d (s) (10 (s (Q.,).)) (s.
(II)) -
N
(5.
N
(dfitt)) (8) (al+))
Σ
$
N #=
dn
(s.a)
(s.a)ESxA
2
Σ
(s,0) (T.T (s,a))
(s, (s.)) (..))))))))))
(s,0)ESxA
N
(dfleti(ss) (als))
27
2 Eapprox, + Lg -
(t)
-
(sra)aal))
N
dn' (s,a)
L3
2C,
(1(())-((())))) 1((())
(299)
Capprox
N
where LQ is defined Lemma E.7, the second line uses Bouchy-Schwarre ' inequality and Young's inequality (117) and the last inequality uses Assumption 4.3 and Jensen's 's inequality.
Analogous bounding ((I7),, by simply substituting f(++1) with f() xt substituting d ((++)) into d", we obtain the same upper bound for ((V)), [(B) and (D)).
L3 N
(IV)). ID)]
2C,
(t)) Fapprox
g 1(5()))
(300)
Plugging (296),(298),(299,, into (291) and dividing both sides by (1 7) yield
0, (nu41) 510) -510 +0(0
< D.a D(++1)
20 11)
(t)
+
2
clte) Eapprox
+
L3 N
||g(0
(((())
(1 7)a 7)a
Taking expectation on both sides of the above expression and making use of the simple fact that
E [V]] S VE[x]
we reach the conclusion (123).
G.8 Proof of Lemma E.9
Proof of Lemma E.9. For any Ç > O, by the actor update rule (34) and (114) we have that
[e(++1) In (++1)T 2
((())) + aah - (5() + (t)
2
s (1 + ()
(
IN T
| + a1 1/ No - (t)
F
(301)
where the last line follows from Young's 's inequality (116) and (11). By the gradient tracking step (33) Young's 's inequality (116) and (11), we have
h (++1) (t)
(h( + (((1)) - (t) (1) + ((T (
|
Wh(t)
(1) (ww(t+)) (1)) 1(2 (b(()T
F
< (1 + 2)0²
(0(0 (U)
+ (1+ 1/5)0²
(t - (0
1(b
-10 y|2
$ (1 )
((()) (
+ +1 1/5002
(1 - (1)
(302)
61

---

where the last inequality follows from the fact
|
w (1+ w0(t)
1(w(((I1T -6
()()))
w wl(+1) (1 | N
W w((+1)) (t)
2
w ((+1) - ",00,,0(+10 (0(++1) - -2o(
wl(+1) ((
N
W [((+1) 20(11)
<
w (c+1) (t)
(303)
Then for any [N]. t E N and w RR, we have
((w, Q ) f (1) (2) )
④ (ss,)w o (ssss as o as ( -2." 27
(ea))~
E
(1) (:
( a)w (s, a am 27
2(w w! E ( (00T (0, a)) ((5,a)) a)]
E
(2,a)
(0)
2
+ (w w
(t) TV (r n. ,
w w
((t))
(1)
w
W..n
200)
2 p)
(304)
where the penultimate line follows from the first-order optimality conditions for the optima (t)
Vw R (w-w.") -0-w. ( TV (w Q ()) 2 0
(305)
and the last line is by Assumption 4.1 and (??).
Note that
(wwha Q((+1), (((+)))((+11))
= =B(aa))diit))
[00 (s,aa)))
(t) - (st
Σ (e ditt)) (s,a) (0 (s. aw Q1 (s, (s) +E
g(+1)
2
(s.a) 24t (0 (Q((+)) a) 2 (s. a))²
(s,a)
(s.0)ESxA
22CyIE 10 (0 (s)a) (1)
Q ( (s)) 2 201 [((t1) <(t)
S 22C approx + 213
(((++)) e(() 2
(306)
where the second inequality uses Assumption 4.3 and Lemma E.7, and the last line uses Assump- tion 4.2.
The above equation (306) together with (304) gives
wx
(++1)
(t)
w Σ
(t+1)
w
1
n=1
1 N
((w!))) (t) (++1)) d(+1)) el ((w!tt)) (t+1) Q((+1) dn a(t1))
<
(1 7) n=1
2
tt opprox + I2g clttz) - -E00 -
C₂
(307)
(1 7)p
where (0)
(w( ...
w (1)
(T) Vt.
62

---

Also note that by Assumption E.2 and (304) we have
1A N: (0(0))
|p
5
S
(308)
7/14
Therefore, by (306) and (308) have
| - w 3
|| - w.
w [ (w(0)
w
+
F
6
NCC Upprnva + Extm) + I2 ( - -
(309)
(1 (1-
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
5 {(+ ((th)=<(01f
(( aat - $
| - ()( - 1 + a (Wh (0) - 1
+ aa((i())
~ū : + +(wx.))
F
16 ( INE
+ 4a
(000 - -1v0 (T)
+ 4a²N
20(1) - (t)))
/
+ 4a PN
F
2
16
( E
2
+ 4a 02
(0) 1 (0)
+ 4a
Σ
N
20000
w
(t)
2
+ 4a
Σ
N
W.
(t)
n=1
m=
4a NE
4a2
s 16
( INE
+ 2
1/00 1 (c)
(310)
F
F
(1 7)2
(1(1-))
where the penultimate line uses Jensen's inequality and the last line follows from (304), Assump- tion E.2 and (271).
Combining (310) and (309) with (302), we deduce
2
h (1+1) 120
F
(1+ 1//) 960 L3
( 11+5+
24L3a²
|(())
|| 1 1 (0)
(1
7/1
(1 7)11
(1++1/() (1- 7)p
6a²
[N(Eaut + CxE
+ 4L2
a22NEsat
(1 (1-7)u 12 7)2 ))
+ a²NC3
(311)
Finally, (124) follows from taking expectations on both sides of (301) and (311).
H Numerical experiments
Experimental setup. We study the empirical performance of FedNPG (Algorithm 1) and entropy- regularized FedNPG (Algorithm 2) on a K K GridWorld problem. To be specific, the collective goal of N agents is to learn global optimal policy to follow predetermined path which starts 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 (where we take N 3 and K 9
example), agent n explores on map n, n E [N]. After taking an action, only when the agent is at the shaded positions can it get reward otherwise it gets O. 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, reward O. Each agent starts at the top left corner. To learn shared policy to follow the path, we aim maximize the average value function of all agents.
stipulate the agent's state doesn't 't change and receive
Results. the following we discuss the empirical results of our algorithms. In all the experiments, we fix the discounted factor 7 0.99. In our experiments, we also don't "on't require the mixing matrix to
63

---

cocppice mep
Figure 1: Gridworld experiement. N agents (N 3 here) aim to learn shared policy follow predetermined path, which is the red dashed line in the complete map. Each agent only has access to partial information about the path and gets reward only at the shaded positions and 0 at other positions. Each agent starts at the top left corner.
strictly adhere to Assumption 3.1. Figure 2, we validate effectiveness of vanilla FedNPG and reguaaz-re FedNPG across different map size K, where
O, 0.005, 0.05, 17 0.1, N = 10, and use a standard ring graph where agent n receives information from agent n + 1 for [V - 1]. and agent N receives information from agent 1, and we set all the weights each edge of the communication graph to 0.5. The corresponding mixing matrix of the standard ring graph is
follows:
0.5
0.5
0
0
0.5
0.5
0
0
0
0
0.5
0.5
0
W
(312)
0.5
0.5
0.5
0
0.5
Here, W (312) satisfies the double stochasticity assumption but is not symmetric.
0.25
X-33
0.3
X-22
0.25
0.23
32- -2.92
3.5
359
34
(a) T
(b) T= 0.005
Figure Changing map size we T = 0, 0.005 and change K for each r. We plot the curves of (V; -V=--V% (²)) \/V² )/V changing with the iteration number. We can see that both vanilla and entropy- regularized NPG converges to the optimal value function in a few iterations, and the convergence speed almost the same across different K.
64

---

Figure illustrates the normalized sub-optimality gap (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 few iterations, and the convergence speed almost the same across different K, i.e. the impact of K on the convergence speed is minimal.
(a) K 10
(b) K 20
(c) K 30
Changing number of agents N. we let K 10, 20, 30 and change N for each K. 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 insensitive to the change of K.
Figure 3:
In Figure 3, we study the performance of our algorithms when the number of agents varies. We set K 10, 20, 30, 0.005, 7) 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 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 to 1, i.e., W1 1, see Figure 4(a); (ii) set the non-zero entries in each row of W all to be number of neighbues see Figure 4(b). We fix = 0.1, K = 10, t 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 number of neighbors of each agent increases. FedNPG performs better when using equal weights.
25
300
25
200
150
125
12.
10
10
30
Inrador
(a) Random weights
(b) Equal weights
Figure 4: Changing communication network topology. We change the number of neighbors of each agent. (i) In Figure 4(a), randomly generalize the weights of the graph such that each row of W sum up to I; (ii) In Figure 4(b), we set the non-zero entries each row of W all to be 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.
H.1 Discussion on the Experiments
Note that even though there are many existing works in federated RI., none of the existing works, to the best of our knowledge, studies federated multi-tasks RL in the decentralized setting. Therefore,
65

---

we are not able to compare our work with existing works. However, here we include comparison between FedNPG and naive baseline without the Q-tracknn technique (line Algorithm l).
45
35
V,
N- tracking
tracking
N 30, tracking:
25
N- tracking
tracking.x
= 20, tracking:x
15-
10
20
25
Figure 5: Comparison between FedNPG and a naive baseline without the Q-tracking technique. The plot shows that while FedNPG converges within a few iterates, the algorithm without Q-tracking diverges, confirming the positive role Q-tracking ensuring convergence.
For this plot, we use the standard ring graph (Eq. 312). We the size of the maze K = 30, learning rate 17 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 few iterates, the algorithm without Q-tracking diverges, confirming the positive role Q-tracking in ensuring convergence.
66

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: we clearly state in the abstract and introduction the claims we made, including the contributions made in the paper and important assumptions and limitations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: we clearly state our assumptions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers penalize honesty concerning limitations.
will be specifically instructed
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
67

---

Justification:
we provide the full set of assumptions and complete (and correct) proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
68

---

Answer:
[No]
Justification: The experiments are simple and can be easily reproduced by following the instructions in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.. ec/
onnooicy))y for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nniss. ct/pcc/pplccc cec/public/pae Seriiies/CodSSubbe sssssssoiccyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experiment details are included in Section H. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[No]
Justification: stochasticity is not critical in our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
69

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 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 figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
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 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics //tp:///eeuuueeeeeeeeeeee tttpp////rrrpp..cpppbbtttt////// htt.lii//Ehiistuuiieeeoo cetthhissuieeeeeeeeeeeeene
Answer: [Yes]
Justification: the research conducted in the paper conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS 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., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: this is theoretical paper and it has no societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact 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.
70

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. 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, scraped datasets)?
Answer: [NA]
Justification: the paper aims to provide better understanding on existing algorithms and thus poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 require this, but we encourage authors to take this into account and make 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 dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
71

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
72


Reviews:
[{"review_id": "cBda0JHwDO", "reviewer": "Reviewer_bXwg", "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.", "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. \n\nCan the authors give some examples about the mixing matrix $W$ and show how to obtain the matrix $W$?\n\nI am happy to change the score according to the answers.", "limitations": "The authors need to more clearly address the limitations on the required information of the proposed algorithms.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The strengths of the paper are summarized as below.\n+ The paper considers federated reinforcement learning in a decentralized setting, which is challenging and closely related to the concerns of the community.\n+ The paper develops algorithms for different cases with tabular settings and function approximation settings.\n+ The paper gives the first rigorous analysis on the convergence rate of the FedNPG and FedNAC, which illustrates some insights including the impact of the spectral radius $\\sigma$ on the performance.", "weaknesses": "The proposed algorithm aggregates the neighborhood information by a mixing matrix $W$. However, it is unclear how to obtain the matrix $W$ in the practical decentralized setting. It would be better to have more explanations on this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer bXwg\n\nThank you for your feedback. Below We address your concerns. If our responses resolve your questions, we'd appreciate your consideration in raising the score. For any remaining issues, please don't hesitate to let us know.\n\n> **(Weaknesses) how to obtain the mixing matrix $W$ in practice**\n\nThere are several standard designs for $W$, such as uniform weights (where each agent assigns equal weight to itself and all its neighbors), Metropolis-Hasting weights (based on the degree of each node) [1], and Laplacian-based weights [2], with the aim that the designed $W$ agrees with the graph topology while mixing fast. Some papers also propose optimization methods to find $W$, see [3] for example.\n\n> **examples of the mixing matrix $W$**\n\nWe are happy to provide the following examples:\n\n- In the server-client setting, the mixing matrix is a rescaled all-one matrix.\n\n\n- In our experiment we assume the commucation network is a standard ring graph whose corresponding mixing matrix is given in Eq.(304) in Appendix H.\n\n- In the star network [2], one central agent communicates with all others and peripheral agents only communicate with the center. It's corresponding mixing matrix is given by\n[[1/4  1/4  1/4  1/4],\n[1/2   1/2  0  0],\n[1/2   0  1/2  0],\n[1/2   0  0  1/2]]\nwhere we assume $N=4$.\n\n- In random network [1], the connections of the nodes are random.\n\n> **regarding the aggregated policy $\\bar \\pi^{(t)}$**\n\nWe want to clarify that in the formal version of all our theorems, we provide consensus error bounds which demonstrate the local policies converge to the aggregated policy $\\bar \\pi^{(t)}$, i.e., there is no need to construct the aggregated policy $\\bar \\pi^{(t)}$ in practice.  Please see (47) (exact entropy-regularized FedNPG), (65) (inexact entropy-regularized FedNPG), (72) (exact vanilla FedNPG), (93) (inexact vanilla FedNPG) and (129) (FedNAC). They show that analyzing the convergence of $\\bar \\pi^{(t)}$ is meaningful and directly relevant to the behavior of the local policies in the decentralized setting.\n\n> **The authors need to more clearly address the limitations on the required information of the proposed algorithms.**\n\nWe speculate that the reviewer is inquiring about the specific information each agent needs to know and share for the algorithms to function properly. Please let us know if our interpretation is incorrect. To address this, we will clarify in the paper that each agent $i$ only needs to know its local reward function $r_i$, its neighbors and the corresponding weights $w_{ij}$. No global information or centralized computation is required during the algorithm execution, and agents only share local policy and Q-function estimates with neighbors. \n\n---\n\nReference:\n\n[1] Y Dandi et al. (2022). Data-heterogeneity-aware mixing for decentralized learning.\n\n[2] CC Chiu et al. (2023). Laplacian matrix sampling for communication-efficient decentralized learning.\n\n[3] L Xiao, S Boyd (2004). Fast linear iterations for distributed averaging.\n\n[4] Qu G, Li N (2017). Harnessing smoothness to accelerate distributed optimization[J]. \n\n[5] Zhao et al (2022). BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7eTK2qpcve", "reviewer": "Reviewer_tByy", "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.", "questions": "None,", "limitations": "None.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The convergence results are strong in that the dependence on $T$ is reasonable and the dependence on the sizes of the state and action spaces is weak.\n\nI appreciate the high-level discussion in Appendix B and the over-arching research goal of trying to understand multi-task learning from a mathematical point of view.", "weaknesses": "The decision to defer a careful comparison to related work to the Supplementary Material is questionable.\n\nLines 100-101:\n\"To the best of our knowledge, the proposed federated NPG and NAC methods are the first policy\n101 optimization methods for multi-task RL that achieve explicit non-asymptotic global convergence\n102 guarantees in terms of iteration and sample complexities, allowing for fully decentralized communi-\n103 cation without any need to share local reward/task information.\"\n\nI 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.\n\n\nLine 215: You have $\\sigma=0$ for a fully connected graph ... is \"client-server\" the best way to describe this?\n\nWhile 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.\n\n\nAlso, let me just nitpick the way a few of the examples relate to the paper:\nIt 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer tByy\n \nThank you for your comments. Below we answer your questions point-by-point. If these clarifications address your primary concerns, we'd appreciate your consideration of increasing your score. Certainly, please don't hesitate to request any further clarification.\n \n> **defer related work to the Supplementary Material**\n\nThank you for your feedback. Our decision was driven by the page limitation and the extensive technical content in the main paper. We'll put the related work to the main paper if this work is accepted and an extra page is allowed.\n\n>**regarding our claim: federated NPG and NAC methods are the first policy optimization methods for multi-task RL that achieve explicit non-asymptotic global convergence guarantees in terms of iteration and sample complexity.**\n\n- We thank the reviewer for bringing this up, and apologize for missing the early literature. \n\n- We will adjust our claim to the following:\n\n   *the proposed federated NPG and NAC methods are the first natural policy gradient based methods for multi-task RL that achieve explicit non-asymptotic global convergence guarantees in terms of iteration and sample complexity.*\n\n- We want to point out that [ZAD+21] studied decentralized PG and did not provide sample complexity analysese, as they assume the advantage function is obtained by oracle. Besides, our entropy-regularized FedNPG has last-iterate convergece guarantee while their algorithm doesn't, even though they also use entropy regularization, and the iteration complexity of ours is better than [ZAD+21] as we leverage NPG-based updates. We'll add a brief comparison with [ZAD+21] in our paper to highlight the distinctions of our results.\n\n> **You have $\\sigma$ for a fully connected graph ... is \"client-server\" the best way to describe this?**\n\n- We appreciate your attention to this detail and will add the following clarification in our updated paper:\n\n*In our paper, we use the term \"server-client\" to refer to the centralized learning setting where there exists a central server that aggregates information from all agents (clients) and the distributes the aggregated information back to all agents. The mixing matrix $W$ of the server-client setting is $W=1/N \\boldsymbol{1}_N\\boldsymbol{1}_N^\\top$ and by Definition 3.2, the spectral radius $\\sigma$ is 0 for this case.*\n\n- The use of \"server-client\" to describe this centralized architecture is common in the decentralized learning literature ([1-3]).\n\n>**points in Appendix B.1 not addressed**\n\nWe want to clarify that our goal is to learn an optimal policy that maximizes the total values over all the agents, rather than hoping to maximize the individual value functions at each agent. \n\nIn line 575, by \"accelerating learning and improving performance by leveraging experiences gained from one task to another,\" we mean that our federated approach allows agents to collectively learn a policy that performs well across all tasks, which would not be possible if agents learned independently. \n\n> **concerns regarding the examples**\n\nWe acknowledge that real-world scenarios are often more complex. Our model represents a meaningful simplification to enable rigorous mathematical analysis, while still capturing essential features of federated multi-task RL problems. While current practice of some applications we envisioned may not be completely aligned with the setting of our federated RL framework, we hope that our algorithm designs might inspire their future adoption into practice.\n\n---\n\n[1] J Ma et al. (2021). Adaptive distillation for decentralized learning from heterogeneous clients.\n\n[2] R Gu et al. (2021). From server-based to client-based machine learning: A comprehensive survey.\n\n[3] H Kasyap et al. (2021). Privacy-preserving decentralized learning framework for healthcare system.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "79DzNuqgxO", "reviewer": "Reviewer_LgxC", "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.", "questions": "Please see the weaknesses part.", "limitations": "No further limitations to be addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is technically sound.\n2. The studied problem is well-motivated\n4. The results are solid and provide insightful relationship between the number of tasks and convergence rate.", "weaknesses": "1. The learning objective function is less general. When the rewards are different, a better learning goal is to find local optimal policies for different tasks (agents).\n2. The technical novelty is less clear. For example, compared to the single task counterpart (Cen et al, 2021), is there any technical difficulties?\n\nCen et al., Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization, 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer LgxC \n\nThank you for your review and positive comments. Below we address you questions point-by-point. If our responses resolve your concerns, we'd appreciate your consideration of increasing your current score. Certainly, please also let us know if you have further questions.\n\n>**regarding learning objective**\n\nWhile we appreciate the perspective that finding local optimal policies for different tasks could be an alternative objective, we believe the problem of finding a single global policy that maximizes the average performance across all tasks is also valuable and necessary in many scenarios, especially when the goal is to collectively maximize the global performance (e.g., for fairness). Please refer to Appendix B for details. We also provide a few examples here:\n\n- The GridWorld experiment in our paper (Appendix H), where agents collectively learn to navigate a global map with partial information. This problem could be seen as a simplified version of the Unmanned Aerial Vehicle (UAV) Patrol Mission, each UAV patrols only in a specific area, and they need to collectively train a strategy utilizing information from the entire patrol range. \n\n- Multi-task robot control, where a single robot needs to perform well across various tasks.\n\n\nNote that our objective is well-established in the federated/decentralized RL literature, see [1-3] for example.\n\n>**regarding technical novelty**\n\nWe have a detailed discussion on our technical novelty in Appendix B.2. We also summarize our key points here to give you a better understanding of the technique difficulties we conquer: \n\nOne 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. \n\nBesides, due to the lack of global information sharing, care needs to be taken to judiciously balance the use of neighboring information (to facilitate consensus) and local data (to facilitate learning) when updating the policy. Compared to the centralized version of our proposed algorithms, a much more delicate theoretical analysis is required to prove our convergence results. For example, the key step to establish the convergence rate of the single-agent exact entropy-regularized NPG is to form the 2nd-order linear system in Eq.(47) in Cen et al., 2021, while in our corresponding analysis, a 4th-order linear system in Lemma 1 is needed, where the inequality in each line is non-trivial and requires the introduction of some intricate and novel auxiliary lemmas, see appendix D.\n\n---\n\n[1] S Zeng et al. (2021) A Decentralized Policy Gradient Approach to Multi-Task Reinforcement Learning.\n\n[2] K Zhang et al. (2018) Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents.\n\n[3] T Chen et al. (2022) Communication-Efficient Policy Gradient Methods for Distributed Reinforcement Learning.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oK1YJW81lJ", "reviewer": "Reviewer_vHsi", "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.", "questions": "See the section above.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The presentation is mostly clear. The theoretical results are solid and seem to be the first in the federated setting.", "weaknesses": "(1) Calling the setting \"multi-task RL\" is a bit confusing. Since each agent has its own reward function, which can be misaligned with other agents' reward functions, assuming that all agents are willing to collaborate to reach a common goal (maximizing the averaged reward) can be unreasonable. For example, suppose there are only three agents, and $r_1=r_2=-r_3$. In this case, the optimal policy for the averaged reward is the same as the local optimal policy for agents 1 and 2, but it is the exact opposite of what agent 3 wants. Therefore, there is no reason to assume that agent 3 is willing to collaborate. Perhaps directly calling the setting \"cooperative RL\" is more suitable.\n\n(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?\n\n(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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer vHsi\n\nThank you for your time in reviewing our paper. We appreciate your positive feedback. Below We address your points. If our responses adequately address your concerns, we would be grateful if you could consider increasing your current score. And we are happy to answer your additional questions.\n\n>**(W1) regarding the name \"multi-task RL\"**\n\nWe understand your concern about the potential confusion between \"multi-task RL\" and the cooperative nature of our setting. However, we believe that \"multi-task RL\" and \"cooperative RL\" are not mutually exclusive terms, as they describe different aspects of the problem:\n\n1. \"Multi-task RL\" refers to the fact that each agent has a different reward function, corresponding to different tasks or objectives within the same environment.\n2. \"Cooperative\" describes the agents' willingness to work together towards a common goal, in this case maximizing the averaged reward\n\nWe have explicitly specified in our paper that we are considering a cooperative setting within the multi-task framework. This approach is consistent with existing literature in the field. For example, [1] and [2] consider respectively the cooperative and adversarial settings within multi-task RL, demonstrating that the term \"multi-task\" does not inherently imply either cooperation or competition.\n\n>**(W2) The convergence rate of federated NAC seems to be much worse (especially in terms of the dependence on $1/(1-\\gamma)$) compared with that of federated Q-learning. Is there a fundamental reason behind it?**\n\nWe want to clarify that our setting is different that of Federated Q-learning (e.g, Woo et al. 2023). Woo et al. 2023 considers the server-client setting, where all the agents share the same environment (both transition kernel and reward function), so the local value functions are in fact the same and no environment heterogeneity is tackled. \n\n>**Suppose that we do not change the goal (which is to have global optimality with respect to the original model not the regularized one) but use regularization as a means for algorithm design. By letting $\\tau$ go to zero at an appropriate rate, or choosing $\\tau$ based on the required accuracy, what is the iteration and sample complexity of entropy-regularized NAC? Do we get $\\varepsilon^{-2}$ or something worse?**\n\nThank you for your question.\nSetting $\\tau=\\frac{(1-\\gamma)\\varepsilon}{4\\log |A|}$ guarantees $V^\\star_\\tau=V^\\star$ and ensures we do not change the goal (see (25) in [3]). Here we adopt this choice of $\\tau$ and let $\\eta=\\eta_0$ defined in Theorem 3.6. Then similar as in Remark D.1 in our paper, by employing fresh samples for the policy evaluation of each agent at every iteration, set $\\varepsilon_q$ in Theorem 3.8 to be $\\varepsilon_q = \\mathcal{O}\\left(\\frac{\\tau^2\\varepsilon}{\\gamma^2N\\sigma^2+(1-\\sigma)^2\\tau^2(1-\\gamma)^6}\\right),$ and invoke the union bound over the iteration complexity $\\widetilde{\\mathcal{O}} \\left(\\frac{N\\sigma^2}{\\tau^2}+\\frac{1}{1-\\gamma}\\right)$, we could give a loose upper bound of sample complexity of entropy-regularized FedNPG as\n$$\\widetilde{\\mathcal{O}} \\left(\\frac{N(N\\sigma^2+\\tau^2)^2}{\\tau^4\\varepsilon^2}\\left(\\frac{N\\sigma^2}{\\tau^2}+\\frac{1}{1-\\gamma}\\right)\\right).$$\n\nHere we only highlight $\\varepsilon$-dependency to simplify the expressions.\n\n- When $\\sigma=0$ (the server-client setting), the above complexity becomes $\\widetilde{\\mathcal{O}} \\left(\\varepsilon^{-2}\\right)$, recovering that of single-agent entropy-regularized NPG ([3]).\n\n- When $\\sigma$ is close to 1, the above complexity becomes $\\widetilde{\\mathcal{O}} \\left(\\varepsilon^{-8}\\right)$, which is worse than the bound for inexact vanilla FedNPG $\\widetilde{\\mathcal{O}} \\left(\\varepsilon^{-3.5}\\right)$ presented in (19). Therefore, FedNAC focused on unregularized case as it has better rates when the goal is to solve the unregulairzed problem. \n\n- The reason why the bound for the entropy-regularized case is worse may be due to proof artifacts as we need to address the complicated interplay between consensus errors and optimization errors (recall that simiar to the single-agent case, in our federated setting, vanilla FedNPG and entropy-regularzied FedNPG also require different proof frameworks), and we leave tightening the bound for future work. \n\n---\n\n[1] S Zeng et al. (2021) A Decentralized Policy Gradient Approach to Multi-Task Reinforcement Learning.\n\n[2] A Anwar and A Raychowdhury (2021). Multi-task federated reinforcement learning with adversaries.\n\n[3] S Cen et al. (2023). Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)