Learning Graphon Mean Field Games and Approximate Nash Equilibria
Authors: Kai Cui
Heinz Koeppl
Venue: ICLR 2022 Poster (2022)
Keywords: Mean Field Games
Reinforcement Learning
Multi Agent Systems

Abstract: Recent advances at the intersection of dense large graph limits and mean field games have begun to enable the scalable analysis of a broad class of dynamical sequential games with large numbers of agents. So far, results have been largely limited to graphon mean field systems with continuous-time diffusive or jump dynamics, typically without control and with little focus on computational methods. We propose a novel discrete-time formulation for graphon mean field games as the limit of non-linear dense graph Markov games with weak interaction. On the theoretical side, we give extensive and rigorous existence and approximation properties of the graphon mean field solution in sufficiently large systems. On the practical side we provide general learning schemes for graphon mean field equilibria by either introducing agent equivalence classes or reformulating the graphon mean field system as a classical mean field system. By repeatedly finding a regularized optimal control solution and its generated mean field, we successfully obtain plausible approximate Nash equilibria in otherwise infeasible large dense graph games with many agents. Empirically, we are able to demonstrate on a number of examples that the finite-agent behavior comes increasingly close to the mean field behavior for our computed equilibria as the graph or system size grows, verifying our theory. More generally, we successfully apply policy gradient reinforcement learning in conjunction with sequential Monte Carlo methods.

Published as a conference paper at ICLR 2022
LEARNING GRAPHON MEAN FIELD GAMES AND APPROXIMATE NASH EQUILIBRIA
Kai Cui & Heinz Koeppl
Department of Electrical Engineering, Technische Universität Darmstadt, Germany (kai. cui, heinz koeppl 1 @bcs tu-darmstadt.
ABSTRACT
Recent advances at the intersection of dense large graph limits and mean field games have begun to enable the scalable analysis of broad class of dynamical sequential games with large numbers of agents. So far, results have been largely limited to graphon mean field systems with continuous-time diffusive or jump dynamics, typically without control and with little focus computational meth- ods. We propose a novel discrete-time formulation for graphon mean field games the limit of non-linear dense graph Markov games with weak interaction. On the theoretical side, we give extensive and rigorous existence and approximation properties of the graphon mean field solution in sufficiently large systems. On the practical side, we provide general learning schemes for graphon mean field equi- libria by either introducing agent equivalence classes or reformulating the graphon mean field system as a classical mean field system. By repeatedly finding a reg- ularized optimal control solution and its generated mean field, we successfully obtain plausible approximate Nash equilibria in otherwise infeasible large dense graph games with many agents. Empirically, we are able demonstrate on a number of examples that the finite-agent behavior comes increasingly close to the mean field behavior for our computed equilibria as the graph or system size grows, verifying our theory. More generally, we successfully apply policy gradient rein- forcement learning in conjunction with sequential Monte Carlo methods.
INTRODUCTION
Today, reinforcement learning (RL) finds application in various application areas such as robotics (Kober al.] (203)), autonomous driving (Kiran et al. 202T) or navigation of stratospheric balloons [Blllemare et al.) 2020) as a method to realize effective sequential
maaiiinnnmainnn in complex problems. RL remains a very active research area, and there remain many challenges multi-agent reinforcement learning (MARL) as generalization of RL such learning goals, non-stationarity and scalability of algorithms (Zhang et al., 202T). Nonetheless, potential applications for MARL manifold and include e.g. teams of unmanned aerial vehicles (Tožička et al.) 2018 Pham al, 2018) or video games (Berner et al.) 2019; Vinyals et al. 2017). While the domain MARL is somewhat empirically successful, problems quickly become intractable the number of agents grows, and methods MARL typically miss a theoretical foundation. A recent tractable approach to handling the scalability problem in MARL are competitive mean field games and cooperative mean field control (Gu et al. 2021). Instead of considering generic multi agent Markov games, one considers many agents under the weak interaction principle, i.e. each agent alone has a negligible influence on all other agents. This class of models naturally contains a large number of real world scenarios and can find application e.g. analysis of power network resilience (Bagagiolo Bauso) 2014), smart heating Kizilkale & Malhame, 2014), edge computing (Banez et al. (019)) or flocking (Perrin et al. 2021b).
See also Djehiche et al. (2017) for review other engineering applications.
Mean field games. Mean field games (MFGs) were first popularized in the independent seminal works of Huang et al. (2006) and Lasry & Lions (2007) for the setting of differential games with diffusion-type dynamics given by stochastic differential equations. See also Guéant al. (2011); Bensoussan et al.] (2013) for a review. Since then, extensions have been manifold and include e.g. discrete-time (Saldi al. 2018), partial observability (Saldi al. 2019), major-minor formulations

---

