# Reinforcement Learning in Nonzero-sum Linear Quadratic Deep Structured
Games: Global Convergence of Policy Optimization

Masoud Roudneshin, Jalal Arabneydi and Amir G. Aghdam This work is supported
in part by the Natural Sciences and Engineering Research Council of Canada
(NSERC) under Grant RGPIN-262127-17.Masoud Roudneshin, Jalal Arabneydi, and
Amir G. Aghdam are with the Department of Electrical and Computer Engineering,
Concordia University, 1455 de Maisonneuve Blvd. West, Montreal, QC, Canada,
Postal Code: H3G 1M8. Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We study model-based and model-free policy optimization in a class of nonzero-
sum stochastic dynamic games called linear quadratic (LQ) deep structured
games. In such games, players interact with each other through a set of
weighted averages (linear regressions) of the states and actions. In this
paper, we focus our attention to homogeneous weights; however, for the special
case of infinite population, the obtained results extend to asymptotically
vanishing weights wherein the players learn the sequential weighted mean-field
equilibrium. Despite the non-convexity of the optimization in policy space and
the fact that policy optimization does not generally converge in game setting,
we prove that the proposed model-based and model-free policy gradient descent
and natural policy gradient descent algorithms globally converge to the sub-
game perfect Nash equilibrium. To the best of our knowledge, this is the first
result that provides a global convergence proof of policy optimization in a
nonzero-sum LQ game. One of the salient features of the proposed algorithms is
that their parameter space is independent of the number of players, and when
the dimension of state space is significantly larger than that of the action
space, they provide a more efficient way of computation compared to those
algorithms that plan and learn in the action space. Finally, some simulations
are provided to numerically verify the obtained theoretical results.

Proceedings of IEEE Conference on Decision and Control, 2020.

##  I Introduction

In recent years, there has been a growing interest in the application of
reinforcement learning (RL) algorithms in networked control systems. One of
the most popular reinforcement learning (RL) algorithms in practice is policy
gradient, due to its stability and fast convergence. However, from the
theoretical point of view, there is not much known about it. Recently, it is
shown in [1] that a single-agent linear quadratic (LQ) optimal control problem
enjoys the global convergence, despite the fact that the optimization problem
is not convex in the policy space. A similar result is obtained for zero-sum
LQ games in [2]. On the other hand, a nonzero-sum LQ game is more challenging
than the above problems, where the existing results on the global (or even
local) convergence of the policy gradient methods are generally not
encouraging [3].

Inspired by recent developments in deep structured teams and games [4, 5, 6,
7, 8, 9], we study a class of LQ games wherein the effect of other players on
any individual player is characterized by a linear regression of the states
and actions of all players. The closest field of research to deep structured
games is mean-field games [10]. In a classical LQ mean-field game, one often
has: (a) homogeneous individual weights (i.e., players are equally important);
(b) the number of players $n$ is asymptotically large with independent
primitive random variables (to be able to predict the trajectory of the mean-
field using the strong law of large numbers); (c) the coupling is through the
mean of the states, where the control coupling (called extended coupling) is
more challenging; (d) the proof technique revolves around the fact that the
effect of a single player on others is negligible, reducing the game to a
coupled forward-backward optimal control problem; (e) the solution concept is
Nash equilibrium; (f) given some fixed-point conditions across the time
horizon, the forward-backward equation admits a solution leading to an
approximate Nash in the finite-population game; (g) they are often not
practical for long-horizon and reinforcement learning applications wherein the
common practice is to adopt a weaker solution concept called stationary Nash
equilibrium (where the trajectory of the mean-field is stationary), and (h)
since the results are asymptotic, the models are limited to those that are
uniformly bounded in $n$. In contrast to mean-field game, LQ deep structured
game often has: (a’) heterogeneous individual weights that are not necessarily
homogeneous; (b’) the number of players is arbitrary (not necessarily very
large) with possibly correlated primitive random variables; (c’) the coupling
is through the weighted mean of the states and actions; (d’) the proof
technique revolves around a gauge transformation initially proposed in [11]
(not based on the negligible effect); (e’) the solution concept is sequential
Nash; (f’) the solution is exact (not an approximate one) for any arbitrary
number of players and it is identified by Riccati equations; (g’) since the
solution concept is sequential, it is well suited for long-horizon and
reinforcement learning, and (h’) since the results are also valid for finite-
population game, the dynamics and cost are not necessarily limited to
uniformly bounded functions with respect to $n$. It is shown in [5] that the
classical LQ mean-field game with the tracking cost formulation is a special
case of deep structured games under standard conditions, where the mean-field
equilibrium coincides with the sequential mean-field equilibrium. It is to be
noted that the LQ mean-field-type game [12, 13, 14] is a single-agent control
problem (i.e., it is not a non-cooperative game), which resembles a team
problem with social welfare cost function.111When the mean field is replaced
by the expectation of the state of the genetic player, the resultant problem
is called mean-field-type game. In particular, it may be viewed as a special
case of risk-neutral LQ mean-field teams introduced in [11], showcased in [15,
16, 17, 18, 19], and extended to deep structured LQ teams in [6]. The
interested reader is referred to [5, Section VI] for more details on
similarities and differences between mean-field games, mean-field-type games
and mean-field teams.

The rest of the paper is organized as follows. In Section II, the problem of
LQ deep structured game is formulated. In Section III, the global convergence
of model-based and model-free policy gradient descent and natural policy
gradient descent algorithms are presented. In Section IV, some numerical
examples are provided to validate the theoretical results. The paper is
concluded in Section V.

##  II Problem Formulation

Throughout the paper, $\mathbb{R}$, $\mathbb{R}_{>0}$ and $\mathbb{N}$ refer
to the sets of real, positive real and natural numbers, respectively. Given
any $n\in\mathbb{N}$, $\mathbb{N}_{n}$, $x_{1:n}$ and $\mathbf{I}_{n\times n}$
denote the finite set $\\{1,\ldots,n\\}$, vector $(x_{1},\ldots,x_{n})$ and
the $n\times n$ identity matrix, respectively. $\|\bm{\cdot}\|$ is the
spectral norm of a matrix, $\|\bm{\cdot}\|_{F}$ is the Frobenius norm of a
matrix, $\operatorname{Tr}(\bm{\cdot})$ is the trace of a matrix,
$\sigma_{\text{min}}(\bm{\cdot})$ is the minimum singular value of a matrix,
$\rho(\bm{\cdot})$ is the spectral radius of a matrix, and
$\operatorname{diag}(\Lambda_{1},\Lambda_{2})$ is the block diagonal matrix
$[\Lambda_{1}\quad 0;0\quad\Lambda_{2}]$. For vectors $x,y$ and $z$,
$\operatorname{vec}(x,y,z)=[x^{\intercal},y^{\intercal},z^{\intercal}]^{\intercal}$
is a column vector. The superscript $-i$ refers to all players except the
$i$-th player. In addition, $\operatorname{poly}(\bm{\cdot})$ denotes
polynomial function.

Consider a nonzero-sum stochastic dynamic game with $n\in\mathbb{N}$ players.
Let $x^{i}_{t}\in\mathbb{R}^{d_{x}}$, $u^{i}_{t}\in\mathbb{R}^{d_{u}}$ and
$w^{i}_{t}\in\mathbb{R}^{d_{x}}$ denote the state, action and local noise of
player $i\in\mathbb{N}_{n}$ at time $t\in\mathbb{N}$, where
$d_{x},d_{u}\in\mathbb{N}$. Define the weighted averages:

$\bar{x}_{t}:=\sum_{i=1}^{n}\alpha^{i}_{n}x^{i}_{t},\quad\bar{u}_{t}:=\sum_{i=1}^{n}\alpha^{i}_{n}u^{i}_{t},$
(1)

