# Decentralized Mean Field Games

Sriram Ganapathi Subramanian1, 3, Matthew E. Taylor2, 4, Mark Crowley1, Pascal
Poupart1, 3

###### Abstract

Multiagent reinforcement learning algorithms have not been widely adopted in
large scale environments with many agents as they often scale poorly with the
number of agents. Using mean field theory to aggregate agents has been
proposed as a solution to this problem. However, almost all previous methods
in this area make a strong assumption of a centralized system where all the
agents in the environment learn the same policy and are effectively
indistinguishable from each other. In this paper, we relax this assumption
about indistinguishable agents and propose a new mean field system known as
_Decentralized Mean Field Games_ , where each agent can be quite different
from others. All agents learn independent policies in a decentralized fashion,
based on their local observations. We define a theoretical solution concept
for this system and provide a fixed point guarantee for a $Q$-learning based
algorithm in this system. A practical consequence of our approach is that we
can address a ‘chicken-and-egg’ problem in empirical mean field reinforcement
learning algorithms. Further, we provide $Q$-learning and actor-critic
algorithms that use the decentralized mean field learning approach and give
stronger performances compared to common baselines in this area. In our
setting, agents do not need to be clones of each other and learn in a fully
decentralized fashion. Hence, for the first time, we show the application of
mean field learning methods in fully competitive environments, large-scale
continuous action space environments, and other environments with
heterogeneous agents. Importantly, we also apply the mean field method in a
ride-sharing problem using a real-world dataset. We propose a decentralized
solution to this problem, which is more practical than existing centralized
training methods.

##  1 Introduction

Most multiagent reinforcement learning (MARL) algorithms are not tractable
when applied to environments with many agents (infinite in the limit) as these
algorithms are exponential in the number of agents (Busoniu, Babuska, and De
Schutter 2006). One exception is a class of algorithms that use the mean field
theory (Stanley 1971) to approximate the many agent setting to a two agent
setting, where the second agent is a mean field distribution of all agents
representing the average effect of the population. This makes MARL algorithms
tractable since, effectively, only two agents are being modelled. Lasry and
Lions (2007) introduced the framework of a _mean field game_ (MFG), which
incorporates the mean field theory in MARL. In MARL, the mean field can be a
population state distribution (Huang 2010) or action distribution (Yang et al.
2018) of all the other agents in the environment.

MFGs have three common assumptions. First, each agent does not have access to
the local information of the other agents. However, it has access to accurate
global information regarding the mean field of the population. Second, all
agents in the environment are independent, homogeneous, and indistinguishable.
Third, all agents maintain interactions with others only through the mean
field. These assumptions (especially the first two) severely restrict the
potential of using mean field methods in real-world environments. The first
assumption is impractical, while the second assumption implies that all agents
share the same state space, action space, reward function, and have the same
objectives. Further, given these assumptions, prior works use centralized
learning methods, where all agents learn and update a shared centralized
policy. These two assumptions are only applicable to cooperative environments
with extremely similar agents. Theoretically, the agent indices are omitted
since all agents are interchangeable (Lasry and Lions 2007). We will relax the
first two assumptions. In our case, the agents are not interchangeable and can
each formulate their own policies during learning that differs from others.
Also, we will not assume the availability of the immediate global mean field.
Instead, agents only have local information and use modelling techniques
(similar to opponent modelling common in MARL (Hernandez-Leal, Kartal, and
Taylor 2019)) to effectively model the mean field during the training process.
We retain the assumption that each agent’s impact on the environment is
infinitesimal (Huang 2010), and hence agents calculate best responses only to
the mean field. Formulating best responses to each individual agent is
intractable and unnecessary (Lasry and Lions 2007).

The solution concepts proposed by previous mean field methods have been either
the centralized Nash equilibrium (Yang et al. 2018) or a closely related mean
field equilibrium (Lasry and Lions 2007). These solution concepts are
centralized as they require knowledge of the current policy of all other
agents or other global information, even in non-cooperative environments.
Verifying their existence is infeasible in many practical environments
(Neumann 1928).

This work presents a new kind of mean field system, _Decentralized Mean Field
Games_ (DMFGs), which uses a decentralized information structure. This new
formulation of the mean field system relaxes the assumption of agents’
indistinguishability and makes mean field methods applicable to numerous real-
world settings. Subsequently, we provide a decentralized solution concept for
learning in DMFGs, which will be more practical than the centralized solution
concepts considered previously. We also provide a fixed point guarantee for a
$Q$-learning based algorithm in this system.

A ‘chicken-and-egg’ problem exists in empirical mean field reinforcement
learning algorithms where the mean field requires agent policies, yet the
policies cannot be learned without the global mean field (Yang and Wang 2020).
We show that our formulation can address this problem, and we provide
practical algorithms to learn in DMFGs. We test our algorithms in different
types of many agent environments. We also provide an example of a ride-sharing
application that simulates demand and supply based on a real-world dataset.

##  2 Background

Stochastic Game: An $N$-player stochastic (Markovian) game can be represented
as a tuple
$\langle\mathcal{S},\mathcal{A}^{1},\ldots,\mathcal{A}^{N},r^{1},\ldots,r^{N},p,\gamma\rangle$,
where $\mathcal{S}$ is the state space, $\mathcal{A}^{j}$ represents the
action space of the agent $j\in\\{1,\ldots,N\\}$, and
$r^{j}:\mathcal{S}\times\mathcal{A}^{1}\times\cdots\times\mathcal{A}^{N}\xrightarrow{}\mathcal{R}$
represents the reward function of $j$. Also,
$p:\mathcal{S}\times\mathcal{A}^{1}\times\cdots\times\mathcal{A}^{N}\xrightarrow{}\Omega(\mathcal{S})$
represents the transition probability that determines the next state given the
current state and the joint action of all agents. Here $\Omega(\mathcal{S})$
is a probability distribution over the state space. In the stochastic game,
agents aim to maximize the expected discounted sum of rewards, with discount
factor $\gamma\in[0,1)$.

Each agent $j$ in the stochastic game formulates a policy, which is denoted by
$\pi^{j}:\mathcal{S}\xrightarrow{}\Omega(\mathcal{A}^{j})$ where the joint
policy is represented as $\boldsymbol{\pi}=[\pi^{1},\ldots,\pi^{N}]$ for all
$s\in\mathcal{S}$. Given an initial state $s$, the value function of the agent
$j$ under the joint policy $\boldsymbol{\pi}$ can be represented as
$v^{j}(s|\boldsymbol{\pi})=\sum_{t=0}^{\infty}\gamma^{t}\mathbb{E}[r^{j}_{t}|s_{0}=s,\boldsymbol{\pi}]$.
The solution concept is the _Nash equilibrium_ (NE) (Hu and Wellman 2003).
This is represented by a joint policy
$\boldsymbol{\pi}_{*}=[\pi^{1}_{*},\ldots,\pi^{N}_{*}]$, such that, for all
$\pi^{j}$, $v^{j}(s|\pi^{j}_{*},\boldsymbol{\pi}^{-j}_{*})\geq
v^{j}(s|\pi^{j},\boldsymbol{\pi}^{-j}_{*})$, for all agents
$j\in\\{1,\ldots,N\\}$ and all states $s\in\mathcal{S}$. The notation
$\boldsymbol{\pi}^{-j}_{*}$ represents the joint policy of all agents except
the agent $j$.

Mean Field Game: MFG was introduced as a framework to solve the stochastic
game when the number of agents $N$ is very large (Lasry and Lions 2007; Huang
et al. 2006). In this setting, calculating the best response to each
individual opponent is intractable, so each agent responds to the aggregated
state distribution
$\mu_{t}\triangleq\lim_{N\xrightarrow{}\infty}\frac{\sum_{j=1,j\neq
i}\boldsymbol{1}(s^{j}_{t})}{N}$, known as the mean field. Let
$\boldsymbol{\mu}\triangleq\\{\mu_{t}\\}^{\infty}_{t=0}$. MFG assumes that all
agents are identical (homogeneous), indistinguishable, and interchangeable
(Lasry and Lions 2007). Given this assumption, the environment changes to a
single-agent stochastic control problem where all agents share the same policy
(Saldi, Basar, and Raginsky 2018). Hence,
$\pi^{1}=\cdots=\pi^{N}=\boldsymbol{\pi}$. The theoretical formulation focuses
on a representative player, and the solution of this player (optimal policy)
obtains the solution for the entire system. The value function of a
representative agent can be given as
$V(s,\boldsymbol{\pi},\boldsymbol{\mu})\triangleq\mathbb{E}_{\boldsymbol{\pi}}\big{[}\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t},\mu_{t})|s_{0}=s\big{]}$,
where $s$ and $a$ are the state and action of the representative agent,
respectively. The transition dynamics is represented as
$P(s_{t},a_{t},\mu_{t})$, where the dependence is on the mean field
distribution. All agents share the same reward function
$r(s_{t},a_{t},\mu_{t})$. The action comes from the policy
$\pi_{t}(a_{t}|s_{t},\mu_{t})$.

The solution concept for the MFG is the mean field equilibrium (MFE). A tuple
$(\boldsymbol{\pi}^{*}_{MFG},\boldsymbol{\mu}^{*}_{MFG})$ is a mean field
equilibrium if, for any policy $\boldsymbol{\pi}$, an initial state
$s\in\mathcal{S}$ and given mean field $\boldsymbol{\mu}^{*}_{MFG}$,
$V(s,\boldsymbol{\pi}^{*}_{MFG},\boldsymbol{\mu}^{*}_{MFG})\geq
V(s,\boldsymbol{\pi},\boldsymbol{\mu}^{*}_{MFG})$. Additionally,
$\boldsymbol{\mu}^{*}_{MFG}$ is the mean field obtained when all agents play
the same $\boldsymbol{\pi}^{*}_{MFG}$ at each $s\in\mathcal{S}$.

Mean Field Reinforcement Learning (MFRL): MFRL, introduced by Yang et al.
(2018), is another approach for learning in stochastic games with a large
number of agents. Here, the empirical mean action is used as the mean field,
which each agent then uses to update its $Q$-function and Boltzmann policy.
Each agent is assumed to have access to the global state, and it takes local
action from this state. In MFRL, the $Q$-function of the agent $j$ is updated
as,

$\begin{array}[]{l}Q^{j}(s_{t},a^{j}_{t},\mu^{a}_{t})\\\
\quad\quad=(1-\alpha)Q^{j}(s_{t},a^{j}_{t},\mu^{a}_{t})+\alpha[r^{j}_{t}+\gamma
v^{j}(s_{t+1})]\end{array}$ (1) where $\displaystyle
v^{j}(s_{t+1})=\sum_{a^{j}_{t+1}}\pi^{j}(a^{j}_{t+1}|s_{t+1},\mu^{a}_{t})Q^{j}(s_{t+1},a^{j}_{t+1},\mu^{a}_{t})$
(2)
$\displaystyle\mu^{a}_{t}=\frac{1}{\mathcal{N}}\sum_{j}a^{j}_{t},a^{j}_{t}\sim\pi^{j}(\cdot|s_{t},\mu^{a}_{t-1})$
(3)
$\displaystyle\pi^{j}(a^{j}_{t}|s_{t},\mu^{a}_{t-1})=\frac{\exp(-\hat{\beta}Q^{j}(s_{t},a^{j}_{t},\mu^{a}_{t-1})}{\sum_{a^{j^{\prime}}_{t}\in
A^{j}}\exp(-\hat{\beta}Q^{j}(s_{t},a^{j^{\prime}}_{t},\mu^{a}_{t-1}))}$ (4)

where $s_{t}$ is the global old state, $s_{t+1}$ is the global resulting
state, $r^{j}_{t}$ is the reward of $j$ at time $t$, $v^{j}$ is the value
function of $j$, $\mathcal{N}$ is the total number of agents, and
$\hat{\beta}$ represents the Boltzmann parameter. The action $a^{j}$ is
assumed to be discrete and represented using one-hot encoding. Like stochastic
games, MFRL uses the NE as the solution concept. The global mean field
$\mu^{a}_{t}$ captures the action distribution of all agents. To address this
global limitation, Yang et al. (2018) specify mean field calculation over
certain neighbourhoods for each agent. However, an update using Eq. 3 requires
each agent to have access to all other agent policies or the global mean field
to use the centralized concept (NE). We omit an expectation in Eq. 2 since
Yang et al. (2018) guaranteed that their updates will be greedy in the limit
with infinite exploration (GLIE).

From Eq. 3 and Eq. 4, it can be seen that the current action depends on the
mean field and the mean field depends on the current action. To resolve this
‘chicken-and-egg’ problem, Yang et al. (2018) simply use the previous mean
field action to decide the current action, as in Eq. 4. This can lead to a
loss of performance since the agents are formulating best responses to the
previous mean field action $\mu^{a}_{t-1}$, while they are expected to respond
to the current mean field action $\mu^{a}_{t}$.

##  3 Related Work

MFGs were first proposed in Huang, Caines, and Malhamé (2003), while a
comprehensive development of the system and principled application methods
were given later in Lasry and Lions (2007). Subsequently, learning algorithms
were proposed for this framework. Subramanian and Mahajan (2019) introduce a
restrictive form of MFG (known as stationary MFG) and provide a model-free
policy-gradient (Sutton et al. 1999; Konda and Tsitsiklis 1999) algorithm
along with convergence guarantees to a local Nash equilibrium. On similar
lines, Guo et al. (2019) provide a model-free $Q$-learning algorithm (Watkins
and Dayan 1992) for solving MFGs, also in the stationary setting. The
assumptions in these works are difficult to verify in real-world environments.
Particularly, Guo et al. (2019) assume the presence of a game engine
(simulator) that accurately provides mean field information to all agents at
each time step, which is not practical in many environments. Further, other
works depend on fictitious play updates for the mean field parameters
(Hadikhanloo and Silva 2019; Elie et al. 2020), which involves the strong
assumption that opponents play stationary strategies. All these papers use the
centralized setting for the theory and the experiments.

Prior works (Gomes, Mohr, and Souza 2010; Adlakha, Johari, and Weintraub 2015;
Saldi, Basar, and Raginsky 2018) have established the existence of a
(centralized) mean field equilibrium in the discrete-time MFG under a
discounted cost criterion, in finite and infinite-horizon settings. Authors
have also studied the behaviour of iterative algorithms and provided
theoretical analysis for learning of the non-stationary (centralized) mean
field equilibrium in infinite-horizon settings (Więcek and Altman 2015; Więcek
2020; Anahtarci, Kariksiz, and Saldi 2019). We provide similar guarantees in
the decentralized setting with possibly heterogeneous agents.

Yang et al. (2018) introduces MFRL that uses a mean field approximation
through the empirical mean action, and provides two practical algorithms that
show good performance in large MARL settings. The approach is model-free and
the algorithms do not need strong assumptions regarding the nature of the
environment. However, they assume access to global information that needs a
centralized setting for both theory and experiments. MFRL has been extended to
multiple types (Subramanian et al. 2020) and partially observable environments
(Subramanian et al. 2021). However, unlike us, Subramanian et al. (2020)
assumes that agents can be divided into a finite set of types, where agents
within a type are homogeneous. Subramanian et al. (2021) relaxes the
assumption of global information in MFRL, however, it still uses the Nash
equilibrium as the solution concept. Further, that work contains some
assumptions regarding the existence of conjugate priors, which is hard to
verify in real-world environments. Additional related work is provided in
Appendix L.

##  4 Decentralized Mean Field Game

The DMFG model is specified by
$\langle\boldsymbol{\mathcal{S}},\boldsymbol{\mathcal{A}},p,\boldsymbol{R},\mu_{0}\rangle$,
where
$\boldsymbol{\mathcal{S}}=\mathcal{S}^{1}\times\cdots\times\mathcal{S}^{N}$
represents the state space and
$\boldsymbol{\mathcal{A}}=\mathcal{A}^{1}\times\cdots\times\mathcal{A}^{N}$
represents the joint action space. Here, $\mathcal{S}^{j}$ represents the
state space of an agent $j\in\\{1,\ldots,N\\}$ and $\mathcal{A}^{j}$
represents the action space of $j$. As in MFGs, we are considering the
infinite population limit of the game, where the set of agents $N$, satisfy
$N\xrightarrow{}\infty$. Similar to the MFG formulation in several prior works
(Lasry and Lions 2007; Huang et al. 2006; Saldi, Basar, and Raginsky 2018), we
will specify that both the state and action spaces are Polish spaces.
Particularly, $\mathcal{A}^{j}$ for all agents $j$, is a compact subset of a
finite dimensional Euclidean space $\Re^{d}$ with the Euclidean distance norm
$||\cdot||$. Since all agents share the same environment, for simplicity, we
will also assume that the state spaces of all the agents are the same
$\mathcal{S}^{1}=\cdots=\mathcal{S}^{N}=\mathcal{S}$ and are locally compact.
Since the state space is a complete separable metric space (Polish space), it
is endowed with a metric $d_{X}$. The transition function
$p:\mathcal{S}\times\mathcal{A}^{j}\times\mathcal{P}(\mathcal{S)}\xrightarrow{}\mathcal{P}(\mathcal{S})$
determines the next state of any $j$ given the current state and action of
$j$, and the probability distribution of the state in the system (represented
by the mean field). The reward function is represented as a set
$\boldsymbol{R}=\\{R^{1},\ldots,R^{N}\\}$, where,
$R^{j}:\mathcal{S}\times\mathcal{A}^{j}\times\mathcal{P}(\mathcal{S})\xrightarrow{}[0,\infty)$
is the reward function of $j$.

Recall that a DMFG has two major differences as compared to MFG and MFRL. 1)
DMFG does not assume that the agents are indistinguishable and homogeneous
(agent indices are retained). 2) DMFG does not assume that each agent can
access the global mean field of the system. However, each agents’ impact on
the environment is infinitesimal, and therefore all agents formulate best
responses only to the mean field of the system (no per-agent modelling is
required).

As specified, in DMFG, the transition and reward functions for each agent
depends on the mean field of the environment, represented by
$\boldsymbol{\mu}\triangleq(\mu_{t})_{t\geq 0}$, with the initial mean field
represented as $\mu_{0}$. For DMFG, mean field can either correspond to the
state distribution
$\mu_{t}\triangleq\lim_{N\xrightarrow{}\infty}\frac{\sum_{j=1}^{N}\boldsymbol{1}(s^{j}_{t})}{N}$
or the action distribution $\mu^{a}_{t}$ as in Eq. 3. Without loss of
generality we use the mean field as the state distribution $\mu_{t}$
(represented by $\mathcal{P}(\mathcal{S})$), as done in prior works (Lasry and
Lions 2007; Elliott, Li, and Ni 2013). However, our setting and theoretical
results will hold for the mean field as action distribution $\mu^{a}_{t}$ as
well.

In the DMFG, each agent $j$ will not have access to the true mean field of the
system and instead use appropriate techniques to actively model the mean field
through exploration. The agent $j$ holds an estimate of the actual mean field
represented by $\mu^{j}_{t}$. Let
$\boldsymbol{\mu}^{j}\triangleq(\mu^{j}_{t})_{t\geq 0}$. Let, $\mathcal{M}$ be
used to denote the set of mean fields
$\\{\boldsymbol{\mu^{j}}\in\mathcal{P}(\mathcal{S})\\}$. A Markov policy for
an agent $j$ is a stochastic kernel on the action space $\mathcal{A}^{j}$
given the immediate local state ($s^{j}_{t}$) and the agent’s current
estimated mean field $\mu^{j}_{t}$, i.e.
$\pi_{t}^{j}:\mathcal{S}\times\mathcal{P}(\mathcal{S})\xrightarrow{}\mathcal{P}(\mathcal{A}^{j})$,
for each $t\geq 0$. Alternatively, a non-Markov policy will depend on the
entire state-action history of game play. We will use $\Pi^{j}$ to denote a
set of all policies (both Markov and non-Markov) for the agent $j$. Let
$s^{j}_{t}$ represent the state of an agent $j$ at time $t$ and $a^{j}_{t}$
represent the action of $j$ at $t$. Then an agent $j$ tries to maximize the
objective function given by the following equation (where $r^{j}$ denotes the
immediate reward obtained by the agent $j$ and $\beta\in[0,1)$ denotes the
discount factor),

