Robust Reinforcement Learning for Stochastic Linear Quadratic Control with Multiplicative Noise

This chapter studies the robustness of reinforcement learning for discrete-time linear stochastic systems with multiplicative noise evolving in continuous state and action spaces. As one of the popular methods in reinforcement learning, the robustness of policy iteration is a longstanding open problem for the stochastic linear quadratic regulator (LQR) problem with multiplicative noise. A solution in the spirit of input-to-state stability is given, guaranteeing that the solutions of the policy iteration algorithm are bounded and enter a small neighborhood of the optimal solution, whenever the error in each iteration is bounded and small. In addition, a novel off-policy multiple-trajectory optimistic least-squares policy iteration algorithm is proposed, to learn a near-optimal solution of the stochastic LQR problem directly from online input/state data, without explicitly identifying the system matrices. The efficacy of the proposed algorithm is supported by rigorous convergence analysis and numerical results on a second-order example.

Confucius once said, Virtue is not left to stand alone. He who practices it will have neighbors. Laurent Praly, the former PhD advisor of the second-named author, is such a beautiful mind. His vision about and seminal contributions to control theory, especially nonlinear and adaptive control, have influenced generations of students including the authors of this chapter. ZPJ is privileged to have Laurent as the PhD advisor during 1989–1993 and is very grateful to Laurent for introducing him to the field of nonlinear control. It is under Laurent’s close guidance that ZPJ started, in 1991, working on the stability and control of interconnected nonlinear systems that has paved the foundation for nonlinear small-gain theory. The research findings presented here are just a reflection of Laurent’s vision about the relationships between control and learning. We also thank the U.S. National Science Foundation for its continuous financial support.

Authors and Affiliations

1. Control and Networks Lab, Department of Electrical and Computer Engineering, Tandon School of Engineering, New York University, 370 Jay Street, Brooklyn, NY, 11201, USA

   Bo Pang & Zhong-Ping Jiang

Corresponding author

Correspondence to Bo Pang .

Editors and Affiliations

1. Department of Electrical and Computer Engineering, New York University, Brooklyn, NY, USA

   Zhong-Ping Jiang

2. Automatic Control, CNRS, Saint Martin d’Heres, France

   Christophe Prieur

3. Department of Electrical and Computer Engineering, Imperial College London, London, UK

   Alessandro Astolfi

Appendix 1

The following lemma provides the relationship between operations \({{\,\mathrm{vec}\,}}(\cdot )\) and \({{\,\mathrm{svec}\,}}(\cdot )\).

Lemma 9.5

([40, Page 57]) For \(X\in \mathbb {S}^n\), there exists a unique matrix \(D_n\in \mathbb {R}^{n^2\times \frac{1}{2}n(n+1)}\) with full column rank, such that

\(D_n\) is called the duplication matrix.

Lemma 9.6

([44, Lemma A.3.]) Let \(\mathcal {O}\) be a compact set such that \(\rho (O)<1\) for any \(O\in \mathcal {O}\), then there exist an \(a_0>0\) and a \(0<b_0<1\), such that

for any \(O\in \mathcal {O}\).

For \(X\in \mathbb {R}^{n\times n}\), \(Y\in \mathbb {R}^{n\times m}\), \(X+\Delta X\in \mathbb {R}^{n\times n}\), \(Y + \Delta Y\in \mathbb {R}^{n\times m}\), supposing X and \(X + \Delta X\) are invertible, the following inequality is repeatedly used:

Appendix 2

The following property of \(\mathcal {L}_{K}(\cdot )\) is useful.

Lemma 9.7

If K is mean-square stabilizing, then \(\mathcal {L}_K(Y_1)\le \mathcal {L}_K(Y_2)\implies Y_1\ge Y_2\), where \(Y_1,Y_2\in \mathbb {S}^n\).

Proof

Let \(\{x_t\}_{t=0}^\infty \) be the solution of the closed-loop system (9.1) with controller \(u=-Kx\). Then for any \(t\ge 1\)

