scaletikzpicturetowidth[1]

# Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games

Stefanos Leonardos
SUTD  Will Overman
UC Irvine  Ioannis Panageas
UC Irvine  Georgios Piliouras
SUTD

###### Abstract

Potential games are arguably one of the most important and widely studied
classes of normal form games. They define the archetypal setting of multi-
agent coordination as all agent utilities are perfectly aligned with each
other via a common potential function. Can this intuitive framework be
transplanted in the setting of Markov Games? What are the similarities and
differences between multi-agent coordination with and without state
dependence? We present a novel definition of Markov Potential Games (MPG) that
generalizes prior attempts at capturing complex stateful multi-agent
coordination. Counter-intuitively, insights from normal-form potential games
do not carry over as MPGs can consist of settings where state-games can be
zero-sum games. In the opposite direction, Markov games where every state-game
is a potential game are not necessarily MPGs. Nevertheless, MPGs showcase
standard desirable properties such as the existence of deterministic Nash
policies. In our main technical result, we prove (polynomially fast in the
approximation error) convergence of independent policy gradient to Nash
policies by adapting recent gradient dominance property arguments developed
for single agent MDPs to multi-agent learning settings.

##  1 Introduction

Reinforcement learning (RL) has been a fundamental driver of numerous recent
advances in Artificial Intelligence (AI) that range from super-human
performance in competitive game-playing [29, 30, 5] and strategic decision-
making in multiple tasks [21, 24, 34] to robotics, autonomous-driving and
cyber-physical systems [7, 38]. A core ingredient for the success of single-
agent RL systems, which are typically modelled as Markov Decision Processes
(MDPs), is the existence of stationary deterministic optimal policies [3, 31].
This allows the design of efficient algorithms that provably converge towards
such policies [1]. However, in practice, a majority of the above systems
involve multi-agent interactions. In such cases, despite the notable empirical
advancements, there is a lack of understanding of the theoretical convergence
guarantees of existing multi-agent reinforcement learning (MARL) algorithms.

The main challenge when transitioning from single to multi-agent RL settings
is the computation of _Nash policies_. A Nash policy for $n>1$ agents is
defined to be a profile of policies $(\pi_{1}^{*},...,\pi_{n}^{*})$ so that by
fixing the stationary policies of all agents but $i$, $\pi_{i}^{*}$ is an
optimal policy for the resulting single-agent MDP and this is true for all
$1\leq i\leq n$ 111Analogue of Nash equilibrium notion. (see Definition 1).
Note that in multi-agent settings, Nash policies may not be unique in
principle.

A common approach for computing Nash policies in MDPs is the use of _policy
gradient_ methods. There has been significant progress in the analysis of
policy gradient methods during the last couple of years, notably including the
works of [1] (and references therein), but it has mainly concerned the single-
agent case: the convergence properties of policy gradient in MARL remain
poorly understood. Existing steps towards a theory for multi-agent settings
involve the papers of [11] who show convergence of independent policy gradient
to the optimal policy for two-agent zero-sum stochastic games, of [37] who
improve the result of [11] using optimistic policy gradient and of [39] who
study extensions of Natural Policy Gradient using function approximation. It
is worth noting that the positive results of [11, 37] and [39] depend on the
fact that two-agent stochastic zero-sum games satisfy the “min-max equals max-
min” property [28] (even though the value-function landscape may not be
convex-concave, which implies that Von Neumann’s celebrated minimax theorem
may not be applicable).

#### Model and Informal Statement of Results.

While the previous works enhance our understanding in _competitive_
interactions, i.e., interactions in which gains can only come at the expense
of others, MARL in _cooperative_ settings remains largely under-explored and
constitutes one of the current frontiers in AI research [10, 9]. Based on the
above, our work is motivated by the following natural question:

Can we get (provable) convergence guarantees for multi-agent RL settings in
which cooperation is desirable?

To address this question, we define and study a class of $n$-agent MDPs that
naturally generalize normal form potential games [22], called _Markov
Potential Games (MPGs)_. In words, a multi-agent MDP is a MPG as long as there
exists a (state-dependent) real-valued potential function $\Phi$ so that if an
agent $i$ changes their policy (and the rest of the agents keep their policy
unchanged), the difference in agent $i$’s value/utility, $V^{i}$, is captured
by the difference in the value of $\Phi$ (see Definition 2). Weighted and
ordinal MPGs are defined similar to their normal form counterparts (see Remark
1).

Under our definition, we answer the above motivating question in the
affirmative. In particular, we show that if every agent $i$ independently runs
(with simultaneous updates) policy gradient on his utility/value $V^{i}$,
then, after $O(1/\epsilon^{2})$ iterations, the system will reach an
$\epsilon$-approximate Nash policy (see informal Theorem 1.1 and formal
Theorem 4.5). Moreover, for the finite sample analogue, i.e., if every agent
$i$ independently runs (with simultaneous updates) stochastic policy gradient,
we show that the system will reach an $\epsilon$-approximate Nash policy after
$O(1/\epsilon^{6})$ iterations.

Along the way, we prove several properties about the structure of MPGs and
their Nash policies (see Theorem 1.2 and Section 3). In sum, our results can
be summarized in the following two Theorems.

######  Theorem 1.1 (Convergence of Policy Gradient (Informal)).

Consider a MPG with $n$ agents and let $\epsilon>0$. Suppose that each agent
$i$ runs independent policy gradient using direct parameterization on their
policy and that the updates are simultaneous. Then, the learning dynamics
reach an $\epsilon$-Nash policy after $\mathcal{O}(1/\epsilon^{2})$
iterations. If instead, each agent $i$ runs stochastic policy gradient using
greedy parameterization (see (4)) on his policy and that the updates are
simultaneous, then the learning dynamics reach an $\epsilon$-Nash policy after
$\mathcal{O}(1/\epsilon^{6})$ iterations.

This result holds trivially for weighted MPGs and asymptotically also for
ordinal MPGs, see Remark 5.

######  Theorem 1.2 (Structural Properties of MPGs).

The following facts are true for MPGs with $n$-agents:

  * a.

There always exists a Nash policy profile $(\pi_{1}^{*},\dots,\pi_{n}^{*})$ so
that $\pi_{i}^{*}$ is deterministic for each agent $i$ (see Theorem 3.1).

  * b.

We can construct MDPs for which each state is a (normal-form) potential game
but which are not MPGs. This can be true regardless of whether the whole MDP
is competitive or cooperative in nature (see Examples 1 and 2, respectively).
On the opposite side, we can construct MDPs that are MPGs but which include
states that are purely competitive (i.e., zero-sum games), see Example 3.

  * c.

We provide sufficient conditions so that a MDP is a MPG. These include cases
where each state is a (normal-form) potential game and the transition
probabilities are not affected by agents actions or the reward functions
satisfy certain regularity conditions between different states (see conditions
C1 and C2 in Proposition 3.2).

#### Technical Overview.

The first challenge in the proof of Theorem 1.1 is that multi-agent settings
(MPGs) do not satisfy the gradient dominance property, which is an important
part in the proof of convergence of policy gradient in single-agent settings
[1]. In particular, different Nash policies may yield different value to each
agent and as a result, there is not a properly defined notion of value in MPGs
(in contrast to zero-sum stochastic games [11]). On the positive side, we show
that agent-wise (i.e., after fixing the policy of all agents but $i$), the
value function, $V^{i}$, satisfies the gradient dominance property along the
direction of $\pi_{i}$ (policy of agent $i$). This can be leveraged to show
that every _(approximate) stationary point_ (Definition 4) of the potential
function $\Phi$ is an _(approximate) Nash policy_ (Lemma 4.2). As a result,
convergence to an approximate Nash policy is established by first showing that
$\Phi$ is smooth and then by applying _Projected Gradient Ascent ( PGA)_ on
$\Phi$. This step uses the rather well-known fact that (PGA) converges to
$\epsilon$-stationary points in $O(1/\epsilon^{2})$ iterations for smooth
functions. As a result, by applying PGA on the potential $\Phi$, one gets an
approximate Nash policy. Our convergence result then follows by showing that
PGA on the potential function, $\Phi$, generates the same dynamics as if each
agent $i$ runs independent PGA on their value function, $V^{i}$.

In the case that agents do not have access to exact gradients, we derive a
similar result for finite samples. In this case, we apply _Projected
Stochastic Gradient Ascent (PSGA)_ on $\Phi$ which (as was the case for PGA)
can be shown to be the same as when agents apply PSGA independently on their
individual value functions. The key is to get an unbiased sample for the
gradient of the value functions and prove that it has bounded variance (in
terms of the parameters of the MPG). This comes from the discount factor,
$\gamma$; in this case, $1-\gamma$ can be interpreted as the probability to
terminate the MDP at a particular state (and $\gamma$ to continue). This can
be used to show that a trajectory of the MDP is an unbiased sample for the
gradient of the value functions. To guarantee that the estimate has bounded
variance, we apply the approach of [11] which requires that agents perform
PSGA with $\alpha$-greedy exploration (see (4)). The main idea is that this
parameterization stays away from the boundary of the simplex throughout its
trajectory.

Concerning our structural results, the main technical challenge is the
dependence of state-transitions (in addition to agents’ rewards) on agents’
actions. Our work in this part is mainly concerned with showing that the class
of MPGs can be significantly larger than state based potential games but also
that even simple coordination games may fail to satisfy the (exact) MPG
property. Finally, concerning the existence of a deterministic Nash policies,
the main challenge is (as in Theorem 1.1) the lack of a (unique) value in
general multi-agent settings. As we show in the proof of Theorem 3.1, this
issue can be still handled within the class of MPGs by constructing single-
agent deviations (to deterministic optimal policies) which keep the value of
the potential constant (at its global maximum). This process (which leads to a
deterministic Nash policy profile) depends critically on the MPG property and
does not generalize to arbitrary MARL settings.

#### Other works on MPGs.

There are only a few papers in the recent literature that define and analyze
MARL settings under the term _Markov Potential Games_ using slight different
definitions (see [18, 33]). These papers mainly focus on state-based potential
MDPs (i.e., MDPs in which every state is a potential game) and require rather
restrictive additional conditions, such as equality or monotonicity of the
state-based potential functions, to address the computational challenge of
finding Nash policies.222The relation of these conditions to the current work
is discussed in more detail in Proposition 3.2 and Remark 2. Our current
results demonstrate the efficiency of simultaneous policy gradient as a to
powerful method to find Nash policies even without additional restrictive
assumptions on the state-based potential functions. Moreover, as mentioned in
Theorem 1.2, the current definition also encompasses MDPs that are not
necessarily potential at each state. To the best of our knowledge, the only
(cooperative) MPGs that have been successfully addressed prior to this work,
are the ones in which all agents receive the same value/utility [36] and which
constitute a subclass of the MPG setting considered in this paper.

##  2 Preliminaries

#### Markov Decision Process (MDP).

The following notation is standard and largely follows [1] and [11]. We
consider a setting with $n$ agents who repeatedly select actions in a shared
Markov Decision Process (MDP). The goal of each agent is to maximize their
respective value function. Formally, a MDP is defined as a tuple
$\mathcal{G}=(\mathcal{S},\mathcal{N},\\{\mathcal{A}_{i},R_{i}\\}_{i\in\mathcal{N}},P,\gamma,\rho)$,
where

  * •

$\mathcal{S}$ is a finite state space of size $S=|\mathcal{S}|$. We will write
$\Delta(\mathcal{S})$ to denote the set of all probability distributions over
the set $\mathcal{S}$.

  * •

$\mathcal{N}=\\{1,2,\dots,n\\}$ is the set of the $n\geq 2$ agents in the
game.

  * •

$\mathcal{A}_{i}$ is a finite action space for agent $i\in\mathcal{N}$ with
generic element $a_{i}\in\mathcal{A}_{i}$. Using common conventions, we will
write $\mathcal{A}=\prod_{i\in\mathcal{N}}\mathcal{A}_{i}$ and
$\mathcal{A}_{-i}=\prod_{j\neq i}\mathcal{A}_{j}$ to denote the joint action
spaces of all agents and of all agents other than $i$ with generic elements
$\mathbf{a}=(a_{i})_{i\in\mathcal{N}}$ and $\mathbf{a_{-i}}=(a_{j})_{i\neq
j\in\mathcal{N}}$, respectively. According to this notation, we have that
$\mathbf{a}=(a_{i},\mathbf{a_{-i}})$. We will write $X=|\mathcal{X}|$ and
$\Delta(\mathcal{X})$ to denote the size of any set
$\mathcal{X}\in\\{\mathcal{A}_{i},\mathcal{A}_{-i},\mathcal{A}\\}$ and the
space of all probability distributions over $\mathcal{X}$, respectively.

  * •

$R_{i}:\mathcal{S}\times\mathcal{A}\to[-1,1]$ is the individual reward
function of agent $i\in\mathcal{N}$, i.e., $R_{i}(s,a_{i},\mathbf{a}_{-i})$ is
the instantaneous reward of agent $i$ when agent $i$ takes action $a_{i}$ and
all other agents take actions $\mathbf{a}_{-i}$ at state $s\in\mathcal{S}$.

  * •

$P$ is the transition probability function, for which $P(s^{\prime}\mid
s,\mathbf{a})$ is the probability of transitioning from $s$ to $s^{\prime}$
when $\mathbf{a}\in\mathcal{A}$ is the action profile chosen by the agents.

  * •

$\gamma$ is a discount factor for future rewards of the MDP, shared by all
agents.

  * •

$\rho\in\Delta(\mathcal{S})$ is the distribution for the initial state at time
$t=0$.

Whenever time is relevant, we will index the above terms with $t$. In
particular, at each time step $t\geq 0$, all agents observe the state
$s_{t}\in\mathcal{S}$, select actions
$\mathbf{a}_{t}=(a_{i,t},\mathbf{a}_{-i,t})$, receive rewards
$r_{i,t}:=R_{i}(s_{t},\mathbf{a}_{t}),i\in\mathcal{N}$ and transition to the
next state $s_{t+1}\sim P(\cdot\mid s_{t},\mathbf{a}_{t})$. We will write
$\tau=(s_{t},\mathbf{a}_{t},\mathbf{r}_{t})_{t\geq 0}$ to denote the
trajectories of the system, where $\mathbf{r}_{t}:=(r_{i,t}),i\in\mathcal{N}$.

#### Policies and Value Functions.

For each agent $i\in\mathcal{N}$, a deterministic, stationary policy
$\pi_{i}:\mathcal{S}\to\mathcal{A}_{i}$ specifies the action of agent $i$ at
each state $s\in\mathcal{S}$, i.e., $\pi_{i}(s)=a_{i}\in\mathcal{A}_{i}$ for
each $s\in\mathcal{S}$. A stochastic, stationary policy
$\pi_{i}:\mathcal{S}\to\Delta(\mathcal{A}_{i})$ specifies a probability
distribution over the actions of agent $i$ for each state $s\in\mathcal{S}$.
In this case, we will write $a_{i}\sim\pi_{i}(\cdot\mid s)$ to denote the
randomized action of agent $i$ at state $s\in\mathcal{S}$. We will write
$\pi_{i}\in\Pi_{i}:=\Delta(\mathcal{A}_{i})^{S}$ and
$\pi=(\pi_{i})_{i\in\mathcal{N}}\in\Pi:=\times_{i\in\mathcal{N}}\Delta(\mathcal{A}_{i})^{S}$,
$\pi_{-i}=(\pi_{j})_{i\neq j\in\mathcal{N}}\in\Pi_{-i}:=\times_{i\neq
j\in\mathcal{N}}\Delta(\mathcal{A}_{j})^{S}$ to denote the joint policies of
all agents and of all agents other than $i$, respectively. A joint policy
$\pi$ induces a distribution $\mathrm{Pr}^{\pi}$ over trajectories
$\tau=(s_{t},\mathbf{a}_{t},\mathbf{r}_{t})_{t\geq 0}$, where $s_{0}$ is drawn
from the initial state distribution $\rho$ and $a_{i,t}$ is drawn from
$\pi_{i}(\cdot\mid s_{t})$ for all $i\in\mathcal{N}$.

The value function, $V_{s}^{i}:\Pi\to\mathbb{R}$, gives the expected reward of
agent $i\in\mathcal{N}$ when $s_{0}=s$ and the agents draw their actions,
$\mathbf{a}_{t}=(a_{i,t},\mathbf{a}_{-i,t})$, at time $t\geq 0$ from policies
$\pi=(\pi_{i},\pi_{-i})$

$V^{i}_{s}(\pi):=\operatorname{\mathbb{E}}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{i,t}\mid
s_{0}=s\right].$ (1)

We also denote
$V^{i}_{\rho}(\pi)=\operatorname{\mathbb{E}}_{s\sim\rho}\left[V^{i}_{s}(\pi)\right]$
if the initial state is random and follows distribution $\rho.$

#### Nash Policies.

The solution concept that will be focusing on is the Nash Policy. Formally:

######  Definition 1 (Nash Policy).

A joint policy, $\pi^{*}=(\pi_{i}^{*})_{i\in\mathcal{N}}\in\Pi$, is a Nash
policy if for each agent $i\in\mathcal{N}$ it holds that

$V_{s}^{i}(\pi_{i}^{*},\pi_{-i}^{*})\geq
V_{s}^{i}(\pi_{i},\pi_{-i}^{*}),\;\;\text{for all
}\pi_{i}\in\Delta(\mathcal{A}_{i})^{S},\;\text{and all }s\in\mathcal{S},$

i.e., if the policy, $\pi_{i}^{*}$, of each agent $i\in\mathcal{N}$ maximizes
agent $i$’s value function for each starting state $s\in\mathcal{S}$ given the
policies, $\pi^{*}_{-i}=(\pi^{*}_{j})_{j\neq i}$, of all other agents $j\neq
i\in\mathcal{N}$. Similarly, a joint policy
$\pi^{*}=(\pi_{i}^{*})_{i\in\mathcal{N}}$ is an $\epsilon$-Nash policy if
there exists an $\epsilon>0$ so that for each agent $i$

$V_{s}^{i}(\pi_{i}^{*},\pi_{-i}^{*})\geq
V_{s}^{i}(\pi_{i},\pi_{-i}^{*})-\epsilon,\;\;\text{for all
}\pi_{i}\in\Delta(\mathcal{A}_{i})^{S},\;\text{and all }s\in\mathcal{S}.$

We note that the definition of Nash policy is the same if $s\sim\rho$ (random
starting state).

#### Markov Potential Games.

We are ready to define the class of MDPs that we will focus on for the rest of
the paper, i.e., Markov Potential Games.

######  Definition 2 (Markov Potential Game).

A Markov Decision Process (MDP), $\mathcal{G}$, is called a _Markov Potential
Game (MPG)_ if there exists a (state-dependent) function
$\Phi_{s}:\Pi\to\mathbb{R}$ for $s\in\mathcal{S}$ so that

$\displaystyle\Phi_{s}(\pi_{i},\pi_{-i})-\Phi_{s}(\pi_{i}^{\prime},\pi_{-i})=V_{s}^{i}(\pi_{i},\pi_{-i})-V_{s}^{i}(\pi_{i}^{\prime},\pi_{-i}),$

for all agents $i\in\mathcal{N}$, all states $s\in\mathcal{S}$ and all
policies $\pi_{i},\pi_{i}^{\prime}\in\Pi_{i},\pi_{-i}\in\Pi_{-i}$. By
linearity of expectation, it follows that
$\Phi_{\rho}(\pi_{i},\pi_{-i})-\Phi_{\rho}(\pi_{i}^{\prime},\pi_{-i})=V_{\rho}^{i}(\pi_{i},\pi_{-i})-V_{\rho}^{i}(\pi_{i}^{\prime},\pi_{-i}),$
where
$\Phi_{\rho}(\pi):=\operatorname{\mathbb{E}}_{s\sim\rho}\left[\Phi_{s}(\pi)\right].$

As in normal-form games, an immediate consequence of this definition is that
the value function of each agent in a MPG can be written as a sum of the
potential _(common term)_ and a term that does not depend on that agent’s
policy _(dummy term)_ , cf. Proposition B.1 in Appendix B. In symbols, for
each agent $i\in\mathcal{N}$ there exists a function
$U^{i}_{s}:\Pi_{-i}\to\mathbb{R}$ so that

$V_{s}^{i}(\pi)=\Phi_{s}(\pi)+U^{i}_{s}(\pi_{-i}),\;\text{ for all
}\pi\in\Pi.$

######  Remark 1 (Ordinal and Weighted Potential Games).

Similar to normal-form games, one may also define more general notions of
MPGs, such as ordinal or weighted Markov Potential Games. Specifically, if for
all agents $i\in\mathcal{N}$, all states $s\in\mathcal{S}$ and all policies
$\pi_{i},\pi_{i}^{\prime}\in\Pi_{i},\pi_{-i}\in\Pi_{-i}$, the function
$\Phi_{s},s\in\mathcal{S}$ satisfies

$\displaystyle\Phi_{s}(\pi_{i},\pi_{-i})-\Phi_{s}(\pi_{i}^{\prime},\pi_{-i})>0\iff
V_{s}^{i}(\pi_{i},\pi_{-i})-V_{s}^{i}(\pi_{i}^{\prime},\pi_{-i})>0,$

then the MDP, $\mathcal{G}$, is called an _Ordinal Markov Potential Game
(OMPG)_. If there exist positive constants $w_{i}>0,i\in\mathcal{N}$ so that

$\displaystyle\Phi_{s}(\pi_{i},\pi_{-i})-\Phi_{s}(\pi_{i}^{\prime},\pi_{-i})=w_{i}(V_{s}^{i}(\pi_{i},\pi_{-i})-V_{s}^{i}(\pi_{i}^{\prime},\pi_{-i})),$

then $\mathcal{G}$ is called a _Weighted Markov Potential Game (WMPG)_.

Similarly to normal-form games, such classes are naturally motivated also in
the setting of multi-agent MDPs. As Example 2 in Section B.1 shows, even
simple potential-like settings, i.e., settings in which coordination is
desirable for all agents, may fail to be exact MPGs (but may still be ordinal
or weighted MPGs) due to the dependence of both the rewards and the
transitions on agents’ decisions. From our current perspective, ordinal and
weighted MPGs (as defined in Remark 1) remain relevant, since as we argue,
policy gradient still converges to Nash policies in these classes of games
(see Remark 5).

#### Independent Policy Gradient and Direct Parameterization

We assume that all agents update their policies _independently_ according to
the _projected gradient ascent (PGA)_ or _policy gradient_ algorithm on their
policies. Independence here refers to the fact that (PGA) requires only local
information (each agent’s own rewards, actions and view of the environment) to
form the updates, i.e., to estimate that agent’s policy gradients. Such
protocols are naturally motivated and particularly suitable for distributed AI
settings in which all information about the interacting agents, the type of
interaction and the agent’s actions (policies) is encoded in the environment
of each agent.333In practice, even though every agent treats their environment
as fixed, the environment changes as other agents update their policies. This
is what makes the analysis of such protocols particularly challenging in full
generality. It also highlights the importance of studying classes of games
(MDPs) in which convergence of independent learning protocols can be obtained
such as zero-sum stochastic games [11] or MPGs as we do in this paper.

The PGA algorithm is given by

$\pi_{i}^{(t+1)}:=P_{\Delta(\mathcal{A}_{i})^{S}}\left(\pi_{i}^{(t)}+\eta\nabla_{\pi_{i}}V^{i}_{\rho}(\pi^{(t)})\right),$
(PGA)

for each agent $i\in\mathcal{N}$, where $P_{\Delta(\mathcal{A}_{i})^{S}}$ is
the projection onto $\Delta(\mathcal{A}_{i})^{S}$ in the Euclidean norm. We
also assume that all players $i\in\mathcal{N}$ use direct policy
parameterizations, i.e.,

$\pi_{i}(a\mid s)=x_{i,s,a}$ (2)

with $x_{i,s,a}\geq 0$ for all $s\in\mathcal{S},a\in\mathcal{A}_{i}$ and
$\sum_{a\in\mathcal{A}_{i}}x_{i,s,a}=1$ for all $s\in\mathcal{S}$. This
parameterization is complete in the sense that any stochastic policy can be
represented in this class [1].

In practice, agents use _projected stochastic gradient ascent_ (PSGA),
according to which, the actual gradient,
$\nabla_{\pi_{i}}V_{\rho}^{i}(\pi^{(t)})$, is replaced by an estimate thereof
that is calculated from a randomly selected (yet finite) sample of
trajectories of the MDP. This estimate, $\hat{\nabla}_{\pi_{i}}^{(t)}$ may be
derived from a single or a batch of observations which in expectation behave
as the actual gradient. We choose the estimate of the gradient of
$V^{i}_{\rho}$ to be

$\hat{\nabla}_{\pi_{i}}^{(t)}=R^{(T,t)}_{i}\sum_{k=0}^{T}\nabla\log\pi_{i}(a_{k}^{(t)}\mid
s_{k}^{(t)}),$ (3)

where $s_{0}^{t}\sim\rho$, and $R^{(T,t)}_{i}=\sum_{k=0}^{T}r^{k}_{i,t}$ is
the sum of rewards of agent $i$ for a batch of time horizon $T$ along the
trajectory generated by the stochastic gradient ascent algorithm at its $t$-th
iterate (recall that the discount factor, $\gamma$, functions as the
probability to continue at each step, so $T$ is sampled from a geometric
distribution).

The direct parameterization is not sufficient to ensure that the variance of
the gradient estimator is bounded (as policies approach the boundary). In this
case, we will require that each agent $i\in\mathcal{N}$ uses instead direct
parameterization with $\alpha$-greedy exploration as follows

$\pi_{i}(a\mid s)=(1-\alpha)x_{i,s,a}+\alpha/A_{i},$ (4)

where $\alpha$ is the exploration parameter for all agents. Under
$\alpha$-greedy exploration, it can be shown that (3) is unbiased and has
bounded variance (see Lemma 4.6). The form of PSGA is

$\pi_{i}^{(t+1)}:=P_{\Delta(\mathcal{A}_{i})^{S}}\left(\pi_{i}^{(t)}+\eta\hat{\nabla}_{\pi_{i}}^{(t)}\right).$
(PSGA)

##  3 Structural Properties of Markov Potential Games

#### Existence of Deterministic Nash Policies.

The first question that we examine, is whether MPGs possess a _deterministic_
Nash policy profile, as is the case in normal-form potential games [22]. In
Theorem 3.1, we show that this important property indeed carries over (which
settles part (a) of informal Theorem 1.2).

######  Theorem 3.1 (Deterministic Nash Policy Profile).

Let $\mathcal{G}$ be a Markov Potential Game (MPG). Then, there exists a Nash
policy $\pi^{*}\in\Delta(\mathcal{A})^{S}$ which is deterministic, i.e., for
each agent $i\in\mathcal{N}$ and each state $s\in\mathcal{S}$, there exists an
action $a_{i}\in\mathcal{A}_{i}$ so that $\pi_{i}^{*}(a_{i}\mid s)=1$.

The proof of Theorem 3.1 (which is deferred to Appendix B) exploits the fact
that we can iteratively reduce the non-deterministic components of an
arbitrary Nash policy profile that corresponds to a global maximizer of the
potential and still retain the Nash profile property at all times. At each
iteration, we isolate an agent $i\in\mathcal{N}$, and find a deterministic
(optimal) policy for that agent in the (single-agent) MDP in which the
policies of all other agents but $i$ remain fixed. The important observation
is that the resulting profile is again a global maximizer of the potential and
hence, a Nash policy profile. This argument critically relies on the MPG
structure and does not seem directly generalizable to MDPs that do not satisfy
Definition 2.

#### Sufficient Conditions for MPGs.

We next turn to the question of which types of games are captured by
Definition 2. It is tempting to think that MDPs which are potential at every
state (meaning that the immediate rewards at every state are captured by a
(normal-form) potential game at that state) are trivially MPGs. As we show in
Examples 1 and 2, this intuition fails in the most straightforward way: we can
construct simple MDPs that are potential at every state but which are purely
competitive (do not possess a deterministic Nash policy) overall (Example 1)
or which are cooperative in nature overall but which do not possess an exact
potential function (Example 2).

######  Example 1.

Consider the two-agent, two-state, and two actions per state MDP,
$\mathcal{G}=\left(\mathcal{S}=\\{0,1\\},\mathcal{N}=\\{A,B\\},(\mathcal{A}_{i}=\\{0,1\\},R_{i})_{i\in\mathcal{N}},P,\rho\right)$
in Figure 2. At state $0$ ($1$), agent A always receives $+2$ ($0$) and agent
B always receives $0$ ($+2$) regardless of the actions they choose. That is,
the reward functions for both states are constant, which implies that both
states are potential games. The transitions are determinstic and are given by

$s_{t+1}=s_{t}\oplus a^{s_{t}}_{A}\oplus a^{s_{t}}_{B},$

where $\oplus$ denotes the xor operator or equivalently, addition modulo $2$,
i.e., $1\oplus 1=0$. The MDP $\mathcal{G}$ is illustrated in Figure 2.

To show that $\mathcal{G}$ is not a MPG, it suffices to show that it cannot
have a deterministic Nash policy as should be the case according to Theorem
3.1. To obtain a contradiction, assume that agent $A$ is using a deterministic
action $a_{A}^{0}\in\\{0,1\\}$ at state $0$. Then, agent $B$, who prefers to
move to state $1$, will optimize their utility by choosing the action
$a^{0}_{B}\in\\{0,1\\}$ that yields $a^{0}_{A}\oplus a_{B}^{0}=1$. In other
words, given any deterministic action of agent $A$ at state $0$, agent $B$ can
choose an action that always moves the sequence of play to state $1$. Thus,
such an action cannot be optimal for agent $A$ which implies that the MDP
$\mathcal{G}$ does not have a deterministic Nash policy profile as claimed.

Intuitively, the two agents in Example 1 play a game of _matching pennies_ in
terms of the actions that they choose (since they prefer playing in opposing
states). Thus, competition arises due to the opposing preferences of the
agents over states even though the immediate rewards at each states are
determined by normal form potential games.

Example 2 shows that a state-based potential game may fail to be a MPG even if
agents have similar preferences over states. In that case, the reason is that
one cannot find an exact potential function due to the dependence of the
transitions on agents’ actions. However, in the case of Example 2, it is
straightforward to show that the game is an ordinal potential game, cf. Remark
2.

######  Example 2.

Consider the two-agent, two-state MDP,
$\mathcal{G}=(\mathcal{S}=\\{0,1\\},\mathcal{N}=\\{A,B\\},\\{\mathcal{A}_{i},$
$R_{i}\\}_{i\in\mathcal{N}},P,\rho)$ in Figure 2. At state $s_{0}$, each agent
has two actions, $\mathcal{A}_{i}=\\{0,1\\}$, whereas at state $s_{1}$, each
agent has a single action. The transitions and instantaneous rewards,
$(R_{A}(s,\mathbf{a}),R_{B}(s,\mathbf{a})),s=0,1,\mathbf{a}=(a^{s}_{A},a^{s}_{B})$
of this MDP are shown in Figure 2. If the action profile
$\mathbf{a}=(a^{0}_{A},a^{0}_{B})=(0,0)$ is selected at state $s_{0}$, then
the play remains there, otherwise the play transitions to state $s_{1}$ and
remains there forever.

$s_{0}$$\bordermatrix{~{}&0&1\cr 0&2,0&2,0\cr
1&2,0&2,0\cr}$$s_{1}$$\bordermatrix{~{}&0&1\cr 0&0,2&0,2\cr
1&0,2&0,2\cr}$$a^{0}_{A}\oplus a^{0}_{B}=0$otherwiseotherwise$a^{1}_{A}\oplus
a^{1}_{B}=0$

Figure 1: A MDP which is potential at every state but which is not a MPG due
to conflicting preferences over states. The agents’ instantaneous rewards,
$(R_{A}(s,\mathbf{a}),R_{B}(s,\mathbf{a}))$, are in matrix form below each
state $s=0,1$.

0.99 $s_{0}$$\bordermatrix{~{}&0&1\cr 0&\phantom{-}5,\phantom{-}2&-1,-2\cr
1&-5,-4&\phantom{-}1,\phantom{-}4\cr}$$s_{1}$$(0,0)$$(a_{A}^{0},a_{B}^{0})=(0,0)$otherwise

Figure 2: A MDP which is potential at every state and cooperative in nature
but which is not a MPG. The action-dependent transitions do not allow the
derivation of an exact potential function.

Since, the game at $s_{0}$ is a version of the Battle of the Sexes and hence a
potential game (see also Section B.1), there exists a potential function
$\phi_{0}$, such that we may write the instantaneous reward,
$R_{i}(s_{0},\mathbf{a})$ of agent $i=A,B$ at that state as the sum of the
potential, $\phi_{0}(\pi)$ (common term) and a dummy term,
$u^{i}_{0}(\pi_{-i})$, which does not depend on the action (policy) of agent
$i$, but only on the action (policy) of agent $-i$, i.e.,
$R_{i}(s_{0},\pi)=\phi_{0}(\pi)+u^{i}_{0}(\pi_{-i})$, for $i=A,B$. Here we are
using the slight abuse of notation that
$R_{i}(s,\pi)=\operatorname{\mathbb{E}}_{\mathbf{a}\sim\pi}R_{i}(s,\mathbf{a})$.
This leads (after some standard algebra) to the following expression for the
value function $V_{0}^{i}(\pi)$ of agent $i=A,B$ with starting state $s_{0}$

$\displaystyle V_{0}^{i}(\pi)$ $\displaystyle=\frac{\phi_{0}(\pi)}{1-\gamma
pq}+\frac{u_{i}(\pi_{-i})}{1-\gamma pq},\quad\text{for }i=A,B,$

where $p,q\in[0,1]$ are the probabilities with which agents $A$ and $B$
respectively select their action $0$ at state $s_{0}$. This expression clearly
indicates the complexity that emerges in MPGs versus static games. Namely, the
first term of the value function is a common term (same for both agents) that
can conveniently become part of a potential function. However, the second term
is a mixture of a common term (denominator) and a term that is different for
each agent (numerator). The reason is that the policy of each agent determines
the time that the agents spend at each state and thus, it does not (generally)
allow for an agent independent term (as required by the definition of a
potential game). However, this game is clearly a _potential-like game_ in
which agents have common interests. This motivates to look at the notion of
ordinal or weighted MPGs. Note that (by a straightforward calculation) this
game is an ordinal MPG for the potential function $\Phi_{s}=\phi_{s}$ for
$s=0,1$.

Based on the intuition from the previous Examples, we formulate the following
sufficient conditions in Proposition 3.2 which ensure that a state based
potential game (i.e., a game that is potential at every state) is also a MPG
according to Definition 2 (cf. Theorem 1.2 part (c)).

######  Proposition 3.2 (Sufficient Conditions for MPGs).

Consider a MDP $\mathcal{G}$ in which every state $s\in\mathcal{S}$ is a
potential game, i.e., the immediate rewards
$R(s,\mathbf{a})=(R_{i}(s,\mathbf{a}))_{i\in\mathcal{N}}$ for each state
$s\in\mathcal{S}$ are captured by the utilities of a (normal-form) potential
game with potential function $\phi_{s}$. Additionally, assume that one of the
following conditions holds

  * C1.

Agent-Independent Transitions: $P(s^{\prime}\mid s,\mathbf{a})$ does not
depend on $\mathbf{a}$, that is, $P(s^{\prime}\mid
s,\mathbf{a})=P(s^{\prime}\mid s)$ is just a function of the present state for
all states $s,s^{\prime}\in\mathcal{S}$.

  * C2.

Equality of Individual Dummy Terms: $P(s^{\prime}\mid s,\mathbf{a})$ is
arbitrary but the dummy terms of each agent’s immediate rewards are equal
across all states, i.e., there exists a function
$u_{s}^{i}:\mathcal{A}_{-i}\to\mathbb{R}$ such that
$R_{i}(s,a_{i},\mathbf{a}_{-i})=\phi_{s}(a_{i},\mathbf{a}_{-i})+u_{s}^{i}(\mathbf{a}_{-i})$,
and

$\nabla_{\pi_{i}(s)}\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum\nolimits_{t=0}^{\infty}\gamma^{t}u_{s_{t}}^{i}(\mathbf{a}_{-i,t})\mid
s_{0}=s^{\prime}\right]=c_{s}\mathbf{1},$

for all states $s^{\prime},s\in\mathcal{S}$, where $c_{s}\in\mathbb{R}$ and
$\mathbf{1}\in\mathbb{R}^{A_{i}}$, where $\pi_{i}(s)$ corresponds to the
policy distribution of agent $i$ at state $s$.

If either C1 or C2 are true, then $\mathcal{G}$ is a MPG.

######  Remark 2.

As the rest of the proofs of Section 3, the proof of Proposition 3.2 is
provided in Appendix B. The following remarks are due.

  1. 1.

Condition C1 can also be viewed as a special case of condition C2. However,
due to its simplicity, it is more instructive to state C1 separately.
Condition C2 (or variations of it) are already present in existing studies of
potential-like MDPs [18, 33]. Example 2 shows that such conditions are
restrictive, in the sense that they do not capture very simple MDPs that
intuitively have a potential-like (cooperative) structure. This motivates the
study of ordinal or weighted potential games as natural models to capture such
cases. As we show, our convergence results about independent policy gradient
naturally extend to these classes as well (see Remark 5).

  2. 2.

Condition C2 is (trivially) satisfied when $u^{i}_{s}$ does not depend on the
state $s$ nor on the actions of other agents, i.e.,
$u^{i}_{s}(\mathbf{a}_{-i})\equiv c^{i}$ for some constant
$c^{i}\in\mathbb{R}$ for all $\mathbf{a}_{-i}\in\mathcal{A}_{-i}$ and all
$s\in\mathcal{S}$. A special case is provided by MDPs in which the
instantaneous rewards of all agents are the same at each state, i.e., such
that $R_{i}(s,a_{i},\mathbf{a}_{-i})=\phi_{s}(a_{i},\mathbf{a}_{-i})$ for all
agents $i\in\mathcal{N}$, all actions $a_{i}\in\mathcal{A}_{i}$ and all states
$s\in\mathcal{S}$. MDPs that satisfy this condition form a subclass of the
current definition and have been studied under the name _Team Markov Games_ in
[36].

The previous discussion focuses on games that are potential at every state as
natural candidates to generalize the notion of normal-form games to state
games. This leaves an important question unanswered: are there games which are
not potential at every state but which are captured by the our current
definition of MPGs? Example 3 answers this question in the affirmative.
Together with Example 1, this settles the claim in Theorem 1.2, part (b).

######  Example 3 (Not potential at every state may still imply MPG).

