# Independent Learning in Mean-Field Games: Satisficing Paths and Convergence
to Subjective Equilibria

Bora Yongacoglu, Gürdal Arslan, and Serdar Yüksel This research was supported
in part by the Natural Sciences and Engineering Research Council (NSERC) of
Canada.B. Yongacoglu and S. Yüksel are with the Department of Mathematics and
Statistics, Queen’s University, Kingston, ON, Canada, email:
<EMAIL_ADDRESS>G. Arslan is with the University of Hawaii, email:
<EMAIL_ADDRESS>
###### Abstract

Independent learners are learning agents that naively employ single-agent
learning algorithms in multi-agent systems, intentionally ignoring the effect
of other strategic agents present in their environment. This paper studies
$N$-player mean-field games from a decentralized learning perspective with two
primary objectives: (i) to study the convergence properties of independent
learners, and (ii) to identify structural properties of $N$-player mean-field
games that can guide algorithm design. Toward the first objective, we study
the learning iterates obtained by independent learners, and we use recent
results from POMDP theory to show that these iterates converge under mild
conditions. In particular, we consider four information structures
corresponding to information at each agent: (1) global state + local action;
(2) local state, mean-field state + local action; (3) local state, compressed
mean-field state + local action; (4) local state with local action. We present
a notion of subjective equilibrium suitable for the analysis of independent
learners. Toward the second objective, we study a family of dynamical systems
on the set of joint policies. The dynamical systems under consideration are
subject to a so-called $\epsilon$-satisficing condition: agents who are
subjectively $\epsilon$-best-responding at a given joint policy do not change
their policy. We establish a useful structural property relating to such
dynamical systems. Finally, we develop an independent learning algorithm for
$N$-player mean-field games that drives play to subjective
$\epsilon$-equilibrium under self-play, exploiting the aforementioned
structural properties to guarantee convergence of policies. Notably, we avoid
requiring agents to follow the same policy (via a representative agent) during
the learning process, which has been the typical approach in the existing
literature on learning for mean-field games.

##  I Introduction

Mean-field games (MFGs) are a relatively recent theoretical framework for
studying strategic environments with a large number of weakly coupled
decision-making agents [1, 2, 3, 4, 5]. In a MFG, the cost and state dynamics
of any particular agent are influenced by the collective behaviour of others
only through a distributional mean-field term. Mean-field games can be viewed
as limit models of $N$-player symmetric stochastic games, where players are
exchangeable and symmetric entities. A number of papers have formally examined
the connection between games with finitely many players and the corresponding
limit model, including the works of [6, 7, 8]. Given the ubiquity of large-
scale decentralized systems in modern engineering, MFGs have been used to
model a diverse range of applications, such resource management [9, 10],
social conventions [11], power control in telecommunications networks [12],
and traffic control [13], among many others.

Multi-agent reinforcement learning (MARL) is the study of the emergent
behaviour in systems of interacting learning agents, with stochastic games
serving as the most popular framework for modelling such systems [14, 15]. In
recent years, there has been a considerable amount of research in MARL that
has aimed to produce algorithms with desirable system-wide performance and
convergence properties. While these efforts have lead to a number of
empirically successful algorithms, such as [16], there are comparatively fewer
works that offer formal convergence analyses of their algorithms, and the bulk
of existing work is suitable only for systems with a relatively small number
of agents.

The majority of theoretical contributions in MARL have focused on highly
structured classes of stochastic games, such as two-player zero-sum games [17,
18] and $N$-player stochastic teams and their generalizations [19, 20]. In
much of the existing literature on MARL, a great deal of information is
assumed to be available to the agents while they learn. These assumptions,
such as full state observability ([17]–[20]) or action-sharing among all
agents (e.g. [21, 22, 23]), are appropriate in some settings but are
unrealistic in many large-scale, decentralized systems modelled by MFGs.

One issue with designing MARL algorithms that use global information about the
local states and actions of all players is that such algorithms do not scale
with the number of players: the so-called curse of many agents is a widely
cited challenge to MARL, wherein the computational burden at each agent
becomes intractable exponentially quickly in the number of agents [24].

Independent learners [25, 26] are a class of MARL algorithms that are
characterized by intentional obliviousness to the strategic environment:
independent learners ignore the presence of other players, effectively
treating other players as part of the environment rather than as the non-
stationary learning agents that they actually are. By naively running a
single-agent reinforcement learning algorithm using only local information,
independent learners are relieved of the burden of excessive information,
which may lead to scalable algorithms for large-scale decentralized systems.
However, additional care must be taken when designing independent learners, as
direct application of single-agent reinforcement learning has had mixed
success even in small empirical studies [27, 28, 29, 30].

In this paper, we study independent learners in partially observed $N$-player
mean-field games. This finite agent model is a slight variation of the model
presented in [7], and is closely related to the standard mean-field game
model, where the set of agents is taken to be infinite. We focus on a
decentralized learning environment in which players do not observe the actions
of other agents and may have a limited view of the overall state of the
system. Furthermore, we assume that players view only the stream of data
encountered during gameplay: players do not have access to a simulator for
sampling feedback data in arbitrary order, nor do they have access to any
other data sets that can be used for training. In this context, we are
interested in developing decentralized algorithms for MFGs that have desirable
convergence properties.

Given that decentralization and learning are the primary focuses of this
study, we are interested in algorithms that have minimal coordination between
agents after play begins. In particular, we wish to avoid forcing agents to
follow the same policy during learning, which (as we discuss later) is a
standard assumption in the literature on learning in MFGs. We also avoid the
popular paradigm of centralized training with decentralized execution, wherein
a global action-value function is learned during training and players select
policies that can be implemented in a decentralized manner informed by this
global quantity. Some examples of studies using this paradigm include [31, 32]
and [33].

Contributions:

  1. 1.

We study learning iterates obtained by independent learners in a partially
observed $N$-player mean-field game. In Theorem 2, we show that when each
agent uses a stationary policy and naively runs Q-learning and state value
estimation algorithms, its learning iterates converge almost surely under mild
conditions on the game;

  2. 2.

We define a notion of subjective $\epsilon$-equilibrium for partially observed
$N$-player mean-field games. By analogy to an $\epsilon$-optimality criterion
for MDPs, we argue that this notion of subjective equilibrium is natural and
suitable for the analysis of independent learners;

  3. 3.

Under two alternative assumptions on the observation channel of the partially
observed $N$-player mean-field game, we establish the existence of both
objective and subjective $\epsilon$-equilibrium for any $\epsilon>0$. (Lemma
7, Theorem 1, Lemmas 12 and 13);

  4. 4.

We introduce the notion of _subjective $\epsilon$-satisficing_. In Theorems 3,
4, and 5, we establish a useful structural property, to be called the
subjective $\epsilon$-satisficing paths property;

  5. 5.

We leverage the aforementioned structure to develop a decentralized
independent learner for playing partially observed $N$-player mean-field
games.

  6. 6.

Under several information structures, we give guarantees of convergence to
subjective $\epsilon$-equilibrium under self-play, with suitably chosen
parameters. In particular, we consider information structures where each agent
has: (a) global state information; (b) local state and mean-field (empirical)
information; (c) local state and a compression of mean-field information; (d)
only local informations.

The paper is organized as follows: in §I-A, we survey related literature. The
model and various important definitions are presented in Section II. The
existence of (objective) equilibrium policies in the set of stationary
policies is discussed in Section III. The topic of naive learning is covered
in Section IV, where we show the convergence of iterates, discuss the
interpretation of the limiting quantities, and argue that subjective
$\epsilon$-equilibrium policies exists. We discuss subjective satisficing in
Section V, and we prove important structural results for partially observed
$N$-player mean-field games. In Section VI, we present a learning algorithm
and its convergence results. Modelling assumptions are discussed in Section
VII, and the final section concludes. Proofs omitted from the body of the
paper are available in the appendices.

Notation: We use ${\rm Pr}$ to denote a probability measure on some underlying
probability space, with additional superscript and subscript indices included
when called for. A finite set $S$, we let $\mathbb{R}^{S}$ denote the real
vector space of dimension $|S|$ where vector components are indexed by
elements of $S$. We let $0\in\mathbb{R}^{S}$ denote the zero vector of
$\mathbb{R}^{S}$ and $1\in\mathbb{R}^{S}$ denote the vector in
$\mathbb{R}^{S}$ for which each component is 1. For standard Borel sets
$S,S^{\prime}$, we let $\mathcal{P}(S)$ denote the set of probability measures
on $S$, and we let $\mathcal{P}(S^{\prime}|S)$ denote the set of transition
kernels on $S^{\prime}$ given $S$. We use $Y\sim\mu$ to denote that the random
variable $Y$ has distribution $\mu$. For an event $A$, we let $\textbf{1}A$
denote the indicator function of the event $A$’s occurrence. If a probability
distribution $\mu$ is a mixture of distributions $\mu_{1},\dots,\mu_{n}$ with
mixture weights $p_{1},\dots,p_{n}$, we write
$Y\sim\sum_{i=1}^{n}p_{i}\mu_{i}$. For $s\in S$, we use
$\delta_{s}\in\mathcal{P}(S)$ to denote the Dirac measure centered at $s$.

###  I-A Related Work

Learning in mean-field games is a nascent but active research area. Early
contributions to learning in mean-field games include [34] and [35], which
studied learning in specific classes of MFGs. Another relatively early
contribution to learning in a mean-field environment is [36], which studies a
model inspired by the mean-field theory of physics; the model used there is
closely related to (but different from) typical models of mean-field games.

More related to the present paper are the works [37, 38, 39, 40, 41] and [42].
By and large, these works approach learning in MFGs by analyzing the single-
agent problem for a representative agent in the limiting case as $N\to\infty$,
and equilibrium is defined using a best-responding condition as well as a
consistency condition; see, for instance, [38, Definition 2.1]. This notion of
equilibrium is inherently symmetric: at equilibrium, all agents use the policy
of the representative agent. In contrast, the notion of equilibrium we
consider is more along the lines of [38, Definition 5.1], as it allows for
different agents to follow different policies.

In [37], the authors study a model of MFGs that allows for costs and state
dynamics to depend also on the distribution of actions of other players. Under
somewhat stringent assumptions of Lipschitz continuity, an existence and
uniqueness of equilibrium result is given, and an algorithm is presented for
learning such an equilibrium. Of note, this paper assumes that the learner has
access to a population simulator for sampling state transition and cost data
at one’s convenience. This algorithm is therefore not suitable for learning
applications in which the data observed by a learner depends on an actual
trajectory of play, obtained during sequential interaction with a system.

A special case of MFGs, called stationary MFGs, is studied in [38]. The
authors present multiple notions of equilibrium and study two-timescale policy
gradient methods in this setting, wherein a representative agent updates its
policy to best-respond to its (estimated) environment on the fast timescale
and updates its estimate for the mean-field flow on the slow timescale. By
assuming access to a simulator for obtaining data, convergence to a weak
notion of local equilibrium is proved.

MFGs with a finite time horizon and uncountable state and action spaces are
considered in [39]. A fictitious play algorithm of sorts is proposed and
analyzed, though the question of learning best-response is black-boxed.

Another fictitious play algorithm is proposed in [40], which in some ways
parallels [38] by iteratively updating both the policy and the mean-field term
at every step of the algorithm. In the algorithm of [40], there is no nested
loop structure, whereby the optimal policy is estimated iteratively while the
mean-field term is held fixed. As with the algorithm of [37], the main
algorithm of [40] is not suitable for use when data arrives to the agent from
an actual trajectory of play, as the main algorithm of [40] requires the agent
to “do nothing” if it so chooses (C.f. Line 4, [40, Algorithm 1]).

A common theme uniting the works cited above is that they are centralized
methods for finding equilibrium in a mean-field game modelling a decentralized
system. The use of a simulator for obtaining data allows these algorithms to
sample data as if it were generated by a population of agents using symmetric
policies at each step of the algorithm. As a result, the problems studied have
essentially no multi-agent flavour due to the lack of strategic interaction in
the mean-field limit. It appears that the principal aim of these papers is to
compute a (near) equilibrium for the mean-field games they study. In contrast,
the primary aim of this paper is to understand the patterns of behaviour that
emerge when agents use reasonable (if naive and/or limited) learning
algorithms in a shared environment. Our focus, then, is less computational and
more descriptive in nature than the aforementioned papers.

In many realistic multi-agent learning settings, even when agents face
symmetric and interchangeable problems, they may employ different learning
algorithms for a variety of reasons (e.g. prior beliefs on the system).
Moreover, since distinct agents will observe distinct local observation
histories and feed these local observation histories to different learning
algorithms, it follows that distinct agents may use radically different
policies over the course of learning. Work in the computational traditional
largely avoids such learning dynamics, and therefore does not encounter the
quite plausible equilibrium policies that are composed of various heterogenous
policies used by a population of homogenous players.

In this paper, we have attempted to depart from the traditional approach of
mandating all agents follow the same policy during learning.

##  II Model: Partially Observed Markov Decision Problems and $N$-Player Mean-
Field Games

In this section, we present two models for strategic decision making in
dynamic environments. The first model, presented in §II-A, is the partially
observed Markov decision problem. Here, a single decision-making agent
interacts with a fixed environment. The cost minimization problem for the
agent is inter-temporal and dynamic, as a cost-relevant state variable evolves
randomly over time according to the system’s history and the agent’s actions.
The second model, presented in §II-B, is our model of partially observed
$N$-player mean-field games. Here, a finite (though possibly large) number of
players interact in a shared environment. The two models are closely related,
and this close relationship features heavily in the analysis and constructions
of subsequent sections.

###  II-A Partially Observed Markov Decision Problems

A finite, partially observed Markov decision problem (POMDP) with the
discounted cost criterion is given by a list $M$:

$M=\left(\mathbb{X},\mathbb{Y},\mathbb{U},c,P,\varphi,\beta,\nu_{0}\right).$
(1)

The components of $M$ are the following: $\mathbb{X}$ is a finite set of
states; $\mathbb{Y}$ is finite set of observation symbols; $\mathbb{U}$ is a
finite set of control actions;
$P\in\mathcal{P}(\mathbb{X}|\mathbb{X}\times\mathbb{U})$ is a transition
kernel that governs the evolution of the state variable;
$c:\mathbb{X}\times\mathbb{U}\to\mathbb{R}$ is a stage cost function that
determines the cost incurred by the agent at each stage/interaction with the
system; $\varphi\in\mathcal{P}(\mathbb{Y}|\mathbb{X})$ is a noisy observation
channel through which the agent observes the system’s state variable;
$\beta\in(0,1)$ is a discount factor for aggregating costs over time;
$\nu_{0}\in\mathcal{P}(\mathbb{X})$ is a initial distribution for the state
variable.

Play of the POMDP $M$ is described as follows: at time $t\in\mathbb{Z}_{\geq
0}$, the system’s state is denoted $x_{t}$ and takes values in $\mathbb{X}$.
An observation variable $y_{t}$ taking values in $\mathbb{Y}$ is generated
according to $y_{t}\sim\varphi(\cdot|x_{t})$. The agent uses its observable
history variable, to be defined shortly, to select its action
$u_{t}\in\mathbb{U}$. The agent then incurs a stage cost
$c_{t}:=c(x_{t},u_{t})$ and the system’s state transitions according to
$x_{t+1}\sim P(\cdot|x_{t},u_{t})$.

For $t\in\mathbb{Z}_{\geq 0}$, we define the _system history sets_
$\\{\mathbb{H}_{t}\\}_{t\geq 0}$ as follows:

$\displaystyle\mathbb{H}_{0}$ $\displaystyle:=\mathbb{X}\times\mathbb{Y}$
$\displaystyle\mathbb{H}_{t+1}$
$\displaystyle:=\mathbb{H}_{t}\times\mathbb{U}\times\mathbb{X}\times\mathbb{Y}=\left(\mathbb{X}\times\mathbb{Y}\times\mathbb{U}\right)^{t+1}\times\mathbb{X}\times\mathbb{Y},\quad\forall
t\geq 0.$

For $t\in\mathbb{Z}_{\geq 0}$, elements of $\mathbb{H}_{t}$ are called system
histories of length $t$, and we use
$\textbf{h}_{t}=(x_{0},y_{0},u_{0},\cdots,u_{t-1},x_{t},y_{t})$, a random
quantity taking values in $\mathbb{H}_{t}$, to denote the $t^{\rm th}$ system
history variable. To capture the information actually observed by the agent
controlling the system, we also define _observable history sets_
$\\{H_{t}\\}_{t\geq 0}$ as follows:

$\displaystyle H_{0}$ $\displaystyle:=\mathcal{P}(\mathbb{X})\times\mathbb{Y}$
$\displaystyle H_{t+1}$
$\displaystyle:=H_{t}\times\mathbb{U}\times\mathbb{R}\times\mathbb{Y}=\mathcal{P}(\mathbb{X})\times\left(\mathbb{Y}\times\mathbb{U}\times\mathbb{R}\right)^{t+1}\times\mathbb{Y},\quad\forall
t\geq 0.$

For $t\in\mathbb{Z}_{\geq 0}$, elements of $H_{t}$ are called _observable
histories of length $t$_, and we use
$h_{t}=(\nu_{0},y_{0},u_{0},c_{0},\cdots,c_{t-1},y_{t})$, a random quantity
taking values in $H_{t}$, to denote the $t^{\rm th}$ _observable history
variable_.

######  Definition 1 (Policies)

A policy (for the POMDP $M$) is defined as a sequence $\pi=(\pi_{t})_{t\geq
0}$ such that $\pi_{t}\in\mathcal{P}(\mathbb{U}|H_{t})$ for each $t$.

We denote the set of all policies for the POMDP $M$ by $\Gamma$. Fixing a
policy $\pi\in\Gamma$ and an initial measure $\nu\in\mathcal{P}(\mathbb{X})$
induces a unique probability measure ${\rm Pr}^{\pi}_{\nu}$ on the set
$(\mathbb{X}\times\mathbb{Y}\times\mathbb{U}\times\mathbb{R})^{\infty}$ such
that

  * •

${\rm Pr}^{\pi}_{\nu}(x_{0}\in\cdot)=\nu(\cdot)$;

  * •