Since K is mean-square stabilizing,

The proof is complete because \(x_0\) is arbitrary. \(\square \)

Now we are ready to prove Theorem 9.1.

Proof

(Theorem 9.1) By (9.7) and (9.8), for any \(x\in \mathbb {R}^n\),

Thus \(\mathcal {H}(P_1,K_2)\le 0\). By definition, \(P_1>0\) and

Then Lemma 9.1 implies that \(K_2\) is mean-square stabilizing. Inserting (9.7) into the above inequality yields \(\mathcal {L}_{K_2}(P_1) \le \mathcal {L}_{K_2}(P_2)\). This implies \(P_1\ge P_2\) by Lemma 9.7. An application of mathematical induction proves the first two items. For the last item, by a theorem on the convergence of a monotone sequence of self-adjoint operators (see [32, Pages 189–190]), \(\lim _{i\rightarrow \infty } P_i\) and \(\lim _{i\rightarrow \infty } K_i\) exist. Letting \(i\rightarrow \infty \) in (9.7) and (9.8), and eliminating \(K_\infty \) in (9.7) using (9.8), we have

The proof is complete by the uniqueness of \(P^*\). \(\square \)

Appendix 3

Proof

(Lemma 9.2) Since \(\mathscr {K}(P^*)\) is mean-square stabilizing, by continuity there always exists a \(\bar{\delta }_0>0\), such that \(\mathscr {R}(P_i)\) is invertible, \(\mathscr {K}(P_i)\) is mean-square stabilizing for all \(P_i\in \mathcal {\bar{B}}_{\bar{\delta }_0}(P^*)\). Suppose \(P_i\in \mathcal {\bar{B}}_{\bar{\delta }_0}(P^*)\). Subtracting

from both sides of the GARE (9.4) yields

Subtracting (9.24) from (9.12), we have

Taking norm on both sides of above equation, (9.11) yields

Since \(\mathscr {K}(\cdot )\) is locally Lipschitz continuous at \(P^*\), by continuity of matrix norm and matrix inverse, there exists a \(c_1>0\), such that

So for any \(0<\sigma <1\), there exists a \(\bar{\delta }_0\ge \delta _0>0\) with \(c_1\delta _0\le \sigma \). This completes the proof. \(\square \)

Appendix 4

Before the proof of Lemma 9.3, some auxiliary lemmas are firstly proved. Procedure 9.2 will exhibit a singularity, if \([\hat{G}_{i}]_{uu}\) in (9.10) is singular, or the cost (9.2) of \(\hat{K}_{i+1}\) is infinity. The following lemma shows that if \(\Delta G_i\) is small, no singularity will occur. Let \(\bar{\delta }_0\) be the one defined in the proof of Lemma 9.2, then \(\delta _0\le \bar{\delta }_0\).

Lemma 9.8

For any \(\tilde{P}_i\in \mathcal {B}_{\delta _0}(P^*)\), there exists a \(d(\delta _0)>0\), independent of \(\tilde{P}_i\), such that \(\hat{K}_{i+1}\) is mean-square stabilizing and \([\hat{G}_{i}]_{uu}\) is invertible, if \(\Vert \Delta G_i\Vert _F\le d\).

Proof

Since \(\mathcal {\bar{B}}_{\bar{\delta }_0}(P^*)\) is compact and \(\mathscr {A}(\mathscr {K}(\cdot ))\) is a continuous function, set

