Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximation

Authors: Chenyu Zhang, Xu Chen, Xuan Di
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: mean field game, linear function approximation, stochastic semi-gradient descent

Abstract:
Mean field games (MFGs) model interactions in large-population multi-agent systems through population distributions. Traditional learning methods for MFGs are based on fixed-point iteration (FPI), where policy updates and induced population distributions are computed separately and sequentially. However, FPI-type methods may suffer from inefficiency and instability due to potential oscillations caused by this forward-backward procedure. In this work, we propose a novel perspective that treats the policy and population as a unified parameter controlling the game dynamics. By applying stochastic parameter approximation to this unified parameter, we develop SemiSGD, a simple stochastic gradient descent (SGD)-type method, where an agent updates its policy and population estimates simultaneously and fully asynchronously. Building on this perspective, we further apply linear function approximation (LFA) to the unified parameter, resulting in the first population-aware LFA (PA-LFA) for learning MFGs on continuous state-action spaces. A comprehensive finite-time convergence analysis is provided for SemiSGD with PA-LFA, including its convergence to the equilibrium for linear MFGs—a class of MFGs with a linear structure concerning the population—under the standard contractivity condition, and to a neighborhood of the equilibrium under a more practical condition. We also characterize the approximation error for non-linear MFGs. We validate our theoretical findings with six experiments on three MFGs.

Decision: accept (poster)
Reviewer scores: 5, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1729522742265

thread_type:
official_review

<thread_object>
creator: reviewer_b4eq

<content>
summary:
This paper studies learning equilibrium policy in mean-field game. The authors propose semiSGD, a SGD style online algorithm, where they treat the policy and population as a unified parameter. For linear MFGs, under small Lipschitz factor case, they establish convergence analysis. Besides, when the Lipschitz factor of the problem is relative large, they show the algorithm converges to the neighborhood of Nash, whose radius scales with the Lipschitz factors.

strengths:
It seems interesting to me the idea that considers the policy and population parameters as a unified parameter to optimize.

The assumptions are clearly stated, and some explanations are provided. 

Numerical experiments are provided.

The comparison in Table 2 provides a good summary.

weaknesses:
1. **About assumptions**: I think the authors should provide some justification about why it is reasonable to consider Assumption 2. In the more standard MFG setting, the equilibrium policy is defined to be the policy that no agent can deviate and increase its value, which correspond to the setting $\Gamma_\pi(Q)(\cdot|s) := \arg\max_a Q(s,a)$. However, Assumption 2 can not cover this setting with finite $L_\pi$, because of the discountinuity of the argmax operator.

    As implied by Assumption 2, the paper seems to consider a "smooth" version of standard Nash equilibrium. It is unclear that why this objective is of interests to study, and also what's the relationship between it and the standard Nash equilibrium.

2. **Comparison with Assumptions in previous work**: this paper consider contraction style assumptions to establish the convergence. Although in remark 2, the authors provide some discussion to justify the assumptions, it is still unclear to me how they compare with previous works. For example, does the contractivity assumption in [1] can be recovered as a special case by choosing some specific parameters in Assumption 2 and 4? Or maybe comparing with [2], which ensures contractivity by introducing the regularization, would Assumption 2 or 4 be satisfied by introducing large enough regularization?

3. **When Theorem 2 is meaningful?** Theorem 2 suggests the convergence with bounded bias. I think it is necessary to have some discussion about the magnitude of the bias term comparing with another algorithm randomly compute $\xi_T$. For instance, can you provide some examples when the bias term can be (much) lower than $\|\xi^*\|$, which suggests the algorithm is better than a random guess by directly assigning $\xi_T = 0$.

    It is also unclear how large $\bar{w}$ is. Given that $\bar{w}$ is a problem-dependent constant, can you explain when $\bar{w}$ can be large or small? That would be helpful to understand when Theorem 2 is meaningful and when it is vacuous.

[1] Guo et al., Learning mean-field games.

[2] Yardim et al., Policy mirror ascent for efficient and independent learning in mean field games

questions:
1. In Assumption 5, $w$ is introduced to denote the upper bound of $\bar{w}$. However, it does not appears in Theorem 2. So what's the reason to mention such an upper bound?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730489304079

