# Dimension-Free Rates for Natural Policy Gradient in Multi-Agent
Reinforcement Learning

Carlo Alfano  Department of Statistics, University of Oxford  Patrick
Rebeschini  Department of Statistics, University of Oxford

###### Abstract

Cooperative multi-agent reinforcement learning is a decentralized paradigm in
sequential decision making where agents distributed over a network iteratively
collaborate with neighbors to maximize global (network-wide) notions of
rewards. Exact computations typically involve a complexity that scales
exponentially with the number of agents. To address this curse of
dimensionality, we design a scalable algorithm based on the Natural Policy
Gradient framework that uses local information and only requires agents to
communicate with neighbors within a certain range. Under standard assumptions
on the spatial decay of correlations for the transition dynamics of the
underlying Markov process and the localized learning policy, we show that our
algorithm converges to the globally optimal policy with a dimension-free
statistical and computational complexity, incurring a localization error that
does not depend on the number of agents and converges to zero exponentially
fast as a function of the range of communication.

##  1 Introduction

Sequential decision-making is a prominent setting in modern statistical
theories and applications, where agents sequentially interact with an
environment—observing its state, taking actions, and receiving rewards—to
maximize notions of reward. Reinforcement learning is the setting where agents
do not have complete knowledge of the environment dynamics, and it has
received increased attention due to its recent successes on a variety of
domains, e.g. games (Silver et al., 2016, 2017) and autonomous driving
(Shalev-Shwartz et al., 2016).

Modern applications typically involve high-dimensional state and action
spaces, and classical algorithms often lead to a computational complexity that
scales exponentially with the number of degrees of freedom in the model.
Understanding which structures can be used to design approximate methods that
can overcome this curse of dimensionality while retaining near-optimal
statistical guarantees is a question of paramount importance.

A class of algorithms that have proven successful to face high-dimensional
models is that of Natural Policy Gradient (NPG) methods (Amari, 1998; Kakade,
2002; Peters and Schaal, 2008; Bhatnagar et al., 2009). It has recently been
shown (Agarwal et al., 2020) that NPG converges to an optimal policy with an
iteration complexity that scales only logarithmically with the cardinality of
the action space and with no explicit dependence on the cardinality of the
state space.

Despite the favorable iteration complexity of NPG, NPG still faces the curse
of dimensionality in applications where the computational cost per iteration
scales exponentially with the number of degrees of freedom. This is the case
in the setting of multi-agent reinforcement learning (MARL), for instance,
where agents distributed over a network iteratively interact with each other
to maximize global notions of reward. In this setting, the computational
complexity of NPG—when applied to the entire network of agents—scales
exponentially with the dimension of the model, which corresponds to the number
of agents (see Section 3.1).

Along with the curse of dimensionality, NPG also faces scalability and
implementability issues within the MARL framework. Applying NPG to the entire
network of agents requires global communication, i.e. it requires each agent
to be able to communicate with every other agent in the network, at every time
step. This requirement is unrealistic in many multi-agent applications of
interest, where the network topology is typically sparse, often grid-like, and
where agents are only allowed to perform computation and communication in a
decentralized manner, interacting only with neighboring agents within a
certain range. These computational and communicational constraints arise, for
instance, in the case of sensor networks, e.g. (Rabbat and Nowak, 2004; Nedic
and Ozdaglar, 2009), and in the case of intelligent transportation systems,
e.g. (Adler and Blue, 2002).

Over the past decades, various approaches have been proposed to address the
curse of dimensionality in high-dimensional reinforcement learning models and,
before that, in high-dimensional dynamical programming models, where exact
knowledge of the probabilistic structure describing the environment is
assumed. A popular approach involves designing algorithms that can exploit
notions of _locality_ , which encodes the assumption that, in some regimes,
information can dissipate when it propagates through the network so that
global computation and communication are not required to meet a prescribed
level of error accuracy. Exploiting locality prompted the use of ad-hoc
approximate factorization and truncation techniques, such as expressing the
value function as a linear combination of basis functions that only depend on
a small subset of local variables (Koller and Parr, 1999; Guestrin et al.,
2001b; Koller and Parr, 2013; Yang and Wang, 2019; Jin et al., 2020). These
ideas have been applied to the MARL setting (Guestrin et al., 2001a, 2002;
Sunehag et al., 2017; Rashid et al., 2018; Zhang et al., 2018a, b; Zhang and
Zavlanos, 2019) and have proven successful in experiments, but lack
theoretical guarantees or non-asymptotic analysis. A recent line of work has
formally considered spatial decay of correlation assumptions for nearest-
neighbors dynamics and designed decentralized algorithms based on policy
gradient and actor-critic methods (Qu and Li, 2019; Qu et al., 2020a; Lin et
al., 2020; Qu et al., 2020b), establishing non-asymptotic convergence
guarantees towards a _stationary_ point, but not towards an _optimal_
policy.111Remark 10 gives a complete comparison of our results against
previous findings that exploit the same type of decay of correlation
assumption. An application of the same principles to the setting of _mean-
field_ MARL (Yang et al., 2018) can be found in Haotian Gu (2021), where the
authors show that a neural network based version of the actor-critic algorithm
can achieve global convergence. In this setting, however, agents are
considered to be indistinguishable and the transition scheme of an agent is
only affected by the mean effect from its neighbors.

In this paper, we design a decentralized algorithm for the MARL setting based
on the NPG framework that only uses local computations and communication for
neighbors of agents within a certain range. We show that our algorithm can
provably exploit spatial decay of correlation properties to overcome the curse
of dimensionality, establishing non-asymptotic convergence guarantees to a
globally _optimal_ policy. In particular, we consider a general formulation of
the decay of correlation assumption from statistical mechanics and probability
theory (Dobrusin, 1970; Föllmer, 1982; Georgii, 2011), whereby agents have an
influence on each other that decays exponentially with their distance on the
network. This type of assumption has been previously considered in the
learning literature, e.g. in Mitliagkas and Mackey (2017); Dagan et al.
(2019); Borja Balle and Geumlek (2019); Prasad et al. (2020); Ilias
Diakonikolas and Sun (2021), and also in the MARL setting, c.f. discussion in
the previous paragraph. Under this assumption, we derive convergence bounds
that are the same as those established for (centralized) NPG in (Agarwal et
al., 2020), worsened only by a localization error that decreases exponentially
with the radius of the communication range. A key feature of our bounds is
that they are _dimension-free_ , as they do not depend on the number of
agents, and depend only logarithmically on the cardinality of the action space
of _individual_ agents and do not explicitly depend on the state space of
individual agents. The localization radius controls the trade-off between
statistical accuracy and computational complexity, as the overall
computational cost of our algorithm scales only with respect to the number of
agents within the local communication radius, and not with the total number of
agents in the network.

Our contribution fits into the more general literature that has shown how
spatial decay of correlations can be used to establish dimension-free results
and are of interest in a variety of settings, such as (Gamarnik, 2013;
Gamarnik et al., 2014), mixing times in spin systems (Hayes, 2006; Dyer et
al., 2006), particle filtering (Rebeschini and Van Handel, 2015), epidemics
(Mei et al., 2017), social networks (Chakrabarti et al., 2008), communication
networks (Zocca, 2019), queuing networks (Papadimitriou and Tsitsiklis, 1994),
and smart transportation (Zhang and Pavone, 2016).

The paper organization is as follows. In Section 2 we describe the MARL
framework and we discuss the model assumptions we work with. In Section 3 we
describe NPG as presented in Agarwal et al. (2020) and discuss its limitations
when applied to MARL. In Section 4 we design a decentralized version of MARL
and state our main results. The Appendix contains all the proofs of our
statements and elaborates on the model assumptions.

##  2 Setting

Let $\mathcal{G}=(\mathcal{K},\mathcal{E})$ be an undirected graph describing
a network of $|\mathcal{K}|=K$ agents. On this graph, the distance
$d(k,k^{\prime})$ between two agents $k,k^{\prime}\in\mathcal{K}$ is defined
as the length of the shortest path between the two vertices. Let
$N^{r}_{k}=\\{k^{\prime}\in\mathcal{K}:d(k,k^{\prime})\leq r\\}$ denote the
neighborhood of radius $r$ of agent $k$, with $N_{k}=N^{1}_{k}$ and
$N^{r}_{-k}=\mathcal{K}\smallsetminus N^{r}_{k}$. Let $S_{k}$ and $A_{k}$ be
the state and action spaces associated with agent $k$. We consider a Markov
Decision Process (MDP) $(\mathcal{S},\mathcal{A},P,r,\gamma,\mu)$:
$\mathcal{S}=\mathcal{S}_{1}\times\dots\times\mathcal{S}_{K}$ and
$\mathcal{A}=\mathcal{A}_{1}\times\dots\times\mathcal{A}_{K}$ are,
respectively, the global state space and the global action space; $\forall
s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}$, $P_{k}(s^{\prime}_{k}|s,a)$ is
the local transition probability, that is the probability that agent $k$
transitions to state $s^{\prime}_{k}$ when the global state and action is
$(s,a)$, and
$P(s^{\prime}|s,a)=\prod_{k\in\mathcal{K}}P_{k}(s^{\prime}_{k}|s,a)$ is the
global transition probability;
$r(s,a)=\frac{1}{K}\sum_{k\in\mathcal{K}}r_{k}(s_{k},a_{k})$ is the global
(network-wide) reward function that we wish to maximize, where
$r_{k}:\mathcal{S}_{k}\times\mathcal{A}_{k}\rightarrow[0,1]$ is the reward for
agent $k$; $\gamma$ is the discount factor and $\mu$ is the starting state
distribution. At time $t$ denote the current state and action by $s(t)$ and
$a(t)$.

To each agent $k$ is assigned a local differentiable policy parameterized by
$\theta_{k}\in\Theta_{k}$,

$\pi_{\theta_{k}}(a_{k}|s)=\frac{e^{f_{\theta_{k}}(s,a_{k})}}{\sum_{a^{\prime}\in\mathcal{A}_{k}}e^{f_{\theta_{k}}(s,a^{\prime})}},$

which depends on the current global state $s$. Given the current global state
$s$, each agent acts independently of the others. Denote
$\theta=(\theta_{1},\dots,\theta_{K})$ and
$\Theta=\Theta_{1}\times\dots\times\Theta_{K}$, then
$\pi_{\theta}(a|s)=\prod_{k\in\mathcal{K}}\pi_{\theta_{k}}(a_{k}|s)$.

For a policy $\pi$ and for each agent $k$, let
$V_{k}^{\pi}:\mathcal{S}\rightarrow\mathbb{R}$ be the respective value
function, which is defined as the expected discounted cumulative reward with
starting state $s(0)=s$, namely,

$V^{\pi}_{k}(s)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{k}(s_{k}(t),a_{k}(t))\bigg{|}\pi,s(0)=s\right],$

where $a(t)\sim\pi(\cdot|s(t))$ and $s(t+1)\sim P(\cdot|s(t),a(t))$. Let
$V^{\pi}$ be the global value function, defined as
$V^{\pi}(s)=\frac{1}{K}\sum_{k\in\mathcal{K}}V^{\pi}_{k}(s)$, and
$V^{\pi}(\mu)$ be the expected global value function when the initial state
distribution is $\mu$, i.e. $V^{\pi}(\mu)=\mathbb{E}_{s\sim\mu}V^{\pi}(s)$.
Our objective is to find an optimal policy
$\pi^{\star}\in\mathop{\mathrm{argmax}}_{\pi}\mathbb{E}_{s\sim\mu}V^{\pi}(s)$.

For a policy $\pi$ and for each agent $k$, let
$Q_{k}^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ be the
respective Q-function, which is defined as the expected discounted cumulative
reward with starting state $s(0)=s$ and starting action $a(0)=a$, namely,

$Q^{\pi}_{k}(s,a)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{k}(s_{k}(t),a_{k}(t))\bigg{|}\pi,s(0)=s,a(0)=a\right],$

where $a(t)\sim\pi(\cdot|s(t))$ and $s(t+1)\sim P(\cdot|s(t),a(t))$. Let
$Q^{\pi}$ be the global value function, defined as
$Q^{\pi}(s,a)=\frac{1}{K}\sum_{k\in\mathcal{K}}Q^{\pi}_{k}(s,a)$.

Let $A_{k}^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ be the
advantage function for policy $\pi$ and agent $k$, representing the advantage
of taking the action $a$ at step $0$ and then following policy $\pi$, with
respect to following policy $\pi$ from the start, and defined as

$A_{k}^{\pi}(s,a)=Q_{k}^{\pi}(s,a)-V_{k}^{\pi}(s).$

Let $A^{\pi}(s,a)=\frac{1}{K}\sum_{k\in\mathcal{K}}A^{\pi}_{k}(s,a)$ be the
global advantage function.

We define the discounted state visitation distribution (Sutton et al., 1999),

$d_{\rho}^{\pi}(s)=(1-\gamma)\mathbb{E}_{s(0)\sim\rho}\sum_{t=0}^{\infty}\gamma^{t}P(s(t)=s|\pi,s(0)),$

and the discounted state-action visitation distribution,

$d^{\pi}_{\nu}(s,a)=(1-\gamma)\mathbb{E}_{s(0),a(0)\sim\nu}\sum_{t=0}^{\infty}\gamma^{t}P(s(t)=s,a(t)=a|\pi,s(0),a(0)),$

where the trajectory $(s(t),a(t))_{t\geq 0}$ is generated by the MDP following
policy $\pi$. Lastly, a function $f:\Theta\rightarrow\mathbb{R}$ is said to be
a $\delta$-smooth function of $\theta$ if,
$\forall\theta,\theta^{\prime}\in\Theta$,

$\left\lVert\nabla f(\theta)-\nabla
f(\theta^{\prime})\right\rVert_{2}\leq\delta\left\lVert\theta-\theta^{\prime}\right\rVert_{2}.$

###  2.1 Model Assumptions

We assume that a version of the Dobrushin condition (Georgii, 2011) holds for
the transition dynamics of the network of agents. Let
$TV(\mu,\nu)=\sup_{A\in\mathcal{F}}\left|\mu(A)-\nu(A)\right|$ be the total
variation distance between the probability distributions $\mu$ and $\nu$
defined on the $\sigma$-algebra $\mathcal{F}$.

###### Assumption 1

(Spatial Decay of Correlation for the Dynamics) Let $C\in\mathbb{R}^{K\times
K}$ be defined as follows:

$C_{ij}=\sup_{s_{j},s_{-j},a_{j},a_{-j},s^{\prime}_{j},a^{\prime}_{j}}TV(P_{i}(\cdot|s_{j},s_{-j},a_{j},a_{-j}),P_{i}(\cdot|s^{\prime}_{j},s_{-j},a^{\prime}_{j},a_{-j})).$

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

$\max_{k\in\mathcal{K}}\sum_{j\in\mathcal{K}}e^{\beta d(k,j)}C_{kj}\leq\rho,$

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

The element $(i,j)$ of the matrix $C$ represents the influence that a
perturbation of the state and action of agent $j$ has on the transition
probability of agent $i$. Assumption 1 encodes the fact that the transition
dynamics of each agent is exponentially less sensible to perturbations of the
state and action of further away agents. The requirement $\rho<1/\gamma$ comes
as we need the spatial decay of correlation for the dynamics to be strong
enough to induce a spatial decay for the Q-function (see Appendix B). A small
value of the discount factor $\gamma$ eases this requirement since it reduces
the effect of perturbations through time. When $\beta=0$ and $\gamma=1$,
Assumption 1 recovers the assumption in Qu et al. (2020a) as a particular
case.

