Last Iterate Convergence in Monotone Mean Field Games

Thank you for your careful review and for your interest in our convergence guarantees for MFGs. We address your comments below.

Minor things: I think [1] is also relevant to add to Table 1, as it has discrete-time convergence results for MFGs (under concavity assumptions) Typo line 671: “for Here”

Thank you for pointing these out. We will add [1] to Table 1 and correct the typo in the revision.

Where does Figure 1 come from? Is it from the experiment further below?

It is mentioned briefly in line 169. Figure 1 illustrates our experiments showing that Regularized Mirror Descent converges exponentially in practice.

how does Lemma E.7 provide the upper bound of exploitability? Can this be made more formal? The convergence result in Thm. 4.4 given in $D_{\mu^\ast}$, how does this imply exponential convergence in a standard metric for the policy, or in exploitability?

Thank you for this request. We shall explain how to get the bound in detail. From Lemma E.7 and the identity $J(\mu,\pi)=\mathbb{E}\_{s\sim\mu\_1}[V_1(s,\mu,\pi)]$, we can bound $\operatorname{Exploit}(\pi^t)\le J(m[\varpi^\ast],\pi_{\textup{BR}}^t)-J(m[\varpi^\ast],\pi^t)+\mathcal{O}(\\|m[\varpi^\ast]-m[\pi^t]\\|),$ where $\pi^t_{\textup{BR}}$ is a maximizer of $J(m[\pi^t],\cdot)$.

Furthermore, by the definition of equilibrium, $J(m[\varpi^\ast],\pi_{\textup{BR}}^t)\le J(m[\varpi^\ast],\varpi^\ast)$, so applying Lemma E.7 again yields $\operatorname{Exploit}(\pi^t)=\mathcal{O}(\\|m[\varpi^\ast]-m[\pi^t]\\|+\sum_h\mathbb{E}\_{s\sim\mu_1}[\\|\varpi^\ast_h(s)-\pi^t_h(s)\\|]).$

Finally, using Pinsker’s inequality and Lemma E.6 (l.631), we obtain $\operatorname{Exploit}(\pi^t)=\mathcal{O}(\sqrt{D_{\mu^\ast}(\varpi^\ast,\pi^t)}).$

Why is (3.1) called intractable? If it is just a regularized MFG, can you not solve it using any regularized MFG algorithm?

“Intractable” here means that finding the pair $(\sigma^{k+1},\pi^{k+1})$ in equation (3.1) exactly is difficult. Most regularized MFG algorithms—including RMD—can only compute this pair approximately. While one could solve a linear program to obtain an exact solution, doing so is not generally scalable. Note that RMD and APP are scalable methods when combined with function approximation.

Thank you for reviewing our paper. We appreciate the opportunity to clarify several points where our exposition may have fallen short regarding our setting and its differences from other works. Below, we explain the position of our paper in this context.

How do the "optimization-based methods for MFGs" (e.g., Guo et al. 2024) that achieve local convergence without monotonicity compare in practical utility to the "global" convergence results achieved here with monotonicity?

Local‑convergence guaranteed methods require the initial policy $\pi^0$ to be sufficiently close to an equilibrium—a condition that cannot be verified a priori—and impose no structural assumptions on the MFG. By contrast, our “global” convergence guarantees require only monotonicity and full support of $\pi^0$, which can be checked before running the algorithm, to ensure convergence of PP and RMD.

In addition, Online Mirror descent-based methods, including RMD, can be scaled to large MFGs using function approximation with deep learning, but "optimization-based methods for MFGs “ would be difficult to scale in a similar way.

The assumption of ergodicity is too strong. Zaman et al. 2023, for example, establish results under weaker class of communicating MDPs. How would the results presented in the paper generalize to such MDPs?

We do not assume the ergodicity (i.e., that any state is reachable from every other state under some policy). Instead, Assumption 2.1 requires only that any state be reachable from some states under any policy. This condition also subsumes the communicating‑MDP setting of Zaman et al. (2023).