$\begin{array}[]{l}J^{j}_{\boldsymbol{\mu}}(\pi^{j})\triangleq\mathbb{E}^{\pi^{j}}[\sum_{t=0}^{\infty}\beta^{t}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})].\end{array}$
(5)

In line with prior works (Yang et al. 2018; Subramanian et al. 2020), we
assume that each agent’s sphere of influence is restricted by its
neighbourhood, where it conducts exploration. Using this assumption, we assert
that, after a finite $t$, the mean field estimate will accurately reflect the
true mean field for $j$, in its neighbourhood denoted as $\mathcal{N}^{j}$.
This assumption specifies that agents have full information in their
neighbourhood, and they can use modelling techniques to obtain accurate mean
field information within the neighbourhood (also refer to flocking from Perrin
et al. (2021)).

######  Assumption 1.

There exists a finite time $T$ and a neighbourhood $\mathcal{N}^{j}$, such
that for all $t>T$, the mean field estimate of an agent $j\in{1,\ldots,N}$
satisfies ($\forall s^{j}\in\mathcal{N}^{j}$)
$\boldsymbol{\mu}^{j}(s^{j})=\boldsymbol{\mu}(s^{j})$. Also, $\forall
s^{j}\in\mathcal{N}^{j}$, we have,
$p(\cdot|s^{j}_{t},a^{j}_{t},\mu^{j}_{t})=p(\cdot|s^{j}_{t},a^{j},\mu_{t})$
and
$r^{j}(\cdot|s^{j}_{t},a^{j}_{t},\mu^{j}_{t})=r^{j}(\cdot|s^{j}_{t},a^{j}_{t},\mu_{t})$.

Let us define a set $\Phi:\mathcal{M}\xrightarrow{}2^{\Pi}$ as
$\Phi(\boldsymbol{\mu^{j}})=\\{\pi^{j}\in\Pi^{j}:\pi^{j}\textrm{ is optimal
for }\boldsymbol{\mu^{j}}\\}$. Conversely, for $j$, we define a mapping
$\Psi:\boldsymbol{\Pi}\xrightarrow{}\mathcal{M}$ as, given a policy
$\pi^{j}\in\Pi^{j}$, the mean field state estimate
$\boldsymbol{\mu}^{j}\triangleq\Psi(\pi^{j})$ can be constructed as,

$\begin{array}[]{l}\mu^{j}_{t+1}(\cdot)=\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}p(\cdot|s^{j}_{t},a^{j}_{t},\mu_{t})\mathcal{P}^{\pi^{j}}(a^{j}_{t}|s^{j}_{t},\mu^{j}_{t})\mu^{j}_{t}(s^{j}_{t}).\end{array}$
(6)

Here $\mathcal{P}^{\pi^{j}}$ is a probability measure induced by $\pi^{j}$.
Later (in Theorem 1) we will prove that restricting ourselves to Markov
policies is sufficient in a DMFG, and hence $\mathcal{P}^{\pi^{j}}=\pi^{j}$.

Now, we can define the _decentralized mean field equilibrium_ (DMFE) which is
the solution concept for this game.

######  Definition 1.

The decentralized mean field equilibrium of an agent $j$ is represented as a
pair $(\pi^{j}_{*}$, $\mu^{j}_{*})\in\Pi^{j}\times\mathcal{M}$ if
$\pi^{j}_{*}\in\Phi(\mu^{j}_{*})$ and $\mu^{j}_{*}=\Psi(\pi^{j}_{*})$. Here
$\pi^{j}_{*}$ is the best response to $\mu^{j}_{*}$ and $\mu^{j}_{*}$ is the
mean field estimate of $j$ when it plays $\pi^{j}_{*}$.

The important distinction between DMFE and centralized concepts, such as NE
and MFE, is that DMFE does not rely on the policy information of other agents.
MFE requires all agents to play the same policy, and NE requires all agents to
have access to other agents’ policies. DMFE has no such constraints. Hence,
this decentralized solution concept is more practical than NE and MFE. In
Appendix F, we summarize the major differences between the DMFG, MFG and MFRL.

##  5 Theoretical Results

We provide a set of theorems that will first guarantee the existence of the
DMFE in a DMFG. Further, we will show that a simple $Q$-learning update will
converge to a fixed point representing the DMFE. We will borrow relevant
results from prior works in centralized MFGs in our theoretical guarantees.
Particularly, we aim to adapt the results and proof techniques in works by
Saldi, Basar, and Raginsky (2018), Lasry and Lions (2007), and Anahtarci,
Kariksiz, and Saldi (2019) to the decentralized setting. The statements of all
our theorems are given here, while the proofs are in Appendices A – E.

Similar to an existing result from centralized MFG (Lasry and Lions 2007), in
the DMFG, restricting policies to only Markov policies would not lead to any
loss of optimality. We use $\Pi^{j}_{M}$ to denote the set of Markov policies
for the agent $j$.

######  Theorem 1.

For any mean field, $\boldsymbol{\mu}\in\mathcal{M}$, and an agent
$j\in\\{1,\ldots,N\\}$, we have,

$\sup_{\pi^{j}\in\Pi^{j}}J^{j}_{\boldsymbol{\mu}}(\pi^{j})=\sup_{\pi^{j}\in\Pi^{j}_{M}}J^{j}_{\boldsymbol{\mu}}(\pi^{j}).$
(7)

Next, we show the existence of a DMFE under a set of assumptions similar to
those previously used in the centralized MFG (Lasry and Lions 2007; Saldi,
Basar, and Raginsky 2018). The assumptions pertain to bounding the reward
function and imposing restrictions on the nature of the mean field (formal
statements in Appendix B). We do not need stronger assumptions than those
previously considered for the MFGs.

######  Theorem 2.

An agent $j\in\\{1,\ldots,N\\}$ in the DMFG admits a decentralized mean field
equilibrium $(\pi^{j}_{*},\mu^{j}_{*})\in\Pi^{j}\times\mathcal{M}$.

We use $\mathcal{C}$ to denote a set containing bounded functions in
$\mathcal{S}$. Now, we define a decentralized mean field operator ($H$),

$\begin{array}[]{l}H:\mathcal{C}\times\mathcal{P}(\mathcal{S})\ni(Q^{j},\boldsymbol{\mu}^{j})\\\
\\\
\quad\quad\quad\xrightarrow{}(H_{1}(Q^{j},\boldsymbol{\mu}^{j}),H_{2}(Q^{j},\boldsymbol{\mu}^{j}))\in\mathcal{C}\times\mathcal{P}(\mathcal{S})\end{array}$
(8)

where

$\begin{array}[]{l}H_{1}(Q^{j},\boldsymbol{\mu}^{j})(s^{j}_{t},a^{j}_{t})\triangleq
r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})\\\ \\\
\quad+\beta\bigintss_{\mathcal{S}}Q^{j}_{\max_{a^{j}}}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\end{array}$
(9)

$\begin{array}[]{l}H_{2}(Q^{j},\boldsymbol{\mu}^{j})(\cdot)\\\
\quad\quad\quad\quad\triangleq\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}p\Big{(}\cdot|s^{j}_{t},\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t}),\mu_{t}\Big{)}\mu^{j}_{t}(s)\end{array}$
(10)

for an agent $j$. Here, $\pi^{j}$ is a maximiser of the operator $H_{1}$.

For the rest of the theoretical results, we consider a set of assumptions
different from those needed for Theorem 2. Here we assume that the reward and
transition functions are Lipschitz continuous with a suitable Lipschitz
constant. The Lipschitz continuity assumption is quite common in the mean
field literature (Yang et al. 2018; Lasry and Lions 2007; Subramanian et al.
2020). We also consider some further assumptions regarding the nature of
gradients of the value function (formal statements in Appendix C). All
assumptions are similar to those considered before for the analysis in the
centralized MFGs (Lasry and Lions 2007; Anahtarci, Kariksiz, and Saldi 2019;
Huang 2010). First, we provide a theorem regarding the nature of operator $H$.
Then, we provide another theorem showing that $H$ is a contraction.

######  Theorem 3.

The decentralized mean field operator $H$ is well-defined, i.e., this operator
maps $\mathcal{C}\times\mathcal{P}(\mathcal{S})$ to itself.

######  Theorem 4.

Let $\mathcal{B}$ represent the space of bounded functions in $\mathcal{S}$.
Then the mapping
$H:\mathcal{C}\times\mathcal{P}(\mathcal{S})\xrightarrow{}\mathcal{C}\times\mathcal{P}(\mathcal{S})$
is a contraction in the norm of $\mathcal{B}(\mathcal{S})$.

Since $H$ is a contraction, by the Banach fixed point theorem (Shukla,
Balasubramanian, and Pavlović 2016), we can obtain that fixed point using the
$Q$ iteration algorithm given by Alg. 1. We provide this result in the next
theorem.

Algorithm 1 Q-learning for DMFG

1: For each agent $j\in\\{1,\ldots,N\\}$, start with initial $Q$-function
$Q^{j}_{0}$ and the initial mean field state estimate $\mu^{j}_{0}$

2: while $(Q^{j}_{n},\mu^{j}_{n})\neq(Q^{j}_{n-1},\mu^{j}_{n-1})$ do

3: $(Q^{j}_{n+1},\mu^{j}_{n+1})=H(Q^{j}_{n},\mu^{j}_{n})$

4: end while

5: Return the fixed point $(Q^{j}_{*},\mu^{j}_{*})$ of $H$

######  Theorem 5.

Let the $Q$-updates in Algorithm 1 converge to $(Q^{j}_{*},\mu_{*}^{j})$ for
an agent $j\in\\{1,\ldots,N\\}$. Then, we can construct a policy $\pi^{j}_{*}$
from $Q^{j}_{*}$ using the relation,

$\pi^{j}_{*}(s^{j})=\arg\max_{a^{j}\in\mathcal{A}^{j}}Q^{j}_{*}(s^{j},a^{j},\mu^{j}_{*}).$
(11)

Then the pair $(\pi^{j}_{*},\mu_{*}^{j})$ is a DMFE.

Hence, from the above results, we have proved that a DMFG admits a DMFE, and
an iterative algorithm using $Q$-updates can arrive at this equilibrium. This
provides a fixed point for Alg. 1, to which the $Q$-values converge.

##  6 Algorithms

We will apply the idea of decentralized updates to the model-free MFRL
framework. We modify the update equations in MFRL (Section 2) and make them
decentralized, where agents only observe their local state and do not have
access to the immediate global mean field. Our new updates are:

$\begin{array}[]{l}Q^{j}(s^{j}_{t},a^{j}_{t},\mu^{j,a}_{t})\\\
\quad=(1-\alpha)Q^{j}(s^{j}_{t},a^{j}_{t},\mu^{j,a}_{t})+\alpha[r^{j}_{t}+\gamma
v^{j}(s^{j}_{t+1})]\end{array}$ (12) where $\displaystyle
v^{j}(s^{j}_{t+1})=\sum_{a^{j}_{t+1}}\pi^{j}(a^{j}_{t+1}|s^{j}_{t+1},\mu^{j,a}_{t+1})Q^{j}(s^{j}_{t+1},a^{j}_{t+1},\mu^{j,a}_{t+1})$
(13) $\displaystyle\mu^{j,a}_{t}=f^{j}(s^{j}_{t},\hat{\mu}^{j,a}_{t-1})$ (14)
$\displaystyle\mbox{and
}\pi^{j}(a^{j}_{t}|s^{j}_{t},\mu^{j,a}_{t})=\frac{\exp(-\hat{\beta}Q^{j}(s^{j}_{t},a^{j}_{t},\mu^{j,a}_{t}))}{\sum_{a^{j^{\prime}}_{t}\in
A^{j}}\exp(-\hat{\beta}Q^{j}(s^{j}_{t},a^{j^{\prime}}_{t},\mu^{j,a}_{t}))}$
(15)

Here, $s^{j}_{t}$ is the local state and $\mu^{j,a}_{t}$ is the mean field
action estimate for the agent $j$ at time $t$ and $\hat{\mu}^{j,a}_{t-1}$ is
the observed local mean field action of $j$ at $t-1$. Other variables have the
same meaning as Eq. 1 – Eq. 4. In Eq. 14, the mean field estimate for $j$ is
updated using a function of the current state and the previous local mean
field. Opponent modelling techniques commonly used in MARL (Hernandez-Leal,
Kartal, and Taylor 2019) can be used here. We use the technique of He and
Boyd-Graber (2016), that used a neural network to model the opponent agent(s).
In our case, we use a fully connected neural network (2 Relu layers of 50
nodes and an output softmax layer) to model the mean field action. The network
takes the current state and previous mean field action as inputs and outputs
the estimated current mean field. This network is trained using a mean square
error between the estimated mean field action from the network (Eq. 14) and
the observed local mean field (local observation of actions of other agents
$\hat{\mu}^{j,a}_{t}$) after action execution. The policy in Eq. 15 does not
suffer from the ‘chicken-and-egg’ problem of Eq. 4 since it depends on the
current mean field estimate, unlike MFRL which used the previous global mean
field in Eq. 4.

We provide a neural network-based $Q$-learning implementation for our update
equations, namely _Decentralized Mean Field Game $Q$-learning_ (DMFG-QL), and
an actor-critic implementation, _Decentralized Mean Field Game Actor-Critic_
(DMFG-AC). Detailed description of the algorithms are in Appendix H (see Algs.
2 and 3). A complexity analysis is in Appendix K, and hyperparameter details
are in Appendix J.

##  7 Experiments and Results

In this section we study the performance of our algorithms. The code for
experiments has been open-sourced (Subramanian 2021). We provide the important
elements of our domains here, while the complete details are in Appendix I.

The first five domains belong to the MAgent environment (Zheng et al. 2018).
We run the experiments in two phases, training and execution. Analogous to
experiments conducted in previous mean field studies (Yang et al. 2018;
Subramanian et al. 2020), all agents train against other agents playing the
same algorithm for 2000 games. This is similar to multiagent training using
self-play (Shoham, Powers, and Grenager 2003). The trained agents then enter
into an execution phase, where the trained policies are simply executed. The
execution is run for 100 games, where algorithms may compete against each
other. We consider three baselines, independent $Q$-learning (IL) (Tan 1993),
mean field $Q$-learning (MFQ) (Yang et al. 2018), and mean field actor-critic
(MFAC) (Yang et al. 2018). Each agent in our implementations learns in a
decentralized fashion, where it maintains its own networks and learns from
local experiences. This is unlike centralized training in prior works (Yang et
al. 2018; Guo et al. 2019). We repeat experiments 30 times, and report the
mean and standard deviation. Wall clock times are given in Appendix M.

First, we consider the mixed cooperative-competitive Battle game (Zheng et al.
2018). This domain consists of two teams of 25 agents each. Each agent is
expected to cooperate with agents within the team and compete against agents
of the other team to win the battle. For the training phase, we plot the
cumulative rewards per episode obtained by the agents of the first team for
each algorithm in Fig. 1(a). The performance of the second team is also
similar (our environment is not zero-sum). From the results, we see that DMFG-
QL performs best while the others fall into a local optimum and do not get the
high rewards. The DMFG-AC algorithm comes second. It has been noted previously
(Yang et al. 2018) that $Q$-learning algorithms often perform better compared
to their actor-critic counterparts in mean field environments. MFQ and MFAC
(using the previous mean field information) performs poorly compared to DMFG-
QL and DMFG-AC (using the current estimates). Finally, IL loses out to others
due to its independent nature. In execution, one team trained using one
algorithm competes against another team from a different algorithm. We plot
the percentage of games won by each algorithm in a competition against DMFG-QL
and DMFG-AC. A game is won by the team that kills more of its opponents. The
performances are in Fig. 1(b) and (c), where DMFG-QL performs best. In
Appendix G, we show that DFMG-QL can accurately model the true mean field in
the Battle game.

(a)  Training

(b) Execution vs. DMFG-QL

(c) Execution vs. DMFG-AC

Figure 1: Battle results. In (a) solid lines show average and shaded regions
represent standard deviation. In (b) and (c) bars are average and black lines
represent standard deviation.

The second domain is the heterogeneous Combined Arms environment. This domain
is a mixed setting similar to Battle except that each team consists of two
different types of agents, ranged and melee, with distinct action spaces. Each
team has 15 ranged and 10 melee agents. This environment is different from
those considered in Subramanian et al. (2020), which formulated each team as a
distinct type, where agents within a team are homogeneous. The ranged agents
are faster and attack further, but can be killed quickly. The melee agents are
slower but are harder to kill. We leave out MFQ and MFAC for this experiment,
since both these algorithms require the presence of fully homogeneous agents.
The experimental procedure is the same as in Battle. From the results we see
that DMFG-QL performs best in both phases (see Fig. 2).

(a)  Training

(b) Execution

Figure 2: Combined Arms results

Next is the fully competitive Gather environment. This contains 30 agents
trying to capture limited food. All the agents compete against each other for
capturing food and could resort to killing others when the food becomes
scarce. We plot the average rewards obtained by each of the five algorithms in
the training phase (Fig. 3(a)). DMFG-QL once again obtains the maximum
performance. In competitive environments, actively formulating the best
responses to the current strategies of opponents is crucial for good
performances. Predictably, the MFQ and MFAC algorithms (relying on previous
information) lose out. For execution, we sample (at random) six agents from
each of the five algorithms to make a total of 30. We plot the percentage of
games won by each algorithm in a total of 100 games. A game is determined to
have been won by the agent obtaining the most rewards. Again, DMFG-QL shows
the best performance during execution (Fig. 3(b)).

(a)  Training

(b) Execution

Figure 3: Gather results

The next domain is a fully cooperative Tiger-Deer environment. In this
environment, a team of tigers aims to kill deer. The deer are assumed to be
part of the environment moving randomly, while the tigers are agents that
learn to coordinate with each other to kill the deer. At least two tigers need
to attack a deer in unison to gain large rewards. Our environment has 20
tigers and 101 deer. In the training phase, we plot the average reward
obtained by the tigers (Fig. 4(a)). The performance of MFQ almost matches that
of DMFG-QL and the performance of DMFG-AC matches MFAC. In a cooperative
environment, best responses to actively changing strategies of other agents
are not as critical as in competitive environments. Here all agents aid each
other and using the previous time information (as done in MFQ and MFAC) does
not hurt performance as much. For execution, a set of 20 tigers from each
algorithm execute their policy for 100 games. We plot the average number of
deer killed by the tigers for each algorithm. DMFG-QL gives the best
performance (Fig. 4(b)).

(a)  Training

(b)  Execution

Figure 4: Tiger-Deer results

