# Sample Complexity of the Linear Quadratic Regulator: A Reinforcement
Learning Lens

Amirreza Neshaei Moghaddam  Department of Electrical and Computer Engineering
University of California at Los Angeles, Los Angeles<EMAIL_ADDRESS>,
Alex Olshevsky  Department of Electrical and Computer Engineering
Boston University<EMAIL_ADDRESS>and  Bahman Gharesifard  Department of
Electrical and Computer Engineering
University of California, Los Angeles<EMAIL_ADDRESS>
###### Abstract.

We provide the first known algorithm that provably achieves
$\varepsilon$-optimality within $\widetilde{\mathcal{O}}(1/\varepsilon)$
function evaluations for the discounted discrete-time LQR problem with unknown
parameters, without relying on two-point gradient estimates. These estimates
are known to be unrealistic in many settings, as they depend on using the
exact same initialization, which is to be selected randomly, for two different
policies. Our results substantially improve upon the existing literature
outside the realm of two-point gradient estimates, which either leads to
$\widetilde{\mathcal{O}}(1/\varepsilon^{2})$ rates or heavily relies on
stability assumptions.

##  1\. Introduction

The Linear-Quadratic Regulator (LQR) has been used as a benchmark in optimal
control theory since the sixties, see [15]. The key distinguishing property of
LQR problems is that the optimal controller is linear and can be fully
characterized by the celebrated Riccati equation [3]. Naturally, with the
recent increase in interest in model-free and data-driven methods, the study
of LQR problems has resurfaced in the literature in scenarios where the model
parameters are unknown and either need to be estimated, or model-free
strategies need to be used. Even though such settings fall within the realm of
adaptive control, the majority of classical studies addressing this issue have
concentrated on system identification or examining asymptotic outcomes [13, 6,
7, 5, 4].

Recently, the problem has been examined from a machine learning standpoint in
both online and offline contexts. In online settings, least-square estimators
have been demonstrated to achieve sublinear regret. This area has seen
extensive research focusing on the details of these estimations [1, 8, 18, 2,
20]. This paper focuses on the offline setting and builds on a sequence of
breakthrough results through a reinforcement learning lens, starting with
[10]. By establishing a gradient domination/Polyak-Lojasiewicz property, the
results of [10] first demonstrate that exact gradient descent, in the model-
based case, converges to the global optimal solution, despite the non-convex
landscape of the LQR problem under study. Using this and in the model-free
settings, gradient estimations are derived from samples of the cost function
value, leading to policy gradient methods. For the undiscounted discrete-time
LQR under the random initialization setting, global convergence guarantees are
provided using so-called one-point gradient estimates. As also explicitly
pointed out in later work [17], the convergence rate for obtaining an
$\varepsilon$-optimal policy established in [10] is only of the order
$\widetilde{\mathcal{O}}(1/\varepsilon^{4})$ in zero-order evaluations. Note
that by zero-order methods, we mean a setup where gradients are not available
and can only be approximated using samples of the function value. The two most
common such methods in the LQR problem are the one-point and two-point
estimates where the former is obtained from a single function evaluation and
the latter from two different such evaluations111To elaborate further, we
provide the formulation of these two methods here. The one-point estimate at a
policy $K\in{\mathbb{R}}^{m\times n}$ is computed as
$\displaystyle\textsl{g}_{r}^{1}(K):={\mathcal{C}}_{\textup{init}}(K+rU;x_{0})\frac{m.n}{r}U,$
for some smoothing radius $r\in{\mathbb{R}}$ and a random matrix
$U\in{\mathbb{R}}^{m\times n}$ drawn uniformly over matrices with unit
Frobenius norm. Likewise, the two-point estimate at a policy
$K\in{\mathbb{R}}^{m\times n}$ is given by
$\displaystyle\textsl{g}_{r}^{2}(K):=\left[{\mathcal{C}}_{\textup{init}}(K+rU;x_{0})-{\mathcal{C}}_{\textup{init}}(K-rU;x_{0})\right]\frac{m.n}{2r}U,$
which requires cost evaluations of implementing two different policies $K+rU$
and $K-rU$ with respect to the same initial state $x_{0}$..

The next significant development related to our work is presented in [17],
which considers the discounted discrete-time LQR and employs zero-order
methods for gradient estimation. For the essential case of one-point gradient
estimation, an enhanced analysis is proposed. This analysis does not rely on
stability assumptions yet improves the convergence rate reported in [10] from
$\widetilde{\mathcal{O}}(1/\varepsilon^{4})$ to
$\widetilde{\mathcal{O}}(1/\varepsilon^{2})$. Remarkably, with a two-point
gradient estimate, $\varepsilon$-optimality can be achieved using only
$\widetilde{\mathcal{O}}(1/\varepsilon)$ function evaluations. Similar
findings are reported in [19], which are somewhat restrictive in terms of
scaling of probability bounds with respect to dimensions. The substantial
improvement in [17] stems from the application of sharp probabilistic
estimates on stability regions using martingale techniques, a method we also
heavily rely on. It should be noted that in both mentioned works, a constant
learning rate is employed for the policy update. Interestingly, it is not
difficult to observe that there is no advantage in using time-varying learning
rates when the technique developed in [17] is applied directly.

It is worth pointing out the literature related to the discrete-time LQR
problem with time-average cost. For instance, [25] employs an actor-critic
approach to achieve a sample complexity of
$\widetilde{\mathcal{O}}(1/\varepsilon^{5})$. Similarly, using actor-critic
methods, [26] demonstrates that a sample complexity of
$\widetilde{\mathcal{O}}(1/\varepsilon)$ is achievable, assuming almost sure
stability and boundedness of the policy size throughout the algorithm.
However, the assumption of boundedness may not always be realistic, and more
so is the assumption on stability, considering the inherently noisy dynamics.
For example, this issue is echoed in the recent work [11], which presupposes
the boundedness of policies at every iteration.

As part of our contributions, and somewhat inspired by REINFORCE [24, 23], we
propose a different gradient estimate scheme, which relies on a new take on
using policy gradient for gradient estimation by appropriately sampling the
deterministic policies. We are able to achieve high-probability upper bounds
on our gradient estimations using moment concentration inequalities. Coupled
with the adoption of time-varying learning rates, our methodology enables us
to reach a $\widetilde{\mathcal{O}}(1/\varepsilon)$ convergence rate,
circumventing the need for two-point gradient estimations.

##  2\. Problem statement

We start with a few mathematical notations that will be used throughout. For
arbitrary matrix $M\in{\mathbb{R}}^{m\times n}$, we use $\lVert M\rVert$,
$\lVert M\rVert_{F}$, and $\sigma_{\mathrm{min}}(M)$ to denote the 2-norm,
Frobenius norm, and the minimum singular value of $M$ respectively. In
addition, for a square matrix $\tilde{M}\in{\mathbb{R}}^{n\times n}$,
$\operatorname{tr}(\tilde{M})$ represents the trace of $\tilde{M}$, and
$\mathcal{K}(\tilde{M})$ denotes the Kreiss constant of $\tilde{M}$:

(1)
$\mathcal{K}(\tilde{M}):=\sup_{\begin{subarray}{c}|z|>1,z\in\mathbb{C}\end{subarray}}(|z|-1)\lVert(zI-\tilde{M})^{-1}\rVert.$

We also use $\langle M_{1},M_{2}\rangle:=\operatorname{tr}(M_{1}^{\top}M_{2})$
to denote the inner product of the matrices
$M_{1},M_{2}\in{\mathbb{R}}^{m\times n}$.

Let us now define the problem under study. We consider the discrete-time
infinite-horizon discounted LQR problem

(2) $\min{\mathbb{E}}\left[\sum_{t\geq
0}\gamma^{t}(x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t})\right]\quad\text{s.t.}\;\>x_{t+1}=Ax_{t}+Bu_{t}+z_{t},$

where $x_{t}\in{\mathbb{R}}^{n}$ is the system state at time $t$, initialized,
deterministically or randomly at $x_{0}$, $u_{t}\in{\mathbb{R}}^{m}$ is the
control input at time $t$, $z_{t}\in{\mathbb{R}}^{n}$ is the additive noise of
the system at time $t$, $A\in{\mathbb{R}}^{n\times n}$ and
$B\in{\mathbb{R}}^{n\times m}$ are the system matrices, and
$Q\in{\mathbb{R}}^{n\times n}$ and $R\in{\mathbb{R}}^{m\times m}$ are
positive-definite matrices that parameterize the quadratic costs. In most of
what follows, we assume that the pair $(A,B)$ is controllable.

As noted above, randomness is introduced in two different ways in the above
problem formulation: through the initialization or as an added disturbance to
the dynamics. This has led to two separate scenarios considered in the
literature:

  * •

Random initialization: where it is assumed that the additive noise $z_{t}$ is
zero for all $t\geq 0$, and that the initial state $x_{0}$ is randomly chosen
from an initial distribution ${\mathcal{D}}_{0}$. Given the initial state
$x_{0}$, we let ${\mathcal{C}}_{\text{init},\gamma}(K;x_{0})$ be the random
variable representing the cost of implementing the linear policy
$K\in{\mathbb{R}}^{m\times n}$, i.e., choosing $u_{t}=-Kx_{t}$ for $t\geq 0$,
from the initial state $x_{0}$:

(3)
${\mathcal{C}}_{\textup{init}}(K;x_{0}):=\sum_{t=0}^{\infty}\gamma^{t}(x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}),$

where $0<\gamma\leq 1$ is the discount factor, and the dynamics is given by
(2) with $z_{t}=0$. That is, in this case the trajectories satisfy the
dynamics

(4) $\displaystyle x_{t+1}=$ $\displaystyle Ax_{t}+Bu_{t},$ (5) $\displaystyle
u_{t}=$ $\displaystyle-Kx_{t}.$

Naturally, the objective is to minimize the population cost defined as

(6)
${\mathcal{C}}_{\textup{init}}(K):={\mathbb{E}}_{x_{0}\sim{\mathcal{D}}_{0}}[{\mathcal{C}}_{\textup{init}}(K;x_{0})]$

over choices of the policy $K$.

  * •

Noisy dynamics: where it is assumed $z_{t}$ is drawn i.i.d. for each $t$ from
a distribution ${\mathcal{D}}_{\text{add}}$, and that the initial state
$x_{0}$ is set deterministically to zero. Given a sequence of random variables
$\mathcal{Z}=\\{z_{t}\\}_{t\geq 0}$, we let
${\mathcal{C}}_{\textup{dyn}}(K;\mathcal{Z})$ be the random variable
representing the cost of implementing the linear policy $K$ on a system where
the additive noise is drawn from $\mathcal{Z}$, i.e.,

(7)
${\mathcal{C}}_{\textup{dyn}}(K;\mathcal{Z}):=\sum_{t=0}^{\infty}\gamma^{t}(x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}),$

where we have set $x_{0}=0$, the dynamics is given by (2) with $u_{t}=-Kx_{t}$
for each $t\geq 0$, and $0<\gamma<1$ is the discount factor. In contrast to
the random initialization setting, the discount factor in this setting obeys
$\gamma<1$ to ensure that the costs sum to something finite. Once again, the
objective is to minimize the population cost

(8)
${\mathcal{C}}_{\textup{dyn}}(K):={\mathbb{E}}_{\mathcal{Z}\sim{\mathcal{D}}_{\text{add}}^{\mathbb{N}}}[{\mathcal{C}}_{\textup{dyn}}(K;\mathcal{Z})].$

By classical results in optimal control theory, see e.g., [12, 15], the
optimal controller in both cases is linear and can be expressed as
$u_{t}=-K^{*}x_{t}$ where $t\geq 0$ and $K^{*}\in\mathbb{R}^{m\times n}$ is
the controller gain, and can be explicitly computed. When the system matrices
are known, which is not the case in this paper, the policy $K^{*}$ can be
derived as follows

(9) $K^{*}=\gamma(R+\gamma B^{\top}PB)^{-1}B^{\top}PA,$

where $P$ denotes the unique positive definite solution to the discounted
discrete-time algebraic Riccati equation [3]:

(10) $P=\gamma A^{\top}PA-\gamma^{2}A^{\top}PB(R+\gamma
B^{\top}PB)^{-1}B^{\top}PA+Q.$

Throughout this paper, we closely follow the notation and terminology that is
introduced in the seminal work [17]. To start, for a random variable
$v\sim{\mathcal{D}}$ where
${\mathcal{D}}\in\left\\{{\mathcal{D}}_{0},{\mathcal{D}}_{\text{add}}\right\\}$,
we assume that

(11) ${\mathbb{E}}[v]=0,\quad{\mathbb{E}}[vv^{\top}]=I,\ \text{and}\ \lVert
v\rVert^{2}\leq C_{m}\ \ \text{a.s.}$

where as per usual, “a.s.” refers to almost surely. The assumption on the
covariance being identity is without loss of generality, see [17]. Moreover,
it is noteworthy to mention that using the definition (3) with the
trajectories following (5), the cost for the random initialization setting can
be rewritten as

(12) ${\mathcal{C}}_{\textup{init}}(K;x_{0})=x_{0}^{\top}P_{K}x_{0},$

where $P_{K}$ is the symmetric positive semi-definite solution to the fixed
point equation:

(13) $P_{K}=Q+K^{\top}RK+\gamma(A-BK)^{\top}P_{K}(A-BK).$

Consequently, it also holds that

(14) $\displaystyle{\mathcal{C}}_{\textup{init}}(K)$
$\displaystyle={\mathbb{E}}_{x_{0}\sim{\mathcal{D}}_{0}}[{\mathcal{C}}_{\textup{init}}(K;x_{0})]$
(15)
$\displaystyle={\mathbb{E}}_{x_{0}\sim{\mathcal{D}}_{0}}[x_{0}^{\top}P_{K}x_{0}]$
(16)
$\displaystyle={\mathbb{E}}_{x_{0}\sim{\mathcal{D}}_{0}}[\operatorname{tr}(P_{K}x_{0}x_{0}^{\top})]$
(17)
$\displaystyle=\operatorname{tr}(P_{K}{\mathbb{E}}_{x_{0}\sim{\mathcal{D}}_{0}}[x_{0}x_{0}^{\top}])$
(18) $\displaystyle\overset{\mathrm{(i)}}{=}\operatorname{tr}(P_{K}),$

where (i) follows from assumption (11) on the randomness. Although this
formulation is stated for the cost under the random initialization setting, it
turns out that the two costs are essentially equivalent when the respective
systems are driven by noise with the same first two moments, in the sense that
is shown in Lemma 2.4 to follow. For this reason, we focus on the random
initialization scenario henceforth.

Let us now state the problem that we consider throughout this paper. We recall
here that we assume that the pair $(A,B)$ is controllable, however, _unknown_.
A policy $K$ is said to stabilize the system $(A,B)$ if we have
$\rho(A-BK)<1$. Note that by the controllability assumption, there exists some
policy $K$ satisfying the condition $\rho(A-BK)<1$. Furthermore, we assume
access to  _some_ stable policy $K_{0}$; this is a mild assumption that can be
satisfied in a variety of ways; we refer the reader to [10, 9]. We use $K_{0}$
to initialize our algorithms, which we shortly introduce.

With this in mind, the main objective of this paper is to find an
$\varepsilon$-optimal policy $\hat{K}$, i.e., one satisfying

${\mathcal{C}}_{\textup{init}}(\hat{K})-{\mathcal{C}}_{\textup{init}}(K^{*})\leq\varepsilon,$

where $K^{*}$ is an optimal policy. The proposed scheme in the literature
crucially involves forming form an estimation of the gradient of the cost
function (3), which then is used for a gradient update with an appropriate
learning rate. In accordance with this, we also propose an algorithm here,
displayed as Algorithm 1, where we use an estimate inspired by the REINFORCE
method [24, 23] with a time-varying learning rate to achieve
$\varepsilon$-optimality.

###  2.1. Regularity properties

We introduce some notations related to the regularity properties of the cost
functions; these will play a crucial role in some of our bounds; the next few
results are borrowed from [17].

######  Lemma 2.1 (LQR Cost is locally Lipschitz).

[17, Lemma 4] Given any linear policy $K$ with finite cost, there exist
positive scalars $(\lambda_{K},\widetilde{\lambda_{K}},\zeta_{K})$, depending
on the function value ${\mathcal{C}}_{\textup{init}}(K)$, such that for all
policies $K^{\prime}$ satisfying ${\lVert
K^{\prime}-K\rVert_{F}\leq\zeta_{K}}$, and for all initial states $x_{0}$, we
have