The assumption of mean-field independent MDP is also strong for MFGs (Zaman et al. 2023, Zeng et al. 2024, etc.) consider the case where $P$ depends on $\mu$. How easy is it to relax this assumption in the paper?

First, Zaman et al. and Zeng et al. impose different conditions on the transition dynamics, such as the contraction assumption (Assumption 1 in Zaman et al.) and the herding condition (Assumption 4 in Zeng et al.), which differ from our monotonicity assumption. Still, neither is strictly stronger than the other. Monotonicity corresponds to convexity in optimization and arises naturally in applications like congestion modeling, whereas a contraction assumption is comparatively strong and imposed purely for theoretical convergence. The herding condition is used where the uniqueness of the equilibrium need not always hold; under our non‑strict monotonicity assumption, the uniqueness of the (unregularized) equilibrium also does not generally follow.

Extending convergence of MD‑based algorithms to mean‑field dependent transitions would require fundamentally different proof techniques—for example, one would need an alternative to Lemma E.4 implicitly used in Perolat et al. (2022) and F. Zhang et al. (2023).

Can the authors elaborate why the initial policy $\pi^0$ should have full support in Prop. C.1?

Full support was not required in Proposition C.1—this result does not depend on $\pi^0.$ We will write this point more clearly in the revision.

Thank you for your feedback. First, we apologize for a typo in Line 71 of the Contributions box. It should read Theorem 3.1 and Theorem 4.3 (not 4.3 and 4.4). We answer the following comment and question:

My main concern is that the exponential convergence rate is not new to regularized games (see Cen et al 2023, Zhang et al 2023, Dong et al 2025). To my knowledge, these papers also use a proximal point-like algorithm. To my knowledge, these papers also use a proximal point-like algorithm.

The exponential convergence is a novel result for the regularized Mean-Field Game. Cen et al.'s result is not for MFG, and Zhang et al. Dong et al. only achieve polynomial rates. The methods in these previous studies are results for policy gradient and mirror descent, which are different from our proximal point-type algorithm (3.1).

Could you explain the technical novelty of the analysis? It seems like the improvement over Zhang et al is on the non-strict monotonicity assumption. But Dong et al’s results are also under non-strict monotonicity.

First, we would like to emphasize that our key technical novelty is not only the last-iterate convergence (LIC) for regularized MFGs, but also the LIC result for unregularized MFGs (Theorem 3.1). To our knowledge, this is the first guarantee of LIC in the unregularized setting. Under unregularized dynamics, no prior work has established LIC. Furthermore, our LIC result for the regularized problem (Theorem 4.3) strictly improves upon Zhang et al.'s and Dong's full-feedback analyses by establishing an asymptotically faster convergence rate under non-strict monotonicity. The key to establishing these two theoretical contributions is correctly evaluating the change in $\mu$. In Theorem 3.1, we were able to neglect $\mu^{k+1}$ of $D_{\mu^{k+1}}$ using Łojasiewicz's inequality; in the proof of Theorem 4.6, we evaluate the dependence of Q-function on $\mu^{t}$ by $D_{\mu^\ast}(\varpi^\ast,\pi^t)$ using the KL divergence property. See Remark 3.3 and 4.6 for details.

Could the poly→exp improvement on the convergence rate be attributed to different feedback types as Dong et al focused on bandit feedback?

No—Zhang et al.’s convergence rate remains polynomial even under full feedback, whereas our analysis yields a strictly faster (exponential-phase) rate under full feedback. Moreover, their bandit-feedback results build directly on their full-feedback polynomial convergence (Theorem 5.1), so they only achieve a polynomial rate in the bandit setting. Therefore, using our exponential-rate guarantee as a foundation, one can expect improved convergence rates under bandit feedback. Although extending our contraction-based analysis to the bandit setting is non-trivial, we believe our techniques could be used to derive stronger polynomial (or even exponential-phase) rates for bandit-feedback algorithms in MFGs, and we plan to explore this in future work.

