Finite-Time Convergence and Sample Complexity of Multi-Agent Actor-Critic Reinforcement Learning with Average Reward
Authors: FNU Hairi
Jia Liu
Songtao Lu
Venue: ICLR 2022 Spotlight (2022)

Abstract: In this paper, we establish the first finite-time convergence result of the actor-critic algorithm for fully decentralized multi-agent reinforcement learning (MARL) problems with average reward. 
In this problem, a set of $N$ agents work cooperatively to maximize the global average reward through interacting with their neighbors over a communication network.
We consider a practical MARL setting, where the rewards and actions of each agent are only known to itself, and the knowledge of joint actions of the agents is not assumed. 
Toward this end, we propose a mini-batch Markovian sampled fully decentralized actor-critic algorithm and analyze its finite-time convergence and sample complexity.
We show that the sample complexity of this algorithm is $\mathcal{O}(N^{2}/\epsilon^{2}\log(N/\epsilon))$.
Interestingly, this sample complexity bound matches that of the state-of-the-art single-agent actor-critic algorithms for reinforcement learning. 

Published as a conference paper at ICLR 2022
FINITE-TIME CONVERGENCE AND SAMPLE COM- PLEXITY OF MULTI-AGENT ACTOR-CRITIC REIN- FORCEMENT LEARNING WITH AVERAGE REWARD
Hairi and Jia Liu
Songtao Lu
Department of Electrical and Computer Engineering The Ohio State University Columbus, OH 43210, USA hairi. 10su. edu, 1 liußece. www.eosuuee.. osu.
IBM Research AI
IBM Thomas J. Watson Research Center Yorktown Heights, NY 10598 songtaoo 1bm. com
ABSTRACT
In this paper, we establish the first finite-time convergence result of the actor-critic algorithm for fully decentralized multi-agent reinforcement learning (MARL) problems with average reward. In this problem, a set of N agents work coop- eratively to maximize the global average reward through interacting with their neighbors over a communication network. We consider a practical MARL set- ting, where the rewards and actions of each agent only known itself, and the knowledge of joint actions of the agents is not assumed. Toward this end, we pro- pose mini-batch Markovian sampled fully decentralized actor-critic algorithm and analyze its finite-time convergence and sample complexity. We show that the sample complexity of this algorithm is O(N / (o)). Interestingly, this sample complexity bound matches that of the state-of-the sfute-of-thh-arr single-agent actor- critic algorithms for reinforcement learning.
INTRODUCTION
1) Background and Motivations: In recent years, multi-agent reinforcement learning (MARL) has found a wide range of applications in networked large-scale systems, such as power grid sys- tems (Riedmiller.ec et all 2000), autonomous driving (Yu et all 2019 Shalev-Shward et all 2016) and strategic games (Silver et al. 2018: Foerster et al., (018).. to name just a few. Although em- pirical successes of MARL applications have been widely observed, the fundamental theoretical understanding of how to develop fast-converging and low sample-complexity MARL algorithms, two of the most important performance metrics for MARL, remains in its infancy so far (see, e.g., (Zhag et all k for an excellent survey). In particular, two important aspects of cooperative MARL algorithm designs deserve special attention:
First, in the multi-agent collaborative setting, the information structure (i.e., the assumptions of who have the knowledge of what) far more complex than its single-agent counterpart and care must be taken in MARL problem formulations. In the cooperative MARL literature so far, many existing works assume full knowledge of joint states and joint actions. which often do not hold true in practice. For example, in autonomous driving (Yu et al. 2019), each vehicle can only observe/detect the actions of the surrounding vehicles that are within its communication range. As another example, in power grid networks (Riedmiller et all 2000). each power distributor generally does not know the resistor values set by other distributors.
Second, most MARL theoretical studies in the MARL literature are focused the discounted total reward setting, where a hyperparameter y E (0. is introduced as the discount factor in the objective function. Although the discounted total reward setting captures the important aspect of diminishing return in the future, it may not be appropriate for many other applications where the long-term average reward is of interest. For example, in the optimization of distributed communi- cation networks with MARL, the typical and natural performance metrics are long-term average throughput or latency in the steady-state.
The lack of fundamental understanding on how to develop efficient cooperative MARL algorithms that consider the above two aspects in terms of information structure, scalability, and communication

---

Published as a conference paper at ICLR 2022
and sample complexities motivates to fill this gap by developing fully decentralized cooperative MARL algorithm in the average reward setting, without assuming joint action knowledge.
2) Technical Challenges: Developing fully decentralized cooperative MARL algorithm for the average reward setting without full joint action knowledge is highly non-trivial and several major technical challenges naturally arise. First, it is well-known that, even in the single-agent reinforce- ment learning (RL) setting, the average reward setting is more challenging to analyze compared to the discounted reward setting, which necessitates different proof techniques (Tsitsiklis & Van Roy! 1999). In MARL, the decentralized nature and the lack of joint action-state information further complicate the algorithm design and analysis in the average reward setting. Second, due to the lack of joint action knowledge, the communication costs among agents in MARL will be significantly increased to achieve satisfying performance, which implies that low sample and communication complexities are even more challenging and critical for MARI without joint action information.
3) Main Results and Contributions: The main contribution of this paper is that we overcome the aforementioned challenges and develop a consensus-based Markovian sampled decentralized actor- critic algorithm for MARL. Our key results in this paper are summarized as follows:
We propose batch-sampled actor-critic algorithm that uses consensus updates in TD-sharing among agents. This batch sampling approach enables more efficient communication compared to the classical fully decentralized MARL. Specifically, in order to converge to an e neighbor- hood of the stationary, we require O( log(e-)) ²)) rounds of communication while only needing O(E (c-2logtt log(( +)) samples. By contrast, the state-of-the-art MARL requires communication round per sampling. Also, our algorithm allows the use of constant step-sizes in both the actor and the critic steps.
We provide the first-ever sample complexity analysis the MARL average reward problem set- ting without joint action information. Our obtained complexity is O(e log(e })) where is the closeness to the neighborhood of stationary point (treating network size N as a fixed constant). It is worth noting that the order-wise sample complexity of our algorithm matches that of the state-of-the-art single-agent RL algorithms.
2 RELATED WORK
In this section, we provide quick overview on the closely related work on MARL algorithms and their theoretical results, along with several notable related counterparts single-agent RL.
For recent advances in MARL algorithms and their theoretical results, Zhang et al. (2021a) provided a comprehensive survey. Also, Lee al. (200)) highlighted the evolution from single-agent to multi-agent RL from distributed optimization perspective. In the broader area of MARL, a line of research has been focused on the MARL policy evaluation problem. These works analyzed the convergence Doan et all (2019) and proposed vari- ous variance reduction of policy evaluation in decentralized MARL algorithms Zhang et all (b02
1) MARL Theoretical Analysis and Algorithm Design:
Doan et all (019) used i.idd sampling and has shown the sample complexity of Ö(e for their TD(0) learning algorithm to reach a mean-square error convergence. However, these algorithms do not involve policy improvement and solely focus on the performance evaluation of given policies. In the areas of joint policy evaluation and improvement, [oersterr et al. (2018) considered multi-agent actor-critic algorithm that has a centralized critic and decentralized actors, which is different from our fully decentralized actor-critic algorithm. In contrast, Zhang all (2018) established asymp- totic convergence results for fully decentralized MARL actor-critic algorithms. Concurrent with our work. Chen et al. (202 has recently studied the mini-batch Markovian sampling actor-critic algorithm for a class of discounted reward MARL problems, where the finite-time convergence re- sult is obtained. They have applied batch sampling for both actor and critic steps and achieved a which is the same as ours. We note that, together with our
sample complexity of D(c-2loo(cc)) work, these are the first finite-time convergence results for MARL. However, there are several key differences between our work and (Chen et all 202 First, we focus on the average reward prob- lem, while Chen et all (2021) studied the discounted reward setting. Second, in (Chen et all 20221), agents share noisy version of the rewards with the neighbors, which requires re- re-sampling process from every sampled reward instance. In contrast, we allow agents to share local TD-errors with their neighbors and no re-sampling is required.
2

---

Published as a conference paper at ICLR 2022
Table 1:
Comparison of sample complexity of single-agent (SA) and multi-agent (MA) AC algo-
rithms and TD(O) algorithms at Average Reward (AR) and Discounted Reward (DR) settings.
Sampling
Paper
Problem
Sample Complexity
actor step
critic step
Qiu et al. (2021)
SAAR
i.i.d.
Markovian
O log
Xu ct al, (2020)
SADR
Markovian
Markovian
O
Zhang al. (2018)
MAAR
Markovian
Markovian
Asymptotic
Doan et al. (2019)
MADR
N/A
i.i.d
O(c=))
Chen al, (2021)
MADR
Markovian
Markovian
O log(E )) ON2 logg N/c))
This paper
MAAR
Markovian
Markovian
We note that single-agent RL can be viewed as a centralized approach, where central controller collects joint actions, rewards and even designs policies for agents. For the single-agent average reward setting, Tsitsiklis & Van Roy (1999) first analyzed the asymptotic convergence of (D(A) algorithm with function approximations in the policy evaluation problem. A & Van Roy (2002) provided insights in terms of differences and connections between average reward and discounted reward of TD-based learning algorithms with function approximations. Recently, Oiu et al. (2021) analyzed the sample complexity for an actor- critic algorithm for the average reward problem. In their actor-critic algorithm, they used batch sampling for the critic learning and i.i.d. sampling for the actor step, with sample complexity being Occ log?(c (c) By applying mini-batch sampling update, we are able to improve the sample complexity by factor of O(e-1) Another closely related work sinle-agenti RL is (Xu et all 2020), where the authors studied the discounted reward problem. They used batch sampling for both actor and critie steps in their actor-critic algorithm and developed new technique to handle bias error in the critic step, which we also adopted for the average approximation parameter analysis in our critic step. This achieved the state-of-the-ar sample complexity of O(E log(E 1)) for single- agent RL. In addition, the global convergence of actor-critic algorithm to the optimal policy has been studied in the case of discounted setting with single time scale in (Fu et all, (020)) and linear quadratic regulator in (Yang et all (019). However, we note that these settings are fundamentally different from the average reward setting and it will be an interesting future direction to consider global convergence possibility in the average reward setting.
2) Related Literature in Single-Agent RL:
To conclude this section, we summarize the aforementioned related actor-critic and TD algorithms and their sample complexity results in Table
3 MULTI-AGENT REINFORCEMENT LEARNING WITH AVERAGE REWARD
3.1 SYSTEM MODEL
Consider a multi-agent system with N agents, denoted by = [1....,N. (1.... worked environment. Let & be the edge set for given network G (W.E). To formulate MARL problem and facilitate our subsequent discussions, we first define the notion of networked multi-agent MDP as follows.
operating in a net-
Definition 1 (Networked Multi-Agent MDP). Let g = (N,E) be a communication net- work that connects N agents. A networked multi-agent MDP defined by following tuple (S, [eTee, P. Leth,, 9), where S is the global state space observed by all agents, A' is the action set for agent i, and P S A > [0, 1 is a global state transition function, and R' S A is the local reward function for agent Let A IlLN A' be the joint action set of all agents.
In this paper, we assume that the global state space S and action space for agent A' are finite. As a result, the joint action space A is also finite for finite N. We also note that at time t 2 0, all agents can observe the current global state $t. However, agent i can only observe its own action a E A', which is the key difference between our model and that in (Zhang et all 2018), where it is assumed that the joint actions are observable to all agents. Moreover, each agent can only observe its own reward rf, i.e., agents do not observe share rewards with other agents at time f. The
3

---

Published as a conference paper at ICLR 2022
reward function (s,s a) is expectation given and a, and the instantaneous reward is denoted by (", i.c., R
(s, = as)))
We consider policies that are stationary. In our MARL system, each agent chooses its action follow- ing its local policy x² that is conditioned on the current global state s, i.e., x <'(a') [s) is the probability for agent to choose action at E A'. Then, the joint policy æ : S x A + [0, can be written as T (a]s) = llE N' (a'[s).
Moreover, the policies the agents parameterized. Specifically, each agent i's local policy can be written The. where 0' Ih denotes the parameter. We let 0 - [00'T,... (0N (T)" RE m. Then, we can write the joint policy as follows: Ta(als) = IILEN To (a'ls).
3.2 TECHNICAL ASSUMPTIONS
We now state the following assumptions on the positivity and continuity of T/e (a']s), which guar- antee the stationary distribution of } under any given policy.
Assumption 1. For any E N,, s S, a' A' and 0' IR"", the policy function Ti.. (a'ls) 2 O. Also, Tg. (s, a) is a continuously differentiable with respect to the parameter 0'. addition, for any 0, we assume the induced Markov chain {s:)22 is irreducible and aperiodic, and its transition matrix pd is 1 (s'1s) EoeA EoeATe(als) Te(als) P(s'|s, a),
Vs,
Assumption I guarantees that the states have stationary distribution (s) over S given any policy Te. As result, the Markov chain of state action pair {(s), at)) also has a stationary distribution ds()) To(a (a(s).
Assumption 2. The instantaneous reward rf is uniformly bounded by a constant Tmax for any i E N and 2 0.
Assumption is common in the literature (see, e.g., (Zhang et all 2018: Xu et all, 2020: Doan et al. 2019)) and easy to be satisfied in many practical MDP models with finite state and action spaces. Assumption 3. Let A be a consensus weight matrix for a given communication network g. There exists positive constant 7) 0 such that A E I N is doubly stochastic and A; 2 n,, Vi E A. Moreover, Aij 2 ú, are connected, otherwise A;j = O for all i,j.
Assumption 3 is standard in the distributed multi-agent optimization literature Nedic Ozdaglar 2009). We remark that for a practical choice of A, one can use the following form A deg(C) (deg(G)-
L), where deg(g) is the degree of the graph 9 (i.e. the maximal vertex de- gree), I is the identity matrix of conforming dimensionality, and the Laplacian matrix of the graph. It is easy to verify that this matrix is symmetric, doubly stochastic and deş(ş] N
Assumption 4. Each agent i's value function is parameterized by the class of linear functions, i.e., Vo(s; w) o(s)² w where dss) A (s), ,ox (s)) RK is the feature associated with the state s E S and K < [S). The feature vectors (ss) are uniformly bounded for any s E S. Without loss of generality, we assume that [|ø())] S 1. Furthermore, the feature matrix & E [glS)*K x has full column rank. Also, for any g Qu o 1, where 1 is an all-one vector.
This assumption on features is standard and has been widely adopted in the literature, c.g., Tsitsiklis Van Roy, 1999. Zhang all, (2018 Qiu all 2021). This assumption implies the fol- lowing property: for any policy To, the inequality wT A w < O holds for any w o O, where A is defined as
An = E
(ss))o
(1)
This property further implies that for all 0, An, is invertible and Amax + AT)) < 0 Oiu all 1b, where Amax() (-) is the largest eigenvalues of the matrix.
Assumption 5. There exists a constant AA > 0 such that Amax(Are + A < -ÀA holds for all 0 E ER mi
Assumption 5 ensures the optimal approximation wy for any given policy To is uniformly bounded (see discussion before Theorem 2 and Lemma
4

---

Published as a conference paper at ICLR 2022
Assumption 6. Let (')(s, a) Vo log (a(s)) be the score function for any state- acttin pair (s, a). For any two policy parameters 8, 0' E RR mi and any state-action pair (s, S Ax there exist positive constants such that the following hold: 1): (1,, a)ll S Ce: 2): (V)) - (o'(l Is|l0
II: where (()) is defined in 2 and denotes the é2-norm.
Assumption O says that the score function is uniformly bounded for any policy and the gradient of the objective function has Lipschitz property with respect to the policy parameter. This assumption has also been adopted in the analysis of the single-agent actor-critic algorithm in (Qiu et al (021).. We note that for the discounted reward problem, this gradient Lipschitz property can be guaranteed through (Xu et all 2020, Assumption 2). We note that Assumption can be satisfied by the class of soft-max policy under the Assumption [[] as in (Guo et al. 2021).
3.3 THE OBJECTIVE FUNCTION
The goal of the agents is to find a joint policy my to maximize the global average long-term reward. Mathematically, this can be written as:
maximizeo
j(0) = lim E
Σ 1=0
Σ sEN
141
Σ #ES
do(s) Σ To(als) R(s,a),
(2)
T-x T
BEA
where R(s,a) a) N Eien R'(s, a)
the global average reward function. Let = +
then we have R(s.a) Ef = 8, at = a). Next, we define the state-action value dg a, To]. and the state value function Vo(+) = = Q0(8, a) (a) The advantage function is defined as follows:
function: Q0(s,a) EI
fe+1 J(0)]so
Advo(s, a) = Qs(s, - Va(s).
(3)
3.4 POLICY GRADIENT THEOREM
The gradient of a policy my for decentralized policy gradient is stated in the following theorem.
Theorem (Policy Gradient Theorem for MARL (Zhang et all 2018)). For any let me S [0, 1] be policy and let (0) be the global average long-term average return defined in (2). Then, the gradient of J(O) with respect to parameter 8 can be computed as:
J(O) Egndo.anme Vo. log 2/ (a'ls) Adva(s,a))
A SANSENSUS-BASER
-CROII ALGORITHM
In this section, we propose consensus based actor-critic algorithm that includes two key steps: actor and critic. In the critic step, the algorithm evaluates the value functions for the policy me, at time L. After the critic step, the algorithm enters the actor step, which improves the policy parameter 0, according to the direction from policy gradient as shown in Theorem I In both steps, we use constant step-sizes and adopt batch sampling.
In this paper, we use linear function approximations for the value functions. Specifically, each agent i has a parameter w² K to approximate the global value functions Vo w²) for each state s S. For linear approximation, we have Vo(s; w²) = ((s)TTu w",, where Φ(s) E R denotes the feature for state s. As result, the gradient of value function state s with respect to approximation parameter w is (ss), i.e. V., Vo, = ((s).
1) The Critic Step: The critic step is achieved through own oracle, which is summarized in Algorithm[] I In the critic step, we allow the agents to communicate the approximation parameters w(s) with their neighbors via the communication network with consensus weight matrix A. For agent i E N, the parameter is locally updated by following rules:
pk. (1 - -11-8)pkr + Brir41
(5)
K2,r rh.41 Wh.r + o (sk -0² (sk,)))
(6)
5

