# The Role of Identification in Data-driven Policy Iteration: A System
Theoretic Study

Bowen Song
Institute for Systems Theory and Automatic Control
University of Stuttgart
Stuttgart, Germany
<EMAIL_ADDRESS>
&Andrea Iannelli
Institute for Systems Theory and Automatic Control
University of Stuttgart
Stuttgart, Germany
<EMAIL_ADDRESS>

###### Abstract

The goal of this article is to study fundamental mechanisms behind so-called
indirect and direct data-driven control for unknown systems. Specifically, we
consider policy iteration applied to the linear quadratic regulator problem.
Two iterative procedures, where data collected from the system are repeatedly
used to compute new estimates of the desired optimal controller, are
considered. In indirect policy iteration, data are used to obtain an updated
model estimate through a recursive identification scheme, which is used in a
certainty-equivalent fashion to perform the classic policy iteration update.
By casting the concurrent model identification and control design as a
feedback interconnection between two algorithmic systems, we provide a closed-
loop analysis that shows convergence and robustness properties for arbitrary
levels of excitation in the data. In direct policy iteration, data are used to
approximate the value function and design the associated controller without
requiring the intermediate identification step. After proposing an extension
to a recently proposed scheme that overcomes potential identifiability issues,
we establish under which conditions this procedure is guaranteed to deliver
the optimal controller. Based on these analyses we are able to compare the
strengths and limitations of the two approaches, highlighting aspects such as
the required samples, convergence properties, and excitation requirement.
Simulations are also provided to illustrate the results.

_K_ eywords Data-driven Control $\cdot$ Policy Iteration $\cdot$ System
Identification $\cdot$ Robustness $\cdot$ Nonlinear Systems

##  1 Introduction

Data-driven control, which aims at providing control design approaches for all
those cases where a complete mathematical description of the system is not
available, is a very active research area [1, 2, 3, 4]. This has several
reasons, including the difficulty in modeling complex systems dominating
modern applications only relying on first-principles and the increasing
availability of data. This area comprises a vast body of works, differing for
problem settings, techniques, and control objectives. However, there are two
categories that fundamentally distinguish almost any proposed method, namely
indirect and direct approaches. In indirect data-driven control, data is
collected and used to learn an estimated model (and possibly its uncertainty),
which is then used in combination with classic model-based control
methodologies. On the other hand, direct data-driven control uses data to
design the controller directly, somehow avoiding the intermediate step of
identifying a model. Traditionally, the former has close connections with
system identification [5] and, when the controller changes during operation,
with indirect adaptive control [6]. Examples of the latter are instead model-
free reinforcement learning (RL) [7] and direct adaptive control [8].
Comparisons between these approaches to data-driven control have recently been
framed in the context of behavioral systems theory [9] and learning theory
[10]. Identifying the strengths and weaknesses of these approaches is a topic
of ongoing research in the community, and achieving a better understanding of
the fundamental differences requires looking at this from a different angle.

In this work, a system theoretic approach is employed to analyze the role of
the identified model, which represents the conceptual distinction between
direct and indirect methods, in establishing important properties such as
number of required samples, convergence rates, and robustness to the quality
of the data. For this we use the observation that iterative algorithms in
learning and optimization can be viewed as dynamical systems [11]. This
viewpoint has been used before for analysis of optimization algorithms using
robust control tools [12, 13] and the interconnections between a plant and an
algorithm [14, 15].

To be concrete, we select a prototypical problem setting that has received
strong interest across the control and RL community, namely policy iteration
(PI) for solving the linear quadratic regulator (LQR) problem. Policy
iteration is a dynamic programming algorithm for optimal control [16, 17] and
is still extensively studied [18, 19, 20, 21] as it is the backbone of many
approximate dynamic programming algorithms used in RL. PI involves two steps:
policy evaluation and policy improvement. In policy evaluation, the cost of a
given policy is computed, which is then leveraged in the second step to obtain
a new (better performing) policy. In its classic formulation, both steps
require knowledge of a model, and convergence can be ensured under assumptions
on cost and dynamics using monotonicity and contractivity properties of the
underlying operators[22]. As for LQR, this is a cornerstone optimal control
problem which is a very common setting to study data-driven algorithms [23,
20, 24, 10, 25, 26]. Relevant works for this study are [20], which
investigates the impact of addictive uncertainties in model-based PI for
continuous-time LQR problems, and [24], which proposes a direct data-driven
policy iteration for the case when system dynamics are unknown.

The paper analyzes the properties of indirect and direct policy iteration
methods to LQR for unknown systems. In both cases we consider online schemes
whereby controller updates take place concurrently with the generation of new
data from the system. In the indirect policy iteration (IPI) case, we consider
the interconnection of a recursive least squares (RLS) estimation algorithm
with a policy iteration scheme. The gain matrix is iteratively updated through
the PI steps applied to the model estimate provided by RLS from recursive
least squares which uses online data measured from the system. We leverage the
observation that this scheme can be seen as a (nonlinear) feedback
interconnection between two algorithmic systems and derive, without making a
priori assumptions on the level of excitation of the data, its closed-loop
response. We can use these results to establish under which conditions this
system converges to the desired values (optimal controller and true system’s
model) and, if not, we can provide a guaranteed upper bound on their distance.
We can capture analytically the lack of excitation in the data used by the
algorithm as a source of disturbance and we are thus able to provide an input-
to-state stability-type result that has an intuitive and useful in practice
interpretation. In the direct policy iteration (DPI) case, the PI steps are
parametrized by quantities that can be estimated directly via the data,
without explicit model identification. For this we build on a recently
developed on-policy (i.e. data are generated with the policy that is being
updated) direct policy iteration method [24] and modify it to address
identifiability issues arising in noise-free scenarios. On the basis of this
analysis, we thoroughly discuss: fundamental limitations of the schemes
compared to the case where a model is available; strengths and weaknesses of
the indirect and direct formulations; and point out clear advantages, at least
for this setting, of the indirect solution. These advantages can be summarized
as a better sample complexity (in the sense of number of required samples to
provide estimates with a guaranteed accuracy) and more robustness to lack of
excitation in the data. We reflect on the role played by the availability of
an estimated model.

The paper is organized as follows. Section 2 introduces the problem setting
and provides some preliminaries. Section 3 and Section 4 detail the
methodologies of the indirect policy iteration and direct policy iteration
approaches and analyze the convergence properties, respectively. Section 5
focuses on comparing the indirect and direct policy iteration approaches,
while Section 6 shows the effectiveness of two proposed policy iteration
methods and verifies the comparisons by simulations. Section 7 serves as a
concluding summary of the whole work.

### Notation

We denote by $A\succeq 0$ and $A\succ 0$ positive semidefinite and positive
definite matrix $A$, respectively. The symbol $\mathbb{S}^{n}_{+}$ denotes the
sets of real $n\times n$ symmetric and positive semidefinite matrices.
$\mathbb{Z}_{+}$ and $\mathbb{Z}_{++}$ are the sets of non-negative integers
and positive integers. Kronecker product is represented as $\otimes$ ,
$vec(A)=[a_{1}^{T},a_{2}^{T},...,a_{n}^{T}]^{T}$ stacks the columns of matrix
$A$ into a vector,
$vecv(v)=[v_{1}^{2},2v_{1}v_{2},...,2v_{1}v_{n},v_{2}^{2},...,2v_{2}v_{n},...,v_{n}^{2}]^{T}$
rearranges the entries of vector $v$ in this specific pattern,
$vecs(P)=[p_{11},...,p_{1n},p_{22},...,p_{2n},...,p_{nn}]^{T}$ stacks the
upper-triangular part of matrix $P\in\mathbb{S}^{n}_{+}$. For matrices,
$\lVert\cdot\rVert_{F}$, $\lVert\cdot\rVert_{2}$ and
$\lVert\cdot\rVert_{\infty}$ denote respectively their Frobenius norm, induced
$2$-norm and infinity norm. $I_{n}$ and $O_{n}$ are the identity matrix and
zero matrix with $n$ row/columns, respectively. The symbols $\lfloor x\rfloor$
and $\lceil x\rceil$ denote the floor function which returns the greatest
integer smaller or equal than $x\in\mathbb{R}$ and ceil function which returns
the smallest integer greater or equal than $x\in\mathbb{R}$, respectively. A
function belongs to class $\mathcal{K}$ if it is continuous, strictly
increasing, and vanishing at the origin. A function $\beta(x,t)$ is called
$\mathcal{KL}$ function if $\beta(x,t)$ decrease to 0 as $t\rightarrow 0$ for
every $x\geq 0$ and $\beta(\cdot,t)\in\mathcal{K}$ for all $t\geq 0$. A
sequence is denoted by $Y:=\\{Y_{t}\\}$ represents a map
$\mathbb{Z}_{+}\rightarrow\mathbb{R}^{n\times m}$. For a scalar sequence
($n=m=1$), we define its infinite norm as $\lVert
Y\rVert_{\infty}=\sup\limits_{t\in{\mathbb{Z}_{+}}}\\{Y_{t}\\}$. The symbols
$\lambda(A)$ and $\lambda_{i}(A)$ denote the set of eigenvalues and the
smallest $i$-th eigenvalue of the square matrix $A$, respectively.

##  2 Problem Setting and Preliminaries

We consider discrete-time linear time-invariant systems of the form

$x_{t+1}=Ax_{t}+Bu_{t},$ (1)

where $x_{t}\in\mathbb{R}^{n_{x}}$ is the system state,
$u_{t}\in\mathbb{R}^{n_{u}}$ is the control input and $t$ is the timestep. The
matrices $A\in\mathbb{R}^{n_{x}\times n_{x}}$ and $B\in\mathbb{R}^{n_{x}\times
n_{u}}$ are unknown, but we assume that the pair $(A,B)$ is stabilizable. This
is a standard assumption in data-driven control [10][24]. The objective is to
design a state-feedback controller $u_{t}=Kx_{t}$ that minimizes the following
infinite horizon cost:

$J(x_{t},K)=\sum\limits_{k=t}^{+\infty}r(x_{k},u_{k})=\sum\limits_{k=t}^{+\infty}x_{k}^{\top}Qx_{k}+u_{k}^{\top}Ru_{k},$
(2)

where $R\succ 0$ and $Q\succeq 0$. Because the dynamics (1) is linear and the
cost (2) is quadratic, this optimal control problem is referred to as an
infinite horizon linear quadratic regulator (LQR). Given a linear state-
feedback control that is stabilizing (i.e. $u_{t}=Kx_{t}$ and the matrix
$A+BK$ is Schur stable), the corresponding cost $J(x_{t},K)$ can be expressed
as $x_{t}^{\top}Px_{t}$, where $P\succ 0$ is also called the quadratic kernel
of the cost function associated with $K$ [24]. Starting from (2), $P$ can be
calculated by solving the following dynamic programming equation named value-
based Bellman equation:

$\underbrace{x_{t}^{\top}Px_{t}}_{J(x_{t},K)}=\underbrace{x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}}_{r(x_{t},u_{t})}+\underbrace{x_{t+1}^{\top}Px_{t+1}}_{J(x_{t+1},K)}.$
(3)

which does not depend on the system model, but only on the state response.
Using (1) in (3), the model-based Bellman equation reads:

$P=Q+K^{\top}RK+(A+BK)^{\top}P(A+BK)$ (4)

It is a well-known result from optimal control [27] that the optimal
controller solution to the LQR problem is a linear state-feedback, and the
optimal feedback gain $K^{*}$ is obtained via:

$\displaystyle K^{*}$ $\displaystyle=-(R+B^{\top}P^{*}B)^{-1}B^{\top}P^{*}A,$
(5a) $\displaystyle P^{*}$
$\displaystyle=Q+A^{\top}P^{*}A-A^{\top}P^{*}B(R+B^{\top}P^{*}B)^{-1}B^{\top}P^{*}A.$
(5b)

Here, $P^{*}$ is the quadratic kernel of the value function, i.e. of the cost
associated with the optimal gain $K^{*}$, and is the unique solution of the
discrete algebraic Riccati equation (DARE) (5b).

###  2.1 Model-based policy iteration

Even when the system’s model is available, solving (5b) directly is
challenging especially when dealing with a high number of system states.
Policy iteration offers an effective iterative approach to finding the optimal
gain $K^{*}$. The basic version of the policy iteration algorithm[28], which
requires knowledge of the system’s matrices $A$ and $B$, is summarized in
Algorithm 1.

Algorithm 1 Model-based policy iteration.

$A,B$, a stabilizing policy gain $K_{1}$

for $i=1,...,+\infty$ do

Policy Evaluation: find $P_{i}$

$P_{i}=Q+K_{i}^{\top}RK_{i}+(A+BK_{i})^{\top}P_{i}(A+BK_{i})$

Policy Improvement: update gain $K_{i+1}$

$K_{i+1}=-(R+B^{\top}P_{i}B)^{-1}B^{\top}P_{i}A$

end for

Algorithm 1 consists of two phases. In the policy evaluation phase, a
stabilizing policy gain $K_{i}$ is evaluated, i.e. its performance according
to the cost function (2) is calculated by computing the corresponding
quadratic kernel $P_{i}$ with the model-based Bellman equation (4). In the
policy improvement phase, a new gain $K_{i+1}$ is obtained by minimizing the
following cost:

$K_{i+1}=\mathop{\mathrm{arg~{}min}}\limits_{K}\underbrace{\left[x_{t}^{\top}Qx_{t}+(Kx_{t})^{\top}R(Kx_{t})+(Ax_{t}+BKx_{t})^{\top}P_{i}(Ax_{t}+BKx_{t})\right]}_{=:J_{\mathrm{PI}}(K)}.$
(6)

Equation (6) can be interpreted as treating $P_{i}$ as if it was the quadratic
kernel of the value function, and then minimizing the associated infinite
horizon cost $J_{\mathrm{PI}}(K)$. Indeed this optimization problem is
unconstrained and strictly convex because $R+B^{\top}P_{i}B\succ 0$. Thus, to
minimize ${J_{\mathrm{PI}}(K)}$ the first order derivative of (6) with respect
to $K$ should be $0$ for every $x_{t}$, yielding:

$\frac{\partial J_{\mathrm{PI}}(K)}{\partial
K}={\left(2\left(R+B^{\top}P_{i}B\right)K+2B^{\top}P_{i}A\right)}\left(x_{t}x_{t}^{\top}\right),$
(7)

and leads indeed to:

$\begin{split}2(R+&B^{\top}P_{i}B)K_{i+1}+2B^{\top}P_{i}A=0_{n_{u}}\Rightarrow
K_{i+1}=-(R+B^{\top}P_{i}B)^{-1}B^{\top}P_{i}A.\end{split}$ (8)

The properties of Algorithm 1 are summarized below.

###### Theorem 1

Properties of model-based PI 1[28]
If the system dynamics $(A,B)$ are controllable, then

  1. 1.

$P_{1}\succeq P_{2}\succeq...\succeq P^{*}$;

  2. 2.

$K_{i}$ stabilizes the system $(A,B)$, for all $i=1,2,...$;

  3. 3.

$\lim\limits_{i\rightarrow\infty}P_{i}=P^{*}$,
$\lim\limits_{i\rightarrow\infty}K_{i}=K^{*}$;

  4. 4.

Convergence rate of $P_{i}$ is given by $\lVert P_{i+1}-P^{*}\rVert_{F}\leq
C\lVert P_{i}-P^{*}\rVert^{2}_{F}$, where $C$ is a constant.

###### Remark 1

The controllability requirement in Theorem 1 can be relaxed to stabilizability
as per [29, Theorem 3].

###  2.2 Online parameter estimation with RLS

When the dynamics are unknown but linear, one can use linear regression to
identify the system’s model[5]. System (1) can be expressed as:

$x_{t+1}=Ax_{t}+Bu_{t}=\underbrace{\left[A,B\right]}_{\theta}\underbrace{\left[\begin{array}[]{cc}x_{t}\\\
u_{t}\end{array}\right]}_{d_{t}}.$ (9)

Given data $\\{d_{k},x_{k+1}\\}^{T}_{k=1}$ from a trajectory of length $T$, a
classic choice for estimating $\hat{\theta}$ is to minimize a least-squares
loss function[10, 25, 26]:

$\begin{split}\theta\in\mathop{\mathrm{arg~{}min}}\limits_{\hat{\theta}}\sum\limits_{k=1}^{T}(x_{k+1}-\hat{\theta}d_{k})^{\top}(x_{k+1}-\hat{\theta}d_{k}).\end{split}$
(10)

When $H_{T}:=\left(\sum\limits_{k=1}^{T}d_{k}d_{k}^{\top}\right)$ is
invertible, $\theta$ is estimated exactly via (10) as follows:

$\begin{split}\theta=\left(\sum\limits_{k=1}^{T}x_{k+1}d_{k}^{\top}\right)H_{T}^{-1}\end{split}$
(11)

This is also called batch least squares because the unknown is obtained in one
step using all the available data. In an online setting where data are not
available all at once but are collected progressively, one can opt for the
recursive least squares (RLS) algorithm [6] which updates the estimate
iteratively based on new measured information. Define
$\theta_{0}:=[\hat{A}_{0},\hat{B}_{0}]$ the initialization of system dynamics
and $\theta_{t}:=[\hat{A}_{t},\hat{B}_{t}]$ the estimates at time $t$ of the
estimation process. In RLS the new estimate $\theta_{t}$ based on the new
trajectory $\\{d_{t},x_{t+1}\\}$ and previous estimates $\theta_{t-1}$ is
obtained in analogy to (11) as:

$\begin{split}\theta_{t}&=\left(\sum\limits_{k=1}^{t}x_{k+1}d_{k}^{\top}\right)H_{t}^{-1}\\\
&=\left(\sum\limits_{k=1}^{t-1}x_{k+1}d_{k}^{\top}+x_{t+1}d_{t}\right)H_{t}^{-1}\\\
&=\left(\theta_{t-1}H_{t-1}+x_{t+1}d_{t}\right)H_{t}^{-1}\\\
&=\left(\theta_{t-1}(H_{t}-d_{t}d_{t}^{\top})+x_{t+1}d_{t}\right)H_{t}^{-1}\\\
&=\theta_{t-1}+(x_{t+1}-\theta_{t-1}d_{t})d^{\top}_{t}H_{t}^{-1}.\end{split}$
(12)

where $H_{t}$ has also a recursive update rule:

$H_{t}=H_{t-1}+d_{t}d_{t}^{\top},$ (13)

and $H_{0}\succ 0$ is an initialized matrix guaranteeing invertibility of
$H_{t}$ at all $t$. As we will see shortly, the convergence of the RLS
algorithm is governed by properties of the sequence $\\{d_{t}d_{t}^{\top}\\}$.

The RLS scheme is summarized in Algorithm 2.

Algorithm 2 Recursive Least Squares.

an initialized estimated system dynamic $\theta_{0}$ and positive definite
matrix $H_{0}$

for $t=1,...,\infty$ do

Given $\\{x_{t+1},d_{t}\\}$

$H_{t}=H_{t-1}+d_{t}d_{t}^{\top}$

