review_iclr_bench/iclr_parsed/04pGUg0-pdZ.txt

# FINITE-TIME CONVERGENCE AND SAMPLE COM## PLEXITY OF MULTI-AGENT ACTOR-CRITIC REIN- FORCEMENT LEARNING WITH AVERAGE REWARD


Hairi and Jia Liu
Department of Electrical and Computer Engineering
The Ohio State University
Columbus, OH 43210, USA
hairi.1@osu.edu, liu@ece.osu.edu

ABSTRACT


Songtao Lu
IBM Research AI
IBM Thomas J. Watson Research Center
Yorktown Heights, NY 10598
songtao@ibm.com


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 O(N [2]/ǫ[2] log(N/ǫ)). Interestingly, this
sample complexity bound matches that of the state-of-the-art single-agent actorcritic algorithms for reinforcement learning.

1 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 systems (Riedmiller et al., 2000), autonomous driving (Yu et al., 2019; Shalev-Shwartz et al., 2016)
and strategic games (Silver et al., 2018; Foerster et al., 2018), to name just a few. Although empirical 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.,
(Zhang et al., 2021a) 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) is 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 al., 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 on the discounted
total reward setting, where a hyperparameter γ ∈ (0, 1) 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 communication networks with MARL, the typical and natural performance metrics are long-term average
throughput or latency in the steady-state.
The lack of a fundamental understanding on how to develop efficient cooperative MARL algorithms
that consider the above two aspects in terms of information structure, scalability, and communication


-----

and sample complexities motivates us to fill this gap by developing a fully decentralized cooperative
MARL algorithm in the average reward setting, without assuming joint action knowledge.

2) Technical Challenges: Developing a 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 reinforcement 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 a satisfying performance, which implies that low sample and communication
complexities are even more challenging and critical for MARL 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 actorcritic algorithm for MARL. Our key results in this paper are summarized as follows:

-  We propose a 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 ǫ neighborhood of the stationary, we require O(ǫ[−][1] log(ǫ[−][1])) rounds of communication while only needing
O(ǫ[−][2] log(ǫ[−][1])) samples. By contrast, the state-of-the-art MARL requires a 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 in the MARL average reward problem setting without joint action information. Our obtained complexity is O(ǫ[−][2] log(ǫ[−][1])), 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 a quick overview on the closely related work on MARL algorithms and
their theoretical results, along with several notable related counterparts in single-agent RL.

1) MARL Theoretical Analysis and Algorithm Design: For recent advances in MARL algorithms
and their theoretical results, Zhang et al. (2021a) provided a comprehensive survey. Also, Lee et al.
(2020) highlighted the evolution from single-agent to multi-agent RL from a 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 al. (2019) and proposed various variance reduction of policy evaluation in decentralized MARL algorithms Zhang et al. (2021b).
Doan et al. (2019) used i.i.d. sampling and has shown the sample complexity of O[˜](ǫ[−][1]) 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, Foerster 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 et al. (2018) established asymptotic convergence results for fully decentralized MARL actor-critic algorithms. Concurrent with
our work, Chen et al. (2021) has recently studied the mini-batch Markovian sampling actor-critic
algorithm for a class of discounted reward MARL problems, where the finite-time convergence result is obtained. They have applied batch sampling for both actor and critic steps and achieved a
sample complexity of O(ǫ[−][2] log(ǫ[−][1])), which is the same as ours. We note that, together with our
work, these are the first finite-time convergence results for MARL. However, there are several key
differences between our work and (Chen et al., 2021). First, we focus on the average reward problem, while Chen et al. (2021) studied the discounted reward setting. Second, in (Chen et al., 2021),
agents share a noisy version of the rewards with the neighbors, which requires a 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.


-----

Table 1: Comparison of sample complexity of single-agent (SA) and multi-agent (MA) AC algorithms and TD(0) algorithms at Average Reward (AR) and Discounted Reward (DR) settings.

|Paper|Problem|Sampling|Col4|Sample Complexity|
|---|---|---|---|---|
|||actor step|critic step||
|Qiu et al. (2021)|SAAR|i.i.d.|Markovian|O(ǫ−3 log2(ǫ−1))|
|Xu et al. (2020)|SADR|Markovian|Markovian|O(ǫ−2 log(ǫ−1))|
|Zhang et al. (2018)|MAAR|Markovian|Markovian|Asymptotic|
|Doan et al. (2019)|MADR|N/A|i.i.d|O˜(ǫ−1)|
|Chen et al. (2021)|MADR|Markovian|Markovian|O(ǫ−2 log(ǫ−1))|
|This paper|MAAR|Markovian|Markovian|O(N 2/ǫ2 log(N/ǫ))|



2) Related Literature in Single-Agent RL: We note that single-agent RL can be viewed as a
centralized approach, where a 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 TD(λ) algorithm with function approximations in the policy
evaluation problem. Also, Tsitsiklis & 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, Qiu et al. (2021) analyzed the sample complexity for an actorcritic 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
O(ǫ[−][3] log[2](ǫ[−][1])). By applying mini-batch sampling update, we are able to improve the sample
complexity by a factor of O(ǫ[−][1]). Another closely related work on single-agent RL is (Xu et al.,
2020), where the authors studied the discounted reward problem. They used batch sampling for both
actor and critic steps in their actor-critic algorithm and developed a 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-art sample complexity of O(ǫ[−][2] log(ǫ[−][1])) for singleagent 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 al., 2020) and linear
quadratic regulator in (Yang et al., 2019). 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.

To conclude this section, we summarize the aforementioned related actor-critic and TD algorithms
and their sample complexity results in Table 1.

3 MULTI-AGENT REINFORCEMENT LEARNING WITH AVERAGE REWARD

3.1 SYSTEM MODEL

Consider a multi-agent system with N agents, denoted by N = {1, · · ·, N }, operating in a networked environment. Let E be the edge set for a given network G = (N, E). To formulate our
MARL problem and facilitate our subsequent discussions, we first define the notion of networked
multi-agent MDP as follows.
Definition 1 (Networked Multi-Agent MDP). Let G = (N, E) be a communication network that connects N agents. A networked multi-agent MDP is defined by following tuple
(S, {A[i]}i∈N, P, {R[i]}i∈N, G), where S is the global state space observed by all agents, A[i] is the
action set for agent i, and P : S ×A×S → [0, 1] is a global state transition function, and R[i] : S ×A
is the local reward function for agent i. Let A = i∈N [A][i][ 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[i] are finite. As

[Q]

a result, the joint action space A is also finite for finite N . We also note that at time t ≥ 0, all
agents can observe the current global state st. However, agent i can only observe its own action
a[i]t [∈A][i][, which is the key difference between our model and that in (Zhang et al., 2018), where it is]
assumed that the joint actions are observable to all agents. Moreover, each agent can only observe
its own reward rt[i][, i.e., agents do not observe or share rewards with other agents at time][ t][. The]


-----

reward function R[i](s, a) is an expectation given s and a, and the instantaneous reward is denoted
by r[i](s, a), i.e., R[i](s, a) = E[r[i](s, a)].

We consider policies that are stationary. In our MARL system, each agent chooses its action following its local policy π[i] that is conditioned on the current global state s, i.e., π[i](a[i]|s) is the probability
for agent i to choose an action a[i] ∈A[i]. Then, the joint policy π : S × A → [0, 1] can be written as
π(a|s) = i∈N [π][i][(][a][i][|][s][)][.]

Moreover, the policies at the agents are parameterized. Specifically, each agent i’s local policy can
be written as[Q] πθ[i] [i][, where][ θ][i][ ∈] [R][m][i][ denotes the parameter. We let][ θ][ ≜] [[(][θ][1][)][T][,][ · · ·][,][ (][θ][N] [)][T][ ]][T][ ∈]
N
RPi=1 [m][i] . Then, we can write the joint policy as follows: πθ(a|s) = i∈N [π][θ][i] [(][a][i][|][s][)][.]

3.2 TECHNICAL ASSUMPTIONS [Q]

We now state the following assumptions on the positivity and continuity of πθ[i] [i] [(][a][i][|][s][)][, which guar-]
antee the stationary distribution of {st} under any given policy.
Assumption 1. For any i ∈N, s ∈S, a[i] ∈A[i] and θ[i] ∈ R[m][i], the policy function πθ[i] [i][(][a][i][|][s][)][ ≥] [0][.]
Also, πθ[i] [i][(][s, a][)][ is a continuously differentiable with respect to the parameter][ θ][i][. In addition, for]
any θ, we assume the induced Markov chain {st}t≥0 is irreducible and aperiodic, and its transition
matrix P [θ] is P [θ](s[′]|s) = a∈A [π][θ][(][a][|][s][)][ ·][ P] [(][s][′][|][s, a][)][,] ∀s, s[′] ∈S.

Assumption 1 guarantees that the states have a stationary distribution dθ(s) over S given any policy

[P]

πθ. As a result, the Markov chain of state action pair {(st, at)} also has a stationary distribution
dθ(s) · πθ(a|s).
Assumption 2. The instantaneous reward rt[i] [is uniformly bounded by a constant][ r][max] [>][ 0][ for any]
i ∈N and t ≥ 0.

Assumption 2 is common in the literature (see, e.g., (Zhang et al., 2018; Xu et al., 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 a positive constant η > 0 such that A ∈ R[N] [×][N] is doubly stochastic and Aii ≥ η, ∀i ∈N .
Moreover, Aij ≥ η if i, j are connected, otherwise Aij = 0 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 =
1

deg(G) [(][deg][(][G][)][ ·][ I][ −] [L][)][,][ where deg][(][G][)][ is the degree of the graph][ G][ (i.e. the maximal vertex de-]
gree), I is the identity matrix of conforming dimensionality, and L is the Laplacian matrix of the
graph. It is easy to verify that this matrix is symmetric, doubly stochastic and η ≥ deg1(G) [≥] N[1] [.]

Assumption 4. Each agent i’s value function is parameterized by the class of linear functions, i.e.,
Vθ(s; w) = φ(s)[T] w where φ(s) ≜ [φ1(s), · · ·, φK (s)][T] ∈ R[K] is the feature associated with the
state s ∈S and K < |S|. The feature vectors φ(s) are uniformly bounded for any s ∈S. Without
loss of generality, we assume that ∥φ(s)∥≤ 1. Furthermore, the feature matrix Φ ∈ R[|S|×][K] has
full column rank. Also, for any u ∈ R[K], Φu ̸= 1, where 1 is an all-one vector.

This assumption on features is standard and has been widely adopted in the literature, e.g.,
(Tsitsiklis & Van Roy, 1999; Zhang et al., 2018; Qiu et al., 2021). This assumption implies the following property: for any policy πθ, the inequality w[T] Aπθ w < 0 holds for any w ̸= 0, where Aπθ is
defined as

Aπθ := Es∼dθ(s),s′∼P (·|s)[(φ(s[′]) − φ(s))φ[T] (s)]. (1)

This property further implies that for all θ, Aπθ is invertible and λmax(Aπθ + A[T]πθ [)][ <][ 0][ (Qiu et al.,]
2021), where λmax(·) is the largest eigenvalues of the matrix.
Assumption 5. There exists a constant λA > 0 such that λmax(Aπθ + A[T]πθ [)][ ≤−][λ][A] [holds for all]
θ ∈ RPi∈N [m][i] .

Assumption 5 ensures the optimal approximation wθ[∗] [for any given policy][ π][θ][ is uniformly bounded]
(see discussion before Theorem 2 and Lemma 4).


-----

Assumption 6. Let ψθ(s, a) = ∇θ log πθ(a|s) be the score function for any state-action pair (s, a).
For any two policy parameters θ, θ[′] ∈ RPi∈N [m][i], and any state-action pair (s, a) ∈S×A, there exist
positive constants such that the following hold: 1): ∥ψθ(s, a)∥≤ Cψ; 2): ∥∇θJ(θ) −∇θJ(θ[′])∥≤
LJ ∥θ − θ[′]∥; where J(θ) is defined in (2) and ∥· ∥ denotes the ℓ2-norm.

Assumption 6 says that the score function is uniformly bounded for any policy and the gradient of
the objective function has a 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., 2021).
We note that for the discounted reward problem, this gradient Lipschitz property can be guaranteed
through (Xu et al., 2020, Assumption 2). We note that Assumption 6 can be satisfied by the class of
soft-max policy under the Assumption 1, as in (Guo et al., 2021).