Consider the 2-agent MDP of Figure 3.

0.7 $s_{0}$$\bordermatrix{~{}&H&T\cr H&\phantom{-}1,-1&-1,\phantom{-}1\cr
T&-1,\phantom{-}1&\phantom{-}1,-1\cr}$$s_{HH}$$\left(\frac{1}{\gamma},-\frac{1}{\gamma}\right)$$s_{HT}$$\left(-\frac{1}{\gamma},\frac{1}{\gamma}\right)$$s_{TH}$$\left(-\frac{1}{\gamma},\frac{1}{\gamma}\right)$$s_{TT}$$\left(\frac{1}{\gamma},-\frac{1}{\gamma}\right)$$s_{1}$$\bordermatrix{~{}&L&R\cr
L&(1,1)&(9,0)\cr R&(0,9)&(6,6)\cr}$$p_{0}$$1-p_{0}$

Figure 3: A $2$-player MPG which is not potential at every state. The rewards
in state $s_{1}$ form a potential game, whereas the rewards in $s_{0}$ do not.
However, the states inside the dotted rectangle do form a potential game and
this can be leveraged to show that the whole MPG is a potential game whenever
$p_{0}$ does not depend on agents’ actions.

At state $s_{0}$, agents’ rewards,
$(R_{1}(s_{0},\mathbf{a}),R_{2}(s_{0},\mathbf{a}))$ form a constant sum
(equivalent to zero-sum) game. The agents’ actions at $s_{0}$ induce a
deterministic transition to a state $s_{ab}$ with $a,b\in\\{H,T\\}$ in which
the only available actions are precisely the chosen actions at $s_{0}$. Each
agent’s instantaneous reward at this state is the reward of the other agent at
$s_{0}$ (scaled by $1/\gamma$). The MDP then transitions deterministically to
state $s_{1}$ which is a potential game with rewards
$(R_{1}(s_{1},\mathbf{a}),R_{2}(s_{1},\mathbf{a}))$. After the agents select
their actions at $s_{1}$, there is an exogenous given probability, $p_{0}$,
according to which the play transitions to state $s=0$. Otherwise it remains
at $s_{1}$.

While the game at state $s=0$ is not a potential game, the combined states in
the dotted rectangle of Figure 3 do form a potential game, with potential
function equal to the sum of the agent’s payoffs at $s_{0}$ (the rewards of
both agents are equal for every pass of the play through the states in the
dotted rectangle). Thus, it is not hard to see that both value functions are
of the form

$V_{s}^{i}\left(\pi_{1},\pi_{2}\right)=c_{1}\left(s\right)\cdot\mathbf{x}_{0}\left(R_{1}(s_{0},\mathbf{a})+R_{2}(s_{0},\mathbf{a})\right)\mathbf{y}_{0}+c_{2}\left(s\right)\cdot\mathbf{x}_{1}R_{i}(s_{1},\mathbf{a})\mathbf{y}_{1},$

for $s\in\\{s_{0},s_{1}\\}$ and $i=\\{1,2\\}$, where
$c_{1}\left(s\right),c_{2}\left(s\right)>0$ are appropriate constants that
depend only the state $s\in\\{s_{0},s_{1}\\}$ and not on the agents. Since the
game at $s_{1}$ is a potential game, with potential function given by a
$2\times 2$ matrix $\phi_{1}$, it is immediate to see that

$\Phi_{s}\left(\pi_{1},\pi_{2}\right):=c_{1}\left(s\right)\mathbf{x}_{0}\left(R_{1}(s_{0},\mathbf{a})+R_{2}(s_{0},\mathbf{a})\right)\mathbf{y}_{0}+c_{2}\left(s\right)\cdot\mathbf{x}_{1}\phi_{1}\mathbf{y}_{1},\text{for
}s\in\\{s_{0},s_{1}\\}$

is a potential function so that $\mathcal{G}$ satisfies the definition of an
MPG.

##  4 Convergence of Policy Gradient in Markov Potential Games

The current section presents the proof of convergence of (projected) policy
gradient to approximate Nash policies in Markov Potential Games (MPGs). We
analyze the cases of both infinite and finite samples using direct and
$\alpha$-greedy parameterizations, respectively.

Before we proceed with the formal statements and proofs of this section, we
provide the commonly used definition of distribution mismatch coefficient [14]
applied to our setting.

######  Definition 3 (Distribution Mismatch coefficient).

Let $\mu$ be any distribution in $\Delta(\mathcal{S})$ and let $\mathcal{O}$
be the set of policies $\pi\in\Delta(\mathcal{A})^{S}$. We call

$D:=\max_{\pi\in\mathcal{O}}\left\|\frac{d^{\pi}_{\mu}}{\mu}\right\|_{\infty}$

the _distribution mismatch coefficient_ , where $d^{\pi}_{\mu}$ is the
discounted state distribution (17).

The first auxiliary Lemma has to do with the projection operator that is used
on top of the independent policy gradient, so that the policy vector
$\pi^{(t)}_{i}$ remains a probability distribution for all agents
$i\in\mathcal{N}$ (see (PGA)). It is not hard to show (due to separability)
that the projection operator being applied independently for each agent $i$ on
$\Delta(\mathcal{A}_{i})^{S}$ is the same as jointly applying projection on
$\Delta(\mathcal{A})^{S}$. This is the statement of Lemma 4.1.

######  Lemma 4.1 (Projection Operator).

Let $\pi:=(\pi_{1},...,\pi_{n})$ be the policy profile for all agents and let

$\pi^{\prime}=\pi+\eta\nabla_{\pi}\Phi_{\rho}(\pi),$

be a gradient step on the potential function for a step-size $\alpha>0$. Then,
it holds that

$P_{\Delta(\mathcal{A})^{S}}(\pi^{\prime})=(P_{\Delta(\mathcal{A}_{1})^{S}}(\pi^{\prime}_{1}),\dots,P_{\Delta(\mathcal{A}_{n})^{S}}(\pi^{\prime}_{n})).$

The main implication of Lemma 4.1 along with the equality of the derivatives
between value functions and the potential function in MPGs, i.e.,
$\nabla_{\pi_{i}}V_{s}^{i}(\pi)=\nabla_{\pi_{i}}\Phi(\pi)$ for all
$i\in\mathcal{N}$ (see property P2 in Proposition B.1), is that running
independent (PGA) on each agent’s value function is equivalent to running
(PGA) on the potential function $\Phi$. In turn, Lemma 4.2 suggests that as
long as policy gradient reaches a point $\pi^{(t)}$ with small gradient along
the directions in $\Delta(\mathcal{A})^{S}$, it must be the case that
$\pi^{(t)}$ is an approximate Nash policy. Together with Lemma 4.1, this will
be sufficient to prove convergence of (PGA).

#### Stationary point of $\Phi$.

To proceed, we need the formal definition of a stationary point for the
potential function $\Phi$ which is given below.

######  Definition 4 ($\epsilon$-Stationary Point of $\Phi$).

A policy profile $\pi:=(\pi_{1},...,\pi_{n})\in\Delta(\mathcal{A})^{S}$ is
called $\epsilon$-stationary for $\Phi$ w.r.t distribution $\mu$ as long as

$\max_{(\pi_{1}+\delta_{1},\dots,\pi_{n}+\delta_{n})\in\Delta(\mathcal{A})^{S},\sum_{i\in\mathcal{N}}\left\|\delta_{i}\right\|^{2}_{2}\leq
1}\sum_{i\in\mathcal{N}}\delta_{i}^{\top}\nabla_{\pi_{i}}\Phi_{\mu}(\pi)\leq\epsilon$
(5)

In words, the function $\Phi(\pi)$ cannot increase in value by more than
$\epsilon$ along every possible local direction
$\delta=(\delta_{1},\dots,\delta_{n})$ that is feasible (namely $\pi+\delta$
is also a policy profile).

######  Lemma 4.2 (Stationarity of $\Phi$ implies Nash).

Let $\epsilon\geq 0$, and let $\pi$ be an $\epsilon$-stationary point of
$\Phi$ (see Definition 4). Then, it holds that $\pi$ is a
$\frac{\sqrt{S}D\epsilon}{1-\gamma}$-Nash policy.

To prove Lemma 4.2, we will need the Gradient Domination property that has
been shown to hold in single-agent MDPs [1]. This is presented in Lemma 4.3.

######  Lemma 4.3 (Agent-wise Gradient Domination Property in MPGs [1]).

Let $\mathcal{G}$ be a MPG with potential function $\Phi$, fix any agent
$i\in\mathcal{N}$, and let $\pi=(\pi_{i},\pi_{-i})\in\Delta(\mathcal{A})^{S}$
be a policy. Let $\pi_{i}^{*}$ be an optimal policy for agent $i$ in the
single agent MDP in which the rest of the agents are fixed to choose
$\pi_{-i}.$ Then, for the policy
$\pi^{*}=(\pi^{*}_{i},\pi_{-i})\in\Delta(\mathcal{A})^{S}$ that differs from
$\pi$ only in the policy component of agent $i$, it holds that

$\Phi_{\rho}(\pi^{*})-\Phi_{\rho}(\pi)\leq\frac{1}{1-\gamma}\left\|\frac{d^{\pi^{*}}_{\rho}}{\mu}\right\|_{\infty}\max_{\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i})}(\pi^{\prime}-\pi)^{\top}\nabla_{\pi_{i}}\Phi_{\mu}(\pi),$

for any distributions $\mu,\rho\in\Delta(\mathcal{S})$.

######  Remark 3 (Best Response).

Intuitively, Lemma 4.3 implies that there is a _best response_ structure in
the agents’ updates that we can exploit to show convergence of (projected)
policy gradient to a Nash policy profile. In particular, given a fixed policy
profile of all agents other than $i$, the decision of agent $i$ is equivalent
to the decision of that agent in a single MDP. Thus, the following inequality
(which stems directly from the gradient domination property in the single MDP)

$V^{i}_{s}(\pi^{*})-V^{i}_{s}(\pi)\leq\frac{1}{1-\gamma}\left\|\frac{d^{\pi^{*}}_{s}}{\mu}\right\|_{\infty}\max_{\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i})}(\pi^{\prime}-\pi)^{\top}\nabla_{\pi_{i}}V^{i}_{\mu}(\pi)$

implies that any stationary point of $V_{s}^{i}$ (w.r.t the variables
$x_{i,s,a}$ of agent’s $i$ policy with the rest of the variables being fixed)
is an optimal policy for $i$, i.e., a best response given the policies of all
other agents.

Lemma 4.3 also suggests that there is an important difference in the Gradient
Domination Property between (multi-agent) MPGs and single agent MDPs (cf.
Lemma 4.1 in [1]). Specifically, for MPGs, the value (of each agent) at
different Nash policies may not be unique444This is in contrast to single-
agent MDPs for which the agent has a unique optimal value even though their
optimal policy may not necessarily be unique. which implies that the gradient
domination property, as stated in Lemma 4.3, will only be enough to guarantee
convergence to _one of_ the optimal (stationary) points of $\Phi$ (and not
necessarily to the absolute maximum of $\Phi$). Having all these in mind, we
can now prove Lemma 4.2.

###### Proof of Lemma 4.2.

Fix agent $i$ and suppose that $i$ deviates to an optimal policy $\pi^{*}_{i}$
(w.r.t the corresponding single agent MDP). Since $\pi$ is
$\epsilon$-stationary it holds that (Definition 4)

$\max_{\pi^{\prime}_{i}\in\Delta(\mathcal{A}_{i})^{S}}(\pi^{\prime}_{i}-\pi_{i})^{\top}\nabla_{\pi_{i}}\Phi_{\mu}(\pi)\leq\sqrt{S}\epsilon.$
(6)

Thus, with $\pi^{*}=(\pi^{*}_{i},\pi_{-i})$, Lemma 4.3 implies that

$\begin{split}\Phi_{\rho}(\pi^{*})-\Phi_{\rho}(\pi)&\leq\frac{1}{1-\gamma}\left\|\frac{d^{\pi^{*}}_{\rho}}{\mu}\right\|_{\infty}\max_{\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i})}(\pi^{\prime}-\pi)^{\top}\nabla_{\pi_{i}}\Phi_{\mu}(\pi)\\\
&\stackrel{{\scriptstyle(\ref{eq:helpm})}}{{\leq}}\frac{D}{1-\gamma}\sqrt{S}\epsilon.\end{split}$
(7)

Thus, using the definition of the potential function (cf. Definition 2), we
obtain that

$V^{i}_{\rho}(\pi^{*})-V^{i}_{\rho}(\pi)=\Phi_{\rho}(\pi^{*})-\Phi_{\rho}(\pi)\leq\frac{\sqrt{S}D\epsilon}{1-\gamma}\,.$

Since the choice of $i$ was arbitrary, we conclude that $\pi$ is an
$\frac{\sqrt{S}D\epsilon}{1-\gamma}$-approximate Nash policy. ∎

The last critical step before we proceed to the formal statement and proof of
Theorem 1.1 is that the potential function $\Phi$ is smooth. This fact is used
in the analysis of both (PGA) and its stochastic counterpart (PSGA).

######  Lemma 4.4 (Smoothness of $\Phi$).

Let $A_{\max}:=\max_{i\in\mathcal{N}}|\mathcal{A}_{i}|$ (the maximum number of
actions for some agent). Then, for any initial state $s_{0}\in\mathcal{S}$
(and hence for every distribution $\mu\in\Delta(\mathcal{S})$ on states) it
holds that

$\left\|\nabla_{\pi}\Phi_{s_{0}}(\pi)-\nabla_{\pi}\Phi_{s_{0}}(\pi^{\prime})\right\|_{2}\leq\frac{2n\gamma
A_{\max}}{(1-\gamma)^{3}}\left\|\pi-\pi^{\prime}\right\|_{2}$ (8)

i.e., $\Phi_{\mu}(\pi)$ is $\frac{2n\gamma A_{\max}}{(1-\gamma)^{3}}$-smooth.

Importantly, $A_{\max}:=\max_{i\in\mathcal{N}}|\mathcal{A}_{i}|$, i.e., the
maximum number of actions for some agent, scales _linearly_ in the number of
agents.

#### Exact gradients case.

We are now ready to prove Theorem 1.1 (restated formally), following standard
arguments about (PGA). Recall that the global maximum among all
values/utilities of agents must be at most one.

######  Theorem 4.5 (Formal Theorem 1.1, part (a)).

Let $\mathcal{G}$ be a MPG and consider an arbitrary initial state. Let also
$A_{\max}=\max_{i}|\mathcal{A}_{i}|$, and set the number of iterations to be
$T=\frac{16n\gamma D^{2}SA_{\max}\Phi_{\max}}{(1-\gamma)^{5}\epsilon^{2}}$ and
the learning rate (step-size) to be $\eta=\frac{(1-\gamma)^{3}}{2n\gamma
A_{\max}}$. If the agents run independent projected policy gradient (PGA)
starting from arbitrarily initialized policies, then there exists a
$t\in\\{1,\dots,T\\}$ such that $\pi^{(t)}$ is an $\epsilon$-approximate Nash
policy.

###### Proof.

The first step is to show that $\Phi$ is a $\beta$-smooth function, in
particular, that $\nabla_{\pi}\Phi$ is $\beta$-Lipschitz with
$\beta=\frac{2n\gamma A_{\max}}{(1-\gamma)^{3}}$ as established in Lemma 4.4.
Then, a standard _ascent lemma_ for Gradient Ascent (see Lemma D.1 from [6])
implies that for any $\beta$-smooth function $f$ it holds that
$f(x^{\prime})-f(x)\geq\frac{1}{2\beta}\left\|x^{\prime}-x\right\|^{2}_{2}$
where $x^{\prime}$ is the next iterate of (PGA). Applied to our setting, this
gives

$\Phi_{\mu}(\pi^{(t+1)})-\Phi_{\mu}(\pi^{(t)})\geq\frac{(1-\gamma)^{3}}{4n\gamma
A_{\max}}\left\|\pi^{(t+1)}-\pi^{(t)}\right\|_{2}^{2}$ (9)

Thus, if the number of iterates, $T$, is $\frac{16n\gamma
D^{2}SA_{\max}}{(1-\gamma)^{5}\epsilon^{2}}$, then there must exist a $1\leq
t\leq T$ so that
$\left\|\pi^{(t+1)}-\pi^{(t)}\right\|_{2}\leq\frac{\epsilon(1-\gamma)}{2D\sqrt{S}}$.
Using a standard approximation property (see Lemma D.2), we then conclude that
$\pi^{(t+1)}$ will be a $\frac{\epsilon(1-\gamma)}{D\sqrt{S}}$-stationary
point for the potential function $\Phi$. Hence, by Lemma 4.2, it follows that
$\pi^{(t+1)}$ is an $\epsilon$-Nash policy and the proof is complete. ∎

#### Finite sample case.

In the case of finite samples, we analyze (PSGA) on the value $V^{i}$ of each
agent $i$ which (as was the case for PGA) can be shown to be the same as
applying projected gradient ascent on $\Phi$. The key is to get an estimate of
the gradient of $\Phi$ (3) at every iterate. Note that $1-\gamma$ now captures
the probability for the MDP to terminate after each round (and it does not
play the role of a discounted factor since we consider finite length
trajectories). Lemma 4.6 argues that the estimator of equation (3) is both
unbiased and bounded.

######  Lemma 4.6 (Unbiased estimator with bounded variance).

It holds that $\hat{\nabla}_{\pi_{i}}^{(t)}$ is an unbiased estimator of
$\nabla_{\pi_{i}}\Phi$ for all $i\in\mathcal{N}$, that is

$\mathbb{E}_{\pi^{(t)}}\hat{\nabla}_{\pi_{i}}^{(t)}=\nabla_{\pi_{i}}\Phi_{\mu}(\pi^{(t)})\textrm{
for all }i\in\mathcal{N}.$

Moreover, for all agents $i\in\mathcal{N}$, it holds that

$\mathbb{E}_{\pi^{(t)}}\left\|\hat{\nabla}_{\pi_{i}}^{(t)}\right\|_{2}^{2}\leq\frac{24A_{\max}^{2}}{\epsilon(1-\gamma)^{4}},\textrm{
for all }i\in\mathcal{N}.$

###### Proof.

It is straightforward from Lemma D.4 and the equality of the partial
derivatives between the value functions and the potential, i.e.,
$\nabla_{\pi_{i}}\Phi_{\mu}=\nabla_{\pi_{i}}V^{i}_{\mu}$ for all
$i\in\mathcal{N}$ (see property P2 in Proposition B.1). ∎

We now state and prove part (b) of Theorem 1.1.

######  Theorem 4.7 (Formal Theorem 1.1, part (b)).

Let $\mathcal{G}$ be a MPG and consider an arbitrary initial state. Let
$A_{\max}=\max_{i}|\mathcal{A}_{i}|$, and set the number of iterations to be
$T=\frac{48(1-\gamma)A_{\max}\Phi_{\max}D^{4}S^{2}}{\epsilon^{6}\gamma^{3}}$
and the learning rate (step-size) to be
$\eta=\frac{\epsilon^{4}(1-\gamma)^{3}\gamma}{48nD^{2}A^{2}_{\max}S}$. If the
agents run projected stochastic policy gradient (PSGA) starting from
arbitrarily initialized policies and using $\alpha$-greedy parametrization
with $\alpha=\epsilon^{2}$, then there exists a $t\in\\{1,\dots,T\\}$ such
that in expectation, $\pi^{(t)}$ is an $\epsilon$-approximate Nash policy.