For any $t\geq 0$, ${\rm
Pr}^{\pi}_{\nu}\left(x_{t+1}\in\cdot|\textbf{h}_{t},u_{t}\right)=P(\cdot|x_{t},u_{t})$;

  * •

For any $t\geq 0$, ${\rm
Pr}^{\pi}_{\nu}(y_{t}\in\cdot|\textbf{h}_{t})=\varphi(\cdot|x_{t})$;

  * •

For any $t\geq 0$, ${\rm
Pr}^{\pi}_{\nu}(u_{t}\in\cdot|h_{t})=\pi_{t}(\cdot|h_{t})$.

For each $\pi\in\Gamma$ and $\nu\in\mathcal{P}(\mathbb{X})$, we denote the
expectation associated to ${\rm Pr}^{\pi}_{\nu}$ by $E^{\pi}_{\nu}$ and use it
to define the agent’s objective function, also called the _(state) value
function_ :

$J_{\pi}(\nu):=E^{\pi}_{\nu}\left[\sum_{t\geq
0}\beta^{t}c(x_{t},u_{t})\right],\quad\forall\pi\in\Gamma,\nu\in\mathcal{P}(\mathbb{X}).$

In the special case that $\nu=\delta_{s}$ for some state $s\in\mathbb{X}$, we
simply write $J_{\pi}(s)$ for $J_{\pi}(\delta_{s})$.

######  Definition 2 (Optimal Policy)

For $\epsilon\geq 0$, a policy $\pi^{*}\in\Gamma$ is called _$\epsilon$
-optimal_ if it satisfies

$J_{\pi^{*}}(\nu)\leq\inf_{\pi\in\Gamma}J_{\pi}(\nu)+\epsilon,$

for any $\nu\in\mathcal{P}(\mathbb{X})$. If a policy is $0$-optimal, it is
simply called an optimal policy.

We now state two important properties that policies may have. These will
feature prominently in the coming sections.

######  Definition 3 (Stationary Policies)

A policy $\pi\in\Gamma$ for the POMDP $M$ is called _stationary_ if there
exists $g\in\mathcal{P}(\mathbb{U}|\mathbb{Y})$ such that for any $t\geq 0$
and any $\tilde{h}_{t}=(\tilde{\nu},\tilde{s}_{0},\dots,\tilde{y}_{t})\in
H_{t}$, we have $\pi_{t}(\cdot|\tilde{h}_{t})=g(\cdot|\tilde{y}_{t})$. We let
$\Gamma_{S}$ denote the set of stationary policies for the POMDP $M$.

######  Definition 4 (Soft Policies)

For $\xi>0$, a policy $\pi\in\Gamma$ is called _$\xi$ -soft_ if, for any
$t\geq 0$ and $\tilde{h}_{t}\in H_{t}$, we have $\pi(a|\tilde{h}_{t})\geq\xi$
for all $a\in\mathbb{U}$. A policy $\pi\in\Gamma$ is called _soft_ if it is
$\xi$-soft for some $\xi>0$.

The goal for an agent controlling the POMDP $M$ is to find an optimal policy.
It is well-known that optimal policies exist for any finite POMDP with the
discounted cost criterion [43]. It is also known that, for general finite
POMDPs, it is not the case that an optimal policy exists within the set
$\Gamma_{S}$.

####  II-A1 Fully Observed Markov Decision Problems

We now discuss an important special case of POMDPs in which the partially
observed state process is fully observed.

######  Definition 5 (MDP)

A fully observed Markov decision problem (or simply an MDP) is a POMDP for
which $\mathbb{X}=\mathbb{Y}$ and $\varphi(\cdot|s)=\delta_{s}$ for each state
$s\in\mathbb{X}$.

The following fact is well-known.

###### Fact 1

Let $M$ be a fully observed MDP. There exists an optimal policy
$\pi^{*}\in\Gamma_{S}$. Moreover, for $\pi\in\Gamma_{S}$, if
$J_{\pi}(s)=\inf_{\pi^{\prime}\in\Gamma}J_{\pi^{\prime}}(s)$ for every
$s\in\mathbb{X}$, then $\pi$ is an optimal policy.

Using the existence of an optimal policy $\pi^{*}\in\Gamma_{S}$, we define the
Q-function, also known as the (state-) action value function, for the MDP $M$
as follows: $Q^{*}_{M}:\mathbb{X}\times\mathbb{U}\to\mathbb{R}$ is given by

$Q^{*}_{M}(s,a):=E^{\pi^{*}}_{\nu}\left[\sum_{t=0}^{\infty}\beta^{t}c(x_{t},u_{t})\middle|x_{0}=s,u_{0}=a\right],\quad\forall(s,a)\in\mathbb{X}\times\mathbb{U},$

where $\pi^{*}\in\Gamma_{S}$ is an optimal policy for $M$ and
$\nu\in\mathcal{P}(\mathbb{X})$ is any initial state distribution. One can
show that, for any $s\in\mathbb{X}$, we have
$J_{\pi^{*}}(s)=\min_{a\in\mathbb{U}}Q^{*}_{M}(s,a)$. The Q-function can then
be used to verify the $\epsilon$-optimality of a given stationary policy; this
is formalized in the lemma below.

###### Lemma 1

Let $\pi\in\Gamma_{S}$ and $\epsilon\geq 0$. We have that $\pi$ is
$\epsilon$-optimal for the MDP $M$ if and only if

$J_{\pi}(s)\leq\min_{a\in\mathbb{U}}Q^{*}_{M}(s,a)+\epsilon,\quad\forall
s\in\mathbb{X}.$ (2)

###### Proof:

For any $s\in\mathbb{X}$, we have that
$\min_{\tilde{a}\in\mathbb{U}}Q^{*}_{M}(s,\tilde{a})=J_{\pi^{*}}(s)=\inf_{\tilde{\pi}\in\Gamma}J_{\tilde{\pi}}(s)$.
∎

Under mild conditions on the MDP $M$, the action value function $Q^{*}_{M}$
can be learned iteratively using the Q-learning algorithm [44]. Similarly, for
stationary policies $\pi\in\Gamma_{S}$, the value function $J_{\pi}$ can be
learned iteratively. Thus, an agent playing the MDP $M$ and using a stationary
policy $\pi\in\Gamma_{S}$ may use an estimated surrogate of the inequality of
(2)—involving stochastic estimates of $Q^{*}_{M}$ and $J_{\pi}$—as a stopping
condition when searching for an $\epsilon$-optimal policy. This idea will
feature heavily in the subsequent sections; in particular, we will use an
analogous condition for our definition of subjective best-responding.

###  II-B $N$-Player Mean-Field Games

We are now ready to present the model of $N$-player mean-field games. The
model below differs from the classical model of mean-field games (as presented
in [1, 2] or [3]), which assumes a continuum of agents. Here, we consider
models with a possibly large but finite number of symmetric, weakly coupled
agents. Our model closely resembles the one used in [7], which studies
existence of equilibrium and allows for general state and actions spaces. In
contrast to [7], we restrict our attention to $N$-player mean-field games with
finite state and action spaces, and we consider a variety of observation
channels.

For $N\in\mathbb{N}$, a partially observed $N$-player mean-field game (MFG) is
described by the following list:

$\mathcal{G}=(\mathcal{N},X_{{\rm
loc}},\mathbb{Y},\mathbb{U},\\{\varphi^{i}\\}_{i\in\mathcal{N}},c,\beta,P_{{\rm
loc}},\nu_{0}).$ (3)

The list defining $\mathcal{G}$ is made up of the following components:

  * •

$\mathcal{N}$ is a set of $N$ players/agents;

  * •

$X_{{\rm loc}}$ is a finite set of states, and we let
$\textbf{X}:=\times_{i\in\mathcal{N}}X_{{\rm loc}}$. We refer to an element
$s\in X_{{\rm loc}}$ as a local state, and we refer to an element
$(s^{i})_{i\in\mathcal{N}}=\textbf{s}\in\textbf{X}$ as a global state, with
the $i^{\rm th}$ component of s denoting player $i$’s local state in global
state s. For each $\textbf{s}\in\textbf{X}$, we define an empirical measure
$\mu(\cdot|\textbf{s})\in\mathcal{P}(X_{{\rm loc}})$ as follows:

$\mu(B|\textbf{s})=\frac{1}{N}\sum_{i\in\mathcal{N}}\delta_{s^{i}}(B),\quad\forall
B\subseteq X_{{\rm loc}},$

  * and we denote the set of all empirical measures by ${\rm Emp}_{N}:=\\{\mu(\cdot|\textbf{s}):\textbf{s}\in\textbf{X}\\}$. An element $\mu\in{\rm Emp}_{N}$ is called a mean-field state;

  * •

For each $i\in\mathcal{N}$, $\varphi^{i}:\textbf{X}\to\mathbb{Y}$ is an
observation function, where $\mathbb{Y}$ is a finite set of observation
symbols. We refer to the pair
$(\mathbb{Y},\\{\varphi^{i}\\}_{i\in\mathcal{N}})$ as the observation channel;

  * •

$\mathbb{U}$ is a finite set of actions, and we let
$\textbf{U}:=\times_{i\in\mathcal{N}}\mathbb{U}$. An element $a\in\mathbb{U}$
is called an (individual) action, and an element
$(a^{i})_{i\in\mathcal{N}}=\textbf{a}\in\textbf{U}$ is called a joint action;

  * •

$c:X_{{\rm loc}}\times\mathcal{P}(X_{{\rm loc}})\times\mathbb{U}\to\mathbb{R}$
is a stage cost function;

  * •

$\beta\in(0,1)$ is a discount factor;

  * •

$P_{{\rm loc}}\in\mathcal{P}(X_{{\rm loc}}|X_{{\rm
loc}}\times\mathcal{P}(X_{{\rm loc}})\times\mathbb{U})$ is a transition kernel
governing local state transitions for each player;

  * •

$\nu_{0}\in\mathcal{P}(\textbf{X})$ is an initial probability distribution for
the global state variable.

Play of the MFG $\mathcal{G}$ is described as follows: at time
$t\in\mathbb{Z}_{\geq 0}$, player $i$’s local state is denoted $x^{i}_{t}$,
while the global state variable is denoted by $\textbf{x}_{t}$ and the mean-
field state is denoted by $\mu_{t}:=\mu(\cdot|\textbf{x}_{t})$. Player $i$
observes its local observation variable
$y^{i}_{t}:=\varphi^{i}(\textbf{x}_{t})$ and uses its locally observable
history variable, defined below, to select an action $u^{i}_{t}\in\mathbb{U}$.
The joint action random variable at time $t$ is denoted $\textbf{u}_{t}$.
Player $i$ then incurs a cost $c^{i}_{t}:=c(x^{i}_{t},\mu_{t},u^{i}_{t})$, and
player $i$’s local state variable evolves according to $x^{i}_{t+1}\sim
P_{{\rm loc}}(\cdot|x^{i}_{t},\mu_{t},u^{i}_{t})$. This process is then
repeated at time $t+1$, and so on.

We now formalize the high-level description above in a manner similar to the
formalization of POMDPs, with distinctions between the overall system history
and each player’s locally observable histories. For any $t\in\mathbb{Z}_{\geq
0}$, we define the sets

$\textbf{H}_{t}:=\left(\textbf{X}\times\textbf{U}\right)^{t}\times\textbf{X},\quad\text{and}\quad
H_{t}:=\mathcal{P}(\textbf{X})\times\left(\mathbb{Y}\times\mathbb{U}\times\mathbb{R}\right)^{t}\times\mathbb{Y}.$

For given $t\geq 0$, the set $\textbf{H}_{t}$ represents the set of overall
system histories of length $t$, while the set $H_{t}$ is the set of histories
of length $t$ that an individual player in the game $\mathcal{G}$ may observe.
Elements of $\textbf{H}_{t}$ are called system histories of length $t$, and we
use
$\textbf{h}_{t}=(\textbf{x}_{0},\textbf{u}_{0},\cdots,\textbf{u}_{t-1},\textbf{x}_{t})$,
a random quantity taking values in $\textbf{H}_{t}$, to denote the $t^{\rm
th}$ system history variable. Similarly, elements of $H_{t}$ are called
_observable histories of length $t$_, and for player $i\in\mathcal{N}$, we use
$h^{i}_{t}=(\nu_{0},y^{i}_{0},u^{i}_{0},c^{i}_{0},\cdots,c^{i}_{t-1},y^{i}_{t})$,
a random quantity taking values in $H_{t}$, to denote player $i$’s $t^{\rm
th}$ _locally observable history variable_.

######  Definition 6 (Policies)

A policy for player $i\in\mathcal{N}$ is defined as a sequence
$\pi^{i}=(\pi^{i}_{t})_{t\geq 0}$ such that
$\pi^{i}_{t}\in\mathcal{P}(\mathbb{U}|H_{t})$ for every $t\geq 0$. We let
$\Gamma^{i}$ denote the set of all policies for player $i$.

######  Definition 7 (Stationary Policies)

Let $i\in\mathcal{N}$. A policy $\pi^{i}\in\Gamma^{i}$ is called _stationary_
if there exists a transition kernel
$f^{i}\in\mathcal{P}(\mathbb{U}|\mathbb{Y})$ such that for any $t\geq 0$ and
any $\tilde{h}_{t}=(\nu,\tilde{y}_{0},\dots,\tilde{y}_{t})\in H_{t}$, we have
$\pi^{i}_{t}(\cdot|\tilde{h}_{t})=f^{i}(\cdot|\tilde{y}_{t})$. We let
$\Gamma^{i}_{S}$ denote the set of stationary policies for player $i$.

Remark: The set of policies—and therefore learning algorithms—available to an
agent depends on the set of locally observable histories, which itself depends
on the observation channel $(\mathbb{Y},\\{\varphi^{i}\\}_{i\in\mathcal{N}})$.
In this paper, our focus is on _independent learners_ , which are learners
that do not use the joint action information in their learning algorithms,
either because they are intentionally ignoring this information or because
they are unable to observe the joint actions. Here, we have chosen to
incorporate this constraint into the information structure. Moreover, to
underscore the importance of learning in our study, we also do not assume that
the players know the cost function $c$. Instead, we assume only that they
receive feedback costs in response to particular system interactions. These
assumptions on the information structure resemble those of other work on
independent learners, e.g. [17, 18, 20, 25, 26, 45, 46], and can be contrasted
with work on _joint action learners_ , where the locally observable history
variables also include the joint action history.

Notation: We let $\bm{\Gamma}:=\times_{i\in\mathcal{N}}\bm{\Gamma}^{i}$ denote
the set of joint policies. To isolate player $i$’s component in a particular
joint policy $\bm{\pi}\in\bm{\Gamma}$, we write
$\bm{\pi}=(\pi^{i},\bm{\pi}^{-i})$, where $-i$ is used in the agent index to
represent all agents other than $i$. Similarly, we write the joint policy set
as $\bm{\Gamma}=\Gamma^{i}\times\bm{\Gamma}^{-i}$, a joint action may be
written as $\textbf{a}=(a^{i},\textbf{a}^{-i})\in\textbf{U}$, and so on.

For each player $i\in\mathcal{N}$, we identify the set $\Gamma^{i}_{S}$ with
the set $\mathcal{P}(\mathbb{U}|\mathbb{Y})$ of transition kernels on
$\mathbb{U}$ given $\mathbb{Y}$. When convenient, a stationary policy
$\pi^{i}\in\Gamma^{i}_{S}$ is treated as if it were an element of
$\mathcal{P}(\mathbb{U}|\mathbb{Y})$, and reference to the locally observable
history variable is omitted. For each $i\in\mathcal{N}$, we introduce the
metric $d^{i}$ on $\Gamma^{i}_{S}$, defined by

$d^{i}(\pi^{i},\tilde{\pi}^{i}):=\max\\{|\pi^{i}(a^{i}|y)-\tilde{\pi}^{i}(a^{i}|y)|:y\in\mathbb{Y},a^{i}\in\mathbb{U}\\},\quad\forall\pi^{i},\tilde{\pi}^{i}\in\Gamma^{i}_{S}.$

We metrize the set of stationary joint policies $\bm{\Gamma}$ with a metric d,
defined as

$\textbf{d}(\bm{\pi},\tilde{\bm{\pi}}):=\max_{i\in\mathcal{N}}d^{i}(\pi^{i},\tilde{\pi}^{i}),\quad\forall\bm{\pi},\tilde{\bm{\pi}}\in\bm{\Gamma}_{S}.$

A metric $\textbf{d}^{-i}$ for the set $\bm{\Gamma}^{-i}_{S}$ is defined
analogously to d. We have that the sets
$\\{\Gamma^{i}_{S}\\}_{i\in\mathcal{N}}$,
$\\{\bm{\Gamma}^{-i}_{S}\\}_{i\in\mathcal{N}}$ and $\bm{\Gamma}_{S}$ are all
compact in the topologies induced by the corresponding metrics.

For any joint policy $\bm{\pi}=(\pi^{i})_{i\in\mathcal{N}}$ and initial
distribution $\nu$, there exists a unique probability measure ${\rm
Pr}^{\bm{\pi}}_{\nu}$ on trajectories in
$(\textbf{X}\times\textbf{U})^{\infty}$ such that the following holds:

  * •

${\rm Pr}^{\bm{\pi}}_{\nu}\left(\textbf{x}_{0}\in\cdot\right)=\nu_{0}(\cdot)$;

  * •

For any $i\in\mathcal{N}$ and $t\geq 0$, ${\rm
Pr}^{\bm{\pi}}_{\nu}\left(u^{i}_{t}\in\cdot\middle|h^{i}_{t}\right)=\pi^{i}_{t}\left(\cdot|h^{i}_{t}\right)$;

  * •

The collection $\\{u^{j}_{t}\\}_{j\in\mathcal{N}}$ is jointly independent
given $\textbf{h}_{t}$;

  * •

For any $i\in\mathcal{N}$ and $t\geq 0$, ${\rm
Pr}^{\bm{\pi}}_{\nu}\left(x^{i}_{t+1}\in\cdot\middle|\textbf{h}_{t},\textbf{u}_{t}\right)=P_{{\rm
loc}}\left(\cdot\middle|x^{i}_{t},\mu(\cdot|\textbf{x}_{t}),u^{i}_{t}\right)$;

  * •

