Robust Cooperative Multi-Agent Reinforcement Learning:
A Mean-Field Type Game Perspective

Reinforcement Learning (RL) has had many successes, such as autonomous driving (Sallab et al., 2017), robotics (Kober et al., 2013), and RL from human feedback (RLHF) (Ziegler et al., 2019), to name a few. These successes have been focused on single-agent scenarios, but many scenarios involving, e.g., financial markets, communication networks, distributed robotics involve multiple agents. Prevailing algorithms for Multi-Agent Reinforcement Learning (MARL) (Zhang et al., 2021b; Li et al., 2021), however, do not model the distinct effects of modeled and un-modeled uncertainties on the transition dynamics, which can result in practical instability in safety-critical applications (Riley et al., 2021).

In this paper we consider a large population multi-agent setting, with stochastic and non-stochastic (un-modeled, possibly adversarial) uncertainties. These types of formulations have been studied under the guise of robust control in the single-agent case (Başar and Bernhard, 2008). The uncertainties (modeled and un-modeled) affect the performance of the system and might even lead to instability. Robust control seeks the robust controller which guarantees a certain level of performance for the system in under a worst-case hypothesis on these uncertainties. We employ here the popular Linear-Quadratic (LQ) setting in order to rigorously characterize and synthesize the solution to the robust multi-agent problem in a data-driven manner. The LQ setting entails a class of models in which the dynamics are linear and the costs are quadratic in the state and the action of the agent. This setting has been used extensively in the literature due to its tractability: the optimal decisions can be computed analytically or almost analytically, up to solving Riccati equations, when one has access to all system matrices. Instances of applications include permanent income theory (Sargent and Ljungqvist, 2000), portfolio management (Cardaliaguet and Lehalle, 2018), and wireless power control (Huang et al., 2003)), among many others. In the absence of knowledge of system parameters, model-free RL methods have also been developed (Fazel et al., 2018; Malik et al., 2019) for single agent LQ settings. We refer to (Recht, 2019) for an overview. When one goes from single to multiple agents, the issue of communicating local state and control information among agents exhibit scalability problems, and in particular, practical algorithms require sharing state information that can scale exponential in the number of agents. Instead, here we consider a distributed information structure where each agent has access only to its own state and the average of states of the other agents. This distributed information structure causes the characterization of the solution to be very difficult, in that previous gradient dominance results from (Fazel et al., 2018) no longer hold. To overcome this difficulty, we utilize the mean-field game and control paradigm, first introduced in the purely non-cooperative agent setting in (Lasry and Lions, 2006; Huang et al., 2006), which replaces individual agents by a distribution over agent types, which enables characterization and computation of the solution. The approach has then been extended to the cooperative setting through the notion of mean field control (Bensoussan et al., 2013; Carmona and Delarue, 2018). Building on this paradigm, this work is the first to develop scalable algorithms for MARL that can handle model mis-specification or adversarial inputs in the sense of robust control in the very large or possibly infinite number of agents defined by the mean-field.

We start Section 2 by formulating a robust multi-agent control problem with stochastic and non-stochastic (un-modeled) noises. The agents have distributed information, such that they have access to their own states and the average behavior of all the agents. Solving this problem entails finding a noise attenuation level (noise-to-output gain) for the multi-agent system and the corresponding robust controller. As in the single-agent setting (Başar and Bernhard, 2008), the robust multi-agent control problem is reformulated into an equivalent zero-sum min-max game between the maximizing non-stochastic noise (which may be interpreted as an adversary) and the minimizing controller. Solving this problem is not possible in the finite agent case due to the limited information available to each agent. Thus, in Section 3 we consider the mean-field (infinite population) version of the problem, that we call the Robust Mean-Field Control (RMFC) problem. As in the finite-population setting, RMFC has an equivalent zero-sum min-max formulation, referred to as the 2-player Zero-Sum Mean-Field Type Game (ZS-MFTG) in (Carmona et al., 2020, 2021), where the controller is the minimizing player and the non-stochastic disturbance is the maximizing one.