(19a)
$\displaystyle|{\mathcal{C}}_{\textup{init}}(K^{\prime})-{\mathcal{C}}_{\textup{init}}(K)|\leq$
$\displaystyle\lambda_{K}\lVert K^{\prime}-K\rVert_{F},\text{ and}$ (19b)
$\displaystyle|{\mathcal{C}}_{\textup{init}}(K^{\prime};x_{0})-{\mathcal{C}}_{\textup{init}}(K;x_{0})|\leq$
$\displaystyle\widetilde{\lambda_{K}}\lVert K^{\prime}-K\rVert_{F}.$

######  Lemma 2.2 (LQR Cost has locally Lipschitz Gradients).

[17, Lemma 5] Given any linear policy $K$ with finite cost, there exist
positive scalars $(\beta_{K},\phi_{K})$, depending on the function value
${\mathcal{C}}_{\textup{init}}(K)$, such that for all policies $K^{\prime}$
satisfying $\lVert K^{\prime}-K\rVert_{F}\leq\beta_{K}$, we have

(20)
$\displaystyle\lVert\nabla{\mathcal{C}}_{\textup{init}}(K^{\prime})-\nabla{\mathcal{C}}_{\textup{init}}(K)\rVert_{F}\leq\phi_{K}\lVert
K^{\prime}-K\rVert_{F}.$

######  Lemma 2.3 (LQR satisfies PL).

[17, Lemma 6] There exists a universal constant $\mu_{\text{lqr}}>0$ such that
for all stable policies $K$, we have

(21)
$\displaystyle\lVert\nabla{\mathcal{C}}_{\textup{init}}(K)\rVert_{F}^{2}\geq\mu_{\text{lqr}}\left({\mathcal{C}}_{\textup{init}}(K)-{\mathcal{C}}_{\textup{init}}(K^{*})\right),$

where $K^{*}$ is a global minimizer of the cost function
${\mathcal{C}}_{\textup{init}}$.

For the sake of exposition, these properties are stated here without
specifying the various smoothness and PL constants. The explicit expressions
for
$\\{\lambda_{K},\widetilde{\lambda_{K}},\phi_{K},\beta_{K},\zeta_{K},\mu_{\text{lqr}}\\}$
in terms of the parameters of the LQR problem are provided in [17, Appendix
A]. Remark 2.1 to follow will provide further elaboration on these parameters
as well.

######  Lemma 2.4 (Equivalence of population costs up to scaling).

[17, Lemma 7] For all policies $K$, we have

$\displaystyle{\mathcal{C}}_{\textup{dyn}}(K)=\frac{\gamma}{1-\gamma}{\mathcal{C}}_{\textup{init}}(K).$

This result shows that the noisy dynamics and random initialization population
costs behave identically when their respective sources of randomness have the
same first two moments. Therefore, we focus on the random initialization cost
from now on and remind the reader that
${\mathcal{C}}(K):={\mathcal{C}}_{\textup{init}}(K)$ for ease of notation.

We define the set

(22) $\mathcal{G}^{\text{lqr}}:=\\{K\ |\
{\mathcal{C}}(K)-{\mathcal{C}}(K^{*})\leq 10{\mathcal{C}}(K_{0})\\}.$

Since ${\mathcal{C}}$ is $(\zeta_{K},\lambda_{K})$ locally Lipschitz and
$(\beta_{K},\phi_{K})$ locally smooth, both properties hold simultaneously
within a Frobenius norm radius $\omega_{K}:=\min\\{\beta_{K},\zeta_{K}\\}$ of
a point $K\in\mathcal{G}^{\text{lqr}}$. We define the quantities

$\phi_{\text{lqr}}:=\sup_{x\in\mathcal{G}^{\text{lqr}}}\phi_{K},\qquad\lambda_{\text{lqr}}:=\sup_{K\in\mathcal{G}^{\text{lqr}}}\lambda_{K},\quad\text{and}\quad\omega_{\text{lqr}}:=\inf_{K\in\mathcal{G}^{\text{lqr}}}\omega_{K}.$

It is noteworthy to mention that these values are non-zero and finite, and
their explicit formulation is provided in [17, Appendix A], see Remark 2.1 to
follow for further clarification.

Observe that by the definition of these quantities, one can immediately show
that for any $K\in{\mathcal{G}}^{\text{lqr}}$ and
$K^{\prime}\in{\mathbb{R}}^{m\times n}$ such that $\lVert
K^{\prime}-K\rVert_{F}\leq\omega_{\text{lqr}}$, we have that

$\displaystyle|{\mathcal{C}}(K^{\prime})-{\mathcal{C}}(K)|\leq$
$\displaystyle\lambda_{\text{lqr}}\lVert K^{\prime}-K\rVert_{F},\text{ and}$
$\displaystyle\lVert\nabla{\mathcal{C}}(K^{\prime})-\nabla{\mathcal{C}}(K)\rVert_{F}\leq$
$\displaystyle\phi_{\text{lqr}}\lVert K^{\prime}-K\rVert_{F}.$

######  Remark 2.1.

We now describe how to specify the set of parameters
$\\{\lambda_{K},\widetilde{\lambda_{K}},\phi_{K},\beta_{K},\zeta_{K},\mu_{\text{lqr}}\\}$
in our setting. We start by recalling that a set of parameters
$\\{c_{K_{0}},c_{K_{1}},\dotsc,c_{K_{9}}\\}$ is defined in [17, Appendix A],
which notably depend on ${\mathcal{C}}(K)$. Subsequently, by replacing said
${\mathcal{C}}(K)$ with
$\sup_{K\in{\mathcal{G}}^{\text{lqr}}}{\mathcal{C}}(K)$, they obtain a set of
constants
$\\{\widetilde{c_{K_{0}}},\widetilde{c_{K_{1}}},\dotsc,\widetilde{c_{K_{9}}}\\}$
which are independent of $K$. For ease of access for the reader, we point out
that

(23)
$\omega_{\text{lqr}}=\widetilde{c_{K_{9}}},\quad\phi_{\text{lqr}}=\widetilde{c_{K_{7}}},\quad\text{and}\quad\lambda_{\text{lqr}}=\widetilde{c_{K_{8}}}.$

Moreover, it holds that $\max\\{\lVert
K\rVert,\|\nabla{\mathcal{C}}(K)\|_{F}\\}\leq\widetilde{c_{K_{1}}}$ for any
$K\in{\mathcal{G}}^{\text{lqr}}$, see [17, Appendix A] and [10, Lemma 22].
Note that the only required modification in the values of
$\widetilde{c_{K_{0}}},\widetilde{c_{K_{1}}},\dotsc,\widetilde{c_{K_{9}}}$ for
our case is having $10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*})$ as
$\sup_{K\in{\mathcal{G}}^{\text{lqr}}}{\mathcal{C}}(K)$ instead of [17]’s
$10{\mathcal{C}}(K_{0})-9{\mathcal{C}}(K^{*})$, due to the difference in our
definition of ${\mathcal{G}}^{\text{lqr}}$ in (22). $\diamond$

We now provide an informal statement of our main result, which shows that our
proposed algorithm obtains an $\varepsilon$-optimal policy after
$\widetilde{\mathcal{O}}(1/\varepsilon)$ iterations. As we outline precisely
later, this algorithm forms an estimate $\widehat{\nabla C}(K_{t})$ of the
gradient at a given time $t$ and updates the policy $K_{t}$ with a time-
varying learning rate $\alpha_{t}$.

######  Theorem 2.1.

(Informal Statement of Our Main Result): If the step-size is chosen as
$\alpha_{t}=C\frac{1}{t+N}$ with $N$ “large enough”, i.e.,
$N\sim\mathcal{O}\left((\log{\frac{1}{\delta}})^{3/2}\right)$ for any chosen
$\delta$, and $C$ being a known constant, then after
$T=\mathcal{O}\left(N/\varepsilon\right)$ iterations, provided the discount
factor is close enough to $1$, we have that

(24) ${\mathcal{C}}(K_{T})-{\mathcal{C}}(K^{*})\leq\varepsilon$

with a probability of at least $4/5-\delta T$. In particular, choosing
$\delta$ proportional to $1/T$, we attain
${\mathcal{C}}(K_{T})-{\mathcal{C}}(K^{*})$ with a constant probability with a
sample complexity of $\widetilde{\mathcal{O}}\left(1/\varepsilon\right)$.

Let us first point out that this result substantially improves the ones in the
literature by achieving a $\widetilde{\mathcal{O}}(1/\varepsilon)$ rate
without any additional assumptions. The best previous result achieves a
convergence rate of $\widetilde{\mathcal{O}}(1/\varepsilon^{2})$ [17] in this
setting. Indeed, $\widetilde{\mathcal{O}}(1/\varepsilon)$ rates were only
available using so-called two-point estimates which re-use randomness (e.g.,
require being able to initialize the system at a given $x_{0}$). As a result,
one must have perfect control over a simulator to use such estimates; one
cannot implement them for systems which need to learn in the real world, for
example. In contrast, our result only uses gradient estimates with a single
zero-order evaluation at each step.

We now begin the process of collecting the essentials needed to articulate our
theorem precisely and to prove this result, beginning with a fresh examination
of the policy gradient that we employ for gradient estimation.

##  3\. Policy Gradient

Most formulations of the policy gradient require probabilistic policies; in
contrast, as can be seen in (5), we have used a deterministic policy given by
$u_{t}=-Kx_{t}$. To remedy, we utilize the control input $u_{\hat{t}}$, to be
defined shortly, where $\hat{t}$ is sampled at random from the distribution
$\mu_{\gamma}(t):=(1-\gamma)\gamma^{t}$, where $t\in\\{0,1,2,\cdots\\}$.
Keeping this in mind, we now compute

(25)
$\widehat{\nabla{\mathcal{C}}}(K):=\frac{1}{1-\gamma}Q^{K}(x_{\hat{t}},u_{\hat{t}})\nabla_{K}\log\pi_{K}(u_{\hat{t}}|x_{\hat{t}}),$

where the control input $u_{\hat{t}}$ is randomly chosen from the Gaussian
distribution $\mathcal{N}(-Kx_{\hat{t}},\sigma^{2}I_{m})$ for some $\sigma>0$
only for the selected iteration $\hat{t}$, and
$x_{\hat{t}}=(A-BK)^{\hat{t}}x_{0}$ with $x_{0}\sim{\mathcal{D}}$ as before.
Note that

(26)
${\mathbb{E}}_{\hat{t}\sim\mu_{\gamma}}\left[\widehat{\nabla{\mathcal{C}}}(K)\right]=\sum_{t=0}^{\infty}\gamma^{t}Q^{K}(x_{t},u_{t})\nabla_{K}\log\pi_{K}(u_{t}|x_{t}),$

where

(27)
$\pi_{K}(u_{t}|x_{t})=\frac{1}{\sqrt{(2\pi)^{m}(\sigma^{2})^{m}}}e^{-\frac{(u_{t}+Kx_{t})^{\top}(u_{t}+Kx_{t})}{2\sigma^{2}}},$

and

(28) $\displaystyle Q^{K}(x_{t},u_{t})$
$\displaystyle:=x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}+\gamma{\mathcal{C}}_{\textup{init}}(K;Ax_{t}+Bu_{t})$
(29)
$\displaystyle\overset{\mathrm{(i)}}{=}x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}+\gamma(Ax_{t}+Bu_{t})^{\top}P_{k}(Ax_{t}+Bu_{t}),$

where (i) is on account of (12). Note that we can also rewrite
$u_{\hat{t}}\sim\mathcal{N}(-Kx_{\hat{t}},\sigma^{2}I_{m})$ as

(30) $u_{\hat{t}}=-Kx_{\hat{t}}+\sigma\eta_{\hat{t}},$

where $\eta_{\hat{t}}\sim\mathcal{N}(0,I_{m})$. Moreover, we have the
following lemma to provide an alternative way of representing (25).

######  Lemma 3.1.

The gradient estimate in (25) can be modified to get

(31)
$\widehat{\nabla{\mathcal{C}}}(K)=-\frac{1}{\sigma(1-\gamma)}Q^{K}(x_{\hat{t}},-Kx_{\hat{t}}+\sigma\eta_{\hat{t}})\eta_{\hat{t}}x_{\hat{t}}^{\top}.$

###### Proof.

Following (25), we have that

(32) $\displaystyle\widehat{\nabla{\mathcal{C}}}(K)=$
$\displaystyle\frac{1}{1-\gamma}Q^{K}(x_{\hat{t}},u_{\hat{t}})\nabla_{K}\log\pi_{K}(u_{\hat{t}}|x_{\hat{t}})$
(33) $\displaystyle\overset{\mathrm{(i)}}{=}$
$\displaystyle\frac{1}{1-\gamma}Q^{K}(x_{\hat{t}},u_{\hat{t}})\nabla_{K}\left(-\frac{(u_{\hat{t}}+Kx_{\hat{t}})^{\top}(u_{\hat{t}}+Kx_{\hat{t}})}{2\sigma^{2}}\right)$
(34) $\displaystyle=$
$\displaystyle\frac{1}{1-\gamma}Q^{K}(x_{\hat{t}},u_{\hat{t}})\nabla_{K}\left(-\frac{u_{\hat{t}}^{\top}u_{\hat{t}}+2u_{\hat{t}}^{\top}Kx_{\hat{t}}+x_{\hat{t}}^{\top}K^{\top}Kx_{\hat{t}}}{2\sigma^{2}}\right)$
(35) $\displaystyle=$
$\displaystyle\frac{1}{1-\gamma}Q^{K}(x_{\hat{t}},u_{\hat{t}})\nabla_{K}\left(-\frac{\operatorname{tr}\left(2x_{\hat{t}}u_{\hat{t}}^{\top}K\right)+\operatorname{tr}\left(x_{\hat{t}}x_{\hat{t}}^{\top}K^{\top}K\right)}{2\sigma^{2}}\right),$

where (i) follows from (27). Now note that

(36)
$\nabla_{K}\operatorname{tr}\left(2x_{\hat{t}}u_{\hat{t}}^{\top}K\right)=\nabla_{K}\operatorname{tr}\left(\left(2u_{\hat{t}}x_{\hat{t}}^{\top}\right)^{\top}K\right)=\nabla_{K}\left\langle
2u_{\hat{t}}x_{\hat{t}}^{\top},K\right\rangle=2u_{\hat{t}}x_{\hat{t}}^{\top},$

and

(37)
$\displaystyle\nabla_{K}\operatorname{tr}\left(x_{\hat{t}}x_{\hat{t}}^{\top}K^{\top}K\right)=$
$\displaystyle\nabla_{K_{1}}\operatorname{tr}\left(x_{\hat{t}}x_{\hat{t}}^{\top}K^{\top}K_{1}\right)+\nabla_{K_{2}}\operatorname{tr}\left(x_{\hat{t}}x_{\hat{t}}^{\top}K_{2}^{\top}K\right)$
(38) $\displaystyle=$
$\displaystyle\nabla_{K_{1}}\operatorname{tr}\left(\left(Kx_{\hat{t}}x_{\hat{t}}^{\top}\right)^{\top}K_{1}\right)+\nabla_{K_{2}}\operatorname{tr}\left(K_{2}^{\top}\left(Kx_{\hat{t}}x_{\hat{t}}^{\top}\right)\right)$
(39) $\displaystyle=$ $\displaystyle\nabla_{K_{1}}\left\langle
Kx_{\hat{t}}x_{\hat{t}}^{\top},K_{1}\right\rangle+\nabla_{K_{2}}\left\langle
Kx_{\hat{t}}x_{\hat{t}}^{\top},K_{2}\right\rangle$ (40) $\displaystyle=$
$\displaystyle 2Kx_{\hat{t}}x_{\hat{t}}^{\top}.$

As a result, combining (36) and (40) with (35) yields

$\displaystyle\widehat{\nabla{\mathcal{C}}}(K)=$
$\displaystyle\frac{1}{1-\gamma}Q^{K}(x_{\hat{t}},u_{\hat{t}})\left(-\frac{1}{2\sigma^{2}}\left(2(Kx_{\hat{t}}x_{\hat{t}}^{\top}+u_{\hat{t}}x_{\hat{t}}^{\top})\right)\right)$
$\displaystyle=$
$\displaystyle\frac{1}{1-\gamma}Q^{K}(x_{\hat{t}},u_{\hat{t}})\left(-\frac{(u_{\hat{t}}+Kx_{\hat{t}})}{\sigma^{2}}x_{\hat{t}}^{\top}\right)$
$\displaystyle\overset{\mathrm{(i)}}{=}$
$\displaystyle-\frac{1}{\sigma(1-\gamma)}Q^{K}(x_{\hat{t}},-Kx_{\hat{t}}+\sigma\eta_{\hat{t}})\eta_{\hat{t}}x_{\hat{t}}^{\top},$

