Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximation
mean field game;linear function approximation;stochastic semi-gradient descent
Yes
No ethics review needed.
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?
* 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.
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.
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.
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
- 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?
- 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.
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.
- 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.
Yes
No ethics review needed.
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?
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.
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.
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
@inproceedings{
anonymous2024stochastic,
title={Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximation},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=tfO07iz0b9},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
mean field game linear function approximation stochastic semi-gradient descent
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/d0a7c11b0ff952fd57c8232daf34e202f22b32b4.pdf
other topics in machine learning (i.e., none of the above)
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/483acac0260b4f0d6c90c267cb87b9c7a578e2b1.zip
Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximation
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission