# Federated LQR: Learning through Sharing

Zhaolin Ren  School of Engineering and Applied Sciences, Harvard University
Aoxiao Zhong  School of Engineering and Applied Sciences, Harvard University
Zhengyuan Zhou  Na Li  School of Engineering and Applied Sciences, Harvard
University

###### Abstract

In many multi-agent reinforcement learning applications such as flocking,
multi-robot applications and smart manufacturing, distinct agents share
similar dynamics but face different objectives. In these applications, an
important question is how the similarities amongst the agents can accelerate
learning in spite of the agents’ differing goals. We study a distributed LQR
(Linear Quadratic Regulator) tracking problem which models this setting, where
the agents, acting independently, share identical (unknown) dynamics and cost
structure but need to track different targets. In this paper, we propose a
communication-efficient, federated model-free zeroth-order algorithm that
provably achieves a convergence speedup linear in the number of agents
compared with the communication-free setup where each agent’s problem is
treated independently. We support our arguments with numerical simulations of
both linear and nonlinear systems.

###### Contents

  1. 1 Introduction
    1. 1.1 Our contributions
    2. 1.2 Related work
    3. 1.3 Notations
  2. 2 Problem Setup
  3. 3 Properties of distributed LQR tracking problem
  4. 4 Algorithm design
    1. 4.1 Background on zeroth-order model-free LQR learning
    2. 4.2 Proposed algorithm: Federated LQR
  5. 5 Main results
  6. 6 Numerical results
  7. 7 Conclusion and future work
  8. A Optimal controller for LQR tracking problem
  9. B Proofs for properties of LQR tracking
    1. B.1 Lemma 1: Existence of global minimizers
    2. B.2 Lemma 2: Non-convexity
    3. B.3 Proposition 1: Gradient dominance
    4. B.4 Proposition 2: Local Lipschitzness and smoothness
  10. C Algorithms
  11. D Analysis of main results
    1. D.1 Theorem 1
    2. D.2 Theorem 2: Benchmark algorithm convergence
    3. D.3 Theorem 3: Comparison of federated and benchmark algorithm
      1. D.3.1 Properties of the one-point and two-point estimators
      2. D.3.2 Convergence for one-point estimator
      3. D.3.3 Convergence for two-point estimator
    4. D.4 Discussion
  12. E More details about numerical results
    1. E.1 Linear system
    2. E.2 Nonlinear system

##  1 Introduction

Sample complexity is an important factor in determining the broad
applicability of a Reinforcement Learning (RL) algorithm. To reduce sample
complexity and hence accelerate learning, various approaches have been
proposed in the field of parallel RL ([1, 2]), where multiple agents with the
same unknown dynamics and objective share information in their learning
process. To broaden the scope of this setting, a natural extension is to
consider the case when distinct agents share similar dynamics but seek
different objectives. This is motivated by applications such as flocking [3],
multi-robot applications [4], and smart manufacturing [5], etc. For instance,
in formation control of multi-robot systems, a group of similar robots might
need to form a pre-specified shape by tracking different target positions. We
note that our setting shares many similarities with federated learning [6],
such as (i) distributed learning via averaging of local updates, and (ii)
communication constraints. Therefore, for ease of exposition, we will use the
term _federated_ when referring to our RL problem later. 111We recognize that
unlike many papers in the federated learning literature, our work does not
consider privacy. Our use of the term “federated” is made primarily to
differentiate our setting from other works in distributed LQR learning where
agents’ dynamics or cost functions could be more general.

We are motivated by the following questions:

  1. 1.

Can the agents leverage the similarities in their problem structures in order
to accelerate learning, despite their differing targets?

  2. 2.

To what extent can they do so in a communication-efficient way?

To make concrete progress, we center our study on a federated LQR tracking
problem, where different agents follow the same (unknown) dynamics but seek to
track distinct targets. For each agent $i$, let $x_{t}^{i}\in\mathbb{R}^{n}$
and $u_{t}^{i}\in\mathbb{R}^{k}$ denote its state and action respectively at
time $t$, with the state dynamics evolving as
$x_{t+1}^{i}=Ax_{t}^{i}+Bu_{t}^{i}.$ Agent $i$’s goal is to drive the state to
a target location $x^{i*}$, which we model via the following discounted
infinite-horizon cost:

$\displaystyle\begin{array}[]{ll}\displaystyle\min_{\begin{subarray}{c}u_{t}^{i},\\\
t\in\mathbb{N}\end{subarray}}\\!\\!\\!\\!&J^{i}\\!:=\\!\displaystyle\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\left((x_{t}^{i}\\!-\\!x^{i*})^{\top}Q(x_{t}^{i}\\!-\\!x^{i*})\\!+\\!(u_{t}^{i})^{\top}Ru_{t}^{i}\right)\right]\\\
\mbox{s.t.}&x_{t+1}^{i}=Ax_{t}^{i}+Bu_{t}^{i},\quad x_{0}^{i}\sim
N(0,\Sigma),\end{array}$ (3)

where $0<\gamma<1$ is a discount factor and $\Sigma$ is a positive-definite
matrix. To ease technical analysis, we assume only the initial state
$x_{0}^{i}$ is stochastic. While the above federated LQR tracking problem
enjoys greater modelling flexibility, it brings new challenges in both
algorithm design and convergence analysis. For instance, recent work [7] has
shown that the classical LQR (single agent and $x^{i*}=0$) enjoys the
_gradient domination_ property, known also as the Polyak-Łojasiewicz
inequality ([8, 9]), a crucial condition to achieve global convergence for
policy gradient. However, it is unclear if gradient domination still holds for
our more general LQR tracking problem (even in the single agent setting). In
addition, for this problem, an optimal policy for each agent $i$ is
$u_{t}^{i}=Kx_{t}^{i}+g^{i}$ [10], where $K$ is identical across the agents,
due to the common $(A,B,Q,R)$ matrices, but the $(g^{i})$’s are distinct.
While the common $K$ suggests possible merits from pooling information, it is
unclear how the agents should efficiently aggregate/communicate their
information (without sharing their data) in joint policy learning and what the
quantitative speedup may be. Further, the distinct $(g^{i})$’s make it
difficult to ascertain if communications among the agents would be truly
beneficial.

###  1.1 Our contributions

First, we study the LQR tracking problem (3) and establish its gradient
domination property for both the single-agent and the federated setting. While
previous works [7] have established the gradient domination property of LQR
when $x^{i*}=0$, that setting is simpler as the optimal policy takes the
linear form $u^{i}=Kx^{i}$. To the best of our knowledge, this paper is the
first to establish the gradient domination property for the more general LQR
tracking problem, when an extra (and distinct) $g^{i}$ is present in each
agent’s optimal policy. Second, we exploit the fact that the same $K$ matrix
is shared across agents (despite distinct $g^{i}$ terms) and propose a model-
free federated zeroth-order policy gradient algorithm where we interweave
local update steps and averaging steps (when agents pool information on the
matrix $K$), balancing between communication efficiency (allowing for
independent updates) and benefits from shared learning (averaging over the $K$
matrix). Under mild conditions, we show that our algorithm provides a speedup
linear in the number of agents over a communication-free algorithm where each
agent learns by itself. This linear speedup, even in the important special
case where tracking is absent (i.e. all $x^{i*}=0$), is previously unknown and
contributes to the broad landscape of reinforcement learning that policy
gradient can be scaled up gracefully (in terms of both sample complexity and
computational efficiency) for the multi-agent LQR problem. Further, and
perhaps even more surprisingly, such linear speedup still remains intact even
when each agent has a heterogeneous component built in their objective.
Finally, we provide simulation results to demonstrate the effectiveness of our
proposed federated policy gradient algorithm in both the linear system setting
(where our convergence theory applies) and the nonlinear system setting (that
goes beyond our convergence guarantees).

###  1.2 Related work

First, as our setting is model-free, gradient estimators in our algorithms are
based on zeroth-order, i.e. function value information, situating our work in
the zeroth-order optimization literature ([11, 12, 13, 14, 15, 16]). Second,
our work reposes on the LQR literature. LQR is a classical reinforcement
learning problem [10], and in recent years it has been studied with renewed
vigor from both model-based ([17, 18, 19]) and model-free perspectives ([7,
20, 14]). Another line of LQR work focuses on online learning of LQR subject
to possibly adversarial conditions ([21, 22]). Our work takes a model-free
approach and is closest in spirit to ([7, 20]). Third, we note that our
problem is a special instance of parallel or concurrent RL ([1, 2, 23]).
Fourth, our work is related to federated learning, an approach proposed to
train centralized models across agents with heterogenous data distributions
subject to communication and privacy constraints ([6, 24]). Recent works have
extended federated learning to the RL setting ([25, 26]). Our proposed
algorithm uses a local computation and then aggregation procedure, a hallmark
of federated learning algorithms based on local SGD [27]. Fifth, the fact that
we seek to learn individualized policies for different agents sharing similar
problem structures relates our work to federated meta-learning ([2, 28]).

###  1.3 Notations

$\lVert\cdot\rVert$ refers to the Euclidean norm for vectors and Frobenius
norm for matrices. In addition, for any algorithm, $\mathcal{F}^{t}$ denotes
its filtration up to time $t$ and
$\mathbb{E}^{t}:=\mathbb{E}[(\cdot)\mid\mathcal{F}^{t}]$ denotes the
conditional expectation on $\mathcal{F}^{t}$. When appropriate, for any vector
$v$, we use $(v)_{K}$ to refer to its subvector corresponding to the $K$
matrix and $(v)_{g}$ to refer to its subvector corresponding to the constant
term $g$. For a positive integer $m$, $[m]$ refers to the set
$\\{1,2,\dots,m\\}$.

##  2 Problem Setup

We now formally introduce the federated LQR tracking problem. Consider $m$
agents each with the same dynamics described in (3). The overall goal is to
minimize the averaged cost of all the agents (here we denote
$\tilde{x}_{t}^{i}:=x_{t}^{i}-x^{i*}$):

$\begin{array}[]{ll}\displaystyle\min_{\begin{subarray}{c}u_{t}^{i}\\\
i\in[m]\\\
t\in\mathbb{N}\end{subarray}}\\!\\!\\!\\!\\!&J_{avg}\\!:=\\!\\!\displaystyle\frac{1}{m}\\!\sum_{i=1}^{m}\\!\mathbb{E}\\!\left[\\!\sum_{t=0}^{\infty}\\!\gamma^{t}\\!\left(\\!(\tilde{x}_{t}^{i})^{\top}\\!Q\tilde{x}_{t}^{i}+\\!(u_{t}^{i})^{\top}Ru_{t}^{i}\\!\right)\\!\right]\\\
\mbox{s.t.}&\tilde{x}_{t}^{i}:=x_{t}^{i}-x^{i*},x_{t+1}^{i}\\!=\\!Ax_{t}^{i}\\!+\\!Bu_{t}^{i},x_{0}^{i}\sim
N(0,\Sigma).\end{array}$ (4)

Because the dynamics and objectives are totally decoupled among agents, the
optimal controllers for Problem (4) are equivalent to optimal controllers for
the single agent Problem (3). As discussed earlier, agent $i$’s optimal policy
is $u_{t}^{i}=K^{i}x_{t}^{i}+g^{i}$ at time $t$ [10]. Note that the target
position, $x^{i*}$, can vary amongst the agents. Despite this, due to the
common $(A,B,Q,R)$ matrices, an optimal controller set takes the form
$\\{(K,g^{i})\\}_{i=1}^{m}$ where every agent share the same $K^{i}=K$ but
with distinct $g^{i}$. We demonstrate this property in the appendix.

Due to the above property, the following two formulations both allow us to
find an optimal controller set $\\{(K^{i},g^{i})\\}_{i=1}^{m}$ that minimizes
$J_{avg}$ for Problem (4). The first formulation, which we refer to as the
_federated_ formulation, uses the fact that we can use the same controller $K$
for each of the agents.

$\begin{array}[]{ll}\displaystyle\min_{K,G}\\!\\!\\!\\!&\bar{J}\\!(\\!K,G\\!)\\!=\\!\displaystyle\frac{1}{m}\\!\sum_{i=1}^{m}\\!\mathbb{E}\\!\left[\sum_{t=0}^{\infty}\gamma^{t}\\!\left((\\!\tilde{x}_{t}^{i}\\!)^{\top}\\!Q\tilde{x}_{t}^{i}\\!+\\!(u_{t}^{i})^{\top}\\!Ru_{t}^{i}\\!\right)\right]\\\
\mbox{s.t.}&\tilde{x}_{t}^{i}:=x_{t}^{i}-x^{i*},\
x_{t+1}^{i}\\!=\\!Ax_{t}^{i}+Bu_{t}^{i},\ u_{t}^{i}\\!=\\!Kx_{t}+g^{i},\\\
&x_{0}^{i}\\!\sim\\!N(0,\Sigma),\
G=\begin{bmatrix}g_{1}^{\top}&g_{2}^{\top}&\cdots&g_{m}^{\top}\end{bmatrix}^{\top}.\end{array}$
(5)

The second formulation, which we call the _independent_ formulation, treats
the $m$ problems independently, giving a distinct variable $K^{i}$ for each
agent $i\in[m]$.

$\begin{array}[]{ll}\displaystyle\min_{K^{i},g^{i}}\\!\\!\\!\\!&J^{i}(K^{i},g^{i})\\!=\displaystyle\\!\mathbb{E}\\!\left[\sum_{t=0}^{\infty}\\!\gamma^{t}\left((\tilde{x}_{t}^{i})^{\top}Q(\tilde{x}_{t}^{i})\\!+\\!(u_{t}^{i})^{\top}Ru_{t}^{i}\right)\right]\\\
\mbox{s.t.}&\tilde{x}_{t}^{i}:=x_{t}^{i}-x^{i*},\
x_{t+1}^{i}=Ax_{t}^{i}+Bu_{t}^{i},\\\ &u_{t}^{i}=K^{i}x_{t}+g^{i},\
x_{0}^{i}\sim N(0,\Sigma).\end{array}$ (6)

The federated formulation allows the $m$ agents to learn together based on
shared information about $K$, while the independent formulation removes
communication burdens since the agents can learn independently. In the sequel,
we will describe and develop an algorithm to minimize $J_{avg}$ that in some
sense interpolates between the two approaches, enjoying the communication
savings of independent updates as well as the information pooling from having
a single $K$. During our learning process, we assume that we are unaware of
the system matrices $A$ and $B$, but know the cost matrices $Q$ and $R$, as
well as the target $x^{i*}$ for each $i$; assuming the knowledge of stage
cost/reward functions is a reasonable assumption in many RL applications [29].
We also assume that we have full state information. Given a policy
$(K^{i},g^{i})$, and a randomly drawn initial state $x_{0}^{i}$, this allows
us to measure the cost $J^{i}(K^{i},g^{i};x_{0}^{i})$ for an agent $i$, which
is a noisy realization of the (expected) local cost $J^{i}(K^{i},g^{i})$. When
the context is clear, we may drop the index $i$ and refer to $J(K,g)$ as the
single-agent cost for LQR tracking problem. Throughout our analysis, we will
also impose the following assumptions.

######  Assumption 1.

The dynamical system governed by the matrices $(A,B)$ is controllable [10].

Thus, there exists $K\in\mathbb{R}^{k\times n}$ such that $\rho(A+BK)<1$,
where $\rho(\cdot)$ measures the spectral radius of a matrix.

######  Assumption 2.

We have access to a stable controller $K_{0}$ such that $\rho(A+BK)<1$.

This is an assumption commonly made in the LQR literature ([7, 20, 19]).

######  Assumption 3.

Cost matrices $Q$, $R$ and the covariance $\Sigma$ for the initial state are
all positive definite.

##  3 Properties of distributed LQR tracking problem

We first study the properties of $\bar{J}$ and $J^{i}$ which will facilitate
our algorithm design and analysis.

######  Lemma 1 (Existence of global minimizer).

For each $J^{i}$, $i\in[m]$, there exists $(J^{i})^{*}\geq 0$ such that

$\min_{K,g}J^{i}(K,g)=(J^{i})^{*}.$

By a similar token, there exists $J_{avg}^{*}\geq 0$ such that

$\min_{\\{K_{i},g^{i}\\}_{i=1}^{m}}\\!\frac{1}{m}\\!\sum_{i=1}^{m}\\!J^{i}(K^{i},g^{i})\\!=\\!\min_{K,G}\bar{J}(K,G)\\!=\\!\min
J_{avg}\\!=\\!J_{avg}^{*}.$

We note in particular that the global minimum values of
$\frac{1}{m}\sum_{i\in[m]}J^{i}$ (independent LQR tracking) and $\bar{J}$
(federated LQR tracking) are identical to each other and to the global minimum
of $J_{avg}$.

######  Lemma 2 (Non-convexity).

If $n\geq 2$, the LQR tracking problem (3) is in general non-convex.

This is a consequence of the fact that when $n\geq 2$, there exists matrices
$K$ and $K^{\prime}$ such that $J(K,0)$ and $J(K^{\prime},0)$ are both finite
but $J((K+K^{\prime})/2,0)$ is not finite. We provide an example in the
appendix. Without additional assumptions, gradient descent on a non-convex
problem can only reach a stationary point, not necessarily a global minimum.
However, it is known that under gradient domination and appropriate smoothness
properties, gradient descent methods, even for a non-convex problem, can find
a global minimizer at a rate comparable to that of strongly convex functions
[30]. Pioneering work in [7] established the gradient domination and local
smoothness of the classical LQR problem (where the target $x^{*}=0$), when the
optimization variable only involves $K$. We establish that both properties
hold in the more general tracking case when the policy involves $K$ as well as
$g$.

######  Proposition 1 (Gradient domination of LQR tracking problem).

Suppose $K$ is stable for the system $(A,B)$, and that $\Sigma$ is positive
definite. Then, for any agent $i$, there exists $\mu^{i}>0$ such that

$\displaystyle J_{i}(K,g^{i})\leq\mu^{i}\left\lVert\nabla
J^{i}(K,g^{i})\right\rVert^{2}.$

Moreover, for the federated cost $\bar{J}(K,G)$, letting
$\mu:=\max_{i\in[m]}\mu^{i}$, we have

$\displaystyle\bar{J}(K,G)\leq\mu\left\lVert\nabla\bar{J}(K,G)\right\rVert^{2}.$

While building on the techniques in [7], the addition of a constant term $g$
changes the complexion of the problem, and requires new analysis. We defer the
full technical proof of Proposition 1 to the appendix. However, gradient
domination alone cannot ensure convergence to a global minimum. As noted in
([7, 20]), a function needs to also exhibit local smoothness properties.

######  Proposition 2 (Local smoothness of LQR tracking problem).

Consider any $i\in[m]$. Let $\mathcal{G}_{C}=\\{(K,g)\mid J^{i}(K,g)\leq C\\}$
be a sublevel set of $J^{i}$, where $C>0$. Then, there exists a local radius
$\rho^{i}>0$, Lipschitz parameter $\lambda^{i}>0$ and Lipschitz smoothness
parameter $L^{i}>0$ such that for any $(K,g)$ in $\mathcal{G}$ , whenever
$\left\lVert(K^{\prime},g^{\prime})-(K,g)\right\rVert\leq\rho^{i}$,

$\displaystyle\left\lVert
J^{i}(K^{\prime},g^{\prime})-J^{i}(K,g)\right\rVert\\!\leq\\!\lambda^{i}\left\lVert(K^{\prime},g^{\prime})-(K,g)\right\rVert,$
$\displaystyle\left\lVert\nabla\\!J^{i}(K^{\prime},g^{\prime})\\!-\\!\nabla
J^{i}(K,g)\right\rVert\\!\leq\\!L^{i}\\!\left\lVert(K^{\prime},g^{\prime})\\!-\\!(K,g)\right\rVert.$

Similarly, for the federated cost $\bar{J}$, let
$\bar{\mathcal{G}}_{C}=\\{(K,G)\mid J^{i}(K,G)\leq C\\}$ be a sublevel set of
$\bar{J}$, where $C>0$. Then, there exists a local radius $\bar{\rho}>0$,
Lipschitz parameter $\bar{\lambda}>0$ and Lipschitz smoothness parameter such
that for any $(K,G)$ in $\bar{\mathcal{G}}_{C}$, whenever
$\lVert(K^{\prime},G^{\prime})-(K,G)\rVert\leq\bar{\rho}$,

$\displaystyle\left\lVert\bar{J}(K^{\prime},G^{\prime})-\bar{J}(K,G)\right\rVert\leq\bar{\lambda}\left\lVert(K^{\prime},G^{\prime})-(K,G)\right\rVert,$
$\displaystyle\left\lVert\nabla\\!\bar{J}(K^{\prime},G^{\prime})\\!-\\!\nabla\bar{J}(K,G)\right\rVert\\!\leq\\!\bar{L}\left\lVert(K^{\prime},G^{\prime})\\!-\\!(K,G)\right\rVert.$

We provide a proof of this result in the appendix.

##  4 Algorithm design

###  4.1 Background on zeroth-order model-free LQR learning

In model-free LQR learning, a common choice is the use of policy gradient [7].
To illustrate this, consider the single agent case, when the tracking target
$x^{*}$ is zero.222We drop the index $i$ in this subsection for ease of
notation. Then, an optimal policy to minimize the infinite-horizon cost is
given by $u_{t}=Kx_{t}$, i.e. a linear time-invariant policy. Policy gradient
on $K$ then involves iterating the update $K_{t+1}=K_{t}-\eta\hat{z}_{t}$,
where $\hat{z}_{t}$ is an estimate of the policy gradient $\nabla J(K_{t})$,
$\eta>0$ is a step-size. Exactly computing the gradient $\nabla J(K_{t})$
requires knowledge of the system matrices $(A,B)$, and recent works ([7, 20])
have proposed a zeroth-order mechanism to estimate the gradient. In this line
of work, the estimate $\hat{z}_{t}$ is calculated based on function value
information about the cost $J(\cdot)$ near the current policy $K_{t}$. One
example is the symmetric two-point estimator, where

$\displaystyle\hat{z}_{t}\\!=\\!(n\cdot
k)\frac{J(K\\!+\\!rU\\!;\\!x_{0})\\!-\\!J(K\\!-\\!rU;x_{0})}{2r}U.$