Differently from Qu et al. (2020a), we require the Dobrushin condition to hold
for the policy as well. This is due to the fact that Assumption 1 is
sufficient to prove the decay of correlation for the Q-function, on which the
algorithm of Qu et al. (2020a) is based, but it is not sufficient to prove the
decay of correlation for the value function, which instead needs an additional
assumption on the policy. Since the NPG framework on which we build upon is
based on both the Q-function and the value function, we make the following
additional assumption.

###### Assumption 2

(Spatial Decay of Correlation for the Policy) Assume that there exist
$\xi,\beta\geq 0$ such that, $\forall\theta\in\Theta$,

$\sup_{s_{N^{r}_{k}},s_{N^{r}_{-k}},s^{\prime}_{N^{r}_{-k}}}TV(\pi_{\theta_{k}}(\cdot|s_{N^{r}_{k}},s_{N^{r}_{-k}}),\pi_{\theta_{k}}(\cdot|s_{N^{r}_{k}},s^{\prime}_{N^{r}_{-k}}))\leq\xi
e^{-\beta r}.$

###### Assumption 3

(Local Policy) Assume that, for any neighborhood radius $r$, the parameters
$\theta_{k}$ can be partitioned in $(\theta_{k})_{N^{r}_{k}}$ and
$(\theta_{k})_{N^{r}_{-k}}$ so that, if $(\theta_{k})_{N^{r}_{-k}}=0$, then

$\pi_{\theta_{k}}(a_{k}|s)=\pi_{\theta_{k}}(a_{k}|s_{N^{r}_{k}}),$
$\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi_{\theta_{k}}(a_{k}|s)=\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi_{\theta_{k}}(a_{k}|s_{N^{r}_{k}}).$

Assumptions 2 and 3 impose a design constraint for the policy class
$\\{\pi_{\theta}\,|\,\theta\in\Theta\\}$ rather than being assumptions on the
nature of the environment, as the case for Assumption 1. Assumption 2 encodes,
for the policy, a type of decay of correlation property that is weaker than
Assumption 1. Assumption 2 allows us to consider a policy class that presents
properties that are necessary for the optimal policy under Assumption 1, as we
show in Appendix C. Assumption 3 is made to address the communication
constraints of the network and requires the possibility of computing the
policy and its gradient without access to the information coming from distant
agents by setting their associated parameters to 0. In practice, we do only
need Assumption 3 to hold for the value of $r$ we want Theorem 9 to hold for.
In Appendix A, we describe a policy class that satisfies both Assumption 2 and
3 for any value of $r$.

###  2.2 Exponential Decay

To take advantage of the local structure of the network, Lin et al. (2020)
define a property regarding the dependence of $Q^{\pi}_{k}(s,a)$ on the
neighbors of $k$.

######  Definition 4 (Lin et al. (2020))

The $(c,\psi)$-exponential decay property for the Q-function holds if, for any
agent $k\in\mathcal{K}$ and for any $(s,a)$,
$(\widetilde{s},\widetilde{a})\in\mathcal{S}\times\mathcal{A}$ such that
$s_{N^{r}_{k}}=\widetilde{s}_{N^{r}_{k}},a_{N^{r}_{k}}=\widetilde{a}_{N^{r}_{k}}$,
we have that

$\left|Q_{k}^{\pi}(s,a)-Q_{k}^{\pi}(\widetilde{s},\widetilde{a})\right|\leq
c\psi^{r+1}.$

In our analysis, we need to define the exponential decay property for the
value function as well.

###### Definition 5

The $(c^{\prime},\phi)$-exponential decay property for the value function
holds if, for any agent $k\in\mathcal{K}$ and for any $s$,
$\widetilde{s}\in\mathcal{S}$ such that
$s_{N^{r}_{k}}=\widetilde{s}_{N^{r}_{k}}$, we have that

$\left|V_{k}^{\pi}(s)-V_{k}^{\pi}(\widetilde{s})\right|\leq
c^{\prime}\phi^{r+1}.$

These two properties mean that the cumulative discounted rewards of agents
have an exponential decaying dependence on the states and actions of distant
agents. We show that both these properties hold in our setting.

###### Proposition 6

If Assumptions 1 and 2 hold, then the exponential decay property holds for
both the Q-function and the value function with parameters
$(c,\psi)=\left(\frac{\gamma\rho e^{\beta}}{1-\gamma\rho},e^{-\beta}\right)$
and
$(c^{\prime},\phi)=\left(\frac{\gamma(\rho+\xi)e^{\beta}}{1-\gamma(\rho+\xi)},e^{-\beta}\right)$,
respectively.

For clarity of exposition, in the rest of the paper we make the following
assumption.

###### Assumption 7

Assume that the exponential decay property holds for the Q-function with
parameters $(c,\psi)$ and that it holds for the value function with parameters
$(c^{\prime},\phi)$.

##  3 Natural Policy Gradient

We consider NPG as presented in Agarwal et al. (2020), which has iteration
complexity that scales as $O(\sqrt{\log|\mathcal{A}|/T})$, where $T$ is the
number of iterations. We now summarize the algorithm and the results in
Agarwal et al. (2020) and show what problems arise in the multi-agent setting
that we consider.

Let $\pi_{\theta}$ be a differentiable policy and define the Fisher
information matrix induced by $\pi_{\theta}$ as

$F_{\mu}(\theta)=\mathbb{E}_{s\sim
d_{\mu}^{\pi}}\mathbb{E}_{a\sim\pi_{\theta}(\cdot|s)}\left[\nabla_{\theta}\log\pi_{\theta}(a|s)(\nabla_{\theta}\log\pi_{\theta}(a|s))^{\top}\right].$

The NPG update, with step-size $\eta$, is defined as

$\theta^{(t+1)}=\theta^{(t)}+\eta
F_{\mu}(\theta^{(t)})^{-1}\nabla_{\theta}V^{\theta^{(t)}}(\mu),$ (1)

where $\theta^{(t)}$ is the set of parameters at iteration $t$,
$\nabla_{\theta}V^{\theta}(\mu)$ is the gradient of the value function with
respect to the policy parameters, and $F_{\mu}(\theta^{(t)})^{-1}$ is the
Moore-Penrose pseudo-inverse of the Fisher information matrix. As discussed in
Agarwal et al. (2020), the update in (1) is equivalent to solving the problem

$w_{\star}\in\mathop{\mathrm{argmin}}_{w}\mathbb{E}_{s\sim
d_{\mu}^{\pi_{\theta}},a\sim\pi_{\theta}(\cdot|s)}\left[\left(A^{\pi_{\theta}}(s,a)-w\cdot\nabla_{\theta}\log\pi_{\theta}(\cdot|s)\right)^{2}\right]$
(2)

and then performing the following update:

$\theta^{(t+1)}=\theta^{(t)}+\frac{\eta}{1-\gamma}w^{\star}.$ (3)

Define

$L(w,\theta,\nu):=\mathbb{E}_{s,a\sim\nu}\left[\left(A^{\pi_{\theta}}(s,a)-w\cdot\nabla_{\theta}\log\pi_{\theta}(a|s)\right)^{2}\right].$

Assume that $\log\pi_{\theta}(a|s)$ is a $\delta$-smooth function of $\theta$
and that $\pi^{(0)}$ is the uniform distribution. Let
$d^{(t)}=d^{\pi_{t}}_{\nu}(s,a)$ and
$d^{\star}(s,a)=d^{\pi^{\star}}_{\mu}(s)\pi^{\star}(a|s)$. Let $\nu$ be a
distribution of $s,a$ such that

$\sup_{w\in\mathbb{R}^{d}}\frac{w^{\top}\Sigma^{(t)}_{d^{\star}}w}{w^{\top}\Sigma^{(t)}_{\nu}w}\leq\kappa,$

where

$\Sigma_{\nu}^{\theta}=\mathbb{E}_{s,a\sim\nu}\left[\nabla_{\theta}\log\pi_{\theta}(a|s)(\nabla_{\theta}\log\pi_{\theta}(a|s))^{\top}\right]$

and $\Sigma^{(t)}=\Sigma^{\theta^{(t)}}$. Lastly, assume that

$\displaystyle\mathbb{E}\left[L(w^{(t)}_{\star},\theta^{(t)},d^{\star})\right]$
$\displaystyle\leq\varepsilon_{\text{bias}},$
$\displaystyle\mathbb{E}\left[L(w^{(t)},\theta^{(t)},d^{(t)})-L(w^{(t)}_{\star},\theta^{(t)},d^{(t)})|\theta^{(t)}\right]$
$\displaystyle\leq\varepsilon_{\text{stat}},$

where

$w^{(t)}_{\star}\in\mathop{\mathrm{argmin}}_{\left\lVert w\right\rVert_{2}\leq
W}L(w,\theta^{(t)},d^{(t)})$

and the expectations are taken w.r.t. the sequence
$(w^{(t)})_{t=0,\dots,T-1}$. Then, running algorithm (3) for $T$ time steps
with $\eta=\sqrt{2\frac{\log|\mathcal{A}|}{(\delta W^{2}T)}}$ for a given
parameter $W$, we have the following guarantee: [Agarwal et al. (2020),
Theorem 6.2]

$\mathbb{E}\left[\min_{t\leq
T}\left\\{V^{\pi^{\star}}(\mu)-V^{(t)}(\mu)\right\\}\right]\leq\frac{W}{1-\gamma}\sqrt{\frac{2\delta\log|\mathcal{A}|}{T}}+\sqrt{\frac{\kappa\varepsilon_{\text{stat}}}{(1-\gamma)^{3}}}+\frac{\sqrt{\varepsilon_{\text{bias}}}}{1-\gamma}.$
(4)

As we highlighted in the introduction, the guarantee (4) is particularly
suitable for high-dimensional settings, as there is no explicit dependence on
$|\mathcal{S}|$ and the dependence on $|\mathcal{A}|$ is only logarithmic. As
to implicit dependencies, Agarwal et al. (2020) state that it is reasonable to
expect that $\kappa$ is not a quantity related to $|\mathcal{S}|$. On the
other hand, $\varepsilon_{\text{stat}}$ and $\varepsilon_{\text{bias}}$ are
constants related to a minimization problem that depends on both $\mathcal{S}$
and $\mathcal{A}$.

###  3.1 Curse of Dimensionality and Scalability/Implementabily Issues in MARL

When applied to the MARL setting, with
$\mathcal{S}=\mathcal{S}_{1}\times\dots\times\mathcal{S}_{K}$ and
$\mathcal{A}=\mathcal{A}_{1}\times\dots\times\mathcal{A}_{K}$, NPG would incur
a curse of dimensionality or scalability and implementabily issues, depending
on the approach used for the minimization problem in (6). The guarantees for
the algorithm in Agarwal et al. (2020) would yield:

$\mathbb{E}\left[\min_{t<T}\\{V^{\pi^{\star}}(\rho)-V^{(t)}(\rho)\\}\right]\leq\frac{WK}{1-\gamma}\sqrt{\frac{2\delta\log\max_{k\in\mathcal{K}}|\mathcal{A}_{k}|}{T}}+\sqrt{\frac{\kappa\varepsilon_{\text{stat}}}{(1-\gamma)^{3}}}+\frac{\sqrt{\varepsilon_{\text{bias}}}}{1-\gamma},$
(5)

where

$w^{(t)}_{\star}\in\mathop{\mathrm{argmin}}_{\left\lVert
w\right\rVert_{2}\leq\sqrt{K}W}L(w,\theta^{(t)},d^{(t)}),$ (6)

under the assumptions

$\displaystyle\mathbb{E}\left[L(w^{(t)},\theta^{(t)},d^{(t)})-L(w^{(t)}_{\star},\theta^{(t)},d^{(t)})|\theta^{(t)}\right]$
$\displaystyle\leq\varepsilon_{\text{stat}},$
$\displaystyle\mathbb{E}\left[L(w^{(t)}_{\star},\theta^{(t)},d^{\star})\right]$
$\displaystyle\leq\varepsilon_{\text{bias}}.$

In the original analysis in Agarwal et al. (2020), $W$ is a parameter set by
the user to control the norm of $w^{(t)}_{\star}$. In our setting, we
normalize this parameter to $\sqrt{K}W$, which is analogous to requiring, for
each agent $k$, the maximum norm of its optimal update $w^{(t)}_{k,\star}$ to
be $W$. Not doing so would mean keeping a constant parameter $W$ despite
increases in the dimensions, i.e. agents, of problem (6), incurring increases
in the bias term. In the multi-agent setting, the iteration complexity given
by the bound in (5) is worse by a factor $K$, compared to the single-agent
setting. The curse of dimensionality appears when solving the minimization
problem in (6), e.g. with gradient descent because the computation of exact
gradients involves a sum/integral over $\mathcal{S}\times\mathcal{A}$, which
has a dimension that grows exponentially with the number of agents. If we
solve the minimization problem with stochastic projected gradient descent,
then the problem of computing gradients disappears as we _assume_ access to
samples to estimate gradients; however, the statistical guarantee becomes
$O(K^{2}/\sqrt{N})$, from being $O(1/\sqrt{N})$ in the single-agent setting,
due to the increase in dimensionality of the update $w$, in particular due to
the scaling bound $\left\lVert w\right\rVert_{2}\leq\sqrt{K}W$ that is used by
a classical convergence result of stochastic projected gradient descent
(Bubeck, 2014). Implementing a sampler could, in turn, involve a curse of
dimensionality.

The dependencies of the minimization problem in (6) cause the algorithm to
incur additional scalability and implementability issues. As the projection
step, the advantage function and the policy gradient depend on the states and
actions of the entire network, which do not factorize, each agent would have
to communicate to every other agent in the network at each iteration to solve
the problem. As mentioned in the introduction, requiring such a level of
communication is rarely viable in real-world applications in the decentralized
MARL setting.

###### Remark 8

These aforementioned problems do not arise in case of independent agents,
where, for each agent $k$, the local transition probabilities satisfy
$P_{k}(s^{\prime}_{k}|s,a)=P_{k}(s^{\prime}_{k}|s_{k},a_{k})$ and policies
satisfy $\pi_{\theta_{k}}(a_{k}|s)=\pi_{\theta_{k}}(a_{k}|s_{k})$. In this
setting, as we show in Appendix D, it is possible to show that applying NPG to
the whole network of $K$ agents corresponds to running $K$ independent runs of
NPG applied to individual agents and to recover the same results of Agarwal et
al. (2020) for the individual agents.

##  4 Decentralized NPG

We design a decentralized version of NPG that is capable of exploiting the
spatial decay of correlation properties that we assume and of avoiding the
curse of dimensionality while still approximately converging to a globally
optimal policy. We do so by limiting the communication range to agents that
are at most at distance $r$ and defining, for each agent $k$, the localized
advantage function, localized value function, localized Q-function, as
follows:

$\displaystyle\widetilde{A}_{k}^{\pi}(s_{N^{r}_{k}},a_{N^{r}_{k}})$
$\displaystyle=\widetilde{Q}_{k}^{\pi}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\widetilde{V}_{k}^{\pi}(s_{N^{r}_{k}}),$
$\displaystyle\widetilde{V}^{\pi}_{k}(s_{N^{r}_{k}})$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{k}(s_{k}(t),a_{k}(t))\big{|}\pi,s_{N^{r}_{k}}(0)=s_{N^{r}_{k}}\right],$
$\displaystyle\widetilde{Q}^{\pi}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{k}(s_{k}(t),a_{k}(t))\big{|}\pi,s_{N^{r}_{k}}(0)=s_{N^{r}_{k}},a_{N^{r}_{k}}(0)=a_{N^{r}_{k}}\right].$

Following Assumption 3, we set $(\theta_{k})_{N_{-k}^{r}}=0,\forall
k\in\mathcal{K}$ and we never update these parameters, so that the policy of
an agent and its gradient do not depend on the states of agents whose distance
is greater than $r$. For each agent $k$, define the loss function