3.3 THE OBJECTIVE FUNCTION

The goal of the agents is to find a joint policy πθ to maximize the global average long-term reward.
Mathematically, this can be written as:


T −1

t=0

X


πθ(a|s) · R[¯](s, a), (2)
a∈A

X


rt[i]+1
i∈N

X


maximizeθ J(θ) = lim
T →∞


T [E]


dθ(s)
s∈S

X


where R[¯](s, a) = N1 i∈N [R][i][(][s, a][)][ is the global average reward function. Let][ ¯]rt = N1 i∈N [r]t[i][,]

then we have R[¯](s, a) = E[¯rt+1|st = s, at = a]. Next, we define the state-action value

P P

function: Qθ(s, a) = E[[P][∞]t=0 r[¯]t+1 − J(θ)|s0 = s, a0 = a, πθ], and the state value function
Vθ(s) = a∈A [Q][θ][(][s, a][)][ ·][ π][θ][(][a][|][s][)][.][ The advantage function is defined as follows:]

Advθ(s, a) = Qθ(s, a) − Vθ(s). (3)

[P]

3.4 POLICY GRADIENT THEOREM

The gradient of a policy πθ for decentralized policy gradient is stated in the following theorem.
Theorem 1 (Policy Gradient Theorem for MARL (Zhang et al., 2018)). For any θ, let πθ : S ×A →

[0, 1] be a policy and let J(θ) be the global average long-term average return defined in (2). Then,
the gradient of J(θ) with respect to parameter θ[i] can be computed as:

∇θi J(θ) = Es∼dθ,a∼πθ [∇θi log πθ[i] [i] [(][a][i][|][s][)][ ·][ Adv][θ][(][s, a][)]][.] (4)

4 A CONSENSUS-BASED ACTOR-CRITIC ALGORITHM

In this section, we propose a 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 πθt at
time t. After the critic step, the algorithm enters the actor step, which improves the policy parameter
θt according to the direction from policy gradient as shown in Theorem 1. 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[i] ∈ R[K] to approximate the global value functions Vθ(s; w[i]) for each state s ∈S.
For linear approximation, we have Vθ(s; w[i]) = φ(s)[T] w[i], where φ(s) ∈ R[K] denotes the feature for
state s. As a result, the gradient of value function at state s with respect to approximation parameter
w[i] is φ(s), i.e. ∇wVθ(s; w[i]) = φ(s).

1) The Critic Step: The critic step is achieved through its own oracle, which is summarized in
Algorithm 1. 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 ∈N, the parameter is locally updated by following rules:

µ[i]k,τ +1 [= (1][ −] [β][)][µ]k,τ[i] [+][ βr]k,τ[i] +1 (5)

δk,τ[i] [=][ r]k,τ[i] +1 [−] [µ]k,τ[i] [+][ φ][T][ (][s][k,τ] [+1][)][w]k[i] [−] [φ][T][ (][s][k,τ] [)][w]k[i] (6)


-----

Algorithm 1: Mini-batch TD learning for Critic

Input : s0, πθt, φ, step-size β, critic step iteration number K, critic batch size M, the
communication network A

1 for k = 0, · · ·, Kc − 1 do

2 sk,0 = sk−1,M ( when k = 0, sk,0 = s0);

3 for all i ∈N do

4 for τ = 0, · · ·, M − 1 do

5 Execute action a[i]k,τ [∼] [π]θ[i] t[i] [(][·|][s][k,τ] [)][;]

6 Observe the state sk,τ +1 and reward rk,τ[i] +1[;]

7 Update µ[i]k,τ +1 [←] [(1][ −] [β][)][ ·][ µ]k,τ[i] [+][ β][ ·][ r]k,τ[i] +1[;]

8 Update δk,τ[i] [←] [r]k,τ[i] +1 [−] [µ]k,τ[i] [+][ φ][T][ (][s][k,τ] [+1][)][w]k[i] [−] [φ][T][ (][s][k,τ] [)][w]k[i] [;]

9 end


M −1

10 Critic Step: ˜wk[i] [←] [w]k[i] [+][ β]M τ =0 [δ]k,τ[i] [·][ φ][(][s][k,τ] [)][;]

11 Consensus Update wk[i] +1 [←] P[P]j∈Ni [A][(][i, j][)][ ·][ ˜]wk[j] [;]

12 end

13 end
Output: sKc−1,M, wKc


M −1

δk,τ[i] [·][ φ][(][s][k,τ] [)][,] (7)
τ =0

X


w˜k[i] [=][ w]k[i] [+][ β]

M


where β > 0 is the step-size of the critic step, µ[i]k,τ [is the estimate of the long-term return of]
agent i, and δk,τ[i] [is the local TD-error for agent][ i][ at iteration][ k][ using sample][ τ] [. Here, in each]
iteration k in the critic step, the approximation parameter is locally updated through a batch of
sampling as in (7), where the batch size is M . Then, agent i will further update the approximation
parameter w[i] through a weighted average of its local and neighboring agents’ parameters as follows:
wk[i] +1 [=][ P]j∈Ni [A][(][i, j][) ˜]wk[i] [.][ This batched sampling update continues for][ K][c][ iterations for each given]
policy πθt.

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 (3), the joint action a also has to be known to compute
the advantage function, whereas in our model, each agent can only observe its own action. As a
result, an estimation of the advantage function is required. Here, we show that the global TD-error
is an unbiased estimate of the advantage function.

At time t, suppose we have samples st, at, st+1 and the rewards {rt[i]+1[}][i][∈N] [then the advantage]
function is as follows: Advθ(st, at) = E[¯rt+1 − J(θ) + Vθ(St+1) − Vθ(st)|st, at], and the global
TD-error can be computed as follows: δt = ¯rt+1 − µt + Vθ(st+1) − Vθ(st), where µt+1 = (1 −
α) · µt + α · ¯rt+1 is the estimate for the average long term return, and α is the step-size for the actor
step. Hence, we have that the expected global TD-error is the advantage function, i.e., E[δt|st, at] =
Aθ(st, at). 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 as δt[i] [=][ r]t[i]+1 [−] [µ]t[i] [+][ V][θ][(][s][t][+1][)][ −] [V][θ][(][s][t][)][, where]
µ[i]t+1 [= (1][ −] [α][)][µ]t[i] [+][ αr]t[i]+1[. We also note that][ µ][t] [=][ 1]N i∈N [µ]t[i] [.]

Thus, once each agent knows the global TD-error, the policy parameter can be updated according toP
the policy gradient rule in (4). However, without any communication, each agent only has the knowledge of its own local TD-error. Moreover, we will show that the networked TD-error is actually the
average of the local TD-errors. Specifically,


δt = ¯rt+1 − µt + Vθ(st+1) − Vθ(st) = [1]


rt[i]+1 [−] [1]

N

i∈N

X


µ[i]t [+][ V][θ][(][s][t][+1][)][ −] [V][θ][(][s][t][)]
i∈N

X


= [1]



[rt[i]+1 [−] [µ]t[i] [+][ V][θ][(][s][t][+1][)][ −] [V][θ][(][s][t][)] = 1]

N

i∈N

X


δt[i][.]
i∈N

X


-----

Algorithm 2: Minibatch-TD sharing for Actor Critic Algorithm

Input : state feature matrix Φ, actor step-size α, Initial parameters θi for all i ∈N

1 for t = 0, · · ·, T − 1 do

2 critic update: wt, st,0 = Minibatch-TD-critic in Algorithm 1;

3 for l = 0, · · ·, B − 1 do

4 for all i ∈N do

5 Execute action a[i]t,l [∼] [π]θ[i] t[i] [(][·|][s][t,l][)][;]

6 Observe the state st,l+1 and reward rt,l[i] +1[;]

7 Update µ[i]t,l+1 [←] [(1][ −] [α][)][ ·][ µ]t,l[i] [+][ α][ ·][ r]t,l[i] +1[;]

8 Update δt,l[i] [←] [r]t,l[i] +1 [−] [µ]t,l[i] [+][ φ][T][ (][s][t,l][+1][)][w]t[i] [−] [φ][T][ (][s][t,l][)][w]t[i][;]

9 Update ψt,l[i] [←∇][θ][i][ log][ π]θ[i] t[i][(][s][t,l][, a]t,l[i] [)][;]

10 end

11 end

δt,[1] 0 -  · · δt,[N]0
. .

12 Let ∆0 =  .. ... .. ;

δt,B[1] −1 -  · · δt,B[N] −1

 

