Taming Communication and Sample Complexities in Decentralized Policy Evaluation for Cooperative Multi-Agent Reinforcement Learning
Authors: Xin Zhang
Zhuqing Liu
Jia Liu
Zhengyuan Zhu
Songtao Lu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Decentralized Mini-max Optimization
Variance Reduction
Nonlinear Function Approximation
Policy Evaluation

Abstract: Cooperative multi-agent reinforcement learning (MARL) has received increasing attention in recent years and has found many scientific and engineering applications. However, a key challenge arising from many cooperative MARL algorithm designs (e.g., the actor-critic framework) is the policy evaluation problem, which can only be conducted in a {\em decentralized} fashion. In this paper, we focus on decentralized MARL policy evaluation with nonlinear function approximation, which is often seen in deep MARL. We first show that the empirical decentralized MARL policy evaluation problem can be reformulated as a decentralized nonconvex-strongly-concave minimax saddle point problem. We then develop a decentralized gradient-based descent ascent algorithm called GT-GDA that enjoys a convergence rate of $\mathcal{O}(1/T)$. To further reduce the sample complexity, we propose two decentralized stochastic optimization algorithms called GT-SRVR and GT-SRVRI, which enhance GT-GDA by variance reduction techniques. We show that all algorithms all enjoy an $\mathcal{O}(1/T)$ convergence rate to a stationary point of the reformulated minimax problem. Moreover, the fast convergence rates of GT-SRVR and GT-SRVRI imply $\mathcal{O}(\epsilon^{-2})$ communication complexity and $\mathcal{O}(m\sqrt{n}\epsilon^{-2})$ sample complexity, where $m$ is the number of agents and $n$ is the length of trajectories. To our knowledge, this paper is the first work that achieves both $\mathcal{O}(\epsilon^{-2})$ sample complexity and $\mathcal{O}(\epsilon^{-2})$ communication complexity in decentralized policy evaluation for cooperative MARL. Our extensive experiments also corroborate the theoretical performance of our proposed decentralized policy evaluation algorithms.

Taming Communication and Sample Complexities in Decentralized Policy Evaluation for Cooperative Multi-A Aent Reinforcement Learning
Xin Zhang* Dept. of Statistics Iowa State University
Zhuqing Liu" Dept. of ECE
Jia Liu Dept. of ECE The Ohio State University Columbus, OH, 43210 liußece. osu. edu
The Ohio State University Columbus, OH, 43210 1iu. Elu.93848osu.com edu
Ames, IA 50010
Ainzhang@iastatee.cm edu
Zhengyuan Zhu Dept. of Statistics Iowa State University Ames, IA 50010 zhuz@iastate edu
Songtao Lu IBM Research AI
IBM Thomas J. Watson Research Center Yorktown Heights, NY 10598 songtaol ilmm com
Abstract
Cooperative multi-agent reinforcement learning (MARL) has received increasing attention recent years and has found many scientific and engineering applica- tions. However, a key challenge arising from many cooperative MARL algorithm designs (e.g., the actor-critic framework) is the policy evaluation problem, which can only be conducted in a decentralized fashion. In this paper, we focus on decentralized MARL policy evaluation with nonlinear function approximation, which is often seen in deep MARL. We first show that the empirical decentral- ized MARL policy evaluation problem can be reformulated as decentralized donconvex-strongly-cooee
minimax saddle point problem. We then develop a decentralized gradient-bas based descent ascent algorithm called GT-GDA that enjoys convergence rate of O1/TT). To further reduce the sample complexity, pose two decentralized stochastic optimization algorithms called GT-SRVR and GT-SRVRI, which enhance GT-GDA by variance reduction techniques. We show that all algorithms all enjoy an (1/TT) convergence rate to a stationary point of the reformulated minimax problem. Moreover, the fast convergence rates of GT-SRVR and GT-SRVRI imply O(e-2) communication complexity and Omn ple complexity, where m the number of agents and n is the length of trajectories. To our knowledge, this paper is the first work that achieves (c--2) in both sample and communication complexities in decentralized policy evaluation for cooperative MARL. Our extensive experiments also corroborate the theoretical results of our proposed decentralized policy evaluation algorithms.
pro-
sam-
Introduction
In recent years, multi ageett reinforcement learning (MARL) has found important applications in many scientific and engineering fields, such as robotic network [45, 22, 41], sensor network [6, 40, 43], and power network [5. 11. 15, 16]. just to name a few. In MARL, multiple agents observe the current joint state over a network, perform their own actions based on the current state, and transition to
Xin Zhang and Zhuqing Liu contributed equally to this work.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the next joint state. Each agent can only observe its local reward, which is function of the joint state and actions. One important paradigm MARL is the cooperative MARL, where the agents share a common goal to find an optimal global policy to achieve the maximum global accumulative reward [63, 62, 13, 37]. As classical reinforcement learning (RL. problems, key component in cooperative MARL algorithms is the policy evaluation (PE) problem, whose goal is to evaluate the expected long-term accumulative reward for a given global policy. In cooperative MARL, agents share common value function based on the joint states. As a result, the parameterization of the value function is the same across all agents. Examples of cooperative MARL include but are not limited to traffic light control [56], autonomous driving [21]. financial trading [26]). etc. In cooperative MARL, the PE problem emerges as a key step for the agents to find an optimal global policy in MARL tasks [3, 23]. For example, in the actor-critic algorithmic framework for MARL, the actors conduct the policy improvement step, while the critics perform the policy evaluation step and estimates the value function. The overall actor-critic algorithm tries to find an optimal policy by iterating between the policy evaluation and improvement steps. Thus, developing efficient policy evaluation algorithms is critical to the success of RL algorithms based the actor-critic framework.
However, developing efficient PE algorithms for MARL is highly non-trivial. On one hand, the global accumulative reward is not directly observable in an MARL system. As a result, the PE problem of MARL can only be solved in a decentralized fahsion. On the other hand, modern MARL tasks have been increasingly complex and often not directly computable. As result, MARL often use highly nonlinear parametric models (c.g., deep neural network (DNN)) for policy approximation. In this paper, we focus on PE based nonlinear function approximations due to the following reasons: 1) linear approximation schemes are based on their pre-defined basis space, which may not be able to approximate the non-linear value function with high accuracy; 2) non-linear neural network approximation can handle the cases where the states space that is mixed with continuous and (infinite) discrete state values; and 3) nonlinear neural network approximation usually have better generalization performance than linear approximation [61]. [20], [60]. However, it has been shown that the convergence performance of RL algorithms with nonlinear function approximations is not guaranteed [49].
In light of the growing importance of MARL, in this paper, focus addressing the above challenges. The key contributions of this paper are summarized as follows:
To our knowledge, this work is the first to investigate the decentralized PE (DPE) problem for MARL with nonlinear function approximations. Via the Fenchel's duality and local reward decomposition, first reformulate the DPE problem of MARI. as decentralized non-convex- strongly-concave minimax saddle point problem. To solve the minimax problem in a decentralized fashion, we propose a trackinnntttakkkig---- show that GT-GDA enjoys a convergence rate of (1/T"), which leads to an O(mon -2 sample complexity and an O(e 2 communication complexity, where m is the number of agents, n is the data size, and is the convergence accuracy.
gradient descent-ascent (GT-GDA) algorithm. We
To further reduce the sample complexity, we develop two variance- algorithms, namely gradient-tracking stochastic recursive variance reduction (GT-SRVR) algorithm and its variant with incremental batch size (GT-SRVRI). We show that both algorithms achieve the same commu- nication complexity O ) as GT-GDA, but requiring a lower sample complexity O(m / -2).
It is worth noting that, in our theoretical analysis, we relax the commonly conditions of the feasible set with some mild assumptions objectives. Thus, the solutions found by our algorithms are exactly the stationary points for the original policy evaluation problem. This result may be of independent interest for general RL problems.
compactness
The rest of the paper is organized as follows. In Section 2, we first provide the preliminaries of the DPE problem of MARL and discuss related works. In Section 3, first introduce the GT-GDA algorithm, and then propose two stochastic variance reduced algorithms, namely GT-SRVR and GT-SRVRI. We present their theoretical properties in Section 4. Section provides numerical results to verify our theoretical findings, and Section 6 concludes this paper.
Problem formulation and related work
In this section, we first introduce the DPE problem formulation in in Section 2.1. Then in Section 2.2, we review the recent developments of PE algorithms and compare them with our work. In Sec-
2

