Reinforcement Learning for Finite Space Mean-Field Type Games

We are grateful for your comments and interesting questions, and we thank you for the positive assessment of our work. We provide detailed answers to your questions below. We will also include all the changes in the revised PDF.

Weakness: Thank you for pointing out the typos and suggesting changes. We will correct all these points in the revised paper.

• Reference: Thank you and sorry for mixing up the references.
• Superscripts: We used the superscript $N_1,N_2,...,N_m$ to emphasize that the number of agents in each coalition might be different. But we agree with your suggestion to make the notation more concise. We will use it in the revised PDF.
• Assumption 3: thank you, we corrected the typo.
• Font size in figures: thank you, we will increase the font size in the revised version.
• Figure reference: Sorry for the typo. The figure referenced in Line 478 should be Figure 11, which contains the testing rewards. We moved it to the Appendix due to space limit and because there are 4 populations in this example.
• The figure mentioned in line 481 is Figure 5. We apologize for the confusion. 
• Captions: Thank you for the suggestions, we will improve the captions in the revised version.

Question 1 (Theorem 2.4 and discount): Thank you for your question. Besides the information provided in point (3) of the common reply, we would like to clarify that:

• The condition $\gamma(1+L_\pi+L_p)<1$ involves $\gamma$ because we consider the infinite horizon setting and it helps to control the propagation of errors in future time steps and give a rate of convergence.
• If $\pi$ and $p$ do not depend on the mean field, i.e., $L_\pi=L_p=0$, this condition reduces to $\gamma<1$ which is standard in MDPs.
• Other works often use similar conditions. For example Saldi et al. (2018) (for MFGs and not MFTGs) also have a restrictive condition on the discount factor ($\beta$ in their notation), namely assumption (g) on page 4261 requires $\alpha\beta\gamma < 1,$ with $\alpha$ and $\gamma$ defined on the same page. Their $\gamma$ is greater than $1$ and $\alpha$ would probably be larger than $1$ too in some cases (e.g., if the transition kernel $p$ gives more mass to regions where $w$ is large). In that case, $\alpha\gamma$ can be much larger than $1$, hence requiring the discount $\beta$ to be much smaller than $1$. Furthermore, Saldi et al. also have conditions on the moduli of continuity $w_p(r)$ and $w_c(r)$ of the transitions and the cost (see assumption (h) on page 4262 in their paper). While it is true that this is slightly less restrictive than Lischitz continuity, their Theorem 4.1 only provides an asymptotic convergence and no convergence rate.

Question 2 (Example 1 and competition): Thank you for this interesting question. We agree and since we got the reviews, we conducted new experiments with a more complex model for Example 1, in which we introduced a cross-population density term in coalition 1's reward function while keeping coalition 2's setting unchanged. With this modification, coalition 1 will learn to avoid coalition 2 while trying to maintain its position, whereas Coalition 2's objective is to catch coalition 1. In the notation of our paper, the reward function for coalition 1 is modified to include a term $-c_{2}(\bar{s}^{1} \times \bar{s}^{2})$ while for coalition 2, we keep the same reward. We observe numerically that the average exploitability of the baseline is above 1000 while the exploitability of our method is below 500. We will include the new setting and the new figures in the revised PDF.

Question 3 (Scalability in number of coalitions): Increasing the number of coalitions is an interesting direction. In this work, we are mostly focused on settings with a relatively small number of coalitions. In Example 4, we have 4 coalitions and we solved it without using very large computing resources (a single RTX 8000 GPU) and we believe it should be possible to solve similar problems with more coalitions (e.g., of the order of 10 coalitions). When the number of coalitions is very large (e.g., hundreds or thousands), it is probably unrealistic to solve exactly the MFTG and we would recommend using other approximations. For instance, one could have a mean field of mean field coalitions, and the algorithm would learn the behavior of one typical agent in one typical coalition. Such models seem similar to graphon-based models (Caines & Huang, 2019) and mean field control games (Angiuli et al., 2022). However such approaches are relevant only for very large number of coalitions. In the regime with small or moderate number of coalitions, we still believe that our approach is more precise and practical. We will add comments about this in the revision.

We thank you for all the comments. We hope that our answers below will answer your questions adequately and convince your of the merits of our paper. We would be grateful if you would consider raising your score.

Weakness 1 (empirical evidence): Thank you for your question. Although the curves sometimes look close, the values actually show a clear improvement: our method brings an improvement of at least 30% in each example. We summarize the relative improvement in the table below, where:

• Baseline Exploitability: The baseline's mean value (as described in the paper).
• Our Exploitability: Our method's mean value (as described in the paper).
• Improvement: The percentage improvement is calculated as: $$\text{Improvement (percentage)} = \frac{\text{Baseline} - \text{Ours}}{\text{Baseline}} \times 100$$

We will include this table in the revision.

Weakness 2 (setting and "coalitions"): "I believe the referenced works [...] refer to standard MFGs as mean-field-type games." We respectfully disagree:

• What Tembine et al. call a mean-field-type game is not standard MFGs. For example in (Tembine, 2017), the author wrote on page 706-707 "In contrast to mean-field games [2, 3] in which a single player does not influence of the mean-field terms, here, it is totally different. In mean-field-type games, a single player may have a strong impact on the mean-field terms." Actually this is one of the major challenges that we tackle in our work and which justifies using population-dependent policies.
• Furthermore, on page 707, "Mean-field-type games with two or more players can be seen as the multi-agent generalization of the single agent mean-field-type control problem." And mean-field-type control problems can be interpreted as a cooperative game with players who try to jointly minimize a cost (or maximize a reward). This is what we call a "coalition".
• The way we use "coalition" might be different from other authors and we are open to using a different word if you have suggestions. But we hope that you now agree with the interpretation and the distinction with MFGs.

Weakness 3 (assumptions and applicability): Though there are 8 assumptions in our paper, they are for different theorems, please see point (3) in our common reply. We want to add that:

• Assumptions 1-3 are used only in Theorem 2.4 and are common in MFG/MFC literature.
• The Assumption on $\gamma$ in Theorem 2.4 is used to obtain a rate of convergence (see also point (3) in the common reply).
• Assumptions 4-6 are used in Theorem 3.1 and are classical conditions for the convergence of the Nash Q-learning algorithm. See Hu & Wellman (2003) and Yang et al. (2018).
• Assumptions 7-8 (Lipschitz continuity for the mean-field functions) are used in Theorem 3.2. These conditions are used to derive a rate of convergence of the error between the discretized MFTG and its original continuous version.

Weakness 4 (Nash-Q analysis): Thank you but it should be noted that our contribution is not the convergence of Nash Q-learning for the discretized problem but the analysis of the Q-function discretization error, which was not at all discussed in the paper of Hu and Wellman because they focused on discrete spaces. In line 353, we wrote: "We omit the proof of Theorem 3.1 as it is essentially the same as in (Hu & Wellman, 2003). We then focus on the difference between the approximated Nash Q-function [...] and the true Nash Q-function". The second result (Theorem 3.2) is our main contribution in this direction. With Theorem 3.1, they give the full picture of convergence of Nash Q-learning for MFTG.

Weakness 5 (graphon games): Thank you for pointing this out. We will include this reference and clarify the connection. However, there is one important difference: when the number of coalitions is finite, each coalition's actions have a non-negligible influence on each of the other coalitions (as in a finite-player game). This is why we consider policies that take as input the population distributions, which are high-dimensional continuous vectors. It is a crucial difference with graphon games, in which the number of coalitions is very large (or, in the limit, infinite), so that one can consider decentralized policies (i.e., policies which depend only on the individual agent's state). In that case, the policy's input is low-dimensional and value functions are easier to approximate.

Quick, note my apologies, the references I mentioned in my review were:

[1] Jusup, Matej, et al. "Safe model-based multi-agent mean-field reinforcement learning." arXiv preprint arXiv:2306.17052 (2023).

[2] Bordelon, Blake, and Cengiz Pehlevan. "Dynamics of finite width kernel and prediction fluctuations in mean field neural networks." Advances in Neural Information Processing Systems 36 (2024).

Thank you for taking the time to reply. We still want to answer point by point, in case you, other reviewers or the Area Chair find these answers useful.

Minor Point 1: The argument that MFTG is very different from MFG and MFMDP is standard in the literature on this topic. We tried our best to convince you, including by citing other works (e.g., by Tembine). Given the page limit, we cannot reproduce in our own paper the whole literature. The readers who want to know more are supposed to refer to the references we cited.

Minor Point 2 (Figure 1): We are sorry but you are mistaken. We did not plot the exploitability of player 2. So there is no basis to say that "the exploitability of player 2 appears constant". Please check again the figure: We plotted the average exploitabilities for each method (second to the left), and for our method it goes towards 0. You might have mistaken the rewards (left plot) for the exploitabilities. But even so, the reward of player 2 is not constant (while the reward of player 1 converges well), so we cannot understand what you meant. Also, we have explained the correspondence between "coalition" and "(central) player" e.g., in lines 101-102.

Minor Point 3 (NE): Here again, we are sorry but the expression "proving NE" alone does not make sense. Maybe you forgot one word? Please note that we have proved convergence of our Nash Q-learning algorithm to an approximate NE (see our Theorems 3.1 and 3.2). This answers your question. Furthermore, we are not sure what you mean by "very minimal evidence to support this". What does "this" refer to? As we have pointed out, MFTGs are different from MFGs. We have provided several references to motivate MFTGs and our Theorem 2.4 shows that MFTGs are a valuable approximation for applications to finite-player problems, which arise in practice.

Major Point (DDPG) We would like to react to your comment "theoretical convergence results for DDPG lies outside the scope of this paper". According to Google Scholar, the DDPG paper [Lillicrap et al., 2016] is cited more than 17000 times. To the best of our knowledge a proof of convergence is still lacking, and the recent paper [Xiong et al., 2022] (see our earlier response) also mentions this. The same goes for many deep RL algorithms, which lack rigorous and generic proofs of convergence. Your comment seems to imply that all these works should be rejected. We disagree.

