Reinforcement Learning for Finite Space Mean-Field Type Games

Authors: Kai Shao, Jiacheng Shen, Chijie An, Mathieu Lauriere
Primary area: reinforcement learning
Keywords: mean field type games, deep reinforcement learning, Nash Q learning

Abstract:
Mean field type games (MFTGs) describe Nash equilibria between large coalitions: each coalition consists of a continuum of cooperative agents who maximize the average reward of their coalition while interacting non-cooperatively with a finite number of other coalitions. Although the theory has been extensively developed, we are still lacking efficient and scalable computational methods. Here, we develop reinforcement learning methods for such games in a finite space setting with general dynamics and reward functions. We start by proving that MFTG solution yields approximate Nash equilibria in finite-size coalition games. We then propose two algorithms. The first is based on quantization of mean-field spaces and Nash Q-learning. We provide convergence and stability analysis. We then propose a deep reinforcement learning algorithm, which can scale to larger spaces. Numerical experiments in 5 environments with mean-field distributions of dimension up to $200$ show the scalability and efficiency of the proposed method.

Decision: reject
Reviewer scores: 3, 3, 8, 8

Reviews and discussion:
<thread>
creation date:
1730375903701

thread_type:
official_review

<thread_object>
creator: reviewer_rave

<content>
summary:
The paper considers mean field type games which combine cooperative and competitive characteristics, i.e. agents form multiple cooperative coalitions but there is competition between coalitions. The authors focus on a quite general finite space case where they derive novel theoretical results and propose different learning schemes. They conclude their work with an evaluation of the proposed learning algorithms on different examples.

strengths:
I think that this paper is a nice contribution to the MF(T)G literature and closes a conceptual gap in the existing literature. This work is well-written and structured. The assumptions for the theoretical results are clearly stated and discussed, and the Nash Q-learning algorithm is also analyzed rigorously. The algorithms appear to perform well on the given examples, and I liked that the authors provide both a mathematically tractable learning approach (Nash Q) as well as a scalable algorithm based on deep learning. Finally, the authors did a good job at discussing limitations of their current work.

weaknesses:
Overall, I think the paper is sound and I did not spot major weaknesses. One general criticism that I have is that the presentation and formatting of the figures can be improved, e.g. by increasing font sizes and making captions more informative (see the following comments for details). Here are my comments:

-	Lines 34-35: Mean field games were not (first) introduced in these references. I think the authors mixed these references up with the earlier works of Lasry and Lions (2007) and Huang, Malhame and Caines (2006), which would be the correct references here.
-	Line 111, a small question regarding notation: Why do we need all $N_1, …, N_m$ in the superscript for the MF of coalition $i$? Wouldn’t it suffice and simplify notations if the superscript would just be $i, N_i$?
-	Suggestion: One could define something like $\bar{N} \coloneqq (N_1, \ldots, N_m)$ or similar to abbreviate the following mathematical expressions.
-	Assumption 3, potential typo: “The policies … satisfies” should be “satisfy”.
-	The font size in most of the figures, especially Figures 1 and 3, is very small. Is it possible to increase the figure font size?
-	Line 478: It says “Fig. 5 (left) shows the testing rewards”. Since Figure 5 is just one plot, what does “left” refer to here? Also, Figure 5 shows exploitabilities but not testing rewards.
-	Line 481: There is a reference to Figure 1 here. Is this correct?
-	Some of the figure captions, e.g. Figures 3 and 5, are very short and uninformative. For example, the caption in Figure 3 could at least mention that the exploitability is averaged over testing sets and players. And it should also briefly state what the bands surrounding the curves depict. In general, it should be possible to get a basic understanding of the figures without reading all details in the main text.