The next domain is the continuous action Waterworld domain, first introduced
by Gupta, Egorov, and Kochenderfer (2017). This is also a fully cooperative
domain similar to Tiger-Deer, where a group of 25 pursuer agents aim to
capture a set of food in the environment while actively avoiding poison. The
action space corresponds to a continuous thrust variable. We implement DMFG-AC
in this domain, where the mean field is a mixture of Dirac deltas of actions
taken by all agents. The experimental procedure is the same as Tiger-Deer. For
this continuous action space environment, we use proximal policy optimization
(PPO) (Schulman et al. 2017) and deep deterministic policy gradient (DDPG)
(Lillicrap et al. 2016), as baselines. We see that DMFG-AC obtains the best
performance in both phases (refer to Fig. 5(a) and (b)).

(a)  Training

(b)  Execution

Figure 5: Waterworld results

Our final environment is a real-world _Ride-pool Matching Problem_ (RMP)
introduced by Alonso-Mora et al. (2017). This problem pertains to improving
the efficiency of vehicles satisfying ride requests as part of ride-sharing
platforms such as UberPool. In our environment, ride requests come from the
open source New York Yellow Taxi dataset (NYYellowTaxi 2016). The road network
(represented as a grid with a finite set of nodes or road intersections)
contains a simulated set of vehicles (agents) that aim to serve the user
requests. Further details about this domain are in Appendix I. We consider two
baselines in this environment. The first is the method from Alonso-Mora et al.
(2017), which used a constrained optimization (CO) approach to match ride
requests to vehicles. This approach is hard to scale and is myopic in
assigning requests (it does not consider future rewards). The second baseline
is the Neural Approximate Dynamic Programming (NeurADP) method from Shah,
Lowalekar, and Varakantham (2020), which used a (centralized) DQN algorithm to
learn a value function for effective mapping of requests. This approach
assumes all agents are homogenous (i.e., having the same capacity and
preferences), which is impractical. To keep comparisons fair, we consider a
decentralized version of NeurADP as our baseline. Finally, we implement DMFG-
QL for this problem where the mean-field corresponds to the distribution of
ride requests at every node in the environment.

Similar to prior approaches (Lowalekar, Varakantham, and Jaillet 2019; Shah,
Lowalekar, and Varakantham 2020), we use the service rate (total percentage of
requests served) as the comparison metric. We train NeurADP and DMFG-QL using
a set of eight consecutive days of training data and test all the performances
in a previously unseen test set of six days. The test results are reported as
an average (per day) of performances in the test set pertaining to three
different hyperparameters. The first is the capacity of the vehicle ($c$)
varied from 8 to 12, the second is the maximum allowed waiting time ($\tau$)
varied from 520 seconds to 640 seconds, and the last is the number of vehicles
($N$), varied from 80 to 120. The results in Figs. 6(a-c) show that DMFG-QL
outperforms the baselines in all our test cases. The mean field estimates in
DMFG-QL help predict the distribution of ride requests in the environment,
based on which agents can choose ride requests strategically. If agents choose
orders that lead to destinations with a high percentage of requests, they will
be able to serve more requests in the future. Thus, DMFG-QL outperforms the
NeurADP method (which does not maintain a mean field). We note that the
service rate for all algorithms is low in this study (10% – 30%), since we are
considering fewer vehicles compared to prior works (Shah, Lowalekar, and
Varakantham 2020) due to the computational requirements of being
decentralized. In practice our training is completely parallelizable and this
is not a limitation of our approach. Also, from Fig. 6(c), an increase in the
number of vehicles, increases the service rate. In Fig. 6(d) we plot the
performance of the three algorithms for a single test day (24 hours — midnight
to midnight). During certain times of the day (e.g., 5 am), the ride demand is
low, and all approaches satisfy a large proportion of requests. However,
during the other times of the day, when the demand is high, the DMFG-QL
satisfies more requests than the baselines, showing its relative superiority.

(a) # of Vehicles

(b) Maximum Pickup Delay

(c) Capacity

(d) Single Day Test

Figure 6: Results for the ride-sharing experiment. For (a), (b) and (c), we
start with a prototypical configuration of $c$=10, $\tau$ = 580, and $N$ =
100, and then vary the different parameters. Figures (a), (b) and (c) share
the same legend given in (a).

##  8 Conclusion

In this paper, we relaxed two strong assumptions in prior work on using mean
field methods in RL. We introduced the DMFG framework, where agents are not
assumed to have global information and are not homogeneous. All agents learn
in a decentralized fashion, which contrasts with centralized procedures in
prior work. Theoretically, we proved that the DMFG will have a suitable
solution concept, DMFE. Also, we proved that a $Q$-learning based algorithm
will find the DMFE. Further, we provided a principled method to address the
‘chicken-and-egg’ problem in MFRL, and demonstrated performances in a variety
of environments (including RMP).

For future work, we would like to extend our theoretical analysis to the
function approximation setting and analyze the convergence of policy gradient
algorithms. Empirically, we could consider other real-world applications like
autonomous driving and problems on demand and supply optimization.

## Acknowledgements

Resources used in preparing this research at the University of Waterloo were
provided by the province of Ontario and the government of Canada through
CIFAR, NRC, NSERC and companies sponsoring the Vector Institute. Part of this
work has taken place in the Intelligent Robot Learning (IRL) Lab at the
University of Alberta, which is supported in part by research grants from the
Alberta Machine Intelligence Institute (Amii); a Canada CIFAR AI Chair, CIFAR;
Compute Canada; and NSERC.

## References

  * Adlakha, Johari, and Weintraub (2015) Adlakha, S.; Johari, R.; and Weintraub, G. Y. 2015.  Equilibria of dynamic games with many players: Existence, approximation, and market structure.  _Journal of Economic Theory_ , 156: 269–316.
  * Alonso-Mora et al. (2017) Alonso-Mora, J.; Samaranayake, S.; Wallar, A.; Frazzoli, E.; and Rus, D. 2017\.  On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment.  _Proceedings of National Academy of Science USA_ , 114(3): 462–467.
  * Anahtarci, Kariksiz, and Saldi (2019) Anahtarci, B.; Kariksiz, C. D.; and Saldi, N. 2019.  Value Iteration Algorithm for Mean-field Games.  _arXiv preprint arXiv:1909.01758_.
  * Bartle (2014) Bartle, R. G. 2014.  _The elements of integration and Lebesgue measure_.  John Wiley & Sons.
  * Busoniu, Babuska, and De Schutter (2006) Busoniu, L.; Babuska, R.; and De Schutter, B. 2006.  Multi-agent reinforcement learning: A survey.  In _2006 9th International Conference on Control, Automation, Robotics and Vision_ , 1–6. IEEE.
  * Cardaliaguet and Hadikhanloo (2017) Cardaliaguet, P.; and Hadikhanloo, S. 2017.  Learning in mean field games: the fictitious play.  _ESAIM: Control, Optimisation and Calculus of Variations_ , 23(2): 569–591.
  * Carmona, Laurière, and Tan (2019a) Carmona, R.; Laurière, M.; and Tan, Z. 2019a.  Linear-quadratic mean-field reinforcement learning: convergence of policy gradient methods.  _arXiv preprint arXiv:1910.04295_.
  * Carmona, Laurière, and Tan (2019b) Carmona, R.; Laurière, M.; and Tan, Z. 2019b.  Model-free mean-field reinforcement learning: mean-field MDP and mean-field Q-learning.  _arXiv preprint arXiv:1910.12802_.
  * Elie et al. (2020) Elie, R.; Pérolat, J.; Laurière, M.; Geist, M.; and Pietquin, O. 2020.  On the Convergence of Model Free Learning in Mean Field Games.  In _AAAI_ , 7143–7150.
  * Elliott, Li, and Ni (2013) Elliott, R.; Li, X.; and Ni, Y.-H. 2013.  Discrete time mean-field stochastic linear-quadratic optimal control problems.  _Automatica_ , 49(11): 3222–3233.
  * Fu et al. (2019) Fu, Z.; Yang, Z.; Chen, Y.; and Wang, Z. 2019.  Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games.  In _ICLR_.
  * Gomes, Mohr, and Souza (2010) Gomes, D. A.; Mohr, J.; and Souza, R. R. 2010.  Discrete time, finite state space mean field games.  _Journal de mathématiques pures et appliquées_ , 93(3): 308–328.
  * Guo et al. (2019) Guo, X.; Hu, A.; Xu, R.; and Zhang, J. 2019.  Learning mean-field games.  In _NeurIPS_ , 4966–4976.
  * Gupta, Egorov, and Kochenderfer (2017) Gupta, J. K.; Egorov, M.; and Kochenderfer, M. 2017.  Cooperative multi-agent control using deep reinforcement learning.  In _AAMAS_ , 66–83. Springer.
  * Hadikhanloo and Silva (2019) Hadikhanloo, S.; and Silva, F. J. 2019.  Finite mean field games: fictitious play and convergence to a first order continuous mean field game.  _Journal de Mathématiques Pures et Appliquées_ , 132: 369–397.
  * Hajek and Raginsky (2019) Hajek, B.; and Raginsky, M. 2019.  Statistical learning theory.  _Lecture Notes_ , 387.
  * He and Boyd-Graber (2016) He, H.; and Boyd-Graber, J. L. 2016.  Opponent Modeling in Deep Reinforcement Learning.  In _ICML_ , volume 48, 1804–1813. JMLR.org.
  * Hernandez-Leal, Kartal, and Taylor (2019) Hernandez-Leal, P.; Kartal, B.; and Taylor, M. E. 2019.  A survey and critique of multiagent deep reinforcement learning.  _Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS)_ , 33(6): 750–797.
  * Hernández-Lerma and Lasserre (2012) Hernández-Lerma, O.; and Lasserre, J. B. 2012.  _Discrete-time Markov control processes: basic optimality criteria_ , volume 30.  Springer Science & Business Media.
  * Hinderer (1970) Hinderer, K. 1970.  Decision models.  In _Foundations of Non-stationary Dynamic Programming with Discrete Time Parameter_ , 78–83. Springer.
  * Hu and Wellman (2003) Hu, J.; and Wellman, M. P. 2003.  Nash Q-learning for general-sum stochastic games.  _Journal of machine learning research_ , 4(Nov): 1039–1069.
  * Huang (2010) Huang, M. 2010.  Large-population LQG games involving a major player: the Nash certainty equivalence principle.  _SIAM Journal on Control and Optimization_ , 48(5): 3318–3353.
  * Huang, Caines, and Malhamé (2003) Huang, M.; Caines, P. E.; and Malhamé, R. P. 2003.  Individual and mass behaviour in large population stochastic wireless power control problems: centralized and Nash equilibrium solutions.  In _42nd IEEE International Conference on Decision and Control_. IEEE.
  * Huang et al. (2006) Huang, M.; Malhamé, R. P.; Caines, P. E.; et al. 2006.  Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle.  _Communications in Information & Systems_, 6(3): 221–252.
  * Kakutani (1941) Kakutani, S. 1941.  A generalization of Brouwer’s fixed point theorem.  _Duke mathematical journal_ , 8(3): 457–459.
  * Kizilkale and Caines (2013) Kizilkale, A. C.; and Caines, P. E. 2013.  Mean Field Stochastic Adaptive Control.  _IEEE Trans. Autom. Control._ , 58(4): 905–920.
  * Konda and Tsitsiklis (1999) Konda, V. R.; and Tsitsiklis, J. N. 1999.  Actor-Critic Algorithms.  In _NeurIPS_. The MIT Press.
  * Lasry and Lions (2007) Lasry, J.-M.; and Lions, P.-L. 2007.  Mean field games.  _Japanese journal of mathematics_ , 2(1): 229–260.
  * Lattimore and Szepesvári (2020) Lattimore, T.; and Szepesvári, C. 2020.  _Bandit algorithms_.  Cambridge University Press.
  * Li et al. (2019) Li, M.; Qin, Z.; Jiao, Y.; Yang, Y.; Wang, J.; Wang, C.; Wu, G.; and Ye, J. 2019\.  Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learning.  In _The World Wide Web Conference, WWW 2019_. ACM.
  * Lillicrap et al. (2016) Lillicrap, T. P.; Hunt, J. J.; Pritzel, A.; Heess, N.; Erez, T.; Tassa, Y.; Silver, D.; and Wierstra, D. 2016.  Continuous control with deep reinforcement learning.  In _ICLR_.
  * Lowalekar, Varakantham, and Jaillet (2019) Lowalekar, M.; Varakantham, P.; and Jaillet, P. 2019.  ZAC: A Zone Path Construction Approach for Effective Real-Time Ridesharing.  In _ICAPS_ , 528–538. AAAI Press.
  * Mguni, Jennings, and de Cote (2018) Mguni, D.; Jennings, J.; and de Cote, E. M. 2018.  Decentralised Learning in Systems With Many, Many Strategic Agents.  In _AAAI_ , 4686–4693. AAAI Press.
  * Mnih et al. (2015) Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M.; Fidjeland, A. K.; Ostrovski, G.; et al. 2015\.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540): 529.
  * Nash (1951) Nash, J. F. 1951.  _Non-Cooperative Games_.  Princeton University Press.
  * Neumann (1928) Neumann, J. v. 1928.  Zur theorie der gesellschaftsspiele.  _Mathematische annalen_ , 100(1): 295–320.
  * NYYellowTaxi (2016) NYYellowTaxi. 2016.  New York yellow taxi dataset.  http://www.nyc.gov/html/tlc/html/about/triprecorddata.shtml.  [Online; accessed 19-June-2021].
  * Perrin et al. (2021) Perrin, S.; Laurière, M.; Pérolat, J.; Geist, M.; Élie, R.; and Pietquin, O. 2021.  Mean Field Games Flock! The Reinforcement Learning Way.  In _IJCAI_ , 356–362.
  * Puterman (1994) Puterman, M. L. 1994.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  Wiley Series in Probability and Statistics. Wiley.  ISBN 978-0-47161977-2.
  * Ropke and Cordeau (2009) Ropke, S.; and Cordeau, J. 2009.  Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows.  _Transportation Science_ , 43(3): 267–286.
  * Saldi, Basar, and Raginsky (2018) Saldi, N.; Basar, T.; and Raginsky, M. 2018.  Discrete-time risk-sensitive mean-field games.  _arXiv preprint arXiv:1808.03929_.
  * Schulman et al. (2017) Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; and Klimov, O. 2017.  Proximal policy optimization algorithms.  In _arXiv preprint arXiv:1707.06347_.
  * Shah, Lowalekar, and Varakantham (2020) Shah, S.; Lowalekar, M.; and Varakantham, P. 2020.  Neural Approximate Dynamic Programming for On-Demand Ride-Pooling.  In _AAAI_ , 507–515. AAAI Press.
  * Shoham, Powers, and Grenager (2003) Shoham, Y.; Powers, R.; and Grenager, T. 2003.  Multi-agent reinforcement learning: a critical survey.  Technical report, Technical report, Stanford University.
  * Shukla, Balasubramanian, and Pavlović (2016) Shukla, S.; Balasubramanian, S.; and Pavlović, M. 2016.  A generalized Banach fixed point theorem.  _Bulletin of the Malaysian Mathematical Sciences Society_ , 39(4): 1529–1539.
  * Stanley (1971) Stanley, H. E. 1971.  Phase transitions and critical phenomena. Clarendon.
  * Subramanian and Mahajan (2019) Subramanian, J.; and Mahajan, A. 2019.  Reinforcement Learning in Stationary Mean-field Games.  In _AAMAS_ , 251–259. IFAAMAS.
  * Subramanian (2021) Subramanian, S. G. 2021.  Decentralized Mean Field Games.  https://github.com/Sriram94/DMFG.
  * Subramanian et al. (2020) Subramanian, S. G.; Poupart, P.; Taylor, M. E.; and Hegde, N. 2020.  Multi Type Mean Field Reinforcement Learning.  In _AAMAS_. IFAAMAS.
  * Subramanian et al. (2021) Subramanian, S. G.; Taylor, M. E.; Crowley, M.; and Poupart, P. 2021.  Partially Observable Mean Field Reinforcement Learning.  In _AAMAS_. ACM.
  * Sutton et al. (1999) Sutton, R. S.; McAllester, D. A.; Singh, S. P.; and Mansour, Y. 1999.  Policy Gradient Methods for Reinforcement Learning with Function Approximation.  In _NIPS_ , 1057–1063. The MIT Press.
  * Tan (1993) Tan, M. 1993.  Multi-agent reinforcement learning: Independent vs. cooperative agents.  In _ICML_.
  * Tanaka, Hori, and Wang (2003) Tanaka, K.; Hori, T.; and Wang, H. O. 2003.  A multiple Lyapunov function approach to stabilization of fuzzy control systems.  _IEEE Transactions on fuzzy systems_ , 11(4): 582–589.
  * Terry et al. (2020) Terry, J. K.; Black, B.; Jayakumar, M.; Hari, A.; Santos, L.; Dieffendahl, C.; Williams, N. L.; Lokesh, Y.; Sullivan, R.; Horsch, C.; and Ravi, P. 2020.  PettingZoo: Gym for Multi-Agent Reinforcement Learning.  In _arXiv preprint arXiv:2009.14471_.
  * Wang et al. (2018) Wang, Z.; Qin, Z. T.; Tang, X.; Ye, J.; and Zhu, H. 2018.  Deep Reinforcement Learning with Knowledge Transfer for Online Rides Order Dispatching.  In _ICDM_ , 617–626. IEEE Computer Society.
  * Watkins and Dayan (1992) Watkins, C. J.; and Dayan, P. 1992.  Q-learning.  _Machine Learning_ , 8(3-4): 279–292.
  * Więcek (2020) Więcek, P. 2020.  Discrete-time ergodic mean-field games with average reward on compact spaces.  _Dynamic Games and Applications_ , 10(1): 222–256.
  * Więcek and Altman (2015) Więcek, P.; and Altman, E. 2015.  Stationary anonymous sequential games with undiscounted rewards.  _Journal of optimization theory and applications_ , 166(2): 686–710.
  * Xu et al. (2018) Xu, Z.; Li, Z.; Guan, Q.; Zhang, D.; Li, Q.; Nan, J.; Liu, C.; Bian, W.; and Ye, J. 2018.  Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach.  In _KDD_. ACM.
  * Yang et al. (2017) Yang, J.; Ye, X.; Trivedi, R.; Xu, H.; and Zha, H. 2017.  Deep Mean Field Games for Learning Optimal Behavior Policy of Large Populations.  _CoRR_ , abs/1711.03156.
  * Yang et al. (2018) Yang, Y.; Luo, R.; Li, M.; Zhou, M.; Zhang, W.; and Wang, J. 2018.  Mean Field Multi-Agent Reinforcement Learning.  In _ICML_. PMLR.
  * Yang and Wang (2020) Yang, Y.; and Wang, J. 2020.  An Overview of Multi-Agent Reinforcement Learning from Game Theoretical Perspective.  _CoRR_ , abs/2011.00583.
  * Yin et al. (2014) Yin, H.; Mehta, P. G.; Meyn, S. P.; and Shanbhag, U. V. 2014.  Learning in Mean-Field Games.  _IEEE Trans. Autom. Control._ , 59(3): 629–644.
  * Zheng et al. (2018) Zheng, L.; Yang, J.; Cai, H.; Zhou, M.; Zhang, W.; Wang, J.; and Yu, Y. 2018.  MAgent: A many-agent reinforcement learning platform for artificial collective intelligence.  In _AAAI_.

##  Appendix A Proof of Theorem 1

For the proof, we will follow the idea of using discounted occupancy measures,
as discussed in Puterman (1994). Let us consider an agent
$j\in\\{1,\ldots,N\\}$. Let $\boldsymbol{\mu}\in\mathcal{M}$ and
$\pi^{j}\in\Pi^{j}$ be arbitrary. Then from the Ionescu-Tulcea theorem (see
Theorem 3.3 in Lattimore and Szepesvári (2020)), a mean field distribution
$\boldsymbol{\mu}$ on $\mathcal{S}$ and a policy $\pi^{j}$ defines a unique
probability measure $\mathcal{P}^{\pi^{j}}$ on
$\mathcal{S}\times\mathcal{A}^{j}$.

