# Scalable Multi-Agent Reinforcement Learning with General Utilities

Donghao Ying Department of Industrial Engineering and Operations Research,
University of California at Berkeley. Email:
<EMAIL_ADDRESS>Yuhao Ding∗ Alec Koppel J.P. Morgan
AI Research. Email<EMAIL_ADDRESS>Javad Lavaei∗

###### Abstract

We study the scalable multi-agent reinforcement learning (MARL) with general
utilities, defined as nonlinear functions of the team’s long-term state-action
occupancy measure. The objective is to find a localized policy that maximizes
the average of the team’s local utility functions without the full
observability of each agent in the team. By exploiting the spatial correlation
decay property of the network structure, we propose a scalable distributed
policy gradient algorithm with shadow reward and localized policy that
consists of three steps: (1) shadow reward estimation, (2) truncated shadow
Q-function estimation, and (3) truncated policy gradient estimation and policy
update. Our algorithm converges, with high probability, to
$\epsilon$-stationarity with $\widetilde{\mathcal{O}}(\epsilon^{-2})$ samples
up to some approximation error that decreases exponentially in the
communication radius. This is the first result in the literature on multi-
agent RL with general utilities that does not require the full observability.

##  1 INTRODUCTION

Many decision-making problems take a form beyond the classic cumulative
reward, such as apprenticeship learning [1], diverse skill discovery [2], pure
exploration [3], and state marginal matching [4], among others. Such problems
can be abstracted as reinforcement Learning (RL) with general utilities [5,
6], which focus on finding a policy to maximize a nonlinear function of the
induced state-action occupancy measure. It generalizes the standard RL in
which the objective is only an inner product between the state-action
occupancy measure induced by the policy and a policy-independent reward for
each state-action pair.

Beyond the single agent RL, consider the multi-agent problem where different
agents need to interact to obtain a favorable outcome by finding a decision
policy that maximizes the global accumulation of all agent’s general utility.
This setting captures a wide range of applications, e.g. epidemics [7], social
networks [8], finance [9], intelligent transportation [10] and wireless
communication networks [11]. Recently, [12] proposed a new mechanism for
cooperation that allows agents to incorporate general utilities for multi-
agent RL (MARL) with common payoffs among agents. To enable the
decentralization of agents’ policies under general utilities, [12] defines
local occupancy measure of each agent as a marginalization of the global
occupancy measure, and it defines the local general utility of the agent as an
arbitrary function of its local occupancy measure. Based on these definitions,
[12] derives a policy gradient-based algorithm, namely Decentralized Shadow
Reward Actor-Critic, where each agent estimates its policy gradient based on
local information and communications with its neighbors.

However, their approach assumes the full observability, i.e., each agent
should have access to the global states and actions of the team. Such
assumption has two limitations. First, it is expensive and sometimes
impossible to communicate with all agents in the team when the size of the
team is large. In addition, full observability also implies that the policy
and critic networks in this approach depend on the global states and actions
of the team, which may be a barrier to effective decentralized implementation
in practice. Moreover, even if individual state and action spaces are often
small, the size of global state and action spaces can be exponentially large
in the number of agents, which can be fundamentally intractable for large
numbers of agents [13].

To address these issues, we aim to develop a scalable algorithm for multi-
agent RL with general utilities without the full observability assumption.
Inspired by the localization idea proposed in [14], our work makes the
following contributions:

  * •

We derive a truncated policy gradient estimator using the shadow reward and
the localized policy for MARL with general utilities. We further establish the
approximation error of the proposed truncated policy gradient estimator based
on the spatial correlation decay assumptions;

  * •

We propose a distributed policy gradient algorithm with shadow reward and
localized policy that consists of three pieces: (1) shadow reward estimation,
(2) truncated shadow Q-function estimation, and (3) truncated policy gradient
estimation and policy update.

  * •

We establish that, with high probability, our algorithm requires
$\widetilde{\mathcal{O}}(\epsilon^{-2})$ samples to achieve
$\epsilon$-stationarity with the error term
$\mathcal{O}\left(n\phi_{0}^{2\kappa}\right)$, where $\phi_{0}\in(0,1)$, $n$
is the number of agents, ${\mathcal{N}}$ is the set of agents.

It is critical to note that the operating hypotheses we require for developing
a localized algorithm for MARL are related to, but distinct from [14] in the
following sense: we assume the transition dynamics and policies of all agents
are globally correlated and the correlation satisfies a spatial decay
property. In contrast, the agents are considered to act on their own with
their transitions only affected by the nearest neighbors in [14].

###  1.1 Notations

For a finite set $\mathcal{S}$, let $\left|\mathcal{S}\right|$ denote its
cardinality and let
$\operatorname{TV}(\mu,\mu^{\prime}):=\sup_{A\subset\mathcal{S}}|\mu(A)-\mu^{\prime}(A)|$
be the total variation distance between two probability distributions $\mu$
and $\mu^{\prime}$ on $\mathcal{S}$. When the variable $s$ follows the
distribution $\xi$, we write it as $s\sim\xi$. Let $\mathbb{E}[\cdot]$ and
$\mathbb{E}[\cdot\mid\cdot]$, respectively, denote the expectation and
conditional expectation of a random variable. Let $\mathbb{R}$ denote the set
of real numbers. For vectors $x$ and $y$, we use $x^{\top}$ to denote the
transpose of $x$ and use $\langle x,y\rangle$ to denote the inner product
$x^{\top}y$. We use the convention that $\|x\|_{1}=\sum_{i}|x_{i}|$,
$\|x\|:=\|x\|_{2}=\sqrt{\sum_{i}x_{i}^{2}}$, and
$\|x\|_{\infty}=\max_{i}|x_{i}|$.

##  2 PROBLEM FORMULATION

Consider an infinite-horizon Markov Decision Process (MDP) over a finite state
space $\mathcal{S}$ and a finite action space $\mathcal{A}$ with a discount
factor $\gamma\in[0,1)$. Let $\xi$ be the initial distribution. A policy $\pi$
is a function that specifies the decision rule of the agent, i.e., the agent
takes action $a\in\mathcal{A}$ with probability $\pi(a|s)$ in state
$s\in\mathcal{S}$. When action $a$ is taken, the transition to the next state
$s^{\prime}$ from state $s$ follows the probability distribution
$s^{\prime}\sim\mathbb{P}(\cdot|s,a)$. In standard RL, the objective is to
maximize the expected (discounted) cumulative reward, i.e.,

$\max_{\pi}V^{\pi}(r):=\mathbb{E}\left[\sum_{k=0}^{\infty}\gamma^{k}r\left(s^{k},a^{k}\right)\bigg{|}a^{k}\sim\pi(\cdot|s^{k}),s^{0}\sim\xi\right],$
(1)

where $r(\cdot,\cdot)$ denotes the reward function and the expectation is
taken over all possible trajectories. The value function can also be written
as $V^{\pi}(r)=\left\langle r,\lambda^{\pi}\right\rangle$, where
$\lambda^{\pi}$ is the discounted state-action occupancy measure defined as

$\lambda^{\pi}(s,a)=\sum_{k=0}^{\infty}\gamma^{k}\mathbb{P}\left(s^{k}=s,a^{k}=a\big{|}a^{k}\sim\pi(\cdot|s^{k}),s^{0}\sim\xi\right),\forall(s,a).$
(2)

We consider a more general problem where the objective is to maximize a
general function of $\lambda^{\pi}$, namely

$\max_{\pi}f(\lambda^{\pi}),$ (3)

where $f:\mathbb{R}^{|\mathcal{S}|\cdot|\mathcal{A}|}\rightarrow\mathbb{R}$
can be a possibly nonlinear function. Such an objective arises in various
applications and is commonly referred to as a general utility [12, 15]. For
instance, in apprenticeship learning [1], the objective is
$f(\lambda^{\pi})=-\operatorname{dist}(\lambda^{\pi},\lambda_{e})$, where
$\lambda_{e}$ corresponds to the expert demonstration and
$\operatorname{dist}(\cdot,\cdot)$ is a distance function. In maximum entropy
exploration [3], $f(\cdot)$ refers to the entropy function such that
$f(\lambda^{\pi})=-\sum_{s}d^{\pi}(s)\log d^{\pi}(s)$, where
$d^{\pi}(s)=(1-\gamma)\sum_{a}\lambda^{\pi}(s,a)$ is the discounted state
occupancy measure.

In this work, we study the decentralized version of (3), where the system is
decentralized among a network of agents associated with a graph
$\mathcal{G}=(\mathcal{N},\mathcal{E})$ (not densely connected). The vertex
set $\mathcal{N}=\\{1,2,\dots,n\\}$ denotes the set of $n$ agents and the edge
set $\mathcal{E}$ prescribes the communication links among agents. Let
$d(i,j)$ be the distance between agents $i$ and $j$ on $\mathcal{G}$, defined
as the length of the shortest path between them. For $\kappa\geq 0$, we define
$\mathcal{N}^{\kappa}_{i}=\\{j\in{\mathcal{N}}|d(i,j)\leq\kappa\\}$ as the set
of agents in the neighborhood of radius $\kappa$ of agent $i$, with the
shorthand notations
$\mathcal{N}^{\kappa}_{-i}:={\mathcal{N}}\backslash\mathcal{N}^{\kappa}_{i}$
and
$-i:={\mathcal{N}}\backslash{\mathcal{N}}_{i}^{0}={\mathcal{N}}\backslash\\{i\\}$.
The details of the decentralization are as follows:

#### Space Decomposition

The global state and action spaces are the product of local spaces, i.e.,
$\mathcal{S}=\mathcal{S}_{1}\times\mathcal{S}_{2}\times\cdots\times\mathcal{S}_{n}$,
$\mathcal{A}=\mathcal{A}_{1}\times\mathcal{A}_{2}\times\cdots\times\mathcal{A}_{n}$,
meaning that for every $s\in\mathcal{S}$ and $a\in\mathcal{A}$, we can write
$s=(s_{1},s_{2},\dots,s_{n})$ and $a=(a_{1},a_{2},\dots,a_{n})$. For each
subset ${{\mathcal{N}}}^{\prime}\subset{\mathcal{N}}$, we use
$(s_{{{\mathcal{N}}}^{\prime}},a_{{{\mathcal{N}}}^{\prime}})$ to denote the
state-action pair for agents in ${{\mathcal{N}}}^{\prime}$. We assume that
each agent has direct access to its own states and actions while accessing
other agents’ information requires communications.