$\widetilde{L}_{k}^{r}(w,\theta,\nu)=\mathbb{E}_{s,a\sim\nu}\left[\left(\widetilde{A}^{\pi_{\theta}}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N_{k}^{r}}}\log\pi_{\theta_{k}}(a_{k}|s_{N^{r}_{k}})\cdot
w\right)^{2}\right].$ (7)

The minimization problem that each agent $k$ aims to solve at each step
becomes

$w^{\star}\in\mathop{\mathrm{argmin}}_{\left\lVert w\right\rVert_{2}\leq
W}\widetilde{L}^{r}_{k}(w,\theta^{(t)},d^{(t)}).$ (8)

In Appendix F we show show how to solve this minimization problem in a
decentralized manner and that, even if $d^{(t)}$ is a global distribution, it
is possible to build a decentralized sampler of it assuming only access to a
global clock.

Input: Learning rate $\eta$; numbers of iterations $T$; an initialized policy
$\pi^{(0)}$.

Set $(\theta_{k})_{N_{-k}^{r}}=0,\forall k\in\mathcal{K}$;

for  _$t=0,\dots,T-1$ ; $k\in\mathcal{K}$_ do

Compute approximately $w^{(t)}_{k}\in\mathop{\mathrm{argmin}}_{\left\lVert
w\right\rVert_{2}\leq W}\widetilde{L}^{r}_{k}(w,\theta^{(t)},d^{(t)})$;

Compute the update
$(\theta_{k})_{N_{k}^{r}}^{(t+1)}=(\theta_{k})_{N_{k}^{r}}^{(t)}+\frac{\eta}{1-\gamma}w^{(t)}_{k}.$

end for

Algorithm 1 Decentralized NPG

Exploiting decay of correlation properties and the policy design constraints
in Assumption 3, Algorithm 1 removes the dependence on $K$ from the iteration
complexity bound and addresses the curse of dimensionality and scalability and
implementability issues outlined in Section 3.1.

###### Theorem 9

Assume that Assumption 3 and Assumption 7 hold. Assume that
$\log\pi_{\theta}(a|s)$ is a $\delta$-smooth function of $\theta$ and that
$\pi^{(0)}$ is the uniform distribution. Let $d^{(t)}=d^{\pi_{t}}_{\nu}(s,a)$
and $d^{\star}(s,a)=d^{\pi^{\star}}_{\mu}(s)\pi^{\star}(a|s)$. Let $\nu$ be a
distribution of $s,a$ for which there exists $\kappa^{\prime}\geq 0$ such that

$\max_{k\in\mathcal{K}}\sup_{w\in\mathbb{R}^{d}}\frac{w^{\top}\Sigma^{(t)}_{d^{\star},k}w}{w^{\top}\Sigma^{(t)}_{\nu,k}w}\leq\kappa^{\prime},$

where, $\forall\theta,\nu,k$

$\Sigma_{\nu,k}^{\theta}=\mathbb{E}_{s,a\sim\nu}\left[\nabla_{(\theta_{k})_{N_{k}^{r}}}\log\pi_{\theta}(a_{k}|s_{N_{k}^{r}})(\nabla_{(\theta_{k})_{N_{k}^{r}}}\log\pi_{\theta}(a_{k}|s_{N_{k}^{r}}))^{\top}\right]$

and $\Sigma_{\nu,k}^{(t)}\equiv\Sigma_{\nu,k}^{\theta^{(t)}}$. Let

$\displaystyle\max_{k\in\mathcal{K}}\mathbb{E}\left[\widetilde{L}_{k}(w^{(t)}_{k,\star},\theta^{(t)},d^{\star})\right]$
$\displaystyle\leq\varepsilon_{\text{bias}},$
$\displaystyle\max_{k\in\mathcal{K}}\mathbb{E}\left[\widetilde{L}_{k}(w^{(t)}_{k},\theta^{(t)},d^{(t)})-\widetilde{L}_{k}(w^{(t)}_{k,\star},\theta^{(t)},d^{(t)})\big{|}\theta^{(t)}\right]$
$\displaystyle\leq\varepsilon_{\text{stat}},$

where

$w^{(t)}_{k,\star}\in\mathop{\mathrm{argmin}}_{\left\lVert
w\right\rVert_{2}\leq W}\widetilde{L}_{k}(w,\theta^{(t)},d^{(t)}).$

Then, Algorithm 1, with $\eta=\sqrt{2\frac{\log|\mathcal{A}|}{(\delta
KW^{2}T)}}$, has the following guarantee:

$\displaystyle\mathbb{E}\left[\min_{t<T}\\{V^{\pi^{\star}}(\mu)-V^{(t)}(\mu)\\}\right]$
$\displaystyle\leq\frac{W}{1-\gamma}\sqrt{\frac{2\delta\log\max_{k\in\mathcal{K}}|\mathcal{A}_{k}|}{T}}+\sqrt{\frac{\kappa^{\prime}\varepsilon_{\text{stat}}}{(1-\gamma)^{3}}}+\frac{\sqrt{\varepsilon_{\text{bias}}}}{1-\gamma}$
(9)
$\displaystyle\quad+\underbrace{\frac{c\psi^{r+1}+c^{\prime}\phi^{r+1}}{1-\gamma}}_{\text{localization
error}}.$

Agent-wise, the assumptions in Theorem 9 correspond to the assumptions made in
Agarwal et al. (2020), in a setting where, for each agent $k$, the state space
and the action space are $\mathcal{S}_{N_{k}^{r}}$ and $\mathcal{A}_{k}$,
respectively, where the policy is defined as
$\pi_{\theta}(a|s)=\pi_{\theta_{k}}(a_{k}|s_{N_{k}^{r}})$ and where the update
$w^{(t)}_{k}$ is bounded by $W$. Theorem 9 shows that Decentralized NPG
recovers the iteration complexity of the algorithm in Agarwal et al. (2020),
worsened only by the fourth term on the RHS of (9). This localization error is
exponentially small in $r$. Theorem 9 provides a dimension-free guarantee on
the average expected cumulative rewards of the whole network, as the upper
bound in (9) does not depend on the number of agents $K$ in the network, and
it depends only on the logarithm of the cardinality of the action space of an
individual agent, with no explicit dependence on the state space of agents.

Theorem 9 shows that, under the assumption on spatial decay of correlation,
Decentralized NPG solves the curse of dimensionality and the scalability and
implementability issues outlined in Section 3.1. The minimization problem in
(8) can be approximately solved in a decentralized manner through stochastic
projected gradient descent, as we show in Appendix F, which leads to
computational savings as we manage to eliminate the dependency on $K$ from the
statistical guarantee of the algorithm, obtaining the same computational
complexity of the single-agent setting, i.e. $O(1/\sqrt{N})$, where $N$ is the
number of gradient steps, which is not surprising because problem (8) regards
only the advantage function and the policy of an individual agent. Then, using
stochastic projected gradient descent and the sampler in Algorithm 2, we
recover, for each agent, the same expected sample complexity of the single
agent setting ($2NT/(1-\gamma)$, where $2/(1-\gamma)$ is the expected length
of a sampler episode). Decentralized NPG can be run locally by each agent and
only requires information from neighbors within distance $r$.

The role of the term $\varepsilon_{\text{bias}}$ in (9) has a difference from
the role that $\varepsilon_{\text{bias}}$ has in (4) (Agarwal et al., 2020).
They both represent the worst-case error that is made by the agents when they
approximate their current advantage function with a linear combination of the
elements of the gradient of their current policy and encode the transfer error
that we make shifting the distribution to $d^{\star}$. In addition to that,
$\varepsilon_{\text{bias}}$ in (9) also encodes the localization error that we
make in Algorithm 1 by using the localized loss defined in (7). In Appendix G
we give a bound for this localization error of the bias term, showing that the
localized bias is at most the non-localized bias, i.e. the bias associated
with an infinite range parameter $r$, plus a quantity that decreases to $0$
exponentially fast in $r$.

###### Remark 10

The works in (Qu and Li, 2019; Qu et al., 2020a; Lin et al., 2020; Qu et al.,
2020b) are closely related to our contribution, as they also use decay of
correlation assumptions to provably avoid the curse of dimensionality in MARL.
Our contribution differs from these works in the following main ways:

  1. 1.

(Decay of correlation) We consider a more general version of the decay of
correlation property (Assumption 1) and, differently from them, we also
require a decay of correlation property to hold for the policy (Assumption 2).
Assumption 1 recovers the version they consider in Qu et al. (2020a) in the
case $\beta=0$ and $\gamma=1$. The generality of our condition allows us to
consider transition dynamics that are not truncated, as they do, and to
control the truncation of the policy.

  2. 2.

(Methodology) Our method is based on NPG framework, while their methods is
based on policy gradient and actor-critic methods.

  3. 3.

(Optimality) We present statistical error bounds w.r.t. to the _optimal_
policy, while the bounds they give are w.r.t. a stationary policy.

  4. 4.

(Computational complexity) Our method has a computational complexity that does
not depend, for any agent $k$, on the number of agents $K$ or the number of
neighbors $|N_{k}^{r}|$. The method in (Qu et al., 2020b) is shown to have a
computational complexity that scales as $O(\log|\mathcal{S}||\mathcal{A}|)$,
hence depending linearly on $K$, using additional assumptions on the minimum
local exploration. The method in (Lin et al., 2020) is shown to have
computational complexity that scales as
$O(\log\max_{k\in\mathcal{K}}|\mathcal{S}_{N_{k}^{r}}||\mathcal{A}_{N_{k}^{r}}|)$,
hence depending linearly on $|N_{k}^{r}|$, using additional assumptions on the
stationarity and on the mixing rates of the MDP.

  5. 5.

(Statistical/Iteration Complexity) Under the only assumptions on decay of
correlation and local policy, our method has an iteration complexity that
scales as $O(\sqrt{\log\max_{k\in\mathcal{K}}|\mathcal{A}_{k}|})$. The methods
in (Qu et al., 2020b; Lin et al., 2020) have an iteration complexity that does
not depend on the state or action spaces.

##  5 Conclusion

We have investigated applications of the NPG framework to MARL, showing how a
standard assumption on the spatial decay of correlation for the dynamics and
for the policy on a network of agents, expressed through a form of Dobrushin
condition, induces a form of exponential decay in the cumulative rewards that
can be exploited by a localized version of NPG to avoid the curse of
dimensionality. The version of NPG that we design scales to large networks and
yields convergence guarantees to the optimal policy that are analogous to the
ones in Agarwal et al. (2020), worsened only by a localization error that
decreases exponentially with the communication radius. Our analysis does not
consider regularization, which has been shown to accelerate convergence for
NPG methods (Geist et al., 2019) and yield linear convergence rates (Cen et
al., 2020).

