Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximation
Authors: Chenyu Zhang
Xu Chen
Xuan Di
Venue: ICLR 2025 Poster (2025)
Keywords: mean field game
linear function approximation
stochastic semi-gradient descent
Primary area: other topics in machine learning (i.e., none of the above)

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

Published as a conference paper at ICLR 2025
STOCHASTIC SEMI-GRADIENT DESCENT FOR LEARN- ING MEAN FIELD GAMES WITH POPULATION-AWARY FUNCTION APPROXIMATION
Chenyu Zhang
Xu Chen
Xuan
MIT Cambridge, MA 02139 zcysxyêmi edu
Columbia University
Columbia University
New York, NY 10025
New York, NY 10025
xc241 20co umbi a edu
sharon. di @col umbia edu
ABSTRACT
Mean field games (MFGs) model interactions in large-population multi-agent sys- tems through population distributions. Traditional learning methods for MFGs are based on fixed-point iteration (FPI), where policy updates and induced population distributions are computed separately and sequentially. However, FPI-type methods may suffer from inefficiency and instability due to potential oscillations caused by this -awaadd--bwwarddd procedure. In this work, we propose a novel perspective that treats the policy and population a unified parameter controlling the game dy- namics. By applying stochastic parameter approximation to this unified parameter, we develop SemiSGD, simple stochastic gradient descent (SGD)-type method, where an agent updates its policy and population estimates simultancously and fully asynchronously. Building on this perspective, we further apply linear function approximation (LFA) to the unified parameter, resulting in the first population- aware LFA (PA-LFA) for learning MFGs on continuous state-action spaces. comprehensive finite-time convergence analysis is provided for SemiSGD with PA-LFA, including its convergence to the equilibrium for linear MFGs-a a class of MFGs with linear structure concerning the population- under the standard contractivity condition, and to a neighborhood of the equilibrium under a more practical condition. We also characterize the approximation error for non-linear MFGs. We validate our theoretical findings with six experiments on three MFGs.
INTRODUCTION
Mean field games (MFGs) (Huang et al. 2006 Lasry & Lions 2007 offer a tractable framework for modeling multi-agent systems with large homogeneous population. In MFGs, the impact of other agents on a particular agent is encapsulated by population mass (or mean field), providing reliable approximation of actual interactions among agents when the number of agents is large. Consequently, understanding the population is fundamental MFGs, as learning these games entails considering both the agent's 's policy and the population dynamics.
Prior work on learning MFGs has mainly focused on fixed-point iteration (FPI) methods and their variations, which is characterized by forward-backwant procedure that alternately calculate the policy update w.r.t. fixed population and the induced population distribution w.r.t. a fixed policy (Guo al. 2019 Elie al. 2220 Perrin al. 2020; Xie et al. 202T;; Cui & Koeppl 2021 Lauriere
et al. 202262 | Anahtarci et al.) (023). However, FPI-type methods face several limitations: 1) The policy learning and population learning in FPI-type methods typically involves distinct iterative processes, and are implemented separately and executed sequentially, potentially increasing the overall computational burden (Mao et al.) 2022 Zaman et al. 2023). 2) Vanilla FPI methods suffer fixed while updating the other, the differences between updates in consecutive iterations can be drastic, causing oscillations in the learning process, phenomenon commonly observed in practice (Cui & Koeppl 2021). 3) Separating the forward and backward processes prevents us from applying abundant methods developed for policy learning, such function approximation (Mao et al. 2022 Huang al. 2024), population learning.
from instability. As the policy or population

---

Published as a conference paper at ICLR 2025
This work delves into the rapidly growing field of online learning for MFGs (Mao al. 2022 Angiuli ett al. 2022 Zaman et al. 2023] Yardim et al., 2023 Zhang et al., 2024a Zeng et al. 2025). where an online agent interacts with the environment and gathers observations
a Markov chain to update its policy and population estimate. A key aspect of our approach is recognizing that the Markov chain is jointly parameterized by both the policy and population distribution, which together define the transition kernel. From this perspective, finding the mean field equilibrium (MFE) becomes problem of identifying the optimal parameter-the fixed point of the Bellman and transition operators. This viewpoint unlocks a large toolbox of stochastic parameter approximation methods for learning MFGs, including simple stochastic gradient descent (SGD)-type methods. Specifically, by treating the policy and population as unified parumeter, we update both estimates fully asynchronously using the same batch of samples, thereby eliminating the need for borward-bakwarr process.
Building on this perspective, we introduce another powerful technique: (LFA), a widely used approach in stochastic approximation methods for policy learning on large or continuous state-action spaces (Melo et al. 2008 Jin et al., 2020). By applying LFA to the unified encmeeee--enommpasiin both the policy and population we develop the first population aware LFA (PA-LFA) for learning MFGs on continuous state-action spaces. This is particularly significant, as many common MFGs, such as autonomous driving (Huang et al. [202T] Chen et al., 2023a b Mo al., 2024), flocking (Perrin al. (02T), and crowd modeling (Lachapelle & Wolfram 201 I Burger et al.] (203)), inherently involve continuous state-action spaces. With PA-LFA, our method enables a simple, fully online, model-free SGD-type method for learning MFGs in these settings,
linear function approximation
supported by strong theoretical guarantees.
While elegant, treating the policy and population as a unified parameter raises several questions:
1) Updating policy and population estimates fully asynchronously creates a strong coupling between
the two, which is absent in
or multi-loop structures (Yardim et al. [023] Zhang
et al. 2024a) or is alleviated in multi siltii-tmmscalee approaches (Mao et al.) 2022]Anniull
Angiuli et al., [023]
Zaman et al. 2023). How can we analyze this coupling and the non-stationary Markov chain
generates to establish convergence guarantees? 2) Empirically, our method simple SGDD-type
method without additional stabilization mechanisms outperforms vanilla FPI in stability and effi- ciency (Section 7p. What theoretical explanation underpins this? 3) How can we design PA-LFA for continuous action spaces such that each population update maintains comparable operational complexity to that in the finite state-action case? 4) How does PA-LFA influence convergence? Under what conditions does it converge to an MFE, and if it doesn't 't, how large is the approximation error?
Main results. With the above questions in mind, we highlight the key contributions of this work:
We propose SemiSGD, a simple online SGD-type method for learning MFGs. We innovatively treat the policy and the population as unified parameter. Algorithmically, we update both simultaneously and asynchronously using the same online observations and learning rate, thus eliminating the forward-backward process typical of FPI methods. Theoretically, we show that the unified parameter in SemiSGD follows a descent direction towards the MFE, whereas neither the policy nor population alone is guaranteed to do so (Lemma] D. This gives a potential explanation for the stability and efficiency of SemiSGD over vanilla FPI (Section 7}.
We formulate novel framework of linear MFGs, characterizing class of MFGs with linear structure concerning the population measure. Linear MFGs accommodates continuous state-action spaces and includes MFGs on finite state-action spaces special case. We prove that linear MFGs enable linear parameterization of both the value function and the population measure.
We extend the linear parameterization to develop population-aware linear function approxima- tion (PA-LFA) for general MFGs. SemiSGD equipped with PA-LFA is the first method to apply LFA to the population measure in MFGs. Notably, updates in SemiSGD with PA-LFA maintain the same operation complexity as in the finite state-action space case, highlighting the simplicity and efficiency of our method.
Finite-time convergence analysis is provided for SemiSGD with PA-LFA. We novelly regard the learning process as a stochastic approximation on non-stationary Markov chain parameterized by the unified parameter: This perspective enables a straightforward SGD-type analysis, elegantly handling the strong coupling between the policy and population and offering insights into the learning dynamics of SemiSGD. We prove that, under a contractivity condition no stronger than prior work, SemiSGD converges to the MFF. The contractivity condition can be hard to
2

---