Above, $r>0$ can be viewed as a smoothing radius, and $U_{t}$ is a random
perturbation vector drawn at random from the unit sphere
$\mathrm{Unif}(\mathbb{S}^{k\cdot n-1})$, where we note that $n\cdot k$ is the
dimension of the ambient space of $K$. The factor $n\cdot k$ is necessary so
that the estimator has the same scaling as the true gradient $\nabla
J(K_{t})$. The symmetric two-point estimator resembles a finite-difference
approximation of the gradient, and as such is clearly motivated. We point out
here a technical caveat — the notation $J(K\pm rU;x_{0})$ means that the two
measurements are based on the policies $K\pm rU$ for a common random initial
state $x_{0}$. In cases when we cannot obtain two neighboring function
evaluations corresponding to the same noisy initial state $x_{0}$, a one-point
estimator based on a single function evaluation may be required ([31,
14])333While we focus on the two-point estimator for clarity in the main
paper, we do include analysis of the one-point estimator in our appendix.. In
our work, we adapt existing zeroth-order estimators proposed in the literature
to our setup, where the policy now comprises not just the matrix $K$ but also
the constant term $g$.

###  4.2 Proposed algorithm: Federated LQR

Motivation. Our overall goal is to find a controller set $\\{(K^{i},g^{i})\\}$
such that $\frac{1}{m}\sum_{i=1}^{m}J^{i}(K^{i},g^{i})$ is close to the
optimal value $J_{avg}^{*}$, using zeroth-order information to form policy
gradient updates. When the $m$ agents learn independently, they are unable to
share information on $K$. Conversely, in the federated formulation (Problem
5), since agents share the same $K$, intuitively this enables them to learn
the optimal $K$ faster, accelerating the learning process. However, the
benefits of information sharing comes at the price of increasing the amount of
communication and coordination among agents. To see this, we observe that the
gradient of the federated cost, $\bar{J}(K,G)$ where
$G=\begin{bmatrix}g_{1}^{\top}&g_{2}^{\top}&\cdots&g_{m}^{\top}\end{bmatrix}^{\top}$,
takes the following form,

$\displaystyle\nabla_{K}\bar{J}(K,G)=\frac{1}{m}\sum_{i=1}^{m}\nabla_{K}J^{i}(K,g^{i}),$
(7)
$\displaystyle\nabla_{g^{i}}\bar{J}(K,G)=\frac{1}{m}\nabla_{g^{i}}J^{i}(K,g^{i})\
\ \forall i\in[m].$ (8)

when $\rho(A+BK)<1$. While computing the gradient of $\bar{J}$ requires only
local computations of $\nabla J^{i}(K,g^{i})$ and then aggregating these
computations to form $\nabla_{K}$, this imposes a high synchronous requirement
on the agents, since communication is required for each (zeroth-order)
gradient update. The strength of the independent formulation where each
$K^{i}$ evolves freely is the absence of such communication burdens.

Our federated approach. To balance between communication efficiency and
benefits from sharing the same $K$, we propose a federated algorithm where
agents interweave steps of gradient updates using local information and steps
where they pool information on the matrix $K$. Our federated LQR learning
algorithm is provided in Algorithm 1. Below we highlight its key features.

1 Given: iteration number $T\geq 1$, communication interval $H\in\mathbb{N}$,
initial stable $K_{0}$, initial $g_{0}^{i}$ for each $i\in[m]$, step size
$\eta>0$, and smoothing radius $r>0$

2 for  _$\mbox{epoch }e\in\\{0,\dots,\frac{T}{H}-1\\}$_ do

3 Set $K_{eH}^{i}\leftarrow K_{eH}$ for each $i\in[m]$

4 for  _$\mbox{iteration }t=eH\\!,\\!eH+1\\!,\\!\dots\\!,\\!(e+1)H-1$_ do

5 for  _$\mbox{(simultaneously) each agent }i\in[m]$_ do

6 Sample $(x_{0})_{t}^{i}\sim\mathcal{D}$,
$u_{t}^{i}\sim\mathrm{Unif}(\mathbb{S}^{n\cdot k+k-1})$

7 Set the zeroth-order estimator $z_{t}^{i}$ as follows (note $d:=n\cdot k+k$)
:
$\displaystyle\\!(\\!z_{t}^{i}\\!)\\!\\!\leftarrow\\!\\!\frac{d\\!\left(\\!J^{i}((K_{t}^{i}\\!,\\!g_{t}^{i})\\!+\\!ru_{t}^{i}\\!;\\!(\\!x_{0}\\!)_{t}^{i}\\!)\\!\\!-\\!\\!J^{i}\\!(\\!(\\!(K_{t}^{i}\\!,g_{t}^{i}\\!)\\!\\!-\\!\\!ru_{t}^{i}\\!;(x_{0})_{t}^{i}\\!)\\!\right)}{2r}\\!u_{t}^{i}$
Update  $\displaystyle K_{t+1}^{i}\leftarrow K_{t}^{i}-\eta(z_{t}^{i})_{K},$
$\displaystyle g_{t+1}^{i}\leftarrow
g_{t}^{i}-\frac{\eta}{m}(z_{t}^{i})_{g},\quad t\leftarrow t+1\\!$

8 end for

9

10 end for

11 Set $K_{(e+1)H}\leftarrow\frac{1}{m}\sum_{i=1}^{m}K_{(e+1)H}^{i}$ (model
averaging of $K$ at end of epoch $e$)

12 end for

return _$K_{T},\ g_{T}^{i}\ \forall i\in[m]$_

Algorithm 1 Federated LQR Learning algorithm

  * •

Initial conditions (Line 1). We assume knowledge of a stable
$K_{0}\in\mathbb{R}^{k\times n}$. The choice of initial constant term
$g_{0}^{i}\in\mathbb{R}^{k}$ for each $i$ is flexible, and can be picked to be
the zero vector without prior information. We assume a constant step-size
$\eta$ and smoothing radius $r$.

  * •

Independent updates during each epoch (Lines 6 through 8). During the $e$-th
epoch, starting from time $t=eH$ and a common initial matrix $K_{eH}$, each
agent $i\in[m]$ simultaneously runs independent zeroth-order gradient descent
dynamics for $H$ iterations, as follows:

$\displaystyle K_{t+1}^{i}=K_{t}^{i}-\eta(z_{t}^{i})_{K},\quad
g_{t+1}^{i}=g_{t}^{i}-\frac{\eta}{m}(z_{t}^{i})_{g},$

where $z_{t}^{i}$ is the zeroth-order estimator of $\nabla
J^{i}(K_{t}^{i},g_{t}^{i})$ computed by agent $i$.

  * •

Zeroth-order gradient estimator (Line 7). We adopt a two-point zeroth-order
gradient estimator, as seen in Line 7 of the algorithm.

  * •

Averaging at the end of each epoch over $K$ (Line 10). At the end of each
epoch, we perform model averaging over the $K$ through

$K_{(e+1)H}=\frac{1}{m}\sum_{i\in[m]}K_{(e+1)H}^{i}.$

Benchmark algorithm. We evaluate the performance of our algorithm against one
which is communication-free, where the $m$ agents evolve their policy gradient
dynamics independently. We note that the zeroth-order estimator
$z_{t}^{i}(\cdot)$ is the same across both algorithms. We place description of
the benchmark algorithm in the appendix due to space limitations.

##  5 Main results

Prelimaries. We first introduce several quantities which will appear in the
main results. The reader might wish to skim this part during a first reading,
returning for a closer look later.

Consider the terms

$\displaystyle Z_{\infty}^{i}:=\max\\{\left\lVert
z_{t}^{i}(\cdot)\right\rVert\\},Z_{\infty}:=\max_{i\in[m]}Z_{\infty}^{i}$
$\displaystyle
Z_{2,K}\\!:=\\!\max_{t}\\!\frac{1}{m}\\!\sum_{i=1}^{m}\\!\mathbb{E}^{t}\\!\left\lVert(z_{t}^{i})_{K}\right\rVert^{2}\\!,Z_{2,G}\\!=\\!\max_{t}\\!\frac{1}{m}\\!\sum_{i=1}^{m}\\!\mathbb{E}^{t}\\!\left\lVert(z_{t}^{i})_{g^{i}}\right\rVert^{2}\\!,$

which collectively form bounds on the maximum size and variance of the zeroth-
order gradient update. We next define the stability region $\mathcal{G}_{0}$
and $\mathcal{G}_{0}^{\prime}$ which we show in the appendix that the iterates
of Algorithm 1 and the benchmark algorithm respectively stay within. Let

$\displaystyle\mathcal{G}_{0}:=\left\\{(K,G):\bar{J}(K,G)\leq
10\bar{J}(K_{0},G_{0})\right\\},$
$\displaystyle\mathcal{G}_{0}^{\prime}:=\left\\{\\!\\{K^{i},g^{i}\\}_{i\in[m]}\\!:\\!\frac{1}{m}\\!\sum_{i=1}^{m}\\!J^{i}\\!(\\!K^{i},g^{i}\\!)\\!\leq\\!10\frac{1}{m}\\!\sum_{i=1}^{m}\\!J^{i}\\!(\\!K_{0}^{i},g_{0}^{i}\\!)\\!\right\\}\\!.$

Next, by Proposition 2, note that there exists a local radius $\rho>0$, local
Lipschitz parameter $\lambda>0$ and local smoothness parameter $L>0$ such that
the following holds.

  1. 1.

If $(K,G)\in\mathcal{G}_{0}$, for any $i\in[m]$, and
$\lVert(K^{\prime},(g^{i})^{\prime})-(K,g^{i})\rVert\leq\rho,$ then

$\displaystyle\lVert\nabla\\!J^{i}\\!(\\!K^{\prime},(g^{i})^{\prime})\\!-\\!\nabla\\!J^{i}\\!(\\!K,g^{i}\\!)\\!\rVert\\!\leq\\!L\lVert(K^{\prime},(g^{i})^{\prime})\\!-\\!(K,g^{i})\rVert,$
$\displaystyle\lVert
J^{i}(K^{\prime},(g^{i})^{\prime})\\!-\\!J^{i}(K,g^{i})\rVert\\!\leq\\!\lambda\lVert(K^{\prime},(g^{i})^{\prime})\\!-\\!(K,g^{i})\rVert.$

  2. 2.

If $(\\{K_{i},g^{i}\\}_{i=1}^{m})\in\mathcal{G}_{0}^{\prime}$, for any
$i\in[m]$, and
$\lVert((K^{i})^{\prime},(g^{i})^{\prime})-(K^{i},g^{i})\rVert\leq\rho$,

$\lVert\\!\nabla\\!J^{i}\\!(\\!(\\!K^{i}\\!)^{\prime}\\!,\\!(g^{i})^{\prime})\\!-\\!\nabla\\!J^{i}\\!(\\!K^{i},g^{i}\\!)\\!\rVert\\!\leq\\!L\lVert\\!(\\!(K^{i})^{\prime},(g^{i})^{\prime})\\!-\\!(\\!K^{i},g^{i}\\!)\\!\rVert.$

  3. 3.

If $(K,G)\in\mathcal{G}_{0}$, and
$\left\lVert(K^{\prime},G^{\prime})-(K,G)\right\rVert\leq\rho$, then

$\lVert\nabla\bar{J}(K^{\prime},G^{\prime})-\nabla\bar{J}(K,G)\rVert\leq
L\lVert(K^{\prime},G^{\prime})-(K,G)\rVert.$

These preliminary definitions pave the way for our main results. We begin with
a statement of the convergence of the federated LQR tracking algorithm,
Algorithm 1.

######  Theorem 1 (Convergence of federated LQR tracking).

Suppose the step-size $\eta$, smoothing radius $r$ and communication interval
$H$ are chosen to satisfy

$\displaystyle\eta\\!\leq\\!\min\left\\{\\!\frac{m\epsilon}{240\\!\mu\\!L\\!\left(\\!Z_{2,G}\\!+\\!Z_{2,K}\\!+\\!6m\eta
LH^{2}Z_{\infty}^{2}\right)}\\!,\\!\frac{L}{8},\frac{\rho}{2HZ_{\infty}}\right\\}\\!,\\!$
$\displaystyle
r\leq\min\left\\{\sqrt{\frac{\epsilon\mu}{720L}}\\!,\\!\rho\right\\}.$

Then, if the error tolerance $\epsilon$ satisfies
$\epsilon\log(120\Delta_{0}/\epsilon))\leq 5\Delta_{0}$, the iterate
$(K_{t},G_{t})$ produced by Algorithm 1 satisfies

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}J^{i}(K_{T},g_{T}^{i})-J_{avg}^{*}\leq\epsilon,$

when $T=\frac{4\mu}{\eta}\log(120\Delta_{0}/\epsilon)$ steps, with probability
at least 3/4, where
$\Delta_{0}=\frac{1}{m}\sum_{i=1}^{m}J^{i}(K_{0},g_{0}^{i})-J_{avg}^{*}$.

We make a few brief remarks about Theorem 1, deferring extended discussion to
the appendix. Inherently, maintaining stability of the matrix $K$, i.e.
$\rho(A+BK)<1$, is a critical issue for LQR learning, since when $K$ is
unstable, the infinite-horizon LQR cost can diverge [7]. This stability
requirement is in tension with the constant accumulation of noise in the
learning procedure due to the stochastic zeroth-order updates. For this
reason, the convergence result holds with a constant probability, namely 0.75
(cf. Theorem 1). Nonetheless, we wish to clarify that the number 0.75 itself
can be increased by carefully tightening our analysis in certain places.
Second, to further increase the convergence probability of the overall
learning process to $1-\delta$ for _any_ $\delta>0$, we can either (i) reduce
the learning rate by using a more conservative stepsize $\eta$, or (ii)
evaluate a short list of solutions generated by several independent runs of
the algorithm (cf. [32]). We believe both these approaches will come at the
cost of an additional dependence on $\tilde{O}\left(\frac{1}{\delta}\right)$
in the sample complexity – we leave rigorous analysis of this to future work.
Finally, we note that our analysis relies heavily on the gradient domination
and local smoothness properties of the federated cost $\bar{J}$.

We have a corresponding convergence result for the benchmark distributed
independent algorithm.

######  Theorem 2 (Convergence for independent distributed LQR tracking).

Suppose

$\displaystyle\eta\leq\min\left\\{\frac{\epsilon}{240\mu
L(Z_{2,G}+Z_{2,K})},\frac{\rho}{2Z_{\infty}},\frac{L}{8},\right\\},$
$\displaystyle
r\leq\min\left\\{\sqrt{\frac{\epsilon\mu}{720L}},\rho\right\\}.$

Then, if the error tolerance $\epsilon$ satisfies
$\epsilon\log(120\Delta_{0}/\epsilon))\leq 5\Delta_{0}$, the iterates
$\\{(K_{t},g_{t}^{i})_{i=1}^{m}\\}$ produced by the benchmark algorithm
satisfy

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}J^{i}(K_{T}^{i},g_{T}^{i})-J_{avg}^{*}\leq\epsilon,$

when $T=\frac{4\mu}{\eta}\log(120\Delta_{0}/\epsilon)\mbox{ steps}$, with
probability at least 3/4, where
$\Delta_{0}=\frac{1}{m}\sum_{i=1}^{m}J^{i}(K_{0}^{i},g_{0}^{i})-J_{avg}^{*}$.

The analysis technique is similar to that for Theorem 1, and we defer further
discussion to the appendix. Building on Theorems 1 and 2, we next compare the
convergence rate of the proposed and benchmark algorithms.

######  Theorem 3 (Speedup from the federated approach).

Let $H=\tilde{O}\left(\frac{\sqrt{T}}{\sqrt{d\lambda m}}\right)$ be the
communication interval. Then, for the federated algorithm, to reach an
$\epsilon$-optimality gap with probability at least 3/4, subject to the
assumptions in Theorem 1, we will need
$T=\tilde{O}\left(\frac{d}{m\epsilon}\right)$ steps.

Meanwhile, for the benchmark, communication-free algorithm, subject to the
assumptions in Theorem 2, reaching an $\epsilon$-optimality gap with
probability at least 3/4 requires $T=\tilde{O}\left(\frac{d}{\epsilon}\right)$
steps.

Above, $\tilde{O}$ hides logarithmic factors as well as smoothness and strong
convexity parameters, and $d=n\cdot k+k$. Thus, under the assumptions set out
in Theorem 1 and Theorem 2, the federated, communication-based, approach
yields a speedup linear in the number of agents.

Under appropriate settings of $H$ (scaling as
$\tilde{O}\left(\frac{\sqrt{T}}{\sqrt{d\lambda m}}\right)$), Theorem 3 says
that convergence for the federated approach is $\tilde{O}(m)$ times faster.
This follows primarily from the periodic averaging of the $K$ matrices, which
reduces the variance in the optimization problem up to a factor of $m$ in a
similar vein to the results in the federated averaging/local SGD literature
([27, 24]). However, while ideally we can allow the step-size $\eta$ to
increase as $m$ increases, thus accelerating convergence, in practice, due to
stability concerns, there exists some maximum step-size which permits
convergence. This echoes the observation about mini-batching in [20]. A more
detailed discussion is provided in the appendix.

##  6 Numerical results

##### Linear system.

We compare our proposed algorithm with the benchmark algorithm for a federated
LQR tracking problem. We use a LQR problem with A,B, Q, R matrices each in
$\mathbb{R}^{3\times 3}$, which can be found in the appendix. Each initial
state $x_{0}^{i}$ is sampled uniformly at random from the canonical basis
vectors and the discount factor $\gamma$ is set to 0.9. The tracking targets
$x^{i*}$ for each agent are randomly sampled from a zero mean Gaussian with
covariance matrix $\frac{1}{10}\times I$. A two-point estimator is used.

In Figure 1(a), we first show the learning process of our federated algorithm
when $m=8$ (errors denote optimality gap), comparing to the learning process
of single agent. We see that the federated algorithm indeed converges,
supporting the convergence result in Theorem 1, with a convergence speed
faster than that for a single agent. Next, in Figure 1(b), we evaluate the
performance of the two algorithms by comparing the largest stepsize which
permits convergence to a fixed error threshold of $\epsilon=0.05$ with
probability at least 0.7. This is an important metric since Theorems 1 and 2
show that the number of iterations required to learn a policy whose cost is
$\epsilon$-close to the optimal cost scales inversely with the stepsize, i.e.
larger stepsize means fewer iterations needed for convergence. For the
independent algorithm, we see that maximum stepsize permitting convergence
does not increase with the number of agents, which makes sense since the
different agents learn independently. Conversely, when $H=1$, we see that the
federated approach does yield an increase in maximum stable stepsize that is
linear in the number of agents $m$ as $m$ increases from $1$ to $16$, which
supports the conclusion in Theorem 3, but that this improvement plateaus as
the number of agents increases further, confirming our earlier discussion
about stability considerations precluding arbitrarily large stepsize. As $H$
increases, i.e. less frequent communication, the increase in the maximum step-
size with the number of agents remains up to $16$ agents, beyond which the
algorithm seems to perform the same as the independent approach. This
reaffirms our observation in Theorem 3 that the maximum communication interval
permitting convergence at a rate similar to when $H=1$ scales inversely with
$\sqrt{m}$.

(a)

(b)

(c)

Figure 1: (a): Errors at each iteration of proposed algorithm and single agent
baseline on a linear system.(mean and standard deviation for 20 runs) (b):
Maximum step-size that allows for convergence to an error tolerance of
$\epsilon=0.05$. (c): Costs at each iteration of proposed algorithm on a non-
linear cartpole system.

##### Non-linear system.

To demonstrate broad applicability of our algorithm, we also perform
simulations of a nonlinear cartpole system [33]. In this system, a pole, which
starts upright with an initial degree $\theta_{0}\in[-\pi/2,\pi/2]$ and
initial angular velocity $\theta_{0}^{\prime}\in\mathbb{R}$, is attached by an
unactuated joint to a cart located at position $x\in\mathbb{R}$ along a
frictionless track with velocity $v\in\mathbb{R}$. While the underlying
dynamics are nonlinear [33], due to the model-free nature of our algorithm, we
are nonetheless able to learn a policy $(K^{i},g^{i})$ for different agents
$i$ sharing similar dynamics that all seek to balance the pole
($\theta^{i*},\theta^{\prime i*}=0$) whilst tracking a distinct target
location $x^{i*}$. For our implementation, we used the Cartpole package in
OpenAI Gym [34]. In Figure 1(c), we show the cost trajectory of the federated
algorithm for this nonlinear system, and see convergent behavior, suggesting
that our algorithm might be applicable even for nonlinear systems. More
details are provided in the appendix.

##  7 Conclusion and future work

In this paper, we proved that gradient domination holds for the general LQR
tracking problem. This paved the way for the development of a federated
algorithm that accelerates the LQR learning process for agents sharing common
dynamics but having distinct tracking targets. We highlight a few directions
for future work: (1) analyzing heterogeneous dynamics, (2) studying more
general cost functions, (3) considering adversarial noise.