is also compact. By continuity and Lemma 9.1, for each \(X\in \mathcal {S}\), there exists a \(r(X)>0\) such that \(\rho (Y+I_n\otimes I_n)<1\) for any \(Y\in \mathcal {B}_{r(X)}(X)\). The compactness of \(\mathcal {S}\) implies the existence of a \(\underline{r}>0\), such that \(\rho (Y+I_n\otimes I_n)<1\) for each \(Y\in \mathcal {B}_{\underline{r}}(X)\) and all \(X\in \mathcal {S}\). Similarly, there exists \(d_1>0\) such that \([\hat{G}_{i}]_{uu}\) is invertible for all \(\tilde{P}_i\in \mathcal {\bar{B}}_{\bar{\delta }_0}(P^*)\), if \(\Vert \Delta G_i\Vert _F\le d_1\). Note that in policy improvement step of Procedure 9.1 (the policy update step in Procedure 9.2), the improved policy\(\tilde{K}_{i+1}=[\tilde{G}_{i}]_{uu}^{-1}[\tilde{G}_{i}]_{ux}\) (the updated policy \(\hat{K}_{i+1}\)) is continuous function of \(\tilde{G}_i\) (\(\hat{G}_i\)), and there exists a \(0<d_2\le d_1\), such that \(\mathscr {A}(\hat{K}_{i+1})\in \mathcal {B}_{\underline{r}}(\mathscr {A}(\mathscr {K}(\tilde{P}_i)))\) for all \(\tilde{P}_i\in \mathcal {\bar{B}}_{\bar{\delta }_0}(P^*)\), if \(\Vert \Delta G_i\Vert _F\le d_2\). Thus, Lemma 9.1 implies that \(\hat{K}_{i+1}\) is mean-square stabilizing. Setting \(d=d_2\) completes the proof. \(\square \)

By Lemma 9.8, if \(\Vert \Delta G_i\Vert _F\le d\), the sequence \(\{\tilde{P}_i\}_{i=0}^{\infty }\) satisfies (9.13). For simplicity, we denote \(\mathcal {E}(\tilde{G}_i,\Delta G_i)\) in (9.13) by \(\mathcal {E}_i\). The following lemma gives an upper bound on \(\Vert \mathcal {E}_i\Vert _F\) in terms of \(\Vert \Delta G_i\Vert _F\).

Lemma 9.9

For any \(\tilde{P}_i\in \mathcal {B}_{\delta _0}(P^*)\) and any \(c_2>0\), there exists a \(0<\delta _1^1(\delta _0,c_2)\le d\), independent of \(\tilde{P}_i\), where d is defined in Lemma 9.8, such that

if \(\Vert \Delta G_i\Vert _F<\delta _1^1\), where \(c_3(\delta _0)>0\).

Proof

For any \(\tilde{P}_i\in \bar{\mathcal {B}}_{\delta _0}(P^*)\), \(\Vert \Delta G_i\Vert _F\le d\), we have from (9.23)

where the last inequality comes from the continuity of matrix inverse and the extremum value theorem. Define

Then by (9.11) and (9.13),

Define

Using (9.25), it is easy to check that \(\Vert \Delta \mathscr {A}_i\Vert _F\le c_5\Vert \Delta G_i\Vert _F\), \(\Vert \Delta b_i\Vert _2\le c_6\Vert \Delta G_i\Vert _F\), for some \(c_5(\delta _0,d)>0\), \(c_6(\delta _0,d)>0\). Then by (9.23)

where the last inequality comes from the continuity of matrix inverse and Lemma 9.8. Choosing \(0<\delta ^1_1\le d\) such that \(c_3\delta ^1_1<c_2\) completes the proof.

Now we are ready to prove Lemma 9.3.

Proof

(Lemma 9.3) Let \(c_2=(1-\sigma )\delta _0\) in Lemma 9.9, and \(\delta _1\) be equal to the \(\delta _1^1\) associated with \(c_2\). For any \(i\in \mathbb {Z}_+\), if \(\tilde{P}_i\in \mathcal {B}_{\delta _0}(P^*)\), then \([\hat{G}_i]_{uu}\) is invertible, \(\hat{K}_{i+1}\) is mean-square stabilizing and

where (9.26) and (9.28) are due to Lemmas 9.2 and 9.9. By induction, (9.26) to (9.28) hold for all \(i\in \mathbb {Z}_+\), thus by (9.27),

