Year: 2021

Abstract:
Actor-critic (AC) algorithms have been widely adopted in decentralized multi-agent systems to learn the optimal joint control policy. However, existing decentralized AC algorithms either need to share agents’ sensitive information, e.g., local actions and policies , or are not sample and communication-efficient. In this work, we develop two decentralized AC and natural AC (NAC) algorithms that are sample and communication-efficient and avoid sharing agents’ local actions and policies . In both algorithms, agents share only noisy rewards and adopt mini-batch local policy gradient updates to improve sample and communication efficiency. Particularly for decentralized NAC, we develop a decentralized Markovian SGD algorithm with an adaptive mini-batch size to efficiently compute the natural policy gradient. Under Markovian sampling and linear function approximation, we prove that the proposed decentralized AC and NAC algorithms achieve the state-of-the-art sample complexities O( −2 ln −1) and O( −3 ln −1), respectively, and achieve an improved communication complexity O( −1 ln −1). Numerical experiments demonstrate that the proposed algorithms achieve lower sample and communication complexities than the existing decentralized AC algorithm.

heading: 1 INTRODUCTION
text: Multi-agent reinforcement learning (MARL) has achieved great success in various application domains, including control (66; 10; 51), robotics (64), wireless sensor networks (24; 67), intelligent systems (71), etc. In MARL, a set of fully decentralized agents interact with a dynamic environment following their own policies and collect local rewards, and their goal is to collaboratively learn the optimal joint policy that achieves the maximum expected accumulated reward.
Classical policy optimization algorithms have been well developed and studied, e.g., policy gradient (PG) (49), actor-critic (AC) (23) and natural actor-critic (NAC) (37; 7). In particular, AC-type algorithms are more computationally tractable and efficient as they take advantages of both policy gradient and value-based updates. However, in the multi-agent setting, decentralized AC is more challenging to design compared with the centralized AC, as the algorithm updates involve sensitive agent information, e.g., local actions, rewards and policies, which must be kept locally in the decentralized learning process. In the existing designs of decentralized AC, the agents need to share either their local actions (70; 69; 8; 36; 72; 27; 19; 26; 11) or local rewards (15; 33; 32) with their neighbors, and hence are not desired. This issue is addressed by Algorithm 2 of (70) at the cost of learning a parameterized model to estimate the averaged reward, yet this approach requires extra learning effort and the reward estimation can be inaccurate. Moreover, existing decentralized AC algorithms are not sample and communication-efficient, and do not have finite-time convergence guarantee, especially under the practical Markovian sampling setting. Therefore, we aim to address the following important question.
• Q1: Can we develop a decentralized AC algorithm that is convergent, sample and communicationefficient, and does not require sharing agents’ local actions and policies ?
On the other hand, as an important variant of the decentralized AC, decentralized NAC algorithm has not been formally developed and rigorously analyzed in the existing literature. In particular, a major challenge is that we need to develop a fully decentralized and computationally tractable scheme to
compute the inverse of the high dimensional Fisher information matrix, and this scheme must be both sample and communication efficient. Hence, we want to ask:
• Q2: Can we develop a computationally tractable and communication-efficient decentralized NAC algorithm that has a low finite-time sample and communication complexity?
In this study, we provide affirmative answers to the above two questions by developing fully decentralized AC and NAC algorithms that are sample and communication-efficient, and do not reveal agents’ local actions and policies. We also develop rigorous finite-time analysis of these algorithms under Markovian sampling. Our contributions are summarized as follows.

heading: 1.1 OUR CONTRIBUTIONS
text: We develop fully decentralized AC and NAC algorithms and analyze their finite-time sample and communication complexities under Markovian sampling. Our results and comparisons to existing works are summarized in Table 1 1. Our decentralized AC and NAC algorithms adopt the following novel designs to accurately estimate the policy gradient in an efficient way.
• Noisy Rewards: In a decentralized setting, local policy gradients (estimated locally by the agents) involve the average of all agents’ local rewards. To help agents estimate this averaged reward without revealing the raw local rewards , we let them share Gaussian-corrupted local rewards with their neighbor, and the variance of the Gaussian noise can be adjusted by each agent to reach its desired level.
• Mini-batch Updates: We apply mini-batch Markovian sampling to both the decentralized actor and critic updates. This approach 1) helps the agents obtain accurate estimations of the corrupted averaged reward; 2) significantly reduces the variance of policy gradient caused by Markovian sampling; and 3) significantly reduces the communication frequency and complexity.
Moreover, for our decentralized NAC algorithm, we additionally adopt the following design to compute the inverse of the Fisher information matrix in an efficient and decentralized way.
• Decentralized Natural Policy Gradient: By reformulating the natural policy gradient as the minimizer of a quadratic program, we develop a decentralized SGD with Markovian sampling that allows the agents to estimate the corresponding local natural gradients by communicating only
1In this table, Õ(·) hides all logarithm factors. In (25), the sample complexity has been established for various AC-type algorithms, and we compare with the best one. In (70), the Algorithm 1 needs to share local actions while the Algorithm 2 does not.
scalar variables with their neighbors. In particular, in order to minimize the sample complexity of the decentralized SGD, we set the batch size to be exponentially increasing.
Theoretically, for the first time, we provide finite-time convergence analysis of decentralized AC and NAC algorithms under Markovian sampling. Specifically, we prove that our decentralized AC and NAC algorithms achieve the overall sample complexities O( −2 ln −1) and O( −3 ln −1), respectively, and both match the state-of-the-art complexities of their centralized versions (60). Moreover, both decentralized algorithms achieve a significantly reduced overall communication complexity O( −1 ln −1). In particular, our analysis involves new technical developments. First, we need to characterize the bias and variance of (natural) policy gradient and stochastic gradient caused by the noisy rewards and the inexact local averaging steps, and control them with proper choices of batch sizes and number of local averaging steps. Second, when using decentralized Markovian SGD to compute the inverse Fisher information matrix, we need to use an exponentially increasing batch size to achieve an optimized sample complexity bound. Such a Markovian SGD with adaptive batch size has not been studied before and can be of independent interest.

heading: 1.2 RELATED WORK
text: Convergence analysis of AC and NAC. In the centralized setting, the AC algorithm was firstly proposed by (23) and later developed into the natural actor-critic (NAC) algorithm (37; 7). Specifically, (37) does not provide any convergence result, while (22; 5) and (20; 6; 7) establish the asymptotic convergence rate of centralized AC and NAC, respectively, which is weaker than our finite-time convergence results. Furthermore, (54; 25; 38; 61; 56) and (54) establish the finite-time convergence rate of centralized AC and NAC, respectively. Please refer to Table 1 for their sample complexities. Moreover, (60) improve the finite-time sample complexities of the above works to the state-of-theart result for both centralized AC and NAC by leveraging mini batch sampling, and our sample complexities match these state-of-the-art results .
In the decentralized setting, a few works have established the almost sure convergence result of AC (15; 27; 47; 33), but they do not characterize the finite-time convergence rate and the sample complexity. To the best of our knowledge, there is no formally developed decentralized NAC algorithm.
Decentralized TD-type algorithms. The finite-time convergence of decentralized TD(0) has been obtained using i.i.d samples (52; 14; 53; 28) and Markovian samples (46; 53), respectively, without revealing the agents’ local actions, policies and rewards . Decentralized off-policy TD-type algorithms have been studied in (34; 45; 9; 12).
Decentralized AC in other MARL settings. Some works apply decentralized AC to other MARL settings that are very different from ours. For example, (44; 36; 17; 11; 57) studied adversarial game. (30) studied a mixed cooperative-competitive environment where each agent maximizes its own Q function (30). (11) proposed Delay-Aware Markov Game which considers delay in Markov game. (68; 31) studied linear control system and linear quadratic regulators instead of an MDP. (55) studied sequential prisoner’s dilemmas.
Policy gradient algorithms. Policy gradient (PG) and natural policy gradient (NPG) are popular policy optimization algorithms. (1) characterizes the iteration complexity (i.e., number of episodes) of centralized PG and NPG algorithms by assuming access to exact policy gradient. They also established a sample complexity result O( −6) in the i.i.d. setting for NPG, which is worse than the state-of-the-art result O( −3 ln −1) of both centralized NAC (60) and our decentralized NAC with Markovian samples. (3) proposes decentralized PG in a simple cooperative MARL setting, where all the agents share one action and the same policy, and they establish a iteration complexity in the order of O( −4). (13; 73) apply decentralized PG to Markov games. (2) applies decentralized NPG to a different cooperative MARL setting where each agent observes its own state, takes its own action and has access to these information of its neighbors.
Value-based algorithms. Value-based algorithms have also been develop for MARL. Specifically, (21; 18) develop distributed Q-learning in a simplified cooperative MARL setting, where the agents share a joint action. In particular, (18) characterizes the convergence rate of a value function-based convergence error, which is a different optimality measure from that of AC-type algorithms. (35) applies distributed Q-learning to another cooperative MARL setting, where each agent observes
its own state and takes its own action. It establishes an asymptotic convergence guarantee, and no convergence rate is given. (40) develops a value propagation algorithm that uses primal-dual method to minimize a soft Bellman error in the MARL setting. Under an assumption that the variance of the stochastic gradient is uniformly bounded, it establishes a non-asymptotic convergence rate to an approximate stationary point.

heading: 2 REVIEW OF MULTI-AGENT REINFORCEMENT LEARNING
text: In this section, we first introduce some standard settings of RL. Consider an agent that starts from an initial state s0 ∼ ξ and collects a trajectory of Markovian samples {st, at, Rt}t ⊂ S × A × R by interacting with an underlying environment (with transition kernel P) following a parameterized policy πω with induced stationary state distribution µω. The agent aims to learn an optimal policy that maximizes the expected accumulated reward J(ω) = (1− γ)E [∑∞ t=0 γ tRt ] , where γ ∈ (0, 1) is a discount factor. The marginal state distribution is denoted as Pω(st) and the visitation measure is defined as νω(s) := (1− γ) ∑∞ t=0 γ
tPω(st = s), both of which depend on the policy parameter ω ∈ Ω and the transition kernel P . We also define the mixed transition kernel Pξ(·|s, a) := γP(·|s, a) + (1− γ)ξ(·), whose stationary state distribution is known to be νω . In the multi-agent RL (MARL) setting, M agents are connected via a fully decentralized network and interact with a shared environment. The network topology is specified by a doubly stochastic communication matrix W ∈ RM×M . At any time t, all the agents share a common state st. Then, every agent m takes an action a(m)t following its own current policy π (m) t (·|st) parameterized by ω (m) t . After all the actions at := {a (m) t }Mm=1 are taken, the global state st transfers to a new state st+1 and every agent m receives a local reward R (m) t . In this MARL setting, each agent m can only access the global state {st}t, its own actions {a(m)t }t and rewards {R (m) t }t and policy π (m) t . Next,
define the joint policy πt(at|st) := ∏M m=1 π (m) t (a (m) t |st) parameterized by ωt = [ω (1) t ; . . . ;ω (M) t ],
and define the average reward Rt := 1M ∑M m=1R (m) t . The goal of the agents is to collaboratively learn the optimal joint policy that maximizes the expected accumulated average reward J(ω) := (1− γ)E [∑∞ t=0 γ tRt
∣∣∣s0 ∼ ξ]. Throughout, we consider the setting that the agents keep interacting with the environment and observing a trajectory of MDP transition samples, which are further used to learn the optimal joint policy.

