ifaamas [AAMAS ’24]Proc. of the 23rd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2024)May 6 – 10, 2024 Auckland, New
ZealandN. Alechina, V. Dignum, M. Dastani, J.S. Sichman (eds.) 2024 2024 1045
ETH Zürich Zürich Switzerland HSE University Moscow Russia ETH Zürich Zürich
Switzerland

# When is Mean-Field Reinforcement Learning Tractable and Relevant?

Batuhan Yardim<EMAIL_ADDRESS>,  Artur Goldman<EMAIL_ADDRESS>and  Niao He
<EMAIL_ADDRESS>
###### Abstract.

Mean-field reinforcement learning has become a popular theoretical framework
for efficiently approximating large-scale multi-agent reinforcement learning
(MARL) problems exhibiting symmetry. However, questions remain regarding the
applicability of mean-field approximations: in particular, their approximation
accuracy of real-world systems and conditions under which they become
computationally tractable. We establish explicit finite-agent bounds for how
well the MFG solution approximates the true $N$-player game for two popular
mean-field solution concepts. Furthermore, for the first time, we establish
explicit lower bounds indicating that MFGs are poor or uninformative at
approximating $N$-player games assuming only Lipschitz dynamics and rewards.
Finally, we analyze the computational complexity of solving MFGs with only
Lipschitz properties and prove that they are in the class of PPAD-complete
problems conjectured to be intractable, similar to general sum $N$ player
games. Our theoretical results underscore the limitations of MFGs and
complement and justify existing work by proving difficulty in the absence of
common theoretical assumptions.

###### Key words and phrases:

Mean-Field Games; Computational Complexity; Approximation

##  1\. Introduction

Multi-agent reinforcement learning (MARL) finds numerous impactful
applications in the real world Shavandi and Khedmati (2022); Wiering (2000);
Samvelyan et al. (2019); Rashedi et al. (2016); Matignon et al. (2007); Mao et
al. (2022). Despite the urgent need in practice, MARL remains a fundamental
challenge, especially in the setting with large numbers of agents due to the
so-called “curse of many agents” (Wang et al., 2020).

Mean-field games (MFG), a theoretical framework first proposed by Lasry and
Lions (2007) and Huang et al. (2006), permits the theoretical study of such
large-scale games by introducing mean-field simplification. Under certain
assumptions, the mean-field approximation leads to efficient algorithms for
the analysis of a particular type of $N$-agent competitive game where there
are symmetries between players and when $N$ is large. Such games appear widely
in for instance auctions Iyer et al. (2014), and cloud resource management Mao
et al. (2022). For the mean-field analysis, the game dynamics with $N$-players
must be _symmetric_ (i.e., each player must be exposed to the same rules) and
_anonymous_ (i.e., the effect of each player on the others should be
permutation invariant). Under this simplification, works such as Perrin et al.
(2020); Anahtarci et al. (2022); Guo et al. (2019); Yardim et al. (2023b);
Pérolat et al. (2022); Xie et al. (2021); Cui and Koeppl (2021) and many
others have analyzed reinforcement learning (RL) algorithms in the MFG limit
$N\rightarrow\infty$ to obtain a tractable approximation of many agent games,
providing learning guarantees under various structural assumptions.

Being a simplification, MFG formulations should ideally satisfy two
desiderata: (1) they should be _relevant_ , i.e., they are good approximations
of the original MARL problem and (2) they should be _tractable_ , i.e., they
are at least easier than solving the original MARL problem. In this work, we
would like to understand the extent to which MFGs satisfy these two
requirements, and we aim to answer two natural questions that remain
understudied:

  * •

_When are MFGs good approximations of the finite player games, when are they
not?_ In particular, are polynomially many agents always sufficient for mean-
field approximation to be effective?

  * •

_Is solving MFGs always computationally tractable, or more tractable than
directly solving the $N$-player game?_ In particular, can MFGs be solved in
polynomial or pseudo-polynomial time?

###  1.1. Related Work

Mean-field RL has been studied in various mathematical settings. In this work,
we focus on two popular formulations in particular: stationary mean-field
games (Stat-MFG, see e.g. Anahtarci et al. (2022); Guo et al. (2019)) and
finite-horizon MFG (FH-MFG, see e.g. Perrin et al. (2020); Pérolat et al.
(2022)). In the Stat-MFG setting the objective is to find a stationary policy
that is optimal with respect to its induced stationary distribution, while in
the FH-MFG setting, a finite-horizon reward is considered with a time-varying
policy and population distribution.

Existing results on MFG relevance/approximation. The approximation properties
of MFGs have been explored by several works in literature, as summarized in
Table 1. Finite-agent approximation bounds have been widely analyzed in the
case of stochastic mean-field differential games Carmona and Delarue (2013);
Carmona et al. (2018), albeit in the differential setting and without explicit
lower bounds. Recent works Anahtarci et al. (2022); Cui and Koeppl (2021) have
established that Stat-MFG Nash equilibria (Stat-MFG-NE) asymptotically
approximate the NE of $N$-player symmetric dynamic games under continuity
assumptions. The result by Saldi et al. (2018), as the basis of subsequent
proofs, shows asymptotic convergence for a large class of MFG variants and
only requires continuity of dynamics and rewards as well as minor technical
assumptions such as compactness and a form of local Lipschitz continuity.
However, such asymptotic convergence guarantees leave the question unanswered
if the MFG models are realistic in real-world games. Many games such as
traffic systems, financial markets, etc. naturally exhibit large $N$, however,
if $N$ must be astronomically large for good approximation, the real-world
impact of the mean-field analysis will be limited. Recently, Yardim et al.
(2023a) provided finite-agent approximation bounds of a special class of
stateless MFG, which assumes no state dynamics. We complement existing work on
approximation properties of both Stat-MFG and FH-MFG by providing explicit
upper and lower bounds for approximation.

Existing results on MFG tractability. The tractability of solving MFGs as a
proxy for MARL has been also heavily studied in the RL community under various
classes of structural assumptions. Since finding approximate Nash equilibria
for normal form games is PPAD-complete, a class believed to be computationally
intractable Daskalakis et al. (2009); Chen et al. (2009), solving the mean-
field approximation in many cases can be a tractable alternative. We summarize
recent work for computationally (or statistically) solving the two types of
MFGs below, with an in-depth comparison also provided in Table 2.

For Stat-MFG, under a contraction assumption RL algorithms such as Q-learning
Zaman et al. (2023); Anahtarci et al. (2022), policy mirror ascent Yardim et
al. (2023b), policy gradient methods Guo et al. (2022b), soft Q-learning Cui
and Koeppl (2021) and fictitious play Xie et al. (2021) have been shown to
solve Stat-MFG with statistical and computational efficiency. However, all of
these guarantees require the game to be heavily regularized as pointed out in
Cui and Koeppl (2021); Yardim et al. (2023b), inducing a non-vanishing bias on
the computed Nash. Moreover, in some works the population evolution is also
implicitly required to be contractive under all policies (see e.g. Guo et al.
(2019); Yardim et al. (2023b)), further restricting the analysis to
sufficiently smooth games. While Guo et al. (2022a) has proposed a method that
guarantees convergence to MFG-NE under differentiable dynamics, the algorithm
converges only when initialized sufficiently close to the solution. To the
best of our knowledge, there are neither RL algorithms that work without
regularization nor evidence of difficulty in the absence of such strong
assumptions: we complement the line of work by showing that unless dynamics
are sufficiently smooth, Stat-MFG is both computationally intractable and a
poor approximation.

A separate line of work analyzes the finite horizon problem. In this case,
when the dynamics are population-independent and the payoffs are monotone the
problem is known to be tractable. Algorithms such as fictitious play Perrin et
al. (2020) and mirror descent Pérolat et al. (2022) have been shown to
converge to Nash in corresponding continuous-time equations. Recent work has
also focused on the statistical complexity of the finite-horizon problem in
very general FH-MFG problems Huang et al. (2023), however, the algorithm
proposed is in general computationally intractable. In terms of computational
tractability and the approximation properties, our work complements these
results by demonstrating that (1) when dynamics depend on the population as
well an exponential approximation lower bound exists, and (2) in the absence
of monotonicity, the FH-MFG is provably as difficult as solving an $N$-player
game.

Finally, we note that there are several other settings and MFG solution
concepts have been analyzed. For instance, a certain class of infinite horizon
MFG has been shown to be equivalent to concave utility RL, proving finite-time
computational guarantees Geist et al. (2022).

###  1.2. Our Contribution

In this work, we formalize and provide answers to the two aforementioned
fundamental questions, first focusing on the approximation properties of MFG
in Section 3 and later on the computational tractability of MFG in Section 4.
Our contributions are summarized as follows.

Firstly, we introduce explicit finite-agent approximation bounds for finite
horizon and stationary MFGs (Table 1) in terms of exploitability in the finite
agent game. In both cases, we prove explicit upper bounds which quantify how
many agents a symmetric game must have to be well-approximated by the MFG,
which has been absent in the literature to the best of our knowledge. Our
approximation results only require a minimal Lipschitz continuity assumption
of the transition kernel and rewards. For FH-MFG, we prove a
$\mathcal{O}\left(\frac{(1-L^{H})H^{2}}{(1-L)\sqrt{N}}\right)$ upper bound for
the exploitabilty where $L$ is the Lipschitz modulus of the population
evolution operator: the upper bound exhibits an exponential dependence on the
horizon $H$. For the Stat-MFG we show that a
$\mathcal{O}\left(\frac{(1-\gamma)^{-3}}{\sqrt{N}}\right)$ approximation bound
can be established, but only if the population evolution dynamics are non-
expansive. Next, for the first time, we establish explicit lower bounds for
the approximation proving the shortcomings of the upper bounds are
fundamental. For the FH-MFG, we show that unless $N\geq\Omega(2^{H})$, an
exploitability linear in horizon $H$ is unavoidable when deploying the MFG
solution to the $N$ player game: hence in general the MFG equilibrium becomes
irrelevant quickly as the problem horizon increases. For Stat-MFG we establish
an $\Omega(N^{\log_{2}\gamma})$ lower bound when the population dynamics are
not restricted to non-expansive population operators, showing that a large
discount factor $\gamma$ also rapidly deteriorates the approximation
efficiency. Our lower bounds indicate that in the worst case, the number of
agents required for the approximation can grow exponentially in the problem
parameters, demonstrating the limitations of the MFG approximation.

Finally, from the computational perspective, we establish that both finite-
horizon and stationary MFGs can be PPAD-complete problems in general, even
when restricted to certain simple subclasses (Table 2). This shows that both
MFG problems are in general as hard as finding a Nash equilibrium of
$N$-player general sum games. Furthermore, our results imply that unless
PPAD=P there are no polynomial time algorithms for solving FH-MFG and Stat-
MFG, a result indicating computational intractability.

Work | MFG type | Key Assumptions | Approximation Rate (in Exploitability)
---|---|---|---
Carmona and Delarue, 2013 | Othera | Affine drift, Lipschitz derivatives |  $\mathcal{O}(N^{-1/(d+4)})$ ($d$ dimension of state space)
Saldi et al., 2018 | Otherb | Continuity |  $o(1)$ (asymptotic: convergence as $N\rightarrow\infty$)
Anahtarci et al., 2022 | Stat-MFG | Lipschitz $P,R$ \+ Regularized + Contractive $\Gamma_{P}$ |  $o(1)$ (asymptotic: convergence as $N\rightarrow\infty$)
Cui and Koeppl, 2021 | Stat-MFG | Continuity |  $o(1)$ (asymptotic: convergence as $N\rightarrow\infty$)
Yardim et al., 2023a | Otherc | Lipschitz $P,R$ | $\mathcal{O}(\nicefrac{{1}}{{\sqrt{N}}})$
Theorem 3.1 | FH-MFG | Lipschitz $P,R$ |  $\mathcal{O}\left(\frac{H^{2}(1-L^{H})}{(1-L)\sqrt{N}}\right)$, $L$ Lipschitz modulus of $\Gamma_{P}$
Theorem 1 | FH-MFG | Lipschitz $P,R$ |  $\Omega(H)$ unless $N\geq\Omega(2^{H})$
Theorem 3.2 | Stat-MFG | Lipschitz $P,R$ \+ Non-expansive $\Gamma_{P}$ | $\mathcal{O}(\nicefrac{{(1-\gamma)^{-3}}}{{\sqrt{N}}})$
Theorem 3.2 | Stat-MFG | Lipschitz $P,R$ | $\Omega(N^{-\log_{2}\gamma^{-1}}))$
Table 1. Selected approximation results for MFG. Notes: a stochastic differential MFG, b infinite-horizon discounted setting with non-stationary policies, c stateless/static MFG setting.  Work | MFG Type | Key Assumptions | Iteration/Sample Complexity result
---|---|---|---
Anahtarci et al., 2022 | Stat-MFG | Lipschitz $P,R$ \+ Regularization + Contractive $\Gamma_{P}$ |  $\widetilde{\mathcal{O}}(\varepsilon^{-4|\mathcal{A}|})$ samples, $\mathcal{O}(\log\varepsilon^{-1})$ iterations
Geist et al., 2022 | Othera | Concave potential |  $\mathcal{O}(\varepsilon^{-2})$ iterations
Perrin et al., 2020 | FH-MFG | Monotone $R$, $\mu$-independent $P$ |  $\mathcal{O}(\varepsilon^{-1})$ (continuous time analysis)
Pérolat et al., 2022 | FH-MFG | Monotone $R$, $\mu$-independent $P$ |  $\mathcal{O}(\varepsilon^{-1})$ (continuous time analysis)
Zaman et al., 2023 | Stat-MFG | Lipschitz $P,R$ \+ Regularization + Contractive $\Gamma_{P}$ |  $\mathcal{O}(\varepsilon^{-4})$ samples
Cui and Koeppl, 2021 | Stat-MFG | Lipschitz $P,R$ \+ Regularization |  $\mathcal{O}(\log\varepsilon^{-1})$ iterations
Yardim et al., 2023a | Otherb | Monotone and Lipschitz $R$ |  $\mathcal{O}(\varepsilon^{-2})$ samples ($N$-player)
Yardim et al., 2023b | Stat-MFG | Lipschitz $P,R$ \+ Regularization + Contractive $\Gamma_{P}$ |  $\mathcal{O}(\varepsilon^{-2})$ samples ($N$-player)
Theorem 4.2 | Stat-MFG | Lipschitz $P,R$ |  PPAD-complete
Theorem 4.3 | FH-MFG | Lipschitz $P,R$ \+ $\mu$-independent $P$ |  PPAD-complete
Theorem 4.3 | FH-MFG | Linear $P,R$ \+ $\mu$-independent $P$ |  PPAD-complete
Table 2. Selected results for computing MFG-NE from literature. In the
assumptions column, contractive $\Gamma_{P}$ indicates that for all
$\pi\in\Pi$, $\Gamma_{P}(\cdot,\pi)$ is a contraction, and regularization
indicates that a non-vanishing bias is present. Notes: a infinite-horizon,
population dependence through the discounted state distribution. b
stateless/static MFG.

##  2\. Mean-Field Games: Definitions, Solution Concepts

#### Notation.

Throughout this work, we assume $\mathcal{S},\mathcal{A}$ are finite sets. For
a finite set $\mathcal{X}$, $\Delta_{\mathcal{X}}$ denotes the set of
probability distributions on $\mathcal{X}$. The norm used will not
fundamentally matter for our results, we choose to equip
$\Delta_{\mathcal{S}},\Delta_{\mathcal{A}}$ with the norm $\|\cdot\|_{1}$. We
define the set of Markov policies
$\Pi:=\\{\pi:\mathcal{S}\rightarrow\Delta_{\mathcal{A}}\\}$,
$\Pi_{H}:=\\{\\{\pi_{h}\\}_{h=0}^{H-1}:\pi_{h}\in\Pi,\forall h\\}$ and
$\Pi_{H}^{N}:=\\{\\{\pi_{h}^{i}\\}_{h=0,i=0}^{H-1,N}:\pi_{h}^{i}\in\Pi,\forall
h\\}$. For policies $\pi,\pi^{\prime}\in\Pi$ denote
$\|\pi-\pi^{\prime}\|_{1}=\sup_{s\in\mathcal{S}}\|\pi(\cdot|s)-\pi^{\prime}(\cdot|s)\|_{1}$.
We denote $d(x,y):=\mathbbm{1}_{\\{x\neq y\\}}$ for $x,y$ in $\mathcal{A}$ or
$\mathcal{S}$. For $\boldsymbol{\pi}\in\Pi^{N},\pi^{\prime}\in\Pi$, we define
$(\pi^{\prime},\boldsymbol{\pi}^{-i})\in\Pi^{N}$ as the policy profile where
the $i$-th policy has been replaced by $\pi^{\prime}$. Likewise, for
$\boldsymbol{\pi}\in\Pi^{N}_{H},\boldsymbol{\pi}^{\prime}\in\Pi_{H}$, we
denote by $(\boldsymbol{\pi}^{\prime},\boldsymbol{\pi}^{-i})\in\Pi^{N}_{H}$
the policy profile where the $i$-th player’s policy has been replaced by
$\boldsymbol{\pi}^{\prime}$. For any $N\in\mathbb{N}_{\geq 0}$,
$[N]:=\\{1,\ldots,N\\}$.

MFGs introduce a dependence on the population distribution over states of the
rewards and dynamics. We will strictly consider Lipschitz continuous rewards
and dynamics, which is a common assumption in literature Guo et al. (2019);
Anahtarci et al. (2022); Yardim et al. (2023b); Xie et al. (2021), formalized
below.

######  Definition  (Lipschitz dynamics, rewards).

For some $L\geq 0$, we define the set of $L$-Lipschitz reward functions and
state transition dynamics as

$\displaystyle\mathcal{R}_{L}:=\Big{\\{}R:\mathcal{S}\times\mathcal{A}\times\Delta_{\mathcal{S}}\rightarrow$
$\displaystyle[0,1]\,:\,|R(s,a,\mu)-R(s,a,\mu^{\prime})|$ $\displaystyle\leq
L\|\mu-\mu^{\prime}\|_{1},\forall s,a,\mu,\mu^{\prime}\Big{\\}},$
$\displaystyle\mathcal{P}_{L}:=\Big{\\{}P:\mathcal{S}\times\mathcal{A}\times\Delta_{\mathcal{S}}\rightarrow$
$\displaystyle\Delta_{\mathcal{S}}\,:\,\|P(s,a,\mu)-P(s,a,\mu^{\prime})\|_{1}$
$\displaystyle\leq L\|\mu-\mu^{\prime}\|_{1},\forall
s,a,\mu,\mu^{\prime}\Big{\\}}.$

Moreover, we define the set of Lipschitz rewards and dynamics as
$\mathcal{R}:=\bigcup_{L\geq
0}\mathcal{R}_{L},\quad\mathcal{P}:=\bigcup_{L\geq 0}\mathcal{P}_{L}$
respectively.

We note that there are interesting MFGs with non-Lipschitz dynamics and
rewards, however, even the existence of Nash is not guaranteed in this case.
Lipschitz continuity is a minimal assumption under which solutions to MFG
always exist, and as our aim is to prove lower bounds and difficulty we will
adopt this assumption. Solving MFG with non-Lipschitz dynamics is more
challenging than Lipschitz continuous MFG (the latter being a subset of the
former), hence our difficulty results will apply.

#### Operators.

We will define the useful population operators
$\Gamma_{P}:\Delta_{\mathcal{S}}\times\Pi\rightarrow\Delta_{\mathcal{S}}$,
$\Gamma_{P}^{H}:\Delta_{\mathcal{S}}\times\Pi\rightarrow\Delta_{\mathcal{S}}$,
and
$\Lambda^{H}_{P}:\Delta_{\mathcal{S}}\times\Pi_{H}\rightarrow\Delta_{\mathcal{S}}^{H}$
as

$\displaystyle\Gamma_{P}(\mu,\pi)$
$\displaystyle:=\sum_{s\in\mathcal{S},a\in\mathcal{A}}\mu(s)\pi(a|s)P(\cdot|s,a,\mu),$
$\displaystyle\Gamma^{H}_{P}(\mu,\pi)$
$\displaystyle:=\underbrace{\Gamma_{P}(\dots\Gamma_{P}(\Gamma_{P}(\mu,\pi),\pi)\dots),\pi)}_{H\text{
times}},$ $\displaystyle\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi})$
$\displaystyle:=\big{\\{}\underbrace{\Gamma_{P}(\dots\Gamma_{P}(\Gamma_{P}(\mu_{0},\pi_{0}),\pi_{1})\dots,\pi_{h-1})}_{h\text{
times}}\big{\\}}_{h=0}^{H-1}$

for all
$n\in\mathbb{N}_{>0},\pi\in\Pi,\boldsymbol{\pi}=\\{\pi_{h}\\}_{h=0}^{H-1}\in\Pi_{H},P\in\mathcal{P},\mu_{0}\in\Delta_{\mathcal{S}}$.

Finally, we will need the following Lipschitz continuity result for the
$\Gamma_{P}$ operator.

###### Lemma

(Yardim et al., 2023b, Lemma 3.2) Let $P\in\mathcal{P}_{K_{\mu}}$ for
$K_{\mu}>0$ and

