PaperlayerView exact revision on arXiv

Source-linked AI summary

Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games

Zuyue Fu, Zhuoran Yang, Yongxin Chen, Zhaoran Wang

arXiv:1910.07498v1math.OCcs.GTcs.LGcs.MAstat.ML

TL;DR

The paper addresses the need for efficient, model-free methods to find Nash equilibria in discrete-time mean-field games. It develops a mean-field actor-critic algorithm with linear function approximation and proves linear-rate convergence to the unique Nash equilibrium.

  • Problem

    Existing work emphasizes Nash-equilibrium existence and uniqueness rather than provably efficient algorithms, and fixed-point methods can require knowledge of the dynamics.

    Source: §1 · pp. 2–3

  • Method

    Using Nash certainty equivalence, the method alternates single-agent actor-critic policy optimization at a given mean-field state with an update to that state.

    Source: §1 · p. 3

  • Results

    The alternating policy and mean-field-state sequences converge to the unique Nash equilibrium at a linear rate.

    Source: §1 · p. 3, §5 · p. 14

  • Takeaways & Limitations

    The work establishes a model-free reinforcement-learning approach with function approximation that provably attains a discrete-time mean-field game's Nash equilibrium.

    Source: §5 · p. 14

    An earlier actor-critic convergence proof assumes convergence to the single-agent optimal policy, which was unverified there.

    Source: §1 · p. 4

Abstract

from arXiv · show

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 functions, 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 approximation, 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 learning with function approximation to discrete-time mean-field Markov games with provable non-asymptotic global convergence guarantees.

1 Introduction

The introduction presents a model-free actor-critic approach for discrete-time mean-field games, including transitions dependent on the mean-field state and LQR with drift, with truncation to handle unbounded critic features. It frames the approach as reaching a unique Nash equilibrium at a linear rate without relying on known dynamics or simulators.

Motivation

  • Mean-field aggregation abstracts away strategic interactions and avoids the intractability of MARL approaches that do not exploit symmetry, while most prior work focuses on equilibrium characterization rather than efficient algorithms.Source: §1 · p. 2

Contributions

  • The approach targets discrete-time mean-field games with linear state transitions, quadratic costs, and population effects represented by the mean-field state.Source: §1 · p. 3
  • The mean-field actor-critic uses approximate single-agent optimization at the current mean-field state, then updates that state assuming agents follow the resulting policy.The method is based on Nash certainty equivalence and uses linear actor and quadratic critic parameterizations that encompass each agent’s optimal policy.Source: §1 · p. 3
  • Alternating policy and mean-field updates converge to the unique Nash equilibrium at a linear rate.The paper also reports linear-rate convergence of single-agent actor-critic policies to the optimal policy of a drifted linear-quadratic regulator.Source: §1 · pp. 3–4
  • The authors present the first efficient model-free RL approach with function approximation that provably attains a discrete-time mean-field game’s Nash equilibrium.Unlike tabular approaches, it handles infinite state and action spaces using trajectory observations rather than a simulator.Source: §1 · pp. 3–4

1 Introduction

  • Unlike Li et al. (2017) and Briani and Cardaliaguet (2018), this work allows state transitions to depend on the mean-field state.Source: §1 · p. 4
  • Earlier convergence results include an actor-critic proof relying on unverified single-agent convergence, an asymptotic Nash-equilibrium result by uz Zaman et al. (2019), and convergence only to a stationary point by Jayakumar and Aditya (2019).Source: §1 · pp. 4–5
  • Yang et al. (2018b) combine mean-field action approximation with Nash Q-learning for large-agent general-sum games, but Nash Q-learning applies only to finite state and action spaces and relies on strong convergence assumptions.Source: §1 · p. 5
  • Because prior policy-evaluation results assume bounded feature mappings, they do not cover this critic update; the work handles unbounded features with truncation.The truncation argument requires more delicate analysis.Source: §1 · p. 5
  • The work uses actor-critic to study LQR with drift, whose additional optimal-policy intercept complicates the state- and action-value functions.The drift introduces the intercept, making the value functions more complicated.Source: §1 · p. 6

2 Linear-Quadratic Mean-Field Game

The section formulates an ergodic linear-quadratic mean-field game in which agents interact through the population mean and seeks a policy that is optimal for each agent at a self-consistent mean-field state.