$\theta_{t}=\theta_{t-1}+(x_{t+1}-\theta_{t-1}d_{t})d^{\top}_{t}H_{t}^{-1}$

end for

###### Remark 2

In practice, one never inverts $H_{t}$ in (12). For example, by using Sherman-
Morrison formula [30], $H_{t}^{-1}$ can be recursively updated as:

$H_{t}^{-1}=(H_{t-1}+d_{t-1}d_{t-1}^{\top})^{-1}=H_{t-1}^{-1}-\frac{H_{t-1}^{-1}d_{t-1}d^{\top}_{t-1}H_{t-1}^{-1}}{1+d^{\top}_{t-1}H_{t-1}^{-1}d_{t-1}},$
(14)

which only requires matrix multiplications between $H_{t-1}^{-1}$ and
$d_{t-1}$.

The estimation error $\Delta\theta_{t}:=\theta_{t}-\theta$ at time index $t$
is given as:

$\displaystyle\Delta\theta_{t}=\Delta\theta_{t-1}\left(I_{n_{x}}-d_{t}d^{\top}_{t}H_{t}^{-1}\right)=\Delta\theta_{t-1}H_{t-1}H_{t}^{-1}=\Delta\theta_{0}H_{0}H_{t}^{-1}.$
(15)

From (15), an upper bound of $\lVert\Delta\theta_{t}\rVert_{F}$ is given as
follows:

$\lVert\Delta\theta_{t}\rVert_{F}\leq\lVert\Delta\theta_{0}H_{0}\rVert_{F}\lVert
H_{t}^{-1}\rVert_{F}=:\Delta\theta_{t}^{\mathrm{Upper}},$ (16)

where $\\{\Delta\theta^{\mathrm{Upper}}_{t}\\}$ is a well-defined sequence
because the inverse of $H_{t}$ always exists.

To characterize the convergence of the RLS estimation error, we introduce the
following properties of sequences.

###### Definition 1

(Global persistency[31])
A sequence $\\{Y_{t}\\}\in\mathbb{S}^{n}_{+}$ is (globally) persistent if
there exist $N\geq 1$ and $\alpha>0$ such that, for all $j\geq 0$,

$\sum\limits_{i=0}^{N-1}Y_{i+j}\succeq\alpha I_{n}.$ (17)

The numbers $\alpha$ and $N$ are respectively the lower bound and persistency
window of $\\{Y_{t}\\}$.
If $Y_{t}$ is not symmetric, then we use the convention that
$\\{Y_{t}\\}\in\mathbb{R}^{n\times m}$ is (globally) persistent if
$\\{Y_{t}Y_{t}^{\top}\\}$ is (globally) persistent.

###### Definition 2

(Local persistency)
A sequence $\\{Y_{t}\\}\in\mathbb{S}^{n}_{+}$ is locally persistent if there
exist $N\geq 1,M\geq 1$ and $\alpha>0$ such that , for all $j=Mk+1$ where
$k\in\mathbb{Z}_{+}$,

$\sum\limits_{i=0}^{N-1}Y_{i+j}\succeq\alpha I_{n}.$ (18)

The numbers $\alpha$ and $N$ are respectively, the lower bound and persistency
window of $\\{Y_{t}\\}$. $M$ is the persistency interval. As before,
$\\{Y_{t}\\}\in\mathbb{R}^{n\times m}$ is locally persistent if
$(Y_{t}Y_{t}^{\top})$ is locally persistent.

Whereas Definition 1 is classic in the adaptive control literature [6], to the
best of the authors’ knowledge, Definition 2 has not been proposed so far and
is a weaker requirement that will prove useful for the coming results. The
difference between global and local persistency is that inequality (17) must
hold for all $j$, whereas (18) must only hold on a subset of indices. If a
sequence is globally persistent with respect to window $N$, then it is also
locally persistent with respect to the same window $N$ and $M=1$. The reverse
is not true. For example, the following periodic scalar sequence
$\\{1,0,0,1,1,0,0,1,...,\\}$ is locally persistent with $N=2$ and $M=2$ but
not globally persistent with $N=2$.

It turns out that local persistency is sufficient to show convergence of the
RLS estimate.

###### Theorem 2

If the sequence $\\{d_{t}\\}$ is locally persistent with respect to any lower
bound $\alpha>0$, any persistency window $N\in\mathbb{Z}_{++}$ and
$M\in\mathbb{Z}_{++}$, then RLS satisfies
$\lim\limits_{t\rightarrow+\infty}\Delta\theta_{t}^{\mathrm{Upper}}=0$ and
thus $\lim\limits_{t\rightarrow+\infty}\theta_{t}=\theta$.

The proof of Theorem 2 can be found in Appendix A.2.

##  3 Indirect Data-driven Policy Iteration

In this section, we analyze the indirect data-driven policy iteration (IPI),
which combines the model-based policy iteration introduced in Algorithm 1 with
the RLS Algorithm 2. The proposed algorithm is a possible solution to perform
PI in the case of unknown system dynamics by performing concurrently policy
optimization and online system identification. Even though IPI is a
straightforward combination of two standard methods, our primary focus is
analyzing its convergence properties and limitations from a system theoretic
viewpoint.

###  3.1 Algorithm definition

First, we introduce the structure of the algorithm, for which it is beneficial
to use two sets of indices: one referring to _episodes_ (denoted by $i$) and
the other to the conventional timesteps $t$. An episode is characterized by a
collection of data $d_{t}$ from a start timestep to an end timestep. In IPI,
the $i$-th episode is associated with the finite length sequence $\\{d_{t}\\}$
from time index $(i-1)\tau_{\mathrm{IPI}}+1$ to time index
$i\tau_{\mathrm{IPI}}$, where $\tau_{\mathrm{IPI}}$ denotes the length of an
episode. This is graphically illustrated in Figure 1.

Figure 1: Illustration of episode indices $i$ and time indices $t$.

###### Remark 3

The reason to use this double index is that PI variables
($\hat{K}_{i},\hat{P}_{i}$) and the RLS variables $(\hat{A}_{i},\hat{B}_{i})$
are updated after each episode $i$. However, the latter updates depend on data
indexed by the timestep $t$ collected within each episode from time index
$(i-1)\tau_{\mathrm{IPI}}+1$ to time index $i\tau_{\mathrm{IPI}}$.

At a generic episode $i\geq 1$, the procedure of IPI involves the following
steps:

  * •

Given a stabilizing policy gain $\hat{K}_{i}$, which originates from the
initialization $(i=0)$ or the previous episode, the evaluation step yielding
$\hat{P}_{i}$ is done by solving the model-based Bellman equation (4) using
the available estimate $(\hat{A}_{i-1},\hat{B}_{i-1})$:

$\hat{P}_{i}=Q+\hat{K}_{i}^{\top}R\hat{K}_{i}+(\hat{A}_{i-1}+\hat{B}_{i-1}\hat{K}_{i})^{\top}\hat{P}_{i}(\hat{A}_{i-1}+\hat{B}_{i-1}\hat{K}_{i}).$
(19)

  * •

The plant is excited with $u_{t}=\hat{K}_{i}x_{t}+e_{t}$, where $e_{t}$ is a
potentially non-zero feedforward term, e.g. a dithering signal introduced for
excitation purposes. The $\tau_{\mathrm{IPI}}$ data points collected from
timestep $(i-1)\tau_{\mathrm{IPI}}+1$ to $i\tau_{\mathrm{IPI}}$ are then
utilized to recursively update the estimates of $(\hat{A}_{i},\hat{B}_{i})$
through the RLS Algorithm:

$\displaystyle H_{i}$
$\displaystyle=H_{i-1}+\left(\sum\limits_{t=(i-1)\tau_{\mathrm{IPI}}+1}^{i\tau_{\mathrm{IPI}}}d_{t}d_{t}^{\top}\right),$
(20a) $\displaystyle\theta_{i}$
$\displaystyle=\left(\theta_{i-1}H_{i-1}+\sum\limits_{t=(i-1)\tau_{\mathrm{IPI}}+1}^{i\tau_{\mathrm{IPI}}}x_{t+1}d_{t}^{\top}\right)H_{i}^{-1}.$
(20b)

  * •

The policy is improved using the updated estimate $(\hat{A}_{i},\hat{B}_{i})$:

$\hat{K}_{i+1}=-(R+\hat{B}_{i}^{\top}\hat{P}_{i}\hat{B}_{i})^{-1}\hat{B}_{i}^{\top}\hat{P}_{i}\hat{A}_{i}.$
(21)

The choice of the excitation policy, which can be different than the one
suggested here and does not even have to be _on-policy_ , as well as the
impact of parameter $\tau_{\mathrm{IPI}}$, will be discussed in detail in
Section 5.2 as part of the comparison with the direct counterpart.

###### Remark 4

The term $e_{t}$ represents an additional degree of freedom of the online
policy, which could be used for example as an exploratory signal normally or
uniformly distributed, or made a function of $\hat{P}_{i}$ or $H_{i}$ for
active learning purposes. We not here however that the subsequent analysis are
agnostic to the choice of $e_{t}$ and remain valid also for the case
$e_{t}=0$. More in general, the choice of the input $u_{t}$, which can be
different than the one suggested here, as well as the impact of parameter
$\tau_{\mathrm{IPI}}$, will be discussed in detail in Section 5.2 as part of
the comparison with the direct counterpart.

The IPI algorithm is graphically illustrated in Figure 2 and summarized in
Algorithm 3.

Figure 2: Concurrent identification and policy iteration scheme. Algorithm 3
Indirect data-driven policy iteration.

$\hat{A}_{0},\hat{B}_{0},H_{0}$, the initial stabilizing policy gain
$\hat{K}_{1}$

for $i=1,...,\infty$ do (episode counter)

Policy Evaluation: find $\hat{P}_{i}$

$\hat{P}_{i}=Q+\hat{K}_{i}^{\top}R\hat{K}_{i}+(\hat{A}_{i-1}+\hat{B}_{i-1}\hat{K}_{i})^{\top}\hat{P}_{i}(\hat{A}_{i-1}+\hat{B}_{i-1}\hat{K}_{i})$

for $j=1,...,\tau_{\mathrm{IPI}}$ do (timestep counter inside episode $i$)

Excite the system with
$u_{\tau_{\mathrm{IPI}}(i-1)+j}=\hat{K}_{i}x_{\tau_{\mathrm{IPI}}(i-1)+j}+e_{\tau_{\mathrm{IPI}}(i-1)+j}$

Collect the data
$\leftarrow(x_{\tau_{\mathrm{IPI}}(i-1)+j},u_{\tau_{\mathrm{IPI}}(i-1)+j},x_{\tau_{\mathrm{IPI}}(i-1)+j+1})$

Use RLS in Algorithm 3 to update $A_{temp},B_{temp},H_{temp}\leftarrow
A_{temp},B_{temp},H_{temp},\mathrm{\textbf{data}}$

end for

$\hat{A}_{i},\hat{B}_{i},H_{i}\leftarrow A_{temp},B_{temp},H_{temp}$

Policy Improvement: update gain $\hat{K}_{i+1}$

$\hat{K}_{i+1}=-(R+\hat{B}_{i}^{\top}\hat{P}_{i}\hat{B}_{i})^{-1}\hat{B}_{i}^{\top}\hat{P}_{i}\hat{A}_{i}$

end for

###  3.2 Closed-loop analysis

As suggested by the representation in Figure 2, we study policy iteration and
recursive least-squares as a feedback interconnection of two coupled dynamical
systems. In the "system PI", the inputs are the estimates
$(\hat{A}_{i},\hat{B}_{i})$ obtained from the RLS, and the dynamics are
described by (21) and (19). In the "system RLS", the inputs are the data
$\\{d_{t}\\}$ and $\\{x_{t+1}\\}$ collected online in an episode, and the
dynamics are described by (20a) and (20b).

We first analyze separately the two building blocks RLS (Section 3.2.2) and PI
(Section 3.2.3), and then provide the main results in Section 3.2.4. Before
proceeding with these analyses, we introduce in Section 3.2.1 new properties
of (data) sequences that are convenient for the analysis of online algorithms
when we cannot assume a priori that the properties of global or local
persistence hold.

####  3.2.1 Properties of general sequences

For the sake of this abstract discussion on sequences properties, we refer in
the reminder to a generic sequence $\\{S_{i}\\}\in\mathbb{S}^{n}_{+}$.

###### Definition 3

(Minimum persistency window length $N^{\mathrm{PW}}_{i}$ and lower bound
$\alpha_{i}^{\mathrm{PW}}$)
Given a sequence $\\{S_{i}\\}\in\mathbb{S}^{n}_{+}$, we define the minimum
persistency window length $N^{\mathrm{PW}}_{i}\in\mathbb{Z}_{+}$ and its
associated lower bound $\alpha_{i}^{\mathrm{PW}}\in\mathbb{R}_{+}$ at index
$i$ as the two variables uniquely defined by these two conditions:

  * •

the matrix $\sum\limits_{k=i}^{i+N^{\mathrm{PW}}_{i}-1}S_{k}$ is full rank,
i.e.
$\lambda_{1}\left(\sum\limits_{k=i}^{i+N^{\mathrm{PW}}_{i}-1}S_{k}\right)=:\alpha_{i}^{\mathrm{PW}}>0$,

  * •

the matrix $\sum\limits_{k=i}^{i+N^{\mathrm{PW}}_{i}-2}S_{k}$ is singular,
i.e.
$\lambda_{1}\left(\sum\limits_{k=i}^{i+N^{\mathrm{PW}}_{i}-2}S_{k}\right)=0$.

If the sequence is not locally persistent, there are indices $i$ for which
$N^{\mathrm{PW}}_{i}$ and $\alpha_{i}^{\mathrm{PW}}$ are not defined. In such
cases, our convention is to set $N^{\mathrm{PW}}_{i}=0$ and
$\alpha_{i}^{\mathrm{PW}}=+\infty$.

Building on this notion, we define the largest persistency window length
$\bar{N}$ and the smallest persistency window bound $\underline{\alpha}$ for a
generic sequence $\\{S_{i}\\}$.

###### Definition 4

(Largest persistency window length $\bar{N}$ and smallest lower bound
$\underline{\alpha}$)
Given a sequence $\\{S_{i}\\}\in\mathbb{S}^{n}_{+}$, we construct two
sequences $N^{PW}=\\{N^{PW}_{i}\\}$ and $\alpha^{PW}=\\{\alpha^{PW}_{i}\\}$,
whose entries are the minimum persistency window length $N^{\mathrm{PW}}_{i}$
and the persistency window lower bound $\alpha_{i}^{\mathrm{PW}}$ with respect
to the sequence $\\{S_{i}\\}$. The largest persistency window length and the
smallest lower bound are then defined as
$\bar{N}:=\sup\\{N^{\mathrm{PW}}_{i}\\}$ and
$\underline{\alpha}:=\inf\\{\alpha_{i}^{\mathrm{PW}}\\}$

We then introduce an auxiliary locally persistent sequence associated with a
generic sequence $\\{S_{i}\\}$ and defined by $N=N_{\max}$, $M=N_{\max}$ and
$\alpha=\alpha_{\min}$ (recall Definition 2), where
$N_{\max}\in[\bar{N},\infty)$ and $N_{\max}\neq 0$,
$\alpha_{\min}\in(0,\underline{\alpha}]$ and $\alpha_{\min}\neq+\infty$. This
sequence is shown as the green line in Figure 3. We define next the sequence
of non-persistent eigenvalues associated with $\\{S_{i}\\}$, which is a useful
measure of the difference between $\\{S_{i}\\}$ and its associated auxiliary
locally persistent sequence.

###### Definition 5

(Number of non-persistent eigenvalues $\\{j^{\mathrm{non}}_{i}\\}$ of a
sequence $\\{S_{i}\\}$)
Given a generic sequence $\\{S_{i}\\}\in\mathbb{S}^{n}_{+}$ and the associated
auxiliary locally persistent sequence defined by $N=N_{\max}$, $M=N_{\max}$
and $\alpha=\alpha_{\min}$. We can define the sequence of number of non-
persistent eigenvalues $\\{j^{\mathrm{non}}_{i}\\}$ with entries defined by:

$\begin{split}j^{\mathrm{non}}_{i}=\max\limits_{j\in\\{1,...,n\\}}~{}j&\\\
s.t.~{}\lfloor\frac{i}{N_{\max}}\rfloor\alpha_{\min}-&\lambda_{j}\left(\sum\limits_{k=1}^{i}S_{k}\right)>0.\end{split}$
(22)

Each entry $j_{i}^{\mathrm{non}}$ can be interpreted as the number of
eigenvalues of $\sum\limits_{k=1}^{i}S_{k}$ which are upper-bounded by
$\lfloor\frac{i}{N_{\max}}\rfloor\alpha_{\min}$, hence the name. When problem
(22) is infeasible, our convention is to set $j^{\mathrm{non}}_{i}=0$.

Figure 3: Graphical representation of sequence properties.

A couple of interesting observations are in order. When $\\{S_{i}\\}$ is
locally persistent with respect to $N=N_{\max}$, $M=N_{\max}$ and
$\alpha=\alpha_{\min}$, then it follows exactly that for all $i$,
$\lambda_{1}\left(\sum\limits_{k=1}^{i}S_{k}\right)\geq\lfloor\frac{i}{N_{\max}}\rfloor\alpha_{\min}$
and thus problem (22) has no solution. Therefore, for locally persistent
sequences we have $j^{\mathrm{non}}_{i}=0$ for all $i\in\mathbb{Z}_{+}$. If a
sequence is non-persistent, then there exists $i\in\mathbb{Z}_{+}$ such that
$j^{\mathrm{non}}_{i}\neq 0$. This explains why, as mentioned earlier, we can
use this notion to quantify the difference between $\\{S_{i}\\}$ and its
associated auxiliary locally persistent sequence.

####  3.2.2 RLS analysis with a generic data sequence in the episodic setting

Standard convergence analysis of RLS assumes that the data sequence is
globally [31] or, as in Theorem 2, locally persistent. In this section, we
study the properties of RLS applied to a generic data sequence by leveraging
the definitions introduced in Section 3.2.1. To analyze RLS across episode
$i$, it is convenient to define the sequence $\\{D_{i}\\}$ with entries
$D_{i}$ given by:

$D_{i}:=\sum\limits_{j=(i-1)\tau_{\mathrm{IPI}}+1}^{i\tau_{\mathrm{IPI}}}d_{j}d_{j}^{\top}.$
(23)

The main result can then be stated as follows.

###### Theorem 3

Given the sequence $\\{D_{i}\\}\in\mathbb{S}^{(n_{x}+n_{u})}_{+}$ with entries
defined in (23), the estimation error of the recursive least squares
initialized with $\theta_{0}$ and $H_{0}=aI,a>0$ is bounded by:

$\begin{split}\lVert\theta_{i}-\theta\rVert_{F}\leq\Delta\theta^{\mathrm{Upper}}_{i}\leq
f\left(\lVert\theta_{0}-\theta\rVert_{F},i\right)+g\left(\lVert
j^{\mathrm{non}}\rVert_{\infty}\right),\end{split}$ (24)