where $\alpha^{i}_{n}\in\mathbb{R}$ is the _influence factor_ (weight) of
player $i$ among its peers. From [4, 5, 6], we refer to the above linear
regressions as _deep state_ and _deep action_ in the sequel. To ease the
presentation, the weights are normalized as follows:
$\sum_{i=1}^{n}\alpha^{i}_{n}=1$.

The initial states $\\{x^{1}_{1},\ldots,x^{n}_{1}\\}$ are random with finite
covariance matrices. The evolution of the state of player $i\in\mathbb{N}_{n}$
at time $t\in\mathbb{N}$ is given by:

$x^{i}_{t+1}=Ax^{i}_{t}+Bu^{i}_{t}+\bar{A}\bar{x}_{t}+\bar{B}\bar{u}_{t}+w^{i}_{t},$
(2)

where $\\{w^{i}_{t}\\}_{t=1}^{\infty}$ is an i.i.d. zero-mean noise process
with a finite covariance matrix. The primitive random variables
$\\{\\{x^{i}_{1}\\}_{i=1}^{n},\\{w^{i}_{1}\\}_{i=1}^{n},\\{w^{i}_{2}\\}_{i=1}^{n},\ldots\\}$
are defined on a common probability space and are mutually independent across
time. The above random variables can be non-Gaussian and correlated (not
necessarily independent) across players. The cost of player
$i\in\mathbb{N}_{n}$ at time $t\in\mathbb{N}$ is given by:

$\begin{split}c_{t}^{i}=&(x_{t}^{i})^{\intercal}Qx_{t}^{i}+2(x_{t}^{i})^{\intercal}S^{x}\bar{x}_{t}+(\bar{x}_{t})^{\intercal}\bar{Q}\bar{x}_{t}\\\
&+(u_{t}^{i})^{\intercal}Ru_{t}^{i}+2(u_{t}^{i})^{\intercal}S^{u}\bar{u}_{t}+(\bar{u}_{t})^{\intercal}\bar{R}\bar{u}_{t},\end{split}$
(3)

where $Q,S^{x},\bar{Q},R,S^{u}$ and $\bar{R}$ are symmetric matrices with
appropriate dimensions.

From [4, 5, 6], an information structure called _deep state sharing_ (DSS) is
considered wherein each player $i\in\mathbb{N}_{n}$ at any time
$t\in\mathbb{N}$ observes its local state $x^{i}_{t}$ and the deep state
$\bar{x}_{t}$, i.e., $u^{i}_{t}=g^{i}_{t}(x^{i}_{1:t},\bar{x}_{1:t})$, where
$g^{i}_{t}$ is a measurable function adapted to the filteration of the
underlying primitive random variables of $\\{x^{i}_{1:t},\bar{x}_{1:t}\\}$.
When the number of players is very large, one can use _no-sharing_ (NS)
information structure wherein each player observes only its local state.
However, such a fully decentralized information structure comes at a price
that one must predict the trajectory of the deep state in time (which
introduces the computational complexity in time horizon in terms of storage
and computation). For example, if the dynamics of the deep state (i.e.,
$A+\bar{A}$ and $B+\bar{B}$) is known (which is not applicable for model-free
applications), the deep state can be predicted a head of time when primitive
random variables are mutually independent by the strong law of large numbers.
Alternatively, one can assume to have access to an external simulator for the
dynamics of the deep state (which is basically DSS structure). In this paper,
we focus on DSS information structure wherein there is no loss of optimality
in restricting attention to stationary strategies despite the fact that the
deep state is not stationary. The interested reader is referred to [5] for the
convergence analysis of NS (approximate) solution to the DSS solution, as
$n\rightarrow\infty$.

Define $\mathbf{g}^{i}_{n}:=\\{g^{i}_{t}\\}_{t=1}^{\infty}$ and
$\mathbf{g}_{n}:=\\{\mathbf{g}^{1},\ldots,\mathbf{g}^{n}\\}$. The admissible
set of actions are square integrable such that
$\mathbb{E}\big{[}\sum_{t=1}^{\infty}\gamma^{t-1}(u^{i}_{t})^{\intercal}u^{i}_{t}\big{]}<\infty$.
Given a discount factor $\gamma\in(0,1)$, the cost-to-go for any player
$i\in\mathbb{N}_{n}$ is described by:

$J^{i}_{n,\gamma}(\mathbf{g}^{i}_{n},\mathbf{g}^{-i}_{n})_{t_{0}}=(1-\gamma)\mathbb{E}\big{[}\sum_{t=t_{0}}^{\infty}\gamma^{t-1}c^{i}_{t}\big{]},\quad
t_{0}\in\mathbb{N}.$ (4)

######  Problem 1.

Suppose that the weights are homogeneous, i.e. $\alpha^{i}_{n}=\frac{1}{n}$,
$i\in\mathbb{N}_{n}$. When a sequential Nash strategy $\mathbf{g}^{\ast}_{n}$
exists, develop model-based and model-free gradient descent and natural policy
gradient descent procedures under DSS information structure such that for any
player $i\in\mathbb{N}_{n}$ at any stage of the game $t_{0}\in\mathbb{N}$, and
any arbitrary strategy $\mathbf{g}^{i}$:

${J^{i}_{n,\gamma}(\mathbf{g}^{\ast,i}_{n},\mathbf{g}^{\ast,-i}_{n})}_{t_{0}}\leq{J^{i}_{n,\gamma}(\mathbf{g}^{i},\mathbf{g}^{\ast,-i}_{n})}_{t_{0}}.$
(5)

######  Remark 1.

_It is to be noted that Problem 1 holds for arbitrary number of players $n$,
where the solution depends on $n$. Since the infinite-population solution is
easier for analysis and may be viewed as a special case, one can generalize
the homogeneous weights $\alpha^{i}_{n}=\frac{1}{n}$ to heterogeneous weights
$\alpha^{i}_{n}=\frac{\beta^{i}}{n}$, where
$\beta^{i}\in[-\beta_{\text{max}},\beta_{\text{max}}]$,
$\beta_{\text{max}}\in\mathbb{R}_{>0}$, $i\in\mathbb{N}_{n}$. The resultant
solution is called _sequential weighted mean-field equilibrium_ (SWMFE) in
[5]. The SWMFE constructs an approximate solution at any stage of the game
$t_{0}\in\mathbb{N}$ such that
$J^{i}_{n,\gamma}(\mathbf{g}^{\ast,i}_{\infty},\mathbf{g}^{\ast,-i}_{\infty})_{t_{0}}\leq{J^{i}_{n,\gamma}(\mathbf{g}^{i},\mathbf{g}^{\ast,-i}_{\infty})}_{t_{0}}+\varepsilon(n)$,
where $\lim_{n\rightarrow\infty}\varepsilon(n)=0$. For more details, see [5,
Theorem 4]._

###  II-A Main challenges and contributions

There are several challenges to solve Problem 1. The first one is the _curse
of dimensionality_ , where the computational complexity of the solution
increases with the number of players. The second one is the _imperfect
information_ structure, where players do not have perfect information about
the states of other players. The third challenge is that the resultant
optimization problem is _non-convex_ in the policy space, see a counterexample
in [1]. The forth one lies in the fact that policy optimization is _not even
locally convergent_ in a game with continuous spaces, in general; see a
counterexample in [3]. The main contribution of this paper is to present an
analytical proof for the global convergence of model-based and model-free
policy gradient algorithms. In contrast to the model-based solution in [5]
(whose number of unknowns increases quadratically with $d_{x}$), the number of
unknown parameters in the proposed algorithms increases linearly with $d_{x}$
and $d_{u}$. To the best of our knowledge, this is the first result on the
global convergence of policy optimization in nonzero-sum LQ games.

##  III Main Results

In this section, we first present a model-based algorithm introduced in [5]
that requires $2d_{x}\times 2d_{x}$ parameters to construct the solution.
Then, we propose two model-based gradient algorithms and prove their global
convergence to the above solution, where their planning space is the policy
space (that requires $2d_{u}\times d_{x}$ parameters to identify the
solution). Based on the proposed gradient methods, we develop two model-free
(reinforcement learning) algorithms and establish their global convergence to
the model-based solution.

