Last Iterate Convergence in Monotone Mean Field Games

Authors: Noboru Isobe, Kenshi Abe, Kaito Ariu
Primary area: optimization
Keywords: mean field game, learning in games

Abstract:
Mean Field Game (MFG) is a framework utilized to model and approximate the behavior of a large number of agents, and the computation of equilibria in MFG has been a subject of interest. Despite the proposal of methods to approximate the equilibria, algorithms that can achieve equilibrium with the most recent policy of the algorithm, namely the last-iterate policy, have been limited. 
We propose the use of a simple, proximal-point-type algorithm to compute strategies for MFGs. Subsequently, we provide the first last-iterate convergence guarantee under the Lasry--Lions-type monotonicity condition. 
We further employ the Mirror Descent algorithm for the regularized MFG to efficiently approximate the update rules of the proximal point method for MFGs. 
We demonstrate that the last-iterate strategy of Mirror Descent converges exponentially fast: we provide the guarantee of computing the $\varepsilon$ approximation in $\mathcal{O}(\log(1/\varepsilon))$ iterations. This research offers a tractable approach for large-scale and large-population games.

Decision: reject
Reviewer scores: 5, 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1730557582619

thread_type:
official_review

<thread_object>
creator: reviewer_b31r

<content>
summary:
The paper studied regularized MFG and proposed a mirror descent algorithm that can converge in $O(\log(1/\epsilon))$ iterations.

strengths:
The paper is well-written and the proof is clear. The result is the first last-iterate convergence in regularized MFG to my best knowledge.

weaknesses:
My main concern is that, with the monotonicity condition and the regularization $\lambda$, the results can be straightforwardly obtained given the existing proof of exponentially fast convergence of MD in monotone games. See [1] for details. 

Specially, the relationship between $D_{\mu^\ast} (\pi^\ast, \pi^{t+1})$ and $D_{\mu^\ast} (\pi^\ast, \pi^{t})$ has already been derived in Zhang et al 2023. To obtain the exponentially fast convergence rate, you would only need to get the $1-\lambda \eta$ factor out of $D_{\mu^\ast} (\pi^\ast, \pi^{t})$. One common way to achieve this is to use the monotonicity condition. From what I understand, this paper uses the same technique that has been used in papers such as [1]. 


[1] Cen, Shicong, Yuting Wei, and Yuejie Chi. "Fast policy extragradient methods for competitive games with entropy regularization." Advances in Neural Information Processing Systems 34 (2021): 27952-27964.

questions:
Can you elaborate on the technical contributions of this work? Specifically, why wouldn't a straightforward application of the analysis proposed in [1] work in regularized monotone mean field games?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730671198234

thread_type:
official_review

<thread_object>
creator: reviewer_aglm

<content>
summary:
This paper studies the convergence performance in Monotone Mean Field Games. The major issue is that the focus of this paper are all well studied. Authors cannot identify the research gap and contribution in a comparison to existing study.

strengths:
The paper is well structured and organized.

weaknesses:
1. Position: Last-iterate convergence and learning regularized MFGs have been extensively studied. However, the discussion of related work in this manuscript is somewhat superficial. The authors should conduct a thorough literature review and clearly position their work within the existing literature. This will help avoid giving the audience the impression that their contribution is marginal, merely by applying a proximal point iteration to MFGs.

2. Exponential convergence of mirror descent: Using mirror descent to learn regularized mean field games (MFGs) is not a novel approach. To the best of my knowledge, previous studies have established a standard convergence rate of $T^{-1/2}$. In contrast, this work claims an exponential convergence rate of $e^{-T}$, which represents a significant improvement. The authors should clearly explain the specific challenges they addressed to achieve this enhanced convergence rate that previous work did not tackle. Additionally, providing numerical demonstrations of such exponential convergence is essential, given the magnitude of this improvement.

3. Presentation: the presentation of the paper is not yet suitable for scientific publication. Please avoid excessive use of colors, shapes, and unconventional layouts. Figure 1 lacks informative content. Additionally, some language and structural transitions are too casual and do not provide sufficient discussion to support the arguments presented convincingly.

4. The numerical experiments are limited. More results regarding the algorithm performance in a comparison to baselines (OMD, FP, Multi-scale, double loop, single loop) for MFGs should be provided.

questions:
Please see details in weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730717816689

thread_type:
official_review

<thread_object>
creator: reviewer_4hfx

<content>
summary:
This paper proposes and algorithm for mean field games (MFGs) based on proximal-point-type iterations. After proving convergence of the last iterate for an ideal algorithm, the paper considers an approximate algorithm based on mirror descent updates. For regularized MFGs, a proof of convergence is provided, with a rate of convergence. A simple illustrative example is shown at the end.

