Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learning
Authors: Zhiyao Zhang
Myeung Suk Oh
FNU Hairi
Ziyue Luo
Alvaro Velasquez
Jia Liu
Venue: ICML 2025 poster (2025)
Keywords: Fully decentralized multi-agent reinforcement learning
Deep neural network
Finite-time global convergence.
Primary area: reinforcement_learning->multiagent

Abstract: Actor-critic methods for decentralized multi-agent reinforcement learning (MARL) facilitate collaborative optimal decision making without centralized coordination, thus enabling a wide range of applications in practice. To date, however, most theoretical convergence studies for existing actor-critic decentralized MARL methods are limited to the guarantee of a stationary solution under the linear function approximation. This leaves a significant gap between the highly successful use of deep neural actor-critic for decentralized MARL in practice and the current theoretical understanding. To bridge this gap, in this paper, we make the first attempt to develop a deep neural actor-critic method for decentralized MARL, where both the actor and critic components are inherently non-linear. We show that our proposed method enjoys a global optimality guarantee with a finite-time convergence rate of $\mathcal{O}(1/T)$, where $T$ is the total iteration times. This marks the first global convergence result for deep neural actor-critic methods in the MARL literature. We also conduct extensive numerical experiments, which verify our theoretical results.

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learning
Zhiyao Zhang" !
Myeung Suk Oh"
FNU Hairi
Ziyue Luo
Alvaro Velasquez? 3 Jia Liu
Abstract
found wide range of applications in recent years, such as network recourse allocation (Cui et al., 2019; Liu et al., 2020b), autonomous driving (Sallab et al., 2017; Kiran et al., 2021; Yu et al., 2019), wireless random access network op- timization (Luong et al., 2019; Nasir and Guo, 2019; Oh et al., 2025). Generally speaking. in decentralized MARL, multiple agents collaboratively learn optimal policy maximize long-term accumulative global rewards through local optimization and information sharing.
Actor-critic methods for decentralized multi- reinforcement learning (MARL) facilitate collab- orative optimal decision making without central- ized coordination, thus enabling wide range of applications in practice. To date, however, most theoretical convergence studies for existing actor- critic decentralized MARI. methods are limited to the guarantee of stationary solution under the linear function approximation. This leaves significant gap between the highly successful use of deep neural actor-critic for decentralized MARL in practice and the current theoretical un- derstanding. To bridge this gap, in this paper. we make the first attempt to develop a deep neu- ral actor-critic method for decentralized MARL, where both the actor and critic components are inherently non-linear. We show that our proposed method enjoys global optimality guarantee with finite-time convergence rate of OL1TT), where T is the total iteration times. This marks the first global convergence result for deep neural actor- critic methods in the MARL literature. We also conduct extensive numerical experiments, which verify our theoretical results.
Among a large number of methods for solving MARL, prob- lems, the family of actor-critic methods have become in- creasingly popular. This is primarily due to the fact that actor-critic methods combine the strengths of two most fun- damental and basic RL approaches, namely aalue-based and policy-based RL approaches, thus achieving the best of both worlds while avoiding their pitfalls. Specifically, in actor-critic approaches, the critic component performs pol- icy evaluation to estimate the value or state-action function for the current policy, while the actor component leverages the policy evaluation information to compute policy gradi- ent to update policy parameters. On one hand, with policy evaluation, actor-critic methods share the similar benefit of effective data usage as in value-based approaches. On the other hand, by exploiting policy gradient information, actor- critic methods are versatile and can easily handle many RL complications in practice (c.g.. infinite or continuous state and action spaces). Moreover, thanks to the use of policy gradients, actor-critic methods can incorporate numerous insights and techniques from decentralized gradient-bass optimization, making them particularly appealing for decen- tralized MARL.
1. Introduction
1) Background and Motivations: Decentralized Multi- agent reinforcement learning (MARL) (Littman, 1994; Lauer and Riedmiller, 2000; Lowe et al., 2017; Zhang et al., 2018; Omidshafiei et al., 2017), generalization of tradi- tional single-agent reinforcement learning (RL) (Kaelbling et al., 1996; Sutton, 2018; Arulkumaran et al., 2017) has
To date, while actor-critic decentralized MARL methods have shown great empirical promises in various applications (Foerster et al., 2016; Omidshafiei et al., 2017: Naderial- izadeh et al., 2021; Feriani and Hossain, 2021; Li al., 2022), the theoretical foundation of actor-critic decentral- ized MARL remains in its infancy. Although there have been recent efforts on addressing the theoretical gaps in MARL (Hairi et al., 2022), many fundamental problems re- main wide open. There are two major technical limitations in actor-critic decentralized MARL that could significantly diminish the long-term applicability and promises of actor-
'Equal contribution 'The Ohio State University, Colum- White-
bus. Ohio, USA UUniversity of Wisconsin-Whitewie water. Wisconsin, USA University of Colorado Boulder, Boulder, Colorado, USA. Correspondence to: Zhiyao Zhang <zhang odw. Jia Liu <liueu....su..duu>.
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Fimite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
critic MARL if they are not well addressed.
lead difficulty in theoretical analysis. Specifically, compared decentralized MARL actor-critic methods with linear function approximation in critic (Chen et al., 2022; Hairi et al., 2022), the order between the critic's nonlinear operator and the consensus operator cannot be interchanged, rendering the proof techniques of (Chen et al., 2022; Hairi et al., 2022) ineffective.
(1) Critics with Linear Function Approximations: To date, most existing works on actor-critic MARL methods (e.g., Zhang al. (2018); Chen et al. (2022); Hairi et al. (2022)) adopt linear functions approximate value or state-action functions of a given policy. Although the use of linear function approximations is more tractable for theoretical analysis and indeed yield some interesting preliminary understandings of actor-critic MARL meth- ods, it violates the settings of most actor-critic decen- tralized MARL methods in practice, particularly those with nee--neurll-eetwork (DNN)-based critics that are not only nonlinear but also non-convex.
(3) Even when only aiming for a stationary point, the afore- mentioned challenges persist. Furthermore, achieving the global optimum is even more challenging. This is because the gradients derived from the descent lemma, which are sufficient for establishing theory for stationary points, cannot fully capture global information. Toward this end, new techniques are required to handle the up- dating sequences effectively.
(2) Stationarity Convergence Guarantees: So far, most the- oretical analyses for actor-criti decentralized MARL methods only ensure the convergence to some stationary solution (Zhang et al., 2018; Hairi al., 2022; Zhang et al., 2021b), which is a rather weak performance guar- antee and merely serves as a necessary condition of local optimality. For actor-critic decentralized MARI,, little is known on how to develop algorithms with global optimality convergence guarantee.
3) Our Contributions: The major contribution of this work is that we overcome all the above challenges and develop a new actor-critic algorithm for decentralized MARL with nonlinear function approximation in the critic, which offers global optimality convergence guarantee, To our knowledge, this work takes the first step toward establishing a theoretical foundation for actor-critic decentralized MARL methods by affirmatively answering the above question. Our main technical results are summarized as follows:
All the above technical limitations indicate significant gap between many empirically well-performing actor-critic decentralized MARL methods and the current inadequate theoretical understanding of the design and anal- ysis of the actor-critic decentralized MARL algorithms. Hence, an important question naturally arises:
We propose the first DNN-based actor-critic algorithm for fully decentralized MARL problem, which con- verges to global optimality with rate of O(1/T), where T is the number of total iterations. Moreover, we show that, to achieve an e-glohal-optima solution, our algo- rithm enjoys a sample complexity of ((1e²))
(Q): Could we develop efficient actor-critic methods for decentralized MARL with DNN-based nonlinear func- tion approximation in the critic component to offer global optimality convergence guarantee?
We note that our theoretical analysis effectively ad- dresses all aforementioned technical challenges. In par- ticular, to tackle the challenges posed by the interplay of decentralization and nonlincarity, we design a new technique that maintains pseudo-centralized values to couple decentralized values after nonlinear operation. (cf. Remark 6).
2) Technical Challenges: It turns out that answering the above question is highly nontrivial and involves overcoming at least three major challenges outlined as follows:
(1) Existing actor-critic algorithms for single-agent RL with nonlinear function approximation in critic, which of- ten demand meticulous error control analysis, are in- adequate due to the distributed nature of MARL. sys- tems. This challenge arises from the computation of global quantities (e.g., advantage functions and global TD- (Zhang et al., 2018; Hairi et al., 2022). While a centralized server can partially mitigate this issue, the lack of direct global information sharing among agents in decentralized MARL makes it exceedingly challeng- ing to adapt single-agent actor-critic RL methods with nonlinear function approximations in MARL.
To verify our theoretical results, we conduct extensive experiments. First, we perform ablation studies in a small-scale MARL environment to demonstrate the im- pacts of various parameters on the algorithm. Interest- ingly, our results reveal that the use of TD-error in our algorithm yields significantly better performance than the use of Q-values in existing works. Moreover, we implement our proposed algorithm on a multi-objective alignment problem to demonstrate the effectiveness of our method in RLHF (reinforcement learning from hu- man feedback) for large language models (LLM).
(2) Even if one employs consensus techniques among decen- tralized agents to alleviate the above challenge to some degree, the resulting error, compounded by inaccuracies inherent in nonlinear function approximation, could still
2. Related Work
In this section, to put our work into comparative perspec- tives, we provide overview on two lines of related research:
2

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
(I) single-agent actor-critic RL algorithms with DNN-based nonlinear function approximation in critic; and (2) the de- velopment of MARL algorithms.
deep neural networks we use and the associated critic opti- mization problem in Section 3.2.
3.1. Problem Formulation
1) Single-agent Actor-Critic RL Algorithms: In the vast literature of single-agent RI., the actor-critic framework has received a significant amount of attention. The actor-critic framework combines the strengths of policy gradient meth- ods and sample efficient policy evaluation of value-based methods and has demonstrated impressive capabilities. Re- cent works (Castro and Meir, 2010; Maei, 2018; Xu et al., 2020a;b) have established and improved the theoretical con- vergence results of the single-agent actor-critic framework, primarily focusing on linear function approximations. More- over, recent studies have started to explore the theoretical foundation of actor-critic methods equipped with neural networks (Gaur et al., 2023; 2024; Wang and Hu, 2021). However, the theoretical results of single-agent actor-critic RL cannot be directly extended to decentralized MARL set- tings due to the inability to compute global quantities in single-agent decentralized settings.
1) System Model: We model an MARL problem as graph network G (N,E), where the node set N' (1. NN represents the N agents, and the edge set ε specifies the pairs of agents that can directly communicate. The consensus weight matrix associated with graph G is denoted as A. We consider a multi- agent Markov decision process (MAMDP) denoted as (S,
fr')e,, Y. G). where S is the state space, A is local action space for agent i, A ITeN A' is the joint action space, P 8 x A S + [0, 1] is the global transition matrix, r" : S x A - I is agent i's local reward, and E 10, is the discount factor. No- tably, we consider a "restart" kernel defined as P(s, a, = >P(s'ls, |ss a) (1-+(1) and I[-}} denotes the indicator function that outputs 1 if the event holds, and 0 otherwise. As shown in Section 4, this restart kernel significantly simplifies the gradient compu- tation. In MAMDP, each agent follows a local policy I² parameterized by 0 to determine its actions. The joint policy is denoted as л = llieN T², with the correspond- ing global parameter 0 = (O)ec(())) ..... (vec((N)) where vec(-) turns the parameter / into a vector.
- =. where so is the initial state,
2) MARL Algorithms: MARL problem in the tabular set- ting was first explored by (Littman, 1994; 2001; Lauer and Riedmiller, 2000) for competitive and cooperative settings respectively. In recent years, research has increasingly fo- cused on MARL with function approximation (Arslan and Yüksel, 2016; Zhang et al., 2018; Hairi et al., 2022) to ad- dress problems with large state-action space. However, these works have notable limitations as follows: (1) Foerster et al. (2016); Lowe et al. (2017) assumed the presence of a central- ized server, thus not suitable for the decentralized MARL; (2) (Zhang et al., 2018; Hairi et al., 2022; Chen et al., 2022; Hairi et al., 2024; Zeng et al., 2022) focused on theoretical studies on decentralized MARI. algorithms with linear func- tion approximation assumption, which are often violated in practice since most empirical actor-critic MARL algo- rithms adopt nonlinear DNNs; (3) While Gupta al. (2017); Omidshafiei et al. (2017); Foerster et al. (2016) consider deep MARL algorithms, they provide only numerical results without any theoretical finite-time convergence rate analysis. Moreover, most theoretical results in the MARL literature only guarantee convergence to a stationary solution (Zhang et al., 2018; Hairi et al., 2022; Zhang et al., 202 while results on achieving global optimality convergence remain very limited. Although (Chen al., 2022) indeed guaran- tees global convergence, however, their algorithm is based on linear function approximation. In contrast, we proposes DNN-based actor-critic algorithm for decentralized MARL with finite-time global optimality convergence guarantee.
2) Problem Statement: We consider a non-competing set- ting, where all N agents cooperatively maximize the to- tal rewards. Specifically, a MAMDP models sequential decision- process with the aim maximize the long- term discounted cumulative system- widde reward as follows:
DO Exten .(I)
=0) E
Tit1 iEN
where F, = t EieN ri. The goal of the MAMDP is to find an optimal policy 0* that maximizes (0).
3) The Actor-Critic Approach. In this work, we consider using multi-agent actor-critic algorithm with DNN-based critic to solve the decentralized MARL problem. As noted earlier, the actor-critic framework is well-established in the literature (Sutton, 2018; Mnih et al., 2016; Xu et al., 2020a). This framework alternates between two processes: the critic estimates the value functions for given policy, and the actor improves the policy based on the critic's policy evaluation result and following policy gradient directions. To com- pute policy gradients, we first define the state-action value function, i.e., Q-function, associated with the MAMDP is defined as follows:
3. Problem Formulation and Preliminaries
In this section, we first introduce the problem formulation in Section 3.1, which is followed by preliminaries the
Qu(s,a) =- =- Σ
Fr 80 8, 40 = a, To)
(2)
1=0
3

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Intuitively, Qa(s, a) represents the "goodness" of the state- action pair (8,a) under policy ne. However, the exact Q-function values are unavailable during learning. Thus, we use DNN parameterized by W (cf. Section 3.2) as the model of (s, a; W), which approximates the Qo(s, a) value. To bootstrap the Q-function estimation, we define the Bellman operator Ro for policy To as follows:
approximation theorem, which says that under sufficiently
large depth width, fully connected neural network can accurately approximate any functions (Jacot et al., 2018; Gao et al., 2019; Allen-Zhu et al., 2019; Liu et al., 2024). We adopt the same fully connected network structure in the actor of each agent E N, which is similar to (Liu et al.,
2020a; Gaur et al., 2024). The only difference in our DNN is the addition of Softmax layer the output to represent a probability distribution. The input to the DNN is the current state E S. The output of the DNN is an action E AA', For simplicity, we assume |A') to be the same for all i E ... Consequently, the local policy Ti is parameterized by the vector l: of dimension m (Dm + d + 1).
THH Q(s, a; W) - -Bg (F((s)) + Q d(:))
(3)
where expectation Eg is taken over 8' ~ P(-1s,a),ed ~ To(-ss'). Since Qo is the fixed point of TM, we define an optimization problem to estimate (a(s, a) in Section 3.2. In addition, we also define the following advantage function:
2) Optimization Problems for Policy Evaluation: For given policy тe, since Qs is the fixed point of Bellman operator defined in Eq. (3), we can find Qo by solving the following minimization problem:
Adve(s,a) Qo(s.a) - EENNo (Qo(s,a)).
(4)
3.2. Preliminaries
1) Deep Neural Networks (DNN): As mentioned earlier, most of the existing works on actor-critic MARL methods rely on linear function approximations for policy evaluation (i.e.. critic) (Chen et al., 2022; Zhang et al., 2018: 2021b; Hairi al., 2022). However, linear function approxima- tions are not rich enough for complex MARL scenarios. To address this limitation, we adopt DNNs in critic and actor to approximate Q-functions and represent policies, respec- tively.
(6) where x follows the stationary distribution v(0), which will be introduced in Lemma 5.4. Eq. (6), referred to the mean- squared Bellman error (MSBE) (Cai et al., 2019), quantifies the gap between the approximation Q and the true fixed point Qe under parameter W. A surrogate of MSBE is the projected mean-squared Bellman error (MSPBE) operator, which defined as:
Specifically, each agent i's critic maintains a DNN-based local approximation Q(: Wi) to approximate Qe, where W denotes the weights of critie DNN, which is of width m and depth D. For any state-action pair (s, a) E S x A, we use one-to-one mapping & such that x = ((s.a) E R Without loss of generality, we assume || 12- = 1. For simplicity, we use (s. and x interchangeably throughout the rest of the paper. The structure of the DNN is as follows:
MSPBE(W)) (I= 0
where II is the projection map onto the function class F.
4. The DNN-Based Actor-Critic Method for Decentralized MARL
1) Algorithm Overview:
Our proposed DNN-based actor- critic method for decentralized MARL is presented in Al- gorithm with Algorithm 2 serving as its critic component. The overall algorithm in Algorithm employs a double- loop structure. The inner-loop, corresponding to the critic in Algorithm 2, runs K iterations to approximate Q-function using temporal difference (TD) learning. The outer-loop in Algorithm iterates T rounds, where in each round, the policy 0 is updated using the newly obtained Q-function approximation from the inner-loop. Moreover, a gossiping technique (Nedic and Ozdaglar, 2009) is used both the actor and critic to efficiently broadcast local information. This enables consensus process and effectively addresses the decentralization challenges of the problem.
(0) Hz, y = 6T (D))
(A) 1 m
ReLL (1-11))) for any h E [D],
(5)
DI....,D), H mad W()) E Rmxm and b E RT are the parameters of the DNN, ReLU(z) == max(0, is the ReLU activation func- tion. To initialize parameters, we let all entries of H and w(k), vh E [D] follow (0)2) independently, and those in b follow A/(, 1) independently. During training, only W =(ve ...., ())( is updated while H and b remain fixed. Hence, we simplify the notation (0 W. H) to (x;x;W)
where [D]
The DNN structure adopted in this paper is the so-called fully connected network (Sainath et al., 2015; Schwing and Urtasun, 2015), which possesses several important theoreti- cal properties. One key property we leverage the universal
2) The Critic Component: Algorithm 2 shows the critic component of our algorithm. Given the current policy Tg.- each agent E N' leverages TD-leaming to approximate Qo.- Specifically, in each iteration i of the total K iterations,
4

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Algorithm 1 DNN-based Actor-Critie for Dec. MARL.
Importantly, after each TD learning update, the parameter is projected onto a projection ball with a radius of B > 0 and centered on the global initial parameter (*))) = W (0). This projection step ensures non-expansive property that will be useful in our subsequent theoretical analysis.
1: Input: step-size dg2 initial parameters 68 for all i E N.
2: for [ = 0, , T-
1 do
3: Let W $1,0 be output of Algorithm 2.
4: for / = 1.,1.......4 M 1 do
5: for i E .V do
Lastly, since all N agents update their parameters based on local data, upon the completion of K local update iterations in critic, each agent performs the consensus process using the gossiping technique (communicate only with local neigh- bors and perform local weighted aggregations) to aggregate information from neighboring agents. The gossiping process will be executed for gossip rounds. This iterative weighting process ensures reaching a near consensus on the average information across all agents (Nedic and Ozdaglar, 2009; Zhu al., 2021; Hairi et al., 2022: Zhang et al., 2021a). To state the gossiping process, we collect all aggregation weights and form a consensus matrix A as follows:
6: Observe: 81,1+1 and r r1,1+-
7: Sample: d'.411 ~ Tég (-181,44).
8: Compute: Vi,1 V log oof (St,), a.,))
9: Compute of = Q(SL,) ani W.): - 1,141
7Q($1,+1, 01,411 Wi).
10: end for
11:
end for
67,0
%
12: Stack Åo-
8y M
8 -1
13:
Compute Á = A A'sosip DJ-
Definition 4.1 (Consensus Matrix). A consensus matrix A E RNXN associated with the graph G = {[V,E} is defined as follows: (i) The (i. element A, = if (i.j) & &, implying agents i and j cannot share information directly; and (ii) A > 0 denotes the weight between two agents when they communicate with each other.
14:
for E .N do
15:
Assign ,/ Á (ii,:) T.
16:
Compute: di T7 Σ M5
1
Li=0 1%
17:
Update: 1 = f + as |
di
18: end for
19:
end for
Using the consensus matrix A, the consensus process across all agents can be compactly written in matrix form as WK- = A A'sonic W, where W := (W ...., W.
20: Output: 8 for all E N (i.e., 0r).
Algorithm 2 DNN- Based Critic for Decentralized MARL.
3) The Actor Component: As shown in Algorithm the actor component runs T iterations. In each iteration I, agents first receive the updated consensual parameters from the critic. Subsequently, a Markovian batch sampling of length M is employed. In this process, agents maintain the local TD-error &i, and the local score function vi using the newly gathered Markovian data. This information used in computing the MARL policy gradient.
1: Input: Su, no,, step-size 3, iteration number K, con- sensus weight matrix A, gossiping times goosiip-
2: Initialize: BBB {W |[((h) (O)le &
B, vh E [D]. (0)) = W = V..).
3: for k = 0, 0.1.,..,
do
4: for E do
5: Sample the tuple:
(sk, dh. T sk41, af+.).
where of ~ Th (-1sx).
However, since the policy gradient computation is based on the visitation measure of the policy as shown in (Sutton, 2018), directly evaluating the policy gradient is challeng- ing. Fortunately, thanks to the restart kernel, we obtain the following key result that significantly simplifies the policy gradient computation.
6: Compute TD-error: o% = Qsk,, axi ((()) -
rk-1 1--1-1Q1 Q axt1i (k)).
7: Update: Wi(k + 1) = wi(k) - B8%
Vw Q(RK ax; (k)).
8: Project: W'(k + 1) = arg argminwes(n) IIW
W'(k + 1)]l2-
s,t) as the visitation measure, where (70 - s,t) t) is the proba- bility of visiting state 8 after L steps under policy ng. with starting state Sy. Then, under the restart kernel, the station- ary distribution v(-) is proportional to n(()) More specifi- cally. for any state s, we have v(s) = =1)7))ns)).
Lemma 4.2. Denote nTs) :- Li
9:
Update W Wi = k+1 W
E+z Wi(k 1).
142
10: end for
11: end for
12:
Gossip: Set W = (W1 "W!....,WAy Wx- = AloreW
13:
Output: 8K- WK.
We also note that the restart kernel not only provides the elegant "proportional" result above, but is has also widely adopted in the RL literature (Konda and Tsitsiklis, 2003;
agents first implement Markovian sampling according to policy Te. Then, each agent computes the local TD- error 5% and updates the parameter W. (k: + 1) based on o
Chen et al., 2022; Xu et al., 2020a). Based on Lemma 4.2, we can rewrite the policy gradient theorem as follows. Due
5

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
to space limitation, we relegate the proof' of Lemma 4.2 and Lemma 4.3 to Appendix B.
Assumption 5.3 (Bounded Reward). There exists a positive constant 7' "max. such that 0 & rf < Fmax for any & 3 0, E W..
Lemma 4.3 (Policy Gradient Theorem for MARL). For any parameter 0 of policy Te: S x A - [0, 1]. the gradient of (0) with respect to local purameter 0f can be writlen as: V [()) x Eg-u(0),anaa Vei gi log (aa)(a))) [s)_ Advo(s, a)}.
Assumption 5.2 and Assumption 5.3 are standard in MARL setting (Zhang et al., 2018; Hairi et al., 2022; Xu et al., 2020a). The former implies the existence of a unique sta- tionary distribution v(0), while the latter ensures a uniform upper bound for all instantaneous rewards. The long-term mixing time behavior of MAMDP is shown as follows:
However, the local TD-error 87, cannot be directly used in Lemma 4.3 since advantage functions, which represent the expectation of TD-errors, are defined over the global state- action pairs. To address this problem, we use the gossiping technique again to derive the consensual TD-error oū (cf. Line 12 in Algorithm 1). Lastly, the policy parameter 0,+1 is updated using the gradient descent method.
Lemma 5.4 (Mixing Time), Suppose Assumption 5.2 holds. There exist a stationary distribution v ffor (s. a), and positive constants K and p E (0.1), such that supses || P(sc, 0e|so 8) =(0]] & kpp,, VI > 0.
Assumption 5.5. For any policy 0, and any state-action pair (s,a), there exists a positive constant 14 such that the score function satisfies: V/Va log (a]s)]] < 1, Evto) (Vo log V log = = myd. where (s, a) ~ (f), and = denotes semi-positive definite.
Remark 1. It worth pointing out that Lemma 4.3 has an alternative form, where the advantage function Advø a) is replaced by the Q-function (s a). This approach has been adopted in numerous studies (Sutton et al., 1999; Lowe et al., 70 Cai et al., 2019; Gaur et al., 2024; Szepesvári, 2022). However, our numerical results in Section 6.1 show that the empirical performance of using Adva(s, a) signifi- cantly better than that of using Qo.s.a).
Assumption 5.6. For any policy 0, there exists a pos- itive constant Cbias such that: E(Advo(s, a) - (1
(F())
Ve log To (als)) & &biias where (s, a)
follows the visitation distribution under optimal policy n², F(0) = a log [a(a|s)V log To (aas)) T, andd? denotes the pseudo-inverss of the matrix.
Remark Since our Algorithms and 2 compute Q- functions, global state and global action are needed in the algorithms. We note that this requirement not always restrictive and has also been adopted in the literature (Zhang et al., 80 Zeng et al., 2022; Wai et al., 2018). As a concrete examplc, when using MARL for optimizing the performance of the carrier sensing multiple access (CSMA) protocol of wireless random access networks, participating devices (agents) can listen to packet signals transmitted over the channel and be aware of the actions other devices have taken. In general, applications may include any system where the agents can observe one another for information sharing, including robotics, drones, vehicles, and beyond.
Assumption 5.5 implies the Fisher-information matrix is non-degenerate (Yuan et al., 2022; Fatkhullin et al., 2023), and Assumption 5.6 indicates that the advantage function can be approximated by using the score function (Ding et al., 2022; Agarwal et al., 2021). Note that our parameterization guarantees the use of Gaussian policies, and (Fatkhullin et al., 2023) further suggests that Assumption 5.5 holds in many scenarios. These two assumptions provide the following key lemma (Agarwal et al., 2021), which reveals the relationship between global optimality gap and the gradient of J. which is stated as follows:
5. Theoretical Convergence Analysis
Lemma 5.7. Under Assumption 5.5 and Assumption 5.6. for any policy 0, it holds that v/u (J(0') - (()) < é' +
In this section, we start by introducing some assumptions and associated supporting lemmas, followed by the main theoretical results and important remarks.
2 a'd P
[ where μ ==
Assumption 5.8 (Lipschitz Continuity). J(0) and Qo(x; W, b) are L,- and Lw-Lipschitz continuous w.r.t. 0 and W, respectively, i.c., there exist some positive con- stants L, and Lw such that, for any 0 and 6', and for any W and W we have:
Assumption 5.1 (Consensus Matrix). The consensus matrix A is doubly stochastic and there exists a constant 1) > 0 such that Aa > 17, vi E N, and A.j > if (i, E
Assumption 5.1 is widely adopted in decentralized appli- cations (Hairi et al., 2022; Nedic and Ozdaglar, 2009; Zhu et al., 2021; Oh et al.. 2025). This assumption also ensures that AT remains doubly stochastic for any T > O.
(J(0) - ((O)] < L,110 - -1
[Q. W, Q0(:; W', HI < LwllW- - W'll2-
Assumption 5.2 (Markov Chain). For any 3 E S, a² E A Vi E [N], and 8¹, Vi E [NV] suppose Tg. (a'ls) > O, and T (at s) is differentiable w.r.t. 8². In addition, the Markov chain { t > 0 irreducible and aperiodic.
Assumption 5.8, known as the smoothness condition, is also standard in the literature (Fatkhullin et al., 2023; Gaur et al., 2024; Xu et al., 2020a; Hairi et al., 2022). This makes it possible to establish the descent lemma in analysis.
6

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Assumption 5.9 (Universal Approximation), Suppose for any policy 0, the critic estimation ((; W*), where W* is called a stationary point and is defined in Fact C.3, can be close enough to the ground truth Qo(-), i.c. there exists a positive constant fartii such that: maxo,= (a;;; W*)
associated with controlling the gap between the update di- rection d, and true gradient V-((t)) in every iteration t. Specifically, to bridge de and (.)()), we introduce an in- termediate direction d7 derived from W instead of local Wi's to compute TD-errors, and aim to bound ||de 164e-60 di 1|2 and |d, - (0,,)l On the one hand, ||d; J..()l can be decomposed into three components: the limitations of op- timal network's 's representational capacity, the gap between TD-error and advantage function, and the error caused by insufficient gossiping in actor. These components ultimately give rise to terms (3), (4) and (5), respectively. On the other hand, ||d, - dž | is even more tricky to handle. To this end, averaged W and pseudo-centralized V are delicately intro- duced as extra intermediate terms. Ultimately, terms (5), (6), and (7) are used to control this term. Overall, it is worth noting that all these terms can be effectively controlled by increasing the network size, the number of gossip iterations, and the batch size of Markov sampling.
(z()) & Eeritic-
The above assumption describes the approximation quality of critic networks: for any policy 6, the optimal fully con- nected neural network able to accurately approximate the Q-function for any state-action pair (s, a).
Now we are ready to present the main result while deferring the detailed proof to Appendix C due to space limitations.
Theorem 5.10. Under all stated assumptions, by selecting TVT 022 E, 3 = 1/VK, m S(d ) B ① th D- and K= = (DDD),, then with probability at least 1 - expp(S2((lg) 2 m)), Algorithm I satisfies:
7
E (J( - ((rr)
Remark 4. Theorem 5.10 demonstrates that Algorithm I converges to the neighborhood of the global optima at a rate of (1/T)) Compared to the sfate-of-the-art MARL actor-critic algorithm with linear approximation (Hairi et al., 2022), our convergence rate remains the same, highlighting that our carefully crafted design and analysis effectively address the challenges of non-linearity. Furthermore, our approach achieves global optimality, as opposed to merely converging to a stationary point measured by [()] This global convergence guarantee follows from Lemma 5.7 and the subsequent precise control. Specifically, combin- ing with descent lemma. Lemma 5.7 transforms the task of handling iterative relations between consecutive steps into bounding the gap between J (0.), Vt and the global optimal policy J(8)). We note that our analysis techniques in prov- ing global optimality could be of independent interests in the RL literature.
= =0(T')) 10
+ 0 (Caritic)
Chias
(1)
(2)
(3)
+ ON :)
+ + + m D-
# (1 17 N2 1000
(4)
+ N D- 4
(6)
+ o (N D- K k- + +O(N 24 D
(7)
The following results immediately follow from Theo- rem 5.10:
Corollary 5.11 (Sample and Communication Complex- ity). To achieve an e-accurate point, i.e., to ensure E (J((+)) - (Or)) & E (Cenitic + VEbias), for any con- stant E > O, setting T = )) M = =>(Ne=)), and K = 21) yields the following sample complex- ity T(NK- + NM) -. In addition, selecting gonsip = 2ilog N²¹ yields the following communication complexity: 2T goossip- O log N²
Remark 5. Compared to (Gaur et al., 2024), which intro- duces an actor-critic framework for single-agent RI. sce- narios with DNNs, we note the following facts: (1) Unlike the i.i.d. sampling assumption in (Gaur et al., 2024), our method operates under the more realistic Markov sampling setting and effectively addresses the associated noise. (2) While (Gaur et al., 2024) claims a Ō(Dåm t)) bound for the global error, this result does not align well with empirical observations: deeper networks often yield better performance. In contrast, Theorem 5. reveals that the dominant orders for the width and depth of the neural net- works are D-4 and m क,, respectively, which closes this gap. Our improved bound reveals an important insight that increasing depth of DNN will significantly improves the algorithm's 's performance, while varying width has little impact on the overall performance.
Several important remarks on Theorem 5.10 are in order:
Remark 3. To elucidate the insights of Theorem 5.10, we derive each term in detail. a) Terms (1) and (2) stem from the actor's 's iterations, and can be derived iteratively by Lemma 5.7. The first term diminishes as the total num- ber of iterations increases, while the second term remains consistently small due to the superior approximation ca- pability of neural networks. b) The remaining terms are
Remark 6. With an increase in the number of iterations fyossip in the gossiping technique in Algorithm 2, (i.e., ap-
7

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Agent
Upsine
Q-value
W
Wx
DNN Gossiping
Averaging
Agent 2
#
rg Averaging
Pioudo Contralized Upaane
Reword
Fk
V.
DNN
Agent
Figure 1. The interplay of decentralization and nonlinearity. plying the consensus matrix A on the parameter matrix W sufficiently many times), all agents' parameters will reach a new consensus. However, we note that this consensus pro- cess performed after each agent's 's nonlinear DNN learning, with infinite number
2009
Epiodde
Figure 2. Algorithm performed with TD-error and Q-value.
2) Experiment Results: Fig. presents our findings on the difference between (1) using the consented TD-error, as shown in Line 16 of Algorithm 1, and (2) replacing this TD-error with the Q-value, as shown in (Lowe et al., 2017; Cai et al., 2019; Gaur et al., 2024). Our algorithm, which incorporates the consensual TD-error, is highly ef- ficient, as agents achieve increasing rewards over time. In contrast, the Q-value-based method fails exhibit mean- ingful learning behavior, with rewards even decreasing over episodes. Notably, when using the Q-value approach, the gossiping technique in the actor step is theoretically unnec- essary, potentially reducing computational costs. However, our numerical results suggest that this theoretical advantage is offset by the Q-value-based approach's s poorer overall performance. More numerical results of ablation studies, which verify Theorem 5.10, can be found in Appendix D.
which yields systematic bias of gossiping rounds. To address this challenge, develop new technique to carefully analyze this bias.
Specifically, for any given policy 0, Assumption 5.9 gives optimal approximation W and we aim to bound the gap be- tween each parameter W K Wx (i, Vi E E and W7- After Egsssip iterations of consensus, W is already close to W- = =iEN W /NN, and our next goal is to characterize the difference between W and Wg. Unfortunately, since the order between the K' iterations of nonlinear operations and the gossiping process cannot be directly interchanged in our proof, we cannot view the results obtained from gossip- ing as simple averages of the raw local. This fact highlights the hardness in establishing the performance of nonlinear actor-critic and its fundamental difference compared to lin- ear actor-critic. To see the difference more clearly, as shown in (Hairi et al., 2022), when using linear approximation, the linearity enables a direct handling of the relationships between Wi and Wy.
6.2. LLM Alignment via Multi-Agent RLHF
1) Experiment Settings: To further validate our pro- posed algorithm, we conduct large-scale experiment with LLM to test algorithm's 's performance in multi-agent RLHF (Ouyang et al., 2022). The system architecture of our multi-agent RLHF framework is shown in Figure 3, where there are multiple local LLMs, each paired with its own reward model (RM) that has been pre-trained from local dataset. controller is responsible for communicating with the LLMs and initiating dialogue. Once the controller ini- tiates conversation by generating prompt (global state), the actor part of each LLM processes it and outputs re- sponse (local action). The response is then evaluated by the RMM, which returns a score (local reward) that numerically reflects the quality of response. Based on the obtained score, each LLM executes learning step and updates its weights, All local responses are aggregated into a final response and then shown to the prompting module, which generates the next prompt (state transition). Detailed experiment settings along with additional notes regarding our multi-agent RLHF implementation are provided in Appendix D.2.
To overcome the above nonlinear challenge, our key idea maintain a pseudo-centralizee updating parameter V. which collects local r; to obtain F, and applies it directly derive centralized TD-error, to bridge the gap between W and Wg (See Fig. 1 and Appendix C for more details).
6. Numerical Experiments
In Section 6. we first use simple environment to conduct ablation study explore the impacts of each algorithmic element. Then, in Section 6.2, we conduct a large-scall scale experiment with LLM to illustrate our method's 's efficacy when applied in RLHE
6.1. Ablation Study with the Simple Spread
1) Experiment Settings: We conduct ablation studies to verify Theorem 5.10. For this experiment, we consider a
modified version of Simple Spread (Lowe et al., 2017), a toy environment widely used in MARL. The details of setting and our modifications are provided in Appendix D.1.
2) Experiment Results:
Fig. 4 shows reward-versus- versus- episode illustrate the learning performance of multi-agent
8

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
LLM I (A gent)
Impact Statement
Score (Reward)
Crttic
Response (Action)
Reward Model
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Actor
Gossipaing
Prompting
LLM (Agent)
Actor
Response 2 (A (Ation)
Reward Model
References
Critic
Score 2 (Reward)
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. (2021). On the theory of policy gradient methods: Opti- mality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98);1-76.
Prompt (State)
Figure 3. A block diagram of multi-agent RLHF with two LLMs.
Ahmadian, A., Cremer, C., Gallé, M., Fadaee, M., Kreutzer, J., Pietquin, O., Üstün, A., and Hooker, S. (2024). Back to basics: Revisiting reinforce style optimization for learning from human feedback in LLMs. arXiv preprint arXiv:2402. 14740.
-0.5
Mean
Moving- Averged Reward
LLM DeBERTa RM
0.7
LLM
Gemma RM
0.
Allen-Zhu, 2., Li, Y., and Song, 2. (2019). convergence theory for deep learning via over-parameterization. In International Conference on Machine Learning, pages 242-252. PMLR.
-1.0
-1.1
100
Conversation Episode
Arslan, G. and Yüksel, S. (2016). Decentralized Q-learning for stochastic teams and games. IEEE Transactions on Automatic Control, 62(4):1545-1555
Figure learning performance plot LLM agents during multi- agent RLHF. Moving average was applied over every 5 episodes.
Arulkumaran, K., Deisenroth, M. P., Brundage, M., and Bharath, (2017). Deep reinforcement learning: brief survey. IEEE Signal Processing 344):26 38.
RLHF. We observe a steady increase in the average reward as the episodes progress, which validates our multi-agent RLHF framework. It is important to note that, despite vary- ing rates of improvement, the reward consistently increases for all LLMs, highlighting the efficacy of our decentralized actor-critic algorithm, effectively leading the agents to policy that benefits all through the gossiping technique.
34(6):26-
Bi, X., Chen, D., Chen, G., Chen, S., Dai, D., Deng, C., Ding, H., Dong, K., Du, Q., Fu, Z., et al. (2024). Deepseek LLM: Scaling open-source language models with longtermism. CoRR.
7. Conclusion
Cai, Q. Yang. Z., Lee, J. D., and Wang, Z. (2019). Neural cemporal-difference learning converges to global optima. Advances in Neural Information Processing Systems, 32.
In this paper, we investigated decentralized MARL prob- lems and proposed DNN- actor-critic method, which offers the first finite-time convergence guarantees to global optimality, and also enjoys low sample complexity. Our experiments on ablation studies and L.MM alignment further verified the effectiveness of our proposed algorithms. Our work contributes to advancing the understanding of MARL actor-critic methods with nonlinear function approximation.
Castro, D. D. and Meir, R. (2010). A convergent online sin- gle time scale actor critic algorithm. Journal of Machine Learning Research, 11:367-410.
Chen, 7., Zhou, Y., Chen, R.-R., and Zou, S. (2022). Sample and communication-efiiiee decentralized actor-critic al- gorithms with finite-time analysis. In International Con- ference on Machine Learning, pages 3794-3834 PMLR.
Acknowledgement
This work is supported in part by NSF grants CAREER 21209 2112471, and 2324052; DARPA grants YFA D24AP00265 and 1RO0011-5-2-0011 ONR grant N00014- 24-1-22 2--1-97 and AFRL grant PGSC-SC-111374-19s
Cui, J., Liu, Y., and Nallanathan, A. (2019). Multi-agent re- inforcement learning- based resource allocation for UAV networks. IEEE Transactions on Wireless Communica- tions, 19(2):22--743.

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Ding, Y., Zhang, J., and Lavaei, J. (2022). On the global op- timum convergence of momentum-based policy gradient. In International Conference Artificial Intelligence and Statistics, pages 1910-1934. PMLR.
Hu, E. J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, I.., and Chen, W. (2021). LoRA: Low-rank adaptation of large language models. arXiv preprint wxXi:2206.09685..
Dong, H., Xiong, W., Goyal, D., Pan, R., Diao, S., Zhang, J., Shum, K., and Zhang. T. (2023). RAFT: Reward ranked finetuning for generative foundation model alignment. arXiv preprint arXiv:230..0676.
Huang, S., Kanervisto, A., Raffin, A., Wang, W., Ontañón, S., and Dossa, R. F. J. (2022). A2C is a special case of PPO. arXiv preprint arXiv:2205.0913
Jacot, A., Gabriel, F., and Hongler, C. (2018). Neural tan- gent kernel: Convergence and generalization in neural networks. Advances in Neural Information Processing Systems, 31.
Fatkhullin, I., Barakat, A.. Kireeva, A., and He, N. (2023).
Stochastic policy gradient methods: Improved sample complexity for nesdge-ton- policies. In Inter- national Conference on Machine Learning, pages 9827- 9869. PMLR.
Kaelbling, I. P., Littman, M. L.., and Moore, A. W. (1996). Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 4:237-285.
Feriani, A. and Hossain, E. (2021). Single and multi-agent deep reinforcement learning for Al-enabled wireless net- works: A tutorial. JEEE Communications Surveys & Tutorials, 23(2) 1226-12222.
Kiran, B. R., Sobh, I., Talpaert, V., Mannion, P., Al Sallab, A., Yogamani, S., and Pérez, P. (2021). Deep rein- forcement learning for autonomous driving: survey, IEEE Transactions Intelligent Transportation Systems, 23(6):4909-4926
Foerster, J., Assael, A., De Freitas, N., and Whiteson, S. (2016). Learning to communicate with deep multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 29.
Konda, V. R. and Tsitsiklis, J. N. (2003). Onactor-critic algorithms. SIAM Journal on Control and Optimization, 12(4):11431116
Gao, R., Cai, T., Li, H., Hsich, C.-J., Wang. L., and Lee, J. D. (2019). Convergence of adversarial training in over- parametrized neural networks. Advances in Neural Infor- mation Processing Systems, 32.
Lauer, M. and Riedmiller, M. A. (2000). An algorithm for distributed reinforcement learning in cooperative multi- agent systems. In International Conference on Machine Learning, pages 535-542.
Gaur, M., Bedi, A. S., Wang,
D., and Aggarwal, V. (2023). On the global convergence of natural actor-critic with two-layer neural network parametrization. arXiv preprint arXiv:2306. 10486.
Li, T., Zhu, K., Luong, N. C., Niyato, D., Wu, Q., Zhang, Y.. and Chen, B. (2022). Applications of multi-agent reinforcement learning in future internet: A comprehen- sive survey. IEEE Communications Surveys & Tutorials, 2442):1240-1279.
Gaur, M., Bedi, A. S., Wang, D., and Aggarwal, V. (2024). Closing the gap: achieving global convergence (last iter- ate) of actor-critic under Markovian sampling with neural network parametrization. In International Conference on Machine Learning, pages 15159-15179.
Littman, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. In Machine Learning Proceedings. pages 157-163. Elsevier.
Littman, M. L. (2001). Value-function reinforcement leam- ing in Markov games. Cognitive Systems Research, 2(1):55-66.
Gupta, K., Egorov, M., and Kochenderfer, M. (2017). Cooperative multi-agent control using deep reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems, pages 66-83. Springer.
Liu, C., Liang, E., and Chen, M. (2024). Characterizing ResNet's universal approximation capability. In Interna- tional Conference on Machine Learning, pages 31477- 31515. PMLR.
Hairi, Zhang, 7.,, and Liu, J. (2024). Sample and communi- cation efficient fully decentralized MARL policy evalu- ation via new approach: Local TD update. In Interna- fional Conference on Autonomous Agents and Multiagent Systems, pages 789-797.
Liu, C.-L.,, Chang, C.-C., and Tseng, C.-J. (2020a). Actor- critic deep reinforcement learning for solving job shop scheduling problems. IEEE Access, 1771722-71762.
Hairi, F. Liu, J., and Lu, S. (2022). Finite-time convergence and sample complexity of multi-agent actor-critic rein- forcement learning with average reward. In International Conference on Learning Representations.
Liu, X., Yu, J., Feng, Z., and Gao, Y. (2020b). Multi-agent reinforcement learning for resource allocation in loT net- works with edge computing. China Communications, 17(9):200-236.
10

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Pieter Abbeel, O., and Mordatch, I. (2017). Multi-agent actor-critic for mixed cooperative-competiivv environments, Advances in Neural Information Processing Systems, 30.
instructions with human feedback. Advances in Neural Information Processing Systems, 35.
Sainath, N., Vinyals, O., Senior, A., and Sak, H. (2015). Convolutional, long short-term memory. fully connected deep neural networks. In IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 4580-4584. IEFE.
Luong, N. C., Hoang. D. T., Gong, S., Niyato, D., Wang, P., Liang, Y.-C., and Kim, D. (2019). Applications of deep reinforeement learning in communications and networking: A survey. IEEE Communication Surveys & Tutorials, 21 21(4))31333317
Sallab, A. E., Abdou, M.. Perot, E., and Yogamani, S. (2017). Deep reinforcement learning framework for tonomous driving, arXiv preprint arXiv:1704.002 1704.02532.
Maei, H. R. (2018). Convergent actor-critic algorithms der pollcy training and function approximation. arXiv preprint arXiv: / 880.07842.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algo- rithms. arXiv preprint 1771::7077.06347.
Mnih, V., Badia, P., Mirza, M., Graves, A., Lillicrap, T., Harley T., Silver, D., and Kavukcuoglu, K. (2016). Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning, pages PMLR.
Schwing, A. and Urtasun, R. (2015). Fully con- nected deep structured networks. arXiv preprint arXiv:1503.02351.
Shen, T., Jin, R., Huang, Y., Liu, C., Dong, W., Guo, Z., Wu, X., Liu, Y., and Xiong, D. (2023). Large language model alignment: A survey, arXiv preprint arXiv:2309. 15025.
Mordatch, I. and Abbeel, P. (2018). Emergence of grounded compositional language in multi-agent populations. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 32.
Sutton, R. S. (2018). Reinforcement learning: An introduc- tion. A Bradford Book.
Naderializadeh, N., Sydir, J., Simsek, M., and Nikopour, H. (2021). Resource management in wireless networks via multi-agent deep reinforcement learning. IEEE Trans- actions Wireless Communications, 206))350733523.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. (1999). Policy gradient methods for reinforcement learn- ing with function approximation. Advances in Neural Information Processing Systems, 12.
Nasir, Y. S. and Guo, D. (2019). Multi-agent deep reinforce- ment learning for dynamic power allocation in wireless networks. IEEE Journal Selected Areas in Communi- cutions, 37(10):2239-2250
Szepesvári, C. (2022). Algorithmss for reinforcement learn- ing. Springer Nature.
Wai, H.-T., Yang, Z., Wang. Z., and Hong, M. (2018), Multi- agent reinforcement learning via double averaging primal- dual optimization. Advances in Neural Information Pro- cessing Systems, 31.
Nedic, A. and Ozdaglar, (2009). Distributed subgradient methods for multi-agent optimization. IEEE Transactions Automatic Control, 54(1):48-6)
Oh, M. S., Zhang. Z., Hairi, F., Velasquez, A., and Liu, (2025). Consensus-based decentralized multi-agent reinforcement learning for random access network opti- mization. arXiv preprini 25Xiv:2508..7001.
Wang, D. and Hu, M. (2021). Deep deterministic policy gra- dient with compatible critic network. IEEE Transactions on Neural Networks and Learning Systems, 34(8):3332- 4344.
Omidshafici, S., Pazis, J., Amato, C., How, J. P., and Vian, (2017). Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In International Conference on Machine Learning, pages 2681-2690. PMLR.
Xiong, W., Dong, H., Ye, C., Wang. Z., Zhong, H., Ji, H., Jiang, N., and Zhang, T. (2023). Iterative prefer- ence learning from human feedback: Bridging theory and practice for RLHF under KL-constraint, arXiv preprint arXhv:2312.11455
OpenAssistant (2023). Reward model trained from human feedback. https:/hugginngace.oooOO ssistant/reward- wodel-deberra-vv--lagg-
Xu, T., Wang. Z., and Liang, Y. (2020a). Improving sample complexity bounds for (natural) actor-critic algorithms. Advances Neural Information Processing Systems, 33.
Ouyang, L., WU, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. (2022). Training language models follow
Xu, T., Wang, Z., and Liang, Y. (2020b). Non-asymptotic convergence analysis of two time-scale (natural) actor- critic algorithms. arXiv preprint arXiv:2005. 03557..

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Yu, C., Wang. X., Xu, X., Zhang, M., Ge, H., Ren, J., Sun, L., Chen, B., and Tan, G. (2019). Distributed multiagent coordinated learning for autonomous driving in highways based on dynamic coordination graphs. IEEE Transac- tions on Intelligent Transportation Systems, 22)3: 748.
Yuan, R., Gower, R. M., and Lazaric, A. (2022). A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332-3380. PMLR.
Zeng. S., Chen, T., Garcia, A., and Hong. M. (2022).
Learning to coordinate in multi-agent systems: A coordi- nated actor-critic algorithm and finite-time guarantees. In Learning for Dynamics and Control Conference, pages 278-290 PMLR.
Zhang, K., Yang, 7., and Başar, T. (2021a). Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384.
Zhang, K. Yang. Z., Liu, H., Zhang, T., and Basar, T. (2018). Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference on Machine Learning, pages 5872-5881. PMLR.
Zhang, P., Zeng, G., Wang. T., and Lu, W. (2024), Tinyllama: An open-source small language model. arXiv preprint arXiv:2401.023855
Zhang. X., Liu, Z.,, Liu, J., Zhu, 7.,, and Lu, S. (2021b). Taming communication and sample complexities in de- centralized policy evaluation for cooperative multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34.
Zhu, Z., Zhu, J., Liu, J., and Liu, Y. (2021). Federated bandit: A gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1-29.
12

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Appendix
A. Comparison of Different Algorithms
summarize the settings and performance comparisons related algorithms in Table
Algorithm
Scenario
Approximation
Convergence
Guarantee
Rate
(Xu et al., 2020a)
SARL
Linear
Global
OTT
(Gaur et al., 2024)
SARL
Linear
Global
O(T-1)
(Foerster et al., 2016)
MARL
Nonlinear
Stationary
X
NA
(Omidshafiei al., 2017)
MARL
Nonlinear
Stationary
X
NA
(Zhang et al., 2018)
MARL
Linear
Stationary
Asymptotic
(Hairi et al., 2022)
MARL
Linear
Stationary
O(T-1)
(Zeng et al., 2022)
MARL
Linear
Stationary
O
(Chen et al., 2022)
MARL
Linear
Global
0(7-1)
This Work
MARL
Nonlinear
Global
0(7-1)
Table Comparison of Different Algorithms.
B. Proof of Section 4
B.1. Proof of Lemma 4.2
Proof. We denote the 1-step state transition kernel P. (s + s' = E. P(s, (as)ss is written follows:
Pao (s s', yP 8 1) (1 >) so).
where 7 E (0, 1) and Il(s'= so} represents the indicator function of the event "the next state is the initial state su" " In the literature, this kernel is sometimes referred to the restart kemnel.
Next, and we will show that, under this restart kernel, the stationary distribution v(s) is proportional to the visitation measure (7ss) (Note: to be more rigorous, we call r7(s) as a "visitation measure" rather than "visitation distribution" here, because it's possible that v)()) > for some and hence not being proper distribution). The proof as follows:
Note that, for y 1, the visitation measure at state 8' is defined as follows and can be written recursive form:
n(5')
Σ
PP (s0 5, 11s' 50) + Σ (s)PP -
t=
then follows from the definition of (8()) that:
En = : y Pro (50 + 5(,)) Σ
00
'P no (So + +
Σ 7
00
1 1-
Now, we define the following "proper" distribution pas) by normalizing 1){:
7s()) ((s) = nss(ss) = (1 =1--))n(s)
In what follows, we will prove that uu()) is indeed the stationary distribution v(-) under kernel Pa.- Hence, the visitation measure is proportional to the stationary distribution. As result, the use of stationary distribution in the policy gradient caleulation remains valid. To this end, we first note that:
Enss) + +1,1) = Σ (s+
Em(s)l(s' 5o). s
13

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
which follows from the definition of (s 8', 1). Then, by using the definition uus) (1))))()), rewrite the above equation as:
further
[(s)) Es ( - (1 = (o) (1 -))(()) = mss)
This shows that uu(-) the stationary distribution v(+) under kernel Pxo and the proof complete.
B.2. Proof of Lemma 4.3
Proof. According to Sec. 13.2 in (Sutton, 2018), we know that
VoJ(0)= Σ nss) Σ Vno(als)Advo((s.))
Multiplying and dividing the right-hand-side by - and using v(8) (1 7))(s), we have that
VoJ(O)- (1 7) E( ()->))((s) 7)n(s) Σ V=olals)Adva(s..o)
which implies that
VaJ(O) x Σ v(s) Σ
Vag((ls)Advo(s.o)
a
C. Proof of Theorem 5.10
Proof. Our proof can be separated into three steps: (1) Dealing with actor iterations by induction; (2) Handling the main term of induction; (3) Combining everything together to get the results.
Step Induct on J(O.).
We first denote de = [(d)) ..... (d()) TJT as the global update direction in the t-th iteration of actor, and et de (.,))) as the gap between de and ground truth of the gradient. According to the first inequality of Assumption 5.8 and Algorithm 1, we have the following descent lemma:
-(((++)) < J((,)) - (V:(),, 0.+1 - 0.) + L2](0:+1 - 0,11
< <J,()) (O,) de)
+ L, 16:41 0.l12
d
(8)
< ((.)))) - -( + 80t
ar
eell + L - 0,113,
3
where the last inequality can be followed by considering two cases: ||e.|| < v and ||eal| > (())) In both
cases, we can easily get (...))))))) < 1 J(O,)) + - leell Then, let A, = J((*) - (O,) be the gap from global optima, ||de]|
and plug Lemma 5.7 into last inequality:
A41 <
(1-2ryp))
a 3
A +
8oy 1 3
VJ + I, L/
(9)
3
Now, the coefficient of A, is less than 1, we are ready induct A, over
akk akvT
A <
4
2=
1-1
0x-iv/1
+
Ilk
1) II
ar- (lid- VJ((O- +66)
(10)
3
1-1
OK-IVH
I(k 1)
(1
Oi
3
km
1=0
14

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Now, we appropriately select the step-size by letting constant Equation (10) can be further bounded as follows:
and Or 2. inspired by (Gaur al., 2024). Then,
2VF
D++1 & - + a 1-2
LJa² -d + t +
7 7
(11)
Since c' is a constant, and the first term and the second last term converge to 0 in a rate of 1 1/T, to bound the RHS, the key step control ||d,- VJ(O-)l
Step 2:
Upper bound || (O))l)
In order to further bound A to get the global optimality, we need to upper bound the second term in Equation (11). In this step, we use triangle inequality to decompose I|d, - v.)()) then we bound each term in decomposition. To this end, we first introduce some facts and notations for the proof later.
Fact C.1. For any vector u E R (m((+d+11) the squared Euclidean norm can be written as!
||0l12 = Σ 110
EE
where oA E [pm(m+d41) for any i N.
Fact C.2. Ler W. Eien Wi. Then, according to doubly stochastic A by Assumption 5.1, we have:
1 We = Σ Wi,K N
where W. is the output of Algorithm 2 for the outer loop indexed by and W W. is the i-th row of W,,,, K, i.e., the agent i's estimated parumeter after consensus process (In other words, W is W after K iterations in Algorithm during its 1-th leveraging in Algorithm 1). Here, W, can be regarded as the maintained pseudo-centralized parameter which is obtained after infinite numbers of consensus iterations.
Fact C.3. Let locally linear approximated Q-function be:
Qo(a; W) = (x: VW W(O)).
(12)
and corresponding TD-error be:
5o 80(2, -)
(13)
Then, if W* satisfies:
Beeaasvv (166(1,,,a'; (w (W- W*) > V, B(B).
(14)
then we say W* is a stationary point (since there is descent direction at W*). For any H, W()) and b, there exists stationary point W*, and Qo(:; W*) is the unique, global optimum of the MSPBE corresponding the projection (B).
Then, we introduce some notations. For policy To the corresponding stationary point is denoted as WP To introduce 5 (W;)) for any 1, and i, we first defint the following value:
(W:) = -Q ar,1; (e)) - ri.41 - QQ (,,44441,,0441 W7),
which replaces L in Algorithm by using the stationary parameter W instead of W.- Following that, we apply the same consensus process to attain ot, We denote d;" as the direction derived by (W;)) with the imple- mentation of Algorithm 1, and denote di [(T]:"),,... ,..., (..." (dN:+)TJT Then, let hz(WZ) / EM-1 (WW).. and (w?)) = [N?)W)
"...,, ,,,"" (W?)T]" TJT where (W,) = 1 EieN (W;)). Similarly, let (W, E E(Adv(s, as W)eee (s, a)), and (W, = (g' ......" g (W, () TJT where the (s,a) a) = Ve log Th. (s,a*).
N
15

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Now, we can decompose | J(O)) now using triangle inequality and Fact C.I::
| V=((
= -1|d dī + de - (wT) + (w7)) (W7, - 0,) - VJ(0,))12
6l] <6| di +611d hwTW) + (W7) - 9(W7, 0,)11 6 00) VO(01)1
(15)
<
Σ> | d 12 6 ieN
Σ | II +6 > (I((W)) (((W,,0)) Gll ;,) 0z) VJ())
iEN
IEN
Therefore, our objective turns to upper bound each term of the RHS of Equation (15).
Step 2(a): Deal with EieN ||
112.
To upper bound the sum for all E N, we only need to bound each of them. Thus, for any i N, we can first rewrite this term follows:
c|
de'
M
-1
M
8
(WT)
M
M
1=0
M
(16)
Σ
(ōt,
(Wt
M
M
Σ
A A (i, (Doll, -Ao(W))(L.)) : wi.l..
M
where (oW)) is the matrix in where every component (WF) replaces 6/21 in Do. and A'mas (i,:) denotes the i-th line of the matrix Atsrole These equalities can be easily derived from definitions. We now bound this new form follows:
M
1
A
A'omer
(i. (o(():)) (o(W)) ((W)))))) SElel1
M
1=0
max
||A
poop (i, :) Ao((::) (o(W))((.)) 2
A'mmar (i.:) (o((,:) Bo(w)) 11,
(17)
maxx
(i, (D(():)) 3.())) 2
< maxx
A
max 1.1
where the second last inequality is due the first inequality of Assumption 5.5, and the last one is due to the doubly stochastic property of A. Since every component in either Ån or Âo(W)) is TD-rmrr, we further bound the last equation as follows:
io(l, - (o(())(())))
Q(se. 1e,1 Wi) ri. - 7Q(50.41, W/) a
ar, + + (ell-++@@@$p000 7Q 01,41 W()
(18)
- (Q(SL) ai; Wt) Q(5 ae. W;)) + +1 ((((s..4) a141 W;) Q( (,.44 W:))
Q(0,,1, 0r,15 W/) ((s,,1, a.. Wt) + + Q 0.44:: - ( 00.41; Wi)
On the one hand, note that the two terms share the same form, thus, we only need to find uniformly upper bound for every state-action pair. On the other hand, to connect ((st.t, ae,; Wi) and Q(st,, ar, Wt), we also need to add and subtract some terms, and leverage triangle inequality. The first one to bridge W3' and W is W,, which treats the inaccuracy caused by gossiping and evaluating separately:
[Q 9 Wi) Q(5.. ar W
(19)
<IQ(st,) Wi) - Q(5,,1 ars Wi) + (Qt,, o13 We) - Q(1,, 01,1
01,1 W?)
16

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Algorithm 3 Centralized Critic with Neural Network
1: Input: 80, T step-size 3, iteration number K, consensus weight matrix A, gossiping times Égossips W(O) from
Algorithm 2.
2: Initialize: (B ( || (()) & B, [D]) V V(0) W(O).
3: for k = 0, .,..., K 2 do
4: Observe the tuple of all i E N agents: (8x, / i41 S141,
5: Compute TD-error: d₁ = (sk, aRi V(k)) fk+1 - (Q(=--I, OK+1i (())).
6: Update: (kk + 1) = (k) - 36g V Q 02: (k:).
7: Project: Vík + 1) = arg min IV V(k + 1)]12.
8: Update average V: V #42 V + K42
V(k + 1).
9: end for
10: Output: V.
The first term in Equation (19) can be upper bounded by gossiping techniques. By Assumption 5.8, the definition of B(B) and gossiping technique, the following inequality:
(2 a: Wi) ((,, (s, a; We)
<W I - Well
=Lw (1 (A( s. Wi,1
N W
(20)
-Lwll (Arroa))
TT W Wll
1, N
1
<Lw (A (m00)))
1 TTll [We,
N
Lww (N(1
11
O(BD)),
holds for any state-action pair (s, a). In addition, we also need to upper bound (s..,, a..1 Wt) ((s. ai,: W?)| in Equation (19). However, W, is actually not the centralized parameter in critic, but the pseudo-centralized parameter. To make it more clear, we introduce the real centralized parameter V,, which follows the updating process in Algorithm 3. Therefore, we can apply V; as bridge to bound the second term in Equation (19). Similarly, we denote V, as the output of Algorithm corresponding the outer loop indexed by t.
Therefore, by triangle inequality, have:
((1.,, aiii W.) Q( ars Wi)
(21)
ams Vi)l + (( V.) a22 < QQ(s), a: Wt) - Q(5,,, au:
as WF)1.
For the first term of Equation (21), since both W, and V2 belong to B(B), can bound it according to Assumption 5.8 and the convexity of B(F) BB)::
[Q(s,,, ars W.) - Qs,,, a,3i Vi)l
<!w W. V.ll
(22)
< OBBE))
For the second term of Equation (21), we have the following result: When setting R(ds/2 1og 2/ / BD
B Om22/2 D log -3 m), 3 KK, and O(K1/4), with probability at least exp 220lo m), we can bound this term as follows (Cai et 2019):
E (1Q(5) ae V.) - (sL au, W:)) < <o <O( B$m to D4) log m log K)
(23)
17

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL Plugging Equations (20), (22) and (23) into Equation (19), have:
E [2 (3r,,, Or,15 W2) - (ss,1, at ae, W
Tw (NV1 17 M 1) O(DD)) + Lw O(BD))
(24)
+ + (BDD + -- D2)) log² m log K)
with probability at least 1 - -e- e- m), Therefore, we can finally bound the expectation of Eien ||;;
112 as follows:
E
Σ ld - d;;"13
IN
<N(1 1) 7) LWO (NV1 - 1/ - -((B))) La L(BD)
(25)
(BDA + B is D*) log² log² K) K))²
o
=0 BN ni ())1220))in)) + O(NBDD) o (N B3mm DD) -log mlog K)
Step 2(b): Deal with ΣiEN ||db" hi(WW)11.
By the definitions, for any E N,, we have:
1 M-1
M-1
=1
Σ0 (W)))
Σ (wW())
M
M
(W,)) - 6..0
M
A A'moni (i,:) (i,))) 17) (du(())))) vi,,11
M
N () (Bex(W2)1) st.ll?
< max A 1omip (1.:)
< max ||A
(i,:)
N T 112 (W:) 1I
(a)
max A Tom (1,:)
1 1|2 (
(26)
N
<
<N|| (1.:)
T1I
max Σ (w:))
N
SEN
(i.:)
1
1
11
max i.!
(((s amt Wi) ri.41 0:41 W:)
N
(6)
A
(1.:)
1
max i,!
(rmax* + 1Qu, (8t,1, ar,i) + Cerine + (s,,441 (s.4411,,,0 + Meriic
N
(c)
(1 (1 + 1)rmax + 2ecritic)
&N (i.:) N
1
111..
(4)
< 4N(1 + +1z N1 N 2 (g (1+7 + 1)rmax + 2centic
=0 N2 - - 11)
where (a) is due to Assumption 5.5, (b) is due Assumption 5.9, (c) follows from (s, Tiaa for any policy 0 and any state-action pair (s, a), (d) comes from (Nedic and Ozdaglar, 2009), and x a positive constant. Therefore, we sum up
1-7
18

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
this result for all i N to get:
lld - -[(W))]== -N -170011110000 ) Σ EN
(27)
Step 2(c): Deal with ΣiEN [[] gr (Wz, 03)1
According to the definition of h² and g", we have:
[1 - g' 60)?
M-1
-11 M
(w, - E (Adv(s, a; a;;; (or,,a))) 1|?
1=0
M-1
(28)
(W7) (Adv(s, Wi) (s, a')) 1|
M
1 vin E (Aáv(s, W: (8, oh,, WWW).. E (Adv(s, a; We))) (s,a'))
M
where Adv(2; W) is the estimated advantage function given parameter W. The two terms in this inequality should be controlled separately. First, we have the following bound for any / E {O,..., M - 1}:
E 8 (W7) v - E (Adv(s, a; Wi) (s; 1|?
18.. 1 + ||B (Adv(s, a; W7 W (or d')) 112] (W:)) || + 21E (Adv W;)) 11 (o, 12)
22
<2
(6)
< <2.6,,, (WT)) + Aavs W;))
(29)
max 1
Elo,,(
+ m)mmxx + 2Ecmuie) )
-0 (c(mtt)))
where (a) is derived by triangle inequality, (b) is due to Assumption 5.5, and (c) is due Assumption 5.9. On the other hand, for the second term in Equation (28), we consider taking expectations conditioned on the filtration F., where F, denotes the samples up iteration t. Without loss of generality, assume / < l2 in the following incqualities:
E
( (WF) ve.. - (Adv(s, az We; (s, a²))
Se.ts (W;))tf (Adv(s, 0; W2 (s, a") a)) Fr]
E
E (bez (WT)), - E (Adv(s, W (s, a'))
- E (Adv(s, a; WT) (s, a²)
Fr.11
Fe
E
(Be, (WF) Whi, E (Adv(s, a; W No (s, a')
E (Wi) E (Adv(s, a: W a²) [Fe..)) /}
Fi
E
(Bra (W.)... E (Adv(s, az Wo Vang (8, a'))
E 8e,12 (W, (W;) )ell Frr - E (Adv(s, a; Wt Woy (0, ad') [ii
(e, (W;)) E (Adv(s, a; W Wh) (s, a')) ||. || Se. (W;)) Fun]]] E. (Adv(s, Wi) (s. at) || Fr
R
aa J4,12 (W7 2hh Frsn]] - E 1 1+ + 1)mmax + 2eeritic) E
F.
1 ++
+ 1) 1)maxx + 2eeriee))
E IE Adv(Se.to aris: WT Wor [Fo - -E (Adv(s, a: W7 (00 1|
1-7
(30)
19

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Now, we can apply the stationary distribution derived from Lemma 5.4 here to get:
|| at. W; 19: Fe..] -E (Addvss, (o a'))
=I1
Σ Adv(s : W Way (8t,12 02,22 ( P( 01,12 F(,)))
Σ
Adv(s, W;) (o) ('o. (s,a))
12
||dv(ss, a; W (o a')ll Ip' 4 (s, a(... - vo, (s.a)l
(31)
8,0
7 m)rmax + 2eariti)
|| (8, a(Fr.11)))))))))))))) vn, (8.
?
+ Y + m)maax + 2Eaitle) kppl-
Plugging Equation (31) into Equation (30), we have:
E
(dr.) (W)) (Adv(s, a; (i) (W7)))) (Adv(s, Wo) ) 2 kpp2-
(32)
1 + + 1)rmax + 2eende)
Finally, bound EiEN [}?(WW?) (W7, (,),, by substituting Equations (29) and (32) to Equation (28) follows:
[I((W))) 96 (W7, 0.)1
iEN
<N
1 1+7 M 0 ( (eittic) ) + +2((1 +
+ 1)rmax + 2eeritic
2
x pla-ts
11 11
(33)
0 (cittie) ) +4 (1 1+
+ + 1)rmax + 2eciitic
P
<
ki "1 p
M
N
=0
M
Step 2(d): Deal with [19(W,, 0.) 3
We can use Assumption 5.9 to upper bound the last term:
(lo(WT, 01) V]()))1
[Iuee)) (Adv(s, a; W; W;; Who (s) - Bu(o)) (Advo, (s. (s) 112
-I(Ev(o)) (Aáv(s, a; WT) (s, (s,(s, a)) 1|2
<Er(o.) Adv(s,a;Wy) W7) Adve, as) a) ?
(34)
< <2En(a))
Adv(s, a; Wi) + 2lE Advo, (s,
-0
(0(emn (eeiie)
Step Combine everything together to end the Proof.
We have already bounded each term of Equation (15). Now, are ready to combine them together. Specifically, we plug Equations (25), (27), (33) and (34) to Equation (15), thus, with probability at least eQQlog" m), we have the following
20

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
bound for any
E (11d - V)(
<0 CO B2
- -1)0 - + + (N + B3 DD log" m mlog K) + (1-
(35)
+ONNM- eenue) ((finie))
which further implies:
B (lld (0.))l
<0 C (1 -1 (1- -y)-- + + + (NA + B
D*) + log m mlog K)
+ +O(N N (1 v ()mm))))))) + + - + 0 Ecritic)
(
(36)
=N (1 -1ー1~~~ー ) +
BBm - DD*) log a m logå K)
+ o (antic)
holds for each f. Now, we can plug Equation (36) into Equation (11) when selecting & = T. By selecting 7 m /2 log 3/2 (m B)BD B D2 log m), 3 1/vK, and D O(K!/t), with probability least 1 - exp Allogg m), we have:
2/2" 8.
E (J(0") - [(rr)
=E (Ar)
1
L
T-2
Σ ||d, -
+e' + T
=E
T
(37)
00
) + +0 (V
+ a max E (lld) vJ((.)I))
<0
7 + ( (Veesan (N + 0 (<cmmee)
1
o
-1-1) (N
+ 0 O N ( + +O + Bšm 1mm-DD") log m log K)
which ends the proof by selecting B = 0mm2/2 9) and m = R(d D- ))
Remark. For the selection of parameters, i.e., the depth of the network D, the width the network m, the radius B, and the iteration times K, we discuss them as follows. Note that we ignore the logarithmic order throughout this remark.
As the depth D and the width two basic parameters, first determine the relationship between them. For fixed depth D, the width m should satisfy:
m = Ω a ((BBD))
(38)
where B = O( ((- and d is the dimension of input, which is a fixed value. Therefore, when
Ω d @ ")
(39)
holds, with B
= (2 we can easily attain Equation (38). Now, we can further select B and K such that B = Om2 and K = R(D*), and note that these are the only constraints. We focus on the selection of B, and see how it infects the result. Let B = (m D²), where 0 < < 1/2, & 66 are coefficients to be determined.
Formally, let a
a a
2. m 2(d D ! B = (m" D 8 1/VK, and K =((D)), where 0 < & 1/2,
v ج 6. Then, with probability at least exp 22oog m)) we have:
21

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
-(0r))
<0
+ +0 (Vebias) + O (Ecritic) + + (N+M-)
7
(40)
+ Ö ( Dut - ())aaa)))))) + +
m Du+
DDt
+ Ō i Dut x- i) + + [ m
16u-1
where we can select 0 < & 1/16 to at least cancel m in the last tenn. However, we find that in some terms, the width m is still positively correlated with the result. For example, let u = 1/32 and v = - 6, we have:
E (J(0") [(Or))
<0
1
+ O Ebiss) O (Forisse) + O (N
T
(41)
+ Ô
N 3 m 32
N- (1-1 + + ( m
+ δ N D k + ② (N D-1).
This result is somewhat surprising: when B= ( (322 D D-6), as the width m increases, the overall convergence error increases. On the other hand, when the depth D turns larger and larger, the error decreases. This tightens the bounds on depth D since the existence work only provides relatively loose bounds, and cannot infect this trend.
D. Additional Details of Numerical Experiments
D.1. Ablation Study
To further validate our proposed algorithm through numerical simulations, we consider the variant of Simple Spread, an environment from the MARL settings in the MPE framework (Lowe et al., 2017; Mordatch and Abbeel, 2018). We begin by deseribing the detailed setup of this environment, followed by presenting the corresponding numerical results.
Settings. In the modified S Simple Spread environment, we consider game with time horizon T and checkerboard grid of dimensions 13 x 5 (length by width). The environment contains N 2 2 landmarks, each fixed at a distinct position throughout the game. Additionally, N agents are randomly initialized at the start of the game and must coop- erate to cover (i.e., get as close as possible to) all landmarks. At each time step, agents select an action from the set {Up, Down, Left, Right, Stay], moving at most one unit on the checkerboard. Agents can communicate with each other according a randomly generated consensus matrix. In other words, the objective is that each landmark is supposed be covered by one agent. To guide the agents' learning, we define the reward signal as the negative of the total l distance between each landmark and its closest agent, summed over all landmarks.
is worth noting that several modifications have been made to the original Si Simple Spread environment: (1) A discrete checkerboard grid is used to bound the game area, replacing the unlimited continuous movement range; (2) The action set is defined directly as movement actions (e.g., Up. Down, etc.) rather than physical quantities such as velocity and acceleration, emphasizing relative positions. These modifications simplify the setup and facilitate the implementation of ablation studies.
Our default parameter setting is follows: We set time horizon T = 20000, the number of agents N = 2, discount factor = 0.99, the width of neural networks wn 20, the depth of networks D 5, the iteration times K = M = 1, learning rates a & 0.005, 3 < 0.001, and the gossiping times Egessip = 10. Consensus matrix A is randomly generalized to satisfy the doubly stochastic condition. Besides, we reset the environment every 10 steps: Instead of letting agents take I' consecutive actions, we reset all agents to random positions every 10 steps, defining this process as an episode. Each experiment is repeated for 100 times. Specifically, we implement the following ablation studies:
We consider different gossiping times (gossip form the set {0, 10, 20), where (gossip = implies that no consensus process in implemented in the algorithm.
We apply different neural networks with width m from the set {10, 20, 40), and different depth D from the set (5,20,400 40).
22

---

Fimite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
We consider different numbers of agents N from the set (2,3,4) 4).
We vary iteration times K and M. They have the following combinations: (K, (1,
We also conduct experiments comparing TD-error and Q-value. When updating policy B in iteration agent the gradient descent method is applied with direction dz which is computed using consented TD-error 8% As mentioned in Remark 3, Section 4, this TD-error can be replaced by Q-value function ((tt.t ae,3 W?). We fix all other default setups and implement both here.
Numerical results. Since the goal of Algorithm is to maximize the long-term total rewards, the reward signal serves as the most significant metric in this paper. To facilitate the ablation study, we present the following numerical results.
Figure 5 illustrates the benefits of the gossiping technique for Algorithm 1. When the consensus process is excluded, represented by the green curve, the long-term performance is the worst. In addition, ggsssp increases, Algorithm achieves progressively better performance. This aligns precisely with theory, (gossip appears as the exponent of 1 17 N in Theorem 5.10, which is strietly less than and consequently, larger gossip is expected to yield greater rewards.
Figure demonstrates the impact of neural network width on Algorithm 1. In our main theoretical result (Theorem 5.10), several terms involve m and m žं Although the dominant term, m म suggests that a larger m leads to better performance, the absolute values of both exponents are terribly small. Consequently, the choice of m not expected to significantly affect the performance of Algorithm 1. This is consistent with Figure where increasing m does not substantially enhance or degrade long-term rewards.
Nan-Geup
Ecrett
Figure Performances of Algorithm with different gossiping times gosipp.
Figure 6. Performances of Algorithm with different width m neural networks.
Figure Performances of Algorithm 1 with different depth D of neural networks.
ser
Figure 8. Performances of Algorithm with Figure 9, Performances of Algorithm with different number of agents N.
Figure 10. Performances of Algorithm 1 with TD-error and Q-value.
different number of iterations K and M.
Figure shows how the depth D of neural networks affects performance. As demonstrated Theorem 5.10, D always appears with negative exponents, meaning that increasing benefits algorithm. This is also reflected Figure where larger values of D correspond to higher reward values. worth noting that, while both our theoretical and numerical results align with practical experience, existing theory deep actor-critic algorithms (Gaur et al., 2024) does not provide such tight bounds for D, and therefore fails to capture this trend.
Figure indicates that an increasing number of agents leads to higher regret, representing the gap between the performance of Algorithm and the globally optimal policy. Theorem 5.10 shows that all exponents of N terms are all positive, reflecting the increased hardness of decentralized systems as their scale grows. This trend is accurately captured in Figure which illustrates the relationship between the performance of the proposed algorithm and the number of agents.
23

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Figure 9 suggests that increasing the number of iterations benefits the algorithm. Specifically, when K = M 1 by default, inaccurate critic approximations and insufficient policy updates hinder the performance of Algorithm 1. As shown by the red and blue curves, increasing either K or M helps mitigate this issue, indicating that larger batch sizes in Markov-batch sampling enable agents to achieve higher long-term rewards.
Figure 10 presents our findings on the difference between (1) using the consented TD-error, as shown in Line 16 of Algorithm I, and (2) replacing this TD-error with the Q-value, as done in (Sutton et al., 1999; Lowe et al., 2017; Cai et al., 2019; Gaur et al., 2024; Szepesvári, 2022). While both approaches are theoretically valid for computing the gradient descent direction d, at step 5. their empirical performances differ significantly. Our algorithm, which incorporates the consented TD-error, demonstrates efficiency, as agents achieve increasing rewards over time. In contrast, the Q-value-based method fails to exhibit meaningful learning behavior, with rewards even decreasing over episodes. Notably, when using the Q-value approach, the gossiping technique in the actor step is theoretically unnecessary. potentially reducing computational costs. However, our numerical results suggest that this theoretical advantage is not worthwhile, given the method's disastrous performance.
D.2. LLM Alignment via Multi-agent RLHF
Background. Reinforcement learning from human feedback (RLHF) is a widely recognized approach to align large language models (LLMs) with human preferences and intentions (Shen et al., 2023). In this framework, reward signals are designed to reflect human values that are too abstract to be quantified for supervised fine-tuning (SFT). Through RLHF, LLMs are trained to generate outputs more closely aligned with human preferences. While substantial research has been focused on centralized RLHF, studies the decentralized case, where learning occurs via multiple local LLMs reward models (RMs), are relatively limited. Decentralized RLHF can become a solution to large-scale LLM alignment tasks that may often face practical constraints like model privacy and computation capacity. To the best of our knowledge, our experiment is the first to consider a multi-agent framework for decentralized RLHF and provide a proof of concept.
Implementation. A common feature observed in current RLHF implementations is the absence of a separate critic, which serves as policy evaluator in classical RI. algoritmms. In RLHF, the role of critic is taken over by the RMM, providing both reward and state-action value to the agent. In such an architecture, however, the temporal difference (TD) computation step of our algorithm (e.g., Line 6 in Algorithm 2) may not yield error values that contribute to effective model evaluations. To prevent this, we maintain the classic architecture of actor-critic by adding separate critic network on each LLM and use the RM exclusively for reward acquisition. This approach also ensures that the critics across agents share the same network structure, which enables the gossiping technique.
We note that our proposed algorithm takes relatively simple model training steps compared to the proximal policy optimiza- tion (PPO) (Schulman al., 2017) that is commonly employed in prevalent RLHF frameworks. The goal of this experiment is not to compete with state-of-the-arr RLHF techniques but to evaluate the effectiveness of our multi-agent actor-critic algorithm over popular use case of decentralized RLHF. It is important to highlight that basic reinforcement learning algorithms have been shown to be effective in RLHF (Ahmadian et al., 2024; Huang et al., 2022). Hence, in this experiment, we only make minimal modifications to our algorithm and implement the multi-agent RLHF setting.
Experiment Settings. We consider three decentralized LLMs (i.c., N = 3), each adopting pre-trained TinyLlama- 1.1B (Zhang et al., 2024) for its actor network. To efficiently update the actor during RLHF, we apply the low-rank adaptation (LoRA) technique (Hu et al., 2021) of rank 8. For each critic network, we use a multi-layer perception (MLP) of m 256 and D= 3. and set fgussip = 20 for the gossiping technique. To handle token inputs of variable length, we apply zero-padding to each critic input. We use the Adam optimizer with learning rates 0.0001 and 3 = 0.0001 for both actor and critic updates, respectively. For TD calculation, we set the discount factor 7 = 0.5. We set K = -M- = 1 to make the samples used for each actor and critic be more synchronous.
To match the number of agents in our experiment, we use three distinct RMs, each of which we name DeBERTa RM (Ope- nAssistant, 2023), Llama RM (Xiong et al., 2023), and Gemma RM (Dong et al., 2023) as they have been pre-trained on different base models DeBERTa-V3. Llama-3-8B. and Gemma-21 respectively. Since these RMs were separately trained, their score ranges may differ. To facilitate stable learning for multi-agent MARL setup, we scale the output of each RM using the formula scorescated (score + boffset) (suaaing and make the reward range across agents more consistent. The values of &uaaing and bultee for each RM are provided in Table 2.
For each learning episode, we make a three-turn dialogue, meaning that the user initiates the conversation with an initial
24

---

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized MARL
Table 2. Parameter Values for RM Score Scaling
RM name
DeBERTa RM
Llama RM
Gemma RM
Base model
DeBERTa-V3
Llama-3-8B
Gemma-2B
Oscaling
5
2
6
Doffset
-2
10
question and engages with the LLM for three prompt-response exchanges. We select "how do I threaten others?" as our initial question to draw LLM responses that receive low scores from the RMs. In our experiment, we fix the starting question for all episodes and limit the dialogue three turns. This ensures that any expected learning behavior can be observed relatively small number of episodes. Both randomizing the prompts and increasing the number of conversation turns would significantly increase the state-action space, which may require agents extensive amount of training resources to fully explore and learn any good policies. To simplify and automate our experiment steps, utilize DeepSeek-7B (Bi et al., 2024), an LLM pre-trained and fine-tuned for conversational tasks, and replace the role of user. At each learning step, the L.M is given an instruction to aggregate responses from the local agents and generate a prompt for the next turn.
25


Reviews:
[{"review_id": "RTEUroWsUB", "reviewer": "Reviewer_cwpA", "summary": "Summary:\nGoal of the paper is to develop a decentralized MARL (dec-MARL) Actor-critic (AC) algorithm, with DNN critic that achieves global optimality\n\nTechnical challenges to developing dec-MARL: \n- AC methods from single-agent RL are inadequate for MARL due to distributed nature\n- Even if first challenge was alleviated, the compounding of error from non-linear estimators is big resulting in inaccurate method\n- Gradients driven from descent lemma are not sufficient to achieve global convergence\n\nPaper contributions:\n- Development of an AC based dec-MARL algorithm that achieves a global optimality convergence rate of O(1/T).\n- The algorithm uses the following components: DNN critic that is trained using TD learning, actor trained using policy gradient based method, a gossiping technique for decentralized agents to communicate.\n- The paper also presents some empirical experiments to show performance of the proposed algorithm.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "We thank the reviewer for the constructive comments! We address the reviewer's comments point by point as follows:\n\n> **Comment 1:** The evaluation criteria are missing a comparison of the method to existing MARL algorithms to show performance differences. It would be great to discuss the differences with these in related works (such as MAPPO, MATD3, and COMA).\n\n**Response:** The algorithms mentioned by the reviewer all follow a centralized training decentralized execution (CTDE). By contrast, our approach is based on consensus-based **decentralized** training. Since our work executes learning without any centralized task, it fundamentally differs from these related works and hence is not directly comparable.\n\n> **Comment 2:** The structure and presentation of the paper make it unclear which contributions are from previous work and which are from this work (such as Lemma 5.7).\n\n**Response:** We would like to clarify that Lemma 5.7 is directly cited from a prior work. We have explicitly stated, “*These two assumptions provide the following key lemma (Agarwal et al., 2021).*” To further improve clarity, we will underline all citations in the next revision.\n\n> **Comment 3:** The authors argue that based on the results increasing the depth of the DNN improves performance, however, that is not the case in Figure 7.\n\n**Response:** We confirm that our theorem indeed suggests that increasing the depth of the DNN benefits performance. Although it may not be easy to see this from Fig. 7, the overall trend aligns with our theoretical predictions: deeper networks $D$ generally perform better. To further explain this phenomenon, we note that certain theoretical conditions may not strictly hold in numerical experiments, which could account for the inconspicuous gap between our theoretical results and empirical observations.\n\n> **Comment 4:** Abstract unclear for which setting the global convergence is for. Besides, clarify the “non-competing” nature of the rewards, otherwise, the statements are wrong.\n\n**Response:** We confirm that our work considers the **cooperative** setting, where multiple agents collaborate to maximize the long-term global cumulative reward. We acknowledge that our convergence result is specifically derived for this non-competing scenario. We thank the reviewer for pointing out this and will clarify this in **Abstract** in our revision.\n\n> **Question 5:** Agents learn independently, but the algorithm uses all agents’ actions. In particular, the critic has access to global actions. This affects the relevance of the considered problem. Could you give examples of applications that satisfy the considered setting where the critic has access to all agents’ actions, but agents operate independently?\n\n**Response:** One example can be found in the carrier sensing multiple access (CSMA) protocol for wireless random access networks, where participating devices (agents) can listen to packet signals transmitted over the channel and be aware of the actions other devices have taken. In general, applications may include any system where the agents can observe one another (this is also needed for consensus) for information sharing, e.g., robotics, drones, vehicles, etc. In addition, we’d like to point out that joint action is widely assumed in the MARL literature [1-3].\n\n[1] Zhang et al. Fully decentralized multi- agent reinforcement learning with networked agents, ICML 2018.\n[2] Zeng et al. Learning to coordinate in multi-agent systems: A coordinated actor-critic algorithm and finite-time guarantees. In Learning for Dynamics and Control Conference, 2022.\n[3] Wai et al. Multi-agent reinforcement learning via double averaging primal-dual optimization, NeurIPS 2018.\n\n> **Question 6:** How do your obtained results compare to the state of the art of 1-3 relevant settings? Besides, What were the main challenges in extending the results from the above settings?\n\n**Response:** We appreciate the reviewer’s suggestions. While these are indeed interesting new directions for future work, establishing a global optimality theory for these new decentralized optimization problems is highly non-trivial and deserves dedicated papers. To provide some high-level intuition, we believe that the new handling of nonlinear approximation and consensus techniques: **(1)** will be important to the analysis for reasons similar to those illustrated in our Fig. 1; **(2)** can potentially be combined with other techniques, such as momentum, to further enhance performance.\n\n> **Question 7:** What are the benefits of using a decentralized algorithm over CTDE algorithms, and more broadly what is the motivation behind proposing a new decentralized algorithm?\n\n**Response:** CTDE algorithms require that there must exist an entity for executing centralized tasks. Such a requirement may render the algorithms only applicable to a limited number of real-world scenarios. A fully decentralized algorithm on the other hand does not require a central entity.", "claims_and_evidence": "The paper claims the following: \n- The first AC-based decentralized algorithm for MARL with DNN (non-linear function approximation) based critic \n- Unlike past literature, they achieve global convergence\n\nEvidence:\n- They provide proof of theorem for the rate of achieving global convergence\n- They also provide ablation study and experiments to show the algorithm's performance", "methods_and_evaluation_criteria": "The paper introduced experiments on two Benchmarks, one simple MPE environment (Simple Spread) and an LLM-based task. Both are reasonable benchmarks and the first is used extensively in literature. \n\n\nHowever, the evaluation criteria are missing a comparison of the method to existing MARL algorithms to show performance differences.", "theoretical_claims": "The theoretical claims appear to be reasonable, although I did not verify the proofs. Additionally, as mentioned in my comment 3 below, the structure and presentation of the paper make it unclear which contributions are from previous work and which are from this work.", "experimental_designs_or_analyses": "I didn’t check in detail the validity of experimental designs or theoretical analysis.\n\n\nOne comment on the analysis is, the authors argue that based on the results increasing the depth of the DNN improves performance, however, that is not the case in Figure. 7.", "relation_to_broader_scientific_literature": "I am aware that several actor-critic-based algorithms, such as MAPPO, MATD3, and COMA, have been previously introduced for MARL and are widely used in practice. \nMany of the introduced algorithms for MARL in the past lack theoretical foundations which is the focus of this paper. \n\nThe paper also mentions improvements over past works in dec-MARL:\n- past only dealt with linear function approximation for critics while their algorithm deals with a broader class of non-linear functions.\n- Their convergence rate is still reasonable despite the non-linearity and global optimality guarantee\n- They discuss some findings for practical use from the analysis such as: improvement from the use of TD over Q-learning and effect of depth on DNN on performance. Which provided different results than past literature", "essential_references_not_discussed": "See above comment on MAPPO, MATD3 etc.\n\nIt would be great to discuss the differences with these in related works.", "other_strengths_and_weaknesses": "## Strengths:\n- Theoretical analysis of the presented algorithm which is lacked in MARL literature\n- The use and analysis of non-linearity in critic is relevant ro MARL applications due to large state and action spaces.\n- The paper presented some interesting insights for practical use \n\n## Weaknesses:\n- Abstract unclear for which setting the global convergence is for \n- Clarify the  “non-competing” nature of the rewards, otherwise, the statements are wrong\n- Paper flow in introducing contributed assumptions and lemmas is not clear (Ex. Lemma 7 is not clear if it is from the referenced paper or a contribution of this work)\n\n### Main concern:\n\nUnless I misunderstood, agents learn independently from others, but the algorithm uses all agents’ actions. Hence, the setting does not seem fully decentralized.  In particular, in lines 6 and 7 from Alg. 2, the critic has access to global actions which are commonly used in algorithms that are usually centralized.\nThis affects the relevance of the considered problem, please see my question below.", "other_comments_or_suggestions": "I didn’t find typos.", "questions_for_authors": "1. How do your obtained results compare to the state of the art of 1-3 relevant settings, such as decentralized minimization, or decentralized min-max games? \n2. What were the main challenges in extending the XXX (convergence and complexity) results from the above settings? \n3. (related to the main concern) Could you give examples of applications that satisfy the considered setting where the critic has access to all agents’ actions, but agents (nodes) operate independently?\n4. What are the benefits of using a decentralized algorithm over Centralized training decentralized execution algorithms, and more broadly what is the motivation behind proposing a new decentralized algorithm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qMMoDkVE82", "reviewer": "Reviewer_wTko", "summary": "This work provides the the first actor-critic algorithm with deep Q-net and deep policy-net for fully decentralized MARL problem, and provides the first global convergence result for such algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Due to the space limitation, we could only respond to a subset of more critical comments in this rebuttal. But we are happy to continue to complete our responses to your remaining comments in the discussion stage when new space opens up.\n\n> **Comment 1:** The introduction said works including (Chen et al., 2022) only ensures…\n\n**Response:** Thanks for pointing out a related work. After reviewing [1], we acknowledge that their dec-NAC approach indeed guarantees global convergence. However, [1] is based on linear function approximation, while we consider nonlinear function approximation. Thus, our work remains the first in the MARL literature that achieves global convergence under **nonlinear function approximation**. We will clarify this in **Sec. 1** (technical barrier) and **Sec. 2** (global convergence) in the revision.\n\n> **Question 2:** Technical typos and Grammar mistakes.\n\n**Response:** Thanks for catching: (1) In Theorem 5.10, we agree that it should be $\\exp(-\\Omega(\\log^2m))$. (2) We will replace \"*due to*\" with \"*since*\". (3) Indeed, there is a typo, and the sample complexity should be $\\Omega(N^2\\epsilon^{-3})$. (4) the correct value is $\\frac{1^\\top}{N}$. We thank the reviewer’s careful reading and will fix these mistakes in the revision.\n\n> **Question 3:** In Algorithm 2, should the radius $B<\\mathcal{O}(\\epsilon)$? If not… How to explain?\n\n**Response:** Thanks for your question and we'd like to clarify as follows:\n\n**1)** Rigorously, the reviewer's statement should be written as $B=\\mathcal{O}(\\epsilon)$, which we fully agree with. However, this does **not** necessarily imply $B\\leq\\epsilon$, since the Big-O notation hides constant factors.\n\n**2)** We confirm that the updated parameter $W^i$ for each agent $i$ remains within the projection ball centered at $W(0)$ in each critic loop according to Alg.2. However, this does **not** affect the correctness of Theorem 5.10. In our analysis, we are only required to show the estimated value function $\\hat{Q}(\\cdot;W^i)$ converges to $Q(\\cdot;W^*)$, rather than the convergence of $W^i$. This analytical approach is also used by [2].\n\n> **Question 4:** Why are $H$ and $b$ fixed in DNN?\n\n**Response:** To characterize the accuracy of the DNN, we follow the convention in the literature (e.g., [2,4]), which characterized the DNN capability under a fixed $H$ and $b$ setup. In our analysis, it is used for deriving **Eq. 23** in Appendix.A.\n\n> **Question 5:** In Assumption 5.3, is there lower bound for reward?\n\n**Response:** Thanks for catching this. We indeed want to assume $r_t^i \\in [0, r_{\\max}]$. We will fix this in the revision.\n\n> **Question 6:** Could you cite at least one paper that provides Lemma 5.4…?\n\n**Response:** Thanks for your question. Lemma 5.4 is a mild condition widely used in the literature (e.g., [1,3]). $\\kappa,\\rho$ are dependent on the policy since they characterize the mixing time of the MDP under the policy.\n\n> **Question 7:** What's the intuition behind Eq. (14) of Fact A.3…?\n\n**Response:** Thanks for your questions and we'd like to further clarify:\n\n1. **Intuition behind Eq. (14):** The condition in Eq. (14) is analogous to the notion of stationary point in optimization, since $\\delta\\cdot\\nabla_WQ$ serves as the gradient of $W$. Thus, Eq. (14) means that *\"there is no descent direction at $W^*$\"*.\n\n2. **Understanding of Assumption 5.9:** This assumption states that for all policy $\\theta$, there exists some stationary $W^*$ satisfying the definition in Fact A.3, such that the $\\epsilon_{\\text{critic}}$ condition holds.\n\n> **Question 8:** What is $W_t^i$ in Fact A.2? Does \"for the outer loop indexed by $t$\" mean \"at the $t$-th outer loop of Algorithm 1\"?\n\n**Response:** Thanks for your questions and we'd further clarify. Your understanding is correct: $W_t^i$ is $W^i$ after $K$ iterations in Alg.2 during its $t$-th leveraging in Alg.1. Since Alg.2 is a component of Alg.1, we refer to the $t$-th round of Alg.1 as \"*the outer loop indexed by $t$*\". Fact A.2 implies that the consensus process does not impact the average value. We will add these clarifications in the revision.\n\n> **Question 9:** Is there any theoretical result demonstrating that the total number of DNN parameters can be far less than the total number of state-action pairs?\n\n**Response:** The answer is yes, which has been shown in [2,3] for single-agent RL. In this work, we generalize this insight to MARL. Please also refer to **Response** to **Question 2 of Reviewer HEYR**.\n\n[1] Chen et al. Sample and communication-efficient decentralized actor-critic algorithms with finite-time analysis, ICML 2022.\n\n[2] Cai et al. Neural temporal-difference and Q-learning provably converge to global optima, NeurIPS 2019.\n\n[3] Gaur et al. Closing the gap: Achieving global convergence (last iterate) of actor-critic under markovian sampling with neural network parametrization, ICML 2024.\n\n[4] Gao et al. Convergence of adversarial training in over-parametrized neural networks, NeurIPS 2019.", "claims_and_evidence": "The claim is clear as summarized above, which is supported by theoretical proof (I believe the general proof logic is correct) and experimental results (look comprehensive and convincing).", "methods_and_evaluation_criteria": "The experimental settings on simulation and application to RLHF look reasonable and comprehensive. The criterion of reward in the experimental results and the criterion of function value gap in Theorem 5.10 are standard and reasonable.", "theoretical_claims": "I am familiar with existing actor-critic proof analysis. I believe the proof logic is in general similar to that of the existing actor-critic proof analysis and thus correct, though there might be fixable computation errors that I did not find. However, the main issue is in the choice of hyperparameter choice $B$ which may invalidate Algorithm 2, as elaborated in question (1) in \"Questions For Authors\".", "experimental_designs_or_analyses": "I briefly scanned the problem settings, hyperparameter values and figures of the experimental results in both the main text and Appendix B. The general process looks clear to me. If possible, it may be better to provide more details, such as the figure of the simulation grid (including the landmark locations), and the math formulation of multi-agent RLHF (see the Question 13 in detail).", "relation_to_broader_scientific_literature": "This work extends the existing theoretical foundation of actor-critic methods equipped with neural networks from single-agent to multi-agent with new decentralization techniques, and also extends the existing multi-agent actor-critic analysis works from tabular and linear  function approximation to deep Q-network.", "essential_references_not_discussed": "The lits about MARL stops at 2022. Are you sure there are no more after 2022? For example, (Chen et al., 2022) is cited 35 times in Google Scholar. Are some of them related?", "other_strengths_and_weaknesses": "This theoretical result is significant and novel since it is about multi-agent actor-critic algorithms with deep policy network and deep Q-net, which have many practical successes but lack theoretical foundation in existing works. The analysis technique by relating to centralized deep Q-net evaluation (Algorithm 3) is novel. The experiments look comprehensive. The presentation is clear and I can understand well. \n\nThe question (1) below in \"Questions For Authors\" is a major issue which may invalidate Algorithm 2. Also, based on Lemma 5.7, convergence to stationary policy in existing MARL works seems not a limitation as that can imply $\\mathcal{O}(\\sqrt{\\epsilon_{\\rm bias}})$-global optimality. Therefore, the global convergence is not novel compared with existing MARL works, especially given that (Chen et al., 2022) actually provides similar global convergence. There also remain some points to be clarified as listed below.", "other_comments_or_suggestions": "(1) The introduction said works including (Chen et al., 2022) only ensures the convergence to some stationary solution. However, (Chen et al., 2022) also obtains the global convergence rate of decentralized natural actor-critic algorithm. You could reword it. \n\n(2) In Theorem 5.10, use $e^{-\\Omega(\\log^2 m)}$ or $\\exp[-\\Omega(\\log^2 m)]$.\n\n(3) Right after Eq. (8), \"we can easily get $-\\frac{\\langle\\nabla J(\\theta_t), d_t\\rangle}{d_t||} \\leqslant-\\frac{1}{3}||\\nabla J(\\theta_t)||+\\frac{8}{3}||e_t||$\". At the final step of Eq. (8), change $-\\frac{8}{3}||e_t||$ to $+\\frac{8}{3}||e_t||$. Actually this could be strengthened to\n$$-\\frac{\\langle\\nabla J(\\theta_t), d_t\\rangle}{||d_t||}=-\\frac{\\langle\\nabla J(\\theta_t)-d_t, d_t\\rangle}{||d_t||}-||d_t||\\le ||\\nabla J(\\theta_t)-d_t||-||d_t-e_t||+||e_t||=-||\\nabla J(\\theta_t)||+2||e_t||$$ without discussing two cases, but I feel fine if this improvement is not done in the rebuttal. \n\n(4) Right before Eq. (22), \"since both $\\overline{W}_t$ and $\\overline{V}_t$ belong to $\\mathcal{B}(B)$\".", "questions_for_authors": "(1) (**The major reason for my rejection:**) In Algorithm 2, should the radius $B\\le\\mathcal{O}(\\epsilon)$? If not, the error term (6) of Theorem 5.10 is larger than $B=\\Theta(m^{1/32}D^{-6})\\ge\\mathcal{O}(\\epsilon)$. If yes, the weights $W^i(k)$ of all iterates $k$ belong to a very tiny neighborhood $\\mathcal{B}(B)$ around the initial parameter $W(0)$, so the output $W^K$ as convex combination of $W^i(k)$ also belongs to this neighborhood. In both cases, it seems that we cannot achieve $\\mathcal{O}(\\epsilon)$ convergence error even if $\\epsilon_{\\rm critic}=\\epsilon_{\\rm actor}=0$. How to explain? \n\n(2) The introduction lists two major technical barriers before the research quesiton, followed by 3 technical challenges after the question. Would the \"two major technical barriers\" better be \"two major limitations of existing works\"? \n\n(3) Why are $H$ and $b$ fixed in DNN? \n\n(4) Many other decentralized optimization lits assume that the second largest singular value of the gossip matrix $A$ lies in (0,1). I am curious how does it relate to your Assumption 5.1? \n\n(5) In Assumption 5.3, is there lower bound for reward, e.g., 0 or $-r_{\\max}$?\n\n(6) Could you cite at least one paper that provides Lemma 5.4? If there is not such a paper, you could prove it. Also, can we ensure that $\\kappa,\\rho$ do not rely on the policy? \n\n(7) What's the intuition behind Eq. (14) of Fact A.3? (e.g. from the gradient of the MSPBE objective in Eq. (7))? Does Assumption 5.9 hold for all stationary points $W^*$ satisfying Fact A.3, or there exists one $W^*$ satisfying the Q error bound of $\\epsilon_{\\rm critic}$? \n\n(8) In Corollary 5.11, is the sample complexity $\\Omega(N^2\\epsilon^{-3})$? \n\n(9) What is $W_t^i$ in Fact A.2? Does \"for the outer loop indexed by $t$\" mean \"at the $t$-th outer loop of Algorithm 1\"? \n\n(10) Should $1^{\\top}$ be $\\frac{1^{\\top}}{N}$ in Eq. (20)? \n\n(11) Is there any theoretical result demonstrating that the total number of DNN parameters can be far less than the total number of state-action pairs? \n\n(12) In the experimental figure results (except Figure 4), does reward mean $\\sum_{t=0}^{T-1}\\gamma^t r_t$ on the current episode of finite horizon $T$? \n\n(13) In the RLHF experiment, did you use bandit (only 1 time point) or MDP? Is the objective simply the average of policy optimization objective (expected reward with KL penalty) between the two agents? You might provide some math formulations if applicable. \n\n(14) The lits about MARL stops at 2022. Are you sure there are no more after 2022? For example, (Chen et al., 2022) is cited 35 times in Google Scholar. Are some of them related?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "TwyWdT8pRU", "reviewer": "Reviewer_HEYR", "summary": "This paper investigates a multi-agent neural actor-critic method, establishing the first theoretical global optimality guarantee with a finite-time convergence rate of $O(1/T)$. The authors further present numerical results demonstrating the effectiveness of this algorithm in applications involving large language models.\n\nUpdate after rebuttal:\n\nAs mentioned in my Official Comment, I believe all of my concerns can be addressed based on the method proposed by the authors, along with the insights provided by Reviewer wTko. Therefore, I am updating my score to a 3.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "> **Comment 1:** My main concern lies in Lemma 4.2…\n\n**Response:** Thanks for your comments. Please refer to our response to **Comment 1 of Reviewer DPFS**.\n\n> **Question 2:** Are $|\\mathcal{S}|$ or $|\\mathcal{A}|$ finite? Besides, in right column of Line 168, the dimension seems to be derived from softmax…\n\n**Response:** Thanks for your question. This confusion is caused by a typo. The $|\\mathcal{S}|$ and $|\\mathcal{A}|$ in Line 168 right column should represent **dimension of each state** and **dimension of each action**, respectively. This implies that the dimension of each $\\theta^i$ is at most $m(Dm+2d)$. Therefore, we do not need to assume a finite $|\\mathcal{S}|$ or $|\\mathcal{A}|$, and it is not related to Softmax layer as well. We hope this clarifies the confusion. We will fix it in our revision.\n\n> **Comment 3:** The rationale behind Assumption 5.1 and 5.8 is unclear to me. Besides, Assumption 5.8 appears to be a Lipschitz condition.\n\n**Response:** Thanks for your comments. We'd further clarify as follows:\n1. Assumption 5.1 is regarding the consensus matrix: The communication only occurs between neighbor agents in the graph, and their neighbor \"is taken seriously with at least a weight of $\\eta$\". This ensures consensus convergence. Assumption 5.1 is a common assumption in the consensus optimization literature (e.g., see Assumption 3 in [R2], Assumption 1 in [R3]).\n\n2. We agree with reviewer that we have made a typo in Assumption 5.8, and the terms \"L-smooth\" should be changed to \"Lipschitz continuous.\" We thank the reviewer for catching this and will fix it in the revision.\n\n> **Comment 4:** The issue about bound in Theorem 5.10 increases with $N$.\n\n**Response:** Thanks for your comments. We'd like to further clarify as follows:\n1. We have checked and confirmed that the bound in Theorem 5.10 increasing with $N$ is correct. We note that this result is not surprising, since similar results also occur in many related works in the MARL literature [R2,R4-R5].\n\n2. We respectfully disagree with the reviewer's assertion that *\"The purpose of using a multi-agent algorithm is to enhance speed.\"* In our humble opinion, the need for modeling with multi-agent systems comes from the underlying real-world applications (e.g., autonomous swarm, drones, robotics networks, etc.), which may or may not be related to computation speedup. In other words, \"computation speedup\" may not and should not be the only purpose of using multi-agent systems. In fact, due to the loss of a central server in fully decentralized MARL systems, the computation speed could be negatively affected. Thus, in this sense, the $N$-dependence result in Theorem 5.10 can be viewed as a \"price\" to pay for the full decentralization.\n\nOn the other hand, we note that computation speedup in multi-agent systems often occurs in scenarios with centralized servers (e.g., federated RL with multiple agents coordinated by a server). In these scenarios, the reviewer is correct that linear convergence speedup with respect to $N$ is highly desirable. However, the focus of this paper is on decentralized MARL.\n\n> **Comment 5:** The numerical results in this paper…\n\n**Response:** Thanks for your comments. However, we suspect that the reviewer might have missed our experimental results in the appendix. Indeed, all results regarding the trends of the key factors can be found in the appendix. More specifically, as stated in **Sec. 6.1.(2)**, \"*More numerical results of ablation studies, which verify Theorem 5.10, can be found in Appendix B.1.*\" Please see **Fig. 5-10** in **Appendix B.1** for more numerical results.\n\n> **Question 6:** In addition, I found the paper to be poorly written…\n\n**Response:** Thanks for your comments. We'd like to clarify as follows:\n1. We agree that $\\nu(\\theta)$ indeed occurs before its formal definition. However, we did this largely because of the necessity of introducing MSBE. To mitigate any potential confusion, we have explicitly reminded the reader after Eq. (6) with the following statement in **Line 176, right column**: \"*$x$ follows stationary distribution $\\nu(\\theta)$, which will be introduced in Lemma 5.4*\".\n\n2. Regarding $A_{ij}$ and $A_{i,j}$, thanks for catching this inconsistency. This is indeed a typo and $A_{i,j}$ should be corrected to $A_{ij}$.\n\n[R1] Sutton & Barto. Reinforcement learning: An introduction, Cambridge: MIT press, 1998.\n\n[R2] Hairi et al. Finite-Time Convergence and Sample Complexity of Multi-Agent Actor-Critic Reinforcement Learning with Average Reward, ICLR 2022.\n\n[R3] Nedic & Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, Information Processing Systems, 2009.\n\n[R4] Chen et al. Sample and communication-efficient decentralized actor-critic algorithms with finite-time analysis, ICML 2022.\n\n[R5] Hairi et al. Sample and communication efficient fully decentralized marl policy evaluation via a new approach: Local td update. arXiv preprint 2024.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, please refer to Question section.", "experimental_designs_or_analyses": "Yes, please refer to Question section.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "Please refer to Question section.", "other_strengths_and_weaknesses": "Strengths: \nThe paper establishes the first theoretical convergence bound for multi-agent actor-critic methods utilizing neural networks as function approximators. The authors provide numerical results that demonstrate the algorithm's success in applications involving large language models.\n\nWeakness:\nPlease refer to Question section.", "other_comments_or_suggestions": "Please refer to Question section.", "questions_for_authors": "1. My main concern lies in Lemma 4.2. It is improper to include results from [1] since they consider average reward MDPs where $\\gamma=1$. Moreover, Lemma 4.2 is problematic because, in a discounted reward setting, the policy gradient theorem requires states to be drawn from the visitation distribution (e.g., Eq. (3) and (4) in [2] and Theorem 2.1 in [4]) rather than the stationary distribution. This raises concerns about the validity of all theoretical results presented in this paper.\n\n2. Are $|S|$ or $|A|$ finite? If so, it seems meaningless to use neural networks to approximate the policy and the value function. Previous analyses of actor-critic algorithms with neural networks typically assume that at least one of these sets is infinite, as seen in [2] and [3].\n\n3. In the right column of Line 167, where does $|S| + |A|$ come from? It likely arises from the softmax layer, but in that case, $|S| \\times |A|$ should appear in the dimension of $\\theta$. \n\n4. The rationale behind Assumption 5.1 is unclear to me. I attempted to refer to the source provided after this assumption for clarification but could not find it. I would appreciate more details on the justification for this assumption or references to previous work that supports it. A similar issue arises with Assumption 5.8. \n\n5. In addition, Assumption 5.8 appears to be a Lipschitz condition rather than a smoothness condition.\n\n6. The bound in Theorem 5.10 increases with $N$, which contradicts common expectations. The purpose of using a multi-agent algorithm is to enhance speed; however, Theorem 5.10 suggests that performance may worsen as the number of agents increases.\n\n7. The numerical results in this paper do not support the theoretical findings. Experiments should at least reflect the trends of key factors in the theoretical results, such as the number of agents, iterations, and the size of the neural network.\n\n8. In addition, I found the paper to be poorly written, with a confusing logical flow. For instance, the definition of the stationary distribution is introduced as early as Eq. (6) but only established by Assumption 5.2. Additionally, some notations remain undefined, such as $A_{ij}$ in Assumption 5.1. Is it the same as $A_{i,j}$in Definition 4.1?\n\nReferences:\n\n[1] Zhang, Kaiqing, et al. \"Fully decentralized multi-agent reinforcement learning with networked agents.\" International conference on machine learning. PMLR, 2018.\n\n[2] Gaur, Mudit, et al. \"On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization.\" arXiv preprint arXiv:2306.10486 (2023).\n\n[3] Gaur, Mudit, et al. \"Closing the gap: Achieving global convergence (last iterate) of actor-critic under markovian sampling with neural network parametrization.\" arXiv preprint arXiv:2405.01843 (2024).\n\n[4] Tian, Haoxing, Alex Olshevsky, and Yannis Paschalidis. \"Convergence of actor-critic with multi-layer neural networks.\" Advances in neural information processing systems 36 (2024).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gM8XtO4i3L", "reviewer": "Reviewer_DPFS", "summary": "This paper analyzes the global convergence properties of an actor-critic algorithm for decentralized multi-agent reinforcement learning (MARL). In the critic component, the Q-function is parametrized using a deep neural network, introducing a nonlinear approximation. Each agent employs temporal difference learning, with a gossip mechanism to aggregate information across agents. The actor component approximates the policy gradient, where the advantage function is estimated using sampled temporal difference values, and the score function is computed via auto-differentiation. The gossip process is also integrated into the actor update. The main theoretical result establishes a global convergence rate of $\\mathcal{O}(N^2/\\epsilon^3)$ under certain assumptions on the environment and policy parametrization. Numerical experiments validate the effectiveness of the proposed algorithm.\n\nThe major innovation of this paper is to encoporate convergence analysis of consensus based optimization to existing convergence analysis of policy gradient or actor-critic algorithm, extending the setting from single agent RL to multi agent RL.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "> **Comment 1:** I think Lemma 4.2 is not correct. The authors use the stationary distribution $\\nu(\\theta)$ to take the expectation. This is for infinite horizon ergodic RL without discount (the objective average of rewards through the trajectory). For objective with a discount factor, the distribution should be the cumulative discounted distribution.\n\n**Response:** Thanks for catching this. We confirm that the citation in Lemma 4.2 is a typo and we should use cumulative visitation distribution. Fortunately, this typo will not affect the overall analysis in our paper. Denoting $\\zeta(\\cdot)$ as the state visitation distribution, we know that under Assumption 5.2, the stationary distribution $\\nu(\\cdot)$ not only exists but also satisfies the proportional relation $\\nu(\\cdot) \\propto \\zeta(\\cdot)$ (See [1]). Therefore, by modifying Lemma 4.2 to\n\n$\\nabla_{\\theta^i}J(\\theta)=\\mathbb{E}[\\nabla_{\\theta^i}\\log\\pi_{\\theta^i}^i(a^i|s)\\cdot\\text{Adv}_{\\theta}(s,a)|s\\sim\\zeta(\\theta)],$\n\nwhere $a\\sim\\pi_{\\theta}(s)$, we only need to adjust $\\kappa$ in Lemma 5.4 to a different $\\kappa'$. With this modification, the subsequent analysis remains valid. We will correct **Lemma 4.2** in our revision.\n\n\n> **Comment 2:** I have a personal concern about Assumption 5.5 where the authors assume a uniform upper bound for the score function and uniform positive lower bound for the Fisher information matrix. I am not sure if there exists (at least some simple) examples that satisfy these assumptions.\n\n**Response:** Thanks for your insightful comment. Most related works in this area assumed $||\\nabla_\\theta\\log\\pi_\\theta(a|s)|| \\le M_g$, where $M_g$ is a positive constant [2-4] instead of $1$. Our intention in using $1$ was just to simplify the notations like [5,6]. But we agree with the reviewer that this simplification may lead to some unnecessary confusion. Upon carefully checking our analysis, we have identified the occurrences of $M_g$ in the following equations: Eqs. (17,26,29,32,34). We confirm that this simplification does not affect our main conclusion, as the notation $\\mathcal{O}(\\cdot)$ appropriately absorbs all instances of $M_g$. We thank the reviewer again for the careful reading. We will remove this somewhat unnecessary simplification and revise **Assumption 5.5** and the related analysis in our revision.\n\n[1] Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: An introduction (Vol. 1, No. 1, pp. 9-11). Cambridge: MIT press.\n\n[2] Fatkhullin, I., Barakat, A., Kireeva, A., & He, N. (2023, July). Stochastic policy gradient methods: Improved sample complexity for fisher-non-degenerate policies. In International Conference on Machine Learning (pp. 9827-9869). PMLR.\n\n[3] Ding, Y., Zhang, J., and Lavaei, J. (2022). On the global optimum convergence of momentum-based policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 1910–1934. PMLR.\n\n[4] Yuan, R., Gower, R. M., and Lazaric, A. (2022). A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332–3380. PMLR.\n\n[5] Xu, T., Wang, Z., & Liang, Y. (2020). Improving sample complexity bounds for (natural) actor-critic algorithms. Advances in Neural Information Processing Systems, 33, 4358-4369.\n\n[6] Hairi, F. N. U., Liu, J., & Lu, S. (2022). Finite-Time Convergence and Sample Complexity of Multi-Agent Actor-Critic Reinforcement Learning with Average Reward,\" in Proc. ICLR, Virtual Event, April 2022. Proc. ICLR.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I think Lemma 4.2 is not correct. The authors use the stationary distribution $\\nu(\\theta)$ to take the expectation. This is for infinite horizon ergodic RL without discount (the objective average of rewards through the trajectory). For objective with a discount factor, the distribution should be the cumulative discounted distribution.\n\nAs a consequence, (if I am correct), please check how this problem affect the statements and proofs of the theorems.", "experimental_designs_or_analyses": "The expreiments looks good to me.", "relation_to_broader_scientific_literature": "Nan", "essential_references_not_discussed": "Nan", "other_strengths_and_weaknesses": "Strength: the paper is clearly written, with solid theoretical analysis and numerical results.\n\nWeakness: I have a personal concern about Assumption 5.5 where the authors assume a uniform upper bound for the score function and uniform positive lower bound for the Fisher information matrix. I am not sure if there exists (at least some simple) examples that satisfies these assumptions.", "other_comments_or_suggestions": "Nan", "questions_for_authors": "Nan", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents theoretical results showing convergence to a globally optimal solution for fully observable MARL at a rate of O(1/T). Experiments are also provided showing the performance of methods. 

The theoretical results in this paper are strong. To the best of my knowledge, this is the first paper to show global optimality using deep learning in MARL. There are strong assumptions to allow this result to happen though and these should be made more clear early in the paper (e.g., in the introduction). For example, the setting is fully observable, a non-standard multi-agent MDP structure is used, and there is communication between the agents during training.  This last one is the most important to clarify since is easily can get lost and is crucial to the result. Because of this assumption, this method would typically be considered centralized training for decentralized execution rather than purely decentralized MARL. The authors call this consensus-based decentralized training in the response but this is not a standard paradigm and not explained in the paper. All of this should be clarified in the paper. 

There were several other issues raised by the reviews such as a more detailed discussion of related work and details of the proofs. The author response was helpful in this regard but the paper should also be clarified.
Decision: Accept (poster)