We will begin with a definition of a discounted occupancy measure for some
mean field $\boldsymbol{\mu}$. Consider an arbitrary policy
$\pi^{j}\in\Pi^{j}$. Then, the discounted occupancy measure
$\nu^{\pi^{j}}_{\boldsymbol{\mu}}\in\mathcal{F}(\mathcal{S}\times\mathcal{A})$
induced by this policy on the set $\mathcal{S}\times\mathcal{A}^{j}$ with mean
field $\boldsymbol{\mu}$ is given by the equation

$\nu^{\pi^{j}}(s^{j},a^{j}|\mu)=\sum_{t=0}^{\infty}\beta^{t}\mathcal{P}^{\pi^{j}}(s^{j}_{t}=s^{j},a^{j}_{t}=a^{j}|\mu_{t}=\mu).$
(16)

The discounted occupancy measure assigns a measure to the given state-action
pair, which is the infinite discounted sum of the process that has a mean
field of $\boldsymbol{\mu}$ and follows the policy $\pi^{j}$, with the agent
$j$ hitting at various times the state $s^{j}$ and taking the action $a^{j}$
at that state.

The discounted measure has a property that the value function can be
represented as a product of the immediate reward and the discounted occupancy
measure. To prove this, consider (from Eq. 5),

$\begin{array}[]{l}J^{j}_{\boldsymbol{\mu}}(\pi^{j})=\mathbb{E}^{\pi^{j}}[\sum_{t=0}^{\infty}\beta^{t}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})]\\\
\\\
=\bigintss_{(s^{j}\in\mathcal{S},a^{j}\in\mathcal{A}^{j})}\sum_{t=0}^{\infty}\beta^{t}\mathbb{E}^{\pi^{j}}[r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\mathcal{I}(s^{j}=s^{j}_{t},a^{j}=a^{j}_{t},\mu_{t}=\mu)]\\\
\\\
\overset{1}{=}\bigintss_{(s^{j}\in\mathcal{S},a^{j}\in\mathcal{A}^{j})}\sum_{t=0}^{\infty}\beta^{t}\mathbb{E}^{\pi^{j}}[r^{j}(s^{j},a^{j},\mu)\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\mathcal{I}((s^{j}_{t}=s^{j},a^{j}_{t}=a^{j},\mu_{t}=\mu)]\\\
\\\
\overset{2}{=}\bigintss_{(s^{j}\in\mathcal{S},a^{j}\in\mathcal{A}^{j})}r^{j}(s^{j},a^{j},\mu)\\\
\quad\quad\quad\quad\quad\sum_{t=0}^{\infty}\beta^{t}\mathbb{E}^{\pi^{j}}[\mathcal{I}(s^{j}_{t}=s^{j},a^{j}_{t}=a^{j},\mu_{t}=\mu)]\\\
\\\
=\bigintss_{(s^{j}\in\mathcal{S},a^{j}\in\mathcal{A}^{j})}r^{j}(s^{j},a^{j},\mu)\\\
\quad\quad\quad\quad\quad\quad\sum_{t=0}^{\infty}\beta^{t}\mathcal{P}^{\pi^{j}}(s^{j}_{t}=s^{j},a^{j}_{t}=a^{j}|\mu_{t}=\mu)\\\
\\\
=\bigintss_{(s^{j}\in\mathcal{S},a^{j}\in\mathcal{A}^{j})}r^{j}(s^{j},a^{j},\mu)\nu^{\pi^{j}}(s^{j},a^{j}|\mu)\\\
\\\ \end{array}$ (17)

Here the notation $\mathcal{I}(x)$ is an indicator function, which equals 1 if
the $x$ is true and 0 if $x$ is false. The sum of all indicators for all the
state-action pairs at a given $t$ equals 1. The step (1) uses this property of
the indicator function, to drop the time indices of the reward function. The
step (2) is from Lebesgue’s dominated convergence theorem (Bartle 2014).

Now we state a lemma needed for our proof.

######  Lemma 1.

For an agent $j\in\\{1,\ldots,N\\}$ and policy $\pi^{j}$, given mean field
$\boldsymbol{\mu}$, there exists a Markov policy $\hat{\pi}^{j}\in\Pi^{j}_{M}$
such that

$\nu^{\hat{\pi}^{j}}(s^{j},a^{j}|\mu)=\nu^{\pi^{j}}(s^{j},a^{j}|\mu)$ (18)

###### Proof.

For a mean field $\boldsymbol{\mu}$, we define an occupancy measure over the
state space
$\tilde{\nu}^{\pi^{j}}(s^{j}|\mu)\triangleq\bigintss_{a^{j}}\nu^{\pi^{j}}(s^{j},a^{j}|\mu)$.

Now consider a Markov policy $\hat{\pi}^{j}$ as follows,

$\begin{array}[]{l}\hat{\pi}^{j}(a^{j}|s^{j},\mu)=\frac{\nu^{\pi^{j}}(s^{j},a^{j}|\mu)}{\tilde{\nu}^{\pi^{j}}(s^{j}|\mu)},\quad\textrm{
if }\tilde{\nu}^{\pi^{j}}(s^{j},\mu)\neq 0\\\ \\\ \textrm{and}\\\ \\\
\hat{\pi}^{j}(a^{j}|s^{j},\mu)=\pi^{j}_{0}(a^{j}),\quad\textrm{ if
}\tilde{\nu}^{\pi^{j}}(s^{j},\mu)=0\end{array}$ (19)

Here, $\pi^{j}_{0}(a^{j})\in\Pi^{j}_{M}$ is an arbitrary policy.

Consider,

$\begin{array}[]{l}\tilde{\nu}^{\hat{\pi}^{j}}(s^{j}|\mu)=\bigintss_{a^{j}}\nu^{\hat{\pi}^{j}}(s^{j},a^{j}|\mu)\\\
\\\
=\bigintss_{a^{j}}\sum_{t=0}^{\infty}\beta^{t}\mathcal{P}^{\hat{\pi}^{j}}(s^{j}_{t}=s^{j},a^{j}_{t}=a^{j}|\mu_{t}=\mu)\\\
\\\
\overset{1}{=}\sum_{t=0}^{\infty}\beta^{t}\mathcal{P}^{\hat{\pi}^{j}}(s^{j}_{t}=s^{j}|\mu_{t}=\mu)\\\
\\\
=\nu_{0}(s^{j})+\sum_{t=1}^{\infty}\beta^{t}\mathcal{P}^{\hat{\pi}^{j}}(s^{j}_{t}=s^{j}|\mu_{t}=\mu)\\\
\\\ =\nu_{0}(s^{j})+\beta\sum_{t=1}^{\infty}\beta^{t-1}\bigintss_{s^{\prime
j}\in\mathcal{S}}\bigintss_{a^{\prime j}\in\mathcal{A}^{j}}\\\ \\\
\mathcal{P}^{\hat{\pi}^{j}}[s_{t-1}^{j}=s^{\prime j},a_{t-1}^{j}=a^{\prime
j}|\mu_{t-1}=\mu^{\prime}]p(s^{j}|s^{\prime j},a^{\prime j},\mu^{\prime})\\\
\\\ =\nu_{0}(s^{j})+\beta\sum_{t=1}^{\infty}\beta^{t-1}\bigintss_{s^{\prime
j}\in\mathcal{S}}\\\ \\\
\quad\quad\quad\quad\quad\quad\quad\quad\mathcal{P}^{\hat{\pi}^{j}}[s_{t-1}=s^{\prime}|\mu_{t-1}=\mu^{\prime}]\\\
\\\ \quad\quad\quad\quad\quad\quad\bigintss_{a^{\prime
j}\in\mathcal{A}^{j}}\hat{\pi}^{j}(a^{\prime j}|s^{\prime
j},\mu^{\prime})p(s^{j}|s^{\prime j},a^{\prime j},\mu^{\prime})\\\ \\\
=\nu_{0}(s^{j})\\\ \\\ +\beta\bigintss_{s^{\prime
j}\in\mathcal{S}}\sum_{t=1}^{\infty}\beta^{t-1}\mathcal{P}^{\hat{\pi}^{j}}[s^{j}_{t-1}=s^{\prime
j}|\mu_{t-1}=\mu^{\prime}]\\\ \\\ \bigintss_{a^{\prime
j}\in\mathcal{A}^{j}}\hat{\pi}^{j}(a^{\prime j}|s^{\prime
j},\mu^{\prime})p(s^{j}|s^{\prime j},a^{\prime j},\mu_{t-1}=\mu^{\prime})\\\
\\\ \overset{2}{=}\nu_{0}(s^{j})+\beta\bigintss_{s^{\prime
j}\in\mathcal{S}}\tilde{\nu}^{\hat{\pi}^{j}}(s^{\prime j}|\mu^{\prime})\\\ \\\
\quad\quad\quad\quad\bigintss_{a^{\prime
j}\in\mathcal{A}^{j}}\hat{\pi}^{j}(a^{\prime j}|s^{\prime
j},\mu^{\prime})p(s^{j}|s^{\prime j},a^{\prime j},\mu^{\prime})\end{array}$
(20)

Here $\nu_{0}(s^{j})$ is the initial distribution of the state of the agent
$j$. To obtain expression (2), see that this follows from expression (1).

Now consider,

$\begin{array}[]{l}\tilde{\nu}^{\pi^{j}}(s^{j}|\mu)=\sum_{t=0}^{\infty}\beta^{t}\mathcal{P}^{\pi^{j}}(s^{j}_{t}=s^{j}|\mu_{t}=\mu)\\\
\\\
=\nu_{0}(s^{j})+\sum_{t=1}^{\infty}\beta^{t}\mathcal{P}^{\pi^{j}}(s^{j}_{t}=s^{j}|\mu_{t}=\mu)\\\
\\\ =\nu_{0}(s^{j})+\beta\sum_{t=1}^{\infty}\beta^{t-1}\bigintss_{s^{\prime
j}\in\mathcal{S}}\bigintss_{a^{\prime j}\in\mathcal{A}^{j}}\\\ \\\
\mathcal{P}^{\pi^{j}}[s^{j}_{t-1}=s^{\prime j},a^{j}_{t-1}=a^{\prime
j}|\mu_{t-1}=\mu^{\prime}]p(s^{j}|s^{\prime j},a^{\prime j},\mu^{\prime})\\\
\\\ =\nu_{0}(s^{j})+\beta\bigintss_{s^{\prime
j}\in\mathcal{S}}\bigintss_{a^{\prime
j}\in\mathcal{A}^{j}}\sum_{t=1}^{\infty}\beta^{t-1}\\\ \\\
\mathcal{P}^{\pi^{j}}[s^{j}_{t-1}=s^{\prime j},a^{j}_{t-1}=a^{\prime
j}|\mu_{t-1}=\mu^{\prime}]p(s^{j}|s^{\prime j},a^{\prime j},\mu^{\prime})\\\
\\\ \overset{1}{=}\nu_{0}(s^{j})\\\ \\\ \quad\quad+\beta\bigintss_{s^{\prime
j}\in\mathcal{S}}\bigintss_{a^{\prime
j}\in\mathcal{A}^{j}}\nu^{\pi^{j}}(s^{\prime j},a^{\prime
j}|\mu^{\prime})p(s^{j}|s^{\prime j},a^{\prime j},\mu^{\prime})\\\ \\\
\overset{2}{=}\nu_{0}(s^{j})+\beta\bigintss_{s^{\prime
j}\in\mathcal{S}}\bigintss_{a^{\prime j}\in\mathcal{A}^{j}}\\\ \\\
\quad\quad\quad\quad\quad\hat{\pi}^{j}(a^{\prime j}|s^{\prime
j},\mu^{\prime})\tilde{\nu}^{\pi^{j}}(s^{\prime
j}|\mu^{\prime})p(s^{j}|s^{\prime j},a^{\prime j},\mu^{\prime})\\\ \\\
=\nu_{0}(s^{j})+\beta\bigintss_{s^{\prime
j}\in\mathcal{S}}\tilde{\nu}^{\pi^{j}}(s^{\prime j}|\mu^{\prime})\\\ \\\
\quad\quad\quad\quad\quad\quad\quad\quad\bigintss_{a^{\prime
j}\in\mathcal{A}^{j}}\hat{\pi}^{j}(a^{\prime j}|s^{\prime
j},\mu^{\prime})p(s^{j}|s^{\prime j},a^{\prime
j},\mu^{\prime})\par\end{array}$ (21)

The (1) is from Eq. 16 and (2) is from Eq. 19. From both Eq. 21 and Eq. 20, we
find that both the discounted state occupation frequency can be recursively
expressed as a term depending on the state occupation frequency at the
previous time step and a few other terms that are the same for both the Eq. 20
and Eq. 21. Since the initial state distribution is the same for both
policies, we can conclude that
$\tilde{\nu}^{\hat{\pi}^{j}}(s^{j}|\mu)=\tilde{\nu}^{\pi^{j}}(s^{j}|\mu)$.

Now, consider

$\begin{array}[]{l}\nu^{\hat{\pi}^{j}}(s^{j},a^{j}|\mu)=\sum_{t=0}^{\infty}\beta^{t}\mathcal{P}^{\hat{\pi}^{j}}(s^{j}_{t}=s^{j},a^{j}_{t}=a^{j}|\mu_{t}=\mu)\\\
\\\
=\sum_{t=0}^{\infty}\beta^{t}\mathcal{P}^{\hat{\pi}^{j}}(a^{j}_{t}=a^{j}|s^{j}_{t}=s^{j},\mu_{t}=\mu)\\\
\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\mathcal{P}^{\hat{\pi}^{j}}(s^{j}_{t}=s^{j}|\mu_{t}=\mu)\\\
\\\
=\sum_{t=0}^{\infty}\beta^{t}\hat{\pi}^{j}(a^{j}_{t}=a^{j}|s^{j}_{t}=s^{j},\mu_{t}=\mu)\\\
\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\mathcal{P}^{\hat{\pi}^{j}}(s^{j}_{t}=s^{j}|\mu_{t}=\mu)\end{array}$
(22)

Also, from Eq. 19, we have

$\begin{array}[]{l}\nu^{\pi^{j}}(s^{j},a^{j}|\mu)=\hat{\pi}^{j}(a^{j}|s^{j},\mu)\times\tilde{\nu}^{\pi^{j}}(s^{j}|\mu)\\\
\\\
=\hat{\pi}^{j}(a^{j}|s^{j},\mu)\times\tilde{\nu}^{\hat{\pi}^{j}}(s^{j}|\mu)\\\
\\\
=\hat{\pi}^{j}(a^{j}|s^{j},\mu)\sum_{t=0}^{\infty}\beta^{t}\mathcal{P}^{\hat{\pi}^{j}}(s^{j}_{t}=s^{j}|\mu_{t}=\mu)\\\
\\\
=\sum_{t=0}^{\infty}\beta^{t}\hat{\pi}^{j}(a^{j}|s^{j},\mu)\mathcal{P}^{\hat{\pi}^{j}}(s^{j}_{t}=s^{j}|\mu_{t}=\mu)\end{array}$
(23)

From Eq. 22 and Eq. 23 we find that
$\nu^{\hat{\pi}^{j}}(s^{j},a^{j}|\mu)=\nu^{\pi^{j}}(s^{j},a^{j}|\mu)$, due to
the property of the Markov policy $\hat{\pi}^{j}$.

∎

######  Theorem 1.

For any mean field, $\boldsymbol{\mu}\in\mathcal{M}$, and an agent
$j\in\\{1,\ldots,N\\}$, we have,

$\sup_{\pi^{j}\in\Pi^{j}}J^{j}_{\boldsymbol{\mu}}(\pi^{j})=\sup_{\pi^{j}\in\Pi^{j}_{M}}J^{j}_{\boldsymbol{\mu}}(\pi^{j}).$

###### Proof.

Now, we aim to show that
$\sup_{\pi^{j}\in\Pi^{j}}J^{j}_{\boldsymbol{\mu}}(\pi^{j})=\sup_{\pi^{j}\in\Pi^{j}_{M}}J^{j}_{\boldsymbol{\mu}}(\pi^{j})$.
Since $\Pi^{j}_{M}\subset\Pi^{j}$, we know that
$\sup_{\pi^{j}\in\Pi^{j}_{M}}J^{j}_{\boldsymbol{\mu}}(\pi^{j})\leq\sup_{\pi^{j}\in\Pi^{j}}J^{j}_{\boldsymbol{\mu}}(\pi^{j})$.
To show the equality we aim to prove
$\sup_{\pi^{j}\in\Pi^{j}_{M}}J^{j}_{\boldsymbol{\mu}}(\pi^{j})\geq\sup_{\pi^{j}\in\Pi^{j}}J^{j}_{\boldsymbol{\mu}}(\pi^{j})$
as well.

To show this result we use Lemma 1. Consider a policy $\pi^{j}$ and a Markov
policy $\hat{\pi}^{j}$, such that
$\nu^{\hat{\pi}^{j}}_{\boldsymbol{\mu}}=\nu^{\pi^{j}}_{\boldsymbol{\mu}}$. Now
using the Eq. 17, we have

$\begin{array}[]{l}J^{j}_{\boldsymbol{\mu}}(\pi^{j})=\bigintss_{(s^{j}\in\mathcal{S},a^{j}\in\mathcal{A}^{j})}r^{j}(s^{j},a^{j},\mu)\nu^{\pi^{j}}(s^{j},a^{j}|\mu)\\\
\\\
\overset{1}{=}\bigintss_{(s^{j}\in\mathcal{S},a^{j}\in\mathcal{A}^{j})}r^{j}(s^{j},a^{j},\mu)\nu^{\hat{\pi}^{j}}(s^{j},a^{j}|\mu)\\\
\\\
\leq\sup_{\hat{\pi}^{j}\in\Pi^{j}_{M}}\bigintss_{(s^{j}\in\mathcal{S},a^{j}\in\mathcal{A}^{j})}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})\nu^{\hat{\pi}^{j}}(s^{j},a^{j}|\mu)\\\
\\\
=\sup_{\hat{\pi}^{j}\in\Pi^{j}_{M}}J^{j}_{\boldsymbol{\mu}}(\hat{\pi}^{j})\end{array}$
(24)

Here (1) is from Lemma 1. Now, from Eq. 24, and taking supermum on both sides,
we get that
$\sup_{\pi^{j}\in\Pi^{j}}J^{j}_{\boldsymbol{\mu}}(\pi^{j})\leq\sup_{\pi^{j}\in\Pi^{j}_{M}}J^{j}_{\boldsymbol{\mu}}(\pi^{j})$,
which concludes our proof.

∎

##  Appendix B Proof of Theorem 2

The proof of this theorem follows the Theorem 1 in Saldi, Basar, and Raginsky
(2018). We aim to extend it to the decentralized setting as mentioned in
Section 5.

Before starting the proof, we will state some assumptions,

######  Assumption 2.

The reward function for all agents $j\in\\{1,\ldots,N\\}$ is bounded and
continuous.

Let us define a function $w:\mathcal{S}\xrightarrow{}[1,\infty)$, such that
there exists an increasing sequence of compact subsets $\\{K_{n}\\}_{n\geq 1}$
of $\mathcal{S}$ where

$\lim_{n\xrightarrow{}\infty}\inf_{s\in\mathcal{S}\backslash
K_{n}}w(s)=\infty.$ (25)

