Graphon Mean-Field Control for Cooperative Multi-Agent Reinforcement Learning

In the following, we consider a cooperative multi-agent system and its associated mean-field limit. In this system, each agent is affected by all others, with different agents exerting different effects on her. This multi-agent system with $N$ agents can be described by a weighted graph $G_{N}=({\cal V}_{N},\mathcal{E}_{N})$, where the vertex set ${\cal V}_{N}=\{1,\ldots,N\}$ and the edge set $\mathcal{E}_{N}$ represent agents and the interactions between agents, respectively. To study the limit of the multi-agent system as $N$ goes to infinity, we adopt the graphon theory introduced in [39] used to characterize the limit behavior of dense graph sequences. Therefore, throughout the paper, we assume the graph $G_{N}$ is dense and leave sparse graphs for future study.

In general, a graphon is represented by a bounded symmetric measurable function $W:$ $\mathcal{I}\times\mathcal{I}\to\mathcal{I}$, with $\mathcal{I}=[0,1]$. We denote by ${\cal W}$ the space of all graphons and equip the space ${\cal W}$ with the cut norm $\|\cdot\|_{\square}$

It is worth noting that each weighted graph $G_{N}=({\cal V}_{N},\mathcal{E}_{N})$ is uniquely determined by a step-graphon $W_{N}$

We assume that the sequence of $W_{N}$ converges to a graphon $W$ in cut norm as the number of agents $N$ goes to infinity, which is crucial for the convergence analysis of cooperative MARL in Section 3.

Some common examples of graphons include

1. 1)

   Erdős Rényi: $W(\alpha,\beta)=p$, $0\leq p\leq 1$, $\alpha,\beta\in\mathcal{I}$;

2. 2)

   Stochastic block model:

   $\displaystyle W(\alpha,\beta)=\left\{\begin{array}[]{rll}p&\mbox{if}\;0\leqslant\alpha,\beta\leqslant 0.5\;\mbox{or}\;0.5\leqslant\alpha,\beta\leqslant 1,\\ q&\mbox{otherwise},\end{array}\right.$

   where $p$ represents the intra-community interaction and $q$ the inter-community interaction;

3. 3)

   Random geometric graphon: $W(\alpha,\beta)=f(\min(|\beta-\alpha|,1-|\beta-\alpha|))$, where $f:[0,0.5]\to[0,1]$ is a non-increasing function.

In this section, we facilitate the analysis of MARL by considering a particular class of MARL with nonuniform interactions, where each agent interacts with all other agents via the aggregated weighted mean-field effect of the population of all agents.

Recall that we use the weighted graph $G_{N}=({\cal V}_{N},\mathcal{E}_{N})$ to represent the multi-agent system, in which agents are cooperative and coordinated by a central controller. They share a finite state space ${\cal S}$ and take actions from a finite action space $\mathcal{A}$. We denote by ${\cal P}({\cal S})$ and ${\cal P}({\cal A})$ the space of all probability measures on ${\cal S}$ and ${\cal A}$, respectively. Furthermore, denote by ${\cal B}({\cal S})$ the space of all Borel measures on ${\cal S}$.

For each agent $i$, the neighborhood empirical measure is given by

where $\delta_{s_{t}^{j}}$ denotes Dirac measure at $s_{t}^{j}$, and $\xi_{i,j}^{N}$ describing the interaction between agents $i$ and $j$ is taken as either

or

At each step $t=0,1,\cdots,$ if agent $i$, $i\in[N]$ at state $s^{i}_{t}\in{\cal S}$ takes an action $a^{i}_{t}\in\mathcal{A}$, then she will receive a reward

where $r:{\cal S}\times{\cal B}({\cal S})\times{\cal A}\to\mathbb{R}$, and she will change to a new state $s^{i}_{t+1}$ according to a transition probability such that

where $P:{\cal S}\times{\cal B}({\cal S})\times{\cal A}\to{\cal P}({\cal S})$.

(2.3)-(2.4) indicate that the reward and the transition probability of agent $i$ at time $t$ depend on both her individual information $(s_{t}^{i},a_{t}^{i})$ and neighborhood empirical measure $\mu^{i,W_{N}}_{t}$.

Furthermore, the policy is assumed to be stationary for simplicity and takes the Markovian form

which maps agent $i$’s state to a randomized action. For each agent $i$, the space of all policies is denoted as $\Pi$.