heading: 3 SAMPLE AND COMMUNICATION-EFFICIENT DECENTRALIZED AC
text: In this section, we propose a decentralized actor-critic (AC) algorithm that is sample and communication-efficient and avoids revealing agents’ local actions, policies and raw rewards .
We first consider a direct extension of the centralized AC to the decentralized case. As each agent m has its own policy π(m), it aims to update the policy parameter ω(m) using the local policy gradient ∇ω(m)J(ω). Under linear approximation of the value function Vθ(s) ≈ φ(s)>θ where φ(s) is the feature vector, the local policy gradient has the following stochastic approximation.
∇ω(m)J(ωt)≈ [ Rt + γφ(s ′ t+1) >θ (m) t − φ(st)>θ (m) t ] ψ (m) t (a (m) t |st), (1)
where a(m)t ∼ π (m) t (·|st), st+1 ∼ Pξ(·|st, at), s′t+1 ∼ P(·|st, at). (2)
Here, θ(m)t is agent m’s critic parameter and ψ (m) t (a (m) t |st) = ∇ω(m) lnπ (m) t (a (m) t |st) is the local score function. It is clear that both θ(m)t and ψ (m) t (a (m) t |st) can be obtained/computed by agent m using the local information. However, the average reward Rt requires agent m aggregating the local rewards from all the other agents, which raises concerns. In the existing literature on decentralized AC, this issue is avoided by either 1) sharing the agents’ actions with each other instead (70; 69; 8; 36; 72; 27; 19; 26; 11), yet the action information is also highly sensitive; or 2) learning a parameterized model to estimate the average reward (70), which requires extra learning effort and does not provide an accurate estimation. Hence, we are motivated to develop a simpler approach that provides accurate estimation of the average reward while avoids sharing raw local rewards .
1. Efficient Policy Gradient Estimation. We propose a decentralized policy gradient estimation scheme that improves the sample and communication efficiency and avoids revealing the agents’ local actions, policies and raw rewards . First, in order for each agent to estimate the average reward Rt in eq. (1), we let each agent m generate a noisy local reward R̃(m)t = R (m) t (1 + e (m) t ) and share with other agents, where e(m)t ∼ N (0, σ2m) 2. The noise variance is determined by the agent based on its desired level. Specifically, every agent m first initializes its local estimation of the averaged reward R (m)
t using its own noisy reward, i.e., R (m) t,0 = R̃ (m) t . Then, each agent m performs decentralized
local averaging with its neighbors Nm for T ′ iterations, i.e.,
R (m) t,`+1 = ∑ m′∈NmWm,m′ R (m) t,` , ` = 0, 1, . . . , T ′ − 1. (3)
After that, agent m obtains the final estimate R (m) t := R (m) t,T ′ . It can be shown that R (m) t converges to the averaged noisy reward 1M ∑M m=1 R̃ (m) t exponentially fast. Ideally, by averaging these noisy local rewards over the M agents, the variance of the noise in the final estimation will be scaled by a factor of 1M . Therefore, to obtain an accurate estimation, the network needs to have a sufficiently large number of agents, which does not always hold in practice.
To address this issue, we let each agent m collect a mini-batch of N Markovian samples in each iteration t to estimate the local policy gradient, which then takes the following form.
∇̂ω(m)J(ωt) = 1
N (t+1)N−1∑ i=tN [ R (m) i + γφ(s ′ i+1) >θ (m) t − φ(si)>θ (m) t ] ψ (m) t (a (m) i |si), (4)
where R (m)
i is an estimation of Ri obtained by agent m following the process described in eq. (3).
Intuitively, each R (m)
i is corrupted by a zero-mean noise with variance O( 1M ) due to averaging over the agents. Then, the mini-batch samples further help scale the noise variance by a factor of 1N . Consequently, with a sufficiently large batch size N , we can obtain an accurate estimation of the averaged reward and hence the policy gradient. To summarize, our decentralized policy gradient estimation scheme has the following advantages.
• Avoid sharing raw rewards: The agents share only noisy rewards R̃(m)t with their neighbors, and the noise variance can be adjusted based on the desired level such thatR(m)t is unknown to the other agents. This is in contrast to other decentralized AC algorithms where the agents need to either share local actions, rewards or collaboratively learn an additional parameterized reward model.
• Sample-efficient: The mini-batch updates help greatly suppress the noise variance of the local policy gradient in (4) and improve its estimation accuracy. On the other hand, mini-batch policy gradient also helps reduce the optimization variance caused by Markovian sampling and leads to a good finite-time sample complexity as we prove later. We note that there is no trade-off between noise variance and sample efficiency here, because for highly noisy local rewards we can choose a large batch size to suppress the overall estimation error to the desired level.
• Communication-efficient: The mini-batch updates also significantly reduce the communication frequency as well as the complexity as we prove later. In comparison, the existing decentralized AC requires to perform one communication round per Markovian sample.
Remark. We note that the local mini-batch policy gradient update in eq. (4) can be computed in an accumulative way by the agent when observing the mini-batch of transition samples on the fly. There is no need to store all these samples and perform a large batch computation.
2. Fully Decentralized Critic Update. The critic parameters of the agents are updated following the standard decentralized TD-type algorithm. Specifically, consider the t-th local critic update of each agent m. It first collects a mini-batch of Nc Markovian samples. Then, starting from a fixed initialization θ(m)t,0 = θ−1, agent m performs Tc iterations of decentralized TD updates as follows, where {st}t∈N follows the transition kernel P and a(m)t ∼ π (m) t (·|st): for t′ = 0, 1, ..., Tc − 1,
θ (m) t,t′+1 = ∑ m′∈Nm Wm,m′ θ (m′) t,t′ + β Nc (t+1)Nc−1∑ i=tNc [ R (m) i + γφ(si+1) >θ (m) t,t′ − φ(si) >θ (m) t,t′ ] φ(si). (5)
2More generally, any noise with zero mean and variance σ2m will work.
Then, the updated critic parameter is set to be θ(m)t := θ (m) t,Tc
. To further reduce the consensus error, we perform additional T ′c steps of local model averaging, as also adopted in (12). The pseudo code of the entire decentralized AC algorithm is summarized in Algorithms 1 and 2 below.
Algorithm 1 Decentralized Actor-Critic Initialize: Actor-critic parameters ω0, θ−1. for actor iterations t = 0, 1, . . . , T − 1 do
I Critic update on θt: by Algorithm 2. I Collect N Markovian samples by eq. (2). for agents m = 1, ...,M in parallel do
I Send noisy local rewards and perform T ′ local average steps following eq. (3). I Compute the estimated local policy gradient ∇̂ω(m)J(ωt) following eq. (4). I Actor update on ωt: ω
(m) t+1 = ω (m) t + α∇̂ω(m)J(ωt).
end end Output: ωT̃ with T̃ uniform∼ {1, 2, . . . , T}.
Algorithm 2 Decentralized TD (critic update) Initialize: Critic parameter θt,0 = θ−1. for critic iterations t′ = 0, 1, . . . , Tc − 1 do
I Collect Nc Markovian samples following policy πt and transition kernel P . for agents m = 1, ...,M in parallel do
I Send local critic parameters. I Decentralized TD update in eq. (5).
end end for iterations t′ = Tc, ..., Tc + T ′c − 1 do
for agents m = 1, ...,M in parallel do I θ(m)t,t′+1 = ∑ m′∈NmWm,m′ θ (m′) t,t′ .
end end Output: θt = θt,Tc+T ′c .

heading: 4 FINITE-TIME CONVERGENCE ANALYSIS OF DECENTRALIZED AC
text: In this section, we analyze the finite-time convergence of Algorithm 1 and characterize the sample and communication complexities. All the notations and universal constants are summarized in Appendices A & F respectively. We first introduce the following standard assumptions that have been widely adopted in the existing literature. Assumption 1. Regarding the transition kernels P,Pξ , denote µω, νω respectively as their stationary state distributions under policy πω and denote P,Pξ respectively as their marginal state distributions. Then, there exist constants κ > 0 and ρ ∈ (0, 1) such that for all t ≥ 0,
sup s∈S
dTV ( P (st | s0 = s) , µω ) ≤ κρt, sup
s∈S dTV
( Pξ (st | s0 = s) , νω ) ≤ κρt (6)
where dTV (P,Q) denotes the total-variation distance between probability measures P and Q. Assumption 2. There exist constants Cψ, Lψ, Lπ > 0 such that for all ω, ω̃ ∈ Ω, s ∈ S and a ∈ A, ‖ψω(a|s)‖ ≤ Cψ , ‖ψω̃(a|s)− ψω(a|s)‖ ≤ Lψ‖ω̃ − ω‖ and dTV ( πω̃(·|s), πω(·|s) ) ≤ Lπ‖ω̃ − ω‖. Assumption 3. There exists Rmax > 0 such that for any agent m and any Markovian sample (s, a, s′), we have 0 ≤ R(m)(s, a, s′) ≤ Rmax. Assumption 4. The feature vectors satisfy ‖φ(s)‖ ≤ 1 for all s ∈ S . There exists a constant λφ > 0 such that λmin ( Es∼µω [φ(s)φ(s)>] ) ≥ λφ for all ω. Assumption 5. The communication matrix W ∈ RM×M of the decentralized network is doubly stochastic, and its second largest singular value satisfies σW ∈ [0, 1).
Assumption 1 has been widely considered in the existing literature (4; 38; 63; 58; 42; 60; 12) and it holds for any time-homogeneous Markov chains with finite-state space and any uniformly ergodic Markov chains. Assumption 2 introduces boundedness and Lipschitzness to the policy and its associated score function (65; 60), and holds for many parameterized policies such as Gaussian policy (25) and Boltzman policy (16). Assumption 4 can always hold by normalizing the feature vector φ(s) Assumption 5 is widely used in decentralized optimization (43; 41) and multi-agent reinforcement learning (46; 53; 12), which ensures that all the decentralized agents can reach a global consensus.
With the above assumptions, we obtain the following finite-time convergence result of the decentralized AC algorithm. Throughout, we follow (60; 56) and define the critic approximation error as ζcriticapprox := supω Es∼νω (Vω(s)−φ(s)>θ∗ω)2 where θ∗ω is the optimal critic parameter (see its definition right before Lemma D.3 in Appendix D). We also define sample complexity as the total number of Markovian samples required for achieving E[‖∇J(ω)‖2] ≤ . All the universal constants are listed in Appendix F.
Theorem 1. Let Assumptions 1–5 hold and adopt the hyperparameters of the decentralized TD in Algorithm 2 following Lemma D.4. Choose α ≤ 14LJ , T ′ ≥ lnM 2 lnσ−1W
. Then, the output of the decentralized AC in Algorithm 1 has the following convergence rate.
E [∥∥∇J(ωT̃ )∥∥2]≤ 4RmaxTα +4(c4σ2T ′W +c5β2σ2T ′cW )+4c6(1− λB8 β)Tc+ 4c7N + 4c8Nc +64C2ψζcriticapprox.
Moreover, to achieve E [∥∥∇J(ωT̃ )∥∥2] ≤ for any ≥ 128C2ψζcriticapprox, we can choose T,N,Nc = O( −1) and Tc, T ′c, T ′ = O(ln −1). Consequently, the overall sample complexity is T (TcNc+N) = O( −2 ln −1), and the communication complexities for synchronizing linear model parameters and rewards are T (Tc + T ′c) = O( −1 ln −1) and TT ′ = O( −1 ln −1), respectively.
Remark. We note that the constraint on is naturally induced by the critic approximation error. In particular, if this approximation errors vanish, for example, when the dimension of features equals the number of states and the parameterized policy space is sufficiently expressive, then we can achieve arbitrarily small target accuracy.
To the best of our knowledge, Theorem 1 provides the first finite-time analysis of decentralized AC under Markovian sampling. To elaborate, under any pre-specified variance σ2m of the reward noise, our result shows that the gradient norm asymptotically converges to the order O(N−1 +N−1c + ζcriticapprox), which can be made arbitrarily close to the linear model approximation error ζcriticapprox by choosing sufficiently large batch sizes N,Nc. In particular, exact gradient convergence can be achieved when there is no model approximation error. The overall sample complexity of our decentralized AC is O( −2 ln −1), matching the state-of-the-art complexity result for centralized AC (60). Moreover, with proper choices of the batch sizes N,Nc = O( −1), the overall communication complexity is significantly reduced to O( −1 ln −1). The proof of Theorem 1 relies on developing several new algorithmic and technical developments to reduce the communication complexity of both the decentralized actor and critic updates while establishing tight convergence error bounds for both components. We further elaborate on these novel technical developments below.
• To achieve an overall reduced communication complexity, we adopt mini-batch updates in both the actor and critic steps to reduce the communication frequency, as opposed to the single sample-based update adopted in the existing work on decentralized TD learning (46). Specifically, in the analysis of the decentralized TD described in Algorithm 2 (see Lemma D.4), the mini-batch updates with batch size O( −1) substantially improve the communication complexity from O( −1 ln −1) to O(ln −1) while help achieve the state-of-the-art sample complexity. Eventually, this together with the mini-batch updates in the decentralized actor steps help achieve the desired overall low communication complexity.
• To achieve the state-of-the-art overall sample complexity, it is critical that the policy gradient vanishes fast, which further requires a fast convergence of the decentralized TD learning. However, although the standard Tc decentralized mini-batch TD updates can yield a small convergence error for the global critic model (i.e., the average of all local critic models), it still suffers from a relatively large consensus error. To resolve this issue, we introduce an additional T ′c global consensus steps in Algorithm 2 to reduce the consensus error. It is proved that a small number O(ln −1) of such steps suffices to yield a desired TD error.
• We inject random noises into the local raw rewards R(m)t to protect the information. These noises introduce additional Markovian bias and variance to the local policy gradients in (4). Fortunately, as proved in Lemma D.6, by applying mini-batch policy gradient updates, we are able to control the bias and variance induced by the noisy rewards to an acceptable level that does not affect the overall sample and communication complexities.

heading: 5 DECENTRALIZED NATURAL AC
text: Natural actor-critic (NAC) is a popular variant of the AC algorithm. It utilizes a Fisher information matrix to perform a natural policy gradient update, which helps attain the globally optimal solution in terms of the function value convergence. In this section, we develop a fully decentralized version of the NAC algorithm that is sample and communication-efficient.
Algorithm 3 Decentralized Natural Actor-Critic Initialize: Actor-critic parameters ω0, θ−1, natural policy gradient h−1. for actor iterations t = 0, 1, . . . , T − 1 do
I Critic update on θt: by Algorithm 2. for agents m = 1, ...,M in parallel do
for iterations k = 0, 1, . . . ,K − 1 do I Collect Nk Markovian samples following eq. (2). I Send R̃(m)i and z (m) i,` and perform T ′ and Tz local average steps, respectively.
I Estimate local gradient ∇̂ω(m)fωt(ht,k) following eqs. (8) and (4). I Perform SGD update in eq. (9).
end I Actor update on ωt: ω (m) t+1 = ω (m) t + αh (m) t .
end end Output: ωT̃ with T̃ uniform∼ {1, 2, . . . , T}.
A major challenge of developing fully decentralized NAC algorithm is computing the inverse Fisher information matrix-vector product involved in the natural policy gradient update. To explain, first recall the exact natural policy gradient update of the centralized NAC algorithm, i.e., ωt+1 = ωt + αF (ωt) −1∇J(ωt), where F (ωt) := Est∼νωt ,at∼πt(·|st) [ ψt(at|st)ψt(at|st)> ] is the Fisher information matrix. However, in the multi-agent case, it is challenging to perform the natural policy gradient update in a decentralized manner. This is because the Fisher information matrix F (ωt) is based on the concatenated multi-agent score vector ψt(at|st) = [ψ(1)t (a (1) t |st); ...;ψ (M) t (a (M) t |st)] and the inverse matrix-vector product F (ωt)−1∇J(ωt) is not separable with regard to each agent’s policy parameter dimensions. Next, we develop a fully decentralized scheme to implement the natural policy gradient update in the multi-agent setting.
First, note that the natural policy gradient update h(ωt) := F (ωt)−1∇J(ωt) is equivalent to the solution of a quadratic program, i.e.,
h(ωt) = arg min h fωt(h) :=
1 2 h>F (ωt)h−∇J(ωt)>h. (7)
Therefore, we can apply K steps of SGD with Markovian sampling to solve this problem and obtain an estimated natural policy gradient update. Specifically, starting from the initialization ht,0 = ht−1 (obtained in the previous iteration), in the k-th SGD step, we sample a mini-batch Bt,k 3 of Nk Markovian samples to estimate ∇fωt(h) as 1Nk ∑ i∈Bt,k ψt(ai|si)ψt(ai|si)
>ht,k − ∇̂J(ωt;Bt,k), where ∇̂J(ωt;Bt,k) is estimated in the same decentralized way as eq. (4) using the mini-batch of samples Bt,k. In particular, each agent m needs to compute the corresponding local gradient 1Nk ∑ i∈Bt,k ψ (m) t (a (m) i |si) [ ψt(ai|si)>ht,k ] − ∇̂ω(m)J(ωt;Bt,k), in which ψ (m) t (a (m) i |si) and ∇̂ω(m)J(ωt;Bt,k) can be computed/estimated by the agent m. Then, it suffices to obtain an estimate of the scalar ψt(ai|si)>ht,k, which can be rewritten as ∑M m=1 ψ (m) t (a (m) i |si)>h (m) t,k . This summation can be easily estimated by the decentralized agents through local averaging. Specifically, each agent m locally computes z(m)i,0 = ψ (m) t (a (m) i |si)>h (m) t,k and performs Tz steps of local averaging,
i.e., z(m)i,`+1 = ∑ m′∈NmWm,m′ z (m′) i,` , ` = 0, 1, . . . , Tz − 1. After that, the quantity Mz (m) i,Tz can be
proven to converge to the desired summation ∑M m=1 ψ (m) t (a (m) i |si)>h (m) t,k exponentially fast. Finally, the local gradient for agent m is approximated as
∇̂ω(m)fωt(ht,k) = M
Nk ∑ i∈Bt,k ψ (m) t (a (m) i |si)z (m) i,Tz − ∇̂ω(m)J(ωt;Bt,k). (8)
Then, the agent m performs the following SGD updates to obtain h(m)t := h (m) t,K .
h (m) t,k+1 = h (m) t,k − η∇̂ω(m)fωt(ht,k), k = 0, ...,K − 1. (9)
3Specifically, the mini-batch Bt,k contains sample indices { tN + ∑k−1 k′=0Nk′ , . . . , tN + ∑k k′=0Nk′ − 1 } .
We emphasize that the above mini-batch SGD updates use Markovian samples. In particular, as shown in Section 6, we need to develop an adaptive batch size scheduling scheme for this SGD in order to reduce its sample complexity. We summarize the decentralized NAC in Algorithm 3.

heading: 6 FINITE-TIME CONVERGENCE ANALYSIS OF DECENTRALIZED NAC
text: To analyze the decentralized NAC, we introduce the following additional standard assumptions. Assumption 6. There exists a constant λF > 0 such that λmin ( F (ω) ) ≥ λF > 0,∀ω ∈ Ω.
Assumption 7. There exists C∗ > 0 such that for ω∗ = arg maxω∈Ω J(ω) and any ω ∈ Ω,
Es∼νω,a∼πω(·|s) [(νω∗(s)πω∗(a|s)
νω(s)πω(a|s)
)2] ≤ C2∗ .
Assumption 6 ensures that the Fisher information matrix F (ω) is uniformly positive definite, and is also considered in (65; 29; 62). Assumption 7 regularizes the discrepancy between the stationary state-action distributions νω∗(s)πω∗(a|s) and νω(s)πω(a|s) (54; 59). We obtain the following finite-time convergence result of the decentralized NAC algorithm. Throughout, we follow (54; 60; 62) and define the actor approximation error as ζactorapprox :=
supω minhEs∼νω,a∼πω(·|s) [( ψω(a|s)>h − Aω(s, a) )2] . All universal constants are listed in Appendix F. Theorem 2. Let Assumptions 1–7 hold and adopt the hyperparameters of the decentralized TD in Algorithm 2 following Lemma D.4. Choose hyperparameters α ≤ min ( 1,
λ2F 4LJC2ψ , C2ψ 2LJ
) , β ≤ 1,
T ′ ≥ lnM 2 lnσ−1W , η ≤ 1 2C2ψ , Tz ≥ ln(3DJC
2 ψ)
lnσ−1W , K ≥ ln 3ln(1−ηλF /2)−1 , N ≥ 2304C4ψ(κ+1−ρ) ηλ5F (1−ρ)(1−ηλF /2)(K−1)/2
and Nk ∝ (1− ηλF /2)−k/2. Then, the output of Algorithm 3 satisfies
J(ω∗)− E [ J(ωT̃ ) ] ≤ c17 Tα + c18 ( 1− ηλF 2 )(K−1)/4 + c19σ Tz W + c20σ T ′ W + c21βσ T ′c W + c23√ Nc
+ c22
( 1− λB 8 β )Tc/2 + Cψ √ c16ζcriticapprox + c24ζ critic approx + C ∗ √ ζactorapprox.
Moreover, to achieve J(ω∗) − E [ J(ωT̂ ) ] ≤ for any ≥ 2Cψ √ c16ζcriticapprox + 2c24ζ critic approx +
2C∗ √ ζactorapprox, we can choose T = O( −1), N,Nc = O( −2), Tc, T ′c, T ′, Tz,K = O(ln −1). Consequently, the overall sample complexity is T (TcNc +N) = O( −3 ln −1), and the communication complexities for synchronizing linear model parameters and rewards are T (Tc+T ′c) = O( −1 ln −1) and TT ′ = O( −1 ln −1), respectively.
Theorem 2 provides the first finite-time analysis of fully decentralized natural AC algorithm. Our result proves that the function value optimality gap converges to the order O ( N −1/2 c + √ ζcriticapprox +√
ζactorapprox ) , which can be made arbitrarily close to the actor and critic approximation error by choosing a sufficiently large batch size Nc. In particular, exact global optimum can be achieved when there is no model approximation error. We note that the overall sample complexity of our decentralized NAC is O( −3 ln −1), matching the state-of-the-art complexity result for centralized NAC (60). Moreover, with the mini-batch updates, the overall communication complexity is significantly reduced to O( −1 ln −1). Similar to that of Theorem 1, our analysis of Theorem 2 also leverages the mini-batch decentralized TD updates to reduce the communication complexity and deal with the bias and variance of the local policy gradient introduced by noisy rewards. In addition, decentralized NAC uses mini-batch SGD with Markovian sampling to solve the quadratic problem in eq. (7). Here, we use a special geometrically increasing batch size scheduling scheme, i.e., Nk ∝ (1 − ηλF /2)−k/2, to achieve the best possible convergence rate under the total sample budget that ∑K k=1Nk = N and obtain the desired overall sample complexity result. Such an analysis of SGD with Markovian sampling under adaptive batch size scheduling has not been studied in the literature and can be of independent interests.

heading: 7 EXPERIMENTS
text: We simulate a fully decentralized ring network with 6 agents. Please refer to Appendix E for detailed environment setup. We implement four decentralized AC-type algorithms and compare their performance, namely, our Algorithms 1 and 3, an existing decentralized AC algorithm (Algorithm 2 of (70)) that uses a linear model to parameterize the agents’ averaged reward (we name it DAC-RP1 for decentralized AC with reward parameterization), and our proposed modified version of DAC-RP1 to incorporate minibatch, which we refer to as DAC-RP100 with batch sizeN = 100. For our Algorithm 1, we choose T = 500, Tc = 50, T ′c = 10, Nc = 10, T
′ = Tz = 5, β = 0.5, {σm}6m=1 = 0.1, and consider batch size choices N = 100, 500, 2000. Algorithm 3 uses the same hyperparameters as those of Algorithm 1 except that T = 2000 in Algorithm 3. For DAC-RP1, we set learning rates βθ = 2(t + 1)
−0.9, βv = 5(t + 1)−0.8 and batch size N = 1 as mentioned in (70). The modified DAC-RP100 adopts the same learning rates as Algorithm 1 with N = 100.
Figure 1 plots the accumulated reward J(ωt) v.s. communication and sample complexity. Each curve includes 10 repeated experiments, and its upper and lower envelopes denote the 95% and 5% percentiles of the 10 repetitions, respectively. For our decentralized AC algorithm (left two figures), its communication and sample complexities for achieving a high accumulated reward are significantly reduced under a larger batch size N . This matches our theoretical understanding in Theorem 1 that a large N helps reduce the communication frequency and policy gradient variance. In comparison, DAC-RP1 (with N = 1) has almost no improvement on the accumulated reward. Moreover, although the modified DAC-RP100 (with N = 100) outperforms DAC-RP1, its performance is much worse than our Algorithm 1 with N = 100. This performance gap is due to two reasons: (i) Both DAC-RP algorithms suffer from an inaccurate parameterized estimation of the averaged reward, and their mean relative reward errors are over 100%. In contrast, our noisy averaged reward estimation achieves a mean relative error in the range of 10−5 ∼ 10−4;(ii) Both DAC-RP algorithms apply only a single TD update per-round, and hence suffers from a large mean relative TD error (about 2% and 1% for DAC-RP1 and DAC-RP100, respectively)whereas our algorithms perform multiple TD learning updates per-round and achieve a smaller mean relative TD error (about 0.3%). For our decentralized NAC algorithm (right two figures), one can make similar observations and conclusions.

heading: 8 CONCLUSION
text: We developed fully-decentralized AC and NAC algorithms that are efficient and do not reveal agents’ local actions and policies . The agents share noisy reward information and adopt mini-batch updates to improve sample and communication efficiency. Under Markovian sampling and linear function approximation, we proved that our decentralized AC and NAC algorithms achieve the state-of-the-art sample complexities O( −2 ln −1) and O( −3 ln −1), respectively, and they both achieve a small communication complexity O( −1 ln −1). Numerical experiments demonstrate that our algorithms achieve better sample and communication complexity than the existing decentralized AC algorithm that adopts reward parameterization.

heading: A NOTATIONS
text: Norms: For any vector x, we denote ‖x‖ as its `2 norm. For any matrix X , we denote ‖X‖, ‖X‖F as its spectral norm and Frobenius norm, respectively.
Difference matrix: ∆ := I − 1M 11 >, where 1 denotes a column vector that consists of 1s.
Moments of random vectors: For a random vector X , we define its variance and covariance matrix as Var(X) := E‖X − EX‖2 and Cov(X) := E ( [X − EX][X − EX]> ) , respectively. It is well
known that E‖X‖2 = Var(X) + ‖EX‖2 and that Var(X) = tr[Cov(X)]. Score function: At any time t, The joint score function ψt(at|st) := ∇ω lnπt(at|st) can be decomposed into individual score functions ψ(m)t (a (m) t |st) := ∇ω(m) lnπ (m) t (a (m) t |st) as ψt(at|st) = [ψ (1) t (a (1) t |st), . . . , ψ (M) t (a (M) t |st)].
Reward functions: At any time t, we denoteR(m)t := R(m)(st, at, st+1) andRt := R(st, at, st+1), where R(s, a, s′) = 1M ∑M m=1R (m)(s, a, s′).
Policy gradient: The policy gradient theorem (50) shows that ∇J(ω) = Eνω [ Aω(s, a)ψω(s, a) ] . (10)
where Aω(s, a) := Qω(s, a) − Vω(s) denotes the advantage function. In the decentralized case, we have the approximations Vω(st) ≈ φ(st)>θ, Qω(st, at) ≈ Rt + γφ(s′t+1)>θ where s′t+1 ∼ P(·|st, at). Therefore, we can stochastically approximate the partial policy gradient as eq. (1), i.e., for m = 1, ...,M ,
∇ω(m)J(ωt)≈ [ Rt + γφ(s ′ t+1) >θ (m) t − φ(st)>θ (m) t ] ψ (m) t (a (m) t |st).
We also define the following mini-batch stochastic (partial) policy gradient. ∇̃ω(m)J(ωt) := 1N ∑(t+1)N−1 i=tN [ Ri + γφ(s ′ i+1) >θ (m) t − φ(si)>θ (m) t ] ψ (m) t (a (m) i |si).
∇̃J(ωt) := [ ∇̃ω(1)J(ωt); . . . ; ∇̃ω(M)J(ωt) ] .
Filtrations: We define the following filtrations for Algorithms 1 & 3.
Ft := σ ( {θ(m)t′ }m∈M,0≤t′≤t ∪ {si, ai, s′i+1, {e (m) i }m∈M} tN−1 i=0 ∪ {stN} ) .
F ′t := σ [ Ft ∪ σ ( {si, ai, s′i+1} (t+1)N−1 i=tN+1 )] .
Ft,k = σ [ Ft ∪ σ ( {si, ai, si+1, s′i+1, {e (m) i }m∈M}i∈∪k−1 k′=0Bt,k′ )] .