$\displaystyle K_{s}:=\sup_{\begin{subarray}{c}s,s^{\prime}\\\
a,\mu\end{subarray}}\left\|P(s,a,\mu)-P(s^{\prime},a,\mu)\right\|_{1},K_{a}:=\sup_{\begin{subarray}{c}a,a^{\prime}\\\
s,\mu\end{subarray}}\left\|P(s,a,\mu)-P(s,a^{\prime},\mu)\right\|_{1}.$

Then it holds for all
$\mu,\mu^{\prime}\in\Delta_{\mathcal{S}},\pi,\pi^{\prime}\in\Pi$ that:

$\|\Gamma_{P}(\mu,\pi)-\Gamma_{P}(\mu^{\prime},\pi^{\prime})\|_{1}\leq
L_{pop,\mu}\|\mu-\mu^{\prime}\|_{1}+\frac{K_{a}}{2}\|\pi-\pi^{\prime}\|_{1},$

where $L_{pop,\mu}:=(K_{\mu}+\frac{K_{s}}{2}+\frac{K_{a}}{2})$ for all
$\pi,\pi^{\prime}\in\Pi$, $\mu,\mu^{\prime}\in\Delta_{\mathcal{S}}$.

In particular, in our settings, Lemma 2 indicates that $\Gamma_{P}$ is always
Lipschitz continuous if $P\in\mathcal{P}$, a property which will become
significant for approximation analysis.

We will be interested in two classes of MFG solution concepts that lead to
different analyses: infinite horizon stationary MFG Nash equilibrium (Stat-
MFG-NE) and finite horizon MFG Nash equilibrium (FH-MFG-NE). The first problem
widely studied in literature is the stationary MFG equilibrium problem, see
for instance Anahtarci et al. (2022); Yardim et al. (2023b); Guo et al. (2019,
2022b); Xie et al. (2021). We formalize this solution concept below.

######  Definition  (Stat-MFG).

A stationary MFG (Stat-MFG) is defined by the tuple
$(\mathcal{S},\mathcal{A},P,R,\gamma)$ for Lipschitz dynamics and rewards
$P\in\mathcal{P},R\in\mathcal{R}$, discount factor $\gamma\in(0,1)$. For any
$(\mu,\pi)\in\Delta_{\mathcal{S}}\times\Pi$, we define the $\gamma$-discounted
infinite horizon expected reward as

$\displaystyle
V^{\gamma}_{P,R}(\mu,\pi):=\operatorname{\mathbb{E}}\left[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t},\mu)\middle|\begin{subarray}{c}s_{0}\sim\mu,\quad
a_{t}\sim\pi(s_{t})\\\ s_{t+1}\sim P(s_{t},a_{t},\mu)\end{subarray}\right].$

A policy-population pair $(\mu^{*},\pi^{*})\in\Delta_{\mathcal{S}}\times\Pi$
is called a Stat-MFG Nash equilibrium if the two conditions hold:

Stability: $\displaystyle\mu^{*}=\Gamma_{P}(\mu^{*},\pi^{*}),$ Optimality:
$\displaystyle
V^{\gamma}_{P,R}(\mu^{*},\pi^{*})=\max_{\pi\in\Pi}V^{\gamma}_{P,R}(\mu^{*},\pi).$
(Stat-MFG-NE)

The second MFG concept that we will consider has a finite time horizon, and is
also common in literature Perolat et al. (2015); Perrin et al. (2020);
Laurière et al. (2022); Huang et al. (2023). In this case, the population
distribution is permitted to vary over time, and the objective is to find an
optimal non-stationary policy with respect to the population distribution it
induces. We formalize this problem and the corresponding solution concept
below.

######  Definition  (FH-MFG).

A finite horizon MFG problem (FH-MFG) is determined by the tuple
$(\mathcal{S},\mathcal{A},H,P,R,\mu_{0})$ where $H\in\mathbb{Z}_{>0}$,
$P\in\mathcal{P},R\in\mathcal{R},\mu_{0}\in\Delta_{\mathcal{S}}$. For
$\boldsymbol{\pi}=\\{\pi_{h}\\}_{h=0}^{H}\in\Pi_{H},\bm{\mu}=\\{\mu_{h}\\}_{h=0}^{H-1}\in\Delta_{\mathcal{S}}^{H}$,
define the expected reward and exploitability as

$\displaystyle V_{P,R}^{H}\left(\bm{\mu},\boldsymbol{\pi}\right)$
$\displaystyle:=\operatorname{\mathbb{E}}\left[\sum_{h=0}^{H-1}R(s_{h},a_{h},\mu_{h})\middle|\begin{subarray}{c}s_{0}\sim\mu_{0},\quad
a_{h}\sim\pi_{h}(s_{h})\\\ s_{h+1}\sim
P(s_{h},a_{h},\mu_{h})\end{subarray}\right],$
$\displaystyle\mathcal{E}_{P,R}^{H}(\boldsymbol{\pi})$
$\displaystyle:=\max_{\boldsymbol{\pi}^{\prime}\in\Pi^{H}}V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}),\boldsymbol{\pi}^{\prime})-V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}),\boldsymbol{\pi}).$

Then, the FH-MFG Nash equilibrium is defined as:

Policy
$\displaystyle\boldsymbol{\pi}^{*}=\\{\pi^{*}_{h}\\}_{h=0}^{H-1}\in\Pi_{H}\text{
such that }$
$\displaystyle\mathcal{E}_{P,R}^{H}(\\{\pi^{*}_{h}\\}_{h=0}^{H-1})=0.$ (FH-
MFG-NE)

##  3\. Approximation Properties of MFG

As established in literature, the reason the FH-MFG and Stat-MFG problems are
studied is the fact that they can approximate the NE of certain symmetric
games with $N$ players, establishing the main relevance of the formulations in
the real world. Such results are summarized in Table 1.

In this section, we study how efficient this convergence is and also related
lower bounds. For these purposes, we first define the corresponding _finite-
player_ game of each mean-field game problem: to avoid confusion, we call
these games _symmetric anonymous dynamic games_ (SAG). Afterwards, for each
solution concept, we will first establish (1) an upper bound on the
approximation error (i.e. the exploitability) due to the mean-field, and (2) a
lower bound demonstrating the worst-case rate. We will present the main
outlines of proofs, and postpone computation-intensive derivations to the
supplementary material of the paper.

###  3.1. Approximation Analysis of FH-MFG

Firstly, we define the finite-player game that is approximately solved by the
FH-MFG-NE.

######  Definition  ($N$-FH-SAG).

An $N$-player finite horizon SAG ($N$-FH-SAG) is determined by the tuple
$(N,\mathcal{S},\mathcal{A},H,P,R,\mu_{0})$ such that
$N\in\mathbb{Z}_{>0},H\in\mathbb{Z}_{>0}$,
$P\in\mathcal{P},R\in\mathcal{R},\mu_{0}\in\Delta_{\mathcal{S}}$. For any
$\boldsymbol{\pi}=\\{\pi_{h}^{i}\\}_{h=0,\ldots,H-1,i\in[N]}\in\Pi_{H}^{N}$,
we define the expected mean reward and exploitability of player $i$ as

$\displaystyle J_{P,R}^{H,N,(i)}\left(\boldsymbol{\pi}\right)$
$\displaystyle:=\operatorname{\mathbb{E}}\left[\sum_{h=0}^{H-1}R(s_{h}^{i},a_{h}^{i},\widehat{\mu}_{h})\middle|\begin{subarray}{c}\forall
j:s_{0}^{j}\sim\mu_{0},\quad a_{h}^{j}\sim\pi_{h}^{j}(s_{h}^{j})\\\
s_{h+1}^{j}\sim
P(s_{h}^{j},a_{h}^{j},\widehat{\mu}_{h}),\widehat{\mu}_{h}:=\frac{1}{N}\sum_{j}\mathbf{e}_{s^{j}_{h}}\end{subarray}\right],$
$\displaystyle\mathcal{E}_{P,R}^{H,N,(i)}(\boldsymbol{\pi})$
$\displaystyle:=\max_{\boldsymbol{\pi}^{\prime}\in\Pi^{H}}J_{P,R}^{H,N,(i)}(\boldsymbol{\pi}^{\prime},\boldsymbol{\pi}^{-i})-J_{P,R}^{H,N,(i)}(\boldsymbol{\pi}).$

Then, the $N$-FH-SAG Nash equilibrium is defined as:

$N$-tuple of policies
$\displaystyle\\{\pi^{(i),*}_{h}\\}_{h=0}^{H-1}\in\Pi^{N}_{H}\text{ such that
}$ $\displaystyle\forall i:\mathcal{E}_{P,R}^{H,N,(i)}$
$\displaystyle(\\{\pi^{*}_{h}\\}_{h=0}^{H-1})=0.$ ($N$-FH-SAG-NE)

If instead $\mathcal{E}_{P,R}^{H,N,(i)}(\boldsymbol{\pi})\leq\delta$ for all
$i$, then $\boldsymbol{\pi}$ is called a $\delta$-$N$-FH-SAG Nash equilibrium.

The above definition corresponds to a real-world problem as the function
$J_{P,R}^{H,N,(i)}$ expresses the expected total payoff of each player: hence
a $\delta$-$N$-MFG-NE is a Nash equilibrium of a concrete $N$-player game in
the traditional game theoretical sense. Also, note that now in the definition
transition probabilities and rewards depend on $\widehat{\mu}_{h}$ which is
the $\mathcal{F}(\\{s_{h}^{i}\\}_{i})=\mathcal{F}_{h}$-measurable random
vector of the empirical state distribution at time $h$ of all agents.

Firstly, we provide a positive result well-known in literature: the $N$-FH-SAG
is approximately solved by the FH-MFG-NE policy. Unlike some past works, we
establish an explicit rate of convergence in terms of $N$ and problem
parameters.

[Approximation of $N$-FH-SAG] Let $(\mathcal{S},\mathcal{A},H,P,R,\mu_{0})$ be
a FH-MFG with $P\in\mathcal{P},R\in\mathcal{R}$ and with a FH-MFG-NE
$\boldsymbol{\pi}^{*}\in\Pi_{H}$, and for any $N\in\mathbb{N}_{>0}$ let
$\boldsymbol{\pi}_{N}^{*}:=(\underbrace{\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*}}_{\text{$N$
times}})\in\Pi_{H}^{N}$. Let $L>0$ be the Lipschitz constant of $\Gamma_{P}$
in $\mu$, and let $\mathcal{G}_{N}:=(N,\mathcal{S},\mathcal{A},H,P,R,\mu_{0})$
be the corresponding $N$-player game. Then:

  1. (1)

If $L=1$, then for all $i\in[N]$,
$\mathcal{E}_{P,R}^{H,N,(i)}(\boldsymbol{\pi}^{*}_{N})\leq\operatorname{\mathcal{O}}(\frac{H^{3}}{\sqrt{N}})$,
that is, $\boldsymbol{\pi}^{*}_{N}$ is a
$\mathcal{O}(\frac{H^{3}}{\sqrt{N}})$-NE of $\mathcal{G}_{N}$.

  2. (2)

If $L\neq 1$, then for all $i\in[N]$,
$\mathcal{E}_{P,R}^{H,N,(i)}(\boldsymbol{\pi}^{*}_{N})\leq\operatorname{\mathcal{O}}\left(\frac{H^{2}(1-L^{H})}{(1-L)\sqrt{N}}\right)$,
that is, $\boldsymbol{\pi}^{*}_{N}$ is a
$\operatorname{\mathcal{O}}\left(\frac{H^{2}(1-L^{H})}{(1-L)\sqrt{N}}\right)$-NE
of $\mathcal{G}_{N}$.

###### Proof.

_(sketch)_ Certain aspects of our proof will mirror the techniques introduced
by Saldi et al. (2018), although we establish an explicit bound. We first
bound the expected empirical population deviation given by
$\operatorname{\mathbb{E}}[\|\widehat{\mu}_{h}-\mu^{\boldsymbol{\pi}}_{h}\|_{1}]=\mathcal{O}\left(\frac{L^{h}}{\sqrt{N}}\right)$
with an inductive concentration argument: at each step $h+1$, given past
states $\widehat{\mu}_{h}$, the empirical distribution $\widehat{\mu}_{h}$ is
a sum of $N$ independent identically distributed sub-Gaussian random
variables. Next, by utilizing the Lipschitz property of rewards and bounding
deviation from the theoretical rewards the result follows in two computational
steps: (1) we show that
$\left|J_{P,R}^{H,N,(1)}(\boldsymbol{\pi},\dots,\boldsymbol{\pi})-V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}),\boldsymbol{\pi})\right|\leq\mathcal{O}(\nicefrac{{1}}{{\sqrt{N}}})$,
and similarly (2) we show that for any policy sequence
$\boldsymbol{\pi}^{\prime}\in\Pi_{h}$, we have
$\left|J_{P,R}^{H,N,(1)}(\boldsymbol{\pi}^{\prime},\boldsymbol{\pi},\dots,\boldsymbol{\pi})-V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}),\boldsymbol{\pi}^{\prime})\right|\leq\mathcal{O}(\nicefrac{{1}}{{\sqrt{N}}})$.
The result follows by definition of exploitability, with explicit constants
shown in the appendix. ∎

$\Gamma_{P}$ in Theorem 3.1 is always $L$-Lipschitz in $\mu$ for some $L$ by
Lemma 2. When $L>1$, the upper bound
$\mathcal{O}\left(\nicefrac{{(1+L^{H})H^{2}}}{{\sqrt{N}}}\right)$ has an
exponential dependence on the Lipschitz constant of the operator $\Gamma_{P}$.
However, for games with longer horizons, the upper bound might require an
unrealistic amount of agents $N$ to guarantee a good approximation due to the
exponential dependency. Next, we establish a worst-case result demonstrating
that this is not avoidable without additional assumptions.

$s_{\text{Left}}$$s_{\text{LB}}$$s_{\text{LA}}$$s_{\text{RA}}$$s_{\text{RB}}$$s_{\text{Right}}$$\mathbbm{1}_{\\{a=a_{\text{B}}\\}}$$\mathbbm{1}_{\\{a=a_{\text{A}}\\}}$$\mathbbm{1}_{\\{a=a_{\text{A}}\\}}$$\mathbbm{1}_{\\{a=a_{\text{B}}\\}}$
Figure 1. Visualization of the counterexample. All orange edges have
probability $\omega_{\varepsilon}(\mu(s_{\text{RA}})+\mu(s_{\text{RB}}))$,
green edges have probability
$\omega_{\varepsilon}(\mu(s_{\text{LA}})+\mu(s_{\text{LB}}))$ independent of
action taken. Edges with probability $0$ are not drawn.

[Approximation lower bound for $N$-FH-SAG] There exists
$\mathcal{S},\mathcal{A}$ and
$P\in\mathcal{P}_{8},R\in\mathcal{R}_{2},\mu_{0}\in\Delta_{\mathcal{S}}$ such
that the following hold:

  1. (1)

For each $H>0$, the FH-MFG defined by
$(\mathcal{S},\mathcal{A},H,P,R,\mu_{0})$ has a _unique_ solution
$\boldsymbol{\pi}^{*}_{H}$ (up to modifications on zero-probability sets),

  2. (2)

For any $H,h>0$, in the $N$-FH-SAG it holds that
$\operatorname{\mathbb{E}}_{H}[\|\widehat{\mu}_{h}-\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}^{*}_{H})_{h}\|_{1}]\geq\Omega\left(\min\\{\
1,\frac{2^{H}}{\sqrt{N}}\\}\right)$.

  3. (3)

For any $H,N>0$ either $N\geq\Omega(2^{H})$, or for each player $i\in[N]$ it
holds that
$\mathcal{E}_{P,R}^{H,N,(i)}(\boldsymbol{\pi}^{*}_{H},\ldots,\boldsymbol{\pi}^{*}_{H})\geq\Omega(H)$.

###### Proof.

_(sketch)_ We provide the basic idea of the proof and leave the cumbersome
computations to the appendix. The proof is constructive: we construct an
explicit FH-MFG where the statements hold, depicted in Figure 1. The FH-MFG
will have 6 states and two actions defined as sets
$\mathcal{S}=\\{s_{\text{Left}},s_{\text{Right}},s_{\text{LA}},s_{\text{LB}},s_{\text{RA}},s_{\text{RB}}\\}$
and $\mathcal{A}=\\{a_{\text{A}},a_{\text{B}}\\}.$ We define the initial state
distribution with
$\bm{\mu}_{0}(s_{\text{Left}})=\bm{\mu}_{0}(s_{\text{Right}})=\nicefrac{{1}}{{2}}$.
The colored state transition probabilities are given by the function:

$\displaystyle\omega_{\epsilon}(x)$ $\displaystyle=\begin{cases}1,\quad
x>\nicefrac{{1}}{{2}}+\epsilon\\\ 0,\quad x<\nicefrac{{1}}{{2}}-\epsilon\\\
\frac{1}{2}+\frac{x-\nicefrac{{1}}{{2}}}{2\epsilon},\quad
x\in[\nicefrac{{1}}{{2}}-\epsilon,\nicefrac{{1}}{{2}}+\epsilon]\end{cases}.$

The uniform policy over all actions $\boldsymbol{\pi}^{*}$ at all states will
be the unique FH-MFG-NE for all $H$, and the mean-field population
distribution for all even $h$ will be
$\mu_{h}^{*}(s_{\text{Left}})=\mu^{*}_{h}(s_{\text{Right}})=\nicefrac{{1}}{{2}}$.
However, for finite $N$, using an anti-concentration bound on the binomial, we
can show that with probability at least $\nicefrac{{1}}{{10}}$,
$\|\mu_{0}^{*}-\widehat{\mu}_{h}\|_{1}\geq\nicefrac{{1}}{{\sqrt{N}}}$. Using
the fact that $\omega_{\epsilon}$ is $(2\epsilon)^{-1}$-expansive in the
interval $[\nicefrac{{1}}{{2}}-\epsilon,\nicefrac{{1}}{{2}}+\epsilon]$, we can
then show that the empirical population distribution exponentially diverges
from the mean-field, that is
$\operatorname{\mathbb{E}}[\|\mu_{2h}^{*}-\widehat{\mu}_{2h}\|_{1}]\geq\Omega(\nicefrac{{5^{h}}}{{\sqrt{N}}})$
until time $K:=\log_{5}\sqrt{N}$. Moreover, with a series of concentration
bounds, it can be shown that within an expected number of
$\operatorname{\mathcal{O}}(\log N)$ steps, all agents will converge to either
$s_{\text{Left}}$ or $s_{\text{Right}}$ during even rounds. Only the colored
transitions are defined to have non-zero rewards, whose definition (provided
in the supplementary) guarantees that the exploitability suffered scales
linearly with $H$ after $N$ agents concentrate on the same state in even
steps. ∎

This result shows that without further assumptions, the FH-MFG solution might
suffer from exponential exploitability in $H$ in the $N$-player game. In such
cases, to avoid the concrete $N$-player game from deviating from the mean-
field behavior too fast, either $H$ must be small or $P$ must be sufficiently
smooth in $\mu$. We note that the typical assumption in the finite-horizon
setting that $P\in\mathcal{P}_{0}$ (see e.g. Perrin et al. (2020); Geist et
al. (2022)) avoids this lower bound since in this case $\Gamma_{P}(\cdot,\pi)$
is simply multiplication by a stochastic matrix which is always non-expansive
($L=1$). We also note at the expense of simplicity a stronger counter-example
inducing exploitability $\Omega(H)$ unless $N\geq\Omega((L-\epsilon)^{H})$ for
all $\epsilon>0$ can be constructed, where $P\in\mathcal{P}_{L}$.

#### A remark.

The proof of Theorem 1 in fact suggests that for finite $N$ and large horizon
$H$, there exists a time-homogenous policy $\widebar{\pi}^{\star}\in\Pi$
different than the FH-MFG solution such that for
$\widebar{\boldsymbol{\pi}}^{\star}_{H}:=\\{\widebar{\pi}^{\star}\\}_{h=0}^{H-1}\in\Pi_{H}$,
the time-averaged exploitability of $\widebar{\boldsymbol{\pi}}^{\star}_{H}$
is small: $\forall
i\in[N]:H^{-1}\mathcal{E}_{P,R}^{H,N,(i)}(\widebar{\boldsymbol{\pi}}^{\star}_{H},\ldots,\widebar{\boldsymbol{\pi}}^{\star}_{H})\leq\operatorname{\mathcal{O}}(H^{-1}\log_{2}N).$

###  3.2. Approximation Analysis of Stat-MFG

Similarly, we introduce the $N$-player game corresponding to the Stat-MFG
solution concept.

######  Definition  ($N$-Stat-SAG).

An $N$-player stationary SAG ($N$-Stat-SAG) problem is defined by the tuple
$(N,\mathcal{S},\mathcal{A},P,R,\gamma)$ for Lipschitz dynamics and rewards
$P\in\mathcal{P},R\in\mathcal{R}$, discount factor $\gamma\in(0,1)$. For any
$(\mu,\boldsymbol{\pi})\in\Delta_{\mathcal{S}}\times\Pi^{N}$, the $N$-player
$\gamma$-discounted infinite horizon expected reward is defined as:

$\displaystyle
J_{P,R}^{\gamma,N,(i)}(\mu,\boldsymbol{\pi}):=\operatorname{\mathbb{E}}\left[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t}^{i},a_{t}^{i},\widehat{\mu}_{t})\middle|\begin{subarray}{c}a_{t}^{j}\sim\pi^{j}(s_{t}^{j}),\widehat{\mu}_{t}:=\frac{\sum_{j}\mathbf{e}_{\text{\tiny$s^{j}_{h}$}}}{N}\\\
s_{0}^{j}\sim\mu,s_{t+1}^{i}\sim
P(s_{t}^{i},a_{t}^{i},\widehat{\mu}_{t})\end{subarray}\right].$