###### Proof.

Let $\delta_{t}=\hat{\nabla}_{\pi}^{(t)}-\nabla_{\pi}\Phi_{\mu}(\pi^{(t)})$
and set $\lambda=\frac{(1-\gamma)^{3}}{2n\gamma A_{\max}}$ (the inverse of the
smooth parameter in 4.4). Moreover, we set
$y^{(t+1)}=P_{\Delta(\mathcal{A})^{S}}(\pi^{(t)}+\eta\nabla_{\pi}\Phi(\pi^{(t)}))$
($y^{(t+1)}$ captures the next iterate of the projected (deterministic)
gradient ascent).

We follow the analysis of Projected Stochastic Gradient Ascent for non-convex
smooth-functions (see [12], Theorem 2.1) that makes use of the Moreau
envelope. Let

$\phi_{\lambda}(x)=\operatorname*{argmin}_{y\in\Delta(\mathcal{A})^{S}}\left\\{-\Phi_{\mu}(y)+\frac{1}{\lambda}\left\|x-y\right\|_{2}^{2}\right\\},$

(definition of Moreau envelope for our objective $\Phi$). From the definition
of $\phi$ and a standard property of projection we get

$\begin{split}\phi_{\lambda}(\pi^{(t+1)})&\leq-\Phi_{\mu}(y^{(t+1)})+\frac{1}{\lambda}\left\|\pi^{(t+1)}-y^{(t+1)}\right\|_{2}^{2}\\\
&\leq-\Phi_{\mu}(y^{(t+1)})+\frac{1}{\lambda}\left\|\pi^{(t)}+\eta\hat{\nabla}_{\pi}^{(t)}-y^{(t+1)}\right\|_{2}^{2}\\\
&=-\Phi_{\mu}(y^{(t+1)})+\frac{1}{\lambda}\left\|\pi^{(t)}-y^{(t+1)}\right\|_{2}^{2}+\frac{\eta^{2}}{\lambda}\left\|\hat{\nabla}_{\pi}^{(t)}\right\|_{2}^{2}+\frac{2\eta}{\lambda}(\pi^{(t)}-y^{(t+1)})^{\top}\hat{\nabla}_{\pi}^{(t)}\end{split}$
(10)

Since $\hat{\nabla}_{\pi}^{(t)}$ is unbiased (Lemma 4.6) we have that
$\mathbb{E}[\delta_{t}|\pi^{(t)}]=0$, therefore
$\mathbb{E}\left[\delta^{\top}_{t}(y^{(t+1)}-\pi^{(t)})\right]=0.$
Additionally, by Lemma 4.6 (applied for all agents $i$) we also have
$\mathbb{E}\left[\left\|\hat{\nabla}_{\pi}^{(t)}\right\|_{2}^{2}\right]\leq\frac{24nA^{2}_{\max}}{\epsilon(1-\gamma)^{4}}.$
Hence by taking expectation on (10) we have:

$\mathbb{E}[\phi_{\lambda}(\pi^{(t+1)})]\leq\mathbb{E}\left[-\Phi_{\mu}(y^{(t+1)})+\frac{1}{\lambda}\left\|\pi^{(t)}-y^{(t+1)}\right\|_{2}^{2}\right]+\frac{2\eta}{\lambda}\mathbb{E}[(\pi^{(t)}-y^{(t+1)})^{\top}\nabla_{\pi}\Phi_{\mu}(\pi^{(t)})]+\frac{24\eta^{2}nA^{2}_{\max}}{\lambda\epsilon(1-\gamma)^{4}}.$

Using the definition of Moreau envelope and the fact that $\Phi$ is
$\frac{1}{\lambda}$-smooth (Lemma 4.4, after the parametrization, the
smoothness parameter does not increase) we conclude that

$\begin{split}\mathbb{E}[\phi_{\lambda}(\pi^{(t+1)})]&\leq\mathbb{E}[\phi_{\lambda}(\pi^{(t)})]+\frac{2\eta}{\lambda}\mathbb{E}[(\pi^{(t)}-y^{(t+1)})^{\top}\nabla_{\pi}\Phi_{\mu}(\pi^{(t)})]+\frac{24\eta^{2}nA^{2}_{\max}}{\lambda\epsilon(1-\gamma)^{4}}\\\
&\leq\mathbb{E}[\phi_{\lambda}(\pi^{(t)})]+\frac{2\eta}{\lambda}\mathbb{E}\left[\Phi_{\mu}(\pi^{(t)})-\Phi_{\mu}(y^{(t+1)})+\frac{1}{2\lambda}\left\|\pi^{(t)}-y^{(t+1)}\right\|_{2}^{2}\right]+\frac{24\eta^{2}nA^{2}_{\max}}{\lambda\epsilon(1-\gamma)^{4}},\end{split}$

or equivalently

$\mathbb{E}[\phi_{\lambda}(\pi^{(t+1)})]-\mathbb{E}[\phi_{\lambda}(\pi^{(t)})]\leq\frac{2\eta}{\lambda}\mathbb{E}\left[\Phi_{\mu}(\pi^{(t)})-\Phi_{\mu}(y^{(t+1)})+\frac{1}{2\lambda}\left\|\pi^{(t)}-y^{(t+1)}\right\|_{2}^{2}\right]+\frac{24\eta^{2}nA^{2}_{\max}}{\lambda\epsilon(1-\gamma)^{4}}$
(11)

Adding telescopically (11), dividing by $T$ and because w.l.o.g
$-\Phi\in[-1,0]$, we get that

$\begin{split}\frac{1}{T}+\frac{24\eta^{2}nA^{2}_{\max}}{\lambda\epsilon(1-\gamma)^{4}}&\geq\frac{2\eta}{\lambda
T}\sum_{t=1}^{T}\mathbb{E}\left[\Phi_{\mu}(y^{(t+1)})-\Phi_{\mu}(\pi^{(t)})\right]-\frac{\eta}{\lambda^{2}T}\sum_{t=1}^{T}\mathbb{E}\left[\left\|y^{(t+1)}-\pi^{(t)}\right\|_{2}^{2}\right]\\\
&\geq\min_{t\in[T]}\left\\{\frac{2\eta}{\lambda}\mathbb{E}\left[\Phi_{\mu}(y^{(t+1)})-\Phi_{\mu}(\pi^{(t)})\right]-\frac{\eta}{\lambda^{2}}\mathbb{E}[\left\|y^{(t+1)}-\pi^{(t)}\right\|_{2}^{2}]\right\\}\end{split}$
(12)

Let $t*$ be the time index that minimizes the above. We show the following
inequality (which provides a lower bound on the RHS of (12):

$\mathbb{E}\left[\Phi_{\mu}(y^{(t*+1)})-\Phi_{\mu}(\pi^{(t*)})\right]-\frac{1}{2\lambda}\mathbb{E}\left[\left\|y^{(t*+1)}-\pi^{(t*)}\right\|_{2}^{2}\right]\geq\frac{1}{\lambda}\mathbb{E}\left[\left\|y^{(t*+1)}-\pi^{(t*)}\right\|_{2}^{2}\right]$
(13)

Observe that by $\frac{1}{\lambda}$-smoothness of $\Phi_{\mu}$ we get that
$H(x):=-\Phi_{\mu}(x)+\frac{1}{\lambda}\left\|x-\pi^{(t*)}\right\|_{2}^{2}$ is
$\frac{1}{\lambda}$-strong convex and moreover $y^{(t+1)}$ is the minimizer of
$H$. Therefore we get that

$H(\pi^{t*})-H(y^{t*+1})\geq\frac{1}{2\lambda}\left\|\pi^{t*}-y^{t*+1}\right\|_{2}^{2},$

or equivalently

$\Phi_{\mu}(y^{t*+1})-\Phi_{\mu}(\pi^{t*})-\frac{1}{\lambda}\left\|\pi^{t*}-y^{t*+1}\right\|_{2}^{2}\geq\frac{1}{2\lambda}\left\|\pi^{t*}-y^{t*+1}\right\|_{2}^{2}.$

By taking expectation of terms above, (13) follows. Combining (12) with (13)
we conclude that

$\frac{1}{T}+\frac{24\eta^{2}nA^{2}_{\max}}{\lambda\epsilon(1-\gamma)^{4}}\geq\frac{2\eta}{\lambda^{2}}\mathbb{E}\left[\left\|\pi^{t*}-y^{t*+1}\right\|_{2}^{2}\right].$

By Jensen’s inequality it occurs that

$\mathbb{E}\left[\left\|y^{(t*+1)}-\pi^{(t*)}\right\|_{2}\right]\leq\sqrt{\frac{\lambda^{2}}{2\eta
T}+\eta\frac{12n\lambda A_{\max}^{2}}{\epsilon(1-\gamma)^{4}}}.$ (14)

To get an $\epsilon$-Nash policy, we have to bound
$\left\|y^{(t*+1)}-\pi^{(t*)}\right\|_{2}\leq\frac{\epsilon(1-\gamma)}{2D\sqrt{S}(2+\sqrt{nA_{max}})}$
and choose $\alpha=\epsilon^{2}$ in the greedy parametrization. This is true
because of Lemma D.3 Lemma 4.2. Hence, we need to choose $\eta,T$ so that

$\sqrt{\frac{\lambda^{2}}{2\eta T}+\eta\frac{12n\lambda
A_{\max}^{2}}{\epsilon^{2}(1-\gamma)^{4}}}\leq\frac{\epsilon(1-\gamma)}{2D\sqrt{S}(2+\sqrt{nA_{max}})}.$

We conclude that $\eta$ can be chosen to be
$\frac{\epsilon^{4}(1-\gamma)^{3}\gamma}{48nD^{2}A^{2}_{\max}S}$ and $T$ to be
$\frac{48(1-\gamma)A_{\max}D^{4}S^{2}}{\epsilon^{6}\gamma^{3}}.$ ∎

######  Remark 4.

Using Markov’s inequality, it is immediate to show that the statement of
Theorem 4.7 holds with high probability. Namely, if we set the number of
iterations to be
$T=\frac{48(1-\gamma)A_{\max}D^{4}S^{2}}{\epsilon^{6}\gamma^{3}\delta^{4}}$
and the learning rate (step-size) to be
$\eta=\frac{\epsilon^{4}(1-\gamma)^{3}\gamma\delta^{2}}{48nD^{2}A^{2}_{\max}S}$,
where $\delta\in(0,1)$, then with probability $1-\delta$ there exists a
$t\in\\{1,\dots,T\\}$ such that $\pi^{(t)}$ is an $\epsilon$-approximate Nash
policy. However, this is a weaker than desired statement, since, optimally,
the running time should be logarithmic in $1/\delta$, (and not polynomial as
above) [23]. Proving such a statement though requires bounds on the higher
moments of the gradient estimator (to apply martingale arguments and
concentration inequalities with exponential bounds) which we could not derive
using current techniques (cf. Lemma 2 in [11]). Such a bound would be possible
if we sample multiple trajectories and take the average (per iteration).

######  Remark 5 (Weighted and ordinal MPGs).

We conclude this section by giving a remark on Weighted and Ordinal MPGs (cf.
Definition in 1). It is rather straightforward to see that our results carry
over for weighted MPGs. The only difference in the running time of (PGA) is to
account for the weights (which are just multiplicative constants).

In contrast, the extension to ordinal MPGs is not immediate and the reason is
that we cannot prove any bound on the smoothness of $\Phi$ in that case (i.e.,
we cannot generalize Lemma 4.4). Therefore, we cannot have rates of
convergence of policy gradient. Nevertheless, it is quite straightforward that
(PGA) converges asymptotically to critical points (in bounded domains) for
differentiable functions. Therefore as long as $\Phi$ is differentiable, it is
guaranteed that asymptotically (PGA) will converge to a critical point of
$\Phi$. By Lemma 4.2, this point will be a Nash policy.

##  5 Experiments: Congestion Games

We next study the performance of the policy gradient algorithm in a general
class of MDPs that are congestion games at every state, [22, 26].

$\leq N/4$$>N/2$4 facilitiesdistancing statesafe state

Figure 4: Upper left panel: An illustration of the MDP that is used in the
experiments with $S=2$ states, $4$ facilities and $N=8$ agents (description in
text). Lower left panel: The distribution of agents at the equilibrium that is
reached by the policy gradient algorithm (common for all runs). Right column:
Trajectories of the L1-accuracy (average difference between current policy and
Nash policy) over the 10 runs for both equal (upper panels) and different
learning rates among agents (lower panels).

#### Experimental setup:

We consider a MDP in which every state is a congestion game (cf. [4]). In the
current experiment, there are $N=8$ agents, $A_{i}=4$ facilities (resources or
locations) that the agents can select from and $S=2$ states: a _safe_ state
and a _distancing_ state. In both states, all agents prefer to be in the same
facility with as many other agents as possible _(follow the crowd)_ [13]. In
particular, the reward of each agent for being at facility $k$ is equal to a
predefined positive weight $w_{k}^{\text{safe}}$ times the number of agents at
$k=A,B,C,D$. The weights satisfy
$w_{A}^{\text{safe}}<w_{B}^{\text{safe}}<w_{C}^{\text{safe}}<w_{D}^{\text{safe}}$,
i.e., facility $D$ is the most preferable by all agents. However, if more than
$4=N/2$ agents find themselves in the same facility, then the game transitions
to the distancing state. At the distancing state, the reward structure is the
same for all agents, but reward of each agent is reduced by a constant amount,
$c$, where $c>0$ is a (considerably large) constant. (We also treat the case
in which $c$ is different for each facility in Appendix E). To return to the
safe state, the agents need to achieve maximum distribution over the
facilities, i.e., no more than $2=N/4$ agents may be in the same facility. We
consider deterministic transitions, however, the results are quantitatively
equivalent also when these transitions occur with some probability (see
Appendix E). The MDP is illustrated in the upper left panel of Figure 4.

#### Paremeters:

We perform episodic updates with $T=20$ steps. At each iteration, we estimate
the Q-functions, the value function, the discounted visitation distributions
and, hence, the policy gradients using the average of mini-batches of size
$20$. We use $\gamma=0.99$. For the presented plots, we use a common learning
rate $\eta=0.0001$ (upper panels) or randomly generated learning rates
(different for each agent) in $[.00005,.0005]$ (lower panels) in Figure 4.
Note that these learning rates are (several orders of magnitude) larger than
the theoretical guarantee, $\eta=\frac{(1-\gamma)^{3}}{2\gamma
A_{\max}n}\approx 1e-08$, of Theorem 4.5. Experiments (not presented here)
with even larger learning rates (e.g., $\eta=0.001$) did not lead
(consistently) to convergence.

#### Results:

The lower left panel of Figure 4 shows that the agents learn the expected Nash
profile in both states in all runs (this is common for both the fixed and the
random learning rates). At the safe state, the agents distribute themselves
equally among the two most preferable facilities (C and D). This leads to a
maximum utility and avoids a transition to the distancing (bad) state. At the
distancing state, the agents learn the unique distribution (2 agents per
facility) that leads them back to the safe state. Importantly, this (Nash)
policy profile to which policy gradient converges to is _deterministic_ in
line with Theorem 4.5. The panels in the middle and right columns depict the
L1-accuracy in the policy space at each iteration which is defined as the
average distance between the current policy and the final policy of all $8$
agents, i.e.,
$\text{L1-accuracy}=\frac{1}{N}\sum_{i\in\mathcal{N}}|\pi_{i}-\pi_{i}^{\text{final}}|=\frac{1}{N}\sum_{i\in\mathcal{N}}\sum_{s}\sum_{a}|\pi_{i}(a\mid
s)-\pi_{i}^{\text{final}}(a\mid s)|.$ The results are qualitatively equivalent
in both cases (common and non-common learning rates). However, due to the
larger step-sizes used by some agents, the algorithm becomes more responsive
and exhibits faster convergence in the non-common case.

##  6 Further Discussion and Conclusions

In this paper, we have presented a number of positive results (both structural
and algorithmic) about the performance of independent policy gradient ascent
in Markov potential games. Specifically, deterministic Nash policies always
exist and independent policy gradient is guaranteed to converge (polynomially
fast in the approximation error) to a Nash policy profile even in the case of
finite samples. Given these positive results, a number of interesting open
questions emerge.

#### Open questions.

Price of (Markov) Anarchy. Price of Anarchy (PoA) [16] is a classic notion in
normal form games that captures the inefficiency due to the lack of a central
authority that would coordinate all agents to implement the social optimum
outcome. Formally, it is defined as the ratio of the social cost of the worst
Nash equilibrium divided by the cost of the social optimum. PoA has been
studied extensively in many classes of games including several classes of
potential games for which tight PoA bounds exist (e.g. congestion games [27]).
It would be interesting to explore to what extent this type of analysis can be
generalized to Markov Potential Games as well as more general classes of
Markov Games.

Stability of Deterministic Policies. When it comes to online learning in
normal form potential games, it is sometimes possible to prove that the
dynamics do not converge to an arbitrary Nash equilibrium, but, in fact, that
most initial conditions converge to a deterministic (sometimes referred to
also as pure) Nash equilibrium [15, 25, 8, 19]. To produce such equilibrium
selection results, standard Lyapunov arguments do not suffice and one needs to
apply more advanced techniques such as the Center-Stable-Manifold theorem [17]
which would be a fascinating direction for future work in MPGs.

Other Algorithmic Approaches: Softmax Parametrization & Natural Policy
Gradient. In [1], the authors show asymptotic convergence to the global
optimum to single-agent MDP in the tabular setting with exact gradients for
the softmax policy parameterization. Moreover, polynomial convergence rate is
shown when additional KL-based entropy regularizer is used, as well as
dimension-free convergence to optimum when Natural Policy Gradient is applied.
Extending such algorithmic techniques to the case of multi-agent MPGs is a
natural direction for future work.

Global Convergence in other Multi-Agent Markov Games. Recently, there has been
intense interest in understanding convergence to Nash policies for different
classes of learning dynamics in Markov zero-sum games [11, 37, 39]. Our
approach moves in orthogonal direction focusing on MPGs and establishing
strong convergence results in these games. A natural open question is whether
and under what conditions can we prove strong convergence guarantees in more
general classes of Markov games, possibly by combining tools and techniques
from both lines of work.

Regularities beyond Equilibration in Multi-Agent Markov Games. Given the
complexities of such multi-agent settings, it is highly unlikely to expect
practical algorithms which can always guarantee convergence to equilibrium.
This is already the case even for the more restricted setting of normal-form
games [35, 2]. Nevertheless, strong guarantees can be shown via, e.g.,
existence of cyclic/recurrent orbits, invariant functions [20] or strong
social welfare guarantees [32]. Whether such results can be extended to Multi-
Agent Markov Games is a stimulating direction for future work.

## Acknowledgements

This project is supported in part by NRF2019-NRF-ANR095 ALIAS grant, grant
PIE-SGP-AI-2018-01, NRF 2018 Fellowship NRF-NRFF2018-07, AME Programmatic Fund
(Grant No. A20H6b0151) from the Agency for Science, Technology and Research
(A*STAR) and the National Research Foundation, Singapore under its AI
Singapore Program (AISG Award No: AISG2-RP-2020-016).

## References

  * [1] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan.  Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes.  In J. Abernethy and S. Agarwal, editors, Proceedings of 33rd Conference on Learning Theory, volume 125 of PMLR, pages 64–66, 2020.
  * [2] Gabriel P Andrade, Rafael Frongillo, and Georgios Piliouras.  Learning in matrix games can be arbitrarily complex.  arXiv preprint arXiv:2103.03405, 2021.
  * [3] Dimitri P. Bertsekas.  Dynamic Programming and Optimal Control.  Athena Scientific, 2nd edition, 2000.
  * [4] I. Bistritz and N. Bambos.  Cooperative multi-player bandit optimization.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2016–2027. Curran Associates, Inc., 2020.
  * [5] Noam Brown and Tuomas Sandholm.  Superhuman ai for multiplayer poker.  Science, 365(6456):885–890, 2019.
  * [6] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  Found. Trends Mach. Learn., 8(3-4):231–357, 2015.
  * [7] Lucian Busoniu, Robert Babuska, and Bart De Schutter.  A comprehensive survey of multiagent reinforcement learning.  IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156–172, 2008.
  * [8] Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos.  Learning with bandit feedback in potential games.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 6372–6381, 2017.
  * [9] A. Dafoe, Y. Bachrach, G. Hadfield, E. Horvitz, K. Larson, and T. Graepel.  Cooperative ai: machines must learn to find common ground.  Nature, 7857:33–36, 2021.
  * [10] A. Dafoe, E. Hughes, Y. Bachrach, T. Collins, K. R. McKee, J. Z. Leibo, K. Larson, and T. Graepel.  Open Problems in Cooperative AI.  arXiv e-prints, December 2020.
  * [11] C. Daskalakis, D.J. Foster, and N. Golowich.  Independent Policy Gradient Methods for Competitive Reinforcement Learning.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5527–5540. Curran Associates, Inc., 2020.
  * [12] Damek Davis and Dmitriy Drusvyatskiy.  Stochastic subgradient method converges at the rate o(k${}^{\mbox{-1/4}}$) on weakly convex functions.  CoRR, abs/1802.02988, 2018.
  * [13] R. Hassin and M. Haviv.  To queue or not to queue: Equilibrium behavior in queueing systems.  Kluwer Academic Publishers, Boston, USA, 2003.
  * [14] S. Kakade and J. Langford.  Approximately Optimal Approximate Reinforcement Learning.  In Proceedings of the Nineteenth International Conference on Machine Learning, ICML ’02, page 267–274, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc.
  * [15] Robert Kleinberg, Georgios Piliouras, and Éva Tardos.  Multiplicative updates outperform generic no-regret learning in congestion games.  In ACM Symposium on Theory of Computing (STOC), 2009.
  * [16] E. Koutsoupias and C. Papadimitriou.  Worst-case equilibria.  In (STACS), pages 404–413. Springer-Verlag, 1999.
  * [17] Jason D Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I Jordan, and Benjamin Recht.  First-order methods almost always avoid strict saddle points.  Mathematical programming, 176(1):311–337, 2019.
  * [18] J. R. Marden.  State based potential games.  Automatica, 48(12):3075–3088, 2012.
  * [19] Ruta Mehta, Ioannis Panageas, and Georgios Piliouras.  Natural selection as an inhibitor of genetic diversity: Multiplicative weights updates algorithm and a conjecture of haploid genetics.  In Innovations in Theoretical Computer Science, 2015.
  * [20] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras.  Cycles in adversarial regularized learning.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703–2717. SIAM, 2018.
  * [21] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  Nature, 518(7540):529–533, Feb 2015.
  * [22] D. Monderer and L. S. Shapley.  Potential Games.  Games and Economic Behavior, 14(1):124–143, 1996.
  * [23] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro.  Robust stochastic approximation approach to stochastic programming.  SIAM Journal on Optimization, 19(4):1574–1609, 2009.
  * [24] OpenAI.  Openai five.  openai.com, 2018.
  * [25] Ioannis Panageas, Georgios Piliouras, and Xiao Wang.  Multiplicative weights update as a distributed constrained optimization algorithm: Convergence to second-order stationary points almost always.  In ICML, 2018.
  * [26] T. Roughgarden.  Intrinsic robustness of the price of anarchy.  J. ACM, 62(5), November 2015.
  * [27] Tim Roughgarden and Éva Tardos.  How bad is selfish routing?  Journal of the ACM (JACM), 49(2):236–259, 2002.
  * [28] L. S. Shapley.  Stochastic games.  PNAS, 1953.
  * [29] 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, 529(7587):484–489, Jan 2016.
  * [30] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  Science, 362(6419):1140–1144, 2018.
  * [31] Richard S. Sutton and Andrew G. Barto.  Reinforcement Learning: An Introduction.  A Bradford Book, Cambridge, MA, USA, 2018.
  * [32] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire.  Fast convergence of regularized learning in games.  In Proceedings of the 28th International Conference on Neural Information Processing Systems, NIPS’15, pages 2989–2997, Cambridge, MA, USA, 2015. MIT Press.
  * [33] S. Valcarcel Macua, J. Zazo, and S. Zazo.  Learning Parametric Closed-Loop Policies for Markov Potential Games.  In International Conference on Learning Representations, 2018.
  * [34] Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander S. Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver.  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  Nature, 575(7782):350–354, Nov 2019.
  * [35] Emmanouil-Vasileios Vlatakis-Gkaragkounis, Lampros Flokas, Panayotis Mertikopoulos, and Georgios Piliouras.  No-regret learning and mixed nash equilibria: They do not mix.  In Annual Conference on Neural Information Processing Systems, 2020\.
  * [36] X. Wang and T. Sandholm.  Reinforcement Learning to Play an Optimal Nash Equilibrium in Team Markov Games.  In Proceedings of the 15th International Conference on Neural Information Processing Systems, NIPS’02, page 1603–1610, Cambridge, MA, USA, 2002. MIT Press.
  * [37] Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo.  Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games.  CoRR, abs/2102.04540, 2021.
  * [38] K. Zhang, Z. Yang, and T. Başar.  Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms.  arXiv e-prints, page arXiv:1911.10635, 2019.
  * [39] Yulai Zhao, Yuandong Tian, Jason D. Lee, and Simon S. Du.  Provably efficient policy gradient methods for two-player zero-sum markov games.  CoRR, abs/2102.08903, 2021.

##  Appendix A Additional Notation and Definitions: Section 2

We first provide some additional notation and definitions that will be used in
the proofs.

#### Q-value and Advantage Functions.

Recall from the main part that the value function,
$V_{s}^{i}:\Pi\to\mathbb{R}$, gives the expected reward of agent
$i\in\mathcal{N}$ when $s_{0}=s$ and the agents draw their actions,
$\mathbf{a}_{t}=(a_{i,t},\mathbf{a}_{-i,t})$, at time $t\geq 0$ from policies
$\pi=(\pi_{i},\pi_{-i})$ and is defined as

$V^{i}_{s}(\pi):=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{i,t}\mid
s_{0}=s\right].$