That is, the value of $w(s)$ gets close to infinity in this limit. Here, the
$w$ can be regarded as a continuous moment function (Saldi, Basar, and
Raginsky 2018).

######  Assumption 3.

There exists a positive $\alpha$ such that the following holds (for all agents
$j\in\\{1,\ldots,N\\}$),

$\sup_{(a^{j},\mu^{j})\in\mathcal{A}^{j}\times
P(\mathcal{S})}\bigintss_{\mathcal{S}}w(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\leq\alpha
w(s^{j}_{t})$ (26)

Also, consider two different moment functions $w$ and $v$, then $\alpha$
satisfies,

$\begin{array}[]{l}\sup_{(a^{j},\mu^{j})\in\mathcal{A}^{j}\times
P(\mathcal{S})}\Big{|}\bigintss_{\mathcal{S}}w(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\\\
\\\
-\bigintss_{\mathcal{S}}v(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t}))\Big{|}\leq\alpha|w(s^{j}_{t})-v(s^{j}_{t})|\end{array}$
(27)

######  Assumption 4.

The initial mean field $\mu_{0}$ satisfies

$\int_{\mathcal{S}}w(s^{j})\mu_{0}(s^{j})\triangleq M<\infty$ (28)

######  Assumption 5.

There exist a $\gamma\geq 1$ and a positive scalar $\mathcal{R}$ such that for
all $t\geq 0$, we define $M_{t}\triangleq\gamma^{t}\mathcal{R}$, then

$\sup_{(a^{j},\mu)\in\mathcal{A}^{j}\times
P(\mathcal{S})}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})\leq M_{t}w(s^{j}_{t})$ (29)

Now, we will state a few definitions required for our proof. For any function
$g:\mathcal{S}\xrightarrow{}\Re$, we define the $w$-norm as:

$||g||_{w}\triangleq\sup_{s\in\mathcal{S}}\frac{|g(s)|}{w(s)}$ (30)

Let $B_{w}(\mathcal{S})$ be the Banach space of all real valued measurable
functions on $\mathcal{S}$ with a finite $w$-norm.

Also, for any signed measure $\mu$ in the space of $\mathcal{S}$, the $w$-norm
can be defined as

$||\mu||_{w}\triangleq\sup_{g\in B_{w}(\mathcal{S}):||g||_{w}\leq
1}\Big{|}\int_{\mathcal{S}}g(s)\mu(s)\Big{|}$ (31)

Further, we define another set

$\mathcal{T}_{w}(\mathcal{S})\triangleq\\{\mu\in\mathcal{P}(\mathcal{S}):||\mu||_{w}<\infty\\}$
(32)

Also, for $t\geq 0$, we define

$\mathcal{T}^{t}_{w}(\mathcal{S})\triangleq\Big{\\{}\mu\in\mathcal{T}_{w}(\mathcal{S}):\int_{\mathcal{S}}w(s)\mu(s)\leq\alpha^{t}M\Big{\\}}$
(33)

where the constant $M$ is obtained from Assumption 4. Like our notation
$\mathcal{P}(\mathcal{S})$, we are using the notation
$\mathcal{P}(\mathcal{S}\times\mathcal{A}^{j})$ to denote the probability of a
state-action pair. Let us consider an element
$\nu\in\mathcal{P}(\mathcal{S}\times\mathcal{A}^{j})$, and use the notation
$\nu_{1}\triangleq\nu(\cdot\times\mathcal{A}^{j})$ to denote the state
marginal of $\nu$. Now we define a new set,

$\mathcal{T}^{t}_{w}(\mathcal{S}\times\mathcal{A}^{j})\triangleq\Big{\\{}\nu\in\mathcal{P}(\mathcal{S}\times\mathcal{A}^{j}):\nu_{1}\in\mathcal{T}^{t}_{w}(\mathcal{S})\Big{\\}}.$
(34)

For each $t\geq 0$, we will define

$L_{t}\triangleq\sum_{k=t}^{\infty}(\beta\alpha)^{k-t}M_{k}$ (35)

Here the constants $\alpha$ and $M_{k}$ are obtained from Assumption 3 and
Assumption 5 respectively.

It follows that the following equation holds,

$L_{t}=M_{t}+(\beta\alpha)L_{t+1}$ (36)

Let $C_{w}(S)$ denote the Banach space of all real valued bounded measurable
functions on $\mathcal{S}$ with a finite $w$-norm.

Let us define a set

$C^{t}_{w}(\mathcal{S})\triangleq\\{u\in C_{w}(\mathcal{S}):||u||_{w}\leq
L_{t}\\}$ (37)

For an agent $j\in\\{1,\ldots,N\\}$, let us consider an operator

$\begin{array}[]{l}T^{\boldsymbol{\mu}}_{t}u^{j}(s_{t})=\max_{a_{t}^{j}\in\mathcal{A}^{j}}\Big{[}r(s_{t}^{j},a_{t}^{j},\mu_{t})\\\
\\\
\quad\quad\quad\quad\quad\quad\quad+\beta\bigintss_{\mathcal{S}}u^{j}(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{]}\end{array}$
(38)

where $u^{j}:\mathcal{S}\xrightarrow{}\Re$

We will first prove the following lemma.

######  Lemma 2.

For all $t\geq 0$ and a given mean field $\boldsymbol{\mu}$, the operator
$T_{t}^{\boldsymbol{\mu}}$ maps $C^{t+1}_{w}(\mathcal{S})$ into
$C^{t}_{w}(\mathcal{S}).$ Also, this operator will satisfy

$||T^{\boldsymbol{\mu}}_{t}u-T^{\boldsymbol{\mu}}_{t}x||_{w}\leq\alpha\beta||u-x||_{w}$
(39)

for any $u,x\in C_{w}(\mathcal{S})$.

###### Proof.

Let $u\in C^{t+1}_{w}(\mathcal{S})$. We have the following relation,

$\begin{array}[]{l}||T^{\boldsymbol{\mu}}_{t}u||_{w}\leq\sup_{(s^{j}_{t},a^{j}_{t})\in\mathcal{S}\times\mathcal{A}^{j}}\\\
\\\
\quad\quad\quad\quad\quad\frac{\Big{|}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})+\beta\bigintss_{S}u(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{|}}{w(s^{j}_{t})}\\\
\\\
\leq\sup_{(s^{j}_{t},a^{j}_{t})\in\mathcal{S}\times\mathcal{A}^{j}}\frac{M_{t}w(s^{j}_{t})+\beta\alpha
L_{t+1}w(s^{j}_{t})}{w(s^{j}_{t})}\\\ \\\ =M_{t}+\beta\alpha L_{t+1}\\\ \\\
=L_{t}\end{array}$ (40)

The second last step is from Assumption 5 and Assumption 3. Also, we use the
bound on the $w$-norm from Eq. 37. The last step is from Eq. 36. This proves
the first statement.

To prove the second statement, without loss of generality, let us assume that
$u_{0}\geq x_{0}$. Now consider,

$\begin{array}[]{l}||T^{\boldsymbol{\mu}}_{t}u-T^{\boldsymbol{\mu}}_{t}x||_{w}=\\\
\\\
\sup_{(s^{j}_{t})\in\mathcal{S}}\frac{\max_{a^{j}_{t}}\Big{|}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})+\beta\bigintsss_{\mathcal{S}}u(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})}{w(s^{j}_{t})}\\\
\\\
\quad\quad\quad\quad\quad\quad\frac{-r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})-\beta\bigintsss_{\mathcal{S}}x(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{|}}{w(s^{j}_{t})}\\\
\\\
=\sup_{(s^{j}_{t})\in\mathcal{S}}\frac{\max_{a^{j}_{t}}\Big{|}\beta\Big{(}\bigintsss_{\mathcal{S}}u(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})}{w(s^{j}_{t})}\\\
\\\
\quad\quad\quad\quad\quad\quad\frac{-\bigintsss_{\mathcal{S}}x(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{)}\Big{|}}{w(s^{j}_{t})}\\\
\\\
=\sup_{(s^{j}_{t})\in\mathcal{S}}\frac{\max_{a^{j}_{t}}\Big{|}\beta\bigintsss_{\mathcal{S}}p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})(u(s^{j}_{t+1})-x(s^{j}_{t+1}))\Big{|}}{w(s^{j}_{t})}\\\
\\\
\leq\sup_{(s^{j}_{t})\in\mathcal{S}}\frac{\alpha\beta\Big{|}(u(s^{j}_{t})-x(s^{j}_{t}))\Big{|}}{w(s^{j}_{t})}\\\
\\\ =\alpha\beta||u-x||_{w}\par\end{array}$ (41)

We apply Assumption 3 and the last step is from Eq. 30. This proves the second
part of the lemma as well.

∎

Let us define a new set $\mathcal{C}$ from $C^{t}_{w}(\mathcal{S})$ as
follows:

$\mathcal{C}\triangleq\Pi_{t=0}^{\infty}C^{t}_{w}(\mathcal{S})$ (42)

Also, let us assign the following metric to $\mathcal{C}$:

$\rho(\boldsymbol{u},\boldsymbol{v})\triangleq\sum_{t=0}^{\infty}\sigma^{-t}||u_{t}-v_{t}||_{w}$
(43)

where $\sigma>0$ and the following assumption holds.

######  Assumption 6.

The variables $\sigma$, $\alpha$, and $\beta$ satisfy $\alpha\sigma\beta<1$.

This assumption guarantees that the metric $\mathcal{C}$ is complete w.r.t
$\rho$, and $\rho(\boldsymbol{u},\boldsymbol{v})<\infty$ for all
$\boldsymbol{u,v}\in\mathcal{C}$.

Using the operators $\\{T^{\boldsymbol{\mu}}_{t}\\}_{t\geq 0}$, let us define
a new operator $T^{\boldsymbol{\mu}}:\mathcal{C}\xrightarrow{}\mathcal{C}$ as
follows (for all $t\geq 0$).

$(T^{\boldsymbol{\mu}}\boldsymbol{u})_{t}=T^{\boldsymbol{\mu}}_{t}u_{t+1}$
(44)

From Lemma 2 we know that $T^{\boldsymbol{\mu}}$ is a well-defined operator
that maps $\mathcal{C}$ to itself. Also, from Eq. 39, $T^{\boldsymbol{\mu}}$
is a contraction operator on $\mathcal{C}$ with constant of contraction
$\alpha\beta\sigma<1$ (from Assumption 6). Now, $T^{\boldsymbol{\mu}}$ will
have a unique fixed point by the Banach fixed point theorem in $\mathcal{C}$.

Now, we move to proving another lemma. Consider a mean field
$\boldsymbol{\mu}$, the optimal value function for an agent $j$ can be given
by

$J^{j,\boldsymbol{\mu}}_{*,t}(s^{j})=\sup_{\pi^{j}\in\Pi^{j}}\mathbb{E}^{\pi^{j}}\Big{[}\sum_{t=0}^{\infty}\beta^{t}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})|s^{j}_{0}=s^{j}\Big{]}.$
(45)

Let
$\boldsymbol{J}^{j,\boldsymbol{\mu}}_{*}\triangleq(J^{j,\boldsymbol{\mu}}_{*,t})_{t\geq
0}$ denote the optimal value function for an agent $j\in\\{1,\ldots,N\\}$.
This function is guaranteed to be continuous by Assumption 2.

######  Lemma 3.

For any $\boldsymbol{\mu}$, the optimal point
$\boldsymbol{J}^{j,\boldsymbol{\mu}}_{*}$, for an agent
$j\in\\{1,\ldots,N\\}$, belongs to the Banach space $\mathcal{C}$.

###### Proof.

Let $\pi$ be a Markov policy. At any time $t\geq 0$, we have

$\begin{array}[]{l}J^{j,\boldsymbol{\mu}}_{*,t}(s)\\\ \\\
=\sum_{k=t}^{\infty}\beta^{k-t}\mathbb{E}^{\pi}(r^{j}(s^{j}_{k},a^{j}_{k},\mu_{k})|s^{j}_{t}=s^{j})\\\
\\\
\leq\sum_{k=t}^{\infty}\beta^{k-t}M_{k}\mathbb{E}^{\pi}(v(s_{k})|s^{j}_{t}=s^{j})\\\
\\\ \leq\sum_{k=t}^{\infty}\beta^{k-t}M_{k}\alpha^{k-t}v(s^{j})\\\ \\\
=L_{t}v(s^{j})\end{array}$ (46)

The second step is from Assumption 5. The third step is from Assumption 3.
Hence, the function $\boldsymbol{J}^{j,\boldsymbol{\mu}}_{*,t}$ belongs to the
set $C^{t}_{w}(\mathcal{S})$ from the Eq. 37.

∎

Let us define another set $\mathcal{D}$ as

$\mathcal{D}\triangleq\Pi^{\infty}_{t=0}\mathcal{T}^{t}_{w}(\mathcal{S}\times\mathcal{A}^{j})$
(47)

Before proving further results, we restate a result proved previously in non-
homogeneous stochastic processes (Hinderer 1970). We will adapt the result to
pertain to an agent $j\in\\{1,\ldots,N\\}$. For any $E$-valued random element
$x$, we use the notation $\mathcal{L}(x)$ to denote the distribution of $x$
(i.e. $\mathcal{L}(x)\in P(E)$).

Consider a variable $\boldsymbol{\nu}\in\mathcal{D}$. From the operator
$T^{\boldsymbol{\mu}}$, we will define another operator
$T^{\boldsymbol{\nu}}$, where the relation is such that $\mu_{t}=\nu_{t,1}$.
Recall that the subscript here refers to the state marginal of $\nu$ (refer
Eq. 34). From the result of $T^{\boldsymbol{\mu}}$, we know that the operator
$T^{\boldsymbol{\nu}}$ is well-defined and has a unique fixed point. Now, we
can state the following result.

######  Lemma 4.

For an agent $j\in\\{1,\ldots,N\\}$, for any $\boldsymbol{\nu}\in\mathcal{D}$,
the collection of value functions $\boldsymbol{J}^{j,\boldsymbol{\nu}}_{*}$ is
the unique fixed point of the operator $T^{\boldsymbol{\nu}}$. Furthermore,
$\pi^{j}\in M$ is optimal if and only if

$\begin{array}[]{l}\nu^{\pi^{j}}_{t}(\\{(s^{j}_{t},a^{j}_{t}):r^{j}(s^{j}_{t},a^{j}_{t},\nu_{t,1})+\\\
\\\
\beta\bigintss_{\mathcal{S}}J^{j,\boldsymbol{\nu}}_{*,t+1}(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\nu_{t,1})=T^{\nu}_{t}J^{j,\boldsymbol{\nu}}_{*,t+1}(s^{j}_{t})\\})\\\
\\\ =1\end{array}$ (48)

where $\nu^{\pi^{j}}_{t}=\mathcal{L}(s^{j}_{t},a^{j}_{t})$.

###### Proof.

See Hinderer (1970).

∎

Now, let us define a set-valued mapping
$\tau:\mathcal{D}\xrightarrow{}2^{|\mathcal{P}(\mathcal{S}\times\mathcal{A})^{\infty}|}$,
for an agent $j$ as follows:

$\tau(\boldsymbol{\nu})=C(\boldsymbol{\nu})\cap B(\boldsymbol{\nu})$ (49)

where

$\begin{array}[]{l}C(\boldsymbol{\nu})\triangleq\\{\boldsymbol{\nu}^{\prime}\in\mathcal{P}(\mathcal{S}\times\mathcal{A}^{j}):\nu^{\prime}_{0,1}=\mu_{0}\textrm{
and }\\\ \\\
\nu^{\prime}_{t+1,1}(\cdot)=\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}p(\cdot|s^{j},a^{j},\nu_{t,1})\nu_{t}(s^{j},a^{j})\\}\end{array}$
(50)

and

