betaFeedback

WorksEngineering

Learning monotone game-theoretic linear MPC

Abstract

We propose a method to learn a game-theoretic model predictive control (GT-MPC) law by imitation from input and output data of a running multi-agent system. By interpreting the recorded inputs as the first moves of the equilibria of a game played by the agents, we learn the GT-MPC weights under hard input constraints and soft output constraints, without requiring the agents to reveal their objectives. We also impose that the resulting generalized Nash equilibrium (GNE) problem is strongly monotone, which ensures the existence and uniqueness of the equilibrium and, hence, that the learned GT-MPC law is well defined and can be evaluated efficiently online by variational GNE-seeking algorithms for linear-quadratic games. Moreover, strong monotonicity implies that the equilibrium is almost everywhere differentiable with respect to the references and the weights, which enables automatic differentiation for gradient-based optimization. In addition, we promote closed-loop stability of the unconstrained equilibrium feedback by incorporating a penalty that involves a jointly learned quadratic Lyapunov function. Learning a GT-MPC formulation enables us to explain the agents' objectives, reproduce their behavior in simulation in new scenarios, optimize their set-points, design mechanisms, and enforce additional constraints. A numerical example illustrates the approach.

Introduction

In game-theoretic model predictive control (GT-MPC), several agents act on a common dynamical system, each optimizing a personal objective that depends on the other agents’ moves under local and shared constraints, and applying the first move of the resulting generalized Nash equilibrium (GNE) at every time step [26, 18, 19, 8, 17, 13]. Each GT-MPC problem is a finite-horizon dynamic game; see [16, 21, 23] for solution algorithms and multi-vehicle applications. Modeling the agents’ costs is often difficult: the agents may be unwilling to disclose their objectives and strategies for privacy reasons, and in many applications the plant is even operated without explicit objectives to minimize, e.g., by standard decentralized control loops or even manually. A natural goal is then to learn, from the observed actions only, a GT-MPC law that reproduces them, so that the agents do not have to reveal their strategies, and that adds the main benefit of MPC, namely, handling input and output constraints. Moreover, once a game representation of agents’ behavior is available, it can be used for higher-level tasks, such as optimization of the set-point signals that enter the game at each step. It also allows reproducing the agents’ behavior in closed-loop simulation, e.g., on a digital twin of the plant, to evaluate what-if scenarios that have not been observed yet.

In this paper we reach this goal by imitation: we learn a game whose equilibria, given reference signals and estimated states, reproduce the agents’ actions. We restrict our attention to strongly monotone linear-quadratic (LQ) games. Roughly speaking, monotonicity plays for games the role that convexity plays for optimization: if the joint feasible set is nonempty, closed, and convex, a strongly monotone game has a unique variational GNE for every value of the parameter (here, the state estimate, reference, and previous input) [15]. So the learned control law is well defined and, as LQ-GNE problems can be solved efficiently [3, 7, 5], easily computable. Moreover, the variational GNE of a strongly monotone LQ game is a path-differentiable function of the parameters, whose derivatives can be computed by automatic differentiation [10], which makes gradient-based learning and equilibrium design well founded.

Unlike [9] and [1], who fit the agents’ objectives by minimizing the residuals of the variational inequality and of the KKT conditions at observed equilibria, respectively, we impose strong monotonicity of the learned game by construction, as also done in [22] through an LMI. Moreover, in [9, 1, 22] the number of unknowns grows linearly with the number of samples, as the dual variables of each sample are optimized. Finally, in our setting only the first move of each equilibrium is observed, not the entire sequence of planned moves that the methods in [9, 1, 22] would require to fit a GT-MPC formulation. Learning was also combined with GT-MPC in [20] for two autonomous vehicles: the GNEs of a known constrained dynamic game are computed offline from random initial conditions, and a neural network trained to predict their reward outcome is used as the terminal cost of each agent’s MPC problem. Here, instead, we learn the unknown costs from closed-loop data, do not assume decoupled dynamics, and solve the learned LQ game online.

We define a class of GT-MPC problems with soft shared output constraints based on a linear state-space model realization learned from the available input / output data. Then, we learn agent-specific weights and slack penalties by a bilevel problem whose inner problems are the LQ-GNE problems of the game at each datapoint, in which strong monotonicity holds by construction and closed-loop stability of the unconstrained Nash equilibrium feedback is enforced by a penalty involving a jointly learned quadratic Lyapunov function, so that the problem can be solved by L-BFGS-B. We illustrate in a numerical example that we can reconstruct an underlying game played by the agents very precisely and shape closed-loop behavior by reference optimization.

Section 2 presents the problem setting, Section 3 recalls monotone LQ games, Section 3.1 characterizes the monotonicity of the GT-MPC game, Section 3.2 presents the bilevel learning problem and its solution algorithm, Section 3.3 closed-loop stability, Section 4 a numerical example, and Section 5 conclusions. The code is available at https://github.com/bemporad/gtmpc_learn.

Notation. We write InI_n for the n×nn \times n identity, ⊗\otimes for the Kronecker product, and sym⁡(M)=12(M+MT)\operatorname{sym}(M) = \frac{1}{2}(M + M^{\mathsf{T}}) for the symmetric part of a square matrix MM. For symmetric matrices, M⪰NM \succeq N means that M−NM - N is positive semidefinite. We write ∥⋅∥2\lVert\cdot\rVert_2 for the Euclidean norm and ∥⋅∥F\lVert\cdot\rVert_F for the Frobenius norm. For a vector xx whose entries are associated with the agents, xix_i collects the entries of agent ii and x−ix_{-i} those of all the other agents. For a matrix AA acting on such vectors, AijA_{ij} is the block that maps xjx_j into the entries of agent ii. We use kk for sample steps and tt for prediction steps. For a vector a∈Rna \in\mathbb{R}^n, [a]+=max⁡{a,0}[a]_+ = \max\{a, 0\}. For a differentiable vector- or matrix-valued function f(θ)f(\theta), df=∑l∂f∂θldθl\mathrm{d}f = \sum_l \frac{\partial f}{\partial\theta_l}\mathrm{d}\theta_l denotes its differential. For a matrix GG, a vector bb, and a set of indices SS, GSG_S is the submatrix of the rows of GG indexed by SS, and bSb_S the subvector of bb indexed by SS.

Data collection and problem setup

We consider a multi-agent process with NN agents, whose behavior we want to imitate, in which agent ii applies the input uk,i∈Rniu_{k,i} \in\mathbb{R}^{n_i} at sample step kk. We write uk=(uk,1,…,uk,N)∈Rnuu_k = (u_{k,1}, \ldots, u_{k,N}) \in\mathbb{R}^{n_u}, with nu=∑i=1Nnin_u = \sum_{i=1}^{N} n_i, and yk∈Rnyy_k \in\mathbb{R}^{n_y} for the measured outputs. We record piecewise-constant references rkj∈Rnyr_k^j \in\mathbb{R}^{n_y}, inputs ukju_k^j, and outputs ykjy_k^j in nen_e experiments, each of length NjN_j, where the input and output measurements can be noisy.

Our goal is to learn a GT-MPC controller from the collected data, as described in the sequel, which imitates the behavior of the agents in tracking their respective references while respecting the following additional input and output constraints:

uk∈UΔuk∈ΔUyk∈Y(1)u_k \in\mathcal{U} \qquad\Delta u_k \in\Delta\mathcal{U} \qquad y_k \in\mathcal{Y} \tag*{(1)}

where Δuk=uk−uk−1\Delta u_k = u_k - u_{k-1} is the vector of input increments and U⊆Rnu\mathcal{U} \subseteq\mathbb{R}^{n_u}, ΔU⊆Rnu\Delta\mathcal{U} \subseteq\mathbb{R}^{n_u}, Y⊆Rny\mathcal{Y} \subseteq\mathbb{R}^{n_y} are polyhedral sets. For simplicity, we assume that U={u∣umin⁡≤u≤umax⁡}\mathcal{U} = \{u \mid u_{\min} \le u \le u_{\max}\}, ΔU={Δu∣Δumin⁡≤Δu≤Δumax⁡}\Delta\mathcal{U} = \{\Delta u \mid\Delta u_{\min} \le\Delta u \le\Delta u_{\max}\}, Y={y∣ymin⁡≤y≤ymax⁡}\mathcal{Y} = \{y \mid y_{\min} \le y \le y_{\max}\}, with possibly infinite entries in umin⁡u_{\min}, umax⁡u_{\max}, ymin⁡y_{\min}, and ymax⁡y_{\max}. We denote by ui,min⁡u_{i,\min}, ui,max⁡u_{i,\max}, Δui,min⁡\Delta u_{i,\min}, and Δui,max⁡\Delta u_{i,\max} the entries of umin⁡u_{\min}, umax⁡u_{\max}, Δumin⁡\Delta u_{\min}, and Δumax⁡\Delta u_{\max} associated with agent ii. As in standard MPC practice, constraints on the inputs and their increments are enforced as hard constraints, while output constraints are treated as soft constraints.

Our aim is to learn a GT-MPC controller of the following form, generalizing the one suggested in [5 Section 5.2]:

min⁡xi,ϵi∑t=0T−1(y(t+1)−rk)⊤Qy,i(y(t+1)−rk)+∑t=0Tu−1Δu(t)⊤QΔu,iΔu(t)+qϵ,iϵi+Qϵ,iϵi2subject toξ(t+1)=Aξ(t)+∑i=1NBiui(t),t=0,…,T−1ξ(0)=ξ^ky(t)=Cξ(t),t=1,…,Tui,min⁡≤ui(t)≤ui,max⁡,t=0,…,Tu−1Δui,min⁡≤Δui(t)≤Δui,max⁡,t=0,…,Tu−1ymin⁡−(∑j=1Nϵj)1≤y(t)≤ymax⁡+(∑j=1Nϵj)1,t=1,…,Tcϵi≥0,i=1,…,N(2)\begin{aligned} \min_{x_i,\epsilon_i}\quad&\sum_{t=0}^{T-1}\left(y(t+1)-r_k\right)^{\top}Q_{y,i}\left(y(t+1)-r_k\right)+\sum_{t=0}^{T_u-1}\Delta u(t)^{\top}Q_{\Delta u,i}\Delta u(t)\\ &+q_{\epsilon,i}\epsilon_i+Q_{\epsilon,i}\epsilon_i^2\\ \text{subject to}\quad&\xi(t+1)=A\xi(t)+\sum_{i=1}^{N}B_i u_i(t),\quad t=0,\ldots,T-1\\ &\xi(0)=\hat{\xi}_k\\ &y(t)=C\xi(t),\quad t=1,\ldots,T\\ &u_{i,\min}\leq u_i(t)\leq u_{i,\max},\quad t=0,\ldots,T_u-1\\ &\Delta u_{i,\min}\leq\Delta u_i(t)\leq\Delta u_{i,\max},\quad t=0,\ldots,T_u-1\\ &y_{\min}-\left(\sum_{j=1}^{N}\epsilon_j\right)\mathbf{1}\leq y(t)\leq y_{\max}+\left(\sum_{j=1}^{N}\epsilon_j\right)\mathbf{1},\quad t=1,\ldots,T_c\\ &\epsilon_i\geq0,\quad i=1,\ldots,N \tag*{(2)} \end{aligned}

where ξ^k\hat{\xi}_k is the estimate at sample step kk of the state vector ξ∈Rn\xi\in\mathbb{R}^{n} associated with the prediction model (A,B,C)(A,B,C), with B=[B1 ⋯ BN]B=[B_1\ \cdots\ B_N] partitioned by agent according to the input allocation, Δu(t)=u(t)−u(t−1)\Delta u(t)=u(t)-u(t-1) with u(−1)=uk−1u(-1)=u_{k-1}, and xi={Δui(t)}t=0Tu−1x_i=\{\Delta u_i(t)\}_{t=0}^{T_u-1}, 1≤Tu≤T1\leq T_u\leq T, with Δu(t)=0\Delta u(t)=0 for t=Tu,…,T−1t=T_u,\ldots,T-1, represents the sequence of input increments decided by agent ii, ϵi\epsilon_i is a slack variable for softening the shared output constraints, and TT, Tu≤TT_u\leq T, and Tc≤TT_c\leq T are, respectively, the prediction, control, and constraint horizons. Note that, in general, the agent-specific weights Qy,iQ_{y,i} and QΔu,iQ_{\Delta u,i} consider the entire vectors of tracking-errors and input-increments, respectively.

Problem (2) can be recast as a parametric LQ-GNE problem with parameter pk=(ξ^k,uk−1,rk)∈Rnpp_k=(\hat{\xi}_k,u_{k-1},r_k)\in\mathbb{R}^{n_p}, np=n+nu+nyn_p=n+n_u+n_y, and decision vector z=(x,ϵ)z=(x,\epsilon), where x=(x1,…,xN)∈RnuTux=(x_1,\ldots,x_N)\in\mathbb{R}^{n_uT_u} collects the input increments of all agents and ϵ=(ϵ1,…,ϵN)\epsilon=(\epsilon_1,\ldots,\epsilon_N). By letting z⋆(pk)=(x⋆(pk),ϵ⋆(pk))z^\star(p_k)=(x^\star(p_k),\epsilon^\star(p_k)) denote the variational GNE of (2) corresponding to pkp_k, the MPC action at sample step kk is given by the first input increment of the optimal sequence, i.e., ukMPC=uk−1+Efx⋆(pk)u_k^{\mathrm{MPC}}=u_{k-1}+E_fx^\star(p_k), where Ef∈{0,1}nu×nuTuE_f\in\{0,1\}^{n_u\times n_uT_u} selects the first increments Δu(0)=(Δu1(0),…,ΔuN(0))\Delta u(0)=(\Delta u_1(0),\ldots,\Delta u_N(0)) from xx.

As we only have input/output data available, we first need to identify a linear discrete-time model (A,B,C)(A,B,C), together with the initial state ξ^0j\hat{\xi}_0^j of each experiment, by solving the standard output-error minimization problem

min⁡A,B,C,ξ^01,…,ξ^0ne∑j=1ne∑k=0Nj−1∥ykj−Cξkj∥22+ϕ(A,B,C,ξ^01,…,ξ^0ne)subject toξk+1j=Aξkj+Bukj,ξ0j=ξ^0j,j=1,…,ne\begin{aligned} \min_{A,B,C,\hat{\xi}_0^1,\ldots,\hat{\xi}_0^{n_e}}\quad&\sum_{j=1}^{n_e}\sum_{k=0}^{N_j-1}\left\|y_k^j-C\xi_k^j\right\|_2^2+\phi(A,B,C,\hat{\xi}_0^1,\ldots,\hat{\xi}_0^{n_e})\\ \text{subject to}\quad&\xi_{k+1}^j=A\xi_k^j+Bu_k^j,\quad\xi_0^j=\hat{\xi}_0^j,\quad j=1,\ldots,n_e \end{aligned}

where ϕ\phi is a small ℓ2\ell_2 regularization function, as described in [4] and the associated jax-sysid package. Then, we run a Kalman filter based on the resulting model, whose noise covariances are tuning parameters, to get state estimates {ξ^kj}k=0Nj−1\{\hat{\xi}_k^j\}_{k=0}^{N_j-1}, starting from ξ^0j\hat{\xi}_0^j, given the corresponding inputs and outputs in experiment jj.