## References

  * Adler and Blue [2002] Jeffrey L Adler and Victor J Blue.  A cooperative multi-agent transportation management and route guidance system.  _Transportation Research Part C: Emerging Technologies_ , pages 433–454, 2002.
  * Agarwal et al. [2020] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.  Optimality and approximation with policy gradient methods in markov decision processes.  _Conference on Learning Theory_ , pages 64–66, 2020.
  * Amari [1998] Shun-Ichi Amari.  Natural gradient works efficiently in learning.  _Neural computation_ , 10:251–276, 1998.
  * Bhatnagar et al. [2009] Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee.  Natural actor–critic algorithms.  _Automatica_ , pages 2471–2482, 2009.
  * Borja Balle and Geumlek [2019] Marco Gaboardi Borja Balle, Gilles Barthe and Joseph Geumlek.  Privacy amplification by mixing and diffusion mechanisms.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Bubeck [2014] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _arXiv preprint arXiv:1405.4980_ , 2014.
  * Cen et al. [2020] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi.  Fast global convergence of natural policy gradient methods with entropy regularization.  _arXiv preprint arXiv: 1912.02906v2_ , 2020.
  * Chakrabarti et al. [2008] Deepayan Chakrabarti, Yang Wang, Chenxi Wang, Jurij Leskovec, and Christos Faloutsos.  Epidemic thresholds in real networks.  _ACM Transactions on Information and System Security_ , pages 1–26, 2008.
  * Dagan et al. [2019] Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Siddhartha Jayanti.  Learning from weakly dependent data under dobrushin’s condition.  In _Conference on Learning Theory_ , pages 914–928. PMLR, 2019.  ISBN 2640-3498.
  * Dobrusin [1970] RL Dobrusin.  Definition of a system of random variables by means of conditional distributions.  _Theory of Probability and its Applications_ , pages 458–486, 1970\.
  * Dyer et al. [2006] Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum.  _Dobrushin conditions and systematic scan_ , pages 327–338.  2006\.
  * Föllmer [1982] Hans Föllmer.  A covariance estimate for gibbs measures.  _Journal of Functional Analysis_ , pages 387–395, 1982.
  * Gamarnik [2013] David Gamarnik.  _Correlation decay method for decision, optimization, and inference in large-scale networks_ , pages 108–121.  2013\.
  * Gamarnik et al. [2014] David Gamarnik, David A Goldberg, and Theophane Weber.  Correlation decay in random decision networks.  _Mathematics of Operations Research_ , pages 229–261, 2014.
  * Geist et al. [2019] Matthieu Geist, Bruno Scherrer, and Olivier Pietquin.  A theory of regularized markov decision processes.  In _International Conference on Machine Learning_ , pages 2160–2169, 2019.
  * Georgii [2011] Hans-Otto Georgii.  _Gibbs measures and phase transitions_.  2011\.
  * Gibbs and Su [2002] Alison L Gibbs and Francis Edward Su.  On choosing and bounding probability metrics.  _International Statistical Review_ , pages 419–435, 2002.
  * Guestrin et al. [2001a] Carlos Guestrin, Daphne Koller, and Ronald Parr.  Multiagent planning with factored mdps.  In _Advances in Neural Information Processing Systems_ , pages 1523–1530, 2001a.
  * Guestrin et al. [2001b] Carlos Guestrin, Daphne Koller, and Ronald Parr.  Max-norm projections for factored mdps.  In _International Joint Conference on Artificial Intelligence_ , pages 673–680, 2001b.
  * Guestrin et al. [2002] Carlos Guestrin, Michail Lagoudakis, and Ronald Parr.  Coordinated reinforcement learning.  In _International Conference on Machine Learning_ , pages 227–234, 2002.
  * Haotian Gu [2021] Xiaoli Wei Renyuan Xu Haotian Gu, Xin Guo.  Mean-field multi-agent reinforcement learning: A decentralized network approach.  _arXiv preprint arXiv: 2108.02731_ , 2021.
  * Hayes [2006] Thomas P Hayes.  A simple condition implying rapid mixing of single-site dynamics on spin systems.  In _Annual IEEE Symposium on Foundations of Computer Science_ , pages 39–46, 2006.
  * Ilias Diakonikolas and Sun [2021] Alistair Stewart Ilias Diakonikolas, Daniel M. Kane and Yuxin Sun.  Outlier-robust learning of ising models under dobrushins condition.  In _Conference on Learning Theory_ , 2021.
  * Jin et al. [2020] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In Abernethy Jacob and Agarwal Shivani, editors, _Conference on Learning Theory_ , pages 2137–2143, 2020.
  * Kakade [2002] S Kakade.  A natural policy gradient.  _Advances in Neural Information Processing Systems_ , 2002.
  * Koller and Parr [2013] Daphne Koller and Ron Parr.  Policy iteration for factored mdps.  _arXiv preprint arXiv:1301.3869_ , 2013.
  * Koller and Parr [1999] Daphne Koller and Ronald Parr.  Computing factored value functions for policies in structured mdps.  In _International Joint Conference on Artificial Intelligence_ , pages 1332–1339, 1999.
  * Lin et al. [2020] Yiheng Lin, Guannan Qu, Longbo Huang, and Adam Wierman.  Distributed reinforcement learning in multi-agent networked systems.  _arXiv preprint arXiv:2006.06555_ , 2020.
  * Mei et al. [2017] Wenjun Mei, Shadi Mohagheghi, Sandro Zampieri, and Francesco Bullo.  On the dynamics of deterministic epidemic propagation over networks.  _Annual Reviews in Control_ , pages 116–128, 2017.
  * Mitliagkas and Mackey [2017] Ioannis Mitliagkas and Lester Mackey.  Improving gibbs sampler scan quality with dogs.  In _International Conference on Machine Learning_ , pages 2469–2477. PMLR, 2017.  ISBN 2640-3498.
  * Nedic and Ozdaglar [2009] Angelia Nedic and Asuman Ozdaglar.  Distributed subgradient methods for multi-agent optimization.  _IEEE Transactions on Automatic Control_ , pages 48–61, 2009.
  * Papadimitriou and Tsitsiklis [1994] Christos H Papadimitriou and John N Tsitsiklis.  The complexity of optimal queueing network control.  In _IEEE Conference on Structure in Complexity Theory_ , pages 318–322, 1994.
  * Peters and Schaal [2008] Jan Peters and Stefan Schaal.  Natural actor-critic.  _Neurocomputing_ , pages 1180–1190, 2008.
  * Prasad et al. [2020] Adarsh Prasad, Vishwak Srinivasan, Sivaraman Balakrishnan, and Pradeep Ravikumar.  On learning ising models under huber’s contamination model.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Qu and Li [2019] Guannan Qu and Na Li.  Exploiting fast decaying and locality in multi-agent mdp with tree dependence structure.  In _IEEE Conference on Decision and Control_ , 2019.
  * Qu et al. [2020a] Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li.  Scalable multi-agent reinforcement learning for networked systems with average reward.  _Advances in Neural Information Processing Systems_ , pages 2074–2086, 2020a.
  * Qu et al. [2020b] Guannan Qu, Adam Wierman, and Na Li.  Scalable reinforcement learning of localized policies for multi-agent networked systems.  In _Conference on Learning for Dynamics and Control_ , 2020b.
  * Rabbat and Nowak [2004] Michael Rabbat and Robert Nowak.  Distributed optimization in sensor networks.  In _International Symposium on Information Processing in Sensor Networks_ , pages 20–27, 2004.
  * Rashid et al. [2018] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson.  Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning.  In _International Conference on Machine Learning_ , pages 4295–4304, 2018.
  * Rebeschini and Van Handel [2015] Patrick Rebeschini and Ramon Van Handel.  Can local particle filters beat the curse of dimensionality?  _Annals of Applied Probability_ , pages 2809–2866, 2015.
  * Shalev-Shwartz and Ben-David [2014] Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Shalev-Shwartz et al. [2016] Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua.  Safe, multi-agent, reinforcement learning for autonomous driving.  _arXiv preprint arXiv:1610.03295_ , 2016.
  * Silver et al. [2016] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.  Mastering the game of go with deep neural networks and tree search.  _Nature_ , pages 484–489, 2016.
  * Silver et al. [2017] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George Van Den Driessche, Thore Graepel, and Demis Hassabis.  Mastering the game of go without human knowledge.  pages 354–359, 2017.
  * Sunehag et al. [2017] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel.  Value-decomposition networks for cooperative multi-agent learning.  _arXiv preprint arXiv:1706.05296_ , 2017.
  * Sutton et al. [1999] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  In _Advances in Neural Information Processing Systems_ , pages 1057–1063, 1999.
  * Yang and Wang [2019] Lin Yang and Mengdi Wang.  Sample-optimal parametric q-learning using linearly additive features.  In Chaudhuri Kamalika and Salakhutdinov Ruslan, editors, _International Conference on Machine Learning_ , pages 6995–7004, 2019.
  * Yang et al. [2018] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang.  Mean field multi-agent reinforcement learning.  In _International Conference on Machine Learning_. PMLR, 2018.
  * Zhang et al. [2018a] Kaiqing Zhang, Zhuoran Yang, and Tamer Basar.  Networked multi-agent reinforcement learning in continuous spaces.  In _IEEE Conference on Decision and Control_ , pages 2771–2776, 2018a.
  * Zhang et al. [2018b] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar.  Fully decentralized multi-agent reinforcement learning with networked agents.  In _International Conference on Machine Learning_ , pages 5872–5881, 2018b.
  * Zhang and Pavone [2016] Rick Zhang and Marco Pavone.  Control of robotic mobility-on-demand systems: a queueing-theoretical perspective.  _The International Journal of Robotics Research_ , pages 186–203, 2016.
  * Zhang and Zavlanos [2019] Yan Zhang and Michael M Zavlanos.  Distributed off-policy actor-critic reinforcement learning with policy consensus.  In _IEEE Conference on Decision and Control_ , pages 4674–4679, 2019\.
  * Zocca [2019] Alessandro Zocca.  Temporal starvation in multi-channel csma networks: an analytical framework.  _Queueing Systems_ , pages 241–263, 2019.

##  Appendix A Policy Class Example

Let $\widetilde{r}=\max_{k,k^{\prime}\in\mathcal{K}}d(k,k^{\prime})$ be the
maximum distance between two agents. Define a set of parameterized
differentiable functions
$\\{f_{(\theta_{k})_{r}}:\mathcal{S}_{N^{r}_{k}}\times\mathcal{A}_{k}\rightarrow\mathcal{C}|0\leq
r\leq\widetilde{r}\\}$, where $\mathcal{C}\subset[-C,C]$ and $C>0$, a set of
parameters $\\{\alpha_{r}\geq 0|0\leq r\leq\widetilde{r}\\}$ and let, for each
agent $k$,

$f_{\theta_{k}}(s,a_{k})=\sum_{r=0}^{\widetilde{r}}\alpha_{r}f_{(\theta_{k})_{r}}(s_{N^{r}_{k}},a_{k}),$
$\pi_{\theta_{k}}(a_{k}|s)=\frac{\exp(f_{\theta_{k}}(s,a_{k}))}{\sum_{a^{\prime}\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(s,a^{\prime}))}.$

By tuning the parameters $\alpha_{r}$, we can make any policy belonging to
this policy class respect Assumptions 2 and 3, as we show in the following.
Let $r\in\\{0,\dots,\widetilde{r}\\}$, let $s,\widetilde{s}\in\mathcal{S}$ be
such that $s_{N^{r}_{k}}=\widetilde{s}_{N^{r}_{k}}$, then

$\displaystyle
TV(\pi_{\theta_{k}}(\cdot|s),\pi_{\theta_{k}}(\cdot|\widetilde{s}))=\frac{1}{2}\sum_{a\in\mathcal{A}_{k}}\left|\pi_{\theta_{k}}(a|s)-\pi_{\theta_{k}}(a|\widetilde{s})\right|$
$\displaystyle=\frac{1}{2}\sum_{a\in\mathcal{A}_{k}}\left|\frac{\exp(f_{\theta_{k}}(s,a))}{\sum_{a^{\prime}\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(s,a^{\prime}))}-\frac{\exp(f_{\theta_{k}}(\widetilde{s},a))}{\sum_{a^{\prime}\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(\widetilde{s},a^{\prime}))}\right|$
$\displaystyle=\frac{\sum_{a\in\mathcal{A}_{k}}\left|\sum_{a^{\prime}\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(s,a))\exp(f_{\theta_{k}}(\widetilde{s},a^{\prime}))-\exp(f_{\theta_{k}}(\widetilde{s},a))\exp(f_{\theta_{k}}(s,a^{\prime}))\right|}{2\sum_{a^{\prime}\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(\widetilde{s},a^{\prime}))\sum_{a^{\prime}\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(s,a^{\prime}))}$
$\displaystyle\leq\frac{\sum_{a\in\mathcal{A}_{k}}\sum_{a^{\prime}\in\mathcal{A}_{k}}\left|\exp(f_{\theta_{k}}(s,a))\exp(f_{\theta_{k}}(\widetilde{s},a^{\prime}))-\exp(f_{\theta_{k}}(\widetilde{s},a))\exp(f_{\theta_{k}}(s,a^{\prime}))\right|}{2\sum_{a^{\prime}\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(\widetilde{s},a^{\prime}))\sum_{a^{\prime}\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(s,a^{\prime}))}$
$\displaystyle\leq\frac{\sum_{a\in\mathcal{A}_{k}}\left|\exp(f_{\theta_{k}}(\widetilde{s},a))-\exp(f_{\theta_{k}}(s,a))\right|}{\sum_{a\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(\widetilde{s},a))}$
$\displaystyle\leq\frac{\sum_{a\in\mathcal{A}_{k}}\left|f_{\theta_{k}}(\widetilde{s},a)-f_{\theta_{k}}(s,a)\right|\exp(\sup_{s^{\prime}\in\\{s,\widetilde{s}\\}}f_{\theta_{k}}(s^{\prime},a))}{\sum_{a\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(\widetilde{s},a))}$
$\displaystyle\leq
e^{2C(\widetilde{r}-r)}\frac{\sum_{a\in\mathcal{A}_{k}}\left|f_{\theta_{k}}(\widetilde{s},a)-f_{\theta_{k}}(s,a)\right|\exp(f_{\theta_{k}}(\widetilde{s},a))}{\sum_{a\in\mathcal{A}_{k}}\exp(f_{\theta_{k}}(\widetilde{s},a))}$
$\displaystyle=e^{2C(\widetilde{r}-r)}\mathbb{E}_{\pi_{\theta_{k}}}\left|\sum_{r^{\prime}=r+1}^{\widetilde{r}}\alpha_{r^{\prime}}\left(f_{(\theta_{k})_{r^{\prime}}}(\widetilde{s}_{N^{r^{\prime}}_{k}},a)-f_{(\theta_{k})_{r^{\prime}}}(s_{N^{r^{\prime}}_{k}},a)\right)\right|$
$\displaystyle\leq
e^{2C(\widetilde{r}-r)}\sum_{r^{\prime}=r+1}^{\widetilde{r}}\alpha_{r^{\prime}}\mathbb{E}_{\pi_{\theta_{k}}}\left|f_{(\theta_{k})_{r^{\prime}}}(\widetilde{s}_{N^{r^{\prime}}_{k}},a)-f_{(\theta_{k})_{r^{\prime}}}(s_{N^{r^{\prime}}_{k}},a)\right|$
$\displaystyle\leq
2Ce^{2C(\widetilde{r}-r)}\sum_{r^{\prime}=r+1}^{\widetilde{r}}\alpha_{r^{\prime}}.$

Setting the parameters
$\\{\alpha_{r^{\prime}}\\}_{r^{\prime}\in\\{r+1,\dots,\widetilde{r}\\}}$ small
enough ensures that the policy respects Assumption 2. Similarly, Assumption 3
is satisfied for a value $r$ of the range parameter if $\alpha_{r^{\prime}}=0$
$\forall r^{\prime}\in\\{r+1,\dots,\widetilde{r}\\}$.

##  Appendix B Proof of Proposition 6

###  B.1 Preliminary Lemmas

To prove Proposition 6, we need a series of intermediate results, which we
state and prove for completeness. Results similar to Lemmas 11 and 12 can be
found in Chapter 8 of Georgii [2011], Lemma 13 is an extension of results from
Qu et al. [2020a].

###### Lemma 11

Let $f:\mathcal{Z}\rightarrow[m,M]$, where
$\mathcal{Z}=\prod_{k\in\mathcal{K}}\mathcal{Z}_{k}$ and $m,M\in\mathbb{R}$.
For every $k\in\mathcal{K}$, let $\mu_{k}$ and $\nu_{k}$ be two distributions
on $\mathcal{Z}_{k}$. Let $\mu$ and $\nu$ be the respective product
distributions. Let
$\delta_{k}(f(z))=\sup_{z_{k},z_{-k},z^{\prime}_{k}}\left|f(z_{k},z_{-k})-f(z^{\prime}_{k},z_{-k})\right|$.
Then:

$\left|\mathbb{E}_{z\sim\mu}f(z)-\mathbb{E}_{z\sim\nu}f(z)\right|\leq\sum_{k\in\mathcal{K}}TV(\mu_{k},\nu_{k})\delta_{k}(f).$

Proof: We prove Lemma 11 by induction. Note that

$TV(\mu,\nu)=\frac{1}{2}\max_{|h|\leq
1}\left|\mathbb{E}_{\mu}(h)-\mathbb{E}_{\nu}(h)\right|$

is an equivalent formulation of the total variation distance [Gibbs and Su,
2002]. For $|\mathcal{K}|=1$, we have that

$\displaystyle\left|\mathbb{E}_{\mu_{1}}(f)-\mathbb{E}_{\nu_{1}}(f)\right|$
$\displaystyle=\left|\mathbb{E}_{\mu_{1}}\left(f-\frac{M+m}{2}\right)-\mathbb{E}_{\nu_{1}}\left(f-\frac{M+m}{2}\right)\right|$
$\displaystyle=\frac{M-m}{2}\left|\mathbb{E}_{\mu_{1}}\left(\frac{2f}{M-m}-\frac{M+m}{M-m}\right)-\mathbb{E}_{\nu_{1}}\left(\frac{2f}{M-m}-\frac{M+m}{M-m}\right)\right|$
$\displaystyle\leq\frac{M-m}{2}\max_{|h|\leq
1}\left|\mathbb{E}_{\mu_{1}}(h)-\mathbb{E}_{\nu_{1}}(h)\right|$
$\displaystyle=TV({\mu_{1}},{\nu_{1}})\delta_{1}(f).$

As induction assumption, assume that Lemma 11 holds for $|\mathcal{K}|-1$.
Then:

$\displaystyle\left|\mathbb{E}_{z\sim\mu}f(z)-\mathbb{E}_{z\sim\nu}f(z)\right|$
$\displaystyle=\left|\mathbb{E}_{z_{1}\sim\mu_{1}}\mathbb{E}_{z_{2:n}\sim\mu_{2:n}}f(z)-\mathbb{E}_{z_{1}\sim\nu_{1}}\mathbb{E}_{z_{2:n}\sim\nu_{2:n}}f(z)\right|$
$\displaystyle\leq\left|\mathbb{E}_{z_{1}\sim\mu_{1}}\mathbb{E}_{z_{2:n}\sim\mu_{2:n}}f(z)-\mathbb{E}_{z_{1}\sim\mu_{1}}\mathbb{E}_{z_{2:n}\sim\nu_{2:n}}f(z)\right|$
$\displaystyle\quad+\left|\mathbb{E}_{z_{1}\sim\mu_{1}}\mathbb{E}_{z_{2:n}\sim\nu_{2:n}}f(z)-\mathbb{E}_{z_{1}\sim\nu_{1}}\mathbb{E}_{z_{2:n}\sim\nu_{2:n}}f(z)\right|$
$\displaystyle\leq\mathbb{E}_{z_{1}\sim\mu_{1}}\left|\mathbb{E}_{z_{2:n}\sim\mu_{2:n}}f(z)-\mathbb{E}_{z_{2:n}\sim\nu_{2:n}}f(z)\right|$
$\displaystyle\quad+\left|\mathbb{E}_{z_{1}\sim\mu_{1}}\widetilde{f}(z_{1})-\mathbb{E}_{z_{1}\sim\nu_{1}}\widetilde{f}(z_{1})\right|.$

where $\widetilde{f}(z_{1})=\mathbb{E}_{z_{2:n}\sim\nu_{2:n}}f(z)$. By
induction assumption:

$\left|\mathbb{E}_{z_{2:n}\sim\mu_{2:n}}f(z)-\mathbb{E}_{z_{2:n}\sim\nu_{2:n}}f(z)\right|\leq\sum_{k\neq
1\in\mathcal{K}}TV(\mu_{k},\nu_{k})\delta_{k}(f(z_{1},\cdot))\leq\sum_{k\neq
1\in\mathcal{K}}TV(\mu_{k},\nu_{k})\delta_{k}(f).$

Since

$\displaystyle\delta_{1}(\widetilde{f})$
$\displaystyle=\sup_{z_{1},z_{1}^{\prime}}\left|\mathbb{E}_{z_{2:n}\sim\nu_{2:n}}f(z_{1},z_{2:n})-\mathbb{E}_{z_{2:n}\sim\nu_{2:n}}f(z_{1}^{\prime},z_{2:n})\right|$
$\displaystyle\leq\sup_{z_{1},z_{1}^{\prime}}\mathbb{E}_{z_{2:n}\sim\nu_{2:n}}\left|f(z_{1},z_{2:n})-f(z_{1}^{\prime},z_{2:n})\right|$
$\displaystyle\leq\sup_{z_{1},z_{1}^{\prime}}\sup_{z_{2:n}}\left|f(z_{1},z_{2:n})-f(z_{1}^{\prime},z_{2:n})\right|=\delta_{1}(f),$

we have

$\displaystyle\left|\mathbb{E}_{z\sim\mu}f(z)-\mathbb{E}_{z\sim\nu}f(z)\right|$
$\displaystyle\leq\mathbb{E}_{z_{1}\sim\mu_{1}}\sum_{k\neq
1\in\mathcal{K}}TV(\mu_{k},\nu_{k})\delta_{k}(f)+TV({\mu_{1}},{\nu_{1}})\delta_{1}(f)$
$\displaystyle\leq\sum_{k\in\mathcal{K}}TV(\mu_{k},\nu_{k})\delta_{k}(f),$

which concludes the induction.

###### Lemma 12

Consider a Markov Chain with state $z\in\mathcal{Z}$, where
$\mathcal{Z}=\prod_{k\in\mathcal{K}}\mathcal{Z}_{k}$ and $\mathcal{K}$ is
defined as in Section 2. Suppose its transition probability factorizes as

$P(z(t+1)|z(t))=\prod_{k\in\mathcal{K}}P_{k}(z_{k}(t+1)|z(t)).$

Let $C\in\mathbb{R}^{K\times K}$ be a matrix whose elements respect the
condition

$C_{ij}\geq\sup_{z_{j},z_{-j},z^{\prime}_{j}}TV(P_{i}(\cdot|z_{j},z_{-j}),P_{i}(\cdot|z^{\prime}_{j},z_{-j})).$

If $\sum_{j\in\mathcal{K}}e^{\beta d(j,k)}C_{kj}\leq\rho$, then,
$\forall\mathcal{J}\subseteq\mathcal{K}$,

$\sup_{z_{j},z_{-j},z^{\prime}_{j}}TV(P_{i}(\cdot|z_{J},z_{-J}),P_{i}(\cdot|z^{\prime}_{J},z_{-J}))\leq\sum_{j\in\mathcal{J}}C_{ij}$

and

$\sup_{z_{J},z_{-J},z^{\prime}_{J}}TV(P_{i}(\cdot|z_{J},z_{-J}),P_{i}(\cdot|z^{\prime}_{J},z_{-J}))\leq\rho
e^{-\beta d(\mathcal{J},i)},$

where $d(\mathcal{J},i)=\min_{j\in\mathcal{J}}d(j,i)$.

Proof: We prove the first claim of Lemma 12 by induction. The first claim
clearly holds if $|\mathcal{J}|=1$. As induction assumption, assume that the
first claim holds for a generic $\mathcal{J}$. Then, it holds for
$\mathcal{J}^{\prime}=\mathcal{J}+\\{k\\}$:

$\displaystyle\sup_{z_{j},z_{-j},z^{\prime}_{j}}TV(P_{i}(\cdot|z_{J^{\prime}},z_{-J^{\prime}}),P_{i}(\cdot|z^{\prime}_{J^{\prime}},z_{-J^{\prime}}))=\sup_{\begin{subarray}{c}A\subseteq\mathcal{Z}_{i}\\\
z_{j},z_{-j},z^{\prime}_{j}\end{subarray}}\left|P_{i}(A|z_{J^{\prime}},z_{-J^{\prime}})-P_{i}(A|z^{\prime}_{J^{\prime}},z_{-J^{\prime}})\right|$
$\displaystyle\leq\sup_{\begin{subarray}{c}A\subseteq\mathcal{Z}_{i}\\\
z_{j},z_{-j},z^{\prime}_{j}\end{subarray}}\left|P_{i}(A|z_{J^{\prime}},z_{-J^{\prime}})-P_{i}(A|z^{\prime}_{J},z_{-J})\right|+\sup_{\begin{subarray}{c}A\subseteq\mathcal{Z}_{i}\\\
z_{j},z_{-j},z^{\prime}_{j}\end{subarray}}\left|P_{i}(A|z^{\prime}_{J},z_{-J})-P_{i}(A|z^{\prime}_{J^{\prime}},z_{-J^{\prime}})\right|$
$\displaystyle\leq\sum_{j\in\mathcal{J}}C_{ij}+C_{ik}=\sum_{j\in\mathcal{J}^{\prime}}C_{ij}.$

The second claim follows immediately, since

$e^{\beta
d(\mathcal{J},i)}\sum_{j\in\mathcal{J}}C_{ij}\leq\sum_{j\in\mathcal{J}}e^{\beta
d(j,i)}C_{ij}\leq\sum_{j\in\mathcal{K}}e^{\beta d(j,i)}C_{ij}\leq\rho,$

and

$\sum_{j\in\mathcal{J}}C_{ij}\leq\rho e^{-\beta d(\mathcal{J},i)}.$

###### Lemma 13

Consider the setting of Lemma 12. For a generic value of $r$, denote by
$d_{t}$ and $\widetilde{d}_{t}$ the distribution of $z(t)$ with starting
state, respectively, $z=(z_{N_{k}^{r}},z_{N_{-k}^{r}})$ and
$\widetilde{z}=(z_{N_{k}^{r}},\widetilde{z}_{N_{-k}^{r}})$. Then, if
$\sum_{j\in\mathcal{K}}e^{\beta d(j,k)}C_{kj}\leq\rho$, we have that
$TV(d_{t,k},\widetilde{d}_{t,k})\leq\rho^{t}e^{-\beta r}$, $\forall
k\in\mathcal{K}$.

Proof: We prove Lemma 13 by induction. The case where $t=1$ follows from Lemma
12. As induction assumption, assume that Lemma 13 holds for $t$. Then,

$\displaystyle\left|\mathbb{E}_{s\sim
d_{t+1,k}(s)}\mathbf{1}_{A}(s)-\mathbb{E}_{s\sim\widetilde{d}_{t+1,k}}\mathbf{1}_{A}(s)\right|$
$\displaystyle=\left|\mathbb{E}_{z\sim d_{t}}E_{s\sim
P_{k}(\cdot|z)}\mathbf{1}_{A}(s)-\mathbb{E}_{z\sim\widetilde{d}_{t}}\mathbb{E}_{s\sim
P_{k}(\cdot|z)}\mathbf{1}_{A}(s)\right|$
$\displaystyle\leq\sum_{j\in\mathcal{K}}TV(d_{t,j},\widetilde{d}_{t,j})\delta_{j}(E_{s\sim
P_{k}(\cdot|\cdot)}\mathbf{1}_{A}(s))$
$\displaystyle\leq\sum_{j\in\mathcal{K}}TV(d_{t,j},\widetilde{d}_{t,j})C_{kj}$
$\displaystyle\leq\sum_{j\in\mathcal{K}}\rho^{t}e^{-\beta(r-d(j,k))}C_{kj}$
$\displaystyle=\rho^{t}e^{-\beta r}\sum_{j\in\mathcal{K}}e^{\beta
d(j,k)}C_{kj}\leq\rho^{t+1}e^{-\beta r},$

where we used Lemma 11 in the first inequality.

###### Lemma 14

Consider the setting of Lemma 12. Let
$P^{t}(z^{\prime}|z)=P(z(t)=z^{\prime}|z(0)=z)$ and

$\delta_{i}P^{t}_{k}=\sup_{z_{i},z_{-i},z^{\prime}_{i}}TV(P_{k}^{t}(\cdot|z_{i},z_{-i}),P_{k}^{t}(\cdot|z^{\prime}_{i},z_{-i})).$

If $\sum_{j\in\mathcal{K}}e^{\beta d(j,k)}C_{kj}\leq\rho$, then $\forall
k\in\mathcal{K}$

$\sum_{i\in\mathcal{K}}e^{\beta d(k,i)}\delta_{i}P^{t}_{k}\leq\rho^{t}.$

Proof: We prove Lemma 14 by induction. The claim holds for $t=1$:

$\sum_{i\in\mathcal{K}}e^{\beta
d(k,i)}\delta_{i}P^{t}_{k}=\sum_{i\in\mathcal{K}}e^{\beta
d(k,i)}C_{k,i}\leq\rho$

As induction assumption, we assume that the claim holds for $t$. Then, using
Lemma 11,

$\displaystyle\delta_{i}P^{t+1}_{k}$
$\displaystyle=\sup_{\begin{subarray}{c}A\subseteq\mathcal{S}_{k}\\\
z_{i},z_{-i},z^{\prime}_{i}\end{subarray}}\left|\mathbb{E}_{s\sim
P_{k}^{t+1}(\cdot|z_{i},z_{-i})}\mathbf{1}_{A}(s)-\mathbb{E}_{s\sim
P_{k}^{t+1}(\cdot|z^{\prime}_{i},z_{-i})}\mathbf{1}_{A}(s)\right|$
$\displaystyle=\sup_{\begin{subarray}{c}A\subseteq\mathcal{S}_{k}\\\
z_{i},z_{-i},z^{\prime}_{i}\end{subarray}}\left|\mathbb{E}_{x\sim
P^{t}(\cdot|z_{i},z_{-i})}E_{s\sim
P_{k}(\cdot|x)}\mathbf{1}_{A}(s)-\mathbb{E}_{x\sim
P^{t}(\cdot|z^{\prime}_{i},z_{-i})}\mathbb{E}_{s\sim
P_{k}(\cdot|x)}\mathbf{1}_{A}(s)\right|$
$\displaystyle\leq\sup_{z_{i},z_{-i},z^{\prime}_{i}}\sum_{j\in\mathcal{K}}TV(P^{t}_{j}(\cdot|z_{i},z_{-i}),P^{t}_{j}(\cdot|z^{\prime}_{i},z_{-i}))\delta_{j}(E_{s\sim
P_{k}(\cdot|\cdot)}\mathbf{1}_{A}(s))$
$\displaystyle\leq\sum_{j\in\mathcal{K}}\delta_{i}P^{t}_{j}C_{kj}$

and, using the inverse triangle inequality,

$\displaystyle\sum_{i\in\mathcal{K}}e^{\beta d(k,i)}\delta_{i}P^{t+1}_{k}$
$\displaystyle\leq\sum_{i\in\mathcal{K}}e^{\beta
d(k,i)}\sum_{j\in\mathcal{K}}\delta_{i}P^{t}_{j}C_{kj}$
$\displaystyle\leq\sum_{j\in\mathcal{K}}e^{\beta
d(k,j)}C_{kj}\sum_{i\in\mathcal{K}}e^{\beta(d(k,i)-d(k,j))}\delta_{i}P^{t}_{j}$
$\displaystyle\leq\sum_{j\in\mathcal{K}}e^{\beta
d(k,j)}C_{kj}\sum_{i\in\mathcal{K}}e^{\beta
d(j,i)}\delta_{i}P^{t}_{j}\leq\rho^{t+1},$

which concludes the induction.

###  B.2 Main Result

Proof:[of Proposition 6] The following holds for every $k\in\mathcal{K}$. Let
$s,\widetilde{s}\in\mathcal{S}$, $a,\widetilde{a}\in\mathcal{A}$ be such that
$s_{N^{r}_{k}}=\widetilde{s}_{N^{r}_{k}}$ and
$a_{N^{r}_{k}}=\widetilde{a}_{N^{r}_{k}}$. Notice that

$\displaystyle\left|Q_{k}^{\pi}(s,a)-Q_{k}^{\pi}(\widetilde{s},\widetilde{a})\right|$
$\displaystyle\leq\sum_{t=0}^{\infty}\gamma^{t}\left|\mathbb{E}\left[r_{k}(s_{k}(t),a_{k}(t))\big{|}\pi,s(0)=s,a(0)=a\right]-\mathbb{E}\left[r_{k}(s_{k}(t),a_{k}(t))\big{|}\pi,s(0)=\widetilde{s},a(0)=\widetilde{a}\right]\right|$
$\displaystyle\leq\sum_{t=1}^{\infty}\gamma^{t}\left|\mathbb{E}\left[r_{k}(s_{k}(t),a_{k}(t))\big{|}\pi,s(0)=s,a(0)=a\right]-\mathbb{E}\left[r_{k}(s_{k}(t),a_{k}(t))\big{|}\pi,s(0)=\widetilde{s},a(0)=\widetilde{a}\right]\right|$
$\displaystyle\leq\sum_{t=1}^{\infty}\gamma^{t}TV(d_{t,k},\widetilde{d}_{t,k}),$

where $d_{t,k}(s_{k},a_{k})$ and $\widetilde{d}_{t,k}(s_{k},a_{k})$ are the
distributions of $s_{k},a_{k}$ at time $t$ with starting point $(s,a)$ and
$(\widetilde{s},\widetilde{a})$, respectively. We use Lemma 13 to bound
$TV(d_{t,k},\widetilde{d}_{t,k})$. The structure of our MDP implies that:

$P(s(t+1),a(t+1)|s(t),a(t))=\prod_{k\in\mathcal{K}}\pi^{k}(a_{k}(t+1)|s(t+1))P_{k}(s_{k}(t+1)|s(t),a(t)).$

Let $C$ be defined as in Assumption 1 and note that

$\displaystyle C_{kj}$
$\displaystyle=\sup_{s_{j},s_{-j},a_{j},a_{-j},s^{\prime}_{j},a^{\prime}_{j}}TV(P_{k}(\cdot|s_{j},s_{-j},a_{j},a_{-j}),P_{k}(\cdot|s^{\prime}_{j},s_{-j},a^{\prime}_{j},a_{-j}))$
$\displaystyle\geq\sup_{s_{j},s_{-j},a_{j},a_{-j},s^{\prime}_{j},a^{\prime}_{j}}TV(P_{k}(\cdot,\cdot|s_{j},s_{-j},a_{j},a_{-j}),P_{k}(\cdot,\cdot|s^{\prime}_{j},s_{-j},a^{\prime}_{j},a_{-j})).$

Then, if Assumption 1 holds, the requirements of Lemma 13 are satisfied.
Therefore, $TV(d_{t,k},\widetilde{d}_{t,k})\leq\rho^{t}e^{-\beta r}$ and

$\left|Q_{k}^{\pi}(s,a)-Q_{k}^{\pi}(\widetilde{s},\widetilde{a})\right|\leq\sum_{t=1}^{\infty}\gamma^{t}TV(d_{t,k},\widetilde{d}_{t,k})\leq
e^{-\beta r}\sum_{t=1}^{\infty}\gamma^{t}\rho^{t}=\frac{\gamma\rho e^{-\beta
r}}{1-\gamma\rho}.$

We use this result to prove the exponential decay property for the value
function. Let