questions:
1. Theorem 2.4: Could the authors please discuss the condition on the discount factor $\gamma (1 +L_\pi + L_p) < 1$? Especially, how restrictive is this inequality?
2. Example 1: I am not sure whether Example 1 is an expressive game. To my understanding, the optimal solution is rather trivial (Coalition 1 stays where it is, Coalition 2 moves to the state of Coalition 1) and I don’t see any potential conflict of interest between the two coalitions. Thus, my question is if the authors consider this game to be competitive in a strict sense on the coalition level? If so, what exactly are the coalitions competing about?
3. How scalable are the proposed learning algorithms with respect to a growing number $m$ of coalitions?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730552454282

thread_type:
official_review

<thread_object>
creator: reviewer_iizw

<content>
summary:
The paper considers an extension of mean field games to many agents in coalitions that compete against each other. In the case of many agents, the infinite-agent case reduces the otherwise difficult problem to a classical finite player game, albeit with high-dimensional state-actions. As a result, the problem is analyzed and solved using classical techniques (Nash Q-Learning) and discretization / deep RL. The proposed algorithms are verified on a variety of examples, and compared to basic independent RL.

strengths:
- The paper is well written and clear. 
- The work fuses existing ideas from MFGs with algorithms from both game theory and deep RL.
- The transfer of NashQ-based theoretical analysis and algorithms beyond classical mean-field RL (Yang et al., 2018) to mean-field games and mean-field-type games is interesting.
- The empirical evaluations and examples extensively demonstrate the potential of proposed algorithms.

weaknesses:
- The empirical significance of the paper is somewhat limited, as the experiments show only limited improvement in terms of exploitability over baselines, while the setting sounds a bit niche to me. I wonder if one could discuss more the significance of the setting, as I believe the referenced works (Tembine et al.) do not consider coalitions, but rather refer to standard MFGs as mean-field-type games.
- The theoretical results are limited due to many assumptions (Assumptions 1-8): The approximate Nash property in Theorem 2.4 requires an unusually strong condition on $\gamma$, and the algorithmic convergence (understandably) requires strong conditions on the stage games. To improve the applicability of the theoretical results, perhaps some assumptions in Section 2.2 could be relaxed or discussed more.
- The model and NashQ-based analysis are not highly novel, as partially remarked by the authors. The setting is also related to graph-based works, e.g., [1] considering infinite numbers of infinitely large coalitions through a double limit.

[1] Caines, Peter E., and Minyi Huang. "Graphon mean field games and the GMFG equations: $\epsilon$-Nash equilibria." 2019 IEEE 58th Conference on Decision and Control (CDC). IEEE, 2019.

questions:
- Is Assumption 3 required, or could one perhaps also consider smaller classes of policies, e.g., ones that do not depend on the deterministic-in-the-limit mean field?
- What is the difficulty in relaxing the strong condition on $\gamma$ in Theorem 2.4, as it is not required in classical MFGs [2]? 
- Could Assumption 8 follow from the previous assumptions?

[2] Saldi, Naci, Tamer Basar, and Maxim Raginsky. "Markov--Nash equilibria in mean-field games with discounted cost." SIAM Journal on Control and Optimization 56.6 (2018): 4256-4287.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730626862937

thread_type:
official_review

<thread_object>
creator: reviewer_ijet

<content>
summary:
This paper explores the application of mean field games (MFGs) to learn approximate ϵ-Nash equilibria. The authors present several theoretical findings. One key result (Theorem 2.4) shows that, with sufficient Lipschitz constraints on the Markov game properties, the approximation error for the finite MFG can be bounded by $O(|S| \sqrt{|A|} / \sqrt{N})$. Another result (Theorem 3.2) demonstrates that, under similar Lipschitz bounds, the $\epsilon$-approximation error can be bounded by a linear function of these constraints, achieved via Nash Q-learning. In addition to the theoretical contributions, the authors present empirical results using the Deep Deterministic Policy Gradient (DDPG) algorithm. They demonstrate that, across multiple settings, the DDPG algorithm converges to an approximate Nash equilibrium.

strengths:
- The paper addresses a relevant and practical problem, and the proposed technology could be applied to real-world scenarios such as cybersecurity and economics.