---

Published as a conference paper at ICLR 2022
Algorithm 1:
Mini-batch TD learning for Critic
Input Su, ne. O, step B, critic step iteration number K, critic batch size M, the communication network A
for k = 0, .... Ke do
$k.0 = 1.MM ( when h: 0, 8k,0 = 80):
for all i E N do
for r = 0, ... M do
Execute action oirr Tot (-1sk,7);
Observe the state 5k,++1 and reward ri r
Update MhiT+1 + (1 (1- - B3 1/ 3 Tho41i Update 8%rr t rh,t++ - 14,tr + + (92,++))uf (sk
end
Critic Step: wi f w + M - ok. ((*k.T)
8
10
Consensus Update wh+1 + EjEN, A(i,5) i
12
end
13
end
Output: 1,,, WK.
B M
Σ 8h ((8k,));
where B > 0 is the step-size of the critic step, perr is the estimate of the long terg-term return of agent and o%rr is the local TD-error for agent at iteration k using sample Here, in each iteration l in the critic step, the approximation parameter is locally updated through batch of sampling as in (7), where the batch size is M. Then, agent will further update the approximation parameter w' through weighted average of its local and neighboring agents' parameters as follows: w = ΣjEN, A (ing. This batched sampling update continues for K2 iterations for each given policy no.-
2) The Actor Step: As shown in Theorem 1 the advantage function needs to be known to compute the gradient. However, from the definition in 33, the joint action a also has to be known to compute the advantage function. whereas in model, each agent can only observe its own action. As result, an estimation of the advantage function required. Here, we show that the global TD-error an unbiased estimate of the advantage function.
At time f, suppose we have samples 8;, O2 St+1 and the rewards {ri hew then the advantage function is follows: Adva ax) E| - J(0) + (D((++1) Vo( (8))]ss, arl, and the global TD-error can be computed as follows: 5, Fr+ Mr + (8(++)) 1 - Vo(st), where 14+1 = (1 a) 11 a Fi+1 the estimate for the average long term return, and a is the step-size for the actor step. Hence, we have that the expected global TD-error is the advantage function, i.c., [[ a,] = (s 0z). Thus, we can use this global TD-error as an unbiased estimate of the advantage function. For agent i, the local TD-error can be computed 5f = rt+1 nu + Vo(s++1) - Vo(*,), where M441 = (1 (1-a)u + art41- We also note that μ4 N EveNu 14.
Thus, once each agent knows the global TD-error, the policy parameter can be updated according to the policy gradient rule in (4. However, without any communication, each agent only has the knowl- edge of its own local TD-error Morcover, we will show that the networked TD-error is actually the average of the local TD-errors. Specifically,
6, Fr+1 Me Vo(se+1) Vo(st) =
1 Σ
I
Σ
pi + Vo(sc+1) Va(s:)
NV
1+1
N
SEN
iEN
Σ brin1 - ri Vo(se41) Vo((s)) = Σ 88.
1
N EN
N
VEN

---

Published as a conference paper at ICLR 2022
Algorithm 2:
Minibatch-TDD sharing for Actor Critic Algorithm
Input state feature matrix 4 actor step-size a, Initial parameters for all N
for: 0,... do
critic update: Wt, $t.0 = Minibatch- -Driichhh---riiiee in Algorithm
for 0.... B do
for all E do
Execute action oi, ~ m0; (-18,1):
Observe the state $t,141 and reward rl.441i
Update Mi,411 f (1 - a) pi, + R..Ti441
Update 8f f r(,441 - phi d² (51,41)0t o² (st,)
Update 4%,11 f- Vo log mेद ($t.) di
end
end
81.0
12
Let Ao
67 B-B-1
i,
for i E: .V do
14
for k = 0 goovip
1 do (xtI(:,i) EjeN. A(i,5) Ac(t));
16
end end
17
18
for
all i E N do Let 51 8 = Depup(:: (:.2;;
19
Actor Step: 01 t- fi + a
2P 5i, vi.
20
B
21
end
22
end
Output: 0, with π chosen uniformly from ... T
For any time f, the average of the local TD-errors is an unbiased estimate of the advantage function. Therefore, we just need let each agent communicate with its neighbors that an average of all local TD-errors can be reached or estimated for all agents.
From the results in (edic & Ozdaglar, 2009). we have lim, A" (x 1 N I'1. However, this convergence is asymptotic, meaning that the exact estimation can only be achieved with infinite iterations (i.e., т + oo). In practice, since one can only apply fi- nite iterations, we use oū to denote the estimate the global TD-error maintained by agent i after ggsssip iterations of updates at time f, i.e., 8j [A'owp]; where A = (5),... 5.
, NYT
the N- dimension vector of local TD-errors at time t. We note that agents do not need to know the weight information of other agents. Rather, each agent just needs to exchange updated estimate of the lo- cal TD-errors with its neighbors for (gossip rounds as shown in Lines 11-16 of Algorithm 2 This communication among agents is also done in a batch fashion, with batch size being B. This implies that for each outer iteration {0... ,T 1), only tgossip rounds of communication for every B samples are needed.
Combined with a B-batched Markovian sampling, the parameter 0 update for agent E N can be written as follows: 0f = 0g + zh B-1 5t. v where the step-size for the actor step and Pi = aa log Tég (St,1, at,)) is the local score function for agent using /-th sample at time t. The actor step of our algorithm is illustrated in Algorithm

---

Published as a conference paper at ICLR 2022
5 THEORETICAL CONVERGENCE ANALYSIS
In this section, we present the convergence results for both the critic and actor steps in Theorems and 3 respectively. Due space limitation, relegate the proofs to the supplementary material.
5.1 CONVERGENCE ANALYSIS FOR CRITIC (ALGORITHM
For a given policy To, we define dy = aandy (+{))(((s,a) - J(O)), where F(s, a) 1 N Eiey r'( (s. a) and J(0) are as defined in 2 For all agents, the optimal solution (Wu et al 2020), (Oiu et all 2021) of this critic learning is w - - where Ar, is defined as in The invertiblity of Aga is due the Assumptions and 4 (see more details in (Qiu et al., 2021 Tsitsiklis & Van Roy, 1999)). Then, the convergence of the critic step is summarized as follows:
Theorem 2 (Convergence and Sample Complexity of the Critic), Suppose that Assumptions 7
hold. For any given policy no, consider the teeraiin generated by Algorithm [ Recall the definition of X in the Assumption 5 and let < min N11- x
NA 128
x. then follows that:
E
luk.
w S K1 N + + NO B2 k
AA B)* Ke 1100
K4 M
+ 2N
wōll +
N,
(8)
8
wherey= = (1 (1-1) (1--)=1),(1+2)) < and n/j n2z R3, K4 are positive constants. If we further let Ke 2 N3
max GNi log 1-) -/
12Nll@n-w3l B S minf
3 v Bnl 2(1 2(1-1~11) 128
da
4
and M 2 GKAN then we have E lluck wall S for all E N with total sample complexity given by =oM=0($ N log( ))
Theorem 2 establishes a convergence result for the policy evaluation of given policy za. We can see that our constant step-size batch-sampled critic process can achieve the same complexity of Ö(e-1) order-wise as the TD(0) learning in Doan et al (001)) where diminishing step-sizes were used. On the other hand, in the single agent average reward setting Qiu all (2021), there exists a von-vanishing error term in their critic convergence. In contrast, with proper choices of iteration number K₂ and batch size M, our mean-square error can be arbitrarily small.
5.2 CONVERGENCE ANALYSIS FOR ACTOR- -RRITIC ALGORITHM (ALGORITHM 2
Define the approximation error introduced by using linear approximation in the critic step, Sapprox max BeREe m. 1g [[Vr. (s) Vw=: [3) For given policy ne, this error represents the gap between ground truth value function under such policy and the value function obtained by the best possible linear approximation. Such an error term is standard in the literature where linear approx- imations are adopted (Qiu et al. 2021: Xu et al. 2020). Let Ry,. defined in Lemma 4 be an upper bound on ||el|| for all policy parameter 0.
Theorem 3 (Overall Convergence Rate and Sample Complexity). Suppose that Assumption 6 hold. Consider the actor-critic algorithm in Algorithm 2 Let step-size at.. It then holds that:
E[I[v0J(07)111
16LJTmax
+ 72N
Σt N
==
||w] wß,1 112
V88g -17 N1
T
T
+ 288 (Tmax RRw [1+ )
+ (2x 1)pl N,
c2 Sapprxx
B(1 p))
where Ka is positive constant. Furthermore, let T' 64I. B > 576 (Tmar + 2R,,, 1 (2nc 1)pl N
(1-p)
and the communication round among the agents t tgassip 1og 64kg Suppose for the N
same setting in Theorem holds that EI llwkk. w1ll 288N for all 0 S S
T, then we have e (0.) S e O (soppee)) ) with total complexity of (B + MK.)T
O N² log( NN) )). And the communication complexity is (Ke + (goosip) T O log( )).
8

---

Published as a conference paper at ICLR 2022
74
2.15
2.1
2.6
1.4
HARI
1.0
1478 Wil
WARL Theakan
Sample Complesty
Complesit
Semple Complexity
(a) System size
(b) System size N 10.
(c) System size 15.
Figure 1: Our TD-sharing algorithm vs classical MARL algorithm.
Theorem 3 concludes the overall sample complexity of our proposed actor-critic algorithm. The sample complexity of O log(E=²)) matches the state-of-the-ar Angle-agent actor-critic RL by Xu al. (2020) and the discounted MARL by Chen et al. (2021).
We note that the overall communication complexity also matches that of (Chen et all 2021) in the discounted reward setting. However, our work still an improvement compared to the classical MARL in Zhang et all (2018) for the average reward setting. Specifically, a communication round after each sampling. By contrast, in this paper, we only need a communica- tion round per (c--)) sampling. This is thanks to the use of batch sampling in the actor step. Also because of the batch sampling, we are able to use a constant step-size for both actor and critic steps. Here, the overall communication cost measured by the number of communication rounds rather than the size of bits transmitted over the network. We follow the standard definition of communi- cation complexity the literature, which widely adopted in the literature, see (Chen al 2018) (Zhang et all 2019). However, note that fgossip. actor step batch size B and critic iteration rounds Ke, scale with Ollog I/e), O(1/e) and (log 1/e) respectively as indicated the Theorem 3 and The amount of information (in terms bits) is (K,NK + BNtgussp)) T O N log ).
et all (2018) 8) needed
EXPERIMENTAL RESULTS
In this section, we conduct experiments to compare our proposed consensus-based TD-sharing MARL algorithm with the most related MARL algorithm in Zhang et all (2018) that also stud- ied average reward. To our knowledge, this is the only work that is directly comparable to ours. The key difference that the knowledge of joint action assumed in Zhang et all (2018), but not in our work. We vary the system size from N = 6, 10 to 15. The blue curve is our TD DD-sharing algorithm and the red curve is classical MARL algorithm average results of 10 trials and the 95% confidence intervals are also plotted. For the details, see A. Appendix. The results
Zhang al. (001)). The curves represent the
Tigure[shov that different system sizes, both algorithms converge to reasonable objective value. Note that if we use uniformly random policy the baseline policy, then the objective values will be around due to the setting of our experiments. All simulation results are above this threshold and our TD-sharing algorithm converge better objective value. See Section A.2 for addition experiment results.
CONCLUSION AND DISCUSSION
In this paper, we studied fully decentralized MARL in average reward setting and proposed batch-sampled actor-critic algorithm. Our main contribution to establish the first finite time con- vergence result for fully decentralized MARL in average reward setting, where the complexity is Occ-2 logg"log(cc")) log(c=))) which matches that of the state-of-ther tf-the-rrt single agent RL. The algorithm reaches such convergence with better communication efficiency. However, it is still in the preliminary stage of the convergence analysis of the MARL since we only used the vanilla average. The future direction will be how to design scalable algorithm in terms of system size.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
Hairi and Jia Liu's work has been supported in part by NSF grants CAREER CNS-2110259, CNS- 2112471, CNS-2102233, CCF-2110252, and a Google Faculty Research Award.
REFERENCES
Rajendra Bhatia. Matrix analysis, volume 169 of. Graduate texts in mathematics, 1997.
Tianyi Chen, Georgios B Giannakis, Tao Sun, and Wotao Yin. Lag: Lazily aggregated gradient for communication-efficcent distributed learning. arXiv preprint arXiv:1805.09900 089659955. 2018.
Ziyi Chen, Yi Zhou, Rongrong Chen, and Shaofeng Zou. Sample and communication--fficciee decentralized actor-critic algorithms with finite-time analysis. arXiv preprini arXiv:2109.03699, 2021.
Thinh Doan, Siva Maguluri, and Justin Romberg, Finite-time analysis of distributed (0) with linear function approximation on multi-agent reinforcement learning. In International Conference Machine Learning. pp. 1626-1635, PMLR, 2019.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agen policy gradients. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018
Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single-timescale actor-critic provably finds globally optimal policy. arXiv preprint arXiv:2008. 2020.
Xin Guo, Anran Hu, and Junzi Zhang. Theoretical guarantees of fictitious discount algorithms for episodic reinforcement learning and global convergence of policy gradient methods. arXiv preprint wwXiv:2109.06362 2021.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
Donghwan Lee, Niao He, Parameswaran Kamalaruban, and Volkan Cevher. Optimization for rein- forcement learning: From a single agent to cooperative agents. IEEE Signal Processing Magazine, 37(3):123-135, 2020.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Soc., 2017.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions Automatic Control, 54(1):48 61, 2009.
Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On finite-time convergence of actor- critic algorithm. IEFE Journal on Selected Areas in Information Theory, 2(2):652-664, 2021.
Martin Riedmiller, Andrew Moore, and Jeff Schneider. Reinforcement learning for cooperating and communicating reactive agents in electrical power grids. In Workshop Balancing Reactivity and Social Deliberation in Multi-Agent Systems, pp. 137-149. Springer, 2000.
Shai Shalev-Shwards Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXivv1610.03225.. 2016.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 140 1144, 2018.
John N Tsitsiklis and Benjamin Van Roy. Average cost temporal-differee learning. Automatica, 35(1 19111)):99999989 1999.
John Tsitsiklis and Benjamin Van Roy. On average versus discounted reward temporal-differenn learning. Machine Learning, 199 2002.
10