A policy profile-population pair
$(\mu^{*},\boldsymbol{\pi}^{*})\in\Delta_{\mathcal{S}}\times\Pi^{N}$ is called
an $N$-Stat-SAG Nash equilibrium if:

$\displaystyle
J_{P,R}^{\gamma,N,(i)}(\mu^{*},\boldsymbol{\pi}^{*})=\max_{\pi\in\Pi}J_{P,R}^{\gamma,N,(i)}(\mu^{*},(\pi,\boldsymbol{\pi}^{*,-i})).$
($N$-Stat-SAG-NE)

If instead
$J_{P,R}^{\gamma,N,(i)}(\mu^{*},\boldsymbol{\pi}^{*})\geq\max_{\pi\in\Pi}J_{P,R}^{\gamma,N,(i)}(\mu^{*},(\pi,\boldsymbol{\pi}^{*,-i}))-\delta$,
then we call $\mu^{*},\pi^{*}$ a $\delta$-$N$-Stat-SAG Nash equilibrium.

[Approximation of $N$-Stat-SAG] Let $(\mathcal{S},\mathcal{A},H,P,R,\gamma)$
be a Stat-MFG and $(\mu^{*},\pi^{*})\in\Delta_{\mathcal{S}}\times\Pi$ be a
corresponding Stat-MFG-NE. Furthermore, assume that $\Gamma_{P}(\cdot,\pi)$ is
non-expansive in the $\ell_{1}$ norm for any $\pi$, that is,
$\|\Gamma_{P}(\mu,\pi)-\Gamma_{P}(\mu^{\prime},\pi)\|_{1}\leq\|\mu-\mu^{\prime}\|_{1}.$
Then, $(\mu^{*},\boldsymbol{\pi}^{*})\in\Delta_{\mathcal{S}}\times\Pi^{N}$ is
a $\operatorname{\mathcal{O}}\left(\frac{1}{\sqrt{N}}\right)$ Nash equilibrium
for the $N$-player game where
$\boldsymbol{\pi}^{*}_{N}:=(\pi^{*},\ldots,\pi^{*})$, that is, for all $i$,

$\displaystyle
J_{P,R}^{\gamma,N,(i)}(\mu^{*},\boldsymbol{\pi}^{*}_{N})\geq\max_{\pi\in\Pi}J_{P,R}^{\gamma,N,(i)}(\mu^{*},(\pi,\boldsymbol{\pi}^{*,-i}_{N}))-\operatorname{\mathcal{O}}\left(\frac{(1-\gamma)^{-3}}{\sqrt{N}}\right).$

###### Proof.

_(sketch)_ Let $(\mu^{*},\pi^{*})$ be a Stat-MFG-NE. The proof method is very
similar to the FH-MFG case: we first bound the expected deviation from the
stable distribution $\mu^{*}$ given by
$\operatorname{\mathbb{E}}[\|\widehat{\mu}-\mu^{*}\|_{1}]$. The truncated
expected rewards can be controlled using similar arguments to the FH-MFG case,
and an application of the dominated convergence theorem yields the
exploitability for the infinite horizon discounted setting. ∎

We also establish an approximation lower bound for the $N$-Stat-SAG. In this
case, the question is if the non-expansive $\Gamma_{P}$ assumption is
necessary for the optimal $\mathcal{O}(\nicefrac{{1}}{{\sqrt{N}}})$ rate. The
below results affirm this: in for Stat-MFG-NE with expansive $\Gamma_{P}$, we
suffer from an exploitability of $\omega(\nicefrac{{1}}{{\sqrt{N}}})$ in the
$N$-agent case.

[Lower bound for $N$-Stat-SAG] For any
$N\in\mathbb{N}_{>0},\gamma\in(\nicefrac{{1}}{{\sqrt{2}}},1)$ there exists
$\mathcal{S},\mathcal{A}$ with $|\mathcal{S}|=6,|\mathcal{A}|=2$ and
$P\in\mathcal{P}_{7},R\in\mathcal{R}_{3}$ such that:

  1. (1)

The Stat-MFG $(\mathcal{S},\mathcal{A},P,R,\gamma)$ has a _unique_ NE
$\mu^{*},\pi^{*}$,

  2. (2)

For any $N$ and
$\boldsymbol{\pi}_{N}^{*}:=(\pi^{*},\ldots,\pi^{*})\in\Pi^{N}$, it holds that
$J_{P,R}^{\gamma,N,(i)}(\boldsymbol{\pi}_{N}^{*})\leq\max_{\pi}J_{P,R}^{\gamma,N,(i)}(\pi,\boldsymbol{\pi}_{N}^{*,-i})-\Omega(N^{-\log_{2}\gamma^{-1}})$.

###### Proof.

_(sketch)_ The counter-example will be similar to the case in the FH-MFG, with
minor modifications to make the Stat-MFG-NE unique. Intuitively, due to the
same anti-concentration bound as before for $T=\log_{2}\sqrt{N}$, at times
$t=0,2,4,\ldots,T-1$ the population deviation from $\mu^{*}$ can be lower
bounded by
$\operatorname{\mathbb{E}}[\|\widehat{\mu}_{t}-\mu^{*}\|_{1}]\geq\Omega(\frac{2^{t}}{\sqrt{N}})$.
By the design of reward functions, this yields an exploitability of

$\displaystyle\Omega\left(\frac{1+2\gamma^{2}+\ldots+(2\gamma^{2})^{T-1}}{\sqrt{N}}\right)=\Omega\left(N^{-\log_{2}\gamma^{-1}}\right).$

The proof is postponed to the supplementary material. ∎

The result above shows that unless the relevant $\Gamma_{P}$ operator is
contracting in some potential, in general, the exploitability of the Stat-MFG-
NE in the $N$-player game might be very large unless the effective horizon
$(1-\gamma)^{-1}$ is small. Hence, in these cases, the mean-field Nash
equilibrium might be uninformative regarding the true NE of the $N$ player
game. In the case of Stat-MFG, our lower bound is even stronger in the sense
that the exploitability no longer decreases with
$\mathcal{O}(\nicefrac{{1}}{{\sqrt{N}}})$ for large $\gamma$. For a
sufficiently long effective horizon $(1-\gamma)^{-1}$ and large enough
Lipschitz constant $L$, the rate in terms of $N$ can be arbitrarily slow.
Furthermore, if we take the ergodic limit $\gamma\rightarrow 1$, we will
observe a non-vanishing exploitability $\Omega(1)$ for _all_ finite $N$.

##  4\. Computational Tractability of MFG

The next fundamental question for mean-field reinforcement learning will be
whether it is always computationally easier than finding an equilibrium of a
$N$-player general sum normal form game. We focus on the computational aspect
of solving mean-field games in this section, and not statistical uncertainty:
we assume we have full knowledge of the MFG dynamics. We will show that unless
additional assumptions are introduced (as typically done in the form of
contractivity or monotonicity), solving MFG can in general be as hard as
finding $N$-player general sum Nash.

We will prove that the problems are PPAD-complete, where PPAD is a class of
computational problems studied in the seminal work by Papadimitriou (1994),
containing the complete problem of finding $N$-player Nash equilibrium in
general sum normal form games and finding the fixed point of continuous maps
Daskalakis et al. (2009); Chen et al. (2009). The class PPAD is conjectured to
contain difficult problems with no polynomial time algorithms Beame et al.
(1995); Goldberg (2011), hence our results can be seen as a proof of
difficulty. Our results are significant since they imply that the MFG problems
studied in literature are in the same complexity class as general-sum
$N$-player normal form games or $N$-player Markov games Daskalakis et al.
(2023). Once again, several computation-intensive aspects of our proofs will
be postponed to the supplementary material.

Due to a technical detail, we will prove the complexity results for a subset
of possible reward and transition probability functions. We formalize this
subset of possible rewards and dynamics as “simple” rewards/dynamics and also
linear rewards, defined below.

######  Definition  (Simple/Linear Dynamics and Rewards).

$R\in\mathcal{R}$ and $P\in\mathcal{P}$ are said to be _simple_ if for any
$s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}$, $P(s^{\prime}|s,a,\mu)$ and
$R(s,a,\mu)$ are functions of $\mu$ that are expressible as finite
combinations of arithmetic operations $+,-,\times,\frac{\cdot}{\cdot}$ and
functions $\max\\{\cdot,\cdot\\},\min\\{\cdot,\cdot\\}$ of coordinates of
$\mu$. They are called _linear_ if $P(s^{\prime}|s,a,\mu)$ and $R(s,a,\mu)$
are linear functions of $\mu$ for all $s,a,s^{\prime}$. The set of simple
rewards and dynamics are denoted by $\mathcal{R}^{\text{Sim}}$ and
$\mathcal{P}^{\text{Sim}}$ respectively, and the set of linear rewards and
transitions are denoted $\mathcal{R}^{\text{Lin}},\mathcal{P}^{\text{Lin}}$
respectively.

A note on simple functions. We define simple functions as above as in general
there is no known efficient encoding of a Lipschitz continuous function as a
sequence of bits. This is significant since a Turing machine accepts a finite
sequence of bits as input. To solve this issue, we prove a slightly stronger
hardness result that even games where $P(s^{\prime}|s,a,\mu),R(s,a,\mu)$ are
Lipschitz functions with strong structure are PPAD-complete. Since we are
proving hardness, other larger classes of $P,R$ including
$\mathcal{P}^{\text{Sim}},\mathcal{R}^{\text{Sim}}$ will have similar
intractability. See also arithmetic circuits with $\max,\min$ gates Daskalakis
and Papadimitriou (2011) for a similar idea.

###  4.1. The Complexity Class PPAD

The PPAD class is defined by the complete problem End-of-The-Line Daskalakis
et al. (2009), whose formal definition we defer to the appendix as it is not
used in our proofs.

######  Definition  (PPAD, PPAD-hard, PPAD-complete).

The class PPAD is defined as all search problems that can be reduced to End-
of-The-Line in polynomial time. If End-of-The-Line can be reduced to a search
problem $\mathcal{S}$ in polynomial time, then $\mathcal{S}$ is called PPAD-
hard. A search problem $\mathcal{S}$ is called PPAD-complete if it is both a
member of PPAD and it is PPAD-hard.

While End-of-the-Line defines the problem class PPAD, it is hard to construct
direct reductions to it. We will instead use two problems that are known to be
PPAD-complete (and hence can be equivalently used to define PPAD): solving
generalized circuits and finding a NE for an $N$-player general sum game.

######  Definition  (Generalized Circuits Rubinstein (2015); Daskalakis et al.
(2023)).

A generalized circuit $\mathcal{C}=(\mathcal{V},\mathcal{G})$ is a finite set
of nodes $\mathcal{V}$ and gates $\mathcal{G}$. Each gate $G\in\mathcal{G}$ is
characterized by the tuple $G(\theta|v_{1},v_{2}|v)$ where
$G\in\\{G_{\leftarrow},G_{\times,+},\mathcal{G}_{<}\\}$,
$\theta\in\mathbb{R}^{\star}$ is a parameter (possibly of length 0),
$v_{1},v_{2}\in V\cup\\{\perp\\}$ are the input nodes (with $\perp$ indicating
an empty input) and $v\in V$ it the output node of the gate. The collection of
gates $\mathcal{G}$ satisfies the property that if
$G_{1}(\theta|v_{1},v_{2}|v),G_{2}(\theta^{\prime}|v^{\prime}_{1},v^{\prime}_{2}|v^{\prime})\in
G$ are distinct gates, then $v\neq v^{\prime}$.

Such circuits define a set of constraints on values assigned to each gate, and
finding such an assignment will be the associated computational problem for
such a circuit desription. We formally define the $\varepsilon$-GCircuit
problem to this end. $\varepsilon$-GCircuit is a standard complete problem for
the class PPAD, and we will work with it for our reductions. We will use the
shorthand notation $x=y\pm\varepsilon$ to indicate that
$x\in[y-\varepsilon,y+\varepsilon]$ for $x,y\in\mathbb{R}$.

######  Definition  ($\varepsilon$-GCircuit Rubinstein (2015)).

Given a generalized circuit $\mathcal{C}=(\mathcal{V},\mathcal{G})$, a
function $p:V\rightarrow[0,1]$ is called an $\varepsilon$-satisfying
assignment if:

  * •

For every gate $G\in\mathcal{G}$ of the form $G_{\leftarrow}(\zeta||v)$ for
$\zeta\in{0,1}$, it holds that $p(v)=\zeta\pm\varepsilon$,

  * •

For every gate $G\in\mathcal{G}$ of the form
$G_{\times,+}(\alpha,\beta|v_{1},v_{2}|v)$ for $\alpha,\beta\in[-1,1]$, it
holds that

$\displaystyle p(v)\in[\max\\{\min\\{0,\alpha p(v_{1})+\beta
p(v_{2})\\}\\}]\pm\varepsilon,$

  * •

For every gate $G\in\mathcal{G}$ of the form $G_{<}(|v_{1},v_{1}|v)$ it holds
that

$\displaystyle p(v)=\begin{cases}&1\pm\varepsilon,\quad p(v_{1})\leq
p(v_{2})-\varepsilon,\\\ &0\pm\varepsilon,\quad p(v_{1})\geq
p(v_{2})+\varepsilon.\end{cases}$

The $\varepsilon$-GCircuit problem is defined as follows:

$\displaystyle\textit{Given generalized circuit }\mathcal{C},\textit{ find an
}\varepsilon\textit{-satisfying assignment of $\mathcal{C}$.}$

$\varepsilon$-GCircuit is one of the prototypical hard instances of PPAD
problems as the result below suggests.

Rubinstein (2015) There exists $\varepsilon>0$ such that
$\varepsilon$-GCircuit is PPAD-complete.

In other words, $\varepsilon$-GCircuit is representative of the most difficult
problem in PPAD which suggests intractability. The $\varepsilon$-GCircuit
computational problem will be used in our proofs by reducing an arbitrary
generalized circuit into solving a particular MFG.

We will also use the general sum 2-player Nash computation problem, which is
the standard problem of finding an approximate Nash equilibrium of a general
sum bimatrix game.

######  Definition  ($2$-Nash).

Given $\varepsilon>0$, $K_{1},K_{2}\in\mathbb{N}_{>0}$, payoff matrices
$A,B\in[0,1]^{K_{1},K_{2}}$, find an approximate Nash equilibrium
$(\sigma_{1},\sigma_{2})\in\Delta_{K_{1}}\times\Delta_{K_{2}}$ such that

$\displaystyle\max_{\sigma\in\Delta_{K_{1}}}\sum_{i\in[K_{1}]}\sum_{j\in[K_{2}]}A_{i,j}\sigma(i)\sigma_{2}(j)-\sum_{i\in[K_{1}]}\sum_{j\in[K_{2}]}A_{i,j}\sigma_{1}(i)\sigma_{2}(j)$
$\displaystyle\leq\varepsilon$
$\displaystyle\max_{\sigma\in\Delta_{K_{2}}}\sum_{i\in[K_{2}]}\sum_{a\in[K_{2}]}B_{i,j}\sigma_{1}(i)\sigma(j)-\sum_{i\in[K_{1}]}\sum_{j\in[K_{2}]}B_{i,j}\sigma_{1}(i)\sigma_{2}(j)$
$\displaystyle\leq\varepsilon$

The following is the well-known result that even the $2$-Nash general sum
problem is PPAD-complete. In fact, any $N$-player general sum normal form game
is PPAD-complete.

Chen et al. (2009) $2$-Nash is PPAD-complete.

###  4.2. Complexity of Stat-MFG

Next, we provide our difficulty results for the Stat-MFG problem. Notably, for
Stat-MFG, the stability subproblem of finding a stable distribution for a
fixed policy $\pi$ itself is PPAD-hard. Even without considering the
optimality conditions, finding a stable distribution in general for a fixed
policy is intractable, unless additional assumptions are introduced (e.g.
$\Gamma_{P}$ is contractive or non-expansive). We define the computational
problem below and state the results.

######  Definition  ($\varepsilon$-StatDist).

Given finite state-action sets $\mathcal{S},\mathcal{A}$, simple dynamics
$P\in\mathcal{P}^{\text{Sim}}$ and policy $\pi$, find
$\mu^{*}\in\Delta_{\mathcal{S}}$ such that
$\|\Gamma_{P}(\mu^{*},\pi)-\mu^{*}\|_{\infty}\leq\frac{\varepsilon}{|\mathcal{S}|}$.

The computational problem as described above is to find an approximate fixed
point of $\Gamma_{P}(\cdot,\pi)$ which corresponds to an approximately stable
distribution of policy $\pi$. We show that $\varepsilon$-StatDist is PPAD-
complete for some fixed constant $\varepsilon$.

[$\varepsilon$-StatDist is PPAD-complete] For some $\varepsilon>0$, the
problem $\varepsilon$-StatDist is PPAD-complete.

###### Proof.

_(sketch)_ The reduction from $\varepsilon$-StatDist to a fixed point problem
(or the Sperner problem Daskalakis et al. (2009)) is straightforward, showing
$\varepsilon$-StatDist is in PPAD. The main challenge of the proof is showing
$\varepsilon$-StatDist is simultaneously PPAD-hard. This is achieved by
showing any $\varepsilon$-GCircuit problem can be reduced to a
$\varepsilon$-StatDist for some $\varepsilon^{\prime}$. For simplicity, we
reduce $\varepsilon$-GCircuit to finding the stable distribution of a
transition kernel $P(s^{\prime}|s,\mu)$. Given a generalized circuit
$\mathcal{C}=(\mathcal{V},\mathcal{G})$, we construct a Stat-MFG that has one
base state $s_{\text{base}}$, one additional state $s_{v}$ for each
$v\in\mathcal{V}$ that is the output of a gate. Let
$\theta:=\frac{1}{8V},B:=\frac{1}{4}$. Also define the function
$u_{\alpha}(x):=\max\\{0,\min\\{\alpha,x\\}\\}$ for any $\alpha\in[0,1]$. We
present the construction and defer the analysis to the appendix: any gate of
the form $G_{\leftarrow}(\zeta||v)$, we will add one state $s_{v}$ such that
$P(s_{\text{base}}|s_{v},\mu)=1$,
$P(s_{v}|s_{\text{base}},\mu)=\frac{\zeta\theta}{\max\\{B,\,\mu(s_{\text{base}})\\}}$.
For any weighted addition gate $G_{\times,+}(\alpha,\beta|v_{1},v_{2}|v)$, we
add a state $s_{v}$ such that $P(s_{\text{base}}|s_{v},\mu)=1$ and
$P(s_{v}|s_{\text{base}},\mu)=\frac{u_{\theta}(\alpha\mu(v_{1})+\beta\mu(v_{2}))}{\max\\{B,\,\mu(s_{\text{base}})\\}}$.
Finally, for each comparison gate $G_{<}(|v_{1},v_{1}|v)$, also add a state
$s_{v}$ and define the transition probabilities:

$\displaystyle P(s_{v}|s_{\text{base}},\mu)$ $\displaystyle=\frac{\theta
p_{\varepsilon/8}(\theta^{-1}\mu(s_{1}),\theta^{-1}\mu(s_{2}))}{\max\\{B,\,\mu(s_{\text{base}})\\}},$
$\displaystyle P(s_{v}|s_{v},\mu)$ $\displaystyle=0,\quad
P(s_{\text{base}}|s_{v},\mu)=1,$

where
$p_{\varepsilon}(x,y):=u_{1}\left(\frac{1}{2}+\varepsilon^{-1}(x-y)\right)$.
Once all gates are added, the construction is completed by defining
$P(s_{\text{base}}|s_{\text{base}},\mu)=1-\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s_{\text{base}},\mu)$.
Simple computation verifies that for any _exact_ stationary distribution
$\mu^{*}$ of the above $P$, an exact assignment the the generalized circuit
can be read by the map $v\rightarrow u_{1}(\frac{\mu^{*}(s_{v})}{\theta})$. ∎

As a corollary, there is no polynomial time algorithm for
$\varepsilon$-StatDist unless PPAD=P, which is conjectured to be not the case.

###### Corollary

There exists a $\varepsilon>0$ such that there exists no polynomial time
algorithm for $\varepsilon$-StatDist, unless P = PPAD.

Most notably, these results show that the stable distribution oracle of Cui
and Koeppl (2021) might be intractable to compute in general, and the shared
assumption that $\Gamma_{P}(\cdot,\pi)$ is contractive in some norm found in
many works Xie et al. (2021); Anahtarci et al. (2022); Yardim et al. (2023b)
might not be trivial to remove without sacrificing tractability.

###  4.3. Complexity of FH-MFG

We will show that finding an $\varepsilon$ solution to the finite horizon
problem is also PPAD-complete, in particular even if we restrict our attention
to the case when $H=2$ and the transition probabilities $P$ do not depend on
$\mu$. We formalize the structured computational FH-MFG problem.

######  Definition  ($(\varepsilon,H)$-FH-Nash).