which proves (i) and (ii) in Lemma 9.3. Then (9.25) implies (iii) in Lemma 9.3.

In terms of (iv) in Lemma 9.3, for any \(\epsilon >0\), there exists a \(i_1\in \mathbb {Z}_+\), such that \(\sup \{\Vert \Delta G_i\Vert _F\}_{i=i_1}^\infty <\gamma ^{-1}(\epsilon /2)\). Take \(i_2\ge i_1\). For \(i\ge i_2\), we have by (ii) in Lemma 9.3,

where the second inequality is due to the boundedness of \(\tilde{P}_i\). Since \(\lim _{i\rightarrow \infty }\beta (c_7,i-i_2)=0\), there is a \(i_3\ge i_2\) such that \(\beta (c_7,i-i_2)<\epsilon /2\) for all \(i\ge i_3\), which completes the proof. \(\square \)

Appendix 5

Notice that all the conclusions of Theorem 9.2 can be implied by Lemma 9.3 if

for Procedure 9.2. Thus, the proof of Theorem 9.2 reduces to the proof of the following lemma.

Lemma 9.10

Given a mean-square stabilizing \(\hat{K}_1\), there exist \(0<\delta _2<\min (\gamma ^{-1}(\epsilon ),\delta _1)\), \(\bar{i}\in \mathbb {Z}_+\), \(\alpha _2>0\), and \(\kappa _2>0\), such that \([\hat{G}_i]_{uu}\) is invertible, \(\hat{K}_i\) is mean-square stabilizing, \(\Vert \tilde{P}_i\Vert _F<\alpha _2\), \(\Vert \hat{K}_i\Vert _F<\kappa _2\), \(i=1,\cdots ,\bar{i}\), \(\tilde{P}_{\bar{i}}\in \mathcal {B}_{\delta _0}(P^*)\), as long as \(\Vert \Delta G\Vert _\infty <\delta _2\).

The next two lemmas state that under certain conditions on \(\Vert \Delta G_i\Vert _F\), each element in \(\{\hat{K}_i\}_{i=1}^{\bar{i}}\) is mean-square stabilizing, each element in \(\{[\hat{G}_i]_{uu}\}_{i=1}^{\bar{i}}\) is invertible, and \(\{\tilde{P}_i\}_{i=1}^{\bar{i}}\) is bounded. For simplicity, in the following we assume \(S>I_n\) and \(R>I_m\). All the proofs still work for any \(S>0\) and \(R>0\), by suitable rescaling.

Lemma 9.11

If \(\hat{K}_i\) is mean-square stabilizing, then \([\hat{G}_i]_{uu}\) is nonsingular and \(\hat{K}_{i+1}\) is mean-square stabilizing, as long as \(\Vert \Delta G_i\Vert _F < a_i\), where

Furthermore,

Proof

By definition,

Since \(R>I_m\), the eigenvalues \(\lambda _j([\tilde{G}_i]_{uu}^{-1})\in (0,1]\) for all \(1\le j\le m\). Then by the fact that for any \(X\in \mathbb {S}^m\)

we have

Thus by [26, Section 5.8], \([\hat{G}_i]_{uu}\) is invertible.

For any \(x\in \mathbb {R}^{n}\) on the unit ball, define

From (9.9) and (9.10) we have

and

Then

where \(\vert \mathcal {X}_{\hat{K}_{i}}\vert _{abs}\) denotes the matrix obtained from \(\mathcal {X}_{\hat{K}_{i}}\) by taking the absolute value of each entry. Thus by (9.31) and the definition of \(\tilde{G}_i\), we have

where

For any x on the unit ball, \(\vert \mathbf {1}^Tx\vert _{abs}\le \sqrt{n}\). Similarly, for any \(K\in \mathbb {R}^{m\times n}\), by the definition of induced matrix norm, \(\vert \mathbf {1}^TKx\vert _{abs}\le \Vert K\Vert _2 \sqrt{m}\). This implies

