Last Iterate Convergence in Monotone Mean Field Games
Authors: Noboru Isobe
Kenshi Abe
Kaito Ariu
Venue: NeurIPS 2025 poster ()
Keywords: mean-field game
learning in games
Primary area: theory
TL;DR: We prove convergence of an efficient method to solve unregularized MFGs under non-strict monotonicity.

Abstract: In the Lasry--Lions framework, Mean-Field Games (MFGs) model interactions among an infinite number of agents.
However, existing algorithms either require strict monotonicity or only guarantee the convergence of averaged iterates, as in Fictitious Play in continuous time.
We address this gap with the following theoretical result.
First, we prove that the last-iterated policy of a proximal-point (PP) update with KL regularization converges to an MFG equilibrium under non-strict monotonicity.
Second, we see that each PP update is equivalent to finding the equilibria of a KL-regularized MFG.
We then prove that this equilibrium can be found using mirror descent with an exponential last-iterate convergence rate.
Building on these insights, we propose the Approximate Proximal-Point ($\mathtt{APP}$) algorithm, which approximately implements the PP update via a small number of Mirror Descent steps.
Numerical experiments on standard benchmarks confirm that the $\mathtt{APP}$ algorithm reliably converges to the unregularized mean-field equilibrium without time-averaging.

Last Iterate Convergence in Monotone Mean Field Games
Noboru Isobe RIKEN AIP
Kenshi Abe
CyberAgent
Tokyo, Japan
Tokyo, Japan
noboru. www.eeriieeee..........
abe abb_.kenshhd@cyybaaatt.ccom co.
Kaito Ariu
CyberAgent
Tokyo, Japan
haito_ariuuccboraggtt.co .o.
Abstract
the Lasry-Lions framework, Mean-Field Games (MFGs) model interactions among infinite number of agents. However, existing algorithms either require strict monotonicity or only guarantee the convergence of averaged iterates, as in Fictitious Play in continuous time. We address this gap with the following theoretical result. First, we prove that the last-iterated policy of a proximal-point (PP) update with KI. regularization converges to equilibrium of MFG under non-strict monotonicity. Second, we see that each PP update is equivalent to finding the equilibria of KL-regularized MFG. We then prove that this equilibrium be found using Mirror Descent (MD) with an exponential last-iterate convergence rate. Building on these insights, we propose the Approximate Proximal-Point (APP) algorithm, which approximately implements the PP update via a small number of MD steps. Numerical experiments on standard benchmarks confirm that the APP algorithm reliably converges to the unregularized mean-fiel. field equilibrium without averaingg.
1 Introduction
Mean Field Games (MFGs) provide a simple and powerful framework for approximating the behavior of large populations of interacting agents. Formulated initially by Lasry and Lions (2007) and M. Huang et al. (2006), MFGs model the collective behavior of homogeneous agents in continuous time and state settings using partial differential equations (Cardaliaguet and Hadikhanloo 2017; Lavigne and Pfeiffer 2023; Inoue et al. 2023). The formulation of MFGs using Markov decision processes (MDPs) Bertsekas and Shreve (1978) and Puterman (1994) has enabled the study of discrete-time and discrete-state models (Gomes et al. 2010).
In this context, a player's policy म, i..., probability distribution over actions, induces the so-called mean field This mean field ja-namely, the distribution of all players' states-then affects both the taate-traniitoon dynamics and the rewards received by every agent. This simple formulation has broadened the applicability of MFGs to Multi-Agent Reinforcement Learning (MARL) (Yang et al. 2018; Guo et 2019; Angiuli al. 2022; Zeman al. 2023: Angiuli al. 2024). Moreover, has become possible to capture interactions among heterogeneous agents (Gao and Caines 2017; Caines and M. Huang 2019).
The applicability of MFGs to MARL drives research into the theoretical aspects of numerical algorithms for MFGs. Under fairly general assumptions, the problem of finding an equilibrium
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

in MFGs is known to be PPAD-complete (Yardim et al. 2024). Consequently, it is essential to impose assumptions that allow for the existence of algorithms capable of efficiently computing an equilibrium. One such assumption is contractivity (Q. Xie et al. 2021; Anahtarci et al. 2023; Yardim al. 2023). However, many MFG instances are known to be non-contractive in practice (Cui and Koeppl 2021). A more realistic assumption is the Lasry-Lions-type monotonicity employed in Pérolat et al. (2022), Zhang et al. (2023), and Yardim and He (2024), which intuitively implies that player's s reward monotonically decreases as more agents converge to a single state. Under the monotonicity assumption, Online Mirror Descent (OMD) has been proposed and widely adopted (Pérolat et al. 2022; Cui and Koeppl 2022; Laurière al. 2022; Fabian et al. 2023). OMD, especially when combined with function approximation via deep learning, has enabled the application of MFGs to MARL (Yang and Wang 2020; K. Zhang et al. 2021; Cui et al. 2022).
Theoretically, last-iterate convergence (LJC) without time-averaging is particularly important deep learning settings due to the constraints imposed by neural networks (NNs), as it ensures that the policy obtained in the last iteration converges. In NNs, computing the time-averaged policy as in the celebrated Fictitious Play method (Brown 1951; Perrin et al. 2020) may be less meaningful due to nonlinearity in the parameter space. This motivation has spurred significant research into developing algorithms that achieve LIC in finite N-player games, seen in, e.g., Mertikopoulos et al. (201 80, Piliouras et al. (2022), Abe et al. (2023), and Abe et al. (2024). However, in the case of MFGs, the results on LIC under realistic assumptions are limited. We refer the reader to read $ 7 and Appendix A to review the existing results in detail.
We aim to develop a simple method to achieve LIC for MFGs with realistic assumption. The first result of this paper is the development of Proximal Point (PP) method using Kullback-Leibler (KI.) divergence. We establish a novel convergence result in Theorem 3.1, showing that the PP method achieves LIC under the monotonicity assumption. When attempting to obtain convergence results in MFG, one faces the difficulty of controlling the mean field μ,, which changes along with the iterative updates of the policy и. We overcome this difficulty using the Lojasiewicz inequality, a classical tool from real analytic geometry.
We further propose the Approximate Proximal Point (APP) method make the PP method feasible, which can be interpreted as an approximation of it. Here, we show that one iteration of the PP method corresponds to finding an equilibrium of the MFG regularized by KI. divergence. This insight leads to the idea of approximating the iteration of PP by regularized Mirror Descent (RMD) introduced by Zhang et al. (2023). Our second theoretical result, presented in Theorem 4.3, is the LIC of RMD with an exponential rate. This result is significant improvement over previous studies that only showed the convergence of the time-averaged policy or convergence at a polynomial rate. In the proof, the dependence of the mean field μ on the policy π makes it difficult to readily exploit the Lipschitz continuity of the Q-function. We address this issue by utilizing the regularizing effect of the KL divergence.
Our experimental results also demonstrate LIC. The APP method can be implemented by making only small modification to the RMD and experimentally converges to the (unregularized) equilibrium.
In summary, the contributions of this paper follows:
Contributions
We present algorithm based the celebrated PP method and, for the first time, establish LIC for non-strictly monotone MFGs (Theorem 3.1).
(ii) We show that one iteration of the PP method is equivalent to solving the regularized MFG, which can be solved exponentially fast by RMD (Theorem 4.3).
(iii) Based on these two theoretical findings. we develop the APP method as an efficient approximation of the PP method (Algorithm 1).
The organization of this paper is as follows: In $ 2, we review the fundamental concepts of MFGs. In $ 3, we introduce the PP method and its convergence results. In $ 4, we present the RMD algorithm and its convergence properties. Finally, in $ 5, we propose a combined approximation method, demonstrating its convergence through experimental validation. $ provides review of related works.

---

2 Problem setting and preliminary facts
Notation: For a positive integer N E N. [N] = (I,...,,,,,. ,N. For a finite set X, A()) = {p E
x Exex p(a) 1}. For function f: + IR and a probability E A(X), (1,T) (())) = Emex f()) For p", p² E (XX), define the KL divergence DkI(F"pp)) p=
Exex (x) log (v"(x)/²*(r)) and the e distance as 1000 -p'l = Ezex (p' - px())
2.1 Mean-field games
Consider model based Mean-Field Game (MFG) that is defined through tuple (8, A, H. P,r, v1). Here, S is a finite discrete space of states, A is a finite discrete space of actions, H E N22 is a time horizon, and P = (= is sequence of transition kernels PA: x A + ASS), that is, if a player with state S4. E S takes action aj E AA at time h E [H]. the next state 8h+1 S will transition according to Sh+1 ~ Ph (- sh, ax). In addition, r = (rk) is a sequence of reward functions T x A x (S)) -> [0. 1]. and μn1 E ((S) is an initial probability of state. Note that, the context of theoretical analysis of the online learning method for MFG (Pérolat et al. 2022; F. Zhang et al. 2023), P is assumed to be independent of the state distribution. It reasonable to assume that at any time h, every state s' E S is reachable:
Assumption 2.1. For each (h, s') E [H] x S, there exists (s, a) E S x A such that PA (s' ss > 0.
Note that it does not require that, for any state s' E S, is reachable by any state-action pair (8, a) E S x A.
Remark 2.2. Our analysis excludes cases in which depends on j4, as studied in Zeman et al. (2023) and Zeng et al. (2024)). These studies also rely other conditions such as contraction herding, which differ in nature from our monotonicity assumption. Extending the analysis to a p-dependent P requires a different approach than that in the existing literature, e.g., Pérolat et al. (2022) and F. Zhang et al. (2023). A full treatment of the case is left for future work.
Given policy æ. the probabilities m|m] (m[T]a) A(S) of the state is recursively defined as follows: m[[T]] Mi and
m[T]a(SA)
Σ
TA-1 (ax-1 sh-1) Ph (sh 9h-1,
(2.1)
1 1.S.aa11..
if h = ..... H. We aim to maximize the following cumulative reward
Jp, ==
Σ
Th (a (s).,
(2.2)
with respect to the policy म. given sequence of state distributions μ E A(S) The mean-field equilibrium defined below means the pair of probabilities μ and policies that achieves the maximum under the constraints 12.
Definition 2.3. pair (p",**)= E A(S) x (A(A))) Jn" TT" max J(,", .)), and (ii) μ² m|rr]. In addition, set II C (A(A)))) as the set of all policies that are in mean-fiell equilibrium.
H is mean-field equilibrium if it satisfies (i)
Under Assumptions 2.4 and 2.5 below, there exists mean-field equilibrium, see the proof of Saldi et al. (2018, Theorem 3.3.) and Pérolat et al. (2022, Proposition 1.). Note that the equilibrium may not be unique if the inequality given below in Assumption 2.4 is non-strict. In other words, the set II" C ())A) " is not a singleton in general. As an illustrative example, one might consider the trivial case where 0. Our goal is to construct algorithm that approximates policy in II"
In this paper, we focus on rewards r that satisfy the following two typical conditions, which are also assumed in Perrin et al. (2020), Perrin et al. (2022), Pérolat et al. (2022), Fabian et al. (2023), and Zhang et al. (2023). The first one is monotonicity of the type introduced by Lasry and Lions (2007), which means, under state distribution = (pn) h== E (SS) if players choose a strategy-calles a policy π (TT)) E (AAA))) to be planned that concentrates on a state or action, they will receive a small reward.
3

---

Assumption 2.4 (Weak monotonicity of r). For all n, E (A(A) )M it holds that
H
Σ
Σ
(ma(s, a, 14)) - ru(s, a, mT)) (pn a) (s, a)) s O,
(2.3)
h= (x
where we μ m[m], Pl (s) == Th (al (s) and Ph(s, tr (a 8) p)))
A reward satisfying Assumption 2.4 is said be monotone. Furthermore, is said be strictly monotone if the equality in (2.3) holds only if π = म. Although most of the previous papers provide theoretical analysis under strict monotonicity, this excludes the case where the transition is symmetrie. We demonstrate that such structures inherently allow the existence of distinct policies generating identical state distributions, leading to the failure of strict monotonicity.
Example (Failure of strict monotonicity in symmetric transitions). In general, symmetry of P with respect to states in MFGs violates strict monotonicity, while preserving monotonicity. Consider an MFG with symmetric transition dynamics, e.g., consider an MDP defined on S = {s1,
{a1. 02), H 2 μ1
(2. 2). For each h E [H] the transition kernels are
0.2 0.8
0.7 0.3
If we take the policy æ 8) 0, (a) 0, Rh (a2 s) 1, for all S and h E [H]. we can see that m]TT = m - (0.5. for all h. Let the reward be of the form (s, a. p))
Ph (s' 8, a = 01) = 0.8 0.2
Pn (s' |s = 0.3
0.7
such that TT. (ar 8) 1, Th (a2
(s. a) f(((s)) with a non-decreasing function f: f0 1] + R such as f(x) = z. which models crowd that avoids overcrowding. Then the monotonicity condition holds for the case т # न. However, striet monotonicity would demand that equality occur only if म. In this example, whenever m[T]] m][r] (here the uniform distribution), the above sum is zero even if π * т. Hence, the game is monotone but not strictly monotone. Such phenomena are limitations in games with balanced transitions.
The second is the Lipschitz continuity of with respect to μ E (A(S)) which is standard in the field of MFGs (Cui and Keeppl 2021; Fabian et al. 2023; F. Zhang et al. 2023). Assumption 2.5 (Lipschitz continuity of r). There exists constant I. such that for every h [M], E S, a E A, and μ. μ' E A(S): [rx a, - (s, a, x²) < L|| p'll-
3 Proximal point-type method for MFG
This section presents algorithm motivated by the Proximal Point (PP) method. Let À > 0 be sufficiently small positive number, roughly "the inverse of learning rate." In the algorithm proposed in this paper, we generate a sequence ((at, )=)))= c (A(A))) x A(S) as
b+ arg max " (A))())))
(J(nht), xx) - (T,
n = m
(3.1)
= where m is defined in (2.1) and (p = En Eewp, (TKL(TA (s))] with probability A(S) If the initial policy T² has full support, i.e., ai Th (a |s) > 0, the rule (3.1) is well-defined, see Proposition C.I.
Interestingly, the rule (3.1) is similar to the traditional Proximal Point (PP) method with KL divergence mathematical optimization and Optimal Transport, see Censor and Zenios (1992) and Y. Xie et al. (2019). Therefore, we also refer to this update rule as the PP method. The well- (O)MD in Pérolat et al. (2022) can be viewed as a linearization of the objective J inside (3.1). Consequently, PP_ which uses the full, un-linearised J- is expected to be less sensitive to approximation error, resulting in more robust convergence under non-strict monotonicity than MD. On the other hand, unlike the traditional PP method, our method changes the objective function ( ): (())))) + R with each iteration E N. Therefore, it difficult to derive a theoretical convergence result of our traditional method from traditional theory. See also Remark 3.3.
3.1 Last-iterate convergence result
The following theorem implies the last-iterate convergence of the policies generated by (3.1). Specifi- cally, it shows that under the assumptions above, the sequence of policies converges to the equilibrium set. This result is crucial for the effectiveness of the algorithm in reaching an optimal policy.

---