where (i) follows from (30). This finishes the proof. ∎

Taking the alternative formulation of our gradient estimate provided in Lemma
3.1 into consideration, we introduce the algorithm

Algorithm 1 LQR with Policy Gradient

1:Given iteration number $T\geq 1$, initial policy
$K_{0}\in{\mathbb{R}}^{m\times n}$, noise parameter $\sigma$, and step size
$\alpha_{t}>0$

2:for $t\in\\{0,1,\ldots,T-1\\}$ do

3: Sample $x_{0}\sim{\mathcal{D}}$, $\hat{t}\sim\mu_{\gamma}$, and
$\eta_{\hat{t}}\sim\mathcal{N}(0,I_{m})$

4: Simulate $K_{t}$ for $\hat{t}$ steps starting from $x_{0}$ and observe
$x_{\hat{t}}$.

5: $u_{\hat{t}}\leftarrow-K_{t}x_{\hat{t}}+\sigma\eta_{\hat{t}}$

6:
$\widehat{\nabla{\mathcal{C}}}(K_{t})\leftarrow-\frac{1}{\sigma(1-\gamma)}\eta_{\hat{t}}x_{\hat{t}}^{\top}Q^{K_{t}}(x_{\hat{t}},u_{\hat{t}})$

7: $K_{t+1}\leftarrow K_{t}-\alpha_{t}\widehat{\nabla{\mathcal{C}}}(K_{t})$
return $K_{T}$

Before we state the next result, note that one can compute

(41) $\nabla{\mathcal{C}}(K)=2((R+\gamma B^{\top}P_{K}B)K-\gamma
B^{\top}P_{K}A){\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}x_{t}^{\top}\right];$

a proof can be found in [10] for the undiscounted case, where $\gamma=1$, and
in [17] for the discounted case. The following proposition plays a key role in
our constructions.

######  Proposition 3.1.

Suppose $u_{\hat{t}}\sim\mathcal{N}(-Kx_{\hat{t}},\sigma^{2}I_{m})$ as before.
Then for any given $K$,

(42) ${\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K)]=\nabla{\mathcal{C}}(K).$

###### Proof.

Following (31),

(43) $\displaystyle{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K)]$ (44)
$\displaystyle=\ $
$\displaystyle{\mathbb{E}}_{\hat{t}\sim\mu_{\gamma}}\left[{\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[{\mathbb{E}}_{\eta_{\hat{t}}\sim\mathcal{N}(0,I_{m})}\left[\widehat{\nabla{\mathcal{C}}}(K)\big{|}\hat{t},x_{0}\right]\bigg{|}\hat{t}\right]\right]$
(45) $\displaystyle\overset{\mathrm{(i)}}{=}\ $
$\displaystyle{\mathbb{E}}_{\hat{t}\sim\mu_{\gamma}}\left[{\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[-\frac{1}{\sigma^{2}(1-\gamma)}{\mathbb{E}}_{\eta_{\hat{t}}\sim\mathcal{N}(0,I_{m})}\left[Q(x_{\hat{t}},-Kx_{\hat{t}}+\sigma\eta_{\hat{t}})(\sigma\eta_{\hat{t}})\big{|}\hat{t},x_{0}\right]x_{\hat{t}}^{\top}\bigg{|}\hat{t}\right]\right]$
(46) $\displaystyle\overset{\mathrm{(ii)}}{=}\ $
$\displaystyle\frac{1}{1-\gamma}{\mathbb{E}}_{\hat{t}\sim\mu_{\gamma}}\left[{\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[{\mathbb{E}}_{\eta_{\hat{t}}\sim\mathcal{N}(0,I_{m})}\left[-\nabla_{u}Q^{K}(x_{\hat{t}},u)\bigg{|}_{u=-Kx_{\hat{t}}+\sigma\eta_{\hat{t}}}\big{|}\hat{t},x_{0}\right]x_{\hat{t}}^{\top}\bigg{|}\hat{t}\right]\right],$

where (i) follows from $x_{\hat{t}}$ being determined when given $x_{0}$ and
$\hat{t}$, and (ii) from Stein’s lemma [22]. Using (29), we compute

$\displaystyle\nabla_{u}Q^{K}(x_{\hat{t}},u)=$
$\displaystyle\nabla_{u}\left(x_{\hat{t}}^{\top}Qx_{\hat{t}}+u^{\top}Ru+\gamma(Ax_{\hat{t}}+Bu)^{\top}P_{K}(Ax_{\hat{t}}+Bu)\right)$
$\displaystyle=$ $\displaystyle 2Ru+2\gamma B^{\top}P_{K}Bu+2\gamma
B^{\top}P_{K}Ax_{\hat{t}},$

which evaluated at $u=-Kx_{\hat{t}}+\sigma\eta_{\hat{t}}$ yields

$\nabla_{u}Q^{K}(x_{\hat{t}},u)\bigg{|}_{u=-Kx_{\hat{t}}+\sigma\eta_{\hat{t}}}=2\left((R+\gamma
B^{\top}P_{K}B)(-Kx_{\hat{t}}+\sigma\eta_{\hat{t}})+\gamma
B^{\top}P_{K}Ax_{\hat{t}}\right).$

Substituting in (46), we obtain

$\displaystyle{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K)]$ $\displaystyle=\
$
$\displaystyle\frac{1}{1-\gamma}{\mathbb{E}}_{\hat{t}\sim\mu_{\gamma}}\left[{\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[2\left((R+\gamma
B^{\top}P_{K}B)K-\gamma
B^{\top}P_{K}A\right)x_{\hat{t}}x_{\hat{t}}^{\top}\bigg{|}\hat{t}\right]\right]$
$\displaystyle=\ $
$\displaystyle\frac{2}{1-\gamma}{\mathbb{E}}_{\hat{t}\sim\mu_{\gamma}}\left[\left((R+\gamma
B^{\top}P_{K}B)K-\gamma
B^{\top}P_{K}A\right)(A-BK)^{\hat{t}}{\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}[x_{0}x_{0}^{\top}]\left((A-BK)^{\hat{t}}\right)^{\top}\right]$
$\displaystyle=\ $ $\displaystyle 2\left((R+\gamma B^{\top}P_{K}B)K-\gamma
B^{\top}P_{K}A\right)\sum_{t=0}^{\infty}\gamma^{t}(A-BK)^{t}{\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}[x_{0}x_{0}^{\top}]\left((A-BK)^{t}\right)^{\top}$
$\displaystyle\overset{\mathrm{(i)}}{=}\ $ $\displaystyle 2\left((R+\gamma
B^{\top}P_{K}B)K-\gamma
B^{\top}P_{K}A\right){\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[\sum_{t=0}^{\infty}\gamma^{t}(A-BK)^{t}x_{0}x_{0}^{\top}\left((A-BK)^{t}\right)^{\top}\right]$
$\displaystyle\overset{\mathrm{(ii)}}{=}\ $ $\displaystyle 2\left((R+\gamma
B^{\top}P_{K}B)K-\gamma
B^{\top}P_{K}A\right){\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[\sum_{t=0}^{\infty}\gamma^{t}x_{t}x_{t}^{\top}\right]$
$\displaystyle\overset{\mathrm{(iii)}}{=}\ $
$\displaystyle\nabla{\mathcal{C}}(K),$

where (i) is done by utilizing the linearity of expectation along with
replacing $\hat{t}$ by $t$ as it is just a sum variable from that equation
forward, (ii) is due to $x_{t}=(A-BK)^{t}x_{0}$, and (iii) follows from (41).
∎

Before moving on to the next result, we define the undiscounted cost

(47)
${\mathcal{C}}_{\textup{und}}(K)={\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[\sum_{t=0}^{\infty}(x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t})\right],$

subject to (5).

######  Lemma 3.2.

Suppose $K_{0}$ is stable and suppose that

$\gamma\in\left(1-\frac{\sigma_{\mathrm{min}}(Q)}{11{\mathcal{C}}_{\textup{und}}(K_{0})},1\right).$

Then

(48)
$\sup_{K\in{\mathcal{G}}^{\text{lqr}}}\rho(A-BK)\leq\frac{1}{\sqrt{\gamma}}\sqrt{1-\frac{\sigma_{\mathrm{min}}(Q)}{10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*})}};$

in particular, the set ${\mathcal{G}}^{\text{lqr}}$ in (22) only contains
stable policies.

Before we provide the proof, we point out that the condition of stability of
$K_{0}$ readily implies that ${\mathcal{C}}_{\textup{und}}(K_{0})$ is finite.

###### Proof.

Suppose $\tilde{K}$ satifies $\rho(A-B\tilde{K})\geq 1$. Then we have

(49) $\displaystyle{\mathcal{C}}(\tilde{K})$
$\displaystyle={\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[\sum_{t=0}^{\infty}\gamma^{t}(x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t})\right]$
(50)
$\displaystyle\geq\sum_{t=0}^{\infty}\gamma^{t}\sigma_{\mathrm{min}}(Q){\mathbb{E}}\lVert(A-B\tilde{K})^{t}x_{0}\rVert^{2}$
(51)
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}\sigma_{\mathrm{min}}(Q){\mathbb{E}}[\operatorname{tr}(((A-B\tilde{K})^{t})^{\top}(A-B\tilde{K})^{t}x_{0}x_{0}^{\top})]$
(52)
$\displaystyle\overset{\mathrm{(i)}}{=}\sum_{t=0}^{\infty}\gamma^{t}\sigma_{\mathrm{min}}(Q)\lVert(A-B\tilde{K})^{t}\rVert_{F}^{2}$
(53)
$\displaystyle\geq\sum_{t=0}^{\infty}\gamma^{t}\sigma_{\mathrm{min}}(Q)\rho((A-B\tilde{K})^{t})^{2}$
(54)
$\displaystyle\overset{\mathrm{(ii)}}{\geq}\sum_{t=0}^{\infty}\gamma^{t}\sigma_{\mathrm{min}}(Q)$
(55) $\displaystyle=\frac{\sigma_{\mathrm{min}}(Q)}{1-\gamma},$

where (i) comes from the linearity of expectation along with the assumption on
the noise from (11), and (ii) follows from the instability of $\tilde{K}$ and
that $\rho(A^{t})=(\rho(A))^{t}$ which holds for any square matrix A. Now as a
result of this, if we also show
$\sup_{K\in{\mathcal{G}}^{\text{lqr}}}{\mathcal{C}}(K)<\frac{\sigma_{\mathrm{min}}(Q)}{1-\gamma}$,
we have proved stability of every $K$ in the set ${\mathcal{G}}^{\text{lqr}}$.
We do so as follows:

$\displaystyle\frac{\sigma_{\mathrm{min}}(Q)}{1-\gamma}\overset{\mathrm{(i)}}{>}11{\mathcal{C}}_{\textup{und}}(K_{0})\overset{\mathrm{(ii)}}{\geq}11{\mathcal{C}}(K_{0})\geq
10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*})\overset{\mathrm{(iii)}}{\geq}\sup_{K\in{\mathcal{G}}^{\text{lqr}}}{\mathcal{C}}(K),$

where (i) comes from the assumption on $\gamma$, (ii) from the fact that for a
given policy, the undiscounted cost is not less than the discounted cost, and
(iii) from the definition of the set ${\mathcal{G}}^{\text{lqr}}$ from (22).
This proves the second claim.

For the first part, since for any $K\in{\mathcal{G}}^{\text{lqr}}$ we have
that $\rho(A-BK)<1$, we conclude that

$\displaystyle{\mathcal{C}}(K)$
$\displaystyle={\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[\sum_{t=0}^{\infty}\gamma^{t}(x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t})\right]$
$\displaystyle\overset{\mathrm{(i)}}{\geq}\sum_{t=0}^{\infty}\gamma^{t}\sigma_{\mathrm{min}}(Q)\rho((A-BK)^{t})^{2}$
$\displaystyle=\sigma_{\mathrm{min}}(Q)\sum_{t=0}^{\infty}(\gamma(\rho(A-BK))^{2})^{t}$
$\displaystyle\overset{\mathrm{(ii)}}{=}\frac{\sigma_{\mathrm{min}}(Q)}{1-\gamma(\rho(A-BK))^{2}},$

where (i) is done the same way as (55) and (ii) follows from
$\gamma(\rho(A-BK))^{2}<1$ for $K\in{\mathcal{G}}^{\text{lqr}}$. As a result,
for $K\in{\mathcal{G}}^{\text{lqr}}$, we have that

$\displaystyle
1-\gamma(\rho(A-BK))^{2}\geq\frac{\sigma_{\mathrm{min}}(Q)}{{\mathcal{C}}(K)}\Rightarrow$
$\displaystyle\gamma(\rho(A-BK))^{2}\leq
1-\frac{\sigma_{\mathrm{min}}(Q)}{{\mathcal{C}}(K)}\Rightarrow$
$\displaystyle\rho(A-BK)\leq\frac{1}{\sqrt{\gamma}}\sqrt{1-\frac{\sigma_{\mathrm{min}}(Q)}{{\mathcal{C}}(K)}},$

which after taking a supremum gives

$\displaystyle\sup_{K\in{\mathcal{G}}^{\text{lqr}}}\rho(A-BK)\leq\frac{1}{\sqrt{\gamma}}\sup_{K\in{\mathcal{G}}^{\text{lqr}}}\sqrt{1-\frac{\sigma_{\mathrm{min}}(Q)}{{\mathcal{C}}(K)}}=\frac{1}{\sqrt{\gamma}}\sqrt{1-\frac{\sigma_{\mathrm{min}}(Q)}{10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*})}},$

concluding the proof. ∎

We next introduce a high probability upper bound on our gradient estimate on
any $K\in{\mathcal{G}}^{\text{lqr}}$.

######  Lemma 3.3.

Suppose $\delta\in(0,\frac{1}{e}]$, and $\gamma$ is chosen as in Lemma 3.2.
Then for any $K\in{\mathcal{G}}^{\text{lqr}}$, we have that

(56)
$\lVert\widehat{\nabla{\mathcal{C}}}(K)\rVert_{F}\leq\frac{\xi_{3}}{1-\gamma}\left(\log\frac{1}{\delta}\right)^{3/2}$

with probability at least $1-\delta$, where
$\xi_{1},\xi_{2},\xi_{3}\in{\mathbb{R}}$ are given by

(57) $\displaystyle\xi_{1}$ $\displaystyle:=\left(\lVert Q\rVert+2\lVert
R\rVert\widetilde{c_{K_{1}}}^{2}+2\gamma(10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*}))\right)e^{3}n^{3}\bar{{\mathcal{K}}}^{3}C_{m}^{3/2}$
(58) $\displaystyle\xi_{2}$ $\displaystyle:=\left(2\lVert
R\rVert+2\gamma\lVert
B\rVert^{2}(10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*}))\right)en\bar{{\mathcal{K}}}C_{m}^{1/2}$
(59) $\displaystyle\xi_{3}$
$\displaystyle:=\frac{1}{\sigma}\left(\xi_{1}5^{1/2}m^{1/2}\right)+\sigma\left(\xi_{2}5^{3/2}m^{3/2}\right),$

where $\bar{{\mathcal{K}}}$ is a positive constant. Moreover,

(60)
${\mathbb{E}}\lVert\widehat{\nabla{\mathcal{C}}}(K)\rVert_{F}^{2}\leq\frac{\xi_{4}}{(1-\gamma)^{2}},$

where

(61) $\displaystyle\xi_{4}$
$\displaystyle:=\frac{1}{\sigma^{2}}\xi_{1}^{2}m+2\xi_{1}\xi_{2}m(m+2)+\sigma^{2}\xi_{2}^{2}m(m+2)(m+4).$

###### Proof.

Using the formulation of $\widehat{\nabla{\mathcal{C}}}(K)$ derived in (31),
we have