From [5], we use a gauge transformation to define the following variables for
any player $i\in\mathbb{N}_{n}$ at any time $t\in\mathbb{N}$:
$\mathbf{x}_{t}^{i}:=\operatorname{vec}(x_{t}^{i}-\bar{x}_{t},\bar{x}_{t})$,
$\mathbf{u}_{t}^{i}:=\operatorname{vec}(u_{t}^{i}-\bar{u}_{t},\bar{u}_{t})$
and
$\mathbf{w}_{t}^{i}:=\operatorname{vec}(w_{t}^{i}-\bar{w}_{t},\bar{w}_{t})$,
where $\bar{w}_{t}:=\frac{1}{n}\sum_{i=1}^{n}w_{t}^{i}$. In addition, we
define the following matrices: $\mathbf{A}:=\operatorname{diag}(A,A+\bar{A})$,
$\mathbf{B}:=\operatorname{diag}(B,B+\bar{B})$, and

$\mathbf{Q}:=\begin{bmatrix}Q&Q+S^{x}\\\ Q+S^{x}&Q+2S^{x}+\bar{Q}\\\
\end{bmatrix},\quad\mathbf{R}:=\begin{bmatrix}R&R+S^{u}\\\
R+S^{u}&R+2S^{u}+\bar{R}\\\ \end{bmatrix}.$ (6)

We now express the per-step cost of each player in (3) as:

$\displaystyle c_{t}^{i}$
$\displaystyle=(\mathbf{x}^{i}_{t})^{\intercal}\mathbf{Q}\mathbf{x}^{i}_{t}+(\mathbf{u}^{i}_{t})^{\intercal}\mathbf{R}\mathbf{u}^{i}_{t}.$
(7)

To formulate the solution, we present a non-standard algebraic Riccati
equation, introduced in [5], as follows:

$\mathbf{M}(\bm{\theta})=\mathbf{Q}+\bm{\theta}^{\intercal}\mathbf{R}\bm{\theta}+\gamma(\mathbf{A}-\mathbf{B}\bm{\theta})^{\intercal}\mathbf{M}(\bm{\theta})(\mathbf{A}-\mathbf{B}\bm{\theta}),$
(8)

where $\bm{\theta}:=\operatorname{diag}(\theta(n),\bar{\theta}(n))$,
$\theta(n):=(F_{n})^{-1}K_{n}$,
$\bar{\theta}(n):=(\bar{F}_{n})^{-1}\bar{K}_{n}$, and matrices ${{}F_{n}}$,
${{}\bar{F}_{n}}$, ${{}K_{n}}$ and ${{}\bar{K}_{n}}$ are given by:

$\displaystyle{{}F_{n}}=(1-\frac{1}{n})\Big{[}R+\gamma
B^{\intercal}{{}\mathbf{M}}^{1,1}(\bm{\theta})B\Big{]}$
$\displaystyle\quad+\frac{1}{n}\Big{[}R+S^{u}+\gamma(B+\bar{B})^{\intercal}{{}\mathbf{M}}^{1,2}(\bm{\theta})B\Big{]},$
$\displaystyle{{}\bar{F}_{n}}=(1-\frac{1}{n})\left[R+S^{u}+\gamma
B^{\intercal}{{}\mathbf{M}}^{2,1}(\bm{\theta})(B+\bar{B})\right]$
$\displaystyle+\frac{1}{n}\left[R+2S^{u}+\bar{R}+\gamma(B+\bar{B})^{\intercal}{{}\mathbf{M}}^{2,2}(\bm{\theta})(B+\bar{B})\right],$
$\displaystyle{{}K_{n}}=(1-\frac{1}{n})\gamma
B^{\intercal}{{}\mathbf{M}}^{1,1}(\bm{\theta})A+\frac{\gamma}{n}(B+\bar{B})^{\intercal}{{}\mathbf{M}}^{1,2}(\bm{\theta})A,$
$\displaystyle\bar{K}_{n}=(1-\frac{1}{n})\gamma
B^{\intercal}{{}\mathbf{M}}^{2,1}(\bm{\theta})(A+\bar{A})+\frac{\gamma}{n}(B+\bar{B})^{\intercal}{{}\mathbf{M}}^{2,2}(\bm{\theta})(A+\bar{A}).$
(9)

######  Assumption 1.

Suppose equations (8) and (III) admit a unique stable solution, which is also
the limit of the finite-horizon solution. In addition, let ${{}F_{n}}$ and
${{}\bar{F}_{n}}$ be invertible matrices, and
$(1-\frac{1}{n}){{}F_{n}}+\frac{1}{n}{{}\bar{F}_{n}}$ be a positive definite
matrix.

We now provide two sufficient conditions for Assumption 1 ensuring the
existence of a stationary solution. Let $G$ denote the mapping from
$\mathbf{M}$ to $\bm{\theta}$ displayed in (III) (where
$\bm{\theta}=G(\mathbf{M})$), and $L$ denote the mapping from $\bm{\theta}$ to
$\mathbf{M}$ expressed in (8) (where $\mathbf{M}=L(\bm{\theta})$). Thus,
$\mathbf{M}=L(G(\mathbf{M}))$ is a fixed-point equation to be solved by fixed-
point methods.

######  Assumption 2.

Let the mapping $L(G(\bm{\cdot}))$ be a contraction, implying that equations
(8) and (III) admit a unique fixed-point solution. In addition, let
${{}F_{n}}$ and ${{}\bar{F}_{n}}$ be invertible matrices, and
$(1-\frac{1}{n}){{}F_{n}}+\frac{1}{n}{{}\bar{F}_{n}}$ be a positive definite
matrix.

######  Assumption 3 (Infinite-population decoupled Riccati equations).

_Let $Q$ and $Q+S^{x}$ be positive semi-definite, $R$ and $R+S^{u}$ be
positive definite, and $\bar{A}$ and $\bar{B}$ be zero. Suppose $(A,B)$ is
stabilizable, and $(A,Q^{1/2})$ and $(A,(Q+S^{x})^{1/2})$ are detectable. When
$n$ is asymptotically large, the non-standard Riccati equation (8) decomposes
into two decoupled standard Riccati equations; see [5, Proposition 2]._

######  Theorem 1 (Model-based solution using non-standard Riccati equation
[5]).

Let Assumption 1 hold. There exists a stationary subgame perfect Nash
equilibrium such that for any player $i\in\mathbb{N}_{n}$ at any time
$t\in\mathbb{N}_{T}$,

$u^{\ast,i}_{t}=-\theta^{\ast}(n)x^{i}_{t}-(\bar{\theta}^{\ast}(n)-\theta^{\ast}(n))\bar{x}_{t},$
(10)

where the gains are obtained from (III). In addition, the optimal cost of
player $i\in\mathbb{N}_{n}$ from the initial time $t_{0}=1$ is given by:
$J^{i}_{n,\gamma}(\bm{\theta}^{\ast})=(1-\gamma)\operatorname{Tr}(\mathbf{M}(\bm{\theta}^{\ast})\bm{\Sigma}^{i}_{x})+\gamma\operatorname{Tr}(\mathbf{M}(\bm{\theta}^{\ast})\bm{\Sigma}^{i}_{w})$,
where $\bm{\Sigma}^{i}_{x}:=\mathbb{E}\big{[}(\operatorname{vec}(\Delta
x^{i}_{1}),\bar{x}_{1})(\operatorname{vec}(\Delta
x^{i}_{1}),\bar{x}_{1})^{\intercal}\big{]}$ and
$\bm{\Sigma}^{i}_{w}:=\mathbb{E}\big{[}\operatorname{vec}(\Delta
w^{i}_{t}),\bar{w}_{t})\operatorname{vec}(\Delta
w^{i}_{t}),\bar{w}_{t})^{\intercal}\big{]}$.

