arXiv:1802.08757v2 [cs.LG] 27 Feb 2018

Fully Decentralized Multi-Agent Reinforcement
Learning with Networked Agents
Kaiqing Zhang\

Zhuoran Yang†

Han Liu∗‡

Tong Zhang‡

Tamer Başar\

Abstract
We consider the problem of fully decentralized multi-agent reinforcement learning (MARL),
where the agents are located at the nodes of a time-varying communication network. Specifically,
we assume that the reward functions of the agents might correspond to different tasks, and are
only known to the corresponding agent. Moreover, each agent makes individual decisions based
on both the information observed locally and the messages received from its neighbors over the
network.
Within this setting, the collective goal of the agents is to maximize the globally averaged
return over the network through exchanging information with their neighbors. To this end,
we propose two decentralized actor-critic algorithms with function approximation, which are
applicable to large-scale MARL problems where both the number of states and the number
of agents are massively large. Under the decentralized structure, the actor step is performed
individually by each agent with no need to infer the policies of others. For the critic step,
we propose a consensus update via communication over the network. Our algorithms are
fully incremental and can be implemented in an online fashion. Convergence analyses of the
algorithms are provided when the value functions are approximated within the class of linear
functions. Extensive simulation results with both linear and nonlinear function approximations
are presented to validate the proposed algorithms. Our work appears to be the first study of
fully decentralized MARL algorithms for networked agents with function approximation, with
provable convergence guarantees.

1

Introduction

In reinforcement learning (Sutton and Barto, 1998), the decision maker (synonymously, agent) aims
to achieve the optimal behavior in the presence of uncertainty by interacting with the environment,
which is usually modeled as a Markov Decision Process (MDP). With the advancement of deep
learning (Goodfellow et al., 2016), reinforcement learning has been shown to achieve striking
\ Department of Electrical and Computer Engineering & Coordinated Science Laboratory, University of Illinois at
Urbana-Champaign
† Department of Operations Research and Financial Engineering, Princeton University
∗ Department of Electrical Engineering and Computer Science and Statistics, Northwestern University
‡ Tencent AI Lab

1

performances in MDP problems such as board games (Silver et al., 2016, 2017), autonomous
driving (Shalev-Shwartz et al., 2016), and robotics (Kober and Peters, 2012). See Li (2017) for an
overview of recent achievements of deep reinforcement learning.
In this work, we study the problem of multi-agent reinforcement learning (MARL), where
a common environment is influenced by the joint actions of multiple agents. In particular, at
each state, each agent takes an action, and these actions together determine the next state of the
environment and the reward of each agent. In addition, the agents are allowed to have different
reward functions from different tasks, but each agent can observe only its own reward. We are
interested in the collaborative setting where the agents have a common goal, which is to jointly
maximize the globally averaged return over all agents in the environment.
For collaborative MARL problems, it is pivotal to specify the protocol of collaboration among
the agents. One tempting choice is to have a central controller which receives the rewards of all
agents, and determines the action for each agent. With information of all the agents available
to the controller, the problem reduces to a classical MDP and can be solved by existing singleagent reinforcement learning algorithms. However, in many real-world scenarios, such as sensor
networks (Rabbat and Nowak, 2004) and intelligent transportation systems (Adler and Blue, 2002),
a central controller simply does not exist or may be costly to install. Moreover, the central controller
needs to communicate with each agent to exchange the information, which incessantly increases
the communication overhead at the single controller. This may degrade the scalability of the
multi-agent system as well as its robustness to malicious attacks.
In view of all these disadvantages of the centralized protocol, we consider here a decentralized
protocol where the agents are connected by a possibly time-varying communication network, which
serves as the channels for the agents to exchange information in absence of any central controller.
Specifically, let {Gt = (N , Et )}t≥0 be a time-varying network, where N is the set of all nodes, and
Et ⊆ {(i, j) : i, j ∈ N } is the set of all edges at time t. We assume that each node represents one agent
and that two agents i ∈ N and j ∈ N can communicate with each other at time t if and only if
(i, j) ∈ Et . As such, at each time step, each agent executes an individual action based on both the
local information and the message sent from its neighbors, with the joint goal of maximizing the
average rewards of all agents over the network. We refer to this protocol as networked multi-agent
reinforcement learning, which is presented in §2.2 in precise terms. This framework of networked
architecture finds a broad range of applications in practical multi-agent systems, such as unmanned
vehicles (Fax and Murray, 2004), robotics (Corke et al., 2005), power grid (Callaway and Hiskens,
2011), and mobile sensor networks (Cortes et al., 2004).
With only local reward and action, classical reinforcement learning algorithms can hardly
maximize the networked-wide averaged reward determined by the joint actions of all agents. To
resolve this problem, we propose two decentralized actor-critic algorithms for networked multiagent systems, based on a novel policy gradient theorem for MARL. Specifically, the actor step is
performed individually by each agent without the need to infer the policies of others. For the critic
step, on the other hand, each agent shares its estimate of the value function with its neighbors on
the network, so that a consensual estimate is achieved, which is further used in the subsequent
actor step. In this regard, the local information at each agent is able to diffuse across the network,
making the network-wide maximum reward achievable. Our algorithms enjoy the advantages of
scalability to large population of agents, robustness against malicious attacks, and communication
efficiency, as in standard distributed/decentralized algorithms over networked systems (Nedic and
Ozdaglar, 2009; Ram et al., 2010; Agarwal and Duchi, 2011; Jakovetic et al., 2011; Tu and Sayed,

2

2012).
Furthermore, one long-standing problem in RL is to increase the scalability of algorithms with
high dimensional state-action spaces. The problem becomes more pronounced in MARL since
the number of joint actions grows exponentially with the number of agents in the system. To
handle this exponential growth, we approximate both the policy and value functions by some
parametrized function classes, such as deep neural networks. Thus, combining the decentralized
network architecture and function approximation, our algorithms can be readily applied to largescale MARL problems where both the number of states and the number of agents are massive. More
importantly, we show that our algorithms converge when linear function approximation is used,
which provides theoretical support for the proposed MARL framework with networked agents.
Main Contribution. Our contribution in this work is three-fold. First, we formulate the fully
decentralized MARL problem for networked agents, and prove a version of the policy gradient
theorem adapted to this setting. Second, we propose two decentralized actor-critic algorithms with
function approximation, which enable our approach to be applied to large-scale MARL problems.
Third, in the special case of where linear function approximation is used, we establish convergence
guarantees for the proposed algorithms. It appears that this is the first class of fully decentralized
MARL algorithms for networked agents with function approximation, with provable convergence
guarantees.
Related Work. Our algorithms belong to the class of actor-critic algorithms. There is a huge body
of literature on single-agent actor-critic algorithms, which are based on the policy gradient theorem
(Baxter and Bartlett, 2000). The first actor-critic algorithm has been introduced in Sutton et al.
(2000); Konda and Tsitsiklis (2000), which have also studied the convergence of the algorithm with
linear function approximation. Later, Kakade (2002) has proposed to update the policy function
using natural gradient descent (Amari, 1998), which leads to the natural actor-critic algorithm
(Peters and Schaal, 2008). Convergence of actor-critic and natural actor-critic algorithms with linear
function approximation have been studied in Bhatnagar et al. (2009, 2008); Castro and Meir (2010);
Bhatnagar (2010). Recently, for deep reinforcement learning, where deep neural networks are
used for function approximation, various actor-critic algorithms have been proposed. For example,
Gruslys et al. (2017); Wang et al. (2016); Gu et al. (2017) have proposed sample-efficient actor-critic
algorithms based on experience replay (Mnih et al., 2015) and off-policy learning (Munos et al.,
2016). In addition, for continuous action spaces, Silver et al. (2014); Lillicrap et al. (2016) have
proposed actor-critic algorithms based on deterministic policies. A more related and popular work
is Mnih et al. (2016), which has proposed the asynchronous actor-critic (A3C) algorithm. Unlike
our MARL framework, the A3C algorithm essentially deals with single-agent RL but with multiple
parallel workers/processors, where no control interaction occurs among the workers. Moreover, a
central controller is required to coordinate the asynchronous update of the workers. In contrast,
our actor-critic algorithms are built upon a version of policy gradient theorem for MARL, with no
central controller required in implementation.
A line of research more relevant to our work here is on MARL. Most existing work on MARL
is based on the framework of Markov games, which was first proposed by Littman (1994) and
then followed by Littman (2001); Lauer and Riedmiller (2000); Hu and Wellman (2003). This
framework applies to the setting with both collaborative and competitive relationships among
agents. However, these early algorithms have been developed only for tabular cases where no
function approximation is used. Moreover, for the collaborative setting considered here, notably
3

team games, references Wang and Sandholm (2003); Arslan and Yüksel (2017) take the reward
of all agents to be identical, which greatly simplifies the problem since the value function can
be estimated locally with no need of information exchange among agents. More recently, several
MARL algorithms using deep neural networks as function approximators have gained increasing
attention (Foerster et al., 2016; Gupta et al., 2017; Lowe et al., 2017; Omidshafiei et al., 2017;
Foerster et al., 2017). However, most of them focus on showing empirical results, without much
convergence guarantees. Moreover, none of them have been designed for our MARL framework
with networked agents, where the communication among agents may contribute toward the overall
performance of MARL in a fully decentralized setting. See §C for a detailed comparison with
existing MARL models and algorithms.
Since we assume the reward functions of the agents to be possibly different, which might
correspond to various different tasks, our work is also pertinent to the literature on multi-task
reinforcement learning (Wilson et al., 2007; Parisotto et al., 2015; Teh et al., 2017), which focuses
on scenarios where a single-agent solves multiple related MDP problems. Common knowledge
is distilled and transferred among the training of policies for different tasks. Although multiple
workers can be used to learn different policies by sharing knowledge with each other (Teh et al.,
2017), the workers solve relevant but independent MDPs, where the workers do not interact with
each other as opposed to our framework. In fact, we consider multiple agents to be heterogeneous
with distinct policies and rewards, while some multi-task RL algorithms rely heavily on the
assumption that the polices of various tasks are similar to a great extent.
Notation. For any vector x ∈ Rn and matrix Y ∈ Rm×n , we use kxk and kY k to denote the Euclidean
norm of x and the induced 2-norm of Y , respectively. We also use kxk∞ and kY k∞ to denote the
infinite norm of x and the induced infinite-norm of Y , respectively. For a finite set A, we use |A|
P
to denote its cardinality. For notational simplicity, we use limt , supt , and t to represent limt→∞ ,
P
supt→∞ , and t≥0 , respectively. For any two numbers a and b, we write a  b if a is much smaller
than b. If not otherwise specified, we denote by I and 1 the identity matrix and all-one vector of
proper dimensions, respectively. We also use [N ] to denote the set of integers {1, · · · , N } and N to
denote the set of non-negative integers.
Roadmap. In §2 we first provide the background material on reinforcement learning, and then
formulate the networked multi-agent MDP to be studied in this work. We present two decentralized
actor-critic algorithms for fully decentralized MARL problems in §3 and provide theoretical
convergence guarantees in §4 when linear function approximation is applied. Proofs of the main
results are given in §5. Experiments with linear function approximation are presented in §6 to
back up our theory.

2

Background

In this section, we introduce the background and formulation of the networked multi-agent
reinforcement learning problem.

2.1

Markov Decision Process and Actor-critic Algorithm

A Markov decision processes is characterized by a quadruple M = hS, A, P , ri, where S is a finite
state space, A is a finite action space, P (s0 | s, a) : S × A × S → [0, 1] is a state transition probability
4

from state s to s0 determined by action a, and R(s, a) : S × A → R is a reward function defined
by R(s, a) = E[rt+1 | st = s, at = a], with rt+1 being the instantaneous reward at time t. Policy of the
agent is a mapping π : S × A → [0, 1], representing the probability of choosing action a at state s.
The objective of the agent is to find the optimal policy that maximizes the expected time-average
reward, notably, long-term return, which is given by J(π):
T −1
X
X
1X
J(π) = lim
E(rt+1 ) =
dπ (s)
π(s, a)R(s, a),
T
T
t=0

s∈S

(2.1)

a∈A

where dπ (s) = limt P(st = s | π) is the stationary distribution of the Markov chain under policy π.
Note that the distribution dπ (s) and the limit in (2.1) are well defined under the assumption that
with any policy π, the Markov chain resulting from the MDP is irreducible and aperiodic.
Given any policy π, the relative action-value associated with a state-action pair (s, a) is thus
defined as (Sutton and Barto, 1998; Puterman, 2014)
X
Qπ (s, a) =
E[rt+1 − J(π) | s0 = s, a0 = a, π].
t

Accordingly, the relative state-value associated with state s under policy π can be defined as
P
Vπ (s) = a∈A π(s, a)Qπ (s, a). For simplicity, we will hereafter refer to Vπ and Qπ (s, a) as state-value
function and action-value function, respectively. When the state and action space is massively large,
Vπ and Qπ (s, a) are usually approximated by some parametrized functions Q(·, ·; ω) and V (·; v),
respectively, with parameters ω and v. The policy π can also be parametrized as πθ . For notational
convenience, hereafter we denote all πθ in the subscript of other symbols as θ, e.g., we write dπθ
and Vπθ as dθ and Vθ , respectively.
Under this parameterization, actor-critic (AC) algorithms have been advocated to solve for the
optimal policy πθ . In particular, the actor-critic algorithms are based on the well-known policy
gradient theorem (Sutton et al., 2000), where the gradient of the return J(θ) with respect to the
policy parameter θ can be written as
∇θ J(θ) = Es∼dθ ,a∼πθ {∇θ log πθ (s, a) · [Qθ (s, a) − b(s)]} .
The term b(s) is usually referred to as the baseline, and ∇θ log πθ is referred to as the score function
of the policy πθ . It has been recognized in Bhatnagar et al. (2008) that the minimum variance
baseline in the action-value function estimator corresponds to the state-value function Vθ (s). Let
Aθ (s, a) = Qθ (s, a) − Vθ (s)

(2.2)

be the advantage function. At time step t, define Qt (ω) = Q(st , at ; ω) and let At be the sample of the
advantage function, i.e.,
X
At = Q(st , at ; ωt ) −
πθt (st , a)Q(st , a; ωt )
a∈A

Let ψt = ∇θ log πθt (st , at ) represent the sample of the score function. As such, one common AC
algorithm based on action-value function approximation has the following form
µt+1 = (1 − βω,t ) · µt + βω,t · rt+1 ,

ωt+1 = ωt + βω,t · δt · ∇ω Qt (ωt ),
5

θt+1 = θt + βθ,t · At · ψt ,

(2.3)

where βω,t , βθ,t > 0 are stepsizes, µt tracks the unbiased estimate of the average return, and
δt = rt+1 − µt + Q(st+1 , at+1 ; ωt ) − Q(st , at ; ωt )
denotes the action-value temporal difference (TD) error. Note that the action at+1 is sampled from
the policy πθt (st+1 , ·). The AC algorithm is usually developed as a two-time-scale algorithm, by
−1
setting the stepsizes βω,t and βθ,t following limt βθ,t · βω,t
= 0. Thus the first two updates in (2.3),
referred to as the critic step, operate at a faster time scale to estimate the action-value function
Q(st , at ; ωt ) under policy πθt . The last update in (2.3), on the other hand, corresponds to the
so-called actor step, which improves the policy along the gradient ascent direction at a slower time
scale.
Furthermore, actor-critic algorithms are shown to achieve state-of-art performances in many
complicated application domains (Peters and Schaal, 2008; Schulman et al., 2015; Mnih et al., 2016;
Bahdanau et al., 2016; Silver et al., 2017). Driven by these success stories, we focus on designing
actor-critic algorithms for MARL over networks in the present work.

2.2

Multi-Agent Reinforcement Learning

Consider now a system of N agents operating in a common environment, denoted by N = [N ]. We
are interested in the decentralized setting where no central controller exists in the system that
either collects rewards or makes the decisions for the agents. Instead, the agents are located on a
possibly time-varying communication network, denoted by Gt = (N , Et ), where Et represents the
set of communication links at time t ∈ N. In other words, Gt is a time-varying and undirected
graph with vertex set N and edge set Et ⊆ {(i, j) : i, j ∈ N , i , j} at time t, where an edge (i, j) ∈ Et
means that agents i and j can share information at time t 1 . We define the multi-agent MDP over
communication networks in detail as follows, which is a natural extension of classical MDP to the
decentralized multi-agent network.
Definition 2.1 (Networked Multi-Agent MDP). Let {Gt = (N , Et )}t≥0 be a time-varying communication network with N agents. A networked multi-agent MDP is characterized by a tuple
(S, {Ai }i∈N , P , {Ri }i∈N , {Gt }t≥0 ) where S is the global state space shared by all the agents in N , and
Q
i
Ai is the set of actions that agent i can execute. In addition, let A = N
i=1 A be the joint action space
of all agents. Then, Ri : S × A → R is the local reward function of agent i, and P : S × A × S → [0, 1]
is the state transition probability of the MDP. Moreover, we assume that the states and the joint
actions are globally observable whereas the rewards are observed only locally.
In view of this definition, at time step t, suppose that the global state is st ∈ S and the agents
i
execute joint actions at = (a1t , . . . , aN
t ) ∈ A. As a result, each agent i ∈ N receives a reward rt+1 ,
which is a random variable with expected value Ri (st , at ). Moreover, the MDP shifts to a new state
st+1 ∈ S with probability P (st+1 | st , at ). We say our model is fully decentralized since both the reward
is received locally and the action is executed locally by each agent.
Furthermore, since each agent chooses its own action individually at each time, it is reasonable
to assume that their choices of actions are conditionally independent given the current state. More
specifically, let π : S × A → [0, 1] be a joint policy function, that is, π(s, a) is the probability of
Q
choosing action a at state s. We assume that π(s, a) = i∈N πi (s, ai ), where πi (s, ai ) is the probability
1 Here we treat (i, j) and (j, i) as the same, which represent the edge between nodes i and j.