thread_type:
official_review

<thread_object>
creator: reviewer_b6vh

<content>
summary:
The manuscript goes beyond existing fixed-point iteration (FPI) methods for solving mean field games, by treating the mean field and agent policy jointly instead of performing forward and backward updates. Here, FPI-type methods are understood as those computing the full forward and backward equations for mean field and optimal policies. The advantage is allowing asynchronous updates to both, which can lead to improved results. An analysis of the resulting semi-gradient descent method is performed under linear models and varying sets of assumptions. Empirically, the designed algorithms are further demonstrated on a variety of problems.

strengths:
- The paper is well written and relatively clear despite the subject matter. 
- The analysis is novel, interesting and extensive, e.g., the combination of linear approximations with MFGs and producing finite-time error bounds, or the convergence results without (directly) assuming contractivity or monotonicity.
- Empirically, the approach appears to be able to outperform existing approaches in some of the demonstrated problems in terms of exploitability. Further, the method is practical, as it is applicable in an online manner to unknown models. 
- The introduction of synchronous updates as opposed to forward-backward computations seems somewhat significant to the study of MFG learning algorithms, as it allows for improved sample complexity and better empirical results.

weaknesses:
- The approach seems to be limited to stationary mean field games, i.e. ones with time-stationary mean fields. This does not match with the compared / referenced literature, of which most are for non-stationary cases. 
- For the theoretical results, there remain limits in terms of significance, as also discussed by the authors. The significance of theoretical results is limited due to the requirement of strong assumptions such as linear models and regularized solutions.
- Some minor issues (incomplete / TeX errors) in references.
- Some points remained unclear to me, see questions below.

questions:
- Uniqueness of solutions seems to not be required. How it is possible that we obtain convergence in the presence of non-unique MFE? Does the theory imply convergence to multiple MFE, or is uniqueness implicitly assumed?
- What is the reasoning behind replacing $M_*$ (the non-unique? unknown MFE) by bootstrap estimates under the current policy (before Eq. (3))? Why can the current policy produce estimates for the mean field $M_*$ of the MFE?
- The methodology does not directly optimize exploitability, what is the difficulty in instead using "true" gradients on the unified parameters to minimize exploitability?
- Can you extend similar techniques to non-time-stationary MFGs?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730717633735

thread_type:
official_review

<thread_object>
creator: reviewer_vqq9

<content>
summary:
In this paper, a numerical method for mean field games is proposed. Mean field games games approximate Nash equilibria for games with many players. Here, the proposed method relies on stochastic semi-gradient updates. Theoretical convergence is proved and numerical illustrations are also given.

strengths:
The paper is relatively clear and the algorithm is new, to the best of my knowledge. The convergence analysis includes sample complexity. The experiments cover different examples and contain a few baselines.

weaknesses:
I understand that empirical convergence is observed beyond the assumptions, but still: it is not clear to me how to check these assumptions in practice.
In the numerical examples, the baselines could be explained more clearly.

questions:
Q1: Theorem 2: Please provide an example satisfying the assumptions of this theorem.

Q2: Section 7: Can you please explain what is FPI+MD? Is it the same as the online mirror descent of (Perolat et al., 2021)? If not, please compare with this algorithm, which is known to empirically converge much faster than fictitious play-type iterations.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730978992798

thread_type:
official_review

<thread_object>
creator: reviewer_bqaj

<content>
summary:
This paper primarily concentrates on the development of a stochastic gradient method for learning in mean-field games.
The proposed algorithm significantly reduces the computational cost associated with calculating the population distribution.
Moreover, the author demonstrates that under certain standard assumptions, the proposed algorithm converges to a stationary point.
Additionally, the algorithm's performance is validated experimentally in various mean-field games.

strengths:
* The problem is well-motivated. Eliminating the forward-backward process of learning algorithms for mean-field games is significantly important.
* The proposed algorithm has a strong convergence guarantee with a rate.

weaknesses:
My primary concern is that the definition of the mean-field equilibrium in this study differs from that in existing studies.
Specifically, this study considers the Bellman operator, as opposed to the commonly used Bellman optimality operator.
Hence, I believe that there is no guarantee for the agent to maximize the expected cumulative discounted reward in the mean field equilibria.
In the context of learning in multi-agent systems, it seems more natural to consider maximizing the expected cumulative discounted reward.
Consequently, I'm wondering why the current definition of equilibrium was considered in this study.
Is it possible to extend the provided theoretical results to the reward-maximizing setting?
If not, I don't think we can fairly compare this study with existing studies on mean-field games.

