This paper studies two fundamental problems in regularized Graphon Mean-Field Games (GMFGs). First, we establish the existence of a Nash Equilibrium (NE) of any $\lambda$-regularized GMFG (for $\lambda\geq 0$). This result relies on weaker conditions than those in previous works for analyzing both unregularized GMFGs ($\lambda=0$) and $\lambda$-regularized MFGs, which are special cases of GMFGs. Second, we propose provably efficient algorithms to learn the NE in weakly monotone GMFGs, motivated by Lasry and Lions [2007]. Previous literature either only analyzed continuous-time algorithms or required extra conditions to analyze discrete-time algorithms. In contrast, we design a discrete-time algorithm and derive its convergence rate solely under weakly monotone conditions. Furthermore, we develop and analyze the action-value function estimation procedure during the online learning process, which is absent from algorithms for monotone GMFGs. This serves as a sub-module in our optimization algorithm. The efficiency of the designed algorithm is corroborated by empirical evaluations.
Paper
Similar papers
Peer review
Summary
The paper focuses on two fundamental problems in regularized Graphon Mean-Field Games (GMFGs). The first problem is to establish the existence of a Nash Equilibrium (NE) of any $\lambda$-regularized GMFG (for $\lambda \geq 0$). The second problem is to propose provably efficient algorithms to learn the NE in weakly monotone GMFGs. Regarding the first problem, this paper used weaker conditions than previous works analyzing unregularized GMFGs ($\lambda = 0$) or $\lambda$-regularized MFGs, which are special cases of $\lambda$-regularized GMFGs. To address the second problem, the paper proposes a discrete-time algorithm and derives its convergence rate solely under weakly monotone conditions. Furthermore, the paper develops and analyzes the action-value function estimation procedure during the online learning process, which is absent from algorithms for monotone GMFGs. The efficiency of the designed algorithm is corroborated by empirical evaluations.
Strengths
1. It's quite fascinating to uncover the link between MFG and GMFG as explored in the paper. Notably, the use of lambda-regularized MFG in Proof 1 to find the NE of regularized GMFG provides an intuitive understanding. 2. PMD for the general function approximation is impressive. The decision to employ policy mirror descent adds an interesting dimension to the methodology. The paper appears to be well-rounded and articulately composed. It has a clear presentation of its findings.
Weaknesses
The paper does have quite a few notations, but it's understandable considering the complexity of GMFG. I've got a few questions, which might also point out some areas in the paper that could be improved. I've put these questions and potential weaknesses together in the question section for easy reference.
Questions
I mainly work on Stochastic game theory, not mean field game, so some of my questions might be quite basic. 1. From the first strength, I'm curious about how an NE of the $\lambda$-regularized GMFG is built from an NE of the made-up $\lambda$-regularized MFG. What makes this possible? This is really interesting to me. Is this a common method for MFG and GMFG? Also, is step 3 in the proof of theorem 1, something new compared to the previous literature? 2. In stochastic game theory, I know that $\lambda$-regularizing usually gives a better landscape for optimization, making it easier to find (and define) NE in the regularized setup. Is it the same in the MFG setting? 3. Is the analysis linked to this paper? It'd be helpful to know the technical differences between [1] and this paper. [1] Zhan, Wenhao, et al. "Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence." SIAM Journal on Optimization 33.2 (2023): 1061-1091. If this is well-addressed, I am down to re-evaluate this paper.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The authors adequately addressed the limitation and potential negative societal impact on their work.
Summary
The paper analyzes policy mirror descent for solving regularized GMFG. The results provide new guarantees for learning GMFG without stringent oracle assumptions, and unlike some past works, it does not restrict the results to continuous time analysis. Furthermore, the paper provides an analysis of the case of function approximation. Experimental results are also presented for certain GMFG.
Strengths
The paper provides convincing theoretical guarantees for the proposed algorithm. Table 1 is in general convincing of the theoretical contributions of the work. The analysed setting is novel and removes theoretical oracle assumptions in past work. Furthermore, the analysis is in discrete time (i.e., purely algorithmic) and not in continuous time dynamics. The theoretical results are very clearly presented, and the assumptions are explicit. There is no ambiguity, and the proofs seem correct (although I might have missed details). Furthermore, the incorporation of a function class in the analysis as opposed to oracle access is new in MFG/GMFG to the best of my knowledge.
Weaknesses
While the provided result for offline RL-based approximation of value functions is interesting theoretically, it might be prohibitive in practice as the results stand. Table 1 seems to indicate a large variety of assumptions employed in literature. It is not directly clear how the setting compares to other alternative settings, for instance, if related, a comparison of weak monotonicity with other definitions of monotonicity as well as contraction. This makes it difficult to compare the theory. Experimental results are restricted to toy problems, however, it is possible that no alternative benchmarks exist for GMFG.
Questions
How does the function class complexity $\mathcal{N}_\infty$ scale in general with various schemes of approximation? Several examples could illuminate the reader. Similarly, making the definition of the covering number in the main body explicit could help reading easier. Line 230: The statement regarding switching policies is not clear to me. In general, is there an intuitive explanation of the weak monotonicity assumption? How do the results compare to the specific case of MFG? The graphon structure seems to be more general than MFG, admitting it as a special GMFG with a particular graphon. For a clear comparison, it could be interesting to state the implied bounds (if any) for the special case of monotone MFG with the corresponding implication made clear. Otherwise a direct comparison might be difficult with continuous time results in MFG.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Potential additional limitations to be discussed were mentioned in the weaknesses and limitations.
Summary
Intuitively, a "graphon mean field game" (GMFG) describes the large-$N$ limit of a game with $N$ players, where the payoff of a player $i$ depends on a weighted average of the states of other players $j\in [N]$. The graphon aspect comes from the fact that players have "identities" given by numbers $U_i\in [0,1]$, and the weights in the averages are of the form $W(U_i,U_j)/N$, where $W$ is a suitable function (if $W$ is constant, we have a regular mean field game MFG). GMFGs are potentially useful in multiagent reinforcement learning whenever agent interactions are not too strong. The present paper does not deal with the finite-$N$ problem, but rather with its continuous limit. One important point is that it considers regularized versions of GMFGs, with an added penalization term. The main results are as follows. * Theorem 1 is a new result on the existence of equilibria for (potentially regularized) GMFGs. The main attraction of this result, in comparison with previous work, is that it only makes continuity assumptions on the reward function and transition probabilities (the function $W$ is still assumed Lipschitz). Moreover, the regularization had not been considered previously. Theorem 1 is obtained via a careful reduction to a non-graphon Mean Field Game, for which the authors also prove a new existence result (Theorem 2). * The paper then considers algorithms for approximating Nash equilibria for GMFGs that satisfy a monotonicity condition. Theorem 3 obtains a result under the existence of an "action function oracle". When that is not available, one can resort to function approximation: this leads to Theorem 4, which works under additional assumptions (and require the regularization). A small set of experiments suggests that the authors' method performs well in practice, and also that regularization is important to achieve good performance.
Strengths
The paper is original and significant. It is also quite clear. The following two points stand out. * The existence results work under weak conditions because of the clever use of "soft" techniques. * The algorithms work under relatively natural conditions.
Weaknesses
* It is not clear to me if the Lipschitz assumption on $W$ is really needed. * The proof of Theorem 4 is not particularly surprising. (I hesitate to call this a "weakness", but it is true that this part of the analysis is not too surprising.) * In certain settings the user may be interested in the unregularized GMFG; however, Theorem 4 requires nonzero regularization. The paper does not provide bounds on how close a (near-)NE for the regularized case is to being a NE for the unregularized game.
Questions
These are simply rewordings of my comments on weaknesses. Q1: Regarding Theorems 1 and 2, it looks like the only place where the Lipschitz assumption on $W$ is used is (D.5). However, it looks that all that is needed is uniform continuity, which is equivalent to continuity. Q2: In certain settings the user may be interested in the unregularized GMFG; however, Theorem 4 requires nonzero regularization. Can one prove bounds on how close a (near-)NE for the regularized case is to being a NE for the unregularized game?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
None were discussed, but I don't think there was any need to do so.
Summary
This paper studies regularized Graphon Mean-Field Games (GMFGs). They make two theoretical improvements over previous works on this topic: * They prove existence of Nash equilibrium under weaker assumptions (e.g., weaker requirement on the continuity of the game) than previous works. * For the special case of monotone regularized GMFGs, they give an mirror-descent algorithm that learns the unique Nash equilibrium. Compared to previous works, the novelty here is that the algorithm works for regularized games in discrete time (as opposed to unregularized games and continuous time). In terms of techniques, their first result follows the proof plan of Cui and Koeppl, [2021] that reduces the problem to proving existence of Nash equilibrium for a subclass of GMFGs called MFGs. Their main technical contribution is proving an equilibrium existence result (Theorem 2) for MFGs under weaker assumptions using a different approach than previous works. Their second result essentially adapts the algorithm from Perolat et al. [2021] to their setting.
Strengths
This paper builds upon previous works and makes reasonable improvements. Most interestingly, the condition of their equilibrium existence result (Theorem 2) seems to be significantly weaker than previous works. The paper is well-written. They did a great job introducing the problem and the results and explaining the techniques and the difference from previous works.
Weaknesses
As someone who is not closely following this line of work, it is hard for me to gauge the significance of the new equilibrium existence result, i.e., whether the weakened assumption is significantly more applicable than the assumptions made in previous works. The paper briefly mentions the assumptions in previous works are ``overly restrictive for real-world applications'' but did not provide any concrete example. The algorithm for learning Nash equilibrium in their setting seems to be rather straightforward adaptation (with more careful analysis) from previous work of Perolat et al. [2021].
Questions
Could you elaborate why the new equilibrium existence results are more applicable than previous works with concrete examples? What are the concrete benefits of the exploration step (Line 5 of Algorithm 1) in your learning algorithm? Is it necessary for proving your result?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
4 excellent
Contribution
2 fair
Limitations
n/a
My question was could you give some concrete examples for your claim `` These conditions are restrictive for real-world applications'' but the conditions of your existence theorem are not restrictive? This is supposed to be the main motivation of this paper, but the paper did not mention any concrete example of such applications. (I understand your existence theorem requires weaker assumptions in many aspects theoretically.)
Response to Reviewer eGqz (Part 1/2)
Thanks for the reply. We would like to give some concrete examples of the existence of NE in MFGs. The results in [1] can be easily generalized to the finite-horizon MDP with undiscounted rewards for comparison. It requires the reward functions and the transition kernels are Lipschitz functions. \begin{align*} |r _{h}(s _{h},a _{h},\mu _{h}) - r _{h}(s _{h}^{\prime},a _{h}^{\prime},\mu _{h}^{\prime})|&\leq L _1\cdot(\mathbb{I}\lbrace s _h\neq s _h^{\prime}\rbrace +2\mathbb{I}\lbrace a _h\neq a _h^{\prime}\rbrace+\Vert \mu _h-\mu _h^{\prime}\Vert _1)\\\\ \Vert P _{h}(\cdot| s _{h}, a _{h},\mu _h)-P _{h}(\cdot| s _h^{\prime}, a _h^{\prime},\mu _h^{\prime})\Vert _{1}&\leq K _1\cdot(\mathbb{I}\lbrace s _h\neq s _h^{\prime}\rbrace +2\mathbb{I}\lbrace a _h\neq a _h^{\prime}\rbrace+\Vert\mu _h-\mu _h^{\prime}\Vert _1) \end{align*} for all $h\in[H]$. Then we define the $Q _{\mathrm{Lip}}$ as $Q _{\mathrm{Lip}}=L _1(1-(K _1/2)^H)/(1-K _1/2)$. Then the contraction constant in Proposition 3 in [1] for finite-horizon MFG with undiscounted rewards is \begin{align*} C = 3K _1+\frac{5}{\lambda}\bigg(L _1+\frac{K _1 Q _{\mathrm{Lip}}}{2}\bigg). \end{align*} The parameters $K _1,L _1, \lambda$ should guarantee that $C<1$, i.e., $K _1<1/3$, and $\lambda>5(L _1+ K _1Q _{\mathrm{Lip}}/2)/(1-3K _1)$. * We consider the suspect susceptible–infected–susceptible(SIS) problem in [2], which is a simplified version of the Susceptible-InfectedRemoved (SIR) problem in [3]. The state space contains the susceptible state $S$ and the infected state $I$, i.e., $\mathcal{S}=\lbrace S,I\rbrace$, and the action space contains the going out $U$ and keeping distance $D$, i.e., $\mathcal{A}=\lbrace U,D \rbrace$. The reward function is defined as $r _{h}(s _{h},a _{h},\mu _{h})=-r _{I}\mathbb{I}\lbrace s _h=I\rbrace –r _{D} \mathbb{I}\lbrace a _h=D\rbrace$, and the transition kernel is defined via \begin{align*} P _{h}(s _{h+1}=I | s _h=S, a _h=U,\mu _h) &= P _{a} \cdot \mu _{h}(I)\\\\ P _{h}( s _{h+1}=S| s _h=I,\cdot,\cdot) &= P _{r}\\\\ P _{h}( s _{h+1}=I| s _h=I, a _h=D,\cdot) &= 0 \end{align*} for all $h\in[H-1]$. The first equation indicates that an outside susceptible person will be infected with probability proportional to the ratio of infected people. The parameters of this problem are $r _I,r _D,P _a,P _r>0$. We can show that \begin{align*} |r _{h}(s _{h},a _{h},\mu _{h})-r _{h}(s _{h}^{\prime},a _{h}^{\prime},\mu _{h})^{\prime}|&\leq \max\lbrace r _{I},r _D/2\rbrace\cdot(\mathbb{I}\lbrace s _h\neq s _h^{\prime}\rbrace +2\mathbb{I}\lbrace a _h\neq a _h^{\prime}\rbrace+\Vert\mu _h-\mu _h^{\prime}\Vert _1)\\\\ \Vert P _{h}(\cdot| s _h, a _h,\mu _h)-P _{h}(\cdot| s _h^{\prime}, a _h^{\prime},\mu _h^{\prime})\Vert _{1}&\leq \max\lbrace 1-P _r,P _a\rbrace\cdot(\mathbb{I}\lbrace s _h\neq s _h^{\prime}\rbrace +2\mathbb{I}\lbrace a _h\neq a _h^{\prime}\rbrace+\Vert\mu _h-\mu _h^{\prime}\Vert _1) \end{align*} To guarantee that $C<1$, we require that $P _r>2/3, P _a<1/3$ and $\lambda$ is larger enough than the rewards $r _{I}, r _D$, which restricts the regularization, the infection and recovery probability of each agent. The results in our work do not impose this constraint. * We consider the linear quadratic MFG in [4]. The state space is $\mathcal{S}=\lbrace -L,\cdots,L\rbrace$, and the action space is $\mathcal{A}=\lbrace -M,\cdots,M\rbrace$. The reward function and the transition kernel are defined as \begin{align*} r _{h}(s _{h},a _{h},\mu _{h})&= -\frac{1}{2}a _h^2+qa _h(m _h-s _h)-\frac{\kappa}{2}(m _h-s _h)^2\\\\ s _{h+1}&= \mathrm{Discretize}[s _h+ a _h + K(m _h-s _h)+\sigma\varepsilon _h] \end{align*} for $h\in[H]$, where $q,\kappa,K>0$ are the parameters of the game, $m _h=\sum _{s\in\mathcal{S}}s\cdot\mu _h(s)$ is the first moment of the state distribution, $\varepsilon\sim\mathcal{N}(0,1)$ is the noise, and $\mathrm{Discretize}[\cdot]$ operator discretizes a state into the closed state in $\mathcal{S}$. With the data processing inequality and some basic calculations, we can show that \begin{align*} |r _{h}(s _{h},a _{h},\mu _{h})-r _{h}(s _{h}^{\prime},a _{h}^{\prime},\mu _{h})^{\prime}|&\leq \max\lbrace (M+2qL)^2/4,L(3\kappa L+2qM)\rbrace\cdot(\mathbb{I}\lbrace s _h\neq s _h^{\prime}\rbrace +2\mathbb{I}\lbrace a _h\neq a _h^{\prime}\rbrace+\Vert\mu _h-\mu _h^{\prime}\Vert _1)\\\\ \Vert P _{h}(\cdot| s _h, a _h,\mu _h)-P _{h}(\cdot| s _h^{\prime}, a _h^{\prime},\mu _h^{\prime})\Vert _{1}&\leq \frac{\max\lbrace |1-K|,1/2,2LK\rbrace}{2\sigma}\cdot(\mathbb{I}\lbrace s _h\neq s _h^{\prime}\rbrace + 2\mathbb{I}\lbrace a _h\neq a _h^{\prime}\rbrace+\Vert\mu _h-\mu _h^{\prime}\Vert _1). \end{align*}
Response to Reviewer eGqz (Part 2/2)
To guarantee that $K _1<1/3$, we require that $2\sigma>3\max\lbrace |1-K|,1/2,2LK\rbrace$. This is intuitive, since when $\sigma$ is much larger than $L$, the noise will be similar to the uniform distribution on $\mathcal{S}$, which makes the state transition unrelated to $s _h,a _h$, and $\mu _h$. We note that the maximal reward an agent can get in each time step is $M^2/2+2qML+2\kappa L^2$. The fulfillment of $\lambda>5(L _1+ K _1Q _{\mathrm{Lip}}/2)/(1-3K _1)$ requires that $\lambda$ is comparable to the maximal reward in each step. In contrast, our results do not require such a constraint. [1] B. Anahtarci, C. D. Kariksiz, N. Saldi. Q-learning in regularized mean-field games. Dynamic Games and Applications, 13(1), 89-117(2023). [2] Kai Cui, and Heinz Koeppl. Learning graphon mean field games and approximate nash equilibria. arXiv preprint arXiv:2112.01280 (2021). [3] A. Aurell, et al. Finite state graphon games with applications to epidemics. Dynamic Games and Applications 12.1 (2022): 49-81. [4] S. Perrin, J. Pérolat, M. Laurière, M. Geist, R. Elie, O. Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems, 33, 13199-13213(2020).
Thank you for the very detailed rebuttals. All of my questions have been answered, and I will leave my rating as a 7.
Thank you
I thank the authors for their rebuttal. I remain favorable to the paper being accepted.
Decision
Accept (poster)