6

that agent i selects action ai ∈ Ai at state s. In other words, the joint policy π can be factorized
as the product of local policies {πi : S × Ai → [0, 1]}i∈N , i.e., the randomized actions picked by
different agents are statistically independent.
Moreover, when the state space S is large, it is useful to consider policies that are in a parametric
function class. For any agent i, we assume that the local policy is given by πθi i , where θ i ∈ Θ i
is the parameter, and Θ i ⊆ Rmi is a compact set. We pack the parameters together by writing
Q
i
θ = [(θ 1 )> , · · · , (θ N )> ]> ∈ Θ, where Θ = N
i=1 Θ . Then the joint policy is given by πθ (s, a) =
Q
i
i∈N πθ i (s, ai ). In the following, we make an regularity assumption on the networked MDP and
policy function, which is standard in the literature.
Assumption 2.2. We assume that for any i ∈ N , s ∈ S, and ai ∈ Ai , the policy function πθi i (s, ai ) > 0
for any θ i ∈ Θ i . Also, πθi i (s, ai ) is continuously differentiable with respect to the parameter θ i over
Θ i . In addition, for any θ ∈ Θ, let P θ be the transition matrix of the Markov chain {st }t≥0 induced
by policy πθ , that is,
X
P θ (s0 | s) =
πθ (s, a) · P (s0 | s, a), ∀s, s0 ∈ S.
(2.4)
a∈A

We assume that the Markov chain {st }t≥0 is irreducible and aperiodic under any πθ .
Assumption 2.2 is standard in the early work on AC algorithms with function approximation
(Konda and Tsitsiklis, 2000; Bhatnagar et al., 2009). It is assumed that the policy πθ (·, ·) is continuously differentiable with respect to θ, which is required by policy gradient methods and is satisfied
by well-known function classes such as deep neural networks. Moreover, since the Markov chain
induced by πθ is irreducible and aperiodic, it has a stationary distribution of dθ (s) over S. Likewise,
the Markov chain of the state-action pair {(st , at )}t≥0 has a stationary distribution dθ (s) · πθ (s, a) for
any s ∈ S and a ∈ A.
In addition, the joint objective of the agents is to collaboratively find a joint policy πθ that
maximizes the globally averaged long-term return over the network based solely on local information.
i
Recall that at time t, agent i receives reward rt+1
and the reward function of agent i is given by
i
R (·, ·). Then our goal is to solve the optimization problem
! X
T −1
X
1 X1 X i
maximize J(θ) = lim
E
rt+1 =
dθ (s)
πθ (s, a) · R(s, a),
T
T
N
θ
t=0

i∈N

s∈S

(2.5)

a∈A

P
P
where R(s, a) = N −1 · Ri (s, a) is the globally averaged reward function. Let r t = N −1 · i∈N rti ;
then, we have R(s, a) = E[r t+1 | st = s, at = a]. Accordingly, the global expected action value function
associated with a state-action pair (s, a) under policy πθ becomes
X h
i
Qθ (s, a) =
E r t+1 − J(θ) | s0 = s, a0 = a, πθ .
(2.6)
t

P
Moreover, the global state-value function Vθ (s) is defined as Vθ (s) = a∈A πθ (s, a)Qθ (s, a) accordingly.
This framework of networked multi-agent systems finds a broad range of applications in
distributed cooperative control problems, including formation control of unmanned vehicles (Fax
and Murray, 2004), cooperative navigation of robots (Corke et al., 2005), load management in
7

energy networks (Callaway and Hiskens, 2011), and flocking of mobile sensor networks (Cortes
et al., 2004), etc. However, most of the existing work on networked cooperative multi-agent systems
is approached in a static setting, in the sense that the optimization objective is deterministic and
there is no control input affecting the transition of the system, see efforts in Nedic and Ozdaglar
(2009); Ram et al. (2010); Agarwal and Duchi (2011); Jakovetic et al. (2011); Tu and Sayed (2012).
Our framework extends the above to a dynamic setting by explicitly modeling an MDP involving
networked agents with only local sensing and control capabilities.

3

Multi-Agent Actor-Critic with Networked Agents

In this section, we present the proposed actor-critic algorithms for the multi-agent MDP with
networked agents. We first establish a policy gradient theorem for MARL, which characterizes the
gradient of J(θ) defined in (2.5) in closed form.
Theorem 3.1 (Policy Gradient Theorem for MARL). For any θ ∈ Θ, let πθ : S × A → [0, 1] be a
policy and let J(θ) be the globally long-term averaged return defined in (2.5). In addition, let Qθ
and Aθ be the action-value function and advantage function defined in (2.6) and (2.2), respectively.
Moreover, for any i ∈ N , we define the local advantage function Aiθ : S × A → R as
X
ei (s, a−i ), where V
ei (s, a−i ) =
Aiθ (s, a) = Qθ (s, a) − V
πθi i (s, ai ) · Qθ (s, ai , a−i ).
(3.1)
θ
θ
ai ∈Ai

Here we denote by a−i the actions of all agents except for i. Recall that θ = [(θ 1 )> , . . . , (θ N )> ]> .
Then the gradient of J(θ) with respect to θ i is given by
h
i
h
i
∇θ i J(θ) = Es∼dθ ,a∼πθ ∇θ i log πθi i (s, ai ) · Qθ (s, a) = Es∼dθ ,a∼πθ ∇θ i log πθi i (s, ai ) · Aθ (s, a)
h
i
= Es∼dθ ,a∼πθ ∇θ i log πθi i (s, ai ) · Aiθ (s, a) .
(3.2)
Proof. The proof of this theorem follows the proof of the policy gradient theorem in single-agent
reinforcement learning (Sutton et al., 2000), which implies that
∇θ J(θ) = Es∼dθ ,a∼πθ [∇θ log πθ (s, a) · Qθ (s, a)]
" X
#
X
X
i
i
=
dθ (s)
πθ (s, a) ∇θ
log πθ i (s, a ) · Qθ (s, a),
s∈S

a∈A

(3.3)

i∈N

where Qθ is the action-value function defined in (2.6), and dθ denotes the stationary distribution of
the Markov chain induced by policy πθ . Here the second equality in (3.3) holds because πθ is the
product of local policy functions. Hence, the gradient with respect to each parameter θ i becomes
X
X
∇θ i J(πθ ) =
dθ (s)
πθ (s, a) · ∇θ i log πθi i (s, ai ) · Qθ (s, a),
(3.4)
s∈S

a∈A

P
which proves the first equality in (3.2). Moreover, since ai ∈Ai πθi i (s, ai ) = 1, we have
"X
#
i
i
∇θ i
πθ i (s, a ) = 0.
ai ∈Ai

8

(3.5)

To simplify the notation, for each i ∈ N , we define a−i as the joint actions of all agents except i, and
Q
let A−i = j,i Aj . Thus, for any function F : S × A−i → R which does not rely on ai , by (3.5), for any
s ∈ S we have
X
h
i
πθ (s, a) · ∇θ i log πθi i (s, ai ) · F(s, a−i )
a∈A

=

X
a−i ∈A−i

−i

F(s, a ) ·

 Y

j
πθ j (s, aj )

j∈N ,j,i

 X

i
i
·
∇θ i πθ i (s, a ) = 0.

(3.6)

ai ∈Ai

ei defined in (3.1) and combined
Thus, replacing F in (3.6) by the value function Vθ and function V
θ
with (3.4), we establish (3.2), which concludes the proof.
Theorem 3.1 shows that the policy gradient with respect to each θ i can be obtained locally using
the corresponding score function ∇θ i log πθi i , provided that agent i has an unbiased estimate of the
global action-value or advantage functions. However, with only local information, these functions
cannot be well estimated since they require the rewards {rti }i∈N of all agents. This motivates our
consensus-based MARL algorithms that leverage the communication network to diffuse the local
information, which fosters collaboration among the agents.

3.1

Algorithms

Now we are ready to develop actor-critic algorithms for networked multi-agent systems. We first
propose an algorithm based on the local advantage function Aiθ defined in (3.1), which requires
estimating the action-value function Qθ of policy πθ . More specifically, let Q(·, ·; ω) : S × A → R be
a family of functions parametrized by ω ∈ RK , where K  |S| · |A|. We assume that each agent i
maintains its own parameter ωi and uses Q(·, ·; ωi ) as a local estimate of Qθ . Moreover, since Qθ in
(2.6) involves the globally averaged reward r t , to aggregate the local information, we let each agent
i share the local parameter ωi with its neighbors on the network, in order to reach a consensual
estimate of Qθ . In this way, each agent is able to improve the current policy via the policy gradient
theorem.
Specifically, the actor-critic algorithm consists of two steps that proceed at different time scales.
In the critic step, the update resembles the action-value TD-learning for policy evaluation in (2.3),
followed by a linear combination of its neighbor’s parameter estimates. Such a parameter sharing
step is also known as the consensus update, which involves a weight matrix Ct = [ct (i, j)]N ×N , where
ct (i, j) is the weight on the message transmitted from i to j at time t The construction of Ct depends
on the network topology of Gt ; see §4.1 for details. Thus, the critic step iterates as follows
X
j
i
i
eti = ωti + βω,t · δti · ∇ω Qt (ωti ), ωt+1
et ,
µit+1 = (1 − βω,t ) · µit + βω,t · rt+1
, ω
=
ct (i, j) · ω
(3.7)
j∈N

where µit tracks the long-term return of agent i, βω,t > 0 is the stepsize, and we let Qt (ω) = Q(st , at ; ω)
for any ω ∈ RK . Moreover, the local TD-error δti in (3.7) is computed as
i
δti = rt+1
− µit + Qt+1 (ωti ) − Qt (ωti ).

(3.8)

As for the actor step, motivated by (3.2) in Theorem 3.1, each agent i improves its policy via
i
θt+1
= θti + βθ,t · Ait · ψti ,

9

(3.9)

Algorithm 1 The networked actor-critic algorithm based on action-value function
e0i , θ0i , ∀i ∈ N ; the initial state s0 of the MDP, and
Input: Initial values of the parameters µi0 , ω0i , ω
stepsizes {βω,t }t≥0 and {βθ,t }t≥0 .
Each agent i ∈ N executes action ai0 ∼ πθi i (s0 , ·) and observes joint actions a0 = (a10 , . . . , aN
0 ).
0

Initialize the iteration counter t ← 0.
Repeat:
for all i ∈ N do
i
Observe state st+1 , and reward rt+1
.
i
i
i
Update µt+1 ← (1 − βω,t ) · µt + βω,t · rt+1
.
Select and execute action ait+1 ∼ πθi i (st+1 , ·).
t
end for
Observe joint actions at+1 = (a1t+1 , . . . , aN
t+1 ).
for all i ∈ N do
i
Update δti ← rt+1
− µit + Qt+1 (ωti ) − Qt (ωti ).
i
et ← ωti + βω,t · δti · ∇ω Qt (ωti ).
Critic step: ω
P
Update Ait ← Qt (ωti ) − ai ∈Ai πθi i (st , ai ) · Q(st , ai , a−i ; ωti ),
t

ψti ← ∇θ i log πθi i (st , ait ).
t

i
Actor step: θt+1
← θti + βθ,t · Ait · ψti .
eti to the neighbors {j ∈ N : (i, j) ∈ Et } over the communication network Gt .
Send ω
end for
for all i ∈ N do
P
j
i
et .
Consensus step: ωt+1
← j∈N ct (i, j) · ω
end for
Update the iteration counter t ← t + 1.
Until Convergence

where βθ,t > 0 is the stepsize. Moreover, Ait and ψti are defined as
X
i
i
i
i
Ait = Qt (ωti ) −
πθi i (st , ai ) · Q(st , ai , a−i
t ; ωt ), ψt = ∇θ i log πθ i (st , at ),
ai ∈Ai

t

t

(3.10)

where the updating rule for Ait follows from the definition of Aiθ in (3.1).
The update in (3.7) for ωti resembles the so-termed diffusion update in Tu and Sayed (2012);
Chen and Sayed (2012) for solving distributed optimization/estimation problems. However, it
differs in two main aspects: i) the update direction δti · ∇ω Qt (ωti ) is not the stochastic gradient
direction of any well-defined objective function, thus the update is not equivalent to solving any
distributed optimization problem; ii) diminishing stepsizes are adopted for possibly almost sure
convergence, whereas mean square convergence was established in Tu and Sayed (2012); Chen and
Sayed (2012). Thus the proof techniques there do not apply to the analysis of the update in (3.7).
We instead resort to the machinery of stochastic approximation for analyzing the convergence of
the update under certain assumptions. Moreover, we note that the updates (3.7)-(3.9) preserve
the privacy of agents in the sense that no information about the individual reward function or the
policy is required for such network-wide collaboration, which inherits one of the advantages of
fully decentralized algorithms. We present the steps of this algorithm in Algorithm 1.
For online implementation of Algorithm 1, the joint actions at+1 is needed to evaluate the
10

action-value TD-error δti . Thus, at time t, each agent updates the critic in (3.7) using (st , at , st+1 , at+1 ).
Moreover, since agent i also needs to store the estimates ωti ∈ RK and θti ∈ Rmi , the total memory
complexity of agent i is O(N + mi + K). On the contrary, in the tabular case, each agent i need to
Q
maintain a Q-table of dimension |S| · |A| × |S| · |A| as in Kar et al. (2013), where |A| = i∈N |Ai | grows
exponentially with the number of agents N in the system.
Note that Algorithm 1 requires action at+1 to compute the update at time t. In the following,
we propose an algorithm which only uses the transition at time t, namely, the sample (st , at , st+1 ),
for parameter update. In fact, one can estimate the advantage function Aθ with the state-value
TD-error, since the latter is an unbiased estimate of the former, i.e.,
h
i
E r t+1 − J(θ) + Vθ (st+1 ) − Vθ (st ) st = s, at = a, πθ = Aθ (s, a), for any s ∈ S, a ∈ A.
(3.11)
To this end, we first estimate J(θ) and Vθ with a scalar µ and a parametrized function V (·; v) : S → R,
respectively, where parameter v ∈ RL with L  |S|. Similar to Algorithm 1, each agent i maintains
and shares local parameters µi and v i following the updates
X
j
i
eit = (1 − βv,t ) · µit + βv,t · rt+1
et ,
µ
,
µit+1 =
ct (i, j) · µ
(3.12)
j∈N

δti

i
= rt+1
− µit

+ Vt+1 (vti ) − Vt (vti ),

veti

= vti

+ βv,t · δti

· ∇v Vt (vti ),

i
vt+1
=

X
j∈N

j

ct (i, j) · vet ,

(3.13)

where we denote Vt (v) = V (st ; v) for any v ∈ RL , and βv,t > 0 is the stepsize. With slight abuse of
notation, we use δti to denote the state-value TD-error of agent i. Note that the local δti can be used
to evaluate the state-value function as for the action-value function evaluation in Algorithm 1.
However, it cannot be used directly to estimate the policy gradient following (3.11), since the local
i
rt+1
is not sampled from the globally averaged reward R.
Accordingly, we propose to estimate the globally averaged reward function R in the critic step
as well. Specifically, let R(·, ·; λ) : S × A → R be the class of parametrized functions, where λ ∈ RM
is the parameter with M  |S| · |A|. To obtain the estimate R(·, ·; λ) at the faster time scale, we seek
to minimize the following weighted mean-square error
X
i2
h
(3.14)
minimize
dθ (s) · πθ (s, a) R(s, a; λ) − R(s, a) ,
λ

s∈S,a∈A

P

where recall that R(s, a) = i∈N Ri (s, a) · N −1 and dθ (s) is the stationary distribution of the Markov
chain {st }t≥0 under policy πθ . The optimization problem (3.14) can be equivalently characterized
as
X X
h
i2
minimize
dθ (s) · πθ (s, a) R(s, a; λ) − Ri (s, a) ,
(3.15)
λ

i∈N s∈S,a∈A

since the two objectives have identical stationary points. The objective (3.15) has the same form of
separable objectives over agents as in the distributed optimization literature (Tsitsiklis et al., 1986;
Nedic and Ozdaglar, 2009; Boyd et al., 2011; Chen and Sayed, 2012). This connection motivates
the following updates for λit to minimize the objective (3.15)
X
i
eit = λit + βv,t · [r i − Rt (λit )] · ∇λ Rt (λit ),
ej ,
λ
λ
=
ct (i, j) · λ
(3.16)
t
t+1
t+1
j∈N

11

