Taming Communication and Sample Complexities in Decentralized Policy Evaluation for Cooperative Multi-Agent Reinforcement Learning

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 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 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 anO(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 O( −2) communication complexity and O(m √ n −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 O( −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.

text: √ n −2) sam-
ple 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 O( −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.

heading: 1 Introduction
text: In recent years, multi-agent 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 (NeurIPS 2021).
the next joint state. Each agent can only observe its local reward, which is a function of the joint state and actions. One important paradigm in 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 in classical reinforcement learning (RL) problems, a 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 a 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 on 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 a result, MARL often use highly nonlinear parametric models (e.g., deep neural network (DNN)) for policy approximation. In this paper, we focus on PE based on 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 a 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, we focus on 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, we first reformulate the DPE problem of MARL as a decentralized non-convexstrongly-concave minimax saddle point problem. To solve the minimax problem in a decentralized fashion, we propose a gradient-tracking-based gradient descent-ascent (GT-GDA) algorithm. We show that GT-GDA enjoys a convergence rate of O(1/T ), which leads to an O(mn −2) sample complexity and an O( −2) communication complexity, where m is the number of agents, n is the data size, and is the convergence accuracy.
• To further reduce the sample complexity, we develop two variance-reduced 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 communication complexity O( −2) as GT-GDA, but requiring a lower sample complexity O(m √ n −2).
• It is worth noting that, in our theoretical analysis, we relax the commonly-used compactness conditions of the feasible set with some mild assumptions on 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.
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, we 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 5 provides numerical results to verify our theoretical findings, and Section 6 concludes this paper.

heading: 2 Problem formulation and related work
text: 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-
tion 2.3, we highlight the challenges in designing efficient DPE algorithms with nonlinear function approximation and the significance of our work.

heading: 2.1 Problem formulation of decentralized policy evaluation for MARL
text: Consider a multi-agent network system G = (N ,L), where N and L denote the sets of agents and edges, respectively, with |N | = 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 (S,A,Pass′ , {Ri(s,a)}mi=1, ζ), where S andA are the state and action spaces, respectively; s ∈ S and a ∈ A are joint state and action; Pass′ is the transition probability from state s to state s′ after taking action a;Ri(s,a) is the local reward received by agent i after taking action a in state s; and ζ ∈ (0, 1) is a discount factor. Both the joint state s and action a are available to all agents, while the local rewardRi is private to agent i. In a multi-agent system, the global reward function is defined as the average of the local rewards 1m ∑m i=1Ri(s,a). Moreover, a joint policy π specifies sequential decision rules for all agents. Policy π(a|s) is the conditional probability of taking joint action a 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: Vπ(s0) = E [ 1 m ∑∞ t=0 ζ t ∑m i=1Ri(st,at)|s0, π ] , where the expectation is taken over all possible state-action trajectories and initial states.
To determine Vπ(·), one of the most effective methods is the temporal-difference (TD) learning algorithm, which focuses on solving the Bellman equation for Vπ(·): V(s)=T πV(s), 1m ∑m i=1Rπi (s)+
ζ ∑ s′∈S Pπss′V(s′), where T π denotes the Bellman operator,Rπi (s) = Ea∼π(·|s)R(s,a) andPπss′ = Ea∼π(·|s)Pass′ However, Pπss′ is unknown in MARL and the size of the state space S could be infinite. To address this challenge, a widely adopted approach is to approximate Vπ(·) by a function Vθ(·) parameterized by θ ∈ Rp. According to the formulation in [38, 50, 10, 9, 30], the Bellman equation can be solved by minimizing the following mean-squared projected bellman error (MSPBE): MSPBE(θ) , 12
∥∥Es∼dπ[(T πVθ(s)− Vθ)∇θVθ(s)>]∥∥2K−1θ , where Kθ = Es∼dπ [∇θVθ(s)∇θVθ(s)>] ∈ Rp×p and dπ is the stationary distribution of the MDP under policy π. From the Fenchel’s duality ‖x‖2A−1 = maxy∈Rp 2〈x,y〉 − y
>Ay, we can reformulate the MSPBE minimization problem as the following primal-dual minimax problem:
min θ∈Rp max ω∈Rp
L(θ,ω) , E [ 〈δ · ∇θVθ(s),ω〉 − 1
2 ω>[∇θVθ(s)∇θVθ(s)>]ω
] , (1)
where the expectation is taken over s ∼ dπ(·), a ∼ π(·|s), s′ ∼ Pas·, and δ = 1m ∑m i=1Ri(s,a) + ζVθ(s′) − Vθ(s). In practice, we only have access to a finite dataset with n-step trajectories D = { (st,at, {Ri(st,at)}ni=1, st+1) }n t=0
. By replacing the unknown expectation with the finite sample average, we have the following empirical minimax problem:
min θ∈Rp max ω∈Rp
F (θ,ω) = 1
n n∑ t=1 〈δt · ∇θVθ(st),ω〉 − 1 2 ω>K̂θω, (2)
where δt , 1m ∑m i=1Ri(st,at) + ζVθ(st+1) − Vθ(st) and K̂θ , 1 n ∑n t=1∇θVθ(st)∇θVθ(st)>. In this paper, we assume that both Kθ and its empirical estimate K̂θ are positive definite for all θ. Define J(θ) , F (θ,ω∗) = maxω∈Rp F (θ,ω), where ω∗ = arg maxω∈Rp F (θ,ω). J(θ) can be viewed as the finite empirical version of MSPBE. Here, we aim to minimize J(θ) by finding a stationary point of F (θ,ω). Recall that in MARL, the local reward is only observable for each individual agent. Thus, it is hard to obtain the global reward 1m ∑m i=1Ri(st,at) and δt in a multi-agent network. To address this challenge, we define δi,t = Ri(st,at) + ζVθ(st+1)− Vθ(st) and decompose the minimax problem in (2) as follows: minθ∈Rp maxω∈Rp F (θ,ω) = 1m ∑m i=1 Fi(θ,ω) =
1 mn ∑m i=1 ∑n t=1 fit(θ,ω), where fit(θ,ω) , 〈δi,t ·∇θVθ(st),ω〉− 1 2ω >[∇θVθ(st)∇θVθ(st)>]ω. We call this step as local reward decomposition. In cooperative MARL, a 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) it is difficult to set up a 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)
in a decentralized fashion, we can rewrite it in the following equivalent form:
min {θi}mi=1 max {ωi}mi=1
1
m m∑ i=1 Fi(θi,ωi) = 1 mn m∑ i=1 n∑ t=1 fit(θi,ωi),
subject to θi = θj ,ωi = ωj , ∀(i, j) ∈ L, (3)
where θi and ωi 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 is also referred to as the “consensus form.”
Clearly, Problems (2) and (3) are equivalent. For a fixed θ, each local function Fi(θi, ·) is a strongly concave function of ω. For a fixed ω, Fi(·,ω) is a non-convex function of θ. Thus, Problem (3) is a decentralized non-convex-strongly-concave 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:
Definition 1 (Sample Complexity). The sample complexity is defined as the total number of incremental first-order oracle (IFO) calls required across all nodes until algorithm converges, where one IFO call evaluates a pair of (fit(θ,ω),∇fit(θ,ω)) at node i. Definition 2 (Communication Complexity). The communication complexity is defined as the total rounds of communications required until algorithm converges, where each node can send and receive a p-dimensional vector with its neighboring nodes in one communication round.

heading: 2.2 Related work on policy evaluation
text: 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, 1], etc. However, most of these early works approximate the value function in a 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 approaches for MARL, the work in [25] proposed to estimate the value function with a linear approximation (i.e., V(s) ≈ φ(s)>θ,θ ∈ Rp, where φ : S → Rp is a feature mapping) and developed a distributed gradient temporal-difference (DGTD) algorithm. However, this work only considered asymptotic convergence analysis and required diminishing step-sizes to 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 as a 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 O(1/T ) convergence rate in finding stationary points. The work in [13] developed a distributed consensus-based TD(0) algorithm, which integrates the network consensus step and local TD(0) updates. They provided a finite-time analysis and showed a convergence rate of O(1/T ). To further improve convergence, the work in [51] proposed a primal-dual distributed incremental aggregated gradient (PD-DistIAG) method to integrate gradient-tracking and incremental aggregated gradient methods to achieve linear convergence. However, a 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 to finding a solution for a linear equation system, which is in essence similar to solving a relatively easy strongly-convex optimization problem [14], [52], [48], [46]. In stark contrast, under non-linear approximation for policy evaluation, the problem possesses a non-convex-strongly-concave 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 two-timescale step-sizes2, resulting in a slow convergence performance. Recently, the work
2A primal-dual algorithm is a two-timescale if γt/ηt → 0 or γt/ηt → ∞ as t→ ∞, where γt and ηt denote the primal and dual step-sizes at time t, respectively.
in [50] showed that PE with nonlinear approximation in RL is equivalent to a non-convex-stronglyconcave minimax optimization problem. To find a stationary point for such minimax problem, they proposed a non-convex primal-dual gradient with variance reduced (nPD-VR) algorithm. However, their algorithm requires an O(1/m) step-size, where m 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 scale first-order stochastic algorithms for the nonconvex-strongly-concave minimax optimization. These two algorithms utilized stochastic gradient with momentum and variance-reduced momentum [8], and achieved O(1/ √ T ) and O(1/T 2/3) convergence rates, respectively. However, diminishing step-sizes are required in these two algorithms, which do not work well in practice.
4) Relations with decentralized nonconvex-strongly-concave minimax optimization: As mentioned earlier, the PE problem of cooperative MARL can be reformulated as a non-convex-stronglyconcave 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 decentralized minimax problem in Problem (2), our proposed algorithms are primal-dual-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 a “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.

