# Infinite Horizon Average Cost Optimality Criteria for Mean-Field
Control††thanks:  E. Bayraktar is partially supported by the National Science
Foundation under grant DMS-2106556 and by the Susan M. Smith chair.

Erhan Bayraktar and Ali Devran Kara  E. Bayraktar and A.D. Kara are with the
Department of Mathematics, University of Michigan, Ann Arbor, MI, USA, Email:
<EMAIL_ADDRESS>
###### Abstract

We study mean-field control problems in discrete-time under the infinite
horizon average cost optimality criteria. We focus on both the finite
population and the infinite population setups. We show the existence of the
average cost optimality equation (ACOE) and the existence of optimal
stationary Markov policies for finite population problems under (i) a
minorization condition that provides geometric ergodicity on the collective
state process of the agents, and (ii) under standard Lipschitz continuity
assumptions on the stage-wise cost and transition function of the agents when
the Lipschitz constant of the transition function satisfies a certain bound.
Furthermore, we provide a relative value iteration algorithm that approximates
the optimal solution of the problem. For the infinite population problem, we
establish the existence of the ACOE, and the existence of optimal policies
under the continuity assumptions on the cost and the transition functions, and
we provide a convergent relative value iteration method for the infinite
population problem as well. Finally, we prove that the optimal value of the
finite population problem converges to the optimal value of the infinite
population problem as the number of agents grows to infinity. This result has
been proven for finite horizon and infinite horizon discounted cost problems,
however, it is the first result for the average cost optimality criteria to
our knowledge.

##  1 Introduction

We focus on optimal control of a team problem where the agents are only
correlated through the so-called mean-field term, i.e. the distribution of the
states of all agents. We aim to analyze the optimal control problem under the
infinite horizon average cost criteria in discrete time.

The dynamics of the model are presented as follows: suppose that $N$ agents
(decision makers or controllers) act cooperatively to minimize a cost
function, and the agents share a common state and an action space denoted by
$\mathds{X}\subset\mathds{R}^{l}$ and $\mathds{U}\subset{\mathds{R}}^{m}$ for
some $l,m<\infty$. For any time step $t$, and agent $i\in\\{1,\dots,N\\}$ we
have

$\displaystyle x^{i}_{t+1}=f(x_{t}^{i},u_{t}^{i},\mu_{\bf
x_{t}},w_{t}^{i},w_{t}^{0})$

for a measurable function $f$, where $\\{w_{t}^{i}\\}$ denotes the i.i.d.
idiosyncratic noise process, and $\\{w_{t}^{0}\\}$ denotes the i.i.d. common
noise process. Furthermore, $\mu_{\bf x}$ denotes the distribution of the
agents on the state space $\mathds{X}$ such that for a given joint state ${\bf
x}:=\\{x^{1},\dots,x^{N}\\}\in\mathds{X}^{N}$

$\displaystyle\mu_{\bf x}:=\frac{1}{N}\sum_{i=1}^{N}\delta_{x^{i}}.$

Equivalently, for a given realization of the common noise, $w_{t}^{0}$, the
next state of the agent $i$ is determined by some stochastic kernel
$\mathcal{T}^{w^{0}_{t}}(\cdot|x_{t}^{i},u_{t}^{i},\mu_{\bf x_{t}})$ such that

$\displaystyle\mathop{\rm Pr}\biggl{(}X^{i}_{t+1}\in
B\,\bigg{|}\,(X^{j},U^{j})_{[0,t]}=(x^{j},u^{j})_{[0,t]},\forall
j=1,\dots,N\biggr{)}$
$\displaystyle\qquad=\int\int_{B}\mathcal{T}^{w_{t}^{0}}(dx^{i}_{t+1}|x^{i}_{t},u^{i}_{t},\mu_{\bf
x_{t}})Pr(dw_{t}^{0}),B\in\mathcal{B}(\mathds{X}),t\in\mathds{N},$ (1)

that is, the conditional probability distribution of the state of some agent
$i$, given the state and action history of all agents, depends only on the
most recent state and action of agent $i$, and the state distribution of other
agents by conditioning on the realizations of the common noise.

At each time stage $t$, each agent receives a cost determined by a measurable
stage-wise cost function
$c:\mathds{X}\times\mathds{U}\times\mathcal{P}_{N}(\mathds{X})\to\mathds{R}$,
where $\mathcal{P}_{N}(\mathds{X})$ is the set of all empirical measures in
$\mathds{X}$ constructed using $N$ dimensional state vectors. That is, at time
$t$, agent $i$ observes the cost

$\displaystyle c(x^{i}_{t},u^{i}_{t},\mu_{\bf x_{t}}).$

For the remainder of the paper, by an abuse of notation, we will sometimes
denote the dynamics in terms of the vector state and action variables, ${\bf
x}=(x^{1},\dots,x^{N})$, and ${\bf u}=(u^{1},\dots,u^{N})$, and vector noise
variables ${\bf w}=(w^{0},w^{1},\dots,w^{N})$ such that

$\displaystyle{\bf x_{t+1}}=f({\bf x_{t},u_{t},w_{t}}).$

For the initial formulation, every agent is assumed to know the state and
action variables of every other agent. We define an admissible policy for an
agent $i$, as a sequence of functions $\gamma^{i}:=\\{\gamma^{i}_{t}\\}_{t}$,
where $\gamma^{i}_{t}$ is a $\mathds{U}$-valued (possibly randomized) function
which is measurable with respect to the $\sigma$-algebra generated by

$\displaystyle I_{t}=\\{{\bf x}_{0},\dots,{\bf x}_{t},{\bf u}_{0},\dots,{\bf
u}_{t-1}\\}.$

Accordingly, an admissible team policy, is defined as
$\gamma:=\\{\gamma^{1},\dots,\gamma^{N}\\}$, where $\gamma^{i}$ is an
admissible policy for the agent $i$. In other words, agents share the complete
information.

The objective of the agents is to minimize the following infinite horizon
average cost function

$\displaystyle J^{N}_{\infty}({\bf
x}_{0},\gamma):=\limsup_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}E_{\gamma}\left[{\bf
c}({\bf X}_{t},{\bf U}_{t})\right]$

where

$\displaystyle{\bf c}({\bf x}_{t},{\bf
u}_{t}):=\frac{1}{N}\sum_{i=1}^{N}c(x^{i}_{t},u^{i}_{t},\mu_{{\bf x}_{t}}).$

The optimal cost is defined by

$\displaystyle J_{\infty}^{N,*}({\bf
x}_{0}):=\inf_{\gamma\in\Gamma}J^{N}_{\infty}({\bf x}_{0},\gamma)$ (2)

where $\Gamma$ denotes the set of all admissible team policies.

We note that the value function that is achieved when agents share full
information, as presented here, will be taken to be our reference point for
simpler information structures.

###  1.1 Literature Review

Multi-agent systems attract attention due to their application flexibility to
real world problems. Many problems that can be modeled as a multi-agent system
may be intractable to model as single agent systems. Event though they offer a
practically rich and relevant model, the mathematical analysis is much more
challenging compared to the single agent systems except for certain classes of
multi-agent systems. The class of problems we consider in this paper, which we
will refer to as mean-field type multi-agent problems, is among the systems
that are mathematically tractable. For the mean-field type multi-agent
systems, the population is homogeneous and weakly interacting such that the
dynamics of each agent depends on the other agents only through the state
distribution of all the other agents. The motivation of this formulation comes
from systems where the effect of a single agent on the whole system is minimal
(which is usually the case for large population systems). The mathematical
tractability of the mean-field systems mainly relies on the observation that
these systems can be modeled as single agent measure valued controlled
processes where the state variable is the distribution of the agents.
Furthermore, by taking the number of agents to infinity, the weak coupling
between the agents can be broken.

The study of mean-field type multi-agent systems can be referred to as the
mean-field game theory if the agents are non-cooperative. If the agents are
cooperative, they are referred to as mean-field control. Mean-field game
theory has been introduced independently by [1, 2]. There has been great
progress and a significant number of publications since then. For some of the
work that has been done since, we cite [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15] and references therein for mean-field game theory studies both in
continuous and discrete time.

For the cooperative case, i.e. for mean-field control, similarly, there have
been a number of studies dealing with structural as well as computational and
learning-related methods. See [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
28, 29, 30, 31, 32, 33, 34] and the references therein for the study of the
dynamic programming principle, learning methods, and justification of the
exchangeability of agents for large (possibly infinite) agent team settings.

We note that most of the papers we have cited so far deal with either the
finite horizon or infinite horizon discounted cost criterion. The standard
tools used to study these problems mostly involve the dynamic programming
principle or the contraction property of the Bellman operator via the discount
factor. However, the analysis of the infinite horizon average cost optimality
criteria requires significantly different tools then the ones used in the
study of finite horizon or discounted criterion. For the average cost
criteria, one usually needs certain stability (or ergodicity) properties of
the controlled process, to ensure the solution of the problem to exist. There
are several works studying the mean-field game and control problems in
continuous time under infinite horizon average cost criteria, see [35, 36, 37,
38, 39, 40, 41, 20].

In discrete-time, the number of studies that focus on the average-cost
optimality criteria for mean-field problems is limited compared to the
continuous-time problems. Furthermore, most of the existing work focuses on
the mean-field game problems. [42, 43, 44, 45, 46] are among the papers that
study ergodic mean-field game problems in discrete time. [45] considers mean-
field game problems with discrete spaces. [44, 46] establish mean-field
equilibria using the ergodicity properties of the agent state process under a
mixing type condition on the agent dynamics. [44] also assumes that the
dynamics do not depend on the mean-field of the agent states. [42, 43] provide
value iteration algorithms for mean-field game problems where the convergence
of these iterations are shown to the mean-field equilibria under certain
minorization and mixing type conditions on the agent dynamics. We note that
the papers that focus on the game setup aim to establish the mean field
equilibria. Therefore, they are able to use the ergodicity properties of the
dynamics by using stationary policies for the agents (independent of the mean-
field term) under minorization conditions on the transition kernel. However,
for mean-field control problems, the focus is mainly on establishing the
existence of the global optimal performance for the team problem. In
particular, the resulting measure valued control problem requires the use of
policies that depend on the mean-field term (empirical distribution of the
states). Hence, the minorization condition by itself may not be sufficient to
establish the convergence to the stationary distributions of the collective
agent states. Hence, in this paper, we make use of weak continuity assumptions
on the agent dynamics without needing the ergodicity or minorization
assumptions on the state process to establish the existence of stationary and
Markov policies, as well as to show convergence of value iteration algorithms.

Finally, to our knowledge, the only paper that deals with the discrete-time
mean-field control problems under average cost (reward) criteria is [47]. In
[47], existence of optimal stationary Markov policies has been established
through the average cost optimaity inequality. It is assumed that the
difference between the optimal value of any two initial points is uniformly
bounded over all initial points and discount factors. This assumption is
usually not easy to verify using conditions on the more primitive system
components. Furthermore, in [47], two special cases are considered, namely (i)
when the cost functions only depends on the mean-field term and the dynamics
are independent of the mean-field term, and there is no common noise (ii) when
the cost functions only depends on the mean-field term (transitions can depend
on the mean field term) and the admissible policies are Lipschitz continuous
in the mean-field term. It is shown that the dynamic optimization problem
reduces to a static optimization problem under either of these special
settings.

Contributions. Our contributors are itemized as follows:

  * •

In Section 2, we focus on the finite population control problem.

    * –