Algorithm 2 The networked actor-critic algorithm based on state-value TD-error
ei , θ i , ∀i ∈ N ; the initial state s0 of the MDP, and
ei0 , v0i , ve0i , λi0 , λ
Input: Initial values of µi0 , µ
0
0
stepsizes {βv,t }t≥0 and {βθ,t }t≥0 .
Each agent i implements ai0 ∼ πθ i (s0 , ·).
0
Initialize the step counter t ← 0.
Repeat:
for all i ∈ N do
i
Observe state st+1 , and reward rt+1
.
i
i
i
ei ← λi + βv,t · [r i − Rt (λi )] · ∇λ Rt (λi ).
et ← (1 − βv,t ) · µt + βv,t · rt+1 , λ
Update µ
t
t
t
t
t+1
i
i
i
i
i
Update δt ← rt+1 − µt + Vt+1 (vt ) − Vt (vt )
Critic step: veti ← vti + βv,t · δti · ∇v Vt (vti ).
Update δeti ← Rt (λit ) − µit + Vt+1 (vti ) − Vt (vti ), ψti ← ∇θ i log πθi i (st , ait ).
t
i
Actor step: θt+1
= θti + βθ,t · δeti · ψti .
ei , vei to the neighbors over Gt .
eit , λ
Send µ
t t
end for
for all i ∈ N do
P
P
j
j
ej , v i ← P
Consensus step: µit+1 ← j∈N ct (i, j)·e
µt , λit+1 ← j∈N ct (i, j)·λ
vt .
j∈N ct (i, j)·e
t
t+1
end for
Update the iteration counter t ← t + 1.
Until Convergence
where Rt (λ) = R(st , at ; λ) for any λ ∈ RM . The update in (3.16) forms the critic step together with
(3.12) and (3.13). We note that the rewards of other agents are not transmitted directly to each
agent, and the estimate R(·, ·; λ) can not recover the individual reward function of others. Hence,
the consensual estimate of globally averaged reward function does not harm the privacy of agents
on their rewards and policies as in Algorithm 1.
Unlike most existing work in distributed optimization, the samples obtained to estimate the
gradient of (3.15) are correlated by the Markov chain {(st , at )}t≥0 under policy πθ . We will also
resort to stochastic approximation to analyze the convergence of this update.
The estimate R(·, ·; λit ) is then used to evaluate the globally averaged TD-error δeti . Accordingly,
the actor step motivated by (3.11) becomes
δeti = Rt (λit ) − µit + Vt+1 (vti ) − Vt (vti ),

i
θt+1
= θti + βθ,t · δeti · ψti .

(3.17)

where βθ,t > 0 is the stepsize and ψti is as defined in (3.10). The steps of this algorithm are given
in Algorithm 2. Similar to Algorithm 1, the online implementation of Algorithm 2 requires the
memory complexity of O(N + L + M + mi ) for each agent i, which results in a great reduction in
contrast to the tabular case when N is large.
Note that both algorithms are applicable to general function approximators including deep
neural networks. In addition, when linear approximation is applied, we provide convergence
guarantees in §4.

12

4

Theoretical Results

In this section, we establish theoretical results for the proposed algorithms. Specifically, with linear
function approximation, we show the convergence of both Algorithms 1 and 2, with complete
proofs relegated to the next section. We start with the following three assumptions which apply to
both algorithms.
Assumption 4.1. The update of the policy parameter θti includes a local projection operator,
Q
i
Γ i : Rmi → Θ i ⊂ Rmi , that projects any θti onto a compact set Θ i . Also, we assume that Θ = N
i=1 Θ
is large enough to include at least one local minimum of J(θ).
This projection is a common technique for stabilizing the transient behavior of stochastic
approximation algorithms (Kushner and Yin, 2003). It has been a standard assumption in many
analyses for two-time-scale reinforcement learning algorithms (Abounadi et al., 2001; Bhatnagar
et al., 2009; Degris et al., 2012; Prasad et al., 2014). Note that this projection is merely for analysis
purposes and may not be necessary when updating θ i in experiments, as we will illustrate later.
Assumption 4.2. The instantaneous reward rti is uniformly bounded for any i ∈ N and t ≥ 0.
We remark that the boundedness assumption on the rewards is rather mild, which is readily
satisfied in practical MDP models with finite state and action spaces.
Furthermore, we make the following assumption on the weight matrix {Ct }t≥0 for the consensus
updates in both algorithms.
Assumption 4.3. The sequence of nonnegative random matrices {Ct }t≥0 ⊆ RN ×N satisfies

(a.1) Ct is row stochastic and E(Ct ) is column stochastic. That is, Ct 1 = 1 and 1> E(Ct ) = 1> .
Furthermore, there exists a constant η ∈ (0, 1) such that, for any ct (i, j) > 0, we have ct (i, j) ≥ η.
(a.2) Ct respects the communication graph Gt , i.e., ct (i, j) = 0 if (i, j) < Et .

>
(a.3) The spectral norm of E[C>
t · (I − 11 /N ) · Ct ] is strictly smaller than one.

(a.4) Given the σ -algebra generated by the random variables before time t, Ct is conditionally
i
independent of rt+1
for any i ∈ N .
We take the matrix Ct to be random for the sake of generality. The randomness can be attributed
to either the randomness of the time-varying graph Gt , e.g., random link failures in sensor networks
(Kar and Moura, 2010), or the randomness of the consensus algorithms, e.g., randomized gossip
schemes (Boyd et al., 2006). The condition (a.1) is standard in developing consensus algorithms,
which guarantees convergence of the update for each agent to a common vector. As noted in Bianchi
et al. (2013), the matrix Ct here is only required to be column stochastic in mean, as opposed to
most other gossip or consensus algorithms that require Ct to be doubly stochastic2 . Note that row
stochasticity constraint Ct 1 = 1 is local, since it simply requires each agent to make the weights
assigned to the updates coming from its neighbors summing to one. The lower boundedness of
the weights is needed to ensure that the limit limt Ct Ct−1 · · · C0 exists (Nedic and Ozdaglar, 2009),
which is required in the proof of the stability of the consensus update (see Appendix §A). The
conditions (a.2) and (a.3) are related to the connectivity of the communication network Gt . It
follows from Boyd et al. (2006); Aysal et al. (2009) that for the gossip type of communication
2 A stochastic matrix P is doubly stochastic if it is both row and column stochastic.

13

schemes, (a.3) holds if and only if the underlying communication graph is connected. See Nedich
et al. (2016) for more discussion on the connection between the spectrum property (a.3) and the
connectivity of time-varying graphs. The condition (a.4) means that Ct and rt+1 are independent
conditioned on the past. This is common for practical multi-agent systems, since the random
communication link failures and the gossip schemes are usually independent of the past history
and irrelevant to the rewards received by the agents.
One particular choice of the weights in Ct that relies on only local information of the agents is
known as Metropolis weights (Xiao et al., 2005; Cattivelli et al., 2008)
X
n
o−1
ct (i, j) = 1 + max[dt (i), dt (j)] , ∀(i, j) ∈ Et ,
ct (i, i) = 1 −
ct (i, j), ∀i ∈ N ,
j∈Nt (i)

where Nt (i) = {j ∈ N : (i, j) ∈ Et } is the set of neighbors of agent i at time t, and dt (i) = |Nt (i)| is the
degree of agent i. Other common choices of Ct that satisfy the conditions (a.1)-(a.3) in Assumption
4.3 include pairwise gossip (Boyd et al., 2006), broadcast gossip (Aysal et al., 2009), and network
dropouts (Bianchi et al., 2013).

4.1

Convergence of Algorithm 1

To show the convergence of Algorithm 1, we make the following additional assumptions on the
value functions and the stepsizes.
Assumption 4.4. For each agent i, the action-value function is parametrized by the class of linear
functions, i.e., Q(s, a; ω) = ω> φ(s, a) where φ(s, a) = [φ1 (s, a), · · · , φK (s, a)]> ∈ RK is the feature associated with the state-action pair (s, a). The feature vectors φ(s, a) are uniformly bounded for any
s ∈ S, a ∈ A. Furthermore, the feature matrix Φ ∈ R|S|·|A|×K has full column rank, where the k-th
column of Φ is [φk (s, a), s ∈ S, a ∈ A]> for any k ∈ [K]. Also, for any u ∈ RK , Φu , 1.
We focus here on the version of Algorithm 1 with linear function approximation for the purpose
of theoretical analysis. Note that the TD-learning-based policy evaluation with nonlinear function
approximation may fail to converge (Tsitsiklis and Van Roy, 1997). Thus, the convergence of AC
algorithms with nonlinear function approximation is not clear even for the single-agent setting. To
the best of our knowledge, all existing AC algorithms with theoretical guarantees are built upon
linear function approximation, e.g., Konda and Tsitsiklis (2000); Bhatnagar et al. (2009); Bhatnagar
(2010). The assumption on the feature matrix Φ is standard and has also been made in Tsitsiklis
and Van Roy (1997, 1999); Bhatnagar et al. (2009) to ensure that policy evaluation has a unique
asymptotically stable solution, as we will show in the proof.
We then make the assumption that the stepsizes βω,t and βθ,t satisfy the following standard
condition similar to that for single-agent AC algorithms with two-time-scale updates.
Assumption 4.5. The stepsizes βω,t and βθ,t satisfy
X
X
X
2
2
βω,t =
βθ,t = ∞,
βω,t
+ βθ,t
< ∞, βθ,t = o(βω,t ).
t

t

t

−1
In addition, limt→∞ βω,t+1 · βω,t
= 1.

For the convergence analysis of Algorithm 1, we use the two-time-scale stochastic approximation
(SA) technique (Borkar, 2008). In particular, we first analyze the convergence of the critic step
14

at the faster time scale, where the joint policy πθ is assumed to be fixed. Then we analyze the
convergence of the policy parameter θt upon the convergence of the critic step.
For notational simplicity, we define P θ (s0 , a0 | s, a) = P (s0 | s, a)πθ (s0 , a0 )3 and Ds,a
θ =Pdiag[dθ (s) ·
>
|S|·|A|
πθ (s, a), s ∈ S, a ∈ A]. Recall that R = [R(s, a), s ∈ S, a ∈ A] ∈ R
has element R(s, a) = i∈N Ri (s, a)·
Q
N −1 . Then we define the operator Tθ : R|S|·|A| → R|S|·|A| for any action-value vector Q ∈ R|S|·|A| as
Tθ (Q) = R − J(θ) · 1 + P θ Q.
Q

(4.1)

With these notations, we establish the convergence of the critic step (3.7) and (3.8) as follows.
Theorem 4.6. Under Assumptions 2.2, and 4.2-4.5, for any given policy πθ , with {µit } and {ωti }
P
generated from (3.7) and (3.8), we have limt i∈N µit · N −1 = J(θ) and limt ωti = ωθ almost surely
(a.s.) for any i ∈ N , where
X
X
J(θ) =
dθ (s)
πθ (s, a)R(s, a)
s∈S

a∈A

is the globally long-term averaged return under joint policy πθ , and ωθ is the unique solution to
h Q
i
Φ > Ds,a
T
(Φω
)
−
Φω
= 0.
(4.2)
θ
θ
θ
θ
We note that the solution to (4.2) is the limiting point of the TD(0) algorithm (Tsitsiklis and
Van Roy, 1999), except that here we approximate the action-value function Qθ rather than the
state-value function Vθ . This point is also the minimizer of the Mean Square Projected Bellman
Error (MSPBE) (Dann et al., 2014), i.e., the solution to
minimize
ω

Q

Φω − ΠTθ (Φω)

2
,
Ds,a
θ

(4.3)

where Π is the operator that projects a vector to the space spanned by the columns of Φ, and k · k2Ds,a
θ

denotes the Euclidean norm weighted by the matrix Ds,a
θ . Thus, Theorem 4.6 states that each agent
is enabled to obtain a copy of the approximation of the globally averaged action-value function,
i.e., ωti → ωθ for all i ∈ N , even with only local rewards and information exchange with neighbors.
This approximation of global value function is then adopted in the actor step to estimate the policy
gradient for each agent.
i
To show convergence of the actor step, we define the quantities Ait,θ and ψt,θ
as
X
>
i
Ait,θ = φt> ωθ −
πθi i (st , ai ) · φ(st , ai , a−i
ψt,θ
= ∇θ i log πθi i (st , ait ),
(4.4)
t ) ωθ ,
ai ∈Ai

where we denote φt = φ(st , at ). Recall that Γ i is the operator that projects any vector onto the
compact set Θ i (see Assumption 4.1). Define a vector Γ̂ i (·) as
n
o.
Γ̂ i [g(θ)] = lim Γ i [θ i + η · g(θ)] − θ i η
(4.5)
0<η→0

P

for any θ ∈ Θ and g : Θ → R i∈N mi a continuous function. In case the limit above is not unique, let
Γ̂ i [g(θ)] be the set of all possible limit points of (4.5). Then we state the convergence of Algorithm
1 with linear function approximation as follows.
3 With slight abuse of notation, the expression P θ has the same form as the transition probability matrix of the Markov
chain {st }t≥0 under policy πθ (see the definition in (2.4)). These two matrices can be easily differentiated by the context.

15

Theorem 4.7. Under Assumptions 2.2 and 4.1-4.5, the policy parameter θti obtained from (3.9)
converges almost surely to a point in the set of asymptotically stable equilibria of
h

i
i
θ̇ i = Γ̂ i Est ∼dθ ,at ∼πθ Ait,θ · ψt,θ
, for any i ∈ N .
(4.6)

Note that Theorem 4.7 is in the same spirit as the convergence results for single-agent AC
algorithms with linear function approximation (Bhatnagar et al., 2009; Bhatnagar, 2010). Since the
linear features here are not restricted to compatible features as in Tsitsiklis
and Van Roy (1997);

i
i
Sutton et al. (2000), convergence to the stationary point of Est ∼dθ ,at ∼πθ At,θ · ψt,θ
= 0 in the set Θ i
is the best one can hope for any AC algorithms with general linear function approximators, even
for the single-agent setting (Bhatnagar et al., 2009; Degris et al., 2012).
In general, since the linear function approximator has nonzero approximation error for Qθ ,
i
even the convergent term Ait,θ · ψt,θ
from the critic step may not be an unbiased estimate of ∇θ i J(θ).
In particular, the estimate of policy gradient Ait,θ · ψti satisfies


nh
i
o
i
i
Est ∼dθ ,at ∼πθ Ait,θ · ψt,θ
= ∇θ i J(θ) + Est ∼dθ ,at ∼πθ φt> ωθ − Qθ (st , at ) · ψt,θ
.

Thus, the convergent point of (4.6) corresponds to a small neighborhood of a local optimum of
J(θ), i.e, ∇θ i J(θ) = 0, provided the error term from the approximation error for the action-value
function φt> ωθ − Qθ (st , at ) is small.

4.2

Convergence of Algorithm 2