heading: 2.3 Significance of our work and challenges of DPE with nonlinear function approximation
text: To our knowledge, our work is the first to solve the DPE problem with nonlinear function approximation for MARL. However, such nonlinear approximation imposes several significant challenges on algorithm development and analysis. As discussed in Section 2.1, we propose to reformulate the DPE problem as a decentralized nonconvex-strongly-concave minimax optimization problem. In the 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/communicationefficient for MARL. To address these limitations, we first propose two decentralized variance-reduced algorithms for solving the nonconvex-strongly-concave DPE minimax problem, for which establishing the convergence rates is highly challenging. Second, we adopt the gradient tracking (GT) technique to reduce network consensus error. Under nonlinear function approximation, our algorithms need to track the gradients for both primal and dual variables. However, such “double gradient tracking” introduces new constraints on algorithm design. Third, many of the existing nonconvex-strongly-concave 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 in our algorithm analysis. To conclude this section, we summarize all related work in Table 1.
Algorithm 1 GT-GDA Algorithm at Agent i. .
1: Set prime-dual parameter pair (θi,0,ωi,0) = (θ0,ω0). 2: Calculate local gradients as pi,0 =∇θFi(θi,0,ωi,0), and di,0 =∇ωFi(θi,0,ωi,0); 3: for t = 1, · · · , T do 4: Update local parameters (θi,t+1,ωi,t+1) as in (6); 5: Calculate local gradients (vi,t+1,ui,t+1) as in (4); 6: Track global gradients (pi,t+1,di,t+1) as in (5); 7: end for