$\begin{array}[]{l}B(\boldsymbol{\nu})\triangleq\Big{\\{}\boldsymbol{\nu}^{\prime}\in\mathcal{P}(\mathcal{S}\times\mathcal{A}^{j}):\forall
t\geq 0,\\\ \\\
\nu^{\prime}_{t}(\big{\\{}(s^{j}_{t},a^{j}_{t}):r^{j}(s^{j}_{t},a^{j}_{t},\nu_{t,1})+\\\
\\\
\beta\bigintss_{\mathcal{S}}J^{j,\boldsymbol{\nu}}_{*,t+1}(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\nu_{t,1})\big{\\}}=1\Big{\\}}\end{array}$
(51)

Now in the next result we show that, the image of $\mathcal{D}$ under $\tau$
is contained in $2^{\mathcal{D}}$.

######  Proposition 1.

For any $\nu\in\mathcal{D}$, we have $\tau(\nu)\subset\mathcal{D}$

###### Proof.

Fix a $\nu\in\mathcal{D}$. To prove the result, it is sufficient to prove that
$C(\boldsymbol{\nu})\subset\mathcal{D}$. Let $\boldsymbol{\nu}^{\prime}\in
C(\boldsymbol{\nu})$. We aim to prove by induction that $\nu^{\prime}_{t,1}\in
P^{t}_{v}(\mathcal{S})$ for all $t\geq 0$. The claim trivially holds for $t=0$
as $\nu^{\prime}_{0,1}=\mu_{0}$. Assume that the claim holds for $t$ and
consider $t+1$. We have

$\begin{array}[]{l}\bigintss_{\mathcal{S}}w(s_{t}^{j})\nu^{\prime}_{t+1,1}(s^{j}_{t+1})\\\
\\\
=\bigintss_{\mathcal{S}\times\mathcal{A}}\bigintss_{\mathcal{S}}w(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\nu_{t,1})\nu_{t}(s^{j}_{t},a^{j}_{t})\\\
\\\ \leq\bigintss_{\mathcal{S}}\alpha w(s^{j}_{t})\nu_{t,1}(s^{j}_{t})\\\ \\\
\leq\alpha^{t+1}M\end{array}$ (52)

The third step is from Assumption 3 and the last step is from the fact that
$\nu_{t,1}\in P^{t}_{v}(\mathcal{S})$. Hence, we can conclude that
$\nu^{\prime}_{t+1,1}\in P^{t+1}_{v}(\mathcal{S})$. ∎

Now we can say that $\boldsymbol{\nu}\in\mathcal{D}$ is a fixed point of
$\tau$ if $\boldsymbol{\nu}\in\tau(\boldsymbol{\nu})$. The following lemma
connects the mean field equilibrium and the fixed points of $\tau$.

######  Lemma 5.

Suppose the set valued mapping $\tau$ has a fixed point
$\boldsymbol{\nu^{j}}=(\nu^{j}_{t})_{t\geq 0}$ for an agent
$j\in\\{1,\ldots,N\\}$. Consider a Markov policy for the agent $j$ as
$\pi^{j}=(\pi^{j}_{t})_{t\geq 0}$, which is obtained by factoring as
$\nu^{j}_{t}(s^{j}_{t},a^{j}_{t})=\nu^{j}_{t,1}(s^{j}_{t})\pi^{j}_{t}(a^{j}_{t}|s^{j}_{t})$,
and let $\boldsymbol{\nu}^{j}_{1}=(\nu^{j}_{t,1})_{t\geq 0}$. Then the pair
$(\pi^{j},\boldsymbol{\nu}^{j}_{1})$ is a decentralized mean field
equilibrium.

###### Proof.

If $\boldsymbol{\nu}^{j}\in\tau(\boldsymbol{\nu}^{j})$, then the corresponding
Markov policy $\pi^{j}$ satisfies the Eq. 48 for $\boldsymbol{\nu}^{j}$. Thus,
by Lemma 4, $\pi^{j}\in\Phi(\boldsymbol{\nu}^{j}_{1})$. Further, since
$\boldsymbol{\nu}^{j}\in C(\boldsymbol{\nu}^{j})$, we have
$\Psi(\pi^{j})=\boldsymbol{\nu}^{j}_{1}$, which completes the proof. ∎

From the Lemma 5, it can be seen that the set valued mapping (operator) $\tau$
having a fixed point is sufficient to guarantee the existence of the
decentralized mean field equilibrium. Like several results in centralized
multiagent systems (Nash 1951) and centralized mean field games (Lasry and
Lions 2007; Huang et al. 2006; Saldi, Basar, and Raginsky 2018), we will use
the Kakutani’s fixed point theorem (Kakutani 1941), to guarantee the existence
of a fixed point for the operator $\tau$. This theorem requires the set on
which the set valued mapping $\tau$ operates to be a non-empty, compact and
convex subset of some Euclidean space. Further, the operator
$\tau(\boldsymbol{\nu}^{j})$ is required to be non-empty and convex for all
$\boldsymbol{\nu}^{j}$. Finally, the operator $\tau$ should have a closed
graph. Given these three conditions, we can conclude that $\tau$ has a fixed
point using the Kakutani’s fixed point theorem.

For the first condition, we need to show that the set on which
$\boldsymbol{\nu}^{j}$ resides is non-empty, compact and convex, i.e. we need
to show that $\mathcal{D}$ is non-empty, compact and convex. First, note that
the function $w$ can be expressed as a continuous moment function and hence
the corresponding set $\mathcal{T}^{t}_{v}(\mathcal{S})$ is guaranteed to be
compact (Hernández-Lerma and Lasserre 2012). As a consequence, the set
$\mathcal{T}^{t}_{v}(\mathcal{S}\times\mathcal{A}^{j})$ is tight, since the
action space $\mathcal{A}^{j}$ is compact. Also, since the set
$\mathcal{T}^{t}_{v}(\mathcal{S}\times\mathcal{A}^{j})$ is closed, it is
compact. Therefore, the set $\mathcal{D}$ is also compact. From Assumption 3
and Assumption 5 we can show that a line segment between any two points in
$\mathcal{D}$ lies in $\mathcal{D}$ and hence the set $\mathcal{D}$ is convex.
These assumptions also guarantee that the set $\mathcal{D}$ is non-empty.

For the third condition, we need to show that $\tau(\boldsymbol{\nu}^{j})$ is
non-empty and convex for any $\boldsymbol{\nu}^{j}\in\mathcal{D}$. Now, from
Lemma 4 we know that $B(\boldsymbol{\nu}^{j})$ is non-empty and hence
$\tau(\boldsymbol{\nu}^{j})$ is non-empty. Also, we can show that each of the
sets $C(\boldsymbol{\nu}^{j})$ and $B(\boldsymbol{\nu}^{j})$ is convex (see
Saldi, Basar, and Raginsky (2018)) and hence, their intersection is convex.
This makes the set $\tau(\boldsymbol{\nu}^{j})$ convex.

######  Lemma 6.

Using Assumptions 2—6, the graph of $\tau$, i.e. the set

$Gr(\tau)\triangleq\\{(\boldsymbol{\nu},\boldsymbol{\mathcal{E}})\in\mathcal{D}\times\mathcal{D}:\boldsymbol{\mathcal{E}}\in\tau(\boldsymbol{\nu})\\}$
(53)

is closed.

###### Proof.

See Proposition 3.9 in Saldi, Basar, and Raginsky (2018) for complete proof. ∎

Now, we are ready to give the final result.

######  Lemma 7.

Using Assumptions 2—6, for an agent $j\in\\{1,\ldots,N\\}$, there exists a
fixed point $\boldsymbol{\nu}^{j}$ of the set valued mapping
$\tau:\mathcal{D}\xrightarrow{}2^{\mathcal{D}}$. Then, the pair
$(\pi^{j},\boldsymbol{\nu}_{1}^{j})$ is a decentralized mean field
equilibrium, where $\pi^{j}$ is the policy of agent $j$ and
$\boldsymbol{\nu}_{1}^{j}$ is its mean field estimate constructed according to
Lemma 5.

###### Proof.

Using the Lemma 6 and our previous results, we have proved that $\mathcal{D}$
is non-empty, compact and convex. Further, the set valued mapping $\tau$ has a
closed graph, is non-empty and convex. Hence, by Kakutani’s fixed point
theorem (Kakutani 1941), $\tau$ has a fixed point. Thus, from Lemma 5 this
fixed point is the decentralized mean field equilibrium. ∎

######  Theorem 2.

An agent $j\in\\{1,\ldots,N\\}$ in the DMFG admits a decentralized mean field
equilibrium $(\pi^{j}_{*},\mu^{j}_{*})\in\Pi^{j}\times\mathcal{M}$.

###### Proof.

Our result follows from Lemma 7. ∎

##  Appendix C Proof of Theorem 3

In this and the subsequent theorems, we follow the theoretical results and
proofs in the work by Anahtarci, Kariksiz, and Saldi (2019), and extend them
to the decentralized setting.

First, we will start with some definition for the norms, similar to our
previous proofs. Consider an agent $j\in\\{1,\ldots,N\\}$. Let
$w:\mathcal{S}\times\mathcal{A}^{j}\xrightarrow{}\Re$ be a continuous weight
function. For any measurable function
$v:\mathcal{S}\times\mathcal{A}^{j}\xrightarrow{}\Re$, the $w$-norm of $v$ is
defined as,

$||v||_{w}\triangleq\sup_{s^{j},a^{j}}\frac{|v(s^{j},a^{j})|}{w(s^{j},a^{j})}.$
(54)

Also, for any measurable function $u:\mathcal{S}\xrightarrow{}\Re$, the
$w_{\max}$-norm is defined as

$||v||_{w_{\max}}\triangleq\sup_{s^{j}}\frac{u(s^{j})}{w_{\max}(s^{j})}.$ (55)

Now we will state a set of assumptions needed for our results.

######  Assumption 7.

For all agents $j\in\\{1,\ldots,N\\}$, the reward function is continuous, and
it satisfies the following Lipschitz bounds (for some Lipschitz constants
$L_{1}$ and $L_{2}$):

$\begin{array}[]{l}||r^{j}(\cdot,\cdot,\mu_{t})-r^{j}(\cdot,\cdot,\hat{\mu}_{t})||_{w}\leq
L_{1}W_{1}(\mu_{t},\hat{\mu}_{t}),\quad\forall\mu_{t},\hat{\mu}_{t}\end{array}$
(56)

where $W_{1}$ is the Wasserstein distance of order 1. Also,

$\begin{array}[]{l}\sup_{(a^{j}_{t},\mu_{t})\in\mathcal{A}^{j}\times
P(\mathcal{S})}|r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})-r(\hat{s}^{j}_{t},a^{j}_{t},\mu_{t})|\\\
\\\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\leq
L_{2}d_{X}(s^{j}_{t},\hat{s}^{j}_{t}),\quad\forall{s^{j}_{t},\hat{s}^{j}_{t}}\end{array}$
(57)

######  Assumption 8.

For an agent $j\in\\{1,\ldots,N\\}$, the transition function
$p(\cdot|s^{j},a^{j},\mu)$ is weakly continuous in $(s^{j},a^{j},\mu)$ and
satisfies the following Lipschitz bounds (for some Lipschitz constants $K_{1}$
and $K_{2}$):

$\begin{array}[]{l}\sup_{s^{j}\in
S}W_{1}(p(\cdot|s^{j}_{t},a^{j}_{t},\mu_{t}),p(\cdot|s^{j}_{t},\hat{a}^{j}_{t},\hat{\mu}_{t}))\\\
\\\ \leq
K_{1}(||a^{j}_{t}-\hat{a}^{j}_{t}||+W_{1}(\mu_{t},\hat{\mu}_{t})),\quad\forall\mu_{t},\hat{\mu}_{t},\forall
a^{j}_{t},\hat{a}^{j}_{t}.\end{array}$ (58)

Also, we have,

$\begin{array}[]{l}\sup_{\mu\in
P(S)}W_{1}(p(\cdot|s^{j}_{t},a^{j}_{t},\mu_{t}),p(\cdot|\hat{s}^{j}_{t},\hat{a}^{j}_{t},\mu_{t}))\\\
\\\ \leq
K_{2}(d_{X}(s^{j}_{t},\hat{s}^{j}_{t})+||a^{j}_{t}-\hat{a}^{j}_{t}||),\quad\forall
s^{j}_{t},\hat{s}^{j}_{t},\forall a^{j}_{t},\hat{a}^{j}_{t}.\end{array}$ (59)

######  Assumption 9.

The action space $\mathcal{A}^{j}$ is convex for all agents
$j\in\\{1,\ldots,N\\}$.

######  Assumption 10.

For all agents $j$ and all time $t$, there exist non-negative real numbers $M$
and $\alpha$ such that for each
$(s^{j}_{t},a^{j}_{t},\mu)~{}\in~{}\mathcal{S}\times~{}\mathcal{A}^{j}~{}\times~{}\mathcal{P}(\mathcal{S})$,
we have

$r^{j}(s^{j}_{t},a^{j}_{t},\mu)\leq M$ (60)

$\int_{S}w_{\max}(s_{t+1}^{j})p(s_{t+1}^{j}|s^{j}_{t},a^{j}_{t},\mu)\leq\alpha
w(s^{j}_{t},a^{j}_{t})$ (61)

######  Assumption 11.

The product of constants $\beta\alpha<1$.

Let $C(\mathcal{S})$ denote the set of real-valued continuous functions on
$\mathcal{S}$. Let $Lip(\mathcal{S})$ denote the set of all Lipshitz
continuous function on $\mathcal{S}$, i.e.,

$Lip(\mathcal{S})\triangleq\\{g\in C(\mathcal{S}):||g||_{Lip}<\infty\\}$ (62)

where $||g||_{Lip}$ is defined as

$||g||_{Lip}\triangleq\sup_{(x,y)\in\mathcal{S}\times\mathcal{S}}\frac{|g(x)-g(y)|}{d_{X}(x,y)}$
(63)

Here $g\in C(\mathcal{S})$. The finiteness of $||g||_{Lip}$ guarantees that
$g$ is Lipschitz continuous with constant $||g||_{Lip}$.

Also, let us define $B(\mathcal{S},K)$ to be the set of all real valued
measurable functions in $\mathcal{S}$ with $w_{\max}$-norm less than $K$. We
use $Lip(\mathcal{S},K)$ to denote the set of all Lipschitz continuous
functions with $||g||_{Lip}<\infty$.

Finally, we define an operator $F:\mathcal{S}\times
Lip(\mathcal{S})\times\mathcal{P}(\mathcal{S})\times\mathcal{A}^{j}\xrightarrow{}\Re$
as

$\begin{array}[]{l}F:\mathcal{S}\times
Lip(\mathcal{S})\times\mathcal{P}(\mathcal{S})\times\mathcal{A}^{j}\ni(s^{j}_{t},v^{j}_{t},\mu_{t},a^{j}_{t})\\\
\\\
\xrightarrow{}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})+\beta\bigintss_{\mathcal{S}}v^{j}_{t}(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\in\Re\end{array}$
(64)

######  Assumption 12.

Let $\mathcal{F}$ be the set of non-negative functions in

$Lip\Big{(}\mathcal{S},\frac{L_{2}}{1-\beta K_{2}}\Big{)}\cap
B\Big{(}\mathcal{S},\frac{M}{1-\beta\alpha}\Big{)}$ (65)

For an agent $j\in\\{1,\ldots,N\\}$, for any $v\in\mathcal{F}$,
$\mu\in\mathcal{P}(\mathcal{S})$, and $s^{j}\in S$, $F(s^{j},v^{j},\mu,\cdot)$
is $\rho$-strongly convex; that is $F(s^{j},v^{j},\mu,\cdot)$ is
differentiable and its gradient $\nabla F$ satisfies

$\begin{array}[]{l}F(s^{j}_{t},v^{j}_{t},\mu_{t},a^{j}_{t})\geq
F(s^{j}_{t},v^{j}_{t},\mu_{t},\hat{a}^{j}_{t})\\\ \\\ +\nabla
F(s^{j}_{t},v^{j}_{t},\mu_{t},\hat{a}^{j}_{t})^{T}\cdot(a^{j}_{t}-\hat{a}^{j}_{t})+\frac{\rho}{2}||a^{j}_{t}-\hat{a}_{t}^{j}||^{2}\\\
\\\ \end{array}$ (66)

for some $\rho>0$ and for all $a^{j}_{t},\hat{a}_{t}^{j}\in\mathcal{A}^{j}$.

######  Assumption 13.

For an agent $j\in\\{1,\ldots,N\\}$, the gradient $\nabla
F(s^{j}_{t},v^{j}_{t},\mu_{t},a^{j}_{t}):\mathcal{S}\times\mathcal{F}\times\mathcal{P}(\mathcal{S})\times\mathcal{A}^{j}\xrightarrow{}\Re$
satisfies the following Lipshitz bound (for some Lipschitz constant $K_{F}$):

$\begin{array}[]{l}\sup_{a^{j}_{t}\in A^{j}}||\nabla
F(s^{j}_{t},v^{j}_{t},\mu_{t},a^{j}_{t})-\nabla
F(\hat{s}^{j}_{t},\hat{v}^{j}_{t},\hat{\mu}_{t},a^{j}_{t})||\\\ \\\ \leq
K_{F}(d_{X}(s^{j}_{t},\hat{s}^{j}_{t})+||v^{j}_{t}-\hat{v}^{j}_{t}||_{w_{\max}}+W_{1}(\mu^{j}_{t},\hat{\mu}_{t}^{j}))\\\
\\\ \end{array}$ (67)

for every
$s^{j}_{t},\hat{s}^{j}_{t}\in\mathcal{S};v^{j},\hat{v}^{j}_{t}\in\mathcal{F},\mu_{t},\hat{\mu}_{t}\in\mathcal{P}(\mathcal{S})$.

Assumption 12 and Assumption 13 present a constraint on the change in the
value function during each of the updates. These assumptions are generally
considered in literature establishing the existence of Lyapunov functions that
guarantee the presence of local and global optimal points (maxima or minima)
as the case may be (Tanaka, Hori, and Wang 2003).

We also need to assume the following for all the constants,

######  Assumption 14.

The following relation holds

$\begin{array}[]{l}k\triangleq\max\\{\beta\alpha+\frac{K_{F}}{\rho}K_{1},\beta\frac{L_{2}}{1-\beta
K_{2}}+\\\ \\\
\quad\quad\quad\quad\quad\quad\quad\Big{(}\frac{K_{F}}{\rho}+1\Big{)}K_{1}+K_{2}+\frac{K_{F}}{\rho}\\}<1\end{array}$
(68)

For the rest of the proof we will also apply Assumption 1. Consider a mean
field $\boldsymbol{\mu}$, the optimal value function for an agent $j$ is given
by the Eq. 45. Using the same procedure as the result in Lemma 4, this optimal
value function can be shown to be a unique fixed point of a Bellman operator
$T_{\boldsymbol{\mu}}$ that is a contraction on the $w_{\max}$-norm with a
constant of contraction $\beta\alpha$ (from Assumption 11). Now we can write
the following equation,

$\begin{array}[]{l}J^{j,\boldsymbol{\mu}}_{*}(s^{j}_{t})=\max_{a^{j}\in\mathcal{A}^{j}}\Big{[}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})+\\\
\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\beta\bigintss_{\mathcal{S}}J^{j,\boldsymbol{\mu}}_{*}(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{]}\\\
\\\ \triangleq
T_{\boldsymbol{\mu}}J^{j,\boldsymbol{\mu}}_{*}(s^{j}_{t})\end{array}$ (69)

Let us assume that this maximization is caused by a policy
$\pi^{j}(a^{j}|s^{j},\mu^{j})$, which will be the optimal policy. In other
words,

$\begin{array}[]{l}\max_{a^{j}\in\mathcal{A}^{j}}\Big{[}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})+\\\
\\\
\quad\quad\quad\quad\quad\quad\beta\bigintss_{\mathcal{S}}J^{j,\boldsymbol{\mu}}_{*}(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{]}=\\\
\\\ r^{j}(s^{j}_{t},\pi^{j}(a^{j}_{t}|s^{j}_{t},\mu^{j}_{t}),\mu_{t})\\\ \\\
\quad\quad\quad\quad\quad+\beta\bigintss_{\mathcal{S}}J^{j,\boldsymbol{\mu}}_{*}(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\end{array}$
(70)

The objective is to obtain this optimal policy. Towards the same we use the
$Q$-functions, where the optimal $Q$-function can be defined as

$\begin{array}[]{l}Q^{j,*}_{\boldsymbol{\mu}}(s^{j}_{t},a^{j}_{t})\\\ \\\
=r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})+\beta\bigintss_{\mathcal{S}}J^{j,\boldsymbol{\mu}}_{*}p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\end{array}$
(71)

The optimal value function given by $J^{j,\boldsymbol{\mu}}_{*}$ is the
maximum of the $Q$-function given by $Q^{j,*}_{\boldsymbol{\mu},\max}$. Hence,
we can rewrite Eq. 71 as follows

$\begin{array}[]{l}Q^{j,*}_{\boldsymbol{\mu}}(s^{j}_{t},a^{j}_{t})=r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})\\\
\\\
\quad\quad\quad\quad\quad+\beta\bigintss_{\mathcal{S}}Q^{j,*}_{\boldsymbol{\mu},\max_{a^{j}}}(s^{j}_{t+1},a^{j})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\\\
\\\ \triangleq HQ^{j,*}_{\boldsymbol{\mu}}(s^{j}_{t},a^{j}_{t})\end{array}$
(72)

Here, the operator $H$ is the optimality operator for the $Q$-functions. Our
objective is to prove that this operator is a contraction and has a unique
fixed point given by $Q_{*}$.

First, let us define a set of all bounded $Q$-functions for an agent
$j\in\\{1,\ldots,N\\}$:

$\begin{array}[]{l}\mathcal{C}\triangleq\Big{\\{}Q^{j}:\mathcal{S}\times\mathcal{A}^{j}\xrightarrow{}[0,\infty);||Q^{j}_{\max}||_{w}\leq\frac{M}{1-\beta\alpha}\\\
\\\ \textrm{ and }\\\ \\\ ||Q^{j}_{\max}||_{Lip}\leq\frac{L_{2}}{1-\beta
K_{2}}\Big{\\}}\end{array}$ (73)

From Assumption 1, Assumption 12 and Assumption 13, we know that there exists
a unique maximiser $\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t})$ for the function
$F$ represented as,

$\begin{array}[]{l}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})\\\ \\\
+\beta\bigintss_{\mathcal{S}}Q^{j}_{\boldsymbol{\mu},\max_{a^{j}}}(s^{j}_{t+1},a^{j})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\\\
\\\ =F(s^{j}_{t},Q^{j}_{\boldsymbol{\mu},\max},\mu_{t},a^{j}_{t}).\end{array}$
(74)

.

This maximser makes the gradient of $F$, 0.

$\nabla
F(s^{j}_{t},Q^{j}_{\boldsymbol{\mu},\max},\mu_{t},\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t}))=0$
(75)

This shows that the maximiser for the operator $H_{2}$ in Eq. 8 is unique,
under the considered assumptions. Now, we are ready to prove the required
theorem.

######  Theorem 3.