Similar to Algorithm 1, we need two additional assumptions for the convergence of Algorithm 2.
Assumption 4.8. For each agent i, the state-value function and the globally averaged reward
function are both parametrized by the class of linear functions, i.e., V (s; v) = v > ϕ(s) and R(s, a; λ) =
λ> f (s, a), where ϕ(s) = [ϕ1 (s), · · · , ϕK (s)]> ∈ RL and f (s, a) = [f1 (s, a), · · · , fM (s, a)]> ∈ RM are the
features associated with s and (s, a), respectively. The feature vectors ϕ(s) and f (s, a) are uniformly
bounded for any s ∈ S, a ∈ A. Furthermore, let the feature matrix Φ ∈ R|S|×L have [ϕ` (s), s ∈ S]> as
its `-th column for any ` ∈ [L], and the feature matrix F ∈ R|S|·|A|×M have [fm (s, a), s ∈ S, a ∈ A]> as
its m-th column for any m ∈ [M]. Then, both Φ and F have full column rank, and for any u ∈ RL ,
Φu , 1.
For convergence analysis, we focus on Algorithm 2 with linear function approximation for both
the state-value function and the globally averaged reward function.
Assumption 4.9. The stepsizes βv,t and βθ,t satisfy
X
X
X
2
2
βv,t =
βθ,t = ∞,
βv,t
+ βθ,t
< ∞, βθ,t = o(βv,t ).
t

t

t

−1
In addition, limt→∞ βv,t+1 · βv,t
= 1.
P
θ
0
0
Recall P (s | s) = a∈A P (s | s, a)πθ (s, a) defined in (2.4) and dθ (s) denote, respectively, the transition probability and stationary distribution of the Markov chain {st }t≥0 under policy πθ . Let Dsθ =
P
diag[dθ (s), s ∈ S]. Also recall that Rθ = [Rθ (s), s ∈ S]> ∈ R|S| has element Rθ (s) = a πθ (s, a)R(s, a).
We thus define the operator TθV : R|S| → R|S| for any state-value vector V ∈ R|S| as

TθV (V ) = Rθ − J(θ) · 1 + P θ V .

We now state the convergence of the critic step (3.12), (3.13), and (3.16) as follows.
16

(4.7)

Theorem 4.10. Under Assumptions 2.2, 4.2, 4.3, 4.8, and 4.9, for any given policy πθ , with {λit },
{µit }, and {vti } generated from (3.12), (3.13), and (3.16), we have limt µit = J(θ), limt λit = λθ , and
limt vti = vθ a.s. for any i ∈ N , where J(θ) is the globally averaged return under joint policy πθ , λθ
and vθ are the unique solutions to


h
i
> s
V
R
−
Fλ
=
0,
Φ
D
F> Ds,a
T
(Φv
)
−
Φv
= 0,
(4.8)
θ
θ
θ
θ θ
θ
s
respectively, where we have Ds,a
θ = diag[dθ (s) · πθ (s, a), s ∈ S, a ∈ A] and Dθ = diag[dθ (s), s ∈ S].
Similarly, the solution vθ in (4.8) is exactly the limiting point of the TD(0) algorithm as if the
rewards of all others are observable to each agent. Moreover, the solution λθ in (4.8) corresponds
to the unique minimizer of the problem (3.14) under Assumption 4.8. Both vθ and λθ are used to
i
define the TD-error δet,θ
upon the convergence of the critic step in Algorithm 2, notably,
>
i
δet,θ
= ft> λθ − J(θ) + ϕt+1
vθ − ϕt> vθ ,

(4.9)

i
where we define ft = f (st , at ) and ϕt = ϕ(st ). Recalling that ψt,θ
= ∇θ i log πθi i (st , ait ), we have the
following theorem on the convergence of Algorithm 2 with linear function approximation.

Theorem 4.11. Under Assumptions 2.2, 4.1-4.3, 4.8, and 4.9, the policy parameter θti obtained
from (3.17) converges almost surely to a point in the set of asymptotically stable equilibria of
h

i
i
i
θ̇ i = Γ̂ i Est ∼dθ ,at ∼πθ δet,θ
· ψt,θ
, for any i ∈ N .
(4.10)
i
i
Note that δet,θ
· ψt,θ
may not be an unbiased estimate of ∇θ i J(θ). In particular, we have



nh
i
o
nh
i
o
i
i
i
i
Est ∼dθ ,at ∼πθ δet,θ
· ψt,θ
= ∇θ i J(θ) + Est ∼dθ ,at ∼πθ ft> λθ − R(st , at ) ψt,θ
+ Est ∼dθ ϕt> vθ − Vθ (st ) ψt,θ
.
If the approximation errors of both functions ft> λθ − R(st , at ) and ϕt> vθ − Vθ (st ) are small, the
convergent point of (4.10) is close to the local optimum of J(θ).

5

Proofs of the Main Results

In this section, we provide the proofs of the convergence results in Section §4. We first provide
a detailed proof for the convergence of Algorithm 1, and then prove the two theorems related to
Algorithm 2 by drawing parallels with the first two proofs.

5.1

Proof of Theorem 4.6

To proceed with the proof, we first establish the stability of the update {ωt }. This stability condition
serves as an assumption in the original two-time-scale SA analysis (Borkar, 2008, Chapter 6.1).
It is usually verified separately using some other sufficient conditions (Borkar and Meyn, 2000;
Andrieu et al., 2005). We will directly use the lemma in the convergence analysis to follow and
defer its proof to Appendix §A.
Lemma 5.1. Under Assumptions 2.2, and 4.2-4.5, the sequence {ωti } generated from (3.7) is
bounded almost surely, i.e., supt kωti k < ∞ a.s., for any i ∈ N .
17

As in the classical two-time-scale SA analysis (Borkar, 2008), we let the policy parameter θt to
be fixed as θt ≡ θ when analyzing the convergence of the critic step. This allows us to show that ωt
will converge to some ωθ depending on θ, which can be further utilized to simplify the proof of
convergence for the slow time scale. In fact, with linear function approximation, one can rewrite
the actor step (3.9) for Algorithm 1 as
!
βθ,t
i
i
i
i
i
·A ·ψ ,
(5.1)
θt+1 = Γ θt + βω,t ·
βω,t t t
where the projection Γ i follows from Assumption 4.1. Note that Ait is also bounded a.s., since the
parameter ωti is bounded by Lemma 5.1, and the feature φt is bounded by and Assumption 4.4.
Moreover, ψti is bounded a.s. by Assumption 2.2 since it is a continuous function over a bounded
−1
set Θ i . Therefore, supt kAit · ψti k < ∞ a.s. Now since βθ,t · βω,t
→ 0 by Assumption 4.5, it follows
−1
i
i
that βθ,t · βω,t · At · ψt → 0 as t → ∞. Now the update in (5.1) can be viewed to track the ordinary
differential equation (ODE) θ̇ i (t) = 0. Hence, one may let θt be a constant when analyzing the
faster update of ωti . For notational simplicity, we eliminate the notations associated with θ unless
otherwise noted.
Let {Ft,1 } be the filtration with Ft,1 = σ (rτ , µτ , ωτ , sτ , aτ , Cτ−1 , τ ≤ t), which is an increasing
>
σ -algebra over time t. For notational convenience, let rt = (rt1 , · · · , rtN )> , µt = (µ1t , · · · , µN
t ) , ωt =
1 >
1 >
N > >
N > >
[(ωt ) , · · · , (ωt ) ] , and δt = [(δt ) , · · · , (δt ) ] . The update of ωt in (3.7) can be rewritten in a
compact form as


ωt+1 = (Ct ⊗ I) ωt + βω,t · yt+1 ,
(5.2)
where ⊗ denotes the Kronecker product, I ∈ RK×K is the identity matrix, and yt+1 = (δt1 φt> , · · · , δtN φt> )> ∈
RKN . Define the operator h·i : RKN → RK by letting
1 X i
1
(5.3)
hωi = (1> ⊗ I)ω =
ω
N
N
i∈N

for any ω = [(ω1 )> , · · · , (ωN )> ]> ∈ RKN and ωi ∈ RK with i ∈ N . That is, hωi ∈ RK represents the
average of the vectors in {ω1 , · · · , ωN }, which are local to individual agents. Let J = (1/N · 11> ) ⊗ I
be the projection operator that projects the vector into the consensus subspace {1 ⊗ u : u ∈ RK }.
Thus we have J ω = 1 ⊗ hωi. Moreover, we define J⊥ as the operator that projects the vector to the
disagreement subspace, i.e., J⊥ = I − J . Thus the disagreement vector ω⊥ = J⊥ ω is written as
ω⊥ = J⊥ ω = ω − 1 ⊗ hωi.

(5.4)

The proof of Theorem 4.6 then consists of two steps. In particular, we separate the iteration
ωt as the sum of a vector in this consensus space and a vector in the disagreement space, i.e.,
ωt = ω⊥,t + 1 ⊗ hωt i. We first show the a.s. convergence of the disagreement vector sequence {ω⊥,t }
to zero. Then, we prove that the consensus vector sequence {1 ⊗ hωt i} converges to the equilibrium
such that hωt i satisfies (4.2).
Step 1. In this step, we establish that limt ω⊥,t = 0 a.s. To this end, we first have the following
lemma on the boundedness of the sequence {µit } for any i ∈ N .
Lemma 5.2. Under Assumptions 2.2 and 4.2, the sequence {µit } generated as in (3.7) is bounded
almost surely, i.e., supt |µit | < ∞ a.s., for any i ∈ N .
18

Proof. The local update in (3.7) forms a stochastic approximation iteration, whose asymptotic
behavior can be captured by the ODE
X
X
µ̇i = −µi +
dθ (s)
πθ (s, a)Ri (s, a).
(5.5)
s∈S

a∈A

Let f (µi ) denote the right hand side (RHS) of (5.5), which is Lipschitz continuous in µi . Moreover,
define fc (µi ) = f (cµi ) · c−1 , then f∞ (µi ) = limc f (cµi ) · c−1 = −µi exists. Therefore, the ODE µ̇i = f∞ (µi )
has origin as the unique asymptotically stable equilibrium. In addition, since rti is uniformly
bounded, we have
h
i
2
i
i
E rt+1
− E(rt+1
Ft,1 ) Ft,1 ≤ K0 · (1 + |µit |2 )
for some K0 < ∞. Therefore, the conditions (a.1) and (a.4) in Assumption B.1 are satisfied. (See
Appendix §B.1 for details.) By Assumption 2.2, (a.2) in Assumption B.1 also holds. We thus
conclude that supt |µit | < ∞ from Theorem B.3 (see also Theorem 9 on page 74-75 in Borkar
(2008)).
Let zti = [µit , (ωti )> ]> and zt = [(zt1 )> , · · · , (ztN )> ]> . By Lemma 5.1, we have P(supt kzt k < ∞) = 1,
S
which means that P( M∈Z+ {supt kzt k ≤ M}) = 1, with Z+ denoting the set of positive integers.
Hence, it suffices to show that limt ω⊥,t I{supt kzt k≤M} = 0, for any M ∈ Z+ , where I{·} is the indicator
−1
function. We then establish that E(kβω,t
ω⊥,t k2 ) is bounded on {supt kzt k ≤ M}, for any M > 0.
Lemma 5.3. Under Assumptions 4.2-4.5, for any M > 0, we have


−1
sup E kβω,t
ω⊥,t k2 I{supt kzt k≤M} < ∞.
t

Proof. First note that by (a.1) in Assumption 4.3 and the fact that (A ⊗ B)(C ⊗ D) = (AC) ⊗ (BD), we
have
(Ct ⊗ I)(1 ⊗ hωi) = (Ct 1) ⊗ hωi = 1 ⊗ hωi.
Hence, ω⊥,t+1 has the form ω⊥,t+1 = J⊥ [(Ct ⊗ I)(ωt + βω,t yt+1 )] = J⊥ [(Ct ⊗ I)(ω⊥,t + βω,t yt+1 )], since
J⊥ (1 ⊗ hωi) is zero. Thus, by the definition of J⊥ in (5.4), the vector ω⊥,t+1 satisfies
ω⊥,t+1 = [(I − 11> /N ) ⊗ I](Ct ⊗ I)(ω⊥,t + βω,t yt+1 ) = [(I − 11> /N )Ct ⊗ I](ω⊥,t + βω,t yt+1 ).

(5.6)

Thus, we have

−1
E βω,t+1
ω⊥,t+1
≤
≤

2
βω,t
2
βω,t+1
2
βω,t
2
βω,t+1

2

2

n
> h
i

o
βω,t
−1
>
−1
Ft,1 = 2
· E βω,t
ω⊥,t + yt+1 C>
(I
−
11
/N
)C
⊗
I
β
ω
+
y
F
t
t+1
t,1
ω,t ⊥,t
t
βω,t+1

h
> 

i
−1
−1
ω⊥,t + yt+1 Ft,1
· ρ · E βω,t
ω⊥,t + yt+1 βω,t
·ρ·



−1
βω,t
ω⊥,t

2

h 
i 1


−1
+ 2 · βω,t
ω⊥,t · E kyt+1 k2 Ft,1 2 + E kyt+1 k2 Ft,1 ,

19

(5.7)

>
where ρ represents the spectral norm of E[C>
t (I − 11 /N )Ct ]. By (a.3) in Assumption 4.3, we
i
have ρ ∈ [0, 1). The first inequality in (5.7) is due to the conditional independence of Ct and rt+1
for all i ∈ N , and thus yt+1 , by (a.4) in Assumption 4.3, and the second inequality is due to the
Cauchy-Schwarz inequality. Moreover, by the definition of yt+1 , we have




X





 X  i

2
2

>
> i
2
i
i
i



E kyt+1 k | Ft,1 = E
δt φt Ft,1  = E
rt+1 − µt + φt+1 ωt − φt ωt φt Ft,1 
i∈N

i∈N


 X i
≤ 3 · E
rt+1 φt

2

2
µit φt +

+

i∈N



>
φt φt+1
− φt>

2

2
ωti



Ft,1 ,

(5.8)

>
where the inequality follows from that by Assumption 4.4, E[kφt (φt+1
−φt> )k2 | Ft,1 ] and E(kφt k2 | Ft,1 )
are both uniformly bounded for any st ∈ S and at ∈ A. Moreover, by Assumption 4.2, we have
i 2
i 2
E(|rt+1
| | Ft,1 ) = E(|rt+1
| | st , at ) also uniformly bounded. Thus the RHS of (5.8) is bounded on the
set {supτ≤t kzτ k ≤ M} for any M > 0 as follows, i.e., there exists K1 < ∞, such that



X 





i 2
E kyt+1 k2 I{supτ≤t kzτ k≤M} Ft,1 ≤ K1 · 1 +
E |rt+1
| Ft,1 .

(5.9)

i∈N

−1
Let ηt = kβω,t
ω⊥,t k2 I{supτ≤t kzτ k≤M} and note that I{supτ≤t+1 kzτ k≤M} ≤ I{supτ≤t kzτ k≤M} . Then by taking
P
i 2
| )] < ∞
expectation over both sides of (5.7), we obtain that there exists K2 = K1 · [1 + E( i∈N |rt+1
such that

E(ηt+1 ) ≤

2
βω,t
2
βω,t+1

q
h
i
p
· ρ · E(ηt ) + 2 E(ηt ) · K2 + K2 .

(5.10)

2
−2
Since limt βω,t
· βω,t+1
= 1 and ρ < 1, for any δ > 0, there exists a large enough t0 such that for any
2
−2
t > t0 , βω,t · βω,t+1 · ρ ≤ 1 − δ. Hence, there exist positive constants K3 and b such that for any t ≥ t0 ,

q
h
i 

p
E(ηt+1 ) ≤ (1 − δ) · E(ηt ) + 2 E(ηt ) · K2 + K2 ≤ 1 − δ/2 · E(ηt ) + b · I{E(ηt )≤K3 } .

By induction, we obtain that E(ηt ) ≤ (1 − δ/2)t−t0 E(ηt0 ) + 2b/δ. Hence, we have supt E(ηt ) < ∞. In
addition, since I{supt kzt k≤M} ≤ I{supτ≤t kzτ k≤M} , we further obtain


−1
sup E kβω,t
ω⊥,t k2 I{supt kzt k≤M} < ∞,
t

which concludes the proof.
Therefore, by Lemma 5.3, we obtain that for any M > 0, there exists a constant K4 < ∞,
P 2
2
such that for any t ≥ 0, E(kω⊥,t k2 ) ≤ K4 · βω,t
on the set {supt kzt k ≤ M}. Since t βω,t
< ∞ by
P
Assumption 4.5, we have that t E(kω⊥,t k2 I{supt kzt k≤M} ) is finite by Fubini’s theorem. This shows
P
that t kω⊥,t k2 I{supt kzt k≤M} < ∞ a.s., which further yields limt ω⊥,t I{supt kzt k≤M} = 0 a.s. By Lemmas
5.1 and 5.2, {supt kzt k < ∞} holds with probability 1. This shows that limt ω⊥,t = 0 a.s., and thus
concludes Step 1.

20

Step 2. We now proceed to show the convergence of the consensus vector 1 ⊗ hωt i. According to
the update in (5.2) and definition (5.3), the iteration of hωt i has the form
hωt+1 i =

1 >
−1
(1 ⊗ I)(Ct ⊗ I)(1 ⊗ hωt i + ωt,⊥ + βω,t yt+1 ) = hωt i + βω,t h(Ct ⊗ I)(yt+1 + βω,t
ω⊥,t )i.
N

Hence, we write the updates for hωt i and hµt i as


hµt+1 i = hµt i + βω,t · E r t+1 − hµt i Ft,1 + βω,t · ξt+1,1 ,


hωt+1 i = hωt i + βω,t · E hδt iφt Ft,1 + βω,t · ξt+1,2 ,

(5.11)
(5.12)

where ξt+1,1 = r t+1 − E(r t+1 | Ft,1 ) and ξt+1,2 is



−1
ξt+1,2 = h(Ct ⊗ I)(yt+1 + βω,t
ω⊥,t )i − E hδt iφt Ft,1 .

Note that E(r t+1 − hµt i | Ft,1 ) is Lipschitz continuous in hµt i. Recall that hδt i has the form
hδt i =

1 X i
>
>
rt+1 − µit + φt+1
ωti − φt> ωti = r t+1 − hµt i + φt+1
hωt i − φt> hωt i.
N
i∈N

Hence, E(hδt iφt | Ft,1 ) is Lipschitz continuous in both hωt i and hµt i, and thus the condition (a.1) in
Assumption B.1 (See Appendix §B.1) is satisfied.
Note that ξt,1 is a martingale difference sequence and satisfies




E kξt+1,1 k2 Ft,1 ≤ K5 · 1 + khωt ik2 + khµt ik2 ,
(5.13)
for some K5 < ∞, since r t+1 is uniformly bounded. In addition, the term ξt,2 is also a martingale
difference sequence, since
h
i
h
i




−1
E h(Ct ⊗ I)(yt+1 + βω,t
ω⊥,t )i Ft,1 = E h(Ct ⊗ I)yt+1 i Ft,1 = E hyt+1 i Ft,1 = E hδt iφt Ft,1 ,
which results from the facts that hω⊥,t i = 0 and that 1> E(Ct ) = 1> . Moreover, we have



−1
E kξt+1,2 k2 Ft,1 ≤ 2 · E yt+1 + βω,t
ω⊥,t

2
Gt



 2
Ft,1 + 2 · E hδt iφt Ft,1 ,

(5.14)

>
−2
where Gt = C>
t 11 Ct ⊗ I · N . Note that Gt has bounded spectral norm since Ct is a stochastic
matrix. Thus the first term in (5.14) can be further bounded over the set {supt kzt k ≤ M}, for any
M > 0. Notably, there exist K6 , K7 < ∞ such that


−1
E yt+1 + βω,t
ω⊥,t

2
Gt



Ft,1 · I{supt kzt k≤M} ≤ K6 · E yt+1

2

−1
+ βω,t
ω⊥,t

2


Ft,1 · I{supt kzt k≤M} < K7 ,

where the second inequality follows from (5.9) and Lemma 5.3. Moreover, the second term in
(5.14) can be bounded by kE(hδt iφt | Ft,1 )k2 ≤ K8 · (1 + khωt ik2 + khµt ik2 ) with some K8 < ∞, due to
i
the boundedness of rt+1
and φt (from Assumptions 4.2 and 4.4). Hence, for any M > 0, it follows
that




E kξt+1,1 k2 Ft,1 ≤ K9 · 1 + khωt ik2 + khµt ik2 ,
(5.15)
21

over the set {supt kzt k ≤ M} for some K9 < ∞. This verifies that on the set {supt kzt k ≤ M} for any
M > 0, the condition (a.4) in Assumption B.1 is satisfied.
Now consider the following ODE that captures the asymptotic behavior of (5.11) and (5.12)

 


 
˙  
 hµi
 hµi   J(θ) 
−1
0
˙ = 
 

 

hzi
(5.16)
hωi
˙  = −Φ > Ds,a 1 Φ > Ds,a (P θ − I)Φ hωi + Φ > Ds,a R.
θ
θ
θ
Recall that Ds,a
θ = diag[dθ (s) · πθ (s, a), s ∈ S, a ∈ A]. Let the RHS of the ODE (5.16) be h(hzi), then
h(hzi) is Lipschitz continuous in hzi, which satisfies the condition (a.1) in Assumption B.1. By the
Perron-Frobenius theorem and Assumption 2.2, the stochastic matrix P θ has a simple eigenvalue
of 1, and its remaining eigenvalues have real parts less than 1. Hence, (P θ − I) has all eigenvalues
θ
with negative real parts but one zero, so does the matrix Φ > Ds,a
θ (P − I)Φ, since Φ is full column
rank by Assumption 4.4. The simple eigenvalue of zero has eigen-vector ν that satisfies Φν = α 1
θ
for some α , 0, since α 1 lies in the eigen-space of Ds,a
θ (P − I) associated with zero. By Assumption
4.4, however, this will not happen with any choice of Φ since Φν , α 1 for any ν ∈ RK . Hence, the
ODE (5.16) is globally asymptotically stable and has its equilibrium satisfying
h
i
θ
−hµi = J(θ),
Φ > Ds,a
R
−
hµi
1
+
P
Φhωi
−
Φhωi
= 0.
(5.17)
θ
Note that the corresponding solution for hµi at equilibrium is J(θ), whereas the solution for hωi has
the form ωθ + αν with any α ∈ R and ν ∈ RK such that Φν = 1. While by Assumption 4.4, Φν , 1,
Q
Q
thus the term ωθ is unique, and it follows that Φ > Ds,a
θ [Tθ (Φωθ ) − Φωθ ] = 0 with Tθ as defined in
(4.1).
Recall from Lemmas 5.1 and 5.2 that {zt } is bounded a.s., so is the sequence {hzt i}. Hence all
conditions for Theorem B.2 to hold are satisfied. For the concatenated vector hzt i = (hµt i, hωt i> )> ,
we thus have limt hµt i = J(θ) and limt hωt i = ωθ over the set {supt kzt k ≤ M} for any M > 0. By
Lemmas 5.1 and 5.2, this holds with probability 1, which concludes Step 2. Combined with Step 1,
we arrive at the conclusion that limt ωti = ωθ for any i ∈ N , which completes the proof for Theorem
4.6.

5.2

Proof of Theorem 4.7

Let Ft,2 = σ (θτ , τ ≤ t) be the σ -field generated by {θτ , τ ≤ t}. In addition, we define


h

i
i
i
ζt+1,1
= Ait · ψti − Est ∼dθt ,at ∼πθt Ait · ψti Ft,2 ,
ζt+1,2
= Est ∼dθt ,at ∼πθt Ait − Ait,θt · ψti Ft,2 ,
where Ait,θt is as defined in (4.4) with θ = θt . Then the actor update in (3.9) with a local projection
becomes




i
i i
i
i
i
i
(5.18)
θt+1 = Γ θt + βθ,t Est ∼dθt ,at ∼πθt At,θt · ψt Ft,2 + βθ,t ζt+1,1 + βθ,t ζt+1,2 .
i
Note that ζt+1,2
= o(1) since the critic converges, i.e., Ait → Ait,θt , at the faster time scale. Moreover,
P
i
letting Mti = tτ=0 βθ,τ ζτ+1,1
, {Mti } is a martingale sequence. Since the sequences {ωti }, {ψti }, and {φt }
i
are all bounded, the sequence {ζt,1
} is also bounded. Hence, by Assumption 4.5, we have
X 
 X
2
2
i
i
E Mt+1
− Mti
Ft,2 =
βθ,t ζt+1,1
< ∞ a.s.
t

t≥1

22

By the martingale convergence theorem (Proposition VII-2-3(c) on page 149 of Neveu (1975)), the
martingale sequence {Mti } converges a.s. Thus, for any  > 0, we have


n
X


i
lim P sup
βθ,τ ζτ,1 ≥  = 0.
t
n≥t

τ=t

In addition, let


g i (θt ) = Est ∼dθt ,at ∼πθt Ait,θt · ψti Ft,2 =

X
st ∈S,at ∈A

i
,
dθt (st ) · πθt (st , at ) · Ait,θt · ψt,θ
t

i
then we show that g i (θt ) is continuous in θti as follows. First, ψt,θ
is continuous by Assumption
t

2.2. Also, the term dθt (st ) · πθt (st , at ) is continuous in θti since it is the stationary distribution and
P
P
thus is the solution to dθt (s) · πθt (s, a) = s0 ∈S,a0 ∈A P θt (s0 , a0 | s, a) · dθt (s0 ) · πθt (s0 , a0 ) and s∈S,a∈A dθt (s) ·
πθt (s, a) = 1, where P θt (s0 , a0 | s, a) = P (s0 | s, a) · πθt (s0 , a0 ). The unique solution to this set of linear
equations can be verified to be continuous in θt , noting that πθt (s, a) > 0 by Assumption 2.2.
In addition, Ait,θt is continuous in θti since ωθt is the unique solution to the linear equation
Q

Φ > Ds,a
θ [Tθ (Φωθ ) − Φωθ ] = 0 and can also be verified to be continuous in θt . Therefore, by KushnerClark lemma (Kushner and Clark, 1978, page 191-196) (see also Theorem B.5 in Appendix §B.2),
the update in (5.18) converges a.s. to the set of asymptotically stable equilibria of the ODE (4.6) for
each i ∈ N , which concludes the proof.
The proof for the convergence of Algorithm 2 is similar to the proofs in 5.1 and 5.2. To avoid
duplication, we leave out some of the details in the proofs to follow.

5.3

Proof of Theorem 4.10

Let zti = [µit , (λit )> , (vti )> ]> ∈ R1+M+L . We first have the following lemma on the stability of the
updates of {zti }, as in Lemma 5.1, the proof of which is provided in Appendix §A.

Lemma 5.4. Under Assumptions 2.2, 4.2, 4.3, 4.8, and 4.9, the sequence {zti } generated from (3.12),
(3.13), and (3.16) satisfies supt zti < ∞ a.s., for any i ∈ N .
Note that δeti · ψti is bounded by Assumptions 2.2, 4.8, and Lemma 5.4. Thus the actor step
(3.17) can be viewed to track ODE θ̇ i = 0 when analyzing the faster time scale update. Thus by
the same argument as in §5.1, we fix the value of θt as a constant θ. For notational convenience,
let vt = [(vt1 )> , · · · , (vtN )> ]> , δt = [(δt1 )> , · · · , (δtN )> ]> , and zt = [(zt1 )> , · · · , (ztN )> ]> . We also use {Ft,1 } to
denote the filtration with Ft,1 = σ (rτ , zτ , sτ , Cτ−1 , τ ≤ t), an increasing σ -algebra. Then the updates
of zt in (3.12), (3.13), and (3.16) have the following compact form


zt+1 = (Ct ⊗ I) zt + βv,t · yt+1 ,
(5.19)
i
i
where yt = [(yt1 )> , · · · , (ytN )> ]> ∈ R(1+M+L)N . Here we denote [rt+1
− µit , (rt+1
− ft> λit )ft> , δti ϕt> ]> by
i
yt+1
. Recall that ft = f (st , at ) and ϕt = ϕ(st ). With the same definitions for h·i, J , and J⊥ , we can
also separate the iteration of zt as the sum of the consensus vector and the disagreement vector, i.e.,
zt = z⊥,t + 1 ⊗ hzt i, with z⊥,t = J⊥ zt . Then the proof proceeds again in two steps as follows.

Step 1. We first establish that limt z⊥,t = 0 a.s. By Lemma 5.4, it suffices to show that for any
−1
M ∈ Z+ , limt z⊥,t I{supt kzt k≤M} = 0. We first establish the boundedness of E(kβv,t
z⊥,t k2 ) over the set
{supt kzt k ≤ M}, for any M > 0.
23

Lemma 5.5. Under Assumptions 4.2, 4.3, 4.8, and 4.9, for any M > 0, we have


−1
sup E kβv,t
z⊥,t k2 I{supt kzt k≤M} < ∞.
t

Proof. Following the derivation of (5.6), we obtain the iteration of z⊥,t as
z⊥,t+1 = [(I − 11> /N ) ⊗ I](Ct ⊗ I)(z⊥,t + βv,t yt+1 ) = [(I − 11> /N )Ct ⊗ I](z⊥,t + βv,t yt+1 ).

(5.20)

Thus, similar to the derivation of (5.7), we obtain

−1
z⊥,t+1
E βv,t+1


2

βv,t
2
−1
−1
Ft,1 ≤ ρ · 2
z⊥,t
z⊥,t + 2 βv,t
· βv,t
βv,t+1
h 
i 1


· E kyt+1 k2 Ft,1 2 + E kyt+1 k2 Ft,1 ,

2

(5.21)

>
where ρ represents the spectral norm of E[C>
t (I − 11 /N )Ct ] and ρ ∈ [0, 1). Then we have




 X i
2
i
2
rt+1 − µit + (rt+1
E kyt+1 k | Ft,1 = E
− ft> λit )ft

2

+

2
δti ϕt

i∈N



Ft,1 .

(5.22)

>
By Assumption 4.8, we have E[kϕt (ϕt+1
− ϕt> )k2 | Ft,1 ] and E(kϕt k2 | Ft,1 ) uniformly bounded for
i 2
i 2
any st ∈ S. Moreover, by Assumption 4.2, we have E(|rt+1
| | Ft,1 ) = E(|rt+1
| | st , at ) also uniformly
bounded for any st ∈ S, at ∈ A. Thus for any M > 0, there exist K1 , K2 < ∞4 such that (5.22) is
further bounded as


X 




2
i
2
E kyt+1 k I{supτ≤t kzτ k≤M} Ft,1 ≤ K1 · 1 +
E |rt+1 | Ft,1  < K2 .
(5.23)
i∈N

−1
Let ηt = kβv,t
z⊥,t k2 I{supτ≤t kzτ k≤M} . By taking expectation on both sides of (5.21), we obtain

E(ηt+1 ) ≤

2
βv,t
2
βv,t+1

q
h
i
p
· ρ · E(ηt ) + 2 E(ηt ) · K2 + K2 .

Following the same argument as in the proof of Lemma 5.3, we obtain supt E(ηt ) < ∞ and thus


−1
sup E kβv,t
z⊥,t k2 I{supt kzt k≤M} < ∞,
t

which concludes the proof.
Therefore, by Lemma 5.5 and Assumption 4.9, we arrive at limt z⊥,t I{supt kzt k≤M} = 0 a.s. for any
M > 0. By Lemma 5.4, {supt kzt k < ∞} holds with probability 1. This shows that limt z⊥,t = 0 a.s.,
and thus concludes Step 1.
4 We note that K and K here are absolute constant values, with slight abuse of notation, we use the same notation as
1
2
in the proof of Theorem 4.6. The same abuse applies to the other constants with notation Kj , for any j ∈ N.

24

Step 2. We now proceed to show the convergence of the consensus vector 1 ⊗ hzt i. The iteration of
hzt i has the form

1 >
−1
(1 ⊗ I)(Ct ⊗ I)(1 ⊗ hzt i + zt,⊥ + βv,t yt+1 ) = hzt i + βv,t h(Ct ⊗ I)(yt+1 + βv,t
z⊥,t )i.
N
Hence, the update for hzt i becomes
hzt+1 i =

hzt+1 i = hzt i + βv,t · E(hyt+1 i | Ft,1 ) + βv,t · ξt+1 ,

where ξt+1 and hyt+1 i have the form

(5.24)

hyt+1 i = [r t+1 − hµt i, (r t+1 − ft> hλt i)ft> , hδt iϕt> ]> ,

−1
ξt+1 = h(Ct ⊗ I)(yt+1 + βω,t
ω⊥,t )i − E(hyt+1 i | Ft,1 ),

>
respectively. Recall that hδt i = r t+1 − hµt i + ϕt+1
hvt i − ϕt> hvt i. Note that E(hyt+1 i | Ft,1 ) is Lipschitz
continuous in hzt i = (hµt i, hλt i> , hvt i> )> , and thus the condition (a.1) in Assumption B.1 is satisfied.
Moreover, one can verify that the term ξt is a martingale difference sequence. The conditional
second moment of ξt can be bounded as





 2
2
−1
E kξt+1 k2 Ft,1 ≤ 2 · E yt+1 + βv,t
z⊥,t G Ft,1 + 2 · E hyt+1 i Ft,1 ,
(5.25)
t

>
G t = C>
t 11 Ct

⊗ I · N −2

where
has bounded spectral norm. Thus the first term in (5.25) is bounded
over the set {supt kzt k ≤ M}, for any M > 0, i.e., there exist K3 , K4 < ∞ such that




2
2
2
−1
−1
E yt+1 + βv,t
z⊥,t G Ft,1 · I{supt kzt k≤M} ≤ K3 · E yt+1 + βv,t
z⊥,t
Ft,1 · I{supt kzt k≤M} < K4 ,
t

(5.26)

where the second inequality follows from (5.23) and Lemma 5.5. Moreover, the second term in
(5.25) can be bounded by

 2






2
E hyt+1 i Ft,1
≤ E hyt+1 i Ft,1 ≤ K5 · 1 + khµt ik2 + khλt ik2 + khvt ik2 = K5 · 1 + khzt ik2
i
with some K5 < ∞ due to the boundedness of rt+1
, ft , and ϕt . Hence, for any M > 0, it follows that




E kξt+1 k2 Ft,1 ≤ K6 · 1 + khzt ik2 ,
(5.27)

over the set {supt kzt k ≤ M} for some K6 < ∞. This verifies the condition (a.4) in Assumption B.1.
Then the ODE associated with (5.24) has the form
 ˙  
  

0
0
hµi  −1
 hµi  J(θ) 







 hλi +  F> Ds,a R  .
˙ = hλi
˙  
−F> Ds,a
0
hzi
(5.28)
   

θ F
θ
  =  >0 s

> Ds (P θ − I)Φ   hvi   > s
˙
−Φ
D
1
0
Φ
hvi
Φ Dθ R θ
θ
θ

Letting the RHS of the ODE (5.28) be h(hzi), we have h(hzi) Lipschitz continuous in hzi. Similar to
the proof in Step 2 of §5.1, one can verify that the ODE has a unique globally asymptotically stable
> >
equilibrium [J(θ), λ>
4.8 on the feature matrices F and Φ. Here λθ and vθ are
θ , vθ ] , byAssumption

h
i
s,a
>
the unique solutions to F Dθ R − Fλθ = 0 and Φ > Dsθ TθV (Φvθ ) − Φvθ = 0, respectively. Recall the

operator TθV defined in (4.7). Moreover, the sequence {zt } is bounded almost surely by Assumption
5.4. Hence all conditions for Theorem B.2 to hold are satisfied. We thus have limt hµt i = J(θ),
limt hλt i = λθ , and limt hvt i = vθ over the set {supt kzt k ≤ M} for any M > 0. By Lemma 5.4 and the
results from Step 1, we obtain that limt µit = J(θ), limt λit = λθ , and limt vti = vθ for any i ∈ N a.s.,
which completes the proof.
25

5.4

Proof of Theorem 4.11

Let Ft,2 = σ (θτ , τ ≤ t) be the σ -field generated by θτ , τ ≤ t. Let
i

h


i
i
i
i
F
,
ζt+1,2
= Est ∼dθt ,at ∼πθt δeti − δet,θ
·
ψ
ζt+1,1
= δeti · ψti − Est ∼dθt ,at ∼πθt δeti · ψti Ft,2 ,
t,2
t
t
i
where δet,θ
is as defined in (4.9) with θ = θt . Then the actor update in (3.17) with a local projection
t
becomes




i
i
i
θt+1
= Γ i θti + βθ,t Est ∼dθt ,at ∼πθt δeti · ψti Ft,2 + βθ,t ζt+1,1
+ βθ,t ζt+1,2
.
(5.29)
i
i
Note that ζt+1,2
= o(1) since the critic converges, i.e., δeti → δet,θ
, at the faster time scale. Moreover,
t
Pt
i
i
i
letting Mt = τ=0 βθ,τ ζτ+1,1 , we have {Mt } a martingale sequence. Note that the sequences {zti }, {ψti },
P
i
i
and {φt } are all bounded, and so is the sequence {ζt,1
}. Hence, we have t E(kMt+1
− Mti k2 | Ft,2 ) < ∞
i
a.s., and further obtain that the martingale sequence {Mt } converges a.s. (Neveu, 1975, page
149)). Thus the condition (a.4) in Assumption B.4 is satisfied. (See Appendix §B.1 for details.)
One can also verify that Est ∼dθt ,at ∼πθt (δeti · ψti | Ft,2 ) is continuous in θti . Therefore, we can apply the
Kushner-Clark lemma (Theorem B.5 in Appendix §B.2) to show that the update in (5.29) converges
a.s. to the set of asymptotically stable equilibria of the ODE (4.10), for each i ∈ N , which concludes
the proof.

6

Numerical Results

In this section, we evaluate the proposed fully decentralized AC algorithms through numerical
simulations with both linear and nonlinear function approximation.

6.1

Linear Function Approximation

We first consider the setting where linear function approximation is adopted. Consider in total
N = 20 agents, each has a binary-valued action space, i.e., Ai = {0, 1}, for all i ∈ N . Thus the
cardinality of the set of actions A is 220 . In addition, there are in total |S| = 20 states. The following
ways of selecting the model and algorithm parameters, including transition probabilities, rewards,
and features, follow from those in Dann et al. (2014). The elements in the transition probability
matrix P are uniformly sampled from the interval [0, 1] and normalized to be stochastic. We also
add a small constant 10−5 onto each element in the matrix to ensure ergodicity of the MDP such
that Assumption 2.2 is satisfied. For each agent i and each state-action pair (s, a), the mean reward
Ri (s, a) is sampled uniformly from [0, 4], which varies among agents. The instantaneous rewards
rti are sampled from the uniform distribution [Ri (s, a) − 0.5, Ri (s, a) + 0.5]. The policy πθi i (s, ai ) is
parameterized following the Boltzman policies, i.e.,


>
i
exp qs,a
iθ


πθi i (s, ai ) = P
>
i
exp qs,b
iθ
bi ∈Ai

where qs,bi ∈ Rmi is the feature vector with the same dimension as θ i , for any s ∈ S and i ∈ N . Here
we set m1 = m2 = · · · = mN = 5. The elements of qs,bi are also uniformly sampled from [0, 1]. In
26

particular, the gradient of the score function thus has the form
X
∇θ i log πθi i (s, ai ) = qs,ai −
πθi i (s, ai )qs,bi .
bi ∈Ai

The feature vectors φ ∈ RK for the action-value function Q(·, ·; ω) in Algorithm 1, ϕ ∈ RL for the
value function V (·; v) and f ∈ RM for the globally averaged reward function R(·, ·; λ) in Algorithm
2, are all uniformly sampled from [0, 1], of dimensions K = 10  |S| · |A|, L = 5 < |S|, and M = 10 
|S| · |A|. Moreover, the selected feature matrices Φ, Φ, and F are all ensured to have full column
rank as required in Assumptions 4.4 and 4.8.
2.65
2.6
2.55
2.5
2.45
2.4
2.35
2.3
2.25

0

200

400

600

800

1000

1200

Figure 1: The convergence of globally averaged returns, when linear function approximation
is used. We plot the returns achieved by both Algorithm 1 and Algorithm 2, along with their
centralized counterparts Central-1 and Central-2.
The consensus weight matrix Ct is chosen independent and identically distributed along time t
by normalizing the absolute Laplacian matrix of a random graph Gt over agents N to be doubly
stochastic. The graph Gt is generated by randomly placing communication links among agents
such that the connectivity ratio5 is 4/N . The stepsizes are selected as βω,t = βv,t = 1/t 0.65 and
βθ,t = 1/t 0.85 , which satisfy Assumptions 4.5 and 4.9.
The performances of the fully decentralized algorithms are compared with those of the centralized algorithms in which the rewards rti of all agents are available at a centralized controller
and the global policy πθ is also updated there. These centralized version algorithms thus reduce to
single-agent AC algorithms with linear function approximation. We use two centralized AC algorithms based on action-value and state-value function approximation, to compare with Algorithm
1 and Algorithm 2, respectively. In particular, the former one, referred to as Central-1, follows the
single-agent AC updates in (2.3). The later one, referred to as Central-2, follows the updates of
5 Note that the connectivity ratio is defined as the ratio between the total degree of the graph and the degree of the
complete graph, i.e., 2E/[N (N − 1)], where E is the number of edges.

27

Algorithm 1 in Bhatnagar et al. (2009) and is based on state-value TD-error as Algorithm 2 here. In
particular, it has the following critic step


µt+1 = (1 − βv,t ) · µt + βv,t · r t+1 ,




δt = r t+1 − µt + Vt+1 (vt ) − Vt (vt ),




 vt+1 = vt + βv,t · δt · ∇v Vt (vt ),

(6.1)

where we recall that Vt (v) = V (st ; v) for any v ∈ RL and βv,t > 0 is the stepsize satisfying Assumption
4.5. Since the rewards of all agents {rti }i∈N are available to the controller, no estimation for the
globally averaged reward function R is needed in the update. Thus, the global state-value TD-error
δt can be computed immediately and used in the actor step as
i
θt+1
= θti + βθ,t · δt · ψti ,

(6.2)

∀i ∈ N ,

where ψti is as defined in (3.10).
As shown in Figure 1, both decentralized algorithms converge to the globally long-term averaged
return as achieved by the two centralized algorithms. Moreover, it is corroborated in Figure 2 that
for each agent, the approximation of action-value function in Algorithm 1 and state-value function
in Algorithm 2 reach consensus at a much faster rate than the AC algorithm converges. It is also
observed that the decentralized algorithms converge to the stationary relative value functions
slower than the centralized counterparts, possibly due to the delay of information diffusion across
the network.
In addition, in terms of policy, both Algorithms 1 and 2 converge to similar policies as their
central counterparts. Figure 3 illustrates the resulting policies by all algorithms, i.e., the probability
distribution πθi i (s, ai ) for a randomly selected state s for any i ∈ N . Note that there are in total
3.5

2.5

3

2

2.5
1.5

2
1

1.5
0.5

1

0
-0.5

0.5
0
0

2000

4000

6000

8000

10000

(a) Algorithm 1 v.s. Central-1

0

2000

4000

6000

8000

10000

(b) Algorithm 2 v.s. Central-2

Figure 2: The convergence of relative value functions at four randomly selected agents, when linear
function approximation is used. We randomly select the agents 2, 5, 8, and 17. In (a), we plot the
convergence curve of the relative action-value at a randomly selected state-action pair, obtained
from Central-1 and Algorithm 1. In (b), we plot the convergence curve of the relative state-value at
a randomly selected state, obtained from Central-2 and Algorithm 2.
28

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0

0

5

10

15

20

25

30

35

0

40

(a) s = 2

0

5

10

15

20

25

30

35

40

(b) s = 18

Figure 3: The policies, i.e., the probability distribution πθ (s, a) at a randomly selected state s. In (a),
we plot the policy obtained from Central-1 and Algorithm 1 at state 2. In (b), we plot the policy
obtained from Central-2 and Algorithm 2 at state 18.
2 × 20 probability values under our setting with binary-valued actions and |S| = 20 states. It is
verified that the joint policy obtained by agents using only local information is almost as good as
the policy obtained by the centralized controller with full system information.

6.2

Nonlinear Function Approximation

We also empirically evaluate the performance of Algorithm 1 and Algorithm 2 when nonlinear
function approximators, for example, neural networks, are adopted. Although it seems difficult
to establish convergence guarantees in this case, we believe that the empirical results are of
independent interest, which justify the effectiveness of the proposed fully decentralized algorithms
in a more sophisticated environment.
To this end, we consider the simulation environment of the Cooperative Navigation task in
Lowe et al. (2017). In this environment, agents need to reach a set of L landmarks through
physical movement. Agents are able to observe the position of the landmarks and other agents,
and are rewarded based on the proximity of any agent to each landmark (Lowe et al., 2017).
To be compatible with our networked multi-agent MDP, we modify the environment there in
the following aspects. First, we assume the state is globally observable, i.e., the position of the
landmarks and other agents are observable to each agent. Moreover, each agent has a certain
target landmark to cover, and the individual reward is determined by the proximity to that certain
landmark, as well as the penalty from collision with other agents. In this way, the reward function
varies between agents. The reward is further scaled by different positive coefficients, representing
the different priority/preferences of different agents. In addition, agents are connected via a
time-varying communication network with several other agents nearby. The collaborative goal of
the agents is then to maximize the network-wide averaged long-term return. The illustration of the
modified Cooperative Navigation environment is provided in Figure 4.
Specifically, we consider N = 10 agents moving in a rectangular region of size 2 × 2. Each agent
29

agent 3
agent 1

agent 4

agent 2

Figure 4: Illustration of the experimental environment for the Cooperative Navigation task we
consider, modified from Lowe et al. (2017). In particular, the blue circles represent the agents,
the orange stars represent the landmarks, the green arrows represent the communication links
between agents, and the gray arrows show the target landmark each agent need to cover.
has a single target landmark, i.e., L = N = 10, which is randomly located in the region. The action
set for each agent is the movement set {left, right, up, down, stay}, and thus |Ai | = 5 for any i ∈ N .
The state s includes the position of the landmarks and other agents, which thus has a dimension of
2(N + L) = 40. The reward of agent i is the negative number of the distance to the target landmark,
plus −1 if agent i collides with any other agents. The coefficients that scale the reward of each
agent are selected randomly from a uniform distribution over [0, 2]. Each agent maintains two
neural networks for actor and critic, respectively. Both neural networks have one hidden layer

Globally Averaged Return J

-2.0

-4.0

-6.0

-8.0

Central-1
Central-2
Algorithm 1
Algorithm 2

-10.0
0

25

50

75

100

125

150

175

200

Number of Episodes

Figure 5: The globally averaged returns for the task of Cooperative Navigation, when neural
networks are used for function approximation. We plot the returns achieved by both Algorithm 1
and Algorithm 2, along with their centralized counterparts Central-1 and Central-2.

30

containing 24 neural units, which all use ReLU as the activation function. The output layer for the
actor network is softmax, and that for the critic network is linear.
The time-varying network Gt and consensus matrix Ct are constructed in the same way as in
§6.2. The stepsizes for the actor and critic step are set as constants 0.001 and 0.01, respectively.
For each episode, the algorithms terminate either all agents reach the target landmarks or after
1000 iterations, and we run in total 200 episodes in each test run. We report the globally averaged
return from 10 test runs in Figure 5.
It is shown in Figure 5 that the proposed algorithms successfully converge even with such
nonlinear function approximators. Both decentralized algorithms are able to achieve globally
averaged return close to the centralized counterparts, though at a slightly slower speed. This
may also be explained by the delay of information diffusion across the network. We note that
the AC algorithms based on state-value TD error, namely, Algorithm 2 and Central-2, seem to be
superior to those based on action-value function approximation, namely, Algorithm 1 and Central1. The former may achieve higher globally averaged reward than the latter with smaller variance.
Our decentralized algorithms seem to inherit such convergence properties of their centralized
counterparts. These observations justify the potential applicability of our algorithms to large-scale
MARL problems, when neural networks are used as function approximators.

7

Conclusions

In this paper, we address the problem of multi-agent reinforcement learning with networked
agents. In particular, we consider the fully decentralized setting where each agent makes individual
decisions and receives local rewards, while exchanging information with neighbors over the
network to accomplish optimal network-wide averaged return. Within this setting, we propose two
decentralized actor-critic algorithms with function approximation, which can handle large-scale
MARL problems with numerous agents and massive state-action spaces. We provide theoretical
analysis on the convergence of the proposed algorithms with linear function approximation. An
interesting direction of future research is to extend our algorithms and analyses to the setting with
not only collaborative agents, but also competitive ones over the network. Moreover, it is also
promising to extend the proposed algorithms to the MARL setting with continuous action spaces.

References
Abounadi, J., Bertsekas, D. and Borkar, V. S. (2001). Learning algorithms for Markov Decision
Processes with average cost. SIAM Journal on Control and Optimization, 40 681–698.
Adler, J. L. and Blue, V. J. (2002). A cooperative multi-agent transportation management and
route guidance system. Transportation Research Part C: Emerging Technologies, 10 433–454.
Agarwal, A. and Duchi, J. C. (2011). Distributed delayed stochastic optimization. In Advances in
Neural Information Processing Systems.
Amari, S.-I. (1998). Natural gradient works efficiently in learning. Neural Computation, 10 251–276.
Andrieu, C., Moulines, É. and Priouret, P. (2005). Stability of stochastic approximation under
verifiable conditions. SIAM Journal on Control and Optimization, 44 283–312.
31

Arslan, G. and Yüksel, S. (2017). Decentralized Q-learning for stochastic teams and games. IEEE
Transactions on Automatic Control, 62 1545–1558.
Aysal, T. C., Yildiz, M. E., Sarwate, A. D. and Scaglione, A. (2009). Broadcast gossip algorithms
for consensus. IEEE Transactions on Signal Processing, 57 2748–2761.
Bahdanau, D., Brakel, P., Xu, K., Goyal, A., Lowe, R., Pineau, J., Courville, A. and Bengio, Y.
(2016). An actor-critic algorithm for sequence prediction. arXiv preprint arXiv:1607.07086.
Baxter, J. and Bartlett, P. L. (2000). Direct gradient-based reinforcement learning. In International
Symposium on Circuits and Systems.
Benaı̈m, M. (1999). Dynamics of stochastic approximation algorithms. Séminaire de Probabilités,
XXXIII, 1709 1–68.
Bhatnagar, S. (2010). An actor–critic algorithm with function approximation for discounted cost
constrained Markov Decision Processes. Systems & Control Letters, 59 760–766.
Bhatnagar, S., Ghavamzadeh, M., Lee, M. and Sutton, R. S. (2008). Incremental natural actor-critic
algorithms. In Advances in Neural Information Processing Systems.
Bhatnagar, S., Sutton, R., Ghavamzadeh, M. and Lee, M. (2009). Natural actor-critic algorithms.
Automatica, 45 2471–2482.
Bianchi, P., Fort, G. and Hachem, W. (2013). Performance of a distributed stochastic approximation
algorithm. IEEE Transactions on Information Theory, 59 7405–7418.
Borkar, V. S. (2008). Stochastic approximation: A dynamical systems viewpoint. Cambridge University
Press.
Borkar, V. S. and Meyn, S. P. (2000). The ODE method for convergence of stochastic approximation
and reinforcement learning. SIAM Journal on Control and Optimization, 38 447–469.
Boutilier, C. (1996). Planning, learning and coordination in multi-agent decision processes. In
Conference on Theoretical Aspects of Rationality and Knowledge.
Boyd, S., Ghosh, A., Prabhakar, B. and Shah, D. (2006). Randomized gossip algorithms. IEEE/ACM
Transactions on Networking, 14 2508–2530.
Boyd, S., Parikh, N., Chu, E., Peleato, B. and Eckstein, J. (2011). Distributed optimization and
statistical learning via the alternating direction method of multipliers. Foundations and Trends®
in Machine Learning, 3 1–122.
Callaway, D. S. and Hiskens, I. A. (2011). Achieving controllability of electric loads. Proceedings of
the IEEE, 99 184–199.
Castro, D. D. and Meir, R. (2010). A convergent online single-time-scale actor-critic algorithm.
Journal of Machine Learning Research, 11 367–410.
Cattivelli, F. S., Lopes, C. G. and Sayed, A. H. (2008). Diffusion recursive least-squares for
distributed estimation over adaptive networks. IEEE Transactions on Signal Processing, 56 1865–
1877.
32

Chen, J. and Sayed, A. H. (2012). Diffusion adaptation strategies for distributed optimization and
learning over networks. IEEE Transactions on Signal Processing, 60 4289–4305.
Corke, P., Peterson, R. and Rus, D. (2005). Networked robots: Flying robot navigation using a
sensor net. Robotics Research 234–243.
Cortes, J., Martinez, S., Karatas, T. and Bullo, F. (2004). Coverage control for mobile sensing
networks. IEEE Transactions on Robotics and Automation, 20 243–255.
Dall’Anese, E., Zhu, H. and Giannakis, G. B. (2013). Distributed optimal power flow for smart
microgrids. IEEE Transactions on Smart Grid, 4 1464–1475.
Dann, C., Neumann, G., Peters, J. et al. (2014). Policy evaluation with temporal differences: A
survey and comparison. Journal of Machine Learning Research, 15 809–883.
Degris, T., White, M. and Sutton, R. (2012). Off-policy actor-critic. In International Conference on
Machine Learning.
Fax, J. A. and Murray, R. M. (2004). Information flow and cooperative control of vehicle formations.
IEEE Transactions on Automatic Control, 49 1465–1476.
Foerster, J., Assael, Y. M., de Freitas, N. and Whiteson, S. (2016). Learning to communicate with
deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems.
Foerster, J., Nardelli, N., Farquhar, G., Torr, P., Kohli, P., Whiteson, S. et al. (2017). Stabilising
experience replay for deep multi-agent reinforcement learning. arXiv preprint arXiv:1702.08887.
Goodfellow, I., Bengio, Y. and Courville, A. (2016). Deep learning. MIT press.
Gruslys, A., Azar, M. G., Bellemare, M. G. and Munos, R. (2017). The reactor: A sample-efficient
actor-critic architecture. arXiv preprint arXiv:1704.04651.
Gu, S., Lillicrap, T., Ghahramani, Z., Turner, R. E. and Levine, S. (2017). Q-prop: Sample-efficient
policy gradient with an off-policy critic. In International Conference on Learning Representations.
Gupta, J. K., Egorov, M. and Kochenderfer, M. (2017). Cooperative multi-agent control using
deep reinforcement learning. In International Conference on Autonomous Agents and Multi-agent
Systems.
Hu, J. and Wellman, M. P. (2003). Nash Q-learning for general-sum stochastic games. Journal of
Machine Learning Research, 4 1039–1069.
Jakovetic, D., Xavier, J. and Moura, J. M. (2011). Cooperative convex optimization in networked
systems: Augmented lagrangian algorithms with directed gossip communication. IEEE Transactions on Signal Processing, 59 3889–3902.
Kakade, S. M. (2002). A natural policy gradient. In Advances in Neural Information Processing
Systems.
Kar, S. and Moura, J. M. (2010). Distributed consensus algorithms in sensor networks: Quantized
data and random link failures. IEEE Transactions on Signal Processing, 58 1383–1400.
33

Kar, S., Moura, J. M. and Poor, H. V. (2013). QD-learning: A collaborative distributed strategy
for multi-agent reinforcement learning through consensus + innovations. IEEE Transactions on
Signal Processing, 61 1848–1862.
Kober, J. and Peters, J. (2012). Reinforcement learning in robotics: A survey. In Reinforcement
Learning. Springer, 579–610.
Konda, V. R. and Tsitsiklis, J. N. (2000). Actor-critic algorithms. In Advances in Neural Information
Processing Systems.
Kushner, H. J. and Clark, D. S. (1978). Stochastic approximation methods for constrained and
unconstrained systems. Springer Science & Business Media.
Kushner, H. J. and Yin, G. G. (2003). Stochastic approximation and recursive algorithms and applications. Springer, New York, NY.
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D. and
Graepel, T. (2017). A unified game-theoretic approach to multi-agent reinforcement learning.
arXiv preprint arXiv:1711.00832.
Lauer, M. and Riedmiller, M. (2000). An algorithm for distributed reinforcement learning in
cooperative multi-agent systems. In International Conference on Machine Learning.
Lewis, F. L., Zhang, H., Hengster-Movric, K. and Das, A. (2013). Cooperative control of multi-agent
systems: Optimal and adaptive design approaches. Springer Science & Business Media.
Li, Y. (2017). Deep reinforcement learning: An overview. arXiv preprint arXiv:1701.07274.
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D. and Wierstra, D.
(2016). Continuous control with deep reinforcement learning. In International Conference on
Learning Representations.
Littman, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. In
International Conference on Machine Learning.
Littman, M. L. (2001). Value-function reinforcement learning in Markov games. Cognitive Systems
Research, 2 55–66.
Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P. and Mordatch, I. (2017). Multi-agent actor-critic
for mixed cooperative-competitive environments. arXiv preprint arXiv:1706.02275.
Macua, S. V., Tukiainen, A., Hernández, D. G.-O., Baldazo, D., de Cote, E. M. and Zazo, S. (2017).
Diff-dac: Distributed actor-critic for multitask deep reinforcement learning. arXiv preprint
arXiv:1710.10363.
Mathkar, A. S. and Borkar, V. S. (2016). Nonlinear gossip. SIAM Journal on Control and Optimization, 54 1535–1557.
Metivier, M. and Priouret, P. (1984). Applications of a Kushner and Clark lemma to general
classes of stochastic algorithms. IEEE Transactions on Information Theory, 30 140–151.

34

Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D. and Kavukcuoglu,
K. (2016). Asynchronous methods for deep reinforcement learning. In International Conference
on Machine Learning.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A.,
Riedmiller, M., Fidjeland, A. K., Ostrovski, G. et al. (2015). Human-level control through
deep reinforcement learning. Nature, 518 529–533.
Movric, K. H. and Lewis, F. L. (2014). Cooperative optimal control for multi-agent systems on
directed graph topologies. IEEE Transactions on Automatic Control, 59 769–774.
Munos, R., Stepleton, T., Harutyunyan, A. and Bellemare, M. (2016). Safe and efficient off-policy
reinforcement learning. In Advances in Neural Information Processing Systems.
Nedic, A. and Ozdaglar, A. (2009). Distributed subgradient methods for multi-agent optimization.
IEEE Transactions on Automatic Control, 54 48–61.
Nedich, A., Olshevsky, A. and Shi, W. (2016). Achieving geometric convergence for distributed
optimization over time-varying graphs. arXiv preprint arXiv:1607.03218.
Neveu, J. (1975). Discrete-parameter martingales. Elsevier.
Omidshafiei, S., Pazis, J., Amato, C., How, J. P. and Vian, J. (2017). Deep decentralized multi-task
multi-agent reinforcement learning under partial observability. In International Conference on
Machine Learning.
Parisotto, E., Ba, J. L. and Salakhutdinov, R. (2015). Actor-mimic: Deep multi-task and transfer
reinforcement learning. arXiv preprint arXiv:1511.06342.
Peters, J. and Schaal, S. (2008). Natural actor-critic. Neurocomputing, 71 1180–1190.
Prasad, H., Prashanth, L. and Bhatnagar, S. (2014). Actor-critic algorithms for learning Nash
equilibria in n-player general-sum games. arXiv preprint arXiv:1401.2086.
Puterman, M. L. (2014). Markov Decision Processes: Discrete stochastic dynamic programming. John
Wiley & Sons.
Rabbat, M. and Nowak, R. (2004). Distributed optimization in sensor networks. In International
Symposium on Information Processing in Sensor Networks.
Ram, S. S., Nedić, A. and Veeravalli, V. V. (2010). Distributed stochastic subgradient projection
algorithms for convex optimization. Journal of Optimization Theory and Applications, 147 516–545.
Schulman, J., Moritz, P., Levine, S., Jordan, M. and Abbeel, P. (2015). High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02438.
Shalev-Shwartz, S., Shammah, S. and Shashua, A. (2016). Safe, multi-agent, reinforcement
learning for autonomous driving. arXiv preprint arXiv:1610.03295.
Shoham, Y., Powers, R. and Grenager, T. (2003). Multi-agent reinforcement learning: A critical
survey. Technical Report.
35

Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser,
J., Antonoglou, I., Panneershelvam, V., Lanctot, M. et al. (2016). Mastering the game of Go
with deep neural networks and tree search. Nature, 529 484–489.
Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D. and Riedmiller, M. (2014). Deterministic
policy gradient algorithms. In International Conference on Machine Learning.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T.,
Baker, L., Lai, M., Bolton, A. et al. (2017). Mastering the game of Go without human knowledge.
Nature, 550 354–359.
Sutton, R. S. and Barto, A. G. (1998). Reinforcement learning: An introduction. Cambridge: MIT
press.
Sutton, R. S., McAllester, D. A., Singh, S. P. and Mansour, Y. (2000). Policy gradient methods
for reinforcement learning with function approximation. In Advances in Neural Information
Processing Systems.
Teh, Y. W., Bapst, V., Czarnecki, W. M., Quan, J., Kirkpatrick, J., Hadsell, R., Heess, N.
and Pascanu, R. (2017). Distral: Robust multi-task reinforcement learning. arXiv preprint
arXiv:1707.04175.
Tsitsiklis, J., Bertsekas, D. and Athans, M. (1986). Distributed asynchronous deterministic and
stochastic gradient optimization algorithms. IEEE Transactions on Automatic Control, 31 803–812.
Tsitsiklis, J. N. and Van Roy, B. (1997). Analysis of temporal-diffference learning with function
approximation. In Advances in Neural Information Processing Systems.
Tsitsiklis, J. N. and Van Roy, B. (1999). Average cost temporal-difference learning. Automatica, 35
1799–1808.
Tu, S.-Y. and Sayed, A. H. (2012). Diffusion strategies outperform consensus strategies for distributed estimation over adaptive networks. IEEE Transactions on Signal Processing, 60 6217–6234.
Wang, X. and Sandholm, T. (2003). Reinforcement learning to play an optimal Nash equilibrium
in team Markov games. In Advances in Neural Information Processing Systems.
Wang, Z., Bapst, V., Heess, N., Mnih, V., Munos, R., Kavukcuoglu, K. and de Freitas, N. (2016).
Sample efficient actor-critic with experience replay. In International Conference on Learning
Representations.
Wilson, A., Fern, A., Ray, S. and Tadepalli, P. (2007). Multi-task reinforcement learning: A
hierarchical Bayesian approach. In International Conference on Machine Learning.
Xiao, L., Boyd, S. and Lall, S. (2005). A scheme for robust distributed sensor fusion based on
average consensus. In International Symposium on Information Processing in Sensor Networks.

36

A Proof for the Stability of Consensus Updates
As mentioned before, the stability of the updates in stochastic approximation is usually proved
separately. Here we provide the proof for the stability of the slower time scale update {ωti } in
Algorithm 1 and {zti } in Algorithm 2, i.e., Lemmas 5.1 and 5.4. In particular, we provide a sufficient
condition for the stability of the consensus-based SA updates following the spirit of the results
in Borkar and Meyn (2000) and Mathkar and Borkar (2016). We first state a main theorem for
stability and then verify that Lemmas 5.1 and 5.4 are two special cases of it.
Let N be the set of agents with |N | = N and xi ∈ Rd for any i ∈ N . Consider the consensus
update for xni ∈ Rd as6
X
n j
h
j io
i
cn (i, j) xn + γn hj (xn , Yn ) + Mn+1 , for any i ∈ N ,
(A.1)
xn+1
=
j∈N

where {Yn }n≥0 is an irreducible and aperiodic Markov chain over the finite set A. Let η denote
i

the stationary distribution of {Yn } and h (xn ) = EYn ∼η [hi (xn , Yn )] denote the expectation of hi (xn , Yn )
over η. Let xn = [(xn1 )> , · · · , (xnN )> ]> ∈ RdN , Cn = [cn (i, j)]N ×N , h = [(h1 )> , · · · , (hN )> ]> ∈ RdN , h(x) =
1

N

[(h )> , · · · , (h )> ]> ∈ RdN , and Mn = [(Mn1 )> , · · · , (MnN )> ]> ∈ RdN . Let {Fn } be the filtration with
Fn = σ (xm , Mm , Ym , Cm−1 , m ≤ n).
Assumption A.1.

We make the following assumptions:

(a.1) The consensus weight matrices {Cn } satisfy Assumption 4.3;
(a.2) hi : Rn × A → Rn is Lipschitz continuous in its first argument for any i ∈ N ;
(a.3) {Mn } is a martingale difference sequence satisfying




E kMn+1 k2 | Fn ≤ K · 1 + kxn k2 ,
for some K > 0;
(a.4) The difference ζn+1 = h(xn ) − h(xn , Yn ) satisfies


kζn+1 k2 ≤ K 0 · 1 + kxn k2 a.s.,
for some K 0 > 0;
(a.5) The stepsize sequence {γn } satisfies

P

n γn

= ∞ and

P

2
n γn

< ∞;

(a.6) Define hc : RdN → RdN as hc (x) = h(cx) · c−1 with some c > 0, and e
hc (y) : Rd → Rd be e
hc (y) =
hhc (1 ⊗y)i. Then e
hc (y) → h∞ (y) as c → ∞ uniformly on compact sets for some h∞ (y) : Rd → Rd .
Also, for some  < N −1/2 , B = {y | kyk < } contains a globally asymptotically stable attractor
of the ODE ẏ = h∞ (y).
6 To avoid possible confusion with the notation of continuous time t needed in the stability analysis, we use subscript
n to denote the iteration index in the proof of Theorem A.2.

37

Note that the definitions of hc and h∞ in (a.6) in Assumption A.1 are different from those in Mathkar
and Borkar (2016). Here we consider the averaged ODE in the consensus subspace for each agent,
while that reference considers the overall ODE associated with (A.1), i.e., define e
h : RdN → RdN
Q
n
−1
as e
h(cx) · c , where C∗ = limn m=1 Cm . In fact, from Nedic and
h(x) = C∗ h(x) and let h∞ (x) = limc e
Ozdaglar (2009); Nedich et al. (2016), the limit C∗ exists and has identical rows and rank one,
provided the sequence {Ct } satisfies Assumption 4.3. Therefore, the globally asymptotical stability
of the ODE ẋ = h∞ (x) (see Assumption (A5) in Mathkar and Borkar (2016)) does not hold for the
linear ODE we consider in the convergence proof of the critic steps in both algorithms. In contrast,
we can verify our condition (a.6) in Assumption A.1 later in the proof of Lemmas 5.1 and 5.4. We
then have the following theorem on the stability of the sequence {xn }.
Theorem A.2. Under Assumption A.1, the sequence {xn } generated from (A.1) is bounded almost
surely, i.e., supn kxni k < ∞ a.s. for any i ∈ N .

A.1

Proof of Theorem A.2

Let ϑc (y, t) denote the solution to the ODE
ẏ = e
hc (y), y(0) = y

(A.2)

We first have the following lemma, which is similar to Lemma 5 in Mathkar and Borkar (2016),
and thus we do not provide its proof here.
Lemma A.3. There exist constants c0 > 0 and T > 0 such that for all initial conditions y within the
sphere {y | kyk ≤ N −1/2 } and all c ≥ c0 , we have kϑc (y, t)k ≤ (1 − 0 ) · N −1/2 for t ∈ [T , T + 1], for some
0 < 0 < 1, where N is the number of agents.
Now, before stating the next set of lemmas, we introduce some notations and terminology. First,
P
by the convention adopted in Borkar and Meyn (2000), we define t0 = 0 and tn = ni=0 γi , n ≥ 0. Then
we define x(t), t ≥ 0 as x(tn ) = xn , n ≥ 0 with linear interpolation on each interval [tn , tn+1 ]. Moreover,
we let T0 = 0 and Tn+1 = min{tm : tm ≥ Tn + T } for any n ≥ 0. Then Tn+1 ∈ [Tn + T , Tn + T + supn γn ].
Let m(n) be such that Tn = tm(n) , for n ≥ 0. Define the piecewise continuous trajectory x̂(t) = x(t) · rn−1
for t ∈ [Tn , Tn+1 ), where rn = maxi∈N {kx(Tn )k, 1}. This implies that kx̂(Tn )k ≤ 1 for any n ≥ 0. We also
−
define x̂(Tn+1
) = x(Tn+1 ) · rn−1 , M̂k+1 = Mk+1 · rn−1 , and ζ̂k+1 = ζk+1 · rn−1 for k ∈ [m(n), m(n + 1)).
Note that {M̂k } is also a martingale difference sequence as {Mk }. We first establish boundedness
of E[kx̂(t)k2 ] as follows.
Lemma A.4. Under Assumption A.1, supt E[kx̂(t)k2 ] < ∞.

Proof. It suffices to show that supm(n)≤k<m(n+1) E[kx̂(tk )k2 ] < M for some M > 0 independent of n.
We first write the update of x̂(tk ) for k ∈ [m(n), m(n + 1)) in a compact form as

n
o
x̂(tk+1 ) = (Ck ⊗ I) x̂(tk ) + γk hrn [x̂(tk )] + M̂k+1 + ζ̂k+1 .
(A.3)
Note that the additional term ζ̂k+1 also satisfies E(kζ̂k+1 k2 | Fk ) ≤ K 0 · (1 + kx̂(tk )k2 ) by condition (a.4)
in Assumption A.1 since rn ≥ 1. Moreover, since Ck ⊗ I has bounded norm, it follows similarly as in
the proof for Lemma 4 on page 25 in Borkar (2008) that
E[kx̂(tk+1 )k2 ]1/2 ≤ E[kx̂(tk )k2 ]1/2 (1 + γk K1 ) + γk K2 ,
38

for some K1 , K2 > 0 and k ∈ [m(n), m(n + 1)). Then, by Grönwall inequality, we have the desired
boundedness of E[kx̂(t)k2 ].
By Lemma A.4, we immediately have the following result.
P
Lemma A.5 (Lemma 5 on page 25 in Borkar (2008)). The sequence { n−1
k=0 γk M̂k+1 } converges almost
surely.
We thus obtain the almost sure boundedness of the trajectory {x̂(t)}.

Lemma A.6. Under Assumption A.1, supt kx̂(t)k < ∞ a.s.

Proof. Recall the update in (A.3) and note that k(Ck ⊗ I)xk∞ ≤ kxk∞ since Ck is a row stochastic
matrix. Thus we have
kx̂(tk+1 )k∞ ≤kx̂(tk )k∞ + γk hrn [x̂(tk )] + M̂k+1 + ζ̂k+1
By iterating (A.4), we obtain
kx̂(tk+1 )k∞ ≤ kx̂(tm(n) )k∞ +
≤ kx̂(tm(n) )k∞ +

k−m(n)
X
l=0

k−m(n)
X


γm(n)+l hrn [x̂(tm(n)+l )]

l=0

h
γm(n)+l · K3 1 + x̂(tm(n)+l )

i
∞

+

∞

+ M̂m(n)+l+1
∞
k−m(n)
X

(A.4)

.

+ ζ̂m(n)+l+1
∞

γm(n)+l M̂m(n)+l+1

l=0

∞

,


∞

(A.5)

for some K3 > 0. The second inequality is due to the Lipschitz continuity of hrn and condition (a.4)
on ζn+1 , by the equivalence of vector norms. Moreover, by Lemma A.5, the third term on the RHS of
P
Pk−m(n)
(A.5) is bounded a.s. since { n−1
γm(n)+l ≤ T +supn γn < ∞
k=0 γk M̂k+1 } converges a.s. Recall that l=0
by definition of m(n) and Tn . Thus, there exist K4 , K5 > 0 such that
kx̂(tk+1 )k∞ ≤ K4 + K5

k−m(n)
X

γm(n)+l x̂(tm(n)+l )

l=0

∞

.

By discrete-time Grönwall inequality, we have
sup
m(n)≤k<m(n+1)

h

i
kx̂(tk )k∞ ≤ K4 · exp K5 · T + sup γn ,
n

(A.6)

where the RHS of (A.6) is a (random) constant independent of n. Hence by equivalence of vector
norms, we further obtain supt kx̂(t)k < ∞, which concludes the proof.
The stability of kx̂(t)k is essential in showing the convergence of the consensus update in (A.3).
For n ≥ 0, let y n (t) denote the trajectory of ẏ = e
hc (y) with c = rn and y n (Tn ) = hx̂(Tn )i, for t ∈ [Tn , Tn+1 ).
Then we have the following lemma.
Lemma A.7. Under Assumption A.1, limn supt∈[Tn ,Tn+1 ) kx̂(t) − 1 ⊗ y n (t)k = 0.

Proof. Since x̂(t) is bounded a.s. on [Tn , Tn+1 ), we can mimic our proofs for Theorems 4.6 and 4.10
to show the convergence of x̂(tk ) for k ∈ [Tn , Tn+1 ) as n → ∞. We will provide here only a sketch.
One can first show that over the set {supk kx̂(tk )k ≤ M} for any M > 0, limk kJ⊥ x̂(tk )k = 0. The
iteration of J⊥ x̂(tk ) has the form (similar to (5.6))
J⊥ x̂(tk+1 ) = [(I − 11> /N )Ck ⊗ I][J⊥ x̂(tk ) + γk yk+1 ],
39

(A.7)



where yk+1 = hrn [x̂(tk )] + M̂k+1 + ζ̂k+1 here. One can easily verify that E kyk+1 k2 I{supk kx̂(tk )k≤M} | Fk <
K6 for some K6 > 0, due to Lipschitz continuity of hrn and the conditions (a.3) and (a.4) in Assumption A.1. Hence, by similar arguments as in the proof of Lemma 5.3, we obtain limk kJ⊥ x̂(tk )k = 0
almost surely, i.e., the vector x̂(tk ) reaches consensus as k → ∞. Then we proceed to show the
convergence of the sequence {hx̂(tk )i}. Define ĥc : Rd × A → Rd as ĥc (y, Yk ) = hh(c · 1 ⊗ y) · c−1 i; then
the iteration can be written as follows
hx̂(tk+1 )i = hx̂(tk )i + γk · E(hyk+1 i | Fk ) + γk · ξk+1 = hx̂(tk )i + γk · ĥrn [hx̂(tk )i, Yk ] + γk · ξk+1 + γk · βk+1 ,
where ξk+1 = h(Ck ⊗ I)(yk+1 + γk−1 J⊥ x̂(tk )i − E(hyk+1 i | Fk ), βk+1 = E(hyk+1 i | Fk ) − ĥrn [hx̂(tk )i, Yk ], and
hyk+1 i = hhrn [x̂(tk )]i + M̂k+1 + hζ̂k+1 i. One can verify that {ξk+1 } is a martingale difference sequence


satisfying E kξt+1 k2 Ft,1 < K7 · (1 + khx̂(tk )ik2 ) for some K7 < ∞ over the set {supk kx̂(tk )k ≤ M}.
In addition, note that E(M̂k+1 | Fk ) = 0 and thus E(hyk+1 i | Fk ) = hh[x̂(tk ), Yk ]i · rn−1 . Thus we have
kβk+1 k ≤ L · kJ⊥ x̂(tk )k · rn−1 for some L < ∞ due to the Lipschitz continuity of h. Hence βk → 0 a.s.
since kJ⊥ x̂(tk )k → 0 a.s. and rn ≥ 1. Moreover, ĥrn [hx̂(tk )i, Yk ] is Lipschitz continuous in hx̂(tk )i.
Therefore, by Theorem B.2, we obtain that hx̂(tk )i → y n (t) as n → ∞, namely k → ∞. Further we
obtain that x̂i (tk ) → y n (t) for any i ∈ N , which concludes the proof following Theorem 2 in Chapter
2 of Borkar (2008).
Now suppose that kxni k → ∞ for some i ∈ N ; then there exists a subsequence of {nq } such that
kxi (Tnq )k → ∞ and thus kx(Tnq )k → ∞. Hence rnq → ∞. If rn > c0 ≥ 1, then kx̂(Tn )k = 1, and thus
ky n (Tn )k = khx̂(Tn )ik ≤ N −1/2 . By Lemma A.3, we have k1 ⊗ y n (Tn− )k = N 1/2 · ky n (Tn− )k ≤ 1 − 0 . Thus
−
by Lemma A.7, we have kx̂(Tn+1
)k < 1 − 00 for some 0 < 00 < 0 . Hence for rn > c0 and sufficiently
large n,
−
)k
kx(Tn+1 )k kx̂(Tn+1
=
< 1 − 00 .
kx(Tn )k
kx̂(Tn )k

It thus follows that if kx(Tn )k > 1, kx(Tk )k falls back to the unit ball at an exponential rate for k ≥ n.
The rest of the argument follows directly from the proof of Theorem 2 in Mathkar and Borkar
(2016), which concludes the proof.
Now we are ready to apply Theorem A.2 to prove Lemmas 5.1 and 5.4. We will return to the
notations in §4.

A.2

Proof of Lemma 5.1

The proof follows by verifying the conditions for Theorem A.2 to hold. Recall that the critic step in
(3.7) has the form


ωt+1 = (Ct ⊗ I) ωt + βω,t · yt+1 ,
with yt+1 = (δt1 φt> , · · · , δtN φt> )> ∈ RKN . Thus the terms corresponding to (A.1) are
hi (ωti , µit , st , at ) = E(δti φt> | Ft,1 ),

i
Mt+1
= δti φt> − E(δti φt> | Ft,1 ).

(A.8)
i

Since the Markov chain {(st , at )}t≥0 is irreducible and aperiodic given policy πθ , we have h (ωti , µit ) =
i
i
i
i
i
θ
Φ > Ds,a
θ [R −µt 1 +P Φωt −Φωt ]. By Lemma 5.2, it is established that {µt } is bounded a.s. Hence, over
40

the set {supt kµt k ≤ M} for any M > 0, there exists some K 0 > 0 such that kh(ωt , µt )−h(ωt , µt , st , at )k2 ≤
K 0 · (1 + kωt k2 ), since the Markov chain is finite. This verifies the condition (a.4) in Assumption
i
A.1. Moreover, since rt+1
and kφt k are uniformly bounded, E(kMt+1 k2 | Ft,1 ) ≤ K · (1 + kωt k2 ) is also
verified for some K > 0. More importantly, over the set {supt kµt k ≤ M}, h∞ (y) exists and has the
form
θ
h∞ (y) = lime
hc (y) = Φ > Ds,a
θ (P − I)Φy.
c

(A.9)

Clearly ẏ = h∞ (y) has origin as its globally asymptotically stable attractor (see the proof of Theorem
4.6 in §5.1). Hence we apply Theorem A.2 to conclude the proof.

A.3

Proof of Lemma 5.4

Recall that the critic step from (3.12), (3.13), and (3.16) has the compact form


zt+1 = (Ct ⊗ I) zt + βv,t · yt+1 ,

(A.10)

i
i
where zti = [µit , (λit )> , (vti )> ]> and yt = [(yt1 )> , · · · , (ytN )> ]> ∈ R(1+M+L)N . Here yt+1
denotes yt+1
=
>
>
>
i
i
i
i
i
>
[rt+1 − µt , (rt+1 − ft λt )ft , δt ϕt ] . Thus the terms corresponding to (A.1) are
i
hi (zti , st , at ) = E(yt+1
| Ft,1 ),

i
i
i
Mt+1
= yt+1
− E(yt+1
| Ft,1 ).

(A.11)

Furthermore, we have


i

h (zti ) = 



 i  i
−1
0
0
 µt   J (θ) 
  i   > s,a i 
 λt  +  F Dθ R  ,
0
−F> Ds,a
0
θ F
    > s i 
s
s
θ
>
>
0
Φ Dθ (P − I)Φ vti
−Φ Dθ 1
Φ Dθ Rθ

P
P
where J i (θ) = s∈S,a∈A dθ (s, a) · Ri (s, a) and Riθ (s) = a πθ (s, a)Ri (s, a). Therefore, one can verify that
both conditions (a.3) and (a.4) in Assumption A.1 are satisfied. In addition, h∞ (y) exists and has
the form


0
0
 −1



 · y.
0
−F> Ds,a
F
0
h∞ (y) = lime
hc (y) = 
θ

c
 > s
s
>
θ
−Φ Dθ 1
0
Φ Dθ (P − I)Φ
Clearly ẏ = h∞ (y) has origin as its globally asymptotically stable attractor (see the proof of Theorem
4.10 in §5.3), which completes the proof.

41

B
B.1

Technical Background
A Basic Result of Stochastic Approximation

For the sake of completeness, we reproduce here a key result from Borkar (2008) that has been used
repeatedly in our proofs. The results follow by specializing Corollary 8 and Theorem 9 on page
74-75 in Borkar (2008). We note that this is actually an extension of Theorem 2.1 and Theorem 2.2
in Borkar and Meyn (2000) to the case with irreducible Markovian state and diminishing noise in
the update. More general conclusions can also be found in Benaı̈m (1999); Kushner and Yin (2003).
Consider the n-dimensional stochastic approximation iteration
xt+1 = xt + γt [h(xt , Yt ) + Mt+1 + βt+1 ], t ≥ 0,

(B.1)

where γt > 0 and {Yt }t≥0 is a Markov chain on a finite set A.
Assumption B.1.

We make the following assumptions:

(a.1) h : Rn × A → Rn is Lipschitz continuous in its first argument;
(a.2) {Yt }t≥0 is an irreducible Markov chain with stationary distribution π;
P
P
(a.3) The stepsize sequence {γt } satisfies t γt = ∞ and t γt2 < ∞;
(a.4) {Mt } is a martingale difference sequence, i.e., E[Mt+1 | xτ , Mτ , Yτ , τ ≤ t] = 0, satisfying
that for some K > 0 and t ≥ 0




E kMt+1 k2 | xτ , Mτ , Yτ , τ ≤ t ≤ K · 1 + kxt k2 .
(a.5) The sequence {βt } is a bounded random sequence with βt → 0 almost surely as t → ∞.
Then the asymptotic behavior of the iteration (B.1) is related to the behavior of the solution to the
ODE
X
ẋ = h(x) =
π(i)h(x, i).
(B.2)
i

Suppose (B.2) has a unique globally asymptotically stable equilibrium x∗ , we then have the following two theorems.
Theorem B.2. Under Assumption B.1, if supt kxt k < ∞ a.s., we have xt → x∗ .
Theorem B.3. Under Assumption B.1, suppose that
lim

c→∞

h(cx)
= h∞ (x)
c

exists uniformly on compact sets for some h∞ ∈ C(Rn ). If the ODE ẏ = h∞ (y) has origin as the
unique globally asymptotically stable equilibrium, then
sup kxt k < ∞ a.s.
t

42

B.2

Kushner-Clark Lemma

We state here the well-known Kushner-Clark Lemma (Kushner and Clark, 1978; Metivier and
Priouret, 1984; Prasad et al., 2014) in the sequel.
Let Γ be an operator that projects a vector onto a compact set X ⊆ RN . Define a vector Γ̂ (·) as





 Γ [x + ηh(x)] − x 

Γ̂ [h(x)] = lim 
,




0<η→0 
η
for any x ∈ X and with h : X → RN continuous. Consider the following recursion in N dimensions
n
o
xt+1 = Γ xt + γt [h(xt ) + ξt + βt ] .
(B.3)
The ODE associated with (B.3) is given by
ẋ = Γ̂ [h(x)].
Assumption B.4.

(B.4)

We make the following assumptions:

(a.1) h(·) is a continuous RN -valued function.
(a.2) The sequence {βt }, t ≥ 0 is a bounded random sequence with βt → 0 almost surely as
t → ∞.
P
(a.3) The stepsizes γt , t ≥ 0 satisfy γt → 0 as t → ∞ and t γt = ∞.
(a.4) The sequence ξt , t ≥ 0 satisfies for any  > 0


n
X


lim P sup
γτ ξτ ≥  = 0.
t
n≥t

τ=t

Then the Kushner-Clark Lemma says the following.
Theorem B.5. Under Assumption B.4, suppose that the ODE (B.4) has a compact set K∗ as its set
of asymptotically stable equilibria. Then xt in (B.3) converges almost surely to K∗ as t → ∞.

43

C

Comparison with Existing Work on Multi-Agent Systems and MARL

In this section, we compare both our model and algorithms with related work on multi-agent systems
and collaborative MARL in details.
Our framework of networked multi-agent systems finds a broad range of applications in
distributed cooperative control problems, including formation control of unmanned vehicles (Fax
and Murray, 2004), cooperative navigation of robots (Corke et al., 2005), load management in
energy networks (Dall’Anese et al., 2013), and flocking of mobile sensor networks (Cortes et al.,
2004), etc. Previously, the collective goal of the multi-agent system is to either reach a stable
and consensus state for all agents (Fax and Murray, 2004; Corke et al., 2005), or solve a static
optimization problem in a distributed fashion (Dall’Anese et al., 2013; Nedic and Ozdaglar, 2009).
In the first line of work, including formation control and consensus problems, the objective is not
formulated explicitly as an optimization problem, and most of the work focuses on continuous-time
dynamic systems. Whereas in the second line of work, the problem is approached in a static setting,
in the sense that the optimization objective is deterministic and there is no control input affecting
the transition of the system, see recent efforts in Nedic and Ozdaglar (2009); Agarwal and Duchi
(2011); Jakovetic et al. (2011); Tu and Sayed (2012); Chen and Sayed (2012). In contrast, we here
model the interaction of multiple agents and evolution of the system as an MDP, a dynamic setting,
and explicitly use the network-wide long-term return as the collaborative goal of all agents. In this
regard, our framework is pertinent to the cooperative/distributed optimal control problems (Lewis
et al., 2013; Movric and Lewis, 2014), but focuses on the discrete-time setting and falls into the
realm of reinforcement learning, where the model of the system may be unknown. One recent
work (Macua et al., 2017) for multi-task RL, which is almost concurrent to ours, is also based on
the model with networked agents. Nonetheless, the MDP problem solved by different agents are
totally decoupled, which excludes the work from the realm of MARL with interactive agents as we
consider here.
Our framework also departs from the existing framework on collaborative MARL models in
the following aspects. In contrast to the canonical multi-agent MDP (MMDP) model proposed in
Boutilier (1996); Lauer and Riedmiller (2000), our model allows the agents to exchange information
over a communication network with possibly sparse connectivity at each agent. This improves
the scalability of the multi-agent model with a high population of agents, which is one of the
long-standing challenges in general MARL problems (Shoham et al., 2003). Moreover, we allow
heterogeneous agents to have various individual reward functions, while the canonical MMDP
assumes a common reward function for all agents. The latter setting greatly simplifies the problem
since no information exchange among agents is necessary to approximate the value function for
each agent. Our model not only fits in the multi-task setting which has gained increasing popularity
in MARL (Omidshafiei et al., 2017; Teh et al., 2017), but also applies to the general multi-agent RL
setting. One of the few models that also consider heterogeneous reward functions in collaborative
MARL is Kar et al. (2013), where the global action is assumed to be actuated by a remote controller,
but in our case, the agents are fully decentralized and have local control capabilities. It is also
worth noting that our model generalizes the team Markov game model for collaborative MARL,
see Littman (2001); Wang and Sandholm (2003); Arslan and Yüksel (2017), where all agents have
individual action sets but share a common payoff function as in the canonical MMDP.
Moreover, our algorithms designed for networked MMDP are distinct from the existing collaborative MARL algorithms in the following aspects. First, our MARL algorithms belong to the

44

type of actor-critic algorithms, whereas several of the existing MARL algorithms are designed
based on Q-learning type (critic-based) algorithms only (Boutilier, 1996; Lauer and Riedmiller,
2000; Kar et al., 2013). Moreover, these algorithms assume either the rewards are common to all
agents (Boutilier, 1996; Lauer and Riedmiller, 2000), or there exists a remote central controller
to take actions for the agents (Kar et al., 2013). More recently, some actor-critic type MARL algorithms with distributed/decentralized structures have gained increasing attention (Gupta et al., 2017;
Lowe et al., 2017; Omidshafiei et al., 2017). They are developed for more complicated settings
where both cooperation and competition may appear among agents. However, they all rely on a
central controller to perform the critic step, which are closer to the hierarchical structure rather
than the fully decentralized structure we consider here. Second, our algorithms apply function
approximation to handle the setting with massively large state and action spaces, while enjoying
theoretical guarantees for convergence as we show in §4. However, the existing collaborative MARL
algorithms are either guaranteed to converge only for tabular cases (Hu and Wellman, 2003; Wang
and Sandholm, 2003; Kar et al., 2013; Prasad et al., 2014), or only have empirical convergence
when function approximation is applied (Foerster et al., 2016; Gupta et al., 2017; Lowe et al., 2017;
Omidshafiei et al., 2017; Foerster et al., 2017; Lanctot et al., 2017). The recent work on multi-task
RL with networked agents (Macua et al., 2017) also focuses on empirical results only, with no
complete convergence analysis.

45