Additionally, I believe that a more detailed explanation of the numerical experiments is necessary.
For example, I'm curious why exploitability was reported for the flocking game, despite the fact that reward maximization is not the main focus of this study.

questions:
My main concerns and questions are outlined in Weaknesses.
Additionally, I have the following question:
* I am not sure how Assumption 5 is relatively weaker than Assumption 4. Could you provide a more intuitive explanation of Assumption 5?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731994032145

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We would like to thank the reviewers for their valuable and insightful comments on our work. We are happy with the overall positive feedback regarding
clarity of presentation (Reviewers `VqQ9` and `b6VH`),
significance of the problem considered in eliminating the forward-backward process (Reviewers `bQAJ` and `b6VH`),
novelty of the method in unifying the policy and population parameters and applying population-aware linear function approximation (Reviewers `VqQ9`, `b6VH`, and `B4eq`),
extensive analysis and strong finite-time convergence guarantees (Reviewers `bQAJ`, `VqQ9`, and `b6VH`),
and effectiveness of the proposed algorithm in practice (Reviewers `VqQ9`, `b6VH`, and `B4eq`).

We are also grateful for the suggestions for improvement. In what follows, we summarize our responses to each of the main comments. We also point out the revisions we have made to the paper in response to these comments.
The modifications are highlighted in **orange** in the revised manuscript.

- Reviewer `bQAJ`: We clarified that our definition of mean-field equilibrium (MFE) does indeed encompass the standard definition of MFE, and our theoretical results and numerical experiments do extend to the reward-maximizing setting. We have added a dedicated section, Appendix B.1, to elaborate on the definition of MFE and its relationship to existing works. We have also added a section in Appendix C.1 to provide detailed explanations of the baseline methods used in our numerical experiments.
- Reviewer `VqQ9`: We provided a detailed explanation of how to verify the assumptions in practice and offered an example satisfying the assumptions of Theorem 2. We have added a section in Appendix C.1 to provide detailed explanations of the baseline methods used in our numerical experiments.
- Reviewer `b6VH`: We clarified that our method, analysis, and experiments go beyond linear models and regularized solutions. We also discussed how our method can be generalized to non-stationary MFGs and how we might directly optimize exploitability. In the revised manuscript, we have added the analysis of MFE uniqueness implied by Assumption 4 or 5.
- Reviewer `B4eq`: We provided detailed discussions about Assumption 2, Theorem 2, and comparisons with assumptions in previous work. We have added a dedicated section (Appendix B.1) that justifies our definitions of MFE and policy operators, as well as their relationship to existing works.

We hope our responses and revisions address the comments raised. We would be happy to engage in further discussions if any queries remain.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper treats the problem of learning in mean-field games (MFGs) and, in particular, analyzes a stochastic approximation method dubbed SemiSGD (stochastic semi-gradient descent) in which agents simultaneously update their policy and population estimates. The authors provide a finite-time analysis for SemiSGD, and they establish its convergence to regularized mean-field equilibria (or neighobrhoods of mean-field equilibria).

The reviewers were mostly positive regarding the paper, and found it relatively well-written and topical. Two main concerns that were raised concern the following points:
- The authors' convergence analysis in Theorem 1 concerns the game's regularized MFE, with the degree of regularization being sufficient to ensure contraction (and, a fortiori, a unique regularized MFE). This reduces the relevance of this result (the authors stated in their rebuttal that they were transparent about this, but the writing is not sufficiently clear in this regard).
- It was also unclear how the authors' assumptions can be verified in practice - especially the delicate conditions involving $w$ and the eigenvalues of the various operators in Appendix H (which, incidentally, make the paper very hard to read at that point).

The authors provided very extensive replies to the reviewers' other questions, but the above concerns remained. While I remain concerned that these points impose considerable limitations on the authors' results (which are not adequately discussed in the paper), I believe the paper's merits outweigh its flaws, so I recommend acceptance.