Similarly, we will write
$V^{i}_{\rho}(\pi):=\operatorname{\mathbb{E}}_{s_{o}\sim\rho}[V^{i}_{s}(\pi)]$
to denote the expected value of agent $i\in\mathcal{N}$ under the initial
state distribution $\rho$.

For any state $s\in\mathcal{S}$, the Q-value function
$Q_{s}^{i}:\mathcal{P}\times\mathcal{A}\to\mathbb{R}$ and the advantage
function $A_{s}^{i}:\mathcal{P}\times\mathcal{A}\to\mathbb{R}$ of agent
$i\in\mathcal{N}$ are defined as

$\displaystyle Q^{i}_{s}(\pi,\mathbf{a})$
$\displaystyle:=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{i,t}\mid
s_{0}=s,\mathbf{a}_{0}=\mathbf{a}\right],\text{ and}$ (15) $\displaystyle
A^{i}_{s}(\pi,\mathbf{a})$
$\displaystyle:=Q^{i}_{s}(\pi,\mathbf{a})-V^{i}_{s}(\pi).$ (16)

#### Discounted State Distribution.

It will be useful to define the discounted state visitation distribution
$d_{s_{0}}^{\pi}(s)$ for $s\in\mathcal{S}$ that is induced by a (joint) policy
$\pi$ as

$d_{s_{0}}^{\pi}(s):=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathrm{Pr}^{\pi}(s_{t}=s\mid
s_{0}),\quad\text{ for all }s\in\mathcal{S}.$ (17)

As for the value function, we will also write
$d_{\rho}^{\pi}(s)=\operatorname{\mathbb{E}}_{s_{0}\sim\rho}[d_{s_{0}}^{\pi}(s)]$
to denote the discounted state visitation distribution when the initial state
distribution is $\rho$.

##  Appendix B Omitted Materials: Section 3

######  Proposition B.1 (Separability of Value Functions and Equality of
Derivatives).

Let
$\mathcal{G}=(\mathcal{S},\mathcal{N},\mathcal{A}=\\{\mathcal{A}_{i}\\}_{i\in\mathcal{N}},P,R,\rho)$
be a Markov Potential Game (MPG) with potential $\Phi_{s}$, for $s\in S$.
Then, for the value function $V_{s}^{i},s\in\mathcal{S}$ of each agent
$i\in\mathcal{N}$, the following hold

  * P1.

Separability of Value Functions: there exists a function
$U^{i}_{s}:\Delta(\mathcal{A}_{-i})^{S}\to\mathbb{R}$ such that for each joint
policy profile $\pi=(\pi_{i},\pi_{-i})\in\Delta(\mathcal{A})^{S}$, we have
$V_{s}^{i}(\pi)=\Phi_{s}(\pi)+U_{s}^{i}(\pi_{-i})$.

  * P2.

Equality of Derivatives: the partial derivatives of agent $i$’s value function
$V^{i}_{s}$ coincide with the partial derivatives of the potential $\Phi_{s}$
that correspond to agent $i$’s parameters, i.e.,

$\partial_{x_{i,s,a}}V_{s}^{i}(\pi)=\partial_{x_{i,s,a}}\Phi_{s}(\pi),\quad\text{
for all }i\in\mathcal{N}\text{and all }s\in\mathcal{S}.$

###### Proof.

To obtain P1, consider any 3 arbitrary policies for agent $i$, notated by
$\pi_{i},\pi_{i}^{\prime},\pi_{i}^{\prime\prime}\in\Delta(\mathcal{A}_{i})^{S}$.
Then, by the definition of MPGs, we have that

$\displaystyle\Phi_{s}(\pi_{i},\pi_{-i})-\Phi_{s}(\pi_{i}^{\prime},\pi_{-i})$
$\displaystyle=V^{i}_{s}(\pi_{i},\pi_{-i})-V^{i}_{s}(\pi_{i}^{\prime},\pi_{-i}),$
$\displaystyle\Phi_{s}(\pi_{i},\pi_{-i})-\Phi_{s}(\pi_{i}^{\prime\prime},\pi_{-i})$
$\displaystyle=V^{i}_{s}(\pi_{i},\pi_{-i})-V^{i}_{s}(\pi_{i}^{\prime\prime},\pi_{-i}).$

for every starting state $s\in\mathcal{S}$. This implies that we can write
$V^{i}_{s}(\pi_{i},\pi_{-i})$ as both

$\displaystyle V^{i}_{s}(\pi_{i},\pi_{-i})$
$\displaystyle=\Phi_{s}(\pi_{i},\pi_{-i})-\Phi_{s}(\pi_{i}^{\prime},\pi_{-i})+V^{i}_{s}(\pi_{i}^{\prime},\pi_{-i})$
$\displaystyle V^{i}_{s}(\pi_{i},\pi_{-i})$
$\displaystyle=\Phi_{s}(\pi_{i},\pi_{-i})-\Phi_{s}(\pi_{i}^{\prime\prime},\pi_{-i})+V^{i}_{s}(\pi_{i}^{\prime\prime},\pi_{-i})$

Thus, we have that
$-\Phi_{s}(\pi_{i}^{\prime},\pi_{-i})+V^{i}_{s}(\pi_{i}^{\prime},\pi_{-i})=-\Phi_{s}(\pi_{i}^{\prime\prime},\pi_{-i})+V^{i}_{s}(\pi_{i}^{\prime\prime},\pi_{-i})$
for any arbitrary pair of policies $\pi_{i}^{\prime}$ and
$\pi_{i}^{\prime\prime}$ for agent $i$, implying that agent $i$’s policy has
no impact on these terms. Accordingly, we can express them as

$U^{i}_{s}(\pi_{-i}):=-\Phi_{s}(\pi_{i}^{\prime},\pi_{-i})+V^{i}_{s}(\pi_{i}^{\prime},\pi_{-i})=-\Phi_{s}(\pi_{i}^{\prime\prime},\pi_{-i})+V^{i}_{s}(\pi_{i}^{\prime\prime},\pi_{-i}),$

where $U^{i}_{s}(\pi_{-i})$ is a function that does not depend on the policy
of agent $i$. Thus, we can express the utility function of any agent $i$ in a
MPG as

$\displaystyle V^{i}_{s}(\pi)=\Phi_{s}(\pi)+U^{i}_{s}(\pi_{-i}).$

as claimed. To obtain P2, we use P1 for a vector $x_{i}$ parameterizing
$\pi_{i}$, and obtain that

$\displaystyle\partial_{x_{i,a}}V^{i}(\pi)=\partial_{x_{i,a}}\Phi(\pi)+0$

for any coordinate $x_{i,a}$ with $a\in A_{i}$ of $x_{i}$, from which we can
see that our claim is true. ∎

Note that P1 serves as a characterization of MPGs. Namely, a multi-agent MDP
is a MPG if and only if the value function of each agent $i\in\mathcal{N}$ can
be decomposed in a term that is common for all players (potential function)
and in a term that may be different for each agent $i\in\mathcal{N}$ but which
depends only on the actions of all agents other than $i$. This property
carries over from normal form (single state) potential games. Also note that
both properties, P1 and P2, hold for any (differentiable for P2) policy
parameterization and not only for the direct one that we use here.

###### Proof of Theorem 3.1.

Let $\Phi$ be the potential function of $\mathcal{G}$. Since the space
$\Delta(\mathcal{A})^{S}=\Delta(\mathcal{A}_{1})^{S}\times...\times\Delta(\mathcal{A}_{n})^{S}$
is compact and $\Phi$ is continuous, $\Phi$ has a global maximum
$\Phi_{\max}$. Let $(\pi_{1}^{*},...,\pi_{n}^{*})$ denote a global maximizer,
i.e., a joint policy profile at which $\Phi_{\max}$ is attained. By the
Definitions of MPGs and Nash policies, this implies, in particular, that
$(\pi_{1}^{*},...,\pi_{n}^{*})$ is a Nash policy, since

$0<\Phi_{s}(\pi_{i}^{*},\pi_{-i}^{*})-\Phi_{s}(\pi_{i},\pi_{-i}^{*})=V_{s}^{i}(\pi_{i}^{*},\pi_{-i}^{*})-V_{s}^{i}(\pi_{i},\pi_{-i}^{*}),$
($\ast$)

for all $i\in\mathcal{N},s\in\mathcal{S}$ and all policies
$\pi_{i}\in\Delta(\mathcal{A}_{i})^{S}$. If $\pi_{1}^{*},...,\pi_{n}^{*}$ are
all deterministic we are done. So, we may assume that there exists an
$i\in\mathcal{N}$ so that $\pi_{i}^{*}$ is randomized and consider the MDP
$\mathcal{G}^{\prime}$ in which the policy of all agents other than $i$ has
been fixed to $\pi_{-i}^{*}$. $\mathcal{G}^{\prime}$ is a single agent MDP
with the same states as $\mathcal{G}$, the same actions and rewards for agent
$i$ and transition probabilities that are determined by the joint distribution
of the environment and the joint policy of all agents other than $i$. As a
single agent MDP, this setting has a deterministic optimal policy, say
$\tilde{\pi}_{i}$, for agent $i$. Thus, it holds that

$V_{s}^{i}(\tilde{\pi}_{i},\pi_{-i}^{*})\leq
V_{s}^{i}(\pi_{i}^{*},\pi_{-i}^{*})\leq
V_{s}^{i}(\tilde{\pi}_{i},\pi_{-i}^{*}),$

where the first inequality follows from the fact that $\pi^{*}$ is a Nash
policy and the second from the optimality of $\tilde{\pi_{i}}$. It follows
that

$V_{s}^{i}(\tilde{\pi}_{i},\pi_{-i}^{*})=V_{s}^{i}(\pi_{i}^{*},\pi_{-i}^{*}),$

i.e., the payoff of agent $i$ at $(\tilde{\pi}_{i},\pi_{-i}^{*})$ is the same
as in $(\pi_{i}^{*},\pi_{-i}^{*})$. Hence, by the definition of the potential
function, we have that

$\displaystyle 0$
$\displaystyle=V_{s}^{i}(\tilde{\pi}_{i},\pi_{-i}^{*})-V_{s}^{i}(\pi_{i}^{*},\pi_{-i}^{*})=\Phi_{s}(\tilde{\pi}_{i},\pi_{-i}^{*})-\Phi_{s}(\pi_{i}^{*},\pi_{-i}^{*}),$

which implies that

$\Phi_{s}(\tilde{\pi}_{i},\pi_{-i}^{*})=\Phi_{s}(\pi_{i}^{*},\pi_{-i}^{*})=\Phi_{\max}.$

Thus, $(\tilde{\pi}_{i},\pi_{-i}^{*})$ is also a global maximizer of $\Phi$
which implies that $(\tilde{\pi}_{i},\pi_{-i}^{*})$ is a Nash policy by the
same reasoning as in equation ($\ast$ ‣ B). Note that the value of all players
other than $i$ may not be the same at the joint policy profile
$(\tilde{\pi}_{i},\pi_{-i}^{*})$ as it is in $(\pi^{*}_{i},\pi_{-i}^{*})$.
However, what we need for our purpose is that this step reduces the number of
randomized policies by one and that it retains the value of the potential
function invariant at its global maximum (which ensures that the ensuing
policy profile is also a Nash policy). By iterating this process until
$\pi_{j}^{*}$ becomes deterministic for all agents $j\in\mathcal{N}$, we
obtain the claim. ∎

###### Proof of Proposition 3.2.

The proof is constructive and proceeds by finding the potential function,
$\Phi_{s},s\in\mathcal{S}$ in both cases, C1-C2. Since the individual rewards
of the agents at each state $s\in\mathcal{S}$ are captured by a potential
function $\phi_{s}$, then for the reward, $R_{i}(s,\mathbf{a})$ of each agent
$i$ at the action profile $\mathbf{a}$, it holds that

$R_{i}(s,\mathbf{a})=\phi_{s}(\mathbf{a})+u^{i}_{s}(\mathbf{a}_{-i}),$ (18)

where $u^{i}_{s}:\Delta(\mathcal{A}_{-i})\to\mathbb{R}$ is a function that
does not depend on the actions of agent $i$ in any way. Thus, we may write the
value function of each agent $i\in\mathcal{N}$ as

$\displaystyle V_{s}^{i}(\pi)$
$\displaystyle=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{i}(s_{t},\mathbf{a}_{t})\mid
s_{0}=s\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\left(\phi_{s_{t}}(\mathbf{a}_{t})+u^{i}_{s_{t}}(\mathbf{a}_{-i,t})\right)\mid
s_{0}=s\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\phi_{s_{t}}(\mathbf{a}_{t})\mid
s_{0}=s\right]+\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}u^{i}_{s_{t}}(\mathbf{a}_{-i,t})\mid
s_{0}=s\right]$ ($\star$)