We are grateful for your comments. It seems that there are some confusions about what our paper is doing. We hope that our answers below will convince you that our paper deserves a better score. If you would like more details, could you please provide specific references?

Weakness (Novelty): Thank you for giving us the opportunity to clarify this point:

1. "incremental to the existing learning methods used for MFG.": As explained in point (1) of the common reply, MFTG and MFG are very different. We propose the first DRL algorithm for MFTG. If you believe that an existing algorithm of the MFG literature can be applied to MFTG, could you please provide a specific reference? We will be glad to provide more explanations.
2. "Reformulation with mean field MDPs is not new either.": While MFMDPs are not new (we mentioned this on line 196), previous works only considered a single MFMDP while we study a game between MFMDP players. Please also check point (2) in our common reply. If this is not clear, please let us know.
3. "Combination of existing methods and concepts": We respectfully disagree with the reviewer: in our paper, we clearly cite prior work but we go beyond these works to solve a new type of problems. As far as we know, there are no existing methods to solve MFTGs like the ones we solve.

Question 1 (finite space/DRL): "why a finite space algorithm needs be to presented first in Sec. 3 while having a DRL for Sec. 4":

• In an MFTG, the central player of each coalition has a value function and a policy. As explained in Section 2.4 (see in particular line 229), these are functions of the population distributions, which are represented as vectors (of dimension the number of possible states). So the value functions we want to compute are naturally taking high-dimensional, continuous inputs. This is why we decided to employ DRL.
• As explained on page 8 of our initial submission the main advantage of this method compared with tabular RL "is that it does not require discretizing the simplexes. The state and action distributions are represented as vectors (containing the probability mass functions) and passed as inputs to neural networks for the policies and the value function".
• Please note that this actually a key difference with RL for MFGs, which usually focuses on decentralized value functions and policies that are functions of the individual state only and not functions of population distribution (see e.g. the references on line 60 of our paper: Subramanian & Mahajan, 2019; Guo et al., 2019; Elie et al., 2020; Cui & Koeppl, 2021). In that case, tabular methods can be used when the state space is finite. This does not hold true in our case due to the presence of the mean-field as an input: even when the state space is finite, the mean field input is continuous.

Question 2 (difference with MFG): "Using DRL for learning MFGs with large state and action spaces is widely used and well developed in MFG":

• First, we are solving MFTGs and not MFGs. Please see our answers to the above Weakness and Question 1.
• Second, as far as we know, there are only a few papers on DRL for MFGs and they are usually restricted to very specific settings. In any case, these papers would not help to solve our MFTGs.
• We hope that our answers help clarifying these points. But if you would like further clarifications, please provide specific references of DRL for MFGs so we can explain why these methods do not jeopardize our work.

We would like to thank again the reviewers for all their work and detailed comments, which greatly helped improve the quality of the paper. We have uploaded a revised version of the PDF. We hope that this new version will convince the reviewers to increase their score. If there are still questions or confusions, we will be glad to answer any follow-up questions.

For convenience, we have highlighted the main changes in blue in the revised text. Furthermore, we summarized below the main changes:

• Section 1:
  • Corrected the initial MFG references (Lasry & Lions, 2007; Huang et al. 2006).
  • Added references to graphon games and mixed mean field control games, with infinitely many mean-field groups, and explained why methods for such games cannot be used for MFTGs.
• Section 2:
  • Section 2.1 (and following): Changed $N_1,\dots,N_m$ to $\bar{N}$ in the superscripts for the populations.
  • Section 2.2: Corrected typo in the former Assumption 3. We have also provided references for former Assumptions 1-3 (new Assumption 1).
  • Assumptions: Regrouped respectively Assumptions 1-3, 4-6 and 7-8 as the new Assumptions 1, 2 and 3. They are used for different purposes so we do not need all of them at the same time.
  • Section 2.2: Added a comment about a comparison with (Saldi et al., 2018) to explain that we provide a rate of convergence and not just asymptotic convergence (which justifies our assumptions are slightly stronger).
  • Section 2.3: Clarified that we study games between MFMDPs and not simple MFMDPs.
• Section 3: Clarified the connection between our assumptions and existing assumptions or results in the literature.
• Section 4: Clarified the two advantages of the DRL algorithm over Nash Q-learning: no need to discretization of the simplexes and no need to solve any stage-game.
• Section 5:
  • Modified the reward function of Example 1 (line 435 and then lines 1369 to 1371) to include bi-directional interactions between the two populations. Replotted Figures 1 and 2 with the new results (we still observe that our method does better than the baseline).
  • Enlarged font size of most figures to make them easier to read.
  • Merged the captions of side-by-side figures for better formatting and better space usage.
  • Added more information in the captions (rewards and exploitabilities are averaged and colorbars are for densities).
  • Corrected figure references.
• Section 6:
  • Added a paragraph on related works.
  • Clarified the reproducibility statement to show that we have included a large amount of details in the appendices.

To accommodate for these changes, we had to make minor adjustments to how some of the equations are displayed but we hope the reviewers will understand that we tried to our best to take their comments into consideration while respecting the page limit.