Networked Communication for Decentralised Agents in Mean-Field Games

## Abstract

Abstract We introduce networked communication to the mean-field game framework, in particular to oracle-free settings where N 𝑁 N italic_N decentralised agents learn along a single, non-episodic run of the empirical system. We prove that our architecture has sample guarantees bounded between those of the centralised- and independent-learning cases. We provide the order of the difference in these bounds in terms of network structure and number of communication rounds, and also contribute a policy-update stability guarantee. We discuss how the sample guarantees of the three theoretical algorithms do not actually result in practical convergence. We therefore show that in practical settings where the theoretical parameters are not observed (leading to poor estimation of the Q-function), our communication scheme significantly accelerates convergence over the independent case (and sometimes even the centralised case), without relying on the assumption of a centralised learner. We contribute further practical enhancements to all three theoretical algorithms, allowing us to present their first empirical demonstrations. Our experiments confirm that we can remove several of the theoretical assumptions of the algorithms, and display the empirical convergence benefits brought by our new networked communication. We additionally show that the networked approach has significant advantages, over both the centralised and independent alternatives, in terms of robustness to unexpected learning failures and to changes in population size.

## 1 Introduction

The mean-field game (MFG) framework (Lasry & Lions, ; Huang et al., ) has been used to address the difficulty faced by multi-agent reinforcement learning (MARL) regarding computational scalability as the number of agents increases. It models a representative agent as interacting not with the other individuals in the population on a per-agent basis, but instead with a distribution of other agents, known as the mean field. The MFG framework analyses the limiting case when the population consists of an infinite number of symmetric and anonymous agents, that is, they have identical reward and transition functions which depend on the mean-field distribution rather than on the actions of specific other players. In this work we focus on MFGs with stationary population distributions (‘stationary MFGs’) (Xie et al., ; Anahtarci et al., ; Zaman et al., ; Yardim et al., ), for which the solution concept is the MFG-Nash equilibrium (MFG-NE), which reflects the situation when each agent responds optimally to the population distribution that arises when all other agents follow that same optimal behaviour. The MFG-NE can be used as an approximation for the Nash equilibrium (NE) in a finite-agent game, with the error in the solution reducing as the number of agents N tends to infinity (Anahtarci et al., ; Saldi et al., ; Yardim et al., ; Toumi et al., ; Hu & Zhang, ). MFGs have therefore been used to find approximate solutions for a wide variety of real-world problems involving a large but finite number of agents, which might otherwise have been too difficult to solve; see Appx. F for further details.

For large, complex many-agent systems in the real world (e.g. swarm robotics or autonomous vehicle traffic), it may not be feasible to find MFG-NEs analytically or via oracles/simulations of an infinite population (as they have been traditionally), such that learning must instead be conducted directly by the original finite population in its deployed environment. In such settings, in contrast to many previous approaches, desirable qualities for MFG algorithms include: learning from the empirical distribution of $N$ agents (without generation or manipulation of this distribution by the algorithm itself or by an external oracle); learning from a single continued system run that is not arbitrarily reset as in episodic learning; model-free learning; decentralisation; fast practical convergence; and robustness to unexpected failures of decentralised learners or changes in population size (Korecki et al., ).

Conversely, MFG frameworks have traditionally been largely theoretical, and methods for finding equilibria have often relied on assumptions that are too strong for real-world applications (Huang et al., ; Anahtarci et al., ; Lauriere et al., ; Perrin et al., ; Laurière et al., ; Guo et al., ; Perrin et al., ; Elie et al., ; Carmona & Laurière, ; Cao et al., ; Germain et al., ; Fouque & Zhang, ; Algumaei et al., ; Angiuli et al., ); see Appx. F for an extended discussion of this related work. In particular, almost all prior work relies on a centralised controller to orchestrate the learning of all agents (Xie et al., ; Anahtarci et al., ; Zaman et al., ; Laurière et al., ; Guo et al., ). However, outside of MFGs, the multi-agent systems community has recognised that the existence of a central controller is a very strong assumption, as well as one that can both restrict scalability by constituting a bottleneck for computation and communication, and reveal a single point of failure for the whole system (Zhang et al., ; ; Wai et al., ; Zhang et al., ; Chen et al., ; Jiang et al., ). For example, if the single server coordinating all the autonomous vehicles in a smart city were to crash, the entire road network would cease to operate. As an alternative, recent work has explored MFG algorithms for independent learning (Yardim et al., ; Mguni et al., ; Yongacoglu et al., ; ; Grammatico et al., ; ; Parise et al., ; Grammatico et al., ). However, prior works focus on theoretical sample guarantees rather than on practical convergence speed, and have largely not considered robustness in the senses we address, despite fault-tolerance being one of the original motivations behind many-agent systems.

We address all of these desiderata by novelly introducing a communication network to the MFG setting. Communication networks have had success in other multi-agent settings, removing the reliance on inflexible, centralised structures (Zhang et al., ; Wai et al., ; Zhang et al., ; Chen et al., ; Doan et al., ; Lin et al., ; Heredia et al., ; Kar et al., ; Suttle et al., ). We focus on ‘coordination games’, i.e. where agents can increase their individual rewards by following the same strategy as others and therefore have an incentive to communicate policies, even if the MFG setting itself is technically non-cooperative. Thus our work can be applied to real-world problems in e.g. traffic signal control, formation control in swarm robotics, and consensus and synchronisation e.g. for sensor networks.

In this work, we show that when the agents’ state-action value functions (Q-functions) can be only roughly estimated due to fewer samples/updates, possibly leading to high variance in policy updates, then propagating policies that are estimated to be better through the population via the communication network leads to faster convergence than that achieved by agents learning entirely independently. This is crucial in large complex environments that may be encountered in real applications, where the idealised hyperparameter choices (such as learning rates and numbers of iterations) required in previous works for theoretical convergence guarantees will be infeasible in practice. We compare our networked architecture with modified versions of earlier theoretical algorithms for the centralised and independent settings; we extend the original algorithms with experience replay buffers, without which we found them unable to converge in practical time. While the use of buffers means that the original theoretical sample guarantees no longer apply, we argue that this is preferable since these guarantees were in any case impractical. On this basis, we conduct numerical comparisons of the three architectures, demonstrating the benefits of communication for both convergence speed and system robustness. For further discussion of how networked communication can benefit robustness in large multi-agent systems, see Appx. D. In summary, our key contributions include the following:

- •
We prove that a theoretical version of our new networked algorithm (Alg. 1) has sample guarantees bounded between those of the centralised and independent settings for learning with a single, non-episodic run of the empirical system. We provide the order of the difference in these bounds in terms of network structure and number of communication rounds, and also contribute a policy-update stability guarantee (Sec. 3.3 and Appx. B.8).
- •
All three theoretical algorithms do not permit convergence in practical time; we show that in practical settings our communication scheme can significantly benefit convergence speed over the independent case, and sometimes even the centralised case (Sec. 3.4.1).
- •
We novelly modify all three theoretical algorithms (Alg. 2) to make their practical convergence feasible, most notably by including an experience replay buffer, allowing us to contribute the first empirical demonstrations of all three algorithms (Sec. 3.4.2).
- •
Our experiments demonstrate the convergence benefits brought by our networked communication, and show we can remove several of the algorithms’ theoretical assumptions (a goal shared by other work on the practicality of MFG algorithms (Cui et al., )) (Sec. 4.1).
- •
We further demonstrate that our decentralised communication architecture brings significant benefits over both the centralised and independent alternatives in terms of robustness to unexpected learning failures and changes in population size (Sec. 4.1 and Appx. E.4).

The main paper is structured as follows: notation and preliminaries are given in Sec. 2; the theoretical algorithms and results are presented in Secs. 3.1-3.3; practical enhancements to the algorithms are given in Sec. 3.4; and experiments and discussion are provided in Sec. 4. Limitations and future work are found in Appx. G, and the broader social impact is considered in Sec. 5.

## 2 Preliminaries

We use the following notation. $N$ is the number of agents in a population, with $\mathcal{S}$ and $\mathcal{A}$ representing the finite state and common action spaces, respectively. The sets $\mathcal{S}$ and $\mathcal{A}$ are equipped with the discrete metric $d(x,y)=\mathbb{1}_{x\neq y}$. The set of probability measures on a finite set $\mathcal{X}$ is denoted $\Delta_{\mathcal{X}}$, and $\mathbf{e}_{x}\in\Delta_{\mathcal{X}}$ for $x\in\mathcal{X}$ is a one-hot vector with only the entry corresponding to $x$ set to 1, and all others set to 0. For time $t\geq 0$, $\hat{\mu}_{t}$ = $\frac{1}{N}\sum^{N}_{i=1}\sum_{s\in\mathcal{S}}$ $\mathbb{1}_{s^{i}_{t}=s}\mathbf{e}_{s}$ $\in$ $\Delta_{\mathcal{S}}$ is a vector denoting the empirical state distribution of the $N$ agents at time $t$. The set of policies is $\Pi$ = {$\pi$ : $\mathcal{S}\rightarrow\Delta_{\mathcal{A}}$}, and the set of Q-functions is denoted $\mathcal{Q}=\{q:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}\}$.
For $\pi,\pi^{\prime}\in\Pi$ and $q,q^{\prime}\in\mathcal{Q}$, we have the norms $||\pi-\pi^{\prime}||_{1}$ := $\sup_{s\in\mathcal{S}}||\pi(s)-\pi^{\prime}(s)||_{1}$ and $||q-q^{\prime}||_{\infty}$ := $\sup_{s\in\mathcal{S},a\in\mathcal{A}}|q(s,a)-q^{\prime}(s,a)|$.

Function $h:\Delta_{\mathcal{A}}\rightarrow\mathbb{R}_{\geq 0}$ denotes a strongly concave function, which we implement as the scaled entropy regulariser $\lambda h_{ent}(u)=-\lambda\sum_{a}u(a)\log u(a)$, for $a\in\mathcal{A}$, $u\in\Delta_{\mathcal{A}}$ and $\lambda>0$. As in some earlier works (Anahtarci et al., ; Yardim et al., ; Algumaei et al., ; Cui & Koeppl, ; Guo et al., ; Yu & Yuan, ), regularisation is theoretically required to ensure the contractivity of operators and continued exploration, and hence algorithmic convergence. However, it has been recognised that modifying the RL objective in this way can bias the NE (Yardim et al., ; Hu & Zhang, ; Lauriere et al., ; Su & Lu, ). We show in our experiments that we are able to reduce $\lambda$ to 0 with no detriment to convergence.

###### Definition 1 ( N -player symmetric anonymous games) .

An N-player stochastic game with symmetric, anonymous agents is given by the tuple $\langle$$N$, $\mathcal{S}$, $\mathcal{A}$, $P$, $R$, $\gamma$$\rangle$, where $\mathcal{A}$ is the action space, identical for each agent; $\mathcal{S}$ is the identical state space of each agent, such that their initial states are {$s^{i}_{0}$}${}_{i=1}^{N}\in\mathcal{S}^{N}$ and their policies are {$\pi^{i}$}${}_{i=1}^{N}\in\Pi^{N}$. $P$ : $\mathcal{S}$ $\times$ $\mathcal{A}$ $\times$ $\Delta_{\mathcal{S}}$ $\rightarrow$ $\Delta_{\mathcal{S}}$ is the transition function and $R$ : $\mathcal{S}$ $\times$ $\mathcal{A}$ $\times$ $\Delta_{\mathcal{S}}$ $\rightarrow$ [0,1] is the reward function, which map each agent’s local state and action and the population’s empirical distribution to transition probabilities and bounded rewards, respectively, i.e.

$$ $s^{i}_{t+1}\sim P(\cdot|s^{i}_{t},a^{i}_{t},\hat{\mu}_{t}),\;\;\;r^{i}_{t}=R(s ^{i}_{t},a^{i}_{t},\hat{\mu}_{t}),\;\;\;\forall i=1,\dots,N.$ $$

The policy of an agent is given by $a^{i}_{t}\sim\pi^{i}(s^{i}_{t})$, that is, each agent only observes its own state, and not the joint state or empirical distribution of the population.

###### Definition 2 ( N -player discounted regularised return) .

With joint policies $\bm{\pi}$ := ($\pi^{1},\dots,\pi^{N}$) $\in\Pi^{N}$, initial states sampled from a distribution $\upsilon_{0}\in\Delta_{\mathcal{S}}$ and $\gamma$ $\in$ [0,1) as a discount factor, the expected discounted regularised returns of each agent $i$ in the symmetric anonymous game are given by

$$ $\Theta^{i}_{h}(\bm{\pi},\upsilon_{0})=\mathbb{E}\left[\sum^{\infty}_{t=0} \gamma^{t}(R(s^{i}_{t},a^{i}_{t},\hat{\mu}_{t})+h(\pi^{i}(s^{i}_{t})))\bigg{|} \begin{subarray}{c}s^{j}_{0}\sim\upsilon_{0}\\ a^{j}_{t}\sim\pi^{j}(s^{j}_{t})\\ s^{j}_{t+1}\sim P(\cdot|s^{j}_{t},a^{j}_{t},\hat{\mu}_{t})\end{subarray}, \forall t\geq 0,j\in\{1,\dots,N\}\right].$ $$

###### Definition 3 ( $\delta$ -NE) .

Say $\delta>0$ and $(\pi,\bm{\pi}^{-i})$ := $(\pi^{1},\dots\pi^{i-1},\pi,\pi^{i+1},\dots,\pi^{N})\in\Pi^{N}$. An initial distribution $\upsilon_{0}\in\Delta_{\mathcal{S}}$ and an $N$-tuple of policies $\bm{\pi}$ := ($\pi^{1},\dots,\pi^{N}$) $\in\Pi^{N}$ form a $\delta$-NE ($\bm{\pi}$, $\upsilon_{0}$), if $\forall i$ = 1,$\dots,N$

$$ $\Theta^{i}_{h}(\bm{\pi},\upsilon_{0})\geq\max_{\pi\in\Pi}\Theta^{i}_{h}((\pi, \bm{\pi}^{-i}),\upsilon_{0})-\delta.$ $$

At the limit as $N\rightarrow\infty$, the population of infinitely many agents can be characterised as a limit distribution $\mu\in\Delta_{\mathcal{S}}$. We denote the expected discounted return of the representative agent in the infinite-agent game - termed an MFG - as $V$, rather than $\Theta$ as in the finite $N$-agent case.

###### Definition 4 (Mean-field discounted regularised return) .

For a policy-population pair ($\pi,\mu$) $\in\Pi\times\Delta_{\mathcal{S}}$,

$$ $V_{h}(\pi,\mu)=\mathbb{E}\left[\sum^{\infty}_{t=0}\gamma^{t}(R(s_{t},a_{t},\mu )+h(\pi(s_{t})))\bigg{|}\begin{subarray}{c}s_{0}\sim\mu\\ a_{t}\sim\pi(s_{t})\\ s_{t+1}\sim P(\cdot|s_{t},a_{t},{\mu})\end{subarray}\right].$ $$

A stationary MFG is one that has a unique population distribution that is stable with respect to a given policy, and the agents’ policies are not time- or population-dependent.

###### Definition 5 (NE of stationary MFG) .

For a policy $\pi^{*}\in\Pi$ and a population distribution $\mu^{*}\in\Delta_{\mathcal{S}}$, the pair ($\pi^{*},\mu^{*}$) is a stationary MFG-NE if the following optimality and stability conditions hold:

$$ $\displaystyle\textrm{optimality:}\quad V_{h}(\pi^{*},\mu^{*})=\max_{\pi}V_{h}( \pi,\mu^{*}),$ $\displaystyle\textrm{stability:}\quad\mu^{*}(s)=\sum_{s^{\prime},a^{\prime}} \mu^{*}(s^{\prime})\pi^{*}(a^{\prime}|s^{\prime})P(s|s^{\prime},a^{\prime},\mu ^{*}).$ $$

If the optimality condition is only satisfied with $V_{h}(\pi^{*}_{\delta},\mu^{*}_{\delta})\geq\max_{\pi}V_{h}(\pi,\mu^{*}_{
\delta})-\delta$, then ($\pi^{*}_{\delta},\mu^{*}_{\delta}$) is a $\delta$-NE of the MFG, where $\mu^{*}_{\delta}$ is obtained from the stability equation and $\pi^{*}_{\delta}$.

The MFG-NE can be used as an approximate NE of the finite $N$-player game in which we may have originally been interested but which is difficult to solve in itself (Yardim et al., ; Lauriere et al., ):

###### Proposition 1 ( N -player NE and MFG-NE (Thm. 1, (Anahtarci et al., 2023 ) )) .

If ($\pi^{*},\mu^{*}$) is a MFG-NE, then, under certain Lipschitz conditions (Anahtarci et al., ), for any $\delta>0$, there exists $N(\delta)\in\mathbb{N}_{>0}$ such that, for all $N\geq N(\delta)$, the joint policy $\bm{\pi}=\{\pi^{*},\pi^{*},\dots,\pi^{*}\}\in\Pi^{N}$ is a $\delta$-NE of the $N$-player game.

###### Remark 1 .

It can be shown that $\delta$ can be characterised further in terms of $N$, with ($\pi^{*},\mu^{*}$) being an $\mathcal{O}$($\frac{1}{\sqrt{N}}$)-NE of the $N$-player symmetric anonymous game (Yardim et al., ).

For our new, networked learning algorithm, we also introduce the concept of a time-varying communication network, where the links between agents that make up the network may change at each time step $t$. Most commonly we might think of such a network as depending on the spatial locations of decentralised agents, such as physical robots, which can communicate with neighbours that fall within a given broadcast radius. When the agents move in the environment, their neighbours and therefore communication links may change. However, the dynamic network can also depend on other factors that may or may not depend on each agent’s state $s^{i}_{t}$. For example, even a network of fixed-location agents can change depending on which agents are active and broadcasting at a given time $t$, or if their broadcast radius changes, perhaps in relation to signal or battery strength.

###### Definition 6 (Time-varying communication network) .

The time-varying communication network {$\mathcal{G}_{t}$}t≥0 is given by $\mathcal{G}_{t}$ = ($\mathcal{N},\mathcal{E}_{t}$), where $\mathcal{N}$ is the set of vertices each representing an agent $i=1,\dots,N$, and the edge set $\mathcal{E}_{t}$ $\subseteq$ {(i,j) : i,j $\in$ $\mathcal{N}$, i $\neq$ j} is the set of undirected communication links by which information can be shared at time t.

A network is connected if there is a sequence of distinct edges forming a path between each distinct pair of vertices. The union of a collection of graphs {$\mathcal{G}_{t},\mathcal{G}_{t+1},\cdots,\mathcal{G}_{t+\omega}\}$ ($\omega\in\mathbb{N}$) is the graph with vertices and edge set equalling the union of the vertices and edge sets of the graphs in the collection (Jadbabaie et al., ). A collection is jointly connected if its members’ union is connected.

###### Definition 1 ( N -player symmetric anonymous games) .

###### Definition 2 ( N -player discounted regularised return) .

###### Definition 3 ( δ 𝛿 \delta italic_δ -NE) .

###### Definition 4 (Mean-field discounted regularised return) .

###### Definition 5 (NE of stationary MFG) .

###### Proposition 1 ( N -player NE and MFG-NE (Thm. 1, (Anahtarci et al., 2023 ) )) .

###### Remark 1 .

###### Definition 6 (Time-varying communication network) .

## 3 Learning with networked, decentralised agents

Summary We first discuss theoretical versions of our operators and algorithm (Secs. 3.1, 3.2) to show that our networked framework has sample guarantees bounded between those of the centralised- and independent-learning cases (Sec. 3.3). We then show that our novel incorporation of an experience replay buffer (Sec. 3.4.2), along with networked communication, means that empirically we can remove many of the theoretical assumptions and practically infeasible hyperparameter choices that are required by the sample guarantees of the theoretical algorithms, in which cases we demonstrate that our networked algorithm can significantly outperform the independent algorithm, and sometimes even the centralised one (Sec. 4).

### 3.1 Learning with N 𝑁 N italic_N agents from a single run

We begin by outlining the basic procedure for solving the MFG using the $N$-agent empirical distribution and a single, continuous system run. The two underlying operators are the same for the centralised, independent and networked architectures; in the latter two cases all agents apply the operators individually, while in the centralised setting a single ‘central’ agent (the agent with index $i=1$) estimates the Q-function and computes an updated policy that is pushed to all the other agents.

We define, for $h_{\mathrm{max}}>0$ and $h:\Delta_{\mathcal{A}}\rightarrow[0,h_{\mathrm{max}}]$, $u_{\mathrm{max}}\in\Delta_{\mathcal{A}}$ such that $h(u_{\mathrm{max}})=h_{\mathrm{max}}$. We further define $q_{\mathrm{max}}:=\frac{1+h_{\mathrm{max}}}{1-\gamma}$, and set $\pi_{\mathrm{max}}\in\Pi$ such that $\pi_{\mathrm{max}}(s)=u_{\mathrm{max}},\forall s\in\mathcal{S}$. For any $\Delta h\in\mathbb{R}_{>0}$, we also define the convex set $\mathcal{U}_{\Delta h}$ := {$u\in\Delta_{\mathcal{A}}:h(u)\geq h_{\mathrm{max}}-\Delta h\}$.

Learning agents use the stochastic temporal difference (TD)-learning operator to repeatedly update an estimate of the Q-function of their current policy with respect to the current empirical distribution, i.e. to approximate the operator $\Gamma_{q}$ (Def. 12, Appx. A):

###### Definition 7 (Stochastic TD-learning operator, simplified from Def. 4.1 in Yardim et al. ( 2023 ) ) .

We define $\mathcal{Z}:=\mathcal{S}\times\mathcal{A}\times[0,1]\times\mathcal{S}\times
\mathcal{A}$, and say that $\zeta^{i}_{t}$ is the transition observed by agent $i$ at time $t$, given by $\zeta^{i}_{t}=(s^{i}_{t},a^{i}_{t},r^{i}_{t},s^{i}_{t+1},a^{i}_{t+1})$. The TD-learning operator $\tilde{F}^{\pi}_{\beta}:\mathcal{Q}\times\mathcal{Z}\rightarrow\mathcal{Q}$ is defined,
for any $Q\in\mathcal{Q},\zeta_{t}\in\mathcal{Z},\beta\in\mathbb{R}$, as

$$ $\tilde{F}^{\pi}_{\beta}(Q,\zeta_{t})=Q(s_{t},a_{t})-\beta\left(Q(s_{t},a_{t})- r_{t}-h(\pi(s_{t}))-\gamma\left(Q(s_{t+1},a_{t+1})\right)\right).$ $$

Having estimated the Q-function of their current policy, agents update this policy by selecting, for each state, a probability distribution over their actions that maximises the combination of three terms (Def. 8): 1. the value of the given state with respect to the estimated Q-function; 2. a regulariser over the action probability distribution (in practice, we maximise the scaled entropy of the distribution); 3. a metric of similarity between the new action probabilities for the given state and those of the previous policy, given by the squared two-norm of the difference between the two distributions. We can alter the importance of the similarity metric relative to the other two terms by varying a parameter $\eta$, which is equivalent to changing the learning rate of the policy update. The three terms in the maximisation function can be seen in the policy mirror ascent (PMA) operator:

###### Definition 8 (Policy mirror ascent operator (Def. 3.5, (Yardim et al., 2023 ) )) .

For a learning rate $\eta>0$ and $L_{h}:=L_{a}+\gamma\frac{L_{s}K_{a}}{2-\gamma K_{s}}$ (where these constants are defined in Assumption 1 in Appx. A), the PMA update operator $\Gamma^{md}_{\eta}:\mathcal{Q}\times\Pi\rightarrow\Pi$ is defined as

$$ $\Gamma^{md}_{\eta}(Q,\pi)(s):=\underset{u\in\mathcal{U}_{L_{h}}}{\arg\max} \left(\langle u,q(s,\cdot)\rangle+h(u)-\frac{1}{2\eta}||u-\pi(s)||^{2}_{2} \right),\forall s\in\mathcal{S},\forall Q\in\mathcal{Q},\forall\pi\in\Pi.$ $$

The theoretical learning algorithm
has three nested loops (see Lines 4, 6 and 7 of Alg. 1). The policy update is applied $K$ times. Before the policy update in each of the $K$ loops, agents update their estimate of the Q-function by applying the stochastic TD-learning operator $M_{pg}$ times. Prior to the TD update in each of the $M_{pg}$ loops, agents take $M_{td}$ steps in the environment without updating. The $M_{td}$ loops exist to create a delay between each TD update to reduce bias when using the empirical distribution to approximate the mean field in a single system run (Kotsalis et al., ). However, we find in our experiments that we are able to essentially remove the inner $M_{td}$ loops (Sec. 4.1).

###### Definition 7 (Stochastic TD-learning operator, simplified from Def. 4.1 in Yardim et al. ( 2023 ) ) .

###### Definition 8 (Policy mirror ascent operator (Def. 3.5, (Yardim et al., 2023 ) )) .

### 3.2 Decentralised communication between agents

In our novel algorithm Alg. 1, agents compute policy updates in a decentralised manner as in the independent case (Lines 5-12), before exchanging policies with neighbours by the following method, which allows policies to spread through the population. Coupled to their updated policy $\pi^{i}_{k+1}$, agents generate a value $\sigma^{i}_{k+1}$ (Line 13). For our theoretical results, we do not focus on a specific method for generating $\sigma^{i}_{k+1}$, such that it can be arbitrary for Thms. 1 and 4 below, and with few restrictions for Thms. 2 and 3. In Sec. 3.4.1 on the practical running of our algorithm, we introduce a specific mechanism for generating $\sigma^{i}_{k+1}$ which advantageously impacts empirical convergence.

Agents broadcast their policy $\pi^{i}_{k+1}$ and the associated $\sigma^{i}_{k+1}$ value to their neighbours (Line 15). Agents have a certain broadcast radius, which defines the structure of the possibly time-varying communication network. Of the policies and associated values received by a given agent (including its own) (Line 16), the agent selects a $\sigma^{j}_{k+1}$ with a probability defined by a softmax function over the received values, and adopts the policy associated with this $\sigma^{i}_{k+1}$, i.e. it sets its own current $\pi^{i}_{k+1}$ and $\sigma^{i}_{k+1}$ to the ones it has selected (Lines 17, 18). This process continues for $C$ communication rounds, before the Q-function estimation steps begin again. After each round, the agents take a step in the environment (Line 19), such that if the communication network is affected by the agents’ states, then agents that are unconnected from any others in a given communication round might become connected in the next. (In our experiments we set $C$ as 1 to show the benefits to convergence speed brought by even a single communication round.) We assume the softmax function is subject to a possibly time-varying temperature parameter $\tau_{k}$. We discuss the effects of the values of $C$ and $\tau_{k}$, and the mechanism for generating $\sigma^{i}_{k+1}$, in subsequent sections.

###### Remark 2 .

Our networked architecture is in effect a generalisation of both the centralised and independent settings (Algs. 2 and 3, Yardim et al. ()). The independent setting is the special case where there are no communication rounds, i.e. $C=0$. The centralised setting is the special case when the method for generating $\sigma^{i}_{k+1}$ involves a unique ID for each agent, with the central learner agent being assumed to generate the highest value by default. In this case we assume $\tau_{k}\rightarrow 0$ (such that the softmax becomes a max function), and that the communication network becomes jointly connected repeatedly, such that the central learner’s policy is always adopted by the entire population, assuming $C$ is large enough that the number of jointly connected collections of graphs occurring within $C$ is equal to the largest diameter of the union of any collection (Rajagopalan & Shah, ; Zhang et al., ).

###### Remark 3 .

In practice, when referring in the following to a centralised version of the networked Alg. 1, for simplicity we assume there is no communication and instead that the updated policy $\pi^{1}_{k+1}$ of the central learner $i=1$ is pushed to all other agents after Line 12, as in Alg. 2 of (Yardim et al., ).

Figure: Algorithm 1 Networked learning with single system run

###### Remark 2 .

###### Remark 3 .

### 3.3 Properties of policy adoption

We first give two theoretical results comparing the sample guarantees of our networked case with those of the other settings; the results respectively depend on whether the networked agents select which communicated policies to adopt at random or not. We then provide the order of the difference in these bounds in the non-random case in terms of network structure and number of communication rounds. We finally give in Appx. B.8 a policy-update stability guarantee, which applies in all scenarios. Appx. A contains the full set of technical assumptions on which these theorems rely.

###### Theorem 1 (Networked learning with random adoption ) .

Full version in Appx. B.2. Say that $\pi^{*}$ is the unique MFG-NE policy. Let $\varepsilon>0$ be an arbitrary value that reduces as $k$ increases by the following relation: $k=\frac{\log 8\varepsilon^{-1}}{\log L^{-1}_{\Gamma_{\eta}}}$, where the constant $L_{\Gamma_{\eta}}$ is defined in Lem. 2 in Appx. A. Let us assume that $C>0$ and $\tau_{k}\rightarrow\infty$, meaning that the softmax function approaches a uniform distribution such that the values of $\sigma^{i}_{k+1}$ are arbitrary and received policies are adopted at random. Then, under the technical assumptions given in Appx. B.2, the random output {$\pi^{i}_{K}$}i of Alg. 1 preserves the sample guarantees of the independent-learning case given in Lem. 3, i.e. the output satisfies, for all agents $i=1,\dots,N$, $\mathbb{E}\left[||\pi^{i}_{K}-\pi^{*}||_{1}\right]\;\leq\;\varepsilon+\mathcal
{O}\left(\frac{1}{\sqrt{N}}\right).$

Proof sketch. Random exchange of policies learnt in a decentralised manner does not change the expectation of the random output of the purely independent-learning setting i.e. where this exchange does not occur. Full proof in Appx. B.3.

Moreover we can show that if $\sigma^{i}_{k+1}$ is generated arbitrarily and uniquely for each $i$, then for $\tau_{k}\in\mathbb{R}_{>0}$ (such that the softmax function gives a non-uniform distribution and adoption of received policies is therefore non-random), the sample complexity of the networked learning algorithm is bounded between that of the centralised and independent algorithms:

###### Theorem 2 (Networked learning with non-random adoption ) .

