Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
Authors: Zuyue Fu
Zhuoran Yang
Yongxin Chen
Zhaoran Wang
Venue:  (2020)

Abstract: We study discrete-time mean-field Markov games with infinite numbers of agents where each agent aims to minimize its ergodic cost. We consider the setting where the agents have identical linear state transitions and quadratic cost func- tions, while the aggregated effect of the agents is captured by the population mean of their states, namely, the mean-field state. For such a game, based on the Nash certainty equivalence principle, we provide sufficient conditions for the existence and uniqueness of its Nash equilibrium. Moreover, to find the Nash equilibrium, we propose a mean-field actor-critic algorithm with linear function approxima- tion, which does not require knowing the model of dynamics. Specifically, at each iteration of our algorithm, we use the single-agent actor-critic algorithm to approximately obtain the optimal policy of the each agent given the current mean- field state, and then update the mean-field state. In particular, we prove that our algorithm converges to the Nash equilibrium at a linear rate. To the best of our knowledge, this is the first success of applying model-free reinforcement learn- ing with function approximation to discrete-time mean-field Markov games with provable non-asymptotic global convergence guarantees.

Published as a conference paper at ICLR 2020
ACTOR-CRITIC PROVABLY FINDS NASH EQUILIBRIA OF LINEAR-QUADRATIC MEAN-FIELD GAMES
Zuyue Fu
Zhuoran Yang
Northwestern University
Princeton University
zuyue fuêu. www.mnowwweweeecccmmmmm edu
zyseprinceton.co
Yongxin Chen
Zhaoran Wang
Georgia Institute of Technology Longchen&gatent edu
Northwestern University
chaoranwangggaai.n
ABSTRACT
We study discrete-time mean-field Markov games with infinite numbers of agents where each agent aims to minimize its ergodic cost. We consider the setting where the agents have identical linear state transitions and quadratic cost func- tions, while the aggregated effect of the agents is captured by the population mean of their states, namely, the mean-field state. For such game, based on the Nash certainty equivalence principle, we provide sufficient conditions for the existence and uniqueness of its Nash equilibrium. Moreover, find the Nash equilibrium, we propose a mean-field actor-critic algorithm with linear function approxima- tion, which does not require knowing the model of dynamics. Specifically, at each iteration of our algorithm, approximately obtain the optimal policy of the each agent given the current mean- field state, and then update the mean-field state. In particular, algorithm converges to the Nash equilibrium at a linear rate. To the best of our knowledge, this is the first success of applying model-free reinforcement learn- ing with function approximation to discrete-time mean-field Markov games with provable con-asymptotic global convergence guarantees.
use the single-agent actor-critic algorithm
prove that
INTRODUCTION
In reinforcement learning (RL) (Sutton and Barto 2018), an agent learns to make decisions that minimize its expected total cost through sequential interactions with the environment. Multi-agent reinforcement learning (MARL) (Shoham et al.) 2003 2007 Busoniu et al. 2008) aims to extend RL to sequential decision-male making problems involving multiple agents. In non-cooperative game, are interested the Nash equilibrium (Nash) 1951) ) which is a joint policy all the agents such that each agent cannot decrease its expected total cost unilaterally deviating from its Nash policy. The Nash equilibrium plays a critical role in understanding the social dynamics of self-interested agents [Ah 2000 Axtell 2002) and constructing the optimal policy of a particular agent via fictitious self- play (Bowling and Veloso 2000; Ganzfried and Sandholm, 2009). With the recent development in deep learning (LeCun et al. 2015), MARL with function approximation achieves tremendous empir-
2016 2017). Poker (Heinrich and Silver, 2016 Moravěík et al., 2017). Star Craft (Vinyals al. 2019). Dota (OpenAl) 2018),, autonomous
ical successes in applications, including Go (Silver et al.
driving (Shalev-Shwartz et al. 2016). multi-robotic systems (Yang and 2004)) and solving social dilemmas (de Cote al. [2066] Leibo et al.,72217 [Hughes et al.]2018)) However, since the capacity of the joint state and action spaces grows exponentially in the number of agents, such MARL ap- proaches become computationally intractable when the number of agents is large, which is common
in real-world applications (Sandholm 2010 Calderone
2017
Wang al. 2017a).
dean-field game proposed by Huang et al. 2003 2006);
Lasry and Lions 2006a 2007) with model the strategic interactions within large pop-
the idea of utilizing mean-field approximation ulation. a mean-field game, each agent has the same cost function and state transition, which depend the other agents only through their aggregated effect. As result, the optimal policy of

---

Published as a conference paper at ICLR 2020
each agent depends solely its own state and the aggregated effect of the population, and such an optimal policy is symmetric across all the agents. Moreover, if the aggregated effect of the popula- tion corresponds to the Nash equilibrium, then the optimal policy of each agent jointly constitutes Nash equilibrium. Although such a Nash equilibrium corresponds to an infinite number of agents, it well approximates the Nash equilibrium for sufficiently large number of agents (Bensoussan al.) 2016). Also, as the aggregated effect of the population abstracts away the strategic interactions be- tween individual agents, it circumvents the computational intractability of the MARL approaches that do not exploit symmetry.
However, most existing work on mean- field games focuses on characterizing the existence and uniqueness of the Nash equilibrium rather than designing provably efficient algorithms. In par- ticular, most existing work considers the continuous-time setting. which requires solving a pair of Hamilton-Jacobi-Be Jach---llaaoi--ll-maaa (HJB) and Fooker-Planck (FP) equations, whereas the discrete-time set- ting is more common in practice, e.g., in the aforementioned applications. Moreover, most existing approaches, including the ones based on solving the HJB and FP equations, require knowing the model of dynamics (Bardi and Priuli 2014), or having the access to a simulator, which generates the next state given any state-action pair and aggregated effect of the population (Guo et al. 2019), which is often unavailable in practice.
To address these challenges, develop efficient model-free RL approach to mrean-field game, which provably attains the Nash equilibrium. In particular, we focus on discrete-time mean-field games with linear state transitions and quadratic cost functions, where the aggregated effect of the population is quantified by the mean-field state. Such games capture the fundamental difficulties of general mean-field games and well approximates variety of real-world systems such as power grids (Minciardi and Sacile, (01T), swarm robots (Fang, 2014] Araki et al.] 2017] Doerr et al.) 2018). and financial systems (Zhou and Li 2000; Huang and Li (018)). In detail, based on the Nash certainty equivalence (NCE) principle (Huang et al. 2006]] 2007), we propose a mean-field actor-critic algorithm which, at each iteration, given the mean-field state 14, approximately attains the optimal policy TH of each agent, and then updates the mean-field state assuming that all the agents follow TH. We parametrize the actor and critic by linear and quadratic fuucttions, respectively, and prove that such parameterization encompasses the optimal policy of each agent. Specifically, we update the actor parameter using policy gradient (Sutton et al. (200) and natural policy gradient (Kakade) 2002 Peters and Schaal 2008 [Bhatnagar et al., 2209) and update the critic parameter using primal-dual gradient temporal difference (Sutton et al. 2209a b). In particular, we prove that given the mean-field state μr, the sequence of policies generated by the actor converges linearly the optimal policy TH Moreover, when alternatingly update the policy and mean-field state, we prove that the sequence of policies and its corresponding sequence of mean-field states converge to the unique Nash equilibrium at linear rate. Our approach can be interpreted from both "passive" and "active" perspectives: (i) Assuming that each self-interested agent employs the single-agent actor- critic algorithm, the policy of each agent converges to the unique Nash policy, which characterizes the social dynamics of a large population of model-free RL agents. (ii) For a particular agent, our approach serves as a fictitious self-play method for it to find its Nash policy, assuming the other agents give their best responses. To the best of our knowledge, our work establishes the first efficient model-free RL approach with function approximation that provably attains the Nash equilibrium of a discrete-time mean-field game. As a byproduct, we also show that the sequence of policies generated by the single-agent actor-critic algorithm converges at linear rate the optimal policy of a quaaar-q regulator (L.QR) problem in the presence of drift, which may be of independent interest.
Related Work. Mean-field game is first introduced in Huang et al.
(2003 2006 Lasry and Li-
ons (2006a b) 2007). In the last decade, there is growing interest in un understanding continuous-timg mian-field games. See, e.g.. Guéant et al.] (20TT); [ennsoussan al.) (2013): Gomes al.) (2014); Carmona and Delarue (2013) 2018) and the references therein. Due to their simple structures, continuous-time linear-quadratic mean-field games are extensively studied under various model as- sumptions. See Li and Zhang (2008): Bardi (201 Wang and Zhang 2201); : Bardi and Priuli (2014): [Hunn et al. (2016a b); Bensoussan et al. (0016) 2017); Caines and Kizilkale (2017); Huang and Huang (2017); Moon and Başar (2018); Huang and Zhou (2019) for examples of this line of work. Meanwhile, the literature on discrete-time linear-quadratic mean-field games remains rela- tively scaree. Most of this line of work focuses characterizing the existence of a Nash equi- librium and the behavior of such a Nash equilibrium when the number of agents goes to infinity
2

---