#### Transition Decomposition

Given the current global state $s$ and action $a$, the local states in the
next period are independently generated, i.e.,
$\mathbb{P}(s^{\prime}|s,a)=\prod_{i\in\mathcal{N}}\mathbb{P}_{i}(s_{i}^{\prime}|s,a)$,
$\forall s^{\prime}\in\mathcal{S}$, where $\mathbb{P}_{i}$ denotes the local
transition probability.

#### Policy Factorization

The global policy can be decomposed as
$\pi(a|s)=\prod_{i\in\mathcal{N}}\pi^{i}\left(a_{i}|s_{\mathcal{N}^{\kappa}_{i}}\right),\forall(s,a)$,
i.e., given global state $s$, each agent $i$ acts independently according to
its local policy $\pi^{i}$, which depends on the state of agents in
$\mathcal{N}^{\kappa}_{i}$. For the policy parameterization, we assume that
the local policy of agent $i$ is parameterized by $\theta_{i}$, and therefore
one can write
$\pi(a|s)=\pi_{\theta}(a|s)=\prod_{i\in\mathcal{N}}\pi_{\theta_{i}}^{i}\left(a_{i}|s_{\mathcal{N}^{\kappa}_{i}}\right)$,
where $\theta=(\theta_{1},\theta_{2},\dots,\theta_{n})\in\Theta$ is the global
parameter.

#### Local Utility

For each agent $i$, define its local discounted state-action occupancy measure
as

$\lambda^{\pi}_{i}(s_{i},a_{i})=\sum_{k=0}^{\infty}\gamma^{k}\mathbb{P}\left(s^{k}_{i}=s_{i},a^{k}_{i}=a_{i}\big{|}a^{k}\sim\pi(\cdot|s^{k}),s^{0}\sim\xi\right),\forall(s_{i},a_{i}),$
(4)

which can be viewed as the marginalization of the global occupancy measure,
i.e.,
$\lambda^{\pi}_{i}(\hat{s}_{i},\hat{a}_{i})=\sum_{s_{i}=\hat{s}_{i},a_{i}=\hat{a}_{i}}\lambda^{\pi}(s,a)$.
Then, the global utility function $f(\cdot)$ can be written as the average of
local utilities, i.e.,
$f(\lambda^{\pi})=1/n\times\sum_{i\in\mathcal{N}}f_{i}(\lambda^{\pi}_{i})$,
where
$f_{i}:\mathbb{R}^{|\mathcal{S}_{i}|\cdot|\mathcal{A}_{i}|}\rightarrow\mathbb{R}$
is a function of the local occupancy measure $\lambda^{\pi}_{i}$ and is
private to agent $i$. Thus, under the parameterization $\pi_{\theta}$, (3) can
be rewritten as

$\max_{\theta\in\Theta}F(\theta),\text{ where
}F(\theta):=f(\lambda^{{\pi_{\theta}}})=\frac{1}{n}\cdot\sum_{i\in\mathcal{N}}f_{i}(\lambda^{\pi_{\theta}}_{i}).$
(5)

Finally, we remark that, by choosing all $f_{i}(\cdot)$ to be linear, (5)
reduces to standard MARL, where each agent $i$ is associated with a local
reward function
$r_{i}:\mathcal{S}_{i}\times\mathcal{A}_{i}\rightarrow\mathbb{R}$ and the
global reward is defined as
$r(s,a):=1/n\times\sum_{i\in\mathcal{N}}r_{i}(s_{i},a_{i})$.

##  3 Truncated Policy Gradient Algorithm with Shadow Reward

In RL with cumulative reward, the policy gradient theorem [16] applies to
computing the gradient of the value function:

$\displaystyle\nabla_{\theta}V^{\pi_{\theta}}(r)$
$\displaystyle=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi_{\theta}},a\sim{\pi_{\theta}}(\cdot|s)}\left[\psi_{\theta}(a|s)\cdot
Q^{\pi_{\theta}}(r;s,a)\right],$ (6)
$\displaystyle=\mathbb{E}\left[\sum_{k=0}^{\infty}\gamma^{k}\psi_{\theta}(a^{k}|s^{k})\cdot
Q^{\pi_{\theta}}(r;s^{k},a^{k})\bigg{|}a^{k}\sim{\pi_{\theta}}(\cdot|s^{k}),s^{0}\sim\xi\right],$

where
$\psi_{\theta}(\cdot|\cdot):=\nabla_{\theta}\log{\pi_{\theta}}(\cdot|\cdot)$
denotes the score function, and $Q^{\pi}(r;s,a)$ is the state-action value
function (Q-function) under reward $r(\cdot,\cdot)$, defined as

$Q^{\pi}(r;s,a)=\mathbb{E}\left[\sum_{k=0}^{\infty}\gamma^{k}r\left(s^{k},a^{k}\right)\bigg{|}a^{k}\sim\pi(\cdot|s^{k}),s^{0}=s,a^{0}=a\right].$
(7)

However, for objective (5) with general utilities, this elegant result no
longer holds. Instead, we have the following lemma.

######  Lemma 1.

For every policy ${\pi_{\theta}}$, it holds that

$\nabla_{\theta}F(\theta)=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi_{\theta}},a\sim{\pi_{\theta}}(\cdot|s)}\left[\psi_{\theta}(a|s)\cdot
Q^{\pi_{\theta}}_{f}(s,a)\right],$ (8)

where
$Q^{\pi_{\theta}}_{f}(\cdot,\cdot):=Q^{\pi_{\theta}}(r^{\pi_{\theta}};\cdot,\cdot)$
is the shadow Q-function and
$r^{\pi_{\theta}}:=\nabla_{\lambda}f(\lambda^{\pi_{\theta}})\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{A}|}$
is the shadow reward associated with policy ${\pi_{\theta}}$.

###### Proof.

For value functions with cumulative reward, we observe the relation
$\nabla_{\theta}V^{\pi_{\theta}}(r)=\nabla_{\theta}\left\langle
r,\lambda^{\pi_{\theta}}\right\rangle=\left\langle
r,\nabla_{\theta}\lambda^{\pi_{\theta}}\right\rangle$. Thus, by the chain
rule, we have that

$\nabla_{\theta}F(\theta)=\nabla_{\theta}f(\lambda^{\pi_{\theta}})=\left\langle\nabla_{\lambda}f(\lambda^{\pi_{\theta}}),\nabla_{\theta}\lambda^{\pi_{\theta}}\right\rangle=\nabla_{\theta}V^{\pi_{\theta}}(r^{\pi_{\theta}}),$
(9)

which completes the proof by the policy gradient theorem. ∎

In the decentralized formulation (5), for each agent $i$, let
$r^{\pi_{\theta}}_{i}:=\nabla_{\lambda_{i}}f_{i}(\lambda^{\pi_{\theta}}_{i})\in\mathbb{R}^{|\mathcal{S}_{i}|\times|\mathcal{A}_{i}|}$
be the local shadow reward, which only depends on the local state and action
for a given policy ${\pi_{\theta}}$, and we define the local shadow Q-function
as $Q_{i}^{\pi_{\theta}}(s,a):=Q^{\pi_{\theta}}(r^{\pi_{\theta}}_{i};s,a)$.
Then, it is clear that
$r^{\pi_{\theta}}=1/n\times\sum_{i\in{\mathcal{N}}}r^{\pi_{\theta}}_{i}$ and
$Q_{f}^{\pi_{\theta}}(s,a)=1/n\times\sum_{i\in{\mathcal{N}}}Q_{i}^{\pi_{\theta}}(s,a)$,
and the gradient of $F(\theta)$ with respect to agent $i$’s local parameter
$\theta_{i}$ can be written as