- The authors conduct a comprehensive empirical study, showing that the DDPG algorithm performs well in converging to an approximate Nash equilibrium.

weaknesses:
- The proofs of error bounds rely heavily on ensuring all components of the MFTG (reward, transition, policy, etc.) satisfy Lipschitz conditions. While this approach is valid, proving these conditions poses no significant technical challenge and may be considered borderline trivial.

- The authors claim to be the first to apply deep reinforcement learning (RL) to MFTGs, yet there are recent works (e.g., [1], [2]) that also explore similar applications. The paper does not adequately position its contributions relative to these advancements.

- There is a disconnect between the theoretical framework (based on Nash Q-learning) and the empirical results (focused on DDPG). The theoretical guarantees are established specifically for Nash Q-learning, but no similar results are provided for DDPG, resulting in a gap between the theory and the experiments.

questions:
- In Section 2.3, the authors show an equivalence between mean-field games and Markov Decision Processes (MDPs). It is well known that MFGs can be represented as MDPs; were any new or useful features introduced in this reformulation to a mean-field MDP?

- In line 384, the authors suggest that solving the one-stage game is already intractable. Are we primarily interested in analyzing the sequential game outcomes, or does the focus remain on the single-stage game? This distinction is crucial, as the results between single stage game and sequential game may differ drastically.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730773575035

thread_type:
official_review

<thread_object>
creator: reviewer_34g4

<content>
summary:
This paper proposes a mean field type game (MFTG) with a finite number of noncooperative coalitions in which each coalition consists of a continuum of cooperative agents. Learning algorithms are proposed to solve approximate Nash equilibria in finite-size coalition games. Convergence and stability analysis are provided. Extensive numerical experiments are conducted.

strengths:
Strength:
The paper is easy to follow with a clear logic from model formulation, equilibrium definition, algorithm implementation, to numerical experiments.

weaknesses:
The novelty remains unclear. The authors are suggested to motivate readers in terms of what fundamental challenges an MFTG brings forth, of which learning algorithms and properties differ significantly from existing MFG and mean field control (MFC). The proposed two learning methods are incremental to the existing learning methods used for MFG. Reformulation with mean field MDPs is not new either.

Overall, this paper is more of a combination of existing concepts and methods for a mean field type game, rather than making fundamental contributions to the field of MFG or MFC.

questions:
Could the authors provide more clarification in terms of why a finite space algorithm needs to presented first in Sec. 3 while having a DRL for Sec. 4? Using DRL for learning MFGs with large state and action spaces is widely used and well developed in MFG.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731897570600

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Common reply

comment:
We thank all reviewers for their efforts and reviews. Their comments help increasing the quality of our paper. We are grateful for their acknowledgement that the paper is "easy to follow with a clear logic" and that our work "addresses a relevant and practical problem". We will soon upload a revised version of the paper with all the changes described in our responses, including new numerical results for a variant of Example 1. In the meantime, we provide detailed answers to all the questions and explain the changes we are making in the paper.

Before giving answers for each reviewer, we want to provide a common reply to a clarify a few important points.

**(1) MFTGs are not MFG nor MFC:** Existing algorithms for mean field games (MFG) and mean field control (MFC) **cannot be used** for the type of problems that our paper studies, namely, mean field type games (MFTGs). Although these topics share some key words, there are important differences. As we wrote on pages 1 and 2: *"MFTGs are different from MFGs because the agents are cooperative within coalitions, while MFGs are about purely non-cooperative agents. They are also different from MFC problems, in which the agents are purely cooperative. As a consequence, computational methods and learning algorithms for MFGs and MFC problems cannot be applied to compute Nash equilibria between mean-field coalitions in MFTGs"*. If the reviewers think that existing algorithms can solve our MFTGs, we encourage them to provide specific references from the literature so we can provide detailed explanations.