(62) $\displaystyle\lVert\widehat{\nabla{\mathcal{C}}}(K)\rVert_{F}=$
$\displaystyle\left|\left|\frac{1}{\sigma(1-\gamma)}\eta_{\hat{t}}x_{\hat{t}}^{\top}Q^{K}(x_{\hat{t}},-Kx_{\hat{t}}+\sigma\eta_{\hat{t}})\right|\right|_{F}$
(63) $\displaystyle\leq$
$\displaystyle\frac{1}{\sigma(1-\gamma)}\lVert\eta_{\hat{t}}\rVert\lVert
x_{\hat{t}}\rVert Q^{K}(x_{\hat{t}},-Kx_{\hat{t}}+\sigma\eta_{\hat{t}}).$

First, note that

(64) $\lVert
x_{\hat{t}}\rVert=\lVert(A-BK)^{\hat{t}}x_{0}\rVert\leq\lVert(A-BK)^{\hat{t}}\rVert\lVert
x_{0}\rVert\overset{\mathrm{(i)}}{\leq}\sup_{t\geq 0}\lVert(A-BK)^{t}\rVert
C_{m}^{1/2},$

where (i) follows from the assumption on the initial state noise mentioned in
(11).

######  Sublemma 3.1.

We have that

(65) $\sup_{K\in{\mathcal{G}}^{\text{lqr}}}\sup_{t\geq
0}\lVert(A-BK)^{t}\rVert$

is finite.

_Proof of Sublemma 3.1._ We start by arguing that ${\mathcal{G}}^{\text{lqr}}$
is a compact set. First, note that since $\|K\|\leq\widetilde{c_{K_{1}}}$ (see
Remark 2.1) for any $K\in{\mathcal{G}}^{\text{lqr}}$, the set
${\mathcal{G}}^{\text{lqr}}$ is bounded. Secondly, since ${\mathcal{C}}(K)$ is
locally Lipschitz in ${\mathcal{G}}^{\text{lqr}}$, it is also continuous, and
hence, by the definition of ${\mathcal{G}}^{\text{lqr}}$ in (22), we have that
${\mathcal{G}}^{\text{lqr}}$ is the pre-image of the closed interval
$[0,10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*})]$ under a continuous map
${\mathcal{C}}:{\mathcal{G}}^{\text{lqr}}\rightarrow{\mathbb{R}}$, implying
${\mathcal{G}}^{\text{lqr}}$ is closed as well. As a result of this, we have
that ${\mathcal{G}}^{\text{lqr}}$ is compact. Now we move on to show why (65)
is finite.

First, let us define

$\displaystyle S(x_{0};K):=\sum_{t=0}^{\infty}\|x_{t}\|^{2},$

where $x_{t+1}=(A-BK)x_{t}$. Moreover, we let

$\displaystyle S(K)$
$\displaystyle:={\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}S(x_{0};K)$
$\displaystyle={\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[\sum_{t=0}^{\infty}\|x_{t}\|^{2}\right]$
$\displaystyle={\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[\sum_{t=0}^{\infty}\|(A-BK)^{t}x_{0}\|^{2}\right]$
$\displaystyle=\sum_{t=0}^{\infty}{\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\left[\operatorname{tr}\left(\left((A-BK)^{t}\right)^{\top}(A-BK)^{t}x_{0}x_{0}^{\top}\right)\right]$
$\displaystyle=\sum_{t=0}^{\infty}\lVert(A-BK)^{t}\rVert_{F}^{2}$
$\displaystyle\geq\sum_{t=0}^{\infty}\lVert(A-BK)^{t}\rVert^{2},$

which after taking the square root of both sides gives

$\displaystyle\sqrt{S(K)}$
$\displaystyle\geq\sqrt{\sum_{t=0}^{\infty}\lVert(A-BK)^{t}\rVert^{2}}$
$\displaystyle\geq\sup_{t\geq 0}\|(A-BK)^{t}\|.$

As a result, we have that

$\sup_{t\geq 0}\|(A-BK)^{t}\|\leq\sqrt{S(K)},$

which after taking a supremum over ${\mathcal{G}}^{\text{lqr}}$ yields

(66) $\sup_{K\in{\mathcal{G}}^{\text{lqr}}}\sup_{t\geq
0}\|(A-BK)^{t}\|\leq\sup_{K\in{\mathcal{G}}^{\text{lqr}}}\sqrt{S(K)}.$

Now it suffices to show $\sup_{K\in{\mathcal{G}}^{\text{lqr}}}\sqrt{S(K)}$ is
finite, which we prove by contradiction. Suppose that this is not the case.
Therefore, there exists a sequence $\\{K_{j}\\}_{j=1}^{\infty}$ such that
$\sqrt{S(K_{j})}\xrightarrow[]{j\to\infty}\infty$. By compactness, we can pick
a convergent subsequence whose limit we denote by $\bar{K}$. We will abuse
notation and henceforth use $K_{j}$ to refer to the subsequence; observe that
$K_{j}$ should also satisfy $\sqrt{S(K_{j})}\xrightarrow[]{j\to\infty}\infty$.

Now since $\bar{K}\in{\mathcal{G}}^{\text{lqr}}$, we have from Lemma 3.2 that
$A-B\bar{K}$ is strictly stable, and thus, there exists a Lyapunov function
$V(x)=x^{\top}\bar{P}x$ where $\bar{P}$ is a positive definite matrix that
satisfies

$(A-B\bar{K})^{\top}\bar{P}(A-B\bar{K})-\bar{P}=-I.$

Therefore, for $j$ large enough,

$(A-BK_{j})^{\top}\bar{P}(A-BK_{j})-\bar{P}\preceq-(1/2)I.$

Then

$\displaystyle V((A-BK_{j})x)-V(x)$
$\displaystyle=x^{T}(A-BK_{j})\bar{P}(A-BK_{j})x-x^{T}\bar{P}x$
$\displaystyle\leq-(1/2)\|x\|^{2}$
$\displaystyle=-\frac{1}{2\lambda_{\mathrm{max}}(\bar{P})}\left(\lambda_{\mathrm{max}}(\bar{P})\|x\|^{2}\right)$
$\displaystyle\overset{\mathrm{(i)}}{\leq}-\frac{1}{2\lambda_{\mathrm{max}}(\bar{P})}V(x),$

where (i) is due to the fact that
$V(x)\leq\lambda_{\mathrm{max}}(\bar{P})\|x\|^{2}$. Thus,

(67)
$V((A-BK_{j})x)\leq\left(1-\frac{1}{2\lambda_{\mathrm{max}}(\bar{P})}\right)V(x).$

As a result, we have that

$\displaystyle S(x_{0};K_{j})$
$\displaystyle=\sum_{t=0}^{\infty}\|x_{t}\|^{2}$
$\displaystyle\overset{\mathrm{(i)}}{\leq}\frac{1}{\lambda_{\mathrm{min}}(\bar{P})}\sum_{t=0}^{\infty}V((A-BK_{j})^{t}x_{0})$
$\displaystyle\overset{\mathrm{(ii)}}{\leq}\frac{1}{\lambda_{\mathrm{min}}(\bar{P})}\sum_{t=0}^{\infty}\left(1-\frac{1}{2\lambda_{\mathrm{max}}(\bar{P})}\right)^{t}V(x_{0})$
$\displaystyle\leq\frac{2\lambda_{\mathrm{max}}(\bar{P})}{\lambda_{\mathrm{min}}(\bar{P})}V(x_{0})$
$\displaystyle\leq\frac{2\lambda_{\mathrm{max}}^{2}(\bar{P})}{\lambda_{\mathrm{min}}(\bar{P})}\|x_{0}\|^{2},$

where (i) follows from $V(x)\geq\lambda_{\mathrm{min}}(\bar{P})\|x\|^{2}$ and
(ii) from (67). Now taking an expectation over $x_{0}\sim{\mathcal{D}}$ yields

$\displaystyle S(K_{j})$
$\displaystyle\leq\frac{2\lambda_{\mathrm{max}}^{2}(\bar{P})}{\lambda_{\mathrm{min}}(\bar{P})}{\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\|x_{0}\|^{2}$
$\displaystyle=\frac{2\lambda_{\mathrm{max}}^{2}(\bar{P})}{\lambda_{\mathrm{min}}(\bar{P})}{\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}\operatorname{tr}(x_{0}x_{0}^{\top})$
$\displaystyle=\frac{2\lambda_{\mathrm{max}}^{2}(\bar{P})}{\lambda_{\mathrm{min}}(\bar{P})}\operatorname{tr}\left({\mathbb{E}}_{x_{0}\sim{\mathcal{D}}}[x_{0}x_{0}^{\top}]\right)$
$\displaystyle=\frac{2\lambda_{\mathrm{max}}^{2}(\bar{P})}{\lambda_{\mathrm{min}}(\bar{P})}\operatorname{tr}(I_{n})$
$\displaystyle=\frac{2n\lambda_{\mathrm{max}}^{2}(\bar{P})}{\lambda_{\mathrm{min}}(\bar{P})},$

and hence,

$\sqrt{S(K_{j})}\leq\sqrt{\frac{2n\lambda_{\mathrm{max}}^{2}(\bar{P})}{\lambda_{\mathrm{min}}(\bar{P})}},$

which is finite, resulting in a contradiction, concluding the proof of (65)
being finite. $\diamond$

We now continue with the proof of lemma. Let us first make a remark. By the
Kreiss matrix theorem [16, 21], we have that

(68) ${\mathcal{K}}(A-BK)\leq\sup_{t\geq 0}\lVert(A-BK)^{t}\rVert\leq e\ n\
{\mathcal{K}}(A-BK).$

Consequently, we can define the following constant

(69)
$\bar{{\mathcal{K}}}:=\sup_{K\in{\mathcal{G}}^{\text{lqr}}}{\mathcal{K}}(A-BK),$

which is finite as a result of (68) along with the finiteness of
$\sup_{K\in{\mathcal{G}}^{\text{lqr}}}\sup_{t\geq 0}\lVert(A-BK)^{t}\rVert$.
Combining (68) and (69) with (64) gives

(70) $\lVert x_{\hat{t}}\rVert\leq e\ n\ C_{m}^{1/2}\ {\mathcal{K}}(A-BK)\leq
e\ n\ C_{m}^{1/2}\ \bar{{\mathcal{K}}},$

for any $\hat{t}\geq 0$. Moreover,

(71) $\displaystyle Q^{K}(x_{\hat{t}},-Kx_{\hat{t}}+\sigma\eta_{\hat{t}})=$
$\displaystyle
x_{\hat{t}}^{\top}Qx_{\hat{t}}+(-Kx_{\hat{t}}+\sigma\eta_{\hat{t}})^{\top}R(-Kx_{\hat{t}}+\sigma\eta_{\hat{t}})$
(72) $\displaystyle+\gamma((A-BK)x_{\hat{t}}+\sigma
B\eta_{\hat{t}})^{\top}P_{K}((A-BK)x_{\hat{t}}+\sigma B\eta_{\hat{t}})$ (73)
$\displaystyle\overset{\mathrm{(i)}}{\leq}$ $\displaystyle\lVert Q\rVert
e^{2}n^{2}\bar{{\mathcal{K}}}^{2}C_{m}+\lVert R\rVert\lVert-
Kx_{\hat{t}}+\sigma\eta_{\hat{t}}\rVert^{2}+\gamma\lVert P_{K}\rVert\lVert
x_{\hat{t}+1}+\sigma B\eta_{\hat{t}}\rVert^{2}$ (74)
$\displaystyle\overset{\mathrm{(ii)}}{\leq}$ $\displaystyle\lVert Q\rVert
e^{2}n^{2}\bar{{\mathcal{K}}}^{2}C_{m}+2\lVert R\rVert\left(\lVert
K\rVert^{2}\lVert
x_{\hat{t}}\rVert^{2}+\sigma^{2}\lVert\eta_{\hat{t}}\rVert^{2}\right)$ (75)
$\displaystyle+2\gamma{\mathcal{C}}(K)\left(\lVert
x_{\hat{t}+1}\rVert^{2}+\sigma^{2}\lVert
B\rVert^{2}\lVert\eta_{\hat{t}}\rVert^{2}\right)$ (76)
$\displaystyle\overset{\mathrm{(iii)}}{\leq}$ $\displaystyle\left(\lVert
Q\rVert+2\lVert
R\rVert\widetilde{c_{K_{1}}}^{2}+2\gamma(10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*}))\right)e^{2}n^{2}\bar{{\mathcal{K}}}^{2}C_{m}$
(77) $\displaystyle+\left(2\sigma^{2}\lVert R\rVert+2\gamma\sigma^{2}\lVert
B\rVert^{2}(10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*}))\right)\lVert\eta_{\hat{t}}\rVert^{2},$

where (i) follows from (70), (ii) from $\lVert
P_{K}\rVert\leq\operatorname{tr}(P_{K})$ along with
$\operatorname{tr}(P_{K})={\mathcal{C}}(K)$ as shown in (18), and (iii) from
the fact that $\lVert K\rVert\leq\widetilde{c_{K_{1}}}$ for any
$K\in{\mathcal{G}}^{\text{lqr}}$ (see Remark 2.1) along with reapplying (70)
and utilizing the upper bound obtained on ${\mathcal{C}}(K)$ by the definition
of the set ${\mathcal{G}}^{\text{lqr}}$. Now applying the derived bounds (70)
and (77) on (63), we conclude that

(78) $\displaystyle\lVert\widehat{\nabla{\mathcal{C}}}(K)\rVert_{F}\leq$
$\displaystyle\frac{\left(\lVert Q\rVert+2\lVert
R\rVert\widetilde{c_{K_{1}}}^{2}+2\gamma(10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*}))\right)e^{3}n^{3}\bar{{\mathcal{K}}}^{3}C_{m}^{3/2}}{\sigma(1-\gamma)}\lVert\eta_{\hat{t}}\rVert$
(79) $\displaystyle+\frac{\sigma^{2}\left(2\lVert R\rVert+2\gamma\lVert
B\rVert^{2}(10{\mathcal{C}}(K_{0})+{\mathcal{C}}(K^{*}))\right)en\bar{{\mathcal{K}}}C_{m}^{1/2}}{\sigma(1-\gamma)}\lVert\eta_{\hat{t}}\rVert^{3}$
(80) $\displaystyle=$
$\displaystyle\frac{1}{1-\gamma}\left(\frac{1}{\sigma}\xi_{1}\lVert\eta_{\hat{t}}\rVert+\sigma\xi_{2}\lVert\eta_{\hat{t}}\rVert^{3}\right).$

Furthermore, since $\eta_{\hat{t}}\sim\mathcal{N}(0,I_{m})$ for any $\hat{t}$,
$\lVert\eta_{\hat{t}}\rVert^{2}$ is distributed according to the chi-squared
distribution with $m$ degrees of freedom
($\lVert\eta_{\hat{t}}\rVert^{2}\sim\chi^{2}(m)$ for any $\hat{t}$).
Therefore, the standard [14] bounds suggest that for arbitrary $y>0$, we have
that

(81) ${\mathbb{P}}\\{\lVert\eta_{\hat{t}}\rVert^{2}\geq m+2\sqrt{my}+2y\\}\leq
e^{-y}.$

Now since by our assumption $0<\delta\leq 1/e$, it holds that
$y=m\log\frac{1}{\delta}\geq m$ and thus

$\displaystyle{\mathbb{P}}\\{\lVert\eta_{\hat{t}}\rVert^{2}\geq
5y\\}\leq{\mathbb{P}}\\{\lVert\eta_{\hat{t}}\rVert^{2}\geq
m+2\sqrt{my}+2y\\}\leq e^{-y},$

which after substituting $y$ with its value $m\log\frac{1}{\delta}$ gives

$\displaystyle{\mathbb{P}}\\{\lVert\eta_{\hat{t}}\rVert^{2}\geq
5m\log\frac{1}{\delta}\\}\leq
e^{-m\log\frac{1}{\delta}}=\delta^{m}\leq\delta.$

As a result, we have $\lVert\eta_{\hat{t}}\rVert\leq
5^{1/2}m^{1/2}(\log\frac{1}{\delta})^{1/2}$ and consequently

$\lVert\eta_{\hat{t}}\rVert^{3}\leq
5^{3/2}m^{3/2}(\log\frac{1}{\delta})^{3/2}$

with probability at least $1-\delta$, which after applying on (80) yields