13 for i ∈N do 

14 for k = 0 : tgossip − 1 do

15 ∆k+1(:, i) ← [P]j∈Ni [A][(][i, j][)][ ·][ ∆][k][(:][, j][)][;]

16 end

17 end


18 for all i ∈N do

19 Let δ[˜]t,[i] 1:B−1 [= ∆][t]gossip [(:][, i][)][ ;]

B−1

20 Actor Step: θt[i]+1 [←] [θ]t[i] [+][ α]B l=0 δ[˜]t,l[i] [·][ ψ]t,l[i] [;]

21 end

P

22 end
Output: θ ˆT [with][ ˆ]T chosen uniformly from {1, · · ·, T }


For any time t, the average of the local TD-errors is an unbiased estimate of the advantage function.
Therefore, we just need to let each agent communicate with its neighbors so that an average of all
local TD-errors can be reached or estimated for all agents.

From the results in (Nedic & Ozdaglar, 2009), we have limτ →∞ A[τ] (x[1], · · ·, x[N] )[T] =
1

N i∈N [x][i][1][. However, this convergence is asymptotic, meaning that the exact estimation can]
only be achieved with infinite iterations (i.e., τ →∞). In practice, since one can only apply fiP
nite iterations, we use δ[˜]t[i] [to denote the estimate of the global TD-error maintained by agent][ i][ after]
tgossip iterations of updates at time t, i.e., δ[˜]t[i] [= [][A][t][gossip] []][i][∆]t[0][, where][ ∆][0]t [= (][δ]t[1][,][ · · ·][, δ]t[N] [)][T][ is 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 local TD-errors with its neighbors for tgossip 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 t ∈{0 · · ·, T − 1}, only tgossip rounds of communication for every B
samples are needed.

Combined with a B-batched Markovian sampling, the parameter θ[i] update for agent i ∈N can be
written as follows: θt[i]+1 [=][ θ]t[i] [+][ α]B Bl=0−1 δ[˜]t,l[i] [·][ ψ]t,l[i] [where][ α][ is the step-size for the actor step and]

ψt,l[i] [=][ ∇][θ][i][ log][ π]θ[i] t[i][(][s][t,l][, a]t,l[i] [)][ is the local score function for agent]P [ i][ using][ l][-th sample at time][ t][. The]
actor step of our algorithm is illustrated in Algorithm 2.


-----

5 THEORETICAL CONVERGENCE ANALYSIS

In this section, we present the convergence results for both the critic and actor steps in Theorems 2
and 3, respectively. Due to space limitation, we relegate the proofs to the supplementary material.

5.1 CONVERGENCE ANALYSIS FOR CRITIC (ALGORITHM 1)

For a given policy πθ, we define bπθ = Es∼dθ,a∼πθ [φ(s)(¯r(s, a) − J(θ))], where ¯r(s, a) =
1

N i∈N [r][i][(][s, a][)][ and][ J][(][θ][)][ are as defined in (2). For all agents, the optimal solution (Wu et al.,]

2020), (Qiu et al., 2021) of this critic learning is wθ[∗] [=][ −][A]π[−]θ[1][b][π]θ [, where][ A][π]θ [is defined as in (1).]

P

The invertiblity of Aπθ is due to the Assumptions 1 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 1-5
hold. For any given policy πθ, consider the iteration generated by Algorithm 1. Recall the definition
of λA in the Assumption 5 and let β < min{ 2(1η−[N]η[−][N][1][−][1]) [,][ λ]128[A] [,] λ4A [}][. It then follows that:]

N

E[ ||wK[i] c [−] [w]θ[∗][||][2][]][ ≤] [κ][′]1[N][ 4][γ][2][K][c][ +][ κ][′′]2 [N][ 6][β][2][ +][ κ][3][N][ 5][γ][K][c] [β]

i=1

X


+ 2N (1 − [λ][A] w0 − wθ[∗][||][2]2 [+][ κ][4] (8)

8 [β][)][K][c] [||][ ¯] M [N,]

where γ := (1−η[N] [−][1])·(1+2β) < 1 and κ[′]1[, κ]2[′′][, κ][3][, κ][4] [are positive constants. If we further let][ K][c] [≥]

12 [max][{][log][γ][−][1][ 6][κ]1[′]ǫ[N][ 4], log(1− λA8 [β][)][−][1] 12N || ¯w0ǫ−wθ[∗][||][2]2 }, β ≤ min{ N[1][3] 6κǫ[′′]2 [,] 2(1η−[N]η[−][N][1][−][1]) [,][ λ]128[A] [,] λ4A [}]

6κ4N
and M ≥ ǫ, then we have E[[P][N]i=1 [||][w]K[i] c [−] [w]θ[∗][||][2][]][ ≤] [ǫ][ for all]q[ i][ ∈N][ with total sample]

complexity given by KcM = O( [N]ǫ [log(][ N]ǫ [))][.]

Theorem 2 establishes a convergence result for the policy evaluation of a given policy πθ. We can
see that our constant step-size batch-sampled critic process can achieve the same complexity of
O˜(ǫ[−][1]) order-wise as the TD(0) learning in Doan et al. (2019), where diminishing step-sizes were
used. On the other hand, in the single agent average reward setting of Qiu et al. (2021), there exists
a non-vanishing error term in their critic convergence. In contrast, with proper choices of iteration
number Kc and batch size M, our mean-square error can be arbitrarily small.

5.2 CONVERGENCE ANALYSIS FOR ACTOR-CRITIC ALGORITHM (ALGORITHM 2)

Define the approximation error introduced by using linear approximation in the critic step, ξapprox[critic] [=]
maxθ∈RPi∈N [mi][ E][s][∼][d][θ] [[][|][V][π][θ] [(][s][)][ −] [V][w]πθ[∗] [(][s][)][|][2][]][. For a given policy][ π][θ][, 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 approximations are adopted (Qiu et al., 2021; Xu et al., 2020). Let Rw, defined in Lemma 4, be an upper
bound on ||wθ|| for all policy parameter θ.
Theorem 3 (Overall Convergence Rate and Sample Complexity). Suppose that Assumption 1-6
hold. Consider the actor-critic algorithm in Algorithm 2. Let step-size α = 4L1J [. It then holds that:]


T N
t=1 i=1 [||][w]t[i] [−] [w]θ[∗]t [||][2]

E[||∇θJ(θ ˜T [)][||][2][]][ ≤] [16][L][J] [r][max] + 72N + 18κ3N [3](1 − η[N] [−][1])[2][t][gossip]

T T

P P

+ 72ξapprox[critic] [+ 288(][r][max][ +][ R][w][)][2][[1 + (2][κ][ −] [1)][ρ][]] N, (9)

B(1 − ρ)


, B ≥ 576 [(][r][max][+2][R][w](1[)]−[2][[1+(2]ρ) [κ][−][1)][ρ][]]


where κ3 is a positive constant. Furthermore, let T ≥ [64][L][J]ǫ[r][max]


and the communication round among the agents tgossip ≥ [1]2 [log][(1][−][η][N] [−][1][)][−][1][ 64][κ]ǫ[3][N][ 3] . Suppose for the

same setting as in Theorem 1 holds so that E[[P][N]i=1 [||][w]K[i] c [−] [w]θ[∗][||][2][]][ ≤] 288ǫ N [for all][ 0][ ≤] [t][ ≤]

T, then we have E[||∇θJ(θt)||[2]] ≤ ǫ + O(ξapprox[critic] [)][,][ with a total complexity of][ (][B][ +][ MK][c][)][T][ =]

O( [N]ǫ[2][ 2][ log(][ N]ǫ [))][. And the communication complexity is][ (][K][c][ +][ t][gossip][)][T][ =][ O][(][ 1]ǫ [log(][ N]ǫ [))][.]


-----

(a) System size N = 6. (b) System size N = 10. (c) System size N = 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(ǫ[−][2] log(ǫ[−][1])) matches the state-of-the-art single-agent actor-critic RL by
Xu et al. (2020) and the discounted MARL by Chen et al. (2021).

We note that the overall communication complexity also matches that of (Chen et al., 2021) in the
discounted reward setting. However, our work is still an improvement compared to the classical
MARL in Zhang et al. (2018) for the average reward setting. Specifically, Zhang et al. (2018) needed
a communication round after each sampling. By contrast, in this paper, we only need a communication round per O(ǫ[−][1]) 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 is measured by the number of communication rounds rather
than the size of bits transmitted over the network. We follow the standard definition of communication complexity in the literature, which is widely adopted in the literature, see (Chen et al., 2018)
(Zhang et al., 2019). However, we note that tgossip, actor step batch size B and critic iteration rounds
Kc, scale with O(log 1/ǫ), O(1/ǫ) and O(log 1/ǫ) respectively as indicated in the Theorem 3 and
2. The amount of information (in terms of bits) is (KcNK + BNtgossip)T = O( ǫ[N][2][ log][ N]ǫ [)][.]

6 EXPERIMENTAL RESULTS

In this section, we conduct experiments to compare our proposed consensus-based TD-sharing
MARL algorithm with the most related MARL algorithm 1 in Zhang et al. (2018) that also studied average reward. To our knowledge, this is the only work that is directly comparable to ours. The
key difference is that the knowledge of joint action is assumed in Zhang et al. (2018), but not in our
work. We vary the system size from N = 6, 10 to 15. The blue curve is our TD-sharing algorithm
and the red curve is classical MARL algorithm in Zhang et al. (2018). The curves represent the
average results of 10 trials and the 95% confidence intervals are also plotted. For the details, see A.1
in Appendix. The results in Figure 1 show that for different system sizes, both algorithms converge
to a reasonable objective value. Note that if we use uniformly random policy as the baseline policy,
then the objective values will be around 2 due to the setting of our experiments. All simulation
results are above this threshold and our TD-sharing algorithm converge to a better objective value.
See Section A.2 for addition experiment results.

7 CONCLUSION AND DISCUSSION

In this paper, we studied fully decentralized MARL in average reward setting and proposed a
batch-sampled actor-critic algorithm. Our main contribution is to establish the first finite time convergence result for fully decentralized MARL in average reward setting, where the complexity is
O(ǫ[−][2] log(ǫ[−][1])), which matches that of the state-of-the-art single agent RL. The algorithm reaches
such convergence with a 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 a more scalable algorithm in terms of system size.


-----

ACKNOWLEDGMENTS

Hairi and Jia Liu’s work has been supported in part by NSF grants CAREER CNS-2110259, CNS2112471, 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-efficient distributed learning. arXiv preprint arXiv:1805.09965, 2018.

Ziyi Chen, Yi Zhou, Rongrong Chen, and Shaofeng Zou. Sample and communication-efficient
decentralized actor-critic algorithms with finite-time analysis. arXiv preprint arXiv:2109.03699,
2021.

Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed td (0) with linear
function approximation on multi-agent reinforcement learning. In International Conference on
Machine Learning, pp. 1626–1635. PMLR, 2019.

Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson.
Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on 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.00483, 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 arXiv: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 reinforcement 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 Mathematical Soc., 2017.

Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61, 2009.

Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On finite-time convergence of actorcritic algorithm. IEEE 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 on Balancing Reactivity
and Social Deliberation in Multi-Agent Systems, pp. 137–149. Springer, 2000.

Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement
learning for autonomous driving. arXiv preprint arXiv:1610.03295, 2016.

David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez,
Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement
learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140–
1144, 2018.

John N Tsitsiklis and Benjamin Van Roy. Average cost temporal-difference learning. Automatica,
35(11):1799–1808, 1999.

John N Tsitsiklis and Benjamin Van Roy. On average versus discounted reward temporal-difference
learning. Machine Learning, 49(2):179–191, 2002.


-----

Yue Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite time analysis of two time-scale actor
critic methods. arXiv preprint arXiv:2005.01350, 2020.

Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural)
actor-critic algorithms. arXiv preprint arXiv:2004.12956, 2020.

Zhuoran Yang, 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.

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 highways based on dynamic coordination graphs. IEEE Transactions on Intelligent Transportation
Systems, 21(2):735–748, 2019.

Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multiagent reinforcement learning with networked agents. In International Conference on Machine
Learning, pp. 5872–5881. PMLR, 2018.

Kaiqing Zhang, Zhuoran Yang, and Tamer Bas¸ar. Multi-agent reinforcement learning: A selective
overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp.
321–384, 2021a.

Xin Zhang, Jia Liu, Zhengyuan Zhu, and Elizabeth S Bentley. Compressed distributed gradient
descent: Communication-efficient consensus over networks. In IEEE INFOCOM 2019-IEEE
Conference on Computer Communications, pp. 2431–2439. 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. In Advances Neural Information Processing Systems (NeurIPS), Virtual Event, December 2021b.

A APPENDIX

In this section, we provide lemmas that lead to the proof of both Theorem 2 and Theorem 3.

In this paper, we use || · || for 2-norm and || · ||T V for total variance norm. ⟨·, ·⟩ denotes the inner
product. Superscript i in quantity x, i.e. x[i], denotes the x quantity correspond to agent i ∈N .
λ(·) and σ(·) denote the eigenvalues and singular values of the corresponding matrix respectively.
All vectors are assumed to be column vector, unless specified. (·)[T] is the transpose of an matrix or
vector. We use 1 to denote all-1 vector with a proper dimension. For a matrix A, [A]i represents
the i-th row of matrix A. Let [⃗]δ = [δ[1], · · ·, δ[N] ][T], i.e. the column vector for local TD-errors. In
comparison, δ denotes the scalar global TD-error, i.e. δ = N[1] i∈N [δ][i][.]

First, we explain the detail of our experiment setup. P

A.1 EXPERIMENT SETUP

We considered the same setting as in the Section 6.1 of Zhang et al. (2018). There are N agents,
each has a binary-valued action space, i.e. A[i] = {0, 1}, for all i ∈N . In addition, in all the results
shown here, we set |S| = 5 states. The elements in the transition matrix are uniformly sampled from
the interval [0, 1] and normalized to be stochastic. We also added 10[−][5] onto each element to ensure
ergodicity of the MDP such that the Assumption 1 is satisfied. For each agent i and state action pair
(s, a), the mean reward R[i](s, a) is sampled uniformly from [0, 4]. The instantaneous rewards rt[i] [are]
sampled from the uniform distribution [R[i](s, a) − 0.5, R[i](s, a) + 0.5]. The policy is parameterized
following the Bolzmann policies, i.e.,

exp(qs,a[T] [i] [θ][i][)]
πθ[i] [i] [(][s, a][i][) =]

b[i]∈A[i][ exp(][q]s,b[T] [i] [θ][i][)]


-----

where qs,b[T] [i][ is the feature vector with the same dimension as][ θ][i][, for all][ s][ ∈S][ and][ i][ ∈N] [. Here,]
we set m1 = · · · = mN = 5. The elements of qs,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 βw,t = t[0]1[.][51][ and][ β][θ,t][ =] t[0]1[.][52][ . The network matrix as chosen]

as a ring network with diagonal elements being 0.4 and off diagonal elements 0.3 .

For our algorithm, we used step-sizes α = 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 βw =
1 1

t[0][.][65][ and][ β][θ][ =] t[0][.][85][ as in the paper (Zhang et al., 2018), and for the constant steptize MARL and]

batch constant stepsize MARL, we chose stepsizes to be βw = 0.9 and βθ = 0.01. For batch MARL
and batch constant stepsize MARL, we used batch size as 10. Other parameters are the same as in
the A.1. We vary the system sizes from N = 5 to N = 15 and the empirical comparison results are
in Figure 2 (a)-(c). In addition, we provide the comparison between average reward setting with the
discounted counterpart of our algorithms for discounting factors ranging from γ = 0.1 to γ = 0.999.
As we can see from Figure 2 (a)-(c), our TD-sharing algorithm performs well compared to the baseline algorithms. Among the modified algorithms, batch constant stepsize MARL shows improvement 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 modification seem to improve the classical MARL. Yet in (a), for smaller system size, i.e. N = 5, only
modifying to the batch size or constant stepsizes don’t seem to improve the performance.
In addition, in (d), for discounted setting, as γ increases and gets closer to 1, 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]1−[ ǫ]γ[−][1] [)][ (Kakade, 2003), to an][ ǫ][ 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 a 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 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 2. Among these three structures, within given sample numbers, ring
network yields the best result.

A.3 SUPPORTING LEMMAS FOR THEOREM 2

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 θ ∈ RPi∈N [m][i], consider the MDP with policy πθ and transition kernel P (·|s, a). Let dθ be the stationary distribution of the MDP. There exist constants κ > 0
and ρ ∈ (0, 1) such that sups∈S ||P (st|s0 = s) − dθ||T V ≤ κρ[t], ∀t ≥ 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; Qiu et al., 2021).