Given simple reward function $R\in\mathcal{R}^{\text{Sim}}$, transition matrix
$P(s^{\prime}|s,a)$, and initial distribution
$\mu_{0}\in\Delta_{\mathcal{S}}$, find a time dependent policy
$\\{\pi_{h}\\}_{h=0}^{H-1}$ such that
$\mathcal{E}_{P,R}^{H}(\\{\pi_{h}\\}_{h=0}^{H-1})\leq\nicefrac{{\varepsilon}}{{|\mathcal{S}|}}$.

Our result in the case of the finite horizon MFG problem is that even in the
case of $H=2$, the problem is PPAD-complete.

[$(\varepsilon,2)$-FH-Nash is PPAD-complete] There exists an $\varepsilon>0$
such that the problem $(\varepsilon,2)$-FH-Nash is PPAD-complete.

###### Proof.

_(sketch)_ Once again, showing $(\varepsilon,2)$-FH-Nash is in PPAD is simple:
it follows from the fact that a FH-MFG-NE is a fixed point of an easy-to-
compute function (see e.g. Huang et al. (2023)). To show that
$(\varepsilon,2)$-FH-Nash is also PPAD-hard, for an arbitrary generalized
circuit $\mathcal{C}=(\mathcal{V},\mathcal{G})$ we construct a FH-MFG whose
$\delta$-NE will be $\delta^{\prime}$-satisfying assignments for $\mathcal{C}$
for some $\delta$’. ∎

###### Corollary

There exists a $\varepsilon>0$ such that there exists no polynomial time
algorithm for $(\varepsilon,2)$-FH-Nash, unless P= PPAD.

These results for the FH-MFG show that the (weak) monotonicity assumption
present in works such as Perrin et al. (2020); Pérolat et al. (2022) might
also be necessary, as in the absence of any structural assumptions the
problems are provably difficult.

Finally, we also show that even if $R(s,a,\mu)$ is a linear function of $\mu$
for all $s,a$ (that is, $R\in\mathcal{R}^{\text{Lin}}$), the intractability
holds, although not for fixed $\varepsilon$. We define the linear
computational problem below.

######  Definition  ($H$-FH-Linear).

Given $\varepsilon>0$, linear reward function $R\in\mathcal{R}^{\text{Lin}}$,
transition matrix $P(s^{\prime}|s,a)$, find a time dependent policy
$\\{\pi_{h}\\}_{h=0}^{H-1}$ such that
$\mathcal{E}_{P,R}^{H}(\\{\pi_{h}\\}_{h=0}^{H-1})\leq\varepsilon.$

[$2$-FH-Linear is PPAD-complete] The problem $2$-FH-Linear is PPAD-complete.

###### Proof.

_(sketch)_ In this case, we provide a reduction from $2$-Nash. For a given
$2$-Nash instance $K_{1},K_{2}\in\mathbb{N}_{>0}$ with payoff matrices
$A,B\in[0,1]^{K_{1},K_{2}}$, we construct an FH-MFG with one initial state for
each player and one additional state for each strategy of each of the players,
resulting in a FH-MFG with $K_{1}+K_{2}+2$ states,
$\mathcal{S}:=\\{s_{\text{base}}^{1},s_{\text{base}}^{2},s^{1}_{1},\ldots,s^{1}_{K_{1}},s^{2}_{1},\ldots,s^{2}_{K_{2}}\\}$.
We set
$\mu_{0}(s_{\text{base}}^{1})=\mu_{0}(s_{\text{base}}^{2})=\nicefrac{{1}}{{2}}$.
The action set will consist of $\max\\{K_{1},K_{2}\\}$ actions. In the first
round, an agent starting from $s_{\text{base}}^{1}$ will be transitioned to
one of states $s^{1}_{1},\ldots,s^{1}_{K_{1}}$ depending on the action picked
receiving zero reward, and likewise and agent starting from
$s_{\text{base}}^{2}$ will transition to one of states
$s^{2}_{1},\ldots,s^{2}_{K_{2}}$. In the second round, the agent will receive
a population-dependent reward regardless of the action player, which is equal
to the expected utility of an action (a linear function). We postpone the
cumbersome details relating to error analysis and dealing with the case
$K_{1}\neq K_{2}$ to the appendix. ∎

We emphasize that for $2$-FH-Linear the accuracy $\varepsilon$ is also an
input of the problem: hence the existence of a pseudo-polynomial time
algorithm is not ruled out.

##  5\. Discussion and Conclusion

We provided novel results on when mean-field RL is relevant for real-world
applications and when it is tractable from a computational perspective. Our
results differ from existing work by provably characterizing cases where MFGs
might have practical shortcomings. From the approximation perspective, we show
clear conditions and lower bounds on when the MFGs efficiently approximate
real-world games. Computationally, we show that even simple MFGs can be as
hard as solving $N$-player general sum games.

We emphasize that our results do not discard MFGs, but rather identify
potential bottlenecks (and conditions to overcome these) when using mean-field
RL to compute a good approximate NE.

This project is supported by Swiss National Science Foundation (SNSF) under
the framework of NCCR Automation and SNSF Starting Grant. A.Goldman was
supported by the ETH Student Summer Research Fellowship.

## References

  * (1)
  * Anahtarci et al. (2022) Berkay Anahtarci, Can Deha Kariksiz, and Naci Saldi. 2022\.  Q-learning in regularized mean-field games.  _Dynamic Games and Applications_ (2022), 1–29.
  * Beame et al. (1995) Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. 1995.  The relative complexity of NP search problems. In _Proceedings of the twenty-seventh annual ACM symposium on Theory of computing_. Las Vegas, Nevada, USA, 303–314.
  * Carmona and Delarue (2013) René Carmona and François Delarue. 2013.  Probabilistic analysis of mean-field games.  _SIAM Journal on Control and Optimization_ 51, 4 (2013), 2705–2734.
  * Carmona et al. (2018) René Carmona, François Delarue, et al. 2018\.  _Probabilistic theory of mean field games with applications I-II_.  Springer.
  * Chen et al. (2009) Xi Chen, Xiaotie Deng, and Shang-Hua Teng. 2009.  Settling the complexity of computing two-player Nash equilibria.  _Journal of the ACM (JACM)_ 56, 3 (2009), 1–57.
  * Cui and Koeppl (2021) Kai Cui and Heinz Koeppl. 2021.  Approximately solving mean field games via entropy-regularized deep reinforcement learning. In _International Conference on Artificial Intelligence and Statistics_. PMLR, 1909–1917.
  * Daskalakis et al. (2009) Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. 2009.  The complexity of computing a Nash equilibrium.  _Commun. ACM_ 52, 2 (2009), 89–97.
  * Daskalakis et al. (2023) Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. 2023\.  The complexity of markov equilibrium in stochastic games. In _The Thirty Sixth Annual Conference on Learning Theory_. PMLR, 4180–4234.
  * Daskalakis and Papadimitriou (2011) Constantinos Daskalakis and Christos Papadimitriou. 2011.  Continuous local search. In _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_. SIAM, 790–804.
  * Geist et al. (2022) Matthieu Geist, Julien Pérolat, Mathieu Laurière, Romuald Elie, Sarah Perrin, Oliver Bachem, Rémi Munos, and Olivier Pietquin. 2022.  Concave Utility Reinforcement Learning: The Mean-field Game Viewpoint. In _Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems_ (Virtual Event, New Zealand) _(AAMAS ’22)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 489–497.
  * Goldberg (2011) Paul W Goldberg. 2011\.  A survey of PPAD-completeness for computing Nash equilibria.  _arXiv preprint arXiv:1103.2709_ (2011).
  * Guo et al. (2019) Xin Guo, Anran Hu, Renyuan Xu, and Junzi Zhang. 2019\.  Learning mean-field games.  _Advances in Neural Information Processing Systems_ 32 (2019).
  * Guo et al. (2022b) Xin Guo, Anran Hu, Renyuan Xu, and Junzi Zhang. 2022b.  A general framework for learning mean-field games.  _Mathematics of Operations Research_ (2022).
  * Guo et al. (2022a) Xin Guo, Anran Hu, and Junzi Zhang. 2022a.  MF-OMO: An optimization formulation of mean-field games.  _arXiv preprint arXiv:2206.09608_ (2022).
  * Huang et al. (2023) Jiawei Huang, Batuhan Yardim, and Niao He. 2023.  On the Statistical Efficiency of Mean Field Reinforcement Learning with General Function Approximation.  _arXiv preprint arXiv:2305.11283_ (2023).
  * Huang et al. (2006) Minyi Huang, Roland P Malhamé, and Peter E Caines. 2006\.  Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle.  _Communications in Information & Systems_ 6, 3 (2006), 221–252.
  * Iyer et al. (2014) Krishnamurthy Iyer, Ramesh Johari, and Mukund Sundararajan. 2014\.  Mean field equilibria of dynamic auctions with learning.  _Management Science_ 60, 12 (2014), 2949–2970.
  * Kaas and Buhrman (1980) Rob Kaas and Jan M Buhrman. 1980.  Mean, median and mode in binomial distributions.  _Statistica Neerlandica_ 34, 1 (1980), 13–18.
  * Lasry and Lions (2007) Jean-Michel Lasry and Pierre-Louis Lions. 2007.  Mean field games.  _Japanese journal of mathematics_ 2, 1 (2007), 229–260.
  * Laurière et al. (2022) Mathieu Laurière, Sarah Perrin, Sertan Girgin, Paul Muller, Ayush Jain, Théophile Cabannes, Georgios Piliouras, Julien P’erolat, Romuald Elie, Olivier Pietquin, and Matthieu Geist. 2022.  Scalable Deep Reinforcement Learning Algorithms for Mean Field Games. In _International Conference on Machine Learning_.
  * Mao et al. (2022) Weichao Mao, Haoran Qiu, Chen Wang, Hubertus Franke, Zbigniew Kalbarczyk, Ravi Iyer, and Tamer Basar. 2022.  A Mean-Field Game Approach to Cloud Resource Management with Function Approximation. In _Advances in Neural Information Processing Systems_.
  * Matignon et al. (2007) Laëtitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. 2007.  Hysteretic q-learning: an algorithm for decentralized reinforcement learning in cooperative multi-agent teams. In _2007 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 64–69.
  * McDiarmid et al. (1989) Colin McDiarmid et al. 1989\.  On the method of bounded differences.  _Surveys in combinatorics_ 141, 1 (1989), 148–188.
  * Papadimitriou (1994) Christos H Papadimitriou. 1994\.  On the complexity of the parity argument and other inefficient proofs of existence.  _Journal of Computer and system Sciences_ 48, 3 (1994), 498–532.
  * Pérolat et al. (2022) Julien Pérolat, Sarah Perrin, Romuald Elie, Mathieu Laurière, Georgios Piliouras, Matthieu Geist, Karl Tuyls, and Olivier Pietquin. 2022.  Scaling Mean Field Games by Online Mirror Descent. In _Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems_. 1028–1037.
  * Perolat et al. (2015) Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. 2015.  Approximate dynamic programming for two-player zero-sum markov games. In _International Conference on Machine Learning_. PMLR, 1321–1329.
  * Perrin et al. (2020) Sarah Perrin, Julien Pérolat, Mathieu Laurière, Matthieu Geist, Romuald Elie, and Olivier Pietquin. 2020.  Fictitious play for mean field games: Continuous time analysis and applications.  _Advances in Neural Information Processing Systems_ 33 (2020), 13199–13213.
  * Rashedi et al. (2016) Navid Rashedi, Mohammad Amin Tajeddini, and Hamed Kebriaei. 2016.  Markov game approach for multi-agent competitive bidding strategies in electricity market.  _IET Generation, Transmission & Distribution_ 10, 15 (2016), 3756–3763.
  * Rubinstein (2015) Aviad Rubinstein. 2015\.  Inapproximability of Nash equilibrium. In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_. 409–418.
  * Saldi et al. (2018) Naci Saldi, Tamer Basar, and Maxim Raginsky. 2018.  Markov–Nash equilibria in mean-field games with discounted cost.  _SIAM Journal on Control and Optimization_ 56, 6 (2018), 4256–4287.
  * Samvelyan et al. (2019) Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philip H. S. Torr, Jakob Foerster, and Shimon Whiteson. 2019.  The StarCraft Multi-Agent Challenge. In _Proc. of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019)_ (Montreal QC, Canada) _(AAMAS ’19)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2186–2188.
  * Shavandi and Khedmati (2022) Ali Shavandi and Majid Khedmati. 2022.  A multi-agent deep reinforcement learning framework for algorithmic trading in financial markets.  _Expert Systems with Applications_ 208 (2022), 118124.
  * Wang et al. (2020) Lingxiao Wang, Zhuoran Yang, and Zhaoran Wang. 2020\.  Breaking the curse of many agents: Provable mean embedding Q-iteration for mean-field reinforcement learning. In _International conference on machine learning_. PMLR, 10092–10103.
  * Wiering (2000) Marco A. Wiering. 2000\.  Multi-agent reinforcement learning for traffic light control. In _Machine Learning: Proceedings of the Seventeenth International Conference (ICML’2000)_. 1151–1158.
  * Xie et al. (2021) Qiaomin Xie, Zhuoran Yang, Zhaoran Wang, and Andreea Minca. 2021.  Learning while playing in mean-field games: Convergence and optimality. In _International Conference on Machine Learning_. PMLR, 11436–11447.
  * Yardim et al. (2023b) Batuhan Yardim, Semih Cayci, Matthieu Geist, and Niao He. 2023b.  Policy mirror ascent for efficient and independent learning in mean field games. In _International Conference on Machine Learning_. PMLR, 39722–39754.
  * Yardim et al. (2023a) Batuhan Yardim, Semih Cayci, and Niao He. 2023a.  Stateless Mean-Field Games: A Framework for Independent Learning with Large Populations. In _Sixteenth European Workshop on Reinforcement Learning_.
  * Zaman et al. (2023) Muhammad Aneeq Uz Zaman, Alec Koppel, Sujay Bhatt, and Tamer Basar. 2023.  Oracle-free reinforcement learning in mean-field games along a single sample path. In _International Conference on Artificial Intelligence and Statistics_. PMLR, 10178–10206.

##  Appendix A MFG Approximation Results

###  A.1. Preliminaries

To establish explicit upper bounds on the approximation rate, we will use
standard concentration tools.

######  Definition  (Sub-Gaussian).

Random variable $\xi$ is called sub-Gaussian with variance proxy $\sigma^{2}$
if
$\forall\lambda\in\mathbb{R}:\quad\mathbb{E}\left[e^{\lambda(\xi-\mathbb{E}\left[\xi\right])}\right]\leq
e^{\frac{\lambda^{2}\sigma^{2}}{2}}$. In this case, we write $\xi\in
SG(\sigma^{2})$.

It is easy to show that if $\xi\in SG(\sigma^{2})$, then $\alpha\xi\in
SG(\alpha^{2}\sigma^{2})$ for any constant $\alpha\in\mathbb{R}$. Furthermore,
if $\xi_{1},\dots,\xi_{n}$ are independent random variables with $\xi_{i}\in
SG(\sigma_{i}^{2})$, then $\sum_{i}\xi_{i}\in SG(\sum_{i}\sigma_{i}^{2})$.
Finally, if $\xi$ is almost surely bounded in $[a,b]$, then $\xi_{i}\in
SG(\nicefrac{{(b-a)^{2}}}{{4}})$. We also state the well-known Hoeffding
concentration bound and a corollary, Lemma A.1.

######  Lemma  (Hoeffding inequality McDiarmid et al. (1989))

Let $\xi\in SG(\sigma^{2})$. Then for any $t>0$ it holds that
$\mathbb{P}\left(|\xi-\mathbb{E}\left[\xi\right]|\geq t\right)\leq
2e^{-\frac{t^{2}}{2\sigma^{2}}}$.

###### Lemma

Let $\xi\in SG(\sigma^{2})$. Then

$\displaystyle\mathbb{E}\left[|\xi-\mathbb{E}\left[\xi\right]|\right]\leq\sqrt{2\pi\sigma^{2}},\quad\mathbb{E}\left[(\xi-\mathbb{E}\left[\xi\right])^{2}\right]\leq
4\sigma^{2}$

###### Proof.

$\displaystyle\mathbb{E}\left[|\xi-\mathbb{E}\left[\xi\right]|\right]$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}(|\xi-\mathbb{E}\left[\xi\right]|\geq
t)dt$
$\displaystyle\stackrel{{\scriptstyle(I)}}{{\leq}}2\int_{0}^{\infty}e^{-\frac{t^{2}}{2\sigma^{2}}}dt=\sqrt{2\pi\sigma^{2}}$

Inequality $(I)$ is true due to Section A.1. Likewise,

$\displaystyle\mathbb{E}\left[(\xi-\mathbb{E}\left[\xi\right])^{2}\right]$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}((\xi-\mathbb{E}\left[\xi\right])^{2}\geq
t)dt$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}(|\xi-\mathbb{E}\left[\xi\right]|\geq\sqrt{h})dt$
$\displaystyle\stackrel{{\scriptstyle(II)}}{{\leq}}2\int_{0}^{\infty}e^{-\frac{h}{2\sigma^{2}}}dt=4\sigma^{2}$

∎

Establishing lower bounds for the mean-field approximation of the $N$-player
game will be more challenging as it will require different tools. To establish
lower bounds, we will need to use the following anti-concentration result for
the binomial distribution.

######  Lemma  (Anti-concentration for binomial)

Let $N\in\mathbb{N}_{>0}$ and $X\sim\operatorname{Binom}(N,p)$ be drawn from a
binomial distribution for some $p\in[\nicefrac{{1}}{{2}},1]$. Then,
$\operatorname{\mathbb{P}}\left[X\geq\frac{N}{2}+\frac{\sqrt{N}}{2}\right]\geq\frac{1}{20}.$

###### Proof.

For $k_{0}:=\left\lceil\frac{N}{2}+\frac{\sqrt{N}}{2}\right\rceil$, we will
lower bound $\sum_{k=k_{0}}^{N}\binom{N}{k}p^{k}(1-p)^{N-k}$ when $N$ is large
enough. If $k_{0}<\lceil Np\rceil$, then the probability in the statement
above is bounded below trivially by $\nicefrac{{1}}{{2}}$ since $\lfloor
Np\rfloor$ lower bounds the median of the binomial Kaas and Buhrman (1980).
Otherwise, if $k_{0}\geq\lceil Np\rceil$, then the function
$\widebar{p}\rightarrow\widebar{p}^{k}(1-\widebar{p})^{N-k}$ is increasing in
$\widebar{p}$ in the interval $[0,p]$. As $\nicefrac{{1}}{{2}}\in[0,p]$, it is
then sufficient to assume $p=\nicefrac{{1}}{{2}}$, and to upper bound
$\operatorname{\mathbb{P}}\left[\frac{N}{2}-\frac{\sqrt{N}}{2}<X<\frac{N}{2}+\frac{\sqrt{N}}{2}\right]$
by $\nicefrac{{9}}{{10}}$ as the binomial probability mass is symmetric around
$\frac{N}{2}$ when $p=\nicefrac{{1}}{{2}}$.

First assuming $N$ is even, we obtain by monotonicity
$\binom{N}{k}\leq\binom{N}{\nicefrac{{N}}{{2}}}$. Using the Stirling bound
$\sqrt{2\pi}k^{k+\frac{1}{2}}\mathrm{e}^{-k}\leq
k!\leq\mathrm{e}k^{k+\frac{1}{2}}\mathrm{e}^{-k}$, we further upper bound
$\binom{N}{\nicefrac{{N}}{{2}}}\leq\frac{e}{\pi}\frac{2^{N}}{\sqrt{N}}$,
resulting in the bound
$\operatorname{\mathbb{P}}\left[\frac{N}{2}-\frac{\sqrt{N}}{2}<X<\frac{N}{2}+\frac{\sqrt{N}}{2}\right]\leq
2^{-N}\sqrt{N}\binom{N}{\nicefrac{{N}}{{2}}}\leq\frac{e}{\pi}\leq\nicefrac{{9}}{{10}}$,
since there are at most $\sqrt{N}$ binomial coefficients being summed.
Finally, assume $N=2m+1$ is odd, then by the binomial formula
$\binom{2m+1}{m+1}=\binom{2m}{m+1}+\binom{2m}{m}\leq
2\binom{2m}{m}\leq\frac{2e}{\pi}\frac{2^{2m}}{\sqrt{2m}}$. Hence we have the
bound on the sum
$\operatorname{\mathbb{P}}\left[\frac{N}{2}-\frac{\sqrt{N}}{2}<X<\frac{N}{2}+\frac{\sqrt{N}}{2}\right]\leq\frac{e\sqrt{N}}{\pi}\frac{1}{\sqrt{N-1}}$.
It is easy to verify that for $N\geq 16$,
$\frac{e\sqrt{N}}{\pi\sqrt{N-1}}\leq\nicefrac{{9}}{{10}}$, and the case when
$N<16$ and $N$ is odd follows by manual computation. ∎

Finally, we prove slightly more general upper bounds than presented in the
main text that approximates the exploitability of an _approximate_ MFG-NE in a
finite population setting. Hence we define the following notions approximate
FH-MFG and Stat-MFG.

######  Definition  ($\delta$-FH-MFG-NE).

Let $(\mathcal{S},\mathcal{A},H,P,R,\mu_{0})$ be a FH-MFG. Then, a
$\delta$-FH-MFG Nash equilibrium is defined as:

Policy
$\displaystyle\boldsymbol{\pi}_{\delta}^{*}=\\{\pi^{*}_{\delta,h}\\}_{h=0}^{H-1}\in\Pi_{H}\text{
such that }$
$\displaystyle\mathcal{E}_{P,R}^{H}(\\{\pi^{*}_{\delta,h}\\}_{h=0}^{H-1})\leq\delta.$
($\delta$-FH-MFG-NE)

######  Definition  ($\delta$-Stat-MFG-NE).

Let $(\mathcal{S},\mathcal{A},P,R,\gamma)$ be a Stat-MFG. A policy-population
pair $(\mu_{\delta}^{*},\pi_{\delta}^{*})\in\Delta_{\mathcal{S}}\times\Pi$ is
called a $\delta$-Stat-MFG Nash equilibrium if the two conditions hold:

Stability:
$\displaystyle\mu_{\delta}^{*}=\Gamma_{P}(\mu_{\delta}^{*},\pi_{\delta}^{*}),$
Optimality: $\displaystyle
V^{\gamma}_{P,R}(\mu_{\delta}^{*},\pi_{\delta}^{*})\geq\max_{\pi\in\Pi}V^{\gamma}_{P,R}(\mu_{\delta}^{*},\pi)-\delta.$
($\delta$-Stat-MFG-NE)

###  A.2. Upper Bound for FH-MFG: Extended Proof of Theorem 3.1

Throughout this section we work with fixed $P\in\mathcal{P}_{K_{\mu}}$ and
$R\in\mathcal{R}_{L_{\mu}}$. For any $\mathcal{X}$ valued random variable $x$
denote $\mathcal{L}(x)(\cdot)\in\Delta_{\mathcal{X}}$ as the distribution of
$x$. We start by introducing some notation.

For given $R$ and $P$ define the following constants:

$\displaystyle L_{s}$
$\displaystyle:=\sup_{s,s^{\prime},a,\mu}\left|R(s,a,\mu)-R(s^{\prime},a,\mu)\right|,$
$\displaystyle\la$
$\displaystyle:=\sup_{s,a,a^{\prime},\mu}\left|R(s,a,\mu)-R(s,a^{\prime},\mu)\right|,$
$\displaystyle K_{s}$
$\displaystyle:=\sup_{s,s^{\prime},a,\mu}\left\|P(\cdot|s,a,\mu)-P(\cdot|s^{\prime},a,\mu)\right\|,$
$\displaystyle K_{a}$
$\displaystyle:=\sup_{s,a,a^{\prime},\mu}\left\|P(\cdot|s,a,\mu)-P(\cdot|s,a^{\prime},\mu)\right\|.$

$R$ and $P$ are bounded due to Section 2, thus all constants
$K_{a},K_{s},\la,L_{s}$ are finite and well-defined, and it always holds that
$K_{s},K_{a}\leq 2$ and $L_{s},\la\leq 1$. With the above definition of
constants, the more general Lipschitz condition holds: $\forall\
s,s^{\prime}\in\mathcal{S}$, $a,a^{\prime}\in\mathcal{A}$,
$\mu,\mu^{\prime}\in\Delta_{\mathcal{S}}$

$\displaystyle\|P(\cdot|s,a,\mu)-P(\cdot|s^{\prime},a^{\prime},\mu^{\prime})\|_{1}\leq$
$\displaystyle K_{\mu}\|\mu-\mu^{\prime}\|_{1}+K_{s}d(s,s^{\prime})$
$\displaystyle+K_{a}d(a,a^{\prime}),$
$\displaystyle|R(s,a,\mu)-R(s^{\prime},a^{\prime},\mu^{\prime})|\leq$
$\displaystyle L_{\mu}\|\mu-\mu^{\prime}\|_{1}+L_{s}d(s,s^{\prime})$
$\displaystyle+\la d(a,a^{\prime}).$

We also introduce the shorthand notation for any
$s\in\mathcal{S},u\in\Delta_{\mathcal{A}},\mu\in\Delta_{\mathcal{S}}$:

$\displaystyle\overline{P}(\cdot|s,u,\mu)$
$\displaystyle:=\sum_{a\in\mathcal{A}}u(a)P(\cdot|s,a,\mu),$
$\displaystyle\overline{R}(s,u,\mu)$
$\displaystyle:=\sum_{a\in\mathcal{A}}u(a)R(s,a,\mu).$

By (Yardim et al., 2023b, Lemma C.1), it holds that

$\displaystyle\|\overline{P}(\cdot|s,u,\mu)-\overline{P}(\cdot|s^{\prime},u^{\prime},\mu^{\prime})\|_{1}\leq$
$\displaystyle K_{\mu}\|\mu-\mu^{\prime}\|_{1}+K_{s}d(s,s^{\prime})$
$\displaystyle+\frac{K_{a}}{2}\|u-u^{\prime}\|_{1},$
$\displaystyle|\overline{R}(s,u,\mu)-\overline{R}(s^{\prime},u^{\prime},\mu^{\prime})|\leq$
$\displaystyle L_{\mu}\|\mu-\mu^{\prime}\|_{1}+L_{s}d(s,s^{\prime})$
$\displaystyle+\frac{\la}{2}\|u-u^{\prime}\|_{1}.$ (1)

We will define a new operator for tracking the evolution of the population
distribution over finite time horizons for a time-varying policy
$\forall\boldsymbol{\pi}=\\{\pi_{h}\\}_{h=0}^{H-1}\in\Pi_{H}$:

$\displaystyle\mathbf{\Gamma}_{P}^{h}(\mu,\boldsymbol{\pi})$
$\displaystyle:=\underbrace{\Gamma_{P}(\dots\Gamma_{P}(\Gamma_{P}(\mu,\pi_{0}),\pi_{1})\dots,\pi_{h-1})}_{h\text{
times}}$
$\displaystyle=\mu_{h}^{\boldsymbol{\pi}}=\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi})_{h},$

so $\mathbf{\Gamma}_{P}^{0}(\mu,\boldsymbol{\pi})=\mu_{0}$. By repeated
applications of Lemma 2, we obtain the Lipschitz condition:

$\displaystyle\|$
$\displaystyle\mathbf{\Gamma}_{P}^{n}(\mu,\\{\pi_{i}\\}_{i=0}^{n-1})-\mathbf{\Gamma}_{P}^{n}(\mu^{\prime},\\{\pi_{i}^{\prime}\\}_{i=0}^{n-1})\|_{1}$
$\displaystyle\leq
L_{pop,\mu}\|\mathbf{\Gamma}_{P}^{n-1}(\mu,\\{\pi_{i}\\}_{i=0}^{n-2})-\mathbf{\Gamma}_{P}^{n-1}(\mu^{\prime},\\{\pi_{i}^{\prime}\\}_{i=0}^{n-2})\|_{1}$
$\displaystyle+\frac{K_{a}}{2}\|\pi_{n-1}-\pi_{n-1}^{\prime}\|_{1}$
$\displaystyle\leq
L_{pop,\mu}^{n}\|\mu-\mu^{\prime}\|_{1}+\frac{K_{a}}{2}\sum_{i=0}^{n-1}L_{pop,\mu}^{n-1-i}\|\pi_{i}-\pi_{i}^{\prime}\|_{1},$
(2)

where $L_{pop,\mu}=(K_{\mu}+\frac{K_{s}}{2}+\frac{K_{a}}{2})$.

The proof will proceed in three steps:

  * •

Step 1. Bounding the expected deviation of the empirical population
distribution from the mean-field distribution
$\mathbb{E}\left[\|\widehat{\mu}_{h}-\mu_{h}^{\boldsymbol{\pi}}\|_{1}\right]$
for any given policy $\boldsymbol{\pi}$.

  * •

Step 2.  Bounding difference of $N$ agent value function $J_{P,R}^{H,N,(i)}$
and the infinite player value function $V_{P,R}^{H}$.

  * •

Step 3.  Bounding the exploitability of an agent when each of $N$ agents are
playing the FH-MFG-NE policy.

Step 1: Empirical distribution bound. Due to its relevance for a general
connection between the FH-MFG and the $N$-player game, we state this result in
the form of an explicit bound.

###### Lemma

Suppose for the $N$-FH-MFG $(N,\mathcal{S},\mathcal{A},N,P,R,\gamma)$, agents
$i=1,\ldots,N$ follow policies $\boldsymbol{\pi}^{i}=\\{\pi_{h}^{i}\\}_{h}$.
Let $\widebar{\boldsymbol{\pi}}=\\{\widebar{\pi}_{h}\\}_{h}\in\Pi^{H}$ be
arbitrary and
$\bm{\mu}^{\widebar{\boldsymbol{\pi}}}:=\\{\mu_{h}^{\widebar{\boldsymbol{\pi}}}\\}_{h=0}^{H-1}=\Lambda^{H}_{P}(\mu_{0},\widebar{\boldsymbol{\pi}})$.
Then for all $h\in\\{0,\ldots,H-1\\}$, it holds that:

$\displaystyle\mathbb{E}\left[\|\widehat{\mu}_{h}-\mu_{h}^{\widebar{\boldsymbol{\pi}}}\|_{1}\right]\leq\frac{1-L_{pop,\mu}^{h+1}}{1-L_{pop,\mu}}|\mathcal{S}|\sqrt{\frac{\pi}{2N}}+\frac{K_{a}}{2N}\sum_{i=0}^{h-1}L_{pop,\mu}^{h-i-1}\Delta_{\pi_{i}},$

where $\Delta_{h}:=\frac{1}{N}\sum_{i}\|\widebar{\pi}_{h}-\pi_{h}^{i}\|_{1}$

###### Proof.

The proof will proceed inductively over $h$. First, for time $h=0$, we have

$\displaystyle\mathbb{E}\left[\|\widehat{\mu}_{0}-\mu_{0}\|_{1}\right]=\sum_{s\in\mathcal{S}}\mathbb{E}\left[\left|\frac{1}{N}\sum_{i=1}^{N}(\mathbbm{1}_{\\{s_{0}^{i}=s\\}}-\mu_{0}(s))\right|\right]\leq|\mathcal{S}|\sqrt{\frac{\pi}{2N}},$

where the last line is due to Section A.1 and the fact that
$\mathbbm{1}_{\\{s_{0}^{i}=s\\}}$ are bounded (hence subgaussian) random
variables, and that in the finite state space we have
$\mathbb{E}\left[\mathbbm{1}_{\\{s_{0}^{i}=s\\}}\right]=\mu_{0}(s)$.

Next, denoting the $\sigma$-algebra induced by the random variables
$(\\{s^{i}_{h}\\})_{i,h^{\prime}\leq h}$ as $\mathcal{F}_{h}$, we have that:

$\displaystyle\mathbb{E}\left[\|\widehat{\mu}_{h+1}-\mu_{h+1}^{\widebar{\boldsymbol{\pi}}}\|_{1}\left|\mathcal{F}_{h}\right.\right]$
$\displaystyle\leq$
$\displaystyle\underbrace{\mathbb{E}\left[\|\mathbb{E}\left[\widehat{\mu}_{h+1}\left|\mathcal{F}_{h}\right.\right]-\Gamma_{P}(\widehat{\mu}_{h},\widebar{\pi}_{h})\|_{1}\left|\mathcal{F}_{h}\right.\right]}_{(\square)}$
$\displaystyle+\underbrace{\mathbb{E}\left[\|\widehat{\mu}_{h+1}-\mathbb{E}\left[\widehat{\mu}_{h+1}\left|\mathcal{F}_{h}\right.\right]\|_{1}\left|\mathcal{F}_{h}\right.\right]}_{(\triangle)}+\underbrace{\mathbb{E}\left[\|\Gamma_{P}(\widehat{\mu}_{h},\widebar{\pi}_{h})-\mu_{h+1}^{\widebar{\boldsymbol{\pi}}}\|_{1}\left|\mathcal{F}_{h}\right.\right]}_{(\heartsuit)}$
(3)

We upper bound the three terms separately. For $(\triangle)$, it holds that

$\displaystyle(\triangle)=$
$\displaystyle\mathbb{E}\left[\|\widehat{\mu}_{h+1}-\mathbb{E}\left[\widehat{\mu}_{h+1}\left|\mathcal{F}_{h}\right.\right]\|_{1}\left|\mathcal{F}_{h}\right.\right]$
$\displaystyle=$
$\displaystyle\sum_{s\in\mathcal{S}}\mathbb{E}\left[|\widehat{\mu}_{h+1}(s)-\mathbb{E}\left[\widehat{\mu}_{h+1}(s)\left|\mathcal{F}_{h}\right.\right]|\left|\mathcal{F}_{h}\right.\right]\leq|\mathcal{S}|\sqrt{\frac{\pi}{2N}},$

since each $\widehat{\mu}_{h+1}(s)$ is an average of independent subgaussian
random variables given $\mathcal{F}_{h}$. Specifically, each indicator is
bounded $\mathbbm{1}_{\\{s^{i}_{h+1}=s\\}}\in[0,1]$ a.s. and therefore is sub-
Gaussian with $\mathbbm{1}_{\\{s^{i}_{h+1}=s\\}}\in SG(1/4)$. Thus we get
$\widehat{\mu}_{h+1}(s)\in SG(1/(4N))$ and apply bound on expected value
discussed in Section A.1.

Next, for
$(\square)=\|\mathbb{E}\left[\widehat{\mu}_{h+1}\left|\mathcal{F}_{h}\right.\right]-\Gamma_{P}(\widehat{\mu}_{h},\widebar{\pi}_{h})\|_{1}$,
we note that

$\displaystyle\mathbb{E}\left[\widehat{\mu}_{h+1}(s)\left|\mathcal{F}_{h}\right.\right]=\mathbb{E}\left[\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}_{\\{s_{h+1}^{i}=s\\}}\left|\mathcal{F}_{h}\right.\right]=\frac{1}{N}\sum_{i=1}^{N}\overline{P}(s|s_{h}^{i},\pi_{h}^{i}(s_{h}^{i}),\widehat{\mu}_{h}),$

therefore

$\displaystyle(\square)$
$\displaystyle=\left\|\frac{1}{N}\sum_{i=1}^{N}\overline{P}(\cdot|s_{h}^{i},\pi_{h}^{i}(\cdot|s_{h}^{i}),\widehat{\mu}_{h})-\sum_{s^{\prime}}\widehat{\mu}_{h}(s^{\prime})\overline{P}(\cdot|s^{\prime},\pi_{h}(\cdot|s^{\prime}),\widehat{\mu}_{h})\right\|_{1}$
$\displaystyle=\left\|\frac{1}{N}\sum_{i=1}^{N}\left(\overline{P}(\cdot|s_{h}^{i},\pi_{h}^{i}(\cdot|s_{h}^{i}),\widehat{\mu}_{h})-\overline{P}(\cdot|s_{h}^{i},\pi_{h}(\cdot|s_{h}^{i}),\widehat{\mu}_{h})\right)\right\|_{1}$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\|\overline{P}(\cdot|s_{h}^{i},\pi_{h}^{i}(\cdot|s_{h}^{i}),\widehat{\mu}_{h})-\overline{P}(\cdot|s_{h}^{i},\pi_{h}(\cdot|s_{h}^{i}),\widehat{\mu}_{h})\|_{1}$
$\displaystyle\stackrel{{\scriptstyle(I)}}{{\leq}}\frac{K_{a}}{2N}\sum_{i=1}^{N}\|\pi_{h}^{i}(\cdot|s_{h}^{i})-\pi_{h}(\cdot|s_{h}^{i})\|_{1}\leq\frac{K_{a}}{2}\Delta_{h},$

where (I) follows from the Lipschitz property (1). Finally, the last term
$(\heartsuit)$ can be bounded using:

$\displaystyle(\heartsuit)=$
$\displaystyle\mathbb{E}\left[\|\Gamma_{P}(\widehat{\mu}_{h},\widebar{\pi}_{h})-\Gamma_{P}(\mu_{h}^{\widebar{\boldsymbol{\pi}}},\widebar{\pi}_{h})\|_{1}\left|\mathcal{F}_{h}\right.\right]\leq
L_{pop,\mu}\|\widehat{\mu}_{h}-\mu_{h}^{\widebar{\boldsymbol{\pi}}}\|_{1}.$

To conclude, merging the bounds on the three terms in Inequality (3) and
taking the expectations we obtain:

$\displaystyle\mathbb{E}\left[\|\widehat{\mu}_{h+1}-\mu_{h+1}^{\widebar{\boldsymbol{\pi}}}\|_{1}\right]\leq
L_{pop,\mu}\mathbb{E}\left[\|\widehat{\mu}_{h}-\mu_{h}^{\widebar{\boldsymbol{\pi}}}\|_{1}\right]+|\mathcal{S}|\sqrt{\frac{\pi}{2N}}+\frac{K_{a}\Delta_{h}}{2}.$

Induction on $h$ yields the statement of the lemma.

∎

Step 2: Bounding difference of $N$ agent value function. Next, we bound the
difference between the $N$-player expected reward function $J_{P,R}^{H,N,(1)}$
and the infinite player expected reward function $V_{P,R}^{H}$. For ease of
reading, expectations, probabilities, and laws of random variables will be
denoted
$\operatorname{\mathbb{E}}_{\infty},\operatorname{\mathbb{P}}_{\infty},\mathcal{L}_{\infty}$
respectively over the infinite player finite horizon game and
$\operatorname{\mathbb{E}}_{N},\operatorname{\mathbb{P}}_{N},\mathcal{L}_{N}$
respectively over the $N$-player game. We use the regular notation
$\operatorname{\mathbb{E}}[\cdot],\operatorname{\mathbb{P}}[\cdot],\mathcal{L}(\cdot)$
without subscripts if the underlying randomness is clearly defined. We state
the main result of this step in the following lemma.

###### Lemma

Suppose $N$-FH-MFG agents follow the same sequence of policies
$\boldsymbol{\pi}=\\{\pi_{h}\\}_{h=0}^{H-1}$. Then

$\left|J_{P,R}^{H,N,(1)}(\boldsymbol{\pi},\dots,\boldsymbol{\pi})-V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}),\boldsymbol{\pi})\right|\\\
\leq(L_{\mu}+\frac{L_{s}}{2})|\mathcal{S}|\sqrt{\frac{\pi}{2N}}\sum_{h=0}^{H-1}\frac{1-L_{pop,\mu}^{h+1}}{1-L_{pop,\mu}}.$

###### Proof.

Due to symmetry in the $N$ agent game, any permutation
$\sigma:[N]\rightarrow[N]$ of agents does not change their distribution, that
is
$\mathcal{L}_{N}(s_{h}^{1},\dots,s_{h}^{N})=\mathcal{L}_{N}(s_{h}^{\sigma(1)},\dots,s_{h}^{\sigma(N)})$.
We can then conclude that:

$\displaystyle\mathbb{E}_{N}\left[R(s_{h}^{1},a_{h}^{1},\widehat{\mu}_{h})\right]$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}_{N}\left[R(s_{h}^{i},a_{h}^{i},\widehat{\mu}_{h})\right]$
$\displaystyle=\mathbb{E}_{N}\left[\sum_{s\in\mathcal{S}}\widehat{\mu}_{h}(s)\overline{R}(s,\pi_{h}(s),\widehat{\mu}_{h}).\right]$

Therefore, we by definition:

$\displaystyle
J_{P,R}^{H,N,(1)}(\boldsymbol{\pi},\dots,\boldsymbol{\pi})=\mathbb{E}_{N}\left[\sum_{h=0}^{H-1}\sum_{s\in\mathcal{S}}\widehat{\mu}_{h}(s)\overline{R}(s,\pi_{h}(s),\widehat{\mu}_{h})\right].$

Next, in the FH-MFG, under the population distribution
$\\{\mu_{h}\\}_{h=0}^{H-1}=\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi})$ we have
that for all $h\in 0,\ldots,H-1$,

$\displaystyle\operatorname{\mathbb{P}}_{\infty}(s_{0}=\cdot)$
$\displaystyle=\mu_{0},$
$\displaystyle\operatorname{\mathbb{P}}_{\infty}(s_{h+1}=\cdot)$
$\displaystyle=\sum_{s\in\mathcal{S}}\operatorname{\mathbb{P}}_{\infty}(s_{h}=s)\operatorname{\mathbb{P}}_{\infty}(s_{h}=\cdot|s_{h}=s)$
$\displaystyle=\Gamma_{P}(\operatorname{\mathbb{P}}_{\infty}(s_{h}=\cdot),\pi_{h}),$

so by induction $\operatorname{\mathbb{P}}_{\infty}(s_{h}=\cdot)=\mu_{h}$.
Then we can conclude that

$\displaystyle
V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}),\boldsymbol{\pi})$
$\displaystyle=\mathbb{E}_{\infty}\left[\sum_{h=0}^{H-1}R(s_{h},\pi_{h}(s_{h}),\mu_{h})\right]$
$\displaystyle=\sum_{h=0}^{H-1}\sum_{s\in\mathcal{S}}\mu_{h}(s)R(s,\pi_{h}(s),\mu_{h}).$

Merging the two equalities for $J,V$, we have the bound:

$\displaystyle|J_{P,R}^{H,N,(1)}(\boldsymbol{\pi},\dots,\boldsymbol{\pi})-V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}),\boldsymbol{\pi})|$
$\displaystyle=$
$\displaystyle\left|\mathbb{E}_{N}\left[\sum_{h=0}^{H-1}\sum_{s\in\mathcal{S}}\widehat{\mu}_{h}(s)\overline{R}(s,\pi_{h}(s),\widehat{\mu}_{h})\right]-\sum_{h=0}^{H-1}\sum_{s\in\mathcal{S}}\mu_{h}(s)R(s,\pi_{h}(s),\mu_{h})\right|$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{N}\left[\sum_{h=0}^{H-1}\left|\sum_{s\in\mathcal{S}}\left(\widehat{\mu}_{h}(s)\overline{R}(s,\pi_{h}(s),\widehat{\mu}_{h})-\mu_{h}(s)R(s,\pi_{h}(s),\mu_{h})\right)\right|\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{N}\left[\sum_{h=0}^{H-1}\left(\frac{L_{s}}{2}\|\mu_{h}-\widehat{\mu}_{h}\|_{1}+L_{\mu}\|\mu_{h}-\widehat{\mu}_{h}\|_{1}\right)\right].$

The statement of the lemma follows by an application of Lemma A.2. ∎

Step 3: Bounding difference in policy deviation. Finally, to conclude the
proof of the main theorem of this section, we will prove that the improvement
in expectation due to single-sided policy changes are at most of order
$\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$.

###### Lemma

Suppose $\boldsymbol{\pi}=\\{\pi_{h}\\}_{h=0}^{H-1}\in\Pi^{H}$ and
$\boldsymbol{\pi}^{\prime}=\\{\pi_{h}^{\prime}\\}_{h=0}^{H-1}\in\Pi^{H}$
arbitrary policies, and
$\bm{\mu}^{\boldsymbol{\pi}}:=\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi})$ is
the population distribution induced by $\boldsymbol{\pi}$. Then

$\left|J_{P,R}^{H,N,(1)}(\boldsymbol{\pi}^{\prime},\boldsymbol{\pi},\dots,\boldsymbol{\pi})-V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}),\boldsymbol{\pi}^{\prime})\right|\\\
\leq\sum_{h=0}^{H-1}\biggl{(}\frac{L_{\mu}}{2}\mathbb{E}\left[\|\widehat{\mu}_{h}-\mu^{\boldsymbol{\pi}}_{h}\|_{1}\right]+K_{\mu}\sum_{h^{\prime}=0}^{h-1}\mathbb{E}\left[\|\widehat{\mu}_{h^{\prime}}-\mu_{h^{\prime}}^{\boldsymbol{\pi}}\|_{1}\right]\biggr{)}.$

###### Proof.

Define the random variables
$\\{s^{i}_{h},a_{h}^{i}\\}_{i,h},\\{\widehat{\mu}_{h}\\}_{h}$ as in the
definition of $N$-FH-SAG (Definition 3.1). In addition, define the random
variables $\\{s_{h},a_{h}\\}_{h}$ evolving according to the FH-MFG with
population
$\bm{\mu}^{\boldsymbol{\pi}}:=\\{\mu^{\boldsymbol{\pi}}_{h}\\}_{h}:=\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi})$
and representative policy $\boldsymbol{\pi}^{\prime}$, independent from the
random variables $\\{s^{i}_{h},a_{h}^{i}\\}_{i,h}$. Hence
$s_{0}\sim\mu_{0},a_{h}\sim\pi^{\prime}(\cdot|s_{h}),s_{h+1}\sim
P(\cdot|s_{h},a_{h},\mu^{\boldsymbol{\pi}}_{h})$. Define also for simplicity

$\displaystyle
E_{N}:=\left|J_{P,R}^{H,N,(1)}(\boldsymbol{\pi}^{\prime},\boldsymbol{\pi},\dots,\boldsymbol{\pi})-V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0}\boldsymbol{\pi}),\boldsymbol{\pi}^{\prime})\right|.$

With these definitions, we have

$\displaystyle E_{N}$
$\displaystyle=\left|\operatorname{\mathbb{E}}\left[\sum_{h=0}^{H-1}R(s_{h},a_{h},\mu^{\boldsymbol{\pi}}_{h})-\sum_{h=0}^{H-1}R(s_{h}^{1},a_{h}^{1},\widehat{\mu}_{h})\right]\right|$
$\displaystyle\leq\sum_{h=0}^{H-1}\left|\operatorname{\mathbb{E}}\left[R(s_{h},a_{h},\mu^{\boldsymbol{\pi}}_{h})-R(s_{h}^{1},a_{h}^{1},\widehat{\mu}_{h})\right]\right|.$
(4)

Furthermore, for any $h\in\\{0,\ldots,H-1\\}$,

$\displaystyle|\operatorname{\mathbb{E}}$
$\displaystyle\left[R(s_{h},a_{h},\mu^{\boldsymbol{\pi}}_{h})-R(s_{h}^{1},a_{h}^{1},\widehat{\mu}_{h})\right]|$
$\displaystyle\leq$
$\displaystyle\left|\operatorname{\mathbb{E}}\left[R(s_{h},a_{h},\mu^{\boldsymbol{\pi}}_{h})-R(s_{h}^{1},a_{h}^{1},\mu^{\boldsymbol{\pi}}_{h})\right]\right|$
$\displaystyle+\left|\operatorname{\mathbb{E}}\left[R(s_{h}^{1},a_{h}^{1},\mu^{\boldsymbol{\pi}}_{h})-R(s_{h}^{1},a_{h}^{1},\widehat{\mu}_{h})\right]\right|$
$\displaystyle\leq$
$\displaystyle\left|\operatorname{\mathbb{E}}\left[R(s_{h},\pi^{\prime}_{h}(s_{h}),\mu^{\boldsymbol{\pi}}_{h})-R(s_{h}^{1},\pi^{\prime}_{h}(s_{h}^{1}),\mu^{\boldsymbol{\pi}}_{h})\right]\right|$
$\displaystyle+L_{\mu}\operatorname{\mathbb{E}}\left[\|\mu^{\boldsymbol{\pi}}_{h}-\widehat{\mu}_{h}\|_{1}\right]$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\|\operatorname{\mathbb{P}}[s_{h}=\cdot]-\operatorname{\mathbb{P}}[s_{h}^{1}=\cdot]\|_{1}+L_{\mu}\operatorname{\mathbb{E}}\left[\|\mu^{\boldsymbol{\pi}}_{h}-\widehat{\mu}_{h}\|_{1}\right],$

where the last line follows since $R$ is bounded in $[0,1]$. Replacing this in
Equation (4),

$\displaystyle
E_{N}\leq\frac{1}{2}\sum_{h}\|\operatorname{\mathbb{P}}[s_{h}=\cdot]-\operatorname{\mathbb{P}}[s_{h}^{1}=\cdot]\|_{1}+L_{\mu}\sum_{h}\operatorname{\mathbb{E}}\left[\|\mu^{\boldsymbol{\pi}}_{h}-\widehat{\mu}_{h}\|_{1}\right].$
(5)

The first sum above we upper bound in the rest of the proof inductively.

Firstly, by definitions of $N$-FH-SAG and FH-MFG, both $s_{0}^{1}$ and $s_{0}$
have distribution $\mu_{0}$, hence
$\|\operatorname{\mathbb{P}}[s_{0}=\cdot]-\operatorname{\mathbb{P}}[s_{0}^{1}=\cdot]\|_{1}=0$.
Assume that $h\geq 1$. We note that $P$ takes values in $\Delta_{\mathcal{S}}$
and the random vector $\widehat{\mu}_{h}$ takes values in the discrete set
$\\{\frac{1}{N}u:u\in\\{0,\ldots,N\\}^{\mathcal{S}},\sum_{s}u(s)=N\\}\subset\Delta_{\mathcal{S}}$,
hence we have the bounds:

$\displaystyle\|$
$\displaystyle\operatorname{\mathbb{P}}[s_{h+1}=\cdot]-\operatorname{\mathbb{P}}[s^{1}_{h+1}=\cdot]\|_{1}$
$\displaystyle\leq$
$\displaystyle\left\|\sum_{s,\mu}P(s,\pi^{\prime}_{h}(s),\mu)\operatorname{\mathbb{P}}[s_{h}^{1}=s,\widehat{\mu}_{h}=\mu]-\sum_{s}P(s,\pi_{h}^{\prime}(s),\mu^{\boldsymbol{\pi}}_{h})\operatorname{\mathbb{P}}[s_{h}=s]\right\|_{1}$
$\displaystyle\leq$
$\displaystyle\left\|\sum_{s}P(s,\pi_{h}^{\prime}(s),\mu^{\boldsymbol{\pi}}_{h})\operatorname{\mathbb{P}}[s_{h}^{1}=s]-\sum_{s}P(s,\pi_{h}^{\prime}(s),\mu^{\boldsymbol{\pi}}_{h})\operatorname{\mathbb{P}}[s_{h}=s]\right\|_{1}$
$\displaystyle+\left\|\sum_{s,\mu}\left(P(s,\pi_{h}^{\prime}(s),\mu)-P(s,\pi_{h}^{\prime}(s),\mu^{\boldsymbol{\pi}}_{h})\right)\operatorname{\mathbb{P}}[s_{h}^{1}=s,\widehat{\mu}_{h}=\mu]\right\|_{1}$
$\displaystyle\leq$
$\displaystyle\left\|\operatorname{\mathbb{P}}[s_{h}^{1}=\cdot]-\operatorname{\mathbb{P}}[s_{h}=\cdot]\right\|_{1}+\sum_{s,\mu}K_{\mu}\left\|\mu-\mu^{\boldsymbol{\pi}}_{h}\right\|_{1}\operatorname{\mathbb{P}}[s_{h}^{1}=s,\widehat{\mu}_{h}=\mu]$
$\displaystyle\leq$
$\displaystyle\left\|\operatorname{\mathbb{P}}[s_{h}^{1}=\cdot]-\operatorname{\mathbb{P}}[s_{h}=\cdot]\right\|_{1}+K_{\mu}\operatorname{\mathbb{E}}\left[\left\|\widehat{\mu}_{h}^{\boldsymbol{\pi}}-\mu^{\boldsymbol{\pi}}_{h}\right\|_{1}\right]$

where the last two lines follow from the fact that $P$ is $K_{\mu}$ Lipschitz
in $\mu$ and stochastic matrices are non-expansive in the total-variation norm
over probability distributions. By induction, we conclude that for all $h\geq
0$, it holds that:

$\displaystyle\|$
$\displaystyle\operatorname{\mathbb{P}}[s_{h}=\cdot]-\operatorname{\mathbb{P}}[s^{1}_{h}=\cdot]\|_{1}\leq
K_{\mu}\sum_{h^{\prime}=0}^{h}\operatorname{\mathbb{E}}\left[\left\|\widehat{\mu}_{h^{\prime}}^{\boldsymbol{\pi}}-\mu^{\boldsymbol{\pi}}_{h^{\prime}}\right\|_{1}\right].$

Placing this result into Equation (5), we obtain the statement of the lemma.

∎

Since
$\mathbb{E}\left[\|\widehat{\mu}_{h^{\prime}}-\mu_{h^{\prime}}^{\boldsymbol{\pi}}\|_{1}\right]$
above in the theorem is of the order of
$\mathcal{O}\left(\nicefrac{{1}}{{\sqrt{N}}}\right)$ by the result in step 1,
the result above allows us to bound exploitability in the $N$-FH-SAG.

Conclusion and Statement of Result. Finally, we can merge the results up until
this stage to upper bound the exploitability. By definition of the FH-MFG-NE,
we have:

$\delta\geq\max_{\boldsymbol{\pi}^{\prime}\in\Pi^{H}}V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}_{\delta}),\boldsymbol{\pi}^{\prime})-V_{P,R}^{H}(\Lambda^{H}_{P}(\mu_{0},\boldsymbol{\pi}_{\delta}),\boldsymbol{\pi}_{\delta})$

The upper bounds on the deviation between $V_{P,R}^{H}$ and
$J_{P,R}^{H,N,(1)}$ from the previous steps directly yields the statement of
the theorem. We state it below for completeness.

It holds that

$\displaystyle\mathcal{E}_{P,R}^{H,N,(1)}(\boldsymbol{\pi}_{\delta},\dots,\boldsymbol{\pi}_{\delta})\leq
2\delta+\frac{C_{1}}{\sqrt{N}}+\frac{C_{2}}{N}=O\left(\delta+\frac{1}{\sqrt{N}}\right)$

where $\boldsymbol{\pi}_{\delta}$ is a $\delta$-FH-MFG Nash equilibrium and

$\displaystyle
C_{1}=|\mathcal{S}|\sqrt{\frac{\pi}{2}}\left((2L_{\mu}+\frac{L_{s}}{2})\sum_{h=0}^{H-1}\frac{1-L_{pop,\mu}^{h+1}}{1-L_{pop,\mu}}+K_{\mu}\sum_{h=0}^{H-1}\sum_{i=0}^{h-1}\frac{1-L_{pop,\mu}^{i+1}}{1-L_{pop,\mu}}\right)$
$\displaystyle
C_{2}=L_{\mu}K_{a}\sum_{h=0}^{H-1}\frac{1-L_{pop,\mu}^{h}}{1-L_{pop,\mu}}+K_{a}K_{\mu}\sum_{h=0}^{H-1}\sum_{i=0}^{h-1}\frac{1-L_{pop,\mu}^{i}}{1-L_{pop,\mu}},$

where we use shorthand notation $\frac{1-L_{pop,\mu}^{k}}{1-L_{pop,\mu}}:=k-1$
when $L_{pop,\mu}=1$.

A note on constants. Note that constants $C_{1},C_{2}$ in Section A.2 depend
on horizon with $\frac{H^{2}}{1-L_{pop,\mu}}$ if $L_{pop,\mu}<1$, with $H^{3}$
if $L_{pop,\mu}=1$ and with $H^{2}\frac{1-L_{pop,\mu}^{H+1}}{1-L_{pop,\mu}}$
if $L_{pop,\mu}>1$.

###  A.3. Lower Bound for FH-MFG: Extended Proof of Theorem 1

The proof will be by construction: we will explicitly define an FH-MFG where
the optimal policy for the $N$-agent game diverges quickly from the FH-MFG-NE
policy.

Preliminaries. We first define a few utility functions. Define
$\mathbf{g}:\Delta_{2}\rightarrow
B_{\infty,+}^{2}:=\\{\mathbf{x}\in\mathbb{R}^{2}:\|\mathbf{x}\|_{\infty}=1,\
x_{1},x_{2}\geq 0\\}$ and $\mathbf{h}:\Delta_{2}\rightarrow[0,1]^{2}$ as
follows:

$\displaystyle\mathbf{g}(x_{1},x_{2})$
$\displaystyle:=\begin{pmatrix}\mathbf{g}_{1}(x_{1},x_{2})\\\
\mathbf{g}_{2}(x_{1},x_{2})\end{pmatrix}:=\begin{pmatrix}\frac{x_{1}}{\max\\{x_{1},x_{2}\\}}\\\
\frac{x_{2}}{\max\\{x_{1},x_{2}\\}}\end{pmatrix},$
$\displaystyle\mathbf{h}(x_{1},x_{2})$
$\displaystyle:=\begin{pmatrix}\mathbf{h}_{1}(x_{1},x_{2})\\\
\mathbf{h}_{2}(x_{1},x_{2})\end{pmatrix}:=\begin{pmatrix}\max\\{4x_{2},1\\}\\\
\max\\{4x_{1},1\\}\end{pmatrix}.$

Furthermore, for any $\epsilon>0$ we define
$\omega_{\epsilon}:[0,1]\rightarrow[0,1]$ as:

$\displaystyle\omega_{\epsilon}(x)$ $\displaystyle=\begin{cases}1,\quad
x>\nicefrac{{1}}{{2}}+\epsilon\\\ 0,\quad x<\nicefrac{{1}}{{2}}-\epsilon\\\
\frac{1}{2}+\frac{x-\nicefrac{{1}}{{2}}}{2\epsilon},\quad
x\in[\nicefrac{{1}}{{2}}-\epsilon,\nicefrac{{1}}{{2}}+\epsilon]\end{cases}.$

$\epsilon\in(0,\nicefrac{{1}}{{2}})$ will be specified later.

It is straightforward to verify that $\mathbf{g}$ has an inverse in its domain
given by

$\displaystyle\mathbf{g}^{-1}(x_{1},x_{2})=\left(\frac{x_{1}}{x_{1}+x_{2}},\frac{x_{2}}{x_{1}+x_{2}}\right),\forall(x_{1},x_{2})\in
B^{2}_{\infty,+}.$

Furthermore, it holds for $\mathbf{x}=(x_{1},x_{2})\in
B^{2}_{\infty,+},\mathbf{y}=(y_{1},y_{2})\in B^{2}_{\infty,+}$

$\displaystyle\|\mathbf{g}^{-1}$
$\displaystyle(\mathbf{x})-\mathbf{g}^{-1}(\mathbf{y})\|_{1}$ $\displaystyle=$
$\displaystyle\left|\frac{x_{1}}{x_{1}+x_{2}}-\frac{y_{1}}{y_{1}+y_{2}}\right|+\left|\frac{x_{2}}{x_{1}+x_{2}}-\frac{y_{2}}{y_{1}+y_{2}}\right|$
$\displaystyle=$
$\displaystyle\left|\frac{x_{1}(y_{2}-x_{2})+x_{2}(x_{1}-y_{1})}{(x_{1}+x_{2})(y_{1}+y_{2})}\right|+\left|\frac{x_{2}(y_{1}-x_{1})+x_{1}(x_{2}-y_{2})}{(x_{1}+x_{2})(y_{1}+y_{2})}\right|$
$\displaystyle\leq$ $\displaystyle 2\|\mathbf{x}-\mathbf{y}\|_{1},$

and likewise for $\mathbf{u},\mathbf{v}\in\Delta_{2}$, letting
$u_{+}:=\max\\{u_{1},u_{2}\\},v_{+}:=\max\\{v_{1},v_{2}\\},$

$\displaystyle\|\mathbf{g}(\mathbf{u})-\mathbf{g}(\mathbf{v})\|_{1}=$
$\displaystyle\left|\frac{u_{1}}{u_{+}}-\frac{v_{1}}{v_{+}}\right|+\left|\frac{u_{2}}{u_{+}}-\frac{v_{2}}{v_{+}}\right|$
$\displaystyle=$
$\displaystyle\left|\frac{u_{1}v_{+}-v_{1}u_{+}}{u_{+}v_{+}}\right|+\left|\frac{u_{2}v_{+}-u_{+}v_{2}}{u_{+}v_{+}}\right|\leq
2\|\mathbf{u}-\mathbf{v}\|_{1}.$

This follows from considering cases and observation that
$u_{+}\geq\nicefrac{{1}}{{2}}$, $v_{+}\geq\nicefrac{{1}}{{2}}$. Then for all
$\mathbf{u},\mathbf{v}\in\Delta_{2}$, $\mathbf{g},\mathbf{h}$ have the bi-
Lipschitz and Lipschitz properties:

$\displaystyle\frac{1}{2}\|\mathbf{u}-\mathbf{v}\|_{1}\leq\|\mathbf{g}(\mathbf{u})-\mathbf{g}(\mathbf{v})\|_{1}\leq
2\|\mathbf{u}-\mathbf{v}\|_{1},$ (6)
$\displaystyle\|\mathbf{h}(\mathbf{u})-\mathbf{h}(\mathbf{v})\|_{1}\leq
4\|\mathbf{u}-\mathbf{v}\|_{1}.$ (7)

Likewise, $\omega_{\epsilon}$, being piecewise linear, also satisfies the
Lipschitz condition:
$|\omega_{\epsilon}(x)-\omega_{\epsilon}(y)|\leq\frac{1}{2\epsilon}|x-y|,\quad\forall
x,y\in[0,1].$

Defining the FH-MFG. We take a particular FH-MFG with 6 states, 2 actions.
Define the state-actions sets:

$\displaystyle\mathcal{S}$
$\displaystyle=\\{s_{\text{Left}},s_{\text{Right}},s_{\text{LA}},s_{\text{LB}},s_{\text{RA}},s_{\text{RB}}\\},\quad\mathcal{A}=\\{a_{\text{A}},a_{\text{B}}\\}.$

Intuitively, the “main” states of the game are
$s_{\text{Left}},s_{\text{Right}}$ and the $4$ states
$s_{\text{LA}},s_{\text{LB}},s_{\text{RA}},s_{\text{RB}}$ are dummy states
that keep track of which actions were taken by which percentage of players
used to introduce a dependency of the rewards on the distribution of agents
over actions as well as states. Define the initial probabilities $\mu_{0}$ by:

$\displaystyle\bm{\mu}_{0}(s_{\text{Left}})$
$\displaystyle=\bm{\mu}_{0}(s_{\text{Right}})=\nicefrac{{1}}{{2}},$
$\displaystyle\bm{\mu}_{0}(s_{\text{LA}})$
$\displaystyle=\bm{\mu}_{0}(s_{\text{RA}})=\bm{\mu}_{0}(s_{\text{RA}})=\bm{\mu}_{0}(s_{\text{RB}})=0.$

When at the states $s_{\text{Left}},s_{\text{Right}}$, the transition
probabilities are defined for all $\mu\in\Delta_{\mathcal{S}}$ by:

$\displaystyle P(s_{\text{LA}}|s_{\text{Left}},a_{\text{A}},\mu)$
$\displaystyle=1,\quad P(s_{\text{LB}}|s_{\text{Left}},a_{\text{B}},\mu)=1,$
$\displaystyle P(s_{\text{RA}}|s_{\text{Right}},a_{\text{A}},\mu)$
$\displaystyle=1,\quad P(s_{\text{RB}}|s_{\text{Right}},a_{\text{B}},\mu)=1.$

