Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper considers the problem of model-free reinforcement learning in discrete-time, linear-quadratic Markovian mean-field games with ergodic costs. The authors begin by establishing the existence and uniqueness of the Nash equilibrium in such a setting, and then proposes an mean-field actor-critic algorithm with linear function approximation. The proposed algorithm is shown to converge linearly with high probability under certain standard conditions. 

The paper is novel in the sense that it extends the recent previous works on model-free learning of MFGs to continuous state-action state spaces, while showing linear global convergence under certain conditions. To my knowledge, the previous works either considers the discrete state-action spaces [Guo et al. (2019)] or has only convergence to local Nash equilibrium (NE) [Jayakumar and Aditya (2019)]. However, I have the following concerns and suggestions for this paper.

1. Some claims of contribution is not very accurate. For example, the paper claims that the proposed algorithm does not require a simulator but only observations of trajectories. However, to invoke Algorithm 2 (mixed actor-critic), one has to fix the mean-field state \mu, which would have required a simulator for running the mixed actor-critic algorithm. Otherwise, the \mu could change if completely following the trajectory. This is the same setting as in some previous works like [Guo et al. (2019)]. The authors may want to double check if this kind of high level claims are accurate or not.

2. The problem setting is not very well stated in Section 2. 
1) The authors should better call the problem at the beginning of Section 2 a "linear-quadratic mean-field N_a-player game", instead of a "linear-quadratic mean-field game", to differentiate from Problem 2.1 below. 
2) The dimensions and assumptions of A, B, Q, R are also not mentioned until Section 3.1, which is also slightly breaking the reading flow. 
3) The policies are also not clearly defined -- e.g., are they stationary or non-stationary, random or deterministic? And are we considering symmetric Nash equilibrium only (which should be so according to the later parts), i.e., all policies \pi^i are the same?
4) In the definition of Problem 2.1, the Nash policy \pi^\star is stated without even defining what the Nash in such a problem is. Similarly, after problem 2.2, Nash equilibrium is mentioned again without defining it. To address the issue, the authors may want to rewrite the cost function in problem 2.1 as J(\pi,\pi'), where \pi and \pi' are two arbitrary policies, and \pi' is not necessarily the Nash policy. Then x_t' (instead of x_t^\star) is the trajectory generated by \pi'. 
5) The authors should not mention problem 2.2 right after problem 2.1. Instead, the authors should add a problem called LQ-SMFG (linear-quadratic stationary MFG), which is basically problem 2.2 but the goal is to simultaneously find \mu^\star and \pi_{\pu}^\star. For such a problem, the objective function can be written as J(\pi,\mu), where \mu basically serves the same role as \pi' in the suggested modification to problem 2.1 above. The original problem 2.2, which is the subproblem of finding \pi_{\mu}^\star given \mu according to Section 3, should be put after introducing \Lambda_1, as it is exactly what \Lambda_1 is solving. The paper should then completely focus on this LQ-SMFG instead of LQ-MFG, as explained in the next point.
6) In Definition 2.3, it should refer to LQ-SMFG mentioned above, as \mu does not even appear in problem 2.1. In addition, the definition of \Lambda_2 is also not clear. The authors may want to state it more clearly, e.g., using a one-step definition as in [Guo et al. (2019)]. 

3. The mixed actor-critic algorithm (with linear approxiamtion) for the subproblem D-LQR for evaluating \Lambda_1 is not well motivated. 
1) For example, the authors should better highlight the difficulty of having the drift terms. The authors do show through propositions 3.3 and 3.4 how they decompose the objective into a standard LQR problem (J_1) and the problem w.r.t. a drift term (J_2). However, it is not clear why this is a must. In particular, why can't we just simply apply the natural actor-critic algorithm on the joint space of K and b? 
2) Also linear approximation is not mentioned in the main text, which should be discussed given its appearance in the abstract. Otherwise, it seems to be a low-hanging fruit given the previous works like [Yang et al. (2019)]. 
3) Why do the authors use natural actor-critic for finding K, but just classical actor-critic to find \mu? This should be further explained. And instead of referring to appendix B repeatedly, the authors might want to directly state the assumptions needed for the input parameters on a high level to make the paper more self-contained (e.g., that the subproblem iteration numbers exceed certain threshold).