Full version in Appx. B.5. Assume that Alg. 1 is run as in Thm. 1, except now $\tau_{k}\in\mathbb{R}_{>0}$. Assume also that $\sigma^{i}_{k+1}$ is generated uniquely for each $i$, in a manner independent of any metric related to $\pi^{i}_{k+1}$, e.g. $\sigma^{i}_{k+1}$ is random or related only to the index $i$ (so as not to bias the spread of any particular policy). Let the random output of this Algorithm be denoted as {$\pi^{i,net}_{K}$}i. Also consider an independent-learning version of the algorithm (i.e. with the same parameters except $C=0$) and denote its random output {$\pi^{j,ind}_{K}$}j; and a centralised version of the algorithm with the same parameters (see Rem. 3) and denote its random output as $\pi^{cent}_{K}$. Then, under the technical assumptions given in Appx. B.5, for all agents $i=1,\dots,N$ and $j=1,\dots,N$, the random outputs {$\pi^{i,net}_{K}$}i, {$\pi^{j,ind}_{K}$}j and $\pi^{cent}_{K}$ satisfy

$$ $\mathbb{E}\left[||\pi^{cent}_{K}-\pi^{*}||_{1}\right]\;\leq\;\mathbb{E}\left[| |\pi^{i,net}_{K}-\pi^{*}||_{1}\right]\leq\;\mathbb{E}\left[||\pi^{j,ind}_{K}- \pi^{*}||_{1}\right]\;\leq\;\varepsilon+\mathcal{O}\left(\frac{1}{\sqrt{N}} \right).$ $$

Proof sketch. Fewer distinct policies in the population means there is less bias in each learner’s estimation of the Q function. So methods for reducing the number of policies in the population (such as non-random adoption in the networked case) lead to faster convergence. Full proof in Appx. B.6.

###### Theorem 3 (Relation between communication network structure and order of difference between the frameworks’ bounds) .

In addition to the assumptions in Thm. 2, now also assume that the communication network $\mathcal{G}_{t}$ remains static and connected during the $C$ communication rounds, and that $\tau_{k}\rightarrow 0\;\forall k$ such that the softmax essentially becomes a max function. Say that $d_{\mathcal{G}}$ is the diameter of the network which is the same for all k, and that $0\leq C\leq d_{\mathcal{G}}$. Call the upper bound found in Thm. 2 for the three architectures $ub_{net}$, $ub_{ind}$ and $ub_{cent}$ respectively. Then we can say that the order of difference in convergence is as follows:

$$ $ub_{cent}+\mathcal{O}\left(\left(\frac{1}{d_{\mathcal{G}}}\right)^{C}\right)\; \;\approx\;\;ub_{net}\;\;\approx\;\;ub_{ind}-\mathcal{O}\left(1-\left(\frac{1} {d_{\mathcal{G}}}\right)^{C}\right).$ $$

Note that when $C\geq d_{\mathcal{G}}$, $\left(\frac{1}{d_{\mathcal{G}}}\right)^{C}=0$, i.e. under these conditions the networked case becomes equivalent to the centralised case such that $ub_{net}=ub_{cent}$. Therefore for $C>d_{\mathcal{G}}$ there is no additional improvement over the bound for the centralised case under these theoretical conditions.

Proof sketch.
The difference in convergence rate between the different architectures depends on the different amounts of divergence between the population’s policies. In a static, connected network, max-consensus is reached when the number of communication rounds $C$ is equal to the diameter $d_{\mathcal{G}}$, giving 0 divergence as in the centralised case. The rate of decrease in divergence is approximately $\frac{1}{d_{\mathcal{G}}}$ for each of the $C$ communication rounds, giving the exponential relation involving $C$ and $d_{\mathcal{G}}$ seen in the theorem. Full proof in Appx. B.7.

###### Remark 4 .

Thm. 3 depends on the assumptions that the communication network is static and fixed, and has the same diameter $d_{\mathcal{G}}$ for all $k$. If we assume instead that the network is only repeatedly jointly connected, we can replace $d_{\mathcal{G}}$ in the results in Thm. 3 with $d_{avg}\cdot\omega$, namely the average diameter of the union of each jointly connected collection of graphs multiplied by the average number of graphs in each jointly connected collection. As noted in Rem. 2, max-consensus is reached if $C$ is large enough that the number of jointly connected collections of graphs occurring within $C$ is equal to the largest diameter of the union of any collection, giving the centralised case; there is no added benefit to higher values of $C$ than this.

###### Remark 5 .

Thm. 3 assumes $\tau_{k}\rightarrow 0\;\forall k$. If we assume instead $\tau_{k}\in\mathbb{R}_{>0}$, then we have $ub_{net}$ $\rightarrow$ $ub_{ind}$ as $C\rightarrow 0$, and $ub_{net}\rightarrow$ $ub_{cent}$ as $C\rightarrow\infty$. This is because the spread of policies is now probabilistic rather than deterministic, and depends on the interplay of $\tau_{k}$ with how large are the differences in the received values of $\sigma^{j}_{k+1}$. Therefore consensus (and hence reduction in divergence between policies) is reached only asymptotically. This applies to both static, connected networks and to repeatedly jointly connected ones, assuming the latter becomes jointly connected infinitely often.

###### Theorem 1 (Networked learning with random adoption ) .

###### Theorem 2 (Networked learning with non-random adoption ) .

###### Theorem 3 (Relation between communication network structure and order of difference between the frameworks’ bounds) .

###### Remark 4 .

###### Remark 5 .

### 3.4 Practical running of algorithms

#### 3.4.1 Generation of σ k + 1 i subscript superscript 𝜎 𝑖 𝑘 1 \sigma^{i}_{k+1} italic_σ start_POSTSUPERSCRIPT italic_i end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_k + 1 end_POSTSUBSCRIPT

The theoretical analysis in Sec. 3.3 requires algorithmic hyperparameters that render convergence impractically slow in all of the centralised, independent and networked cases (see Rem. 8, Appx. B.9). For practical convergence of the algorithms, we seek to drastically increase $\{\beta_{m}\}$ and reduce $M_{td}$ and $M_{pg}$, though this will naturally break the theoretical guarantees and give a poorer estimation of the Q-function $\hat{Q}^{i}_{M_{pg}}$, and hence a greater variance in the quality of the updated policies $\pi^{i}_{k+1}$. However, in such cases we found empirically that an appropriate method for generating $\sigma^{i}_{k+1}$ dependent on $\pi^{i}_{k+1}$ allows our networked algorithm to significantly outperform the independent setting, and sometimes even the centralised setting, by advantageously biasing the spread of particular policies. This is an alternative to generating $\sigma^{i}_{k+1}$ arbitrarily or independently of $\pi^{i}_{k+1}$ as required in the theoretical settings in Sec. 3.3.

We do so by setting $\sigma^{i}_{k+1}$ to a finite approximation $\widehat{\Theta^{i}_{h,k+1}}(\bm{\pi}_{k+1},\upsilon_{0})$ of $\Theta^{i}_{h,k+1}(\bm{\pi}_{k+1},\upsilon_{0})$ where $\bm{\pi}_{k+1}$ := ($\pi^{1}_{k+1},\dots,\pi^{N}_{k+1}$), by tracking the discounted return for $E$ evaluation steps. This is given by

$$ $\widehat{\Theta^{i}_{h,k+1}}(\bm{\pi}_{k+1},\upsilon_{0})=\left[\sum^{E}_{e=0} \gamma^{e}(R(s^{i}_{t},a^{i}_{t},\hat{\mu}_{t})\right.+h(\pi^{i}(s^{i}_{t}))) \left|\begin{subarray}{c}t=t+e\\ a^{j}_{t}\sim\pi^{j}_{k+1}(s^{j}_{t})\\ s^{j}_{t+1}\sim P(\cdot|s^{j}_{t},a^{j}_{t},\hat{\mu}_{t})\end{subarray}, \forall j\in\{1,\dots,N\}\right].$ $$

Generating $\sigma^{i}_{k+1}$ in this way means that the policies that are more likely to be adopted and spread through the communication network are those which are estimated to receive a higher return in reality, despite being generated from poorly estimated Q-functions. This explains why our networked method can in practice outperform even the centralised case, where the updated policy of the agent with arbitrary index $i=1$ gets pushed to all other agents regardless of its quality.
Naturally the quality of the finite approximation depends on the number of evaluation steps $E$, but we found empirically that $E$ can be much smaller than $M_{pg}$ and still give significant convergence benefits.

#### 3.4.2 Algorithm acceleration by use of experience-replay buffer

Even with networked communication, the empirical convergence of our original algorithm is too slow for practical demonstration, as also in the centralised and independent cases. We therefore offer a further technical contribution allowing the first practical demonstrations of all three architectures for learning from a single continued system run.

The modifications made to our Alg. 1 are shown in blue in Alg. 2, Appx. C. Instead of using a transition $\zeta^{i}_{t-2}$ to compute the TD update within each $M_{pg}$ iteration and then discarding the transition, we store the transition in a buffer (Line 11) until after the $M_{pg}$ loops. Replay buffers are a common (MA)RL tool used especially with deep learning, precisely to improve data efficiency and reduce autocorrelation (Lin, ; Fedus et al., ; Xu et al., ). When learning does take place in our modified algorithm (Lines 13-18), it involves cycling through the buffer for $L$ iterations - randomly shuffling the buffer between each - and thus conducting the TD update on each stored transition $L$ times. This allows us to reduce the number of $M_{pg}$ loops, as well as not requiring as small a learning rate $\{\beta_{m}\}$, allowing much faster learning in practice. Moreover, by shuffling the buffer before each cycle we reduce bias resulting from the dependency of samples along the single path, which may justify being able to achieve adequate stable learning even when reducing the number of $M_{td}$ waiting steps within each $M_{pg}$ loop. Naturally the experience replay buffer means that theoretical guarantees given in Sec. 3.3 no longer apply, but we trade this off for practical convergence times. See Appx. C for further discussion.

Figure: Figure 1: ‘Target agreement’ game. Even with only a single round of communication, our networked case outperforms the independent case in terms of exploitability, and significantly outperforms in terms of return. The fact that the lowest broadcast radius (0.2) ends with similar exploitability to the independent case yet much higher return shows that our networked algorithm can help agents to find ‘preferable’ equilibria.
Refer to caption: extracted/5916013/agree_10runs.png

## 4 Experiments

Our technical contribution of the experience replay buffer to MFG algorithms for learning from continuous system runs allows us also to contribute the first empirical demonstrations of these algorithms, not just in the networked case but also in the centralised and independent cases. The latter two serve as baselines to demonstrate the advantages of the networked architecture.We follow prior works on stationary MFGs in the types of game used in our demonstrations (Zaman et al., ; Lauriere et al., ; Algumaei et al., ; Lauriere, ; Cui et al., ). We focus on grid-world environments where agents can move in one of the four cardinal directions or remain in place. We present results from two tasks defined by the reward functions of the agents; see Appx. E.1 for full technical description of our task settings.

Figure: Figure 2: ‘Cluster’ game, testing robustness to 50% probability of policy update failure. The communication network allows agents that have successfully updated their policies to spread this information to those that have not, providing redundancy. Independent learners cannot do this and hardly appear to learn at all; likewise the centralised architecture is susceptible to its single point of failure. Thus our networked architecture significantly outperforms both the centralised and independent cases.
Refer to caption: extracted/5916013/clusterfail_10runs.png

Cluster. Agents are rewarded for gathering together. The agents are given no indication where they should cluster, agreeing this themselves over time.

Target agreement. The agents are rewarded for visiting any of a given number of targets, but their reward is proportional to the number of other agents co-located at that target. The agents must therefore coordinate on which single target they will all meet at to maximise their individual rewards.

As well as the standard scenario for these tasks, we conduct robustness tests in two settings, reflecting those elaborated in Appx. D. The first illustrates robustness to learning failures: at every iteration $k$ each learner (whether centralised or decentralised) fails to update its policy (i.e. Line 12 of Alg. 1 is not executed such that $\pi^{i}_{k+1}=\pi^{i}_{k}$) with a 50% probability. The second test illustrates robustness to increases in population size. Instead of having 250 agents throughout, the population begins with 50 agents learning normally, and a further 200 agents are added to the population at the marked point.

Experiments are evaluated via three metrics (see Appx. E.2 for a full discussion): an approximation of the exploitability of the joint policy $\bm{\pi}_{k}$; the average discounted return of the agents’ policies $\pi_{k}^{i}$; and the population’s policy divergence. Hyperparameters are discussed in Appx. E.3.

### 4.1 Discussion

We give here three example figures illustrating the benefits of the networked architecture; in each the decimals refer to each agent’s broadcast radius as a fraction of the maximum possible distance in the grid (i.e. the diagonal). See figure captions for details, and Appx. E.4 for further experiments and discussion. For limitations and future work, see Appx. G. As well as allowing convergence within a practical number of iterations, even with only a single communication round, the combination of the buffer and the networked architecture allows us to remove in our experiments a number of the assumptions required for the theoretical algorithms:

- •
We significantly reduce $M_{pg}$ while still converging within a reasonable $K$. With smaller values for $M_{pg}$ (the number of samples in the buffer) and $L$ (the number of loops through the buffer for updating the Q-function), and hence with worse estimation of the Q-function, the networked architecture outperforms the independent case to an even greater extent. This underlines its advantages in allowing faster convergence in practical settings.
- •
We can reduce the $M_{td}$ parameter (theoretically required for the learner to wait between collecting samples when learning from a single system run) to 1, effectively removing the innermost loop of the nested learning algorithm (see Line 7 of Alg. 1).
- •
We can reduce the scaling parameter $\lambda$ of the entropy regulariser to 0, i.e. we converge even without regularisation, allowing us to leave the NE unbiased, and also removing Assumption 3 (Appx. A). In general an unregularised MFG-NE is not unique (Yardim et al., ); the ability of the agents to coordinate on one of the multiple solutions in the centralised and networked cases may explain why they outperform the independent-learning case.
- •
For the PMA operator (Def. 8), we conduct the optimisation over the set $u\in\Delta_{\mathcal{A}}$ instead of $u\in\mathcal{U}_{L_{h}}$, i.e. we can choose from all possible probability distributions over actions instead of needing to identify the Lipschitz constants given in Assumption 1 (Appx. A).

## 5 Broader impact / ethics statement

As with many advances in machine learning, and those relating to multi-agent systems in particular, in the long term our research on large populations of coordinating agents could have negative social outcomes if pursued by malicious actors, including surveillance and military uses. However, our work is primarily foundational and far from deployments, and it also has a large range of potential beneficial applications (such as smart grids and disaster response). Moreover, better understanding the dynamics of large multi-agent systems (as we seek to do in this paper) can contribute to ensuring safety by reducing the risks of unintended failures or outcomes.

We hope to help mitigate potential harmful consequences of this research by fostering transparency through submitting our code in the Supplementary Material, which we commit to publishing online under license upon acceptance of the paper.

## 6 Reproducibility statement

The code files to run our experiments are uploaded in the Supplementary Material. We discuss the hyperparameters for our experiments in Table 1 in Appx. E.3. The technical assumptions for our theoretical results are given in Appx. A, and complete proofs are provided in Appx. B.

## Technical appendices

## Appendix A Further definitions and assumptions for theorems in Sec. 3.3

###### Assumption 1 (Lipschitz continuity of $P$ and $R$ , from Assumption 1, Yardim et al. ( 2023 ) ) .