where:
$f\left(\lVert\theta_{0}-\theta\rVert_{F},i\right):=a(n_{x}+n_{u})\frac{\lVert\theta_{0}-\theta\rVert_{F}}{a+\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}}$
and $g\left(\lVert
j^{\mathrm{non}}\rVert_{\infty}\right):=\lVert\Delta\theta_{0}\rVert_{F}\lVert
j^{\mathrm{non}}\rVert_{\infty}$; $\alpha_{\min}$ and $N_{\max}$ are
parameters associated with the auxiliary locally persistent sequence of
$\\{D_{i}\\}$; and $\\{j^{\mathrm{non}}_{i}\\}$ is the associated sequence
(see Definition 5).

The proof of Theorem 3 can be found in Appendix B.1. This result recovers
Theorem 2 when its conditions hold.

###### Corollary 1

If the data sequence $\\{d_{t}\\}$ is locally persistent with respect to any
persistency window $N_{d_{t}}$, persistency interval $M_{d_{t}}$ and lower
bound $\alpha_{d_{t}}$, for any positive integer
$\tau_{\mathrm{IPI}}\in\mathbb{Z}_{++}$, then
$\mathop{lim}\limits_{i\rightarrow\infty}\lVert\theta_{i}-\theta\rVert_{F}=0$
and thus
$\mathop{lim}\limits_{i\rightarrow\infty}\Delta\theta^{\mathrm{Upper}}_{i}=0$.

###### Proof 1

From Theorem 3, we know that if the sequence $\\{d_{t}\\}$ is locally
persistent as defined in Definition 2, then the sequence $\\{D_{i}\\}$ is also
locally persistent with respect to persistency window length
$M_{d_{t}}\lceil\frac{N_{d_{t}}}{M_{d_{t}}}\rceil$, persistency window
interval $M_{d_{t}}\lceil\frac{N_{d_{t}}}{M_{d_{t}}}\rceil$and
$\alpha_{d_{t}}\tau_{\mathrm{IPI}}$. As a result, $j_{i}^{\mathrm{non}}=0$ and
thus the estimation error asymptotically converges to 0.

When $\\{d_{t}\\}$ is not locally persistent, then Theorem 3 provides an upper
bound for the estimation error which can be computed based on the properties
of $\\{D_{i}\\}$ and its auxialiary sequence.

We finally remark that Theorem 2 stated the convergence of RLS with respect to
the time index $t$, while Corollary 1 emphasizes the convergence of RLS with
respect to the episode index $i$, which is relevant to the IPI setting. There
is no conceptual difference between the two, as clear from the proof of
Corollary 1. In particular, it is important to observe that convergence is
guaranteed for any selection of $\tau_{\mathrm{IPI}}$.

####  3.2.3 PI analysis with nominal system

In a similar decoupling spirit, and as an introduction to the main result
covered in the next section, we study here the convergence of policy iteration
applied to the true system $(A,B)$.

Let $\alpha(P_{i}):=B^{\top}P_{i}A$ and $\beta(P_{i}):=R+B^{\top}P_{i}B$
(where $\beta(P_{i})$ is a positive definite matrix and thus is always
invertible). Inserting the equation of policy improvement step (4) into the
policy evaluation step (8), the equation between $P_{i}$ and $P_{i+1}$
formulated by $A,B,Q,R$ reads:

$\displaystyle P_{i+1}$
$\displaystyle=Q+A^{\top}P_{i+1}A+\alpha^{\top}(P_{i})\beta^{-1}(P_{i})\beta(P_{i+1})\beta^{-1}(P_{i})\alpha(P_{i})$
(25)
$\displaystyle-\alpha^{\top}(P_{i+1})\beta^{-1}(P_{i})\alpha(P_{i})-\alpha^{\top}(P_{i})\beta^{-1}(P_{i})\alpha(P_{i+1}).$

Using $vec(EFG)=(F^{\top}\otimes E)vec(G)$ from [30], we can rewrite (25) as:

$\displaystyle\underbrace{[I_{n_{x}}\otimes
I_{n_{x}}-(A^{\top}-\alpha^{\top}(P_{i})\beta^{-1}(P_{i})B^{\top})\otimes(A^{\top}-\alpha^{\top}(P_{i})\beta^{-1}(P_{i})B^{\top})]}_{=:\mathcal{A}(P_{i})}vec(P_{i+1})$
(26)
$\displaystyle=vec(Q+\alpha^{\top}(P_{i})\beta^{-1}(P_{i})R\beta^{-1}(P_{i})\alpha(P_{i})).$

If $\mathcal{A}(P_{i})$ is invertible, we can define an operator
$\mathcal{L}^{-1}_{(A,B,P_{i})}$ that connects $P_{i}$ and $P_{i+1}$ with
system matrix $(A,B)$ from (26):

$P_{i+1}=\mathcal{L}^{-1}_{(A,B,P_{i})}(Q+\alpha^{\top}(P_{i})\beta^{-1}(P_{i})R\beta^{-1}(P_{i})\alpha(P_{i})).$
(27)

By connecting Theorem 1 and (26), we develop the following theorem:

###### Theorem 4

Given a stabilizable system $(A,B)$ and $P_{0}\succeq P^{*}$ as the initial
condition, for any $P_{i}$ which is recursively computed from $P_{i-1}$ using
(26) with $i\in\mathbb{Z}_{++}$, $\mathcal{A}(P_{i})$ is always invertible and
there always exists a constant $c\in(0,1)$, such that:

$\lVert P_{i+1}-P^{*}\rVert_{F}\leq c\lVert P_{i}-P^{*}\rVert_{F}.$ (28)

The proof of Theorem 4 is given in Appendix C.1. Whereas convergence of PI in
this setting is a well-known result, Theorem 4 shows in addition that $P_{i}$
converges exponentially to $P^{*}$ when initialized as in the statement. A
similar result was recently shown in [19], but we use here a different norm
and proof technique, so this result can be considered novel and of independent
interest.

####  3.2.4 Convergence analysis of IPI

We are now at the stage of analyzing the convergence properties of the
interconnection in Figure 4 between the RLS and PI systems, studied
independently in the previous Sections.

Figure 4: Convergence analysis of coupled dynamical systems.

Before stating the main result, we introduce two assumptions.

###### Assumption 1

The estimates $(\hat{A}_{i},\hat{B}_{i})$ obtained from RLS are stabilizable
$\forall i\in\mathbb{Z}_{+}$.

We note that the employed RLS scheme does not provide any a priori guarantee
on the satisfaction of this assumption. However, this condition can be checked
before using the estimated model in the PI routine, and thus in practice,
whenever this condition is violated, the system is excited and RLS is applied
until a stabilizable estimate is obtained. Because the true system $(A,B)$ is
stabilizable, under the assumption of a locally persistent data sequence, we
can also prove the existence of an index $i_{\mathrm{st}}$ such that
$(\hat{A}_{i},\hat{B}_{i})$ obtained from RLS is stabilizable for all $i\geq
i_{\mathrm{st}}$. This is formally stated next.

###### Theorem 5

For any initialization $(\hat{A}_{0},\hat{B}_{0})$ and stabilizable pair
$(A,B)$, given a locally persistent sequence $\\{D_{i}\\}$ with respect to any
lower bound $\alpha>0$, any persistency window $N\in\mathbb{Z}_{++}$ and
$M\in\mathbb{Z}_{++}$, there always exists an index $i_{\mathrm{st}}$ such
that $\forall i\geq i_{\mathrm{st}}$, the estimate obtained from RLS
$(\hat{A}_{i},\hat{B}_{i})$, is stabilizable.

The proof of Theorem 5 is given in Appendix D.1. This theorem ensures that
there always exists an $i_{\mathrm{st}}$ such that after $i_{\mathrm{st}}$,
Assumption 1 is always satisfied.

###### Assumption 2

Given a stabilizable estimate $(\hat{A}_{i},\hat{B}_{i})$, we assume that
$\hat{P}_{i}\succeq P^{*}_{(\hat{A}_{i},\hat{B}_{i})}$ $\forall
i\in\mathbb{Z}_{+}$, where $\hat{P}_{i}$ is obtained via (19) and
$P^{*}_{(\hat{A}_{i},\hat{B}_{i})}$ is the quadratic kernel of the value
function associated with $(\hat{A}_{i},\hat{B}_{i})$ and is calculated by
solving (5b).

Assumption 2 guarantees that item 1 and item 2 in Theorem 1 hold, which is
convenient for the subsequent analysis. Moreover, if $\hat{P}_{i}\succeq
P^{*}_{(\hat{A}_{i},\hat{B}_{i})}$ and we iteratively refine $\hat{P}_{i}$ via
Algorithm 1 using $(\hat{A}_{i},\hat{B}_{i})$, then $\hat{P}_{i}$ converges
exponentially to $P^{*}_{(\hat{A}_{i},\hat{B}_{i})}$. On the contrary, if
$\hat{P}_{i}\nsucceq P^{*}_{(\hat{A}_{i},\hat{B}_{i})}$, there are no
guarantees that $\hat{K}_{i}$ stabilizes $(\hat{A}_{i},\hat{B}_{i})$ and the
subsequent policy evaluation might be infeasible. In practice, one only needs
to have that $\hat{K}_{i}$ stabilizes the associated estimate, and this can be
checked directly. Heuristics to achieve Assumption 2 include again choosing
$\tau_{\mathrm{IPI}}$ sufficiently large, or re-initializing $\hat{K}_{i}$
with a gain that stabilizes the current estimated system dynamic
$(\hat{A}_{i},\hat{B}_{i})$. Relaxing this requirement with tighter sufficient
conditions is left for future work.

We state next the main result of the section.

###### Theorem 6

Consider the coupled recursive least squares and policy iteration system with
non-minimum state representation:

$\displaystyle\hat{P}_{i}$
$\displaystyle=Q+\hat{K}_{i}^{\top}R\hat{K}_{i}+(\hat{A}_{i-1}+\hat{B}_{i-1}\hat{K}_{i})^{\top}\hat{P}_{i}(\hat{A}_{i-1}+\hat{B}_{i-1}\hat{K}_{i}),$
(29a) $\displaystyle H_{i}$
$\displaystyle=H_{i-1}+\left(\sum\limits_{t=(i-1)\tau_{\mathrm{IPI}}+1}^{i\tau_{\mathrm{IPI}}}d_{t}d_{t}^{\top}\right),$
(29b) $\displaystyle\theta_{i}$
$\displaystyle=\left(\theta_{i-1}H_{i-1}+\sum\limits_{t=(i-1)\tau_{\mathrm{IPI}}+1}^{i\tau_{\mathrm{IPI}}}x_{t+1}d_{t}^{\top}\right)H_{i}^{-1},$
(29c) $\displaystyle\hat{K}_{i+1}$
$\displaystyle=-(R+\hat{B}_{i}^{\top}\hat{P}_{i}\hat{B}_{i})^{-1}\hat{B}_{i}^{\top}\hat{P}_{i}\hat{A}_{i}.$
(29d)

If Assumption 1 and Assumption 2 are satisfied, then for any positive integer
$\tau_{\mathrm{IPI}}\in\mathbb{Z}_{++}$ the estimate $\hat{P}_{i}$ and
$\theta_{i}$ satisfy the following relationships:

$\displaystyle\lVert\hat{P}_{i}-P^{*}\rVert_{F}$
$\displaystyle\leq\beta\left(\lVert\hat{P}_{0}-P^{*}\rVert_{F},i\right)+\gamma\left(\lVert\Omega\rVert_{\infty}\right),$
(30a) $\displaystyle\lVert\theta_{i}-\theta\rVert_{F}$
$\displaystyle\leq\Delta\theta^{\mathrm{Upper}}_{i}\leq
f\left(\lVert\theta_{0}-\theta\rVert_{F},i\right)+g\left(\lVert
j^{\mathrm{non}}\rVert_{\infty}\right).$ (30b)

where: $\beta\left(\cdot,\cdot\right):=c^{i}\lVert\hat{P}^{0}-P^{*}\rVert_{F}$
is a $\mathcal{KL}$ function with $c\in(0,1)$;
$\gamma\left(\lVert\Omega\rVert_{\infty}\right):=\frac{1}{1-c}\lVert\Omega\rVert_{\infty}$
is a $\mathcal{K}$ function; $\Omega$ is a scalar sequence with
$\Omega_{i}:=\sigma_{i}\Delta\theta^{\mathrm{Upper}}_{i}$ and
$\sigma_{i}:=\sum\limits_{k=0}^{8}\rho_{k}(\Delta\theta^{\mathrm{Upper}}_{i})^{k}$;
and the detailed expressions of $\rho_{k}>0$ are provided in Appendix D.2. The
functions $f(\cdot)$ and $g(\cdot)$ are given in Theorem 3.

The proof of Theorem 6 can be found in Appendix D.2.

###### Remark 5

(ISS-type interpretation of (30) in Theorem 6)
A few comments are given in order to better interpret the result of Theorem 6.
For this, we would like to briefly recall input-to-state stability (ISS),
which is a notion of stability widely employed to analyze the stability of
nonlinear systems subject to external disturbances [32] [33]. Given a
nonlinear system $y_{t+1}=f(y_{t},w_{t})$, the system is said to be input to
state stable if there exist $\beta_{\mathrm{ISS}}\in\mathcal{KL}$ and
$\gamma_{\mathrm{ISS}}\in\mathcal{K}$ such that

$\lVert y_{t}\rVert\leq\beta_{\mathrm{ISS}}\left(\lVert
y_{0}\rVert,t\right)+\gamma_{\mathrm{ISS}}\left(\lVert
w\rVert_{\infty}\right).$ (31)

As can be seen from the equation above, if a system is ISS, then it is
globally asymptotically stable in the absence of external inputs and its state
is bounded by a function of the size of the external inputs.

Let us go back now to equation (30a). Using boundedness of
$\Delta\theta^{\mathrm{Upper}}_{i}$ (see Lemma 1 in the Appendix A.1) and thus
of $\sigma_{i}$, we can rewrite it equivalently as:

$\lVert\hat{P}_{i}-P^{*}\rVert_{F}\leq\beta\left(\lVert\hat{P}_{0}-P^{*}\rVert_{F},i\right)+\bar{\gamma}\left(\lVert\Delta\theta^{\mathrm{Upper}}\rVert_{\infty}\right).$
(32)

where
$\bar{\gamma}\left(\lVert\Delta\theta^{\mathrm{Upper}}\rVert_{\infty}\right):=\frac{\sigma_{0}}{1-c}\lVert\Delta\theta^{\mathrm{Upper}}\rVert_{\infty}$.
Eq.32 says that the policy iteration system formulated by (29a) and (29d) is
input-to-state stable with respect to the sequence
$\Delta\theta^{\mathrm{Upper}}$ representing the RLS estimation error.

Let us now turn our attention to equation (30b). The function $f(x,i)$ is not
a $\mathcal{KL}$ function unless $N_{\max}=1$ because of the floor function.
However, note that $f(x,i)$ is always non-increasing with respect to $i$,
$f(x,i)\rightarrow 0$ when $i\rightarrow\infty$ and $f(x,i)\rightarrow 0$ when
$x\rightarrow 0$. The function $g(x)$ is not a $\mathcal{K}$ function because
$j_{i}^{\mathrm{non}}\in\mathbb{Z}_{+}$, but satisfies $g(x)\rightarrow 0$
when $x\rightarrow 0$. Therefore, we can qualitatively interpret (30b) as an
ISS-type stability result.

The interesting aspect of this informal interpretation is that we can view the
sequences associated with estimation error and lack of persistent excitation
as disturbance terms acting on the PI and RLS dynamics, respectively.

Building on this interpretation, we finally provide the following two
corollaries.

###### Corollary 2

Given the assumptions and notations of Theorem 6, and an episode
$i_{\mathrm{re}}>1$, the following holds

$\lVert\hat{P}_{i}-P^{*}\rVert_{F}\leq\beta\left(\lVert\hat{P}_{i_{\mathrm{re}}}-P^{*}\rVert_{F},i-i_{\mathrm{re}}\right)+\frac{\sigma_{i_{\mathrm{re}}}}{1-c}\Delta\theta^{\mathrm{Upper}}_{i_{\mathrm{re}}},\quad
i\geq i_{\mathrm{re}}.$ (33)

Because $\sigma_{i_{\mathrm{re}}}\leq\sigma_{0}$, we can see also analytically
that a faster convergence of $\Delta\theta^{\mathrm{Upper}}_{i}$ contributes
to a faster convergence of $\hat{P}_{i}$.

###### Corollary 3

Under the assumptions and notations of Theorem 6, if the data sequence
$\\{d_{t}\\}$ is locally persistent with respect to any $N,M,\alpha$, then
$\mathop{lim}\limits_{i\rightarrow\infty}\theta_{i}=\theta$,$\mathop{lim}\limits_{i\rightarrow\infty}\hat{P_{i}}=P^{*}$
and $\mathop{lim}\limits_{i\rightarrow\infty}\hat{K_{i}}=K^{*}$.

Corollary 3, which is proven in Appendix D.3, shows that IPI asymptotically
finds the optimal gain $K^{*}$. We remark that this holds for any value of
$\tau_{\mathrm{IPI}}$.

When the sequence is not locally persistent, Theorem 6 is still informative
and allows a bound on the distance $\lVert\hat{P}_{i}-P^{*}\rVert_{F}$ to be
quantified as:

$\lVert\hat{P}_{i}-P^{*}\rVert_{F}\leq\beta\left(\lVert\hat{P}_{0}-P^{*}\rVert_{F},i\right)+\bar{\gamma}\left(f\left(\lVert\theta_{0}-\theta\rVert_{F},i\right)+g\left(\lVert
j^{\mathrm{non}}\rVert_{\infty}\right)\right).$ (34)

##  4 Direct Data-driven Policy Iteration

This Section investigates a possible approach to perform policy iteration
using data but without having to explicitly identify a model. This approach,
referred to here as DPI to mark its direct nature, is a modified version of
the algorithm recently presented in [24] to address identifiability issues
arising in noise-free scenarios. The DPI algorithm has the same episodic
structure introduced in Section 3 with reference to IPI, and therefore we also
use here the two indices timesteps $t$ and episode step $i$ with the same
meaning. The key difference is that the data collected in each episode, of
length $\tau_{\mathrm{DPI}}$, are used here to learn the parameters required
in the policy iteration update involved in the PI steps.

###  4.1 Preliminaries of model-free policy iteration

In this section, we review the necessary background material from [24]. At a
generic episode $i\geq 1$, the DPI procedure involves the two steps described
next.

####  4.1.1 Model-free policy evaluation

In order to perform the policy evaluation step in Algorithm 1 in a model-free
fashion, the key observation is that (3), used to explain the basic idea of
PI, does not require the system dynamics. Introducing $vecs(P_{i})$, where
$x_{t}$ is the system state at timestep $t$ and $P_{i}$ is the quadratic
kernel at episode $i$, this equation can be rewritten as follows:

${\underbrace{\left(vecv(x_{t})-vecv(x_{t+1})\right)}_{=:\Phi_{t}}}^{\top}vecs(P_{i})=x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}=r(x_{t},K_{i}x_{t})$
(35)

Estimating $vecs(P_{i})$ requires solving the linear equation (35), which
consists of $\frac{n_{x}(n_{x}+1)}{2}$ unknown entries defining the upper-
triangle part of a symmetric matrix. To this end, the system is excited using
the control input $u_{t}=K_{i}x_{t}$ for at least
$\tau_{\mathrm{PE}}=\frac{n_{x}(n_{x}+1)}{2}$ instances. If the sequence
$\\{\Phi_{t}\\}$ is globally persistent with respect to
$N=\frac{n_{x}(n_{x}+1)}{2}$, i.e.

$\sum\limits_{k=t}^{t+\tau_{\mathrm{PE}}-1}\Phi_{k}\Phi_{k}^{\top}\succ 0,$
(36)

then $vecs(P_{i})$ can be estimated from the data
$\\{x_{t},...,x_{t+\tau_{\mathrm{PE}}}\\}$ as follows:

$\begin{split}vecs({P}_{i})=\left(\sum\limits_{k=t}^{t+\tau_{\mathrm{PE}}-1}\Phi_{k}\Phi_{k}^{\top}\right)^{-1}\left(\sum\limits_{k=t}^{t+\tau_{\mathrm{PE}}-1}\Phi_{k}r(x_{k},K_{i}x_{k})\right).\end{split}$
(37)

###### Remark 6

This method is only applicable to a system subject to process noise, as for
example in $x_{t+1}=Ax_{t}+Bu_{t}+w_{t}$. In noise-free cases (or cases with a
very low amount of process noise), introducing the simple linear feedback
results in the evolution $x_{t+1}=(A+BK_{i})x_{t}$ which determines a lack of
identifiability of $P_{i}$. The discussion on decoupling the data dependency
and refining this method to resolve this issue will be presented in the
following subsection 4.2.

####  4.1.2 Model-free policy improvement

The objective in this step is to find the updated policy $K_{i+1}$ based on
the evaluation $P_{i}$. The system is excited by $u_{t}=K_{i}x_{t}+\eta_{t}$,
where $\eta_{t}\sim\mathcal{N}(0,W_{\eta})$ serves as additional excitation
and must be present. The reason for the need of introducing this additional
excitation in the policy will be evident soon. The corresponding value-based
Bellman equation can be expressed as:

$(x_{t+1}-B\eta_{t})^{\top}P_{i}(x_{t+1}-B\eta_{k})=x_{t}^{\top}(P_{i}-Q-K_{i}^{\top}RK_{i})x_{t}.$
(38)

This leads to:

$\begin{split}2x_{t}^{\top}{A^{\top}P_{i}B}\eta_{t}+(2K_{i}x_{t}+\eta_{t}){B^{\top}P_{i}B}(u_{t}-K_{i}x_{t})&=x_{t}^{\top}(Q+K_{i}^{\top}RK_{i}-P_{i})x_{t}+x_{t+1}^{\top}P_{i}x_{t+1},\\\
{\underbrace{\left[\begin{array}[]{c}2x_{t}\otimes\eta_{t}\\\
vecv(u_{t})-vecv(K_{i}x_{t})\end{array}\right]}_{=:\Gamma_{t}}}^{\top}\underbrace{\left[\begin{array}[]{c}vec(B^{\top}P_{i}A)\\\
vecs(B^{\top}P_{i}B)\end{array}\right]}_{=:\xi_{i}}&=\underbrace{x_{t}^{\top}(Q+K_{i}^{\top}RK_{i}-P_{i})x_{t}+x_{t+1}^{\top}P_{i}x_{t+1}}_{=:c_{t}}.\end{split}$
(39)

Eq. (39) shows that introducing $\eta_{t}$ is critical to ensure that
$B^{\top}P_{i}B,B^{\top}P_{i}A$ can be estimated, otherwise $\Gamma_{t}$ is
always zero matrix. The vector $vecs(B^{\top}P_{i}B)$ consists of
$\frac{n_{u}(n_{u}+1)}{2}$ unknown entries (because of symmetry) whereas the
vector $vec(B^{\top}P_{i}A)$ presents $n_{x}n_{u}$ unknown. If the sequence
$\\{\Gamma_{t}\\}$ is globally persistent with respect to
$N=\frac{n_{u}(n_{u}+1)}{2}+n_{x}n_{u}$, i.e.

$\sum\limits_{k=t}^{t+\tau_{\mathrm{PI}}-1}\Gamma_{t}\Gamma_{t}^{\top}\succ
0,$ (40)

then $\xi_{i}$ can be obtained as follows:

$\xi_{i}=\left(\sum\limits_{k=t}^{t+\tau_{\mathrm{PI}}-1}\Gamma_{t}\Gamma_{t}^{\top}\right)^{-1}\left(\sum\limits_{k=t}^{t+\tau_{\mathrm{PI}}-1}\Gamma_{t}c_{k}\right)$
(41)

After estimating $\xi_{i}$, the gain can be updated with
$K_{i+1}=-(R+B^{\top}P_{i}B)^{-1}B^{\top}P_{i}A$.

###### Remark 7

If the number of minimum samples discussed before are fulfilled and the
sequences $\\{\Phi_{t}\\}$ and $\\{\Gamma_{t}\\}$ are globally persistent with
respect to the orders defined earlier, $P_{i}$ and $\xi_{i}$ are estimated
exactly at each step and thus the properties of model-based policy iteration
in Theorem 1 apply here as well.

###  4.2 Algorithm definition

As mentioned in Remark 6, an issue in [24] preventing its use in a noise-free
scenario is the loss of identifiability of $P_{i}$. To overcome it, one
solution is to add a signal $\eta_{t}$ targeted to decouple the dependence
across data points. The issue with using an additional excitation $\eta_{t}$
for the policy evaluation step is that the evaluated policy is the affine
policy $\hat{K}_{i}x_{t}+\eta_{t}$ and not just the linear state-feedback one,
thus introducing an error. To solve this problem, we introduce an average
system.

The average system is formulated as follows: when $t$ is odd, $\eta_{t}$ is
randomly selected from a Gaussian distribution, and when $t$ is even,
$\eta_{t}$ is selected as $\eta_{t}=-\eta_{t-1}$. The state evolutions at two
consecutive times when $t$ is odd are given as follows:

$\displaystyle x_{t+1}$
$\displaystyle=Ax_{t}+Bu_{t}=Ax_{t}+B(\hat{K}_{i}x_{t}+\eta_{t}),$ (42a)
$\displaystyle x_{t+2}=Ax_{t+1}+Bu_{t}=$ $\displaystyle
Ax_{t+1}+B(\hat{K}_{i}x_{t+1}+\eta_{t+1})=Ax_{t+1}+B(\hat{K}_{i}x_{t+1}-\eta_{t}).$
(42b)

By summing up the state evolutions, we obtain the average system dynamics:

$(x_{t+2}+x_{t+1})=A(x_{t+1}+x_{t})+B\hat{K}_{i}(x_{t+1}+x_{t}).$ (43)

Because $t$ is odd, we can define $t=2k-1$ with $k\in\mathbb{Z}_{+}$. This
allows the use of the data pairs $\\{x_{2k}+x_{2k-1}\\}$ together with
$\\{x_{2k+1}+x_{2k}\\}$ to evaluate the gain $\hat{K}_{i}$, as described in
Section 4.1.1. Because the policy evaluation is executed based on the average
system (data pairs), each episode must consist of an even number of data
points. The stage cost for the average system is defined as:

$R_{k}:=(x_{2k-1}+x_{2k})^{\top}Q(x_{2k-1}+x_{2k})+(x_{2k-1}+x_{2k})^{\top}\hat{K}_{i}^{\top}R\hat{K}_{i}(x_{2k-1}+x_{2k}).$
(44)

This leads to a newly formulated value-based Bellman equation:

$(x_{2k}+x_{2k+1})^{\top}\hat{P}_{i}(x_{2k}+x_{2k+1})+R_{k}=(x_{2k-1}+x_{2k})^{\top}\hat{P}_{i}(x_{2k-1}+x_{2k}).$
(45)

Consequently, we can obtain $\hat{P}_{i}$ by solving the following equation:

$\displaystyle{\underbrace{\left(vecv(x_{2k-1}+x_{2k})-vecv(x_{2k}+x_{2k+1})\right)}_{=:\phi_{k}}}^{\top}vecs(\hat{P}_{i})=R_{k}.$
(46)

We collect the data from time index $t$ to $t+\tau_{\mathrm{DPI}}-1$,
constituting an episode with length $\tau_{\mathrm{DPI}}$. The collected data
provide $\frac{\tau_{\mathrm{DPI}}}{2}$ data pairs. If the data sequence
$\\{\phi_{k}\\}$ are persistently exciting with respect to order
$\frac{n_{x}(n_{x}+1)}{2}$, the solution to equation (46) is given by:

$vecs(\hat{P}_{i})=\left(\sum\limits_{k=\frac{t+1}{2}}^{\frac{t+1}{2}+\frac{\tau_{\mathrm{DPI}}}{2}}\phi_{k}\phi_{k}^{\top}\right)^{-1}\left(\sum\limits_{k=\frac{t+1}{2}}^{\frac{t+1}{2}+\frac{\tau_{\mathrm{DPI}}}{2}}\phi_{k}R_{k}\right).$
(47)

The policy improvement step does not require modifications and thus is taken
identically to Section 4.1.2. The overall procedure of DPI is summarized in
Algorithm 4.

Algorithm 4 Direct data-driven policy iteration.

stabilizing policy gain $K_{1}$

for $i=1,...,\infty$ do (episode counter)

for $j=1,...,\tau_{\mathrm{DPI}}$ do (timestep counter inside episode $i$)

Excite the system with
$u_{\tau_{\mathrm{DPI}}(i-1)+2j-1}=\hat{K}_{i}x_{\tau_{\mathrm{DPI}}(i-1)+2j-1}+\eta_{\tau_{\mathrm{DPI}}(i-1)+2j-1}$,
$\eta_{t}\sim\mathcal{N}(0,W_{\eta})$

Collect the data
$D_{PI}\leftarrow(x_{\tau_{\mathrm{DPI}}(i-1)+2j-1},u_{\tau_{\mathrm{DPI}}(i-1)+2j-1},x_{\tau_{\mathrm{DPI}}(i-1)+2j})$

Excite the system with
$u_{\tau_{\mathrm{DPI}}(i-1)+2j}=\hat{K}_{i}x_{\tau_{\mathrm{DPI}}(i-1)+2j}-\eta_{\tau_{\mathrm{DPI}}(i-1)+2j-1}$

Collect the data
$D_{PI}\leftarrow(x_{\tau_{\mathrm{DPI}}(i-1)+2j},u_{\tau_{\mathrm{DPI}}(i-1)+2j},x_{\tau_{\mathrm{DPI}}(i-1)+2j+1})$

Collect the data
$D_{PE}\leftarrow(x_{\tau_{\mathrm{DPI}}(i-1)+2j-1}+x_{\tau_{\mathrm{DPI}}(i-1)+2j},u_{\tau_{\mathrm{DPI}}(i-1)+2j-1}+u_{\tau_{\mathrm{DPI}}(i-1)+2j},x_{\tau_{\mathrm{DPI}}(i-1)+2j}+x_{\tau_{\mathrm{DPI}}(i-1)+2j+1})$

end for

Policy Evaluation: find $\hat{P}_{i}$

Calculate $\hat{P}_{i}$ via (47) with $D_{PE}$

Policy Improvement: update gain $\hat{K}_{i+1}$

Calculate $B^{\top}P_{i}B,B^{\top}P_{i}A$ via (41) with $D_{PI}$

$\hat{K}_{i+1}=-(R+B^{\top}P_{i}B)^{-1}B^{\top}P_{i}A$

end for

###  4.3 Conditions for convergence of DPI

First, we analyze the minimum number of samples of each episode. The matrix
$\hat{P}_{i}$ is a symmetric matrix, requiring a minimum of
$\frac{n_{x}(n_{x}+1)}{2}$ data pairs for its exact estimation. As a result,
$n_{x}(n_{x}+1)$ data points are necessary during the policy evaluation phase.
In the policy improvement phase, $B^{\top}P_{i}B$ and $B^{\top}P_{i}A$ are
estimated. We note that $B^{\top}P_{i}B$ is also a symmetric matrix. Hence, a
total of $\frac{n_{u}(n_{u}+1)}{2}+n_{u}n_{x}$ data points are necessary for
the policy improvement. Crucially, the same data points are employed for both
the policy evaluation and policy improvement simultaneously. Thus, the minimum
number of required samples for each episode, which influences the choice of
$\tau_{\mathrm{DPI}}$, is determined by
$\max[n_{x}(n_{x}+1),\frac{n_{u}(n_{u}+1)}{2}+n_{u}n_{x}]$. When the required
samples in each episode are provided and in addition the data sequences $\phi$
and $\Gamma$ are globally persistent with respect to corresponding order
(ensuring the existence of inverse operations in (47) and (41)), the
estimations of $\hat{P}_{i}$, $B^{\top}P_{i}B$ and $B^{\top}P_{i}A$ are exact.
In this case, the algorithm enjoys the properties outlined in Theorem 1. We
can conclude that $\hat{P}_{i}$ and $\hat{K}_{i}$ converge to $P^{*}$ and
$K^{*}$, respectively.

When the length of the episode is insufficient to meet the overall required
number of samples per episode, Eq. (46) and Eq. (39) become underdetermined.
This implies that $\hat{P}_{i}$, $B^{\top}P_{i}B$, and $B^{\top}P_{i}A$ cannot
be precisely solved, leading to the divergence of $\hat{K}_{i}$ and
$\hat{P}_{i}$.

##  5 Discussion of IPI and DPI

In this section, we compare the salient features of the analyses performed to
IPI and DPI in Section 3 and 4, respectively. A summary of the key aspects is
presented in Table 1 at the end of this section.

###  5.1 Data persistency of excitation

From Corollary 3, we observe that the convergence of IPI is guaranteed when
the data sequence is locally persistent with respect to any $N,M,\alpha$. In
contrast, DPI requires exact estimation of $\hat{P}_{i}$, $B^{\top}P_{i}B$ and
$B^{\top}P_{i}A$ in each episode. The data used for the estimation of
$\hat{P}_{i}$ must be persistently exciting with respect to order
$\frac{n_{x}(n_{x}+1)}{2}$. As for the estimation of $B^{\top}P_{i}B$ and
$B^{\top}P_{i}A$, the data sequence within one episode must be persistently
exciting with respect to order $\frac{n_{u}(n_{u}+1)}{2}+n_{u}n_{x}$.
Moreover, Theorem 6 provides for IPI computable bounds on the error between
estimates and true values due to a lack of excitation in the sequence. These
bounds are structured and point out the contribution due to the non-exciting
part of the sequence (see terms depending on the function $g$ in (34)). On the
contrary, in the case of DPI nothing can be said in the case of non-
persistently exciting sequences because the systems of equations (46) and (39)
are underdetermined. In IPI, data persistency is assured when selecting
$e_{t}\sim\mathcal{N}(0,W_{e})$. However, in DPI, even if $\eta_{t}$ is drawn
from $\mathcal{N}(0,W_{\eta})$, the persistency of sequence $\phi$, $\Gamma$
cannot be directly guaranteed from the persistency of sequence $\\{x_{t}\\}$
due to the nonlinear vector operation $vecs(\cdot)$.

###  5.2 Selection of episode length

The selection of $\tau_{\mathrm{IPI}}$ has two major implications. First, it
can have a beneficial effect on the achievement of Assumptions 1 and 2, as
already discussed therein. On the other hand, it is a trade-off parameter
between the rate at which the system dynamics are learned and how often the
policy iteration is performed. The theoretical minimum value for
$\tau_{\mathrm{IPI}}=1$, and its choice is a system-dependent compromise among
the aforementioned aspects. The selection of $\tau_{\mathrm{DPI}}$ must
satisfy the persistently exciting order requirement of both policy evaluation
and policy improvement phase, i.e.
$\tau_{\mathrm{DPI}}=\mathrm{max}[n_{x}(n_{x}+1),\frac{n_{u}(n_{u}+1)}{2}+n_{u}n_{x}]$.
If $\tau_{\mathrm{DPI}}$ is less than the minimum required samples,
convergence cannot be guaranteed. In practice, $\tau_{\mathrm{DPI}}$ should
always be selected larger than the minimum required samples because data
persistency cannot be assured, as explained in the previous subsection.

###  5.3 Number of required samples and convergence rate

If
$\tau_{\mathrm{DPI}}=\mathrm{max}[n_{x}(n_{x}+1),\frac{n_{u}(n_{u}+1)}{2}+n_{u}n_{x}]$
and the excitation conditions are met in _each_ episode, then DPI follows the
convergence rate exhibited by policy iteration using the true model. Under
this condition, the upper bound on the iterate error of DPI, denoted as
$f_{\mathrm{DPI}}^{\mathrm{Upper}}(i_{\mathrm{DPI}})$, can then be derived
using Theorem 4 as follows:

$\begin{split}\lVert\hat{P}_{i_{\mathrm{DPI}}}-P^{*}\rVert_{F}&\leq
c\lVert\hat{P}_{i_{\mathrm{DPI}}-1}-P^{*}\rVert_{F}\leq...\leq
c^{{i_{\mathrm{DPI}}}}\lVert\hat{P}_{0}-P^{*}\rVert_{F}=:f_{\mathrm{DPI}}^{\mathrm{Upper}}(i_{\mathrm{DPI}}),\end{split}$
(48)

where $i_{\mathrm{DPI}}$ is the episode index of DPI. Defining the episode
index of IPI as $i_{\mathrm{IPI}}$, the upper bound on the iterate error of
IPI denoted as $f_{\mathrm{IPI}}^{\mathrm{Upper}}(i_{\mathrm{IPI}})$, outlined
in Theorem 6, can be obtained as follows:

$\lVert\hat{P}_{i_{\mathrm{IPI}}}-P^{*}\rVert_{F}\leq
c^{i_{\mathrm{IPI}}}\lVert\hat{P}_{0}-P^{*}\rVert_{F}+\frac{\sigma_{0}}{1-c}\lVert\Delta\theta^{\mathrm{Upper}}\rVert_{\infty}=:f_{\mathrm{IPI}}^{\mathrm{Upper}}(i_{\mathrm{IPI}}).$
(49)

We can then draw a comparison between the upper bounds on the error of DPI and
IPI starting from an identical initialization $\hat{P_{0}}$ at the same
episode counter $i_{\mathrm{DPI}}=i_{\mathrm{IPI}}$:

$f_{\mathrm{DPI}}^{\mathrm{Upper}}(i_{\mathrm{DPI}})=c^{{i_{\mathrm{DPI}}}}\lVert\hat{P}_{0}-P^{*}\rVert_{F}\leq
c^{i_{\mathrm{IPI}}}\lVert\hat{P}_{0}-P^{*}\rVert_{F}+\frac{\sigma_{0}}{1-c}\lVert\Delta\theta^{\mathrm{Upper}}\rVert_{\infty}=f_{\mathrm{IPI}}^{\mathrm{Upper}}(i_{\mathrm{IPI}}).$
(50)

where the inequality comes from the fact that, as seen in (49),
$f_{\mathrm{IPI}}^{\mathrm{Upper}}(i_{\mathrm{IPI}})$ has an additional non-
negative term due to the model mismatch. As a result, at the same episode
$f_{\mathrm{DPI}}^{\mathrm{Upper}}(i_{\mathrm{DPI}})$ is always smaller than
$f_{\mathrm{IPI}}^{\mathrm{Upper}}(i_{\mathrm{IPI}})$. However, it is
essential to observe that the minimum episode length required by IPI and DPI,
discussed in the previous section, is markedly different. While for IPI the
theoretical minimum number of samples is $1$, for DPI this depends
polynomially on the state and input sizes. This means that
$\tau_{\mathrm{IPI}}$ can be much smaller than $\tau_{\mathrm{DPI}}$, allowing
more episodes to take place within the same number of total timesteps. If we
compare the two methods given the same fixed time budget, that is
$\tau_{\mathrm{DPI}}i_{\mathrm{DPI}}=\tau_{\mathrm{IPI}}i_{\mathrm{IPI}}$,
then IPI can perform a much larger number of episode.

The explanation for this much better _sample complexity_ of IPI, when compared
to DPI, has to do with the different learning objectives of the algorithms.
Precisely, IPI utilizes data only to learn the system dynamics $(A,B)$, while
DPI employs data to learn in each episode the value function and the improved
policy $(P_{i},K_{i})$. Whereas the system dynamics $(A,B)$ is time-invariant
and thus all the available data contribute towards its estimation,
$(P_{i},K_{i})$ are episode-related quantities and hence the increase of
information attained by each data point is limited to the current episode.
From this perspective, identifying a model allows a more efficient use of the
data to be made, because effectively it decreases the number of unknowns that
should be estimated from data.

###  5.4 Excitation policy

In IPI, the control input is expressed as $u_{t}=\hat{K}_{i}x_{t}+e_{t}$,
while in DPI, the control input is given as $u_{t}=\hat{K}_{i}x_{t}+\eta_{t}$.
However, there is a notable distinction in the selection of the individual
terms of this policy. In DPI, $\eta_{t}$ needs to satisfy specific conditions
to form data pairs, and $\hat{K}_{i}$ must be the policy gain obtained from
the policy improvement step of the previous episode, i.e. data should be "on-
policy". On the other hand, IPI allows for a more flexible selection of
$\hat{K}_{i}$. The use of a model to perform the steps in PI allows the
controller design and online data collection to be decoupled, because the
collected data are used to learn a model and not the evaluation and
improvement of the controller. In this work, the choice of controller
$u_{t}=\hat{K}_{i}x_{t}+e_{t}$ used during IPI is only driven by the aim to
minimize the cost function (2) also during learning. However, IPI does not
require "on-policy" data, and thus any controller, e.g. any pre-stabilizing
gain $\hat{K}$, would be an acceptable solution. From this perspective, the
availability of a model provides for this problem greater flexibility in
selecting the online controller. In this work, we do not specify the selection
of $e_{t}$ in IPI, while our analysis holds for any selection of $\hat{K}_{i}$
and $e_{t}$. In the following simulations, we select $e_{t}$ as a Gaussian
distributed signal to ensure persistency and also $e_{t}=0$ to verify the
performance of IPI with a non-persistent sequence. Understanding how to best
design $e_{t}$ based on online available information such as $\hat{P}_{i}$ or
$H_{i}$ is a natural follow-up to this work.

###  5.5 Closed-loop stability of the plant and algorithm dynamics

In Section 3.2, we analyze the algorithmic closed-loop dynamic formed by RLS
and PI. This is also illustrated with the blue blocks connected by the blue
lines in Figure 2. Whereas Theorem 6, under certain assumptions, shows a
bounded response for this interconnection, we do not discuss the closed-loop
stability of the interconnection with the physical plant, depicted by the
black blocks connected with black lines. For the "off-policy" case where IPI
runs with a given pre-stabilizing gain $\hat{K}$, this analysis is trivial and
we could conclude closed-loop stability of the physical-algorithmic system
because the plant is effectively decoupled from the algorithm. In the "on-
policy" case, this is an interesting question that could be studied as part of
future work.

In DPI, when the excitation and sample requirements discussed in Section 4.3
are satisfied, the feedback gain $\hat{K}_{i}$ obtained from the Algorithm 2
provably stabilizes the true plant (this comes from standard true model-based
PI results [28]). Conversely, when the requirements on the convergence are not
met, there are no closed-loop stability guarantees.

| IPI | DPI
---|---|---
Assumptions | Assumption 1,2 |
Persistently exciting order | $N>0$ | PE:$\frac{n_{x}(n_{x}+1)}{2}$, PI:$\frac{n_{u}(n_{u}+1)}{2}+n_{u}n_{x}$
Selection of excitation | flexible | $u_{t}=\hat{K}_{i}x_{t}+\eta_{t}$
Minimum episode length | $1$ | $\max\\{n_{x}(n_{x}+1),\frac{n_{u}(n_{u}+1)}{2}+n_{u}n_{x}\\}$
Convergence rate | (49) | (48)
Table 1: Comparison between IPI and DPI.

##  6 Simulation Results

In this section, we present simulation results111The Matlab codes used to
generate these results are accessible from the repository:
https://gitlab.com/col-tasas/datadrivenpolicyiteration-ipi-dpi to illustrate
some of the properties of IPI and DPI methods discussed in the previous
sections. We consider the following system which was already used in prior
studies [24, 7, 34, 25]:

$x_{t+1}=\underbrace{\left[\begin{array}[]{ccc}1.01&0.01&0\\\
0.01&1.01&0.01\\\
0&0.01&1.01\end{array}\right]}_{A}x_{t}+\underbrace{\left[\begin{array}[]{ccc}1&0&0\\\
0&1&0\\\ 0&0&1\end{array}\right]}_{B}u_{t}$ (51)

The weighting matrices $Q$ and $R$ are set to $0.001I_{3}$ and $I_{3}$,
respectively. The estimations of $A$ and $B$ are initialized as zero matrices
$0_{3}$ and $H_{0}$ for RLS is set to $0.01I_{6}$. The initial stabilizing
policy gain $K_{0}$ is set to $diag\\{-1.5,-1.0,-0.5\\}$ which stabilizes (51)
and also the initial estimate $\hat{A}_{0}$ and $\hat{B}_{0}$. The simulation
results are depicted in Figure 5.

Figure 5: Comparison of DPI and IPI with different episode lengths
$\tau_{\mathrm{IPI}}$ and $\tau_{\mathrm{DPI}}$ (the variable $\tau$ in the
$x$-axis denotes the length of the episode in the respective approach).

Figure 5 illustrates the convergence of the quadratic kernel of the value
function $\hat{P}_{i}$ and feedback gain $\hat{K}_{i}$ for different choices
of episode length. For this problem, the minimum number of samples required by
DPI is $15$, thus we use here $\tau_{\mathrm{DPI}}=16$, which includes
redundant data to meet the requirement for the formulation of data pairs. For
any $\tau_{\mathrm{DPI}}<16$, both $\hat{P}_{i}$ and $\hat{K}_{i}$ diverge. It
can be observed that IPI has a faster convergence rate to the optimum when
compared to DPI, in accordance with the discussion before. The black dotted
line in Figure 5 shows the case of IPI with $\tau_{\mathrm{IPI}}=10$ and
$e_{t}=0$, indicating that the data sequence is not locally persistent.
Consequently, the estimation error of $\theta_{i}$ is never zero, and
$\hat{K}_{i}$ stays within a non-zero error from the optimal $K^{*}$. The
numerical results illustrate overall the analytical aspects discussed in
Section 3.2.4.

##  7 Conclusion

In this work we studied indirect and direct approaches to data-driven LQR
policy iteration with the goal to understand what are the main implications of
having or not a model. We viewed the indirect approach as a feedback
interconnection between an identification scheme and the policy iteration
algorithm, both seen as instances of algorithmic dynamical systems responsible
for the concurrent learning and control. We analysed this nonlinear closed-
loop system without making any assumption on the level of excitation of the
data and notably captured non-persistent data sequences as dynamic
perturbations to the algorithm. For the direct approach, we extended a
recently proposed method from the literature and precisely assessed its data
and excitation requirements. In this problem setting, the availability of an
intermediate model determines a lower number of required samples, the
possibility to employ more flexible policies, and an increased robustness to
lack of excitation in the data. The goal of the work was to isolate and
understand the fundamental effects associated with the availability of a
model, therefore no noise is considered in the analysis. This is a limitation
of the current study and a comparison between indirect and direct approaches
in the presence of process and measurement noise should be considered in
future work. Moreover, an adaptive design of the excitation signal $e_{t}$ in
IPI, which is guided by the current system theoretic analysis, is another
important future direction.

## Acknowledgements

Bowen Song acknowledges the support of the International Max Planck Research
School for Intelligent Systems (IMPRS-IS).

## References

  * [1] Zhong-Sheng Hou and Zhuo Wang.  From model-based control to data-driven control: Survey, classification and perspective.  Information Sciences, 235:3–35, 2013.  Data-based Control, Decision, Scheduling and Fault Diagnostics.
  * [2] A. Khaki-Sedigh.  An Introduction to Data-Driven Control Systems.  Wiley, 2023.
  * [3] Damoon Soudbakhsh, Anuradha M. Annaswamy, Yan Wang, Steven L. Brunton, Joseph Gaudio, Heather Hussain, Draguna Vrabie, Jan Drgona, and Dimitar Filev.  Data-driven control: Theory and applications.  In 2023 American Control Conference (ACC), pages 1922–1939. 2023 American Control Conference (ACC), 2023.
  * [4] Florian Dörfler.  Data-driven control: Part two of two: Hot take: Why not go with models?  IEEE Control Systems Magazine, 43(6):27–31, 2023.
  * [5] L. Ljung.  System Identification: Theory for the User.  Prentice Hall information and system sciences series. Prentice Hall PTR, 1999.
  * [6] K.J. Åström and B. Wittenmark.  Adaptive Control.  Dover Books on Electrical Engineering. Dover Publications, 2008.
  * [7] Benjamin Recht.  A tour of reinforcement learning: The view from continuous control.  Annual Review of Control, Robotics, and Autonomous Systems, 2(1):253–279, 2019.
  * [8] Anuradha M. Annaswamy.  Adaptive control and intersections with reinforcement learning.  Annual Review of Control, Robotics, and Autonomous Systems, 6(1):65–93, 2023.
  * [9] Florian Dörfler, Jeremy Coulson, and Ivan Markovsky.  Bridging direct and indirect data-driven control formulations via regularizations and relaxations.  IEEE Transactions on Automatic Control, 68(2):883–897, 2023.
  * [10] Stephen Tu and Benjamin Recht.  The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint.  In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99, pages 3036–3083. PMLR, 25–28 Jun 2019.
  * [11] A. Bhaya and E. Kaszkurewicz.  Control Perspectives on Numerical Algorithms and Matrix Problems.  Advances in Design and Control. Society for Industrial and Applied Mathematics, 2006.
  * [12] Carsten Scherer and Christian Ebenbauer.  Convex synthesis of accelerated gradient algorithms.  SIAM Journal on Control and Optimization, 59(6):4615–4645, 2021\.
  * [13] Laurent Lessard.  The analysis of optimization algorithms: A dissipativity approach.  IEEE Control Systems Magazine, 42(3):58–72, 2022.
  * [14] Dominic Liao-McPherson, Terrence Skibik, Jordan Leung, Ilya Kolmanovsky, and Marco M. Nicotra.  An analysis of closed-loop stability for linear model predictive control based on time-distributed optimization.  IEEE Transactions on Automatic Control, 67(5):2618–2625, 2022.
  * [15] Andrea Zanelli, Quoc Tran-Dinh, and Moritz Diehl.  A lyapunov function for the combined system-optimizer dynamics in inexact model predictive control.  Automatica, 134:109901, 2021.
  * [16] Frank L Lewis, Draguna Vrabie, and Vassilis L Syrmos.  Optimal control.  John Wiley & Sons, 2012.
  * [17] D. Bertsekas.  Abstract Dynamic Programming: 3rd Edition.  Athena Scientific., 2022.
  * [18] Youngsuk Park, Ryan A. Rossi, Zheng Wen, Gang Wu, and Handong Zhao.  Structured policy iteration for linear quadratic regulator.  In Proceedings of the 37th International Conference on Machine Learning, ICML’20. Proceedings of the 37th International Conference on Machine Learning, JMLR.org, 2020.
  * [19] Donghwan Lee.  Convergence of dynamic programming on the semidefinite cone for discrete-time infinite-horizon lqr.  IEEE Transactions on Automatic Control, 67(10):5661–5668, 2022\.
  * [20] Bo Pang, Tao Bian, and Zhong-Ping Jiang.  Robust policy iteration for continuous-time linear quadratic regulation.  IEEE Transactions on Automatic Control, 67(1):504–511, 2022.
  * [21] Dimitri Bertsekas.  Newton’s method for reinforcement learning and model predictive control.  Results in Control and Optimization, 7:100121, 2022.
  * [22] Tae Yoon Chun, Jae Young Lee, Jin Bae Park, and Yoon Ho Choi.  Stability and monotone convergence of generalised policy iteration for discrete-time linear quadratic regulations.  International Journal of Control, 89(3):437–450, 2016.
  * [23] Hesameddin Mohammadi, Armin Zare, Mahdi Soltanolkotabi, and Mihailo 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.
  * [24] Farnaz Adib Yaghmaie, Fredrik Gustafsson, and Lennart Ljung.  Linear quadratic control using model-free reinforcement learning.  IEEE Transactions on Automatic Control, 68(2):737–752, Feb 2023\.
  * [25] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu.  On the sample complexity of the linear quadratic regulator.  Foundations of Computational Mathematics, 20, 10 2017.
  * [26] Mina Ferizbegovic, Jack Umenberger, Håkan Hjalmarsson, and Thomas B. Schön.  Learning robust lq-controllers using application oriented exploration.  IEEE Control Systems Letters, 4(1):19–24, 2020.
  * [27] Augusto Ferrante and Lorenzo Ntogramatzidis.  The generalised discrete algebraic riccati equation in linear-quadratic optimal control.  Automatica, 49(2):471–478, 2013.
  * [28] G. Hewer.  An iterative technique for the computation of the steady state gains for the discrete optimal regulator.  IEEE Transactions on Automatic Control, 16(4):382–384, 1971.
  * [29] G.A Hewer.  Analysis of a discrete matrix riccati equation of linear control and kalman filtering.  Journal of Mathematical Analysis and Applications, 42(1):226–236, 1973.
  * [30] K. B. Petersen and M. S. Pedersen.  The matrix cookbook.  Technical University of Denmark, October 2008.  Version 20081110.
  * [31] Adam L. Bruce, Ankit Goel, and Dennis S. Bernstein.  Convergence and consistency of recursive least squares with variable-rate forgetting.  Automatica, 119:109052, 2020.
  * [32] Eduardo D. Sontag.  Input to State Stability: Basic Concepts and Results, pages 163–220.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2008.
  * [33] Zhong-Ping Jiang and Yuan Wang.  Input-to-state stability for discrete-time nonlinear systems.  Automatica, 37(6):857–869, 2001.
  * [34] Yasin Abbasi-Yadkori, Nevena Lazic, and Csaba Szepesvari.  Model-free linear quadratic control via reduction to expert prediction.  In International Conference on Artificial Intelligence and Statistics. International Conference on Artificial Intelligence and Statistics, 2018.
  * [35] Chi-Kwong Li and Roy Mathias.  The lidskii-mirsky-wielandt theorem – additive and multiplicative versions.  Numerische Mathematik, 81, 06 2001.
  * [36] C.D. Meyer.  Matrix Analysis and Applied Linear Algebra.  Society for Industrial and Applied Mathematics, 2023.

##  Appendix A Appendix 1

###  A.1 Lemma 1

###### Lemma 1

For any sequence $\\{d_{t}\\}$, the upper bound of the estimation error
$\Delta\theta^{\mathrm{Upper}}_{t}$ of the RLS is non-increasing with respect
to $t$, i.e.

$\Delta\theta_{t}^{\mathrm{Upper}}\geq\Delta\theta_{t+1}^{\mathrm{Upper}},\forall
t\in\mathbb{Z}_{+}$ (52)

From (13), we know that:

$H_{0}\preceq...\preceq H_{t}\preceq...\preceq H_{\infty}.$ (53)

We then use the following result, which is proven in Appendix A.3

###### Lemma 2

Given two positive definite matrix $A,B$, if $A\succeq B$, then $\lVert
A^{-1}\rVert_{F}\leq\lVert B^{-1}\rVert_{F}$.

Using (53) and Lemma 2, the following holds for every $t\in\mathbb{Z}_{+}$:

$\Delta\theta_{t}^{\mathrm{Upper}}=\lVert\Delta\theta_{0}H_{0}\rVert_{F}\lVert
H_{t}^{-1}\rVert_{F}\geq\lVert\Delta\theta_{0}H_{0}\rVert_{F}\lVert
H_{t+1}^{-1}\rVert_{F}=\Delta\theta_{t+1}^{\mathrm{Upper}}.$ (54)

Then we know that $\Delta\theta_{t}^{\mathrm{Upper}}$ is non-increasing with
respect to time index $t$ irrespective of any property of $H_{t}$,
i.e.$\\{d_{t}\\}$. Lemma 1 is now proven.

###  A.2 Proof of Theorem 2

Now we focus on the convergence of the estimation error introduced by
recursive least squares under the assumption of a locally persistent sequence
defined by $M,N,\alpha$. When the data sequence $\\{d_{t}\\}$ is locally
persistent, (18) holds. Then we can get:

$\begin{split}\lVert\Delta\theta_{t}\rVert_{F}&\leq\lVert\Delta\theta_{0}H_{0}\rVert_{F}\lVert
H_{t}^{-1}\rVert_{F}=\Delta\theta_{t}^{\mathrm{Upper}}\\\
&\leq\lVert\Delta\theta_{0}H_{0}\rVert_{F}\left\lVert\left(H_{0}+\sum\limits_{j=0}^{\left\lfloor\frac{t}{M\left\lceil\frac{N}{M}\right\rceil}\right\rfloor}\sum\limits_{k=0}^{N-1}d_{k+j(M\left\lceil\frac{N}{M}\right\rceil)}d_{k+j(M\left\lceil\frac{N}{M}\right\rceil)}^{\top}\right)^{-1}\right\rVert_{F}\\\
&\leq\lVert\Delta\theta_{0}H_{0}\rVert_{F}\left\lVert\left(\left(\left\lfloor\frac{t}{M\left\lceil\frac{N}{M}\right\rceil}\right\rfloor+1\right)\alpha
I_{n_{x}+n_{u}}\right)^{-1}\right\rVert_{F}\\\
&\leq\frac{\sqrt{n_{x}+n_{u}}\lVert\Delta\theta_{0}H_{0}\rVert_{F}}{\sqrt{\left(\left\lfloor\frac{t}{M\left\lceil\frac{N}{M}\right\rceil}\right\rfloor+1\right)\alpha}}.\end{split}$
(55)

