Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis
Authors: Ziyi Chen
Yi Zhou
Rong-Rong Chen
Shaofeng Zou
Venue: ICLR 2022 Submitted (2022)

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 do not preserve the privacy of agents or are not sample and communication-efficient. In this work, we develop two decentralized AC and natural AC (NAC) algorithms that are private, and sample and communication-efficient. In both algorithms, agents share noisy information to preserve privacy and adopt mini-batch 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 the proposed decentralized AC and NAC algorithms achieve the state-of-the-art sample complexities $\mathcal{O}(\epsilon^{-2}\ln\epsilon^{-1})$ and $\mathcal{O}(\epsilon^{-3}\ln\epsilon^{-1})$, respectively, and the same small communication complexity $\mathcal{O}(\epsilon^{-1}\ln\epsilon^{-1})$. Numerical experiments demonstrate that the proposed algorithms achieve lower sample and communication complexities than the existing decentralized AC algorithm.

Under review as a conference paper at ICLR 2022
SAMPLE AND COMMUNICATION-EEFICERR DECEN- TRALIZED ACTOR-CRITIC ALGORIHTMS WITH FINITE- TIME ANALYSIS
Anonymous authors Paper under double-blind review
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-efficieeee develop two decentralized AC and natural AC (NAC) algorithms that are sample and communication
In this work, we
and avoid sharing agents' local actions and policies In both algorithms,, agents share only noisy rewards and adopt mini-batee local policy gradient updates to improve sample and communication efficiency. Particularly for decentralized NAC, we develop 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 Ole 2 e-! and O(e In IIne"), respectively, and achieve an improved communication complexity O(e lnn Numerical experiments demonstrate that the proposed algorithms achieve lower sample and communication complexities than the existing decentralized AC algorithm.
INTRODUCTION
Multi-agent reinforcement learning (MARL) has achieved great success in various application domains, including control (66; 10; 51), roboties (64), wireless sensor networks (24; 67), intelligent systems (71), etc. In MARL, 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, c.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 and do not have finite-time convergence
algorithms are not sample and communication--fficie guarantee, especially under the practical Markovian sampling setting. Therefore, we aim to address the following important question.
Ql: Can we develop a decentralized AC algorithm that is convergent, sample and communication- efficient, and does not require sharing agents' local actions and policies? ?
On the other hand, as 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 need to develop a fully decentralized and computationally tractable scheme

---