2 Linear-Quadratic Mean-Field Game

  • The game uses linear state transitions and quadratic costs, with each agent's state and action driven by a policy and Gaussian noise.The objective is an ergodic expected cost.Source: §2 · pp. 6–7
  • In the infinite-population formulation, agents are coupled through the mean-field state, while the model assumes identical drift terms and symmetric state transitions and costs.The population limit is taken after focusing on a fixed agent under the symmetry assumption.Source: §2 · pp. 6–7
  • A Nash equilibrium is a profile (π1, ..., πNa) in which, for every agent i and alternative policy eπi, Ji under the profile is no greater than Ji when only i’s policy is replaced.The formulation seeks π* such that J(π*) = inf over π in Π of J(π).Source: §2 · p. 7
  • The paper also gives a more general formulation with an interaction term between an agent's state and the mean-field state, and states that the later results carry over with minor modification.The analysis focuses on the simpler formulation for clarity.Source: §2 · p. 7
  • For a fixed mean-field state, the game reduces to a drifted LQR problem; solving it at the equilibrium mean-field state yields the Nash policy.The mean-field state acts as an additional drift term in the single-agent problem.Source: §2 · pp. 7–8

3 Mean-Field Actor-Critic

The section characterizes when the Nash equilibrium pair exists uniquely and develops a mean-field actor-critic procedure that alternates single-agent policy optimization with a mean-field update.

3.1 Existence and Uniqueness of Nash Equilibrium Pair

  • The equilibrium characterization makes the composite mean-field operator Λ(·) = Λ2(·, Λ1(·)) L0-Lipschitz.The first regularity condition is implied by mild conditions on A, B, Q, and R.Source: §3.1 · p. 9
  • Under Assumption 3.1, the paper establishes a unique Nash equilibrium pair for the LQ-MFG.The conditions include a unique symmetric positive-definite Riccati solution and a contraction bound L0 < 1.Source: §3.1 · p. 9

3.2 Mean-Field Actor-Critic for LQ-MFG

  • The mean-field actor-critic alternates between approximately optimizing the policy at the current mean-field state and updating that state from the resulting policy.The outer fixed-point procedure relies on policy optimization and the long-run mean-field generated by that policy.Source: §3.2 · pp. 9–10

3.3 Natural Actor-Critic for D-LQR

  • For a fixed mean-field state, the natural actor-critic solves a drifted LQR problem using linear-Gaussian policies and policy-evaluation estimates.The policy parameters are a feedback matrix K and offset b, with Gaussian exploration noise.Source: §3.3 · pp. 10, 12
  • The drift-induced cost component J2(K, b) is strongly convex in b, and its minimum over b is independent of K.This supports optimizing the feedback matrix through J1(K) before updating the offset using the gradient of J2.Source: §3.3 · pp. 11–12
  • The natural actor-critic estimates policy-evaluation quantities with a critic, then updates K and b in separate actor steps.The K update uses an estimated natural gradient; the b update uses an estimated gradient of J2 at K*.Source: §3.3 · p. 12

4 Global Convergence Results

The convergence result bounds the final mean-field state and policy parameters relative to the unique Nash equilibrium. Under the theorem’s conditions, Algorithm 1 converges linearly.

4 Global Convergence Results

  • At update s, the algorithm uses an approximately optimal policy for mean-field state μs, with expected total-cost error below εs.The policy is optimal under the current mean-field state in the exact-update description.Source: §4 · p. 14
  • After S iterations, ∥μS−μ*∥2≤ε, ∥KS−K*∥F≤ε, and ∥bS−b*∥2≤(1+L1)·ε.Here μ* is the Nash mean-field state, and KS and bS are parameters of policy πS.Source: §4 · p. 14
  • Algorithm 1 converges linearly to the unique Nash equilibrium pair when its inputs satisfy Theorem 4.1’s conditions.The theorem specifies a sufficiently small tolerance ε and a number of iterations S.Source: §4 · pp. 13–14
  • The authors present this as the first successful function-approximation RL result finding Nash equilibria in mean-field games with theoretical guarantees.They describe the result as laying theoretical foundations for applying modern reinforcement-learning techniques to general mean-field games.Source: §4 · p. 14

5 Conclusion

The conclusion gives sufficient conditions for a unique Nash equilibrium and reports linear convergence of a mean-field actor-critic algorithm. The appendix also defines notation used in its proofs.

5 Conclusion

  • The paper provides sufficient conditions for existence and uniqueness of the Nash equilibrium pair in discrete-time linear-quadratic mean-field games.Source: §5 · p. 14
  • The mean-field actor-critic algorithm with linear function approximation converges to the Nash equilibrium pair at a linear rate.Source: §5 · p. 14
  • The algorithm can be modified to use other parameterized function classes, including deep neural networks.Source: §5 · p. 14
  • The authors identify risk-sensitive, robust, and partially observed mean-field games as directions for future extensions.Source: §5 · p. 14

A Notations in the Appendix

  • Appendix notation defines svec(M) as symmetric-matrix vectorization and smat as its inverse, and defines ⊗s through its action on svec(M).Source: A Notations in the Appendix · p. 26

B.1 Results in D-LQR

The section gives closed forms and structural results for the single-agent LQR problem, then establishes a conditional linear-convergence guarantee for Algorithm 2. Its analysis includes the value functions, the expected-cost decomposition, and gradients of the cost components.

B.1 Results in D-LQR

  • The state-value function is quadratic in x, and the action-value function is quadratic in (x,u).The section provides closed forms for both functions.Source: §B.1 · pp. 26–27
  • The expected total cost J(K,b) is decomposed into J1(K), J2(K,b), and additional terms.Proposition B.2 gives this decomposition.Source: §B.1 · p. 27
  • Proposition B.3 establishes the gradients of J1(K) and J2(K,b) with respect to b.The proposition states the gradient forms for J1(K) and for J2(K,b) with respect to b.Source: §B.1 · p. 27
  • Under ρ(A−BK0)<1, Theorem B.4 gives Algorithm 2 a linear-convergence guarantee for a fixed mean-field state.The theorem states its guarantee with probability at least 1−ε^10.Source: §B.1 · p. 28

B.2 Primal-Dual Policy Evaluation Algorithm

The section develops a primal-dual policy evaluator and extends the cost analysis to a general drifted LQ-MFG formulation, including a contrast with TD(0). It also describes modified actor-critic algorithms for Problems C.1 and C.2 and establishes non-asymptotic convergence results.

B.2 Primal-Dual Policy Evaluation Algorithm

  • Algorithm 3 uses primal-dual gradient-TD updates instead of directly solving the evaluation system, whose ΘK,b matrix is invertible when ρ(A−BK) < 1.It estimates the mean-field state by simulating the policy for eT steps before constructing estimated features.Source: §B.2 · p. 30
  • Under the stated stabilizing-policy and cost conditions, Theorem B.8 guarantees convergence of Algorithm 3 for sufficiently large simulation and iteration lengths.The theorem uses step sizes γt = γ0t^-1/2 and requires eT to exceed a polynomial threshold that depends on problem parameters and (1 − ρ)^−6.Source: §B.2 · p. 31

B.3 Temporal Difference Policy Evaluation Algorithm

  • TD(0) is presented as a practical alternative, but the paper's non-asymptotic convergence theorem covers the primal-dual method because ergodic TD(0) convergence is only shown asymptotically.The cited non-asymptotic TD(0) analyses address discounted MDPs (Bhandari et al., 2018; Korda and La, 2015).Source: §B.3 · pp. 33–34

C General Formulation

  • For the general drifted LQ-MFG problem, expected total cost is decomposed into terms eJ1(K) and eJ2(K,b), a noise contribution σ² · tr(R), and an additional mean-field-dependent term.The proposition defines eJ1(K) and eJ2(K,b) in terms of the general drifted LQR formulation.Source: C General Formulation · p. 35
  • For any K, eJ2(K, b) is νK-strongly convex in b and has an ιK-Lipschitz continuous gradient in b.The additional term 2µ⊤PµK,b is linear in b, so it preserves strong convexity.Source: C General Formulation · p. 35
  • The minimizing offset ebK = argminb eJ2(K, b) has a minimum value eJ2(K, bK) that is independent of K.The passage defines S = [(I − A)Q−1(I − A)⊤ + BR−1B⊤]−1.Source: C General Formulation · p. 36
  • Propositions C.6 and C.7 establish closed forms for the state- and action-value functions and gradients of eJ1(K) and eJ2(K, b).Source: C General Formulation · pp. 36–37
  • With slight modifications to Algorithms 1, 2, and 3, similar actor-critic algorithms solve both Problem C.1 and Problem C.2, and all non-asymptotic convergence results hold.Source: C General Formulation · p. 37

D.1 Proof of Theorem 4.1

The proof compares the iterated mean-field state with the state generated by the optimal policy. It uses the independence of K* from the mean-field state and bounds error terms under a contraction condition.

D.1 Proof of Theorem 4.1

  • K* is independent of the mean-field state, so the proof treats it as a fixed parameter.The proof compares the optimal-policy-generated mean-field state with the iterates produced by Algorithm 1.Source: §D.1 · p. 37
  • The proof bounds three error terms when comparing the current iterate with the optimal-policy-generated mean-field state.It introduces E1, E2, and E3 after expressing the difference using the triangle inequality.Source: §D.1 · p. 37
  • Under Assumption 3.1, L0 < 1; with the proof’s choice S = O(log(1/ε)), the stated bound holds with probability at least 1 − ε^5.Source: §D.1 · p. 39

D.2 Proof of Theorem B.4

The proof establishes the final cost bound by controlling the K and b updates separately. It uses gradient dominance for J1 and bounds the corresponding cost gaps for both parameter updates.

D.2 Proof of Theorem B.4

  • The proof bounds J1(KN)−J1(K*) below ε/2 with high probability.This is Part 1 of the proof.Source: §D.2 · p. 40
  • The proof bounds J2(KN,bH)−J2(K*,b*) below ε/2 with high probability.This is Part 2 of the proof.Source: §D.2 · pp. 40, 43
  • J(KN,bH)−J(K*,b*)<ε follows by separately bounding the J1 and J2 cost gaps.The proof treats each gap as less than ε/2 with high probability.Source: §D.2 · p. 40
  • J1(K) is gradient dominant for parameters K with finite cost.The proof invokes this property to control the K-update cost gap.Source: §D.2 · pp. 40, 43

D.3 Proof of Theorem B.8

The proofs develop supporting theoretical arguments for equilibrium and optimization, establishing a saddle point, controlling a primal-dual gap, and proving equilibrium uniqueness via contraction. They also provide supporting analysis using truncation, mixing, and results on optimization, cost decomposition, and value and action-value functions.

D.3 Proof of Theorem B.8

  • Lemma D.6 places the generated ζK,b and the associated ξ(ζ) within their respective feasible sets.Source: §D.3 · p. 45
  • Theorem B.8’s proof establishes a saddle point, then controls the primal-dual gap using truncation, β-mixing, and a convex-concave stochastic-gradient bound.The trajectory is shown to be β-mixing when ρ(A − BK) < 1.Source: §D.3 · pp. 46, 49, 50, 51

E.1 Proof of Proposition 3.2

  • The proof of Proposition 3.2 parameterizes policies by K and b and defines a metric on the policy space Π.The metric uses positive constants c1 and c2.Source: §E.1 · p. 52
  • Under Assumption 3.1, the operator Λ is a contraction, so Banach’s fixed-point theorem gives a unique fixed point and equilibrium pair for Problem 2.1.The contraction factor is L0 = L1L3 + L2 < 1.Source: §E.1 · p. 54

E.2 Proof of Proposition 3.4

  • The KKT conditions are used to solve the constrained optimization problem and obtain its minimizer.The proof then substitutes the minimizer into J2(K, b) and derives expressions involving K_NK and the policy parameter.Source: §E.2 · pp. 54–55

E.3 Proof of Proposition B.2

  • The proof derives a cost decomposition involving J1(K), J2(K, b), and the noise term σ^2 · tr(R).The displayed decomposition also includes a mean-field-dependent term, but its expression is incomplete in the supplied passage.Source: §E.3 · p. 56

E.4 Proof of Proposition 3.3

  • The Hessian of J2(K, b) is positive definite and independent of b.The proof denotes its minimum singular value, though the supplied passages do not include its expression.Source: §E.4 · p. 56

E.5 Proof of Proposition B.3

  • The proof uses the closed-loop recursion y_{t+1} = (A − BK)y_t to derive expressions involving Υ_K and q_{K,b}.The supplied passages do not show those expressions.Source: §E.5 · p. 57

E.6 Proof of Proposition B.1

  • The value function V_{K,b}(x) is quadratic, and its expectation under the policy’s stationary distribution is zero.The quadratic form is stated as x^T Gx + r^T x + h, with G, r, and h functions of K and b.Source: §E.6 · p. 58

E.7 Proof of Proposition B.5

  • The proof establishes that Q_{K,b}(x, u) takes a linear form with a scalar term β_{K,b} independent of x and u.The supplied passages do not include the full linear expression.Source: §E.7 · p. 59

E.8 Proof of Proposition B.6

The proof establishes stability and stationary-distribution uniqueness for the transition under consideration, along with invertibility and bounds for ΘK,b. It also derives Lemma D.1 and bounds used in Lemma D.2.

E.8 Proof of Proposition B.6

  • ρ(A−BK)<1 establishes stability, and the resulting Markov chain has a unique stationary distribution.The proof uses this stability to verify the transition in (E.24).Source: §E.8 · p. 60
  • ΘK,b is invertible, with its norm and inverse-related bounds controlled by ∥K∥₂ and ρ(A−BK).The proof also establishes a positive lower bound for σmin(eΘK,b).Source: §E.8 · pp. 60–61

F.1 Proof of Lemma D.1

  • The proof of Lemma D.1 propagates y_t under yt+1=(A−BK2)yt and uses ΥK1 to derive the lemma.Source: §F.1 · pp. 61–62

F.2 Proof of Lemma D.2

  • For D.16, positivity of a quadratic-form term yields a lower bound on DK,K*(y); for D.17, the proof invokes K*’s optimality.Source: §F.2 · p. 63

F.3 Proof of Lemma D.3

These proofs establish bounds on update quantities and cost differences, then verify that the relevant variables remain in their specified sets. They rely on probability bounds and algebraic estimates stated in the proof passages.

F.3 Proof of Lemma D.3

  • The proof bounds ∥P eKₙ₊₁−PKₙ₊₁∥₂ and establishes (F.13) with probability at least 1−ε¹⁵.Source: §F.3 · pp. 64, 66

F.4 Proof of Lemma D.4

  • The cost difference J1(K)−J1(K*) is expressed as a trace difference and as an expectation of quadratic forms.The expectation is under yt+1=(A−BK)yt with y0∼N(0,Ψε).Source: §F.4 · pp. 66–67

F.5 Proof of Lemma D.5

  • The proof combines cost nonincrease from b0 with a bound on ∥μKN,b∥₂ to obtain a high-probability estimate.Source: §F.5 · p. 68

F.6 Proof of Lemma D.6

  • D.6 shows ζK,b∈Vζ and ξ(ζ)∈Vξ for every ζ∈Vζ, using the expected cost-feature vector form.Source: §F.6 · pp. 70–72

F.7 Proof of Lemma D.7

The proofs bound Gaussian mean and covariance estimates, control successive approximation gaps, and derive expectation and matrix bounds used in the lemmas. They also calculate the expected cost-feature vector from the quadratic cost and feature definition.

F.7 Proof of Lemma D.7

  • The Gaussian mean and covariance estimates satisfy bounds scaled by (1−ρ)^−2 and (1−ρ)^−1, respectively, with probability at least 1−eT^−6.The proof assumes ez0∼N(μ†,Σ†).Source: §F.7 · pp. 72–73

F.8 Proof of Lemma D.8

  • The proof controls |F−bF| and |bF−eF| separately, then combines the bounds to control |F−eF|.Source: §F.8 · pp. 74–75

F.9 Proof of Lemma E.2

  • In the Gaussian-moment calculation for Lemma E.2, the centered terms A2 and A3 vanish.Source: §F.9 · p. 76

F.10 Proof of Lemma E.3

  • The proof bounds the relevant ΘK,b quantity by a constant depending on ∥K∥₂ and ρ(A−BK).Source: §F.10 · pp. 78–79

F.11 Proof of Lemma F.2

  • Lemma F.2’s expected cost-feature vector is derived by evaluating D1 and D2 using the quadratic cost and feature-vector definition.Source: §F.11 · pp. 79–81

G Auxiliary Results

This section collects auxiliary Gaussian and matrix results: a Gaussian quadratic-form identity, a symmetric Kronecker-product eigenvalue formula, and a Gaussian-vector bound setup.

G Auxiliary Results

  • For w ∼ N(0, I), E[(w⊤Uw)(w⊤Vw)] = 2 tr(UV) + tr(U)·tr(V) for symmetric matrices U and V.The passage attributes the detailed proof to Rudelson et al. (2013).Source: G Auxiliary Results · pp. 81–82
  • For commuting symmetric M and N, M ⊗s N has eigenvalues (α_iβ_j + α_jβ_i)/2 for 1 ≤ i ≤ j ≤ n.Here α_i and β_i are their eigenvalues in a common orthogonal eigenbasis; the formula gives n(n + 1)/2 eigenvalues.Source: G Auxiliary Results · p. 81
  • Lemma G.3 introduces a bound involving A and a standard Gaussian vector η, with an absolute constant C and a threshold t ≥ 0.The supplied statement does not include the bound's expression.Source: G Auxiliary Results · p. 82

Related papers

Loading 1910.07498v1…