The collection $\\{x^{j}_{t+1}\\}_{j\in\mathcal{N}}$ is jointly independent
given $\textbf{h}_{t},\textbf{u}_{t}$.

For each $\bm{\pi}\in\bm{\Gamma}$ and $\nu\in\mathcal{P}(\textbf{X})$, we let
$E^{\bm{\pi}}_{\nu}$ denote the expectation associated to ${\rm
Pr}^{\bm{\pi}}_{\nu}$ and we use it to define player $i$’s (state) value
function:

$J^{i}_{\bm{\pi}}(\nu):=E^{\bm{\pi}}_{\nu}\left[\sum_{t=0}^{\infty}\beta^{t}c^{i}_{t}\right]=E^{\bm{\pi}}_{\nu}\left[\sum_{t=0}^{\infty}\beta^{t}c(x^{i}_{t},\mu_{t},u^{i}_{t})\right].$

######  Lemma 2 (Continuity of Value Functions)

Let $\mathcal{G}$ be the partially observed $N$-player mean-field game defined
in (3). For any initial measure $\nu\in\mathcal{P}(\textbf{X})$ and any player
$i\in\mathcal{N}$, the mapping $\bm{\pi}\mapsto J^{i}_{\bm{\pi}}(\nu)$ is
continuous on $\bm{\Gamma}_{S}$.

From the final expression in the definition of $J^{i}_{\bm{\pi}}(\nu)$, one
can see that player $i$’s objective is only weakly coupled with the rest of
the system: player $i$’s costs depend on the global state and joint action
sequences $\\{\textbf{x}_{t},\textbf{u}_{t}\\}_{t\geq 0}$ only through player
$i$’s components $\\{x^{i}_{t},u^{i}_{t}\\}_{t\geq 0}$, the mean-field state
sequence $\\{\mu_{t}\\}_{t\geq 0}$, and the subsequent influence
$\\{\mu_{t}\\}_{t\geq 0}$ has on the evolution of $\\{x^{i}_{t}\\}_{t\geq 0}$.
Nevertheless, player $i$’s objective function does depend on the policies of
the remaining players. This motivates the following definitions.

######  Definition 8 (Best-Response)

Let $\epsilon\geq 0$, $\nu\in\mathcal{P}(\textbf{X})$, $i\in\mathcal{N}$, and
$\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}$. A policy $\pi^{*i}\in\Gamma^{i}$ is called
an $\epsilon$-_best-response to $\bm{\pi}^{-i}$ with respect to $\nu$_ if

$J^{i}_{(\pi^{*i},\bm{\pi}^{-i})}(\nu)\leq\inf_{\tilde{\pi}^{i}\in\Gamma^{i}}J^{i}_{(\tilde{\pi}^{i},\bm{\pi}^{-i})}(\nu)+\epsilon.$

For $i\in\mathcal{N}$, $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}$, $\epsilon\geq 0$,
and $\nu\in\mathcal{P}(\textbf{X})$, we let ${\rm
BR}^{i}_{\epsilon}(\bm{\pi}^{-i},\nu)\subseteq\Gamma^{i}$ denote player $i$’s
set of $\epsilon$-best-responses to $\bm{\pi}^{-i}$ with respect to $\nu$. If,
additionally, $\pi^{i}\in{\rm BR}^{i}_{\epsilon}(\bm{\pi}^{-i},\nu)$ for all
$\nu\in\mathcal{P}(\textbf{X})$, then $\pi^{i}$ is called a _uniform
$\epsilon$-best-response to $\bm{\pi}^{-i}$_. The set of uniform
$\epsilon$-best-responses to a policy $\bm{\pi}^{-i}$ is denoted ${\rm
BR}^{i}_{\epsilon}(\bm{\pi}^{-i})$.

######  Definition 9 (Equilibrium)

Let $\epsilon\geq 0$, $\nu\in\mathcal{P}(\textbf{X})$, and
$\bm{\pi}^{*}\in\bm{\Gamma}$. The joint policy $\bm{\pi}^{*}$ is called an
_$\epsilon$ -equilibrium with respect to $\nu$_ if $\pi^{*i}$ is an
$\epsilon$-best-response to $\bm{\pi}^{*-i}$ with respect to $\nu$ for every
player $i\in\mathcal{N}$. Additionally, if $\bm{\pi}^{*}\in\bm{\Gamma}$ is an
$\epsilon$-equilibrium with respect to every $\nu\in\mathcal{P}(\textbf{X})$,
then $\bm{\pi}^{*}$ is called a _perfect $\epsilon$-equilibrium._

For $\epsilon\geq 0$ and $\nu\in\mathcal{P}(\textbf{X})$, we let
$\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}(\nu)\subset\bm{\Gamma}$ denote the set
of $\epsilon$-equilibrium policies with respect to $\nu$, and we let
$\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}$ denote the set of perfect
$\epsilon$-equilibrium policies. Furthermore, we let
$\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}_{S}(\nu):=\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}(\nu)\cap\bm{\Gamma}_{S}$
for each $\nu\in\mathcal{P}(\textbf{X})$ and we let
$\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}_{S}:=\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}\cap\bm{\Gamma}_{S}$.

In the next section, we will describe conditions under which
$\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}_{S}\not=\varnothing$, and we will state
criteria for verifying whether a particular stationary policy
$\pi^{i}\in\Gamma^{i}_{S}$ is an $\epsilon$-best-response to the stationary
joint policy $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$. These criteria will be
analogous to the state-by-state inequality for MDPs presented in (2). Those
results will serve as temporarily postponed motivation for the following
definitions.

######  Definition 10 (Subjective Function Family)

Let $\mathcal{G}$ be the $N$-player MFG in (3). Let
$\mathcal{V}=\left\\{V^{i}_{\bm{\pi}}:\mathbb{Y}\to\mathbb{R}\middle|i\in\mathcal{N},\bm{\pi}\in\bm{\Gamma}_{S}\right\\}$
and let
$\mathcal{W}=\left\\{W^{i}_{\bm{\pi}}:\mathbb{Y}\times\mathbb{U}\to\mathbb{R}\middle|i\in\mathcal{N},\bm{\pi}\in\bm{\Gamma}_{S}\right\\}$
be two families of functions. Then, the pair $(\mathcal{V},\mathcal{W})$ is
called a _subjective function family for $\mathcal{G}$._

######  Definition 11 (Subjective Best-Responding)

Let $\epsilon\geq 0$, $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$, and let
$(\mathcal{V},\mathcal{W})$ be a subjective function family for $\mathcal{G}$.
A policy $\pi^{*i}\in\Gamma^{i}_{S}$ is called a
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-best-response to
$\bm{\pi}^{-i}$ if we have

$V^{i}_{(\pi^{*i},\bm{\pi}^{-i})}(y)\leq\min_{a^{i}\in\mathbb{U}}W^{i}_{(\pi^{*i},\bm{\pi}^{-i})}(y,a^{i})+\epsilon,\quad\forall
y\in\mathbb{Y}.$

For a fixed player $i\in\mathcal{N}$, a stationary joint policy
$\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$, and a subjective function family
$(\mathcal{V},\mathcal{W})$, we let

${\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i},\mathcal{V},\mathcal{W})\subseteq\Gamma^{i}_{S}$

denote player $i$’s (possibly empty) set of
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-best-responses to
$\bm{\pi}^{-i}$.

######  Definition 12 (Subjective Equilibrium)

Let $\epsilon\geq 0$ and let $(\mathcal{V},\mathcal{W})$ be a subjective
function family for $\mathcal{G}$. A joint policy
$\bm{\pi}^{*}\in\bm{\Gamma}_{S}$ is called a
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-equilibrium for
$\mathcal{G}$ if, for every $i\in\mathcal{N}$, $\pi^{*i}$ is a
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-best-response to
$\bm{\pi}^{*-i}$.

For any subjective function family $(\mathcal{V},\mathcal{W})$, we let ${\rm
Subj}_{\epsilon}(\mathcal{V},\mathcal{W})\subseteq\bm{\Gamma}_{S}$ denote the
(possibly empty) set of $(\mathcal{V},\mathcal{W})$-subjective
$\epsilon$-equilibrium policies for $\mathcal{G}$.

###  II-C On the Observation Channel

To this point, we have left the particular observation channel
$(\mathbb{Y},\\{\varphi^{i}\\}_{i\in\mathcal{N}})$ unspecified. We conclude
this section by offering three alternatives for the observation channel. The
particular choice used in practice will depend on the application area: in
some instances, there will be a natural restriction of information leading to
a particular observation channel. In other instances, information may be
plentiful in principle but agents may voluntarily compress a larger/more
informative observation variable for the purposes of function approximation.
We offer additional discussion on this topic in Section VII, where we compare
this work with other recent works on learning in mean-field games.

######  Assumption 1 (Global State Observability)

$\mathbb{Y}=\textbf{X}$ and $\varphi^{i}(\textbf{s})=\textbf{s}$ for each
global state $\textbf{s}\in\textbf{X}$ and player $i\in\mathcal{N}$.

######  Assumption 2 (Mean-Field State Observability)

$\mathbb{Y}=X_{{\rm loc}}\times{\rm Emp}_{N}$ and
$\varphi^{i}(\textbf{s})=(s^{i},\mu(\cdot|\textbf{s}))$ for each global state
$\textbf{s}\in\textbf{X}$ and player $i\in\mathcal{N}$.

######  Assumption 3 (Compressed State Observability)

For some $k\in\mathbb{N}$, let $[k]:=\\{1,2,\dots,k\\}$ and let
$f:\mathcal{P}(X_{{\rm loc}})\to[k]$. Then, $\mathbb{Y}=X_{{\rm
loc}}\times[k]$ and for each $i\in\mathcal{N}$, $\textbf{s}\in\textbf{X}$, we
have $\varphi^{i}(\textbf{s})=(s^{i},f(\mu(\cdot|\textbf{s})).$

######  Assumption 4 (Local State Observability)

$\mathbb{Y}=X_{{\rm loc}}$ and for each $i\in\mathcal{N}$,
$\textbf{s}\in\textbf{X}$, we have $\varphi^{i}(\textbf{s})=s^{i}.$

The mean-field state observability assumption of Assumption 2 is the standard
observation channel considered in works on mean-field games, see e.g. [7] and
the references therein. The observation channel of Assumption 3 can be
motivated using the discussion above; it serves to lessen the computational
burden at a given learning agent in a partially observed $N$-player mean-field
game and, as we discuss in Section VII, may be a more appropriate modelling
assumption in some applications.

Remark: By taking $k=1$, we see that local state observability is in fact a
special case of compressed state observability, where the compressed
information about the mean-field state is totally uninformative. We include
Assumption 4 separately to highlight the importance of this set-up, even
though mathematically all results under Assumption 4 will automatically follow
from those involving Assumption 3.

##  III Stationary Equilibrium Policies: Existence under Two Observation
Channels

We now present some results relating partially observed $N$-player mean-field
games to partially observed and fully observed Markov decision problems. We
then leverage these connections to present results on the existence of
stationary equilibrium policies. These results will guide the analysis and
development of theoretical constructs in the subsequent sections. In
particular, they will be used as auxiliary results when proving the existence
of subjective equilibria.

###### Lemma 3

Let $\mathcal{G}$ be a partially observed $N$-player MFG. Fix player
$i\in\mathcal{N}$ and let $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$ be a
stationary policy for the remaining players. Then, player $i$ faces a
partially observed Markov decision problem $M_{\bm{\pi}^{-i}}$ with partially
observed state process $\\{\textbf{x}_{t}\\}_{t\geq 0}$.

Lemma 3, whose proof is straightforward and omitted, gives conditions under
which a player faces a POMDP. Under certain additional conditions, described
below in Corollary 1 and in Lemma 8, one can show that player
$i\in\mathcal{N}$ faces a fully observed MDP. When player $i$ faces an MDP in
its observation variable, the classical theory of MDPs and reinforcement
learning can be brought to bear on player $i$’s optimization problem, leading
to results on the existence of certain equilibrium policies and
characterization of one’s best-response set.

###  III-A Existence of Stationary Equilibrium under Global State
Observability

###### Corollary 1

Let $\mathcal{G}$ be a partially observed $N$-player MFG in which Assumption 1
holds. Fix player $i\in\mathcal{N}$ and let
$\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$ be a stationary policy for the
remaining players. Then, player $i$ faces a (fully observed) Markov decision
problem $M_{\bm{\pi}^{-i}}$ with controlled state process
$\\{y^{i}_{t}\\}_{t\geq 0}$, where
$y^{i}_{t}=\varphi^{i}(\textbf{x}_{t})=\textbf{x}_{t}$ for every $t\geq 0$.

Under Assumption 1, Lemma 3 immediately yields Corollary 1, which says that if
$\bm{\pi}^{-i}$ is stationary, then player $i$ faces a multi-agent environment
that is equivalent to a single-agent MDP $M_{\bm{\pi}^{-i}}$. As such, we can
consider player $i$’s Q-function for this environment, which we denote by
$Q^{*i}_{\bm{\pi}^{-i}}:\textbf{X}\times\mathbb{U}\to\mathbb{R}$.

$Q^{*i}_{\bm{\pi}^{-i}}\left(\textbf{s},a^{i}\right):=E^{\bm{\pi}^{*}}_{\nu_{0}}\left[\sum_{t=0}^{\infty}\beta^{t}c(x^{i}_{0},\mu(\cdot|\textbf{x}_{t}),u^{i}_{t})\middle|\textbf{x}_{0}=\textbf{s},u^{i}_{0}=a^{i}\right],$

for each $(\textbf{s},a^{i})\in\textbf{X}\times\mathbb{U}$, where
$\bm{\pi}^{*}=(\pi^{*i},\bm{\pi}^{-i})$ and $\pi^{*i}\in\Gamma^{i}_{S}\cap{\rm
BR}^{i}_{0}$.

The value $Q^{*i}_{\bm{\pi}^{-i}}(\textbf{s},a^{i})$ represents the optimal
cost-to-go to player $i$ when play begins at global state
$\textbf{s}\in\textbf{X}$, player $i$ takes action $a^{i}\in\mathbb{U}$ at
time 0 and follows the policy $\pi^{*i}$ thereafter, and the remaining players
play according to the stationary policy $\bm{\pi}^{-i}$.

By Lemma 1, player $i$ can verify whether a given stationary policy
$\pi^{i}\in{\rm BR}^{i}_{\epsilon}(\bm{\pi}^{-i})\cap\Gamma^{i}_{S}$ by
verifying whether

$\max_{\textbf{s}\in\textbf{X}}\left(J^{i}_{(\pi^{i},\bm{\pi}^{-i})}(\textbf{s})-\min_{a^{i}\in\mathbb{U}}Q^{*i}_{\bm{\pi}^{-i}}(\textbf{s},a^{i})\right)\leq\epsilon.$

We will use the following lemmas, whose proofs are mechanical and may be found
in [46].

###### Lemma 4

Let $\mathcal{G}$ be an $N$-player MFG satisfying Assumption 1. Let
$i\in\mathcal{N}$ and $(\textbf{s},a^{i})\in\textbf{X}\times\mathbb{U}$. The
mapping $\bm{\pi}^{-i}\mapsto Q^{*i}_{\bm{\pi}^{-i}}(\textbf{s},a^{i})$ is
continuous on $\bm{\Gamma}^{-i}_{S}$.

###### Lemma 5

Let $\mathcal{G}$ be an $N$-player MFG satisfying Assumption 1. Let
$i\in\mathcal{N}$ and $\textbf{s}\in\textbf{X}$. Then, the mapping
$\bm{\pi}^{-i}\mapsto\min_{a^{i}\in\mathbb{U}}Q^{*i}_{\bm{\pi}^{-i}}(\textbf{s},a^{i})$
is continuous on $\bm{\Gamma}^{-i}_{S}$.

###### Lemma 6

Let $\mathcal{G}$ be an $N$-player MFG satisfying Assumption 1. For any player
$i\in\mathcal{N}$ and $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$, the mapping

$\pi^{i}\mapsto\max_{\textbf{s}\in\textbf{X}}\left(J^{i}_{(\pi^{i},\bm{\pi}^{-i})}(\textbf{s})-\min_{a^{i}\in\mathbb{U}}Q^{*i}_{\bm{\pi}^{-i}}(\textbf{s},a^{i})\right)$

is continuous on $\Gamma^{i}_{S}$.

###### Lemma 7

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game
satisfying Assumption 1. Then, there exists a stationary policy that is a
perfect equilibrium. That is,
$\bm{\Gamma}^{0{\rm\text{-}eq}}_{S}\not=\varnothing$.

A partially observed $N$-player mean-field game with global state
observability (Assumption 1) is a special case of the finite $N$-player
stochastic games studied in [47], and so Lemma 7 follows from [47, Theorem 2].
Nevertheless, it is informative to study the proof technique, as it can be
used to prove existence of equilibrium policies under other observation
channels, where existence does not follow from [47, Theorem 2].

The proof of Lemma 7 involves invoking Kakutani’s fixed point theorem on a
product best-response mapping from $\bm{\Gamma}_{S}$ to its power set, where
the $i^{\rm th}$ component maps $\bm{\pi}\mapsto{\rm
BR}^{i}_{0}(\bm{\pi}^{-i})\cap\Gamma^{i}_{S}$ for each
$\bm{\pi}\in\bm{\Gamma}_{S}$. By Corollary 1, one sees that each component
mapping maps to non-empty, convex, and compact sets. The upper hemicontinuity
of the component mappings can be established using the Lemma 2 and Lemmas 4–6,
above.

From the proof sketch for Lemma 7, one can see the crucial role played by the
MDP structure facing a given player when the remaining players follow a
stationary policy. When Assumption 1 does not hold and the observation channel
compresses the global state information, in general player $i$ will not face
an MDP with controlled state process $\\{y^{i}_{t}\\}_{t\geq 0}$, and as a
result replicating this line of proof not possible for general observation
channels $(\mathbb{Y},\\{\varphi^{i}\\}_{i\in\mathcal{N}})$. As we discuss
below, it is possible to employ the same proof technique in the special case
of mean-field state observability (Assumption 2), although additional care
must be given to account for the loss of global state observability.

###  III-B Existence of Stationary Equilibrium Under Mean-Field State
Observability

######  Definition 13 (Mean-Field Symmetric Policies)

Let $i,j\in\mathcal{N}$ and let $\pi^{i}\in\Gamma^{i}_{S}$,
$\pi^{j}\in\Gamma^{j}_{S}$ be stationary policies. We say that the policies
$\pi^{i}$ and $\pi^{j}$ are _mean-field symmetric_ if both are identified with
the same transition kernel in $\mathcal{P}(\mathbb{U}|\mathbb{Y})$. For any
subset of players $I\subset\mathcal{N}$, a collection of policies
$\\{\pi^{i}\\}_{i\in I}$ is called mean-field symmetric if, for every $i,j\in
I$, we have that $\pi^{i}$ and $\pi^{j}$ are mean-field symmetric.

###### Lemma 8

Let $\mathcal{G}$ be an $N$-player MFG, let $i\in\mathcal{N}$, and let
Assumption 2 hold. If $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$ is mean-field
symmetric, then $i$ faces a fully observed MDP $M_{\bm{\pi}^{-i}}$ with
controlled state process $\\{y^{i}_{t}\\}_{t\geq 0}$, where
$y^{i}_{t}=\varphi^{i}(\textbf{x}_{t})=(x^{i}_{t},\mu(\cdot|\textbf{x}_{t}))$
for all $t\geq 0$.

Lemma 8 is proved in Appendix -A. From this proof, one observes two things:
first, the condition that $\bm{\pi}^{-i}$ is mean-field symmetric cannot be
relaxed in general; second, if $\bm{\pi}^{-i}$ is mean-field symmetric and
$\nu,\nu^{\prime}\in\mathcal{P}(\textbf{X})$ are arbitrary initial
distributions, then for any policy $\pi^{i}\in\Gamma^{i}$, putting
$\bm{\pi}=(\pi^{i},\bm{\pi}^{-i})$, we have

${\rm Pr}^{\bm{\pi}}_{\nu}(\cdot|y^{i}_{0}=y,u^{i}_{0}=a^{i})={\rm
Pr}^{\bm{\pi}}_{\nu^{\prime}}(\cdot|y^{i}_{0}=y,u^{i}_{0}=a^{i}),\quad\forall(y,a^{i})\in\mathbb{Y}\times\mathbb{U}.$
(4)

In light of Lemma 8, we define the Q-function for player $i$ when playing
$\mathcal{G}$ against a mean-field symmetric policy
$\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$ as

$Q^{*i}_{\bm{\pi}^{-i}}(y,a^{i}):=E^{(\pi^{*i},\bm{\pi}^{-i})}_{\nu}\left[\sum_{t=0}^{\infty}\beta^{t}c(x^{i}_{t},\mu(\cdot|\textbf{x}_{t}),u^{i}_{t})\middle|y^{i}_{0}=y,u^{i}_{0}=a^{i}\right],\quad\forall
a^{i}\in\mathbb{U},$

for every
$y\in\varphi^{i}(\textbf{X})=\\{\varphi^{i}(\textbf{s}):\textbf{s}\in\textbf{X}\\}$,
where $\pi^{*i}\in{\rm BR}^{i}_{0}(\bm{\pi}^{-i})\cap\Gamma^{i}_{S}$ is a
best-response to $\bm{\pi}^{-i}$ and $\nu\in\mathcal{P}(\textbf{X})$ is
arbitrary. (That $\nu$ can be arbitrarily chosen follows from the preceding
discussion culminating in (4).) For elements
$y\in\textbf{X}\setminus\varphi^{i}(\textbf{X})$, we may define
$Q^{*i}_{\bm{\pi}^{-i}}(y,a^{i})$ arbitrarily, say
$Q^{*i}_{\bm{\pi}^{-i}}(y,\cdot)\equiv 0$.

For any player $i\in\mathcal{N}$, we let $\bm{\Gamma}^{-i}_{S,{\rm
sym}}\subset\bm{\Gamma}^{-i}_{S}$ denote the set of mean-field symmetric joint
policies for the remaining players, and we let $\bm{\Gamma}_{S,{\rm
sym}}\subset\bm{\Gamma}_{S}$ denote the set of mean-field symmetric joint
policies. We note that the sets $\Gamma^{i}_{S}$ and $\bm{\Gamma}^{-i}_{S,{\rm
sym}}$ are in bijection, and we define ${\rm
sym}^{i}:\Gamma^{i}_{S}\to\bm{\Gamma}^{-i}_{S,{\rm sym}}$ by

${\rm
sym}^{i}(\pi^{i})=\left(\pi^{i}\right)_{j\in\mathcal{N}\setminus\\{i\\}},\quad\forall\pi^{i}\in\Gamma^{i}_{S}.$

We metrize $\bm{\Gamma}^{-i}_{S,{\rm sym}}$ using the metric $d^{i}$ on
$\Gamma^{i}_{S}$:

$\textbf{d}^{-i}_{{\rm sym}}\left({\rm sym}^{i}(\pi^{i}),{\rm
sym}^{i}(\tilde{\pi}^{i})\right):=d^{i}(\pi^{i},\tilde{\pi}^{i}),\quad\forall\pi^{i},\tilde{\pi}^{i}\in\Gamma^{i}_{S}.$

We note that the metric $\textbf{d}^{-i}_{{\rm sym}}$ is equivalent to the
metric $\textbf{d}^{-i}$ restricted to $\bm{\Gamma}^{-i}_{S,{\rm sym}}$. In
the lemmas below—whose proofs resemble those of Lemmas 4–6—continuity of
functions with domain $\bm{\Gamma}^{-i}_{S,{\rm sym}}$ is with respect to the
topology induced by $\textbf{d}^{-i}_{{\rm sym}}$.

###### Lemma 9

Let $\mathcal{G}$ be an $N$-player mean-field game satisfying Assumption 2.
Fix $i\in\mathcal{N},(y,a^{i})\in\mathbb{Y}\times\mathbb{U}$. The mapping
$\bm{\pi}^{-i}\mapsto Q^{*i}_{\bm{\pi}^{-i}}(y,a^{i})$ is continuous on
$\bm{\Gamma}^{-i}_{S,{\rm sym}}$.

###### Lemma 10

Let $\mathcal{G}$ be an $N$-player mean-field game satisfying Assumption 2.
Fix $i\in\mathcal{N},y\in\mathbb{Y}$. The mapping
$\bm{\pi}^{-i}\mapsto\min_{a^{i}\in\mathbb{U}}Q^{*i}_{\bm{\pi}^{-i}}(y,a^{i})$
is continuous on $\bm{\Gamma}^{-i}_{S,{\rm sym}}$.

###### Lemma 11

Let $\mathcal{G}$ be an $N$-player mean-field game satisfying Assumption 2.
Fix $i\in\mathcal{N}$ and $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S,{\rm sym}}$.
Then, the mapping