## References

  * [1] Maria Dimakopoulou and Benjamin Van Roy  “Coordinated Exploration in Concurrent Reinforcement Learning”  In _Proceedings of the 35th International Conference on Machine Learning_ 80, PMLR, 2018, pp. 1270–1278
  * [2] Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis and Tamer Başar  “Communication-efficient distributed reinforcement learning”  In _arXiv preprint arXiv:1812.03239_ , 2018
  * [3] Reza Olfati-Saber  “Flocking for multi-agent dynamic systems: Algorithms and theory”  In _IEEE Transactions on automatic control_ 51.3 IEEE, 2006, pp. 401–420
  * [4] Kwang-Kyo Oh, Myoung-Chul Park and Hyo-Sung Ahn  “A survey of multi-agent formation control”  In _Automatica_ 53 Elsevier, 2015, pp. 424–440
  * [5] Hyoung Seok Kang et al.  “Smart manufacturing: Past research, present findings, and future directions”  In _International journal of precision engineering and manufacturing-green technology_ 3.1 Springer, 2016, pp. 111–128
  * [6] Jakub Konecný et al.  “Federated Learning: Strategies for Improving Communication Efficiency”  In _CoRR_ abs/1610.05492, 2016  arXiv:1610.05492
  * [7] Maryam Fazel, Rong Ge, Sham M. Kakade and Mehran Mesbahi  “Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator”  In _Proceedings of the 35th International Conference on Machine Learning_ 80, PMLR, 2018, pp. 1466–1475
  * [8] Boris T Polyak  “Gradient methods for the minimisation of functionals”  In _USSR Computational Mathematics and Mathematical Physics_ 3.4 Elsevier, 1963, pp. 864–878
  * [9] Stanisław Łojasiewicz  “A topological property of real analytic subsets”  In _Coll. du CNRS, Les ´equations aux d´eriv´ees partielles_ , 1963, pp. 87–89
  * [10] Brian DO Anderson and John B Moore  “Optimal control: linear quadratic methods”  Courier Corporation, 2007
  * [11] Yurii Nesterov and Vladimir Spokoiny  “Random gradient-free minimization of convex functions”  In _Foundations of Computational Mathematics_ 17.2 Springer, 2017, pp. 527–566
  * [12] Ohad Shamir  “An optimal algorithm for bandit and zero-order convex optimization with two-point feedback”  In _The Journal of Machine Learning Research_ 18.1 JMLR. org, 2017, pp. 1703–1713
  * [13] Davood Hajinezhad, Mingyi Hong and Alfredo Garcia  “ZONE: Zeroth-Order Nonconvex Multiagent Optimization Over Networks”  In _IEEE Transactions on Automatic Control_ 64.10 IEEE, 2019, pp. 3995–4010
  * [14] Yingying Li, Yujie Tang, Runyu Zhang and Na Li  “Distributed Reinforcement Learning for Decentralized Linear Quadratic Control: A Derivative-Free Policy Optimization Approach” 120, PMLR, 2020, pp. 814–814
  * [15] Anit Kumar Sahu, Dusan Jakovetic, Dragana Bajovic and Soummya Kar  “Distributed zeroth order optimization over random networks: A Kiefer-Wolfowitz stochastic approximation approach”  In _Proceedings of the 57th IEEE Conference on Decision and Control_ , 2018, pp. 4951–4958
  * [16] Yujie Tang and Na Li  “Distributed zero-order algorithms for nonconvex multi-agent optimization”  In _2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2019, pp. 781–786  IEEE
  * [17] Yasin Abbasi-Yadkori, Nevena Lazic and Csaba Szepesvári  “Model-Free Linear Quadratic Control via Reduction to Expert Prediction”  In _The 22nd International Conference on Artificial Intelligence and Statistics_ 89, PMLR, 2019, pp. 3108–3117
  * [18] Samet Oymak and Necmiye Ozay  “Non-asymptotic identification of lti systems from a single trajectory”  In _2019 American Control Conference (ACC)_ , 2019, pp. 5655–5661  IEEE
  * [19] Sarah Dean et al.  “On the sample complexity of the linear quadratic regulator”  In _Foundations of Computational Mathematics_ Springer, 2019, pp. 1–47
  * [20] Dhruv Malik et al.  “Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems”  In _PMLR_ 89, 2019, pp. 2916–2925
  * [21] Naman Agarwal, Elad Hazan and Karan Singh  “Logarithmic regret for online control”  In _Advances in Neural Information Processing Systems_ , 2019, pp. 10175–10184
  * [22] Max Simchowitz, Karan Singh and Elad Hazan  “Improper Learning for Non-Stochastic Control”  In _Conference on Learning Theory_ 125, PMLR, 2020, pp. 3320–3436
  * [23] Kaiqing Zhang et al.  “Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents” 80, PMLR, 2018, pp. 5872–5881
  * [24] Xiang Li et al.  “On the Convergence of FedAvg on Non-IID Data”  In _8th International Conference on Learning Representations_ , 2020
  * [25] Hankz Hankui Zhuo et al.  “Federated reinforcement learning”  In _arXiv preprint arXiv:1901.08277_ , 2019
  * [26] Boyi Liu, Lujia Wang and Ming Liu  “Lifelong federated reinforcement learning: a learning architecture for navigation in cloud robotic systems”  In _IEEE Robotics and Automation Letters_ 4.4 IEEE, 2019, pp. 4555–4562
  * [27] Sebastian U. Stich  “Local SGD Converges Fast and Communicates Little”  In _7th International Conference on Learning Representations_ , 2019
  * [28] Alireza Fallah, Aryan Mokhtari and Asuman Ozdaglar  “Personalized federated learning: A meta-learning approach”  In _arXiv preprint arXiv:2002.07948_ , 2020
  * [29] Benjamin Recht  “A tour of reinforcement learning: The view from continuous control”  In _Annual Review of Control, Robotics, and Autonomous Systems_ 2 Annual Reviews, 2019, pp. 253–279
  * [30] Hamed Karimi, Julie Nutini and Mark Schmidt  “Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition”  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , 2016, pp. 795–811  Springer
  * [31] Abraham D. Flaxman, Adam Tauman Kalai and H. McMahan  “Online convex optimization in the bandit setting: gradient descent without a gradient”  In _Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms_ , 2005, pp. 385–394
  * [32] Saeed Ghadimi and Guanghui Lan  “Stochastic first-and zeroth-order methods for nonconvex stochastic programming”  In _SIAM Journal on Optimization_ 23.4 SIAM, 2013, pp. 2341–2368
  * [33] Shlomo Geva and Joaquin Sitte  “A cartpole experiment benchmark for trainable controllers”  In _IEEE Control Systems Magazine_ 13.5 IEEE, 1993, pp. 40–51
  * [34] Greg Brockman et al.  “OpenAI Gym”, 2016  arXiv:1606.01540 [cs.LG]
  * [35] Karl Johan Åström and Richard M Murray  “Feedback systems: an introduction for scientists and engineers”  Princeton university press, 2010

##  Appendix A Optimal controller for LQR tracking problem

We derive in this section the optimal controller for the cost $J^{i}$ in
Equation 3. We will show that the optimal controller takes the form
$u_{t}^{i}=Kx_{t}^{i}+g^{i}$, where $K$ is independent of $x^{i*}$. For
convenience, we will drop the $i$ index in the superscript in this section.

######  Proposition 3 (Optimal controller for $J$).

Suppose the system given by $(\sqrt{\gamma}A,\sqrt{\gamma}B)$ is controllable.
The cost-to-go value function, $V(x_{0})$, for the discounted infinite-horizon
problem 3, takes the form

$\displaystyle V(x_{0})=x_{0}^{\top}Px_{0}+2x_{0}^{\top}q+r,$

where

$\displaystyle P=Q-(\gamma B^{\top}PA)^{\top}(R+\gamma B^{\top}PB)^{-1}(\gamma
B^{\top}PA)+\gamma A^{\top}PA,$ $\displaystyle q=-Qx^{*}-(\gamma
B^{\top}PA)^{\top}(R+\gamma B^{\top}PB)^{-1}(\gamma B^{\top}q)+\gamma
A^{\top}q,$ $\displaystyle r=(x^{*})^{\top}Qx^{*}-(\gamma
B^{\top}q)^{\top}(R+\gamma B^{\top}PB)^{-1}(\gamma B^{\top}q)+\gamma r.$

Moreover, the optimal controller is time-invariant and of the form

$\displaystyle u=Kx+g,where$

.

$K=-(R+\gamma B^{\top}PB)^{-1}(\gamma B^{\top}PA),\quad g=-(R+\gamma
B^{\top}PB)^{-1}\gamma B^{\top}q.$

In particular, note that $K$ is independent of $x^{*}$, but $g$ is not. Then,
the optimal expected cost (recall expectation is taken over the initial
condition) takes the following form

$\displaystyle C(u^{*})$
$\displaystyle=\mathbb{E}[x_{0}^{\top}Px_{0}+2x_{0}^{\top}q+r]$
$\displaystyle=\operatorname*{tr}(P\Sigma)+2\mathbb{E}[x_{0}]^{\top}q+r,$

where $\Sigma=\mathbb{E}[x_{0}x_{0}^{\top}]$.

###### Proof.

We note that the cost-to-go value function starting from $x_{0}$ takes the
form

$V(x_{0})=x_{0}^{\top}Px_{0}+2x_{0}^{\top}q+r,$

which is motivated by appealing to the value function in the finite horizon
[10] and taking the limit as $t$ goes to infinity.

Then,

$\displaystyle V(x)=\min_{u}(x-x^{*})^{\top}Q(x-x^{*})+u^{\top}Ru+\gamma
V(Ax+Bu).$

Taking the gradient with respect to $u$, we find that

$\displaystyle\nabla_{u}$
$\displaystyle=2Ru+\nabla_{u}(\gamma\left((Ax+Bu)^{\top}P(Ax+Bu)+2(Ax+Bu)^{\top}q+r\right))$
$\displaystyle=2Ru+2\gamma B^{\top}P(Ax+Bu)+2\gamma B^{\top}q.$

Setting $\nabla_{u}$ to be 0, we find that $2(R+\gamma B^{\top}PB)u+2\gamma
B^{\top}PAx+2\gamma B^{\top}q=0$, which implies that

$\displaystyle u^{*}=-(R+\gamma B^{\top}PB)^{-1}(\gamma B^{\top}PAx+\gamma
B^{\top}q).$

Then, plugging this back into $V(x)$,

$\displaystyle V(x)$
$\displaystyle=x^{\top}Qx+2x^{\top}(-Qx^{*})+(x^{*})^{\top}Qx^{*}$
$\displaystyle\quad+\left((R+\gamma B^{\top}PB)^{-1}(\gamma B^{\top}PAx+\gamma
B^{\top}q)\right)^{\top}R\left((R+\gamma B^{\top}PB)^{-1}(\gamma
B^{\top}PAx+\gamma B^{\top}q)\right)$
$\displaystyle\quad+\gamma[(Ax-B\left((R+\gamma B^{\top}PB)^{-1}(\gamma
B^{\top}PAx+\gamma B^{\top}q)\right))^{\top}P$
$\displaystyle\quad\quad(Ax-B\left((R+\gamma B^{\top}PB)^{-1}(\gamma
B^{\top}PAx+\gamma B^{\top}q)\right))^{\top}]$
$\displaystyle\quad+\gamma\left(2q^{\top}(Ax-B\left((R+\gamma
B^{\top}PB)^{-1}(\gamma B^{\top}PAx+\gamma B^{\top}q)\right))\right)+\gamma r$
$\displaystyle=x^{\top}Qx+2x^{\top}(-Qx^{*})+(x^{*})^{\top}Qx^{*}$
$\displaystyle\quad+(\gamma B^{\top}PAx+\gamma B^{\top}q)^{\top}(R+\gamma
B^{\top}PB)^{-1}(\gamma B^{\top}PAx+\gamma B^{\top}q)$
$\displaystyle\quad-\gamma\left[2(Ax)^{\top}P(B\left((R+\gamma
B^{\top}PB)^{-1}(\gamma B^{\top}PAx+\gamma B^{\top}q)\right))\right]$
$\displaystyle\quad+\gamma x^{\top}A^{\top}PAx$
$\displaystyle\quad+2\gamma\left[q^{\top}Ax-q^{\top}(B\left((R+\gamma
B^{\top}PB)^{-1}(\gamma B^{\top}PAx+\gamma B^{\top}q)\right))\right]+\gamma r$
$\displaystyle=x^{\top}Qx+2x^{\top}(-Qx^{*})+(x^{*})^{\top}Qx^{*}$
$\displaystyle\quad-(\gamma B^{\top}PAx+\gamma B^{\top}q)^{\top}(R+\gamma
B^{\top}PB)^{-1}(\gamma B^{\top}PAx+\gamma B^{\top}q)$
$\displaystyle\quad+\gamma x^{\top}A^{\top}PAx+2\gamma q^{\top}Ax+\gamma r$

Collecting terms, we find that

$\displaystyle P=Q-(\gamma B^{\top}PA)^{\top}(R+\gamma B^{\top}PB)^{-1}(\gamma
B^{\top}PA)+\gamma A^{\top}PA,$ $\displaystyle q=-Qx^{*}-(\gamma
B^{\top}PA)^{\top}(R+\gamma B^{\top}PB)^{-1}(\gamma B^{\top}q)+\gamma
A^{\top}q,$ $\displaystyle r=(x^{*})^{\top}Qx^{*}-(\gamma
B^{\top}q)^{\top}(R+\gamma B^{\top}PB)^{-1}(\gamma B^{\top}q)+\gamma r.$

∎

##  Appendix B Proofs for properties of LQR tracking

###  B.1 Lemma 1: Existence of global minimizers

###### Proof of Lemma 1..

That a minimizer exists for each $J^{i}(K,g)$, $i\in[m]$ is a consequence of
Proposition 3. That the optimal $K^{i}$ for each $J^{i}$ can be the same for
each $i\in[m]$ is consequence of the observation in Proposition 3 that the
optimal controller for $J^{i}$ does not depend on $x^{i*}$. ∎

###  B.2 Lemma 2: Non-convexity

We provide here a simple example, $n=2$ ( here $n$ is state dimension),
showing that $J(K)$, the centralized LQR cost, is non-convex. By extension
$J(K,g)$ cannot be convex in general as well.

######  Proposition 4.

Consider the centralized LQR cost

$J(K)=\sum_{t=0}^{\infty}x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t},$

where $u_{t}=Kx_{t}$, and $x_{t+1}=Ax_{t}+Bu_{t}$, where
$x_{t}\in\mathbb{R}^{n}$ and $u_{t}\in\mathbb{R}^{k}$. Then $J(K)$ is in
general non-convex for $n\geq 2$.

###### Proof.

We provide a counterexample where the set of stable controllers $K$ is not
convex. Pick

$A=\begin{bmatrix}-0.5&0\\\ 0&-0.5\end{bmatrix},\quad B=\begin{bmatrix}1&0\\\
0&1\end{bmatrix},\quad K_{1}=\begin{bmatrix}0&4040\\\ 0&0\end{bmatrix},\quad
K_{2}=\begin{bmatrix}0&0\\\ 4040&0\end{bmatrix}.$

Then, $(A,B)$ is a controllable system. In addition, observe that

$\rho(A+BK_{1})=\rho\left(\begin{bmatrix}-0.5&4040\\\
0&-0.5\end{bmatrix}\right)<1,\quad\rho(A+BK_{2})=\rho\left(\begin{bmatrix}-0.5&0\\\
4040&-0.5\end{bmatrix}\right)<1.$

However,

$\rho\left(A+B\left(\frac{K_{1}+K_{2}}{2}\right)\right)=\rho\left(\begin{bmatrix}-0.5&2020\\\
2020&-0.5\end{bmatrix}\right)>1,$

which can be shown via direct computation. This proves that LQR is in general
non-convex for $n\geq 2$. ∎

###  B.3 Proposition 1: Gradient dominance

We first prove gradient dominance for the single-agent LQR tracking, before
showing that the federated formulation with the same $K$ variable for every
agent is also gradient dominant.

Let $0<\gamma<1$ be a discount factor, and $\Sigma$ be a covariance matrix.
Consider the following problem:

$\begin{array}[]{ll}\displaystyle\min_{K,g}&J(K,g)=\mathbb{E}\left[\sum_{t}^{\infty}\gamma^{t}c(x_{t},u_{t})\right],\\\
\mbox{such
that}&c(x_{t},u_{t})=(x_{t}-x^{*})^{\top}Q(x_{t}-x^{*})+u_{t}^{\top}Ru_{t}\\\
&x_{t+1}=Ax_{t}+Bu_{t}\\\ &u_{t}=Kx_{t}+g,\\\ &x_{0}\sim
N(0,\Sigma).\end{array}$ (9)

For a policy $(K,g)$, define the following cost-go-function
$V_{K,g}:\mathbb{R}^{n}\to\mathbb{R}_{\geq 0}$, where for any
$z\in\mathbb{R}^{n}$,

$\displaystyle
V_{K,g}(z)=\sum_{t=0}^{\infty}\gamma^{t}c(x_{t},Kx_{t}+g),\quad\mbox{where
}x_{0}=z.$

######  Lemma 3.

Suppose $\sqrt{\gamma}\rho((A+BK))<1$. Then,

$\displaystyle V_{K,g}(z)=z^{\top}P_{K}z+2z^{\top}q_{K,g}+r_{K,g},$

where

$\displaystyle P_{K}=Q+K^{\top}RK+\gamma(A+BK)^{\top}P_{K}(A+BK),$
$\displaystyle
q_{K,g}=(I-\gamma(A+BK)^{\top})^{-1}\left(-Qx^{*}+K^{\top}Rg+\gamma(A+BK)^{\top}P_{K}Bg\right),$
$\displaystyle
r_{K,g}=\frac{1}{1-\gamma}\left((x^{*})^{\top}Qx^{*}+g^{\top}Rg+\gamma\left(g^{\top}B^{\top}P_{K}Bg+2g^{\top}B^{\top}q_{K,g}\right)\right).$

###### Proof.

We note that direct calculations show that
$V_{K,g}(z)=z^{\top}P_{K}z+2z^{\top}q_{K,g}+r$ for some $P_{K},q_{K,g},$ and
$r_{K,g}$. We will seek to find a recursive formula for $P_{K},q_{K,g}$ and
$r_{K,g}$. Since $V_{K,g}(z)=z^{\top}P_{K}z+2z^{\top}q_{K,g}+r_{K,g}$,

$\displaystyle V_{K,g}(z)$
$\displaystyle=z^{\top}P_{K}z+2z^{\top}q_{K,g}+r_{K,g}$
$\displaystyle=c(z,Kz+g)+\gamma V_{K,g}(Az+B(Kz+g))$
$\displaystyle=(z-x^{*})^{\top}Q(z-x^{*})+(Kz+g)^{\top}R(Kz+g)$
$\displaystyle\quad+\gamma(A+BK)z+Bg)^{\top}P_{K}((A+BK)z+Bg)+2((A+BK)z+Bg)^{\top}q_{K,g}+r_{K,g}$
$\displaystyle=z^{\top}(Q+K^{\top}RK+(A+BK)^{\top}P_{K}(A+BK))z$
$\displaystyle\quad+2z^{\top}(-Qx^{*}+K^{\top}Rg+(A+BK)^{\top}P_{K}Bg+(A+BK)^{\top}q_{K,g})$
$\displaystyle\quad+(x^{*})^{\top}x^{*}+g^{\top}Rg+\gamma
g^{\top}B^{\top}P_{K}Bg+2g^{\top}B^{\top}q_{K,g}+r_{K,g}.$

Matching coeffients, we find that

$\displaystyle P_{K}=Q+K^{\top}RK+\gamma(A+BK)^{\top}P(A+BK),$ $\displaystyle
q_{K,g}=-Qx^{*}+K^{\top}Rg+\gamma(A+BK)^{\top}P_{K}Bg+\gamma(A+BK)^{\top}q_{K,g},$
$\displaystyle
r_{K,g}=(x^{*})^{\top}Qx^{*}+g^{\top}Rg+\gamma\left[g^{\top}B^{\top}P_{K}Bg+2g^{\top}B^{\top}q_{K,g}+r_{K,g}\right].$

Some algebraic simplifications for the equations involving $q_{K,g}$ and
$r_{K,g}$ then yield the result. ∎

We next compute the gradient of $J$.

######  Lemma 4.

Define

$C_{K}=RK+\gamma B^{\top}P_{K}(BK+A),\quad d_{K,g}=Rg+\gamma
B^{\top}P_{K}Bg+\gamma B^{\top}q_{K,g}.$

The gradients of $J$ with respect to $K$ and $g$ are the following:

$\displaystyle\nabla_{K}J=2C_{K}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}x_{t}^{\top}\right]+2d_{K,g}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{\top}\right],$
$\displaystyle\nabla_{g}J=2C_{K}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}\right]+2d_{K,g}\sum_{t=0}^{\infty}\gamma^{t}.$

###### Proof.

Observe that for any $z\in\mathbb{R}^{n}$,

$\displaystyle V_{K,g}(z)$ $\displaystyle=c(z,Kz+g)+\gamma V((A+BK)z+Bg)$
$\displaystyle=(z-x^{*})^{\top}Q(z-x^{*})+(Kz+g)^{\top}R(Kz+g)$
$\displaystyle\quad+\gamma((A+BK)z+Bg)^{\top}P_{K}((A+BK)z+Bg)+2((A+BK)z+Bg)^{\top}q_{K,g}+r_{K,g}.$

Taking the gradient first with respect to $K$, we find that

$\displaystyle\nabla_{K}V_{K,g}(z)$
$\displaystyle=2R(Kz+g)z^{\top}+2\gamma\left(B^{\top}P_{K}((A+BK)z+Bg)z^{\top}+B^{\top}q_{K,g}z^{\top}\right)$
$\displaystyle\quad+\gamma\nabla_{K}V_{K,g}(x_{1})\big{|}_{x_{1}=(A+BK)z+Bg}.$

Using recursion, and taking expectations, we find that

$\displaystyle\nabla_{K}J$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{\infty}2\gamma^{t}\left((RK+\gamma
B^{\top}P_{K}(A+BK))x_{t}x_{t}^{\top}+(Rg+\gamma
B^{\top}P_{K}Bg+B^{\top}q_{K,g})x_{t}^{\top}\right)\right]$

We next compute the gradient with respect to $g$. Observe that

$\displaystyle\nabla_{g}V_{K,g}(z)$ $\displaystyle=2R(Kz+g)+2\gamma
B^{\top}P_{K}((A+BK)z+Bg)+2\gamma
B^{\top}q_{K,g}+\gamma\nabla_{g}V(x_{1})\big{|}_{x_{1}=(A+BK)z+Bg}.$

Using recursion, and taking expectations, we find that

$\displaystyle\nabla_{g}J$
$\displaystyle=2\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\left((RK+\gamma
B^{\top}P(A+BK))x_{t}+Rg+\gamma B^{\top}P_{K}Bg+\gamma
B^{\top}q_{K,g}\right)\right].$

∎

We define the advantage function $A_{K,g}(x,u)$ as

$\displaystyle A_{K,g}(x,u)$ $\displaystyle=c(x,u)+\gamma
V_{K,g}(Ax+Bu)-V_{K,g}(x).$

For any two policies $(K,g)$ and $(K^{\prime},g^{\prime})$, the next lemma
provides an expression for the difference between $J(K,g)$ and
$J(K^{\prime},g^{\prime})$ in terms of the advantage function.

######  Lemma 5.

For any two policies $(K,g)$ and $(K^{\prime},g^{\prime})$, let
$\\{(x_{t},u_{t})\\}$ and $\\{(x_{t}^{\prime},u_{t}^{\prime})\\}$ denote the
state-action trajectories corresponding to $(K,g)$ and
$(K^{\prime},g^{\prime})$ respectively, where $u_{t}=Kx_{t}+g$ and
$u_{t}^{\prime}=K^{\prime}x_{t}^{\prime}+g^{\prime}$. Then,

$\displaystyle J(K,g)-J(K^{\prime},g^{\prime})$
$\displaystyle=-\mathbb{E}\sum_{t=0}^{\infty}A_{K,g}(x_{t}^{\prime},K^{\prime}x_{t}^{\prime}+g).$

Moreover, defining

$\displaystyle C_{K}=RK+\gamma B^{\top}P(BK+A),\quad d_{K,g}=Rg+\gamma
B^{\top}PBg+\gamma B^{\top}q,$
$\displaystyle\Sigma^{*}=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{*}(x_{t}^{*})^{\top}\right],\quad\rho^{*}=\mathbb{E}\left[\sum_{t=0}\gamma^{t}x_{t}^{*}\right],\quad\beta_{\gamma}=\sum_{t=0}^{\infty}\gamma^{t},$