###  III-A Model-based solution using policy optimization

From Theorem 1, there is no loss of optimality in restricting attention to
linear identical stationary strategies of the form
$\bm{\theta}=\operatorname{diag}(\theta,\bar{\theta})$. Therefore, we select
one arbitrary player $i$ as a learner and other players as imitators (that are
passive during the learning process). More precisely, at each time instant,
player $i$ uses a gradient algorithm to update its strategy whereas other
players employ the updated strategy to determine their next actions. In this
article, we discard the process of selecting the learner, but in order to have
a fair implementation, the learner may be chosen randomly at each
iteration.222For the special case of infinite population, it is also possible
that all players become learners, i.e., they simultaneously learn the
strategies as long as their exploration noises are i.i.d. In such a case, the
infinite-population deep state reduces to weighted mean-field and remains
unchanged.  For simplicity of presentation, we omit the superscript $i$ and
the subscription of the cost function. Hence, the strategy of the learner can
be described by:
$\mathbf{u}_{t}=-\bm{\theta}\mathbf{x}_{t},\mathbf{u}_{t}\in\mathbb{R}^{2d_{u}},\mathbf{x}_{t}\in\mathbb{R}^{2d_{x}},t\in\mathbb{N}$.

######  Lemma 1.

The following holds at the initial time $t_{0}=1$:

$[\nabla_{\theta}J(\bm{\theta}),\nabla_{\bar{\theta}}J(\bm{\theta})]=2\mathbf{P}_{n}\mathbf{E}_{\bm{\theta}}\bm{\Sigma}_{\bm{\theta}},$
(11)

where

$\begin{cases}\mathbf{P}_{n}:=[(1-\frac{1}{n})\mathbf{I}_{d_{u}\times
d_{u}},\frac{1}{n}\mathbf{I}_{d_{u}\times d_{u}}],\\\
\mathbf{E}_{\bm{\theta}}:=(\mathbf{R}+\gamma\mathbf{B}^{\intercal}\mathbf{M}(\bm{\theta})\mathbf{B})\bm{\theta}-\gamma\mathbf{B}^{\intercal}\mathbf{M}(\bm{\theta})\mathbf{A},\\\
\bm{\Sigma}_{\bm{\theta}}:=\mathbb{E}\big{[}(1-\gamma)\sum_{t=1}^{\infty}\gamma^{t-1}\mathbf{x}_{t}\mathbf{x}_{t}^{\intercal}\big{]}.\end{cases}$
(12)

###### Proof.

The proof is presented in Appendix A. ∎

In this paper, we consider two gradient-based methods.

  * •

Policy gradient descent:

$\bm{\theta}_{k+1}=\bm{\theta}_{k}-\eta\operatorname{diag}(\nabla_{\theta}J(\bm{\theta}_{k}),\nabla_{\bar{\theta}}J(\bm{\theta}_{k})).$
(13)

  * •

Natural policy gradient descent:

$\bm{\theta}_{k+1}=\bm{\theta}_{k}-\eta\operatorname{diag}(\nabla_{\theta}J(\bm{\theta}_{k}),\nabla_{\bar{\theta}}J(\bm{\theta}_{k}))\bm{\Sigma}_{\bm{\theta}}^{-1}.$
(14)

To prove our convergence results, we impose extra standard assumptions,
described below.

######  Assumption 4.

The initial policy is stable. A policy $\bm{\theta}$ is said to be stable if
$\rho(\mathbf{A}-\mathbf{B}\bm{\theta})<1$.

######  Assumption 5.

Given the learner,
$\mathbb{E}\big{[}\mathbf{x}_{1}(\mathbf{x}_{1})^{\intercal}\big{]}$ is
positive definite. For the special case of i.i.d. initial states,
$\mathbb{E}\big{[}\mathbf{x}^{i}_{1}(\mathbf{x}^{i}_{1})^{\intercal}\big{]}$=
$\operatorname{diag}((1-\frac{1}{n})\text{cov}(x_{1}),\frac{1}{n}\text{cov}(x_{1})+\mathbb{E}\big{[}x_{1}\big{]}\mathbb{E}\big{[}x_{1}\big{]}^{\intercal})$
is positive definite if $\text{cov}(x^{i}_{1})=:\text{cov}(x_{1})$ and
$\mathbb{E}\big{[}x^{i}_{1}\big{]}\mathbb{E}\big{[}x^{i}_{1}\big{]}^{\intercal}=:\mathbb{E}\big{[}x_{1}\big{]}\mathbb{E}\big{[}x_{1}\big{]}^{\intercal}$,
$i\in\mathbb{N}_{n}$, are positive definite.

######  Assumption 6.

For finite-population model, $\mathbf{Q}$ and $\mathbf{R}$ are positive
definite matrices. For the infinite-population case satisfying Assumption 3,
$Q$ and $Q+S$ are positive definite.

Assumptions 4–6 are standard conditions in the literature of LQ reinforcement
learning [1, 20], which ensure that for any stable $\bm{\theta}$,
$J(\bm{\theta})$ is properly bounded and
$\bm{\Sigma}_{\bm{\theta}}\succcurlyeq\mathbb{E}\big{[}\mathbf{x}_{1}(\mathbf{x}_{1})^{\intercal}\big{]}$
is positive definite. We now show that the best-response optimization at the
learner satisfies the Polyak-Lojasiewicz (PL) condition [21, 22], which is a
relaxation of the notion of strong convexity. Let
$\mu:=\sigma_{min}(\mathbb{E}\big{[}\mathbf{x}_{1}\mathbf{x}_{1}^{\intercal}\big{]})$.

######  Lemma 2 (PL condition).

Let Assumptions 1, 4, 5 and 6 hold. Let also $\bm{\theta}^{*}$ be the Nash
policy in Theorem 1. There exists a positive constant
$L_{1}(\bm{\theta}^{\ast})$ such that

$J(\bm{\theta})-J(\bm{\theta}^{*})\leq
L_{1}(\bm{\theta}^{\ast})\|[\nabla_{\theta}J(\bm{\theta}),\nabla_{\bar{\theta}}J(\bm{\theta})]\|_{F}^{2},$
(15)

where
$L_{1}(\bm{\theta}^{\ast})=\frac{n^{2}\|\bm{\Sigma}_{\bm{\theta}^{*}}\|}{4\mu^{2}\sigma_{\text{min}}(\mathbf{R})}$.
For the special case of infinite population (i.e. $n=\infty$) with i.i.d.
initial states under Assumptions 3, 4, 5 and 6, one has
$L_{1}(\bm{\theta}^{\ast})=\frac{\|\bm{\Sigma}^{1,1}_{\bm{\theta}^{*}}\|}{4\sigma_{min}(\text{cov}(x_{1}))^{2}\sigma_{\text{min}}(R)}+\frac{\|\bm{\Sigma}^{2,2}_{\bm{\theta}^{*}}\|}{4\sigma_{min}(\mathbb{E}[x_{1}]\mathbb{E}[x_{1}]^{\intercal})^{2}\sigma_{\text{min}}(R+S^{u})}$.

###### Proof.

The proof is presented in Appendix B. ∎

In the following lemmas, we show that the cost function and its gradient are
locally Lipschitz functions.

######  Lemma 3 (Locally Lipschitz cost function).

For any $\bm{\theta}^{\prime}$ satisfying the inequality
$\|\bm{\theta}^{\prime}-\bm{\theta}\|_{F}<\varepsilon(\bm{\theta})$, there
exists a positive constant $L_{2}(\bm{\theta})$ such that
$|J(\bm{\theta}^{\prime})-J(\bm{\theta})|\leq
L_{2}(\bm{\theta})\|\bm{\theta}^{\prime}-\bm{\theta}\|_{F}$, where the
explicit expressions of $\varepsilon(\bm{\theta})$ and $L_{2}(\bm{\theta})$
can be obtained in a similar manner as [20, Lemma 15].