$\pi^{i}\mapsto\max_{s\in\textbf{X}}\left(J^{i}_{(\pi^{i},\bm{\pi}^{-i})}(\textbf{s})-\min_{a^{i}\in\mathbb{U}}Q^{*i}_{\bm{\pi}^{-i}}(\varphi^{i}(\textbf{s}),a^{i})\right)$

is continuous on $\Gamma^{i}_{S}$.

The following theorem states that, under mean-field state observability, a
stationary perfect equilibrium exists for the partially observed $N$-player
mean-field game $\mathcal{G}$. This result is new, to our knowledge. The proof
technique parallels that of [47, Theorem 2], making the required modifications
to account for partial observability of the global state.

###### Theorem 1

Let $\mathcal{G}$ be an $N$-player mean-field game satisfying Assumption 2.
For any $\epsilon\geq 0$, there exists a perfect $\epsilon$-equilibrium policy
in $\bm{\Gamma}_{S}$. That is,
$\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}_{S}\not=\varnothing.$

###### Proof:

Fix player $i\in\mathcal{N}$. We define a point-to-set mapping
$B^{i}:\Gamma^{i}_{S}\to 2^{\Gamma^{i}_{S}}$ with $B^{i}(\pi^{i})={\rm
BR}^{i}_{\epsilon}({\rm sym}^{i}(\pi^{i}))\cap\Gamma^{i}_{S}$ for every
$\pi^{i}\in\Gamma^{i}_{S}$. By Lemma 8, we have that
$B^{i}(\pi^{i})\subseteq\Gamma^{i}_{S}$ is non-empty, convex, and compact for
each $\pi^{i}\in\Gamma^{i}_{S}$.

If $({\rm sym}^{i}(\tilde{\pi}^{i}))_{k\geq 0}$ is a sequence of mean-field
symmetric joint policies in $\bm{\Gamma}^{-i}_{S,{\rm sym}}$ converging to
some ${\rm sym}^{i}(\tilde{\pi}^{i}_{\infty})\in\bm{\Gamma}^{-i}_{S,{\rm
sym}}$ and $(\pi^{i}_{k})_{k\geq 0}$ is a sequence in $\Gamma^{i}_{S}$ such
that (1) $\lim_{k\to\infty}\pi^{i}_{k}=\pi^{i}_{\infty}\in\Gamma^{i}_{S}$ and
(2) for every $k\geq 0$, we have that $\pi^{i}_{k}\in{\rm
BR}^{i}_{\epsilon}({\rm sym}^{i}(\tilde{\pi}^{i}_{k}))$, then one can use
Lemma 2 and Lemmas 9–11 to conclude that $\pi^{i}_{\infty}\in{\rm
BR}^{i}_{\epsilon}({\rm
sym}^{i}(\tilde{\pi}^{i}_{\infty}))\cap\Gamma^{i}_{S}=B^{i}({\rm
sym}^{i}(\tilde{\pi}^{i}_{\infty}))$. This implies that the point-to-set
mapping $B^{i}$ is upper hemicontinuous.

We invoke Kakutani’s fixed point theorem on $B^{i}$ to obtain a fixed point
$\pi^{*i}\in B^{i}(\pi^{*i})={\rm BR}^{i}_{\epsilon}({\rm
sym}^{i}(\pi^{*i}))\cap\Gamma^{i}_{S}$. It follows by symmetry that
$\left(\pi^{*i},{\rm
sym}^{i}(\pi^{*i})\right)\in\Gamma^{i}_{S}\times\bm{\Gamma}^{-i}_{S,{\rm
sym}}\subset\bm{\Gamma}_{S}$ is a perfect $\epsilon$-equilibrium for
$\mathcal{G}$. ∎

Remark: (Compressed State Observability and Subjective Equilibria) Under
compressed state observability (Assumption 3), it is generally not true that a
given player $i\in\mathcal{N}$ faces a fully observed MDP with state process
$\\{y^{i}_{t}\\}_{t\geq 0}$ when the remaining players follow a stationary
policy. In fact, partial analogs of Corollary 1 and Lemma 8 do not generally
hold even when restricting the remaining players to use a policy in a small
subset of the stationary policies. Consequently, it cannot be guaranteed that
any stationary policy for player $i\in\mathcal{N}$ is an $\epsilon$-best-
response to a stationary joint policy for the remaining players. Moreover, the
proof technique of Theorem 1 cannot be used, as the required regularity
properties of the best-response correspondence may fail to hold. Accordingly,
we treat this set-up differently in our results below.

##  IV Convergence of Naive Single-Agent Learning under Stationary Policies

In this section, we study the convergence of learning iterates obtained when
an independent learning agent, player $i\in\mathcal{N}$ in our mean-field game
$\mathcal{G}$, naively runs single-agent RL algorithms that treats its
observation variable $\\{y^{i}_{t}\\}_{t\geq 0}$ as though it were the state
variable of a MDP. This learning process is formalized in Algorithm 1, below,
where we have fixed the policies of all players to be stationary. By fixing
the policies of the remaining players $-i$ to be stationary, this section
focuses on the effect that decentralized information has on independent
learners, leaving aside the well-known challenge of non-stationary [48].

We begin with an assumption on the transition kernel $P_{{\rm loc}}$. For
intuitive simplicity, we state this assumption in terms of the underlying
state process.

###### Assumption 5

Under any soft stationary policy $\bm{\pi}\in\bm{\Gamma}_{S}$, the global
state process $\\{\textbf{x}_{t}\\}_{t\geq 0}$ is an irreducible, aperiodic
Markov chain on X.

###### Theorem 2

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game for which
Assumption 5 holds, and let $\bm{\pi}\in\bm{\Gamma}_{S}$ be soft. Suppose
player $i\in\mathcal{N}$ uses Algorithm 1. We have the following:

  1. 1.

There exist deterministic functions
$\tilde{V}^{*i}_{\bm{\pi}}:\mathbb{Y}\to\mathbb{R}$ and
$\tilde{W}^{*i}_{\bm{\pi}}:\mathbb{Y}\times\mathbb{U}\to\mathbb{R}$ such that,
for any $\nu\in\mathcal{P}(\textbf{X})$,

$\lim_{t\to\infty}\bar{J}^{i}_{t}=\tilde{V}^{*i}_{\bm{\pi}}\quad\text{and}\quad\lim_{t\to\infty}\bar{Q}^{i}_{t}=\tilde{W}^{*i}_{\bm{\pi}}\quad{\rm
Pr}^{\bm{\pi}}_{\nu}\text{-almost surely.}$

  2. 2.

If Assumption 1 holds, then
$\tilde{V}^{*i}_{\bm{\pi}}(\textbf{s})=J^{i}_{\bm{\pi}}(\textbf{s})$ for all
$\textbf{s}\in\textbf{X}$ and
$\tilde{W}^{*i}_{\bm{\pi}}=Q^{*i}_{\bm{\pi}^{-i}}$.

  3. 3.

If Assumption 2 holds and $\bm{\pi}^{-i}$ is mean-field symmetric, then
$\tilde{V}^{*i}_{\bm{\pi}}(\varphi^{i}(\textbf{s}))=J^{i}_{\bm{\pi}}(\textbf{s})$
for all $\textbf{s}\in\textbf{X}$ and
$\tilde{W}^{*i}_{\bm{\pi}}=Q^{*i}_{\bm{\pi}^{-i}}$.

###### Proof:

By Lemma 3, player $i$ faces a POMDP with observation sequence
$\\{y^{i}_{t}\\}_{t\geq 0}$ and underlying state process
$\\{\textbf{x}_{t}\\}_{t\geq 0}$. By Assumption 5 and the assumed softness of
$\bm{\pi}$, we have that all pairs
$(\textbf{s},a^{i})\in\textbf{X}\times\mathbb{U}$ are visited infinitely often
${\rm Pr}^{\bm{\pi}}_{\nu_{0}}$-almost surely. We can therefore invoke [49,
Theorem 4.1] to establish the almost sure convergence of Q-factor iterates
$\\{\widehat{Q}^{i}_{t}\\}_{t\geq 0}$. The same analysis can be used to
establish the convergence of the value function iterates
$\\{\widehat{J}^{i}_{t}\\}_{t\geq 0}$. This proves the first part.

By Corollary 1, under Assumption 1, player $i$ faces an MDP with state process
$\\{\textbf{x}_{t}\\}_{t\geq 0}$. Again by the softness of $\bm{\pi}$ and
Assumption 5, each $(\textbf{s},a^{i})\in\textbf{X}\times\mathbb{U}$ is
visited infinitely often almost surely. The convergence of Q-factors under
these conditions is well-known; see for instance [50]. The same analysis can
be used to prove that
$\lim_{t\to\infty}\widehat{J}^{i}_{t}(\textbf{s})=J^{i}_{\bm{\pi}}(\textbf{s})$
almost surely for each $\textbf{s}\in\textbf{X}$, proving the second part.

The proof of the third part parallels that of the second part, replacing
Corollary 1 by Lemma 8 and replacing $\textbf{x}_{t}$ by
$y^{i}_{t}=(x^{i}_{t},\mu(\cdot|\textbf{x}_{t}))$ as needed. ∎

1

2Initialize Soft $\bm{\pi}\in\bm{\Gamma}_{S}$,
$\bar{Q}^{i}_{0}=0\in\mathbb{R}^{\mathbb{Y}\times\mathbb{U}}$ and
$\bar{J}^{i}_{0}=0\in\mathbb{R}^{\mathbb{Y}}$

3

4for $t\geq 0$ ($t^{th}$ stage)

5

6 Player $i$ selects $u^{i}_{t}\sim\pi^{i}(\cdot|y^{i}_{t})$

7

8 Players $-i$ select $\textbf{u}^{-i}_{t}$ according to $\bm{\pi}^{-i}$

9

10 Player $i$ observes $y^{i}_{t+1}$ and cost
$c^{i}_{t}:=c^{i}(\textbf{x}_{t},u^{i}_{t},\textbf{u}^{-i}_{t})$

11

12
$n^{i}_{t}:=\sum_{k=0}^{t}\textbf{1}\\{(y^{i}_{k},u^{i}_{k})=(y^{i}_{t},u^{i}_{t})\\}$

13

14 $m^{i}_{t}:=\sum_{k=0}^{t}\textbf{1}\\{y^{i}_{k}=y^{i}_{t}\\}$

15

16 Q-factor update:
$\displaystyle\bar{Q}^{i}_{t+1}(y^{i}_{t},u^{i}_{t})=\left(1-\frac{1}{n^{i}_{t}}\right)\bar{Q}^{i}_{t}(y^{i}_{t},u^{i}_{t})+\frac{1}{n^{i}_{t}}\left(c^{i}_{t}+\beta\min_{a^{i}\in\mathbb{U}}\bar{Q}^{i}_{t}(y^{i}_{t+1},a^{i})\right),$

17 and $\bar{Q}^{i}_{t+1}(y,a)=\bar{Q}^{i}_{t}(y,a)$ for all
$(y,a)\not=(y^{i}_{t},u^{i}_{t})$.

18 Value function update:
$\displaystyle\bar{J}^{i}_{t+1}(y^{i}_{t})=\left(1-\frac{1}{m^{i}_{t}}\right)\bar{J}^{i}_{t}(y^{i}_{t})+\frac{1}{m^{i}_{t}}\left(c^{i}_{t}+\beta\bar{J}^{i}_{t}(y^{i}_{t+1})\right),$
and $\bar{J}^{i}_{t+1}(y)=\bar{J}^{i}_{t}(y)$ for all $y\not=y^{i}_{t}$.