which means \(\mathbf {1}^T\vert \mathcal {X}_K\vert _{abs}\mathbf {1}\le m(\sqrt{n} + \Vert K\Vert _2)^2\). Thus

Then \(S>I_n\) leads to

for all x on the unit ball. So \(\hat{K}_{i+1}\) is mean-square stabilizing by Lemma 9.1.

By definition,

where the second inequality comes from [26, Inequality (5.8.2)], and the last inequality is due to (9.30). This completes the proof. \(\square \)

Lemma 9.12

For any \(\bar{i}\in \mathbb {Z}_+\), \(\bar{i}>0\), if

where \(a_i\) is defined in Lemma 9.11, then

for \(i=1,\cdots ,\bar{i}\), where

Proof

Inequality (9.32) yields

where

Inserting (9.9) into above inequality, and using Lemma 9.7, we have

With \(S>I_n\), (9.35) yields

Similar to (9.36), we have

From (9.36) to (9.37), we obtain

By definition of \(\epsilon _{2,i}\) and condition (9.34),

Then [34, §28. Theorem 3] yields

An application of (9.29) completes the proof. \(\square \)

Now we are ready to prove Lemma 9.10.

Proof

(Lemma 9.10) Consider Procedure 9.2 confined to the first \(\bar{i}\) iterations, where \(\bar{i}\) is a sufficiently large integer to be determined later in this proof. Suppose

Condition (9.38) implies condition (9.34). Thus \(\hat{K}_i\) is mean-square stabilizing, \([\hat{G}_i]_{uu}^{-1}\) is invertible, \(\Vert \tilde{P}_i\Vert _F\) and \(\Vert \hat{K}_i\Vert _F\) are bounded. By (9.9) we have

Letting \(E_i = \hat{K}_{i+1} - \mathscr {K}(\tilde{P}_i)\), the above equation can be rewritten as

where \(\mathcal {N}(\tilde{P_i}) = \mathcal {L}_{\mathscr {K}(\tilde{P_i})}^{-1}\circ \mathcal {R}(\tilde{P}_i),\) and

Given \(\hat{K}_1\), let \(\mathcal {M}_{\bar{i}}\) denote the set of all possible \(\tilde{P}_i\), generated by (9.39) under condition (9.38). By definition, \(\{\mathcal {M}_j\}_{j=1}^\infty \) is a nondecreasing sequence of sets, i.e., \(\mathcal {M}_1\subset \mathcal {M}_2 \subset \cdots \). Define \(\mathcal {M} = \cup _{j=1}^\infty \mathcal {M}_j\), \(\mathcal {D} = \{P\in \mathbb {S}^n\ \vert \ \Vert P\Vert _F\le 6\Vert \tilde{P}_1\Vert _F\}\). Then by Lemma 9.12 and Theorem 9.1, \(\mathcal {M}\subset \mathcal {D}\); \(\mathcal {M}\) is compact; \(\mathscr {K}(P)\) is stable for any \(P\in \mathcal {M}\).

Now we prove that \(\mathcal {N}(P^1)\) is Lipschitz continuous on \(\mathcal {M}\). Using (9.11), we have

where the last inequality is due to the fact that matrix inversion \(\mathscr {A}(\cdot )\), \(\mathscr {K}(\cdot )\), and \(\mathcal {R}(\cdot )\) are locally Lipschitz, thus Lipschitz on compact set \(\mathcal {M}\) with some Lipschitz constant \(L>0\).

Define \(\{P_{k\vert i}\}_{k=0}^{\infty }\) as the sequence generated by (9.12) with \(P_{0\vert i}=\tilde{P}_i\). Similar to (9.39), we have

By Theorem 9.1 and the fact that \(\mathcal {M}\) is compact, there exists \(k_0\in \mathbb {Z}_+\), such that

Suppose