The obtained datasets {(rkj,ukj,ϵ^kj)}\{(r_k^j,u_k^j,\hat{\epsilon}_k^j)\} are used for learning a parametric linear-quadratic GNE problem of the form (2) by fitting the output and input-increment weights Qy,iQ_{y,i}, QΔu,iQ_{\Delta u,i}, and the weights on slack variables qϵ,iq_{\epsilon,i}, Qϵ,iQ_{\epsilon,i} to best replicate the observed behavior of the expert controller, i.e., we wish that

uk−1j+Efx⋆(pkj)≈ukj(3)u_{k-1}^j+E_{\mathrm{f}}x^\star(p_k^j)\approx u_k^j \tag*{(3)}

where x⋆(pkj)x^\star(p_k^j) is the vector of input increments of the variational GNE of (2) for p=pkjp=p_k^j, i.e., we interpret the measured moves ukju_k^j of the agents as the first moves of the GNE of a game of the form (2) played by the agents at step kk. Once the game is learned, the GT-MPC law applies the first move of the GNE, at which all the agents play best responses to each other. We also require that the resulting game be strongly monotone, so that its variational GNE, and hence the left-hand side of (3), is unique whenever (2) is feasible.1

Learning monotone GT-MPC games

In a parametric LQ game with constant agents’ Hessian matrices and affine dependence on the parameter pp in the linear cost terms, agent ii minimizes over zi=(xi,ϵi)z_i=(x_i,\epsilon_i) the cost

Ji(z;p)=12ziTAˉiizi+∑j≠iziTAˉijzj+qˉi(p)Tzi+(terms not depending on zi)(4)J_i(z;p)=\frac{1}{2}z_i^\mathsf{T}\bar{A}_{ii}z_i+\sum_{j\ne i}z_i^\mathsf{T}\bar{A}_{ij}z_j+\bar{q}_i(p)^\mathsf{T}z_i+\text{(terms not depending on }z_i\text{)} \tag*{(4)}

where z=(x,ϵ)z=(x,\epsilon), Aˉii\bar{A}_{ii} is symmetric, and qˉi(p)\bar{q}_i(p) is affine in pp. Agent ii’s problem is convex when Aˉii⪰0\bar{A}_{ii}\succeq0. The pseudogradient F(z;p)F(z;p) collects the agents’ gradients ∇ziJi(z;p)\nabla_{z_i}J_i(z;p) with respect to their own decision variables, in the same ordering as zz, so that F(z;p)=Aˉz+qˉ(p)F(z;p)=\bar{A}z+\bar{q}(p), with Aˉ=[Aˉij]∈Rnz×nz\bar{A}=[\bar{A}_{ij}]\in\mathbb{R}^{n_z\times n_z} and qˉ\bar{q} collecting the vectors qˉi\bar{q}_i, where nz=nuTu+Nn_z=n_uT_u+N. The game is monotone with constant μ≥0\mu\ge0 [15, 24] if