In Section 4 we propose a bi-level RL algorithm to compute the Nash equilibrium for the ZS-MFTG (which equivalently yields the robust controller for the robust multi-agent problem) in the form of Receding-horizon Gradient Descent Ascent (RGDA) (Algorithm 1). The upper-level of RGDA, uses a receding-horizon approach, i.e., it finds the controller parameters starting from the last timestep $T-1$ and moving backwards-in-time (à la dynamic programming). The receding-horizon policy gradient approach was used in Kalman filtering (Zhang et al., 2023) and LQR problems (Zhang and Başar, 2023). The present work builds on this approach to multi-agent problems, which helps in simplifying the complex nature of the cost landscape (known to be non-coercive (Zhang et al., 2021a)) and renders it convex-concave. The lower-level employs gradient descent-ascent to find the saddle point (Nash equilibrium) for each timestep $t$. The convex-concave nature of the cost (due to the receding-horizon approach) proves to be a key component in proving linear convergence of the gradient descent-ascent to the saddle point (Theorem 4.1). Further analysis shows that the total accumulated error in the RGDA is small given that the lower level of RGDA has good convergence (Theorem 4.2). The gradient descent-ascent step requires computation of the stochastic gradient. We use a zero-order method (Fazel et al., 2018; Malik et al., 2019) which only requires access to the cost to compute stochastic gradients, and hence is truly model-free.

Literature Review: Robust control gained importance in the 1970s when control theorists realized the shortcomings of optimal control theory in dealing with model uncertainties (Athans et al., 1977; Harvey and Stein, 1978). The work of (Başar, 1989) was the first one to formulate the robust control problem as a zero-sum dynamic game between the controller and the uncertainty. Robust RL first introduced by (Morimoto and Doya, 2005) has recently had an increase in interest in for the single agent setting, where its ability to process trajectory data without explicit knowledge of system parameters can be used to learn robust controllers to address worst-case uncertainty (Zhang et al., 2020a; Kos and Song, 2017; Zhang et al., 2021c). Some recent works consider RL in scenarios with reward uncertainties (Zhang et al., 2020b), state uncertainty (He et al., 2023) or uncertainty in other agents’ policies (Sun et al., 2022). There have been some works on the intersection of RL for robust and multi-agent control (Li et al., 2019; He et al., 2023), yet there has not been any significant effort to provide (1) sufficient conditions for solvability of the multi-agent robust control problem i.e. determining the noise attenuation level of a system and (2) provable Robust multi-agent RL (RMARL) algorithms in the large population setting, as proposed in this paper.

This is made possible due to the mean-field game and control paradigm, which considers the limiting case as the number of agents approaches infinity. This paradigm was first introduced in the context of non-cooperative game theory as Mean-Field Games (MFGs) concurrently by (Lasry and Lions, 2006; Huang et al., 2006). Since then, the question of learning equilibria in MFGs has gained momentum, see (Laurière et al., 2022b). In particular, there have been several works dealing with RL for MFGs (Guo et al., 2019; Elie et al., 2020; Perrin et al., 2020; Zaman et al., 2020; Xie et al., 2021; Anahtarci et al., 2023), deep RL for MFGs (Perrin et al., 2021; Cui and Koeppl, 2021a; Laurière et al., 2022a), learning in multi-population MFGs (Pérolat et al., 2022; Zaman et al., 2021, 2023b), independent learning in MFGs (Yongacoglu et al., 2022; Yardim et al., 2023), oracle-free RL for MFGs (Angiuli et al., 2022; Zaman et al., 2023a) and RL for graphon games (Cui and Koeppl, 2021b; Fabian et al., 2023). There have also been several works on RL for MFC, which is the cooperative counterpart, see e.g. (Carmona et al., 2019a, b; Gu et al., 2021; Mondal et al., 2022; Angiuli et al., 2022). But these works require ability to sample from the true transition model, and hence are inapplicable in the case of mis-specification or modeling errors. To address this setting, we introduce the Robust MFC problem. We will connect this problem to MFTGs Tembine (2017), which contain mixed cooperative-competitive elements. Zero-sum MFTG model a zero-sum competition between two infinitely large teams of agents. Prior work on the theoretical framework of zero-sum MFTG include (Choutri et al., 2019; Tembine, 2017; Cosso and Pham, 2019; Carmona et al., 2021; Guan et al., 2024). Related to RL, the works (Carmona et al., 2020, 2021) propose a data-driven RL algorithm based on Policy Gradient to compute the Nash equilibrium between the two coalitions in an LQ setting but do not provide a theoretical analysis of the algorithm.