Thank you for reviewing our work. We respond to your questions below.

What is the primary theoretical obstacle to deriving a convergence guarantee for the combined APP algorithm?

In our current analysis of the inner RMD iterations, the allowable step size $\eta^\ast$ must shrink towards zero as $\sigma_{\textup{min}}$ becomes small. Indeed, an equilibrium of the MFG $\pi^\star$ may assign zero probability to some actions, so $\pi^\star_{\textup{min}}=0$. Hence, any convergent APP would drive some $\sigma^k_{\textup{min}}\to 0$, leaving no positive $\eta^\ast$ that satisfies our bounds. Overcoming this requires new techniques to handle vanishing regularization mass.

How does the approximation error from using a finite $\tau$ affect the stability and convergence of the outer PP loop?

A precise theoretical bound is challenging, but the outer loop remains stable in experiments even for $\tau\approx5$. However, when the contraction factor $(1-\lambda\eta)$ is close to 1, a small $\tau$ can lead to instability in the outer PP loop. We will note this trade-off in the revision.

Could you provide more intuition on how the use of the Łojasiewicz inequality (for the PP proof) and the detailed value function analysis (for the RMD proof) were tailored to overcome this specific challenge?

Mean-field games are challenging because, even if the policy $\pi$ acts optimally, the mean field $\mu$ merely follows passively and does not itself move optimally towards $\mu^\star$. Our key innovation is to track only the policy updates: the Łojasiewicz inequality quantifies how changes in only $\pi^t$ affect the cumulative reward $J$, allowing us to avoid explicit tracking of $\mu^t$.

Could the authors discuss how the RMD differentiates from that in zero-sum game (see e.g. [1] [2]).

In zero-sum games, both players’ policies receive explicit regularization terms. By contrast, in an MFG, only the single-agent policy $\pi$ is directly regularized, and the mean field $\mu$ does not appear under the KL term. This asymmetry leads to a single-player fixed-point rather than a saddle-point structure.

Moreover, if the feedbacks are potentially delayed or asynchronous, could the authors give intuition on how to adapt the algorithms non-trivially in these scenarios (see e.g. [3])?

Conceptually, one can adapt RMD to delayed feedback by evaluating the Q-function $Q_h^{\lambda,\sigma}(s,a,\pi^t,\mu^t)$ at a delayed index $\kappa^{(t)}$, i.e. $Q_h^{\lambda,\sigma}(s,a,\pi^{\kappa^{(t)}},\mu^{\kappa^{(t)}})$. For asynchronous updates one might let $\kappa^{(t)}$ depend on the current $\mu$, but the precise feedback model would need to be specified. We will add a brief discussion of this in the revision.

How should one select the regularization parameter $\lambda$ and the number of inner iterations $\tau$ in practice? The parameter $\lambda$ controls the gap between the regularized and unregularized equilibria, while $\tau$ controls the accuracy of the PP update.

In practice, one should choose $\lambda<1$ as large as possible—so that the inner loop remains small—while reducing $\eta$ to maintain convergence as to satisfy (D.5). This choice allows a small number of inner iterations $\tau$ while keeping the outer loop stable.

Is there a theoretical relationship between these parameters that would guarantee convergence for the overall APP algorithm?

Due to the abovementioned obstacle, we have no theoretical guarantee linking $\lambda$, $\tau$, and $\eta$ for the complete APP algorithm. Techniques in monotone games [Theorem 5.8, Abe et al. 2024] might yield such parameter relationships; we leave this to future work.

Thank you very much for your comments. We are happy to hear that our rebuttal helped clarify some points about our work. In the revised manuscript, we will expand the discussion to clearly distinguish the asymmetric regularization in mean-field games from the symmetric structure of zero-sum games.