That is, the agent transitions to one of
$\\{s_{\text{LA}},s_{\text{RA}},s_{\text{RB}},s_{\text{LB}}\\}$ to remember
its last action and left-right state. When at states
$\\{s_{\text{LA}},s_{\text{RA}},s_{\text{RB}},s_{\text{LB}}\\}$, the
transition probabilities are:

$\displaystyle\text{If }s$
$\displaystyle\in\\{s_{\text{LA}},s_{\text{LB}},s_{\text{RA}},s_{\text{RB}}\\}:$
$\displaystyle P(s^{\prime}|s,a,\mu)$
$\displaystyle=\begin{cases}\omega_{\epsilon}(\mu(s_{\text{LA}})+\mu(s_{\text{LB}})),\text{
if }s^{\prime}=s_{\text{Left}}\\\
\omega_{\epsilon}(\mu(s_{\text{RA}})+\mu(s_{\text{RB}})),\text{ if
}s^{\prime}=s_{\text{Right}}\end{cases},\forall\mu,a.$

The other non-defined transition probabilities are of course $0$.

Finally, let $\alpha,\beta>0$ such that $\alpha+\beta<1$ (to be also defined
later). The reward functions are defined for all $\mu\in\Delta_{\mathcal{S}}$
as follows:

$\displaystyle R(s_{\text{Left}},a_{\text{A}},\mu)=$ $\displaystyle
R(s_{\text{Left}},a_{\text{B}},\mu)=0,$ $\displaystyle
R(s_{\text{Right}},a_{\text{A}},\mu)=$ $\displaystyle
R(s_{\text{Right}},a_{\text{B}},\mu)=0,$
$\displaystyle\begin{pmatrix}R(s_{\text{LA}},a_{\text{A}},\mu)\\\
R(s_{\text{LB}},a_{\text{A}},\mu)\end{pmatrix}=$
$\displaystyle(1-\alpha-\beta)\mathbf{g}\big{(}\mu(s_{\text{LA}})+\mu(s_{\text{LB}}),\mu(s_{\text{RA}})+\mu(s_{\text{RB}})\big{)}$
$\displaystyle+\alpha\mathbf{h}(\mu(s_{\text{LA}}),\mu(s_{\text{LB}}))$
$\displaystyle\begin{pmatrix}R(s_{\text{LA}},a_{\text{B}},\mu)\\\
R(s_{\text{LB}},a_{\text{B}},\mu)\end{pmatrix}=$
$\displaystyle(1-\alpha-\beta)\mathbf{g}\big{(}\mu(s_{\text{LA}})+\mu(s_{\text{LB}}),\mu(s_{\text{RA}})+\mu(s_{\text{RB}})\big{)}$
$\displaystyle+\alpha\mathbf{h}(\mu(s_{\text{LA}}),\mu(s_{\text{LB}}))+\beta\mathbf{1}$
$\displaystyle\begin{pmatrix}R(s_{\text{RA}},a_{\text{A}},\mu)\\\
R(s_{\text{RB}},a_{\text{A}},\mu)\end{pmatrix}=$
$\displaystyle(1-\alpha-\beta)\mathbf{g}\big{(}\mu(s_{\text{RA}})+\mu(s_{\text{RB}}),\mu(s_{\text{LA}})+\mu(s_{\text{LB}})\big{)}$
$\displaystyle+\alpha\mathbf{h}(\mu(s_{\text{RA}}),\mu(s_{\text{RB}}))$
$\displaystyle\begin{pmatrix}R(s_{\text{RA}},a_{\text{B}},\mu)\\\
R(s_{\text{RB}},a_{\text{B}},\mu)\end{pmatrix}=$
$\displaystyle(1-\alpha-\beta)\mathbf{g}\big{(}\mu(s_{\text{RA}})+\mu(s_{\text{RB}}),\mu(s_{\text{LA}})+\mu(s_{\text{LB}})\big{)}$
$\displaystyle+\alpha\mathbf{h}(\mu(s_{\text{RA}}),\mu(s_{\text{RB}}))+\beta\mathbf{1}$

Note that only at odd steps do the agents get a reward, and at this step, it
does not matter which action the agent plays, only the state among
$\\{s_{\text{LA}},s_{\text{LA}},s_{\text{RA}},s_{\text{RB}}\\}$ and the
population distribution. The parameters $\epsilon,\alpha,\beta$ of the above
FH-MFG are “free” parameters to be specified later.

A minor remark. The arguments of $\mathbf{g}$ above will be with probability
one in the set $\Delta_{2}$ at odd-numbered time steps, but to formally
satisfy the Lipschitz condition $R\in\mathcal{R}_{2}$ one can for instance
replace
$\mathbf{g}\big{(}\mu(s_{\text{RA}})+\mu(s_{\text{RB}}),\mu(s_{\text{LA}})+\mu(s_{\text{LB}})\big{)}$
with
$\mathbf{g}\big{(}\mu(s_{\text{RA}})+\mu(s_{\text{RB}})+\mu(s_{\text{Left}}),\mu(s_{\text{LA}})+\mu(s_{\text{LB}})+\mu(s_{\text{Right}})\big{)}$
in the definitions, which will not impact the analysis since at odd timesteps
$\mu(s_{\text{Right}})=\mu(s_{\text{Left}})=0$ for both the FH-MFG and $N$-FH-
SAG.

Note that with these definitions,
$P\in\mathcal{P}_{\nicefrac{{1}}{{2\epsilon}}},R\in\mathcal{R}_{2}$ since only
$\forall\
s,s^{\prime}\in\mathcal{S},a,a^{\prime}\in\mathcal{A},\mu,\mu^{\prime}\in\Delta_{\mathcal{S}}$,
we have by the definitions:

$\displaystyle\|P(\cdot|s,a,\mu)-P(\cdot|s^{\prime},a^{\prime},\mu^{\prime})\|_{1}$
$\displaystyle\leq
2d(s,s^{\prime})+2d(a,a^{\prime})+\frac{1}{2\epsilon}\|\mu-\mu^{\prime}\|_{1},$
(8) $\displaystyle|R(s,a,\mu)-R(s^{\prime},a^{\prime},\mu^{\prime})|$
$\displaystyle\leq d(s,s^{\prime})+d(a,a^{\prime})+2\|\mu-\mu^{\prime}\|_{1},$
(9)

for any $\alpha,\beta>0$ with $\alpha+\beta<1$ and $\alpha<\frac{1}{4}$, using
the Lipschitz conditions in (6), (7).

Step 1: Solution of the FH-MFG. Next, we solve the infinite player FH-MFG and
show that the policy $\boldsymbol{\pi}^{*}_{H}:=\\{\pi^{*}_{h}\\}_{h=0}^{H-1}$
given by:

$\displaystyle\pi_{h}^{*}(a|s):=\begin{cases}1,\text{if $h$ odd and
$a=a_{\text{B}}$}\\\ \frac{1}{2},\text{if $h$ even}\\\ 0,\text{if $h$ odd and
$a=a_{\text{B}}$}\end{cases}$

It is easy to verify in this case that, if
$\bm{\mu}^{*}:=\\{\mu^{*}_{h}\\}_{h}$ is induced by $\boldsymbol{\pi}^{*}$:

$\displaystyle\mu^{*}_{h}(s_{\text{LA}})$
$\displaystyle=\mu^{*}_{h}(s_{\text{LB}})=\mu^{*}_{h}(s_{\text{RA}})=\mu^{*}_{h}(s_{\text{RB}})=\nicefrac{{1}}{{4}},\text{
if $h$ odd},$ $\displaystyle\mu^{*}_{h}(s_{\text{Left}})$
$\displaystyle=\mu^{*}_{h}(s_{\text{Right}})=\nicefrac{{1}}{{2}},\text{ if $h$
even}.$

In this case, the induced rewards in odd steps are state-independent (it is
the same for all states
$s_{\text{RA}},s_{\text{RB}},s_{\text{LA}},s_{\text{LB}}$), therefore the
policy $\boldsymbol{\pi}^{*}$ is the optimal best response to the population
and a FH-MFG.

In fact, $\boldsymbol{\pi}^{*}$ is unique up to modifications in zero-
probability sets (e.g., modifying $\pi^{*}_{h}(s_{\text{Left}})$ for odd $h$,
for which $\operatorname{\mathbb{P}}[s_{h}=s_{\text{Left}}]=0$). To see this,
for _any_ policy $\boldsymbol{\pi}\in\Pi_{H}$, it holds that

$\displaystyle\mu_{h}^{\boldsymbol{\pi}}(s_{\text{Left}})$
$\displaystyle=\mu_{h}^{\boldsymbol{\pi}}(s_{\text{Right}})=\nicefrac{{1}}{{2}},\text{
if $h$ even},$
$\displaystyle\mu_{h}^{\boldsymbol{\pi}}(s_{\text{LA}})+\mu_{h}^{\boldsymbol{\pi}}(s_{\text{LB}})$
$\displaystyle=\mu_{h}^{\boldsymbol{\pi}}(s_{\text{RA}})+\mu_{h}^{\boldsymbol{\pi}}(s_{\text{RB}})=\nicefrac{{1}}{{2}},\text{
if $h$ odd},$

as the action of the agent does not affect transition probabilities between
$s_{\text{Left}},s_{\text{Right}}$ in even rounds. Moreover, as odd stages,
the action rewards terms only depend on the state apart from the positive
additional term $\beta\mathbf{1}$, so the only optimal action will be
$a_{\text{B}}$. Finally, for $\alpha>0$, the actions
$a_{\text{A}},a_{\text{B}}$ must be played with equal probability as otherwise
the term $\alpha\mathbf{h}(\mu(s_{\text{RA}}),\mu(s_{\text{RB}}))$ will lead
to the action with lower probability assigned by being optimal.

Step 2: Population divergence in $N$-FH-MFG. We will analyze the empirical
population distribution deviation from $\bm{\mu}^{*}$, namely, we will lower
bound $\operatorname{\mathbb{E}}[\|\mu_{h}^{*}-\widehat{\mu}_{h}\|_{1}]$. The
results in this step will be valid for _any_ policy profile
$(\boldsymbol{\pi}^{1},\ldots,\boldsymbol{\pi}^{N})\in\Pi$: we emphasize that
at even $h$, $\widehat{\mu}_{h}$ is independent of agent policies in the $N$
player game. In this step, we also fix $\nicefrac{{1}}{{2\varepsilon}}=8$.

We will analyze $\widehat{\mu}_{h}$ at all even steps $h=2m$ where
$m\in\mathbb{N}_{\geq 0}$. Define the sequence of random variables for all
$m\in\mathbb{N}_{\geq 0}$ as $X_{m}:=\widehat{\mu}_{2m}(s_{\text{Left}})$.
Define $\mathcal{G}:=\\{\frac{k}{N}:k=0,\ldots,N\\}$. Note that for all even
$h=2m$, it holds almost surely that
$\widehat{\mu}_{h}(s_{\text{Left}}),\widehat{\mu}_{h}(s_{\text{Right}})\in\mathcal{G}$.
By the definition of the MFG, it holds for any $m\geq 0,k\in[N]$ that

$\displaystyle\operatorname{\mathbb{P}}[NX_{0}=k]=\binom{N}{k}2^{-N},$
$\displaystyle\operatorname{\mathbb{P}}[NX_{m+1}=k|X_{m}]=\binom{N}{k}(\omega_{\varepsilon}(X_{m}))^{k}(1-\omega_{\varepsilon}(X_{m}))^{k},$

that is, given $X_{m}$, $NX_{m+1}$ is binomially distributed with
$NX_{m+1}\sim\operatorname{Binom}(N,\omega_{\epsilon}(X_{m}))$ without any
dependence on the actions played by agents. Therefore

$\displaystyle\mathbb{E}\left[X_{m+1}|X_{m}\right]=\omega_{\epsilon}(X_{m}),\quad\operatorname{\mathbb{V}\\!\mathrm{ar}}\mathopen{}\left[X_{m+1}|X_{m}\right]\leq\frac{1}{4N}.$

We define the following set $\mathcal{G}_{*}:=\\{0,1\\}\subset\mathcal{G}$. By
the definition of the mechanics, if $x\in\mathcal{G}_{*},m\in\mathbb{N}_{\geq
0}$, it holds for all $m^{\prime}>m$ that
$\operatorname{\mathbb{P}}[X_{m^{\prime}}=X_{m}|X_{m}=x]=1$, that is once the
Markovian random process $X_{m}$ hits $\mathcal{G}_{*}$, it will remain in
$\mathcal{G}_{*}$. Furthermore, for $K:=\lfloor\log_{5}\sqrt{N}\rfloor$, and
for $k=0,\ldots,K$ define the level sets:

$\displaystyle\mathcal{G}_{-1}$
$\displaystyle:=\mathcal{G},\quad\mathcal{G}_{k}:=\left\\{x\in\mathcal{G}:\left|x-\frac{1}{2}\right|\geq\frac{5^{k}}{2\sqrt{N}}\right\\}.$

For all $k\geq K$, define $\mathcal{G}_{k}:=\mathcal{G}_{*}.$

Firstly, we have that

$\displaystyle\operatorname{\mathbb{P}}[X_{0}\in\mathcal{G}_{0}]=$
$\displaystyle\operatorname{\mathbb{P}}\left[\left|\frac{1}{N}\sum_{i}\mathbbm{1}_{\\{s_{0}^{i}=s_{\text{Left}}\\}}-\frac{1}{2}\right|\geq\frac{1}{2\sqrt{N}}\right]$
$\displaystyle=$
$\displaystyle\operatorname{\mathbb{P}}\left[\left|\sum_{i}\mathbbm{1}_{\\{s_{0}^{i}=s_{\text{Left}}\\}}-\frac{N}{2}\right|\geq\frac{\sqrt{N}}{2}\right]\geq\frac{1}{10},$

where in the last line we applied the anti-concentration result of Lemma A.1
on the sum of independent Bernoulli random variables
$\mathbbm{1}_{\\{s_{0}^{i}=s_{\text{Left}}\\}}$ for $i\in[N]$.

Next, assume that for some $m\in 1,\ldots,K-1$ we have $p\in\mathcal{G}_{m}$.
If $\omega_{\epsilon}(p)\in\\{0,1\\}$, it holds trivially that
$\operatorname{\mathbb{P}}[X_{m+1}\in\mathcal{G}_{m+1}|X_{m}=p]=1$. Otherwise,
if $\omega_{\epsilon}(p)\in(0,1)$,

$\displaystyle\operatorname{\mathbb{P}}$
$\displaystyle[X_{m+1}\in\mathcal{G}_{m+1}|X_{m}=p]$ $\displaystyle=$
$\displaystyle\operatorname{\mathbb{P}}\left[|X_{m+1}-\frac{1}{2}|\geq\frac{5^{m+1}}{2\sqrt{N}}\,\middle|\,X_{m}=p\right]$
$\displaystyle\geq$
$\displaystyle\operatorname{\mathbb{P}}\left[|\omega_{\epsilon}(p)-\frac{1}{2}|-|X_{m+1}-\omega_{\epsilon}(p)|\geq\frac{5^{m+1}}{2\sqrt{N}}\middle|X_{m}=p\right].$

Since in this case
$|\omega_{\epsilon}(X_{m})-\frac{1}{2}|=|\omega_{\epsilon}(X_{m})-\omega_{\epsilon}(\frac{1}{2})|\geq\nicefrac{{1}}{{2\epsilon}}|X_{m}-\omega_{\epsilon}(\frac{1}{2})|$,
we have

$\displaystyle\operatorname{\mathbb{P}}$
$\displaystyle[X_{m+1}\in\mathcal{G}_{m+1}|X_{m}=p]$ $\displaystyle\geq$
$\displaystyle\operatorname{\mathbb{P}}\left[|\omega_{\epsilon}(p)-\frac{1}{2}|-|X_{m+1}-\omega_{\epsilon}(p)|\geq\frac{5^{m+1}}{2\sqrt{N}}\middle|X_{m}=p\right]$
$\displaystyle=$
$\displaystyle\operatorname{\mathbb{P}}\left[\Big{|}X_{m+1}-\omega_{\epsilon}(p)\Big{|}\leq\left|\omega_{\epsilon}(p)-\frac{1}{2}\right|-\frac{5^{m+1}}{2\sqrt{N}}\middle|X_{m}=p\right]$
$\displaystyle\geq$
$\displaystyle\operatorname{\mathbb{P}}\left[\Big{|}X_{m+1}-\omega_{\epsilon}(p)\Big{|}\leq
8\frac{5^{m}}{2\sqrt{N}}-\frac{5^{m+1}}{2\sqrt{N}}\middle|X_{m}=p\right]$
$\displaystyle=$
$\displaystyle\operatorname{\mathbb{P}}\left[\Big{|}X_{m+1}-\omega_{\epsilon}(p)\Big{|}\leq
3\frac{5^{m}}{2\sqrt{N}}\middle|X_{m}=p\right]$ $\displaystyle\geq$
$\displaystyle 1-2\exp\left\\{-\frac{9}{50}25^{m+1}\right\\}$

where in the last line we invoked the Hoeffding concentration bound (Lemma
A.1).

Using the above result inductively for $m\in 0,\ldots,K$ it holds that

$\displaystyle\operatorname{\mathbb{P}}[X_{m}\in\mathcal{G}_{m}|X_{0}\in\mathcal{G}_{0}]\geq$
$\displaystyle\prod_{m^{\prime}=1}^{m}\operatorname{\mathbb{P}}[X_{m^{\prime}}\in\mathcal{G}_{m^{\prime}}|X_{m^{\prime}-1}\in\mathcal{G}_{m^{\prime}-1}]$
$\displaystyle\geq$
$\displaystyle\prod_{m^{\prime}=1}^{m}\left(1-2\exp\left\\{-\frac{9}{50}25^{m^{\prime}}\right\\}\right)$
$\displaystyle\geq$
$\displaystyle\left(1-2\sum_{m^{\prime}=0}^{\infty}\exp\left\\{-\frac{9}{50}25^{m^{\prime}+1}\right\\}\right)$
$\displaystyle\geq$
$\displaystyle\left(1-2\sum_{m^{\prime}=0}^{\infty}\exp\left\\{-\frac{9}{2}m^{\prime}-\frac{9}{2}\right\\}\right)$
$\displaystyle\geq$
$\displaystyle\left(1-\frac{2e^{-\nicefrac{{9}}{{2}}}}{1-e^{-\nicefrac{{9}}{{2}}}}\right)\geq\frac{9}{10}.$

Since for $k>K$,
$\operatorname{\mathbb{P}}[X_{k+1}\in\mathcal{G}_{*}|X_{k}\in\mathcal{G}_{*}]=1$
and
$\operatorname{\mathbb{P}}[X_{0}\in\mathcal{G}_{0}]\geq\nicefrac{{1}}{{10}}$,
it also holds that

$\displaystyle\operatorname{\mathbb{P}}[X_{m}\in\mathcal{G}_{m},\forall m\geq
0]\geq\frac{9}{100}.$

Finally, we use the above lower bound on the probability to lower bound the
expectation:

$\displaystyle\mathbb{E}\left[\|\widehat{\mu}_{2m}-\mu_{2m}\|_{1}\right]$
$\displaystyle\geq\operatorname{\mathbb{P}}[X_{m}\in\mathcal{G}_{m}]\,\mathbb{E}\left[\left\|\widehat{\mu}_{2m}-\mu_{2m}\right\|_{1}\left|X_{m}\in\mathcal{G}_{m}\right.\right]$
$\displaystyle\geq\operatorname{\mathbb{P}}[X_{m}\in\mathcal{G}_{m}]\,\mathbb{E}\left[2|X_{m}-\nicefrac{{1}}{{2}}|\,\,\left|X_{m}\in\mathcal{G}_{m}\right.\right]$
$\displaystyle\geq\frac{9}{100}\,\min\left\\{\frac{5^{m}}{\sqrt{N}},1\right\\}.$

For odd $h=2m+1$, we also have the inequality

$\displaystyle\mathbb{E}\left[\|\widehat{\mu}_{2m+1}-\mu_{2m+1}\|_{1}\right]$
$\displaystyle\geq\mathbb{E}\left[\|\widehat{\mu}_{2m}-\mu_{2m}\|_{1}\right]$
$\displaystyle\geq\frac{9}{100}\,\min\left\\{\frac{5^{m}}{\sqrt{N}},1\right\\}.$

which completes the first statement of the theorem (as
$5^{H/2}=\Omega(2^{H})$).

Step 3: Hitting time for $\mathcal{G}_{*}$. We will show that the empirical
distribution of agent states almost always concentrates on one of
$s_{\text{Left}},s_{\text{Right}}$ during the even rounds in the $N$-player
game, and bound the expected waiting time for this to happen. The
distributions of agents over states $s_{\text{Left}},s_{\text{Right}}$ in the
even rounds are policy independent (they are not affected by which actions are
played): hence the results from Step 2 still hold for the population
distribution and the expected time computed in this step will be valid for any
policy.

For simplicity, we define the FH-MFG for the non-terminating infinite horizon
chain, and we will compute value functions up to horizon $H$. Define the
(random) hitting time $\tau$ as follows:

$\displaystyle\tau:=\inf\\{m\geq
0:\widehat{\mu}_{2m}(s_{\text{Left}})\in\mathcal{G}_{*}\\}=\inf\\{m\geq
0:X_{m}\in\mathcal{G}_{*}\\}.$