$\nabla_{\theta_{i}}F(\theta)=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi_{\theta}},a\sim{\pi_{\theta}}(\cdot|s)}\left[\psi_{\theta_{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\cdot\frac{1}{n}\sum_{j\in{\mathcal{N}}}Q^{\pi_{\theta}}_{j}(s,a)\right],$
(10)

where we use the policy factorization to derive that
$\nabla_{\theta_{i}}\log{\pi_{\theta}}(a|s)=\nabla_{\theta_{i}}\log{\pi_{\theta_{i}}^{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})=:\psi_{\theta_{i}}(a_{i}|s)$,
and we refer to $\psi_{\theta_{i}}(\cdot|\cdot)$ as the local score function.
Thus, updating the local parameter $\theta_{i}$ with the gradient (10)
requires knowing the global state and action as well as the shadow Q-functions
of all agents, which can be inefficient in large networks due to the
communication cost. In the remainder of the section, we show that an accurate
gradient estimator can be designed for all agents while only local
communications with neighbors are required under some correlation decay
assumptions.

###  3.1 Spatial Correlation Decay Assumption

Following [17], we assume that a form of correlation decay property holds for
the transition probability [18, 19].

######  Assumption 1.

For a matrix $M\in\mathbb{R}^{n\times n}$ whose $(i,j)$ entry is defined as

$M_{ij}=\sup_{s_{j},a_{j},s_{j}^{\prime},a_{j}^{\prime},s_{-j},a_{-j}}\operatorname{TV}\left(\mathbb{P}_{i}\left(\cdot|s_{j},s_{-j},a_{j},a_{-j}\right),\mathbb{P}_{i}\left(\cdot|s_{j}^{\prime},s_{-j},a_{j}^{\prime},a_{-j}\right)\right),$
(11)

assume that there exists $\beta\geq 0$ such that

$\max_{i\in{\mathcal{N}}}\sum_{j\in{\mathcal{N}}}e^{\beta
d(i,j)}M_{ij}\leq\rho,$ (12)

with $\rho<1/\gamma$, where $\gamma$ is the discount factor.

By definition, the element $M_{ij}$ characterizes the maximum level of impact
of agent $j$’s state and action on the local transition probability of agent
$i$. Then, Assumption 1 mainly requires that such impacts decrease
exponentially with respect to the distance between agents. Such a decay is
usually typical in engineered systems with large networks, e.g., in wireless
communication where the strength of signals decreases exponentially with the
distance [20, 21].

###  3.2 Truncated Shadow Q-function

We first introduce the notion of exponential decay for Q-functions [14], which
is a form of correlation decay property.

######  Definition 1.

For $c\geq 0$ and $\phi\in(0,1)$, the $(c,\phi)$-exponential decay property
holds if, for every policy $\pi_{\theta}$, agent $i$, and state-action pairs
$(s,a),(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}$ with
$s_{\mathcal{N}^{\kappa}_{i}}=s^{\prime}_{\mathcal{N}^{\kappa}_{i}}$,
$a_{\mathcal{N}^{\kappa}_{i}}=a^{\prime}_{\mathcal{N}^{\kappa}_{i}}$, the
local shadow Q-function satisfies

$\left|Q_{i}^{\pi_{\theta}}(s,a)-Q_{i}^{\pi_{\theta}}(s^{\prime},a^{\prime})\right|\leq
c\phi^{\kappa}.$ (13)

The exponential decay property holds when the dependency of each agent’s local
shadow Q-function on other agents’ states and actions exponentially decreases
with respect to their distances. Motivated by [14] and [19], for every $i$, we
define
$\widehat{Q}^{\pi_{\theta}}_{i}:\mathcal{S}_{\mathcal{N}^{\kappa}_{i}}\times\mathcal{A}_{\mathcal{N}^{\kappa}_{i}}\rightarrow\mathbb{R}$
to be agent $i$’s truncated shadow Q-function, depending only on the states
and actions of agents in the neighborhood $\mathcal{N}^{\kappa}_{i}$:

$\displaystyle\widehat{Q}^{\pi_{\theta}}_{i}(s_{\mathcal{N}^{\kappa}_{i}},a_{\mathcal{N}^{\kappa}_{i}}):=Q^{\pi_{\theta}}_{i}(s_{\mathcal{N}^{\kappa}_{i}},\bar{s}_{\mathcal{N}^{\kappa}_{-i}},a_{\mathcal{N}^{\kappa}_{i}},\bar{a}_{\mathcal{N}^{\kappa}_{-i}}),$
(14)

for every
$(s_{\mathcal{N}^{\kappa}_{i}},a_{\mathcal{N}^{\kappa}_{i}})\in\mathcal{S}_{\mathcal{N}^{\kappa}_{i}}\times\mathcal{A}_{\mathcal{N}^{\kappa}_{i}}$,
where
$(\bar{s}_{\mathcal{N}^{\kappa}_{-i}},\bar{a}_{\mathcal{N}^{\kappa}_{-i}})$ is
any fixed state-action pair for the agents in $\mathcal{N}^{\kappa}_{-i}$.
That is, the estimator
$\widehat{Q}^{\pi_{\theta}}_{i}(s_{\mathcal{N}^{\kappa}_{i}},a_{\mathcal{N}^{\kappa}_{i}})$
can be viewed as an approximate of the true shadow Q-function
$Q^{\pi_{\theta}}_{i}(s,a)$ by taking arbitrary values for
$(s_{\mathcal{N}^{\kappa}_{-i}},a_{\mathcal{N}^{\kappa}_{-i}})$. Compared with
$Q^{\pi_{\theta}}_{i}$, the estimator $\widehat{Q}^{\pi_{\theta}}_{i}$ depends
on much smaller state and action spaces, and it is thus easy to estimate and
store.

When the $(c,\phi)$-exponential decay property holds for Q-functions, it can
be intuitively understood that the accuracy of this approximation has the
order $\mathcal{O}(\phi^{\kappa})$. The following lemma shows that, when
Assumption 1 holds and the shadow reward is universally bounded, the
exponential decay property is satisfied. We are thus capable of proving that
$\widehat{Q}^{\pi_{\theta}}_{i}$ is a satisfactory approximation of
$Q^{\pi_{\theta}}_{i}$.

######  Lemma 2.

Suppose that Assumption 1 holds and there exists $M_{f}>0$ such that
$\|\nabla_{\lambda_{i}}f_{i}(\lambda_{i}^{\pi_{\theta}})\|_{\infty}\leq
M_{f}$, $\forall i\in\mathcal{V},\theta\in\Theta$. Then, (I) the
$(c_{0},\phi_{0})$-exponential decay property holds with
$(c_{0},\phi_{0})=\left(\frac{2\gamma\rho
M_{f}}{1-\gamma\rho},e^{-\beta}\right)$, (II) the truncated shadow Q-function
satisfies
$\underset{s,a}{\sup}\left|\widehat{Q}^{\pi_{\theta}}_{i}(s_{\mathcal{N}^{\kappa}_{i}},a_{\mathcal{N}^{\kappa}_{i}})-Q^{\pi_{\theta}}_{i}(s,a)\right|\leq
c_{0}\phi_{0}^{\kappa}$.

Under the bounded gradient assumption, we can treat the shadow Q-functions as
standard Q-functions with bounded reward functions. We refer the reader to
[17] for the proof of part (I) in Lemma 2. Then, part (II) follows directly
from the definition of the exponential decay property. We note that the set of
all possible state-action occupancy measures forms a convex polytope in
$\mathbb{R}^{|\mathcal{S}|\times|\mathcal{A}|}$ and is therefore a compact
set. Thus, requiring the existence of $M_{f}>0$ in Lemma 2 is not a
restrictive assumption and it naturally holds if the gradient
$\nabla_{\lambda}f(\lambda)$ is a continuous mapping on the set of occupancy
measures. We additionally remark that a faster rate of the exponential decay
property may be proved under extra assumptions, e.g., mixing properties of the
underlying Markov chain [14].

###  3.3 Truncated Policy Gradient Estimator

In this section, we introduce how the exponential decay property can help
design scalable algorithms.

As mentioned earlier, the major challenge in employing the exact policy
gradient (10) comes from obtaining the global state-action pairs and the local
shadow Q-functions of all agents, which may incur high costs in large
networks. Instead, we consider the following truncated policy gradient
estimator:

$\displaystyle\widehat{g}_{i}(\theta)=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi_{\theta}},a\sim{\pi_{\theta}}(\cdot|s)}\bigg{[}{\psi}_{\theta_{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\cdot\frac{1}{n}\sum_{j\in\mathcal{N}^{\kappa}_{i}}\widehat{Q}^{\pi_{\theta}}_{j}(s_{\mathcal{N}^{\kappa}_{j}},a_{\mathcal{N}^{\kappa}_{j}})\bigg{]},$
(15)

Compared to the true policy gradient (10), the estimator
$\widehat{g}_{i}(\theta)$ replaces the shadow Q-functions with their truncated
estimators. Furthermore, it only uses the truncated Q-functions of agents in
$\mathcal{N}^{\kappa}_{i}$. In the next proposition, we evaluate the
approximation error of $\widehat{g}_{i}(\theta)$.

######  Proposition 1.

Let Assumption 1 hold. Suppose that there exist $M_{f},M_{\psi}>0$ such that
$\|\nabla_{\lambda_{i}}f_{i}(\lambda_{i}^{\pi_{\theta}})\|_{\infty}\leq M_{f}$
and $\|\psi_{\theta_{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\|\leq M_{\psi}$,
$\forall
i\in{\mathcal{N}},(s,a)\in\mathcal{S}\times\mathcal{A},\theta\in\Theta$. Then,
for all $i\in{\mathcal{N}},\theta\in\Theta$, we have that

$\|\widehat{g}_{i}(\theta)-\nabla_{\theta_{i}}F(\theta)\|\leq\frac{c_{0}\phi_{0}^{\kappa}M_{\psi}}{1-\gamma}.$
(16)

###### Proof.

In this proof, we write $\mathbb{E}_{s\sim
d^{\pi_{\theta}},a\sim{\pi_{\theta}}(\cdot|s)}$ simply as $\mathbb{E}$. The
difference term in (16) can be expanded as

$\displaystyle\widehat{g}_{i}(\theta)-\nabla_{\theta_{i}}F(\theta)$
$\displaystyle=\dfrac{1}{n(1-\gamma)}{\mathbb{E}\left[\psi_{\theta_{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\left(\sum_{j\in\mathcal{N}^{\kappa}_{i}}\widehat{Q}^{\pi_{\theta}}_{j}(s_{\mathcal{N}^{\kappa}_{j}},a_{\mathcal{N}^{\kappa}_{j}})-\sum_{j\in{\mathcal{N}}}Q^{\pi_{\theta}}_{j}(s,a)\right)\right]}$
(17)
$\displaystyle=\dfrac{1}{n(1-\gamma)}\mathbb{E}\left[\psi_{\theta_{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\sum_{j\in{\mathcal{N}}}\left(\widehat{Q}^{\pi_{\theta}}_{j}(s_{\mathcal{N}^{\kappa}_{j}},a_{\mathcal{N}^{\kappa}_{j}})-Q^{\pi_{\theta}}_{j}(s,a)\right)\right]$
$\displaystyle\quad-\dfrac{1}{n(1-\gamma)}\mathbb{E}\left[\psi_{\theta_{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\sum_{j\in\mathcal{N}^{\kappa}_{-i}}\widehat{Q}^{\pi_{\theta}}_{j}(s_{\mathcal{N}^{\kappa}_{j}},a_{\mathcal{N}^{\kappa}_{j}})\right].$

Now, we show that the second term above is actually 0. Indeed, for given
$s\in\mathcal{S}$, one can write:

$\displaystyle\quad\mathbb{E}_{a\sim{\pi_{\theta}}(\cdot|s)}\left[\psi_{\theta_{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\sum_{j\in\mathcal{N}^{\kappa}_{-i}}\widehat{Q}^{\pi_{\theta}}_{j}(s_{\mathcal{N}^{\kappa}_{j}},a_{\mathcal{N}^{\kappa}_{j}})\right]$
(18)
$\displaystyle=\sum_{a}\prod_{k\in{\mathcal{N}}}\pi_{\theta_{k}}^{k}(a_{k}|s_{\mathcal{N}^{\kappa}_{k}})\cdot\frac{\nabla_{\theta_{i}}{\pi_{\theta_{i}}^{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})}{{\pi_{\theta_{i}}^{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})}\cdot\sum_{j\in\mathcal{N}^{\kappa}_{-i}}\widehat{Q}^{\pi_{\theta}}_{j}(s_{\mathcal{N}^{\kappa}_{j}},a_{\mathcal{N}^{\kappa}_{j}})$
$\displaystyle=\sum_{a}\prod_{k\neq
i}\pi_{\theta_{k}}^{k}(a_{k}|s_{\mathcal{N}^{\kappa}_{k}})\cdot\nabla_{\theta_{i}}{\pi_{\theta_{i}}^{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\cdot\sum_{j\in\mathcal{N}^{\kappa}_{-i}}\widehat{Q}^{\pi_{\theta}}_{j}(s_{\mathcal{N}^{\kappa}_{j}},a_{\mathcal{N}^{\kappa}_{j}})$
$\displaystyle=\sum_{a_{-i}}\bigg{[}\left(\sum_{a_{i}}\nabla_{\theta_{i}}{\pi_{\theta_{i}}^{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\right)\cdot\prod_{k\neq
i}\pi_{\theta_{k}}^{k}(a_{k}|s_{\mathcal{N}^{\kappa}_{k}})\cdot\sum_{j\in\mathcal{N}^{\kappa}_{-i}}\widehat{Q}^{\pi_{\theta}}_{j}(s_{\mathcal{N}^{\kappa}_{j}},a_{\mathcal{N}^{\kappa}_{j}})\bigg{]}$
$\displaystyle=0,$

where we expand the expectation and the score function in the first equality.
The third equality holds since $j\in\mathcal{N}^{\kappa}_{-i}$ implies
$i\notin\mathcal{N}^{\kappa}_{j}$, and thus the summation
$\sum_{j\in\mathcal{N}^{\kappa}_{-i}}\widehat{Q}^{\pi_{\theta}}_{j}(s_{\mathcal{N}^{\kappa}_{j}},a_{\mathcal{N}^{\kappa}_{j}})$
is irrelevant to $a_{i}$. In the last equality, since
$\sum_{a_{i}}\nabla_{\theta_{i}}{\pi_{\theta_{i}}^{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})=\nabla_{\theta_{i}}\left[\sum_{a_{i}}{\pi_{\theta_{i}}^{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\right]=\nabla_{\theta_{i}}1=0$,
we conclude that the whole term is equal to zero. Therefore, it holds that

$\displaystyle\|\widehat{g}_{i}(\theta)-\nabla_{\theta_{i}}F(\theta)\|$
$\displaystyle=\left\lVert\dfrac{1}{n(1-\gamma)}\mathbb{E}\left[\psi_{\theta_{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\sum_{j\in{\mathcal{N}}}\left(\widehat{Q}^{\pi_{\theta}}_{j}(s_{\mathcal{N}^{\kappa}_{j}},a_{\mathcal{N}^{\kappa}_{j}})-Q^{\pi_{\theta}}_{j}(s,a)\right)\right]\right\rVert$
(19) $\displaystyle\leq\dfrac{1}{n(1-\gamma)}\cdot M_{\psi}\cdot n\cdot
c_{0}\phi_{0}^{\kappa}$

where we use Lemma 2 to bound the difference between the truncated shadow
Q-functions and true shadow Q-functions. This completes the proof. ∎

Proposition 1 shows that, the accuracy of the truncated gradient estimator has
the order $\mathcal{O}(\phi_{0}^{\kappa})$, which decreases along with the
communication radius $\kappa$. Thus, it indicates a feasible direction to
reduce the communication of agents to their $\kappa$-neighborhoods.

###  3.4 Algorithm Design

In this section, we present our method, Distributed Policy Gradient Algorithm
with Shadow Reward, for solving problem (5). The algorithm, summarized in
Algorithm 1, consists of the following elements:

Algorithm 1 Distributed Policy Gradient Algorithm With Shadow Reward and
Localized Policy

1: Input: Initial policy $\theta^{0}$; initial distribution $\xi$;
communication radius $\kappa$; step-sizes $\\{\eta_{\theta}^{t}\\}$; batch
size $B$; episode length $H$.

2: for iteration $t=0,1,2,\dots$ do

3: Sample $B$ trajectories
$\tau=\left\\{(s^{0},a^{0}),\cdots,(s^{H-1},a^{H-1})\right\\}$ with length
$H$, under policy $\pi_{\theta^{t}}$, initial distribution $\xi$. Collect them
as batch $\mathcal{B}_{t}$.

4: Each agent $i$ estimates its local occupancy measure
$\lambda^{\pi_{\theta^{t}}}_{i}$ through
$\widetilde{\lambda}^{t}_{i}=\frac{1}{B}\sum_{\tau\in\mathcal{B}_{t}}\sum_{k=0}^{H-1}\gamma^{k}\cdot\mathbf{e}_{i}\left(s_{i}^{k},a_{i}^{k}\right)\in\mathbb{R}^{|\mathcal{S}_{i}|\times|\mathcal{A}_{i}|},$
(20) and computes the empirical shadow reward
$\widetilde{r}_{i}^{t}=\nabla_{\lambda_{i}}f_{i}(\widetilde{\lambda}^{t}_{i})$.

5: Each agent $i$ communicates with its neighborhood
$\mathcal{N}^{\kappa}_{i}$ and estimate the truncated Q-function under
$\widetilde{r}_{i}^{t}$, denoted as $\widetilde{Q}^{t}_{i}$.

6: Each agent $i$ shares $\widetilde{Q}^{t}_{i}$ with its neighborhood
$\mathcal{N}^{\kappa}_{i}$ and estimates the truncated policy gradient through
$\displaystyle\widetilde{g}_{i}^{t}=\frac{1}{B}\sum_{\tau\in\mathcal{B}_{t}}\bigg{[}\sum_{k=0}^{H-1}\gamma^{k}{\psi}_{\theta_{i}^{t}}(a_{i}^{k}|s_{\mathcal{N}^{\kappa}_{i}}^{k})\cdot\frac{1}{n}\sum_{j\in\mathcal{N}^{\kappa}_{i}}\widetilde{Q}^{t}_{i}(s_{\mathcal{N}^{\kappa}_{j}}^{k},a_{\mathcal{N}^{\kappa}_{j}}^{k})\bigg{]}.$
(21)

7: Each agent $i$ updates the policy through
$\theta_{i}^{t+1}=\theta_{i}^{t}+\eta_{\theta}^{t}\cdot\widetilde{g}_{i}^{t}.$
(22)

8: end for

#### Shadow Reward Estimation (lines 3-4)

In the beginning of each iteration $t$, the current policy is simulated to
generate a batch of $B$ trajectories with length $H$. Since the local policy
${\pi_{\theta_{i}}^{i}}(\cdot|s_{\mathcal{N}^{\kappa}_{i}})$ of each agent $i$
only depends on the states of $\mathcal{N}^{\kappa}_{i}$, the process of
trajectory sampling is comply with the communication requirement. Then, using
local state-action information, each agent $i$ forms an estimation
$\widetilde{\lambda}^{t}_{i}$ for its local occupancy measure through (20),
where we define
$\mathbf{e}_{i}\left(s_{i},a_{i}\right)\in\mathbb{R}^{|\mathcal{S}_{i}|\times|\mathcal{A}_{i}|}$
as a vector with its $(s_{i},a_{i})$-th entry equal to one and other entries
equal to zero. Finally, the empirical shadow reward is computed via
$\widetilde{r}_{i}^{t}=\nabla_{\lambda_{i}}f_{i}(\widetilde{\lambda}^{t}_{i})$.

#### Truncated Shadow Q-function Estimation (line 5)

In the next stage, each agent $i$ takes $\widetilde{r}_{i}^{t}$ as their
reward function (pretending that to be the true shadow reward) and
communicates with its neighborhood $\mathcal{N}^{\kappa}_{i}$ to estimate the
truncated shadow Q-function $\widehat{Q}^{t}_{i}$. We do not specify the
estimation process and allow the use of any existing approach for Q-function
evaluation as long as it satisfies the error bound required for the
theoretical analysis in Section 4 (see Assumption 4). For example, one can use
the Temporal difference (TD) learning [22], which is a model-free method for
estimating the Q-function. In TD-learning, all agents iteratively update their
estimations along a common trajectory
$\tau=\left\\{(s^{0},a^{0}),\cdots,(s^{H-1},a^{H-1})\right\\}$ under policy
${\pi_{\theta^{t}}}$. For every new global state-action pair $(s^{k},a^{k})$,
the TD-learning updates the current estimation $\widetilde{Q}^{t}_{i}$ through

$\displaystyle\widetilde{Q}^{t}_{i}(s^{k-1}_{\mathcal{N}^{\kappa}_{i}},a^{k-1}_{\mathcal{N}^{\kappa}_{i}})$
$\displaystyle\leftarrow(1-\eta_{Q}^{k-1})\widetilde{Q}^{t}_{i}(s^{k-1}_{\mathcal{N}^{\kappa}_{i}},a^{k-1}_{\mathcal{N}^{\kappa}_{i}})+\eta_{Q}^{k-1}\big{[}\widetilde{r}_{i}^{t}(s_{i}^{k-1},a_{i}^{k-1})+\gamma\widetilde{Q}^{t}_{i}(s^{k}_{\mathcal{N}^{\kappa}_{i}},a^{k}_{\mathcal{N}^{\kappa}_{i}})\big{]},$
(23)
$\displaystyle\widetilde{Q}^{t}_{i}(s_{\mathcal{N}^{\kappa}_{i}},a_{\mathcal{N}^{\kappa}_{i}})$
$\displaystyle\leftarrow\widetilde{Q}^{t}_{i}(s_{\mathcal{N}^{\kappa}_{i}},a_{\mathcal{N}^{\kappa}_{i}}),\text{
for
}(s_{\mathcal{N}^{\kappa}_{i}},a_{\mathcal{N}^{\kappa}_{i}})\neq(s^{k-1}_{\mathcal{N}^{\kappa}_{i}},a^{k-1}_{\mathcal{N}^{\kappa}_{i}}),$

where $\\{\eta_{Q}^{k}\\}$ are the learning step-sizes. As shown in [14,
Theorem 5], the above procedure exhibits an error rate of
$\mathcal{O}(1/\sqrt{H})$ under a local exploration assumption. Together with
the error induced by the empirical shadow reward, this implies
$\|\widetilde{Q}^{t}_{i}-\widehat{Q}^{t}_{i}\|_{\infty}=\mathcal{O}(1/\sqrt{H}+\|\widetilde{r}_{i}^{t}-{r}_{i}^{t}\|_{\infty})$.
Besides the TD-learning, one can also deploy other model-free or model-based
estimators depending on the sampling mechanisms, e.g., [23, 24].

#### Truncated Policy Gradient Estimation and Policy Update (lines 6-7)

At the final stage, every agent $i$ exchanges their estimation
$\widetilde{Q}^{t}_{i}$ with the neighborhood $\mathcal{N}^{\kappa}_{i}$ and
evaluates the truncated policy gradient (15) through (21). The new policy is
obtained by performing a policy gradient ascent with the estimated gradient
$\widetilde{g}_{i}^{t}$.

######  Remark 1.

In contrast to a major line of MARL research, e.g., [12, 25], full
observability is not required for executing Algorithm 1, i.e., the agents do
not need have access to the global information, including the global state and
action. Instead, for the specified communication radius $\kappa$, each agent
$i$ needs to communicate with its neighborhood $\mathcal{N}^{\kappa}_{i}$ to
sample trajectories, estimate its local shadow Q-function, and estimate its
truncated policy gradient.

##  4 CONVERGENCE ANALYSIS

In this section, we analyze the convergence behavior of Algorithm 1. We first
summarize the additional technical assumptions required, among which some have
appeared in the previous section.

######  Assumption 2.

Let $\Lambda$ be the set of all possible occupancy measures $\lambda$. The
utility function $f(\cdot)$ satisfies: (I) $\exists M_{f}>0$ such that
$\|\nabla_{\lambda_{i}}f_{i}(\lambda_{i})\|_{\infty}\leq M_{f}$, $\forall
i\in{\mathcal{N}}$ and $\lambda\in\Lambda$. (II) $\exists L_{\lambda}$ such
that
$\|\nabla_{\lambda_{i}}f_{i}(\lambda_{i})-\nabla_{\lambda_{i}}f_{i}(\lambda_{i}^{\prime})\|_{\infty}\leq
L_{\lambda}\|\lambda_{i}-\lambda_{i}^{\prime}\|$, $\forall i\in{\mathcal{N}}$
and $\lambda,\lambda^{\prime}\in\Lambda$.

######  Assumption 3.

The parameterized policy $\pi_{\theta}$ and the associated occupancy measure
$\lambda^{\pi_{\theta}}$ satisfy: (I) $\exists M_{\psi}>0$ such that the score
function $\|\psi_{\theta_{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})\|\leq
M_{\psi}$, $\forall i\in{\mathcal{N}}$,
$(s,a)\in\mathcal{S}\times\mathcal{A}$, $\theta\in\Theta$. (II) $\exists
L_{\theta}>0$ such that the utility function
$F(\theta)=f(\lambda^{\pi_{\theta}})$ is $L_{\theta}$-smooth with respect to
$\theta$.

Besides the bounded gradient and the bounded score function assumptions, we
additionally assume that the utility function
$f_{i}(\lambda_{i}^{\pi_{\theta}})$ is smooth with respect to both the
occupancy measure $\lambda_{i}$ and the policy $\theta$. These assumptions are
standard in the literature of reinforcement learning with general utilities
[3, 12, 15, 26].

As discussed in Section 3, we do not specify the estimation process for the
truncated shadow Q-functions. Instead, we assume that an oracle is used, which
produces a bounded-error approximation to the true function. Let
$\widehat{Q}^{\pi_{\theta}}_{r_{i}}(\cdot,\cdot)\in\mathbb{R}^{|\mathcal{S}_{\mathcal{N}^{\kappa}_{i}}|\times|\mathcal{A}_{\mathcal{N}^{\kappa}_{i}}|}$
be the $\kappa$-truncated local Q-function under reward
$r_{i}\in\mathbb{R}^{|\mathcal{S}_{i}|\times|\mathcal{A}_{i}|}$ for agent $i$.

######  Assumption 4.

For every $i\in{\mathcal{N}}$ and $\theta\in\Theta$, an approximation
$\widetilde{Q}^{\pi_{\theta}}_{r_{i}}(\cdot,\cdot)$ can be computed for
$\widehat{Q}^{\pi_{\theta}}_{r_{i}}(\cdot,\cdot)$ such that

$\sup_{s_{\mathcal{N}^{\kappa}_{i}},a_{\mathcal{N}^{\kappa}_{i}}}\left|\widetilde{Q}^{\pi_{\theta}}_{r_{i}}(s_{\mathcal{N}^{\kappa}_{i}},a_{\mathcal{N}^{\kappa}_{i}})-\widehat{Q}^{\pi_{\theta}}_{r_{i}}(s_{\mathcal{N}^{\kappa}_{i}},a_{\mathcal{N}^{\kappa}_{i}})\right|\leq\epsilon_{0}\|r_{i}\|_{\infty},$
(24)

where $\epsilon_{0}>0$ is the approximation error.

Under Assumption 4, we have that the estimator $\widetilde{Q}^{t}_{i}$ in line
5 of Algorithm 1 satisfies
$\|\widetilde{Q}^{t}_{i}-\widehat{Q}^{\pi_{\theta^{t}}}_{\widetilde{r}_{i}^{t}}\|_{\infty}\leq\epsilon_{0}\|\widetilde{r}_{i}^{t}\|_{\infty}$.
This can be achieved, for example, with $\mathcal{O}(1/(\epsilon_{0})^{2})$
samples by the TD-learning procedure (23).

Before analyzing the convergence of Algorithm 1, we first present a few
auxiliary results, which evaluate the estimators
$\widetilde{\lambda}^{t}_{i}$, $\widetilde{r}_{i}^{t}$,
$\widetilde{Q}^{t}_{i}$, and $\widetilde{g}_{i}^{t}$.

######  Proposition 2.

Let $\delta_{0}\in(0,1/(2n))$ be the failure probability. Under Assumptions
2-4, it holds for every period $t\geq 0$ that

  1. (I)

for each agent $i\in{\mathcal{N}}$, with probability $1-\delta_{0}$

$\|\widetilde{\lambda}^{t}_{i}-\lambda^{\pi_{\theta^{t}}}_{i}\|\leq\epsilon_{1}(\delta_{0}),\
\|\widetilde{r}_{i}^{t}-r_{i}^{t}\|_{\infty}\leq
L_{\lambda}\epsilon_{1}(\delta_{0}).$ (25)

  2. (II)

with probability $1-n\delta_{0}$

$\|\widetilde{Q}^{t}_{i}-\widehat{Q}^{\pi_{\theta^{t}}}_{i}\|_{\infty}\leq\epsilon_{0}M_{f}+\frac{L_{\lambda}\epsilon_{1}(\delta_{0})}{1-\gamma},\
\forall i\in{\mathcal{N}}.$ (26)

  3. (III)

with probability $1-2n\delta_{0}$

$\|\widetilde{g}_{i}^{t}-\widehat{g}_{i}(\theta^{t})\|\leq\epsilon_{2,i}(\delta_{0}),\
\forall i\in{\mathcal{N}},$ (27)

where

$\displaystyle\epsilon_{1}(\delta_{0})=\sqrt{\frac{4+2\gamma^{2H}B-16\log\delta_{0}}{(1-\gamma)^{2}B}},\quad\epsilon_{2,i}(\delta_{0})=\frac{|\mathcal{N}^{\kappa}_{i}|}{n}\mathcal{O}\left(\epsilon_{0}+\sqrt{\frac{\log(1/\delta_{0})}{B}}+\gamma^{H}\right).$
(28)

###### Proof.

We refer the reader to [12, Appendix D.1] for the proof of part (I). For part
(II), we first recall that $\widetilde{Q}^{t}_{i}$ is a sample-based
estimation for the truncated local Q-function
$\widehat{Q}^{\pi_{\theta^{t}}}_{\widetilde{r}_{i}^{t}}$. By combining the
error bound (25) with Assumptions 2 and 4, we obtain that with probability
$1-\delta_{0}$

$\displaystyle\|\widetilde{Q}^{t}_{i}-\widehat{Q}^{\pi_{\theta^{t}}}_{i}\|_{\infty}$
$\displaystyle\leq\|\widetilde{Q}^{t}_{i}-\widehat{Q}^{\pi_{\theta^{t}}}_{\widetilde{r}_{i}^{t}}\|_{\infty}+\|\widehat{Q}^{\pi_{\theta^{t}}}_{\widetilde{r}_{i}^{t}}-\widehat{Q}^{\pi_{\theta^{t}}}_{i}\|_{\infty}$
(29)
$\displaystyle\leq\epsilon_{0}\|\widetilde{r}_{i}^{t}\|_{\infty}+\frac{\|\widetilde{r}_{i}^{t}-r_{i}^{t}\|_{\infty}}{1-\gamma}$
$\displaystyle\leq\epsilon_{0}M_{f}+\frac{L_{\lambda}\epsilon_{1}(\delta_{0})}{1-\gamma}.$

By applying the union bound, we have that with probability $1-n\delta_{0}$,
the bound (29) holds for all agents $i\in{\mathcal{N}}$.

For part (III), let $\mathcal{F}_{t}$ denote the $\sigma$-algebra generated by
all the trajectories in $\mathcal{B}_{t}$ sampled at the $t$-th iteration and
let

$\widehat{g}_{i}^{t}:=\frac{1}{B}\sum_{\tau\in\mathcal{B}_{t}}\bigg{[}\sum_{k=0}^{H-1}\gamma^{k}{\psi}_{\theta_{i}^{t}}(a_{i}^{k}|s_{\mathcal{N}^{\kappa}_{i}}^{k})\frac{1}{n}\sum_{j\in\mathcal{N}^{\kappa}_{i}}\widehat{Q}^{\pi_{\theta^{t}}}_{i}(s_{\mathcal{N}^{\kappa}_{j}}^{k},a_{\mathcal{N}^{\kappa}_{j}}^{k})\bigg{]},$
(30)

which differs from $\widetilde{g}_{i}^{t}$ only in the Q-function term. Next,
we derive the bound (27) through the decomposition

$\displaystyle\widetilde{g}_{i}^{t}-\widehat{g}_{i}({\pi_{\theta^{t}}})=\left(\widetilde{g}_{i}^{t}-\widehat{g}_{i}^{t}\right)+\left(\widehat{g}_{i}^{t}-\mathbb{E}\left[\widehat{g}_{i}^{t}|\mathcal{F}_{t}\right]\right)+\left(\mathbb{E}\left[\widehat{g}_{i}^{t}|\mathcal{F}_{t}\right]-\widehat{g}_{i}(\theta^{t})\right).$
(31)

For the first difference, it holds from part (II) and Assumption 3 that with
probability $1-n\delta_{0}$.

$\displaystyle\|\widetilde{g}_{i}^{t}-\widehat{g}_{i}^{t}\|^{2}$
$\displaystyle\leq\left[\frac{1}{1-\gamma}\cdot
M_{\psi}\cdot\frac{|\mathcal{N}^{\kappa}_{i}|}{n}\right]^{2}\left(\epsilon_{0}M_{f}+\frac{L_{\lambda}\epsilon_{1}(\delta_{0})}{1-\gamma}\right)^{2}$
(32)
$\displaystyle=\frac{|\mathcal{N}^{\kappa}_{i}|^{2}M_{\psi}^{2}}{n^{2}(1-\gamma)^{2}}\left(\epsilon_{0}M_{f}+\frac{L_{\lambda}\epsilon_{1}(\delta_{0})}{1-\gamma}\right)^{2}=:C_{1,i},$

Then, we bound the second term in (31). For a trajectory $\tau$ and
$k_{1},k_{2}\geq 0$, we define that

$G^{t}_{i}(\tau_{k_{1}}^{k_{2}}):=\sum_{k=k_{1}}^{k_{2}}\gamma^{k}{\psi}_{\theta_{i}^{t}}(a_{i}^{k}|s_{\mathcal{N}^{\kappa}_{i}}^{k})\cdot\frac{1}{n}\sum_{j\in\mathcal{N}^{\kappa}_{i}}\widehat{Q}^{\pi_{\theta^{t}}}_{i}(s_{\mathcal{N}^{\kappa}_{j}}^{k},a_{\mathcal{N}^{\kappa}_{j}}^{k}).$
(33)

It is clear from definition that
$\widehat{g}_{i}^{t}=1/B\cdot\sum_{\tau\in\mathcal{B}_{t}}G^{t}_{i}(\tau_{0}^{H-1})$.
By Assumptions 2 and 3, it holds that

$\displaystyle\mathbb{E}\left[\|G^{t}_{i}(\tau_{0}^{H-1})\|^{2}|\mathcal{F}_{t}\right]\leq\frac{|\mathcal{N}^{\kappa}_{i}|^{2}M_{f}^{2}M_{\psi}^{2}}{n^{2}(1-\gamma)^{4}}$
(34)

Thus, by [27, Lemma 18], we have that with probability $1-\delta_{0}$

$\left\|\widehat{g}_{i}^{t}-\mathbb{E}\left[\widehat{g}_{i}^{t}|\mathcal{F}_{t}\right]\right\|^{2}\leq\frac{(2-8\log\delta_{0})|\mathcal{N}^{\kappa}_{i}|^{2}M_{f}^{2}M_{\psi}^{2}}{n^{2}(1-\gamma)^{4}B}=:C_{2,i}.$
(35)

Finally, to bound the third term in (31), we derive that

$\displaystyle\|\mathbb{E}\left[\widehat{g}_{i}^{t}|\mathcal{F}_{t}\right]-\widehat{g}_{i}(\theta^{t})\|^{2}$
$\displaystyle=\left\|\mathbb{E}\left[G^{t}_{i}(\tau_{0}^{H-1})|{\pi_{\theta^{t}}},\xi\right]-\widehat{g}_{i}(\theta^{t})\right\|^{2}$
(36)
$\displaystyle=\left\|\mathbb{E}\left[G^{t}_{i}(\tau_{0}^{\infty})|{\pi_{\theta^{t}}},\xi\right]-\widehat{g}_{i}(\theta^{t})-\mathbb{E}\left[G^{t}_{i}(\tau_{H}^{\infty})|{\pi_{\theta^{t}}},\xi\right]\right\|^{2}$
$\displaystyle=\left\|\mathbb{E}\left[G^{t}_{i}(\tau_{H}^{\infty})|{\pi_{\theta^{t}}},\xi\right]\right\|^{2}$
$\displaystyle\leq\frac{\gamma^{2H}|\mathcal{N}^{\kappa}_{i}|^{2}M_{\psi}^{2}M_{f}^{2}}{n^{2}(1-\gamma)^{4}}=:C_{3,i}.$

where we use the fact that $G^{t}_{i}(\tau_{0}^{\infty})$ is an unbiased
estimator for $\widehat{g}_{i}(\theta^{t})$ in the third equality. The
inequality in the last line follows from Assumptions 2 and 3.

Putting (31), (32), (35), (36) together, we have that

$\displaystyle\|\widetilde{g}_{i}^{t}-\widehat{g}_{i}(\theta^{t})\|^{2}$
$\displaystyle\leq
3\bigg{[}\|\widetilde{g}_{i}^{t}-\widehat{g}_{i}^{t}\|^{2}+\|\widehat{g}_{i}^{t}-\mathbb{E}\left[\widehat{g}_{i}^{t}|\mathcal{F}_{t}\right]\|^{2}+\|\mathbb{E}\left[\widehat{g}_{i}^{t}|\mathcal{F}_{t}\right]-\widehat{g}_{i}(\theta^{t})\|^{2}\bigg{]}$
(37) $\displaystyle\leq 3(C_{1,i}+C_{2,i}+C_{3,i})$
$\displaystyle=\frac{|\mathcal{N}^{\kappa}_{i}|^{2}}{n^{2}}\mathcal{O}\left(\epsilon_{0}^{2}+\epsilon_{1}(\delta_{0})^{2}+\frac{\log(1/\delta_{0})}{B}+\gamma^{2H}\right)$
$\displaystyle=\frac{|\mathcal{N}^{\kappa}_{i}|^{2}}{n^{2}}\mathcal{O}\left(\epsilon_{0}^{2}+\frac{\log(1/\delta_{0})}{B}+\gamma^{2H}\right),$

where we use the definition of $\epsilon_{1}(\delta_{0})$ in (28). Finally, we
note that, by the union bound, (35) holds for all agents $i\in{\mathcal{N}}$
with probability $1-n\delta_{0}$. Since (32) holds with probability
$1-n\delta_{0}$ and (36) is deterministic, we conclude that, with probability
$1-2n\delta_{0}$, the bound (37) holds for all agents. The proof is completed
by taking $\epsilon_{2,i}(\delta_{0}):=\sqrt{3(C_{1,i}+C_{2,i}+C_{3,i})}$. ∎

Proposition 2 evaluates the accuracy of the estimation for the truncated
policy gradient. Together with Proposition 1, this provides a probabilistic
upper bound for the gradient estimation error
$\|\widetilde{g}^{t}_{i}-\nabla_{\theta_{i}}F(\theta^{t})\|$, which we will
use to prove the convergence of Algorithm 1 in the following theorem.

######  Theorem 1.

Suppose that Assumptions 1-4 hold and the step-sizes satisfy
$\eta_{\theta}^{t}\leq 1/(4L_{\theta})$, $\forall t\geq 0$. For every $T>0$,
let $\delta_{0}=\delta/(2nT)$, where $\delta\in(0,1)$ is the failure
probability. Then, with probability $1-\delta$, it holds that

$\frac{\sum_{t=0}^{T-1}\eta_{\theta}^{t}\left\|\nabla_{\theta}F(\theta^{t})\right\|^{2}}{\sum_{t=0}^{T-1}\eta_{\theta}^{t}}\leq\frac{4\left(F(\theta^{T})-F(\theta^{0})\right)}{\sum_{t=0}^{T-1}\eta_{\theta}^{t}}+3\Delta(\delta_{0}),$
(38)

where

$\Delta(\delta_{0})=\mathcal{O}(n\phi_{0}^{2\kappa})+\sum_{i\in{\mathcal{N}}}\frac{|\mathcal{N}^{\kappa}_{i}|^{2}}{n^{2}}\mathcal{O}\left(\epsilon_{0}^{2}+\frac{\log(1/\delta_{0})}{B}+\gamma^{2H}\right).$
(39)

###### Proof.

By the smoothness of $F(\theta)$ (Assumption 3), when the step-size satisfies
$\eta_{\theta}^{t}\leq 1/(4L_{\theta})$, the policy update (22) implies

$\displaystyle F(\theta^{t+1})-F(\theta^{t})$
$\displaystyle\geq\sum_{i\in{\mathcal{N}}}\left[\left\langle\nabla_{\theta_{i}}F(\theta^{t}),\eta_{\theta}^{t}\widetilde{g}_{i}^{t}\right\rangle-\frac{L_{\theta}}{2}\|\eta_{\theta}^{t}\widetilde{g}_{i}^{t}\|^{2}\right]$
(40)
$\displaystyle=\sum_{i\in{\mathcal{N}}}\bigg{[}\eta_{\theta}^{t}\left\langle\nabla_{\theta_{i}}F(\theta^{t}),\nabla_{\theta_{i}}F(\theta^{t})-(\nabla_{\theta_{i}}F(\theta^{t})-\widetilde{g}_{i}^{t})\right\rangle$
$\displaystyle\quad-\frac{L_{\theta}}{2}(\eta_{\theta}^{t})^{2}\left\|\nabla_{\theta_{i}}F(\theta^{t})-(\nabla_{\theta_{i}}F(\theta^{t})-\widetilde{g}_{i}^{t})\right\|^{2}\bigg{]}$
$\displaystyle\geq\sum_{i\in{\mathcal{N}}}\bigg{[}\eta_{\theta}^{t}\left\|\nabla_{\theta_{i}}F(\theta^{t})\right\|^{2}-\frac{\eta_{\theta}^{t}}{2}\left(\left\|\nabla_{\theta_{i}}F(\theta^{t})\right\|^{2}+\left\|\nabla_{\theta_{i}}F(\theta^{t})-\widetilde{g}_{i}^{t}\right\|^{2}\right)$
$\displaystyle\quad-
L_{\theta}(\eta_{\theta}^{t})^{2}\left(\left\|\nabla_{\theta_{i}}F(\theta^{t})\right\|^{2}+\left\|\nabla_{\theta_{i}}F(\theta^{t})-\widetilde{g}_{i}^{t}\right\|^{2}\right)\bigg{]}$

where we apply the basic inequality $2\left\langle
a,b\right\rangle\leq\|a+b\|^{2}/2\leq\|a\|^{2}+\|b\|^{2}$ in the last
inequality. By rearranging the terms in (40) and using the condition
$\eta_{\theta}^{t}\leq 1/(4L_{\theta})$, we have that

$F(\theta^{t+1})-F(\theta^{t})\geq\frac{\eta_{\theta}^{t}}{4}\left\|\nabla_{\theta}F(\theta^{t})\right\|^{2}-\frac{3\eta_{\theta}^{t}}{4}\sum_{i\in{\mathcal{N}}}\left\|\nabla_{\theta_{i}}F(\theta^{t})-\widetilde{g}_{i}^{t}\right\|^{2},$
(41)

which further implies that

$\eta_{\theta}^{t}\left\|\nabla_{\theta}F(\theta^{t})\right\|^{2}\leq
4\left(F(\theta^{t+1})-F(\theta^{t})\right)+3\eta_{\theta}^{t}\sum_{i\in{\mathcal{N}}}\left\|\nabla_{\theta_{i}}F(\theta^{t})-\widetilde{g}_{i}^{t}\right\|^{2}.$
(42)

By Propositions 1 and 2, with probability $1-\delta_{0}$, it holds that

$\displaystyle\sum_{i\in{\mathcal{N}}}\left\|\nabla_{\theta_{i}}F(\theta^{t})-\widetilde{g}_{i}^{t}\right\|^{2}$
$\displaystyle\leq\sum_{i\in{\mathcal{N}}}2\left(\|\nabla_{\theta_{i}}F(\theta^{t})-\widehat{g}_{i}(\theta^{t})\|^{2}+\|\widehat{g}_{i}(\theta^{t})-\widetilde{g}_{i}^{t}\|^{2}\right)$
(43) $\displaystyle=2\sum_{i\in
N}\left[\left(\frac{c_{0}\phi_{0}^{\kappa}M_{\psi}}{1-\gamma}\right)^{2}+\left(\epsilon_{2,i}(\delta_{0})\right)^{2}\right]$
$\displaystyle=:\Delta(\delta_{0}).$

The relation (39) follows directly from the definition of $\epsilon_{2,i}$ in
Proposition 2, Applying the union bound again, we have that (43) holds for all
$t=0,1,\dots,T-1$ with probability $1-\delta$, where $\delta=(2nT)\delta_{0}$.
Thus, by substituting (43) into (42) and summing over $t=0,1,\dots,T-1$, we
conclude that with probability $1-\delta$

$\displaystyle\frac{\sum_{t=0}^{T-1}\eta_{\theta}^{t}\left\|\nabla_{\theta}F(\theta^{t})\right\|^{2}}{\sum_{t=0}^{T-1}\eta_{\theta}^{t}}$
$\displaystyle\leq\frac{\sum_{t=0}^{T-1}4\left(F(\theta^{t+1})-F(\theta^{t})\right)}{\sum_{t=0}^{T-1}\eta_{\theta}^{t}}+\frac{\sum_{t=0}^{T-1}3\eta_{\theta}^{t}\Delta(\delta_{0})}{\sum_{t=0}^{T-1}\eta_{\theta}^{t}}$
(44)
$\displaystyle=\frac{4\left(F(\theta^{T})-F(\theta^{0})\right)}{\sum_{t=0}^{T-1}\eta_{\theta}^{t}}+3\Delta(\delta_{0}),$

which completes the proof. ∎

Under constant step-sizes $\eta_{\theta}^{t}\equiv\eta_{\theta}$, the bound
(38) becomes

$\frac{1}{T}\sum_{t=0}^{T-1}\left\|\nabla_{\theta}F(\theta^{t})\right\|^{2}\leq\frac{4\left(F(\theta^{T})-F(\theta^{0})\right)}{\eta_{\theta}T}+3\Delta(\delta_{0}),$
(45)

which implies an $\mathcal{O}(1/T)$ iteration complexity with the
approximation error $3\Delta(\delta_{0})$. As shown in (39), the constant
$\Delta(\delta_{0})$ will be small when the rate of spatial correlation decay
is fast, the computational error $\epsilon_{0}$ for Q-functions is small, and
enough samples are used to estimate the local occupancy measure. Notably, when
the size of $\kappa$-neighborhood $|\mathcal{N}^{\kappa}_{i}|$ is relatively
small for all agents compared to the total number of agents $n$, the term
$\sum_{i\in{\mathcal{N}}}{|\mathcal{N}^{\kappa}_{i}|^{2}}/{n^{2}}$ approaches
$\mathcal{O}(1/n)$ and $\Delta(\delta_{0})=\mathcal{O}(n\phi_{0}^{2\kappa})$
approximately holds.

Suppose that an $\mathcal{O}(1/(\epsilon_{0})^{2})$ oracle is used for the
truncated Q-function estimation (line 5 in Algorithm 1), i.e., the
approximation (24) is achieved with $\mathcal{O}(1/(\epsilon_{0})^{2})$
samples. We analyze the sample complexity of Algorithm 1 to compute an
$\epsilon$-stationary point.

######  Theorem 2.

Suppose that Assumptions 1-4 hold and an $\mathcal{O}(1/(\epsilon_{0})^{2})$
oracle is used for the truncated Q-function estimation. For every $\epsilon>0$
and $\delta\in(0,1)$, let $T=\mathcal{O}(\epsilon^{-1})$,
$\eta_{\theta}^{t}\equiv 1/(4L_{\theta})$, $\epsilon_{0}=\sqrt{\epsilon}$,
$\delta_{0}=\delta/(2nT)$, batch size
$B=\mathcal{O}\left(\log(1/\delta_{0})\epsilon^{-1}\right)$, episode length
$H=\mathcal{O}\left(\log(1/\epsilon)\right)$. Then, with probability
$1-\delta$, it holds that

$\frac{1}{T}\sum_{t=0}^{T-1}\left\|\nabla_{\theta}F(\theta^{t})\right\|^{2}=\mathcal{O}\left(\epsilon+n\phi_{0}^{2\kappa}\right).$
(46)

The total number of samples required is
$\widetilde{\mathcal{O}}(\epsilon^{-2})$.

###### Proof.

The $\epsilon$-stationarity (46) follows directly from (38) and (39) in
Theorem 1. In every iteration, $B\times
H=\widetilde{\mathcal{O}}(\epsilon^{-1})$ samples are used to estimate the
occupancy measure and compute the empirical shadow reward, (perhaps another)
$\mathcal{O}(1/\epsilon_{0}^{2})=\mathcal{O}(\epsilon^{-1})$ samples are used
to estimate the truncated Q-function. Since there are
$T=\mathcal{O}(\epsilon^{-1})$ iterations, the total number of samples used is
$\widetilde{\mathcal{O}}(\epsilon^{-2})$. ∎

As discussed in Section 3, the TD-learning procedure (23) is an
$\mathcal{O}(1/(\epsilon_{0})^{2})$ oracle for the truncated Q-function
estimation with high probability. Below, we provide two further remarks.

######  Remark 2 (Global Optimality).

Suppose that the utility function $f(\lambda)$ is concave in $\lambda$, which
generalizes the linear objective for standard RL. If the policy
parameterization satisfies [15, Assumption 5.11], then problem (5) does not
have spurious local solutions. Thus, the error bound (38) implies convergence
to global optimality.

######  Remark 3.

The communication radius $\kappa$ plays an important role in both Theorems 1
and 2. As $\kappa$ increases, the term $\phi_{0}^{2\kappa}$ decreases, yet the
size of the $\kappa$-neighborhood $|\mathcal{N}^{\kappa}_{i}|$ increases,
making the constant
$\sum_{i\in{\mathcal{N}}}{|\mathcal{N}^{\kappa}_{i}|^{2}}/{n^{2}}$ increase.
Also, the increase of $|\mathcal{N}^{\kappa}_{i}|$ will amplify the
communication cost and make the estimation of truncated Q-functions less
efficient. Thus, finding a good balance is important in determining $\kappa$.

######  Remark 4.

In this work, we focus on the policy search in a class of localized policies,
where each local policy
${\pi_{\theta_{i}}^{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})$ only depends on
the states of agents in $\mathcal{N}^{\kappa}_{i}$. It is possible to relax
this “hard” requirement to a “soft” requirement. Below, we briefly describe
the idea of this extension.

Consider the factorization
$\pi_{\theta}(a|s)=\prod_{i\in\mathcal{N}}\pi_{\theta_{i}}^{i}\left(a_{i}|s\right)$,
where each local policy ${\pi_{\theta_{i}}^{i}}$ depends on the global state
$s$. We assume that a form of spatial correlation decay property holds for the
local policy ${\pi_{\theta_{i}}^{i}}(a_{i}|s)$ and the associated local score
function
$\psi_{\theta_{i}}(a_{i}|s)=\nabla_{\theta_{i}}\log{\pi_{\theta_{i}}^{i}}(a_{i}|s)$,
such that

$\displaystyle\sup_{s,s^{\prime}_{\mathcal{N}^{\kappa}_{-i}}}$
$\displaystyle\operatorname{TV}\left({\pi_{\theta_{i}}^{i}}(\cdot|s_{\mathcal{N}^{\kappa}_{i}},s_{\mathcal{N}^{\kappa}_{-i}}),{\pi_{\theta_{i}}^{i}}(\cdot|s_{\mathcal{N}^{\kappa}_{i}},s^{\prime}_{\mathcal{N}^{\kappa}_{-i}})\right)\leq
c_{1}\phi_{1}^{\kappa},$ (47)
$\displaystyle\sup_{s,s^{\prime}_{\mathcal{N}^{\kappa}_{-i}}}$
$\displaystyle\operatorname{TV}\left(\psi_{\theta_{i}}(\cdot|s_{\mathcal{N}^{\kappa}_{i}},s_{\mathcal{N}^{\kappa}_{-i}}),\psi_{\theta_{i}}(\cdot|s_{\mathcal{N}^{\kappa}_{i}},s^{\prime}_{\mathcal{N}^{\kappa}_{-i}})\right)\leq
c_{1}\phi_{1}^{\kappa},$

where $c_{1}\geq 0$ and $\phi_{1}\in(0,1)$ are two constants. In light of this
decay property, we define the induced truncated policy of
${\pi_{\theta_{i}}^{i}}$ as (similar to the definition of truncated
Q-function)

${\widehat{\pi}_{\theta_{i}}^{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}}):={\pi_{\theta_{i}}^{i}}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}},\bar{s}_{\mathcal{N}^{\kappa}_{-i}}),\
\forall
s_{\mathcal{N}^{\kappa}_{i}}\in\mathcal{S}_{\mathcal{N}^{\kappa}_{i}},$ (48)

where $\bar{s}_{\mathcal{N}^{\kappa}_{-i}}$ is any fixed state for the agents
in $\mathcal{N}^{\kappa}_{-i}$. Similarly, we define
$\widehat{\psi}(a_{i}|s_{\mathcal{N}^{\kappa}_{i}})$ as the truncated score
function.

By using the truncated policy and score function, we can still implement
Algorithm 1 without violating the observability and communication
requirements. Meanwhile, it is important to quantify the information loss in
using the truncated policy as an approximation for the true policy, which
depends on the global state. Specifically, new approximation errors would
arise in the trajectory sampling, and then affect the estimation of shadow
rewards, shadow Q-functions, and policy gradients. Under condition (47), the
errors in the occupancy measure can be upper-bounded as follows.

######  Lemma 3.

Suppose that condition (47) holds. Let
${\widehat{\pi}_{\theta}}:=\prod_{i\in{\mathcal{N}}}{\widehat{\pi}_{\theta_{i}}^{i}}$
be the induced truncated policy of ${\pi_{\theta}}$. It holds that

$\left\|\lambda_{i}^{\hat{\pi}_{\theta}}-\lambda_{i}^{\pi_{\theta}}\right\|_{1}\leq\frac{nc_{1}\phi_{1}^{k}}{(1-\gamma)^{2}},\forall
i\in\mathcal{N}.$ (49)

When Assumption 2 holds, we can further show that the errors in the empirical
shadow rewards and truncated Q-functions have the same order
$\mathcal{O}(\phi_{1}^{\kappa})$ as the occupancy measure. Together, the same
convergence rate and sample complexity as in Theorems 1 and 2 can be proved
with an approximation error that has the order
$\mathcal{O}(\phi_{0}^{2\kappa}+\phi_{1}^{2\kappa})$, which accounts for the
inaccuracies from both the use of truncated policy gradients and the truncated
policies. We refer the reader to [28] for the proof of Lemma 3.

##  5 CONCLUSIONS

In this paper, we study the scalable MARL with general utilities, defined as
nonlinear functions of the team’s long-term state-action occupancy measure. We
propose a scalable distributed policy gradient algorithm with shadow reward
and localized policy, which has three steps: (1) shadow reward estimation, (2)
truncated shadow Q-function estimation, and (3) truncated policy gradient
estimation and policy update. By exploiting the spatial correlation decay
property of the network structure, we rigorously establish the convergence and
sample complexity of the proposed algorithm. Future work includes
generalization to the safety-critical setting and considering information
asymmetry among the agents.

## ACKNOWLEDGMENT

This work was supported by grants from ARO, AFOSR, ONR and NSF.

## References

  * [1] Pieter Abbeel and Andrew Y Ng.  Apprenticeship learning via inverse reinforcement learning.  In Proceedings of the twenty-first international conference on Machine learning, page 1, 2004.
  * [2] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine.  Diversity is all you need: Learning skills without a reward function.  arXiv preprint arXiv:1802.06070, 2018.
  * [3] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest.  Provably efficient maximum entropy exploration.  In International Conference on Machine Learning, pages 2681–2691. PMLR, 2019.
  * [4] Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdinov.  Efficient exploration via state marginal matching.  arXiv preprint arXiv:1906.05274, 2019.
  * [5] Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang.  Variational policy gradient method for reinforcement learning with general utilities.  Advances in Neural Information Processing Systems, 33:4572–4583, 2020.
  * [6] Tom Zahavy, Brendan O’Donoghue, Guillaume Desjardins, and Satinder Singh.  Reward is enough for convex mdps.  Advances in Neural Information Processing Systems, 34, 2021.
  * [7] Wenjun Mei, Shadi Mohagheghi, Sandro Zampieri, and Francesco Bullo.  On the dynamics of deterministic epidemic propagation over networks.  Annual Reviews in Control, 44:116–128, 2017.
  * [8] Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, DJ Strouse, Joel Z Leibo, and Nando De Freitas.  Social influence as intrinsic motivation for multi-agent deep reinforcement learning.  In International conference on machine learning, pages 3040–3049. PMLR, 2019.
  * [9] Jae Won Lee, Byoung-Tak Zhang, et al.  Stock trading system using reinforcement learning with cooperative agents.  In Proceedings of the Nineteenth International Conference on Machine Learning, pages 451–458, 2002.
  * [10] Rick Zhang and Marco Pavone.  Control of robotic mobility-on-demand systems: a queueing-theoretical perspective.  The International Journal of Robotics Research, 35(1-3):186–203, 2016.
  * [11] Alessandro Zocca.  Temporal starvation in multi-channel csma networks: an analytical framework.  Queueing Systems, 91(3):241–263, 2019.
  * [12] Junyu Zhang, Amrit Singh Bedi, Mengdi Wang, and Alec Koppel.  Multi-agent reinforcement learning with general utilities via decentralized shadow reward actor-critic.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9031–9039, 2022.
  * [13] Vincent D Blondel and John N Tsitsiklis.  A survey of computational complexity results in systems and control.  Automatica, 36(9):1249–1274, 2000.
  * [14] Guannan Qu, Adam Wierman, and Na Li.  Scalable reinforcement learning for multiagent networked systems.  Operations Research, 2022.
  * [15] Junyu Zhang, Chengzhuo Ni, Csaba Szepesvari, Mengdi Wang, et al.  On the convergence and sample efficiency of variance-reduced policy gradient method.  Advances in Neural Information Processing Systems, 34:2228–2240, 2021.
  * [16] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  Advances in neural information processing systems, 12, 1999.
  * [17] Carlo Alfano and Patrick Rebeschini.  Dimension-free rates for natural policy gradient in multi-agent reinforcement learning.  arXiv preprint arXiv:2109.11692, 2021.
  * [18] Hans-Otto Georgii.  Gibbs measures and phase transitions.  In Gibbs Measures and Phase Transitions. de Gruyter, 2011.
  * [19] David Gamarnik.  Correlation decay method for decision, optimization, and inference in large-scale networks.  In Theory Driven by Influential Applications, pages 108–121. INFORMS, 2013.
  * [20] David Tse and Pramod Viswanath.  Fundamentals of wireless communication.  Cambridge university press, 2005.
  * [21] Lawrence G Roberts.  Aloha packet system with and without slots and capture.  ACM SIGCOMM Computer Communication Review, 5(2):28–42, 1975.
  * [22] Richard S Sutton.  Learning to predict by the methods of temporal differences.  Machine learning, 3(1):9–44, 1988.
  * [23] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen.  Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction.  Advances in neural information processing systems, 33:7031–7043, 2020.
  * [24] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen.  Minimax pac bounds on the sample complexity of reinforcement learning with a generative model.  Machine learning, 91(3):325–349, 2013.
  * [25] Siliang Zeng, Tianyi Chen, Alfredo Garcia, and Mingyi Hong.  Learning to coordinate in multi-agent systems: A coordinated actor-critic algorithm and finite-time guarantees.  In Learning for Dynamics and Control Conference, pages 278–290. PMLR, 2022.
  * [26] Donghao Ying, Mengzi Guo, Yuhao Ding, Javad Lavaei, and Zuojun Shen.  Policy-based primal-dual methods for convex constrained markov decision processes.  arXiv preprint arXiv:2205.10715, 2022.
  * [27] Jonas Moritz Kohler and Aurelien Lucchi.  Sub-sampled cubic regularization for non-convex optimization.  In International Conference on Machine Learning, pages 1895–1904. PMLR, 2017.
  * [28] Donghao Ying, Yunkai Zhang, Yuhao Ding, Alec Koppel, and Javad Lavaei.  Scalable primal-dual actor-critic method for safe multi-agent reinforcement learning with general utilities.  Preprint, 2023.