The second inequality comes from (13) and the positive semidefinitiness of
$d_{t}d_{t}^{\top}$. The third inequalities comes from (18).
From (55) we can conclude that the convergence of RLS under the assumption of
a locally persistent sequence $\\{d_{t}\\}$ is
$\lVert\Delta\theta_{t}\rVert_{F}\sim\mathcal{O}(\frac{1}{\sqrt{\left\lfloor\frac{t}{M\left\lceil\frac{N}{M}\right\rceil}\right\rfloor}})$

###  A.3 Proof of Lemma 2

For every positive definite matrix $A$, $\lVert
A\rVert_{F}^{2}=\mathop{trace}(A^{2})$[30, 541]. Because $A\succeq
B\succ\mathbf{0}$, then $\lambda_{i}(A)\geq\lambda_{i}(B)>0$,
$\lambda_{i}(B^{-1})\geq\lambda_{i}(A^{-1})>0$. We get:

$\lVert
A^{-1}\rVert_{F}^{2}=\mathop{trace}\left((A^{-1})^{2}\right)=\sum_{i}\limits\lambda_{i}(A^{-1})^{2}\leq\sum_{i}\limits\lambda_{i}(B^{-1})^{2}=\mathop{trace}\left((B^{-1})^{2}\right)=\lVert
B^{-1}\rVert_{F}^{2}.$ (56)

That is, it holds $\lVert A^{-1}\rVert_{F}\leq\lVert B^{-1}\rVert_{F}$.

##  Appendix B Appendix 2

###  B.1 Proof of Theorem 3

From (54) and with $H_{0}=aI$, we can get:

$\begin{split}\lVert\Delta\theta_{i}\rVert_{F}&\leq\Delta\theta_{i}^{\mathrm{Upper}}=\lVert\Delta\theta_{0}H_{0}\rVert_{F}\lVert
H_{i}^{-1}\rVert_{F}=a\lVert\Delta\theta_{0}\rVert_{F}H_{i}^{-1}=a\lVert\Delta\theta_{0}\rVert_{F}\sqrt{\mathop{trace}((H_{i}^{-1})^{2})}\\\
&=a\lVert\Delta\theta_{0}\rVert_{F}\sqrt{\sum\limits_{j=1}^{n_{x}+n_{u}}\lambda_{j}^{2}(H_{i}^{-1})}=a\lVert\Delta\theta_{0}\rVert_{F}\sqrt{\sum\limits_{j=1}^{n_{x}+n_{u}}\frac{1}{\lambda_{j}^{2}(H_{i})}}\leq
a\lVert\Delta\theta_{0}\rVert_{F}\sum\limits_{j=1}^{n_{x}+n_{u}}\frac{1}{\lambda_{k}(H_{i})}\\\
&=a\lVert\Delta\theta_{0}\rVert_{F}\sum\limits_{j=1}^{n_{x}+n_{u}}\frac{1}{\lambda_{j}\left(H_{0}+\sum\limits_{k=1}^{i}D_{k}\right)}=a\lVert\Delta\theta_{0}\rVert_{F}\sum\limits_{j=1}^{n_{x}+n_{u}}\frac{1}{a+\lambda_{j}\left(\sum\limits_{k=1}^{i}D_{k}\right)}.\end{split}$
(57)

The inequality in (57) comes from the inequality of arithmetic and the
positive eigenvalues of the positive definite matrix.

$\begin{split}\lVert\Delta\theta_{i}\rVert_{F}&\leq\Delta\theta_{i}^{\mathrm{Upper}}\leq
a\lVert\Delta\theta_{0}\rVert_{F}\sum\limits_{j=1}^{n_{x}+n_{u}}\frac{1}{a+\lambda_{j}\left(\sum\limits_{k=1}^{i}D_{k}\right)}\\\
&=a\lVert\Delta\theta_{0}\rVert_{F}\sum\limits_{j=1}^{n_{x}+n_{u}}\frac{1}{a+\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}-\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}+\lambda_{j}\left(\sum\limits_{k=1}^{i}D_{k}\right)}\\\
&=\frac{a(n_{x}+n_{u})\lVert\Delta\theta_{0}\rVert_{F}}{a+\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}}+\sum\limits_{j=1}^{n_{x}+n_{u}}\underbrace{\frac{a\lVert\Delta\theta_{0}\rVert_{F}\left(\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}-\lambda_{j}\left(\sum\limits_{k=1}^{i}D_{k}\right)\right)}{\left(a+\lambda_{j}\left(\sum\limits_{k=1}^{i}D_{k}\right)\right)\left(a+\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}\right)}}_{\mathcal{E}(j)}.\end{split}$
(58)

We analyze $\mathcal{E}(j)$ by focusing on the eigenvalues
$\lambda_{j}\left(\sum\limits_{k=1}^{i}D_{k}\right)$. Because
$\lambda_{j}\left(\sum\limits_{k=1}^{i}D_{k}\right)\geq 0$ for all $j$, the
denominator of $\mathcal{E}(j)$ is positive for every $j$. According to
Definition 5, $j^{\mathrm{non}}_{i}$ of the total $n_{u}+n_{x}$ eigenvalues
satisfy the inequality
$\lfloor\frac{i}{N_{\max}}\rfloor\alpha_{\min}-\lambda_{j}\left(\sum\limits_{k=1}^{i}D_{k}\right)>0$.
This implies that this part of the numerator of $\mathcal{E}(j)$ is upper-
bounded by
$a\lVert\Delta\theta_{0}\rVert_{F}\lfloor\frac{i}{N_{\max}}\rfloor\alpha_{\min}$.
The remaining part is instead less than or equal to $0$. We can further
simplify (58) as:

$\begin{split}\lVert\Delta\theta_{i}\rVert_{F}&\leq\Delta\theta_{i}^{\mathrm{Upper}}\leq\frac{a(n_{x}+n_{u})\lVert\Delta\theta_{0}\rVert_{F}}{a+\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}}+\frac{j^{\mathrm{non}}_{i}a\lVert\Delta\theta_{0}\rVert_{F}\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}}{\left(a+\lambda_{j}\left(\sum\limits_{k=1}^{i}D_{k}\right)\right)\left(a+\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}\right)}\end{split}$
(59)

If $i\geq N_{\max}$, then from (59) we can get:

$\begin{split}\lVert\Delta\theta_{i}\rVert_{F}&\leq\Delta\theta_{i}^{\mathrm{Upper}}\leq\frac{a(n_{x}+n_{u})\lVert\Delta\theta_{0}\rVert_{F}}{a+\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}}+\frac{j^{\mathrm{non}}_{i}a\lVert\Delta\theta_{0}\rVert_{F}\lfloor\frac{i}{N_{\max}}\rfloor\alpha_{\min}}{a\left(\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}\right)}\\\
&=a(n_{x}+n_{u})\frac{\lVert\Delta\theta_{0}\rVert_{F}}{a+\lfloor\frac{i}{N_{\max}}\rfloor{\alpha_{\min}}}+\lVert\Delta\theta_{0}\rVert_{F}j^{\mathrm{non}}_{i}\end{split}$
(60)

The first inequality is obtained by leveraging positivity of the eigenvalues
in the denominator of the second term in (59). For the case $0\leq i\leq
N_{\max}$, we know that the inequality (60), which can be simplified as
$\lVert\Delta\theta_{i}\rVert_{F}\leq\Delta\theta_{i}^{\mathrm{Upper}}\leq(n_{x}+n_{u})\lVert\Delta\theta_{0}\rVert_{F}$,
still holds. The proof of Theorem 3 is concluded by using the fact that
$j^{\mathrm{non}}_{i}\leq\lVert j^{\mathrm{non}}\rVert_{\infty},\forall
i\in\mathbb{Z}_{+}$.

##  Appendix C Appendix 3

###  C.1 Proof of Theorem 4

Before proving Theorem 4, we introduce the following lemma:

###### Lemma 3

Given a stabilizable system dynamic $(\tilde{A},\tilde{B})$, and
$\tilde{P}^{*}_{(\tilde{A},\tilde{B})}$ is the solution of the DARE (5b)
formulated by the $(\tilde{A},\tilde{B})$,

  1. 1.

For any $\tilde{P}\succeq P^{*}_{(\tilde{A},\tilde{B})}$, the feedback gain
$\tilde{K}=-(R+\tilde{B}^{\top}\tilde{P}\tilde{B})^{-1}\tilde{B}^{\top}\tilde{P}\tilde{A}$
stabilizes the system, i.e. $\lVert\tilde{A}+\tilde{B}\tilde{K}\rVert_{2}<1$,

  2. 2.

Defining $\tilde{\mathcal{A}}(\tilde{P}):=[I_{n_{x}}\otimes
I_{n_{x}}-(\tilde{A}^{\top}+\tilde{B}^{\top}\tilde{K}^{\top})\otimes(\tilde{A}^{\top}+\tilde{B}^{\top}\tilde{K}^{\top})]$,
then
$\lVert\tilde{\mathcal{A}}^{-1}(\tilde{P})\rVert_{F}\leq\frac{\sqrt{n_{x}}}{1-\lVert\tilde{A}+\tilde{B}\tilde{K}\rVert^{2}_{2}}$,

  3. 3.

For any initialized $\tilde{P}_{0}\succeq P^{*}_{(\tilde{A},\tilde{B})}$ and
$\tilde{P}_{i+1}:=\mathcal{L}^{-1}_{(\tilde{A},\tilde{B},\tilde{P}_{i})}(Q+\tilde{\alpha}^{T}(\tilde{P}_{i})\tilde{\beta}^{-1}(\tilde{P}_{i})R\tilde{\beta}^{-1}(\tilde{P}_{i})\tilde{\alpha}(\tilde{P}_{i}))$
where
$\tilde{\alpha}(\tilde{P}_{i}):=\tilde{B}^{\top}\tilde{P}_{i}\tilde{A},\tilde{\beta}(\tilde{P}_{i}):=R+\tilde{B}^{\top}\tilde{P}_{i}\tilde{B}$,
there exist a constant $\tilde{\epsilon}\in[0,1)$, such that
$\frac{\sqrt{n_{x}}}{1-\tilde{\epsilon}^{2}}\geq\lVert\tilde{\mathcal{A}}(\tilde{P_{i}})\rVert_{F}$,
for all $i\in\mathbb{Z}_{+}$.

The proof of Lemma 3 is given in Section C.2. We emphasize that Lemma 3 holds
for any stabilizable system dynamic $(\tilde{A},\tilde{B})$, for instance, the
true system $(A,B)$ or a stabilizable estimate $(\hat{A}_{i},\hat{B}_{i})$.

Now we start to prove Theorem 4. From item 1 in Lemma 3, we know that $K_{1}$
stabilizes the system $(A,B)$ and thus Theorem 1 holds for the following
analysis. By leveraging Theorem 1, if $K_{1}$ stabilizes the system, then
$\forall i\in\mathbb{Z}_{+},K_{i}$ also stabilizes the system. Thus, all the
eigenvalues of $A+BK_{i}$ are inside the unit circle, i.e. $\lVert
A+BK_{i}\rVert_{2}<1~{}\forall i\in\mathbb{Z}_{+}$. Consequently,
$\lVert(A^{\top}-\alpha^{\top}(P_{i})\beta(P_{i})^{-1}B^{\top})\otimes(A^{\top}-\alpha^{\top}(P_{i})\beta(P_{i})^{-1}B^{\top})\rVert_{2}<1$,
as
$A^{\top}-\alpha^{\top}(P_{i})\beta(P_{i})^{-1}B^{\top}=(A+BK_{i+1})^{\top}$.
Then we can infer that the eigenvalues of $\mathcal{A}(P_{i})$ are
$1-\lambda((A^{\top}-\alpha^{\top}(P_{i})\beta(P_{i})^{-1}B^{\top})\otimes(A^{\top}-\alpha^{\top}(P_{i})\beta(P_{i})^{-1}B^{\top}))$,
all of which are greater than $0$. Thus, the matrix
$\mathcal{A}(P_{i}),~{}\forall i=\mathbb{Z}_{+}$ is always invertible if
$P_{0}\succeq P^{*}$.
Due to item 1 in Theorem 1, we can conclude for any $P_{i}\succeq P^{*}$ that:

$\lVert P_{i+1}-P^{*}\rVert_{F}\leq\lVert P_{i}-P^{*}\rVert_{F}.$ (61)

For any $P_{i}\neq P^{*}$, $P_{i}\neq P_{i+1}$ for all $i\in\mathbb{Z}_{+}$
because $P^{*}$ is the only equilibrium point of DARE (5b), we can conclude
there always exists $\xi_{i}\in(0,1)$ such that:

$\lVert P_{i+1}-P^{*}\rVert_{F}\leq\xi_{i}\lVert P_{i}-P^{*}\rVert_{F}.$ (62)

For $P_{i}=P^{*}$, we can also find $\xi_{i}\in(0,1)$, such that (62) holds.
From item 4 in Theorem 1, we know that $\lVert P_{i+1}-P^{*}\rVert_{F}\leq
C\lVert P_{i}-P^{*}\rVert^{2}_{F}$, where $C$ is a constant. From item 3 in
Theorem 1, we know that there exists an index $i_{c}\geq 1$, such that $\lVert
P_{i_{c}}-P^{*}\rVert_{F}<\frac{1}{C}$. Then we can always find a constant
$c=\max\\{\xi_{1},\xi_{2},...,\xi_{i_{c}},C\lVert
P_{i_{1}}-P^{*}\rVert_{F}\\}\in(0,1)$, such that $\lVert
P_{i+1}-P^{*}\rVert_{F}\leq c\lVert P_{i}-P^{*}\rVert_{F}$ for all
$i\in\mathbb{Z}_{+}$ and $P_{0}\succeq P^{*}$.

###  C.2 Proof of Lemma 3

First, we proof item 1. We introduce the Lyapunov function
$V(x_{t}):=x_{t}^{\top}\tilde{P}x_{t}$. Because of the stabilizability of
$(\tilde{A},\tilde{B})$, there exists a feedback gain $\tilde{K}^{*}$ that
stabilizes the system and also minimizes the cost in (2). From (6),
$\tilde{K}$ is the minimum of $J_{\mathrm{PI}}(K)$, then we have:

$\begin{split}&x_{t}^{\top}Qx_{t}+(\tilde{K}x_{t})^{\top}R(\tilde{K}x_{t})+(\tilde{A}x_{t}+\tilde{B}\tilde{K}x_{t})^{\top}\tilde{P}(\tilde{A}x_{t}+\tilde{B}\tilde{K}x_{t})\\\
&\leq
x_{t}^{\top}Qx_{t}+(\tilde{K}^{*}x_{t})^{\top}R(\tilde{K}^{*}x_{t})+(\tilde{A}x_{t}+\tilde{B}\tilde{K}^{*}x_{t})^{\top}\tilde{P}(\tilde{A}x_{t}+\tilde{B}\tilde{K}^{*}x_{t})\\\
&=x_{t}^{\top}P^{*}_{(\tilde{A},\tilde{B})}x_{t}+(\tilde{A}x_{t}+\tilde{B}\tilde{K}^{*}x_{t})^{\top}(\tilde{P}-P^{*}_{(\tilde{A},\tilde{B})})(\tilde{A}x_{t}+\tilde{B}\tilde{K}^{*}x_{t})\\\
&=x_{t}^{\top}\tilde{P}x_{t}-(x_{t}^{\top}(\tilde{P}-P^{*}_{(\tilde{A},\tilde{B})})x_{t}-x_{t}^{\top}(\tilde{A}+\tilde{B}\tilde{K}^{*})^{\top}(\tilde{P}-P^{*}_{(\tilde{A},\tilde{B})})(\tilde{A}+\tilde{B}\tilde{K}^{*})x_{t})\end{split}$
(63)

Subsequently, it follows that:

$\begin{split}V(x_{t+1})-V(x_{t})&=(\tilde{A}x_{t}+\tilde{B}\tilde{K}x_{t})^{\top}\tilde{P}(\tilde{A}x_{t}+\tilde{B}\tilde{K}x_{t})-x_{t}^{\top}\tilde{P}x_{t}\\\
&\leq-
x_{t}^{\top}Qx_{t}-(\tilde{K}x_{t})^{\top}R(\tilde{K}x_{t})-(x_{t}^{\top}(\tilde{P}-P^{*}_{(\tilde{A},\tilde{B})})x_{t}-x_{t}^{\top}(\tilde{A}+\tilde{B}\tilde{K}^{*})^{\top}(\tilde{P}-P^{*}_{(\tilde{A},\tilde{B})})(\tilde{A}+\tilde{B}\tilde{K}^{*})x_{t})\\\
&\leq 0\end{split}$ (64)

The first inequality comes from (63) and the second inequality is because all
eigenvalues of $\tilde{A}+\tilde{B}\tilde{K}^{*}$ are inside the unit circle.
From [35, Lemma 2.2], we know that
$(\tilde{P}-P^{*}_{(\tilde{A},\tilde{B})})\succeq(\tilde{A}+\tilde{B}\tilde{K}^{*})^{\top}(\tilde{P}-P^{*}_{(\tilde{A},\tilde{B})})(\tilde{A}+\tilde{B}\tilde{K}^{*})$.
From (64), we can conclude that, $\tilde{K}$ stabilizes the system
$(\tilde{A},\tilde{B})$.
Now, we proceed with the proof of item 2. As established in item 1, all
eigenvalues of the matrix
$(\tilde{A}^{\top}+\tilde{B}^{\top}\tilde{K}^{\top})\otimes(\tilde{A}^{\top}+\tilde{B}^{\top}\tilde{K}^{\top})$
are inside of the unit circle with [30, 517]. Therefore, we can derive:

$\begin{split}\lVert\tilde{\mathcal{A}}^{-1}(\tilde{P})\rVert_{F}&\leq\sqrt{n_{x}}\lVert\tilde{\mathcal{A}}^{-1}(\tilde{P})\rVert_{2}=\sqrt{n_{x}}\lVert\sum\limits_{k=0}^{\infty}[(\tilde{A}^{\top}+\tilde{B}^{\top}\tilde{K}^{\top})\otimes(\tilde{A}^{\top}+\tilde{B}^{\top}\tilde{K}^{\top})]^{k}\rVert_{2}\\\
&\leq\sqrt{n_{x}}\sum\limits_{k=0}^{\infty}\lVert[(\tilde{A}^{\top}+\tilde{B}^{\top}\tilde{K}^{\top})\otimes(\tilde{A}^{\top}+\tilde{B}^{\top}\tilde{K}^{\top})]^{k}\rVert_{2}\\\
&\leq\sqrt{n_{x}}\sum\limits_{k=0}^{\infty}\lVert\tilde{A}^{\top}+\tilde{B}^{\top}\tilde{K}^{\top}\rVert_{2}^{2k}=\sqrt{n_{x}}\sum\limits_{k=0}^{\infty}\lVert\tilde{A}^{\top}+\tilde{B}^{\top}\tilde{K}^{\top}\rVert_{2}^{2k}\\\
&\leq\frac{\sqrt{n_{x}}}{1-\lVert\tilde{A}+\tilde{B}\tilde{K}\rVert^{2}_{2}}.\end{split}$
(65)