Some minor suggestions.
1) The discussion about why the Markov chain of states generated by the Nash policy \pi^\star admits a stationary distribution on page 4 is not clear. In general, don't we need additional assumptions like the ergodicity of the induced Markov chain?
2) The claim that there exists a unique optimal policy \pi_{\mu}^\star of Problem 2.2 on page 5 is not clearly stated with the necessary assumptions. The authors should at least mention that under certain standard conditions, etc.
3) In (2.1), there should also be \sigma\in \mathbb{R}.
4) On top of page 6, the authors may want to give an example of the so-called "mild regularity conditions" (e.g., positive definite of Q and R, etc.).
5) At the bottom of page 6, P_K is not defined clearly -- is it the solution to the Riccati equation? And how does it relate to the X in the Riccati equation of assumption 3.1(i)?


review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: Summary
The present work is concerned with providing a provably convergent algorithm for linear-quadratic mean field games. Here, for a given average behavior of the (large number of) players, the optimal strategy is given by an LQR with drift and the solution of the mean field game consists in finding a pair of (π , μ ) such that π = π(μ) is an optimal strategy under the mean field (the average behavior) μ and μ = μ(π, μ) is the mean field obtained if all players use the strategy π, under the mean field μ. First, the authors show that under "standard" assumptions the map μ ↦ μ(π(μ)), μ) is contractive and hence, by the Banach fixed point theorem, has a unique solution, resulting in a unique Nash equilibrium of the mean-field game. Second, they show that by using an actor-critic method to approximate π(μ) for a given μ, this argument can be turned into an algorithm with provably linear convergence rate. The authors prove a natural result that seems to be technically nontrivial (I did not have the time to follow their proof in detail). Thus, I believe the paper should be accepted.

Questions/Suggestions to the author
(1) It might be helpful for the reader to include a rough sketch of the proof and algorithm earlier in the paper

(2) Since, as you mention, Assumption 3.1 (ii) "is standard in the literature", I would assume that it has been used before in order to prove existence of Nash equilibria using the Banach fixed point theorem? If so, I would suggest pointing this out to the reader and briefly mentioning the differences (if any) to the existing proofs in the literature.

(3) On the bottom of page 4 you argue that the expectation of the state converges to a constant vector in the limit of large time, "since the Markov vhain of states ... admits a stationary distribution". In general, the existence of a stationary distribution does not imply convergence to the stationary distribution. Could please explain?
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: Summary and Decision 

This paper studied an actor-critic learning algorithm for solving a mean field game. More specifically, the authors showed a particular actor-critic algorithm converges for linear-quadratic games with a quantitative bound in Theorem 4.1. Notably, results on learning algorithms for solving mean field games without prior knowledge of the parameters are rare, so results of this type is highly desirable. However, the algorithm studied in this paper is uniquely tailored for the (very special!) linear-quadratic setting, which is very unsatisfying. We will discuss concern this in detail below. 

Overall, I recommend a weak accept for this paper. 

Background 

Mean field games is a theory of large population games, where we assume each agent has infinitesimal contributions to the dynamics in the limit as number of agents go to infinity. Similar to mean field theory of particles, the limiting dynamics can be completely characterized by a single distribution of agents, commonly know as McKean-Vlasov dynamics. The theory drastically simplifies computation for large population games: while it is essentially impossible to find a Nash equilibrium for a 100 agent game, we can compute the Nash equilibrium for the mean field limit and approximate the finite game. 

Mathematically, mean field games remain very difficult to solve even knowing the parameters and dynamics. Therefore it is often important to first study a simple case where we can solve the game analytically. In the context of optimal control and mean field games, we can often recover closed form solutions (up to the solution of a Riccati equation) when the dynamics are linear and the cost is quadratic. We call this class of games linear-quadratic mean field games (LQ-MFG). To interpret the LQ assumption, typical control problems in this setting can be recast into a convex optimization problem in the control (or strategy) using convex analysis techniques. Therefore LQ assumptions provides both theoretical and computational tractability. 