In Section 2.2, we establish the existence of the average cost optimality
equation (ACOE) and the existence of optimal stationary Markov policies under
a minorization condition on the agent dynamics (Assumption 1). We also provide
a relative value iteration algorithm and its convergence with a convergence
rate. However, convergence speed diminishes as the number of agents grows and
can even fail for the infinite population.

    * –

In Section 2.3, we show the existence of the ACOE and the existence of optimal
policies without the mixing (or minorization) condition. Instead, we work with
the standard continuity conditions used to study mean-field control problems.
Namely, we assume that the stage-wise cost function and the agent transition
function are Lipschitz continuous, and the state and action spaces are compact
(see Assumption 2). We note that avoiding the use of strong ergodicity
assumptions (e.g. Assumption 1) on the state process is a significant
relaxation.

    * –

In Section 2.4, we provide a relative value iteration method and show its
convergence, which can be used to approximate the optimal solutions for the
average cost criteria under Assumption 2.

  * •

In Section 3, we focus on the infinite population control problem, which can
be modeled as a measure valued single agent control problem. Even though the
problem can be seen as a Markov decision process (MDP), the standard tools
used to study the average cost optimality criteria fail for the measure valued
mean-field MDP problem (see Remark 4 for more detail). Hence, we utilize
different tools:

    * –

In Section 3.2, we show that Assumption 2 is also sufficient for the infinite
population problem to establish the ACOE and the existence of optimal
policies.

    * –

Similarly, in Section 3.3, we show that the relative value iteration algorithm
for the infinite population problem is convergent under Assumption 2.

  * •

Finally, in Section 4, we show that the optimal average cost value of the
finite population problem converges to the optimal average cost value of the
infinite population problem as the number of agents grows to infinity. Note
that this result has been proven in the past for the finite horizon and the
infinite horizon discounted cost criteria. However, for the infinite horizon
average cost criteria, it is the first result to the best of our knowledge.

###  1.2 Metrics for Probability Measures

For the analysis of the technical results, we will make use of different
distance notions for probability measures; total variation distance and the
Wasserstein metric.

For some Polish, a separable completely metrizable topological space
$\mathds{X}$, for probability measures $\mu,\nu\in\mathcal{P}(\mathds{X})$,
the _total variation_ metric is given by

$\displaystyle\|\mu-\nu\|_{TV}$
$\displaystyle=2\sup_{B\in\mathcal{B}(\mathds{X})}|\mu(B)-\nu(B)|=\sup_{f:\|f\|_{\infty}\leq
1}\left|\int f(x)\mu(\mathrm{d}x)-\int f(x)\nu(\mathrm{d}x)\right|,$

where the supremum is taken over all measurable real $f$ such that
$\|f\|_{\infty}=\sup_{x\in\mathds{X}}|f(x)|\leq 1$.

The other distance notion we will use in the paper is the first order
Wasserstein metric. Following the Kantorovich-Rubinstein duality, the first
order Wasserstein distance between two probability measures
$\mu,\nu\in\mathcal{P}(\mathds{X})$ can be written as

$\displaystyle W_{1}(\mu,\nu)=\sup_{\|f\|_{Lip}\leq 1}\left|\int
f(x)\mu(dx)-\int f(x)\nu(dx)\right|$

where $\|f\|_{Lip}$ denotes the minimal Lipschitz constant of $f$.

##  2 Ergodic Control of Finite Populations

For the rest of the paper, we will analyze the problem by considering the
controlled process to be the state distribution of the agents, rather than the
state vector of the agents.

In this section, we will define an MDP for the distribution of the agents,
where the control actions are the joint distribution of the state and action
vectors of the agents.

We let the state space to be $\mathcal{Z}={\mathcal{P}}_{N}(\mathds{X})$ which
is the set of all empirical measures on $\mathds{X}$ that can be constructed
using the state vectors of the agents.

The admissible set of actions for some state $\mu\in\mathcal{Z}$, is denoted
by $U(\mu)$, where

$\displaystyle
U(\mu)=\\{\Theta\in{\mathcal{P}}_{N}(\mathds{X}\times\mathds{U})|\Theta(\cdot,\mathds{U})=\mu(\cdot)\\},$
(3)

that is, the set of actions for a state $\mu$, is the set of all joint
empirical measures on $\mathds{X}\times\mathds{U}$ whose marginal on
$\mathds{X}$ coincides with $\mu$.

We equip the state space $\mathcal{Z}$, and the action sets $U(\mu)$, with the
first order Wasserstein distance $W_{1}$.

In order to define the transition model for this centralized MDP, we note that
the empirical distributions of the agents’ states of the original team problem
induces a controlled Markov chain. In particular, for some set
$B\in{\mathcal{B}}(\mathcal{Z})$, we can write

$\displaystyle Pr(\mu_{t+1}\in
B|\mu_{t},\dots\mu_{0},\Theta_{t},\dots,\Theta_{0})$
$\displaystyle\qquad=\int_{{\bf
x_{t},u_{t}}\in\mathds{X}^{N}\times\mathds{U}^{N}}Pr(\mu_{t+1}\in B|{\bf
x_{t},u_{t}})Pr({\bf
dx_{t},du_{t}}|\mu_{t},\dots\mu_{0},\Theta_{t},\dots,\Theta_{0}).$

For any $\mu_{\bf x_{t},u_{t}}=\Theta_{t}$, and $\mu_{\bf x_{t}}=\mu_{t}$, the
inside term can be written as

$\displaystyle Pr(\mu_{t+1}\in B|{\bf
x_{t},u_{t}})=\int\mathds{1}_{\\{\mu_{f({\bf
x_{t},u_{t},\mu_{x_{t}},w_{t}})}\in B\\}}P(d{\bf w_{t}})$

where $P(\cdot)$ is the probability measure governing the idiosyncratic and
the common noise processes, and ${\bf w_{t}}$ is the noise vector with length
$N+1$.

If any two pairs $({\bf x_{t},u_{t}}),({\bf x^{\prime}_{t},u^{\prime}_{t}})$
have the same empirical distribution $\Theta_{t}$, then they can be viewed as
reordered versions of each other. Furthermore, since the dynamics are
identical for every agent, i.e. since the agent are exchangeable, for some
${\bf w_{t}}$, and ${\bf x_{t+1}}=f({\bf x_{t},u_{t},\mu_{\bf x_{t}}w_{t}})$,
where $\mu_{\bf x_{t+1}}=\mu_{t+1}$, by reordering ${\bf w_{t}}$, one can
construct some ${\bf w^{\prime}_{t}}$ such that ${\bf x^{\prime}_{t+1}}=f({\bf
x^{\prime}_{t},u^{\prime}_{t},\mu_{\bf x_{t}},w^{\prime}_{t}})$, where ${\bf
x^{\prime}_{t+1}}$ is just a reordered version of ${\bf x_{t+1}}$, and in
particular $\mu_{\bf x_{t+1}}=\mu_{\bf x^{\prime}_{t+1}}$.

Since the idiosyncratic noises are identically distributed for every agent, as
a result of the above discussion, for any two pairs $({\bf x_{t},u_{t}}),({\bf
x^{\prime}_{t},u^{\prime}_{t}})$ with the same empirical distribution
$\Theta_{t}$,

$\displaystyle Pr(\mu_{t+1}\in B|{\bf x_{t},u_{t}})=Pr(\mu_{t+1}\in B|{\bf
x^{\prime}_{t},u^{\prime}_{t}}).$

Therefore, the empirical distributions of the agents’ states $\mu_{t}$, and of
the joint state and actions $\Theta_{t}$ define a controlled Markov chain such
that

$\displaystyle Pr(\mu_{t+1}\in
B|\mu_{t},\dots\mu_{0},\Theta_{t},\dots,\Theta_{0})=Pr(\mu_{t+1}\in
B|\mu_{t},\Theta_{t})$ $\displaystyle:=\eta(B|\mu_{t},Q_{t})$ (4)
$\displaystyle=Pr(\mu_{t+1}\in B|{\bf x_{t},u_{t}}),\text{ for any }({\bf
x_{t},u_{t}}):\mu_{({\bf x_{t},u_{t}})}=\Theta_{t}$

where $\eta(\cdot|\mu,\Theta)\in{\mathcal{P}}({\mathcal{P}}_{N}(\mathds{X}))$
is the transition kernel of the centralized measure valued MDP, which is
induced by the dynamics of the team problem.

We define the stage-wise cost function $k(\mu,\Theta)$ by

$\displaystyle k(\mu,\Theta):=\int
c(x,u,\mu)\Theta(dx,du)=\frac{1}{N}\sum_{i=1}^{N}c(x^{i},u^{i},\mu).$ (5)

Thus, we have an MDP with state space $\mathcal{Z}$, action space
$\cup_{\mu\in\mathcal{Z}}U(\mu)$, transition kernel $\eta$ and the stage-wise
cost function $k$.

We define the set of admissible policies for this measured valued MDP as a
sequence of functions $g=\\{g_{0},g_{1},g_{2},\dots\\}$ such that at every
time $t$, $g_{t}$ is measurable with respect to the $\sigma$-algebra generated
by the information variables

$\displaystyle
I_{M}=\\{\mu_{0},\dots,\mu_{t},\Theta_{0},\dots,\Theta_{t-1}\\}.$

We denote the set of all admissible control policies by $G$ for the measure
valued MDP.

In particular, we define the infinite horizon average expected cost function
under a policy $g$ by

$\displaystyle
K^{N}_{\infty}(\mu_{0},g)=\limsup_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}E_{\mu_{0}}^{\eta}\left[k(\mu_{t},\Theta_{t})\right].$

We also define the optimal cost by

$\displaystyle K_{\infty}^{N,*}(\mu_{0})=\inf_{g\in
G}K^{N}_{\infty}(\mu_{0},g).$ (6)

###  2.1 Average Cost Optimality Equation for the Measure Valued MDP for
Finite Populations

The average cost optimality equation (ACOE) is a common tool to analyze the
optimality of the average cost criteria for MDPs. In particular for the model
described in the last section, the ACOE is given by

$\displaystyle j^{*}+v^{*}(\mu)=\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}v^{*}(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)},$
(7)

for some $v^{*}\in{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))$ where
$B({\mathcal{P}}_{N}(\mathds{X}))$ denotes the set of bounded and measurable
functions on ${\mathcal{P}}_{N}(\mathds{X})$ and some constant $j^{*}$ where
$U(\mu)$ denotes the set of admissible actions for the empirical distribution
$\mu$. If the ACOE exists, then the optimal value function is given by the
constant $j^{*}$. We present the following result for completeness and future
references:

######  Theorem 1.

[48] Suppose there exists
$v^{*}\in{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))$ and some constant
$j^{*}$ such that

$\displaystyle j^{*}+v^{*}(\mu)=\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}v^{*}(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)},$

we then have

  * (i)

For any initial point $\mu\in{\mathcal{P}}_{N}(\mathds{X})$, the constant
$j^{*}$ is the optimal infinite horizon average cost, that is

$\displaystyle j^{*}=K^{N,*}_{\infty}(\mu)=\inf_{g\in G}K^{N}_{\infty}(\mu,g)$

for every $\mu\in{\mathcal{P}}_{N}(\mathds{X})$.

  * (ii)

If there exists a policy $g^{*}\in G$ satisfying the ACOE, then this
stationary policy is an optimal policy for the average infinite horizon cost
problem; that is, if $g^{*}$ satisfies

$\displaystyle
j^{*}+v^{*}(\mu)=k(\mu,g^{*}(\mu))+\int_{{\mathcal{P}}_{N}(\mathds{X})}v^{*}(\mu_{1})\eta(d\mu_{1}|\mu,g^{*}(\mu))$

then $K^{N}_{\infty}(\mu,g^{*})=K_{\infty}^{N,*}(\mu)$.