(F(z;p)−F(z′;p))T(z−z′)≥μ∥z−z′∥2(F(z;p)-F(z';p))^\mathsf{T}(z-z')\ge\mu\lVert z-z'\rVert^2

for all zz, z′z', which here is the same as

sym⁡(Aˉ)⪰μInz.(5)\operatorname{sym}(\bar{A})\succeq\mu I_{n_z}. \tag*{(5)}

When μ>0\mu>0 the game is strongly monotone. With a shared constraint z∈Z(p)z\in\mathcal{Z}(p), where Z(p)\mathcal{Z}(p) is nonempty, closed, and convex, the variational GNEs are the solutions of the variational inequality defined by F(⋅;p)F(\cdot;p) on Z(p)\mathcal{Z}(p) [14]. Since FF is continuous and strongly monotone, this variational inequality has a unique solution [15], so the game has a unique variational GNE.

Pseudogradient structure

Let ufull=(u(0),…,u(T−1))∈RnuTu_{\mathrm{full} }=(u(0),\ldots,u(T-1))\in\mathbb{R}^{n_uT} denote the input sequence for the full horizon, which is related to the increments xi∈RniTux_i\in\mathbb{R}^{n_iT_u} of the agents as ufull=u_{\mathrm{full}}= (1T⊤⊗Inu)uk−1+∑i=1NΛixi(\mathbf{1}_T^\top\otimes I_{n_u})u_{k-1}+\sum_{i=1}^{N}\Lambda_i x_i, Λi=Π⊗Eˉi⊤\Lambda_i=\Pi\otimes\bar{E}_i^\top, where 1T∈RT\mathbf{1}_T\in\mathbb{R}^T is the vector of ones, Π∈{0,1}T×Tu\Pi\in\{0,1\}^{T\times T_u} has entries Πhl=1\Pi_{hl}=1 if l≤hl\le h and 00 otherwise, and Eˉi∈{0,1}ni×nu\bar{E}_i\in\{0,1\}^{n_i\times n_u} selects ui=Eˉiuu_i=\bar{E}_i u. Then, the explicit form of the predicted outputs Y=(y(1),…,y(T))∈RnyTY=(y(1),\ldots,y(T))\in\mathbb{R}^{n_yT} is the following affine function of (p,x)(p,x):

Y=Φξ^k+ΓufullΦ=[CACA2⋮CAT]Γ=[CB0⋯0CABCB⋯0⋮⋮⋱⋮CAT−1BCAT−2B⋯CB]Y=\Phi\hat{\xi}_k+\Gamma u_{\mathrm{full}}\qquad \Phi=\begin{bmatrix} \mathcal{C}\mathcal{A}\\ \mathcal{C}\mathcal{A}^{2}\\ \vdots\\ \mathcal{C}\mathcal{A}^{T} \end{bmatrix} \qquad \Gamma=\begin{bmatrix} \mathcal{C}\mathcal{B} & 0 & \cdots& 0\\ \mathcal{C}\mathcal{A}\mathcal{B} & \mathcal{C}\mathcal{B} & \cdots& 0\\ \vdots& \vdots& \ddots& \vdots\\ \mathcal{C}\mathcal{A}^{T-1}\mathcal{B} & \mathcal{C}\mathcal{A}^{T-2}\mathcal{B} & \cdots& \mathcal{C}\mathcal{B} \end{bmatrix}

with Φ∈RnyT×n\Phi\in\mathbb{R}^{n_yT\times n} and Γ∈RnyT×nuT\Gamma\in\mathbb{R}^{n_yT\times n_uT} or, equivalently, Y=Φξ^k+Γuuk−1+∑i=1NΓixiY=\Phi\hat{\xi}_k+\Gamma_u u_{k-1}+\sum_{i=1}^{N}\Gamma_i x_i, where Γi=ΓΛi∈RnyT×niTu\Gamma_i=\Gamma\Lambda_i\in\mathbb{R}^{n_yT\times n_iT_u} and Γu=Γ(1T⊗Inu)∈RnyT×nu\Gamma_u=\Gamma(\mathbf{1}_T\otimes I_{n_u})\in\mathbb{R}^{n_yT\times n_u}.

By substituting the predictions in (2), the cost of agent ii is an LQ cost of the form (4), with Aˉii=blkdiag⁡(Aii,2Qϵ,i)\bar{A}_{ii}=\operatorname{blkdiag}(A_{ii},2Q_{\epsilon,i}), Aˉij=blkdiag⁡(Aij,0)\bar{A}_{ij}=\operatorname{blkdiag}(A_{ij},0) for j≠ij\ne i, and qˉi(p)=(qi(p),qϵ,i)\bar{q}_i(p)=(q_i(p),q_{\epsilon,i}), where

Aij=2Γi⊤Qˉy,iΓj+2ITu⊗QΔu,iijA_{ij}=2\Gamma_i^\top\bar{Q}_{y,i}\Gamma_j+2I_{T_u}\otimes Q_{\Delta u,i}^{ij}
qi(pk)=2Γi⊤Qˉy,i(Φξ^k+Γuuk−1−(1T⊗Iny)rk)(6)q_i(p_k)=2\Gamma_i^\top\bar{Q}_{y,i}\left(\Phi\hat{\xi}_k+\Gamma_u u_{k-1}-(\mathbf{1}_T\otimes I_{n_y})r_k\right) \tag*{(6)}

for all i,ji,j, with Qˉy,i=IT⊗Qy,i\bar{Q}_{y,i}=I_T\otimes Q_{y,i}, QΔu,iij=EˉiQΔu,iEˉj⊤∈Rni×njQ_{\Delta u,i}^{ij}=\bar{E}_iQ_{\Delta u,i}\bar{E}_j^\top\in\mathbb{R}^{n_i\times n_j}. So qi(p)q_i(p) is linear in pp. Only the block row ii of QΔu,iQ_{\Delta u,i} enters AA, i.e., agent ii’s own weight QΔu,iiiQ_{\Delta u,i}^{ii} and the cross weights Si=EˉiQΔu,iEˉ−i⊤∈Rni×(nu−ni)S_i=\bar{E}_iQ_{\Delta u,i}\bar{E}_{-i}^\top\in\mathbb{R}^{n_i\times(n_u-n_i)}, where Eˉ−i\bar{E}_{-i} selects u−iu_{-i}; the other blocks of QΔu,iQ_{\Delta u,i} multiply terms that do not depend on xix_i, and do not affect the game.

The row block ii of AA and qq depends only on agent ii’s weights Qy,iQ_{y,i} and QΔu,iQ_{\Delta u,i}. For a fixed model (A,B,C)(\mathcal{A},\mathcal{B},\mathcal{C}), both AA and qq are linear in the weight matrices. The slack ϵi\epsilon_i enters agent ii’s problem only through the terms qϵ,iϵi+Qϵ,iϵi2q_{\epsilon,i}\epsilon_i+Q_{\epsilon,i}\epsilon_i^2 and the shared output constraints. Note that the diagonal block Aii=2Γi⊤Qˉy,iΓi+2(ITu⊗QΔu,iii)A_{ii}=2\Gamma_i^\top\bar{Q}_{y,i}\Gamma_i+2(I_{T_u}\otimes Q_{\Delta u,i}^{ii}) is positive definite when Qy,i⪰0Q_{y,i}\succeq0 and QΔu,iii≻0Q_{\Delta u,i}^{ii}\succ0. Agent ii’s problem (2) is then a strictly convex QP in xix_i, and also in ϵi\epsilon_i when Qϵ,i>0Q_{\epsilon,i}>0.

The pseudogradient of the GT-MPC game is F(z;p)=(Ax+q(p),qϵ+2Qϵϵ)F(z;p)=(Ax+q(p),q_\epsilon+2Q_\epsilon\epsilon), with A=[Aij]∈RnuTu×nuTuA=[A_{ij}]\in\mathbb{R}^{n_uT_u\times n_uT_u}, q=(q1,…,qN)q=(q_1,\ldots,q_N), qϵ=(qϵ,1,…,qϵ,N)q_\epsilon=(q_{\epsilon,1},\ldots,q_{\epsilon,N}) and Qϵ=diag⁡(Qϵ,1,…,Qϵ,N)Q_\epsilon=\operatorname{diag}(Q_{\epsilon,1},\ldots,Q_{\epsilon,N}), whose Jacobian with respect to zz is Aˉ=blkdiag⁡(A,2Qϵ)\bar{A}=\operatorname{blkdiag}(A,2Q_\epsilon), and qˉ(p)=(q(p),qϵ)\bar{q}(p)=(q(p),q_\epsilon). So, by (5), the game is strongly monotone in zz, with constant μ>0\mu>0, if and only if

sym⁡(A)⪰μInuTuQϵ,i≥μ2,i=1,…,N.(7)\operatorname{sym}(A)\succeq\mu I_{n_uT_u}\qquad Q_{\epsilon,i}\ge\frac{\mu}{2},\qquad i=1,\ldots,N. \tag*{(7)}

For a fixed model, the first condition is an LMI in (Qy,i,QΔu,i)i=1N(Q_{y,i},Q_{\Delta u,i})_{i=1}^{N}, and the second one is a simple bound on each quadratic slack penalty.

Proposition 1. Suppose that (7) holds with μ>0\mu>0, that uk−1∈Uu_{k-1}\in\mathcal{U}, and that the bounds on the increments contain 0. Then, for every pp, the GT-MPC game has a unique variational GNE z⋆(p)=(x⋆(p),ϵ⋆(p))z^\star(p)=(x^\star(p),\epsilon^\star(p)).

Proof. The shared feasible set is closed and convex, and it is nonempty, since x=0x=0 with large enough slacks is feasible. By (7), F(⋅;p)F(\cdot;p) is continuous and strongly monotone with constant μ\mu on this set, so the variational inequality that it defines on the set has a unique solution [15], which is the unique variational GNE.

Learning problem

Our goal now is to set up a learning problem that identifies all the weights in (2) such that the resulting game is strongly monotone, i.e., satisfies (7). Since the pseudogradient matrix of the GT-MPC game is constrained to the structure (6), we cannot directly exploit the form A=WTW+D−DT+μInuTuA=W^{\mathsf{T}}W+D-D^{\mathsf{T}}+\mu I_{n_uT_u} that characterizes every strongly monotone LQ game, as was recently shown in [6 Lemma 4.4], where WW is upper triangular and DD is block strictly upper triangular. Instead, let us parametrize the agent-specific weights with variables Cy,i∈Rny×nyC_{y,i}\in\mathbb{R}^{n_y\times n_y}, Ci∈Rni×niC_i\in\mathbb{R}^{n_i\times n_i}, and Si∈Rni×(nu−ni)S_i\in\mathbb{R}^{n_i\times(n_u-n_i)}, i=1,…,Ni=1,\ldots,N, where Qy,i=Cy,iTCy,iQ_{y,i}=C_{y,i}^{\mathsf{T}}C_{y,i}, SiS_i are the cross weights on input increments, and the own weights are

QΔu,iii=CiTCi+(η+c(θ))Inic(θ)=12[μ−λmin⁡(sym⁡(A~(θ)))]+(8)Q_{\Delta u,i}^{ii}=C_i^{\mathsf{T}}C_i+\left(\eta+c(\theta)\right)I_{n_i}\qquad c(\theta)=\frac{1}{2}\left[\mu-\lambda_{\min}\left(\operatorname{sym}(\widetilde{A}(\theta))\right)\right]_+ \tag*{(8)}

where η>0\eta>0 is small and fixed, while A~(θ)\widetilde{A}(\theta) is the pseudogradient matrix (6) obtained with c(θ)=0c(\theta)=0. By (6), adding cInicI_{n_i} to each QΔu,iiiQ_{\Delta u,i}^{ii} provides λmin⁡(sym⁡(A(θ)))≥μ\lambda_{\min}(\operatorname{sym}(A(\theta)))\ge\mu for every θ\theta. The remaining block E‾−iQΔu,iE‾−iT\overline{E}_{-i}Q_{\Delta u,i}\overline{E}_{-i}^{\mathsf{T}} does not affect the game; after learning we set it to SiT(QΔu,iii)−1SiS_i^{\mathsf{T}}(Q_{\Delta u,i}^{ii})^{-1}S_i, the smallest block for which QΔu,i⪰0Q_{\Delta u,i}\succeq0. The slack penalties qϵ,iq_{\epsilon,i} and Qϵ,iQ_{\epsilon,i} are scalars and are kept directly as optimization variables. Then, we learn the agent-specific weights and the slack penalties by solving

min⁡θ1NK∑k=1K∥u‾k(θ)−uk∥22+ρ2∑i=1N(∥Qy,i∥F2+∥QΔu,iii∥F2+2∥Si∥F2)subject toqϵ,i≥0,Qϵ,i≥μ2,i=1,…,N(9)\begin{aligned} \min_{\theta}\quad&\frac{1}{NK}\sum_{k=1}^{K}\left\lVert\overline{u}_k(\theta)-u_k\right\rVert_2^2+\frac{\rho}{2}\sum_{i=1}^{N}\left(\left\lVert Q_{y,i}\right\rVert_F^2+\left\lVert Q_{\Delta u,i}^{ii}\right\rVert_F^2+2\left\lVert S_i\right\rVert_F^2\right)\\ \text{subject to}\quad&q_{\epsilon,i}\ge0,\qquad Q_{\epsilon,i}\ge\frac{\mu}{2},\qquad i=1,\ldots,N \tag*{(9)} \end{aligned}

where θ=(Cy,i,Ci,Si,qϵ,i,Qϵ,i)i=1N\theta=(C_{y,i},C_i,S_i,q_{\epsilon,i},Q_{\epsilon,i})_{i=1}^{N} is the vector that collects all the learnable parameters of the game, uku_k is the measured input at sample step kk, and u‾k(θ)=uk−1+Efx⋆(pk;θ)\overline{u}_k(\theta)=u_{k-1}+E_f x^\star(p_k;\theta) is the first move of the variational GNE

z⋆(pk;θ)=(x⋆(pk;θ),ϵ⋆(pk;θ))z^\star(p_k;\theta)=\left(x^\star(p_k;\theta),\epsilon^\star(p_k;\theta)\right)

of the game (2) with the weights θ\theta at the parameter pkp_k. The scalar ρ>0\rho>0 weights the regularization of the weights Qy,iQ_{y,i}, QΔu,iiiQ_{\Delta u,i}^{ii}, and SiS_i.

Due to the GNE terms u‾k(θ)\overline{u}_k(\theta), the optimization problem in (9) is a bilevel problem, whose lower-level problems are the GNE problems of the game at the parameters pkp_k. By Proposition 1, u‾k(θ)\overline{u}_k(\theta) is uniquely defined for all kk and admissible θ\theta, as the measured inputs satisfy the input constraints. For compactness of notation, in (9) we drop the superscript jj and number all the sample steps of all experiments consecutively as k=1,…,Kk = 1, \ldots, K. We describe below how we solve this bound-constrained bilevel nonlinear least-squares problem with L-BFGS-B [12], including the initial guess and the computation of the GNEs and of their derivatives with respect to θ\theta.

Initialization. We initialize the components of θ\theta as

Cy,i=s InyCi=μ+δ2−η IniSi=0qϵ,i=qϵ0Qϵ,i=Qϵ0C_{y,i} = \sqrt{s}\,I_{n_y} \qquad C_i = \sqrt{\frac{\mu+\delta}{2}-\eta}\,I_{n_i} \qquad S_i = 0 \qquad q_{\epsilon,i} = q_\epsilon^0 \qquad Q_{\epsilon,i} = Q_\epsilon^0
i=1,…,Ni = 1,\ldots,N

where s≥0s \ge0 is a scale factor, δ>0\delta> 0 is small, η≤(μ+δ)/2\eta\le(\mu+\delta)/2, qϵ0>0q_\epsilon^0 > 0, and Qϵ0≥μ/2Q_\epsilon^0 \ge\mu/2. Then (6) gives the symmetric matrix A~(θ)=2sΓˉ⊤Γˉ+(μ+δ)InuTu⪰(μ+δ)InuTu\widetilde{A}(\theta) = 2s\bar{\Gamma}^{\top}\bar{\Gamma} + (\mu+\delta)I_{n_u}T_u \succeq(\mu+\delta)I_{n_u}T_u for every s≥0s \ge0, where Γˉ=[Γˉ1 ⋯ ΓˉN]\bar{\Gamma} = [\bar{\Gamma}_1 \ \cdots\ \bar{\Gamma}_N], so that c(θ)=0c(\theta) = 0 at the initial point. With the slack penalties fixed to qϵ0q_\epsilon^0 and Qϵ0Q_\epsilon^0, we choose ss by minimizing the imitation loss, i.e., the first term of the objective in (9), over a logarithmic grid of values of ss, which requires solving KK LQ-GNE problems for each grid value.

Computing the GNEs and their derivatives. As L-BFGS-B is a gradient-based method, we need to differentiate the LQ-GNEs z⋆(pk;θ)z^\star(p_k;\theta) with respect to θ\theta efficiently. Recall that the pseudogradient of the game is Aˉ(θ)z+qˉ(p)\bar{A}(\theta)z+\bar{q}(p), with Aˉ(θ)=blkdiag⁡(A(θ),2Qϵ)\bar{A}(\theta)=\operatorname{blkdiag}(A(\theta),2Q_\epsilon) and qˉ(p)=(q(p),qϵ)\bar{q}(p)=(q(p),q_\epsilon), and let Gz≤b(pk)Gz \le b(p_k) collect the shared constraints of (2), where bb also depends on uk−1u_{k-1}. As by strong monotonicity (5) matrix Aˉ(θ)\bar{A}(\theta) is invertible, by [7 Lemma 5.1] the variational GNE is zk⋆=z0,k−Aˉ−1G⊤λk⋆z_k^\star= z_{0,k}-\bar{A}^{-1}G^\top\lambda_k^\star, z0,k=−Aˉ−1qˉ(pk)z_{0,k}=-\bar{A}^{-1}\bar{q}(p_k), where λk⋆\lambda_k^\star solves the QP

min⁡λ λ⊤sym⁡(H)λ+q0,k⊤λs.t.Hλ+q0,k≥0, λ≥0(10)\min_{\lambda}\ \lambda^\top\operatorname{sym}(H)\lambda+q_{0,k}^\top\lambda\quad\text{s.t.}\quad H\lambda+q_{0,k}\ge0,\ \lambda\ge0 \tag*{(10)}

with H=GAˉ−1G⊤H=G\bar{A}^{-1}G^\top and q0,k=b(pk)−Gz0,kq_{0,k}=b(p_k)-Gz_{0,k}. Although uˉk(θ)\bar{u}_k(\theta) and its derivatives could be obtained directly by solving (10) with a differentiable QP solver [2, 25], we take a more efficient approach here. Let θj\theta^j be the value of the parameters at the jj-th iteration of the learning algorithm. We compute zk⋆(θj)z_k^\star(\theta^j) by a tailored LQ-GNE solver (such as DR-DAQP [3]) and identify the set Ak(θj)\mathcal{A}_k(\theta^j) of constraints with positive multipliers (we drop the dependence on θj\theta^j from now on for simplicity of notation). Then, we write zk⋆=z0,k−Aˉ−1GAk⊤λAkz_k^\star=z_{0,k}-\bar{A}^{-1}G_{\mathcal{A}_k}^{\top}\lambda_{\mathcal{A}_k}, where GAkAˉ−1GAk⊤λAk=GAkz0,k−bAk(pk)G_{\mathcal{A}_k}\bar{A}^{-1}G_{\mathcal{A}_k}^{\top}\lambda_{\mathcal{A}_k}=G_{\mathcal{A}_k}z_{0,k}-b_{\mathcal{A}_k}(p_k) are the rows of Hλ+q0,k=0H\lambda+q_{0,k}=0 of the active constraints. For a fixed active set, this is a linear system HAk(θ)λAk=hk(θ)H_{\mathcal{A}_k}(\theta)\lambda_{\mathcal{A}_k}=h_k(\theta), with HAk=GAkAˉ−1GAk⊤H_{\mathcal{A}_k}=G_{\mathcal{A}_k}\bar{A}^{-1}G_{\mathcal{A}_k}^{\top} and hk=GAkz0,k−bAk(pk)h_k=G_{\mathcal{A}_k}z_{0,k}-b_{\mathcal{A}_k}(p_k), whose coefficients depend smoothly on θ\theta through Aˉ(θ)\bar{A}(\theta) and qˉ(pk)\bar{q}(p_k). If the rows of GAkG_{\mathcal{A}_k} are linearly independent, the multipliers λAk\lambda_{\mathcal{A}_k} are positive, and the inactive constraints are strictly satisfied, the active set does not change for small perturbations of θ\theta. Then λAk(θ)\lambda_{\mathcal{A}_k}(\theta), zk⋆(θ)z_k^\star(\theta), and hence uˉk(θ)\bar{u}_k(\theta) are smooth functions of θ\theta around θj\theta^j, with dλAk=HAk−1(dhk−dHAkλAk)d\lambda_{\mathcal{A}_k}=H_{\mathcal{A}_k}^{-1}(dh_k-dH_{\mathcal{A}_k}\lambda_{\mathcal{A}_k}), obtained by differentiating HAkλAk=hkH_{\mathcal{A}_k}\lambda_{\mathcal{A}_k}=h_k, and hence dzk⋆=dz0,k−d(Aˉ−1)GAk⊤λAk−Aˉ−1GAk⊤dλAkdz_k^\star= dz_{0,k} - d(\bar{A}^{-1})G^\top_{\mathcal{A}_k}\lambda_{\mathcal{A}_k} - \bar{A}^{-1}G^\top_{\mathcal{A}_k}d\lambda_{\mathcal{A}_k}. In our numerical experiments, we implement the map from θ\theta to the imitation loss through these linear systems in JAX [11].

Closed-loop stability enforcement

Strong monotonicity guarantees that the GT-MPC law is well defined, but not that the closed loop is asymptotically stable. Without constraints, the variational GNE is x⋆(p)=−A(θ)−1q(p)x^\star(p)=-A(\theta)^{-1}q(p), which is linear in p=(ξ^k,uk−1,rk)p=(\hat{\xi}_k,u_{k-1},r_k), so that the vector of first input increments of all agents is Kξ(θ)ξ^k+Ku(θ)uk−1+Kr(θ)rkK_{\xi}(\theta)\hat{\xi}_k+K_u(\theta)u_{k-1}+K_r(\theta)r_k. In closed loop with the identified model and ξ^k=ξk\hat{\xi}_k=\xi_k, the state ζk=(ξk,uk−1)\zeta_k=(\xi_k,u_{k-1}) evolves as ζk+1=M(θ)ζk+Mr(θ)rk\zeta_{k+1}=M(\theta)\zeta_k+M_r(\theta)r_k, for some matrix Mr(θ)M_r(\theta), where M(θ)=[A+BKξ(θ)B(I+Ku(θ))Kξ(θ)I+Ku(θ)]M(\theta)=\begin{bmatrix} A+B K_{\xi}(\theta) & B(I+K_u(\theta)) \\ K_{\xi}(\theta) & I+K_u(\theta) \end{bmatrix}. Under the assumption that the observed multi-agent system generating the training data is asymptotically stable, we can enforce asymptotic stability of the unconstrained closed loop a priori by adding to the objective of (9) the following penalty

ρs[∥LM(θ)L−1∥22−γ2]+2(11)\rho_s\left[\left\|LM(\theta)L^{-1}\right\|_2^2-\gamma^2\right]_+^2 \tag*{(11)}

where ρs>0\rho_s>0 weights the penalty relative to the imitation loss, γ∈(0,1)\gamma\in(0,1) is a desired contraction rate, and the matrix L∈R(n+nu)×(n+nu)L\in\mathbb{R}^{(n+n_u)\times(n+n_u)}, upper triangular with positive diagonal, is learned together with θ\theta. Since ∥LML−1∥2<1\|LML^{-1}\|_2<1 is equivalent to M⊤PM≺PM^\top P M\prec P with P=L⊤LP=L^\top L, a value of ∥LM(θ)L−1∥2\|LM(\theta)L^{-1}\|_2 below 1 certifies the quadratic Lyapunov function ζ⊤Pζ\zeta^\top P\zeta of the unconstrained closed loop. Conversely, by [4 Lemma 1] applied to M/γM/\gamma, for every matrix MM with spectral radius smaller than γ\gamma there exists such an LL, given by the Cholesky factor of the solution of a Lyapunov equation, for which ∥LML−1∥2<γ\|LML^{-1}\|_2<\gamma, so the penalty can be zeroed for every game whose closed-loop matrix M(θ)M(\theta) has spectral radius smaller than γ\gamma. As (11) is a penalty, we check that ∥LM(θ)L−1∥2<1\|LM(\theta)L^{-1}\|_2<1 at the solution and, otherwise, increase ρs\rho_s and solve the problem again starting from the current solution. By the separation principle, stability of M(θ)M(\theta) also implies stability of the nominal closed loop with the Kalman filter when constraints are not active, although it does not guarantee global closed-loop stability under constraints, nor robustness to the mismatch between the identified model and the actual process.

Numerical example

Generating system. We consider a randomly generated open-loop stable process with nu=3n_u=3 inputs, ny=3n_y=3 outputs, n=4n=4 states, and N=3N=3 agents, each commanding one input. The constraints are ∣ui∣≤0.15|u_i|\le0.15, ∣Δui∣≤0.1|\Delta u_i|\le0.1, and we want to enforce ∣yi∣≤ymax⁡=3|y_i|\le y_{\max}=3. The agents operate the process by playing a GT-MPC game of the form (2) with T=Tc=10T=T_c=10, Tu=4T_u=4, the true model and state, the soft output constraints ∣yi∣≤3|y_i|\le3 with the slack penalties qϵ,i=0.003q_{\epsilon,i}=0.003 and Qϵ,i=0.5Q_{\epsilon,i}=0.5, and the weights Qy,1=10−4diag⁡(1,0.6,0.1)Q_{y,1}=10^{-4}\operatorname{diag}(1,0.6,0.1), Qy,2=10−4diag⁡(0.1,1,0.6)Q_{y,2}=10^{-4}\operatorname{diag}(0.1,1,0.6), Qy,3=10−4diag⁡(0.6,0.1,1)Q_{y,3}=10^{-4}\operatorname{diag}(0.6,0.1,1), and QΔu,i=wieieiTQ_{\Delta u,i}=w_i e_i e_i^{\mathsf{T}}, where eie_i is the iith column of I3I_3 and (w1,w2,w3)=(0.05,0.1,0.2)(w_1,w_2,w_3)=(0.05,0.1,0.2). The pseudogradient matrix AA of this game is not symmetric, ∥A−AT∥F/∥A∥F=0.30\lVert A-A^{\mathsf{T}}\rVert_F/\lVert A\rVert_F=0.30, so the game is not a potential game that can be represented by a single centralized MPC cost. It is also strongly monotone, with λmin⁡(sym⁡(A))=0.106\lambda_{\min}(\operatorname{sym}(A))=0.106. All three inputs and outputs are dynamically coupled by the system dynamics.

Data collection. We record ne=7n_e=7 experiments of 200 steps in which the agents operate according to the underlying (unknown) GT-MPC strategy. Each experiment starts from the equilibrium of a reference uniformly distributed in [−1.5,1.5]3[-1.5,1.5]^3, a range in which the corresponding equilibrium input always satisfies the input constraints, and the references of all the agents are piecewise constant, with new values uniformly distributed in [−5,5]3[-5,5]^3 every 15 steps. The output noise is uniformly distributed in [−0.05,0.05][-0.05,0.05].

Learning. Using jax-sysid, we first identify a model with n=4n=4 states from these closed-loop data in 2.3 s2^2.2 On 3 further experiments generated in the same way, the open-loop simulation of the identified model, from the initial states estimated by jax-sysid, achieves best fit rates 100(1−∥yl−y^l∥2/∥yl−yˉl∥2)100(1-\lVert y_l-\hat{y}_l\rVert_2/\lVert y_l-\bar{y}_l\rVert_2) of 98.7%, 98.6%, and 98.7% on the outputs l=1,2,3l=1,2,3, where yly_l collects the measured values of output ll, y^l\hat{y}_l the simulated ones, and yˉl\bar{y}_l is the mean of yly_l.

For the GT-MPC structure to learn, we use T=Tc=10T=T_c=10, μ=0.1\mu=0.1, ρ=10−5\rho=10^{-5}, η=10−3\eta=10^{-3}, and different values of TuT_u between 1 and TT. We initialize the bilevel problem with qϵ0=10−3q_\epsilon^0=10^{-3}, Qϵ0=0.1Q_\epsilon^0=0.1, and δ=0.01\delta=0.01, searching ss over the grid log⁡10s∈{−10,−9.5,…,−2}\log_{10}s\in\{-10,-9.5,\ldots,-2\} for initializing the solution of (9), which we solve by the L-BFGS-B solver of SciPy with the stability penalty (11), γ=0.9\gamma=0.9, and ρs=10\rho_s=10. The Kalman filter uses the process noise covariance 10−6I410^{-6}I_4, the measurement noise covariance 0.0523I3\frac{0.05^2}{3}I_3, and the initial covariance 10−4I410^{-4}I_4.

Controller. At each time step kk, the GT-MPC law estimates ξ^k\hat{\xi}_k by a Kalman filter based on the identified model, sets pk=(ξ^k,uk−1,rk)p_k=(\hat{\xi}_k,u_{k-1},r_k), and computes the variational GNE of (2), which exists and is unique by Proposition 1, by the DR-DAQP solver [3] through the nashopt package [5].

Results. We validate the controllers on 10 runs of 80 steps, each with a set-point change from r0r^0 to r1r^1, starting from the equilibrium of r0r^0. Each component of r1r^1 is uniformly distributed in [−2.7,2.7][-2.7,2.7], and r0=r1−sign⁡(r1)∘dr^0=r^1-\operatorname{sign}(r^1)\circ d, with dd uniformly distributed in [0,3]3[0,3]^3. The Kalman filter of the GT-MPC law starts from the equilibrium state of the identified model for r0r^0. Table 1 reports, for different values of TuT_u, the training time, the monotonicity constant λmin⁡(sym⁡(A(θ)))\lambda_{\min}(\operatorname{sym}(A(\theta))) of the learned game, and the closed-loop imitation errors

AgentsLearned, Tu=4T_u=4
diag⁡(Qy,1)\operatorname{diag}(Q_{y,1})10−4(1,0.6,0.1)10^{-4}(1,0.6,0.1)0.89⋅10−4(1.04,0.58,0.08)0.89\cdot10^{-4}(1.04,0.58,0.08)
diag⁡(Qy,2)\operatorname{diag}(Q_{y,2})10−4(0.1,1,0.6)10^{-4}(0.1,1,0.6)0.89⋅10−4(0.12,1.03,0.61)0.89\cdot10^{-4}(0.12,1.03,0.61)
diag⁡(Qy,3)\operatorname{diag}(Q_{y,3})10−4(0.6,0.1,1)10^{-4}(0.6,0.1,1)0.89⋅10−4(0.57,0.09,1.01)0.89\cdot10^{-4}(0.57,0.09,1.01)
QΔu,111Q_{\Delta u,1}^{11}0.050.050.89⋅0.0530.89\cdot0.053
QΔu,222Q_{\Delta u,2}^{22}0.10.10.89⋅0.1010.89\cdot0.101
QΔu,333Q_{\Delta u,3}^{33}0.20.20.89⋅0.2010.89\cdot0.201
qϵ,iq_{\epsilon,i}0.0030.0030.89⋅0.00280.89\cdot0.0028
Qϵ,iQ_{\epsilon,i}0.50.50.89⋅0.540.89\cdot0.54
TuT_uTime [s]λmin⁡\lambda_{\min}RMSu\mathrm{RMS}_uRMSy\mathrm{RMS}_y
117.87.80.19080.19080.04530.04530.07060.0706
2210.910.90.10000.10000.02140.02140.02450.0245
3314.514.50.10000.10000.01060.01060.01330.0133
4421.721.70.10000.10000.00160.00160.00260.0026
5519.619.60.10000.10000.00510.00510.00500.0050
6611.111.10.10000.10000.00800.00800.00640.0064
7725.825.80.10000.10000.00650.00650.00650.0065
8836.436.40.10000.10000.00620.00620.00690.0069
9935.135.10.10000.10000.00580.00580.00700.0070
101057.857.80.10000.10000.00580.00580.00700.0070

Table 1. Numerical example. Left: true weights used by the agents and weights learned with Tu=4T_u=4. Right: learning time, monotonicity constant λmin⁡=λmin⁡(sym⁡(A(θ)))\lambda_{\min}=\lambda_{\min}(\operatorname{sym}(A(\theta))), and imitation errors for Tu=1,…,TT_u=1,\ldots,T.

RMSu=(∑j=110∑k=079∥ukj−ua,kj∥22∑j=110∑k=079∥ua,kj∥22)1/2\mathrm{RMS}_u=\left(\frac{\sum_{j=1}^{10}\sum_{k=0}^{79}\lVert u_k^j-u_{a,k}^j\rVert_2^2}{\sum_{j=1}^{10}\sum_{k=0}^{79}\lVert u_{a,k}^j\rVert_2^2}\right)^{1/2}
RMSy=(∑j=110∑k=079∥ykj−ya,kj∥22∑j=110∑k=079∥ya,kj∥22)1/2\mathrm{RMS}_y=\left(\frac{\sum_{j=1}^{10}\sum_{k=0}^{79}\lVert y_k^j-y_{a,k}^j\rVert_2^2}{\sum_{j=1}^{10}\sum_{k=0}^{79}\lVert y_{a,k}^j\rVert_2^2}\right)^{1/2}

where (ykj,ukj)(y_k^j,u_k^j) and (ya,kj,ua,kj)(y_{a,k}^j,u_{a,k}^j) are the measured outputs and the inputs of the closed loops with the GT-MPC law and with the agents in run jj. The average CPU time per step taken by the solver to evaluate the GT-MPC action ranges between 21 and 96 μ\mus depending on the control horizon TuT_u. With closed-loop stability enforced, the GT-MPC law learned by (9) imitates the agents with imitation errors below 0.071 for all TuT_u, and the smallest for Tu=4T_u=4, which is the control horizon indeed used by the agents generating the training data.

Figure 1 shows a run of the GT-MPC law learned by (9) with Tu=4T_u=4. The GT-MPC law produces closed-loop trajectories that are almost indistinguishable from those of the agents. As shown in Table 1 (left), for Tu=4T_u=4 the learned weights are close to those of the agents up to a common scale factor α=0.89\alpha=0.89, which leaves the GNEs unchanged, and the off-diagonal entries of Qy,iQ_{y,i} and the cross weights SiS_i are small, below 1.6⋅10−61.6\cdot10^{-6} and 2.8⋅10−32.8\cdot10^{-3} in magnitude, respectively. With the stability penalty, the unconstrained closed loops are asymptotically stable for all TuT_u (spectral radius between 0.72 and 0.85).

Figure 1. Agents (black) and GT-MPC law learned with Tu=4T_u = 4 by (9) (blue, dashed), tracking the references rdesr^{\mathrm{des}} (dotted), agents reacting to the reference generator (12) (green), and generated references rr (orange). Top: outputs and bounds (dashed). Bottom: inputs.

Set-point optimization

The learned game can be used for higher-level tasks without requiring the agents to reveal their objectives. As an example, a reference generator placed on top of the agents, who keep playing their own GT-MPC game, sends them at each step kk the reference

rk=arg⁡min⁡r  (y^1(r)−r1,kdes)2+ω∑l=23(y^l(r)−rl,kdes)2+σ∥r−rkdes∥22(12)r_k = \underset{r}{\arg\min}\; \left(\hat{y}_1(r)-r^{\mathrm{des}}_{1,k}\right)^2 + \omega\sum_{l=2}^{3}\left(\hat{y}_l(r)-r^{\mathrm{des}}_{l,k}\right)^2 + \sigma\left\lVert r-r_k^{\mathrm{des}}\right\rVert_2^2 \tag*{(12)}

where rkdesr_k^{\mathrm{des}} is the reference of Figure 1 to track, y^(r)=C(A^ξ^k+Buˉk(r))\hat{y}(r)=C\left(\hat{A}\hat{\xi}_k+B\bar{u}_k(r)\right) is the output predicted by the identified model when the agents apply the GT-MPC action uˉk(r)\bar{u}_k(r) of the game learned with Tu=4T_u=4 at p=(ξ^k,uk−1,r)p=(\hat{\xi}_k,u_{k-1},r), ω∈(0,1)\omega\in(0,1) reduces the importance of tracking y2y_2 and y3y_3, and σ>0\sigma>0 prevents excessive deviations of rr from rkdesr_k^{\mathrm{des}}. We solve (12) by a Gauss-Newton method, using the derivatives of the GNE of § 3.2. As shown in Figure 1 (green) for ω=0.02\omega=0.02 and σ=10−2\sigma=10^{-2}, the generator largely removes the dip and the bump of y1y_1 caused by the coupling with the other loops (see red circles), at the price of slower transients of y2y_2 and y3y_3.

Conclusions

We have proposed a method for learning strongly monotone GT-MPC laws from input/output data of multiple agents, and illustrated the use of the learned game for explaining the agents’ objectives and for optimizing the references given to the agents. Future research will address other higher-level uses of the learned game, such as mechanism design, and extensions to state-dependent weights and nonlinear systems.

Generative AI Use

Generative AI tools were used to help write and proofread the paper and for generating the Python code used in the reported example.

Acknowledgments

This work was funded by the European Union (ERC Advanced Research Grant COMPACT, No. 101141351). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. The work was also supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), project number 528033031.