where $\tau\sim\pi$ is the random trajectory generated by policy $\pi$. To
show that $\mathcal{G}$ is a MPG, it suffices to show that the value function
of each agent $i\in\mathcal{N}$ can be decomposed in a term that is common for
all agents (and which may depend on the actions of agent $i\in\mathcal{N}$)
and in a term that does not depend (in any way) in the actions of agent $i$
(dummy term), cf Proposition B.1. The first term in expression (B), i.e.,
$\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\phi_{s_{t}}(\mathbf{a}_{t})\mid
s_{0}=s\right]$, depends on the actions of all players and is common for all
agents $i\in\mathcal{N}$ (and is thus, a good candidate for the potential
function). The second term in expression (B), i.e.,
$\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}u_{s_{t}}^{i}(\mathbf{a}_{-i,t})\mid
s_{0}=s\right]$, does not depend on player $i$ via the payoffs
$u_{s_{t}}^{i}(\mathbf{a}_{-i,t})$, but, in general, it does depend on player
$i$ via the transitions, $\tau\sim\pi$. The two cases in the statement of
Proposition 3.2 ensure precisely that this term is independent of the policy
of agent $i$, in which case it is a dummy term for agent $i$ or that is also
common for all players, in which case it can be included in the potential
function. Specifically, we have that

  * C1.

If the transitions do not depend on the action of the players, we have that
$\tau\sim P$, where $P$ is an exogenously given distribution function (state-
wise). In this case, we have that

$\Phi_{s}(\pi):=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\phi_{s_{t}}(\mathbf{a}_{t})\mid
s_{0}=s\right]$

is a potential function and
$U_{s}^{i}(\pi_{-i}):=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}u_{s_{t}}^{i}(\mathbf{a}_{-i,t})\mid
s_{0}=s\right]$ is a dummy term that does not depend (in any way) on the
policy of agent $i\in\mathcal{N}$.

  * C2.

Under the assumptions of condition C2, we will show that again

$\Phi_{s^{\prime}}(\pi):=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\phi_{s_{t}}(\mathbf{a})\mid
s_{0}=s^{\prime}\right]$

is a potential function for $G$ and that the same decomposition as in
condition C1 of the value function of agent $i$ in a common and a dummy term
applies. To see this, let $\pi_{i},\pi_{i}^{\prime}\in\Pi_{i}$ be two policies
of agent $i$ and let
$\pi=(\pi_{i},\pi_{-i}),\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i})$ where
$\pi_{-i}$ is the fixed policy of all agents other than $i$. Then, using (B),
we have that

$\displaystyle V_{s^{\prime}}^{i}(\pi)-V_{s^{\prime}}^{i}(\pi^{\prime})=$
$\displaystyle\;\Phi_{s^{\prime}}(\pi)-\Phi_{s^{\prime}}(\pi^{\prime})$
$\displaystyle+\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}u^{i}_{s_{t}}(\mathbf{a}_{-i,t})\mid
s_{0}=s^{\prime}\right]-\operatorname{\mathbb{E}}_{\tau\sim\pi^{\prime}}\left[\sum_{t=0}^{\infty}\gamma^{t}u^{i}_{s_{t}}(\mathbf{a}_{-i,t})\mid
s_{0}=s^{\prime}\right].$

Using the intermediate value theorem, there exists a policy $\xi_{i}$ which is
a convex combination of $\pi_{i},\pi_{i}^{\prime}$ such that

$\displaystyle\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}u^{i}_{s_{t}}(\mathbf{a}_{-i,t})\mid
s_{0}=s^{\prime}\right]-\operatorname{\mathbb{E}}_{\tau\sim\pi^{\prime}}\left[\sum_{t=0}^{\infty}\gamma^{t}u^{i}_{s_{t}}(\mathbf{a}_{-i,t})\mid
s_{0}=s^{\prime}\right]$
$\displaystyle=(\pi_{i}-\pi_{i}^{\prime})^{\top}\nabla_{\pi_{i}}\operatorname{\mathbb{E}}_{\tau\sim(\xi_{i},\pi_{-i})}\left[\sum_{t=0}^{\infty}\gamma^{t}u^{i}_{s_{t}}(\mathbf{a}_{-i,t})\mid
s_{0}=s^{\prime}\right]$

Since $\pi_{i},\pi_{i}^{\prime}$ correspond to probability distributions at
every state $s\in\mathcal{S}$, their difference is equal to $0$ (state-wise).
In turn, the displayed condition in C2 implies that

$\nabla_{\pi_{i}}\operatorname{\mathbb{E}}_{\tau\sim\xi}\left[\sum_{t=0}^{\infty}\gamma^{t}u^{i}_{s_{t}}(\mathbf{a}_{-i,t})\mid
s_{0}=s^{\prime}\right]=(c_{s}\mathbf{1})_{s\in\mathcal{S}},$

which is enough to ensure that the dot product in the previous equation is
equal to $0$ and the claim follows.

Summing up, in both cases, C1-C2, $\mathcal{G}$ is an MPG as claimed. ∎

Note that the proof of the (trivial) case in which the instantaneous rewards
of all agents $i\in\mathcal{N}$ are equal at each state $s\in\mathcal{S}$ (cf.
Remark 2) is similar. In this case, it is immediate to see that the
instantaneous rewards are precisely given by the potential function at that
state, i.e., it holds that $R_{i}(s,\mathbf{a})=\phi_{s}(\mathbf{a})$ for all
$i\in\mathcal{N}$ and all $s\in\mathcal{S}$. In this case, it holds that
$u_{s}^{i}(\mathbf{a}_{-i})\equiv 0$ for all $i\in\mathcal{N}$ and all
$s\in\mathcal{S}$ and hence,

$\Phi_{s}(\pi):=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\phi_{s_{t}}(\mathbf{a})\mid
s_{0}=s\right]$

is a potential function for $G$, and the dummy terms are all equal to $0$,
i.e., $U_{s}^{i}(\pi_{-i})\equiv 0$.

###  B.1 Examples

######  Example 2 (Continued).

At each state, $s\in\\{0,1\\}$, the agents’ payoffs, $(R_{s}^{1},R_{s}^{2})$,
form a potential game (at that state), and are given as follows

State $0:$ $\displaystyle(R_{0}^{1},R_{0}^{2})=\bordermatrix{~{}&0&1\cr
0&\phantom{-}5,\phantom{-}2&-1,-2\cr
1&-5,-4&\phantom{-}1,\phantom{-}4\cr},\,\,\text{ with potential
\;}\Phi_{0}=\begin{pmatrix}\phantom{-}4&0\\\ -6&2\end{pmatrix},$ State $1:$
$\displaystyle(R_{1}^{1},R_{1}^{2})=(0,0),\,\,\text{ with potential
\;}\Phi_{1}=0.$

In this MDP, agents need only to select an action at state $s_{0}$. Thus, we
will denote a policy, $\pi_{1}$, of agent $1$ by $\pi_{1}=(p,1-p)$ where
$p\in[0,1]$ is the probability with which agent $A$ selects action $0$ at
state $s_{0}$. Similarly, we will denote a policy, $\pi_{2}$, of agent $B$ by
$\pi_{2}=(q,1-q)$ where $q\in[0,1]$ is the probability with which agent $B$
selects action $0$ at state $s_{0}$. Moreover, we will slightly abuse notation
and write

$R_{0}^{i}(\pi)=R_{0}^{i}(\pi_{1},\pi_{2})=\pi_{1}^{\top}R_{0}^{i}\pi_{2}=[p,1-p]R_{0}^{i}[q,1-q]^{\top}.$

We also assume that the horizon is infinite and there is a discount factor
$\gamma\in[0,1)$. Accordingly, we can calculate the value functions
$V_{0}^{i}(\pi_{1},\pi_{2})$ of agents $i=A,B$ starting from state $s_{0}$ as
follows,

$\displaystyle V_{0}^{i}(\pi)$ $\displaystyle=R_{0}^{i}(\pi)+\gamma
pqV_{0}^{i}(\pi)-\gamma(1-pq)\times 0$

which yields the solution

$\displaystyle V_{0}^{i}(\pi)$ $\displaystyle=\frac{R_{0}^{i}(\pi)}{1-\gamma
pq},\quad\text{for }i=A,B.$

Next, we use the Performance Difference Lemma (Lemma 3.2 by [1]) to determine
the difference in the value between two different policies. We will do this
for agent $1$ (the calculation is similar for agent $2$: we use here $1$ for
agent 1 and 2 for agent $B$). For a policy $\pi=(\pi_{1},\pi_{2})$, we have at
state $s_{0}$ that

$\displaystyle\operatorname{\mathbb{E}}_{a\sim\pi_{1}(\cdot\mid
s_{0})}[A^{1}_{0}(\pi^{\prime},\mathbf{a})]$
$\displaystyle=pA^{1}_{0}(\pi^{\prime},0,a_{2})+(1-p)A^{1}(\pi^{\prime},1,a_{2})$
$\displaystyle=p\left[R_{0}^{1}(0,\pi_{2})+\gamma
qV_{0}(\pi^{\prime})-V_{0}(\pi^{\prime})\right]+(1-p)\left[R_{0}^{1}(1,\pi_{2})+0-V_{0}(\pi^{\prime})\right]$
$\displaystyle=pR_{0}^{1}(0,\pi_{2})+(1-p)R_{0}^{1}(0,\pi_{2})-(1-\gamma
pq)V_{0}(\pi^{\prime})$ $\displaystyle=R_{0}^{1}(\pi)-(1-\gamma
pq)V_{0}(\pi^{\prime}).$

At state $s_{1}$, there is only one available action for each agent which
yields a payoff of $0$. Thus,

$\displaystyle\operatorname{\mathbb{E}}_{a\sim\pi_{1}(\cdot\mid
s_{1})}[A^{1}_{1}(\pi^{\prime},\mathbf{a})]$ $\displaystyle=0.$

Moreover, concerning the discounted visitation distribution, we have that

$\displaystyle d^{\pi}_{0}(s_{0})$
$\displaystyle=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathrm{Pr}^{\pi}(s_{t}=s_{0}\mid
s_{0})=(1-\gamma)\left[1+\gamma pq+(\gamma
pq)^{2}+\dots\right]=\frac{1-\gamma}{1-\gamma pq},$

and $d^{\pi}_{0}(s_{1})=1-d^{\pi}_{0}(s_{0})=\frac{\gamma(1-pq)}{1-\gamma
pq}$. Thus, using all the above, we have that

$\displaystyle V_{0}(\pi)-V_{0}(\pi^{\prime})$
$\displaystyle=\frac{1}{1-\gamma}\left[\frac{1-\gamma}{1-\gamma
pq}\cdot(R_{0}^{1}(\pi)-(1-\gamma
pq)V_{0}(\pi^{\prime}))+\frac{\gamma(1-pq)}{1-\gamma pq}\cdot 0\right]$
$\displaystyle=\frac{R_{0}^{1}(\pi)}{1-\gamma
pq}-V_{0}(\pi^{\prime})=V_{0}(\pi)-V_{0}(\pi^{\prime}).$

which shows that our initial calculations conform with the outcome specified
by the Performance Difference Lemma.

Finally, a direct calculation shows that $\Phi_{s}=\phi_{s}$ for $s=0,1$ is a
valid potential function for which the MDP is an _ordinal_ MPG.

######  Example 3 (Continued).

At state $s_{0}$, we consider the game with action sets
$A_{1}(s_{0})=A_{2}(s_{0})=\\{H,T\\}$ and (instantaneous) payoffs

$R_{1}(s_{0},a_{1},a_{2})=\bordermatrix{~{}&H&T\cr H&\phantom{-}1&-1\cr
T&-1&\phantom{-}1\cr}\quad\text{and}\quad
R_{2}(s_{0},a_{1},a_{2})=\bordermatrix{~{}&H&T\cr H&-1&\phantom{-}1\cr
T&\phantom{-}1&-1\cr},$

where $a_{1}$ denotes the action of agent $1$ and $a_{2}$ the action of agent
$2$ (agent $1$ selects rows and agent $2$ selects columns in both matrices).
This is a constant sum game (equivalent to zero-sum) and hence, it is not an
(ordinal) potential game. Apart from the instantaneous rewards, agents’
actions at $s_{0}$ induce a deterministic transition to a state in which the
only available actions to the agents are precisely the actions that they chose
at state $s_{0}$ and their instantaneous rewards at this state are the rewards
of the other agent at $s_{0}$. In particular, there are four possible
transitions to states $s_{ab}$ with $a,b\in\\{H,T\\}$, with action sets and
instantaneous rewards given by

$A_{1}(s_{ab})=\\{a\\},A_{2}(s_{ab})=\\{b\\},\quad
R_{1}(s_{ab},a,b)=R_{2}(s_{0},b,a),\,\,R_{2}(s_{ab},a,b)=R_{1}(s_{0},b,a),$

for agents 1 and 2, respectively. Note that the visitation probability of this
states is equal to the visitation probability of state $s_{0}$. After visiting
one of these states, the MDP transitions to state $s_{1}$ which is a potential
game, with potential function given by

$\Phi_{1}=\bordermatrix{~{}&L&R\cr L&4&3\cr R&3&0\cr}$

As mentioned above, the game in state $s_{0}$ does not admit a potential
function. However, the joined rewards $RJ_{1},RJ_{2}$ of agents $1$ and $2$
which result from selecting an action profile $(a,b)\in{H,T}^{2}$ at $s_{0}$
and then traversing both $s_{0}$ and the ensuing $s_{ab}$ (part included in
the dotted rectangle in Figure 3), do admit a potential function. The
potential function in this case is the sum of agents’ rewards and is given by

$\Phi_{0ab}=\bordermatrix{~{}&H&T\cr H&1-1&1-1\cr
T&1-1&1-1\cr}=\bordermatrix{~{}&H&T\cr H&0&0\cr T&0&0\cr}.$

Let $\pi_{1}=(\mathbf{x}_{0},\mathbf{x}_{1})$ denote a policy of agent $1$.
Here $\mathbf{x}_{0}=(x_{0},1-x_{0})$, where $x_{0}\in[0,1]$ is the
probability with which agent $1$ chooses action $H$ at state $s_{0}$.
Similarly, $\mathbf{x}_{1}=(x_{1},1-x_{1})$ where $x_{1}\in[0,1]$ is the
probability with which agent $1$ chooses action $L$ at state $s_{1}$. At
states $s_{ab},a,b\in\\{H,T\\}^{2}$, agents only have one action to choose
from, so this choice is eliminated from their policy representation.
Similarly, we represent a policy of agent $2$ by
$\pi_{2}=\left(\mathbf{y}_{0},\mathbf{y}_{1}\right)$ with
$y_{0},y_{1}\in[0,1]$. Let also

$p_{0}:=p_{0}\left(\pi_{1},\pi_{2}\right):=\mathrm{Pr}(s_{t+1}=s_{0}\mid
s_{t}=s_{1},\pi_{1},\pi_{2}),$ (19)

In the general case, $p_{0}$, i.e., the transition probability from $s_{1}$ to
$s_{0}$, may depend on the actions of the agents or it may be completely
exogenous (i.e., constant with respect to agents’ actions). If we write

$p_{0}(a_{1},a_{2}):=\mathrm{Pr}(s_{t+1}=s_{0}\mid
s_{t}=s_{1},a_{1},a_{2}),\quad\text{for }a_{1},a_{2}\in\\{L,R\\},$

to denote the probability of transitioning from state $s_{1}$ to state $s_{0}$
given that the agents chose actions $a_{1},a_{2}\in\\{L,R\\}$ at state
$s_{1}$, then we can write $p_{0}$ as

$\displaystyle p_{0}$
$\displaystyle=\operatorname{\mathbb{E}}_{(a_{1},a_{2})\sim(\pi_{1},\pi_{2})}[p_{0}(a_{1},a_{2})]=\sum_{(a_{1},a_{2})\in\\{L,R\\}^{2}}\mathrm{Pr}(a_{1},a_{2}\mid\pi_{1},\pi_{2})\cdot
p_{0}(a_{1},a_{2})$
$\displaystyle=x_{1}y_{1}p_{0}(L,L)+x_{1}(1-y_{1})p_{0}(L,R)+(1-x_{1})y_{1}p_{0}(R,L)+(1-x_{1})(1-y_{1})p_{0}(R,R).$
(20)

Using this notation, we can now proceed to compute the value function of each
state of the MDP in Figure 3. Since the value of states
$s_{a,b},a,b\in{H,T}^{2}$ is equal to a constant reward plus the value of
state $s_{1}$ (discounted by $\gamma$), it suffices to calculate the value for
states $s_{0}$ and $s_{1}$. We have that

$\displaystyle V_{0}^{1}\left(\pi_{1},\pi_{2}\right)$
$\displaystyle=\mathbf{x}_{0}R_{0}^{1}\mathbf{y}_{0}+\gamma\left(\mathbf{x}_{0}\left(R_{0}^{2}/\gamma\right)\mathbf{y}_{0}\right)+\gamma^{2}V_{1}^{1}\left(\pi_{1},\pi_{2}\right)$
$\displaystyle V_{1}^{1}\left(\pi_{1},\pi_{2}\right)$
$\displaystyle=\mathbf{x}_{1}R_{1}^{1}\mathbf{y}_{1}+\gamma\left[p_{0}V_{0}^{1}\left(\pi_{1},\pi_{2}\right)+(1-p_{0})V_{1}^{1}\left(\pi_{1},\pi_{2}\right)\right],$
which after some trivial calculations yield $\displaystyle
V_{0}^{1}\left(\pi_{1},\pi_{2}\right)$
$\displaystyle=\mathbf{x}_{0}\left(R_{0}^{1}+R_{0}^{1}\right)\mathbf{y}_{0}+\gamma^{2}V_{1}^{1}\left(\pi_{1},\pi_{2}\right)$
$\displaystyle V_{1}^{1}\left(\pi_{1},\pi_{2}\right)$
$\displaystyle=\frac{1}{1-\gamma\left(1-p_{0}\right)}\left[\mathbf{x}_{1}R_{1}^{1}\mathbf{y}_{1}+\gamma
p_{0}V_{0}^{1}\left(\pi_{1},\pi_{2}\right)\right].$

This is a system of $2$ equations in the $2$ unknown quantities,
$V_{0}^{1}\left(\pi_{1},\pi_{2}\right)$ and
$V_{1}^{1}\left(\pi_{1},\pi_{2}\right)$. Solving for these two quantities,
yields the unique solution

$\displaystyle V_{0}^{1}\left(\pi_{1},\pi_{2}\right)$
$\displaystyle=\frac{1}{1-\gamma\left(1-p_{0}\right)-\gamma^{3}p_{0}}\left[\left(1-\gamma\left(1-p_{0}\right)\right)\mathbf{x}_{0}\left(R_{0}^{1}+R_{0}^{2}\right)\mathbf{y}_{0}+\gamma^{2}\mathbf{x}_{1}R_{1}^{1}\mathbf{y}_{1}\right].$
$\displaystyle V_{1}^{1}\left(\pi_{1},\pi_{2}\right)$
$\displaystyle=\frac{1}{1-\gamma\left(1-p_{0}\right)-\gamma^{3}p_{0}}\left[\gamma
p_{0}\mathbf{x}_{0}\left(R_{0}^{1}+R_{0}^{2}\right)\mathbf{y}_{0}+\mathbf{x}_{1}R_{1}^{1}\mathbf{y}_{1}\right].$

In the case that $p_{0}$ is a constant with respect to $\pi_{1},\pi_{2}$, then
both value functions are of the form