The first inequality follows from the definitions of induced 2-norm and
Frobenius norm. The first equality comes from [30, Eq. 186]. The second and
third inequalities come from the sub-additive and sub-multiplicative of matrix
norms.This shows Item 2 in Lemma 3. By combining item 1 in Lemma 3 with
Theorem 1, it follows that $\hat{K}_{1}$ computed from $\hat{P}_{0}$
stabilizes the system and $\tilde{P}_{i}$ converges to
$P^{*}_{(\tilde{A},\tilde{B})}$, forming a convergent sequence
$\\{\tilde{P}_{i}\\}$. Then we can always find
$\tilde{\epsilon}:=\sup\\{\lVert\tilde{A}+\tilde{B}\tilde{K}_{i}\rVert_{2}\\}\in[0,1)$,
such that
$\frac{\sqrt{n_{x}}}{1-\tilde{\epsilon}^{2}}\geq\lVert\tilde{\mathcal{A}}(\tilde{P_{i}})\rVert_{F}$,
for all $i\in\mathbb{Z}_{+}$. Consequently, item 3 in Lemma 3 is also proven.

##  Appendix D Appendix 4

###  D.1 Proof of Theorem 5

The pair $(A,B)$ is stabilizable, implying the existence of a gain
$K_{\mathrm{st}}$ such that $\lVert A+BK_{\mathrm{st}}\rVert_{2}<1$. Let
$L:=A+BK_{\mathrm{st}}$. According to Chapter 6 in [36], the eigenvalues of
the matrix $L\in\mathbb{R}^{n_{x}\times n_{x}}$ vary continuously with the
entries of $L$. Therefore, there exists a $\Delta L$ such that $\lVert
L+\Delta L\rVert_{2}<1$. Since $\lVert L\rVert_{2}+\lVert\Delta
L\rVert_{2}\geq\lVert L+\Delta L\rVert_{2}$, it follows that if $\lVert\Delta
L\rVert_{2}<1-\lVert L\rVert_{2}$, then $\lVert L+\Delta L\rVert_{2}<1$. If
$\lVert\Delta L\rVert_{2}\geq\lVert\Delta A_{i}+\Delta
B_{i}K_{\mathrm{st}}\rVert_{2}$, where $\Delta A_{i}:=\hat{A}_{i}-A$, $\Delta
B_{i}:=\hat{B}_{i}-B$ and $(\hat{A}_{i},\hat{B}_{i})$ are the estimates from
RLS, we can conclude $\lVert A+BK_{\mathrm{st}}+\Delta A_{i}+\Delta
B_{i}K_{\mathrm{st}}\rVert_{2}=\lVert\hat{A}_{i}+\hat{B}_{i}K_{\mathrm{st}}\rVert_{2}<1$.
Because of $\Delta\theta_{i}=\left[\Delta A_{i},\Delta B_{i}\right]$, we know
that:

$\lVert\Delta A_{i}\rVert_{2}~{}\mathrm{or}~{}\lVert\Delta
B_{i}\rVert_{2}\leq\lVert\Delta\theta_{i}\rVert_{2}.$ (66)

If $\lVert\Delta\theta_{i}\rVert_{2}\leq\frac{\lVert\Delta
L\rVert_{2}}{1+\lVert K_{\mathrm{st}}\rVert_{2}}$, then we have:

$\begin{split}\lVert\Delta A_{i}+\Delta
B_{i}K_{\mathrm{st}}\rVert_{2}&\leq\lVert\Delta A_{i}\rVert_{2}+\lVert\Delta
B_{i}\rVert_{2}\lVert K_{\mathrm{st}}\rVert_{2}\\\
&\leq\lVert\Delta\theta_{i}\rVert_{2}+\lVert\Delta\theta_{i}\rVert_{2}\lVert
K_{\mathrm{st}}\rVert_{2}\leq\lVert\Delta L\rVert_{2}.\end{split}$ (67)

From (67), $K_{\mathrm{st}}$ stabilizes the system
$(\hat{A}_{i},\hat{B}_{i})$, and thus, $(\hat{A}_{i},\hat{B}_{i})$ is
stabilizable. By Theorem 2, we know that when the sequence is locally
persistent with respect to any $N,M,\alpha$, then
$\lim\limits_{i\rightarrow\infty}\Delta\theta_{i}=0$. This means there exists
an index $i_{\mathrm{st}}$ such that for all $i\geq i_{\mathrm{st}}$,
$\lVert\Delta\theta_{i}\rVert_{2}\leq\frac{\lVert\Delta L\rVert_{2}}{1+\lVert
K_{\mathrm{st}}\rVert_{2}}$, then the estimates $(\hat{A}_{i},\hat{B}_{i})$
are always stabilizable. The proof is complete.

###  D.2 Proof of Theorem 6

For proving (30b) we can simply use Theorem (3). Indeed this holds for any
data sequence in input to the RLS scheme, hence also for the one generated by
IPI. We can the focus just on (30a). At episode $i$, $\hat{P}_{i+1}$ is
updated with the estimates $(\hat{A}_{i},\hat{B}_{i})$ and $\hat{P}_{i}$. We
define $\alpha_{i}(\hat{P}_{i}):=\hat{B}_{i}^{\top}\hat{P}_{i}\hat{A}_{i}$ and
$\beta_{i}(\hat{P}_{i})=\beta_{i}^{\top}(\hat{P}_{i}):=R+\hat{B}_{i}^{\top}\hat{P}_{i}\hat{B}_{i}$.
First, we must check if the inverse operation
$\mathcal{L}^{-1}_{(\hat{A}_{i},\hat{B}_{i},P_{i})}$ based on a stabilizable
$(\hat{A}_{i},\hat{B}_{i})$ in (27) still exists. Because of Assumption 2 and
item 1 in Lemma 3, we know that $\hat{K}_{i}$ stabilizes the system
$(\hat{A}_{i},\hat{B}_{i})$. Thus, the inverse operation
$\mathcal{L}^{-1}_{(\hat{A}_{i},\hat{B}_{i},\hat{P}_{i})}$ exists and
$\hat{P}_{i+1}$ can be calculated as follows:

$\begin{split}\hat{P}_{i+1}&=\mathcal{L}^{-1}_{(\hat{A}_{i},\hat{B}_{i},\hat{P}_{i})}(Q+\alpha_{i}^{\top}(\hat{P}_{i})\beta_{i}^{-1}(\hat{P}_{i})R\beta_{i}^{-1}(\hat{P}_{i})\alpha_{i}(\hat{P}_{i})).\end{split}$
(68)

We rewrite (68) as two terms, one term denotes the update of $\hat{P}_{i}$
with respect to (27) formulated by the true system $(A,B)$, the other term
denotes the difference between (27) formulated by $(\hat{A}_{i},\hat{B}_{i})$
and $(A,B)$:

$\begin{split}\hat{P}_{i+1}&=\mathcal{L}^{-1}_{(A,B,\hat{P}_{i})}(Q+\alpha^{\top}P(\hat{P}_{i})\beta^{-1}(\hat{P}_{i})R\beta^{-1}(\hat{P}_{i})\alpha(\hat{P}_{i}))+\varepsilon(\Delta
A_{i},\Delta B_{i}),\end{split}$ (69)

where

$\begin{split}\varepsilon(\Delta A_{i},\Delta
B_{i}):=&\mathcal{L}^{-1}_{(\hat{A}_{i},\hat{B}_{i},\hat{P}_{i})}(Q+\alpha_{i}^{\top}(\hat{P}_{i})\beta_{i}^{-1}(\hat{P}_{i})R\beta_{i}^{-1}(\hat{P}_{i})\alpha_{i}(\hat{P}_{i}))\\\
&-\mathcal{L}^{-1}_{(A,B,\hat{P}_{i})}(Q+\alpha^{\top}(\hat{P}_{i})\beta^{-1}(\hat{P}_{i})R\beta^{-1}(\hat{P}_{i})\alpha(\hat{P}_{i})).\end{split}$
(70)

Now, we aim to find the upper bound of $\lVert\varepsilon(\Delta A_{i},\Delta
B_{i})\rVert_{F}$ in terms of $\lVert\Delta\theta_{i}\rVert_{F}$. The
following lemma from [20, Equation 19] is used, when $X,X+\Delta X$ are
invertible:

$\lVert X^{-1}Y-(X+\Delta X)^{-1}(Y+\Delta Y)\rVert_{F}\leq\lVert
X^{-1}\rVert_{F}(\lVert\Delta Y\rVert_{F}+\lVert(X+\Delta
X)^{-1}\rVert_{F}\lVert(Y+\Delta Y)\rVert_{F}\lVert\Delta X\rVert_{F}).$ (71)

With (16) and (54), we can get:

$\lVert\Delta A_{i}\rVert_{F}~{}\mathrm{or}~{}\lVert\Delta
B_{i}\rVert_{F}\leq\lVert\Delta\theta_{i}\rVert_{F}\leq\Delta\theta^{\mathrm{Upper}}_{i}\leq\Delta\theta^{\mathrm{Upper}}_{0}.$
(72)

We define the updated gain $\hat{K}_{i+1}$ as the gain computed with the
current estimated system matrix $(\hat{A}_{i},\hat{B}_{i})$ and $\hat{P}_{i}$
and $\bar{K}_{i+1}$ as the gain computed with $(A,B)$ and $\hat{P}_{i}$.

$\begin{split}\lVert\Delta
K_{i+1}\rVert_{F}&=\lVert\hat{K}_{i+1}-\bar{K}_{i+1}\rVert_{F}\\\
&=\lVert(R+B^{\top}\hat{P}_{i}B)^{-1}B^{\top}\hat{P_{i}}A-(R+B^{\top}\hat{P}_{i}B+\Delta_{\beta_{i}})^{-1}(B^{\top}\hat{P}_{i}A+\Delta_{\alpha_{i}})\rVert_{F}\\\
&\leq\lVert(R+B^{\top}\hat{P}_{i}B)^{-1}\rVert_{F}(\lVert\Delta_{\alpha_{i}}\rVert_{F}+\lVert(R+\hat{B}_{i}^{\top}\hat{P}_{i}\hat{B}_{i})^{-1}\rVert_{F}\lVert\hat{B}_{i}^{\top}\hat{P}_{i}\hat{A}_{i}\rVert_{F}\lVert\Delta_{\beta_{i}}\rVert_{F}),\end{split}$
(73)

where $\Delta_{\beta_{i}},\Delta_{\alpha_{i}}$ are given as

$\Delta_{\beta_{i}}=\Delta B_{i}^{\top}\hat{P}_{i}\Delta
B_{i}+B^{\top}\hat{P}_{i}\Delta B_{i}+\Delta B_{i}^{\top}\hat{P}_{i}B,$ (74)
$\Delta_{\alpha_{i}}=\Delta B_{i}^{\top}\hat{P}_{i}\Delta
A_{i}+B^{\top}\hat{P}_{i}\Delta A_{i}+\Delta B_{i}^{\top}\hat{P}_{i}A.$ (75)

The inequality in (73) comes from (71). Given any stabilizable
$(\hat{A}_{i},\hat{B}_{i})$, from Theorem 1 and Lemma 3, we know that
$\lVert\hat{P}_{i+1}\rVert_{F}$ is bounded by $\lVert\hat{P}_{i}\rVert_{F}$.
Then we can get $\lVert\hat{P}_{i}\rVert_{F}\leq\lVert\hat{P}_{0}\rVert_{F}$.
Together with (74) (75) and (72), the norm of
$\lVert\Delta_{\beta_{i}}\rVert_{F},\lVert\Delta_{\alpha_{i}}\rVert_{F}$ are
bounded by:

$\begin{split}\lVert\Delta_{\beta_{i}}\rVert_{F}&=\lVert\Delta
B_{i}^{\top}\hat{P}_{i}\Delta B_{i}+B^{\top}\hat{P}_{i}\Delta B_{i}+\Delta
B_{i}^{\top}\hat{P}_{i}B\rVert_{F}\\\
&\leq\lVert\Delta\theta_{i}\rVert_{F}\underbrace{\lVert\hat{P}_{0}\rVert_{F}(\Delta\theta^{\mathrm{Upper}}_{i}+2\lVert
B\rVert_{F})}_{=:\delta_{1}}=\delta_{1}\lVert\Delta\theta_{i}\rVert_{F},\end{split}$
(76) $\begin{split}\lVert\Delta_{\alpha_{i}}\rVert_{F}&=\lVert\Delta
B_{i}^{\top}\hat{P}_{i}\Delta A_{i}+B^{\top}\hat{P}_{i}\Delta A_{i}+\Delta
B_{i}^{\top}\hat{P}_{i}A\rVert_{F}\\\
&\leq\lVert\Delta\theta_{i}\rVert_{F}\underbrace{\lVert\hat{P}_{0}\rVert_{F}(\Delta\theta^{\mathrm{Upper}}_{i}+\lVert
B\rVert_{F}+\lVert
A\rVert_{F})}_{=:\delta_{2}}=\delta_{2}\lVert\Delta\theta_{i}\rVert_{F}.\end{split}$
(77)

The inequalities in (76) and (77) come from the sub-multiplicative property
and item 1 in Theorem 1. Then (73) can be further simplified as:

$\begin{split}\lVert\hat{K}_{i+1}-\bar{K}_{i+1}\rVert_{F}&\leq\lVert(R+B^{\top}\hat{P}_{i}B)^{-1}\rVert_{F}(\lVert\Delta_{\alpha_{i}}\rVert_{F}+\lVert(R+\hat{B}_{i}^{\top}\hat{P}_{i}\hat{B}_{i})^{-1}\rVert_{F}\lVert\hat{B}_{i}^{\top}\hat{P}_{i}\hat{A}_{i}\rVert_{F}\lVert\Delta_{\beta_{i}}\rVert_{F})\\\
&\leq\lVert R^{-1}\rVert_{F}(\lVert\Delta_{\alpha_{i}}\rVert_{F}+\lVert
R^{-1}\rVert_{F}\lVert\Delta
B_{i}+B\rVert_{F}\lVert\hat{P}_{i}\rVert_{F}\lVert\Delta
A_{i}+A\rVert_{F}\lVert\Delta_{\beta_{i}}\rVert_{F})\\\
&\leq\delta_{3}\lVert\Delta\theta_{i}\rVert_{F},\end{split}$ (78)

where
$\delta_{3}:=\delta_{33}(\Delta\theta^{\mathrm{Upper}}_{i})^{3}+\delta_{32}(\Delta\theta^{\mathrm{Upper}}_{i})^{2}+\delta_{31}\Delta\theta^{\mathrm{Upper}}_{i}+\delta_{30}$,
with $\delta_{33}:=\lVert R^{-1}\rVert_{F}\lVert\hat{P}_{0}\rVert_{F}$,
$\delta_{32}:=2\lVert R^{-1}\rVert_{F}\lVert\hat{P}_{0}\rVert_{F}(\lVert
A\rVert_{F}+\lVert B\rVert_{F})$, $\delta_{31}:=(\lVert
R^{-1}\rVert_{F}\lVert\hat{P}_{0}+\lVert
R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2}\left[(\lVert
A\rVert_{F}+\lVert B\rVert_{F})^{2}+\lVert A\rVert_{F}\lVert
B\rVert_{F}\right]$,
$\delta_{30}:=2\lVert R^{-1}\rVert_{F}\lVert\hat{P}_{0}\rVert_{F}\lVert
B\rVert_{F}+\lVert R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2}\lVert
A\rVert_{F}\lVert B\rVert_{F}(\lVert A\rVert_{F}+\lVert B\rVert_{F})$.

The first inequality comes from the positive semidefiniteness of
$B^{\top}\hat{P}_{i}B$ and $\hat{B}_{i}^{\top}\hat{P}_{i}\hat{B}_{i}$. The
second inequality comes from (72) (76) and (77). In (26),
$\mathcal{A}(\hat{P}_{i})=[{I}_{n_{x}}\otimes{I}_{n_{x}}-(A^{\top}+\bar{K}_{i}^{\top}B^{\top})\otimes(A^{\top}+\bar{K}_{i}^{\top}B^{\top})]$.
Similarly, we define
$\mathcal{A}_{i}(\hat{P}_{i}):=[{I}_{n_{x}}\otimes{I}_{n_{x}}-(\hat{A}_{i}^{\top}+\hat{K}_{i}^{\top}\hat{B}_{i}^{\top})\otimes(\hat{A}_{i}^{\top}+\hat{K}_{i}^{\top}\hat{B}_{i}^{\top})]$
and
$\Delta\mathcal{A}_{i}(\hat{P}_{i}):=\mathcal{A}_{i}(\hat{P}_{i})-\mathcal{A}(\hat{P}_{i})$,

$\begin{split}\lVert\Delta\mathcal{A}_{i}(\hat{P_{i}})\rVert_{F}&=\lVert\mathcal{A}(\hat{P_{i}})-\mathcal{A}_{i}(\hat{P_{i}})\rVert_{F}\\\
&=\lVert(\hat{A}_{i}+\hat{B}_{i}\tilde{K}_{i+1})\otimes(\hat{A}_{i}+\hat{B}_{i}\tilde{K}_{i+1})-(A+B\bar{K}_{i+1})\otimes(A+B\bar{K}_{i+1}))\rVert_{F}\\\
&=\lVert(A+\Delta A_{i}+(B+\Delta
B_{i})(\bar{K}_{i+1}+\Delta{K}_{i+1})\otimes(\cdot)-(A+B\bar{K}_{i+1})\otimes(A+B\bar{K}_{i+1}))\rVert_{F}\\\
&=\lVert(A+B\bar{K}_{i+1}+\underbrace{\Delta A_{i}+B\Delta{K}_{i+1}+\Delta
B_{i}(\bar{K}_{i+1}+\Delta{K}_{i+1}}_{=:\mathcal{C}_{i}})\otimes(\cdot)-(A+B\bar{K}_{i+1})\otimes(A+B\bar{K}_{i+1}))\rVert_{F}.\end{split}$
(79)