References

  1. [1]S. Allen, S. A. Gabriel, and J. P. Dickerson. Using inverse optimization to learn cost functions in generalized Nash games. Computers & Operations Research, 142:105721, 2022.arxiv.org/abs/2102.12415
  2. [2]B. Amos and J. Z. Kolter. OptNet: Differentiable optimization as a layer in neural networks. In Proceedings of the 34th International Conference on Machine Learning, pages 136–145, 2017.arxiv.org/abs/1703.00443
  3. [3]D. Arnström, E. Benenati, and G. Belgioioso. DR–DAQP: A hybrid operator splitting and active-set solver for affine variational inequalities. arXiv preprint arXiv:2604.02531, 2026.arxiv.org/abs/2604.02531
  4. [4]A. Bemporad. An L-BFGS-B approach for linear and nonlinear system identification under ℓ₁ and group-lasso regularization. IEEE Transactions on Automatic Control, 70(7):4857–4864, 2025.arxiv.org/abs/2403.03827
  5. [5]A. Bemporad. NashOpt: A Python library for computing generalized Nash equilibria. arXiv preprint arXiv:2512.23636, 2025.arxiv.org/abs/2512.23636
  6. [6]A. Bemporad and T. Tatarenko. Learning parametric monotone games. arXiv preprint arXiv:2609.02494, 2026.arxiv.org/abs/2609.02494
  7. [7]A. Bemporad and T. Tatarenko. Solving monotone linear-quadratic generalized Nash equilibrium problems via quadratic programming. arXiv preprint arXiv:2608.07336, 2026.arxiv.org/abs/2608.07336
  8. [8]E. Benenati and S. Grammatico. Linear-quadratic dynamic games as receding-horizon variational inequalities. IEEE Transactions on Automatic Control, 71(4):2404–2417, 2026.arxiv.org/abs/2408.15703
  9. [9]D. Bertsimas, V. Gupta, and I.C. Paschalidis. Data-driven estimation in equilibrium using inverse optimization. Mathematical Programming, 153(2):595–633, 2015.
  10. [10]J. Bolte, E. Pauwels, and A. Silveti-Falls. Differentiating nonsmooth solutions to parametric monotone inclusion problems. SIAM Journal on Optimization, 34(1):71–97, 2024.arxiv.org/abs/2212.07844
  11. [11]J. Bradbury, R. Frostig, P. Hawkins, M.J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang. JAX: composable transformations of Python+NumPy programs. http://github.com/google/jax, 2018.
  12. [12]R.H. Byrd, P. Lu, J. Nocedal, and C. Zhu. A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific Computing, 16(5):1190–1208, 1995.
  13. [13]E. Dimou, F. Fabiani, and A. Bemporad. Receding horizon games with stability guarantees. In 65th IEEE Conference on Decision and Control, 2026.
  14. [14]F. Facchinei and C. Kanzow. Generalized Nash equilibrium problems. 4OR, 5(3):173–210, 2007.
  15. [15]F. Facchinei and J.-S. Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York, 2003.
  16. [16]D. Fridovich-Keil, E. Ratner, L. Peters, A.D. Dragan, and C.J. Tomlin. Efficient iterative linear-quadratic approximations for nonlinear multi-player general-sum differential games. In Proc. IEEE International Conference on Robotics and Automation, pages 1475–1481, Paris, France, 2020.
  17. [17]S. Hall, G. Belgioioso, F. Dörfler, and D. Liao-McPherson. Stability certificates for receding-horizon games. IEEE Transactions on Automatic Control, 71(5):3511–3518, 2026.arxiv.org/abs/2404.12165
  18. [18]S. Hall, G. Belgioioso, D. Liao-McPherson, and F. Dörfler. Receding horizon games with coupling constraints for demand-side management. In 61st IEEE Conference on Decision and Control, pages 3795–3800, 2022.DOI
  19. [19]S. Hall and A. Bemporad. Solving multiparametric generalized Nash equilibrium problems and explicit game-theoretic model predictive control. arXiv preprint arXiv:2512.05505, 2025. Code available at https://github.com/bemporad/nash_mpqp.arxiv.org/abs/2512.05505
  20. [20]H. Kim, E.L. Zhu, C.S. Lim, and F. Borrelli. Learning two-agent motion planning strategies from generalized nash equilibrium for model predictive control. In Proc. 7th Annual Learning for Dynamics and Control Conference, volume 283 of Proceedings of Machine Learning Research, pages 112–123, 2025.arxiv.org/abs/2411.13983
  21. [21]S. Le Cleac’h, M. Schwager, and Z. Manchester. ALGAMES: A fast solver for constrained dynamic games. In Robotics: Science and Systems XVI, 2020.
  22. [22]A. Mallick, R. Rahimi Baghbadorani, P. Mohajerin Esfahani, and S. Grammatico. Learning in inverse games: Tractable training with probabilistic guarantees. arXiv preprint arXiv:2610.03481, 2026.arxiv.org/abs/2610.03481
  23. [23]M. Pustilnik and F. Borrelli. Generalized Nash equilibrium solutions in dynamic games with shared constraints. arXiv preprint arXiv:2502.19569, 2025.arxiv.org/abs/2502.19569
  24. [24]G. Scutari, D. P. Palomar, F. Facchinei, and J.-S. Pang. Convex optimization, game theory, and variational inequality theory. IEEE Signal Processing Magazine, 27(3):35–49, 2010.DOI
  25. [25]K. Tracy and Z. Manchester. On the differentiability of the primal-dual interior-point method. arXiv preprint arXiv:2406.11749, 2024.arxiv.org/abs/2406.11749
  26. [26]M. Wang, Z. Wang, J. Talbot, J. C. Gerdes, and M. Schwager. Game-theoretic planning for self-driving cars in multivehicle competitive scenarios. IEEE Transactions on Robotics, 37(4):1313–1325, 2021.

Paper details

vlnc:W_zr8yfuab
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

Generative AI tools

View statement
Looking for related papers…
Contents