for an optimal policy $(K^{*},g^{*})$, we can show that

$\displaystyle J(K,g)-J(K^{*},g^{*})$
$\displaystyle\leq\frac{1}{\sigma_{\min}(R)}\left(\operatorname*{tr}(C_{K}^{\top}C_{K}\Sigma^{*})+2\operatorname*{tr}((\rho^{*})^{\top}C_{K}^{\top}d_{K,g})+d_{K,g}^{\top}d_{K,g}\beta_{\gamma}\right).$

###### Proof.

First consider the difference in cost-to-go, starting from the initial state
$x_{0}$.

$\displaystyle V_{K^{\prime},g^{\prime}}(x_{0})-V_{K,g}(x_{0})$
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}c(x_{t}^{\prime},u_{t}^{\prime})-V_{K,g}(x_{0})$
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}\left(c(x_{t}^{\prime},u_{t}^{\prime})+V_{K,g}(x_{t}^{\prime})-V_{K,g}(x_{t}^{\prime})\right)-V_{K,g}(x_{0})$
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}\left(c(x_{t}^{\prime},u_{t}^{\prime})+\gamma
V_{K,g}(x_{t+1}^{\prime})-V_{K,g}(x_{t}^{\prime})\right).$

For the last line, we utilized the fact that $x_{0}=x_{0}^{\prime}$.

Then, we get that

$\displaystyle V_{K^{\prime},g^{\prime}}(x_{0})-V_{K,g}(x_{0})$
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}A_{K,g}(x_{t}^{\prime},u_{t}^{\prime})$

We next compute $A_{K,g}(x,K^{\prime}x+g^{\prime})$. Recall that

$\displaystyle V_{K,g}(x)$
$\displaystyle=(x-x^{*})^{\top}Q(x-x^{*})+(Kx+g)^{\top}R(Kx+g)+\gamma
V_{K,g}((A+BK)x+Bg).$

Then, observe that

$\displaystyle A_{K,g}(x,K^{\prime}x+g^{\prime})$
$\displaystyle=c(x,K^{\prime}x+g^{\prime})+\gamma
V_{K,g}(Ax+B(K^{\prime}x+g^{\prime}))-V_{K,g}(x)$
$\displaystyle=(x-x^{*})^{\top}Q(x-x^{*})+(K^{\prime}x+g^{\prime})^{\top}R(K^{\prime}x+g^{\prime})$
$\displaystyle\quad+\gamma
V_{K,g}(Ax^{\prime}+B(K^{\prime}x+g^{\prime}))-V_{K,g}(x)$
$\displaystyle=x^{\top}(Q+(K^{\prime})^{\top}RK^{\prime})x+2x^{\top}\left(-Qx^{*}+(K^{\prime})^{\top}Rg^{\prime}\right)+g^{\prime\top}Rg^{\prime}$
$\displaystyle\quad+\gamma\left((A+BK^{\prime})x+Bg^{\prime}\right)^{\top}P_{K}\left((A+BK^{\prime})x+Bg^{\prime}\right)$
$\displaystyle\quad+2\gamma\left((A+BK^{\prime})x+Bg^{\prime}\right)^{\top}q_{K,g}+\gamma
r_{K,g}-V_{K,g}(x)$
$\displaystyle=x^{\top}\left(Q+(K+K^{\prime}-K)^{\top}R(K+K^{\prime}-K)\right)x$
$\displaystyle\quad+2x^{\top}\left(-Qx^{*}+(K+K^{\prime}-K)^{\top}R(g+g^{\prime}-g)\right)+(g+g^{\prime}-g)^{\top}R(g+g^{\prime}-g)$
$\displaystyle\quad+\gamma\left((A+B(K+K^{\prime}-K))x+B(g+g^{\prime}-g)\right)^{\top}P_{K}\left((A+B(K+K^{\prime}-K))x+B(g+g^{\prime}-g)\right)$
$\displaystyle\quad+2\gamma\left((A+B(K+K^{\prime}-K))x+B(g+g^{\prime}-g)\right)^{\top}q_{K,g}+\gamma
r_{K,g}-V_{K,g}(x)$
$\displaystyle=x^{\top}\left(2(K^{\prime}-K)^{\top}RK+(K^{\prime}-K)^{\top}R(K^{\prime}-K)\right)x$
$\displaystyle\quad+2x^{\top}\left((K^{\prime}-K)^{\top}Rg^{\prime}+K^{\top}R(g^{\prime}-g)\right)$
$\displaystyle\quad+2\left((g^{\prime}-g)^{\top}Rg\right)+(g^{\prime}-g)^{\top}R(g^{\prime}-g)$
$\displaystyle\quad+\gamma\left[2x^{\top}\left(B(K^{\prime}-K)\right)^{\top}P_{K}(A+BK)x+x^{\top}\left(B(K^{\prime}-K)\right)^{\top}P_{K}\left(B(K^{\prime}-K)\right)x\right]$
$\displaystyle\quad+\gamma\left[2x^{\top}\left(B(K^{\prime}-K)\right)^{\top}P_{K}(Bg^{\prime})+2x^{\top}(A+BK)^{\top}P_{K}(B(g^{\prime}-g))\right]$
$\displaystyle\quad+\gamma\left[2x^{\top}(B(K^{\prime}-K))^{\top}q_{K,g}\right]$
$\displaystyle\quad+\gamma\left[2(B(g^{\prime}-g))^{\top}P_{K}(Bg)+(B(g^{\prime}-g))^{\top}P_{K}(B(g^{\prime}-g))+2(B(g^{\prime}-g))^{\top}q_{K,g}\right]$
$\displaystyle=2\operatorname*{tr}(xx^{\top}(K^{\prime}-K)^{\top}RK)+2\operatorname*{tr}(x^{\top}(K^{\prime}-K)^{\top}R(g^{\prime}-g))+2\operatorname*{tr}(x^{\top}(K^{\prime}-K)^{\top}Rg)$
$\displaystyle\quad+2\gamma\operatorname*{tr}(x^{\top}(K^{\prime}-K)^{\top}B^{\top}P_{K}(BK+A)x)+2\gamma\operatorname*{tr}(x^{\top}(K^{\prime}-K)^{\top}B^{\top}P_{K}B(g^{\prime}-g))$
$\displaystyle\quad+2\gamma\operatorname*{tr}(x^{\top}(K^{\prime}-K)^{\top}B^{\top}P_{K}Bg)+2\gamma\operatorname*{tr}(x^{\top}(K^{\prime}-K)^{\top}B^{\top}q_{K,g})$
$\displaystyle\quad+\operatorname*{tr}(xx^{\top}(K^{\prime}-K)^{\top}(R+\gamma
B^{\top}P_{K}B)(K^{\prime}-K))$
$\displaystyle\quad+2\operatorname*{tr}(x^{\top}K^{\top}R(g^{\prime}-g))+2\operatorname*{tr}(g^{\top}R(g^{\prime}-g))+2\gamma\operatorname*{tr}((g^{\prime}-g)^{\top}B^{\top}P_{K}(A+BK)x)$
$\displaystyle\quad+2\gamma\operatorname*{tr}((g^{\prime}-g)^{\top}B^{\top}P_{K}Bg)+2\gamma\operatorname*{tr}((g^{\prime}-g)^{\top}B^{\top}q_{K,g})$
$\displaystyle\quad+(g^{\prime}-g)^{\top}(R+\gamma
B^{\top}P_{K}B)(g^{\prime}-g)$

Via completing the square, defining

$C_{K}=RK+\gamma B^{\top}P_{K}(BK+A),\quad d_{K,g}=Rg+\gamma
B^{\top}P_{K}Bg+\gamma B^{\top}q_{K,g},$

using the fact that $(R+\gamma B^{\top}P_{K}B)$ is positive definite, we find
that the advantage function satisfies the following inequality:

$\displaystyle A_{K,g}(x,K^{\prime}x+g^{\prime})$
$\displaystyle=\left((K^{\prime}-K)x+(g^{\prime}-g)+(R+\gamma
B^{\top}P_{K}B)^{-1}\left(C_{K}x+d_{K,g}\right)\right)^{\top}(R+\gamma
B^{\top}P_{K}Bg)$
$\displaystyle\quad\left((K^{\prime}-K)x+(g^{\prime}-g)+(R+\gamma
B^{\top}P_{K}B)^{-1}\left(C_{K}x+d_{K,g}\right)\right)$
$\displaystyle\quad-(C_{K}x+d_{K,g})^{\top}(R+\gamma
B^{\top}P_{K}B)^{-1}(C_{K}x+d_{K,g})$
$\displaystyle\geq-(C_{K}x+d_{K,g})^{\top}(R+\gamma
B^{\top}P_{K}B)^{-1}(C_{K}x+d_{K,g})$

Using the inequality for the advantage, and taking expectations, we find that

$\displaystyle J(K^{\prime},g^{\prime})-J(K,g)$
$\displaystyle\geq-\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}\left[(C_{K}x_{t}^{\prime}+d_{K,g})^{\top}(R+\gamma
B^{\top}P_{K}B)^{-1}(C_{K}x_{t}^{\prime}+d_{K,g})\right].$

Applying this to an optimal policy $(K^{*},g^{*})$, we find that

$\displaystyle J(K,g)-J(K^{*},g^{*})$
$\displaystyle\leq\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}\left[(C_{K}x_{t}^{*}+d_{K,g})^{\top}(R+\gamma
B^{\top}P_{K}B)^{-1}(C_{K}x_{t}^{*}+d_{K,g})\right]$
$\displaystyle\leq\frac{1}{\sigma_{\min}(R)}\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}\left[(C_{K}x_{t}^{*}+d_{K,g})^{\top}(C_{K}x_{t}^{*}+d_{K,g})\right]$
$\displaystyle=\frac{1}{\sigma_{\min}(R)}\left(\operatorname*{tr}(C_{K}^{\top}C_{K}\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{*}(x_{t}^{*})^{\top})+2\operatorname*{tr}((\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{*})^{\top}C_{K}^{\top}d_{K,g})+d_{K,g}^{\top}d_{K,g}\sum_{t=0}^{\infty}\gamma^{t}\right)$

∎

Before finally establishing gradient dominance, we first need the following
elementary linear algebra fact.

######  Lemma 6.

Suppose $g\in\mathbb{R}^{n}$ for some $n\in\mathbb{Z}_{+}$. Then, for any
positive semi-definite (PSD) $n$ by $n$ matrix $\Sigma$, the $(n+1)$ by
$(n+1)$ matrix

$\displaystyle M:=\begin{bmatrix}gg^{\top}+\Sigma&g\\\
g^{\top}&1\end{bmatrix}$

is PSD.

###### Proof.

Observe that

$\displaystyle M=\begin{bmatrix}\Sigma&0\\\
0&0\end{bmatrix}+\begin{bmatrix}g\\\
1\end{bmatrix}\begin{bmatrix}g^{\top}&1\end{bmatrix},$

where the first summand matrix is PSD, and the second summand is a rank-one
matrix outer product and hence also PSD. Thus, $M$ is PSD since the sum of two
PSD matrices is PSD. ∎

######  Proposition 5 (Gradient dominance of LQR with tracking).

Define

$C^{*}=\max\left\\{\lVert\Sigma^{*}\rVert_{2}+\lVert\rho^{*}\rVert_{2},\sum_{t=0}^{\infty}\gamma^{t}+\lVert\rho^{*}\rVert_{2}\right\\},$

where

$\Sigma^{*}:=\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{*}(x_{t}^{*})^{\top},\quad\rho^{*}:=\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{*}$

are the discounted state covariance matrix and mean vector respectively
corresponding to an optimal policy. Suppose

$\mathbb{E}[x_{0}]=0,\quad\mathbb{E}[x_{0}x_{0}^{\top}]=\Sigma\succeq\alpha
I\mbox{ for some }\alpha>0,\quad\lvert\rho(A+BK)\rvert<1.$

Then,

$\displaystyle
J(K,g)-J(K^{*},g^{*})\leq\frac{C^{*}}{4\min\\{\alpha,1\\}^{2}\sigma_{\min}(R)}\lVert\nabla
J\rVert_{F}^{2}.$

We also have a lower bound:

$J(K,g)-J(K^{*},g^{*})\geq\frac{\min\\{\alpha,1\\}}{\lVert
R+B^{\top}P_{K}B\rVert_{2}}\operatorname*{tr}(E_{K,g}^{\top}E_{K,g})$

###### Proof.

From Lemma 5, using our definition of $C^{*}$, we get that

$\displaystyle J(K,g)-J(K^{*},g^{*})$
$\displaystyle\leq\frac{1}{\sigma_{\min}(R)}\left(\operatorname*{tr}(C_{K}^{\top}C_{K}\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{*}(x_{t}^{*})^{\top})+2\operatorname*{tr}((\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{*})^{\top}C_{K}^{\top}d_{K,g})+d_{K,g}^{\top}d_{K,g}\sum_{t=0}^{\infty}\gamma^{t}\right)$
$\displaystyle\leq\frac{C^{*}}{\sigma_{\min}(R)}\left(\left\lVert
C_{K}\right\rVert_{F}^{2}+\left\lVert d_{K,g}\right\rVert_{F}^{2}\right).$

Define the quantities

$\displaystyle\Sigma_{K,g}=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}x_{t}^{\top}\right],\quad\rho_{K,g}=\mathbb{E}\left[\sum_{t=0}\gamma^{t}x_{t}\right],\quad\beta_{\gamma}=\sum_{t=0}^{\infty}\gamma^{t},$

where the state trajectory $\\{x_{t}\\}$ is generated by the policy $(K,g)$.
Then, based on Lemma 4, we have the following expression for
$\left\lVert\nabla J(K,g)\right\rVert_{F}^{2}$,

$\displaystyle\left\lVert\nabla J(K,g)\right\rVert_{F}^{2}$
$\displaystyle=4\left\lVert\begin{bmatrix}C_{K}\Sigma_{K,g}+d_{K,g}\rho_{K,g}^{\top}&C_{K}\rho_{K,g}+\beta_{\gamma}d_{K,g}\end{bmatrix}\right\rVert_{F}^{2}$
$\displaystyle=4\left\lVert\begin{bmatrix}C_{K}&d_{K,g}\end{bmatrix}\begin{bmatrix}\Sigma_{K,g}&\rho_{K,g}\\\
\rho_{K,g}^{\top}&\beta_{\gamma}\end{bmatrix}\right\rVert_{F}^{2}$
$\displaystyle=4\operatorname*{tr}(E_{K,g}^{\top}E_{K,g}M_{K,g}M_{K,g}^{\top}),$

where

$\displaystyle E_{K,g}:=\begin{bmatrix}C_{K}&d_{K,g}\end{bmatrix},\quad
M_{K,g}:=\begin{bmatrix}\Sigma_{K,g}&\rho_{K,g}\\\
\rho_{K,g}^{\top}&\beta_{\gamma}\end{bmatrix}.$

We note that

$\displaystyle M_{K,g}:$
$\displaystyle=\begin{bmatrix}\Sigma_{K,g}&\rho_{K,g}\\\
\rho_{K,g}^{\top}&\beta_{\gamma}\end{bmatrix}$
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}\begin{bmatrix}\mathbb{E}[x_{t}x_{t}^{\top}]&\mathbb{E}[x_{t}]\\\
\mathbb{E}[x_{t}]^{\top}&1\end{bmatrix}$
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}\begin{bmatrix}\mathbb{E}[x_{t}]\mathbb{E}[x_{t}]^{\top}+\mathbb{E}[(A+BK)^{t}x_{0}x_{0}^{\top}((A+BK)^{t})^{\top}]&\mathbb{E}[x_{t}]\\\
\mathbb{E}[x_{t}]^{\top}&1\end{bmatrix}$
$\displaystyle\succeq\begin{bmatrix}\Sigma&0\\\ 0&1\end{bmatrix}$
$\displaystyle\succeq\alpha\begin{bmatrix}I_{n\times n}&0\\\
0&1\end{bmatrix}.$

where we used Lemma 6 for the penultimate matrix inequality, and the
assumptions $\mathbb{E}[x_{0}]=0$ and
$\mathbb{E}[x_{0}x_{0}^{\top}]\succeq\alpha I$ for the final matrix
inequality. This implies then that

$\displaystyle\left\lVert\nabla J(K,g)\right\rVert_{F}^{2}$
$\displaystyle=4\operatorname*{tr}(E_{K,g}^{\top}E_{K,g}M_{K,g}M_{K,g}^{\top})$
$\displaystyle\geq
4\min\\{\alpha,1\\}^{2}\operatorname*{tr}(E_{K,g}^{\top}E_{K,g}).$

Therefore,

$\displaystyle J(K,g)-J(K^{*},g^{*})$
$\displaystyle\leq\frac{C^{*}}{\sigma_{\min}(R)}\left(\left\lVert
C_{K}\right\rVert_{F}^{2}+\left\lVert d_{K,g}\right\rVert_{F}^{2}\right)$
$\displaystyle=\frac{C^{*}}{\sigma_{\min}(R)}\operatorname*{tr}(E_{K,g}^{\top}E_{K,g})$
$\displaystyle\leq\frac{C^{*}}{4\min\\{\alpha,1\\}^{2}\sigma_{\min}(R)}\left\lVert\nabla
J(K,g)\right\rVert_{F}^{2}$

For the lower bound, pick $K^{\prime}=K-(R+\gamma B^{\top}P_{K}B)^{-1}C_{K}$,
and $g^{\prime}=g^{\prime}-(R+\gamma B^{\top}P_{K}B)^{-1}d_{K,g}$. Then,
following the analysis of the advantage function in Lemma 5, we have

$\displaystyle J(K,g)-J(K^{*},g^{*})$ $\displaystyle\geq
J(K,g)-J(K^{\prime},g^{\prime})$
$\displaystyle=-\mathbb{E}\sum_{t=0}A_{K,g}(x_{t}^{\prime},K^{\prime}x_{t}^{\prime}+g^{\prime})$
$\displaystyle=\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}[(C_{K}x_{t}^{\prime}+d_{K,g})^{\top}(R+\gamma
B^{\top}P_{K}B)^{-1}(C_{K}x_{t}^{\prime}+d_{K,g})]$
$\displaystyle=\operatorname*{tr}((E_{K,g}M_{K^{\prime},g^{\prime}})^{\top}(R+B^{\top}P_{K}B)^{-1}E_{K,g}M_{K^{\prime},g^{\prime}})$
$\displaystyle\geq\frac{\min\\{\alpha,1\\}}{\lVert
R+B^{\top}P_{K}B\rVert_{2}}\operatorname*{tr}(E_{K,g}^{\top}E_{K,g})$

∎

We next show that the distributed LQR tracking, considered in Problem 5, is
also gradient dominant. We hence focus our attention on $\bar{J}(K,g)$.

######  Lemma 7 (Gradient of coupled distributed LQR tracking cost).

For a policy $(K,G)=(K,g^{1},g^{2},\dots,g^{m})$, we have

$\displaystyle\nabla_{K}\bar{J}(K,G)=\sum_{i=1}^{m}2\left(C_{K}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{i}(x_{t}^{i})^{\top}\right]+d_{K,g^{i}}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}(x_{t}^{i})^{\top}\right]\right).$
$\displaystyle\nabla_{g^{i}}\bar{J}(K,G)=2\left(C_{K}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{i}\right]+d_{K,g^{i}}\sum_{t=0}^{\infty}\gamma^{t}\right)\quad\forall
i\in[m].$

###### Proof.

For any $x=(x^{1},x^{2},\dots,x^{m})\in\mathbb{R}^{mn}$, where for each
$i\in[m]$, $x^{i}\in\mathbb{R}^{n}$, define the average value function

$\displaystyle V_{K,G}(x)$ $\displaystyle:=\sum_{i=1}^{m}V_{K,g^{i}}(x^{i})$
$\displaystyle=\sum_{i=1}^{m}(x^{i})^{\top}P_{K}x^{i}+2(x^{i})^{\top}q_{K,g^{i}}+r_{K,g^{i}}.$

Then, supposing that for each $i\in[m]$, $x^{i}\stackrel{{\scriptstyle
iid}}{{\sim}}N(0,\Sigma)$, we find that

$\displaystyle\bar{J}(K,G)$ $\displaystyle=\mathbb{E}_{x}V_{K,G}(x).$

Then, differentiating, we get

$\displaystyle\nabla_{K}V_{K,G}(x)=\sum_{i=1}^{m}\nabla_{K}V_{K,g^{i}}(x^{i}),$
$\displaystyle\nabla_{g^{i}}V_{K,G}(x)=\nabla_{g^{i}}V_{K,g^{i}}(x^{i})\quad\forall
i\in[m].$

Taking expectations, using our result for the gradient of a single-agent LQR
tracking problem in Lemma 4, we find that

$\displaystyle\nabla_{K}\bar{J}(K,G)=\sum_{i=1}^{m}2\left(C_{K}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{i}(x_{t}^{i})^{\top}\right]+d_{K,g^{i}}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}(x_{t}^{i})^{\top}\right]\right).$
$\displaystyle\nabla_{g^{i}}\bar{J}(K,G)=2\left(C_{K}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{i}\right]+d_{K,g^{i}}\sum_{t=0}^{\infty}\gamma^{t}\right)\quad\forall
i\in[m].$

∎

Our next result shows that gradient dominance is preserved for the coupled LQR
tracking problem.

######  Proposition 6 (Gradient dominance for coupled LQR tracking problem).

Define

$C^{i*}=\max\left\\{\lVert\Sigma^{*}\rVert_{2}+\lVert\rho^{i*}\rVert_{2},\sum_{t=0}^{\infty}\gamma^{t}+\lVert\rho^{i*}\rVert_{2}\right\\},$

where

$\Sigma^{i*}:=\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{i*}(x_{t}^{i*})^{\top},\quad\rho^{i*}:=\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{i*}$

are the discounted state covariance matrix and mean vector respectively
corresponding to an optimal policy for agent $i$. Define then

$C^{*}=\max_{i\in m}C^{i*}.$

Suppose for each $i\in[m]$ that

$\mathbb{E}[x_{0}^{i}]=0,\quad\mathbb{E}[x_{0}^{i}(x_{0}^{i})^{\top}]=\Sigma\succeq\alpha
I\mbox{ for some }\alpha>0,\quad\lvert\rho(A+BK)\rvert<1.$

Then,

$\displaystyle\bar{J}(K,G)-\bar{J}(K^{*},G^{*})\leq\frac{C^{*}}{4\min\\{\alpha,1\\}^{2}\sigma_{\min}(R)}\lVert\nabla\bar{J}\rVert_{F}^{2}.$