We find an upper bound on \(\Vert P_{k\vert i}-\tilde{P}_{i+k}\Vert _F\). Notice that from (9.39) to (9.41),

Then (9.40) and (9.43) yield

An application of the Gronwall inequality [2, Theorem 4.1.1.] to the above inequality implies

By (9.11), the error term in (9.39) satisfies

where \(C_1\) is a constant and the inequality is due to the continuity of matrix inverse.

Let \(\bar{i}>k_0\), and \(k=k_0\), \(i = \bar{i}-k_0\) in (9.44). Then by condition (9.38), Lemma 9.12, (9.43), (9.44), and (9.45), there exist \(i_0\in \mathbb {Z}_+\), \(i_0>k_0\), such that \(\Vert P_{k_0\vert \bar{i}-k_0} -\tilde{P}_{\bar{i}}\Vert _F<\delta _0/2\), for all \(\bar{i}\ge i_0\). Setting \(i = \bar{i}-k_0\) in (9.42), the triangle inequality yields \(\tilde{P}_{\bar{i}}\in \mathcal {B}_{\delta _0}(P^*)\), for \(\bar{i}\ge i_0\). Then in (9.38), choosing \(\bar{i}\ge i_0\) such that \(\delta _2 = b_{\bar{i}}<\min (\gamma ^{-1}(\epsilon ),\delta _1)\) completes the proof. \(\square \)

Appendix 6

For given \(\hat{K}_1\), let \(\mathcal {K}\) denote the set of control gains (including \(\hat{K}_1\)) generated by Procedure 9.2 with all possible \(\{\Delta G_i\}_{i=1}^\infty \) satisfying \(\Vert \Delta G\Vert _\infty <\delta _2\), where \(\delta _2\) is the one in Theorem 9.2. The following result is firstly derived.

Lemma 9.13

Under the conditions in Theorem 9.3, there exist \(\bar{L}_0>0\) and \(N_0>0\) such that for any \(\bar{L}\ge \bar{L}_0\) and \(N\ge N_0\), \(\hat{K}_i\in \mathcal {K}\) implies \(\Vert \Delta G_i\Vert _F< \delta _2\), almost surely.

Proof

By definition, in the context of Algorithm 9.1,

where \(\tilde{P}_i\) is the unique solution of (9.9) with \(K=\hat{K}_i\). Thus, the task is to prove that each term in the right-hand side of the above inequality is less than \(\delta _2/3\). To this end, we firstly study \(\Vert \tilde{P}_i - \hat{P}_{i,\bar{L}} \Vert _F\). Define \(\hat{p}_{i,j}={{\,\mathrm{vec}\,}}(\hat{P}_{i,j})\), by Lemma 9.5, Line 11 and Line 12 in Algorithm 9.1 can be rewritten as

where \(\hat{p}_{i,0}\in \mathbb {R}^{n^2}\) and

Similar derivations applied to (9.20) with \(K=\hat{K}_i\) yield

Since (9.20) is identical to (9.14), (9.47) is identical to (9.15) with K and \({{\,\mathrm{vec}\,}}(P_{K,j})\) replaced by \(\hat{K}_i\) and \(\bar{p}_{i,j}\) respectively, and

Since \(\mathscr {A}(\hat{K}_i)\), \(\hat{K}_i\in \mathcal {K}\) is mean-square stabilizing, by Lemma 9.4

where \(\bar{P}_{i,j} = {{\,\mathrm{vec}\,}}^{-1}(\bar{p}_{i,j})\). By definition and Theorem 9.2, \(\bar{\mathcal {K}}\) is bounded, thus compact. Let \(\mathcal {V}\) be the set of the unique solutions of (9.5) with \(K\in \mathcal {K}\). Then by Theorem 9.2 \(\mathcal {V}\) is bounded. So \(\mathscr {A}(K)\) is mean-square stable for \(\forall K\in \bar{\mathcal {K}}\), otherwise by (9.11) and Lemma 9.1 it contradicts the boundedness of \(\mathcal {V}\). Define \(\mathcal {K}_1 = \{\mathscr {A}(K)+I_n\otimes I_n\vert K\in \bar{\mathcal {K}}\}\). Then \(\rho (X)<1\) for any \(X\in \mathcal {K}_1\), and by continuity \(\mathcal {K}_1\) is a compact set. This implies the existence of a \(\delta _3>0\), such that \(\rho (X)<1\) for any \(X\in \bar{\mathcal {K}}_2\), where