heading: B PROOF OF THEOREM 1
text: Theorem 1. Let Assumptions 1–5 hold and adopt the hyperparameters of the decentralized TD in Algorithm 2 following Lemma D.4. Choose α ≤ 14LJ , T ′ ≥ lnM 2 lnσ−1W
. Then, the output of the decentralized AC in Algorithm 1 has the following convergence rate.
E [∥∥∇J(ωT̃ )∥∥2]≤ 4RmaxTα +4(c4σ2T ′W +c5β2σ2T ′cW )+4c6(1− λB8 β)Tc+ 4c7N + 4c8Nc +64C2ψζcriticapprox.
Moreover, to achieve E [∥∥∇J(ωT̃ )∥∥2] ≤ for any ≥ 128C2ψζcriticapprox, we can choose T,N,Nc = O( −1) and Tc, T ′c, T ′ = O(ln −1). Consequently, the overall sample complexity is T (TcNc+N) = O( −2 ln −1), and the communication complexities for synchronizing linear model parameters and rewards are T (Tc + T ′c) = O( −1 ln −1) and TT ′ = O( −1 ln −1), respectively.
Proof. Concatenating all the agents’ actor updates in Algorithm 1, we obtain the joint actor update ωt+1 = ωt + α∇̂J(ωt). Then, the item 7 of Lemma D.5 implies that
J(ωt+1) ≥ J(ωt) +∇J(ωt)>(ωt+1 − ωt)− LJ 2 ∥∥ωt+1 − ωt∥∥2 = J(ωt) + α∇J(ωt)>∇̂J(ωt)− LJα 2
2 ∥∥∇̂J(ωt)∥∥2 (i)
≥ J(ωt) + α‖∇J(ωt)‖2 + α∇J(ωt)> ( ∇̂J(ωt)−∇J(ωt) ) − LJα2
∥∥∇̂J(ωt)−∇J(ωt)∥∥2 − LJα2∥∥∇J(ωt)∥∥2 (ii)
≥ J(ωt) + (α
2 − LJα2
) ‖∇J(ωt)‖2 − (α 2 + LJα 2 )∥∥∇̂J(ωt)−∇J(ωt)∥∥2
(iii)
≥ J(ωt) + α
4 ‖∇J(ωt)‖2 − α ∥∥∇̂J(ωt)−∇J(ωt)∥∥2 where (i) and (ii) use the inequalities ‖x‖2 ≤ 2‖x − y‖2 + 2‖y‖2 and x>y ≥ − 12‖x‖ 2 − 12‖y‖ 2 for any x, y ∈ Rd, respectively, and (iii) uses the condition that α ≤ 14LJ . Then, summing up the inequality above over t = 0, 1, . . . , T − 1 yields that
J(ωT ) ≥ J(ω0) + α
4 T−1∑ t=0 ‖∇J(ωt)‖2 − α T−1∑ t=0 ∥∥∇̂J(ωt)−∇J(ωt)∥∥2. Rearranging the equation above and taking expectation on both sides yields that
E ∥∥∇J(ωT̃ )∥∥2 = 1T T−1∑ t=0 E‖∇J(ωt)‖2
≤ 4 Tα E[J(ωT )− J(ω0)] + 4 T T−1∑ t=0 E [∥∥∇̂J(ωt)−∇J(ωt)∥∥2]
(i) ≤ 4Rmax Tα + 4c4σ 2T ′ W + 4c5β 2σ 2T ′c W + 4c6
( 1− λB 4 β )Tc
+ 4c7 N + 4c8 Nc + 64C2ψζ critic approx, (11)
where (i) uses the item 4 of Lemma D.5 and eq. (39) of Lemma D.6 (The condition of Lemma D.6 that T ′ ≥ lnM2 ln(σ−1) holds). This proves the error bound of Theorem 1.
Finally, for any ≥ 128C2ψζcriticapprox, it can be easily verified that the following hyperparameter choices make the error bound in (11) smaller than and also satisfy the conditions of this Theorem and those in Lemma D.4 that β ≤ min ( λB
8C2B , 4λB , 1−σ 2CB
) , Nc ≥ ( 2 λB + 2β ) 192C2B [1+(κ−1)ρ] (1−ρ)λB .
α = min ( 1, 1
4LJ
) = O(1)
β = min ( λB
8C2B ,
4
λB , 1− σ 2CB
) = O(1)
T = ⌈48Rmax
α
⌉ = O( −1)
T ′ = ⌈ 1
2 ln(σ−1) max
[ ln(48c4 −1), lnM ]⌉ = O ( ln( −1) )
T ′c = ⌈ ln(48c5β2 −1)
2 ln(σ−1)
⌉ = O ( ln( −1) ) Tc = ⌈ ln(48c6 −1) 2 ln[(1− λBβ/4)−1] ⌉ = O ( ln( −1)
) N = ⌈48c7 ⌉ = O( −1)
Nc = ⌈ max [48c7 , ( 2 λB + 2β )192C2B [1 + (κ− 1)ρ] (1− ρ)λB ]⌉ = O( −1) (12)

heading: C PROOF OF THEOREM 2
text: Theorem 2. Let Assumptions 1–7 hold and adopt the hyperparameters of the decentralized TD in Algorithm 2 following Lemma D.4. Choose hyperparameters α ≤ min ( 1,
λ2F 4LJC2ψ , C2ψ 2LJ
) , β ≤ 1,
T ′ ≥ lnM 2 lnσ−1W , η ≤ 1 2C2ψ , Tz ≥ ln(3DJC
2 ψ)
lnσ−1W , K ≥ ln 3ln(1−ηλF /2)−1 , N ≥ 2304C4ψ(κ+1−ρ) ηλ5F (1−ρ)(1−ηλF /2)(K−1)/2
and Nk ∝ (1− ηλF /2)−k/2. Then, the output of Algorithm 3 satisfies
J(ω∗)− E [ J(ωT̃ ) ] ≤ c17 Tα + c18 ( 1− ηλF 2 )(K−1)/4 + c19σ Tz W + c20σ T ′ W + c21βσ T ′c W + c23√ Nc
+ c22
( 1− λB 8 β )Tc/2 + Cψ √ c16ζcriticapprox + c24ζ critic approx + C ∗ √ ζactorapprox.
Moreover, to achieve J(ω∗) − E [ J(ωT̂ ) ] ≤ for any ≥ 2Cψ √ c16ζcriticapprox + 2c24ζ critic approx +
2C∗ √ ζactorapprox, we can choose T = O( −1), N,Nc = O( −2), Tc, T ′c, T ′, Tz,K = O(ln −1). Consequently, the overall sample complexity is T (TcNc +N) = O( −3 ln −1), and the communication complexities for synchronizing linear model parameters and rewards are T (Tc+T ′c) = O( −1 ln −1) and TT ′ = O( −1 ln −1), respectively.
Proof. Concatenating all the agents’ actor updates in Algorithm 3, we obtain the joint actor update ωt+1 = ωt + αht. Then, the item 7 of Lemma D.5 implies that
J(ωt+1) ≥ J(ωt) +∇J(ωt)>(ωt+1 − ωt)− LJ 2 ∥∥ωt+1 − ωt∥∥2 = J(ωt) + α∇J(ωt)>ht − LJα 2
2 ∥∥ht∥∥2 (i) ≥ J(ωt) + α∇J(ωt)>F (ωt)−1∇J(ωt) + α∇J(ωt)>[ht − h(ωt)]
− LJα2 ∥∥ht − h(ωt)∥∥2 − LJα2∥∥F (ωt)−1∇J(ωt)∥∥2
(ii) ≥ J(ωt) + ( α C2ψ − α 2C2ψ − LJα 2 λ2F ) ‖∇J(ωt)‖2 − (αC2ψ 2 + LJα 2 )∥∥ht − h(ωt)∥∥2
(iii)
≥ J(ωt) + α
4C2ψ ‖∇J(ωt)‖2 − αC2ψ ∥∥ht − h(ωt)∥∥2 where (i) uses the notation that h(ωt) 4 = F (ωt)
−1∇J(ωt) and the inequality that ‖x‖2 ≤ 2‖x − y‖2 + 2‖y‖2 for any x, y ∈ Rd, (ii) uses the item 3 of Lemma D.7 and the inequality that x>y ≥ − 1
2C2ψ ‖x‖2 − C
2 ψ
2 ‖y‖ 2 for any x, y ∈ Rd, and (iii) uses the condition that α ≤ min
( λ2F
4LJC2ψ , C2ψ 2LJ
) .
Taking expectation on both sides of the above inequality, summing over t = 0, 1, . . . , T − 1 and rearranging, we obtain that
1
T T−1∑ t=0 E‖∇J(ωt)‖2 ≤ 4C2ψ Tα E[J(ωT )− J(ω0)] + 4C4ψ T T−1∑ t=0 E ∥∥ht − h(ωt)∥∥2
(i) ≤ 4C2ψRmax
Tα + 4C4ψ
[ c10 ( 1− ηλF
2
)(K−1)/2 + c11σ 2Tz + c12σ 2T ′
+ c13β 2σ2T ′ c + c14 ( 1− λB 4 β )Tc + c15 Nc + c16ζ critic approx ] , (13)
where (i) uses the item 4 of Lemma D.5 and the item 8 of Lemma D.7.
By Assumption 2, lnπω(s, a) is an Lψ-smooth function of ω. Denote ω∗:= arg minω∈Ω J(ω) and denote Eω∗ as the unconditional expectation over s ∼ νω∗ , a ∼ πω∗(·|s). We obtain that
Eω∗ [ lnπt+1(a|s)− lnπt(a|s) ]
≥ Eω∗ [( ∇ωt lnπt(a|s) )> (ωt+1 − ωt) ] − Lψ
2 E‖ωt+1 − ωt‖2
= αEω∗ [ ψt(a|s)>ht ] − Lψα 2 2 E [ ‖ht‖2 ] (i)
≥ αEω∗ [ ψt(a|s)> ( ht − h(ωt) )] + αEω∗ [ ψt(a|s)>h(ωt)−Aωt(s, a) ] + αEω∗ [ Aωt(s, a) ] − Lψα2E
[∥∥ht − h(ωt)∥∥2]− Lψα2E[∥∥F (ωt)−1∇J(ωt)∥∥2] (ii)
≥ −αCψ √ E [∥∥ht − h(ωt)∥∥2]− αC∗√ζactorapprox
+ αE [ J(ω∗)− J(ωt) ] − Lψα2E [∥∥ht − h(ωt)∥∥2]− Lψα2λ−2F E[∥∥∇J(ωt)∥∥2], where (i) uses the inequality that ‖x‖2 ≤ 2‖x − y‖2 + 2‖y‖2 for any x, y ∈ Rd and the notation that h(ωt) 4 = F (ωt)
−1∇J(ωt), (ii) uses Cauchy-Schwarz inequality, the items 3 & 6 of Lemma D.7, the inequality that E‖X‖ ≤ √ E [ ‖X‖2 ] for any random vector X and the equality that
Eω∗ [ Aωt(s, a) ] = E [ J(ω∗)− J(ωt) ] (See its proof in Lemma 3.2 of (1).). Averaging the inequality above over t = 0, 1, . . . , T − 1 and rearranging it yields that
J(ω∗)− E [ J(ωT̃ ) ] = 1
T T−1∑ t=0 E [ J(ωt) ] ≤ 1 Tα Eω∗ [ lnπT (a|s)− lnπ0(a|s) ] + C∗ √ ζactorapprox + Cψ T T−1∑ t=0 √ E [∥∥ht − h(ωt)∥∥2]
+ Lψα
T T−1∑ t=0 E [∥∥ht − h(ωt)∥∥2]+ Lψα Tλ2F T−1∑ t=0 E [∥∥∇J(ωt)∥∥2]
(i) ≤ 1 Tα
Es∼νω∗ [ KL ( πω∗(·|s)||π0(·|s) ) − KL ( πω∗(·|s)||πT (·|s) )] + C∗ √ ζactorapprox
+ Cψ [ c10 ( 1− ηλF
2
)(K−1)/2 + c11σ 2Tz + c12σ 2T ′ + c13β 2σ2T ′ c
+ c14
( 1− λB 4 β )Tc + c15 Nc + c16ζ critic approx ]1/2 + Lψα [ c10 ( 1− ηλF
2
)(K−1)/2 + c11σ 2Tz + c12σ 2T ′ + c13β 2σ2T ′ c
+ c14
( 1− λB 4 β )Tc + c15 Nc + c16ζ critic approx ] + Lψα
λ2F
{4C2ψRmax Tα + 4C4ψ [ c10 ( 1− ηλF 2 )(K−1)/2 + c11σ 2Tz + c12σ 2T ′ + c13β 2σ2T ′ c
+ c14
( 1− λB 4 β )Tc + c15 Nc + c16ζ critic approx ]} (ii)
≤ 1 Tα
Es∼νω∗ [ KL ( πω∗(·|s)||π0(·|s) )] + C∗ √ ζactorapprox
+ Cψ [√ c10 ( 1− ηλF
2
)(K−1)/4 + √ c11σ Tz + √ c12σ T ′ + √ c13βσ T ′c
+ √ c14 ( 1− λB 4 β )Tc/2 + √ c15 Nc + √ c16ζcriticapprox ] + Lψ ( 1 +
4C4ψ λ2F
)[ c10 ( 1− ηλF
2
)(K−1)/4 + c11σ Tz + c12σ T ′ + c13βσ T ′c
+ c14
( 1− λB 4 β )Tc/2 + c15√ Nc + c16ζ critic approx ] + 4LψC 2 ψRmax
Tαλ2F (iii) =
c17 Tα + c18
( 1− ηλF
2
)(K−1)/4 + c19σ Tz + c20σ T ′ + c21βσ T ′c + c22 ( 1− λB 4 β )Tc/2
+ c23√ Nc + Cψ
√ c16ζcriticapprox + c24ζ critic approx + C ∗ √ ζactorapprox, (14)
where (i) uses the definition of KL divergence that KL ( πω∗(·|s)||πω(·|s) ) =
Ea∼πω∗ (·|s) [ lnπω∗(a|s)− lnπω(a|s) ∣∣s] and eqs. (13) & (54), (ii) uses the condition that α ≤ 1 and
the inequality that √∑n i=1 xi ≤ ∑n i=1 √ xi for any n ∈ N+ and x1, . . . , xn ≥ 0, (iii) uses the nota-
tions that c17:=Es∼νω∗ [ KL ( πω∗(·|s)||π0(·|s) )] + 4LψC 2 ψRmax
λ2F , c18 := Cψ
√ c10 +c10Lψ ( 1+
4C4ψ λ2F
) ,
c19 := Cψ √ c11 + c11Lψ ( 1 +
4C4ψ λ2F
) , c20 := Cψ √ c12 + c12Lψ ( 1 +
4C4ψ λ2F
) , c21 := Cψ √ c13 +
c13Lψ
( 1 +
4C4ψ λ2F
) , c22 := Cψ √ c14 + c14Lψ ( 1 +
4C4ψ λ2F
) , c23 := Cψ √ c15 + c15Lψ ( 1 +
4C4ψ λ2F
) ,
c24 := c16Lψ
( 1 +
4C4ψ λ2F
) . This proves the error bound of Theorem 2.
Finally, for any ≥ 2Cψ √ c16ζcriticapprox + 2c24ζ critic approx + 2C ∗√ζactorapprox, it can be verified that the following hyperparameter choices make the error bound in (14) smaller than and satisfy all the conditions of this Theorem and those in Lemma D.4 that β ≤ min ( λB
8C2B , 4λB , 1−σ 2CB ) , Nc ≥(
2 λB
+ 2β ) 192C2B [1+(κ−1)ρ]
(1−ρ)λB .
α = min ( 1, λ2F
4LJC2ψ , C2ψ 2LJ
) = O(1)
β = min ( 1,
λB 8C2B , 4 λB , 1− σ 2CB
) = O(1)
η = 1
2C2ψ = O(1)
T = ⌈14c17 α ⌉ = O( −1)
K = ⌈ max [ ln 3
ln[(1− ηλF /2)−1] ,
4 ln(14c18 −1) ln [ (1− ηλF /2)−1 ] + 1]⌉ = O[ ln( −1)] Tz = ⌈ max [ ln(3DJC2ψ) ln(σ−1) , ln(14c19 −1) ln(σ−1) ] = ⌉ O [ ln( −1) ]
T ′ = ⌈ max [ lnM
2 ln(σ−1) ,
ln(14c20 −1)
ln(σ−1)
]⌉ = O [ ln( −1) ] T ′c = ⌈ ln(14c21 −1) ln(σ−1) ⌉ = O [ ln( −1)
] Tc = ⌈ 2 ln(14c22 −1) ln[(1− λBβ/4)−1] ⌉ = O [ ln( −1)
] N =
⌈ 2304C4ψ(κ+ 1− ρ) ηλ5F (1− ρ)(1− ηλF /2)(K−1)/2 ⌉ = O( −2)
Nc = ⌈ max [( 2 λB + 2β )192C2B [1 + (κ− 1)ρ] (1− ρ)λB , 196c223 −2 ]⌉ = O( −2) (15)