Note that for any $p\in\mathcal{G}$, it holds that
$\operatorname{\mathbb{P}}[X_{m+1}\in\mathcal{G}_{*}|X_{m}=p]=\widehat{\mu}_{2m}(s_{\text{Left}})^{N}+\widehat{\mu}_{2m}(s_{\text{Right}})^{N}=p^{N}+(1-p)^{N}\geq
2^{-N}.$ Therefore for all $m$ it holds that
$\operatorname{\mathbb{P}}[\widehat{\mu}_{2m}\notin\mathcal{G}_{*}]\leq\left(1-2^{-N}\right)^{m-1}$.
By the Borel-Cantelli lemma, we can conclude that $\tau<\infty$ almost surely,
and in particular $T_{\tau}:=\operatorname{\mathbb{E}}[\tau|X_{0}=x]<\infty$
for any $x\in\mathcal{G}$.

Next, we compute the expected value $T_{\tau}$. Define the following two
quantities:

$\displaystyle T_{-1}$
$\displaystyle:=\sup_{x\in\mathcal{G}_{-1}}\\{\operatorname{\mathbb{E}}[\tau|X_{0}=x]\\}$
$\displaystyle T_{0}$
$\displaystyle:=\sup_{x\in\mathcal{G}_{0}}\\{\operatorname{\mathbb{E}}[\tau|X_{0}=x]\\}.$

First, we compute an upper bound for $T_{0}$. Define the event:

$\displaystyle
E_{0}:=\bigcap_{m^{\prime}\in[K]}\\{X_{m^{\prime}}\in\mathcal{G}_{m^{\prime}}\\}.$

Then, $T_{0}$ is upper bounded by:

$\displaystyle T_{0}=$
$\displaystyle\sup_{x\in\mathcal{G}_{0}}\operatorname{\mathbb{E}}[\tau|X_{0}=x]$
$\displaystyle=$
$\displaystyle\sup_{x\in\mathcal{G}_{0}}\operatorname{\mathbb{E}}[\tau|E_{0},X_{0}=x]\operatorname{\mathbb{P}}[E_{0}|X_{0}=x]$
$\displaystyle+\operatorname{\mathbb{E}}[\tau|E_{0}^{c},X_{0}=x]\operatorname{\mathbb{P}}[E_{0}^{c}|X_{0}=x]$
$\displaystyle\leq$
$\displaystyle\sup_{x\in\mathcal{G}_{0}}\operatorname{\mathbb{E}}[\tau|E_{0},X_{0}=x]\operatorname{\mathbb{P}}[E_{0}|X_{0}=x]$
$\displaystyle+\operatorname{\mathbb{E}}[\tau|E_{0}^{c},X_{0}=x]\operatorname{\mathbb{P}}[E_{0}^{c}|X_{0}=x]$
$\displaystyle\leq$ $\displaystyle
K\frac{9}{10}+\left(K+T_{-1}\right)\frac{1}{10}=K+\frac{T_{-1}}{10}$

where in the last step we used the lower bound on
$\operatorname{\mathbb{P}}[E_{0}]$ from Step 2. Similarly for $T_{-1}$, from
the one-sided anti-concentration bound (Lemma A.1) it holds that:

$\displaystyle T_{-1}\leq$
$\displaystyle\sup_{x\in\mathcal{G}_{-1}}\operatorname{\mathbb{E}}[\tau|X_{0}=x]$
$\displaystyle\leq$
$\displaystyle\operatorname{\mathbb{E}}[\tau|x\in\mathcal{G}_{0},X_{0}=x]\operatorname{\mathbb{P}}[x\in\mathcal{G}_{0}|X_{0}=x]$
$\displaystyle+\operatorname{\mathbb{E}}[\tau|x\notin\mathcal{G}_{0},X_{0}=x]\operatorname{\mathbb{P}}[x\notin\mathcal{G}_{0}|X_{0}=x]$
$\displaystyle\leq$
$\displaystyle\frac{1}{20}(T_{0}+1)+\frac{19}{20}(T_{-1}+1),$

the last line following since $T_{-1}>T_{0}$ by definition. Solving the two
inequalities, we obtain

$\displaystyle T_{\tau}\leq T_{-1}\leq\frac{200}{9}+\frac{10K}{9}\leq
23+\frac{5}{9}\log_{5}{N}.$

Step 4: Ergodic optimal response to $N$-players. Next, we formulate a policy
$\boldsymbol{\pi}^{\text{br}}=\\{\pi^{\text{br}}_{h}\\}_{h=0}^{H-1}\in\Pi^{H}$
that is ergodically optimal for the $N$-player game and can exploit a
population that deploys the unique FH-MFG-NE. For all $h$, the optimal policy
will be defined by:

$\displaystyle\pi^{\text{br}}_{h}(a|s)=\begin{cases}1,\text{ if
$s=s_{\text{Left}}$, $a=a_{\text{A}}$}\\\ 1,\text{ if $s=s_{\text{Right}}$,
$a=a_{\text{B}}$}\\\ 1,\text{ if
$s\notin\\{s_{\text{Left}},s_{\text{Right}}\\}$, $a=a_{\text{B}}$}\\\ 0,\text{
otherwise}\end{cases}$

Intuitively, $\pi^{\text{br}}_{h}$ becomes optimal once all the agents are
concentrated in the same states during the even rounds, which happens very
quickly as shown in Step 3. Assume that agents $i=2,\ldots N$ deploy the
unique FH-MFG-NE $\boldsymbol{\pi}^{i}=\boldsymbol{\pi}^{*}$, and for agent
$i=1$, $\boldsymbol{\pi}^{1}=\boldsymbol{\pi}^{\text{br}}$. We decompose the
three components of the rewards for the first agent, as defined in the
construction of the MFG (Step 1):

$\displaystyle J_{P,R}^{H,N,(1)}$
$\displaystyle(\boldsymbol{\pi}^{\text{br}},\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*})$
$\displaystyle=\mathbb{E}\left[\sum_{\begin{subarray}{c}h\text{ odd}\\\ 0\leq
h\leq H\end{subarray}}(1-\alpha-\beta)R^{1,\mathbf{g}}_{h}+\alpha
R^{1,\mathbf{h}}_{h}+\beta\mathbbm{1}_{\\{a^{1}_{h}=a_{B}\\}}\right]$
$\displaystyle\geq(1-\alpha-\beta)\mathbb{E}\left[\sum_{\text{odd
}h=0}^{H-1}R^{1,\mathbf{g}}_{h}\right]+\beta\left\lfloor\frac{H}{2}\right\rfloor$

as by definition clearly
$\mathbb{E}\left[\mathbbm{1}_{\\{a^{1}_{h}=a_{B}\\}}\right]=1$ for all odd $h$
and $R^{\mathbf{h}}_{h}\geq 0$ almost surely.

We analyze the terms $R^{1,\mathbf{g}}_{h}$ when the first agent follows
$\boldsymbol{\pi}^{\text{br}}$. By the definition of the dynamics and
$\boldsymbol{\pi}^{\text{br}}$, it holds that

$\displaystyle
R^{1,\mathbf{g}}_{h}=g_{1}(\widehat{\mu}_{h-1}(s_{h-1}^{1}),\widehat{\mu}_{h-1}(\widebar{s}_{h-1}^{1}))$

where $\widebar{s}_{h-1}^{1}:=s_{\text{Left}}$ if
$s_{h-1}^{1}=s_{\text{Right}}$ and $\widebar{s}_{h-1}^{1}:=s_{\text{Right}}$
if $s_{h-1}^{1}=s_{\text{Left}}$. As
$\operatorname{\mathbb{P}}[s^{1}_{h-1}=\cdot,\ldots,s^{N}_{h-1}=\cdot]$ at
even step $h-1$ is permutation invariant, it holds that
$\operatorname{\mathbb{P}}[s^{1}_{h-1}=\cdot|\widehat{\mu}_{h-1}=\mu]=\mu(\cdot)$
for any $\mu\in\mathcal{G}$. Therefore,

$\displaystyle\operatorname{\mathbb{E}}[R^{1,\mathbf{g}}_{h}]=$
$\displaystyle\sum_{\begin{subarray}{c}\mu\in\mathcal{G}\\\
s\in\\{s_{\text{Left}},s_{\text{Right}}\\}\end{subarray}}\operatorname{\mathbb{P}}[\widehat{\mu}_{h-1}=\mu]\operatorname{\mathbb{P}}[s^{1}_{h-1}=s|\widehat{\mu}_{h-1}=\mu]$
$\displaystyle\operatorname{\mathbb{E}}[R^{1,\mathbf{g}}_{h}|s^{1}_{h-1}=s,\widehat{\mu}_{h-1}=\mu]$
$\displaystyle=$ $\displaystyle\sum_{\begin{subarray}{c}\mu\in\mathcal{G}\\\
s\in\\{s_{\text{Left}},s_{\text{Right}}\\}\end{subarray}}\operatorname{\mathbb{P}}[\widehat{\mu}_{h-1}=\mu]\mu(s)g_{1}(\mu(s),\mu(\widebar{s}))\geq\nicefrac{{1}}{{2}},$

as for any $\mu$, if $s$ is such that $\mu(s)\geq\mu(\widebar{s})$ then
$g_{1}(\mu(s),\mu(\widebar{s}))=1$. Furthermore, by the definition of the
hitting time $\tau$, for any odd $h\geq 1$,
$\mathbb{E}\left[R^{\mathbf{g}}_{h}\left|2\tau<h\right.\right]=\mathbb{E}\left[R^{\mathbf{g}}_{h}\left|\widehat{\mu}_{h-1}(s_{\text{Left}})\in\mathcal{G}_{*}\right.\right]=1$,
as after time $2\tau$ the action $a_{\text{A}}$ will be optimal with reward
$R^{\mathbf{g}}_{h}=1$ almost surely, as $\boldsymbol{\pi}^{br}$ chooses
action $a_{\text{A}}$ at even steps.

Finally, using the lower bound of $\nicefrac{{1}}{{2}}$ for
$R^{\mathbf{g}}_{h}$ when $h<2\tau$ and that $R^{\mathbf{g}}_{h}=1$ when
$h>2\tau$, we obtain:

$\displaystyle\mathbb{E}\left[\sum_{\begin{subarray}{c}h\text{ odd}\\\ 0\leq
h\leq H\end{subarray}}R^{\mathbf{g}}_{h}\right]=$
$\displaystyle\mathbb{E}\left[\sum_{\begin{subarray}{c}h\text{ odd}\\\ 0\leq
h\leq\min\\{2\tau,H\\}\end{subarray}}R^{1,\mathbf{g}}_{h}+\sum_{\begin{subarray}{c}h\text{
odd}\\\ \min\\{2\tau,H\\}+1\leq h<H\end{subarray}}R^{1,\mathbf{g}}_{h}\right]$
$\displaystyle\geq$
$\displaystyle\mathbb{E}\left[\frac{1}{2}\min\left\\{\tau,\left\lfloor\frac{H}{2}\right\rfloor\right\\}+\left(\left\lfloor\frac{H}{2}\right\rfloor-\min\left\\{\tau,\left\lfloor\frac{H}{2}\right\rfloor\right\\}\right)\right]$
$\displaystyle\geq$
$\displaystyle\left\lfloor\frac{H}{2}\right\rfloor-\frac{1}{2}\mathbb{E}\left[\min\left\\{\tau,\left\lfloor\frac{H}{2}\right\rfloor\right\\}\right]$
$\displaystyle\geq$
$\displaystyle\left\lfloor\frac{H}{2}\right\rfloor-\frac{1}{2}\mathbb{E}\left[\tau\right]=\left\lfloor\frac{H}{2}\right\rfloor-\frac{T_{\tau}}{2}$

Merging the inequalities above, we obtain

$\displaystyle\,J_{P,R}^{H,N,(1)}(\boldsymbol{\pi}^{\text{br}},\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*})\geq(1-\alpha-\beta)\left(\left\lfloor\frac{H}{2}\right\rfloor-\frac{T_{\tau}}{2}\right)+\beta\left\lfloor\frac{H}{2}\right\rfloor.$

Step 5: Bounding exploitability. Finally, we will upper bound also the
expected reward of the FH-MFG-NE policy $\boldsymbol{\pi}^{*}$ and hence lower
bound the exploitability. Our conclusion will be that $\boldsymbol{\pi}^{*}$
suffers from a non-vanishing exploitability for large $H$, as
$\boldsymbol{\pi}^{\text{br}}$ becomes the best response policy after
$H\gtrsim\log N$. In this step, we assume the probability space induced by all
$N$ agents following FH-MFG-NE policy $\boldsymbol{\pi}^{\text{br}}$.

We have the definition

$\displaystyle J_{P,R}^{H,N,(1)}$
$\displaystyle(\boldsymbol{\pi}^{*},\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*})=\operatorname{\mathbb{E}}\left[\sum_{h=0}^{H-1}R(s_{h}^{1},a_{h}^{1},\widehat{\mu}_{h})\right]$
$\displaystyle\leq$
$\displaystyle(1-\alpha-\beta)\operatorname{\mathbb{E}}\left[\sum_{\text{odd
}h=0}^{H-1}R^{1,\mathbf{g}}_{h}\right]+(\alpha+\beta)\left\lfloor\frac{H}{2}\right\rfloor$

This time, when $h$ odd and $h>2\tau$, it holds that
$\operatorname{\mathbb{E}}[R^{\mathbf{g}}_{h}|h>2\tau]=\nicefrac{{1}}{{2}}$
since $\boldsymbol{\pi}^{*}$ takes actions $a_{\text{A}},a_{\text{B}}$ with
equal probability in even steps, yielding $R^{\mathbf{g}}_{h}=1$ and
$R^{\mathbf{g}}_{h}=0$ respectively almost surely. As before,

$\displaystyle\mathbb{E}\left[\sum_{\begin{subarray}{c}h\text{ odd}\\\ 0\leq
h\leq H\end{subarray}}R^{\mathbf{g}}_{h}\right]=$
$\displaystyle\mathbb{E}\left[\sum_{\begin{subarray}{c}h\text{ odd}\\\ 0\leq
h\leq\min\\{2\tau,H\\}\end{subarray}}R^{1,\mathbf{g}}_{h}+\sum_{\begin{subarray}{c}h\text{
odd}\\\ \min\\{2\tau,H\\}+1\leq h<H\end{subarray}}R^{1,\mathbf{g}}_{h}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\min\left\\{\tau,\left\lfloor\frac{H}{2}\right\rfloor\right\\}+\frac{1}{2}\left(\left\lfloor\frac{H}{2}\right\rfloor-\min\left\\{\tau,\left\lfloor\frac{H}{2}\right\rfloor\right\\}\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\mathbb{E}\left[\left\lfloor\frac{H}{2}\right\rfloor+\min\left\\{\tau,\left\lfloor\frac{H}{2}\right\rfloor\right\\}\right]$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\left\lfloor\frac{H}{2}\right\rfloor+\frac{1}{2}\operatorname{\mathbb{E}}[\tau]=\frac{1}{2}\left\lfloor\frac{H}{2}\right\rfloor+\frac{1}{2}T_{\tau}.$

The statement of the theorem then follows by lower bounding the exploitability
as follows:

$\displaystyle\mathcal{E}_{P,R}^{H,N,(1)}$
$\displaystyle(\boldsymbol{\pi}^{*},\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*})$
$\displaystyle=$
$\displaystyle\max_{\boldsymbol{\pi}}J_{P,R}^{H,N,(1)}(\boldsymbol{\pi},\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*})-J_{P,R}^{H,N,(1)}(\boldsymbol{\pi}^{*},\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*})$
$\displaystyle\geq$ $\displaystyle
J_{P,R}^{H,N,(1)}(\boldsymbol{\pi}^{\text{br}},\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*})-J_{P,R}^{H,N,(1)}(\boldsymbol{\pi}^{*},\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*})$
$\displaystyle\geq$
$\displaystyle(1-\alpha-\beta)\left(\left\lfloor\frac{H}{2}\right\rfloor-\frac{T_{\tau}}{2}-\frac{1}{2}\left\lfloor\frac{H}{2}\right\rfloor-\frac{T_{\tau}}{2}\right)-\alpha\left\lfloor\frac{H}{2}\right\rfloor$
$\displaystyle\geq$
$\displaystyle(1-\alpha-\beta)\left(\frac{H}{4}-24-\frac{5}{9}\log_{5}{N}\right)-\alpha\left\lfloor\frac{H}{2}\right\rfloor$

The above inequality implies that if $H\geq\log_{2}N$, then

$\displaystyle\mathcal{E}_{P,R}^{H,N,(1)}$
$\displaystyle(\boldsymbol{\pi}^{*},\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*})$
$\displaystyle\geq$
$\displaystyle(1-\alpha-\beta)\left(\frac{1}{4}-\frac{5}{9\log_{2}5}\right)H-\alpha\frac{H}{2}-24,$

which implies
$\mathcal{E}_{P,R}^{H,N,(1)}(\boldsymbol{\pi}^{*},\boldsymbol{\pi}^{*},\ldots,\boldsymbol{\pi}^{*})\geq\Omega(H)$
by choosing $\alpha,\beta$ small constants as
$\frac{1}{4}-\frac{5}{9\log_{2}5}>0$.

###  A.4. Upper Bound for Stat-MFG: Extended Proof of Theorem 3.2

Let $\mu^{*},\pi^{*}$ be a $\delta$-Stat-MFG-NE. As before, the proof will
proceed in three steps:

  * •

Step 1. Bounding the expected deviation of the empirical population
distribution from the mean-field distribution
$\mathbb{E}\left[\|\widehat{\mu}_{h}-\mu^{*}\|_{1}\right]$ for any given
policy $\boldsymbol{\pi}$.

  * •

Step 2.  Bounding difference of $N$ agent value function
$J_{P,R}^{\gamma,N,(i)}$ and the infinite player value function
$V^{\gamma}_{P,R}$ in the stationary mean-field game setting.

  * •

Step 3.  Bounding the exploitability of an agent when each of $N$ agents are
playing the Stat-MFG-NE policy.

Step 1: Empirical distribution bound. We first analyze the deviation of the
empirical population distribution $\widehat{\mu}_{t}$ over time from the
stable distribution $\mu^{*}$. For this, we state the following lemma and
prove it using techniques similar to Corollary D.4 of Yardim et al. (2023b).

###### Lemma

Assume that the conditions of Theorem 3.2 hold, and that
$(\mu^{*},\pi^{*})\in\Delta_{\mathcal{S}}$ is a Stat-MFG-NE. Furthermore,
assume that the $N$ agents follow policies $\\{\pi^{i}\\}_{i=1}^{N}$ in the
$N$-Stat-MFG, define
$\Delta_{\widebar{\pi}}:=\frac{1}{N}\sum_{i}\|\widebar{\pi}-\pi^{i}\|_{1}$.
Then, or any $t\geq 0$, we have

$\displaystyle\operatorname{\mathbb{E}}\left[\|\mu^{*}-\widehat{\mu}_{t}\|_{1}\right]\leq\frac{tK_{a}\Delta_{\pi}}{2}+\frac{2(t+1)\sqrt{|\mathcal{S}|}}{\sqrt{N}}.$

###### Proof.

$\mathcal{F}_{t}$ as the $\sigma$-algebra generated by the states of agents
$\\{s_{t}^{i}\\}$ at time $t$. For $\widehat{\mu_{0}}$, we have by definitions
that

$\displaystyle\operatorname{\mathbb{E}}\left[\widehat{\mu_{0}}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\frac{1}{N}\sum_{i}\mathbf{e}_{s_{t}^{i}}\right]=\mu^{*}$
$\displaystyle\operatorname{\mathbb{E}}\left[\|\widehat{\mu_{0}}-\mu^{*}\|_{2}^{2}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\frac{1}{N^{2}}\sum_{i}\left\|\left(\mathbf{e}_{s_{t}^{i}}-\mu^{*}\right)\right\|_{2}^{2}\right]\leq\frac{4}{N}$

where the last line follows by independence. The two above imply
$\operatorname{\mathbb{E}}\left[\|\widehat{\mu_{0}}-\mu^{*}\|_{1}\right]\leq\frac{2\sqrt{|\mathcal{S}|}}{\sqrt{N}}$.

Next, we inductively calculate:

$\displaystyle\operatorname{\mathbb{E}}$
$\displaystyle\left[\widehat{\mu}_{t+1}\middle|\mathcal{F}_{t}\right]=\operatorname{\mathbb{E}}\left[\frac{1}{N}\sum_{s^{\prime}\in\mathcal{S}}\sum_{i=1}^{N}\mathbbm{1}(s_{t+1}^{i}=s^{\prime})\mathbf{e}_{s^{\prime}}\middle|\mathcal{F}_{t}\right]$
$\displaystyle=\sum_{s^{\prime}\in\mathcal{S}}\mathbf{e}_{s^{\prime}}\sum_{i=1}^{N}\frac{1}{N}\widebar{P}(s^{\prime}|s_{t}^{i},\pi^{i}(s_{t}^{i}),\widehat{\mu}_{t}),$
(10) $\displaystyle\operatorname{\mathbb{E}}$
$\displaystyle[\|\widehat{\mu}_{t+1}-\operatorname{\mathbb{E}}[\widehat{\mu}_{t+1}|\mathcal{F}_{t}]\|_{2}^{2}|\mathcal{F}_{t}]$