Because $\lVert\bar{K}_{i+1}\rVert_{F}\leq\lVert R^{-1}\rVert_{F}\lVert
B^{T}\rVert_{F}\lVert\hat{P}_{i}\rVert_{F}\lVert A\rVert_{F}\leq\lVert
R^{-1}\rVert_{F}\lVert B^{T}\rVert_{F}\lVert\hat{P}_{0}\rVert_{F}\lVert
A\rVert_{F}$, then
$\lVert\mathcal{C}_{i}\rVert_{F}\leq\delta_{4}\lVert\Delta\theta_{i}\rVert_{F}$,
where
$\delta_{4}:=\delta_{44}(\Delta\theta^{\mathrm{Upper}}_{i})^{4}+\delta_{43}(\Delta\theta^{\mathrm{Upper}}_{i})^{3}+\delta_{42}(\Delta\theta^{\mathrm{Upper}}_{i})^{2}+\delta_{41}\Delta\theta^{\mathrm{Upper}}_{i}+\delta_{40}$,
with $\delta_{44}:=\delta_{33}$, $\delta_{43}:=\delta_{32}+\lVert
B\rVert_{F}\delta_{33}$, $\delta_{42}:=\delta_{31}+\lVert
B\rVert_{F}\delta_{32}$,
$\delta_{41}:=\delta_{30}+\lVert B\rVert_{F}\delta_{31}$, $\delta_{40}:=\lVert
B\rVert_{F}\delta_{30}+\lVert R^{-1}\rVert_{F}\lVert A\rVert_{F}\lVert
B\rVert_{F}\lVert\hat{P}_{0}\rVert_{F}+1$.

Consequently, (79) can be further simplified as:

$\begin{split}\lVert\Delta\mathcal{A}_{i}(\hat{P_{i}})\rVert_{F}&=\lVert\mathcal{C}_{i}\otimes(A+B\bar{K}_{i+1})+(A+B\bar{K}_{i+1})\otimes\mathcal{C}_{i}+\mathcal{C}_{i}\otimes\mathcal{C}_{i}\rVert_{F}\\\
&\leq 2\lVert\mathcal{C}_{i}\rVert_{F}\lVert
A+B\bar{K}_{i+1}\rVert_{F}+\lVert\mathcal{C}_{i}\rVert_{F}^{2}\\\
&\leq\delta_{5}\lVert\Delta\theta_{i}\rVert_{F},\end{split}$ (80)

where
$\delta_{5}:=\delta_{58}(\Delta\theta^{\mathrm{Upper}}_{i})^{8}+\delta_{57}(\Delta\theta^{\mathrm{Upper}}_{i})^{7}+\delta_{56}(\Delta\theta^{\mathrm{Upper}}_{i})^{6}+\delta_{55}(\Delta\theta^{\mathrm{Upper}}_{i})^{5}+\delta_{54}(\Delta\theta^{\mathrm{Upper}}_{i})^{4}+\delta_{53}(\Delta\theta^{\mathrm{Upper}}_{i})^{3}+\delta_{52}(\Delta\theta^{\mathrm{Upper}}_{i})^{2}+\delta_{51}(\Delta\theta^{\mathrm{Upper}}_{i})^{1}+\delta_{50}$,
with $\delta_{58}:=\delta_{44}\delta_{44}$,
$\delta_{57}:=2\delta_{44}\delta_{43}$,
$\delta_{56}:=2\delta_{44}\delta_{42}+\delta_{43}\delta_{43}$,
$\delta_{55}:=2\delta_{44}\delta_{41}+2\delta_{43}\delta_{42}$,
$\delta_{54}:=\delta_{44}\delta_{40}+2\delta_{43}\delta_{41}+\delta_{42}\delta_{42}+2(\lVert
A\rVert_{F}+\lVert R^{-1}\rVert_{F}\lVert A\rVert_{F}\lVert
B\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F})\delta_{44}$,
$\delta_{53}:=2\delta_{43}\delta_{40}+2\delta_{42}\delta_{41}+2(\lVert
A\rVert_{F}+\lVert R^{-1}\rVert_{F}\lVert A\rVert_{F}\lVert
B\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F})\delta_{43}$,
$\delta_{52}:=2\delta_{42}\delta_{40}+\delta_{41}\delta_{41}+2(\lVert
A\rVert_{F}+\lVert R^{-1}\rVert_{F}\lVert A\rVert_{F}\lVert
B\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F})\delta_{42}$,
$\delta_{51}:=2\delta_{41}\delta_{40}+2(\lVert A\rVert_{F}+\lVert
R^{-1}\rVert_{F}\lVert A\rVert_{F}\lVert
B\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F})\delta_{41}$,
$\delta_{50}:=\delta_{40}\delta_{40}+2(\lVert A\rVert_{F}+\lVert
R^{-1}\rVert_{F}\lVert A\rVert_{F}\lVert
B\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F})\delta_{40}$.

The first inequality comes from $\lVert M\otimes N\rVert_{F}=\lVert
M\rVert_{F}\lVert N\rVert_{F}$ and the second inequality comes from (78).
Defining
$\tilde{K}_{i+1}^{\top}R\tilde{K}_{i+1}:=\bar{K}_{i+1}^{\top}R\bar{K}_{i+1}+\Delta_{KRK}$
and together with (78), we can also get:

$\begin{split}\lVert\Delta_{KRK}\rVert_{F}&=\lVert(\bar{K}_{i+1}+\Delta{K}_{i+1})^{\top}R(\bar{K}_{i+1}+\Delta{K}_{i+1})-\bar{K}_{i+1}^{\top}R\bar{K}_{i+1}\rVert_{F}\\\
&=\lVert\bar{K}_{i+1}^{\top}R\Delta{K}_{i+1}+\Delta{K}_{i+1}^{\top}R\bar{K}_{i+1}+\Delta{K}_{i+1}^{\top}R\Delta{K}_{i+1}\rVert_{F}\\\
&\leq\delta_{6}\lVert\Delta\theta_{i}\rVert_{F},\end{split}$ (81)

where
$\delta_{6}:=\delta_{66}(\Delta\theta^{\mathrm{Upper}}_{i})^{6}+\delta_{65}(\Delta\theta^{\mathrm{Upper}}_{i})^{5}+\delta_{64}(\Delta\theta^{\mathrm{Upper}}_{i})^{4}+\delta_{63}(\Delta\theta^{\mathrm{Upper}}_{i})^{3}+\delta_{62}(\Delta\theta^{\mathrm{Upper}}_{i})^{2}+\delta_{61}(\Delta\theta^{\mathrm{Upper}}_{i})^{1}+\delta_{60}$,
with $\delta_{66}:=\lVert R\rVert_{F}\delta_{33}\delta_{33}$,
$\delta_{65}:=2\lVert R\rVert_{F}\delta_{33}\delta_{32}$,
$\delta_{64}:=2\lVert R\rVert_{F}\delta_{33}\delta_{31}+\lVert
R\rVert_{F}\delta_{32}\delta_{32}$, $\delta_{63}:=2\lVert
R\rVert_{F}\delta_{33}\delta_{30}+2\lVert
R\rVert_{F}\delta_{32}\delta_{31}+2\lVert
B\rVert_{F}\lVert\hat{P}_{0}\rVert_{F}\lVert A\rVert_{F}\delta_{33}$,
$\delta_{62}:=\lVert R\rVert_{F}\delta_{31}\delta_{31}+2\lVert
R\rVert_{F}\delta_{32}\delta_{30}+2\lVert
B\rVert_{F}\lVert\hat{P}_{0}\rVert_{F}\lVert A\rVert_{F}\delta_{32}$,
$\delta_{61}=2\lVert R\rVert_{F}\delta_{31}\delta_{30}+2\lVert
B\rVert_{F}\lVert\hat{P}_{0}\rVert_{F}\lVert A\rVert_{F}\delta_{31}$,
$\delta_{60}:=\lVert R\rVert_{F}\delta_{30}\delta_{30}+2\lVert
B\rVert_{F}\lVert\hat{P}_{0}\rVert_{F}\lVert A\rVert_{F}\delta_{30}$.

We plug (70) (71) (80) (81) into (71), then we can obtain:

$\begin{split}\lVert\varepsilon(\Delta A_{i},\Delta
B_{i})\rVert_{F}&=\lVert\mathcal{A}^{-1}(\hat{P_{i}})(Q+\bar{K}_{i+1}^{\top}R\bar{K}_{i+1})-\mathcal{A}^{-1}_{i}(\hat{P_{i}})(Q+\tilde{K}_{i+1}^{\top}R\tilde{K}_{i+1})\rVert_{F}\\\
&=\lVert\mathcal{A}^{-1}(\hat{P}_{i})(Q+\bar{K}_{i+1}^{\top}R\bar{K}_{i+1})-(\mathcal{A}(\hat{P}_{i})+\Delta\mathcal{A}_{i}(\hat{P}_{i}))^{-1}(Q+\bar{K}_{i+1}^{\top}R\bar{K}_{i+1}+\Delta_{KRK})\rVert_{F}\\\
&\leq\lVert\mathcal{A}^{-1}(\hat{P}_{i})\rVert_{F}(\delta_{6}+\delta_{5}\lVert\mathcal{A}^{-1}_{i}(\hat{P}_{i})\rVert_{F}\lVert
Q+\bar{K}_{i+1}^{\top}R\bar{K}_{i+1}\rVert_{F})\lVert\Delta\theta_{i}\rVert_{F}.\end{split}$
(82)

From item 3 in Lemma 3, we define $\epsilon:=\sup\\{\lVert
A+B\hat{K}_{i}\rVert_{2}\\}\in[0,1)$, such that
$\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\geq\lVert\mathcal{A}^{-1}(\hat{P_{i}})\rVert_{F}$,
for all $i\in\mathbb{Z}_{+}$. From item 2 in Lemma 3, we know that
$\hat{K}_{i}$ stabilizes the system $(\hat{A}_{i},\hat{B}_{i})$, i.e.
$\epsilon_{i}:=\lVert\hat{A}_{i}+\hat{B}_{i}\hat{K}_{i}\rVert_{2}\in[0,1)$,
for all $i\in\mathbb{Z}_{+}$. Then we can always find a
$\epsilon_{\max}:=\sup\\{\epsilon_{i}\\}$, such that
$\lVert\mathcal{A}^{-1}_{i}(\hat{P_{i}})\rVert_{F}\leq\frac{\sqrt{n_{x}}}{1-\epsilon_{\max}^{2}}$.
Now we can further simplify (82):

$\begin{split}\lVert\varepsilon(\Delta A_{i},\Delta
B_{i})\rVert_{F}&\leq\lVert\mathcal{A}^{-1}(\hat{P_{i}})\rVert_{F}(\delta_{6}+\delta_{5}\lVert\mathcal{A}^{-1}_{i}(\hat{P_{i}})\rVert_{F}\lVert
Q+\bar{K}_{i+1}^{\top}R\bar{K}_{i+1}\rVert_{F})\lVert\Delta\theta_{i}\rVert_{F}\\\
&\leq\underbrace{\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}(\delta_{6}+\delta_{5}\frac{\sqrt{n_{x}}}{1-\epsilon_{\max}^{2}}(\lVert
Q\rVert_{F}+\lVert\bar{K}_{i+1}\rVert_{F}\lVert
R\rVert_{F}\lVert\bar{K}_{i+1}\rVert_{F}))}_{=:\sigma_{i}}\lVert\Delta\theta_{i}\rVert_{F}\\\
&=\sigma_{i}\lVert\Delta\theta_{i}\rVert_{F}\leq\sigma_{i}\Delta\theta_{i}^{\mathrm{Upper}},\end{split}$
(83)

where
$\sigma_{i}=\sum\limits_{k=0}^{8}\rho_{k}(\Delta\theta^{\mathrm{Upper}}_{i})^{k}$
and the detailed expressions of $\rho_{k}>0$ are given as follows:
$\rho_{8}:=\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\frac{\sqrt{n_{x}}}{1-\epsilon_{max}^{2}}(\lVert
Q\rVert_{F}+\lVert A\rVert_{F}^{2}\lVert B\rVert_{F}^{2}\lVert
R\rVert_{F}\lVert
R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2})\delta_{58}$,
$\rho_{7}:=\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\frac{\sqrt{n_{x}}}{1-\epsilon_{max}^{2}}(\lVert
Q\rVert_{F}+\lVert A\rVert_{F}^{2}\lVert B\rVert_{F}^{2}\lVert
R\rVert_{F}\lVert
R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2})\delta_{57}$,
$\rho_{6}:=\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\delta_{66}+\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\frac{\sqrt{n_{x}}}{1-\epsilon_{max}^{2}}(\lVert
Q\rVert_{F}+\lVert A\rVert_{F}^{2}\lVert B\rVert_{F}^{2}\lVert
R\rVert_{F}\lVert
R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2})\delta_{56}$,
$\rho_{5}:=\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\delta_{65}+\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\frac{\sqrt{n_{x}}}{1-\epsilon_{max}^{2}}(\lVert
Q\rVert_{F}+\lVert A\rVert_{F}^{2}\lVert B\rVert_{F}^{2}\lVert
R\rVert_{F}\lVert
R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2})\delta_{55}$,
$\rho_{4}:=\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\delta_{64}+\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\frac{\sqrt{n_{x}}}{1-\epsilon_{max}^{2}}(\lVert
Q\rVert_{F}+\lVert A\rVert_{F}^{2}\lVert B\rVert_{F}^{2}\lVert
R\rVert_{F}\lVert
R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2})\delta_{54}$,
$\rho_{3}:=\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\delta_{63}+\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\frac{\sqrt{n_{x}}}{1-\epsilon_{max}^{2}}(\lVert
Q\rVert_{F}+\lVert A\rVert_{F}^{2}\lVert B\rVert_{F}^{2}\lVert
R\rVert_{F}\lVert
R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2})\delta_{53}$,
$\rho_{2}:=\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\delta_{62}+\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\frac{\sqrt{n_{x}}}{1-\epsilon_{max}^{2}}(\lVert
Q\rVert_{F}+\lVert A\rVert_{F}^{2}\lVert B\rVert_{F}^{2}\lVert
R\rVert_{F}\lVert
R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2})\delta_{52}$,
$\rho_{1}:=\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\delta_{61}+\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\frac{\sqrt{n_{x}}}{1-\epsilon_{max}^{2}}(\lVert
Q\rVert_{F}+\lVert A\rVert_{F}^{2}\lVert B\rVert_{F}^{2}\lVert
R\rVert_{F}\lVert
R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2})\delta_{51}$,
$\rho_{0}:=\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\delta_{60}+\frac{\sqrt{n_{x}}}{1-\epsilon^{2}}\frac{\sqrt{n_{x}}}{1-\epsilon_{max}^{2}}(\lVert
Q\rVert_{F}+\lVert A\rVert_{F}^{2}\lVert B\rVert_{F}^{2}\lVert
R\rVert_{F}\lVert
R^{-1}\rVert_{F}^{2}\lVert\hat{P}_{0}\rVert_{F}^{2})\delta_{50}.$

Now, we can go back to (69): for any $i\in\mathbb{Z}_{+}$

$\begin{split}\lVert\hat{P}_{i+1}-P^{*}\rVert_{F}&\leq\lVert\mathcal{L}^{-1}_{(A,B,\hat{P}_{i})}(Q+\alpha^{\top}(\hat{P}_{i})\beta^{-1}(\hat{P}_{i})R\beta^{-1}(\hat{P}_{i})\alpha(\hat{P}_{i}))-P^{*}\rVert_{F}+\lVert\varepsilon(\Delta
A_{i},\Delta B_{i})\rVert_{F}\\\ &\leq
c\lVert\hat{P}_{i}-P^{*}\rVert_{F}+\sigma_{i}\lVert\Delta\theta_{i}\rVert_{F}\leq
c\lVert\hat{P}_{i}-P^{*}\rVert_{F}+\underbrace{\sigma_{i}\Delta\theta_{i}^{\mathrm{Upper}}}_{=:\Omega_{i}}.\end{split}$
(84)

The first inequality comes from taking the norm of (69) and Theorem 5, and the
second inequality comes from (84). Then we recursively apply (84) and get:

$\begin{split}\lVert\hat{P}_{i}-P^{*}\rVert_{F}&\leq
c\lVert\hat{P}_{i-1}-P^{*}\rVert_{F}+\Omega_{i-1}\leq
c^{2}\lVert\hat{P}_{i-2}-P^{*}\rVert_{F}+(1+c)\lVert\Omega\rVert_{\infty}\\\
&\leq...\leq
c^{i}\lVert\hat{P}_{0}-P^{*}\rVert_{F}+(1+c+c^{2}+...+c^{i-1})\lVert\Omega\rVert_{\infty}\leq
c^{i}\lVert\hat{P}_{0}-P^{*}\rVert+\frac{1}{1-c}\lVert\Omega\rVert_{\infty}.\end{split}$
(85)

Then we finish the proof and get the final result:

$\lVert\hat{P}_{i}-P^{*}\rVert_{F}\leq\beta\left(\lVert\hat{P}_{0}-P^{*}\rVert_{F},i\right)+\gamma\left(\lVert\Omega\rVert_{\infty}\right),$
(86)

where
$\beta(\lVert\hat{P}_{0}-P^{*}\rVert,i):=c^{i}\lVert\hat{P}_{0}-P^{*}\rVert_{F}$
is $\mathcal{KL}$ function and
$\gamma(\lVert\Omega\rVert_{\infty}):=\frac{1}{1-c}\lVert\Omega\rVert_{\infty}$
is a $\mathcal{K}$ function.

###  D.3 Proof of Corollary 3

From Lemma 1 and Corollary 1, we know that the sequence
$\Delta\theta_{i}^{\mathrm{Upper}}$ is non-increasing and converges to $0$ if
the sequence is locally persistent with respect to any $N,M,\alpha$. For any
$\epsilon>0$, there exists an index $i_{1}\in\mathbb{Z}_{+}$, such that
$\Delta\theta_{i_{1}}^{\mathrm{Upper}}<\frac{\epsilon_{1}(1-c)}{2\sigma_{0}}$.
Consequently,
$\sup\\{\Delta\theta_{i}^{\mathrm{Upper}}\\}_{i=i_{1}}^{\infty}<\frac{\epsilon_{1}(1-c)}{2\sigma_{0}}$.
Now, consider $i_{2}\geq i_{1}$. For $k\geq i_{2}$, because $\hat{P}_{i}$ is
bounded, we have the following from (32):

$\begin{split}\lVert\hat{P}_{i}-P^{*}\rVert_{F}&\leq\beta(\lVert\hat{P}_{i_{2}}-P^{*}\rVert_{F},i-i_{2})+\frac{\epsilon_{1}}{2}\\\
&\leq\beta(\epsilon_{2},i-i_{2})+\frac{\epsilon_{1}}{2},\end{split}$ (87)

for some $\epsilon_{2}>0$. Since
$\lim\limits_{i\rightarrow\infty}\beta(\epsilon_{2},i-i_{2})=0$, there exists
an $i_{3}\geq i_{2}$ such that
$\beta(\epsilon_{2},i-i_{2})<\frac{\epsilon_{1}}{2}$ for all $i\geq i_{3}$.
This completes the proof $\lim\limits_{i\rightarrow\infty}\hat{P}_{i}=P^{*}$.
Together with Corollary 1,
$\lim\limits_{i\rightarrow\infty}\theta_{i}=\theta$, we can conclude
$\lim\limits_{i\rightarrow\infty}\hat{K}_{i}=K^{*}$.