###### Proof.

Building on our gradient dominance analysis for single-agent LQR tracking in
Proposition 5, we find that

$\displaystyle\bar{J}(K,G)-\bar{J}(K^{*},G^{*})$
$\displaystyle=\sum_{i=1}^{m}J(K,g^{i})-J(K^{*},(g^{i})^{*})$
$\displaystyle\leq\sum_{i=1}^{m}\frac{C^{*}}{\sigma_{\min}(R)}\left(\left\lVert
C_{K}\right\rVert_{F}^{2}+\left\lVert d_{K,g^{i}}\right\rVert_{F}^{2}\right).$

Meanwhile, defining for convenience

$\displaystyle\Sigma_{K,g^{i}}^{i}:=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{i}(x_{t}^{i})^{\top}\right]\
\ \mbox{ and }\ \
\rho_{K,g^{i}}^{i}:=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}(x_{t}^{i})^{\top}\right]\quad\forall
i\in[m],\quad\beta_{\gamma}=\sum_{t=0}^{\infty}\gamma^{t},$

using the result in Lemma 7, we have

$\displaystyle\left\lVert\nabla J(K,G)\right\rVert_{F}^{2}$
$\displaystyle=\left\lVert\nabla_{K}\bar{J}(K,G)\right\rVert_{F}^{2}+\sum_{i=1}^{m}\left\lVert\nabla_{g^{i}}\bar{J}(K,G)\right\rVert_{F}^{2}$
$\displaystyle=4\left\lVert\begin{bmatrix}C_{K}&d_{K,g^{1}}&d_{K,g^{2}}&\dots&d_{K,g^{m}}\end{bmatrix}\begin{bmatrix}\sum_{i=1}^{m}\Sigma_{K,g^{i}}^{i}&\rho_{K,g^{1}}^{1}&\rho_{K,g^{2}}^{2}&\cdots&\rho_{K,g^{m}}^{m}\\\
(\rho_{K,g^{1}}^{1})^{\top}&1&0&\cdots&0\\\
(\rho_{K,g^{2}}^{2})^{\top}&0&1&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
(\rho_{K,g^{m}}^{m})^{\top}&0&0&\cdots&1\end{bmatrix}\right\rVert^{2}$
$\displaystyle=4\operatorname*{tr}(E_{K,G}^{\top}E_{K,G}M_{K,G}M_{K,G}^{\top}),$

where

$\displaystyle
E_{K,G}:=\begin{bmatrix}C_{K}&d_{K,g^{1}}&d_{K,g^{2}}&\dots&d_{K,g^{m}}\end{bmatrix},$
$\displaystyle
M_{K,G}:=\begin{bmatrix}\sum_{i=1}^{m}\Sigma_{K,g^{i}}^{i}&\rho_{K,g^{1}}^{1}&\rho_{K,g^{2}}^{2}&\cdots&\rho_{K,g^{m}}^{m}\\\
(\rho_{K,g^{1}}^{1})^{\top}&1&0&\cdots&0\\\
(\rho_{K,g^{2}}^{2})^{\top}&0&1&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
(\rho_{K,g^{m}}^{m})^{\top}&0&0&\cdots&1\end{bmatrix}.$

Using Lemma 6, and the assumptions $\mathbb{E}[x_{0}^{i}]=0$ and
$\mathbb{E}[x_{0}^{i}(x_{0}^{i})^{\top}]=\Sigma\geq\alpha I$ for each $i$, we
can show that

$\displaystyle M_{K,G}\succeq\begin{bmatrix}m\alpha I_{n\times n}&0_{n\times
m}\\\ 0_{m\times n}&I_{m\times m}\end{bmatrix}.$

This implies then that

$\displaystyle\left\lVert\nabla\bar{J}(K,G)\right\rVert_{F}^{2}$
$\displaystyle=4\operatorname*{tr}(E_{K,G}^{\top}E_{K,G}M_{K,G}M_{K,G}^{\top})$
$\displaystyle\geq 4\left(m^{2}\alpha^{2}\left\lVert
C_{K}\right\rVert_{F}^{2}+\sum_{i=1}^{m}\left\lVert
d_{K,g^{i}}\right\rVert_{F}^{2}\right)$ $\displaystyle\geq
4\min\\{\alpha,1\\}^{2}\left(\sum_{i=1}^{m}\left\lVert
C_{K}\right\rVert_{F}^{2}+\left\lVert d_{K,g^{i}}\right\rVert_{F}^{2}\right)$

Therefore,

$\displaystyle\bar{J}(K,G)-\bar{J}(K^{*},G^{*})$
$\displaystyle\leq\sum_{i=1}^{m}\frac{C^{*}}{\sigma_{\min}(R)}\left(\left\lVert
C_{K}\right\rVert_{F}^{2}+\left\lVert d_{K,g^{i}}\right\rVert_{F}^{2}\right)$
$\displaystyle\leq\frac{C^{*}}{4\min\\{\alpha,1\\}^{2}\sigma_{\min}(R)}\left\lVert\nabla\bar{J}(K,G)\right\rVert_{F}^{2}.$

∎

The preceding work allows us to prove Proposition 6.

###### Proof of Proposition 6.

By Proposition 5, we have that

$\displaystyle J^{i}(K,g^{i})\leq\mu^{i}\lVert\nabla
J^{i}(K,g^{i})\rVert^{2},$

where

$\displaystyle\mu^{i}=\frac{C^{i*}}{4\min\\{\alpha,1\\}^{2}\sigma_{\min}(R)},$

and $C^{i*}$ is as defined in Proposition 6. In addition, by Proposition 6, we
see that

$\displaystyle\bar{J}(K,G)-\bar{J}(K^{*},G^{*})\leq\max_{i\in[m]}\mu^{i}\lVert\nabla\bar{J}(K,G)\rVert^{2}$

∎

###  B.4 Proposition 2: Local Lipschitzness and smoothness

In the sequel, without loss of generality, we assume that the covariance of
the initial noise distribution, $\Sigma$, is the identity matrix $I_{n\times
n}$.

We first define $C(K)$ to be the following cost, a standard LQR with no
tracking based on the system matrices, cost matrices and discount factor
$\gamma$.

$\begin{array}[]{ll}&C(K)=\sum_{t=0}^{\infty}x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t},\\\
\mbox{such that}&x_{t+1}=\sqrt{\gamma}Ax_{t}+\sqrt{\gamma}Bu_{t},\\\
&u_{t}=Kx_{t}.\end{array}$ (10)

This lemma shows that if $J(K,g)\leq C$ for some $C>0$, then $C(K)\leq C$.

######  Lemma 8.

Suppose $J(K,g)\leq C_{0}$ for some $C_{0}>0$, and that $\mathbb{E}[x_{0}]=0$.
Then, $C(K)\leq C_{0}$.

###### Proof.

Based on lemma 3, we see that

$\displaystyle J(K,g)$ $\displaystyle=\operatorname*{tr}(\Sigma
P_{K})+\mathbb{E}[x_{0}]^{\top}q_{K,g}+r_{K,g},$
$\displaystyle=\operatorname*{tr}(\Sigma P_{K})+r_{K,g}=C(K)+r_{K,g},$

where we used $\mathbb{E}[x_{0}]=0$ as well as the easy-to-check fact that
$C(K)=\operatorname*{tr}(\Sigma P_{K})$. Since $r_{K,g}\geq 0$ has to hold —
otherwise the value function $V(K,g;0)$, _i.e._ value function of $(K,g)$ when
$x_{0}=0$, is negative —, it follows that $J(K,g)=C(K)+r_{K,g}\leq
C_{0}\implies C(K)\leq C_{0}$. ∎

Next we show that if $J(K,g)$ is bounded by $C_{0}$, then $P_{K}$, $K$ and $g$
are all bounded by constants involving $C_{0}$ and system parameters.

######  Lemma 9.

Suppose $J(K,g)\leq C_{0}$ for some $C_{0}>0$. Then, $P_{K}\leq C_{0}$, and
moreover, there exists constants $c_{1},c_{2}>0$ depending on $C_{0}$ and
$A,B,Q,R,\gamma$ such that

$\displaystyle\lVert K\rVert\leq c_{1},\lVert g\rVert\leq c_{2}.$

###### Proof.

That $P_{K}\leq C_{0}$ holds follows from $C(K)\leq C_{0}$ and $\Sigma=I$.
Next, by Lemma 25 of [7], since $C(K)\leq C_{0}$, there exists $c_{1}$
depending on $C_{0}$ and system parameters such that $\lVert K\rVert\leq
c_{1}$.

Finally we show that $g$ is bounded. To this end, note that the cost at $t=0$
is bounded by $C_{0}$, namely

$\displaystyle\mathbb{E}[(x_{0}-x^{*})^{\top}Q(x_{0}-x^{*})+(Kx_{0}+g)^{\top}R(Kx_{0}+g)]\leq
C_{0}$
$\displaystyle\implies\operatorname*{tr}(Q)+(x^{*})^{\top}Qx^{*}+x_{0}^{\top}(K^{\top}RK)x_{0}+g^{\top}Rg\leq
C_{0}$ $\displaystyle\implies g^{\top}Rg\leq C_{0}$
$\displaystyle\implies\lVert g\rVert\leq\sqrt{C_{0}/\sigma_{\min}(R)}:=c_{2}.$

∎

Next, define $S_{K}:=(I-\gamma(A+BK)^{\top})^{-1}$. We show that $S_{K}$ is
bounded, and that the difference $\lVert S_{K^{\prime}}-S_{K}\rVert$ is
bounded by $\lVert K^{\prime}-K\rVert$ times some constant.

######  Lemma 10.

Define $S_{K}:=(I-\gamma(A+BK)^{\top})^{-1}$. Suppose $J(K,g)\leq C_{0}$.
Then,

$\displaystyle\lVert
S_{K}\rVert_{2}\leq\frac{2C_{0}}{\sigma_{\min}(Q)}:=c_{3}.$

###### Proof.

From the argument in Lemma 13 of [7], it holds that

$\displaystyle\operatorname*{tr}(\Sigma_{K})\leq\frac{C(K)}{\sigma_{\min}(Q)},$

where

$\displaystyle\Sigma_{K}=\mathbb{E}\sum_{t=0}^{\infty}x_{t}x_{t}^{\top},$

where $\\{x_{t}\\}$ is generated by the policy $u_{t}=Kx_{t}$,
$x_{t+1}=\sqrt{\gamma}Ax_{t}+\sqrt{\gamma}Bu_{t}$, and $x_{0}\sim
N(0,\Sigma)$. We first show that $\lVert
S_{K}\rVert_{2}\leq\frac{2C(K)}{\sigma_{\min}(Q)}$. To this end, since
$\sqrt{\gamma}\rho(A+BK)<1$, by the same argument as in Lemma 23 of [7], we
find that

$\displaystyle\lVert S_{K}\rVert_{2}$
$\displaystyle\leq\frac{1}{1-\sqrt{\gamma}\rho(\sqrt{\gamma}A+\sqrt{\gamma}BK)}$
$\displaystyle\leq\frac{1}{1-\rho(\sqrt{\gamma}A+\sqrt{\gamma}BK)}$
$\displaystyle\leq 2\operatorname*{tr}(\Sigma_{K})$
$\displaystyle\leq\frac{2C(K)}{\sigma_{\min}(Q)}.$

∎

Next, we seek to bound $(S_{K^{\prime}}-S_{K})$ — to be precise, we show when
$K-K^{\prime}$ is small enough, $\lVert S_{K}^{\prime}-S_{K}\rVert_{2}$ can be
bounded in terms of $\lVert K^{\prime}-K\rVert$.

######  Lemma 11.

Suppose $\lVert S_{K}\rVert_{2}(\gamma\lVert B\rVert_{2}\lVert
K-K^{\prime}\rVert)\leq\frac{1}{2}$, and $\gamma\rho(A+BK^{\prime})<1$ (so
$S_{K^{\prime}}$ is well-defined). Then,

$\displaystyle\lVert S_{K^{\prime}}-S_{K}\rVert_{2}\leq 2\lVert
S_{K}\rVert_{2}\gamma\lVert B\rVert_{2}\lVert K^{\prime}-K\rVert.$

###### Proof.

For the purposes of this proof, we define

$C:=I-\gamma(A+BK),\quad D:=\gamma B(K-K^{\prime}).$

Then, we have

$\displaystyle S_{K^{\prime}}-S_{K}$ $\displaystyle=(C+D)^{-1}-C^{-1}$
$\displaystyle=C^{-1}\left(I+C^{-1}D\right)^{-1}-C^{-1}$
$\displaystyle=C^{-1}\left((I+C^{-1}D)^{-1}-I\right)$

Next, consider $I+C^{-1}D$. Observe that

$\displaystyle(I+C^{-1}D)^{-1}=I-C^{-1}D(I+C^{-1}D)^{-1}$
$\displaystyle\implies\lVert I+C^{-1}D\rVert\leq 2,$

where the first can be verified by multiplying both sides with $I+C^{-1}D$,
and the second is a consequence of $\lVert C^{-1}D\rVert_{2}\leq\lVert
S_{K}\rVert_{2}(\gamma\lVert B\rVert_{2}\lVert K^{\prime}-K\rVert)\leq 1/2$,
our assumption. Therefore, using some algebraic manipulation, we have that

$\displaystyle S_{K^{\prime}}-S_{K}$
$\displaystyle=C^{-1}\left((I+C^{-1}D)^{-1}-I\right)$
$\displaystyle=C^{-1}(C^{-1}D(I+C^{-1}D)^{-1}),$

which implies that

$\displaystyle\lVert S_{K^{\prime}}-S_{K}\rVert_{2}$ $\displaystyle=\lVert
C^{-1}(C^{-1}D(I+C^{-1}D)^{-1})\rVert_{2}$ $\displaystyle\leq 2\gamma\lVert
S_{K}\rVert^{2}\lVert B\rVert\lVert K^{\prime}-K\rVert$

∎

Next, we show that if $K^{\prime}$ is within a ball around $K$, then we must
have $\gamma\rho(A+BK^{\prime})<1$.

######  Lemma 12.

Suppose

$\displaystyle\lVert
K^{\prime}-K\rVert\leq\frac{\sigma_{\min}(Q)}{4C(K)\lVert\sqrt{\gamma}B\rVert_{2}(\lVert\sqrt{\gamma}A+\sqrt{\gamma}BK\rVert_{2}+1)}.$

Then, $\sqrt{\gamma}(A+BK^{\prime})<1$.

###### Proof.

This follows from the same argument in Lemma 22 of [7], but with $\mu$ in that
proof replaced with 1, and the system $(A,B)$ replace by
$(\sqrt{\gamma}A,\sqrt{\gamma}B)$. ∎

Finally, we explicitly state the condition on $(K^{\prime}-K)$ such that
$\gamma\lVert S_{K}\rVert_{2}\lVert B\rVert_{2}\lVert
K^{\prime}-K\rVert\leq\frac{1}{2}$.

######  Lemma 13.

Suppose $\lVert K^{\prime}-K\rVert\leq\frac{\sigma_{\min}(Q)}{4\gamma\lVert
B\rVert C(K)}$. Then,

$\displaystyle\gamma\lVert S_{K}\rVert_{2}\lVert B\rVert_{2}\lVert
K^{\prime}-K\rVert\leq\frac{1}{2}.$

At this point, we take a chance to state a few results establishing $C(K)$ is
locally Lipschitz. These results are based on [7] and [20]. Similar to [20],
we assume boundedness of the initial distribution of $x_{0}$ in the proofs,
noting that an extension to sub-Gaussian random distribution is possible by
appealing to high-probability bounds and standard truncation arguments. Thus,
in the sequel, we will work with the assumption $\lVert x_{0}\rVert^{2}\leq
C_{n}$ for some $C_{n}>0$.

######  Lemma 14.

Suppose $C(K)\leq C_{0}$. Suppose $\lVert K^{\prime}-K\rVert\leq c_{4}$. Then,

$\displaystyle\lvert C(K^{\prime})-C(K)\rvert\leq\frac{n}{C_{n}}c_{11}\lVert
K^{\prime}-K\rVert,$ $\displaystyle\lvert
C(K^{\prime},x_{0})-C(K,x_{0})\rvert\leq c_{11}\lVert K^{\prime}-K\rVert,$
$\displaystyle\lVert
P_{K^{\prime}}-P_{K}\rVert_{2}\leq(c_{8}+c_{9}+c_{10})\lVert
K^{\prime}-K\rVert.$

By Lemma 13 of [7], it follows that $\lVert P_{K}\rVert\leq C(K)$.

Next, we prove a bound for $\lVert q_{K,g}\rVert$.

######  Lemma 15.

Suppose $\sqrt{\gamma}(A+BK)<1$, and $J(K,g)<C_{0}$. Suppose also that $\lVert
K^{\prime}-K\rVert\leq c_{4}.$ Then,

$\displaystyle\lVert q_{K,g}\rVert\leq c_{12}$

for an explicit constant $c_{12}>0$ involving $C_{0}$ and the system
parameters.

###### Proof.

We have

$\displaystyle q_{K,g}=S_{K}(-Qx^{*}+K^{\top}Rg+\gamma(A+BK)^{\top}P_{K}Bg)$

Observe that $\lVert-Qx^{*}\rVert\leq\lVert Q\rVert_{2}\lVert x^{*}\rVert$.
Next, note that

$\displaystyle\lVert K^{\top}Rg\rVert$ $\displaystyle\leq\lVert K\rVert\lVert
R\rVert\lVert g\rVert$ $\displaystyle\leq c_{1}c_{2}\lVert R\rVert.$

Next, observe that

$\displaystyle\gamma\lVert(A+BK)^{\top}P_{K}Bg\rVert$
$\displaystyle\leq\sqrt{\gamma}\lVert P_{K}\rVert\lVert B\rVert_{2}\lVert
g\rVert$ $\displaystyle\leq\sqrt{\gamma}C_{0}\lVert B\rVert_{2}c_{2}.$

This implies that

$\displaystyle\lVert q_{K,g}\rVert$ $\displaystyle=\lVert
S_{K}(-Qx^{*}+K^{\top}Rg+\gamma(A+BK)^{\top}P_{K}Bg)\rVert$
$\displaystyle\leq\lVert S_{K}\rVert_{2}\lVert-
Qx^{*}+K^{\top}Rg+\gamma(A+BK)^{\top}P_{K}Bg)\rVert$ $\displaystyle\leq
c_{3}\left(c_{1}c_{2}\lVert R\rVert+\sqrt{\gamma}C_{0}\lVert
B\rVert_{2}c_{2}+\sqrt{\gamma}C_{0}\lVert B\rVert_{2}c_{2}\right):=c_{12}.$

∎

Next, we provide a bound for the quantity
$(q_{K^{\prime},g^{\prime}}-q_{K,g})$.

######  Lemma 16.

Suppose $\sqrt{\gamma}\rho(A+BK)<1$, and $J(K,g)<C_{0}$. Suppose also that
$\lVert K^{\prime}-K\rVert\leq c_{4},\lVert g^{\prime}-g\rVert\leq 1$. Then,

$\displaystyle\lVert q_{K^{\prime},g^{\prime}}-q_{K,g}\rVert\leq c_{15}\lVert
K^{\prime}-K\rVert+c_{16}\lVert g^{\prime}-g\rVert,$

where

$c_{15}:=2\gamma c_{3}\lVert B\rVert_{2}\lVert
Qx^{*}\rVert+c_{13}+c_{14},\quad c_{16}:=2c_{1}c_{3}\lVert
R\rVert_{2}+c_{3}C_{0}\lVert B\rVert_{2}$

and $c_{13},c_{14}>0$ are constants depending on $C_{0}$ and the system
parameters, introduced in the proof later.

###### Proof.

We have

$\displaystyle q_{K^{\prime},g^{\prime}}-q_{K,g}$
$\displaystyle=S_{K^{\prime}}(-Qx^{*}+(K^{\prime})^{\top}Rg^{\prime}+\gamma(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime})$
$\displaystyle\quad-S_{K}(-Qx^{*}+K^{\top}Rg+\gamma(A+BK)^{\top}P_{K}Bg)$
$\displaystyle=(S_{K^{\prime}}-S_{K})(-Qx^{*})+\left(S_{K^{\prime}}(K^{\prime})^{\top}Rg^{\prime}-S_{K}K^{\top}Rg\right)+\left(S_{K^{\prime}}\gamma(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}-S_{K}\gamma(A+BK)^{\top}P_{K}Bg\right)$

We treat the three terms separately. First, observe that

$\displaystyle\lVert(S_{K^{\prime}}-S_{K})(-Qx^{*})\rVert$
$\displaystyle\leq(2\gamma\lVert S_{K}\rVert_{2}\lVert B\rVert_{2}\lVert
K^{\prime}-K\rVert)\lVert Q\rVert_{2}\lVert x^{*}\rVert$ $\displaystyle\leq
2\gamma c_{3}\lVert B\rVert_{2}\lVert Q\rVert_{2}\lVert x^{*}\rVert\lVert
K^{\prime}-K\rVert.$

Next, observe that

$\displaystyle\lVert
S_{K^{\prime}}(K^{\prime})^{\top}Rg^{\prime}-S_{K}K^{\top}Rg\rVert$
$\displaystyle=\lVert(S_{K^{\prime}}-S_{K})((K^{\prime})^{\top}Rg^{\prime})+S_{K}((K^{\prime})^{\top}Rg^{\prime})-S_{K}K^{\top}Rg\rVert$
$\displaystyle=\lVert(S_{K^{\prime}}-S_{K})((K^{\prime})^{\top}Rg^{\prime})+S_{K}((K^{\prime})^{\top}Rg^{\prime}-K^{\top}Rg)+S_{K}K^{\top}Rg-
S_{K}^{\top}K^{\top}Rg\rVert$ $\displaystyle\leq 2\gamma c_{3}\lVert
B\rVert_{2}\lVert K^{\prime}-K\rVert((\lVert K\rVert+1)\lVert
R\rVert_{2}\lVert g\rVert+1)$ $\displaystyle\quad+2c_{3}\left(\left\lVert
K^{\top}R(g^{\prime}-g)+(K^{\prime}-K)^{\top}Rg+(K^{\prime}-K)^{\top}R(g^{\prime}-g)\right\rVert\right)$
$\displaystyle\leq 2\gamma c_{3}\lVert B\rVert_{2}(c_{1}+1)\lVert
R\rVert_{2}(c_{2}+1)\lVert K^{\prime}-K\rVert$
$\displaystyle\quad+2c_{3}\left(\lVert K\rVert\lVert R\rVert_{2}\lVert
g^{\prime}-g\rVert+\lVert K^{\prime}-K\rVert\lVert R\rVert_{2}\lVert
g\rVert+\lVert K^{\prime}-K\rVert\lVert R\rVert_{2}\lVert
g^{\prime}-g\rVert\right)$ $\displaystyle\leq 2\gamma c_{3}\lVert
B\rVert_{2}(c_{1}+1)\lVert R\rVert_{2}(c_{2}+1)\lVert K^{\prime}-K\rVert$
$\displaystyle\quad+2c_{3}(c_{1}\lVert R\rVert_{2}\lVert
g^{\prime}-g\rVert+\lVert K^{\prime}-K\rVert\lVert R\rVert_{2}c_{2}+\lVert
R\rVert_{2}\lVert K^{\prime}-K\rVert)$ $\displaystyle=\left(2\gamma
c_{3}\lVert B\rVert_{2}(c_{1}+1)\lVert R\rVert_{2}(c_{2}+1)+\lVert
R\rVert_{2}c_{2}+\lVert R\rVert_{2}\right)\lVert
K^{\prime}-K\rVert+2c_{1}c_{3}\lVert R\rVert_{2}\lVert g^{\prime}-g\rVert$
$\displaystyle=\left(2\gamma c_{3}\lVert B\rVert_{2}(c_{1}+1)\lVert
R\rVert_{2}(c_{2}+1)+(c_{2}+1)\lVert R\rVert_{2}\right)\lVert
K^{\prime}-K\rVert+2c_{1}c_{3}\lVert R\rVert_{2}\lVert g^{\prime}-g\rVert$