Algorithm 1 Naive Learning in an $N$-player MFG

Remarks: In [49], the authors show that $\tilde{W}^{*i}_{\bm{\pi}}$,
restricted to
$\\{\varphi^{i}(\textbf{s}):\textbf{s}\in\textbf{X}\\}\times\mathbb{U}$, is in
fact the Q-function for _some_ fully observed Markov decision problem with
state space
$\varphi^{i}(\textbf{X}):=\\{\varphi^{i}(\textbf{s}):\textbf{s}\in\textbf{X}\\}$.
The same argument used there can be used to establish that
$\tilde{V}^{*i}_{\bm{\pi}}$, restricted to $\varphi^{i}(\textbf{X})$, is the
state value function for the _same_ MDP. A complete specification of this
MDP—with explicit characterization of its transition probabilities and its
stage cost function—is possible, but is somewhat involved. We refer to [49,
Section 3.2] for details, and instead offer the following important notes:

  * (i)

The MDP with state space $\varphi^{i}(\textbf{X})$ described above is an
instance of what [49] calls _an approximate belief MDP with memory length 0_.

  * (ii)

Under Assumption 5, each soft policy $\tilde{\bm{\pi}}\in\bm{\Gamma}_{S}$
gives rise to a unique invariant measure
$\nu_{\tilde{\bm{\pi}}}\in\mathcal{P}(\textbf{X})$, and we have that ${\rm
Pr}^{\tilde{\bm{\pi}}}_{\nu}\left(\textbf{x}_{t}\in\cdot\right)\to\nu_{\tilde{\bm{\pi}}}(\cdot)$
in total variation as $t\to\infty$.

  * (iii)

The MDP described above, with state space $\varphi^{i}(\textbf{X})$, depends
on the joint policy $\bm{\pi}$ through the invariant measure $\nu_{\bm{\pi}}$.
In particular, this MDP depends on the entire joint policy
$(\pi^{i},\bm{\pi}^{-i})$, not merely on $\bm{\pi}^{-i}$. Crucially, this
means that the limiting quantities $\tilde{V}^{*i}_{\bm{\pi}}$ and
$\tilde{W}^{*i}_{\bm{\pi}}$ depend, in general, on the policy $\pi^{i}$ used
by player $i$. This is in contrast to the MDP settings (including the specific
cases in Parts 2) and 3) of Theorem 2), where the limiting values of
Q-learning and value function learning are the same for different
(soft/sufficiently exploratory) policies.

  * (iv)

In general, as player $i$ does not face an MDP with state process
$\\{y^{i}_{t}\\}_{t\geq 0}$, $i$ does not face this particular MDP on
$\varphi^{i}(\textbf{X})\subset\mathbb{Y}$. The limiting quantities
$\tilde{V}^{*i}_{\bm{\pi}}$ and $\tilde{W}^{*i}_{\bm{\pi}}$ do not, in
general, have any inherent relevance to player $i$’s objective function in the
game $\mathcal{G}$. These quantities should instead be interpreted as the
subjective beliefs of player $i$, which were arrived at through a naive
independent learning process.

We conclude this section by introducing notation for the subjective function
family corresponding to each agent’s subjective beliefs obtained through the
learning process described in Algorithm 1.

######  Definition 14 (Naively Learned Subjective Function Family)

Let
$\mathcal{V}^{*}=\left\\{V^{*i}_{\bm{\pi}}:\mathbb{Y}\to\mathbb{R}\middle|i\in\mathcal{N},\bm{\pi}\in\bm{\Gamma}_{S}\right\\}$
be the collection of functions defined as follows: for each $i\in\mathcal{N}$
and $\bm{\pi}\in\bm{\Gamma}_{S}$,
$V^{*i}_{\bm{\pi}}:=\tilde{V}^{*i}_{\bm{\pi}}$ if $\bm{\pi}$ is soft and
$V^{*i}_{\bm{\pi}}\equiv\frac{\|c\|_{\infty}}{1-\beta}+1$ otherwise.

Let
$\mathcal{W}^{*}=\left\\{W^{*i}_{\bm{\pi}}:\mathbb{Y}\times\mathbb{U}\to\mathbb{R}\middle|i\in\mathcal{N},\bm{\pi}\in\bm{\Gamma}_{S}\right\\}$
be collection of functions defined as follows: for each $i\in\mathcal{N}$ and
$\bm{\pi}\in\bm{\Gamma}_{S}$, $W^{*i}_{\bm{\pi}}:=\tilde{W}^{*i}_{\bm{\pi}}$
if $\bm{\pi}$ is soft and $W^{*i}_{\bm{\pi}}\equiv 0$ otherwise.

Then, the pair $(\mathcal{V}^{*},\mathcal{W}^{*})$ is called the _naively
learned subjective function family_ for $\mathcal{G}$.