In this section we introduce the robust multi-agent control problem by first defining the dynamics of the multi-agent system along with its performance and noise indices. The performance and noise indices have been introduced in the literature (Başar and Bernhard, 2008) in order to quantify the affect of the accumulated noise (referred to as noise index) on the performance of the system (called the performance index). The noise attenuation level is then defined as an upper bound on the ratio between the performance and noise indices given that the agents employ a robust controller. Hence the robust multi-agent problem is that of finding the robust controller under which a certain noise attenuation is achieved. In order to solve this problem, we reformulate it as a min-max game problem as in the single-agent setting (Başar and Bernhard, 2008). Consider an $N$ agent system. We let $[N]=\{1,\dots,N\}$. The $i^{th}$ agent has dynamics which are linear in its state $x^{i}_{t}\in\mathbb{R}^{m}$, its action $u^{1,i}_{t}\in\mathbb{R}^{p}$, and the mean-field counterparts, $\bar{x}_{t}$ and $\bar{u}^{i}_{t}$. The disturbance $u^{2,i}_{t}$ is referred to as non-stochastic noise¹¹1The non-stochastic noise is assumed to have identity coefficient in the dynamics (1) for simplicity of analysis but can be easily changed to some other matrix of appropriate size. since it is an un-modeled disturbance and can even be adversarial. This is similar in spirit to the works of (Simchowitz et al., 2020). Let $T$ be a positive integer, interpreted as the horizon of the problem. The initial condition of agent $i$’s state, $i\in[N]$, is $x^{i}_{0}=\omega^{0,i}+\bar{\omega}^{0}$, where $\omega^{0,i}\sim\mathcal{N}(0,\Sigma^{0})$ and $\bar{\omega}^{0}\sim\mathcal{N}(0,\bar{\Sigma}^{0})$ are i.i.d. noises. For $t\in\{0,\ldots,T-1\}$,

where $u^{1,i}_{t}$ is the control action of the $i^{th}$ agent, $\bar{x}_{t}:=\sum_{i=1}^{N}x^{i}_{t}/N$ is referred to as the state mean-field and $\bar{u}^{j}_{t}:=\sum_{i=1}^{N}u^{j,i}/N$ for $j\in\{1,2\}$ are the control and noise mean-fields respectively. Each agent’s dynamics are perturbed by two types of noise: $\omega^{i}_{t}$ and $\bar{\omega}_{t}$ are referred to as stochastic noises since they are i.i.d. and their distributions are known ($\omega^{i}_{t}\sim\mathcal{N}(0,\Sigma)$ and $\bar{\omega}_{t}\sim\mathcal{N}(0,\bar{\Sigma})$). All of our results (excluding the finite-sample analysis of the RL Algorithm) can be readily generalized for zero-mean non-Gaussian disturbances with finite variance.

In order to define the robust control problem we define the performance index of the population which penalizes the deviation of the agents from their (state and control) mean-fields and also regulates the mean-fields:

where the matrices $Q_{t},\bar{Q}_{t}>0$ are symmetric matrices, $\mathcal{u}^{j}=(\mathcal{u}^{j,i})_{i\in[N]}$ where each $\mathcal{u}^{j,i}$ for $j\in\{1,2\}$ is adapted to the distribution information structure i.e. $\sigma$-algebra generated by $x^{i}_{t}$ and $\bar{x}_{t}$ and $\mathcal{U}^{1},\mathcal{U}^{2}$ represent the set of all possible $\mathcal{u}^{1},\mathcal{u}^{2}$, respectively. We define the noise index of the population in a similar manner

The robust control problem for this $N$ agent system is that of finding the range of noise attenuation levels $\gamma>0$ such that:

Any $\gamma$ for which the above inequality is satisfied is referred to as a viable attenuation level and the least among them is called the minimum attenuation level. The controller $\mathcal{u}^{1}$ which ensures a particular level $\gamma$ of noise attenuation is referred to as the robust controller corresponding to $\gamma$ (or robust controller in short). Since the inequality (4) can also be reformulated as $J_{N}(\cdot)/\varpi_{N}(\cdot)\leq\gamma^{2}$, a viable attenuation parameter $\gamma^{2}$ is also an upper bound on the noise-to-output gain of the system. As outlined in (Başar and Bernhard, 2008) for a single agent problem the condition (4) is equivalent to finding the range of value of $\gamma>0$ such that

where the infimizing controller $u^{1}$ is the robust controller and the supremizing controller $u^{2}$ is the worst-case non-stochastic noise. If we define the robust $N$ agent cost $J^{\gamma}_{N}$ as follows

then using (2) and (3), the robust $N$ agent control problem (5) can be equivalently written as

Due to the distributed information structure of the agents the standard theory of single-agent robust control does not apply in this setting. Hence we are unable to provide sufficient conditions for a given $\gamma>0$ to be a viable attenuation level, and we resort to the mean-field limit as $N\to\infty$, which is of independent interest. The next section formulates the Robust Mean-Field Control (RMFC) problem and its equivalent 2-player zero-sum Mean-Field Type Game (ZS-MFTG) representation, and provides sufficient conditions for solvability of both.