We next handle
$\left(S_{K^{\prime}}\gamma(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}-S_{K}\gamma(A+BK)^{\top}P_{K}Bg\right)$.
By a similar algebraic manipulation to the immediately preceding set of
derivations, we find that

$\displaystyle\left\lVert
S_{K^{\prime}}\gamma(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}-S_{K}\gamma(A+BK)^{\top}P_{K}Bg\right\rVert$
$\displaystyle=\left\lVert(S_{K^{\prime}}-S_{K})\gamma(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}+S_{K}(\gamma(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}-\gamma(A+BK)^{\top}P_{K}Bg)\right\rVert$
$\displaystyle\leq\gamma\lVert
S_{K^{\prime}}-S_{K}\rVert\lVert(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}\rVert+\lVert
S_{K}\rVert_{2}\lVert\gamma(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}-\gamma(A+BK)^{\top}P_{K}Bg\rVert.$

We first handle $\gamma\lVert
S_{K^{\prime}}-S_{K}\rVert\lVert(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}\rVert$.
This involves bounding
$\sqrt{\gamma}\lVert(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}\rVert$. To
this end, observe that

$\displaystyle\sqrt{\gamma}\lVert(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}\rVert$
$\displaystyle\leq\lVert P_{K}^{\prime}\rVert_{2}\lVert B\rVert_{2}\lVert
g^{\prime}\rVert$ $\displaystyle=\lVert
P_{K}+P_{K^{\prime}}-P_{K}\rVert_{2}\lVert B\rVert_{2}\lVert g^{\prime}\rVert$
$\displaystyle\leq(\lVert P_{K}\rVert_{2}+(c_{8}+c_{9}+c_{10})\lVert
K^{\prime}-K\rVert)\lVert B\rVert_{2}(c_{2}+1)$
$\displaystyle\leq(C_{0}+c_{8}+c_{9}+c_{10})\lVert B\rVert_{2}(c_{2}+1)$

This gives us

$\displaystyle\gamma\lVert
S_{K^{\prime}}-S_{K}\rVert\lVert(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}\rVert$
$\displaystyle\leq\sqrt{\gamma}(C_{0}+c_{8}+c_{9}+c_{10})\lVert
B\rVert_{2}(c_{2}+1)\lVert S_{K^{\prime}}-S_{K}\rVert$
$\displaystyle\leq\sqrt{\gamma}(C_{0}+c_{8}+c_{9}+c_{10})\lVert
B\rVert_{2}(c_{2}+1)2\gamma\lVert S_{K}\rVert_{2}\lVert B\rVert_{2}\lVert
K^{\prime}-K\rVert$ $\displaystyle\leq
2\gamma^{3/2}(C_{0}+c_{8}+c_{9}+c_{10})\lVert B\rVert_{2}^{2}(c_{2}+1)\lVert
K^{\prime}-K\rVert$

Next, we handle
$\lVert\gamma(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}-\gamma(A+BK)^{\top}P_{K}Bg\rVert$.
Observe that

$\displaystyle\lVert\gamma(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}-\gamma(A+BK)^{\top}P_{K}Bg\rVert$
$\displaystyle=\left\lVert\gamma((A+BK^{\prime})^{\top}-(A+BK)^{\top})P_{K^{\prime}}Bg^{\prime}+\gamma(A+BK)^{\top}(P_{K^{\prime}}Bg^{\prime}-P_{K}Bg)\right\rVert$
$\displaystyle=\left\lVert\gamma((A+BK^{\prime})^{\top}-(A+BK)^{\top})\right\rVert\left\lVert
P_{K^{\prime}}Bg^{\prime}\right\rVert+\gamma\left\lVert(A+BK)^{\top}\left((P_{K^{\prime}}-P_{K})Bg^{\prime}+P_{K}B(g^{\prime}-g)\right)\right\rVert$
$\displaystyle\leq\gamma\lVert B\rVert_{2}^{2}\lVert
K^{\prime}-K\rVert(C_{0}+c_{8}+c_{9}+c_{10})\lVert B\rVert_{2}(c_{2}+1)$
$\displaystyle\quad+\sqrt{\gamma}\left(\lVert P_{K^{\prime}}-P_{K}\rVert\lVert
B\rVert_{2}(c_{2}+1)+\lVert P_{K}\rVert_{2}\lVert B\rVert_{2}\lVert
g^{\prime}-g\rVert\right)$ $\displaystyle\leq\gamma\lVert
B\rVert_{2}^{2}(C_{0}+c_{8}+c_{9}+c_{10})\lVert B\rVert_{2}(c_{2}+1)\lVert
K^{\prime}-K\rVert$ $\displaystyle\quad+\sqrt{\gamma}\lVert
B\rVert_{2}(c_{2}+1)(c_{8}+c_{9}+c_{10})\lVert K^{\prime}-K\rVert+C_{0}\lVert
B\rVert_{2}\lVert g^{\prime}-g\rVert$ $\displaystyle\leq(\gamma\lVert
B\rVert_{2}^{2}(C_{0}+c_{8}+c_{9}+c_{10})\lVert
B\rVert_{2}(c_{2}+1)+\sqrt{\gamma}\lVert
B\rVert_{2}(c_{2}+1)(c_{8}+c_{9}+c_{10}))\lVert K^{\prime}-K\rVert+C_{0}\lVert
B\rVert_{2}\lVert g^{\prime}-g\rVert.$

Thus,

$\displaystyle\lVert
S_{K}\rVert_{2}\lVert\gamma(A+BK^{\prime})^{\top}P_{K^{\prime}}Bg^{\prime}-\gamma(A+BK)^{\top}P_{K}Bg\rVert$
$\displaystyle\leq c_{3}(\gamma\lVert
B\rVert_{2}^{2}(C_{0}+c_{8}+c_{9}+c_{10})\lVert
B\rVert_{2}(c_{2}+1)+\sqrt{\gamma}\lVert
B\rVert_{2}(c_{2}+1)(c_{8}+c_{9}+c_{10}))\lVert K^{\prime}-K\rVert$
$\displaystyle\quad+c_{3}C_{0}\lVert B\rVert_{2}\lVert g^{\prime}-g\rVert.$

Define now

$\displaystyle c_{13}:=2\gamma c_{3}\lVert B\rVert_{2}(c_{1}+1)\lVert
R\rVert_{2}(c_{2}+1)+(c_{2}+1)\lVert R\rVert_{2},$ $\displaystyle
c_{14}=2\gamma^{3/2}(C_{0}+c_{8}+c_{9}+c_{10})\lVert B\rVert_{2}^{2}(c_{2}+1)$
$\displaystyle\quad+c_{3}(\gamma\lVert
B\rVert_{2}^{2}(C_{0}+c_{8}+c_{9}+c_{10})\lVert
B\rVert_{2}(c_{2}+1)+\sqrt{\gamma}\lVert
B\rVert_{2}(c_{2}+1)(c_{8}+c_{9}+c_{10}))$

Then, combining everything, we find that

$\displaystyle\lVert q_{K^{\prime},g^{\prime}}-q_{K,g}\rVert$
$\displaystyle\leq(2\gamma c_{3}\lVert B\rVert_{2}\lVert
Qx^{*}\rVert+c_{13}+c_{14})\lVert K^{\prime}-K\rVert+(2c_{1}c_{3}\lVert
R\rVert_{2}+c_{3}C_{0}\lVert B\rVert_{2})\lVert g^{\prime}-g\rVert$

∎

We are now finally ready to bound $(r_{K^{\prime},g^{\prime}}-r_{K,g})$, after
which we can wrap up our local Lipschitz argument for $J(K,g)$.

######  Lemma 17.

Suppose $\sqrt{\gamma}\rho(A+BK)<1$, and $J(K,g)<C_{0}$. Suppose also that
$\lVert K^{\prime}-K\rVert\leq c_{4},\lVert g^{\prime}-g\rVert\leq 1$. Then,

$\displaystyle\lVert r_{K^{\prime},g^{\prime}}-r_{K,g}\rVert\leq c_{19}\lVert
K^{\prime}-K\rVert+c_{20}\lVert g^{\prime}-g\rVert$

where

$c_{19}:=c_{17}+c_{18},$

and

$\displaystyle c_{17}:=\frac{1}{1-\gamma}\left[2c_{2}+1+\gamma(\lVert
B\rVert_{2}^{2}(C_{0}+c_{8}+c_{9}+c_{10})(c_{2}+1)+\lVert
B\rVert_{2}^{2}c_{2}C_{0})\right],$ $\displaystyle
c_{18}:=\frac{1}{1-\gamma}\left[2\gamma(\lVert
B\rVert_{2}(c_{12}+c_{15}+c_{16})+\lVert B\rVert_{2}c_{2}c_{16})\right],$
$\displaystyle c_{20}:=\frac{1}{1-\gamma}\left[\gamma\lVert
B\rVert_{2}^{2}c_{2}^{2}(c_{8}+c_{9}+c_{10})+2\gamma\lVert
B\rVert_{2}c_{2}(c_{15}\right].$

###### Proof.

Recall that

$\displaystyle
r_{K,g}=\frac{1}{1-\gamma}\left((x^{*})^{\top}Qx^{*}+g^{\top}Rg+\gamma\left(g^{\top}B^{\top}P_{K}Bg+2g^{\top}B^{\top}q_{K,g}\right)\right).$

Then,

$\displaystyle r_{K^{\prime},g^{\prime}}-r_{K,g}$
$\displaystyle=\frac{1}{1-\gamma}((g^{\prime})^{\top}Rg^{\prime}+\gamma((g^{\prime})^{\top}B^{\top}P_{K^{\prime}}Bg^{\prime}+2(g^{\prime})^{\top}B^{\top}q_{K^{\prime},g^{\prime}}))$
$\displaystyle\quad-\frac{1}{1-\gamma}(g^{\top}Rg+\gamma(g^{\top}B^{\top}P_{K}Bg+2(g)^{\top}B^{\top}q_{K,g})).$

We omit the factor $\frac{1}{1-\gamma}$ for now. We first consider the term
$(g^{\prime})^{\top}Rg^{\prime}-g^{\top}Rg$. Note that

$\displaystyle\lVert(g^{\prime})^{\top}Rg^{\prime}-g^{\top}Rg\rVert$
$\displaystyle=\lVert(g^{\prime}-g)^{\top}g^{\prime}+g^{\top}(g^{\prime}-g))\rVert$
$\displaystyle\leq(c_{2}+1)\lVert g^{\prime}-g\rVert+c_{2}\lVert
g^{\prime}-g\rVert$ $\displaystyle=(2c_{2}+1)\lVert g^{\prime}-g\rVert.$

Next, we consider
$\gamma[((g^{\prime})^{\top}B^{\top}P_{K^{\prime}}Bg^{\prime}-g^{\top}B^{\top}P_{K}Bg]$.
Observe that

$\displaystyle((g^{\prime})^{\top}B^{\top}P_{K^{\prime}}Bg^{\prime}-g^{\top}B^{\top}P_{K}Bg$
$\displaystyle=(g^{\prime}-g)^{\top}B^{\top}P_{K^{\prime}}Bg^{\prime}+g^{\top}B^{\top}(P_{K^{\prime}}Bg^{\prime}-P_{K}Bg)$
$\displaystyle=(g^{\prime}-g)^{\top}B^{\top}P_{K^{\prime}}Bg^{\prime}+g^{\top}B^{\top}((P_{K^{\prime}}-P_{K})Bg^{\prime}+P_{K}B(g^{\prime}-g)).$

Then,

$\displaystyle\gamma\lVert((g^{\prime})^{\top}B^{\top}P_{K^{\prime}}Bg^{\prime}-g^{\top}B^{\top}P_{K}Bg\rVert$
$\displaystyle\leq\gamma\lVert B\rVert_{2}(C_{0}+c_{8}+c_{9}+c_{10})\lVert
B\rVert(c_{2}+1)\lVert g^{\prime}-g\rVert$ $\displaystyle\quad+\gamma(\lVert
B\rVert_{2}^{2}c_{2}^{2}\lVert P_{K^{\prime}}-P_{K}\rVert+\lVert
B\rVert_{2}^{2}c_{2}C_{0}\lVert g^{\prime}-g\rVert)$
$\displaystyle\leq\gamma\lVert B\rVert_{2}(C_{0}+c_{8}+c_{9}+c_{10})\lVert
B\rVert(c_{2}+1)\lVert g^{\prime}-g\rVert+\gamma\lVert
B\rVert_{2}^{2}c_{2}^{2}(c_{8}+c_{9}+c_{10})\lVert
K^{\prime}-K\rVert+\gamma\lVert B\rVert_{2}^{2}c_{2}C_{0}\lVert
g^{\prime}-g\rVert$ $\displaystyle=\gamma(\lVert
B\rVert_{2}^{2}(C_{0}+c_{8}+c_{9}+c_{10})(c_{2}+1)+\lVert
B\rVert_{2}^{2}c_{2}C_{0})\lVert g^{\prime}-g\rVert+\gamma\lVert
B\rVert_{2}^{2}c_{2}^{2}(c_{8}+c_{9}+c_{10})\lVert K^{\prime}-K\rVert.$

We finally turn to
$2\gamma((g^{\prime})^{\top}B^{\top}q_{K^{\prime},g^{\prime}})-2\gamma(g^{\top}B^{\top}q_{K,g})$.
We have

$\displaystyle\lVert(g^{\prime})^{\top}B^{\top}q_{K^{\prime},g^{\prime}}-g^{\top}B^{\top}q_{K,g}\rVert$
$\displaystyle=\lVert(g^{\prime}-g)^{\top}B^{\top}q_{K^{\prime}g^{\prime}}+g^{\top}B^{\top}(q_{K^{\prime},g^{\prime}}-q_{K,g})\rVert$
$\displaystyle\leq\lVert g^{\prime}-g\rVert\lVert B\rVert_{2}(\lVert
q_{K,g}\rVert+\lVert q_{K^{\prime},g^{\prime}}-q_{K,g}\rVert)+\lVert
g\rVert\lVert B\rVert_{2}\lVert q_{K^{\prime},g^{\prime}}-q_{K,g}\rVert$
$\displaystyle\leq\lVert g^{\prime}-g\rVert\lVert
B\rVert_{2}(c_{12}+c_{15}+c_{16})+\lVert B\rVert_{2}c_{2}(c_{15}\lVert
K^{\prime}-K\rVert+c_{16}\lVert g^{\prime}-g\rVert)$ $\displaystyle=(\lVert
B\rVert_{2}(c_{12}+c_{15}+c_{16})+\lVert B\rVert_{2}c_{2}c_{16})\lVert
g^{\prime}-g\rVert+\lVert B\rVert_{2}c_{2}(c_{15}\lVert K^{\prime}-K\rVert).$

Combining everything, we find that

$\displaystyle\lvert r_{K^{\prime},g^{\prime}}-r_{K,g}\rvert$
$\displaystyle\leq\frac{1}{1-\gamma}\left[\lVert(g^{\prime})^{\top}Rg^{\prime}-g^{\top}Rg\rVert+\gamma\lVert((g^{\prime})^{\top}B^{\top}P_{K^{\prime}}Bg^{\prime}-g^{\top}B^{\top}P_{K}Bg\rVert+2\gamma\lVert(g^{\prime})^{\top}B^{\top}q_{K^{\prime},g^{\prime}}-g^{\top}B^{\top}q_{K,g}\rVert\right]$
$\displaystyle\leq\frac{1}{1-\gamma}\left[2c_{2}+1+\gamma(\lVert
B\rVert_{2}^{2}(C_{0}+c_{8}+c_{9}+c_{10})(c_{2}+1)+\lVert
B\rVert_{2}^{2}c_{2}C_{0})\right]\lVert g^{\prime}-g\rVert$
$\displaystyle\quad+\frac{1}{1-\gamma}\left[2\gamma(\lVert
B\rVert_{2}(c_{12}+c_{15}+c_{16})+\lVert B\rVert_{2}c_{2}c_{16})\right]\lVert
g^{\prime}-g\rVert$ $\displaystyle\quad+\frac{1}{1-\gamma}\left[\gamma\lVert
B\rVert_{2}^{2}c_{2}^{2}(c_{8}+c_{9}+c_{10})+2\gamma\lVert
B\rVert_{2}c_{2}(c_{15}\right]\lVert K^{\prime}-K\rVert$

∎

We are now ready to state the local Lipschitz property of $J(K,g)$ and its
sample cost variant $J(K,g;x_{0}))$.

######  Proposition 7 (Local Lipschitz of sample and expected cost of
$J(K,g)$).

Suppose $\sqrt{\gamma}\rho(A+BK)<1$, and $J(K,g)<C_{0}$. Suppose also that
$\lVert K^{\prime}-K\rVert\leq c_{4},\lVert g^{\prime}-g\rVert\leq 1$. Then,

$\displaystyle J(K^{\prime},g^{\prime})-J(K,g)\leq
c_{21}\lVert(K^{\prime}-K,g^{\prime}-g)\rVert,$

where

$c_{21}=\frac{\max\\{\frac{n}{C_{n}}c_{11}+c_{19},c_{20}\\}}{\sqrt{2}}.$

Similarly, for the initial state $x_{0}$ of any sample,

$\displaystyle J(K^{\prime},g^{\prime};x_{0})-J(K,g;x_{0})\leq
c_{22}\lVert(K^{\prime}-K,g^{\prime}-g)\rVert,$

where

$c_{22}=\frac{\max\\{C_{n}(c_{8}+c_{9}+c_{10})+\sqrt{C_{n}}c_{15}+c_{19},c_{16}+c_{20}\\}}{\sqrt{2}}.$

###### Proof.

We first show the local Lipschitz property of the expected cost. Recall from
Lemma 14 that $\lvert C(K^{\prime})-C(K)\rvert\leq\frac{n}{C_{n}}c_{11}\lVert
K^{\prime}-K\rVert.$ Then, using the assumption that $\mathbb{E}[x_{0}]=0$ and
$\mathbb{E}[x_{0}]=I$, we find that

$\displaystyle\lvert J(K^{\prime},g^{\prime})-J(K,g)\rvert$
$\displaystyle=\lvert
C_{K^{\prime}}+r_{K^{\prime},g^{\prime}}-(C_{K}+r_{K,g})\rvert$
$\displaystyle\leq\lvert C(K^{\prime})-C(K)\rvert+\lvert
r_{K^{\prime},g^{\prime}}-r_{K,g}\rvert$
$\displaystyle\leq\frac{n}{C_{n}}c_{11}\lVert K^{\prime}-K\rVert+c_{19}\lVert
K^{\prime}-K\rVert+c_{20}\lVert g^{\prime}-g\rVert$
$\displaystyle=(\frac{n}{C_{n}}c_{11}+c_{19})\lVert
K^{\prime}-K\rVert+c_{20}\lVert g^{\prime}-g\rVert$

where we used Lemma 17 for the second last line. Then the result for the
expected cost holds by the observation that $(a+b)^{2}\leq 2(a^{2}+b^{2})$ for
any $0\leq a,b$.

We next examine the sample cost for a starting state $x_{0}$, which we can
write as $V_{K,g}(x_{0})$, using notation from Lemma 3. We have

$\displaystyle\lvert V_{K^{\prime},g^{\prime}}(x_{0})-V_{K,g}(x_{0})\rvert$
$\displaystyle=\lvert
x_{0}^{\top}(P_{K^{\prime}}-P_{K})x_{0}+2x_{0}^{\top}(q_{K^{\prime},g^{\prime}}-q_{K,g})+r_{K^{\prime},g^{\prime}}-r_{K,g}\rvert$
$\displaystyle\leq\lVert P_{K^{\prime}}-P_{K}\rVert_{2}\lVert
x_{0}\rVert^{2}+2\lVert x_{0}\rVert^{\top}\lVert
q_{K^{\prime},g^{\prime}}-q_{K,g}\rVert+\lvert
r_{K^{\prime},g^{\prime}}-r_{K,g}\rvert$ $\displaystyle\leq
C_{n}(c_{8}+c_{9}+c_{10})\lVert K^{\prime}-K\rVert+2\sqrt{C_{n}}(c_{15}\lVert
K^{\prime}-K\rVert+c_{16}\lVert g^{\prime}-g\rVert)+c_{19}\lVert
K^{\prime}-K\rVert+c_{20}\lVert g^{\prime}-g\rVert$
$\displaystyle=(C_{n}(c_{8}+c_{9}+c_{10})+\sqrt{C_{n}}c_{15}+c_{19})\lVert
K^{\prime}-K\rVert+(c_{16}+c_{20})\lVert g^{\prime}-g\rVert.$

∎

We are now ready to show that $J(K,g)$ is also locally Lipschitz smooth,
_i.e._ its gradient is Lipschitz. We first recall from Lemma 4 that the
gradients of $J$ with respect to $K$ and $g$ are the following:

$\displaystyle\nabla_{K}J=2C_{K}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}x_{t}^{\top}\right]+2d_{K,g}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{\top}\right],$
$\displaystyle\nabla_{g}J=2C_{K}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}\right]+2d_{K,g}\sum_{t=0}^{\infty}\gamma^{t},$

where

$C_{K}=RK+\gamma B^{\top}P_{K}(BK+A),\quad d_{K,g}=Rg+\gamma
B^{\top}P_{K}Bg+\gamma B^{\top}q_{K,g}.$