Published as a conference paper at ICLR 2020
(Gomes et al. 2010 Tembine and Huang 2011 Moon and Başar 2014 Biswas 2015 Saldi al., 2018a Sa bj 2019). See also Yang et al. (20 8a). which applies maximum entropy inverse RL (Zibaar et a 2008) to infer the cost function and social dynamies of discrete-time mean-field field games with finite state and action spaces. Our work is most related to Guo et al. (2019), where they propose mean-field Q-learning algorithm (Watkins and Dayan T992) for discrete-time mean-field games with finite state and action spaces. Such an algorithm requires the access to a simulator, which, given any state-action pair and mean-field state, oulputs the next state. In contrast, both our state and action spaces are infinite, and we do not require such simulator but only observations of trajec- tories under given mean-field state. Conrespondingly, we study the mean-field actor-critic algorithm with linear function approximation, whereas their algorithm is tailored to the tabular setting. Also, our work is closely related Mguni et al. (2018), which focuses on a more restrictive setting where the state transition does not involve the mean-field state. In such a setting, mean-field games are potential games, which is, however, not true in more general settings (Li et al., 2017 Briani and Cardaliaguet 2018). In comparison, we allow the state transition to depend on the mean- field state. Meanwhile, they propose a fictitious self-play method based on the single-agent actor-critic algo- rithm and establishes its asymptotic convergence. However, their proof of convergence relies on the assumption that the single-agent actor-critic algorithm converges to the optimal policy, which is unverified therein. In addition, our work is related to JJyakumar and Aditya (2019), where the proposed algorithm is only shown to converge asymptotically to a stationary point of the mean-field game.
Our work also extends the line of work on finding the Nash equilibria of Markov games using MARL. Due to the computational intractability introduced by the large number of agents, such
line of work focuses on finite-agent Markov games (Littman 1994
2001, Hu and Wellman 1998
Bowling [001] Lagoudakis and Parr 2002: Hu and Wellman 2003:
Conitzer and Sandholm 2007
Perolat et al., 2015; Pérolat et al.) 2016b 2018 Wei et al., 2017:
Zhang et al. 2018 Zou et al.
90199Casggain et al. 2019p. See also Shoham et al. [ [2003] 2007): Busoniu et al. 2008 Li (2018)
for detailed surveys. Our work is related to Yang al. (2018b), where they combine the mean- mean-field
approximation of actions (rather than states) and Nash Q-learning (Hu and Wellman| (003) to study
general-sum Markov games with a large number of agents. However, the Nash Q-learning algorithm is only applicable to finite state and action spaces, and its convergence is established under rather strong assumptions. Also, when the number of agents goes to infinity, their approach yields variant of tabular Q-learning, which is different from our mean-field actor-critic algorithm.
For policy optimization, based on the policy gradient theorem, /Sutton al. (2000); Konda and Tsit- siklis (2000) propose the actor-critic algorithm, which is later generalized to the natural actor-critic algorithm (Peters and Schaal 2008 Bhatnagar et al. 2009). Most existing results on the conver- gence of actor-critic algorithms are based on stochastic approximation using ordinary differential equations (Bhatnagar et al. 2009 Castro and Meir 2010, Konda and Tsitsiklis, 2000 Maei 2018).
Cheorem,,Sutton
which are asymptotic in nature. For policy eva vvalunaton. the convergence of primal-die ddall gradient tem- poral difference is studied in [iu et al. (2015): Du et al. (017)); Wang et al. (2017b) Yu (2017); Wai et al. (2018). However, this line of work assumes that the feature mapping is bounded, which is not the case in our setting. Thus, the existing convergence results are not applicable to analyzing the critic update in our setting. To handle the unbounded feature mapping, we utilize truncation argument, which requires more delicate analysis.
Finally, our work extends the line of work that studies model-free RL for LQR. For example, Bradtke (1993); Bradtke et al.] (1994) show that policy iteration converges to the optimal policy. Tuu and Recht 7):17;; Dean et al. (2017) study the sample complexity of least-squares
-iffeeee
for policy evaluation. More recently, Fazel et all (2018); Malik et al. (2018); Tu and Rechi (2018) show that the policy gradient algorithm converges at a linear rate the optimal policy. See as also Hardt et al. (2016) Dean et al. (2018) for more in this line of work. Our work is also closely related to Yang al. (211)), where they show that the sequence of policies generated by the natural actor- critic algorithm enjoys a linear rate of convergence to the optimal policy. Compared with this work, when fixing the mean-field state, we use the actor-critic algorithm to study LQR in the presence of drift, which introduces significant difficulties in the analysis. As we show in (3 the drift causes the optimal policy to have an additional intercept, which makes the state- and action-value functions more complicated.
3

---

Published as a conference paper at ICLR 2020
Notations. We denote by | the spectral norm, p(M) the spectral radius, miin miia(M) the min- imum singular value, and (a) the maximum singular value of a matrix M. We use |a|2z 2 to represent the f2-norm of a vector a, and {a)} to denote the sub-vector (aq, ai+1s...., 0z)* where og is the k-th entry of the vector a. For scalars ui....,00 we denote by poly(a1, an) the polynomial of d1..... an. and this polynomial may vary from line to line. We use [n]] to denote the set {1, ..) for any N.
LINEAR- CHIEAR-QUADRTTE MEAN-FIELD GAME
quaarauuaatiic mean-field Na-player game involves N₂ E N agents, whose state transitions are given by
4+1 = Axt + Bud Ar, + d' + w/,
vt V 0, E (Na).
Here A E Rm B E m and A E _m are matrices, of E R and un R2 are the state and action vectors of agent i, respectively, the vector d' E R is drift term, w/ E R is an independent random noise term following the Gaussian distribution (0, V.), and = 1/N, Σド= at is the mean-field state. The agents are coupled through the mean-field state _, In the linear-quadratic mean-field Na-player game, the cost of agent i [Na] at time
is given by c = (xt) TTQ + (uf) Rut + x, Que.
where Q E R=xm R E Pexk and Q mm are matrices, and ut is generated by n', i..., the policy agent i. To measure the performance of agent following its policy n' under the influence of the other agents, we define the expected total cost of agent as
JT
No) lim E T
We are interested in finding Nash equilibrium (T x² :..., N),, which defined by n x No) < J
J' (IT
n ))
Vi'. i E [Na].
That is, agent i cannot further decrease its expected total cost by unilaterally deviating from its Nash policy.
For the simplicity of discussion, we assume that the drift term d' identical for each agent. We consider taking the infinite- iifiiite-population limit N, oo, where each agent has infinitesimal contri- bution to the dynamics of the system. Thus, the joint policy of all the agents except agent can be modeled mean-field policy nt, and all the agents following such mean-field policy #1 generate the mean-field state Er,, where { h:o is generated following the policy æt. By the symmetry of the agents in terms of their state transitions and cost functions, we focus on a fixed agent and drop superscript hereafter.
Before we formally present the formulation of linear-quadratic mean-field games, we first introduce the following mean-field LQR (MF-LQR) problem, which aims to find an optimal policy for the fixed agent given the mean-field policy n².
Problem 2.1 (MF-LQR). Given the mean-field policy Ti, we consider the following formulation,
2++1 Ar, Bu, + AEx! + We
c(Te, u4) = xi Qu, + u, Ru4 + (Ex)) T '(Ex)))
[ xt)
lim T-200
E T t=
c(ær, uz)
where x, E RT the state vector, 4 E R is the action vector generated by the policy n, {a] J2 is the trajectory generated by the policy o!, wt E Rmm an independent random noise term following the Gaussian distribution A (0, W.), and Rn is a drift term. Here the expectation Ex! taken across all the agents. We aim to find n² such that J(x", mt) infren J[n m.).

---

Published as a conference paper at ICLR 2020
Note that controllable linear system using linear quadratic optimal control is always stable. Further combining the fact that our linear closed-loop dynamics in Problem 2.1 is driven by the Gaussian noise term W/, we know that the Markov chain of states generated by the policy x admits stationary distribution and converges this stationary distribution. This implies that the mean-field state lEr! converges to a constant vector pl as I + oc, which serves as a time-invariant mean-field state, As we consider the ergodic setting, it then suffices study Problem with sufficiently large. Therefore, the influence of the mean-field -feldffidd policy गí is captured by the mean-field state jut. By re- re-formulating Problem 2.1 with slight abuse of notations, we obtaín the following drifted-L.RR (D-LQQ).
Problem 2.2 (D-LQR). Given mean-field state J R consider the following formulation,
3++1 = Ax Bu, + Ap + d Wey ca(Te; u+) = Ii QIe u. Rug + u qu.
(x) = lim T-220
Σ
cu (2 uz)
T
where E Ih is the state vector, E TR is the action vector generated by the policy wy E R an independent random noise term following the Gaussian distribution (D, V..), and d E Rm is drift term. We aim to find an optimal policy xp such that (T())) infxen (T).
Compared with the most studied LQR problem (Lewis et al., 2012), both the state transition and the cost function in Problem 2.2 have drift terms, which act as the mean-field "force" that drives the states away from zero. Such mean-field "force" introduces additional challenges when solving Problem 2.2 in the model-free setting (see $3.3 for details). On the other hand, the unique optimal policy Ty of Problem 2.2 admits a linear form (Tx) = - K + dug under certain regularity conditions (Anderson and Moore 2007 where the matrix Kい E Rx and the vector b,, R are the parameters of TH Motivated by such a linear form of the optimal policy, we define the class of linear-Gaussian policies as
II [m(x) K by + 17: K Rexm by R*),
(2.1)
where a E R and the standard Gaussian noise term 77 E R is included to encourage exploration. To solve Problem 2.2. it suffices to find the optimal policy o within II. We define A (u) T as the optimal policy under the mean-field state μ.
Assume that all the agents follow the linear policy (Ix) - K b, under the mean-field state μ. By plugging u, = π (2;) into the state transition in Problem 2.2 as - Do, we know that these agents generate new mean-field state Veew such that
Nnew (I A BKx) (x (Bbr + Au + dd).
We define (2 π) -nnew as such new mean-field state.
Now, we ready present the following linear-quadratic mean- hean-field game (LQ-MFG). Problem 2.3 (LQ-MFG). We consider the following formulation.
I++1 = Azi + Bu + Ay + d + We.
c(2,, Me) = xI7 Qx, u, Ru, + p TQu,
J(m, (4)
lim E T'
cl u.)
where E 1dth is the state vector, Ut E R is the action vector generated by the policy म, E R the mean-field state, W, E m is an independent random noise term following the Gaussian distribution (0, Vw), and d E R is a drift term. We aim to find pair (u²,"*) such that (i) J(=", 1² inf J (IT, )²);; (ii) Exy converges μ² + oc, where {x; h000 the Markov chain of states generated by the policy x².
The formulation in Problem 2.3 studied by Lasry and Lions (007): Bensoussan et al. (2016); Saldi et al. 2018a| b). We propose more general formulation in Problem C.2 (see C of the appendix for
5

---

Published as a conference paper at ICLR 2020
details), where additional interaction term between the state vector 2; and the mean-field state incorporated into the cost function. According to our analysis in |[] up to minor modification, the results in the following sections also carry to Problem Therefore, for the sake of simplicity, we focus on Problem 2.3 in the sequel.
In Problem 2.3 condition (i) is equivalent to the optimality of the policy л² under the mean-field state 14", namely, (1(²)) = πτ. Meanwhile, condition (ii) is equivalent to the invariance of the mean-field state μ= given the policy n². namely, A2(x", .²) p². Such equivalence follows from the NCE principle (Huang et al. 2006; 2007), which also motivates the following definition of the Nash equilibrium pair (Saldi et al. (0)8a
Definition 2.4 (Nash Equilibrium Pair). The pair (μ², ,-*) Rm x constitutes Nash equilibrium pair of Problem 2.3 if it satisfies x = A1(x") and n² = A2("", Here μ² is called the Nash mean-field state and called the Nash policy.
By Definition 2.4 Problem 2.3 aims find Nash equilibrium pair (n²,, )²)
MEAN-FIELD ACTOR-CRITIC
We first characterize the existence and uniqueness of the Nash equilibrium pair of Problem 2.3 under mild regularity conditions, and then propose a mean-field actor-critic algorithm to obtain such Nash equilibrium. As a building block the mean-field actor-critic, we propose the natural actor-critic to solve Problem 2.2
3.1
EXISTENCE AND UNIQUENESS NASII EQUILIBRIUM PAIR
We now establish the existence and uniqueness of the Nash equilibrium pair defined in Definition We impose the following regularity conditions.
2.4
Assumption 3.1. We assume that the following statements hold:
The algebraic Riccati equation X = =ATXA A Q AT X X X admits unique symmetric positive definite solution X*:
i It holds for Lo L1L3 + L2 that Lo < 1, where
L = [[(( - A)Q (T
BR
| (T-A)" - R
L = [1 p(A BK*)] |
La = [1-p(A- BK*)] B|||2
Here K* - X R) -BT
The first assumption is implied by mild regularity conditions the matrices A, B. Q, and R. which
are (1) the positivity of R: (2) the non-negativity of Q C C: (3) the observability of (A, C);; (4) the stability of (A, B). See De Souza al. (198)) : Lewis et al. (012) for more details. The second assumption is standard in the literature (Bensoussan et al. 2016:] Saldi et al. (0188), which ensures the stability of the LQ-MFG. In the following proposition, we show that Problem 2.3 admits a unique Nash equilibrium pair.
Proposition 3.2 (Existence and Uniqueness of Nash Equilibrium Pair). Under Assumption 3.1 the operator A-- A2 Ai (-)) is Lo-Lipschitz, where Lo is given in Assumption 3.1 Moreover, there exists unique Nash equilibrium pair (μ²,, π of Problem 2.3
Proof. See E.I for detailed proof.
3.2 MEAN-FIELD ACTOR-CRITIC FOR LQ-MFG
The NCE principle motivates fixed-point approach to solve Problem 2.3 which generates a quence of policies {T and mean-fieke states {1a}.20 satisfying the following two properties: (i) Given the mean-field state Pa, the policy π, is optimal. (ii) The mean-field state becomes M4+1 as > sc, all the agents follow π, under the current mean-field state μ.. Here (i) requires solving Problem 2.2 given the mean-field state μs, while (ii) requires simulating the agents following the

---

Published as a conference paper at ICLR 2020
Algorithm Mean-Field Actor-Critic for solving LQ-MIG.
1: Input:
Initial mean-field state 1oo and Initial policy to with parameters Ko and b0- Numbers of iterations S, (Na)ee(s). (Hs)ae[s)- (Tam Tan Je
(Th. Tht s.I.
Stepsizes (ES)) (7))) ((see (o Des.
2: for = 0.1, do
3: Policy Update: Solve for the optimal policy xx+1 with parameters Ks+1 and bu+1 of Problem
2.2 via Algorithm 2 with Mas Ta. NN. Hs, (Ts,nyTa,nnent Ta, TnENN. (T s. To s [he] Ys 7h
(Nemcchee(NA)/eeeTr....) and {o (Ta.,,ch which gives the estimated mean-fiche state
11..11..111
4: Mean-Field State Update: Update the mean mean-field state via ps+1 + PKatide
5: end for
6: Output: Pair (Ts; ps))
policy ns given the current mean-field M4s- Based such properties, propose the mean-field actor-critic Algorithm
Algorithm requires solving Problem 2.2 each iteration to obtain T, A (Ha) and M441 (2ss J.). To this end, we introduce the natural actor-critic in 333 that solves Problem 2.2
3.3 NATURAL ACTOR-CRITIC FOR D-LQR
Now we focus on solving Problem 2.2 for fixed mean-field state μ4, we thus drop the subscript hereafter. With slight abuse of notations, we write Tx,((x) = - -xx + b + to emphasize the dependence on and and JKK, b) = ((TK.)) consequently. Now, we propose natural actor-critic solve Problem 2.2
For any policy nK, E IT, by the state transition in Problem 2.2 we have
F++1 (A BK)2, + (Bb + Ap d) + Ce,
C ~~~100 V.).
(3.1)
where V, TBB ... It is known that if p(A BK) 1. then the Markov chain {zr h1o0
induced by (3.1) has a unique stationary distribution .V' (P 2x) (Anderson and Moore 2007
where the mean-field state PK& and the covariance + k satisfy that
HK. = (1 - BK (Bb + Ap dd), Φ = (A (A-ABK) B A BK) Ve.
(3.2)
(3.3)
Meanwhile, the Bellman equation for Problem 2.2 takes the following form
Pk = + K RK) + (A -BK) Px(A - BK).
(3.4)
Then by calculation (see Proposition B.2 in B.1 of the appendix for details), it holds that the ex- pected total cost JKK, b) is decomposed as
J(K, b) (K) J2(K b) + 0² tr()) + p TH,
(3.5)
where (K) and J2(K, b) are defined as
Jı(K) = =r[(Q + K RK) = [Pr(P (pK.) J2( -(mKo) ( -RK
KT KTRK
RK
-KT
[HKDb)
(3.6)
RK
R
Here Jn (K) is the expected total cost in the most studied LQR problems (Yang al. 2019 Fazel et al. 2018), where the state transition does not have drift terms. Meanwhile, J2(K, b) to the expected cost induced by the drift terms. The following two propositions characterize the properties of Jz K, b).
sondesponds
First, show that Ja K, is strongly convex in b.

---

Published as a conference paper at ICLR 2020
Proposition 3.3. Given any K, the function J2(K, b) is vK st-oolyygly convex in b. Here VK mmin (X,, Vi, + Y2, Y2,k), where Y1,K (I A BK) B R and Y2,K Q!/2(I - A+ В B. Also, J2(K, b) has Lipssccciitz continuous gradient in b, where LK is upper bounded (K I [1 p(A BK)] B || || + |B ||
Proof. See E.4 for detailed proof.
Second, we show that ming J2((,b) is independent K. Proposition 3.4. We define 6k argming J2( b), where (2(K,b) is defined in (3.6). holds
that
bk [KQQ A) BJ [11 -JQ (I- A) BR (Au + dd)
Moreover, () takes the form of
J2(K, b*) = (Ap d) [[T AI A) T BB (Au d),
which is independent of K.
Proof. See E.2 for detailed proof.
Since min, J2(K, b) is independent of K by Proposition 3.4 it holds that the optimal K is the same as argmink J1 (K). This motivates us to minimize [K. b) by first updating K following the gradient direction V VKJi(K)
the optimal K*, then updating b following the gradient direction VoJ2(K", b). We now design our algorithm based on this idea.
We define Yk. PK,b, and qK,b
Tk Q + A PKA
P
r
r Tx
B PKA
R+ B B
T
PK. = A [ (Ap + d) + [K,]],
(Ap + d) + fK,,), 9K,b = BT [P
(3.7)
where JK.b -T--A BK) ((i0)-((1 [[(A T + Au d) KT T Rb). By calculation (see Proposition B.3 in B.1 of the appendix for details), the gradients J₁(K) and J2(K, b) take the forms of
(KK = - - ØK.
Vo22(,b)) T (- + T qK.b.
Our algorithm follows the natural actor-critic method (Bhatnagar et al. 2009) and actor-critic method (Konda and Tsitsikii 2000). Specifically, (i) To obtain the optimal K in the critic up-
date step, we estimate the matrix Yx by Tx via policy evaluation algorithm, e.g., Algorithm 3 3or Algorithm (see (B.2) and of the appendix for details); in the actor update step, update K via K K 7- (T K TRI), where the term T3 K - T is the estimated natural gradient. (ii) To obtain the optimal 6* given K* in the critic update step, we estimate T K* QK*,A .hs and μKK by TK., TK b. and fu-. .6 via a policy evaluation algorithm; In the actor update step, we update b via b b b- VnJ2(K*, (K*,,), b), where V,,J(K**, .b) = T estimated gradient. Combining the above procedure, obtain the natural actor-critic for Problem 2.2 which is stated in Algorithm[2
& + b) T21 f + TK-.a the
One may want to apply gradient method to JKK b) directly in the joint space of K and b. However, the gradient dominance property of J1 JK(K) in the most studied LQR problem (Yang et al. 2019) no longer holds for J(K,b). b). Therefore, the convergence of the gradient method to J(K is not guaranteed in our problem.
4 GLOBAL CONVERGENCE RESULTS
The following theorem establishes the rate of convergence of Algorithm D to the Nash equilibrium pair (μ²", x²) of Problem 2.3
8

---

Published as a conference paper at ICLR 2020
Algorithm 2 Natural Actor-Critic Algorithm for D-LQR.
1: Input:
Mean-field state j and initial policy &Ka.bo
Numbers of iterations N, H, (Ta, Tn TnInE[N]. (Th, TR]NEIH)-
Stepsizes 7, 7 (Tn,t) (T (RR,
2: for = 0, 2,,,,...,NN. N do
3: Critic Update: Compute Tx, via Algorithm with bor ,4 TniIns (To,theep.. Ko, and
by as inputs.
4: Actor Update: Update the parameter via
Knt1 f Kn - (7. K, Kn R...)
5: end for
6: for = 2,
Critic Update: Compute PKN.,, KNN TKNi via Algorithm with dh Ms Th. Th
7:
(vh ( Ko, and by.
8:
Actor Update: Update the parameter via
b < ba 70 [ (- (KKNūK + bb) + 921 K + :u..
9: end for Output: Policy TK,6 TKN Ag estimated mean-field state DK D.NN. ba
Theorem 4.1 (Convergence of Algorithm []. For sufficiently small tolerance number of iterations Algorithm such that
0, we set the
S log(llug - 14 11 12--11
(4.1)
log(1/ L/)
For any & E [S], we define
E, = min
[1 - p(A - BK*) Bl [|Al]2) -1 1(IA=112+1111112
+|ddl12)) Smin((1))
o (R) E2,
vK- [1 ( - |B|
Mo(u.)- .6, { 2
(4.2)
where vk- defined in Proposition 3.3 and
Mo(r)) 4 1 'T ATT [(T A)Q A)T BR BR (Aus + d0)l
[uK- + min! (V.) amin (R)) 1/2
(4.3)
In the s-th policy update step in Line of Algorithm I we set the inputs via Theorem B.4 such that Ju, (T.+1) Jus (TT..) < Eer where the expected total cost Jr, (-) is defined Problem 2.2 and
Th (1,,)) is the optimal policy under the mean-field state ug. Then it holds with probability at
least 1 - g that
||us - S2
-K Se. - S (1+ L.)
Here n² is the Nash mean-field state, Ks and by are parameters of the policy иT. and K and b* are parameters of the Nash policy n².
Proof Sketch. The proof of the theorem is based the convergence of the natural actor-critic al- gorithm 2 and a contraction argument. First, we prove in Theorem B.4 that Algorithm 2 converges linearly the optimal policy Problem 2.2 By this, in each iteration of Algorithm the error between μs+1 and 1 to be E, > O with high probability, where 1 is the mean-field state generated by the optimal policy A (1))) in other words, # A(Ha). Combining the fact
control
from Proposition 3.2 that A(-) is contraction, we deduce that
|| /² I ||A(U)) 11, + E. I Lo 11le 1² + E.

---

Published as a conference paper at ICLR 2020
with high probabilityy, where E, >> 0 is some enror term and is specified in the detailed proof. More- over, by telescoping sum, and note that the sum E Eg is upper bounded by the desired error e, we conclude the theorem. See [.1 for a detailed proof.
We highlight that if the inputs of Algorithm D satisfy the conditions stated in Theorem B.4 it holds that Ju, (T.+1) - Ju. (
< Eg for any E [S]. See Theorem B.4 in B. of the appendix for details. By Theorem 4.1 Algorithm converges linearly the unique Nash equilibrium pair (n² >²) of Problem 2.3 To the best of our knowledge, this theorem is the first successful attempt to establish that reinforcement learning with function approximation finds the Nash equilibrium pairs in mean mean-field games with theoretical guarantee, which lays the theoretical foundations for applying modern reinforcement learning techniques to general mean-fiele games.
5 CONCLUSION
For the discrete-time linear-quadratic mean-field games, we provide sufficient conditions for the existence and uniqueness of the Nash equilibrium pair. Moreover, we propose the mean-field actor- critic algorithm with linear function approximation that is shown converges to the Nash equilibrium pair with linear rate of convergence. Our algorithm can be modified use other parametrized function classes, including deep neural networks, for solving mean-field games. For future research, we aim to extend our algorithm other variations of mean-field games including risk-sensitive mean-field games (Saldi et al. (2088a] Tembine et al., 2014). robust mean-field games (Bauso et al., 2016), and partially observed mean-field games (Saldi et 2019).
REFERENCES
Alizadeh, F., Haeberly, J.-P. A. and Overton, M. L. (1998). Primal-dual interior-poing methods for semidefinite programming: convergence rates, stability and numerical results. SIAM Journal on Optimization, 8 746-768.
Anderson, B. D. and Moore, B. (2007). Optimal control: linear quadratic methods. Courier Corporation.
Araki, B., Strang, J., Pohorecky, S., Qiu, C., Naegeli, T. and Rus, D. (2017). Multi-robot path plan- ning for swarm of robots that can both fly and drive. In 2017 IEEE International Conference Robotics and Automation (ICRA). IEBE.
Ash, C. (2000). Social-self-interes.. Annals of public and cooperative economics, 71 261-284.
Axtell, R. L. (2002). Non-cooperative dynamics of multi-agent teams. In Autonomous Agents and Multiagent Systems.
Bardi, M. (2011). Explicit solutions of some linear-quadratic mean field games. Networks and heterogeneous media. 243-261.
Bardi, M. and Priuli, F. S. (2014). Linear-quadrate n-person and mean-field games with ergodic cost. SIAM Journal on Control and Optimization, 52 3022-3052.
Bauso, D., Tembine, H. and Başar, T. (2016). Robust mean field games. Dynamic games and appli- cations, 277-303.
Bensoussan, A., Chau, M., Lai, Y. and Yam, S. C. P. (2017). Linear-quadratic mean field Stack- elberg games with state and control delays. SIAM Journal on Control and Optimization, 55
Bensoussan, A., Frehse, J. and Yam, P. (2013).. Mean Mean.fiel games and mean fien type control theory. Springer.
Bensoussan, A., Sung, K., Yam, C. and Yung, S. (2016). Linear-quadratie mean field games. Journal of Optimization Theory and Applications, 169 496-529.
10

---

Published as a conference paper at ICLR 2020
Bhandari, J., Russo, D. and Singal, R. (2018). A finite time analysis of temporal difference learning with linear function approximation. arXiv preprint arXiv:1806.02455
Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M. and Lee, M. (2009). Natural actor-critic algorithms. Automatica, 45 2471-2482.
Biswas, A. (2015). Mean field games with ergodic cost for discrete time markov processes. arXiv preprint arXiv:1510.0800
Borkar, V. S. and Meyn, S. P. (2000). The ODE method for convergence of stochastic approximation
and reinforcement learning. SIAM Journal on Control and Optimization, 38 447-469.
Bowling, M. (2001). Rational and convergent learning in stochastic games. International Con- ference Artificial Intelligence.
Bowling, M. and Veloso, M. (2000). An analysis of stochastic game theory for multiagent reinforce- ment learning. Tech. rep.. Carnegie Mellon University.
Bradtke, S. (1993). Reinforcement learning applied to linear quadratic regulation. In Advances in Neural Information Processing Systems.
Bradtke, S. J., Ydstie, B. E. and Barto, A. G. (1994). Adaptive linear quadratic control using policy iteration. In American Control Conference, vol. 3. IEEE.
Briani, A. and Cardaliaguet, P. (2018). Stable solutions in potential mean field game systems. Non- linear Differrntiall Equations and Applications, 25
Busoniu, L., Babuska, and De Schutter, (2008). A comprehensive survey of multiagent rein- forcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 38 156-172.
Caines, P. E. and Kizilkale, A. C. (2017). e-nash equilibria for partially observed LQG mean field games with major player. IEEE Transactions Automatic Control, 62 3225-3234.
Calderone, D. J. (2017). Models of Competition for Intelligent Transportation Infrastructure: Park- ing, Ridesharing, and External Factors in Routing Decisions. University of California, Berkeley.
Carmona, R. and Delarue, F. (2013). Probabilistic analysis of mean-field games. SIAM Journal on Control and Optimization, 51 2705-2734.
Carmona, R. and Delarue, F. (2018). Probabilistic Theory of Mean Field Games with Applications 1-I1. Springer.
Casgrain, P., Ning, B. and Jaimungal, S. (2019). Deep Q-learning for Nash equilibria: Nash-DQN. arXiv preprint arXiv: 1904. 10554.
Castro, D. D. and Meir, R. (2010). convergent online single time scale actor critic algorithm. Journal of Machine Learning Research, 11 367-410.
Conitzer, V. and Sandholm, T. (2007). AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents. Machine Learning, 67 23-43.
de Cote, E. M., Lazaric, A. and Restelli, M. (2006). Learning to cooperate in multi-agent social dilemmas. In International Conference on Autonomous Agents and Multiagent Systems. ACM.
De Souza, C., Gevers, M. and Goodwin, G. (1986). Riccati equations in optimal filtering of non- stabilizable systems having singular state transition matrices. IEEE Transactions on Automatic Control, 31 831-838.
Dean, S., Mania, H.. Matni, N., Recht, B. and Tu, S. (2017). On the sample complexity of the linear quadratic regulator. arXiv preprint arXiv:1710.0166
Dean, S., Mania, H., Matni, N., Recht, B. and Tu, S. (2018). Regret bounds for robust adaptive control of the linear quadratic regulator. In Advances in Neural Information Processing Systems.

---

Published as a conference paper at ICLR 2020
Doerr, B., Linares, R., Zhu, P. and Ferrari, S. (2018). Random finite set theory and optimal control for large spacecraft swarms. arXiv preprint ar1.v:1810.00696.
Du, S. S., Chen, J., Li, L., Xiao, L. and Zhou, D. (2017). Stochastic variance reduction methods for policy evaluation. In Proceedings of the 34th International Conference on Machine Learning- Volume 70. JMLR. org.
Fang, J. (2014). The LQR controller design of two-wheeled self-balancing robot based on the parti- cle swarm optimization algorithm. Mathematical Problems in Engineering, 2014.
Fazel, M., Ge, R., Kakade, S. M. and Mesbahi, M. (2018). Global convergence of policy gradient methods for the linear quadratic regulator. arXiv preprint arXiv:1801.000
Ganzfried, S. and Sandholm, T. (2009). Computing equilibria in multiplayer stochastic games of imperfect information. In Twenty-First International Joint Conference Artificial Intelligence.
Gomes, D. A., Mohr, and Souza, R. R. (2010). Discrete time, finite state space field games. Journal de mathématiques pures et appliquées, 93 308-328.
Gomes, D. A. et al. (2014). Mean field games models brief survey, Dynamic Games and Appli- cations, 1 110-154.
Guéant, O., Lasry, J.-M. and Lions, P.L.. (2011). Mean field games and applications. In Paris- Princeton lectures on mathematical finance 2010. Springer, 205-266.
Guo, X., Hu, A., Xu, and Zhang, J. (2019). Learning mean-field games. arXiv preprint
Hardt, M., Ma, T. and Recht, B. (2016). Gradient descent learns linear dynamical systems. arXiv preprint
Heinrich, J. and Silver, D. (2016). Deep reinforcement learning from self-play in imperfect- information games. arXiv preprint 163001160../1121.
Hu, J. and Wellman, M. P. (1998). Multiagent reinforcement learning: Theoretical framework and algorithm. In International Conference Machine Learning. Morgan Kaufmann Publishers Inc.
Hu, J. and Wellman, M. P. (2003). Nash Q-learning for general-sun stochastic games. Journal of machine learning research, 1039-1069.
Huang, J. and Huang, M. (2017). Robust mean field www.guuuarrrituuusuiiiiii games with unknown L'=ddisturbance. SIAM Journal on Control and Optimization, 55 2811-2840.
Huang, and Li, N. (2018). Linear innear-quadratic mean-field game for stochastic delayed systems. IEEE Transactions on Automatic Control, 63 9722-2729,
Huang, J., Li, X. and Wang, T. (2016a). Mean-field Saaa---qurraai--Gausiii (LQG) games for stochastic integral systems. JEEE Transactions on Automatic Control, 61 2670-2675
Huang, J., Wang, S. and Wu, Z. (2016b). Backward mean-field lincar-quadratic- aaat-uuu-tat--aaasiiinn Gaussian (LQG) games: Full and partial information. IEEE Transactions on Automatic Control, 61 3784 3796.
Huang, M., Caines, P. E. and Malhamé, R. P. (2003). Individual and mass behaviour large popu- lation stochastic wireless power control problems: centralized and nash equilibrium solutions. In Conference on Decision and Control. IEEE.
Huang, M., Caines, P. E. and Malhamé, R. P. (2007). Large--ooullate cost-coupled LQG problems with nonuniform agents: individual-mant mass behavior and decentralized e-Nash equilibria. IEEE transactions on automatic control, 52 1560-1571.
Huang, M., Malhamé, R. P., Caines, P. E. et al. (2006). Large population stochastic dynamic games: closed-loop Mckean- Vlasov systems and the Nash certainty equivalence principle. Communica- fions in Information Systems, 6 221-252.
12

---

Published as a conference paper at ICLR 2020
Huang, M. and Zhou, M. (2019). Linear quadratic mean field games: Asymptotic solvability and relation to the fixed point approach. arXiv preprint XI1::1903.08776.
Hughes, E., Leibo, J. Z., Phillips, M., Tuyls, K., Dueñez- Guzman, E., Castañeda, A. G., Dunning, I., Zhu, McKee, K., Koster, R. et al. (2018). Inequity aversion improves co- operation in intertemporal social dilemmas. In Advances in Neural Information Processing Systems.
Jayakumar, S. and Aditya, M. (2019). Reinforcement learning in stationary mean-field games. In International Conference Autonomous Agents and Multiagent Systems.
Kakade, S. M. (2002). A natural policy gradient. In Advances in neural information processing systems.
Konda, V. R. and Tsitsiklis, N. (2000). Actor-critic algorithms. In Advances in neural information processing systems.
Korda, N. and La, P. (2015). On TD(0) with function approximation: Concentration bounds and centered variant with exponential convergence. International Conference on Machine Learn- ing.
Kushner, H. and Yin, G. G. (2003). Stochastic approximation and recursive algorithms and appli- cations. Springer Science & Business Media.
Lagoudakis. M. G. and Parr, R. (2002). Value function approximation in zero-sum Markov games. In Uncertainty in Artificial Intelligence.
Lasry, J.-M. and Lions, P.-L. (2006a). Jeux à champ moyen. I-le cas stationnaire. Comptes Rendus Mathématique, 343 619-625.
Lasry, J.-M. and Lions, P.-L. (2006b). Jeux à champ moyen. Il-horizon fini et contrôle optimal. Comptes Rendus Mathématique, 343 679-684.
Lasry, J.-M. and Lions, P.-L. (2007). Mean field games. Japanese journal of mathematics, 229 260.
LeCun, Y., Bengio, Y. and Hinton, G. (2015). Deep learning. Nature, 521 436-444,
Leibo, 7., 7ambaldi, V., Lanctot, M., Marecki, and Graepel, T. (2017). Multi-agent reinforce-
ment learning in sequential social dilemmas. In International Conference Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Sys- tems.
Lewis, F. L., Vrabie, D. and Syrmos, V. L. (2012). Optimal control. John Wiley & Sons.
Li, S., Zhang, W. and Zhao, L. (2017). Connections between mean-field game and social welfare optimization. arXiv preprint arXiv:1703.10211.
Li, T. and Zhang. J.-F. (2008). Asymptotically optimal decentralized control for large population stochastic multiagent systems. IEEE Transactions on Automatic Control, 53 1643-1660.
Li, Y. (2018). Deep reinforcement learning. arXiv preprint arXiv:1810.06339,
Littman, M. L. (1994). Markov games as framework for multi-agent reinforcement learning. In Machine Learning Proceedings /994. Elsevier, 157-163.
Littman, M. L. (2001). Friend-or-foe Q-learning in general-sum games. In Proceedings of the Eigh- teenth International Conference on Machine Learning.
Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S. and Petrik. M. (2015). Finite-sample analysis of proximal gradient 'DD algorithms. Conference on Uncertainty Artificial Intelligence.
Maei, H. R. (2018). Convergent actor-critic algorithms under off-policy training and function ap- proximation. arXiv preprint arXiv: 1802.07842
13

---

Published as a conference paper at ICLR 2020
Magnus, J. R. (1979). The expectation of products of quadratic forms in normal variables: the practice. Statistica Neerlandica, 33 131-136.
Magnus, J. R. et al. (1978). The moments of products of quadratic forms in normal variables. Univ., Instituut voor Actuariaat Econometrie.
Malik, D., Pananjady, A., Bhatia, K., Khamaru, K., Bartlett, P. and Wainwright, M. (2018). Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. arXiv preprint arXiv: /8/::18//0// 181.00835. 08305.
Mguni, D., Jennings, and de Cote, E. M. (2018). Decentralised learning in systems with many, many strategic agents. In Phirty-Secome AAAI Conference on Artificial Intelligence.
Minciardi, R. and Sacile, R. (2011) 1). Optimal control in cooperative network of smart power grids. JEEE Systems Journal, 6 126-133.
Moon, J. and Başar, T. (2014). Discrete-time LQG mean field games with unreliable communica- tion. In Conference on Decision and Control. IEEE.
Moon, and Başar, T. (2018). Linear quadratic mean field stackelberg differential games. Automat- ica, 97 200-213.
Moravčík, M., Schmid, M., Burch, N., Lisý, V., Morrill, D., Bard, N., Davis, T. Waugh, K., Johanson, M. and Bowling, M. (2017). Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356 508-513.
Nash, (1951). Non-cooperative games. Annals of mathematics 286-295.
OpenAl (2018). Openai five.
Pérolat, J., Piot, B., Geist, M., Scherrer, B. and Pietquin, O. (2016a). Softened approximate policy iteration for markov games. In International Conference on Machine Learning.
Pérolat, Piot, B. and Pietquin, O. (2018). Actor-critic fictitious play in simultaneous move multi- Stage games. In International Conference on Artificial Intelligence and Statistics.
Pérolat, J., Piot, B., Scherrer, B. and Pietquin, O. (2016b). On the use of non-staien non-stationary strategies for solving two-player zero-sum Markov games. In International Conference on Artificial Intelli- gence and Statistics.
Perolat, J., Scherrer, B., Piot, B. and Pietquin, O. (2015). Approximate dynamic programming for two-player zero-sum Markov games. International Conference on Machine Learning (ICML 2015).
Peters, J. and Schaal, S. (2008). Natural actor-critic. Neurocomputing, 71 1180-1190.
Rudelson, M., Vershynin, R. al. (2013). Hanson-wright inequality and Gabssan concentra- tion. Electronic Commuiccations in Probability, 18.
Saldi, N., Basar, T. and Raginsky, M. (2018a). Discrete-time risk-sensitive mean-field games. arXiv preprint IrXiv:1808. 000.00999.
Saldi, N., Basar, and Raginsky, M. (2018b). Markov-Nash equilibria mean-field games with discounted cost. SIAM Journal on Control and Optimization, 56 4256-4287.
Saldi, N., Basar, T. and Raginsky, M. (2019). Approximate Nash equilibria in partially observed stochastic games with mean-field interactions. Mathematics of Operations Research.
Sandholm, W. H. (2010). Population Games and Evolutionary Dynamics. MIT Press.
Shalev-Shwartz, S., Shammah, S. and Shashua, A. (2016). Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295.
Shoham, Y., Powers, R. and Grenager, T. (2003). Multi-agent reinforcement learning: critical survey.
14

---

Published as a conference paper at ICLR 2020
Shoham, Y., Powers, R. and Grenager, T. (2007). If multi-agent learning is the answer, what is the question? Artificial Intelligence, 171 365-377.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Pamn V., Lanctot, M. et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529 484-489.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A. et al. (2017). Mastering the game of Go without human knowl- edge. Nature, 550 354.
Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT Press.
Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C. and Wiewiora, E. (2009a). Fast gradient-descent methods for temporal-differene learning with linear function ap- proximation. In Proceedings of the 26th Annual International Conference on Machine Learning. ACM.
Sutton, R. S., Maei, H. R. and Szepesvári, C. (2009b). A convergent o(n) temporal-difee difference algo- rithm for off-policy learning with linear function approximation. In Advances in neural informa- tion processing systems.
Sutton, R. S., McAllester, D. A., Singh, S. P. and Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In Advances in neural information process- ing systems.
Sznitman, A.-S. (1991). Topics in propagation of chaos. In Ecole d'été de probabilités de Saint- Flour XIX-1989. Springer, 165-251.
Tembine, H. and Huang, M. (2011). Mean field difference games: Mckean-V Vlasov dynamics. In Conference on Decision and Control and European Control Conference. IEEE.
Tembine, H., Zhu, Q. and Başar, T. (2014). Risk-sensitive mean-field games. IEEE Transactions on Automatic Control, 59 835-850
Tu, S. and Recht, B. (2017). Least-squares temporal difference learning for the linear quadratic regulator. arXiv preprint 1rXiv:1712.0864/
Tu, S. and Recht, B. (2018). The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. arXiv preprint arXiv:181.00355..
Vinyals, O.,. Babuschkin, I., Chung, J., Mathieu, M., Jaderberg, M., Czarnecki, W., Dudzik, A.,
Huang, A.. Georgiev, P., Powell, R. et al. (2019). Alphastar: Mastering the real-time strategy game starcraft ii.
Wai, H.-T., Yang, Z., Wang, P. Z. and Hong, M. (2018). Multi-agent reinforcement learning via dou- ble averaging primal-dual optimization. In Advances in Neural Information Processing Systems.
Wang, B.-C. and Zhang, J.-F. (2012). Mean field games for large-population multiagent systems with Markov jump parameters. SIAM Journal on Control and Optimization, 50 2308-2334.
Wang, J., Zhang W., Yuan, et (2017a). Display advertising with real-time bidding (RTB) and behavioural targeting. Foundations and Trends in Information Retrieval, 11 297-435.
Wang, Y., Chen, W., Liu, Y., Ma, Z.-M and Liu, T.-Y. (2017b). Finite sample analysis of the GTD policy evaluation algorithms in Markov setting. In Advances in Neural Information Processing Systems.
Watkins, C. and Dayan, P. (1992). Q-leariing Machine learning, 829--292.
Wei, C.-Y., Hong, Y.-T. and Lu, C.-J. (2017). Online reinforcement learning in stochastic games. In Advances in Neural Information Processing Systems.
Yang, E. and Gu, D. (2004). Multiagent reinforcement learning for multi-robot systems: A survey. Manuscript.
15

---

Published as a conference paper at ICLR 2020
Yang, J., Ye, X., Trivedi, R., Xu, H. and Zha, H. (2018a). Deep mean field games for learning opti- mal behavior policy of large populations. In International Conference on Learning Representa- fions.
Yang, Y., Luo, R., Li, M., Zhou, M., Zhang, W. and Wang, (2018b). Mean field multi-agent rein- forcement learning. arXiv preprint arXiv:/802.05433 852388
Yang, Z., Chen, Y., Hong, M. and Wang, Z. (2019). On the global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. arXiv preprint arXiv:1907.06245
Yu, H. (2017). On convergence of some gradient based temporal-difffrencee algorithms for off- policy learning. arXiv preprint arXiv: 171.v917...06652.
Zhang, K., Yang, Z., Liu, H., Zhang, T. and Başar, T. (2018). Finite-sample analyses for fully de- centralized multi-agent reinforcement learning. arXiv preprint arXiv:/812.02783..
Zhou, X. Y. and Li, D. (2000). Continuous-tine timoe mean- verrance portfolio selection: A stochastic LQ framework, Applied Mathematics and Optimization, 19-33.
Ziebart, B. D., Maas, A. L., Bagnell, A. and Dey, A. K. (2008). Maximum entropy inverse rein- forcement learning. In AAAI Conference Artificial Intelligence, vol. 3.
Zou, S., Xu, T. and Liang, Y. (2019). Finite-sample analysis for SARSA and Q-learning with linear function approximation. arXiv preprint 02234.
16

---

Published as a conference paper at ICLR 2020
A NOTATIONS IN THE APPENDIX
In the proof, for convenience, for any invertible matrix M, we denote by M-T = (M-1)T= = (M (MTT-= and || ||r the Frobenius norm. We also denote by svec(M) the symmetric vectoriza- tion of the symmetric matrix M, which is the vectorization of the upper triangular matrix of the symmetric matrix M, with off-diagonal entries scaled by v2. We denote by smat(-) the inverse operation. For any matrices G and H, we denote by G H the Kronecker product, and G & H the symmetric Kronecker product, which is defined as a mapping on a vector svec(M) such that (G @, H (M)) 1/2 svec (vec(HMe MG + GMH' ).
For notational simplicity, we write E,, (-) to emphasize that the expectation is taken following the policy
B AUXILIARY ALGORITHMS AND ANALYSIS
B. RESULTS D-LQR
In this section, we provide auxiliary results in analyzing Problem 2.2 First, we introduce the value
functions of the Markoy decision process (MDP) induced by Problem 2.2 We define the state- and action-value functions VK Vx,((I) and Qx,(< u) as follows
VK,(I)) = Σ B B[c(Er, u)) xo =a] - -J(Kb))
(B.1)
==
QKo(æ, u) c(2, u) (KK ([VK,N(<T)) z uo = u.]
(B.2)
where follows the state transition, and follows the policy TK,6 given Tt. In other words, we have 4, Kr, + b+ og,, where 17s ~ (O, The following proposition establishes the close forms of these value functions.
Proposition B.1. The state-value function VK,(+)) takes the form of
Vk,((x) x T PKT (x) + 2f mK,6) PK PKK.PKKKK
(B.3)
and the oction-value function Q2,6 v) takes the form of
QK,(xx,
26
Tx K
PK.b
2 ④1
(P(Pk(K) - . PR
11
9K,b
b
Rb + 26 R. JK,.b
(K, + K" RRK + PK))Kк
+ 2f [Ay + d) -MK. + (Ap + PP d),
(B.4)
where fK.6 (T + BK) -T T(A - -BK) Pk (EK)PP((P)
Ay + d) - K Rb). and Tx. PK.b, and
4K.b are defined in 3.7
Proof. See E.6 for detailed proof.
By Proposition B. we know that VK,((T) is quadratic in x, while QK,( u) is quadratic in (x u. )T. Now, we show that (3.5) holds.
Proposition B.2. The expected total cost ((K,)) b) defined in Problem 2.2 takes the form of
J(K,b) b) (KK) + J2(K, b) o² (r( + p TQ,
where
Ji(K) = u[(( + KT RK) LV(K...)), (KK&))
(
T
RK
-K
[KKD)
J2
b
RK
R
Here WKR& is defined in 3.2). Dx defined in 333 and Px is defined in (3.4
17

---

Published as a conference paper at ICLR 2020
Proof. See E.3 for detailed proof.
The following proposition establishes the gradients of (K) and J2(K, b), respectively.
Proposition B.3. The gradient of (1()) and the gradient of J2(K, b) with respect to b take the forms of
VKJi(K)) 2 - T PK.
(0 (- + TK 9K.]],
where Tk and 9K,b are defined in (3.
Proof. See E.5 for detailed proof.
The following theorem establishes the convergence of Algorithm 2
Theorem B.4 (Convergence of Algorithm 2 Assume that p(A BKo) < 1. Let >. be
sufficiently small tolerance. We set
S [ + BBI J(o, bo) ominl (V.)] (V.))=
N 2 C. x 1a > log 4 [KKo bu) J(K", [[[K",")]] ---1
T, 2 poly (I) 11+ | 12. |1 (Ko: bu)) Xx [11 11-p(A p(A- - -BK,)) -9 9
T, 2 poly pal([]4,,)))) (I|4,llF. 11.0011....111 || (Ko, bo)) Ax. [1-p(A - BKn)]
-12 12-
nn.t 70 112
7dt S min( 1 p(A BKN), [1 p(A BKN)] (111112 || ||||2 |1 11Q112) }.
11 Co VKN (7-)-1 Log ([K, 60) ((KK,bb*M . }
T > poly [| [I,,
J (KNN, 60)) - 'KKN
-1-p(A BKN)] -5-
Th 2 poly ply([| (I [I.. [1bnl22 11/12, J(KN, bo)) A MKN
-2
[1- 1(A - BKN)]
Th.- = 70 t 1/2
where C. Co. and 70 are positive absolute constants, {Kn incin and {br heem are the sequences generated by Algorithm [ λK, is specified Proposition B.6 and VKn is specified in Proposition
3.3
Then it holds with probability at least 1 100 that
J(KN. by) J(K (K)),b)) <,,
| b" l S Mo(n) 8/2
|KN K* < (om min (It) ss] 1/2
Mk uK-,0-122 1
where Ms(H)) is defined in
Proof. See D.2 for detailed proof.
By Theorem B. 3.4 given any mean-field state μr, Algorithm converges linearly to the optimal policy
π. of Problem 2.2
B.2 PRIMAL-DUAL POLICY EVALUATION ALGORITIM
Note that the critic update steps Algorithm 2 are built upon the estimators of the matrix Tx and the vector 9K.b. We now derive policy evaluation algorithm to establish the estimators of Tx and (K.b, which based on gradient temporal difference algorithm (Sutton al. 2009a).
We define the feature vector as
(fI,
(x u) =
T -- UKB
(B.5)
1 (- KKK,5 b)
18

---

Published as a conference paper at ICLR 2020
where
(1-
(u-(-Kuxs b) )
(0 u) svec
uKd (--(-KuKA
x
I uKd
Recall svee(M) gives the symmetric vectorization the symmetric matrix M. We also define
(vec(TK)
(DKA))
agb Txx
μ.K.b
(B.6)
-KKKb +
(K.b)
where Yx, PK.b, and yk.b defined in OK,. Meanwhile, we define
3.7
To estimate Yk and qk,b, it suffices estimate
K = E (ax, (M(( u) w0x', v()',,')) }
(B.7)
where (x', u()) is the state-action pair after (zz, u) following the policy *K&. and the state transition. The following proposition characterizes the connection between ① and a.b. Proposition B.5. It holds that
J(K,b)
J(K ETKK a [c(2, u) u))
OKO))
agd
where (x u) is defined in B.. OgKb is defined in [B.6 and ① defined in BB.
Proof. See E.7 for detailed proof.
By Proposition B.5 to obtain arg,b, it suffices to solve the following linear system in Ç (S1: C2
J(K, θ 5 B [c(a,, u) ..))
(B.8)
where for notational convenience, we define
0
θx,6 = Em [1b(,, w)] θK,²)
(B.9)
The following proposition shows that O is invertible.
Proposition B.6. p(A BK) 1, then the matrix θK,6 is invertible, and |0K,,ll2 S 4(1 +
|K 12)2 1 Also, miin (θx.)) ) 2 Ak. where Ax only depends on ||K]] and p(A - BK).
Proof. See
E.8 for a detailed proof.
By Proposition B.6 θx.6 invertible. Therefore, B.8) admits the unique solution ÇK.b
(J(K, b). k.b)
Now, we present the primal-dual gradient temporal difference algorithm.
Primal-Dual Gradient Method. Instead of solving B.8) directly, minimize the following loss function with respect to = ((<+) (C2)T
[ - JKK 6)]² + | (z, w))s² + 0K,05 Er [c(æ, (I)( u)]
(B.10)
By Fenchel's duality, the minimization of B.10 is equivalent to the following primal-dual min-max problem,
(BrK [1b(2, w)]s² + Ox - FT [e(2, u) wi]] $2
min max F(C.E)
(B.11)
ÇEV: EEVE
+ 1st ((K, -g- - -1E111/2,
19

---

Published as a conference paper at ICLR 2020
where we restrict the primal variable in compact set Vg and the dual variable & in compact set Ve, which are specified in Definition B.7 holds that
Ve c: F = =5- + E E [x(2, w)] 5² Vga fa = x (1, w) O 0x, E [o(2, u) w)b u)] -
F==== b) 5²
(B.12)
The primal-dual gradient method updates ç and & via
5' x 5 - ((,EE, + - -
(² 22 - (((=)(( + 2 - Ve=F(C,E)
(B.13)
Estimation of Mean-Field State JK To utilize the primal-dual gradient method in BB.13 remains to evaluate the feature vector (x u). Note that by (B.5), the evaluation of the feature vector (x, u) requires the mean-field state μK,b. In what follows, we establish the estimator jk, of the mean-field state μK, by simulating the MDP following the policy TKS for T steps, and calculate the estimated feature vector 5(x;, u) by
((x, u)
((z
PK, 11 - (- K TuK.b +b)
(B.14)
where G(x, u) takes the form of ((x, u) svec
(u [ (a-(--k KPK,b - -6) )
-- (1-[-KKAsi + +b))
uKo
I- uKb
We now define the sets V/e and V/3 in (B.1I).
Definition B.7. Given Ku and by such that p(A - BKx) 1 and J(Ko, bo) co, we define the sets V& and V/g as
V/ = c: ct s J(K, bo), 16 S Mc.1 + M3.2 (1 + |||]| p(--p(AA-A ( "}
"
VE = {s: |591 s J(Ko, bo), 1152 S Ms (1 + |
3 [1 - ((A BK)] BK]] }
Here Mc,1, Mc.2, and Me are constants independent of K and b, which take the forms of
Mc. [11Q]]= + [|/[]]=) (II + [[B] Vd J J[Ko, bo) miin (Va))
(11A112 + [[B]|2) J (Ko, 60)2 o o (w) Tm (Q),
+ [I1@1l2 + [[]|l) + (I|AIl2 2 + 11112)2² JKKo bo) o I [w))
J(Ko, bo) [-_.] (Q) + __ (R))
Mr.2 (1I-A]12 + [|B])2) (RQ + KR),
Mg C' (M3, + Mc.2) JKo, bo) - (Q),
where C' is positive absolute constant, and si and K are condition numbers of and R, respec- tively.
We summarize the primal-dual gradient temporal difference algorithm in Algorithm 3 Hereafter, for notational convenience, we denote by 24 the estimated feature vector (22,, 44).
We now characterize the rate of convergence of Algorithm 3
Theorem B.8 (Convergence of Algorithm 3. Given Ko, by. K, and b such that p( A and J(K,b) b) < J(Ko, bo). we define the sets V: and V& through Definition B.7 Let 7t
BK₂)
not 1/2 where 7 a positive absolute constant. Let p (p(A BK), 1).
For T >
p |1]] ||11 J J(Ko bo)) p) and sufficiently large T, it holds with probability
least 1 - -6 that
log T T1/2 (1 0)1 T1/4 (1 p)) +
TT
]
||@K,b - 0x,bll 1/2 < 2x² poly, (I |e, |b||2, |1 J( (K))
20

---

Published as a conference paper at ICLR 2020
Algorithm 3 Primal-Dual Gradient Temporal Difference Algorithm.
1: Input: Policy *,, mean-field state ns, numbers of iteration T and T, stepsizes (ethe parameters Ko and bn-
2: Define the sets Ve and Ve via Definition B.7 with Ko and bo-
3: Initialize the parameters by Ço E Ve and Ço E Vg.
4: Sample Zo from the the stationary distribution ([KK,, +x).
5: for 0, 7 do
6: Given the mean rean-fiield state μ. take action ū, following TK,6 and generate the next state T1+1-
7: end for
8: Set MKKbb < 1/T Ez= Iy and compute the estimated feature vector v via (.14).
9: Sample Zo from the the stationary distribution. N (uK,, xx).
10: for == ...... T
do
11: Given the mean- field state μ4, take action u, following T,, observe the cost c₁, and generate
the next state 2++1-
Set 6.+1 + Ç + (
T cz.
13:
Update parameters via
G G 7111 (c) + 4 Et)
Set Ge 7+1 Ve )et1) st.
6-1+ - (1- E 7+11 (5t -+),
241 (1-7+1) . +++1 det1 Vr.
14:
Project G++1 and be+1 to V& and V4, respectively.
end for
16: Set 0.b f- (E=n>) 71 (ET (2), and
ix +- smat((k
jK,b
āK,,2 - TK
PK,b -KiKs +b)
TK.b
where āK,6,1 = (āx,))) (*td+))))+ and @K,62 = (āKo)
(ktdd+)(kkdd)
17:
Output: Estimators PK Px. and (K.b-
where AR is defined in Proposition B.6 Same bounds for || Y l/ 11 pK.l2.. and
l@ā - 1 hold. Meanwhile, it holds with probability at least T that
log T
[7 - MKcoll2 &
(1 -1-p) 22- polyy (1 K[lr, [1b||2, 111412,, J(K. bo)).
71/1
Proof. See D.3 for detailed proof.
B.3 TEMPORAL DIFFERENCE POLICY EVALUATION ALGORITIM
Besides the primal-dual gradient temporal difference algorithm, we can also evaluate a,K by TD(O) method (Sutton and Barto 2018) in practice, which presented in Algorithm 4
Note that in related literature [Bhandari et al. 2018 Korda and La 2015), non-asymptotic conver-
gence analysis of TD(0) method with linear function approximation is only applied to discounted MDP. As for our ergodic setting, the convergence of TD(() method is only shown asymptotically (Borkar and Meyn 2000 Kushner and Yin 2003) using ordinary differential equation method.
Therefore, in the convergence theorem proposed in 3 we only focus on the primal-dual gradient temporal difference method (Algorithm 3) to establish nom-asymptotic convergence result.
C GENERAL FORMULATION
Compared with Problem 2.3 more general formulation includes additional term 2, Pu in the cost function. For the completeness of this paper, we define this general formulation here. Following from same argument in suffices to study the setting where is sufficiently large. First, propose the following general drifted LQR (general D-LQR) problem, which is parallel to Problem
2.2
21

---

Published as a conference paper at ICLR 2020
Algorithm 4 Temporal Difference Policy Evaluation Algorithm.
1: Input: Policy T,, number of iteration T and T, stepsizes (nher
2: Sample To from the stationary distribution N ((uK 2x).
3: for t= O....
do
4: Take action Ur under the policy TK, and generate the next state Tr+1+
5: end for
6: Set 7.K - 1/T
1
E/ Tr.
7: Sample 2o from the the stationary distribution (HK,, Øx).
8: for f - T do
9: Given the mean feean-ieeld state μs, take action u, following TK, observe the cost ct and generate
the next state 2++1-
10: Set dc+1 G + (8) 1442) +2
- ct. Update parameters via G + (1 - 741) G + 7411 a and G2+1 t- CP - -1++1 8.41 B.
12: Project Ee to V/2 where Ve is compact set.
13: end for
Set 0k
(EF-10)- (6) (Et, Tt- {?), and
Kx t smat (,,,,)..
pKb
+ 0,, - TK -KūKK +b)
TKK.6
QR.b
(k+d+))()+d)) where 0KK61 = ( (x+d++ and 0K, (āk,) 1(kkt))/2 15:
Output: Estimators 0K, Tg, and qK.b-
Problem C.1 (General D-LQR). For any given mean-field state E R", consider the following formulation
E++1 = Ax. + Bu, + Ap + d + Wt.
(st, uz) = x. Qu+ u, Ru, 11 Tuu++ 2xr PM.
(x(T) lim
Cx (1 u+)
T-+00
T
where E R is the state vector, E R is the action vector generated by the policy n,, wa E R an independent random noise term following the Gaussian distribution (O, V..), and d Rm a drift term. We aim to find an optimal policy n such that JT(TT) = infren JT((T..
In Problem C.1 the unique optimal policy mT(() still admits linear form T7 (ax)) - K x + dag
Anderson Moore 2007), where the matrix K2; E R and the vector dm; E R are the parameters the policy и. then suffices to find the optimal policy in the class defined in (2.1)
Parallel to Problem 2.3 we define the general LQ-MFG problem as follows.
Problem C.2 (General LQ-MFG). We consider the following formulation
Jt+1 = Axx + Bu, + Aµ + d Wt.
E(z,, u1) = = Qx, + u, Ru; + p T Qu + 2x, Pv.
J( lim E
T Σ
Exe, u.)
T-400
where 2, E Rdh is the state vector, Un E E is the action vector generated by the policy म. μ R" the mean-field state, E 1 is independent random noise term following the Gaussian distribution (0, Vw), and d gm is a drift term. We aim to find pair (4", ,")" such that (i) J(=*,p² = inf [T, )²);; (ii) Ex; converges to μ² + where {aī he20 is the Markov chain of states generated by the policy T.
One that Problem C.2 aims find Nash equilibrium pair (n² n²)
22

---

Published as a conference paper at ICLR 2020
Similar to the discussions in 3.2 to solve Problem C.2 one can design algorithm similar to Algorithm [ which solves Problem C.I and obtain the new mean-field state at each iteration. We omit the detailed algorithm here. Now, we focus on solving Problem C.1 in the sequel.
Similar to [3.3 we drop the subscript when we focus on Problem C.1 for a fixed μ. We write (x) Kx + + a to emphasize the dependence on K and b, and J(K, b) J(TK,)) consequently. We derive explicit form of the expected total cost J(K, b) in the following propo- sition.
Proposition C.3. The expected total cost J(K, b) in Problem C.1 is decomposed as
J(K,b) b) = (K) J2(K, b) + o² tr( + p Qu4
where (K) and J2(K, b) take the forms of
(K) tr[(Q + KJ RK) tr(Pk
(K,K)) (00 [KKbb]
Q + KRRK
-K R)
R)
(KK6b)
(bbb
24
PPK.--
-RK
R
Here jK, given (3.2). 4 k is given in (3.). and PK is given in 3.4.
Proof. The proof is similar to the one of Proposition B.2 Thus omit it here.
Compared with the form of J(K,b) given in (355). we see that the only difference is that J(K, b) contains an extra term 2p T PμK, 5 in J2 (K, b), which is only linear term (recall that Px, is linear in b by 3.2 Thus, J2(K, b) is still strongly convex in b, as shown in the proposition below.
Proposition C.4. Given any K, the function J2(K, b) is VK -t-oolyggly convex in b, here VK = miin (YT,x² X + K2 x2,x,, where Y1,K = R2 A BK) - R2/2 and 12,x
Q1/3(T + BK)- B. Also, J2(K, b) has xx Lipschht continuous gradient in where ix upper bounded such that I [1 p(A BK) BI) || |R] + | [1Q11.).
Proof. The proof is similar to the one of Proposition 3.3
Thus we omit it here.
Parallel Proposition 3.4 derive similar proposition the sequel.
Proposition C.5. Denote by T argmin, J2(K, K, b), then Jz(K, (K) takes the form
J2(K5bk)= (At+ PT
1)
S(I A)Q-1 (0-10--A1) A) 3Q- A) S(T - A)Q -
s
)
Ale d)
which is independent of K. Here S [[T A)Q II A)T + BR B And i takes the form
-1-A1---1100 j = [QQ A) R 'B S. [AA++ + d) + (1 - A)Q PT - -QQ
Proof. The proof is similar the one of Proposition 3.4 Thus we omit it here.
Similar to Problem 2.2 define the state- and oation-value functions
VK.a(T) =
(at, 4+) sop x, = Krt + b onl - (.
Qx u) a(,, m) J(K,b) (V(K,,(('')
where the is the state generated by the state transition after the state-action pair (I, u). A slight modification of Proposition B.T gives the proposition below.
23

---

Published as a conference paper at ICLR 2020
Proposition C.6. For Problem C.1 the state-value function VK,O(z) takes the form
Vk,((>)= Px (r(Pk&Pp (x) + 2f MK,b) (HKK)) PKMK.b.
and the action-value function (2, u) takes the form
QK,( =
1
TK K
PK,b (K.b)
I
(r(Pk(() - o2 PxBB) bb Rb
26 RKNKE (MK.)) (Q K K RK + PRIKKO + +2f (Ap d) -K,6]
(Apr + d) (Aç + d) 2/1 PμK,--
Here the matrix Tx is given in (377). and the vectors PK,b, qk.6 are given as
PK.h
[A (Au + d) - [Ko]] + Pp
B PK (Au + d) fK,0] )
(C.1)
9K.b)
where the vector FK. (1 (1- A BK) [(A BK) PR(Bb + Au d) K Rb PaJ.
Proof. The proof is similar to the one of Proposition B.1
Thus we omit it here.
Now establish the gradients of .((Kb) b) for Problem C.I
Proposition C.7. The gradient of (K) and the gradient of J2(K, w.r.t. takes the form
VKJ((K) 2 ) 4K.
VoJ2(K, b) = 2 ( + - KKKO + ēK,),
where the matrix Tr is given in 3.7 and the vector 9K,6 is given in C.I
Proof. The proof is similar to the one of Proposition B.3 Thus we omit it here.
Equipped with above results, parallel to the analysis in 33 is clear that by slight modification of Algorithms 0 and 3 we derive similar actor-critic algorithms to solve both Problem C.2 and Problem C.I where all the non-asymptotic convergence results hold. We omit the algorithms and the convergence results here.
D PROOFS OF THEOREMS
D.1 PROOF OF THEOREM
We define MC+1 A(us), which is the mean-field state generated by the optimal policy
(H=),,b A1(P,) under the current mean-field state pa By Proposition 3.4 the optimal
(()))) is independent of the mean-field state μ.. Therefore, we write K K (p) hereafter for notational convenience. By (3.2). we know that
M 1 = (I -T-A+ A+ BB*)1 (b+)) + Ap,, + dd).
We define
7s+ = (T- A BK,) (Bb. + Apts + d),
which is the mean-field state generated by the policy i, under the current mean-field state (4s, where K2 and b, are the parameters of the policy T.. By triangle inequality, we have
||
1² ||
||
Mot1lla
||
M4+1 1 llz
||
ll2.
(D.1)
Ea
Es
where Ps+1 is generated by Algorithm I
We upper bound E,. Eg, and Eg the sequel.
Upper Bound of Fj. By Theorem B.4 it holds with probability at least 10 that
E
||
Rstall2 < Es S//82
(D.2)
24

---

Published as a conference paper at ICLR 2020
where Ea is given in (42
Upper Bound of Ez. By the triangle inequality, we have
F₂ [[T A BK,) -1 (Bbs + Aps, + d) (T A+ BK*) [Bb Apss d)
< || + Aps + d||2" || [T- A BK* + B(K, - K-] (I- A BK*)
2
+ ||( A + BK,) 12 -|B1|2 -166- 6" b'(())ll2
(D.3)
By Taylor's expansion, we have
||| A+ BK + B(K, -1
= ||(7 (T- - BK [ A B(K, - K*]] (T- -K)
s 2 A BKK)) (T BK*)
(D.44
Meanwhile, by Taylor's expansion, it holds with probability at least 1 1 that
[| A+ BK, - 112
[I A BK + B(K, - KT))
[I A+ A+ BK") (I+ (I A+ BK-BBK""BBBBL - -K))) - -11,
< [1 [1- [1-p(A- (1--P(A-BBI BKT] - (1 || A+ BK BK |K" K 212
s 2
- p(A ( BK')
(D.5)
where the last inequality comes from Theorem B.4 By plugging D.4 and D.5 in D.3 it holds with probability at least 100 that
PB $ 2/ BB + Apss + d||2 ||(7 A + BK*) kT) A B
+11(1 - A + BK,) 1112 11, ||
||bg- - 6 bb())))l2
< 2| Bb (1s) + A/4. - d112 -01--(AA p(A - BK*)] -2
||B|22 - - K*1la
(D.6)
+2[1 - p(A - BK*] -2 ||B||2 |bb, - (1a))l2
By Proposition 3.4 it holds that
|| Bb (ua) + Aps + d S L B||| |/ 12 ||112 |1 + ||]||2
< (L1 |B||a ||A12)) || + ||d]|,
(D.7)
where the scalar L, defined in Assumption 3.1 probability least 1 10 that
Meanwhile, by Theorem B.4 it holds with
KK KK < [ (V.) omin (R)
e.)
|b. 6" (p=))l2 - Mo(p.) e//2,
(D.8)
where M)())) defined in
(43 Combining
D.6
D.7
D.8).
and the choice of e, in
holds with probability at least e10 that
Eg S 2
(D.9)
Upper Bound Eg. By Proposition 3.2 we have
Es ||
-²112 = | |p(p)) - A(p Lo llp, p² 12112,
(D.10)
where Lg = L1 + L2 by Assumption 3.1
By plugging DD.2
D.9 and DD100) in D.I. know that
||441 , ,0ll2 Lo llu. 1² 2
(D.11)
25

---

Published as a conference paper at ICLR 2020
which holds with probability at least - =00_ Following from (D.11) and union bound argument with S ([llog(//e)), holds with probability at least 1 E that
lus - 10112 - L I|mo p= 122 E/2,
where we use the fact that Lo < 1 by Assumption 3.1 By the choice of S in (4.1). it further holds with probability at least 5 that
l 1² S.
(D.12)
By Theorem B.4 and the choice Es
4.2 holds with probability least e that
[ |F |Ks K (us) I I [omia (.)) Tmin (R) Es]
1/2 S..
(D.13)
Meanwhile, by the triangle inequality and the choice of E, (4.2). holds with probability least 1 - 5 that
1bs - b'1l2 - |bs - bz (ps)
+ +110** (145) - b" 111
ES $ Ms(us)
1/2
+ L1 Ils
(1 L1) E,
(D.14)
B. B.4 and Proposition 3.4 and the last inequality comes from (.122). By (D.12). (D.13) and (D.4.. we conclude the proof of the theorem.
where the second inequality comes from Theorem
D.2 PROOF OF THEOREM B.4
Proof. We first show that (K,)) (KK) E/2 with a high probability, then show that J2(KN, J2(K", < 5/2 with a high probability. Then we have
J(KN, bx) J(K b*) = J. (Kx) + J2K,,, - J((K*) J2(K",
with a high probability, which proves Theorem B.4
Part 1.
We show that Jı(Kx) - Ji(K*) < e/2 with a high probability.
We first bound (i(K)) - (1(2 for any K₁ and K2. By Proposition B.2 Ji(K) takes the form of
(KK = tr(PP v.) = F.y.N Pku).
(D.15)
The following lemma calculates y² PK, y PK,y for any K₁ and Kg.
Lemma D.1. Assume that p(A - BK1) < 1 and p(A - BK2) < 1. For any state vector we
denote by {y/, h2o the sequence generated by the state transition 3/+1 = (A BK2) with initial state It holds that
y T PK.Y - PK,V= Σ Dk.. 120
where
DK, (v) = 2y (K2 K1 (T K, r2, 1
T(KK (K2 K1) T (K2 K1)y-
Here Tx is defined in 3.7
Proof. See E.1 for a detailed proof.
The following lemma shows that Jı JK) is gradient dominant.
Lemma D.2. Let K" be the optimal parameter and K be parameter such that (K(K) < co, then it holds that
(K) Ji(K*) < ml
(R) 1|
r
(D.16)
JKK (KK) 2 omin (w)) || -
K
(D.17)
26

---

Published as a conference paper at ICLR 2020
Proof. See F2 for a detailed proof.
Recall that from Algorithm 2 the parameter K is updated via
Kn+1 = Kn Y (T Kn Kn - T ),
(D.18)
where Tk. is the output of Algorithm
We upper bound [J1(K - (K*) in the sequel.
First, we show that if Ji (Kn) Ji (KKK*)
e/2 holds for any N, we obtain that
(1 - J1(KN-1) S ... S (Koo),
(D.19)
which holds with probability at least 1 e03 We prove D.19) by mathematical induction. Suppose that
J(KK) S (1 S... s... 5.. (K())
(D.20)
which holds for 0. In what follows, we define Ka+1 as
Knti = Knn -- ( Rn Kn - r
(D.21)
where Tk. is given in (3.7 7. By D.2Ij, we have
Ji (Kn+1) - Ji(K,) = By--((...)) (P (Phts Knt1 -PK,)
22 2 Knni
(T Kn -T T Kn Kn, [x
+ tr ku+i
(I K, -T T TT (T Kn - -
< 22 ur( 1 Rn+i
(T Kn Kn - -r,,) ) T (T
Kn Kn [x.) )]
(D.22)
+~² | 22 K.
||e
tr R.+1 1 K Kn - T K. ) (T Kr Kn - -
where the first equality comes from (D.5)) the second equality comes from Lemma D.I and the last inequality comes from the trace inequality. By the definition of Y T in (3.7), we obtain that
|| | ll < || + | PK, ll2 = || [|]] + |B J1 (Kn) o (V.)
< || + | J. (Ko) o (V.),
(D.23)
where the second inequality comes from Proposition B.2 By plugging (D.23) and the choice of stepsize 7 S R||2 + |B Ju (Ko)
a (V.))
into (.22). we obtain that
Jn J. (K,) S -7 tr K, (T K. Kn Tx K..) ) (T K, T2.
< -y min (V,) tr (T K_ Kn Tk, K..) J
Ka Kn - -n-rk,))
S - amin (V.) miin (R) 1000)1100000 110 - ( < <0, (D.24)
where the last inequality comes from Lemma D.2
The following lemma upper bounds [J (KK+1) Jn (1Kx++))
Lemma D.3. Assume that J1 (Kn) I J1 (Ko). It holds with probability at least - 515 that
[T( - J1 (K S omin(( (W,)-oo -.ii (R)
1| 1 -.ae-l11--//// =/4,
where Kn+1 and Kn+1 are defined in D.18 and D.21 respectively.
Proof. See F3 for a detailed proof.
Combining D.24 and Lemma D.3 (Knn) - (K(K) 2 e/2, holds with probability at least
1 15 that
Jr (K(() S J1 [ (K - (KKK)
+ [T n+ (1(+1))
S - muin (V.) Fmin (R) T 11x--11 e/4 0.
(D.25)
27

---

Published as a conference paper at ICLR 2020
Combining (D.20) and (D25). it holds with probability at least 1 - = that
Ji(Kn+1) Ji(Kn) S .... S J1 (Ko).
Finally, following from a union bound argument and the choice of N in Theorem B.4 if (K,) (1KK)) 2 E/2 holds for any n S N, we have
(Kx) S J1(KN-1) S Ji(u),
which holds with probability at least 1 - 1 Thus, we complete the proof of D.19)
Combining DD24 and D.25 for J1 (K,) JI(K 8/2, have
(1))) ((K)) - [1 7 min (V.) ) min (R) f| k- ||='] [J,, J [K*)],
which holds with probability at least - e Meanwhile, following from union bound argument and the choice of N in Theorem B.4 it holds with probability at least e!l that
J1 J( ([KK)-JJ(K))) J2(KK) S e/2.
(D.26)
The following lemma upper bounds |N [= Lemma D.4. For any K, we have
|
K |p S min (W.) o miin (H)) (JI((](KK))))))) - (1(K))
Proof. See F.4 for detailed proof.
Combining D.26 and Lemma D.4 we have
|N K" K*IlF S [omin (v.)) omin (R) =//2] 1/2
(D.27)
which holds with probability 1 =-=l_
Part 2. We show that J2(KNN by) J2(K",b') < E/2 with high probability. Following from Proposition 3.4 it holds that J2(K", "KK,,," b²) = J2 Kx). Therefore, it suffices to show that J2(K n. by) J2(KN. (Kw) < E/2.
First, we show that if J2(K N, bn) - J2(KN. bkx) 2 2/2 for any h < H, we obtain that J2(KN, bz) & J2(KN bH-1) S ... & J2(KN, b1) < J,(KN,bu bo).
(D.28)
which holds with probability least e13 We prove D.28 by mathematical induction. Suppose that
J2 bn) & J2(KN. bn $ ... & J2(KN, ((K,,bb) bo).
(D.29)
Recall that by Algorithm the parameter is updated via
bh+1 bn - 7² VzJ2(KN,bi) ba).
(D.30)
Here
Volz(KN,bn) = T22 (-KNāKx... + bn) + T KN Pux. + TKrius
(D.31)
where TKv and @ are the outputs of Algorithm We define ba+1 as bnt1 = by 7. VoJ2(KN,bb)) bn).
(D.32)
Here
VoJ2 bn.
T2 (- KNPKw.b, + bb) + T x M + NKn
(D.33)
where Tky and vKv.b, vb.. are defined in (.7 We upper bound (2(NN bb+1) J2(KN, kv) in the
sequel. Following from (D.32) and Proposition 3.3 have
J2(KN, bb+1) J2(KN. N. bn)
/2 VoJ2(KN, bn))112
S - VKN 7 (KN, J,K,Nbb by) J2( bKx]]
< -KKK 7 <00, 0,
(D.34)
where VKN is specified in Proposition 3.3 The following lemma upper bounds JJ2(KN bnt1)
J2 b.41)..
28

---

Published as a conference paper at ICLR 2020
Lemma D.5. Assume that J2(KN. by.) 1 J2(KN, bu). It holds with probability at least - g/6 that J2 bn+1) - J2(KN, bn+1)) VKN
5/2, e//2
where b and b are defined in (D300) and (D.32) respectively.
Proof. See E.3 for a detailed proof.
Combining D.34 and Lemma D.5 we know that if J2(KN, bn)) 12(KN,bfe 2 it holds with probability at least 1 5 that
J2(KNN b(41) 22(KN bn)) S J2 b1) J2(K N. bn.) + J2((NN, bl+1) J2( (KNN ba+1)l
-PKy .7 E/2 <.
(D.35)
Combining (.29 and D.35 it holds with probability at least 1 - E that
J2(KN, bb+1) S J2(KN, bb.) S N2(KN,,0)) bo).
Following from a union bound argument and the choice of H in Theorem B.4 J2(KN,,b) bn) J2(KN, bk) holds for any h S H. have J2 bR) - J2(K b ... J2(KN..b) bo).
which holds with probability least 1 - _. Thus, we finish the proof of (D.28).
Combining (D.34) and Lemma D.5 for J2(KN, bn) J2(KN, &x) e/2, we have
Jz N b1) J2 KN b Kw) ) s (1 vK* 77)) [32(Kx bn.) 12(KN (K,, bK))]
which holds with probability at least 1 - 1l3 Meanwhile, following from union bound argument and the choice of H in Theorem B.4 it holds with probability at least ell that
Jz (NNNbbn) J2(KN, bK)) S s//2.
(D.36)
By Proposition 3.3 and (D36)) it holds with probability at least - ell that |b 8Kx 1| S (2e/ux.)
(D.37)
Following from Proposition 3.4 know that
Kk - b' (KN KI)Q-=(1- A)T
(D.38)
(1 - A)Q AI + BR-BBB (Au + d).
Combining (D.77).
D.37 and (D.88). holds with probability 1 e0 that
|لb - KK 1|2 I My et/2,
where
Mo(1) Q- T)T - A) + BB- (Au + d)
[ - (V.) m (R))
We finish the proof of the theorem.
D.3 PROOF OF THEOREM B.8
Proof. We follow the proof of Theorem 4.2 in Yang al. (2019). where they only consider LQR without drift terms. Since our proof requires much more delicate analysis, we present it here.
Part 1. denote by 2 and f the primal and dual variables generated by Algorithm the primal-dual gap of (B.IT
We define
gap
( max F(G,E)
min F(C.E).
(D.39)
EEVE
SEVC
29

---

Published as a conference paper at ICLR 2020
In the sequel, upper bound |āx,6 ax,ol2 using (D.39).
We define (K,b and E(C) as
CK.6 = (J(K,b),
E(C) = argmax E).
(D.40)
Following from (B.12 we know that
<²(c) b),
((K,)), 6), The following lemma shows that ÇK.6 E Vę and E(C) E Vg for any Ç E Vç-
(C = J
ExK [1 w)]s' 0K, Eux Ld, (D.41)
Lemma D.6. Under the assumptions in Theorem B.8 it holds that ÇK,6 (J(K, ak, e Vc- Also, for any Ç Vc, the vector E(C) defined in (D.40 satisfies that E(C) E Vę-
Proof. See F.6 for a detailed proof.
By (..12). we know that Ve VeF(CK,,, 0) = 0 and VgF((K,b 0) 0. Combining Lemma D.6 holds that (CK,s, 0) is saddle point of the function F(. {) defined in (B.11)
Following from DD399, it holds that
B [v, + Ox, - EM [o(x, u)b w)] 11= +
=F(G,E(() = max F(G.E) gap(C. + min F(S. E), EEVE
(D.42)
CEV:
where the first equality comes from (D.41) and the second equality comes from the fact that E(C) =
argmaxgev, F(C, 5) by (D.40) and Lemma D.6 We upper bound the RHS of (D.22) and lower bound the LHS of (D.22) in the sequel.
As for the RHS of D.42) holds for any & E V/ that
min F(C,E) CEV:
S min max F(S,E) min F(5.(()) CEV:
CEV: eEV:
1 min {
[|Erxs [vt u)] + OK, - ET [c(z, u)b(a, w|]l + =152-J(KK J(K, b)|²
2 SEVE
= 0,
(D.43)
where the first equality comes from the fact that E(C) = argmaxçev; F(C. <) by (D.40) and Lemma
D.6 the second equality comes from (D.4T), and the last equality holds by taking < = CK.D E Vç- Meanwhile, we lower bound the LHS of (D42) as
E B [v(2, w)] 0x - -ETKA [o(I, u)v(z w) w - -
-kx:((-<<a)]13 A 1
6x -x,,61
Xx | x
(D.44)
where the first equality comes from the definition of θ from Proposition B.6 Here Ax is defined in Proposition B.6 Combining (D.22). (D.43) and (D.44). holds that
& in B.9. and the first inequality comes
|| ax,ll Ax² gap((.
(D.45)
which finishes the proof of this part.
Part 2. We now upper bound gap(C, 2 We denote by 2ة (म. ",," fort E [T], where T, and ü are generated in Line Algorithm 3 Following from the state transition in Problem 2.3 and the form of the linear policy, { (e(7)) follows the following transition,
2+1
LE, + 5z,
(D.46)
30

---

Published as a conference paper at ICLR 2020
where
Ap+ - - K (Ay d) b)
81
(-Kw
Wt
==
A B -KB)
-KA
Note that we have
B -KB)
)
L -KA KA
( (A B).
Then by the property of spectral radius, it holds that
pL) = =((11 (A B)
(-xx)
[ (-k)) p(A - BK) <
Thus, the Markov chain generated by (D.46) admits a unique stationary distribution WW,, Ex), where
N4 = (1- E. LE (-KV_
V K +
K.
(D.47)
The following lemma characterizes the average
f
N2 1/T Zt.
(D.48)
1=1
Lemma D.7. It holds that
D2 ~ N 1zz = 5
where || s Mp (1 (1- p)-2 are positive absolute constants. Moreover, holds with probability at least 7-6 that
Here M, and My 2, || and || || S Mr (1 p1 ||
log T
1i= M=lla S T1/1 (1 -1-10 p) p)- poooooyy x12 KKlr, [1+||2, ||xl|2)-
Proof. See E.7 for a detailed proof.
Lemma D.7 gives that
log T
goly(1|<<1l,, || ||,, 11b|l2, I1wl(2). || - |K,6ll2 S 71/1 (1 p1-
which holds with probability at least 1 7-
We now apply a truncation argument to show that gap( 3) is upper bounded. We define the event in the sequel. Following from Lemma D.7 it holds for any N N( Σ.) that
= P. + 1/T u7 ~ N(O, E, 1/7 Ex).
By Lemma G.3 there exists a positive absolute constant Co such that
Tre
12 tr(
(. > < 2exp
[- - min + -1)==11"))
(D.49)
where we write E. + 1/T Σn for notational convenience. By taking in (D.49) for a sufficiently large positive absolute constant C₁, it holds that
Ci log T ||E,1F
f|l12- - n. 1// 17 u{{E)) > C1 log T -1||E=11e 11r We define the event E,, for any / [T]
T
(D.50)
E11 = f11=f112e pa. + 1/f 12 -(SE)) < C1 log T. (1.1le)
31

---

Published as a conference paper at ICLR 2020
Then by (D.50), it holds for any t [T] that
P(E 2 1 1 T
(D.51)
Also, we define
E = n E1,1-
(D.52)
16|2]
Following from a union bound argument and (D.51). it holds that
P(E1) 2 1 - T
(D.53)
Also, conditioning on E it holds for sufficiently large T that
max AE(T]
||
< C1- log T' o(S)) 11
< 20 [1 Ms(1 - /79 log T ||_=|12 M,(1-p) 2//2//2 -1
< C2 log T (1 || -|
2l2 (1 p) + Css (11612 + [l (1 p) -4 T
$ 202 log T (1 + ||]]] -
x101
pp
(D.54)
where G, C2 and C3 positive absolute constants. Here, the first inequality comes from the definition of & in (D.52), the second inequality comes from Lemma D.7 and the third inequality
comes from D.47) Also, define the following event
& {1l Mz 1/T Holl2 C.
(D.55)
Then by Lemma D.7 we know that
(( 2 2
(D.56)
for T sufficiently large. We define the event as
E E n E2.
Then following from DD53 D.56
and union bound argument, know that
P(EE) 2 1 1-1--55 -
Now, define the truncated feature vector (1x (Fx, u) a( u) 1 the truncated cost function 2(2, u) as E(æ, u) c(x, u) ll and also the truncated objective function F(C, as
F(C. E) [(()(*+ + E [ 3 No | B(e)) e² + [c E[a] g- - 11E11//2 (D.57)
where we write v = (x, u) and ē = ट(æ, u) for notational convenience. Here the expectation taken following the policy TK,s and the state transition. The following lemma establishes the upper bound of (F(( F(C. where F(C,E) and F(C.E) are defined in (B.II) and (D57).
respectively.
Lemma D.8. It holds with probability at least 7 that
1
log
IF(C.E)-((C.. - F(),E) <
(1 - p2- poly(I| 116ll Mllll, ((Ko bo)).
2T
71/4
Proof. See F.8 for a detailed proof.
Following from D.39) and Lemma D.8 it holds with probability at least T that gap C. ga. )
1
log 7
(1 -2 poly([| |||||, |1 J(Ko,
(D.58)
2T
T1/4
32

---

Published as a conference paper at ICLR 2020
where we define g)
gap (ap(S,E) = max E(S,E) min F(S. 5).
&EV2
<EV:
Therefore, to upper bound of gap(S, we only need to upper bound gap(s.
Part We upper bound gap(s: 5) in the sequel. We first show that the trajectory generated by the policy TK,6 and the state transition in Problem 2.2 3-mixing.
Lemma D.9. Consider linear system Ut-1 = Dye + 0 + th, where {y:)120 C R the matrix D |2x satisfying p(D) 1, the vector & 12m and vs -N 2 the Gaussians. We denote by 5a the marginal distribution of for any 2 0. Meanwhile, assume that the stationary distribution of {ye 1220 a Gaussian distribution A D)-1a, Exe), where Eoo is the covariance matrix. We define the 3-mixing coefficients for any 2 as follows
((n) sup Byww, 120
|| (-1 -o
Then, for any E (p(D), 1), the B-mixing coefficients satisfy that
(mn) C..D. [ir(2>>)) + m mm-(1- (1- (1-
where D,D a is a constant, which only depends on p. D, and 1) We say that the sequence fur is 3-mixing with parameter p.
Proof. See Proposition 3.1 in Tu and Recht (2017) for details.
Recall that by 3.1 the sequence {xt 1220 follows
1t+1 (A BK)a, + (Bb + Ap d) + Et.
6, ~~,00 M.),
where the matrix A BK satisfies that p(A BK) < 1. Therefore, by Lemma D.9 the sequence {zehe20 is 8-mixing with parameter p E (p(A - BK), 1). where 2; (=) 24 The following lemma upper bounds the primal-dual gap for convex-concave problem.
Lemma D.10. Let X and y be two compact and convex sets such that | x' 211 s M and lly y' 1|2 S
M for any x, x' E X' and y, y' E y. We consider solving the following minimax problem
min max (xx,y) Ra [G (;)),, ZE vEy
where the objective function H(r, v) is convex in æ and concave in y. In addition, assume that the distribution w. is B-mixing with (n) < C..p", where C, is constant. Meanwhile, we assume that it holds almost surely that G(æ, yi e) is Lo-Lipschitz in both and y. the gradient V,G(z, yi E) is T, Lipschit in for any y V, the gradient V, yi is LipLipschitz in y for any X, where Ce, Lo, L > 1. Each step of our gradient- based method takes the following forms,
r++1 = x [ox 7 Va Ga Vat( (t),
Me+1 = T [v+ - 7++1 VyG(E,, ve:
where the operators Ex and Ty projects the variables back to X' and V, respectively, and the stepsizes take the form % = "o t 1/2 1/2 for a constant To > 0. Moreover, let = (E - yeD+) and 7 1 -> Te.ee) be the final output of the gradi- method after T iterations, then there exists positive absolute constant C, such that for any 5 E (0, 1), the primal-dual gap to the minimax problem is upper bounded as
7))
C (M² + Σ3 + LoLLM) log T + log(1/6) + C. C.L.M log(1/p)
max H y) - min H(x < zEA
yEY
VT
T
which holds with probability at least 1 5.
Proof. See Theorem 5.4 in Yang al. (2019) for details.
33

---

Published as a conference paper at ICLR 2020
To use Lemma D.10 we define the function G(G. 20))
G(S.E:15 ) [0ct + (e) 1 5- + 1/2 11E112.
where vे- == u) and T = "0',, Note that the gradients of GiS, र5, x take the form
T² +g' (の 3 T2)
( 5² --
V.G(S,E),))))
VEG(G,EN,,)) = (55)) + (0 V 52 - 5
By Definition B.7 and Lemma D.6 know that
VV 1 1 poly(I) J(Ko bu)) log" T (1 p)
VEG(S, w) poly( [|][]] |lal|2 (Ko, bo)) log 2 T [. -p) -p)
(D.59)
This gives the Lipschitz constant Lo in Lemma D.10 for C(S,E:0) vi v.)))) 8¹). Also, the Hessians of G(S. E: 1, T take the forms of
G) =0,
C, = --1,
which follows that
& G(G.G
G(G.E 10112 =
(D.60)
This gives the Lipschitz constant L, in Lemma D.10 for V.G(G, E: ". v and V V.G(S v Moreover, note that (D.54) provides an upper bound of M, combining (D559 D.60 and Lemma D.10 it holds with probability least 1 7 that
poly [r, ||l|2, J D,, bo)) log 9
gap(C, <
(D.61)
(1 p) VT
Combining DD45). D.58
and D.61), we know that
log 6 T
log T
||0,,6 a..b S Ax² poly, (|| le. [|bll,, ||lll22. J [[Ko bu))
T1/ (1 - p)*
T1/4 (1 p)
Same bounds for | - Tx lPpK0 - PK.ll.. and ||āK,b -K. hold. We finish the proof of the theorem.
E PROOFS OF PROPOSITIONS
E. PROOF OF PROPOSITION 3.2
Proof. We follow a similar proof as in the one of Theorem 1.1 in [Sznitmann (1991) and Theorem 3.2 in Bensoussan al. (2016). Note that for any policy πKK 6 E II, the parameters K and uniquely determine the policy. We define the following metric on II.
Definition E. For any TK TK2 E II, we define the following metric,
| Tr lla |
K2lla 02 ||bb ball2,
where and are positive constants.
One can verify that Definition E. satisfies the requirement of being a metric. We first evaluate the forms of the operators A, (+) and A2(:.))
Forms of the operators Ar (-) and A2(:,-). By the definition of Ai (n), which gives the optimal policy under the mean-field state it holds that
A1(p) = T
where T" solves Problem 2.2 This gives the form of (-).) We now turn to A2 TT, which gives the mean-field state fnew generated by the policy a under the current mean-field state p. In Problem
34

---

Published as a conference paper at ICLR 2020
2.2 the sequence of states fze) constitutes Markov chain, which admits unique stationary distribution. Thus, by the state transition in Problem 2.2 and the form of the Gaaes-an policy, have
Mnew = (A - BK+ Unew + (Bbx + Ap + d),
(E.1)
where Kr and bx are parameters of the policy π. By solving E. for Mnew, it holds that
(2 Mnew
A+ BKa) (Bbr + Ap d).
This gives the form of A-(:)).
Next, we compute the Lipschitz constants for A1(-) and A2(+.))
Lipschitz constant for (-). By Proposition 3.4 for any 14, 122 E Rmm the optimal K fixed for Problem 2.2 Therefore, by the form of the optimal 6k given in Proposition 3.4 it holds that
||A((e)) - (12))l S c2
[(T - A)Q - A) + +BR B
[K-Q (T--)" R RR
A)
|| /2/12
02 |lli u2l12,
(E.2)
where L1 defined in Assumption
Lipschitz constants for A2(,, -). By Proposition 3.4 for any μli U2 E R", the optimal K is fixed for Problem 2.2 Thus, for any II such that optimal policy under some μ RM it holds that
| 12(u2, =|( A+ BK2)
-1. A ( 122)l22
< [1 - [1--((A BK) ||Al|2 | - 222122
L2 | H2l12:
(E.3)
where L2 defined in Assumption 3.1 and K2 = K is the parameter of the policy n. Meanwhile, for any mean-field state μ E R and any poicies 11 22 II that are optimal under some mean-field states (4i, respectively, we have
A mI) A2(U,
||(1 A ((K)=++K*)--B (bx, - bxa))l2
[1 p(1 BK*) -1 11 |lb.n b ll2
= c La ||| 12112:
(E.4)
where in the last equality, we use the fact that Kx, Kr K by Proposition 3.4 Here La is defined in Assumption 3.1 and bn, and byg are the parameters of the policies Tı and m2.
Now we show that the operator A(-) is contraction. For any μ1, f22 E R"" , holds that
(A())) M12)ll2 211
22 ( (1
< A2 Ar - Ao(mI, (/ +//0 As A1
3 c Los A (12)) 1 Le 1I uzllz
3 La cabl || - 22ll2 + L2 || - 1 LL + L2) 111111111 P2l12,
where the first inequality comes from triangle inequality, the second inequality comes from E.3 and (E.4). and the last inequality comes from (..2). By Assumption 3.I we know that Lo L3 L2 < 1, which shows that the operator A(.) is contraction. Moreover, by Banach fixed-
point theorem, we obtain that A(-) has a unique fixed point, which gives the unique equilibrium pair of Problem 2.3 We finish the proof of the proposition.
35

---

Published as a conference paper at ICLR 2020
E.2 PROOF OF PROPOSITION 3.4
Proof. By the definition of (2,, b) in (36) and the definition of μKR66 in 3.2 the problem
min J2(K, 6)
equivalent the following constrained problem.
(
Q + K RK
-K R
11
min
RK
R
s.t. (I (I- A BK)μ (Bb + Ap + d) = 0.
(E.S)
Following from the KKT conditions of (E.5). it holds that
2MK
+ NKA=
NK
11 (
+ Ap + =d=0,
(E.6)
where
Q + TTKRRK RK
-KTR)
A+ BK)
)
MK
NK
-RK
R
B
By solving (E.6). the minimizer of
E..
takes the form of
[KK.MM bx
N M NK) (Ap + d).
(E.7)
bk
By substituting E.7 into the definition of (2 b) in (36 have
J2(K, (KK,
(Ap d) (N M NK) -1 AA + d).
(E.8)
Meanwhile, by calculation, we have
Q-1 KQQ' KQ- 1--KKT + R-1
M
Therefore, the term NI M
Nx in E. takes the form of
K
N K M NK (I - AI- AT) BR-
(E.9)
By plugging E.9 into
E.8
we have
J2(K, bk)
(Ap + d) [ AIQ (1- (I- BR BB (Ap
(Au + +d).
Also, by plugging E..9 into (E.7.. we have
(KK = ( KQ- - A)T (KQ--0-XP RT AJQ '1 A) BR B | '(Au + d).
(T A)T
bk
We finish the proof of the proposition.
E.3 PROOF OF PROPOSITION B.2
Proof. By the definition of the cost function c(x, u) in Problem 2.2 (recall that we drop the subscript j when we focus Problem 2.2), have
Ec;
E(z] Qz, + u, Rug + μ Q1)
E(x] Qx, 2. KT RKx, 26 TRRK + Rb ozn Rn: + P Qu)
[1 (Q + KJ RK)x,- - -26 [bTRK, + 6T Rb+ 0² tr(R) + 4 TTp,
(E.10)
where write G c( u.) for notational convenience. Here in the second line
(K)( = - Kxx; + b+ om. Therefore, combining (E.10) and the definition of J(K, 6) in Problem
2.2
we have
1 T
J(K,b) lim
E (Q + K RK) 26 26 RKx,] + Rb + 0² .t(R)) + Qu
T-000
1=
=Ex-N(mMAOx)) (Q+K K R RKK + Rb 0² tr(R) p Qu
=tr[(Q + KT RK)0K] + + + K (RR) - 2h RKPKb
(E.11)
+T Rb 0² ur(
R) + Tu.
36

---

Published as a conference paper at ICLR 2020
Now, by iteratively applying (3.3) and 3.4). we have
tr (Q + K RK RK) = =t v.).
(E.12)
where Px is given in 3.4 Combining
[C. and E. we know that
J(K, b) - Ji(K J2(K, b) tr(lt) + P Qus
where
J1(K) = +r((0+++ KJ RK]ØK] (P(..
J2( (KKA))
K -K -0 -RK
[KKbb
RK
R
We finish the proof of the proposition.
E.4 PROOF PROPOSITION 3.3
Proof. By calculating the Hessian matrix of J2(K, b), we have
(2,, =B (I + BK) (Q (Q KJ RK)(I - A+ -KB
- [RK(1 A BK) B A+ BK) -T K' TT R] + R
-[ - BK) BB [R1/2K(1 A BK) - RR/2
+ B (I - A+ BK) A BK)-IB,
which is a positive definite matrix independent of b. We denote by its minimum singular value as VK. Also, note that // //2 (K, 6)1l2 is upper bounded as
V J2K, 1)]l2 - [1 P(A - BK) -2
(I | || + |BI| 1Q112).
Therefore, holds that
LK S ((A A - BK) -
(1 ||K1| |R]|| + B 11
where ix is the maximum singular value of 22 (,b), b). We finish the proof of the proposition.
E.5 PROOF OF PROPOSITION B.3
Proof. Following from Proposition B.2 it holds that
J1 (K) V.) E0 v.y Pky) By~w(o. [fx
(E.13)
where (N) = y Pky. By the definition Px in 3.4.. we obtain that
(K]K(1) Vx (Q + KT RK) + [[A BK)B] Pk - [ }
2RK T + V fx((A- BK)y]
(E.14)
Also, we have
V ((A BK)) = VKfk (AA 2B Px BK)yu
(E.15)
By plugging (E.15) into [E.14). we have
(z) = 2 (R B B) B PK vy VKSx((A- BK)y).
PxA
(E.16)
By iteratively applying 16) holds that
VKfK(y) =x
PT BTBBBB PKA] Σ Bov.
(E.17)
1=
where Met1 = (A- BK)y; with yo = y. Now, combining E.13) and E.17
holds that
(K) = 2[ T Px - B PRA] = 2(T K T
4x,
where Yx is defined 3.7 Meanwhile, combining the form of PK,s in 3.2 holds by calcula- tion that
Vod2( b) = 2 (- + + uK. + qk.b],
where gK is defined in 3.7 We finish the proof of the proposition.
37

---

Published as a conference paper at ICLR 2020
E.6 PROOF OF PROPOSITION B.1
Proof. From the definition of VK,((0) in B.1 and the definition of the cost function c(2, u) in Problem 2.2 it holds that
Vko(o))=
[ B D (Q+ K RK)x, R...
1=
b Pbb + oani Ro "u' xo =] J((KK))
Combining 3.1g we know that Vx)((z) is a quadratic function taking the form of VK,(=)) = x GI + + h. where G, and h are functions of K and b. Note that VK,((T) satisfies that
(K,((x) = ciz, - Kr + b) J(K b) + [V,,(<²)|
(E.18)
by substituting the form of c(a, kx+bb in Problem 2.2 and J J(K,b) in 3.5 into E. that
obtain
x Gx + +r
=x KJ RK) 26 RKv Rbb Qu
(E.19)
-|ur(Px v.) + kk.b (Q + -TT (K - 2bb RKKKK P Qup + bT bTRb))
+ ((AA - BK) + (Bb + Au + d) ([(A-BK) + (Bb + Au + d)]
+ tr(GW) + r [(A - -BK)2 + (Bb + Ap + d)) + h 0² -r(R).
By comparing the quadratic terms and linear terms on both the LHS and RHS in E.19 that
obtain
G = P
r r= 2fk
PK (Bb (Bb+Ap+ol K Rb). Also, by the definition of (x) in [B.I. we know that E[VK,o(z)] = 0, where the expectation is taken following the stationary distribution generated by the policy πHZ and the state transition. Therefore, have
where fK.6 AI-
h == -ffKkbKK uk PKKPRKK. u(Px(k))
which shows that
VK,(#)= = x Pxx - ((( + 25k uk,) - P PRUKE.
(E.20)
For the action-value function QK, u), by plugging E.20
into B.2 we obtain that
Qx.(xx, =
Yk
+2
PKb
tr( (x(p - o² ir(R + PxBB
i1
9K.6
11
b Rb + 25 RK
P + K RK PK)NKD
+ 2f [(A + d) uK.D) + (Ap + d) PK P
We finish the proof of the proposition.
E.7 PROOF OF PROPOSITION B.5
Proof. By Proposition B. holds that QK. takes the following linear form
QK,( u) = (x u) aaK 3K,. where 3K is scalar independent of x and u. Note that QK,(I,, u) satisfies that
(E.21)
QK.6 u) = c(æ, u) - JK, b) + Ex [QK,(='' u') x u). where (a', (e',") is the state-action pair after (xr, u) following the policy TH. and the state transition. Combining EE.1 and (E.22), we obtain that
(E.22)
(1 u) aK. c(2, u) J(K b) + Ex [2b(2', ,'' x2, (z,ui u] aKd.
(E.23)
38

---

Published as a conference paper at ICLR 2020
By left multiplying (z u) to both sides of (E.23). and taking the expectation, we have
EaKa { {b(2,, (1)(2, u) (<x', u²)] } axo + BaK [1, J(K, b) Ex [e(e, ())((, 2)].
Combining the definition of the matrix Ox in B.7 we have
(BnRs 1
J(KKb)
J(K,b) BAKC [c(x, u), u))
BEKK [v(x, w)] which concludes the proof of the proposition.
O.Kbb
E.8 PROOF OF PROPOSITION B.6
Proof. Invertibility and Upper Bound. We denote by 2t (xx uu.) for any t 2 0. Then following from the state transition and the policy TK,. the transition of ( takes the form of
2++1 Le + V ōi,
(E.24)
where L, v and are defined as
B L KA -KB)
Au + d K (Aμ + d) +)),
6, ( tomm
Wt
Kwr
Note that L also takes the form of
L -K (A B).
Combining the fact that p(UV) PVVU) for any matrices U and V, know that p(L) p(A
BK) < 1, which verifies the stability of (E.24). Following from the stability of (E.24). we know that the Markov chain generated by (E.24) admits a unique stationary distribution N (pz, Eg). where uz and Σg satisfy that
11= Lpk +M
Vs.
where
V -K
V.KT KYCK +021
v
Also, we know that Dg takes the form of
( 11
(-
4K KOR
KKK
+021) ( )
+ (-xx) $
-
Σ. = Cov
K
(E.25)
where &x is defined in
3.3
The following lemma establishes the form of 0g.b-
Lemma E.2. The matrix θK, B.7 takes the form of
2 8. E.)(1 - L & L)T
K
Ee(1 -
Proof. See R.9 for a detailed proof.
Note that since p(L) < 1, both 1 - L 8. L and 7 L are positive definite. Therefore, by Lemma the matrix θ Kg is invertible. This finishes the proof of the invertibility of θ K.s. Moreover, by and Lemma E.2 upper bound the spectral norm of θ
E.2
E. 25
10x,olla max
|| (1 [111)). ||E2|2 (1 + [1[112)] s 4(1 K || 12
which proves the upper bound of | 12,2
39

---

Published as a conference paper at ICLR 2020
Minimum singular value.
To lower bound m (O,,), we only need to upper bound mmxx (+))) = k/o/ll.. We first calculate Qg.- Recall that the matrix K, in (B.8) takes the form of
+ KK
( [1b( u)
By the definition of the feature vector (xx, u) in B.. the vector ōN = ExKollb(,, u)] takes the form of
(svee(( [
0. = E (1,, w)]
0 Ok+m
where Ok- denotes the all-zero column vector with dimension k m. Also, since ②x is invert- ible, the matrix K, also invertible, whose inverse takes the form of
1 θxO Kgb (-Oxl Kib J. OK.b)
The following lemma upper bounds the spectral norm of 3 K,b' Lemma E.3. The spectral norm of the matrix @R is upper bounded by positive constant Ax. where dx only depends on K 2| and p(A BK).
Proof. See F.10 for detailed proof.
By Lemma E.3 we know that mmin (Onin(nm (OK,s) ) is lower bounded by a positive constant Ax 1/AK. which only depends on || and p(A BK). This concludes the proof of the proposition.
F PROOFS OF LEMMAS
F.1 PROOF OF LEMMA D.I
Proof. Following from 3.4. it holds that
y PK.
[[A BK2) (Q + K. (A BK2)
(F.1)
Mcanwhile, by the state transition yt+1 (A- BK2) we know that
= (A - 3K2)' yo = (A BK2)'y.
(F2)
By plugging F2 into
F.
it holds that
y PK.y
31 (Q + K. RK2) E(n
(vl Que + ve K.J RK29)).
(F33
120
120
Also, it holds that
y T PK.y
Σ 120
(W E(vit2
Pki Ut+1 - vu PK.V))
(F44
Combining
F3 and
F.4
we have
PK, PKI
(v. Que + U1 T K,J RK29 + VIL PK, Ue+11 - vi v))
(F.5)
220
Also, by the state transition 1/+1 (A BK2 (K2))1, it holds for any t that v. Que + v KT RK2n: + VT.1PK
PK, 1/+1 3/ PKI
v1 QQ + (K2 K1 K1)T RiK2 K1 + Ki))ya
u. [A BKi B(K2 -Ki)] PK, [A BKi B(K2 Ki) v² PKP We
-yy (K₂ - K1) [R + +B PK, -B, B)KK BT PK.
=
+ M. (K2 - T()T(R+ (RR)T(++OO) +R2+BB TBBT Pk. (K2 - -Ki)8t
= 2yy (K2 K1)T TTT K1 - )1 + vT (K2 K1) K 22 (K₂ Ki)
(FF)
40

---

Published as a conference paper at ICLR 2020
where the matrix T Ki is defined in 3.7 By plugging (.66) into F.5 have
y PK. 3/ PK.Y
= -> 2vi (K2 - K1) ( K1
Tk, vu + v4 (K₂ K1) T (K2 K1))
t20
-E D KK
120
where (y) 2y ( Ki T w y TK2 T (K2 Ki)y. We
finish the proof of the lemma.
F.2 PROOF OF LEMMA D.2
Proof. We prove (D.66) and (D.17) separately in the sequel.
Proof of (D.16). From the definition of (K) (.6). we have
(1(K) (1(K)) = tr([p w. Pk- v.)
Eo PKY - yn PK-9)
Σ DK.K-(U6)
(F.7)
where in the last equality, we apply Lemma D.I and the expectation is taken following the transition
Vo+1 = (A- BK*) yys with initial state yo ~ N (0, V.)) Here we denote by Dx.k* k- (y) as
DK,K-(0) = 2y (K* K) 1yy T
(K K) T T (K* K)y.
Also, we write DK,K- (1) as
DK.K- (y) = 2y (K* -
K) (K
(F.8)
= y T[KK - K - r K K
-yT T (T
r )y-
Note that the first term on the RHS of (F.8) positive, due to the fact that it a quadratic form of positive definite matrix, we lower bound D K- (y) as
D (v) 2 1 (T - r ((
-
-r
(F.9)
Combining
F.7 and F9
it holds that
(() <
E Σ
-
120
1 ll2 (T - (T
< || 11, 0 212 tr (T T T
I ml (R) 2 1|2 tr (T K - K
where the last line comes from the fact that T R + B T Px 2 R. This complete the proof of D.16).
Proof of (D17). Note that for any K, it holds by the optimality of K that
((K))J((K)) (K( (K) = E Σ Dx D +20
(F.10)
where the expectation is taken following the transition V/+1 = (A BK ye with initial state yo (o V.). ). By taking K = - (T (372)-(((7))))
(TT K - T21) and following from a similar calculation as in (8). the function K (v) takes the form of
D ( -y (T -
(
-T yg-
(F.11)
41

---

Published as a conference paper at ICLR 2020
Combining (F.10) and (F.11 it holds that
J(K) J(K*)
2 - (
min (.)) 1 -r ( -
where we use the fact that Φxx = (A - 1 BK) + v. = v. in the last line. This
finishes the proof of (D.17).
F.3 PROOF OF LEMMA D.3
Proof. By Proposition B.2 have
(i(( Ji (K)+)) tr (P.... 1k,11) ).. (24i
1k, 112 [[ellr. (F.12)
The following lemma upper bounds the term [| Pkn-ill2.
Lemma F.1. Suppose that the parameters K and K satisfy that
K K||2 (IIA BKI22 + 1) || I amii ( \|)
(F.13)
then it holds that
|PR Pxll2 S 6 min (w)) 1 k 1| |||||| |||| || K|12
(F.14)
B1 || ) ||4 BK || || + 1).
Proof. See Lemma 5.7 in Yang et al. (2019) for detailed proof.
To use Lemma F.1 it suffices verify that Ka+1 and Knt1 satisfy F.13 Note that from the definitions of Kn+1 and Kn+1 in (D18) and (.21)) respectively, we have
||Kat1 Kntille- (IIA - BRn 1 1/2 + 11 k_+1 l/2 y 1 K. - Y YxK,ll l|ll (1 + [K,, 112) (IIA - BKn+ill2 + 1) 11 R 112.
(F.15)
Now, we upper bound the RHS of F.155 For the term ||A B BK ||2, it holds by the definition of Kn- in D.21 that
|| BK BKatil
< BK + - 12- || Kn -121 l2
S A BK, 12 + 7 | B| { 1l2 (1+ ((Lnll2).
(F.16)
By the definition of Tx, in 3.7 we upper bound ["<,,, as
| k. ll
|| 2 + [ + (||A|]: + [1r] || ll2
|| 2 + |||| + (II-A])= + [1 J1 (K(o) -mln (W.),
(F.17)
where the last line comes from the fact that
(1o) 2 (I,,,,) = (Q + K, RK, iP(P.. V.) 2 |P l2 T (.c). As for the term | | RRt1 ||2 in (F.15). from the fact that
(Ko 2 J1 (Kn+1) = [rQ + KT RK k
| 1 K lll O (Q),
it holds that
1 R ll2 I (K() ami (Q)-
(F.18)
Therefore, combining (F155.
F.16).
and F.18). we know that
| Kn+ill 1/21. (IIA BK 122 1) 11 R
I poly, (1)Kn (2) i Tx.
(F.19)
42

---

Published as a conference paper at ICLR 2020
From Theorem B.& it holds with probability at least 1 - T -, that
poly [| l1Al12) log" Tn
[ k., - Tx, S
(F.20)
AK, (1 p)2
T//4 poly, (I) (. le. 11.b0lll...11 (|lll))
log 1/2 TT
AXA
Ta/s (1 p)
which holds for any P E (AA--BK),, (,,,,,), 1). Note that from the choice of Tn and Tū in the statement of Theorem th4]
Tn 2 polys (l) lle, |16ll22 [|all2) A ||- p(A - BK,)) 6
T, 2 p (l) le. (1100102..111 [[all2) AR. [1- 11-p(A- - BKn))
12
it holds that
poly' [1 15 [1Aal22)
log' Tn T
polys (I) (mlEE,, |l (|al12)
log
1/2 T
AR, (1 - p1
AK.
Th (1 p)
< min
[poly, (1)
Omin 41 1/4 |B
(F.21)
poly (1) (la)
e/8 Omin (.) m (R)
|| 11 1 wlll
Combining (..1)) (220 and (F21), we know that (F13) holds with probability at least 15
for sufficiently small & 0. Meanwhile, by (6.6 (F.17 and F118), the RHS of (F.14) is upper bounded as
6 a min
(ww) 11 Rnti l12 1| ll2 || || - Kn+ille
(II /2 (kn+lll2) I|AA BKn-ille + ||B]|2 |Rntalle + 11)
poly2 [ ll2 || T Tx,,ll I|F.
(F.22)
Now, by Lemma
F.1 it holds with probability at least 1 - 15 that
|R
Pk Pk ll2 S 6 omin w || K44, 1/2 |K || [|8x+1 Knt1ll2
(1] Km 1 (12) 11A BR ll2 + ||B||2 [| /|2 + 1)
< poly (2l1)) | K. -T -Yk..l
S 7 min (V.) ominn (R) | I...
(F.23)
where the second incquality comes from (F222). and the last inequality comes from F.20 and F22
Combining (F.12) and (F.23). it holds with probability at least 1- 1s that
(K,+ J, (K $ 7 amin (V.) Jmin (R) || 11 5/44
which concludes the proof of the lemma.
F.4 PROOF OF LEMMA D.4
Proof. Note that T K*
T K- is the natural gradient of J1 at the minimizer K*, which implies
that
T& K* -T2- = O.
(F:24)
By Lemma D.I it holds that
(iK - (K*)
ir(Px PK- V.) = Ey PKY - v. Pk-y)
2y (K K*) K*)(T - Dir ue (K K*) T (K - K=) K')wi) }
EE
Σ
120
E
Σ
ME (K - K*) T (K Km)
(F.25)
120
43

---

Published as a conference paper at ICLR 2020
where we use (F244) in the last line. Here the expectations are taken following the transition y1++1 (A - BK) with initial state yo ~ (0, W.). Also, we have
De (K - k*) T.. (K k2)
120
tr[0x( (K k*) K- (K K}]]
1 1| 1|2 tr| (K K*) (K - [K)
min (v). min (R) || K 11:
(F:26)
where we use the fact that Φx (A BK) p K (A - BK) ) + v ł v, and T R+ Pk- B z
R in the last line. Combining F.25 and F.26 we have
Ji(K) Jı (K*) 2 miin (V.) mmin (R) || - K*I...
We conclude the proof of the lemma.
F.5
PROOF OF LEMMA D.5
Proof. Following from Proposition
we have
J2(KN. bb+1) J2 (KNN bn+1)
59 VoJ2 (KN: b1+11 [VbJ2 bb) VoJ2(KN kn)
+ (7²)2 /2 | VNJ2(KN AnJ2 (KN, bn)112
J2(KN, bn+1) J2(KNN bn+1)
S - (oN2(KN, 11+1)
( [VoJ2(KN bn) - (k22(KNN bn)]
(F.27)
- (6)) 1xx /2: VoJg(KNN bn) 2o b1
where vky and LKw are defined in Proposition 3.3 Also, following from Proposition B.3 it holds that
VoJ2(KN (o S poly, (I) (lel, lbbn J[K,,, bu)) [1 - p(A - [[-BBKK]]
(F.28)
Combining F.27
F288 and the fact that VKN S LKx p(A- p(A--Bx)]] poly2(11<xx11)).
we know that
(KN, bnt1) (2 N, 1)+1)l
(F.29)
(/ poly, (l) (12) |/Vo bn) bo.
bn)1l [1- ((A-A(AB))) BKN)] + +7" poly, (| ||r, |bb l1,, [|112,, J JKKN bo)) (KNJ(KNN bn) {oJz(KN, bn)
-2
[1 p(A BKN)
Note that from the definition of VoJ2(KN, (K,,,,, bn) and VoJ2(KN. b.) in D.31 and D.33 respec- tively, it holds by triangle inequality that
| VVbJ((KN) bm) - VnJe( KN, bw)llp
T - T l1 || 1l2 1I Ma 1/ |l2 | 110xx,b. - MKNNball bb ll2
T T 112 llbulla + || - lla || Ma lla + 1@ QKN MaKNnaalla
r Nx 1l2 ||pxv.b. MKN.0n 1l2.
By Theorem B.8 combining the fact that J2(KN, bn) S J2(KN, bo) and the fact that |laky S
J(KN, bo) miin (Q), we know that with probability at least - (Th) (Th) -6 it holds for any
P (p(A BKv ). 1) that
V.J2 n. by) (K,,(KK,
(F.30)
log T (TT))/1(1~ - p)2 + log 1/2 1/2 T
< x polyy pI Klle,,
I |lAll.. J2(KNN bu))
(T /8 (1 p)]
44

---

Published as a conference paper at ICLR 2020
Following from the choices of >
,, The and T. in the statement of Theorem B.4 it holds that
70 poly, ( lIr, 116m|12, 11ll/1/222 12, JK ,,,,,,,) bo)) ARN polyy ( (11Kx |1r,
[1 12, 2/ (22 bo))
log % T
log" 1/2 T
(Th) p)2 + (T (1 - p) [1 ---ple p(A A -BBNK)]]
+ [1 - p(A A - BKN]] -2
log 6 n2
log To
K bo)) polya (1) (NNlI: |1b ll, 11 J2(K
(T2) p] +
(Th)2/4 (1 - p)2
(78)) poly, poly, X
S VKy -
Further combining (F29 and F.30 it holds with probability at least 1 - _0 that
J2(K w. bb+1) J2 1 S vnN e/2.
We then finish the proof of the lemma.
F.6 PROOF OF LEMMA D.6
Proof. We show that SK.6 E V/ and E(C) E Vg for any Ç E Ve separately.
Part First show that CK.6 E Vc. Note that from Definition B.7 we know that Ck J(K, b) satisfies that 0 S Sk.6 I (Ko, bu). It remains to show that Ci. = αKK satisfies that ||5 S
Mç. By the definition of oxK6 in (B.6), we know that
|a 2 [ K 11 + x 11: (Ila,,011 + (
+ (11-A112 [B112)² 2 (1lPxl12 A| + d|22 (1
(F.11)
where SKK,- = (I- A+
BK) (B + Au d) KT lib) and for notational simplicity, we denote by 1=,,6 = KKK, + b. We only need to bound Kx. uKKbb, 1k,66 Pk. and
fK. Note that by Proposition B.2 the expected total cost J(K, b) takes the form of
J(K,b) = tr(P + Kk.QUKk + (kk,)) T + +o²
tr( (R) + = Qp.
Thus, have
J(Ko: bo) 2 J(K,b) 2 min (ww) tr( (r(Pk) 2 min (ww) Pk 112, J(Ko, bo) 2 J(K,b) 2 -K 2 Omin (Q) || 12,
[Koo bu) 2 J(K 2 ( Ruk,o 2 Tmin (R) |
which imply that
|| Pxll2 S J(Ko, bn)/ (Vw),
|uK,ol12 S J( J(Ko, bo) m (Q),
11 S J(Ko, bo) min R).
(F.22)
For Y it holds that
Q
A B
Tk-
0
R
+
PK (A B),
which gives
|T < [
+ [[][]]]
+ (IA)) + |B P llf.
| 1l2 E (11@122 + [ + (114122 + || 1
Combining
2 and the fact that [| < vm [|Pxl12. we know that
M x |F < (1Q)|r [R]r]) + (I|l [[B] Vm J[Ka, bn)/o ( (Vw),
T k ll < (1Q112- [[A|]22 + (IIAI]2 + 113112)) JKoo bminnmmim/////// (V.))
(F.33)
45

---

Published as a conference paper at ICLR 2020
Now, upper bound the vector fk.b. Note that by algebra, the vector fK.6 takes the form of
fK,6 -PKKKK + (1 A+ (AO-BBK)T--BA (QUKE K KJ &RRkk))
Therefore, we upper bound JKK. as
|| _ J(Ko, bo)2
-mmnn (w
min (Q) [1 1(A - BK]] -1 (KQ KRR [[ (F.34)
Combining F331
F.22
(F33). and FF34). holds that
1s ||ox,,ll2 Me,1 + M2,2 (1 + ||]]]) [1 [1- B
Therefore, holds that (K,6 E Vc-
Part 2. Now we show that for any Ç E Vc, we have E(C) E Vg. Recall that from (D.41) it holds that (C) = J(K,)),
(C) TT [v(2, w) Ox,6 BE [c(2, u))((, (F.35)
Then we have
[<' =Is' J(K,b) J(Ko, bo);
(F.36)
where we use the fact that since Ç E Vç. we have 0 S 5² s [Ko, bo) by Definition B.7 Also, by we have
F.35).
ETICA (x(x, + 110xolll2 115 + E [c(x, (x)
(F.37)
B2
B3
Note that we upper bound B1 as
Bi S J(Ko. | [b, w)]
(F.38)
Following from the definition of (xx u) in B.5). we know that
Ex (,,
(x),,))]] w]] s ||alle.
(F.39)
where Σg is defined as
4x K K&x
DKK
+ -0 22) + +(1
1
Σ Cov =
Φ -
K&
Combining F.38 and F.39
we have
B1 S J(Ko bo) ||
(F.40)
By Proposition B.6 we upper bound B₂
(M₃,1 + Mq.2) [1 p(A - p(A-BB)] B2 S 4(1 + {1 |
(F.41)
where the fact that Ç V/s and Definition B.7 As for the term BN in F.37 utilize the following lemma to provide an upper bound.
Lemma E2. The vector Exx, [c(x, u (I, u)] takes the following form,
2svec digg (o,diiigg((())))) (Q, R) + (Ez, (iag(Q,()))5))
E [c(x, u))((, w)] =
2Q
Σ,
2R
(svec(Ex))
+ LukoQUKK + (uk Rpi [qu]
Om
OF
Here the matrix E, takes the form of
Φx KK
KK K t02.1)
Σg =
46

---

Published as a conference paper at ICLR 2020
Proof. See F..1 for detailed proof.
From Lemma
and FF3 it holds that
B3 $ 3 [[ + [R]| + (Ko. bu) 1|Q1112///200 min (Q)
(F.2)
+ (Ko, bo) / (R)] | 11
Moreover, by the definition of Σ, in E.25 combining the triangle inequality, we have the following
bounds for | ll and |_g|12.
|E s 2(d + | 1 1xll2 112,
|2glle 2(1 + | |
(F.43)
Also, we have
J(Ko bo) 2 b(, 2 tr (Q K RK)Φk] 2 |1 O (Q),
which gives the upper bound for Φ follows,
| 12 I [KK, bo) min (Q).
(F.44)
Therefore, combining FF37
F.40
and (.44), we know that
( s C (Mr.1 + M2,2) J(Ko // (Q)
(F.45)
(1+ [K] [1-p(A [K)]
By F.36 and (.45)) we know that ((S) V/8 for any ( E Vc- We conclude the proof of the lemma.
D
F.7 PROOF OF LEMMA D.7
Proof. Assume that Ey Nu4 Σ₁). Following from the fact that
2+1 122 + v + 6z,
it holds that
L-1 T'
E ~ N
Σ
I' (I +
(F.46)
1=0
1=0
where
V
KV K + +021)
KV
From D.47 we know that μı takes the form of
86 Σ
N1 = L)
Lvv.
(F.47)
j=0
Therefore, combining (F46)) and F.47 have
f oc
E(P.) = p2=
L'v.
(F.48)
T
We denote by
T
T
L
L'v.
t=1
[=1
i=!
47

---

Published as a conference paper at ICLR 2020
Meanwhile, it holds that
T
L 14
ΣΣ L.v
$ Σ p(L) 1114112 + Σ (L))' |11|
t=1 i=t
< [1 [())] || [1 xL)]]
|||/||2
$ M₁ (1 2² ||
(F.49)
where M, is positive absolute constant.
For the covariance, note that for any random variables X ~ NN 21) and Y Mup, E2). know that = X + Ni + #2, 2). where ||S||ı I 2|[ii||F + 2| ll.. Combining (F.46). we know that fag ~ N (EE E7/TT), where En satisfies that
f 1-1
4/2. [5 $ Σ p(L)at
|E || +
ΣΣ
((L) ||
[=1
t=1 im
$ [1 - p(]]]
-1 |_+||r + T. [1 pl p(T.)/]=' 1
which implies that
| S My (1 - p) p) 1 Ie.
(F.50)
where My is positive absolute constant. Combining (F48). F.49 and E.50). obtain that
Do ~ N P2 +
T FuT / 1
where 11w S Mn p1 - ||m112 and |A S My (1 (1-p) -1 1-1.. Moreover, by the Gaussian tail inequality, it holds with probability at least T that
li - Malla < log
(1 (1 21 2plyy (0ly(1@x<l [[e,, [1bll,, ||al|2).
T1/4
Then we finish the proof of the lemma.
F.8 PROOF OF LEMMA D.8
Proof. We continue using the notations given in (D. We define
F(C.E) = (B()) E 5
B(ao) } - e² + 1[5--B(6 -g- - 1/2 115112.
where C (1x u) is the estimated feature vector. Here the expectation only taken over the trajectory generated by the state transition and the policy KK.b, conditioning on the randomness induced when calculating the estimated feature vectors. Thus, the function F(C, is still random, where the randomness comes from the estimated feature vectors. Note that [F(C, {) - F(C,E) < [F(C.E) ) - F(C.E) + (f(5. - E).. Thus, we only need to upper bound [F(, () F(C,E)) and (F F(),E))
Part 1. First we upper bound [F(),E) F(. {. Note that by algebra, we have
F((,E) F((.E))
(ES 355¹ + E V')2
- e -
T - E(c((- - x}]} E²
E((l - )11z) [[' E(Ilo Vl + 2116112) ||52 + E(c) 11E2112.
(F.51)
48

---

Published as a conference paper at ICLR 2020
where the expectation is only taken over the trajectory generated by the state transition and the policy it holds that
TK From Lemma D.7
P P( Me + 1/T prll2 S C1) 21-T
(F.52)
Therefore, combining (H.52). holds with probability at least 1 7 that
B1Iv- + 2 21 I poly (1 12 K[ee, |1 a e J J bo)):
(F.53)
where the expectation conditioned on the randomness induced when calculating the estimated feature vectors. Also, we know that
E(c) S poly (1
|
[|b||2, ((Ko,
(F.54)
Therefore, combining (F5T
(F.44). and Definition B.7 it holds with probability at least E.53).
1 1-7-0 that
F(C,E) - F(c.E) - B(Ie) 122)) poly (1 2l, || ll.. |b|| |11lllll221112 (Ko, bo)).
(F.55)
Following from the definitions of (xx u) in B.5) and (22, u) in (B.14). we upper bound || u) (xx u) l2 for any x and v as
[,, u) Max 1) I| - Us + (0s - M₂)T + (iz us)z 1| 11 |1 Pa 11
< poly [1 1|2, || lle, |16||2, I 12, J (Ku, bu)) 11 Ms 122.
(F.56)
where μ2 is defined in (D.77). p. is defined in (D.48). and (x u )T_ Also, by Lemma we know that
D.7
log T
li= - ~ S
(1 p2 -poly( (1 k ll: [[r] |b]|2, 11a112, J(Ko, bo)),
(F.57)
71/1
which holds with probability at least T- Combining F.55) probability at least 1 - T that
(.56). and (F57). it holds with
log T T1/4
(1-p) p)- poly (I) |b61 11 [Ko, bo)).
(F.58)
Part 2. We now upper bound [F(G.E) F(.. { in the sequel. By definitions, have
F(C.5)
F(c
{ReO 5) + FE( - ক 3 - ( B a } B(c - 2)
< (BOOE*+ + B(OB" x²² BBOD }
T 1² =(OE -1.-
(F.59)
+ L 2<
T s² 1(gne)
where we define the event 8 as
E'=
n [I us + 1/T 17l12 - -rr( S Ci log T (1( E2
n
(E(TT
where & is defined in (D55). Combining the fact that PP&)) 2 -6 and Lemma G.3 it holds
that (PEE) - T-6 Following similar argument in Part 1, it holds from F.59 that
F(C.E) -((C,)) <
71/4 poly [[]] [bbl lllll,, [[Ko. bo))
1
(F.60)
for sufficiently large and T.
Now, combining F.58 and F.60p. by triangle inequality, it holds with probability at least 1 - that
log T
F(C.E) - -(C.E) <
(1 - (1-p)- -2- "-poly [/6122 ||ll|2 J JKoo bo)).
27
114
We finish the proof of the lemma.
49

---

Published as a conference paper at ICLR 2020
F.9 PROOF OF LEMMA E.2
Proof. Recall that the feature vector (ar u) takes the following form
(x) [svee[ p2)(2 p=) 1)
p1z
We then have
(10, u) "bla' (u) = (svec [yu] (Ty + ()(TT) + 5) (Ly +
(F.61)
where we denote by y Ug. and (z', u') is the state-action pair after (x, u) following the state transition and the policy T..6. Therefore, for any symmetric matrices M, N and any vectors m, n, it holds from (B.7) and (F.61) that
(svec())) m
(vee(N)) O.B
n
(vee(())) (wee((uu)) (svec[vo) - (Ly + () ()) - (sve(((v))))) - (Ly +6)
(sveo(AV))
Ey,
m
n
By.. ((M +m mmyy) [(N. (Ly + () 5) ) + n (y Ly 59]}
By (wVV' T, ,M) (uyJ Lyy' T LT Vs, N)) E.y (wy .M n (y Ly))
(F.62)
A
A2
+ Ey (m T y. (uy Lyy LL L. Vo, + By m y n (y --)l
As
A
where the expectations are taken over NO Σz) and 8 ~ NO0, Ms). We evaluate the terms A,, A2, Ag. and A4 the sequel.
For the terms A2 and A3 in (F.62). by the fact that y ----- 1=- ~ NO, Ez), we know that these two terms vanish. For A4, it holds that
A = Ey |m y (y - Ly) n] = E, [m yy (1 Tn = m EI - Ln..
(F.63)
For A1, by algebra, we have
A (wvV .M) (yv Lyy" L N2,
Ey (WVV, ,,VVTMM) M)- (yy" Lyy'" LT, ,,N) Ey (1yy) , (W,,
= [y My y (N NLNN - (E,, M) (V,,,)
Eun-N(an)) u E u. TT!//((N L [NND)E!/3u (Ez, M) N). (F.64)
Now, by applying Lemma G.1 the first term the RHS of (.64)). know that
A1 = 2t / /2//2M//// / L NLJE!/2
+ +tr(E//2M) /// L NNDE - (). .V, (V,, (NM,,,,N-TTNDD)) (E. (E, - - Vs.
=
where we use the fact that Σ. LE V in the last equality. By using the property of the operator svec(.) and the definition of the symmetric Kronecker product, we obtain that
A 2svec (M) Tvee
svec [N I,T NT)E..]
8. E3 - (E 8. (E.LT) svec((N) = 2svec(M)) T Σ.
2svee((M)
[2i, ((E
2. 21)(1 L 8, L) [ssec(((N).
(F.65)
50

---

Published as a conference paper at ICLR 2020
Combining F.62
(F.3) and (.655
we obtain that
svec(a))
(veee(N))
K,
m
sVe) (22 85 -
- L. [vvc(() + TmEll - D)"n
(svec(M))
T
[2 0, [. - 1.)T
--(1- ---)) (svec(N))
Thus, the matrix θ Ktb takes the following form,
K (2 0g - & L.)
Eg(I -x(I-L)] -]])
which concludes the proof of the lemma.
F.10 PROOF OF LEMMA E.3
Proof. From the definition of θ.. in B.9 it holds that
o
< 1 | K.
+
110
(F.66)
where 0= is defined as
(svee(E.s) 0 Ok+m
σ_ E [1b(2,, u)]
We bound the RHS of (F.66) in the sequel. For the term Q
Ox,6 K,b combining Lemma E.2
we have
11/2 (I (I- 8, L)
TEE 82 Σg) svec(E.))
0k+m
1/2. (T. (T- 1. L0 L.) (S)-T(p- 8 Σ-イ) svee(E.z)
O
1/2 (T- 0. L)-T svec
(F.67)
0 0k+m
where we use the property of the symmetric Kronecker product in the second and last line. By taking the spectral norm on both sides of (F.67). it holds that
7 = 1/2 [I -I- ||0 K.b
T L 02 -T svec(E,))) )|1
||svec < 1/2 |[[- 0. L) - - 2)1
$ 1/2 [1- - ||F
< 1// vk+ m [1-p((L)) -1 -1=, ||2
= 1/2 Vk + m [1- p2()] -1 - (Ei))
(F.68)
where in the third line we use Lemma G.2 to the matrix L L. Similarly, we upper bound ||0 1222122 in the sequel
0 Ralla min 1/2 [1- - p²() (E,) p(.]] min {
(F.69)
Thus, combining (.66 (.68). and (.69), we obtain that
@ @x < 1 + 1/2 Vk + m [1 (T.] - (Ex)
min 1/2 (1)) m (Es), p(L)) -1 _1__ (E=)}
(F.70)
51

---

Published as a conference paper at ICLR 2020
Now it remains to characterize min (Es). For any vectors R and r R we have
Σ S
Pu (x) (8) {(s (0- +r (u KuKD b)]²}
We {(s--l( KJ (T) -K,0) or T n]²} BENNI [(s KJ (x wxxo)² + By.
( n) (FE71)
The first term on the RHS of F7 lower bounded as
EgnN(ukss
[(s K (T [kx,)] - = (s ())-KTT)TTe (x(()) kT)
||s K r112 min (K) 2 1|s K TT, r112 min (w))
KTrl3
(F.72)
where the last inequality comes from the fact that J (1x) min (w))) by term on the RHS of (F.71) takes the form
3.3
The second
E,- n) = 0ô11113
(F.73)
Therefore, combining
F77
F.72
and
F373 we have
Σ
|| K r12 min (ww) o ||r
min (.)) || + [o² ||| m [Ww]] 111122
From this, know that
Jmin (E2) 2 min Omin (V.,), | Jmin (Vw)).
(F.74)
Thus, combining (F700 and [.74). we know that ||0x,olla is upper bounded by a constant Xx. where Åg only depends on || and p(L) = p(A -K).. This finishes the proof of the lemma.
F.11
PROOF OF LEMMA F2
Proof. First, note that the cost function c(x, u) takes the following form,
svec (liaa(Q, R)] 2QμK,b 2R
cxx,u) vxx U)T
(okoo)RRkkee [KK, (ok.0) Rykk + p Qu].
For any matrix and vectors Uaa Ua holds that
(svec(V))
Eax. [o(x, ())(2
Va
Vu
(svec (ooe[dia(Q,,0 (RRR)
(Vv)c(V))
Baxs u)
2Q 2R
10 T)
Uz Vo
(F:75)
D1
(svec(V)
T + ET (uT + (K* Rpi + 4 (uQ))
Uo
Dr
In the sequel, calculate D, and D2 respectively.
52

---

Published as a conference paper at ICLR 2020
Calculation of D1. Note that by the definition of () u) in (B.5). it holds that
(2Quk.b
D1 = B
(= (z-)x) Uz)
diagaQQ. 12) 1 12) + (= 1z)²
2R
(= (== 11=) + (=- 1z)
Ux
V'us
E [[2 -m=) (daag(Q,1))) - (2)) (z - Us)) (x)TTT(C (2 1c=)
(F.76)
(2QμKbb
E (2
(z 1=)(== -=²)
U2
Vu
Here (x T) and uz B (z). For the first term the RHS of (F76), note that
u1 N (0, ).). Therefore, by Lemma G.I we obtain that
E Ex [2z pe) diag(Q. R2 ps) (2 uz) V((2 [z]]
= 2 2 diag Q, RR v) + (Ee, diag(Q (Q, R)) (Ee, V)
svec
25. 22. Q, R) + (E diag( Q, R)) Σg svec(V).
(F.77)
Mcanwhile, the second term on the RHS of (F.76) takes the form of
(2QKKb) 2R
]
(2Q 2R
ExK.
(z - (z) - ps)
Ux
Ex
(F.78)
Un
Combining (.76).
(.77
and F.78 we obtain that
2svee diagg RYE, + diag
)
T
(vvec(V)
D1
(2QUk.b) Σ, 2
(F:79)
Uu
Calculation of D2. By the definition of the feature vector (1r u) in (B.5), we know that
(svec(E:))
/svee(V))
Rykoo + Qu) D2 (KkOQKKK (Hk,s)
0m
Un
(F.80)
O₃
the
Now, combining F.75
(.79p. and F.80 it holds that
2svee [E, (Q, RYE, + (E,, diag(Q, R))E2]
E [c(E, u)) w]]
(2Q
Σ, 2R
(svec(E>)
+ IKK + (H RU + [QQ
0m
which concludes the proof of the lemma.
G AUXILIARY RESULTS
Lemma G.1. Assume that the random variable ~ (), and let U and V be two symmetric matrices, then it holds that
((w Uw w Vvw)= 2tr(UV) + tr()) tr(V).
53

---

Published as a conference paper at ICLR 2020
Proof. See Magnus et al. (1978) and Magnus (1979) for detailed proof.
Lemma G.2. Let M, N be commuting symmetric matrices, and let a...... ax ...... Sn denote their eigenvalues with ....... Un common basis of orthogonal eigenvectors. Then the n(n + 1)/2 eigenvalues of M 8, N are given by (as$3 + ay,::/22, where 1 sisjs n.
Proof. See Lemma 2 in Alizadeh et al. 1998) for a detailed proof.
Lemma G.3. For any integer m > 0, let A E R= and 1j NN(0, Im). Then, there exists some absolute constant C' >> 0 such that for any
2 O, we have
p|1 An B(n' T Ar))
s 2 exp -aapp---miine mmiin((1A 41A112))
Proof. See Rudelson et al. (2013) for a detailed proof.
54


Reviews:
[{"review_id": "HkeV7N2CKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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\nThe 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.\n\nQuestions/Suggestions to the author\n(1) It might be helpful for the reader to include a rough sketch of the proof and algorithm earlier in the paper\n\n(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.\n\n(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?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByxCE7vQcS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 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. \n\nThe 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.\n\n1. 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.\n\n2. The problem setting is not very well stated in Section 2. \n1) 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. \n2) 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. \n3) 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?\n4) 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'. \n5) 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.\n6) 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)]. \n\n3. The mixed actor-critic algorithm (with linear approxiamtion) for the subproblem D-LQR for evaluating \\Lambda_1 is not well motivated. \n1) 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? \n2) 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)]. \n3) 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).\n\nSome minor suggestions.\n1) 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?\n2) 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.\n3) In (2.1), there should also be \\sigma\\in \\mathbb{R}.\n4) 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.).\n5) 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)?\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Byx4wYANtr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 and Decision \n\nThis 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. \n\nOverall, I recommend a weak accept for this paper. \n\nBackground \n\nMean 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. \n\nMathematically, 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. \n\nHere 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. \nhttps://arxiv.org/abs/1302.6416\n\nFurthermore, 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. \n\nIn 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. \n\n\nDiscussion of Contributions \n\nThis 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. \n\nOverall, 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. \n\nFrom 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. \n\n\nDiscussion of Limitations \n\nThe 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:\n\n1. 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. \n2. 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. \n\nTherefore, 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. \n\nWe 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. \n\nIn 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. \n\n*Edit:* I believe the discussions below have address several important concerns, and I will raise my score to accept.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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)