Learning Regularized Monotone Graphon Mean-Field Games
Authors: Fengzhuo Zhang
Vincent Tan
Zhaoran Wang
Zhuoran Yang
Venue: NeurIPS 2023 poster (2023)
Keywords: mean-field approximation
graphon games
multi-agent reinforcement learning

Abstract: 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 previous works 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.

Learning Regularized Monotone Graphon Mean-Field Games
Fengzhuo Zhang'
Vincent F. Tan' Zhaoran Wang²
Zhuoran Yang? Yale University
National University of Singapore Northwestern University fzzhangdu. nus edu, vtanθnus edu.sg.
zhaoranwang@gmaill com, zhuoranyang, work@gmail.com
Abstract
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 A-regularized GMFG (for 0). This result relies on weaker conditions than those in previous works for analyzing both unregularized GMFGs (A = 0)
and X-regularized MFGs, which are special cases of GMFGs. Second, we pro- pose 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 required extra conditions to analyze discrete-time algorithms. In contrast, we design a discrete-timg algorithm and derive its conver- gence 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 sub-module in our optimization algorithm. The efficiency of the designed algorithm is corroborated by empirical evaluations.
Introduction
In Agett Reinforcement Learning (MARL), the sizes of state and action spaces grow expo-
nentially in the number of agents, which is known the "curse of many agents" [Sonu et al. 2017
Wang et al. 2020) and restrict its applicability to large-scale scenarios. The Mean-Field Game (MFG)
has thus been proposed mitigate this problem by exploiting the homogeneity assumption (Huang
jet al. 2006 Lasry and Lions] 2007]. and it has achieved tremendous successes in many real-world applications [Cousin et al. [201 Achdou al. 20200. However, the homogeneity assumption an impediment when modeling scenarios in which the agents are heterogeneous. GMFGs, as extensions
of MFGs, have thus been proposed to model the behaviors of heterogeneous agents and ameliorate
the "curse of many agents" at the same time Parise and Ozdaglar 2019 Carmona et al.
2022
Despite the empirical successes of the Graphon Mean-Field Game (GMFG) [Aurell et al. 2022a its
theoretical understanding is lacking. First, sufficient conditions for Nash Equilibrium (NE) existence in regularized GMFG have not been established. Most works only address the existence of the NE in unregularized GMFGs. However, regularization is employed in practical implementations for improved exploration and robustness [Geist al., 2019]. Moreover, previous works prove the existence of NE in regularized MFGs, a special case of GMFGs, only under the contraction condition, which overly restrictive for real-world applications. Second, the analysis of discrete- time algorithms for monotone GMFGs is lacking. Most existing works design provably efficient discrete-ting time algorithms only under contraction conditions, as shown in Table I Complementarily: previous works on monotone GMFGs either only derive the convergence rate for continuous time algorithms, which ignores the discretization error, or require extra conditions, (c.g., potential games) to analyze discrete- iiscrete-time algorithms.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Comparison of GMFGs and MFGs learning algorithms
No population
Online playing
Discrete-time Convergence
Condition
Heterogeneity
manipulation
algorithm
rate
Anahtarci et al.
2022
Contraction Contraction
No
No
No
Yes
Yes
Xie et al. 202 a
No
Yes
No
Yes
Yes
Zaman et
2022
Contraction
No
Yes
No
Yes
Yes
Yardim ct al.
2022
Contraction
Yes
Yes
No
Yes
Yes
Perrin
2020
Monotone
No
No
No
No
Yes
Potential
Geist et al.
[022
No
No
No
Yes
Yes
&Monotone
Perolat et
2021
Monotone
Yes
Yes
Yes
No
No
Fabian et al.
2022
Monotone
Yes
Yes
Yes
No
No
Our work
Monotone
Yes
Yes
Yes
Yes
Yes
In this paper, we first consider GMFGs in full generality, i.e., without any contraction monotone
conditions. The goal is to establish the existence of NE in the regularized GMFG in this general setting. Then we focus monotone GMFGs motivated by Lasry and Lions [007]. We aim to learn the unique NE from the online interactions of all agents with and without the action-value function oracle. When the oracle is absent, the action-value functions should be estimated from the data of sampled agents generated in the online game.
In the analysis, we have to overcome difficulties that arise from both the existence of the NE problem and the learning of the NE. First, the proof the existence of NE in regularized GMFG involves establishing some topological spaces and operators related to NE are applicable. However, the direct construction of the space and the operators for GMFGs with uncountably infinite agents is challenging. Second, the design and analysis of the discrete-time NE learning algorithm require subtle exploitation of the monotone condition. Unlike continuous time algorithms with infinitesimal step sizes, the design appropriate step sizes is additionally required for the discrete-time algorithm to guarantee that iterates evolve appropriately. This guarantee originates from the delicate utilization of the monotone condition in the optimization procedures.
which fixed point theorems
To address the difficulty of the existence problem, we construct a regularized MFG from the reg- ularized GMFG and show that the NE of the constructed game can be converted into the NE of the original game, thus mitigating the difficulty of having an uncountable number of agents. To handle the difficulty in the NE learning problem, we design the Monotone GMFG Policy Mirror Descent (MonoGMFG-PMMD algorithm, which iteratively implements policy mirror descent for each player. We show that this procedure results in decrease of the KL. divergence between the iterate and the NE, and this decrease is related to the gap appearing in the weakly monotone condition. When the action-value function oracle is absent, also design and analyze action-value functions estimation algorithms to serve as a submodule of the optimization procedures.
We first establish the existence of the NE in the X-regularized GMFG with 2 assuming Lipschitzness of graphons and continuity transition kernels and reward functions. Our result relaxes the assumption of the Lipschitzness of transition kernels and rewards required in previous works on unregularized GMFGs and the contraction condition in the literature on regularized MFG (Cui and Koeppl [021a]. Then design and analyze the MonoGMFG-PMII algorithm. Using an action-value function oracle, the convergence rate for MonoGMFG-PMD is proved to be (T22 after T iterations. Without the oracle, the convergence rate includes an additional ((K-1/2 + NN1) term that arises from sampling N agents and collecting data from K episodes, reflecting the generalization error and the approximation error of the estimation algorithm. As shown in Table [. our algorithm can be implemented from the online interaction of agents and does not require the distribution flow manipulation. Detailed explanations of the properties stated in the columns of Table are provided in Appendix A Our result for MonoGMFG-PNM provides the first convergence rate for discrete-ting algorithms in monotone GMFGs.
Main Contributions:
2 Related Works
MFGs were proposed by Huang et al. [2066] and Lasry and Lions (0077] to model the interactions among a set of homogeneous agents. In recent years, learning the NE of the MFGs formulated by

---

discrete-time time Markov Decision Process (MDP)s has attracted a lot of interest. There is a large body of works that design and analyze algorithms for the MFGs under contraction conditions [Anahtarei
et al. 2019 2022 Cui and Koeppl, 2021a Xie et al. 2 Zaman et al. 2022 Yardim et al. [022]] Typically, these works design reinforcement learning algorithms to approximate the contraction operators in MFGs, and the NE is learned by iteratively applying this operator. In contrast, another
line of works focuses on the MFGs under monotone conditions. Motivated by Lasry and Lions [200)] the transition kernels in these works are independent of the mean fields. |Perrin et al. [2020] proposed and analyzed the continuous-time fictitious play algorithm, which dynamically weighs the past mean fields and the best response policies to derive new mean fields and policies. With the additional potential assumption, Geist et al. 2021 derived the convergence rate for the discrete- time fictitious play algorithm. |Peollat et al. [202] then proposed the continuous-tim policy mirror descent algorithm but only proved the asymptotic convergence, i.e., the consistency. In summary, there is no convergence rate result for any discrete-time algorithm for MFGs under the monotone condition. In addition, the relationship between the contraction conditions and the monotone conditions is not clear from existing works, but they complement each other.
To capture the potential heterogeneity among agents, GMFGs have been proposed by Parise and Ozdaglar [019] in static settings an extension of MFGs. The heterogeneous interactions among agents are represented by graphons. Aurell et al. (022b), Caines and Huang [2019] then extended the GMFGs to the continuous-time setting, where the existence and the uniqueness of NE were established. Vasaal et al.] [2020] formulated discrete-time GMFGs and provided way to compute the NE with master equations. With the precise underlying graphons values, Cui and Koeppl 2021b proposed algorithms to learn the NE of GMFGs with the contraction condition by modifying MFGs learning algorithms. |Fabian al. [2022] considered the monotone GMFG and proposed the continuous-time policy mirror descent algorithm to learn the NE. However, only consistency was provided in the latter two works.
Notation Let [N] := {1, (1,..... .... Given a measurable space F)) we denote the collection of all the measures and the probability measures on F2, as M(2) and A(I2), respectively. For metric space (XY || []). we use C(X) and (x)) to denote the set of all continuous functions and the set of all bounded continuous functions on X, respectively. For measurable space (X,F) and two distributions P.C. Q E ( the total variation distance between them is defined as TV Q) := su ((A)) ) sequence of measures (m²) on X' is said to converge weakly to measure if Ix ((r)) (dz) + fx ((x))((x) for all g E C)(X)..
3 Preliminaries
3.1 Graphon Mean-Field Games
We consider a GMFG that is defined through a tuple S, P,,, The horizon (or length) of the game is denoted as H. In GMFG, we have infinite players, each corresponding to point a E I [0, 1]. The state and action space of them are the same, denoted as S C Rd. and A C Rd respectively. The interaction among players is captured by graphons. Graphons are symmetric functions that map [0, 1|2 to [0. 1]. Symmetry here refers to that W(a, 3) = W(3,0 a)) for all a, 3 E j0, 1). We denote the set of graphons as W = {W- [0, 1 + [0, 1] W is symmetric.). The set of graphons of the game is W = [W)) with W,, E W. The state transition and reward of each player are influenced by the collective behavior of all the other players through an aggregate
3 E MMS).. At time h E [H]. denote the state distribution of player 3 E I as pld E A(S). The aggregate for player a E I with the underlying graphon Wn, E W is then defined as
2h - -[ Wa 8)1g a3.
(1)
The transition kernels P= [Pr) of the game are functions PA S x A M(S) - for all h E [H]. At time h, if player takes action Oj E A at state Sy E S, her state will transition according to 1 ~ (- I 8 ag ).) The reward functions are denoted as Th : S x A x M(S) - [0, 1] for all E [H]. We note that the players in GMFG are heterogeneous. This means that different players will, in general, receive different aggregates from other players. The distribution /11 E ASS) is the
initial state distribution for all the players. policy for an player a is T = {mf [h= E I where
T S *(A) takes action based only on the current state, and II is the set of all these policies.
3

---

A policy for all the players x² E îî = II
is the collection of the policies of each player, i.e, x² { Jasz. In the following, we denote the state distributions of all the players at time h and the state distributions of all the players at any time (distribution flow) respectively as / = {ug faez and n² ( E Å ((S)#x7 Eqn. I shows that the aggregate 2% is a function of μz and Wh, so to make this dependence explicit, we also write it as 2f (uK W.).
We consider the entropy- regularzeee GMFG. It has been shown that the regularization results in policy gradient algorithms converging faster (Shani et al. [220 Cen et al. 2022]. In this game, the rewards of each player are the sum of the original rewards and the negative entropy of the policy
multiplied by a constant. In X-regularized GMFG (A 2 0), the value function and the action- value
function of player a with policy x² on the MDP induced by the distribution flow px² are defined as
H Σ
= =I=" (, ;,=)
(s of of (v7, W.)) - Alog क. (af (8)
8h =
(2)
N (s, T
ra(s, a, = ( Wi)) ET" [VA+
,² 88 8, 0i = a
for all h. E [H]. where the expectation Ex is taken with respect to the stochastic process induced by implementing policy x² on the MDP induced by μ²² The cumulative reward function of player a is defined as JA (I" .1=)) = E (V>.0 (s, TT, "=","))))))))))"")"")) ).))] Then the notion of an NE is defined as follows.
Definition 1. An NE of the X-regularized GMFG is a pair (T" (1= II â that satisfies: (i) (player rationality) [x ,1²² = ma Jh (0",,1"""" for all a E I up to zero- measure set on with respect to the Lebesgue measure. (ii) (Distribution consistency) The distribution flow n² is equal to the distribution flow induced by implementing the policy n
Similar to the NE for the finite- finite-player games, the NE of the X-regularized GMFG requires that the policy of each player is optimal. However, in GMFGs, the optimality is with respect to pT
3.2 Mean-Fiee Games
As an important subclass of GMFG, MFG corresponds to the GMFG with constant graphons, i.c, W (a, 8) = p for all a, 8 E T. MFGs involve infinite homogeneous players. All the players employ the same policy and thus share the same distribution flow. The aggregate in Eqn. | degenerates to 2% = So p-
fl, d3 d3 = p 14 for all a E I. Here μa is the state distribution of a representative player. Thus, an MFG is denoted by tuple (S,A, 11, P, F, M1). The state space, the action space, and the horizon are respectively denoted as S, A, and H. Here, the transition kernels P = ] are functions Pa : S x A x A(S) - S, and reward functions F4 : S x A A(S) - [0, 1] for all h E [H] In the MFG, all the players adopt the same policy π = { {TT /== where Tr E II. The value function and the action-value function in the X-regularized MFG with the underlying distribution
1
If
flow / [m E ASS) can be similarly defined as Eqn. (2) and (3) respectively as follows
H Vi E Σ
Fr aes pc) AlogTe(a st)
sh =
(s a,) Fn(ss a, mb) + ET [Vi+ (S1+1, ग. 1)) = 8, an = =]]
for all h E [H]. The cumulative reward is J (T, E,, E (V, m)]. The notion of NE can be similarly derived as follows.
Definition 2. An NE of the X-regularized MFG is a pair (T", ,1²) E II x (SS) that satisfies: (i) (player rationality) {x = maxaen" J (R,1(") (ii) (Distribution consistency) The distribution flow j²¹ is equal to the distribution flow induced by the policy x².
Remark 1. Compared with Definition [ the definition of NE in MFG only involves the policy and the distribution flow of a single representative player, since the agents are homogeneous in MFGs.
4 Existence of the NEs in Regularized GMFGs and MFGs
We now state some assumptions to demonstrate the existence of a NE for X-regularized GMFGs.

---

Assumption 1. The state space S is compact, and the action space A is finite.
This assumption imposes rather mild constraints on S and A. In real-world applications, the states are usually physical quantities and thus reside in a compact set. For the action space, many deep reinforcement learning algorithms discretize the potential continuous action sets into finite sets Lowwe
et al. 2017 Mordatch and Abbeel 2018).
Assumption 2. The graphons for h E [H] are continuous functions.
The stronger version of this assumption (Lipschitz continuity) is widely adopted in GMFG works (Cui and Koeppl 2021b Fabian et al. [022]. It helps us to build the continuity of the transition kernels and rewards with respect to players.
Assumption 3. For all h E [H], the reward function ra(s, a, 2) is continuous on S x A x M(S), that is if (8nz Ons an;)2]) Zn) + (s. a, 2) as + oc, then Th (8n: Onl zn) (8, a, 2). The transition kernel Ph(. 8, a, 2) is weakly continuous in S x A x M(S), that is if (8ny Un 2n) - (8, a, 2) as P. 8, 2, weakly.
0C, Pa 88y On: Zn)
This assumption states the continuity of the models, i.e., the transition kernels and the rewards, as functions of the state, action, and aggregate. We note that the Lipschitz continuity assumption of the model in the previous works implies that our assumption satisfied [Cui and Koeppl 2021b Fabian Next, state the existence result of regularized GMFG.
al. 2022
Theorem 1. Under Assumptions (I,S,A, P.r, W. H1) admits an NE
and 3 for all X 2 0, the X-regularized GMFG E.
This theorem strengthens previous existence results in Cui and Koeppl [2021b] and Fabian al. [2022) in two aspects. First, our assumptions are weaker. These two existing works require a finite state space and the Lipschitz continuity of the models. contrast, we only need a compact state space and the model continuity. Second, their results only hold for the unregularized case (A = 0), whereas ours holds for any X 2 O. In the proof of Theorem [ we construct MFG from the given GMFG and show that an NE of the constructed MFG can be converted to an NE of the GMFG. Then we prove the existence of NE in the constructed regularized MFG. Our existence result for the regularized MFG is also a significant addition to the MFG literature.
Remark 2. Although we show that an NE of the constructed MFG can be converted to an NE of GMFG, this proof does imply that GMFG forms subclass of or is equivalent to MFG. This is because we have only demonstrated the relationship between the NEs of these two games, but the exact realizations of the GMFG and the conceptually constructed MFG may differ. It means that the sample paths of these two games may not be the same, which include the realizations of the states, actions, and rewards of all the players.
We next state the assumption needed for the MFG.
Assumption 4. The MFG (S,A, H. p,), satisfies that: (i) The state space S is compact, and the action space A is finite. (ii) The reward functions Fx,s,,, for h E [H] are continuous on S A (S). The transition kernels are weakly continuous on S A x A(S); that if (Sn, any Pn) + (s, μ) as n + oc, P- Sn, On pn) + Pa(- 5, weakly.
Then the existence of the NË is stated as follows.
Theorem 2. Under Assumption 4 the X-regularzied MFG MFG A, H. P,F,m) admits NE (R, ())
H A for any X 0.
Our result in Theorem imposes weaker conditions than previous works (Cui and Koeppl| 202 la
Anahtarci et al., 2022 to guarantee the existence of an NE. These existing works prove the existence of NE by assuming a contractive property and the finiteness of the state space. They also require strong Lispehitz assumption (Anahtarci et al., 2022), where the Lipschitz constants of the models should be small enough. In contrast, we only require the continuity assumption in Theorem 2 This due to our analysis of the operator for the regularized MFG and the use of Kakutani fixed point theorem Guide (2006).
5

---

Learning NE of Monotone GMFGs
In this section, we focus on GMFGs with transition kernels that are independent of the aggregate i.c. Ph: : S x A - S for h E [M] This model is motivated by the seminal work Lasry and Lions [2007]. where the state evolution in continuous-time MFG is characterized by the Fokker-Plank equation. However, the form of the Fokker-Plaa
equation results in the state transition of each player being independent of other players. This model is also widely accepted the discrete-
GMFG and MFG literature [Fabian et al. 2022
Perrin et al. 2020
Perolat et al. 2021
5.1
Monotone GMFG
We first generalize the notion of monotonicity from multi-populatio population MFGs in Perolat et al. 2021 to GMFGs.
Definition 3 (Weakly Monotone Condition), A GMFG said to be weakly monotone if for any pt. P. E ASS x A) and their marginalizations on the states 1²t f=² E A(S), we have
1. Σ (x ( Ww)) - ru (s, o Wh)) ds da S aEA
for all h E [H] where Wn is the underlying graphon. It strictly weakly monotone if the inequality is strict when p² + p².
In two MDPs induced by the distribution flows 1z² of n and jJ² of # the weakly monotone condition states that we can achieve higher rewards at stage h [H] by swapping the policies. This condition has two important implications. The first is the uniqueness of the NE.
Proposition 1. Under Assumptions
/ and a strictly weakly monotone X-regularized GMFG has unique NE for any À 2 0 to a zero-measure set on I with respect to the Lebesgue measure.
In the following, denote this unique NE (I+ _, 1), and aim to learn this NE. The second implication concerns the relationship between the cumulative rewards of two policies.
Proposition 2. Ifa X-regularized GMFG satisfies the weakly monotone condition, then for any two policies n T II and their induced distribution flows p.t f E A, we have
S," (T ,1²) ) Jaa(aa ,i)) JAa (1")) - ( .p²) da 50
If the >-regularized GMFG satisfies the strictly weakly monotone condition, then the inequality is strict when n- + 7
Proposition shoow that if we have two policies, we can improve the cumulative rewards on the MDP induced by these policies by swapping the policies. This implies an important property of the NE ( I.) Since T I is optimal on the MDP induced by μ nz we have fo J ( t0 . da 2
So (x==,,";))) da for any nh II. Then Proposition 2 shows that fo J ( م²) da Z So (> ) da for any policy -I and the distribution flow JN² it induces. This means that the NE policy gains cumulative rewards not less than any policy x² the MDP induced by ZF, This motivates the design of our NE learning algorithm.
5.2 Policy Mirror Descent Algorithm for Monotone GMFG
In this section, we introduce the algorithm to learn the NE, which is called MonoGMFG-PNM and whose pscudo-code is outlined in Algorithm T It consists of three main steps. The first step estimates the action-value function (Line 3). We need to evaluate the action-value function of a policy on the MDP induced by itself. This estimate can obtained for each player independently by playing the of several times. We assume access sub-module for this and quantify the estimation error in our analysis. The second step is the policy mirror descent (Line 4). Given Ar,. < 1, This step can be equivalently formulated
11 (-|s) = argmax PEA(A) - Am
[Q0) (
TH (f)pp) ( - AR(D)] - DuupllmA Vs

---

Algorithm MonoGMFG-PMD
Procedure:
1: Initialize Tf [(] Unif(A) for all S, [H] and
2: fort 2, . do
3: Compute the action-value function ") a, oi ,T) for all a E I and h E [H] where 14 is
the distribution flow induced by कद.
4: 1 (8) x (-18) 1-21% exp (n A. (.. for all E I and h E [H]
5: 1H+1, (1 s)= (1 (--3.)224..0 -.)) (,Un(((A)
6: end for
7:
Output म Unif( (T1127)
where R(p) - (p, log p) is the negative entropy function. This step aims to improve the performance of the policy ne on its own induced MDP. Intuitively, since the policy T- in NE performs better than के on the MDP induced by pf shown in Section 5.1 the improved policy T should be closer " than xT. The third step mixes the current policy with the uniform policy (Line 5) to encourage exploration.
MonoGMFG- PONGGMFFGPMDII is different from previous NE learning algorithms for monotone GMFG in Perolat al. [202T] Fabian et al. [2022] in three different ways. First, MonoGMFG-PMD designed to learn the NE of the X-regularized GMFG with À > 0, whereas other algorithms learn the NE of the unregularized GMFGs. As a result, our policy improvement (Line 4) discounts the previous but other algorithms retain T(A Second, our algorithm is discrete-time and thus amenable for practical implementation. However, other provably efficient algorithms evolve in continuous time. Finally, MonoGMPG- PMD encourages exploration in Line 5, which is important for the theoretical analysis. Such step is missing in other algorithms.
policy as
5.3 Theoretical Analysis for MonoGMFG-PMD with Estimation Oracle
This section provides theoretical analysis for the MonoGMFG-PMII algorithm given action-value function oracle in Line 3, i.e., QA Q,,aa. We denote the unique NE of the X-regularized GMFG as (T -.)) For any policy n² we measure the distance the policy - of NE using
H Σ h=1
D(T3)=
=
B
( (68)) do.
This metric measures the weighted KL divergence between policy TI and the NE policy, and the weights are the NE distribution flow y².
Theorem 3. Assume that the GMFG is strictly weakly monotone and we have action-value function oracle. Let Tt = 17 = O(T 1/2) and 3i = O(T in MonoGMFG- PMD. For any A we have
A log T T1/2
D
0
T
1=1
Theorem provides the first convergence rate result for a discrete-time algorithm on strictly weakly monotone GMFGs under mild assumptions. In contrast, Perolat al.) [2021), Fabian et al. [2022] only consider the continuous- time policy mirror descent, which is difficult for the practical implementation. and only provide the asymptotic consistency results. Geist et al. [021] derive exploitability results for a fictitious play algorithm but require the potential structure and the Lipschitzness of the reward function. Our proof for Theorem mainly exploits properties of NE discussed in Section 5.1 Concretely, we use the fact that the policy mirror descent procedure reduces the distance between the policy iterate and the NE as D( D(= s fo J> 1uf) J> "if da. Thus, the policy iterate becomes closer to the NE. However, the discretization error and the exploration influence (Line 5) also appear, requiring additional care to show that ((= ). in general, decreases.

---

Algorithm 2 Estimation of Action-value Function
Procedure:
1: Sample N players [i/ S [0, 1].
2: The 7th player implements Tt b, for i E [N], and the other players implement mł.
3: Collect data (( a2, ",,) 1,,, N.K.K of sampled players from K independent episodes.
4: Initialize H++ (s, a) = 0 for all s SE S, a E A and [N].
5: for time h = H ................................ do
6: for Player = 1, ,in parallel) do
7:
Qna argminn En= (f(s attn)) -r - Vi (s i/N (s)) ( (8, ), Teh (1,)) AR((Ti,) (:,)).
-V i/N
8:
ho
9:
end for
10:
end for
11: Output ( Ji,-=
5.4 Theoretical Analysis for MonoGMFG-PMD with General Function Classes
In this section, we remove the requirement that one is given oracle access to an action-value function and we estimate it in Line 3 of MonoGMFG-PMD using general function classes. We consider the action-value function class F = Fi x ... x FH. where Fú C { S x A + [0, (H - / + 1)(1
A log [A]]]] the class of action-value functions time h [H]. Then we estimate the action-value functions using Algorithm 2
This algorithm mainly involves two steps. The first is involves data collection (Line 3). Here assign policies to players and collect data from their interactions. We let the sampled players implement behavior policies ( b,, ". which can be different from { i/N ).N, This will not change the aggregate 2 (14, Wx) for any E I. since only a gero-measure set of players change their policies. The second is the action-value function estimation (Lines and 8). The action-value function is selected based on the previous value function, and the value function is updated from the derived estimate. This can be implemented parallel for all players. We highlight that the estimation analysis cannot leverage results from general non- paraparaeetrcc regression [Wainwright 2019), since the response variable h+1 is not independent of s ,, in our setting.
Assumption 5 (Realizabilitt). For any policy nI E II and the induced distribution flow y.² E Å, we have Q (. /=) E for h E [H].
This assumption ensures that we can find the nominal action-value function in the function class. For a policy π E II and function ʃ S x A + I. we define the operator (Tğ- M)s,a) = Pa (J :), TTTTtt (+is)) XR( (-1s)))) For policy nH and the induced distribution (s, x", " ,,²) = rs(s, a, =f) + (Tr" 2,. (s,a),
flow n we have Q
Assumption 6 (Completeness). For any policy n πI and the induced distribution flow 1st Å have that for all E Fut1. 2 Wi)) + (TT" f) For all E I, h H H-1]. 1].
This completeness assumption ensures that the estimates from F also satisfy the relationship between nominal action-value functions through 7,," These realizability and completeness assumptions are widely adopted in the off off-po evaluation and offline reinforcement learningg literature [Uchara et al. 2022
Xie et al. 2021b).
Assumption 7. The reward functions {ra)l M= are Lipschitz in z, i.e., [ra(s, - (s. 2')l s L, - 2' la for all s E S,a E A, h E [H]. The graphons for h E [H] are Lipschitz continuous functions, iee., there exists a constant I, Tw > 0 (depending only W [Wa)# such that
[W, 3) Wa(o', .8') S Lw((a- - o' + |B 311) for all a B, E [0,1], and h E [H].
The Lipschitzness assumption is common in the GMFG works [Parise and Ozdaglar 2019 Carmonal let al. 2022 Cui and Koeppl 20216). It helps us to approximate the action-value function of a player b,i by that of sampled players. We denote the state distributions of player i induced by policy n. as u
b,i Then require the behavior policies (T b. J to satisfy the following requirements.
8

---

Beach Problem with SBM-grashons
Beach Bar Problem with exp-graphons
10
10P
Expleitability
Expleitabiiity
12.1
12"1
35
30
20
Optimization Iteration
Optimization Iteration
(a) Beach Bar problem with SBM graphons
(b) Beach Bar problem with exp-graphons.
Figure I: Simulation results for Beach Bar problem with SBM and exp-graphons.
Assumption 8. For any E (T), the behavior policies explore sufficiently. More precisely, for any policy π E II and induced distributions E A(S)", we have supsES,oet .E Th(a s)/=[](( s) S C and supses dpp(s)/dpp (s) S for E [H] and i [N] where Cr,Cr are constants.
This assumption guarantees that the behavior policies explore the actions that may adopted by of and -.. Such an assumption is widely adopted in offline reinforcement learning and off aff-policy evaluation works (Uehara al., 2022 Xie et al. 2021b].
Theorem 4. Assume that the GMFG is weakly monotone and that Assumptions 3
and 8 hold.
Let q = = O(T 1/2) and B = 3 = O(T-1) in Algorithm (MonoGMFG- MMD). Then with probability at least 8. Algorithmss (antaimmmaaanndaa and yield
T
A Alog T VT
B2 log
TNH Nox K, F(mm)
H log N
D
I
CiC2
T
AVK
1=1
where Bи = H(1 + A Alog [A)), and No KK = max Noc Fk) is the -oo-rrnnn number of the function class.
The error in Theorem connsssss of both the optimization and estimation errors. The optimization error corresponds the first term, which also appears Theorem The estimation error consists of the generalization error and the approximation error, in the second and third terms respectively. When the function class F is finite, this term scales as OKK-1/2), 11/2), which originates from the fact that we estimate the action-value function from the empirical error instead of its population counterpart. The approximation еπтоr scales as O(N-1), This term originates from the fact that the action-vale value function of player approximated by that of the sampled player near a. To learn a policy that is most > far from the NE, we can set T = Ö(e=*) K Ó 2), and N Ö(e which in total results TK- = Ö(e episodes of online plays.
Experiments
In this section, we conduct experiments corroborate our theoretical findings. We run different algorithms on the Beach Bar problem Perrin et al.) [2020), Fabian et al. [2022]. The underlying graphons are set to Stochastic Block Model (SBM) and exp- axp-graphons. The details of experiments are deferred to Appendix B Since the NEs of the games are not available, we adopt the exploitability to measure the proximity between policy and the NE. For a policy xI and its induced distribution flow n==,, the exploitability for the X-regularized GMFG is defined as
L''' max RETT
Exploit
JA (x ,1= )da.
First, the experimental results demonstrate the necessity of modelling the heterogeneity of agents. F demonstrates the performance degradation of approximating GMFG by MFG. Here we let the agents play in the GMFG with constant graphons Wa(a, B) p for p E {0, 0.5, 1}. The agents have oracle access to the action-value function. We observe that this approximation results in gross errors for learning the NEs of GMFGs with non-constant graphons.
Second, the experiments show that the algorithms designed for unregularized GMFG cannot learn the NE of regularized GMFG, We implement the discrete-time version of the algorithm in Fabian et al.

---

2022|; results marked "Unreg PMD" show that the exploitability first decreases and then increases. In line with the discussion in Section 5.2] this originates from keeping too much gradient knowledge in previous iterates x². The gradient of the policy is largely correct in the several initial iterations, but a large amount of past knowledge results in it deviating in later iterations, since the past knowledge accumulates. In contrast, our algorithm discounts the past knowledge as (TT²) )
Finally, the results indicate the influence of action-value function estimation. In the experiments. we run our algorithm when N = 5, K 300, N = 10, K = 100, and N = 10, K = 300. Figure shows that the algorithm with N 10. K 300 can achieve smaller error than the algorithms both
with N = 10, K = 100 and N = 5, K 300. This is in agreement with Theorem
7 Conclusion
In this paper, we focused on two fundamental problems of X-regularized GMFG. Firstly, we established the existence of NE. This result greatly weakened the conditions in the previous works. Secondly, the provably efficient learning algorithms were proposed and analyzed in the weakly monotone GMFG motivated by] Lasry and Lions (2007]. The convergence rate of MonoGMFG-PMII features the first performance guarantee of discrete-time algorithm without extra conditions in monotone GMFGs. We leave the lower bound of this problem to the future works.
Acknowledgments and Disclosure of Funding
Fengzhuo Zhang and Vincent Tan acknowledge funding by the Singapore Data Science Consortium (SDSC) Dissertation Research Fellowship. the Singapore Ministry of Education Academic Research Fund (AcRF) Tier under grant number A-8000423-00-00 and AcRF Tier under grant numbers 1-8000980-00-00 and 1-8000189-01--0 Zhaoran Wang acknowledges National Science Founda- tion (Awards 2048075, 2008827, 2015568, 1934931), I), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their support.
References
Y. Achdou, P. Cardaliaguet, F. Delarue, A. Porretta, F. Santambrogio, Y. Achdou, and M. Laurière. Mean field games and applications: Numerical aspects. Mean Field Games: Cetraro, Italy 2019, pages 249-307, 2020.
B. Anahtarci, C. D. Kariksiz, and N. Saldi. Fitted gelaarning in mean-field games. arXiv preprint 1912. 2019.
B. Anahtarci, C. D. Kariksiz, and N. Saldi. Q-learning in regularized mean-field games. Dynamic Games and Applications, pages 1-29, 2022.
A. Aurell, Carmona, G. Dayamkhı, and M. Laurière. Finite state graphon games with applications to epidemics. Dynamic Games and Applications, 12(1):49-81, 2022a.
A. Aurell, R. Carmona, and M. Lauriere. Stochastic graphon games: Ii. the linear-quadratic case. Applied Mathematics & Optimization, 85(3):1-33, 2022b.
D. Bertsekas and S. E. Shreve. Stochastic optimal control: the discrete-time case, volume 5, Athena Scientific, 1996.
Q. Cai, Z. Yang. C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1296 PMLR, 2020.
E. Caines and M. Huang. Graphon mean field games and the gmfg equations: g-nash equilibria. In 2019 IEEE 58th conference on decision and control (CDC), pages 286-292. IEEE, 2019.
R. Carmona, D. B. Cooney, C. V. Graves, and M. Lauriere. Stochastic graphon games: I. the static case. Mathematics of Operations Research, 47(1):750-778, 2022.
S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2064)22563,2578 2022.
10

---

A. Cousin, S. Crépey, O. Guéant, D. Hobson, M. Jeanblanc, J. Lasry, J. Laurent, P. Lions, P. Tankov, and O. Guéant. Mean field games and applications. finance 2010, pages 205-266, 2011.
lectures on mathematical
K. Cui and H. Koeppl. Approximately solving mean field games via entropy-regularize deep reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1909-1917. PMLR, 2021a.
Kai Cui and Heinz Koeppl. Learning graphon mean field games and approximate nash equilibria. In International Conference on Learning Representations, 2021b.
C. Fabian, Cui, and H. Koeppl. Learning sparse graphon mean field games. arXiv preprint arXiv:2209.03888 2022.
M. Geist, B. Scherrer, and O. Pietquin. A theory of regularized markov decision processes. In International Conference Machine Learning, pages 2160-2169 PMLR, 2019.
M. Geist, J. Pérolat, M. Laurière, Elie, Perrin, Bachem, R. Munos, and O. Pietquin. Concave utility reinforcement learning: the mean-field game viewpoint. arXiv preprint arXiv:2066.0378. 2021.
A. H. Guide. Infinite dimensional analysis. Springer, 2006.
L. Györfi, M. Kohler, A. Krzyzak, and H. Walk. distribution-free theory of nonparametric regression, volume 1. Springer, 2002.
K. Hinderer. Foundations of non-stationary dynamic programming with discrete time parameter, 1970.
M. Huang, R. Malhamé, and P. E. Caines. Large population stochastic dynamic games: closed-loop mckean-vlasov systems and the nash certainty equivalence principle. 2006.
H.-J Langen. Convergence of dynamic programming models. Mathematics of Operations Research, 6(4):493-512, 1981.
J. Lasry and P. Lions. Mean field games. Japanese journal of mathematics, 2(1):229-260) 2007.
R. Lowe, Y. I. Wu, A. Tamar, J. Harb, OpenAl Pieter A., and Mordatch. Multi-agent actor-critic for mixed cooperative-competiii environments. Advances in neural information processing systems, 30, 2017.
I. Mordatch and P. Abbeel. Emergence of grounded compositional language in multi-agent popula- tions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Francesca Parise and Asuman Ozdaglar. Graphon games. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 457-458, 2019.
J. Perolat, S. Perrin, R. Elie, M. Laurière, G. Piliouras, M. Geist, K. Tuyls, and O. Pietquin. Scaling up mean field games with online mirror descent. arXiv preprint arXiv:2103.00623, 2021.
S. Perrin, J. Pérolat, M. Laurière, M. Geist, R. Elie, and O. Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems, 18:13199-13213 2020.
L. Shani, Y. Efroni, and S. Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5668-5675, 2020.
E. Sonu, Y. Chen, and P. Doshi. Decision-theoreth planning under anonymity in agent populations. Journal of Artificial Intelligence Research, 59:725-770, 2017.
M. Uehara, C. Shi, and N. Kallus. review of off-policy evaluation reinforcement learning. arXiv preprint ar 2IX.:22112.06355. 2022.

---

D. Vasal, R. K. Mishra, and S. Vishwanath. Master equation of discrete time graphon mean field games and teams. arXiv preprint arXiv:2001.05633, 2020.
M. J. Wainwright. figghdiieesiooal statistics: non-asymplotic viewpoint, volume 48, Cambridge university press, 2019.
L. Wang, Z. Yang. and Z. Wang. Breaking the curse of many agents: Provable mean embedding Q- iteration for mean-field reinforcement learning. In International Conference on Machine Learning. pages 10092 10103. PMLR, 2020.
Q Xie, Z. Yang, Z. Wang, and Minca. Learning while playing mean-field games: Convergence and optimality. In International Conference on Machine Learning, pages 11366-11447 PMLR, 2021a.
Xie, C. Cheng, Jiang, P. Mineiro, and A. Agarwal. Bellman-consisten pessimism for offline reinforcement learning. Advances in neural information processing systems, 6666683-6694, 2021b.
B. Yardim, S. Cayci, M. Geist, and N. He. Policy mirror ascent for efficient and independent learning in mean field games. arXiv preprint arXiv:2212.144493 2022.
M. A. uz Zaman, A. Koppel, S. Bhatt, and T. Basar. Oracle-free reinforcement learning in mean-field games along single sample path. arXiv preprint arXiv:2208. //60: 2022.
12


Reviews:
[{"review_id": "SII8A81aYE", "reviewer": "Reviewer_eGqz", "summary": "This paper studies regularized Graphon Mean-Field Games (GMFGs). They make two theoretical improvements over previous works on this topic:\n* They prove existence of Nash equilibrium under weaker assumptions (e.g., weaker requirement on the continuity of the game) than previous works.\n* 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).\n\nIn 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.", "questions": "Could you elaborate why the new equilibrium existence results are more applicable than previous works with concrete examples?\n\nWhat are the concrete benefits of the exploration step (Line 5 of Algorithm 1) in your learning algorithm? Is it necessary for proving your result?", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "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": "\nAs 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.\n\nThe 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].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. We address the major concerns in the following.\n\n**Detailed Comparison of NE Existence Conditions**\n\nTheorems 1 and 2 in our work,  Proposition 3 in [1], and Proposition 3 in [2] all derive the existence of Nash Equilibrium (NE) in the regularized Mean-Field Games (MFG) or Graphon Mean-Field Games (GMFG). Our results in Theorems 1 and 2 hold for continuous reward functions, weakly continuous transition kernel, Lipschitz graphons, and any value of regularization parameter $\\lambda\\geq 0$. In contrast, Proposition 3 in [1] proves the existence of NE via contraction, which requires that $K_{H}<1$ therein. From the definition of $K_{H_1}$ and $K_{1}$, the condition $K_{H}<1$ requires that the Lipschitz constants of transition kernels, and reward functions to be sufficiently small. Proposition 3 in [2] requires that the regularization parameter $\\lambda$ should be sufficiently larger than the Lispchitz constants of the game operators. These conditions are restrictive for real-world applications. In addition, our results hold for compact state space, but [2] is constrained to the setting with finite state space.\n\nTheorem 1 in our work, Theorem 1 in [3], and Theorem 1 in [4] all consider the existence of NE in GMFGs. However, [3] and [4] only prove the existence of NE in the unregularized case under the Lipschitz continuity of the transition kernels and reward functions. In contrast, our work provides the results for all $\\lambda\\geq 0$, including both the regularized and unregularized cases, under the continuity of reward functions and the weak continuity of transition kernels.\n\n**Algorithm Comparison With Perolat et al. [2021]**\n\nWe would like to highlight three main differences between our algorithm and the algorithm in [5].\n\nFirst, our provably efficient algorithm is discrete-time, while the one in [5] is continuous-time. In the realistic application of the algorithm, the optimization can only be implemented in a discrete-time manner, which introduces additional quantization error for the one in [5]. In contrast, our discrete-time algorithm does not suffer from this additional error.\n\nSecond, our optimization algorithm does not assume that we have access to the nominal value of the action-value functions, while [5] only analyzes the algorithm with the true action-value functions. The analysis of the algorithm with action-value function estimates requires a perturbation analysis of the algorithm, which is important for applications to realistic scenarios.\n\nFinally, our algorithm has an additional exploration procedure that is not included in [5]. Intuitively, this procedure guarantees that the support of the NE policy is contained in that of the policy estimate in each step, which accommodates the potential error originating from the action-value function estimation and the quantization. Technically, this guarantees that the KL divergence between the NE policy and the policy estimate in each iteration is finite, as shown in (F.1) in Appendix.\n\n[1] B. Anahtarci, C. D. Kariksiz, and N. Saldi. Q-learning in regularized mean-field games. Dynamic Games and Applications 13.1 (2023): 89-117.\n\n[2] K. Cui, and H. Koeppl. Approximately solving mean field games via entropy-regularized deep reinforcement learning. International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n[3] K. Cui, and H. Koeppl. Learning graphon mean field games and approximate Nash equilibria. In International Conference on Learning Representations (2022).\n\n[4] F. Christian, K. Cui, and H. Koeppl. Learning sparse graphon mean field games. International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n\n[5] J. Perolat, et al. \"Scaling up mean field games with online mirror descent.\" arXiv preprint arXiv:2103.00623 (2021)."}, {"review_id": "QxKw2ODuqK", "reviewer": "Reviewer_Epba", "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. \n\nThe 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.\n\n* 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). \n\n* 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). \n\nA small set of experiments suggests that the authors' method performs well in practice, and also that regularization is important to achieve good performance. \n\n   ", "questions": "These are simply rewordings of my comments on weaknesses. \n\nQ1: 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.\n\nQ2: 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? ", "limitations": "None were discussed, but I don't think there was any need to do so. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is original and significant. It is also quite clear. The following two points stand out. \n\n* The existence results work under weak conditions because of the clever use of \"soft\" techniques. \n* The algorithms work under relatively natural conditions.  ", "weaknesses": "* It is not clear to me if the Lipschitz assumption on $W$ is really needed. \n* 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.)\n* 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.  \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. We address the major concerns in the following.\n\n**Lipschitz Continuity of $W$**\n\nWe thank the reviewer for this suggestion. For the proof of Theorem 1, the Liphschitz assumption on $W$ is only used to establish (D.5), and this can be proved with continuity assumption. We will modify this in the revised version. \n\n**Novelty of Theorem 4**\n\nThe learning error bound in Theorem 4 mainly consists of two terms: the optimization error and the estimation error. We would like to discuss them separately.\n\nFirst, the optimization error analysis in Theorem 4 is a direct adaption of Theorem 3. This is the first analysis of the discrete-time algorithm only under the monotone condition even in the Mean-Field Games (MFG) problem, a subclass of Graphon Mean-Field Games (GMFG) with constant graphons. Here we make use of the intuition provided by Proposition 2 to guide the analysis of the policy mirror descent in a non-stationary environment.\n\nSecond, the estimation error is analyzed with the general function approximation and provides the error dependency on the number of episodes $K$ and the number of sample agents $N$. This analysis is important for the realistic application of the algorithm, where the algorithm needs to estimate the action-value function from samples. Our results provide the guidance to choose the parameters $T$, $N$, and $K$ to achieve a learning error $\\varepsilon$.\n\n**Regularization Explanation**\n\nFirst, we note that the regularized setting itself is important in the MFGs, a subclass of GMFGs. In the real-world applications, there are usually constraints about the safety and the incentives for the exploration in the learning process, and people formulate these requirements via regularizations. The regularized setting is widely studied in MFGs [1,2,3]. Our work follows this thread and consider learning NE for the regularized GMFGs.\n\nSecond, we would like to quantify the difference between the NEs of the regularized GMFGs and the unregularized GMFGs. Here, we denote the NE of the $\\lambda$-regularized one as $(\\pi^{\\ast,\\mathcal{I}},\\mu^{\\ast,\\mathcal{I}})$ and denote the optimal policy of the unregularized MDP induced by $\\mu^{\\ast,\\mathcal{I}}$ as $\\pi^{\\mathcal{I}}$. Now we examine how far $(\\pi^{\\ast,\\mathcal{I}},\\mu^{\\ast,\\mathcal{I}})$ is from the NE of the unregularized GMFGs. We note that $\\mu^{\\ast,\\mathcal{I}}$ is induced by the policy $\\pi^{\\ast,\\mathcal{I}}$, and thus they satisfy the distribution consistency condition. For the player rationality condition, Theorem 2 in [4] shows that $V_{1}^{0,\\alpha}(s,\\pi^{\\alpha},\\mu^{\\ast,\\mathcal{I}})\\leq V_{1}^{\\lambda,\\alpha}(s,\\pi^{\\alpha},\\mu^{\\ast,\\mathcal{I}})+\\lambda H\\log|\\mathcal{A}|$ for all $\\alpha\\in[0,1]$ and $s\\in\\mathcal{S}$. Therefore, $(\\pi^{\\ast,\\mathcal{I}},\\mu^{\\ast,\\mathcal{I}})$ satisfies the player rationality condition up to $\\lambda H\\log|\\mathcal{A}|$. We highlight that this gap also appears in the MFG works [1,2]. Our work focuses on learning the regularized GMFGs and leaves easing this gap as the future work.\n\n[1] B. Anahtarci, C. D. Kariksiz, and N. Saldi. Q-learning in regularized mean-field games. Dynamic Games and Applications 13.1: 89-117  (2023).\n\n[2] Q. Xie, Z. Yang, Z. Wang, and A. Minca. Learning while playing in mean-field games: Convergence and optimality. In International Conference on Machine Learning (pp. 11436-11447). PMLR (2021).\n\n[3] B. Yardim, S. Cayci, M. Geist, N. He. Policy mirror ascent for efficient and independent learning in mean field games. In International Conference on Machine Learning (pp. 39722-39754). PMLR (2023).\n\n[4] M. Geist, B. Scherrer, and O. Pietquin. A theory of regularized markov decision processes. International Conference on Machine Learning. PMLR, (2019)."}, {"review_id": "TVlZmOsWRm", "reviewer": "Reviewer_veSy", "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.", "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.\n\nLine 230: The statement regarding switching policies is not clear to me. In general, is there an intuitive explanation of the weak monotonicity assumption?\n\nHow 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.\n", "limitations": "Potential additional limitations to be discussed were mentioned in the weaknesses and limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\nThe 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).\n\nFurthermore, 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.\n\nTable 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.\n\nExperimental results are restricted to toy problems, however, it is possible that no alternative benchmarks exist for GMFG.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. We address the major concerns in the following.\n\n**Empirical Action-Value Function Estimation and Simulation Benchmark**\n\nOur work focuses on the optimization complexity and the sample complexity of the algorithms. The efficacy of our proposed algorithms, including the action-value function estimation, is corroborated in the simulation results. We note that there is no benchmark for GMFGs, and we follow the experiment settings in the previous works [1,2]. \n\nWe note that Line 7 in Algorithm 2 may incur potentially computational cost for the action-value function estimation. However, this step has closed-form expressions for the tabular case, which includes a wide range of applications[3]. For the more complex environment, this step can be implemented via gradient descent. We leave the application of our algorithms, especially the action-value function estimation, on them as future work.\n\n**Comparison of Different Monotone Conditions and Contraction**\n\nWe first provide a comparison between the different monotone conditions. Our work, [1], and [4] all consider the monotone condition for multi-population/graphon mean-field games. [1] defines the inequality in our Proposition 2 as the monotone condition. [4] defines the monotone condition for multi-population MFGs, and the monotone condition in our work can recover their definition by setting the graphons as block-wise constant graphons in Definition 3. [2] and [5] consider the monotone condition for MFGs. The definition of monotone condition in [5] is a special case of the definition in [4] by setting the number of populations as one. The definition in [2] is a special case of [5], where the reward functions are the sum of the distribution flow-independent part and the distribution flow-dependent part.\n\nThe literature of MFGs, a subclass of GMFGs, is split into two threads: the contraction condition and the monotone condition. We note that the comparison between the monotonicity and the contraction is open even for MFGs. \n\n\n**Example of Covering Numbers**\n\nWe give some examples of the covering number of the function class. Consider a one-dimensional parametric function class $\\mathcal{F} _{\\mathrm{exp}}=\\lbrace f _{\\theta}:[0,1]\\rightarrow\\mathbb{R}\\,|\\,\\theta\\in[0,1]\\rbrace$, where $f _{\\theta}= 1-\\exp(\\theta x)$. The covering number is $\\log \\mathcal{N} _{\\infty}(\\delta,\\mathcal{F} _{\\mathrm{exp}})\\asymp \\log(1/\\delta)$ as $\\delta\\rightarrow 0$ [6]. Consider a non-parametric function class $\\mathcal{F} _{L}=\\lbrace g:[0,1]\\rightarrow\\mathbb{R}\\,|\\, g(0)=0, |g(x)-g(y)|\\leq L|x-y| \\text{ for all }x,y\\in[0,1]\\rbrace$. The covering number is $\\log \\mathcal{N} _{\\infty}(\\delta,\\mathcal{F} _{\\mathrm{exp}})\\asymp L/\\delta$ as $\\delta\\rightarrow 0$ [6].\n\n\n**Explanation of the Switching Policies Argument**\n\nThe statement regarding switching policies can be clarified through Proposition 2. Here we note that Proposition 2 states that for $\\pi^{\\mathcal{I}}$, $\\tilde{\\pi}^{\\mathcal{I}}$ and the corresponding distribution flows $\\mu^{\\mathcal{I}}$,$\\tilde{\\mu}^{\\mathcal{I}}$, implementing policies $\\tilde{\\pi}^{\\mathcal{I}}$, $\\pi^{\\mathcal{I}}$ on the MDPs induced by $\\mu^{\\mathcal{I}}$, $\\tilde{\\mu}^{\\mathcal{I}}$ will have higher rewards than implementing policies $\\tilde{\\pi}^{\\mathcal{I}}$, $\\pi^{\\mathcal{I}}$ on the MDPs induced by themselves. Thus, switching policies can get higher rewards on at least one of the MDPs induced by $\\mu^{\\mathcal{I}}$ and $\\tilde{\\mu}^{\\mathcal{I}}$.\n\n**Comparision with MFG results**\n\nWe highlight that our results for GMFGs directly imply the results for MFGs when the graphons are constant graphons. For example, with constant graphons, Theorem 3 implies that the convergence rate of Algorithm 1 for MFGs is $\\tilde{O}(T^{-1/2})$ in the sense of the KL divergence. Theorem 3 in [4] shows that with the additional potential structure, the fictitious play algorithm converges at rate $O(T^{-1/2})$ in the sense of exploitability. We can prove that the performance guarantee in KL divergence implies that in exploitability, and the resultant bound for our algorithm is $\\mathrm{Exploit}(\\hat{\\pi})=\\tilde{O}(T^{-1/4})$. Although the rate is slower that $O(T^{-1/2})$ in [4], we do not require the potential structure. The reason for an additional square root here is that we adopt Pinsker’s inequality, and this may be improved with a tighter distribution flow error analysis than the following analysis.\n\nHere we specify the main proof ideas. For a policy $\\pi$ that is close to NE policy $\\pi^{\\ast}$ in KL, we denote the distribution flow induced by $\\pi$ as $\\mu$ and denote the optimal policy on the MDP induced by $\\mu$ as $\\tilde{\\pi}^{\\ast}$. We aim to prove that the difference between the cumulative rewards of $\\tilde{\\pi}^{\\ast}$ and $\\pi$ on $\\mu$ is bounded. This can be achieved by noting that: 1. The performance difference lemma can bound this with the Total Variation (TV) between $\\pi$ and  $\\tilde{\\pi}^{\\ast}$. 2. The TV between $\\tilde{\\pi}^{\\ast}$ and $\\pi^{\\ast}$ is proportional to the TV between $\\mu$ and $\\mu^{\\ast}$, since they are the optimal policies on the MDPs induced by $\\mu$ and $\\mu^{\\ast}$. 3. $\\mu$ and $\\mu^{\\ast}$ are close since they are induced by $\\pi$ and $\\pi^{\\ast}$.\n\n[1] C. Fabian, K. Cui, and H. Koeppl. Learning sparse graphon mean field games. Aistats PMLR, 2023.\n\n[2] S. Perrin, et al. Fictitious play for mean field games: Continuous time analysis and applications. Neurips 33 (2020).\n\n[3] A. Aurell, et al. \"Finite state graphon games with applications to epidemics.\" Dynamic Games and Applications 12.1 (2022).\n\n[4] J. Perolat, et al. Scaling up mean field games with online mirror descent. arXiv:2103.00623(2021).\n\n[5] M. Geist, et al. Concave utility reinforcement learning: the mean-field game viewpoint. arXiv:2106.03787(2021).\n\n[6] M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge university press, 2019."}, {"review_id": "XECbRgEKE2", "reviewer": "Reviewer_NT3m", "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.\n", "questions": "I mainly work on Stochastic game theory, not mean field game, so some of my questions might be quite basic.\n\n1. 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?\n\n2. 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?\n\n3. Is the analysis linked to this paper? It'd be helpful to know the technical differences between [1] and this paper.\n[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.\n\nIf this is well-addressed, I am down to re-evaluate this paper.", "limitations": "The authors adequately addressed the limitation and potential negative societal impact on their work.\n\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n2. PMD for the general function approximation is impressive. The decision to employ policy mirror descent adds an interesting dimension to the methodology.\n\nThe 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. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. We address the major concerns in the following.\n\n**Relationship between NEs of $\\lambda$-regularized GMFGs and MFGs**\n\nTo build an NE of $\\lambda$-regularized GMFGs from an NE of the constructed $\\lambda$-regularized MFG, we take the position of the agent as a state in the MFG. This method is partially covered by [1], but we are the first to provide the mathematically strict proof of this method.\n\n**Novelty of Step 3 in the Proof of Theorem 1**\n\nYes, the work  [1] only considers the unregularized case in Step 3. In contrast, we cope with the regularized MFGs and prove Theorem 2. This requires us to prove the corresponding regularized game operator is closed, and we achieve this by constructing a set $A_{h}^{(n)}$ in Lines 721 and 722 and proving Proposition 8.\n\n**Regularization Explanation**\n\nRegularization is a standard technique in game theory. In GMFGs, it helps us to uniquely define the optimal policy of the MDP induced by any distribution flow. The regularization also makes sure that the optimal policy is not a degenerate distribution, and thus makes KL divergence an appropriate performance metric for us to analyze.\n\n\n**Comparison With Zhan et al. 2023**\n\nWe would like to highlight that we consider a different problem as [2]. They analyze the performance of policy mirror descent in a fixed MDP. In contrast, we analyze the policy mirror descent in a non-stationary MDP, and the non-stationarity originates from that the reward functions change according to the distribution flows induced by the policies.\n\n[1] K. Cui, and H. Koeppl. Learning graphon mean field games and approximate Nash equilibria. In International Conference on Learning Representations (2022).\n\n[2] 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"}]

Author rebuttal:

Meta-review: This paper presents a compelling exploration of regularized Graphon Mean-Field Games (GMFGs) and offers valuable contributions to this research area. It tackles the challenging problems of establishing Nash Equilibrium (NE) existence in regularized GMFGs and devising efficient algorithms for learning NE in weakly monotone GMFGs. Notably, the paper establishes a novel link between regularized GMFGs and regularized Mean-Field Games (MFGs), shedding light on a method for constructing NEs using MFGs as an intermediate step. The provided empirical evaluations, though limited to toy problems, reinforce the practical applicability of the proposed algorithms. While the paper could benefit from improved clarity in some sections and deeper comparisons with related work, it contributes to the understanding and efficient solution of regularized GMFG and constitutes a technically solid contribution.
Decision: Accept (poster)