heading: D SUPPORTING LEMMAS
text: First, we extend the Lemma F.3 of (12) to the Lemma D.1 below. The item 1 of Lemma D.1 generalizes the case n = 1 to any n ∈ N+, the items 2 & 3 remain unchanged, and the item 4 is added for convenience of our convergence analysis. Lemma D.1. The doubly stochastic matrix W and the difference matrix ∆ = I − 1M 11
> have the following properties:
1. ∆Wn = Wn∆ = Wn − 1M 11 > for any n ∈ N+.

heading: 2. The spectral norm of W satisfies ‖W‖ = 1.
text: 3. For any x ∈ RM and n ∈ N+, ‖Wn∆x‖ ≤ σnW ‖∆x‖ (σW is the second largest singular value of W ). Hence, for any H ∈ RM×M , ‖Wn∆H‖F ≤ σnW ‖∆H‖F .
4. ∥∥Wn − 1M 11>∥∥ ≤ σnW , ∥∥Wn − 1M 11>∥∥F ≤ σnW√M for any n ∈ N+.
Proof. The proof of items 2 & 3 can be found in (12). We prove the item 1 and item 4.
We prove item 1 by induction. The case n = 1 of the item 1 can be proved by the following two equalities, as shown in (12).
∆W = ( I − 1
M 11>
) W = W − 1
M 11>W = W − 1 M 11>
W∆ = W ( I − 1
M 11>
) = W − 1
M W11> = W − 1 M 11>
Suppose the case of n = k holds for a certain k ∈ N+, then the following two equalities proves the case of n = k + 1 and thus proves the item 1.
∆W k+1 = (∆W k)W = ( W k − 1
M 11>
) W = W k+1 − 1
M 11>
W k+1∆ = W (W k∆) = W ( W k − 1
M 11>
) = W k+1 − 1
M 11>
The item 4 can be proved by the following two inequalities.∥∥∥Wn − 1 M 11> ∥∥∥ (i)= ∥∥Wn∆∥∥ = sup x:‖x‖≤1 ‖Wn∆x‖ (ii) ≤ sup x:‖x‖≤1 σnW ‖∆‖‖x‖ (iv) = σnW , (16)
∥∥∥Wn − 1 M 11> ∥∥∥ F (i) = ∥∥Wn∆∥∥ F (iii) ≤ σnW ‖∆‖F
(iv) = σnW √ M (
1− 1 M
)2 +M(M − 1) ( − 1 M )2 ≤ σnW √ M, (17)
where (i) uses the item 1, (ii) and (iii) use the item 3 (H = I in (iii)), and (iv) uses the fact that ∆ has M diagnoal entries 1 − 1M and M(M − 1) off-diagnoal entries − 1 M , which implies that ‖∆‖ = 1.
Next, we extend the Lemma F.2. of (12) to the Lemma D.2 below.
Lemma D.2. Suppose the Markovian samples {si, ai}i≥0 are generated following the policy πω and transition kernel P ′ (can be P or Pξ), and s′i+1 ∼ P(·|si, ai). Then, for any deterministic mapping X : S × A× S × S → Rp×q (p, q ∈ N+ are arbitrary.) such that ‖X(s, a, s′, s̃)‖F ≤ Cx and for any s, s′, s̃ ∈ S, a ∈ A, we have
E [∥∥∥ 1 n n+n′−1∑ i=n′ X(si, ai, si+1, s ′ i+1)−X ∥∥∥2 F ∣∣∣sn′] ≤9C2x(κ+ 1− ρ) n(1− ρ) ,∀n, n′ ∈ N+ (18)
where X = E [ X(si, ai, si+1, s ′ i+1) ∣∣si] with si ∼ µω (or νω) when P ′ = P (or Pξ). Proof. Denote Y (s, a, s′) := Es̃∼P′(·|s,a) [ X(s, a, s′, s̃)
∣∣s, a, s′] which satisfies ‖Y (s, a, s′)‖ ≤ Cx and Esi∼νω [ Y (si, ai, si+1) ] = X . Hence, Lemma F.2 of (12) can be applied to Y (s, a, s′) and obtain the following inequality
E [∥∥∥ 1 n n+n′−1∑ i=n′ Y (si, ai, si+1)−X ∥∥∥2 F ∣∣∣sn′] ≤8C2x(κ+ 1− ρ) n(1− ρ) . (19)
Therefore, we obtain that
E [∥∥∥ 1 n n+n′−1∑ i=n′ X(si, ai, si+1, s ′ i+1)−X ∥∥∥2 F ∣∣∣{si, ai, si+1}n+n′−1i=n′ ]
= ∥∥∥E[ 1
n n+n′∑ i=n′ X(si, ai, si+1, s ′ i+1)−X ∣∣∣{si, ai, si+1}n+n′−1i=n′ ]∥∥∥2 F
+ Var [ 1 n n+n′−1∑ i=n′ X(si, ai, si+1, s ′ i+1) ∣∣∣{si, ai, si+1}n+n′−1i=n′ ] (i) = ∥∥∥ 1 n n+n′−1∑ i=n′ Y (si, ai, si+1)−X ∥∥∥2 F
+ 1
n2 n+n′−1∑ i=n′ Var [ X(si, ai, si+1, s ′ i+1) ∣∣{si, ai, si+1}n+n′−1i=n′ ] (ii)
≤ ∥∥∥ 1 n n+n′−1∑ i=n′ Y (si, ai, si+1)−X ∥∥∥2 F + C2x n
(20)
where (i) uses the conditional independency among {s′i+1} (t+1)N−1 i=tN on {si, ai, si+1} n+n′−1 i=n′ and (ii) uses the fact that ‖X(si, ai, si+1, s′i+1)‖F ≤ Cx. Finally, eq. (18) can be proved via the following inequality.
E [∥∥∥ 1 n n+n′∑ i=n′ X(si, ai, si+1, s ′ i+1)−X ∥∥∥2 F ∣∣∣sn′]
(i) ≤ E [∥∥∥ 1 n n+n′−1∑ i=n′ Y (si, ai, si+1)−X ∥∥∥2 F ∣∣∣sn′]+ C2x n
(ii) ≤ 8C 2 x(κ+ 1− ρ) n(1− ρ) + C2x n ≤ 9C 2 x(κ+ 1− ρ) n(1− ρ) ,
where (i) takes the conditional expectation of eq. (20) on s′n and (ii) uses eq. (19).
Next, we prove the following Lemmas D.3 & D.4 on the decentralized TD in Algorithm 2. We first define the following useful notations.
λφ := λmin ( Es∼µω [φ(s)φ(s)>] ) > 0, see Assumption 4.
B(s, s′) := φ(s) [ γφ(s′)− φ(s) ]> .
Bt := 1 Nc ∑(t+1)Nc−1 i=tNc B(si, si+1).
Bω := Es∼µω,a∼πω(·|s),s′∼P(·|s,a) [ B(s, s′) ] .
b(m)(s, a, s′) := R(m)(s, a, s′)φ(s). b(s, a, s′) := 1M ∑M m=1 b (m)(s, a, s′).
b (m) t := 1 Nc ∑(t+1)Nc−1 i=tNc b(m)(si, ai, si+1).
bt := 1 M ∑M m=1 b (m) t .
bω := Es∼µω,a∼πω(·|s),s′∼P(·|s,a) [ b(s, a, s′) ] .
θ∗ω := B −1 ω bω , which is the optimal critic parameter under policy πω .
Lemma D.3. The following bounds hold for Algorithm 2.
1. ‖B(s, s′)‖F , ‖Bt‖F , ‖Bω‖F ≤ CB := 1 + γ, ‖b(m)(s, a, s′)‖, ‖b(s, a, s′)‖, ‖b(m)t ‖, ‖bt‖, ‖bω‖ ≤ Cb := Rmax.
2. θ>Bωθ ≤ −λB2 ‖θ‖ 2 uniformly for all ω, where λB := 2(1− γ)λφ > 0.

heading: 3. ‖θ∗ω‖ ≤ Rθ := 2CbλB uniformly for all ω.
text: Proof. We first prove the item 1. Notice that for any vectors x, y ∈ Rd,
‖xy>‖F = √√√√ d∑ i=1 d∑ j=1 (xiyj)2 = √√√√ d∑ i=1 x2i √√√√ d∑ j=1 y2j = ‖x‖‖y‖.
Hence, we obtain that ‖B(s, s′)‖F = ∥∥φ(s)(γφ(s′)− φ(s))>∥∥ F = ‖φ(s)‖‖γφ(s′)− φ(s)‖ ≤ 1 + γ := CB , (21)
‖b(s, a, s′)‖ = R(s, a, s′)‖φ(s)‖ ≤ Rmax := Cb. (22)
The other terms listed in the item 1 can be proved by applying the Jensen’s inequality to the convex function ‖ · ‖. Next, we prove the item 2, where we use the underlying distribution that s ∼ µω, a ∼ πω(·|s), s′ ∼ P(·|s, a). We obtain that
θ>Bωθ = Eω ( θ>φ(s) [ γφ(s′)− φ(s) ]> θ )
= γEω [( θ>φ(s) )( θ>φ(s′) )] − Eω [( θ>φ(s) )2]
≤ γ 2
( Eω [( θ>φ(s) )2] + Eω [( θ>φ(s′) )2])− Eω[(θ>φ(s))2] (i) = (γ − 1)Eω [( θ>φ(s)
)2] = −(1− γ)θ>Eω[φ(s)φ(s)>]θ (ii)
≤ −λB 2 ‖θ‖2, (23)
where (i) uses the fact that s, s′ ∼ µω which is the stationary state distribution with the transition kernel P and the policy πω , and (ii) uses Assumption 4 and we denote λB := 2(1− γ)λφ > 0. Finally, the item 3 can be proved via the following inequality.
‖θ∗ω‖2 (i) ≤ − 2 λB (θ∗ω) >Bωθ ∗ ω ≤ 2 λB ‖θ∗ω‖‖Bωθ∗ω‖ = 2 λB ‖θ∗ω‖‖bω‖ ≤ 2Cb λB ‖θ∗ω‖, (24)
where (i) uses the item 2. Lemma D.4. Under Assumptions 1–5 and choosing β ≤ min ( λB
8C2B , 4λB , 1−σW 2CB
) , Nc ≥ ( 2 λB +
2β ) 192C2B [1+(κ−1)ρ]
(1−ρ)λB , Algorithm 2 has the following convergence rate.
M∑ m=1 E [∥∥θ(m)Tc+T ′c − θ∗ωt∥∥2∣∣ωt] ≤ σ2T ′cW β2c2 + 2M[c3(1− λB8 β)Tc + c1Nc ] . (25)
Moreover, to achieve ∑M m=1 E [∥∥θ(m)Tc+T ′c − θ∗ωt∥∥2∣∣ωt] ≤ , we can choose Tc, T ′c = O[ ln( −1)] and Nc = O( −1). Consequently, the sample complexity is TcNc = O [ −1 ln( −1) ] and the
communication complexity is Tc + T ′c = O [ ln( −1) ] .
Proof. In Algorithm 2, by averaging the TD update rule (26) over the agents m ∈M, we obtain that the averaged critic parameter θt,t′ := 1M ∑M m=1 θ (m) t,t′ follows the following update rule
θt,t′+1 = 1
M M∑ m=1 [ M∑ m′=1 Wm,m′θ (m′) t,t′ + β ( Bt′θ (m) t,t′ + b (m) t′ )] = 1
M M∑ m′=1 θ (m′) t,t′ + β 1 M M∑ m=1 ( Bt′θ (m) t,t′ + b (m) t′ ) = θt,t′ + β ( Bt′θt,t′ + bt′ ) (26)
which can be viewed as a centralized TD update using the Markovian samples {si, ai}i from the transition kernel P and the joint policy πt. Therefore, Theorem 4 in (60) can be directly applied to analyze this centralized TD update and obtain the following convergence rate of θt,t′ , since all the conditions of that theorem are met 4.
E [∥∥θt,Tc − θ∗ωt∥∥2∣∣ωt] ≤(1− λB4 β )Tc E [∥∥θt,0 − θ∗ωt∥∥2∣∣ωt]
+ ( 2 λB + 2β )192(C2BR2θ + C2b )[1 + (κ− 1)ρ]
(1− ρ)λBNc (i) ≤ 2 (
1− λB 4 β )Tc (∥∥θ−1∥∥2 +R2θ)+ c1Nc (ii)
≤ c3 (
1− λB 4 β )Tc + c1 Nc . (27)
where (i) uses the condition that β ≤ 4/λB , the item 3 of Lemma D.3 and the constant that c1 := 1920(C2BR 2 θ+C 2 b )[1+(κ−1)ρ]
(1−ρ)λ2B , (ii) uses the constant that c3 := 2 (∥∥θ−1∥∥2 +R2θ). 4We corrected the typo 1− λB
8 β, which should be 1− λB 4 β.
Next, we consider the consensus error ‖∆Θt,t′‖2F = ∑M m=1 ∥∥θ(m)t,t′ − θt,t′∥∥2 where we define Θt,t′ := [θ (1) t,t′ , . . . , θ (M) t,t′ ]
>. Note that the critic-step (26) can be rewritten into the following matrix form
Θt,t′+1 = WΘt,t′ + β ( Θt,t′B > t′ + [b (1) t′ ; . . . ; b (M) t′ ] >); t′ = 0, 1, . . . , Tc − 1, (28) which further implies that for any t′ = 0, 1, . . . , Tc − 1,∥∥∆Θt,t′+1∥∥F (i)≤ ∥∥W∆Θt,t′∥∥F + β∥∥∆Θt,t′B>t′ ∥∥F + β∥∥∆[b(1)t′ ; . . . ; b(M)t′ ]>∥∥F
(ii) ≤ (σW + βCB) ∥∥∆Θt,t′∥∥F + β √√√√M M∑ m=1 ‖b(m)t′ ‖2
(iii)
≤ 1 + σW 2 ∥∥∆Θt,t′∥∥F + βMCb, where (i) uses the item 1 of Lemma D.1, (ii) uses the item 3 of Lemma D.1 and the item 1 of Lemma D.3, (iii) uses the condition that β ≤ 1−σW2CB and the item 1 of Lemma D.3. Telescoping the inequality above yields that∥∥∆Θt,Tc∥∥F ≤ (1 + σW2 )Tc∥∥∆Θt,0∥∥F + 2βMCb1− σW (i)= 2βMCb1− σW , (29) where (i) uses the equality that ∆Θ0 = O due to the initial condition that Θt,0 = [θ−1; . . . ; θ−1]>.
On the other hand, the final T ′c local average steps in Algorithm 2 can be rewritten into the following matrix form
Θt,t′+1 = WΘt,t′ ; t = Tc, Tc + 1, . . . , Tc + T ′ c − 1.
Hence, the average critic parameter θt,t′ does not change in these local average steps, i.e.,
θt,Tc+T ′c = 1 M Θ>t,Tc+T ′c1 = 1 M Θ>t,Tc(W T ′c)>1 = 1 M Θ>t,Tc1 = θt,Tc . (30)
Therefore, we obtain that M∑ m=1 ∥∥θ(m)t,Tc+T ′c − θt,Tc∥∥2 = M∑ m=1 ∥∥θ(m)t,Tc+T ′c − θt,Tc+T ′c∥∥2 = ‖∆Θt,Tc+T ′c‖2F = ‖∆WT ′cΘt,Tc‖2F (i) = ‖WT ′ c∆Θt,Tc‖2F (ii) ≤ σ2T ′ c W ‖∆Θt,Tc‖ 2 F
(iii)
≤ σ2T ′ c
W (2βMCb 1− σW )2 (iv) = σ 2T ′c W β 2c2/2 (31)
where (i) and (ii) use the items 1 and 3 of Lemma D.1 respectively, (iii) uses eq. (29), (iv) denotes that c2 := 2 ( 2MCb 1−σW )2 . Combining eqs. (27) & (31) yields that
M∑ m=1 E [∥∥θ(m)t,Tc+T ′c − θ∗ωt∥∥2∣∣ωt] ≤ 2 M∑ m=1 E [∥∥θ(m)t,Tc+T ′c − θt,Tc∥∥2∣∣ωt]+ 2ME[∥∥θt,Tc − θ∗ωt∥∥2∣∣ωt]
≤ σ2T ′ c
W β 2c2 + 2M [ c3 ( 1− λB 4 β )Tc + c1 Nc ] .
In the inequality above, replacing θ(m)t,Tc+T ′c from Algorithm 2 by its corresponding variable θ (m) t from Algorithm 1 proves eq. (25). Finally, it can be easily verified that the following hyperparameter choices make the error bound in (25) smaller than and also satisfy the conditions of Lemma D.4.
β = min ( λB
8C2B ,
4
λB , 1− σW 2CB
) = O(1)
Nc = max [( 2 λB + 2β )192C2B [1 + (κ− 1)ρ] (1− ρ)λB , 6Mc1 −1 ] = O( −1)
Tc = ⌈ ln(6Mc3 −1)
ln [( 1− λBβ/4 )−1]⌉ = O[ ln( −1)]
T ′c = 2 ⌈ ln(3β2c2 −1)
ln(σ−1W )
⌉ = O [ ln( −1) ]
Lemma D.5. For any ω, ω̃ ∈ Ω, s ∈ S and a(m) ∈ Am (Am denotes the action space for the agent m), the following properties hold.
1. ‖ψ(m)ω (a(m)|s)‖ ≤ Cψ , where ψ(m)ω (a(m)|s) := ∇ω(m) lnπ (m) ω (a(m)|s).
2. ‖ψ(m)ω̃ (a (m)|s)− ψ(m)ω (a(m)|s)‖ ≤ Lψ‖ω̃(m) − ω(m)‖.
3. dTV [ π (m) ω̃(m) (·|s), π(m) ω(m) (·|s) ] ≤ Lπ‖ω̃(m) − ω(m)‖.
4. 0 ≤ Vω(s), Qω(s, a) ≤ (1− γ)Rmax, 0 ≤ J(ω) ≤ Rmax. 5. dTV [ νω(·|s), νω̃(·|s) ] ≤ Lν‖ω′ − ω‖ where Lν := Lπ[1 + logρ(κ−1) + (1− ρ)−1].
6. dTV [ Qω̃(s, a), Qω(s, a) ] ≤ LQ‖ω̃ − ω‖ where LQ := 2RmaxLν1−γ .