###### Proof.

The proof is omitted due to space limitation. ∎

######  Lemma 4 (Locally Lipschitz gradient).

For any $\bm{\theta}^{\prime}$ satisfying the inequality
$\|\bm{\theta}^{\prime}-\bm{\theta}\|_{F}<\varepsilon(\bm{\theta})$, there
exists a positive constant $L_{3}(\bm{\theta})$ such that

$\|[\nabla J_{\theta}(\bm{\theta}^{\prime}),\nabla
J_{\bar{\theta}}(\bm{\theta}^{\prime})]-[\nabla J_{\theta}(\bm{\theta}),\nabla
J_{\bar{\theta}}(\bm{\theta})]\|_{F}\leq
L_{3}(\bm{\theta})\|\bm{\theta}^{\prime}-\bm{\theta}\|_{F},$ (16)

where the explicit expressions of $\varepsilon(\bm{\theta})$ and
$L_{3}(\bm{\theta})$ can be obtained in a similar manner as [20, Lemma 16].

###### Proof.

The proof is omitted due to space limitation. ∎

######  Theorem 2 (Global convergence via model-based gradient).

Let Assumptions 1, 4, 5 and 6 hold. For a sufficiently small fixed step size
$\eta$ chosen as
$\eta=\operatorname{poly}\big{(}\frac{\mu\sigma_{\text{min}}(\mathbf{Q})}{J(\bm{\theta}_{1})},\frac{1}{\sqrt{\gamma}\rVert\mathbf{A}\lVert},\frac{1}{\sqrt{\gamma}\rVert\mathbf{B}\lVert},\frac{1}{\rVert\mathbf{R}\lVert},\sigma_{\text{min}}(\mathbf{R})\big{)}$,
and for a sufficiently large number of iterations $K$ such that
$K\geq\frac{\rVert\mathbf{\Sigma_{\bm{\theta}^{*}}}\lVert}{\mu}\log\frac{J(\bm{\theta}_{1})-J(\bm{\theta}^{*})}{\varepsilon}\operatorname{poly}\big{(}\frac{J(\bm{\theta}_{1})}{\mu\sigma_{\text{min}}(\mathbf{Q})},{\sqrt{\gamma}\rVert\mathbf{A}\lVert},{\sqrt{\gamma}\rVert\mathbf{B}\lVert},{\rVert\mathbf{R}\lVert}$,
$\frac{1}{\sigma_{\text{min}}(\mathbf{R})}\big{)}$, the gradient descent
algorithm (13) leads to the following bound:
$J(\bm{\theta}_{K})-J(\bm{\theta}^{*})\leq\varepsilon$. In particular, for a
fixed step size
$\eta=\frac{1}{\|\mathbf{P}_{n}^{\intercal}\mathbf{P}_{n}\|(\rVert\mathbf{R}\lVert+\frac{\gamma\rVert\mathbf{B}\lVert^{2}J(\bm{\theta}_{1})}{\mu})}$
and for a sufficiently large number of iterations $K$, i.e.,
$K\geq\frac{\rVert\mathbf{\Sigma_{\bm{\theta}^{*}}}\lVert\|\mathbf{P}_{n}^{\intercal}\mathbf{P}_{n}\|}{\mu}\big{(}\frac{\rVert\mathbf{R}\lVert}{\sigma_{\text{min}}(\mathbf{R})}+\frac{\gamma\rVert\mathbf{B}\lVert^{2}J(\bm{\theta}_{1})}{\mu\sigma_{\text{min}}(\mathbf{R})}\big{)}\log\frac{J(\bm{\theta}_{1})-J(\bm{\theta}^{*})}{\varepsilon}$,
the natural policy gradient descent algorithm (14) enjoys the bound:
$J(\bm{\theta}_{K})-J(\bm{\theta}^{*})\leq\varepsilon$.

###### Proof.

Following the proof technique in [1, Theorem 7], we choose a sufficiently
small step size $\eta$ such that the value of the cost decreases at each
iteration. More precisely, for the natural policy gradient descent at
iteration $K$,
$J({\bm{\theta}}_{K+1})-J(\bm{\theta}^{*})\leq(1-\frac{\mu\sigma_{\text{min}}(\mathbf{R})}{\|\mathbf{P}_{n}^{\intercal}\mathbf{P}_{n}\|(\rVert\mathbf{R}\lVert+\frac{\gamma\rVert\mathbf{B}\lVert^{2}J(\bm{\theta_{1}})}{\mu})\rVert\mathbf{\Sigma_{\bm{\theta}^{*}}}\lVert})(J({\bm{\theta}}_{K})-J(\bm{\theta}^{*}))=(1-\eta\frac{\mu\sigma_{\text{min}}(\mathbf{R})}{\rVert\mathbf{\Sigma_{\bm{\theta}^{*}}}\lVert})(J({\bm{\theta}}_{K})-J(\bm{\theta}^{*}))$.
The above recursion is contractive for the specified $\eta$. ∎

###  III-B Model-free solution using policy optimization

It is desired now to develop a model-free RL algorithm.

######  Lemma 5 (Finite-horizon approximation).

For any $\bm{\theta}$ with finite $J(\bm{\theta})$, define
${\tilde{J}_{T}}(\bm{\theta}):=(1-\gamma)\mathbb{E}[\sum_{t=1}^{T}\gamma^{t-1}c_{t}]$
and
$\tilde{\bm{\Sigma}}_{\bm{\theta}}=(1-\gamma)\mathbb{E}[\sum_{t=1}^{T}\gamma^{t-1}\mathbf{x}_{t}\mathbf{x}_{t}^{\intercal}]$.
Let
$\varepsilon(T):=\frac{d_{x}(J(\bm{\theta}))^{2}}{(1-\gamma)T\mu\sigma_{\text{min}}^{2}(\mathbf{Q})}$
and
$\bar{\varepsilon}(T):=\varepsilon(T)(\rVert\mathbf{Q}\lVert+\rVert\mathbf{R}\lVert\rVert\mathbf{\bm{\theta}}\lVert^{2})$,
then
$\|\tilde{\bm{\Sigma}}_{\bm{\theta}}-\bm{\Sigma}_{\bm{\theta}}\|\leq\varepsilon(T)$
and $|{\tilde{J}_{T}}(\bm{\theta})-J(\bm{\theta})|\leq\bar{\varepsilon}(T)$.

###### Proof.

The proof is omitted due to space limitation. ∎

Let $\mathbb{S}_{r}$ be a set of uniformly distributed points with norm $r>0$
(e.g., the surface of a sphere). In addition, let $\mathbb{B}_{r}$ denote the
set of all uniformly distributed points whose norms are at most $r$ (e.g., all
points within the sphere). For a matrix
$\tilde{\bm{\theta}}=\operatorname{diag}(\tilde{\theta},\tilde{\bar{\theta}})$,
these distributions are defined over the Frobenius norm ball. Hence,
$J_{r}(\bm{\theta})=\mathbb{E}_{\tilde{\bm{\theta}}\sim\mathbb{B}_{r}}[J(\bm{\theta}+\tilde{\bm{\theta}})]$.
Since the expectation can be expressed as an integral function, one can use
Stokes’ formula to compute the gradient of $J_{r}(\bm{\theta})$ with only
query access to the function values.

######  Lemma 6 (Zeroth-order optimization).

For a smoothing factor $r>0$,
$[\nabla_{\theta}J(\bm{\theta}),\nabla_{\bar{\theta}}J(\bm{\theta})]=\frac{2d_{x}d_{u}}{r^{2}}\mathbb{E}_{\tilde{\bm{\theta}}\sim\mathbb{S}_{r}}[J(\bm{\theta}+\tilde{\bm{\theta}})[\tilde{\theta},\tilde{\bar{\theta}}]]$.

###### Proof.

The proof follows directly from the zeroth-order optimization approach [23,
Lemma 1]. ∎

######  Lemma 7.