As a result of the Lemma 1, the Markov chain of state-action pair {st, at}t≥0 for policy πθ also has
the property of ergodicity. We state this result as the following lemma.


-----

(a) N = 5 (b) N = 10

2.5


1.5

1

0.5

|Col1|Col2|Col3|Col4|Col5|Col6|Col7|
|---|---|---|---|---|---|---|
||||||||
||||||||
||||TD-sharing Discounted Discounted|MARL Counter Counter|part with part with|=0.1 =0.5|
||||||||
||||||||
||||||||
||||Discounted Discounted Discounted|Counter Counter Counter|part with part with part with|=0.9 =0.99 =0.999|
||||||||
||||||||


TD-sharing MARL
Discounted Counterpart with =0.1

Discounted Counterpart with =0.5

Discounted Counterpart with =0.9

Discounted Counterpart with =0.99

Discounted Counterpart with =0.999


Sample Number 10[5]

(d) average vs discounted


(c) N = 15


Figure 2: The empirical comparisons of algorithms


2.25

2.2


2.15

2.1


2.05

2

1.95


1.9

|Col1|Col2|Col3|Col4|Col5|Col6|Col7|
|---|---|---|---|---|---|---|
||||||||
||||||||
||||||||
||||||||
||||Rin||||
|||||Rin|g Network||
||||Sm Reg|Sm Reg|all World N ular Netw|etwork ork|
||||||||


Ring Network
Small World Network
Regular Network


Sample Number 10[5]

Figure 3: Different Network Structures on Performance When N = 10


-----

Lemma 2. Suppose the Assumption 1 hold, let νθ be the stationary distribution of the state-action
pair MDP. Then, we have

sup ||P (st, at|s0 = s) − νθ||T V ≤ κρ[t], ∀t ≥ 0. (10)
s∈S

Proof. For any given s0 ∈S, by definition, we have


||P (st, at|s0) − νθ||T V = [1]

2

= [1]

2

= [1]

2

= [1]

2

= [1]


|P (st = s, at = a|s0) − νθ(s, a)|
(s,a)∈S×A

X

|P (st = s|s0)πθ(at = a|st = s) − νθ[s][(][s][)][π][θ][(][a][|][s][)][|]
(s,a)∈S×A

X

|(P (st = s|s0) − νθ[s][(][s][))][π][θ][(][a][|][s][)][|]
(s,a)∈S×A

X

πθ(a|s)|P (st = s|s0) − νθ[s][(][s][)][|]
(s,a)∈S×A

X

|P (st = s|s0) − νθ[s][(][s][)][|]
s∈S

X


= ||P (st|s0) − νθ[s][||][T V] [≤] [κρ][t][.]

Since it holds for all s0 ∈S, equation 10 holds.

As a result of Assumption 5, we have the following lemmas.

Lemma 3. For all policy πθ, we have

⟨w, Aπθ w⟩≤− [λ]2[A] [||][w][||][2] (11)

where λA is defined in Assumption 5.

Proof. Because of the fact w[T] Aπθ w = w[T] A[T]πθ [w][, we have]


w[T] Aπθ w = [1] πθ [w][)]

2 [(][w][T][ A][π][θ] [w][ +][ w][T][ A][T]

= [1] πθ [)][w]