We first prove the following lemma, which will simplify the analysis of
$\mathbb{E}[\sum_{t=0}\gamma^{t}x_{t}x_{t}^{\top}].$ To this end we first
define a sequence $\\{y_{t}\\}$, $y_{0}=x_{0}$, that is obtained by following
the linear policy $u_{t}=Kx_{t}$ for the system
$(\sqrt{\gamma}A,\sqrt{\gamma}B)$ such that
$y_{t+1}=\sqrt{\gamma}A+\sqrt{\gamma}BKy_{t}$. Then, define

$\Sigma_{K}:=\mathbb{E}[\sum_{t=0}^{\infty}y_{t}y_{t}^{\top}].$

Then,

######  Lemma 18.

Recall the sequence $\\{y_{t}\\}$ and the corresponding state sum-of-
covariance matrix $\Sigma_{K}$ that we defined before this lemma. We have

$\displaystyle\mathbb{E}\left[\sum_{t}\gamma^{t}x_{t}x_{t}^{\top}\right]=\Sigma_{K}+(S_{K}^{\top}Bg)(Bg)^{\top}S_{K}.$

###### Proof.

Observe that

$\displaystyle\mathbb{E}[x_{t}x_{t}^{\top}]=\mathbb{E}[(x_{t}-\mathbb{E}[x_{t}])(x_{t}-\mathbb{E}[x_{t}])^{\top}]+\mathbb{E}[x_{t}]\mathbb{E}[x_{t}]^{\top}.$

Recall that $x_{t+1}=(A+BK)x_{t}+Bg,$ so
$\mathbb{E}[x_{t+1}]=(A+BK)^{t}\mathbb{E}[x_{t}]+Bg$. A direct calculation
shows that (since $\mathbb{E}[x_{0}]=0)$

$\displaystyle\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}x_{t}]$
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}(A+BK)^{t}Bg$
$\displaystyle=S_{K}^{\top}Bg.$

Next, via similar algebraic calculation, we find that

$\displaystyle\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}(x_{t}-\mathbb{E}[x_{t}])(x_{t}-\mathbb{E}[x_{t}])^{\top}]$
$\displaystyle=\mathbb{E}[\sum_{t=0}^{\infty}y_{t}y_{t}^{\top}],$

since for each summand the terms involving $g$ cancel out. ∎

Next we show that $\Sigma_{K^{\prime}}-\Sigma_{K}$ can also be bounded.

######  Lemma 19.

Suppose $\sqrt{\gamma}\rho(A+BK)<1$, and $J(K,g)<C_{0}$. Suppose also that
$\lVert K^{\prime}-K\rVert\leq c_{4}$. Then,

$\displaystyle\lVert\Sigma_{K^{\prime}}-\Sigma_{K}\rVert\leq c_{23}\lVert
K^{\prime}-K\rVert,$

where $c_{23}=8(\frac{C_{0}}{\sigma_{\min}(Q)})^{2}\sqrt{\gamma}\lVert
B\rVert_{2}.$ In addition, due to the assumption $\lVert
K^{\prime}-K\rVert\leq c_{4}$, we have

$\displaystyle\lVert\Sigma_{K^{\prime}}-\Sigma_{K}\rVert\leq 2c_{3}.$

###### Proof.

This follows from Lemma 16 of [7]. ∎

Next, we show that $C_{K,g}$ and $d_{K,g}$ are both bounded. Recall that
$E_{K,g}=\begin{bmatrix}C_{K,g}&d_{K,g}\end{bmatrix}$. From the lower bound in
Lemma 5, we see that (using our simplifying assumption that
$\mathbb{E}[x_{0}x_{0}^{\top}]=I$)

$\displaystyle\operatorname*{tr}(E_{K,g}^{\top}E_{K,g})\leq(J(K,g)-J(K^{*},g^{*}))\lVert
R+B^{\top}P_{K}B\rVert_{2}$ $\displaystyle\implies\lVert
C_{K,g}\rVert^{2}+\lVert d_{K,g}\rVert^{2}\leq C_{0}(\lVert R\rVert_{2}+\lVert
B\rVert_{2}^{2}C_{0}):=c_{24}^{2}.$

We next bound the quantities $C_{K^{\prime}}-C_{K}$ and
$d_{K^{\prime},g^{\prime}}-d_{K,g}$.

######  Lemma 20.

Suppose $\sqrt{\gamma}\rho(A+BK)<1$, and $J(K,g)<C_{0}$. Suppose also that
$\lVert K^{\prime}-K\rVert\leq c_{4},\lVert g^{\prime}-g\rVert\leq 1$. Then,

$\displaystyle\lVert C_{K^{\prime}}-C_{K}\rVert\leq c_{25}\lVert
K^{\prime}-K\rVert$ $\displaystyle\lVert
d_{K^{\prime},g^{\prime}}-d_{K,g}\rVert\leq c_{26}\lVert
K^{\prime}-K\rVert+c_{27}\lVert g^{\prime}-g\rVert,$

where

$\displaystyle c_{25}=\lVert R\rVert_{2}+\gamma\lVert
B\rVert_{2}[(c_{8}+c_{9}+c_{10})+\lVert B\rVert_{2}C_{0})]$ $\displaystyle
c_{26}=\gamma\lVert B\rVert_{2}^{2}(c_{2}+1)(c_{8}+c_{9}+c_{10})+\gamma\lVert
B\rVert_{2}c_{15}$ $\displaystyle c_{27}=\lVert R\rVert_{2}+\gamma\lVert
B\rVert_{2}^{2}C_{0}+\gamma\lVert B\rVert_{2}c_{16}.$

###### Proof.

We first handle $C_{K^{\prime}}-C_{K}$. We have

$\displaystyle\lVert C_{K^{\prime}}-C_{K}\rVert$ $\displaystyle\leq\lVert
RK^{\prime}+\gamma B^{\top}P_{K^{\prime}}(BK^{\prime}+A)-(RK+\gamma
B^{\top}P_{K}(BK+A))\rVert$ $\displaystyle\leq\lVert R\rVert_{2}\lVert
K^{\prime}-K\rVert+\gamma\lVert
B\rVert_{2}\lVert(P_{K^{\prime}}-P_{K})(A+BK^{\prime})+P_{K}B(K^{\prime}-K)\rVert$
$\displaystyle\leq\lVert R\rVert_{2}\lVert K^{\prime}-K\rVert+\gamma\lVert
B\rVert_{2}[(c_{8}+c_{9}+c_{10})\lVert K^{\prime}-K\rVert+\lVert
B\rVert_{2}C_{0}\lVert K^{\prime}-K\rVert]$ $\displaystyle=(\lVert
R\rVert_{2}+\gamma\lVert B\rVert_{2}[(c_{8}+c_{9}+c_{10})+\lVert
B\rVert_{2}C_{0})])\lVert K^{\prime}-K\rVert.$

Meanwhile,

$\displaystyle\lVert d_{K^{\prime},g^{\prime}}-d_{K,g}\rVert$
$\displaystyle=\lVert Rg^{\prime}+\gamma
B^{\top}P_{K^{\prime}}Bg^{\prime}+\gamma
B^{\top}q_{K^{\prime},g^{\prime}}-(Rg+\gamma B^{\top}P_{K}Bg+\gamma
B^{\top}q_{K,g})\rVert$ $\displaystyle\leq\lVert R\rVert_{2}\lVert
g^{\prime}-g\rVert+\gamma\lVert
B\rVert_{2}\lVert(P_{K^{\prime}}-P_{K})Bg^{\prime}+P_{K}B(g^{\prime}-g)\rVert+\gamma\lVert
B\rVert_{2}\lVert q_{K^{\prime},g^{\prime}}-q_{K,g}\rVert$
$\displaystyle\leq\lVert R\rVert_{2}\lVert g^{\prime}-g\rVert+\gamma\lVert
B\rVert_{2}(\lVert B\rVert_{2}(c_{2}+1)(c_{8}+c_{9}+c_{10})\lVert
K^{\prime}-K\rVert+C_{0}\lVert B\rVert_{2}\lVert g^{\prime}-g\rVert)$
$\displaystyle\quad+\gamma\lVert B\rVert_{2}(c_{15}\lVert
K^{\prime}-K\rVert+c_{16}\lVert g^{\prime}-g\rVert)$ $\displaystyle\leq(\lVert
R\rVert_{2}+\gamma\lVert B\rVert_{2}^{2}C_{0}+\gamma\lVert
B\rVert_{2}c_{16})\lVert g^{\prime}-g\rVert$ $\displaystyle\quad+(\gamma\lVert
B\rVert_{2}^{2}(c_{2}+1)(c_{8}+c_{9}+c_{10})+\gamma\lVert
B\rVert_{2}c_{15})\lVert K^{\prime}-K\rVert$

∎

We are finally ready to bound $\lVert\nabla J(K^{\prime},g^{\prime})-\nabla
J(K,g)\rVert$.

######  Proposition 8 ($J(K,g)$ is locally smooth).

Suppose $\sqrt{\gamma}\rho(A+BK)<1$, and $J(K,g)<C_{0}$. Suppose also that
$\lVert K^{\prime}-K\rVert\leq c_{4},\lVert g^{\prime}-g\rVert\leq 1$. Then,

$\displaystyle\lVert\nabla_{K}J(K^{\prime},g^{\prime})-\nabla_{K}J(K,g)\rVert\leq
c_{28}\lVert K^{\prime}-K\rVert+c_{29}\lVert K^{\prime}-K\rVert,$
$\displaystyle\lVert\nabla_{g}J(K^{\prime},g^{\prime})-\nabla_{g}J(K,g)\rVert\leq
c_{30}\lVert K^{\prime}-K\rVert+c_{31}\lVert K^{\prime}-K\rVert.$

Together, we find that

$\displaystyle\lVert\nabla J(K^{\prime},g^{\prime})-\nabla J(K,g)\rVert$
$\displaystyle\leq\lVert\nabla_{K}J(K^{\prime},g^{\prime})-\nabla_{K}J(K,g)\rVert+\lVert\nabla_{g}J(K^{\prime},g^{\prime})-\nabla_{g}J(K,g)\rVert$
$\displaystyle\leq\frac{\max\\{c_{28}+c_{30},c_{29}+c_{31}\\}}{\sqrt{2}}\lVert(K^{\prime}-K,g^{\prime}-g)\rVert,$

where

$\displaystyle c_{28}=2c_{25}[\lVert
B\rVert_{2}^{2}(c_{2}+1)^{2}(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})^{2}+(3c_{3})]+2c_{24}2\gamma c_{3}^{2}\lVert B\rVert_{2}(\lVert
B\rVert_{2}^{2}(c_{2}+1)^{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2}))$
$\displaystyle\quad+c_{2}\lVert B\rVert_{2}(2\gamma c_{3}^{2}\lVert
B\rVert_{2}+2c_{23}$ $\displaystyle\quad+2c_{26}\lVert
B\rVert_{2}(c_{2}+1)(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})+2c_{24}c_{2}\lVert B\rVert_{2}2\gamma c_{3}^{2}\lVert
B\rVert_{2}$ $\displaystyle c_{29}=2c_{24}c_{3}\lVert
B\rVert_{2}(c_{2}+1)\lVert B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})+2c_{2}\lVert B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})$ $\displaystyle\quad+2c_{27}\lVert
B\rVert_{2}(c_{2}+1)(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})+2c_{24}\lVert
B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})$ $\displaystyle
c_{30}=2c_{25}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})\lVert
B\rVert_{2}(c_{2}+1)+2c_{24}(2\gamma c_{3}^{2}\lVert B\rVert_{2})\lVert
B\rVert(c_{2}+1)+2c_{26}\frac{1}{1-\gamma},$ $\displaystyle
c_{31}=2c_{24}c_{3}\lVert B\rVert_{2}+2c_{27}\frac{1}{1-\gamma}.$

###### Proof.

We first tackle
$\lVert\nabla_{K}J(K^{\prime},g^{\prime})-\nabla_{K}J(K,g)\rVert$. Using Lemma
18, we have

$\displaystyle\nabla_{K}J(K,g)$
$\displaystyle=2C_{K}\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}x_{t}x_{t}^{\top}]+2d_{K,g}\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}x_{t}^{\top}]$
$\displaystyle=2C_{K}(S_{K}^{\top}Bg(Bg)^{\top}S_{K}+\Sigma_{K})+2d_{K,g}(Bg)^{\top}S_{K}.$

Thus

$\displaystyle\lVert\nabla_{K}J(K^{\prime},g^{\prime})-\nabla_{K}J(K,g)\rVert$
$\displaystyle\leq
2\lVert(C_{K^{\prime}}-C_{K})(S_{K^{\prime}}^{\top}Bg^{\prime}(Bg^{\prime})^{\top}S_{K^{\prime}}+\Sigma_{K^{\prime}})+C_{K}[S_{K^{\prime}}^{\top}Bg^{\prime}(Bg^{\prime})^{\top}S_{K^{\prime}}+\Sigma_{K^{\prime}}-(S_{K}^{\top}Bg(Bg)^{\top}S_{K}+\Sigma_{K}))]\rVert$
$\displaystyle\quad+2\lVert(d_{K^{\prime},g^{\prime}}-d_{K,g})(Bg^{\prime})^{\top}S_{K^{\prime}}+d_{K,g}((Bg^{\prime})^{\top}S_{K^{\prime}}-(Bg)^{\top}S_{K})\rVert$

We handle the first summand. Observe that

$\displaystyle
2\lVert(C_{K^{\prime}}-C_{K})(S_{K^{\prime}}^{\top}Bg^{\prime}(Bg^{\prime})^{\top}S_{K^{\prime}}+\Sigma_{K^{\prime}})+C_{K}[S_{K^{\prime}}^{\top}Bg^{\prime}(Bg^{\prime})^{\top}S_{K^{\prime}}+\Sigma_{K^{\prime}}-(S_{K}^{\top}Bg(Bg)^{\top}S_{K}+\Sigma_{K}))]\rVert$
$\displaystyle\leq 2\lVert C_{K^{\prime}}-C_{K}\rVert\lVert
S_{K^{\prime}}^{\top}Bg^{\prime}(Bg^{\prime})^{\top}S_{K^{\prime}}+\Sigma_{K^{\prime}}\rVert$
$\displaystyle\quad+2\lVert
C_{K}\rVert\lVert(S_{K^{\prime}}-S_{K})(Bg^{\prime}(g^{\prime})^{\top}B^{\top}S_{K^{\prime}})+S_{K}(Bg^{\prime}(g^{\prime})^{\top}B^{\top}S_{K^{\prime}}-Bg(g)^{\top}B^{\top}S_{K})+\Sigma_{K^{\prime}}-\Sigma_{K}\rVert$
$\displaystyle\leq 2c_{25}\lVert K^{\prime}-K\rVert[\lVert
B\rVert_{2}^{2}(c_{2}+1)^{2}(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})^{2}+(3c_{3})]$ $\displaystyle\quad+2c_{24}2\gamma c_{3}^{2}\lVert
B\rVert_{2}\lVert K^{\prime}-K\rVert(\lVert
B\rVert_{2}^{2}(c_{2}+1)^{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2}))$
$\displaystyle\quad+2c_{24}c_{3}\lVert
B\rVert_{2}\lVert(g^{\prime}-g)(g^{\prime})^{\top}B^{\top}S_{K^{\prime}}+g((g^{\prime})^{\top}B^{\top}S_{K^{\prime}}-g^{\top}B^{\top}S_{K})\rVert$
$\displaystyle\quad+2c_{23}\lVert K^{\prime}-K\rVert$ $\displaystyle\leq
2c_{25}\lVert K^{\prime}-K\rVert[\lVert
B\rVert_{2}^{2}(c_{2}+1)^{2}(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})^{2}+(3c_{3})]$ $\displaystyle\quad+2c_{24}2\gamma c_{3}^{2}\lVert
B\rVert_{2}\lVert K^{\prime}-K\rVert(\lVert
B\rVert_{2}^{2}(c_{2}+1)^{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2}))$
$\displaystyle\quad+2c_{24}c_{3}(\lVert B\rVert_{2}\lVert
g^{\prime}-g\rVert(c_{2}+1)\lVert B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})$ $\displaystyle\quad+2c_{2}\lVert g^{\prime}-g\rVert\lVert
B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})+c_{2}\lVert
B\rVert_{2}(2\gamma c_{3}^{2}\lVert B\rVert_{2}\lVert K^{\prime}-K\rVert))$
$\displaystyle\quad+2c_{23}\lVert K^{\prime}-K\rVert$

For the next summand, observe that

$\displaystyle
2\lVert(d_{K^{\prime},g^{\prime}}-d_{K,g})(Bg^{\prime})^{\top}S_{K^{\prime}}+d_{K,g}((Bg^{\prime})^{\top}S_{K^{\prime}}-(Bg)^{\top}S_{K})\rVert$
$\displaystyle\leq 2(c_{26}\lVert K^{\prime}-K\rVert+c_{27}\lVert
g^{\prime}-g\rVert)\lVert B\rVert_{2}(c_{2}+1)(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})$ $\displaystyle\quad+2c_{24}\lVert g^{\prime}-g\rVert\lVert
B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})+2c_{24}c_{2}\lVert
B\rVert_{2}2\gamma c_{3}^{2}\lVert B\rVert_{2}\lVert K^{\prime}-K\rVert.$

Therefore,

$\displaystyle\lVert\nabla_{K}J(K^{\prime},g^{\prime})-\nabla_{K}J(K,g)\rVert\leq
c_{28}\lVert K^{\prime}-K\rVert+c_{29}\lVert g^{\prime}-g\rVert,$

where

$\displaystyle c_{28}=2c_{25}[\lVert
B\rVert_{2}^{2}(c_{2}+1)^{2}(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})^{2}+(3c_{3})]+2c_{24}2\gamma c_{3}^{2}\lVert B\rVert_{2}(\lVert
B\rVert_{2}^{2}(c_{2}+1)^{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2}))$
$\displaystyle\quad+c_{2}\lVert B\rVert_{2}(2\gamma c_{3}^{2}\lVert
B\rVert_{2}+2c_{23}$ $\displaystyle\quad+2c_{26}\lVert
B\rVert_{2}(c_{2}+1)(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})+2c_{24}c_{2}\lVert B\rVert_{2}2\gamma c_{3}^{2}\lVert
B\rVert_{2}$ $\displaystyle c_{29}=2c_{24}c_{3}\lVert
B\rVert_{2}(c_{2}+1)\lVert B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})+2c_{2}\lVert B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})$ $\displaystyle\quad+2c_{27}\lVert
B\rVert_{2}(c_{2}+1)(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})+2c_{24}\lVert
B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2}).$

Next, observe that

$\displaystyle\lVert\nabla_{g}J(K^{\prime}g^{\prime})-\nabla_{g}J(K,g)\rVert$
$\displaystyle=\lVert
2C_{K^{\prime}}S_{K^{\prime}}^{\top}Bg^{\prime}+2d_{K^{\prime},g^{\prime}}\sum_{t}\gamma^{t}-2C_{K}S_{K}^{\top}Bg+2d_{K,g}\sum_{t}\gamma^{t}\rVert$
$\displaystyle\leq 2\lVert C_{K^{\prime}}-C_{K}\rVert\lVert
S_{K^{\prime}}\rVert_{2}\lVert B\rVert_{2}(c_{2}+1)+2\lVert
C_{K}\rVert\lVert(S_{K^{\prime}}^{\top}-S_{K}^{\top})Bg^{\prime}+S_{K}^{\top}B(g^{\prime}-g)\rVert$
$\displaystyle\quad+2\lVert
d_{K^{\prime},g^{\prime}}-d_{K,g}\rVert\frac{1}{1-\gamma}$ $\displaystyle\leq
2c_{25}\lVert K^{\prime}-K\rVert(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2})\lVert B\rVert_{2}(c_{2}+1)+2c_{24}(2\gamma c_{3}^{2}\lVert
B\rVert_{2})\lVert K^{\prime}-K\rVert\lVert
B\rVert(c_{2}+1)+2c_{24}c_{3}\lVert B\rVert_{2}\lVert g^{\prime}-g\rVert$
$\displaystyle\quad+2(c_{26}\lVert K^{\prime}-K\rVert+c_{27}\lVert
g^{\prime}-g\rVert)\frac{1}{1-\gamma}$
$\displaystyle=\left(2c_{25}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})\lVert
B\rVert_{2}(c_{2}+1)+2c_{24}(2\gamma c_{3}^{2}\lVert B\rVert_{2})\lVert
B\rVert(c_{2}+1)+2c_{26}\frac{1}{1-\gamma}\right)\lVert K^{\prime}-K\rVert$
$\displaystyle\quad+\left(2c_{24}c_{3}\lVert
B\rVert_{2}+2c_{27}\frac{1}{1-\gamma}\right)\lVert g^{\prime}-g\rVert$

∎

###### Proof of Proposition 2.

The local Lipschitz and smoothness results in Proposition 2 are a consequence
of Proposition 7 and Proposition 2. ∎

##### Constants used in local Lipschitz and smoothness arguments.

Below is a list of constants used in the local Lipschitz and smoothness
argument, where $C_{0}>0$ is an upper bound on $J(K,g)$.

  1. 1.

$c_{1}=\frac{\sqrt{(C_{0}-C(K^{*}))(\rho(R)+\lVert
B\rVert^{2}C_{0})}}{\sigma_{\min}(R)}+\frac{\lVert B\rVert C_{0}\lVert
A\rVert}{\sigma_{\min}(R)}$

  2. 2.

$c_{2}=\sqrt{\frac{C_{0}}{\sigma_{\min}(R)}}$

  3. 3.

$c_{3}=\frac{2C_{0}}{\sigma_{\min}(Q)}$

  4. 4.

$c_{4}=\min\left\\{\frac{\sigma_{\min}(Q)}{4C_{0}\lVert\sqrt{\gamma}B\rVert(\lVert\sqrt{\gamma}A+\sqrt{\gamma}BK\rVert+1)},1\right\\}$

  5. 5.

$c_{5}=\frac{\sigma_{\min}(Q)}{4\gamma\lVert B\rVert C_{0}}$.

  6. 6.

$c_{6}=\frac{1}{\sigma_{\min}(R)}\left(\sqrt{(\lVert R\rVert_{2}+\lVert
B\rVert_{2}^{2}C_{0})(C_{0}-C^{*})}+\lVert B\rVert_{2}\lVert
A\rVert_{2}C_{0}\right)$

  7. 7.