$\delta_{j}Q_{k}^{\pi}(s,a)=\sup_{s_{j},s_{-j},a_{j},a_{-j},s^{\prime}_{j},a^{\prime}_{j}}|Q_{k}^{\pi}(s_{j},s_{-j},a_{j},a_{-j})-Q_{k}^{\pi}(s^{\prime}_{j},s_{-j},a^{\prime}_{j},a_{-j})|.$

Using Lemma 11 and Assumption 2, we have that

$\displaystyle\left|V_{k}^{\pi}(s)-V_{k}^{\pi}(\widetilde{s})\right|=\left|\mathbb{E}_{a\sim\pi(\cdot|s)}Q_{k}^{\pi}(s,a)-\mathbb{E}_{a\sim\pi(\cdot|\widetilde{s})}Q_{k}^{\pi}(\widetilde{s},a)\right|$
$\displaystyle\leq\left|\mathbb{E}_{a\sim\pi(\cdot|s)}Q_{k}^{\pi}(s,a)-\mathbb{E}_{a\sim\pi(\cdot|\widetilde{s})}Q_{k}^{\pi}(s,a)\right|+\left|\mathbb{E}_{a\sim\pi(\cdot|\widetilde{s})}Q_{k}^{\pi}(s,a)-\mathbb{E}_{a\sim\pi(\cdot|\widetilde{s})}Q_{k}^{\pi}(\widetilde{s},a)\right|$
$\displaystyle\leq\sum_{i\in\mathcal{K}}TV(\pi_{i}(\cdot|s),\pi_{i}(\cdot|\widetilde{s}))\delta_{i}Q_{k}^{\pi}(s,a)+\frac{\gamma\rho
e^{-\beta r}}{1-\gamma\rho}$ $\displaystyle\leq\xi e^{-\beta
r}\sum_{i\in\mathcal{K}}e^{-\beta
d(i,k)}\delta_{i}Q_{k}^{\pi}(s,a)+\frac{\gamma\rho e^{-\beta
r}}{1-\gamma\rho}.$

We have already shown that the MDP satisfies the condition of Lemma 14. Using
it we obtain

$\sum_{i\in\mathcal{K}}e^{\beta
d(k,i)}\delta_{i}(Q^{\pi}_{k}(s,\cdot))\leq\sum_{t=1}^{\infty}\gamma^{t}\sum_{i\in\mathcal{K}}e^{\beta
d(k,i)}\delta_{i}P^{t}_{k}\leq\sum_{t=1}^{\infty}\gamma^{t}\rho^{t}=\frac{\gamma\rho}{1-\gamma\rho},$

where

$\delta_{i}P^{t}_{k}=\sup_{s_{j},s_{-j},a_{j},a_{-j},s^{\prime}_{j},a^{\prime}_{j}}TV(P_{k}^{t}(\cdot,\cdot|s_{j},s_{-j},a_{j},a_{-j}),P_{k}^{t}(\cdot,\cdot|s^{\prime}_{j},s_{-j},a^{\prime}_{j},a_{-j})).$

Then, we have that

$\left|V_{k}^{\pi}(s)-V_{k}^{\pi}(\widetilde{s})\right|\leq\frac{\gamma\rho(1+\xi)e^{-\beta
r}}{1-\gamma\rho}.$

##  Appendix C Decay for the Optimal Policy

###### Lemma 15

Assume that the exponential decay property holds for the Q-function with
parameters $(c,\psi)$. Then the exponential decay property holds also for the
value function associated with the optimal policy, with parameters
$(3c,\psi)$.

Proof: The following holds for every $k\in\mathcal{K}$. Let
$s,\widetilde{s}\in\mathcal{S}$ be such that
$s_{N^{r}_{k}}=\widetilde{s}_{N^{r}_{k}}$ and let
$a_{N^{r}_{-k}}\in\mathcal{A}_{N^{r}_{-k}}$.

$\displaystyle\left|V_{k}^{\star}(s)-V_{k}^{\star}(\widetilde{s})\right|=\left|\mathbb{E}_{a\sim\pi^{\star}(\cdot|s)}Q_{k}^{\star}(s,a)-\mathbb{E}_{a\sim\pi^{\star}(\cdot|\widetilde{s})}Q_{k}^{\star}(\widetilde{s},a)\right|=\left|\max_{a}Q_{k}^{\star}(s,a)-\max_{a}Q_{k}^{\star}(\widetilde{s},a)\right|$
$\displaystyle=\left|\max_{a}Q_{k}^{\star}(s,a)-\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(s,a_{N^{r}_{k}},a_{N^{r}_{-k}})+\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(s,a_{N^{r}_{k}},a_{N^{r}_{-k}})\right.$
$\displaystyle\quad-\left.\max_{a}Q_{k}^{\star}(\widetilde{s},a)-\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(\widetilde{s},a_{N^{r}_{k}},a_{N^{r}_{-k}})+\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(\widetilde{s},a_{N^{r}_{k}},a_{N^{r}_{-k}})\right|$
$\displaystyle=\left|\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(s,a_{N^{r}_{k}},a_{N^{r}_{-k}})-\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(\widetilde{s},a_{N^{r}_{k}},a_{N^{r}_{-k}})\right|$
$\displaystyle\quad+\left|\max_{a}Q_{k}^{\star}(\widetilde{s},a)-\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(\widetilde{s},a_{N^{r}_{k}},a_{N^{r}_{-k}})\right|+\left|\max_{a}Q_{k}^{\star}(s,a)-\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(s,a_{N^{r}_{k}},a_{N^{r}_{-k}})\right|$
$\displaystyle\leq\left|\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(s,a_{N^{r}_{k}},a_{N^{r}_{-k}})-\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(\widetilde{s},a_{N^{r}_{k}},a_{N^{r}_{-k}})\right|+2c\psi^{r+1}.$

Let
$a^{\prime}_{N^{r}_{k}}\in\mathop{\mathrm{argmax}}_{a_{N^{r}_{k}}}Q_{k}^{\star}(s,a_{N^{r}_{k}},a_{N^{r}_{-k}})$,
then

$\displaystyle
Q_{k}^{\star}(s,a^{\prime}_{N^{r}_{k}},a_{N^{r}_{-k}})-\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(\widetilde{s},a_{N^{r}_{k}},a_{N^{r}_{-k}})$
$\displaystyle\leq
Q_{k}^{\star}(\widetilde{s},a^{\prime}_{N^{r}_{k}},a_{N^{r}_{-k}})-\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(\widetilde{s},a_{N^{r}_{k}},a_{N^{r}_{-k}})+c\psi^{r+1}$
$\displaystyle\leq\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(\widetilde{s},a_{N^{r}_{k}},a_{N^{r}_{-k}})-\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(\widetilde{s},a_{N^{r}_{k}},a_{N^{r}_{-k}})+c\psi^{r+1}=c\psi^{r+1}.$

The same holds for
$\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(\widetilde{s},a_{N^{r}_{k}},a_{N^{r}_{-k}})-\max_{a_{N^{r}_{k}}}Q_{k}^{\star}(s,a_{N^{r}_{k}},a_{N^{r}_{-k}})$.
The lemma follows immediately.

We make an assumption on the minimum influence that the action of an agent has
on its expected future rewards. Assumption 16 and Proposition 17 hold for any
$k\in\mathcal{K}$.

###### Assumption 16

Let
$\mathcal{A}^{\star}=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}Q_{k}^{\star}(s,a)$,
$\forall s\in\mathcal{S}$. Assume that, if $\widetilde{a}$ is such that
$\widetilde{a}_{k}\notin\mathcal{A}^{\star}_{k}$, then

$\left|Q_{k}^{\star}(s,a)-Q_{k}^{\star}(s,\widetilde{a})\right|\geq R$

###### Proposition 17

Assume that the exponential decay property holds for the Q-function with
parameters $(c,\psi)$ and that Assumption 16 holds. Let
$s,\widetilde{s}\in\mathcal{S}$ be such that
$s_{N^{r}_{k}}=\widetilde{s}_{N^{r}_{k}}$. Let
$\mathcal{A}^{\star}=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}Q_{k}^{\star}(s,a)$
and
$\widetilde{a}\in\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}Q_{k}^{\star}(\widetilde{s},a)$.
If $r>\log_{\psi}R/4c$, then $\widetilde{a}_{k}\in\mathcal{A}^{\star}_{k}$.

Proof: We prove this by contradiction. Lemma 15 shows that, $\forall r>0$, if
$s,\widetilde{s}\in\mathcal{S}$ are such that
$s_{N^{r}_{k}}=\widetilde{s}_{N^{r}_{k}}$,

$\left|V_{k}^{\star}(s)-V_{k}^{\star}(\widetilde{s})\right|=\left|\max_{a}Q_{k}^{\star}(s,a)-\max_{a}Q_{k}^{\star}(\widetilde{s},a)\right|\leq
3c\psi^{r+1}.$

Let $a\in\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}Q_{k}^{\star}(s,a)$ and
$\widetilde{a}\in\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}Q_{k}^{\star}(\widetilde{s},a)$.
Let
$\mathcal{A}^{\star}=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}Q_{k}^{\star}(s,a)$
and assume that $\widetilde{a}_{k}\notin\mathcal{A}^{\star}_{k}$. Then

$\displaystyle\left|Q_{k}^{\star}(s,a)-Q_{k}^{\star}(\widetilde{s},\widetilde{a})\right|$
$\displaystyle=\left|Q_{k}^{\star}(s,a)-Q_{k}^{\star}(s,\widetilde{a})+Q_{k}^{\star}(s,\widetilde{a})-Q_{k}^{\star}(\widetilde{s},\widetilde{a})\right|$
$\displaystyle\geq\left|\left|Q_{k}^{\star}(s,a)-Q_{k}^{\star}(s,\widetilde{a})\right|-\left|Q_{k}^{\star}(s,\widetilde{a})-Q_{k}^{\star}(\widetilde{s},\widetilde{a})\right|\right|$
$\displaystyle\geq\left|Q_{k}^{\star}(s,a)-Q_{k}^{\star}(s,\widetilde{a})\right|-c\psi^{r+1}\geq
R-c\psi^{r+1}$

where we used Assumption 16 in the last passage. Then, due to Lemma 15, if
$r>\log_{\psi}R/4c$ we have a contradiction.

Proposition 17 shows that the optimal policy of an agent is not influenced by
distant agents. Assumption 2 ensures that the policy class we consider
respects this condition.

##  Appendix D Independent Agents

By completely independent agents we mean agents whose transition dynamics are
independent and whose policy is defined, for
$s\in\mathcal{S},a\in\mathcal{A}$, as:

$\displaystyle\pi_{\theta}(a|s)$
$\displaystyle=\prod_{k\in\mathcal{K}}\pi_{\theta_{k}}(a_{k}|s_{k})=\prod_{k}\frac{e^{f_{\theta_{k}}(s_{k},a_{k})}}{\sum_{a^{\prime}\in\mathcal{A}_{k}}e^{f_{\theta_{k}}(s_{k},a^{\prime})}}.$

In accordance to previous assumptions, we also assume that
$\pi_{\theta_{k}}(a_{k}|s_{k})$ is $\delta$-smooth.

Proof:[of Remark 8] Firstly we show that the two applications of the algorithm
coincide. Let

$L(w)=\mathbb{E}_{s\sim
d_{\nu}^{\pi},a\sim\pi_{\theta}(\cdot|s)}\left[\left(A^{\pi_{\theta}}(s,a)-w\cdot\nabla_{\theta}\log\pi_{\theta}(a|s)\right)^{2}\right].$

In Agarwal et al. [2020], the NPG update is

$w_{\star}\in\mathop{\mathrm{argmin}}_{w}L(w).$

We now show that the gradient of the loss function is the same as the one in
the single agent setting. This is enough to show that the two algorithms
coincide, since every other operation coincides. The only exception is the
projection step, problem that can be side-stepped by projecting each single
component of the gradient vector instead of the whole vector. For each agent
$k$ we have that

$\displaystyle\nabla_{\theta_{k}}L(w)$ $\displaystyle=\mathbb{E}_{s\sim
d_{\nu}^{\pi},a\sim\pi_{\theta}(\cdot|s)}\left[\left(A^{\pi_{\theta}}(s,a)-w\cdot\nabla_{\theta}\log\pi_{\theta}(a|s)\right)\nabla_{\theta_{k}}\log\pi_{\theta}(a|s)\right]$
$\displaystyle=\sum_{j\in\mathcal{K}}\mathbb{E}_{s\sim
d_{\nu}^{\pi},a\sim\pi_{\theta}(\cdot|s)}\left[\left(\frac{1}{K}A_{j}^{\pi_{\theta}}(s_{j},a_{j})-w_{j}\cdot\nabla_{\theta_{j}}\log\pi_{\theta}(a_{j}|s_{j})\right)\nabla_{\theta_{k}}\log\pi_{\theta}(a|s)\right]$
$\displaystyle=E_{s_{k}\sim
d_{\nu,k}^{\pi},a_{k}\sim\pi^{k}_{\theta_{k}}(\cdot|s_{k})}\left[\left(\frac{1}{K}A_{k}^{\pi_{\theta}}(s_{k},a_{k})-w_{k}\cdot\nabla_{\theta_{k}}\log\pi_{\theta}(a_{k}|s_{k})\right)\nabla_{\theta_{k}}\log\pi_{\theta}(a_{k}|s_{k})\right],$

which corresponds to the gradient for the single agent setting.

With regards to guarantees, since the problem is decoupled, for any agent $k$
we have the same result as in Agarwal et al. 2020:

$\mathbb{E}\left[\min_{t<T}\\{V_{k}^{\pi^{\star}}(\rho)-V_{k}^{(t)}(\rho)\\}\right]\leq\frac{W}{1-\gamma}\sqrt{\frac{2\delta\log|\mathcal{A}_{k}|}{T}}+\sqrt{\frac{\kappa\varepsilon_{\text{stat},k}}{(1-\gamma)^{3}}}+\frac{\sqrt{\varepsilon_{\text{bias},k}}}{1-\gamma},$

where we assumed that

$\mathbb{E}\left[L_{k}(w^{(t)}_{k},\theta^{(t)}_{k},d^{(t)}_{k})-L(w^{(t)}_{\star,k},\theta^{(t)}_{k},d^{(t)}_{k})|\theta^{(t)}_{k}\right]\leq\varepsilon_{\text{stat},k},$
$\mathbb{E}\left[L(w^{(t)}_{\star,k},\theta^{(t)}_{k},d^{\star}_{k})\right]\leq\varepsilon_{\text{bias},k},$

where $d^{(t)}_{k}=d_{\nu}^{\pi_{k}^{(t)}}\pi^{{(t)}}_{k}$,
$d^{\star}_{k}=d_{\nu}^{\pi_{k}^{\star}}\pi^{\star}_{k}$ and

$L_{k}(w,\theta_{k},d)=\mathbb{E}_{s_{k},a_{k}\sim
d}\left[\left(A_{k}^{\pi_{\theta_{k}}}(s_{k},a_{k})-w\cdot\nabla_{\theta_{k}}\log\pi_{\theta_{k}}(a_{k}|s_{k})\right)^{2}\right],$
$w^{(t)}_{\star,k}\in\mathop{\mathrm{argmin}}_{\lVert w\rVert_{2}\leq
W}L_{k}(w,\theta^{(t)}_{k},d^{(t)}_{k}).$

The same result holds for the whole network:

$\displaystyle\mathbb{E}\left[\min_{t<T}\\{V^{\pi^{\star}}(\rho)-V^{(t)}(\rho)\\}\right]$
$\displaystyle=\mathbb{E}\left[\min_{t<T}\left\\{\frac{1}{K}\sum_{k\in\mathcal{K}}\left(V_{k}^{\pi^{\star}}(\rho)-V_{k}^{(t)}(\rho)\right)\right\\}\right]$
$\displaystyle\leq\mathbb{E}\left[\min_{t<T}\max_{k\in\mathcal{K}}\left\\{V_{k}^{\pi^{\star}}(\rho)-V_{k}^{(t)}(\rho)\right\\}\right].$