$\displaystyle\lVert\widehat{\nabla{\mathcal{C}}}(K)\rVert_{F}\leq$
$\displaystyle\frac{1}{1-\gamma}\left(\frac{1}{\sigma}\xi_{1}5^{1/2}m^{1/2}\left(\log\frac{1}{\delta}\right)^{1/2}+\sigma\xi_{2}5^{3/2}m^{3/2}\left(\log\frac{1}{\delta}\right)^{3/2}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{1-\gamma}\left(\frac{1}{\sigma}\xi_{1}5^{1/2}m^{1/2}+\sigma\xi_{2}5^{3/2}m^{3/2}\right)\left(\log\frac{1}{\delta}\right)^{3/2}$
$\displaystyle=$
$\displaystyle\frac{\xi_{3}}{1-\gamma}\left(\log\frac{1}{\delta}\right)^{3/2},$

proving the first claim.

As for the second claim, note that using (80), we have

(82)
$\displaystyle\lVert\widehat{\nabla{\mathcal{C}}}(K)\rVert_{F}^{2}\leq\frac{1}{(1-\gamma)^{2}}\left(\frac{1}{\sigma^{2}}\xi_{1}^{2}\lVert\eta_{\hat{t}}\rVert^{2}+2\xi_{1}\xi_{2}\lVert\eta_{\hat{t}}\rVert^{4}+\sigma^{2}\xi_{2}^{2}\lVert\eta_{\hat{t}}\rVert^{6}\right).$

Now since $\lVert\eta_{\hat{t}}\rVert\sim\chi(m)$ whose moments are known,
taking an expectation on both sides of (82) results in

$\displaystyle{\mathbb{E}}\lVert\widehat{\nabla{\mathcal{C}}}(K)\rVert_{F}^{2}\leq$
$\displaystyle\frac{1}{(1-\gamma)^{2}}\left(\frac{1}{\sigma^{2}}\xi_{1}^{2}{\mathbb{E}}\lVert\eta_{\hat{t}}\rVert^{2}+2\xi_{1}\xi_{2}{\mathbb{E}}\lVert\eta_{\hat{t}}\rVert^{4}+\sigma^{2}\xi_{2}^{2}{\mathbb{E}}\lVert\eta_{\hat{t}}\rVert^{6}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{(1-\gamma)^{2}}\left(\frac{1}{\sigma^{2}}\xi_{1}^{2}m+2\xi_{1}\xi_{2}m(m+2)+\sigma^{2}\xi_{2}^{2}m(m+2)(m+4)\right)$
$\displaystyle=$ $\displaystyle\frac{\xi_{4}}{(1-\gamma)^{2}},$

concluding the proof. ∎

Following Lemma 3.3, we now define the following event for each iteration $t$
of Algorithm 1:

(83)
$\mathcal{A}_{t}=\left\\{\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\leq\frac{\zeta_{3}}{1-\gamma}\left(\log{\frac{1}{\delta}}\right)^{3/2}\right\\}.$

Having this, we introduce the following lemma:

######  Lemma 3.4.

Suppose $\delta\in(0,e^{-3/2}]$, and $\gamma$ is chosen as in Lemma 3.2. Then
for any given $K_{t}\in{\mathcal{G}}^{\text{lqr}}$, we have that

(84)
$\|{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}_{t}}]-\nabla{\mathcal{C}}(K_{t})\|_{F}\leq\frac{3\zeta_{3}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}.$

###### Proof.

Following Proposition 3.1, we have that

$\displaystyle\nabla{\mathcal{C}}(K_{t})=$
$\displaystyle{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})]$
$\displaystyle=$
$\displaystyle{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}_{t}}]+{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}^{c}_{t}}].$

Therefore,

(85)
$\displaystyle\|{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}_{t}}]-\nabla{\mathcal{C}}(K_{t})\|_{F}$
(86) $\displaystyle=\ $
$\displaystyle\|{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}^{c}_{t}}]\|_{F}$
(87) $\displaystyle\overset{\mathrm{(i)}}{\leq}\ $
$\displaystyle{\mathbb{E}}\left[\|\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}^{c}_{t}}\|_{F}\right]$
(88) $\displaystyle=\ $
$\displaystyle{\mathbb{E}}\left[\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}1_{\mathcal{A}^{c}_{t}}\right]$
(89) $\displaystyle\overset{\mathrm{(ii)}}{\leq}\ $
$\displaystyle{\mathbb{E}}\left[\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}1_{\left\\{\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\geq\frac{\zeta_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}{1-\gamma}\right\\}}\right]$
(90) $\displaystyle=\ $
$\displaystyle{\mathbb{P}}\left\\{\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\geq\frac{\zeta_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}{1-\gamma}\right\\}{\mathbb{E}}\left[\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\bigg{|}\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\geq\frac{\zeta_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}{1-\gamma}\right],$

where (i) follows from Jensen’s inequality and (ii) from the fact that

$\mathcal{A}^{c}_{t}=\left\\{\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}>\frac{\zeta_{3}}{1-\gamma}\left(\log{\frac{1}{\delta}}\right)^{3/2}\right\\}\subseteq\left\\{\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\geq\frac{\zeta_{3}}{1-\gamma}\left(\log{\frac{1}{\delta}}\right)^{3/2}\right\\}.$

Moreover, it holds that

(91)
$\displaystyle{\mathbb{E}}\left[\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\bigg{|}\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\geq\frac{\zeta_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}{1-\gamma}\right]$
(92) $\displaystyle=$
$\displaystyle\frac{\zeta_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}{1-\gamma}+\frac{\bigints_{\frac{\zeta_{3}}{1-\gamma}\left(\log{\frac{1}{\delta}}\right)^{3/2}}^{\infty}{\mathbb{P}}\\{\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\geq
z\\}\
dz}{{\mathbb{P}}\left\\{\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\geq\frac{\zeta_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}{1-\gamma}\right\\}}.$

Now recall from Lemma 3.3 that

(93)
${\mathbb{P}}\left\\{\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\geq\frac{\zeta_{3}}{1-\gamma}\left(\log{\frac{1}{\delta}}\right)^{3/2}\right\\}\leq\delta$

for arbitrary $\delta$, which implies

(94) ${\mathbb{P}}\left\\{\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\geq
z\right\\}\leq e^{-\left(\frac{z(1-\gamma)}{\zeta_{3}}\right)^{2/3}}.$

Now combining (94), (92), and (90) yields

(95)
$\displaystyle\|{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}_{t}}]-\nabla{\mathcal{C}}(K_{t})\|_{F}$
(96) $\displaystyle\leq$
$\displaystyle{\mathbb{P}}\left\\{\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\geq\frac{\zeta_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}{1-\gamma}\right\\}\frac{\zeta_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}{1-\gamma}+\bigintss_{\frac{\zeta_{3}}{1-\gamma}\left(\log{\frac{1}{\delta}}\right)^{3/2}}^{\infty}e^{-\left(\frac{z(1-\gamma)}{\zeta_{3}}\right)^{2/3}}dz$
(97) $\displaystyle\overset{\mathrm{(i)}}{\leq}$
$\displaystyle\frac{\zeta_{3}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}+\frac{\zeta_{3}}{1-\gamma}\bigintss_{\left(\log{\frac{1}{\delta}}\right)^{3/2}}^{\infty}e^{-u^{2/3}}du$
(98) $\displaystyle=$
$\displaystyle\frac{\zeta_{3}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}+\frac{\zeta_{3}}{1-\gamma}\left(\frac{3}{2}\delta\left(\log{\frac{1}{\delta}}\right)^{1/2}+\frac{3}{4}\sqrt{\pi}\operatorname{erfc}\left(\sqrt{\log{\frac{1}{\delta}}}\right)\right)$
(99) $\displaystyle\overset{\mathrm{(ii)}}{\leq}$
$\displaystyle\frac{\zeta_{3}}{1-\gamma}\left(\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}+\frac{3}{2}\delta\left(\log{\frac{1}{\delta}}\right)^{1/2}+\frac{3}{4}\sqrt{\pi}\delta\right)$
(100) $\displaystyle\overset{\mathrm{(iii)}}{\leq}$
$\displaystyle\frac{3\zeta_{3}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2},$

where (i) follows from (93) along with a change of variables
$u=\left(\frac{1-\gamma}{\zeta_{3}}\right)z$ in the integral, (ii) from the
fact that
$\operatorname{erfc}\left(\sqrt{\log{\frac{1}{\delta}}}\right)\leq\delta$, and
(iii) from $\delta\leq e^{-3/2}$. This concludes the proof. ∎

Before introducing the next lemma, let us denote the optimality gap of iterate
$t$ of the algorithm by

(101) $\Delta_{t}:={\mathcal{C}}(K_{t})-{\mathcal{C}}(K^{*}).$

Moreover, let ${\mathcal{F}}_{t}$ denote the $\sigma$-algebra containing the
randomness up to iteration $t$ of Algorithm 1 (including $K_{t}$ but not
$\widehat{\nabla{\mathcal{C}}}(K_{t})$). We then define

(102) $\tau_{1}:=\min\left\\{t\ |\
\Delta_{t}>10{\mathcal{C}}(K_{0})\right\\},$

which is a stopping time with respect to ${\mathcal{F}}_{t}$.

######  Lemma 3.5.

Suppose $\delta\in(0,e^{-3/2}]$, $\gamma$ is as suggested in Lemma 3.2, and
the update rule follows

(103) $K_{t+1}=K_{t}-\alpha_{t}\widehat{\nabla{\mathcal{C}}}(K_{t})$

with a step-size $\alpha_{t}$ such that for all $t\in\\{0,1,2,\dotsc\\}$,

$\alpha_{t}\leq\frac{\omega_{\text{lqr}}}{\frac{\zeta_{3}}{1-\gamma}\left(\log{\frac{1}{\delta}}\right)^{3/2}}.$

Then for any $t\in\\{0,1,2,\dotsc\\}$, we have

(104)
${\mathbb{E}}[\Delta_{t+1}1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]1_{\tau_{1}>t}\leq\left(\left(1-\mu_{\text{lqr}}\alpha_{t}\right)\Delta_{t}+\frac{3\zeta_{3}\widetilde{c_{K_{1}}}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\alpha_{t}+\frac{\phi_{\text{lqr}}\alpha_{t}^{2}}{2}\frac{\xi_{4}}{(1-\gamma)^{2}}\right)1_{\tau_{1}>t},$

where $\Delta_{t}$ and $\mathcal{A}_{t}$ are defined in (101) and (83)
respectively.

###### Proof.

First, note that by the definition of $\tau_{1}$ in (102), $\tau_{1}>t$
implies $K_{t}\in{\mathcal{G}}^{\text{lqr}}$. In addition, since
$\alpha_{t}\leq\frac{\omega_{\text{lqr}}}{\frac{\zeta_{3}}{1-\gamma}\left(\log{\frac{1}{\delta}}\right)^{3/2}}$,
the event $\mathcal{A}_{t}$ implies that

$\|K_{t+1}-K_{t}\|_{F}=\|\alpha_{t}\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}\leq\omega_{\text{lqr}}.$

Thus, by local smoothness of ${\mathcal{C}}(K_{t})$, see Lemma 2.2, it holds
that

$\displaystyle(\Delta_{t+1}-\Delta_{t})1_{\tau_{1}>t}1_{\mathcal{A}_{t}}=$
$\displaystyle({\mathcal{C}}(K_{t+1}-{\mathcal{C}}(K_{t}))1_{\tau_{1}>t}1_{\mathcal{A}_{t}}$
$\displaystyle\leq$
$\displaystyle\left(\left\langle\nabla{\mathcal{C}}(K_{t}),K_{t+1}-K_{t}\right\rangle+\frac{\phi_{\text{lqr}}}{2}\lVert
K_{t+1}-K_{t}\rVert_{F}^{2}\right)1_{\tau_{1}>t}1_{\mathcal{A}_{t}}$
$\displaystyle=$
$\displaystyle\left(-\alpha_{t}\left\langle\nabla{\mathcal{C}}(K_{t}),\widehat{\nabla{\mathcal{C}}}(K_{t})\right\rangle+\frac{\phi_{\text{lqr}}\alpha_{t}^{2}}{2}\lVert\widehat{\nabla{\mathcal{C}}}(K_{t})\rVert_{F}^{2}\right)1_{\tau_{1}>t}1_{\mathcal{A}_{t}},$

which after taking an expectation conditioned on ${\mathcal{F}}_{t}$ gives

$\displaystyle{\mathbb{E}}[\Delta_{t+1}1_{\tau_{1}>t}1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]-{\mathbb{E}}[\Delta_{t}1_{\tau_{1}>t}1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]$
$\displaystyle\leq$
$\displaystyle-\alpha_{t}\left\langle\nabla{\mathcal{C}}(K_{t}),{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\tau_{1}>t}1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]\right\rangle+\frac{\phi_{\text{lqr}}}{2}\alpha_{t}^{2}{\mathbb{E}}[\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}^{2}1_{\tau_{1}>t}1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}].$

Since $\Delta_{t}$ and $1_{\tau_{1}>t}$ are determined by ${\mathcal{F}}_{t}$,

