Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
main_review: [Major Pros]

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

[Major Cons]

Despite the several pros mentioned above, there are also some issues that the authors need to address and/or improve on, as listed below.
1. 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)). 
2. 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. 
3. 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. 

There are also some more minor comments and questions, as detailed below:
1. The authors should compare with [B].
2. On page 2, should “Graph mean field systems” be “Graphon mean field systems”?
3. 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. 
4. 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? 
5. In Section 6, what does “graphon index estimation become important for finite system model-based RL” mean? 
6. In Appendix A.3.1, what is G(I)? 

[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).

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

[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).

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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. 

My concerns are the following:

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

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

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

4. 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? 
 
Reference: 
(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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
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. 
2. 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. 
3. 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$.
4. 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. 
5. 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
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. 

I 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)
-	Sparse 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. 
-	Is it possible to obtain a result on convergence rate for Proposition 2?  

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.
review_title: null

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)