Thus, if one can guarantee the existence of the ACOE (7), for the
$N$-population measure valued MDP, existence of an optimal stationary policy
for the distribution of the population can also be shown under appropriate
measurable selection conditions. We will establish the ACOE under two
different sets of assumptions. For the first case, we will assume a
minorization condition on the dynamics of the agents, which will in turn give
us a mixing type result for the state vector of all agents. For the second
case, we will assume that the cost and transition functions of the agents are
Lipschitz continuous without assuming the minorization condition.

######  Remark 1.

We note that the ACOE may not be unique; it is clear that $j^{*}$ is unique to
the problem as it is equal to the optimal value; however, there may be several
$v^{*}$ that satisfy the ACOE. In fact any shifted version of $v^{*}$, e.g.
$v^{\prime}=v^{*}+M$ for some $M<\infty$ will also satisfy the ACOE.

###  2.2 Existence of ACOE under Minorization and Geometric Ergodicity

We introduce a relative value iteration approach that converges to the ACOE in
(7). Define the operator
$T:{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))\to{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))$
such that for $v\in{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))$

$\displaystyle Tv(\mu):=\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}v(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)},$
(8)

Using this, we now define a relative operator,
$T_{0}:{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))\to{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))$,
such that for some fixed $\mu_{0}\in{\mathcal{P}}_{N}(\mathds{X})$

$\displaystyle T_{0}v(\mu):=Tv(\mu)-Tv(\mu_{0}).$ (9)

In what follows, we focus on the contraction property of the relative operator
$T_{0}$.

Recall the stochastic kernel (see (1)),
$\mathcal{T}^{w^{0}}(\cdot|x_{t}^{i},u_{t}^{i},\mu_{\bf
x_{t}})\in{\mathcal{P}}(\mathds{X})$ for the agent dynamics.

######  Assumption 1.

There exists a non-trivial measure $\pi(\cdot)\in{\mathcal{B}}(\mathds{X})$
with $\pi(\mathds{X})>0$, and there exists measurable set
$B\in{\mathcal{B}}(\mathds{W})$ with positive probability, $P(B)>0$, such that
for any $x_{t}^{i},u_{t}^{i},\mu_{\bf x_{t}}$ we have

$\displaystyle\mathcal{T}^{w^{0}}(\cdot|x_{t}^{i},u_{t}^{i},\mu_{\bf
x_{t}})\geq\pi(\cdot)$

for all $w^{0}\in B$.

######  Theorem 2.

Under Assumption 1, we have that

$\displaystyle\|T_{0}^{k}v_{0}-v^{*}\|_{\infty}\to 0$

for any $v_{0}\in{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))$ and for some
$v^{*}\in{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))$, where $T_{0}^{k}$
denotes the operator $T_{0}$ defined by (9) applied $k$-times. Furthermore,
$v^{*}$ satisfies the following ACOE

$\displaystyle j^{*}+v^{*}(\mu)=\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}v^{*}(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)}.$

###### Proof.

We define the span semi-norm for a function $f$ such that

$\displaystyle\|f\|_{sp}:=\sup_{x}f(x)-\inf_{x}f(x).$

We will show that the operator $T_{0}$ is a contraction under the span norm.

Let $f,g$ be measurable functions and
$\mu,\mu^{\prime}\in{\mathcal{P}}_{N}(\mathds{X})$. Then by the definition of
$T_{0}$, we can write:

$\displaystyle|\left(T_{0}f(\mu)-T_{0}g(\mu)\right)-\left(T_{0}f(\mu^{\prime})-T_{0}g(\mu^{\prime})\right)|$
$\displaystyle=|(Tf(\mu)-Tf(\mu_{0}))-(Tg(\mu)-Tg(\mu_{0}))-(Tf(\mu^{\prime})-Tf(\mu_{0}))+(Tg(\mu^{\prime})-Tg(\mu_{0}))|$
$\displaystyle\phantom{}=|(Tf(\mu)-Tg(\mu))-(Tf(\mu^{\prime})-Tg(\mu^{\prime}))|$
$\displaystyle=\Bigg{|}\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}f(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)}$
$\displaystyle\phantom{xxxx}-\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}g(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)}$
$\displaystyle\qquad\qquad-\Bigg{(}\inf_{\Theta\in
U(\mu^{\prime})}\bigg{(}k(\mu^{\prime},\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}f(\mu_{1})\eta(d\mu_{1}|\mu^{\prime},\Theta)\bigg{)}$
$\displaystyle\phantom{xxxxxxxxxxxxxxx}-\inf_{\Theta\in
U(\mu^{\prime})}\bigg{(}k(\mu^{\prime},\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}g(\mu_{1})\eta(d\mu_{1}|\mu^{\prime},\Theta)\bigg{)}\Bigg{)}\Bigg{|}.$

Assume now without loss of generality that the first difference is greater
than the second difference, and denote the minimizer action selections by
$\Theta^{f},\Theta^{g},\Theta^{f}_{0},\Theta_{0}^{g}$ respectively in the
order of the terms in the equation. We can then find an upper-bound as:

$\displaystyle|(Tf(\mu)-Tg(\mu))-(Tf(\mu^{\prime})-Tg(\mu^{\prime}))|$
$\displaystyle\leq\bigg{(}k(\mu,\Theta_{g})+\int_{{\mathcal{P}}_{N}(\mathds{X})}f(\mu_{1})\eta(d\mu_{1}|\mu,\Theta_{g})-k(\mu,\Theta_{g})-\int_{{\mathcal{P}}_{N}(\mathds{X})}g(\mu_{1})\eta(d\mu_{1}|\mu,\Theta_{g})\bigg{)}$
$\displaystyle-\bigg{(}k(\mu^{\prime},\Theta^{\prime}_{f})+\int_{{\mathcal{P}}_{N}(\mathds{X})}f(\mu_{1})\eta(d\mu_{1}|\mu^{\prime},\Theta^{\prime}_{f})-k(\mu^{\prime},\Theta^{\prime}_{f})-\int_{{\mathcal{P}}_{N}(\mathds{X})}g(\mu_{1})\eta(d\mu_{1}|\mu^{\prime},\Theta^{\prime}_{f})\bigg{)}$
$\displaystyle\leq\int_{{\mathcal{P}}_{N}(\mathds{X})}f(\mu_{1})-g(\mu_{1})\eta(d\mu_{1}|\mu,\Theta_{g})-\int_{{\mathcal{P}}_{N}(\mathds{X})}f(\mu_{1})-g(\mu_{1})\eta(d\mu_{1}|\mu^{\prime},\Theta^{\prime}_{f})$
(10)

For any $\mu,\mu^{\prime}\in{\mathcal{P}}_{N}(\mathds{X})$ and any $\Theta\in
U(\mu),\Theta^{\prime}\in U(\mu^{\prime})$ there exists state and action
vectors ${\bf x,x^{\prime},u,u^{\prime}}$ such that $\mu_{\bf x}=\mu,\mu_{\bf
x^{\prime}}=\mu^{\prime}$ and
$\mu_{\bf(x,u)}=\Theta,\mu_{\bf(x^{\prime},u^{\prime})}=\Theta^{\prime}$.
Furthermore, following the definition of $\eta$ (see (2)), we have that for
any $A\in{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))$

$\displaystyle\eta(A|\mu,\Theta)=Pr(\mu_{1}\in A|{\bf x,u})=Pr(\\{{\bf
x_{1}\in\mathds{X}}:\mu_{\bf x_{1}}\in A\\}|{\bf x,u})$
$\displaystyle\eta(A|\mu^{\prime},\Theta^{\prime})=Pr(\mu_{1}\in A|{\bf
x^{\prime},u^{\prime}})=Pr(\\{{\bf x_{1}\in\mathds{X}}:\mu_{\bf x_{1}}\in
A\\}|{\bf x^{\prime},u^{\prime}}).$ (11)

Note that $\mathds{X}^{N}$ and $\mathds{U}^{N}$ are equipped with the product
topology, and the vector state process ${\bf x}_{t}\in\mathds{X}^{N}$ is also
a controlled Markov chain, where the control variables are ${\bf
u}_{t}\in\mathds{U}^{N}$ are simply the action vector variables. We write the
transition kernel of the vector state process as $P({\bf x}_{t+1}\in\cdot|{\bf
x_{t},u_{t}})$.

Consider $\pi(\cdot)\in{\mathcal{P}}(\mathds{X})$ from Assumption 1, we define
the product measure $\pi^{N}(\cdot)\in{\mathcal{P}}(\mathds{X}^{N})$ using
$\pi(\cdot)$, that is, for any rectangular set $E=E_{1}\times\dots\times
E_{N}$ where $E_{1},\dots,E_{N}\subset\mathds{X}$, we have that

$\displaystyle\pi^{N}(E)=\pi(E_{1})\times\dots\times\pi(E_{N}).$

Furthermore, using the conditional independence of the agent states, $x^{j}$
for $j=1,\dots,N$, given ${\bf x,u}$ (or given $x^{j},u^{j},\mu_{\bf x}$), and
given the common noise realization we can also write that

$\displaystyle P({\bf x_{1}}\in E|{\bf
x,u})=\int\prod_{j=1}^{N}\mathcal{T}^{w^{0}}(x^{j}_{1}\in
E_{j}|x^{j},u^{j},\mu_{\bf x})P(dw^{0})$

Consider a general measurable set $A\in{\mathcal{B}}(\mathds{X}^{N})$, which
can be written as a countable union of disjoint rectangular sets, say
$\\{E^{i}\\}_{i}$, such that $\cup_{i}E^{i}=A$. We can then write

$\displaystyle P({\bf x_{1}}\in A|{\bf x,u})$
$\displaystyle=\sum_{i}P(E^{i}|{\bf
x,u})=\sum_{i}\int\prod_{j=1}^{N}\mathcal{T}^{w^{0}}(E^{i}_{j}|x^{j},u^{j},\mu_{\bf
x})P(dw^{0})$
$\displaystyle\geq\sum_{i}\prod_{j=1}^{N}\pi(E^{i}_{j})P(B)=P(B)\sum_{i}\pi^{N}(E^{i})=P(B)\pi^{N}(A).$

Note that by construction, $\pi^{N}(\cdot)$ is a non-trivial measure, and
furthermore, $\pi^{N}(\mathds{X}^{N})=\pi(\mathds{X})^{N}<1$. We denote by
$\hat{P}(\cdot|{\bf x,u}):=P(\cdot|{\bf x,u})-P(B)\pi^{N}(\cdot)$. Going back
to (2.2) and denoting $h(\mu):=f(\mu)-g(\mu)$, we write

$\displaystyle\int_{{\mathcal{P}}_{N}(\mathds{X})}f(\mu_{1})-g(\mu_{1})\eta(d\mu_{1}|\mu,\Theta_{g})-\int_{{\mathcal{P}}_{N}(\mathds{X})}f(\mu_{1})-g(\mu_{1})\eta(d\mu_{1}|\mu^{\prime},\Theta^{\prime}_{f})$
$\displaystyle=\int h(\mu_{\bf x_{1}})P(d{\bf x_{1}}|{\bf x,u_{g}})-\int
h(\mu_{\bf x_{1}})P(d\bf{x_{1}}|{\bf x^{\prime},u^{\prime}_{f}})$
$\displaystyle=\int h(\mu_{\bf x_{1}})\hat{P}(d{\bf x_{1}}|{\bf x,u_{g}})-\int
h(\mu_{\bf x_{1}})\hat{P}(d\bf{x_{1}}|{\bf x^{\prime},u^{\prime}_{f}})$
$\displaystyle\leq\sup_{\mu}h(\mu)\hat{P}(\mathds{X}^{N}|{\bf
x,u_{g}})-\inf_{\mu}h(\mu)\hat{P}(\mathds{X}^{N}|{\bf
x^{\prime},u^{\prime}_{f}})$
$\displaystyle\leq\|f-g\|_{sp}\left(1-P(B)\pi^{N}(\mathds{X}^{N})\right).$