---

Published as a conference paper at ICLR 2022
Yue Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite time analysis of two time-scale actor critic methods. arXiv preprint arXiv:2005.013500 2020.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. arXiv preprint arXiv:2004. 129566 2020.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. On the global conver- gence of actor-critic: A case for linear quadratic regulator with ergodic cost. arXiv preprint urXiv:1907.062: 2019.
Chao Yu, Xin Wang, Xin Xu, Minjie Zhang, Hongwei Ge, Jiankang Ren, Liang Sun, Bingcai Chen, and Guozhen Tan. Distributed multiagent coordinated learning for autonomous driving in high- ways based dynamic coordination graphs. IEEE Transactions Intelligent Transportation Systems, 21 2019.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. In International Conference on Machine Learning. pp. 5872-5881. PMLR, 2018.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbbook of Reinforcement Learning and Control, pp. 321-384, 2021a.
Xin Zhang, Jia Liu, Zhengyuan Zhu, and Elizabeth S Bentley. Compressed distributed gradient descent: Communication-efficiee consensus over networks. In IEEE INFOCOM 2019-IEEE Conference on Computer Communications, pp. 2431-2433 IEEE, 2019.
Xin Zhang, Zhuqing Liu, Jia Liu, Zhengyuan Zhu, and Songtao Lu. Taming communication and sample complexities in decentralized policy evaluation for cooperative multi-agent reinforcement learning. Advances Neural Information Processing Systems (NeurIPS), Virtual Event, Decem- ber 2021b.
A APPENDIX
In this section, we provide lemmas that lead to the proof of both Theorem aldd Theorem 3
In this paper, we use || for 2-norm and || ||rv for total variance norm. (:--) denotes the inner product. Superseript in quantity æ. i.e. x². denotes the quantity correspond to agent i E A. X() and (-) denote the eigenvalues and singular values the corresponding matrix respectively. All vectors are assumed be column vector, unless specified. (-)² is the transpose of an matrix or vector. We use 1 to denote all-1 vector with proper dimension. For matrix A, [A]; represents the i-th row of matrix A. Let comparison. 8 denotes the scalar global TD-error error, i.c. = + Eiex
[6' ..... 8N1T. i.c. the column vector for local TD-errors. In
First, we explain the detail of our experiment setup.
A.1 EXPERIMENT SETUP
We considered the same setting in the Section 6.1 of Zhang et al. (0118). There N agents, each has a binary-valued action space, i.e. A'' = {0, 1}. for all E N. In addition, in all the results shown here, set the interval [O. 1] and normalized to be stochastic. We also added 10 onto each element to ensure ergodicity of the MDP such that the [ssumption[[is satisfied. For each agent and state action pair a), the mean reward R' (s, a) is sampled uniformly from [0, 4]. The instantaneous rewards r are sampled from the uniform distribution [R' (s, a) - 0.5, Rt following the Bolzmann policies, i.e.,
states. The elements in the transition matrix
uniformly sampled from
(s, a) + 0.5]. The policy is parameterized
exp(12..00)
The (s, EvEA explo
11

---

Published as a conference paper at ICLR 2022
where 96,6 is the feature vector with the same dimension 8", for all S and N. Here, we set my
mn 5. The elements of Is.bi are uniformly sampled from [0, 1e3]. We set the dimension for state features K = 3. The feature matrix & are insured to have full column. The stepsizes for classical MARL are set as Bu.t = #0.51 and Bg.: = 20.52. The network matrix as chosen as ring network with diagonal elements being 0.4 and off diagonal elements 0.3..
For our algorithm, we used step-sizes a 1 and 0.1. The batch sizes are B 10, M 10 and the critic iterations are 10 and actor iterations are T 100.
A.2 ADDITIONAL EXPERIMENT RESULTS
We have modified classical MARL into i)constant stepsize MARL, ii)batch MARL and iii)batch constant stepsize MARL. For classical MARL and batch MARL, we chose the stepsizes as 3 = ga.ss and Bg- aa in the paper (Zhang al.. 2018), and for the constant steptize MARL and batch constant stepsize MARL, we chose stepsizes to be 8.... = 0.9 and Bg = 0.01. For batch MARL used batch size as 10. Other parameters are the same in We vary the system sizes from N = 5 to = 15 and the empirical comparison results are in Figure (a)-(c). In addition, we provide the comparison between average reward setting with the discounted counterpart of our algorithms for discounting factors ranging from Y = 0.1 to 7 = 0.999. As we can see from 2 (a)-(C), our TD-sharing algorithm performs well compared to the base- line algorithms. Among the modified algorithms, batch constant stepsize MARL shows improve- ment compared to the classical MARL in all three cases. Moreover in (b) and (c), when system size is larger, specifically N 10 and N = 15. either batch modification or constant stepsize modifi- cation seem to improve the classical MARL. Yet (a), for smaller system size, i.e. N = only modifying to the batch size constant stepsizes don't 't seem to improve the performance.
and batch constant stepsize MARL,
the |
In addition, in (d), for discounted setting, as y increases and gets closer to I, the objective value is closer to the average reward setting. It is because as the discounting factor approaches 1, the effective horizon, which scales with O log c (Kakade, 2003), to an e close stationary point gets larger and larger. As a result, it will get closer to the average reward setting. However, we can see average setting value converges to significantly higher value. More importantly, one advantage of the average reward setting is that with more samples, the policies can potentially keep updating and so is the objective value. From Figure 2(d), we can see that as the number of sample increases, the average reward setting objective value still evolves, which means the policies are keep updating. However, for the discounted reward case, the extra sample doesn't it affect the objective value.
In Figure 3 we have shown the results of different network structures on the performance when system size is 10. We compared the ring network, small world network and 2-regular network. The small world network is generated with mean node degrees being 4 and rewiring probability being 0.2. The entries of matrix A, for both small world network and regular network, are set as the way discussed after Assumption 3 Different network structures exhibit different performances, but all are better than baseline value Among these three structures, within given sample numbers, ring network yields the best result.
A.3 SUPPORTING LEMMAS FOR THEOREM
Because of the Assumption 1 by Levin & Peres, 2017 Theorem 4.9), for aperiodic and irreducible Makrov chains, we can guarantee the following lemma holds:
Lemma 1. For any policy parameter E EiEN m., consider the MDP with policy zo and transi- tion kernel P(-|s,a, Let dg be the stationary distribution of the MDP. There exist constants k > 0 and p E (0, 1) such that supses [| 80 = 8) - dellTv S kp', V12 0.
This lemma has been adopted directly as an assumption in many related works in theoretical analysis of RL (Xu et al_ 2020 Chen et al. 2021: Oiu et all, 102
As a result of the Lemma [ the Markov chain of state-action pair {st, at heo for policy Ty also has the property of ergodicity. We state this result the following lemma.
12

---

Published as a conference paper at ICLR 2022
2.4
2.3
22
2.15
365
2.05
classic MARL
classic MARL
1.95
Constant Stepsize MARL
Conslant Stepsize MARL
Batch Constant Stepsize MARL
1.7
Batch Constant Stepsize MARL
1.9
TD-sharing MARL
1.0
1.85
0
2
3
Sample Number
x10
Sample Number
x10
(a) N 5
(b)
2.15
2.5
2.05
1.5
J00
TD-sharing
1.85
Discounted Counterpart with --0.1
Discounted Counterpart 0-0
Batch MARL
0.5
Discounted Counterpart with +=0.9
Constant Stapaize MARL
Discounted Counterpart with --0.99
Constent MARL
Diecounted Counterpart
TD sharing MARL
1.85
Sample Number
x10
Sample Number
x10
(c) N 15
(d) average vs discounted
Figure The empirical comparisons algorithms
2.25
2.2
2.15
2.1
((0)
2.05
Ring Network
1.95
Small World Network
Regular Network
1.9
3
5
Sample Number
1
Figure 3: Different Network Structures on Performance When N 10
13

---

Published as a conference paper at ICLR 2022
Lemma 2. Suppose the Assumption hold, let vg be the stationary distribution of the state- action pair MDP. Then, we have
sup
P(s;, 0yls0 = 8) vollTV S kpp, V2
(10)
Proof. For any given 80 E S, by definition, we have
1
(e vollrv
Σ
PP( 8, a/so) vs)
2
(s,a)e5xA
Σ
P(s: = sTso) = a/s; = =8) - -((())((aass)
2
(AA
Σ
[(((s: s|s0) ((((s))=o((ss)
(s,a)ESxA
Σ
To(a|s)[P(s: =|/0) - r3(s)
(s,)ESxA
Σ
P((s: = s|s0) - vz(s))
2 #E8
|| (sn) vollTV S kp'.
Since it holds for all so S, equation 10 holds.
As result of Assumption 5 we have the following lemmas.
Lemma 3. For all policy no, we have
AA ||ol|2
(w, Ana w) S 2
(11)
where Aa is defined in Assumption
Proof. Because of the fact w Ax, w = w² A w. we have
w² A w
(w" Ano w + w² A w)
2
u (A + ATo )w
2
Aa w"
AA |1/0122
(12)
2
In fact, interestingly enough, the Assumption and Lemma are equivalent in a sense that the statement in the Lemma 3 is taken as the assumption, the statement in the Assumption 5 can be obtained as result. And the paper (Xu et all 2020) used the statement in the Lemma as an assumption, whereas in ours and (Qiu et a 2021), we assumed Assumption
Lemma 4. For any given policy πy. the corresponding optimal value function approximation pa- rameter w is uniformly bounded, specifically, there exists R., == Armax XA
such that
||gll S R..
(13)
Proof. It's easy to see that (()) S Tmax from equation 2 and F(s,a) S Tmax for any (s, a) pair. Then, have
||lس|| ||
A 1-1bbel
14

---

Published as a conference paper at ICLR 2022
|| (w o(s))o
(())]I (0 J())I
< || (f
(1) o()))o" -
min (-Eands (N), (1 ((-s0) (())) (
[ J
aow -
J(O))lI
Amin' ( ATo
2E 2g [|] (
4r max
X
where the third equality used the fact ||A-1|| from Bhatia (199) (Proposition III 5.1).
Omin (A) and the second from the last inequality is
Note that, for agent i E .N, the estimated long term average reward phrr at sample of iteration A in equation can be written
3)- -1- +1 B) 3)-bo-
(14)
1=1
Lemma 5. For any i E N and 2 0, step size 0 < B < 1, for the estimated long term average reward for agent we have
M4+1 = -1-1111100 3) + Br
(15)
bounded by Tmax iee. |pita| S Tmax.
Proof. WLOG, we suppose that 0 < ub S Tmmax. we have
In(+1l 1(1 - 3)yb + 3r
(1 1-) + 31r21-
(16)
By the supposition, we have |Hس/ I Tmax. We assume wil S Tmax holds for iteration t 0, then fort + 1, by equation 16
W S (1 - 3)1d + Blril S (1 3) + -rmax = Tmax-
Therefore, Lemma 5 holds by mathematical induction.
For a given policy Ty. to establish bound on the difference between the optimal approximation parameter wz, first derive bound the difference between parameter wi and the average among all agents Wk at time k. Then, we derive a bound for the difference between average Wy and the optimal wy.
We have following notations for the analysis. Given an agent E N,, we consider the consensus error at time i and we denote Qi wf Wk, where úh N Eien wt- Then, we denote the matrix form as Q2 1Q) Q R KxN Then, we have the following lemma.
Lemma 6. Suppose the Assumption 2
and hold. For the consensus error matrix, we have
||Q++1|| Skg | + Kg
(17)
where y = N-1) (1+ < 1, K1 = 211 + (1 + and k/g = +1 (N (NN Jmmax
Proof. By equation
the parameter update wi for agent iteration is can written as follows
3
+
8h.r
((Sk.T)
M
3
M-1
= # +
Σ
3
"h - -(1 (1- 133)mm -1 -
M
T=0
1=1
15

---

Published as a conference paper at ICLR 2022
+ Φ ((5k.T+1 T - o(sk,))) uuil ((5k.T)
8 M-1 # +
(00,,))(((sKTTTT))) - (((k, )1"m]
M
T=U
3
M-1
+
Σ
(r -
Σ (1 - B) -
- (11- (1--)") ())()(O))))))
(18)
M
r=0
After consensus step, the update will be
wk+11
Σ
A(i.g)
JEN,
3 M-1
Σ A(i.j) [ur
Σ
os ((((,))))(( (1 wx
M
JEN,
0
B M
(T (RTT+1
3 Σ
(1 - 3)- k.l - -11- -11_) 16)6(().T))
M
7=
1=1
8
M-1
Σ A(i,j)
w/
Σ
((8k+))1 Σ A(i,j) w
M
JEN.
JEAL
B M-1
Σ ((sk.r)
Σ
A(i,)) (1 (r 1 BE (1- T/.1
- (1- 3)7
M T=U
JEM
1=1
M-1
3
Wk ww- (AA.)"
+
Σ
(o(sk.r)(() -00--11))0($_-7- ((8k,))1 ) -AAs.)
M
7=0
B
M Σ
d( Ar. (1k,741
Ea 211 -y- (1 -38
(19)
where W [wt, wh.- ... w E RKXN is the matrix form of all parameters at time k. A is the i-th row of matrix A and Fk, (rk, ,.,,) Now we consider the average dynamics of the algorithm. Recall Wi = W/4 EiEN wh. then using equation 19 we have
1 Σ
wh+t
Wk+1
N
iEN
M-1
Σ
Wh (A,,) +
Σ
( (0((k.++1 ((8k.r) W (Ar,))
N
M
EEN
T=0
3 M-1
((5K.T)
(r, (Tu,T+1 3 > (1-8)) 1/-=-/rxtt - (1 99) (3)TTM mo)
M
8 M-1
Wk
1+
1
(sk (0( - ((3k.t)]²"
W N
N
M
T=0
M-1 Σ
1
+
((SK.T)
Σ
A - >
B) -
Tk. - (1 ()0
M
N
T=U
iEN
1=1
8 M-1
Th +
(skk))
M
8 M
+
Σ
(SkkTT
T
(Fk. - 3 > (1-50 (1-9)- Tki1
-0-)) (1- -3)
M
N
1=1
16

---

Published as a conference paper at ICLR 2022
B
M-1
W2 +
Σ
- -((ski7) )1" 11'xxx
M
7=0
8
M-1
Σ
((8E,)
501 t=1
(1 - - (1- m))
(20)
M
where Fk.1 EiEN
Given an agent E N, we consider the consensus error at time and recall Qj = w/ Tx. Then, have
Uh-1 -w/+1 W6+11
3 M
-W (Ai..)
Wkk
Σ M
o( (((0rT))))) (65k,t)) (Ac.)* wwx)
M-1
Σ
((sk.))
1 (rk,r++ -3 E --- rk. (1 1 33 No). (21)
1=1
Then, for the matrix form Qu = 10 ... .04 E RKXN we have
8
Qk+1
=QAAT
+
- o(sk.r - )1² Q
M
T=U
8
1
((A, 11 (rk, Σ (1 3)--1rk. (1 B)² fo)
+
M
M-1
8
Qu
+
Σ
- ((kk (o(skrr1)))))
M
T=0
M-
+
8
((KE
B D
1 (1-)) (1 p0) (A- - 117)
M
N
7=0
1=1
(22)
where the first equality is due to A being doubly stochastic. For convenience, denote Bg- M EMT ((sk.)))((sk.T+)) d(sk.))] and Cj 8) 8 - (1 3omo Then, iteratively have
I
1 EMO' o(sk, ITkkr41 E Mt
1 Q++1 =(I + (.,3B))uu A + (A30((A N 111))
( Qu
3B: CA- 1 aA
(23)
1=0
t=
Then, the norm of the consensus error is following
k
k
||Q+tll = II (I + 3B,) + 3
III
(T+ CB (11))A-11)
N
1=
1=0 E>t
I (I [
3BIIl| ((Qo(A7) k+1
3
II
(I + 3Bi1l ||C,]| -cll--1(A--
1111 T )
-
N
1=0
ix1
(24)
Note that since is doubly stochastic, so is AT, Let (AT) From Nedic & Ozdaglar (2009), know that
k+1 be the i-th column of matrix (AT)++1.
Qu *+ = (AT)
Qu N
1|
17

---

Published as a conference paper at ICLR 2022
-1 -1
((
1
N
JEN
Σ
1(A))
1
1lll
N
JEN
1 1 -N-
N 2 17 N-
11¹h 1
max
|1%/1
JEN
21 + 17 11 )[1 -np 1 -
(25)
Hence, ||Q ++1 < 2N2 + (N (8- (1-
|o| To bound the first term in the RHS
of equation 24 we have
b (1+ + (B,)I & II
II t=
| 3B.11
1=0
II
+||BBI)
==
&
(26)
t=
In order to make sure it converges to the neighborhood of consensus in the limit, the step size has
N-1 to satisfy y == (1 - 1/ 1/ (1 + 23) < 1, which results in 3 2[1 2, Hence, for the first
term in the RHS of equation 24 we have
II 1=0
(1 3BDIII 110I11110444 =
where 11 = 2(11+ + 23) + 7 (N 11-
Furthermore, we have
||A ||A [I(A 11 +1
1 11 S 22N2 + +1 IN-N))))(1 17 N-1nh- (27)
N
N
And |C&l| < 2.Nr where Tmax = supi,sa r' (ss a). This is because
M-1
||C/|| =
(
Σ (1 '
rk. - -1- Hol |0l
M
1=1
M
[1 ) || -3 2 (1 8)- The " (1 -3" no)
M
1=1
11-1)1111111444 [[0(
(1 - (1 3Y
<
[| + 2 3) 3/- -|ralll + (1 - --)
M
1=1
M
+ 3 - (1 - ())
Nrmax
Nr max + (1 3)7 N Nrmax] 2N maxx
M
1- 3)
Then for the second term of equation 24 we have
(I + BB |
((AA
1
11 11T)A A
N
1=0 i>t
18

---

Published as a conference paper at ICLR 2022
SB
+ 23)x k-t m2ax 2N (1++) (1 -17
1=0
k K2N33 1 - g 1
K2B
(28)
1=0
where K2 4(1 + 17 (V-1)) ) maax. Further, for consensus error equation 24 we have
||Q++1|| k2 || K2N 1 - -
1-9 Sk1 1|Q KgN28
(29)
where xn2
Ka
The corresponding average parameter under the policy To will converge to the solution to the following equation wi Ap where Ag (s ((+))²) by [(ea))=d((s))((((:
((0))((s)) and F(s, a) = n r's, a).
Now consider || - -w'l. Recall from the average parameter equation equation 20 and the corresponding ODE is
Aguo + bg. ig
(30)
For the difference between average dynamics and the optimal value, we have the following lemma. Lemma 7. For B min
128 X and M 2 ( B)
614441+(x-1pp)) we have
(1-P)AA
AA | 0o w + Aa
1 + 3) 1536(4R2 - r m1 + (K 1)p]
[ -0gl S (1
8
(1 p)AaM
(31)
Proof. The proof follows from verifying the Assumption 3 of Xu et al (002)). then we can apply the results from Theorem Xu al (2020).
1. For item in the assumption, it's easy to check that ||Aa|| S C. 4 by Assumption 4nd
by < C 2r max.
2. For item 2, it holds because of Lemma
3. For item 3, it holds because of Lemma
And we recall that the bound on ||w/||| is Rw 4rmax Hence, by Theorem 4 of Xu et al. 2020 min
Xa
and M + 2,3) 19203 19 (x)-))) equation 31 holds.
A.4 PROOF OF THROREM 2
As result from Lemma and Lemma 7
we provide the following proof for Theorem 2
Proof. Therefore, by equation 17 and equation we have
lu w [2
N
N 1 - wx + 2E
$ 2E
|0x w/ll
<2|
2NE|| -wقسl w6
Xa
< N2, ( =||Qull N² 2N
3) K 11000 - wil2
8
19

---

Published as a conference paper at ICLR 2022
192 R + +,, + +(s (1)p)pp
2N + 25)
1
AA
(1 (1-P)
AA B)x 100 will +
XA
$ k 22
+ 36
+ kk B +22
NV
M
where 1n 2n 12 R²2 =2X
K3
4k1k2|1 Qoll and 64
62 +
3072(4 tr (x-
()-A)A
A.5 PROOF OF THROREM 3
We wi denote the optimal value function parameter under policy Og time and Wr = [(w])=" :... ("r"" E RNN*K, which is the aggregated function approximation pa- rameters from Line 2 of Algorithm [2] Recall the 8f generated by Line 18 of Algorithm 2 which is the i-th agent's estimate of the global TD-error from sample at time t after con- B Li (2,(())) vif,, and ve(wr) [1] (w:))² ,.... (1f" (wx))²JF h/(w[t) n EEo dr,((17) 4h,, and he(wt) = [(h] (wot)) ..... (41 (wt)) (s, = Bt.. (s.a) (s, a, s,,5))ss [|s,at a] and g' (w, 0) E[Adv a)ver (s, a')]. where ds is the reward distribution of state-action pair (s, By Taylor expansion and the Lipschitz property from Assumption we have
sensus. Let uf:)
J(0++1) 2 ((0,) + (VoJ(0.), 0c11 - B1) 2 1110+11 0bl1
= ((,,) + +V (w(w)) - VoJ(O.) + voJ(O.)) - LJa²
2
Lja²
+ a 11000 v((m)) veJ(O.))
2 -|ur((r))
-V)((0)) (0,)11
1 2 ((O)) + 2a a - [(ao) 1a
where the last inequality is because
(VoJ(()), v(()) - voJ(H.)) 2 - (or(ws) - [oJ(1)
and
[]v((),) Vo.( + VoJ(())) > (w)) VoJ( VoJ
(32)
Taking expectations on both sides conditioned on the filtration F, and rearranging the terms, have
1 a-- - -=
< (0)
+ Ga + LJa )Ba (0.)(1))
(33)
Then, we establish upper bound on the third term of the RHS. By definition, we have
[[vx(wr)) - [(.))1
= =11vx(we)= - v,(w)) + v.()) - h((w]) + h((w)) - g(w 02) + g(w], 0.) - (oJ(1)))
5 (wx) v1( + 6/ 6((vz(w;) hr 11 (w?) oww,, 0.)1
61lg(w], 02) vo.(1.
(34)
We note that [wxx) - u2 (w 1| E [|o - (wx and the other three terms in equa- tion 34 can also be similarly decomposed. For the first term in the RHS of equation 34 we have
[|o{(w))) v(((w))1²
20

---

Published as a conference paper at ICLR 2022
B-1
B
(wre)
1
Σ
(w,)) viull?
B
B
1=0
18 ((, - [[,((W]]]] +1,,11?
1 B
Σ 1=0
[A (A(owt)):(w) - un "ur"1")
- ((xe)) (6(()--)))(((((( - 12,111
(w,, """"1"""(((sstt1))
[0(().111) - ((s.,)) w1,111?
max
(6 BB-
(E BB-1 ||[AArrar]] |:100m]1111[[(((01++] -((ss)))1) 112 11
max
4. (4.110; wi 1/1 Σ
|wm will
(35)
where the third equality is from
8t.r(u:) (wf)
[A (coos)) (,0e,(122) [A [A (:3,((())
[A (roo))))) l/ (0),(
(s11+1) - -(t) - o² (sc)((ut wi)
[A [A'mooo]
oJ (w) -wf) w (s(()))( - w27)
[A ); (w, w (6())))))
For the second term in the RHS of equation 34 we have
[,o}(w;) - (1w
1 B-1
1 B-1
-11
8 (ut)) v4,11
Σ
(.,(w])) 11
B I=
B
1
R-1
-11
1
(w,) - Se,((we() )] v1,11? -
= 1
1
Σ
B-1
[AA
-
1 x11)) (w)(w)) vt,ll?
1=0
<
max
|| (Ia'mmon]
N 1T (.,(wi) -i,Il??
(0.....B-1)
1
max
||[A/rsio]
1
1/ (|,,, -110)11111111 11
le(U,--,BB- B-1)
N
1 + 17
11)
< max
(2
(1 17 -1 ||0,,( (1]]]]
1e(0.-. B-
1 - N
16N + 11 (N-1)) ~,,~~ -1~~-)oommn )² (rmmx + R2o) = K3 2 17 N- 2 20
(36)
where Ky 16(1 + n (N 1))
(r (rmax + R2 We note that the second equality is because
(1,( - (2,((
= 1.0. -
N 1 (
= (Iatimio)) - 1 - 1") Be((w)).
21

---

Published as a conference paper at ICLR 2022
For the last inequality, we note that (t,((=)) is bounded because rewards and feature vectors bounded, μ² is bounded for constant step size and wi is bounded from the critic step. That is, for j E N entry in (w"" by definition,
(,,( =r(, 14, (0($1_-1) ((8,.))
Hence, its 2-norm bound is
[",, = 11 u4, + (0(82++1) ((s,,))"
$ |1 + || (10(se.41) - ((s.,))l.
- Tmax + Fmax +
Rw S 2rmax + 2
(37)
For the last term in equation 34 we have
(1 02)
[o,(l
(s.a) (Avww; (s, a)wo, (s, a), (s.0)) (Adv (s) (s,
|[Bd (s,a) [(dd (s, a) - Advo, (s, (s. a]]l
(Bed, (a.a) (Adv mz (s, a) Adva, (s. (s. a)ll))
(Ede, (a)a)
Adv m (s, a) (s, a)] /|, (8, a)l
(Eda (n
||Adv (s, a) (s, a))
(Eda, (s.a)
[|E[V (s')[s, a] Vu; (s) - E[Ve; (s')] + Vo: (s)
S (Eeo, (.)
[[B[Vug (s') Viz (s') + Vn; (5) - Vvz (s)
(Edo, (s.a) [B[]Vun (s') Vo; (s') + Vu (s) Vo; (s)
Vw; (s) - Ve: [s)]] - Vw; - Vo: (s)
S 4(B[ (s) Voz (s) < 4E| Vwg (s) - Vo= (s) < eeritic
(38)
Sppptxx
For each i E N, we have
[1/](w]] n² (w] 0!11 Se, (w) Vos E. (Ad (s, (s)
B
B-1
Σ
Se (w) woo [Adv (s,
B
B- B
(dr, (w)) - E.,a (Advi; (s, a) (s, a²)) dr (w, (w)) - E E.. (s, (s,
B
B
1
((0,((1))) - aE,alAdvvwr (s, a)vi (y (s, a²)
B
(8e,, (w)) [Add(Ad or (s, a) (s, a²)), 88,1 (wo)) E.,a [Adv (s, (s, (s,
B2
Taking expectation the filtration Fe, we have B[]lk((w?) of (w, 03){]
B-
E
( we: - E.,a (Adv (8, a))a [')1[
Ba
Σ
E (w7 E. (s, (s, a'), 8 (wi)en (Aw; (8, (s,
B
1
16
5 (Fmax + R2
E E. (Advv (s, a)wa (s. (s)) 8e,, (w)) E.,a (Adv (s, a))i (s, F()
B2
1
22

---

Published as a conference paper at ICLR 2022
where the incquality follows from triangle inequality and the facts that 1 (wf) I mmmax + 2R and [Es,a [Adww; (s, a) a)v (s, a']]l [ (we D60;]l I 2r + 2 WLOG, for the following term, we suppose 1 < l2. Then we have
E
(8e,, (wf) -E,,a (A.alAdv... mn (s, a)d% (s, a')), 5 (wf) E. (Adv (s, (s, (')))
E
E (de.t, (w²) Es w (s, a) vi (s, a²) }], S (w) wo: E..lAdv
()) Fr.41 |r/
E
(de.1 (wn) yoho -.,.a
)1, 82. (m) Do: Es,a (Adv
() F 1.1, [[
E
( (w )o: Essa [Adv
}1 R R (w Way [FE.]] E., [Adv w (8, }}
E
(6c.1. (w-) yoog - E.,a [Adv
] | Adv mi (5t,12 ane Moy [r.. Es,0 Adv (s. a) (s. ))>}
1, (w:) )ooe - Es,a (adV
I|I E [Ad (St.1. and obg [e,, Es,a (Bya (s. a) (s. (s.
2 max + 2R )E [|E[Adv (81.2)) C1 12,22 oo Fe..) - Es, (Adv (8, a) (8, d3)11l
<16(rmax ) (o_))xx'==1
where the last inequality follows from
[[B[Adv (81,42 (t.1 tho [F,,,) B.,a [Avv (8, v) (s. a² a')]ll
-Il Σ wd (8 0t, (e,22))oo (11,)) P(St, a1 (,.
Σ
Adv wr (s, a))a a)v a)ll
(de.2g (e.22)
(8,a)
Σ [|Adw (s, a) (s, a')ll (apiillp'''> (s. vo, (s)
<2(2rmax 2R
((Fi)) - (8,
<4(rmax + Rw )mp's hmppa-t. 11
Then, we have
B B[]h)(w]]) 0 [F
B [r6 + R2,) + 16( + R Σ phann
12711
1 ( + R2m)) 32(rmax max + )2x) )2pB 1-p p
B
16 16(rmax + (1 + (2xs 1)p]
(39)
B(1 pp)
Then, we have
Bl]lux(wr) VoJ(0.)] S24N Σ
| will + Ging,N((1 - N1)
96(Tmax + Ry R1 + (2x 1)p) N
+ 24 +
(40)
B(1 - p)
As a result, substituting equation equation 40 into equation 33 and taking expectation over F, on both sides, we have
1 a- LI
1
N
$ -E](((+)) + 12a + Lsa?)
24N
Σ
loo - w 1|2
23

---

Published as a conference paper at ICLR 2022
(Tmax
Rw ) + (2k - 1om-1ppppp - N).
+6KgN - 11 11 +
24cariti
Sappoox + 96
(41)
B(1-1
By considering step size 41." and dividing both sides of previous equation by 167,' we have
NV
-[ 72N
||w we 1
(Tmax + Rww (1 (2N 1)p]
+ 18 11 2 + 72 + 288N
B(1 PP
(42)
Let 1't be a random variable that takes value uniformly among {1, T). Taking summation over
t (1.-.. ( and dividing by T, we have
T Σ
E [
Bll [
161 (B] - R(J(())))
T
N ===
| -w/l
72N
T
T (Fmax ( (2k 1)pl
+ 1883NN 17/ 11 11) +
72eciiii Sapprox
288
B(1 - p)
16L,E[J(OT)
| -
w|l1
+ +2NN
T
T
(rmax RRw)) (2x 1)p] N.
+ N8 - -1) 2) + 72
288
Supprox
B(1 - p)
24


Reviews:
[{"review_id": "oAXFeNvCmg7", "reviewer": "Reviewer_avem", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, the paper is well-written, well-motivated, and the literature review is very complete. I enjoyed reading the paper. The detailed comments are as follows:\n\n1. It would be better if the authors could explicitly summarize the difference, and mainly, the technical challenges of the analyses for the decentralized average reward setting, compared to the discounted setting and the centralized setting, in the introduction of the paper. \n2. I wonder what is the difference of the Algorithm 2 in the paper from the Algorithm 2 in Zhang et al., 2018? In the Algorithm 2 therin, the \"global average reward\" $\\bar r$ needs to be estimated separately, in order to obtain the right TD error estimate. It seems a bit surprising to me that this paper can do it using only $r^i$. A detailed comparison and intuition would be necessary. \n3. In the statement of Theorem 3, how large is the eps^{critic}_{approx? Would the upper bound for stationarity be vacuous? Some discussions are necessary.\n4. It would be better if the simulation section could include more complicated and realistic settings. The current empirical contribution is a bit limited. \n5. Some typos: On the top of page 2: \"without join action\" should be \"without joint action\"; Assumption 5. “bdd” should be “bounded”.", "summary_of_the_paper": "This paper establishes the first finite-time convergence result of the actor-critic algorithm for fully decentralized multi-agent reinforcement learning (MARL) problems with average reward. It focuses on the practical setting where the rewards and actions of each agent are only known to itself, and the knowledge of joint actions of the agents is not assumed. The established finite-sample complexity matches that of the state-of-the-art single-agent actor-critic algorithms.", "summary_of_the_review": "The paper has made valid contribution to the area of multi-agent RL, and is well-written. As the empirical contribution is a bit limited, so I would view the main contribution to be theoretical. However, some detailed comparison with the most related works is needed, before justifying the novelty and significance of the theoretical contribution.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "UX7SRWZRPdT", "reviewer": "Reviewer_F2da", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Reasons to accept]\nThis paper makes some relatively non-trivial progress on top of (Zhang et al., 2018). In particular, while (Zhang et al., 2018) requires that each agent observes the joint actions of all agents, this paper only requires each agent to observe their own private action. In addition, this paper also derives the first non-asymptotic bound for fully decentralized MARL on average reward MDPs. Thirdly, some numerical experiments are also provided to show that the modifications in this paper actually lead to improvement over the algorithm in (Zhang et al., 2018). \n\n[Questions and concerns]\nHowever, there are also some issues in this paper regarding assumptions, literature comparisons and numerical experiments that the authors need to address. See below for the details.\n1. The comparison of the results with (Zhang et al., 2018) may not be sufficiently fair. In particular, the assumptions made in that paper seems to be different from the current paper (e.g., Assumption 7 seems not to be needed in (Zhang et al., 2018). I would suggest the authors to make it clearer in Section 3.2 which assumptions are different from (Zhang et al., 2018), why they are essential, and how they help obtaining the improved results (like the non-asymptotic results) in the current paper. On a related point, the clarity of Section 3.2 also needs some improvement. For example, Assumption 2 is implied by Assumption 1, and so should not be stated as a separate assumption. Also, the notation of consensus weight matrix, $A_{\\pi_{\\theta}}$ and advantage functions all use $A$, which might cause some confusion. \n2. The authors should also compare the results with the recent global optimality literature of actor-critic methods, such as [A,B]. Are there any essential challenges in obtaining global optimality bounds using the techniques introduced in papers such as [A,B]? Also, in [A], it is mentioned that from both theoretical and practical perspectives, bi-level actor-critic methods which first update the critic to sufficient accuracies as in the current paper are typically seldom adopted in practice. However, the numerical results in this paper seem to suggest that the bi-level/mini-batch updates might indeed be beneficial. Some more discussion and numerical experiments are needed to validate this (see the next point for more comments). \n3. I have some questions for the numerical experiments. The authors mentioned that constant step-sizes are key to the improvement over (Zhang et al., 2018). Then what if using the same constant step-sizes for the classical MARL algorithm in (Zhang et al., 2018)? And what about updating classical MARL in a mini-batch critic/bi-level manner as in this paper? I think providing these comparisons are important to understand what are essential in the modifications on top of the classical MARL algorithm. Otherwise, it gives me an impression that allowing for observing global actions is impeding the performance, which is counterintuitive. \n\nThere are also some minor suggestions, as detailed below:\n1. In Assumption 5, why is $\\Phi u \\neq 1$ for any $u$ reasonable? I understand that this is a classical assumption, but still some explanations would be helpful. \n2. Some more comments on what the quantity $A_{\\pi_{\\theta}}$ in (1) is would be helpful. \n3. On page 6, 2) The Actor Step, “where in our model” might better be “whereas in our model”. \n4. On page 7, what is “the weight information of other agents”?\n5. It would be helpful to refer to the x-axis in the plots as “number of samples” instead of “sample complexity”. And just to double check, does one sample mean tuple of $(s,a,r,s’)$?  \n\n[A] Fu, Zuyue, Zhuoran Yang, and Zhaoran Wang. \"Single-timescale actor-critic provably finds globally optimal policy.\" arXiv preprint arXiv:2008.00483 (2020).\n\n[B] Yang, Zhuoran, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. \"On the global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost.\" arXiv preprint arXiv:1907.06246 (2019).\n", "summary_of_the_paper": "This paper considers cooperative multi-agent reinforcement learning (MARL) for average reward MDPs with fully decentralized actor-critic methods. In particular, the authors make some progress on top of existing works in this direction, and in particular (Zhang et al., 2018). More precisely, the authors remove the assumption in (Zhang et al., 2018) that the joint actions are observable to all agents, and propose to modify the actor updates with mini-batch TD sharing to accommodate the scenario where each agent only observes its own action. The authors then establish a finite-sample bound for the proposed algorithm in terms of convergence to stationary points under linear value function approximation. Numerical experiments are also provided to showcase the benefits of the modifications over the algorithm in (Zhang et al., 2018). ", "summary_of_the_review": "The theoretical contribution of this paper on top of (Zhang et al., 2018) is good. However, there also are some issues in terms of the assumptions, comparisons with the global convergence of actor-critic methods literature and numerical experiments that need to be addressed. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PfdGn8XB_gj", "reviewer": "Reviewer_N673", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\nOnly local action is observed, which is an improvement from [Zheng et al 2018]. \nFinite-time convergence is provided which matches those bounds in single-agent AC. \n \nWeakness\n1. The time index is a bit confusing. In Algorithm 1 (TD subroutine), there is a $s_{k,\\tau}$ state sequence. In the outer loop, there is a $s_{t,\\tau}$ sequence. This is quite confusing: do these states in the subroutine and the main Algorithm 2 form a single trajectory, or these are multiple trajectories?\n2. In the TD subroutine, many TD errors are computed. Why can’t such TD errors be used to estimate the advantage function, as opposed to the approach in the paper (Line 1-10 in Algorithm 2) where many new TD errors are sampled? \n3. The benefit of Batch is not sufficiently discussed. For example, how does the batch algorithm compare with the “non-batch” algorithm, where one update is made after each sample?\n4. While $t_{gossip}$ scales with $1/\\epsilon$, each time a $B$-length vector is communicated, and $B$ also scales with $1/\\epsilon$. So the overall communication is somehow more than just $t_{gossip}$, and this should be discussed. \n5. This simulation scope seems too limited (in the standard of ICLR). \n", "summary_of_the_paper": "This paper studies a networked MARL problem based on the model in [Zhang et al 2018], where each agent can observe the global state, take local action and observe local rewards. The key difference in setting from [Zhang et al 2018] is that [Zhang et al 2018] assume the global action can be observed, but in this paper, only local action is known to each agent. To deal with this, an additional consensus loop is added to estimate the average TD error, which can be used to estimate the advantage function. Further, compared to [Zhang et al 2018], a finite time error bound is provided. \n", "summary_of_the_review": "Overall this is an interesting generalization from [Zhang et al 2018], but I feel many points are worth more elaboration and discussion. More simulation is needed. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Bi_gZr3O-EG", "reviewer": "Reviewer_AYYd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The paper is in general well written and well motivated. The ideas are clearly explained and presented in an organized way. \n- The log(N^5/\\epsilon) term in the complexity appears odd. It seems that that log(N/\\epsilon) is enough. \n- The assumption on observable global-state and unobservable global action should be better justified. It would be helpful to provide an example for it.. \n- Assumption 1 needs more explanation. It seems to assume that the optimal policy will always utilize all actions with non-zero probability? Usually it is more common that a deterministic policy exists for many problems. Please elaborate. \n- There is a typo in Assumption 5. “bdd” should be “bounded”. \n- The last sentence in Assumption 5 should be better explained. What does the condition imply?\n - Theorem 2 seems to indicate that a smaller beta gives a better result? Can the authors provide some intuition? \n- The paper claims that the current work is still an improvement of Zhang et al 2018. Can this be made more specified? \n- In the experimental section, the reviewer wonders whether schemes from the discounted case with gamma->1 can be compared here? Intuitively, they should also give reasonable performance. \n- Any intuition for the fact that the empirical sample complexity does not scale with N? Could this be because of the special topology used? \n- It might be helpful to strengthen the experimental section. The current setup is a bit limited.", "summary_of_the_paper": "The paper studies the finite-time convergence and sample complexity of MARL with average reward, focusing on actor-critic algorithm. It proposes a mini-batch Markovian sampled algorithm and obtain its sample complexity. \n", "summary_of_the_review": "The paper is well written and the topic is timely and of interest. Some assumptions/statements require more elaboration and the experiments should be strengthened. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AFHdxXwsjrF", "reviewer": "Reviewer_v83u", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well written and easy to follow in general. Its theoretical contribution on the first finite time convergence result (to the stationary point) for fully decentralized MARL in the average reward setting is important. However, I have some comments and questions for the authors, which are listed below.\n1. Why is the work (Chen et al., 2021) independent of the number of agents? Is it because of the difference between discounted setting and the average reward setting?\n2. Assumption 2 should be a lemma or a proposition under Assumption 1. Also, I think Assumption 7 should be able to be replaced with some more explicit conditions (see for example Lemma 10 in [1]). Also it would be better if the authors can comment on how essential this assumption is as it is not needed in (Zhang et al., 2018).\n3. Please better highlight the differences from (Zhang et al., 2018) in Algorithm 2, and which parts are improvements that lead to better theoretical guarantees and numerical results and which parts are sacrifices to allow for private (instead of joint) actions observability. In particular, in Section 4, the explanation on the modification of the actor step to allow for private action observations is unclear. It's a bit hard to follow what's the relationship among the global, networked and local TD errors and what are changed compared to the TD error computation in (Zhang et al., 2018). It would also be helpful to comment more which changes are to allow for the more challenging private action observation assumption, and which changes (also) contribute to some theoretical and numerical improvements (as suggested in the subsequent sections). \n4. At the end of Section 5, it seems that the comment on the $O(\\epsilon^{-1})$ sampling does not necessarily indicate that (Zhang et al., 2018)'s overall communication complexity is empirically worse (with appropriate hyper-parameter choices, such as step-sizes and mini-batches). In fact, synchronous actor and critic updates (instead of first updating the critic for many steps and then updating the actor) is more frequently adopted in practice. \n5. It looks a bit weird to me why observing the joint actions does not seem to have any benefits according to the numerical experiments. If I understand correctly, in addition to addressing the private action observation challenge, this paper also considers mini-batch updates and constant step-sizes modifications. These can also be easily applied to the classical MARL algorithm in (Zhang et al., 2018). For a fair empirical comparison, I think it's important to provide some comparisons with the mini-batch constant step-size version of the baseline classical MARL algorithm. \n\nReferences:\n[1] X. Guo, A. Hu and J. Zhang. Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methods.", "summary_of_the_paper": "This paper studies the cooperative average reward fully decentralized multi-agent reinforcement learning (MARL) problems, where the agents interact with their neighbors over a communication network. It proposes a consensus-based actor-critic algorithm and shows its convergence to the stationary point. The convergence rate and sample complexity of this algorithm are provided and comparison with existing algorithm is shown in the numerical experiments. ", "summary_of_the_review": "This paper proposes a new actor-critic algorithm to deal with a cooperative average reward fully decentralized MARL and provides the first finite time convergence result. The theoretical results are important. However, the differences with existing literature are not well explained and numerical experiments need some improvements.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides actor-critic method for fully decentralized MARL. The results remove some of the restrictions from existing results and have also obtained a sample bound that matches with the bound in single agent RL. The authors also give detailed responses to the reviewers' concerns. The overall opinions from the reviewers are positive.
Decision: Accept (Spotlight)