$V_{s}^{i}\left(\pi_{1},\pi_{2}\right)=c_{1}\left(s\right)\cdot\mathbf{x}_{0}\left(R_{0}^{1}+R_{0}^{2}\right)\mathbf{y}_{0}+c_{2}\left(s\right)\cdot\mathbf{x}_{1}R_{1}^{i}\mathbf{y}_{1},\quad\text{for
}s\in\\{s_{0},s_{1}\\},\,\,\text{and }i=\\{1,2\\},$

where $c_{1}\left(s\right),c_{2}\left(s\right)>0$ are appropriate constants
that depend only the state $s\in\\{s_{0},s_{1}\\}$ and on agents $1,2$. Since
the game at $s_{1}$ is a potential game, with potential function given by a
$2\times 2$ matrix $\Phi_{1}$, it is immediate to infer that

$V_{s}^{i}\left(\pi^{\prime}_{1},\pi_{2}\right)-V_{s}^{i}\left(\pi_{1},\pi_{2}\right)=\Phi_{s}\left(\pi^{\prime}_{1},\pi_{2}\right)-\Phi_{s}\left(\pi_{1},\pi_{2}\right),\text{for
}s\in\\{s_{0},s_{1}\\},$

with

$\Phi_{s}\left(\pi_{1},\pi_{2}\right):=c_{1}\left(s\right)\mathbf{x}_{0}\left(R_{0}^{1}+R_{0}^{2}\right)\mathbf{y}_{0}+c_{2}\left(s\right)\cdot\mathbf{x}_{1}\Phi_{1}\mathbf{y}_{1},\text{for
}s\in\\{s_{0},s_{1}\\}.$

However, if $p_{0}$ depends on the actual policies of agents $1$ and $2$, cf.
equation (19), then it is not immediate to determine a potential (or even to
decide whether a (exact) potential exists or not).

######  Remark 6.

Several elements of Example 3 have been selected in the sake of simplicity and
are not necessary for the main takeaway, i.e., that there are MDP that are not
potential at some states but which are MPGs. First, the transitions from
$s_{0}$ to the states $s_{ab}$ need not be deterministic. To see this, let
$q\in(0,1)$ and assume that if the agents select actions $H,T$ is $s_{0}$,
then the process transitions with probability $q$ to a state $s_{HT}$ with
rewards $(-1,1)/q\gamma$ and with probability $(1-q)$ to a state
$s^{\prime}_{HT}$ with rewards $(1,-1)/(1-q)\gamma$. The rest remains the
same. Accordingly, the expected reward for agent $1$ after $(H,T)$ has been
selected in $s_{0}$ is the same as in the current format.

Second, the construction with states $s_{0}$ and $s_{ab},(a,b)\in{H,T}^{2}$ is
not the only one that leads to such an example. Another very common instance
occurs in the case of _aliasing_ between $s_{0}$ and states $s_{ab}$, i.e.,
when the agents cannot tell these states apart. The intuition which carries
over from the currently presented example is that the roles of the agents are
essentially reversed between the two states but the agents do not know (from
the observable features) in which state they are. Thus, any valid policy,
selects the same action in both states leading to the same situation as in the
presented example.

Finally, if the horizon is finite, then the instantaneous rewards in states
$s_{ab}$ still work if we eliminate the scaling factor (here $\gamma$). Thus,
the construction works in both episodic and continuing settings.

##  Appendix C Omitted Materials: Section 4

###### Proof of Lemma 4.1.

Observe that for any set $\mathcal{X}\subseteq\mathbb{R}^{n}$, it holds that

$P_{\mathcal{X}}(y)=\operatorname*{argmin}_{x\in\mathcal{X}}\left\|x-y\right\|_{2}^{2}.$

Thus,

$\displaystyle P_{\Delta(\mathcal{A})^{S}}(y)$
$\displaystyle=\operatorname*{argmin}_{x\in\Delta(\mathcal{A})^{S}}\left\|x-\pi^{\prime}\right\|_{2}^{2}=\operatorname*{argmin}_{x_{1}\in\Delta(\mathcal{A}_{1})^{S},...,x_{n}\in\Delta(\mathcal{A}_{n})^{S}}\sum_{i=1}^{n}\left\|x_{i}-\pi^{\prime}_{i}\right\|_{2}^{2}$
$\displaystyle=\sum_{i=1}^{n}\operatorname*{argmin}_{x_{i}\in\Delta(\mathcal{A}_{i})^{S}}\left\|x_{i}-\pi^{\prime}_{i}\right\|_{2}^{2}=(P_{\Delta(\mathcal{A}_{1})^{S}}(\pi^{\prime}_{1}),\dots,P_{\Delta(\mathcal{A}_{n})^{S}}(\pi^{\prime}_{n})).\qed$

To prove Lemma 4.3, we will use a multi-agent version of the Performance
Difference Lemma (cf. [1] for a single agent and [11] for two agents).

######  Lemma C.1 (Multi-agent Performance Difference Lemma).

Consider an n-agent MDP $\mathcal{G}$ and fix an agent $i\in\mathcal{N}$.
Then, for any policies
$\pi=(\pi_{i},\pi_{-i}),\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i})\in\Pi$ and
any distribution $\rho\in\Delta(S)$, it holds that

$V^{i}_{\rho}(\pi)-V^{i}_{\rho}(\pi^{\prime})=\frac{1}{1-\gamma}\operatorname{\mathbb{E}}_{s\sim
d_{\rho}^{\pi}}\operatorname{\mathbb{E}}_{a_{i}\sim\pi_{i}(\cdot\mid
s)}\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi_{-i}(\cdot\mid
s)}\left[A_{s}^{i}(\pi^{\prime},a_{i},\mathbf{a}_{-i})\right],$

where $\mathbf{a}_{-i}\sim\pi_{-i}(\cdot\mid s)$ denotes the action profile of
all agents other than $i$ that is drawn from the product distribution induced
by their policies $\pi_{-i}=(\pi_{j})_{j\neq i\in\mathcal{N}}\in\Pi_{-i}$.

###### Proof.

For any initial state $s\in\mathcal{S}$ and joint policies
$\pi=(\pi_{i},\pi_{-i}),\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i})\in\Pi$, it
holds that

$\displaystyle V^{i}_{s}(\pi)-V^{i}_{s}(\pi^{\prime})$
$\displaystyle=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{i,t}\mid
s_{0}=s\right]-V^{i}_{s}(\pi^{\prime})$
$\displaystyle=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\left(r_{i,t}-V_{s_{t}}(\pi^{\prime})+V_{s_{t}}(\pi^{\prime})\right)\mid
s_{0}=s\right]-V^{i}_{s}(\pi^{\prime})$
$\displaystyle=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\left(r_{i,t}-V_{s_{t}}(\pi^{\prime})+\gamma
V_{s_{t+1}}(\pi^{\prime})\right)\mid s_{0}=s\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\left(r_{i,t}+\gamma\operatorname{\mathbb{E}}\left[V_{s_{t+1}}(\pi^{\prime})\mid
s_{t},a_{i,t},\mathbf{a}_{-i,t}\right]-V_{s_{t}}(\pi^{\prime})\right)\mid
s_{0}=s\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{\tau\sim\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}A_{s_{t}}^{i}(\pi^{\prime},\mathbf{a}_{t})\mid
s_{0}=s\right]$
$\displaystyle=\frac{1}{1-\gamma}\operatorname{\mathbb{E}}_{s^{\prime}\sim
d_{\rho}^{\pi}}\operatorname{\mathbb{E}}_{a_{i}\sim\pi_{i}(\cdot\mid
s^{\prime})}\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi_{-i}(\cdot\mid
s^{\prime})}\left[A_{s^{\prime}}^{i}(\pi^{\prime},\mathbf{a})\right].$

Taking expectation over the states $s\in\mathcal{S}$ with respect to the
distribution $\rho\in\Delta(\mathcal{S})$ yields the result. ∎

###### Proof of Lemma 4.3.

Fix an agent $i\in\mathcal{N}$ and let
$\pi=(\pi_{i},\pi_{-i}),\pi^{*}=(\pi_{i}^{*},\pi_{-i})\in\Pi=\Delta(\mathcal{A})^{S}$.
By the definition of MPGs (cf. Definition 2), it holds that

$V^{i}_{\rho}(\pi^{*})-V^{i}_{\rho}(\pi)=\Phi_{\rho}(\pi^{*})-\Phi_{\rho}(\pi).$

Thus, using the multi-agent version of the Performance Difference Lemma (cf.
Lemma C.1), we have for any distribution $\mu\in\Delta(\mathcal{S})$ that

$\displaystyle\Phi_{\rho}(\pi^{*})-\Phi_{\rho}$
$\displaystyle(\pi)=V^{i}_{\rho}(\pi^{*})-V^{i}_{\rho}(\pi)$
$\displaystyle=\frac{1}{1-\gamma}\operatorname{\mathbb{E}}_{s\sim
d_{\rho}^{\pi^{*}}}\operatorname{\mathbb{E}}_{a_{i}\sim\pi^{*}_{i}(\cdot\mid
s)}\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi^{*}_{-i}(\cdot\mid
s)}\left[A_{s}^{i}(\pi,a_{i,t},\mathbf{a}_{-i,t})\right]$
$\displaystyle\leq\frac{1}{1-\gamma}\max_{\pi^{\prime}_{i}\in\Pi_{i}}\left\\{\sum_{s\in\mathcal{S}}d_{\rho}^{\pi^{*}}(s)\operatorname{\mathbb{E}}_{a_{i}\sim\pi^{\prime}_{i}(\cdot\mid
s)}\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi^{*}_{-i}(\cdot\mid
s)}\left[A_{s}^{i}(\pi,a_{i},\mathbf{a}_{-i})\right]\right\\},$
$\displaystyle=\frac{1}{1-\gamma}\max_{\pi^{\prime}_{i}\in\Pi_{i}}\left\\{\sum_{s\in\mathcal{S}}\frac{d_{\rho}^{\pi^{*}}(s)}{d_{\mu}^{\pi}(s)}d_{\mu}^{\pi}(s)\operatorname{\mathbb{E}}_{a_{i}\sim\pi^{\prime}_{i}(\cdot\mid
s)}\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi^{*}_{-i}(\cdot\mid
s)}\left[A_{s}^{i}(\pi,a_{i},\mathbf{a}_{-i})\right]\right\\},$
$\displaystyle\leq\frac{1}{1-\gamma}\left\|\frac{d^{\pi^{*}}_{\rho}}{d^{\pi}_{\mu}}\right\|_{\infty}\max_{\pi^{\prime}_{i}\in\Pi_{i}}\left\\{\sum_{s\in\mathcal{S}}d_{\mu}^{\pi}(s)\operatorname{\mathbb{E}}_{a_{i}\sim\pi^{\prime}_{i}(\cdot\mid
s)}\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi^{*}_{-i}(\cdot\mid
s)}\left[A_{s}^{i}(\pi,a_{i},\mathbf{a}_{-i})\right]\right\\}.$

To proceed, observe that

$\operatorname{\mathbb{E}}_{a_{i}\sim\pi_{i}(\cdot\mid
s)}\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi^{*}_{-i}(\cdot\mid
s)}\left[A_{s}^{i}(\pi,a_{i},\mathbf{a}_{-i})\right]=0.$

Thus, for any $\pi^{\prime}_{i}\in\Pi_{i}$ and any state $s\in\mathcal{S}$, it
holds that

$\displaystyle\operatorname{\mathbb{E}}_{a_{i}\sim\pi^{\prime}_{i}(\cdot\mid
s)}\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi^{*}_{-i}(\cdot\mid
s)}\left[A_{s}^{i}(\pi,a_{i},\mathbf{a}_{-i})\right]=$ $\displaystyle=$
$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}\left(\pi_{i}^{\prime}(a_{i}\mid
s)-\pi_{i}(a_{i}\mid
s)\right)\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi^{*}_{-i}(\cdot\mid
s)}\left[A_{s}^{i}(\pi,a_{i},\mathbf{a}_{-i})\right]$ $\displaystyle=$
$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}\left(\pi_{i}^{\prime}(a_{i}\mid
s)-\pi_{i}(a_{i}\mid
s)\right)\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi^{*}_{-i}(\cdot\mid
s)}\left[Q_{s}^{i}(\pi,a_{i},\mathbf{a}_{-i})\right]$

since $V^{i}_{s}(\pi)$ does not depend on $a_{i}$. Substituting back in the
last inequality of the previous calculations, we obtain that

$\displaystyle\Phi_{\rho}(\pi^{*})-\Phi_{\rho}(\pi)\leq$ $\displaystyle\leq$
$\displaystyle\left\|\frac{d^{\pi^{*}}_{\rho}}{d^{\pi}_{\mu}}\right\|_{\infty}\max_{\pi^{\prime}_{i}\in\Pi_{i}}\left\\{\sum_{s,a_{i}}\frac{d_{\mu}^{\pi}(s)}{1-\gamma}\left(\pi_{i}^{\prime}(a_{i}\mid
s)-\pi_{i}(a_{i}\mid
s)\right)\operatorname{\mathbb{E}}_{\mathbf{a}_{-i}\sim\pi^{*}_{-i}(\cdot\mid
s)}\left[Q_{s}^{i}(\pi,a_{i},\mathbf{a}_{-i})\right]\right\\}$
$\displaystyle=$
$\displaystyle\left\|\frac{d^{\pi^{*}}_{\rho}}{d^{\pi}_{\mu}}\right\|_{\infty}\max_{\pi^{\prime}_{i}\in\Pi_{i}}(\pi_{i}^{\prime}-\pi_{i})^{\top}\nabla_{\pi_{i}}V_{\mu}^{i}(\pi),$

where we used the policy gradient theorem ([1, 31]) under the assumption of
direct policy parameterization (cf. equation (2)). We can further upper bound
the last expression by using that $d^{\pi}_{\mu}(s)\geq(1-\gamma)\mu(s)$ which
follows immediately from the definition of the discounted visitation
distribution $d^{\pi}_{\mu}(s)$ for any initial state distribution $\mu$.
Finally, property P2 of Proposition B.1, implies that
$\nabla_{\pi_{i}}V^{i}_{\rho}(\pi)=\nabla_{\pi_{i}}\Phi_{\rho}(\pi)$ (making
crucial use of the MPG structure). Putting these together, we have that

$\displaystyle\Phi_{\rho}(\pi^{*})-\Phi_{\rho}(\pi)$
$\displaystyle\leq\frac{1}{1-\gamma}\left\|\frac{d^{\pi^{*}}_{\rho}}{\mu}\right\|_{\infty}\max_{\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i}^{*})}(\pi^{\prime}-\pi)^{\top}\nabla_{\pi_{i}}V^{i}_{\mu}(\pi)$
$\displaystyle=\frac{1}{1-\gamma}\left\|\frac{d^{\pi^{*}}_{\rho}}{\mu}\right\|_{\infty}\max_{\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i}^{*})}(\pi^{\prime}-\pi)^{\top}\nabla_{\pi_{i}}\Phi_{\mu}(\pi),$

as claimed. ∎

###### Proof of Lemma 4.4.

It suffices to show that the maximum eigenvalue in absolute value of the
Hessian of $\Phi$ is at most $\frac{2n\gamma A_{\max}}{(1-\gamma)^{3}}$, i.e.,
that

$\left\|\nabla^{2}\Phi_{\mu}\right\|_{2}\leq\frac{2n\gamma
A_{\max}}{(1-\gamma)^{3}}\,.$

We first prove the following intermediate claim.

######  Claim C.2.

Consider the symmetric block matrix $C$ with $n\times n$ matrices so that
$\left\|C_{ij}\right\|_{2}\leq L$. Then, it holds that
$\left\|C\right\|_{2}\leq nL$, i.e., if all block submatrices have spectral
norm at most $L$, then $C$ has spectral norm at most $nL$.

###### Proof.

We will prove the claim by induction on $n$. For $n=2$ we need to show that

$\left\|C\right\|_{2}:=\left\|\left(\begin{array}[]{cc}C_{11}&C_{12}\\\
C_{21}&C_{22}\end{array}\right)\right\|_{2}\leq 2L$

if
$\left\|C_{11}\right\|_{2},\left\|C_{12}\right\|_{2},\left\|C_{21}\right\|_{2},\left\|C_{22}\right\|_{2}\leq
L.$ Define matrix $W$ to be

$W:=2L\cdot I-C=\left(\begin{array}[]{cc}2L\cdot I-C_{11}&-C_{12}\\\
-C_{21}&2L\cdot I-C_{22}\end{array}\right),$

where $I$ is the identity matrix (of appropriate size). If we show that $W$ is
positive semi-definite, then it follows that $W$ has only non-negative
eigenvalues, which, in turn, implies that the spectral norm of $C$ is at most
$2L$. To see this, set

$W_{1}:=\left(\begin{array}[]{cc}L\cdot I-C_{11}&0\\\ 0&L\cdot
I-C_{22}\end{array}\right),W_{2}:=\left(\begin{array}[]{cc}L\cdot I&-C_{12}\\\
-C_{21}&L\cdot I\end{array}\right).$

$W_{1}$ is positive semi-definite as a block diagonal matrix with diagonal
blocks positive semi-definite matrices. Moreover, by Schur complement we get
that $W_{2}$ is positive semi-definite as long as $L\cdot I$ is positive semi-
definite and $L\cdot I-\frac{1}{L}\cdot C_{12}C_{21}$ is positive
semidefinite. By assumption, we have that

$\frac{1}{L}\left\|C_{12}C_{21}\right\|_{2}\leq\frac{1}{L}\left\|C_{12}\right\|_{2}\left\|C_{12}\right\|_{2}\leq
L,$

which implies that $L\cdot I-\frac{1}{L}\cdot C_{12}C_{21}$ has non-negative
eigenvalues. Thus, $W_{2}$ is positive semi-definite. We conclude that
$W_{1}+W_{2}$ is positive semi-definite (sum of positive semi-definite
matrices is positive semi-definite) and the claim follows.

For the induction step, suppose that the claim holds for an $n=k-1\geq 2$. To
establish that it also holds for $k$, we need to show that

$\left\|C\right\|_{2}:=\left\|\left(\begin{array}[]{cccc
}C_{11}&C_{12}&\dots&C_{1k}\\\ C_{21}&C_{22}&\dots&C_{2k}\\\
\vdots&\vdots&\vdots&\vdots\\\
C_{k1}&C_{k2}&\dots&C_{kk}\end{array}\right)\right\|_{2}\leq kL$

as long as $\left\|C_{ij}\right\|_{2}\leq L$ for all $i,j$. Let $W=kL\cdot
I-C$. To show that $W$ is positive semi-definite consider

$W_{1}:=\left(\begin{array}[]{ccccc}kL\cdot
I-C_{11}&-C_{12}&-C_{13}&\dots&-C_{1k}\\\ -C_{21}&L\cdot I&0&\dots&0\\\
\vdots&\vdots&\vdots&\vdots\\\ -C_{k1}&0&0&\dots&L\cdot
I\end{array}\right),W_{2}:=W-W_{1}.$

By induction, it follows that $W_{2}$ is positive semi-definite. We need to
show that the same holds for $W_{1}$. By Schur complement we obain that
$W_{1}$ is positive semi-definite if and only if $kL\cdot
I-C_{11}-\frac{1}{L}\sum_{i=2}^{k}C_{1i}C_{i1}$ is positive semi-definite. It
follows that