Consider a system with infinitely many agents, where the generic agent has linear dynamics of its state $x_{t}$ for a finite-horizon $t\in\{0,\ldots,T-1\}$:

where $u^{1}_{t}$ is the control action of the generic agent, $\bar{x}_{t}:=\mathbb{E}[x_{t}|(\bar{\omega}_{s})_{0\leq s\leq t-1}]$ is referred to as the state mean-field and $\bar{u}^{j}_{t}:=\mathbb{E}[u^{j}_{t}|(\bar{\omega}_{s})_{0\leq s\leq t-1}]$ for $j\in\{1,2\}$ are the control and noise mean-fields respectively. The initial condition of the generic agent is $x_{0}=\omega^{0}+\bar{\omega}^{0}$, where $\omega^{0}\sim\mathcal{N}(0,\Sigma^{0})$ and $\bar{\omega}^{0}\sim\mathcal{N}(0,\bar{\Sigma}^{0})$ are i.i.d. noises. The stochastic noises $\omega^{i}_{t}$ and $\bar{\omega}_{t}$ are i.i.d. such that $\omega^{i}_{t}\sim\mathcal{N}(0,\Sigma)$ and $\bar{\omega}_{t}\sim\mathcal{N}(0,\bar{\Sigma})$, whereas the non-stochastic noise $u^{2}_{t}$ are un-modeled uncertainties. Similar to the $N$ agent case, we define the robust mean-field cost $J^{\gamma}$ as follows

Now the robust mean-field control problem which is the mean-field analog to (6) is defined as follows.

Now, under the condition of interchangability of the inf and sup operations, the problem of finding
$\inf_{\mathcal{u}^{1}}\sup_{\mathcal{u}^{2}}J^{\gamma}(\mathcal{u}^{1},\mathcal{u}^{2})$ is that of finding the Nash equilibrium (equivalently, saddle point, in this case) of the Zero-sum 2-player Mean-Field Type Game; see (Carmona et al., 2020, 2021) for a very similar LQ setting without the theoretical analysis of the RL algorithm. In the following section we provide sufficient conditions for existence and uniqueness of a solution to this saddle point problem along with the value of $\inf_{\mathcal{u}^{1}}\sup_{\mathcal{u}^{2}}J^{\gamma}(\mathcal{u}^{1},\mathcal{u}^{2})$.

This result can be proved using techniques in proofs of Theorem 3.2 in (Başar and Bernhard, 2008) or Proposition 36 in (Carmona et al., 2021). We now use the Nash value of the game (14) to come up with a condition for the attenuation level $\gamma$ which solves the robust mean-field control problem (9). First we simplify expression in (9) $\mathbb{E}\sum_{t=0}^{T-1}\lVert\omega_{t}\rVert^{2}+\lVert\bar{\omega}_{t}\rVert^{2}=T\operatorname{Tr}(\Sigma+\bar{\Sigma})$ using the i.i.d. stochastic nature of the noise. Combining this fact with (14), we arrive at the conclusion that (9) will be satisfied if and only if

The proof of this result can be found in the Supplementary Materials. The above theorem states that, if for a given $\gamma$, conditions (12) and (16) are satisfied (given that $M^{\gamma}_{t}$ and $\bar{M}^{\gamma}_{t}$ are defined by (13)), then not only is $\gamma$ a viable attenuation level for the original Robust multi-agent control problem (1)-(4), but the Nash equilibrium for the ZS-MFTG also yields the robust controller $u^{1,i*}_{t}=-K^{1*}_{t}(x^{i}_{t}-\bar{x}_{t})-L^{1*}_{t}\bar{x}_{t}$ for the original finite-agent game. Condition (16) is strictly stronger than condition (15) but approaches (16) as $N\rightarrow\infty$.