Let $\tilde{\bm{\theta}}_{1},\ldots,\tilde{\bm{\theta}}_{L}$,
$L\in\mathbb{N}$, be i.i.d. samples drawn uniformly from $\mathbb{S}_{r}$.
There exists $\varepsilon(L):=\operatorname{poly}(1/L)>0$, such that
$[\tilde{\nabla}^{L}_{\theta}J(\bm{\theta}),\tilde{\nabla}^{L}_{\bar{\theta}}J(\bm{\theta})]=\frac{2d_{x}d_{u}}{r^{2}L}\sum_{l=1}^{L}J(\bm{\theta}+\tilde{\bm{\theta}}_{l})[\tilde{\theta},\tilde{\bar{\theta}}]$
converges to
$[\nabla_{\theta}J(\bm{\theta}),\nabla_{\bar{\theta}}J(\bm{\theta})]$ in the
Frobenius norm with a probability greater than
$1-({\frac{2d_{x}d_{u}}{\varepsilon(L)}})^{-2d_{x}d_{u}}$. From Lemma 5, there
exists $\varepsilon(L,T):=\operatorname{poly}(1/L,1/T)>0$ such that
$[\tilde{\nabla}^{L,T}_{\theta}J(\bm{\theta}),\tilde{\nabla}^{L,T}_{\bar{\theta}}J(\bm{\theta})]=\frac{2d_{x}d_{u}(1-\gamma)}{r^{2}L}\sum_{l=1}^{L}[\sum_{t=1}^{T}\gamma^{t-1}(c_{t})][\tilde{\theta}_{l},\tilde{\bar{\theta}}_{l}]$
is $\varepsilon(L,T)$ close to
$[\nabla_{\theta}J(\bm{\theta}),\nabla_{\bar{\theta}}J(\bm{\theta})]$ with a
probability greater than
$1-({\frac{2d_{x}d_{u}}{\varepsilon(L,T)}})^{-2d_{x}d_{u}}$ in the Frobenius
norm.

###### Proof.

The proof is omitted due to space limitation. ∎

######  Theorem 3 (Global convergence via model-free gradient).

Let Assumptions 1, 4, 5 and 6 hold. For a sufficiently large horizon $T$ and
samples $L$, model-free gradient descent and natural policy gradient decent
with the empirical gradient in Lemma 7 and covariance matrix in Lemma 5
converge to the model-based solutions in Theorem 2. In particular, the
gradient descent algorithm converges with a probability greater than
$1-({\frac{2d_{x}d_{u}}{\varepsilon(L,T)}})^{-2d_{x}d_{u}}$, where
$\varepsilon(L,T)=\operatorname{poly}(1/L,1/T)$.

###### Proof.

From [1, Theorem 31] and Theorem 2, one has the following inequality at
iteration $K\in\mathbb{N}$ for a sufficiently small step size
$\eta\leq\eta_{max}$,
$J(\bm{\theta}_{K+1})-J(\bm{\theta}^{*})\leq(1-\eta\eta_{max}^{-1})(J(\bm{\theta}_{K})-J(\bm{\theta}^{*}))$.
At iteration $K$, denote by $\tilde{\nabla}_{K}$ the empirical gradient and by
$\hat{\bm{\theta}}_{K+1}=\bm{\theta}_{K}-\eta\tilde{\nabla}_{K}$ the update
with the empirical gradient. From Lemma 3,
$|J(\hat{\bm{\theta}}_{K+1})-J(\bm{\theta}_{K+1})|\leq\frac{1}{2}\eta\eta_{max}^{-1}\varepsilon(L,T)$,
when
$\rVert\hat{\bm{\theta}}_{K+1}-\bm{\theta}_{K+1}\lVert\leq\frac{1}{2}\eta\eta_{max}^{-1}\varepsilon(L,T)(1/L_{2}(\bm{\theta}_{K+1}))$,
upon noting that
$\hat{\bm{\theta}}_{K+1}-\bm{\theta}_{K+1}=\eta(\nabla_{K}-\tilde{\nabla}_{K})$
and
$\rVert\nabla_{K}-\tilde{\nabla}_{K}\lVert\leq\frac{1}{2}\eta_{max}^{-1}\varepsilon(L,T)(1/L_{2}(\bm{\theta}_{K+1}))$.
According to the Bernstein inequality, the above inequality holds with a
probability greater than
$1-({\frac{2d_{x}d_{u}}{\varepsilon(L,T)}})^{-2d_{x}d_{u}}$. Therefore, from
Lemmas 4 and 7, the distance between the empirical gradient and the exact one
monotonically decreases as the number of samples and rollouts increases,
provided that the smoothing factor $r$ is sufficiently small. Consequently,
one arrives at
$J(\hat{\bm{\theta}}_{K+1})-J(\bm{\theta}^{*})\leq(1-\frac{1}{2}\eta\eta_{max}^{-1})(J(\bm{\theta}_{K})-J(\bm{\theta}^{*}))$,
when $J(\bm{\theta}_{K})-J(\bm{\theta}^{*})\leq\varepsilon(L,T)$. This
recursion is contractive; i.e., the rest of the proof will be similar to that
of Theorem 2. ∎

##  IV Simulations

In this section, simulations are conducted to demonstrate the global
convergence of the proposed gradient methods. To compute the Nash policy,
plotted in dashed lines in the figures, we use the solution of equation (8).

Example 1. Consider a dynamic game with the following parameters: $\eta=0.1$,
$n=100$, $T=100$, $L=3$,
$A=0.7,B=0.4,\bar{A}=0,\bar{B}=0,Q=1,R=1,S^{x}=4,S^{u}=0,\bar{Q}=0$,
$\bar{R}=0$, $\Sigma_{x}=1$ and $\Sigma_{w}=0.4$. It is observed in Figure 1
that natural policy gradient descent reaches the Nash strategy faster than the
gradient descent.

Figure 1: Convergence of the model-based gradient descent and natural policy
gradient descent algorithms in Example 1.

Example 2. Let the system parameters be $\eta=0.04$, $n=10$, $T=10$, $r=0.09$,
$L=1500$, $A=1,B=0.5,\bar{A}=0,\bar{B}=0,Q=1,R=1,S^{x}=2,S^{u}=0,\bar{Q}=1$,
$\bar{R}=0$, $r=0.09$, $\Sigma_{x}=0.05$ and $\Sigma_{w}=0.01$. The model-free
policy gradient algorithm was run on a 2.7 GHz Intel Core i5 processor for
$10$ random seeds. After $6000$ iterations, which took roughly $10$ hours,
both $\theta$ and $\bar{\theta}$ reached their optimal values as depicted in
Figure 2.

Figure 2: Convergence of the proposed model-free algorithm in Example 2.
Figure 3: The effect of the number of players on the policy in Example 3.

Example 3. In this example, let the system parameters be $\eta=0.1$, $T=100$,
$L=3$, $A=0.8,B=0.2,\bar{A}=0,\bar{B}=0,Q=1,R=1,S^{x}=2,S^{u}=0,\bar{Q}=4$,
$\bar{R}=0$, $\Sigma_{x}=1$ and $\Sigma_{w}=0.1$. To investigate the effect of
the number of players, we considered five different values for
$n\in\\{2,5,10,20,100\\}$. It is shown in Figure 3 that the policies converge
to a limit as the number of players increases, which is known as the mean-
field limit.

##  V Conclusions

In this paper, we investigated model-based and model-free gradient descent and
natural policy gradient descent algorithms for LQ deep structured games with
homogeneous weights. It was shown theoretically and verified by simulations,
that the gradient-based methods enjoy the global convergence to the sequential
Nash solution. One of the main features of the proposed solutions is that
their planning space is independent of the number of players. The obtained
results naturally extend to asymptotically vanishing weights and other
variants of policy gradient algorithms such as REINFORCE and actor-critic
methods.