$c_{7}=\max\left\\{\frac{C_{0}}{\sigma_{\min}(Q)}\sqrt{(\lVert
R\rVert_{2}+\lVert B\rVert_{2}^{2}C_{0})(C_{0}-C^{*})},c_{6}\right\\}$

  8. 8.

$c_{8}=4\left(\frac{C_{0}}{\sigma_{\min}(Q)}\right)^{2}\lVert
Q\rVert_{2}\lVert B\rVert_{2}(\lVert A\rVert_{2}+\lVert B\rVert_{2}c_{7}+1)$

  9. 9.

$c_{9}=8\left(\frac{C_{0}}{\sigma_{\min}(Q)}\right)^{2}(c_{7}^{2})\lVert
R\rVert_{2}\lVert B\rVert_{2}(\lVert A\rVert_{2}+\lVert B\rVert_{2}c_{7}+1)$

  10. 10.

$c_{10}=2\left(\frac{C_{0}}{\sigma_{\min}(Q)}\right)^{2}(c_{7}+1)\lVert
R\rVert_{2}$

  11. 11.

$c_{11}=C_{n}(c_{8}+c_{9}+c_{10})$

  12. 12.

$c_{12}=c_{3}\left(c_{1}c_{2}\lVert R\rVert+2\sqrt{\gamma}C_{0}\lVert
B\rVert_{2}c_{2}\right)$

  13. 13.

$c_{13}=2\gamma c_{3}\lVert B\rVert_{2}(c_{1}+1)\lVert
R\rVert_{2}(c_{2}+1)+(c_{2}+1)\lVert R\rVert_{2}$

  14. 14.

$c_{14}=2\gamma^{3/2}(C_{0}+c_{8}+c_{9}+c_{10})\lVert
B\rVert_{2}^{2}(c_{2}+1)+c_{3}(\gamma\lVert
B\rVert_{2}^{2}(C_{0}+c_{8}+c_{9}+c_{10})\lVert
B\rVert_{2}(c_{2}+1)+\sqrt{\gamma}\lVert
B\rVert_{2}(c_{2}+1)(c_{8}+c_{9}+c_{10}))$

  15. 15.

$c_{15}=2\gamma c_{3}\lVert B\rVert_{2}\lVert Qx^{*}\rVert+c_{13}+c_{14}$

  16. 16.

$c_{16}=2c_{1}c_{3}\lVert R\rVert_{2}+c_{3}C_{0}\lVert B\rVert_{2}$.

  17. 17.

$c_{17}=\frac{1}{1-\gamma}\left[2c_{2}+1+\gamma(\lVert
B\rVert_{2}^{2}(C_{0}+c_{8}+c_{9}+c_{10})(c_{2}+1)+\lVert
B\rVert_{2}^{2}c_{2}C_{0})\right]$

  18. 18.

$c_{18}=\frac{1}{1-\gamma}\left[2\gamma(\lVert
B\rVert_{2}(c_{12}+c_{15}+c_{16})+\lVert B\rVert_{2}c_{2}c_{16})\right]$

  19. 19.

$c_{19}=c_{17}+c_{18}$

  20. 20.

$c_{20}=\frac{1}{1-\gamma}\left[\gamma\lVert
B\rVert_{2}^{2}c_{2}^{2}(c_{8}+c_{9}+c_{10})+2\gamma\lVert
B\rVert_{2}c_{2}(c_{15}\right]$

  21. 21.

$c_{21}=\frac{\max\\{\frac{n}{C_{n}}c_{11}+c_{19},c_{20}\\}}{\sqrt{2}}$

  22. 22.

$c_{22}=\frac{\max\\{C_{n}(c_{8}+c_{9}+c_{10})+\sqrt{C_{n}}c_{15}+c_{19},c_{16}+c_{20}\\}}{\sqrt{2}}$

  23. 23.

$c_{23}=8(\frac{C_{0}}{\sigma_{\min}(Q)})^{2}\sqrt{\gamma}\lVert B\rVert_{2}$

  24. 24.

$c_{24}=\sqrt{C_{0}(\lVert R\rVert_{2}+\lVert B\rVert_{2}^{2}C_{0})}$

  25. 25.

$c_{25}=\lVert R\rVert_{2}+\gamma\lVert
B\rVert_{2}[(c_{8}+c_{9}+c_{10})+\lVert B\rVert_{2}C_{0})]$

  26. 26.

$c_{26}=\gamma\lVert B\rVert_{2}^{2}(c_{2}+1)(c_{8}+c_{9}+c_{10})+\gamma\lVert
B\rVert_{2}c_{15}$

  27. 27.

$c_{27}=\lVert R\rVert_{2}+\gamma\lVert B\rVert_{2}^{2}C_{0}+\gamma\lVert
B\rVert_{2}c_{16}$

  28. 28.

$c_{28}=2c_{25}[\lVert B\rVert_{2}^{2}(c_{2}+1)^{2}(c_{3}+2\gamma
c_{3}^{2}\lVert B\rVert_{2})^{2}+(3c_{3})]+2c_{24}2\gamma c_{3}^{2}\lVert
B\rVert_{2}(\lVert B\rVert_{2}^{2}(c_{2}+1)^{2}(c_{3}+2\gamma c_{3}^{2}\lVert
B\rVert_{2}))+c_{2}\lVert B\rVert_{2}(2\gamma c_{3}^{2}\lVert
B\rVert_{2}+2c_{23}+2c_{26}\lVert B\rVert_{2}(c_{2}+1)(c_{3}+2\gamma
c_{3}^{2}\lVert B\rVert_{2})+2c_{24}c_{2}\lVert B\rVert_{2}2\gamma
c_{3}^{2}\lVert B\rVert_{2}$

  29. 29.

$c_{29}=2c_{24}c_{3}\lVert B\rVert_{2}(c_{2}+1)\lVert
B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})+2c_{2}\lVert
B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})+2c_{27}\lVert
B\rVert_{2}(c_{2}+1)(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})+2c_{24}\lVert
B\rVert_{2}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})$

  30. 30.

$c_{30}=2c_{25}(c_{3}+2\gamma c_{3}^{2}\lVert B\rVert_{2})\lVert
B\rVert_{2}(c_{2}+1)+2c_{24}(2\gamma c_{3}^{2}\lVert B\rVert_{2})\lVert
B\rVert(c_{2}+1)+2c_{26}\frac{1}{1-\gamma}$

  31. 31.

$c_{31}=2c_{24}c_{3}\lVert B\rVert_{2}+2c_{27}\frac{1}{1-\gamma}$

##  Appendix C Algorithms

We restate here Algorithm 1 from the main paper, as well as Algorithm 2
(benchmark algorithm) which we omitted. In particular, we consider the more
general setting where one-point or two-point estimator can be used.

1 Given: iteration number $T\geq 1$, communication interval $H\in\mathbb{N}$,
initial stable $K_{0}$, initial $g_{0}^{i}$ for each $i\in[m]$, step size
$\eta>0$, and smoothing radius $r>0$

2 for  _$\mbox{epoch }e\in\\{0,\dots,\frac{T}{H}-1\\}$_ do

3 Set $K_{eH}^{i}\leftarrow K_{eH}$ for each $i\in[m]$

4 for  _$\mbox{iteration }t=eH,eH+1,\dots,(e+1)H-1$_ do

5 for  _$\mbox{(simultaneously) each agent }i\in[m]$_ do

6 Sample $(x_{0})_{t}^{i}\sim\mathcal{D}$,
$u_{t}^{i}\sim\mathrm{Unif}(\mathbb{S}^{n\cdot k+k-1})$

7 Set the zeroth-order estimator $z_{t}^{i}$ as follows :
$\displaystyle(z_{t}^{i})\leftarrow\begin{cases}z_{r}^{1}((K_{t}^{i},g_{t}^{i}),u_{t}^{i},(x_{0})_{t}^{i})&\mbox{
if in one-point setting,}\\\
z_{r}^{2}((K_{t}^{i},g_{t}^{i}),u_{t}^{i},(x_{0})_{t}^{i})&\mbox{ if in two-
point setting.}\end{cases}$

8

9 end for

10

11 end for

12 Set
$K_{(e+1)H}\leftarrow\frac{1}{m}\sum_{i=1}^{m}K_{(e+1)H}^{i}\quad(\mbox{model
averaging of $K$ at end of epoch }e)$

13

14 end for

return _$K_{T},\ g_{T}^{i}\ \forall i\in[m]$_

Algorithm 2 Federated LQR Learning algorithm

######  Remark 1.

The one-point and two-point zeroth order estimators are defined as follows for
the LQR problem with random initialization:

$\displaystyle
z_{r}^{1}((K_{t}^{i},g_{t}^{i}),u_{t}^{i},(x_{0})_{t}^{i}):=\frac{d}{r}\hat{J}^{i}((K_{t}^{i},g_{t}^{i})+ru_{t}^{i};(x_{0})_{t}^{i})u_{t}^{i},$
$\displaystyle
z_{r}^{2}((K_{t}^{i},g_{t}^{i}),u_{t}^{i},(x_{0})_{t}^{i}):=\frac{d}{2r}\left(J^{i}((K_{t}^{i},g_{t}^{i})+ru_{t}^{i};(x_{0})_{t}^{i})-J^{i}(((K_{t}^{i},g_{t}^{i})-ru_{t}^{i};(x_{0})_{t}^{i})\right)u_{t}^{i},$

where $d=n\cdot k+k$ (i.e. dimension of $K$ plus dimension of $g$). In
addition, we note that
$\hat{J}^{i}(K,g):=\min\\{J^{i}(K,g),10J_{0}^{i}(K_{0},g_{0}^{i})\\}$ (where
$J_{0}^{i}:=J^{i}(K_{0},g_{0}^{i})$), which incurs a bias in the gradient
estimation procedure but simplifies the maximum bound on $z_{r}^{1}$ 444This
truncation technique was also used in [14].

The next algorithm, Algorithm 3, is the benchmark algorithm which we will
compare our federated algorithm against. We note that it basically runs $m$
independent zeroth-order gradient descent independently.

1 Given: iteration number $T\geq 1$, communication interval $H\in\mathbb{N}$,
initial stable $K_{0}$, initial $g_{0}^{i}$ for each $i\in[m]$, step size
$\eta>0$, and smoothing radius $r>0$

2 for  _$\mbox{iteration }t=0,1,\dots,T-1$_ do

3 for  _$\mbox{(simultaneously) each agent }i\in[m]$_ do

4 Sample $(x_{0})_{t}^{i}\sim\mathcal{D}$,
$u_{t}^{i}\sim\mathrm{Unif}(\mathbb{S}^{n\cdot k-1})$

5 Set the zeroth-order estimator $z_{t}^{i}$ as follows:
$\displaystyle(z_{t}^{i})\leftarrow\begin{cases}z_{r}^{1}((K_{t}^{i},g_{t}^{i}),u_{t}^{i},(x_{0})_{t}^{i})&\mbox{
if in one-point setting,}\\\
z_{r}^{2}((K_{t}^{i},g_{t}^{i}),u_{t}^{i},(x_{0})_{t}^{i})&\mbox{ if in two-
point setting.}\end{cases}$

6 Update $K_{t+1}^{i}\leftarrow K_{t}^{i}-\eta(z_{t}^{i})_{K}$, $\quad
t\leftarrow t+1$

7 Update $g_{t+1}^{i}\leftarrow g_{t}^{i}-\eta(z_{t}^{i})_{g}$

8 end for

9

10 end for

11

return _$K_{T}^{i},\ g_{T}^{i}\ \forall i\in[m]$_

Algorithm 3 Benchmark distributed LQR algorithm

##  Appendix D Analysis of main results

We first state the following terms which will be used in the proofs to follow.
Consider the terms

$\displaystyle Z_{\infty}^{i}:=\max\\{\left\lVert
z_{t}^{i}(\cdot)\right\rVert\\},\quad
Z_{\infty}:=\max_{i\in[m]}Z_{\infty}^{i}$ $\displaystyle
Z_{2,K}:=\max_{t}\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}^{t}\left\lVert(z_{t}^{i})_{K}\right\rVert^{2},\quad
Z_{2,G}=\max_{t}\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}^{t}\left\lVert(z_{t}^{i})_{g^{i}}\right\rVert^{2},$

which collectively form bounds on the maximum size and variance of the zeroth-
order gradient update. We next define the stability region $\mathcal{G}_{0}$
and $\mathcal{G}_{0}^{\prime}$ which we show in the appendix that the iterates
of Algorithm 1 and the benchmark algorithm respectively stay within. Let

$\displaystyle\mathcal{G}_{0}:=\left\\{(K,G):\bar{J}(K,G)\leq
10\bar{J}(K_{0},G_{0})\right\\},$
$\displaystyle\mathcal{G}_{0}^{\prime}:=\left\\{\\{K^{i},g^{i}\\}_{i\in[m]}:\frac{1}{m}\sum_{i=1}^{m}J^{i}(K^{i},g^{i})\leq
10\frac{1}{m}\sum_{i=1}^{m}J^{i}(K_{0}^{i},g_{0}^{i})\right\\}.$

Next, by Proposition 2, note that there exists a local radius $\rho>0$, local
Lipschitz parameter $\lambda>0$ and local smoothness parameter $L>0$ such that
the following holds.

  1. 1.

If $(K,G)\in\mathcal{G}_{0}$, for any $i\in[m]$, and
$\lVert(K^{\prime},(g^{i})^{\prime})-(K,g^{i})\rVert\leq\rho,$ then

$\displaystyle\lVert\nabla J^{i}(K^{\prime},(g^{i})^{\prime})-\nabla
J^{i}(K,g^{i})\rVert\leq
L\lVert(K^{\prime},(g^{i})^{\prime})-(K,g^{i})\rVert,$ $\displaystyle\lVert
J^{i}(K^{\prime},(g^{i})^{\prime})-J^{i}(K,g^{i})\rVert\leq\lambda\lVert(K^{\prime},(g^{i})^{\prime})-(K,g^{i})\rVert.$

  2. 2.

If $(\\{K_{i},g^{i}\\}_{i=1}^{m})\in\mathcal{G}_{0}^{\prime}$, for any
$i\in[m]$, and
$\lVert((K^{i})^{\prime},(g^{i})^{\prime})-(K^{i},g^{i})\rVert\leq\rho$,

$\lVert\nabla J^{i}((K^{i})^{\prime},(g^{i})^{\prime})-\nabla
J^{i}(K^{i},g^{i})\rVert\leq
L\lVert((K^{i})^{\prime},(g^{i})^{\prime})-(K^{i},g^{i})\rVert.$

  3. 3.

If $(K,G)\in\mathcal{G}_{0}$, and
$\left\lVert(K^{\prime},G^{\prime})-(K,G)\right\rVert\leq\rho$, then

$\lVert\nabla\bar{J}(K^{\prime},G^{\prime})-\nabla\bar{J}(K,G)\rVert\leq
L\lVert(K^{\prime},G^{\prime})-(K,G)\rVert.$

###  D.1 Theorem 1

In this subsection, we provide analysis and proof of convergence for Theorem
1, which provides analysis for Algorithm 1.

At a high level, proving Theorem 1 requires us to show the following two
things.

  1. 1.

Showing an expected decrease in cumulative cost every epoch — we will do so by
designing a suitable virtual sequence that matches the true iterates at the
start of each epoch, and show a per-iteration decrease in cost for this
virtual sequence.

  2. 2.

Showing that the iterates remain stable throughout the algorithm with large
probability — we will do so by a martingale argument.

Let $\mathcal{I}_{H}=\\{H,2H,\dots,T\\}$ denote the iterations where model
averaging over $K$ is performed. Observe then that the iterates of $K$ evolve
in the following way.

$K_{t+1}^{i}=\begin{cases}K_{t}^{i}-\eta(z_{t}^{i})_{K}&\mbox{if
}t\notin\mathcal{I}_{H}\\\ \frac{1}{m}\sum_{i=1}^{m}K_{t}^{i}&\mbox{if
}t\in\mathcal{I}_{H}.\end{cases}$

To facilitate analysis, consider the following virtual sequence

$\displaystyle\bar{K}_{t}=\frac{1}{m}\sum_{i=1}^{m}K_{t}^{i},\quad\bar{K}_{0}=K_{0}.$

We see that the virtual sequence of $K$ and the true sequence of $G$ evolve as
follows:

$\displaystyle(\bar{K}_{t+1},G_{t+1})=(\bar{K}_{t},G_{t})-\eta\frac{1}{m}\sum_{i=1}^{m}\nabla
J^{i}(K_{t}^{i},g_{t}^{i}).$

We will work extensively with this joint sequence. We first define a stability
region of the algorithm, which we will show the joint sequence
$(\bar{K}_{t},G_{t})$ stays in throughout the algorithm. Let

$\displaystyle\mathcal{G}_{0}:=\left\\{(K,G):\bar{J}(K,G)\leq
10\bar{J}(K_{0},G_{0})\right\\}.$

Then, by Proposition 2, there exists $\rho>0$ such that the following holds.

  1. 1.

If $(K,G)\in\mathcal{G}_{0}$, for any $i\in[m]$, if
$\lVert(K^{\prime},g^{i})-(K,g^{i})\rVert\leq\rho$, then $\lVert\nabla
J^{i}(K^{\prime},g^{i})-\nabla J^{i}(K,g^{i})\rVert\leq
L\lVert(K^{\prime},g^{i})-(K,g^{i})\rVert$

  2. 2.

If $(K,G)\in\mathcal{G}_{0}$, if
$\left\lVert(K^{\prime},G^{\prime})-(K,G)\right\rVert\leq\rho$, then
$\lVert\nabla\bar{J}(K^{\prime},G^{\prime})-\nabla\bar{J}(K,G)\rVert\leq
L\lVert(K^{\prime},G^{\prime})-(K,G)\rVert$.

We first show a per-iteration change in optimality gap for the joint sequence,
which will be essential in the convergence proofs. For convenience, define the
optimality gap

$\displaystyle\Delta_{t}=\bar{J}(\bar{K}_{t},G_{t})-\bar{J}^{*}.$

######  Lemma 21 (Per-iteration change in optimality gap).

Suppose $(\bar{K}_{t},G_{t})\in\mathcal{G}^{0}$. Then, if we choose step-size
$\eta>0$, smoothing radius $r>0$ and communication interval $H\geq 1$ such
that

$\displaystyle\eta\leq\min\left\\{\frac{\rho}{2HZ_{\infty}},\frac{L}{8}\right\\},\quad
r\leq\min\\{\sqrt{\frac{\epsilon}{720L\mu}},\rho\\},$

the optimality gap satisfies the following bound

$\displaystyle\mathbb{E}^{t}[\Delta_{t+1}]\leq(1-\frac{\eta}{4\mu})\Delta_{t}+\frac{\eta^{2}L}{2}\left(\frac{Z_{2,K}+Z_{2,G}}{m}+6\eta
LH^{2}Z_{\infty,K}^{2}\right)+\frac{\eta}{120\mu}\epsilon.$

###### Proof.

By choosing $\eta\leq\frac{\rho}{2Z_{\infty}}$, we find that

$\displaystyle\left\lVert(\bar{K}_{t+1},G_{t+1})-(\bar{K}_{t},G_{t})\right\rVert^{2}$
$\displaystyle=\left\lVert\bar{K}_{t}-\eta\frac{1}{m}\sum_{i=1}^{m}(z_{t}^{i})_{K}(K_{t}^{i},g_{t}^{i})-\bar{K}_{t}\right\rVert^{2}+\sum_{i=1}^{m}\left\lVert
g_{t}^{i}-\frac{\eta}{m}(z_{t}^{i})_{g^{i}}(K_{t}^{i},g_{t}^{i})-g_{t}^{i}\right\rVert^{2}$
$\displaystyle\leq\eta^{2}(2Z_{\infty}^{2})\leq\rho^{2}.$

Since $(\bar{K}_{t},G_{t})\in\mathcal{G}_{0}$, by local smoothness, and taking
conditional expectation on $\mathcal{F}_{t}$ (which we denote by
$\mathbb{E}^{t}$), it follows that

$\displaystyle\mathbb{E}^{t}\bar{J}(\bar{K}_{t+1},G_{t+1})$
$\displaystyle\leq\bar{J}(\bar{K}_{t},G_{t})-\eta\mathbb{E}^{t}\left\langle\nabla_{K}\bar{J}(\bar{K}_{t},G_{t}),\frac{1}{m}\sum_{i=1}^{m}(z_{t}^{i})_{K}(K_{t}^{i},g_{t}^{i})\right\rangle+\frac{L}{2}\mathbb{E}^{t}\left\lVert\eta\frac{1}{m}\sum_{i=1}^{m}z_{t}^{i}(K_{t}^{i},g_{t}^{i})\right\rVert^{2}$
$\displaystyle\quad-\frac{\eta}{m^{2}}\sum_{i=1}^{m}\mathbb{E}^{t}\left\langle\nabla_{g^{i}}J^{i}(\bar{K}_{t},g_{t}^{i}),(z_{t}^{i})_{g^{i}}(K_{t}^{i},g_{t}^{i})\right\rangle+\frac{L}{2}\frac{1}{m^{2}}\sum_{i=1}^{m}\mathbb{E}^{t}\left\lVert\eta(z_{t}^{i})_{g^{i}}(K_{t}^{i},g_{t}^{i})\right\rVert^{2}$
$\displaystyle=\bar{J}(\bar{K}_{t},G_{t})-\eta\left\langle\nabla_{K}\bar{J}(\bar{K}_{t},G_{t}),\frac{1}{m}\sum_{i=1}^{m}\nabla_{K}J^{i}_{r}(K_{t}^{i},g_{t}^{i})\right\rangle+\frac{L\eta^{2}}{2}\mathbb{E}^{t}\left\lVert\frac{1}{m}\sum_{i=1}^{m}(z_{t}^{i})_{K}(K_{t}^{i},g_{t}^{i})\right\rVert^{2}$
$\displaystyle\quad-\frac{\eta}{m^{2}}\sum_{i=1}^{m}\left\langle\nabla_{g^{i}}J^{i}(\bar{K}_{t},g_{t}^{i}),\nabla_{g^{i}}J^{i}_{r}(K_{t}^{i},g_{t}^{i})\right\rangle+\frac{L\eta^{2}}{2}\frac{1}{m^{2}}\sum_{i=1}^{m}\mathbb{E}^{t}\left\lVert(z_{t}^{i})_{g^{i}}(K_{t}^{i},g_{t}^{i})\right\rVert^{2}$

We first handle the term
$-\eta\left\langle\nabla_{K}\bar{J}(\bar{K}_{t},G_{t}),\frac{1}{m}\sum_{i=1}^{m}\nabla_{K}J^{i}_{r}(K_{t}^{i},g_{t}^{i})\right\rangle$.
Observe that