The objective of the multi-agent system (2.2)-(2.5) is to maximize the expected discounted accumulated reward averaged over all agents, i.e.,

subject to (2.2)-(2.5) with a discount factor $\gamma$ $\in$ $(0,1)$.

We expect the cooperative MARL (2.2)-(2.2) to become a GMFC problem as $N\to\infty$. In GMFC, there is a continuum of agents $\alpha\in\mathcal{I}$, and each agent with the index/label $\alpha\in\mathcal{I}$ follows

where $\mu_{t}^{\alpha}$ $={\cal L}(s_{t}^{\alpha})$, $\alpha\in\mathcal{I}$ denotes the probability distribution of $s_{t}^{\alpha}$, and $\mu_{t}^{\alpha,W}$ is defined as the neighborhood mean-field measure of agent $\alpha$:

with the graphon $W$ given in Assumption 2.1.

To ease the sequel analysis, define the space of state distribution ensembles ${\boldsymbol{{\cal M}}}:={\cal P}({\cal S})^{\mathcal{I}}:=\{f:\mathcal{I}\to{\cal P}({\cal S})\}$ and the space of policy ensembles ${\boldsymbol{\Pi}}:={\cal P}({\cal A})^{{\cal S}\times\mathcal{I}}$. Then ${\boldsymbol{\mu}}:=(\mu^{\alpha})_{\alpha\in\mathcal{I}}$ and ${\boldsymbol{\pi}}:=(\pi^{\alpha})_{\alpha\in\mathcal{I}}$ are elements in ${\boldsymbol{{\cal M}}}$ and ${\boldsymbol{\Pi}}$, respectively.

The objective of GMFC is to maximize the expected discounted accumulated reward averaged over all agents $\alpha\in\mathcal{I}$

In this section, we show that GMFC (2.8)-(2.3) can be reformulated as a MDP with deterministic dynamics and continuous state-action space ${\boldsymbol{{\cal M}}}$ $\times$ ${\boldsymbol{\Pi}}$.

The proof of Theorem 3.1 is similar to the proof of Lemma 2.2 in [23]. So we omit it here.

(3.4) and (3.2) indicate the evolution of the state distribution ensemble ${\boldsymbol{\mu}}_{t}$ over time. That is, under the fixed policy ensemble ${\boldsymbol{\pi}}$, the state distribution $\mu_{t+1}^{\alpha}$ of agent $\alpha$ at time $t+1$ is fully determined by the policy ensemble ${\boldsymbol{\pi}}$ and the state distribution ensemble ${\boldsymbol{\mu}}_{t}$ at time $t$. Note that the state distribution of each agent $\alpha$ is fully coupled with state distributions of the population of all agents via the graphon $W$.

With the reformulation in Theorem 3.1, the associated $Q$ function starting from $({\boldsymbol{\mu}},{\boldsymbol{\pi}})\in{\boldsymbol{{\cal M}}}\times{\boldsymbol{\Pi}}$ is defined as

Hence its Bellman equation is given by

In this section, we show that GMFC (2.8)-(2.3) provides a good approximation for the cooperative multi-agent system (2.2)-(2.2) in terms of the value function and the optimal policy ensemble. To do this, the following assumptions on $W$, $P$, $r$, and ${\boldsymbol{\pi}}$ are needed.

Assumption 3.3 is common in graphon mean-field theory [21, 15, 29]. Indeed, the Lipschitz continuity assumption on $W$ in Assumption 3.3 can be relaxed to piecewise Lipschitz continuity on $W$.

Assumptions 3.4-3.6 are standard and commonly used to bridge the multi-agent system and mean-field theory.

To show approximation properties of GMFC in the large-scale multi-agent system, we need to relate policy ensembles of GMFC to policies of the multi-agent system. On one hand, one can see that any ${\boldsymbol{\pi}}\in{\boldsymbol{\Pi}}$ leads to a $N$-agent policy tuple $(\pi^{1},\ldots,\pi^{N})\in\Pi^{N}$ with

On the other hand, any $N$-agent policy tuple $(\pi^{1},\ldots,\pi^{N})\in\Pi^{N}$ can be seen as a step policy ensemble ${\boldsymbol{\pi}}^{N}$ in ${\boldsymbol{\Pi}}$:

Directly learning Q function of GMFC in (3.6) will lead to high complexity. Instead, we will introduce a smaller class of GMFC with a lower dimension in the next section, which enables a scalable algorithm.