Published as a conference paper at ICLR 2025
verify in practice and potentially implies large regularization. In response, propose new condition that is more practical. This condition allows general non-regularized policies, under which SemiSGD converges to neighborhood centered at the MFE. In both scenarios, SemiSGD enjoys state-of-the-ar sample complexities.
For non-linear MFGs, SemiSGD with PA-LFA converges to the projected MFE (or its neighbor- hood). We characterize the distance between this projected MFE and the actual MFE in terms of the intrinsic approximation error in the linear representation.
We conduct six experiments on three MFGs to demonstrate the properties of our methods: 1) For continuous state-action spaces. PA-LFA is more efficient and accurate than discretization; 2) SemiSGD automatically stabilizes without additional mechanics, achieves a higher accuracy, and is faster by eliminating the forward-backwee procedure.
Related work. Learning MFGs has garnered increasing attention, with recent comprehensive reviews
byLLauriére et al. (2022a); Cui et al. (2022). To address the instability issue of FPI, various stabilization
mechanisms have been proposed, broadly categorized into: 1) regularization (Cui & Koeppi| 202T
Anahtarci al. 2023): ; 2) fictitious play (Elie al.] 2020 Perrin et al. 2020; Cardaliaguer &
Hadikhanloo| (017): 7): and 3) mirror descent (Perolat et al. 2202 Xie ct al. | Yardim ct al. [003
Laurière al. [202bb). Recently, |Angiuli et al. (2022): ; Zaman et al. al.] (2023); Yardim et al. (0023);
Zhang et al. (2024a) developed online oracle-free methods for the population learning in MFGs,
where a population estimate is updated using online observations without requiring an oracle to
manipulate the population or directly return the population measure. /Angiuli et al. (2023); Zaman cet al. (2023); Mao et al. (2022); Zeng et al. (2025) further proposed single-loop multi-timescale schemes to asynchronously update the policy and population estimates. On the policy learning side, Mao et al. (202)); y: Huang et al. (2024) considered function approximation, though they both assume access to the population measure rather than learning it. An extended literature review with detailed comparisons of existing setups and methods is provided in Appendix A
Notation. A complete list of symbols and their meanings is provided in Table 3 We denote the set of probability measures on a space X' as D(x'), and the set of signed measures as M(Y). When X is finite with d elements, the probability simplex on it is denoted as A C CR. 8, is the Dirac delta measure at &. Without subscript, the inner product denotes the vector inner product (z, y) = x { y is the direct sum of elements in linear spaces, which reduces their concatenation (z: y) when x and y are vectors. The norm without subscript denotes the E norm for vectors, and & operator norm for matrices. For (vector-valued) functions on S, the L2 inner product is defined as (f. L. = Is (s))gs))ds, and the L1 norm is denoted as || ||] Is flf((s) [s)
2 STOCHASTIC SEMI-GRADIENT DESCENT FOR MFGs ON FINITE STATE-ACTION SPACES
2.1 REVISIT ONLINE LEARNING FOR MFGs ON FINITE STATE-ACTION SPACES
We consider an infinite-horizon Markov decision process (MDP) denoted by (S, r, P,7), with the state space S and action space A being finite. In MFGs, the reward function r and transition kernel P depend on the population distribution over the state space. Specifically, for given state-action pair (s, a) E S x A and population distribution E D(S), r(s, a, μ) and P(s' s, a, μ)) denote the reward received and the probability of transitioning to state s' E S. We consider a bounded reward function with | < R. is the discount factor.
An agent in an MFG aims to find a policy RT, which maps a state to a distribution on the action space determining the agent's 'ss actions, that maximizes its expected cumulative discounted reward while interacting with the population. We utilize a value-based approach to calculate policies and assume access policy operator F, (Zou et al. 2019 Zhang al. 2024a) that returns policy based on an (action-) value function Q: S x + R. We write =Q == PT (Q).
J. We define two operators for any
value functions Q. Q' E ||A| and population measures M, M' E D(S):
(ss,a) Bi [r(s, a, M) M) (s', a')], with a' a' s'~ P(: s,,, M) (Bellman) P(Q.M) EErrrr (P(s (s, with s~ aaaa-
(Transition)
3

---

Published as a conference paper at ICLR 2025
Then our learning goal, the mean field equilibrium (MFE), is defined as the fixed point of these two operators. With an argmax policy operator, the fixed point of the Bellman operator satisfies the Bellman optimality equation, leading the standard MFE definition in the maximiiii setting (Laurière et al. 2022b] Angiuli et al. 2023); with a regularized policy operator, e.g., softmax, the fixed point corresponds to the regularized MFE (Cui & Koeppl 202T Zaman al. 2023). See
Appendix B.I for more discussions on our MFE definition.
Definition 1 (Mean field equilibrium). A value function-population distribution pair (Q,M) ) is mean field equilibrium (MFE) if it satisfies Q = Tiq.M> Q and M P(q.M)
typical FPI-type method (approximately) calculates the fixed point of the Bellman operator given the current population distribution, i.e., the best response, and the fixed point of the transition operator given the current value function, i.e., the induced population distribution, alternately. Under certain contractivity conditions, FPI converges to the MFE (Guo et al. 2019).
This work focuses on model-free online learning methods for MFGs. In such methods, an agent maintains estimates about the value function and population measure, and uses online observations to update its estimates. For the value function, temporal difference (TD) methods (Sutton & Barto 2018) are widely used. Given an online observation tuple O = (s, s', aa) and step-size a, on-policy TD (or SARSA (Sutton & Barto 2018 updates the Q-value function as follows:
Q a) + Q(s, a) - ag(Q; with g(Q:0) = Q(s,a) - r(s, a, M) 7Q(s a').
(1)
For the population distribution, Monte Carlo (MC) sampling (t.atuzzúski et al. 2013) is a common choice. Given a new state sample sf and step-size a, MC updates the population measure as follows:
M + M - O); with g(M; = M- - 62,
where dg the Dirac delta measure and is a one-hot vector for finite state spaces.
TD and MC updates are widely used in online learning for MFGs (Angiuli al. 2022 Zaman et al.) 2023| Zhang et al.] 2024a). Fixing the policy and population measure (i.e., fixing the Markov kernel), TD converges to the optimal value function, and MC converges to the induced population distribution.
2.2 STOCHASTIC SEMI-GRADIENT DESCENT
Combining [ and in single pass gives a simple SGD-type method. g in [T] and ( is referred as semi-gradients, as it does not represent the actual gradient of any loss function but provides a similar descent direction to the stationary point, i.e., the zero point of g g term our method SemiSGD and present it in Algorithm [ where (Qr; M,) denotes the concatenated representation of the value function and population measure, as they are both vectors for finite state-action spaces. Similarly, g represents the concatenation of the semi eemiiggadients for the value function and population measure.
Algorithm 1: Stochastic semi gradienrdient descent (SemiSGD)
input: Initial value function Qo(= (0), 0o)), population estimate Mo(= (w/, ),)),, and state 80- for t == 0, o......,2 do
Observe ag I' (Q.]ss)), r2 r(st, at, (1)), st, a, Mi), a+t1~ ~ " (Q+)) Update for finite MFGs: (Q++1; M++1) = (Q:: M,) - a.g(((1; M,); 8, a, ,',)
or with PA-LFA: Č++1 = IT(E, (E))
return (Qr, Mr) or εT.
Algorithm| is an online, single-loop, uni-timescale method that is free from any baawwdd process. Not only does it update the value function and population measure estimates in an SGD- like manner, but it provides an actual descent direction through the mean- -ath semi cemi-gradient defined as BIQ.M)() (-) = (( O), where O is the online observation tuple following the steady distribution induced by the policy and transition kernel determined by Q and M.
'itt slight abuse of notation, we use a single operator to return semi semi-gradien gradients throughout the paper, for both the action-value function and population measure; it should be clear from the context and its arguments which one it refers to.
4

---

Published as a conference paper at ICLR 2025
Lemma (Descent direction; informal). Suppose (Q+;M.) is an MFE. Suppose the reward function,
transition kernel, and policy operator are Lipschitz continuous with Lipschitz constant L. For any value function Q and population measure M, with AQ = Q. and AM = M Ma, have
(AM, ((Q, (M)) - || [IAMIIIA + ||AM))),
(Q)) - ---IIQQ1 + LIA + ||M])).
Due to the coupling between Q and M, neither an) (M) nor - -(Q.M) is guaranteed to be descent direction, no matter how small the Lipschitz constant L is. However, if S 1/2, adding the two inequalities gives
{(Q: M) - (Q.; (t).)
& (I(Q; (Q.; M.)
formal and generalized version of Lemma for linear MFGs, which encompasses finite MFGs (Example 2 is proved in Appendix H.1 We now discuss some key insights from Lemma
Descent direction. The concatenated semi-gradient points to descent direction for the concatenated estimate (Q: while neither the value function nor population measure alone is guaranteed to follow a descent direction, no matter how small the Lipschitz constant when far from equilibrium (i.e.,
FPP-type
SGD-type
R0
(lg TT
0a(
100
T
P4
large ||M M. and |QQ - Q-I)). This strongly suggests treating the value function and population measure as a unified parameter and updating them simultaneously at the same rate. The small Lipschitz constant condition L S 1/2 in the lemma, formalized Assumption 4 in Section ensures contractivity. Thus, while both methods converge under the contractivity assumption, SemiSGD follows descent direction but FPI may not, hinting the sample efficiency of SemiSGD. See Figure for an illustration.
M2
(T., P4)
(Tee [4,
Figure 1: Learning dynamics.
Incremental update by design. Incrementally updating parameters damping update steps, rather than switching to entirely new estimates, is a common stabilization technique in learning MFGs (Lauriere et al., (0022),, used in methods like fictitious play and mirror descent (Lauriere et al. (002b). As an SGD-type method, updates in SemiSGD are incremental by design. This, combined with the previous point, suggests that SemiSGD enjoys automatic stabilization without needing additional stabilization mechanisms, as confirmed by our experiments (Section 7 These two insights also offer a potential explanation for the oscillation issues seen in FPI-type methods.
Stochastic approximation non-stationary Markov chains. The lemma highlights that the value function and population measure jointly shape the landscape of learning MFGs and should be treated unified parameter. SemiSGD naturally fits stochastic approximation method on a non non-starionary Markov chain for finding the equilibrium parameter, with non con--ttiionarity arising from the changing transition kernel as the value function and population measure updated. Two- timescale approaches are used to mitigate the non-stationarity and parameter coupling (Angiuli et al., 2023 Zaman al., 2023 Mao al. 2022). Using a unified parameter, our approach enables simpler uni-timescale scheme with a straightforward SGD-type analysis that accounts for coupling and achieves better sample complexities (see Table Moreover, for general policy operators, which may fail the small Lipschitz constant condition, the stochastic approximation is rapidly changing Markov chain (Zhang al. (003). Building on the results for this class of methods, we are able to, for the first time, characterize the finite-time convergence performance of learning MFGs without contractivity or monotonicity condition.
LINEAR MEAN FIELD GAMES
We now extend setup beyond finite state-action spaces. Viewing the value function and population measure as a unified parameter, we can naturally extend linear MDP (Jin et al.) (020) and LFA for the value function to handle population measures large continuous state spaces. Before extending LFA to population measures in the next section, we first introduce linear MFGs, a class of MFGs based on linear MDPs with a linear structure in the transition kernel w.r.t. the population measure. Definition 2 (Linear mean field games). An MDP (S, A, P.r.y) is a linear MDP (Jin et al. 2020) with feature map Φ: S x A - Rdd if there exists d, (signed) population-dependent measures
5

---

Published as a conference paper at ICLR 2025
WM (w ( j=1 M(S) and an unknown population-dependdnt vector vas Rdi, such that for any state-action pair (8, a) ES x A and population distribution M E DS)), we have
P(s' 8, a, .M- = (Ó(s, a). (ar
r(s, a, M) = (d(s,a).vM)
A linear MFG further assumes measure basis & D(S)da such that for any population M, there exists an unknown matrix Qu E IR4 xd2 such that war = Pas th indicating that P(s' 8, a, M) = (ő(s, a), (s))(s))) We require @ to be Lx and to be L and L2 (thus its Gram matrix exists). Without loss of generality, we assume sups,a [ a)ll S and sup, [|x(())] s F.
A linear MFG assumes MDP components, the transition kernel and reward function, lie in the linear span known basis functions, giving a linear structure to the value function and population measure. Proposition 1. For linear MFG, for any population distribution M and policy n, we denote Qh as the action-value function and Pis as the induced population measure w.r.t. the MDP determined by M and π. Then, there exist vector parameters 0 E Rd and n E Rd such that (5x(s') (1b(6),, m) V(s,a,8') XESxxxxx S.
Qu (8. a) (d(s,a),0)
The proof of Proposition] iss deferred to Appendix E. Remarkably, requiring that the transition kernel being linear w.r.t. measure basis is essential for the linear structure of the population measure. In this paper, we reserve letters 0 for the value function parameter and 1y for the population measure parameter. And denote the concatenated parameler parameters (7, 0, {) and their corresponding functions (Q, M. (Q, M) interchangeably in our analysis. For example, we say Ç E 1dd is a mean field equilibrium (MFE) if its corresponding value function Q (Ø, ff and population measure M = (5b, .7) satisfy Definition
= (11 0). Additionally, we will use
Example 1 (Linear MDP plus oopulation-independen transition kernel,, MFGS with linear MDP and
transition kernel are a trivial example of linear MFGs, where ΩM = I
for all M D(S).
Example 2 (Finite state-action space). For finite MFGs, let the feature map e return the one-hot vector of each state-action pair, i.c., ((s, a) = (s.aa E @lSTAA,, and the measure basis &i return the Dirac delta measure at each state, i.e., (ss))) 8, E A (s), Construct the matrix f2 E [|S)) such that ([2))((.)) = P(s'1 | s, M). Similarly, construct the vector 1/s E R SI|AA such that (VM) r(s, a, M). Then, for any (s, a,,,,s)) E S x A x S, we have P(s') P(51|s, a, M) = Srrd (e(s,a), Paro(s))) r(s,a, et e (e(s.a))MM)
Example 2 implies that all the analysis for linear MFGs applies to finite MFGs (see also Appendix K.
4 SEMISGD WITH POPULATION AWARE LINEAR FUNCTION APPROXIMATION
Proposition D presents the first linear parameterization of the population measure in MFGs. Applying this general MFGs leads to population- aware linear function approximation (PA-LFA). More discussions on motivations of PA-LFA can be found in Appendix B.2 PA-LFA necessitates a tailored stochastic update rule for the population measure estimate. Let M. be the objective population measure and define the loss function L == IIM M. 1l2, Then, the gradient of the loss is
V (V M,, M,) L. (w), (v) m)) M,).,
As the MFE population measure M, is unknown, replace it with the empirical Delta distribution (bootstrapping), giving the semi-gradient
g(n: s') = (1b, (vb, n) 5z) L2 = -S (S)) yjss - Sf (s) G.n (555),
(3)
where G = Is (s) is the Gram matrix of measure basis v6.
2 retains the updated population measure as probability vector, which is not necessarily the when using 3 as the semi-gradient, due the presence of general Gp and (bss)) that may not be an identity matrix or a probability vector. Therefore, we need to apply a projection to the updated parameter ensure that it remains a probability vector, giving our stochastic update rule:
For finite MFGs,
a (r))))))
where (n) g(75 81+1) and A is the projection operator onto the probability simplex A

---

Published as a conference paper at ICLR 2025
Remark (Operation complexity). The simplex projection has a worst-case complexity of O(d)) (Condat 2016). In semi- amii-radient evaluation, Gy is constant matrix, and thus we only need to evaluate y the next state s' and multiply parameter with fixed matrix, with the matrix-vector multiplication having a complexity of (d2).. Therefore, the total worst-case operation complexity of the update rule (4) is O(d)). Moreover, the simplex projection has expected complexity of (d2)) (Condat 2016). And if G has precomputed properties and/or special structures, such as being sparse with O ((d)) non-zero elements, the complexity of the semi-gradient evaluation is (d2)), giving total expected operation complexity of (d2), which is the same as that of ( for finite MFGs with a state space of size |S| = ((2)).
Similarly, we can get the TD update rule for the value function parameter (Sutton & Barto 2018):
g(0: 0) = o(s a) ((0(s, a) ro(s' a'), 8) r) = Go - (()), where O (s, a. r, s a'), and G (0) = ())(s,)((())))))))))))))))) (s.()))))))))) a) - ro(s', d²))² and p(O) = ((s,a)r. The update rule for the action-value function parameter is
o++1 (0, a.ge (e)))
(5)
where we denote (x = g0; Ot). O. = (8,, O22 r2,, 814 I, ae+1), and 11 is the projection operator
onto the Fuclidean ball BD == {0 E Rdh ||0|| < D). Similar to the population measure update, the projection is commonly used with LFA to ensure that the value function parameter remains bounded (Bhandari et al. [0188 Zou et al. 2019), which is automatically satisfied in finite MFGs (Appendix K).
Specifically, we need D 2 [00] where 0, is the MFE value function parameter.
Combining and 5 gives the update rule for the unified parameter:
Er+1 = 11(E: (G)) = -l B x (Er ar (O,) e G+)&,
(p @ (O.)))) (6)
(6) updates the action-value function and population measure using the same online observations with the same learning rate. Replacing Line 3 in Algorithm [ with (6) gives SemiSGD with LFA.
The next section shows that SemiSGD converges to a zero point of the mean-patt path semi-gradice oc := En O), where de is the observation distribution induced by the parameter g. The next proposition states that this point is an MFE, thus validating the derivation in this section.
Proposition 2 (MFE as a stationary point). For linear MFGs, & is an MFE if and only if (E()) = O.
We prove an extended version of Proposition 2 in Appendix F showing that the stationary point actually corresponds to a projected MFF for general (non-linear) MFGs.
5 SAMPLE COMPLEXITY ANALYSIS
This section provides a finite-sample analysis of the convergence of SemiSGD with LFA, thus covering finite MFGs as a special case. We denote Par s, a) == P(s' s, a, M) and FM r a) = r(s, a, .) for short. For transition kernels, we define the total variation operator norm || == (uPpEMM($AADllllree
[ P( 8, (d)(ds,d We now state the assumptions for the analysis.
Assumption 1 (Lipschitz MDP). The transition kernel and reward function are Lipschitz continuous w.r.t. the population measure. That is, there exists positive constants Lp and L,, such that for any state-action pair (x, a) and population measures M1, M2. we have
PPM - PM, S (Tp/Vda))l - ||M,, - loo S (T.// db) - -M2l/Tv-
Assumption (Lipschitz policy operator). There exists a constant L, such that for any state s and value functions Q1, Q2. we have ||T',(Q))
(Q2) s)l[TV S L 1Q Q2
Assumption 3 (Uniform ergodicity). The MDP is uniformly ergodic for any parameter any value
function Q and population measure M. That is, there exists constants m 2 1, E (0, 1), and ((Q.M). such that for any initial distribution Mo E D(S), it holds that [| - P Pi Moll S mp'.
For notational convenience, we define an ergodicity constant o = 2 + á + mp" /(1 p) with à = logg -11, and H == (1 (1+7) R + 2F, which can be regarded as the scale of the problem.
7

---

Published as a conference paper at ICLR 2025
Assumption 4. The Lipschitz constants are sufficiently small such that 30 max Lp. Ln } H L, S
2w, where w E 10, is problem-dependeee constant (defined in Lemma 9 in Appendix
H.1
Remark 2. Assumption I is standard regularity condition for MFGs that do not assume blanket
contractivity assumption Cui & Koeppl 2021; Angiuli et al., 2023 Anahtarci et al. 2023; Yardim
al. 2023 Huang al. 2024). Assumption 2 ensures the smoothness of policy updates, a condition
typically met through regularization. Example policy operators satisfying Assumption 2 include
softmax (Cui & Koeppl 2021| Zaman al. [020] Angiuli al. ) mirror descent (Perolat et al.
2021 Laurière et al., 2022b), and mirror ascent (Yardim et al. 2023). Assumption 3 is a standard
mixing assumption for online methods with Markovian sampling (Bhandari et al., 2018 Zou et al.
2019 Angiuli et al. 2022 Zaman et al. (023), ensuring that the agent's exploration adequately covers the state-action space. Notably, Assumption B also typically satisfied by regularizing behavior policies (Yardim et al. 2023). It is noteworthy that even earlier works using blanket contractivity assumption recognize that contractivity can achieved through regularization, provided that "the transition kernel and reward function are Lipschitz and the corresponding Lipschitz constants are small enough" (Xie et al. 2021). Therefore, Assumption 4 is the key assumption that guarantees the contractivity of learning dynamics. In summary, our assumptions closely align with those in Angiuli et al. (2023); [Anahtarci et al. (2023), and are not more restrictive than those in the literature for contractive MFGG. See also Appendix for convergence results in the absence of Assumption 4
We can now bound the mean squared error of SemiSGD recursively, which directly gives several unite-time error bounds.
Theorem (One-step progress), Let &. = (0x: ) be an MFE parameter. Let {&r = (0); be a sequence of parameters generated by SemiSGI). Then, under Assumptions to
have
log at 1 max Ly 1²H
- -,
Oaa log' a,
w
Corollary (Constant step-size). Given a constant step-size a = Cn, we have
Eller - 12 2 < eoowT | 1= + w- 122 O log ag ).
Let ogg = (log (w)(T) Then Corollary states Elirr - 1 ((H2log² () giving
an Oor~2log² 1 sample complexity for an c-MFE (E) Ey - E-1 s c). A linearly decaying step-size
sequence improves the logarithmic factor, giving a convergence rate of ((H2 log / (w²)) (see
Corollary Reducing to finite MFGs, the complexity becomes Ô
SAR"
(see Corollary
1F(1-
These results also imply the uniqueness of the MFE under the assumptions of Theorem [ The sample complexity is tight up to logarithmic factor, consistent with other stochastic approximation methods, and strictly better than existing results for learning MFGs (Table 2b.b See Appendix [B3] discussions.
for more
APPROXIMATION ERROR FOR NON-LINEAR MFGs
SemiSGD with PA-LFA applies to non-linear MFGs as long as the feature map 6 and measure basis a are specified. However, for non-linear MFGs, it remains unclear: 1) What point does SemiSGD with PA-LFA converge to? 2) What factors characterize the approximation error caused by PA-LFA?
For the first question, it turns out that the convergence point of SemiSGD with PA-LFA, i.e., the zero point of the mean-path semi- gradiet developed in Section corresponds to a projected MFR (0, n) defined by (0, Φ) 11. Te (0, Ø) and (17, v) = Ps (n, th), where 11, and HL are orthogonal projection operators onto the linear spans of Φ and v. respectively. The formal definitions and proof of the statement are deferred to Appendix F For linear MFGs, as images of T and P are within the linear spans of é and ub (Appendix E the projected MFE coincides with the MFE itself (Proposition 2 The following theorem answers the second question.
Theorem 2 (Approximation error). Let &o = (0.; no) be the convergence point of SemiSGD with PA-LFA. Let (g., P.) be the actual MFE. Write P. == Peo for short, and similarly for P., To, and T...
8

---

Published as a conference paper at ICLR 2025
Then, Assumption 3
indicates the existence of E N such that
5 yoRUa
(Lr 7oRLp
6q = 1-11g-- - -0, 00) clc S
1 1-7
cg
(1-7)vdg)
+ 111. - 110-ll
khp
Cu I1,e, - no) 11rv &
Cu +
k. + + -II.P.llTV
Vd2
If the Lipschitz constants are small enough: 2 (yoR + (1-7))) (1 -)) (1-
and 2(Lp(10R
(1-7)k) + Lr v)vd2) & (1+ 2p (1 - 7) d2, then
2
bq + cu min {r, pم (cp + kew);
where <== 11g. To and cs = IIP. - P. Irv are inherent approximation error induced by the projection onto the linear spans of basis and ib, which independent of the algorithm. Moreover, [f - ||V p (c.g., P. induces reversible Markov chain), k ==
The proof of Theorem is given in Appendix The approximation enror of PA-LFA scales with the inherent approximation error determined by the chosen basis, which is consistent with the approximation error of LFA for value function Tsitsiklis & Van Roy 1997..
NUMERICAL, EXPERIMENTS
To evaluate SemiSGD with PA-LFA, we conduct six experiments on three MFG examples: speed control (Appendix C.2) flocking (Appendix C.4). and network routing (Appendix C.)). When com- paring with FPI-type methods, alongside vanilla online FPI, we equip FPI with entropy regularization (ER), fictitious play (FP), and mirror descent (MD). Please refer Appendix [ the detailed setup, full results and analysis, and additional experiments. Here, we present some highlights of the results.
Figure 2a reports MSE curves for the speed control game. This example showcases the sample efficiency, stability, and accuracy of SemiSGD, particularly compared to vanilla FPI. The flocking game highly sensitive the reward (Appendix C.5). Large regularization may obscure the reward signal, leading to ncar-constant policies and population distributions, while other methods except SemiSGD cannot handle regulaauar policies well. Figure 2b reports exploitability curves for the flocking game, showing that only SemiSGD can effectively learn the game with near-greedy policies. The goal of the network routing game to direct the traffic from the origin the destination. reports the population distribution learned by SemiSGD on this highly non-smooth game. Figure exaainee how number of inner loop iterations (K) affect the convergence of FPI (Appendix C.3) it suggests that, given the same number of total samples, reducing K monotonically improves the convergence. Notably, when K 1, online FPI is equivalent to SemiSGD, which structure. Figure (Appendix CC7) on learned distribution and accuracy respectively, demonstrating that with proper choice of measure basis, PA-LFA generalizes better and achieves higher accuracy.
Figure 2c
removes the
PA-LFA with discretization
FPC
FPE
TPE
TPT MD
SuaiSCD
Sunpyee
Sumplee
(a) Speed control.
(b) Flocking.
(c) Network routing.
Figure 2: Convergence performance of SemiSGD and FPI.

---

Published as a conference paper at ICLR 2025
Dim.)
Diseret.
PA-LFA
100
LEA KFF
+20 .01
.17 .00
.1 .01
15
.2 .14
.11 111.00
Deedry
10
.27 1
20
.15+.13
.07 +04
25
.18+
+06+.04
40
.15 13
.10
50
.16 1 113
.11 1 .02
Samppio
0.25
8.55
Figure 3: On inner iterations. Figure 4: LFA & Discretization. Table 1: MSE of LFA & Discretization
CONCLUSION
This work proposes simple SGD-type method for learning MFGs, eliminating the haward-backwarr structure in FPI-type methods and the need for complex stabilization mechanisms. Our approach leverages novel perspective that unifies the value function and population measure single parameter, enabling straightforward analysis that elegantly handle the coupling between policy and population while offering insights into the learning dynamics.
Building on this perspective, develop the first population-awal linear function approximation for MFGs on large continuous state-action spaces, with sample and operation efficiency guarantees, as well approximation error characterization. Function approximation is just example of how techniques from policy learning can be extended to population learning using this unified perspective, and expect further advancements in this direction.
More broadly, our methodology is generalizable to other dynamical systems that can be parameterized by learnable parameters, including (finite) population games (Sandholm (2010), evolutionary games (Hilbe et al. 2018), graphon games (Zhou et al. 2024), and policy optimization for MFGs (Zeng
al. 2025
ACKNOWLEDGMENTS
This work sponsored by NSF under CAREER award number CMMI-1943998.
REFERENCES
Berkay Anahtarci, Can Deha Kariksiz, and Naci Saldi. Q-learning in regularized mean-field games. Dynamic Games and Applications, 13(1):89-11) 117, 2023.
Andrea Angiuli, CannPieere Fouque, and Mathieu Laurière. Unified reinforcement Q-learning for mean field game and control problems. Mathematics of Control, Signals, and Systems, 34(2): 217-271, 2022.
Andrea Angiuli, Pannree Fouque, Mathieu Laurière, and Mengrui Zhang. Convergence of multi- scale reinforcement q-learning algorithms for mean field game and control problems. arXiv preprint arXiv:2312.06653 2023.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. Conference on learning theory, pp. 1691-1692. PMLR, 2018.
Rajendra Bhatia. Matrix analysis, volume 169, Springer Science & Business Media, 2013.
Martin Burger, Marco Di Francesco, Peter Markowich, and Marie-Theree Wolfram. Mean field games with nonlinear mobilities in pedestrian dynamics. arXiv preprint arXiv: 1304.5201, 2013.
Pierre Cardaliaguet and Saeed Hadikhanloo. Learning in mean field games: The fictitious play. ESAIM: Control, Optimisation and Calculus of Variations, 23(2):569-591, 2017. 2017.
10

---

Published as a conference paper at ICLR 2025
Xu Chen, Shuo Liu, and Xuan Di. Learning dual mean field games graphs. In European Conference on Artificial Intelligence, pp. 421-428. IOS Press, 2023a.
Xu Chen, Shuo Liu, and Xuan Di. A hybrid framework of reinforcement learning and physics- informed deep learning for spatiotemporal mean field games. In Proceedings of the 22nd Interna- fional Conference on Autonomous Agents and Multiagent Systems, AAMAS '23, 2023b.
Laurent Condat. Fast projection onto the simplex and the 11 ball. Mathematical Programming, 158 (1):575-585, 2016.
Kai Cui and Heinz Koeppl. Approximately solving mean field games via entropy-regularized deep reinforcement learning. In International Conference Artificial Intelligence and Statistics, pp- 1909-1917. PMLR, 2021.
Kai Cui, Anam Tahir, Gizem Ekinci, Ahmed Elshamanhory, Yannick Eich, Mengguang Li, and Heinz Koeppl. A survey on Large-populatn systems and scalable multi-agent reinforcement learning. arXiv preprint XXXv:2209903859 2022.
Romuald Elie. Julien Perolat, Mathieu Laurière, Matthieu Geist, and Olivier Pietquin. On the convergence of model free learning in mean field games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7143-7150, 2020.
Bolin Gao and Lacra Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. arXiv preprint TrXxiv:704.00800 2017.
Xin Guo, Anran Hu, Renyuan Xu, and Junzi Zhang. Learning mean-field games. Advances Neural Information Processing Systems, 32, 2019.
Christian Hilbe, Stěpán Šimsa, Krishnendu Chatterjee, and Martin A Nowak. Evolution of cooperation in stochastic games. Nature, 559(7713) 2018.
Jiawei Huang, Batuhan Yardim, and Niao He. On the statistical efficiency of mean-field reinforcement learning with general function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 289-297. PMLR, 2024.
Kuang Huang, Xu Chen, Xuan Di, and Qiang Du Dynamic driving and routing games for autonomous vehicles on networks: A mean field game approach. Transportation Research Part C: Emerging Technologies, 128:103 103110,, 089,88911118 2021.
Minyi Huang, Roland P Malhamé, and Peter E Caines. Large population stochastic dynamic games: Closed-loop Melenn-Vl systems and the Nash certainty equivalence principle. Communica- lions in Information and Systems, 6(3):221-252 2006.
Dean Isaacson and Glenn R. Luecke. Strongly ergodic Markov chains and rates of convergence using spectral conditions. Stochastic Processes and their Applicutions,
1978.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pp. 2137-2143. PMLR, 2020.
Aimé Lachapelle and Marie-Therese Wolfram. On mean field game approach modeling congestion and aversion in pedestrian crowds. Transportation research part B: methodological, 45(10): 1572-1589, 201
Jean-Michel Lasry and Pierre-Louis Lions. Mean field games. Japanese journal of mathematics, (1):229-260, 2007.
Krzysztof Latuszyíski, Blažej Miasojedow, and Wojciech Niemiro. Nonasymptotic bounds on the estimation error of meme algorithms. 2013.
Mathieu Laurière, Sarah Perrin, Matthieu Geist, and Olivier Pietquin. Learning mean field games: A survey. arXiv preprint arXiv:2205./29. 2022a.

---

Published as a conference paper at ICLR 2025
Mathieu Laurière, Sarah Perrin, Sertan Girgin, Paul Muller, Ayush Jain, Theophile Cabannes, Geor- gios Piliouras, Julien Pérolat, Romuald Elie, Olivier Pietquin, et al. Scalable deep reinforcement learning algorithms for mean field games. In International Conference on Machine Learning, pp. 12078-12095 2095. PMLR, 2022b.
Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, and Yuejie Chi. Is q-learning minimax optimal? tight sample complexity analysis. Operations Research, 72(1):222-236, 2024.
Weichao Mao, Haoran Qiu, Chen Wang, Hubertus Franke, Zbigniew Kalbarczyk, Ravishankar Iyer, and Tamer Basar. A mean-field game approach to cloud resource management with function approximation. Advances in Neural Information Processing Systems, 35:36243-36255 2022.
Francisco S Melo, Sean P Meyn, and Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th international conference on Machine learning, pp. 664-671, 2008.
Sean P. Meyn and Richard L.. Tweedie. Markov Chains and Stochastic Stability. Springer Science & Business Media, 2012.
A Yu Mitrophanov. Sensitivity and convergence of uniformly ergodic Markov chains. Journal of Applied Probability, 1003): 2005.
Zhaobin Mo, Xu Chen, Xuan Di, Elisa Iacomini, Chiara Segala, Michael Herty, and Mathieu Lauriere. A game-theoretic framework for generic second-order traffic flow models using mean field games and adversarial inverse reinforcement learning. Transportation Science, (8(6):1403-1426 2024. doi: 10. 11..1277/rr.22222.5333
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Julien Perolat, Sarah Perrin, Romuald Elie, Mathieu Laurière, Georgios Piliouras, Matthieu Geist, Karl Tuyls, and Olivier Pietquin. Scaling up mean field games with online mirror descent. arXiv preprint arXiv:2103.006: 2021.
Sarah Perrin, Julien Pérolat, Mathieu Laurière, Matthieu Geist, Romuald Elie, and Olivier Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems, 33:13199-13215, 2020.
Sarah Perrin, Mathieu Laurière, Julien Pérolat, Matthieu Geist, Romuald Élie, and Olivier Pietquin. Mean field games flock! The reinforcement learning way. In Proceedings of the Thirtieth Interna- tional Joint Conference on Artificial Intelligence pp. 356-3622 International Joint Conferences on Artificial Intelligence Organization, 2021.
William H Sandholm. Population games and evolutionary dynamics. MIT press, 2010.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
J.N. Tsitsiklis and B. Van Roy. An analysis temporal-difffrrnce learning with function approxima- tion. JEEE Transactions Automatic Control, 42(5))674-69) 690, May 1997. ISSN 001 89286. doi: 10.1109/9.58087.
Qiaomin Xie, Zhuoran Yang, Zhaoran Wang, and Andreea Minca. Learning while playing in mean- field games: Convergence and optimality. In International Conference on Machine Learning, pp. 11436-11447. PMLR, 2021.
Batuhan Yardim, Semih Cayci, Matthieu Geist, and Niao He. Policy mirror ascent for efficient and independent learning in mean field games. In International Conference Machine Learning, pp. 39722-39754. PMLR, 2023.
Muhammad Aneeq Uz Zaman, Kaiqing Zhang. Erik Michling, and Tamer Basar. Reinforcement learning in non-stations -tatsnationary discrete-time time quaar-quadratic mean-field games. In 2020 59th IEEE Conference Decision and Control (CDC), pp. IEEF, 2020.
12

---

Published as a conference paper at ICLR 2025
Muhammad Aneeq Uz Zaman, Alec Koppel, Sujay Bhatt, and Tamer Basar. Oracle free reinforcement learning in mean-fiel rean-field games along a single sample path. In International Conference on Artificial Intelligence and Statistics, pp. 20178-10206. PMLR, 2023.
Sihan Zeng, Sujay Bhatt, Alec Koppel, and Sumitra Ganesh. Learning in herding mean field games: Single-loop algorithm with finite-time convergence analysis. In International Conference on Artificial Intelligence and Statistics. PMLR, 2025.
Chenyu Zhang, Xu Chen, and Xuan Di. A single online agent can efficiently learn mean field games. In European Conference Artificial Intelligence. IOS Press, 2024a.
Chenyu Zhang, Han Wang, Aritra Mitra, and James Anderson. Finite-time analysis of on-policy heterogeneous federated reinforcement learning. The Twelfth International Conference on Learning Representations, 2024b.
Shangtong Zhang, Remi Tachet Des Combes, and Romain Laroche. On the convergence of SARSA with linear function approximation. In International Conference on Machine Learning, 41613- 41646. PMLR, 2023.
Fuzhong Zhou, Chenyu Zhang, Xu Chen, and Xuan Di. Graphon mean field games with representa- tive player: Analysis and learning algorithm. In International Conference Machine Learning, pp. 62210-62256. PMLR, 2024.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. Advances in neural information processing systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2025
Appendix
Table of Contents
Extended literature review
15
B More discussions on motivations
16
B.1 Definitions of MFE and policy operators
16
Motivations for LFA
17
B.3
Comparison sample complexity
C
Additional experiments
19
C.1
General setup and remark
19
Speed control on a ring road
20
C.3
Number of innor loop itcrations
21
C.4
Flocking game
21
Regularization
23
C.6
Network routing
23
C.7
PA-LFA and grid discretization
24
D
Notation
25
E Proof of Proposition
27
Projected MFF stationary point
G
Preliminary lemmas
29
H
Sample complexity analysis
32
H.1 Key lemmas
32
112 Proof Theorem]
38
H. Proof of Corollaries
39
Convergence with general policy operators
40
Proof of Theorem]3 3
41
2
Convergence region
44
Approximation error analysis
45
Mean field games with finite state-action space
K. Implicit regularization
47
Convergence rate
47
14

---

Published as a conference paper at ICLR 2025
A EXTENDED LITERATURE REVIEW
Table 2: Comparison of learning methods for MFGs. In algorithm structure, IL and rL with >> 1 denote single- and multi-loop algorithms, 1TS and xTS with x > 1 denote uni- and multi-timescale schemes, respectively. Additional mechanisms contain fictitious play (FP), mirror descent (MD), and entropy regularization (ER). MFG structures contain contractivity, monotonicity, and the herding structure. In learning dynamics assumptions, (C) denotes blanket contractivity assumption, (R) denotes regularization, (L. denotes small Lipschitz constants condition, (M) denotes monotonicity, and (H) denotes the herding condition.
Algorithm implementations
Theoretical properties
Reference
Algo. struct.
Add. mech.
Oracle- free
Function approx.
MFG struct.
Dyna. assmp.
Sample
Population
Policy
complex.
Guo 2019
FB
contract. (C)
Lhe al. 20200
FB
FP
mono. (M)
Perrin 2020
FB
FP MD
mono.
(M)
Xic et al. 202
FB
contract. (C)
& Koeppl [2021
FB
ER
contract. (R)
Laurérre et
2022b
FB
FP&MD
Mao al. 2022
IL&ITS
contract. (C)
Anguuli al
2//22
2023
IL&ITS
contract. (L&R)
Anahtarci et
2023
FB
ER
contract. (L&R)
Zaman et al.
2023
IL&ITS
contract.
(C)
O(E
Yandim 202.
31.
MD
contract. (R)
Ofe log" "og""""
Zhang ct al.
2024a
2L
contract.
(C)
Ole e
Huang al. 20224
FB
Ole Olg-l loge
Zeng al. 2025
IL&ITS
herding
(H)
O(E
This paper
LL&ITS
contract.
(L.
O(e 2 loge 4
There is a growing body of literature on learning MFGs, with most relevant works summarized in Readers can refer to Laurière et al. (2022a): Cui al. (2022) for a comprehensive review.
Table 2
We cast previous methods into the category that has a FPI-type algorithm structure, which typically forward-backwand (FB) structure to calculate policy evaluution/oppiiizzaioo and induced population sequentially. To enable online learning and boost efficiency, several works have proposed multi-loop (xL) algorithms update the policy and population simultaneously in an online fashion (Yardim et al., 2023 Zhang et al. 2024a). However, following an FPI-type structure, multi-loop algorithms fox the policy or population in the inner loops, which observed to be more time- consuming and incur oscillations in the learned policies (Mao et al. 2022). In response, two-timescale (2TS) asynchronous update schemes have been proposed in Mao et al. (2022); AAgiulii et al. (2022) 2023): : Zaman et al. (2020), where their "single-loop" is highlighted as a key feature. However, in two-timescale scheme, the policy or population updates much slower than the other to circumvent their strong coupling, essentially resembling a FPI-type structure. Moreover, due to the existence of slower timescale, two-timescale methods typically have a larger sample complexity bound (Table 2). To accelerate the multi-timescale scheme, Zeng et al. (2025) adopt momentum-te type buffers for parameter updates, resulting in an essentially uni-timescale step size with automatic stabilization similar SemiSGD. In stark contrast, our method updates the policy and population simultaneously and fully asynchronously, resulting in simple single-loop and uni-timescale method, completely removing the FPI-type structure and achieving an efficient ( sample complexity as an SGD method.
To address the instability issue of FPI, researchers have proposed various additional mechanics to stabilize the learning process, broadly categorized into three classes: 1) entropy regularization (ER) (Anahtarci al. 2023; Cui & Koeppl, 20 2) fictitious play (FP) (Elic et al. 20200 Perrin
ct al. 2020 Cardaliaguet & Hadikhanloo 2017); and 3) mirror descent (MD) (Perolat et al. 2021
Xie et 2021 Yardim al. 2023). Notably, MD inherently includes regularization, with entropy regularization being a special case LLuuriére et al. 20225). In our algorithm implementation, we do not require any additional mechanics, demonstrating the automatic stabilization of SemiSGD.
Learning MFGs necessitates learning both the policy and the population. Some claimed online methods only learn the policy using online methods such as online reinforcement learning, but
15

---

Published as a conference paper at ICLR 2025
assume oracle for the population measure. As result, the sample complexity results of these works (Mao et al., 2022; Huang et al., 2024) do not capture the population learning. We follow Zaman oracle-free method one that does not assume access to oracle which can provide the (estimated) population measure under a given policy. Among oracle-free methods, work together with Angiuli et al. (2022): Zaman al. (2023); Zeng al. (2025) maintain population estimate using online observations of a single agent. While Yardim et al. (2023 uses the empirical state distribution of N agents to approximate the population measure.
et al.. 2023) to dehne
To deal with large state and action spaces and obtain strong theoretical guarantees, MMo el al. 2022 Huang et al. 2024) consider function approximation for the policy learning MFGs. Our work is the first to apply function approximation to the population learning, which we argue is equally important as the policy learning for learning MFGs.
Turning to the theoretical properties of learning methods, two classes of MFG structure conditions are commonly considered that ensure convergence: the monotonicity condition imposes structure on the reward function ensuring that the exploitability is Lyapunov function (Elie et al., [2220] Perrin et al. 202T), and the contractivity condition requires that the algorithm gives a contraction mapping. Most recently, [Zen et al. (2025) propose new class of MFGs called the herding class, which allows for multiple equilibria. There are many combinations of dynamics assumptions to ensure the contractivity of the algorithm. The most straightforward one is to assume a blanker contractivity condition, which for FPI-type methods is equivalent to require the composition of the Norward-backward process be contractive mapping. Assuming that the mapping from the policy to the induced population is contractive, some works impose regularization on the policy to ensure that the mapping from the population measure to the policy is contractive, hence making their composition contractive (Cui & Koeppl| (02TT. To further reduce the granularity of the assumptions, Yardim al. (2023); Angiuli al. (2023); Anahtarci et al. (2023) inspect the environment elements. Specifically, they assume the reward function and transition kernel are Lipschitz continuous with sufficiently small Lipschitz constants, and impose strong regularization, to ensure the contractivity of the FPP-type algorithm. Our assumptions closely resemble the last set of assumptions.
B MORE DISCUSSIONS ON MOTIVATIONS
B. DEFINITIONS OF MFE AND POLICY OPERATORS
We now extend the discussion in Section 2 on our definition of MFE.
Standard definition of MFE using Bellman optimality equation. Our definition of MFE follows
the standard definition of defining the MFE as the fixed point of the Bellman operator and transition operator (Laurière et al. 2022b Cui & Koeppl, 2021 Zaman et al. 2023 Anahtarci et al. 2023). These two pxint equations are also known as the "best response" condition and "consistency" condition in the MFG literature. The standard definition of the best response condition is defined
using the Bellman optimality equation; see e.g., Angiuli et al. (2023). Our Definition recovers the standard definition with an a argmax policy operator:
(argmax))
(Q)(s) (a argmax, Q(s,a'))
Specifically, with an ar amamax policy operator, [ellmman becomes
Tss, Big.s [r(s, a,s,,, M) y max + with a' = argmax Q(s',a'),'' a'), P(: P(.1,PP. M).
The fixed point of this operator satisfies
(x) = E [n(s, a, M) + +7 max ('( at)]
which is exactly the Bellman optimality equation. Therefore, our definition of MFE covers the standard definition of MFF.
16

---

Published as a conference paper at ICLR 2025
Regularized MFE with regularized policy operators. Our definition of MFE is general as accommodates general policy operators. For example, with a softmax policy operator,
L cxp(Q(s..) (Q)[s) = E. exp(((s,a'))
((sottmax)
Definition
exactly recovers the definition of the Boltzmann MFE (Cui & Koeppl 2021 Zaman
et al. 2023). Notably, the above softmax policy operator satisfies Assumption 2 with Lipschitz
constant Lx-
With general regularized policy operator, e.g., a mirror descent policy operator with
regularizer h
(Perolat et al. 2021] Yardim et al. 2023).
((MD) (Q) = argmax (p. Q(s,(((s) h(p))
PEλA
Definition T corresponds to the regularized MFE, which is widely studied in the MFG literature (Mao et a 2022 Anahtarci et al.) 2023). Again, the mirror descent policy operator satisfies Assumption
when the regularizer is strongly convex (Yardim al. 2023). Regularization common technique
to stabilize the learning process and ensure the convergence of the FPI-type algorithm (Laurière et al.
2022ah.
B.2 MOTIVATIONS FOR PA-LFA
In the main text, we highlight that PA-LFA is a natural extension if we consider the value function and population measure unified parameter controlling the dynamics. On the other hand, there other direct motivations for developing function approximation method for the population learning MFGs.
Higher accuracy. As illustrated in Example 2 given continuous state space, discretizing the space gives special linear function approximation that uses Dirac distributions as basis measures, denoted as 8. Suggested by our analysis Section different measure bases lead different representation spaces of the population measure, which in turn affects the approximation accuracy of applying LFA (Theorem Therefore, we choose proper measure basis & such that
dist( span vb) < spsttuu,spaa()))
or equivalently, 6 <6 in Theorem 2 then IFA with basis 1/ will have a higher accuracy than simple grid discretization, as the former has a representation space closer to the true equilibrium. This is validated in our experiments; see Figures 12 and 13 and Table [
Incorporating prior knowledge. Continuing comparison between LFA and grid discretization, the latter is not appropriate for continuous or dependent distributions. For example, in our experiment on the ring road, the population measure is a continuous distribution, meaning that high density in one state will lead to high density in the neighboring states. However, discretization does not capture this dependency. Continuous population distributions
common in real-world applications, such as traffic flow (Chen et al. 2023a), flocking (Perrin et al. [2021). and crowd dynamics (Lachapelle & Wolfram 2011 et al. 2013). Furthermore, real-world population distributions can exhibit complex dependency structures, such as distributions on transportation networks (Zhang et al. 2024a). we have prior knowledge on the dependency structure, we can choose proper measure basis to capture this dependency, leading more efficient population learning process. Figure 12 also provides a clear illustration on this point.
Sample efficiency. As provided in Section 5 the sample complexity of SemiSGD scales with H² where H can be regarded as the problem scale. In Appendix K we show that for finite MFG the
problem scale is
SSAR 1-7
H =
which scales with the state-action space size. By choosing a low dimensional LFA (d, < (S][A). can achieve much lower sample complexity.
17

---

Published as a conference paper at ICLR 2025
the operation complexity of each update in SemiSGD with PA-LFA. Specifically, when d2 = |S), the operation complexity of each update in SemiSGD with without PA-LFA is comparable. When d2 < |S], PA-LFA gives significant reduction in operation complexity of each update. Note that the total operation complexity of the algorithm = sample (iteration) complexity operation complexity per iteration. Thus, combining the sample efficiency gain from PA-LFA, an even larger operational efficiency gain is achieved.
Operational efficiency. Remark
analyzes Jamalyzees
caveat is that if the environment simulator, especially the reward function and transition kernel, takes the full population measure as input, the operational efficiency gain in each update from PA-LFA may be offset. However, for many real-world applications, the simulator may not need the full population measure. For instance, for MFGs with sparse or local interaction, meaning that an agent's 8 reward and transition only depend on the population density on a few states, the simulator only needs to know the population density on these states. Linear MFGs are another example. Recall the definition of linear MFGs (Definition 2); the transition simulator is a mapping:
P: D(S) B M + S& + (0) Paav).
By Proposition] know that any induced population measure of linear MFG is within span Additionally, the population measure estimate maintained by our method is also within span (vb). Thus, the transition simulator can utilize this low-dimensional structure:
P: span (v) 3 M = (v,, 1) + 52M + (6, (61b
P Rd 3 + (1b, n) + (w.n + (d, (w).))
That is, for any linear MFG, there exists transition simulator P that takes low-dimensional vectors as input. This is also true for the reward function.
Nevertheless, since the sample efficiency gain always holds, PA-LEA always reduces the total operation complexity of the algorithm.
B.3 COMPARISON OF SAMPLE COMPLEXITY
The worst-case sample complexity of SemiSGD analyzed in Section 5 O -2 log -1 (see also Corollary 3 This complexity aligns with that of SGD for Lipschitz functions (0(c [emirovskij
& Yudin ) MCMC methods (O(e-3) (Latuszyúski et al. 2013)). and is better than the state-
of-the-art complexity of TD methods (TD(O): O(c-2 log -T) (Bhandari et al. 2018 8). Q-learning: O 1og" ) Li al. 2024)), and SARSA: O(c 22 log c-1) (ou et al. 2019 All these bounds are tight up to logarithmic factors. The consistency of these complexities is not surprising as they all belong to the class of stochastic approximation methods for single parameter. In contrast, existing methods that treat the value function and population measure as two parameters and update them
using a two-timescale scheme have much worse sample complexity (Mao al. 2022 2023
Zaman et al.
Under the contractivity assumption, oracle-free methods Yardim al. 2023 Theorem 4.3) and Zhang al. 2024a Theorem 1) have a comparable sample complexity O log -- SemiSGD. Besides that their complexity is worse than ours up to a logarithmic factor, the source of the logarithmic dependence is also different. Both Yardim al. (2023); Zhang et al. (2024a) use multi- loop FPI-type methods, with each outer loop being a contractive mapping. Due to this contraction, both methods need only Ologe-1) outer loops, with each loop having sample complexity of Oc 1)). On the other hand, SemiSGD, being single-loop method, only needs the same number of samples as that of one outer loops in Yardim et al. (0023); Zhang et al. (2024a). The logarithmic dependence in SemiSGD's sample complexity comes from the non-stationarity introduced by the timevvrryin population measure estimate and behavior policy. In summary, Yardim et al. (2023); ;; Zhang et al. (2024a) need multiple runs of the policy vvaluation/optimizztioo and induced population calculation procedure, with each run having the same sample complexity as SemiSGD, which only needs one of the stochastic approximation method.
18

---

Published as a conference paper at ICLR 2025
C ADDITIONAL EXPERIMENTS
C.I GENERAL SETUP REMARK
All numerical results averaged over 10 independent runs with random initialization. 95% confi- dence regions are reported. The following parameters are shared for all methods in this set experiments unless otherwise specified: total number of samples 7 10 with the number of inner loop iterations being K 500 for FPI-type methods, constant step-size 10 policy operator I softmax with large inverse temperature (near-greedy).
Reference methods. We compare SemiSGD with vamilla online FPI and its variants with stabiliza- tion mechanisms entropy regularization (ER), fictitious play (FP), and online mirror descent (MD). For all methods, we use on-policy TD learning to learn the best response value function, and MCMC calculate the induced population measure. Specifically, for online FPI, we follow ZZhang al.) (2024a) to repeat the forward population calculation and backward policy evaluation alternatively; for FP, we follow Perrin et al. (2020); Laurière et al. (2022b) to mix the historical population measures with the current one after each induced population calculation; for MD, follow Perolat al. (2021): Laurière Laurieee et al. (2022b) to conduct an incremental Q-value function update after cach policy evaluation; for ER, follow Cui & Koeppl (2021) temperature (also called Boltzmann policies) for the policy update. We summarize the reference methods in Algorithm
the softmax policy operator with large
Algorithm 2: Reference methods
input: Initial value function yu- population measure No, and policy mo- T/K K do
for t == O, ..
Forward population calculation: P441 is induced by policy æe- if FP then
Pt+11 f ((iist)) + a4p4+1
(hiist)) +- Me++1
Backward policy evaluation: 4++1 evaluates Te with 14+1-
MD then
9++1 t (hisst) + 049141
g (hist)) < 9-+1-
10
11
ER then
Policy update: Me+1 = (Treg) (9(+)).
13
else
Policy update: TT+1 (((++)))
15
return
(Tr/K,H//K
Regularization.
To minimize regularization for all methods except ER, we use the softmax policy operator with a large inverse temperature such that
Lnr max Q(s min miin((s,a)) ((s,aa)) R3 2, E aE
log10
(7)
aeA
where L, to represent the inverse temperature, softmax is Lipschitz continuous with the inverse temperature being a Lipschitz constant (Gao & Pavel 2017). This setup ensures near- greedy policies with negligible regularization. One can verify that in experiments, the Q-value differences between actions are typically small, leading to a large La. Consequently, the theoretical regularization implied by Assumption is not enforced in our experiments. For ER,
small inverse temperature L (ER) = L2 /=0 to implement the entropy regularization. Regularization can significantly impact learning dynamics; see Appendix C.5 for more experiments regularization.
We focus on two convergence performance metrics: mean squared error (MSE) of the population distribution and exploitability of the policy.
19

---

Published as a conference paper at ICLR 2025
Reference MFE and mean squared error. We compare our results with the reference MFE distribution Mre. which is calculated by model-based FPI with FP. The model-based FPI consists of value iteration (Sutton & Barto, 2018) for the best responses and direct computation of the induced population measure using the transition operator. Then, the (population measure) mean squared error (MSE) is calculated as
MSE(M) = | - Mye
Σ (M(s) - SES
Note that this is equivalent to the 1-Wasserstein distance between the two measures for finite state spaces.
Exploitablity.
Perrin (2020) defines the exploitability policy as follows:
exploitability (T)) == max maxxas-pp Vss mx) Eorua (T;
where V(s; n, (u) is the value function determined by policy π and population distribution μ. The exploitability results in experiments calculated using model-based value iteration. We remark that although exploitability is a useful metric to evaluate the performance of the learned policy, is an operator determined by the underlying MDP, which may not be smooth and hence does not directly reflect the learning dynamics.
C.2 SPEED CONTROL ON A RING ROAD
consider a speed control game on ring road, i.e., the unit circle 8 = =0 1). At location & E St, the representative vehicle selects speed a, and then moves to the next location following transition = s + aAt (mod 1). where At is the time interval between two consecutive decisions. Without loss of generality, we discretize both the location space and the speed space using a granularity of As Aa = 0.02. Thus, both our discretized state (location) space and action (speed) space be represented by condition, we choose the
assume that the speed is bounded by 1, i..., the speed space is also [0, 1). Then
= A = {0, 0.02. time interval to be At 0.02 < / max a. The objective of vehicle is maintain some desired speed while avoiding collisions with other vehicles. Thus, it needs to reduce the speed in areas with high population density. A classic cost function for this goal is the Lighthill- Sarthhll-Whithanne Whitham- "bitham-Richards function:
0.98} [50]. By the
(1 (u(s)
2
(LWW)) (8, a. (8,a,
As.
Mjam
Ornax
where Pjam is the jam density, and Omax is the maximum speed. However, in an infinite horizon game, this cost function induces trivial MFE, where the equilibrium policy and population are both constant across the state space. Therefore, we introduce a stimulus term that varies across different locations:
1 r(s, a - b(s)
1 (1 (1-100
ju(s)
As,
Pjam amax
where the factor of one-half before the population distribution term is included account for the presence the new stimulus term. This new cost function makes the MFE more complex and corresponds real-world situations where vehicles may have distinct desired speeds at different locations due to environmental variations. Specifically, we choose the stimulus term as b(s) = (.2(sin 4TS) + 2). and set jjam = 3/S and amax 1. The discount factor is set as 7 1 As 0.98. To ensure the condition in 7 we choose large inverse temperature of L 10 for all
methods except ER, which uses (ERt) Lz/10².
The convergence of model-based FPI with FP is shown in Figure arguing the near-optimality of the reference MFE.
The convergence performance is reported in Figure 6 The MSE comparison (Figure 6al demonstrates that SemiSGD 1) is more efficient, with a much faster convergence, 2) is more stable without any stabilization techniques, 3) and is more accurate, with lower MSE. The efficiency gain of SemiSGD is partially due to its removal the bawkkrd-bccwward structure typical in FPI-type methods; we will ex explore more on this in Appendix C.3 Another observation is that although FPI equipped with ER
20

---

Published as a conference paper at ICLR 2025
100
2.9
2-
0,5
0,5
Iteration
Figure 5: Exploitablity of model-based FPI with FP.
or FP stabilizes, its learned population distribution significantly deviates from the reference MFE, evidenced by Figures and and 6c This illustrates the fact that the regularized MFE may be far from the true MFE. For the exploitability, SemiSGD seems to oscillate. However, exploitability a function determined by the underlying MDP, which may not be smooth. Therefore, exploitability does not directly reflect the learning dynamics.
FPT FR
Tojstattty
6a-
Seaples
Susgtor
State Space
(a) MSE.
(b) Exploitablity.
(c) Learned distributions.
Figure 6: Convergence performance on speed control.
C.3 NUMBER OF INNER LOOP ITERATIONS
When implementing FPI-type methods, we choose a relatively large number of inner loop iterations K 500 demonstrate the difference of double-loop structure from a single-loop fully asyn- chronous structure. In this section, we explore the impact of this important hyperparameter. Notably, when
online FPI is equivalent to SemiSGD.
Fixing the number of total samples T = 10 we vary the number of inner loop iterations K from to 500 for vanilla FPI. The convergence performance is reported in Figure 7 Evident from both the MSE and exploitability plots, reducing the number of inner loop iterations leads to monotonic improvement. This backs our theoretical analysis Section 2.2 and suggests removing the forward- backward or multi-loop structure can significantly improve the convergence performance.
C.4 FLOCKING GAME
We consider a flocking game on a one dimensional space = [0, 1]. We set the destination point Saet = 1. To form infinite-horizon game, connect the destination point to the starting point Sstart = 0. Similar to the speed control game Appendix C.2] at location s E S, the agent selects speed
[0, 1]. and then moves to the next location following transition s' s aAt (mod 1). Then we discretize both the location space and the speed space using granularity of As Aa 0.02 and choose the time interval to be A/- 0.02 < As/ max a. The objective of an agent is to reach the destination as fast as possible while aligning its speed with its neighbors. A cost function for this goal is:
r(s, a. 14) -(a² c(Sact neighbor(1u, 8)
21

---

Published as a conference paper at ICLR 2025
1033
10a
125
125
30
30
10
Exploitabilityy
10
MSE
50
100
150
200
20
40
60
80
100
Samples
109
Samples
(a) MSE.
(b) Exploitablity.
Figure 7: Convergence performance with different numbers inner loop iterations.
where e is a positive constant; neighbor(ju, 8) calculates the average location of the neighbors of s:
10t 8' s'u((' dss neighbor(H, 8) 1 p(s')ds'
where is the radius of the neighborhood, and pad the population measure with zero beyond the boundary. Specifically, we choose = 0.5 and r = 0.1. The discount factor is set as 7 = 1- As 0.98. To ensure the condition in methods except ER, which uses
choose large inverse temperature of I, 106 for all Lz/109.
The convergence of model-based FPI with FP is shown in Figure arguing the near-optimality of the reference MFF.
X1I-
3.8
3.6
Figure 8: Exploitablity of model-based FPI with FP.
The convergence performance is reported in Figure 9 population distribution has a gathering behavior near the destination, and SemiSGD the only method that captures this behavior (see Figure 99). Judging from the reported metric, we conclude that other methods fails to learn the game. One possible explanation is that flocking game highly sensitive to the reward function, whose supremum norm is small (R < As 0.02). As result, large regularization obscures the reward signal, leading to a near-come constatt policy and population distribution. However, other methods except SemiSGD cannot handle warr-greddy policies well, leading poor performance. To justify this explanation, we further explore the impact of regularization in Appendix C.5
We first want to highlight that the MFE
22

---

Published as a conference paper at ICLR 2025
X35
FP1 ER
Pap SAARIS
Sample
Sample
Stado
(a) MSE.
(b) Exploitablity.
(c) Learned distributions.
Figure Convergence performance on flocking game.
C.5 REGULARIZATION
As can see from other experiments, regularization plays a crucial role in the learning process. In this section, we explore the impact of regularization on the convergence performance of learning the flocking game. We impose different levels of regularization
SemiSGD, and report the convergence performance in Figure TO Recall that a small I. implies a large regularization. Consistent with Appendix C.4 large regularization (I,- S 102) obscures the reward signal, leading near-constant policy and population distribution. With moderate regularization (I, 10*), SemiSGD begins to capture the gathering behavior near the destination. And with negligible regularization (L, 2 10%), SemiSGD achieves small MSE. However, the greediness may lead to a high exploitability, as shown
Figure I0a
SIFE
20-00
11:
6.05
441
Sanuako
11
Straplo
30-12
Stule
(a) Exploitablity.
(b) MSE.
(c) Learned distributions.
Figure 10: Convergence performance with different levels of regularization.
summary, this experiment demonstrates the trade-off between regularization and accuracy. Regu- larization helps stabilize the learning process, but too much regularization may smooth out important information and drive the regularized MFE away from the true MFE.
C.6 NETWORK ROUTING
We consider a routing game on the Sioux Falls network graph with nodes and 74 directed edges. We designate node the starting point and node 20 the destination. To construct an infinite- horizon game, we add a restart edge 675 from the destination back to the starting point. On each edge, vehicle selects its that the vehicle will follow the chosen edge without any randomness. Therefore, both the state space and the action space can be represented by the edge set, i.e., S A = {er,... ... e75) [75], where is the restart edge. It is worth noting that a vehicle can only select from the outgoing edges of its current location as next edge.
edge travel to. We consider deterministic environment, meaning
The objective of vehicle is to reach the destination as fast as possible. Due to congestion, vehicle spends longer time on an edge with higher population distribution. Specifically, the cost (time) on
TThe topology of the network is available transportationneter
htcpp:://gittub..cmmm/ees
23

---

Published as a conference paper at ICLR 2025
non-restart edge is plcmng (4) = 1cj & eTS), where is cost constant. To drive the vehicle to the destination, impose reward at the restart edge: yllemm. (s. a, (2) c2 e75 Together, we get the cost function:
a(s,a, a. = c1 + eTs
c2 675
congestion cost
terminal roward
We set C1 10 and cg 10.
The other algorithmic parameters chosen as follows: the discount factor = 0.5, the initial state is uniformly sampled, the initial value function is set as all-zero, the initial population randomly generated.
Similarly, to satisfy 7. we choose a large inverse temperature of Lx = 10 for all methods except ER, which uses T. (ER) T.r /11//000. The performance comparison is reported in Figure 11 We only plot the learned population distribution by SemiSGD in Figure as all methods learn similar distributions. Notably, all methods except FPI with ER have oscillatory behavior in the exploitability around the same value. This is due to the highly non-smooth nature of the underlying environment and the choice of near- sear-greddy policies. In terms of MSE, only SemiSGD and FPI with ER achieve a low MSE, with SemiSGD achieving the lowest error and being the most stable.
FP1
120
2005
120
Sumple
Sumplo
(a) Exploitablity.
(b) MSE.
(c) Learned population distribution.
Figure 11: Convergence performance network routing.
C.7 PA-LFA AND GRID DISCRETIZATION
To demonstrate the effectiveness of PA-LFA, compare it with grid discretization the speed control example (Appendix (.2). The reference MFE is calculated using grid discretization with granularity of 1/200. We only apply LFA to the population measure estimate, as this is our main focus. The measure basis is chosen as
(s)s) = =fx((0) fww (s=ssss))) s,)T)),
where far is probability density function of the normal distribution with mean and variation v, and 8; is the center of the basis function. Specifically, we set c 1.2 and v = d2/2 and evenly distribute {
We run SemiSGD with d, states (grid discretization) or d2 basis functions (PA-LFA) for 7 104 steps. Recall that PA-LFA with de dimensional feature space has comparable operation complexity to grid discretization with d2 states. Other parameters are the same as the general setup. The final MSE (accuracy) comparison reported Table [ The MSE curves and learned population distributions are shown in Figure 13 and Figure 12] respectively. As we can see, PA-LFA achieves better accuracy than grid discretization for all d2 50. This is because by choosing an appropriate measure basis, PA-LFA generalizes better than grid discretization, as the representation capacity of span z larger than the grid discretization and the representation space of & is closer to the MFE population measure. This is more evident when dy is small. As illustrated in Figure 12 with just few basis functions, PA-LFA can capture the general shape of the MFE population distribution much better than grid discretization.
24

---

Published as a conference paper at ICLR 2025
Stace qpil
(a) d2
(b) d2 =
(c) d2 = 8.
(d) d2 = 10.
d2 20.
(f) d2 25.
(g) d2 40.
(h) d2 50.
Figure 12: LFA versus discretization on learned distributions.
Seagle
(a) d2
(b) d2 = 5.
(c) d2 = 8.
(d) d2 = 10.
(c) d2 20.
(f) d2 = 25.
(g) d2 = 40.
(h) d2 = 50.
Figure 13: LFA versus discretization on MSE.
D NOTATION
provides a summary of the symbol notation used in this paper. We introduce some supple- mentary notation to assist analysis.
Concatenation and direct sum. We consider Unite-dimensione Euclidean spaces as the parameter spaces. Thus, for any x E Rdd and y E IR,,, we denote their concatenation as (æ; y) E &di, We sometimes write it as the general direct sum between two vectors x @ y Rd @ R = 4dd, For matrices and operators, we have (A @ (x @ By) = Ax @ By. This notation is especially useful for handling the unified parameter f 0 @ 17 (see, e.g., Lemma 7. Additionally, we use 3 to denote the unified parameter space E = ddd e Rd
Unprojected parameters.
We denote the unprojected parameters as غ. Ö, and ij. That is
f n(()= II[E, aE)))
For any parameter E. in the projected region, we have ||E. TT s I|c. - -El
25

---

Published as a conference paper at ICLR 2025
Table 3: Notation.
Notation
Definition
(XX), M(x)
Space of probability and signed measures on space A' Probability simplex
A
8
Dirac delta measure
0, A
Action and action space
8
State and state space
R
Reward function and its supremum norm bound Discount factor
P.P
Transition kernel and operator
T
Bellman operator
Q.q
Action-value function
M.
Population measure
T
Policy and policy operator State-action feature map State measure basis Norm bound of v Feature/measure space dimension Linear reward function parameter Linear transition kernel parameter Population measure parameter
F
d
w,
0
Value function parameter Concatenated parameter and its parameter space Projection operator
f
II
D
Value function projection bound
Problem scale (H = (1 7) + R 2F)
g
Semi-gradiens
G Go 4
Temporal difference operator
G
Gram matrix
L
Lipschitz constant
w
Contraction constant Step-size
m, P. G, le
Ergodicity constants
Backtracking period
Steady distributions. We denote E D(S) as the steady state distribution induced by parameter = 1)) i.e., by policy I (0) and transition kernel and reward function determined by population measure parameter 17. Mę is the marginal distribution of the following two steady distributions:
me(s, a) = (e(s) s), (s,5,, a, 8' aa) == (=())) (a 8) P(s' 6') 8,a, m)) |
We write Eg as the expectation over the steady distribution induced by ç; should be clear from the context which steady distribution is used.
Semi-gradients and temporal difference operators. Here we review the definition of semi- gradients. With slight abuse of notation, we use a single operator g to return semi gradients for both the action-value function and population measure. It should be clear from the argument of which parameter the semi-gradient for. Specifically, with sample tuple
a, (s,a,r,s',dt we have s(E: 0) (a(O; O); g(m: O)) (G) :p(O); G (s')),
where Gy is the gram matrix of the operators defined as
basis 1b and G& and the temporal difference
Go( - (bs ((s, -665 d')) p(O) = ó(s a)r.
Notably, Gø is a constant matrix, and G is a Gram-like matrix that depends on the sample tuple. Therefore, we sometimes drop the subscript in G and use other subscripts indicate its dependence
26

---

Published as a conference paper at ICLR 2025
on the sample tuple. It should be clear that any G with subscript other than v refers G When the sample tuple is an online observation at time step t, ie.. O2 = (St, at, Ft, $c-1, ac+1), we use shorthand
g = g(:;O.).
G. = (O,), P= (0,). v/2 - (O.).
Backtracking is an analysis technique introduced tackle rapidly changing Markov chains Zou et al. 2019 Zhang et al. 2023 2024b). It considers virtual stationary Markov chain by backtracking a period r, fixing the parameter &r-r. and then sampling the Markovian observations with the fixed parameter. By the ergodicity of stationary Markov chains (Assumption 3 the virtual trajectory rapidly converges to the stationary distribution induced by & We denote O2 the virtual observation tuple on this virtual trajectory at time When we consider the semi-gradients on this virtual trajectory, we write out its dependence on Ö₂ explicitly:
g (:-(;; Go-r(O,), ((-)( (+,)
with the subscript indicating the backtracking period r.
Mean-parh semi- gradienadsnnss are the expectation semi aemi-gradients over a steady distribution induced by a parameter:
0 = [3 O),
where the subscript & indicates that the observation tuple O follows the steady distribution induced by g= = (0: 7)) More explicitly, the states follows the steady distribution corresponding to transition kernel P(. ()), and the actions follow policy (0),, and the rewards are generated by r(,,', 7))
Similarly, we have
GE (O)), Pe EO)(
Jे. EgV(ss).
When the parameter has subscript εo. also shorthand
-o Ic.
G. Ge Po = Bco v. Te..
For example, Dr = Dg and g. = og..
E PROOF OF PROPOSITION
Proof. By the Bellman equation, have
(ī)(s,0) = r(s,a, + I "T ('s s,a, ds'd'd'
SXA
= (d((,,)), +7
(s' (o(s, a) (M ds da'
5xA
a(, + / Qur(s', Marbls (dssssdddddd
By the transition equation, have
(x) = I
SXA P( P(818,, a M)r(a (s)dsda
Jsxa (0(8, (), Rar x(a) s)r (s) dsda
ISna (W(5), ((s, a(a s) dssda
((6)),
17 a) 8) (s ds)d
SSXA
27

---

Published as a conference paper at ICLR 2025
F PROJECTED MFE AND STATIONARY POINT
We call value function-population measure pair stationary point if the mean-path semi-gradient evaluated at this point zero. Section 5 and Appendix H show that SemiSGD converges to stationary point. Ideally. want the stationary point to be MFE (Definition D Proposition [ and Appendix[B show that for linear MFGs, images of T and P are within the linear spans of ø and vi, indicating the linear structure of the MFE. However, this does not hold for general (non-linear) MFGs, hinting the discrepancy between the stationary point and the MFE for non-linear MFGs.
We define the projected MFE using the Bellman operator and transition operator composed with the projection operators.
Definition 3 (Projected MFE). We say & = (0; constitutes a projected MFE if
(ø, 0) 1 (0. 0) ( n) 1. (v), m)
where T. and Ih orthogonal projection operators onto the linear spans of é and vh, respectively.
It should be noted that the projection operators determined by the inner product structure of the function spaces. They can be explicitly expressed as
IL 20
(0. )).
where ø is the function basis and inner product on MMS), giving
) is the chosen inner product. Specifically, we choose the L2
- + G (b)
For the projection acting on Te, we choose the inner product induced by the steady distribution jlg. i.e, (1,9)us (()))()))((do) Then, we have
T= = GT (o
where Gg is the Gram matrix of ø w.r.t the inner product (s.)) Note that Ge is different from the TD operator Go or Gg defined in Appendix D which is only Gram-like.
We now ready prove generalized version of Proposition Recall that for linear MFGs, the
projected MFE is the MFE itself.
Proposition 3 (Projected MFE as a stationary point). & is a projected MFE if and only if (e) 0.
Proof. For a parameter { = (0; m). by the definition of mean-path semi-gradients, we have
D (0) =Eş [ō(s, a) (o" (s, - (s', r(s,
0s (7) =Eş m - ((s'))
where the observation tuple (s, a' hand, by the definition of the projection operators, we have
s', a') follows the steady distribution induced by &. On the other
a Id) (d. 0) G (0) Te ()) 0TO,
where Id is the identity operator. Suppose Φ is linearly independent. Then, we get
(Tl Te - Id) (e, 0)
+ G (ob, Te (0, 0)) =0
(ò, Te (0, 0)) = Ge
- (0, Bg (.(...)) + - (s', a' )8) - EE a)o as) =0 de
- Eg [o(s, a) a) n) + + (8', a'))] Belo(s, (s. =0
- leg [d(s,0] a) (6" as) n0 (s', (...)))-rsss. =0
(0) = 0.
28

---

Published as a conference paper at ICLR 2025
Similarly, for the projected transition operator, we have
(T&P Id) n)) = 0 s GT (1b, Pe (1) m, - +b
(v, Pe (V) n1) Gwm
Sena ( s,a, s) (s) Gw 0
SaXA
Ee/1i(s'11 G =0
(n) = 0.
Therefore, by Definition is projected MFE and only gE
G PRELIMINARY LEMMAS
We present some preliminary lemmas that used throughout the analysis.
Lemma 2 (Norm relations). For any vectors I, y, have
| @ y|l = ||=]|| + |ll
|| + vlli < ||yll + |
o ① ull2 - || + llall2,
| + vll2 = 11 + ||=113
| + |1yl 12 < v /max (d1, d2
a + ul12.
1x u/ max | 1lvl
x vll s 11vl + 1
||||| - || vll
|^|||||b|l _ 1| 4 v/13.
I S || ① vll
Proof. All relations are basic facts of norms and can be easily verified.
Lemma 3 (Gradient bounds). For any parameter (0; n) and any observation tuple O we have
[0; O) S(1 (1++))1011 + R
[[g(n; O)] <F||n|| + F.
Moreover, suppose [[@]] s D and [| = Ler H = -11+)) R 2F. Then, we have
llo(;: S H.
Proof. By definition, have
llo(0: O)K (1G)(0)0- < [G [lp(O)]
<l((e),))]l(<<,.a) 10(8. a' |||||| [ ())lsss,))
<11+))100|++
where the fact that []((s, a)]l _ Similarly, we have
lla(:: O)| < l 0) || ((s'lla s (Gellopllnll + +l0(s)))
The operator norm of G satisfies
|/ (()) (s)dds)
< sup / [1)())] (v), n) ds < F, 1
||Gollop- = sup ||ann]i = sup
lllll==1
I|lll =1
where the last inequality uses the norm bound of ab and the fact that (v), r7) is a probability measure. Therefore, we get
[| O) 2F.
Then, Lemma indicates that [|o({; H given that ||0|| & D.
29

---

Published as a conference paper at ICLR 2025
To be more general, Assumptions and 2 are stated in terms of the differences of population measures and value functions. For the case of presentation, we will develop our results terms of the parameters, and state the more general results in terms of the differences of population measures and value functions without proof. We need to first translate the Lipschitzness assumptions in terms of the parameters. In the rest of the paper, refer the following lemma when need the Lipschitzness assumptions in terms of the parameters.
Lemma 4 (Lipschitzness in parameters). Assumption 7 and Assumption imply that for any two parameters č (0) and & (02; 12),, we have
Pm - Pm llv & Lp LpImm 72ll. Te. (-1 To, (- r)] L 110 82l1.
Il - I'z --malls 1lco S Lr Lrll -22l.
Proof.
The proof is straightforward noticing the fact that
(b,, n) 1|Tv = / (n) ||lll
n7" ||>l|
ds S Illll & deblmnll. (ss)
and
|l (6, 0) 11 = |10T o(s [1]01Ilo(s, a)lll I ||0||-
Lemma (Lipschitz steady distributions). For any two steady distributions 11 and p/ induced by parameters & (m) and Ee (02; 12), we have
l p lTv S aL (110 02/1 + 1lm 72(1))
where o 2 mp") mpp/(1 p). log, m
m- and = max {Lp, L.). Involved constants Since us and μe are marginal distributions of pg. corollary,
are defined in Assumptions 1 to we have
lle 1ly S aL (110 02ll + 1l -22ll).
||,,, - PeallTV S aL (110) 02| ||
-22ll)
Proof. We first prove the last inequality in the lemma. By Mitrophanov 2005 have
Conollary 3.1),
|M,, TV S (a Ps - PEa lTv,
where Pe represents the transition kernel determined by policy T (0) and population measure v, and
1 ((>))) P() 8 n)ds
1 |SxA ((s)oo(a|s)P)) (,, (s, n)sda
| Pe == sup (EM(S)
= sup (EM(S) Ivll
TV
ll l
By the triangle inequality, have
||اا Mea lrv S ol P(o Piommllrvv + P(l P(osma)llv
(8)
For the first term, by Assumption I we have
1/5 SxA
P(o - Plormillyy = sup GEMiS) 1
((s)To (cls) -- dsda
1/ SXA a(s,a) a(s,a) (P(-1s,a, - P(- a,) dsda
< sup sEMiSxA) 1
TV
[P -P ITV
<Tp 7/21-
30

---

Published as a conference paper at ICLR 2025
Similarly, for the second term in (), by Assumption we have
VeLA (()ss( (als) TT, s))dsda
|| P(emm)) P(emm))llT
sup
SXA
eED(S) I
TV
< sup VEDIS Iv
((8) 18, 12, (a [a|s) 8) - To, (a s)ddedsdss
saXA
sup vED(S)
g(s)) || (:1s) (- ( ds
rv
[ ((s) Lx 02||ds
< sup (ED(S) |
L ||0
02
Let == max {Lp, ] Plugging the above two inequalities into (8 gives
| - Peallrv S ao (l 72ll + 10 - 021l).
Then, by the definition of uee we have
(
l1e - 16,
IMa. (s) (a)s) s) - -Me (s) s) dsda
exA
(INE, (8) - Mea (8)1 To, (a () + Mes (s) |To (als) ()) To, (a| {)) dsda
SxA
l - MeallTV + - (EL ||=e, (-1 - mo. (-1s) s)]
< 2) (l|m 72ll + 110: 02ll) + L 110 02ll
<(a - L (Ilm - -ell + |10 021l)
Similarly, by the definition of u we have
1 1 lTv Sllng, - 1Iy + Lr Er|mm - 7ell + I=1101 - 02ll
SoL (llm 72ll + 110 0211).
Corollary 2. Similarly, for steady distributions induced by general value functions and population measures #1 = M.) 42 M2), we have
max [11m1 - Halliv Ill| - Pillav, sallrv,llut Illi p livl } so ( (1 - M2l + L= Q2
Lemma 6 (Lipschitz temporal difference operators), For any two sets of mean-path temporal difference operators Gş., &el, Pe, and G Peas Ve, determined by parameters E (01:)) and
& (02) we have
||GE, - -Gaall SaT(1 + (1(0 021l + || - 7/21))=
|1ps. - -eall SoLR (10, 02ll + ||m: n2ll) L. 72
11 - -eall SoLF (1 02l1 + ||m - -72ll)-
where a and are defined Lemma and L, defined Assumption
Proof. By definition, have
I/ s -) 70(5' ( (s,a,s', u (s, dsdads'da' da'
||G;, - GGa.ll
<
52x ||((s,) v0(s
(pt. (s,, - (s, .'') dsdaad da'.
31

---

Published as a conference paper at ICLR 2025
Since (lo(s, a))l - 1, we have [ - s 11+- Then, by Lemma 5 have
||G - G = (1+))) (10) 021 + || 72ll).
Similarly, by definition, we have
11 -Peall = |1 sxa
- -ls (s,
[ ISXA (r(s,a.)) | (s) nes (0, (x. + u (8, am) r(s,a, nall) dada
Rllus, - - llv + Lr 1m 7ell
SoLR (10) - 021l + Ilm m2ll) + L. 7211,
and
1& - ts S Fllm - Pel SOLF (1101 02ll + ll - m2ll))
Lemma (Lipschitz semi-gradin eemi-gradient,. Given a aixeed semi- aomi-gradient operator g (which can be a mean- path semi- mmmi-gradient), for any parameters E2 E E, we have
((((5)) - g(Ea)ll S Hl|s - E2ll- Let & (11: and &2 (2): For any { (0; m)) such that ||0|| S G. we have
lā (E) De. (E) & H max (Lp, ] (1 021 + 11/ - 72 I) L,lim - -m22l-
We first show that the semi-gradient operator is Lipschitz in its argument. By definition, have
Proof.
19(E1: O) c( O> (G₂(O) G.) E2)ll s (G)(()) Gylloplls - E2ll. We get the result by noticing that
(O) @ Gællop S max (O) (oo |lop) max (1 + 7, F} s H. Next, show that the mean-path semi comi-gradient operator is Lipschitz in the parameter. Another representation of the mean-path semi mradiigrrdentt
g5. (G 0 Pe:;Gun ve..)
Therefore, by Lemma 6 we have
||0c. (E) - (cx S G|, Gg.00 - be, + beall + || - Gopp Tb. + Tea
<D GGz G5all + |!ōç; - bg. + |ig - &
<a R+ F) (110 - 021 + ||m - 1/22)) + Lrllm - 7//1-
H SAMPLE COMPLEXITY ANALYSIS
H.1 KEY LEMMAS
In this section, we first decompose the mean square error into different terms, and then bound each term separately.
Lemma 8 (Error decomposition). Let & be the optimal parameter. Recall that by Proposition 2
g. (E.) = O. We have
BllE++1 - 12
SR11 - E.1
=BIls, 12 22,,E (Et - Er, Br(Ee)) + + alll):(E:))1
EllE: 12 2 (E.))((E:)11
20, (E: {., (e.)) - g_.))
(descent)
-2,,EE (E. E., 0. (r.))
(progress)
-20, (E. E., - ((-r(E)))
(mix)
-0,,1E. (E+ (r.)) (E-r(E)))
(backtrack)
32

---

Published as a conference paper at ICLR 2025
Lemma 9 (Descent). Let &. (0xin=) be projected MFE. For any parameter & (0:n)
BB A Ad, denote AO 0- 0. and An 1I T)-- We have
-nn n. Be ge. (n.)) S -Amin ( | + (1 + ([An)). -00 0. (0) (0.)) S -(1 -1-111 Ammin (Gg))110012- + OLH
I(1 + [| + L. A0II.
That is, neither -1e nor (0) is guaranteed to be a descent direction. (GØ), (1 - --))))))) >min (G5.) Suppose 30 LH + Ly S 2w. Then, we have min (Gm),
Let w =
(5 E,, (5(5) - Dg. (S+)) S -wll5 - Exll?.
Proof. We first focus on the first two inequalities. We denote An == 1Ι and AO = - 0.. For the population measure parameter, by definition, have
A,, 0e (1) 0g. (n-)) = (An, - G. Any 3rE we.)
Note that Gb is a positive definite Gram matrix if &b is linearly independent. Then, by Lemma we have
- -An, (n) De. (n.)) v - (An. G + 11 - v5. ||
Amin
(G (G |l +O + (101)).
(9)
For the value function parameter, we have
(A0.0c(0) (0) Dc. (0.)) (A0, Gg. 0, Fe.. GG (p)
= (A0, -Gg. fg..A. A0 + (Ge. -Gg)0 + :e - -gs-)
S (A0, G5. AA) + +DIGG - Gelll |B|| + 110g - &e.. F.. ||1
By Lemma we have
(A),5e(0) De. (0.)) s - (~0, Gg. A0) + (1 + +) +oT.[(]A0]| + |Anl) Inll).
(10)
For matrix G, we define Wmin (G) min - (z. Gx). For GG., have
Wmin (G..) min Eg. 0T o(s ()((s) 7 a Te) = min Eg, 1 - yuull ||0
110 =1
where u = TTo(s, a) and u' = 8 o(s's "'s'.a') .²). We have
1 [R[u²) Rin = - (R[u²) + +E(u()) R.[u
EE E|uu' S 2
Therefore.
Winin (Ge.) (1 (1-?) min Eq. [u²] = (1 (1-7) (T ((b0" = (1-7))umin (6e.)=(10)))
(Gt.)
||0|==1
(11)
where Gg. is the Gram matrix of the feature map & under the steady distribution induced by E., and the last equality uses the property of normal matrices. Plugging the above derivation into (TO) gives
(A0, (0) āe. (0.)) < ||
A |
(12)
It is clear that 9 and (2) are controlled by both ||| and Anyll When
|///|
>
A
12
suggests that ge (0) may not be descent direction for |A0|] when
|
>
suggests
that 7e (n) may not be descent direction for ||
However, combining and 12 gives
(Ac. (E) Øe. (E-)) (1 7) (G&, ) 1 Amin (G+))IAn| 2 +LFFIAAn] -
- A (oLF oL 2F) L.) An|l-
33

---

Published as a conference paper at ICLR 2025
By Lemma
we have
(AC, (c(5) δc. (5-))
(G (Gg,). Amin (nin(G)))lAEII +OLH|ASI 1 2(0LH + (
s min 7) Amin
1.)
s min((1 - Amin (Gg.). Amin (G / (30TH + I..) ||AE||.
Let w = 1 min (1 Aenin (G..) Amiu (G&)} Suppose 30 + Ly S 2w. Then, we have
2
(AC. (c((( 0ç. (5x)) S - w||
The above inequality suggests that (e) is descent direction for || if the Lipschitz constants small enough.
Arj
R4
A6
Rd
B
-Be(n)
An
Rd
20
0 (vy)
0.10)
(g(E)
(0) 1 (r))
A#e An
(e())) AC)
Figure 14: An illustrative example for Lemma I where - (E) gives a descent direction, while Dc (9) does not.
Lemma 10 (Progress). For any (0:n) in Bdd x A da and for any time step t and period have
(T)((() (E)-(E) S ou--
where Cprog == max L,,,, Lr) 2 2..FF.
Proof. By Lemma 7 we have
((d(E) - (E)Il s LLH (100 0 + 11 Th- II) + Lr - 7h-r|1-
According to the update rule of 0 and 17, have
10 0--1| || S 0 0--1/
| 1 0:- (0, 1)
1177 1 || < i/ T--l/| ||a ( (1-1)) ||-
Since ||6c-1|| & D and ||m--/|| S || ||| = 1, by Lemma 3 we have
||: 0--1 il + ||m 7-11l || S a ((1 (1++)) R) a 2F a.-HH.
By the triangle inequality, we get
(E) (E)+(E) SOLH
Σ - -
| --1-1l
1m0
Sa ToLL 20,-
=0,,, Cprog
where we require that the step size a, is non-inereasing, and Cprog = max(L Lp 2T, F.
34

---

Published as a conference paper at ICLR 2025
Lemma 11 (Mix). Let Fi-r be the filtration generated by the history up time t For any {= (0:n) E BD A that is independent of Dt-r and Qt-r conditioned Fi-r, and for any time step and period т, we have
E
D (E: Õ,) - (c-r(E) Fr-.)
(
mpp H.
Proof. We denote Pt-, the observation distribution the virtual trajectory by fixing the transition kernel Ps. at time t т. We have
E Br (5, - Dc- (5) F Fi-7]
1 S2XA2 (o(3,a) (r(s, a) + r0= (8', a'y0 - (s,,))))))) :0(6)) -((Fea)
-ol F(rr)) -10 (o)
Pa B) n llvv
<((1 + + + R+ F)
Since Pt-y and 1 share the same policy To.-. and transition kernel Pe..., we have
P ner lIrv (.
veerrllyy S mp H,
where the last inequality uses Assumption 3
Lemma 12 (Baketrack). Ft- be the filtration generated by the history up to time t - T. For any & = (0; m) E BB, x d that is independent of Dr and Dt-r conditioned on Ft and for any time step t and period r, we have
Br(E, O.) (x, Fi-r]] Oback((ac
E
where Cback(T) = (T + 1)LH2 + F.
Proof. By definition, we have
E 0.) - - F(-T]]
sixde (Co()) (P.(0,
= do
52XA2 (0)00))))(00=00000// = o|Fr-) - (p 0 (0) = F )do
<(11 + 7)D + F)[|P P
+ Sax (pm @v) (P:(O, =0 F(-7) Pt (O: do
TV
1 (pn, - Pm..) (mm..Pmm.) (o)Pt-r FFFF
TV
<((1 + + F)JP, - + L, 11 n-
where P; and p are the distributions of observation at time step L on the actual trajectory and the virtual trajectory, respectively. By the proof of Lemma 10 we have !| Th- ll S 04-7T 2F. Therefore, have
F. (5, O.) - gi (5,
[+-
H|| Pt--llrv + 20
(13)
Let = be the set of all parameters. We first expand P, with conditional probabilities:
Pi(O, = (s, ( (())
Pi(s: = Str) = - =)) (a
P(s' |s, 1 Et a (a' s')dgd'',
35

---

Published as a conference paper at ICLR 2025
where 5 (0: 1) and 5¹ = :/)) We then decompose P1-7 into similar form:
P = (s, a, s', ,d)) F(-r)
=Pt-r (5t = $ re-r: 8L To. (al s) P a, Tt (a'1 s')
=Pt-r (3t = s /(rTTi 81- no. (a P(s 18, 5, To, (a' 5')
P =E 8 s)) = = -
Sc St-1 E, 8, a)dEdE'.
Therefore, can decompose the distribution difference into four parts:
Pt P
- -/ (P((s = s F(-r) - P1- = F(-r)) = El (1-7,,11777 88))
To(als) P(s' s.a.n)) 6 Ee-rr 8tr =
= E, =s ao I s')dgde'
(S))
Pr- = 8 Fi = 5l E1
8) (To(a 8) - To , (a|s))
E2
P(s'
P(s'|8,0, 8, a,
P((Et 1///)8,)1))(((( S2-1 01 E, = a a)To (al (oddss)ddd s')dE
(S2)
Pa-+(h =8 Fi-r) P. = El St-: 8)50, (a 8) (P(s' (8,,,11) P(s' a,
PE E'
8 86- E1-1 = {. 8,a To I (s')sss)))) 'dEde
(Sz)
+
Pe-r (3r- = s8 F( P: = El [1-r, 8t-r 8 = 8) (a 8) P(s 1,,61,,,,,,00 a,r))
E2
PE = =E' &t = E, = 8,0 =a)= (TO (a' 8s) To__ (d' ()) agdg'. (Sa)
We now bound each part separately. By integrating out the later part, S becomes the marginal difference of the state distribution:
[
Sidddads' da' = (((())= Pe- = =s(F(r())
(Vorecee Prlfe-1 = = P s,,,n')
P((E = 16 E, s,a, = a) (a' s s')dEdE'dada da' ds
(P((si = s| F( - Pt-r(3, = F. ds
< <|[((s = -FFrr) - Pt-- 1
= |P--1(3: = = F(-r) - (.. F
By Jensen's 's inequality, we have
1 = FFFr. - Pt-r(Kt = (
SXA2 P0-1 =
- (
( )ddddadd
<
Sx PO.1 = (8, a') [F - Pr_ -0,00, (o),,, rV
dodada'
= Pi-1(01- = -F = = ( TV
That is, S₁ is recursively bounded by PP-1 Pr-rlITV.
36

---

Published as a conference paper at ICLR 2025
For S2, we have
S2dsdads'de da'
S2x,22
= =) (To(aa s) -o._ (a|s))
SXAXE
8.00 aa) (a' | ss)ddss s')dd'da'ds da' de' dsdadg ( SXAXE P(s/)s,,,7))PP(E = - = =
-=-(==8111) Pr(EE-1 = -1 (To(a)) 8) - -o (als)) dsdadg
SxAXE
< SxE
P((E-11 = El S1 = [- - TB._. (1)5)llly dsdg.
By Assumption 2 and Lemma 10 for any E E such that P:(E--1 F(-r) o 0 (which is
equivalent to (s = El E 8 81 = 8) # 0 as all policies are ergodic), we have
TT () To. (-1 [) TV S a ( 7)G R).
Therefore, we get
JSP S2dadads' San-r(T 11 (11
+] (1)=((+1))) R))
-8 = - = s)dodg SxS
=0 1) + + +R).
For S3. we have
Sydsdads' da'
8*x
x"AXXX Pe-
= ( P E 86-T, 5)00, (a|s)
(P(5' P(s'1 s, a, m)-)) PolEe = 11 = 5. = =s = a)
(/1 (/ (a') (d''ss) dsdadd' 'dgg
Pa- Fi Strr (t)) 100e.-(()) (a|5 =s
AXAX
|P(-|s,a,n)) p(.|s,,, (,lssa,n n.s,a, Pi(Er = g' ( E. St 8, at a)dsdadedg'.
Similar to the bound for S2, by Assumption and Lemma 10 for any g E such that Pr(Ee = Fi of have
|P((1,,a,77) - ((.1,,,0,2-7)111 S 20p
Therefore, we get
Sydadads'de da' son-rLLp
P Ft = E 8t
=
Sax
SXAXE2
ne T8._ (al (o))))
-' 8t = E, 5, a)dsdadEdg"
TLp.
Similar to the bound for S2, for St, we have
Sadsdads'da' S CterTIa((( + 7)G + R).
S2
Plugging back the above bounds for S,, S2, S3. and S4, we get
| - Pt- Pt-rllrv $ Pt-1 Pt-r lla + (L R)+ LpF)
37

---

Published as a conference paper at ICLR 2025
Recursively, we get
P - Pt--llv S 2LH (lav-1) S a 1)LH,
where require the step size to be non-increasing. Plugging the above bound back to 13 gives the desired result.
H.2 PROOF OF THEOREM I
Theorem 1.
Let (0.; n,) be a (projected) MFF. Let {3 (0:; be sequence of parameters
generated by Algorithm(] [
Then, under Assumptions 1to 3o + Ly S 2ww, we have
E Elec++1 E. < (1 a. -..1 + a + aj log a, L3 w
Proof. We denote AG = E.. We first plug Lemmas 1 and 3 into Lemma 8 to get
E A6++1 11 <(1 w )E| A + H12
+ 20, (A, gr (5t) - 0 G.- (Et))
(14)
+ R (AÇ, -r-r (Et (E,)
(15)
+ 2,,E (AC, 0r (Et) Br(Et))
(16)
For [4]. by Young's inequality, for any 3 > 0, we have
1 E
2E (AC,, (Ex) De- (G.)) < 3E AC 1
1l (E)) (.(5.))
3
By Lemma T0
we get
2E (c - Bc-r (Ex)) $ 3E Accl + a
(17)
prog
For 15 note that conditioned on Fi-r. Pr-r - is determined and @r-r is only dependent on the virtual Markovian trajectory. Thus, & is independent of O and g:-r conditioned on Fi Therefore, by Lemma and Young's s inequality, we have
2E (AC.. (Ee) (t-r(E)) 22 [E [AG
Ft- (E,) - - (Et) 1F--1> 2T E || [(-+]] [E (Ga- -c-r (Et) Ft--1ll
2mmp HE ||
<8E ||
1 2 2 2
(18)
For (66, we cannot directly apply Lemma 12 & and ge are dependent conditioned on Fe-r. To
proceed, we employ the following decomposition:
(At (E+) ge(E)) = E (Ac.. (E+) (E--)) (gc(E)) - ge(Ee-7)))
H.
E (E+ E St - (E( E (AE,- -, (Er-r) - (E(()-)))
H2
Hs.
For H1, by the Lipschitzness of the eemi-gradient (Lemma) 7 and Lemma 10 we have
S 20,, 2 E..EE |
For Hg, by Lemmas and T0
we get
H2 < 2H O.-
For Hg, - is independent of ge and g:-7 conditioned on Fc Similar to the bound of 18) by
Lemma 12 we have
H3
E
E A Fo-r] (6, - (((()-))(FF-)))) AE
< E
[||
[[-r]
| (E.-7) Dc- (()-r) Ft-+1111
5at-r7
||
38

---

Published as a conference paper at ICLR 2025
Then, applying Lemma 10 and Young's inequality gives
2H3 (ot-TTChan (ot- + = 20 2 / + -
Plugging H1, H2, and H3 back into decomposition and applying Young's inequality, we get
21E (A (Et) (Ex)) $2gE A
TH2 a (2HCback 8-1 (Chaok + +4H+))
(19)
Finally, plugging the bounds
17 19 back into 14 16 gives
B| 1 <(1 204w + 4a 3 2e + 0 222 + 40400 H2
+ az ( C prog + 3 m² pa H² + P + B- + 4HH)))
Now we choose T not too small such that
log a, log
Then, p² S dg. We require the step-size to be non-increasing, and
Σ
ar a to0 and log ai = =
The first condition indicates that lim sup 01/2/ a; == Ca,1 < co. And there exists Ca.2 2 > such that 01/2/ar /a S Ca,2 lim sup, 01/2/ a for any time step t. The second condition indicates the existence of Ca,2 > 0 such that Ot-r C0,300/2 for any l. In conclusion, we have
at- S Ca,301/2 Ca, C.ay.
Then, we choose B = w//4 Together, we get
E A 2 5(1 a |E| DE 2 at (112 2112= 4TC, 112)
(20)
ai (-² C Cprog Clack + AH²) + m² 11²) + C2
=11 - a 1 af C2(as) at Cs(as),
where we use C2 and C3 to encapsulate the terms in the right-hand side 20 Plugging back the definitions of Oprog and Cback gives the final result
B| 2|2 u1- AC +H- log a, 1)+ {L,, Lp, L H
O(a log" at 1
w
where the asymptotic equivalence holds as a₃ + 0.
H.3 PROOF OF COROLLARIES
Corollary
1
For constant step-size ot coo, we have
H2
El E.11 e e E.113
+
0
w
w
Proof. By Theorem ! we have
T Σ 1=
El|ET - 12 <(1 - (nnw)"'150 22
kow)
<e -oon
1550 - - + On (C2 + C3
Ton'
1550 12 + w H² O log 1)
Corollary 3 (Linearly decaying step-size). We define linearly decaying step-size sequence aq
4/(w(t 1)), and the convex combination ÊT T[T+1] ΣT Ei t&g. Then, we have
H2 log
E Er - E 5
TT
39

---

Published as a conference paper at ICLR 2025
Proof. Rearranging the result of Theorem I gives
1
1 B| B|
04 C2 + of
EJ 16+11
C3.
2
a
Substituting 0g = 4/(w(t + 1)) and multiplying by gives
(t 1)t
t(t+1)
8t
321
|B|| - 2 El AE
E
A
112
C2 +
C3. (21)
2
w² (1 +
(+ + 1)2
By Jensen's inequality, we have
T
1
-
(22)
T(T
1)
1=0
Combining (21 and (22)
gives
t
4C3
T
H log T w2T
ET 1x S
C2
= 0
+
++1
W t=0
(t
+ 1)3
I CONVERGENCE WITH GENERAL POLICY OPERATORS
Assumption for ensuring contractivity can be restrictive in practice. Its requirement for the policy operator to have a small Lipschitz constant typically requires large regularization (Yardim et al. 2023
Angiuli et al. (023). However, this may limit the algorithm to only learning near-uniform policies
(Zhang et al. 2023), and the learned regularized MFE (Cui & Koeppl 2021 Anahtarci et al. 2023
may be distant from the true MFE.
On the other hand, without any contractivity or monotonicity assumption, the existence and uniqueness of the MFE are not guaranteed. Assuming MFE exists that satisfies Proposition [ we can replace Assumption 4 with an alternative assumption on the reward function and measure basis to ensure that SemiSGD converges to a neighborhood of the MFE.
Assumption 5. The reward function and measure basis satisfy that L, w/2 and R+F S w² /(4L), where L. / /max (d1, d2) max (Lp, ] and w (0, w| is problem-dependen constant.
Theorem 3 (Convergence with general policy operators). Suppose e. (0.; is an MFE and Bund Then, & is the unique MFE and a linearly decaying step-size sequence 0g 4/(1 + wl) gives
+ (
(DLL,
log T
ET E.1l S. S0
2
Theorem 3aeeemm3esee establishes that, SemiSGD with a general policy operator (no restriction on Lę) converges to neighborhood centered at the MFE, whose radius scales with the sup norm of the reward function (R), its variation (L,). and the measure basis (F). The convergence rate is not compromised. To the best of our knowledge, this is the first theoretical convergence result for learning MFGs without contractivity or monotonicity assumption, although the convergence is to a region rather than a point.
As discussed in Section 2.2 with general Lipschitz constants, SemiSGD is essentially a stochastic approximation method on a rapidly changing Markov chain.
Remark 3. Assumption or Assumption 5 is purely for theoretical convergence analysis. None of them is enforced in our numerical experiments. Guided by the insights Section 2.2 we use near- gear-greedy policies without regularization or additional stabilization mechanisms in our algorithm implementation. Our numerical results demonstrate that SemiSGD with general policy operators converges efficiently to point.
We acknowledge the remaining gaps between our theoretical analysis and practical implementation: 1) Although the condition in Theorem Bl arguably more practical than the small Lipschitz constants condition (Assumption 4), as it is structural condition satisfied by class of MFGs, it cannot
40

---

Published as a conference paper at ICLR 2025
explain the empirical success of SemiSGD for general MFGs 2) The convergence region bound in Theorem 3 may not tight, and empirically the convergence region can be significantly smaller and may even converge to point. These gaps partially result from our limited understanding of stochastic approximation methods on rapidly changing Markov chains (Zhang et al. 2023) and call for further investigation into the structure of this class of methods.
I.1 PROOF THEOREM 3
Our convergence result for general policy operators leverages Zhang al. [2023 Corollary 3.10) for stochastic approximation methods on rapidly changing Markov chains. Thus, we only need to verify that SemiSGD satisfies all the assumptions in Zhang al. (2023) and specify the corresponding parameters and constants. Table provides a side-by-side comparison of the notations and constants for easy reference.
Table 4: Comparison of notations and constants in Zhang et al. 2023 and our setting.
Description
Ours
Zhang et al.
2023
Parameter
& = (0e; nc)
W/ = 02
Observation sample
0,
Y
Algorithm operator
- Or) + Et
Fa.
(wr, Y,)
Mean-path operator
id aae
f
Projection operator
r
Update rule (
Č1+1 II( ang(Eri O())
W1+1
I(we ar (Fw,, (Fw, Yi) w.))
Steady distribution
Me
dg
Assumption 3.4
Zero/fixed point
0: (A(A()) 0
Fo(w)) wg
Assumption
Algorithm
Assumption 3.1
Assumption
Assumption
Assumption 3.2 and Lemma 3.3
contractivity of Bellman and transition operators
Assumption
Assumption 3.4
Assumption
Lemma
Assumption 3.5 (i)
Assumption
Algorithm
Assumption 3.5 (ii)
Assumption
Lemma
Assumption 3.5 (iii)
Assumption
Lemma
Assumption 3.5 (iv)
Assumption
Lemma
Assumption 3.5 (vi)
Assumption
Assumption and Lemma
Assumption 3.5 (vii)
Assumption
D > w-
Assumption 3.6
Assumption
O₁ 4/(1 + +ll)
Assumption 3.7
Constant
VI azd
Ka
Constant
n LF
Constant
max (1 + 7, F) + 0
Constant
L'
Constant
R+ F
U F
Constant
oL(1 + 7) mmx (1,, d2]
L'
Constant
R+F + oL(1+7]
UH
I+7
Constant
Unn
Constant
(R + F)
Un
Constant
30
Li
Constant
Lp
Lp
For general MFGs, can always scale the reward function and state space to meet the sup norm condition Assumption 5
However, it is unclear whether the MFF after scaling corresponds original MFE.
41

---

Published as a conference paper at ICLR 2025
Zhang al. 2023 Assumption 3.1) is satisfied by action selection rule in Algorithm
Pr (0 = 0 (s, a, ",,s'''')) Pr ((9++1, a1+1, S142, a(+2) (s, a, a,,
=P (5t+1 0141,
Te.4 1e441(6 (a' |s))
= (0++1,0).
That is, the transition depends on the current parameter.
Zhang et al.
2023
Assumption 3.2) is directly satisfied by Assumption 3
Zhang et al. (2023 Assumption 3.4 (i)) satisfied by the contraction property of the Bellman and
transition operators. To ease representation, we define mapping A that maps any parameter to the zero point of 8g. Recall that
(c(5") (Ge + Gb) (Fe 1 vE).
we know that Gg and Gy are positive definite. Thus, we have By previous analysis (e.g., Lemma
A() (Ge @ G+))
(pe + whe.
indicating the existence and uniqueness the zero point Øc-
Zhang al. 2023) Assumption 3.4 (ii)) be verified by modifying the proof of Lemma
2 For given parameter ( E E, we denote A(C) = { = (0: 7), A = E E. AØ = and Ar = 1]
for any { (0; n) E. Then, similar the proof of Lemma 9 have
(An, (n)) - - Amin |G
(23)
(A0, (c())) S - 7) (G
Note that here the coupling between 9 and 17 is gone as we fix the parameter Ç that controls the dynamics, resulting in stationary setting. Let
{ (1-7))minn (G Amin (G.))
inf min CEE
Note that determines Ge through the transition kernel. Since the of transition kernels compact state space is compact, the infimum achieved. And by definition, we have 0 < w < w S 1/2. By Lemma
7 we have
[E) = (E) (c(E)) & max f1 +1+ | Ell-
(24)
Combining (33 and 24 gives
||s ())() E|1² <1 - 2a (An, de (1)) 2a: (A0.5.(00) + 1 (c
< A 20 | A 2 a² max {1 7, 2 ||a||2
=(1 - 2000 + a² max {1 7 F) =
Therefore, let == W/ w/ (max
+ y, 2 When a S a, the above inequality gives a pseudo- Assumption 3.4 (ii)):
contraction (Zhang al. 2023
||$ - -ag(()))) - El| < vI am E
In Zhang et al. 2023 Assumption 3.5), (i) is satisfied by Lemma 7 (ii) is satisfied by our update rule,
because given an observation O, g(E: O) is independent of the parameter controlling the dynamics.
(iii) is satisfied by Lemma 3 (iv) is satisfied by Lemma 7
pe, (E) øe. (E) SoL ((1 (1+1))1011 + F) / d1 dellls1 E2ll + L, Lr n2ll
<aI(( + 7) max / d2)
[1811+
R F
Lr
115:
-Eal--
1 1+7
oL(1 +
42

---

Published as a conference paper at ICLR 2025
Before verifying Zhang al. (2023
Assumption 3.5 (v) and (vi)), first show the following norm
bound:
[G: @ Go)
=0 =0
min (Gg ① Gv)
(25)
min (sym (Gg ① Gv))
(26)
min {
{Amin (sym (G$) Amin (G+)}
(27)
-min {wmin (GE) Amin (G+)) -1
<min {11 7) Amin
(G Amin (Gw)}
(28)
Si ///
(29)
where (25) is the spectral norm equality; (26) uses the Fan can-Hoffman inequality (Bhatia 2013) and the fact that (ym + Gw) is positive definite, where sym(A) (A + A²" )2: (2 uses the fact
that A(A @ B) X(A) A(B), where X(A) is the set of eigenvalues A: (88 is by and 29
is by the definition of w.
Therefore, we have
[|A(S)) - A(E2)1 S (Ge, @ Gy)
@ WE,) (0e,
-G @ Gv) (ōes @ WEa)
(GE, Gv)) Gw) -1 ( @ ve.)) - (Ōe, + vEEa
U,
+ (Ge, - -GGe, + Gw)) Gwv) 11,, 1l @ weall.
U/
For U1, by Lemma 6 and 29 we have
U1 S w-
maL F) F)+ L.)) 115 E211/2.
For U2 we have
U2 < (Ge, Gb)) Gb)
|(Ge, @ G+)) - (Ge, @ G+) [Ge, Gb)
| $ Deall
op
sw 7) max d2 R F) /
where the last inequality uses
(29) and Lemma 6 Plugging Un and U, back gives
[|A(E) A((2) L. Ezll.
where
T 10
w a max d2) (R + F) + (T,+t/22)) Ttr./).
(30)
and thus Zhang et (2023
Assumption 3.5 (v)) is satisfied.
By the definition of A and (29). (Zhang et al. 2023
Assumption 3.5 (vi)) is satisfied:
sup $EE
[A(E]] S (R+
Zhang al. 2023
Assumption 3.5 (vii)) is satisfied by Assumption I and Lemma
Let D > max { ( //, [[ /Zhng et al.
2023
Assumption 3.6) is satisfied.
Finally, let a, 4/(1 + wt). Zhang al.
2023
Assumption 3.7) is satisfied. Note that we do not Assumption 3.7) because we use asymptotic notations.
need the parameter lo in Zhang et al. (2023
Proof of Theorem By Zhang et al.
2003
Corollary 3.10), we have
L2 D2
log T
||Er A(G)))] =
2
T
43

---

Published as a conference paper at ICLR 2025
By Assumption get
Lu S v (w/4 w/4) S 1/2.
Therefore, A is contraction mapping. Suppose there exists another MFE &ux. We have
I|5. - E-.ll = ||A(E)) A(E..)) < Tu 11. - E..Il S 1/2115. Eaa which implies &. Ex.. We also get
E [llET - E+ll SE []| Er + - Ex
=E Er + A(E
S (1 + - -Eall,
which gives
[DLT, + w [(R F))
log T
E Ellee - -1. S
E [llEr A(Ex)]l
L
VT
where L = L mmx(d1xx
I.2 CONVERGENCE REGION
The radius of the convergence region in Theorem needs to be further inspected to make the bound informative. We compare it with two constants: the projection radius D and the magnitude of the optimal policy parameter |[xl]--
A desirable property of the convergence region is that it can be much smaller than the projection radius D. This property is not enjoyed by some algorithms with linear function approximation. For instance, linear Q-learning with asymptotically visits every part of the projection ball. To achieve this property, we need
L, + ū
L(R F)
S1,
1
which is equivalent to
I, S T² and R + $ 3
(31)
Recall from Assumption that
L, S w and R + S w
Therefore, to make the convergence region radius smaller than the projection radius, we need to further scale down the bounds on L,, R, and F by w.
We now discuss the condition for the convergence region radius to be smaller than ||E= ensuring that the algorithm finds better parameter than & = 0. Note that the only requirement on the projection radius is that it should be no smaller than the magnitude of the optimal policy parameter 6_*, i.c., D ||@||. We first consider the where have good estimate of 6. Let D ||[||- Then, one can see that (31) ensures that the convergence region radius is smaller than ||
Next, consider a general D. Denote e (I, L(R F)u-11) 1/m² /22 which is independent of D. Theorem implies that, in expectation, &r will be bounded by [Er S || +D. cD. Thus, the projection will be inactive if D 2 ||E.|| cD. Let D' x (1 c). We know that running the algorithm with projection radius D or D' is equivalent for large T, as the projection will be inactive in both cases. Consequently, we only need ||g.|| be smaller than the convergence region radius D = D' = (1 - c), which is equivalent to
| 1 --c c c 1eal = L, S w²/ and R S w
Therefore, we conclude that the convergence region in Theorem is especially informative holds.
31
44

---

Published as a conference paper at ICLR 2025
J APPROXIMATION ERROR ANALYSIS
This section aims to characterize the approximation error of SemiSGD for general (non-linear) MFGs. Recall that SemiSGD converges to the projected MFE (Appendix F Let &o (0s; n,) be the convergence point of SemiSGD with PA-LFA. Let (g+, pa) be the actual MFE. The approximation error defined as
cq = 11 - (é, (b) co
Cp = 1| - (16 llv..
(32)
Additionally, we define the inherent error of the chosen basis as
E 11.. 1o
< IPp I.
The next two lemmas bound the approximation errors in correlated. Theorem is direct corollary of Lemmas 13 and assumption. Lemma 13 (Value function approximation error).
separately, showing how they are under the small Lipschitz constants
Eq $ (7+ 7o 2oRLE
1-7 cv + Lr + 70 RRRLp
(1 (1-7)vda
Eu + E
Proof. We first have the decomposition:
" S (é, 0o) II T0% bl + ||T 2o g0l1o0>
(33)
where a is the orthogonal projection operator onto the linear span of basis & w.r.t. the inner product induced by the Eo. Since &o projected MFE, by Definition we get
(v,, 0o) - a || ||l To (b, 0o) - l S To (6. 0o) - -2
(34)
where To Te. and the inequality uses the fact that T. is non-expansive operator. Since q. is an equilibrium value function, we have
[|To (0, 0o) q- lo T| (ò, 0o) T-g. 1o0 S T ((6, 0.) q-) 1lo + +1[(To (T))--)))-lla... (35)
For the first term in (35). the Bellman operator's definition gives
[| (10,0o) g-)l 7 (1(6) y- lla 76g-
(36)
Similar to the Lipschitzness of TD operators (Lemma(6), the second term follows:
(35) can be bounded as
[(To - (s)
= | (vi nol) - (1,,,,,,))) [
ISXA rea(d' (u (s,a,,')))) ul(s,,, ds ds'da'
LLill (b) - u.ll + 111001bo1lut - u
(37)
Lp cp + Lxtg) Vol
SL,eg + lll
(38)
where 37 uses Assumption
and 38) uses Corollary
Since q. is the best response to px, we have
R
||o
E Beg .
r'r(s, ac)
R
(39)
1 1-
t=
1=0
Plugging back into 38 gives
39
YoR ( (L.p Top
[[T
T.) S Lycg
(L
Cp + Lot(g)
(40)
1 1-7 VTTz
Plugging 36 and 40) back into (35) gives
( JoRLs
+ Lor RoRLp
To (b, 0.) - q. 10ll S
1
(1 7)
En
(41)
Plugging 41 back into 34 and then 33 gives the desired result.
45

---

Published as a conference paper at ICLR 2025
Lemma 14 (Population measure approximation enror).
Proof. For uniformly ergodic MDPs, p == -llm P. exists, which maps any distribution to jt.- The uniform ergodicity equivalent to strong ergodicity (Meyn & Tweedie 2012), which implies following relation about the geometric convergence rate [Isacsson & Luecke
1978
p(P. -
where p(P) returns the spectral radius P. Without loss of generality, we assume p > p(P. - -P:)) Then, by Isaacson & Luecke (1978 Corollary 3.9), for any p > p(P. ) there exists & E N such that
|| p I S p",
where the norm is the operator norm induced by the total variation norm. Now apply the decomposition:
p S (10, no) - P (1,, nod rV +
|p (v) no) Ma lly.
(42)
E1
E2
Since E is projected MFE, by Definition we have
E = 1==(((1g (1I.)))) - P.t (2/, no)
TV $ (1) -
- p
A further decomposition gives
E S P.P.P. (II k - -p--1) + IL (Po - PP) + (II,- - Id) p
Tv
Note that both II and P are non-expansive operators. By the sub-multiplicaiivtyy of operator norms, we have
E E PI) k-1 - p.-11 11 TV
+
- + -
-
(43)
Fa
We denote cg = lP, - Prllllvv eg is the inherent approximation error induced by v. For Es. by definition, we have
Es sup INITTVSI 1/500 /SA
(W, (a -P-l u.) (als) u(s)dsdaa
TV
Lp
Sletg +
Vdz tu-
Plugging the above bound of Eg back into
443 gives the following recursion:
Lp
E < (Ig
ph
+ -aagg +
" +
Vdz²
Lp + Ex)
<k Lnngq +
(44)
VTzz
For Ez, since n. is the equilibrium population measure, and poo maps any distribution to Pa,, we have
Eg ph (v, no) ue + p. -M- -M-lly
|/ (1,, no) - -P:i + p: (W)TTo) - p. 1.
=I((Ph P (11b, - -.)
< p x IT Sp
< Cp.
(45)
Plugging and (45) back into (42 gives
kTp
Cp $ 0²
cp + KL + keg-
Vdz
Furthermore, if [P. - P.00/yy E p. for example, P. corresponds to a reversible Markov chain, then k k=1- 1.
46

---

Published as a conference paper at ICLR 2025
K MEAN FIELD GAMES WITH FINITE STATE-ACTION SPACE
Recall that SemiSGD with PA-LFA (Algorithm D reduces to tabular SemiSGD (Algorithm) ! for finite state-action spaces, when the feature map and measure map are chosen as
((s, a) = ((,a) E ER
AI,
v(x) = e E A
Then, Q 0 E RISIIA and M 1y E A s are the parameters themselves.
K.1 IMPLICIT REGULARIZATION
We first show that tabular SemiSGD does not need the projection step for regularizing the parameters (see (6) That is, tabular SemiSGD enjoys implicit regularization. For [| we first have ||)>(" s
Recall the stochastic update rule of M:
M++1 Mr a (Mc Cec+1) =1 (1- a) + a65411
Suppose Mr E A and the step-size is smaller than one. Then M++1 O. Furthermore, we have
|M = Σ (la (s) = (1-a) Σ
Mr(s++ Σ C = (55)=((-a)+++))))) (1-a)+a= 1,
SES
SES
sES
indicating that M1+1 E |s|, without any projection.
For [|]]| notice that the true action-value function induced by any policy is bounded by ||//|100 S 2t=07 R R/(1 - 7) =: Dx Suppose current estimated value function satisfies that |Q S
D Doo. then we have
Qu41 (s, a)l = (sx, az) + (r (8141, - Qi(s;,
=I(1 a)Q at) + a (8441, 0411) + and
S (1 Do + +ay Dx + aR
R
(1 a + ar)
+ aaR
1
R Dx
Therefore, if the bound holds for the initial estimated value function, it holds for all sequential estimated value functions. Then, the following & norm bound holds for all value functions:
VSI R D:
Consequently,
H (1++7)
A + 1)
(VISIARR
+2=0
(17
1 1-y
K.2 CONVERGENCE RATE
We now figure out the scale of the descent parameter w for finite MFGs. First, for tabular SemiSGD,
Ge = /. According to Lemma 9 Amin (Gp) = 1. Second, G. = diag(ul (s, a)), where μ. is the steady state-action distribution induced by k.. Thus, Amin (G.) min,, (s, a) | We define À= min,,a μ1 a) > 0, the probability of visiting the least probable state-action pair in the MFE. Then, we have
1 min [1in((1= 7)mmiu (G Aminn (G+))
1 } >)
2
We ready state the sample complexity of tabular SemiSGI.
47

---

Published as a conference paper at ICLR 2025
Corollary 4. With either constant step size at ag = =looTi((UT) linearty decaying step size Ot 11(w(1 + t)), there exists convex combination Er of the iterates {Ee)t=1 such that
ET E. =
| A2 7)
where Ô suppresses Jogarithmic
Notably, tabular SemiSGD has the same sample complexity as TD Learning methods (Bhandari et al. 2018 Zou et al. 2019).
48


Reviews:
[{"review_id": "pteuaBmYsz", "reviewer": "Reviewer_bQAJ", "summary": "This paper primarily concentrates on the development of a stochastic gradient method for learning in mean-field games.\nThe proposed algorithm significantly reduces the computational cost associated with calculating the population distribution.\nMoreover, the author demonstrates that under certain standard assumptions, the proposed algorithm converges to a stationary point.\nAdditionally, the algorithm's performance is validated experimentally in various mean-field games.", "questions": "My main concerns and questions are outlined in Weaknesses.\nAdditionally, I have the following question:\n* I am not sure how Assumption 5 is relatively weaker than Assumption 4. Could you provide a more intuitive explanation of Assumption 5?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The problem is well-motivated. Eliminating the forward-backward process of learning algorithms for mean-field games is significantly important.\n* The proposed algorithm has a strong convergence guarantee with a rate.", "weaknesses": "My primary concern is that the definition of the mean-field equilibrium in this study differs from that in existing studies.\nSpecifically, this study considers the Bellman operator, as opposed to the commonly used Bellman optimality operator.\nHence, I believe that there is no guarantee for the agent to maximize the expected cumulative discounted reward in the mean field equilibria.\nIn the context of learning in multi-agent systems, it seems more natural to consider maximizing the expected cumulative discounted reward.\nConsequently, I'm wondering why the current definition of equilibrium was considered in this study.\nIs it possible to extend the provided theoretical results to the reward-maximizing setting?\nIf not, I don't think we can fairly compare this study with existing studies on mean-field games.\n\nAdditionally, I believe that a more detailed explanation of the numerical experiments is necessary.\nFor example, I'm curious why exploitability was reported for the flocking game, despite the fact that reward maximization is not the main focus of this study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M3akGc8sor", "reviewer": "Reviewer_VqQ9", "summary": "In this paper, a numerical method for mean field games is proposed. Mean field games games approximate Nash equilibria for games with many players. Here, the proposed method relies on stochastic semi-gradient updates. Theoretical convergence is proved and numerical illustrations are also given.", "questions": "Q1: Theorem 2: Please provide an example satisfying the assumptions of this theorem.\n\nQ2: Section 7: Can you please explain what is FPI+MD? Is it the same as the online mirror descent of (Perolat et al., 2021)? If not, please compare with this algorithm, which is known to empirically converge much faster than fictitious play-type iterations.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is relatively clear and the algorithm is new, to the best of my knowledge. The convergence analysis includes sample complexity. The experiments cover different examples and contain a few baselines.", "weaknesses": "I understand that empirical convergence is observed beyond the assumptions, but still: it is not clear to me how to check these assumptions in practice.\nIn the numerical examples, the baselines could be explained more clearly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G5Zqce4UIp", "reviewer": "Reviewer_b6VH", "summary": "The manuscript goes beyond existing fixed-point iteration (FPI) methods for solving mean field games, by treating the mean field and agent policy jointly instead of performing forward and backward updates. Here, FPI-type methods are understood as those computing the full forward and backward equations for mean field and optimal policies. The advantage is allowing asynchronous updates to both, which can lead to improved results. An analysis of the resulting semi-gradient descent method is performed under linear models and varying sets of assumptions. Empirically, the designed algorithms are further demonstrated on a variety of problems.", "questions": "- Uniqueness of solutions seems to not be required. How it is possible that we obtain convergence in the presence of non-unique MFE? Does the theory imply convergence to multiple MFE, or is uniqueness implicitly assumed?\n- What is the reasoning behind replacing $M_*$ (the non-unique? unknown MFE) by bootstrap estimates under the current policy (before Eq. (3))? Why can the current policy produce estimates for the mean field $M_*$ of the MFE?\n- The methodology does not directly optimize exploitability, what is the difficulty in instead using \"true\" gradients on the unified parameters to minimize exploitability?\n- Can you extend similar techniques to non-time-stationary MFGs?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and relatively clear despite the subject matter. \n- The analysis is novel, interesting and extensive, e.g., the combination of linear approximations with MFGs and producing finite-time error bounds, or the convergence results without (directly) assuming contractivity or monotonicity.\n- Empirically, the approach appears to be able to outperform existing approaches in some of the demonstrated problems in terms of exploitability. Further, the method is practical, as it is applicable in an online manner to unknown models. \n- The introduction of synchronous updates as opposed to forward-backward computations seems somewhat significant to the study of MFG learning algorithms, as it allows for improved sample complexity and better empirical results.", "weaknesses": "- The approach seems to be limited to stationary mean field games, i.e. ones with time-stationary mean fields. This does not match with the compared / referenced literature, of which most are for non-stationary cases. \n- For the theoretical results, there remain limits in terms of significance, as also discussed by the authors. The significance of theoretical results is limited due to the requirement of strong assumptions such as linear models and regularized solutions.\n- Some minor issues (incomplete / TeX errors) in references.\n- Some points remained unclear to me, see questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2a3zlyDdzy", "reviewer": "Reviewer_B4eq", "summary": "This paper studies learning equilibrium policy in mean-field game. The authors propose semiSGD, a SGD style online algorithm, where they treat the policy and population as a unified parameter. For linear MFGs, under small Lipschitz factor case, they establish convergence analysis. Besides, when the Lipschitz factor of the problem is relative large, they show the algorithm converges to the neighborhood of Nash, whose radius scales with the Lipschitz factors.", "questions": "1. In Assumption 5, $w$ is introduced to denote the upper bound of $\\bar{w}$. However, it does not appears in Theorem 2. So what's the reason to mention such an upper bound?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "It seems interesting to me the idea that considers the policy and population parameters as a unified parameter to optimize.\n\nThe assumptions are clearly stated, and some explanations are provided. \n\nNumerical experiments are provided.\n\nThe comparison in Table 2 provides a good summary.", "weaknesses": "1. **About assumptions**: I think the authors should provide some justification about why it is reasonable to consider Assumption 2. In the more standard MFG setting, the equilibrium policy is defined to be the policy that no agent can deviate and increase its value, which correspond to the setting $\\Gamma_\\pi(Q)(\\cdot|s) := \\arg\\max_a Q(s,a)$. However, Assumption 2 can not cover this setting with finite $L_\\pi$, because of the discountinuity of the argmax operator.\n\n    As implied by Assumption 2, the paper seems to consider a \"smooth\" version of standard Nash equilibrium. It is unclear that why this objective is of interests to study, and also what's the relationship between it and the standard Nash equilibrium.\n\n2. **Comparison with Assumptions in previous work**: this paper consider contraction style assumptions to establish the convergence. Although in remark 2, the authors provide some discussion to justify the assumptions, it is still unclear to me how they compare with previous works. For example, does the contractivity assumption in [1] can be recovered as a special case by choosing some specific parameters in Assumption 2 and 4? Or maybe comparing with [2], which ensures contractivity by introducing the regularization, would Assumption 2 or 4 be satisfied by introducing large enough regularization?\n\n3. **When Theorem 2 is meaningful?** Theorem 2 suggests the convergence with bounded bias. I think it is necessary to have some discussion about the magnitude of the bias term comparing with another algorithm randomly compute $\\xi_T$. For instance, can you provide some examples when the bias term can be (much) lower than $\\|\\xi^*\\|$, which suggests the algorithm is better than a random guess by directly assigning $\\xi_T = 0$.\n\n    It is also unclear how large $\\bar{w}$ is. Given that $\\bar{w}$ is a problem-dependent constant, can you explain when $\\bar{w}$ can be large or small? That would be helpful to understand when Theorem 2 is meaningful and when it is vacuous.\n\n[1] Guo et al., Learning mean-field games.\n\n[2] Yardim et al., Policy mirror ascent for efficient and independent learning in mean field games", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)