Theorem 3.1. Let (o be the sequence defined by (3.1). In addition to As- sumptions 2.1, 2.4, and 2.5, assume that the initial policy TO has full support, i.e. m Th (a 8) > O. Then, the sequence (a converges to the set II of equilibrium, i.e,, lim dist(o*, III') O. where we set dist(a, = an E(ns))e (lon(s) - [T)ls) for a E (A(A)))
Note that Theorem 3.1 no longer relies on the strict-monotoni loo and Silva 2019; Elie et al. 2020; Pérolat et al. 2022). Moreover, unlike the continuous- results of Perrin et al. (2020) and Pérolat et al. (2022), it applies directly to the discrete-time scheme (3.1).
imposed in earlier works (Hadikhan-
Proof sketch of Theorem 3.1. If we accept the next lemma, we can easily prove Theorem 3.1:
Lemma 3.2. Suppose Assumption 2.4. Then, for any equilibrium (μ² TT" it holds that .²)) ) D yet h+1 ot)) De OT- o ( k+1 - Dur (x" ) S "("""ttt - _("",
S J
,("",='))
(3.2)
Lemma 3.2 implies that the KL divergence from an equilibrium point to the generated pol- icy becomes smaller as the cumulative reward J increases. We note that the function J(pt )) (A(A))) 3 π H [[p", π) E R is polynomial, thus real-analytic. Then we ap- ply (Fojasiewicz 1971, $18, Théorème 2) and find that there exist positive constants a and C satisfying J ;) J(p", x²) S -C(dist (TT, IT* for any т E (A(A))) Combining the above two inequalities yields that Dw (T*", o k + D (TT", o²) S -Cdist((a* .Ir)) Thus,
the telescoping sum of this inequality yields Eh= (dist(o* ) implies lim dist((o.,
(='.aa (a))
C < +00, which
IT*) = 0.
Remark 3.3 (Challenges in the proof of Theorem 3.1). The technical difficulty in the proof lies in
the term D ++ (a** ( in (3.2). it were not dependent on that is, D p = Dur-, then LIC would follow straightforwardly from D (TT* o Dy- (TT", o*) I -D, (a++1 , where we use Definition 2.3 and the second line of (3.2). However, D Dr changes depending on k. Therefore, in the above proof, we have made a special effort to avoid using D )*). One may have seen proofs employing the simple argument described above in games other than MFG, such as monotone games (Rosen 1965). The reason why such an argument is possible in monotone games is that the mean field, j does not appear. This difference makes it difficult to use the straightforward argument described above in MFGs.
4 Approximating proximal point with mirror descent in regularized MFG
As in the PP method, it is necessary to find (u==1,aht)) o.+1) at each iteration. How- ever, it is difficull to exactly compute (1++1, g(th) due to the implicit nature of (3.1). Therefore, this section introduces Regularized Mirror Descent (RMD), which approximates the solution (1++1, o for each policy o². The novel result in this section is that the divergence between the sequence generated by RMD and the equilibrium decays exponentially shown in Figure 1.
10
10--
4.1 Approximation of the update rule of PP with regularized MFG
10
Interestingly, solving (3.1) corresponds finding an equilibrium for KL- regularized MFG introduced in Cui and Koeppl (2021) and F. Zhang et al. (2023). We review the settings for the regularized MFG. For each (H, which plays the role of gh in (3.1), we define the regularized cumulative reward JA (H, for (u, T) E A(S) x (A(A)5)B to be
10-11
RND with - C-ccee-
parameter X > 0 and policy
10-12
500 of inemttons
1000
1630
JA (p, T) = Hu, T) (z.
(4.1)
Figure 1: Behavior of RMD.
The assumption of full support is also imposed on d:
5

---

Assumption 4.1. The base o has full support, i.e., the minimum value given by
min
min
Th (a s)
strictly positive.
For the reward JA.o, we introduce a regularized equilibrium:
Definition 4.2. A pair =²) E A(S) x (A(A)))" is regularized equilibrium of JA, if it satisfies (i) JA (n²,, w²) = maXFEA(S)" JA. (n", T), and (ii) μ m(=").
Specifically, (n++1 x can be characterized as the regularized equilibrium of JA.o* for ls E E. Note that the equilibrium is unique under Assumption 4.1, Appendix C.
In the next subsection, we will introduce RMD using value functions, which are defined as follows: for each / [L]] E S, E A. E ((S) and π E A(A) define the state value function VA ( (A(A)S)H + R and the stale-action value function xh A x A(8)
(A(A)S) + R as
H
VA p) = E (G
Σ
(ri(s), - ADKI, (S))
VÀo. #+1 = 0, (4.2)
2 a, 14, == = (8, a, (ua) + E Eetti P(a,,,))) (V (1,+1, x)]. Here, the discrete-time stochastic process ((s,, (=)
(4.3)
1r is induced recursively by sn. and 8141
P((st,a)) ~ ((())) for each 1 E (h,..., H - 1} and an (sH).. Note that the objective function JA in Definition 4.2 can be expressed as JA (u, T) = Bewan VV> (s.
4.2 An exponential convergence result
In this subsection, we introduce the iterative method for finding the regularized equilibrium proposed by F. Zhang et al. (2023) as RMD. The method constructs a sequence ((*', ,x¹) ) (A(A))) x
A(S)" approximating the regularized equilibrium of Jλ. using the following rule:
1 Ar) ((0) (8, ,T, ,'','),)) - ADKa (D))))).(()))) - -DRI (e, {(0)
++1 (s) = arg max
h
PEA(A)
1 1+ = m[[7+1],
(4.4)
A is the state-action value function defined in (4.3). We give the pseudo-code of RMD in Algorithm 2. For the sequence of policies in RMD, we can establish the convergence result as follows:
where 1) > 0 is another learning rate, and 2,,0
Theorem 4.3. Let ((pl, DE CAIS) x (A(A)S) be the sequence generated by (4.4), and (fe², , =") E (SS) x (A(A)))) be the regularized equilibrium given in Definition 4.2. In addition Assumptions 2.4, 2.5, and 4.1, suppose that 1 S n1,, where 11" 0 is the upper bound of the learning rate defined in (D.5), which only depends on X, o, H and (A). Then, the sequence (i )22 satisfies that for E N
An Dr- 1---2
, <
-22/
ad) Ant/2, Clearly, the inequality states that an ap- which leads D (ω", T') E D Da (
proximate policy n¹ satisfying Dy- x²) < can be obtained in Ollog (1/=)) iterations.
Remark 4.4. While Theorem 4.3 provides an exponentially decreasing bound, the theoretical upper bound 17" on the step size 17 can be small, see (D.4) and (D.5) in detail.
This metric (==(==,na is widely used in F. Zhang et al. (2023) and Dong et al. (2025) because provides an upper bound for the so-called exploitability Exploit(Tr) == max [=) m')
J (m[[T) m) as Exploit(z") = o (Dr (wo ,7)) by the Lipschitz continuity of V,A. We also note that Theorem 4.3 improves upon the previous results by F. Zhang et al. (2023) and Dong et al. (2025) in the regime with large number of iterations t. Indeed, the authors obtained (,-" Σ m²) <

---

O(Alog" T/VT) and " I /ve. On the other hand, these bounds for finite t may be smaller since the constant 17 inside our exponent could be small.
4.3 Intuition for exponential convergence: continuous-timn version of RMD
The convergence of (T');= can be intuitively explained by considering a continuous limit (200 with respect to the time t of RMD. In this paragraph. we will use the idea of mirror flow (Krichene et al. 2015; Tzen et al. 2023; Deb et al. 2023) and continuous dynamics in games (Taylor and Jonker 1978; Mertikopoulos al. 2018; Pérolat et al. 2021; Pérolat et al. 2022) observe the exponential convergence of the flow to equilibrium. According to Deb et al. (2023, (2.1)). the continuous curve of should satisfy that
di th (a 8) = = (a) (s,
n (a
A Alog
(4.5)
Tn (1
The flow induced by the dynamical system (4.5) converges to equilibrium exponentially as time t goes infinity.
Theorem 4.5. Let nt be solution of (4.5) and wt regularized equilibrium defined in
Definition 4.2. Suppose that Assumption 2.4. Then
d d dt
D m S - -D (w=", x²);
for all 1. 2 O. Moreover, the inequality implies D (w² x²) S p 70) exp (-10).
exp
Technically, the non-Lipschitz continuity of the value function 0 ( (s, a, o. (c)) in the right-hand side of (4.5) is non-trivial for the existence of the solution π: [0, +o0) + (A(A))) of the differ- ential equation (4.5), see, e.g., Coddington and Levinson (1984). The proof of this existence and Theorem 4.5 are given in Appendix C.
4.4 Proof sketch of the convergence result for RMD
We return from antinuous-time dynamics (4.5) to the discrete-time algorithm (4.4). The technical difficulty in the proof of Theorem 4.3 is the non-Lipschitz continuity of the value function Q in (4.4), that is, the derivative of AA (s, a, TT) with respect the policy æ can blow up as ı approaches the boundary of the space (A(A))) of probability simplices. We can overcome this difficulty as shown in the following sketch of proof:
Proof sketch of Theorem 4.3. In similar way to Theorem 4.5, we can obtain the following inequality with discretization emr.r:
Du- (w", . 111 - Da- (= ,==t,,))') - Ann
+ Dz-(T', n T(+1),
(4.6)
where we property of KL divergence, see the proof in Appendix D. The remainder of the proof is almost entirely dedicated to showing that the above error term is sufficiently small and bounded compared to the other terms in (4.6). As result, we obtain the following claim:
Claim 4.6. Suppose that the learning is less than the upper bound 11º in (D.5). Then
Dr. (T 11
Crr2 (x w²),
where 0 the constant defined in (D.4), which satisfies Cn" S A/2.
The key to proving Claim 4.6 is leveraging another claim that, over the sequence (T²)), the value function 0, behaves well, almost if it were Lipschitz continuous function, see Lemma D.3. for details. Therefore, applying Claim 4.6 to (4.6) completes the proof.
Remark 4.7 (Challenges in the proof of Theorem 4.3). The technical difficulty in the proof lies in the fact that the Q-function (s, x², , j²") in the algorithm (4.4) depends on the mean field u² ml ('), which is determined forward by (2.1) from past times 1 to h 1. On the other hand,

---

Algorithm 1: APP for MFG
Algorithm 2: RMD x², X, 17, n7,00, .)
Input: MFG A, H, P.r. M,,, initial policy
Initialization: Set 0, x² T0,
TO #iterations N, x > 0
t- 0²:
Initialization: Set h +- 0, ot n
2
while t < do
2 while k < N do
3
Compute je' =m[[7'];
Compute (1++1,, ( by solving
3
Compute Q) (s, a, n²) by (4.3);
4
5
Compute x x+1 as
0 gh-1 = RMD o* A. n, ,),)
Th x (a 1 8) (on 8)) ( (a ()) s))1-an
p = ml
(s, (s, n" exp (s
,1))
Update k + 1: 1;; Output: of o'
Update & 4- +++1;
return w")
the Q-function is also determined by the policy future times h + 1 to H through the dynamic programming principle given by (4.3). As result, it becomes difficult apply the backward induction argument, which is known in the context of MDPs and Markov games, to Q-functions. This difficulty is specific MFGs and is not seen in other regularized games such as engropy-regullrrized zero-sum Markov games, where the Q-function depends only on future policies. Therefore, it is less feasible to directly apply the techniques of existing research, such as Cen et al. (2023), RMD for MFGs. Our proof instead utilizes the properties of the KL divergence to deal with this difficulty.
4.5
APP: approximating PP updates with RMD
We recall that we need to develop an algorithm that efficiently approximates the update rule of the PP method since the rule (3.1) is intractable. To this end, we employ the regularized Mirror Descent (RMD) to solve the (unregularized) MFG as substitute for the rule. Specifically, after repeating the RMD iteration (4.4) a sufficient number of times, we update the base distribution a using the most recently obtained policy o++ We call this method APP, which is summarized in Algorithm 1. In APP, updating the base seems like a small modification of RMD, but it is crucial for convergence. Without this update, we can only obtain regularized equilibria, which are generally different from our ultimate goal of unregularized equilibria. In fact, Definition 2.3, 4.2 and Assumption 2.4 yield that Ju",, n²) [pp,, w*) S A(D,, (T* oo) - Du- (w", .o)), which roughly implies that the gap between regularized and unregularized equilibria is O()). Experimental results in Cui and Koeppl (2021) also suggest that to find the (unregularized) equilibrium with regularized algorithm, it is necessary to tune the hyperparameter À appropriately. Theoretically, the results we have established in Theorems 3.1 and 4.3 provide some convergence guarantees for APP. Empirically, the experimental results in the next section suggest that APP also achieves LIC. We conjecture that the rate of convergence for APP, as predicted by these experiments, may also be derived.
5 Numerical experiment
We numerically demonstrate that APP, which is the approximated version of (3.1), can achieve convergence to the mean-field equilibrium. We evaluate the convergence of APP using the Beach Bar Process introduced by Perrin et al. (2020), a standard benchmark for MFGs. In particular, the transition kernel P in this benchmark gives random walk on a one-dimensional discretized torus S (0, (O...., S| - 13. and the reward is to be (1, a, 11) = -|al/|S| |s- - log pa (s) with a E A = {1 +0, +1}. Note that this benchmark satisfies the monotonicity assumption in Assumption 2.4. See Appendix F for further details. Figure/ 2 is summary of the results of the experiment. The most notable aspect is the convergence of exploitability, as shown in Figure 2b. APP decreases the exploitability with each iteration when we update a. Figure 2a and 2c illustrate the qualitative validity of the approximation achieved by APP. In this benchmark, the equilibrium expected to lie the vertices of the probability simplex. Therefore, RMD, which can shift the equilibrium to the interior of the probability simplex, seems unable to find the mean- mean-field equilibrium
8

---

10"1
(mpoore"))
H520 of
10-4
30-3
64
updlde
10-1
propoces 10)
pessosed [+ 101
propased 1000)
RMD
137
10
10
30F
10
Rggh
@lteration
(a) The difference between RMD and APP the evolution of (na (ua))=1
(b) Convergence of Exploit
(c) Trajectory of (#f (1))
Figure 2: Experimental results for Algorithm 1 for Beach Bar Process
accurately. On the other hand, the sequence (T*); of policies generated by APP shows behavior that converges to the vertices.
Limitations
Our results provide the first asymptotic (Theorem 3.1) and exponential (Theorem 4.5) convergence guarantees for PP and RMD in non-strictly monotone (unregularized) MFGs under the model-based setting, assuming that the transition kernels and reward functions are available. This leaves open several important questions. First, we do not consider the more realistic scenario in which the transition of mean-field and reward must be learned from data, nor do we provide any sample- complexity or statistical guarantees, such as those in J. Huang et al. (2024), which would be required for rigorous model-free or data-driven applications. Second, our theoretical advantages are strictly in terms of iteration complexity under monotonicity: we establish faster convergence rates per iteration, but we do not claim any improvements overall computational cost (for example, the cost of solving each PP subproblem or evaluating Q in RMD)), nor do we analyze how these methods scale with large and
state or action spaces in practice. Finally, although the proximal-pone of PP and RMD makes them, in principle, compatible with nonlinear function approximators, such as NNs, we have not studied approximation errors as in F. Zhang et al. (2023), stability issues, or empirical performance in high-dimensional highly nonlinear settings.
structure
Establishing LIC for APP remains open. We conjecture that a resolution will require proving a uniform positive lower bound on 17" that guarantees LIC for RMD, which will improve the current estimate; see Remark 4.4.
By synchronous feedback we mean that, at (outer/inner) iterate k. all updates use the Q-function evaluated on the current pair (x* ,,²)). In practice, feedback may be delayed or asynchronous. A at a delayed index k(O), By analogy with asynchronous gradient play in zero-sum games (Ao et al. 2023), we expect last-iterate stability to persist under bounded staleness with suitably reduced stepsize. A complete analysis in the MFG setting left for future work.
natural adaptation is to evaluate Q at stale iterate, e.g., (( _x*
Related works
As result the focus on the modeling potential of various population dynamics. there has been significant increase in the literature on computations of cquilibria in large-scale MFG, or so-called Learning MFGs. We refer readers read (Laurière al. 2024) a comprehensive survey of Learning in MFGs. Guo et al. (2019) and Anahtarci et al. (2020) developed fixed-point iteration that alternately updates the mean-field μ and policy π, based on the algorithm of MDPs. They showed that this fixed-point iteration achieves LIC under a condition of contraction. However, it is known that the condition of contraction does not hold for many games in Cui and Koeppl (2021). In MFGs where the contraction assumption does not hold, it is observed that the fixed-point iteration oscillates the case of linear-quadratic MFGs (I (Laurière 2021). Fictitious play, which averages mean fields or policies over time, was developed to prevent this oscillation. Hadikhanloo and Silva (2019), Elie et

---

al. (2020), and Perrin (2022) showed that the average in fictitious play converges to an equilibrium under the monotonicity assumption in Assumption 2.4. On the other hand, such time averaging has the disadvantage of slowing the experimental rate of convergence observed in I Laurière et al. (2024) and making difficult to scale up using deep learning.
Pérolat et al. (2022) applied Mirror Descent to MFG and developed a scalable method. This method has the practical benefits of being compatible with deep learning and is applicable to variants of variants (Laurière et al. 2022; Fabian et al. 2023). However, the theoretical guarantees are somewhat restrictive, as they often require strong assumptions like contraction for last-iterate convergence. In fact, they showed last-iterate convergence (LIC) of continuous time algorithms under strict monotonicity assumptions. However, results for discrete-time settings or non-strict monotonicity are lacking. In addition to fictitious play and MD, methods using the actor-crite method (Zeng et al. 2024), value iteration (Anahtarci al. 2020), multi-time scale (Angiuli et 2022; Angiuli et al. 2023; Angiuli et al. 2024) and semi-gradien method (C. Zhang et al. 2025) have been developed, but to the best of our knowledge, the theoretical convergence results of these methods require a condition of contraction. See the upper part of Table for details.
Rather than focusing on the algorithm explained above, Cui and Koeppl (2021) focused on the problem setting of MFG and aimed to achieve a fast convergence of the algorithms by considering regularization of MFG. This type of regularization is typical in the case of MDPs and two-player zero- sum Markov games. where Mirror Descent achieves exponential convergence (Zhan et al. 2021; Cen al. 2023). One expects similar convergence results for regularized MFGs, but the fast convergence results without strong assumptions have been limited so far. F. Zhang et al. (2023) and Dong et al. (2025) demonstrated polynomial convergence rates for MD under monotonicity. authors in Q. Xie et al. (2021), Mao et al. (2022), Cui and Keeppl (2021), and Anahtarci et al. (2023) develop an algorithm that converges polynomially for regularized MFG, and they impose restrictive assumptions such as contraction and strict monotonicity, Appendix A provides an extensive review comparing existing results Learning in MFGs.
addition, the
Conclusion
This paper proposes the novel method to achieve LIC under the monotonicity (Assumption 2.4). The main idea behind the derivation of the method is to approximate the PP type method (3.1) 1) using RMD. Theorem 3.1 implies that the PP method achieves LIC, and Theorem 4.3 establish the exponential convergence of RMD. A future task of this study is to prove the convergence rates of the combined method, APP.
Acknowledgments and Disclosure of Funding
The first author was supported by JSPS KAKENHI Grant Numbers JP22KJ1002 and JP25H01453, as well as by JST ACT-X Grant Number JPMJAX25C2. Kaito Ariu was supported by ISPS KAKENHI Grant Numbers 23K 19986 and 25K21291.
References
K. Abe, K. Ariu, M. Sakamoto, and A. Iwasaki (2024). "Adaptively Perturbed Mirror Descent for Learning in Games". In: ICML.
K. Abe, K. Ariu, M. Sakamoto, K. Toyoshima, and A. Iwasaki (2023). "Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sume Sum Games". In: AISTATS. Vol. 206. Proceedings of Machine Learning Research. PMLR, pp. 7999-8028
A. Agarwal, N. Jiang, S. M. Kakade, and W. Sun (2022). Reinforcement Learning: Theory and Algorithms, online.
B. Anahtarci, C. D. Kariksiz, and Saldi (2020). "Value iteration algorithm for mean-field games".
In: Syst. Control. Lett. 143, 104744. (2023). "Q-Leamnng in Regularized Mcan-field Games". In: Dynamic Games and Applications 13.1, pp. 89-117.
A. Angiuli, J. Fouque, and M. Laurière (2022). "Unified reinforcement Q-learning for mean field game and control problems". " In: Math. Control. Signals Syst. 34.2, pp. 217-271.
10

---

A. Angiuli, J. Fouque, M. Laurière, and M. Zhang (2023), "Analysis of Multiscale Reinforcement
Q-Learning Algorithms for Mean Field Control Games". In: CoRR abs/23
(2024). "Analysis of Multiscale Reinforcement Q-Learning Algorithms for Mean Field Control Games". In: CoRR abs/2405. 17017.
R. Ao, S. Cen, and Y. Chi (2023). "Asynchronous Gradient Play in Zero-Sum Multi-agent Games". In: ICLR.
D. P. Bertsekas and S. E. Shreve (1978). Stochastic optimal control. Vol. 139, Mathematics in Science and Engineering. The discrete time case. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, pp. xiii+323.
G. W. Brown (1951). "Iterative Solution of Games by Fictitious Play". In: Activity Analysis of
Production and Allocation. Ed. by T. C. Koopmans. New York: Wiley.
P. F. Caines and M. Huang (2019). "Graphon Mean Field Games and the GMFG Equations: c-Nash
Equilibria". In: CDC IEFE, pp. 286-292.
P. Cardaliaguet and S. Hadikhanloo (2017). "Learning in mean field games: The fictitious play". In:
ESAIM: COCV 23.2, pp. 569-591.
S. Cen, Y. Chi. S. S. Du, and L. Xiao (2023). "Faster Last-iterate Convergence of Policy Optimization
in Zero-Sum Markov Games". In: ICLR.
Y. Censor and S. A. Zenios (1992). "Proximal minimization algorithm withD-functions" In: Journal
of Optimization Theory and Applications 73.3, pp. 451-464.
R. Chill, E. Fasangova, and U. Fakulta (2010). "Gradient Systems". In: 13th International Internet Seminar.
A. Coddington and N. Levinson (1984). Theory of Ordinary Differential Equations. International series in pure and applied mathematics. R.E. Krieger.
K. Cui and H. Koeppl (2021). "Approximately Solving Mean Field Games via
Deep Reinforcement Learning.. In: AISTATS. Vol. 130. Proceedings of Machine Learning Research. PMLR, pp. 1909-1917.
(2022). "Learning Graphon Mean Field Games and Approximate Nash Equilibria". In: ICLR. K. Cui, A. Tahir, G. Ekinci, A. Elshamanhory, Y. Eich, M. Li, and H. Koeppl (2022). "A Survey on Large-Pory Proggeetpotttionn Systems and Scalable Aulti-Agent Reinforcement Learning". In: CoRR foss/200.008555
N. Deb, Y.-H. Kim, S. Pal, and G. Schiebinger (2023). Wasserstein Mirror Gradient Flow as the limit of the Sinkhorn Algorithm.
J. Dong, B. Wang, and Y. Yu (2025). "Last-iterate Convergence in Regularized Graphon Mean Field Game". In: AAAI AAAI Press, pp. 13779-13787.
R. Elie, J. Pérolat, M. Laurière, M. Geist, and O. Pietquin (2020). "On the Convergence of Model Free Learning in Mean Field Games". In: AAAI, pp. 7143-7150.
C. Fabian, K. Cui, and H. Koeppl (2023). "Learning Sparse Graphon Mean Field Games". In: AISTATS. Vol. 206. Proceedings of Machine Learning Research. PMLR, pp. 4486-4514, (2024). "Learning Mean Field Games on Sparse Graphs: A Hybrid Graphex Approach", In: ICLR. S. Gao and P. E. Caines (2017). "The control of arbitrary size networks of linear systems via graphon limits: An initial investigation". In: CDC. IEEE, pp. 1052-1057.
M. Geist, J. Pérolat, M. Laurière, R. Elie, S. Perrin, O. Bachem, R. Munos, and O. Pietquin (2022). "Concave Utility Reinforcement Learning: The Mean-field Game Viewpoint". In: AAMAS. In- ternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), pp. 489-
497.
M. Geist, B. Scherrer, and O. Pietquin (2019). "A Theory of Regularized Markov Decision Processes".
In: ICML. Vol. 97. Proceedings of Machine Learning Research. PMLR, pp. 2160-2169.
D. A. Gomes, J. Mohr, and R. R. Souza (2010). "Discrete time, finite state space mean field games".
In: Journal de Mathématiques Pures et Appliquées 93.3, pp. 308-328.
X. Guo, A. Hu, R. Xu, and J. Zhang (2019). "Learning Mean-Field Games", In: NeurlPS, pp. 4967- 4977.
X. Guo, A. Hu, and J. Zhang (2024). "MF-OMO: An Optimization Formulation of Mean-Field Games". In: SIAM Journal Control and Optimization 62. pp. 243-270.
S. Hadikhanloo and F. J. Silva (2019). "Finite Mean Field Games: Fictitious play and convergence to first order continuous mean field game". In: Journal de Mathématiques Pures Appliquées 132,
pp. 369-397.
A. Hu and J. Zhang (2024). "MF-OML: Online MieldFieed Reinforcement Learning with Occupation Measures for Large Population Games", In: CoRR abs/2405.00282.
11

---

J. Huang, B. Yardim, and N. He (2024). "On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximation", In: AISTATS. Vol. 238. Proceedings of Machine Learning Research. PMLR, pp. 289-297.
M. Huang, R. P. Malhamé, and P. E. Caines (2006). "L.aree population stochastic dynamic games: closed-loop McKean-Vlasse Vlasov systems and the Nash certainty equivalence principle". In: Communi-
cations in Information & Systems 6.3, pp. 221-252.
D. Inoue, Y. Ito, T. Kashiwabara, N. Saito, and H. Yoshida (2023). "A fictitious-play finite-difference method for linearly solvable mean field games". In: ESAIM: M2AN 57.4, pp. 1863-1892.
W. Krichene, A. M. Bayen, and P. L. Bartlett (2015). "Accelerated Mirror Descent in Continuous and Discrete Time". In: NIPS, pp.
J.-M. Lasry and P.-L. Lions (2007). "Mean field games". In: Jpn. J. Math. 2.1, pp. 229-260. M. Laurière (2021). "Numerical methods for mean field games and mean field type control". In: Mean field games. Vol. 78. Proc. Sympos. Appl. Math. Amer. Math. Soc., Providence, RI, pp. 221-282. M. Laurière, S. Perrin, M. Geist, and O. Pietquin (2024). "Learning in Mean Field Games: A Survey".
In: CoRR abs/2205. 12944v4.
M. Laurière, S. Perrin, S. Girgin, P. Muller, A. Jain, T. Cabannes, G. Piliouras, J. Perolat, R. Elic, O. Pietquin, and M. Geist (2022). "Scalable Deep Reinforcement Learning Algorithms for Mean Field Games". In: Proceedings of the 39th International Conference on Machine Learning. Ed. by K. Chaudhuri. S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato. Vol. 162. Proceedings of Machine Learning Research. PMLR, Pp. 12078-12095
Lavigne and L. Pfeiffer (2023). "Generalized Conditional Gradient and Learning in Potential Mean Field Games". In: Applied Mathematics & Optinization 88.3, p. 89. Leonardos, G. Piliouras, and K. Spendlove (2021). Exxploration-Exploiaaeee
in Multi-Agent Competition: Convergence with Bounded Rationality". In: NeurlPS, pp. (6318-26331) Lojasiewiez (1971). "Sur les ensembles amii-nalyttiqus." In: Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 2, pp. 237-241.
W. Mao, H. Qiu, C. Wang. H. Franke, Z. Kalbarczyk, R. K. Iyer, and T. Basar (2022). "A Mean-Field Game Approach to Cloud Resource Management with Function Approximation". In: NeuriPS. P. Mertikopoulos, C. Papadimitriou, and G. Piliouras (2018). "Cycles in Adversarial Regularized Learning". In: SODA, pp. 2703-2717.
J. Pérolat, R. Munos, J. Lespiau, S. Omidshafici, M. Rowland, P. A. Ortega, N. Burch, T. W. Anthony, D. Balduzzi, B. D. Vylder, G. Piliouras, M. Lanctot, and K. Tuyls (2021). "From Poincaré Recur- rence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization". In: ICML. Vol. 139. Proceedings of Machine Learning Research. PMLR, pp. 8525-8535.
J. Pérolat, S. Perrin, R. Elie, M. Laurière, G. Piliouras, M. Geist, K. Tuyls, and O. Pietquin (2022). "Scaling Mean Field Games by Online Mirror Descent". In: AAMAS. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), pp. 1028-1037.
S. Perrin (2022). "Scaling up Multi-agent Reinforcement Learning with Mean Field Games and Vice-versa". PhD thesis. Université de Lille.
S. Perrin, M. Laurière. J. Pérolat, R. Élic, M. Geist, and O. Pietquin (2022). "Generalization in Mean Field Games by Learning Master Policies". In: AAAI. AAAI Press, pp. 9413-9421.
Perrin, J. Pérolat, M. Laurière, M. Geist, R. Elie, and O. Pietquin (2020). "Fietitious Play for Mean Field Games: Continuous Time Analysis and Applications". In: NeurIPS.
G. Piliouras, R. Sim, and S. Skoulakis (2022). "Beyond Time-Average Convergence: Opar-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update". In: NeurIPS.
M. L. Puterman (1994). Markov decision processes: discrete stochastic dynamic programming. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. A Wiley-Interscience Publication. John Wiley Sons, Inc., New York, pp. xx+649.
J. B. Rosen (1965). "Existence and uniqueness of equilibrium points for concave N N-person games". In: Econometrica 33, pp. 520-534.
N. Saldi, T. Başar, and M. Raginsky (2018). "Markov-Nash Equilibria in Mean-Field Games with Discounted Cost". In: SIAM Journal on Control and Optimization 56.6, pp. 4256-4287.
P. D. Taylor and L. B. Jonker (1978). "Evolutionary stable strategies and game dynamics". In: Mathematical Biosciences 40.1, pp. 145-156.
B. Tzen, A. Raj. M. Raginsky, and F. R. Bach (2023). "Variational Principles for Mirror Descent and Mirror Langevin Dynamics". In: IEEE Control. Syst. Lelt. 7, pp. 1542-1547.
Q Xie, Z. Yang. Z. Wang, and A. Minca (2021). "Learning While Playing in Mean-Field Games: Convergence and Optimality". In: ICML. Vol. 139. Proceedings of Machine Learning Research. PMLR, pp. 11436-11447
12

---

Y. Xie. X. Wang, R. Wang, and H. Zha (2019). "A Fast Proximal Point Method for Computing Exact Wasserstein Distance". In: UAL. Vol. 115. Proceedings of Machine Learning Research. AUAI Press, pp. 433-453.
Y. Yang. R. Luo, M. Li, M. Zhou, W. Zhang, and Wang (2018). "Mean Field Multi-Agent Reinforcement Learning". In: ICML. Vol. 80. Proceedings of Machine Learning Research. PMLR, pp. 5567-5576.
Y. Yang and J. Wang (2020). "An Overview of Multi-Agent Reinforcement Learning from Game Theoretical Perspective". In: CoRR (bs0220
B. Yardim, S. Cayci. M. Geist, and N. He (2023). "Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games". In: JCML. Vol. 202. Proceedings of Machine Learning Research.
PMLR. pp. 39722-39754.
B. Yardim, A. Goldman, and N. He (2024). "When is Mean-Field Reinforcement Learning Tractable and Relevant?" In: AAMAS. International Foundation for Autonomous Agents and Multiagent Systems ACM, pp. 2038-2046.
B. Yardim and N. He (2024). "Exploiting Approximate Symmetry for Efficient Multi-Agent Rein- forcement Learning". In: CoRR abs/2408.1511
M. A. u. Zeman, A. Koppel, S. Bhatt, and T. Basar (2023). "Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Path". In: AISTATS. Vol. 206. Proceedings of Machine Learning Research. PMLR, pp. 10178-10206.
S. Zeng, S. Bhatt, A. Koppel, and S. Ganesh (2024). "A Policy Optimization Approach to the Solution of Unregularized Mean Field Games". In: ICML 2024 Workshop: Foundations of Reinforcement Learning and Control - Connections and Perspectives.
W. Zhan, S. Cen, B. Huang, Y. Chen, J. D. Lee, and Chi (2021). "Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence". In: CoRR abs/2105.
C. Zhang, X. Chen, and X. Di (2025). "Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-ANe Aware Function Approximation". In: ICLR. F. Zhang, V. Y. F. Tan, Z. Wang. and Z. Yang (2023). "Learning Regularized Monotone Graphon Mcan-Field Games". ". In: NeurIPS.
K. Zhang. Z. Yang, and T. Başar (2021). "Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms". In: Handbook of Reinforcement Learning and Control. Cham: Springer International Publishing, pp. 321-384.
13

---

A
Detailed Explanation of Related Works
Table I: Summary of related work on convergence of iterative methods for MFGs
Discrete
Assumption
LIC
time
Guo et al. (2019)
Contract.
Elie et al. (2020),
Strict Mono.
Hadikhanloo and Silva (2019)
Perrin et al. (2020)
Mono.
Anahtarci al. (2020)
Contract.
Pérolat et al. (2022)
Strict Mono.
Geist et al. (2022)
Concavity
V
MFG
Angiuli et al. (2022), Angiuli et al. (2023), Angiuli et al. (2024)
Contract.
Yardim et al. (2023)
Contract.
Zeng et al. (2024)
Herding
C. Zhang et al. (2025)
Contract.
V
Ours (Theorem 3.1)
Mono.
/
Q. Xie et al. (2021)
Contract.
Cui and Koeppl (2021)
Contract.
Mao et al. (2022)
Contract.
Regularized
Anahtarci al. (2023)
Contract.
v
MFG
F, Zhang al. (2023)
Strict Mono.
Dong et al. (2025)
Mono.
w/ poly. rate
Ours (Theorem 4.5)
Mono.
w/ exp. rate
A.1
Comparison with literature on MFGs
Based on Table 1, we will discuss the technical contributions made by this paper in Learning in MFGs below.
Last-iterate convergence (LIC) results for MFGs: Pérolat et al. (2022) showed that Mirror Descent achieves LIC only under strictly monotone conditions, i.e., if the equality in the Lemma E.2 satisfied only π = т. In contrast, our work establishes LIC even in non-strictly monotone scenarios. While the distinction regarding strictness might seem subtle, it is profoundly significant. Indeed, non-strictly monotone MFGs encompass the fundamental examples of finite-horizon Markov Decision Processes. Moreover, in strictly monotone cases, mean-field equilibria become unique. Consequently, as Zeng et al. (2024) also noted, strictly monotone rewards fail to represent MFGs with diverse equilibria.
Theorem 4.3, which supports the efficient execution RMD, novel two respects: RMD achieves LIC, and the divergence the equilibrium decays exponentially. Indeed, one of the few works that analyze the convergence rate of RMD states that the time-averaged policy T =t= T² to time T converges to the equilibrium in (1)=²²) iterations (F. Zhang et al. 2023). Additionally, although it is a different approach from MD, known that applying fixed-point iteration to regularized MFG achieves an exponential convergence rate under the assumption that the regularization parameter À is sufficiently large (Cui and Koeppl 2021). In contrast, our work includes the cases if À is small with 7) 1²", where note that 17" depends À though (D.5).
Regularized MFGs:
14

---

Optimization-basel methods for MFGs: In addition to Mirror Descent and Fictitious Play, new type of learning method using the characterization of MFGs as optimization problems has been proposed (Guo et al. 2024; Hu and J. Zhang 2024). In this work, the authors establish local convergence of the algorithms without the assumption of monotonicity. Specifically, is proven that an optimization method can achieve LIC if the initial guess T." of the algorithm is sufficiently close to the Nash equilibrium, which cannot be verified a priori. In contrast, our convergence results state "global" convergence under the assumption of monotonicity of the reward. We note that the monotonicity can be checked before running the algorithms to ensure convergence of PP and RMD.
The authors in Zeng et al. (2024) and C. Zhang et al. (2025) have recently developed algorithms that sequentially update not only the policy x but also the mean field μ and value function. These algorithms have advantages over conventional methods in terms of computational complexity. On the other hand, in theoretical analysis, restrictive assumptions such contraction are still being used, and there is room for improvement under the monotonicity assumption.
Mean-field-awazd methods for MFGs:
A.2 Comparison of MFG and related games
In research on the method of learning in games, regularization of games is often studied in order to improve extrapolation. For example, Geist et al. (2019) gave unified convergence analysis method for regularized MDPs. (Lconardos et al. 2021) also discussed unique regularized equilibria of weighted zero-sum polymatrix games. On the other hand, it is a difficult task to apply the same theoretical analysis methods to MFG as to these games. In Remarks 3.3 and 4.7, we confirmed that the mean field j MFG can hinder convergence analysis. the following two paragraphs, we will describe more specifically the difficulty of applying the methods used in other games to MFG.
Sequential imperfect information game in Pérolat et al. (2021) vs. MFG: Pérolat et (2021) focused on the reaching probability p over histories in sequential imperfect information games, or extensive-form games. In contrast, we focused on the distribution of states μ m | in MFGs. The dependency on π is fundamentally different: P depends on in linear-like manner, while our μ has highly nonlinear dependency on ı thorough the function m defined in (2.1). Addressing this nonlinearity required novel techniques exploiting the inductive structure of (2.1) with respect to time h.
MDP vs. MFG: The known argument in Zhan et al. (2021, Lemma 6) cannot be directly applied to MFGs. The main reason that the inner product (Q)(s), x
p) in the right-hand side of the three-point lemma concerns the policy at iteration index h + 1, not k. In our analysis (as shown on page 18), this term is transformed into (Q* (s), x² (s) - p). which allows us to apply a crucial lemma (Lemma E.4) that holds for MFGs. This transformation is non-trivial and essential for our analysis. In the three-point lemma, the term Da, (T x (()) appears as a discretization error. In contrast, our analysis derives a reverse version Da- (n **+1). ). This distinction is significant, especially for non-symmetric divergences such as the KL divergence. The reverse order in our analysis is crucial for the theoretical guarantees we provide.
B Proof of Theorem 3.1
Proof of Lemma 3.2. Let update rule (3.1) and Lemma E. we have
be mean-field equilibrium defined in Definition 2.3. By the
0f (s) [1((s)
1 riat (8, ( k+1 (1tt)-- A log
(Th.
-oo=ottt((0 S S0,
for each [H]. s S and N.i...
(RL(TT(S), d (s)) (TL( (f)) - DK k+ (s), (s)
< 1 ( (s, ", oht1, ,+1) (o r))(s))
(B.1)
Taking the expectation with respect to 8 ~ pij and summing (B.1) 1) over [H] yields D Dy (T*, xtl)- Da (IT", of) + D (a h+1 o*)
15

---

H Eonpi (0 (s, (s, okt1 p (o -
h=1 By virtue of Lemmas E.2 and E.4, we further have
Σ Eawpi ((o (s, o o (1 (, m
S JA (utt _outt) - JAio" (u*+),,,) ,,²) ADz (T" ,0 + AD p- (ottt, ,0t)
Joi (n', oot11) Ja.od (1* , T²)) ADn (T' ot) + AD (ottl, ,tt)
S I(u", "i(m"oohtly ,utll ,(",,²) -DDpa11 x²*) AD (akt1 oth)
where we use the identity JAMo (T²,.T) = J[,", σ)) - AD ( 0²) for a E (A(A)S) and Definition 2.3.
C Proof of Theorem 4.5
Proof of Theorem 4.5. Let hT:RIA - I be the convex conjugate of h, i.e. he" 1((w))
EaEa (xp(v(a)) for E TR. RRAA,, From direct computations, we have
d
Du- (== x²)
dt
H
Σ B B h=l
DKL so (s), (s). (s))
dt
( 1 (s)
Σ E Bg
(s) dt (
H
1 (s)
(s, (s,,,,,,,, - > Alog क (a s)
E
E
(b) / (als)
oh (a 8)
h=1
H
Th (a 8) ) oh (a
(mhh ( -x)) Q² T", 1 - X llgg
h=1
Σ
E Benue
K (i))s (s. nt. p')i A Σ E Eanpi
{(1th- -))
log (
on (s) )
We apply Lemma E.4 for the first term and get
Σ Benus ((Th (8), 2h (8, , m [())]
(C.I)
-a (H', x²) - joi (n', x") - AD (w", 0) + AD (N'
Similarly, we apply Lemma E.5 for the second term and get
Esupi (isi (s),,,,, log (s) ) on (8)
Du- (T',
( .)) (=' 0)+ (==" (C.2)
Combining (C.1) and (C.2) yields
d D (w", n²) = J (1', ((u,,=))) x²) - J2. (n², (1²,=*) x²) - AD (=),
dt
By virtue of the definition of mean-field equilibrium and Lemma E.2, we find J² n²) Ja (H', x*) s ja (1²", x²)
ja (H² の <
Therefore, we obtain
(== (,= < (=="
16

---

Proposition C.1. Under Assumptions 2.1, 2.4, and 2.5, there exists a unique maximizer of JA (4², (A(())))) + R. for each k E N.
Proposition C.I also leads the uniqueness the regularized equilibrium introduced in Definition 4.2. To elaborate further: Suppose there are two different regularized equilibria (μī, wi) ) and (22, wa)). If we assume wi + wi. the following contradiction arises: From Lemma E.2, we have
(At wi) + J wn) S J =5) + JA (1S, wi).
Additionally, from Proposition C.I, we know that JA ( =i) 2 (A wb) and JA (ug wx) (n 2 (us, wi). Adding these two inequalities gives us JA wi) + JA (1², =5) 2 (A =5) J (1g, wi)
(12,
Therefore, wi Φ. Moreover, by the definition of regularized equilibria, μu m = m[=3] μ.. This contradicts the assumption that the two equilibria are different. Thus, the equilibrium is unique.
The uniqueness of Proposition C.I itself is a new result. The proof uses a continuous-time dynamics shown in Theorem 4.5, see Appendix C. In the following proof, employ the same proof strategy in Chill et al. (2010, Theorem 2.10). Before the proof, set u (T)) TT (a
Th (a s) (Q) (s, a, n, m(x)) Alog
for π E (A(A)5)).
Proof of Proposition C.I. The existence is shown by slightly modified version of (F. Zhang al. 2023, Theorem 2). It remains to prove the uniqueness. Fix the regularized equilibrium w" E (A(A)))
First of all, we prove the global existence of (4.5). By the local Lipschitz continuity of the right-hand side of the dynamics (4.5) and Picard-Lindeles theorem, there exists unique maximal solution æ of (4.5) with the initial condition T|e-g n². Namely, there exist T E (0, +oo] and æ: [0, - IR such that n is differentiable on (0,7) and it holds that (4.5) for all / (0,T). Thus, Theorem 4.5 ensures that
( + (w-( d S ( )= = <<< +o0, (=)"t",,
for every E (), As a result, the trajectory far E (A(A)S) L (0, is included in K. = E (A(A))) Dp-(=", & c). Note that K2 is compact from Pinsker inequality.
Since the right-hand side of (4.5) is continuous on K., we obtain SuP be (Tt) || < to0.
Thus, the equation (4.5) implies continuous function on [0, T].
de is uniformly bounded on [0, T). Hence, " extends to a
To obtain a contradiction, we assume T < +00. Then, there exists the solution n' of (4.5) on larger interval than with new initial condition n' r'|r=r xT, which contradicts the maximality of the solution r.
Therefore, the limit lim nt exists and is equal to w". Here, w" is arbitrary, the regularized equilibrium is unique.
D Proof of Theorem 4.3
We easily show the following lemma by the optimality of 41+1 in (4.4).
Lemma D.1. It holds that
( (
n [²)) Alog
++1 Th
[t)(ss)
(s)
- log Th
++ (s)
0.
(s))
for all 8 RIAI such that 5(a) 0.
17

---

We next show that (x")e is apart from the boundary of A as follows.
Lemma D.2. Let (TT)) be the sequence defined by (4.4) and w² be the policy satisfies Definition 4.2.
Assume that there exist vectors why and (x())) E RIAA satisfying
wh (a s)
XH log minn S wg (a 8) -XH log min:
Oh (a 8) exp
w (a 8) À
2XH log miin I <w (a 8) S H,
T (a 8) x exp
for all A. (A(A)S) h E [H] and S. Then, for any h [H] S, and t 2 0,
holds that
max {[llog म (+)] |oog (+)] H(1 X log minn)
loglAA.
Proof. We first show that ग can be written as
wh (a (als8) (s)
क (a s) & exp
(D.1)
A
for vector wf, (s) E RIA satisfying 2AH log miin S wt (a 8) S H. We prove it by induction on t. Suppose that there exist E N and wf satisfying (D.1). By the update rule (4.4), we have
++1 (a 8) x (on (a a))* (a s)) -- exp (no (s.a.
Ymao, (a 8) + - Ayu (a 8) + An 2 (s,a,
α exp
A
Set w (a 8) == bnug (a 8) (1 n)) + Xn (s, a, x', ,d)), we get m (als) (a1)
From Lemma E.3 and the hypothesis of the induction, get 2AH log mmin S wht1 (a] S H.
Then we have for any a1, ag A: T (a1 6) = exp
wh (a1 8) wht (a2 [0) 5)) S exp
H(1 - log minn)
Sexp
T/. (a2 s)
A
It follows that:
H(1 Alog mmin)
H(1 A log mmin)
min n (a|s) 2 exp
max o (a 8) 29 exp d'EA
aaA Therefore, we have:
A
A
H - Alog mmin)
log T (s)
+ +log/A/.
A
From Lemmas E.1 and E.3, have for TH and a1, a2 E A:
"x (01 8)
" (s, a1 T², .²) + wx (a) 9) Q²:00 (s, a2, T ,','')))))))))))))' p²))
wg (az s)
cxp
Th (0g 8)
((1 Alog min))
< exp
X
and, we get |llog / (s)]l
H(1 H(1->loR log|A/.
T (a 8)
Lemma D.3. Let G (s, a n", ,²²) = Q,: (s, a' xt, Alog
Th (a
(s, x', ,1²) G\."' (s,
H
< 2L
|lf pi 111 (E + ((,a,xx''="))
t=h
for a, d' E A. Here,
C,a.H, = 2A
min'
+ 2(1 H) X(1 + 2H) log amin + Bolog [A],
18

---

and
8/t 8, an = a S1+1 ai) a: ~ 5j (st) for each E {h..... H
H
Fx(a,",, w²) = E
m (8t) - (s))))
1=
Proof of Lemma D.3. We first compute the absolute value as follows:
G (s, ,²) Ch (s, (s,d', x², ,4')
(s, - Alog
h (a 8)
( (s, - Alog
Th (a' ())
h (a 8)
Th (a' (s)
(s, ) Alog
t (a s)
(s, ,0, ,²)= A Alog Tn (a' 5)
b (a' 8)
Th (a s)
(0 (s, n' n²) Qn (s,0, ,²))"))))))))))))((
wi, 1 (oh (s, a ,4) O₂ (s, a' "
(D.2)
By Lemmas D.2 and E.I, the first term of right-hand side in (D.3) can be computed as
T s)
(s, "h ".. :1) )- Alog T (a' () on (a' 8) Allog % (a' 88) (a' 8)
0n (a 8) Q, (8, a, "., ,1²) log
Alog / (a 8)
# (a 8)
Aoog /y (a' 8)
A Alg
Th (a 8)
(a s)
-
on (a' 8)
s)
x (a' ())
log
+ log
Th (a
T
(a' s)
+
(|// (a
th (a {) + | (a' s) ~ (a' |s]])
min
millaeA R (a 8)
H(1 A Alog Ominn
< 2||A| exp
(1= (a s) - क (a $) ا (a' (s) th (a' s)))
A
(D.3)
By Proposition E.8 and Lemma E.6, the second term is bounded as
(0 (s, (s,a, n², x². Q/ (s,
w',,") (s,,,"",,")) (0 as, w²) Q "','',"'''''
H
$ 2L Σ ||ę - 11ll1
1-h
8h41 PR (o s,a),
+ Ca "
Σ
|T ~/(())
8141 ai),
ai t (s)
1=h+1
for each / E {h 1, H}
8h+1 Pa (o ( s,a"), 8141 P((st, at);
W')
(s:) -()))((ss))))
w (81)
1=1+1
for each / E (h 1,.... H)
Furthermore, CA (T w
can be bounded as
A.o (TT w ) 522 - A log amin + 21 H(1 - > log Omin)
+ log A
A
2(1 + H) X(1 + 2H) log amin 2x 1ogog/ All.
Proof of Theorem 4.3. Set
C==4F² 4
12
(D.4)
|A| exp
H(l A log min!
19

---

1(1-A log "min"
2
+ +2(1 + H) X(1 2H) log min + 2A log [A]
-1H?
L²² +
A 11 min!
A 1 CAI)
17 min 2H +
(D.5)
2C'
where C, is the constant defined in Lemma D.3. We prove the inequality by induction on t.
(I) Base step 0: is obvious.
(II) Inductive step:
Suppose that there exists t E N such that n' E Q. Lemma D.1 yields that
D (wo, ,
D2 (w=",x'' D' (x xl11)
5 (s)
L8 Eanui
log
(5) - -
1+1 (s) h
H
K I "
Q (s, , x'²) Alog
F (8)
(0 -
An
(n(s)
h=1
E
(s
Ao (s, o, n" p'), (0/ (
Xn
(D.6)
Xn
H
E B K log
(s)
(s) ( - 10-m++))p (s))
+ 1 An
h=1
"
(AD (0) (x .0))
1 1 An
Xn
(Dp- (w=" -0)- - -D (==", x 12) Dp (T 1+ (nrtt1,))) ,)))
+ 1 Xn
Ay (=0""=",m"" )
1 An
where is bounded from below as follows: By Lemma E.4, get (r (nt+1 w') - S ~ x x111 + AD (w", о) AD - (T e+ .0). By virtue of the definition of mean-field equilibrium and Lemma E.2, we find jam0 (p (p w²) ja (nt +1 2 j (n", w-) J (n x21 0.
== A
Then, we obtain
12 (D' -ADp- ,0).
For the last term Dn- (Tt,, n of the leftmost hand of (D.6), we can employ similar argument
to (Abe et al. 2023, Lemma 5.4), that is, we can estimate Dp- (T², =(+)) as follows: Set G(a) =
Gh (s, a, n", ,²) = Q,, (s, a, T", p²) Alog T) (a 8) Note that max (eAl (G(a') G(a))
σh (a 8)
20

---

7"' by Lemma D.3. By the update rule (4.4) and concavity of the logarithmic function log, we have
Du (T'; x
H
Benuy
Σ Th (a 8) log
T (a
s)
++1
(a | 8)
h=1
LaEd
h
(on (a |s)) (x) (a' s)) exp (nOR ( nt, at)
Σ
H E
Σ
th (a log
a'EA
exp (on (a 8)) (TT (al 8)) A exp (mohh (s, a, Tt, ,ti))
/=1
aEd
T Ta 8)
Σ
t (a' s)epp n1th ( (s, x², ,14) - \n) log on (a' 8)
H1 E B
Σ aEA
Th (a 8) log
d'EA
10 (s, ot (4)- - An 5 (a ((1s))
5)
exp
on (a 8)
Σ mh (a' s)exp net (s, x' .0) 10,
xn log T (a' 8) on (a' 8)
H
B
log
Σ
The
(a s)
d'EA
x², 11, - An T (a exp (s,
1=1
aEA
0h (a [}]s)
(D.7)
If we take 17 to be 1) S n7,, it follows that
$ for a, a' E A. Thus, we can use the inequality ex S + x2 for x S 1 and obtain
Dy- (1)
11
log Σ hh (a I 8) m (d') ((0))))))a(
Exspi
h=1
a,a'EA
H
EsnpA
log Σ
कx (a () (d'l 8) () G(a) + + - -(a)))))())))
-
hm1
a,A'EA
log Σ क (a (a'1 8) (d)) (1
E Egnpi
4=1
a,a'EA
Σ Ta s) ( - ((G(d))((o))) ]
E Egnpi
log 1+
a.a'EA
1)²
2
E
(a () T (a' (
A=1
a.a'EA
By Lemma D.3, we can see that
Σ Th (a 5) m/ (a' (d'1 (G((a))-((a
a.E'EA
H
2
Σ
Th (alls) ()) (a' s)
22
Σ
|nf - pīll; + CCN.HMM(EEaaaT + En'd', Ex(d,
EAA'EA
t=h
H
|ui mill. 1) 2
(BRla, (0)) + ERla', ,',') * (CRR
Σ the (a m/ (s)
8L2
Σ
+
a.
H
< 21,
Σ
| 1ill? + 8 ((ChraBil
2 Σ
कB (a (a) E
1=h
aEd
21

---

H
1ill + 8 (CCAoNBl)))) 3
T (a
8L2 Σ
||4
wh (a 5) (',,
w (a 8)
1=h
H Σ
8(CA,,,H.1A))
< <8L2H
|
1h (a 8) ('
|A] exp
11(1 log miin)
1=h
aEA
H1 > 1=h
811 (I)
H
< <812
|14
mill?
[ - m(
AA| exp
H(1-Alog min)
1=h
H
4H (H(Co..,,A AI)
< 8
2
1l4
Du (w²",²')
|A| exp
/!(1 [[(1-Alog mmin) ming
Moreover, Lemma E.6 bounds
i=
ll
/r 11 as
11
H
1 H
[| - ={(())]1?) - 2
D (00
1=h
1=h k=
Therefore, finally obtain
(=- π x - (1 - xy + ;0) = 2
Du- (5'
(D.8)
where we use On S Ci¹² < 1/2.
E
Useful Lemmas
For Mean-field games, one can write down the Bellman optimality equation as follows: for function Q':S + A(A), policy T':S + ((A), o':S - ((A) and E 8 set
f (Q', Lemma E.1. Let (4", w²) be equilibrium in the sense of Definition 4.2. Then, it holds that
xs), - ADKL A (s), (s)).
(E.1)
(i(()) arg max f (Q) (s. ( :2))"") x on (o exp PEΔ(A)
(s, o, w0" x0,,²")
for each E S and h E [H]. Moreover,
(Q) "s," log
T Th
5 0,
for all 8 E RlAl such that 6(a= O.
Proof. See the Bellman optimality equation (e.g.. (Agarwal et al. 2022, Theorem 1.9)).
Lemma E.2. Under Assumption 2.4, it holds that, for all n, E (A()))) Ja (m[x]. T) + J (m|7], H) Aa (m|T]. T)) JA (m|7), π) < 0,
where m is defined in (2.1).
Proof of Lemma E.2. The proof is similar (F. Zhang et al. 2023, SH). Set = m[nT] and m m
One can obtain that
JA. (mim), J (ml7), JA (m(T), Jm
J JA + (J+ (7.
Σ
Σ
(sT Σ
Th (an sn) (rn (Sh, ar, m4) rh (Sh, ah Fi.))
1= S
arEA
H
(sN) Σ
N (an 8h) (rn(sn, an, T.)) (h ah, (h))
EA
22

---

Σ (Th (a s) (a(s) tr (a s) (r))() un. (2h an. ph)),
R,s,a
and the right-hand side of the above inequality is less than 0 by Assumption 2.4.
Lemma E.3. Let V/A.0 be the state value function defined in (4.2) and Q be the state action value function defined in (4.3). For any 8 A, E A, and h E [H) it holds that
X(H 1) log m S V/Xio (s, σ S h h+ 1,
A(H - h + 1) log min - 2% (s,a, - -
Proof. We prove the inequalities by backward induction on h. By definition, we have
VAA (.
E
(r(ss,,a,,1)) pi) (D))(
sh.
(ra(s, (n),
TA (s))
Σ V (8141,1447
Σ REEA
Pn (8N+1 8, an (an
#h+1ES
< 1 + max
V (8++1.H4T).
and
(s,
(rn(s, ,, (4), (s))) - (TK)(TA(SA))
Σ
VÀo ( Σ
Ph (88+1 sn an (an
BR+IES
RKEA
2 A log min
+ max VAA V (3441,117)
1EI
Then, we have
V (s,p, E [X(H h 1) log m 1).
by the induction. The definition 2 in (4.3) immediately yields the bound.
Lemma E.4. For all n, E (A(A)))H, it holds that
H
Eg [7)n [[ ((ITA #s)(s), Q² (s. m.
E
J (u, T) - jir (H, AD ( AD m
where set u m(r]..
23

---

Proof. From the definition of VA and Qa in (4.2) and (4.3), we have
(TT((s), 2210 _,,,,,,,))))
E mm//l
H
B Ba
(T) , 14) + E Vi4 (8141,14,7) 8h41 ~ P(s, (mm)
E B1 (s (sh pn) (Dk AD (T.
/=1
H
E Eg
Whti (96+1,
8h41 P(s, an, Un), an ~ [o(
(E.2)
h=1
H
sh+1 P(s, ah Mh), an ~ n (s)
E si sm [7]a
Vil (sh, - E
h+t (941,,41,
h=1
Σ EE Ba
E
vida (5h+1,1447)
sh+1 P(s, ah ph), (8)
H
E Ba
(s, (2, + AD (T,
Similarly, (4.1) and (2.1) gives us
E Bawm/Rla (3
H
Es, Bm [5]a (4) [rn(sn, mn) (Fs(( + AD ADmpF(TTTo]
(E.3)
E B [7)n
E Vida (8h+1,14,
8h41 ans Un), (s)
h=1
H R #h+t
~Aa () + Am (T, σ)
+
[V (s.
Combining (E.2) and (E.3) yields
Fa [7 ((TH - (5) (i))),Q"" Qx ,,
+ (DmiH)(TTOO))
smm 7]
(A, + ADm
Σ B Berm(f h=1
v Vari(s.1.)))
(Ba-m[R) (y)i0((s, ,1,
AD (T, (=
(JAi (4. AD (m.
Egrya [V- (s, m)
J2. + +A AD (m)
which concludes the proof.
Lemma F.S. For all n. 7 E (A(A)))) it holds that
E Baum(Fix ((mm-7))(s) (s). log
Th m1(s)
)
(m (m, + ()
0% (s)
24

---

Proof. A direct computation yields
((m (m)))))) log
Th (5(
(s) |
E ma
H
[7], [ (Tn(()),0g (s(s)
(s)
(m. - -E
Buwm [F],
log
(8)
((s)
h=1
= (m - - + Dm(
Lemma E.6. The operator m defined in (2.1) L-Lipschitz, namely, it holds that
|m[ - -m[=011+ $
<ΣE, Eagmm( [[] - x/(s:)]ll,
(E.4)
1m0
for n, I' E (A(A)))) and all E , H.. Here, we set no(s) Tt( = U for all s E S.
Proof. Fix q. x' E (A(A)S) We prove the inequality by induction on h.
(I) Base step h = O: is obvious because || [r][=] m [r]] I1 = || Hi 0.
(II) Inductive step:
Suppose that there exists [H] satisfying the inequality (E.4). By (2.1), we
obtain
|| [ h++ - mm(7)//12
Σ Sh+2E8,
Ph+1 (8142 9441,04+1 m (x) (an+1 (8441) Th+t (an-1 (8++1)
(9h-1,0h+1)ESK4
Σ
Ph+t (8h42 8841, a2+1) Th41 (an+1 5h++1 ( mmlaa// (88+1)]
(ES
Σ
ml=]a+1((h42)) Mh41 (an+1 (8h+1) Th+1 (an+1 (att))
(#h-1
+
Σ m(4))+1((h41)) m(n') [ (Sh+1)
#44188
E. Eentromiiii The ( - F I]] + [[m[[]]+] ( m
By the hypothesis of the induction, we finally obtain
[m[m]a+2 [1]7]]++2l
< E Egom|That (0)))())) t = (6) Σ E [| - (+))]
h+1
E am (s) [|](()) x
Lemma E.7. Let n. n' E (A(A)))" μ. 1l E A(S),, s sE S, and h E (1....,, H 1}. Assume min min( (a s), (a s)} > 0,
and set MH+1 = ph Us. TH+1(s) = (s) for all S.
V/ (s, T. ViA (s, ,4/)
=
H+1
S141 ~ ((((),)); 01 Ml (st) for each / (h...., + 1}
<
E
Σ (C* a((31)]l1 Lll pillz)
25

---

for Here, (T. T') > O is defined in Proposition E.8, and the discrete time stochastic process
(si) induced recursively as 8t+1 P(( a), oi Ti (3)) for each I {h..... 1}.
Proof. Fix n. x', and p². We prove the inequality by backward induction on
(I Base step h H + is obvious because Vi+ (8, 1T) Vt ( =10 0 0.
(II Inductive step:
Suppose that there exists / E [Hf] satisfying
N4t (s, n. n) (s, .1)
Sh+1 8, 81+1 P((S), at),
#+
<
Σ
m(())) + Lllea - pálli) (TT
0f ~ x (s)) for each 1 E {h + 1.....
1=h+1
H + 1 (E.5)
for all 8 E S. By the definition of the value function in (4.2) and Assumption 2.5, we have
VA p,) v (s, ,2)
(Th (an 8) rm an an. n/K (an 8) s)ra(s, ah))))
A
+ (T))
Σ
Pa (sh+1 s,)n)
Th (an 8) ( x (an 8) V at' (1))
On E.A. 1A-1ES
< (s) (1)(1)11++ +
Σ arEA
Th (an (s) (rn an un) r/ (n an, Hh)!
log Th (an s) -1) thh (an (s [lo ThK (an s)
))
+
Σ
(an (s
oh (an 1))
on (an ())
a.EA
(|)T(s) Th (8)]l1
Σ
Ph (sh+1 1s, an) on (an (s) V2 T,) (s x'm'')
anEA.
88+1ES
< (s)
(8) Tallpn phlll
1 (OTTT)) nn (a s) [|] - - (+)]1
+ A max log (h,a,8)
Ph (sN+1 an) on (ax 8) Vili (s TI) - V (s Rl)
A.E.A
< S - Dllea 1hhl11
+ V (s
V (s (8 .n)
8h+1 ~ Ph (Sk, an);
ah TA (8h)
Combining the above inequality and the hypothesis of the induction completes the proof.
26

---

Proposition E.8. Let Qa.a be the function defined by (4.3), and x', E ((A(A)S)")} be policies with supports. Under Assumptions 2.5 and 4.1, it holds that
Q as Q (8, .n))
H
S L p4 pill CA, 1=h
Σ J=
[[T(())) -/(()))) Sn.
for s,)) E [M] x S A and p. A(S) Here, the random variables (st)f=h+1 follows the stochastic process starting from state at time h, induced from P and n, and the function Cho ((A(A)))H) + R given by Chi (m, x²)
in (h.,,a) x|x log (awx²) (a. s)-
Proof of Proposition E.8. Let h be larger than 2. By the definition of O given in (4.3) and Lemma E.7, we have
2 (8, 1 nT, (1) - 2 (8, u, .1)
< Th-1 (5, a. 1h-1 - Th-1 a, ph-1)) + Es (s.a) Vi (shr T, (1) V (sh+ मं .N)
< - - 1h-1ll +
V (sh, n, H)) (sh,
( nT, pt) n²)]
Combining the above inequality and Lemma E.7 completes the proof.
F
Experiment Details
We ran experiments on a laptop with an 11th Gen Intel Core i7-1165G7 8-core CPU, 16GB RAM, running Windows 11 Pro with WSL. As is clear from Algorithm 1, APP is deterministic. Thus, ran the algorithm only once for each experimental setting. We implemented APP using Python. The computation of Q*.a and in Algorithm I was based on the implementation provided by Fabian et al. (2023).
Algorithms. In this experiment, implement APP in Algorithm 1. implement RMD (i.e., Algorithm without the update of σạ) in (4.4), For both algorithms, the learning rate is fixed at 17 0.1, and we vary the regularization parameter and update time T to the experiments.
For comparison, also
We show further details for the Beach Bar Process. {-1, +1}, 0.1,7 = 0.1, and
We set H = 10, [8| = 10.A =
1-8
if = +0 & =
6
Pa (8' 8,a)
if +1 & s' 11,
otherwise,
where we choose 0.1. In addition, we initialize σ and 0 in Algorithm 1 as the uniform distributions on A.
Remark F.I. When the contraction factor 1 - Ar is close to 1, we can observe small can lead to instability in the outer PP loop.
27

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The introduction clearly states the two main contributions--LIC for the proximal-point update (Theorem 3.1) and exponential convergence of RMD (Theorem 4.5)- and these match the theoretical and experimental results presented.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
(ii) Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper includes 6 on limitations of the applicability of our theory.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
(iii) Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer: [Yes]
Justification: All assumptions are stated alongside Theorems 3.1 and 4.5, and detailed proofs are provided in the appendices. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
(iv) Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: Appendix gives full details of the benchmark (Beach Bar Process), hyperpa- rameters, and implementation environment (Python, deterministic runs).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
Open access to data and code
29

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The paper provides the code for reproducing the results in $ 5 as supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips...
cetpoomssssoooooiiiiiioo onPolicy icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /náps. wwtppccccc/a/ccccccccccccccccltt wwtpcc/gguu/eeeeee /alesee/oodSmbmii ssiiinoossssiiioooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
(vi)
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: $ and Appendix F fully specify the algorithm parameters, benchmark setup, and evaluation metric (exploitability)
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
(vii)
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Our proposed algorithms (Algorithms I and 2) are deterministic, thus error bars confidence intervals are less meaningful.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
30

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
(viii)
Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix F reports execution on an 1 1ith Gen Intel Core 16-17 CPU with 16 GB RAM under Windows 11 Pro (WSL)
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
(ix)
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
cc Coubblcc/tticsGuicee
Answer: [Yes]
Justification: The work foundational and does involve sensitive data, human subjects, or applications raising ethical issues.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
(x) Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: No broader impacts discussion appears in the main text or appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
31

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
(xi) Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The paper does not release high-risk models or datasets needing special safeguards.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
(xii) Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No license or terms of use are specified for the external implementation by (Fabian al. 2024)
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
32

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comdattasess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
(xiii) New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new datasets or code assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
(xiv)
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No numan-subjec research or crowdsourcing is involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
(xv) Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The work does involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
33

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
(xvi)
Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core methods do not involve any use of large language models.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttaaa://eeeraaaee / for what should or should not be described.
34


Reviews:
[{"review_id": "8K3VCaJ31Y", "reviewer": "Reviewer_Nj5a", "summary": "The paper aims to understand convergence guarantees for monotone finite-horizon MFGs. Existing results have some shortcomings, such as suboptimal rates, assumptions of strict monotonicity, not providing last-iterate convergence, and requiring regularization. This work proves a linear convergence bound for monotone MFGs for regularized MD, improving upon past work. This result is suggested to imply convergence to non-regularized NE by showing that it asmpyotically approximates an implicit proximal point update rule. Experimental evaluations are provided.", "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.\n\n- Theorem 4.3 and correspondingly the update rule (4.4) tackle a similar setting as in Zhang et al., 2024. However, while their analysis only yields sublinear convergence,\n\n- The continuous time analysis of Perolat et al., 2021 is more straightforward than the analysis of the work, although it does not yield the more important discrete time convergence. I am curious to what extent the discretization of the ODE (corresponding to the (O)MD update) proposed by Perolate et al. can be used to still obtain a discrete time result. Clearly, in this work, the learning rate $\\eta$ is quite small, so the results might already be in the regime where an ODE is discretized. This is already somewhat suggested by Theorem 4.4, however, could the analysis directly incorporate the ODE up to a discretization error? To what extent does the analysis differ from standard ODE discretization methods that are used in optimisation literature?\n\n- 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?\n\n- What are the major bottlenecks when generalizing the results to graphon MFGs?", "limitations": "Discussed in the paper.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\nI think the analysis of the work is interesting and potentially a good contribution to the understanding of MFGs and MF reinforcement learning. It is a clean result that is also meaningful for many practical problems.\n\nThe paper is well-written, and the theoretical results are easy to follow. The commentary on the theoretical developments compared to existing work on MFGs was helpful.\n\n## Weaknesses:\n\nI list some concerns below, I am happy to discuss further following the responses of the authors.\n\nFrom the theory side, one major concern is the convergence rate that has been proved. The exponential convergence of Theorem 4.3 matches intuitively the ODE rate, though in discrete time the fraction is $\\left(1 - \\frac{\\lambda\\eta}{2}\\right)$, where $\\eta < \\eta^{\\*}$. Learning rate $\\eta^\\*$ defined in D.5 determines the exponential convergence rate, and $\\eta^\\*$ can be very small. By tracing the results and constants, it seems $\\eta^\\*$ will scale with $e^{-H\\lambda^{-1}}$ and $(-\\log \\sigma_{min})^{-1}$, which might be extremely small. In this regard, while the convergence result is indeed linear, it is difficult to compare it with the sublinear rate of Zhang et al. 2023. Furthermore, since the convergence of APP is not known, one would typically set $\\lambda$ to be small, which exponentially worsens the linear rate.\n\nRelated to this, at some point in the main text, mentioning the dependence of $\\eta^*$ on the problem parameters might be helpful, at least asymptotically. It is currently somewhat difficult to understand how the rate of linear convergence changes depending on the problem parameters such as $|\\mathcal{S}|, |\\mathcal{A}|, H, \\sigma_{min}$.\n\nRegarding the presentation of the results, while I like the exposition, it was not clear if the PP method had implications beyond being a theoretically illuminating tool. As far as I understand, in the current state of the work the convergence of APP is not known, although MD seems to asymptotically approximate PP.\n\nFinally, I am not fully convinced regarding the strict monotonicity assumption. 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}^{\\*}$?\n\nMinor points:\n\n- potential formatting issue at Figure 1\n- Difficult to read axis labels in Figure 2-a", "was_revised": true, "final_justification": "My questions regarding the paper's results were answered. I appreciate the efforts of the reviewers to add further explanations to their paper. I still have minor concerns regarding the magnitude of constants, and the authors have promised to expand on this.\n\nOverall, I keep my positive score.", "rebuttal": "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.\n> it is difficult to compare it with the sublinear rate of Zhang et al. 2023.\n\nFirst, 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.\n\n\nLet 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.\n> 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}^*$?\n   \n 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.\nCompared 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.\n\nWe will next give you an answer to your questions.\n> 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.\n\n 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.\n> 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?\n\n 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)). \n> 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?\n\n 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.\n> What are the major bottlenecks when generalizing the results to graphon MFGs?\n\n 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."}, {"review_id": "1tgfEFzSK3", "reviewer": "Reviewer_K4bh", "summary": "This paper presents a novel algorithmic framework for achieving last-iterate convergence in mean-field games under the assumption of non-strict monotonicity. Current methods often require stricter assumptions like contractivity or strict monotonicity, or only guarantee the convergence of time-averaged policies. The authors' approach is twofold. First, they introduce a Proximal Point method with KL-divergence regularization. They provide a proof that the last iterate of this method asymptotically converges to a mean-field equilibrium, a result established without requiring strict monotonicity. Second, they observe that each update of this PP method is equivalent to finding the equilibrium of a KL-regularized MFG. They then show that this regularized subproblem can be solved by the Regularized Mirror Descent  algorithm with an exponential last-iterate convergence rate, which is a significant improvement over previous polynomial-rate or time-averaged results. Based on these theoretical insights, the paper proposes the Approximate Proximal-Point algorithm, which uses a finite number of RMD steps to approximate the PP update, and demonstrates its empirical convergence on a standard MFG benchmark.", "questions": "1.  The APP algorithm's performance seems dependent on $\\tau$, the number of inner RMD iterations. The experiments show a difference in performance between $\\tau=10$ and $\\tau=1000$. What is the primary theoretical obstacle to deriving a convergence guarantee for the combined APP algorithm? How does the approximation error from using a finite $\\tau$ affect the stability and convergence of the outer PP loop?\n2.  Could the authors elaborate on the technical challenges specific to MFGs that complicate the convergence analysis? The paper correctly points out that the mean-field dependency, where the policy iterate $\\pi^k$ influences its own update through the mean-field $\\mu^k = m[\\pi^k]$, is a key difficulty not present in standard N-player games. 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?\n3. Could the authors discuss how the RMD differentiates from that in zero-sum game (see e.g. [1] [2] ). 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])? A discussion clarifying the relationship to these works would further strengthen the paper's positioning.\n3.  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. Is there a theoretical relationship between these parameters that would guarantee convergence for the overall APP algorithm?\n\n\n\n**Numerical Scores:**\n\n* **Quality & Technical Soundness:** 4\n* **Clarity:** 3\n* **Originality & Significance:** 3\n* **Overall Score:** 4\n* **Confidence:** 4\n\n\n\n\n\n[1] Cen, S., Wei, Y., & Chi, Y. (2021). Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34, 27952-27964.\n\n[2] Park, C., Zhang, K., & Ozdaglar, A. (2023). Multi-player zero-sum markov games with networked separable interactions. Advances in Neural Information Processing Systems, 36, 37354-37369.\n\n[3] Ao, R., Cen, S., & Chi, Y. (2023, January). Asynchronous Gradient Play in Zero-Sum Multi-agent Games. In International Conference on Learning Representations (ICLR).", "limitations": "The authors provide a good discussion of the paper's limitations in Section 6, correctly identifying the model-based setting, the focus on iteration complexity over per-iteration computational cost, and the lack of analysis with function approximation. The most significant limitation, which is mentioned as a future goal but not framed as a limitation, is the absence of a convergence proof for the main APP algorithm. Moreover, it would be more concrete to discuss the relationship between the RMD in the mean-field game with that in Zero-sum Games and its adaptivity to the asynchronous multi-player scenarios, as mentioned before. A more direct discussion of the challenges involved in bridging this theoretical gap would strengthen the paper.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1.  **Addresses the Problem Under Weaker Assumptions:** The paper makes a contribution by tackling last-iterate convergence under non-strict monotonicity. This is a more general and practical assumption than the strict monotonicity or contractivity required by much of the prior work, and it correctly includes important cases, such as games with symmetric transitions, where strict monotonicity fails.\n\n2.  **Theoretical Improvements:** The paper delivers two important theoretical results. The first is the asymptotic last-iterate convergence of the PP method (Theorem 3.1) in this setting. The second, and perhaps more impactful, is the exponential convergence rate established for RMD in solving the regularized MFG subproblems (Theorem 4.3), which improves upon previous results that showed polynomial or time-averaged convergence.\n\n3.  **Well-Motivated and Elegant Algorithm Design:** The proposed APP algorithm is a well-motivated and practical method. The insight to frame the problem as approximating an intractable PP update by using RMD to solve a sequence of regularized MFGs is elegant.\n\n**Weaknesses:**\n\n1.  **Lack of Convergence Guarantee for the Proposed APP Algorithm:** While the paper provides convergence guarantees for the idealized PP method (asymptotic) and the RMD subproblem solver (exponential), it does not provide a formal convergence guarantee or rate for the final, practical APP algorithm (Algorithm 1). APP approximates the PP update with a finite number of RMD steps, introducing an error that is not theoretically analyzed. The authors state that deriving a convergence rate for APP is a conjecture and a future task.\n\n2.  **Reliance on a Model-Based Setting:** The entire analysis is conducted in a model-based setting, where the transition kernels and reward functions are assumed to be known. This assumption limits the direct applicability of the theoretical results to many reinforcement learning scenarios where the agent must learn from data without a model of the environment.", "was_revised": true, "final_justification": "After carefully reviewing the rebuttal and author responses, I am raising my score from 4 to 5.\nResolved Issues:\n\nThe authors provided clear explanations for the theoretical obstacles in proving APP convergence, particularly the challenge of vanishing regularization mass as $\\eta\\to 0$\nThey clarified the key distinctions between MFG and zero-sum game settings, especially regarding asymmetric vs. symmetric regularization\nThey demonstrated understanding of how their techniques (Łojasiewicz inequality, value function analysis) address the unique challenges in MFGs\nThey committed to adding discussions on connections to related work in multi-agent learning\n\nRemaining Issues:\n\nLack of formal convergence guarantee for the practical APP algorithm remains the primary limitation\nThe model-based setting assumption still limits direct applicability to model-free RL scenarios\n\nWeight Assessment:\nThe theoretical contributions (PP convergence under non-strict monotonicity, exponential RMD convergence) are significant advances that outweigh the remaining limitations. The authors acknowledge these limitations honestly and provide a clear research direction. The promised additions to contextualize their work within the broader literature will strengthen the paper's impact.\nRecommendation: Accept. This paper makes solid theoretical contributions to an important problem and presents a well-motivated algorithm, despite some remaining theoretical gaps.", "rebuttal": "Thank you for reviewing our work. We respond to your questions below.\n\n> What is the primary theoretical obstacle to deriving a convergence guarantee for the combined APP algorithm?\n\nIn 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.\n\n> How does the approximation error from using a finite $\\tau$ affect the stability and convergence of the outer PP loop?\n\nA 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.\n\n> 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?\n\nMean-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$.\n\n> Could the authors discuss how the RMD differentiates from that in zero-sum game (see e.g. [1] [2]).\n\nIn 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.\n\n> 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])?\n\nConceptually, 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.\n\n> 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.\n\nIn 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.\n\n> Is there a theoretical relationship between these parameters that would guarantee convergence for the overall APP algorithm?\n\nDue 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."}, {"review_id": "I3oEOkBt11", "reviewer": "Reviewer_YWXi", "summary": "This paper studies a monotone mean field game without strict monotonicity. It proposes a proximal point-like algorithm that can solve the regularized version of the MFG exponentially fast. Numerical experiments also validate the proposed algorithm empirically.", "questions": "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. \n\nCould the poly-> exp improvement on the convergence rate be attributed to different feedback types as Dong et al focused on bandit feedback?", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is nicely presented with sufficient explanation and insights into how the algorithm is developed. \n\nStrength: the proximal point like algorithm is very well explained with figures to aid the understanding of it. The intuition from the continuous time version of the algorithm also help motivates and bridge the connection to previous work on continuous time mean field algorithms. \n\nWeakness: 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. From my brief skim of the proof, I cannot tell the technical novelty of the analysis and I am not sure if it could be straightforwardly extended from the existing analysis.\n\nI am not fully convinced by the contribution of this work because the proposed proximal-point–like algorithm does not appear significantly different from the extragradient-type algorithm used in Cen et al. (2023). Although the authors argue that the main challenge in extending the analysis of Cen et al. (2023) lies in the backward induction of the Q-function (Remark 4.6), this issue is already well-known in monotone mean-field games and has been addressed in Zhang et al. 2023 (Section F) and Dong et al. 2025 (Lemma B.1). \n\nOne key difference between the two work lies on that Dong et al uses the naive mirror descent algorithm, while this one uses the proximal point like algorithm. Combining bandit feedback is difficult with the proximal point algorithm, so I would have expected that the improvement on the convergence speed stem from here. Similar reasoning can be applied to Zhang et al. One improvement of the results in Theorem 4.3 is that it improves the terms in Equation E.1 that are due to the exploration with bandit feedback (Lemma I.3).\nBut we only care about the full information feedback, the exponential speedup brought by the proximal point like algorithm, combined with the speed up from not having to explore,  is not too surprising an this combination is known to be able to do that in regular non-mean-field monotone game (Cen et al).", "was_revised": true, "final_justification": "After the reviewer-author discussion, I do agree that the analysis and result, although expected, is new. I don't oppose to the acceptance of this paper.", "rebuttal": "Thank you for your feedback.\nFirst, 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).\nWe answer the following comment and question:\n\n> 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.\n\n\nThe 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).\n\n\n\n\n> 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.\n\nFirst, 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.\nFurthermore, 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.\nThe 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.\n\n\n> Could the poly→exp improvement on the convergence rate be attributed to different feedback types as Dong et al focused on bandit feedback?\n\n\n\nNo—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.\nAlthough 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."}, {"review_id": "fKfVCWSCGu", "reviewer": "Reviewer_GbwY", "summary": "The paper addresses the challenge of achieving last-iterate convergence (LIC) in Mean-Field Games (MFGs), especially under the more realistic assumption of non-strict monotonicity. The last-iterated policy of a proximal-point (PP) update, which incorporates Kullback–Leibler (KL) regularization, is shown to converge to an MFG equilibrium even under non-strict monotonicity. Each PP update step is shown to be equivalent to finding the equilibria of a KL-regularized MFG, and this regularized equilibrium can be found efficiently using Regularized Mirror Descent (RMD) with an exponential last-iterate convergence rate. Building on these theoretical insights, the paper proposes the Approximate Proximal-Point (APP) algorithm. APP approximates the PP update by executing a small number of RMD steps. Numerical experiments on standard benchmarks, such as the Beach Bar Process, show that APP reliably converges to the un-regularized mean-field equilibrium without time-averaging.", "questions": "1. 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?\n2. 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?\n3. 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?\n4. Can the authors elaborate why the initial policy~$\\pi_0$ should have full support in Prop. C.1?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The paper directly tackles the crucial problem of LIC in MFGs, which is relevant for deep learning applications where time-averaged policies can be less meaningful due to nonlinearity in parameter space.\n2. Establishing convergence under non-strict monotonicity enhances the applicability in practice.\n3. Establishing exponential convergence rate for RMD is a useful result, improving previous results that achieved only polynomial or time-averaged convergence.\n4. The Proximal-Point (PP) method, with un-linearized objective, is expected to be less sensitive to approximation error and more robust in non-strictly monotone settings compared to standard Mirror Descent (MD).\n5. Proposition C.1 is interesting.\n\nWeaknesses:\n1. The model is assumed to be known, and naturally no sample complexity analyses like the most recent references. A more realistic setting would have been the case where the parameters are learned from the data. \n2. A couple of very strong assumptions in relation to the latest literature on MFGs (see Questions)\n3. It is not clear how the results are placed in the literature when considered in conjunction with the rather `outdated' assumptions used.", "was_revised": true, "final_justification": "The rebuttal helped clarify the key concerns.", "rebuttal": "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. \n> 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?\n\nLocal‑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.\n\nIn 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.\n\n> 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?\n\nWe 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).\n\n> 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?\n\nFirst, 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.\n\nExtending 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). \n\n> Can the authors elaborate why the initial policy $\\pi^0$ should have full support in Prop. C.1?\n\nFull 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."}, {"review_id": "4TYF9B4DcA", "reviewer": "Reviewer_z4KT", "summary": "The authors consider an algorithm for learning equilibria in mean field games with last iterate convergence, to obtain low exploitability during final stages of learning, as opposed to playing suboptimal during learning in methods such as fictitious play. The algorithm is supported by rigorous theoretical analysis of convergence, as well as empirically by performing a successful numerical experiment.", "questions": "- Where does Figure 1 come from? Is it from the experiment further below?\n- I think the explanation on line 203 is unclear, how does Lemma E.7 provide the upper bound of exploitability? Can this be made more formal?\n- The convergence result in Thm. 4.4 given in $D_{\\mu^*}$, how does this imply exponential convergence in a standard metric for the policy, or in exploitability?\n- Why is (3.1) called intractable? If it is just a regularized MFG, can you not solve it using any regularized MFG algorithm?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The claims of last-iterate convergence are supported by theoretical results, as well as experimentally in one example problem. The benchmark Beach Bar problem makes sense for the field of learning MF equilibria. The experiments are limited and could be extended to show the limitations of the proposed methodology beyond the Beach Bar example, beyond regularized MFGs or even beyond the theoretical assumptions made in the work. In particular, there is no MF interaction in the dynamics, which is a common theoretical assumption but might be circumvented in practice / experiments.\n\nThe contributions would seem relevant, to consider last iterate convergence in more general monotone settings, as opposed to existing works that require averaging after playing as in fictitious play or considering special cases such as graphon MFGs. However,  without application to a data-driven setting with N-agent systems and without access to the model, it seems although LIC is achieved, model knowledge and exact calculation of Q-functions is necessary. In that case, I am not sure of the advantage of LIC over any other convergence in existing literature, which could be compared more clearly.\n\nThe clarity could be improved by stating concisely the differences to existing theoretical results and algorithms, whenever a new result is introduced, e.g., Thm. 4.3 and Thm 4.4. Some things remained unclear for me, see the questions section below.\n\nMinor things:\n- I think [1] is also relevant to add to Table 1, as it has discrete-time convergence results for MFGs (under concavity assumptions)\n- Typo line 671: \"for Here\"\n\n[1] Geist, Matthieu, et al. \"Concave Utility Reinforcement Learning: The Mean-field Game Viewpoint.\" Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems. 2022.", "was_revised": true, "final_justification": "I appreciate the additional explanations and would like to keep the score, as all the questions have been answered.", "rebuttal": "Thank you for your careful review and for your interest in our convergence guarantees for MFGs. We address your comments below.\n\n>Minor things:\n> I think [1] is also relevant to add to Table 1, as it has discrete-time convergence results for MFGs (under concavity assumptions)\n> Typo line 671: “for Here”\n\nThank you for pointing these out. We will add [1] to Table 1 and correct the typo in the revision.\n\n> Where does Figure 1 come from? Is it from the experiment further below?\n\nIt is mentioned briefly in line 169. Figure 1 illustrates our experiments showing that Regularized Mirror Descent converges exponentially in practice.\n> how does Lemma E.7 provide the upper bound of exploitability? Can this be made more formal?\n> 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?\n\nThank you for this request. We shall explain how to get the bound in detail.\nFrom 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)$.\n\nFurthermore, 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)\\\\|]).$$\n\nFinally, 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)}).$$\n\n> Why is (3.1) called intractable? If it is just a regularized MFG, can you not solve it using any regularized MFG algorithm?\n\n“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."}]

Author rebuttal:

Meta-review: This work introduces I once looked at Lastry–Lions monotonicity into the MFG setting, and defines a new proximal point-type method to solve it. This work enhances the field of mean field games by introducing a new class of solvable problems. While the practical utility of this condition is somewhat limited, experimentally the result of introducing the proposed algorithm yields to substantial gains in convergence rate and a novel analysis of the last-iterate which justifies acceptance.
Decision: Accept (poster)