This section will show that discretizing the graphon index $\alpha\in\mathcal{I}$ of GMFC enables to approximate Q function in (3.6) by an approximated Q function in (3.10) below defined on a smaller space, which is critical for designing efficient learning algorithms.

Precisely, we choose uniform grids $\alpha_{m}\in\mathcal{I}_{M}:=\{\frac{m}{M},0\leq m\leq M\}$ for simplicity, and approximate each agent $\alpha\in\mathcal{I}$ by the nearest $\alpha_{m}\in\mathcal{I}_{M}$ close to it. Introduce $\widetilde{\boldsymbol{{\cal M}}}_{M}:={\cal P}({\cal S})^{\mathcal{I}_{M}}$, $\widetilde{\boldsymbol{\Pi}}_{M}:={\cal P}({\cal A})^{{\cal S}\times{\cal I}_{M}}$. Meanwhile, $\tilde{\boldsymbol{\mu}}:=(\tilde{\mu}^{\alpha_{m}})_{m\in[M]}\in\widetilde{\boldsymbol{{\cal M}}}_{M}$ and $\tilde{\boldsymbol{\pi}}:=(\tilde{\pi}^{\alpha_{m}})_{m\in[M]}\in\widetilde{\boldsymbol{\Pi}}_{M}$ can be viewed as a piecewise constant state distribution ensemble in ${\boldsymbol{{\cal M}}}$ and a piecewise constant policy ensemble in ${\boldsymbol{\Pi}}$, respectively. Our arguments can be easily generalized to nonuniform grids.

Consequently, instead of performing algorithms according to (3.6) with a continuum of graphon labels directly, we work with GMFC with $M$ blocks called block GMFC, in which agents in the same block are homogeneous. The Bellman equation for Q function of block GMFC is given by

where the neighborhood mean-field measure, the aggregated reward $\widetilde{R}:\widetilde{\boldsymbol{{\cal M}}}_{M}\times\widetilde{\boldsymbol{\Pi}}_{M}\to\mathbb{R}$ and the aggregated transition dynamics $\widetilde{\boldsymbol{\Phi}}:\widetilde{\boldsymbol{{\cal M}}}_{M}\times\widetilde{\boldsymbol{\Pi}}_{M}\to\widetilde{\boldsymbol{{\cal M}}}_{M}$ are given by

We see from (3.10) that block GMFC is a MDP with deterministic dynamics $\widetilde{\boldsymbol{\Phi}}$ and continuous state-action space $\widetilde{\boldsymbol{{\cal M}}}_{M}\times\widetilde{\boldsymbol{\Pi}}_{M}$. The following Theorem shows that there exists an optimal policy ensemble of block GMFC in $\widetilde{\boldsymbol{\Pi}}_{M}$.

Furthermore, we show that with sufficiently fine partitions of the graphon index $\mathcal{I}$, i.e., $M$ is sufficiently large, block GMFC (3.10)-(3.13) well approximates the multi-agent system in Section 2.2.

Theorem 3.9 shows that the optimal policy ensemble of block GMFC is near-optimal for all sufficiently large multi-agent systems, meaning that block GMFC provides a good approximation for the multi-agent system.

Recall that block GMFC can be viewed as a MDP with deterministic dynamics and continuous state-action space. To learn block GMFC, one can adopt a similar kernel-based Q learning method in [24] for MFC, a uniform discretization method or deep reinforcement algorithms like DDPG [37] for MFC in [9] with theoretical guarantees. Since block GMFC has a higher dimension than classical MFC, we choose to adapt DRL algorithm Proximal Policy Optimization (PPO) [47] to block GMFC and then apply the learned policy ensemble of block GMFC to the multi-agent system to validate our theoretical findings. We describe the deployment of block GMFC in the multi-agent system in Algorithm 1, which we call it N-agent GMFC.

To prove Theorem 3.7, we need the following two Lemmas. We start by defining the step state distribution ${\boldsymbol{\mu}}_{t}^{N}:=({\mu}_{t}^{N,\alpha})_{\alpha\in\mathcal{I}}$ for notational simplicity

Lemma 4.1 shows the convergence of the neighborhood empirical measure to the neighborhood mean-field measure.

Moreover, if the graphon convergence in Assumption 2.1 is at rate $\mathcal{O}(\frac{1}{\sqrt{N}})$, then

Lemma 4.2 shows the convergence of the state distribution of $N$-agent game to the state distribution of GMFC.