## References

  * [1] M. Fazel, R. Ge, S. M. Kakade, and M. Mesbahi, “Global convergence of policy gradient methods for the linear quadratic regulator,” _arXiv preprint arXiv:1801.05039_ , 2018.
  * [2] K. Zhang, Z. Yang, and T. Basar, “Policy optimization provably converges to Nash equilibria in zero-sum linear quadratic games,” in _Advances in NeurIPS_ , 2019, pp. 11 598–11 610.
  * [3] E. Mazumdar, L. J. Ratliff, M. I. Jordan, and S. S. Sastry, “Policy-gradient algorithms have no guarantees of convergence in continuous action and state multi-agent settings,” _arXiv preprint arXiv:1907.03712_ , 2019.
  * [4] J. Arabneydi and A. G. Aghdam, “Deep teams: Decentralized decision making with finite and infinite number of agents,” _IEEE Transactions on Automatic Control, DOI: 10.1109/TAC.2020.2966035_ , 2020.
  * [5] J. Arabneydi, A. G. Aghdam, and R. P. Malhamé, “Explicit sequential equilibria in LQ deep structured games and weighted mean-field games,” _conditionally accepted in Automatica_ , 2020.
  * [6] J. Arabneydi and A. G. Aghdam, “Deep structured teams with linear quadratic model: Partial equivariance and gauge transformation,” _[Online]. Available at https://arxiv.org/abs/1912.03951_ , 2019.
  * [7] ——, “Deep structured teams and games with Markov-chain model: Finite and infinite number of players,” _Submitted_ , 2019.
  * [8] J. Arabneydi, M. Roudneshin, and A. G. Aghdam, “Reinforcement learning in deep structured teams: Initial results with finite and infinite valued features,” in _Proceedings of IEEE Conference on Control Technology and Applications_ , 2020.
  * [9] V. Fathi, J. Arabneydi, and A. G. Aghdam, “Reinforcement learning in linear quadratic deep structured teams: Global convergence of policy gradient methods,” in _Proceedings of the 59 IEEE Conference on Decision and Control_ , 2020.
  * [10] P. E. Caines, M. Huang, and R. P. Malhamé, “Mean field games,” in _Handbook of Dynamic Game Theory_ , T. Başar and G. Zaccour, Eds. Springer International Publishing, 2018, pp. 345–372.
  * [11] J. Arabneydi, “New concepts in team theory: Mean field teams and reinforcement learning,” Ph.D. dissertation, Department of Electrical and Computer Engineering, McGill University, Canada, 2016.
  * [12] R. Elliott, X. Li, and Y.-H. Ni, “Discrete time mean-field stochastic linear-quadratic optimal control problems,” _Automatica_ , vol. 49, no. 11, pp. 3222–3233, 2013.
  * [13] A. Bensoussan, J. Frehse, and P. Yam, _Mean field games and mean field type control theory_. Springer-Verlag New York, 2013.
  * [14] R. Carmona and F. Delarue, _Probabilistic Theory of Mean Field Games with Applications I-II_. Springer, 2018.
  * [15] J. Arabneydi and A. Mahajan, “Linear quadratic mean field teams: Optimal and approximately optimal decentralized solutions,” _Available at https://arxiv.org/abs/1609.00056_ , 2016.
  * [16] ——, “Team-optimal solution of finite number of mean-field coupled LQG subsystems,” in _Proceedings of the 54 IEEE Conference on Decision and Control_ , 2015, pp. 5308 – 5313.
  * [17] M. Baharloo, J. Arabneydi, and A. G. Aghdam, “Near-optimal control strategy in leader-follower networks: A case study for linear quadratic mean-field teams,” in _Proceedings of the 57 IEEE Conference on Decision and Control_ , 2018, pp. 3288–3293.
  * [18] ——, “Minmax mean-field team approach for a leader-follower network: A saddle-point strategy,” _IEEE Control Systems Letters_ , vol. 4, no. 1, pp. 121–126, 2019.
  * [19] J. Arabneydi and A. G. Aghdam, “Optimal dynamic pricing for binary demands in smart grids: A fair and privacy-preserving strategy,” in _Proceedings of American Control Conference_ , 2018, pp. 5368–5373.
  * [20] D. Malik, A. Pananjady, K. Bhatia, K. Khamaru, P. L. Bartlett, and M. J. Wainwright, “Derivative-free methods for policy optimization: Guarantees for linear quadratic systems,” _Journal of Machine Learning Research_ , vol. 21, no. 21, pp. 1–51, 2020.
  * [21] B. Polyak, “Gradient methods for solving equations and inequalities,” _USSR Computational Mathematics and Mathematical Physics_ , vol. 4, no. 6, pp. 17–32, 1964.
  * [22] S. Lojasiewicz, “A topological property of real analytic subsets,” _Coll. du CNRS, Les equations aux d´eriv´ees partielles_ , pp. 87–89, 1963\.
  * [23] A. D. Flaxman, A. T. Kalai, and H. B. McMahan, “Online convex optimization in the bandit setting: Gradient descent without a gradient,” in _Proceedings of the ACM-SIAM Symposium on Discrete Algorithms_. Society for Industrial and Applied Mathematics, 2005, p. 385–394.

##  Appendix A Proof of Lemma 1

To compute the best-response of the learner, we fix the strategies of other
players, and then find the gradient of the cost function with respect to
$\theta$ and $\bar{\theta}$. Suppose player $i\in\mathbb{N}_{n}$ uses the
strategy
$u^{i}_{t}=\theta^{i}x^{i}_{t}+(\bar{\theta}^{i}-\theta^{i})\bar{x}_{t}$.
Therefore, one has:

$\mathbf{u}^{i}_{t}=\begin{bmatrix}(1-\frac{1}{n})\theta^{i}&(1-\frac{1}{n})\bar{\theta}^{i}\\\
\frac{1}{n}\theta^{i}&\frac{1}{n}\bar{\theta}^{i}\end{bmatrix}\mathbf{x}^{i}_{t}+\sum_{j\neq
i}\begin{bmatrix}-\frac{1}{n}\theta^{j}&-\frac{1}{n}\bar{\theta}^{j}\\\
\frac{1}{n}\theta^{j}&\frac{1}{n}\bar{\theta}^{j}\end{bmatrix}\mathbf{x}^{j}_{t}.$
(17)

From (4) and (7),
$J_{\mathbf{x}^{i}_{1}}(\bm{\theta})=\mathbb{E}\big{[}(\mathbf{x}^{i}_{1})^{\intercal}\mathbf{Q}\mathbf{x}^{i}_{1}+(\mathbf{u}^{i}_{1})^{\intercal}\mathbf{R}\mathbf{u}^{i}_{1}\big{]}+\gamma
J_{\mathbf{x}^{i}_{2}}(\bm{\theta})$
$=\mathbb{E}\big{[}(\mathbf{x}^{i}_{1})^{\intercal}\mathbf{Q}\mathbf{x}^{i}_{1}+(\mathbf{u}^{i}_{1})^{\intercal}\mathbf{R}\mathbf{u}^{i}_{1}\big{]}+\gamma\mathbb{E}\big{[}(\mathbf{x}^{i}_{2})^{\intercal}\mathbf{M}(\bm{\theta})\mathbf{x}^{i}_{2}\big{]}$.
Taking the derivatives with respect to $\theta^{i}$ and $\bar{\theta}^{i}$,
and then making $\theta^{i}=\theta^{j}=\theta$ and
$\bar{\theta}^{i}=\bar{\theta}^{j}=\bar{\theta}$, leads to:

$\begin{cases}\nabla_{\theta}J_{\mathbf{x}_{1}}(\bm{\theta})=2\Big{(}(1-\frac{1}{n})(\mathbf{R}^{1,1}+\gamma{\mathbf{B}^{1,1}}^{\intercal}\mathbf{M}^{1,1}(\bm{\theta})\mathbf{B}^{1,1})\\\
+\frac{1}{n}(\mathbf{R}^{2,1}+\gamma{\mathbf{B}^{2,1}}^{\intercal}\mathbf{M}^{2,1}(\bm{\theta})\mathbf{B}^{2,1})\Big{)}\theta\mathbb{E}\big{[}\Delta
x_{1}\Delta x_{1}^{\intercal}\big{]}\\\
+2\Big{(}(1-\frac{1}{n})(\mathbf{R}^{1,2}+\gamma{\mathbf{B}^{1,2}}^{\intercal}\mathbf{M}^{1,2}(\bm{\theta})\mathbf{B}^{1,2})+\frac{1}{n}(\mathbf{R}^{2,2}\\\
+\gamma{\mathbf{B}^{2,2}}^{\intercal}\mathbf{M}^{2,2}(\bm{\theta})\mathbf{B}^{2,2})\Big{)}\bar{\theta}\mathbb{E}\big{[}\bar{x}_{1}\Delta
x_{1}^{\intercal}\big{]}+\gamma\nabla_{\theta}J_{\mathbf{x}_{2}}(\bm{\theta}),\\\
\nabla_{\bar{\theta}}J_{\mathbf{x}_{1}}(\bm{\theta})=2\Big{(}(1-\frac{1}{n})(\mathbf{R}^{1,1}+\gamma{\mathbf{B}^{1,1}}^{\intercal}\mathbf{M}^{1,1}(\bm{\theta})\mathbf{B}^{1,1})\\\
+\frac{1}{n}(\mathbf{R}^{2,1}+\gamma{\mathbf{B}^{2,1}}^{\intercal}\mathbf{M}^{2,1}(\bm{\theta})\mathbf{B}^{2,1})\Big{)}\theta\mathbb{E}\big{[}\Delta
x_{1}\bar{x}_{1}^{\intercal}\big{]}\\\
+2\Big{(}(1-\frac{1}{n})(\mathbf{R}^{1,2}+\gamma{\mathbf{B}^{1,2}}^{\intercal}\mathbf{M}^{1,2}(\bm{\theta})\mathbf{B}^{1,2})\\\
+\frac{1}{n}(\mathbf{R}^{2,2}+\gamma{\mathbf{B}^{2,2}}^{\intercal}\mathbf{M}^{2,2}(\bm{\theta})\mathbf{B}^{2,2})\Big{)}\bar{\theta}\mathbb{E}\big{[}\bar{x}_{1}\bar{x}_{1}^{\intercal}\big{]}+\gamma\nabla_{\bar{\theta}}J_{\mathbf{x}_{2}}(\bm{\theta}).\end{cases}$
(18)

The the rest of the proof follows from the recursive application of (18) and
equations (8), (III) and (12).

##  Appendix B Proof of Lemma 2

Let
$\tilde{\mathbf{P}}_{n}:=\operatorname{diag}((1-\frac{1}{n})\mathbf{I}_{d_{u}\times
d_{u}},\frac{1}{n}\mathbf{I}_{d_{u}\times d_{u}})$. We express (11) in terms
of the square matrix $\tilde{\mathbf{P}}_{n}$ such that $\Delta
J_{\theta}(\bm{\theta})=:\Delta J^{1}_{\theta}(\bm{\theta})+\Delta
J^{2}_{\theta}(\bm{\theta})$ and $\Delta J_{\bar{\theta}}(\bm{\theta})=:\Delta
J^{1}_{\bar{\theta}}(\bm{\theta})+\Delta J^{2}_{\bar{\theta}}(\bm{\theta})$,
where

$\nabla_{\bm{\theta}}\tilde{J}:=\begin{bmatrix}\Delta
J^{1}_{\theta}(\bm{\theta})&\Delta J_{\bar{\theta}}(\bm{\theta})\\\ \Delta
J^{2}_{\theta}(\bm{\theta})&\Delta
J_{\bar{\theta}}(\bm{\theta})\end{bmatrix}=2\tilde{\mathbf{P}}_{n}\mathbf{E}_{\bm{\theta}}\bm{\Sigma}_{\bm{\theta}}.$
(19)

Following [1, Lemma 10] and after some algebraic manipulations, we can derive
the following inequality for sequences
$\\{\mathbf{x}^{\ast}_{t}\\}_{t=1}^{\infty}$ and
$\\{\mathbf{u}^{\ast}_{t}\\}_{t=1}^{\infty}$ generated by the Nash policy
$\bm{\theta}^{*}$. In particular, from (11),
$\Sigma_{\bm{\theta}}\succcurlyeq\mathbb{E}\big{[}(\mathbf{x}_{1}\mathbf{x}_{1}^{\intercal})\big{]}$,
and the fact that $\tilde{\mathbf{P}}_{n}$ is positive definite for any finite
$n$, it results that:
$J(\bm{\theta})-J(\bm{\theta}^{*})\leq(1-\gamma)\mathbb{E}\sum_{t=1}^{\infty}\gamma^{t-1}\operatorname{Tr}({\mathbf{x}^{\ast}_{t}}{\mathbf{x}^{\ast}_{t}}^{\intercal}\mathbf{E}_{\bm{\theta}}^{\intercal}(\mathbf{R}+\gamma\mathbf{B}^{\intercal}\mathbf{M}_{\bm{\theta}}\mathbf{B})^{-1}\mathbf{E}_{\bm{\theta}})=\operatorname{Tr}(\Sigma_{\bm{\theta}^{*}}\mathbf{E}_{\bm{\theta}}^{\intercal}(\mathbf{R}+\gamma\mathbf{B}^{\intercal}\mathbf{M}_{\bm{\theta}}\mathbf{B})^{-1}\mathbf{E}_{\bm{\theta}})\leq\frac{\|\bm{\Sigma}_{\bm{\theta}^{*}}\|}{\sigma_{\text{min}}(\mathbf{R})}\operatorname{Tr}(\mathbf{E}_{\bm{\theta}}^{\intercal}\mathbf{E}_{\bm{\theta}})=\frac{\|\bm{\Sigma}_{\bm{\theta}^{*}}\|}{4\sigma_{\text{min}}(\mathbf{R})}\operatorname{Tr}({\bm{\Sigma}_{\bm{\theta}}}^{-1}\nabla_{\bm{\theta}}\tilde{J}^{\intercal}\mathbf{P}_{n}^{-2}\nabla_{\bm{\theta}}\tilde{J}{\bm{\Sigma}_{\bm{\theta}}}^{-1})\leq$
$\frac{0.25\mu^{-2}\|\bm{\Sigma}_{\bm{\theta}^{*}}\|}{\sigma_{\text{min}}(\tilde{\mathbf{P}_{n}})^{2}\sigma_{\text{min}}(\mathbf{R})}$
$\|[\nabla_{\theta}J(\bm{\theta}),\nabla_{\bar{\theta}}J(\bm{\theta})]\|_{F}^{2}.$
For $n=\infty$, $\tilde{\mathbf{P}}_{n}$ is not invertible; however, equation
(8) under Assumption 3 decomposes into two _decoupled_ standard Riccati
equations with matrices $(A,B,Q,R)$ and $(A,B,Q+S^{x},R+S^{u})$. By following
the approach proposed in [1, Lemma 11], it is straightforward to show that the
cost difference in this case is upper bounded by:
$\frac{\|\bm{\Sigma}^{1,1}_{\bm{\theta}^{*}}\|}{4\sigma_{min}(\text{cov}(x_{1}))^{2}\sigma_{\text{min}}(R)}\|\nabla_{\theta}J(\bm{\theta})\|_{F}^{2}$
\+
$\frac{\|\bm{\Sigma}^{2,2}_{\bm{\theta}^{*}}\|}{4\sigma_{min}(\mathbb{E}[x_{1}]\mathbb{E}[x_{1}]^{\intercal})^{2}\sigma_{\text{min}}(R+S^{u})}\|\nabla_{\bar{\theta}}J(\bm{\theta})\|_{F}^{2}$.