heading: 3 Gradient-tracking gradient descent ascent algorithm.
text: 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), a popular approach is to let agents aggregate their neighbor information through a consensus weight matrix M ∈ Rm×m [39, 51]. Let [M]ij denote the element in the i-th row and the j-th column in M. M satisfies the following properties: (a) Doubly stochastic: ∑m i=1[M]ij = ∑m j=1[M]ij = 1; (b) Symmetric: [M]ij = [M]ji, ∀i, j ∈ N ; and (c) Network-Defined Sparsity: [M]ij > 0 if (i, j) ∈ L; otherwise [M]ij = 0, ∀i, j ∈ N . The above properties imply that the eigenvalues of M are real and can be sorted as −1 < λm(M) ≤ · · · ≤ λ2(M) < λ1(M) = 1. We define the second-largest eigenvalue in magnitude of M as λ , max{|λ2(M)|, |λm(M)|}. Our GT-GDA algorithm for each agent i is illustrated in Algorithm 1. Specifically, at the t-th iteration, agent i first calculates the local full gradients as follows:
vi,t = ∇θFi(θi,t,ωi,t), ui,t = ∇ωFi(θi,t,ωi,t). (4) Note that vi,t and ui,t only contain the gradient information of the local objective function Fi(θ,ω). Thus, merely updating with vi,t and ui,t cannot guarantee the convergence of the global objective function F (θ,ω). To address this challenge, we introduce two auxiliary variables, pi,t and di,t. The agent updates the two variables by performing the following local weighted aggregation:
pi,t= ∑ j∈Ni [M]ijpj,t−1 + vi,t − vi,t−1, di,t= ∑ j∈Ni [M]ijdj,t−1 + ui,t − ui,t−1, (5)
where Ni , {j ∈ N , : (i, j) ∈ L} denotes the set of agent i’s neighbors. Technically, pi,t and di,t track the directions of global gradients. With some derivations, it can be shown that∑ i∈N pi,t= ∑ i∈N ∇θFi(θi,t,ωi,t) and ∑ i∈N di,t= ∑ i∈N ∇ωFi(θi,t,ωi,t). Lastly, each agent updates local parameters following the conventional decentralized gradient descent and ascent steps:
θi,t+1 = ∑ j∈Ni [M]ijθj,t − γpi,t, ωi,t+1 = ∑ j∈Ni [M]ijωj,t + ηdi,t, (6)
where the constants γ and η 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 (θ,ω) = 1m ∑m i=1 Fi(θ,ω) and J(θ) = maxω∈Rp F (θ,ω) satisfy:
(a) (Boundness from Below): There exists a finite lower bound J∗ = infθ J(θ) > −∞; (b) (Lipschitz Smoothness): Local objective function Fi(θ, ·) isLF -Lipschitz smooth, i.e., there exists
a positive constant LF such that the gradient ∇Fi(θ,ω) = [∇θFi(θ,ω)>,∇ωFi(θ,ω)>]> satisfies ‖∇Fi(θ,ω)−∇Fi(θ′,ω′)‖2≤L2F ‖θ−θ′‖2+L2F ‖ω−ω′‖2,∀ θ,θ′,ω,ω′ ∈ Rp, i ∈ [m];
(c) (Strong Concavity in Dual): Local objective function Fi(θ, ·) is µ-strongly concave for fixed θ ∈ Rp, i.e., there exists a positive constant µ such that ‖∇ωFi(θ,ω)−∇ωFi(θ,ω′)‖ ≥ µ‖ω−ω′‖,∀ θ,ω,ω′∈Rp, i∈ [m]
(d) (Bounded Dual Maximizer): For any primal variable θ ∈ Rp, its associated dual maximizer ω∗(θ) , arg maxω∈Rp F (θ,ω) is bounded, i.e., ‖ω∗(θ)‖<∞;
(e) (Bounded Gradient at Maximum): The partial derivative at maximum point ∇θF (θ,ω∗(θ)) is bounded, i.e., ‖∇θF (θ,ω∗(θ))‖ <∞, ∀ θ ∈ Rp.
In these assumptions, (a) and (b) are standard in literature. It can be verified that (c) holds when K̂θ is positive definite; (d)-(e) guarantee that ∇J(θ) = ∇θF (θ,ω∗(θ)) (see Lemma 10 in the supplementary material). Note that most of the existing works [28, 42] adopt the compactness assumption to 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 ‖ω∗(θ)‖ and ‖∇θF (θ,ω∗(θ))‖. To quantify the convergence rate, we propose to use the following new metric, which is the key to the success of establishing all convergence results in this paper:
Mt ,‖∇J(θ̄t)‖2+2‖ω∗t −ω̄t‖2+ 1
m m∑ i=1 ( ‖θi,t−θ̄t‖2+‖ωi,t−ω̄t‖2 ) , (7)
where ω∗t denotes ω ∗(θ̄t) = arg maxω∈Rp F (θ̄t,ω). The first term in (7) measures the convergence of primal variable θ: ‖∇J(θ̄t)‖2 = 0 indicates that θ̄t is a first-order stationary point for J(·). The second term in (7) measures ω̄t’s convergence to the unique maximizer ω∗t for F (θ̄t, ·). The last term in (7) is the average consensus error of local copies. Thus, as Mt → 0, we have that the algorithm reaches a 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 error terms over multi-agents, 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 ‖θ̄t − θ∗‖2 as it can be viewed as a strongly convex optimization, while the other terms are the same. Based on the metric in (7), we have the following:
Theorem 1 (Convergence of GT-GDA). Under Assumption 1, if the step-sizes satisfy that κ , γ/η ≤ µ2/13L2F and η ≤ min{k1, k2, k3, k4}, then GT-GDA has the following convergence result:
1
T + 1 T∑ t=0 E[Mt]≤ 2E[P0−J∗] min{1, L2F }(T+1)γ ,
where Pt is a potential function defined as:
Pt,J(θ̄t)+ 8γL2F µη ‖ω̄t−ω∗t ‖2+ 1 m m∑ i=1 ‖θi,t−θ̄t‖2+‖ωi,t−ω̄t‖2+γ‖pi,t−p̄t‖2+η‖di,t−d̄t‖2,
and the constants in the step-size η are as follows:
k1 = 13L2F 2µ2
( LF +
L2F µ
+ (1− λ) ) , k2 =
13L2F µ2 ( 1/2 + 1/(1− λ)2 ) , k3 = (1− λ) 6µ(1 + 1/κ) ,
k4 = 26(1− λ)L2F
(µ2 + 144L4F + 4L 2 Fµ
2 + 48µ2L2F (1+1/κ) 1−λ ) .
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{|λ2|, |λm|} < 1). Therefore, k2 and k4 are close to zero in this case. Also, the ratio of the step-sizes κ , γ/η is required to be a non-zero constant. Either a too small or a 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 η and γ.
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 2-stationary solution, i.e.,
1 T+1 ∑T t=0 E[Mt] ≤ 2, the total communication rounds are on the order of O( −2) and the total samples evaluated across the network system is on the order of O(mn −2).