heading: 7. J(ω) is LJ -smooth where LJ := Rmax(4Lν + Lψ)/(1− γ).
text: 8. ‖∇J(ω)‖ ≤ DJ := CψRmax1−γ .

heading: 9. F (ω) is LF -Lipschitz where LF := 2Cψ(LπCψ + LνCψ + Lψ).
text: 10. h(ω) is Lh-Lipschitz where Lh := 2λ−1F (DJλ −1 F LF + LJ).
Proof. For any ω(m), ω̃(m) ∈ Ωm, s ∈ S and a(m) ∈ Am, arbitrarily select ω(m ′) = ω̃(m ′) ∈ Ωm′ , a(m
′) ∈ Am′ for everym′ ∈ {1, ...,M}/{m}. Denote ω = [ω(1); . . . ;ω(M)], ω̃ = [ω̃(1); . . . ; ω̃(M)], a = [a(1), . . . , a(M)]. Notice that the joint score vector has the following decomposition
ψω(a|s) = [ψ(1)ω (a(1)|s); . . . ;ψ(M)ω (a(M)|s)]. (32)
Hence, the items 1 & 2 can be proved via the following two inequalities, respectively.
‖ψ(m)ω (a(m)|s)‖ ≤ √√√√ M∑ m′=1 ‖ψ(m ′) ω (a(m ′)|s)‖2 (i)= ‖ψω(a|s)‖ (ii) ≤ Cψ.
‖ψ(m)ω̃ (a (m)|s)− ψ(m)ω (a(m)|s)‖ = ‖ψω̃(a|s)− ψω(a|s)‖
(i) ≤ Lψ‖ω̃ − ω‖ = Lψ‖ω̃(m) − ω(m)‖
where (i) uses Assumption 2.
Next, we prove the item 3. Notice that dTV [ πω̃(·|s), πω(·|s) ] (i) = sup
A⊂A |πω̃(A|s)− πω(A|s)|
(ii)
≥ sup A1⊂A1,...,AM⊂AM ∣∣∣ M∏ m′=1 πω̃(m′)(Am′ |s)− M∏ m′=1 πω(m′)(Am′ |s) ∣∣∣
(iii) = sup
A1⊂A1,...,AM⊂AM ∣∣∣ M∏ m′=1,m′ 6=m πω(m′)(Am′ |s) ∣∣∣∣∣∣πω̃(m)(Am|s)− πω(m)(Am|s)∣∣∣
(iv) = sup
Am⊂Am ∣∣∣πω̃(m)(Am|s)− πω(m)(Am|s)∣∣∣ = dTV[π(m)ω̃(m)(·|s), π(m)ω(m)(·|s)], where (i) denotes that πω(A|s) = ∫ A πω(a|s)da, (ii) uses the relation that ×m∈MAm ⊂ A, (iii) uses our construction that ω(m ′) = ω̃(m
′) ∈ Ωm′ ,∀m′ ∈ {1, ...,M}/{m}, and (iv) uses Am′ = Am′ to achieve the supremum. Therefore, the item 2 can be proved via the following inequality.
dTV [ π (m) ω̃(m) (·|s), π(m) ω(m) (·|s) ] = dTV [ πω̃(·|s), πω(·|s) ] ≤ Lπ ‖ω̃ − ω‖ = Lπ‖ω̃(m) − ω(m)‖,
where (i) uses Assumption 2.
The item 4 can be proved by the following three inequalities that use Assumption 3.
0 ≤ Vω(s) = Eω [ ∞∑ t=0 γtRt ∣∣∣s0 = s] ≤ ∞∑ t=0 γtRmax = Rmax 1− γ ,
0 ≤ Qω(s, a) = Es′∼P(·|s,a)[R(s, a, s′) + γVω(s′)] ≤ Rmax + γ Rmax 1− γ = Rmax 1− γ ,
0 ≤ J(ω) = (1− γ)Eω [ ∞∑ t=0 γtRt ] ≤ (1− γ) ∞∑ t=0 γtRmax = Rmax.
The proof of the items 5 – 7 can be found in the proof of Lemma 3, Lemma 4 and Proposition 1 of (60), respectively.
Next, the item 8 is proved by the following inequality.∥∥∇J(ω)∥∥ = ∥∥Es∼νω,a∼πω(·|s)[Qω(s, a)ψω(a|s)]∥∥ (i)
≤ Es∼νω,a∼πω(·|s) [ |Qω(s, a)| ∥∥ψω(a|s)∥∥] (ii)≤ CψRmax 1− γ ,
where (i) applies Jensen’s inequality, (ii) uses Assumption 2 and the item 4.
Next, the item 9 is proved by the following inequality.∥∥F (ω̃)− F (ω)∥∥ = ∥∥Es∼νπω̃ ,a∼πω̃(·|s)[ψω̃(a|s)ψω̃(a|s)>]− Es∼νπω ,a∼πω(·|s)[ψω(a|s)ψω(a|s)>]∥∥
(i) ≤ ∥∥Es∼νπω̃ ,a∼πω̃(·|s)[ψω̃(a|s)ψω̃(a|s)>]− Es∼νπω ,a∼πω(·|s)[ψω̃(a|s)ψω̃(a|s)>]∥∥ + Es∼νπω ,a∼πω(·|s)
[∥∥[ψω̃(a|s)− ψω(a|s)]ψω̃(a|s)>∥∥] + Es∼νπω ,a∼πω(·|s)
[∥∥ψω(a|s)[ψω̃(a|s)− ψω(a|s)]>∥∥] (ii)
≤ ∥∥∥∫ S×A [νω̃(s)πω̃(a|s)− νω(s)πω(a|s)] [ ψω̃(a|s)ψω̃(a|s)> ] dsda ∥∥∥+ 2CψLψ‖ω̃ − ω‖ ≤ C2ψ ∫ S×A |νω̃(s)πω̃(a|s)− νω(s)πω(a|s)|dsda+ 2CψLψ‖ω̃ − ω‖
≤ C2ψ ∫ S×A νω̃(s)|πω̃(a|s)− πω(a|s)|dsda
+ C2ψ ∫ S×A πω(a|s)|νω̃(s)− νω(s)|dsda+ 2CψLψ ∥∥ω̃ − ω∥∥
(iii) ≤ 2LπC2ψ ∥∥ω̃ − ω∥∥+ 2LνC2ψ∥∥ω̃ − ω∥∥+ 2CψLψ∥∥ω̃ − ω∥∥ := LF∥∥ω̃ − ω∥∥
where (i) applies triangle inequality and then Jensen’s inequality to the norm ‖·‖, (ii) uses Assumption 2, (iii) uses the equality that ∫ S νω(s)ds = ∫ A πω(a|s)da = 1 as well as the inequlities that∫
A |πω̃(a|s)− πω(a|s)|da = 2dTV [ πω̃(·|s), πω(·|s) ] ≤ 2Lπ‖ω̃ − ω‖ (based on Assumption 2) and
that ∫ S |νω̃(s)− νω(s)|ds = 2dTV [ νω(·|s), νω̃(·|s) ] ≤ 2Lν‖ω′ − ω‖ (based on the item 5).
Finally, the item 10 is proved by the following inequality∥∥h(ω̃)− h(ω)∥∥ = ∥∥F (ω̃)−1∇J(ω̃)− F (ω)−1∇J(ω)∥∥
≤ 2 ∥∥[F (ω̃)−1 − F (ω)−1]∇J(ω̃)∥∥+ 2∥∥F (ω)−1[∇J(ω̃)−∇J(ω)]‖
(i) ≤ 2DJ ∥∥F (ω)−1[F (ω)− F (ω̃)]F (ω̃)−1∥∥+ 2LJ∥∥F (ω)−1∥∥∥∥ω̃ − ω∥∥
(ii) ≤ 2DJλ−2F LF ∥∥ω̃ − ω∥∥+ 2LJλ−1F ∥∥ω̃ − ω∥∥ := Lh∥∥ω̃ − ω∥∥,
where (i) uses the items 7 & 8, and (ii) uses the inequality that ‖F (ω)−1‖ = λmax(F (ω)−1) = λmin[F (ω)] −1 ≤ λ−1F for all ω (since F (ω) and F (ω)−1 are positive definite) and the item 9.
Next, we bound the approximation error of the following stochastic (partial) policy gradients.
∇̂ω(m)J(ωt) := 1
N (t+1)N−1∑ i=tN [ R (m) i + γφ(s ′ i+1) >θ (m) t − φ(si)>θ (m) t ] ψ (m) t (a (m) i |si), (33)
∇̂J(ωt) := [ ∇̂ω(1)J(ωt); . . . ; ∇̂ω(M)J(ωt) ] , (34)
∇̂ω(m)J(ωt;Bt,k) := 1
Nk ∑ i∈Bt,k [ R (m) i + γφ(s ′ i+1) >θ (m) t − φ(si)>θ (m) t ] ψ (m) t (a (m) i |si), (35)
∇̂J(ωt;Bt,k) := [ ∇̂ω(1)J(ωt); . . . ; ∇̂ω(M)J(ωt) ] . (36)
Lemma D.6. Let Assumptions 1-5 hold and adopt the hyperparameters of the decentralized TD in Algorithm 2 following Lemma D.4. Choose T ′ ≥ lnM
2 ln(σ−1W ) . Then, the following properties hold.
1. The estimated average reward R (m)
i has the following bias and variance bound. M∑ m=1 E [ R (m) i −Ri ∣∣Ri]2 ≤Mσ2T ′W R2max, (37)
M∑ m=1 Var [ R (m) i ∣∣Ri] ≤4R2maxσ2, (38) where Ri := [R (1) i ; . . . ;R (M) i ] denotes the joint reward.