For $\bm{\pi}\in\bm{\Gamma}_{S}$ that is not soft, we have chosen to define
$V^{*i}_{\bm{\pi}}$ and $W^{*i}_{\bm{\pi}}$ as we have in order to avoid
introducing $(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective
$\epsilon$-equilibrium that may not be the outcome of the naive learning
process. We now discuss when the existence of such subjective equilibrium can
be guaranteed and challenges that arise in guaranteeing existence under
decentralized information.

###  IV-A Existence of Subjective Equilibrium under Global or Mean-Field State
Observability

###### Lemma 12

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game
satisfying Assumptions 1 and 5. Let $\epsilon>0$. Then, there exists
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-equilibrium
policies. That is, ${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$.

###### Proof:

Recall that the set $\bm{\Gamma}_{S}$ is compact under the topology induced by
the metric d. Combining this compactness with Lemmas 2 and 5, we see that
those functions are in fact uniformly continuous on $\bm{\Gamma}_{S}$ and
$\bm{\Gamma}^{-i}_{S}$, for any fixed $i\in\mathcal{N}$. It follows from this
that there exists $\xi>0$ such that if two joint policies
$\bm{\pi},\bm{\pi}^{\prime}\in\bm{\Gamma}_{S}$ satisfy
$\textbf{d}(\bm{\pi},\bm{\pi}^{\prime})<\xi$, then we have

$\left|J^{i}_{\bm{\pi}}(\textbf{s})-J^{i}_{\bm{\pi}^{\prime}}(\textbf{s})\right|<\frac{\epsilon}{2}\quad\text{and}\quad\left|\min_{a^{i}\in\mathbb{U}}Q^{*i}_{\bm{\pi}^{-i}}(\textbf{s},a^{i})-\min_{a^{i}\in\mathbb{U}}Q^{*i}_{\bm{\pi}^{-i}}\right|<\frac{\epsilon}{2},$
(5)

for any $i\in\mathcal{N},\textbf{s}\in\textbf{X}$. We fix
$\bm{\pi}^{*}\in\bm{\Gamma}^{0{\rm\text{-}eq}}_{S}$ to be a perfect
equilibrium policy, which exists by Lemma 7. Let $\bm{\pi}_{\rm
soft}\in\bm{\Gamma}_{S}$ be a soft joint policy satisfying
$\textbf{d}(\bm{\pi}^{*},\bm{\pi}_{\rm soft})<\xi$.

By Theorem 2 and the construction of $(\mathcal{V}^{*},\mathcal{W}^{*})$,
since $\bm{\pi}_{\rm soft}$ is soft, we have that

$W^{*i}_{\bm{\pi}_{\rm soft}}=Q^{*i}_{\bm{\pi}^{-i}_{\rm
soft}}\quad\text{and}\quad V^{*i}_{\bm{\pi}_{\rm
soft}}(\textbf{s})=J^{i}_{\bm{\pi}_{\rm soft}}(\textbf{s})$

for each $i\in\mathcal{N}$ and $\textbf{s}\in\textbf{X}$. Combining this with
(5), it follows that $V^{*i}_{\bm{\pi}_{\rm
soft}}(\textbf{s})\leq\min_{a^{i}\in\mathbb{U}}W^{*i}_{\bm{\pi}_{\rm
soft}}(\textbf{s},a^{i})+\epsilon$ for any $\textbf{s}\in\textbf{X}$ and any
$i\in\mathcal{N}$, which shows that $\bm{\pi}_{\rm soft}\in{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$. ∎

###### Lemma 13

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game
satisfying Assumptions 2 and 5. Let $\epsilon>0$. Then, there exists
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-equilibrium
policies. That is, ${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$.

###### Proof:

Replacing $\bm{\Gamma}_{S}$ by $\bm{\Gamma}_{S,{\rm sym}}$ as required, the
proof of Lemma 13 parallels that of Lemma 12 and is omitted. ∎

Note that we have not ruled out the existence of subjective-but-not-objective
$\epsilon$-equilibrium policies, i.e. policies in ${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\setminus\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}$.

###  IV-B Equilibria under Compressed Mean-Field State and Local State
Information

We note that the proof methods utilized to guarantee the existence of
equilibria under Assumption 1 and 2 do not apply to partially observed
$N$-player mean-field games with the observation channels of Assumptions 3 or
4. In our analysis to follow, for convergence results, we will be assuming the
existence of subjective equilibria when one of Assumptions 3 or 4 holds. We
emphasize that establishing existence of such subjective equilibria is an open
problem. We note however that for a large number of agents (large $N$),
subjective equilibria almost coincides with Nash equilibria and therefore an
existence analysis following [51, Theorem 4.1] can be employed for games with
large $N$. See also [52, 53, 54] and [7] for related studies.

##  V Subjective Satisficing and Policy Updating Dynamics

With the goal of better informing algorithm design, this section studies the
structure and limitations of a class of discrete-time dynamical systems on
$\bm{\Gamma}_{S}$, the set of stationary joint policies in a partially
observed $N$-player mean-field game. We are interested in a class of dynamical
systems that arise when, at every time index, each agent updates its policy in
response to the prevailing joint policy. The defining characteristic of the
class of dynamical systems we consider is that players do not switch policies
when they are subjectively $\epsilon$-best-responding to the prevailing joint
policy, but are otherwise free to change their policy arbitrarily when they
are not subjectively $\epsilon$-best-responding. Instances from this class of
dynamical systems are natural in multi-agent reinforcement learning settings,
where agents may experiment with various policies when performing poorly but
settle on a policy when performing well.

For the following definitions, let $\mathcal{G}$ be a partially observed
$N$-player game, let $i\in\mathcal{N}$, let $\epsilon\geq 0$, and let
$(\mathcal{V},\mathcal{W})$ be a subjective function family for $\mathcal{G}$.

######  Definition 15 (Policy Update Rules)

A mapping $T^{i}:\bm{\Gamma}_{S}\to\Gamma^{i}_{S}$ is called a policy update
rule for (player $i$). A collection $\textbf{T}=\\{T^{j}\\}_{j\in\mathcal{N}}$
of policy update rules for each player is called a _joint policy update rule_.

###### Definition 16

If a policy update rule $T^{i}$ satisfies

$\pi^{i}\in{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i},\mathcal{V},\mathcal{W})\Rightarrow
T^{i}(\bm{\pi})=\pi^{i},$

for every $\bm{\pi}\in\bm{\Gamma}_{S}$, then $T^{i}$ is said to be
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-satisficing. A joint policy
update rule $\textbf{T}=\\{T^{i}\\}_{i\in\mathcal{N}}$ is called
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-satisficing if each player’s
component policy update rule is $(\mathcal{V},\mathcal{W})$-subjective
$\epsilon$-satisficing.

######  Definition 17 (Subjective Satisficing Paths)

A sequence of policies $(\bm{\pi}_{k})_{k\geq 0}$ in $\bm{\Gamma}_{S}$ is
called a _$(\mathcal{V},\mathcal{W})$ -subjective $\epsilon$-satisficing path_
if, for every $i\in\mathcal{N}$ and $k\geq 0$, we have

$\pi^{i}_{k}\in{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i}_{k},\mathcal{V},\mathcal{W})\Rightarrow\pi^{i}_{k+1}=\pi^{i}_{k}.$

Given a joint policy update rule T and a joint policy
$\bm{\pi}\in\bm{\Gamma}_{S}$, we let $\textbf{T}(\bm{\pi})\in\bm{\Gamma}_{S}$
be the joint policy given by
$\textbf{T}(\bm{\pi})=\\{T^{i}(\bm{\pi})\\}_{i\in\mathcal{N}}$; that is,
player $i$’s component of $\textbf{T}(\bm{\pi})$ is given by
$T^{i}(\bm{\pi})$. We define $\textbf{T}^{0}(\bm{\pi}):=\bm{\pi}$ for any
joint policy update rule T and joint policy $\bm{\pi}\in\bm{\Gamma}_{S}$. We
further define
$\textbf{T}^{k+1}(\bm{\pi})=\textbf{T}\left(\textbf{T}^{k}(\bm{\pi})\right)$
for each $k\geq 0$. This allows us to denote the orbits of T from a given
initial policy $\bm{\pi}\in\bm{\Gamma}_{S}$ as
$\\{\textbf{T}^{k}(\bm{\pi})\\}_{k\geq 0}$.

Intuitively, when an agent follows a $(\mathcal{V},\mathcal{W})$-subjective
$\epsilon$-satisficing rule, it only considers switching its policy when its
(subjectively) deems the policy to be performing poorly. No further
restrictions are placed on how an agent is allowed to switch (or not switch)
its policy when it is subjectively unsatisfied. We note that given a
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-satisficing rule T and any
initial policy $\bm{\pi}\in\bm{\Gamma}_{S}$, the resulting orbit
$\\{\textbf{T}^{k}(\bm{\pi})\\}_{k\geq 0}$ is a
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-satisficing path. Moreover,
we observe that $(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-equilibrium
policies are invariant under any $(\mathcal{V},\mathcal{W})$-subjective
$\epsilon$-satisficing joint policy update: if $\bm{\pi}^{*}\in{\rm
Subj}_{\epsilon}(\mathcal{V},\mathcal{W})$ and T is
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-satisficing, then
$\textbf{T}^{k}(\bm{\pi}^{*})=\bm{\pi}^{*}$ for all $k\geq 0$. In addition to
stability, it is natural to ask whether a given joint policy update rule T
drives its orbits to ${\rm Subj}_{\epsilon}(\mathcal{V},\mathcal{W})$. This
motivates the following definition.

######  Definition 18 (Subjective Satisficing Paths Property)

Let $\bm{\Pi}\subseteq\bm{\Gamma}_{S}$ be a subset of joint policies. The game
$\mathcal{G}$ is said to have the _$(\mathcal{V},\mathcal{W})$ -subjective
$\epsilon$-satisficing paths property within $\bm{\Pi}$_ if the following
holds: for every $\bm{\pi}\in\bm{\Pi}$, there exists a
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-satisficing path
$(\bm{\pi}_{k})_{k\geq 0}$ such that (i) $\bm{\pi}_{0}=\bm{\pi}$, (ii)
$\bm{\pi}_{k}\in\bm{\Pi}$ for all $k\geq 0$, and (iii) for some $K<\infty$,
$\bm{\pi}_{K}\in{\rm Subj}_{\epsilon}(\mathcal{V},\mathcal{W})$.

When the game $\mathcal{G}$ does not have the
$(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-satisficing paths property
in a policy subset $\bm{\Pi}\subset\Gamma_{S}$, there exist initial policies
for which _no_ $(\mathcal{V},\mathcal{W})$-subjective $\epsilon$-satisficing
update rule can drive play to subjective equilibrium in finitely many steps.
In such instances, it would be inappropriate to employ MARL algorithms that
rely on the “win-stay, lose-shift” paradigm to guide exploration of the policy
set $\bm{\Pi}$. There are many examples of MARL algorithms that rely on this
win-stay, lose-shift paradigm. We selectively cite [55, 56, 57] and [20].

###  V-A Naively Learned Subjective Functions and $\epsilon$-Satisficing

We now shift our attention to our subjective function family of interest,
$(\mathcal{V}^{*},\mathcal{W}^{*})$, which arises out of the naive independent
learning process of Section IV. We will argue that any partially observed
$N$-player mean-field game will admit
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing paths to
equilibrium under global state observability and mean-field state
observability. For compressed state observability, we show that if subjective
equilibria exist then subjective $\epsilon$-satisficing paths exist.

####  V-A1 Subjective Satisficing Paths under Global State Observability

###### Definition 19

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game for which
Assumption 1 is satisfied, and let $i\in\mathcal{N}$. A stationary policy
$\pi^{i}\in\Gamma^{i}_{S}$ is said to be _of the mean-field type_ if there
exists $f^{i}\in\mathcal{P}(\mathbb{U}|X_{{\rm loc}}\times{\rm Emp}_{N})$ such
that
$\pi^{i}(\cdot|\textbf{s})=f^{i}\left(\cdot\middle|s^{i},\mu(\cdot|\textbf{s})\right)$
for every global state $\textbf{s}\in\textbf{X}$.

We identify each stationary policy of the mean-field type with its associated
transition kernel in $\mathcal{P}(\mathbb{U}|X_{{\rm loc}}\times{\rm
Emp}_{N})$.

###### Definition 20

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game for which
Assumption 1 is satisfied. For $i,j\in\mathcal{N}$, let
$\pi^{i}\in\Gamma^{i}_{S}$ and $\pi^{j}\in\Gamma^{j}_{S}$ both be of the mean-
field type. We say that $\pi^{i}$ and $\pi^{j}$ are _mean-field symmetric_ if
they are identified with the same transition kernel in
$\mathcal{P}(\mathbb{U}|X_{{\rm loc}}\times{\rm Emp}_{N})$.

This definition of mean-field symmetry is effectively the same as the
definition given earlier. Here, we redefine it to emphasize that this
definition pertains to stationary policies for a different observation
channel, namely that of global state observability rather than that of mean-
field state observability, for which the earlier definition was tailored.

###### Lemma 14

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game for which
Assumptions 1 and 5 are satisfied, and let $\epsilon\geq 0$. Let
$\bm{\pi}\in\bm{\Gamma}_{S}$ be a stationary joint policy for which $\pi^{p}$
is of the mean-field type for each player $p\in\mathcal{N}$. Suppose that, for
some $i,j\in\mathcal{N}$, we have that $\pi^{i}$ and $\pi^{j}$ are mean-field
symmetric, then we have

$\pi^{i}\in{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i},\mathcal{V}^{*},\mathcal{W}^{*})\iff\pi^{j}\in{\rm
Subj\text{-}BR}^{j}_{\epsilon}(\bm{\pi}^{-j},\mathcal{V}^{*},\mathcal{W}^{*}).$

A proof of Lemma 14 can be found in Appendix -B. Lemma 14 enables the
following important result, our first on the existence of
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing paths.

###### Theorem 3

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game for which
Assumptions 1 and 5 hold. Let $\epsilon>0$, and let
$(\mathcal{V}^{*},\mathcal{W}^{*})$ be the naively learned subjective function
family for $\mathcal{G}$. Suppose $\bm{\Pi}\subset\bm{\Gamma}_{S}$ is a subset
of stationary joint policies satisfying the following properties: (i) Every
$\bm{\pi}\in\bm{\Pi}$ is of the mean-field type; (ii) $\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$; (iii) the
set $\bm{\Pi}$ is symmetric, i.e. $\Pi^{j}=\Pi^{j}$ for each
$i,j\in\mathcal{N}$.

Then, $\mathcal{G}$ has the $(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective
$\epsilon$-satisficing paths property within $\bm{\Pi}$.

The proof of Theorem 3 parallels that of [46, Theorem 8], which was in the
context of symmetric, fully observed stochastic games. We include the proof
here both for completeness and to illustrate the key role of symmetry in the
proof technique. This same technique will also be applicable for some of our
results to follow.

###### Proof:

Let $\bm{\pi}\in\bm{\Pi}$. We will argue that there exists a
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing path of
finite lenth from $\bm{\pi}$ to ${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$.

We put $C_{-1}=\varnothing$. Let $\bm{\pi}_{0}:=\bm{\pi}$. Picking
$i(0)\in\mathcal{N}$ arbitrarily, we put
$C_{0}=\\{j\in\mathcal{N}:\pi^{j}_{0}=\pi^{i(0)}_{0}\\}$, where equality of
policies is interpreted as mean-field symmetry (i.e. equality of underlying
transition kernels in $\mathcal{P}(\mathbb{U}|X_{{\rm loc}}\times{\rm
Emp}_{N})$). The set $C_{0}$ will be called our first cohort. One can see that
all players in $C_{0}$ use the same policy and no player outside of $C_{0}$
uses the policy of the players in $C_{0}$. Trivially, the sequence of length
one $(\bm{\pi}_{0})$ is a $(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective
$\epsilon$-satisficing path.

For some $n\in\\{0,1,\dots,N\\}$, suppose that we have a sequence of joint
policies $(\bm{\pi}_{k})_{k=0}^{n}\subset\bm{\Pi}$ and a corresponding
sequence of player subsets/“cohorts” $(C_{k})_{k=0}^{n}\subseteq\mathcal{N}$
such that the following items hold for each $k\in\\{0,1,\dots,n\\}$:

  1. 1.

All players in $C_{k}$ use the same policy under $\bm{\pi}_{k}$: for all
$i,j\in C_{k}$, we have $\pi^{i}_{k}=\pi^{j}_{k}$;

  2. 2.

We have $|C_{k}|\geq|C_{k-1}|+1$;

  3. 3.

If $i\in C_{k}$ and $j\notin C_{k}$, then $\pi^{i}_{k}\not=\pi^{j}_{k}$;

  4. 4.

The finite length sequence $\bm{\pi}_{0},\dots,\bm{\pi}_{k}$ is a
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing path.

Proceeding in cases, we now argue that either
$\bm{\pi}_{0},\cdots,\bm{\pi}_{n}$ is itself a
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing path
into ${\rm Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$ or otherwise can
be extended to such a path.

The first case to consider is that where $C_{n}=\mathcal{N}$. Here, either
$\bm{\pi}_{n}\in{\rm Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$ or
$\bm{\pi}_{n}\notin{\rm Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$. As
the former case is trivial, we focus on the latter case. Since
$\bm{\pi}_{n}\notin{\rm Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$,
there exists some player $i\in\mathcal{N}$ such that $\pi^{i}_{n}\notin{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i}_{n},\mathcal{V}^{*},\mathcal{W}^{*})$.
Then, by item (1) above, invoking Lemma 14 we see that in fact
$\pi^{i}_{n}\notin{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i}_{n},\mathcal{V}^{*},\mathcal{W}^{*})$
for all $i\in\mathcal{N}$. Thus, each player may change its policy and the
resulting sequence of joint policies will remain a
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing path.
Formally, let $\bm{\pi}^{*}\in{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\cap\bm{\Pi}$, then
$(\bm{\pi}_{0},\dots,\bm{\pi}_{n},\bm{\pi}^{*})$ is a
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing path of
finite length from $\bm{\pi}$ into ${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\cap\bm{\Pi}$, as desired.

The second case to consider is that where $C_{n}\not=\mathcal{N}$ is a proper
subset of the set of players. Again, either $\bm{\pi}_{n}\in{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$ or $\bm{\pi}_{n}\notin{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$; again, the former case is
trivial and we focus on the latter case. In the latter case, one of the
following sub-cases holds, using item (1) and Lemma 14: either (a)
$\pi^{i}_{n}\notin{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i}_{n},\mathcal{V}^{*},\mathcal{W}^{*})$
for every $i\in C_{n}$ or (b) $\pi^{i}_{n}\in{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i}_{n},\mathcal{V}^{*},\mathcal{W}^{*})$
for any $i\in C_{n}$.

In sub-case (a), each player in $C_{n}$ may change its policy: select a player
$p(n)\in\mathcal{N}\setminus C_{n}$ arbitrarily. (Player $p(n)$ need not be
subjectively $\epsilon$-best-responding to $\bm{\pi}^{-p(n)}_{n}$.) We define
the joint policy $\bm{\pi}_{n+1}$ by $\pi^{i}_{n+1}=\pi^{i}_{n}$ for $i\notin
C_{n}$ and $\pi^{i}_{n+1}=\pi^{p(n)}_{n}$ for $i\in C_{n}$. We also define a
player subset

$C_{n+1}:=\left\\{j\in\mathcal{N}:\pi^{j}_{n+1}=\pi^{p(n)}_{n+1}\right\\}.$

By construction, we have that $C_{n}\not=C_{n}\cup\\{p(n)\\}\subseteq C_{n+1}$
and furthermore $\bm{\pi}_{0},\bm{\pi}_{1},\dots,\bm{\pi}_{n},\bm{\pi}_{n+1}$
is a $(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing
path.

In sub-case (b) we have that $\bm{\pi}_{n}\notin{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$, $C_{n}\not=\mathcal{N}$,
and $\pi^{i}_{n}\in{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i}_{n},\mathcal{V}^{*},\mathcal{W}^{*})$
for any $i\in C_{n}$. Thus, there exists a player $p\in\mathcal{N}\setminus
C_{n}$ such that $\pi^{p}_{n}\notin{\rm
Subj\text{-}BR}^{p}_{\epsilon}(\bm{\pi}^{-p}_{n},\mathcal{V}^{*},\mathcal{W}^{*})$.
We define a joint policy $\bm{\pi}_{n+1}\in\bm{\Pi}$ as
$\pi^{i}_{n+1}=\pi^{i}_{n}$ if $i\not=p$ and $\pi^{p}_{n+1}=\pi^{i*}_{n}$ for
some player $i^{*}\in\mathcal{N}$. We also define $C_{n+1}=C_{n}\cup\\{p\\}$
and we have that $\bm{\pi}_{0},\bm{\pi}_{1},\dots,\bm{\pi}_{n},\bm{\pi}_{n+1}$
is a $(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing
path.

One can see that this process of extending the sequences
$\\{\bm{\pi}_{k}\\}_{k=0}^{n}$ and $\\{C_{k}\\}_{k=0}^{n}$ into the sequences
$\\{\bm{\pi}_{k}\\}_{k=0}^{n+1}$ and $\\{C_{k}\\}_{k=0}^{n+1}$ as described
may continue only for finitely many steps before we reach $C_{n}=\mathcal{N}$,
which we have seen results in a $(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective
$\epsilon$-satisficing path of finite length from $\bm{\pi}$ into ${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\cap\bm{\Pi}$. ∎

###### Corollary 2

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game
satisfying Assumptions 1 and 5. Let $\epsilon>0$ and let
$\bm{\Pi}:=\\{\bm{\pi}\in\bm{\Gamma}_{S}:\pi^{i}\text{ is of the mean-field
type for all }i\in\mathcal{N}\\}.$ Then, $\mathcal{G}$ has the
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing paths
property within $\bm{\Pi}$.

###### Proof:

Using the proof of Theorem 1, we have that $\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$. The set
$\bm{\Pi}$ thus satisfies the conditions of Theorem 3, and the result follows.
∎

####  V-A2 Subjective Satisficing Paths under Mean-Field State Observability

We now provide a result analogous to Theorem 3 under mean-field state
observability. To facilitate this result, we now state an analog to Lemma 14.

###### Lemma 15

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game for which
Assumptions 2 and 5 hold, and let $\epsilon\geq 0$. Let
$\bm{\pi}\in\bm{\Gamma}_{S}$. For $i,j\in\mathcal{N}$, suppose $\pi^{i}$ and
$\pi^{j}$ are mean-field symmetric. Then, we have

$\pi^{i}\in{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i},\mathcal{V}^{*},\mathcal{W}^{*})\iff\pi^{j}\in{\rm
Subj\text{-}BR}^{j}_{\epsilon}(\bm{\pi}^{-j},\mathcal{V}^{*},\mathcal{W}^{*}).$

A proof of Lemma 15 can be found in Appendix -B.

###### Theorem 4

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game for which
Assumptions 2 and 5 hold. Let $\epsilon>0$, and let
$(\mathcal{V}^{*},\mathcal{W}^{*})$ be the naively learned subjective function
family for $\mathcal{G}$. Suppose $\bm{\Pi}\subset\bm{\Gamma}_{S}$ is a subset
of stationary joint policies satisfying the following properties: (i)
$\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$; (ii) the
set $\bm{\Pi}$ is symmetric, i.e. $\Pi^{j}=\Pi^{j}$ for each
$i,j\in\mathcal{N}$. Then, $\mathcal{G}$ has the
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing paths
property within $\bm{\Pi}$.

The argument used in the proof of Theorem 3 can suitably modified (e.g.
replacing Lemma 14 by Lemma 15) to prove Theorem 4, and so the proof is
omitted.

###### Corollary 3

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game for which
Assumptions 2 and 5 hold. Let $\epsilon>0$, and let
$(\mathcal{V}^{*},\mathcal{W}^{*})$ be the naively learned subjective function
family for $\mathcal{G}$. Then, $\mathcal{G}$ has the
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing paths
property within $\bm{\Gamma}_{S}$.

####  V-A3 Subjective Satisficing Paths under Compressed State Observability

In light of our previous discussion on the possible non-existence of (naively
learned) subjective $\epsilon$-equilibrium in games with compressed state
observability, we now give a qualified result analogous to Theorem 3 and 4 for
the compressed state observation channel. In contrast to the earlier results,
here we must assume the existence of subjective equilibrium.

###### Definition 21

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game and let
$i\in\mathcal{N}$. A policy $\pi^{i}\in\Gamma^{i}_{S}$ is said to be _of the
local type_ if there exists a transition kernel
$g^{i}\in\mathcal{P}(\mathbb{U}|X_{{\rm loc}})$ such that

$\pi^{i}(\cdot|\varphi^{i}(\textbf{s}))=g^{i}(\cdot|s^{i}),\quad\forall\textbf{s}\in\textbf{X}.$

Each policy of the local type is identified with the corresponding transition
kernel in $\mathcal{P}(\mathbb{U}|X_{{\rm loc}})$. For players
$i,j\in\mathcal{N}$, if the policies
$\pi^{i}\in\Gamma^{i}_{S},\pi^{j}\in\Gamma^{j}_{S}$ are both of the local type
and are identified with the same transition kernel, we say $\pi^{i}$ and
$\pi^{j}$ are _locally symmetric_.

###### Lemma 16

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game for which
Assumptions 3 and 5 hold. Let $\bm{\pi}\in\bm{\Gamma}_{S}$. For
$i,j\in\mathcal{N}$, suppose $\pi^{i}$ and $\pi^{j}$ are locally symmetric.
Then, we have

$\pi^{i}\in{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i},\mathcal{V}^{*},\mathcal{W}^{*})\iff\pi^{j}\in{\rm
Subj\text{-}BR}^{j}_{\epsilon}(\bm{\pi}^{-j},\mathcal{V}^{*},\mathcal{W}^{*}).$

The proof of Lemma 16 is essentially the same as the proof of Lemma 15, and is
therefore omitted.

###### Theorem 5

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game for which
Assumptions 3 and 5 hold. Let $\epsilon>0$, and let
$(\mathcal{V}^{*},\mathcal{W}^{*})$ be the naively learned subjective function
family for $\mathcal{G}$. Assume that ${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$. Suppose
$\bm{\Pi}\subset\bm{\Gamma}_{S}$ is a subset of stationary joint policies
satisfying the following properties: (i) $\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$; (ii) the
set $\bm{\Pi}$ is symmetric, i.e. $\Pi^{j}=\Pi^{j}$ for each
$i,j\in\mathcal{N}$. Then, $\mathcal{G}$ has the
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing paths
property within $\bm{\Pi}$.

The argument used in the proof of Theorem 3 can suitably modified (e.g.
replacing Lemma 14 by Lemma 16) to prove Theorem 5, and so the proof is
omitted.

###  V-B Quantization of the Policy Space

For algorithm design purposes, it will be advantageous to restrict policy
selection to a finite subset of stationary policies. We argue that if the
restricted set of policies is obtained via a sufficiently fine quantization of
the original set, then the performance loss for an agent optimizing over this
subset will be negligible. Moreover, we argue that if the restricted subset of
policies is suitably fine and symmetric, then the structural properties of the
previous section will be inherited: in particular, subjective near-equilibrium
policies will exist in the restricted set, and furthermore the subjective
satisficing paths property will hold within this finite subset of policies.

For the following definitions, let $\mathcal{G}$ be a partially observed
$N$-player mean-field game, let $i\in\mathcal{N}$. Recall that $d^{i}$ is a
metric on the set $\Gamma^{i}_{S}$, suitably defined to match the assumed
observation channel.

###### Definition 22

Let $\xi>0$ and $\tilde{\Pi}^{i}\subseteq\Gamma^{i}_{S}$. A mapping
$q^{i}:\tilde{\Pi}^{i}\to\tilde{\Pi}^{i}$ is called a _$\xi$ -quantizer (on
$\tilde{\Pi}^{i}$_) if (i)
$q^{i}(\tilde{\Pi}^{i}):=\\{q^{i}(\pi^{i}):\pi^{i}\in\tilde{\Pi}^{i}\\}$ is a
finite set and (ii) $d^{i}(\pi^{i},q^{i}(\pi^{i}))<\xi$ for all
$\pi^{i}\in\tilde{\Pi}^{i}$.

###### Definition 23

Let $\xi>0$ and let $\tilde{\Pi}^{i}\subseteq\Gamma^{i}_{S}$. A set of
policies $\Pi^{i}\subseteq\tilde{\Pi}^{i}$ is called a $\xi$-quantization of
$\tilde{\Pi}^{i}$ if $\Pi^{i}=q^{i}(\tilde{\Pi}^{i})$, where $q^{i}$ is some
$\xi$-quantizer on $\tilde{\Pi}^{i}$.

A set $\Pi^{i}\subseteq\Gamma^{i}_{S}$ is called a quantization of
$\Gamma^{i}_{S}$ if it is a $\xi$-quantization of $\Gamma^{i}_{S}$ for some
$\xi>0$. A quantization $\Pi^{i}$ is called _soft_ if each policy
$\pi^{i}\in\Pi^{i}$ is soft. The expression “fine quantization” will be used
to reflect that a policy subset is a $\xi$-quantization for suitably small
$\xi$. We extend the definitions above and each of these terminological
conventions to also refer to quantizers and quantizations of sets of joint
policies. For instance,
$\bm{\Pi}=\times_{i\in\mathcal{N}}\Pi^{i}\subset\bm{\Gamma}_{S}$ is a
$\xi$-quantization of $\bm{\Gamma}_{S}$ if each $\Pi^{i}$ is a
$\xi$-quantization of $\Gamma^{i}_{S}$, and so on.

###### Definition 24

Let $\bm{\Pi}\subset\bm{\Gamma}_{S}$ be a quantization of $\bm{\Gamma}_{S}$.
We say that $\bm{\Pi}$ is _symmetric_ if $\Pi^{i}=\Pi^{j}$ for each
$i,j\in\mathcal{N}$.

Using the various continuity results presented above, the following results
are straightforward.

###### Lemma 17

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game
satisfying Assumptions 1 and 5. Let $\epsilon>0$. There exists
$\xi=\xi(\epsilon)>0$ such that if $\bm{\Pi}\subset\bm{\Gamma}_{S}$ is any
soft $\xi$-quantization of $\bm{\Gamma}_{S}$, then we have

  1. 1.

$\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}\cap\bm{\Pi}\not=\varnothing$;

  2. 2.

${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\cap\bm{\Pi}\not=\varnothing$.

Moreover, if $\tilde{\bm{\Pi}}\subset\bm{\Gamma}_{S}$ is the set of joint
stationary policies of the mean-field type, there exists $\xi=\xi(\epsilon)>0$
such that if $\bm{\Pi}$ is a soft, symmetric $\xi$-quantization of
$\tilde{\bm{\Pi}}$, then we have

  1. 3)

${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\cap\bm{\Pi}\not=\varnothing$;

  2. 4)

$\mathcal{G}$ has the $(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective
$\epsilon$-satisficing paths property within $\bm{\Pi}$.

###### Lemma 18

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game
satisfying Assumptions 2 and 5. Let $\epsilon>0$. There exists
$\xi=\xi(\epsilon)>0$ such that if $\bm{\Pi}\subset\bm{\Gamma}_{S}$ is any
soft, symmetric $\xi$-quantization of $\bm{\Gamma}_{S}$, then we have

  1. 1.

$\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}\cap\bm{\Pi}\not=\varnothing$;

  2. 2.

${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\cap\bm{\Pi}\not=\varnothing$;

  3. 3.

$\mathcal{G}$ has the $(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective
$\epsilon$-satisficing paths property within $\bm{\Pi}$.

Lemmas 17 and 18 guarantee that the game $\mathcal{G}$ has the subjective
satisficing paths property within finely quantized subsets of policies. This
has two desirable consequences for algorithm design purposes. First, players
can restrict their policy search from an uncountable set (all stationary
policies) to a finite subset of policies with only a small loss in
performance.

The second desirable consequence is such: since the game $\mathcal{G}$ has the
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing paths
property within $\bm{\Pi}$, play can be driven to (subjective)
$\epsilon$-equilibrium by changing only the policies of those players that are
“$\epsilon$-unsatisfied,” so to speak. We thus obtain a stopping condition,
whereby player $i$ can settle on a policy whenever it is subjectively
$\epsilon$-best-responding. In contrast, the stability of
$\epsilon$-equilibrium may be threatened when an algorithm requires a player
to change policies while already $\epsilon$-best-responding. We selectively
cite [58, 59] and [60] as recent examples of work showing non-convergence of
policies to equilibrium when each agent runs a policy gradient algorithm.

Taken together, these points remove the need for coordinated search of the
joint policy space $\bm{\Pi}$: since
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing paths to
equilibrium exist within $\bm{\Pi}$ and $\bm{\Pi}$ is finite, play can be
driven to $\epsilon$-equilibrium even by random policy updating by those
players that are not subjectively $\epsilon$-best-responding. Moreover, this
structure also removes the need for specialized policy updating rules (such as
inertial best-responding [19] or gradient ascent [17]) that taken into account
special structure in the game.

1

2Set Parameters

3 $e^{i}\in(0,1)$: experimentation probability when not subjectively
$\epsilon$-best-responding

4 $\Pi^{i}\subset\Gamma^{i}_{S}$: a fine quantization of $\Gamma^{i}_{S}$.

5

6Initialize $\pi_{0}^{i}\in\Pi^{i}$: initial policy

7

8for $k\geq 0$ ($k^{th}$ policy update)

9

10 Receive $V^{*i}_{\bm{\pi}_{k}}$ and $W^{*i}_{\bm{\pi}_{k}}$ (from oracle)

11

12

13 if  _
$V^{*i}_{\bm{\pi}_{k}}(y)\leq\min_{a^{i}}W^{*i}_{\bm{\pi}_{k}}(y,a^{i})+\epsilon$
for all $y\in\mathbb{Y}$ _ then

14 $\pi^{i}_{k+1}=\pi^{i}_{k}$

15 else

16 $\pi^{i}_{k+1}\sim(1-e^{i})\delta_{\pi^{i}_{k}}+e^{i}\text{Unif}(\Pi^{i})$

17 Go to $k+1$

18

Algorithm 2 $\epsilon$-satisficing Policy Revision (for player
$i\in\mathcal{N}$)

We now formalize the preceding remarks. For each $i\in\mathcal{N}$, suppose
$\Pi^{i}\subset\Gamma^{i}_{S}$ is a finite quantization of either
$\\{\pi^{i}\in\Gamma^{i}_{S}:\pi^{i}\text{ is of the mean-field type}\\}$
(under global state observability, Assumption 1) or $\Gamma^{i}_{S}$ (under
mean-field observability, Assumption 2). Letting
$\bm{\Pi}=\times_{i\in\mathcal{N}}\Pi^{i}$, suppose that $\Pi^{i}=\Pi^{j}$ for
each $i,j\in\mathcal{N}$ and furthermore ${\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$. Consider
the time homogenous Markov chain $\\{\bm{\pi}_{k}\\}_{k\geq 0}$ in the set
$\bm{\Pi}$ generated according to Algorithm 2. Since the game has the
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing paths
property within $\bm{\Pi}$ and players randomly explore their policy sets when
not $\epsilon$-best-responding, this process converges almost surely to some
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-equilibrium in
$\bm{\Pi}$. This is formalized in Lemmas 19 and 20, below.

###### Lemma 19

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game
satisfying Assumptions 1 and 5, and let $\epsilon>0$. Let
$\bm{\Pi}\subset\bm{\Gamma}_{S}$ be a quantization of the set
$\\{\bm{\pi}\in\bm{\Gamma}_{S}:\pi^{i}\text{ is of the mean-field type
}\forall i\in\mathcal{N}\\}$, and suppose $\bm{\Pi}$ satisfies (i)
$\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$; (ii)
$\Pi^{i}=\Pi^{j}$ for all $i,j\in\mathcal{N}$; and (iii) every policy
$\bm{\pi}\in\bm{\Pi}$ is soft.

Suppose that each agent $i\in\mathcal{N}$ updates is policy sequence
$\\{\pi^{i}_{k}\\}_{k\geq 0}$ according to Algorithm 2 and that, for each
$k\geq 0$, the policy updates for $\bm{\pi}_{k+1}$ are conditionally
independent across agents given $\bm{\pi}_{k}$. Then,

$\lim_{k\to\infty}{\rm
Pr}(\bm{\pi}_{k}\in\bm{\Pi}\cap\bm{\Gamma}^{\epsilon{\rm\text{-}eq}})=1.$

###### Lemma 20

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game
satisfying Assumptions 2 and 5, and let $\epsilon>0$. Let
$\bm{\Pi}\subset\bm{\Gamma}_{S}$ be a quantization of $\bm{\Gamma}_{S}$ and
suppose $\bm{\Pi}$ satisfies (i) $\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$; (ii)
$\Pi^{i}=\Pi^{j}$ for all $i,j\in\mathcal{N}$; and (iii) every policy
$\bm{\pi}\in\bm{\Pi}$ is soft.

Suppose that each agent $i\in\mathcal{N}$ updates is policy sequence
$\\{\pi^{i}_{k}\\}_{k\geq 0}$ according to Algorithm 2 and that, for each
$k\geq 0$, the policy updates for $\bm{\pi}_{k+1}$ are conditionally
independent across agents given $\bm{\pi}_{k}$. Then,

$\lim_{k\to\infty}{\rm Pr}(\bm{\pi}_{k}\in\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*}))=1.$

The primary difference between Lemmas 19 and 20 is such: in the former,
convergence to an objective equilibrium is guaranteed, while in the latter one
only has convergence to a subjective equilibrium. The proofs are essentially
the same, and we therefore only include a proof of Lemma 20.

###### Proof:

We have that $\\{\bm{\pi}_{k}\\}_{k\geq 0}$ is a time homogenous Markov chain
on $\bm{\Pi}$. For any subjective $\epsilon$-equilibrium
$\bm{\pi}^{*}\in\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$, we have that the singleton
$\\{\bm{\pi}^{*}\\}$ is an absorbing set for this Markov chain, by Lines 6-7
of Algorithm 2. (The condition in Line 6 is equivalent to verifying whether
$\pi^{i}_{k}\in{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i}_{k},\mathcal{V}^{*},\mathcal{W}^{*})$.)

By Theorem 4, the game $\mathcal{G}$ has the
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-satisficing paths
within $\bm{\Pi}$. For any $\bm{\pi}\in\bm{\Pi}$, let $L_{\bm{\pi}}<\infty$
denote the length of a shortest $(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective
$\epsilon$-satisficing path within $\bm{\Pi}$ that starts at $\bm{\pi}$ and
terminates at a policy in $\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})$. Call such a policy
$\bm{\pi}^{*}$ and note it depends on $\bm{\pi}$. We also define
$p_{\bm{\pi}}>0$ as the probability the Markov chain follows this path when
starting at $\bm{\pi}$, i.e.

$p_{\bm{\pi}}:={\rm
Pr}(\bm{\pi}_{L_{\bm{\pi}}}=\bm{\pi}^{*}|\bm{\pi}_{0}=\bm{\pi})>0,\quad\forall\bm{\pi}\in\bm{\Pi}.$

Define $L:=\max\\{L_{\bm{\pi}}:\bm{\pi}\in\bm{\Pi}\\}$ and
$\hat{p}:=\min\\{p_{\bm{\pi}}:\bm{\pi}\in\bm{\Pi}\\}>0$. For any $m\geq 0$, we
have that

${\rm Pr}\left(\bigcap_{j=1}^{m}\\{\bm{\pi}_{jL}\notin\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\\}\right)\leq(1-\hat{p})^{m}.$

Taking $m\to\infty$ gives the result. ∎

We note that, in Line 9 of Algorithm 2, the choice to update the policy
according to
$\pi^{i}_{k+1}\sim(1-e^{i})\delta_{\pi^{i}_{k}}+e^{i}\text{Unif}(\Pi^{i})$ was
somewhat arbitrary. In particular, the choice to uniformly mix over $\Pi^{i}$
with probability $e^{i}>0$ was made to ensure the paths to equilibrium exist
in the Markov chain of Lemma 20. The choice to remain with one’s old policy
with probability $1-e^{i}$ was arbitrarily picked for ease of exposition, and
can be replaced by any suitable distribution over $\Pi^{i}$ according to the
taste of the system designer. Some choices may include gradient descent
projected back onto $\Pi^{i}$ or selecting a best-response to
$\bm{\pi}^{-i}_{k}$ within $\Pi^{i}$. Such changes may result in a significant
speed-up of convergence to equilibrium when they are well-suited to the
underlying game, but the guarantee holds in any case due to the uniform
randomization.

In its present form, Algorithm 2 cannot be implemented in an online MARL
setting, as we have assumed oracle access to the quantities
$V^{*i}_{\bm{\pi}_{k}}$ and $W^{*i}_{\bm{\pi}_{k}}$. In a decentralized,
independent learning setting, these quantities may be estimated through the
use of (intentionally) naive single-agent learning algorithms, as described in
Section IV. The algorithm presented in the next section will effectively mimic
the mechanics of Algorithm 2, replacing knowledge that $\pi^{i}_{k}\in{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i}_{k},\mathcal{V}^{*},\mathcal{W}^{*})$
by a learned estimate. That is, the learning algorithm of the next section
(Algorithm 3) can be viewed as a noise-perturbed, learning-based approximation
to Algorithm 2.

##  VI Learning Algorithm and Convergence Results

In this section, we present Algorithm 3, a decentralized learning algorithm
suitable for playing partially observed $N$-player mean-field games. At a high
level, Algorithm 3 is an analog to Algorithm 2: whereas an oracle provides the
subjective function information in Algorithm 2, here the subjective functions
are learned using system feedback. The learned subjective functions are then
used to estimate whether the agent is (subjectively) $\epsilon$-best-
responding.

1

2Set Parameters

3 $\Pi^{i}\subset\Gamma^{i}_{S}$ : a fine quantization of $\Gamma^{i}_{S}$

4

5$\\{T_{k}\\}_{k\geq 0}$: a sequence in $\mathbb{N}$ of learning phase lengths

6 set $t_{0}=0$ and $t_{k+1}=t_{k}+T_{k}$ for all $k\geq 0.$

7 $e^{i}\in(0,1)$: random policy updating probability

8 $d^{i}\in(0,\infty)$: tolerance level for sub-optimality

9

10Initialize $\pi_{0}^{i}\in\Pi^{i}$ (arbitrary),
$\widehat{Q}_{0}^{i}=0\in\mathbb{R}^{\mathbb{Y}\times\mathbb{U}}$,
$\widehat{J}^{i}_{0}=0\in\mathbb{R}^{\mathbb{Y}}$

11

12for $k\geq 0$ ($k^{th}$ exploration phase)

13 for $t=t_{k},t_{k}+1,\dots,t_{k+1}-1$

14 Observe $y^{i}_{t}=\varphi^{i}(\textbf{x}_{t})$

15 Select $u^{i}_{t}\sim\pi^{i}_{k}(\cdot|y^{i}_{t})$

16

17 Observe $c^{i}_{t}:=c(x^{i}_{t},\mu(\cdot|\textbf{x}_{t}),u^{i}_{t})$ and
$y^{i}_{t+1}$

18 Set
$n_{t}^{i}=\sum_{\tau=t_{k}}^{t}\textbf{1}\\{(y^{i}_{\tau},u^{i}_{\tau})=(y^{i}_{t},u^{i}_{t})\\}$

19 Set $m_{t}^{i}=\sum_{\tau=t_{k}}^{t}\textbf{1}\\{y^{i}_{\tau}=y^{i}_{t}\\}$

20
$\widehat{Q}_{t+1}^{i}(y^{i}_{t},u_{t}^{i})=\left(1-\frac{1}{{n_{t}^{i}}}\right)\widehat{Q}_{t}^{i}(y^{i}_{t},u_{t}^{i})+\frac{1}{{n_{t}^{i}}}\big{[}c^{i}_{t}+\beta\min_{a^{i}}\widehat{Q}_{t}^{i}(y^{i}_{t+1},a^{i})\big{]}$

21
$\widehat{J}^{i}_{t+1}(y^{i}_{t})=\left(1-\frac{1}{{m^{i}_{t}}}\right)\widehat{J}^{i}_{t}(y^{i}_{t})+\frac{1}{{m^{i}_{t}}}\left[c^{i}_{t}+\beta\widehat{J}^{i}_{t}(y^{i}_{t+1})\right]$

22

23

24 if  _
$\widehat{J}^{i}_{t_{k+1}}(y)\leq\min_{a^{i}}\widehat{Q}^{i}_{t_{k+1}}(y,a^{i})+\epsilon+d^{i}$
$\forall y\in\mathbb{Y}$,_ then

25 $\pi^{i}_{k+1}=\pi^{i}_{k}$

26 else

27 $\pi^{i}_{k+1}\sim(1-e^{i})\delta_{\pi^{i}_{k}}+e^{i}\text{Unif}(\Pi^{i})$
)

28 Reset $\widehat{J}^{i}_{t_{k+1}}=0\in\mathbb{R}^{\mathbb{Y}}$ and
$\widehat{Q}^{i}_{t_{k+1}}=0\in\mathbb{R}^{\mathbb{Y}\times\mathbb{U}}$

29

Algorithm 3 Independent Learning

###  VI-A Learning with Global State

We begin by presenting convergence results for Algorithm 3 under global state
observability, the richest of the information structures that we consider.
Under Assumption 1, strong convergence guarantees can be made. These are
presented below in Theorem 6. In order to state this result, we now fix
$\epsilon>0$ and make the following assumptions on the various parameters of
Algorithm 3.

###### Assumption 6

Fix $\epsilon>0$ and for each $i\in\mathcal{N}$ let $\Gamma^{i}_{S,{\rm
MF}}:=\\{\pi^{i}\in\Gamma^{i}_{S}:\pi^{i}\text{ is of the mean-field
type.}\\}$. Assume that
$\bm{\Pi}\subset\times_{i\in\mathcal{N}}\Gamma^{i}_{S,{\rm MF}}$ is a fine
quantization of $\times_{i\in\mathcal{N}}\Gamma^{i}_{S,{\rm MF}}$ satisfying:
(1) $\Pi^{i}=\Pi^{j}$ for all $i,j\in\mathcal{N}$; (2)
$\bm{\Pi}\cap\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}\not=\varnothing$; (3) For
any $\bm{\pi}\in\bm{\Pi}$, $\bm{\pi}$ is soft.

Next we present a restriction on the parameters
$\\{d^{i}\\}_{i\in\mathcal{N}}$. For each player $i\in\mathcal{N}$, the
tolerance parameter $d^{i}$ is taken to be positive to account for noise in
the learned estimates, but cannot be too large, otherwise poorly performing
policies may be mistaken for $\epsilon$-best-responses. The bound $\bar{d}$
below is defined analogous to $\bar{\delta}$ in [46] and depends on both
$\epsilon$ and $\bm{\Pi}$.

###### Assumption 7

For each player $i\in\mathcal{N}$, $d^{i}\in(0,\bar{d}_{G})$, where
$\bar{d}_{G}=\bar{d}_{G}(\epsilon,\bm{\Pi})$ is specified in Appendix -D.

###### Theorem 6

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game
satisfying Assumptions 1 and 5, and let $\epsilon>0$. Suppose the policy set
$\bm{\Pi}$ and the tolerance parameters $\\{d^{i}\\}_{i\in\mathcal{N}}$
satisfy Assumptions 6 and 7, and suppose all players follow Algorithm 3. For
any $\xi>0$, there exists
$\tilde{T}=\tilde{T}(\xi,\epsilon,\bm{\Pi},\\{d^{i}\\}_{i\in\mathcal{N}})$
such that if $T_{k}\geq\tilde{T}$ for all $k$, then

${\rm
Pr}\left(\bm{\pi}_{k}\in\bm{\Pi}\cap\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}\right)\geq
1-\xi,$

for all sufficiently large $k$.

The proof of Theorem 6 is given in Appendix -D. The details of the proof
resemble those of [20, 46]. In essence, one shows that if the exploration
phases are sufficiently long, then the learning iterates approximate the
subjective functions. Then, the policy process $\\{\bm{\pi}_{k}\\}_{k\geq 0}$
obtained from Algorithm 3 can be shown to approximate the policy process of
Algorithm 2, and the convergence to near equilibrium is shown using the theory
of satisficing paths.

Remark: The policy update
$\pi^{i}_{k+1}\sim(1-e^{i})\delta_{\pi^{i}_{k}}+e^{i}\text{Unif}(\Pi^{i})$ was
chosen for expositional clarity. One can replace $\delta_{\pi^{i}_{k}}$ by any
distribution over $\Pi^{i}$ without losing the convergence guarantees of
Theorem 6. More generally, $\delta_{\pi^{i}_{k}}$ can be replaced by any
transition kernel in
$\mathcal{P}(\Pi^{i}|\Pi^{i}\times\mathbb{R}^{\mathbb{Y}}\times\mathbb{R}^{\mathbb{Y}\times\mathbb{U}})$,
where the distribution over $\Pi^{i}$ depends on $\pi^{i}_{k}$,
$\widehat{J}^{i}_{t_{k+1}}$, and $\widehat{Q}^{i}_{t_{k+1}}$. Furthermore,
each agent $i\in\mathcal{N}$ may use a different transition kernel for this
update, allowing for heterogeneity in the learning dynamics. This remark
parallels a comment made in §V-B.

###  VI-B Learning with Mean-Field State Information

We now present a result analogous to Theorem 6 for the case of mean-field
state observability. Here, we do not guarantee convergence to objective
equilibrium but rather subjective equilibrium. Recall that we use
$(\mathcal{V}^{*},\mathcal{W}^{*})$ to denote the naively learned subjective
function family for the game $\mathcal{G}$.

###### Assumption 8

Fix $\epsilon>0$. Assume that $\bm{\Pi}$ is a fine quantization of
$\bm{\Gamma}_{S}$ satisfying: (1) $\Pi^{i}=\Pi^{j}$ for all
$i,j\in\mathcal{N}$; (2) $\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$; (3) For
any $\bm{\pi}\in\bm{\Pi}$, $\bm{\pi}$ is soft.

In analogy to the preceding parameter restriction, we again restrict $d^{i}$
to be positive but small.

###### Assumption 9

For all $i\in\mathcal{N}$, $d^{i}\in(0,\bar{d}_{{\rm MF}})$, where
$\bar{d}_{{\rm MF}}=\bar{d}_{{\rm MF}}(\epsilon,\bm{\Pi})$ is specified in
Appendix -E.

###### Theorem 7

Let $\mathcal{G}$ be a partially observed $N$-player mean-field game
satisfying Assumptions 2 and 5, and let $\epsilon>0$. Suppose the policy set
$\bm{\Pi}$ and the tolerance parameters $\\{d^{i}\\}_{i\in\mathcal{N}}$
satisfy Assumptions 8 and 9, and suppose all players follow Algorithm 3. For
any $\xi>0$, there exists
$\tilde{T}=\tilde{T}(\xi,\epsilon,\bm{\Pi},\\{d^{i}\\}_{i\in\mathcal{N}})$
such that if $T_{k}\geq\tilde{T}$ for all $k$, then

${\rm Pr}\left(\bm{\pi}_{k}\in\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\right)\geq 1-\xi,$

for all sufficiently large $k$.

A proof of Theorem 7 is available in Appendix -E. The details mirror those of
Theorem 6. Unlike the setting with global state observability, however, here
it is possible that play settles at a subjective equilibrium that is not an
objective equilibrium. That is, it is possible that $\left(\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\right)\setminus\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}\not=\varnothing$,
and that Algorithm 3 drives play to such a policy.

###  VI-C Learning with Compressed State Observability State

We conclude this section with a discussion of convergence guarantees for
Algorithm 3 under compressed state observability (Assumption 3). As we have
discussed previously, there is no guarantee that the set $\bm{\Gamma}_{S}$
contains $\epsilon$-equilibrium policies—either in the objective sense or in
the subjective sense using the naively learned subjective function family
$(\mathcal{V}^{*},\mathcal{W}^{*})$. As a result, the convergence guarantees
in this setting are highly qualified, and must be made with a potentially
restrictive assumption that subjective $\epsilon$-equilibrium exist within the
set of policies $\bm{\Pi}$.

###### Assumption 10

Fix $\epsilon>0$. Assume that the set of
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-equilibrium is non-
empty. That is,

${\rm Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing.$

###### Assumption 11

Fix $\epsilon>0$. Assume that $\bm{\Pi}$ is a fine quantization of
$\bm{\Gamma}_{S}$ satisfying: (1) $\Pi^{i}=\Pi^{j}$ for all
$i,j\in\mathcal{N}$; (2) $\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\not=\varnothing$; (3) For
any $\bm{\pi}\in\bm{\Pi}$, $\bm{\pi}$ is soft.

In analogy to the preceding parameter restriction, we again restrict $d^{i}$
to be positive but small.

###### Assumption 12

For all $i\in\mathcal{N}$, $d^{i}\in(0,\bar{d}_{\rm comp})$, where
$\bar{d}_{\rm comp}=\bar{d}_{\rm comp}(\epsilon,\bm{\Pi})$ is specified in
Appendix -F.

###### Theorem 8

Let $\epsilon>0$ and let $\mathcal{G}$ be a partially observed $N$-player
mean-field game satisfying Assumptions 3, 5, and 10. Suppose the policy set
$\bm{\Pi}$ and the tolerance parameters $\\{d^{i}\\}_{i\in\mathcal{N}}$
satisfy Assumptions 11 and 12, and suppose all players follow Algorithm 3. For
any $\xi>0$, there exists
$\tilde{T}=\tilde{T}(\xi,\epsilon,\bm{\Pi},\\{d^{i}\\}_{i\in\mathcal{N}})$
such that if $T_{k}\geq\tilde{T}$ for all $k$, then

${\rm Pr}\left(\bm{\pi}_{k}\in\bm{\Pi}\cap{\rm
Subj}_{\epsilon}(\mathcal{V}^{*},\mathcal{W}^{*})\right)\geq 1-\xi,$

for all sufficiently large $k$.

##  VII Discussion

###  VII-A On Observation Channels

As previously described in §II-C, the standard information structure available
to players mean-field games is that of mean-field state observability
(Assumption 2), wherein at time $t\geq 0$, player $i\in\mathcal{N}$ observes
its local state $x^{i}_{t}$ and the mean-field state
$\mu(\cdot|\textbf{x}_{t})$, a probability distribution over $X_{{\rm loc}}$.
We now consider situations in which compressed state observability (Assumption
3) may be more appropriate.

To determine the most appropriate observation channel used in the model for a
particular application, it is natural to begin by asking how a player’s
observations are actually obtained in the application itself. (Here, we
emphasize that the actual observation channel encountered need not be the same
as the observation channel used in the model of the game.) We envision three
(actual) observation channels as being the most plausible:

  1. 1.

An agent may obtain its own readings on the global state variable through its
own local sensors. Such an (actual) observation channel is truly decentralized
and would result in a rather limited view of the overall system. Consequently,
this may give rise to compressed state observability in and of itself, and the
actual observation channel may be used as the model’s observation channel.

  2. 2.

Agents may use local sensors to obtain a partial view of the system, and then
supplement this knowledge by communicating with nearby agents. This, too,
would give rise to a limited view of the overall system. Here, too, one may
naturally take the model’s observation channel to be the same as the actual
observation channel, and Assumption 3 may be more appropriate than Assumption
2.

  3. 3.

Agents may obtain their observations through some type of centralized entity,
which monitors the local states of all agents and then computes and broadcasts
a (possibly compressed) signal about the mean-field state. For example, in an
application where agents are autonomous vehicles, local states are locations
in a traffic network, and action selection corresponds to selection of a path
to one’s destination, agents may rely on a satellite navigation system to
locate themselves in the traffic network and also to identify which road links
are congested. In this set-up, if the central entity broadcasts a compressed
signal, then the actual observation channel gives rise to compressed state
observability. Such is the case, for instance, with navigation systems that
report road congestion using a three-tiered system of low-, moderate-, and
high-congestion road links.

In addition to applications where the actual observation channel results in a
limited view of the overall system, compressed state observability may also
arise in systems with rich (actual) observation channels if players
voluntarily choose to discard information in their learning process. When the
number of players, $N$, and the number of local states, $|X_{\rm loc}|$, are
both moderately large, the set of empirical measures ${\rm
Emp}_{N}=\\{\mu(\cdot|\textbf{s}):\textbf{s}\in\textbf{X}\\}$ becomes unwieldy
for the purposes of (tabular) learning. As such, it is reasonable to expect
that naive independent learning agents will employ some form of function
approximation, with quantization of ${\rm Emp}_{N}$ offering the simplest form
of function approximation. Moreover, a common compression scheme may be shared
by all agents in such an application, perhaps as the result of some shared
“conventional wisdom” about the system.

###  VII-B Challenges to Proving Existence of Subjective Equilibrium Under
Compressed State Observability

Under global state observability (Assumption 1) and mean-field state
observability (Assumption 2), we have shown that naively learned subjective
$\epsilon$-equilibrium policies exist for $\epsilon>0$. Unfortunately, it is
difficult to produce analogous guarantees under the narrower information
structure of Assumption 3. We now discuss some complications that arise when
the observation channel is less informative, and we explain how this poses a
challenge to establishing existence of subjective equilibrium.

####  VII-B1 Challenges Preventing a Parallel Proof

The proofs of Lemmas 12 and 13 have two essential components. First, one
obtains an _objective_ stationary perfect equilibrium for the game, via Lemma
7 or Theorem 1. By the various continuity results, we then obtain a soft
policy that is sufficiently close to the equilibrium that their action values
and state values are close. Second, one uses Theorem 2 to relate the naively
learned values to known quantities—namely, the action values and state values
of the MDP faced by each player.

In the case where Assumption 3 holds, neither essential step outlined above
can be taken. In particular, as we have previously discussed, stationary
perfect $\epsilon$-equilibrium need not exist under compressed state
observability, which precludes the first step. Moreover, since it is not the
case that player $i$ faces an MDP in its observation variable when the
remaining players follow a stationary policy $\bm{\pi}^{-i}$, one cannot use
the Q-function and value function as surrogates for the naively learned
quantities $W^{*i}_{\bm{\pi}}$ and $V^{*i}_{\bm{\pi}}$, respectively. For
these reasons, directly paralleling the proofs of Lemmas 12 and 13 is not
possible.

####  VII-B2 Obstacles to a More Direct Proof

Rather than attempting to parallel the proofs of Lemmas 12 and 13, one may
attempt to mimic the proof technique of [47] and prove the existence of
subjective equilibrium using the properties of the subjective best-response
correspondences. To use this approach, one may study the mappings

$\bm{\pi}\mapsto{\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i},\mathcal{V}^{*},\mathcal{W}^{*}),$

for each $i\in\mathcal{N}$ and some $\epsilon\geq 0$. If one can establish
that these correspondences satisfy various conditions, then invoking a fixed
point theorem (e.g. Kakutani’s fixed point theorem or a suitable
generalization) would establish existence of a
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-equilibrium.

This approach, too, comes with a number of obstacles. The first obstacle is
the definition of the subjective functions $V^{*i}_{\bm{\pi}}$ and
$W^{*i}_{\bm{\pi}}$ for policies $\bm{\pi}$ that are not soft. Defining these
functions to be the ${\rm Pr}^{\bm{\pi}}_{\nu_{0}}$-almost sure limits of the
iterates $\\{\widehat{J}^{i}_{t}\\}_{t\geq 0}$ and
$\\{\widehat{Q}^{i}_{t}\\}_{t\geq 0}$ is sensible only when these limits can
be guaranteed to exist and, furthermore, it is sensible only when these almost
sure limiting values do not depend on the sample path. This is the case when
$\bm{\pi}$ is soft, but may not be so when $\bm{\pi}$ is not soft. It appears
that one cannot easily bypass this issue by restricting the domain to be the
set of soft policies, since the set of soft policies is not compact in
$\bm{\Gamma}_{S}$.

A second and distinct obstacle has to do with the confounding effect of the
exploration policy $\pi^{i}$ used by player $i$ when learning. Recall that,
for a soft policy $\bm{\pi}$ and under Assumption 5, the naively learned
quantities $V^{*i}_{\bm{\pi}}$ and $W^{*i}_{\bm{\pi}}$ are the value function
and Q-function for _some_ MDP with state space $\varphi^{i}(\textbf{X})$.
Critically, this MDP depends on both $\pi^{i}$ and $\bm{\pi}^{-i}$, in
general.111If, instead, the MDP depended on $\bm{\pi}^{-i}$ alone, it would
follow immediately that ${\rm
Subj\text{-}BR}^{i}_{\epsilon}(\bm{\pi}^{-i},\mathcal{V}^{*},\mathcal{W}^{*})$
was non-empty, compact, and convex. As such, one cannot use standard results
from the theory of MDPs to establish that the subjective best-response
correspondences have the required properties.

####  VII-B3 Possible Avenues for Establishing Subjective Equilibrium Under
Compressed State Observability

One natural, albeit limited, approach to guaranteeing the existence of
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-equilibrium policies
is to narrow the class of games under consideration. For example, one may
restrict attention to mean-field games for which the transition kernel
$P_{{\rm loc}}$ depends on the mean-field state only through its compressed
representation, which is available to each player under Assumption 3. From
this, analogs to Lemma 8, mean-field symmetry, Theorem 1, and the final part
of Theorem 2 can be obtained, which in turn will allow one to employ the proof
technique of Lemmas 12 and 13.

##  VIII Conclusion

In this paper, we considered partially observed $N$-player mean-field games
from the point of view of decentralized independent learners. Independent
learning is characterized by ignoring the presence of other strategic agents
in the system, treating one’s environment as if it were a single agent MDP,
and naively running single agent learning algorithms to select one’s policy.
Using an analogy to near-optimality criteria for MDPs, we developed a notion
of subjective $\epsilon$-equilibrium for $N$-player mean-field games, and we
studied the convergence of naive single-agent learning iterates in the game
setting. After establishing the existence of subjective $\epsilon$-equilibrium
with respect to these naively learned value functions (under certain
observability conditions), we revisited the notion of $\epsilon$-satisficing
paths introduced in [46] and extended the notion to consider subjective
satisficing paths. In this framework, we studied the structural properties of
$N$-player mean-field games and argued that subjective $\epsilon$-satisficing
paths to subjective $\epsilon$-equilibrium exist under various information
structures for partially observed $N$-player mean-field games.

Apart from the structural and conceptual contributions described above, we
have also presented Algorithm 3, a decentralized independent learner for
playing partially observed $N$-player mean-field games, and we have argued
that Algorithm 3 drives policies to subjective $\epsilon$-equilibrium under
self-play. This algorithm and its convergence guarantees are significant for
three primary reasons: (1) To establish convergence of policies, our proof
program exploits the considerable (and heretofore underexploited) structure of
satisficing paths; (2) Unlike the bulk of results on learning in mean-field
games, the convergence guarantees of Algorithm 3 do not mandate that players
use the same policy at a given time or the same policy update rule to switch
policies at the end of an exploration phase. As such, our algorithm is capable
of describing learning dynamics for a population of homogenous agents that may
arrive at a joint policy consisting of heterogenous policies; (3) The learning
dynamics presented here result in system stability—in that policies settle to
a particular joint policy—but the emergent behaviour need not be an objective
equilibrium. Convergence to non-equilibrium policies may arise in real-world
strategic environments; our notion of naively learned subjective equilibrium
may present an interpretation for such real-world stability in some instances.

###  -A Proof of Lemma 8

###### Proof:

Fix $i\in\mathcal{N}$. Recall that $\mathbb{Y}=X_{{\rm loc}}\times{\rm
Emp}_{N}$ and player $i$’s observation function
$\varphi^{i}:\textbf{X}\to\mathbb{Y}$ is given by
$\varphi^{i}(\textbf{s})=(s^{i},\mu(\cdot|\textbf{s}))$ for any
$\textbf{s}\in\textbf{X}$. For any $k\geq 0$, we let
$y^{i}_{k}:=\varphi^{i}(\textbf{x}_{k})=(x^{i}_{k},\mu(\cdot|\textbf{x}_{k}))$.

Let $\nu\in\mathcal{P}(\textbf{X})$ be any initial distribution of the global
state variable and let $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$ be mean-field
symmetric. Let $\pi^{i}\in\Gamma^{i}_{S}$ be any stationary policy for player
$i$, and let $\bm{\pi}=(\pi^{i},\bm{\pi}^{-i})$. We must show that the
following holds for all $t\geq 0$ and any $A\subseteq\mathbb{Y}$:

$\displaystyle{\rm Pr}^{\bm{\pi}}_{\nu}\left[y^{i}_{t+1}\in
A\middle|\\{y^{i}_{k},u^{i}_{k}:0\leq k\leq t\\}\right]={\rm
Pr}^{\bm{\pi}}_{\nu}\left[y^{i}_{t+1}\in A\middle|y^{i}_{t},u^{i}_{t}\right],$

${\rm Pr}^{\bm{\pi}}_{\nu}$-almost surely.222For brevity, we omit the
qualifier “${\rm Pr}^{\bm{\pi}}_{\nu}$-almost surely” on all subsequent
equalities involving conditional expectations.

Fix $t\geq 0$. For any $A\subseteq\mathbb{Y}$, let $\textbf{1}_{A}$ denote the
indicator function of the event $\\{y^{i}_{t+1}\in A\\}$. Using the law of
iterated expectations and conditioning on the (finer) $\sigma$-algebra
generated by the random variables $\\{\textbf{x}_{k},u^{i}_{k}:0\leq k\leq
t\\}$, we have

$\displaystyle
E^{\bm{\pi}}_{\nu}\left(\textbf{1}_{A}\middle|\\{y^{i}_{k},u^{i}_{k}:0\leq
k\leq t\\}\right)=$ $\displaystyle
E^{\bm{\pi}}_{\nu}\left[E^{\bm{\pi}}_{\nu}\left(\textbf{1}_{A}\middle|\\{\textbf{x}_{k},u^{i}_{k}:0\leq
k\leq t\\}\right)\middle|\\{y^{i}_{k},u^{i}_{k}:0\leq k\leq t\\}\right]$
$\displaystyle=$ $\displaystyle
E^{\bm{\pi}}_{\nu}\left[E^{\bm{\pi}}_{\nu}\left(\textbf{1}_{A}\middle|\textbf{x}_{t},u^{i}_{t}\right)\middle|\\{y^{i}_{k},u^{i}_{k}:0\leq
k\leq t\\}\right].$

Thus, it suffices to show that
$E^{\bm{\pi}}_{\nu}\left(\textbf{1}_{A}\middle|\textbf{x}_{t},u^{i}_{t}\right)=E^{\bm{\pi}}_{\nu}\left(\textbf{1}_{A}\middle|y^{i}_{t},u^{i}_{t}\right)$
holds for all $A\subseteq\mathbb{Y}$. Moreover, since $\mathbb{Y}$ is a finite
set, it suffices to show that this holds for all singletons $A=\\{w\\}$,
$w\in\mathbb{Y}$.