Since $\mu,\mu^{\prime}$ are arbitrary, this shows that $T_{0}$ is a
contraction under the span norm. Hence, there exists a $v^{*}$ such that
$\|T_{0}v^{*}-v^{*}\|_{sp}=0$. Equivalently, there exists some constant $C$,
such that $T_{0}v^{*}(\mu)-v^{*}(\mu)=C$ for all $\mu$. We can also write this
as

$\displaystyle v^{*}(\mu)=$ $\displaystyle\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}v(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)}$
$\displaystyle-\inf_{\Theta\in
U(\mu_{0})}\bigg{(}k(\mu_{0},\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}v(\mu_{1})\eta(d\mu_{1}|\mu_{0},\Theta)\bigg{)}+C.$

Note that $T_{0}$ is constructed so that $T_{0}^{k}v(\mu_{0})=0$ for all $k$.
Hence, the fixed point also satisfies $v^{*}(\mu_{0})=0$. For the above
equation, we then must have that $C=0$. Therefore, among the span-norm
equivalent set of functions that $T_{0}^{k}$ converges to under the span semi-
norm, for the one with $v^{*}(\mu_{0})=0$, we have convergence under the
uniform norm as well. That is $\|T_{0}^{k}v_{0}-v^{*}\|_{\infty}\to 0$, for
any $v_{0}\in{\mathcal{B}}({\mathcal{P}}_{n}(\mathds{X}))$, such that
$v^{*}(\mu_{0})=0$ and it satisfies the following

$\displaystyle v^{*}(\mu)=$ $\displaystyle\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}v(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)}$
$\displaystyle-\inf_{\Theta\in
U(\mu_{0})}\bigg{(}k(\mu_{0},\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}v(\mu_{1})\eta(d\mu_{1}|\mu_{0},\Theta)\bigg{)}$

which is in the form of ACOE with

$\displaystyle j^{*}=\inf_{\Theta\in
U(\mu_{0})}\bigg{(}k(\mu_{0},\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}v(\mu_{1})\eta(d\mu_{1}|\mu_{0},\Theta)\bigg{)}$

∎

######  Remark 2.

Assumption 1 requires that under a set of positive probability on the common
noise, an agent can go to a subset of the state space $\mathds{X}$, with
positive probability decided by the measure $\pi$ no matter what the current
state, action, and the empirical measure are. Note that $\pi$ does not have to
be a probability measure. However, if $\pi(\mathds{X})<1$, then the
contraction constant ${1-P(B)\pi(\mathds{X})^{N}}$ we use in the proof goes to
$1$ as $N$ grows. This suggests that for large (or infinite) populations,
Theorem 2 no longer has a useful conclusion. One way to avoid this problem is
to require $\pi$ to be a probability measure. In other words, if there exists
a measurable set $B\in{\mathcal{B}}(\mathds{W})$ with positive probability,
$P(B)>0$, such that for any $x_{t}^{i},u_{t}^{i},\mu_{\bf x_{t}}$ we have

$\displaystyle\mathcal{T}^{w^{0}}(\cdot|x_{t}^{i},u_{t}^{i},\mu_{\bf
x_{t}})=\pi(\cdot)$

where $\pi$ is a probability measure, then Theorem 2 will still provide a
contraction constant, uniform over the population $N$. This condition can be
thought of as resetting the distribution of every agent to $\pi$ under certain
common noise realizations. This is clearly a strong assumption, and maybe an
artificial one. Thus, in the following we will use a different set of
assumptions.

######  Remark 3.

Assumption 1, we use in this section, is also a sufficient condition for
geometric ergodicity of the vector state process of the team under stationary
policies. Consider two team state processes under the same policy $\gamma$,
denote by $\pi_{t}^{\gamma}\in{\mathcal{P}}(\mathds{X}^{N})$ and
$\hat{\pi}_{t}^{\gamma}\in{\mathcal{P}}(\mathds{X}^{N})$ the marginal
distributions of the state vectors at time $t$. One can show that under
Assumption 1

$\displaystyle\|\pi_{t+1}^{\gamma}-\hat{\pi}_{t+1}^{\gamma}\|_{TV}\leq\alpha\|\pi_{t+1}^{\gamma}-\hat{\pi}_{t+1}^{\gamma}\|_{TV}$
(12)

where $\alpha=(1-P(B)\pi(\mathds{X})^{N})<1$. In particular, one can use this
relation to show that $\pi_{t}^{\gamma}$ is a Cauchy sequence, and thus
converges to some $\pi^{\gamma}$ under total variation metric, since
${\mathcal{P}}(\mathds{X}^{N})$ is complete under total variation. The limit
point $\pi^{\gamma}$ is the invariant measure of the vector state process
under the stationary team policy $\gamma$. Furthermore, using (12), one can
also show that for any starting distribution of agents

$\displaystyle\|\pi^{\gamma}_{t+1}-\pi^{\gamma}\|_{TV}\leq 2\alpha^{t}$

with $\alpha=(1-P(B)\pi(\mathds{X})^{N})<1$. Therefore, Assumption 1 implies
the geometric ergodicity of the vector state process of the team.

###  2.3 Existence of ACOE and Optimal Policies under Continuity of Transition
and Cost Functions

We have shown the existence of the ACOE and thus the existence of optimal
stationary Markov policies under a minorization condition for the dynamics of
the agents. However, we have also observed that this approach may fail when
the number of agents is large.

In this section, we will show that the ACOE can be established using the
vanishing discount approach under the assumption that the transition and cost
functions of the agents are Lipschitz continuous. Furthermore, the approach
presented in this section will be valid for large populations, and in
particular for the infinite population as we will see later.

######  Assumption 2.

  * i.

$\mathds{X}$ and $\mathds{U}$ are compact.

  * ii.

$f$ is Lipschitz in $x,u,\mu$ such that

$\displaystyle|f(x,u,\mu,w^{i},w^{0})-f(x^{\prime},u^{\prime},\mu^{\prime},w^{i},w^{0})|\leq
K_{f}\left(|x-x^{\prime}|+|u-u^{\prime}|+W_{1}(\mu,\mu^{\prime})\right)$

for some $2K_{f}<1$, uniformly in $w^{i},w^{0}$ where $W_{1}$ is the first
order Wasserstein distance.

  * iii.

$c$ is Lipschitz in $x,u,\mu$ such that

$\displaystyle|c(x,u,\mu)-c(x^{\prime},u^{\prime},\mu^{\prime})|\leq
K_{c}\left(|x-x^{\prime}|+|u-u^{\prime}|+W_{1}(\mu,\mu^{\prime})\right)$

for some $K_{c}<\infty$.

######  Theorem 3.

Under Assumption 2, there exists a constant $j^{*}$, and a function
$h\in{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))$, such that

$\displaystyle j^{*}+h(\mu)=\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\int_{{\mathcal{P}}_{N}(\mathds{X})}h(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)}.$

Furthermore, there exists a stationary and Markov policy $g$ which arrives the
infimum at the right hand side.

###### Proof.

We start by analyzing the discounted cost criteria. Let

$\displaystyle
K_{\beta}^{N}(\mu,g)=\sum_{t=0}^{\infty}\beta^{t}E_{\mu}^{g}\left[k(\mu_{t},\Theta_{t})\right]$

be the discounted cost under some policy $g$ where $0<\beta<1$ is some
discount factor. Furthermore, let $K_{\beta}^{N,*}(\mu)$ denote the optimal
discounted cost function for the initial agent distribution
$\mu\in{\mathcal{P}}_{N}(\mathds{X})$.

We define the following relative discounted value function, for some fixed
$\mu^{\prime}\in{\mathcal{P}}_{N}(\mathds{X})$:

$\displaystyle
h_{\beta}^{N}(\mu):=K^{N,*}_{\beta}(\mu)-K^{N,*}_{\beta}(\mu^{\prime}).$

Using the Bellman equation for $K^{N,*}_{\beta}(\mu)$ and by rearranging some
terms, one can write that

$\displaystyle K^{N,*}_{\beta}(\mu)-K^{N,*}_{\beta}(\mu^{\prime})$
$\displaystyle=\inf_{\Theta\in U(\mu)}\bigg{(}k(\mu,\Theta)$
$\displaystyle+\beta\int\left(K_{\beta}^{N,*}(\mu_{1})-K^{N,*}_{\beta}(\mu^{\prime})\right)\eta(d\mu_{1}|\mu,\Theta)-(1-\beta)K^{N,*}_{\beta}(\mu^{\prime})\bigg{)}.$

Using the definition $h_{\beta}^{N}$ function, we can also write that

$\displaystyle h_{\beta}^{N}(\mu)=\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\beta\int
h_{\beta}^{N}(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)-(1-\beta)K^{N,*}_{\beta}(\mu^{\prime})\bigg{)}$
(13)

Next, we will show that $h_{\beta}^{N}$ is uniformly bounded and
equicontinuous (over $\beta$) when we metrize ${\mathcal{P}}_{N}(\mathds{X})$
with the first order Wasserstein distance. Thus we can invoke the Arzela-
Ascoli theorem since ${\mathcal{P}}_{N}(\mathds{X})$ is complete and separable
under the Wassertein metric.

For the boundedness:

$\displaystyle
h_{\beta}^{N}(\mu)=K^{N,*}_{\beta}(\mu)-K^{N,*}_{\beta}(\mu^{\prime})\leq\frac{2K_{c}}{1-2K_{f}\beta}W_{1}(\mu,\mu^{\prime})$

where we used [24, Lemma 4] for the last step. Furthermore, since we assume
that $\mathds{X}$ is compact (and bounded), $W_{1}(\mu,\mu^{\prime})$ is
uniformly bounded as well. Hence, $h_{\beta}^{N}(\mu)$ is uniformly bounded
over $\beta$ when $2K_{f}<1$.

For equicontinuity, similarly, for some $\mu,\hat{\mu}$ we write

$\displaystyle
h_{\beta}^{N}(\mu)-h_{\beta}^{N}(\hat{\mu})=K^{N,*}_{\beta}(\mu)-K^{N,*}_{\beta}(\mu^{\prime})-K^{N,*}_{\beta}(\hat{\mu})+K^{N,*}_{\beta}(\mu^{\prime})\leq\frac{2K_{c}}{1-2K_{f}\beta}W_{1}(\mu,\hat{\mu})$
(14)

which proves that $h_{\beta}^{N}(\mu)$ is equicontinuous over $\beta$ if
$2K_{f}<1$, as the bound becomes uniform over $\beta$.

Furthermore, the stage-wise cost function is uniformly bounded as $c$ is
continuous and $\mathds{X}$ is compact. Hence, for the fixed $\mu^{\prime}$,
$(1-\beta)K^{N,*}_{\beta(k)}(\mu^{\prime})$ is a bounded sequence over
$\beta$. Thus, there exists a sequence of discount factors, say $\beta(k)\to
1$, such that, $(1-\beta(k))K_{\beta(k)}^{N,*}(\mu^{\prime})\to j^{*}$ for
some constant $j^{*}$. If we consider some other
$\mu\in{\mathcal{P}}_{N}(\mathds{X})$, we can also show that