---

tion 2.3, we highlight the challenges in designing efficient DPE algorithms with nonlinear function approximation and the significance of our work.
2.1 Problem formulation of deventralized policy evaluation for MARL
Consider a multi-agent network system G = (N, where W and C denote the sets of agents and edges, respectively, with [M] = m. In the system, the agents cooperatively perform a learning task. The agents can communicate with each other through edges in L. An MARL problem is formulated based on the multi-agent Markov decision process (MDP) framework, which is characterized by a quintuple A, sw's {R, (s. a) S), where S and A are the state and action spaces, respectively; s E S and a E A are joint state and action: P is the transition probability from state s to state s' after taking action a: (s, a) is the local reward received by agent i after taking action in state and Ç E (0, 1) is a discount factor. Both the joint state S and action a are available to all agents, while the local reward R, is private to agent i. In multi-agent system, the global reward function is defined as the average of the local rewards D{= (s, a). Moreover, a joint policy π specifies sequential decision rules for all agents. Policy 'T ((a ()) is the conditional probability of taking joint action given state s. The goal of PE is to estimate the value function of a given policy π,, which is defined as the long-term discounted accumulative reward: (*n)s) E m E S -=== (st, ar) [So, "T.
where the expectation is taken over all possible state-action trajectories and initial states.
To determine (-), one of the most effective methods is the rithm, which focuses on solving the Bellman equation for V (.): -(s))(=>>VV) - Σ (s)++
(TD) learning algo-
Eves P where T denotes the Bellman operator, (T) = (--la( R(s, a) andP
Rawx(1ss Pas sx However, P is unknown in MARI. and the size of the state space could be infinite. To address this challenge, a widely adopted approach to approximate (*(-) by a function V-(() parameterized by 0 E RP. According to the formulation in [38, 50, 10, 9, 30], the Bellman equation can be solved by minimizing the following mean-squared projected bell-
man eтror (MSPBE): MSPBE(() & =||"e--a-(TTVVea
- Vo) (e)a(s) T]
K where K =
Bynds VoVo(s)VoVo(s)] E RPXP and d= is the stationary distribution of the MDP under policy From the Fenchel's duality ||x|] -1 maXyERs y(x,y) - Ay, we can reformulate the MSPBE minimization problem as the following primal-dual minimax problem:
1 _ (VoVo(s)VolV(())) Jw], min max L(0, w) A E[(6 VoVo(s). - 2
(1)
PERP weRn
where the expectation is taken over s (') T-1ss) s' ~ Pa and 5 = E (Vo(s')= - (s).). In practice, we only have access to a finite dataset with n-step trajectories D = { (ss, a,, (s,, sample average, we have the following empirical minimax problem:
By replacing the unknown expectation with the finite
1
1 Kow.
min max F(O, w)
(ò, VoVo(s)). w) - 2
(2)
OER WERF
where 5, 1 E (s,,, a.) + (Vo(5)11) Vs(s:) and K. A EE VoVo(s))
In this paper, we assume that both Kg and its empirical estimate Ko are positive definite for all 0. Define J(0)= a F(O, w-) = max F(O, w), where w* = arg maxwERr F(0,w). J(0) can be viewed as the finite empirical version of MSPBE. Here, we aim to minimize J(0) by finding a stationary point of F(O, w). Recall that in MARL, the local reward only observable for each indi- vidual agent. Thus, it is hard to obtain the global reward 1 m i-1 R,(s,, ar) and 8, in a multi-agent Vo(ss) and decom- pose the minimax problem in (2) as follows: mingER. max F(O, w) = - DT F((O.w) = w) 1w (VoVo(s) VoVo(s:)
network. To address this challenge, we define d,,, = R. (S., a.) ) + +(Vo()++1)
1 Σm E fi((e (f, w) where (a w) A We call this step as local reward decomposition. In cooperative MARL, key challenge is that the PE problem in (2) has to be solved in a decentralized fashion, which is due to the fact that i) the locally observed rewards are private and cannot be shared with the other agents/central server; ii) is difficult to set up central sever in many MARL applications while decentralized setting is more flexible (e.g., wireless network [59], UAV network [7]); and iii) the central server is vulnerable to cyber-attacks and would be a significant communication bottleneck [57], [27]. To solve Problem (2)
3

---

in decentralized fashion, we can rewrite it in the following equivalent form:
Σ Pi w.) 1 m n am
m
min m
max
fa (i),,,,,
m
t=1 mn
subject to 0, - = Wj. ((i,)))
(3)
where 0, and Wi are the local copies of the original primal-dual parameters at agent i. In (3), the equality constraint ensures that the local copies at all nodes are equal to each other, so the formulation also referred as the "consensus form."
Clearly, Problems (2) and (3) are equivalent. For a fixed 0, each local function F; (; .) is a strongly concave function of w. For fixed w, F.(; w) is a non-convex function of 0. Thus, Problem (3) is minimax consensus optimization problem. In this paper, we adopt two complexity metrics that are widely used in the decentralized optimization literature (e.g., [47]) to measure the efficiency of an algorithm:
decentralized wi--convee-ttronlyy-cocca
Definition (Sample Complexity). The sample complexity is defined as the total number of incre- mental first-order oracle (IFO) calls required across all nodes until algorithm converges, where one IFO call evaluates a pair of (fie(0,w) V fie(O, w)) at node i.
Definition (Communication Complexity). The communication complexity is defined as the total rounds of communications required until algorithum converges, where each node can send and receive a p-dimensional vector with its neighboring nodes in one communication round.
2.2 Related work on policy evaluation
1) The tabular approach:
The study of MARL under the MDP formulation traces its roots to the seminal work by [29]. Motivated by this formalization, several methods have been developed to solve and analyze MARL problems, including [24, 54, 17, 11, etc. However, most of these early works approximate the value function in tabular form, which only works for cases where the state and action spaces are relatively small. For complex MARL tasks where the state space is large or even infinite, the tabular approach becomes intractable.
2) Policy evaluation with linear function approximation: To address limitation in tabular ap- proaches for MARL, the work in [25] proposed to estimate the value function with a linear approx- imation (i.e., V(s) (ss) 0, 0 R". where & S - Rº is a feature mapping) and developed distributed gradient temporal-differen
(DGTD) algorithm. However, this work only considered asymptotic convergence analysis and required diminishing step-sizes ensure convergence. In [12), the authors proposed a distributed homotopy primal-dual algorithm (DHPD) for the PE problem in MARL. They also cast MSPBE minimization
stochastic primal-dual optimization problem, where the objective is convex in primal and strongly-concave in dual. By using an adaptive restarting scheme, DHPD achieves an (1/TT) convergence rate in finding stationary points. The work in [13] developed a distributed consensus-basee TD(0) algorithm, which integrates the network consensus step and local TD(0) updates. They provided smite-time analysis and showed a convergence rate of O(/TT). To further improve convergence, the work in [51] proposed primal-dual distributed incremental aggregated gradient (PD-DistIAG) method to integrate gradient-tracking and incremental aggregated gradient methods to achieve linear convergence. However, major limitation of the linear approximation approach is that it is not applicable for nonlinear MARL models (e.g., DNN).
3) Policy evaluation with nonlinear function approximation (single-agent): In the literature, PE with nonlinear approximation is by far only limited to single-agent RL. For policy evaluation, linear and nonlinear approximation approaches differ fundamentally in the following aspects. Under linear approximation for policy evaluation, the problem boils down finding a solution for a linear equation system, which is in essence similar to solving relatively easy strongly-convex optimization problem [14], [52]. [48], [46]. In stark contrast, under non-line non-linear approximation for policy evaluation, the problem possesses a non-convex convex-strongly-come
structure, and it is far more challenging to find a saddle point solution. To our knowledge, the work in [4] was the first to study the PE problem with nonlinear approximations and developed a nonlinear TD algorithm. However, the proposed algorithms adopted wwo-timescale step step-sizes?, resulting in slow convergence performance. Recently, the work
A primal- primal-dual algorithm is a two to-timesealee if y//n + 0 or 7//m + oc as + co. where 7 and 1): denote the primal and dual step-sizes time t, respectively.
4

---

Table 1: Comparisons among existing policy evaluation algorithms, where m is the number of agents; n is the size of dataset; 2² is the convergence error. Our proposed algorithms are marked in bold.
Decentralized Multi Agett
Nonlinear Approxi.
Convex Sets
Sample Complex.
Commun.
Algorithm
Reference
Complex.
STSG
X
O O
[42]
ASTSG
X
DHPD
[12]
V
X
/
Omne
Ole F)
PD-DistlAG
[51]
V
X
X
Om log
Olloge
APP-SAG
[44]
X
X
(m log e
Ologe
DTDT
[53]
X
X
O mm log
Ologg
GT-GDA
Theorem
X
O(mne ")
O(e
GT-SRVR
Theorem 3
/ X
Omm
O
GT-SRVRI
Theorem 4
The feasible parameter spaces are required to closed convex sets.
in [50] showed that PE with nonlinear approximation in RL is equivalemt to a non-convex-stronge concave minimax optimization problem. To find stationary point for such minimax problem, they proposed a non-convex primal-dual gradient with variance reduced (nPD-VR algorithm. However, their algorithm requires (11/m) step-size, where is the size of the dataset. This is problematic in cases with a large transition dataset. More recently, the authors of [42] proposed two single-time minimax optimization. These two algorithms utilized stochastic gradient with momentum and variance-reduced momentum [8], and achieved (1/vV)) and O (1//7//3) convergence rates, respectively. However, diminishing step-sizes are required in these two algorithms, which do not work well in practice.
scale first-order stochastic algorithms for the nonconvex- wetpreee-sstoooyyyoeeeee
minimax optimization: As men- tioned earlier, the PE problem of cooperative MARL can be reformulated as non-convex-stronggl concave optimization (NCSC) problem (see details in Problem (2). Thus, our work is also closely related to the area of decentralized NCSC minimax optimization. To efficiently solve the decentral- ized minimax problem in Problem (2), our proposed algorithms are primal-dual-ben based algorithms, where we update the two variables simultaneously rather than alternatively. Thus, our proposed algorithms are much simpler and significantly different from existing related works that require to solve maximization subproblem for dual variable in each iteration [36]. Further, we propose "hybrid" scheme that non-trivially integrates variance reduction and gradient tracking techniques for both primal and dual variables. Compared with algorithms in [31].[32], with simple stochastic gradient updates and variable mixing, our proposed scheme enjoys much improved theoretical and numerical performances. Also, we note that the theoretical analysis of the more sophisticated hybrid scheme in the PE problem of cooperative MARL is more involved compared to existing works and necessitates new proof techniques.
4) Relations with decentralized nonconnee--ttronglycoom
2.3 Significance of our work and challenges of DPE with nonlinear function approximation
To our knowledge, our work is the first to solve the DPE problem with nonlinear function approxi- mation for MARL. However, such nonlinear approximation imposes several significant challenges on algorithm development and analysis. As discussed in Section 2.1, we propose reformulate the minimax optimization problem. In the
DPE problem as a decentralized nonconvex-strongly literature, although a few works [32, 31, 34] have studied similar decentralized minimax problem, their variable updates rely on either stochastic or full gradients, which are not sample/communication.. efficient for MARL. To address these limitations, we first propose two decentralized variance-reduced algorithms for solving the sonconve--ttronlyycoom the convergence rates is highly challenging. Second, we adopt the gradient tracking (GT) technique to reduce network consensus eтror. Under nonlinear function approximation, our algorithms need to track the gradients for both primal and dual variables. However, such "double gradient tracking" intro- duces new constraints on algorithm design. Third, many of the existing nonconvex serconvee-stronglyy strongly-concav minimax optimization methods (e.g. [42, 50)) require prior knowledge of the compact domain of model variables, which cannot be assumed in DPE for MARL. Such unboundedness in DPE creates new challenges and necessitates new proof techniques our algorithm analysis. To conclude this section, we summarize all related work in Table 1.
DPE minimax problem, for which establishing
5

---

Algorithm 1 GT-GDA Algorithm at Agent i.
1: Set prime-dual parameter pair (0,.o, Wr.0) = (0, w
2: Calculate local gradients as Ps, = Voli(O Wo,)), and d = Vw.i Wi,);
3: for t = 1,...... T do
4: Update local parameters (0,,41, w as in (6):
5: Calculate local gradients (Vi,++1, (1 as in (4);
6: Track global gradients (Pi,+1,, dee+1) as in (5);
7: end for
3 Gradient-tracking gradient descent ascent algorithm.
In this section, we first present a gradient-tracking gradient descent ascent (GT-GDA) method for solving the DPE problem in (3) for MARL, and then provide the its theoretical results.
1) The Algorithm:
For the consensus problem in (3), popular approach is let agents aggregate
their neighbor information through a consensus weight matrix M E Rm [39, 51]. Let M]
denote the element in the i-th row and the j-th column in M. M satisfies the following properties:
(a) Doubly stochastic: >x
Ziil [M]ú = >' -j [M]i = 1; (b) Symmetric:
m
[M];j [M] Vi, E W;
and (c) Network- Deefnned Sparsity: MM > 0 Of (i.j) E L; otherwise [M] = 0, Vi,j E W. The
above properties imply that the eigenvalues of M are real and can sorted as -1 < (M) S
1. We define the second-largest eigenvalue in magnitude of M as A max max[[A2(M) Am (M)] Our GT-GDA algorithm for each agent i is illustrated in Algorithm 1. Specifically, at the 1-th iteration, agent i first calculates the local full gradients as follows:
S >²(M) < X1 (M)
Vs. = FoF((O.,)) W,,),, u,t = V (e Wi,))
(4)
Note that Va, and UgSt only contain the gradient information of the local objective function F w). Thus, merely updating with vi, and u,, cannot guarantee the convergence of the global objective function F00 w). To address this challenge, we introduce two auxiliary variables, p and d The agent updates the two variables by performing the following local weighted aggregation:
Pi. Σ [M] + ViD Vic--1, d., Σ M + i U11-1 (5) JEN:
JEN.
where NG A (j E W,: (1,5) E L) denotes the set of agent i's neighbors. Technically, pa. and di track the directions of global gradients. With some derivations, it can be shown that
EiEN Sr. p EiEN (eFi(0,ee ws.e) and Eiev di,== (. wt.)). Lastly, each agent updates local parameters following the conventional decentralized gradient descent and ascent steps:
0,++1= = Σ MM - PPi,, Wi++==
Σ [M]j + r/d..
JEN,
JEN.
where the constants ? and 17 are the step-sizes for individual primal and dual variables, respectively.
2) Theoretical Results of GT-GDA: In this section, we will establish the convergence behaviors of the proposed GT-GDA algorithm. Toward this end, we first state several assumptions as follows: Assumption 1. The function F(6,
Em F((0,w) w) and J(Ø) = max F(O, w) satisfy:
(a) (Boundness from Below): There exists a finite lower bound J info J(0) -os;
(b) (Lipschitz Smoothness): Local objective function (, .) is Lipiscchtt biiipschittsmmoohh..
smooth. i.e., there exists a positive constant LF such that the gradient F. w) = ( w) F.F, w) TJT satisfies F w) FV, w/)ll 2
w II, V2, 0' w,w' E RP, i E [m]:
(c) (Strong Concavity in Dual): Local objective function F.(O.-) -) is p--ttrongly concave for fixed a positive constant μ. such that F, F.O. (10..") vl|w-w'll,' 0, w, w/ ERPPiE, [m]
O E IRP, i.e., there exists
(d) (Bounded Dual Maximizer): For any primal variable RP, its associated dual maximizer
w0) a arg maX F(O,w w) is bounded, i.e., (0)]|<<
(e) (Bounded Gradient at Maximum): The partial derivative maximum point V ((0, (0) is bounded, i.e., o w" (0)) < 00, V0 R..

---

In these assumptions, (a) and (b) are standard in literature. It can be verified that (c) holds when Ke is positive definite; (d)-(e) guarantee that VJ(0) VoF w (0)) (see Lemma 10 in the supplementary material). Note that most of the existing works [28, 42] adopt the compactness assumption ensure such gradient equivalence. The compactness assumption restricts the feasible parameter space as a closed convex set. Although we also make these boundedness assumptions, the convergence performance of our algorithm is independent of the upper bound of ([w"()) and || ((, w" (0)) To quantify the convergence rate, we propose to use the following new metric, which is the key the success of establishing all convergence results in this paper:
2n, [|V - well
m Σ (110,, (100,,-0.11 0.1l 1 We 11²);
where W denotes w/ w0,) = arg max F(Or, w. The first term in (7) measures the convergence indicates that O, first-order stationary point for J()). The second term in (7) measures W, 's convergence to the unique maximizer w for F(O,, -. The last term in (7) is the average consensus error of local copies. Thus, as Mr + reaches consensus first-order stationary point of the original MSPBE problem. In comparison, the single-agent PE problem [42] does not have the last four consensus eгrоr terms over multi-agent and so it is dramatically different from our DPE problem. Also, for the linear approximation PE problem in [51], the first term is replaced with 0, 0* I| as it can viewed as a strongly convex optimization, while the other terms are the same. Based on the metric in (7), we have the following:
of primal variable 0: [0,
have that the algorithm
Theorem 1 (Convergence of GT-GDA). Under Assumption I, if the step-sizes satisfy that _ 2n/n" S jtt / and 17 I min(k1, k2, 12, ka, ka), then GT-GDA has the following convergence result:
T
2E -J
S min (T+1)
T+I
where B. is a potential function defined as:
SyL2 Bi L [(,))
|
w
112 1
M 10
-d.1?,
μm)
and the constants in the step-size are as follows:
13L3 kj 2/12
L3
13L7 (1 (1- k2 12 1/1111111111 2)))
(1 (1- A) 6p + 1/K)
LF
ha
/
26(1 L3.
h4
(122 + 144L$ + 4L + 18
Remark 1. In Theorem 1, the step-sizes and convergence rate depend on by the network topology. For a sparse network, À is close to (but not exactly) one (recall that = max{[A2l, |mm < 1). Therefore, k2 and 1; are close to zero in this case. Also, the ratio of the step-sizes λ - r/n is required to be non-zero constant. Either too small or too large value of might affect the primal or dual convergence of the algorithm. This restriction is due to the consensus error in the decentralized training. In practice, one can first determine and then select 7) and 7.
From Theorem 1, we immediately have the following complexity results for GT-GDA:
Corollary 2. Under the same conditions in Theorem 1, to achieve an -tatiionny solution, i.e.. T+i
1 II E[M, I è, the total communication rounds are on the order of O( and the total
samples evaluated across the network system is on the order of O(mne"
4 Gradient-tracking stochastic variance reduction algorithms
In the GT-GDA algorithm, agents need to evaluate local full gradients in each iteration, which may result in high sample complexity when the trajectory length is large in MARL. This limitation motivates us to leverage the stochastic recursive variance-reduce approach (e.g., [55]) to achieve low sample complexity in MARL decentralized policy evaluation.
7

---

Algorithm 2 GT-SRV//GT-SRVVR Algorithm at Agent i.
If GT-SRVR: n |S,, qq; If GT-SRRR:: R ( ///111/gg.... q, C.e 2 ,,), S1,,1 q. 1: Set prime-dual parameter pair (0 Wa,u) = (0) w²).
2: Draw Ri,0 samples without replacement and calculate local stochastic gradient estimators as
Pt, V2,0
RR. -. JER Volij (O.0, wio)), and d. 0 TR. V w (00,0 wa,o);
3: for ( 1, , do
4: Update local parameters (0.,4+ Wi,e-1 in (6);
5: Calculate local gradient estimators (Vi,441, 0g,++1) as in (8);
6: Track global gradients (Ps,c+1; (P..+1,d..44)) as in (5);
7:
end for
1) The Algorithms: We first propose algorithm called gradient-tracking stochastic recursive variance reduction (GT-SRVR) algorithm. Different from GT-GDA, in iteration t and at agent i, GT-SRVR estimates the local gradient with the following estimators:
VoPi(O0,; wi.); Vi,+i [S Ejes,, (Vofi (O,,,, (0..)(00.1,,,,111 otherwise,
if mod(!, v) = 0,
Vir
(8a)
V Fi wi))), u [s.,] Ejes., (V (0,,, -i, w (0..-1, otherwise, (8b)
if mod(t, g) = 0.
where S is local subsample at the tth iteration for agent i. In (8), the algorithm evaluates full gradients V (O,,, ws,e) only every q steps. For other iterations with mod(t, q) # O, the algorithm estimates the local gradients with a
of gradients [S,a Ejes,, Vwffi ws,)) and a recursive correction term 1 [St.a] EjEs, fi (0..,, ((,--) It will be shown later that, thanks to the periodic full gradient (when mod q) = 0) and recursive correction term, GT-SRVR is able to achieve the same convergence rate and communication complexity as GT-GDA. Moreover, because of the Sr subsampling, GT-SRVR has a lower sample complexity than GT-GDA. The full description of GT-SRVR is shown in Algorithm 2.
Note that in GT-SRVR, full gradients are still required for every g steps, which may still incur a high computational cost. Also, in the initialization phase (before the main loop), agents need to evaluate full gradients, which could be time-consuming To address these limitations, we propose an enhanced version of GT-SRVR called GT-SRVR with Incremental batch size (GT-SRVRI). Specifically, we modify the gradient estimators in (8a) and (8b) for the ith iteration with mod(t, q) = 0 as follows:
1 (ilis(Onr Wi.))
Volcs w.,)), U Ricl RiAAIERR.. JER.,
Vi,t
Rinh JER.,.
where R.,, is a subsample set (sampling without replacement), whose size chosen as RRal = min((t// (t/q 1)"q,.c." 2 2, nn.. Here, a 0 is a constant, is desired convergence error, and c, is constant that depends on e. Our design of [R,, is motivated by the fact that the periodic full gradient evaluation only plays an important role in the later stage of the convergence process for achieving high accuracy. Later, we will see that under some mild assumptions and parameter settings, GT-SRVRI has similar convergence performance as GT-SRVR. The full description of CT-SSRVR/GT-SRVRI is shown in Algorithm 2.
Remark 2. In GT-SRVRI, we increase the batch-size as the number of iterations increases. We note that the work in [18] also proposed batch-size adaptation scheme based on the historical gradient information. Although similar idea can be also adopted in our algorithms, requires the exact value of the stochastic gradient variance o² for batch-size selection as well as extra memory cost to store the -astory-gradient information, which is less practical compared to our approach.
2) Theoretical Results of GT-SRVR/GT-SRRR. Now, we establish the convergence performance of GT-SRVR/GT-SRVRRL First, we replace Assumption 1(b) with the following individual Lipschitz smoothness assumption:
Assumption 2 (Lipschitz smoothness). The function fay (0. is Ly-Lipschitz smonth iee. there exists
constant L5 > 0, such that the gradient V fi, (0, w) VV @ WI (ufa((0, w)TTT satisfies
|V fi w) v fiy (0', w w2)ll 13
+ L3
o' w. w Rd 2 [m], [n].
8

---

We note that Assumption 2 is a common assumption for stochastic variance reduced methods [55, 47, 42]. Further, we make the following assumption only for GT-SRVRI algorithm: Assumption& 3 (Bounded Variance). There exists constant o² 0, such that E| V (., VP,(O, w)ll v o², V 0, w, E i E [m] j E [n).
With the metric in (7), the convergence of GT-SRVR/GT-SRVR can be characterized as follows: Theorem (Convergence of GT-SRVR), Under Assumption (a)((c))()) and Assumption 2, if the step-sizes satisfy 7/n S 1²/1313 and vj S min(ks, Kar Kr, hig}, then we have the following convergence result for GT-SRVR:
1
2 2TE J min (ein(1, (1, LT) 1)7
E
T+L
where Pt the potential function defined as:
L
pr ((,)+
|00
w 11
Σ
- -Pl -d, d2
pmj
and the constants in the step-size are:
1
1
18L3
13L;
Co =
Ks
K6 8uCo'
2
122
112
(1/2 + 1/(1 - 1)3)
26(1 - 1)13
1317
12
kg
L, + 4
+ + (1-
(n22 + 144L, + 14447
4L332² + 64G)L))22)
2n22
Theorem (Convergence of GT-SRVRI). Under Assumption I (a)&(c)ee), Assumption 2, and the same parameter settings and potential function stated in Theorem have the following convergence result for GT-SRVRI:
2Eppo -PrH]
+
T+1
min
b0
(1+ )+4+
12 (1+
1441.
o²2
d'C(n,q,a) (10)
112 Ce
T+1
where the constant C(n, q, oi) is defined as:
H. (m) Laa if a> and a+1
C(n, g, ())
+1, if o=
In Theorems 3 and 4, it can seen that the step-sizes and convergence performance depend on the network topology and the ratio of the step-sizes n. Additionally, the convergence performance GT-SRVRI is affected by the constant C'n,, g. a),, which depends on the inexact gradient estimation in /th iteration with mod(l, q) O.
Remark 3.
Following from Theorems and 4, immediately have the sample and communication complexity results for GT-SRVRIGT-SRYY
Corollary 5. Under the conditions in Theorems 3 and 4, and with q vn. to achieve e-
stationary solution (i.e., T4 ET L
E[M]] < e?) with /nc² < 1, we have:
for GT-SRVR, the total communication rounds are ( and the total samples evaluated across the network are (mm/nie-)) -));
GT-SRVRI with a Z 1, the total communication rounds are bounded by O(log( ([log(/n)e"> and the total samples evaluated across the network are bounded by O(m logí /1) 2))-
Remark 4. From Corollary 5, we can see that GT-SRVR has the same communication complexity as GT-GDA, but the sample complexity is lower than GT-GDA. For GT-SRVRI with a 2 1, the upper bounds of both the complexities have an additional factor log( /n) factor compared with GT- SRVR. Although the theoretical complexity bounds for GT-SRVRI is weaker than GT-SRVR (due to abandoning full gradients completely), we show through experiments Section 5 that GT-SRVRI empirically outperforms than GT-SRVR in practice.

---

19
08
38
166)
507
10
((8)
OPSEA
D50BA
0T-00A
Sample complesity
round
ration
(a) MSPBE value sam- (b) Convergence metric
(c) [MSPBE value vs. (d) Convergence metric
ple complexity.
vs. sample complexity. comm. complexity.
vs. comm. complexity.
Figure I: MARL decentralized policy evaluation performance comparison.
Experimental Results
In this section, demonstrate the performance of our proposed GT-GDA and GT-SRVR/GT-SRVRR algorithms for cooperative MARL decentralized policy evaluation. We adopt the environment of Cooperative Navigation task in [33], which consists of m agents inhabiting two-dimensional world with continuous space and discrete time. In the system, agents cooperate with each other to reach their own landmarks. Due to space limitation, the detailed experimental settings and different network topologies are relegated to the supplementary material.
Since there is existing work in the literature solving decentralized policy evaluation with nonlinear function approximation for MARL, we compare our algorithms with two stochastic algorithms simple baselines in experiments: 1) Decentralized Stochastic Gradient Descent Ascent (DSGDA) and 2) Gradient-Tracke Tracking- -aased Stochastic Gradient Descent Ascent (GT-SGDA) (see the supplementary material for their detailed definitions). We initialize the parameters from the normal distribution for all the algorithms. The learning rates is fixed as = 10-1,1 10-1
From Figure ((a) and 1(b), it can be that GT-SRVRI converges much faster than other algorithms (GT-GDA, GT-SRVR, GT-SGD and DSGD) in terms of the total number of gradient evaluations. We can also observe that both GT-SRVR and GT-SRVRI have better sample efficiency in attaining high accuracy (error smaller than 10 10-9) than the other three algorithms thanks to the variance- reduced techniques. As is shown in Figure I(c) and (d)) GT-SRVR and GT-SRVRI have the same communication cost as GT-GDA, which is much lower than those of DSGDA and GT-SGDA. Our experimental results confirm our theoretical analysis that GT-SRVR/GT-SRVR enjoy low sample and communication complexities.
6 Conclusion
In this paper, we studied the decentralized MARL policy evaluation problem with nonlinear function approximation. We first reformulated the problem as decentralized non-convex-stronge strongly-cooncvee minimax problem and developed a gradient tracking based algorithm called GT-GDA. We showed that GT-GDA algorithm has the communication complexity of ((--2) and sample complexity of O(mne-2) To further reduce the sample complexity while maintaining the communication complexity, we proposed two stochastic variance-reduced methods called GT-SRVR and GT-SRVRI, both of which can achieve the same communication complexity as GT-GDA but improve the sample complexity to (mn -)). We have also conducted extensive numerical studies to verify the performance our proposed algorithms. We note that our work opens up several interesting direction mechanisms further
for future research. First, It is interesting to adopt communication-effinn reduce the communication cost, especially when the parameters are nigh-dimensional. Second, is also interesting to study MARL problems with partially observable information. Lastly, decentralized MARL policy evaluation with non-linear approximation with Markovian online sampling remains an important open problem, which is worth further investigation.
Acknowledgments and Disclosure of Funding
This work has been supported in part by NSF grants CAREER CNS-21 10259, CN5-21 CNS-2102233, CCF-2110252 ECCS-2140277, 199-C4CF-193488 and Google Faculty Research Award.
10

---

References
[1] Gürdal Arslan and Serdar Yüksel. Decentralized q-learning for stochastic teams and games. IEEE Transactions on Automatic Control, 62(4):1545-1555, 2016.
[2] Pierre Bernhard and Alain Rapaport. On theorem of danskin with an application to theorem of von neumann-sion. Nonlinear Analysis: Theory, Methods & Applications, 24(8):1163-1188) 1995.
[3] Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming: an overview. In Proceedings of 1995 34th IEEE Conference on Decision and Control, volume 1, pages 560-564. IEEE, 1995.
[4] Shalabh Bhatnagar, Doina Precup, David Silver, Richard S Sutton, Hamid Maei, and Csaba Szepesvári. Convergent comporal-differene learning with arbitrary smooth function approxi- mation. Advances in Neural Information Processing Systems, 12:1204-1212 2009.
[5] Duncan S Callaway and lan A Hiskens. Achieving controllability of electric loads. Proceedings of the IEEE, 99(1):184-199, 2010.
[6] Jorge Cortes, Sonia Martinez, Timur Karatas, and Francesco Bullo. Coverage control for mobile sensing networks. IEEE Transactions on Robotics and Automation, 20(2):243-255, 2004.
[7] Jingjing Cui, Yuanwei Liu, and Arumugam Nallanathan. Multi-agent reinforcement learning- based resource allocation for uay networks. IEEE Transactions on Wireless Communications, 19(2):729-765 -73,, 2019.
[8] Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction non-convex sgd. In Advances in Neural Information Processing Systems, pages 15236-15245, 2019.
[9] Bo Dai, Niao He, Yunpeng Pan, Byron Boots, and Le Song. Learning from conditional distributions via dual embeddings. In Artificial Intelligence and Statistics, pages 1458-1467 PMLR, 2017.
[10] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In Interna- tional Conference on Machine Learning, pages 1125-1134. PMLR, 2018.
[11] Emiliano Dall' Anese, Hao Zhu, and Georgios B Giannakis. Distributed optimal power flow for smart microgrids. IEEE Transactions on Smart Grid, 4(3):1464 1475, 2013.
[12] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo R Jovanovic. Fast multi-agent temporal-differene learning via homotopy stochastic primal-dual method. In Optimization Foundations for Reinforcement Learning Workshop, 33rd Conference on Neural Information Processing Systems, 2019.
[13] Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed TD(0) with linear function approximation on multi-agent reinforcement learning. In International Conference Machine Learning, pages 1626-1635, 2019.
[14] Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. arXiv preprint arXiv: 170.::170..07944. 2017.
[15] Damien Ernst, Mevludin Glavic, and Louis Wehenkel. Power systems stability control: rein- forcement learning framework. IEEE Transactions on Power Systems, 19(1):427-435, 2004.
[16] Mevludin Glavic, Raphaël Fonteneau, and Damien Emstt Reinforcement learning for electric power system decision and control: Past considerations and perspectives. IFAC-PapersOnLine. 50(1):6918-66) 6927, 2017.
[17] Junling Hu and Michael Wellman. Nash q-learning for general-sum stochastic games. Journal of Machine Learning Research, 1039v):0039-1063 2003.

---

[18] Kaiyi Ji, Zhe Wang, Bowen Weng, Yi Zhou, Wei Zhang, and Yingbin Liang. History-gradient aided batch size adaptation for variance reduced algorithms. In International Conference on Machine Learning, pages 4762-4772. PMIR, 2020.
[19] Zhanhong Jiang, Aditya Balu, Chinmay Hegde, and Soumik Sarkar. Collaborative deep learning in fixed topology networks. In Advances in Neural Information Processing Systems, pages 9914, 2017.
[20] Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. arXiv preprint 171.0556,, 2017.
[21] Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 2021.
[22] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal of Robotics Research, 32(1 (2((1)):228-113 2013.
[23] Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of Machine Learning Research, (0Dec):1110-11111 149, 2003.
[24] Martin Lauer and Martin Riedmiller. An algorithm for distributed reinforcement learning in cooperative multi-agent systems. In In Proceedings of the Seventeenth International Conference on Machine Learning. Citeseer, 2000.
[25] Donghwan Lee, Hyungjin Yoon, and Naira Hovakimyan. Primal-dual algorithm for distributed reinforcement learning: distributed GTD. 2018 IEEE Conference on Decision and Control (CDC), pages 1977-1972. IEEE, 2018.
[26] Jae Won Lee, Byoung-Take Zhang, al. Stock trading system using reinforcement learning with cooperative agents. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 451-458, 2002.
[27] Xiangru I Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 5336-5346, 2017.
[28] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for conconvex-concayy minimax problems. In International Conference on Machine Learning, pages 6083-6093. PMLR, 2020.
[29] Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine Learning Proceedings 1994, pages 157-163. Elsevier, 1994.
[30] Bo Liu, Ian Gemp, Mohammad Ghavamzadeh, Liu, Sridhar Mahadevan, and Marek Petrik. Proximal gradient temporal difference learning: Stable reinforcement learning with polynomial sample complexity. Journal of Artificial Intelligence Research, 63:461 1944,9944400 2018
[31] Mingrui Liu Liu, Youssef Mroueh, Wei Zhang, Xiaodong Cui, Jerret Ross, and Payel Das. Decentralized parallel algorithm for training generative adversarial nets. In Conference Neural Information Processing Systems, 2020.
[32] Weijie Liu, Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil, Zebang Shen, and Nenggan Zheng. A decentralized proximal point-type method for saddle point problems. arXiv preprint arXiv:1910. 14380, 2019.
[33] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettive environments. arXiv preprint arXiv: (tv::/70.02277 2017.
[34] Songtao Lu, Kaiqing Zhang, Tianyi Chen, Tamer Basar, and Lior Horesh. Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning. In AAAI Conference on Artificial Intelligence, 2021.
12

---

[35] Songtao Lu, Xinwei Zhang, Haoran Sun, and Mingyi Hong. GNSD: A tradieet-tracking based nonconvex stochastic algorithm for decentralized optimization. In 2019 IEEE Data Science Workshop (DSW), pages 315-321. IEFE, 2019.
[36] Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient de- scent ascent for stochastic nonconvex-stronglyy-ooee minimax problems. arXiv preprint arXiv:2001.03724 2020.
[37] Sergio Valcarcel Macua, Jianshu Chen, Santiago Zazo, and Ali H Sayed. Distributed pol- icy evaluation under nultiple behavior strategies. IEEE Transactions on Automatic Control, (0(5):1260-1274 2014.
[38] Hamid Reza Maei, Csaba Szepesvari, Shalabh Bhatnagar, Doina Precup, David Silver, and Richard S Sutton. Convergent temporal-difference learning with arbitrary smooth function approximation. Advances in Neural Information Processing Systems, pages 1204-1212 2009.
[39] Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent opti- mization. IEEE Transactions on Automatic Control, 54(1):48, 2009.
[40] Petter Ogren, Edward Fiorelli, and Naomi Ehrich Leonard. Cooperative control of mobile sensor networks: Adaptive gradient climbing in a distributed environment. IEEE Transactions on Automatic Control, 49(8): 1302, 2004.
Applications on roboties. Journal of Intelligent & Robotic Systems, 86(2):153 153-173, 2017. [41] Athanasios S Polydoros and Lazaros Nalpantidis. Survey of model-based reinforcement learning:
[42] Shuang Qiu, Zhuoran Yang. Xiaohan Wei, Jieping Ye, and Zhaoran Wang. Single-timescale stochastic nonconvex-concave optimization for smooth nonlinear TD learning. arXiv preprint arXiv:2008. /0103, 2020.
[43] Michael Rabbat and Robert Nowak. Distributed optimization in sensor networks. In Proceedings of the 3rd Iternational Symposium on Information Processing in Sensor Networks, pages 20-27, 2004.
[44] Xingyu Sha, Jiaqi Zhang, Keyou You, Kaiging Zhang, and Tamer Basar. Fully asyn- chronous policy evaluation in distributed reinforcement learning over networks. arXiv preprint MiXiv:2033.00433 2020.
[45] William D Smart and Pack Kaelbling. Effective reinforcement learning for mobile robots. In Proceedings 2002 IEEE International Conference Robotics and Automation (Cat. No. 02CH37292), volume 4, pages 3404-3410. IEEE, 2002.
[46] Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andid learning. In Conference on Learning Theory, pages 2803-2830. PMLR, 2019.
[47] Haoran Sun, Songtao Lu, and Mingyi Hong. Improving the sample and communication complexity for decentralized non-convex optimization: Joint gradient estimation and tracking. In International Conference on Machine Learning, pages 9217-9228. PMLR, 2020.
[48] Jun Sun, Gang Wang, Georgios Giannakis, Qinmin Yang, and Zaiyue Yang. Finite-time analysis of decentralized temporal-difference learning with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 4485-449 PMLR, 2020.
[49] JohAn analysis tempn N Tsitsiklis and Benjamin Van Roy. An analysis demporal- learning with function approximation. IEEE Transactions on Automatic Control, 42(5))677-6600 1997.
[50] Hoi-To Wai, Mingyi Hong, Zhuoran Yang, Zhaoran Wang, and Kexin Tang. Variance reduced policy evaluation with smooth function approximation. Advances in Neural Information Processing Systems, 32:5784-5795, 2019.
13

---

[51] Hoi-To Wai, Zhuoran Yang, Zhaoran Wang. and Mingyi Hong. Multi-agen reinforcement learning via double averaging primal-dual optimization. In Advances in Neural Information Processing Systems, pages 9649-9660, 2018.
[52] Gang Wang and Georgios B Giannakis. Finite-time error bounds for biased stochastic approxi- mation with applications to q-learning. In International Conference on Artificial Intelligence and Statistics, pages 3015-3024. PMLR, 2020.
[53] Gang Wang. Songtao Lu, Georgios B Giannakis, Gerald Tesauro, and Jian Sun. Decentralized td tracking with linear function approximation and its finite-time analysis. Advances in Neural Information Processing Systems, 2020, 2020.
[54] Xiaofeng Wang and Tuomas Sandholm. Reinforcement learning play an optimal nash equilibrium in team markov games. Advances in Neural Information Processing Systems, 15:1603-1610, 2002.
[55] Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. In Advances in Neural Information Processing Systems, pages 2406-2416, 2019.
[56] Marco A Wiering. Multi-agent reinforcement learning for traffic light control. In Machine Learning: Proceedings of the Seventeenth International Conference (ICML'2000)), pages 1151- 1158, 2000.
[57] Zhaoxian Wu, Han Shen, Tianyi Chen, and Qing Ling. Byzantine-resilient decentralized td learning with linear function approximation. IEEE Transactions on Signal Processing. 2021.
[58] Ran Xin, Usman Khan, and Soummya Kar. improved convergence analysis for decentral- ized online stochastic non-convex optimization. arXiv preprint arXiv:2008.04/1 2020.
[59] Fuqiang Yao and Luliang Jia. A collaborative multi-agent reinforcement learning anti-jamming algorithm wireless networks. IEEE Wireless Communications Letters, 8(4): 2019.
[60] Amy Zhang, Nicolas Ballas, and Joelle Pineau. A dissection of overfiuting and generalization in continuous reinforcement learning. arXiv preprint arXiv: 00188800007777 2018.
[61] Chiyuan Zhang, Oriol Vinyals, Remi Munos, and Samy Bengio. A study overfitting in deep reinforcement learning. arXiv preprint arXiv: 1804:v8800.06680 2018.
[62] Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021.
[63] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi-agent reinforcement learning with networked agents. International Conference on Machine Learning, pages 1872-5881. PMLR, 2018.
14


Reviews:
[{"review_id": "vM8Dq6l6_md", "reviewer": "Reviewer_6xn4", "summary": "This paper considers decentralized MARL policy evaluation with nonlinear function approximation. The authors first reformulate the policy evaluation problem as a decentralized nonconvex-strongly-concave minimax saddle point problem and then develop a decentralized gradient-based descent ascent algorithm called GT-GDA that enjoys a convergence rate of O(1/T ).\n", "questions": "", "limitations": "", "rating": 7, "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": "Pros:\nThis work is the first to investigate the decentralized PE (DPE) problem for MARL with nonlinear function approximation.\t\t\n\nCons:\nGT-GDA has the same sample complex and communication complexity as DHPD [1] in which linear function approximations are considered. It is not clear to me, from both practical and theoretical perspectives, the advantage of considering nonlinear functional approximations.\n\n[1] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo R Jovanovic. Fast multi-agent temporal-difference learning via homotopy stochastic primal-dual method. In Optimization Foundations for Reinforcement Learning Workshop, 33rd Conference on Neural Information Processing Systems, 2019.\n\nIt will be nice to provide some numerical experiments to highlight and demonstrate the advantage of the proposed framework as there are several closely related works such as [2] and [3].\n\n[2] Hoi-To Wai, Mingyi Hong, Zhuoran Yang, Zhaoran Wang, and Kexin Tang. Variance reduced policy evaluation with smooth function approximation. Advances in Neural Information Processing Systems, 32:5784–5795, 2019.\n\n[3] Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. In Advances in Neural Information Processing Systems, pages 9649–9660, 2018. \n \n\n\n#############after authors' response#############\n\nI am happy with the responses from the authors (especially on the further elaboration of the contributions and explanation on why the direct comparisons with existing algorithms are not applicable). I will raise my score to 7.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "seG9kCaf6gz", "reviewer": "Reviewer_ZsKo", "summary": "This work analyzes decentralized policy evaluation problem for MARL under non-linear approximation for the first time, and the sample complexity is further reduced via variance reduction technique. The prevalent compact feasible set assumption is relaxed to mild assumptions on the objective function. ", "questions": "", "limitations": "", "rating": 7, "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": "Originality: This work is claimed as the first analysis on decentralized policy evaluation problem for MARL under non-linear approximation. However, advice (1) below probably invalidates this claim, so this work is not that original. \n\nQuality: The submission is technically sound for minimax optimization but not for RL. See advice (1) below for detail. \n\nClarity: The submission is clear and well organized. \n\nSignificance: The results are not significant. See advice (1) below for detail. \n\nAdvice and questions: \n(1) Your evaluation metric $\\frac{1}{T+1} \\sum_{t=0}^{T} \\mathbb{E}\\left[\\mathfrak{M}_{t}\\right]$ is only about the empirical objective function $F$ and its related $J$, which depends on the fixed data. In contrast, all the policy evaluation works I read use the objective function $\\mathcal{L}$ (eq. (1)) to ensure generalization ability. In addition, your Assumptions 1-3 are also data-dependent. In this case, I can envision that the proof simply repeats or slightly adjusts that of the finite-sum minimax optimization, without using the generating distribution of the Markovian samples, yes? If yes, this analysis is simply about finite-sum minimax optimization not RL. $\\textbf{This is the main reason why I reject this paper. If you can solve this issue, I will accept this paper.}$ \n\nTo ensure convergence on $\\mathcal{L}$, each iteration needs to use a different sample mini-batch to avoid high correlation among stochastic gradients and high computation complexity, as done by almost all the works I have seen. The data should be treated as randomly generated from MDP, not as fixed. Then, bias and variance analysis of the stochastic gradient that estimates $\\nabla \\mathcal{L}$ are perhaps also needed. Finally, the evaluation metric should rely on $\\mathcal{L}$ not dataset, and the complexity should not contain data size $n$. \n\nAlso, it is more desirable to replace the data-dependent assumptions into some more basic assumptions on the MDP. For example, bounded reward mapping $R$ can imply and thus replace Assumption 1a. Assumptions on $V_{\\theta}$ are perhaps also desirable such as Lipschitz or L-smooth properties, which might imply some of Assumptions 1-3.\n\n(2) In the following sentence in the abstract, you could add “under nonlinear function approximation”, since [14], [37], [42] achieved lower complexity than yours under linear function approximation. \n\n“To our knowledge, this paper is the first work that achieves O(ε−2) in both sample  and communication complexities in decentralized policy evaluation for cooperative MARL. ”\n\n(3) Typo: In the V function definition in the first paragraph of Section 2.1, change $s_{t+1}$ into $a_t$. \n\n(4) Typo: In eq. (2), change $\\frac{1}{m}\\sum_{t=1}^m$ into $\\frac{1}{n}\\sum_{t=1}^n$. \n\n(5) The author sequence of [14] should be\nGang Wang, Songtao Lu, Georgios B. Giannakis, Gerald Tesauro, Jian Sun3\n\n(6) You might also cite the following papers on policy evaluation using linear function approximation. \n\n- Sun, J., Wang, G., Giannakis, G. B., Yang, Q., & Yang, Z. (2020, June). Finite-time analysis of decentralized temporal-difference learning with linear function approximation. In International Conference on Artificial Intelligence and Statistics (pp. 4485-4495). PMLR.\n\n- Chen, Z., Zhou, Y., & Chen, R. (2021). Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity. ArXiv:2103.13147.\n\n- Liu, R., & Olshevsky, A. (2021). Distributed TD (0) with Almost No Communication. ArXiv:2104.07855.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not mentioned. \nBoth the authors and I do not think this theoretical work could have any immediate societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "I think this work has no ethical concerns. ", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "About 5 hours"}, "extra_text": {}}, {"review_id": "m6pRSNGDFEz", "reviewer": "Reviewer_qMVk", "summary": "This paper studies decentralized cooperative policy evaluation. The main idea is to reformulate it as some standard decentralized optimization problem and then apply the gradient tracking and variance reduction technique.\n", "questions": "", "limitations": "", "rating": 5, "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": "I feel the problem setting is kind of artificial and is not well motivated by real-world applications. In this setting, the network topology is static and the value function of each agent has the same parameterization (e.g., if the value function is a neural network, then each agent shall use the same NN architecture). I cannot think of a practical application where all these conditions are met while we still cannot do centralized PE. Also in this setting, why do we want to do PE? \n\nThe technical contributions look marginal. Formulating decentralized PE as a decentralized optimization problem is straightforward, and the techniques for solving the reformulated problem have been widely studied in the decentralized optimization literature. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is purely theoretical. I am not aware of any potential negative societal impact.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "3yu8VElDut", "reviewer": "Reviewer_d6sP", "summary": "This paper studies the problem of policy evaluation in a decentralized multi-agent reinforcement learning setting with non-linear function approximation. The authors present a gradient tracking based descent-ascent optimization algorithm GT-GDA that aggregates global gradients by a network-weighted aggregation, and consequently updates local parameters by descent/ascent. The authors establish convergence of the proposed algorithm and additionally analyse a reduced-variant extension. Experimental results establish convergence in several numerical benchmarks.", "questions": "", "limitations": "", "rating": 7, "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": "Originality and quality: The paper makes a complete analysis of the presented algorithm for decentralized policy evaluation in the nonlinear setting, and additionally analyses a variant with reduced variance as well. Few points:\n- Given that the authors have discussed a new problem setting, it would be helpful to pin-point the exact technical contributions (from both algorithmic and theoretical points of view), as it is unclear from the current manuscript what aspects of the paper are derived from existing research.\n- The motivation for the problem is still lacking: I would imagine the non-linear setting to be more difficult than the linear function approximation setting, however, it is unclear to me what technical challenges one would face in extending linear algorithms to the non-linear setting.\n- The experimental results are a bit lacking: only one problem is examined, and there are no baselines to compete with. While it is clear that the authors are tackling _decentralized nonlinear_ function approximation, it would be interesting nonetheless to compare their algorithm with linear baselines in a linear (or nearly-linear) environment. Additionally, the ablations in the supplementary material can be extended to larger systems to examine the effect of sparsity: the 6-node system considered does not seem challenging based on Figure 6.\n\nClarity: The paper is generally well-written but requires proof-reading to remove spelling and grammar issues.\n\nSignificance: The contributions are focused and tackle a somewhat niche problem (decentralized nonlinear policy evaluation).\n\nSpecific Questions:\n- How do the potential functions described in Theorems 1 and 2 compare with existing single-agent and linear function approximation potentials?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not discussed the limitations of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies decentralized policy evaluation for cooperative multi-agent RL. The main approach of this paper is (1) reduce the problem to a minimax optimization problem, and (2) develop new algorithms for solving this minimax problem using gradient tracking and variance reduction technique. As pointed out by reviewers, the main concerns of this paper are that (a) the main technique contribution is mostly in optimization, while the paper currently mainly sells as a RL paper, without detailed comparison in terms of rate with existing optimization algorithms. (b) the strongly concave assumption lacks justification in the RL setting. Except these, most reviewers are convinced that the paper is well-written, the results are solid, and this paper makes interesting contributions. We hope authors can address above concerns in the final version.
Decision: Accept (Poster)