The decentralized mean field operator $H$ is well-defined, i.e. this operator
maps $\mathcal{C}\times\mathcal{P}(\mathcal{S})$ to itself.

###### Proof.

We first apply Assumption 1. Now, consider the decentralized mean field
operator as defined in Eq. 8. To prove the given theorem, we know that
$H_{2}(Q^{j},\boldsymbol{\mu})\in\mathcal{P}(\mathcal{S})$. We need to prove
that $H_{1}(Q^{j},\boldsymbol{\mu})\in\mathcal{C}$. Let us consider an element
$(Q^{j},\boldsymbol{\mu})\in\mathcal{C}\times\mathcal{P}(\mathcal{S})$. Then
we have,

$\begin{array}[]{l}\sup_{s^{j}_{t},a^{j}_{t}}\frac{\Big{|}H_{1}(Q^{j},\boldsymbol{\mu})(s^{j}_{t},a^{j}_{t})\Big{|}}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\
=\sup_{s^{j}_{t},a^{j}_{t}}\frac{\Big{|}r^{j}(s^{j}_{t},a^{j}_{t},\mu)+\beta\bigintss_{\mathcal{S}}Q^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{|}}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\
\leq\sup_{s^{j}_{t},a^{j}_{t}}\frac{\Big{|}r^{j}(s^{j}_{t},a^{j}_{t},\mu)\Big{|}}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\
\quad\quad+\beta\sup_{s^{j}_{t},a^{j}_{t}}\frac{\Big{|}\bigintss_{\mathcal{S}}Q^{j}_{\max}(s^{j}_{t+1},a^{j}_{t},\mu_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{|}}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\ \leq M\\\ \\\
+\beta||Q^{j}_{\max}||_{w_{\max}}\sup_{s^{j}_{t},a^{j}_{t}}\frac{\Big{|}\bigintss_{\mathcal{S}}w_{\max}(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{|}}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\ \leq M+\beta\alpha||Q^{j}_{\max}||_{w}\\\ \\\ \leq
M+\beta\alpha\frac{M}{1-\beta\alpha}\\\ \\\
=\frac{M}{1-\beta\alpha}\end{array}$ (76)

We used the Assumption 10 and the fact that
$||Q^{j}||_{w_{\max}}\leq||Q^{j}||_{w}$.

Also, we have,

$\begin{array}[]{l}|H_{1}(Q^{j},\boldsymbol{\mu})_{\max}(s^{j}_{t})-H_{1}(Q^{j},\boldsymbol{\mu})_{\max}(\hat{s}^{j}_{t})|\\\
\\\ =\max_{a^{j}\in\mathcal{A}^{j}}[r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})\\\ \\\
\quad\quad+\beta\bigintss_{\mathcal{S}}Q^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})]\\\
\\\
\quad\quad-\max_{a^{j}\in\mathcal{A}^{j}}[r^{j}(\hat{s}^{j}_{t},a^{j}_{t},\mu_{t})\\\
\\\
\quad\quad+\beta\bigintss_{\mathcal{S}}Q^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|\hat{s}^{j}_{t},a^{j}_{t},\mu_{t})]\\\
\\\
\leq\sup_{a^{j}\in\mathcal{A}^{j}}\Big{|}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})-r^{j}(\hat{s}^{j}_{t},a^{j}_{t},\mu_{t})\Big{|}\\\
\\\ +\beta\sup_{a^{j}\in
A^{j}}\Big{|}\bigintss_{\mathcal{S}}Q^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\\\
\\\
\quad\quad\quad-\bigintss_{\mathcal{S}}Q^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|\hat{s}^{j}_{t},a^{j}_{t},\mu_{t})\Big{|}\\\
\\\ \leq L_{2}d_{X}(s,\hat{s})+\beta
K_{2}||Q^{j}_{\max}||_{Lip}d_{X}(s,\hat{s})\\\ \\\ \leq\frac{L_{2}}{1-\beta
K_{2}}d_{X}(s,\hat{s})\end{array}$ (77)

Here we are using the Assumption 7 and Assumption 8. This proves that
$H_{1}(Q^{j},\mu)\in\mathcal{C}$ and concludes our proof. ∎

##  Appendix D Proof of Theorem 4

######  Theorem 4.

Let $\mathcal{B}$ represent the space of bounded functions in $\mathcal{S}$.
Then the mapping
$H:\mathcal{C}\times\mathcal{P}(\mathcal{S})\xrightarrow{}\mathcal{C}\times\mathcal{P}(\mathcal{S})$
is a contraction in the norm of $\mathcal{B}(\mathcal{S})$.

In this section, we will continue to use the set of assumptions and
definitions we introduced in Appendix C.

###### Proof.

Fix any $(Q^{j},\mu)$ and $(\hat{Q}^{j},\hat{\mu})$ in
$\mathcal{C}\times\mathcal{P}(\mathcal{S})$, let us consider,

$\begin{array}[]{l}||H_{1}(Q^{j},\mu)-H_{1}(\hat{Q}^{j},\hat{\mu})||_{w}\\\
\\\ =\sup_{s^{j}_{t},a^{j}_{t}}\\\ \\\
\Big{[}\frac{r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})+\beta\bigintss_{\mathcal{S}}Q^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\
\quad\quad\quad\frac{-r^{j}(s^{j}_{t},a^{j}_{t},\hat{\mu}_{t})-\beta\bigintss_{\mathcal{S}}\hat{Q}^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\hat{\mu}_{t})}{w(s^{j}_{t},a^{j}_{t})}\Big{]}\\\
\\\
\leq\sup_{s^{j}_{t},a^{j}_{t}}\frac{|r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})-r^{j}(s^{j}_{t},a^{j}_{t},\hat{\mu}_{t})|}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\
+\beta\sup_{s^{j}_{t},a^{j}_{t}}\frac{\Big{|}\bigintss_{\mathcal{S}}Q^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\
\quad\quad\quad\frac{-\bigintss_{\mathcal{S}}\hat{Q}^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\hat{\mu}_{t})\Big{|}}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\ \leq L_{1}W_{1}(\mu,\hat{\mu})\\\ \\\
\quad\quad+\beta\sup_{s^{j}_{t},a^{j}_{t}}\frac{\Big{|}\bigintss_{\mathcal{S}}Q^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\
\quad\quad\quad\frac{-\bigintss_{\mathcal{S}}\hat{Q}^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{|}}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\
\quad\quad+\beta\sup_{s^{j}_{t},a^{j}_{t}}\frac{\Big{|}\bigintss_{\mathcal{S}}\hat{Q}^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{|}}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\
\quad\quad\quad\frac{-\bigintss_{\mathcal{S}}\hat{Q}^{j}_{\max}(s^{j}_{t+1},a^{j},\mu^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\hat{\mu}_{t})\Big{|}}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\ \leq
L_{1}W_{1}(\mu,\hat{\mu})+\beta||Q^{j}_{\max}-\hat{Q}^{j}_{\max}||_{w_{\max}}\\\
\\\
\quad\quad\sup_{s^{j}_{t},a^{j}_{t}}\frac{\Big{|}\bigintss_{\mathcal{S}}w_{\max}(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\Big{|}}{w(s^{j}_{t},a^{j}_{t})}\\\
\\\
+\beta||\hat{Q}^{j}_{\max}||_{Lip}\sup_{s^{j}_{t},a^{j}_{t}}\frac{W_{1}(p(\cdot|s^{j}_{t},a^{j}_{t},\mu_{t}),p(\cdot|s^{j}_{t},a^{j}_{t},\hat{\mu}_{t}))}{w(s^{j}_{t},a^{j}_{t})}\par\\\
\\\ \leq
L_{1}W_{1}(\mu,\hat{\mu})+\beta\alpha||Q^{j}-\hat{Q}^{j}||_{w}+\beta\frac{L_{2}}{1-\beta
K_{2}}K_{1}W_{1}(\mu,\hat{\mu})\par\par\par\end{array}$ (78)

First we apply Assumption 7. In the last step we apply Assumption 8 and
Assumption 10.

Now consider the distance between $H_{2}(Q^{j},\boldsymbol{\mu})$ and
$H_{2}(\hat{Q}^{j},\hat{\boldsymbol{\mu}})$. First, we will consider the
difference between the unique maximiser $\pi^{j}(s^{j},Q^{j},\mu^{j})$ of
$H_{1}(Q^{j},\boldsymbol{\mu})(s^{j},a^{j})$ and the unique maximiser
$\pi^{j}(s^{j},\hat{Q}^{j},\hat{\mu}^{j})$ of
$H_{1}(\hat{Q}^{j},\hat{\boldsymbol{\mu}})(s^{j},a^{j})$ with respect to the
action (using the Assumption 1). Let us consider the function,

$\begin{array}[]{l}F:\mathcal{S}\times\mathcal{C}\times\mathcal{P}(\mathcal{S})\times\mathcal{A}^{j}\ni(s^{j}_{t},v^{j}_{t},\mu_{t},a^{j}_{t})\\\
\\\
\xrightarrow{}r^{j}(s^{j}_{t},a^{j}_{t},\mu_{t})+\beta\bigintss_{\mathcal{S}}v(s^{j}_{t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{t})\in\Re\end{array}$
(79)

This is $\rho$-strongly convex by Assumption 12, hence it satisfies the
following equation (Hajek and Raginsky 2019),

$[\nabla F(s^{j}_{t},v^{j}_{t},\mu_{t},a^{j}_{t}+b^{j}_{t})-\nabla
F(s^{j}_{t},v^{j}_{t},\mu_{t},a^{j}_{t})]^{T}\cdot
r^{j}_{t}\geq\rho||b^{j}_{t}||^{2}$ (80)

For any $a^{j}_{t},b^{j}_{t}\in\mathcal{A}^{j}$ and for any
$s^{j}_{t}\in\mathcal{S}$, we can use the notation
$a^{j}_{t}=\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t})$ and
$b^{j}=\pi^{j}(s^{j}_{t+1},\hat{Q}^{j}_{t},\hat{\mu}^{j}_{t})-\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t})$.

Now, $a^{j}_{t}=\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t})$ is the unique
maximiser of the strongly convex function
$F(s^{j}_{t},Q_{max,t}^{j},\mu_{t},\cdot)$, we have

$\nabla
F(s^{j}_{t},Q_{max,t}^{j},\mu_{t},\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t}))=0$
(81)

Also, the term
$a^{j}_{t}+b^{j}_{t}=\pi^{j}(s^{j}_{t+1},\hat{Q}^{j}_{t},\hat{\mu}^{j}_{t})$
is the unique maximiser of
$F(s^{j}_{t+1},\hat{Q}_{max,t}^{j},\hat{\mu}_{t},\cdot)$. Now, using
Assumption 12 and Eq. 80 we have,

$\begin{array}[]{l}-\nabla
F(s^{j}_{t+1},\hat{Q}_{max,t}^{j},\hat{\mu}_{t},a^{j}_{t})^{T}\cdot
b^{j}_{t}\\\ \\\ \quad\quad\quad=-\nabla
F(s^{j}_{t+1},\hat{Q}_{max,t}^{j},\hat{\mu}_{t},a^{j}_{t})^{T}\cdot
b^{j}_{t}\\\ \quad\quad\quad+\nabla
F(s^{j}_{t+1},\hat{Q}_{max,t}^{j},\hat{\mu}_{t},a^{j}_{t}+b^{j}_{t})^{T}\cdot
b^{j}_{t}\geq\rho||b^{j}_{t}||^{2}\end{array}$ (82)

Similarly, using the Assumption 13 we also have,

$\begin{array}[]{l}-\nabla
F(s^{j}_{t+1},\hat{Q}_{max,t}^{j},\hat{\mu}_{t},a^{j}_{t})^{T}\cdot
b^{j}_{t}\\\ \\\ =-\nabla
F(s^{j}_{t+1},\hat{Q}_{max,t}^{j},\hat{\mu}_{t},a^{j}_{t})^{T}\cdot
b^{j}_{t}\\\ \quad\quad\quad+\nabla
F(s^{j}_{t},Q_{max,t}^{j},\mu_{t},a^{j}_{t})^{T}\cdot b^{j}_{t}\\\ \\\
\leq||b^{j}_{t}||||\nabla F(s^{j}_{t},Q_{max,t}^{j},\mu_{t},a^{j}_{t})\\\ \\\
\quad\quad-\nabla
F(s^{j}_{t+1},\hat{Q}_{max,t}^{j},\hat{\mu}_{t},a^{j}_{t})||\\\ \\\ \leq
K_{F}||b^{j}_{t}||(d_{X}(s^{j}_{t},s^{j}_{t+1})+||Q_{max,t}^{j}-\hat{Q}_{max,t}^{j}||_{w_{max}}\\\
\\\ \quad\quad\quad+W_{1}(\mu_{t},\hat{\mu}_{t}))\\\ \\\ \leq
K_{F}||b^{j}_{t}||(d_{X}(s^{j}_{t},s^{j}_{t+1})+||Q_{t}^{j}-\hat{Q}_{t}^{j}||_{w}\\\
\\\ \quad\quad\quad+W_{1}(\mu_{t},\hat{\mu}_{t}))\end{array}$ (83)

Therefore, from the above two equations,

$\begin{array}[]{l}\pi^{j}(s^{j}_{t+1},\hat{Q}^{j}_{t},\hat{\mu}^{j}_{t})-\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t})\\\
\\\
\leq\frac{K_{F}}{\rho}(d_{X}(s^{j}_{t+1},s^{j}_{t})+||Q_{t}^{j}-\hat{Q}_{t}^{j}||_{w}+W_{1}(\mu_{t},\hat{\mu}_{t}))\end{array}$
(84)

Now, consider the $W_{1}$ distance between $H_{2}(Q^{j},\boldsymbol{\mu})$ and
$H_{2}(\hat{Q}^{j},\hat{\boldsymbol{\mu}})$.

$\begin{array}[]{l}W_{1}(H_{2}(Q^{j},\boldsymbol{\mu}),H_{2}(\hat{Q}^{j},\boldsymbol{\hat{\mu}}))\\\
\\\ =\sup_{||g||_{Lip}\leq
1}\Big{|}\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}\bigintss_{\mathcal{S}}g(s^{j}_{t+1})\\\
\\\ \quad\quad\quad
p\big{(}s^{j}_{t+1}|s^{j}_{t},\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t}),\mu_{t}\big{)}\mu_{t}(s^{j}_{t})\\\
\\\
\quad\quad-\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}\bigintss_{\mathcal{S}}g(s^{j}_{t+1})\\\
\\\ \quad\quad\quad
p\big{(}s^{j}_{t+1}|s^{j}_{t},\pi^{j}(s^{j}_{t},\hat{Q}^{j}_{t},\hat{\mu}^{j}_{t}),\hat{\mu}_{t}\big{)}\hat{\mu}_{t}(s^{j}_{t})\Big{|}\\\
\\\ \leq\sup_{||g||_{Lip}\leq
1}\Big{|}\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}\bigintss_{\mathcal{S}}g(s^{j}_{t+1})\\\
\\\ \quad\quad\quad
p\big{(}s^{j}_{t+1}|s^{j}_{t},\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t}),\mu_{t}\big{)}\mu_{t}(s^{j}_{t})\\\
\\\
\quad\quad-\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}\bigintss_{\mathcal{S}}g(s^{j}_{t+1})\\\
\\\ \quad\quad\quad
p\big{(}s^{j}_{t+1}|s^{j}_{t},\pi^{j}(s^{j}_{t},\hat{Q}^{j}_{t},\hat{\mu}^{j}_{t}),\hat{\mu}_{t}\big{)}\mu_{t}(s^{j}_{t})\Big{|}\\\
\\\ +\sup_{||g||_{Lip}\leq
1}\Big{|}\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}\bigintss_{\mathcal{S}}g(s^{j}_{t+1})\\\
\\\ \quad\quad\quad
p\big{(}s^{j}_{t+1}|s^{j}_{t},\pi^{j}(s^{j}_{t},\hat{Q}^{j}_{t},\hat{\mu}^{j}_{t}),\hat{\mu}_{t}\big{)}\mu_{t}(s^{j}_{t})\\\
\\\
\quad\quad-\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}\bigintss_{\mathcal{S}}g(s^{j}_{t+1})\\\
\\\ \quad\quad\quad
p\big{(}s^{j}_{t+1}|s^{j}_{t},\pi^{j}(s^{j}_{t},\hat{Q}^{j}_{t},\hat{\mu}^{j}_{t}),\hat{\mu}_{t}\big{)}\hat{\mu}_{t}(s^{j}_{t})\Big{|}\\\
\\\
\overset{(1)}{\leq}\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}\sup_{||g||_{Lip}\leq
1}\Big{|}\bigintss_{\mathcal{S}}g(s^{j}_{t+1})\\\ \\\ \quad\quad\quad
p\big{(}s^{j}_{t+1}|s^{j}_{t},\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t}),\mu_{t}\big{)}\mu_{t}(s^{j}_{t})\\\
\\\
-\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}\bigintss_{\mathcal{S}}g(s^{j}_{t+1})p\big{(}s^{j}_{t+1}|s^{j}_{t},\pi^{j}(s^{j}_{t},\hat{Q}^{j}_{t},\hat{\mu}^{j}_{t}),\hat{\mu}_{t}\big{)}\Big{|}\\\
\\\
\quad\quad\quad\mu_{t}(s^{j}_{t})+(K_{2}+\frac{K_{F}}{\rho})W_{1}(\mu_{t},\hat{\mu_{t}})\\\
\\\
\leq\bigintss_{\mathcal{S}\times\mathcal{A}^{j}}W_{1}\Big{(}p\big{(}\cdot|s^{j}_{t},\pi^{j}(s^{j}_{t},Q^{j}_{t},\mu^{j}_{t}),\mu_{t}\big{)},\\\
\\\ \quad\quad\quad
p\big{(}\cdot|s^{j}_{t},\pi^{j}(s^{j}_{t},\hat{Q}^{j}_{t},\hat{\mu}^{j}_{t}),\hat{\mu}_{t}\big{)}\Big{)}\mu_{t}(s^{j}_{t})\\\
\\\
\quad\quad\quad+\Big{(}K_{2}+\frac{K_{F}}{\rho}\Big{)}W_{1}(\mu_{t},\hat{\mu_{t}})\par\par\par\\\
\\\
\overset{(2)}{\leq}\frac{K_{F}}{\rho}K_{1}\Big{(}||Q^{j}_{t}-\hat{Q}^{j}_{t}||_{w}+W_{1}(\mu_{t},\hat{\mu}_{t})\Big{)}\\\
\\\
\quad\quad+K_{1}W_{1}(\mu_{t},\hat{\mu}_{t})+\Big{(}K_{2}+\frac{K_{F}}{\rho}\Big{)}W_{1}(\mu_{t},\hat{\mu_{t}})\end{array}$
(85)

In the above derivation, (1) and (2) are obtained from Assumption 8 and Eq. 84
(also refer Anahtarci, Kariksiz, and Saldi (2019)). Combining Eq. 78 and Eq.
85, and applying Assumption 14, the required result is proved. The constant of
contraction is $k$ defined in Assumption 14.

∎

##  Appendix E Proof of Theorem 5

######  Theorem 5.

Let the $Q$-updates in Algorithm 1 converge to $(Q^{j}_{*},\mu_{*}^{j})$ for
an agent $j\in\\{1,\ldots,N\\}$. Then, we can construct a policy $\pi^{j}_{*}$
from $Q^{j}_{*}$ which is expressed as

$\pi^{j}_{*}(s^{j})=\arg\max_{a^{j}\in\mathcal{A}^{j}}Q^{j}_{*}(s^{j},a^{j},\mu^{j}_{*}).$