heading: 4 Gradient-tracking stochastic variance reduction algorithms
text: In the GT-GDA algorithm, agents need to evaluate local full gradients in each iteration, which may result in a high sample complexity when the trajectory length n is large in MARL. This limitation motivates us to leverage the stochastic recursive variance-reduced approach (e.g., [55]) to achieve low sample complexity in MARL decentralized policy evaluation.
Algorithm 2 GT-SRVR/GT-SRVRI Algorithm at Agent i. . If GT-SRVR: |Ri,t|=n, |Si,t|=q; If GT-SRVRI: |Ri,t|=min{(t/q+1)αq, c −2, n}, |Si,t|=q.
1: Set prime-dual parameter pair (θi,0,ωi,0) = (θ0,ω0). 2: Draw Ri,0 samples without replacement and calculate local stochastic gradient estimators as
pi,0 =vi,0 = 1 |Ri,0| ∑ j∈Ri,0∇θfij(θi,0,ωi,0), and di,0 =ui,0 = 1 |Ri,0| ∑ j∈Ri,0∇ωfij(θi,0,ωi,0);
3: for t = 1, · · · , T do 4: Update local parameters (θi,t+1,ωi,t+1) as in (6); 5: Calculate local gradient estimators (vi,t+1,ui,t+1) as in (8); 6: Track global gradients (pi,t+1,di,t+1) as in (5); 7: end for
1) The Algorithms: We first propose an 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:
vi,t = { ∇θFi(θi,t,ωi,t), if mod(t, q) = 0, vi,t−1+
1 |Si,t| ∑ j∈Si,t ( ∇θfij(θi,t,ωi,t)−∇θfij(θi,t−1,ωi,t−1) ) , otherwise, (8a)
ui,t = { ∇ωFi(θi,t,ωi,t), if mod(t, q) = 0, ui,t−1+
1 |Si,t| ∑ j∈Si,t ( ∇ωfij(θi,t,ωi,t)−∇ωfij(θi,t−1,ωi,t−1) ) , otherwise, (8b)
where Si,t is a local subsample at the tth iteration for agent i. In (8), the algorithm evaluates full gradients∇Fi(θi,t,ωi,t) only every q steps. For other iterations with mod(t, q) 6= 0, the algorithm estimates the local gradients with a mini-batch of gradients 1|Si,t| ∑ j∈Si,t∇ωfij(θi,t,ωi,t) and a
recursive correction term ui,t−1− 1|Si,t| ∑ j∈Si,t∇ωfij(θi,t−1,ωi,t−1). It will be shown later that, thanks to the periodic full gradient (when mod(t, 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 Si,t 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 q 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 tth iteration with mod(t, q) = 0 as follows :
vi,t = 1 |Ri,t| ∑ j∈Ri,t ∇θfij(θi,t,ωi,t), ui,t = 1 |Ri,t| ∑ j∈Ri,t ∇ωfij(θi,t,ωi,t), (9)
where Ri,t is a subsample set (sampling without replacement), whose size is chosen as |Ri,t| = min{(t/q + 1)αq, c −2, n}. Here, α > 0 is a constant, is a desired convergence error, and c > 0 is a constant that depends on . Our design of |Ri,t| 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 GT-SRVR/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 a batch-size adaptation scheme based on the historical gradient information. Although similar idea can be also adopted in our algorithms, it requires the exact value of the stochastic gradient variance σ2 for batch-size selection as well as extra memory cost to store the history-gradient information, which is less practical compared to our approach.
2) Theoretical Results of GT-SRVR/GT-SRVRI: Now, we establish the convergence performance of GT-SRVR/GT-SRVRI. First, we replace Assumption 1(b) with the following individual Lipschitz smoothness assumption: Assumption 2 (Lipschitz smoothness). The function fij(θ, ·) is Lf -Lipschitz smooth, i.e., there exists a constant Lf > 0, such that the gradient ∇fij(θ,ω)= [∇θfij(θ,ω]>,∇ωfij(θ,ω)>)> satisfies ‖∇fij(θ,ω)−∇fij(θ′,ω′)‖2≤L2f‖θ−θ′‖2+L2f‖ω−ω′‖2, ∀ θ,θ′,ω,ω′ ∈ Rp, i ∈ [m], j ∈ [n].
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 a constant σ2 > 0, such that E‖∇fij(θ,ω) − ∇Fi(θ,ω)‖2 ≤ σ2, ∀ θ,ω,∈ Rp, i ∈ [m], j ∈ [n].
With the metric in (7), the convergence of GT-SRVR/GT-SRVRI can be characterized as follows: Theorem 3 (Convergence of GT-SRVR). Under Assumption 1 (a)&(c)-(e) and Assumption 2, if the step-sizes satisfy κ , γ/η ≤ µ2/13L2f and η ≤ min{k5, k6, k7, k8}, then we have the following convergence result for GT-SRVR:
1
T + 1 T∑ t=0 E[Mt]≤ 2E[p0−J∗] min{1, L2f}(T + 1)γ ,
where pt is the potential function defined as:
pt,J(θ̄t)+ 8γL2f µη ‖ω̄t−ω∗t ‖2+ 1 m m∑ i=1 ( ‖θi,t−θ̄t‖2+‖ωi,t−ω̄t‖2+γ‖pi,t−p̄t‖2+η‖di,t−d̄t‖2 ) ,
and the constants in the step-size η are:
C0 = 1
1− λ (1 +
1 κ ) + 1 2 + 18L2f µ2 , k5 = 13L2f µ2 ( 1/2 + 1/(1− λ)2 ) , k6 = 1 8µC0 ,
k7 = 26(1− λ)L2f
(µ2 + 144L4f + 4L 2 fµ 2 + 64C0L2fµ 2) , k8 =
13L2f 2µ2
( Lf +
L2f µ
+ (1− λ) ) .
Theorem 4 (Convergence of GT-SRVRI). Under Assumption 1 (a)&(c)-(e), Assumption 2, and the same parameter settings and potential function as stated in Theorem 3, we have the following convergence result for GT-SRVRI:
1
T+1 T∑ t=0 E[Mt]≤ 2E[p0−pT+1] min{1, L2f}(T+1)γ +
1
min{1, L2f} ×
(12 λ (1+ 1 κ )+4+ 144L2f µ2 )(σ2 2 c + σ2C(n, q, α) T+1 ) , (10)
where the constant C(n, q, α) is defined as:
C(n, q, α) ,
{ 1
1−α ( n q ) ( 1α−1)− α1−α , if α>0 and α 6=1 log(nq )+1, if α=1.
Remark 3. In Theorems 3 and 4, it can be seen that the step-sizes and convergence performance depend on the network topology and the ratio of the step-sizes κ. Additionally, the convergence performance of GT-SRVRI is affected by the constant C(n, q, α), which depends on the inexact gradient estimation in tth iteration with mod(t, q) = 0.
Following from Theorems 3 and 4, we immediately have the sample and communication complexity results for GT-SRVR/GT-SRVRI: Corollary 5. Under the conditions in Theorems 3 and 4, and with q = √ n, to achieve an 2-
stationary solution (i.e., 1T+1 ∑T t=0 E[Mt] ≤ 2) with √ n 2 ≤ 1, we have:
• for GT-SRVR, the total communication rounds are O( −2) and the total samples evaluated across the network are O(m √ n −2)); • GT-SRVRI with α ≥ 1, the total communication rounds are bounded by O(log( √ n) −2) and the
total samples evaluated across the network are bounded by O(m log( √ n) √ n −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 α ≥ 1, the upper bounds of both the complexities have an additional factor log( √ n) factor compared with GTSRVR. Although the theoretical complexity bounds for GT-SRVRI is weaker than GT-SRVR (due to abandoning full gradients completely), we show through experiments in Section 5 that GT-SRVRI empirically outperforms than GT-SRVR in practice.

heading: 5 Experimental Results
text: In this section, we demonstrate the performance of our proposed GT-GDA and GT-SRVR/GT-SRVRI algorithms for cooperative MARL decentralized policy evaluation. We adopt the environment of Cooperative Navigation task in [33], which consists of m agents inhabiting a 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 no existing work in the literature on solving decentralized policy evaluation with nonlinear function approximation for MARL, we compare our algorithms with two stochastic algorithms as simple baselines in our experiments: 1) Decentralized Stochastic Gradient Descent Ascent (DSGDA) and 2) Gradient-Tracking-Based 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, η = 10−1.
From Figure 1(a) and 1(b), it can be seen 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−9) than the other three algorithms thanks to the variancereduced techniques. As is shown in Figure 1(c) and 1(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-SRVRI enjoy low sample and communication complexities.

heading: 6 Conclusion
text: In this paper, we studied the decentralized MARL policy evaluation problem with nonlinear function approximation. We first reformulated the problem as a decentralized non-convex-strongly-concave minimax problem and developed a gradient tracking based algorithm called GT-GDA. We showed that GT-GDA algorithm has the communication complexity of O( −2) and sample complexity of O(mn −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 O(m √ n −2). We have also conducted extensive numerical studies to verify the performance of our proposed algorithms. We note that our work opens up several interesting direction for future research. First, It is interesting to adopt communication-efficient mechanisms to further reduce the communication cost, especially when the parameters are high-dimensional. Second, it 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-2110259, CNS-2112471, CNS-2102233, CCF-2110252, ECCS-2140277, NSF-CCF-1934884 and a Google Faculty Research Award.

Review summaries:
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.