Published as a conference paper at ICLR 2022
(Nourian & Caines
2013) and many more. In the learning community, there has been immense
recent interest in finding and analyzing solution methods for mean field equilibria
(Cardaliaguet &
Hadikhanloo/ 2017; 2017, Mguni et al. 2018; Guo et al.
2019; Subramanian & Mahajan Eli et al.)
J020)CCur & Koeppl] 2021 Pasztor et al. 2021 Perolat et al. [022] Perrin et al.
2021a), solving
the inverse reinforcement learning problem YYang al. 2018a) applying related approximations
directly to MARL (Yang et al. 2018b). In contrast to our work, Yang et al. (2018a) consider states instead of agents on a graph, while Yang et al. (0018) requires restrictive assumptions and only considers averages instead of distributions of the neighbors. Recently, focus increased also on the cooperative case of mean field control (Carmona et al.) 2019b] |Mondal et al.) (02T), for which dynamic programming holds on an enlarged state space, resulting in high-dimensional Markov
decision process (Pham & Wei 2018 Motte
Pham 2019
Gu et al. 2020 Cui et al. 2021).
Mean field systems on graphs. For mean field systems on dense graphs, prior work mostly con- siders mean field systems without control ( (Vizuete et al. 2020) or time-dynamics, i.c. the static case (Parise & Ozdaglar 2019; Carmona et al.) 2019a). To the best of our knowledge, Gao & Caines (217)) and Caines & Huang (2019) are the first to consider general continuous-time diffusion- graphon mean field systems with control, the latter proposing many clusters of agents as well as proving an approximate Nash property as the number of clusters and agents grows. There have since been efforts to control cooperative graphon mean field systems with diffusive linear dynamics using spectral methods (Gao & Caines 2019a bj. On the other hand, Bayraktar al. (2020); Bet et al. (0200) consider large non-clustered systems in a continuous-tine diffusion-type -type setting without con- trol, while Auuell et al. (2021b) and Aurell et al. (2021a) consider continuous- -ime linear-quadranl systems and continuous time jump processes respectively. To the best of our knowledge, only Vasal jet al. (2021) have considered solving and formulating a graphon mean field game in discrete time, though requiring analytic computation of an infiiie-dimenniionll value function defined over all mean fields and thus being inapplicable to arbitrary problems in a black-box, learning manner. In contrast, give general learning scheme and also provide extensive theoretical analysis of our algorithms and (slightly different) model. Finally, for sparse graphs there exist preliminary results (Gkogkas& & Kuehn 2020; Lacker & Soret, 2020), though the setting remains to be developed.
Our contribution. In this work, we propose a dense graph limit extension of MFGs in discrete time, combining graphon mean field systems with mean field games. More specifically, we consider limits of many-agent systems with discrete-time graph- dynamics and weak neighbor interac- tions. In contrast to prior works, we consider one of the first general discrete-time formulations as well as its controlled case, which is a natural setting for many problems that are inherently discrete in time or to be controlled digitally at discrete decision times. Our contribution can be summarized as: (i) formulating one of the first general discrete-time graphon MFG frameworks for approximat- ing otherwise intractable large dense graph games; (ii) providing extensive theoretical analysis of existence and approximation properties in such systems; (iii) providing general learning schemes for finding graphon mean field equilibria, and (iv) empirically evaluating our proposed approach with verification of theoretical results in the finite N-agent graph system, finding plausible approximate Nash equilibria for otherwise infeasible large dense graph games with many agents.
2 DENSE GRAPH MEAN FIELD GAMES
In the following, we will give a dense graph N-agent model as well as its corresponding mean field system, where agents are affected only by the overall state distribution of all neighbors, as visualized in Figure [] As a result of the law of large numbers, this distribution will become deterministic - the mean field a review. The study of dense large graph limits deals with the limiting representation of adjacency matrices called graphons. Define I := 10. and Wo the space of all bounded, symmetric and measurable functions (graphons) W E Wo W: I x I - IR bounded by 0 < W < 1. For any simple graph G (II,...,N) NN, E),, we define its step-graphon a.c. uniquely by
N + J0. We begin with graph- traph-theoretical preliminaries,
also Lovász (2012) for
Wo(z.v)
Σ (JE(L....))
10.ee 1 +1 1 1E((
(1)
2

---

Published as a conference paper at ICLR 2022
(8)
(b)
(c)
1.0
6
2x0.5
0.5
00
1.0 0.0
1.0
Figure I: Graphical model visualization. (a): A graph with 5 nodes; (b): The associated step
graphon of the graph in (a) continuous domain version of its adjacency matrix; (c): A visualiza- tion of the dynamics, i.c. the center agent is affected only by its neighbors (grey).
see e.g. Figure We equip Wo with the cut (semi-)norm ||-I|- and (pseudo-)metris do
[iln == sup
W(z, v) dr dy
6n, W*) inf] W ll,,
8,T SxT
for graphons W, W E Wo and (z, (w((()) p(v)); where the supremum is over all measurable subsets S,T S and the infimum is over measure-preserriig bijections yp: I - I.
To provide motivation, note that convergence in 83 is equivalent to e.g. convergence of probabil- ities of locally encountering any fixed subgraph by randomly sampling a subset of nodes. Many such properties graph sequences (Gn)New New converging to some graphon W Wo can then be described by W, and we point to Lovász (2012) for details. In this work, we will primarily use the analytical fact that for converging graphon sequences |[aN W + 0, we equivalently have
J.Il (WGx (a, B) ()),)))))()))))))) d3 da + sup
|Way W
(3)
under the operator norm of operators Loo + L1, see e.g.
Lovász 2012). Lemma 8.11.
By Lovász 2012). Theorem 11.59, the above is equivalent convergence in the cut metric 6n GN. -) O p to relabeling. In the following, we will therefore assume sequences of simple graphs Gn (VN, Ex) with vertices Vv [I.....Ny edge sets EN. edge indicator variables (KJ)EE for all nodes i, E VN. and associated step graphons WN converging in cut norm.
Assumption 1. The sequence of step-graphone (Wn)Nen converges in cul norm |1-I|p or equiva- lently operator norm [I-Il--- N + oo to some graphon W Wy i.e.
[WN l O, |[Nx - WilL -
Next, we define W-random graphs to consist of vertices Vy = (I....,N .N. with adjacency matrices y generated by sampling graphon indices a, uniformly from I and edges 4% Bernoulli (a,, ay)) ) for all vertices i,j VN. For experiments, by Lovász (012)). Lemma 10.16, we can thereby generate a.s. converging graph sequences by sampling -randoo graphs for any fixed graphon W Wy. In principle, whenever a valid relabeling function yo is known.
could also consider arbitrary graph generating processes
In work, the usage of graphons enables to extend the expressiveness of classical MFGs. As examples, we will use the limiting graphons of uniform attachment, ranked attachment and p-Erdös-Rényi (ER) random graphs given by max(x, y). Wrank (z. y) = xy and Wer (z, y) = p respectively (Borgs et al. 2011 Lovász 2012). each of which exhibits different node connectivities as shown in Figure
find mean field systems dense graphs and
Wunit x, y)
2,0
50.5
Wesl
0.3
0.0
0.0
0.01
Figure 2: Three graphons used in our experiments. (a): Uniform attachment graphon; (b): Ranked attachment graphon; (c): Réndi (ER) graphon with edge probability 0.5.
3

---

Published as a conference paper at ICLR 2022
Finite agent graph game. For simplicity of analysis, we consider finite state and action spaces X. as well as times T == {0, (0......:7 - 1}. On a metric space A, define the spaces of all Borel probability measures P(A) and all Borel measures Bi (AA) bounded by 1, equipped with the L norm. For simplified notation, we denote both a measure v and its probability mass function by v(.). Define the space of policies IT == P(4) i.e. agents apply Markovian feedback policies r = (TT)EET E II that act on local state information. This allows for the definition of weakly interacting agent state and action random variables
X ~ po:
U ~ x | X(), X ~ P(: P( GJ), TE VN
(5)
under some transition kernel P: X' Ex xB (2) + P(X), where the empirical neighborhood mean field Gj of agent is defined as the (2t) (unnormalized) neighborhood state distribution
G
Σ Ox
(6)
N
JEVN
where 8 is the Dirac measure, i.e. each agent affects each other at most negligibly with factor 1/N. Finally, for each agent we define separate, competitive objectives
(N ....,
" N E
Σ rx G.
to be maximized over n², where r X x u x Bi - R is an arbitrary reward function.
Remark 1.
We can also consider infinite horizons, J.
, = [Ei f'r(X; Uj. GD]
with all results but Theorem 4 holding. One may also extend state-action distributions, heteroge- neous starting conditions and tmme-dependent r, P, though we avoid this for expositional simplicity.
Remark 2. Note that it is straightforward to extend to heterogeneous agents by modelling agent types as part of the agent state, see also e.g. Mondal et al. (202I). It is only required to model agent states in a unified manner, which does not imply that there can be no heterogeneity.
With this, we can give a typical notion of Nash equilibria as found e.g. in Saldi et al. (2018). How- ever, under graph convergence in Assumption [T] is always possible for a finite number of nodes to have an arbitrary neighborhood differing from the graphon as N - co. Thus, it is impossible to show approximate optimality for all nodes and only possible to show for an increasingly large fraction 1 - p 1 of nodes. For this reason, we slightly weaken the notion of Nash equilibria by restricting to a fraction - p of agents, as e.g. considered in (Carmona 2004 Elie et al. 2020).
Definition 1. An (E,p) -MarkovNash equilibrium (almost Markov-Nash equilibrium) for s,p 0 is defined as a tuple of policies (T ,.....,,"" ") E 11.N such that for any i WN. we have
(m
...., > E, sup JNN((t ..... i-1 ,, mrth i+1
(8)
Ten
for some set WN C VN containing at least [(1 - ] agents, i.e. [WN| 2 [(1 111-20 N).
The minimal such è > 0 for any fixed policy tuple (and typically = 0) is also called its exploitabil- p of agents, if the fraction p negligible, it will have negligible impact on other agents as a result of the weak interaction property. Thus, the solution will remain approximately optimal for almost all agents for sufficiently small p regardless of the behavior of that fraction p of agents. In the following, we will give a limiting system that shall provide (s, p)- Marroov--aast equilibria with E, p - 0 as N + xC.
ity. Whilst we ordain e-optimality only for a fraction
Graphon mean field game. The formal N + co limit of the N-agent game constitutes its graphon mean field game (GMFG), which shall be rigorously justified in Section 3 We define the space of measurable state marginal ensembles M, = P(x)² _ and measurable mean field ensembles M := P(X)TXI in the sense that a + (x) is measurable for any μ E M, t E T, x X. Similarly, we define the space of measurable policy ensembles II IT. i.e. with measurable a ト x. (u x) for any π E II, T, E X, u u.
In the GMFG, we will consider infinitely many agents a E I instead of the finitely many E VN- As a result, we will have infinitely many policies T2 E II - one for each agent a through some measurable policy ensemble E II. We again define state and action random variables
X po:
U
7. ( X2), N P(. 1 UR (&), v(a,1) E EIXT
(9)
4

---

Published as a conference paper at ICLR 2022
where we introduce the (now deterministic) B1 (VV)-alu neighborhood mean field of agents
G =
W ((a, d3
(10)
for some deterministic E M. Under fixed E II, 14 should be understood as the law of X 14 (. Finally, define the maximization objective of agent a over x" for fixed μ E M
(T
E
Σ ufxx,UU.GG
(11)
To formulate the limiting version of Nash equilibria, we define map V: II + M mapping from policy ensemble II the corresponding generated mean field ensemble μ ( E M by
p = po: (2))(x)) = Σ
14
Σ Tf x: P(x' x u, G,), Ya E I
(12)
ZEN
MEW
where integrability in 10 holds by induction, and note how then μa = ((.)).
Similarly, let cb MM- + n map from mean field ensemble to the set of optimal policy ensem- bles π characterized by nº E arg max eEl (+) ) for all a E I. which is particularly fulfilled (u x)) > 0 = arg wax Qu (1,, (f, w for all a E E T, E X, U, where Qu is the optimal action value function under fixed E M following the Bellman equation
(t, r(z, u. U.) + Σ P(x' x u, G,, arg max Q (t 2,2',u)) w'El
(13)
x'E
with (T, u) = 0 and generally time-dependent, see Puterman (2014) for review.
We can now define the GMFG version Nash equilibria as policy ensembles æ generating mean field ensembles fe under which they optimal, as μe (((() if all agents I follow T².
Definition 2. A Graphon Mean Field Equilibrium (GMFE) is a pair (π p)) E II x M such that ((x) and μ V (T).
THEORETICAL ANALYSIS
To obtain meaningful optimality results beyond empirical mean field convergence, will need a Lipschitz assumption as in the uncontrolled, continuous-tine case (ef. BBaraktar et al. (2200) Condition 2.3) and typical in mean field theory (Huang al. 2006).
Assumption 2. Let P, W be Lipschitz continuous with Lipschitz constants L,, Lp. Lw > 0.
Note that proofs but Theorem T also hold only block-wise Lipschitz continuous W, see Appendix A.I Since X' x U B, (X) is compact, is bounded by the extreme value theorem. Proposition 1. Under Assumption r will be bounded by |r| S M, for some constant M, > 0.
We then obtain existence of GMFE by reformulating the GMFG as classical MFG and applying existing results from [aaldi et al.] (2018). More precisely, we consider the equivalent MFG with extended state space X x I, action space U, policy E 7xx xxxxI, mean field jé E P(X x I)T, reward function F((ar, ai), (.) = r(x, u. fz W W(ar,
(ar,8))ū( B) B3 d,3) and transition dynamics such that the states ax) follow (Xo, ao) No = po & Uni 11) and
Xet1 P(- &.,ū / W () a+t1
Ü, ~ tt( (e,
(14)
Theorem 1. Under Assumption there exists a GMFE (TT, p1) II M.
Meanwhile, in finite games, even showing the existence of Nash equilibria in local feedback policies problematic (Saldi et al. 2018). Note however, that while this reformulation will be useful for learning and existence, it does not allow us to conclude that the finite graph game is well approx- imated, as classical MFG approximation theorems e.g. in Saldi et al. (2018) do not consider the graph structure and directly use the limiting graphon W in the dynamics 14
5

---

Published as a conference paper at ICLR 2022
As our next main result, we shall therefore show rigorously that the GMFE can provide increasingly good approximations of the NNagent finite graph game as N + oc. As mentioned, the following also holds for only block-wise Lipschitz continuous W instead of fully Lipschitz continuous W. Complete mathematical proofs together with additional theoretical supplements can be found in Appendix [A.]] and [A.2] To obtain joint N-agent policies approximate Nash equilibria from GMFE (T, (d), we define the map [TT )) = (T', ",,",...,,,) ,x) E 11 where
Ti(u x)) = क, 2 (u x); V(a,t,,,)) EIxTxx xuu
(15)
with N. as by Assumption the agents are correctly labeled such that they match up with their limiting graphon indices a; E I. In our experiments, we use the a generated during the generation process of the W-random graphs, though for arbitrary finite systems one would have to first identify the graphon as well as an appropriate assignment of agents to graphon indices a, E Z, which is a separate, non-trivial problem requiring at least graphon estimation, e.g. Xu 2018).
For theoretical analysis, we propose to lift the empirical distributions and policy tuples to the con- tinuous domain Z, i.e. under an Naagent policy tuple (TT x² E I1 we define the step policy ensemble "." N E II and the random empirical step measure ensemble fe, E EMby by
N.o T
Σ 1 SEVN
Te
N.a P4
Σ 1 VEVY
6xp) v(a,t)
(16)
In the following, we consider deviations of the i-th agent from (T ....,,,................... ) = [N(TT) E II to (IT) ..... x'-1, n. m ...., x E IIN, ie. the i-th agent deviates by instead applying & E II. Note that this includes the special case of no agent deviations. For any f: X' x I + R and state marginal ensemble 14, E Mr. define ((( == S Exsx f(z, a)p (z:) da. We are now ready to state our first result of convergence of empirical state distributions to the mean field, potentially at the classical rate (I//VN) and consistent with results in uncontrolled, continuous graphon mean field systems (cf. [Bayraktar et al. (2000), Theorem 3.2).
diffusive
Theorem 2. Consider Lipschitz continuous π E II up to a finite number of discontinuities Da, with associated mean field ensemble μ (T((T)) ). Under Assumption 7 and the N-agent policy (I ..... x² R. x ...... NN) E II with (IT .²...., xN) (T) E IIN, f E II, t T, we have for all measurable functions f: X I + uniformly bounded by some My > 0. that
E [1 (f) pe(f))] -
+
(17)
uniformly over all possible deviations â E 11, E VN. Furthermore, if the graphon convergence in Assumption 1 is at rate (()/VN), then this rate of convergence is also O(1/VN).
In particular, the technical Lipschitz requirement of π typically holds for cies (Mondal et al.) | Pasztor et al., 2021) and includes also the case of finitely many optimality regimes over all graphon indices a Z. which is sufficient to achieve arbitrarily good approximate Nash equilibria through our algorithms
based poli-
shown in Section 4 We would like to remark that the above result generalizes convergence of state histograms to the mean field solution, since the state marginals of agents are additionally close to each of their graphon mean field equivalents. The above will be necessary to show convergence of the dynamics of a deviating agent to
Xx* po: OF7 #: (xx))
P(- & O, G²), VET (18)
for almost all agents i. i.c. the dynamics are approximated by using the limiting deterministic neighborhood mean field G see Appendix A.1 This will imply the approximate Nash property: Theorem 3. Consider a GMFE (T, 11) with Lipschitz continuous т up to a finite number of discon- tinuities Dx. Under Assumptions [ andd 2 for any e, > there exists N' such that for all N N', the policy (T) ..... T (T) E 11. is an (E, -Markov Nash equilibrium, i.e.
JN (M N) 2 max JNN (TT) ...., 7 1-11 T. i+ Hell
N)
(19)
for all i E Wy and some WN Vx: [Ww| 2 [(1 p)N].
In general, Nash equilibria are highly intractable (Daskalakis et al. 2009). Therefore, solving the GMFG allows obtaining approximate Nash equilibria in the N V-aeent system for sufficiently large N, since E, + 0 as N + oc. As a side result, we also obtain first results for the uncontrolled discrete- time case by considering trivial action spaces with [2/] 1, see Corollary A.2 in the Appendix.

---

Published as a conference paper at ICLR 2022
4 LEARNING GRAPHON MEAN FIELD EQUILIBRIA
By learning GMFE, one may potentially solve otherwise intractable large N -agent games. For learn- ing, we can apply any existing techniques for classical MFGs (e.g. Mguni et al (2018); Subramanian & Mahajan (2019); Guo et al. 2019)) since by (14) we have reformulated the GMFG as a classical MFG with extended state space. Nonetheless, it may make sense to treat the graphon index a E I separately, e.g. when treating special cases such as block graphons, or by grouping graphically sim- ilar agents. We repeatedly apply two functions 6 v by beginning with the mean field 1z" = (=*)
generated by the uniformly random policy n", and computing π= =((=), f=*1 = ( for n = 0, I.... until convergence using one of the following two approaches:
Equivalence classes method. We introduce agent equivalence classes, or discretization, of I for the otherwise uncountably many agents a E I by partitioning I into M subsets. For example, in the special case of block graphons (block-wise constant W), one can solve separately for each block equivalence class (type) of agents, since all agents in the class share the same dynamics. Note that in contrast to multi-class MFGs (Huang et al.] 2006), GMFGs are rigorously connected to finite graph games and can handle an uncountable number of classes a. To deal with general graphons, we choose equidistant representatives OG I, 1, . M covering the whole interval I, and approximate each agent a Σ, by the nearest 0g for the intervals I, C I of points closest to that oz to obtain M approxi- mate equivalence classes. Formally, we approximate mean fields (T) = EM' 1 oez, A recursively computed over all times for any fixed policy ensemble and similarly policies ((1) = En 1 L go where g is the optimal policy of 0; for fixed μ.. We solve the optimal control problem for each equivalence class using backwards induction (alter- natively, one may use reinforcement learning), and solve the evolution equation for the representatives at of the equivalence classes recursively. For space reasons, the details are found in Appendix A.33 Note that this does not mean that we consider the N-agent problem with N = M, but instead we approximate the limiting problem with the limiting graphon W, and the solution will be near-optimal for all sufficiently large finite systems at once.
Direct reinforcement learning, We directly apply RL as L. The central idea is to consider the GMFG as a classical MFG with extended state space X' I, i.c. for fixed mean fields, we solve the MDP defined by (4). Agents condition their policy not only on their own state, but also their node index E I and the current time E T, since the mean fields are non-stationary in general and require time-dependent policies for optimality. Here, we assume that we can sample from simulator of (9) for given fixed mean field commonly assumed in MFG learning literature (Guo et al., 2019 [Sbraaannia & Mahajan 2019). For application to arbitrary finite systems, one could apply model- RL approach coupled with graphon estimation, though this remains outside the scope of this work. For solving the mean field evolution equation (2), we can again use any applicable numerical method and choose a conventional sequential Monte Carlo method for V. While it is possible to exactly solve optimal control problems for each agent equivalence class with finite state- action spaces, this is generally not the case for e.g. continuous state-action spaces. Here, a general reinforcement learning solution can solve otherwise intractable problems in an elegant manner, since the graphon index a simply becomes part of a continuous state space.
For convergence, we begin by stating the classical feedback regularity condition (Huang al. 2006 Guo et al. 2019) after equipping II, .M e.g. with the supremum metric.
Proposition 2. Assume that the maps i & are Lipschitz with constants cı, C2 and ei C2 < 1. Then the fixed point iteration -+ = (((("))) converges.
Feedback regularity is not assured, and thus there is no general convergence guarantee. Whilst one could attempt to apply fictitious play (Mguni et al., 2018), additional assumptions will be needed regularize by introducing Boltz-
for convergence. Instead, whenever necessary for convergence, mann policies TP (u Z) & exp(+QQ x, u)) with temperature 17, provably converging to an approximation for sufficiently high temperatures (Cui & Koeppl 202T).
Theorem 4. Under Assumptions[[and) the equivalence classes algorithm with Boltzmann policies ((1)) (u a)) x exp(), } ( (1, x. u)) converges for sufficiently high temperatures 1) >> O.
7

---

Published as a conference paper at ICLR 2022
W
1/0
3.0
0.5
17
0.0
000
0.00
0.90
1.0
0.50
1.0
0.25
0.25
600
0.00
Figure 3: Achieved equilibrium via M = 100 approximate equivalence classes in SIS-Graphon, plotted for each agent a Z. Top: Probability of taking precautions when healthy. Bottom: Proba- bility of being infected. It can be observed that agents with less connections (higher a) will take less precautions. (a): Uniform attachment graphon; (b): Ranked attachment graphon; (c): ER graphon.
Importantly, even an exact solution of the GMFG only constitutes an approximate Nash equilibrium in the finite-graph system. Furthermore, even the existence of exact finite-system Nash equilibria in local feedback policies is not guaranteed, see the discussion in (aldi et al. (2018) and references therein. Therefore, little is lost by introducing slight additional approximations for the sake of a tractable solution, if at all needed (e-g. the Investment- Graphhn problem the following converges without introducing Boltzmann policies), since near optimality holds for small temperatures (Cui & Koeppl 202I). Indeed, we find that we can show optimality of the equivalence classes approach for sufficiently fine partitions of I, giving
theoretical foundation for our proposed algorithms.
Theorem 5. Under Assumptions / and 2 for solution (π. of the M equivalence classes method and for any E.P > 0 there exists N', M E N such that for all N N', the policy (m² ,,, (TT II is an (e. -Markoov Nash equilibrium.
II x M. @(M), μ (TT)
A theoretically rigorous analysis of the elegant direct reinforcement learning approach is beyond our scope and deferred to future works, though empirically find that both methods agree.
EXPERIMENTS
In this section, we will give an empirical verification of our theoretical results. As we are unaware of any prior discrete-time GMFGs (except for the example in Vasal et al. (202T), which similar to the first problem in the following). we propose two problems adapted from existing non-graph- based works on the three graphons in Figure 2 For space reasons, we defer detailed descriptions of problems and algorithms,, plots well as further analysis, including exploitability and verification of stability of our solution with respect to the number of equivalence classes to Appendix A.3
The SIS-Graphon problem
considered in Cui & Koeppl (2021) classical discrete-time
MFG. We impose an epidemics scenario where people (agents) are infected with probability propor- tional to the number of infected neighbors and recover with fixed probability. People may choose to take precautions (e.g. social distancing), avoiding potential costly infection periods at a fixed cost.
In the Investment- Graphe problem adaptation of a problem studied by Chen al. 202 where it was in turn adapted from Weintraub et al.) (2010) we consider many firms maximizing profits, where profits are proportional product quality and decrease with total neighborhood prod- uct quality, i.c. the graph models overlap in e.g. product audience or functionality. Firms can invest to improve quality, though it becomes more unlikely to improve quality as their quality rises.
Learned equilibrium behavior. For the SIS SS--rraphon problem, we apply softmax policies for each approximate equivalence class to achieve convergence, see Appendix [A.3 for details on tem- perature choice and influence. In Figure the learned behavior can be observed for various a. As expected, in the ER graphon case, behavior is identical over all a. Otherwise, we find that agents take more precautions with many connections (low a) than with few connections (high a).. For the uniform attachment graphon, we observe no precautions in case of negligible connectivity (a + 1), while for the ranked attachment graphon there is such I (cf. Figure 2. Further, the fraction of infected agents at stationarity rises as a falls. A similar analysis holds for Seessttent-Graphee without need for regularization, see Appendix A.3
8

---

Published as a conference paper at ICLR 2022
(5)
SIS- Graphon, Wis
uao M Aul
SIS- Graphon, Weat
GiS-Graphon, Wr
1000 14"
20
3o
70
100
25
100
25
50
109
wwestment-Graphen Was
Investment-co Graphon. West
Investment Graphon,
Sreesment-Graphoon W
Jal
110 M
10
1M0N 14"
90
Figure 4: Decreasing maximum deviation between average N-agent objective and mean field objec- tive over all agents for the GMFE policy and 5 W -randoom graph sequences. (a): Uniform attachment graphon: (b): Ranked attachment graphon; (c): ER graphon.
Note that the specific method of solution is not of central importance here, as in general any RL
and filtering method can be substituted to handle 1. otherwise intractable or 2. inherently sample- based settings. Indeed, we achieve similar results using PPO (Schulman et al. (2017) in Investment- Graphon, enabling general RL-based methodology for GMFGs. In Appendix [A.]] find that PPO achieves qualitatively and quantitatively similar behavior to the equivalence classes method, with slight deviations due to the approximations from PPO and Monte Carlo. In particular, the PPO exploitability = 2 remains low compared to E > 30 for the uniform random policy, see Appendix A.3 In Appendix [A.3] we also show how, due to the non- non-stationarity of the environment, naive application of MARI. (Yu et al. ( fails to converge, while existing mean field MARL. techniques (Yang et al. 2018b) remain incomparable as agents must observe the average actions of all neighbors. On STS- Graphon, we require softmax policies to achieve convergence, which is not possible with PPO as no Q-function is learned. In general, one could use entropy regularized poli- cies, c.g. SAC (Haarnoja et al. 2018), or alternatively use any value-based reinforcement learning method, though an investigation of the best approach is outside of our scope.
Quantitative verification of the mean field approximation. To verify the rigorously established accuracy of our mean field system empirically, we will generate W -randoom graphs. Note that there are considerable difficulties associated with an empirical verification of (I9). since 1. for any N one must check the Nash property for (almost) all N agents, 2. finding optimal क is intractable, as no dynamic programming principle holds on the non-Markovian local agent state, while acting on the full state fails by the curse of dimensionality, and 3. the inaccuracy from estimating all :0:==....... 1,...,N N at once increases with N due to variance, i.e. cost scales fast with N for fixed variance. Instead,
J. -.ii= =
verify (26) in Appendix A. using the GMFE policy systems of up to = π for the closest a and comparing for all agents at once (p = 0).
N = 100 agents, i.c. Shown in Figure 4 for W -rrandom graph sequences, at each N we performed 10000 runs to estimate max; J - T. We find that the maximum deviation between achieved returns and mean field return decreases as N + cc, verifying that obtain an increasingly good approximation of the finite N N-agent graph system. The oscillations in Figure 4 stem from the randomly sampled graphs.
6 CONCLUSION
In this work, we have formulated a new framework for dense graph-based dynamical games with the weak interaction property. On the theoretical side, we have given one of the first general discrete- time GMFG formulations with existence conditions and approximate Nash property of the finite graph system, thus extending classical MFGs and allowing for tractable, theoretically well-founded solution of competitive large-scale graph-based games on large dense graphs. On the practical side, we have proposed a number of computational methods to tractably compute GMFE and experi- mentally verified the plausibility of our methodology on a number of examples. Venues for further extensions are manifold and include extensions of theory to e.g. continuous spaces, partial ob- servability or common noise. So far, graphons assume dense graphs and cannot properly describe sparse graphs (W = 0), which remain an active frontier of research. Finally, real-world applica- tion scenarios may be of interest, where estimation of agent graphon indices becomes important for model-baseed MARL. We hope that our work inspires further applications and research into scalable MARL using graphical dynamical systems based on graph limit theory and mean field theory.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work has been funded by the LOEWE initiative (Hesse, Germany) within the emergenCITY center. The authors also acknowledge support by the German Research Foundation (DFG) via the Collaborative Research Center (CRC) 1053 MAKI.
ETHICS STATEMENT
Existing mean field methodologies, including ours, currently require manual modeling and have not been applied in model-based based reinforcement learning setting for given finite agent systems. As result, we do not foresee any immediate ethical issues stemming from this work.
REPRODUCIBILITY STATEMENT
For reproducibility, in the supplement we provide all code required to reproduce all results in this work. This includes but limited our models and problems, algorithms well as all plotting scripts for all of the figures found in this work.
REFERENCES
Alexander Aurell, Rene Carmona, Gokce Dayanikli, and Mathieu Lauriere. Finite state graphon 2021a.
games with applications to epidemics. arXiv preprint
Alexander Aurell, Rene Carmona, and Mathieu Lauriere. Stochastic graphon games: li. the linear- quadratic case. arXiv preprint arXiv:2105.12320 2021b.
Fabio Bagagiolo and Dario Bauso. Mean-field games and dynamic demand management in power grids. Dynamic Games and Applications, 4(2):155-176. 2014.
Reginald A Banez, Lixin Li, Chungang Yang, Lingyang Song, and Zhu Han. A mian-field-type game approach to computation offloading in mobile edge computing networks. In ICC 2019- 2019 IEEE International Conference on Communications (ICC), pp. 1-6. IEEE, 2019.
Erhan Bayraktar, Suman Chakraborty, and Ruoyu Wu. Graphon mean field systems. arXiv preprint arXiv:2003.131800 2020.
Mare G Bellemare, Salvatore Candido, Pablo Samuel Castro, Jun Gong, Marlos C Machado, Sub- hodeep Moitra, Sameera S Ponda, and Ziyu Wang. Autonomous navigation of stratospheric bal- loons using reinforcement learning. Nature, 58877836:77-82, 2020.
Alain Bensoussan, Jens Frehse, and Phillip Yam. Mean field games and mean field type control theory, volume 101. Springer, 2013.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv:1912.06660,, 2019.
Gianmarco Bet, Fabio Coppini, and Francesca R Nardi. Weakly interacting oscillators on dense random graphs. arXiv preprint urXiv:2006.06670, 2020.
Christian Borgs, Jennifer Chayes, László Lovász, Vera Sós, and Katalin Vesztergombi. Limits of randomly grown graph sequences. European Journal of Combinatorics, 32(7):985-999, 2011.
Peter Caines and Minyi Huang. Graphon mean field games and the gmfg equations: e-nash equilibria. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 286-292. IEEE, 2019.
Pierre Cardaliaguet and Saced Hadikhanloo. Learning in mean field games: the fictitious play. ESAIM: Control, Optimisation and Calculus of Variations, 23(2):569-511, 2017.
Guilherme Carmona. Nash equilibria of games with continuum of players, 2004.
10

---

Published as a conference paper at ICLR 2022
René Carmona, Daniel Cooney, Christy Graves, and Mathieu Lauriere. Stochastic graphon games: the static case. arXiv preprint arXiv:1911.10664 2019a.
René Carmona, Mathieu Laurière, and Zongjun Tan. Model-free mean- mean-field reinforcement learning: mean-field mdp and mean-field q-learning. arXiv preprint arXiv: 12802, 2019b.
Yang Chen, Jiamou Liu, and Bakhadyr Khoussainov. Agent-level maximum entropy inverse rein- forcement learning for mean field games. arXiv preprint arXiv:2104. 14654, 2021.
Kai Cui and Heinz Koeppl. Approximately solving mean field games via entropy-regularizer deep reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp- 1909-1917. PMLR, 2021.
Kai Cui, Anam Tahir, Mark Sinzger, and Heinz Koeppl. Discrete-time mean field control with environment states. arXiv preprint arXiv:2104. 14900, 2021.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195-259 2009.
Boualem Djehiche, Alain Tcheukam, and Hamidou Tembine. Mean-field-typ games in engineering [].. AIMS Electronics and Electrical Engineering, 1(1):18-73, 2017.
Romuald Elic. Julien Perolat, Mathieu Laurière, Matthicu Geist, and Olivier Pietquin. On the con- vergence of model free learning in mean field games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7143-7150, 2020.
Shuang Gao and Peter E Caines.
The control of arbitrary size networks of linear systems via graphon limits: An initial investigation. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 1052-1057. IEEE, 2017.
Shuang Gao and Peter E Caines. Graphon control of large-scale networks linear systems. JEEE Transactions Automatic Control, 45(10):400044105 2019a.
Shuang Gao and Peter Caines. Spectral representations of graphons very large network systems control. In 2019 IEEE 58th Conference Decision and Control (CDC), pp. 5068-5075. IEEE, 2019b.
Marios-Antonios Gkogkas and Christian Kuehn. Graphop mean-field limits for kuramoto-type mod- els. arXiv preprint arXiv:2007. 022668, 2020.
Haotian Gu, Xin Guo, Xiaoli Wei, and Renyuan Xu. Mcan-field controls with q-lcarning for coop-
erative marl: Convergence and complexity analysis. arXiv preprint 241311, 2020.
Haotian Gu, Xin Guo, Xiaoli Wei, and Renyuan Xu. Mcan-field multi-agent reinforcement learning:
A decentralized network approach. arXiv preprint arXiv: 108.033, 2021.
Olivier Guéant, Jean-Michel Lasry, and Pierre-Louss Lions. Mean field games and applications. In Paris-Princetor lectures mathematical finance 2010, pp. 205-266. Springer, 2011.
Xin Guo, Anran Hu, Renyuan Xu, and Junzi Zhang. Learning mean mean-field games. In Advances in Neural Information Processing Systems, pp. 4966-4976, 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learning. pp. 1861-1870. PMLR, 2018.
Minyi Huang, Roland P Malhamé, and Peter E Caines. Large population stochastic dynamic games: closed-loop mckean-vlasov systems and the nash certainty equivalence principle. Communica- tions in Information & Systems, (33:22112552 2006.
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yoga- mani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. JEEE Transactions Intelligent Transportation Systems, 2021.

---

Published as a conference paper at ICLR 2022
Arman C Kizilkale and Roland P Malhame. Collective target tracking mean field control for electric space heaters. In 22nd Mediterranean Conference on Control and Automation, pp. 829- 834. IEEE, 2014.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal of Robotics Research, (2(11): 2013.
Daniel Lacker and Agathe Soret. case study on stochastic games on large graphs in mean field and sparse regimes. arXiv preprint arXiv:2005.14100 2020.
Jean-Michel Lasry and Pierre-Louis Lions. Mean field games. Japanese journal of mathematics, (1):229-260, 2007.
Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gon- zalez, Michael Jordan, and lon Stoica. Rllib: Abstractions for distributed reinforcement learning. In International Conference on Machine Learning, pp.
PMLR, 2018.
László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
David Mguni, Joel Jennings, and Enrique Munoz de Cote. Decentralised learning in systems with many, many strategic agents. Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Washim Uddin Mondal, Mridul Agarwal, Vaneet Aggarwal, and Satish V Ukkusuri. On the approx-
imation of cooperative heterogeneous multi-agent reinforcement learning (marl) using mean field control (mfc). arXiv preprint (txxxx:2199.402220 2021.
Médéric Motte and Huyên Pham. Mean-field markov decision processes with common noise and open-loop controls. arXiv preprint arXiv:1912.07888 2019.
Mojtaba Nourian and Peter E Caines, e-nash mean field game theory for nonlinear stochastic dy- namical systems with major and minor agents. SIAM Journal on Control and Optimization, -33333 2013.
Francesca Parise and Asuman Ozdaglar. Graphon games. In Proceedings of the 2019 ACM Confer- ence on Economics and Computation, pp. 457-458, 2019.
Barna Pasztor, Ilija Bogunovic, and Andreas Krause. Efficient model-base multi-agent mean- mean-field reinforcement learning. arXiv preprint arXiv:2107.0400 2021.
Julien Perolat, Sarah Perrin, Romuald Elie, Mathieu Laurière, Georgios Piliouras, Matthieu Geist, Karl Tuyls, and Olivier Pietquin. Scaling up mean field games with online mirror descent. arXiv preprint arXiv:2103.0062. 2021.
Sarah Perrin, Mathieu Laurière, Julien Pérolat, Romuald flii,, Matthieu Geist, and Olivier Pietquin. Generalization mean field games by learning master policies. arXiv preprint (10i::209900911,,, 2021a.
Sarah Perrin, Mathieu Laurière, Julien Pérolat, Matthieu Geist, Romuald Élie, and Olivier Pietquin. Mean field games flock! the reinforcement learning way. arXiv preprint arXiv:2105.07933. 2021b.
Huy Xuan Pham, Hung Manh La, David Feil-Seifer, and Aria Nefian. Cooperative and distributed reinforcement learning of drones for field coverage. arXiv preprint arXiv:1803.072560 2018.
Huyên Pham and Xiaoli Wei. Bellman equation and viscosity solutions for mean-field stochas- tic control problem. ESAIM: Control, Optimisation and Calculus of Variations, 24(1):437-461, 2018.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Naci Saldi, Tamer Basar, and Maxim Raginsky, Markov-nash nash equilibria in hean-field games with discounted cost. SIAM Journal on Control and Optimization, (266)4256-4287 2018.
12

---

Published as a conference paper at ICLR 2022
Naci Saldi, Tamer Başar, and Maxim Raginsky. Approximate nash equilibria in partially observed stochastic games with mean-field interactions. Mathematics of Operations Research, 44(3):1006- 1033, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint orXiv:1707.06344 2017.
Jayakumar Subramanian and Aditya Mahajan. Reinforcement learning in stationary mean-field games. In Proceedings of the 18th International Conference on Autonomous Agents and MultiA- gent Systems, pp. 251-259, 2019.
Jan Tožíčka, Benedek Szulyovszky, Guillaume de Chambrier, Varun Sarwal, Umar Wani, and Man- tas Gribulis. Application of deep reinforcement learning to uav fleet control. In Proceedings of SAI Intelligent Systems Conference, pp. 1179-1177 Springer, 2018.
Deepanshu Vasal, Rajesh Mishra, and Sriram Vishwanath. Sequential decomposition of graphon mean field games. In 2021 American Control Conference (ACC), pp. 730-736. IEEE, 2021.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Starcraft ii: A new challenge for reinforcement learning. arXiv preprint 1rX1v:1708.04782, 2017.
Renato Vizuete. Paolo Frasca, and Federica Garin. Graphon-based sensitivity analysis of sis epi-
demics. JEEE Control Systems Letters, 4(3):542-547, 2020.
Gabriel Y Weintraub, C Lanier Benkard, and Benjamin Van Roy. Computational methods for obliv- 2010.
ious equilibrium. Operations research, 2
Jiaming Xu. Rates of convergence of spectral methods for graphon estimation. In International
Conference Machine Learning, pp. 5433-5442. PMLR, 2018.
Jiachen Yang, Xiaojing Ye, Rakshit Trivedi, Huan Xu, and Hongyuan Zha. Learning deep mean field games for modeling large population behavior. In International Conference on Learning Representations, 2018: 8a.
Yaodong Yang. Rui Luo, Minne Li. Ming Zhou, Weinan Zhang, and Jun Wang. Mcan field multi- agent reinforcement learning, In International Conference on Machine Learning, pp. 5571-5580. PMLR, 2018b.
James J Yeh. Real Analysis: Theory Of Measure And Integration. World Scientific Publishing Company, 2014.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01955. 2021.
Kaiqing Zhang. Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp- 321-384, 2021.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 THEORETICAL DETAILS
In this section, will give all intermediate results required to prove the results in the main text, as well as additional results, e.g. for the uncontrolled case. For convenience, we first state all obtained theoretical result. Proofs for each of the theorems and corollaries can be found in their own sections further below.
Note that except for Theorem 1 as mentioned in the main text we can also slightly weaken As- sumption 2 to block-wise Lipschitz continuous W, ie. there exist Lw > O and disjoint intervals {I1 J U.I. I s.t. Vi.j {I..... Q).
[W v) W (a. 5) & Lw(K .l + by rl). (r,,)) (5,ū) E I, I
(20)
which is fulfilled e.g. for block-wise Lipschitz-continuuus or block-wise constant graphons.
For a E I, define the a-neighborhood maps G Mr - P(X) and empirical a-neighborhood maps G M₁ + P(X) as
G))) = / ((a, d3, G) = /f Wx Ww 3) as
(21)
and note how we naturally have 02 (*r)) in the mean field system and Gi G (p in the finite system. Finally, for v, E MM, x E II and graphon W, define the ensemble transition kernel operator P.u.w: Mr + MM via
Eve(z) Emt(ulz) (1 112,,, u, (Wa,,3)// 3)/ d8)
(22)
TEX
aEll
and note how have |4++1 P.pee in the mean field system.
After showing Theorem 2. we continue by showing convergence of the law of deviating agent state X; to the law of the corresponding auxiliary mean field systems given by
No:
Ú ~ 1.1.1
X 41 ~ P( X U. WLET
(23)
for almost all agents i as N + 3c. 30.
Lemma A.1. Consider Lipschitz continuous π E II up to finite number of discontinuities Da. with associated mean field ensemble μ Vi(TT). Under Assumptions 7 and 2 and the N N-agent policy (T) ...., "'..,''''1,,. T²1,,A,, x+4) ...., "...,T", vV) E IIN where ) x..,x% .......7"
(T) E IIN, f II arbitrary. for any uniformly bounded family of functions 9 from X to R. and any E. 0, TE
(
there exists N' E N such that for all N > N' we have
sup gEG
E [[((X))]
- ((x(
<6
(24)
uniformly over â E 11, E WN for some WN C. VN with [Wal Z ((1-))N1:
Similarly, for any uniformly Lipschitz. uniformly bounded family of measurable functions H. from X x Bi (X) to I and any s,p > O, L T, there exists N' E N such that for all >> N' we have
h(x;, GA (MN ( -E [M(8 & (wo)) <e
sup
(25)
NER
uniformly over â E II, WN for some WN C. VN with [Ww| [J-
As a direct implication of the above results, the objective functions of almost all agents converge uniformly to the mean field objectives.
Corollary A.1. Consider Lipschitz continuous π E II up to finite number of discontinuities D., with associated mean field ensemble μ (TT)). Under Assumptions
7 and 2 and the N Naggent
policy (w',..., --11 म., π 7it1 ,,..., NN) E II where (T
n² "r²,7" "...,.. ..,, N [N( )T) IIN क II
arbitrary, for any e.p > O, there exists N' E N such that for all N > N' we have
J ( ..... i-1 A, 2 i+1 ..... T
1 (+t) <E
(26)
uniformly over â E II E WN for some Wy C VN with [Wx| [(1 (11p)NN
14

---

Published as a conference paper at ICLR 2022
The approximate Nash property (Theorem 3) of GMFE (T, (e) then follows immediately from the definition of a GMFE, since т is by definition optimal under pt.
As corollary, we also obtain results for the uncontrolled case without actions, which is equivalent to the case where [2]] = 1, i.c. there being only one trivial policy that is always optimal.
Corollary A.2. Under Assumption and [ = 1, we have for all measurable funcioonss f: XxI +
IR uniformlyy bounded by [fl S M, and all E T that
1 (f) pe(f)] + +0.
(27)
Furthermore, if the convergence in Assumption / is at rate O(I/VN), the rate of convergence is also at (L)/VN).
If further Assumption 2 holds, then for any uniformly bounded family of functions G from X to R and any E, > t T, there exists N' e IN such that for all N > N we have
sup sEg
E [9(x)))
-E B [0((
) <E
(28)
uniformly over Wx for some WN C. VN with [Wr| 2 L(1 L(1-P) D) and similarly for any uniformly Lipschitz. uniformly bounded family of measurable functions H from X Bi (X) to IR and any E, > t E T, there exists N E N such that for all > N' we have
sup
h(x GN (1)
E [M(X & (wo))] <E
(29)
NEW
uniformly over i WN for some WN VN with [NN| 2 (1--)N].
A.2 PROOFS
In this section, we will give full proofs the statements made in the main text and in Appendix A.
A.2.1 PROOF OF THEOREM 1
Proof. First, will verify Saldi al. (0188) Assumption for the MFG with dynamics given by [14). For this purpose, as in Saldi et al. (2018) let metrize the product space with the sup-metric, and equip the space P(X' x I) with the weak topology. Note that the results hold for both the finite and infinite horizon setting, see Saldi et al. (2018), Remark 6.
(a) The reward function F((2,, a); u. (i) r(ar, u, fz (oje,B)ee(s (,3) is continuous, since for ((I,, an), Un pn)) ((I, 21 we have
J W(an, ()) + / B) (3
by Lipschitz continuity of W and weak convergence of ün, and therefore
r(Ins Uni / ((an; ()) + r(x, [(a,
by Assumption
(b) The action space is compact and the state space is locally compact.
(c) Consider the moment function w(æ a) = 2. In this case, we can choose ( = 1 (we use instead of in Saldi et al. (2018)).
(d) The stochastic kernel P that fulfills 14 such that (Re+11 a441) ~ P(: (X,, Ur Fe)
is weakly continuous, since for ((I,: Okz)) Myn (A)) - (xx u. we again have
J W (an, ())x
()a,))
15

---

Published as a conference paper at ICLR 2022
and therefore for any continuous bounded f: X
J f fdP(- (In, an), Un Pm)) = | x
fdpa (In, a), Mn: San, (da)
XxI
In. Uni / ((an, (- d3)
f ddp(-
[ sdp(. I,, Jz ((a,B) ())
/ [
XxI
by disintegration of P and 14.
(c) By boundedness of r, we trivially have v(x) = S 00.
(f) By boundedness of r, we can trivially choose B = 1 (we flip the usage of 3 and 7).
As result of the above choices, S7B = < trivially.
By Saldi et al. (2018), Theorem 3.3 we have the existence of a mean field equilibrium (+t pi) with some Markovian feedback policy म acting on the state (X,, ox). By defining the mean field and policy ensembles π, la via ( .x) ( xr, a²), P. ()); we obtain existence of the a-a.c. optimal policy ensemble π, since at any time t E T. the joint state-action distribution j4: @ the puts mass 1 on optimal state-action pairs (see [aaldi et al. (2018). Theorem 3.6), implying that for a.e. a the policy must be optimal, as otherwise there exists a non-null set Io S I such that for all Io. there some suboptimality > which directly contradicts the prequel.
For the remaining suboptimal a E To in the null set To C I, we redefine optimally for those a (always possible in our case, see e.g. PPtterman| (2014)). This policy ensemble generates μ = (x) a-a.e. uniquely, and we need only consider its a-a.e. unique equivalence class for optimality, implying π ((H). Furthermore, f4 always measurable by definition, whereas π is measurable because स, is by definition a Markov kernel, and thus Ry ...) 7. ((u) I...) for Borel set {u) is a measurable function, which implies measurability of (w xr (see e.g. Yeh (0014), Appendix E). Therefore, we have proven existence of the GMFE (T,, pt).
A.2.2 PROOF OF THEOREM 2
Proof. The proof is by induction as follows.
Initial case. For O, we trivially have for all measurable functions f: x I uniformly bounded by Ifl S My a law of large numbers result
E II (f) Ho(li]
/
E
Σ
N0
(x) ((x,))
Σ Hg (x) (())]((e) [(x (x)
ZEX
FEX
[ (1 [(Xi a) da )1
E
1(Xi,a) da -
N
VEVN
ai 1 (12
1)
E
Σ
(1
5(Xg. or) day dle)
N
VEVN
11)
1)
27
2M,
ΣE
5(x E
f(X), a² da
N2
(1 (+
VN
JEVN
by definition of yua. independence of (Xi and Xi ~ 44 = pg for all E Vx, E I, where the second equality follows from Fubini's theorem.
16

---

Published as a conference paper at ICLR 2022
Induction step. Assume that the induction assumption holds at t. Then by definition of yu," for all bounded function f X x I + R with If| I My,
E (ff (1)1 - E
(f) H 1. wN [D] P.T
P.T L. ww (5) - uº Pi,n w (D
Lu w ( 2e LHE w (D)
pe LAN w (f) ub Pi.m,. [t)
E
1 P w. (f) - (e)1
First term.
We have by definition of 1r"
( - Pe pm ww nnl
E
=
Σ
M
(x) (2) ((o,
TEX
Σ
N. (x)
Σ
No
(u x))
Σ P
x' 1,,, Wwla, Mu No a3) (83)
a))
He
T
DEX
NEl
x'EX
[1 ((X da x x1]1
E
S(Xi ((Xi+); da - E
N
BEVN
(L ax) -a Je [(X
x. xx1)) 27
E
Σ
N
SEVN
()) do da- S(Xi ax da x x))]]
N2
VEVN
2M,
VN
where the last equality follows from conditional independence of (X given X, = (Xi)ievy and the law of total expectation.
Second term. We have
E
pi N pm
L.N, w (f)
uia pm (.....(F)) [5]
[ Σ
E
Hi
N. (x) (x)
Σ
Te Na (()xx)
x))
Σ P
x' I, WN(a,3)) N, as) f(x', a) da
MEX
NEll
N'E
Σ REX
(x)
Σ
Na (u
Σ P
x I,U, I W(aa ()) d8) f(2',
wEll
E'E
< 11|M,Lp V.N.I. WN(a,
N.3 d3
W(a, 3), N. ds da
V.A. Ww 3)
$ 118 sup NeX
N. (z) ((a, B) (x) de da + 0
by Assumption 1 and pr N.9 (x) trivially being bounded by 1. If the convergence in Assumption rate O(1/VN), then this convergence is also rate O(1/VN).
17

---

Published as a conference paper at ICLR 2022
Third term.
We have
E
pi N
t.pe"" w (f)
ui I P
E
Me
Na
au x)
Σ
P
x' I. u,
W), ds) f(d a(zl,a)
I
REE
WEM
''ER'
1 BEX
P4
(x)
Σ
o (u x))
Σ
P
x' 11 1212,,,
1), dB) s(2'
NEM
x'EX
$ M
N. (u x)
n (u
x))
da
[No]
= =
E JEV
Tt N
(u 1 x)) - क, (u x) da
(5.)))) +1
+ +
me(u x) - (p -
x)] da
Li + M &
2|Dz1 M
2 N
$
N
by assumption of Lipschitz continuous up to finite number of discontinuities Dx well as the deviating agent i's error term, for which the integrands are bounded by 2.
Fourth term.
We have
N u
p.T
PT (f)
1b
PT... [n]
PM
[ Σ
E
14
(x)())
N.a
(x) Σ mp x) Σ P x' x, u. M), (B) (al, a) da
ZEN
DELl
Σ ZEX
No (x)
Σ mp (u Σ Σ
P f W(aa 3)m aB) (( da
BEll
x'EX
< M E
sup
P x' 1,, I,
W(a, N.B d3)
R.u
I
P 20' (P / W ((,, ((, d3) da
Σ E /./// W(a, (a, (2)) W(a, (i( da
< Lp
x'Ex
(1(
s & Lp
VN
in the case of rate (II/VN), or uniformly to zero otherwise, from Lipschitz P by defining the functions f (z, ()) W (a. 1)-1 for any (x' E X X and using the induction assumption on faaaa to obtain
[. 1
W (a,
No (2)) WWa,))a(((')d da
= { ((a, 3) N.3 (x)) / W(a, (),, (1) da C'(1)
/ || (1 (Fr milfa, da S
VN
for some (1 > O uniformly over all f bounded by if the convergence in Assumption | is at rate ((1/VN) or uniformly to zero otherwise.
18

---

Published as a conference paper at ICLR 2022
Fifth term. We have
E 11 N Pr,pe. (f)
te (....w())
/ Σ Mr (x)
E
(x)
Σ
Σ
P x' 12, W(a 3) ds) f(x', a)
P
da W(a, () dB) f(al, [
ZEX
WEM
x'E
J [MA())
(z)
Σ
( x)
Σ
P
x6' 12,,,,,,
I TEX
F'E
E /. Σ
M4 N (z)
/ En
ZEN
ZEN
C'(M))
E (1')(()) (f') - M((l') S
VN
in the case of rate O(I/VN), or uniformly to zero otherwise, again by induction assumption applied to the function
f(, =
Σ क
( r)
Σ
( x'
x, W(a, 9) dB) f(2',a)
x'E
bounded by My. This completes the proof by induction.
A.2.3 PROOF OF LEMMA A.
Proof. First, we will show that (2 implies (25).
We consider uniformly Lipschitz, uniformly bounded family of mea- surable functions H. from X' x (x)) to Let Mr be the uniform bound functions H and Ln be the uniform Lipschitz constant. Then, for arbitrary h E H we have
Proof of
25
B h(x; & (4 ()) E
1(X,*
G (mo))]
B MXx; G (n(")]
E M(x G (m4)
+ I [MXX; Gp (m))
E Mxxx G (m/)
+ E [M(X3; G (mi))
E |xx G (1+)
which we will analyze in the following.
First term
We have
M(x G (14 ]) - [M(x G (()))
E
S E.
R h1 [xx; G (14²)) - h(xx G (1+) x:]
< Ln E
[| (M - G (m+)
(x) d3 - / WN( i (1) s / Wn n 0) No9 (x)
C(1)
= Ln
VN
xEX
by Theorem applied to the functions f' (2', 3) = WN( 3) 1 uniformly bounded by 1.
Second term Similarly, we have
E M(X: G (m.))) -E [MXX & x (m+))
< Tup G (14)) G ((+))l
19

---

Published as a conference paper at ICLR 2022
Wv(( i 3) - () m (x) d3
$ Ln
DEA
$ Ln
Σ
[WN( i N
3) - N / (x.12))
W(a,
Mi (x) d3
FE
+ Lb Σ
W(a, -a i
ue (z)
N
(5
TEX
where the latter term can be bounded as
Ln
Σ
N
d(a, - -W 9) ue (x)
(57
xEX
S T/ Σ
[ N
S( (5+++
(W(a, W(
[Na]
N 18) (1((z) (x) do
#E
1
Lw La
N
N
N
by Assumption
Alternatively, if we assumed the weaker block-wise Lipschitz condition on W in (20). can obtain the same result for almost all E Vy i.e. for any Po > 0 there exists N' E NN such that for any N > N', there exists set W (W 2 [(1 NN such that for all i W the above is true: Since by (20) there exist only a finite number Q of intervals and therefore jumps, there can be only
Q many for which the above fails, while for all other we again have
VAN N
(W(a, - W( [Na]] N
.9)) mg da
(
+1
JSg NN/ / (++
ul (z) da .3)) _
[Na]
Σ
[(a,,)) B) W
N
JE(I.....Q) Q}
Ia
Lw L
<
N
N
N
by 20). as (xx)
I
C I I, for some ls E (l....,Q) Q}.
For the former term we observe that
WN W 1) -N-N
i 1 W(a, ()a pi (x)
T
xEX
11, I/Wwila. (WWaaa))-W(a.)))( ((a, do
Tn
Σ N
xEX
and by defining for any x E X' the terms I.N (x) via
(())= +1 1/4 (Ww(a, -(a,)) Wawedel- da
and noticing that we have
1 W(a, (z) da
by Assumption D
we can conclude that for any E 0 there exists N' N such that for any
N > N', there exists a set W W 2 [(1 P such that for all i E W we have
T²((x)
(x) < 61,
20

---

Published as a conference paper at ICLR 2022
since by the above e1P1, and from I, (x:) 2 0 it would otherwise follow that N E (x) 2 N [pI & 2 61p1 which would be direct contradiction. Therefore, for all E WX we have uniformly
choose N' E N such that for any N N' we have N E (x)
1/8 (WNi(a, W(a, ()( (x) da Lu E (x) (++
LA Σ N MEN'
NEt
Third term. By 24 for any P2, > 0 there exists a set W 1M 2 1(1 - P2)NN such that for all i E W we have
G * | [
(p()) - B ! (m))) <52
independent of II.
The intersection of W WN. W has at least N - Noo | - [p N| - N2 agents fulfilling 25 which completes the proof of (24) -
(25 for almost all agents by choosing 62 sufficiently V [paN] 2 [(1 - p) which is equivalent (1-P1N and is true for sufficiently large N, since the limit,
small and Po: P1.P2
< 3 such that N - N
[1
to
N
1
P N
[Pr Ni
P2 N1
Po P1 P2 and [1-p))N]
p as N 0o.
N
Proof of (24). All that remains is to show 24). which will automatically imply (25 at all times
t T by the prequel. We will show (24 by induction.
Initial case. Att 0, ((x)) po L(X,5' by definition. Thus, trivially
[o(xx]]] - E g
=0<e.
Induction step. For any uniformly bounded family of functions & from X to R with bound Mg- we will show that for any E, > 0, there exists N' E N such that for all N > No we have
E (g(( EE [o(
<s
uniformly over II, i Wy for some Wx C VN with WN 2 [(1 (11-p)N], Observe that
E [o((
E g - [ & (m)))] E [IN G (p:))
where we defined the uniformly bounded, uniformly Lipschitz functions
(N,(
Σ Re x)
P(d') xx u. v)x('()))
NEN
x'EX
with Lipschitz constant | and uniform bound Mg. By the induction assumption and 24) 25 from the prequel, there exists N' E N such that for all N > N' we have
E [NN GN (NN D]]
( G& (no) <E
uniformly over E 11, E Wy for some WN S VN with WNn 2 [(1 NJ which completes the proof by induction.
A.2.4 PROOF OF COROLLARY A.I
Proof. Define the uniformly bounded, uniformly Lipschitz functions
ra ( = Σ r(æ, u, (
NEW
with Lipschitz constant [U]L, and uniform bound M, such that by Lemma A.1 and Fubini's theo- rem. there exists N' E N such that for all N > N' we have
J (T) ...., -' 1-1 n, n 1+1
. Ju (#)
21

---

Published as a conference paper at ICLR 2022
Σ 1=0
ra (x G (x (m)) - raa (x G (w:1i] <e.
uniformly over स E 11 E WN for some Wx C VN with WN 2 aul-p) [J by choosing the maximum over all N' at each finite time step from Lemma A.1
log <(1->)
In case of the infinite horizon discounted objective, we instead first cut off a time such that trivially
1M,
log 7
Σ (X;
(xx.G*((0 (m.)))
(x.. & (m:))
7
T
r+ (X G+ (m.))) EE' r+. (X,²² G (mi))
T 7
rh (X
G (n+i)
- rs (X, G (p.i)) 2
and then handle the remaining term analogously to the finite horizon case.
A.2.5
PROOF OF THEOREM 3
Proof. By Corollary A.1 for any > 0 there exists N' E N such that for all N > N' we have
(J; N (π
n, π i+ π Ji (TT ..... , ))
max EEI
J (T' ,...,, x n. n x x 5 (π)
max #ell
x
JH (T)) J ()+))
max
Hell
+
ju (π
J. (T (m²
+ 0
2 =
2
uniformly over i E Wx for some WN S. VN with WNr| > ((L-))N] since x arg max, h (T) by definition of a GMFE. Reordering completes the proof. N
A.2.6 PROOF OF COROLLARY
Proof. The proof follows immediately from Theorem 2 and Lemma A. by considering the trivial policy that always chooses the only action available together with its generated mean field μ (TT).
A.2.7 PROOF PROPOSITION
Proof. The set II is a complete metric space, since existence of limits follows from completeness of E. pointwise limits of measurable functions measurable, and policies will remain normalized. Banach's fixed point theorem applied & & gives us the desired result.
A.2.8 PROOF OF THEOREM 4
Proof. Formally, approximate mean fields by ((T)) EM Laei, fi for any fixed policy ensemble π, and similarly policies Φ(μ)- ΣM 1 LaEž, th 7 where Th is the sofumax policy of a; for fixed μ. i.e.
exp (t....)))
T& (u xx) Enerr exp (t,,..u))
11
(30)
22

---

Published as a conference paper at ICLR 2022
T X' u un- der Assumption 2 Since the Lipschitz constants are shared over all a, by Cui & Koeppl (2021), Lemma B.7.5, 30 is therefore Lipschitz with Lipschitz constant proportional to 1/n,, which imme- diately implies that & also Lipschitz with Lipschitz constant cn/n. By its recursive definition as compositions of Lipschitz functions, V Lipschitz as well with some constant c2. Therefore, the composition of both functions // c Lipschitz with constants c102/17. which will be less than for sufficiently large v). By Proposition the equivalence classes algorithm v o converges to fixed point.
By the Bellman equation 13). (t, u) is Lipschitz in μ for all (t, u)
A.2.9 PROOF OF THEOREM 5
Proof. First, note that under the equivalence classes method, the distance between any and its representant a; uniformly shrinks to zero as M - oc, i.e. max;= sup,ct, |a - 0gl - 0.
We begin by showing that a solution of the M equivalence classes method (TT, E II x M, E ((H), je (T) following (31). (32) fulfills approximate optimality, i.e. for any e > 0 there
exists M' s.t. for all M M
sup max (J) (T) <E,
aEI nell
where we introduced the true, exact mean field ensemble = (TT) following 12 the block-wise solution policy E aee TT: of the M equivalence classes method, well the true mean field system under jı and any policy π E II
generated by
X6 po,
U
Tr(- Xf')
X
P(- X UP C8), ((x,))
with valued G7 = Jz W(a, B) d3 and (T) = ا r(xg 0f. G.)]
while sys-
tem 99 is to be understood as the system under the approximate mean field ensemble μ.
To see this, we will analyze
sup max (T) - (TT)) < max sup max (J) - (T)) aeI nell
i=I....M aet xell
max sup max (J)( - J (T))
I=..... aei, well
+ max sup max (Jr, (T) - Ju (T)
EI.....M aet, well
+ max sup (JH, (ma:) - J (
i=I.... aci,
+ max sup (JL( - J (x²))
LI...., M
aEi.
First term For any π E II, define the uniformly bounded, uniformly Lipschitz functions
(2, = Σ r(z,,,, V)TT
NEW
with Lipschitz constant L. and uniform bound M, such that for the first term, we have (JÉ( - (T)) < ( J
T-1
W
E (X GP)] (xr G
MiBB MMMMN
E [rx (80, G3) - rx (8 G +
E Fr (Xa G3] - Err G&l
1=0
L / W(a, () u3))
E rr x G.|
E
1r=(x;
G
23

---

Published as a conference paper at ICLR 2022
For the former term, note that
MW B) - -m()
Σ / W W(a, 3) (4
2,
I max
sup | l - 19
i= i act:
and we will show by induction over t = 0, ,,, T that aet, 1| - 14 || + 0 over all a
uniformly over all equivalence classes I, At t we have trivially to Po- Assume that suPaež, l1 1 + O. Then for I. + 1, we have
sup acT:
| 14+11
sup acī,
Σ (i(x)) (x)
Σ Ti x)) x, u,
u,, G9)
Σ
1z (x)
Σ
Ti Tp (u P) 8, G71
FEN
ueld
xEd
uell
< sup aeī,
Σ (1(()) (z)
Σ
2, G.) ( x)
Σ xEX
Pt (x)
Te (2 P) x, u, G(n)
TEX
uEll
Σ xE
Pt (z)
Σ
Tr (u I
u.u, G
Σ
Mi (z)
Tt
04 (u P) x, U. (.
NEM
xEX
Σ Pt (x) FEX
Σ
ti (u x)
Σ
Pi
DL (x)
tt
di (u r) x, u, C7.
aEX
WEH
$ sup
Σ (i(x)) (x)
Σ
x u, G.)
Σ xEX
P (x)
Σ
ग( (u x) x, GT
aeī, FEE
aEM
xx 1
++1++
as M + since the first term is uniformly Lipschitz in by 122 as recursive composition, finite multiplication and addition of Lipschitz. functions, whereas the other terms tend to zero by induction hypothesis. Since the Lipschitz constants do not depend on Σ, the convergence uniform.
To bound the latter term, we first note that (- G)) is always bounded by M, regardless of f, T, iee. again suffices to show that for any family of functions G from X' to uniformly bounded by M,, we have
sup E [x(]] [[((X])| +
gES
The proof is by induction. At = O. we trivially have ((X;) = Ho = L(x.). Assuming that the induction hypothesis holds at t, then at 1 have
sup E ((((++))) [9((X gEG
sup gEG
|E [x(XF, Gf)) E (1,(X, +
by the induction hypothesis, where we defined the uniformly bounded functions
4(x = Σ me(u| xx)
Σ
P(x' [x, u, v)g((')))
KEW
x'EX
with uniform bound M,. Therefore, [J[(m) ( + 0 uniformly over all m
Second term. For the second term, we analogously have
(J (T) - Ju (i)) < (T Ju (T)
1 // [[ W(a,, 3) d3)
Σ 1=0
+
Σ t=u
E [r (XP. ( - E (X," G
24

---

Published as a conference paper at ICLR 2022
where the former term uniformly tends to zero M over all by Lipschitz W from As- sumption 2 and increasingly fine partition intervals I, while for the latter term again show that for any family of functions & from X' to I uniformly bounded by Mr, we have
sup E [x(x E (g( }] + gEG
The proof is by induction. At = O, we trivially have [(x;) = p4 = (. Assuming that the induction hypothesis holds at t, then at t - 1 we have
sup TE [o(x;+1) [g(X D]] = sup gEG
|R (4( G )) (X G )] + 0
gEg
by the induction hypothesis, where we defined the uniformly bounded functions
(x = Σ (e(ul x)
Σ
P(x' 2x (r,u,,)) P)g((')
NEW
r'ER
with uniform bound M,. Therefore, (T Júh (T) + 0 uniformly over all a, x.
Third term. By definition, we have optimality of E ((z) under the approximate mean field μ each representative og. Therefore, the term max (Jur (xz) Ju (I²)) is upper bounded by 0, as there is no policy æ that improves over "
Fourth and fifth term. The results follow from the first and second term by inserting x" for m
Variations on the setting. The infinite horizon discounted case is handled as in the proof of Corol- I.
[A.1 i.e repeating the above up to some chosen time horizon T and trivially bounding all terms with & > T. The block-wise Lipschitz graphon case (20) is handled by choosing the equivalence classes 4 C I such that they are part of at most one block I of the graphon.
Proof of Theorem 5 Now fix any e,p 0. As result of the prequel, have that there exists M' s.t. for all M M
sup max J] (TT" JJ(( 3
aE FEll
Pick any such M > M By Corollary A.1 (for the first and third term, since л is constant with at most M discontinuities) and the prequel (for the second term), there exists N' e N such that for all N >> N' we have
max (J (TT #EIl
1-1
n N J. (T ,..., ,
max
N (mT ,..., 1 n., m xN $ (m)
1
#ell
j (TT) - - (TT
+ max #ell
N
j
(T+)
JN (m ,..., N)
=
3
which holds uniformly over i E Wx for some Wx VN with [Wxl > [(1 p)N], since + arg max Ju (T) by definition a GMFE, Reordering completes the proof.
A.3 EXPERIMENTAL DETAILS
In this section, we will give a full description of all the algorithms and hyperparameters used during our experiments. For reinforcement learning, we use PPO (Schulman et al. 2017).
For the approximate equivalence classes, we shall consider grids (am [0, 1))m with asso-
ciated policies (I m1)... M and mean fields am P(X))) mm=1,... M. For the grid,
25

---

Published as a conference paper at ICLR 2022
Algorithm Fixed point iteration
1: Initialize ju as the mean field induced by the uniformly random policy q.
2: for k 0, o.... do
3: Compute πx E II either directly by PPO on (14), or by computing Q# via Algorithm 2 and
using (38) obtain a softmax policy.
4: Compute f induced by x² using Algorithm or for RL the neighborhood mean fields
G directly using Algorithm 4
5: end for
Algorithm Backwards induction
1: Input: Grid (amm & [0, 1J)m= mean field μ E M.
2: for m = , M do
3: Initialize terminal condition QT for all (z, u, X x xu.
4: to 1,..., do
5: for (I,u) E X do
6: Q (4, I, u) f r(a, u. G. ( +Z P(x' I, U,u, max Qa (1+1, w²).
7: end for
8: end for
9:
end for
10:
Return (Qu m
choose the points a'm. the closest 0mm-
m 100
with m o,..., 100. Here, an agent shall use the policy nm with
To be precise, for the approximate mean field μ (TT) we define pa = = for the an closest to a, i.c. formally, we thus have
(
Σ LEin
(31)
for any fixed policy ensemble n, with fi defined through the recursive equation
p
pos (im
(a')
Σ p
m (u P)) x, u. G.mm) m I....,
.......M..... M (32)
ZEX
where under the assumption of equivalence classes I. [am; bm] of size (bm am); we obtain neighborhood mean fields via
G
Σ (bm am) (a, am)
(33)
Note that in our algorithms, we shall assume equisized partitions and use (bm -0m))m)= 1. Similarly, the policy ensemble is approximated by
M
(()) = Σ 11e2 T. 1=1
(34)
where 7: is the optimal policy of a; for any fixed μr, i.e. the optimal policy and mean field of each approximated by the optimal solution and mean field of the closest Os, which is an increasingly good approximation for sufficiently fine grids under the standing Lipschitz assumptions. In the case of block-wise Lipschitz continuous graphons via (20). a similar justification holds as long as each equivalence class remains constrained to one of the blocks of the graphon, see Theorem 5
In Algorithm I the learning scheme is described on a high level. In our experiments, we either use approximate equivalence classes via Algorithms 2 and reinforcement learning in the form of PPO together with sequential Monte Carlo in Algorithm though in principle one can mix arbitrary methods.
26

---

Published as a conference paper at ICLR 2022
Algorithm 3 Forward simulation
Input: Grid (0m E [0. m M. policy π II.
2: Initialize starting condition Mo No for all m ,,..., M.
3: for 0,
do
4: for = :.......4 M1 do
5: 14-21 >xEx -i (xx) Eneer ip [ u, 1/ Ems (a)m
6: end for
7: end for
8: Return (1 )m M...,MM
Algorithm Sequential Monte Carlo
1: Input: Number of trajectories K 5, number of particles L 200, policy E II.
2: for = 1,..., K do
3: Initialize particles am ~ (ni 1)), x0 ~ po for all m I....,L. L.
4: for ,..., T do
5: for m = 1, 1,.... I do
6: Sample action - (- 84
m.hk).
7: Sample new particle state It41 P(- 14 m,k
mikk
u, 1 Enmn W W(ams On (n)02r.h)
8: end for
9: end for
end for
11:
return neighborhood mean fields G R K I En W(a,am)
1
E
1
We ran each trial of our experiments on a single conventional CPU core, with typical wall-clock times reaching up to at most a few days. We estimate the required compute to approximately 6500 core hours. We did not use any GPUs or TPUs. More specifically, the training of our approximate equivalence class approach took on average approximately 24 hours for 250 iterations in SIS and 50 iterations in Investment. As result, 3 the selection of appropriate temperatures took around 2500 core hours. The PPO experiments took approximately 3 days for each configuration, resulting in approximately 200 core hours for Figure 7 Finally, for the N-agent evaluations in Figure each run up to 100 agents takes up to 4 core hours. Adding on top of that around 250 core hours for the rest of the experiments results in a total of approximately 4000 core hours.
For PPO, we used the RLlib implementation by Liang et al. (2018) (version 1.2.0, Apache-2.0 license). To allow for time-dependent policies, we append the current time to the network inputs. Further, discrete-valued observations are one-hot encoded. Any other parameter configurations are given Algorithms 2 and 4 as well as in Table
As for the specific configurations used in the PPO experiments, we give the hyperparameters in Table Tnd used with a feedforward neural network policy consisting of two hidden layers with 256 nodes and tanh activations, outputting softmax policy over all actions.
A.3.1 PROBLEM DEFINITIONS
For each possible problem setting, we list the applied temperature setting in Table 2 In the follow- ing, let G P(x).
SIS-Graphon. In the SIS SIS-Graphon game as described in the main text, we have X = {S, 4 D), (T( 0.5, r(z, u, G) -2 ( (x) 0.5 I(D) (u) and T {0, (0....,4) 49). Similar parameters produce similar results, and we set the transition probabilities as
IP(S 1, 0.2,
PPT S, U, G) 0.8 -()),
P(1 D.-) 0.
Investment-Graphon. Similarly, in the Investment-Grappon game have X {0, 1, 11...9). 9). 4 = (1,0), = =1, 2, I-Exexx x'G(") 2 ((n) and T = .o........................ 49}. We set
0.3r
27

---

Published as a conference paper at ICLR 2022
Table 1: PPO Hyperparameters
Symbol
Function
Value
Learning rate
0.00005
Discount rate
X
GAE lambda
0.99
CKL
KL coefficient
0.2
B
KL target
0.006
Cent
Entropy coefficient
0.01
Clip parameter
0.2
Training batch size
4000
Bm
Mini batch size
128
ISGD
SGD iterations per training batch
30
Table 2: Temperature configurations
Experiment
17 for approximate equivalence classes
SIS-Grae ISS-Graphon, Wunif SIS- Srs-Grapon,, W Waak SIS-Graphon, Wer Investment-Grappe W ufi
0.101
0.3
0.101
Investment- Graphon, Investment- investment-Graphon, Wer
Invesonent-Graphon, Wrank
0
0.05
the transition probabilities for 0, .,....,aa...
9 - Φ
P( + 1x, I,
10
1 1+
F(x x I,
10
P(r (x,,
while for 9 the next state is always = 9.
A.3.2 EXPLOITABILITY AND TEMPERATURE CHOICE
In the following, will explain choice of temperatures in Table by approximately evaluating the average cxploitability of GMFE candidates (π, μ)) - as is intractable to approximately evaluate the maximum exploitability over all defined by
AJ(T, p1)
sup (+ - (m (m do. Jzmen
(35)
More specifically, when using approximate equivalence classes, we compute the exploitability of some policy π computing the optimal policy л obtained via Algorithm [ under the fixed mean field f generated by via Algorithm 3 inserting n into 335) and then approximating by
1 M
Σ
Σ
mo(x)
Σ To(u x)Qu. x, u).
(36)
m=1.....
TEX
well
Here, we defined for any policy स E II and the policy evaluation functions Qu. as usual via
(t, = r(x, u, G
Σ P(æ' Lx,u
Σ
no(u' [x) (t 1,
(37)
x'EX
w'Ell
with terminal condition Q4." (T, , x, u) = 0, which can be computed as Algorithm see also Puterman (2014) for review.
To achieve convergence of fixed point iterations to approximate equilibria, for previous μ² E M compute the action value function Q!- via Algorithm 2 using approximate equivalence classes
28

---

Published as a conference paper at ICLR 2022
palcy pictor
3.1
$.10
010
$.15
Figure 5: Final approximate exploitability mean and its minimum/ maximum (shaded region) over the last 10 iterations for various temperatures 7). We can see convergence for sufficiently high temperatures and choose the lowest temperature such that we still have convergence with low ex- ploitability. Furthermore, compared to the uniformly random policy, our approximate exploitability problem,
is significantly lower, indicating a good approximate GMFE. For the DivestmentGrrahhe the approximate exploitability of the uniform policy is not shown, as it is above 30. (a): SIS- Graphon; (b): Sevestent-Graphaan
and then define the next policy n+ ((x²)) for every I via the softmax function
Qui (t.
exp
nt1, x) a
1
(38)
Q
Eneu exp
for the closest a; with some temperature 1) > chosen minimally for convergence.
For choosing the temperature, we evaluate the approximate final exploitability at various temper- atures. The results can be seen in Figure where we plot the average, minimum and maximum exploitability over the last 10 iterations of the fixed point learning scheme. The reasoning behind choosing our temperatures as in iab that we can see no fluctuations (indicating convergence of learning scheme) together with a low approximate exploitability at the indicated temperatures.
A.3.3 ADDITIONAL EXPERIMENTS
In Figure 6 we plot investment behavior at quality = O well as expected quality for each of the approximate equivalence class solution, and similarly Figure for the PPO solution with sequential Monte Carlo. Here, for each we averaged quality over all particles within distance of 0.05 to a. We can see that PPO achieves qualitatively and quantitatively similar behavior, deviating slightly due to the approximate optimality of the PPO algorithm. To be precise, when evaluating exploitability via either solution, we find that the learned policy exploitability remains around æ ss 2, compared to & 30 for the uniform random policy.
In Figure g the equilibrium behavior is shown for the Sweetment-Graphoon problem without softmax policy regularization (except for the ER graphon case), as find that the problem already converges to very good equilibrium with low approximate exploitability, see Figure [5) In this problem, we find that the resulting (deterministic without regularization) policy will let agents invest up certain quality, after which any further investment is avoided. The agents with higher connectivity will invest up to lower quality, as they are in competition with more products.
In Figuregland 10 we have performed ablations over the number of equivalence classes for the SIS- Graphon problem. As can observed, the solution obtained by approximate equivalence classes remains stable regardless of the particular number of equivalence classes, showing the stability of discretization approach and supporting Theorem
Finally, in Figure II we exemplarily show training results of applying state-of-the-ar multi-agent reinforcement learning methods such as multi-agent PPO (MAPPO, Yu et al.) (202T) on the finite- agent system with observed, randomized -eeeeiedpeer-ppiodeee graphon indices and W -random graphs. Here, we use the same hyperparameters as shown in Table [ As can be seen, due to the non-station of the other agents, naive application of MARL techniques fails to converge at all.
29

---

Published as a conference paper at ICLR 2022
(8)
Wmiif
(b)
W rak
W.
1.0
1.41
1.0
xr-00
0.3
0.5
5211
0.0
20
40
20
40
20
40
1.0
1.0
L (
1.0
2 0
0.55
0.5
0.5
20
40
20
40
20
40
Figure 6: The M 100 approximate equivalence classes solution of Investment Graphon.. We plot the probability of investing at state = 0 (top) together with the evolution of average quality (bottom). (a): Uniform attachment graphon; (b): Ranked attachment graphon; (c): ER graphon.
Wmmif
1.0
(b)
Wrin
1.01
[c]
Wr,
0
1.0
0.5
0.0
0.0
0.0
20
40
1.0
1.0
1.0
L [16
L
0.5
0.5
0.0
0.0
0.0
20
40
20
Figure 7: The probability investing at state x = (top) together with the evolution of average quality (bottom) for PPO. The solution is similar Figure 6, though slightly different due to the approximations stemming from PPO and sequential Monte Carlo. (a): Uniform attachment graphon; (b): Ranked attachment graphon: (c): ER graphon.
W mt
(b)
W
(c)
W
1.0
1.0
9
1.0
0.5
c 0..
1
0.5
20
411
20
401
201
40
1.0
0.5
0.5
0.5
0.0
0.0
0.0
401
Figure 8: Achieved equilibrium via M = 100 approximate equivalence classes in Investment- Graphon. Top: Maximum quality up to which agents will invest (Iī 2) > 0.5), shown for each a I,t E T. Bottom: Expected quality versus time of each agent I. It can be observed that agents with less connections (higher a) will invest more. (a): Uniform attachment graphon; (b): Ranked attachment graphon; (c): ER graphon.
30

---

Published as a conference paper at ICLR 2022
W
W
W unr
1.0
1.0
1.0
1.0
1.0
1.0
05
92
0.5
0.5
0.5
0.5
0.5
0.5
0.0
0.0
40
20
40
0.50
1.0
0.25
0.25
0.5
0.5
(00
0.00
0.0 0.00
0.0 0.00
0.0
40
20
Figure 9: Achieved equilibrium via approximate equivalence classes in SIS SIS-Grapher Graphon for the uniform attachment graphon, plotted for each representative a; E Z. Top: Probability of taking precautions when healthy. Bottom: Probability of being infected. (a): .M- = 10; (b): M 30; (c): M 50.
(8)
W
(b)
Wrak
(c)
Wank
1.0
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
0.0
40
20
0.50
1.0
0.50
1.0
0.50
1.0
0.25
0.5
0.25
0.5
0.25
0.5
0.00
20
40
20
40
0
20
40
Figure 10: Achieved equilibrium via approximate equivalence classes in SIS- SIS-Graphon for the ranked attachment graphon, plotted for each representative a; E I. Top: Probability taking precautions when healthy. Bottom: Probability of being infected. (a): M 10; (b): M 20; (c): M 30.
1.0
WM
088
-1000
0.6
0.6
of expacted
-1000
04
-1200
1..
02
13000
0.0
0.0
50
100
230
30
40
Iterations
Figure 11: Learning curve and results for an exemplary straightforward application of multi-agent PPO (MAPPO, Yu et al. (202T).. Left: Sum of expected agent objectives over learning iterations; Right: Final policy probability of taking precautions when healthy.
31


Reviews:
[{"review_id": "zW-ZBaZGo37", "reviewer": "Reviewer_wpJP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Graphon games are an emerging topic of research and developing learning algorithms for such games is an interesting research direction. Furthermore, the authors provide rigorous proofs for the statements of their main results. The proof techniques are quite classical in the mean field game literature, but it is nice that the authors provide detailed proofs in the appendix. \n\nMy concerns are the following:\n\n1. Definition 1: It would be helpful for the reader to clarify why you use this notion, which is weaker than the simpler and more classical notion of $\\epsilon$-Nash equilibrium. Is there a classical reference for this notion? By the way, is it connected to the notion of $(\\epsilon,\\delta)$ mean field Nash equilibrium considered (for the limiting game) e.g. in (Elie et al., 2020)?\n\n2. Theorems 2 and 3: the Lipschitz condition on $\\boldsymbol{\\pi}$ seems very restrictive. The authors state that it is easy to verify it in “the case where only finitely many optimality regimes exist over all graphon indices”. Although this property probably holds for block-wise constant graphons, I imagine it is not satisfied in many interesting examples. It would be helpful to formulate conditions on the model (transition and reward functions) that are sufficient to obtain this Lipschitz continuity. \n\n3. About the computational advantage of GMFG: below Theorem 3, the authors recall that computing Nash equilibria in finite-player games is in general \"highly intractable\". However, here the authors consider a special class of games. Could you quantify the computational advantage brought by the graphon game framework compared with its N-player counterpart? It seems that (1) the class of graphon games studied in this paper is quite restrictive due to the regularity assumptions and the fact that the transition and reward functions are the same functions for all players and (2) the authors use extra approximations in the two proposed numerical approaches so we can imagine that these methods compute only approximations of Nash equilibria. So overall, I am not sure whether the graphon games considered in this work are really more tractable than their N-player counterparts. It would be very important to explain this better in order to clarify the advantages of the proposed approaches. \n\n4. About the numerical examples: For the first example (SIS-example in section 5.1), the results are interesting but there is not clear description of which algorithm is being used. In Figure 7 (appendix), it is nice to see the influence of the temperature. But sometimes the temperature required to get convergence is not negligible. I imagine that due to this issue, the solution can be quite different from the true Nash equilibrium. So do we know the influence of this temperature on the policy computed by the algorithm? \n \nReference: \n(Elie et al., 2020) Elie, R., Perolat, J., Laurière, M., Geist, M., & Pietquin, O. (2020, April). On the convergence of model free learning in mean field games. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 34, No. 05, pp. 7143-7150).", "summary_of_the_paper": "This paper studies a class of games with a continuum of agents that connected by a graphon. This corresponds to the limit of games with a finite number of players connected by a graph. In the recent literature, such games have been considered in continuous time, and here the authors focus on a discrete time version. They first analyze the game by showing existence of a Nash equilibrium (defined in a suitable sense), and they prove that using the equilibrium policy from the game with a continuum of players in a game with a finite number of players provides an approximate Nash equilibrium. Then, two numerical approaches are proposed, both based on fixed point iterations that alternate between updating the distribution and updating the optimal control. The first method relies on backward induction to compute the optimal control of representative agents in a set of equivalence classes. The second method relies on reinforcement learning to compute the optimal control. Last, numerical examples are provided. ", "summary_of_the_review": "The authors provide theoretical results showing the game is well posed, and they provide interesting numerical results (also in the appendix). But overall I am not sure whether the “learning” part is really crucial in the paper. If it is the case, more explanations on the advantages of the proposed approach should be included.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "uzSO2O55Py", "reviewer": "Reviewer_V2M1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Proposition 2 is very standard in the MFG literature. However, the assumption seems very abstract and too strong. The authors should give some discussions on when the assumption holds or how to verify this assumption, especially the existence of the Lipschitz mapping $\\hat{\\Phi}$, which is an element chosen from a set mapping (e.g., how it is chosen). Some more formal and detailed explanations are needed here. \n2. The first algorithm for learning GMFG in Section 4 is not well-explained. More details should be provided. In the first method in Section 4, it’s not clear why it makes sense to discretize $\\alpha$ into $\\alpha_i$’s and solve optimal control problems for each equivalence class of the associated $\\alpha_i$. More formal justifications of this algorithm is needed to understand how it’s derived, especially given that it has no convergence analysis. \n3. The algorithms used in the experiments can not solve exactly for the NE of the GMFG problem since they all use discretization. And the error induced by this discretization is not mentioned in the paper. It is also not clear what discretization (the value of $M$) is chosen in Algorithm 2 and 3. If we want to find the NE for GMFG, it would be better if experiments can show how solution evolves when $M$ gets larger instead of fixing one value of $M$.\n4. There is no theoretical convergence or related performance analysis regarding the two proposed algorithm in Section 4, which largely limited the paper's algorithmic contributions. Proposition 2 is mostly an existing result in the classical learning MFG literature, and neglects all kinds of randomness and approximation, which is not very meaningful. \n5. The numerical results lack some comparisons with existing MARL algorithms (with and without mean-field approximations, e.g., those in Yang et al., 2018).  ", "summary_of_the_paper": "This paper studies discrete time dense graph mean field games (GMFG). It discusses the settings of both finite-agent graph game and GMFG and shows that under mild Lipschitz continuous assumptions, the Nash equilibrium of the GMFG exists. It establishes that the NE of the GMFG is a good approximation of the NE of an N-agent game and empirically verifies this result. It then proposes two algorithms for solving the NE of GMFG, one with the idea of discretizing the graphon index, and the other utilizing the equivalence of GMFG to a classical MFG with an extended state space. The proposed algorithms are tested on an SIS-Graphon problem and an Investment-Graphon problem to validate their performances. ", "summary_of_the_review": "This paper provides some nice contributions to the theory of graphon mean-field games in discrete-time settings. It also provides some heuristic learning algorithms, though without theoretical justifications. Some preliminary numerical results are also provided, but without comparisons with the existing MARL algorithms.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ipaJZDcso20", "reviewer": "Reviewer_GRFn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Major Pros]\n\nThis paper proposes a novel GMFG framework, with a relatively complete characterization of the GMFE existence and graphon mean-field approximation errors. The proposed learning algorithms and the numerical experiments also add to the practical contribution of this paper.\n\n[Major Cons]\n\nDespite the several pros mentioned above, there are also some issues that the authors need to address and/or improve on, as listed below.\n1. Section 2 is a bit too heavy as an introductory section. It might be better to start with Section 2.1, and describe the idea of local interaction and local averaging for a group of networked agents in a more intuitive manner. Some visualization of the N-agent scenario will also be helpful (see e.g., (Yang et al., 2018)). \n2. The algorithm description and motivation of the first learning method (which discretizes the graphon index) are not sufficiently clear. It would be helpful to compare this discretization approach with multi-population mean-field games in more details and discuss about what are the benefits of considering GMFG, and to better explain why for each equivalence class the optimal control problems can be solved independently. The verbal description is a bit too informal, while the Appendix A.3 is too focused on the experiment details while not providing sufficient explanations on how these heuristic algorithms are derived. The justification of the algorithm design logic is especially important since no formal convergence theory for the proposed learning algorithms is established. \n3. The numerical experiments lack some important comparisons. Firstly, since GMFG is proposed to solve N-player games approximately, existing algorithms for solving N-player games (especially those proposed for multi-agent reinforcement learning) are all fair comparisons. Hence to demonstrate the effectiveness of the proposed two learning schemes, comparisons with algorithms such as those mentioned in (Yang et al., 2018) and [A] are needed. Also, performance in the N-player setting is only demonstrated with the indirect metric (26), which is not sufficiently convincing and informative. \n\nThere are also some more minor comments and questions, as detailed below:\n1. The authors should compare with [B].\n2. On page 2, should “Graph mean field systems” be “Graphon mean field systems”?\n3. Please discuss more about the relationship between the GMFG model and the one adopted in (Yang et al., 2018) and [C], which are also related to graph based games. \n4. In Section 5.2, do you mean that (26) instead of (19) is evaluated? And what is \\pi^{\\alpha_i} and how is it computed? \n5. In Section 6, what does “graphon index estimation become important for finite system model-based RL” mean? \n6. In Appendix A.3.1, what is G(I)? \n\n[A] Lowe, Ryan, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. \"Multi-agent actor-critic for mixed cooperative-competitive environments.\" arXiv preprint arXiv:1706.02275 (2017).\n\n[B] Vasal, Deepanshu, Rajesh Mishra, and Sriram Vishwanath. \"Sequential decomposition of graphon mean field games.\" In 2021 American Control Conference (ACC), pp. 730-736. IEEE, 2021.\n\n[C] Yang, Jiachen, Xiaojing Ye, Rakshit Trivedi, Huan Xu, and Hongyuan Zha. \"Learning deep mean field games for modeling large population behavior.\" arXiv preprint arXiv:1711.03156 (2017).\n", "summary_of_the_paper": "This paper proposes a discrete-time graphon mean-field game (GMFG) framework as a limiting model to approximate large population dense graph games. Existence of graphon mean-field equilibrium (GMFE) is proved by reformulating GMFG as a classical MFG, and a graphon mean-field approximation result is also obtained. The authors then propose two learning algorithms for computing GMFE, one based on discretizing the graphon index, while the other based on the aforementioned classical MFG reformulation. Some preliminary numerical experiments are also provided to demonstrate the theoretical findings and to validate the proposed algorithms. ", "summary_of_the_review": "The contribution on proposing discrete-time GMFG and establishing existence and approximation results are good, but the algorithmic and numerical contributions are limited. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "hLdB05jSjqF", "reviewer": "Reviewer_B2QF", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think the paper makes a strong and important contribution. To the best of my knowledge, the results in this work are novel: the formulation for graphon mean field games is new, the existence and convergence results are new, and the algorithm is novel as well. The problem considered in the paper is an important problem in practice: in many applications, the subjects of interest interact with each other. The authors provide a strong solution to the problem, from modeling, to theory, to algorithm. The paper is also well-written and I enjoyed reading it. \n\nI don’t see a clear weakness of the paper. Here are a few things I’d love to see (which of course might be beyond the scope of this work due to page limit)\n-\tSparse graphon, i.e., the graphon W_N / rho_N -> W, where rho_N is the sparsity parameter that goes to 0 as N goes to infinity. As far as I checked, I think the proofs can still go through in this case (as long as rho_N is not too small). I think this might be a more realistic setting in practice, since we won’t be interacting with a constant proportion of people in the world. \n-\tIs it possible to obtain a result on convergence rate for Proposition 2?  \n", "summary_of_the_paper": "This paper studies Markov games with large number of agents. The authors start by proposing a novel discrete-time formulation for graphon mean field games. They show that the mean field game exists, and that finite graph games converge to the mean field game when the number of agents goes to infinity. They also provide an algorithm that learns an approximate Nash equilibria. ", "summary_of_the_review": "Overall, I think the paper makes a strong and important contribution. The results in this work are novel and important. The paper is well-written. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies graphon mean-field games, whereby a continuum of agents are connected by a graphon. They study a discrete time version and show existence of a Nash equilibrium (under Lipschitz conditions). Moreover they prove that it corresponds to an approximate Nash equilibrium for the game with a finite number of players, thereby validating graphon mean-field games as a natural abstraction when the number of players is sufficiently large. Finally they give algorithms based on fixed point iterations (one based on discretizing the graphon index, the other based on reformulating it as a classical mean-field game) for computing such an equilibrium. They give numerical experiments to validate their approach. The reviewers pointed out various writing issues or other results that would help complete the picture. Many of these were addressed and/or clarified by the authors in their revision. Overall the paper provides an appealing and relatively complete characterization of equilibria in graphon mean-field games.
Decision: Accept (Poster)