Thank you for your careful review and your interest in convergence guarantees for MFGs. We are happy to address your comments below. First, we will add a reply to your comment in the Weakness section.

it is difficult to compare it with the sublinear rate of Zhang et al. 2023.

First, Zhang et al. only show convergence of averages over iterations of policy $\pi^t$, whereas we prove convergence of $\pi^t$ itself (last-iterate convergence; LIC). RMDs exhibit exponentially LIC, and our results align with this phenomenon.

Let us compare our LIC results with the averaged convergence results of Zhang et al., at least in the asymptotic regime of sufficiently large $t$. Our exponential rate is tighter than the sublinear bound of Zhang et al. 2023. In contrast, as you know, Zhang et al.’s bound for finite $t$ may be numerically smaller since the constant inside our exponent could be pretty small. We will add a remark on this trade‑off in the revised manuscript.

Looking at the work due to Zhang et al. 2023, it seems that the strict monotonicity assumption is not required for the convergence analysis, but rather for the uniqueness of the regularised equilibrium. Does Theorem 4.3 not also implicitly assume that there exists a unique equilibrium given by $\bar{\omega}^*$?

Your observation is correct. Our key technical step to remove the strictness of monotonicity is that non‑strict monotonicity guarantees the uniqueness of the KL‑regularized equilibrium. Therefore, in Theorem 4.3, uniqueness is not an extra assumption but a derived conclusion. Compared to Zhang et al. (2023), we emphasize that Zhang’s convergence analysis is carried out only under the entropy regularization on the MFG—a far stronger condition than non‑strict monotonicity alone. They do not obtain any last‑iterate convergence guarantee in the absence of regularization. By contrast, our Theorem 3.1 establishes last‑iterate convergence for the unregularized MFG under only non‑strict monotonicity.

We will next give you an answer to your questions.

Could assumption 2.3 also be generalized to the case where the reward function $r$ depends on the mean‑field flow over states and actions? That is, when $\mu_h^\pi(s,a)$ is the population flow on states and actions induced by policy $\pi$. In some MFGs, the population’s actions distribution is also significant.

Conceptually, such a generalization appears feasible but depends on the exact formulation. We consider that your suggestion of replacing $\mu_h(s)$ by $\mu_h(s, a)$ requires redefining the population flow in equation (2.1), which effectively changes the entire MFG setup. We believe that our convergence arguments would extend without significant changes with an MDP-style redefinition, but we have not yet formalized this. We will include a discussion of this extension in the revision.

Could the analysis directly incorporate the ODE up to a discretization error? To what extent does the analysis differ from standard ODE discretization methods used in optimization literature?

Yes, we could go up through equation (4.6). We follow an ODE‑style argument (akin to Theorem 4.4). The novel part of our proof of Theorem 4.3 lies in bounding the discretization error (see the “blue box” in (4.6)).

The paper comes quite close to deriving a rate for the unregularized problem via APP and the RMD convergence. What is the main bottleneck that prevents merging the results to obtain a novel convergence result?

As you note, the main bottleneck is that $\sigma_{\textup{min}}$ may tend to zero, which forces the allowable step size $\eta^\ast$ to zero. Indeed, an MFG equilibrium $\pi^\ast$ can assign zero probability to some actions, so $\pi^\ast_{\textup{min}}(a\mid s)=0$. Hence, if APP converges, some $\sigma^k(s)$ would converge to zero, and no positive $\eta^\ast$ would satisfy our current analysis. Overcoming this requires new ideas to handle vanishing mass.

What are the major bottlenecks when generalizing the results to graphon MFGs?

We do not anticipate significant difficulties here. Our problem setting for the convergence analysis does not conflict with the graphon generalisation as discussed in the literature. Therefore, it can be applied to graphon MFGs without introducing any new technical hurdles.. Accordingly, our results should extend naturally to graphon MFGs, albeit with more cumbersome notation.