**(2) MFTGs = Nash equilibrium between MFMDPs:** Solving an MFTG is significantly more complex than solving a mean field MDP (MFMDP). Indeed, the concept of MFMDP has been introduced for discrete time MFC [Motte & Pham, 2022], [Carmona et al., 2023], which is a *fully cooperative* population. In this paper, we consider a **non-cooperative** game where each central player has an **MFMDP**. Our paper is to MFMDP what Markov games are to plain MDPs. Solving Nash equilibria is much more complex than solving MDPs; see for instance (Daskalakis et al., 2023).

**(3) Assumptions and theoretical results:**  In this paper, we assume that the environment satisfies certain Lipschitz conditions. These **assumptions are frequently used** in MFGs and MFC see e.g. (Anahtarci et al., 2023), (Cosso et al., 2019), (Guan et al., 2024). Notice that our theoretical results provide not only convergence but **rates of convergence** (both for $\epsilon$-Nash approximation and error analysis of Nash Q-learning), so we believe it is worth making these assumptions. It should also be noted that we **do not require all the assumptions at the same time**: we have 3 groups of assumptions, namely Assumptions 1-3, 2-5 and 6-7, which are used respectively in Theorems 2.4, 3.1 and 3.2. 

In our replies below, we provide extra references when needed at the end of each reply. Other references are the same as in our paper.

**References:**

Anahtarci, Berkay, Can Deha Kariksiz, and Naci Saldi. "Q-learning in regularized mean-field games." Dynamic Games and Applications 13.1 (2023): 89-117.

Cosso, Andrea, and Huyên Pham. "Zero-sum stochastic differential games of generalized McKean–Vlasov type." Journal de Mathématiques Pures et Appliquées 129 (2019): 180-212.

Daskalakis, Constantinos, Noah Golowich, and Kaiqing Zhang. "The complexity of markov equilibrium in stochastic games." In The Thirty Sixth Annual Conference on Learning Theory, pp. 4180-4234. PMLR, 2023.

Guan, Yue, Mohammad Afshari, and Panagiotis Tsiotras. "Zero-Sum Games between Mean-Field Teams: Reachability-Based Analysis under Mean-Field Sharing." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 9. 2024.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper explores reinforcement learning methods for mean-field type games (MFTGs), a setting where cooperative agents within coalitions compete non-cooperatively against other coalitions. The authors propose a Nash Q-learning algorithm with theoretical guarantees and a deep RL-based algorithm which appears to perform favorably. 

A major concern that persisted throughout the discussion is that the paper’s contributions were seen as incremental relative to prior work.

In the words of Reviewer 34g4, “the novelty remains unclear” and that the work is “more of a combination of existing concepts and methods for a mean field type game, rather than making fundamental contributions.” Reviewer iiZW agreed (“the model and NashQ-based analysis are not highly novel”)

While the authors clarified that MFTGs differ significantly from MFGs and MFC, some reviewers remained unconvinced.

Reviewer iiZW, while positive on the paper, mentioned that the "The work fuses existing ideas from MFGs with algorithms from both game theory and deep RL". This gave credence to the fact that---while MFTGs are different from MFGs---the paper might be an application of well-understood ideas. I asked the negative reviewers to please comment on whether the authors' response had changed their mind after the discussion, but they mentioned being still convinced the paper was just lacking in novelty.

Lack of novelty per se need not be an insurmountable barrier: papers do not need to invent the wheel to be useful. So, the next question that was assessed was whether the problem tackles an important setting. Reviewer iiZW seemed the only to touch on this. While overall appreciative of the paper, they mentioned that "the setting sounds a bit niche to me. I wonder if one could discuss more the significance of the setting [..]".  So, unfortunately, this is not useful in dismissing the incrementality worry of the negative reviewers.

Overall, my impression is that the above concern with incrementality is the only real issue of the contribution (a concern of perceived disconnect between the theoretical results and experiments, by Reviewer ijet, was dismissed in the decision as not substantive enough).

I think the paper would benefit from addressing the above by clarifying the technical novelty.