Provable Fictitious Play for General Mean-Field Games
Authors: Qiaomin Xie
Zhuoran Yang
Zhaoran Wang
Andreea Minca
Venue:  (2021)
Keywords: Mean-field games
Fictitious play
Entropy regularization
Nash equilibrium

Abstract: We propose a reinforcement learning algorithm for stationary mean-field games, where the goal is to learn a pair of mean-field state and stationary policy that constitutes the Nash equilibrium. When viewing the mean-field state and the policy as two players, we propose a fictitious play algorithm which alternatively updates the mean-field state and the policy via gradient-descent and proximal policy optimization, respectively. Our algorithm is in stark contrast with previous literature which solves each single-agent reinforcement learning problem induced by the iterates mean-field states to the optimum. Furthermore, we prove that our fictitious play algorithm converges to the Nash equilibrium at a sublinear rate. To the best of our knowledge, this seems the first provably convergent reinforcement learning algorithm for mean-field games based on iterative updates of both mean-field state and policy.

Under review as a conference paper at ICLR 2021
PROVABLE FICTITIOUS PLAY FOR GENERAL MEAN- FIELD GAMES
Anonymous authors Paper under double-blind review
ABSTRACT
We propose a reinforcement learning algorithm for stationary mean-field games, where the goal is to learn a pair of mean-field state and stationary policy that con- stitutes the Nash equilibrium. When viewing the mean-field state and the policy as two players, we propose fictitious play algorithm which alternatively updates the mean-field state and the policy via gradient-descent and proximal policy opti- mization, respectively. Our algorithm is in stark contrast with previous literature which solves each single-agent reinforcement learning problem induced by the it- erates mean-field states to the optimum. Furthermore, we prove that our fictitious play algorithm converges to the Nash equilibrium sublinear rate. To the best of our knowledge, this seems the first provably convergent reinforcement learning algorithm for mean-field games based on iterative updates of both mean-field state and policy.
INTRODUCTION
Multi-agent reinforcement learning (MARL) (Shoham et al. 2007 Busoniu et al., 2008 Hernandez- Leal et al., 2017: Hernandez-Leal et al.)
Zhang et al.) (019) aims to tackle sequential decision-
making problems in multi-agent systems
Wooldridge 2009) by integrating the classical reinforce-
ment learning framework (Sutton & Barto 2018) with game-theoretical thinking (Başar & Olsder)
1998.. Powered by deep-learning (Goodfellow al., (016). MARL recently has achieved striking
empirical successes in games (Silver et al.] [016:] |0 et al.. 2019: Berner et al. 2019
Schrittwieser al. 2019), robotics (Yang & Guj 20044; Busoniu et al. 2006 Leottau et al. 2018).
transportation (Kuyer et al.
2008 Mannion et al. (2016), and social science (Leibo et al.
2017
Jaques et al. 2019 Cao et al. 2018 McKee et al. 2020).
Despite the empirical successes, MARL is known to suffer from the scalability issue. Specifically, in a multi-agent system, each agent interacts with the other agents as well as the environment, with the goal of maximizing its own expected total return. As result, for each agent, the reward function and the transition kernel of its local state also involve the local states and actions of all the other agents. As result, the number of agents increases, the capacity of the joint state-action space grows exponentially, which brings tremendous difficulty to reinforcement learning algorithms due to the need to handle high-dimensional input spaces. Such a curse of dimensionality due having a large number of agents in the system is named as the "curse of many agents" (Sonu et al. 2017).
To circumvent such notorious curse, popular approach is through mean-field approximation. which imposes symmetry among the agents and specifies that, for each agent, the joint effect of all the other agents summarized by a population quantity, which oftentimes given by the empirical distribution of the local states and actions of all the other agents or a functional of such an empirical distribution. Specifically, to obtain symmetry, the reward and local state transition functions are the same for each agent, which are functions of the local state-action and the population quantity. Thanks to mean-ficld approximation, such a multi-agent system, known as the mean- mean-field game (MFG) (Huang et al. 2003 Lasry & Lions 2006a b) 2007 [Huang et al. 2007 Guéant et al. 2011 Carmona & Delarue 2018). is readily scalable to an arbitrary number of agents.
In this work, aim find the Nash equilibrium (Nash 1950) of MFG with infinite number of
agents via reinforcement learning. By mean-field approximation, such a game consists of a pop-
ulation of symmetric agents among which each individual agent has infinitesimal effect over the

---

Under review as a conference paper at ICLR 2021
whole population. By symmetry, it suffices to find symmetric Nash equilibrium where each agent adopts the same policy. Under such consideration, we can focus on a single agent, also known as the representative agent, and view MFG as a game between the representative agent's local policy t and the mean-field state & which aggregates the collective effect of the population. Specifically, the representative agent aims find the optimal policy when the mean-field state is fixed to L, which reduces to solving a Markov decision process (MDP) induced by L. Simultancously, we aim let & be the mean-field state when all the agents adopt policy æ. The Nash equilibrium of such a two-player game, (s* ), yields symmetric Nash equilibrium x² of the original MFG.
Under proper conditions, the Nash equilibrium (T" can be obtained via fixed-point updates, which generate a sequence {T,, } as follows. For any t 2 O, in the t-th iteration, we solve the MDP induced by L, and let TT be the optimal policy. Then we update the mean-field state by letting Li+1 be the mean-field state obtained by letting every agent follow Te. Under appropriate assump- tions, the mapping from f, to L1+1 is contraction and thus such an iterative algorithm converges to the unique fixed-point of such contractive mapping, which corresponds to - (Guo et al. 2019).
Based on the contractive property, various reinforcement learning methods are proposed to approxi-
mately implement the fixed-point updates and find the Nash equilibrium (*) (Guo et al. 2019
2020 Anahtarci et al.] 2019b]a al 2020). However, such an approach requires solving a standard reinforcement learning problem approximately within each iteration, which itself is solved by an
iterative algorithm such as Q-learning (Watkins & Dayan 1992 Mnih et al. 2015
Bellemare et al.
2017) or actor-critic methods (Konda & Tsitsiklis [2000] Haarnoja et al., 2018 Schulman et al.
2015 2017). As a result, this approach leads to a double-loop iterative algorithm for solving MFG. When the state space S is enormous, function approximation tools such as deep neural networks are equipped to represent the value and policy functions in the reinforcement learning algorithm, making solving each inner subproblem computationally demanding.
To obtain a computationally efficient algorithm for MFG, we consider the following question:
Can we design a single-loop reinforcement learning algorithm for solving MFG which updates the policy and mean-field state simultaneously in each iteration?
For such a question, we provide an affirmative answer by proposing a fictitious play (Brown 1951) policy optimization algorithm, where we view the policy and mean-field state L as the two players and update them simultaneously in each iteration. Fictitious play is a general algorithm framework for solving games where each player first infers the opponent and then improves its own policy based on the inferred opponent information. When it comes to MFG, in each iteration, the policy player π first infers the mean-fiels field state implicitly by solving policy evaluation problem associated with π on the MDP induced by L. Then the policy æ is updated via proximal policy optimization (PPO) (Schulman et al.) 2017) step with entropy regularization, which is adopted to ensure the uniqueness of the Nash equilibrium. Meanwhile, the mean-field state L obtains its update direction by solving how the mean-field state evolves when all the agents execute policy π with their state distribution being C. Then C is updated towards this direction with some stepsize. Such an algorithm is single- loop as the mean-field state L is updated immediately when π is updated.
Furthermore, since L is distribution over the state space S, when S is continuous, L lies in an space, which makes it computationally challenging to be updated. To overcome this challenge, we employ a succinct representation of L via kernel mean embedding, which maps L to an element in a reproducing kernel Hilbert space (RKHS) (Smola et al.) [007] Gretton et al.) 2008 Srrieeumbuuur al. 2010). Such mechanism enables within RKHS, which can be computed efficiently.
update the mean-field state
When the stepsizes for policy and mean-field state updates are properly chosen, we prove that our single-loop fictitious play algorithm converges to the retropy-regularized Nash equilibrium at sub- linear ((T-1/5)-rat where T is the total number of iterations and ((-) hides logarithmic terms. To our best knowledge, we establish the first single-loop reinforcement learning algorithm for mean- field game with finite-time convergence guarantee to Nash equilibrium.
Our Contributions. Our contributions are two-fold. First, we propose a single-loop fictitious play algorithm that updates both the policy and the mean-field state simultaneously in each iteration, where the policy is updated via entropy-regularicg proximal policy optimization. Moreover, we utilize kereel mean embedding to represent the mean-field states and the policy update subroutine
2

---

Under review as a conference paper at ICLR 2021
can readily incorporate any function approximation tools to represent both the value and policy functions, which makes our fictitious play method a general algorithmic framework that is able to handle MFG with continuous state space. Second, prove that the policy and mean-fiell state sequence generated by the proposed algorithm converges to the Nash equilibrium of the MFG at a sublinear O rate.
Related Works. Our work belongs to the literature on discrete-time MFG. A variety of works have focused on the existence of a Nash equilibrium and the behavior of Nash equilibrium as the number of agents goes to infinity under various settings of MFG. See, e.g.. Gomes et al. 2010); Tembine & Huang (20TT); Moon & Başar (2014); [Biswas (2013): Saldi al. (2018b al 2019 | Wiecek] (2020) and the references therein. In addition, our work is more related to the line of research that aims to solve MFG via reinforcement learning methods. Most of the existing works propose to find the Nash equilibrium via fixed-point iterations in space of the mean-fiell states, which requires solving Anahtarci ct al., 2019a b; Fu ct al. 2019, uz Zaman et al., 2020, Anahharci et al. 2020). Among these works, Guo iet al. 2019: 2020;; ; Anahtarci et al. (2019) 9a bb 2020) propose to solve each MDP via Q-learning Watkins & Dayan (1992) or approximated value iteration (Munos & Szepesvári] 2008). whereas Fu itt a (2019): uz Zaman et al. (2020) solve each MDP using actor-critic (Konda & Tsitsiklis 2000)
an MDP induced by mcan-fire -feld state within each iteration (Guo et al. 2019 2020
under the linear-quadratic setting. Furthermore, more closely related works are Eliie al. (2019);
Perrin et al. 2020)), which study the convergence of a version of fictitious play for MFG. Similar to our algorithm, their fictitious play also regards the policy and the mean- -eeud state as the two players. However, for policy update. they compute the best response policy to the current mean-field state by solving the MDP induced by the mean-field state to approximate optimality, and the obtained policy is added to the set of previous policy iterates to form a mixture policy. As result, their algorithm is double-loop in essence due to solving an MDP in each iteration. In contrast, our fictitious play is single-loop the policy is updated via a single PPO step in each iteration, and the mean-field state is updated before the policy solves any MDP associated with a mean-field state.
Notations. We use ||-1|, to denote the vector norrm, and A A(D) the probability simplex over D. The Kullback-Leibler (KL) divergence between Pl,22 E ((A) is defined as DKL (xi(ll))))) (|p2) == EaEA Pi (a) log pa(a) Let 1, IR²" denote the all-one vector. For two quantities x and y that may depend on problem parameters (IA),, 7, etc.), if x 2 Cy holds for a universals constant C > O, we write Z y. x ((y) and y (z). We use Ō(-) to denote O(-) ignoring logarithmic factors.
p2(a)-
BACKGROUND AND PRELIMINARIES
In this section, we first review the standard setting mean-field games (MFG) from Guo et al. 2019) and then introduce a more general MFG with mean embedding and entropy regularization.
2.1 MEAN-FIELD GAMES
Consider discrete- time Markov game involving an infinite number of identical and interchangeable agents. Let S C Rd and A C R2 be the state space and action space, respectively, that are common to the agents. We assume that S is compact and A is finite. The reward and the state dynamic for each agent depend on the collective behavior of all agents through the mean-field state, i.e., the distribution of the states of all agents. As the agents are homogencous and interchangeable, one can focus on a single agent representative of the population. Letr: S x A x A(S) + [0, Rmax] be the (bounded) reward function and P: S x time f, the representative agent is in state St E S, and the probability distribution of st, denoted by C, E (SS), corresponds to the mean-field state. Upon taking an action a, E A, the agent receives reward r(st, at, Lt) and transitions to a new state 81+1 P((|st,, de f.). A Markovian policy for the agent is a function æ. + ((A) that maps her own state to a distribution over actions i.e., T m(a ()) is the probability of taking action in state s. Let I1 be the set of all Markovian policies.
ASS) + A(S) be the state transition kernel. At each
In general, the policy may be a function of the mean-field state Le as well. We have suppressed this dependency since our ultimate goal is to find a stationary equilibrium, under which the mean-field state remains fixed over time. See Guo et al. (2019) Saldi al. (2018h) for similar treatment.
3

---

Under review as a conference paper at ICLR 2021
When an agent is operating under policy II and the mean-fiell population flow is L := (Cr)e2o, we define the expected cumulative discounted reward (or value function) of this agent as
V () = = E[- 7'r(ss 4x2 Lx) 80 =]]
where at ~ (T))s)), S1+1 ~ P(-|st, a,, Ct). and y E (0,1) is the discount factor. The goal of this agent is to find a policy that maximizes VT L) while interacting with the mean-field L.
We are interested finding a stationary (time- (nmeeddndee)ddntt) Nash Equilibrium (NE) of the game, which is populeyy-p pair (x* L² x ((S) satisfying the following two properties:
(Agent rationality) V= (s. ()) 2 (" (),, V' II, 8 E S.
(Population consistency) L L", Vt under policy x² with initial hean-field state Lo L-
That is, x² is the optimal policy under the mean-field L, and 2 remains fixed under π². We
formalize the notion of NE in Section 2.3 after introducing more general setting of MFG.
2.2 MEAN EMBEDDING OF MEAN-FIELD STATES
Note that the mean-field state L is a distribution over the states. When the state space is con- tinuous, the NE (x" (*) is an infinite dimensional object, posing challenges for learning the NE. To overcome this challenge, we make use of succinet representation of the mean-field via mean embedding, which embeds the mean-field states into a reproducing kernel Hilbert space (RKHS) (moola et al. 2007 Gretton et al. 2008 Srriperumbudur et al., 2010). Specifically, given a positive definite kernel k: S X + R, let H. be the associated RKHS endowed with the inner product (: ( and norm 11-11x-- For each L E (S)) its mean embedding Pec H is defined
(s) == Ex~e s)(x,))], E.
Let M : Ce S H the set of all possible mean embeddings. Note that when is the identity kernel, we have μ L and M = A(S). On the other hand, when k is more structured (e.g., with a fast decaying eigen spectrum), M has significantly lower complexity than the set (SS) of raw mean-field states.
We assume that the MFG respects the mean embedding structure, in the sense that the reward r x x M + 10, Rmaa] and transition kernel P 8 x A M + (S)) (with a slight abuse of notation) depend on the mean-field state L through its mean embedding representation Mg. In particular, at each time with state s, and mean-fiee faend state Li, the representative agent takes action a₂ ~ T(-)s;), receives reward r(s,, at ) and then transitions to a new state 8-41 ~ P(-Ist, az, (c.). The NE of the game is defined analogously. As mentioned, when k is the identity kernel, the above setting reduces to the standard setting in Section 2.1 with raw-mean field states.
We impose standard regularity condition the kernel k.
Assumption 1. The kernel k is bounded and universal, in the sense that k(s, 1 E S and the corresponding RKHS H is dense w.r.t the Log norm the space of continuous functions on
Assumption T is standard in the kernel learning literature (Caponnetto & De Vito 2007 Muandet
et al. 2012 Szabó et al. 2015 Lin et al. 2017). When the kernel is bounded, the embedding of each L E A (S) satisties | 11 S &Janc [K(x, J1l dr 1. When uses universal kernel (e.g.,
Gaussian or Laplace kernel), the mean embedding mapping is injective and hence each embedding
a M uniquely characterizes distribution L in A(S) (Gretton et al. 2008 2012).
2.3 ENTROPY REGULARIZATION
To ensure the uniqueness of the NE and achieve fast algorithmic convergence, we use an entropy regularization approach (Cen et al. 2020 Shani et al., (2019) Nachum al. (007). which augments the standard expected reward objective with an entropy term of the policy. In particular, we define the entropy-regularives value function as
V.A. (s) Ea
In ae 1)) A ((g
where the parameter À > O controls the regularization level and μ is the mean-embedding of some given mean-field state (fixed over time). Equivalently, one may view V.A. as the usual value function
4

---

Under review as a conference paper at ICLR 2021
of π with entropy-regularized reward (s, a) == r(s, - Alogs((als)
Ys E A.
(1)
Also define the Q-function of a policy и as
Q (s, a) - r(s, a ()) + yB [V) (81) so = 3, =a]
(2)
which is related to the value function as
VA (s) (-1ls))) [Q,
Alg = (Q, ). (-16)) + H (=(1ss))
where HI (T((1s)) == E. π (a|s) log I(aas) is the Shannon entropy of the distribution क (-1ss). Since the reward function r is assumed to moauddodnded, it easy to show that the Q-function also bounded as Q I Qmax == (Rmax + 7- log [A))/(1 7); see Lemma
Single-Agent MDP When the mean-field state and its mean-embedding remain fixed over time, i.c. C. = L and Mc. = Vt, representative agent aims to solve the optimization problem
max (:S))((A)
VAA
(4)
for each s S. This problem corresponds to finding the cantrop--regulare optimal policy for single-agent discounted MDP, denoted by MDP, == (S, P r(s,
that is induced by μ E MM. Let xA. be the optimal solution to the problem (4 that is, the optimal regularized policy of MDP, j.- The optimal policy is unique whenever À > U. One can thus define a mapping I : :M- - via (1)) = Th which maps each embedded mean-field state j to the optimal regularized policy T of MDP,,. μ. Let Q,*"* be the optimal regularized Q-function corresponding to the optimal policy m/
Throughout the paper, we fix state distribution Ho ASS), which will serve the initial state of our policy optimization algorithm. For each E M and a policy π : - A(A), define
(x) = Borin [VTAT(s))
(5)
as the expectation of the value function (2) of policy on the regularized MDP,,, a. We detine the discounted state visitation distribution Pi induced by a policy x on MDP, as:
(5) = (1 Σ
7P((s== =
(6)
A=0 where P(st s) is the state distribution when Su 1u and the actions chosen according to
Mean-field field Dynamics. When all agents follow the same policy r, we can define another mapping I22 : 11 X - M that describes the dynamic the embedded mean-field state. In particular, given the current embedding corresponding to some mean-field state L, the next embedded mean-field state n+ = [2( (4) is given by
2 c+((') - E(s))((a))) u)ds,
n² pcc
Note that the evolution of the mean-field depends the agents' policy in deterministic manner.
Entropy-regulariee Mean-field Nash Equilibrium (NE). With the above notations, we can formally define our notion of equilibrium.
Definition 1. stationary (time- -ndeeedndeenn entropy-regulande Nash equilibrium for the MFG is a policy- policy-population population pair (T*,,4* E 1I x M that satisfies
(agent rationality)
"' = (""),, " = T2(r",
(population consistency)
When A= 0, the above definition reduces to that of the (unregularized) NE discussed in Section 2.1 which requires x² to the unregularized optimal policy of MDP,,- For general values of X, the regularized NE (x*" "="",x") approximates the unregularized NE (Geist et al. 2019). in the sense that n is an approximate optimal policy of MDP,, μ- satisfying
max J-- (T)) JAA (T²) s Alog [A/(11 7). #Ell
5

---

Under review as a conference paper at ICLR 2021
One may further define the composite mapping A M + MM as A (p) A is contraction, the regularized NE exists and is unique (Guo et al. 2019). Moreover, the iterates {(TT, Me) given by the two-step update
=T (T) When When
Ty (1e);
Me+1 =
[2( pt))
converge to the regularized NE at linear rate. Note that the first step above requires oracle for computing the exact optimal policy x//"" In most cases, such an exact oracle is not available; various single-agent reinforcement learning algorithms have been considered for computing an approximate optimal policy, including Q-learning (Guo et al. 2019) and policy gradient methods (Guo et al.) 2020 Subramanian & Mahajan 2019). The recent work by |llie et al. (2019) considers fictitious play iterative learning scheme. We remark that their convergence guarantee requires being able to compute the approximate optimal policy an arbitrary precision with high probability.
3 FICTITIOUS PLAY ALGORITHM FOR MFG
In this section, we present fictitious play algorithm, which simultaneously estimates the policy x' and the embedded mean-fiee Sean-field state µe of the NE. As given in Algorithm II each iteration of the algorithm involves three steps: policy evaluation (line 3), policy improvement (line 4), and updating the embedded mean-field state (line 5). Below we explain each step more details.
Algorithm Mean-Embeddder Fictitious Play
1: Input: initial estimate (oo (4)) step size sequence {ar, 3:2020 mixing parameter f).
2: for Iteration / = 0, 1, ,,,...,777
do
3: (Policy evaluation step) Compute an approximate version Q S x A - [0, Qmax] of the
Q-function Qa::= of policy Ne with respect to the entropy-regullrrized MDP,,.
4: (Policy improvement step) Update the policy by
मम (-1s) x (TT((-ss)) exp (ar (s,)))
(8)
T++1 (+1s) (1 m) (-1s) +n (A/AA
(9)
5: Update the embedded mean-field state by
N++1 = (1 8:) + Br (2(
(10)
6: end for
7: Output: (TTe He)...))
Policy Evaluation. In each iteration, we first evaluate the current policy mi with respect to the regularized single-agent MDP,,. ur induced by the current mean-field estimate μ4, In particular, we compute an approximation Q of the true Q-function Q == QAA,",,, which can be done using, e.g., TD(O) or LSTD methods. Our theorem characterizes how convergence depends on the policy evaluation error in this step.
Policy Improvement. To update our policy estimate ne, first compute an intermediate policy Re-1 by a single policy improvement step: for each s E S,
*141(-1s)= = argmax {ar(Q)(s,) - Allo क, (-Is), x (-1s) n<((ls)) - DKL (+((1))][T(((Is)) }
at ((-A))EA(A)
(11)
where 0y > is the stepsize. This step corresponds to one iteration of Proximal Policy Optimization (PPO) (Schulman et al.) 2017). It can also be viewed as one mirror descent iteration, where the shifted Q-function (s, -) A log (-(sss) plays the role of the gradient. The maximizer 7 in equation (IT) can be computed in closed form as done in equation (8) in Algorithm [ We then compute the new policy TT+1 by mixing 7. with small amount of uniform distribution, as done in equation (9) "Mixing in" a uniform distribution is a standard technique to prevent the policy from approaching the boundary of the probability simplex and becoming degenerate. Doing so allows us to upper bound a quantity of the form DKL. (p || 7.+1 (-Is) (cf. Lemma which otherwise may be infinite. It also ensures that the KI. divergence satisfies Lipschitz condition (ef. Lemma

---

Under review as a conference paper at ICLR 2021
Mean-field Update. We next compute updated (embedded) mean-field state 44+1 weighted average of the current Hu and the mean-field state [2( (4) induced by the new policy T++1, namely, Mr+1 (1 3e)e4, + 3, (2 Me), where Br E (0, 1) is the stepsize. This update can be viewed as single step of the (soft) fixed point iteration for the equation μ (2(
We remark that our algorithm is similar the classical fictitious play approach for finding NEs, where each agent plays a response to the empirical average of its opponent's past behaviors. In our algorithm, the representative agent views the population of all agents collectively as an opponent. Expanding the recursion (8) and ignoring the difference between T and Te+1, we can write the policy t++1
(-+1(-Is) o exp(E: (s,
for some positive weights {w Therefore, the representative agent is playing policy that responds to the (weighted) average of all previous Q functions, which reflects the representative agent's 'entss belief on the aggregate population policy.
Also note that our algorithm only performs a single policy improvement step to compute the updated
policy *++1- It is unnecessary to compute the exact optimal policy " (Ja) under μ4e (which would require an inner loop for solving MDP,,). ). as jr is only an approximate anyway of the true NE mean-field μ². Our algorithm updates π,, and Pr simultaneously within single loop.
MAIN RESULTS
In this section, we establish the theoretical guarantees on learning the regularized NE (TT", j(') of the MFG for our fictitious play algorithm. To state our theorem, we first discuss several regularity assumptions on the MFG model. Recall the definition (6) of the discounted state visitation distribu- tion and let pa == - E A(S) be the visitation distribution induced by the NE (IT", ,("), We make use of the following distance metric between two policies म,, n' E II:
D(T, x')
Egup' (-1s) X' [-1s)
(12)
As in the classical MFG literature (Guo et al. 2020 Saldi et al. 2018b), we assume certain Lipschitz M defined in Section 2.3 The
properties for the two mappings r M II and 12 Il first assumption states that (p) is Lipschitz in the mean-embedded mean-field state with respect the RKHS norm.
Assumption 2. There exists constant d2 > such that for any p. pl E M, it holds that
D ((T(()) s di 11 -0' 1'
The second assumption states that T2 μu) is Lipschitz in each of its arguments when the other argument is fixed.
Assumption 3. There exist constants d2 >> 0, dg > O such that for any policies म, a' E II and embedded mean-field states p. μ¹ E M,, holds that [TT, --T(m',,))l) S d2 ('), [IT2(T, - -T(T,, S da 11 1/ 1
Assumptions and 3 immediately imply Lipschitzness of the composite mapping A M M, which we recall is defined as A²) = T2 (H), The proof is provided in Appendix D.I
Lemma 1. Suppose Assumptions 2 and 3 hold. Then for each p. n² E M, it holds that (M) A>()')) S (d1dz + ds) I| p'llx
We next impose an assumption the boundedness of certain concentrability coefficients. This type of assumption, standard in analysis of policy optimization algorithms (Kakade & Langford, 2002 Shani et al., 2019; Bhandari & Russo 2019 Agarwal et al. 2020), allows one define the policy optimization error in an average-cast sense with respect to appropriate distributions over the states.
Assumption 4 (Finite Concentrability Coefficients). There exist two constants Cp. Cp > such that for each μ M, it holds that
:= =uup x²
(s)/p((s) s Co and { (R -
Th (s) [0
(1)31" S CC
1/2
Pu 1p"

---

Under review as a conference paper at ICLR 2021
Finally, our last assumption stipulates that the state visitation distributions smooth with respect to the (embedded) mean-field states of the MFG. This assumption is analogous to those in the liter- ature MDP and two-player games (Fei et al., 2020; Radanovic et al. 2019), which requires the visitation distributions to be smooth with respect to the policy.
Assumption 5. There exists constant du > O, such that for any n. u. E M, it holds that
|
PM 1 11, - do ll 1l
We now state our theoretical guarantees on the convergences of the policy-population sequence T to the NE {*",,²"), For the estimates of the embedded mean-field states, it is natural to consider the distance ||| - 1| in RKHS norm. For convergence to NE policy μ², recall that μ is the optimal policy to MDP,,t μ²- and each iteration of our algorithm involves single policy improvement step to compute *++1 rather than solving MDP,,, jr, to its optimal policy Mi+1 == (14)). As such, we analyze the difference between these two policies in terms of D (TE+1, T(+1), where
{ in A
the metric D is defined in equation 12).
Also let pi
Pus Tets denote the discounted visitation
distribution induced by the optimal policy Ti+1 of MDP, JA
With the above considerations in mind,
we have the following theorem, which proved in Appendix
Theorem 1. Suppose that Assumptions
7 hold and dıd2- + d3 < and that the error in the policy
evaluation step in Algorithm 7 satiisfies
Expp (s,) (x I
Se
VI [T].
With the choice of
n=
c
TT
a4 = ca T 2/5 2/5
BI == 4/5
for some universal constants On > 0, Co > 0 and c3 > 0 in Algorithm [ the resulting policy and embedded mean-field state sequence {(T,, |4) satisfy
T
T
D(T mt) x //x (VIOET -T- + vē).
D
(13)
T
i=1
1=1
1=1
T
Σ
Mc
p
11
S
1 Vx
(VlogT (Vlo-.---1/3 + VE).
(14)
Theorem bounds the distance between n, and the optimal policy n; of MDP,,, μç- By directly mea- suring the distance between n. and the NE policy n², we can define the notion of 8-approximate NE of the game.
Definition 2. For each 8 > 0, policy-populatinn pair (T. is called 8 8-approximate (entropy- regularized) NE of the MFG if
D(T, x < 8 and ||I م 11 S
The following corollary of Theorem
D shows that after T iterations of our algorithm, the average -approximate NE.
poiiuatooplltionn pair ( Σt= Te, T Σt me) is an Ö ((r--//)-approiimanl Corollary 1. Under the assumptions of Theorem
have
D 2G T
Σ
Σ
S J (VlogT 1/5 . H
vo).
Te,
T
Vx
We prove this corollary Appendix
The above results require an Ez-error of for policy evaluation. A variety of algorithms have been shown to achieve such a guarantees, including TD(0) and LSTD (Bhandari et al. 2018).
We also remark that the foo condition on concentrability coefficient in Assumption 0 can be relaxed 1/2 Cp. under which we can establish an O(T-1/9) convergence rate; see Theorem 2 and Corollary 2 Appendix for the details.
to & condition of the form (B[Ip% (s)/p"
(s)
The subscript in of emphasizes that of only depends on the mean-ficle fanld state f at time through #ट+1
(fc)
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods markov decision processes. In Conference on Learning Theory, pp. 64 66,66, 2020.
Berkay Anahtarci, Can Deha Kariksiz, and Naci Saldi. Fitted Q-learning in mean-field games. arXiv preprint arXiv:/912. 2019a.
Berkay Anahtarci, Can Deha Kariksiz, and Naci Saldi. Value iteration algorithm for mean-field games. arXiv preprint arXiv:1909001770 2019b.
Berkay Anahtarci, Can Deha Kariksiz, and Naci Saldi. Q-learning regularized mean-field games. arXiv preprint arXiv:2003. 12155,, 2020.
Tamer Başar and Geert Jan Olsder. Dynamic noncooperative game theory. SIAM, 1998.
Mare Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforcement learning. arXiv preprint arXiv: 1000000077..8777 2017.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 1XXix:9//2006880 2019.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv:I906.011 01786, 2019.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference On Learning Theory, pp. 1691-1692, 2018.
Anup Biswas. Mean field games with ergodic cost discrete time markov processes. arXiv preprint arXiv:1510.08968, 2015.
George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-376, 1951.
Lucian Busoniu, Bart De Schutter, and Robert Babuska. Decentralized reinforcement learning con- trol of a robotic manipulator. In 2006 9th International Conference on Control, Automation, Robotics and Vision, pp. 1-6. IEEE, 2006.
Lucian Busoniu, Robert Babuska, and Bart De Schutter, A comprehensive survey of multiagent rein- forcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-17) 2008
Kris Cao, Angeliki Lazaridou, Mare Lanctot. Joel Leiboo Karl Tuyls, and Stephen Clark. Emergent communication through negotiation. arXiv preprint arXiv: 03980, 2018.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
René Carmona and François Delarue. Probabilistic Theory of Mean Field Games with Applications I-II. Springer, 2018
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.06558 2020.
Romuald Elie, Julien Pérolat, Mathieu Laurière, Matthieu Geist, and Olivier Pietquin. On the con- vergence of model free learning in mean field games. arXiv preprint arXiv: 1907.02633 2019.
Yingjie Fei, Zhuoran Yang, Zhaoran Wang, and Qiaomin Xie. Dynamic regret policy optimization in non-stationary environments, arXiv preprint 2010:2007.000448. 2020.

---

Under review as a conference paper at ICLR 2021
Zuyue Fu, Zhuoran Yang, Yongxin Chen, and Zhaoran Wang. Actor-critic provably finds nash equilibria of linear- quadra-ue mean-fiet field games. arXiv preprint arX:v:1910.07498, 2019.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision
processes. In JCML 2019-Thirt International Conference on Machine Learning, 2019.
Diogo Gomes, Joana Mohr, and Rafael Rigao Souza. Discrete time, finite state space mean field games. Journal de mathématiques pures et appliquées, 93(3):308-322 2010.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola.
A kernel method for the two-sample problem. Journal of Machine Learning Research, 1:1-10, 2008.
Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Olivier Guéant, Jean-Michel Lasry, and Pierre-Louis Lions. Mean field games and applications. In lectures on mathematical finance 2010, pp. 205-266. Springer, 2011.
Xin Guo, Anran Hu, Renyuan Xu, and Junzi Zhang. Learning mean-field games. In Advances in Neural Information Processing Systems, pp. 4967-4977, 2019.
Xin Guo, Anran Hu, Renyuan Xu, and Junzi Zhang. A general framework for learning mean-field games. arXiv preprint arXiv:2003.0660 000669 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint 1rXivv1801.01220, 2018.
Pablo Hemandez-Lead Bilal Kartal, and Matthew E Taylor. Is multiagent deep reinforcement learn- ing the answer the question? brief survey. learning, 21:22.
Pablo Hemandez-Leaa, Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. A sur- vey of learning in multiagent environments: Dealing with con-stationarity. arXiv preprint 1707.09 2017.
Minyi Huang, Peter Caines, and Roland P Malhamé. Individual and mass behaviour in large pop- ulation stochastic wireless power control problems: centralized and nash equilibrium solutions. In 42nd IEEE International Conference on Decision and Control (IEEE Cat. No. 03CH37475), volume 1, pp. 98-103. IEEE, 2003.
Minyi Huang, Peter E Caines, and Roland P Malhamé. Large-population cost-coupled LQG prob- lems with nonuniform agents: individual-mann behavior and decentralized e-Nash equilibria. IEEE Transactions Automatic Control, 52(9):1560-1571 2007.
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, DJ Strouse, Joel Z Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference on Machine Learning, pp. 1049-3049. PMLR, 2019.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, volume 2, pp. 267-274, 2002.
Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pp. 1008-1014, 2000.
Lior Kuyer, Shimon Whiteson, Bram Bakker, and Nikos Vlassis. Multiagent reinforcement learning for urban traffic control using coordination graphs. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 656-671. Springer, 2008
Cean-Miched Lasry and Pierre-Louis Lions. Jeux champ moyen. i-le cas stationnaire. Comptes Rendus Mathématique, 343(9):619--22 2006a.
10

---

Under review as a conference paper at ICLR 2021
Jean-Michel Lasry and Pierre-Louis Lions. Jeux champ moyen. hi-horizon fini et contrôle optimal. Comptes Rendus Mathématique, 343(10):679-66) 684, 2006b.
Jean-Michel Lasry and Pierre-Louis Lions. Mean field games. Japanese journal of mathematics, (1):229-260, 2007.
Joel Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmas. arXiv preprint arXiv:/702.03033) 2017.
David L Leottau, Javier Ruiz-del Solar, and Robert Babuška. Decentralized reinforcement learning of robot behaviors. Artificial Intelligence, 256:130-1550 130-159, 2018.
Shao-Bo Bo Lin, Xin Guo, and Ding-Xuan Zhou. Distributed learning with regularized least squares. The Journal of Machine Learning Research, 18(1):3202-3233) 2017.
Patrick Mannion, Jim Duggan, and Enda Howley. An experimental review of reinforcement learning algorithms for adaptive traffic signal control. In Autonomic road transport support systems, pp- 47-66. Springer, 2016.
Kevin R McKee, Ian Gemp, Brian McWilliams, Edgar A Duéñez-Guzmáá, Edward Hughes, and Joel Z Leibo. Social diversity and social preferences in mixed-motive reinforcement learning. arXiv preprint urXiv:2002.02322) 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 ((7540):529-533 2015.
Jun Moon and Tamer Başar. Discrete-tine time lgg mean field games with unreliable communication. In 53rd IEEE Conference on Decision and Control, pp. 2697-2702. IEEE, 2014.
Krikamol Muandet, Kenji Fukumizu, Francesco Dinuzzo, and Bernhard Schölkopf. Learning from distributions via support measure machines. In Advances in neural information processing sys- tems, pp. 10-18, 2012.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9MMa)) 2008.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2775-2785 2017.
John F Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(1):48-4)))) 49, 1950.
Sarah Perrin, Julien Pérolat, Mathieu Laurière, Matthieu Geist, Romuald Elie, and Olivier Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. arXiv preprint arXiv:2007.03458, 2020.
Goran Radanovic, Rati Devidze, David C Parkes, and Adish Singla. Learning to collaborate in markov decision processes. arXiv preprint 1rXiv:1901.0802, 2019.
Naci Saldi, Tamer Basar, and Maxim Raginsky. Discrete-time risk-sensitive mean-field games. arXiv preprint arXiv:
2018a.
Naci Saldi, Tamer Basar, and Maxim Raginsky. Markov-nash equilibria in mean-field games with discounted cost. SIAM Journal on Control and Optimization, (26)))4256-287,200 2018b.
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 2019.
Julian Schrittwieser, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with leamed model. arXiv preprint arXiv: 1.02265, 2019.
11

---

Under review as a conference paper at ICLR 2021
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.064477 2017.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. arXiv preprint vrXiv:1909.022 2019.
Yoav Shoham, Rob Powers, and Trond Grenager. If multi-agent learning is the answer, what the question? Artificial intelligence, 171(7):3653777, 2007.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panncershelvam, and Marc Lanctot, Master- ing the game of Go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, and Adrian Bolton. Mastering the game of Go without human knowledge. Nature, 550(7676):354-35,, 2017.
Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory, pp. 13-31. Springer, 2007.
Ekhlas Sonu, Yingke Chen, and Prashant Doshi. Decision-theoretic planning under anonymity in agent populations. Journal of Artificial Intelligence Research. 59:725-770, 2017.
Bharath K Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert RG Lanckriet. Hilbert space embeddings and metrics probability measures. The Journal of Ma- chine Learning Research, 11:1517-1561, 2010.
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-259, 2019.
Richard S Sutton and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
Zoltán Szabó, Arthur Gretton, Barnabás Póczos, and Bharath Sriperumbudur. Two-stage sampled learning theory on distributions. In Artificial Intelligence and Statistics, pp. 948-957, 2015.
Hamidou Tembine and Minyi Huang. Mean field difference games: Mckean-vlasov dynamics. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, pp. 1006-1011. IEEE, 2011.
Muhammad Aneeq Zaman, Kaiqing Zhang, Erik Miehling, and Tamer Başar. Approximate cquilibrium computation for discrete-time linear-quadratic mean-field games. In 2020 American Control Conference (ACC), pp. 333-339. IEEE, 2020.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czameeki, Michaël Mathicu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft using multi-agent reinforcement learning. Nature, 375(7782) 2019.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-22)) 292, 1992.
Piotr Wigcek. Discrete-time ergodic mean-field games with average reward compact spaces.
Dynamic Games and Applications, 10(1):222-256, 2020.
Michael Wooldridge. An introduction to multiagent systems. John Wiley & Sons, 2009.
Erfu Yang and Dongbing Gu. Multiagent reinforcement learning for multi-robot systems: A survey. Technical Report CSM 04, 2004.
Kaiqing Zhang, Zhuoran Yang. and Tamer Bayar. Multi-agent reinforcement learning: A selective overview of theories and algorithms, arXiv preprint arXiv: /XX1::99/1.1063: 2019.
12

---

Under review as a conference paper at ICLR 2021
Appendices
A TECHNICAL LEMMAS
Lemma 2. Let p" and p E A(A) and p 1)pp 11 TTAT Then
|
DKL (p' S log
"
DKL (v'1l0) - DKL (p' S 21.
Proof. By definition we have
(a(a)
DKL (p'1l0) Σ p (a)a)
log
M(a)
aeA
p² (a) (1 n)p(a) + 1
Σ (a) log
Σ acA
p (a) log
0+ A
|AI
log
1
thereby proving the first inequality.
Note that
p(a)
DKL (p" (p) DKI. (p"llp) Σ (a(a log
(15)
p(a)
aeAA
If p(0) P(a) < 1 for all a E A then have
DEL (p'11)) (1)) - DKL (p'llp) 00
otherwise, there exists a' such that p(a') p(aa) and we have
p(a')
p(a')
log
log
p(a')
(1 n)p(aa) + 7/ A
p(a')
log
m)p((")
$ 1-
I 217,
where the third step follows from the fact that log(z) S x - for all x > 0 and the last step holds as
7 E [0, z.. Therefore, we have log the proof.
p(a") pla
I 2m. Applying Holder's inequality to (15) completes
Lemma 3. Let Letx,y x, and z E A(A). Ifx(a) 2 ai, v(a) 2 ai and =(a) for all A, then
(xl(()12) (ull)) < x<1 log log min {ai, a2}
1
|| - vll.
Proof.
Under the lower bound assumption of the lemma, we have (xl1( log
x(a) x(a)
< 1 + log
dr((a)
ag
and
dDKL(x(12) dx(a)
< - log a1
13

---

Under review as a conference paper at ICLR 2021
It follows that
(xllz)
max 1 log 1 -1 log 01
} s 11+ log
(x(a)
02
min {ai, a2)
20
Hence the function + DRL (x]l)) is Lipschitz w.r.t. ||-11,, the dual norm of 1m
B PROOF OF THEOREM 1
In order to obtain an upper bound on the optimality gap
o/ || /
(16)
where 1 is the embedded mean-field state of the entropy regularized NE, we also need to estimate the gap between TT.11 and the optimal solution the entropy regularized MDP,, yr We define
o++1 == Es-ni [RLL.
(17)
to quantify the convergence of policy sequence.
Before proceeding, we establish the following properties of entropy regularized MDPs, which are central to the convergence analysis.
Properties of Regularized MDP. The following lemma quantifies the performance difference between two policies for a regularized MDP measured terms the expected total reward through the Q-function and their KL-divergence. The proof is provided in Appendix D.2
Lemma 4 (Performance Difference). For each μ E M and policies æ S + (AA), it holds that
(2') (T) B Bampp' [DKL. ( (T(()1)[[=(((=)))
1-7 B Ba ((,).(ss)) Alog (-1s). N' (-(ss - π (-1s))]
(18)
where P is the discounted state visitation distribution induced by the policy x' on MDP,
We can characterize the optimal policy T/ in terms of the optimal Q-function QA*** as a Boltzmann distribution of the form Cen al. (2020); Nachum al. (2017)
Q (8,a)
(als) exp
(19)
For the setting where the reward function is bounded, we then can obtain lower bound on nh as stated in the following lemma. The proof is provided Appendix D.3 Lemma
5. Suppose that there exists a constant Rmax > O such that 7s, as, we have
Rmax. For each μ E M, and each policy S A(A),
1 S Qmax := Rmax + >>loog IA
1 1-y
Also, the optimal policy ah for the regularized MDP, satisfies
T (als)) Aauax [ AAl
Vs S.EEA
Convergence Analysis. We now move to the convergence analysis. For clarity of exposition, we use E.p || n' E. [DRL (T]] shorthand for Egep [DKL. =1(s))[=((+1s))) We recall that the step sizes chosen as
[ as shorthand for Eyyp [[|)(-(() (()(s))ll]) where E ASS); we also use
at = a C. T 2/5
B = =ceT c/T5 4/5
where the parameters ca and Cj satisfy that:
T 1,
4/57 1.
(20)
Here d = di d2 dg > O, where di appears in Assumption 2 and de, d3 appear in Assumption
14

---

Under review as a conference paper at ICLR 2021
Step 1: Convergence of Policy. To analyze the convergence of the optimality gap " g+ = l11411 - 1*ll we first characterize the convergence behavior of the policy se- quence {mT)20- In particular, we establish a recursive relationship between of
Ex-p; [DRL. (1)] and of as stated in the following lemma. The proof is pro-
vided in Section B.I
Lemma 6. Under the setting Theorem / for each 2 1, we have
do lo log A + nCpd1) ) Il - Mell + + + Q
of S (1-dav)) + (1- )ar) (1-Dar)
aj + 2n,
2
(21)
where: K = I log IAI 2R X(1-7)
"
Recall that ftr (1 Be- 1144 1 + 3 [2 14 11). Under Assumption [ we have
|| Mel1 B2-1 M1 (eTe: 23,-1-
(22)
Lemma 6 implies that
$ (1 - Aa,)o + (1 111-a0m Aia)) + 2Ea, + P a; + 27,
(23)
2
where we define
|Al
C1 = do log
nCpdi)
n
With ag = a 3r = B, from Equation 23 we have that
o Aa
(ot - ) + Aa
1
-
1) C1S+
23 A
Q
a
+
27
(24)
2X
λa
Summing over l 0.2,....
- on both sides of 24 and dividing by gives
1
T
(0th -oo) +
(1 (1-11)
C1
C
2e
Q max
21
T
Tha
Aa
2
Aa
T1B
2:
211
0 n + λa
+ X
a Xa
(25)
Tha
2X
When choosing a Therefore, we obtain
OTT-4/5
4/5)
and 17 ((T-1), we have C1
Olog T))
T-1 Σ
log T 2e
of
+
(26)
T t=0
X/2/5
x
If we let T be random number sampled uniformly from (1...., T}, then the above equation can be written equivalently as
log T
2s X
ET
[o S
+
(27)
272
Step 2: Convergence of Mean-field Embedding. We now proceed to characterize the optimality
gap for the embedded mean-field state. We obtain the following upper bound on the optimality gap F =
|| 1¹ H- The proof is provided in Section B.2
Lemma 7. Under the setting of Theorem 7 for each 2 we have
6 (1 3,d) of d2 D.V.
where d= did2 - d3 > 0.
Lemma 7 implies that
d2C, p
02 < d3,
(0' o411 +
V Vo
i+1
(28)
15

---

Under review as a conference paper at ICLR 2021
With 8, = = OOTTT--40 4/5), averaging equation
28 over iteration f = o...., T 1, we obtain
C2C
(o
T
d3T
dT
0
drC,
T-1
0
d3T
dT
1=0
d2C,
T
<
++1
13T
d
T f=
where the last inequality follows from Cauchy-Schin Sauchy-Schwarz inequality. From Eq. (2).. we have
T
--1
0
1/5 T-11/
p
T
+
d2Cp p
log T XT2/5
+
2
T
P
d
d
t=0
logT
2
X72/5 +
Vlog
T
+
VE
VA
T1/5
This equation, together with Jensen's 's inequality, proves equation (4) in Theorem
Turning to equation
[13 in Theorem
we have
D (T,, m.) ET DD (T]
t=1
EyBeup ||] (+(s)) - [T(+)s)]]]]]
1² (s)
|+s((|s)) x (11a)11
pi (s)
ET ETESppi
p² (s)
12
E EeyEerp [1m7(-10) - क (-1s)][]]
(T-1(s)
(1
ET 12DKL (17((19)](TT(((11)
C.. 2ET [oT]]
v vlog T T1/5
VO)
where step (i) follows from Cauchy-Schward inequality, step (di) follows from Assumption 4 and Pinsker's inequality, and step (tii follows from the bound in equation (27). The above equation, together with Jensen's 's inequality, proves equation (T3). We have completed the proof of Theorem]
B.1
PROOF OF LEMMA 6
The following lemma characterizes this policy improvement step. The proof is provided in Section D.4
Lemma 8. For any distributions p" .p E A(A) state 8 and function G S A + RR it holds por E A(A) with p-) x p(-) exp [aG(ss -) that
DKL (p')lp') < DKL (p" lIp) (G(s,-).p' p) a [|G(s, 113 /2.
Recall that
*111(11s) & TT (-1s)) exp a (Q) (( (
16

---

Under review as a conference paper at ICLR 2021
Lemma 8 implies that for each S, we have
DeL (T441 (+))
DRe (+(41())))]((((((())) - az (2)(s,)) - ()) (121(11) ne(-10) + || až/2
-DEL (1)41()))))
(s, Alog Te (-1s), m (11) - me((1s))
- =21 (11s) - - mT((1s) + |0:11 02/2
+ + (.)
<DEL (1))((( a (s, Al
Te (-1)) -h (11) =<(+1s))
+ Qi - (3. + 0 2 02//2.
Recall that (141(118) = () + - Ma1 Lemma 2 implies that
DKL (1444(1)))/
< <KIL. (1)4 + 2n.
(29)
DKI. (#)+1(1)))(m<(({}}) a (s, (log)(()s), te(ls))
(s)-)) (7 ) + +1@0 a2/2+2n
+ 2or
(30)
Y((a)
Taking expectation over PË both sides of (30) yields
Epp DKL (14
<Bp; [DRL. (Tt4 [[=]]] a.Egspp ((,)(s - A log TH (-(5)), a (-18) ne(-15)}] + Exmpi [Yr(s)]
(a) Ept [DRL (Té [|]]] - (1 7)ac [J (Ti+1) - Jmn (Tre] Nxd [DKL. (Té+il[=e)] + Esnpt [Y{(s)]
(1 Epp DRL [[=a]] Rupp [Yr(s)]
(c)
(1 ax Ept [KL ( [T) +(1 - A1 Eee DEL (#iz (lm)) DKL (N ((Te)
+ + [V((s)]
(31)
where step (a) follows from Lemma 4 step (b) follows from the fact that JA (m²) < JA (m(+1) as
Tē-1 = (mm) is the optimal policy for the regularized MDP p and step (c) holds due to triangle inequality.
Next we bound the first and second terms on the RHS of (3) separately.
For the second term Bz: Note that πHZ1 and qē are the optimal policy for the regularized MDP,,, i. and MDP,,. au respectively. Define
Rmax + 7 |A|
T [A exp
A(1 77)
By Lemma 5 for all (s, a) E x A, we have
# (a|s) 7, and (a(ss) 2
Applying Lemma 3 yields
B2 S KEEappi
[| न.+ (+1s) pi(s) || - - (1))l)
= xRaap'
(p)(s)
S KC ||| (-|s) - -f4
Assumption 4
x.,D (1(
S SnCdd 1| -eelle
Pellx.
Assumption
(32)
17

---

Under review as a conference paper at ICLR 2021
where
1
== 1 log
min
[2| f
log |A
2
Rmax
max
log |Al + 1(1 -
1
1-7
4
[A|
2ma
log
+ X(1 ?)
1
?
n
2 Rmaxx
KL KLmax +
X(1 7)
For the first term B₁: We have
Bi = Rpp [DLL (Tt))xz)) + PRpp
- -Bpi_.) [RLL (T(l(==)]
(8) pi-1(8)
Epi_, [DEL (T/ [|m]]] + Esmp'
P" (*(s) DRL ( (TT(
(p)(s) pr-i(s)
Ep:- [DL ([]]] Eenp
KLmax:
(*(s)
(6) E DRL (Tī [e) + KLmax do l1ke - 11-1l1
(33)
where step (a) uses the fact that DKr. (xx ((s)s(((((s))) S KLmax == log 141 (cf. Lemma and step (b) follows from Assumption 5
Combining
31..
32 and 333, we have
Ppp DKi. (mi+1
Me+1)
<(1 Ap;) [DLL (TT [T]]
(1 da,)da KLmax l| - Pe-1llz0 + (1 Aa 11 - Hellz + EoNpp [Y((s)]
=(1 ) [DLL (mī² [T))
(1 )aa) (do KLmax + xCpdi) -Helll + Eanpt [Yr(s)]
(34)
Note that
2
Egsp; [Vi(s)] EarEuwpi (1.) Q2 (2)))))
0z + 21
2
Q
[1006s.) - 27
< 2ay Esnp?
+
+
2m
2
Pinex
< 2804 +
of 21z
2
where the last step holds by the assumption on the policy evaluation error and the fact that Q x A [0, Qmax] satisfies @ S Qmax by definition. Combining the last two display
equations proves the lemma.
18

---

Under review as a conference paper at ICLR 2021
B.2 PROOF OF LEMMA
Proof. According to the update rule 10 for the embedded mean-field state, we have
||++1 p= llx
= =I(1 -Br)me + (.T2(Fe+1, 1l
||(1 31) (re -1²) + Be (T2 (TT))), me) -²) Be [T2 (TT me) - 1
S(1 3e) 11/e - -2) + 3 IT's (TT ([(((e)),{)) Me) 1m
+ Be B1l2112 (IT(u), mz) 12 Me) 11
① (1 3e) 1i4e - 1 1l + 3e [2 (mT) me) - (FA(H"),
+ 8 [2 (TT()). - ( 1e)
(35)
(6)
where the equality (i) follows from the fact that p= 22 (TM())) Lemma implies that A(p) 22 (T)()), did2 + d3 Lipschitz. follows that
(a) S (did2 + da) like 1*l
(36)
By Assumption B have
(b) dzD (14)),
(37)
Combining Eqs. 35 37 yields
||-1 1l 5 (1 - B,d) -ike μ 11 + d23.D (TT(H)) T+)))
(38)
where à = 1 dz d2
d3 > 0.
Let us bound the second RHS term above. By the definition of policy distance in equation have
[2
D (IT(H)) T(41) = Ep- [[] - m411/a]]
Eerpp
( ++t2(11s)11]]
(s()
Egwpi
(s) [| (+2((1))])))
(s) 27
1/2
Raspp
BBspp || (116) met (16)))
(+)
I Cpy v Banp; [DKL (1)6((())(((22((ss)
(39)
where the first inequality holds due to Cauchy-Schward inequality, the last inequality follows from Assumption and Pinsker's inequality.
Combining
38
39
gives
|| n 1x (1 3,d) lime 1² 11 d23,7 /BNop [DLL (19=1(()
This completes the proof.
C PROOF OF COROLLARY
Proof. Note that for each E [T'], we have
D(T,, x²) < D (TT, mt) + D (m
D (Te, mt) D (F)()))
< D (TT, m,) di 1|me p I1x
19

---

Under review as a conference paper at ICLR 2021
where the last step follows from Assumption
2
on the Lipschitzness of rÿ. It follows that
D
Te
x²*
H4
1
T
T
H
T
T
D (Te, π
+)+ +
11 - 11" 11
T
T
T
1
T
D (Te, mx) + d1 life - 1² (1 T
like - 1² 11
log T T1/5 V=
where in the last step we apply the bounds
13) and 14 in Theorem |
D ADDITIONAL PROOFS
D.1 PROOF OF LEMMA I
Proof. By the definition of A, we have
[A) - (1))l
[T (T) I2 (TA(')) u²) ll
$ TT (T) /1) -I2 (Ti()'), ()) Ix + [[ (TT())))) - r2 (T) p')l
triangle inequality
SdgD (M), (1))) + ds || 1l11
Assumption 3
<dide 11I μ² 11x + d3 || r 1l
Assumption
which proves the lemma.
D.2 PROOF OF LEMMA 4
Proof. By the definition of V. in we have
V (s)
8
= E,, wet ((
A. (V)++ (s)) 1 1800 =
Aan (s, + >V> (8++1) (se) 80
+ V2 (8).
(40)
Recall that the Q-function Qha"" of a policy æ for the regularized MDP, p. is related to V.A.x as # (A)((s) Eanx(e) (Q) (s,a) Alog ( [a]ss) (s. (s.-) + (I((5()))
vs
(,,(s, = r(s, 11) + (E [V] (s:)] a(s,a)E5 SSx A.
We have
(Q (s, ),, (11s) Eaw)'() (s)
E Es)n((s (s) (r(s, a, 1) + BBs (s))))))))
p (s,0 (s, + +7V/ (s1) Alog T (als)
(s)ss
p/x5 (s, +1// (s1) AH (=((ss))
(s)
20

---

Under review as a conference paper at ICLR 2021
Therefore,
-(-ss) = (1).e ( (s,0, + (V AHI (x'(ss))))) (s) AH (=((1s)
Bawn (s), p (s,a, >V (s) -x - H (T(
(41)
Plugging into (40) we have
V (s) ViA (s)
E Ba / (tt))
(0 (st, (st, (.(()) x-1ss)) so
1=
x (H (T (-1ss) H (T((+s.))
80 =
(42)
1=0
Recall the definition of (T) in 5). Taking expectation with respect Vo on both sides of yields
JA(T') - (T)
(Q (s (+1ss) - x(-1ss))
1=0
+ E (00
7 (H (T (-1s)) - - (T(-ss))))
Sappy' (Q (8, )) ) (-1s) --(ss))) + X (H (#(())) - (
(43)
For the entropy term in 43 we have
E B
[ (T'' (-1s)) - I (x(+1s))
log T' (-(1s) ' (-1s) - log (-|s)) aT(1ss) }
E 2'
log (-1s) - log 2 2'(15)
x xx(11s) - (1088 ((1s)) (T(11))
=Bsupg'
π (.11))
=B p
log (-|s)) म (-|s) x(-1s) DKL (N' (+(((1s)
(44)
Taking 44 into (43
yields the desired equation in Lemma
D.3 PROOF OF LEMMA 5
Proof. Note that the value function VA, can be written as
V (s) E
(st,
By the definition of A. in we have Er (se, ar)] S Rmax + Alog |A]. Therefore,
(se,
Ruax Alog LA|
0 s VV
EsES,
and
Rmax + A Alog [A]
Rmax + >A |A|
0 < (8, S Rmax +
V
1 1-
1
21

---

Under review as a conference paper at ICLR 2021
For the second inequality, we have
exp
T (als)
EDEA exp (Q (s.b)/A)
EbEa exp (9max/
e / |A|
claimed.
D.4
PROOF OF LEMMA 8
Proof. For any function g A - and distribution E ((A). let 2 : A + be a constant function defined by
z(a) log Σ p(a') exp (xp(aggaa)))
a'EA
Note that for any distributions p², pp' E (2)) - -p') -0)=0, =0. Since
p-(-) p(.) exp (ag(-)),
we have ag(()) = x(()) + (og(((())/p() Hence
a (g.1"" - p²) = (z 1=+1og(1) /p),1' -p')
=2.pp" pp) + (log(p" /p).p") + (log(n' /p" "p'))") + (log(r//D): -p')
DKL (p"llp) DKL (0" 10')p' DKL (p' Ip).
Therefore, for each state E S, we have
- p) = a (G(s, ),v - 1/) + a (G((, -p)
= DKL. (v" [lp) - DRL. (p"lle') - DKI. (D'llp) + a (G(s p}
I DKL (p'1lp [[ppp DEL (p*llp') DKL (p'llp) a )1 -1pp 11p-p'll p'l11
Rearranging terms yields
DKL (p"llp') < DKL (p"llp) a (G(s, ),p" - p) - DRL (v'lp) +a [[((s, )1l 11p p'1l1 (45)
Meanwhile, by Pinsker's inequality, it holds that
DKL (p'llp) 2 1|p p/1??/12
(46)
By combining 45 and (4)) we obtain
DKL (p" Ilp') S DKL (p" (lp) (G(s, ',p" p) 11-11p- /2 + | - 1/11,
s DKL (p" [lp) (G(s, ",p² p) + a² [[((ss 11 /2,
which concludes the proof.
E A WEAKER ASSUMPTION ON CONCENTRABILITY
In this section, consider weaker assumption on concentrability, under which Algorithm | learns a pplicy-population pair that is -appooiimapo NE after T itterations.
We consider the following distance metric between two policies म. e'''el II:
W W(T, m')
V Eanp-
[|<((ls) T' (+(1s)
(47)
Similarly before, assume certain Lipschitz properties for the two mappings I' M - II and T2: : II x M + M defined in Section [.3) particular, we impose the following two assumtpions, both stated in terms of the distance metric ((:-)) defined in (47) above.
Assumption 6. There exists constant d1 > such that for any p., pl M, it holds that
W (T)GH, di ||I 1 12
22

---

Under review as a conference paper at ICLR 2021
Assumption 7. There exist constants d2 0, d3 0 such that for any policies n, r' II and embedded mean-field states p. E M, it holds that
[ (T, p1) ( p)) 2 S d2W (F, n²)
[ (1) [T 11 S d3 |p 11
Assumptions 6 and 7 immediately imply Lipschitzness of the composite mapping A M - M, which we recall is defined as A (²) T (1),
Lemma 9, Suppose Assumptions
0 and 7 hold. Then for each μ² E M, it holds that (M) - (A())))) & (d1d2 + d3) ll p wll
We also consider the following relaxed, f2-type assumption on the concentrability coefficients.
Assumption 8 (Finite Concentrability Coefficients). There exist two constants Cp. Cp > such that for each E M, it holds that
1/2
1/2
The PH (8)
(s())
E eoupp
CCp
and
E
S Cp.
(s)
eoupp"
Te Pk
(s)
We establish the following convergence result for Algorithm
Theorem 2. Suppose that Assumptions 5 in the policy evaluation step in Al Algorithm Saaihhmmmaaattaa safisfies
hold and djd2 dg < 1 and that the error
Ex-pp
(ss,
||]]
EE ee
With the choice of
n= CoT
= c. 4/9
31 = 3 3
8/
8/9
for some universal constants On > 0, Ca > 0 and cg > 0 in Algorithm [ the resulting policy and embedded mean-field state sequence ((Te, ) satisfy
T
(log
At.
M
Tt
W (Te, m;) 174
T
+
+t1/4)
(48)
1=1
t=1
T
T
(logT))/4
like 4² 4²1lx 2 1/4
+ +s1/1)
(49)
T1/9
t=1
The following corollary of Theorem shows that after iterations of our algorithm, the average policy-population pair ET Ne, Ei mz) is Ö (T 1/9) -aproximate NE.
Corollary 2. Under the assumptions of Theorem
we have
1
1') 1/4 + 51/4 e4/A)
W
Σ
T2, T²
+
M4 w¹
S
T
T
1/4
T1/9
E. PROOFS OF THEOREM AND COROLLARY
The proof follows similar lines as those of Theorem and Corollary I with all appearances of the distance D replaced by the new distance W. Below only point out the modifications needed.
Lemma remains valid as stated. For the proof of this lemma, the only different step is bounding the term B2 in equation (3Tp. In partieular, the bounds in equation 32) should be replaced by the
23

---

Under review as a conference paper at ICLR 2021
following:
B2 S KEsspp
(-1s) -
pi(s)
xBsup
(1m)(( m (+15)]1
(*(s)
[ (p2((5) 27
$ R, Bowp'
Bsspp' [||
ob+ (-1s)
S xCp: V /Bsmpr
|| - m - (-1)(1
Assumption
wC,W (T((4))),
S xC || - Mell
Assumption
(50)
Lemma 7 should be replaced by the following lemma.
Lemma 10. Under the setting of Theorem 2 for each 2 0, we have
(1 - Bed) of + d2y (o
where à 1 d1d2- d3 0.
The proof of Lemma 10 similar to that of Lemma 7 The only different step the term
D (He),), Te+1) in equation (38) should be replaced by W (F)(e), re+1). which can be bounded as follows:
w ((())))+4a))
V
Essp'
|| mpp (+|s) (++1(+1s)]1
(s)
( - Te+ (1=))1
Eompi
(8)
1/4
(s)
BaNp;
Eenpt (1)+) - +++1(115)11
(s)
EEswe || (-1s) Te {()) 1/4
273
Cp
C (Esppt [DE
1/4
(51)
where step (i) holds by Assumption 8 and the fact that ||v w/1l1 < 2, Vu, v E A(A). and step (it)
follows Pinsker's inequality.
We now turn to the proof of Theorem
We first establish the convergence for of by following the exactly same steps from equation 21 up
to equation 25
We restate the bound on T Ei= of in (5) as follows:
T
1
C13
2s
+ D
27
00 +
+
a +
(52)
T
Tha
Aa
X
2 λa
t=0
When choosing a OTTT119)) 3 Therefore, we obtain
O -899)
and n
OT ) have C1
O(og T))
log T
2s
Σ oz
+
(53)
T
4/9
X
t=
If we let be random number sampled uniformly from (1...., T}, then the above equation can be written equivalently as
log T
25 X
ET |
S
+
(54)
4/
24

---

Under review as a conference paper at ICLR 2021
We now proceed to bound the average embedded mean-field state 1/2 Et= of. Lemma 10 implies
de
o - 23, (0 -/tt))
(o=+1)
(55)
d
With B, === 8/9), averaging equation 55 over iteration 0, ....,.. T 1, we obtain
T
d2y
T-1
+
0f
(0
o%²o
00 1 1/4
d3T
dT
01
d2p
C,
(o 1/4
d3T
dT
(
00
d2 /o
T
+
I+1
J5T
t=0
(1)
d2 duyT,,
( T-1
1/4
+
++1
23T
d
T
1=0
where steps (i) and (ii) follow from Sauchy-Schward inequality.
From equation
we have
lavo, C logT
0
d2 1/9
2:
1/4
T-9
T
d
d
XT'4/9
1=0
log'T T
2e
1/1
24
XT1/9
A
(T
+
1/1
X1/4
T1/9
This equation, together with Jensen's inequality, proves equation (49p in Theorem Turning to equation
488 in Theorem we have
T
W (T,, x,) = ET [W (TT, T)]
T
ET V Bawp'
|1 -
T (1(s))
IV3
(s))
ET E Eamat
||+((-))) TT (1)))p
16)
(2)
(s(s) [2]
1/4
ETEa-pj
. B E. |
(s)
(1)
( ETE [|T7(-1s) - ar(1s)]1]] 1/4
5
(10)
C, (f. EETENwR (DKI. (1)()) 1/4
VT, (Er [o=]] 1/1
(log ()gg T1/9
1)1/1 +el/1)
1/4
where step (1) holds due to Jensen's inequality, step (ii) follows from
inequality,
step (iii) follows from Assumption 8 and the fact that ||v D'll, S 2, Vu, v' E A(A), step (iv)
25

---

Under review as a conference paper at ICLR 2021
comes from Pinsker's inequality, and step (e) follows from the bound in equation (54) The above
equation, together with Jensen's inequality, proves equation (48). We have completed the proof of Theorem 2
The proof of Corollary is the same as that of Corollary and is omitted here.
26


Reviews:
[{"review_id": "fKAgKFEjpgZ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nSummary:\nThe paper focuses on the computation of Nash equilibrium in a Multi agent setting, with a very large number of agents. This leads to the consideration of reinforcement leaning algorithms for mean field games (i.e. with an infinite number of agents) and obtain the convergence of a single loop fictititious play algorithm to the Nash equilibrium of entropy regularized mean field games.  \n\nStrength of the paper:\n- The connection between the derived mathematical property and the very interesting problem of interest, i.e. learning in a multi agent setting with numerous agents is well motivated.  \n- The paper is well written and technically sound. The mathematical results provided are technical, difficult and are presented in a pedagogic manner\n\nWeakness of the paper:\n- The convergence property relies on a very strong and a priori unrealistic assumption on the Lipschitz coefficients os the distribution <-> policy mappings: d_1d_2+d_3<1. Authors should justify when this assumption can indeed be satisfied and directly read on underlying Mean Field Game Structure. \n- No numerical experiments are presented to verify the convergence of the algorithm and compare it to alternative methods in the literature. \n\nRecommandation; Given the scope of the paper in comparison to the one of the ICLR conference, together with the weaknesses detailed above, I recommend to reject the paper. \n\nQuestions during the rebuttal period:\n1. Can you provide reasonable sufficient conditions on the mean field game dynamics ensuring that the assumption d_1d_2+d_3<1 is satisfied? Even though it already appeared in previous papers, it is really very strong stated as such. \n2. Can you provide numerical experiments confirming the theoretical findings of the paper?\n3. Focusing on penalized MFGs, the role of the penalization coefficient \\lambda seems to be of particular interest, and a necessity in your approach. Is the dependence of the NE (policy and or state distribution) clear with respect to \\lambda? What are the practical implications of the choice of \\lambda? \n4. How does your approach compare to the 2-time scale approach provided by Angiuli et al. (Unified Reinforcement Q-Learning for Mean Field Game and ControlProblems) in terms of single/multiple loops?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "VlgAcA-IDtI", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers a Markov mean-field game where the continuum of players is summarized by their distribution over the state space. The policy of each player is a function of the state alone (and not a function of mean-field distribution). It is assumed that the game is \"well-behaved\" so it can be embedded in a regular and bounded kernel.  It is also assumed the relevant that the composition of the relevant mappings forms a contraction mapping, along with several other technical assumptions. An algorithm that approximates the Nash equilibrium (NE) of the game is proposed, which consists of an entropy-regulated reinforcement learning step and an update of the  (embedded) mean-field state step. Based on the contraction structure, it is proved that this algorithm converges to an approximate NE with a rate (T^-1/5) for T iterations, and the approximation depends on the entropy regularization parameter and the error bound of the reinforcement learning step. \n\nThe paper is clearly written and the math is solid and well explained. The topic of the paper is likely to be interesting to a broad audience, provided that more insight and discussion are given. The main concern is with the novelty or significance of the result.\n\nSingle Loop/Double Loop - \n\ni) While I agree that a single loop is overall more elegant, this feels like some kind of an intermediate motivation for the paper. The real motivation is of course the computational complexity of the NE approximation algorithm. It is not obvious that a single loop algorithm is less complicated overall since it can take more outer iteration to converge. Providing complexity guarantees and comparing them with state of the art, or at least providing some numerical simulations for the same purpose, seems necessary to make the contribution significant. Since you do provide the convergence rate, converting that to complexity seems straightforward, isn't it?\n\nii) It is claimed that (Guo et al., 2019) and others require to solve an MDP each iteration. The abstract also implies this (\"in stark contrast...\"). Is this really the case? it looks like (Guo et al., 2019) also works with an approximate solution to the MDP, it's just that the number of RL iterations it has to do each time has a lower bound. Please discuss that in more detail, since not being clear regarding this issue makes the whole single loop advantage vague. For example, if an algorithm runs only 20 iterations of RL every outer iteration, is it really a double loop algorithm? and what if it runs 2 iterations?  if it ends up being a quantitative comparison, then one would naturally wonder how good of an epsilon (in Theorem 1) can be achieved with a \"one iteration\" approximation of Q (aren't iterations required to approximate Q?).  If it's big, and \\lambda is small, then the approximation of the NE might be poor. \n\nKernel -\n\nThe writing is a bit confusing regarding whatever this is a technique or an assumption, and I think it's more of the latter. To clarify this, please add to Assumption 1 the part that says that the game can be embedded in this kernel. Nevertheless, I do agree it is a reasonable assumption to make.\n\nEntropy Regulation - \n\nIt is not entirely clear why this regulation is crucial, and the price is convergence to an approximate NE instead of the exact one (which the abstract is misleading about). What happens if there are multiple NE? (is this even the case?) It seems reasonable to request to converge to one of them. How much faster does it make the convergence, compared to other algorithms? For example, it looks like (Guo et al., 2019) don't employ this regularization and prove that the NE is unique, so why is it needed here? why can't we choose \\lambda=0? More discussion is needed to make this design choice to look less arbitrary. \n\nReinforcement Learning and Fictitious Play  - \n\nI find the use of both names a bit misleading, at least in some contexts. \n\nRL - While the algorithm definitely calls an RL routine, the algorithm itself isn't RL in the sense that it isn't model free. It looks like the step in (10) requires knowing the transition probabilities to compute (7). This seems like a disappointing assumption. How does that compare to the literature? can this assumption be removed? Intuitively it feels like making this step \"noisy\" as well should be possible as long as the contraction structure remains. Please correct me if didn't get this part right. \n\nFictitious Play (FP) plays the *best* response to the empirical distribution of the past actions of the opponents. This isn't exactly the case here, and the title+abstract make it look like the contribution is to study the behavior of FP in a mean-field game, and not to solve a Mean-field game with an algorithm that has some resemblance to FP. \n\nContraction - stating the assumption as d1d2+d3<1 is a bit too dry. Isn't that possible just to assume that the composition in Lemma 1 is a contraction? it reads better. \n\nAssumptions - I think that providing more discussion and intuition about each of the assumptions will make the paper more interesting. What assumptions will be extremely hard to remove,  and what is more for convenience? please also mention the literature in this discussion with more detail than \"x was assumed in y\", for example, what was required in other papers that made other assumptions. A conclusion section is missing in this paper, and this could be the right place to suggest future directions that can make other researchers interested in picking up on your result and perhaps remove some of the assumptions. \n\nOrganization - the order of the lemmas in the appendix interrupts the flow of the reading. It's best to introduce a lemma and then prove it, giving some intuition about its role in the bigger picture. Alternatively, some lemmas (statement + proof) can be postponed, and the proofs that use them can say \"where (a) follows from Lemma x\". \n\nMinor Comments:\n\n\"the proposed algorithm converges to the Nash equilibrium of the MFG\"  - but the NE of the MFG (with no regularization) isn't necessarily unique. Please rephrase. \n\n\"\\mathcal{A} is finite\" this is more than a technical assumption, it means that the paper considers discrete action sets, which seems like something that should be stated more clearly. \n\nI think it's better to reverse (7), since the second equation is the mapping. \n\nSome parameters, like \\lambda, are missing from the algorithm's input, and also from the Theorem's statement. \n\nWhy does the proof of Lemma 2 need Holder's inequality at the end? looks like it's just bounded by 2\\eta? \n\nI believe that a factor of |A| is missing in \\kappa of Lemma 6. \n\n(32) - should be Assumption 2 and not Assumption (2). \n\nbelow (34) - why Q of t-1 and not t? \n\n\n\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "H2M_LI9xrKY", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers reinforcement learning (RL) for finding Nash equilibriums (NE) in general stationary mean-field games (MFG). It attempts to address the problem of designing a single-loop RL algorithm which updates the policy and the mean-field state simultaneously in each iteration while maintaining provable global convergence to NEs, which is a significant open problem in the existing literature. To this end, the authors propose a PPO-based fictitious play algorithm and show that it converges to approximate NEs at a sublinear rate. \n\nThe major contributions of this paper are listed below:\n1. Unlike the existing works in the literature, which solves the mean-field state induced RL subproblem to near optima in each iteration before moving on to the next mean-field update, the algorithm proposed in this paper only performs a single step of policy improvement and then immediately moves on to the mean-field update step. \n2. By introducing entropy regularization, the authors also makes the Lipschitz continuity of the optimal policies with respect to the mean-field states (Assumption 2) more reasonable (due to the softmax format and uniqueness of the optimal policies) than the counterparts of this assumption for unregularized MDPs in the literature. \n3. it introduces kernel mean embedding, which adds to the flexibility of the proposed framework. \n\nHowever, this paper also has several limitations and weaknesses, as listed below:\n1. The most significant issue is that in the propose algorithm (Algorithm 1), the step in line 3 requires computing an approximate evaluation of $\\hat{Q}_t^{\\lambda}$. Although the authors explain that this could be done using TD(0), LSTD and so on, all these algorithms (and in general, any RL algorithm) still require fixing the mean-field state $\\mathcal{L}_t$ while simulating through and getting samples from the MDP subproblem induced by $\\mathcal{L}_t$. In practice, the mean-field state cannot be easily fixed if one is interacting with the real-world (instead of a simulator), as when the policy is executed the mean-field gets updated immediately as well. This is the actual source of the limitations of the existing double-loop algorithms, which still cannot be avoided by the proposed algorithm in this paper. An actual single-loop algorithm should not require fixing the mean-field state. In particular, for Algorithm 1, only one update should be allowed when evaluating the $\\hat{Q}_t^{\\lambda}$ function. So the actual contribution in terms of proposing a single-loop algorithm is limited. \n2. The paper does not include the errors caused by introducing the entropy regularization term to the original problem into the final results. Although it should not be very difficult to include these errors in the final results due to the bound at the bottom of page 5 and the Lipschitz continuity assumptions made throughout the paper, the authors should formally include it and discuss about the trade-off between choosing a larger $\\lambda$ to improve the convergence rate and choosing a smaller $\\lambda$ to control the regularization error. \n3. The necessity of introduction of kernel mean embedding and the corresponding assumptions on RKHS is questionable. By embedding the original mean-field state $\\mathcal{L}_t$ as $\\mu_t$, we are still dealing with an infinite dimensional mean-field state embedding ($\\mu_t$), which does not seem to introduce any quantitative simplification (apart from the qualitative “lower complexity” claim mentioned by the authors). From the presentation of this paper, it seems that the major use of the embedding is introducing a well-defined distance inherited from the underlying RKHS. However, such tools can also be achieved by considering Wasserstein distances and TV distances for general probability measures. The authors should provide a clear explanation on why introducing the mean embedding is necessary and helpful. \n4. On a related point, in line 5 of Algorithm 1, unless $\\mathcal{M}$ is shown to be convex, the update (10) may no longer yield $\\mu_{t+1}$ in $\\mathcal{M}$, and in such a case the corresponding original mean-field state $\\mathcal{L}_{t+1}$ cannot be retrieved and hence the algorithm cannot move on (cf. (7)). The authors should explain clearly why $\\mathcal{M}$ is convex or why this is not an issue.\n5. In general, when the state space is infinite, the Q-table will also be infinite. In such a case, either function approximation or something like the nearest neighbor Q-learning [2] should be used. The authors should at least discuss about this for line 3 in Algorithm 1. \n\nFinally, some slightly more minor comments:\n1. The concentrability coefficients look different from the literature, which typically has the denominator being the initial distribution or a uniform bound on discounted state-visitation measures corresponding to arbitrary policies (see e.g., [1, Assumption 1]) instead of the optimal one (like the $\\rho^\\star$ here). The authors may want to provide some further intuition and explanations on why this is the case to help the readers gain better insights. \n2. The performance difference lemma (Lemma 4) seems to be mostly the same as Lemma 1 (Performance improvement) in Cen et al., 2020. The authors should either directly refer to Cen et al., 2020 for this result, or state clearly the difference. \n3. The authors assumed that the kernel of the RKHS satisfies that $k(s,s)\\leq 1$ for all $s\\in\\mathcal{S}$. How stringent is this assumption? Is it always achievable by some rescaling? If so, the authors may want to add a quick comment on this in the draft. \n4. In formula (3), it seems that there is a missing $\\lambda$ coefficient before the regularization term $\\mathbb{H}$.\n5. In the abstract, “by the iterates mean-field states” might better be “by the iterates of mean-field states”. \n\nIn short, this paper attempts to address an important problem in the RL for MFG literature, and made some successful contributions. However, due to the technical limitations and weaknesses mentioned above, I think the paper is still not ready for publication in ICLR in its current format. \n\n[1] Shani, Lior, Yonathan Efroni, and Shie Mannor. \"Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps.\" arXiv preprint arXiv:1909.02769 (2019).\n\n[2] Shah, Devavrat, and Qiaomin Xie. \"Q-learning with nearest neighbors.\" In Advances in Neural Information Processing Systems, pp. 3111-3121. 2018.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7OJPe7vMWNq", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper proposes a single loop reinforcement learning algorithm for stationary mean-field games. In particular, when viewing the mean-field state and the stationary policy as two players, the goal is to find a Nash equilibrium. Updating these two players alternatively via gradient-descent and proximal policy optimization, the proposed algorithm is proved to converge sublinearly to the Nash equilibrium.\n\nComment:\nThis paper is well-written as it well explains the problem setting of the mean-field game step-by-step. While existing fixed-point algorithms require to solve the MDP induced by the current mean-field state exactly, the authors propose to take the model-free RL approach which is able to handle continuous state space. Also, the single loop structure of the algorithm is often favored over the nested loop scheme in terms of the practical performance (which unfortunately is not validated through empirical study in this paper).\n\nConcern:\nMy major concern is the assumption made on the relations between three Lipschitz continuity constants in Theorem 1: To achieve the described convergence rate, the authors assume that $d_1 d_2 + d_3<1$. I do not see how such configuration would hold in general. Such an assumption significantly limits the applicability of the theory developed in the paper (which is main claim of the paper as there is no empirical study provided). ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is interesting work, but not yet sufficiently mature for publication.  Although the authors propose an novel algorithm and provide an analysis, the reviewers raised several criticisms about the comparison to previous work, the lack of any empirical evaluation, the strength and unnaturalness of the assumptions used to establish convergence.  After discussion, the reviewers remained largely unsatisfied with the author responses to these questions, and none recommended accepting this paper.
Decision: Reject