$\left\|C_{11}-\frac{1}{L}\sum_{i}C_{1i}C_{i1}\right\|_{2}\leq\left\|C_{11}\right\|_{2}+\frac{1}{L}\sum_{i=2}^{k}\left\|C_{1i}\right\|_{2}\left\|C_{i1}\right\|_{2}\leq
L+(k-1)L=kL.$

Hence $W_{1}$ is positive semi-definite and the induction is complete. ∎

Returning to the statement of Lemma 4.4, we will show that

$\left\|\nabla^{2}_{\pi_{j}\pi_{i}}V^{j}_{\mu}\right\|_{2}\leq C,$ (21)

for all $i,j\in\mathcal{N}$ with $C$ chosen to be $\frac{2\gamma
A_{\max}}{(1-\gamma)^{3}}$. Assuming we have shown (21), we conclude from
Claim C.2 that

$\left\|\nabla^{2}\Phi_{\mu}\right\|_{2}\leq nC,$

and hence $\Phi$ will be $nC$-smooth (the proof of Lemma 4.4 will follow).

To prove (21), we follow the same proof steps as in the proof of [1], Lemma
D.3. We will need to prove an upper bound on the largest eigenvalue (in
absolute value) of the matrix

$\nabla^{2}_{\pi_{j}\pi_{i}}V^{j}_{\mu}=\nabla^{2}_{\pi_{j}\pi_{i}}V^{i}_{\mu},$

along the direction where only agent $i$ is allowed to change policy.

Fix policy $\pi=(\pi_{1},...,\pi_{n})$, agents $i\neq j$, scalars $t,s\geq 0$,
state $s_{0}$ and $u,v$ be unit vectors such that $\pi_{i}+t\cdot
u\in\Delta(\mathcal{A}_{i})^{S}$ and $\pi_{j}+s\cdot
v\in\Delta(\mathcal{A}_{j})^{S}$. Moreover, let
$V(t)=V^{i}_{s_{0}}(\pi_{i}+t\cdot u,\pi_{-i}).$ and
$W(t,s)=V^{i}_{s_{0}}(\pi_{i}+t\cdot u,\pi_{j}+s\cdot v,\pi_{-i,-j}).$ It
suffices to show that

$\max_{\left\|u\right\|_{2}=1}\left|\frac{d^{2}V(0)}{dt^{2}}\right|\leq\frac{2\gamma|\mathcal{A}_{i}|}{(1-\gamma)^{3}}\textrm{
and
}\max_{\left\|u\right\|_{2}=1}\left|\frac{d^{2}W(0,0)}{dtds}\right|\leq\frac{2\gamma\sqrt{|\mathcal{A}_{i}||\mathcal{A}_{j}|}}{(1-\gamma)^{3}}.$
(22)

  * •

We first focus on $V(t)$.

It holds that
$V(t)=\sum_{a\in\mathcal{A}_{i}}\sum_{\mathbf{a}\in\mathcal{A}_{-i}}(x_{i,s_{0},a}+tu_{i,s_{0},a})\prod_{j\neq
i}x_{j,s_{0},a_{j}}Q^{i}_{s_{0}}((\pi_{i}+tu,\pi_{-i}),(a,\mathbf{a}))$ (note
that
$\sum_{a\in\mathcal{A}_{i}}\sum_{\mathbf{a}\in\mathcal{A}_{-i}}(x_{i,s_{0},a}+tu_{i,s_{0},a})\prod_{j\neq
i}x_{j,s_{0},a_{j}}=1$ since it is a distribution), hence taking the second
derivative we have

$\begin{split}\frac{d^{2}V(0)}{dt^{2}}=&\sum_{a\in\mathcal{A}_{i}}\sum_{\mathbf{a}\in\mathcal{A}_{-i}}(x_{i,s_{0},a}+tu_{i,s_{0},a})\prod_{j\neq
i}x_{j,s_{0},a_{j}}\frac{d^{2}Q^{i}_{s_{0}}(\pi,(a,\mathbf{a}))}{dt^{2}}\\\
&+2\sum_{a\in\mathcal{A}_{i}}\sum_{\mathbf{a}\in\mathcal{A}_{-i}}u_{i,s_{0},a}\prod_{j\neq
i}x_{j,s_{0},a_{j}}\frac{dQ^{i}_{s_{0}}(\pi,(a,\mathbf{a}))}{dt}\end{split}$
(23)

For the remaining of the first part of the proof, we shall show

$\left|\frac{dQ^{i}_{s_{0}}(\pi,(a,\mathbf{a}))}{dt}\right|\leq\frac{\gamma\sqrt{|\mathcal{A}_{i}|}}{(1-\gamma)^{2}}\textrm{
and
}\left|\frac{d^{2}Q^{i}_{s_{0}}(\pi,(a,\mathbf{a}))}{dt^{2}}\right|\leq\frac{2\gamma^{2}|\mathcal{A}_{i}|}{(1-\gamma)^{3}},$

and then combining with (23) we get

$\begin{split}\left|\frac{d^{2}V(0)}{dt^{2}}\right|&\leq\frac{2\gamma\sqrt{|\mathcal{A}_{i}|}}{(1-\gamma)^{2}}\sum_{a\in\mathcal{A}_{i}}|u_{i,s_{0},a}|+\frac{2\gamma^{2}|\mathcal{A}_{i}|}{(1-\gamma)^{3}}\\\
&\leq\frac{2\gamma|\mathcal{A}_{i}|}{(1-\gamma)^{2}}+\frac{2\gamma^{2}|\mathcal{A}_{i}|}{(1-\gamma)^{3}}\\\
&\leq\frac{2\gamma A_{\max}}{(1-\gamma)^{3}}\,.\end{split}$

To bound the derivative of the $Q$-function, observe that
$Q^{i}_{s_{0}}((\pi_{i}+tu,\pi_{-i}),(a,\mathbf{a}))=e^{\top}_{s_{0},a}(I-\gamma
P(t))^{-1}r$, where $r(s_{0},a)$ is the expected reward of agent $i$ (w.r.t
the randomness of the remaining agents) if he chooses action $a$ at state
$s_{0}$ and $P(t)$ is state-action transition matrix of w.r.t the joint
distribution of all agents but $i$, i.e., $\pi_{-i}$ and the environment.

It is clear that $\frac{d^{2}P}{dt^{2}}=0$ (linear with respect to $t$ because
of direct parametrization) and moreover
$\left\|\frac{dP}{dt}\right\|_{\infty}\leq\sum_{a\in\mathcal{A}_{i}}|u_{i,s_{0},a}|\leq\sqrt{\mathcal{A}_{i}}\leq\sqrt{A_{\max}}.$
Using the fact that $\left\|(I-\gamma
P(t))^{-1}\right\|_{\infty}\leq\frac{1}{1-\gamma},$ we get

$\begin{split}\left|\frac{dQ^{i}_{s_{0}}(\pi,(a,\mathbf{a}))}{dt}\right|&=\gamma\left|e^{\top}_{s_{0},a}(I-\gamma
P(0))^{-1}\frac{dP(0)}{dt}(I-\gamma
P(0))^{-1}r\right|\leq\frac{\gamma\sqrt{|\mathcal{A}_{i}|}}{(1-\gamma)^{2}}\leq\frac{\gamma\sqrt{A_{\max}}}{(1-\gamma)^{2}},\end{split}$
(24)

and also

$\begin{split}\left|\frac{d^{2}Q^{i}_{s_{0}}(\pi,(a,\mathbf{a}))}{dt^{2}}\right|&=2\gamma^{2}\left|e^{\top}_{s_{0},a}(I-\gamma
P(0))^{-1}\frac{dP(0)}{dt}(I-\gamma P(0))^{-1}\frac{dP(0)}{dt}(I-\gamma
P(0))^{-1}r\right|\\\
&\leq\frac{2\gamma^{2}|\mathcal{A}_{i}|}{(1-\gamma)^{3}}\leq\frac{2\gamma^{2}A_{\max}}{(1-\gamma)^{3}},\end{split}$
(25)

Since $u$ is arbitrary, the first part of (22) is proved.

  * •

For the second part, we focus on $W(t)$ which is equal to

$\begin{split}W(t,s)=&\sum_{a\in\mathcal{A}_{i}}\sum_{b\in\mathcal{A}_{j}}\sum_{\mathbf{a}\in\mathcal{A}_{-i,-j}}(x_{i,s_{0},a}+tu_{i,s_{0},a})(x_{j,s_{0},b}+sv_{j,s_{0},b})\cdot\\\
&\cdot\prod_{j^{\prime}\neq
i,j}x_{j^{\prime},s_{0},a_{j^{\prime}}}Q^{i}_{s_{0}}((\pi_{i}+tu,\pi_{j}+sv,\pi_{-i,-j}),(a,b,\mathbf{a}))\end{split}$
(26)

We consider the derivative of $W$ (26) and we get

$\begin{split}\frac{dW(0,0)}{dtds}&=\sum_{a\in\mathcal{A}_{i}}\sum_{b\in\mathcal{A}_{j}}\sum_{\mathbf{a}\in\mathcal{A}_{-i,-j}}u_{i,s_{0},a}v_{j,s_{0},b}\cdot\prod_{j^{\prime}\neq
i,j}x_{j^{\prime},s_{0},a_{j^{\prime}}}Q^{i}_{s_{0}}(\pi,(a,b,\mathbf{a}))\\\
&+\sum_{a\in\mathcal{A}_{i}}\sum_{\mathbf{a}\in\mathcal{A}_{-i}}u_{i,s_{0},a}\cdot\prod_{j^{\prime}\neq
i}x_{j^{\prime},s_{0},a_{j^{\prime}}}\frac{dQ^{i}_{s_{0}}(\pi,(a,\mathbf{a}))}{dt}\\\
&+\sum_{b\in\mathcal{A}_{j}}\sum_{\mathbf{a}\in\mathcal{A}_{-j}}v_{j,s_{0},b}\cdot\prod_{j^{\prime}\neq
j}x_{j^{\prime},s_{0},a_{j^{\prime}}}\frac{dQ^{i}_{s_{0}}(\pi,(b,\mathbf{a}))}{dt}.\\\
&+\sum_{\mathbf{a}\in\mathcal{A}}\prod_{j^{\prime}}x_{j^{\prime},s_{0},a_{j^{\prime}}}\frac{d^{2}Q^{i}_{s_{0}}(\pi,\mathbf{a})}{dtds}.\end{split}$
(27)

The first term of the sum in absolute value is at most
$\frac{\sqrt{|\mathcal{A}_{i}||\mathcal{A}_{j}|}}{1-\gamma}$ (assuming rewards
lie in $[0,1]$.) Moreover using (24) the second term of the sum in absolute
value is bounded by
$\frac{\gamma\sqrt{|\mathcal{A}_{i}|}\sqrt{|\mathcal{A}_{i}|}}{(1-\gamma)^{2}}$
and the third term by
$\frac{\gamma\sqrt{|\mathcal{A}_{j}|}\sqrt{|\mathcal{A}_{i}|}}{(1-\gamma)^{2}}.$
To bound the $\frac{d^{2}Q^{i}_{s_{0}}(\pi,\mathbf{a})}{dtds}$, the same
approach works that we used to prove (25) with the extra fact that the state-
action transition matrix is $P(t,s)$ and moreover the reward $r(s_{0},a,b)$ is
the expected reward of agent $i$ (w.r.t the randomness of all agents but
$i,j$) if $i$ chooses action $a$ and $j$ chooses $b$ at state $s_{0}.$

Finally for the fourth term we get that

$\begin{split}\left|\frac{d^{2}Q^{i}_{s_{0}}(\pi,\mathbf{a})}{dtds}\right|&\leq\gamma^{2}\left|e^{\top}_{s_{0},a}(I-\gamma
P(0,0))^{-1}\frac{dP(0,0)}{ds}(I-\gamma
P(0,0))^{-1}\frac{dP(0,0)}{dt}(I-\gamma P(0,0))^{-1}r\right|+\\\
&+\gamma^{2}\left|e^{\top}_{s_{0},a}(I-\gamma
P(0,0))^{-1}\frac{dP(0,0)}{dt}(I-\gamma
P(0,0))^{-1}\frac{dP(0,0)}{ds}(I-\gamma P(0,0))^{-1}r\right|+\\\
&+\gamma\left|e^{\top}_{s_{0},a}(I-\gamma
P(0,0))^{-1}\frac{d^{2}P(0,0)}{dt^{2}}(I-\gamma P(0,0))^{-1}r\right|\\\
&\leq\frac{\gamma^{2}\sqrt{|\mathcal{A}_{i}||\mathcal{A}_{j}|}}{(1-\gamma)^{3}}+\frac{\gamma^{2}\sqrt{|\mathcal{A}_{i}||\mathcal{A}_{j}|}}{(1-\gamma)^{3}}+\frac{\gamma\sqrt{|\mathcal{A}_{i}||\mathcal{A}_{j}|}}{(1-\gamma)^{2}}\leq\frac{2\gamma\sqrt{|\mathcal{A}_{i}||\mathcal{A}_{j}|}}{(1-\gamma)^{3}}\leq\frac{2\gamma
A_{\max}}{(1-\gamma)^{3}}.\qed\end{split}$

##  Appendix D Auxiliary Lemmas

Recall that $P_{\mathcal{X}}$ denotes the projection onto some set
$\mathcal{X}$.

######  Lemma D.1 ([6], Lemma 3.6).

Let $f$ be a $\beta$-smooth function555Differentiable with $\nabla f$ to be
$\beta$-Lipschitz. with convex domain $\mathcal{X}$. Let $x\in\mathcal{X}$,
$x^{+}=P_{\mathcal{X}}(x-\frac{1}{\beta}\nabla f(x))$ and
$g_{\mathcal{X}}(x)=\beta(x-x^{+})$. Then the following holds true:

$f(x^{+})-f(x)\leq-\frac{1}{2\beta}\left\|g_{\mathcal{X}}(x)\right\|_{2}^{2}.$

######  Lemma D.2 ([1], Proposition B.1).

Let $f(\pi)$ be a $\beta$-smooth function in $\pi\in\Delta(\mathcal{A})^{S}$.
Define the gradient mapping

$G(\pi)=\beta\left(P_{\Delta(\mathcal{A})^{S}}\left(\pi+\frac{1}{\beta}\nabla_{\pi}f(\pi)\right)-\pi\right)$

and the update rule for the projected gradient is
$\pi^{\prime}=\pi+\frac{1}{\beta}G(\pi)$. If
$\left\|G(\pi)\right\|_{2}\leq\epsilon$, then

$\max_{\pi+\delta\in\Delta(\mathcal{A})^{S},\left\|\delta\right\|_{2}\leq
1}\delta^{\top}\nabla_{\pi}f(\pi^{\prime})\leq 2\epsilon.$

######  Lemma D.3.

Let $\Phi_{\mu}(\pi)$ be the potential function (which is $\beta$-smooth) and
assume $\pi\in\Delta(\mathcal{A})^{S}$ uses $\alpha$-greedy parametrization.
Define the gradient mapping

$G(\pi)=\beta\left(P_{\Delta(\mathcal{A})^{S}}\left(\pi+\frac{1}{\beta}\nabla\Phi_{\mu}(\pi)\right)-\pi\right)$

and the update rule for the projected gradient is
$\pi^{\prime}=\pi+\frac{1}{\beta}G(\pi)$. If
$\left\|G(\pi)\right\|_{2}\leq\epsilon$, then

$\max_{\pi+\delta\in\Delta(\mathcal{A})^{S},\left\|\delta\right\|_{2}\leq
1}\delta^{\top}\nabla\Phi_{\mu}(\pi^{\prime})\leq 2\epsilon+\sqrt{n\alpha
A_{\max}}.$

###### Proof.

It is a direct application of Lemma D.2 and the fact that $\Phi_{\mu}$ is
Lipschitz with parameter $\frac{\sqrt{nA_{\max}}}{(1-\gamma)^{2}}$ (this is
Proposition 3 in page 23 of [11]). ∎

######  Lemma D.4 (Unbiased with bounded variance [11]).

It holds that $\hat{\nabla}_{\pi_{i}}^{(t)}$ is unbiased estimator of
$\nabla_{\pi_{i}}V^{i}$ for all $i$, that is

$\mathbb{E}_{\pi^{(t)}}\hat{\nabla}_{\pi_{i}}^{(t)}=\nabla_{\pi_{i}}V^{i}_{\rho}(\pi^{(t)})\textrm{
for all }i.$

Moreover for all agents $i$ we get that (this is what the authors actually
prove)

$\mathbb{E}_{\pi^{(t)}}\left\|\hat{\nabla}_{\pi_{i}}^{(t)}\right\|_{2}^{2}\leq\frac{24A_{\max}^{2}}{\alpha(1-\gamma)^{4}}.$

##  Appendix E Additional Experiments

In this part, we provide a systematic analysis of variations of the
experimental setting in Section 5.

#### Coordination beyond MPGs

As mentioned in Remark 5, we know that policy gradient converges also in other
cooperative settings which may fail to be exact MPGs. To study this case, we
modify our experiment from Section 5. The setting remains mostly the same,
except now in the distancing state the rewards are reduced by a differing (yet
still sufficiently large) amount, $c_{k}$, for each facility $k=A,B,C,D$.

Figure 5: Figures similar to Figure 4, except now with
$c>c_{A}>c_{B}>c_{C}>c_{D}$ as described in the text. Independent policy
gradient requires more iterations to converge compared to the symmetric shift
setting, but still arrives at the same Nash policy.

Despite the introduced asymmetry, it is still natural that cooperation is
desirable in this setting. In particular, if the $c_{k}$’s for all $k=A,B,C,D$
are taken to be greater than the $c$ of the MDP from Section 5, then the
agents can be said to have even “stronger” incentive to cooperate. The results
of running independent policy gradient on this variant are shown in Figure 5.
Independent policy gradient requires more iterations to converge compared to
the symmetric setting, but still arrives at the same Nash policy.

#### Coordination with more agents and facilities

Figure 6: Convergence to deterministic Nash policies of independent policy
gradient in a variation of the MDP of Section 5 with $N=16$ agents and
$A_{i}=5$ facilities, $\mathcal{A}_{i}=\\{A,B,C,D,E\\}$ with
$w_{A}<w_{B}<w_{C}<w_{D}<w_{E}$ (i.e., $E$ is the most preferable by all
agents). Again, while there are several (symmetric) deterministic Nash
policies, all of them yield the same distribution of agents among states
(leftmost panel). All runs converge successfully to that outcome (however,
some runs required a larger number of iterates to converge).

We next test the performance of the independent policy gradient algorithm in a
larger setting with $N=16$ agents and $A_{i}=5$ facilities,
$\mathcal{A}_{i}=\\{A,B,C,D,E\\}$ with $w_{A}<w_{B}<w_{C}<w_{D}<w_{E}$ (i.e.,
$E$ is the most preferable by all agents). We use a learning rate
$\eta=0.0001$ for all agents (which is again much larger than the theoretical
guarantee of Theorem 4.5). All runs lead to convergence to an (optimal) Nash
policy as shown in the middle and rightmost panels. The leftmost panel shows
the distribution of the agents among facilities in both states, which is the
same (and the optimal one) in all Nash policies that are reached by the
algorithm. The results are shown in Figure 6.

#### Coordination with random transitions

Figure 7: Convergence to deterministic Nash policies of independent policy
gradient in two variations of the MDP of Section 5 with stochastic transitions
between states.

Next, we study the effect of adding randomness to the transitions on the