heading: 2. The stochastic policy gradients have the following error bound.
text: E [∥∥∇̂J(ωt)−∇J(ωt)∥∥2] ≤c4σ2T ′W + c5β2σ2T ′cW + c6(1− λB8 β)Tc
+ c7 N + c8 Nc + 16C2ψζ critic approx (39)
E [∥∥∇̂J(ωt;Bt,k)−∇J(ωt)∥∥2∣∣Ft,k] ≤c4σ2T ′W + 16C2ψ M∑
m=1 ∥∥θ(m)t − θ∗ωt∥∥2 +
c7 Nk + 16C2ψζ critic approx, (40)
where Ft,k := σ [ Ft ∪ σ ( {si, ai, si+1, s′i+1, {e (m) i }m∈M}i∈∪k−1 k′=0Bt,k′ )] .
Proof. We will first prove the item 1.
When Ri := [R (1) i ; . . . ;R (M) i ] is given and fixed, the randomness of R̃ (m) i := R (m) i (1 + e (m) i ) and ∇̂ω(m)J(ωt) defined in eq. (4) only comes from the noises {e (m) i }Mm=1. Since {e (m) i }Mm=1 are independent noises with zero mean and variances σ21 , . . . , σ 2 M , R̃i := [R̃ (1) i ; . . . ; R̃ (M) i ] has the following moments
E [ R̃i|Ri ] = Ri,
cov [ R̃i|Ri ] = diag [ (R (1) i ) 2σ21 , . . . , (R (M) i ) 2σ2M ] := Σi.
Hence, R̂i := [R (1) i , . . . , R (m) i ] > = WT ′ R̃i (the second “=” comes from eq. (3) and the notations that R̃(m)i := R̂ (m) i,0 and that R̂ (m) i := R̂ (m) i,T ′) has the moment that E [ R̂i|Ri ] = WT ′ Ri and
Cov [ R̂i|Ri ] = WT ′ Σi(W T ′)>. Therefore, eq. (37) can be proved as follows
M∑ m=1 E [ R (m) i −Ri ∣∣Ri]2 = ∥∥∥E[R̂i −Ri1∣∣Ri]∥∥∥2 = ∥∥∥WT ′Ri − 1 M 11>Ri ∥∥∥2 ≤ ∥∥∥WT ′ − 1
M 11> ∥∥∥2‖Ri‖2 (i)≤ Mσ2T ′W R2max, where 1 is a M -dim vector of 1’s, (i) uses the inequality that ‖Ri‖2 = ∑M m=1(R (m) i )
2 ≤MR2max (based on Assumption 3) and the item 4 of Lemma D.1. Then, eq. (38) can be proved as follows M∑ m=1 var [ R (m) i
∣∣Ri] = Var[R̂i|Ri] = tr[(WT ′)>ΣiWT ′] = tr [( WT
′ − 1 M
11> )
Σi
( WT
′ − 1 M
11> )>] + tr [ (WT ′ )Σi ( 1 M 11> )]
+ tr [( 1 M 11> ) Σi(W T ′)> ] + tr [( 1 M 11> ) Σi ( 1 M 11> )]
(i) ≤ MR2maxσ2 ∥∥∥WT ′ − 1
M 11> ∥∥∥2 + 2 M tr [ WT ′ Σi11 >]+ 1 M2 tr[1(1>Σi1)1>]
(ii)
≤ MR2maxσ2σ2T ′ W + 2
M 1>ΣiW
T ′1 + 1
M2 (1>Σi1)tr[1>1]
(iii)
≤ R2maxσ2 + 3
M 1>Σi1
= R2maxσ 2 +
3
M M∑ m=1 (R (m) i ) 2σ2m
(iv)
≤ 4R2maxσ2,
where (i) uses the equality that tr(Y >) = tr(Y ) and the inequality (41) below in which X = WT
′ − 1M 11 > and the m-th entry of vm ∈ RM is 1 while its other entries are 0, (ii) uses the item 4 of Lemma D.1 and the equality that tr(xy>) = y>x for any x, y ∈ RM , (iii) uses the condition that T ′ ≥ [lnM ]/[2 ln(σ−1W )] and the item 1 of Lemma D.1, (iv) uses Assumption 3.
tr(XΣiX>) =tr(X>XΣi) = M∑ m=1 v>mX >XΣivm ≤ M∑ m=1 ‖vm‖‖X‖2‖Σivm‖
= M∑ m=1 (R (m) i ) 2σ2m‖X‖2 ≤MR2maxσ2‖X‖2. (41)
Next, we will prove eq. (39) in the item 2, where the error term can be decomposed as follows∥∥∇̂J(ωt)−∇J(ωt)∥∥2 ≤ 4 ∥∥∇̂J(ωt)− gt∥∥2︸ ︷︷ ︸ (I) +4 ∥∥gt − g∗t ∥∥2︸ ︷︷ ︸ (II)
+ 4 ∥∥g∗t − g∗t∥∥2︸ ︷︷ ︸
(III)
+4 ∥∥g∗t −∇J(ωt)∥∥2︸ ︷︷ ︸
(IV )
, (42)
where we use the following notations that
gt := [g (1) t ; . . . ; g (M) t ], (43)
g (m) t :=
1
N (t+1)N−1∑ i=tN [ Ri + γφ(s ′ i+1) >θ (m) t − φ(si)>θ (m) t ] ψ (m) t (a (m) i |si), (44)
g∗t := 1
N (t+1)N−1∑ i=tN [ Ri + γφ(s ′ i+1) >θ∗ωt − φ(si) >θ∗ωt ] ψt(ai|si), (45)
g∗t := Es∼νωt ,a∼πt(·|s),s′∼P(·|s,a) [ R(s, a, s′) + γφ(s′)>θ∗ωt − φ(s) >θ∗ωt ] ψt(a|s) ∣∣ωt]. (46) Conditioned on the following filtration
F ′t :=σ [ Ft ∪ σ ( {si, ai, s′i+1} (t+1)N−1 i=tN+1 )] =σ ( {θ(m)t′ }m∈M,0≤t′≤t ∪ {si, ai, s ′ i+1} (t+1)N−1 i=0 ∪ {s(t+1)N} ∪ {{e (m) i }m∈M} tN−1 i=0 ) ,
the error term (I) can be bounded as follows. E [∥∥∇̂J(ωt)− gt,k∥∥2∣∣∣F ′t]
= E [ M∑ m=1 ∥∥∇̂ω(m)J(ωt)− g(m)t,k ∥∥2∣∣∣F ′t] (i) =
M∑ m=1 E [∥∥∥ 1 N (t+1)N−1∑ i=tN ( R (m) i −Ri ) ψ (m) t (a (m) i |si) ∥∥∥2∣∣∣F ′t] (ii)
≤ M∑ m=1 ∥∥∥E[ 1 N (t+1)N−1∑ i=tN ( R (m) i −Ri ) ψ (m) t (a (m) i |si) ∣∣∣F ′t]∥∥∥2 +
M∑ m=1 Var [ 1 N (t+1)N−1∑ i=tN ( R (m) i −Ri ) ψ (m) t (a (m) i |si) ∣∣∣F ′t] (iii)
≤ M∑ m=1 ∥∥∥E[ 1 N (t+1)N−1∑ i=tN ( R (m) i −Ri )∣∣∣F ′t]ψ(m)t (a(m)i |si)∥∥∥2
+ 1
N2 M∑ m=1 (t+1)N−1∑ i=tN Var [( R (m) i −Ri ) ψ (m) t (a (m) i |si) ∣∣F ′t] (iv)
≤ M∑ m=1 [ 1 N (t+1)N−1∑ i=tN E ( R (m) i −Ri ∣∣F ′t)]2∥∥ψ(m)t (a(m)i |si)∥∥2
+ 1
N2 M∑ m=1 (t+1)N−1∑ i=tN ∥∥ψ(m)t (a(m)i |si)∥∥2var[R(m)i −Ri∣∣F ′t] (v)
≤ C2ψ N M∑ m=1 (t+1)N−1∑ i=tN [ E ( R (m) i −Ri ∣∣F ′t)]2 + C2ψN2 (t+1)N−1∑ i=tN M∑ m=1 var [ R (m) i ∣∣F ′t] (vi)
≤ C2ψ(Mσ2T ′ W R 2 max) + C2ψ N (4R2maxσ 2)
= C2ψR 2 max
( Mσ2T ′ W + 4 N σ2 ) , (47)
where (i) uses the definitions of ∇̂ω(m)J(ωt) and g (m) t defined in eqs. (33) & (44) respectively, (ii) uses the relation that E‖X‖2 = Var(X) + ‖EX‖2 for any random vector X , (iii) uses the facts that ψ
(m) t (a (m) i |si), Ri ∈ F ′t are fixed while {R
(m) i } (t+1)N−1 i=tN are random and independent given F ′t , (iv) uses the equality that Var(xY ) = ∑d j=1 var(xyj) = ∑d j=1 y 2 j var(x) = ‖y‖2var(x) for any random scalar x and fixed vector Y = [y1, . . . , yd] ∈ Rd (Here we denote y = ψ(m)t (a (m) i |si) ∈ F ′t), (v) applies Jensen’s inequality to the convex function (·)2 and uses the item 1 of Lemma D.5 as well as
the fact that Ri ∈ F ′t is fixed, (vi) uses eqs. (37) & (38) and the fact that the conditional distribution of R (m)
i on Ri ∈ F ′t is the same as that on F ′t since the noise e (m) i is independent from any other
variables.
Then we bound the error term (II) of eq. (42) as follows.
∥∥gt − g∗t ∥∥2 = M∑ m=1 ∥∥∥ 1 N (t+1)N−1∑ i=tN ( [γφ(s′i+1)− φ(si)]>(θ (m) t − θ∗ωt) ) ψ (m) t (a (m) i |si) ∥∥∥2 (i)
≤ 1 N (t+1)N−1∑ i=tN M∑ m=1 ∥∥γφ(s′i+1)− φ(si)∥∥2∥∥θ(m)t − θ∗ωt∥∥2∥∥ψ(m)t (a(m)i |si)∥∥2 (ii)
≤ C2ψ(1 + γ) 2
N
(t+1)N−1∑ i=tN M∑ m=1 ∥∥θ(m)t − θ∗ωt∥∥2 = 4C2ψ
M∑ m=1 ∥∥θ(m)t − θ∗ωt∥∥2, (48) where (i) applies Jensen’s inequality to the convex function ‖ · ‖2, (ii) uses Assumption 4 and the item 1 of Lemma D.5.
To bound the error term (III) of eq. (42), denote that X(s, a, s′, s̃) = [ R(s, a, s̃) + γφ(s̃)>θ∗ωt − φ(s) >θ∗ωt ] ψt(a|s), (49)
which satisfies ‖X(s, a, s′, s̃)‖ ≤ [ |R(s, a, s̃)|+ ∥∥γφ(s̃) + φ(s)∥∥∥∥θ∗ωt∥∥]∥∥ψt(a|s)∥∥ ≤ Cψ(Rmax + 2Rθ) (the second≤ uses the item 3 of Lemma D.3) andX = Esi∼νt [ X(si, ai, si+1, s ′ i+1)
∣∣Ft] = g∗t where sN , ωt ∈ Ft := σ ( {θ(m)t′ }m∈M,0≤t′≤t ∪{si, ai, s′i+1, {e (m) i }m∈M} tN−1 i=0 ∪{stN} ) are fixed. Hence, Lemma D.2 yields that
E [∥∥g∗t − g∗t∥∥2∣∣Ft] = E[∥∥∥ 1N (t+1)N−1∑ i=tN X(si, ai, si+1, s ′ i+1)−X ∥∥∥2∣∣∣Ft] ≤ 9C2ψ(Rmax + 2Rθ) 2(κ+ 1− ρ)
N(1− ρ) . (50)
Next, we bound the error term (IV) of eq. (42). Notice that
g∗t −∇J(ωt) = Eωt [( R(s, a, s̃) + [γφ(s̃)− φ(s)]>θ∗ωt − [ R(s, a, s̃) + γVωt(s̃)− Vωt(s) ]) ψt(a|s) ∣∣∣ωt] = Eωt [( γ [ φ(s̃)>θ∗ωt − Vωt(s̃) ] − [ φ(s)>θ∗ωt − Vωt(s) ]) ψt(a|s)
∣∣∣ωt]. (51) Hence,
‖g∗t −∇J(ωt)‖2 = ∥∥∥Eωt[(γ[φ(s̃)>θ∗ωt − Vωt(s̃)]− [φ(s)>θ∗ωt − Vωt(s)])ψt(a|s)∣∣∣ωt]∥∥∥2
(i) ≤ Eωt [∥∥∥(γ[φ(s̃)>θ∗ωt − Vωt(s̃)]− [φ(s)>θ∗ωt − Vωt(s)])ψt(a|s)∥∥∥2∣∣∣ωt]
(ii) ≤ 2C2ψEωt [ γ2 ∥∥∥φ(s̃)>θ∗ωt − Vωt(s̃)∥∥∥2 + ∥∥∥φ(s)>θ∗ωt − Vωt(s)∥∥∥2∣∣∣ωt]
= 2C2ψγ 2 ∫ S×A×S ∥∥∥φ(s̃)>θ∗ωt − Vωt(s̃)∥∥∥2νt(s)πt(a|s)P(s̃|s, a)dsdads̃ + 2C2ψEωt
[∥∥∥φ(s)>θ∗ωt − Vωt(s)∥∥∥2∣∣∣ωt] (iii)
≤ 2C2ψγ ∫ S×A×S ∥∥∥φ(s̃)>θ∗ωt − Vωt(s̃)∥∥∥2νt(s)πt(a|s)Pξ(s̃|s, a)dsdads̃
+ 2C2ψEωt [∥∥∥φ(s)>θ∗ωt − Vωt(s)∥∥∥2∣∣∣ωt]
(iv) = 2C2ψ(γ + 1)Eωt [∥∥∥φ(s)>θ∗ωt − Vωt(s)∥∥∥2∣∣∣ωt] (v)
≤ 4C2ψζcriticapprox, (52) where (i) applies Jensen’s inequality to the convex function ‖ · ‖2, (ii) uses the inequality that ‖x + y‖2 ≤ 2‖x‖2 + 2‖y‖2 for any x, y ∈ Rd, (iii) uses the inequality that P(s′|s, a) ≤ γ−1Pξ(s′|s, a);∀s, s′ ∈ S, a ∈ A, (iv) uses the equality that ∫ S×A νt(s)πt(a|s)Pξ(s̃|s, a)dsda =
νt(s̃), and (v) uses the notation that ζcriticapprox := supω Es∼νω [∣∣Vω(s)− φ(s)>θ∗ω∣∣2]. Substituting eqs. (47),(48),(50)&(52) into eq. (42) yields that
E [∥∥∇̂J(ωt)−∇J(ωt)∥∥2∣∣Ft] ≤ 4C2ψR2max ( Mσ2T ′ W + 4 N σ2 ) + 16C2ψ M∑ m=1
∥∥θ(m)t − θ∗ωt∥∥2 + 36C2ψ(Rmax + 2Rθ) 2(κ+ 1− ρ)
N(1− ρ) + 16C2ψζ critic approx
= c4σ 2T ′ W + c7 N + 16C2ψ M∑ m=1 ∥∥θ(m)t − θ∗ωt∥∥2 + 16C2ψζcriticapprox, (53) where θ(m)t , ωt ∈ Ft are fixed, and we take the conditional expectation of eq. (47) on Ft ⊂ F ′t and denote that c4 := 4MC2ψR 2 max, c7 := 16C 2 ψR 2 maxσ 2 + 36C2ψ(Rmax+2Rθ) 2(κ+1−ρ) 1−ρ . Substituting eq. (25) into the unconditional expectation of eq. (53) yields that
E [∥∥∇̂J(ωt)−∇J(ωt)∥∥2] ≤ c4σ2T ′
W + c7 N + 16C2ψ
( σ 2T ′c W β 2c2 + 2M [ c3 ( 1− λB 8 β )Tc + c1 Nc ]) + 16C2ψζ critic approx
= c4σ 2T ′ W + c5β 2σ 2T ′c W + c6 ( 1− λB 8 β )Tc + c7 N + c8 Nc + 16C2ψζ critic approx,
where we denote that c5 := 16c2C2ψ , c6 := 32Mc3C 2 ψ , c8 := 32Mc1C 2 ψ . This proves eq. (39).
Equation (40) can be proved in the same way as that of proving eq. (53). There are two differences. First, ∇̂J(ωt;Bt,k) uses the minibatch Bt,k of size Nk while ∇̂J(ωt) uses batchsize N . Second, eq. (40) is conditioned on the filtrationFt,k := σ [ Ft∪σ ({ si, ai, si+1, s ′ i+1, {e (m) i }m∈M } i∈∪k−1
k′=0Bt,k′ )] which includes not only the filtration Ft use by eq. (53) but also the minibatches ∪k−1k′=0Bt,k′ used by the previous (k − 1) SGD steps.
Lemma D.7. Implementing Algorithm 3 with η ≤ 1 2C2ψ , T ′ ≥ lnM 2 ln(σ−1W ) , Tz ≥ ln(3DJC
2 ψ)
ln(σ−1W ) ,
K ≥ ln 3ln[(1−ηλF /2)−1] , N ≥ 2304C4ψ(κ+1−ρ) ηλ5F (1−ρ)(1−ηλF /2)(K−1)/2 and Nk ∝ (1 − ηλF /2)−k/2, the involved quantities have the following properties, where Eω denotes the expectation under the underlying distributions that s ∼ νω , a ∼ πω(·|s).
1. λF ≤ λmax[F (ω)] = ‖F (ω)‖ ≤ C2ψ,∀ω.
2. 12 ≤ 1− ηC 2 ψ ≤ ∥∥I − ηF (ω)∥∥ ≤ 1− ηλF , so η ≤ 12λF . 3. C−2ψ ≤ ‖F (ω)−1‖ ≤ λ −1 F . For any ω, x ∈ Rdω , x>F (ω)−1x ≥ C −2 ψ ‖x‖2.
4. ∥∥h(ω)∥∥ ≤ 1λF ∥∥∇J(ω)∥∥ ≤ DJλF .
5. h(ω) = arg min h
Eω [( ψω(a|s)>h−Aω(s, a) )2] , so
Eω [( ψω(a|s)>h(ω)−Aω(s, a) )2] ≤ ζactorapprox where s ∼ νω , a ∼ πω(·|s).
6. Eω∗ [ ψω(a|s)>h(ω)−Aω(s, a) ] ≥ −C∗ √ ζactorapprox,∀ω.
7. Nk = N(1−ηλF /2)(K−1−k)/2(1−
√ 1−ηλF /2)
1−(1−ηλF /2)K/2 ≥ 576C
4 ψ(κ+1−ρ)
λ4F (1−ρ) .
8. ht approximates the natural gradient h(ωt) with the following error bound. E [∥∥ht − h(ωt)∥∥2] ≤ c10(1− ηλF
2
)(K−1)/2 + c11σ 2Tz W + c12σ 2T ′ W + c13β 2σ 2T ′c W
+ c14
( 1− λB 8 β )Tc + c15 Nc + c16ζ critic approx. (54)
Proof. The item 1 is proved by the following inequality.
λF (i) ≤λmin[F (ω)] ≤ λmax[F (ω)] (ii) = ‖F (ω)‖
= ∥∥Eω[ψ(a|s)ψ(a|s)>]∥∥ ≤ Eω[∥∥ψ(a|s)∥∥∥∥ψ(a|s)>∥∥] (iii)≤ C2ψ,
where (i) uses Assumption 6, (ii) uses the fact that F (ω) is positive definite implied by Assumption 6, (iii) applies Jensen’s inequality to the convex function ‖ · ‖ and (iv) uses Assumption 2. Next we will prove the item 2. On one hand,
λmin [ I − ηF (ω) ] = 1− ηλmax [ F (ω) ] (i) ≥ 1− ηC2ψ ≥ 1
2 , (55)
where (i) uses the item 1, (ii) uses the condition that η ≤ 1 2C2ψ . On the other hand,
λmin [ I − ηF (ω) ] ≤ λmax [ I − ηF (ω) ] (i) = ‖I − ηF (ω)‖ = I − ηλmin [ F (ω) ] ≤ 1− ηλF , (56)
where (i) uses the fact that I − ηF (ω) is positive definite based on eq. (55). Hence, eqs. (55) & (56) prove the item 2.
The item 3 can be proved by the fact that F (ω)−1 is positive definite with minimum eigenvalue λmax[F (ω)] −1 ≥ C−2ψ and maximum eigenvalue λmin[F (ω)]−1 ≤ λ −1 F implied by the item 1.
The item 4 can be proved by the following inequality.
‖h(ω)‖ = ∥∥F (ω)−1∇J(ω)∥∥ ≤ ∥∥F (ω−1)∥∥∥∥∇J(ω)∥∥ (i)≤ λ−1F ∥∥∇J(ω)∥∥ (ii)≤ λ−1F DJ ,
where (i) uses the item 3 and (ii) uses the item 8 of Lemma D.5.
Next we will prove item 5.
Consider the following function of x ∈ Rdω .
fω(x) = 1 2 Eω [( ψω(a|s)>x−Aω(s, a) )2] = 1
2 x>Eω
[ ψω(a|s)ψω(a|s)> ] x− Eω [ Aω(s, a)ψω(a|s) ]> x+ 1 2 Eω [ Aω(s, a) 2 ]
= 1 2 x>F (ω)x−∇J(ω)>x+ 1 2 Eω [ Aω(s, a) 2 ]
Since ∇2f(ω) = F (ω) is positive definite, f is strongly convex quardratic and thus it has unique minimizer h(ω) = F (ω)−1∇J(ω) obtained by solving h from the equation ∇fω(h) = F (ω)h − ∇J(ω) = 0. Hence,
Eω [∥∥ψω(a|s)>h(ω)−Aω(s, a)∥∥2]
= min h
Eω [( ψω(a|s)>h−Aω(s, a) )2] ≤ sup
ω min h
Eω [( ψω(a|s)>h−Aω(s, a) )2] := ζactorapprox, (57)
which proves the item 5.
The item 6 can be proved by the following inequality. Eω∗ [ Aω(s, a)− ψω(a|s)>h(ω) ] = ∫ νω∗(s)πω∗(a|s) [ Aω(s, a)− ψω(a|s)>h(ω) ] dsda
= ∫ νω(s)πω(a|s)
νω∗(s)πω∗(a|s) νω(s)πω(a|s)
[ Aω(s, a)− ψω(a|s)>h(ω) ] dsda
= Eω [νω∗(s)πω∗(a|s) νω(s)πω(a|s) [ Aω(s, a)− ψω(a|s)>h(ω) ]] ≤ √ Eω [(νω∗(s)πω∗(a|s)
νω(s)πω(a|s)
)2]√ Eω [( Aω(s, a)− ψω(a|s)>h(ω) )2] (i)≤ C∗√ζactorapprox, (58) where (i) uses Assumption 7 and the item 5. Multiplying −1 to the above inequality proves the item 6.
Next, the item 7 can be proved as follows.
Nk (i) =N (1− ηλF /2)−k/2∑K−1 k′=0(1− ηλF /2)−k ′/2
= N(1− ηλF /2)(K−1−k)/2(1−
√ 1− ηλF /2)
1− (1− ηλF /2)K/2 (ii)
≥ 2304C4ψ(κ+ 1− ρ) ηλ5F (1− ρ)(1− ηλF /2)(K−1)/2 (1− ηλF /2)(K−1)/2(ηλF /2) 1 + √ 1− ηλF /2
≥ 576C4ψ(κ+ 1− ρ)
λ4F (1− ρ) ,
where (i) uses the conditions that Nk ∝ (1 − ηλF /2)−k/2 and ∑K−1 k=0 Nk = N and (ii) uses the condition that N ≥ 2304C 4 ψ(κ+1−ρ)
ηλ5F (1−ρ)(1−ηλF /2)(K−1)/2
Finally, we will prove the item 8. Until the end of this proof, we use the underlying distribution that ai ∼ πt(·|si),si+1 ∼ Pξ(·|si, ai) for tN ≤ i ≤ (t+ 1)N − 1 in the t-th iteration of the multi-agent NAC algorithm (Algorithm 1).
The local averaging steps of zi,` := [z (1) i,` , . . . , z (M) i,` ] > yield the following consensus error bound.
M∑ m=1 (z (m) Tz − zTz )2 = ‖∆zi,Tz‖2 = ‖∆WTzzi,0‖2 (i) = ‖WTz∆zi,0‖2 (ii) ≤ σ2TzW ‖∆zi,0‖ 2
(iii) ≤ σ2TzW M∑ m=1 (z (m) i,0 ) 2 = σ2TzW M∑ m=1 [ ψ (m) t (a (m) i |si) >h (m) t,k ]2 (iv)
≤ C2ψσ 2Tz W M∑ m=1 ∥∥h(m)t,k ∥∥2 ≤ C2ψσ2TzW ∥∥ht,k∥∥2, where zTz := 1 M ∑M m=1 z (m) i,Tz
, (i) and (ii) use the items 1 and 3 of Lemma D.1 respectively, (iii) uses the equality that ‖∆‖ = 1, and (iv) uses the item 1 of Lemma D.5. Then, we define the following stochastic gradients of function fω .
∇̃ω(m)fωt(ht,k) := 1
Nk ∑ i∈Bt,k ψ (m) t (a (m) i |si)ψt(ai|si) >ht,k − ∇̂ω(m)J(ωt;Bt,k)
∇̃fωt(ht,k) := 1
Nk ∑ i∈Bt,k ψt(ai|si)ψt(ai|si)>ht,k − ∇̂J(ωt;Bt,k)
= [ ∇̃ω(1)fωt(ht,k); . . . ; ∇̃ω(M)fωt(ht,k) ] ,
∇̂ω(m)fωt(ht,k) := M
Nk ∑ i∈Bt,k ψ (m) t (a (m) i |si)z (m) i,Tz − ∇̂ω(m)J(ωt;Bt,k),
∇̂fωt(ht,k) := [ ∇̂ω(1)fωt(ht,k); . . . ; ∇̂ω(M)fωt(ht,k) ]> ,
where ∇̂ω(m)J(ωt;Bt,k) and ∇̂J(ωt;Bt,k) are defined in eqs. (35) & (36) respectively. Hence,∥∥∇̂fωt(ht,k)− ∇̃fωt(ht,k)∥∥2 =
M∑ m=1 ∥∥∇̂ω(m)fωt(ht,k)− ∇̃ω(m)fωt(ht,k)∥∥2 =
M∑ m=1 ∥∥∥ 1 Nk ∑ i∈Bt,k [ Mz (m) i,Tz − ψt(ai|si)>ht,k ] ψ (m) t (ai|si) ∥∥∥2 (i) ≤ 1 Nk ∑ i∈Bt,k M∑ m=1
∥∥M(z(m)i,Tz − zTz)ψ(m)t (ai|si)∥∥2 (ii)
≤ M2C2ψ Nk ∑ i∈Bt,k M∑ m=1 (z (m) i,Tz − zTz )2 ≤M2C4ψσ 2Tz W ∥∥ht,k∥∥2. (59) where (i) uses the equality that ψt(ai|si)>ht,k = ∑ m∈M z (m) i,Tz
= MzTz , (ii) uses the item 1 of Lemma D.5.
Since, ωt, ht,k ∈ Ft,k while {si, ai}i∈Bt,k are random. Hence, E [∥∥∇̂fωt(ht,k)−∇fωt(ht,k)∥∥2∣∣Ft,k]
= E [∥∥∥ 1 Nk ∑ i∈Bt,k [ ψt(ai|si)ψt(ai|si)> ] ht,k − ∇̂J(ωt;Bt,k)− F (ωt)ht,k +∇J(ωt) ∥∥∥2∣∣∣Ft,k] (i)
≤ 2E [∥∥∥ 1 Nk ∑ i∈Bt,k [ ψt(ai|si)ψt(ai|si)> ] − F (ωt) ∥∥∥2‖ht,k‖2∣∣∣Ft,k] + 2E
[∥∥∇̂J(ωt;Bt,k)−∇J(ωt)∥∥2∣∣Ft,k] (ii) = 2E
[∥∥∥ 1 Nk ∑ i∈Bt,k [ ψt(ai|si)ψt(ai|si)> ] − F (ωt) ∥∥∥2∣∣∣Ft,k]‖ht,k‖2 + 2E
[∥∥∇̂J(ωt;Bt,k)−∇J(ωt)∥∥2∣∣Ft,k] (iii)
≤ 18C4ψ(κ+ 1− ρ)
Nk(1− ρ) ‖ht,k‖2 + 2c4σ2T
′ W + 2c7 Nk + 32C2ψ M∑ m=1 ∥∥θ(m)t − θ∗ωt∥∥2 + 32C2ψζcriticapprox, (60)
where (i) uses the inequalities that ‖x + y‖2 ≤ 2‖x‖2 + 2‖y‖2 for any x, y ∈ Rd, (ii) uses the fact that ht,k ∈ Ft,k, and (iii) uses eq. (40) and applies Lemma D.2 to the quantity that X(s, a, s′, s̃) = ψt(a|s)ψt(a|s)> in which ωt ∈ Ft,k is fixed and ‖X(s, a, s′, s̃)‖F ≤ C2ψ . Combining eqs. (59) & (60) yields that
E [∥∥∇̂fωt(ht,k)−∇fωt(ht,k)∥∥2∣∣Ft,k]
≤2E [∥∥∇̂fωt(ht,k)− ∇̃fωt(ht,k)∥∥2∣∣Ft,k]+ 2E[∥∥∇̃fωt(ht,k)−∇fωt(ht,k)∥∥2∣∣Ft,k]
≤C4ψ [ 2M2σ2TzW +
36(κ+ 1− ρ) Nk(1− ρ)
] ‖ht,k‖2 + 4c4σ2T ′
W
+ 4c7 Nk + 64C2ψ M∑ m=1 ∥∥θ(m)t − θ∗ωt∥∥2 + 64C2ψζcriticapprox. (61)
Therefore, E [∥∥ht,k+1 − h(ωt)∥∥2∣∣Ft,k]
= E [∥∥ht,k − η∇̂fωt(ht,k)− h(ωt)∥∥2∣∣Ft,k]
(i) ≤ (1 + ηλF )E [∥∥ht,k − η∇fωt(ht,k)− h(ωt)∥∥2∣∣Ft,k]
+ [ 1 + (ηλF ) −1]E[∥∥η[∇̂fωt(ht,k)−∇fωt(ht,k)]∥∥2∣∣Ft,k] (ii) = (1 + ηλF )
∥∥ht,k − ηF (ωt)[ht,k − h(ωt)]− h(ωt)∥∥2 + η ( η + λ−1F ) E [∥∥∇̂fωt(ht,k)−∇fωt(ht,k)∥∥2∣∣Ft,k]
= (1 + ηλF ) ∥∥[I − ηF (ωt)][ht,k − h(ωt)]∥∥2
+ η ( η + λ−1F ) E [∥∥[∇̂fωt(ht,k)−∇fωt(ht,k)]∥∥2∣∣Ft,k]
(iii) ≤ (1 + ηλF )(1− ηλF )2 ∥∥ht,k − h(ωt)∥∥2
+ 2η
λF
( C4ψ [ 2M2σ2TzW +
36(κ+ 1− ρ) Nk(1− ρ)
] ‖ht,k‖2 + 4c4σ2T ′
W
+ 4c7 Nk + 64C2ψ M∑ m=1 ∥∥θ(m)t − θ∗ωt∥∥2 + 64C2ψζcriticapprox) ≤ (1− ηλF )
∥∥ht,k − h(ωt)∥∥2 + 2η
λF
( 2C4ψ [ 2M2σ2TzW +
36(κ+ 1− ρ) Nk(1− ρ)
] (‖ht,k − h(ωt)‖2 + ‖h(ωt)‖2)
+ 4c4σ 2T ′ W + 4c7 Nk + 64C2ψ M∑ m=1 ∥∥θ(m)t − θ∗ωt∥∥2 + 64C2ψζcriticapprox) (iv)
≤ (
1− ηλF 2 )∥∥ht,k − h(ωt)∥∥2 + 2η λF ( 2C4ψ [ 2M2σ2TzW + 36(κ+ 1− ρ) Nk(1− ρ) ]D2J λ2F
+ 4c4σ 2T ′ W + 4c7 Nk + 64C2ψ M∑ m=1 ∥∥θ(m)t − θ∗ωt∥∥2 + 64C2ψζcriticapprox) (v)
≤ (
1− ηλF 2 )∥∥ht,k − h(ωt)∥∥2 + 8η λF ( C4ψM 2σ2TzW + c9 Nk
+ c4σ 2T ′ W + 16C 2 ψ M∑ m=1 ∥∥θ(m)t − θ∗ωt∥∥2 + 16C2ψζcriticapprox) where (i) uses the inequality that ‖x+y‖2 ≤ (1+ηλF )‖x‖2 +[1+(ηλF )−1]‖y‖2 for any x, y ∈ Rd, (ii) uses the notation that ∇fωt(h) = F (ωt)h − ∇J(ωt) = F (ωt)[h − h(ωt)] and the fact that ωt, ht,k ∈ Ft,k, (iii) uses eq. (61) and the item 2 of this Lemma, (iv) uses the conditions that Tz ≥ ln(3DJC 2 ψ)
ln(σ−1W ) and the item 7 of this Lemma, and (v) uses the notation that c9 :=
18C4ψD 2 J (κ+1−ρ)
λ2F (1−ρ) + c7.
Then, taking unconditional expectation of the above inequality and iterating it over k = 0, 1, . . . ,K−1 yield that
E [∥∥ht − h(ωt)∥∥2] = E[∥∥ht,K − h(ωt)∥∥2] ≤ (
1− ηλF 2
)K E [∥∥ht,0 − h(ωt)∥∥2]+ 8η
λF K−1∑ k=0 ( 1− ηλF 2 )K−1−k ( C4ψM
2σ2TzW + c9 Nk + c4σ 2T ′ W + 16C 2 ψ M∑ m=1 E [∥∥θ(m)t − θ∗ωt∥∥2]+ 16C2ψζcriticapprox)
(i) ≤ (
1− ηλF 2
)K E [∥∥ht−1 − h(ωt)∥∥2]
+ 16
λ2F
( C4ψM 2σ2TzW + c4σ 2T ′ W + 16C 2 ψ M∑ m=1 E [∥∥θ(m)t − θ∗ωt∥∥2]+ 16C2ψζcriticapprox)
+ 8ηc9[1− (1− ηλF /2)K/2] NλF (1− √ 1− ηλF /2) K−1∑ k=0 ( 1− ηλF 2 )(K−1−k)/2 (ii)
≤ (
1− ηλF 2
)K E [∥∥ht−1 − h(ωt)∥∥2]+ 16
λ2F
( C4ψM 2σ2TzW + c4σ 2T ′ W + 16C 2 ψζ critic approx ) +
256C2ψ λ2F
( σ 2T ′c W β 2c2 + 2M [ c3 ( 1− λB 8 β )Tc + c1 Nc ]) +
8ηc9 NλF (1− √
1− ηλF /2)2 (iii) ≤ (
1− ηλF 2
)K E [∥∥ht−1 − h(ωt)∥∥2]+ 16
λ2F
( C4ψM 2σ2TzW + c4σ 2T ′ W + 16C 2 ψζ critic approx ) +
256C2ψ λ2F
( σ 2T ′c W β 2c2 + 2M [ c3 ( 1− λB 8 β )Tc + c1 Nc ]) + 128c9 Nηλ3F
(62)
(iv) ≤ 3 (
1− ηλF 2
)K E [∥∥ht−1 − h(ωt−1)∥∥2 + ∥∥h(ωt−1)∥∥2 + ∥∥− h(ωt)∥∥2]
+ 16
λ2F
( C4ψM 2σ2TzW + c4σ 2T ′ W + 16C 2 ψζ critic approx ) +
256C2ψ λ2F
( σ 2T ′c W β 2c2 + 2M [ c3 ( 1− λB 8 β )Tc + c1 Nc ]) + 128c9 Nηλ3F
(v) ≤ 3 (
1− ηλF 2
)K E [∥∥ht−1 − h(ωt−1)∥∥2]+ 6D2J
λ2F
( 1− ηλF
2 )K + 16
λ2F
( C4ψM 2σ2TzW + c4σ 2T ′ W + 16C 2 ψζ critic approx ) +
256C2ψ λ2F
( σ 2T ′c W β 2c2 + 2M [ c3 ( 1− λB 8 β )Tc + c1 Nc ]) + 128c9 Nηλ3F ,
where (i) uses the notation that ht,0 = ht, the item 7 of this Lemma and the inequality that ∑K−1 k=0 ( 1 − ηλF2 )K−1−k ≤ 2ηλF , (ii) uses Lemma D.4, (iii) uses the inequality that 1 (1− √ 1−ηλF /2)2 = (1+ √ 1−ηλF /2)2 (ηλF /2)2 ≤ 16(ηλF )2 implied by the item 2 of this Lemma, (iv) uses the inequality that ‖x+ y + z‖2 ≤ 3‖x‖2 + 3‖y‖2 + 3‖z‖2,∀x, y, z ∈ Rd, and (v) uses the items 4 of this Lemma. Taking unconditional expectation of the above inequality and iterating it over t yield that
E [∥∥ht − h(ωt)∥∥2]
(i) ≤ [ 3 (
1− ηλF 2
)K]t E [∥∥h0 − h(ω0)∥∥2]+ 12D2J
λ2F
( 1− ηλF
2 )K + 32
λ2F
( C4ψM 2σ2TzW + c4σ 2T ′ W + 16C 2 ψζ critic approx ) +
512C2ψ λ2F
( σ 2T ′c W β 2c2 + 2M [ c3 ( 1− λB 8 β )Tc + c1 Nc ]) + 256c9 Nηλ3F
(ii) ≤ [ 3 (
1− ηλF 2
)K]t[( 1− ηλF
2
)K E [∥∥h−1 − h(ω0)∥∥2]
+ 16
λ2F
( C4ψM 2σ2TzW + c4σ 2T ′ W + 16C 2 ψζ critic approx ) +
256C2ψ λ2F
( σ 2T ′c W β 2c2 + 2M [ c3 ( 1− λB 8 β )Tc + c1 Nc ]) + 128c9 Nηλ3F ] +
12D2J λ2F
( 1− ηλF
2
)K + 32
λ2F
( C4ψM 2σ2TzW + c4σ 2T ′ W + 16C 2 ψζ critic approx )
+ 512C2ψ λ2F
( σ 2T ′c W β 2c2 + 2M [ c3 ( 1− λB 8 β )Tc + c1 Nc ]) + 256c9 Nηλ3F
(iii) ≤ 2 (
1− ηλF 2 )K(∥∥h−1∥∥2 + D2J λ2F ) +
12D2J λ2F
( 1− ηλF
2
)K + 48
λ2F
( C4ψM 2σ2TzW + c4σ 2T ′ W + 16C 2 ψζ critic approx ) +
768C2ψ λ2F
( σ 2T ′c W β 2c2 + 2M [ c3 ( 1− λB 8 β )Tc + c1 Nc ]) +
384c9 ηλ3F
ηλ5F (1− ρ)(1− ηλF /2)(K−1)/2
2304C4ψ(κ+ 1− ρ) (iv) ≤ c10 (
1− ηλF 2
)(K−1)/2 + c11σ 2Tz W + c12σ 2T ′ W + c13β 2σ 2T ′c W
+ c14
( 1− λB 8 β )Tc + c15 Nc + c16ζ critic approx
where (i) uses the inequality that 3(1 − ηλF /2)K ≤ 1 implied by the condition that K ≥ ln 3ln[(1−ηλF /2)−1] , (ii) uses eq. (62) with t = 0, (iii) uses the condition that N ≥ 2304C4ψ(κ+1−ρ) ηλ5F (1−ρ)(1−ηλF /2)(K−1)/2 as well as the inequalities that ∥∥h−1 − h(ω0)∥∥2 ≤ 2∥∥h−1∥∥2 +
2 ∥∥h(ω0)∥∥2 ∗≤ 2∥∥h−1∥∥2 + 2D2Jλ−2F (* uses the item 4 of this Lemma) and that 3(1− ηλF /2)K ≤ 1, (iv) denotes that c10 := 2‖h−1‖2 + 14D 2 J
λ2F +
c9λ 2 F
C4ψ , c11 :=
48C4ψM 2
λ2F , c12 := 48c4λ2F , c13 := 768c2C
2 ψ
λ2F ,
c14 := 1536Mc3C
2 ψ
λ2F , c15 :=
1536Mc1C 2 ψ
λ2F , c16 := 768C2ψ λ2F . This proves the item 8 of this Lemma.

heading: E EXPERIMENT SETUP AND ADDITIONAL RESULTS
text: In this section, we present all the details of experiment setup and additional experiment results.
E.1 EXPERIMENT SETUP
We simulate a fully decentralized ring network with 6 fully decentralized agents, using communication matrix with diagonal entries 0.4 and off-diagnonal entries 0.3. The shared state space contains 5 states and each agent can take 2 actions. We adopt the softmax policy πω(a|s) ∝ eωs,a . The entries of the transition kernel and the reward functions are independently generated from the standard Gaussian distribution (with proper normalization of the absolute value for the transition kernel). We use the rows of a 5-dimensional identity matrix as state features. We set the discount factor γ = 0.95.
We implement and compare four decentralized AC-type algorithms in this multi-agent MDP: our decentralized AC in Algorithm 1, our decentralized NAC in Algorithm 3, an existing decentralized AC algorithm (Algorithm 2 of (70)) that uses a linear model to parameterize the agents’ averaged reward R(s, a, s′) = ∑ i λifi(s, a, s
′) (we name it DAC-RP1 for decentralized AC with reward parameterization) 5, and our proposed modified version of DAC-RP1 to incorporate minibatch, which we refer to as DAC-RP100 with batch size N = 100. For our Algorithm 1, we choose T = 500, Tc = 50, T ′c = 10, Nc = 10, T
′ = Tz = 5, β = 0.5, {σm}6m=1 = 0.1, and consider batch size choices N = 100, 500, 2000. Algorithm 3 uses the same hyperparameters as those of Algorithm 1 except that T = 2000 in Algorithm 3. We select α = 10, 50, 200 for Algorithm 1 with N = 100, 500, 2000 respectively, and Tz = 5, α = 0.1, 0.5, 2, η = 0.04, 0.2, 0.8, K = 50, 100, 200, Nk ≡ 2, 5, 10 for Algorithm 3 with N = 100, 500, 2000, respectively. For DAC-RP1 that was originally designed for discount factor γ = 1, we slightly adjust it to fit our setting where 0 < γ < 16.
5The original algorithm in (70) uses the parameterization R(s, a) = ∑ i λifi(s, a), and we extend to our
setting where the rewards also depend on the next state s′. 6(70) defined the Q-function Qθ(s, a) = E [ rt+1 − J(θ) ] for policy parameter θ and used the temporal differences δit = rit+1 − µit + Vt+1(vit) − Vt(vit) and δ̃it = Rt(λit) − µit + Vt+1(vit) − Vt(vit) for critic
For this adjusted DAC-RP1, we select diminishing stepsizes βθ = 2(t+ 1)−0.9, βv = 5(t+ 1)−0.8 as recommended in (70) and use the rows of a 1600-dimensional identity matrix as the reward features {fi(s, a, s′) : s, s′ ∈ S, a ∈ A} (i = 1, 2, . . . , 1600) to fully express R(s, a, s′) over all the 5 × 26 × 5 = 1600 triplets (s, a, s′). DAC-RP100 has batchsizes 100 and 10 for actor and critic updates respectively, and selects constant stepsizes βv = 0.5, βθ = 10. This setting is similar to Algorithm 1 with N = 100 to inspect the reason of performance difference between Algorithm 1 and DAC-RP1. All the algorithms are repeated 10 times using initial state 0 and the same initial actor parameter ω0 generated from standard Gaussian distribution.
E.2 GRADIENT NORM CONVERGENCE RESULTS IN RING NETWORK
Figure 2 plots ‖∇J(ωt)‖2 v.s. communication complexity (t(Tc + Tc + T ′) = 65t, t(Tc + Tc + T ′ + Tz) = 70t and 2t for Algorithms 1 & 3, and both DAC-RP algorithms, respectively)7 and sample complexity (t(TcNc +N), 2t and 110t for both of our AC-type algorithms, DAC-RP1 and DAC-RP100, respectively).8 For each curve, its upper and lower envelopes denote the 95% and 5% percentiles of the 10 repetitions, respectively.
Similar to the result of accumulative reward J(ωt) shown in Figure 1, it can be seen from Figure 2 that the communication and sample efficiency of both our decentralized AC and NAC algorithms improve with larger batchsize due to reduced gradient variance, which matches our understanding in Theorems 1 & 2. Our decentralized AC and NAC algorithms significantly outperform DAC-RP1 which has batchsize 1. Using mini-batch, DAC-RP100 outperforms a lot than DAC-RP1, and converges to critical points earlier than Algorithm 1. However, it can be seen from Figure 1 that such early convergence turns out to have much lower J(ωt) than Algorithm 1 with N = 100 and Nc = 10. Such a performance gap is caused by two reasons: (i) Both DAC-RP1 and DAC-RP100 suffer from an inaccurate parameterized estimation of the averaged reward, and the mean relative estimation errors of both DAC-RP1 and DAC-RP100 are over 100% 9. In contrast, our noisy averaged reward estimation achieves a mean relative error in the range of 10−5 ∼ 10−4. 10 ; (ii) Both DAC-RP1
update and actor update respectively. To fit 0 < γ < 1, we use δit = rit+1 + γVt+1(vit) − Vt(vit) and δ̃it = Rt(λ i t) + γVt+1(v i t)− Vt(vit) where µit ≈ J(θt) is removed since Qθ(s, a) = E(rt+1). In addition, we used two different chains generated from transition kernels P , Pξ respectively for critic update and actor update as in our Algorithm 1.
7Each update of our decentralized AC uses Tc + T ′c and T ′ communication rounds for synchronizing critic model and rewards, respectively. Each update of our decentralized NAC uses Tc + T ′c, T ′, T ′z communication rounds for synchronizing critic model, rewards and scalar z, respectively. Each update of both DAC-RP1 and DAC-RP100 uses 1 communication round for synchronizing v and λ respectively.
8DAC-RP1 uses 1 sample for actor and critic updates respectively. DAC-RP100 uses 100 and 10 samples for actor and critic updates respectively.
9The relative reward estimation error at the t-th iteration of both DAC-RP1 and DAC-RP100 is defined as A/B where A = 1 M|S|2|A| ∑M m=1 ∑ s,s′∈S ∑ a∈A[R(s, a, s ′) − ∑ i λ (m) i fi(s, a, s
′)]2 and B = 1 |S|2|A| ∑ s,s′∈S ∑ a∈AR(s, a, s
′)2. 10At the t-th iteration of Algorithms 1 & 3, we focus on r(m)t = 1 N ∑(t+1)N−1 i=tN R (m) i as the estimation of
the batch-averaged reward rt = 1N ∑(t+1)N−1 i=tN Ri since its estimation error affects the accuracy of the policy gradient (4). The relative estimation error is defined as 1 Mr2t ∑M m=1(r (m) t − rt)2.
and DAC-RP100 apply only a single TD update per-round, and hence suffers from a larger mean TD learning error (about 2% and 1% for DAC-RP1 and DAC-RP100, respectively), whereas our algorithms perform multiple TD learning updates per-round and achieve a smaller mean relative error (about 0.3% and 0.07% for our decentralized AC and NAC respectively) 11. All these relative errors are averaged over iterations.
E.3 ADDITIONAL EXPERIMENTS IN FULLY CONNECTED NETWORK
To investigate the effect of network topology on the performance of our algorithms, we also conduct the above experiments on a fully connected network with 6 fully decentralized agents, using communication matrix with diagonal entries 0.4 and all the other entries 0.12. The MDP environment and all the hyperparameters are the same as the above experiments for ring network. Figures 3 & 4 plot the learning curves of the optimality gap J∗ − J(ωt) and ‖∇J(ωt)‖2 respectively for fully connected network. To make comparison, we plot J∗ − J(ωt) and ‖∇J(ωt)‖ in Figures 5 & 2 respectively for the above experiments with ring network. It can be seen by comparing these figures that network topology does not much affect the performance of these algorithms, so the conclusions for ring network that we summarized right before this subsection also holds for fully connected network.
11The TD error at the t-th iteration is defined as 1 M‖θ∗ωt‖ 2
∑M
m=1 ‖θ (m) t − θ∗ωt‖ 2.
E.4 TWO-AGENT CLIFF NAVIGATION
receives −0.5 reward otherwise. If an agent is not at “X” or “D” and selects a direction that points outside the grid, then it stays in the previous location and receives −1 reward. The optimal path for both agents is the red path shown in Figure 6, which has the minimum accumulative reward J∗ = −0.1855 under the discount factor γ = 0.95. For our Algorithm 1, we choose T = 500, Tc = 50, T ′c = 10, Nc = 10, T
′ = Tz = 5, β = 0.5, {σm}6m=1 = 0.1, and consider batch size choices N = 100, 500, 2000. Our Algorithm 3 uses the same hyperparameters as those of Algorithm 1 except that we choose T = 2000. We select α = 1, 5, 20 for Algorithm 1 with N = 100, 500, 2000 respectively, and Tz = 5, α = 0.002, 0.01, 0.04, η = 0.002, 0.01, 0.04, K = 50, 100, 200, Nk ≡ 2, 5, 10 for Algorithm 3 with N = 100, 500, 2000, respectively. For DAC-RP1, we select T = 10000, βv = 10(t+ 1)−0.6 and βθ = 5(t+ 1)−0.6. For DAC-RP100, we use T = 2000 and batchsizes 100 and 10 for actor and critic updates respectively, and selects constant stepsizes βv = 0.5, βθ = 1. This setting is similar to Algorithm 1 with N = 100 to inspect performance difference between Algorithm 1 and DAC-RP1.
We plot J∗ − J(ωt) and ‖∇J(ωt)‖ in Figures 7 & 8 respectively. It can be seen from these figures that both our Algorithm 1 & Algorithm 3 significantly reduce the function value gap J∗− J(ωt), and their convergence is faster with a larger batchsize. In contrast, the function value gaps of DAC-RP1 and DAC-RP100 do not decrease sufficiently and converge to a high value. In particular, since DAC-RP100 achieves a larger function value gap than our Algorithm 1 with N = 100 while their hyperparameter choices are similar, we attribute this performance gap to the inaccurate average reward estimation and TD error, as we analyzed in Appendix E.2.

heading: F CONSTANT SCALARS
text: The following global constants are frequently used.
M : The number of agents.
γ: Discount rate.
Rmax: The reward bound such that 0 ≤ R(m)(s, a, s′) ≤ Rmax for any s, s′ ∈ S and a ∈ A (Assumption 3). Hence, 0 ≤ R(m)(s, a, s′), R(m)i , Ri ≤ Rmax. σW ∈ [0, 1): The second largest singular value of W . ω∗ := maxω J(ω) denotes the optimal policy parameter.
The following constants are defined in Lemma D.3.
CB := 1 + γ.
Cb := Rmax. λφ := λmin ( Es∼µω [φ(s)φ(s)>] ) > 0 satisfies Assumption 4.
λB := 2(1− γ)λφ > 0. (Assumption 4 implies that λφ > 0.)
Rθ := 2Cb λB .
The policy-related norm bounds and Lipschitz parameters are defined as follows.
Cψ, Lψ, Lπ > 0 defined in Assumption 2: For all s ∈ S, a ∈ A and ω, ω̃, ‖ψω(a|s)‖ ≤ Cψ, ‖ψω̃(a|s)− ψω(a|s)‖ ≤ Lψ‖ω̃ − ω‖ and dTV ( πω̃(·|s), πω(·|s) ) ≤ Lπ‖ω̃ − ω‖.
Lν := Lπ[1 + logρ(κ −1) + (1− ρ)−1].
LQ := 2RmaxLν 1−γ .
LJ := Rmax(4Lν + Lψ)/(1− γ).
DJ := CψRmax
1−γ .
LF := 2Cψ(LπCψ + LνCψ + Lψ).
Lh := 2λ −1 F (DJλ −1 F LF + LJ) where λF := infω∈Ω λmin[F (ω)] > 0 (λmin denotes the minimum eigenvalue) which satisfies Assumption 6.
The following constants are defined to simplify the notations in the proof.
c1 := 1920(C2BR 2 θ+C 2 b )[1+(κ−1)ρ]
(1−ρ)λ2B .
c2 := 2 (
2MCb 1−σW
)2 .
c3 := 2 (∥∥θ−1∥∥2 +R2θ) where θ−1 is the initial parameter of decentralized TD (Algorithm 2).
c4 := 4MC 2 ψR 2 max.
c5 := 16c2C 2 ψ .
c6 := 32Mc3C 2 ψ .
c7 := 16C 2 ψR 2 maxσ
2 + 36C2ψ(Rmax+2Rθ) 2(κ+1−ρ) 1−ρ .
c8 := 32Mc1C 2 ψ .
c9 := 18C4ψD 2 J (κ+1−ρ)
λ2F (1−ρ) + c7.
c10 := 2‖h−1‖2 + 14D 2 J
λ2F +
c9λ 2 F
C4ψ where h−1 is the initial natural gradient of Algorithm 3.
c11 := 48C4ψM 2
λ2F .
c12 := 48c4 λ2F .
c13 := 768c2C
2 ψ
λ2F .
c14 := 1536Mc3C
2 ψ
λ2F .
c15 := 1536Mc1C
2 ψ
λ2F .
c16 := 768C2ψ λ2F .
c17 := Es∼νω∗ [ KL ( πω∗(·|s)||π0(·|s) )] + 4LψC 2 ψRmax
λ2F .
c18 := Cψ √ c10 + c10Lψ ( 1 +
4C4ψ λ2F
) .
c19 := Cψ √ c11 + c11Lψ ( 1 +
4C4ψ λ2F
) .
c20 := Cψ √ c12 + c12Lψ ( 1 +
4C4ψ λ2F
) .
c21 := Cψ √ c13 + c13Lψ ( 1 +
4C4ψ λ2F
) .
c22 := Cψ √ c14 + c14Lψ ( 1 +
4C4ψ λ2F
) .
c23 := Cψ √ c15 + c15Lψ ( 1 +
4C4ψ λ2F
) .
c24 := c16Lψ
( 1 +
4C4ψ λ2F
) .

Review summaries:
This paper developed two sample and communication efficient decentralized actor-critic algorithms for multi-agent reinforcement learning. Specifically, the authors proposed decentralized AC and natural AC algorithms that can be private and efficient for different agents to learn. They added noise the local rewards of agents, which were shared among different agents. Moreover, the authors adopted mini-batch updates for the actors and critics in these two algorithms. Theoretically, the authors showed that both algorithms were able to achieve the state-of-the-art sample complexities. To validate the proposed algorithms, they used a simple environment to show the superiority over the existing decentralized AC algorithm. Overall, the investigated topic in this paper is absolutely interesting. The sample and communication complexities of decentralized MARL algorithms remain active research areas. While the mathematical analysis in this work looks good, the numerical results to me don't look very convincing. Additionally, there are quite a few points I have in mind regarding the proposed algorithm and the relevant analysis.

In this work, the authors propose two decentralized policy gradient-type algorithms for multi-agent reinforcement learning, namely, a decentralized actor-critic algorithm and a decentralized natural actor-critic algorithm. The stochastic updates of both algorithms preserve the agents' privacy information, including their local actions and local rewards. The authors analyze the finite-time convergence rate of both algorithms under Markovian sampling and linear function approximation, and prove that both algorithms achieve the state-of-the-art sample complexities and improved communication complexities.