strengths:
The paper is relatively clear and addresses an interesting question (last-iterate convergence). It seems to have a good theoretical foundation.

weaknesses:
The first result holds under general assumptions but the algorithm cannot be implemented. The second result holds only for regularized MFGs, which can be quite different from the original (unregularized) MFG problem and there is not much discussion about this. As a consequence, the contributions seem relatively limited.

questions:
Q1. In Assumption 2.1, please clarify why “It is reasonable to assume” it. For example, it is violated in many examples of the MFG literature in grid world models, where the agents cannot jump from a given state to any other given state (for any action). I think this would be true only if there is a very strong noise that can propel an agent to any other state in just one time step. It does not seem very realistic from the physical viewpoint. Please explain.

Q2. In Definition 4.2, are regularized equilibria unique? Otherwise, please explain how you can say “the regularized equilibrium” in Theorems 4.3 and 4.4. 

Q3. Algorithm 2 and Theorem 4.3: it seems to rely very strongly on the RMD of Zhang et al. (2023). How does the proof of convergence of Theorem 4.3 differs from theirs?

Q4. Theorems 4.3 and 4.4: Could you please confirm whether these results hold for any $\lambda$ and $\sigma$, simply under Assumption 4.1? I just want to make sure there is no requirement to take $\lambda$ large enough as e.g., in  Cui & Koeppl (2021).

Q5. Theorems 4.3 and 4.4: Here it seems that the convergence only holds for the regularized MFG. How far is it from the true MFG equilibrium?

Q6. Could you please explain whether the example considered in the numerical part satisfies all the assumptions required for your convergence results? Also, is it not strictly monotone (so that it does not fall in the case covered by Perolat et al. (2022))?

Q7. To really see how your method compares with existing one, please compare your algorithm with other baselines, such as the algorithms considered in Perolat et al. (2022) (in particular the mirror-descent-type one, which has last-iterate convergence, as you mentioned).

Typos:
Definition 2.4: “is mean-field” -> “is a mean-field”
Page 3: “has the full support” -> “has full support”
</content>
</thread_object>

</thread>
<thread>
creation date:
1732208431687

thread_type:
official_review

<thread_object>
creator: reviewer_ywpq

<content>
summary:
This paper proposes algorithms for achieving fast convergence to equilibria in monotone mean field games. The first (conceptual) algorithm is based on a proximal point method type of algorithm that is based on possibly hard to implement update step. Next, the authors employ the Mirror Descent algorithm for a regularized MFG which can efficiently approximate the update of the proximal point method. This process converges exponentially fast to equilibria of the regularized game.

strengths:
- the paper studies a well motivated problem (MFG games + monotonicity).
- it contains provable theoretical analysis of their last iterate results.
- the proof structure is easy to parse.

weaknesses:
- the theoretical results feel somewhat incremental from a technical stand point. E.g. the use of the regularized variant of MD to achieve fast convergence in monotone settings feel very similar to e.g. [1]. Clearly, there are more technicalities involved to adapt the results to this precise setting but arguably these technicalities do not feel conceptually/technically novel. On the somewhat positive side, this makes parsing the proof rather straightforward.
- the experiments could be expanded. For example, prior work that studied last-iterate convergence in (non-strict) monotone settings used the experiments to study the effects of equilibrium selection [2]. Although the possibility of diverse equilibria is advertised in the paper as an important element of monotone games, not present in strictly monotone games, the implications of which equilibria get selected is not addressed. I feel that this is a missed opportunity that would make the paper significantly stronger.

[1] Julien Perolat, et al. From Poincare recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In ICML, volume 139 of Proceedings of Machine Learning Research, pp. 8525–8535. PMLR, 2021.
[2] Leonardos, S., et al. Exploration-exploitation in multi-agent competition: convergence with bounded rationality. Advances in Neural Information Processing Systems, 2021.

questions:
Can you say anything about the effects of your algorithm to equilibrium selection? Either theoretically or experimentally?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732802307697

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global  comment by authors

comment:
We appreciate the detailed feedback on our paper. We would like to highlight the technical novelty of our main theorems (Theorem 3.1 and 4.3).

---

# Significance of Our Convergence Results
First, we would like to emphasize again the importance of our convergence results.

- **LIC without Strong Assumptions**: Unlike many referenced works requiring strong assumptions (e.g., contraction), our results demonstrate last-iterate convergence (LIC) without such conditions.
- **Proximal Point Method (PP)**: Demonstrating LIC for PP cannot be achieved by merely leveraging existing optimization techniques. Our finding that a single update of PP can be interpreted as solving a crucial regularized MFG is non-trivial (see lines 180-185 of our manuscript).
- **Exponential Convergence of Regularized Mirror Descent**: Derived a different discretization error $ D_{\mu^\ast}(\pi^t, \pi^{t+1}) $ from Zhang et al., facilitating clearer subsequent analysis. Our discretization error can be bounded by $ D_{\mu^\ast}(\pi^\ast, \pi^t) $ (see l.369-372).