2 [w][T][ (][A][π][θ][ +][ A][T]


≤− [λ][A] (12)

2 [w][T][ w][ =][ −] [λ]2[A] [||][w][||][2][.]

In fact, interestingly enough, the Assumption 5 and Lemma 3 are equivalent in a sense that if the
statement in the Lemma 3 is taken as the assumption, the statement in the Assumption 5 can be
obtained as a result. And the paper (Xu et al., 2020) used the statement in the Lemma 3 as an
assumption, whereas in ours and (Qiu et al., 2021), we assumed Assumption 5.

Lemma 4. For any given policy πθ, the corresponding optimal value function approximation parameter wθ[∗] [is uniformly bounded, specifically, there exists][ R][w][ :=][ 4][r]λ[max]A > 0 such that

||wθ[∗][|| ≤] [R][w][.] (13)

Proof. It’s easy to see that J(θ) ≤ rmax from equation 2 and ¯r(s, a) ≤ rmax for any (s, a) pair.
Then, we have

||wθ[∗][||][ =][ || −] [A][−]πθ[1][b][π]θ [||]


-----

−1
= || − Es∼dθ(s),s′∼P (·|s)[(φ(s[′]) − φ(s))φ[T] (s)] -  Es∼dθ,a∼πθ [φ(s)(¯r(s, a) − J(θ))]||

−1
≤|| − Es∼dθ(s),s′∼P (·|s)[(φ(s[′]) − φ(s))φ[T] (s)]
 || · ||Es∼dθ,a∼πθ [φ(s)(¯r(s, a) − J(θ))]||

1
=  
 -  ||Es∼dθ,a∼πθ [φ(s)(¯r(s, a) − J(θ))]||

σmin −Es∼dθ(s),s′∼P (·|s)[(φ(s[′]) − φ(s))φ[T] (s)]

r(s, a) − J(θ))]||
≤ [2][||][E][s][∼] [d][θ][,a][∼][π][θ] [[][φ][(][s][)(¯] 


λmin(−Aπθ − A[T]πθ [)]


r(s, a)| + |J(θ)|)]
≤ [2][E][s][∼][d][θ][,a][∼][π][θ] [[][||][φ][(][s][)][|| ·][ (][|][¯]


= [4][r][max]

λA


where the third equality used the fact ||A[−][1]|| = σmin1(A) [and the second from the last inequality is]

from Bhatia (1997) (Proposition III 5.1) .

Note that, for agent i ∈N, the estimated long term average reward µ[i]k,τ [at sample][ τ][ of iteration][ k]
in equation 5 can be written as


µ[i]k,τ [=][ β]


(1 − β)[τ] [−][l]rk,l[i] [+ (1][ −] [β][)][τ] [µ]0[i] [.] (14)
l=1

X


Lemma 5. For any i ∈N and t ≥ 0, step size 0 < β < 1, for the estimated long term average
reward for agent i, we have

µ[i]t+1 [= (1][ −] [β][)][µ]t[i] [+][ βr]t[i] (15)

is bounded by rmax, i.e. |µ[i]t+1[| ≤] [r][max][.]

Proof. WLOG, we suppose that 0 < µ[i]0 [≤] [r][max][, we have]

|µ[i]t+1[|][ =][ |][(1][ −] [β][)][µ]t[i] [+][ βr]t[i][|]

≤ (1 − β)|µ[i]t[|][ +][ β][|][r]t[i][|][.] (16)

By the supposition, we have |µ[i]0[| ≤] [r][max][. We assume][ |][µ]t[i][| ≤] [r][max] [holds for iteration][ t >][ 0][, then]
for t + 1, by equation 16

|µ[i]t+1[| ≤] [(1][ −] [β][)][|][µ]t[i][|][ +][ β][|][r]t[i][| ≤] [(1][ −] [β][)][r][max] [+][ βr][max] [=][ r][max][.]

Therefore, Lemma 5 holds by mathematical induction.

For a given policy πθ, to establish a bound on the difference between the optimal approximation
parameter wθ[∗][, we first derive a bound the difference between parameter][ w]k[i] [and the average among]
all agents ¯wk at time k. Then, we derive a bound for the difference between average ¯wk and the
optimal wθ[∗][.]

We have following notations for the analysis. Given an agent i ∈N, we consider the consensus
error at time k and we denote Q[i]k [=][ w]k[i] [−] w[¯]k, where ¯wk := N1 i∈N [w]k[i] [. Then, we denote the]

matrix form as Qk = [Q[1]k[,][ · · ·][, Q][N]k []][ ∈] [R][K][×][N][ Then, we have the following lemma.]

P

Lemma 6. Suppose the Assumption 2 and 3 hold. For the consensus error matrix, we have

||Qk+1|| ≤κ1N [2]γ[k]||Q0|| + κ[′]2[N][ 3][β] (17)

where γ := (1 − η[N] [−][1]) · (1 + 2β) < 1, κ1 = 2(1 + 2β)(1 + η[−][(][N] [−][1)]) and κ[′]2 [=][ 4(1+][η][−]1[(][N]−[−]γ[1)][)][r][max] .

Proof. By equation 7, the parameter update ˜wk[i] [for agent][ i][ at iteration][ k][ can be written as follows]


w˜k[i] [=][ w]k[i] [+][ β]

M

= wk[i] [+][ β]


δk,τ[i] [·][ φ][(][s][k,τ] [)]
τ =0

X

M −1



[rk,τ[i] +1 [−] [β]
τ =0

X


(1 − β)[τ] [−][l]rk,l[i] [−] [(1][ −] [β][)][τ] [µ]0[i]
l=1

X


-----

+ φ(sk,τ +1)[T] wk[i] [−] [φ][(][s][k,τ] [)][T][ w]k[i] []][ ·][ φ][(][s][k,τ] [)]


M −1

φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T] wk[i]
τ =0

X


= wk[i] [+][ β]

M


M −1

(rk,τ[i] +1 [−] [β]
τ =0

X


+ [β]


(1 − β)[τ] [−][l]rk,l[i] [−] [(1][ −] [β][)][τ] [µ]0[i] [)][φ][(][s][k,τ] [)][.] (18)
l=1

X


After a consensus step, the update will be


wk[i] +1 [=]


A(i, j) · ˜wk[j]
j∈Ni

X

A(i, j) · [wk[j] [+][ β]

M

j∈Ni

X


M −1

φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T] wk[j]
τ =0

X


M −1

(rk,τ[j] +1 [−] [β]
τ =0

X


+ [β]


(1 − β)[τ] [−][l]rk,l[j] [−] [(1][ −] [β][)][τ] [µ]0[j] [)][φ][(][s][k,τ] [)]]
l=1

X

M −1


A(i, j) · wk[j] [+][ β]

M

j∈Ni

X


φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T][ X] A(i, j) · wk[j]
τ =0 j∈Ni

X

τ


M −1

+ [β] φ(sk,τ )

M

τ =0

X


A(i, j) · (rk,τ[j] +1 [−] [β]
j∈Ni

X


(1 − β)[τ] [−][l]rk,l[j] [−] [(1][ −] [β][)][τ] [µ]0[j] [)]
l=1

X


M −1

φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T] wk · (Ai,:)[T]
τ =0

X


= wk · (Ai,:)[T] + [β]


M −1

+ [β] φ(sk,τ )Ai,:(rk,τ +1 − β

M

τ =0

X


(1 − β)[τ] [−][l]rk,l − (1 − β)[τ] µ0) (19)
l=1

X


where wk = [wk[1][, w]k[2][,][ · · ·][, w]k[N] []][ ∈] [R][K][×][N][ is the matrix form of all parameters at time][ k][,][ A][i,][:][ is]
the i-th row of matrix A and rk,l = (rk,l[1] [,][ · · ·][, r]k,l[N] [)][. Now we consider the average dynamics of the]
algorithm. Recall ¯wk = N[1] i∈N [w]k[i] [, then using equation 19 we have]


w¯k+1 = [1]

N

= [1]


wk[i] +1
i∈N

X

wk · (Ai,:)[T] + [β]

M

i∈N

X


M −1

φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T] wk · (Ai,:)[T]
τ =0

X


M −1

φ(sk,τ )Ai,:(rk,τ +1 − β
τ =0

X


+ [β]


(1 − β)[τ] [−][l]rk,l − (1 − β)[τ] µ0)
l=1

X


M −1

φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T][ 1]

N [w][k][ ·][ 1]

τ =0

X


= [1]

N [w][k][ ·][ 1][ +][ β]M


M −1

φ(sk,τ ) [1]

N

τ =0

X


+ [β]


(1 − β)[τ] [−][l]rk,l − (1 − β)[τ] µ0)
l=1

X


Ai,:(rk,τ +1 − β
i∈N

X


M −1

φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T] w¯k
τ =0

X


= ¯wk + [β]


M −1

φ(sk,τ ) [1]

N [1][T][ (][r][k,τ] [+1][ −] [β]

τ =0

X


+ [β]


(1 − β)[τ] [−][l]rk,l − (1 − β)[τ] µ0)
l=1

X


-----

M −1

φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T] w¯k
τ =0

X


= ¯wk + [β]


M −1

φ(sk,τ )(¯rk,τ +1 − β
τ =0

X


+ [β]


(1 − β)[τ] [−][l]r¯k,l − (1 − β)[τ] µ0) (20)
l=1

X


where ¯rk,l = N[1]


i∈N [r]k,l[i] [.]


Given an agent i ∈N, we consider the consensus error at time k and recall Q[i]k [=][ w]k[i] [−] w[¯]k. Then,
we have

Q[i]k+1 [=][w]k[i] +1 [−] w[¯]k+1


M −1

φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T] (wk · (Ai,:)[T] − w¯k)
τ =0

X


=wk · (Ai,:)[T] − w¯k + [β]


M −1

φ(sk,τ )(Ai,: − [1]

N [1][T][ )(][r][k,τ] [+1][ −] [β]

τ =0

X


+ [β]


(1 − β)[τ] [−][l]rk,l − (1 − β)[τ] µ0). (21)
l=1

X


Then, for the matrix form Qk = [Q[1]k[,][ · · ·][, Q][N]k []][ ∈] [R][K][×][N] [, we have]


M −1

φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T] QkA[T]
τ =0

X


Qk+1 =QkA[T] + [β]


M −1

φ(sk,τ )[(A − [1]

N [11][T][ )(][r][k,τ] [+1][ −] [β]

τ =0

X


+ [β]


(1 − β)[τ] [−][l]rk,l − (1 − β)[τ] µ0)][T]
l=1

X


M −1

φ(sk,τ )[φ(sk,τ +1) − φ(sk,τ )][T] QkA[T]
τ =0

X


=QkA[T] + [β]


M −1

φ(sk,τ )[rk,τ +1 − β
τ =0

X


+ [β]


τ

(1 − β)[τ] [−][l]rk,l − (1 − β)[τ] µ0][T] (A − N[1] [11][T][ )]
l=1

X


(22)

where the first equality is due to A being doubly stochastic. For convenience, denote Bk =
1 M −1 1 M −1