Here we will specifically note the paper of Elliot, Li, and Ni, where we can find a closed form solution of the discrete time LQ-MFG with finite horizon. 
https://arxiv.org/abs/1302.6416

Furthermore, we will also distinguish between games with a finite horizon and infinite horizon. While there are difficulties associated with both cases, typically an ergodic infinite horizon problem removes the time variable from the equation, making the problem slightly easier. Hence many researchers in MFG prefer to begin by studying the ergodic problem. 

In the context of reinforcement learning, we are more interested in solving MFG without knowledge of underlying parameters, dynamics, or even the cost function. This direction is still relatively new for the MFG community, and many problems remain open. The ultimate goal of this line of research is to develop generic and scalable algorithms that can solve general MFGs without knowledge of the game parameters/dynamics/cost etc. 


Discussion of Contributions 

This work is the first analysis of actor-critic algorithms for solving MFG. At the same time, the paper studies discrete time MFGs, which is generally less popular but no less interesting. Therefore a theoretical convergence result in this setting is highly desired. 

Overall, the mathematical set up of this problem is very convoluted. This likely motivated the authors to make more simplifying LQ type assumptions to recover stronger results. Even with these assumptions, to put all the pieces of the puzzle together is no easy task. The authors have to consider the interaction between the agent state and the mean field state, as well as the estimation of optimal controls and how to bound errors from estimation error. This led to a long appendix of proofs - while too lengthy to verify, the results seem sensible. 

From this, I believe the mathematical analysis itself is a worthy contribution. This paper will serve as a good starting point for future analysis of more complex problem settings and other learning algorithms in MFGs. 


Discussion of Limitations 

The main concern regarding this paper is on quantifying how much of a contribution the results add to the broader community. While results on LQ-MFGs are always nice to have, I believe the specific actor-critic algorithm depends too much on the LQ structure for this work to be useful. Two examples of these are:

1. on page 5, above equation (2.1), the actor-critic algorithm will be only seeking policies that are linear in the state x. This is taking advantage of the fact that we know LQ-MFGs have linear optimal policies. 
2. on page 7, below equation (3.7), the algorithm requires to know the form of the gradient of the cost function - and therefore leading to a direct estimation of matrices \Upsilon that form the gradient. This is only possible in LQ-MFGs. 

Therefore, results from this paper will be very difficult to generalize to other actor-critic algorithms for LQ-MFGs. At the same time, it's also difficult to generalize these results to the same actor-critic algorithm for non-LQ-MFGs. 

We also note that if we can assume knowledge of the LQ form of underlying dynamics and the form of the cost function, but no knowledge of the parameters, the problem reduces down to a parameter estimation problem. In this case, we can speculate the results of Elliot, Li, and Ni can be adapted to the ergodic case, and we can recover the approximate optimal controls given estimated parameters. Furthermore, in some sense, this particular actor-critic algorithm is implicitly estimating a sufficient set of parameters (the \Upsilon matrices) to find the optimal control. Essentially, if we rely too much on the LQ structure, the problem is then rendered much less interesting. 

In summary, the ultimate goal of this line of research is to approximately solve non-LQ games, therefore the value of this current paper is very incremental in the larger context of learning MFGs. While serving as a reference for future analysis of related algorithms for MFGs, it will be difficult to borrow concrete ideas and results from this paper to build on. 

*Edit:* I believe the discussions below have address several important concerns, and I will raise my score to accept.
review_title: Official Blind Review #2

Meta-review: The authors propose an actor-critic method for finding Nash equilibrium in linear-quadratic mean field games and establish linear convergence under some assumptions. There were some minor concerns about motivation and clarity, especially with regards to the simulator. In an extensive and interactive rebuttal, the authors were able to argue that their results/methods, which appear to be rather specialized to the LQ setting, offer insight/methods beyond the LQ setting.
Decision: Accept (Poster)