$\displaystyle|(1-\beta(k))K_{\beta(k)}^{N,*}(\mu)-j^{*}|$
$\displaystyle\leq|(1-\beta(k))K_{\beta(k)}^{N,*}(\mu)-(1-\beta(k))K_{\beta(k)}^{N,*}(\mu^{\prime})|+|(1-\beta(k))K_{\beta(k)}^{N,*}(\mu^{\prime})-j^{*}|$
$\displaystyle\leq(1-\beta(k))\left|h^{N}_{\beta(k)}(\mu)\right|+|(1-\beta(k))K_{\beta(k)}^{N,*}(\mu^{\prime})-j^{*}|\to
0$

where we used the boundedness of $h_{\beta}^{N}$ and the fact that along the
sequence $\beta(k)$, $|(1-\beta(k))K_{\beta(k)}^{N,*}(\mu^{\prime})-j^{*}|\to
0$. Hence, not only for the fixed $\mu^{\prime}$ but for all
$\mu\in{\mathcal{P}}_{N}(\mathds{X})$, we have that
$|(1-\beta(k))K_{\beta(k)}^{N,*}(\mu)-j^{*}|\to 0$.

We have shown that $h_{\beta}^{N}$ is equicontinuous, hence there exists a
further subsequence, say $\beta(k^{\prime})$, such that
$h^{N}_{\beta(k^{\prime})}\to h$ uniformly, for some continuous function $h$,
using the Arzela-Ascoli Theorem. If we take the limit of both sides in (13)
along $\beta(k^{\prime})$, we can see

$\displaystyle h(\mu)=\lim_{k^{\prime}\to\infty}\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\beta(k^{\prime})\int
h_{\beta(k^{\prime})}^{N}(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)}-j^{*}$

One can also justify the exchange of infimum and the limit using the
equicontinuity of $h_{\beta}^{N}$, compactness of $\mathds{X}$, and thus the
weakly pre-compactness of ${\mathcal{P}}_{N}(\mathds{X})$, see [49, Theorem
7.3.3], once we exchange the limit and the infimum, we get

$\displaystyle h(\mu)=\inf_{\Theta\in U(\mu)}\bigg{(}k(\mu,\Theta)+\int
h(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)}-j^{*}$

which proves the first part. The second part follows as the measurable
conditions are satisfied, since the limit function $h_{\beta}^{N}$, and the
cost function $k$ are continuous, $\eta$ is weakly continuous and the action
set $U(\mu)$ is compact and can be shown to be lower continuous under
Assumption 2. ∎

###  2.4 Relative Value Iteration Convergence under Continuity of Transition
and Cost Functions

The relative value iterations we have provided in Section 2.2 have been shown
to converge under the minorization condition Assumption 1 with a convergence
rate. We have used the contraction property of the relative value operator
$T_{0}$ (see (9)) to prove the convergence. However, the contraction constant
tends to $1$, as the number of agents grows.

In this section, we will show the convergence of the relative value iterations
under Assumption 2 without using the contraction arguments. The value
iterations can be used to approximate the relative value functions, $h$, that
satisfy the ACOE and thus can be used the compute the optimal policies.

Recall the relative value iterations: We first fix a state
$\mu_{0}\in{\mathcal{P}}_{N}(\mathds{X})$, and we define the following
operator (see also (8)), for any measurable function $v$:

$\displaystyle Tv(\mu)=\inf_{\Theta\in U(\mu)}\left\\{k(\mu,\Theta)+\int
v(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\right\\}.$

Using this operator, we define the following relative value iteration operator
(see also (9))

$\displaystyle T_{0}v(\mu):=Tv(\mu)-Tv(\mu_{0}).$

######  Theorem 4.

Let

$\displaystyle v_{t}(\mu):=T_{0}^{t}v_{0}(\mu)$

where the initial estimate is $v_{0}(\mu):=\inf_{\Theta}k(\mu,\Theta)$. Under
Assumption 2,

$\displaystyle v_{t}(\mu)\to h(\mu)$

uniformly for $\mu\in{\mathcal{P}}_{N}(\mathds{X})$ for some measurable $h$.
Furthermore, $h$ satisfies the ACOE, i.e.

$\displaystyle h(\mu)+j^{*}=\inf_{\Theta\in U(\mu)}\left\\{k(\mu,\Theta)+\int
h(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\right\\}.$

Thus, one can compute the optimal policy by finding the selector of the right
hand side.

###### Proof.

We start by defining the finite $t$-horizon discounted optimal cost and denote
it by $K_{\beta}^{N,t}$. We now show that $\|K_{\beta}^{N,t}\|_{Lip}\leq
2K_{c}\sum_{i=0}^{t}(2\beta K_{f})^{i}$. We prove this by induction: for
$t=0$, we have that $K_{\beta}^{N,0}(\mu)=\inf_{\Theta}k(\mu,\Theta)$, and
thus we can write for any $\mu,\mu^{\prime}\in{\mathcal{P}}_{N}(\mathds{X})$:

$\displaystyle\left|K_{\beta}^{N,0}(\mu)-K_{\beta}^{N,0}(\mu^{\prime})\right|=|k(\mu,\Theta)-k(\mu^{\prime},\Theta^{\prime})|$

where $\Theta$ and $\Theta^{\prime}$ are the selectors for $\mu$ and
$\mu^{\prime}$. Depending on which cost is bigger, the team actions can be
alternated to get a greater upper bound, i.e. we can write that

$\displaystyle\left|K_{\beta}^{N,0}(\mu)-K_{\beta}^{N,0}(\mu^{\prime})\right|\leq\sup_{\bf
u}|k(\mu,\Theta_{\bf x,u})-k(\mu^{\prime},\Theta_{\bf x^{\prime},u})|$

where ${\bf x}$ and ${\bf x^{\prime}}$ some team state vectors that have
distributions $\mu$ and $\mu^{\prime}$. One can show that (see [24, Lemma 3])

$\displaystyle|k(\mu,\Theta_{\bf x,u})-k(\mu^{\prime},\Theta_{\bf
x^{\prime},u})|\leq 2K_{c}W_{1}(\mu,\mu^{\prime})$

which proves the initial step of the induction. We now assume the result holds
for $t$, and show that it holds for $t+1$ as well. Using the dynamic
programming principle, we write

$\displaystyle
K_{\beta}^{N,t+1}(\mu)=\inf_{\Theta}\left\\{k(\mu,\Theta)+\beta\int
K_{\beta}^{N,t}(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\right\\}$ $\displaystyle
K_{\beta}^{N,t+1}(\mu^{\prime})=\inf_{\Theta}\left\\{k(\mu^{\prime},\Theta)+\beta\int
K_{\beta}^{N,t}(\mu_{1})\eta(d\mu_{1}|\mu^{\prime},\Theta)\right\\}$

using the action exchange, we can again write that

$\displaystyle\left|K_{\beta}^{N,t+1}(\mu)-K_{\beta}^{N,t+1}(\mu^{\prime})\right|\leq$
$\displaystyle\sup_{\bf u}|k(\mu,\Theta_{\bf x,u})-k(\mu^{\prime},\Theta_{\bf
x^{\prime},u})|$ $\displaystyle+\beta\int
K_{\beta}^{N,t}(\mu_{1})\eta(d\mu_{1}|\mu,\Theta_{\bf x,u})-\beta\int
K_{\beta}^{N,t}(\mu_{1})\eta(d\mu_{1}|\mu^{\prime},\Theta_{\bf x^{\prime},u})$
$\displaystyle\leq
2K_{c}W_{1}(\mu,\mu^{\prime})+\beta\|K_{\beta}^{N,t}\|_{Lip}W_{1}(\eta(d\mu_{1}|\mu^{\prime},\Theta_{\bf
x,u}),\eta(d\mu_{1}|\mu^{\prime},\Theta_{\bf x^{\prime},u}))$

Noting that $W_{1}(\eta(d\mu_{1}|\mu^{\prime},\Theta_{\bf
x,u}),\eta(d\mu_{1}|\mu^{\prime},\Theta_{\bf x^{\prime},u}))\leq
2K_{f}W_{1}(\mu,\mu^{\prime})$ (see [24, Lemma 3]) and using the induction
step proves the claim that $\|K_{\beta}^{N,t}\|_{Lip}\leq
2K_{c}\sum_{i=0}^{t}(2\beta K_{f})^{i}$.

Hence, if we define

$h_{\beta}^{N,t}(\mu):=K_{\beta}^{N,t}(\mu)-K_{\beta}^{N,t}(\mu_{0}),$

we have that

$\displaystyle h_{\beta}^{N,t}(\mu)\leq 2K_{c}\sum_{i=0}^{t}(2\beta
K_{f})^{i}W_{1}(\mu,\mu_{0})\leq 2K_{c}\frac{1}{1-2K_{f}}W_{1}(\mu,\mu_{0})$

where the last bound is valid uniformly for all $\beta$ and $t$ as we assume
$2K_{f}<1$. Since $\mathds{X}$ is assumed to be compact, we can conclude that
$h_{\beta}^{N,t}(\mu)$ is uniformly bounded. Similarly, we can show that

$\displaystyle h_{\beta}^{N,t}(\mu)-h_{\beta}^{N,t}(\mu^{\prime})\leq
2K_{c}\sum_{i=0}^{t}(2\beta K_{f})^{i}W_{1}(\mu,\mu^{\prime})\leq
2K_{c}\frac{1}{1-2K_{f}}W_{1}(\mu,\mu^{\prime})$ (15)

which shows that $h_{\beta}^{N,t}(\mu)$ is equicontinuous over $\beta$ and
$t$.

Recall that the relative value functions that satisfy the ACOE may not be
unique, even up to a constant. Hence, for the proof, we will work with a
particular relative value function $h$, that we have used in Theorem 3, i.e.
the relative value function $h$ we use in the proof, is the limit of a
convergent subsequence of
$h^{N}_{\beta}(\mu):=K_{\beta}^{N,*}(\mu)-K_{\beta}^{N,*}(\mu_{0})$.

We will show that for the particular $h$ that satisfies the ACOE constructed
in Theorem 3, we have $\|v_{t}-h\|_{\infty}\to 0$. We start by assuming that
it is not true and that for any given $\epsilon>0$, there exists some
subsequence $t(m)$, such that $\|v_{t(m)}-h\|_{\infty}>\epsilon$ for all $m$.

If we consider the fixed sequence $t(m)$, and pick some sequence $\beta(m)\to
1$, we can find a subsequence say $t(m^{\prime})$ and $\beta(m^{\prime})$ such
that

$\displaystyle h_{\beta(m^{\prime})}^{N,t(m^{\prime})}\to g$

for some continuous function $g$ along $m^{\prime}$ using the Arzela-Ascoli
theorem since $h_{\beta}^{N,t}$ is equicontinuous and uniformly bounded over
$\beta$ and $t$. Hence, for some fixed $\epsilon>0$, we can find some
$M<\infty$ such that for all $m^{\prime}>M$, we have

$\displaystyle\|h_{\beta(m^{\prime})}^{N,t(m^{\prime})}-g\|_{\infty}\leq\epsilon.$

Note that $\lim_{t\to\infty}h_{\beta}^{N,t}(\mu)=h^{N}_{\beta}(\mu)$ uniformly
over $\mu$, along any sequence $t\to\infty$. We then have for any
$m^{\prime}>M$

$\displaystyle\epsilon\geq\lim_{n^{\prime}\to\infty}\|h_{\beta(m^{\prime})}^{N,t(n^{\prime})}-g\|_{\infty}=\|h^{N}_{\beta(m^{\prime})}-g\|_{\infty},$

which implies that

$\displaystyle\lim_{m^{\prime}\to\infty}h^{N}_{\beta(m^{\prime})}=g$

uniformly over $\mu$ as well. Hence $g\equiv h$.

Similarly, we have $\lim_{\beta\to
1}h_{\beta}^{N,t}(\mu)=K_{t}^{N}(\mu)-K_{t}^{N}(\mu_{0})=T_{0}^{t}v_{0}(\mu)=v_{t}(\mu)$
uniformly over $\mu$ where $K_{t}^{N}(\mu)$ is the optimal $t$-horizon
undiscounted cost. Thus, using identical arguments, we can also show that

$\displaystyle v_{t(m^{\prime})}\to h$

which contradicts our initial assumption since $v_{t(m^{\prime})}$ is a
subsequence of $v_{t(m)}$, and hence proves the result.

∎

##  3 Ergodic Control of Mean Field Limit Problem

In Section 2, we have focused on solutions to the problem of a finite
population team, for which the resulting policy is a mapping
$g:{\mathcal{P}}_{N}(\mathds{X})\to{\mathcal{P}}_{N}(\mathds{X}\times\mathds{U})$.
In other words, the policy provides a distribution rule for the joint state-
action of the agents, by looking at the state distribution of the agents. Note
that this policy is a recipe for the team, however, to apply this policy at
the agent level, one needs to coordinate the agents in order to realize the
recipe state-action distribution. For example, if the distribution of the
agents is given by $\mu\in{\mathcal{P}}_{N}(\mathds{X})$, and the optimal
action is given by
$\Theta(du,dx)\in{\mathcal{P}}_{N}(\mathds{U}\times\mathds{X})$, then
$\Theta(du,dx)$ serves as a recipe for the team of agents. The agents need to
coordinate to create this joint distribution among each other. In particular,
every agent may be required to apply different, asymmetric policies, even if
their states are the same, i.e. the agent level policies might depend on the
identity of the agents. It might be the case for example, two agents $i\neq j$
with same state $x^{i}=x^{j}$, might need to apply different policies
$\gamma^{i}(\cdot|x^{i},\mu_{\bf x}),\gamma^{j}(\cdot|x^{j},\mu_{\bf x})$.
Asymmetric policies, especially for the large number of agents, can be hard to
coordinate.

To deal with this coordination challenge, the usual approach is to consider
the infinite population problem. The infinite population problem which we will
introduce in this section, provides a policy, say
$g:{\mathcal{P}}(\mathds{X})\to{\mathcal{P}}(\mathds{X}\times\mathds{U})$,
that maps the marginal distribution of a representative agent to a joint
state-action measure. For example, if the state is
$\mu\in{\mathcal{P}}(\mathds{X})$, and the recipe action is some
$\Theta(dx,du)\in{\mathcal{P}}(\mathds{X}\times\mathds{U})$, then by
disintegrating, $\Theta(dx,du)=\gamma(du|x,\mu)\mu(dx)$, every agent can apply
the agent level symmetric policy $\gamma(\cdot|x,\mu)$, which solves the
coordination challenge.

In this section, we consider the control problem for the infinite population
of agents, i.e. for $N\to\infty$. We will first provide a control problem for
a single agent, and formulate it as a controlled measure valued Markov
process.

###  3.1 Infinite Population Measure Valued Control Problem

We present a control problem for the measure process $\mu_{t}$, by changing
the control variables as well. We will let the control actions be the joint
measures on $\mathds{X}\times\mathds{U}$. Let
$\Theta_{t}\in{\mathcal{P}}(\mathds{X}\times\mathds{U})$ such that the first
marginal of $\Theta_{t}$ agrees with the state distribution of the agent
$\mu_{t}$. We define the stage-wise cost function $k(\mu_{t},\Theta_{t})$
similar to the finite population measure valued MDP construction so that

$\displaystyle k(\mu_{t},\Theta_{t}):=\int c(x,u,\mu_{t})\Theta(dx,du).$

An admissible policy $g=\\{g_{t}\\}$ is a sequence of control functions such
that each can use the information variables
$\\{\mu_{0},\dots,\mu_{t},\Theta_{0},\dots,\Theta_{t-1}\\}$. Let $G$ be the
set of all admissible policies for the measure valued process.

Recall the transition kernel $\mathcal{T}^{w^{0}}(\cdot|x,u,\mu)$ defined in
(1), which defines a probability measure on $\mathds{X}$ given the last state,
action, and measure variables $(x,u,\mu)$ and the common noise $w^{0}$. We can
define the dynamics of the measure process $\mu_{t}$ using
$\mathcal{T}^{w^{0}}$ so that

$\displaystyle\mu_{t+1}(\cdot)=F(\mu_{t},\Theta_{t},w^{0}):=\int\mathcal{T}^{w^{0}}(\cdot|x,u,\mu_{t})\Theta(dx,du).$

Note that the dynamics can also represented using a Markov kernel, which we
will denote by

$\eta(d\mu_{t+1}|\mu_{t},\Theta_{t})$

by an abuse of notation; recall that we have used the same notation to denote
the transition kernel of the finite population measure valued MDP (see (2)).
Even though these transition kernels are totally different we use the same
notation for simplicity.

We define the cost function to be minimized as

$\displaystyle
K_{\infty}(\mu,g)=\limsup_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}E_{\mu}^{g}\left[k(\mu_{t},\Theta_{t})\right]$

where $\mu=\mu_{0}$.

We denote the optimal cost function by $K^{*}_{\infty}(\mu)$ such that

$\displaystyle K^{*}_{\infty}(\mu)=\inf_{g\in G}K_{\infty}(\mu,g).$

######  Remark 4.

We note that even though the infinite population problem can be structured as
a classical single agent MDP problem, the standard tools used to study the
average cost optimality criteria for MDPs may not be directly applicable. The
standard methods (see e.g. [50, 51, 52]) requires certain ergodicity
conditions on the controlled state process, as well as mixing type conditions
of the state process under total variation norm, e.g. conditions similar to
Assumption 1. These conditions may be easy to verify for state variables
living in general Euclidean state spaces, e.g. for the finite population
problem as we have seen in Section 2.2. However, for the measure valued
controlled process we have introduced in this section for the infinite
population problem, these conditions are not applicable unless we assume very
strong conditions on the system dynamics. For example, a slightly weaker
version of Assumption 1 requires that

$\displaystyle\|\eta(\cdot|\mu,\Theta)-\eta(\cdot|\mu^{\prime},\Theta^{\prime})\|_{TV}\leq
2\alpha$ (16)

for some $\alpha<1$. If we assume for simplicity that there is no common noise
and consider the infinite population measure valued process, this will always
fail, since the process becomes deterministic, and in particular we get
$\|\eta(\cdot|\mu,\Theta)-\eta(\cdot|\mu^{\prime},\Theta^{\prime})\|_{TV}=2$
for any $\mu,\mu^{\prime},\Theta,\Theta^{\prime}$. In particular, most of the
tools developed to study MDPs under average cost criteria fail for
deterministic systems. With the presence of common noise, the dynamics becomes
stochastic again, however, verifying the standard average cost criteria
assumptions is not immediate. For example, as we have observed in Remark 2, in
order to verify (16) for infinite population dynamics, a sufficient condition
is that there exists a measurable set $B\in{\mathcal{B}}(\mathds{W})$ with
positive probability, $P(B)>0$, such that for any $x,u,\mu$ we have

$\displaystyle\mathcal{T}^{w^{0}}(\cdot|x,u,\mu)=\pi(\cdot)$

where $\pi$ is a probability measure. In words, there exists a set of common
noise realizations which resets the measure flow to some
$\pi(\cdot)\in{\mathcal{P}}(\mathds{X})$. Obviously, this is a very
restrictive assumption, and thus, in what follows, we use different tools to
study the average cost optimality.

###  3.2 Existence of ACOE and Optimal Policies under Continuity of Transition
and Cost Functions

We will first analyze the optimality problem, and establish the existence of
stationary Markov optimal policies for the infinite population problem as in
the finite population problem. We follow the same steps in Section 2.3 and
establish a result parallel to Theorem 3. As before, we will use the vanishing
discount approach. Let

$\displaystyle
K_{\beta}(\mu,g)=\sum_{t=0}^{\infty}\beta^{t}E_{\mu}^{g}\left[k(\mu_{t},\Theta_{t})\right]$

where $0<\beta<1$ is some discount factor. Furthermore, let
$K_{\beta}^{*}(\mu)$ denote the optimal discounted cost function.

We define the following relative discounted value function, for some fixed
$\mu^{\prime}\in{\mathcal{P}}(\mathds{X})$:

$\displaystyle
h_{\beta}(\mu):=K^{*}_{\beta}(\mu)-K^{*}_{\beta}(\mu^{\prime}).$

######  Theorem 5.

Under Assumption 2, there exists a constant $j^{*}$, and a function
$v^{*}\in{\mathcal{B}}({\mathcal{P}}_{N}(\mathds{X}))$, such that

$\displaystyle j^{*}+v^{*}(\mu)=\inf_{\Theta\in
U(\mu)}\bigg{(}k(\mu,\Theta)+\int_{{\mathcal{P}}(\mathds{X})}v^{*}(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\bigg{)}.$

Furthermore, there exists a stationary and Markov policy $g$ which arrives the
infimum at the right hand side.

###### Proof.

As in the proof of Theorem 3, we define the relative discounted value function
for some fixed $\mu^{\prime}\in{\mathcal{P}}(\mathds{X})$:

$\displaystyle h_{\beta}(\mu)=K_{\beta}^{*}(\mu)-K_{\beta}^{*}(\mu^{\prime}).$

A careful look at the proof of Theorem 3 shows that it is sufficient to show
$h_{\beta}$ is uniformly bounded and equicontinuous over $\beta\in(0,1)$.

For $h_{\beta}$, we have that

$\displaystyle
h_{\beta}(\mu)=K_{\beta}^{*}(\mu)-K_{\beta}^{*}(\mu^{\prime})\leq$
$\displaystyle\lim_{N\to\infty}E\left[\left|K_{\beta}^{*}(\mu)-K_{\beta}^{N,*}(\mu^{N})\right]\right|+E\left[\left|K_{\beta}^{N,*}(\mu^{N})-K_{\beta}^{N,*}(\mu^{N^{\prime}})\right|\right]$
$\displaystyle+E\left[\left|K_{\beta}^{N,*}(\mu^{N^{\prime}})-K_{\beta}^{*}(\mu^{\prime})\right|\right]$
$\displaystyle\leq\frac{2K_{c}}{1-2K_{f}\beta}W_{1}(\mu,\mu^{{}^{\prime}})$
(17)

where $\mu^{N}$ and $\mu^{N^{\prime}}$ are empirical distributions for $N$
agents under $\mu$ and $\mu^{\prime}$, and the expectation is taken according
to their randomness. Taking the limit $N\to\infty$, the first and last terms
go to $0$ by [47, 30] under Assumption 2, and the middle term is bounded by
$\frac{2K_{c}}{1-2K_{f}\beta}W_{1}(\mu^{N},\mu^{N,^{\prime}})$ as we have
shown in (14). Hence, we have uniform boundedness together with compactness of
$\mathds{X}$. For the equicontinuity one can follow the same steps.

For the second part of the result, we have that the measurable selections
conditions holds under Assumption 2, as the cost function $k(\mu,\Theta)$ is
continuous in both variables, and the transition kernel
$\eta(\cdot|\mu,\Theta)$ is weakly continuous in both variables, furthermore
$U(\mu)$ is compact and lower-semi continuous. Therefore, the proof is
complete. ∎

###  3.3 A Relative Value Iteration Algorithm under Continuity of Cost and
Transition Functions

In this section, we will provide a convergent relative value function
algorithm. Thus, it can be used the compute the optimal policies for the
infinite population problem.

We first fix a state $\mu_{0}\in{\mathcal{P}}(\mathds{X})$, and we define the
following operator (see also (8)), for any measurable function $v$:

$\displaystyle Tv(\mu)=\inf_{\Theta\in U(\mu)}\left\\{k(\mu,\Theta)+\int
v(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\right\\}$

Using this operator, we define the following relative value iteration operator
(see also (9))

$\displaystyle T_{0}v(\mu):=Tv(\mu)-Tv(\mu_{0})$

######  Theorem 6.

Let

$\displaystyle v_{t}(\mu):=T_{0}^{t}v_{0}(\mu)$

where the initial estimate is $v_{0}(\mu):=\inf_{\Theta}k(\mu,\Theta)$. Under
Assumption 2,

$\displaystyle v_{t}(\mu)\to h(\mu)$

uniformly for $\mu\in{\mathcal{P}}(\mathds{X})$ for some measurable $h$.
Furthermore, $h$ satisfies the ACOE, i.e.

$\displaystyle h(\mu)+j^{*}=\inf_{\Theta\in U(\mu)}\left\\{k(\mu,\Theta)+\int
h(\mu_{1})\eta(d\mu_{1}|\mu,\Theta)\right\\}.$

Thus, one can compute the optimal policy by finding the selector.

###### Proof.

The proof is almost identical to the proof of Theorem 4. Recall that the key
step in that proof was to show that

$h_{\beta}^{t}(\mu):=K_{\beta}^{t}(\mu)-K_{\beta}^{t}(\mu_{0}),$

is uniformly bounded and equicontinuous over $\beta$ and $t$ where
$K_{\beta}^{t}$ is the optimal discounted $t$ horizon cost for the infinite
population problem. For the boundedness, we write

$\displaystyle h_{\beta}^{t}(\mu)$
$\displaystyle=K_{\beta}^{t}(\mu)-K_{\beta}^{t}(\mu_{0})\pm
E\left[K_{\beta}^{t,N}(\mu^{N})\right]\pm
E\left[K_{\beta}^{t,N}(\mu_{0}^{N})\right]$
$\displaystyle\leq\left|K_{\beta}^{t}(\mu)-E\left[K_{\beta}^{t,N}(\mu^{N})\right]\right|+\left|E\left[K_{\beta}^{t,N}(\mu^{N})-K_{\beta}^{t,N}(\mu^{N}_{0})\right]\right|+\left|E\left[K_{\beta}^{t,N}(\mu_{0}^{N})\right]-K_{\beta}^{t}(\mu_{0})\right|$

where $K_{\beta}^{t,N}$ is the optimal discounted $t$-horizon cost for the
$N$-population problem and $\mu^{N},\mu_{0}^{N}$ are the empirical
distributions under the source measures $\mu$ and $\mu_{0}$. The first and the
last terms converge to 0 as $N\to\infty$ under Assumption 2 as shown in [47,
30]. The middle term is bounded by

$\displaystyle\left|E\left[K_{\beta}^{t,N}(\mu^{N})-K_{\beta}^{t,N}(\mu^{N}_{0})\right]\right|\leq\frac{2K_{c}}{1-2K_{f}}E\left[W_{1}(\mu^{N},\mu_{0}^{N})\right]\xrightarrow{N\to\infty}\frac{2K_{c}}{1-2K_{f}}W_{1}(\mu,\mu_{0})$

where we use the bound in (15), which proves the uniform boundedness as
$\mathds{X}$ is assumed to be compact. For equicontinuity, we can use
identical arguments. Hence, following the proof steps of Theorem 4, the result
can be established.

∎

##  4 Convergence of Value Functions as $N\to\infty$

Finally, in this section, we prove that the optimal value function for the
finite population problem converges to the value function of the infinite
population problem under infinite horizon average cost criteria.

######  Theorem 7.

Under Assumption 2 for any $\mu_{0}\in{\mathcal{P}}(\mathds{X})$, we have that

$\displaystyle\lim_{N\to\infty}E\left[\left|K_{\infty}^{N,*}(\mu_{0}^{N})-K_{\infty}^{*}(\mu_{0})\right|\right]=0$

where $\mu_{0}^{N}$ is an empirical measure based on $\mu_{0}$, denoting the
distribution of $N$ agents.

###### Proof.

We will prove the result using the ACOE for the finite population and the
infinite population problem. Recall that we have proved the existence of ACOE
for the finite and infinite population problems under Assumption 2, in Theorem
5 and Theorem 3 such that:

$\displaystyle
h^{N}(\mu_{0}^{N})=\inf_{\Theta^{N}}\left\\{k(\mu_{0}^{N},\Theta^{N})+\int
h^{N}(\mu_{1}^{N})\eta(d\mu_{1}^{N}|\mu^{N}_{0},\Theta^{N})\right\\}-j^{N}$
$\displaystyle h(\mu_{0})=\inf_{\Theta}\left\\{k(\mu_{0},\Theta)+\int
h(\mu_{1})\eta(d\mu_{1}|\mu_{0},\Theta)\right\\}-j$

for some measurable relative value functions $h^{N},h$, and where $j^{N},j$
are constants that are equal to the optimal value functions, i.e.
$K_{\infty}^{N,*}(\mu_{0}^{N})=j^{N}$ for all $\mu_{0}^{N}$ and
$K_{\infty}^{*}(\mu_{0})=j$ for all $\mu_{0}$. In particular, under Assumption
2, there exist optimal selectors, say $f$ and $f^{N}$ such that

$\displaystyle h^{N}(\mu_{0}^{N})=k(\mu_{0}^{N},f^{N}(\mu_{0}^{N}))+\int
h^{N}(\mu_{1}^{N})\eta(d\mu_{1}^{N}|\mu^{N}_{0},f^{N}(\mu_{0}^{N}))-j^{N}$
$\displaystyle h(\mu_{0})=k(\mu_{0},f(\mu_{0}))+\int
h(\mu_{1})\eta(d\mu_{1}|\mu_{0},f(\mu_{0}))-j$

Iterating these equalities $T$ times we get

$\displaystyle
h^{N}(\mu_{0}^{N})=\sum_{t=0}^{T-1}E_{\mu_{0}^{N}}^{f^{N}}\left[k(\mu_{t}^{N},\Theta^{N}_{t})\right]+E_{\mu_{0}^{N}}^{f^{N}}\left[h^{N}(\mu_{T}^{N})\right]-Tj^{N}$
$\displaystyle
h(\mu_{0})=\sum_{t=0}^{T-1}E_{\mu_{0}}^{f}\left[k(\mu_{t},\Theta_{t})\right]+E_{\mu_{0}}^{f}\left[h(\mu_{T})\right]-Tj$
(18)

If we denote the finite horizon costs under some policies $g^{N},g$ by

$\displaystyle
K_{T}^{N}(\mu_{0}^{N},g^{N})=E_{\mu_{0}^{N}}^{g^{N}}\left[\sum_{t=0}^{T-1}k(\mu_{t}^{N},\Theta^{N}_{t})\right]$
$\displaystyle
K_{T}(\mu_{0},g)=E_{\mu_{0}}^{g}\left[\sum_{t=0}^{T-1}k(\mu_{t},\Theta_{t})\right]$

We can then write, using (4)

$\displaystyle
K_{T}^{N}(\mu_{0}^{N},f^{N})-Tj^{N}=h^{N}(\mu_{0}^{N})-E_{\mu_{0}^{N}}^{f^{N}}\left[h^{N}(\mu_{T}^{N})\right]$
$\displaystyle
K_{T}(\mu_{0},f)-Tj=h(\mu_{0})-E_{\mu_{0}}^{f}\left[h(\mu_{T})\right]$

We will later show that $\|h\|_{\infty}\leq M$ and $\|h^{N}\|_{\infty}\leq M$,
where $M$ is uniform over $N$. Hence, we can write

$\displaystyle\frac{K_{T}^{N}(\mu_{0}^{N},f^{N})}{T}-j^{N}\leq\frac{2M}{T}$
$\displaystyle\frac{K_{T}(\mu_{0},f)}{T}-j\leq\frac{2M}{T}$

If we iterate the ACOE’s, over some policies $g,g^{N}$ (including the finite
horizon optimal policies), instead of the selectors $f,f^{N}$, the equations
in (4), can be represented as the following inequalities:

$\displaystyle
h^{N}(\mu_{0}^{N})\leq\sum_{t=0}^{T-1}E_{\mu_{0}^{N}}^{g^{N}}\left[k(\mu_{t}^{N},\Theta^{N}_{t})\right]+E_{\mu_{0}^{N}}^{g^{N}}\left[h^{N}(\mu_{T}^{N})\right]-Tj^{N}$
$\displaystyle
h(\mu_{0})\leq\sum_{t=0}^{T-1}E_{\mu_{0}}^{g}\left[k(\mu_{t},\Theta_{t})\right]+E_{\mu_{0}}^{g}\left[h(\mu_{T})\right]-Tj$

Using the same bound on $h,h^{N}$

$\displaystyle\frac{-2M}{T}\leq\frac{K_{T}^{N}(\mu_{0}^{N},g^{N})}{T}-j^{N}$
$\displaystyle\frac{-2M}{T}\leq\frac{K_{T}(\mu_{0},g)}{T}-j$

As we have noted, the above lower bounds are valid for the finite horizon
optimal policies as well. Furthermore, because of the optimality, we have that
$\frac{K_{T}^{N,*}(\mu_{0}^{N})}{T}\leq\frac{K_{T}^{N}(\mu_{0}^{N},f^{N})}{T}$
and $\frac{K_{T}^{*}(\mu_{0})}{T}\leq\frac{K_{T}(\mu_{0},f)}{T}$ where $f$ and
$f^{N}$ are the selectors for the ACOE, i.e. the optimal policies for the
infinite horizon average cost problem. Hence, we can write

$\displaystyle\frac{-2M}{T}\leq\frac{K_{T}^{N,*}(\mu_{0}^{N})}{T}-j^{N}\leq\frac{K_{T}^{N}(\mu_{0}^{N},f^{N})}{T}-j^{N}\leq\frac{2M}{T}$
$\displaystyle\frac{-2M}{T}\leq\frac{K_{T}^{*}(\mu_{0})}{T}-j\leq\frac{K_{T}(\mu_{0}^{N},f)}{T}-j\leq\frac{2M}{T}$

Hence, if $M$ is uniform over $N$, taking $T\to\infty$, we get

$\displaystyle\frac{K_{T}^{N,*}(\mu_{0}^{N})}{T}-j^{N}\to 0$
$\displaystyle\frac{K_{T}^{*}(\mu_{0})}{T}-j\to 0$ (19)

uniformly over $N$.

To show that $h$ and $h^{N}$ are uniformly bounded over $N$, we write using
(14) and (3.2)

$\displaystyle h^{N}(\mu_{0}^{N})=\lim_{\beta\to
1}h_{\beta}^{N}(\mu_{0}^{N})\leq M$ $\displaystyle h(\mu_{0})=\lim_{\beta\to
1}h_{\beta}(\mu_{0})\leq M$

where $M$ is independent of $N$.

Finally, we write

$\displaystyle
E\left[\left|K_{\infty}^{N,*}(\mu_{0}^{N})-K_{\infty}^{*}(\mu_{0})\right|\right]=E\left[\left|K_{\infty}^{N,*}(\mu_{0}^{N})-K_{\infty}^{*}(\mu)\pm\frac{K_{T}^{*}(\mu_{0})}{T}\pm\frac{K_{T}^{N,*}(\mu_{0}^{N})}{T}\right|\right]$
$\displaystyle\leq
E\left[\left|K_{\infty}^{N,*}(\mu_{0}^{N})-\frac{K_{T}^{N,*}(\mu_{0}^{N})}{T}\right|\right]+E\left[\left|\frac{K_{T}^{N,*}(\mu_{0}^{N})}{T}-\frac{K_{T}^{*}(\mu_{0})}{T}\right|\right]$
$\displaystyle\quad+E\left[\left|\frac{K_{T}^{*}(\mu_{0})}{T}-K_{\infty}^{*}(\mu_{0})\right|\right]$

We have shown in (4) that we can choose a large enough $T$, independent of $N$
such that the first and the last terms are less than $\epsilon/3$ for any
given $\epsilon>0$. For the chosen $\epsilon$ and $T$, it has been shown in
[47, 30] that the middle term goes to $0$, i.e. can be made less than
$\epsilon/3$, for some large $N<\infty$, under Assumption 2. Hence the proof
is completed. ∎

## References

  * [1] M. Huang, R. P. Malhamé, and P. E. Caines, “Large population stochastic dynamic games: closed-loop mckean-vlasov systems and the nash certainty equivalence principle,” Communications in Information & Systems, vol. 6, no. 3, pp. 221–252, 2006.
  * [2] J. M. Lasry and P. L. Lions, “Mean field games,” Japanese journal of mathematics, vol. 2, no. 1, pp. 229–260, 2007.
  * [3] D. A. Gomes and J. Saúde, “Mean field games models—a brief survey,” Dynamic Games and Applications, vol. 4, no. 2, pp. 110–154, 2014.
  * [4] R. Carmona and F. Delarue, “Probabilistic analysis of mean-field games,” SIAM Journal on Control and Optimization, vol. 51, no. 4, pp. 2705–2734, 2013\.
  * [5] A. Bensoussan, J. Frehse, and P. Yam, Mean field games and mean field type control theory, vol. 101.  Springer, 2013.
  * [6] H. Tembine, Q. Zhu, and T. Başar, “Risk-sensitive mean-field games,” IEEE Transactions on Automatic Control, vol. 59, no. 4, pp. 835–850, 2013\.
  * [7] M. Huang, P. E. Caines, and R. P. Malhamé, “Large-population cost-coupled LQG problems with nonuniform agents: individual-mass behavior and decentralized epsilon -Nash equilibria,” IEEE transactions on automatic control, vol. 52, no. 9, pp. 1560–1571, 2007.
  * [8] B. Anahtarci, C. D. Kariksiz, and N. Saldi, “Q-learning in regularized mean-field games,” Dynamic Games and Applications, pp. 1–29, 2022.
  * [9] R. Elie, J. Perolat, M. Laurière, M. Geist, and O. Pietquin, “On the convergence of model free learning in mean field games,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 7143–7150, 2020\.
  * [10] Z. Fu, Z. Yang, Y. Chen, and Z. Wang, “Actor-critic provably finds Nash equilibria of linear-quadratic mean-field games,” 2020.
  * [11] X. Guo, A. Hu, R. Xu, and J. Zhang, “Learning mean-field games,” Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [12] S. Perrin, J. Pérolat, M. Laurière, M. Geist, R. Elie, and O. Pietquin, “Fictitious play for mean field games: Continuous time analysis and applications,” Advances in Neural Information Processing Systems, vol. 33, pp. 13199–13213, 2020.
  * [13] J. Subramanian and A. Mahajan, “Reinforcement learning in stationary mean-field games,” in Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 251–259, 2019.
  * [14] N. Saldi, T. Basar, and M. Raginsky, “Markov–nash equilibria in mean-field games with discounted cost,” SIAM Journal on Control and Optimization, vol. 56, no. 6, pp. 4256–4287, 2018.
  * [15] N. Saldi, T. Başar, and M. Raginsky, “Approximate nash equilibria in partially observed stochastic games with mean-field interactions,” Mathematics of Operations Research, vol. 44, no. 3, pp. 1006–1033, 2019.
  * [16] E. Bayraktar, A. Cosso, and H. Pham, “Randomized dynamic programming principle and Feynman-Kac representation for optimal control of Mckean-Vlasov dynamics,” Transactions of the American Mathematical Society, vol. 370, no. 3, pp. 2115–2160, 2018.
  * [17] M. F. Djete, D. Possamaï, and X. Tan, “McKean–Vlasov optimal control: the dynamic programming principle,” The Annals of Probability, vol. 50, no. 2, pp. 791–833, 2022.
  * [18] M. Laurière and O. Pironneau, “Dynamic programming for mean-field type control,” Comptes Rendus Mathematique, vol. 352, no. 9, pp. 707–713, 2014\.
  * [19] H. Pham and X. Wei, “Dynamic programming for optimal control of stochastic McKean–Vlasov dynamics,” SIAM Journal on Control and Optimization, vol. 55, no. 2, pp. 1069–1101, 2017.
  * [20] R. Carmona and M. Laurière, “Convergence analysis of machine learning algorithms for the numerical solution of mean field control and games i: The ergodic case,” SIAM Journal on Numerical Analysis, vol. 59, no. 3, pp. 1455–1485, 2021.
  * [21] M. Germain, J. Mikael, and X. Warin, “Numerical resolution of Mckean-Vlasov FBSDEs using neural networks,” Methodology and Computing in Applied Probability, pp. 1–30, 2022.
  * [22] E. Bayraktar, A. Cecchin, and P. Chakraborty, “Mean field control and finite agent approximation for regime-switching jump diffusions,” Applied Mathematics & Optimization, vol. 88, no. 2, p. 36, 2023.
  * [23] E. Bayraktar and X. Zhang, “Solvability of infinite horizon Mckean–Vlasov FBSDEs in mean field control problems and games,” Applied Mathematics & Optimization, vol. 87, no. 1, p. 13, 2023.
  * [24] E. Bayraktar, N. Bauerle, and A. D. Kara, “Finite approximations for mean field type multi-agent control and their near optimality,” 2023.
  * [25] S. Sanjari, N. Saldi, and S. Yüksel, “Optimality of independently randomized symmetric policies for exchangeable stochastic teams with infinitely many decision makers,” Mathematics of Operations Research, 2022\.
  * [26] S. Sanjari and S. Yuksel, “Optimal policies for convex symmetric stochastic dynamic teams and their mean-field limit,” SIAM Journal on Control and Optimization, vol. 59, no. 2, pp. 777–804, 2021.
  * [27] D. Lacker, “Limit theory for controlled McKean–Vlasov dynamics,” SIAM Journal on Control and Optimization, vol. 55, no. 3, pp. 1641–1672, 2017\.
  * [28] M. Fornasier, S. Lisini, C. Orrieri, and G. Savaré, “Mean-field optimal control as gamma-limit of finite agent controls,” European Journal of Applied Mathematics, vol. 30, no. 6, pp. 1153–1186, 2019.
  * [29] M. Motte and H. Pham, “Quantitative propagation of chaos for mean field Markov decision process with common noise,” Electronic Journal of Probability, vol. 28, pp. 1–24, 2023.
  * [30] M. Motte and H. Pham, “Mean-field Markov decision processes with common noise and open-loop controls,” The Annals of Applied Probability, vol. 32, no. 2, pp. 1421–1458, 2022.
  * [31] R. Carmona, M. Laurière, and Z. Tan, “Model-free mean-field reinforcement learning: mean-field MDP and mean-field Q-learning,” arXiv preprint arXiv:1910.12802, 2019.
  * [32] H. Gu, X. Guo, X. Wei, and R. Xu, “Mean-field controls with q-learning for cooperative marl: convergence and complexity analysis,” SIAM Journal on Mathematics of Data Science, vol. 3, no. 4, pp. 1168–1196, 2021.
  * [33] H. Gu, X. Guo, X. Wei, and R. Xu, “Dynamic programming principles for mean-field controls with learning,” Operations Research, 2023.
  * [34] A. Angiuli, J.-P. Fouque, and M. Laurière, “Unified reinforcement q-learning for mean field game and control problems,” Mathematics of Control, Signals, and Systems, vol. 34, no. 2, pp. 217–271, 2022.
  * [35] E. Feleqi, “The derivation of ergodic mean field game equations for several populations of players,” Dynamic Games and Applications, vol. 3, pp. 523–536, 2013.
  * [36] P. Cardaliaguet, J.-M. Lasry, P.-L. Lions, and A. Porretta, “Long time average of mean field games,” Networks and heterogeneous media, vol. 7, no. 2, pp. 279–301, 2012.
  * [37] A. Arapostathis, A. Biswas, and J. Carroll, “On solutions of mean field games with ergodic cost,” Journal de Mathématiques Pures et Appliquées, vol. 107, no. 2, pp. 205–251, 2017.
  * [38] M. Bardi and F. S. Priuli, “Linear-quadratic n-person and mean-field games with ergodic cost,” SIAM Journal on Control and Optimization, vol. 52, no. 5, pp. 3022–3052, 2014.
  * [39] M. Cirant, “Stationary focusing mean-field games,” Communications in Partial Differential Equations, vol. 41, no. 8, pp. 1324–1346, 2016.
  * [40] F. Dragoni and E. Feleqi, “Ergodic mean field games with hörmander diffusions,” Calculus of Variations and Partial Differential Equations, vol. 57, pp. 1–22, 2018.
  * [41] D. A. Gomes, S. Patrizi, and V. Voskanyan, “On the existence of classical solutions for stationary extended mean field games,” Nonlinear Analysis: Theory, Methods & Applications, vol. 99, pp. 49–79, 2014.
  * [42] N. Saldi, “Discrete-time average-cost mean-field games on polish spaces,” Turkish Journal of Mathematics, vol. 44, no. 2, pp. 463–480, 2020.
  * [43] B. Anahtarcı, C. D. Karıksız, and N. Saldi, “Value iteration algorithm for mean-field games,” Systems & Control Letters, vol. 143, p. 104744, 2020.
  * [44] A. Biswas, “Mean field games with ergodic cost for discrete time markov processes,” arXiv preprint arXiv:1510.08968, 2015.
  * [45] P. Wiecek and E. Altman, “Stationary anonymous sequential games with undiscounted rewards,” Journal of optimization theory and applications, vol. 166, pp. 686–710, 2015.
  * [46] P. Wiecek, “Discrete-time ergodic mean-field games with average reward on compact spaces,” Dynamic Games and Applications, vol. 10, no. 1, pp. 222–256, 2020.
  * [47] N. Bäuerle, “Mean field Markov decision processes,” Applied Mathematics & Optimization, vol. 88, no. 1, p. 12, 2023.
  * [48] O. Hernández-Lerma, Adaptive Markov Control Processes.  Springer-Verlag, 1989.
  * [49] S. Yüksel, “Optimization and control of stochastic systems,” Queen’s University, Lecture notes, available online, URL: https://mast.queensu.ca/ yuksel/LectureNotesOnStochasticOptControl.pdf.
  * [50] O. Hernandez-Lerma and J. B. Lasserre, Discrete-Time Markov Control Processes: Basic Optimality Criteria.  Springer, 1996.
  * [51] O. Hernández-Lerma and J. B. Lasserre, Further topics on discrete-time Markov control processes.  Springer, 1999.
  * [52] A. Arapostathis, V. S. Borkar, E. Fernandez-Gaucherand, M. K. Ghosh, and S. I. Marcus, “Discrete-time controlled Markov processes with average cost criterion: A survey,” SIAM J. Control and Optimization, vol. 31, pp. 282–344, 1993.