Under review as a conference paper at ICLR 2022
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 computatioally tractable and communication-effiienin decentralized NAC algorithm that has low finite-time sample and communication complexity?
In this study, provide affirmative answers the above two questions by developing fully decen- tralized AC and NAC algorithms that are sample and communication- -fficattinefficinnt,, and do not reveal agents' local actions and policies. We also develop rigorous finite- unite-time analysis of these algorithms under Markovian sampling. Our contributions are summarized as follows.
Table 1: List of complexities of the existing AC and NAC algorithms for achieving |||l V [w)]] S c and E[J(w") - [(w)] I c, respectively.
Share local
Sampling scheme
Sample complexity
Communication complexity
Algorithm
Papers
action/policy
(54)
i.i.d.
(
(38)
i.i.d.
O
Centralized AC
(25)
i.i.d.
O
(61)
Markovian
O 2.5
2: In
(56)
Markovian
((c-25)
(60)
Markovian
Ole 'Ine O(n
(70: 69; 15)
(72: 27; 26)
Markovian
Decentralized AC
(70; 33)
Markovian
This work
Markovian
Ole O(ee"ne"")
Ole Ine"")
(54)
i.idd.
Ole O(e-3))
Centralized NAC
(61)
Markovian
Ole "In"E"
(60)
Markovian
O (nc
Decentralized NAC
This work
Markovian
Ole ((e
O(e O(e-)
1.1 OUR CONTRIBUTIONS
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 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-corrupter 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 critie 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 decentralized NAC algorithm, we additionally adopt the following design to compute the inverse of the Fisher information matrix an efficient and decentralized way.
By reformulating the natural policy gradient as the min- imizer 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
Decentralized Natural Policy Gradient:
In this table, Ø(-) 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.
2

---

Under review as a conference paper at ICLR 2022
scalar variables with their neighbors. In partieular, 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 ((c=2 In 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 In ). In particular, our analysis involves new technical developments. First, we need 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 SGI) 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.
and
In c-!)
1.2 RELATED WORK
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 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 for their sample complexities. Moreover, (60) improve the finite-time sample complexities of the above works to the state-of-the- art result for both centralized AC and NAC by leveraging mini batch sampling, and our sample complexities match these state-of-the- 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 Enite-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 noopeaaive-competiin
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 '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 sample complexity result O(E-E) in the i.i.d. setting for NPG, which is worse than the state-of-the-and result O In lne") of both centralized NAC (60) and our decentralized NAC with Markovian samples. (3) proposes decentralized PG in 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 2.) (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 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
3

---

Under review as a conference paper at ICLR 2022
its own state and takes its own action. It establishes 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 assumption that the variance of the stochastic gradient is uniformly bounded, it establishes a non-asymptotic convergence rate to an approximate stationary point.
2 REVIEW OF MULTI-AGENT REINFORCEMENT LEARNING
In this section, first introduce some standard settings of RL. Consider agent that starts from an initial state 8o ~ & and collects a trajectory of Markovian samples {*c: 0z Re)e l C x A x I by interacting with an underlying environment (with transition kernel P) following parameterized policy Th with induced stationary state distribution M.s The agent aims to learn an optimal policy that maximizes the expected accumulated reward [(w) (1 >) Ei= 7 ReR: where y E (0, 1) is a discount factor. The marginal state distribution is denoted (s,) and the visitation measure
is defined as vw (s) == (1 - 7) Σx > (P = 8), both of which depend on the policy parameter 5 and the transition kernei P. We also define the mixed transition kernel Pe Pe((ls, a)
yP((ss, a) + (1 - 7))(,) whose stationary state distribution is known to be Vw-
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 IR MRM, At any time all the agents share a common state st. Then, (mm) following its own current policy s, (-1s) parameterized by new state 814-1 and every agent m receives local reward re(")) In this MARL setting, each agent m can only
every agent m takes an action at (m) Jm=1 are taken, the global state 8t transfers
w (m()) After all the actions a, {az
access the global state {t its actions (a{m)), }. and rewards (R(m)), ) and policy n, (mm)) Next, define the joint policy Tx. (at (t) = I 1m=1 (a; (m)] (ss) parameterized by wt = [w, (1) :...:..... w (M)
(m)
and define the average reward Rg == ΣM A!m) The goal of the agents to collaboratively learn the optimal joint policy that maximizes the expected accumulated average reward (ww)
(1 - [> >" Re 5o ~ <]. Throughout, we consider the setting that the agents keep interacting with the environment and observing trajectory of MDP transition samples, which are further used
to learn the optimal joint policy.
SAMPLE AND COMMUNICATION-EFFIIENN DECENTRALIZED AC
In this section, we propose a decentralized actor-critic (AC) algorithm that is sample and communication--fficientt 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 x(T), aims to update the policy parameter (m()) using the local policy gradient
V wim [ws). Under linear approximation of the value function Vo(s) Rs dbs) T where d(s) is the feature vector, the local policy gradient has the following stochastic approximation.
Vatin J (we) Re 70(5641) 0lm) - ((x)) TT(mm)
(a. (s)),
where (m)
(mi) (-1st), 8041 Pe((10ts (1)181,5)),60 6671 a.). m(())
(2)
Here, m( is agent m's critic parameter and wi ((m)) (afm)) (sc) = - Valm In I (m²) (a; (m))ss)))) is the local score function. It is clear that both o(T))) and ()))) (a(m))ss)) can be obtained/computed by agent m using the local information. However, the average reward RS 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 I) 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.
4

---

Under review as a conference paper at ICLR 2022
1. Efficient Policy Gradient Estimation. We propose 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 R, in eq. (I), we let each agent m generate a noisy local reward Ri(")) = _r("))
(1 + <(m)) and share with other agents, where (m) (O, o 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
R2 (! using its own noisy reward, i.e., R2,0 R( Then, each agent m performs decentralized
local averaging with its neighbors Nn. for T" iterations, i.e.,
R Em'eN,. Wm,m' Ri,e) f 0,1,...,, T 1.
After that, agent m obtains the final estimate Rim)) == R( can be shown that Ri(m) converges
to the averaged noisy reward 17 ΣM R(m) 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 factor of 3 Therefore, to obtain an accurate estimation, the network needs 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 to estimate the local policy gradient, which then takes the following form.
awrmy) (4+1)N-1 Σ
R m)
+ TT o(s;) @
(mm) w (a [s)),
(4)
where Ti!") is an estimation of Rt obtained by agent m following the process described in eq. (3). Intuitively, each R,(') is corrupted by a zero-mean noise with variance ( (())) due to averaging over the agents. Then, the mini-batch samples further help scale the noise variance by a factor of v. Consequently, with 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(")) with their neighbors, and the noise variance can be adjusted based on the desired level such that R!()) 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 additional parameterized reward model.
Sample-efficintt 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 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.
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.
coammunicationeeffccee
Remark. We note that the local mini- hini-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 the fly. There 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 mini-batch of N, Markovian samples. Then, starting from fixed initialization (.))) 0_1, i, agent m performs T. iterations of decentralized TD updates as follows,
where {se follows the transition kernel P and of (m) न. (m) (-Ist): for t' 0, 1,,1,... Te-1.
(++1)N,-1
(m)
Σ Wm. (mm') +
3
Σ
(()) + 70($441) T Tm ((s.) To ((s.). (5)
No
nn N.
i=NN.
"More generally, any noise with zero mean and variance oi will work.
5

---

Under review as a conference paper at ICLR 2022
Then, the updated critic parameter is set be o(m) :- ( To further reduce the consensus error, we perform additional T" steps of local model averaging, also adopted in (12). The pseudo code of the entire decentralized AC algorithm is summarized in Algorithms and 2 below.
Algorithm 2 Decentralized TD (critic update)
Algorithm 1 Decentralized Actor-Critic
Initialize: Critic parameter 01,0 = 8-1.
Initialize: Actor-critic parameters wo, 8-1.
for critic iterations t' = 0, .,. T. do
for actor iterations t = 0, 0......,
do Critic update 0₁: by Algorithm 2.
Collect Ne Markovian samples following
policy मे and transition kernel P.
Collect N Markovian samples by eq. (2).
for agents 1, ,.... M in parallel do
for agents m I..... M in parallel do
Send local critic parameters. Decentralized TD update in eq. (5).
Send noisy local rewards and perform
T' local average steps following eq. (3).
end end iterations t' = Te, T do
Compute the estimated local policy
gradient V J following eq. (4).
for
Actor update on W/t
for agents m = 1, M in parallel do (lm) 11441 Em'eN.. W Wm,m² ol
(m) 1+1 = w + aa wil (wr).
end end
end
end
Output: Wp with 7 uniform f1.2....,T)
Output: 02 = 01.T.TT-
4 UNITE-TIME CONVERGENCE ANALYSIS OF DECENTRALIZED AC
In this section, we analyze the finite-time convergence of Algorithm 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, Pe, denote pwa Va respectively as their stationary state distributions under policy nw and denote P, Pg respectively their marginal state distributions. Then, there exist constants k. > and E (0, 1) such that for all 1 2 O,
sup drv (st 80 , S rip', sup (P& (8e 80 =)) uw) S kxp sES
(6)
sES
where drv Q) denotes the intal-vriaatinn distance between probability measures P and Q.
Assumption 2. There exist constants Cvp, Lo,, Lx > O such that for all w, W E Q, 8 E S and a E A. (a|s)) < C₁,, [[)s(a)s)) - Ahe (als)) < by 1 - will and drv (mw(<1s), (-16) < L l| - will
Assumption 3. There exists Rmax O such that for any agent m and any Markovian sample (s, a, s'), we have 0 & (1,)(ss,,)))) s') Rmax-
Assumption 4. The feature vectors satisfy [|o(s)]l S 1 for all E S. There exists constant À 0 such that Amin (Ee-uy (o(s)((s))) 2 N for all
Assumption 5. The communication matrix W E MMM of the decentralized network is doubly stochastic, and its second largest singular value satisfies ow E 10.
Assumption 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 Φbs) Assumption widely used in decentralized optimization (43; 41) and multi-agent reinforcement learning (46; 53; 12), which ensures that all the decentralized agents can reach global consensus.
With the above assumptions, we obtain the following finite-time convergence result of the decen- tralized AC algorithm. Throughout, we follow (60; 56) and define the critic approximation error as caritic
Saporox := sup.,, Egwee (Va (s) o(s) 82 where 6 is the optimal critic parameter (see its definition right before Lemma D.3 in Appendix D). We also define sample complexity the total number of Markovian samples required for achieving E[]] [[))]] S c. All the universal constants are listed in Appendix F.

---

Under review as a conference paper at ICLR 2022
Theorem 1. Let Assumptions 1-5 hold and adopt the hyperparameters of the decentralized TD _ T' 2 In Then, the output of the in Algorithm 2 following Lemma D.4, Choose a I AL.' decentralized AC in Algorithm has the following convergence rate.
2lnow
E [
4Rmax
+4(cloW 22' +c33B'ow)
21. + )
dB To 40T 8
4cs Nc
+64C%
serie @S Sappixx
Ta
Moreover, to achieve [ S e for any 128C x ccritic we can choose T, N,N,No O and TV = O e ). Consequently, the overall sample complexity T(IoNc+N) In Olc-2Inc
ln and the communication complexities for synchronizing linear model parameters and rewards are T(T + TT) = O(c O( Inc and TT = =0 In "), respectively.
Remark. We note that the constraint on e naturally induced by the critic approximation error. In particular, if this appreximation errors vanish, for example, when the dimension of features equals the number of states and the parameterized policy space sufficiently expressive, then we can achieve arbitrarily small target accuracy.
To the best of our knowledge, Theorem I provides the first finite-time analysis of decentralized AC under Markovian sampling. To elaborate, under any pre-specified variance o of the reward noise, our result shows that the gradient norm asymptotically converges to the order O(N-1 + .o + Ceriti ) which can be made arbitrarily close to the linear model approximation error Cappin by choosing sufficiently large batch sizes N, Ne- In partieular, exact gradient convergence there is no model approximation error. The overall sample complexity of our decentralized AC is O(e 2 In ")) matching the state-of-thed of-the-art complexity result for centralized AC (60). Moreover, with proper choices of the batch sizes N, No = O the overall communication complexity is significantly reduced to O(c In c!).
be achieved when
The proof of Theorem 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, 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 substantially improve the communication complexity from O(e In e to OOn (1) while help achieve the state-of-thh-arr sample complexity. Eventually, this together with the mini- -atch 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 fast convergence of the decentralized TD learning. However, although the standard T; decentralized mini-batch TD updates can yield small convergence error for the global critic model (i.e., the average of all local critic models), still suffers from relatively large consensus error. To resolve this issue, we introduce an additional T" global consensus steps in Algorithm
reduce the consensus error. It is proved that a small number OInn of such steps suffices to yield desired TD error.
We inject random noises into the local raw rewards R!!") 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.
5 DECENTRALIZED NATURAL AC
Natural actor-critic (NAC) is a popular variant of the AC algorithm. It utilizes a Fisher information matrix to perform 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-effiiiennn.
7

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Decentralized Natural Actor-Critic
Initialize: Actor-critic parameters wo, 9-1. natural policy gradient h-1- for actor iterations = 0, .......,""
do Critic update 0₂: by Algorithm 2. for agents m = 1..., .M in parallel do
for iterations k 0. 1....,
do Collect N₂ Markovian samples following eq. (2).
Send R and "i,
[(m) and perform I" and T2 local average steps, respectively,
Estimate local gradient V Vatmn fun (he,x) following eqs. (8) and (4).
Perform SGI) update in eq. (9).
end
Actor update on wit w(th = wi (m) ahi (m))
end end
Output: Wi with 7 uniform f1.2.....
major challenge of developing fully decentralized NAC algorithm 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., W/+1 = wr - (f)) JV(()) where F(w)) := Eer (-)ss. (ar information matrix. However, in the multi-agent case, it is challenging to perform the natural policy gradient update in decentralized manner. This is because the Fisher information matrix F(wr) is based on the concatenated multi-agent score vector th (arlse) = [et (a. |s); v/ (M) and the inverse matrix vector product (V policy parameter dimensions. Next, we develop fully decentralized scheme to implement the natural policy gradient update in the multi-agent setting.
(at ( (arls))) is the Fisher
(az (18) [s:]]
not separable with regard each agent's
First, note that the natural policy gradient update h(w)) == solution of a quadratic program, i.e.,
is equivalent to the
h(w+)) = arg min fw, (h) = In IT VJ(())
Therefore, 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 44.0 = h4-1 (obtained in the previous iteration). in the k-th SGD step, we sample mini-batch B., of Nu Markovian samples to estimate Vau, (h) N₂ EieB,, (b) The VJ(w, BL,.),
1
where (we; B,,s) is estimated in the same decentralized way eq. (4) using the mini-batch of samples B. In particular, each agent m needs to compute the corresponding local gradi- (s:) (a ( - aatm Br,)), in which df (a{")(((")) (m(m))/s)))) and Vuins (ure; Br,,)) can be computed/estimatee by the agent m. Then, it suffices to obtain estimate (m)
Nú EieB,, (a(""))
(m7)
of the scalar u/x (a: he which can be rewritten as Em=
|s.) ( h.mm) This summa- tion can be easily estimated by the decentralized agents through local averaging. Specifically, each (a. (m))
agent m locally computes 21,0
((m
(m()))
h/m)) and performs T2 steps of local averaging, (s.) TT.m
[s.)
(m) i.c., 2i,++1 Em'EN. W Wm,m' Zi,e
8= 0, ......., T. After that, the quantity M Mz,n can be proven to converge to the desired summation >M (m) (a!
(m')
(m)) (s;) i (m) exponentially fast. Finally,
2,k
the local gradient for agent m is approximated
wim San, (hr,,)
M
((("))
(a (m) (m) Vi Mure; Br,s)- [8))
(8)
N
1EB..x
Then, the agent m performs the following SGD updates to obtain h. (mm) : h
h h
(m) (m)
aim (hr,)), k O,..,
(9)
"Specifically, the mini-batch B., contains sample indices (t.V+ Et-1 Nw....,, Ei No -w-
8

---

Under review as a conference paper at ICLR 2022
We emphasize that the above mini-batch SGD updates 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.
6 FINITE-TIME CONVERGENCE ANALYSIS OF DECENTRALIZED NAC
To analyze the decentralized NAC, we introduce the following additional standard assumptions. Assumption 6. There exists a constant XØ > 0 such that Amin (F(w)) 2 Xp > 0, Yuu E Q. Assumption 7. There exists C, > such that for w- = arg max ((w and any w E Ω
Mw Mu (s)T (als)
V (s) ) S C..
E (arunnar
Assumption 6 ensures that the Fisher information matrix F(w) is uniformly positive definite, and is also considered in (65; 29; 62). Assumption 7 regularizes the discrepancy between the stationary state-action distributions Vw (s)T (als) and Va (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 Sapprox
(actor
a)) All universal constants are listed in Ap- sup,, ming a) (((((((l)))) pendix F.
Theorem 2. Let Assumptions 1-7 hold and adopt the hyperparameteers of the decentralized TD in C²
Algorithm 2 following Lemma D.4. Choose hyperparameters a S min (1, AL,C3 :LJ ,
X².
B S 1,
M T" M 2lnow
1) S -0
Tg 2
Im(3D,C3)
K Z In 1/1 N 2 RA (1 M](1 (1 /2//2 1772
13010-
lnw
and No (1 T/}F /2)/222)k k/2, Then, the oulput of Algorithm 3 satisfies
- [
C17 + e1s Ta
Tdp))
(K-1//4
+ +C1goW + C200 B21Bo Th +
C23 /Ne
2
+ C22
(1
AB
3)))
3)
To/2
+ + C16 Sappaxx + C24 Sappexx + C"
ceritic
Cactor Supprex
8
Moreover, to achieve J(w)) [2 [[[(w S c for any 2 20 C16
Supporx 2024
ceritic
2C* /Cappise we can choose T = O,- N.N. = O(c Te, T T T2, K OIn 1)). Con-
sequently, the overall sample complexity is T(T.Ne N) = O(E In ) and the communication complexities for synchronizing linear model parameters and rewards are T O(E Ine and TT = -n lnc-)), 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 ONN
critic Sapprox
V Sapporx) ) which can made arbitrarily close to the actor and critic approximation error by choosing sufficiently large batch size No. In particular, exact global optimum can be achieved when there is no model approximation error. We note that the overall sample complexity our decentralized NAC is O(c-3 In ", matching the ofate-oftthe-ar complexity result for centralized NAC (60). Moreover, with the mini-batch updates, the overall communication complexity is significantly reduced lne
Similar to that of Theorem 1, our analysis of Theorem 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 eq. (7). Here, we use special geometrically increasing batch size scheduling scheme, i.e., N& (1 (-AA//) -2//2 to achieve the best possible convergence rate under the total sample budget that Σ N₂ = N and obtain the desired overall sample complexity result. Such analysis of SGD with Markovian sampling
under adaptive batch size scheduling has not been studied in the literature and can be of independent interests.

---

Under review as a conference paper at ICLR 2022
1c-1
6.00
6.00
5.75
#p-. 100
5.75
Ap. 1. 150
5.8
5.8
3 5.50
Mp.1.4 7000
4p-0
5.50
Ag. 2000
Mg. 7w5500
Ap 3:0
Hp M-0
5.6
Ag NN-500
My /ew100
5.25
5.25
5.4
Ag. 4g.1/0t20000
5.4
4gg33 Mg.33/002200
5.2
5.00
5.00
5.0
5.0
4.75
4.75
0
0.0
0.5
1.0
0.0
0.5
Communication complexity
lef
Sample complexity
Communication complexity
Sample
1e6
complexity
Figure 1: Comparison of accumulated discounted reward (wx) among decentralized AC-type algorithms in a ring network with sparse connections.
7 EXPERIMENTS
We simulate 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, (70)) that uses a linear model to parameterize the agents' averaged reward (we name it DAC-RPI for decentralized AC with reward parameterization), and our proposed modified version of DAC-RP1 to incorporate minibatch, which we refer to as DAC-RPI00 with batch size N = 100. For our Algorithm choose 7 500, T, 50, TV 10, N. 10, T" T. 5, B 0.5, {o. Jmm=mm=1- 0.1, and consider batch size choices N = 100, 500, 2000. Algorithm 3 uses the same hyperparameters as those of Algorithm except that 2000 in Algorithm 3. For DAC-RPI, we set learning rates Bg 2(t + 1)-0.9 3r 5(t 1)-0.8 and batch size N = as mentioned in (70). The modified 100.
Algorithms 1 and 3, existing decentralized AC algorithm (Algorithm 2 of
DAC-RP100 adopts the same learning rates as Algorithm with
Figure 1 plots the accumulated reward J(w) 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 high accumulated reward are significantly reduced under larger batch size N. This matches theoretical understanding in Theorem I that a large helps reduce the communication frequency and policy gradient variance. In comparison, DAC-RP1 (with N 1) has almost no improvement the accumulated reward. Moreover, although the modified DAC-RPI00 (with N = 100) outperforms DAC-RP1, its performance is much worse than our Algorithm with N 100. This performance gap 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 mean relative error in the range of 10-5 ~ 10 ((i) 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), can make similar observations and conclusions.
8 CONCLUSION
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(c-2Inc" In and O(e -3 In e'), respectively, and they both achieve a small communication complexity O(c In e '). Numerical experiments demonstrate that our algorithms achieve better sample and communication complexity than the existing decentralized AC algorithm that adopts reward parameterization.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
[ A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. ArXiv:1908.0m 00261, 2019.
[2] C. Alfano and P. Rebeschini. Dimension-free rates for natural policy gradient in multi agent reinforcement learning. ArXiv:2109.1169 2021.
[3] Q. Bai, M. Agarwal, and V. Aggarwal. Joint optimization of multi-objective reinforcement learning with policy gradient based algorithm. ArXiv:2105.14125 2021.
[4] Bhandari, D. Russo, and R. Singal. finite time analysis of temporal difference learning with linear function approximation. In Proc. Conference on Learning Theory (COLT), volume 75, pages 1691-1692, 2018.
[5] S. Bhatnagar. An actor-critic algorithm with function approximation for discounted cost constrained markov decision processes. Systems & Control Letters, 59(12);60-766, 2010.
[6] S. Bhatnagar, M. Ghavamzadeh, M. Lee, and R. S. Sutton. Incremental natural actor-critic algorithms. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 20, pages 105-112, 2007.
[7] S. Bhatnagar, R. Sutton, M. Ghavamzadeh, and M. Lee. Natural actor-critic algorithms. Automatica, 45( (5(11))2471-2482 2009.
[8] G. Bono, J. S. Dibangoye, L. Matignon, F. Pereyron, and O. Simonin. Cooperative multi-agent policy gradient. In Proc. Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 476, 2018
[9] L. Cassano, K. Yuan, and A. H. Sayed. Multi-agent fully decentralized value function learning with linear convergence rates. IEEE Transactions on Automatic Control, 2020.
[10] B. Chalaki and A. Malikopoulos. hysteretic q-learning coordination framework for emerging mobility systems in smart cities. ArXiv:201 N.KV::20/1.031331 1.03137. 2020.
[11] B. Chen, M. Xu, Z. Liu, L. Li, and D. Zhao. Delay-aware multi-agent reinforcement learning. ArXiv:2005.05441, 2020.
[12] Z. Chen, Y. Zhou, and R. Chen. Multi-agent off-policy td learning: Finite-time analysis with near-optimal sample complexity and communication complexity. 1131::2103.13147, 2021.
[13] C. Daskalakis, D. J. Foster, and N. Golowich. Independent policy gradient methods for competitive reinforcement learning. ArXiv:2101.04233, 2021.
[14] T. Doan, S. Maguluri, and J. Romberg. Finite-time analysis of distributed TD(O) with linear func- tion approximation multi-agent reinforcement learning. In Proc. International Conference on Machine Learning (ICML), volume 97, pages 1626-1635, 09-15 Jun 2019.
[15] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson. Counterfactual multi-agent policy gradients. In Proc. Association for the Advancement of Artificial Intelligence (AAAI), volume 32, 2018.
[16] A. Ghosh and V. Aggarwal. Model free reinforcement learning algorithm for stationary mean field equilibrium for multiple types of agents. ArXiv:2012.15377, 2020.
[17] D. Hennes, D. Morrill, S. Omidshafiei, R. Munos, Perolat, M. Lanctot, A. Gruslys, J.-B. Lespiau, P. Parmas, E. Duéfez-Guzzmá, et al. Neural replicator dynamics: Multiagent learning via hedging policy gradients. In Proc. International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 492-501, 2020.
[18] P. Heredia, H. Ghadialy, and S. Mou. Fimite-sample analysis of distributed q-learning for multi-agent networks. In 2020 American Control Conference (ACC), pages 3511-3516, 2020.
[19] P. C. Heredia and S. Mou. Distributed multi-agent reinforcement learning by actor-critic method. IFAC-PupersOnLLine, 52((0):363-33) 2019.
11

---

Under review as a conference paper at ICLR 2022
[20] S. M. Kakade. A natural policy gradient. In Proc. Advances in Neural Information Processing Systems (NeurlPS), volume 14, 2001.
[21] S. Kar, J. M. F. Moura, and H. V. Poor. Qd-learning: A collaborative distributed strategy for multi-agent reinforcement learning through consensus innovations. IEEE Transactions Signal Processing, 61(7):1848-182, 2013.
[22] V. Konda. Actor-critic algorithms (ph.d. thesis). Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2002.
[23] V. R. Konda and J. N. Tsitsiklis. Actor-critic algorithms. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 1008-1014, 2000.
[24] V. Krishnamurthy, M. Maskery, and G. Yin. Decentralized adaptive filtering algorithms for sensor activation in an unattended ground sensor network. IEEE Transactions on Signal 2008.
Processing. 36(12):6086-00
[25] H. Kumar, A. Koppel, and A. Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. ArXiv:1910.08411 2019.
[26] Y. Lin, Y. Luo, K. Zhang, Yang. Z. Wang. T. Basar, R. Sandhu, and Liu. An asyn- chronous multi-agent actor-critic algorithm for distributed reinforcement learning. In NeurlPS Optimization Foundations for Reinforcement Learning Workshop, 2019.
[27] Y. Lin, K. Zhang, Z. Yang. 7. Wang. T. Başar, R. Sandhu, and Liu. communication-effiieent multi-agent actor-critic algorithm for distributed reinforcement learning. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5562-5567, 2019.
[28] R. Liu and A. Olshevsky. Distributed td (0) with almost no communication, ArXiv:2104.07855, 2021.
[29] Y. Liu, K. Zhang, T. Basar, and W. Yin. An improved analysis of (variance-reduced) policy gra- dient and natural policy gradient methods. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 7624-7636, 2020.
[30] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, and I. Mordatch. Multi-agent actor-critic for mixed cooperative-compettive environments. ArXiv:/706.02275. 2017.
[31] Y. Luo, Z. Yang, Z. Wang, and M. Kolar. Natural actor-critic converges globally for hierarchical linear quadratic regulator. ArXiv:1912.06875, 2019.
[32] X. Lyu, Y. Xiao, B. Daley, and C. Amato. Contrasting centralized and decentralized crities in multi-agent reinforcement learning. ArXivv21022.4402, 2021.
[33] X. Ma, Y. Yang, C. Li, Y. Lu, Q. Zhao, and Y. Jun. Modeling the interaction between agents in cooperative multi agent reinforcement learning. 1xXi::2002.0042.. 2021.
[34] S. V. Macua, Chen, Zazo, and A. H. Sayed. Distributed policy evaluation under multiple behavior strategies. IEEE Transactions on Automatic Control, 6065):1200-1274, 2014.
[35] D. J. Ornia and M. Mazo Jr. Event-based communication in multi-agent distributed q-learning. 10.0v:210.001417 2021.
[36] Perolat, B. Piot, and O. Pietquin. Actor-critic fictitious play in simultaneous move multistage games. In Proc. International Conference Artificial Intelligence and Statistics, pages 919- 928, 2018.
[37] Peters and S. Schaal. Natural actor-critic. Neurocomputing, 7107-9):1100-1199 2008
[38] S. Qiu, Z. Yang, J. Ye, and Z. Wang. On the finite-time convergence of actor-critic algorithm. In NeurIPS Optimization Foundations for Reinforcement Learning Workshop, 2019.
[39] W. Qiu, X. Wang. R. Yu, R. Wang, X. He. B. An, S. Obraztsova, and Z. Rabinovich. Rmix: Learning sensitive policies forcooperative reinforcement learning agents. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2021.
12

---

Under review as a conference paper at ICLR 2022
[40] C. Qu, S. Mannor, H. Xu, Y. Qi, L. Song, and J. Xiong. Value propagation for decentralized networked deep multi-agent reinforcement learning. In Proc. Advances in Neural Information Processing Systems (NeurIPS)), pages 1184-1193, 2019.
[41] R. Saha, S. Rini, M. Rao, and A. Goldsmith. Decentralized optimization over noisy, rate- constrained networks: How to agree by talking about how we disagree. ArXiv:2010.11222 2020.
[42] M. Shaocong, Z. Yi, and Z. Shaofeng. Variance- off off-iy tde learning: Non-asymptotic convergence analysis. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[43] N. Singh, D. Data, J. George, and S. Diggavi. Squarm-sgd: Communicatioon-fficinnn momentum sgd for decentralized optimization. ArXiv:2005.00411, 2020.
[44] S. Srinivasan, M. Lanetot, V. Zambaldi, J. Pérolat, K. Tuyls, R. Munos, and M. Bowling. Actor- critic policy optimization in partially observable multiagent environments. ArXiv: 180.00000 2018.
[45] M. S. Stanković and S. S. Stanković. Multi-agent temporal-diffent differenee learning with linear function approximation: Weak convergence under time-varying network topologies. In Proc. American Control Conference (ACC), pages 167-172, 2016.
[46] Sun, Wang, G. B. Giannakis, Q. Yang, and Z. Yang. Finite-sample analysis of decentral- ized lemporal-differene learning with linear function approximation. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 4485-4495, 2020.
[47] W. Suttle, Z. Yang, K. Zhang, Z. Wang, T. Basar, and J. Liu. A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning. ArXiv:1903.0637 2019. 2019.
[48] R. S. Sutton and G. Barto. Reinforcement learning: An introduction (Second Edition). 2018.
[49] R. S. Sutton, McAllester, S. Singh, and Mansour. Policy gradient methods for rein- forcement learning with function approximation. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 12, 2000.
[50] R. S. Sutton, D. A. McAllester, S. P. Singh, Y. Mansour, et al. Policy gradient methods for reinforeement learning with function approximation. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 99, pages 1057-1063, 1999.
[51] F. Venturini, F. Mason, F. Pase, F. Chiariotti, A. Testolin, A. Zanella, and M. Zorzi. Distributed reinforcement learning for flexible and efficient uav swarm control. ArXiv:2103.04666 2021.
[52] H.-T. Wai, Yang, Z. Wang, and M. Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 9672-9683, 2018
[53] G. Wang, S. Lu, G. Giannakis, G. Tesauro, and J. Sun. Decentralized tracking with linear function approximation and its finite-time analysis. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
[54] L. Wang, Q. Cai, Z. Yang, and Z. Wang. Neural policy gradient methods: Global optimality and rates of convergence. ArXiv: DrxXiv:990..0 /909.01 150, 2019.
[55] W. Wang. J. Hao, Y. Wang, and M. Taylor. Achieving cooperation through deep multiagent reinforcement learning in sequential prisoner's 's dilemmas. In Proc. of International Conference on Distributed Artificial Intelligence (DAI), pages 2019.
[56] Y. F. Wu, W. ZHANG, P. Xu, and Q. Gu. A finite-time analysis of two time-scale actor-critic methods. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 17617-17628. 2020.
[57] B. Xiao, B. Ramasubramanian, and R. Poovendran. Shaping advice in deep multi-agent reinforcement learning. 1r3 2021.
13

---

Under review as a conference paper at ICLR 2022
[58] T. Xu and Y. Liang. Sample complexity bounds for two timescale value-based reinforcement learning algorithms. ArXiv:2011.05053, 2020.
[59] T. Xu, Y. Liang, and G. Lan. A primal approach to constrained policy optimization: Global optimality and finite-time analysis. ArXiv:2011.0586) 2020.
[60] Xu, Z. Wang, and Y. Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
[61] Xu, Z. Wang, and Y. Liang. Non-asymptotic convergence analysis two time-scale (natural) actor-critic algorithms. 2rX55:2005.03557, 2020.
[62] T. Xu, Z. Yang. Z. Wang, and Y. Liang. Doubly robust off-policy actor-critic: Convergence and optimality. ArXiv:2102.11866, 2021.
[63] T. Xu, S. Zou, and Y. Liang. Two time-scalll scale off- off-policy td learning: Non-asymptotic analysis over markovian samples. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 10634-10644, 2019.
[64] Z. Yan, N. Jouandeau, and A. A. Cherif. A survey and analysis of multi-robot coordination. International Journal of Advanced Robotic Systems, 10(12):399, 2013.
[65] L. Yang, Q Zheng, and G. Pan. Sample complexity of policy gradient finding second-order stationary points. ArXiv:2012.01491, 2020.
[66] E. Yanmaz, M. Quaritsch, S. Yahyanejad, B. Rinner, H. Hellwagner, and C. Bettstetter. Com- munication and coordination for drone networks. In Proc. International Conference on Ad Hoc Networks, pages 79-91, 2017.
[67] M. Yuan, Q. Cao, M.-o. Pun, and Y. Chen. Towards user scheduling for 6g: A fairness-orietted scheduler using multi-agent reinforcement learning. ArXiv:20/2.1508/ 2020.
[68] H. Zhang, H. Jiang, Y. Luo, and G. Xiao. Data-driven optimal consensus control for discrete- time multi-agent systems with unknown dynamics using reinforcement learning method. IEEE Transactions on Industrial Electronics, 64(5):4091-4100 2016.
[69] K. Zhang, Z. Yang, and Basar. Networked multi-agent reinforcement learning in continuous spaces. In Proc. 2018 IEEE Conference Decision and Control (CDC), pages 2771-2776. IEEE, 2018
[70] K. Zhang, Z. Yang. H. Liu, Zhang, and T. Basar. Fully decentralized multi-agent reinforcement learning with networked agents. In Proc. International Conference on Machine Learning (ICML), pages 5872-5881, 2018.
[71] W. Zhang, H. Liu, F. Wang, T. Xu, H. Xin, D. Dou, and H. Xiong. Intelligent electric vehicle charging recommendation based on multi-agent reinforcement learning. ArXiv:2102.07359, 2021.
[72] Y. Zhang and M. M. Zavlanos. Distributed off-policy actor-critic reinforcement learning with policy consensus. In Proc, Conference on Decision and Control (CDC), pages 4674-4679, 2019.
[73] Y. Zhao, Y. Tian, J. D. Lee, and S. S. Du. Provably efficient policy gradient methods for two-player zero-sum markov games, ArXiv:2102, 08903, 2021.
14

---

Under review as a conference paper at ICLR 2022
Appendix
Table of Contents
A Notations
15
B Proof of Theorem 1
16
C Proof of Theorem 2
17
D Supporting Lemmas
20
E Experiment Setup and Additional Results
37
E.1 Experiment Setup
37
E.2 Gradient Norm Convergence Results in Ring Network
38
E.3 Additional Experiments in Fully Connected Network
39
E,4 Two-agent Cliff Navigation
40
F Constant scalars
41
A
NOTATIONS
Norms:
For any vector we denote ||>||| as its l2 norm. For any matrix X, we denote || |X as spectral norm and Frobenius norm, respectively.
1 Difference matrix: A = M 111 where 1 denotes a column vector that consists of 1s.
Moments of random vectors: For a random vector X, define its variance and covariance matrix as Var(X) = E | and Cov(X) == E[[ EX] - Ex]])). respectively, It is well known that X|| Var X) || and that Var(X) = tr(Cov(X)).
Score function: At any time t, The joint score function (aels)) = Vu In To st) can be de- (s)) as (arls)) =
composed into individual score functions wh ((m) (m²) [st) == Vaim In (m) (a, (m)) [16]] (a. (1) (st). (a)))ss)...............))) u6 (a), (M)))ss))
(a/
Reward functions: At any time f, we denote R!m) == ((m) as s141) and R = R(s 01, S241). where R(s,
a, 5') 1 EM (((m)(ss a, s').
Policy gradient: The policy gradient theorem (50) shows that
V((w) Er, (s, a)
(10)
where (s, = Qs, (s) denotes the advantage function. the decentralized case,
we have the approximations (st) ((+:) T (st,),) ss R, 70($(+1) To where s'41 P(. a). Therefore, we can stochastically approximate the partial policy gradient eq. (1), i.e. for m I,..,,M. M,
V Wilm J (ur) Rs 76(5(41) T(()) o(s,) mm
1/2 (("))ss))))
We also define the following mini-batch stochastic (partial) policy gradient.
Vuins (wi) = -/2/ Ei=E
((+1)N1 RR (0(5(411 To! o(si) ml vs (m)
(J(w)) = Vanny J(e)]
Filtrations:
We define the following filtrations for Algorithms & 3.
15

---

Under review as a conference paper at ICLR 2022
F a ( JeE U (8s, ag 6441 (e("")JeMM Imme)i u {oiN)).
F a (F (
Fi, = a
8441, 641 {e; (m) meMMheuttiss
B PROOF OF THEOREM
Theorem 1. Let Assumptions 1-5 hold and adopt the hyperparameters of the decentralized TD in Algorithm 2 following Lemma D.4, Choose a I 4L.' T 2 In Then, the output of the decentralized AC Algorithm has the following convergence rate.
2lnow
E [W)
4Rmax
2 21: ) +4(cLoW +csBoow
AB A 8
4C7
40s
+64C ab Sappaxx
Ta
N
No
Moreover, to achieve [[]]]( e for any 128C x ceritic we can choose T, N,N,No O and To, T" T = (mn ") Consequently, the overall sample complexity ((ToNo+N) = O(e-21nn O(e- ))) and the communication complexities for synchronizing linear model parameters and rewards are T(Te + T = O(c ln) and TT = =Oc-- In c 1) respectively.
Proof. Concatenating all the agents' actor updates in Algorithm we obtain the joint actor update W++1= = Wi + (Wr). Then, the item 7 of Lemma D.5 implies that
Ls
[wi+1) 2 (wx) + Vi(wr) (WI-1 - w))
| - will"
= J(w)) aVJ((w) (.][ (V](): Lsa²
- J(w)) + [ + ( (FJ(())((((()) - vJ(Wi))
Lsa // [[))(w)) [w:))l Laaal|
2 ((wr) + (
0 - T. [J](w 1 1 + Laaa ((nr))
(10) 2 J(w)) + [ a (w:) - [uwu))
where (i) and (ii) use the inequalities ||=1| < 2| - y/1 + 2| and x x 2 11 ] 1
2
1. for any x, E Rd. respectively, and (iii) uses the condition that S Ti, Then, summing up the inequality above over = 0, I,...., T - yields that
T-1
T-1 [VJ(W) - Σ - V
J(WT) 2 I(wo) +
1=U
t=
Rearranging the equation above and taking expectation both sides yields that
E
E [
T
1=0
4 T-1
< Ta
E[J(wT) [ww))
Σ
E |
[(w)) -VJ(w))
T
(6)
4.mmx
2T" + 4c4ow + 4c,,8² Now
2T: + 4co (1
(1-
\B
An To
To
4
4c7
4cs
+
+ -4C2 ceritic Supproxs
Supprope
(11)
N
No
where (i) uses the item of Lemma D.5 and eq. (39) of Lemma D.6 (The condition of Lemma D.6 M 2In(a 15 holds). This proves the enror bound of Theorem 1.
that T"
16

---

Under review as a conference paper at ICLR 2022
Finally, for any 2 128C Sapprox- it can be easily verified that the following hyperparameter choices make the error bound in (11) smaller than e and also satisfy the conditions of this Theorem and those
2 + 23) 1920 (1+((1))))))))
in Lemma D.4 that 3 < min 8C Au 2C
No
min
[1
011)
4L,/
AB
- (L))
B = min
SCB B
AB 2CB
48 max
T
= O(c
ac
T'
max [In(48c46 11)48846-)),111 M]] ((I((()))
2 2ln(o-1)
In In(48c5,82 32 =O(In(E-))
T
2 2ln(o-1)
In (48cge
Te
= =I(((e))))
21n \B 1/334)--11
4807
N
O(6
48c7
2
1920 + (m- 1)pl
N
max
[_c]
+ 2/3)
O
(12)
AB
(1 1--pl p)>B
C PROOF OF THEOREM? 2
Theorem 2. Let Assumptions 1-7 hold and adopt the hyperparameters of the decentralized TD in
Algorithm following Lemma D.4. Choose hyperparameters a min (1, 4T,
x²
<
22
T 2 M 17 S
1 T, 2 In(3DaC3)
K 2
In3
N 2
2304C (K- 1-p)
2laow
20
lnow
In
9112) T,
n (1 (1-p)( (11711122)) 1173
and N₂ (1 n/> 22) 12)
k/2 Then, the output of Algorithm satisfies
[[
-
C17 + c1s (1-
(--AP)
7AP)
(K 1/11/4
+ ciggow + c200w + c21Bo T2 +
C23
To
2
VNe
+ 022 (1 dB 3)
T6/2
C16 C1o + C21 Sappoxx + 0² + Cip
ceritic
Cappor
8
Moreover, to achieve J(w)) - [w]( S for any - 20 v C16 Sappos + 2024 2022
crrtic
20* Sappaoe we can choose T = O,--), N, = O Te, Ty T Tg, K = OIn -)). Con-
sequently, the overall sample complexity is T(T.Ne + N) = O -1), and the communication complexities for synchronizing linear model parameters and rewards are +T))+T.) = and TT = =OE Ine ll),),, respectively.
Proof. Concatenating all the agents' actor updates in Algorithm 3, we obtain the joint actor update Wi+1 = Wi + ah,. Then, the item of Lemma D.5 implies that
LJ |W++ - w. 1
[(r+1)) 2 J(wr) + V.(w)) (T (W1+1 - wi)
2
= -(wr)) + (wi) TTe, he Lja²
||1ell?
2
( - I(we) + (()) F(w:)) -V (wir) + (ww)) [he k(wr))
-.aa2llh 1u(we)]l2 T. (
17

---

Under review as a conference paper at ICLR 2022
(16)
L
+ L -(0c
(a
2 (wr) +
[J[[w))]1
) | - h(wrr))
2C
X
(66) 2 I(wr) + 4C
V 21 - aC* 1+ - m(wwr))
where (i) uses the notation that h(w)) F(wr) ( and the inequality that || 2 2 3/1 + 2||y|| 2 for any 2; V R (ii) uses the item 3 of Lemma D.7 and the inequality that æ y 2
c 20 | 2 || for any xi y Rd, and (iii) uses the condition that min
X C
42, C2 2I
Taking expectation on both sides of the above inequality, summing over 0, 1, T 1 and rearranging, we obtain that
40 - " B[J[(WT) [(w)]]
40
Σ
[W)J(
E
E El h4
h(wr)]l
T
Ta
T
40 20 Rmax
(1- 7AF
(K-1)/2
+ +40
C10
c11021 2T' + C1202 27"
Ta
2
C138 2T
+ c14
An
B
+
C15
+
C16 Saprrxx
criti
(13)
4
N
where (i) uses the item 4 of Lemma D.5 and the item 8 of Lemma D.7.
By Assumption 2, In (s. a) is an Ly-smi Ly-shooth function of w. Denote := arg min [w) and denote En-- as the unconditional expectation over Man, Tw- (-|s). We obtain that
E. [In ( In Tz (a]s)]
2 R. [V In (als)) (wi+1 - we)
Le El|wet1 - well
2
= =ol. [N((als)T hee] L
E [[(11bl1?]
2
a. (als) (hi h(w)))] aiE [1a (a)ss Mwr) Au, (8, + (s,
L 2 ElleE h(w))/ll ||
10)
_ a R2 [B[]|b 11114-- ((w)))1 - aC./
//cappo
Factor
Sapprox
+aB[J(w²) - [w.)]] - 2 "E[[ h(ww))l T [[
where (i) uses the inequality that ||= 2||x - v112 + 2||y/12 for any x, y E Id and the notation that h(rx) _ -w
(ii) uses Cauchy-Schwarz inequality, the items & 6 of Lemma
E [[]]] for any random vector X and the equality that E.- [A,, [s. a)) = [ - J [w))] (See its proof Lemma 3.2 of (1).). Averaging the inequality above over t = 0,1....,,7 . - and rearranging it yields that
D.7, the inequality that X|| $
T-1
- - [[w)]]]] = - Σ
[[((w))
1=
< 1
C
T-1
Ta
Eu-
[In - In [o(ss)] + +C.
Suppeux
+
T
E
hh
h(ww:)l1
Lyo
L
E h4 - h
+
E [[
T
TX2 1=
(6)
Expee- KLL (Tu- (KL (-10)]]00((11) KL( (-1)(((()]777((111)) + 0"
actorr
Ta
Sapprox
(1- ndr (K-1)/2
+ Ce [10
+ 21 2T: + 0120 2T' + c13,320 2T:
2
18

---

Under review as a conference paper at ICLR 2022
+ +c1
11 (1a(1-
AB
Tc
C15
N₂
C16
Sapprox
ceitic
1/2
7Ap
(K
11/2
L
c10
c1102T: 27: + c1202 2T
+ +1382022 2T.
2
+ +c44
1-
AB
3
To
C15
+
scriiic C16 C1o
No
Loor
402
1)
Rmax
40, ci0 (1
mdF
(K (K-1)/2
c1102 2T:
+ c1120 2T
+ +1138000 25
2/.
Ta
2
+ c14
1
\B3)
AB
3)
To
C15
c16 sapiipi
}
No
(1)
1
Ta
Bsnugt
(KL( (+)))][0(-111) +Ct
Sapprox
Co Se[Veo)
1
(K-1)/4
Vanoo + Vazo" Ve133oT.
2
1
AB
To/2
+
V
C15
No
+
Velo
Ceritic Spprexx
Tap
11
+
40
C10
(K-1)/4
+1100 + +122"" + C13300
X2
2
+ +c11
AB B
Te/2
+
C15
+
C16
cetticc
42
4
VNe
Tadp
(118) 617
+ C18 (1
M\p
11/1
+ C190 + c200 + To + 622
AB
B)
Tel2
Ta
2
4
C23
+ Cu/
C16
+ C24 Sapprox
critic
+ C
Cactor Sapprox
(14)
VNe
where (i) uses the definition of KL divergence that KL( (-|s)[(=m(1ss))
Baww (-1a) In a (als) - In au (a|s) ss] and eqs. (13) & (54), (ii) uses the condition that a S and the inequality that v // vi < Ei VTz for any N+ and , In 2 0. (iii) uses the nota- tions that C17:=Bawaa [ (115)][0((ss)]] 45, Rmax
.18 C + cio (1 40
XB
x
C19 = Covon + cuL [+
40,)
C20 == Cove12 + ci2 (1+
40 X
621 = Cev
X
clabo 1 +
10d
Xx
C22 Cover4 + ciaby [1
+
10t
Xp
C23
C + cioles [ + Xp
10d
404 Xx
624 166
1 +
This proves the error bound of Theorem 2.
can be verified that the following hyperparameter choices make the error bound in (14) smaller than and satisfy all An 4 1-)), No Z
Finally, for any c 2 20 Cie Coritic + 2024 Sapprox
ceritic + 2C Factor
Sapprox
the conditions of this Theorem and those in Lemma D.4 that 3 < min (8C) An 20
2 A + 2/3
1920 ( (1-p)AB
X/. C
a min (1, 4L $
2L, 0(1)
\ø 4 1 1 0
B 0=min 3-min (1,
= 0(1)
802 XB 2CB
1 2C (1)
14c17
T ae
= 1
19

---

Under review as a conference paper at ICLR 2022
1n3
41
In[(1 ///F22) 2 In [1 7/p 22pp22) 22/ + +1 - [[n[c=))]
max
Ll(33
In In(14ciee 111 = [[[n(c)))
T3 max
In(o-1)
In(o=1)
In
In In(14020c
T max
= [[n((="))
2l 1)
In(o-11
1n(14c21 -
TV
-0 ([([(c()))
In(o-1)
2 21n(14c226 1)
Te
0(In(6-1)
[n((1 AB//4
23040 1) (16 + 1 p)
(/ - p)(1 - (4 -E -2)
No max ( -- + 233
1920 [1+ + (K5 - 1)pl
196629 2 =0(E
(15)
(1 11-p) p)AB
D SUPPORTING LEMMAS
First, we extend the Lemma F.3 of (12) to the Lemma D.1 below. The item of Lemma D. generalizes the case = 1 to any n E N+, the items 2 & 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 A ==-- M 111 have the following properties:
1. AW" -"A W M1
111 for any E N+.
2. The spectral norm of W satisfies [[W]| =1.
For any x E RM and n N+, || Az|l S ow | (ow is the second largest singular value of W.. Hence, for any E MXM | AH S ofy ||
4. - Mo 11 S oW
W / 11
ow VM for any N+.
Proof. The proof of items 2 & can be found in (12). We prove the item I and item 4. We prove item by induction. The equalities, as shown in (12).
of the item can be proved by the following two
AW (I
1
11 W W
11 W = W - 11
M
M
M
WA = W
1 11 W
WI1 = W 11T
M
M
M
Suppose the case of n k holds for certain & E N then the following two equalities proves the case n + 1 and thus proves the item I.
AW (AW*)W = (w* 11 W = Wh+1
M 11
M
W W(W*A) = W (wr w(wk=
1
11 = Wh+1
11
M
M
The item can be proved by the following two inequalities.
W
1
W'
= sup
|
Ax
(4)
sup
|||||||>||||
(1r)
o
(16)
M
s:i #1
#
20

---

Under review as a conference paper at ICLR 2022
(161
W
11 M
W A I owllA|F
(iv)
oiv v M(1 Mr + ((M - 1)
1 M M S o VM, (17)
where (i) uses the item 1, (ii) and (iii) use the item 3 (H I in (ii)), and (iv) uses the fact that has M diagnoal entries 1 M and M(M - 1) off-diagnoal entries 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 {st, az)s00 are generated following the policy tu and transition kernel P' (can be P or Ps), and 6/41 P(-(si,,s) as). Then, for any deterministic mapping
X : S x A S x S Roxq (p.q q N+ are arbitrary.) such that [X((s, a, 3)]l S C2 and for any 8, s' E S, A. we have
n+n'-1
Σ
X(s ai S,11, (441) x1
X (,0
90 11 Vn,n' E N (18)
n(1 - p)
where X ((s,,, Oz, 1 [6 with 8, Mou (or Uw) when P' =P (or Pe).
Proof. Denote Y as, = () [X s', 3) a, s'] which satisfies ( a, s')ll s Oz and Eg (s; aj, s1+1)] = X. Hence, Lemma F22 of (12) can be applied to Y(s, a, s') and obtain the following inequality
E
ntn' -1
Σ
(11,)),0111)> -x
8n' S
80 + -p)
(19)
n11
Therefore, we obtain that
B
Σ
a 8441) -X]
{st, ats S141) 1=tn'
n
nnn
R
X(si, ag 8141,
X
(8i ai 8:41 1ntn' 1otn
ntwl-1
Var
X(si, 0s 8i+1, 8141, s/41 {ss, as 8141 341) 1atn'
t=n'
as,,,,
Var
85+ D -1]
(10
C2
Y(s,, 8:41) - -X +
(20)
n
where (i) uses the conditional independency among (5/41 ( uses the fact that X a, 8i+1, 1(41))l I C.--
(++1)-1
on {si, ai 1
petn'-1 and (ii)
Finally, eq. (18) can be proved via the following inequality.
Σ
X(ss, 0i S1+1. 4/41) - X
x²²² Fr
21

---

Under review as a conference paper at ICLR 2022
E
Σ
Y(s, ai,
-x 8/'
+
8.
t=
(0)
(K+-ppp))
C 90 + p)
11 P)
n
n(1 p)
where (i) takes the conditional expectation of eq. (20) on s/ and (ii) uses eq. (19).
Next, we prove the following Lemmas D.3 & D.4 on the decentralized TD Algorithm 2. We first define the following useful notations.
A Amin (E [0(s) > see Assumption 4.
B(s, 8) == = (6))((((()))))))) [ss)]
B. N. Li
(1+1)N B(si,
B = (rr
[B(s, s')].
80m) (s, a.) 80) = ( a, (8())
b(8, a, 8') 1 EM ((()) (s, (s, 8¹).
M
mp(²) = N. Di=iNe ((H1)N--1 z(m) (8i, ai 8641).
b. = 1 &M mmm))
M
bw =
(-s,a) [bs,, a, s')].
05 = B which is the optimal critic parameter under policy Tw-
Lemma D.3. The following bounds hold for Algorithm 2.
1. [B(ss || BullF I CB = +
[[b(m) (s, a, s')l,, [[(s s'Ill, [|b("")] lbb |لw/|| S Cb:== Riuax-
2. 0 (TBO0 < - - 1 uniformly for all w, where ÄB = 2(1 7) > 0.
||0211 S Rg =
2Cs Aa
uniformly for all w.
Proof. We first prove the item
Notice that for any vectors w, y E Tedd
d d
d
d
(m:0))2
y
|
1= 1=1
Hence, we obtain that
[B(s,'')ll= ([0(s) ((s)) "1 [1(())lllnd(') o(s) $1 CB. ((s))
(21)
[b(s,a,s)) R(s, a, (')((((s)] S Rmax Co.
(22)
The other terms listed in the item 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 Men ~ TT (11))
P(-ss, a). We obtain that
T B = Eu (TT o(s) ((s))1((s)) - -(s))
=7 (0 ((s)) (0T (()(())]]]]]](])) - -Eu [s))
22

---

Under review as a conference paper at ICLR 2022
< 7 Eu (0 o(s)) + +Bu ((TT(()))) En [00T o(5))
2
@
(r B) (0T o(s))
-1 7)0
"Ew T ())) 10
AB 10112 2
(23)
where (i) uses the fact that s, s' ~ Mww which is the stationary state distribution with the transition
kernel P and the policy Tw, and (ii) uses Assumption 4 and we denote Ån = 2(1 7) >> 0. Finally, the item 3 can proved via the following inequality.
2 =00)
2 AB
2
2Cb
|1
BuO S T
| ||سا 1
(24)
AB
AB
XB
where (i) uses the item 2.
Lemma D.4. Under Assumptions 1-5 and choosing B S min 8C% Xa 20g
Ag 1-aw) ), N₂ 2 (B
23) 1920 [10( Algorithm 2 has the following convergence rate.
(1 (1-p)>B
Σ
E
(m) P.T 03,11 12.111uu S
2T ow B22 + +M (
AB To 91]
(25)
N
[c]][[]]]] Moreover, to achieve EM Bllloittr 06,11 [rr] S c, we can choose Te, To = o ([(((()))
)
and Ne O) Consequently, the sample complexity is ToNe O fe In(e and the communication complexity is Te + T O[In(e
Proof. In Algorithm by averaging the TD update rule (26) over the agents E M, obtain that the averaged critic parameter Oz,
1.
Em= o'r follows the following update rule
M7
M
02
W
mm Wm.m0lmm mlm²
((Br + +b(ml))
M
m/=1
(m))
1 M
(Bro( + +bx ((m)))
+
3
M
m===1
= De. + BB. + bb)
(26)
which can be viewed centralized TD update using the Markovian samples {st, ai); from the transition kernel ' and the joint policy Therefore, Theorem 4 in (60) can be directly applied to analyze this centralized TD update and obtain the following convergence rate of Or,,, since all the conditions of that theorem are met
B Bu,r. 82,11 [[e] S
<(11
(1-
AB Te
3
E B .u 0% [|]
4
192 CC2, R1 + C3) (K 1)p)
+ 2,3
AB
(1 - 1--)\BBN
(8)
2
AB
B
To
(10-11
12 Rg)
C1
No
(6))
(1 \B
C3 4
3
+
No
(27)
where (i) uses the condition that 3 < 4/AB, the item of Lemma D.3 and the constant that
1920 C2 (L) (ii) uses the constant that C3 == 2(||=,]| + R2).
(1-p)\g
WWe corrected the typo Al B, which should be Au B.
23

---

Under review as a conference paper at ICLR 2022
M Or = 10 i....... 1T. Note that the critic-step (26) can be rewritten into the following matrix form
Next, we consider the consensus error || 11
2m=1
|0(2))
0e,1 1| where we define
O1.+1 = W + 3(Or, By + 1/ :4..; 1T;;
- 1,
(28)
which further implies that for any = 0, o......, T 1,
[ 11ا + 81| A B.
+ $| ;...;bb. 1 11
(80
oo + BCBCH) 11 +
M Σ m=1
M
1
1
||2
(1)) 1 ow ow | 3MM.,
2
where (i) uses the item 1 of Lemma D.I, (ii) uses the item of Lemma D.1 and the item of Lemma
D.3, (iii) uses the condition that B < 1-ow and the item of Lemma D.3. Telescoping the inequality above yields that
2C'
A S (- + ww)
T. |10 + 23MC, (i) 23MCc
(29)
ow OW
where (i) uses the equality that A O due to the initial condition that Or,o 10
:0...
0-1 TT
On the other hand, the final To local average steps in Algorithm 2 can be rewritten into the following matrix form
O = W Te, + T.. TT
Hence, the average critic parameter or, does not change in these local average steps, i.e.,
OIT.ITE = M
O...
0T. (WT))
UT...
(30)
M
M
Therefore, we obtain that
M
| ITeTT:
0e.T.11==
Σ
(m)
UT..+T:I1 - =1
TT.TT:
m=1
(ii)
W
11?
S Ow
2T
(8is) Ow
2T
23MC,
(iv)
ow
2T'
c2022
(31)
-o
where (i) and (ii) use the items 1 and 3 of Lemma D.I respectively, (iii) uses eq. (29), (iv) denotes
that 02 = 2 2MC, Combining eqs. (27) & (31) yields that
M
E
(m) U.T.+T 0% [1/ 2 Σ
E 0
(m) L.T.TT
De,r 11 [[]we] + 2ME
0% [1]]
82002222222 + 2M ca [cs(1- AB Fw
2T
Ab
Te
N
In the inequality above, replacing g(m)
&.I.+Ty from Algorithm by its corresponding variable p(m) from
Algorithm proves eq. (25). Finally, 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.
\B 8C2
ow = 01))
B min
A
20
B
192C 2 + (N - 1)pl
6McG - O(E
N₂ max
+ 25)
AB
(1 p)>B
24

---

Under review as a conference paper at ICLR 2022
T. = In(6Mege
- [0[
In [11 AB3344) -
T = In(3332 o2e 1
O (In(e=)))
In(ow))
Lemma D.5. For any w. EQ, 8 E and (l)) E Am (Am denotes the action space for the agent m), the following properties hold.
|| [s) _ Cz. where w/(m) (a(m)]s) == Wiims In In (m)) (a (a(m)]s)
l|ve [1)) (a(m)]s) [s) - 1ل (m)) (a(m) [s)l| S Lxp [T(m) - wm()))
3. drv 200 (+1s); wim) (-1s) I Lx ( - wmm)l.
(m)
(m)
o (u(s), a) $ (1 - 7) Rmax. 0 S [(w) S Rmax.
5. drylv S Lollw will where Lu == Lx log, (x- + (1 p)
6. drv[Qu(s, a) Qu (s, ] s Loll will where LQ 2.marrke
1-7
7. (ww is L smooth where L = (4L, + L/)/(1 7))
8. [[V](w)] s D,
Ca 1-7
F(w) Lipscchit where LF := 20pp20p(L + Ly + Lw).
10. h(w) is Lu Lipschitt where Ln = 2X (D1AF' Lp + L.).
Proof. For any ((m), ()()) E am E S and (m) E Am, arbitrarily select (mx) = 5i(mm) E 2mn
a(mx') E Am for every m E {l, M) mm Denote w = (w) : S "..; : (())]
== aa (..)), Notice that the joint score vector has the following decomposition
(als)
w (a [s): (1 (a(M)
(32)
Hence, the items & 2 can be proved via the following two inequalities, respectively.
(4) (m)') (0(0m''((( (a(tn))(s)]2 (als)) I Cs.
[ (am))(ss) =
1l I (m)) (((m))s)) - (m))) = (a)s) whi (a|s))
Li || wlll L (m))mm) - (m))
where (i) uses Assumption 2.
Next, we prove the item 3. Notice that
drv(TT (-1s), Tw (-1s)]
(1)
sup
| (Als) nu (A[s)
ACA
(1))
M II A1 CAM m/=1
2
sup
Tipemn) (Amr (s) Twim (Ame 1ss]
m
(181
II Tast (Ame (s) paaaoo (Am (s) Twoin (Amls)
sup
A AiCAl... CAs
m/=1,m'
25

---

Under review as a conference paper at ICLR 2022
(10)
Tagtmn (Amls) - Twltm) (Amls) = drv (m) (-1s), o (m) (-1s)]
Am Cmm
where (i) denotes that Tw (Als) S To (alass)da, (ii) uses the relation that M A, (iii) uses our construction that (mm') = (m(mm) E Smm, V'' E {I,..., M {m). and (iv) uses Am = Am to achieve the supremum. Therefore, the item can be proved via the following inequality.
drv (amm
(-1s), क Li (-1s)] = drv mT(()s), (-1s) L l| will [ (m))
where (i) uses Assumption
The item 4 can be proved by the following three inequalities that use Assumption 3.
80
Rmax
0 S Vs((s E.w
Σ
E
Rmax 1
1=
Rmax
Rmax
0 s Qu(s, a) = E. -Bsp(((s R(s,a, (s) Rmax + 7 1--
0 J(w) = (1- 1E
Σ
R S
7 Rmax Rinxx.
t=
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.
[ = aar (-1+) [Qw (s, (a]s]]
(10) B Bany [10 a) [)]
C
<
where (i) applies Jensen's inequality, (ii) uses Assumption 2 and the item Next, the item 9 is proved by the following inequality.
(()) - F(w)]]
B Bawang am (11s) (cls) 1 - E are (aals))) I]
(8)
Eg-uig a (aasss)) (als)) I[]
Ex (a TI|
Eewery
+ Eg me
(als))
(40)
/ (MS (0)))
]dsdda 2. w|l
SXA
o3 SXA
(oo(s) (s) dsda + L. wil
s
03
(s(s) - (als)
SXA
/
C2
Tw (allss)\usss)) (8) - - (dsda + 20 w|l
SXA
(11)
2L, ull
22, w|l 2c || w|| = LF || w|
where (i) applies triangle inequality and then Jensen's inequality the norm || (ii) uses Assumption 2, (iii) uses the equality that Is Vw (s) = JA To (a)s)do = 1 as well as the inequlities that [A ma (als) (alss)) 2dTV (a]()s), mm (-1s) < 2b | w|l (based on Assumption 2) and that Ss jus (s)ss) 2drv an (118), (-1s) 2T will (based on the item 5).
26

---

Under review as a conference paper at ICLR 2022
Finally, the item 10 is proved by the following inequality
(M()) h(w)]l
s =:11:0001--P111110000-----000000 v
- w|l
< LF 2 w|l = La - w||
where (i) uses the items 7 & 8, and (ii) uses the inequality that |I(()) = Amax (F(w)-1)
Amiin [F(w)] N A for all w (since F(w) and F(w)-1 are positive definite) and the item 9.
Next, we bound the approximation error the following stochastic (partial) policy gradients.
(++1)--
(wwe) =
Σ
+ + 0 o(s:)
T To(m)) 10 (a)
(a/ (s;), (ss),
(33)
N=N
VJ(w)) == :=[v wa) J(w);: Junn)
(34)
(wim Br,k)) = N
1
Σ
R
m))
7 ( (o!Tm ((s;)) ( (si) (35)
KEB..k
JWr Be,)) Be,d;:B,):::: ((a):... ([rr,
(36)
Lemma D.6. Let Assumptions 1-5 hold and adopt the hyperparameters of the decentralized TD in M Then, the following properties hold.
Algorithm 2 following Lemma D.4. Choose T 2 2la(aw")
1. The estimated average reward R (m)
has the following bias and variance bound.
M
Σ
E
R. R.]
<Mow
2T R
(37)
m=11
Var
R
Rd
SAR
mmxx
(38)
where R4 := [IR() M) denotes the joint reward.
The stochastic policy gradients have the following error bound.
[[] VJ(W))] Scoo
27"
2T: + co cg
An 3
Te
ow
C7
Cs
+ 1602 certtic
(39)
No
Supprex
E [[[ss( V](W))) Scrow 27"
160
|0!m) 0% 11
C7
1602
Sapprex
(40)
Nv
(m)) s/1 , (c) me mmmmlieutzy. B..ll where FL.: : or (a((s 01,
Proof. We will first prove the item 1.
When R; = [ :.. R. M) is given and fixed, the randomness of R. = R( (1 + (m))
and (wrr) defined eq. (4) only comes from the noises {e (m) M
m==1. Since (m)) IM
m==1
are independent noises with zero mean and variances ....., Ji R. [R :...; R has the following moments
E [. Ras
27

---

Under review as a conference paper at ICLR 2022
cov R2: R.] diag[ (o ..... (R, )3 Ex-
Hence, R₁ == R3 11
A m I WT Rs (the second "=" comes from eq. (3) and the nota-
tions that Rmm))
((m)
and that R((m) R(mp))) has the moment that I3| [. R.] WT Rg and
Cov Po. [R]] W Ej (WTT) Therefore, eq. (37) can be proved as follows
M
Σ
E R
m)
R Ráj
= B[ R.
R3
= W R 11 11 Rd
M
m=1
$ WT M 11
|1:111
(
S Mow Rmaax
where 1 is M-dim vector of 1 1's, (i) uses the inequality that 1| - (R m2))) M
(based on Assumption 3) and the item 4 of Lemma D.I. Then, eq. (38) can be proved as follows
M
var
R ml)
R.
= Varl Rs R.)
= tr[(
T E, J
ur| =m(( (WTT
1 I1T)
WT
11 )11) ] + tr ( Dr
1
[1)
M
M
M
+ tr
M 11 (1111
E.
E.( [T]
+
(( M
Eg M 11 }
M R2
1
11
|
2
+
2
tr
[W2
E;
1
M
M
M R
2T" OW
+
2
TT.T
1
(1 1111)t(([
M
M2
(1))
3
R R
+
1
M
Rmax
3
Σ
(R(m))?0
p
M
22
mix
where (i) uses the equality that tr(YT) = tr(Y) and the inequality (41) below in which X
WT 3 11 and the m-th entry of Um E TR. is while its other entries are (ii) uses the item
of Lemma D.1 and the equality that tr(zy"
TTa J for any æ, y E RR (iii) uses the condition that T" 2 M]/2 (n(aw and the item 1 of Lemma D.I, (iv) uses Assumption 3.
M
M
ux(EEx)) = X
u
XE
[emll]] |emll||X| (|
m=l
m=1
M
2 < M MR
2 11
(41)
Next, we will prove eq. (39) in the item 2, where the error term can be decomposed as follows
[W](w))) - v(wn)) S M(w) - gell +4 |1ge - 96 11?
(1)
(1T)
+
gt
Fil 2
+4 g V.(w)))
(42)
(111)
(IV)
where we use the following notations that
ge = [ (.. 55. (M))
(43)
28

---

Under review as a conference paper at ICLR 2022
(++1)--1
(m)
1
Σ
R + () -((:)) ( (s:),
(44)
N
(1-1)N-1
1
=
Σ
[ + 70($(41) To - -(ss) T [ (asls))))
(45)
N
Th
awt E Bo
[(s, (11) x 02, 02. [c(ls)))
(46)
Conditioned on the following filtration
= au (411)2NN (c+1)N-1 u (SC+NNN Uffe! ( m =a((p meM.osrse U {ss, az s/4 1=
the error term (I) can be bounded as follows.
E
ge.6 11 F!]
M
(im) (wer) - 21 Fi]
E
M
(++1)N-1
mm) Ra) RZ) (m)) (a!
(s.) (a)
(mm)
E
m=1
i=
(1)
M
(++1)N-1
(m) - Ro) 2/ (m)) (a (
(s.)) Fi! ||
E
m=1
EN
(++1)N-1
Var
Σ
R
(m)
- Rv (m)) (a (1)) (s:) F!
I=
(61)
M
E
(++1)-1
Σ
R
m))
R.) F w5 (1m)) (a ( [s:)
M
(++1)-11
Σ
Var
(R (m) - R5)) (m))
(a)
(mamm)) [s:) Fi
N
(mv)
M
(++1)N-1
Σ
E(R
(m) Ri: [ (0)
(m)) [s:) {
N
m=1
M
(++1)N-1
Σ
Σ
|
(m)) (a! (mm) |s:))
var R
R Fi
N2
LN
M
(++1)N-1
C2 (++1)N-1 M
Σ
[E
(m)
+
Σ Σ
var R (m)
Fi]
N
N2
i=tN
i=th
(06)
C2
2 (Mow 2T
R
+
(AR²
(RRmaxx )2)
N
= c (Mow + N
g2)
(47)
where (i) uses the definitions of v wm) J (ux) and gr
(m) defined in eqs. (33) & (44) respectively, (ii)
uses the relation that ||| Var + |EX 1 for any random vector X, (iii) uses the facts that
(!(T)) (a.m) ls),, R. E Fi are fixed while (R. (m) (++1)N-1 are random and independent given F/, (iv)
Ej v/ var(z)) = | var((z) for any random scalar x and fixed vector Y = [yI...., ya] E 2dd (Here we denote = ws! (o(m))(a (a. (m²) |s;) E F)), (v) applies Jensen's inequality to the convex function (.)2 and uses the item of Lemma D.5 as well as
uses the equality that Var(xY) = Σ/= var(zy,) = ==
29

---

Under review as a conference paper at ICLR 2022
the fact that R3 E Fl is fixed, (vi) uses eqs. (37) & (38) and the fact that the conditional distribution of R m variables.
R₂ E F/ is the same as that on Fú since the noise ej c(T) is independent from any other
Then we bound the error term (II) of eq. (42) as follows.
(++1N-1
110
Σ
1),)) ((m)
v( (a." [s;]
(++1)N-1 -
Σ
Σ
-1 (a! [s:)]| [s,"m
Ow. 1/
N
N=N
(10)
C C 7)²
((+1)--1
Σ
Σ
M
110mml) - 0-,1" 1|
N
i
m=1
M
4C
(m)
0%, 11
(48)
m=1
where (i) applies Jensen's inequality the convex function || (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,
R(s, a. 3) + x6(3) To;, (ss)) ((,()al))
(49)
which satisfies ||X a, 8 || S [ a, 3) + 7 + ((s)) 8 [a(()a)))| S (Rmax 2a) (the second < uses the item 3 of Lemma D.3) and X = Espoy [((s, at, 8it1, 1/41) Fi| = 9t
where &N Wi E Fe == a (0(mm) Hence, Lemma D.2 yields that
meM.ossse U {5t, a, 1/11111 (m)) me IIN-1 U {SEN)) are fixed.
(++1)N-1 Σ
E [19
31]] =
X(s;, Oj, S141, 1/+1) - X
x F.
90 (Rmax + 22 11
(50)
N(1-1 p)
Next, we bound the error term (IV) of eq. (42). Notice that
Dt V((we)
=Ew, (R(s, + hro(3) -p(ss][ 03 [R(s, + +5) Vas (5)] (b (alss))) (
=Buri [<]((<3)00n TO0 - (5)] [d(s)] Too)T Vo) 2 (ha(al)) [r)]
(51)
Hence,
Bun, [7(0(3)T To - [3) - [d(s) 0% Val (5)] 2h (als) wx 11
19 [](w)]12 =
(4)
Ew. (7(((() T0G Vvn, (3) [d(s) TO. Van (s)) (b((als))
(12)
< 20 Bun, (63( T 0% Vas (3))
+ [ss) TO VaA (5) km
20
[o(3) Ti, Vas (3)
(1(s) (als))(3 addsdads
SSXAXS
+ + B.s,
||0(5)
-Va, Va, (3)) [
(18)
S 20%
(0(3) 0r - V3)
(a(s) addsdads
SxAXS
30

---

Under review as a conference paper at ICLR 2022
+ +2 [|((s) o2, -vas (c)]/(10) [wo)
(30) 20 (7 + 1) [00) Ow To Van (8) (x)
40 Sapproxx
(52)
where (i) applies Jensen's inequality to the convex function || I12. (ii) uses the inequality that | + y/1² I |||=|| + /| for any I, E Rd, (iii) uses the inequality that (( S > PP a); Vs, s' E S, a E A, (iv) uses the equality that fsxa 2
a)ddda = (3), and (v) uses the notation that Sapprox sup Eonn, [[V[(s) o(s) 0% [ Substituting eqs.
(5))) into eq. (42) yields that
E [w]))((w)) [1(
M
R2 S 2 4 Raax
(Mo + 4 ~² 160
Σ 110
02, 11
m=1
(Pmux + 22)
p)
+16C
Supprox
N(1 p)
2T e7 c.ow +
16C 2 v
Σ
|10(m)
0% 11
+ 16C
ceiiti
(53)
N
Supprex>
where mlm) W E Ft are fixed, and we take the conditional expectation of eq. (47) on Fi C Fj and
denote that Ca := 4MC2 R R C7 == 160 R + 360 (Rmax (x+11p) Substituting eq. (25) into the unconditional expectation of eq. (53) yields that
1-p
E [[] - [+(()) S C40W
2T
C7 + 160
(
3p + 2M
(1
AB
AB
1
160 ceiiii Sapprrx
N
8
C.oW 2T"
cg
ow
21"
+ co
AB
3
Te
C7
Cs
+
16C2
ceritic Sapprox
N
where we denote that C == 160 i. co == 32Mc3 cs 32 C2. 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 B,,x) uses the minibatch B,, of size N₂ while V (w;)) uses batchsize N. Second, eq. (40) is conditioned on the filtration Fr, == o [F,OO (f8i, ai, 81-1: 1441 (e!""))MMM) b B.
which includes not only the filtration F, by eq. (53) but also the minibatches U Br, used by the previous (k 1) SGD steps.
Lemma D.7. Implementing Algorithm 3 with S
T
In M
T. 2
ln(3D,C
20%
2 2lm(o 5''
In(ow:)
3n3 KJ In (1)))=(2) N 2 (3040)(+11-2 and N₂ x (1 k/222 the involved quantities have the following properties, where E., denotes the expectation under the underlying distributions that s Vw, a ~ (-1s).
k/2
1. dp S Amax Amxxx [[w)] = [[[(W]] - C2 Vw.
2. 1 1 < || - [w) < 1 - urs so 11 S 1
IAF 3. c S (1F(w))11 S AF- For any w. E Rdd,, IT
4. ||()]]| s + [()ل)) < Ps.
5. Mww) = arg min F.n. (v/h(aa)s) Th (s, so
E. (vhs hh(w) - As(s,
< Supprex where & Uwe a (-(ss)
31

---

Under review as a conference paper at ICLR 2022
6. E. (alss - (s, 2 -Cn
Cappappeee VW..
Carzor
7. N = / (-nn--//-//
S76C (x+11p)
1-(1-nAr /2)
(1
8. h2 approximates the natural gradient h(we) with the following error bound.
Billh - h(we)]l 1 c10 (1 9dF
(K-
+ cl + c12o
+ c13.3o of
2
+ c14
1
AB
To
+
C15
+ Cippapp
(54)
8
N₂
Proof. The item 1 is proved by the following inequality.
X Amin| [F(w)] & Amax [F(w)] (5t)
[[(W]]]
(1i1) < E. [[|) (a]s) [[] S C2
where (i) uses Assumption 6, (ii) uses the fact that F(w) is positive definite implied by Assumption (iii) applies Jensen's 's inequality to the convex function and (iv) uses Assumption 2. Next will prove the item 2. On one hand,
(1) Mmmax [F())] 2 C 2 2'
1
Amin [T (y
(55)
where (i) uses the item 1, (ii) uses the condition that 17 I .
On the other hand,
Amin [/- S Amax -T- F)]) _ || - F(w)]] = mymiin [F(w)] S nAP, (56)
where (i) uses the fact that F)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(w)-1 positive definite with minimum eigenvalue Amax [Fw)]] C-2 and maximum eigenvalue Amin [Fw]] Ap implied by the item 1.
The item can be proved by the following inequality.
[h(w)] [[ < [|= 2 XF [> (
DD'
where (i) uses the item 3 and (ii) uses the item of Lemma D.5.
Next we will prove item
Consider the following function of x E Rdd,
fa(x) E. =
1 1 a Bu (s) 2
2 En
- E (s as)
1 F(w)z - [[w)=-VJ(w) x En (A
2
Since (()(w) F(w) is positive definite, f is strongly convex quardratic and thus it has unique obtained by solving h from the equation f.a F(w)h-
minimizer h(w) [(w) (V)() (
VJ(w) = 0. Hence,
E. [ll Tn(w) a|]
min Euy (als) T (s, 3
ht
s sup min E.n [ (Ww As (s. Supprox>
actor
(57)
32

---

Under review as a conference paper at ICLR 2022
which proves the item 5.
The item can be proved by the following inequality.
E [Am (s, a) (als) h(w)]
Vi (s) (als) A. (s, (als) h(w)) dsda
(a|s)
Va (8) FT (8) (a|s)
(s, (als)) T hww
Va -Te- (s, (ulass) [hw]]]]][[]]]]]]]]]]]]]
En
Vw nw (als)
Mi- (S) (m) 21
Rew (AA((s,)) - (L(()s))((w))) & C. /.
Sapprox
(58)
(e (als)
where (i) uses Assumption 7 and the item 5. Multiplying -1 1 to the above inequality proves the item
Next, the item 7 can be proved as follows.
N₁ N (1 - A/ (2) /2) k/2
Σ = (1 /2)
N(1 7/ (1)
v n/F/2)
1 (1 1/)p/2)K/2 K/2
2304 (n: p)
(1- (K)(
mM - p) (k
1 11/1122
576C (N +1 p)
(1 (1) p)
where (i) uses the conditions that N2 x (1 23040 (x+11 1-p)
k/2 and Σk-1 N2 N and (ii) uses the
condition that 2 -A
1173
Finally, we will prove the item 8. Until the end of this proof, we use the underlying distribution that a, ~ (e((1ss),ss44 ~ Pe(-1s,, a.) for iN < <is < (t + 1)N 1 in the f-th iteration of the multi-agent NAC algorithm (Algorithm 1).
The local averaging steps of 21, == [3
(M) T yield the following consensus error bound. i,
(M)T
M
(1t)
(m) Tr
Er, )2=
A 12= |WW T.
2.0 1
|
I ow
2T.
||
A2s
l
(iii)
M
2T'
Σ
(2,,0
(m))
ow
27'
(m)
(a.
(s:) (ss)) h (m)
(112)
m=1
m=1
(10)
C
o
w
2T,
2
Cloo
where 27. M7
A. (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 of Lemma D.5.
M [m]
Then, we define the following stochastic gradients of function fu-
wimm Fus (1e,,)) = N
1
(m)) (a!" (m)) (s))pe(aa)s)) si) he.k - Fajmn Bi,k)
iEB
1
SJ,, (11,e) = ((((sss)) he (J(r::
Σ
Nk
HEB.,
33

---

Under review as a conference paper at ICLR 2022
V was
far for
V Vwin fur (m)) (a! (he,k)....;
P wimm fwr (h(,k) = No
M
Σ w
(1)) (a)"")ss)))111 (m) - A (wee BLb))
iEB
Si, (he,x) = Wis (He,,))..... Wwnn (1e,,))]
where A wim) wwmm Be,k) and Jurr B(,x) are defined eqs. (35) & (36) respectively. Hence,
| ( - Vin, (kr,)))
M
(m) Sur (Me,,) - wim Sun (
m=1
M (m)) ve(ailss) he w/ m/ (ailss))
Nk
B
(m)) M (FCT. Err
BeB m=1
M2C
22's | M2 o (m) where (i) uses the equality that v'e (as he EmEm Ri,T. Lemma D.5.
(m) (IT
-Zr.)²
(59)
N
SE m=1
MET. (ii) uses the item 1 of
Since, We, be,k E Fi, while {st, J.B., are random. Hence,
E E|l V far (h),))
V.u, Fen)
1
[ch(aalss)((((alsss)] hh. VJl Be,k) F(we)eu + V.(we))|
E
NE
i
(9
[dh(aalsss))h((a(l)s))) F(wre)] [Mc, [2
S
2E
N
BE
+ 2E
[|] V [wn: Br,s) - VJ(WE)] [Fe.]]
(00
Σ (cal F(wr)) 1 FF. [Fix]11be.all 11
2E
N
B
2F
[wnr Br,k) VJ(a))
(m)) 180 (K + p) N1 p1
x
|11,,,e112 + 2c,ow +
27
207 N
+
320
2
M
(6())
11. + 32C
critic Sapprox
m==
(60)
where (i) uses the inequalities that || + yll < 2||=||| + 2/yl| for any x.y Rd. (ii) uses fact that hr E Fe,, and (iii) uses eq. (40) and applies Lemma D.2 to the quantity that X X(s, a, s 8) 1h (a)s)))(((s)) in which we Fr,x is fixed and [| a, 8', () S V.
Combining eqs. (59) & (60) yields that E V Ja,, (hr,,) - V Sa, (1e Fr,,]]
22 V fu, (hr,,) 7 f.. (fr,,))
FF.N]] + 2E 2E|1 Vl (hr,,) - V Swe (hr,))))) Fe.e]
36(x + 1 1 p))
<C 2M 2 ow
||/e,21112 + Ac4o
N1 - p)
M
+ N₂.
407
+ 6AC%
Σ
(m) - 02, 112
64C Sapprox.
(61)
m=1
34

---

Under review as a conference paper at ICLR 2022
Therefore,
B |1, - h(w=z)l Frrm]
=B[llhe -n sur (tee,k) h((we)) [1
( $ (1 + (1+ ) 11, - NW (he,)) h(wo)ll [FF
+ +[1+ + (n)r))]][[(1)) [V (Prc,k) V (1t,,)) 11 Fr.e]
@ (1+ |1,,, (wse)) [Re, - h[w+)] - 11 1(ww))) )( |1
+ + + 2²') / fwu (b),,) - V.n. (ms,,))) (1
(1+n)>)ll [1 - 7/ (wx)) [ 1(w))]]1²
+ + 27 ) fw. (he,a) - Vf, (he, [FaN]
(2))
S (1+ m)) n) kl, - -h(wr))1
+ 2n (ot
2M o + 36(K + 1 - p)
||/r,al1 + 4c
dp
N₂ - p)
+ N&
407
+ +4C
Σ
M
|10mm) - 02,11' + 64C2
Sapprox
m=l
S (1 - ))=))
h1. - h(wx)]1
+ 27 (20 2212 +
36(k + 1 1111p p)
(11/1x - h(2z))1 + 11((3))1) +
Ar
N1 - p)
M
+ 4c + 407
+ 64C
Σ
100mm
0% 11" 664
N₂ m=1
(wv)
(1 (1- nd
|1/e,, - Muz))1++
+
20 dx
(20g) 2
2T's
36(K + 1 - 1- D3
2
N₂ p) X
+ 1c 2T"
407
+ 6403 Σ
M
|00mm) 02, 11 + 64C caritee 1o Sapprox
+
N₂
(0)
11 n11F)
|1 - M(ar)]1
81/
(ct M2 o
2T. + Co
+ Ap
2
N
M
+ c.oW 2T' + 1602
Σ
(10(5) - 0% 1| + 16C critic 1 Sapprux
m==
where (i) uses the inequality that || y11 < (1+n)>)||=l)) + "1 for any y E Rd, (ii) uses the notation that V (h) F(w;)h VJ(..) (w::)(h h(wr)) and the fact that
wi, be E Fr,s. (iii) uses eq. (61) and the item of this Lemma, (iv) uses the conditions that Tg 2
C3) and the item 7 of this Lemma, and (v) uses the notation that cg in(ow)) )
1801 (x+1 x1
+ C7.
Then, taking unconditional excoeectionaeeppeccaaionn of the above inequality and iterating over A: = 0, 1.... K-1 yield that
E h1 - h(we))] = =Ell/b.k - M(wr))121
s (1- ndr)
E "lllbe. - -
+
8n K-1
Σ
(1
ndr K-1-k
2
d
2
km0
C ow
2T.
C9
cooot" + +160
Σ E [[[||| (m)
0z, 18] + 160
critic Sapprox
Nu
(
(1- ndr) K
"Ellbba- - 9
35

---

Under review as a conference paper at ICLR 2022
+
16 X
2T: C 3 1 W
+ c.o
2F"
+ +60
10
Σ
M
E
0 mm)) -0%, -0,,11² + 160 ceriti
v Sapprox
m=1 1
S - (1 - 77p 12) k/21
k-1
Σ
(1
nAp
(K-1-2)/2
Ndx - /1 - /2)
2
k=
(6)
nAF K
16
11
BE |[ h(wr)|1
+
(C 2T:
+ +Coo 27 + 16C2 Sapprox
2
x
2560
2T
3202 + 2M [03 (1-
[cs(1-
An B
To
No. 1
81y0g
+
+ NAr(1 - nFF
X2
(60)
(1
nAp 2
K
E. B1llii-1 M(we)|1²]
+
16
(c*
Mow
ow
22:
+ clo 27"
+ 16C Soppic
+
2560
2T
8200
02 + 2M c3 [cs(1-
AB
3
To
+
N )) + 128cs
C1
(62)
X2
8
Nn
(iv)
mdr K
3 1
E
1 h(w) + || 1| + || - h(ww)) |
16
2 2T. ow
+ cooo + 1602 Suppprox) )
X2
256C2
2T 8²002 02 + 2M 10s 2M(cs(1
AB
Te
N )) + 1280g
3
+
X
8
Nn
(0)
ndp K
6D3
1>p K
3
1
B -111i11111 - h(w(-1))l -
11
+
(1
2
X
2
16
+
(C.
M o + ccoo + 160 sappiip
13 Sapproxx)
X₂
256C
2T
3º02 02 + 2M [cs
(1 [os(|
AB
To
128cg Nn
B
+
X2
N
where (i) uses the notation that 00 =
hr, the item 7 of this Lemma and the inequality
that Kk-1 (1
ndr
K-1-k
S n
(ii) uses Lemma D.4, (iil) uses the inequality that
2
(1+
22)
16 ma implied by the item 2 of this Lemma, (iv) uses
VI /2)
(nAF/2)
the inequality that ||.r + y + =1I2 < 3| + 3| 3| + 3||=| Vo, y, 2 E Rd,, and (v) uses the items of this Lemma. Taking unconditional expectation of the above inequality and iterating it over yield that
E h/, - h(<x))l*]
(1)
3 ndF) K1t t B[]]/o h(wb)) 1
12D3 X
MAF K
32
(C,,22
2T, + cCoo + +1602 Supppox))
X2
512C2
3 + 2M [os (1
AB
To
G1
1)
2560g
@w
B)
+
+
X2
8
N.
N1
(10
(3(1
nde
K 1
''((1
ddp
K
E
- - M(woi)
2
2
16
(Ct (CM
MoW
ow
21:s
+ +C4oW
27"
+ 160
2) Sapprox)
256C3
2T' 820z + 2M
[cs(1-
AB B)
Te
(!)) +
128cg
(o
+
X/
No
12D3
(1
ndF K
+
32
(C..
o + coow
2T
+ 1602
S Seppic
X
2
xx
36

---

Under review as a conference paper at ICLR 2022
512C
21
82 + 2M (cs(1
A )
AB
To
C1
2560g
(Ww
+
X
No
Nn
((0)
ndp)
K
(1h_11² 11
D3
5 2
Xp
12D2
Adp) K
48
X
2
+
X
(C
W
21-
+ coow
27
+ 160 Sapprox)
7680
21
18200022 0² + 2M 03 (11
A/ 3)
To
Ci
X
No.
384cg
11
- (1 - " ////2)((k
/2) (K 1)/2
+
n
2304C (K + p)
(10)
mAF
(K- 11/2
2T: + C12ow 2T + c13320 2T: ow
S C10 1
+ c11 w
2
Te
C15
+ C14
+
+ c16
8
Ne
where (i) uses the inequality that 3(1 - n/r/2)K S 1 implied by the condition that
K 2 I 1 (ii) uses eq. (62) with = O, (iii) uses the condition that N 2
In3
1 p)(1 g2r /2X 1772 as well as the inequalities that ||-11 - h(wo) 12 S 2/ 1|@
2304 (x+
2 h(wo)| 2 3 2 hد 1| + 22 (* uses the item 4 of this Lemma) and that 3(1 2)) < 1,
(iv) denotes that 610 == 1/
1481
X
+
ca C
G1 =
480 M²
G12 ==
48c1 X
C13 ==
7
X
C
1536Mc; Co
768C2
C11 2 C15
X
C16
This proves the item 8 of this Lemma.
E EXPERIMENT SETUP AND ADDITIONAL RESULTS
In this section, we present all the details of experiment setup and additional experiment results.
E EXPERIMENT SETUP
We simulate a fully decentralized ring network with 6 fully decentralized agents, using communication matrix with diagonal entries 0.4 and off- entries 0.3. The shared state space contains 5 states and each agent can take 2 actions. We adopt the softmax policy (als)) xx eMs.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 5-dimensional identity matrix state features. We set the discount factor y 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') Σ; fa(, s') (we name it DAC-RP1 for decentralized AC with reward parameterizaatin) 5, and our proposed modified version of DAC-RPI to incorporate minibatch, which we refer to as DAC-RPI00 with batch size N = 100. For our Algorithm 1, we choose T 500, T. 50, TV 10, No 10, T' = T. 5, B = 0.5. {a.m 16 mm=1 0.1, and consider batch size choices N = 500, 2000. Algorithm 3 uses the same hyperparameters as those of Algorithm except that T' = 2000 in Algorithm
We select a 10, 50, 200 for Algorithm I with N 100, 500, 2000 respectively, and T. = 5, a = 0. 0.5. 2, 0.04, 0.2, 0.8. K = 50, 100, 200, N₂ = 2, 5, 10 for Algorithm 3 with N 100, 500, 2000, respectively. For DAC-RPI that was originally designed for discount factor 7 = 1, we slightly adjust it to fit our setting where 0 < 7 < 1
'The original algorithm in (70) uses the parameterization R(s,a) Σ, A a), and we extend to our setting where the rewards also depend on the next state s'.
*(70) defined the Qufuctioon Qo(s, a) B|Fr+1 ](0) for policy parameter 0 and used the temporal
differences of
ritz pá (of) vi(n() and 52 Re() på Veti(vt) Ve(vi) for critic
37

---

Under review as a conference paper at ICLR 2022
10-5
2.0
20:1000000
2.0
13
Alg.AA 3.33 103
No 7.0-200
Ag:1/4-230
38-502
1.5
1.5
6
DAC-RF3
DAC-9P102
DAG:4P100
1.0
2.0
0.5
0.5
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
Communication complexity
Semple complexity
1e5
Communication complexity
le5
Sample complexitty
1e5
Figure 2: Comparison of [ux)]] among decentralized AC-type algorithms for ring network.
For this adjusted DAC-RPI, we select diminishing stepsizes 3, = 2(1 3, 5(l + +1) 1)-0. as recommended in (70) and use the rows of a di00ndimeai identity matrix as the reward features {f((s, a, s') : s, E S.a E A} (i = 1.2..... 1600) to fully express R(s, o, s') over all the 5 x 2 x 5 1600 triplets (s, a,,a, 8'). DAC-RP100 has batchsizes 100 and 10 for actor and critic updates respectively, and selects constant stepsizes 8, = 0.5, Ag = 10. This setting is similar to Algorithm I with N 100 to inspect the reason of performance difference between Algorithm and DAC-RPI. All the algorithms are repeated 10 times using initial state O and the same initial actor parameter wi generated from standard Gaussian distribution.
E.2 GRADIENT NORM CONVERGENCE RESULTS IN RING NETWORK
Figure 2 plots J [[² v.s. communication complexity (((T, + Ta + +T) 65/. ((T, + Te + T' + T.) = 70% and 2/ for Algorithms & 3, and both DAC-RP algorithms, respectively)" and sample complexity (t(T,N + N). 2t and 110t for both of our AC-type algorithms, DAC-RP1 and DAC-RPI00, respectively). $ 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 [wz) 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-RP 100 outperforms a lot than DAC-RP1, and converges to critical points earlier than Algorithm 1. However, it can be seen from Figure I that such early convergence turns out to have much lower (wx) than Algorithm 1 with N = 100 and N. 10. Such 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-RPI and DAC-RPI00 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 < ? < 1. we use 8f r/+ + (o)) Vi(22) and = (x())) + (v)) Vi(vÉ) where of Rs J(O:) removed since Qo(s, a) = E(F.41). In addition, we used two different chains generated from transition kernels P, Pe respectively for critic update and actor update as in our Algorithm 1.
'Each update of decentralized AC uses T. TV and T' communication rounds for synchronizing critic model and rewards, respectively. Each update of our decentralized NAC uses T. + TV, T', TV communication rounds for synchronizing critic model, rewards and scalar 2, respectively, Each update of both DAC-RU RPI and DAC-RPI00 uses communication round for synchronizing e and À respectively.
*DAC-RP) RPl uses sample for actor and critic updates respectively. DAC-RPI00 uses 100 and 10 samples for actor and critic updates respectively.
'hhe relative reward estimation error the t-th iteration of both DAC-RP] and RAC- is de- MM Eswes Eees ( a, s') -,, (m)) ((s,a,,')) and
fined as A/B where
MISPLA
[ Ex,'es EoE R(s.a,s')²
10 At the t-th iteration of Algorithms & 3, we focus on T(!)) = $/4 E (1-1)-1 T! as the estimation of
the batch-averaged reward F, w (++1)N1 R2 since its estimation error affects the accuracy of the policy gradient (4). The relative estimation error is defined NF! MM (7(m)) F.)
38

---

Under review as a conference paper at ICLR 2022
and DAC-RPIO0 apply only single TD update per-round, and hence suffers from a larger mean TD learning error (about 2% and 1% for DAC-RPI and DAC-RPI00, 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) !! All these relative errors averaged over iterations.
E.3 ADDITIONAL EXPERIMENTS IN FULLY CONNECTED NETWORK
To investigate the effect of network topology on the performance our algorithms, we also conduct the above experiments fully connected network with 6 fully decentralized agents, using commu- nication matrix with diagonal entries 0.4 and all the other entries 0.12. The MDP environment and all the same the above experiments for ring network. Figures 3 & 4 plot the learning curves of the optimality gap J - (wr) and || J || respectively for fully connected network. To make comparison, we plot J (wx) and J(x)) || in Figures & 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.
the hyperparameters
1.50
1.4
Mg-1-M-2000
Ap. 100
1.4
4k-31/9-500
Alp 3 3:0
1.25
1.25
Ag. Hg.3.M-0000
1.2
Agg 3/000000
1.00
0.75
Aj. 2000
DAC-aP1
D4C AP100
1g00000000
1.00
0.75
Al..1 1l N-00000
Agg. N.000
DAC-FF
[AC AP100
3
0.8
1.0
0.8
0.6
0.50
0.4
0.4
0.5
1.0
Communication complexity
1ed
Sample
165
Communication complexity
le5
Sample complexity
le6
complexity
Figure 3: Comparison of optimality gap (ww) (wn) among decentralized AC-type algorithms in
fully connected network.
1.2
Ap. 100
12
Ag. 100000
A5.3 100
Ag 3-0
Ag.. 200
Akg.1 10000
A0-1-4-200 Ag. 4g-3.M-0000
4g-11/0-500
1.0
20000000000
dgy 2000
4g 3 3-00000
0.8
0.8
|P
0.4
0.4
0.0
0.0
0
0.5
1.0
0.0
0.5
1.0
Communication
Tedt
Samplc complexity
1e5
Communication compiexity
1e5
Sample
le6
compiexity
complexity
Figure 4: Comparison of [(r]]] among decentralized AC-type algorithms in fully connected network.
1.50
1.50
1.4
Ag-1.M-000
1.4
Aig 1.030
1.25
1.2
20-33.1-2000
0
44-0---000
Ap 100
4g.1N 150
4p.11
1.0
3 1.0
#g..M. 2000
1.N.N..3 2200
0.8
4971
0.75
(AL-4133
BAC 3P100
BAC AP100
0.6
0.6
0.4
0.25
0.2
0.2
0
3
0.0
0.5
1.0
0.0
0.5
1.0
Communication complexity
1ef
Sample complexity
165
Communication complexity
le5
Sample complexity
le6
Figure 5: Comparison of optimality gap J(w*) (wr) among decentralized AC-type algorithms in ring network.
"The TD error at the (-th iteration is defined as M 17
ΣM (m0mm) 02,
39

---

Under review as a conference paper at ICLR 2022
E.4 TWO-AGENT CLIFF NAVIGATION
In this subsection, we test our algorithms in solv- ing a two-agent Cliff Navigation problem (39) in grid-world environment. This problem is adapted from its single-agent version (see Ex- ample 6.6 of (48)). As illustrated in Figure 6, two agents start from the starting point "S" on 3 x 4 grid and aim to reach the destination "D". Here, global state is defined as the joint lo- cation of the agents, and there are in total (3 x 4)² 144 global states. In most states, an agent can choose to move up, down, left or right by one step and receives -1 reward. How- ever, once an agent falls into the cliff "X", will return to the starting point "S" and receives -10 reward. When an agent reaches "D", will always stay at "D", and receives 0 reward the other agent also reaches/stays at "D", or receives -0.5 reward otherwise. If an agent is not "X" or "D" and selects direction that points outside the grid, then stays in the previous location and receives -1 reward. The optimal path for both agents is the red path shown in Figure which has the minimum accumulative reward J = -0.1855 under the discount factor 0.95.
6
S
X
X
Figure 6: Two-agent cliff navigation. ("S", "X", "D" denote starting point, cliff and destination re- spectively. The optimal path is shown in red.)
For our Algorithm 1, choose T 500, Tc 50, = 10, N. 10, T' = 5, B 0.5, fam 16 0.1, and consider batch size choices N = 100, 500, 2000. Our Algorithm 3 uses the same hyperparameters as those of Algorithm except that choose T 2000. We select a 5, 20 for Algorithm with N = 100, 500, 2000 respectively, and T, = 5, a = 0.002, 0.01, 0.04, n 0.002, 0.01, 0.04, K = 50, 100, 200, N₂. = 10 for Algorithm with N 100, 500, 2000, respectively, For DAC-RPI, we select T = 10000, 3. = 10(t + 1)-0. and [8g = 5(t + 1) 0.6 For DAC-RPI00, we use 2000 and batchsizes 100 and 10 for actor and critic updates respectively,
and selects constant stepsizes 3g = 0.5, 80 = 1. This setting is similar to Algorithm with N = 100
to inspect performance difference between Algorithm I and DAC-RPI.
10=1
-Joo
Ap. 100
Alg /0=100
Ag. 3.M-300 Ag-1104-2000
Agg 3 N4-500
Alg
N--00
Mg.11/--2000
N-N-50
Ag Mg-10-5500
Agg. NevoooD
Wil 2.-2244-2000
DBC RP1
CAC-U71
DAC RP100
DAC APE00
0.0
0.5
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0 1e6
Communication complexity
1e5
Sample
1e3
Communicatiin compiexity
Sample complexity
complextt
Figure 7: Comparison optimality gap (ww)) J (wrr) among decentralized AC-type algorithms on cliff navigation.
Aig N--00-1
Ri. N---00-000
2.0
Aug. N-500
Aig. Me-500
Agg3 2gg-100-300
Agg rewwoo
Ala. N.-2000
A.g 2002
#.g-1.4-2000
1.5
1.0
0.5
0.5
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Communiccaion complexity
1e5
Sample complexity
163
Communication complexity
1e5
Semple complexity
le6
Figure 8: Comparison of optimality gap J(w)) J [(ae) among decentralized AC-type algorithms on cliff navigation.
40

---

Under review as a conference paper at ICLR 2022
We plot - and (w;)) in Figures 7 & 8 respectively. It can be seen from these figures that both our Algorithm & Algorithm significantly reduce the function value gap J - J (wg ). and their convergence is faster with larger batchsize. In contrast, the function value gaps of DAC-RPI and DAC-RP100 do not decrease sufficiently and converge to a high value. In particular, since DAC-RP100 achieves larger function value gap than Algorithm I 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.
F CONSTANT SCALARS
The following global constants are frequently used.
M: The number of agents.
?y: Discount rate.
m The reward bound such that 0 < (Assumption 3). Hence, 0 < n !m)) (s,a, 8'), pQ(m) R. S Rmax.
S Rmax for any s, E 8 and A
ow E [0, 1): The second largest singular value of W.
wn == _ax ((w) denotes the optimal policy parameter.
The following constants are defined in Lemma D.3.
CB -1+
C. := Rmaxx-
Aa Amiin (E (o(s)o(s) > satisfies Assumption 4.
AB 2(1 7)>>)>> > 0. (Assumption 4 implies that A > 0.)
Rg
2Ch. Az
The policy-related norm bounds and Lipschitz parameters defined as follows.
Cg, Lg La > 0 defined in Assumption For all 8 E S, a E A and w. [[w S C.. (als) (a|s)) < Lo - w|ll and drv (ma(- (-1s)) s L - - will
Ly = I + log, (16 1) + (1 p)-
LQq = 1-7
ke Lie.
L Rmax (ALu Lw) -
D, = CoRmax
1-7
LF = 20O(L + LuC + L.).
+ Ly) where Ap = infwen Amin[F(ub > 0 (Amin denotes the minimum eigenvalue) which satisfies Assumption 6.
L, = 2x (D)''(D>'110 Lp L
The following constants are defined simplify the notations in the proof.
Ci = C92 n2 + 1)p]
(1-P)X,
02 = 2( 2MG )²
C3 2(110_]11 2| R?)) where 0-2 is the initial parameter of decentralized TD (Algorithm 2).
4MC2 R2
41

---

Under review as a conference paper at ICLR 2022
96 32Mc33
360 360 (flmar +2Ro))
= 160 R x²
1-p
08 32Mc C
C9 = DJ + C7.
(1(1-p)
010 = 2 11 12 + 14D3
co C
where h- is the initial natural gradient of Algorithm 3.
480+ M²
C11 X
48c4 C12 X
C
C13
X
C5
C14 ==
X
M636
C15 =
A
768C3
X
KL ( (-55])//(T + 4h, Bmax
C17 Egne
10
018 CN + c10
1
X
1 10-
019 = CNVonI + c11 Lu
2/2
1 + 404
= Cove12 + 1
2/
10
22 Cov0 c
1
2ラ
1 104
02 = CNVOT= + ciaban
40
= CVVEI5 + GsLiv
1 +
Xx
40t1 c24 := cooo 11
x/
42


Reviews:
[{"review_id": "kqjK4ubCcPc", "reviewer": "Reviewer_ZhdW", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is professionally written and well-organized. This is the first work that derives sample complexity bounds for decentralized AC-type algorithms, and the obtained sample complexities match the existing ones of centralized AC and NAC. Moreover, the corresponding communication complexities are orderwise lower.\n\nPros: \n\nThe developed algorithms are fully decentralized. Especially for the decentralized NAC algorithm, the agents use decentralized SGD to compute the inverse of the fisher information matrix via solving a quadratic problem. This is proven to be computation-efficient.\n\nThe algorithm designs of AC and NAC use mini-batch sampling to substantially reduce the communication complexity (by an order of $\\epsilon$). Also, the algorithm updates avoid sharing local actions. To accurately estimate the average reward while preserving privacy of the local rewards, the authors propose to add large Gaussian noises to each of the local rewards, and the total noise variance is shown to be substantially suppressed after averaging. This is because the mini-batch samples and local averaging help suppress the noise variance.\n\nFor the decentralized NAC, decentralized SGD is used to solve for the natural gradient update. This decentralized SGD uses Markovian samples and an adapted batch size scheme. Such a design helps optimize the error bound and achieve the desired complexity.\n\nQuestions:\n\nThe decentralized NAC algorithm involves multi-level loops, is there a more effective way to implement it in practice?\n\nFor the same algorithm, is it possible that we only update the inner mini-batch SGD for a single iteration and still achieve the desired complexity results?\n\nIn the critic update, the algorithm performs multiple steps of local model averaging after the main critic updates. What is the purpose of introduing these additional consensus steps? Is it necessary?", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper is professionally written and well-organized. This is the first work that derives sample complexity bounds for decentralized AC-type algorithms, and the obtained sample complexities match the existing ones of centralized AC and NAC. Moreover, the corresponding communication complexities are orderwise lower. I think the developed decentralized AC and NAC algorithms are good complements to the existing multi-agent RL literature, and hence I recommend accepting this work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eAXFJKXZAo7", "reviewer": "Reviewer_hsKp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n1.\tThe proposed two decentralized multi-agent actor-critic algorithms achieve the state-of-the-art sample and communication complexities. The proposed algorithms also preserve privacy which seems important in practice.  \n2.\tExperiments have demonstrated that the proposed algorithms achieve lower sample and communication complexities than the existing decentralized AC algorithms. \n\nWeakness: \n1.\tThe paper does not put this work into context. In general, efforts over the past year/two have been made to develop different policy-based and value-based algorithms for MARL, some of which have also considered communication efficiency. Authors have missed many works in this field. Even for related works mentioned in this paper, the authors did not discuss their advantages and disadvantages, which makes hard to evaluate the real contributions of this work. \n\n2.\tIn the beginning of this paper, the authors mention privacy as the main motivation and the selling point of this paper. However, there is not explicitly definition of privacy nor the theoretical guarantee on privacy. In addition, there is a growing line of literature of differential privacy in RL, which has not been discussed in this work.\n\n3.\tThe proposed algorithm seems impossible to be implemented in practice. There are two reasons behind this. One is that the number of samples N and N_c need to grow with accuracy epsilon^-1, which will eventually blow up as the number of iterations increase. More importantly, different from existing decentralized AC algorithm that uses one transition per update (e.g., [63]), the proposed algorithms require N or N_c transitions involving global states and actions per local update. Note that different from the centralized AC and PG, in the decentralized MARL setting, unless the agent has a accurate simulator to simulate the entire MARL systems, it is not possible to obtain more than one transition per update in MARL.\n\n4.\tThe optimality gap in Theorem 2 can be very large. Specifically, there are three terms that depend on the unknown actor and critic approximation errors. Are they necessary to be in the bound? Any lower bound to justify this? Is it possible to quantify this?\n\n5.\tNumerical experiments seem very limited and not thorough enough considering the number of works published on a daily basis in this field. Specifically, only randomly generated MDPs have been tested and only one baseline [63] has been compared. Furthermore, in Theorem 2, the global convergence has been proved. It would be great to validate the optimality gap in this simulation.\n\n", "summary_of_the_paper": "This paper introduces a decentralized multi-agent actor-critic algorithm. Different from existing algorithms, the new algorithm enjoys both the privacy and the communication efficiency. \n ", "summary_of_the_review": "Two new decentralized AC algorithms have been developed with guaranteed  sample and communication complexities. However, some claims are not justified and the implementation is not realistic. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cBR7eMZCwIf", "reviewer": "Reviewer_RWPJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The sample complexity of the proposed decentralized algorithms is comparable to their single-agent state-of-the-art results.\n\n2. The decentralized NAC algorithm is probably the first one in the literature. \n\n3. Using a separate distributed averaging procedure to estimate team average policy gradient is an interesting idea to avoid sharing/broadcasting local actions. \n\nWeaknesses:\n\n1. Although the idea of using a separate distributed averaging procedure to estimate team average policy gradient is interesting, it requires additional coordination among the networked agents. The value of T' needs to be carefully designed and shared among all the agents. \n\n2. The paper claims privacy-preserving. But it reads like a immediate, lower-level privacy concern. Does it involve any qualitative support?\n\n3. The paper claims the technical challenges due to mini-batch updates. But the description at the end of Section 4 is still vague. What is the difference/novelty compared with the techniques used in \"Finite-sample analysis for decentralized batch multi-agent reinforcement learning with networked agents\" by Zhang et al. in TAC 2021?\n\n4. The proposed idea involves additional T' iterations for distributed averaging in each time step. Is it still fair to compare with the single-agent case without such inner iterations? \n\n5. Why in Table 1 (63) is marked as both private and non-private? \n\n", "summary_of_the_paper": "The paper proposes two decentralized AC algorithms, one for actor-critic and the other for natural actor-critic, which are sample and communication efficient. The paper also provides their finite time performance, which is comparable with their corresponding single-agent state-of-the-art results in sample complexity. ", "summary_of_the_review": "The paper proposes a new decentralized AC framework which combines existing decentralized techniques including distributed averaging and TD learning. The idea is interesting but not sophisticated. The NAC part is probably the first decentralized NAC algorithm. Combining existing tools may lead to new analysis challenges, which needs to be further clarified. Thus I think the paper is on the board line. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RhmJrgHPTvO", "reviewer": "Reviewer_8K9V", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1.\tIn the abstract, the authors mentioned that the proposed algorithms were developed with linear function approximation. That way, how to apply the theory to scenarios where typically deep nets are utilized?\n2.\tIn Table 1, though this paper is focused on AC type of algorithms, other decentralized algorithms, such as Q learning, value-prop, etc., should be discussed here for comparison as well. \n3.\tWhen the authors mentioned Markovian sample, would it refer to a trajectory or just one transition? If it was a trajectory, then it might be enough in practice. As a mini-batch in practice could be time-consuming for updates, though it did really reduce the variance.\n4.\tIn the proposed algorithm, each agent shares Gaussian-corrupted local reward. Then the differential privacy should be involved in this work? Also, why not sharing the parameters of actor or critic, which has been popular in decentralized optimization domain?\n5.\tThe authors only put related works together without any discussion on their advantages and disadvantages, which renders the weak motivation. I would suggest the authors discuss these in detail to provide better comparison.\n6.\tIn page 5, the authors mentioned that they could choose a large batch size to suppress the overall estimation error to the desired level. A large batch will definitely affect the accuracy and computational time in practice based on existing conclusions from the study in deep learning using large batch. Additionally, the authors cannot just always increase the size of mini-batch.\n7.\tIn Algorithm 2, extra local model averaging steps are taken. Would this cause additional communication overhead in practice?\n8.\tIn Theorem 1, $\\epsilon$ is required to satisfy a condition. Similarly in Theorem 2. Why do you need such conditions? Can you not just define it as an arbitrarily small constant as in other works? If $\\epsilon$ is too big, the optimality would be poor. For the finite-time analysis, can you not just make the step size and other constants satisfy some conditions w.r.t. time $T$ and derive the complexity? That way, typically $T$ needs to be sufficiently larger than one constant.\n9.\tIn the discussion for Theorem 1, the author mentioned that “different from the existing decentralized TD (39) that uses a single sample to update the value function parameters per communication round, we use a mini-batch of $N_c$ samples instead to significantly reduce the communication complexity of decentralized TD learning while maintaining the same level of sample complexity.” Basically existing decentralized TD algorithm uses a single sample to update the value function parameters per communication round, the authors used a mini-batch of samples to reduce the communication complexity. Why is this true? Basically, when a mini-batch of samples is used, the variance can be used. But if the authors keep the same communication frequency, the number of communication rounds remains the same. Or after the authors use the mini-batch of samples, they do multiple updates before next communication round? When the authors mentioned the same level of sample complexity, I think they should give more detail on this. As in their case, I am not very clear about what sample complexity refers to. Is it the number of data samples required for update? Or the number of gradient oracles required? Or else?\n10.\tIn the decentralized NAC, it requires to solve a quadratic programming. Would it increase the computational complexity when solving a quadratic programming problem? The approximation to the inverse Fisher information matrix looks complicated. In practice, what is computational time cost? Also, the Fisher information matrix has to be uniformly positive definite for the analysis. Such an assumption seems to be too strong.\n11.\tAfter Theorem 2, one statement is that “the result proves that the function value optimality gap asymptotically converges to the order…”. Finite-time typically corresponds to the non-asymptotic convergence, correct? If the authors require asymptotic behavior, why are those different parameters required to satisfy conditions w.r.t. $\\epsilon$? Or did I misunderstand?\n12.\tAt the bottom of Page 8, the authors mentioned that a sample budget was set in the analysis. Why is such a total sample budget constraint there? When $k$ is very large, $N_k$ will be huge. How would you implement this in practice?\n13.\tThough the experimental results make sense and sort of validate the algorithms, they are not convincing. First, the benchmark environment is too simple, only a few states with a couple actions. We have no idea how the proposed methods would perform under some popular benchmarks, such as gridworld, which has many more states. Second, more algorithms are required for comparison. It is understandable that this paper focuses significantly on the AC type of algorithms, while other existing algorithms have been proposed, and one or two of them should be used for the comparison. Third, for decentralized algorithms, different topologies are critical to be shown for demonstrate the effectiveness.\n14.\tIn this paper, the authors used partial policy gradient. Why not directly using local policy gradient? The authors also mentioned that “…to obtain an accurate estimation, the network needs to have a sufficiently large number of agents, which can be unrealistic in practice.” But typically in practice, this can happen and remains a challenge. How to scale decentralized algorithms to large networks?\n15.\tWhat is $(\\{s_t\\})_t$ in page 5?\n\n****************************************\nI really appreciate the detailed responses from the authors and they did address some confusions regarding the theoretical analysis. More experimental results also provided better validation for the proposed algorithms. However, there are still some confusions in the revised draft. For example, in Table 1, why is the sample complexity for paper (54) much much larger than others? If $\\epsilon = 0.001$, then the complexity is completely intractable. I checked the paper and don't think the complexity given in the Table 1 for paper (54) is correct. Additionally, after carefully reviewing comments from other reviewers, I decided to keep the score and believe with some more work, the paper will be technically solid and sound and a nice publication.", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall, I think the current form of the paper still requires substantial work to make it technically solid and sound. In particular, the numerical results are not very convincing, and there are numerous confusions in the analysis, which have weakened the theoretical contributions. I hope my comments can help out.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While authors have updated the draft to address reviewers' concerns, some parts are still not clear enough and the presentation needs further improvements. I encourage authors to revise the draft accordingly and resubmit in the future venues.
Decision: Reject