Define

The boundedness of \(\mathcal {K}\), (9.22), and (9.48) imply the existence of \(N_1>0\), such that for any \(N\ge N_1\), any \(\hat{K}_i\in \mathcal {K}\), almost surely

where \(C_9>0\) is a constant. Then

and (9.46) admits a unique stable equilibrium, that is,

for some \(\mathring{P}_i\in \mathbb {S}^n\). From (9.46), (9.47), (9.49), and (9.51), we have

Thus by (9.23), for any \(N\ge N_1\), any \(\hat{K}_i\in \mathcal {K}\), almost surely

where \(C_{10}\) and \(C_{11}\) are some positive constants, and the last inequality is due to (9.48), (9.50) and the fact that \(\mathcal {K}_1\) and \(\bar{\mathcal {K}}_2\) are compact sets. Then for any \(\epsilon _1>0\), the boundedness of \(\mathcal {K}\) and (9.22) implies the existence of \(N_2\ge N_1\), such that for any \(N\ge N_2\), almost surely

as long as \(\hat{K}_i\in \mathcal {K}\). By Lemma 9.6 and (9.52), for any \(N\ge N_2\) and any \(\hat{K}_i\in \mathcal {K}\),

for some \(a_0>0\), \(1>b_0>0\) and \(a_1>0\). Therefore there exists a \(\bar{L}_1>0\), such that for any \(\bar{L}\ge \bar{L}_1\), and any \(N\ge N_2\), almost surely

as long as \(\hat{K}_i\in \mathcal {K}\). With (9.52) and (9.53), we obtain

almost surely for any \(\bar{L}\ge \bar{L}_1\), any \(N\ge N_2\), as long as \(\hat{K}_i\in \mathcal {K}\). Since \(\epsilon _1\) is arbitrary, we can choose \(\epsilon _1\) such that almost surely

for any \(\bar{L}\ge \bar{L}_1\), any \(N\ge N_2\), as long as \(\hat{K}_i\in \mathcal {K}\).

Secondly, by definition and (9.54), there exist \(\bar{L}_2\ge \bar{L}_1\) and \(N_3\ge N_2\), such that

for any \(\bar{L}\ge \bar{L}_2\), any \(N\ge N_3\), as long as \(\hat{K}_i\in \mathcal {K}\).

Thirdly, since \(\mathcal {V}\) is bounded, \(\hat{P}_{i,\bar{L}}\) is also almost surely bounded by (9.54). Thus, from Line 14 in Algorithm 9.1 and (9.22), there exists \(N_4\ge N_3\), such that

for any \(N\ge N_4\) and any \(\bar{L}\ge \bar{L}_2\), as long as \(\hat{K}_i\in \mathcal {K}\).

Setting \(N_0 = N_4\) and \(\bar{L}_0 = \bar{L}_2\) yields \(\Vert \Delta G_i\Vert <\delta _2\). \(\square \)

Now we are ready to prove the convergence of Algorithm 9.1.

Proof

(Theorem 9.3) Since \(\hat{K}_1\in \mathcal {K}\), Lemma 9.13 implies \(\Vert \Delta G_1\Vert _F<\delta _2\) almost surely. By definition, \(\hat{K}_2\in \mathcal {K}\). Thus \(\Vert \Delta G_i\Vert _F<\delta _2, i=1,2,\cdots \) almost surely by mathematical induction. Then Theorem 9.2 completes the proof. \(\square \)

Reprints and permissions

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics