Data-Driven Network LQG Mean Field Games with Heterogeneous Populations via Integral Reinforcement Learning

The gist: This paper establishes a data-driven solution for infinite horizon linear quadratic Gaussian Mean Field Games with network-coupled heterogeneous agent populations where the dynamics of the agents are unknown.

Problem Formulation

The problem considers a population of agents grouped into K classes, where each class k contains a large number of identical agents, and an agent ak,i has dynamics given by dxk,i(t) = (Akxk,i(t) + Bkuk,i(t))dt + Dkdwk,i(t) (2). The agent seeks to find the control uk,i that minimizes the class-specific discounted cost functional Jk(uk,i) = E Z ∞ 0 e−ρt x˜⊤ k,iQkx˜k,i + u⊤ k,iRkuk,i dt (2). The resulting H = JHkmK ∈ R N×N with N = PK k=1 nk is the network coupling matrix (2). Under Assumption 1, the pair (Ak − 1/2 ρIN, Bk) is stabilizable and the pair (Ak − 1/2 ρIN, Q 1/2 k) is observable for all class k ∈ K.

Solution Technique

The solution technique relies on Integral Reinforcement Learning and Kleinman’s iteration for solving algebraic Riccati equations (ARE). The resulting algorithm uses trajectory data to generate network-coupled MFG strategies for agents and does not require parameters of agents’ dynamics (Abstract). To establish the multi-class LQG-MFG strategy purely based on trajectory data, the approach combines the Kleinman algorithm (Kleinman, 1968) for iteratively solving symmetric ARE and the IRL technique for updating strategies based on trajectory data (3).

Key Results and Algorithm Steps

The paper proposes a method to learn the agent strategies from trajectory data by combining Kleinman’s iteration with IRL. The iterative procedure involves solving equation (9) for Pk, for all k, and equation (8b) for omega (3). The resulting matrices P(l)k, omega(l), L(l)P,k and L(l)omega satisfy convergence properties where lim l→∞ L(l)P,k = L∗P,k and lim l→∞ P(l)k = P∗,k (Proposition 2). The algorithm requires multiple trajectories of the states and control inputs of the representative agent ak,1 for all k ∈ K (Remark 4).

Algorithm 1 details the process:

1. Initialization: Choose L(0)omega s.t. A− 1/2 ρIN −BL(0)omega is Hurwitz and s.t. the associated class-specific L(0)P,k ensure Ak−1/2 ρInk−BkL(0)P,k are Hurwitz for all k (Algorithm 1).

2. Data Collection: Apply U(t) = −L(0)omega X(t) + l(t) to global system composed of selected agents and compute data vectors δP,k, Ixx,k, Ixα,k, δt for tj, j ∈ 1 to l until rank(Ξ1,k) and rank(Ξ2) satisfy persistence of excitation (Assumption 4) (Algorithm 1).

3. Policy Iteration: Repeat solving for class-specific parameters using equation (19): [Pˆ(l)k vec(L(l)P,k) θ(l)P,k] = (Ξ⊤1,kΞ1,k −1 Ξ⊤1,k∆4k), and solving for global parameters using equation (20): [omegaˆ(l) vec(L(l)omega) θ(l)omega] = (Ξ⊤2 Ξ2 −1 Ξ⊤2 ∆5). Update l ← l + 1 until kP(l)k −P(l−1)k k ≤ ε for all k & komega(l−omega)(l-1)k ≤ ε are defined for the interval [t1, tl +∆t] and satisfy Assumption 4 (Algorithm 1).

Convergence and Validation

Under Assumptions 1,2, and 3, the resulting matrices P(l)k and P(l)omega converge to their ground truth values as l→∞ (Proposition 2). The convergence is demonstrated numerically using a representative agent ak,1 for each class k (Table 2 and Table 3). Furthermore, the mean field trajectories are computed offline using the learned control gains, and validation involves simulating a finite population of 50 agents per class with control input uk,i(t) = −LP,kxk,i(t) − LΠ,kX(50)(t) (23). The results comparing trajectories using learned gains to those using gains computed by care serving as ground truth are presented in Fig. 2 (Fig. 2).

Conclusion

This paper established a data-driven algorithm for computing strategies for continuous-time infinite horizon LQG MFGs with heterogeneous network-coupled populations that contain completely unknown dynamics (5). Under conditions on the persistency of excitation and on the existence of unique stabilizing solution for the corresponding AREs, the algorithm converges to the MFG strategies that depend on the classes and network couplings (5). Future investigations should extend these solutions to cases with network-coupled dynamics, directed network couplings, finite time horizons, and nonlinear agent dynamics (5).

--- Page 1 ---

Data-Driven Network LQG Mean Field Games with Heterogeneous Populations via Integral Reinforcement Learning ⋆ Jean Zhu ∗ Shuang Gao ∗∗ Department of Mechanical Engineering, Polytechnique Montr´eal & GERAD, Montreal, Canada (email: jean.zhu@etud.polymtl.ca) shuang.gao@polymtl.ca Department of Electrical Engineering, Polytechnique Montr´eal & GERAD, Montreal, Canada (email: shuang.gao@polymtl.ca) Abstract: This paper establishes a data-driven solution for infinite horizon linear quadratic Gaussian Mean Field Games with network-coupled heterogeneous agent populations where the dynamics of the agents are unknown. The solution technique relies on Integral Reinforcement Learning and Kleinman’s iteration for solving algebraic Riccati equations (ARE). The resulting algorithm uses trajectory data to generate network-coupled MFG strategies for agents and does not require parameters of agents’ dynamics. Under technical conditions on the persistency of excitation and on the existence of unique stabilizing solution to the corresponding AREs, the learned network-coupled MFG strategies are shown to converge to their true values. Keywords: Mean field games, data-driven control, integral reinforcement learning, adaptive dynamic programming, multi-agent systems

--- Page 2 ---

0n×m ∈ R n×m the zero matrix, and 1n×m ∈ R n×m the matrix of ones. For a matrix A ∈ R m×n, vec(A) corresponds to the mn-dimensional vector formed by stacking the columns of A on top of each other. ⊗ denotes the Kronecker product between two matrices. A 0 (resp. A ≻ 0) denotes that matrix A is positive semidefinite (resp. positive definite). diag(M1,..., MN) denotes the matrix with diagonal blocks M1, · · ·, MN and zero elsewhere. For K, nk, ml N, M ∈ N, M = JMklK ∈ R N×M, where N = PK k=1 nk and M = PK l=1 ml denotes a block matrix with blocks Mkl ∈ R n×m, with k, l ∈ 1 to K. Consider a matrix A ∈ R k×k. A is called strong (k1, k2) c-splitting if, of its k = k1 +k2 eigenvalues, it has k1 eigenvalues in the open left half plane, and k2 in the open right half plane, with none on the imaginary axis. An l-dimensional subspace (with l ≤ k) of A denoted by V of R n is an invariant subspace if AV ⊂ V; in this case, AV = V A0 for some A0 ∈ R l×l where V ∈ R n×l and span(V) = V. If A0 is Hurwitz, V is called a stable invariant subspace. An l-dimensional subspace (with l ≤ k) of A ∈ R k×k is called a graph subspace if it’s spanned by the columns of a k × l matrix whose first l rows form an invertible submatrix (see Huang and Zhou (2020)).

--- Page 3 ---

Consider a population of agents grouped into K classes, where each class k ∈ K contains a large number of identical agents. Let ck denotes the number of agents in class k. An agent ak,i of class k has dynamics given by dxk,i(t) = (Akxk,i(t) + Bkuk,i(t))dt + Dkdwk,i(t) (1). where xk,i(t) ∈ R nk and uk,i(t) ∈ R mk are the states and control inputs respectively.

1. The system can be improved to learn network-coupled Mean Field Game (MFG) strategies for agents with unknown dynamics using Integral Reinforcement Learning (IRL). This allows for the generation of network-coupled MFG strategies for agents that do not require parameters of agents’ dynamics.

2. The improved AI system can solve the infinite horizon linear quadratic Gaussian MFG problem where agent dynamics are completely unknown. It achieves this by using a data-driven algorithm that generates network-coupled MFG strategies from trajectory data, extending existing IRL methods for homogeneous LQGMFG.

3. The system can perform adaptive control for heterogeneous populations in continuous-time settings, such as those found in renewable energy grids or autonomous vehicle networks. This capability is realized through the learned control input structure derived from the solution to the Algebraic Riccati Equations (AREs).