There exist constants $K_{\mu},K_{s},K_{a},L_{\mu},L_{s},L_{a}\in\mathbb{R}_{\geq 0}$ such that $\forall s,s^{\prime}\in\mathcal{S},\forall a,a^{\prime}\in\mathcal{A},\forall
\mu,\mu^{\prime}\in\Delta_{\mathcal{S}}$,

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

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

###### Definition 9 (Population update operator, from Def. 3.1, Yardim et al. ( 2023 ) ) .

The single-step population update operator $\Gamma_{pop}:\Delta_{\mathcal{S}}\times\Pi\rightarrow\Delta_{\mathcal{S}}$ is defined as, $\forall s\in\mathcal{S}$:

$$ $\Gamma_{pop}(\mu,\pi)(s):=\sum_{s^{\prime}\in\mathcal{S}}\sum_{a^{\prime}\in \mathcal{A}}\mu(s^{\prime})\pi(a^{\prime}|s^{\prime})P(s|s^{\prime},a^{\prime} ,\mu).$ $$

Let us use the short hand notation $\Gamma^{n}_{pop}(\mu,\pi):=\underbrace{\Gamma_{pop}(\dots\Gamma_{pop}(\Gamma_{
pop}(\mu,\pi),\pi),\dots,\pi)}_{n\text{ times}}$.

We recall that $\Gamma_{pop}$ is known to be Lipschitz:

###### Lemma 1 (Lipschitz population updates, from Lem. 3.2, Yardim et al. ( 2023 ) ) .

$\Gamma_{pop}$ is Lipschitz with

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

where $L_{pop,\mu}$ := $\left(\frac{K_{s}}{2}+\frac{K_{a}}{2}+K_{\mu}\right)$, $\forall\pi\in\Pi,\mu\in\Delta_{\mathcal{S}}$.

For stationary MFGs the population distribution must be stable with respect to a policy, requiring that $\Gamma_{pop}(\cdot,\pi)$ is contractive $\forall\pi\in\Pi$:

###### Assumption 2 (Stable population, from Assumption 2, Yardim et al. ( 2023 ) ) .

Population updates are stable, i.e. $L_{pop,\mu}<1$.

###### Definition 10 (Stable population operator $\Gamma_{pop}^{\infty}$ , from Def. 3.3, Yardim et al. ( 2023 ) ) .

Given Assumption 2, the operator $\Gamma_{pop}^{\infty}:\Pi\rightarrow\Delta_{\mathcal{S}}$ maps a given policy to its unique stable population distribution such that $\Gamma_{pop}(\Gamma_{pop}^{\infty}(\pi),\pi)=\Gamma_{pop}^{\infty}(\pi)$, i.e. the unique fixed point of $\Gamma_{pop}(\cdot,\pi):\Delta_{\mathcal{S}}\rightarrow\Delta_{\mathcal{S}}.$

###### Definition 11 ( $Q_{h}$ and $q_{h}$ functions) .

We define, for any pair $(s,a)\in\mathcal{S}\times\mathcal{A}$:

$$ $Q_{h}(s,a|\pi,\mu):=\mathbb{E}\left[\sum^{\infty}_{t=0}\gamma^{t}(R(s_{t},a_{t },\mu)+h(\pi(s_{t})))\left|\begin{subarray}{c}s_{0}=s,\\ a_{0}=a\end{subarray},\begin{subarray}{c}s_{t+1}\sim P(\cdot|s_{t},a_{t},\mu), \\ a_{t+1}\sim\pi(\cdot|s_{t+1})\end{subarray},\forall t\geq 0\vphantom{\sum^{ \infty}_{t=0}\gamma^{t}(R(s_{t},a_{t},\mu)+}\right]\right.$ $$

and

$$ $q_{h}(s,a|\pi,\mu):=R(s,a,\mu)+\gamma\sum_{s^{\prime},a^{\prime}}P(s^{\prime}| s,a,\mu)\pi(a^{\prime}|s^{\prime})Q_{h}(s^{\prime},a^{\prime}|\pi,\mu).$ $$

###### Definition 12 ( $\Gamma_{q}$ operator) .

The operator $\Gamma_{q}:\Pi\times\Delta_{\mathcal{S}}\rightarrow\mathcal{Q}$ mapping population-policy pairs to Q-functions is defined as $\Gamma_{q}(\pi,\mu):=q_{h}(\cdot,\cdot|\pi,\mu)\in\mathcal{Q}$ $\forall\pi\in\Pi,\mu\in\Delta_{\mathcal{S}}$.

We also assume that the regulariser $h$ ensures that all actions at all states are explored with non-zero probability:

###### Assumption 3 (Persistence of excitation, from Assumption 3, Yardim et al. ( 2023 ) ) .

We assume there exists $p_{inf}>0$ such that:

- 1.
$\pi_{\mathrm{max}}(a|s)\geq p_{inf}$ $\forall s\in\mathcal{S},a\in\mathcal{A}$,
- 2.
For any $\pi\in\Pi$ and $q\in\mathcal{Q}$ that satisfy, $\forall(s,a)\in\mathcal{S}\times\mathcal{A}$, $\pi(a|s)\geq p_{inf}$ and $0\leq q(s,a)\leq Q_{\mathrm{max}}$, it holds that $\Gamma^{md}_{\eta}(q,\pi)(a|s)\geq p_{inf}$, $\forall(s,a)\in\mathcal{S}\times\mathcal{A}$.

###### Assumption 4 (Sufficient mixing, from Assumption 4, Yardim et al. ( 2023 ) ) .

For any $\pi\in\Pi$ satisfying $\pi(a|s)\geq p_{inf}>0$ $\forall s\in\mathcal{S},a\in\mathcal{A}$, and any initial states {$s^{i}_{0}$}${}_{i}\in\mathcal{S}^{N}$, there exist $T_{mix}>0,\delta_{mix}>0$ such that $\mathbb{P}(s^{j}_{T_{mix}}=s^{\prime}|${$s^{i}_{0}$}${}_{i})$ $\geq\delta_{mix}$, $\forall s^{\prime}\in\mathcal{S},j\in[N]$.

###### Definition 13 (Nested learning operator) .

For a learning rate $\eta>0$, $\Gamma_{\eta}:\Pi\rightarrow\Pi$ is defined as

$$ $\Gamma_{\eta}(\pi):=\Gamma_{\eta}^{md}(\Gamma_{q}(\pi,\Gamma_{pop}^{\infty}( \pi)),\pi).$ $$

###### Lemma 2 (Lipschitz continuity of $\Gamma_{\eta}$ , from Lem. 3.7, (Yardim et al., 2023 ) )) .

For any $\eta>0$, the operator $\Gamma_{\eta}:\Pi\rightarrow\Pi$ is Lipschitz with constant $L_{\Gamma_{\eta}}$ on ($\Pi,||\cdot||_{1}$).

###### Assumption 1 (Lipschitz continuity of P 𝑃 P italic_P and R 𝑅 R italic_R , from Assumption 1, Yardim et al. ( 2023 ) ) .

###### Definition 9 (Population update operator, from Def. 3.1, Yardim et al. ( 2023 ) ) .

###### Lemma 1 (Lipschitz population updates, from Lem. 3.2, Yardim et al. ( 2023 ) ) .

###### Assumption 2 (Stable population, from Assumption 2, Yardim et al. ( 2023 ) ) .

###### Definition 10 (Stable population operator Γ p ⁢ o ⁢ p ∞ superscript subscript Γ 𝑝 𝑜 𝑝 \Gamma_{pop}^{\infty} roman_Γ start_POSTSUBSCRIPT italic_p italic_o italic_p end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT , from Def. 3.3, Yardim et al. ( 2023 ) ) .

###### Definition 11 ( Q h subscript 𝑄 ℎ Q_{h} italic_Q start_POSTSUBSCRIPT italic_h end_POSTSUBSCRIPT and q h subscript 𝑞 ℎ q_{h} italic_q start_POSTSUBSCRIPT italic_h end_POSTSUBSCRIPT functions) .

###### Definition 12 ( Γ q subscript Γ 𝑞 \Gamma_{q} roman_Γ start_POSTSUBSCRIPT italic_q end_POSTSUBSCRIPT operator) .

###### Assumption 3 (Persistence of excitation, from Assumption 3, Yardim et al. ( 2023 ) ) .

###### Assumption 4 (Sufficient mixing, from Assumption 4, Yardim et al. ( 2023 ) ) .

###### Definition 13 (Nested learning operator) .

###### Lemma 2 (Lipschitz continuity of Γ η subscript Γ 𝜂 \Gamma_{\eta} roman_Γ start_POSTSUBSCRIPT italic_η end_POSTSUBSCRIPT , from Lem. 3.7, (Yardim et al., 2023 ) )) .

## Appendix B Full theorems and complete proofs

### B.1 Sample guarantees of independent-learning case

###### Lemma 3 (Independent learning, from Thm. 4.5, Yardim et al. ( 2023 ) ) .

Define $t_{0}:=\frac{16(1+\gamma)^{2}}{((1-\gamma)\delta_{mix}p_{inf})^{2}}$.
Assume that Assumptions 1, 2, 3 and 4 hold, that $\eta>0$ satisfies $L_{\Gamma_{\eta}}<1$, and that $\pi^{*}$ is the unique MFG-NE. The learning rates are $\beta_{m}=\frac{2}{(1-\gamma)(t_{0}+m-1)}$ $\forall m\geq 0$, and let $\varepsilon>0$ be arbitrary. There exists a problem-dependent constant $a\in[0,\infty)$ such that if $K=\frac{\log 8\varepsilon^{-1}}{\log L^{-1}_{\Gamma_{\eta}}}$, $M_{pg}>\mathcal{O}(\varepsilon^{-2-a})$ and $M_{td}>\mathcal{O}(log^{2}\varepsilon^{-1})$, then the random output {$\pi^{i}_{K}$}i of Alg. 1 when run with $C=0$ (such that there is no communication) satisfies for all agents $i=1,\dots,N$,

$$ $\mathbb{E}\left[||\pi^{i}_{K}-\pi^{*}||_{1}\right]\;\leq\;\varepsilon+\mathcal {O}\left(\frac{1}{\sqrt{N}}\right).$ $$

###### Lemma 3 (Independent learning, from Thm. 4.5, Yardim et al. ( 2023 ) ) .

### B.2 Full version of Thm. 1

###### Theorem 1 (Networked learning with random adoption) .

For $p_{inf}$ and $\delta_{mix}$ defined in Assumptions 3 and 4 respectively, define $t_{0}:=\frac{16(1+\gamma)^{2}}{((1-\gamma)\delta_{mix}p_{inf})^{2}}$.
Assume that Assumptions 1, 2, 3 and 4 hold, and that $\pi^{*}$ is the unique MFG-NE policy. For $L_{\Gamma_{\eta}}$ defined in Lem. 2, we assume $\eta>0$ satisfies $L_{\Gamma_{\eta}}<1$. The learning rates are $\beta_{m}=\frac{2}{(1-\gamma)(t_{0}+m-1)}$ $\forall m\geq 0$, and let $\varepsilon>0$ be arbitrary. Assume also that $C>0$, with $\tau_{k}\rightarrow\infty$. There exists a problem-dependent constant $a\in[0,\infty)$ such that if $K=\frac{\log 8\varepsilon^{-1}}{\log L^{-1}_{\Gamma_{\eta}}}$, $M_{pg}>\mathcal{O}(\varepsilon^{-2-a})$ and $M_{td}>\mathcal{O}(log^{2}\varepsilon^{-1})$, then the random output {$\pi^{i}_{K}$}i of Alg. 1 preserves the sample guarantees of the independent-learning case given in Lem. 3, i.e. the output satisfies, for all agents $i=1,\dots,N$,

$$ $\mathbb{E}\left[||\pi^{i}_{K}-\pi^{*}||_{1}\right]\;\leq\;\varepsilon+\mathcal {O}\left(\frac{1}{\sqrt{N}}\right).$ $$

(Proof in Appx. B.3.)

###### Theorem 1 (Networked learning with random adoption) .

### B.3 Proof of Thm. 1

###### Proof.

If $\tau_{k}\rightarrow\infty$, the softmax function that defines the probability of a received policy being adopted in Line 17 of Alg. 1 gives a uniform distribution. Policies are thus exchanged at random between communicating agents an arbitrary $C>0$ times, which does not affect the random output of the algorithm, such that the random output satisfies the same expectation as if $C=0$. ∎

###### Proof.

### B.4 Conditional TD learning from a single continuous run of the empirical distribution of N 𝑁 N italic_N agents

###### Lemma 4 (Conditional TD learning from a single continuous run of the empirical distribution of $N$ agents, from Thm. 4.2, Yardim et al. ( 2023 ) ) .

Define $t_{0}:=\frac{16(1+\gamma)^{2}}{((1-\gamma)\delta_{mix}p_{inf})^{2}}$. Assume Assumption 4 holds and let policies {$\pi^{i}$}i be given such that $\pi^{i}(a|s)\geq p_{inf}$ $\forall i$. Assume Lines 5-11 of Alg. 1 are run with policies {$\pi^{i}$}i, arbitrary initial agents states {$s^{i}_{0}$}i, learning rates $\beta_{m}=\frac{2}{(1-\gamma)(t_{0}+m-1)}$, $\forall m\geq 0$ and $M_{pg}>\mathcal{O}(\varepsilon^{-2})$, $M_{td}>\mathcal{O}(\log\varepsilon^{-1})$. If $\bar{\pi}\in\Pi$ is an arbitrary policy, $\Delta$ := $\sum_{i=1}^{N}||\pi^{i}-\bar{\pi}||_{1}$ and $Q^{*}$ := $Q_{h}(\cdot,\cdot|\bar{\pi},\mu_{\bar{\pi}})$, then the random output $\hat{Q}^{i}_{M_{pg}}$ of Lines 5-11 satisfies

$$ $\mathbb{E}\left[||\hat{Q}^{i}_{M_{pg}}-\;Q^{*}||_{\infty}\right]\leq \varepsilon+\mathcal{O}\left(\frac{1}{\sqrt{N}}+\frac{1}{N}\Delta+||\pi^{i}- \bar{\pi}||_{1}\right).$ $$

###### Lemma 4 (Conditional TD learning from a single continuous run of the empirical distribution of N 𝑁 N italic_N agents, from Thm. 4.2, Yardim et al. ( 2023 ) ) .

### B.5 Full version of Thm. 2

###### Theorem 2 (Networked learning with non-random adoption) .

Assume that Assumptions 1, 2, 3 and 4 hold, and that Alg. 1 is run with learning rates and constants as defined in Thm. 1, except now $\tau_{k}\in\mathbb{R}_{>0}$. Assume that $\sigma^{i}_{k+1}$ is generated uniquely for each $i$, in a manner independent of any metric related to $\pi^{i}_{k+1}$, e.g. $\sigma^{i}_{k+1}$ is random or related only to the index $i$ (so as not to bias the spread of any particular policy). Let the random output of this Algorithm be denoted as {$\pi^{i,net}_{K}$}i. Also consider an independent-learning version of the algorithm (i.e. with the same parameters except $C=0$) and denote its random output {$\pi^{j,ind}_{K}$}j; and a centralised version of the algorithm with the same parameters (see Rem. 3) and denote its random output as $\pi^{cent}_{K}$. Then for all agents $i=1,\dots,N$ and $j=1,\dots,N$, the random outputs {$\pi^{i,net}_{K}$}i, {$\pi^{j,ind}_{K}$}j and $\pi^{cent}_{K}$ satisfy

$$ $\mathbb{E}\left[||\pi^{cent}_{K}-\pi^{*}||_{1}\right]\;\leq\;\mathbb{E}\left[| |\pi^{i,net}_{K}-\pi^{*}||_{1}\right]\leq\;\mathbb{E}\left[||\pi^{j,ind}_{K}- \pi^{*}||_{1}\right]\;\leq\;\varepsilon+\mathcal{O}\left(\frac{1}{\sqrt{N}} \right).$ $$

(Proof in Appx. B.6.)

###### Theorem 2 (Networked learning with non-random adoption) .

### B.6 Proof of Thm. 2

###### Proof.

We build off the proof of our Lem. 3, given in Thm. D.9 of Yardim et al. (), where the sample guarantees of the independent case are worse than those of the centralised algorithm as a result of the divergence between the decentralised policies due to the stochasticity of the PMA updates. For an arbitrary policy $\bar{\pi}_{k}\in\Pi$, for all $k=0,1,\dots,K$ define the policy divergence as the random variable $\Delta_{k}$ := $\sum_{i=1}^{N}||\pi^{i}_{k}-\bar{\pi}_{k}||_{1}$. We can say that $\Delta_{k,cent}=0$ $\forall k$ is the divergence in the centralised case, while in the networked case the policy divergence is $\Delta_{k+1,c}$ after communication round $c\in 1,\dots,C$. The independent case is equivalent to the scenario when $C=0$, such that its policy divergence can be written $\Delta_{k+1,0}$.

For $\tau_{k}\in\mathbb{R}_{>0}$, the adoption probability Pr$\left(\mathrm{adopted}^{i}=\sigma^{j}_{k+1}\right)$ = $\frac{\exp{(\sigma^{j}_{k+1}}/\tau_{k})}{\sum^{[J^{i}_{t}]}_{x=1}\exp{(\sigma^
{x}_{k+1}}/\tau_{k})}$ (as in Line 17 of Alg. 1) is higher for some $j\in J^{i}_{t}$ than for others. This means that for $c>0$ for which there are communication links in the population, in expectation the number of unique policies in the population will decrease, as it will likely become that $\pi^{i}_{k+1}=\pi^{j}_{k+1}$ for some $i,j\in\{1,\dots,N\}$. As such, $\Delta_{k+1,cent}\leq\mathbb{E}\left[\Delta_{k+1,C}\right]\leq\mathbb{E}\left[
\Delta_{k+1,0}\right]$, i.e. the policy divergence in the independent-learning case is expected to be greater than or equal to that of the networked case.

The proof of Lem. 3 given in Thm. D.9 of Yardim et al. () ends with, for constants $\chi$ and $\xi$,

$$ $\mathbb{E}\left[||\pi^{i}_{K}-\pi^{*}||_{1}\right]\leq 2L_{\Gamma_{\eta}}^{K}+ \frac{\chi}{1-L_{\Gamma_{\eta}}}+\xi\sum^{K-1}_{k=1}L_{\Gamma_{\eta}}^{K-k-1} \mathbb{E}\left[\Delta_{k}\right],$ $$

where in our context the policy divergence in the independent case $\mathbb{E}\left[\Delta_{k+1}\right]$ is equivalent to $\mathbb{E}\left[\Delta_{k+1,C}\right]$ when $C=0$, i.e. $\mathbb{E}\left[\Delta_{k+1,0}\right]$.

Since $\Delta_{k+1,cent}\leq\mathbb{E}\left[\Delta_{k+1,C}\right]\leq\mathbb{E}\left[
\Delta_{k+1,0}\right]$, we obtain our result, i.e. for all agents $i=1,\dots,N$ and $j=1,\dots,N$, the random outputs {$\pi^{i,net}_{K}$}i, {$\pi^{j,ind}_{K}$}j and $\pi^{cent}_{K}$ satisfy

$$ $\mathbb{E}\left[||\pi^{cent}_{K}-\pi^{*}||_{1}\right]\;\leq\;\mathbb{E}\left[| |\pi^{i,net}_{K}-\pi^{*}||_{1}\right]\leq\;\mathbb{E}\left[||\pi^{j,ind}_{K}- \pi^{*}||_{1}\right]\;\leq\;\varepsilon+\mathcal{O}\left(\frac{1}{\sqrt{N}} \right).$ $$

∎

###### Remark 6 .

It may help to see that our result is a consequence of the following. Denote $\hat{Q}^{i,net}_{M_{pg}}$, $\hat{Q}^{i,ind}_{M_{pg}}$ and $\hat{Q}^{cent}_{M_{pg}}$ as the random outputs of Lines 5-11 of Alg. 1 in the networked, independent and centralised cases respectively. In Lem. 4, we can see that policy divergence gives bias terms in the estimation of the Q-value. Therefore, given $\Delta_{k+1,cent}\leq\mathbb{E}\left[\Delta_{k+1,C}\right]\leq\mathbb{E}\left[
\Delta_{k+1,0}\right]$, we can also say

$$ $\mathbb{E}\left[||\hat{Q}^{cent}_{M_{pg}}-Q^{*}||_{\infty}\right]\;\leq\; \mathbb{E}\left[||\hat{Q}^{i,net}_{M_{pg}}-Q^{*}||_{\infty}\right]\\ \leq\;\mathbb{E}\left[||\hat{Q}^{i,ind}_{M_{pg}}-Q^{*}||_{\infty}\right].$ $$

In other words, the networked case will require the same or fewer outer iterations $K$ to reduce the variance caused by this bias than the independent case requires (where the bias is non-vanishing), and the same or more iterations than the centralised case requires.

###### Proof.

###### Remark 6 .

### B.7 Proof of Thm. 3

###### Proof.

From the proof of Thm. 2 in Appx. B.6 we have:

$$ $\mathbb{E}\left[||\pi^{i,ind}_{K}-\pi^{*}||_{1}\right]\leq ub_{ind}=2L_{\Gamma _{\eta}}^{K}+\frac{\chi}{1-L_{\Gamma_{\eta}}}+\xi\sum^{K-1}_{k=1}L_{\Gamma_{ \eta}}^{K-k-1}\mathbb{E}\left[\Delta_{k,0}\right],$ $$

$$ $\mathbb{E}\left[||\pi^{i,net}_{K}-\pi^{*}||_{1}\right]\leq ub_{net}=2L_{\Gamma _{\eta}}^{K}+\frac{\chi}{1-L_{\Gamma_{\eta}}}+\xi\sum^{K-1}_{k=1}L_{\Gamma_{ \eta}}^{K-k-1}\mathbb{E}\left[\Delta_{k,C}\right],$ $$

$$ $\;\;\;\;\;\mathbb{E}\left[||\pi^{cent}_{K}-\pi^{*}||_{1}\right]\leq ub_{cent}= 2L_{\Gamma_{\eta}}^{K}+\frac{\chi}{1-L_{\Gamma_{\eta}}}+\xi\sum^{K-1}_{k=1}L_{ \Gamma_{\eta}}^{K-k-1}\mathbb{E}\left[\Delta_{k,cent}\right].$ $$

With a static, connected network and $\tau_{k}\rightarrow 0\;\forall k$, max-consensus is always reached after $C=d_{\mathcal{G}}$ communication rounds, such that $\Delta_{k,cent}=\Delta_{k,d_{\mathcal{G}}}=0$. There is a decrease in the divergence by a factor of approximately $\frac{1}{d_{\mathcal{G}}}$ with each communication round up to $C=d_{\mathcal{G}}$, such that:

$$ $\mathbb{E}\left[\Delta_{k,c+1}\right]\approx\mathbb{E}\left[\Delta_{k,c}\right ]\times\frac{1}{d_{\mathcal{G}}}\text{, \;giving}$ $$

$$ $\mathbb{E}\left[\Delta_{k,C}\right]\approx\mathbb{E}\left[\Delta_{k,0}\right] \times\left(\frac{1}{d_{\mathcal{G}}}\right)^{C}.$ $$

We can therefore also say:

$$ $ub_{ind}=2L_{\Gamma_{\eta}}^{K}+\frac{\chi}{1-L_{\Gamma_{\eta}}}+\xi\sum^{K-1} _{k=1}L_{\Gamma_{\eta}}^{K-k-1}\mathbb{E}\left[\Delta_{k,0}\right],$ $$

$$ $ub_{net}\approx 2L_{\Gamma_{\eta}}^{K}+\frac{\chi}{1-L_{\Gamma_{\eta}}}+\xi \sum^{K-1}_{k=1}L_{\Gamma_{\eta}}^{K-k-1}\mathbb{E}\left[\Delta_{k,0}\right] \times\left(\frac{1}{d_{\mathcal{G}}}\right)^{C},$ $$

$$ $\;\;\;\;\;ub_{cent}=2L_{\Gamma_{\eta}}^{K}+\frac{\chi}{1-L_{\Gamma_{\eta}}}.$ $$

We therefore firstly have

$$ $ub_{ind}-ub_{net}\approx\xi\sum^{K-1}_{k=1}L_{\Gamma_{\eta}}^{K-k-1}\mathbb{E} \left[\Delta_{k,0}\right]-\xi\sum^{K-1}_{k=1}L_{\Gamma_{\eta}}^{K-k-1}\mathbb{ E}\left[\Delta_{k,0}\right]\times\left(\frac{1}{d_{\mathcal{G}}}\right)^{C},$ $$

which simplifies to

$$ $ub_{ind}-ub_{net}\approx\xi\sum^{K-1}_{k=1}L_{\Gamma_{\eta}}^{K-k-1}\mathbb{E} \left[\Delta_{k,0}\right]\times\left(1-\left(\frac{1}{d_{\mathcal{G}}}\right)^ {C}\right),$ $$

giving us one of the results, namely

$$ $ub_{net}\approx ub_{ind}-\mathcal{O}\left(1-\left(\frac{1}{d_{\mathcal{G}}} \right)^{C}\right).$ $$

Secondly, we have

$$ $ub_{net}\approx ub_{cent}+\xi\sum^{K-1}_{k=1}L_{\Gamma_{\eta}}^{K-k-1}\mathbb{ E}\left[\Delta_{k,0}\right]\times\left(\frac{1}{d_{\mathcal{G}}}\right)^{C},$ $$

giving us the second result

$$ $ub_{net}\approx ub_{cent}+\mathcal{O}\left(\left(\frac{1}{d_{\mathcal{G}}} \right)^{C}\right).$ $$

∎

###### Remark 7 .

If it is always $\sigma^{1}_{k+1}$ and $\pi^{1}_{k+1}$ that is adopted by the whole population (i.e. $i=1$), then this is exactly the same as the centralised case. If the $\sigma^{j}_{k+1}$ and $\pi^{j}_{k+1}$ that gets adopted has different $j$ for each $k$ then this is akin to a version of the centralised setting where the index of the central learning agent may differ for each $k$.

###### Proof.

###### Remark 7 .

### B.8 Policy-update stability guarantee

###### Theorem 4 (Policy-update stability guarantee) .

Let Alg. 1 run as per Thm. 1 or Thm. 2, and say that $\varepsilon_{k}$ is the error term at iteration $k=\frac{\log 8\varepsilon_{k}^{-1}}{\log L^{-1}_{\Gamma_{\eta}}}$. For all agents $i$, the maximum possible distance between $\pi^{i,net}_{k}$ and $\pi^{i,net}_{k+1}$ is given by $\mathbb{E}\left[||\pi^{i,net}_{k}-\pi^{i,net}_{k+1}||_{1}\right]\leq
\varepsilon_{k}+\varepsilon_{k+1}+\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$. This bound provides policy-update stability guarantees during the learning process; moreover the bound shrinks with each successive $k$ since $\varepsilon_{k}$ decreases with $k$. Equivalent analysis can also be conducted for both the centralised and independent cases.

###### Proof.

Thms. 1 and 2 bound the difference between each agent’s current policy $\pi^{i}_{k}$ and the unique equilibrium policy $\pi^{*}$, with the difference depending on the bias term $\varepsilon_{k}$ that relates to the iteration $k$ as indicated. Policies $\pi^{i}_{k}$ and $\pi^{i}_{k+1}$ fall within balls centred on $\pi^{*}$ with radii of $\varepsilon_{k}+\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$ and $\varepsilon_{k+1}+\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$ respectively. This means that the maximum possible distance between $\pi^{i}_{k}$ and $\pi^{i}_{k+1}$ is the sum of these radii, i.e. $\mathbb{E}\left[||\pi^{i}_{k}-\pi^{i}_{k+1}||_{1}\right]\leq\varepsilon_{k}+
\varepsilon_{k+1}+\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$, giving the result.∎

###### Theorem 4 (Policy-update stability guarantee) .

###### Proof.

### B.9 Remark on theoretical hyperparameters when used in practical settings

###### Remark 8 .

The theoretical analysis in Sec. 3.3 and Appx. B requires algorithmic hyperparameters (Thms. 1 and 2) that render convergence impractically slow in all of the centralised, independent and networked cases. (Indeed Yardim et al. () do not provide empirical demonstrations of their algorithms for the centralised and independent cases.) In particular, the values of $\delta_{mix}$ and $p_{inf}$ give rise to very large $t_{0}$, causing very small learning rates $\{\beta_{m}\}_{m\in\{0,\dots,M_{pg}-1\}}$, and necessitating very large values for $M_{td}$ and $M_{pg}$.

###### Remark 8 .

## Appendix C Algorithm acceleration by use of experience-replay buffer (further details)

The intuition behind the better learning efficiency resulting from our experience replay buffer in Alg. 2 is as follows. The value of a state-action pair $p$ is dependent on the values of subsequent states reached, but the value of $p$ is only updated when the TD update is conducted on $p$, rather than every time a subsequent pair is updated. By learning from each stored transition multiple times, we not only make repeated use of the reward and transition information in each costly experience, but also repeatedly update each state-action pair in light of its likewise updated subsequent states.

We leave $\beta_{m}$ fixed across all iterations, as we found empirically that this yields sufficient learning. We have not experimented with decreasing $\beta$ as $l$ increases, though this may benefit learning.

The transitions in the buffer are discarded after the replay cycles and a new buffer is initialised for the next iteration $k$, as in Line 6. As such the space complexity of the buffer only grows linearly with the number of $M_{pg}$ iterations within each outer loop $k$, rather than with the number of $K$ loops.

Figure: Algorithm 2 Networked learning with experience replay

## Appendix D Extended discussion on robustness of communication networks in MFGs and related experimental settings

We consider two scenarios to which we desire real-world many-agent systems (e.g. robotic swarms or autonomous vehicle traffic) to be robust; these scenarios form the basis of our experiments on robustness (see Sec. 4 and Figs. 3, 3, 5 and 6). The networked setup affords population fault-tolerance and online scalability, which are motivating qualities of many-agent systems.

Firstly, we consider a scenario in which the learning/updating procedure of agents fails with a certain probability within each iteration, in which cases $\pi^{i}_{k+1}=\pi^{i}_{k}$ (see Figs. 3 and 5 for our experimental results and discussion of this scenario). In real-life decentralised settings, this might be particularly liable to occur since the updating process might only be synchronised between agents by internal clock ticks, such that some agents may not complete their update in the allotted time but will nevertheless be required to take the next step in the environment. Such failures slow the improvement of the population in the independent case, and in the centralised setting it means no improvement occurs at all in any iteration in which failure occurs, as there is a single point of failure. Networked communication instead provides redundancy in case of failures, with the updated policies of any agents that have managed to learn spreading through the population to those that have not. This feature thus ensures that improvement can continue for potentially the whole population even if a high number of agents do not manage to learn at a given iteration.

Secondly, we may want to arbitrarily increase the size of a population of agents that are already learning or operating in the environment (we can imagine extra fleets of autonomous cars or drones being deployed) - see Appx. F for comparison with other works considering this type of robustness (Eck et al., ; Gao et al., ; Dawood et al., ; Wu et al., ). A purely independent setting would require all the new agents to learn a policy individually given the existing distribution, and the process of their following and improving policies from scratch may itself disturb the NE that has already been achieved by the original population.
With a communication network, however, the policies that have been learnt so far can quickly be shared with the new agents in a decentralised way, hopefully before their unoptimised policies can destabilise the current NE. This would provide, for example, a way to bootstrap a large population from a smaller pre-trained group, if training were considered expensive in a given setting. See Figs. 3 and 6 for our experimental results and discussion of this scenario.

## Appendix E Experiments

Figure: Figure 4: ‘Cluster’ game. Even with only a single communication round, our networked architecture significantly outperforms the independent case, which hardly appears to be learning at all. All broadcast radii except the smallest (0.2) appear to match and at times even outperform the centralised case.
Refer to caption: extracted/5916013/cluster_10runs.png

Figure: Figure 5: ‘Target agreement’ game, testing robustness to 50% probability of policy update failure. All the networked cases significantly outperform the independent case and also learn much faster than the centralised case for long periods. The communication network allows agents that have successfully updated their policies to spread this information to those that have not, providing redundancy. Independent learners cannot do this so have even slower convergence than normal; likewise the centralised architecture is susceptible to its single point of failure, hence learning can be slower than in the networked case.
Refer to caption: extracted/5916013/agreefail_10runs.png

Figure: Figure 6: ‘Cluster’ game, testing robustness to a five-times increase in population. While the independent algorithm appears to enjoy similar exploitability to the other cases (see Rem. 9), we can see from its average return that it is not in fact learning at all; while the return rises after the increase in population size this is only because there are now more agents with which to be co-located, rather than because learning has progressed. Since here, unlike in the ‘target agreement’ game in Fig. 3, independent agents have hardly improved their return in the first place, we do not see the adverse effect that the addition of agents to the population has on the progress of learning. All networked cases perform similarly to or significantly outperform the centralised case, and all significantly outperform the independent case in terms of return. The communication network allows the learnt policies to quickly spread to the newly arrived agents, such that the progression of learning is minimally disturbed, without needing to rely on the assumption of a centralised learner. The fact that, in all cases, the return prior to the population increase is lower than in Fig. 4, is reflective of the fact that the error in the solution reduces as $N$ tends to infinity.
Refer to caption: extracted/5916013/clusteradd_10runs.png

Figure: Figure 7: ‘Cluster’ game on the larger 16x16 grid. While the independent-learning case has similar exploitability to the other settings, we can see that it is not actually learning to increase its return at all, making this an undesirable equilibrium. (I.e. agents are moving about randomly so there is little a deviating agent can do to increase its reward, hence exploitability is low even though the agents are not in fact clustered - see Rem. 9.) All the networked settings perform similarly to the centralised case and significantly outperform the return of the independent agents.
Refer to caption: extracted/5916013/cluster16_10runs.png

Figure: Figure 8: ‘Target agreement’ game on the larger 16x16 grid. There is greater differentiation in this setting than in the 8x8 grid (Fig. 1) between the different broadcast radii in the networked cases, as is to be expected in a less densely populated environment. The two largest broadcast radii (1.0 and 0.8), which have the most connected networks, significantly outperform the independent case in terms of both exploitability and return. However, the other broadcast radii perform similarly to the independent case.
Refer to caption: extracted/5916013/agree16_10runs.png

Figure: Figure 9: ‘Cluster’ game with $\tau_{k}$ fixed as 100 for all $k$; compare this to Fig. 4 where $\tau_{k}$ is annealed. Without the annealing scheme, the networked architecture appears to perform similarly to the independent case in terms of exploitability, but several broadcast radii outperform the independent case in terms of return, demonstrating that our networked algorithm can still help agents find ‘preferable’ equilibria. However, whereas with annealing the networked architecture converges similarly to the centralised case, here it performs less well.
Refer to caption: extracted/5916013/clusterstatic_10runs.png

Figure: Figure 10: ‘Target agreement’ game with $\tau_{k}$ fixed as 100 for all $k$. Without our annealing scheme for the softmax temperature, the networked architecture does not outperform the independent case. Compare this to Fig. 1 which shows the benefit of annealing $\tau_{k}$.
Refer to caption: extracted/5916013/agreestatic_10runs.png

Experiments were conducted on a MacBook Pro, Apple M1 Max chip, 32 GB, 10 cores. We use scipy.optimize.minimize (employing Sequential Least Squares Programming) to conduct the optimisation step in Def. 8, and the JAX framework to accelerate and vectorise some elements of our code.

For reproducibility, the code to run our experiments is provided with our Supplementary Material, and will be made publicly available upon publication.

### E.1 Games

We conduct numerical tests with two games (defined by the agents’ objectives), chosen for being particularly amenable to intuitive and visualisable understanding of whether the agents are learning behaviours that are appropriate and explainable for the respective objective functions. In all cases, rewards are normalised in [0,1] after they are computed.

##### Cluster.

This is the inverse of the ‘exploration’ game in (Lauriere et al., ), where in our case agents are encouraged to gather together by the reward function $R(s^{i}_{t},a^{i}_{t},\hat{\mu}_{t})=$ log$(\hat{\mu}_{t}(s^{i}_{t}))$. That is, agent $i$ receives a reward that is logarithmically proportional to the fraction of the population that is co-located with it at time $t$. We give the population no indication where they should cluster, agreeing this themselves over time.

##### Agree on a single target.

Unlike in the above ‘cluster’ game, the agents are given options of locations at which to gather, and they must reach consensus among themselves. If the agents are co-located with one of a number of specified targets $\phi\in\Phi$ (in our experiments we place one target in each of the four corners of the grid), and other agents are also at that target, they get a reward proportional to the fraction of the population found there; otherwise they receive a penalty of -1. In other words, the agents must coordinate on which of a number of mutually beneficial points will be their single gathering place. The reward function is given by $R(s^{i}_{t},a^{i}_{t},\hat{\mu}_{t})=r_{targ}(r_{collab}(\hat{\mu}_{t}(s^{i}_{
t})))$, where

$$ $r_{targ}(x)=\begin{cases}x\quad&\text{if}\,\exists\phi\in\Phi\text{ s.t. dist} (s^{i}_{t},\phi)=0\\ -1\quad&\text{otherwise,}\\ \end{cases}$ $$

$$ $r_{collab}(x)=\begin{cases}x\quad&\text{if}\,\hat{\mu}_{t}(s^{i}_{t})>1/N\\ -1\quad&\text{otherwise.}\\ \end{cases}$ $$

### E.2 Experimental metrics

To give as informative results as possible about both performance and proximity to the NE, we provide several metrics for each experiment. All metrics are plotted with 2-sigma error bars (2 $\times$ standard deviation), computed over the 10 trials (each with a random seed) of the system evolution in each setting. This is computed based on a call to numpy.std for each metric over each run.

#### E.2.1 Exploitability

Works on MFGs frequently use the exploitability metric to evaluate how close a given policy $\pi$ is to a NE policy $\pi^{*}$ (Lauriere et al., ; Perrin et al., ; Laurière et al., ; Algumaei et al., ; Pérolat et al., ). The metric quantifies how much an agent can benefit by deviating from the policy pursued by the rest of the population, by measuring the difference between the return given by a policy that maximises the expected discounted regularised (via $h$) reward $V_{h}$ for a given population distribution, and the return given by the policy that gives rise to this distribution. If $\pi$ has a large exploitability then an agent can significantly improve its return by deviating from $\pi$, meaning that $\pi$ is far from $\pi^{*}$, whereas an exploitability of 0 implies that $\pi=\pi^{*}$. Denote by $\mu^{\pi}$ the distribution generated when $\pi$ is the policy followed by all of the population aside from the deviating agent; then the exploitability of policy $\pi$ is defined as:

$$ $\mathcal{E}(\pi)=\max_{\pi^{\prime}}V_{h}(\pi^{\prime},\mu^{\pi})-V_{h}(\pi, \mu^{\pi}).$ $$

Since we do not have access to the exact best response policy $\arg\max_{\pi^{\prime}}V_{h}(\pi^{\prime},\mu^{\pi})$, we instead approximate the exploitability metric, similarly to (Perrin et al., ), as follows. We freeze the policy of all agents apart from a deviating agent, for which we store its current policy and then conduct 40 $k$ loops of policy improvement (we found that 40 iterations was enough to converge to a policy that maximised $V_{h}$ for the given population distribution). To approximate the expectations, we take the best return of the deviating agent across the 40 $k$ loops, as well as the mean of all the other agents’ returns across these same loops. We then revert the agent back to its stored policy, before learning continues for all agents. As such, the quality of our approximation is limited by the number of policy improvement rounds, which must be restricted for the sake of running speed of the experiments. Due to the expensive computations required for this metric, we evaluate it on alternate $k$ iterations.

Since prior works conducting empirical testing have generally focused on the centralised setting, evaluations have not had to consider the exploitability metric when not all agents are following a single policy $\pi_{k}$, as may occur in the independent or networked settings. The method described above for approximating exploitability involves calculating the mean return of all non-deviating agents’ policies. While this is $\pi_{k}$ in the centralised case, if the non-deviating agents do not share a single policy, then this method is in fact approximating the exploitability of their joint policy $\bm{\pi}^{-d}_{k}$, where $d$ is the deviating agent.

#### E.2.2 Average discounted return

We record the average discounted return of the agents’ policies $\pi_{k}^{i}$ during the $M_{pg}$ steps - this allows us to observe that settings that converge to similar exploitability values may not have similar average agent returns, suggesting that some algorithms are better than others at finding not just NE, but preferable NE. See for example Fig. 10, where the networked agents converge to similar exploitability as the independent agents, but receive higher average reward.

#### E.2.3 Policy divergence

We record the population’s average policy divergence $\frac{1}{N}\Delta_{k}$ := $\frac{1}{N}\sum_{i=1}^{N}||\pi_{k}^{i}-{\pi_{k}^{1}}||_{1}$ for the arbitrary policy $\bar{\pi}={\pi^{1}}$. This allows us to demonstrate that populations approaching the NE (i.e. with joint exploitability approaching zero) do not necessarily actually share a single policy $\pi^{*}$ as suggested by the theoretical sample guarantees in Sec. 3.3. Our experimental plots show that this is particularly often the case in the independent setting. The greater divergence in the independent case also indicates why convergence is slower here (see Rem. 6).

### E.3 Hyperparameters

See Table 1 for our hyperparameter choices. In general, we seek to show that our networked algorithm is robust to ‘poor’ choices of hyperparameters e.g. low numbers of iterations, as may be required when aiming for practical convergence times in complex real-world problems. By contrast, the convergence speed of the independent-learning algorithm (and sometimes also the centralised algorithm) suffers much more significantly without idealised hyperparameter choices. As such, our experimental demonstrations in the plots generally involve hyperparameter choices at the low end of the values we tested during our research.

We can group our hyperparameters into those controlling the size of the experiment, those controlling the number of iterations of each loop in the algorithm and those affecting the learning/policy updates or policy adoption ($\beta,\eta,\lambda,\tau,\gamma$).

Hyper-parameter Value Comment
\tablehead
Hyper-parameter Value Comment

Continued on next page
\tablelasttail

**Table 1: Hyperparameters**
| Hyper-param. | Value | Comment |
| --- | --- | --- |
| Gridsize | 8x8 / 16x16 | Most experiments are run on the smaller grid, while Figs. 7 and 8 showcase learning in a larger state space. |
| Trials | 10 | We run 10 trials with different random seeds for each experiment. We plot the mean and 2-sigma error bars for each metric across the trials. |
| Pop. | 250 | We tested $N$ in {25,50,100,200,250,500}, with the networked architecture generally performing equally well with all population sizes $\geq$ 50. We chose 250 for our demonstrations, to show that our algorithm can handle large populations, indeed often larger than those demonstrated in other mean-field works, especially for grid-world environments (Yongacoglu et al., ; Cui & Koeppl, ; Cui et al., ; Guo et al., ; Subramanian & Mahajan, ; Yang et al., ; Ganapathi Subramanian et al., ; ; Subramanian et al., ), while also being feasible to simulate wrt. time and computation constraints.<br>In experiments testing robustness to population increase, the population instead begins at 50 agents and has 200 added at the marked point. |
| $K$ | 200 / 400 | $K$ is chosen to be large enough to see exploitability reducing, and converging where possible. |
| $M_{pg}$ | 500 / 1000 | We wish to illustrate the benefits of our networked architecture and replay buffer in reducing the number of loops required for convergence, i.e. we wish to select a low value that still permits learning. We tested $M_{pg}$ in {300,500, 600,800,1000,1200,1300,1400,1500,1800,2000,2500,3000}, and chose 500 for demonstrations on the 8x8 grids, and 1000 for the 16x16 grids. It may be possible to optimise these values further in combination with other hyperparameters. |
| $M_{td}$ | 1 | We tested $M_{td}$ in {1,2,10,100}, and found that we could still achieve convergence with $M_{td}=1$. This is much lower than the requirements of the theoretical algorithms, essentially allowing us to remove the innermost nested learning loop. |
| $C$ | 1 | We tested $C$ in {1,20,50,300}. We choose 1 to show the convergence benefits brought by even a single communication round, even in networks that may have limited connectivity; higher $C$ has even better performance. |
| $L$ | 100 | As with $M_{pg}$, we wish to select a low value that still permits learning. We tested $L$ in {50,100,200,300,400,500}. In combination with our other hyperparameters, we found $L\leq 50$ led to less good results, but it may be possible to optimise this hyperparameter further. |
| $E$ | 100 | We tested $E$ in {100,300,1000}, and choose the lowest value to show the benefit to convergence even from very few evaluation steps. It may be possible to reduce this value further and still achieve similar results. |
| $\gamma$ | 0.9 | Standard choice across RL literature. |
| $\beta$ | 0.1 | We tested $\beta$ in {0.01,0.1} and found 0.1 to be small enough for sufficient learning at an acceptable speed. Further optimising this hyperparameter (including by having it decay with increasing $l\in 0,\dots,L-1$, rather than leaving it fixed) may lead to better results. |
| $\eta$ | 0.01 | We tested $\eta$ in {0.001,0.01,0.1,1,10} and found that 0.01 gave stable learning that progressed sufficiently quickly. |
| $\lambda$ | 0 | We tested $\lambda$ in {0,0.0001,0.001,0.01,0.1,1}. Since we can reduce $\lambda$ to 0 with no detriment to empirical convergence, we do so in order not to bias the NE. |
| $\tau_{k}$ | cf. comment | For fixed $\tau_{k}$ $\forall k$, we tested {1,10,100,1000}. In our experiments for fixed $\tau_{k}$ the value is 100 (see Figs. 9 and 10); this yields learning, but does not perform as well as if we anneal $\tau_{k}$ as follows. We begin with $\tau_{0}=10000/(10**\lceil(K-1)/10\rceil$), and multiply $\tau_{k}$ by 10 whenever $k\bmod 10=1$ i.e. every 10 iterations. Further optimising the annealing process may lead to better results. |

### E.4 Additional experiments and discussion

In this section we showcase results with our standard hyperparameter choices continuing from those shown in Sec. 4.1 (Figs. 4, 5 and 6), and we also vary several hyperparameters to show their effects on convergence (Figs. 7 - 10).

###### Remark 9 .

Note that the reward structure of our games is such that exploitability sometimes increases from its initial value before it decreases down to 0. This is because agents are rewarded proportionally to how many other agents are co-located with them: when agents are evenly dispersed at the beginning of the run, it is difficult for even a deviating, best-responding agent to significantly increase its reward. However, once some agents start to aggregate, a best-responding agent can take advantage of this to substantially increase its reward (giving higher exploitability), before all the other agents catch up and aggregate at a single point, reducing the exploitability down to 0. Due to this arc, in some of our plots the independent case may have lower exploitability at certain points than the other architectures, but this is not necessarily a sign of good performance. In fact, we can see in some such cases that the independent case is not learning at all, with the independent agents’ average return not increasing and the exploitability staying level rather than ultimately decreasing (see, for example, Figs. 3, 4, 6 and 7).

In our additional experiments, where the results are discussed fully in each figure’s caption, the factors we vary to show the effects on convergence are as follows:

- •
Grid size. Figs. 7 and 8 show the result of learning on a grid of size 16x16 instead of 8x8 as in all other experiments. There is at times greater differentiation in this setting than in the 8x8 grid between the performances of the different broadcast radii of the networked architecture (as is to be expected in a less densely populated environment). The networked architecture continues to significantly outperform the independent case for most broadcast radii, and sometimes even the centralised case.
- •
Choice of softmax temperature. Figs. 9 and 10 illustrate the effect of fixed $\{\tau_{k}\}_{k\in\{0,\dots,K-1\}}=100$, where the networked architecture does not perform as well as if we use the stepped annealing scheme employed in all the other experiments and detailed in Table 1. The intuition behind the better performance achieved with the annealing scheme is as follows. If we begin with $\tau_{k}\rightarrow 0$ (such that the softmax approaches being a max function), we heavily favour the adoption of the highest rewarded policies to speed up progress in the early stages of learning. Subsequently we increase $\tau_{k}$ in steps, promoting greater randomness in adoption, so that as the agents come closer to equilibrium, poorer policy updates that nevertheless receive a high return (due to randomness) do not introduce too much instability to learning and prevent convergence.

###### Remark 9 .

## Appendix F Extended related work

Multi-agent reinforcement learning (MARL) (Zhang et al., ; Busoniu et al., ) is a generalisation of reinforcement learning (Sutton & Barto, ) that has recently seen empirical success in a variety of domains, underpinned by breakthroughs in deep learning, including robotics (Leottau et al., ; Lv et al., ; Orr & Dutta, ; Guan et al., ; Ali et al., ), smart autonomy and infrastructures (Shalev-Shwartz et al., ; Mannion et al., ), complex games (Samvelyan et al., ; Vinyals et al., ; Berner et al., ), economics (Rashedi et al., ; Shavandi & Khedmati, ), social science and cooperative AI (Leibo et al., ; Cao et al., ; Jaques et al., ; McKee et al., ). However, it has been computationally difficult to scale MARL algorithms beyond configurations with agents numbering in the low tens, as the joint state and action spaces grow exponentially with the number of agents (Xie et al., ; Lauriere et al., ; Perrin et al., ; Shavandi & Khedmati, ; Daskalakis et al., ; Vinyals et al., ; Mcaleer et al., ). Nevertheless, the value of reasoning about interactions among very large populations of agents has been recognised, and an informal distinction is sometimes drawn between multi- and many-agent systems (Wang et al., ; Zheng et al., ; Cui et al., ). The latter situation can be more useful (as in cases where better solutions arise from the presence of more agents (Orr & Dutta, ; Ornia et al., ; Shiri et al., ; Eck et al., )), more parallelisable (Andréen et al., ), more fault tolerant (Chang et al., ), or otherwise more reflective of certain real-world systems involving large numbers of decision makers (Eck et al., ; Rashedi et al., ; Shavandi & Khedmati, ; Meigs et al., ). Indeed, MFGs have been applied to a wide variety of real world problems, including financial markets (Trimborn et al., ); cryptocurrency mining (Li et al., ); autonomous vehicles (Huang et al., ); traffic signal control (Hu et al., ); resource management in fisheries (Yoshioka et al., ); crowdsensing (Yang et al., ); electric vehicle charging (Dey & Xu, ); communication networks (Wang et al., ; ); swarms (); data collection by UAVs (Emami et al., ); edge computing (Aggarwal et al., ; Shen et al., ; Miao et al., ); cloud resource management (Mao et al., ); smart grids, and other large-scale cyber-physical systems (Bauso & Tembine, ; Mishra et al., ; Benamor et al., ).

Our networked communication framework possesses all of the following desirable qualities for mean-field algorithms when applied to large, complex real-world many-agent systems: learning from the empirical distribution of $N$ agents without generation or manipulation of this distribution by the algorithm itself or by an external oracle; learning from a single continued system run that is not arbitrarily reset as in episodic learning (also referred to in other works as a single sample path/trajectory (Zaman et al., ; Yardim et al., )); model-free learning; decentralisation; fast practical convergence; and robustness to unexpected failures of decentralised learners or changes in the size of the population.

Conversely, as we emphasise in Sec. 1, the MFG framework was originally mainly theoretical (Lasry & Lions, ; Huang et al., ). The MFG-NE is traditionally found by solving a coupled system of dynamical equations: a forward evolution equation for the mean-field distribution, and a backwards equation for the representative agent’s optimal response to the mean-field distribution, as in Def. 5 (Yoshioka et al., ); crucially, these methods relied on the assumption of an infinite population (Laurière et al., ). Early work solved the coupled equations using numerical methods that did not scale well for more complex state and action spaces (Achdou & Capuzzo-Dolcetta, ; Carlini & Silva, ; Briceño-Arias et al., ; Achdou et al., ); or, even if they could handle higher-dimensional problems, the methods were based on known models of the environment’s dynamics (i.e. they were model-based) (Anahtarci et al., ; Guo et al., ; Carmona & Laurière, ; Cao et al., ; Germain et al., ; Fouque & Zhang, ; Huang et al., ; ), and/or computed a best-response to the mean-field distribution (Huang et al., ; Lauriere et al., ; Perrin et al., ; Laurière et al., ; Guo et al., ; Perrin et al., ; Elie et al., ; Algumaei et al., ). The latter approach is both computationally inefficient in non-trivial settings (Yardim et al., ; Laurière et al., ), and in many cases is not convergent (as in general it does not induce a contractive operator) (Lauriere et al., ; Cui & Koeppl, ). Subsequent work, including our own, has therefore moved towards model-free and/or policy-improvement scenarios (Mishra et al., ; Laurière et al., ; Guo et al., ; Subramanian & Mahajan, ; Angiuli et al., ; Mishra et al., ; Cacace, Simone et al., ; Perolat et al., ; Lee et al., ), possibly with learning taking place by observing N-agent empirical population distributions (Yardim et al., ; Hu & Zhang, ; Yongacoglu et al., ).

Most prior works, including algorithms designed to solve the MFG using an N-agent empirical distribution, have also assumed an oracle that can generate samples of the game dynamics (for any distribution) to be provided to the learning agent (Anahtarci et al., ; Guo et al., ; ; Anahtarci et al., ; Fu et al., ), or otherwise that the algorithm has direct control over the population distribution at each time step, such as in cases when the agents’ policies and distribution are updated on different timescales (Angiuli et al., ), with the fictitious play method being particularly popular (Xie et al., ; Zaman et al., ; Mao et al., ; Lauriere et al., ; Perrin et al., ; ; Mguni et al., ; Cui et al., ; Lauriere, ; Subramanian & Mahajan, ; Angiuli et al., ; Tembine et al., ; Cardaliaguet, Pierre & Hadikhanloo, Saeed, ; Geist et al., ; Frédéric Bonnans et al., ). In practice, many-agent problems may not admit such arbitrary generation or manipulation (for example, in the context of robotics or controlling vehicle traffic), and so a desirable quality of learning algorithms is that they update only the agents’ policies, rather than being able to arbitrarily reset their states. Learning may thus also need to leverage continuing, rather than episodic, tasks (Sutton & Barto, ). Yardim et al. (), Yongacoglu et al. () and our own work therefore present algorithms that seek the MFG-NE using only a single run of the empirical population. Almost all prior work relies on a centralised controller to conduct learning on behalf of all the agents (Xie et al., ; Anahtarci et al., ; Zaman et al., ; Laurière et al., ; Guo et al., ). More recent work, including our own, has explored MFG algorithms for decentralised learning with N agents (Yardim et al., ; Mguni et al., ; Yongacoglu et al., ; ; Grammatico et al., ; ; Parise et al., ; Grammatico et al., ).

Naturally, inter-agent communication is most applicable in settings where learning takes place along a continuing system run, rather than the distribution being manipulated by an oracle or arbitrarily reset for new episodes, since these imply a level of external control over the population that results in centralised learning. Equally, it is in situations of learning from finite numbers of real, deployed agents (rather than simulated settings) that we are most likely to be concerned with fault tolerance. As such, our work is most closely related to Yardim et al. () and Yongacoglu et al. (), which provide algorithms for centralised and independent learning with empirical distributions along continued system runs: we contribute a networked learning algorithm in this setting. Yongacoglu et al. () empirically demonstrates an independent learning algorithm when agents observe compressed information about the mean-field distribution as well as their local state, but they do not compare this to any other algorithms or baselines. Yardim et al. () compares algorithms for centralised and independent learning theoretically, but does not provide empirical demonstrations. In contrast, in addition to providing theoretical guarantees, we empirically demonstrate our networked learning algorithm, where agents observe only their local state, in comparison to both centralised and independent baselines, as well as concerning ourselves with the speed of practical convergence and robustness, unlike these works.

Improving the training speed and sample efficiency of (deep) (multi-agent) RL is gaining increasing attention (Yu et al., ; Wiggins et al., ; Wu et al., ; Patel et al., ), though our own work is one of the only on MFGs to be concerned with this. Huang & Lai () trains on a distribution of MFG configurations to speed up inference on unseen problems, but does not learn online in a decentralised manner as in our own work. Similarly, while some attention has been given to the robustness of multi-agent systems to varying numbers of agents, where it is sometimes referred to as ‘ad-hoc teaming’, ‘open-agent systems’, ‘scalability’ or ‘generalisation’ (Eck et al., ), it has more commonly been addressed in MARL (Gao et al., ; Dawood et al., ) than in MFGs (Wu et al., ). Wu et al. () presents an MFG approach that allows new agents to join the population during execution, but training itself takes place offline in a centralised, episodic manner. Our networked communication framework presented in the current work, on the other hand, allows decentralised agents to join the population during online learning and to have minimal impact on the learning process by adopting policies from existing members of the population through communication.

An existing area of work called ‘robust mean-field games’ studies the robustness of these games to uncertainty in the transition and reward functions (Bauso & Tembine, ; Bauso et al., ; ; Moon & Başar, ; Huang & Huang, ; Yang et al., ; Tirumalai & Baras, ; Aydın & Saldi, ), but does not consider fault-tolerance, despite this being one of the original motivations behind many-agent systems. On the other hand, we focus on robustness to failures and changes in the agent population itself.

We note a similarity between 1. our method for deciding which policies to propagate through the population (described in Sec. 3.4.1) and 2. the computation of evaluation/fitness functions within evolutionary algorithms to indicate which solutions are desirable to keep in the population for the next generation (Eiben & Smith, ). Moreover, the research avenue broadly referred to as ‘distributed embodied evolution’ involves swarms of agents independently running evolutionary algorithms while operating within a physical/simulated environment and communicating behaviour parameters to neighbours (Haasdijk et al., ; Trueba et al., ), and is therefore even more similar to our setting, where decentralised RL updates are computed locally and then shared with neighbours. In distributed embodied evolution, the computed fitness of solutions helps determine both which are preserved by agents during local updates, and also which are chosen for broadcast or adoption between neighbours (Hart et al., ; Fernández Pérez et al., ; Fernández Pérez & Sanchez, ). Indeed, some works on distributed embodied evolution specifically consider features or rewards relating to the joint behaviour of the whole population (Gomes & Christensen, ; Prieto et al., ), similar to MFGs. The adjacent research area of cultural/language evolution for swarm robotics (Cambier et al., ; ; ) has similarly demonstrated the combination of evolutionary approaches and multi-agent communication networks for self-organised behaviours in swarms. However, unlike our own work, none of these areas employ reinforcement learning in the update of policies or the computation of the fitness functions.

We preempt objections that communication with neighbours might violate the anonymity that is characteristic of the mean-field paradigm, by emphasising that the communication in our algorithm takes place outside of the ongoing learning-and-updating parts of each iteration. Thus the core learning assumptions of the mean-field paradigm are unaffected, as they essentially apply at a different level of abstraction (a convenient approximation) to the reality we face of $N$ agents that interact within the same environment. Indeed, prior works have combined networks with mean-field theory, such as using a mean field to describe adaptive dynamical networks (Berner et al., ).

## Appendix G Limitations and future work

Our algorithm for the networked case (Alg. 1), as well as prior work on the centralised and independent cases (Yardim et al., ), all have multiple nested loops. This is a potential limitation for real-world implementation, since the decentralised agents might be sensitive to failures in synchronising these loops. However, in practice, we show that our networked architecture provides redundancy and robustness (which the independent-learning algorithm lacks) in case of learning failures that may result from the necessities of synchronisation (see Appx. D). We have also shown that networked communication in combination with the replay buffer allows us to reduce the hyperparameter $M_{td}$ to 1, essentially removing the inner ‘waiting’ loop. Nevertheless, our algorithm still features multiple loops, and future work lies in simplifying the algorithms further to aid practical implementation, possibly by techniques such as asynchronous communication (Ma et al., ).

Since the MFG setting is technically non-cooperative, we have preempted objections that agents would not have incentive to communicate their policies by focusing on coordination games, i.e. where agents seek to maximise only their individual returns, but receive higher rewards when they follow the same strategy as other agents. In this case they stand to benefit by exchanging their policies with others. Nevertheless, in real-world settings, the communication network could be vulnerable to malfunctioning agents or adversarial actors poisoning the equilibrium by broadcasting untrue policy information. It is outside the scope of this paper to analyse how much false information would have to be broadcast by how many agents to affect the equilibrium, but real-world applications may need to compute this and prevent it. Future research to mitigate this risk might build on work such as Piazza et al. (), where ‘power regularisation’ of information flow is proposed to limit the adverse effects of communication by misaligned agents.

While our MFG algorithms are designed to handle arbitrarily large numbers of agents (and theoretically perform better as $N\rightarrow\infty$), the code for our experiments naturally still suffers from a bottleneck of computational speed when simulating agents that in the real world would be acting and learning in parallel, since the GPU can only process JAX-vectorised elements in batches of a certain size.

Our experiments are based on relatively small toy examples that clearly demonstrate the advantages of our new approach, but which lack the complexity of the real-world applications to which we wish to address the approach. It is feasible that in more complex problems, it may not be possible to reduce hyperparameter values to the same extent we have demonstrated in our experimental examples.

Moreover, real-world examples would likely require handling larger and continuous state/action spaces (the latter perhaps building on related work such as Tang et al. ()), which in turn may require (non-linear) function approximation. Future work therefore involves incorporating neural networks into our networked communication architecture for oracle-free, non-episodic MFG settings. Extending our algorithms in this way, which would depend on modifying the PMA step (Vieillard et al., ; Wu et al., ), would allow us to introduce communication networks to MFGs with non-stationary equilibria, in addition to those with larger state/action spaces. Our method for non-stationary games will likely have agents’ policies depending both on their local state and also on the population distribution (Mishra et al., ; Laurière et al., ; Perrin et al., ; Carmona et al., ), but such a high-dimensional observation object would require moving beyond tabular settings to those of function approximation. The present work demonstrates the benefits of the networked communication architecture when the Q-function is poorly estimated and introduces experience relay buffers to the setting of learning from a continuous run of the empirical system. Both elements are an important bridge to employing (non-linear) function approximation in this setting, where the problems of data efficiency and imprecise value estimation can be even more acute, and where we may want to employ experience replay buffers to provide uncorrelated data to train the neural networks (Zhang & Sutton, ). When the policy functions are approximated rather than tabular, our agents would communicate the functions’ parameters instead of the whole policy as now.

In our future work with non-stationary equilibria, where agents’ policies will also depend on the population distribution, it may be a strong assumption to suppose that decentralised agents with local state observations and limited communication radius would be able to observe the entire population distribution. We will therefore explore a framework of networked agents estimating the empirical distribution from only their local neighbourhood as in (Ganapathi Subramanian et al., ), and possibly also improving this estimation by communicating with neighbours (Yongacoglu et al., ), such that this useful information spreads through the network along with policy parameters.

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 1
presentation: 2
questions: The statements are not clear. MARL is a learning framework assuming a finite number of N agents, while MFG is a game-theoretical framework with N-player limit. My understanding is that this paper aims to address the challenge in MARL when the population size grows, but still finite. Thus, it remains unclear how the proposed algorithm is related to MFG, and how MFG can help with the learning of N agents even under the communication scheme. Could the authors clarify the relationship?
soundness: 2
strengths: It introduces a practical communication network to accelerate the convergence of independent learning, without relying on a central learner.
summary: This paper aims to introduce networked communication to the mean field game framework and show how communication accelerates convergence of the learning. Two games are provided, namely, cluster and agree on a single target, to validate the proposed framework.
weaknesses: 1. The experiments have shown extensive results but only on two games. The insights are more on the practical side that introducing communication could benefit convergence. 
2. The theoretical contribution of this paper is unclear. It showed that practically introducing communication could benefit convergence, but where the theoretical contribution lies is not well motivated.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: - In Theorem 3, when $C$ grows larger, why does the gap between learning with partial communication and independent learning seem to be smaller instead of larger? Since more communication may further stabilize the learning process.
- Why when $d_{\mathcal G}$ is 1, the gap between learning with partial communication and centralized learning is 1? Since they are now identical to each other. Also, I'm wondering why the gap between learning with partial communication and independent learning is 0 when $d_{\mathcal G}$ is 1.
- Why is there no ablation study of replay buffer?
soundness: 2
strengths: - The authors provide experiments to justify the results.
- Using a communication network to interpolate between centralized and independent learning is interesting.
summary: This paper investigates learning in mean-field games with a communication network. Specifically, previous work investigated centralized (communicate arbitrarily) and independent learning (no communication at all) in mean-field games. This paper extends the result to the cases when players can only communicate with some neighbors, which is an interpolation between the centralized and the independent cases.

The contribution of the paper is two-fold. Firstly, it shows that when players can communicate partially, the sample complexity is bounded between that of the centralized and the independent cases. Secondly, it shows that the algorithm will converge faster empirically with a replay buffer, including centralized, independent, and partially communicated settings.

[1] Batuhan Yardim, Semih Cayci, Matthieu Geist, and Niao He. Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games. In International Conference on Machine Learning, pp. 39722–39754. PMLR, 2023.
weaknesses: ## Main Concerns
- The theoretical results in this paper do not show the superiority over independent learning. The assumptions in Theorem 3 are too restrictive ($\tau_k\to 0$) and the gap $(\frac{1}{d_{\mathcal G}})^C$ is small.

## Minor Weaknesses
- Writings: The writing of this paper can be further improved. 
  - For example, in Section 3.2, where the authors first introduce $\sigma_{k+1}^i$, the authors may add a brief explanation about what it is.
  - On line 376, when $C\geq d_{\mathcal G}$, it is not $(\frac{1}{d_{\mathcal G}})^{C}=0$ but instead that term in the bound above disappears.

I would be glad to raise the score once the author addresses the issues above.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. How much improvement in learning speed does the introduction of the experience replay buffer bring? 
2. How are the RL states specifically configured in the experiments?
soundness: 3
strengths: 1. The theoretical analysis in the paper is comprehensive and aligns with intuition. The authors point out that the networked communication paradigm conceptually lies between centralized and decentralized approaches and demonstrate that this is also true in terms of sample efficiency and convergence speed, which is very interesting.
2. The experimental results demonstrate that the networked communication method is robust and high-performing, combining the advantages of centralized and decentralized framework. This is consistent with the authors' claims.
3. The paper is well-written and easy to follow. The authors provide all the necessary theories and experimental settings in the main text, with more detailed proofs and specifics included in the appendix.
summary: This paper proposes a networked communication multi-agent reinforcement learning framework to solve mean-field games. The paper first provides theoretical insights into this networked communication paradigm, including the conceptual, sample efficiency, and convergence speed relationships between networked communication learning and centralized versus decentralized learning approaches. Based on this, the paper presents the practical implementation of the paradigm, including a specific method for generating communication content and the introduction of an experience replay buffer to accelerate learning. Through experiments on two grid-world scenarios, the authors demonstrate that the networked communication-based algorithm achieves performance comparable to centralized algorithms, along with higher robustness.
weaknesses: 1. In the theoretical section, the authors present a highly general framework (Algorithm 1), which can evolve into various specific algorithms by adjusting parameters. However, I note that the authors do not compare their practical algorithm with existing MFG algorithms in their experiments. Can any existing algorithms be compared in the experiments? 
2. The communication concept in the paper differs from the typical concept of communication in multi-agent reinforcement learning, which may cause confusion for readers. In those works, communication content between agents is often a learnable vector. In contrast, the networked communication paradigm proposed here is more akin to an evolutionary paradigm, where the policies with higher estimated can propagate within the population.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 4
questions: - What is the benefit over independent learning and centralized learning in terms of robustness? In Fig. 3 it seems to me that all the curves observe the same relative shock. 
- I am not sure why it would make sense to "cooperate" in a competitive game (sharing policies with other agents).
- Could one consider other types of robustness, e.g., against self-interested agents manipulating the policies of others, or model errors / heterogeneity?
- How is the approximation of decrease in divergence obtained in Appx. B.7?
- Figures 1, 2, 3 are hard to read due to their small size. What is depicted in the shaded region?
soundness: 3
strengths: - The paper is very well written and very clear on the main ideas. 
- The work novelly fuses analysis of networked learning with the more realistic recent independent learning concept in MFGs.
- The theoretical results from analyzing the number of independent learned policies are elegant, interesting and significant, as they imply the usefulness of communication in the field of learning in MFGs.
- The discussion of related work and placement of contribution is very extensive and good.
summary: The paper considers a networked learning setting for mean field games that is in-between centralized learning and independent learning. Agents independently learn as in prior work, but share policies through a graph to reduce sample complexity by spreading better policies. The main contribution is theoretical, implying that communication should result in better sample complexity than independent learning. The resulting algorithms were also empirically verified on two problems.
weaknesses: - Although the primary contribution is theoretical, the empirical results are limited in terms of considered problems and their complexity. The exact definition of the problems remains unclear to me, but as far as I understand there is no example with mean field interaction in the state dynamics. 
- The performed empirical changes discussed on page 10 were not empirically shown to be important / no ablation was performed.
- The robustness results are limited to failure in the communication networks and naturally the numbers of agents, so I am not sure what is the benefit over independent learning for robustness.
- See also questions below.

---

confidence: 3
contribution: 3
initial_rating: 1
presentation: 1
questions: * The restriction to stationary MFGs seems to be quite substantial, in the sense that — I can imagine — a player could have an incentive to act in a way which differs from how others act in some games, and that could plausibly lead to a change in the empirical distribution of agents’ state. By restricting ourselves to cases where this does not happen, are we removing potentially-important NE from consideration?
    * My sense is that the only reason for considering this restriction is that it allows us to write down policies as maps from agents’ individual state to action distributions. Without this restriction of stationarity, I believe we would need players’ policies to depend also upon the current (overall) state distribution. If this is the case, it would be helpful to explain things in this way to justify the restriction as necessary for tractability reasons.
* Thm. 1 asserts that there is a unique MFG-NE point. Under what conditions is this assured?
* In Thm. 3, why are there three different upper bounds being discussed? There only appears to be one ultimate upper bound for all three methods in Thm.  2, because the intermediate bounds are not quantified explicitly. Reading the equation on line 373, it seems like we are just talking about somehow roughly quantifying the differences between the three terms on the left of the equation on line 359. 
    * I don’t understand how (1/d_G)^C = 0 on line 376. That does not seem arithmetically possible.
    * I am not clear on how to interpret the \approx symbols in line 373. Is there a precise interpretation?
* It is unclear to me why the changes discussed on line 404 break the theoretical properties derived in the previous section. Especially because this is so central to the structure of the paper, I urge the authors to emphasize the relevant assumptions in the main text rather than punting so much to the appendices.
* The intuition in the paragraph starting on line 418 is very clear! Can the authors provide any theoretical analysis which supports this intuition? Or failing this, can the authors provide a clear remark explaining why such analysis is difficult so as to provide a template for future investigation on this topic?
* Why does the green networked curve appear to be doing better in Fig. 2 than it was in Fig. 1? Isn’t the scenario harder? What is going on here?
    * The statement “independent learners cannot do this and hardly appear to learn at all” is confusing because the reader must deduce on their own that this is referring only to the center subfigure and not to the others. Labelling subfigures would help.
* It is not quite clear to me how the proposed method is handling the change in population size. I suggest the authors clarify exactly how this is done.
* I would appreciate further discussion of the non-uniqueness issue raised in line 535, and how it relates to convergence to a single equilibrium as \lambda \to 0. It is not clear to me how coordination mathematically arises here, or why things do not break (e.g., due to ill-conditioning) as \lambda \to 0.
soundness: 2
strengths: The main theoretical result is particularly interesting: it is quite intuitive that learning in a networked setting would interpolate the performance of independent and centralized schemes, but proving that this is so is a very nice contribution.
summary: This paper studies mean field games in which there is assumed to be a stationary distribution of agents’ state at equilibrium. The authors propose an algorithm for networked policy learning in these games, prove that its performance interpolates that of purely independent and centralized learning schemes, and evaluate the performance of all three approaches in two toy problems. This evaluation shows that the proposed approach works well in parameter regimes and with algorithmic modifications which are not explained by the theory.
weaknesses: * It would be better if the limitations and future work were included in the main text, not the appendix.
* Operator \Gamma_q is not defined properly in the main text. First use is on line 233.
* It would be useful to provide some explanation of what is going on in Definition 7 for readers unfamiliar with Yardim 2023.
* The construction of Definition 8 is not self-contained. All variables ought to be clearly defined in the main text; otherwise the paper is very difficult to understand.
* Nitpick: I suggest moving Alg. 1 up 1 page, so that one does not need to scroll so much between its introduction on line 256 and the algorithm itself.
* The prose description of the algorithm in Sec. 3.2 is difficult to understand as it refers to terms and relations which are not on the same page. I suggest defining all terms formally and precisely inline with proper equation numbers, and structuring the description at a high level with paragraph headers whose titles describe what is going on.
* I also suggest adding comments in the algorithm in order to make it more clear what is going on in different parts. Currently, it is hard to parse because there are so many symbols that were not clearly defined in the main text, and are also not explained in the algorithm block clearly enough to make sense of them without referring back to the main text and trying to connect the dots. For example, I have no idea what \sigma^i_k is precisely, and can only deduce that it is a scalar by examining its use in line 15 of Alg. 1. Line 351 says it can be chosen at random (on line 11 of Alg. 1), but that only adds to my confusion.
* \epsilon is undefined in Thm. 2.
* Graph diameter is never defined as far as I can see.
* The transition buffer usage appears to be a major contribution of the paper, yet it is not described precisely in the final subsection of Sec. 3.
* Fig. 1 is way too small to be readable. All text should be readable by the naked eye. (Same for Fig. 2 and Fig. 3.)
    * It is unclear how many independent trials these results are based upon. Confidence intervals are overlapping for many of the methods, which makes it difficult to visually distinguish between them, and also makes any statistical claims unclear. For example, stating that “our networked architecture significantly outperforms…” (line 508) does not really make sense because all the confidence intervals are so often overlapping, and without a direct pointer to a graph where this is not happening it is hard to justify that conclusion.
    * “Exploitability” is not defined as far as I see in the main text. Neither is “policy divergence.”
* More precise descriptions of the tasks and experiment setup should be provided in the main text of Sec. 4. Without additional information here, the results are difficult to interpret.
* It would be nice if there were figures (in the main text) illustrating the relative performance of the theoretically-sound version of the algorithm with the “hacked” version which breaks the theoretical guarantees but is claimed to perform better. This seems to be a major oversight in the results, since it is such an important part of the authors’ claimed contributions in the introduction and in the discussion on page 10.
* The point on line 538 does not make sense because it relies on something defined only in the appendices.

Meta-review: The paper explores a networked learning framework for Mean Field Games (MFGs), positioned between centralized and independent learning. It presents theoretical insights that suggest that communication in this networked setup can improve sample complexity and convergence speed. The theoretical results are supported by experiments on two grid-world scenarios.

Overall, the Reviewers appreciated the theoretical contributions. For instance, Reviewer y6Sh highlighted the "elegant and significant" results on the utility of communication in MFGs. However, concerns emerged regarding correctness, scope of the experiments, and clarity of the presentation:
- Reviewer xtau noted restrictive assumptions in Theorem 3 and was not sold on the empirical benefits of the proposed method over independent learning. Eventually this led to an in-depth analysis of the technical content. There was a long discussion where progress was made, but it looks like some points remained unresolved, with the last message of the discussion chain, belonging to the author, listing several questions. The last message from the reviewer reads "Therefore, I think the current version is not ready [to be] published and I will maintain my score."
- Reviewer yxK2 found the paper difficult to follow because the key definitions and details were relegated to the appendix. They seemed to be the only reviewer with this issue.
- Reviewer jMnr suggested that additional experiments on communication tradeoffs would improve the work. It remains somewhat unclear, however, what experiments the reviewer had in mind.

While I find the second and third concerns minor, the first one regarding technical details is substantial and needs to be addressed.

Decision: Reject