In this section we present the Receding-horizon policy Gradient Descent Ascent (RGDA) algorithm to compute the Nash equilibrium (Theorem 3.2) of the 2-player MFTG (7)-(8), which will also generate the robust controller for a fixed noise attenuation level $\gamma$. For this section we assume access to only the finite-horizon costs of the agents under a set of control policies, and not the state trajectories. Under this setting the model of the agents cannot be constructed hence our approach is truly model free (Malik et al., 2019). Due to the non-convex non-concave (also non-coercive (Zhang et al., 2020b)) nature of the cost function $J^{\gamma}$ in (11), instead we solve the receding-horizon problem, for each $t=\{T-1,\ldots,1,0\}$ backwards-in-time. This entails solving $2\times T$ min-max problems, where each problem is convex-concave and aims at finding $(K_{t},L_{t})=\big{(}(K^{1}_{t},K^{2}_{t}),(L^{1}_{t},L^{2}_{t})\big{)}$ at time step $t$, given the set of future controllers (controllers for times greater than $t$), $\big{(}(\tilde{K}_{t+1},\tilde{L}_{t+1}),\ldots,(\tilde{K}_{T},\tilde{L}_{T})\big{)}$ are held constant. But first we must approximate the mean-field term using finitely many agents.

We first define some relevant notation. We define the joint controllers for each timestep $t$ as $\bar{K}_{t}=[(K^{1}_{t})^{\top},(K^{2}_{t})^{\top}]^{\top}$ and $\bar{L}_{t}=[(L^{1}_{t})^{\top},(L^{2}_{t})^{\top}]^{\top}$, for the sake of conciseness. For each timestep $t\in\{T-1,\ldots,1,0\}$ let us also define the target joint controllers $\tilde{\bar{K}}^{*}_{t}=(\tilde{K}^{1*}_{t},\tilde{K}^{2*}_{t}),\tilde{\bar{L}}^{*}_{t}=(\tilde{L}^{1*}_{t},\tilde{L}^{2*}_{t})$, as the set of policies which exactly solve the receding-horizon min-max problem (18). Notice that the set of target controllers $\tilde{\bar{K}}^{*}_{t},\tilde{\bar{L}}^{*}_{t}$ are unique (due to convex-concave nature of (18)) but do depend on the set of future joint controllers $(\bar{K}_{s},\bar{L}_{s})_{t<s<T}$. On the other hand, the Nash joint controllers are denoted by $\bar{K}^{*}_{t}=(K^{1*}_{t},K^{2*}_{t})$ and $\bar{L}^{*}_{t}=(L^{1*}_{t},L^{2*}_{t})$. Furthermore, the target joint controllers are equal to the Nash joint controllers $(\tilde{\bar{K}}^{*}_{t},\tilde{\bar{L}}^{*}_{t})=(\bar{K}^{*}_{t},\bar{L}^{*}_{t})$ only if the future joint controllers are also Nash $(\bar{K}_{s},\bar{L}_{s})_{t<s<T}=(\bar{K}^{*}_{s},\bar{L}^{*}_{s})_{t<s<T}$.

Closed form expressions of the bounds can be found in the proof given in the Supplementary materials. The linear rate of convergence is made possible by building upon the convergence analysis of descent ascent in (Fallah et al., 2020) due to the convex-concave nature of the cost function (18). The proof generalizes the techniques used in (Fallah et al., 2020) to stochastic unbiased gradients by utilizing the fact that the bias in stochastic gradients $\tilde{\nabla}_{j}\tilde{J}^{i,\gamma}_{t}$ for $j\in\{1,2\}$ can be reduced by reducing the smoothing radius $r$. This in turn causes an increase in the variance of the stochastic gradient which is controlled by increasing the mini-batch size $N_{b}$.

Now we present the non-asymptotic convergence guarantee of the paper stating that even though each iteration of the outer loop (as timestep $t$ moves backwards-in-time) accumulates error, if the error in each outer loop iteration is small enough, the total accumulated error will also be small enough. The proof can be found in the Supplementary Materials.

The Nash gaps at each time $t$, $\lVert K^{j}_{t}-K^{j*}_{t}\rVert$ and $\lVert L^{j}_{t}-L^{j*}_{t}\rVert$ for $j\in\{1,2\}$ are due to a combination of the optimality gap in the inner loop $\lVert\bar{K}_{t}-\tilde{\bar{K}}^{*}_{t}\rVert^{2}_{2},\lVert\bar{L}_{t}-\tilde{\bar{L}}^{*}_{t}\rVert^{2}_{2}$ and the accumulated Nash gap in the future joint controllers $\lVert K^{j}_{s}-K^{j*}_{s}\rVert$ and $\lVert L^{j}_{s}-L^{j*}_{s}\rVert$ for $j\in\{1,2\}$ and $t<s<T$. The proof of Theorem 4.2 characterizes these two quantities and then shows that if the optimality gap at each timestep $t\in\{0,\ldots,T-1\}$ never exceeds some small $\epsilon$, then the Nash gap at any time $t$ never exceeds $\epsilon$ scaled by a constant.