##  Appendix E Proof of Theorem 9

We follow the proof in Agarwal et al. [2020] modifying it where necessary. We
start by proving a modified NPG Regret Lemma.

###### Lemma 18

Consider the setting of Theorem 9, then we have that:

$\mathbb{E}\left[\min_{t<T}\\{V^{\pi^{\star}}(\rho)-V^{(t)}(\rho)\\}\right]\leq\frac{W}{1-\gamma}\sqrt{\frac{2\delta\max_{k\in\mathcal{K}}\log|\mathcal{A}_{k}|}{T}}+\mathbb{E}\left[\frac{1}{T(1-\gamma)}\sum_{t=0}^{T-1}\text{err}_{t}\right],$

where

$\text{err}_{t}=\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[A^{(t)}(s,a)-\frac{1}{K}\nabla_{\theta}\log\pi^{(t)}(a|s)\cdot
w^{(t)}\right].$

Proof: We assume $\log\pi_{\theta}(a|s)$ is a $\delta$-smooth function of
$\theta$. By smoothness we have:

$\displaystyle\log\frac{\pi^{(t+1)}(a|s)}{\pi^{(t)}(a|s)}$
$\displaystyle\geq\nabla_{\theta}\log\pi^{(t)}(a|s)\cdot(\theta^{(t+1)}-\theta^{(t)})-\frac{\delta}{2}\left\lVert\theta^{(t+1)}-\theta^{(t)}\right\rVert^{2}_{2}$
$\displaystyle=\eta\nabla_{\theta}\log\pi^{(t)}(a|s)\cdot
w^{(t)}-\eta^{2}\frac{\delta}{2}\left\lVert w^{(t)}\right\rVert^{2}_{2}.$

Then

$\displaystyle\frac{1}{K}\mathbb{E}_{s\sim
d_{\rho}^{\pi^{\star}}}(\text{KL}(\pi^{\star}_{s}||\pi^{(t)}_{s})-\text{KL}(\pi^{\star}_{s}||\pi^{(t+1)}_{s}))=\frac{1}{K}\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[\log\frac{\pi^{(t+1)}(a|s)}{\pi^{(t)}(a|s)}\right]$
$\displaystyle\geq\frac{\eta}{K}\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[\nabla_{\theta}\log\pi^{(t)}(a|s)\cdot
w^{(t)}\right]-\eta^{2}\frac{\delta}{2K}\left\lVert
w^{(t)}\right\rVert^{2}_{2}$ $\displaystyle=\eta\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[A^{(t)}(s,a)\right]+\eta\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[\frac{1}{K}\nabla_{\theta}\log\pi^{(t)}(a|s)\cdot
w^{(t)}-A^{(t)}(s,a)\right]$
$\displaystyle\quad-\eta^{2}\frac{\delta}{2K}\left\lVert
w^{(t)}\right\rVert^{2}_{2}$
$\displaystyle=(1-\gamma)\eta\left(V^{\pi^{\star}}(\rho)-V^{(t)}(\rho)\right)-\eta^{2}\frac{\delta}{2K}\left\lVert
w^{(t)}\right\rVert^{2}_{2}-\eta\text{ err}_{t},$

where

$\text{err}_{t}=\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[A^{(t)}(s,a)-\frac{1}{K}\nabla_{\theta}\log\pi^{(t)}(a|s)\cdot
w^{(t)}\right].$

Rearranging

$\displaystyle
V^{\pi^{\star}}(\rho)-V^{(t)}(\rho)\leq\frac{1}{1-\gamma}\left(\frac{1}{\eta
K}\mathbb{E}_{s\sim
d_{\rho}^{\pi^{\star}}}(\text{KL}(\pi^{\star}_{s}||\pi^{(t)}_{s})-\text{KL}(\pi^{\star}_{s}||\pi^{(t+1)}_{s}))+\frac{\eta\delta}{2}W^{2}+\text{err}_{t}\right)$

and summing over t

$\displaystyle
V^{\pi^{\star}}(\rho)-\frac{1}{T}\sum_{t=0}^{T-1}V^{(t)}(\rho)\leq$
$\displaystyle\frac{1}{\eta KT(1-\gamma)}\sum_{t=0}^{T-1}\mathbb{E}_{s\sim
d_{\rho}^{\pi^{\star}}}(\text{KL}(\pi^{\star}_{s}||\pi^{(t)}_{s})-\text{KL}(\pi^{\star}_{s}||\pi^{(t+1)}_{s}))$
$\displaystyle+\frac{1}{T(1-\gamma)}\sum_{t=0}^{T-1}\left(\frac{\eta\delta}{2}W^{2}+\text{err}_{t}\right)$
$\displaystyle\leq$ $\displaystyle\frac{\mathbb{E}_{s\sim
d_{\rho}^{\pi^{\star}}}\text{KL}(\pi^{\star}_{s}||\pi^{(0)}_{s})}{\eta
KT(1-\gamma)}+\frac{\eta\delta
W^{2}}{2(1-\gamma)}+\frac{1}{T(1-\gamma)}\sum_{t=0}^{T-1}\text{err}_{t}$
$\displaystyle\leq$ $\displaystyle\frac{\log|\mathcal{A}|}{\eta
KT(1-\gamma)}+\frac{\eta\delta
W^{2}}{2(1-\gamma)}+\frac{1}{T(1-\gamma)}\sum_{t=0}^{T-1}\text{err}_{t}.$

Optimizing for $\eta$, we obtain the lemma.

We can now prove Theorem 9

Proof:[of Theorem 9] After using the NPG Regret Lemma we want to bound the
$\text{err}_{t}$ term. We do so by dividing it in 3 parts. Let
$(w^{(t)})_{t=1,\dots,T}$ be an update sequence such that, for each $t,k$,
$(w_{k}^{(t)})_{N^{r}_{-k}}=0$, then

$\displaystyle\text{err}_{t}$ $\displaystyle=\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[A^{(t)}(s,a)-\frac{1}{K}\nabla_{\theta}\log\pi^{(t)}(a|s)\cdot
w^{(t)}\right]$
$\displaystyle=\frac{1}{K}\sum_{k\in\mathcal{K}}\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[A^{(t)}_{k}(s,a)-\nabla_{\theta_{k}}\log\pi^{(t)}(a|s)\cdot
w^{(t)}_{k}\right]$
$\displaystyle=\frac{1}{K}\sum_{k\in\mathcal{K}}\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[A^{(t)}_{k}(s,a)-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot(w_{k}^{(t)})_{N^{r}_{k}}\right]$
$\displaystyle=\frac{1}{K}\sum_{k\in\mathcal{K}}\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[\widetilde{A}^{(t)}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot(w_{k,\star}^{(t)})_{N^{r}_{k}}\right]$
$\displaystyle\quad+\frac{1}{K}\sum_{k\in\mathcal{K}}\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[A^{(t)}_{k}(s,a)-\widetilde{A}^{(t)}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})\right]$
$\displaystyle\quad+\frac{1}{K}\sum_{k\in\mathcal{K}}\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot((w^{(t)}_{k,\star})_{N^{r}_{k}}-(w_{k}^{(t)})_{N^{r}_{k}})\right],$

where $\forall k\in\mathcal{K}$

$w^{(t)}_{k,\star}\in\mathop{\mathrm{argmin}}_{\begin{subarray}{c}\left\lVert
w\right\rVert_{2}\leq W\\\ w(N^{r}_{-k})=0\end{subarray}}\mathbb{E}_{s\sim
d^{(t)},a\sim\pi^{(t)}(\cdot|s)}\left[\widetilde{A}^{(t)}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a_{k}|s_{N^{r}_{k}})\cdot
w\right]^{2}.$

We now analyse each term separately.

#### Term 1

$\displaystyle\frac{1}{K}\sum_{k\in\mathcal{K}}\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[\widetilde{A}^{(t)}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot(w_{k,\star}^{(t)})_{N^{r}_{k}}\right]$
$\displaystyle\leq\frac{1}{K}\sum_{k\in\mathcal{K}}\sqrt{\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[\widetilde{A}^{(t)}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot(w_{k,\star}^{(t)})_{N^{r}_{k}}\right]^{2}}\leq\sqrt{\varepsilon_{\text{bias}}}$

#### Term 2

Firstly, we have that $\forall k\in\mathcal{K}$

$\displaystyle\widetilde{Q}^{\pi}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{k}(s_{k}(t),a_{k}(t))\big{|}\pi_{N^{r}_{k}},s_{N^{r}_{k}}(0)=s_{N^{r}_{k}},a_{N^{r}_{k}}(0)=a_{N^{r}_{k}}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{k}(s_{k}(t),a_{k}(t))\big{|}\pi_{N^{r}_{k}},s_{N^{r}_{k}}(0)=s_{N^{r}_{k}},a_{N^{r}_{k}}(0)=a_{N^{r}_{k}},\right.\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.\left.s_{N^{r}_{-k}}(0),a_{N^{r}_{-k}}(0)\right]\right]$
$\displaystyle=\mathbb{E}\left[Q_{k}^{\pi}\left(s_{N^{r}_{k}},a_{N^{r}_{k}},s_{N^{r}_{-k}}(0),a_{N^{r}_{-k}}(0)\right)\right],$

for some distribution of $s(0)_{N^{r}_{-k}}$ and $a(0)_{N^{r}_{-k}}$.
Similarly $\forall k\in\mathcal{K}$

$V^{\pi}_{k}(s)-\widetilde{V}^{\pi}_{k}(s_{N^{r}_{k}})=\mathbb{E}\left[V^{\pi}_{k}(s)-V_{k}^{\pi}\left(s_{N^{r}_{k}},s(0)_{N^{r}_{-k}}\right)\right].$

So

$A^{\pi}_{k}(s,a)-\widetilde{A}^{\pi}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})=Q^{\pi}_{k}(s,a)-\widetilde{Q}^{\pi}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})-V^{\pi}_{k}(s)+\widetilde{V}^{\pi}_{k}(s_{N^{r}_{k}}),$
$\displaystyle V^{\pi}_{k}(s)-\widetilde{V}^{\pi}_{k}(s_{N^{r}_{k}})$
$\displaystyle=\mathbb{E}\left[V^{\pi}_{k}(s)-V_{k}^{\pi}\left(s_{N^{r}_{k}},s(0)_{N^{r}_{-k}}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[c^{\prime}\xi^{r+1}\right]=c^{\prime}\xi^{r+1}$

and

$\displaystyle
Q^{\pi}_{k}(s,a)-\widetilde{Q}^{\pi}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})$
$\displaystyle=\mathbb{E}\left[Q^{\pi}_{k}(s,a)-Q_{k}^{\pi}\left(s_{N^{r}_{k}},a_{N^{r}_{k}},s(0)_{N^{r}_{-k}},a(0)_{N^{r}_{-k}}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[c\rho^{r+1}\right]=c\rho^{r+1}.$

Then $\forall k\in\mathcal{K}$

$\left|A^{\pi}_{k}(s,a)-\widetilde{A}^{\pi}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})\right|\leq
c\rho^{r+1}+c^{\prime}\xi^{r+1}.$

#### Term 3

In this paragraph, we denote, $\forall k\in\mathcal{K}$,
$w^{(t)}_{k,\star}=(w^{(t)}_{k,\star})_{N^{r}_{k}}$ and
$w^{(t)}_{k}=(w_{k}^{(t)})_{N^{r}_{k}}$ for clarity of exposition. Remember
that

$\Sigma_{\nu,k}^{\theta}=\mathbb{E}_{s,a\sim\nu}\left[\nabla_{(\theta_{k})_{N_{k}^{r}}}\log\pi_{\theta}(a_{k}|s_{N_{k}^{r}})(\nabla_{(\theta_{k})_{N_{k}^{r}}}\log\pi_{\theta}(a_{k}|s_{N_{k}^{r}}))^{\top}\right]$

and that we assume, $\forall k$,

$\sup_{w\in\mathbb{R}^{d}}\frac{w^{\top}\Sigma^{(t)}_{d^{\star},k}w}{w^{\top}\Sigma^{(t)}_{\nu,k}w}\leq\kappa^{\prime}.$

Then $\forall k\in\mathcal{K}$

$\displaystyle\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot(w^{(t)}_{k,\star}-w^{(t)}_{k})\right]$
$\displaystyle\leq\sqrt{(w^{(t)}_{k,\star}-w^{(t)}_{k})^{\top}\Sigma^{(t)}_{d^{\star},k}(w^{(t)}_{k,\star}-w^{(t)}_{k})}$
$\displaystyle=\sqrt{\frac{(w^{(t)}_{k,\star}-w^{(t)}_{k})^{\top}\Sigma^{(t)}_{d^{\star},k}(w^{(t)}_{k,\star}-w^{(t)}_{k})}{(w^{(t)}_{k,\star}-w^{(t)}_{k})^{\top}\Sigma^{(t)}_{\nu,k}(w^{(t)}_{k,\star}-w^{(t)}_{k})}(w^{(t)}_{k,\star}-w^{(t)}_{k})^{\top}\Sigma^{(t)}_{\nu,k}(w^{(t)}_{k,\star}-w^{(t)}_{k})}$
$\displaystyle\leq\sqrt{\kappa^{\prime}(w^{(t)}_{k,\star}-w^{(t)}_{k})^{\top}\Sigma^{(t)}_{\nu,k}(w^{(t)}_{k,\star}-w^{(t)}_{k})}$
$\displaystyle[\text{using that $(1-\gamma)\nu\leq d^{\pi^{(t)}}_{\nu}$}]$
$\displaystyle\leq\sqrt{\frac{\kappa^{\prime}}{1-\gamma}(w^{(t)}_{k,\star}-w^{(t)}_{k})^{\top}\Sigma_{d^{(t)}}^{(t)}(w^{(t)}_{k,\star}-w^{(t)}_{k})}.$

Since $w^{(t)}_{k,\star}$ optimizes
$\widetilde{L}_{k}(w,\theta^{(t)},d^{(t)})$ the first order optimality
condition implies that, $\forall w$, $\forall k\in\mathcal{K}$,

$(w-w^{(t)}_{k,\star})\cdot\nabla\widetilde{L}_{k}(w^{(t)}_{k,\star},\theta^{(t)},d^{(t)})\geq
0.$

So $\forall w$, $\forall k\in\mathcal{K}$,

$\displaystyle\widetilde{L}_{k}(w,\theta^{(t)},d^{(t)})-\widetilde{L}_{k}(w^{(t)}_{k,\star},\theta^{(t)},d^{(t)})$
$\displaystyle=\mathbb{E}_{s\sim
d^{(t)},a\sim\pi^{(t)}(\cdot|s)}\left[\widetilde{A}_{k}^{(t)}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot
w\right.$
$\displaystyle\left.\qquad\qquad\qquad\qquad\quad+\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot
w^{(t)}_{k,\star}-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot
w^{(t)}_{k,\star}\right]^{2}$
$\displaystyle\qquad-\widetilde{L}_{k}(w^{(t)}_{k,\star},\theta^{(t)},d^{(t)})$
$\displaystyle=\mathbb{E}_{s\sim
d^{(t)},a\sim\pi^{(t)}(\cdot|s)}\left[\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot
w^{(t)}_{k,\star}-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot
w\right]^{2}$ $\displaystyle+2(w-w^{(t)}_{k,\star})\mathbb{E}_{s\sim
d^{(t)},a\sim\pi^{(t)}(\cdot|s)}\left[\left(\widetilde{A}_{k}^{(t)}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot
w^{(t)}_{k,\star}\right)\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.\cdot\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\right]$
$\displaystyle=(w^{(t)}_{k,\star}-w^{(t)}_{k})^{\top}\Sigma_{d^{(t)}}^{(t)}(w^{(t)}_{k,\star}-w^{(t)}_{k})+(w-w^{(t)}_{k,\star})\cdot\nabla\widetilde{L}_{k}(w^{(t)}_{k,\star},\theta^{(t)},d^{(t)})$
$\displaystyle\geq(w^{(t)}_{k,\star}-w^{(t)}_{k})^{\top}\Sigma_{d^{(t)}}^{(t)}(w^{(t)}_{k,\star}-w^{(t)}_{k}).$

