Finite-Sample Convergence Bounds for Trust Region Policy Optimization in Mean Field Games
Authors: Antonio Ocello
Daniil Tiapkin
Lorenzo Mancini
Mathieu Lauriere
Eric Moulines
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement learning
mean-field games
trust region proximal optimization
Nash equilibrium
finite sample complexity
Primary area: reinforcement_learning->multiagent
TL;DR: Finite sample complexity analysis of the novel MF-TRPO algorithm for ergodic Mean Field Games in finite state-action spaces

Abstract: We introduce Mean Field Trust Region Policy Optimization (MF-TRPO), a novel algorithm designed to compute approximate Nash equilibria for ergodic Mean Field Games (MFGs) in finite state-action spaces. Building on the well-established performance of TRPO in the reinforcement learning (RL) setting, we extend its methodology to the MFG framework, leveraging its stability and robustness in policy optimization. Under standard assumptions in the MFG literature, we provide a rigorous analysis of MF-TRPO, establishing theoretical guarantees on its convergence. Our results cover both the exact formulation of the algorithm and its sample-based counterpart, where we derive high-probability guarantees and finite sample complexity. This work advances MFG optimization by bridging RL techniques with mean-field decision-making, offering a theoretically grounded approach to solving complex multi-agent problems.

Finite-Sample Convergence Bounds for Trust Region Policy Optimization in Mean-Field Games
Antonio Ocello! Daniil Tiapkin 12
Lorenzo Mancini! Mathieu Laurière Eric Moulines
Abstract
A powerful framework to model these adaptive decision agents is Multi-Agent Reinforcement Learning (MARL), which enables agents to learn optimal strategies through interaction with both the environment and other agents (see, e.g., Zhang et al., 2021; Gronauer & Diepold, 2022). How- ever, MARL faces two major challenges: scalability and non-stationariiy. As the number of agents increases, the joint state-action space grows exponentially, making learn- ing computationally prohibitive. Additionally, because all agents are simultaneously updating their policies, the en- vironment becomes non-stationary from the perspective of each individual agent, severely hindering convergence and stability. To address these issues, many techniques have been considered, like Centralized Training with Decentral- ized Execution (CTDE) (Foerster et al., 2018) and attention approaches (Iqbal & Sha, 2019). While these methods im- prove stability and learning efficiency, it comes at signifi- cant computational cost, limiting its scalability in large-scale systems.
We introduce Mean-Field Trust Region Policy Optimization (MF-TRPO), novel algorithm de- signed to compute approximate Nash equilib- ria for ergodic Mean-Field Games (MFG) in fi- nite state-action spaces. Building on the well- established performance TRPO in the reinforce- ment learning (RI.) setting, we extend its method- ology to the MFG framework, leveraging its stabil- ity and robustness in policy optimization. Under standard assumptions in the MFG literature, we provide a rigorous analysis of MF-TRPO, estab- lishing theoretical guarantees on its convergence. Our results cover both the exact formulation of the algorithm and its sample-based counterpart, where derive tigh-probability guarantees and finite sample complexity. This work advances MFG optimization by bridging RL techniques with mean-field decision decision-making, offering a theo- retically grounded approach to solving complex multi-agent problems.
Under the assumptions of homogeneity and anonymity, com- plex multi-agent games can be effectively approximated us- ing Mean-Field Games (MFG). MFG provide asymptotic approximation of exchangeable particle systems the num- ber of agents grows. Originally introduced by Lasry & Lions (2006a;b; 2007) and Huang et al. (2003; 2005; 2006a;b), MFG replace direct agent-to-agent interactions with a rep- resentative agent interacting with the statistical distribution of the population. Due to their analytical tractability and broad applicability, MFG have been widely adopted across various domains, including economic modeling (Bassière et al., 2024), finance (Lavigne & Tankov, 2023; Carmona et al., 2015), public health dynamics (Doncel et al., 2022), and energy storage (Alasseur et al., 2020).
1. Introduction
In an increasingly interconnected world, autonomous sys- tems capable of adaptive decision-making have become indispensable. Their range of applications is vast and contin- uously expanding, spanning from autonomous driving (see, e.g., Shalev-Shware et al., 2016) to energy market con- trol (Samvelyan et al., 2019), and from traffic light opti- mization (Wiering et al., 2000) to advanced robotic sys- tems (Matignon et al., 2007; Kober et al., 2013).
ICMAP, CNRS, Acolc polytechnique, Institut Polytechnique de Paris, 91020 Palaiseau, France Uniieersité Paris-Saclay, CNRS, LMO, 91405, Orsay, France 'Shanghai Frontiers Science Center of Artificial Intelligence and Deep Learning at NYU Shanghai and NYU-ECNU Institute of Mathematical Sciences. 567 West Yangsi Road, Pudong New District, Shanghai. China 200124 MMohamed bin Zayed University Artificial Intelligence, UAE Correspon- dence to: Antonio Ocello <antonio.oom wceliioocccoooee polytechnique.edu>
In particular, Mean- Reinforcement Learning (MFRL) arises as the scaling limit of many MARL problems, posi- tioning itself at the intersection of MFG and Reinforcement Learning (RL). In this setting, RL techniques are employed to solve equilibrium problems in large-scale multi-agent sys- tems. At the core of this framework, each agent optimizes its objective while treating the mean-field distribution as fixed. This structure closely resembles CTDE in the MARL setting, but its computational cost is significantly reduced due to the mean-field approximation. In turn, the distribu-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Finite-Sample Convergence Bounds for MF-TRPO
tion evolves dynamically based on the collective behavior of all agents. This formulation extends the classical notion of Nash equilibrium to the Mean-Field Nash Equilibrium (MFNE), where equilibrium emerges from the interaction between individual decision-making and population-wide updates.
MF-TRPO, with finite-sample complexity guar- antees under the v-paradigm, requiring at most 0(1/=)) environment interactions to reach an E-MFNE.
Numerical experiments validating the efficiency and effectiveness of our approach in representative MFRL settings.
MFNE provide an adequate approximation for large- scale multi-agent interactions, achieving an O(1/VN)- approximate Nash equilibrium in the corresponding N- player game (Cardaliaguet et al., 2019; Fischer & Silva, 2021; Flandoli et al., 2022). This approximation drastically reduces the complexity of analyzing strategic interactions in large populations, establishing MFG as a scalable and com- putationally efficient framework for real-world applications.
2. Framework
We use the discounted formulation as an approximation to the ergodic setting, a standard approach the literature (see, e.g., Laurière et al., 2022). This methodology allows us to build on the well-established theoretical framework of discounted RL while capturing the long-term behavior of the ergodic formulation in a stepwise fashion. In partic- ular, we adopt the Mcan-Field Markov Decision Process (MF-MDP) framework, a natural extension of the infinite- horizon discounted MDP commonly studied in RL (Sutton & Barto, 2018a). This adaptation preserves the computa- tional tractability and convergence properties of the dis- counted problem while approximating the stationary dynam- ies of the ergodic setting. The MF-MDP framework thus serves as a bridge between classical RL and MFG models and provides a structured approach to policy optimization that is valid for both finite horizons and stationary regimes. A detailed discussion of this approach and its theoretical foundations can be found the Appendix B.
Related works. Recent work in MFG has explored the use of proximal methods due to their stability and empir- ical performance. Notably, Pérolat et al. (2022); Perrin al. (2022) analyze Online Mirror Descent (OMD) from model-specific perspective, while Yardim et al. (2023) extend this direction with model-free approach. However, their analysis does not address population updates, operat- ing in a restricted no-manipulation regime. These works have demonstrated the effectiveness of proximal methods in MFG, which is consistent with our research direction.
We extend this line of research by establishing finite-sample complexity guarantees providing rigorous theoretical framework that ensures provable efficiency in solving MFG. Moreover, we explicitly incorporates the role of monotonic- ity in stabilizing population dynamics, key aspect of the ergodic structure in MFG, and relax overly restrictive as- sumptions- such as uniformly munded-awwyy-foon from- policies or absolute continuity with respect the uniform distribution. With more flexible framework, we get refined learning guarantees under weaker assumptions, achieving an ((1/L) L) convergence rate in the optimization problem with improved sample efficiency, thus broadening the appli- cability of these methods. For an additional discussion on related work, we refer to Appendix A.
Notations. For finite set X, let P(X) denote the set of probability distributions over X. A finite MF-MDP is tuple (S ,r,,)) where S is a finite state space, A is finite action space, P: S x A X P(S) + P(S) is the transition function, r: S x A x P(S) + R is the reward function, 7 E [0, 1) is the discount factor. Since we consider probability distributions over finite state space of size [S], they can be identified as vectors in || thus, we define the inner product (,, +) and the Euclidean norm |1-112 accordingly.
We assume that is continuous, thus bounded, and denote by ||r |l its upper bound, i.e., r(s, a, pu) E [0, ||r |olll for (s, a, μu) E S x A x P(S). Given a policy π: S + P(A) and a population profile μ E P(S), we define the transition operator P as the transition matrix induced by the proba- bility kernel, where actions are sampled as a T(s) under the mean-field parameter p. i.e.,
Contributions. We propose Exact ME-TRPO and Sample-Based MF-TRPO, trust-region-based algo- rithms for computing approximate MENE the MFRL setting. Our method combines the structure of ergodic MFG with the stability of trust-region optimization to enable theoretically grounded learning in multi-agent environments. Our key contributions are:
(x() = = (als)) (s))s,,,,) for 8, ES,
aEd
1. Theoretical analysis of Exact MF-TRPO with a bound on the exploitability of the learned policies, quantifying the achieved MFNN after K iterations.
(PP Σ ((s)) ()
for
S0ES
2. A sasple-based
variant,
Sample-Bar Based
Denote >T, the stationary distribution of the Markov chain
2

---

Finite-Sample Convergence Bounds for MF-TRPO
Pa. Let II to be set the policies, i.e., the of fune- tions from S to P(A). For E S, and n, n' E II, the Kullback-eeibler (KL) divergence between the two distribu- tions <--ss) and x (-1s) is defined as ([]((()))][(((((({) = EnEA T [ [8) (a) (a|[s) if x is absolutely con- (-)))(())]
Define d. (resp. dz and - the occupation measure of the process (st)e induced by this policy, under the popula- tion distribution μ and initial distribution (resp. 6, and p). i.e..
tinuous to n².
= oc otherwise. We use the notation (-) to hide polylogarithmic factors in the asymptotic complexity.
df (1
Σ /P az) (8,
(5)
with so E. at ~ (T))) and s P (1( 0e, n)), and The its spatial marginal, i.e.
Problem formulation. As in Laurière et al. (2022), the discounted stationary problem within mean-field interac- tion setting is designed approximate the N-player game in the ergodic regime, as 7 - 1. In this setting. repre- sentative agent in the mean-field approximation seeks to maximize the expected discounted sum of rewards while interacting with the population distribution under a policy æ. The objective function is given by
(e((3)) = Σ dg
(6)
acA
Interactions with the environment. In the RL literature, various paradigms have been proposed to structure the in- teraction between an agent and its environment, influencing how data is collected and utilized for policy updates. In our setting, two fundamental actions can be performed: reset and step. The reset action initializes the environment by sampling a new state from the distribution v, effectively allowing the agent to restart from fresh initial condition. The step action, on the other hand, takes chosen action and the mean-field distribution profile μt, and progresses the environment based on the current state s. Specifically, it samples the next state from the transition kernel P (-|ss, a, (4) and updates the environment accordingly. This interaction model aligns with previous works (Kakade, 2003; Shani et al., 2020) and provides an intermediate assumption in the spectrum of data access models in RL. It is therefore weaker than assuming full access to the true model or generative model, where arbitrary state-action pairs can be queried, but stronger than the setting where no restarts are allowed, restricting exploration to trajectories induced by the current policy. This ensures reliable state exploration and promotes stable convergence.
JMFG (T, (,,
(2)
>' [r(ss, ar. 11) + nn nog (F(a [s))]
Given an initial state 80 ~ E, actions are sampled at each time step as a₂ ~ ([- st). with state transitions governed by the kernel P, i.e., S1+1 P( St, ae. (4). We consider regulai--e variant of the classical MFG problem, where 17 denotes the entropy regularization parameter.
As MFG are an Nt)p///)aapprpiimaaaii
of the N N-player game, it is natural to introduce an additional regularization term. If this extra bias remains within the order of the ex- isting approximation error, model fidelity is thus preserved. Regularization enhances solution stability, which is partic- ularly beneficial given the inherent nonlinearity of MFG optimization. This is especially advantageous in RL set- tings, where small perturbations in the value function or policy updates can otherwise lead to erratic behavior.
The value function defined as
Nash Equilibrium. Our work aims to compute a MFNE, A Nash equilibrium (NE), fundamental concept in game theory, represents a stable state in which no player can improve her payoff by unilaterally changing her strategy, i.e. each player reacts optimally to the strategies of the others.
MFG (u,E) max MFG (), well
(3)
With a slight abuse of notation, we use VMFG (n) and JMFG /4)) to denote VMF (m, 5,) for E S (resp. VM (H, H)) and MFG (I, H)).
s) (resp.
In the MFG framework, as the number of agents approaches infinity, this concept extends to a situation in which each agent optimally adapts its strategy to the behavior of the collective population. This leads to a mean-field fixed- point condition in which individual decisions shape and are shaped by the evolving population distribution. This formu- lation makes MFG a powerful tool for analyzing large-scale strategic interactions.
Furthermore, let QJ denote the regularized Q-funcioon, de- fined as
())))))
=r(s,a,1))> P(s'ss,a,,)) MMG (M, s'ES
We denote nn the optimal policy of optimization prob-
lem VFFG (H), which is unique in the entropy-regularize RL (see, e.g. Haarnoja et al., 2017; Geist et al., 2019).
Definition 2.1 (MFNE). A pair (T.. is said to be a MFNE if it satisfies the following two conditions:
3

---

Fimite-Sample Convergence Bounds for MF-TRPO
1. (Optimality under the population dynamics) The policy n, is an optimal solution to (3), given the popu- lation evolution Mrx, L.C.
3. Assumptions
We outline the key assumptions that guarantee the well- posedness and stability of the MFG problem, providing a foundation for deriving finite-sample complexity bounds for the proposed algorithm.
JMF (Tn
(
max J MMG (T,) TEll
A-1. Let r (resp. P) be Lipschitz continuous with respect to n4, with Lipschitz constant L,j (resp. L,.), i.e, for 8, E S,
2. (Consistency of the population evolution) The popu- lation distribution fs- is fixed point of the mean-field evolution equation
E A, and n² P(S), we have
[r a, p) - r(s, a, n()l S L, |l - ll2 PP (ss P( d' n() & Lp || - / 4'1l2
14* = 14 P
In this definition, the first condition ensures that no indi- vidual agent can improve their long-term objective by uni- laterally deviating from the equilibrium policy T.. Given the equilibrium population distribution p.,, this optimality condition guarantees that the policy т,, remains the best possible strategy for each agent, thereby ensuring individual rationality.
Lipschitz continuity for the MDP parameters ensures that small perturbations in the state or action lead to propor- tionally small changes in the transition dynamics. This assumption is well established in the RL literature (Asadi et al., 2018; Le Lan et al., 2021) and it facilitates the deriva- tion of meaningful error bounds and convergence rates in policy optimization. From this, we establish Lipschitz con- tinuity of the optimal policies w.r.t. mean-field parameter as follows (ef. Corollary E.4).
The second condition enforces consistency in population dynamics: when all agents follow the equilibrium policy Te, the resulting population distribution remains stable over time. This fixed-point property ensures the system's 's long- term evolution does not deviate from the equilibrium state.
Proposition 3.1. Suppose Assumption I holds. Then, there exists constant Cx such that, for p. p¹ E P(S),
This notion of equilibrium, introduced by Nash (1950) and extended to the mean-field setting by Lasry & Lions (2006a;b; 2007); Huang et al. (2003; 2005; 2006a), is fun- damental game theory. In these works, the authors gen- eralize the results of Nash (1951), proving the existence of at least one NE using the Brouwer Fixed-Point Theorem. This non-constructive result holds under mild assumptions, such as the continuity of payoff functions and the compact- ness of strategy spaces, forming a cornerstone for analyzing strategic interactions. However, explicitly computing such equilibria remains challenging, particularly in the multi- player regime (Austrin et al., 2011).
sup [ S C Te lill--p" SES
where up is the optimal policy associated with the mean-field distribution p.
This result connects the structural properties of the MFG framework with the behavior of the associated optimal poli- cies, forming key theoretical foundation for the analysis of the proposed algorithms.
2-2. There exist an integer M 2 and a real number Cop.MFG < such that, for μs E P(S), we have
Exploitability. A key metric for evaluating the deviation from a NE is exploitability (Laurière et al., 2022). Formally, the mean-field setting, it defined as:
(u (w-w', ul, ul.
M - w/ -W(P77 M
Cop.MFG ll 1e'12"
(TT, 11) := max MFG x'ell
XTrY)) - JMG (T,, dr.pe dmaa)
This monotonicity condition of the mean-field update is employed in various forms throughout the MFG litera- ture (Angiuli et al., 2022; 2023; Yardim et al., 2023). This condition, originally introduced in the foundational works by Huang et al. (2003; 2005; 2006a;b), ensures that iterative updates to the population distribution progressively aligns the system with the NE.
This quantity measures the potential improvement an indi- vidual agent could achieve by deviating unilaterally from the learned policy æ, given as mean-field parameter the stationary distribution An,uu
This condition extends the classical contractivity condition, which corresponds to M = 1 (see, e.g., Guo et al., 2019). The condition might fail for M 1 but hold for some
Definition 2.2. A pair (p)) is said to be a MENEE,, if its exploitability is bounded by e, iee, (TTes S..

---

Finite-Sample Convergence Bounds for MF-TRPO
M > 1, reflecting the combined effect of the Lipschitz continuity of the regularized best response and the ergod- icity of the Markov reward process P A full in-depth discussion of this condition and its implications is provided in Appendix F.4. As the regularized best response admits a unique optimizer Tue the previous condition ensures the uniqueness of the fixed point of the associated operator, i.e.
Algorithm Exact TRPO(A)
1: Initialize: To is the uniform policy.
2: Input: L.
3: for l E [T]] do
JMF (Te,
-(1->pp)) ) 1m
5: Say. == fa
d 2 (s) > 0}
6:
for E Saze do
7:
for a E A do
p. P
8:
a, Quan (3, a) + a8, 14)
t7 E. P P(s' |s, a. J (me,
with μe, the unique fixed point of this operator. This implies that, in this setting, we obtain the uniqueness of the MFNE, corresponding to the pair (Tr.. H..).
9: end for
10: teti(als) + pol icyupaate Queni (a,
I1: end for
A-3. The MF-MDP (S, A,P,,, is unichain: for every fixed μ E P(S), every stationary policy ı induces a unique stationary distribution A over the state space, satisfying, for all s S, the following equation:
12:
end for
13: Output: TL.
(8)
P(s o' () I 8')) (m))) (e(xa)
Σ
used in Exact MF-TRPO is particularly well-suited for TRPO (see, e.g., Shani et al., 2020), as the proximal policy update fully exploits the entropy term, enabling a soft-max closed-form updates in terms of the Q-functions. This prop- erty enhances convergence by ensuring smoother and more stable policy iterations.
Moreover, there exist constants / E (0, and Creg > such that the following uniform mixing property holds for all &, u P(S) and 2 0:
| (P Amm TV
Although (3) is not a convex optimization problem, the adaptive nature of the regularization term allows us to use mirror descent techniques from convex analysis to establish strong convergence guarantees. In particular, we derive finite-sample complexity bounds showing that show that Exact MF- ME-TRPO converges rate of O(1LL).
S CECEP'
(9)
The unichain property eliminates ambiguities in the initial population distribution caused by multiple recurrent classes, which could otherwise complicate value function evalua- tion and policy improvement steps. As highlighted in Shani et al. (2020), optimal policies are defined only within the recurrent states of the Markov reward process at equilib- rium. Moreover, the ergodicity property naturally aligns with the regularization framework, as it promotes explo- ration within the Markov chain, leading to a more robust and stable optimization landscape.
TRPO. For a fixed mean-field population distribution p. Exact TRPO(μ) provides a reliable approximation of the value function. The convergence of the algorithm is ex- plicitly influenced by the regularization parameter 17, which determines the optimal step size 1/(n(e++ 22)..
A4. We have that
d Th (s) v(s)
The proposed algorithm relies on the subroutine PolicyUpdate, a key step in refining the policy at each iteration. This update mechanism is inherently tied to the regularization scheme employed in the mirror ascent formulation of TRPO. Specifically, with entropic regularization, as shown in Beck (2017), the policy update admits a closed-form solution in the form of a softmax function. This structure inherently ensures that the updated policy remains within the probabilistic simplex without requiring additional projections. This fosters smooth and stable learning while preventing overly aggressive updates that could destabilize the optimization process.
sup sup AEP(S) SES
<00
The structured interaction with the environment in the con- sidered RL. paradigm requires this concentration property of the occupation measure with respect to the reset distribution v. This property enhances sample efficiency and aids in the accurate estimation of key quantities, such as the value function.
4. Exact algorithm: Exact MF-TRPO
We now introduce Exact MF-TRPO to solve the opti- mization problem (3). Note that the entropic regularization
This policy update leverages a function Q : S x A + R and policy π E IT iteration f, leading to an explicit update
5

---

Finite-Sample Convergence Bounds for MF-TRPO
Algorithm 2 Exact MF-TRPO
fies
Input: Initial distribution μo. K.
&
2: Initialize: Initial policy To the uniform policy,
log L)
|lux - 1 22ep
3j
+ C
3: for & [K] do
2
T.
4: Th <-Exact TRPO(UE-1)
M
for k 2 1, with T == MFG.
5: p&k + MK-1 + 3h 1i--1
(PTt Hk-1
- -Mk-1
All constants appearing in our results are explicitly defined and detailed in Appendix C. where also provide complete proofs supporting our theoretical guarantees.
population update
6: end for
7: Output: j.x.
This convergence result proves its effectiveness in tackling the challenges inherent in the non- non-linear and non- gradient structure of MFNE. Below, we summarize the key insights derived from this result:
rule given by
Qr cxpls) (ar (Q(s, a) - 7 log x (a EWEx (Talls) exp (ar
log क (dlls))
Convergence. We establish an exponential rate of convergence in the first term of the bound to the equi- librium population distribution μu,, while the second one captures the finite- saite-ssappe bias in the best-response computation.
with learning rate ag 1/(n(e + 2))-
Shani et al. (2020) establishes enror bounds for the approxi- mation of value functions that can be directly generalized to our setting. Building on these results, we quantify the gap between the value function the computed policy and the optimal value function under the given mean- mean-field distri- bution. This allows to control the policy itself, and derive policy guarantees.
Learning Rates constraints. The theorem provides ex- plicit constraints the step size 3 (ef. condition (17)), ensuring stability and preventing oscillations or diver- gence in the optimization process.
Explicit Dependence on Model Parameters. All con- stants in the convergence bound are fully character- ized in terms of the structural parameters of the model (ef. Appendix C).
Proposition 4.1. Suppose that Assumptions I and hold. Let (me)/=n be the sequence generated by the Exact TRPO(μ) algorithm. Then, there exists constant C > 0 such that, for all L 2 1, we have
Controlled Policy Learning Bias. The bias intro- duced by policy updates in Exact TRPO, bounded by log(L)/L L (Proposition 4.2), remains controlled throughout the iterative process. This ensures algo- rithmic stability, even with approximations in policy optimization.
log Esnp [1ss - [1(()))] & SC colog
L
We now present Exact ME MF-TRPO, which iteratively solves the MFG problem (3) by updating the pop- ulation distribution μ using the output of Exact (R))(u). This approach assumes direct access to the transition ker- nel and cost function, eliminating the need for stochastic approximation in policy updates.
MF-TRPO.
With these results, we can now explicitly quantify the pa- rameter corresponding to the proximity of our obtained solution with respect to the MFNE.
Corollary 4.3. Suppose that Assumptions 1, 2, and 3 hold. Let μK (resp. TK-1) the output of Exact ME-TRPO (resp. Exact TRPO(UK)) )). Then, there exists a constant C 0, such that (TK+1; PK) is E MFNN, with
The analysis of Exact MF-TRPO is instrumental to under- stand the performances of its sample-bases based counterpart. We do this providing precise theoretical guarantees on conver- gence rates without the additional complexity of sampling- induced errors. Building this deterministic setup, we then focus the convergence behavior of the broader Sample-Based MF-TRPO framework. We use the la- bel "informul" to avoid overloading the main text with technical assumptions (e.g., on learning rates), rigorously stated in Appendix C. Proposition 4.2 (informal). Suppose that Assumptions 1, 2, and 3 hold. Then, there exists a constant > 0 such that the sequence k20 generated by Exact MF-TRPO satis-
K - j=1
log(L)
εK =
B
+ CV
L
5. Stochastic approximation: Sample-Based MF-TRPO
We provide Sample-Based MF-TRPO, a model-free variant of the previous algorithm designed to operate with- out explicit knowledge of the environment's dynamics, nor
6

---

Simite-Sample Convergence Bounds for MF-TRPO
Algorithm 3
()
While we do not have a statistically feasible expression for this mixture policy, it is straightforward sample from UuniCa using Uniform ( ,.), as dis- "r
1: Initialize: To(-|s) U(A) for 8 E S.
2: Input: 12, e, > 0, L.
3: for E [L] do
cussed in Remark D.I.
4: =
Proposition 5.1. Suppose Assumptions 1, 2, 3, and 4 hold. Fix e, > O. Let #b @baif.pe be the output of Cample-Based TRPO(J), over iterations.
5:
Que.y (s, a) = n) = 0, for any (s, a)
6: for I,..., do
Sample 8, ~ -J (.), ~ ((A)
7:
Then, there exists C> such that the following holds with probability greater than
8:
Qunu( (8) (2 t r (8i, (s, 1))
Eieng' se (P53at())))))nn [r (st, oc, (c,
+1 log
E Eaw
uni (-1s) (-16)- I.
(1s))-T((+1)) (T(sss) TV
[|]]] S c
log L L
+E)
9:
Qn (80 t -Ceena ny(8i, ai) t no((s, a4) +1
(sc, a.)
+ Q R (8s, Oj.
10:
11:
S = S U (si)
All the constants appearing in our results are explicitly de- fined and detailed in Appendix D. where we also provide the complete proof's supporting our theoretical guarantees.
12:
end for
13:
for Shr do
14:
for a E A do
15:
(ten()s + Doles me(saa))
((
MF-TRPO.
We present a version of Samp1 e- Ba Rased MF TRPO, with the full algorithm and detailed implemen- tation provided in Appendix D.3.
16: end for
17: th+1 (als) + Pol PolicyUpdate(fe Qrepi (a, 8)
18:
end for
One key aspect of the algorithm is the initialization step. Unlike in a generative model paradigm, access to a state 8 ~ ju is only available through a subroutine initialized at the restart distribution v. For further details on this procedure, refer Appendix D.2.
19:
end for
20:
Output: #z =0
the reward function. Sample-Bast ME-TRPO utilizes sampled trajectories to estimate these updates, making it more applicable to real-world scenarios.
The theoretical foundation of the convergence guarantees of this algorithm relies on deriving high-probability estimates
First, we adapt Exact TRPO to estimate policy updates in a data-driven manner. This approach leverages sampled trajectories to approximate the policy gradient, pro- viding quantitative bounds on the proximity of the best response. Additionally, this TRPO formulation is particu- larly well-suited to the considered oracle-based framework, incorporating the v-restart modeling. This structure ensures robust exploration while maintaining stability in policy up- dates, aligning naturally with the trust-region optimization paradigm.
TRPO.
Algorithm 4 Sample Based MF-TRPO (informal)
1: Input: Initial distribution μo, K.
2: Initialize: Initial policy To is the uniform policy.
3: for A: E [K] do
4: Rx. --ample-Baas
TRPO(AN-1).
for p E [P] do
6: Initialize 80,p,k jik-1-
7:
for m [M] do
Sm.p.k ~ P (-18m-1ppk) end for
The inherent stochasticity in the updates prevents from establishing sample complexity bounds on the last iter- ate of the algorithm. However, by leveraging an averag-
10: Skip 1 11M.m))a)))
11:
end for
12: Č x 1 Ep St.
ing scheme, implemented through a dedicated subroutine (cf. Remark D.1), we mitigate this variability and provide clear quantitative bounds on the desired gap. Specifically, the policy we focus on the uniform mixture a uDaif. over the first L + 1 policies. This averaging scheme is standard in the RL literature and, in the unregularized case, satisfies the identity
P
13: Pu + -k=- 1 + Bk (Ga- - -mt-11)
14: end for
15: Output: μ4K-
(cf. Proposition D.3). This is a crucial step in sample com- plexity bounds and is achieved using martingale- based argument (Harvey et al., 2019). By leveraging concentra- tion inequalities for martingales, the analysis ensures that the error in estimating key quantities, such as the policy value and state distributions, remains controlled with high (1I) probability throughout the learning process.
MPG (Ite, MMG (4 = MFG (4 (# fnt
s M. ..
E=
7

---

Finite-Sample Convergence Bounds for MF-TRPO
Proposition 5.2 (informal). Suppose Assumptions I, 2, 3, and 4 hold. Fix 6, 6 > 0. Then, there exists a constant C' > 0 such that the sequence {ua3820 generated by Sample-Based MF- -RRO satisfies, for k 21, 1,
with established convergence bounds in Shani al. (2020), emphasizing balanced trade-off between computational efficiency and the precision required to approximate the MFNE.
k 33
log(L) L
6. Numerical Experiments
11 /2.12 exp
+
C
+ Cc.
We present here the results of the numerical experiments obtained with the Samp e-Based MF-TRPO algorithm. The environment considered is Grid-Baser Crowd Model- ing game where, from given initial distribution, agents are tasked with moving through a grid, avoiding both static obstacles and potential overcrowding. A representative player's state corresponds to her position within the grid, and at every time step, she can choose to move in any di- rection stay in place. The reward structure imposes small penalty for movement, offers slight incentive for staying, and discourages agents from entering overcrowded areas. In addition, agents are encouraged to move toward a designated target, that is,
All the constants appearing in our results are explicitly de- fined and detailed in Appendix D, where we also provide the complete proofs supporting theoretical guarantees.
The sample-based convergence analysis of Sample-Based MF-TRPO in the model-free set- ting demonstrates that the algorithm preserves the same desirata described in Section driving the convergence of its exact counterpart Exact MF WE-TRPO-proximg updates, entropic regularization, and trust-region opti- mization-remain intact. While having model-agnostic nature, its theoretical power of estimation of the MFNE is preserved, as explicit knowledge of the environment's transition dynamics or reward structure is required. It builds on trajectory sampling to iteratively refine policy updates while maintaining stability and efficiency.
ass = rs, a. max {0.3 - 0.1 dd(s, Starett;; 0},
where .).,,) is d-distance between the corresponding states, and the crowd reward is defined as
This result entails that the stochastic error in the estimation of the mean-field distribution at each iteration does not compound throughout the iterative process. By leveraging concentration inequalities and high-probability guarantees, the cumulative impact of these estimation errors remains controlled, preventing divergence or instability. As a result, sample-Based MF-TRPO retains strong convergence guarantees, making it a practical approach for solving MFG in data-driven manner.
r as a) = - log(((s)) (((ss)+++T +I(a),
where ((a) = 0.2 (a=Styy) - 0.2 1 (a with 1 be- ing the indicator function and и being a crowd-aversion parameter. We refer to Appendix F for additional details and experimental results related to the Exact MF-TRPO algorithm. The environment used here a x 5 grid fea- turing three walls located at coordinates (1, 2), 2), and (3,2), 2). The point of interest is located in the bottom-right corner of the grid, and all the players start clustered in the top-left corner. In Figure it is possible to observe that the exploitability behavior of the Samp l ee-lee-Beeeese Based MF-TRPO algorithm converges after a few iterations, matching the the- oretical predictions, whereas Figure illustrates the progres- sion of the mean field distribution across three different time steps during the learning phase, thus demonstrating that the players progressively learn to distribute themselves around the point of interest, preserving spread over the whole state space.
Moreover, we can also bound the exploitability as follows.
Corollary 5.3. Suppose that Assumptions 1, 2, 3, and 4 hold. Fix 8 > 0. Let fuK (resp. TT [ the out- put of Sample-Based ME-TRPO (resp. the iterates of Sample-Based TRPO((4)). Then, there exists a con- stant C > 0 such that
K
log(L) L
0 exp
B3 j=1
+e
4
7. Conclusion
The complexity analysis demonstrates that the proposed Sample-Based MF-TRPO algorithm achieves com- putational cost scaling as ( to reach an e-MFNE (cf. Remark D.7). This scaling emerges naturally from two principal contributions: the inner loop performing the policy optimization via smmpee-Base TRPC, and the outer population distribution update. These results align well
In this work, we introduced Exact MF MF-TRPO, novel algorithm for computing MFNE in ergodic MFG. By lever- aging the trust-region policy optimization framework, we established explicit non-asymptotic convergence guarantees, demonstrating that Exact ME-TRPO inherits the ((1LL) rate from TRPO, ensuring efficient learning in structured multi-agent systems.
8

---

Finite-Sample Convergence Bounds for MF-TRPO
the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. The work of L.M. and E.M. has been supported by Technology Innovation Institute (TII), project Fed21earn. The work of D.T. has been supported by the Paris Ile-de-France Région the framework of DIM A14IDE.
101
10
Exploitability
100
10
10-1
10-1
10-2
200
0
100
200
Iterations
Iterations
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none which we feel must be specifically highlighted here.
Figure 1. Exploitability achieved by the Sample Based MF TRPP algorithm in the 5 x Grid-Based Crowd Modeling game with the bottom-right corner being point of interest. The left plot corresponds to 0.05, and the right to = 0.3 with results averaged over 10 3 random seeds, respectively.
References
0.
Achdou, and Capuzzo-Dolcetta, Mean field games: numerical methods. SIAM Journal on Numerical Analysis, 48(3):1136-1166) 2010.
06
a6
04
11
34
Achdou, Y. and Laurière, M. Mean field games and applica- tions: Numerical aspects. In Mean Field Games, volume 2281 of C.I.M.E. Foundation Subseries, Pp. 249-307. Springer International Publishing. 2020.
Figure 2. Evolution of the mean field distribution for 1 0.05 in the 5 Grid-Based Based Crowd Modeling game with bottom-right corner being point of interest. From left right: step 0, step 10 and step 200.
Achdou, Y. and Porretta, A. Convergence of a finite differ- ence scheme to weak solutions of the system of partial differential equations arising in mean field games. SIAM Journal on Numerical Analysis, 54(1):161-186, 2016.
To bridge the gap between theoretical guarantees and prac- tical applicability, we further developed Sample e Based ME-TRPO, a model-free variant that estimates policy up- dates solely from sampled trajectories, under the v-restart RL paradigm. Using concentration inequalities, we pro- vided finite-sample complexity bounds for this algorithm, proving convergence under more relaxed assumptions com- pared to recent literature. Moreover, we show that total number of calls to the environment that scales as (())e)), consistent with standard RI. results (see, e.g., Shani et al., 2020). This result highlights the potential RL techniques for scalable and data-driven MFG solutions.
Achdou, Y., Camilli, F., and Capuzzo-Dolcetio I. Mean field games: numerical methods for the planning problem. SIAM Journal on Control and Optimization, 50(1):77- 109, 2012.
Agarwal, A., Kakade, S., and Yang, L. F. Model-based rein- forcement learning with a generative model is minimax optimal. Conference on Learning Theory, pp. 67-83. PMLR, 2020.
Overall, work contributes to the growing intersection of MFG and RL, providing both theoretical insights and algo- rithmic advancements. Future directions include extending these methods to more general MFG settings, such as those with continuous state spaces, and exploring adaptive sam- pling techniques to further improve efficiency real-world applications.
Alasseur, C., Ben Taher, I., and Matoussi, A. An extended mean field game for storage in smart grids. Journal of Optimization Theory and Applications, 184:644-670, 2020.
Algumaci, T., Solozabal, R., Alami, R., Hacid, H.. Debbah, M., and Takáč, M. Regularization of the policy updates for stabilizing mean field games. In Pacific-Asia Con- ference on Knowledge Discovery and Data Mining, pp. 361-372. Springer, 2023.
Acknowledgements
The work of A.O. and E.M. was funded by the European Union
1601). Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union or
Anahtarci, B., Kariksiz, C. D., and Saldi, N. Learning mean- field games with discounted and average costs. Journal of Machine Learning Research. 24(17):1-59, 2023a.

---

Finite-Sample Convergence Bounds for MF-TRPO
Anahtarci, B., Kariksiz, C. D., and Saldi, N. Q-learning in regularized mean-field games. Dynamic Games and Applications, 13(1):89-117, 2023b.
reinforcement learning (ADPRL), pp. 202-209, IEEE, 2011.
Cardaliaguet, P., Delarue, F., Lasry, J.-M., and Lions, P.- L. The master equation and the convergence problem in mean field games:(ams-2211) Princeton University Press, 2019.
Anand, E.,, Karmarkar, I., and Qu, Mean-field sampling for cooperative multi-agent reinforcement learning. arXiv preprint arXiv:2412.006611 2024.
Angiuli, A., Fouque, J.-P., and Laurière, M. Unified rein- forcement Q-learning for mean field game and control problems. Mathematics of Control, Signals, and Systems, 34(2)217-271, 2022.
Carmona, R. and Laurière, M. Convergence analysis of machine learning algorithms for the numerical solution of mean field control and games I: The ergodic case. SIAM Journal on Numerical Analysis, 59(3):1455-144 1485, 2021.
Angiuli, A., Fouque, J.-P., Laurière, M., and Zhang, M. Convergence of multi-scale reinforcement Q-learning al- gorithms for mean field game and control problems. arXiv preprint arXiv:2312.0660 2023.
Carmona, R., Delarue, F., el. Probabilistic theory of mean field games with applications I-II. Springer, 2018.
Carmona, R. A., Fouque, J. P., and Sun, H. Mean field games and systemic risk. Communications in Mathemati- cal Sciences, 13(4):9 2015.
Arapostathis, A., Biswas, A., and Carroll, On solu- tions of mean field games with ergodic cost. Journal de Mathématiques Pures el Appliquées, 107(2):205-251, 2017.
Chassagneux, J.-F., Crisan, D., and Delarue, F. Numerical method for fbsdes of McKean- Vlasov type. The Annals of Applied Probability, 29(3):1640- 2019.
Asadi, K., Mísra, D., and Littman, M. Lipschitz continuity in model-based reinforcement learning. In International Conference Machine Learning, pp. 264-273. PMLR, 2018.
Cover, T. M. Elements of information theory. John Wiley Sons, 1999.
Austrin, P., Braverman, M., and Chlamtáē, E. Inapprox- imability of nn-complete variants of nash equilibrium. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 13-25. Springer, 2011.
Cui, K. and Koeppl, H. Approximately solving mean field games via entropy-reeullrized deep reinforcement learn- ing. In International Conference on Artificial Intelligence and Statistics, pp. 1909-1917. PMLR, 2021.
Azar, G. M., Munos, R., and Kappen, J. J. Minimax pac bounds on the sample complexity of reinforcement leam- ing with a generative model. Machine learning, 91:325- 349, 2013.
Cui, K. and Koeppl, H. Learning graphon mean field games and approximate Nash equilibria. In International Con- ference on Learning Representations, 2022.
Doncel, J., Gast, N., and Gaujal, B. A mean field game analysis of sir dynamics with vaceination. Probability in the Engineering and Informational Sciences, 36(2): 482-499, 2022.
Bardi, M. and Priuli, F. S. Linear- Linear-quadratic n-person and mean-field games with ergodic cost. SIAM Journal on Control and Oplimization, 3255333022-3 2014.
Bassière, A., Dumitrescu, R., and Tankov, P. A mean-field game model of electricity market dynamics. In Quantita- tive Energy Finance: Recent Trends and Developments, pp. 181-219. Springer, 2024.
Espinosa, G.-E. and Touzi, N. Optimal investment under relative performance concerns. Mathematical Finance, 25(2):221-2577 2015.
Fischer, M. and Silva, F. J. On the asymptotic nature of first order mean field games. Applied Mathematics & Optimization, 84:2327-2357, 2021.
Becherer, D. and Hesse, S. Common noise by random mea- sures: Mean-field equilibria for competitive investment and hedging. arXiv preprint arXiv:2408.00 175, 2024.
Flandoli, F., Ghio, M., and Livieri, G. N-player games and mean field games of moderate interactions. Applied Mathematics & Optimization, 85(3):38, 2022.
Beck, A. First-order methods in optimization. SIAM, 2017.
Bhandari, and Russo, D. Global optimality guarantees for policy gradient methods. Operations Research, 2024.
Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S. Counterfactual multi-agent policy gradi- ents. Proceedings of the AAAI conference on artificial intelligence, 32(1), 2018
Braun, D. A., Ortega, A., Theodorou, E., and Schaal, S. Path integral control and bounded rationality. In 2011 IEEE symposium on adaptive dynamic programming and
10

---

Finite-Sample Convergence Bounds for MF-TRPO
Fort, G., Moulines, E., and Priouret, P. Convergence of adap- tive and interacting markov chain monte carlo algorithms. The Annals of Statistics, 396)):362-33289, 2011.
solutions. In 42nd IEEE international conference deci- sion and control (IEEE cat. No. 03CH37475), volume 1, pp. 98-103. IEEE, 2003.
Fox, R., Pakman, A., and Tishby, N. Taming the noise in reinforcement learning via soft updates. Proceedings of the Phirty-Second Conference on Uncertainty in Artificial Intelligence, 2016.
Huang. M., Malhamé, R. P., and Caines, P. E. Nash equi- libria for sage--populatinn lincar stochastic systems of weakly coupled agents. In Analysis, control and optimiza- tion of complex dynamic systems, pp. 215-252. Springer, 2005.
Geist, M., Scherrer, B., and Pietquin, O. A theory of regu- larized markov decision processes. International Con- ference on Machine Learning, pp. 2160-2169. PMLR, 2019.
Huang, M., Malhamé, R. P., and Caines, P. E. Large popu- lation stochastic dynamic games: closed-loop McKean- Vlasov systems and the Nash certainty equivalence prin- ciple. Commun. Inf. Syst., 6(1):221-255) 2006a.
Geist, M., Pérolat, J.. Laurière, M., Elie, R., Perrin, S., Bachem, O., Munos, R., and Pietquin, O. Concave utility reinforcement learning: The mean-field game viewpoint. In Proceedings of the 21 International Conference on Autonomous Agents and Multiagent Systems, pp. 489- 497, 2022.
Huang, M., Malhamé, R. P., and Caines, P. E. Nash cer- tainty equivalence in large population stochastic dynamic games: Connections with the physies of interacting parti- cle systems. In Proceedings of the 45th IEEE Conference Decision and Control, pp. 4921 4926. IEEE, 2006b.
Germain, M., Mikael, J., and Warin, X. Numerical resolu- tion of McKean- Valsenn-Vlasov FBSDEs using neural networks. Methodology and Computing Applied Probability, 24 (4):2557-2286, 2022.
Iqbal, and Sha, F. Actor-attention-critic for multi-agent reinforcement learning. In International conference machine learning, pp. 2961-2970. PMLR, 2019.
Gronauer, S. and Diepold, K. Multi-agent deep reinforce- ment learning: a survey. Artificial Intelligence Review, 55(2))895-944 2022.
Kakade, S. and Langford, J. Approximately optimal ap- proximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learn- ing. pp. 277,274, 2002.
Guo, X., Hu, A., Xu, R., and Zhang. J. Learning mean- field games. Advances in neural information processing systems, 32, 2019.
Kakade, S. M. On the sample complexity of reinforcement learning. University of London, University College Lon- don (United Kingdom), 2003.
Guo, X., Hu, A., Xu, R., and Zhang, J. A general frame- work for learning mean-field games. Mathematics of Operations Research, (8(2):5566686 2023.
Kearns, M. and Singh, S. Finite Finite-sample convergence rates for q-learning and indirect algorithms. Advances in neural information processing systems, 11, 1998.
Haarnoja, T., Tang, H., Abbeel, P., and Levine, S. Rein- forcement learning with deep energy-based policies. In International conference on machine learning, pp. 1352- 1361. PMLR, 2017.
Kober, J., Bagnell, J. A., and Peters, J. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 1233 1274, 2013.
Harvey, N. J., Liaw, C.. Plan, Y., and Randhawa, S. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pp. 1579-1613. PMLR, 2019.
Lacker, D. and Zariphopoulou, T. Mean field and n-agent games for optimal investment under relative performance criteria. Mathematical Finance, 29(4):1003-1038, 2019.
Lasry, J.-M. and Lions, P.-.. Jeux à champ moyen. I-Le cas stationnaire, Comptes Rendus Mathématique, 343(9); 615-625, 2006a.
Howard, R. A. Dynamic programming and markov pro- cesses. John Wiley, 1960.
Howard, R. A. and Matheson, J. Risk-sensitive markov decision processes. Management science, 18(7):356-369 1972.
Lasry, J.-M. and Lions, P.-L. Jeux champ moyen. II- Horizon fini contrôle optimal. Comptes Rendus. Mathématique, 343(10):679 6844 2006b.
Huang, M., Caines, P. E., and Malhamé, R. P. Individual and mass behaviour large population stochastic wireless power control problems: centralized and nash equilibrium
Lasry, J.-M. and Lions, P.-L. Mean field games. Japanese journal of mathematics, 2(1):229 2007.

---

Finite-Sample Convergence Bounds for MF-TRPO
Laurière, M., Perrin, S., Pérolat, J., Girgin, S., Muller, P., Élie, R., Geist, M., and Pietquin, O. Learning in mean field games: A survey, arXiv preprint arXiv:2205.12944 2022.
Perrin, S., Pérolat, J., Laurière, M., Geist, M., Elie, R., and Pietquin, O. Fictitious play for mean field games: Continuous time analysis and applications. Advances in neural information processing systems, 18:13199-13215 2020.
Lavigne, P. and Tankov, P. Decarbonization of financial markets: mean-field game approach. arXiv preprinl arXiv:2301.09163, 2023.
Perrin, S., Laurière, M., Pérolat, J., Geist, M., Elie, R., and Pietquin, O. Mean Field Games Flock! The Rein- forcement Learning Way. In Proceedings of the Thirtieth International Joinl Conference on Artificial Intelligence, LJCAI-21, pp. 356-362, 8 2021.
Le Lan, C., Bellemare, M. G., and Castro, P. S. Metrics and continuity in reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(9): 8261-8269, 2021.
Perrin, S., Laurière, M., Pérolat, J., Elie, R., Geist, M., and Pietquin, O. Generalization in mean field games by learning master policies. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9):9413-4211, 2022.
Mao, W. Qiu, H., Wang, C., Franke, H., Kalbarezyk, Z.,, Iyer, R., and Basar, T. A mean-field game approach to cloud resource management with function approximation. Advances in Neural Information Processing Systems, 35: 06243-36258, 2022.
Peters, J., Mulling, K., and Altun, Y. Relative entropy policy search. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1):1607-1612, 2010.
Marcus, S. I., Gernande--Gauceraadd E., Hernández- Hernandez, D., Coraluppi, S., and Fard, P. Risk sensitive markov decision processes. In Systems and control in the twenty-first century, pp. (39.279. Springer, 1997.
Puterman, M. L. and Shin, M. C. Modified policy itera- tion algorithms for discounted markov decision problems. Management Science, 24(11):127-11337, 1978.
Matignon, L., Laurent, G. J., and Le Fort-Piat, N. Hys- teretic q-learning: algorithm for decentralized rein- forcement learning in cooperative multi multi-agent teams. In 2007 HEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 64-69, IEEE, 2007.
Ruszczyúski, A. Risk-averse dynamic programming for markov decision processes. Mathematical programming. 125:235-261, 2010.
Saldi, N. Discrete-time average-cost mean-field games on polish spaces. Turkish Journal of Mathematics, 44(2): 463-480, 2020.
Mci. J., Xiao, C., Szepesvari, C., and Schuurmans, D. On the global convergence rates of softmax policy gradient methods. In International conference on machine learn- ing, pp. 6820-6829. PMLR, 2020.
Samvelyan, M., Rashid, T., De Witt, C. S., Farquhar, G., Nardelli, N., Rudner, T. G., Hung, C.-M., Torr, H., Foerster, J., and Whiteson, S. The starcraft multi-agent challenge. arXiv preprini arXiv: 120.//0020240 04043, 2019.
Mnih, V. Asynchronous methods for deep reinforcement learning. International Conference on Machine Learning. pp. 1928-1937, 2016
Scherrer, B. and Geist, M. Local policy search in a convex space and conservative policy iteration as boosted policy search. In Machine Learning and Knowledge Discovery in Databases: European Conference. ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings, Part III 14, pp. 35-50. Springer, 2014.
Nash, J. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48-44 49,484491111 1950.
Nash, J. Non-cooperative games. Annals of Mathematics, 54(2))286-295, 1951.
Neu. G., Jonsson, A., and Gómez, V. A unified view of entropy-regularizze markov decision processes. arXiv preprint 100.::17705.77770 2017.
Schulman, J., Levine, S., Moritz, P., Jordan, M., and Abbeel, P. Trust region policy optimization. In Proceedings of the 32nd International Conference on International Conference Machine Learning- Volume 37, pp. 1889- 1897, 2015.
O' O'Donoghue, B., Munos, R., Kavukcuoglu, K., and Mnih, V. Combining policy gradient and q-learning. 5th Inter- national Conference on Learning Representations, 2017.
Shalev-Shwand S., Shammah, S., and Shashua, A. Safe, multi-agent, reinforcement learning for autonomous driv- ing. arXiv preprint arXiv:1610.0322 2016.
Pérolat, J., Perrin, S., Elie, R., Laurière, M., Piliouras, G., Geist, M., Tuyls, K., and Pietquin, O. Scaling mean field games by online mirror descent. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pp.
Shani. L., Efroni, Y., and Mannor, S. Adaptive trust region policy optimization: Global convergence and faster rates
2022.
12

---

Finite-Sample Convergence Bounds for ME-TRPO
for regularized mdps. Proceedings of the AAAI Confer- on Artificial Intelligence, 34(04))5668-55)) 5675, 2020.
Sidford, A., Wang, M., Wu, X., Yang, L.., and Ye, Y. Near- optimal time and sample complexities for solving markov decision processes with generative model. Advances in Neural Information Processing Systems, 31, 2018.
Sutton, R. and Barto, A. G. Reinforcement learning: An introduction. SIAM Rev, 6(2):423, 2018a.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018b.
Szepesvári, C. Algorithms for reinforcement learning. Springer nature, 2022.
Tangpi, L. and Zhou, X. Optimal investment in a large popu- lation of competitive and heterogeneous agents. Finance and Stochastics, 28(2):99-5551, 2024.
Weinan, E., Han, J., and Jentzen, A. Deep learning- baaedd numerical methods for nigh-diimesiioal parabolic partial differential equations and backward stochastic differential equations. Communications in Mathematics and Statis- tics, 4(5):349-380, 2017.
Wiering, M. A. et al. Multi-agent reinforcement learning for traffic light control. In Machine Learning: Proceedings of the Seventeenth International Conference (ICML'2000)
pp. 1151-1158, 2000.
Williams, R. J. and Peng. J. Function optimization using connectionist reinforcement learning algorithms. Con- nection Science, 3(3))241-2600 1991.
Yardim, B., Cayci, S., Geist, M., and He, N. Policy mirror ascent for efficient and independent learning in mean field games. In International Conference on Machine Learning, pp. 39722-39754, PMLR, 2023.
Zaman, M. A. U., Koppel, A., Bhatt, S., and Basar, T. Oracle-free reinforcement learning in mean-field games along single sample path. In International Conference on Artificial Intelligence and Statistics, pp. 10178-10206. PMLR. 2023.
Zhang, K., Yang, Z., and Başar, Multi aggnt reinforce- ment learning: A selective overview of theories and algo- rithms. Handbook of reinforcement learning and control,
pp. 321-384, 2021.
Ziebart, B. D. Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegie Mel- lon University, 2010.
Ziebart, B. D., Bagnell, J. A., and Dey, A. K. Modeling interaction via the principle of maximum causal entropy. International Conference on Machine Learning (ICML), pp. 1255 -1262, 2010.
13

---

Finite-Sample Convergence Bounds for MF-TRPO
Appendix
In the appendix, we provide a detailed exposition the theoretical foundations and technical results supporting our main contributions. In Appendix A, we give broad deseription of related work in MFG and MFRL, and in Appendix B, we lay out the fundamental framework of the MFG problem we aim study. This section introduces the ergodic MFG formulation and its connection the discounted setting. We also discuss the role of entropic regularization in RL and MFG, emphasizing its impact on stability and the approximation of Nash equilibria. In Appendix B.4, we present key assumptions we use in the proofs. In Appendix C, we present the exact IRPOO-aseed algorithm for solving the MFG problem. This section provides a precise formulation of the exact methods and establishes its theoretical convergence guarantees. The adaptation of TRPO to the MFG setting is examined in detail, leveraging the structure of entropy-regularize RL. We present formal results on convergence rates and error bounds, ensuring the effectiveness and reliability of these methods in computing approximate MFNE. In Appendix D, we extend our analysis to the sample-based version of the algorithm. Here, we derive global sample complexity results and analyze the statistical error introduced by sampling. We establish high- probabiiltt bounds on the approximation enror at each iterations. Next, in Appendix E, we provide additional proofs and auxiliary results that support the theoretical analysis conducted in the previous sections. These supplementary results play crucial role in rigorously validating the convergence and stability properties of our proposed algorithms. Finally, in Appendix F we provide additional experimental details as well as experiments on exact versions of the algorithm.
A. Related works
(LQ) case, where explicit solutions can be derived analytically or through simple ordinary differential equations, computing MFNE numerically remains challenging and active research area. A vast body of literature has focused on addressing the computational complexity of these models, leading to three major methodological approaches.
Except for the well-known
The first class of methods relies on PDE approximations, leveraging the classical formulation of MFG through the JellliBBlllaa equation coupled with the Setter-PPaanc-ooooogoooo equation (Achdou & Capuzzo-Dolcetti 2010; Achdou al., 2012 2; Achdou & Porretta, 2016; Achdou & Laurière, 2020). While mathematically elegant, these methods suffer from the well-documented curse of dimensionality, as solving PDEs numerically becomes intractable in high-dimensional state spaces.
The second approach leverages deep learning techniques with neural networks to approximate equilibrium solutions. These methods exploit function approximation to bypass explicit PDE resolution, making them a promising alternative in high- dimensional settings (Weinan et al., 2017; Chassagneux et al., 2019; Germain et al., 2022). However, they lack rigorous convergence guarantees. Additionally, these methods struggle to capture model specifications in a purely data-driven manner directly, limiting their adaptability in real-world applications.
The third category of numerical methods integrates RI. techniques into the MFG framework, leading to two primary subcategories. The first subcategory employs RL as a solver for given MFG model, using value-based or policy- RL techniques to approximate Nash equilibria (Pérolat et al., 2022; Perrin et al., 2022). These approaches have achieved state-of-the-ar performance in various settings and have been successfully deployed in large-scale simulations.
The second subcategory focuses on developing model-free RL algorithms for solving MFG, often incorporating regularization techniques enhance stability (Cui & Koeppl, 2021; Perrin et al., 2021). While these methods show promising empirical performance, theoretical guarantees on smite-sample complexity remain limited, particularly for model-based RL approaches.
RL for MFG. Among model-free RL approaches, we identify three main categories: value function-basee methods, actor- critic methods-winn combine value-based and policy-based approaches and policy-oriented methods. As classical RL, proximal methods have emerged as state-of-the-arr techniques across a wide range of tasks, both in model-specific and model-agnostic settings.
Several studies have explored Q-learning-based algorithms for MFG, establishing theoretical convergence guaran- tees (Angiuli et al., 2022; 2023; Guo et al., 2019; Anahtarci et al., 2023b). However, these approaches rely on stringent assumptions that are often difficult to verify in practice. Moreover, Q-learning operates within the generative model oracle framework of RL, which assumes full query access to state-action transitions. In contrast, the restart oracle assumption provides a significantly weaker paradigm, offering a more practical and adaptable alternative for real-worle learning settings.
14

---

Simite-Sample Convergence Bounds for MF-TRPO
Two-timescale updates have been employed in, e.g. Zaman et al. (2023) and Mao et al. (2022), where policy updates operate on a faster timescale, while the population distribution evolves more slowly based on model-based estimates of state dynamics. However, these approaches introduce significant challenges in both theoretical analysis and practical implementation. Their convergence often relies on strong assumptions that are difficult to verify, particularly in non non-stationary environments.
In the MFG setting, proximal methods have been adopted for their stability properties and strong empirical performance. Among these approaches, we highlight the work of Pérolat et al. (2022), where the authors investigate Online Mirror Descent (OMD) from a model-specific perspective. Yardim et al. (2023) build up in this direction, developing the model-free analysis. Their approach, however, does not consider the crucial aspect of population updates, placing itself in the mo-manipulation regime. In contrast, our work explicitly discusses how the monotonicity assumption up to certain threshold, perspective that aligns naturally with the ergodic nature of the Markov reward process once a policy has been selected. This additional consideration allows us to provide a more refined analysis of the learning dynamics in MFG, ensuring a more structured and well-posed approach to policy optimization.
stabilize the population evolution
Furthermore, Yardim et al. (2023) imposes stringent assumptions by requiring that policies remain uniformly bounded away from zero by fixed constant, effectively enforcing an overly rigid form of regularization. This constraint exceeds the controlled bias typically introduced by entropic regularization. Notably, similar assumption appears in Angiuli et al. (2022; 2023), where the Markov reward process is required to be absolutely continuous with respect to the uniform distribution over the state-action space-a significantly stronger condition than our unichain assumption.
By adopting a more flexible framework, we relax these restrictive conditions while improving sample complexity, particularly in terms of the number of required trajectories. Our analysis still achieves an ((1LL) error bound in trajectory estimates but under significantly milder assumptions.
An interesting direction for future work would be connect our framework with that of Anand et al. (2024), which focuses mean-field control. While their setting assumes cooperative agents optimizing common objective, our work addresses non-cooperative mean-field games. Despite this key difference, it would be valuable to explore how our analytical tools particularly for handling weak structural assumptions- could generalize their approach to broader settings.
B. Framework
B.1. Ergodic MFG problem
The ergodic problem focuses on optimizing the long-term average performance of stochastic system over an infinite time horizon. In contrast to finite time horizon problems, the emphasis on stability and efficiency over time, making it essential for operations such as energy systems, financial markets and resource management. The goal is to find stationary policies that balance short-term costs with long-term gains. This approach is robust to uncertainties and ensures consistent performance despite stochastic disturbances.
Ergodic MFG have been first studied in continuous time and space problems (see, e.g., Bardi & Priuli, 2014; Arapostathis et al., 2017; Carmona & Laurière, 2021). In the context of discrete-time MFG, the ergodic setting has been studied by Saldi (2020) under the terminology of average-cost MFG. Anahtarci al. (2023a) proposed a learning algorithm based on Q-learning and analyzed its convergence and sample complexity using a strict contraction argument.
Similarly, in Guo et al. (2023), the authors address the problem of evolving mean-field parameters, focusing dynamically adjusting the population distribution over time. This differs from our approach, where we aim to learn policies without requiring explicit control or manipulation of the mean-field field distribution at each step.
B.2. From ergodic MFG to discounted formulation
In this article, we focus on an ergodic equilibrium problem within the framework of mean-field games. This problem is traditionally defined as the unique solution resulting from the optimization of a long-term average cost function
T
MFG (4 == lim inf E T-
1 T
Σ
r (st, as, ub)
song, (-)s))))))) ii 11 Pre #44 (1ps,arr.p)))
for π = (m We seek Nash equilibria with respect to this cost function, iee, a tuple (m*,, n,, {) such that
15

---

Fimite-Sample Convergence Bounds for MF-TRPO
JMRG (m", 11,)) max JMFG IT 14, ;
((8)) Pr-
Such problem independent of the initial condition & and is stationary. Therefore, we can consider only constant vectors π ( for के = π, for any 2 0, am I1.
Moreover, given the stationarity of both the policy and the problem, we can further restrict ourselves to time- invaiinnaiant policies and reformulate the problem as follows.
erg.stat (T) lim inf T-000
E T
Σ
(8t, 0t: (t; (1)
eamu, a-le)) S (1se.ee.))))
Moreover, as also noted in Carmona et al. (Chapter 7.1, Volume 1, 2018), we have that
JFG org,stat (T, 11) == lim 7-1 1
1
J MFG (.)
with
MFG TT, 14, = =
(st, at,
earg, (omme(-l9e)) P (1
For this reason, for a close to I, we can consider the problem as formulated in Section 2. This is also the consideration behind the formulation of the ergodic problem presented in Laurière et al. (Remark 8, 2022).
B.3. Regularization
Entropy regularization in RL. Entropy regularization has been a prominent concept across various fields, including RL (Sutton & Barto, 20; Szepesvári, 2022). In dynamic programming and RL contexts, entropy-regularize Bellman equations and corresponding algorithms have been extensively studied to address key challenges. These include inducing safe exploration (Fox et al., 2016) and designing risk-sensitive policies (Howard & Matheson, 1972; Marcus al., 1997; Ruszczyúskii, 2010). Additionally, these methods have been employed to model behaviors of imperfect decision-makers, as demonstrated by Ziebart et al. (2010); Ziebart (2010); Braun et al. (2011).
Beyond dynamic programming approaches, direct policy search methods have emerged as a powerful alternative for optimizing retropy-regularizzed objectives. These methods, which aim to drive safe online exploration in unknown Markov decision processes, have been explored in works such as Williams & Peng (1991); Peters et al. (2010); Schulman et al. (2015); Mnih (2016); O' o'Donoghue al. (2017). Notably, state-of-the-art RL methods, including those by Mnih (2016); Schulman et al. (2015), leverage reguaay-re policy search to balance exploration and exploitation effectively, highlighting the central role of regularization in achieving robust and safe learning.
Regularization, particularly the entropic one, has been extensively studied in the theoretical literature. In Neu et al. (2017), the authors provide a comprehensive analysis of mirror descent methods for RI, highlighting how regularization influences policy optimization and convergence properties. Similarly, Geist al. (2019) formalize the theoretical impact entropy regularization, demonstrating its role in stabilizing policy updates and improving exploration.
Regularization in RL for MFG. In the inherently non-linear MFG setting, stabilizing policy updates essential to ensuring convergence and preventing oscillatory behavior. In this setting, the underlying dynamics involve the interplay of numerous agents and necessitate precise balance between individual and collective objectives. Regularization plays key role by smoothing the cost landscape, mitigating instability, and creating well-conditioned optimization problems, ultimately leading to more reliable and efficient learning dynamics.
Moreover, MFG serve as approximations of the N-player game problem in MARL, leveraging assumptions like anonymity and homogeneity to simplify the otherwise intractable dynamics of joint policy updates in large-scale systems. Intro- ducing regularization into the MFG framework not only enhances stability but is theoretically justified, as the additional
16

---

Sinite-Sample Convergence Bounds for MF-TRPO
approximation error introduced by regularization is comparable the inherent O(1/VN) error of the MFG approximation itself.
Moreover, in the context of RL for MFG, regularize policies has been used to facilitates convergence of learning algo- rithms. Cui & Koeppl (2021) show that strict contraction property used by several other works fail to holds in general. The authors then studied a modified MFG with an entropy-regularizee reward and showed that, for a sufficiently large degree of regularization, policy-iteration type RL algorithms can be shown to converge using contraction techniques. A similar approach has been used by Anahtarci et al. (2023b) to prove convergence of Q-learning algorithm, and by Yardim al. (2023) to prove the convergence of policies learned by independent learners in regularized MFG. On the empirical side, policy regularization has also been used by Algumaei et al. (2023) through an algorithm relying proximal policy optimization (PPO).
B.4. Discussion the assumptions
Lipschitz property of the MDP parameters. Assumption 1 of Lipschitz continuity on the parameters of the MDP, reward function r and transition probability matrix P. implies that the MDP does not change abruptly with respect to the state or action. This ensures that small perturbations in these variables lead to correspondingly small changes in the MDP's dynamics.
This assumption is well-established in the RL literature (see, egg., Asadi et al., 2018; Le Lan et al., 2021) and serves several critical purposes. First, it ensures the smoothness of value functions, essential for the stability of iterative optimization methods Second, it enables the derivation of meaningful error bounds and convergence rates, as shown in foundational works on policy optimization.
Moreover, as the reward function r is defined on a compact domain, since S and A are finite, it is guaranteed that ||r|| < cc. A common practice in RL literature to normalize r. i.e., ||r 1, without loss of generality (Mei et al., 2020). This normalization simplifies expressions and makes algorithms sraeeiiddependen.. However, in this work, we retain ||r||xo explicitly in our analysis to emphasize the clear dependence of all constants and bounds on the magnitude of the reward function. This approach ensures transparency in how the properties of r influence the theoretical results and practical performance.
Unique recurrence property of the Markov reward process. To ensure the well-posedness of the TRPO algorithm and derive meaningful performance bounds, we impose the unichain assumption 3. This assumption guarantees that the Markov chain induced by any admissible policy has a single recurrent class, potentially accompanied by a set of transient states. Such property ensures that the long-term behavior of the Markov chain is well-defined, with unique stationary distribution for each policy.
The unichain property plays a pivotal role in stabilizing the analysis of RL algorithms, particularly TRPO, as highlighted in Neu et al. (2017). eliminates ambiguities on the initial population distribution arising from multiple recurrent classes, which could otherwise complicate the evaluation of value functions and policy improvement steps. As shown in in Puterman & Shin (1978), this condition is satisfied if all policies induce an irreducible and aperiodic Markov chain. Moreover, in the regularized setting, the regularization term helps in its satisfaction. Therefore, for any mean-field population profile p. the Markov chain P/"" is irreducible and aperiodic, implying the existence of unique stationary distribution Azx and establishes the foundation for the mixing property (9).
The ergodicity assumption has been explored in various forms by different authors in the MFG literature. Notably, Angiuli et al. (2022; 2023) impose the condition that the induced Markov chain is aperiodic and absolutely continuous with respect to the uniform distribution over the state space. While this guarantees strong mixing properties, it is highly restrictive assumption, it effectively enforces immediate communication between all states, which is often unrealistic in practical applications. Instead, we generalize this assumption by adopting standard ergodicity condition widely used in RL literature (Mci et al., 2020). This approach maintains the necessary stability properties while allowing for more realistic transition dynamics, ensuring broader applicability in complex multi-agent systems.
Finite concentration of the occupation measure. In this paper, we adopt RL paradigm where access to the environment is structured through a v--rettar, ensuring that each learning episode begins from a well-defined initial state distribution. The concentration of the occupation measure assumption is crucial for the convergence of the Sample-Bas algorithm, ensuring that the estimation of the policy update remains stable and accurate over successive iterations. To
TRPO
17

---

Finite-Sample Convergence Bounds for MF-TRPO
compute this task, the algorithm operates in an episodic setting, where each episode begins by drawing an initial state so from the restart distribution v followed by collecting trajectory (so, ro, $1; (1.-.. under the current policy Te- This episodic structure allows the algorithm to interact with the MDP in a controlled manner, facilitating the estimation of quantities like the value function JMFG.
This approach builds on the seminal work of Kakade (2003), which introduced the notion of a v-restart model as an intermediary assumption in RL. The v-restart model is weaker than having direct access to the true model or a generative model (Kearn & Singh, 1998; Azar et al., 2013; Sidford al., 2018: Agarwal al., 2020), as it does not require full knowledge of the transition kernel or the reward function. At the same time, it is stronger than the unrestricted case where no restarts are allowed, ensuring that the algorithm can sample states from well-defined initial distribution at the start of each episode. This controlled interaction with the environment is crucial for accurately estimating value functions and gradients in the Sample- Based TRPO algorithm, ultimately enabling convergence guarantees.
The supremum in Assumption 4, often referred to as the concentrability coefficient, plays a critical role in the theoretical analysis of policy search algorithms. This concept was initially highlighted in the foundational work of Kakade & Langford (2002) and has since been extensively studied in the RL (RL) literature.
One of the reasons the concentrability coefficient has garnered attention is its frequent appearance in the analysis of approximate policy iteration schemes. Research by Scherrer & Geist (2014) and Bhandari & Russo (2024) shows that the concentrability coefficient often governs error propagation during learning. In essence, it provides bounds on how errors in approximating value functions or policies propagate through successive updates.
C. Exact algorithms
Various algorithms have been proposed in the literature to address the exact MFG problem in scenarios where the MDP kernel and the reward function are fully accessible. In this case, the value function and a best response can be computed using dynamic programming and backward induction. This approach has been used, e.g., by Perrin et al. (2020) and Pérolat et al. (2022) to implement Fictitious Play (FP) and Online Mirror Descent (OMD) respectively. Cui & Koeppl (2022) presented a exact fixed point algorithm for graphon games. Angiuli et al. (2023) analyzed the convergence of a model-specific multi-scale algorithm for MFG.
This line of research often stems from the classical control theory and optimization frameworks, tailored to solve specific MFG problems with high precision. These methods focus on the exact representation of the MFG dynamics, providing critical insights into the equilibrium behavior of large-agent systems. In this work, we propose a novel adaptation of the TRPO algorithm, building on the robust framework of Shani et al. (2020). Our adaptation incorporates key elements of the MFG structure, leveraging entropic regularization and mean-field population dynamics. Moreover, we establish finite sample complexity results for this algorithm, demonstrating its theoretical convergence properties and its practical applicability in solving the ergodic MFG problem under a finite state-action setting.
C.1. TRPO exact formulation
TRPO, inherently structured as a mirror descent method, proves particularly well-suited for entropy-regullrrized settings. This framework benefits from a significant simplification: the policy update admits closed-form solution (Beck, 2017), expressed in terms of the Q-function associated with the current policy. By recasting the optimization problem in terms of Q-function computation, the algorithm focuses the essential dynamies of the system, effectively bypassing the need for direct policy optimization over high-dimensional space.
This closed-form update leverages the softmax form of the policy, direct consequence of entropy regularization. The softmax structure ensures that the updated policies remain strictly in the interior of the probability simplex P(S), avoiding deterministic solutions. This property not only facilitates numerical stability but also aligns with the theoretical foundations of the regularized problem. The use of first-order conditions becomes feasible and efficient, as the regularization term enforces a smooth, convex optimization landscape.
Moreover, the reward function's 's linear dependence the policy pairs seamlessly with the coereive nature of the entropy- regularized optimization problem. The coercivity guarantees that the optimal policies minimize the objective within the confines of the simplex, effectively balancing exploration and exploitation. This alignment between the problem structure and the algorithm's mechanics underscores the power of TRPO in achieving convergence while maintaining
18

---

Finite-Sample Convergence Bounds for MF-TRPO
theoretical guarantees in entropy-rregularized MFG settings. By translating the original optimization problem into Q-function evaluations, the algorithm provides practical yet robust pathway to finding approximate Nash equilibria in complex systems.
In the case where the mean-field population distribution parameter is fixed, the algorithm Exact TRPO(p) provides robust approximation to the value function. By iteratively updating the policy using trust region optimization techniques, the algorithm ensures convergence rates that explicitly depend on the regularization parameter r). Given fixed r,, the learning rate 1/(r7( + 2)) is optimally chosen balance stability and efficiency in the policy updates. The following result establishes the error bounds for the value function approximation, highlighting the role of entropic regularization in convergence guarantees. Specifically, the bounds quantify the discrepancy between the value funetion induced by the computed policy and the optimal value function for the given mean-field population profile.
Theorem C.1 (Theorem 16 in Shani al. (2020)). Fix μ P(S) the initial distribution. Let {Telé be the sequence generated by the Exact TRPO(μ) algorithm. Then, there exists constant CTRPO,0 > 0 such that
JMG (T.. M S CTRrO, (lr + + log² [Al) log 771 33
(12)
L
Corollary C.2. Let (Ne)L=) be the sequence generated by the Exact TRPO(μ) algorithm. Then, have that
Σ [ Ta(-ss) m(s) S CTRPO. log L
(13)
with
2 (1lr loo + 1/2 log? [Al) CTRFO.0 == CTRPO. (11 7)
n11 7)3
Proof. Using Proposition E.2, we use the relationship between the total variation distance of a policy æ to the optimal policy Ty and the corresponding difference in their value functions obtainine
2 m-(sss m(s) n11 7) (JAIFO (TprHs 12) L + t=
Σ [| - 1 SES
Σ
MMG (mT.
Therefore, using (12), we get (13).
C.2. Exact algorithm
We now analyze Algorithm 5, where no approximation is made. This algorithm is exact and does not involve any approximation. We provide convergence result for this algorithm in the tabular setting.
Algorithm 5 ExactAlgo
1: Input: M.
2: Initialize: /4g-
3: for k E [K] do
Tmz-1 M 4: Pk = Pk-1 + Sy 1x-1 (P ) 1h-1)
Update population distribution
5: end for
6: Output: J..
Proposition C.3. Suppose that Assumptions 1, 2, and hold. Assume that, for any k ' 0,
T
B& < 7
(14)
Cop.MEG + C2 Crg.M
19

---

Finite-Sample Convergence Bounds for MF-TRPO
with = MFG. Then, the sequence k20 defined in ExactAlge go satisfies
llkk - p. 12 s (1 - TBk) || p4,
(15)
Moreover, the step-sizes Be satisfy
3k = 00,
(16)
km0
we have that the exact algorithm ExactAlgo converges the optimal policy in the tabular setting.
Proof. We focus on the convergence of the sequence μı toward p.,. Recall that μa, is the fixed point (8). From this condition, then have that
M. PT.. Ms (P77.) )ar
We then have that
Pk-1 ux + Bk { [ (P TPu-1 M
112
p-11
(Pie-1
Mk-2 1
1k-1 14 + Bk { {(1e (w (P (Pax-1'
M
N+ (P Te M )M
m1. 1-m))) |
pk Mk-1)
(1 3x) (ux-1 ml,) + Bx { 1 (P (P
}1
Mr (P
=(1 Bx)² *114--1 Hall + 2(1 3x)8r Mh-1 Mas 1
Fuk (
pa=-
Mr (P Tmn M
)M
+ 2 | (P M
-4 (P )
)
M
Applying Assumptions 2, and Corollary E.4, together with Lemma E. the previous equality implies that
|| - p. = [1 3x) (1 (2Cop.MFG 1)33)) R,
PErg.Ml 1| - m.l12
Since 3r satisfy (14), then obtain 15. We see that 15 is contraction inequality. Combining this with (16), it implies that the sequence μa converges to μ., exponentially fast, i.e.,
k Σ j=1
114 - 1.112 $ II (1 - +3,) 11 - -1 S exp - j=1
|1 - 11
The rate of convergence is determined by the step-size Bg. This concludes the proof.
Remark C.4. The exact algorithm ExactAlgo is simplified version of the algorithm consider in this paper. The exact algorithm does not involve any approximation, thus is deterministic. This convergence is in line with deterinistic optimization. In fact, to get precision of e, we need k to be of order
log(Ileo (=) 2Co + C2 Cr M) . if Bg is constant equal to 7 0 such that (14) is verified;
I| - 12.11111/// e exp(1 2Cop.MFG C2 C2 M. if By C/k for certain C such that (14) verified.
We now analyze the convergence of the algorithm with approximation, i.e., Algorithm 2. We consider the following algorithm.
Theorem C.5. Suppose that Assumptions 1 and 2 hold. Assume that, for any k 2
T
Bx < bo = 402 n. C + 2T
for k 2 1,
(17)
20

---

Finite-Sample Convergence Bounds for MF-TRPO
Then, the exact algorithm Exact MF-TRPO converges the optimal policy in the tabular setting. In particular, we have that
1ull2 sexp
r (-
EB33 5=1
Bj
I100
20MP -m-111
log( Lt
(18)
7
L.
with
1- Cop.
CMP.O = 2 ho
Proof. We focus on the convergence of the sequence + Pas with pa as in (8). Denote Tr the output of Exact TRPO(()) at each step. We then have that
A
ui--1 3112
1p 12
1k-1 uxx + Bv
uik-1
Hk--1
M
(P Tyk )m²)
M
1k-1 1x + Bk
|kk-1
1kh-1
+
+
1k-1
P
pk-
M
(P Pua-1 ) M
)am)
P4-1
14. + Bk
lkkz1
142-1
M
2
Fux pk--
)
Bk [1x (P ) M
+
|kh1
1kk-1
1rx
(1 3a) (14=1 11,) + Bx
pkk-1 (
1k-1
(P (P
M
(P The yby
+Bau
|k-1
P P
=(1 Ba)) P111x-11 - 11 11 + 2(1 3x
Ph-1 Mas 14k11
Tuk (
)
M
Mr (P M
+ 3 | (P - M4 (P jad
M
M2
-K-1 (P (P 15
+ 2(1 - 3x
|K--1 Ma, 14-1
P 14-1
+ 8 | (p M - 1k-1
Jun (p
Mx-1
+ 209 (uk-1
paTe ))
M
14-11
P P
M
Mk-1
(P
P - 1xx )P% M
Tug-1 15
Applying Assumptions 2 and Corollary E.4 together with Lemma E. and following the same lines as in the proof
21

---

Finite-Sample Convergence Bounds for MF-TRPO
of Proposition C.3, the previous equality implies that
|
p. 11 - [L - 3x) (1 - 2r)3p) + O2 7.
Erg,M
|| Hall2
+ + 3r)8B
|h-1 phr Mk-1
p
Mk-1 (P
142-1
+ 8
MK-1
(
1k--1
M
- 14-1
P
[k-1
M
1
+ 23 M4-1
(pTte ((i-1) Mk-1 (P
[up-1
MM-1 (P
Fua-1
M
p4 (P )ar
Pi
14k
[LL 84) (1 (1+ (1)-2))33) + O2. C2
Erg.Ml || HAll2
+ +3 - Tx)TT B.T2 +23LTT.
We now proceed in studying the terms T1, T2, and T3.
Using Young's inequality, we get that
1
(Pite ))M² 14-11 (P THa-1) M
T1 S || 14+11 +
Mk-1
2r
1
|| - 1
+
T2,
2r
and, using Lemma E.1 and Corollary E.4,
S 1k-1 (P (P 14 (P)ti)
1
M
(pit.) ) M - 14-1
(P/t) Fun
M
T33
+
lk-1
(Paz-1
2
2
2
1
1
$ C Girg. 1|1k-1 pe 122 + T2
Since T from Assumption 2 and Be satisfies (17), a straightforward computation shows that
(1 3x) (1 + (1 3) + C2 F. Erg.M
- 33 S (1 -
T 2
Moreover, applying Lemma E.I, together with Theorem C.I on the performances of TRPO, we have
T2 I Crgg.M
Σ 2 (s) (-1s) - (
LeES
< Mrgg,M Σ Mk-1 (s) [|TT((11) TH (11))]
LBES
MFG (M 14- 14x- S OErg, 20tRro.0 log(L)
< Merg, (JMFG
Therefore, combining the previous inequalities, we have that
||uk - 1el13 (1
7
2 3x) || 14- + Bx
1 Bx
+
3,8
20 3CErg.CCTRPO.
log(T.)
2
L
< (1
7/2 3x)
T
||
14-113 + 3x
2 + by
CCEg.MCCRPP L
log(L)
(19)
< (1
14113 7 9x || -
log(L)
+ CMF,
2
L
Developping the recursion (19), we obtain
|1 - 11.12 <
II
11 - T 8.) I1 - 1ml123 + OMF
log(L) L)
3,
II (1 (1-1) 36
2
L
5=1
(=j+1
Σ 3i 1110 - 11112 CMRRo log(L)
13 (1 T 31)
exxp
1=1
1=1
8=141
22

---

Fimite-Sample Convergence Bounds for MF-TRPO
Note that the second term of the r.h.s. of the previous inequality is telescopic sum, as the central term be rewritten as
8 II
-1-2
II 1 t=j+1
-0)
II 1I t=j
(1- (
t=j+1
Therefore, get (18).
E-MFNE. With the theoretical foundations established in Theorem C.1 and Theorem C.S, we can now derive a result on the closeness of the proposed algorithm to the MFNE. Specifically, we show that Exact MF MF-TRPO achieves an e-MFNE, where the approximation error is explicitly quantified follows.
Corollary C.6. Suppose that Assumptions I, 2, and 3 hold. Assume that, for any k 2 0, the learning rate By satisfies (17).
Let pa (resp. 1k)1) the output of Exact MF-TRPO (resp. Exact TRPO(p))). Then, (TK-1, pk) is ex-MFNE, with
20Erg V 17(1 (1
ek 6NE,1, Co (1+CErg,,0 Crgg (1 + Ca, v VONE.2.
V (ONELL))
(1111100 + 1/2 log" [Al) log I
ŌNE,1,K = CTRPO,
L
T 2
11 1/40=1x112 + 2CMF. log(L)
ŌNE,2 = exp
B3
T.
Proof. From Proposition E.5, we have that the exploitability of a policy æ and a mean-field parameter can be bound by the gap of optimality of the x w.r.t the value function JMFG (., p1 (s) and the distance between and the stationary distribution Am.
From Theorem C.I, we have that
max MFG (xt, (kk: (k: JMG (ITK. Hkk 146) S 8NE,1,K TEll
(20)
On the other hand, using the fact that (T 14) is MENE, we have
Amatripe (px (wa) + (Aounite Aouyy + (Drugiiu >maat
Pk
Then, applying Lemma E.I, together with Corollary E.4, we obtain
(Asm.. Assee |1 S CEggooo (1 + Crr u llp. mxll2
Moreover, from Theorem C.I on the performances of Exact TRPO, together with Lemma E.1 and Proposition E.2, we have
|| < CBrgo0o
Σ (e((s) (+1s)) Tpp (+1
#ES
2C 2o V
20 20 V
V JMFG (Tex Mky px)
JMGG ( Pki mk)
711 7)
1111 -
Using the triangle inequality, together with Theorem C.5, we can bound |u4 - Amanni 1lz as
|| - Ama-n 12 < (1 + CErg, dc (1 + Cr,z)) || - Mall2 + 20Erg vis)
v VONELL
n11 -7)
2Crrg, v181
(1 Crrg,oo (1 + Cz,z)) / 8NE,22
V VON,II.
1 -
23

---

Fimite-Sample Convergence Bounds for MF-TRPO
Using the last inequality and (20), together with Proposition E.5, have that
((T6+1, S 1N Ci (1+ CEngooo (1+ Ca, v /NE,2, +
B0 S
. VNNE.I
Ek
111 (1)
Therefore, (pk, TK+1) is Ex-MFNE as defined in Definition (2.1).
Remark C.7. From this corollary, it follows directly that to achieve an e-MFNE, the required number of inner policy updates and outer population updates K must satisfy the following scaling conditions:
I. T and K Ke (log((/e))
This implies that the sample complexity of the proposed algorithm scales polynomially in 1/s with respect to the inner optimization steps and logarithmically with respect to the outer mean-field updates. This confirms the efficiency of our approach, ensuring that even for small values of e, convergence to approximate MFNE remains computationally feasible.
D. Model free algorithms
Model-free approaches play a fundamental role in developing model-agnostic algorithms capable of autonomously adapt- ing to diverse and evolving environments. In the MFG context, various models have been proposed across different domains (Perrin et al., 2021; Yardim et al., 2023), and recent efforts have explored data-driven methodologies to enhance their applicability. Following this line of research, we introduce Sample e Based MF MF-TRPO, model-free approach tailored for MFG problems. By leveraging RL techniques with scalable sample-based updates, method contributes to the growing body of work on data-driven MFG solutions, providing finite-sample complexity guarantees in this setting. This framework further aligns MFG with model-free learning paradigms, broadening their potential for real-world deployment in complex decision decision-making environments.
D.I. TRPO sample-based formulation
In the framework established by Shani et al. (2020), it is important to note that the sample-based algorithm does not provide a last-iterate sample complexity guarantee. This contrasts with the exact algorithm, where the policy improvement lemma (Lemma 15, Shani al., 2020) serves as a foundation for analyzing the convergence properties of the last iterate. In the exact update setting, this guarantee analogous to Howard's lemma (Howard, 1960). However, the presence of sampling errors in the sample-based setting hinders the attainment of such guarantees, necessitating more refined approach when designing and analyzing RL algorithms for MFG.
To address this limitation, it becomes essential to consider alternative strategies than Theorem 5 in Shani et al. (2020). This theorem, however, still provides a framework for analyzing the uniform mixture of the policies generated during the iterative procedure, rather than relying solely on the last iterate. By shifting focus to such policy, we can generalize the theoretical guarantees of the algorithm-a property inherent to the MFG setting.
Additionally, the connection between the value function and the policy space plays crucial role. Proposition E.2 ensures that the gap in value functions directly bounds the differences between policies. This property provides a pathway refine the policy improvement process and derive meaningful finite-sample complexity guarantees. By combining these insights, we can propose robust methodology where the sample- based algorithm achieves convergence with high probability, utilizing uniform mixture policies to overcome the challenges posed by the lack of last-iterate guarantees.
Overall, this refinement introduces a smarter utilization of the sample-based algorithm, emphasizing the role of averaging in mitigating the variability and uncertainty inherent in sample-base based methods. This approach not only aligns with the theoretical underpinnings of convex optimization but also strengthens the practical applicability of RL algorithms in MFG, delivering finite-sample complexity results with rigorous probabilistic guarantees.
Remark D.I. For a fixed μ4, the output of Sample- Baseed TRPO(μ) is the uniform mixture policy # UnaE., This policy is such that, in the unregularized case, we have (11). It consists on a mixture of Ω. for f O,... L. The following dedicated subroutine achieve the sampling process in a computationally efficient manner, without performing direct mixture at every decision step.
24

---

Fimite-Sample Convergence Bounds for ME-TRPO
Algorithm Sample-Baser T)PO())
1: Initialize: TT(( (AA) for any E S.
2: Input: e, >> 0, L.
3: for E [L] do
4: S = (). Vs, a, Q Q (8, a) = O, (rs
(AP( Ilo +1 log (IS) logt +11
5:
(1 -)-
Sample Trajectories
6:
Te 2 1-
1 log
Rollout horizon
[A[(IIrI IoR)
7:
porp=10 ,,...,
I.........0 ..do do
8:
Sample 8; (g ()) a, ~ ((A)
Q+c (8:, 02, as, (1) + El= " sind, (PP)) ( [r at, /4) + 17 log (fe(aels)))
9:
# Truncated rollout.
10:
( a:) f Tue ai) (s) + 0x.
(1 aj) t ne Ri) +1
S S (si)
13:
end for
14:
for 8 S do
15:
for a E Ado
((.00
16:
En'ea nels,a")
17:
end for
te(al)) लरीाe tc(al)))
Eored #e(a'ls) करनन Q (s,a") -n log )
19:
end for
end for JUnif, Output: #L
21:
Algorithm 7 Uniform Mniturr
1: Input: (fele-a....--
2: Draw a random variable i (u((fo,,,...))
Output: Az
This policy is defined is to sample from this policy efficiently without explicitly computing arithmetic average the sampling level, particularly in its use within the inner loop of Sample- number of iterations L is fixed beforehand, the procedure begins by drawing random variable uniformly from the set {0, L,.., . LJ. Once i is selected, the sampling step follows the policy fz. This approach ensures that the selected action is drawn a policy a uunif without incurring unnecessary computational overhead during execution.
TRPO(μ). Moroever, given that the
In particular, due the regularization term, have that the following inequality holds:
MFG (tt...p S JMG
(4 Unii, p.
(21)
In the absence of regularization, the objective linear in the occupancy measure, which allows for exact equalities when considering mixtures of policies. However, once the entropic regularization term is introduced, the objective becomes concave in the occupancy measure (see, c.g., Neu al. (2017) for proof). As result, only obtain the previous inequality rather than (11) when averaging over iterates, as in the relation involving the mixture policy.
Theorem D.2 (Based on Theorem 5 in Shani et (2020)). Suppose Assumption 4 holds. e, 0. Let (#e)e2o be the
25

---

Finite-Sample Convergence Bounds for MF-TRPO
sequence generated by Sample e TRPO(W), using
|Al2 (IrIlsc + log (Al) (IS) log 2| + log })
Ie 2
(1-7) 22
trajectories in each iteration and rollout up to time T7 with
1 log (14) (1rrllo + log (A1)
T 7
Then, there exists TRRO,1 > such that for all 2 1, the following holds with probability greater than
8
JMG (T 11) JMFG ( (aLEE. (1)
1
< JMGG (TT)
JMGG (1 L+1
8=0
(22)
(1r1112 + 112² log"
(AI) |A|2 1A12
log L
d y/
S TRRP.11
111 (l. +1
(1 - 7)2
V
Proof. The proof of this result is based the proof of Shani et al. (Theorem 5, 2020). The main difference is that we considering the uniform mixture of the policies generated during the iterative procedure.
Applying Shani et al. (Lemma 19, 2020), we get
1 (JMFG (Tp: (1) - JMFG (#t.):
n){E + 2)
(11
DR(TTN ate) Da(TT AtHHE) (e(T)))tet))
+ 1²(()) 20 + 2)2 + Jhick
(+2)
< d -
{+]
Da(TT)5te) - Da(Tm)teei)) + 27 + 222 + +d
12(L))
f+2 2
with
d Fu (s)
Ie
p. ck
Fu SES
(smx))
Σ
m/l + 2) (IA (s, - 17 (1 + log (t(())s))
aEA
log ( + log (())s (als) (a|s))
[Ir11 + 1 |AA
h(e) -(1 + 8n)
log
1-7
using that h is non-decreasing function. Multiplying both sides by n7( + 2), summing from e - 0 to L, and using the linearity of expectation, we get
(1
MFG M1,)), - JMF (.,,
t=
h2(L)
T ui
(Dr(TT TO) (I+ DD (
+
- (l 2)d
2n(E+ + 2)
t=
L
(L)
1
the <
n.pl DippDDD Da(Ta, To)
+
+ Σ
T(l + 2)
2n + 2)
1=1
t=
(L(
<log |A|
Σ
Σ
nie
2)d
21((E + 2)
26

---

Simite-Sample Convergence Bounds for MF-TRPO
with the occupancy measure dh defined (6), where the second relation holds by the positivity of the Bregman distance, and the third relation by Shani al. (Lemma 28, 2020) for uniformly initialized no.
log |A| + CTRPO,1 n11 7) JJMFG (Tuslt,)) - JMFG (.)) v
(L) log L
L (e + 2)d
+
1
1
8=
Dividing by (L + 1), we obtain
L (JMFG (TT) JMF (Tt. p. kl)
log |A]
h² (L) log
(I. +1) + CRRPO 1/1 -) + (1- (L 1)
Σ
(l + 2)
t=
Plugging in Shani et (Lemma 22 and Lemma 23, 2020), we get that for any (c, 8), if the number of trajectories in the 8-th iteration satisfies
8|,4/2 [Ir1l12 + 1 log" IAI)
(1s)og log 2|A|| + log 7
2
< 7)2
65
and the rollout is performed up to time Tę with
1 log
Te 2 -
||| [1] + log (Al)
then with probability at least 1 - 8,
MPG (T - MFG (Tre, ,1, v,)
L
log |A|
(T) log I. + CTRPO,1 711 - (L++)) 1)
1
Σ 2=0
nlé + 2)d 2)d Micce
CTRPO.1 y)-
d
u.p
(1 1)
(1->)
TV
where we used Assumption bound the last term. Thus, combining this with (21), we obtain that
MFG (T M4 (1) J MFG
(TT Uniffft
s...) p.)
MFG (T p1) MFG (.))
(11r11 + 17² log² (A]) AAl log
c
< CTRPO,1
+
711 - (
(1-
D.2. Initialization step in the sample-based algorithm
The initialization step of the Sample- Based MF MF-TRPO algorithm presents particular challenges due the limited operations allowed, specifically the reset and action operations, described in Section 2. During each iteration of the algorithm, the initial state must be sampled from the distribution Ak-1-
As detailed in Section 5, the distribution update in the algorithm follows the iterative rule:
fu +- Pk-1 + Bx (āe PM-1).
27

---

Fimite-Sample Convergence Bounds for MF-TRPO
where & is the output of single iteration of the Sample Based ME-TRPO algorithm. Consequently, at iteration k, the distribution ů is an estimator of
R-1 I - 3,)
k-1
Σ t=1
Be
II (1
33)0 (Ptt)²
(p
j=(+1
since the update Če at iteration é of Cample-BBasee MF MF-TRPO, is an unbiased estimator of the product distribution
v(P (P ... (P )M.
To correctly initialize the environment to state such that 8 ~ fux the following subroutine applied:
1. Sampling a Level. Define the categorical random variable Cat, that takes value in the discrete space {0, L..... k with probabilities given by
II (1 83), 31 II (1 Bac), Bk.
4=2
i.e.
PP (Cat:: = =Be
II (1 3z)
j==++1
2. Selecting a Level. Draw a sample ~ Cala-
init 3. Rollout Procedure, Starting from an initial state sampled as So,p.k ~ v, execute a rollout of the Markov transition kernels up level ?, having i be the particle approximation of ( ... (P&
D.3. Sample based algorithm and High Probability Estimates
Transitioning from exact computations to sample-based setting, we introduce estimators for the key quantities involved in the learning process. These estimators leverage sampled trajectories to approximate the necessary expectations while maintaining computational efficiency.
To ensure the reliability of these approximations, we establish high-probabilit error bounds by leveraging concentration inequalities. This allows us to rigorously assess the performance of the algorithm, providing quantitative guarantees on the estimation error and its impact on the overall convergence rate. Through this probabilistic framework, we ensure that the sample-base based algorithm retains stability and efficiency despite the inherent stochasticity.
28

---

Finite-Sample Convergence Bounds for MF-TRPO
Algorithm 8 Sample-Bases MF-TRPO
Input: K.
2: Initialize: Initial policy no(-|s) (AA,, for any 8. Initial distribution po V.
3: for & [K] do
4: #r <-Sample-Based (RPO
Update of the policy.
5: p [P] do
6: Cate
# Sampling level.
7: Sample SU.p.k ~
8:
for L E [
do
9:
for m E [M] do Sample ginit (P.
- Dee (1 Rollout from the MDP for level E.
11: end for
12: end for
13: Initialize 80,p.
init
# Initialization.
EM..p.'
14: for m E [M] do
Sample Sm.p.k ~ EnEA P(-(mm-1.pd a, tux (al(aalm mpp)) k.kk end for CR.P t ((sM)))))).
Rollout from the MDP.
18:
end for
19:
EA Ep== St.p.
Ab + -- Bk (Sx 1
# Update population distribution.
21:
end for Output: μ..
22:
Examining the Sample learning process. First, the policy update is performed through Sample-Based TRPO, whose finite-sample analysis in high probability established in Theorem D.2. This result ensures that the policy iterates remain well-controlled throughout the optimization process in high probability. Secondly, in order to analyze the evolution of the mean-field population distribution, we need to establish similar high-probability bound on the estimation of the term شمع (P } which represents the transition dynamics under the estimated policy.
Sample-Based Based MF- TRPO algorithm, we observe that two key approximations are introduced in the
The unbiased estimator of this term uses the trajectories {sm.p,A-1) M and is given by the empirical sum of Št.p ( (-). Note that each component of this vector is distributed according to a Bernoulli distribution and centered in fu-11 (Pfa pe_,)" )M Therefore, define e the following martingale difference term
1 Ek P
Ship Pux-1 R
Px-1
with SM.p.k-1 defined as in Sample- Based MF TRPO.
To address this, we first derive Proposition D.3, which a preliminary concentration result that quantifies the approximation error in the estimation of this key quantity. The first one Proposition D.3, which provides guarantees on the deviation of the error incurred in single iteration of the algorithm, with high probability. Specifically, it establishes that the error made while estimating the error each iteration, which is bounded increment of a martingale. This result is pivotal, it ensures that the emrors introduced in each iteration of the algorithm controlled and do not diverge as the algorithm progresses, and lays the foundation for rigorous convergence analysis of Sample -Baled ME-TRPO.
Proposition D.3. For any and if the number of trajectories in the k-th iteration satisfies:
64
2
P>
log
2
8
then, with probability at least 1 8. the following holds:
|k0e 6.
29

---

Finite-Sample Convergence Bounds for MF-TRPO
Proof. From previous consideration, have that ČR is unbiased and eg is martingale difference. Moreover, note that Sh.p l (P JM is a bounded vectore, i.e.
|ikp P (P Aa-1 )m1 11
2 St.p Pk-1 (P (P (
2 (kip(s) -ix-1 (Pix- (M(
Σ WES
(k + Σ
Pk-1 (P hx MM)) = 4.
SES
Moreover, using Jenses's inequality, we have that
P
|kxl|2
Σ Sn.
ju- (P )M
S
1 P
Stap ii=-1 (P Me- p 1, 4.
P
Therefore, eg is bounded martingale difference. show that the increment is bounded with high probability, we use Hoeffding's 's inequality, Let Ex
Eper ck.p. where Ek,Y Sk.p - ----11 (P/t )M Then, for any ty 0, we have
P Σ Σ
1
(ptt An- ) M
)
(M)))) 2 (xp(() - fik-1 (Pft Px-1
P
Σ
ch.p
P
+ES
p=0
Pe. 64
2xxp
8.
This consideration is a special case of the Generalized Freedman inequality presented in Harvey et al. (2019). The inequality provides sharp high-probability bounds for the sum of bounded, dependent random variables. In our case, the formulation is simplified due to the presence of a uniform bound on the variables we aim to control.
Therefore, in order to guarantee that
P
(pet
)
)
M
4
(p tx
Pc-1) ))am
6k
Px-1
<
P
Ek.p
pix-1
p=0
Se,
we need the number of trajectories to be least
64
2
P
log
D.4. Convergence of Sample-Based MF- ME-TRPO
We now extend the exact analysis of Exact ME-TRPO to its sample-based counterpart, establishing global sample complexity bounds. While the exact algorithm benefits from having full knowledge of the transition kernel and reward function, the sample-based version introduces additional approximation errors due to finite sampling. We quantify these errors and derive high-brrobbbiliyy guarantees on the convergence of the algorithm. This requires adapting the theoretical tools developed in the exact setting to account for trajectory-bart based estimations and ensuring that the resulting policy updates remain stable despite stochastic approximations.
Theorem D.4. Suppose that Assumptions
and 4 hold. Assume that the following holds
Bk < b
for k > 1.
(23)
6C2 602,, Cr Ce
+ 27
For any e > and > 0, if the number of trajectories in each iteration for Samp e Based MF-TRPO satisfies
64
2
P>
log
(24)
30

---

Finite-Sample Convergence Bounds for MF-TRPO
and the number of iteration in each epoch of Sample Sampple-Basee Based TRPO satisfies
Te |4/2 (1|r + log² |Al) (IS) log 2|A + log 3)
(25)
and the rollout is performed up to time Te with
1 log
(14) (111 + + 1og 141)
Te 2 1 -
(26)
Then, with probability at least
8, we have that
1 m=12 S exp
Sexp
1140 1el2 - B3
I
20MFF log(L)
2CMF
(27)
L
with
T:= 1 - Cop.MFG
2 bj
CMP.1 = CErg.M . CTRPO.
CME = 2 (CErg. OTRPO.2 + 1)
20
(1r112 + 172 log 1A)
[A|2 log L
CTRPO,1 171 ()
17(1 7)3 L
20 20'IRPO.11
1
J u.u
CTRPO,2 111
71)
71
with CTRPO,1 the constant coming from Theorem D.2.
Proof. We focus on the convergence the sequence Pys + μ., with μa, as in (8). Denote â (resp. ? the output of Cample-Basee TRPO( each step (resp. the estimator used in the update of fux Sample-Bases MF-TRPO).
31

---

Finite-Sample Convergence Bounds for ME-TRPO
We then have that
Ag Hol12
Ak-1 Mr, 3x (Cx
p
1
M 1r 8k
(p/8x 11--
+ Bk
(iss-1
M i
Ak- Mx 3k
Ek p
(pft
Ax--1)
+Bx
A
p Rx
M
1 (p
TAk Pa-1
1) M
Pv-1
pk-1 P MAR-1
M
2
+
(pft .)* M
))M)
Pk 1 Mr 3k
( P/
-in-1 (P (p( 15
+Bx
P TAp-) M
f Br (1en (P oM- - 1111)
+ +Bk
(Ax pax-1 (ptr. (hh..)
M
(1 Bk) (Ak-1 (4)) + Bx
+
PC-1
tu
Ac-1
+Bx iix- (p) Mx-1
M
- pa (P 1u
)av)
=(1 - 3x)² 1ix--1 1
1s
+ 2(1 3x) < (ik-1 p1x Ee iu-1
(D& AM
áe - (pts (
+ 8
+ 23
(a- Px-1
(p (n-1)
fix-1
(pA (k-11) ) fix11 (P
Ak-1
max-1
+ +238
Eo - م
(p Ae-.)
(p m
)
Me (P )dr
A
+ 2(1
3k)3s (Wa-1
Mha Pix-1
(P
Pa-1
Me (PT.. )ar
+ 32
ii-- (P R
M T
1xx (Pit.. M
+ 2(1 Bx) (in-1 Me. fik-1
(p= mpp-2))
Pc-1
+ 82
| (pfc..) M - fux-1
)M
(p
Apc-s
31 12
Px-1
+ 288 (ia-1 (pfte ))M fik-1
(
(p
Fie-1
3
(p (p
Tit-1) M 14 (P yM
fix-1
Rx
Applying Assumptions 2 and Corollary E.4 together with Lemma E. and following the same lines as in the proof
32

---

Fimite-Sample Convergence Bounds for MF-TRPO
of Proposition C.3, the previous equality implies that
A ps 112 - [11- (001--x)1 3x) (1 (2Cop.MFG- - 1))a)) + BRO n. Beg,Mal 11Āx-1 - 14
(in-1 - - ii--1 (P
+ + - -3
Pxx
+ 8
& Pk-1 (PtL..,
2
+ 2
& - Px-1
(ptte
M
(ptt (i--1)
M
- -x--1 (P ix-1
M
Pk-1)
+ +238
(4 - Px-1 (ptu (e-1)
M
P
(p (
) 25
- Mr (P )mv
M
(k-1
+ +2(1 3x)3k (DA-11 ph P
(pte M
(P
kax-1 M Fix--
ik--1)
P
+ 88
AA-1 (pth ,)(H M
-ix-1
(p
Thk--1
M
2
+ 2,38 ( (pft ) M - 1ix-- (p Aa-1
1) M
.ik=11 (ptin, 1)²²² M
- Mx (P M
An-1
=: [1(1 - 8x) (1 + (2Cop. 1)8k) + BR,.2,
Ja Beeg,al 1 -14-1-11112 14x11
+ 23 - B, B2 + +,3 2
+ 23 - 3x)TT + STT2 + 25/TT
We now proceed in studying the terms Ej, Ez, Eg. E4, Tí, T2, and T3. Using Young's inequality, we get that
1
E1 S | - 11 + &e i (Pit..)
S
l
- 1all
E2,
4
2
Egl S
i (p Ax
)m² i
- (p
Tpp
M
1
&t i
15
||2
T2
E2
Ps--
2
2
2
Px=1 (P (pae-)) )M--))---)
- Mr (P/ )ar
M
1
M |
E, <
Px-1
< 0
2 x C 11 - 11
E2
2
where we used Lemma E. and Corollary E.4 in the last inequality. Using Young's inequality, we get that
T 1
T |10k-1 11 +
1
ii-- (ptt pp-.)
)M
M -
-i (P
Ap
Ax-1
)
1 T
1i
+
1 T2
4
2
4
T3l S
2
1
i (p P 1) W0
- 14 (p#t. d5 22
+
2
1
(p
Mi
)
M
- fkk-1
Px-1
31
2
2
1 02
Tiog. 1ipx-1 ph + +TT22 T2,
2
where we used Lemma E. and Corollary E.4 in the last inequality. Since from Assumption 2 and 3r satisfies (23). straightforward computation shows that
(1- (1+ (1-1117)000 B)x)) + 388 Cr < T -
33

---

Finite-Sample Convergence Bounds for MF-TRPO
Since have that (25) holds, we can apply Theorem D.2, together with Lemma E. get that
T2 v CRrg,M
Σ i 1 (8)
(-1s) The .(1s)]T
S CBrR,
Pk- (s) [ Mpe- (11s)
LEE
I CRRR, (JALFG (T 1: Px Px- JMNG (#x Pu-1, Pu-1))
I CErg,M 77(1 ()
2
CTRPO,1 L
log(L) + CIRPO22)
Moreover, since (24) holds, using Proposition D.3, we have that, with probability at least 1 - 6,
E2 S E.
Therefore, combining the previous inequalities, we have that
A - |r 1
T 3/s) 11 - 11 11
$
2
2(1 - -Ba) 3,3x)
Log(L) I.
+ Bh
CRRR.
OTRPO,1
+ CTRRO.22 é +
(28)
T
B/b)
|| + 11.12 1 + 3x + bj
CErg.M (TRPO,1
log(L)
+ CTRPO,2 e te
2
L
2
T
|| - 14, 11 + 3x CMF,1
log(L)
BN CMF, c.
Developping the recursion (28), we obtain
A:
11112 - II (1
7 3;3) 1110 11-12
j=1
+
CMP,2
log(T.) L
+ By CMF c
Σ
B3
II
k
(1
T 2
5=1
E=j+1
I exp
Σ Bi
||H0 -nall2
2
CMP.1
log(L)
By CMF
Σ
B II (1 _1,) (=j+1
k
L
Note that the second term of the r.h.s. of the previous inequality is a telescopic sum, as the central term can be rewritten as
k B II 1 - 33) = II
(1 - 31)
- -1- F.)
f=1+1
[=j+1
[=j
Therefore, we get (18). Moreover, since 8g satisfy (14), this concludes the proof.
D.5. M-NNEE
We aim to characterize the proximity of an approximate Nash equilibrium, specifically an e-Nash equilibrium. In this context, we address two key questions:
34

---

Finite-Sample Convergence Bounds for MF-TRPO
1. Given fixed budget K of sampled trajectories, how close the value function to the unique Nash equilibrium?
2. Given a target approximation level E, how many trajectories K are required to achieve an e-Nash equilibrium?
These questions are crucial for understanding the sample complexity of learning equilibria in mean-field soun-field settings and provide insights into the efficiency of our algorithmic approach.
Corollary D.5. Suppose that Assumptions I, 2, 3, and hold. Fix 6, 0. Assume that, for any k 2 0, the learning rate By. satisfies (23), and let P be the number of trajectories in each iteration for Sample-Based ME-T satisfying (24). Let
Pyg (resp. (i the output of Sample-Bases MF-TRPO (resp. of Sample-Basen TRPO(())) Then, we have
the following bound on the exploitability
o( Unitiik ,x) S
with
(1 + CErgo (1 + Cnaai)) V VONE2.* +
20Frg vi8
6x 6,E, + Cs
V 6NE,,,K
17(1 [)
[Ir|122 + 172 log² (A1) |A|2 log L
ÔNE. = CTRPO,1
sup NEP(S)
1)(1 - () +1
(1 (1-7)²
v
11 - 1-111 + 20MF, log(L) (L) 3
20MF.2
NN = exp exp
L
Proof. From Proposition E.5, we have that the exploitability of policy and mean-field parameter can be bound by the gap of optimality of the æ w.r.t. the value function JMFG (-, (, n1) and the distance between μ and the stationary distribution Am,ju-
From Theorem D.2, we have that
MRG (Tt, fake Ax) - JEG (# (AUNTT-RK (x)) S 8NE,1.
max xell
(29)
On the other hand, using the fact that (Tu, is MENE, we have
X An faa. = =ip+ - 14a) 14a) + (Dopuitte d + (Arogiee Napperinn .nn)
for é = o...., L. As in proof of Corollary C.6, we have
| Xxpe 112 S CErg (1 + Crrtee Clm Puall22
Moreover,
|amen Ai Aepaside pm 11, S org,
Σ (s()s)
ApniT,P (-1s) Tee (-s))-
AL
20 Visi
JMFG (T Pu, Pa)) JMFG uniif fuk Pas)
11(1 -?)
20Frg000 V S
V JON,
711 7)
Using the triangle inequality, together with Theorem D.2, we can bound | > Agnarri Pa as
A Aane an 11 < (1 + CErg, (1 + Cz.H)) l|p.. - Aull2 + 2CErg VSSI
V
171 -7)
(1 + Cerg,oo (1 Cr,H)) / 8NE,2K + 20Frg,oo V18T
v V
111 77)
35

---

Fimite-Sample Convergence Bounds for MF-TRPO
Using the last inequality and (20), together with Proposition E.5, have that d( ( (bx) S Ek
Remark D.6. It is important to note that our analysis does not directly bound the exploitability of the last iterate but on the uniform mixture of policies over the learning process. This distinction arises due to the absence of an exact counterpart to Howard's theorem (Howard, 1960) in Sample Cample-Based TRPO, as noted in Appendix D.I. Unlike Exact TRPO, where policy improvement guarantees can be established step by step, sampling errors introduce additional variability that prevents such guarantees in the sample-based setting.
Despite this limitation, our results demonstrate that the learned policies perform well average and that approximate the MFNE accordingly. The bounded average exploitability ensures that, over time, the algorithm remains close to an equilibrium, reinforcing the practical effectiveness of the proposed approach in large-scale multi-agent learning.
Remark D.7. From the obtained sample complexity result, it follows directly that to achieve s-MFNE, the required number of inner policy updates L and outer population updates K must satisfy the following scaling conditions:
L E ((166²) and K E (log((//2))
In addition to these requirements, we also establish that the number of episodes P and the number of iterations per policy update/ l/ must satisfy
P,I. E Õ(1/64).
These additional conditions ensure that the variance introduced by the sampling procedure remains controlled, allowing for a sufficiently accurate estimation of the value function and policy updates. This highlights the tradeoff between computational efficiency and precision in approximating the MFNE, showing that our algorithm achieves well-balanced complexity while ensuring convergence guarantees.
At each iteration of Sample -aanle MF MF-TRPO, the total number of calls to the enviromment consists of those re- quired by the Sample-Based TRPO procedure plus the additional subroutine for updating the mean-field parameter. Sample-Based TRPO requires O(1/E") environment calls, scaling proportionally to the product T. x Te- This aligns with Shani et al. (2020); however, we highlight a distinction stemming from the chosen metrics: the metric they use corresponds the square root of our exploitability measure, introducing cubic dependency in terms of Additionally, the total complexity includes multiplicative factor K, whose contribution is negligible in practice due its logarithmic scaling, preserving overall algorithmic efficiency.
On the other hand, in each iteration of Samp Baseed MF-TRPO, the update step for the mean-field distribution scales as Ö(Px x I x K), which means ((1=²²) calls to the MF-MDP. This complexity arises naturally from the oracle assumption adopted, which involves an initialization step at each iteration potentially requiring up to K steps to accurately initialize the mean-field distribution. While introducing additional complexity, this initialization procedure crucial for maintaining consistency across iterative population updates, thereby ensuring the stability and convergence accuracy of the algorithm towards the mean-field Nash equilibrium.
Combining these two contributions, we obtain an overall complexity that scales as Ō(1/="), consistent with established convergence rates in the RI. literature.
E. Technical Lemmata
E.1. Lipschitzness of the Markov reward process iterates
We show in this section that Assumption implies the existence of Lipschitz constant for the operator X and (P for any j P(S) and M 2 0.
Lemma F.1. Suppose Assumptions and holds. Fix M 2 0 (resp. M oo). Then, there exists a constant Cerg 2
36

---

Finite-Sample Convergence Bounds for MF-TRPO
such that
(Pz) M4
- -P()
a5
Σ E(s) [|((||s) =-1s- + 111e 14
TV
SES
Eeg
sup [|[(s]) x (((1s)]] + 111-- r'll2)
+ES
(30)
(resp. [| Aw Sorgoo
Σ {(s) || n' (-15) + 1110 1 1/112
AES
S CErgooo
sup [|/p|/((1s)) - n (+1+))l E(x) + llee 1² )
with
M
CErg Lp
CE =Frg Lp
(resp. Cergooo
for n. n' E and μ. μ² E P(S).
Proof. This proof adapted from Fort et al. (Lemma 4.2, 2011) on parametrized Markov chains.
Step Consider first M < oc. By employing telescoping sum, we obtain
(p*) M
(pxx (P:)-((P))
-(P)z)
= Σ
M-11
P
M-m-1
( - Pm-Px) (P:z)
m==
Consider function wh: S + R+ with |/ I 1. Therefore, since P P is a difference of probabilities, we have that
M
(s) - [<(P>t) M
g PT
2 (s)
SES
(31)
Σ
ΣΣ> m== S'ES
5
(
M-m-1
m -px) ((PF)"(( (s',s))(ss - - (r)))
This due to the fact that whenever we evaluate the previous difference of probabilities matrices on vh the term Eves ue (s) is perceived constant by the transition kernels P and px', summing this part to zero.
Define om: S + R4
Om (s) = Σ
(p=
( - P
(s,
m Σ ((P"))"("'"" (6''"")(("") - )x( E"ES
S'ES
From Assumption 3, we have that
(Pxx) m (8',8")(('"") (m S CErg!" 1
(32)
Therefore, we have
[dm( < sup sES
(s))s - -P (s, CErgP" bbllo
and, applying Assumption 1, we get
[o(s) < Le (1]((-1)) n' m'(+)))l + 11 n'llz) CErgp" 1
37

---

Simite-Sample Convergence Bounds for MF-TRPO
for any o' E S. Combining this with (31), we get, from the characterization of the total variation norm of the integral with respect the positive functions bounded in sup-norm by that
[s(7)
M as - <(px))
SLp
M-1
Σ
P
Σ SES
E (P:)
M-m-1
([](+|s) x (((1s)][TV + 11e r 12)12)
TV
M-1
1
Lp CErg
m
{(s) (1](--s) - x (+s))lT + 11 m2ll2)
m=0
NES
1 PM
<pp CErg 1-p P
Σ - (+1+s)] + 1111e p'll2
WES
M
Spp CErg
sup [| -- (-1+s)]T + l1 - μ²
1
where we have used the fact that P. stochastic matrix, thus its biggest eigenvalue I and & is a vector just positive components.
Step 2. Consider now the ergodic distributions. Fix M 2 1. From triangle inequality, have M/ TV
M (PT)
+ =(((;)) -1pp))((pppp)) -(pp) (I + [((p;) M
-Dor -
D A 1| S Ao.
TV
TV
From Assumption 3 together with Step 1, obtain
1 pM ((s) x (+1)l + 11 v' n'llaa + Oregu
D Avi Arwwlly llav S Crergt
+ Lp CFrg
1 1 P
lES
Lp OBig
Σ E(s) [|[(-1)) 7 ('(1s)]] + 111ue- n'lla) + CReApa
- p
Lp CErg
S Cregg" M
+ 1 1
sup [| - - (11+8)] + lle v(ll2) + Craup"
As this is true for any M 1, taking M to infinity, from Fatou's lemma we get (30).
E.2. From bound on Value function to bounds on Policy
In this section, we demonstrate how a bound on the value function naturally leads to a corresponding bound on the policies. In the seminal work by Shani et al. (2020), an ((1/N) bound was established for the cost functions. This result can be extended to derive bound on the distance between policies by leveraging the properties of regularization. The connection between the value function and policies highlights the role of regularization in maintaining both theoretical guarantees and practical performance stability.
Indeed, from the entropic regularization, the optimization problem (3) with respect to the profile admits a unique solution TT. These considerations form the foundation of the following proposition.
Proposition E.2. We have that
[|[[(= - T. (110)))) S 17(1 7)
(TM H4 su) MFG MM (T.
(33)
for any so S.
Proof. Denote Ω the entropic regularization tem in the reward function (2) as function of the occupation measure, iee.
Ω (d = Σ (og(((()))
aEA,
38

---

Fimite-Sample Convergence Bounds for MF-TRPO
with d, in 5. Therefore, express JMFG
JMF [1,
E (1) (a, + 1122 (dā
(34)
a.A,
Taking the disentegration the spatial component, have the following relationship between the occupation measure and its marginal
(s, Σn (als) (st s/so ~ 8111 a(,)st,,,11))
(35)
1=
= (als)) (s))
with di in 6. This also implies that
Ω (d
Σ
L a) log(T(als))= =
Σ
(a|s)) log(<(als)) (s)
(36)
aEA,,ES
aEA,,ES
From (34), as the optimal value does not depend on the initial condition, we have that the optimal policy TH of the previous optimization problem satisfies
JFG (T Me so) 0
for any S. Combining this with (35), we obtain that the previous condition equivalent to
r (s, G. (u) = V/ (d (s, a)
for any a E so E S. We recall that the Bregman divergence Dn with respect the regularization is defined as follows Da(ull//) ((v)) (Vv) - V
(v (v- for v.v AxS.
Therefore,
JMG (T, (T, 14,
JMEG (1,
Σ
(s,,,,1) (d
d (s, a) + 1752 (d% 1782 (d
(s,0)ESXA
(37)
Σ
V2 (d (s, (d - d (s, + n/02 (d - -7/5 (d
=n
(x.))ESxA
= 17 Do (d 80.01
However, we have that with the Bregman divergence corresponding to the entropy regularization Ω has the following expression (see, e.g., Neu et al., 2017)
(aass)
Do 1.n.ulldaii
= Σ
d
(8, a) a log
[a(a)s)
(a,))SxxA
(als)
Σ
d a
T(als) log
M.50
TT(aas))
aEA
(s)
KL
p.50
Moreover, from the definition of d, extracting the first term of the series, we obtain
Th (s) =(1
7 (s: =))
1=0
=(1 - 70000p (s) + (1 (1-7)
(Pp =
=(1 -1- -000) (s) (1 7)7
'pp (8141 s)
39

---

Fimite-Sample Convergence Bounds for MF-TRPO
Using the decomposition of P (5(41 8)
Pp ($141 s)
Σ
P(84+1 = 5/5t = =s.aa = p = ( =
(d)a))ESxA
Σ
'' = 5s =d))
(s',0))ESxA
we get
d (s) (s) -(1 - -00 +7
Σ
P(s)s', s' m)(1 7) Σ 7 (p -.,0= d')
(dTa'))SSA
=(1 - (s) +7
Σ
P(s]s', a', pdd p
(8a)))SXA
Therefore, for a function vb + 10, we have
Σ SSS
(s) m.50 (s) = (1 - >))b(()) +y
Σ
Σ (ssss w.)
(0 (eE
2 (1 - (1-7))($0)
since sb is a positive function and d% is positive measure. Applying this to the positive function 8 + [[] together with Pinsker's inequality (see, e,g. Cover, 1999), we have
Da (d sa.u |
2 (1 - 7)KLL (T
1 7 |[<(a|s)) (al(as)))l
2
Combining this with (37), we get (33).
Proposition E.3. Suppose Assumption / holds. Then, we have for any two 1a. p that
Ty + - Lp (1)
+ n nlog [A))
MFG (T U4 80) - MMG (TW S
||0 1 1/12
(38)
1 1-7
and
L, + 7 Lp (11r + m log (Al)
JMG (x,, S0) JMFG JMMG 1
I-g
=11 11' 112
(39)
1 1-7
for any 80 S and any E II.
Proof. Step 1. Let us state the optimal Bellman equations
(s, r(8,, + 7 Σ (( JMG (T,
e'ES
JMG (mp:11 = nloog
Σ PaE
- o7 (0.00)
exp
We notice that function 17 log EE + (::)) is 1-Lipschitz in norm since the -noor of the gradient of this function always lies on a probability simplex (see, e.g., Geist et al., 2019). Thus, we have
MFG (T So) - MMG JMFG My, so) & max Q7 (su. .) Qa (su, )) .E
40

---

Fimite-Sample Convergence Bounds for MF-TRPO
Then, study the Lipschitzness of optimal Q-values for arbitrary action ag E A
QTH (s0, ao) - 0 (00: no) - Ir (80, oo, 11) -r (s0: a0, a0,
Σ
P (s'1ss,, (s,, co, ui - Ps (s'1so, ao [()) MMG (T He,
+7
c'ES
( |s, k/) ( (Tus - JMFG [' Σ
7
s'ES
By Assumption 1, we have
Ir (50, ao, pi) (00,
an. 1()1 La 11 p'1l2 [P
a00 no, p2) P( on, "0.11') Lp ll ll2
thus
(70 ao) - -277' (so: ao)l s (Irr + yTop || (Tp: Me 1loo) ll 1'll2
+ MFC JMF (TT - JMGG J H :lloo
Overall, we have a recursive bound on difference between value functions
|M (T - J MFG (TT uL, :llo0 S (Ir + +Thp [| (T ni -llooo) -11ee w
+ 7 [ (IT)) JMFG (Tp' pL, :)looo
therefore
Th + Tlop | (Tp: My Iooe 1| u'll2
M| (T u4, - MFG (Twe M :1) S
1-7
By bound MM (TTp Ml AIoo (l n log AA))((1 - 7), conclude the statement (38).
Step 2. Applying directly the Bellman equation, we have
JJMPO((T (T, 80) J MFG (T,, u², so)) T(ooloo) Ir (so, ao, ao, (so. ao n')l
A
Σ T()))00)
Σ 3'ES
[P (8'180 ao. ao.1)) - (s'180: ao, n²)) JMG (T 8')
+
AgEA
To))ls))
Σ
P(' (islss,, (o.
( JMFG (TT' [t'
s'ES
Following the same lines as in the Step 1, we can then obtain (39).
Corollary E.4. Suppose Assumption holds. Then, we have for any two μ, μl' that
sup (+1s) SES
Tw (+bs)) S Czr, 1| 11l12
(40)
with
4
Lr + - Lp (1rll n log (Al)
Cn,,u == n1( 77)
1-7

---

Fimite-Sample Convergence Bounds for MF-TRPO
Proof. From E.2, have that
(+|s0))
T (=((ss))liiv
2
(JMBC (4, JMPG
$ 171 7)
2
(Tus (J
JMFG (TT,, 80) + JMFG , - JMFG (w,,H,880))
771 7)
Then, applying twice Proposition E.3, we obtain (40).
E.3. Bound on the Exploitability
To analyze the exploitability & of given policy π and a given mean-field parameter μ. we decompose it into two key contributions. The first term captures the suboptimality of the best response against the mean-field distribution, quantifying how much an agent can improve its reward by deviating optimally. The second term accounts for the discrepancy between the current population distribution and the stationary distribution of the Markov reward process induced by ( 1t). This decomposition allows us explicitly bound the exploitability by controlling both the policy's 's optimality and the convergence of the population dynamics to equilibrium.
Proposition E.5. Fix a policy π E TI and two mean-field parameter μa E P(S). Then, we have that the exploitability & as defined in (7) bounded by
Φ( (u) S [max MPG (T) - JMFG (T,, ()) + Co 1e - 1ll2
x¹
with
C = Lr + I-g Lp (11 + 1 1lo [Al)
||r + 17 1)ggg((AA) + 22 |S|
(41)
1-7
Proof. Fix a policy π E 11 and two mean-field parameter p.p E P(S). Then, we have that JMF (IT, p1,1)) MJM (4) JMG (I,, .1) + (JMFG (z, 14) JMFG (z, JMFG (x.)//11))
On the one hand, from Proposition E.3, we have that
L, + 1- Lp (11rlloo + ry log [Al)
JFG (T, - J
(T, JMFG
-11e 1 112
1 1-7
On the other hand, we have that
MFG (T, 1T. > (o)
8E8
and similar decomposition applies for JMF (TT, ,()). This means that
MMG (T, pp, p)) M pl' ,1,1) S MFG (a. (')p's lp'(s) -m(s)
||r llae
+ mlg(((A4))
Σ (n'(s) - p(s)
<
1-7
SES
||r loo + 17 (og(
S S
|| pll2
where we have applied Cauchy-Schward inequality the last bound. Therefore, we can bound the exploitability & as defined in (7)
((T,1) max J(T', An, dr,)) - [ Ao, d=ar)) x'ell
S max J( μ. 1)) J [TT M., 11) Co |R 14/12 r'ell
42

---

Fimite-Sample Convergence Bounds for MF-TRPO
E.4. Discussion the monotonicity of the optimal Markov Kernel
Define the operator PM as (M(()) := (PT*)) M In this section, we outline sufficient conditions under which this operator, responsible for updating the population distribution in the MFG framework, exhibits monotonicity. Monotonicity of PM is crucial property that ensures stability and convergence of the iterative updates toward the Nash equilibrium.
This operator represents a generalization the standard contractivity condition, which traditionally formulated with M This generalization motivated by the fact that, as we aim at studying the regularized ergodic MFG problem (2)-(3), the condition can hold for some M 1.
This contractivity condition reflects the combined effect of the Lipschitz continuity of the regularized best response n and the ergodicity of the Markov reward process P ensuring the stability and convergence of the mean-field population updates in the ergodic setting.
Lemma E.6 (Strong monotonicity of PM). Suppose that Assumptions and 3 hold. We have for all distribution measures and pl
(Pa(4')-PMa(a (00ld--PMlll PN)(1), p) S Cop.MFG l| 1l12
with
CoP.MEG CErg Top 1 1 + Cz.Ne) + Cergp"
Proof. Consider the following decomposition
M - W (,PM((()) (p))(m)) (ui n, ((Px)))((pP))) - )"1)
(ppp))
(m (e' -w) -w) (P..))) 15
)m))
On one hand, applying Lemma E.1 and Seuuchy-Schaare inequality, obtain
n/' u.
(p M
(p
M
(pxx)) M - (p
11p1 mll2
TV
$ 1|p² - Mll2 CergLp 1- 1
sup || - 1
(-1s))) + +11 - 1121
1 - p
lEES
1-pa
<Crrg Top 1 (1 + Cr,) || 11'122
where in the last inequality we have applied Corollary (E.4). On the other hand, from Assumption 3, we get that
4' ( ( u. (4' (ou'-H))pp) (P M
$ 11kl - 1/11 | - (P(()))))
M
(
TV
< 11 - w/h (1u(e2z)) M
+ | -
uf )Pxx)) N )
TV
11 1ll1
2CErggM
<2 S CEeRp M I| 11122
The condition MFG < 1 is satisfied when the Lipschitz constant Lp associated with the transition kernel is sufficiently small, and the exponent M is large enough.
43

---

Finite-Sample Convergence Bounds for MF-TRPO
Intuitively, a smaller Lp indicates that the transition dynamics of the MDP are less sensitive to changes in the population distribution, reducing the potential for instability. A regularity condition on Σp is standard assumption in the literature ensure the uniqueness of the MFNE. Similar assumptions have been employed in various works, including Becherer & Hesse (2024), Espinosa & Touzi (2015), Lacker & Zariphopoulou (2019), and Tangpi & Zhou (2024), among many others. These studies leverage regularity constraints to prevent degeneracies in equilibrium selection and to guarantee well-posedness in the associated fixed-point problems.
Meanwhile, a larger M amplifies the effect of the contraction over multiple iterations of the operator, ensuring convergence even in cases where individual updates are not strongly contractive. This interplay between Lp and M highlights the importance of balancing the model's inherent dynamics with the structural assumptions to guarantee monotonicity and stability in the population updates.
F. Additional Experiments
We present results for the Exact MF-TRPO algorithm on two extensions of the Crowd Modeling game and we benchmark our results against Ficticious Play (FP) (Perrin et al., 2020) and Online Mirror Descent (OMD) (Pérolat et al., 2022). Our findings demonstrate that the exact algorithm matches the performance of state-of-the-art methods, highlighting its effectiveness in these settings. In the following, provide detailed overview of the games employed.
Grid-based Crowd Modeling Game. This environment, inspired by the Four Rooms example from Geist et al. (2022), is based on a two-dimensional grid with obstacles. Each agent's state is defined by her position on the grid, and she can choose from five possible actions: moving left, right, up, down, or staying in place. The reward function is designed to discourage overerowding by penalizing agents based on the population density at their next position. Specifically, agents receive a negative reward proportional to the logarithm of the density at their destination, encouraging a more even distribution across the state space. Additionally, small bonus is given for staying in place, while moving in any direction results in penalty. Formally, the reward function is defined as
r as -n log(u(s)) + +(a))
where r(a) = 0.2 (a=Stayy 0.2 1 (ay with being the indicator function and x being a crowd-aversion parameter.
In this environment, the transition matrix does not depend on the mean-field distribution μe; however, some stochasticity introduced through slipperiness parameter: when an agent selects action, she is most likely to follow it, but there remains smaller probability of performing different valid move. In particular, for each action, total slipperiness probability of 0.1 is evenly distributed among the alternative actions. Furthermore, this game can be extended by introducing designated point of interest, denoted as Starget, which guides the behavior of the players. The modified reward function is defined as
i f(s, p4) rs, a. (a) + max (0.3 0.1 d(s, Surga)) 0)
where r rss, a, .i) denotes the previously defined reward function, and d(s,, Starget) is the distance between state s and the target state Surget. computed the & norm of their coordinate difference.
Two-Islands-Graph Crowd Modeling. The Two Islands Crowd Modeling Game replaces the grid structure with two interconnected graphs, referred to as islands, connected by a single narrow bridge. The main challenge in this setting arises
10
TP
10-1
101.
Exploitability
10-1
GND
t.-s.
10-4
10-2
10-5
10-7
10-1
10-7
10-9
10-10
10
2000
4000
6000
8000
10000
1000
2000
3000
4000
1000
2000
3000
4000
5000
Iteration
Iteration
Iteration
Figure 3. The reading order is (from left right): Four Rooms Crowd Modeling, Two-Islands--ras Graph Crowd Modeling, and Four Rooms Crowd Modeling with point of interest. Solid lines denote 77 = 0.05, whereas dashed lines indicate 0.3.
44

---

Finite-Sample Convergence Bounds for MF-TRPO
Table Parameter settings for the algorithms.
Algorithn/Parameteer
7
L
It
P
M
Exact TRPO
{0.2,
0.4)
0.9
{0.05,
0.3]
10
0.01
N/A
N/A
N/A
Sample-Based ME-TRPO
0.2
0.9
{0.05, 0.3)
100
0.1
3
10
3
10
100
from the limited connectivity between the two sub-populations. The transition matrix is generated randomly, assigning to each node probability distribution over its neighboring nodes, including itself. The reward function penalizes the logarithm of the mean--iell distribution while encouraging movement toward the second island ig.
(s,, (u) = - log(u(s))) Laeis + lsei))
The Exact ME MF-TRPO algorithm is evaluated on the two proposed variants of the Grid-Based environment and on the Two--slands-Grrs Graph Crowd Modeling game. The former modeled as an x 11 grid with walls delineating four symmetric and interconnected rooms, as in Geist et al. (2022), with all the players starting clustered in the top-left corner. For the latter, we consider a state space size |S| and an action space of size |AA] = 2, with branching factor of 2, that is, each state is connected exactly two neighbors. Here, initially, all players are positioned at location on the first island i (see Figure 5).
F.1. Experimental setting
Results are presented for two different values of the regularization parameter: 77 0.05 and 7) 0.3 and, throughout all experiments, the discount factor is set y 0.9. A key feature of both the exact and sample-based methods is the of warm start for the policy in the RI. component. Rather than resetting the policy to uniform distribution over actions at each iteration, it is initialized with the policy learned from the previous iteration. Moreover, the step size used for updating the distribution remains constant throughout the learning phase, i.e., 3x = B. The key parameters for the two algorithms are summarized in Table
F.2. Results
The plots presented show the exploitability, defined in Equation (7), to evaluate the effectiveness of our approach, along with the evolution of the mean-field distribution over time. Compared to FP and OMD, Exact ME-TRPO performs competitively across all evaluated environments, demonstrating superior long-term performance. training progresses, the model continually improves its policy and ultimately outperforms the other algorithms (see Figure 3). Moreover, players in grid-based games tend move toward less crowded areas, gradually achieving Moreover, when point of interest is introduced, the players manage cluster around it (see Figure 6). Finally, as shown in Figure 5, the players progressively concentrate on the second island, attracted by the higher reward present in that region.
uniform distribution (see Figure 4).
1.0
0.020
0.0125
0.8
0.0100
0.6
0,0075
0.010
0.0050
0.005
0.000
0.0000
Figure Evolution of the mean field distribution for 7 = 0.05 in the Four Rooms Crowd Modeling game, From left right: step 0, step 1000 and step 5000.
45

---

Finite-Sample Convergence Bounds for ME-TRPO
1.0
0:23
0.8
0.20
0.6
0.10
0.0
Figure 5. Evolution of the mean field distribution for 77 0.05 in the Two-Islands Graph Crowd Modeling game. From left right: step 0, step 2000 and step 5000.
0.0125
0.015
0.0100
0.0000
0.0075
0,0050
0.2
0.0025
0.0
0.0000
0.000
Figure 6. Evolution of the mean field distribution for v = 0.05 in the Four Rooms Graph Crowd Modeling game with the bottom-right corner being point of interest. From left right: step 0, step 1000 and step 5000.
46


Reviews:
[{"review_id": "syfIcUz6KL", "reviewer": "Reviewer_SqLi", "summary": "The paper studies the problem of computing Nash equilibria for discounted tabular Mean Field Games, and proposes a trust region policy optimization framework to learn stable and optimal policies. It provides a theoretical analysis of the framework, showing theoretical guarantees of its convergence. \n\nThe paper considers the mean-field entropy-regularized objective, which is well-studied in the literature, and uses a TRPO framework to retain the standard $\\tilde{O}(1/L)$ error bounds in the trajectory estimates, but without assumptions of uniformly bounded away trajectories or continuous reward functions.\n\n## update after rebuttal\n\nThe authors have addressed all my concerns involving the Lipschitz continuity assumption: I am particularly glad that they can show the validity of the theorems under the (even) weaker assumption of the Lipschitz constant bound of $|r|_\\infty$. Moreover, I am happy that the authors have addressed my concerns about assumptions 3 and 4, and I am excited that there is a way for them to incorporate some notion of mean-field sampling, which demonstrates a lot of promise for faster runtimes under the (continued) assumption of homogeneity of the agents.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank Reviewer SqLi for the valuable feedback.  Below, we address the issues raised in the review.\n\n> **The practical significance of the Lipschitz continuity of the reward functions (with respect to μ  and a) seems a bit strange in this tabular setting [...] I would think that the (admittedly, more naïve) $ | r ( s, a, \\mu ) - r( s, a' ,\\mu') | \\leq |r|_{ \\infty } $**\n\nWe respectfully disagree with the Reviewer and would like to point out that the Lipschitz continuity of the reward function with respect to a mean-field measure is critical to establishing convergence rates since, under the proposed condition, any small deviation of the mean-field measure can significantly change the reward function. However, we will remove the continuity condition with respect to actions to simplify the notation.\n\n> **The exact MF-TRPO algorithm requires oracle access to P, which is not an assumption stated in the body of the paper.**\n\nWe will explicitly state the assumption for the exact MF-TRPO algorithm in the revised version of the manuscript. Additionally, we would like to point out that the sample-based version of MF-TRPO was designed explicitly to avoid this assumption.\n\n> **In proposition B.3 in the appendix, I wonder if the proposition is missing a further condition on the step size that $\\sum_{k=0}^\\infty \\beta_k^2 < +\\infty$.**\n\nNo, we do not need this assumption since we are considering the finite-horizon guarantees. The only assumption on $\\beta_k$ that we need is stated in (23) (see Theorem C.4 in Appendix) and it requires $\\beta_k$ to be only smaller than a constant. Notably, any decreasing step-size condition will eventually start satisfying this bound, but may harm the final convergence bound. \n\n> **The paper has no experiments.**\n\nWe considered the paper a theoretical one, but we decided to include numerical studies to stress the applicability of our methods; see https://anonymous.4open.science/r/TRPO-MFG-0468/rebuttal/experiments.md. \n\n> **The paper could motivate the additional assumptions a bit further, for instance it relies on a strong Lipschitz condition on the reward function.**\n\nThe assumption of Lipschitz continuity of the reward function in mean-field distribution is standard in the literature, see, e.g. Angiuli et al. (2021, 2023); Guo et al. (2019); Anahtarci et al. (2023a,b); Zaman et al (2023); Yardim et al. (2023). Additionally, we would like to emphasize that in a large part of practical situations, this condition is also satisfied. \n\n> **In this mean-field TRPO formulation, can you derive a better sample efficiency through mean-field sampling [1]?**\n\nWe thank the reviewer for this insightful suggestion. The approach proposed in [1] focuses on **mean-field control**, where agents act cooperatively to optimize a shared social welfare objective. In contrast, our setting is that of **mean-field games (MFGs)**, where agents are non-cooperative and aim to selfishly optimize their own value functions in interaction with the aggregate behavior of the population.\nThis fundamental distinction complicates a direct application of the approach in [1] to our setting. Specifically, their framework hinges on computing a centralized $Q$-function that captures the collective objective, whereas our formulation requires solving for a fixed point of decentralized best-responses among agents.\nNonetheless, we agree that exploring the **mean-field control counterpart** of our approach could be a fruitful direction. Adapting our methodology to cooperative settings might yield improved sample efficiency and unify learning procedures for both paradigms. We plan to investigate this avenue in future work.\n\n> **Can you extend this formulation to the linear MDP setting beyond the current tabular approach? For instance, the famous mean-field paper by Yang et. al. (2018) provides a Q-learning process in the mean-field setting that works under linear function approximation.**\n\nWe think that such an extension is possible but not straightforward. For example, one needs to guarantee the mean-field distribution's learnability, which might require a new type of assumptions for linear MDPs. However, we find it an exciting direction for further work. \n\n\n\nAdditionally, we would like to thank a reviewer for a list of misprints and other small comments. We have happily introduced the required changes in the revised manuscript.", "claims_and_evidence": "- The practical significance of the Lipschitz continuity of the reward functions (with respect to $\\mu$ and $a$) seems a bit strange in this tabular setting. Lipschitz continuity seems like a more reasonable assumption if the input to the reward function is a point on a manifold, rather than discretized values. In this setting, I would think that the (admittedly, more naïve) $\\|r(s, a, \\mu) - r(s, a', \\mu')\\|\\_\\infty \\leq \\|r\\|_\\infty$ is the most reasonable bound, despite the further explanation in the appendix,\n- The exact MF-TRPO algorithm requires oracle access to $P$, which is not an assumption stated in the body of the paper,\n- In proposition B.3 in the appendix, I wonder if the proposition is missing a further condition on the step size that $\\sum_{k=0}^{\\infty}\\beta_k^2 <\\infty$,\n- However, besides the points above, I find that the idea of driving high-probability estimates for the estimation error using martingale analysis is appropriately rigorously presented, and the theoretical claims appear to be sufficiently rigorous. For instance, theorem B.1 provides a $\\tilde{O}(1/L)$ bound which is exactly what the paper claims.", "methods_and_evaluation_criteria": "The paper has no experiments.", "theoretical_claims": "I did not look very carefully at the line-by-line theoretical claims, but the general structure seems reasonable.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "This paper contributes to the broader work on TRPO in various mean-field RL settings.", "essential_references_not_discussed": "For an audience unfamiliar with mean-field methods, it would be nice if the famous mean-field Q-learning paper by Yang et. al. (2018), which introduces mean-field MARL, were to be discussed as well.", "other_strengths_and_weaknesses": "- This paper claims to remove some restrictive technical assumptions from previous work. I haven't verified the line-by-line methodology in detail, but it appears to be correct,\n- The paper could motivate the additional assumptions a bit further, for instance it relies on a strong Lipschitz condition on the reward function,", "other_comments_or_suggestions": "- would be good to specify _before equation 2_ that this is the entropy regularized objective function,\n- Line 1645 \"tem\" should be \"term\",\n- How does assumption 3 not follow from ergodicity of the Markov chain?\n- Line 243 \"showing that\" is followed by \"show that\" which should be removed,\n- Line 1296: should be \"Jensen's inequality\", and it would be good to clarify that this is a Doob martingale", "questions_for_authors": "1) In this mean-field TRPO formulation, can you derive a better sample efficiency through mean-field sampling [1]?  \n2) Can you extend this formulation to the linear MDP setting beyond the current tabular approach? For instance, the famous mean-field paper by Yang et. al. (2018) provides a Q-learning process in the mean-field setting that works under linear function approximation...\n\nReferences:\n1. Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning (Anand et. al. 2025)", "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": "9hxP0g8S29", "reviewer": "Reviewer_Dz92", "summary": "This paper investigates the finite-sample complexity of a TRPO-inspired method for Mean Field Games (MFGs). It is a game with anonymous agents whose number goes to infinity. A mean-field game is formulated through a mean-field MDP that consists of a population distributions over the state spaces and the reward and transition function are dependent on the population density.\n\nA mean-field Nash equilibrium is a population distribution over state that is invariant to transition and also, the policy achieves the maximum value of the MDP for the particular population distribution.\n\nThe authors use the TRPO policy update along an update between consecutive population distributions. They begin by analyzing their algorithm for the exact case and show exponential convergence to the optimal population distribution.\n\nThen, the authors demonstrate how their method converges when samples are used to approximate the policy gradients.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their precise and thoughtful comments, which have greatly contributed to the refinement of our work. While our initial submission was positioned as primarily theoretical, we appreciate the suggestion and have decided to include **numerical experiments** to better illustrate the applicability and practical relevance of our methodology; see https://anonymous.4open.science/r/TRPO-MFG-0468/rebuttal/experiments.md. \n\n> **What does Lipschitz w.r.t. actions mean? Or, where do you define what |a−a′|  means?** \n\nWe agree with the reviewer’s comment and have removed the Lipschitz condition with respect to the action variable to avoid any confusion. This assumption was not essential for the main results and its removal clarifies the presentation.\n\n> **How does your algorithm compare to other policy optimization techniques?**\n\nWe thank the reviewer for this insightful question. In our work, we adopt a TRPO approach within a $\\nu$-restarted episodic setting. This framework is notably different from the generative setting commonly used in conjunction with $Q$-learning techniques, which have been previously explored in the literature.\n\nOur choice of TRPO is motivated by the inherent instability associated with learning a MFNE. We believe that TRPO-based methods, by enforcing stable policy updates through trust region constraints, are better equipped to handle these instabilities. This design choice allows us to align our algorithmic contributions with a theoretically grounded optimization framework while addressing the specific challenges posed by equilibrium learning in large populations.\n\n> **Would you expect PPO to work as well?**\n\nWhile in practice PPO is known to perform well and could likely be applied in our setting with similar empirical results, the theoretical understanding of PPO remains limited—particularly in the context of convergence guarantees and stability in equilibrium learning. For this reason, we chose TRPO to ground our analysis on a well-understood and principled algorithm, while acknowledging that extending the analysis to PPO remains an interesting direction for future work.\n\n> **Would you be able to incorporate a critic in MF-TRPO?**\n\nIn the current theoretical version of MF-TRPO, the critic is implemented via Monte Carlo estimates, which allows for a clean analysis and convergence guarantees. However, in practical implementations, it is indeed possible to replace the Monte Carlo critic with a parametric critic, such as a neural network. This would introduce additional approximation errors and dependencies on function approximation dynamics, which would significantly complicate the theoretical analysis. Extending the theory to account for these effects remains an interesting and challenging direction for future work.\n\nAdditionally, we would like to thank the reviewer for their careful reading and for pointing out a number of misprints and minor issues. We have gladly incorporated all the suggested corrections into the revised manuscript.", "claims_and_evidence": "The claims are supported by formal mathematical proofs.", "methods_and_evaluation_criteria": "No experiments were provided. The theoretical results used mathematical reasoning.", "theoretical_claims": "I checked extensively the proofs for the exact TRPO and in short the proofs for the stochastic approximation of TRPO.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper is related to the broader literature of mean-field games and also policy gradient methods.", "essential_references_not_discussed": "I do not believe that some key references are missing.", "other_strengths_and_weaknesses": "Strengths:\n* the design of an algorithm based on TRPO, one of the most widely used in practice algorithms, is remarkable\n* the finite-sample complexity result on top of the provable convergence of the latter algorithm is also good.\n\nWeaknesses:\n* no experimental evaluation of the algorithm", "other_comments_or_suggestions": "What does Lipschitz w.r.t. actions mean? Or, where do you define what $|a-a'|$ means?\n912 deterinistic -> deterministic\n1660 Taking the disentegration between on the spatial component", "questions_for_authors": "* How does your algorithm compare to other policy optimization techniques?\n* Would you expect PPO to work as well?\n* Would you be able to incorporate a critic in MF-TRPO?", "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": "pepWSEb23K", "reviewer": "Reviewer_qGy3", "summary": "The authors formulate algorithms for learning equilibria in MFGs. They provide high-probability guarantees and\nfinite sample complexity in the ergodic setting, with relaxed assumptions.\n\n## update after rebuttal\nI thank the authors for their response and additional experiments. The additional experiments and clarifications sound good to me.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and insightful questions. We address them in order below.\n\n> **A strength is the ergodic setting and sample-based guarantees, as they make contributions more directly applicable in real systems, though assumptions such as $\\nu$-restarting and bounds still remain restrictive or hard to verify.**\n\nWe agree that the $\\nu$-restarting assumption may appear restrictive at first glance; however, it closely mirrors the way environments are typically implemented in practice—for example, in widely-used libraries such as `gymnasium`, where each episode begins by sampling an initial state from a fixed restart distribution. This realism was a key motivation behind adopting this assumption in our mean-field setting, as it allows us to formulate sample-based guarantees applicable to a richer class of examples.\n\n> **For me it is a bit unclear how to set all the parameters in practice to run the algorithm, e.g. M.**\n\nWe thank the reviewer for this valuable remark. In the revised version of the manuscript, we have included a more detailed discussion on the role and impact of each parameter—particularly $M$—within the convergence analysis. This was done to better guide the practical implementation of the algorithm. Specifically, we describe how these parameters influence the convergence rate and provide explicit scaling relations that help estimate their appropriate magnitudes. Our analysis begins with the TRPO procedure as a warm start, which offers a structured way to set these parameters based on theoretical guarantees. We hope this clarification helps bridge the gap between theory and practice.\n\n> **I understand the focus is on the theoretical contribution of the paper. Since the contribution is a new algorithm however, and given that this is not the first work on sample based algorithms (Yardim et al.), some experiments would be good to show the usefulness.**\n\nWe thank the reviewer for this constructive comment. While our original intention was to focus on the theoretical aspects of the proposed algorithm, we fully acknowledge the importance of empirical validation. Taking this suggestion into account, we have included numerical experiments in the revised manuscript to illustrate the practical applicability and performance of our method, see https://anonymous.4open.science/r/TRPO-MFG-0468/rebuttal/experiments.md.\n\n> **Assumption 2 is discussed to be a relaxed version of existing assumptions, but in fact it seems from Appx. D.3 that the bound C_{op,MFG} will require both Lipschitz conditions as well as conditions on the uniform mixing, the latter of which appears to not always be necessary in existing algorithms, see e.g. (Anahtarci, 2023)?**\n\nWe thank the reviewer for this observation. We would like to clarify that while Assumption 2 is framed as a relaxation of classical assumptions, it is indeed necessary for deriving a meaningful and non-asymptotic bound in our ergodic setting. Regarding the comparison with Anahtarci (2023), we point out that Remark 3 in the cited paper explicitly acknowledges the need for a $\\beta$-mixing assumption when moving away from the i.i.d. sampling regime, which aligns with our framework. Therefore, our assumptions are directly comparable in scope and purpose, as both approaches require a form of temporal dependence control to ensure valid generalization and convergence guarantees in sample-based reinforcement learning.", "claims_and_evidence": "Theoretical evidence has been provided for the developed algorithms. No experiments were performed.", "methods_and_evaluation_criteria": "The proposed methods make sense, since solving MFGs for NE is a difficult problem, and new sample-based algorithms and analyses are appropriate to move the applicability of MFGs further towards real systems.", "theoretical_claims": "The proofs look fine and plausible to me, I briefly checked the exact versions of the proofs for results up to page 6.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The explanation of prior work looks good to me, as does the additional exposition in the Appendix.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "- A strength is the ergodic setting and sample-based guarantees, as they make contributions more directly applicable in real systems, though assumptions such as $\\nu$-restarting and bounds still remain restrictive or hard to verify.\n- The writing is very clear, and results are rigorous.\n- For me it is a bit unclear how to set all the parameters in practice to run the algorithm, e.g. M.\n- I understand the focus is on the theoretical contribution of the paper. Since the contribution is a new algorithm however, and given that this is not the first work on sample based algorithms (Yardim et al.), some experiments would be good to show the usefulness.", "other_comments_or_suggestions": "Typo l. 345 \"qunatitatives\"", "questions_for_authors": "See above. And in particular, Assumption 2 is discussed to be a relaxed version of existing assumptions, but in fact it seems from Appx. D.3 that the bound C_{op,MFG} will require both Lipschitz conditions as well as conditions on the uniform mixing, the latter of which appears to not always be necessary in existing algorithms, see e.g. (Anahtarci, 2023)?", "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": "X4HgYaIM3i", "reviewer": "Reviewer_uHrJ", "summary": "This paper extends the known concept of trust region policy optimization (TRPO) from the general reinforcement learning literature to the case of ergodic and entropy regularized mean field games. Besides the exact TRPO, the authors also state a stochastic, sample based version of TRPO and present theoretical results for both the exact and stochastic version.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful feedback, which helped us refine the clarity and contextualization of our work. We have revised the manuscript accordingly, including a more detailed comparison with related literature, especially in the ergodic and sample-based MFG setting, to better highlight our contributions.\n\n**Claims:**\n\nBy “well-defined learning rate,” we meant rates satisfying the conditions in Propositions B.5 and C.4, which ensure algorithmic convergence. We clarified this phrasing in the revised manuscript. On “exponential convergence,” we now specify that it refers to the convergence of the mean-field parameter (see Proposition B.3), while the second term captures the finite-sample bias in the best-response computation. The revised text reflects this distinction.\n\nOur approach stands out by operating in the $\\nu$-restarted RL paradigm, which differs significantly from the generative model assumptions used in prior works such as Angiuli et al. (2021, 2023), Guo et al. (2019), Anahtarci et al. (2023b), Zaman et al. (2023), and Mao et al. (2022). We consider a different paradigm for the ergodic setting. Pérolat et al. (2022) provides no finite-sample guarantees, and Yardim et al. (2023) relies on a strong persistence of excitation assumption, requiring near-uniform policies—something we avoid. By using TRPO instead of OMD, we extend the theoretical analysis to a more stable algorithm. This makes our contribution both practically and theoretically more general than existing approaches.\n\n**Comments:**\n\n1. **TRPO.** We now provide an expanded discussion explaining that TRPO stabilizes policy updates by constraining their deviation. This is especially valuable in MFGs, where small changes can cause instability due to the interaction through the population parameter. TRPO’s trust region mitigates such effects and ensures more reliable convergence to Nash equilibria.\n2. **Occupation Measure.** We added a clarification emphasizing its role in the ergodic setting, where it represents the long-run empirical distribution of state-action pairs under a policy. As such, it encodes the joint interaction between policy and mean-field behavior, making it central to our analysis.\n5. **Notation $\\hat{\\pi}$.** This was a typo in Proposition 5.1, now corrected for consistency with earlier definitions.\n6. **``Informal” Propositions.** The label was used to avoid overloading the main text with technical assumptions on learning rates, which are detailed rigorously in the appendix. We’ve added a comment to clarify that the propositions are mathematically precise.\n\n**Questions:**\n\n1. **Empirical Evaluation.** While our paper was originally theoretical, following the reviewer’s suggestion, we now include a numerical evaluation to demonstrate the practical applicability of our method, see https://anonymous.4open.science/r/TRPO-MFG-0468/rebuttal/experiments.md.\n\n2. **Assumption 4**, standard in $\\nu$-restarted RL (e.g., Kakade & Langford, 2002; Shani et al., 2019), ensures sufficient exploration from the initial distribution. It applies only to optimal mean-field policies, making it milder than uniform assumptions in prior work. **Assumption 3** supports convergence guarantees by ensuring ergodic distributions can be learned, as initial conditions fade and occupancy measures concentrate around their expected values.\n\nAlso, we emphasize that these assumptions hold not for any possible policy (that is, uniform concentrability and uniform mixing) but only for the class of optimal mean-field policies. As a result, in our opinion, our assumptions are weak and follow the advances for the single-agent setting. We clarified their roles and practical relevance in the revised manuscript.\n\n3. **What Sets Our Approach Apart:**\n- We work under a realistic, $\\nu$-restarted ergodic MFG paradigm, aligning with practical frameworks like `gymnasium`. This differs from many works that either assume generative models or episodic settings with i.i.d. data.\n- We provide explicit, finite-sample convergence guarantees—still uncommon in the MF-RL literature. We add in the revised version the dependence on key parameters such as the horizon length, population size, and the complexity of the environment.\n- Our assumptions are mild, avoid hard constraints in the softmax temperature for the policies, and are tailored to the practical $\\nu$-restarted framework.\nThese features make our work distinct, both in theory and potential application, within the current MF-RL landscape.", "claims_and_evidence": "The claims made by this paper are not very clear. The authors often make rather vague claims such that their learning approach is \"a practical and scalable approach for solving mean-field games in large, complex, and data-driven settings\" (page 8, lines 409 to 412).  They do not provide any empirical evaluation to back up this claim and the theoretical analysis also appears to be only partially convincing at best.", "methods_and_evaluation_criteria": "There is no empirical evaluation.", "theoretical_claims": "I am not convinced by the theoretical results. First of all, it is not discussed what Assumptions 3 and 4 actually mean in a mean field setting and whether these assumptions are used in any existing mean field game works. For example, how should one check that the two conditions of Assumption 3 are actually fulfilled in an arbitrary given system? \n\nSecond, I do not understand the \"key insights\" of Proposition 5.2 listed in the paper. The mean field distance is bounded by a sum of two terms where only one summand has an exponential character, but the authors claim that there is \"exponential convergence\". What about the second summand then? Furthermore, I am unsure what the insight \"Well-defined Learning rate\" means: are there also (many) other models with ill-defined learning rates? If so, the authors should outline their contribution.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "Although the paper extensively discusses prior works, it remains unclear what the notable contributions of this work are. The authors outline the advantages of entropy regularization for MFGs in their approach multiple times, but these advantages are already well-established in the existing literature. Overall, the authors do not clearly state what sets their work apart from the existing literature. They should precisely pinpoint where the current SOTA learning algorithms fail and why their method provides an improvement in these situations. Additionally, any numerical evaluation and empirical comparison with benchmark methods would be beneficial.", "essential_references_not_discussed": "Related works are discussed.", "other_strengths_and_weaknesses": "Strengths: the paper discusses related works and the learning approach might advance the current literature.\n\nWeaknesses:\n- no empirical evaluation\n- strong and sometimes unclear assumptions\n- no precise statement on how the proposed approach is better than existing ones\n- the theoretical results do not outline crucial advantages of the proposed learning algorithms", "other_comments_or_suggestions": "Comments:\n1. The authors should discuss in more detail what a trust region is intuitively and how it entails a better algorithmic performance in mean field games.\n2. The authors should explain the intuition behind an occupation measure (page 2).\n3. Each of the two Lipschitz constants in Assumption 1 has two different notations. The notations should be unified.\n4. Typo page 5, line 243: \"showing that show that\"\n5. What does the notation $\\hat{\\pi}$ mean in Proposition 5.1 and where is it introduced in the paper?\n6. What is the meaning behind the word \"informal\" in brackets next to Propositions 5.2 and 6.2? Does that mean the statements are not mathematically precise?", "questions_for_authors": "The main questions are closely related to the main weaknesses:\n\n1. Why is there no empirical evaluation?\n2. What is the practical meaning of Assumptions 3 and 4 and how are they justified?\n3. What exactly sets the proposed approach apart from existing learning algorithms?\n4. In which way do the theoretical results support the advantages of the MF-TRPO framework compared to existing algorithms?", "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:

Meta-review: This paper develops Trust Region Policy Optimization (TRPO) algorithms for Mean Field Games. It establishes finite-sample theoretical analysis for exact and stochastic versions under relaxed assumptions compared to prior work. While initial reviews raised concerns regarding assumptions and the lack of experiments, the authors' rebuttal effectively addressed major technical points for most reviewers. This leads to a consensus supporting acceptance among the reviewers.
Decision: Accept (poster)