M τ =0 [φ][(][s][k,τ] [)[][φ][(][s][k,τ] [+1][)][ −] [φ][(][s][k,τ] [)]][T][ and][ C][k][ =] M τ =0 [φ][(][s][k,τ] [)[][r][k,τ] [+1][ −] [β][ P]l[τ]=1[(1][ −]

β)[τ] [−][l]rk,l − (1 − β)[τ] µ0][T] . Then, iteratively we have

P P

Qk+1 =(I + βBk)QkA[T] + βCk(A − N[1] [11][T][ )]


(I + βBt˜[)][C][t][(][A][ −] [1] (23)

N [11][T][ )][A][k][−][t]

t=0 t>t˜

X Y


(I + βBt)Q0(A[T] )[k][+1] + β
t=0

Y


Then, the norm of the consensus error is following


k

(I + βBt˜[)][C][t][(][A][ −] [1]

N [11][T][ )][A][k][−][t][||]

t>t˜

Y


(I + βBt)Q0(A[T] )[k][+1] + β
t=0

Y


||Qk+1|| =||

≤||


t=0


k

||(I + βBt˜[)][|| · ||][C][t][|| · ||][(][A][ −] [1]

N [11][T][ )][A][k][−][t][||][.]

t>t˜

Y

(24)


(I + βBt)|| · ||Q0(A[T] )[k][+1]|| + β
t=0 t=0

Y X


Note that since A is doubly stochastic, so is A[T] . Let (A[T] )[k]:,i[+1] be the i-th column of matrix (A[T] )[k][+1].
From Nedic & Ozdaglar (2009), we know that


||Q0(A[T] )[k]:,i[+1][||][ =][ ||][Q][0][(][A][T][ )]:[k],i[+1] − Q0


N [1][||]


-----

((A[T] )[k]j,i[+1] − [1] 0[||]

N [)][Q][j]

j∈N

X


= ||


|(A[T] )[k]j,i[+1] − [1] 0[||]

N [| · ||][Q][j]

j∈N

X


≤ N · 2 [1 +][ η][−][(][N] [−][1)] 0[||]

1 − η[N] [−][1][ (1][ −] [η][N] [−][1][)][k][+1][ ·][ max]j∈N [||][Q][j]

≤ 2N (1 + η[−][(][N] [−][1)])(1 − η[N] [−][1])[k] -  ||Q0||. (25)

Hence, ||Q0A[k][+1]|| ≤ 2N [2](1 + η[−][(][N] [−][1)])(1 − η[N] [−][1])[k] -  ||Q0||. To bound the first term in the RHS
of equation 24, we have


|| (I + βBt)|| ≤

t=0

Y


||I + βBt||
t=0

Y

k

(||I|| + β||Bt||)
t=0

Y

k

(1 + 2β) = (1 + 2β)[k][+1]. (26)

t=0

Y


In order to make sure it converges to the neighborhood of a consensus in the limit, the step size has
η[N] [−][1]
to satisfy γ := (1 − η[N] [−][1]) · (1 + 2β) < 1, which results in β < 2(1−η[N] [−][1]) [. Hence, for the first]

term in the RHS of equation 24, we have


|| (I + βBt)|| · ||Q0A[k][+1]|| ≤ κ1N [2]γ[k]||Q0||

t=0

Y


where κ1 = 2(1 + 2β)(1 + η[−][(][N] [−][1)]).

Furthermore, we have

||(A − [1] (27)

N [11][T][ )][A][k][−][t][||][ =][ ||][A][k][−][t][+1][ −] N[1] [11][T][ || ≤] [2][N][ 2][(1 +][ η][−][(][N] [−][1)][)(1][ −] [η][N] [−][1][)][k][−][t][.]


And ||Ct|| ≤ 2Nrmax, where rmax = supi,s,a r[i](s, a). This is because

M −1 τ

||Ck|| = || [1] φ(sk,τ )[rk,τ +1 − β (1 − β)[τ] [−][l]rk,l − (1 − β)[τ] µ0][T] ||

M

τ =0 l=1

X X

M −1 τ

≤ [1] ||φ(sk,τ )[rk,τ +1 − β (1 − β)[τ] [−][l]rk,l − (1 − β)[τ] µ0][T] ||

M

τ =0 l=1

X X

M −1 τ

≤ [1] ||φ(sk,τ )|| · ||rk,τ +1 − β (1 − β)[τ] [−][l]rk,l − (1 − β)[τ] µ0||

M

τ =0 l=1

X X

M −1 τ

≤ [1] [||rk,τ +1|| + β (1 − β)[τ] [−][l]||rk,l|| + (1 − β)[τ] ||µ0||]

M

τ =0 l=1

X X

M −1

≤ [1] [Nrmax + β [1][ −] [(1][ −] [β][)][τ]

M 1 − (1 − β) [Nr][max][ + (1][ −] [β][)][τ] [Nr][max][] = 2][Nr][max][.]

τ =0

X


Then for the second term of equation 24, we have


k

||(I + βBt˜[)][|| · ||][C][t][|| · ||][(][A][ −] [1]

N [11][T][ )][A][k][−][t][||]

t>t˜

Y


t=0


-----

(1 + 2β)[k][−][t] -  2Nrmax · 2N [2](1 + η[−][(][N] [−][1)])(1 − η[N] [−][1])[k][−][t]
t=0

X


≤β


k

γ[k][−][t] = κ2N [3]β [1][ −] [γ][k][+1] (28)

1 − γ

t=0

X


=κ2β


where κ2 = 4(1 + η[−][(][N] [−][1)])rmax. Further, for consensus error equation 24, we have

||Qk+1|| ≤ κ1N [2]γ[k]||Q0|| + κ2N [3]β [1][ −] [γ][k][+1] ≤κ1N [2]γ[k]||Q0|| + κ[′]2[N][ 3][β] (29)

1 − γ


where κ[′]2 [=] 1κ−2γ [.]

The corresponding average parameter under the policy πθ will converge to the solution to
the following equation wθ[∗] = A[−]θ [1][b][θ][, where][ A][θ] = Es∼dθ(s)[φ(s)(φ(s[′]) − φ(s))[T] ], bθ =
E(s,a)∼dθ(s,a)[(¯r(s, a) − J(θ))φ(s)] and ¯r(s, a) = N[1] i∈N [r][i][(][s, a][)][.]

Now consider || ¯wk − w[∗]||. Recall the from the average parameter equation equation 20 and theP
corresponding ODE is

w˙ θ = Aθwθ + bθ. (30)

For the difference between average dynamics and the optimal value, we have the following lemma.


λ4A [}][ and][ M][ ≥] [(][ 1]λA [+][ β][)][ 6144[1+(](1−ρ)[κ]λ[−]A[1)][ρ][]], we have


Lemma 7. For β ≤ min{ 128[λ][A] [,]


w [+][ r]max[2] [)[1 + (][κ][ −] [1)][ρ][]]

E[|| ¯wK − wθ[∗][||][2]2[]][ ≤] [(1][ −] [λ][A] w0 − wθ[∗][||][2]2 [+ ( 1] + β) [1536(4][R][2] .

8 [β][)][K] [||][ ¯] λA (1 − ρ)λAM

(31)

Proof. The proof follows from verifying the Assumption 3 of Xu et al. (2020), then we can apply
the results from Theorem 4 of Xu et al. (2020).

1. For item 1 in the assumption, it’s easy to check that ||Aθ|| ≤ CA = 4 by Assumption 4 and
bθ ≤ Cb = 2rmax.

2. For item 2, it holds because of Lemma 3.

3. For item 3, it holds because of Lemma 1.

And we recall that the bound on ||wθ[∗][||][ is][ R][w][ =][ 4][r]λ[max]A [. Hence, by Theorem 4 of Xu et al. (2020),]

β ≤ min{ 8[λ]C[A]A[2] [,] λ4A [}][ and][ M][ ≥] [(][ 2]λA [+ 2][β][)][ 192][C](1A[2] −[[1+(]ρ)λ[κ]A[−][1)][ρ][]], equation 31 holds.

A.4 PROOF OF THEOREM 2

As a result from Lemma 4 and Lemma 7, we provide the following proof for Theorem 2.

Proof. Therefore, by equation 17 and equation 31, we have


E[ ||wK[i] [−] [w]θ[∗][||][2][]]

i=1

X

N N

≤ 2E[ ||wK[i] [−] w[¯]K ||[2]] + 2E[ || ¯wK − wθ[∗][||][2][]]

i=1 i=1

X X

≤ 2||QK ||[2] + 2N E[|| ¯wK − wθ[∗][||][2][]]


≤ 2(κ1N [2]γ[K] ||Q0|| + κ[′]2[N][ 3][β][)][2][ + 2][N] [(1][ −] [λ][A] w0 − wθ[∗][||][2]2

8 [β][)][K] [||][ ¯]


-----

A[R]w[2] [+][ C]b[2][)[1 + (][κ][ −] [1)][ρ][]]