$\displaystyle{\mathbb{E}}[\Delta_{t+1}1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]1_{\tau_{1}>t}$
$\displaystyle\leq$
$\displaystyle\left(\Delta_{t}{\mathbb{E}}[1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]-\alpha_{t}\left\langle\nabla{\mathcal{C}}(K_{t}),{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]\right\rangle+\frac{\phi_{\text{lqr}}}{2}\alpha_{t}^{2}{\mathbb{E}}[\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}^{2}1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]\right)1_{\tau_{1}>t}$
$\displaystyle\overset{\mathrm{(i)}}{\leq}$
$\displaystyle\left(\Delta_{t}-\alpha_{t}\left\langle\nabla{\mathcal{C}}(K_{t}),{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]\right\rangle+\frac{\phi_{\text{lqr}}}{2}\alpha_{t}^{2}{\mathbb{E}}[\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}^{2}|{\mathcal{F}}_{t}]\right)1_{\tau_{1}>t}$
$\displaystyle=$
$\displaystyle\Delta_{t}1_{\tau_{1}>t}-\alpha_{t}\left\langle\nabla{\mathcal{C}}(K_{t}),\nabla{\mathcal{C}}(K_{t})+{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]-\nabla{\mathcal{C}}(K_{t})\right\rangle
1_{\tau_{1}>t}$
$\displaystyle+\frac{\phi_{\text{lqr}}}{2}\alpha_{t}^{2}{\mathbb{E}}[\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}^{2}|{\mathcal{F}}_{t}]1_{\tau_{1}>t}$
$\displaystyle=$
$\displaystyle\Delta_{t}1_{\tau_{1}>t}-\alpha_{t}\left\langle\nabla{\mathcal{C}}(K_{t}),\nabla{\mathcal{C}}(K_{t})\right\rangle
1_{\tau_{1}>t}$
$\displaystyle-\alpha_{t}\left\langle\nabla{\mathcal{C}}(K_{t}),{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]-\nabla{\mathcal{C}}(K_{t})\right\rangle
1_{\tau_{1}>t}+\frac{\phi_{\text{lqr}}}{2}\alpha_{t}^{2}{\mathbb{E}}[\|\widehat{\nabla{\mathcal{C}}}(K_{t})\|_{F}^{2}|{\mathcal{F}}_{t}]1_{\tau_{1}>t}$
$\displaystyle\overset{\mathrm{(ii)}}{\leq}$
$\displaystyle\Delta_{t}1_{\tau_{1}>t}-\alpha_{t}\|\nabla{\mathcal{C}}(K_{t})\|_{F}^{2}1_{\tau_{1}>t}$
$\displaystyle+\alpha_{t}\|\nabla{\mathcal{C}}(K_{t})\|_{F}\|{\mathbb{E}}[\widehat{\nabla{\mathcal{C}}}(K_{t})1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]-\nabla{\mathcal{C}}(K_{t})\|_{F}1_{\tau_{1}>t}+\frac{\phi_{\text{lqr}}}{2}\alpha_{t}^{2}\frac{\zeta_{4}}{(1-\gamma)^{2}}1_{\tau_{1}>t}$
$\displaystyle\overset{\mathrm{(iii)}}{\leq}$
$\displaystyle\Delta_{t}1_{\tau_{1}>t}-\alpha_{t}\mu_{\text{lqr}}\Delta_{t}1_{\tau_{1}>t}+\frac{3\zeta_{3}\widetilde{c_{K_{1}}}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\alpha_{t}1_{\tau_{1}>t}+\frac{\phi_{\text{lqr}}}{2}\alpha_{t}^{2}\frac{\zeta_{4}}{(1-\gamma)^{2}}1_{\tau_{1}>t}$
$\displaystyle=$
$\displaystyle\left(\left(1-\mu_{\text{lqr}}\alpha_{t}\right)\Delta_{t}+\frac{3\zeta_{3}\widetilde{c_{K_{1}}}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\alpha_{t}+\frac{\phi_{\text{lqr}}\alpha_{t}^{2}}{2}\frac{\xi_{4}}{(1-\gamma)^{2}}\right)1_{\tau_{1}>t},$

where (i) follows from $1_{\mathcal{A}_{t}}\leq 1$, (ii) from Lemma 3.3, and
(iii) from applying the PL inequality (21), the fact that
$\|\nabla{\mathcal{C}}(K_{t})\|_{F}\leq\widetilde{c_{K_{1}}}$ for any
$K_{t}\in{\mathcal{G}}^{\text{lqr}}$ (see Remark 2.1), and Lemma 3.4. This
finishes the proof of Lemma 3.5. ∎

We are now in a position to state a precise version of our main result.

######  Theorem 3.1.

Suppose $K_{0}$ is stable and $\gamma$ is as suggested in Lemma 3.2. If the
step-size $\alpha_{t}$ is chosen as

(105) $\displaystyle\alpha_{t}=\frac{2}{\mu_{\text{lqr}}}\frac{1}{t+N}\quad$
$\displaystyle\text{for}\quad
N=\max\left\\{N_{1},\frac{2}{\mu_{\text{lqr}}}\frac{\xi_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}{(1-\gamma)\omega_{\text{lqr}}}\right\\},$

where

(106) $\displaystyle
N_{1}=\max\left\\{2,\frac{4\phi_{\text{lqr}}\xi_{4}}{\mu_{\text{lqr}}^{2}(1-\gamma)^{2}}\frac{2}{{\mathcal{C}}(K_{0})}\right\\},$

then for a given error tolerance $\varepsilon$ such that
${\mathcal{C}}(K_{0})\geq\frac{\varepsilon}{20}$, and $\delta$ chosen
arbitrarily to satisfy

(107) $\displaystyle\delta\leq\min$ $\displaystyle\Bigg{\\{}2\times
10^{-5},\left(\frac{\phi_{\text{lqr}}\zeta_{4}\omega_{\text{lqr}}}{960\zeta_{3}^{2}\widetilde{c_{K_{1}}}{\mathcal{C}}(K_{0})}\right)^{3}\varepsilon^{3},$
(108)
$\displaystyle\left(\frac{\phi_{\text{lqr}}\zeta_{4}}{480(1-\gamma)\mu_{\text{lqr}}\zeta_{3}\widetilde{c_{K_{1}}}N_{1}{\mathcal{C}}(K_{0})}\right)^{3}\varepsilon^{3},\left(\frac{\mu_{\text{lqr}}(1-\gamma)}{240\zeta_{3}\widetilde{c_{K_{1}}}}\right)^{3}\varepsilon^{3}\Bigg{\\}},$

the iterate $K_{T}$ of the Algorithm 1 after

(109) $T=\frac{40}{\varepsilon}N{\mathcal{C}}(K_{0})$

steps satisfies

(110) ${\mathcal{C}}(K_{T})-{\mathcal{C}}(K^{*})\leq\varepsilon$

with a probability of at least $4/5-\delta T$.

It is essential to re-emphasize that, as also evident from the statement of
Theorem 3.1, there is no reliance on a stability assumption; rather, the
result is proven to hold with a certain probability. In particular, the
instances of the algorithm that lead to instability at any iteration before
$T$ are factored into the failure probability $1/5+\delta T$.

The proof of Theorem 3.1 relies on an intermediate result, namely Proposition
3.2, which we establish next. Before doing so, we provide some observations
regarding the statement of the theorem. First, we have the following remark
for $\delta$:

######  Remark 3.1 (Selection of $\delta$ for the probability of failure).

The $\delta T$ term in the probability of failure stated in Theorem 3.1 can be
adjusted arbitrarily; however, since $T$ depends on $N$ which depends on
$\delta$ itself, we add some further discussion here. If we want the $\delta
T$ term to be less than some arbitrary small $\delta^{\prime}$, it needs to
hold that

$\delta
T=\delta\frac{40}{\varepsilon}\max\left\\{N_{1}{\mathcal{C}}(K_{0}),\frac{2\zeta_{3}{\mathcal{C}}(K_{0})}{\mu_{\text{lqr}}\omega_{\text{lqr}}(1-\gamma)}\left(\log{\frac{1}{\delta}}\right)^{3/2}\right\\}\leq\delta^{\prime}.$

Therefore, $\delta$ first needs to satisfy

(111)
$\displaystyle\frac{40}{\varepsilon}N_{1}{\mathcal{C}}(K_{0})\delta\leq\delta^{\prime}\Rightarrow\delta\leq\frac{\delta^{\prime}\varepsilon}{40N_{1}{\mathcal{C}}(K_{0})},$

and secondly,

(112)
$\displaystyle\frac{80\zeta_{3}{\mathcal{C}}(K_{0})}{\mu_{\text{lqr}}\omega_{\text{lqr}}(1-\gamma)}\frac{1}{\varepsilon}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\leq\delta^{\prime}\Rightarrow\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\leq\frac{\mu_{\text{lqr}}\omega_{\text{lqr}}(1-\gamma)}{80\zeta_{3}{\mathcal{C}}(K_{0})}\delta^{\prime}\varepsilon.$

Now since $a^{3}\left(\log{\frac{1}{a^{3}}}\right)^{3/2}\leq a$ for any
$a\in(0,1)$, for (112) to hold, it would suffice to have

(113)
$\delta\leq\left(\frac{\mu_{\text{lqr}}\omega_{\text{lqr}}(1-\gamma)}{80\zeta_{3}{\mathcal{C}}(K_{0})}\right)^{3}(\delta^{\prime}\varepsilon)^{3}.$

Note that (113) is only a loose sufficient bound on $\delta$ that can be
improved (for instance, the exponents in (113) can be reduced from $3$ to $2$
considering the other requirements on $\delta$ in (108)); however, since the
dependence of $T$ on $\delta$ is logarithmic, the looser requirement only adds
a constant and does not change the order.

As a result, adding (111) and (113) to the existing requirements on $\delta$
in (108), we will have

(114) $\displaystyle\delta\leq\min$ $\displaystyle\Bigg{\\{}2\times
10^{-5},\left(\frac{\phi_{\text{lqr}}\zeta_{4}\omega_{\text{lqr}}}{960\zeta_{3}^{2}\widetilde{c_{K_{1}}}{\mathcal{C}}(K_{0})}\right)^{3}\varepsilon^{3},\left(\frac{\phi_{\text{lqr}}\zeta_{4}}{480(1-\gamma)\mu_{\text{lqr}}\zeta_{3}\widetilde{c_{K_{1}}}N_{1}{\mathcal{C}}(K_{0})}\right)^{3}\varepsilon^{3},$
(115)
$\displaystyle\left(\frac{\mu_{\text{lqr}}(1-\gamma)}{240\zeta_{3}\widetilde{c_{K_{1}}}}\right)^{3}\varepsilon^{3},\frac{\delta^{\prime}\varepsilon}{40N_{1}{\mathcal{C}}(K_{0})},\left(\frac{\mu_{\text{lqr}}\omega_{\text{lqr}}(1-\gamma)}{80\zeta_{3}{\mathcal{C}}(K_{0})}\right)^{3}(\delta^{\prime}\varepsilon)^{3}\Bigg{\\}},$

which will lead to the result of Theorem 3.1 holding with probability
$4/5-\delta^{\prime}$ after

$T\sim\frac{N}{\varepsilon}\sim\mathcal{O}\left(\frac{1}{\varepsilon}\left(\log{\frac{1}{(\delta^{\prime}\varepsilon)^{3}}}\right)^{3/2}\right)=\mathcal{O}\left(\frac{1}{\varepsilon}\left(\log{\frac{1}{\delta^{\prime}}+\log{\frac{1}{\varepsilon}}}\right)^{3/2}\right)=\widetilde{\mathcal{O}}\left(\frac{1}{\varepsilon}\right)$

iterations of Algorithm 1. $\diamond$

Secondly, we find it worthwile to provide the following observation on the
choice of $\sigma$:

######  Remark 3.2 (Selection of $\sigma$ and its impact on $T$).

Note that the value of $\sigma$ in (27) is at our discretion, so one natural
question would be regarding the asymptotic analysis of $\sigma$ and its impact
on our rate $T$. Observe that the only effect of $\sigma$ on $T$ is through
$\xi_{3}$ and $\xi_{4}$ defined in (59) and (61) respectively. Taking
everything else as constants, following the choice of $T$ and $N$ suggested in
Theorem 3.1, we have that
$T\geq\mathcal{O}\left(\max\\{\xi_{3},\xi_{4}\\}\right)$. Now since both
$\xi_{3}$ and $\xi_{4}$ will grow unbounded as $\sigma$ approaches either zero
or infinity, so does $T$. Therefore, we choose a non-zero value for $\sigma$
instead. An optimal value can be derived, but given that this only affects the
constants in the rate, we opt for $\sigma=1$. $\diamond$

Thirdly, note that for any $K_{t}\in{\mathcal{G}}^{\text{lqr}}$, by our choice
of $\alpha_{t}$ and $N$ in Theorem 3.1, we have

(116) $\displaystyle\lVert K_{t+1}-K_{t}\rVert_{F}=$
$\displaystyle\lVert\alpha_{t}\widehat{\nabla{\mathcal{C}}}(K_{t})\rVert_{F}$
(117) $\displaystyle=$
$\displaystyle\frac{2}{\mu_{\text{lqr}}}\frac{1}{t+N}\lVert\widehat{\nabla{\mathcal{C}}}(K_{t})\rVert_{F}$
(118) $\displaystyle\leq$
$\displaystyle\frac{2}{\mu_{\text{lqr}}}\frac{1}{N}\lVert\widehat{\nabla{\mathcal{C}}}(K_{t})\rVert_{F}$
(119) $\displaystyle\overset{\mathrm{(i)}}{\leq}$
$\displaystyle\omega_{\text{lqr}}\frac{\lVert\widehat{\nabla{\mathcal{C}}}(K_{t})\rVert_{F}}{\frac{\xi_{3}}{1-\gamma}\left(\log\frac{1}{\delta}\right)^{3/2}},$

where (i) follows from (105). Now applying Lemma 3.3 on (119) yields

(120) $\lVert
K_{t+1}-K_{t}\rVert_{F}\leq\omega_{\text{lqr}}=\inf_{K\in{\mathcal{G}}^{\text{lqr}}}\omega_{K}$

with probability at least $1-\delta$, where
$\omega_{K}=\min\\{\beta_{K},\zeta_{K}\\}$. This implies that the local
Lipschitzness and local smoothness properties of the cost hold for the update
at iteration $t$ with probability at least $1-\delta$.

Fourthly, to help unravel the logical reasoning elucidated in the proof, we
introduce the following stopping times:

(121) $\displaystyle\tau_{2}$ $\displaystyle:=\min\left\\{t\geq 1\ \Big{|}\
\lVert\widehat{\nabla{\mathcal{C}}}(K_{t-1})\rVert_{F}>\frac{\xi_{3}}{1-\gamma}\left(\log\frac{1}{\delta}\right)^{3/2}\right\\}$
(122) $\displaystyle\tau$ $\displaystyle:=\min\\{\tau_{1},\tau_{2}\\},$

with $\tau_{1}$ previously defined in (102). Essentially, one can observe that
as long as $t<\tau_{1}$ and $t+1<\tau_{2}$, it holds that
$K_{t}\in{\mathcal{G}}^{\text{lqr}}$ and $\lVert
K_{t+1}-K_{t}\rVert_{F}\leq\omega_{\text{lqr}}$, implying that local
Lipschitzness and local smoothness properties of the cost hold until that
iteration. By the definition of $\tau$ in (122), we have that

(123) $1_{\tau>t}=1_{\tau_{1}>t}1_{\tau_{2}>t}.$

Moreover, following the definition of $\mathcal{A}_{t}$ in (83), it also holds
that

(124) $1_{\tau_{2}>t+1}=1_{\tau_{2}>t}1_{\mathcal{A}_{t}}.$

Finally, we note that the idea of introducing a stopping time (122), which
helps identify the failure of the algorithm and is also used to define a
stopped process later on, is inspired by [17]. However, despite the similarity
of our forthcoming statements to those in the proof of [17, Theorem 8], the
paths we take to prove said statements are considerably different due to the
differences in how we defined our stopping time (and subsequently the stopped
process to be defined later on), our gradient estimation method, the time-
varying learning rate, etc.

Having covered all of the above, we are now ready to present the following
proposition:

######  Proposition 3.2.

Under the parameter settings of Theorem 3.1, we have

${\mathbb{E}}[\Delta_{T}1_{\tau>T}]\leq\frac{\varepsilon}{20}.$

Furthermore, the event $\left\\{\tau>T\right\\}$ happens with a probability of
at least $\frac{17}{20}-\delta T$.

###### Proof.

The following provides us with a stepping stone for proving the first claim:

######  Sublemma 3.2.

Under the parameter settings of Theorem 3.1, we have that

(125)
${\mathbb{E}}[\Delta_{t}1_{\tau>t}]\leq\frac{\varepsilon}{40}+\frac{N{\mathcal{C}}(K_{0})}{t+N},$

for all $t\in[T]$.

_Proof of Sublemma 3.2._ We prove this result by induction on $t$ as follows:

Base case ($t=0$):

$\displaystyle\Delta_{0}1_{\tau>0}\leq\Delta_{0}\leq{\mathcal{C}}(K_{0})=\frac{N{\mathcal{C}}(K_{0})}{0+N}\leq\frac{\varepsilon}{40}+\frac{N{\mathcal{C}}(K_{0})}{0+N},$

which after taking expectation proves the claim for $t=0$.

Inductive step: Let $k\in[T-1]$ be fixed and assume that

(126)
${\mathbb{E}}[\Delta_{k}1_{\tau>k}]\leq\frac{\varepsilon}{40}+\frac{N{\mathcal{C}}(K_{0})}{k+N}$

holds (the inductive hypothesis). Observe that

(127) $\displaystyle{\mathbb{E}}[\Delta_{k+1}1_{\tau>k+1}]$
$\displaystyle\overset{\mathrm{(i)}}{=}{\mathbb{E}}[\Delta_{k+1}1_{\tau_{1}>k+1}1_{\tau_{2}>k+1}]$
(128)
$\displaystyle\overset{\mathrm{(ii)}}{\leq}{\mathbb{E}}[\Delta_{k+1}1_{\tau_{1}>k}1_{\tau_{2}>k}1_{\mathcal{A}_{k}}]$
(129)
$\displaystyle={\mathbb{E}}[{\mathbb{E}}[\Delta_{k+1}1_{\tau_{1}>k}1_{\tau_{2}>k}1_{\mathcal{A}_{k}}|{\mathcal{F}}_{k}]]$
(130)
$\displaystyle\overset{\mathrm{(iii)}}{=}{\mathbb{E}}[{\mathbb{E}}[\Delta_{k+1}1_{\mathcal{A}_{k}}|{\mathcal{F}}_{k}]1_{\tau_{1}>k}1_{\tau_{2}>k}],$

where (i) follows from (123), (ii) from equation (124) along with the fact
that $1_{\tau_{1}>k+1}\leq 1_{\tau_{1}>k}$, and (iii) is due to
$1_{\tau_{2}>k}$ and $1_{\tau_{1}>k}$ being determined by ${\mathcal{F}}_{k}$.
By Lemma 3.5, we have that

(131)
$\displaystyle\left({\mathbb{E}}[\Delta_{k+1}1_{\mathcal{A}_{k}}|{\mathcal{F}}_{k}]1_{\tau_{1}>k}\right)1_{\tau_{2}>k}$
(132) $\displaystyle\leq$
$\displaystyle\left(\left(\left(1-\mu_{\text{lqr}}\alpha_{k}\right)\Delta_{k}+\frac{3\zeta_{3}\widetilde{c_{K_{1}}}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\alpha_{k}+\frac{\phi_{\text{lqr}}\alpha_{k}^{2}}{2}\frac{\xi_{4}}{(1-\gamma)^{2}}\right)1_{\tau_{1}>k}\right)1_{\tau_{2}>k}$
(133) $\displaystyle\overset{\mathrm{(i)}}{=}$
$\displaystyle\left(\left(1-\frac{2}{k+N}\right)\Delta_{k}+\frac{6\zeta_{3}\widetilde{c_{K_{1}}}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}}{\mu_{\text{lqr}}(1-\gamma)}\frac{1}{k+N}+\frac{2\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{(k+N)^{2}}\right)1_{\tau>k},$

where (i) follows from(123) along with replacing $\alpha_{k}$ with its value
in (105). Now due to the choice of $\delta$ in (108), we have that

$\delta\leq\left(\frac{\mu_{\text{lqr}}(1-\gamma)}{240\zeta_{3}\widetilde{c_{K_{1}}}}\right)^{3}\varepsilon^{3},$

which after noting that $a^{3}\left(\log{\frac{1}{a^{3}}}\right)^{3/2}\leq a$
for any $a\in(0,1)$ implies

(134)
$\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\leq\frac{\mu_{\text{lqr}}(1-\gamma)}{240\zeta_{3}\widetilde{c_{K_{1}}}}\varepsilon\Rightarrow\frac{6\zeta_{3}\widetilde{c_{K_{1}}}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}}{\mu_{\text{lqr}}(1-\gamma)}\leq\frac{\varepsilon}{40}.$

Applying (134) on (133) yields

$\displaystyle{\mathbb{E}}[\Delta_{k+1}1_{\mathcal{A}_{k}}|{\mathcal{F}}_{k}]1_{\tau_{1}>k}1_{\tau_{2}>k}$
$\displaystyle\leq$
$\displaystyle\left(\left(1-\frac{2}{k+N}\right)\Delta_{k}+\frac{\varepsilon}{40}\frac{1}{k+N}+\frac{2\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{(k+N)^{2}}\right)1_{\tau>k}$
$\displaystyle\leq$
$\displaystyle\left(1-\frac{2}{k+N}\right)\Delta_{k}1_{\tau>k}+\frac{\varepsilon}{40}\frac{1}{k+N}+\frac{2\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{(k+N)^{2}},$

which after taking expectation results in

(135)
$\displaystyle{\mathbb{E}}[{\mathbb{E}}[\Delta_{k+1}1_{\mathcal{A}_{k}}|{\mathcal{F}}_{k}]1_{\tau_{1}>k}1_{\tau_{2}>k}]$
(136) $\displaystyle\leq$
$\displaystyle\left(1-\frac{2}{k+N}\right){\mathbb{E}}[\Delta_{k}1_{\tau>k}]+\frac{\varepsilon}{40}\frac{1}{k+N}+\frac{2\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{(k+N)^{2}}.$

Combining the hypothesis (inequality (126)) and inequality (130) with (136),
we obtain

$\displaystyle{\mathbb{E}}[\Delta_{k+1}1_{\tau>k+1}]$ $\displaystyle\leq$
$\displaystyle\left(1-\frac{2}{k+N}\right)\left(\frac{\varepsilon}{40}+\frac{N{\mathcal{C}}(K_{0})}{k+N}\right)+\frac{\varepsilon}{40}\frac{1}{k+N}+\frac{2\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{(k+N)^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{\varepsilon}{40}+\left(1-\frac{1}{k+N}\right)\frac{N{\mathcal{C}}(K_{0})}{k+N}-\frac{1}{(k+N)^{2}}\left(N{\mathcal{C}}(K_{0})-\frac{2\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\right)$
$\displaystyle\overset{\mathrm{(i)}}{\leq}$
$\displaystyle\frac{\varepsilon}{40}+\left(\frac{k+N-1}{(k+N)^{2}}\right)N{\mathcal{C}}(K_{0})$
$\displaystyle\leq$
$\displaystyle\frac{\varepsilon}{40}+\frac{N{\mathcal{C}}(K_{0})}{k+N+1},$

where (i) follows from the fact that

$N{\mathcal{C}}(K_{0})\geq
N_{1}{\mathcal{C}}(K_{0})\geq\left(\frac{4\phi_{\text{lqr}}\xi_{4}}{\mu_{\text{lqr}}^{2}(1-\gamma)^{2}}\frac{2}{{\mathcal{C}}(K_{0})}\right){\mathcal{C}}(K_{0})=\frac{8\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\geq\frac{2\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}.$

This proves the claim for $k+1$, completing the inductive step. $\diamond$

Now utilizing Sublemma 3.2 and the choice of $T$ from (109) in Theorem 3.1,

$\displaystyle{\mathbb{E}}[\Delta_{T}1_{\tau>T}]\leq\frac{\varepsilon}{40}+\frac{N{\mathcal{C}}(K_{0})}{T+N}\leq\frac{\varepsilon}{40}+\frac{N{\mathcal{C}}(K_{0})}{T}=\frac{\varepsilon}{20},$

which finishes the proof of the first claim of Proposition 3.2. Now before
moving on to the second claim, we introduce the following sublemma:

######  Sublemma 3.3.

Under the parameter setup of Theorem 3.1, we have that for all $t\in[T]$,

(137)
$\frac{3\zeta_{3}\widetilde{c_{K_{1}}}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\alpha_{t}+\frac{\phi_{\text{lqr}}\zeta_{4}}{2(1-\gamma)^{2}}\alpha_{t}^{2}+\frac{4\phi_{\text{lqr}}\zeta_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{t+N+1}\leq\frac{4\phi_{\text{lqr}}\zeta_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{t+N}.$

_Proof of Sublemma 3.3._ First, substituting $\alpha_{t}$ with its value in
(105), inequality (137) becomes

(138)
$\displaystyle\frac{6\zeta_{3}\widetilde{c_{K_{1}}}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}}{(1-\gamma)\mu_{\text{lqr}}}\frac{1}{t+N}+\frac{2\phi_{\text{lqr}}\zeta_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\left(\frac{1}{(t+N)^{2}}+\frac{2}{t+N+1}\right)\leq\frac{2\phi_{\text{lqr}}\zeta_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\left(\frac{2}{t+N}\right)$
(139)
$\displaystyle\iff\frac{6\zeta_{3}\widetilde{c_{K_{1}}}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}}{(1-\gamma)\mu_{\text{lqr}}}\frac{1}{t+N}\leq\frac{2\phi_{\text{lqr}}\zeta_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\left(\frac{2}{t+N}-\frac{2}{t+N+1}-\frac{1}{(t+N)^{2}}\right)$
(140)
$\displaystyle\iff\frac{6\zeta_{3}\widetilde{c_{K_{1}}}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}}{(1-\gamma)\mu_{\text{lqr}}}\frac{1}{t+N}\leq\frac{2\phi_{\text{lqr}}\zeta_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\left(\frac{2}{(t+N)(t+N+1)}-\frac{1}{(t+N)^{2}}\right)$
(141)
$\displaystyle\iff\frac{6\zeta_{3}\widetilde{c_{K_{1}}}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}}{(1-\gamma)\mu_{\text{lqr}}}\frac{1}{t+N}\leq\frac{2\phi_{\text{lqr}}\zeta_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\left(\frac{t+N-1}{(t+N)^{2}(t+N+1)}\right)$
(142)
$\displaystyle\iff\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\leq\frac{\phi_{\text{lqr}}\zeta_{4}}{3\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}}\left(\frac{t+N-1}{(t+N)(t+N+1)}\right).$

Note that for the right-hand side of (142), we have for all $t\in[T]$ that

(143)
$\displaystyle\frac{\phi_{\text{lqr}}\zeta_{4}}{3\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}}\left(\frac{t+N-1}{t+N}\frac{1}{t+N+1}\right)$
$\displaystyle\overset{\mathrm{(i)}}{\geq}\frac{\phi_{\text{lqr}}\zeta_{4}}{6\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}}\left(\frac{1}{t+N+1}\right)$
(144)
$\displaystyle\geq\frac{\phi_{\text{lqr}}\zeta_{4}}{6\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}}\left(\frac{1}{T+N+1}\right)$
(145)
$\displaystyle\overset{\mathrm{(ii)}}{\geq}\frac{\phi_{\text{lqr}}\zeta_{4}}{12\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}}\left(\frac{1}{T}\right),$

where (i) follows from the fact that $\frac{t+N-1}{t+N}\geq\frac{1}{2}$ which
is due to $N\geq 2$ (see (105) and (106)), and (ii) from
${\mathcal{C}}(K_{0})\geq\frac{\varepsilon}{20}$ under the settings of Theorem
3.1, which results in

$T=\frac{40}{\varepsilon}N{\mathcal{C}}(K_{0})\geq 2N\geq
N+1\Rightarrow\frac{1}{T+N+1}\geq\frac{1}{2T}.$

As a result of (142) and (145), in order to conclude the proof Sublemma 3.3,
it would suffice to show that

(146) $\displaystyle\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\leq$
$\displaystyle\frac{\phi_{\text{lqr}}\zeta_{4}}{12\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}}\left(\frac{1}{T}\right)$
(147) $\displaystyle=$
$\displaystyle\frac{\phi_{\text{lqr}}\zeta_{4}}{12\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}}\frac{\varepsilon}{40}\frac{1}{N{\mathcal{C}}(K_{0})}$
(148) $\displaystyle=$
$\displaystyle\frac{\phi_{\text{lqr}}\zeta_{4}}{12\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}}\frac{\varepsilon}{40}\frac{1}{\max\left\\{N_{1}{\mathcal{C}}(K_{0}),\frac{2{\mathcal{C}}(K_{0})}{\mu_{\text{lqr}}}\frac{\xi_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}{(1-\gamma)\omega_{\text{lqr}}}\right\\}}$
(149) $\displaystyle=$
$\displaystyle\frac{\phi_{\text{lqr}}\zeta_{4}}{12\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}}\frac{\varepsilon}{40}\min\left\\{\frac{1}{N_{1}{\mathcal{C}}(K_{0})},\frac{\mu_{\text{lqr}}\omega_{\text{lqr}}(1-\gamma)}{2{\mathcal{C}}(K_{0})\zeta_{3}\left(\log{\frac{1}{\delta}}\right)^{3/2}}\right\\}.$

For (149) to hold, we need two inequalities to hold as a result of the
$\min\\{.,.\\}$ operator. First, we require

(150)
$\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\leq\frac{\phi_{\text{lqr}}\zeta_{4}}{480\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}N_{1}{\mathcal{C}}(K_{0})}\varepsilon.$

Now since $a^{3}\left(\log{\frac{1}{a^{3}}}\right)^{3/2}\leq a$ for all
$a\in(0,1)$ and the choice of $\delta$ in (108), i.e.,

$\delta\leq\left(\frac{\phi_{\text{lqr}}\zeta_{4}}{480\zeta_{3}\widetilde{c_{K_{1}}}(1-\gamma)\mu_{\text{lqr}}N_{1}{\mathcal{C}}(K_{0})}\right)^{3}\varepsilon^{3},$

we conclude that (150) holds for the parameter setup of Theorem 3.1.

Secondly, it needs to hold that

(151)
$\displaystyle\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\leq\frac{\phi_{\text{lqr}}\zeta_{4}\omega_{\text{lqr}}}{960\zeta_{3}^{2}\widetilde{c_{K_{1}}}{\mathcal{C}}(K_{0})\left(\log{\frac{1}{\delta}}\right)^{3/2}}\varepsilon$
(152)
$\displaystyle\iff\delta\left(\log{\frac{1}{\delta}}\right)^{3}\leq\frac{\phi_{\text{lqr}}\zeta_{4}\omega_{\text{lqr}}}{960\zeta_{3}^{2}\widetilde{c_{K_{1}}}{\mathcal{C}}(K_{0})}\varepsilon.$

Now if

$\frac{\phi_{\text{lqr}}\zeta_{4}\omega_{\text{lqr}}}{960\zeta_{3}^{2}\widetilde{c_{K_{1}}}{\mathcal{C}}(K_{0})}\varepsilon\leq
0.028,$

for any
$\delta\leq\left(\frac{\phi_{\text{lqr}}\zeta_{4}\omega_{\text{lqr}}}{960\zeta_{3}^{2}\widetilde{c_{K_{1}}}{\mathcal{C}}(K_{0})}\right)^{3}\varepsilon^{3}$,
we have that

$\delta\left(\log{\frac{1}{\delta}}\right)^{3}\leq\frac{\phi_{\text{lqr}}\zeta_{4}\omega_{\text{lqr}}}{960\zeta_{3}^{2}\widetilde{c_{K_{1}}}{\mathcal{C}}(K_{0})}\varepsilon,$

and if

$\frac{\phi_{\text{lqr}}\zeta_{4}\omega_{\text{lqr}}}{960\zeta_{3}^{2}\widetilde{c_{K_{1}}}{\mathcal{C}}(K_{0})}\varepsilon>0.028,$

it would suffice to have that

$\delta\left(\log{\frac{1}{\delta}}\right)^{3}\leq 0.028,$

which would hold for any $\delta\leq 2\times 10^{-5}$. As a result, due to the
choice of $\delta$ in (108), i.e.,

$\delta\leq\min\left\\{2\times
10^{-5},\left(\frac{\phi_{\text{lqr}}\zeta_{4}\omega_{\text{lqr}}}{960\zeta_{3}^{2}\widetilde{c_{K_{1}}}{\mathcal{C}}(K_{0})}\right)^{3}\varepsilon^{3}\right\\},$

we have that (152) will also hold under the parameter setup of Theorem 3.1.
Finally, since both (150) and (152) hold for $\delta$ as chosen in (108),
inequality (149) is satisfied, finishing the proof. $\diamond$

We now prove the second claim. Even though our proof strategy mimics the one
in [17], the structure of the stopping times in (102) and (122) makes the
arguments more involved. Note that this difference in the definition of the
stopping time (and subsequently the stopped process) can be attributed to the
fact that in contrast to [17]’s one scenario (leaving the stable region) which
may lead their algorithm to fail, there are two possible scenarios that may
cause the failure of our algorithm. We start by introducing the stopped
process

(153) $Y_{t}:=\Delta_{\tau_{1}\wedge
t}1_{\tau_{2}>t}+\frac{4\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{t+N}\quad\text{for
each }t\in[T].$

We next show that this process is a supermartingale. First, we have that

(154) $\displaystyle{\mathbb{E}}[Y_{t+1}|{\mathcal{F}}_{t}]$ (155)
$\displaystyle=$ $\displaystyle{\mathbb{E}}[\Delta_{\tau_{1}\wedge
t+1}1_{\tau_{2}>t+1}|{\mathcal{F}}_{t}]+\frac{4\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{t+N+1}$
(156) $\displaystyle=$ $\displaystyle{\mathbb{E}}[\Delta_{\tau_{1}\wedge
t+1}1_{\tau_{2}>t+1}\left(1_{\tau_{1}\leq
t}+1_{\tau_{1}>t}\right)|{\mathcal{F}}_{t}]+\frac{4\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{t+N+1}$
(157) $\displaystyle=$ $\displaystyle{\mathbb{E}}[\Delta_{\tau_{1}\wedge
t+1}1_{\tau_{2}>t+1}1_{\tau_{1}\leq
t}|{\mathcal{F}}_{t}]+{\mathbb{E}}[\Delta_{\tau_{1}\wedge
t+1}1_{\tau_{2}>t+1}1_{\tau_{1}>t}|{\mathcal{F}}_{t}]+\frac{4\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{t+N+1}.$

Then for the first term on the right-hand side of (157), it holds that

(158) $\displaystyle{\mathbb{E}}[\Delta_{\tau_{1}\wedge
t+1}1_{\tau_{2}>t+1}1_{\tau_{1}\leq t}|{\mathcal{F}}_{t}]\leq$
$\displaystyle{\mathbb{E}}[\Delta_{\tau_{1}\wedge
t+1}1_{\tau_{2}>t}1_{\tau_{1}\leq t}|{\mathcal{F}}_{t}]$ (159)
$\displaystyle=$ $\displaystyle
1_{\tau_{2}>t}{\mathbb{E}}[\Delta_{\tau_{1}\wedge t+1}1_{\tau_{1}\leq
t}|{\mathcal{F}}_{t}]$ (160) $\displaystyle=$ $\displaystyle
1_{\tau_{2}>t}{\mathbb{E}}[\Delta_{\tau_{1}\wedge t}1_{\tau_{1}\leq
t}|{\mathcal{F}}_{t}]$ (161) $\displaystyle=$
$\displaystyle\Delta_{\tau_{1}\wedge t}1_{\tau_{2}>t}1_{\tau_{1}\leq t}.$

As for the second term, we have

(162) $\displaystyle{\mathbb{E}}[\Delta_{\tau_{1}\wedge
t+1}1_{\tau_{2}>t+1}1_{\tau_{1}>t}|{\mathcal{F}}_{t}]$ (163)
$\displaystyle\overset{\mathrm{(i)}}{=}$
$\displaystyle{\mathbb{E}}[\Delta_{\tau_{1}\wedge
t+1}1_{\tau_{1}>t}1_{\tau_{2}>t}1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]$ (164)
$\displaystyle=$
$\displaystyle{\mathbb{E}}[\Delta_{t+1}1_{\tau_{1}>t}1_{\tau_{2}>t}1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]$
(165) $\displaystyle=$
$\displaystyle{\mathbb{E}}[\Delta_{t+1}1_{\mathcal{A}_{t}}|{\mathcal{F}}_{t}]1_{\tau_{1}>t}1_{\tau_{2}>t}$
(166) $\displaystyle\overset{\mathrm{(ii)}}{\leq}$
$\displaystyle\left(\left(1-\mu_{\text{lqr}}\alpha_{t}\right)\Delta_{t}+\frac{3\zeta_{3}\widetilde{c_{K_{1}}}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\alpha_{t}+\frac{\phi_{\text{lqr}}\alpha_{t}^{2}}{2}\frac{\xi_{4}}{(1-\gamma)^{2}}\right)1_{\tau_{1}>t}1_{\tau_{2}>t}$
(167) $\displaystyle=$
$\displaystyle\left(\left(1-\frac{2}{t+N}\right)\Delta_{t}+\frac{3\zeta_{3}\widetilde{c_{K_{1}}}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\alpha_{t}+\frac{\phi_{\text{lqr}}\alpha_{t}^{2}}{2}\frac{\xi_{4}}{(1-\gamma)^{2}}\right)1_{\tau_{1}>t}1_{\tau_{2}>t}$
(168) $\displaystyle\overset{\mathrm{(iii)}}{\leq}$
$\displaystyle\Delta_{t}1_{\tau_{1}>t}1_{\tau_{2}>t}+\frac{3\zeta_{3}\widetilde{c_{K_{1}}}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\alpha_{t}+\frac{\phi_{\text{lqr}}\alpha_{t}^{2}}{2}\frac{\xi_{4}}{(1-\gamma)^{2}}$
(169) $\displaystyle\overset{\mathrm{(iv)}}{=}$
$\displaystyle\Delta_{\tau_{1}\wedge
t}1_{\tau_{1}>t}1_{\tau_{2}>t}+\frac{3\zeta_{3}\widetilde{c_{K_{1}}}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\alpha_{t}+\frac{\phi_{\text{lqr}}\alpha_{t}^{2}}{2}\frac{\xi_{4}}{(1-\gamma)^{2}},$

where (i) follows from (124), (ii) from Lemma 3.5, (iii) from
$1_{\tau_{1}>t}1_{\tau_{2}>t}\leq 1$ along with the fact that
$\frac{2}{t+N}\leq 1$ for all $t\in[T]$, and (iv) from
$\Delta_{t}1_{\tau_{1}>t}=\Delta_{\tau_{1}\wedge t}1_{\tau_{1}>t}$.

Combining (157), (161), and (169), we obtain that for all $t\in[T]$,

$\displaystyle{\mathbb{E}}[Y_{t+1}|{\mathcal{F}}_{t}]\leq$
$\displaystyle\Delta_{\tau_{1}\wedge t}1_{\tau_{2}>t}1_{\tau_{1}\leq
t}+\Delta_{\tau_{1}\wedge t}1_{\tau_{1}>t}1_{\tau_{2}>t}$
$\displaystyle+\frac{3\zeta_{3}\widetilde{c_{K_{1}}}}{1-\gamma}\delta\left(\log{\frac{1}{\delta}}\right)^{3/2}\alpha_{t}+\frac{\phi_{\text{lqr}}\alpha_{t}^{2}}{2}\frac{\xi_{4}}{(1-\gamma)^{2}}+\frac{4\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{t+N+1}$
$\displaystyle\overset{\mathrm{(i)}}{\leq}$
$\displaystyle\Delta_{\tau_{1}\wedge t}1_{\tau_{2}>t}(1_{\tau_{1}\leq
t}+1_{\tau_{1}>t})+\frac{4\phi_{\text{lqr}}\zeta_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{t+N}$
$\displaystyle=$ $\displaystyle\Delta_{\tau_{1}\wedge
t}1_{\tau_{2}>t}+\frac{4\phi_{\text{lqr}}\zeta_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{t+N}$
$\displaystyle=$ $\displaystyle Y_{t},$

where (i) follows from Sublemma 3.3. This proves the claim that $Y_{t}$ is a
supermartingale. Moreover, define the following events:

(170) $\displaystyle\mathcal{E}_{1}$
$\displaystyle:=\\{\tau_{2}\leq\tau_{1}\;\text{and}\;\tau_{2}\in[T]\\}$ (171)
$\displaystyle\mathcal{E}_{2}$
$\displaystyle:=\\{\tau_{1}<\tau_{2}\;\text{and}\;\tau_{1}\in[T]\\}$ (172)
$\displaystyle\mathcal{E}_{3}$
$\displaystyle:=\left\\{\max_{t\in[T]}\Delta_{\tau_{1}\wedge
t}1_{\tau_{2}>t}\geq 10{\mathcal{C}}(K_{0})\right\\},$

and hence, we have ${\mathbb{P}}\\{\tau\leq
T\\}={\mathbb{P}}(\mathcal{E}_{1})+{\mathbb{P}}(\mathcal{E}_{2})$. Now since
$\tau_{2}\leq\tau_{1}$ in $\mathcal{E}_{1}$ suggests that
$\lVert\widehat{\nabla{\mathcal{C}}}(K_{\tau_{2}-1})\rVert_{F}>\frac{\xi_{3}}{1-\gamma}\left(\log\frac{1}{\delta}\right)^{3/2}$
despite $\Delta_{\tau_{2}-1}\leq 10{\mathcal{C}}(K_{0})$ (which implies
${\mathcal{K}}_{\tau_{2}-1}\in{\mathcal{G}}^{\text{lqr}}$), after applying
union bound on the result of Lemma 3.3, we have

(173) ${\mathbb{P}}(\mathcal{E}_{1})\leq\delta T.$

Furthermore, note that $\tau_{1}<\tau_{2}$ in $\mathcal{E}_{2}$ implies that
$\Delta_{\tau_{1}\wedge\tau_{1}}1_{\tau_{2}>\tau_{1}}=\Delta_{\tau_{1}}$ and
since $\tau_{1}\in[T]$, it holds that

$\max_{t\in[T]}\Delta_{\tau_{1}\wedge
t}1_{\tau_{2}>t}\geq\Delta_{\tau_{1}\wedge\tau_{1}}1_{\tau_{2}>\tau_{1}}=\Delta_{\tau_{1}}\overset{\mathrm{(i)}}{>}10{\mathcal{C}}(K_{0}),$

where (i) follows the definition of $\tau_{1}$. As a result of this, we have
that $\mathcal{E}_{2}$ implies $\mathcal{E}_{3}$, and consequently,
${\mathbb{P}}(\mathcal{E}_{2})\leq{\mathbb{P}}(\mathcal{E}_{3})$. Finally,
since $Y_{t}\geq\Delta_{\tau_{1}\wedge t}1_{\tau_{2}>t}$ for all $t\in[T]$, we
have that

(174) $\displaystyle{\mathbb{P}}(\mathcal{E}_{2})\leq$
$\displaystyle{\mathbb{P}}(\mathcal{E}_{3})$ (175) $\displaystyle=$
$\displaystyle{\mathbb{P}}\left\\{\max_{t\in[T]}\Delta_{\tau_{1}\wedge
t}1_{\tau_{2}>t}\geq 10{\mathcal{C}}(K_{0})\right\\}$ (176)
$\displaystyle\leq$ $\displaystyle{\mathbb{P}}\left\\{\max_{t\in[T]}Y_{t}\geq
10{\mathcal{C}}(K_{0})\right\\}$ (177)
$\displaystyle\overset{\mathrm{(i)}}{\leq}$
$\displaystyle\frac{{\mathbb{E}}[Y_{0}]}{10{\mathcal{C}}(K_{0})}$ (178)
$\displaystyle=$ $\displaystyle\frac{\Delta_{\tau_{1}\wedge
0}1_{\tau_{2}>0}+\frac{4\phi_{\text{lqr}}\xi_{4}}{(1-\gamma)^{2}\mu^{2}_{\text{lqr}}}\frac{1}{N}}{10{\mathcal{C}}(K_{0})}$
(179) $\displaystyle\overset{\mathrm{(ii)}}{\leq}$
$\displaystyle\frac{\Delta_{0}+{\mathcal{C}}(K_{0})/2}{10{\mathcal{C}}(K_{0})}$
(180) $\displaystyle\leq$
$\displaystyle\frac{{\mathcal{C}}(K_{0})+{\mathcal{C}}(K_{0})/2}{10{\mathcal{C}}(K_{0})}$
(181) $\displaystyle=$ $\displaystyle\frac{3}{20},$

where (i) follows from applying Doob/Ville’s inequality for supermartingales,
and (ii) from the condition on the choice of $N$ in Theorem 3.1. Utilizing the
acquired probability bounds (173) and (181), we observe that

$\displaystyle{\mathbb{P}}\\{\tau\leq T\\}=$
$\displaystyle{\mathbb{P}}(\mathcal{E}_{1})+{\mathbb{P}}(\mathcal{E}_{2})$
$\displaystyle\leq$ $\displaystyle\delta T+\frac{3}{20},$

which verifies the second claim of Proposition 3.2, concluding the proof. ∎

The proof of our main result is a straightforward corollary:

###### Proof of Theorem 3.1.

We now show how Proposition 3.2 can be employed to validate the claims of
Theorem 3.1. Note that

$\displaystyle{\mathbb{P}}\left\\{\Delta_{T}\geq\varepsilon\right\\}\leq$
$\displaystyle{\mathbb{P}}\left\\{\Delta_{T}1_{\tau>T}\geq\varepsilon\right\\}+{\mathbb{P}}\left\\{1_{\tau\leq
T}=1\right\\}$ $\displaystyle\overset{\mathrm{(i)}}{\leq}$
$\displaystyle\frac{1}{\varepsilon}{\mathbb{E}}[\Delta_{T}1_{\tau>T}]+{\mathbb{P}}\left\\{\tau\leq
T\right\\}$ $\displaystyle\overset{\mathrm{(ii)}}{\leq}$
$\displaystyle\frac{1}{20}+\frac{3}{20}+\delta T=\frac{1}{5}+\delta T,$

where (i) follows from Markov’s inequality and (ii) follows from Proposition
3.2. ∎

##  4\. Summary and Discussion

We have provided an algorithm with $\varepsilon$-optimality guarantees with a
provable convergence rate of $\widetilde{\mathcal{O}}(1/\varepsilon)$ for the
discounted discrete-time LQR problem in the model-free setting. This was made
possible by employing a gradient estimation technique inspired by REINFORCE,
combined with a time-varying step-size. Our results contrast from the ones
obtained by two-point methods – which make the stronger assumption of assuming
access to cost for two different policies with the same realization of the
initial conditions – as well as results that assume stability of the policies.

An interesting future direction would be to investigate an actor-critic
approach that could maintain the rate without requiring further assumptions.
Moreover, one could consider an extension of the presented results for the
undiscounted case; in particular, the current analysis of gradient estimation
with one zero-order evaluation per iteration heavily relies on sampling from a
distribution whose definition relies on the discount factor be strictly less
that one.

## References

  * [1] Y. Abbasi-Yadkori and C. Szepesvári.  Regret bounds for the adaptive control of linear quadratic systems.  In Proceedings of the 24th Annual Conference on Learning Theory, pages 1–26, 2011.
  * [2] M. Akbari, B. Gharesifard, and T. Linder.  Logarithmic regret in adaptive control of noisy linear quadratic regulator systems using hints.  Journal of Machine Learning Research, 2022.  submitted, arXiv preprint arXiv:2210.16303.
  * [3] D. P. Bertsekas.  Dynamic Programming and Optimal Control.  Athena Scientific, 1995.
  * [4] S. Bittanti and M. C. Campi.  Adaptive control of linear time invariant systems: the “bet on the best” principle.  Communications in Information & Systems, 6(4):299–320, 2006.
  * [5] M. C. Campi and P. R. Kumar.  Adaptive linear quadratic Gaussian control: the cost-biased approach revisited.  SIAM Journal on Control and Optimization, 36(6):1890–1907, 1998\.
  * [6] H. Chen and L. Guo.  Optimal adaptive control and consistent parameter estimates for ARMAX model with quadratic cost.  SIAM Journal on Control and Optimization, 25(4):845–867, 1987.
  * [7] H. Chen and J. Zhang.  Identification and adaptive control for systems with unknown orders, delay, and coefficients.  IEEE Transactions on Automatic Control, 35(8):866–877, 1990.
  * [8] A. Cohen, T. Koren, and Y. Mansour.  Learning linear-quadratic regulators efficiently with only $\sqrt{T}$ regret.  In International Conference on Machine Learning, pages 1300–1309. Proceedings of Machine Learning Research, 2019.
  * [9] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu.  Regret bounds for robust adaptive control of the linear quadratic regulator.  Advances in Neural Information Processing Systems, 31, 2018.
  * [10] M. Fazel, R. Ge, S. Kakade, and M. Mesbahi.  Global convergence of policy gradient methods for the linear quadratic regulator.  In International Conference on Machine Learning, pages 1467–1476. PMLR, 2018.
  * [11] C. Ju, G. Kotsalis, and G. Lan.  A model-free first-order method for linear quadratic regulator with $\tilde{O}(1/\varepsilon)$ sampling complexity, 2023.
  * [12] R. E. Kalman et al.  Contributions to the theory of optimal control.  Bol. Soc. Mat. Mexicana, 5(2):102–119, 1960.
  * [13] T. Lai and C. Wei.  Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems.  The Annals of Statistics, 10(1):154–166, 1982.
  * [14] B. Laurent and P. Massart.  Adaptive estimation of a quadratic functional by model selection.  The Annals of Statistics, 28(5):1302–1338, 2000.
  * [15] E. B. Lee and L. Markus.  Foundations of optimal control theory.  Wiley, New York, 1967.
  * [16] J. R. Leveque and L. N. Trefethen.  On the resolvent condition in the kreiss matrix theorem.  BIT Numerical Mathematics, 24:584–591, 1984.
  * [17] D. Malik, A. Pananjady, K. Bhatia, K. Khamaru, P. L. Bartlett, and M. J. Wainwright.  Derivative-free methods for policy optimization: Guarantees for linear quadratic systems.  Journal of Machine Learning Research, 21(21):1–51, 2020.
  * [18] H. Mania, S. Tu, and B. Recht.  Certainty equivalence is efficient for linear quadratic control.  In Advances in Neural Information Processing Systems, volume 32, 2019.
  * [19] H. Mohammadi, A. Zare, M. Soltanolkotabi, and M. R. Jovanović.  Convergence and sample complexity of gradient methods for the model-free linear–quadratic regulator problem.  IEEE Transactions on Automatic Control, 67(5):2435–2450, 2022.
  * [20] M. Simchowitz and D. Foster.  Naive exploration is optimal for online LQR.  In International Conference on Machine Learning, pages 8937–8948. Proceedings of Machine Learning Research, 2020.
  * [21] M. N. Spijker.  On a conjecture by le veque and trefethen related to the kreiss matrix theorem.  BIT Numerical Mathematics, 9:551–555, 1991.
  * [22] C. M. Stein.  Estimation of the mean of a multivariate normal distribution.  The Annals of Statistics, 9(6):1135–1151, 1981.
  * [23] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour.  Policy gradient methods for reinforcement learning with function approximation.  In Proceedings of the 12th International Conference on Neural Information Processing Systems, pages 1057–1063, 1999.
  * [24] R. J. Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Machine Learning, 8:229–256, 1992.
  * [25] Z. Yang, Y. Chen, M. Hong, and Z. Wang.  Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost.  In Neural Information Processing Systems, 2019.
  * [26] M. Zhou and J. Lu.  Single timescale actor-critic method to solve the linear quadratic regulator with convergence guarantees.  Journal of Machine Learning Research, 24(222):1–34, 2023.