Finite-Sample Convergence Bounds for Trust Region Policy Optimization in Mean Field Games

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.

Claims:

By “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.

Our 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.

Comments:

1. 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.
2. 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.
3. Notation $\hat{\pi}$. This was a typo in Proposition 5.1, now corrected for consistency with earlier definitions.
4. ``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.

Questions:

1. 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.

2. 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.

Also, 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.

3. What Sets Our Approach Apart:

• 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.
• 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.
• Our assumptions are mild, avoid hard constraints in the softmax temperature for the policies, and are tailored to the practical $\nu$-restarted framework. These features make our work distinct, both in theory and potential application, within the current MF-RL landscape.

We thank the reviewer for their positive feedback and insightful questions. We address them in order below.

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.

We 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.

For me it is a bit unclear how to set all the parameters in practice to run the algorithm, e.g. M.

We 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.

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.

We 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.

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)?

We 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.

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.

What does Lipschitz w.r.t. actions mean? Or, where do you define what |a−a′| means?

We 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.

How does your algorithm compare to other policy optimization techniques?

We 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.

Our 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.

Would you expect PPO to work as well?

While 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.

Would you be able to incorporate a critic in MF-TRPO?

In 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.

Additionally, 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.

We would like to thank Reviewer SqLi for the valuable feedback. Below, we address the issues raised in the review.

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 }$

We 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.

The exact MF-TRPO algorithm requires oracle access to P, which is not an assumption stated in the body of the paper.

We 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.

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$.

No, 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.

The paper has no experiments.

We 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.

The paper could motivate the additional assumptions a bit further, for instance it relies on a strong Lipschitz condition on the reward function.

The 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.

In this mean-field TRPO formulation, can you derive a better sample efficiency through mean-field sampling [1]?

We 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. This 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. Nonetheless, 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.

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.

We 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.

Additionally, 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.