+ 2N ( [2] + 2β) [192(][C] [2]

λA (1 − ρ)λAM


≤ κ[′]1[N][ 4][γ][2][K][ +][ κ][′′]2 [N][ 6][β][2][ +][ κ][3][N][ 5][γ][K] [β][ + 2][N] [(1][ −] [λ][A] w0 − wθ[∗][||][2]2 [+][ κ][4]

8 [β][)][K] [||][ ¯] M [N]

where κ[′]1 = 2κ[2]1[||][Q][0][||][2][,] κ”2 = 2κ[′]2[2][,] κ3 = 4κ1κ[′]2[||][Q][0][||][ and][ κ][4] = ( λ[1]A [+]

β) [3072(4][R]w[2] [+](1[r]−max[2]ρ)λ[)[1+(]A [κ][−][1)][ρ][]] .


A.5 PROOF OF THEOREM 3

We use wt[∗] [to denote the optimal value function parameter under policy][ θ][t] [at time][ t][ and]
wt = [(wt[1][)][T][,][ · · ·][,][ (][w]t[N] [)][T][ ]][T] ∈ R[N] [×][K], which is the aggregated function approximation parameters from Line 2 of Algorithm 2. Recall the δ[˜]t,l[i] [generated by Line 18 of Algorithm 2,]
which is the i-th agent’s estimate of the global TD-error from sample l at time t after consensus. Let vt[i][(][w][t][) =] B1 Bl=0−1 δ[˜]t,l[i] [(][w][t][)][ ·][ ψ]t,l[i] [and][ v][t][(][w][t][) = [(][v]t[1][(][w][t][))][T][,][ · · ·][,][ (][v]t[N] [(][w][t][))][T][ ]][T][,]

h[i]t[(][w]t[∗][) =] B1 Bl=0−1 [δ][t,l][(][w]t[∗][)]P[ ·][ ψ]t,l[i] [and][ h][t][(][w]t[∗][) = [(][h]t[1][(][w]t[∗][))][T][,][ · · ·][,][ (][h]t[N] [(][w]t[∗][))][T][ ]][T][, Adv][w][(][s, a][) =]

Es′∼P (·|s,a),r∼dr(s,a)[δw(s, a, s[′])|s, a] and g[i](w, θ) = E[Advw(s, a)ψθi (s, a[i])], where dr(s, a) is
P
the reward distribution of state-action pair (s, a). By Taylor expansion and the Lipschitz property
from Assumption 6, we have


J(θt+1) ≥ J(θt) + ⟨∇θJ(θt), θt+1 − θt⟩− [L][J]

2 [||][θ][t][+1][ −] [θ][t][||][2]

= J(θt) + α⟨∇θJ(θt), vt(wt) −∇θJ(θt) + ∇θJ(θt)⟩− [L][J] [α][2]


||vt(wt)||[2]


= J(θt) + α||∇θJ(θt)||[2] + α⟨∇θJ(θt), vt(wt) −∇θJ(θt)⟩− [L][J] [α][2]

2

−∇θJ(θt) + ∇θJ(θt)||[2]


||vt(wt)


≥ J(θt) + ( [1]

2 [α][ −] [L][J] [α][2][)][||∇][θ][J][(][θ][t][)][||][2][ −] [(1]2 [α][ +][ L][J] [α][2][)][||][v][t][(][w][t][)][ −∇][θ][J][(][θ][t][)][||][2]

where the last inequality is because


⟨∇θJ(θt), vt(wt) −∇θJ(θt)⟩≥− [1]

2 [||∇][θ][J][(][θ][t][)][||][2][ −] 2[1] [||][v][t][(][w][t][)][ −∇][θ][J][(][θ][)][||][2][,]


and

||vt(wt) −∇θJ(θt) + ∇θJ(θt)||[2] ≤ 2||vt(wt) −∇θJ(θt)||[2] + 2||∇θJ(θt)||[2]. (32)

Taking expectations on both sides conditioned on the filtration Ft and rearranging the terms, we
have


( [1]

2 [α][ −] [L][J] [α][2][)][E][[][||∇][θ][J][(][θ][t][)][||][2][|F][t][]][ ≤] [E][[][J][(][θ][t][+1][)][|F][t][]][ −] [J][(][θ][t][)]

+ ( [1] (33)

2 [α][ +][ L][J] [α][2][)][E][[][||][v][t][(][w][t][)][ −∇][θ][J][(][θ][t][)][||][2][|F][t][]][.]

Then, we establish upper bound on the third term of the RHS. By definition, we have

||vt(wt) −∇θJ(θt)||[2]


= ||vt(wt) − vt(wt[∗][) +][ v][t][(][w]t[∗][)][ −] [h][t][(][w]t[∗][) +][ h][t][(][w]t[∗][)][ −] [g][(][w]t[∗][, θ][t][) +][ g][(][w]t[∗][, θ][t][)][ −∇][θ][J][(][θ][t][)][||][2]

≤ 6||vt(wt) − vt(wt[∗][)][||][2][ + 6][||][v][t][(][w]t[∗][)][ −] [h][t][(][w]t[∗][)][||][2][ + 6][||][h][t][(][w]t[∗][)][ −] [g][(][w]t[∗][, θ][t][)][||][2]

+ 6||g(wt[∗][, θ][t][)][ −∇][θ][J][(][θ][t][)][||][2][.] (34)

We note that ||vt(wt) − vt(wt[∗][)][||][2][ =][ P]i∈N [||][v]t[i][(][w][t][)][ −] [v]t[i][(][w]t[∗][)][||][2][ 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

||vt[i][(][w][t][)][ −] [v]t[i][(][w]t[∗][)][||][2]


-----

B−1

δ˜t,l[i] [(][w][t][)][ ·][ ψ]t,l[i] [−] [1]

B

l=0

X

B−1


B−1

δ˜t,l[i] [(][w]t[∗][)][ ·][ ψ]t,l[i] [||][2]
l=0

X


= || [1]

B

= || [1]

B

= || [1]



[δ[˜]t,l[i] [(][w][t][)][ −] δ[˜]t,l[i] [(][w]t[∗][)]][ ·][ ψ]t,l[i] [||][2]
l=0

X


B−1

|| [1] [A[t][gossip] ]i(wt − wt[∗][1][T][ )][T][ [][φ][(][s][t,l][+1][)][ −] [φ][(][s][t,l][)]][ ·][ ψ]t,l[i] [||][2]

B

l=0

X

max t [1][T][ )][T][ [][φ][(][s][t,l][+1][)][ −] [φ][(][s][t,l][)]][ ·][ ψ]t,l[i] [||][2]
l∈{0,···,B−1} [||][[][A][t][gossip] []][i][(][w][t][ −] [w][∗]

max t [1][T][ ||][2][ · ||][ψ]t,l[i] [||][2]
l∈{0,···,B−1} [||][[][A][t][gossip] []][i][||][2][||][[][φ][(][s][t,l][+1][)][ −] [φ][(][s][t,l][)]][||][2][||][w][t][ −] [w][∗]


≤ 4 · ||wt − wt[∗] [⊗] [1][||][2][ = 4]

where the third equality is from

δ˜t,l[i] [(][w][t][)][ −] δ[˜]t,l[i] [(][w]t[∗][)]


||wt[i] [−] [w]t[∗][||][2] (35)
i=1

X


= [A[t][gossip] ]i[⃗]δt,l(wt) − [A[t][gossip] ]i[⃗]δt,l(wt[∗][)]

= [A[t][gossip] ]i[[⃗]δt,l(wt) − [⃗]δt,l(wt[∗][)]]

φ[T] (st,l+1)(wt[1] [−] [w]t[∗][)][ −] [φ][T][ (][s][t,l][)(][w]t[1] [−] [w]t[∗][)]
.

= [A[t][gossip] ]i  ..

φ[T] (st,l+1)(wt[N] [−] [w]t[∗][)][ −] [φ][T][ (][s][t,l][)(][w]t[N] [−] [w]t[∗][)]




= [A[t][gossip] ]i(wt − wt[∗][1][T][ )][T][ [][φ][(][s][t,l][+1][)][ −] [φ][(][s][t,l][)]][.]

For the second term in the RHS of equation 34, we have

||vt[i][(][w]t[∗][)][ −] [h]t[i][(][w]t[∗][)][||][2]


B−1 B−1

δ˜t,l[i] [(][w]t[∗][)][ ·][ ψ]t,l[i] [−] [1] δt,l(wt[∗][)][ ·][ ψ]t,l[i] [||][2]

B

l=0 l=0

X X

B−1

[δ[˜]t,l[i] [(][w]t[∗][)][ −] [δ][t,l][(][w]t[∗][)]][ ·][ ψ]t,l[i] [||][2]
l=0

X


= || [1]

B

= || [1]

B

= || [1]


B−1

l=0

X



[A[t][gossip] ]i − N[1] [1][T] ⃗δt,l(wt[∗][)][ ·][ ψ]t,l[i] [||][2]




max [A[t][gossip] ]i − [1] ⃗δt,l(wt[∗][)][ ·][ ψ]t,l[i] [||][2]
l∈{0,···,B−1} [||] N [1][T]
 

max δt,l(wt[∗][)][||][2][ · ||][ψ]t,l[i] [||][2]
l∈{0,···,B−1} [||][[][A][t][gossip] []][i][ −] N[1] [1][T][ ||][2][ · ||][⃗]


max δt,l(wt[∗][)][||][2]
l∈{0,···,B−1} [N] [(21 +]1 −[ η][−]η[N][(][N][−][−][1][1)][ (1][ −] [η][N] [−][1][)][t][gossip][+1][)][2][ · ||][⃗]


≤ 16N [2]((1 + η[−][(][N] [−][1)])(1 − η[N] [−][1])[t][gossip] )[2](rmax + Rw)[2] = κ3N [2](1 − η[N] [−][1])[2][t][gossip] (36)

where κ3 = 16(1 + η[−][(][N] [−][1)])[2](rmax + Rw)[2]. We note that the second equality is because

δ˜t,l[i] [(][w]t[∗][)][ −] [δ][t,l][(][w]t[∗][)]

= [A[t][gossip] ]i[⃗]δt,l(wt[∗][)][ −] N[1] [1][T] [⃗]δt,l(wt[∗][)]



[A[t][gossip] ]i − N[1] [1][T] ⃗δt,l(wt[∗][)][.]




-----

For the last inequality, we note that δt,l(w[∗]) is bounded because rewards and feature vectors are
bounded, µ[i] is bounded for constant step size and wt[∗] [is bounded from the critic step. That is, for]
j ∈N entry in [⃗]δt,l(w[∗]) by definition,

δt,l[j] [(][w][∗][) =][ r]t,l[j] [−] [µ]t,l[j] [+ [][φ][(][s][t,l][+1][)][ −] [φ][(][s][t,l][)]][T][ w]t[∗][.]

Hence, its 2-norm bound is

||δt,l[j] [(][w][∗][)][||][ =][ ||][r]t,l[j] [−] [µ]t,l[j] [+ [][φ][(][s][t,l][+1][)][ −] [φ][(][s][t,l][)]][T][ w]t[∗][||]

≤||rt,l[j] [||][ +][ ||][µ][j]t,l[||][ +][ ||][φ][(][s][t,l][+1][)][ −] [φ][(][s][t,l][)][|| · ||][w]t[∗][||]

≤ rmax + rmax + [||φ(st,l+1)|| + ||φ(st,l)||] · Rw ≤ 2rmax + 2Rw. (37)

For the last term in equation 34, we have

||g(wt[∗][, θ][t][)][ −∇][θ][J][(][θ][t][)][||][2]

= ||Edθt (s,a)[Advwt[∗][(][s, a][)][ψ][θ][t] [(][s, a][)]][ −] [E][d][θ]t [(][s,a][)][[][Adv][θ][t][(][s, a][)][ψ][θ][t] [(][s, a][)]][||][2]

= ||Edθt (s,a)[(Advwt[∗][(][s, a][)][ −] [Adv][θ][t] [(][s, a][))][ψ][θ][t] [(][s, a][)]][||][2]

≤ (Edθt (s,a)[||(Advwt[∗][(][s, a][)][ −] [Adv][θ][t][(][s, a][))][ψ][θ][t] [(][s, a][)][||][])][2]

≤ (Edθt (s,a)[||Advwt[∗][(][s, a][)][ −] [Adv][θ][t] [(][s, a][)][|| · ||][ψ][θ][t] [(][s, a][)][||][])][2]

≤ (Edθt (s,a)[|Advwt[∗][(][s, a][)][ −] [Adv][θ][t][(][s, a][)][|][])][2]

= (Edθt (s,a)[|E[Vwt[∗] [(][s][′][)][|][s, a][]][ −] [V][w]t[∗][(][s][)][ −] [E][[][V][θ]t[∗][(][s][′][)][|][s, a][] +][ V][θ]t[∗][(][s][)][|][])][2]

≤ (Edθt (s,a)[|E[Vwt[∗] [(][s][′][)][ −] [V][θ]t[∗][(][s][′][)][|][s, a][]][|][ +][ |][V][w]t[∗] [(][s][)][ −] [V][θ]t[∗][(][s][)][|][])][2]

≤ (Edθt (s,a)[E[|Vwt[∗] [(][s][′][)][ −] [V][θ]t[∗][(][s][′][)][||][s, a][] +][ |][V][w]t[∗] [(][s][)][ −] [V][θ]t[∗][(][s][)][|][])][2]

= (E[|Vwt[∗] [(][s][)][ −] [V][θ]t[∗][(][s][)][|][] +][ E][[][|][V][w]t[∗] [(][s][)][ −] [V][θ]t[∗][(][s][)][|][])][2]

≤ 4(E[|Vwt[∗] [(][s][)][ −] [V][θ]t[∗][(][s][)][|][])][2][ ≤] [4][E][[][|][V][w]t[∗] [(][s][)][ −] [V][θ]t[∗][(][s][)][|][2][]][ ≤] [4][ξ]approx[critic] [.] (38)

For each i ∈N, we have

||h[i]t[(][w]t[∗][)][ −] [g][i][(][w]t[∗][, θ]t[i][)][||][2]


B−1

δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][,][ 1]B
l1=0

X


B−1

δt,l2 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗] [(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][⟩]
l2=0

X


= ⟨ [1]

B

= [1]

B[2]


B−1

l1=0

X

B−1


B−1

⟨δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗] [(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][, δ][t,l][2] [(][w]t[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗] [(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][⟩]
l2=0

X


= [1]

B[2]


||δt,l(wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][||][2]
l=0

X


+ [1]

B[2]


⟨δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][, δ][t,l][2] [(][w]t[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]t,l[i] 2 [(][s, a][i][)]][⟩][.]
l1̸=l2

X


Taking expectation over the filtration Ft, we have

E[||h[i]t[(][w]t[∗][)][ −] [g][i][(][w]t[∗][, θ]t[i][)][||][2][|F][t][]]


B−1

E ||δt,l(wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][||][2][|F][t]
l=0

X h


= [1]

B[2]


+ [1]

B[2]


E ⟨δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][, δ][t,l][2] [(][w]t[∗][)][ψ]θt[i] [−] [E][s,a][[][A][w]t[∗] [(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][⟩|F][t]
l1̸=l2

X h


≤ [16]

B [(][r][max][ +][ R][w][)][2]


+ [1]

B[2]


E ⟨δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][, δ][t,l][2] [(][w]t[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][⟩|F][t]
l1̸=l2

X h


-----

where the inequality follows from triangle inequality and the facts that |δt,l1 (wt[∗][)][ψ]θt[i] [| ≤] [2][r][max][ +]
2Rw and |Es,a[Advwt[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][|][ =][ |][E][[][δ][t,l][1] [(][w]t[∗][)][ψ]θt[i] []][| ≤] [2][r][max][ + 2][R][w][. WLOG, for the]
following term, we suppose l1 < l2. Then we have

E ⟨δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][, δ][t,l][2] [(][w]t[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][⟩|F][t]
h i

=E E ⟨δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] [i] [(][s, a][i][)]][, δ][t,l]2 [(][w]t[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][⟩|F][t,l][1] |Ft
h h i i

=E ⟨δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] [i] [(][s, a][i][)]][,][ E] δt,l2(wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][|F][t,l][1] ⟩|Ft
h h i i

=E ⟨δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] [i] [(][s, a][i][)]][,][ E][[][δ][t,l]2 [(][w]t[∗][)][ψ]θt[i] [|F][t,l][1] []][ −] [E][s,a][[][Adv][w]t[∗] [(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][⟩|F][t]
h i

=E ⟨δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] [i] [(][s, a][i][)]][,][ E][[][Adv][w]t[∗] [(][s][t,l][2] [, a][t,l][2] [)][ψ][θ]t[i] [|F][t,l][1] []][ −] [E][s,a][[][Adv][w]t[∗] [(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][⟩|F][t]
h i

≤E ||δt,l1 (wt[∗][)][ψ]θt[i] [−] [E][s,a][[][Adv][w]t[∗] [(][s, a][)][ψ]θ[i] [i] [(][s, a][i][)]][|| · ||][E][[][Adv][w]t[∗] [(][s][t,l][2] [, a][t,l][2] [)][ψ][θ]t[i] [|F][t,l][1] []][ −] [E][s,a][[][Adv][w]t[∗] [(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][|||F][t]
h

≤2(2rmax + 2Rw)E ||E[Advwt[∗][(][s][t,l][2] [, a][t,l][2] [)][ψ][θ]t[i] [|F][t,l][1][]][ −] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][|||F][t]
h i

≤16(rmax + Rw)[2]κρ[l][2][−][l][1]

where the last inequality follows from

||E[Advwt[∗][(][s][t,l][2] [, a][t,l][2] [)][ψ][θ]t[i] [|F][t,l][1][]][ −] [E][s,a][[][Adv][w]t[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)]][||]


=||


Advwt[∗][(][s][t,l][2] [, a][t,l][2] [)][ψ][θ]t[i] [(][s][t,l][2] [, a][t,l][2] [)][P] [(][s][t,l][2] [, a][t,l][2] [|F][t,l][1] [)][ −]
(st,l2,at,l2 )

X


Advwt[∗][(][s, a][)][ψ][θ]t[i] [(][s, a][)][ν][θ][t] [(][s, a][)][||]
(s,a)

X


≤ ||Advwt[∗][(][s, a][)][ψ]θ[i] t[i] [(][s, a][i][)][|| · |][P][ l][2][−][l][1][(][s, a][|F][t,l][2] [)][ −] [ν][θ][t][(][s, a][)][|]

s,a

X

≤2(2rmax + 2Rw) · ||P [l][2][−][l][1](s, a|Ft,l2 ) − ν(s, a)||T V
≤4(rmax + Rw)κρ[l][2][−][l][1].

Then, we have

E[||h[i]t[(][w]t[∗][)][ −] [g][i][(][w]t[∗][, θ]t[i][)][||][2][|F][t][]]

≤ [1]

B[2][ [16][B][(][r][max][ +][ R][w][)][2][ + 16(][r][max][ +][ R][w][)][2][κ]


ρ[l][2][−][l][1]]

l2̸=l1

X


≤ [1] ]

B[2][ [16][B][(][r][max][ +][ R][w][)][2][ + 32(][r][max]1[ +] −[ R]ρ[w][)][2][κρB]

≤ [16(][r][max][ +][ R][w][)][2][[1 + (2][κ][ −] [1)][ρ][]] . (39)

B(1 − ρ)


Then, we have

E[||vt(wt) −∇θJ(θt)||[2]] ≤24N


||wt[i] [−] [w]t[∗][||][2][ + 6][κ][3][N][ 3][(1][ −] [η][N] [−][1][)][2][t][gossip]
i=1

X


+ 24ξapprox[critic] [+ 96(][r][max][ +][ R][w][)][2][[1 + (2][κ][ −] [1)][ρ][]] N (40)

B(1 − ρ)

As a result, substituting equation equation 40 into equation 33 and taking expectation over Ft on
both sides, we have


( [1]

2 [α][ −] [L][J] [α][2][)][E][[][||∇][θ][J][(][θ][t][)][||][2][]]

≤ E[J(θt+1)] − E[J(θt)] + ( [1]

2 [α][ +][ L][J] [α][2][)]


||wt[i] [−] [w]t[∗][||][2]
i=1

X


24N


-----

+6κ3N [3](1 − η[N] [−][1])[2][t][gossip] + 24ξapprox[critic] [+ 96(][r][max][ +][ R][w][)][2][[1 + (2][κ][ −] [1)][ρ][]] N . (41)

B(1 − ρ)



By considering step size α =


1

4LJ [, and dividing both sides of previous equation by]


1

16LJ [, we have]


E[||∇θJ(θt)||[2]] ≤16LJ (E[J(θt+1)] − E[J(θt)]) + 72N


||wt[i] [−] [w]t[∗][||][2]
i=1

X


+ 18κ3N [3](1 − η[N] [−][1])[2][t][gossip] + 72ξapprox[critic] [+ 288][N][ (][r][max][ +][ R][w][)][2][[1 + (2][κ][ −] [1)][ρ][]]

B(1 − ρ)

(42)

Let T[ˆ] be a random variable that takes value uniformly among {1, · · ·, T }. Taking summation over
t = {1, · · ·, T } and dividing by T, we have


E[||∇θJ(θ ˆT [)][||][2][] = 1]

T


E[||∇θJ(θt)||[2]]
t=1

X


T N
t=1 i=1 [||][w]t[i] [−] [w]t[∗][||][2]

≤ [16][L][J] [(][E][[][J][(][θ][T][ )]][ −] [E][[][J][(][θ][0][)])] + 72N

T T
P P

+ 18κ3N [3](1 − η[N] [−][1])[2][t][gossip] + 72ξapprox[critic] [+ 288(][r][max][ +][ R][w][)][2][[1 + (2][κ][ −] [1)][ρ][]] N

B(1 − ρ)

N
i=1 [||][w]t[i] [−] [w]t[∗][||][2]

≤ [16][L][J] [E][[][J][(][θ][T][ )]] + 72N

T T
P

+ 18κ3N [3](1 − η[N] [−][1])[2][t][gossip] + 72ξapprox[critic] [+ 288(][r][max][ +][ R][w][)][2][[1 + (2][κ][ −] [1)][ρ][]] N.

B(1 − ρ)


-----