Therefore

$\displaystyle\mathbb{E}\left[\mathbb{E}_{s\sim
d^{\star},a\sim\pi^{\star}(\cdot|s)}\left[\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot(w^{(t)}_{k,\star}-w^{(t)}_{k})\right]\right]$
$\displaystyle\leq\sqrt{\mathbb{E}\left[\frac{\kappa^{\prime}}{1-\gamma}(\widetilde{L}_{k}(w,\theta^{(t)},d^{(t)})-\widetilde{L}_{k}(w^{(t)}_{k,\star},\theta^{(t)},d^{(t)}))\right]}$
$\displaystyle=\sqrt{\mathbb{E}\left[\frac{\kappa^{\prime}}{1-\gamma}\mathbb{E}\left[(\widetilde{L}_{k}(w,\theta^{(t)},d^{(t)})-\widetilde{L}_{k}(w^{(t)}_{k,\star},\theta^{(t)},d^{(t)}))\big{|}\theta^{(t)}\right]\right]}$
$\displaystyle\leq\sqrt{\frac{\kappa^{\prime}\varepsilon_{\text{stat}}}{1-\gamma}},$

which completes the proof.

##  Appendix F Statistical Error

Assume access to a global clock, then Algorithm 2 is a sampler of $d^{(t)}$
and an unbiased sampler of
$\widetilde{A}_{k}^{(t)}(s_{N^{r}_{k}},a_{N^{r}_{k}})$, for every
$k\in\mathcal{K}$.

###### Proposition 19

Consider the setting of Theorem 9 and assume access to the sampler in
Algorithm 2. Assume that
$\left\lVert\nabla_{(\theta_{k})_{N_{k}^{r}}}\log\pi^{(t)}(a|s)\right\rVert_{2}\leq
B$. Then, solving the minimization problem in (8) with stochastic projected
gradient descent for $N$ steps and step size
$\alpha=W/(8B(BW+\frac{1}{1-\gamma})\sqrt{N})$ gives

$\varepsilon_{\text{stat}}\leq\frac{8BW(BW+\frac{1}{1-\gamma})}{\sqrt{N}}.$

Proof: The proposition follows from a result on stochastic projected gradient
descent [Shalev-Shwartz and Ben-David, 2014]. Consider the minimization
problem $\min_{x\in C}f(x)$ for a convex function $f$, then performing the
update

$x_{t+1}=P_{C}(x_{t}-\alpha v_{t}),$

where $C=\\{x:\left\lVert x\right\rVert_{2}\leq W\\}$ for some $W\geq 0$,
$P_{C}(\cdot)$ is the projection on $C$, $v_{t}$ is such that
$\mathbb{E}[v_{t}|x_{t}]=\nabla f(x_{t})$ and $\left\lVert
v_{t}\right\rVert\leq\rho$, for $N$ steps and with
$\alpha=\sqrt{\frac{W^{2}}{\rho^{2}N}}$, gives

$\mathbb{E}\left[f\left(\frac{1}{N}\sum_{t=1}^{N}x_{t}\right)\right]-f(x^{\star})\leq\frac{W\rho}{\sqrt{N}}.$

Noticing that $\widetilde{A}^{(t)}_{k}(s,a)\leq 2/(1-\gamma)$ and that the
sampled gradient is therefore bounded by $8B(BW+\frac{1}{1-\gamma})$ gives the
proposition.

The minimization problem in (8) can therefore be solved by each agent $k$
through stochastic projected gradient descent, which only depends on the
states and actions of $N^{r}_{k}$ and on the parameters
$(\theta_{k})_{N_{k}^{r}}$ and with a computational cost that does not depend
on $K$.

Input: Starting state-action distribution $\nu$

For each agent $k\in\mathcal{K}$ set $\widehat{Q}_{k}=0$, $\widehat{V}_{k}=0$.

$\forall k\in\mathcal{K}$, sample $s_{k}(0),a_{k}(0)\sim\nu_{k}$ and start at
state $s_{k}(0)$;

($d^{\pi}_{\nu}$ sampling) At every time-step $h\geq 0$:

with probability $\gamma$, $\forall k\in\mathcal{K}$ execute $a_{k}(h)$,
transition to $s_{k}(h+1)$ and sample
$a_{k}(h+1)\sim\pi_{k}(\cdot|s_{N^{r}_{k}}(h+1))$;

else accept $(s(h),a(h))$ as the sample and exit the loop, each agent only
saves $\left(s_{N^{r}_{k}}(h),a_{N^{r}_{k}}(h)\right)$.

Set SampleQ=True with probability 1/2;

if  _SampleQ=True_ then

$\forall k\in\mathcal{K}$ execute $a_{k}(h)$ and then, for every time-step
$h^{\prime}>h$ with termination probability $\gamma$, transition to
$s_{k}(h^{\prime})$, sample
$a_{k}(h^{\prime}+1)\sim\pi_{k}(\cdot|s_{N^{r}_{k}}(h^{\prime}+1))$ and set
$\widehat{Q}_{k}=\widehat{Q}_{k}+r(s_{k}(h^{\prime}),a_{k}(h^{\prime}))$;

end if

else

$\forall k\in\mathcal{K}$ sample $a_{k}(h)\sim\pi_{k}(\cdot|s_{N^{r}_{k}}(h))$
and execute $a_{k}(h)$ and then, for every time-step $h^{\prime}>h$ with
termination probability $\gamma$, transition to $s_{k}(h^{\prime})$, sample
$a_{k}(h^{\prime}+1)\sim\pi_{k}(\cdot|s_{N^{r}_{k}}(h^{\prime}+1))$ and set
$\widehat{V}_{k}=\widehat{V}_{k}+r(s_{k}(h^{\prime}),a_{k}(h^{\prime}))$;

end if

Result: $(s(h),a(h))$ and
$\left(\widehat{A}_{k}\left(s_{N^{r}_{k}}(h),a_{N^{r}_{k}}(h)\right)=2\left(\widehat{Q}_{k}-\widehat{V}_{k}\right)\right)_{k\in\mathcal{K}}$.

Algorithm 2 Sampler

##  Appendix G Bias analysis

Let $\widetilde{L}_{k}^{r}$ and $w_{k,\star}$ be defined as in Section 4. For
every $k\in\mathcal{K}$, let

${L}_{k}(w,\theta,\nu)=\mathbb{E}_{s,a\sim\nu}\left[\left({A}^{\pi_{\theta}}_{k}(s,a)-\nabla_{\theta_{k}}\log\pi_{\theta_{k}}(a_{k}|s)\cdot
w\right)^{2}\right].$

Let $\varepsilon_{\text{bias},r}$ be the smallest possible localized bias term
associated to the range parameter $r$, i.e.

$\varepsilon_{\text{bias},r}=\max_{k\in\mathcal{K}}\widetilde{L}_{k}^{r}(w_{k,\star},\theta^{(t)},d^{\star}),$

which is the same assumption as in Theorem 9, but with an equality instead of
an inequality. Let $\varepsilon_{\text{bias}}$ be the smallest possible non-
localized bias term associated with an infinite range parameter, i.e. the case
where we make no approximation, namely,

$\varepsilon_{\text{bias}}=\max_{k\in\mathcal{K}}{L}_{k}(w^{\prime}_{k,\star},\theta^{(t)},d^{\star})$

where

$w^{\prime}_{k,\star}\in\mathop{\mathrm{argmin}}_{\lVert w\rVert_{2}\leq
W}{L}_{k}(w,\theta^{(t)},d^{(t)}).$

###### Proposition 20

Assume that

$\left\lVert\nabla_{\theta_{k}}\log\pi^{(t)}(a|s)\right\rVert_{2}\leq B$

and that

$\left\lVert\nabla_{(\theta_{k})_{N^{r}_{-k}}}\pi_{\theta}(a_{k}|s)\right\rVert_{2}\leq\omega_{r}.$

Then

$\varepsilon_{\text{bias},r}\leq\varepsilon_{\text{bias}}+e_{r}+2\left(\frac{2}{1-\gamma}+WB\right)\sqrt{\frac{2\kappa^{\prime}e_{r}}{1-\gamma}}+\frac{2\kappa^{\prime}e_{r}}{1-\gamma},$

where

$e_{r}=\left(\frac{4}{1-\gamma}+2WB\right)W\omega_{r}+\left(\frac{4}{1-\gamma}+2WB\right)\left(c\psi^{r+1}+c^{\prime}\phi^{r+1}\right).$

The second assumption can be respected by choosing a policy belonging to the
policy class described in Appendix A, as $\omega_{r}$ can be controlled by
setting the parameters $\\{\alpha_{r}\\}$ small enough. In particular, it is
possible to set it to be exponentially small in $r$. Therefore, the
proposition shows that the localized bias is at most the bias associated with
an infinite range parameter plus a quantity that goes to 0 exponentially fast
in $r$. We present the proof of this result below.

Proof:[of Proposition 20] To prove the proposition we need two intermediate
results. For any $w$,$\theta$ and $\nu$, we have that

$\displaystyle\left|\widetilde{L}^{r}_{k}((w)_{N^{r}_{k}},\theta,\nu)-L_{k}(w,\theta,\nu)\right|$
$\displaystyle=\mathbb{E}_{s,a\sim\nu}\left[\left(\widetilde{A}^{\pi_{\theta}}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})\right)^{2}-\left({A}^{\pi_{\theta}}_{k}(s,a)\right)^{2}\right]$
$\displaystyle\quad+\mathbb{E}_{s,a\sim\nu}\left[\left(\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot(w)_{N^{r}_{k}}\right)^{2}-\left(\nabla_{\theta_{k}}\log\pi_{\theta_{k}}(a_{k}|s)\cdot
w\right)^{2}\right]$
$\displaystyle\quad+2\mathbb{E}_{s,a\sim\nu}\left[{A}^{\pi_{\theta}}_{k}(s,a)\nabla_{\theta_{k}}\log\pi_{\theta_{k}}(a_{k}|s)\cdot
w-\widetilde{A}^{\pi_{\theta}}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s)\cdot(w)_{N^{r}_{k}}\right]$
$\displaystyle\leq\frac{4}{1-\gamma}\left(c\psi^{r+1}+c^{\prime}\phi^{r+1}\right)+2W^{2}B\omega_{r}+2WB\left(c\psi^{r+1}+c^{\prime}\phi^{r+1}\right)+\frac{4}{1-\gamma}W\omega_{r}$
$\displaystyle=e_{r}.$

Following the same passages in the proof of Theorem 9 in Appendix E, we have
that

$\displaystyle\max_{k\in\mathcal{K}}\mathbb{E}_{s,a\sim
d^{\star}}\left[\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s_{N^{r}_{k}})^{\top}\left((w^{\prime}_{k,\star})_{N^{r}_{k}}-w_{k,\star}\right)\right]$
$\displaystyle\leq\sqrt{\frac{\kappa^{\prime}}{1-\gamma}(\widetilde{L}^{r}_{k}((w^{\prime}_{k,\star})_{N^{r}_{k}},\theta^{(t)},d^{(t)})-\widetilde{L}^{r}_{k}(w_{k,\star},\theta^{(t)},d^{(t)}))}$
$\displaystyle[\text{using the first result}]$
$\displaystyle\leq\sqrt{\frac{\kappa^{\prime}}{1-\gamma}\left|{L}_{k}(w^{\prime}_{k,\star},\theta^{(t)},d^{(t)})-\widetilde{L}^{r}_{k}(w_{k,\star},\theta^{(t)},d^{(t)})\right|+\frac{\kappa^{\prime}e_{r}}{1-\gamma}}$
$\displaystyle=\sqrt{\frac{\kappa^{\prime}}{1-\gamma}\left|\min_{\lVert
w\rVert_{2}\leq W}{L}_{k}(w,\theta^{(t)},d^{(t)})-\min_{\lVert w\rVert_{2}\leq
W}\widetilde{L}^{r}_{k}((w)_{N^{r}_{k}},\theta^{(t)},d^{(t)})\right|+\frac{\kappa^{\prime}e_{r}}{1-\gamma}}$
$\displaystyle\leq\sqrt{\frac{2\kappa^{\prime}e_{r}}{1-\gamma}}.$

We can now prove the proposition.

$\displaystyle\varepsilon_{\text{bias},r}$
$\displaystyle=\max_{k\in\mathcal{K}}\mathbb{E}_{s,a\sim
d^{\star}}\left[\left(\widetilde{A}^{(t)}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s_{N^{r}_{k}})\cdot
w_{k,\star}\right)^{2}\right]$
$\displaystyle=\max_{k\in\mathcal{K}}\mathbb{E}_{s,a\sim
d^{\star}}\left[\left(\widetilde{A}^{(t)}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s_{N^{r}_{k}})\cdot(w^{\prime}_{k,\star})_{N^{r}_{k}}\right)^{2}\right.$
$\displaystyle\qquad\qquad\qquad\quad+2\left(\widetilde{A}^{(t)}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s_{N^{r}_{k}})\cdot(w^{\prime}_{k,\star})_{N^{r}_{k}}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\quad\cdot\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s_{N^{r}_{k}})^{\top}\left((w^{\prime}_{k,\star})_{N^{r}_{k}}-w_{k,\star}\right)$
$\displaystyle\left.\qquad\qquad\qquad\quad+\left(\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s_{N^{r}_{k}})^{\top}\left((w^{\prime}_{k,\star})_{N^{r}_{k}}-w_{k,\star}\right)\right)^{2}\right]$
$\displaystyle\leq\max_{k\in\mathcal{K}}\mathbb{E}_{s,a\sim
d^{\star}}\left[\left(\widetilde{A}^{(t)}_{k}(s_{N^{r}_{k}},a_{N^{r}_{k}})-\nabla_{(\theta_{k})_{N^{r}_{k}}}\log\pi^{(t)}(a|s_{N^{r}_{k}})\cdot(w^{\prime}_{k,\star})_{N^{r}_{k}}\right)^{2}\right]$
$\displaystyle\quad+2\left(\frac{2}{1-\gamma}+WB\right)\sqrt{\frac{2\kappa^{\prime}e_{r}}{1-\gamma}}+\frac{2\kappa^{\prime}e_{r}}{1-\gamma}$
$\displaystyle=\max_{k\in\mathcal{K}}\widetilde{L}_{k}^{r}((w^{\prime}_{k,\star})_{N^{r}_{k}},\theta^{(t)},d^{\star})+2\left(\frac{2}{1-\gamma}+WB\right)\sqrt{\frac{2\kappa^{\prime}e_{r}}{1-\gamma}}+\frac{2\kappa^{\prime}e_{r}}{1-\gamma}$
$\displaystyle\leq\varepsilon_{\text{bias}}+e_{r}+2\left(\frac{2}{1-\gamma}+WB\right)\sqrt{\frac{2\kappa^{\prime}e_{r}}{1-\gamma}}+\frac{2\kappa^{\prime}e_{r}}{1-\gamma}.$