Then the pair $(\pi^{j}_{*},\mu_{*}^{j})$ is a DMFE.

###### Proof.

From the Theorem 4 we know that $(Q^{j}_{*},\mu^{j}_{*})$ is a fixed point of
$H$. Using the Assumption 1, we consider a $\mu_{*}$, where
$\mu_{*}(s^{j})=\mu^{j}_{*}(s^{j})$, for all states $s^{j}\in\mathcal{N}^{j}$.
Hence, we can construct the following equations.

$\begin{array}[]{l}Q^{j}_{*}(s^{j}_{t},a^{j}_{t},\mu^{j}_{*})=r^{j}(s^{j}_{t},a^{j}_{t},\mu_{*,t})\\\
\\\
\quad\quad\quad+\beta\bigintss_{\mathcal{S}}Q^{j}_{*,\max}(s^{j}_{t+1},a^{j},\mu^{j}_{*,t+1})p(s^{j}_{t+1}|s^{j}_{t},a^{j}_{t},\mu_{*,t})\end{array}$
(86)

$\mu^{j}_{*,t+1}(\cdot)=\int_{\mathcal{S}\times\mathcal{A}^{j}}p(\cdot|s^{j}_{t},a^{j}_{t},\mu_{*,t})\pi^{j}_{*}(a^{j}_{t}|s^{j}_{t},\mu^{j}_{*,t})\mu_{*,t}(s^{j}_{t})$
(87)

From Eq. 87 and Assumption 1, we can construct the mean field estimate of
agent$j$, $\boldsymbol{\mu}^{j}_{*}$. Now, the above equations imply that
$\pi^{j}_{*}\in\Phi(\mu^{j}_{*})$ and $\mu^{j}_{*}=\Psi(\pi^{j}_{*})$. Hence,
$(\pi^{j}_{*},\mu^{j}_{*})$ is a decentralized mean field equilibrium.

∎

##  Appendix F Differences Between Mean Field Settings

Table 1 captures the differences between the three mean field frameworks,
MFRL, MFG, and DMFG. Particularly, we show that the DMFG is different from
other frameworks introduced previously, and it is more practical than prior
methods as it relaxes some strong assumptions in them.

There are several disadvantages in using a centralized solution concept like
Nash equilibrium (or, by extension, the mean field equilibrium) in multiagent
systems. These are listed as follows: 1) Centralized nature of the
equilibrium, though practical systems have a decentralized information
structure. 2) The equilibrium computation is almost intractable for more than
two agents (Neumann 1928). 3) Needs strong assumptions to give theoretical
guarantees of convergence of learning systems in general sum games (Hu and
Wellman 2003), even in the stationary case. 4) The equilibrium requires
agreement between agents even in the competitive case. 5) It is hard to verify
this point in practice. Our decentralized solution concept (DMFE) is more
practical than the Nash equilibrium and the mean field equilibrium, since it
does not suffer these limitations noted for the centralized methods.

Method |  MFRL Yang et al. (2018) |  MFG Lasry and Lions (2007) |  DMFG (ours)
---|---|---|---
Game formulation |  Stochastic Game |  Mean Field Game |  Decentralized Mean Field Game
Reward function |  Same for all agents |  Same for all agents |  Can be different
Action space |  Discrete only |  Can be continuous |  Can be continuous
Action space |  Same for all agents |  Same for all agents |  Can be different
Solution Concept |  Nash Equilibrium (centralized) |  Mean Field Equilibrium (centralized) |  Decentralized Mean Field Equilibrium
Complexity of obtaining the mean field |  Exponential in agents |  Exponential in agents |  Constant in agents
Theoretical Guarantees |  Needs very strong assumptions |  Needs weak assumptions |  Needs weak assumptions
Number of agents |  Should be large but finite |  Can be infinite in the limit |  Can be infinite in the limit
Mean Field Information |  Global |  Global |  Local
Agents |  Identical and homogeneous |  Identical and homogeneous |  Non-identical
Policy |  Stationary |  Can be non-stationary |  Can be non-stationary
State Observable |  Global |  Local |  Local
Table 1: Table to capture the differences between Mean Field Reinforcement
Learning (MFRL), Mean Field Games (MFG), and Decentralized Mean Field Games
(DMFG).

##  Appendix G Mean Field Modelling in DMFG-QL

In this section, we plot the mean square error between the estimated mean
field action ($\mu^{j,a}_{t}$) (from the neural network representing Eq. 14)
and the true observed local mean field action ($\hat{\mu}^{j,a}_{t}$) to show
that the true local mean field action can be accurately modelled by the DMFG-
QL algorithm. We will use the Battle game for this illustration.

Figure 7: This figure shows the average (per agent) mean square error (MSE)
between the true local mean field action and the estimated mean field action
from the neural network in each episode (sum of MSE in the 500 steps) of the
Battle game training experiment. The results show that the MSE steadily
reduces, and hence DMFG-QL is able to accurately model the true mean field.
The result shows the average of 10 runs (negligible standard deviation).

Fig. 7 shows the mean square errors (MSE) between the true mean field action
and the estimated mean field action, averaged per agent, for each episode of
the Battle game. The MSE converges to a small value close to 0 during
training. This shows that the DMFG-QL algorithm can accurately model the mean
field, which contributes to its superior performance in many of our
experimental domains. As stated in Section 6, DMFG-QL algorithm formulates
best responses to the current mean field action. This contrasts with
approaches such as MFQ that formulate best responses to the previous mean
field, which leads to a loss in performance. We start the plot in Fig 7 from
episode 200 (instead of 0), since the first few episodes have a very high MSE,
that simply skews the axis of the resulting graph.

##  Appendix H Algorithm Pseudo-Code

Algorithm 2 provides the pseudo-code of the DMFG-QL algorithm. Here, the
neural networks are used as the function approximator for the $Q$-function. In
addition, we include the use of a second target network and a replay buffer
for training, as done in the popular Deep $Q$-learning (DQN) algorithm (Mnih
et al. 2015). Also, similar to Yang et al. (2018), we specify that the
policies satisfy the GLIE assumption and hence we use the max operator over
the $Q$-value of the next state (i.e. choose the action that maximizes the Q
value) to calculate the temporal difference (T.D.) error instead of
maintaining a distinct value function as in Eq. 13.

Algorithm 3 provides the pseudo-code of the DMFG-AC algorithm. This algorithm
uses the policy as the actor, and the value function as the critic, as is
common in practice (Konda and Tsitsiklis 1999). We choose to use a stochastic
actor that does not depend on the mean field. This is done to provide an
algorithm that can work independent of the mean field during execution. Since
the critic (not used during execution) can be dependent on the mean field, we
additionally parameterize the value function with the mean field. The modified
updates can be seen in Algorithm 3. For both Algorithm 2 and Algorithm 3 we
initialize the estimated mean field distribution to a uniform distribution
(arbitrarily).

Algorithm 2 Q-learning for Decentralized Mean Field Games (DMFG-QL)

1: Initialize the $Q$-functions (parameterized by weights)
$Q_{\phi^{j}},Q_{\phi^{j}_{\\_}}$, for all agents $j\in\\{1,\ldots,N\\}$

2: Initialize the mean field estimate (parameterized by weights)
$\mu^{j,a}_{\eta}$ for each agent $j\in\\{1,\ldots,N\\}$

3: Initialize the estimated mean field $\mu^{j,a}_{0,\eta}$ for each $j$ to a
uniform distribution

4: Initialize the total steps (T) and total episodes (E)

5: Obtain the current state $s^{j}_{t}$

6: while Episode $<$ E do

7: while Step $<$ T do

8: For each agent $j$, obtain action $a^{j}_{t}$ from the policy induced by
$Q_{\phi^{j}}$ with the current estimated mean action $\mu^{j,a}_{t,\eta}$ and
the exploration rate $\hat{\beta}$ according to Eq. 15

9: Execute the joint action $\textbf{a}_{t}=[a^{1}_{t},\ldots,a_{t}^{N}]$.
Observe the rewards $\textbf{r}_{t}=[r^{1}_{t},\ldots,r^{N}_{t}]$ and the next
state $\textbf{s}_{t+1}=[s_{t+1}^{1},\ldots,s_{t+1}^{N}]$

10: For each agent $j$, obtain the current observed local mean action
($\hat{\mu}^{j,a}_{t}$)

11: Update the parameter $\eta$ of the mean field network using a mean square
error between the observed mean action $\hat{\mu}^{j,a}_{t}$ and the current
estimated mean action $\mu^{j,a}_{t,\eta}$ for all $j$

12: For each $j$, obtain the mean field estimates $\mu^{j,a}_{t+1,\eta}$ for
the next state $s_{t+1}^{j}$ using the mean field network according to Eq. 14

13: For each $j$, store $\langle
s^{j}_{t},a^{j}_{t},r^{j}_{t},s_{t+1}^{j},\mu^{j,a}_{t,\eta},\mu^{j,a}_{t+1,\eta}\rangle$
in replay buffer $B$

14: Set the next mean field estimate as the current mean field estimate
$\mu^{j,a}_{t,\eta}=\mu^{j,a}_{t+1,\eta}$ and the next state as the current
state $s_{t}^{j}=s_{t+1}^{j}$ for all agents $j\in\\{1,\ldots,N\\}$

15: end while

16: while $j$ = $1$ to $N$ do

17: Sample a minibatch of K experiences $\langle
s^{j}_{t},a^{j}_{t},r^{j}_{t},s_{t+1}^{j},\mu^{j,a}_{t,\eta},\mu^{j,a}_{t+1,\eta}\rangle$
from $B$

18: Set
$y^{j}=r^{j}_{t}+\gamma\max_{a^{j}_{t+1}}Q_{\phi^{j}_{\\_}}(s^{j}_{t+1},a^{j}_{t+1},\mu^{j,a}_{t+1,\eta})$
according to Eq. 12

19: Update the Q network by minimizing the loss
$L(\phi^{j})=\frac{1}{K}\sum(y^{j}-Q_{\phi^{j}}(s^{j}_{t},a^{j}_{t},\mu^{j,a}_{t,\eta}))^{2}$

20: end while

21: Update the parameters of the target network for each agent $j$ with
learning rate $\tau$;
$\phi^{j}_{\\_}\leftarrow\tau\phi^{j}+(1-\tau)\phi^{j}_{\\_}$

22: end while

Algorithm 3 Actor-Critic for Decentralized Mean Field Game (DMFG-AC)

1: Initialize the $V$-function or critic (parameterized by weights)
$V_{\phi^{j}}$ and the policy or actor (parameterized by weights)
$\pi_{\theta^{j}}$ for all agents $j\in{1,\ldots,N}$

2: Initialize the mean field estimate (parameterized by weights)
$\mu^{j,a}_{\eta}$ for each agent $j\in\\{1,\ldots,N\\}$

3: Initialize the estimated mean field $\mu^{j,a}_{0,\eta}$ for each $j$ to a
uniform distribution

4: Initialize the total episodes (E)

5: Obtain the current state $s^{j}_{t}$

6: while Episode $<$ E do

7: For each agent $j$, obtain action $a^{j}_{t}$ from the policy
$\pi_{\theta^{j}}$ at the current state $s^{j}_{t}$

8: Execute the joint action $\textbf{a}_{t}=[a^{1}_{t},\ldots,a_{t}^{N}]$.
Observe the rewards $\textbf{r}_{t}=[r^{1}_{t},\ldots,r^{N}_{t}]$ and the next
state $\textbf{s}_{t+1}=[s_{t+1}^{1},\ldots,s_{t+1}^{N}]$

9: For each agent $j$, obtain the current observed local mean field action
($\hat{\mu}^{j,a}_{t}$)

10: Update the parameter $\eta$ of the mean field network using a mean square
error between the observed mean action $\hat{\mu}^{j,a}_{t}$ and the current
estimated mean action $\mu^{j,a}_{t,\eta}$ for all $j$

11: For each $j$, obtain the mean field estimates $\mu^{j,a}_{t+1,\eta}$ for
the next state $s_{t+1}^{j}$ using the mean field network according to Eq. 14

12: Set $y^{j}=r^{j}_{t}+\gamma
V_{\phi^{j}}(s^{j}_{t+1},\mu^{j,a}_{t+1,\eta})$ as the T.D. target according
to Eq. 12

13: For each $j$, update the critic by minimizing the loss
$L(\phi^{j})=(y^{j}-V_{\phi^{j}}(s^{j}_{t},\mu^{j,a}_{t,\eta}))^{2}$

14: For each $j$, update the actor using the log loss
$\mathcal{J}(\theta^{j})=\log\pi_{\theta^{j}}(a^{j}_{t}|s^{j}_{t})L(\phi^{j})$

15: Set the next mean field estimate as the current mean field estimate
$\mu^{j,a}_{t,\eta}=\mu^{j,a}_{t+1,\eta}$ and the next state as the current
state $s_{t}^{j}=s_{t+1}^{j}$ for all agents $j\in\\{1,\ldots,N\\}$

16: end while

##  Appendix I Experimental Details

In this section, we describe each of our game domains in detail, including the
reward functions. We also provide the implementation details of our
algorithms, especially the hyperparameters. We also discuss the wall-clock
times of our algorithmic implementations. Each episode for the Petting Zoo
environments has a maximum of 500 steps. In our implementation of MFQ and
MFAC, the agents learn in a decentralized fashion with independent networks
and use the previous mean field of the local neighbourhood instead of the
global mean field.

The first 5 domains are obtained from the Petting Zoo environment (Terry et
al. 2020), and the game parameters are mostly left unchanged from those given
in Terry et al. (2020). In these games, as agents can die during game play, we
use the agent networks saved in the last available episode during training for
the execution experiments. Complete details of these domains are given in each
of the sub-sections below.

### Battle Domain

This is the first domain from the Petting Zoo environment (Terry et al. 2020)
that is mixed cooperative-competitive. This domain was originally defined in
the MAgents simulator (Zheng et al. 2018). We have two teams of 25 agents,
each learning to cooperate against the members of the same team and compete
against the members of its opponent team. The agent gets rewarded for
attacking and killing agents of the opposing team. At the same time, the agent
is penalized for being attacked. In our implementation, each agent learns
using its local observation and cannot get global information. Each agent has
a view range of a circular radius of 6 units around it. Most rewards are left
as defaults, as given in Terry et al. (2020). The agents get a penalty of
-0.005 for each step (step reward) and a penalty of -0.1 for being killed. The
agents get a reward of 5 for attacking an opponent and a reward of 10 for
killing an opponent. There is an attack penalty of -0.1 (penalty for attacking
anything). Agents start with a specific number of hitpoints (HP) that are
damaged upon being attacked. Agents lose 2 HP when attacked and recover an HP
of 0.1 for every step that they are not attacked. They start with 10 HP, and
when this HP is completely lost, the agent dies. Each agent can view a
circular range of 6 units around it (view range) and can attack in a circular
range of 1.5 units around it (attack range). The action space of each agent is
a discrete set of 21 values, which corresponds to taking moving and attacking
actions in the environment. In this game, we assume that agents can get
perfect information about actions of other agents at a distance of 6 units
from themselves and no information beyond this point. In the execution phase,
a game is considered to be won by a team that kills more opponent agents. If
both teams kill the same number of agents, the team having the higher
cumulative reward is determined as the winner.

### Gather Domain

In this environment, all agents try to capture limited food available in the
environment and gain rewards. Each food needs to be attacked before it can be
captured (takes 5 attacks to capture food). This is a fully competitive game,
where all agents try to outcompete others in the environment and gain more
food for themselves. Agents can also kill other agents in the environment by
attacking them (just a single attack). Each agent gets a step penalty of
-0.01, an attack penalty (penalty for attack) of -2 and a death penalty
(punishment for dying) of -20. Also, each agent gets a reward of 20 for
attacking food and a reward of 60 for capturing the food. There are a total of
30 agents learning in our environment. The action space of each agent is a set
of 33 values. The agents have a view range of 7 and an attack range of 1. All
other conditions and rewards are the same as the Battle game.

### Combined Arms Domain

The Combined Arms environment is a heterogeneous large-scale team game with
two types of agents in each team. The first type is a ranged agent, which can
move fast and attack agents situated further away but has fewer HP. The second
type is the melee agent that can only attack close-by agents and move slowly;
however, they have more HP. The reward function for the agents is the same as
that given in the battle game. The action space of the melee agents is a
discrete set of 9 values, while the action space of the ranged agents is a
discrete set of 25 values. The actions correspond to moving in the environment
and attacking neighbouring agents. The ranged agents have a maximum HP of 3,
and the melee agents have a maximum HP of 10. The maximum HP is the limit
after which the HP of any agent cannot increase in this environment. Like the
battle domain, agents lose 2 HP for each time they are attacked and gain 0.1
HP for each step without being attacked. In our experiments, each team
consists of 25 agents, with 15 ranged and 10 melee agents at the start. The
view range is 6 and the attack range is 1 for melee agents. The view range is
6 and attack range is 2 for ranged agents. All other conditions and rewards
are the same as the Battle game. To create the mean field we choose to use the
action space of the type which has the larger number of actions (i.e. we use
the action space of the ranged agents).

### Tiger-Deer Domain

In the tiger-deer environment, tigers are the learning agents, cooperating
with each other to kill deer in the environment. At least two tigers need to
attack a deer together to get high rewards. The tigers start with an HP of 10
and gain an HP of 8 whenever they kill deer. The tigers lose an HP of 0.021 at
each step they do not eat a deer and die when they lose all the HP. In this
game, the deer move randomly in the environment, and start with an HP of 5 and
lose 1 HP upon attack. The tiger gets a reward of +1 for attacking a deer
alongside another tiger. In this game, each tiger is assumed to get perfect
information about the actions of other tigers at a distance of 4 units from
itself and no information beyond this point. The view range of the tiger is 4
and the attack range is 1. The tigers also get a shaping reward of 0.2 for
attacking a deer alone. All other rewards and conditions are the same as the
Battle game.

### Waterworld Domain

The Waterworld domain was first introduced as a part of the Stanford
Intelligent Systems Laboratory (SISL) environments by Gupta, Egorov, and
Kochenderfer (2017). We use the same domain adapted by the Petting Zoo
environment (Terry et al. 2020). This is a continuous action space
environment, where a group of pursuer agents aim to capture food and avoid
poison. These pursuers are the learning agents, while both food and poison
move randomly in the environment. This is a cooperative environment where
pursuer agents need to work together to capture food. At least two agents need
to attack a food particle together to be able to capture it. The action is a
two-element vector, where the first element corresponds to horizontal thrust
and the second element corresponds to vertical thrust. The agents choose to
use a thrust to make themselves move in a particular direction with a desired
speed. The action values are in the range [-1, +1]. Our domain contains 25
pursuer agents, 25 food particles and 10 poison particles. The food is not
destroyed but respawned upon capture. The agents get a reward of +10 upon
capturing food and a penalty of -1 for encountering poison. If a single agent
encounters food alone, it gets a shaping reward of +1. Each time an agent
applies thrust, the agent obtains a penalty of thrust penalty $\times$
||action||, where the value of thrust penalty is -0.5. Since this is a
cooperative environment, each agent is allowed access to the global mean field
action which is composed of actions of all agents in the environment, at each
time step. This is done to simplify this complex domain.

### Ride-Sharing Domain

In this domain, our problem formulation and environment are the same as that
described in Shah, Lowalekar, and Varakantham (2020). The demand distribution
is obtained from the publicly available New York Yellow Taxi Dataset
(NYYellowTaxi 2016). The overall approach follows six steps. First, the user