---


# Comparison with Prior Work
In addition to Appendix A, we discuss the comparison with specific previous studies as indicated by the reviewers below:
- **Comparison with Zhang et al. (2023)**
  - **Zhang et al.**: Demonstrated convergence for the time-averaged policy $\frac{1}{T}\sum_{t=1}^T\pi^t$ with the rate $\mathcal{O}(T^{-1/2})$.
  - **Our Work**: Proven last-iterate convergence with the exponential rate, meaning the convergence of the actual policy $\pi^t$. This provides stronger guarantees on the convergence behavior of the algorithm.

- **Continuous-time Analysis in Perolat et al. (2022) vs. Discrete-time Analysis**
  - **Perolat et al.**: Analyzed the convergence of the continuous-time Follow-the-Regularized-Leader algorithm.
  - **Our Work**: Extended beyond continuous-time convergence (Theorem 4.4) to address discrete-time convergence (Theorem 4.3). Discrete-time convergence is more challenging due to the need for precise evaluation of discretization errors (see equation (4.6) and Claim 4.5 for details).

- **Sequential Imperfect Information Game in Perolat et al. (2021) vs. Mean Field Game (MFG)**
  - **Perolat et al.**: Focused on the reaching probability $\rho^\pi$ over histories in Sequential Imperfect Information Games.
  - **Our Work**: Focused on the distribution of states $\mu=m[\pi]$ in MFGs. The dependency on $\pi$ is fundamentally different: $\rho$ depends on $\pi$ in a linear-like manner, while our $\mu$ has a highly nonlinear dependency on $\pi$ (see equation (2.1)). Addressing this nonlinearity required novel techniques exploiting the inductive structure of equation (2.1) with respect to time $h$.
  > Julien Perolat, et al. From Poincare recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In ICML, volume 139 of Proceedings of Machine Learning Research, pp. 8525–8535. PMLR, 2021.

- **Markov Decision Processes (MDPs) in Zhan et al. (2023) vs. MFGs**
  - **Zhan et al.**: The theory for MDPs cannot be directly applied to MFG for the convergence of mirror descent. The inner product $\langle Q^{k}(s),\pi^{k+1}(s)-p\rangle$ in [[Lem. 6, Zhan et al.]](https://arxiv.org/abs/2105.11066) is not compatible with the property specific to MFG (lemma E.4).
  - **Our Work**: Derived $\langle Q^{k}(s),\pi^{k}(s)-p \rangle$ instead, allowing us to apply the property (see the fourth line of equation (D.6)).
  > Zhan, W., Cen, S., Huang, B., Chen, Y., Lee, J. D., & Chi, Y. (2023). Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. SIAM Journal on Optimization, 33(2), 1061-1091.

---


# Our Technical Novelty
Finally, we explain the techniques of proof that we used to obtain the novel results described above.

- **Challenge**: Non-Lipschitzness of the Q function, not addressed by prior research including Zhang et al. (2023).
- **Our Solution**: Established a novel claim in Claim 4.5 and l.370: “the value function $ Q_h^{\lambda,\sigma} $ behaves well, almost as if it were a Lipschitz continuous function.”

---

We hope this clarifies the technical novelty and significance of our contributions.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper examines a proximal-point algorithm for computing equilibrium strategies in mean field games (MFGs), and focuses in particular on the algorithm's "last-iterate" convergence properties - that is, the convergence of the sequence of play generated by the algorithm, as opposed to some averaged version thereof. The authors consider MFGs that satisfy a (weak) monotonicity condition in the spirit of Lasry and Lions, and they employ an approach based on mirror descent to efficiently approximate update rules for regularized MFGs. The paper's main result is that regularized mirror descent converges at a geometric rate, attaining an $\varepsilon$-equilibrium in $\mathcal{O}(\log(1/\varepsilon))$ iterations.

While the reviewers appreciated the convergence properties of the proposed algorithms, it was pointed out that the combination of regularization and Bregman-type proximal point algorithms is very close to previous works in the literature - e.g., by Perolat et al. in the context of MFGs - and the effort required to adapt these techniques to the authors' precise setting was deemed somewhat incremental. Concerns were also raised regarding the experimental validation of the proposed algorithms relative to other algorithmic baselines for MFGs, especially in the strict-/weak-monotonicity gap.

The authors' rebuttal and responses did not significantly sway the reviewers' original opinion, who remained unanimously on the side of rejection (albeit borderline so), ultimately leading to a reject recommendation.