Rate of Convergence and Error Bounds for LSTD($λ$)

Introduction

In a large Markov Decision Process context, we consider LSTD($\lambda$), the least-squares temporal-difference algorithm with eligibility traces proposed by Boyan (2002). It is a popular algorithm for estimating a projection onto a linear space of the value function of a fixed policy. Such a value estimation procedure can for instance be useful in a policy iteration context to eventually estimate an approximately optimal controller (Bertsekas and Tsitsiklis, 1996; Szepesvári, 2010).

LSTD(λ𝜆\lambda) and Related background

where $\gamma\in(0,1)$ is a discount factor. It is well-known that the value function $v$ is the unique fixed point of the linear Bellman operator $T$:

It can easily be seen that $v\in{\cal B}({\cal X},V_{\text{max}})$ with $V_{\text{max}}=\frac{R_{\text{max}}}{1-\gamma}$.

The feature functions $(\phi_{j})_{j\in\{1,...,d\}}$ are linearly independent.

Let ${\cal S}$ be the subspace generated by the vectors $(\phi_{j})_{1\leq j\leq d}$. We consider the orthogonal projection $\Pi$ onto ${\cal S}$ with respect to the $\mu$-weighed quadratic norm

It is well known that this projection has the following closed form

where $D_{\mu}$ is the diagonal matrix with elements of $\mu$ on the diagonal.

The goal of LSTD($\lambda$) is to estimate a solution of the equation $v=\Pi T^{\lambda}v$, where the operator $T^{\lambda}$ is defined as a weighted arithmetic mean of the applications of the powers $T^{i}$ of the Bellman operator $T$ for all $i>1$:

Note in particular that when $\lambda=0$, one has $T^{\lambda}=T$. By using the facts that $T^{i}$ is affine and $\|P\|_{\mu}=1$ (Tsitsiklis and Roy, 1997; Nedic and Bertsekas, 2002), it can be seen that the operator $T^{\lambda}$ is a contraction mapping of modulus $\frac{(1-\lambda)\gamma}{1-\lambda\gamma}\leq\gamma$; indeed, for any vectors $u,v$:

If we replace $\Pi$ and $T^{\lambda}$ with their expressions (Equations 1 and 2), it can be seen that $\theta$ is a solution of the equation $A\theta=b$ (Nedic and Bertsekas, 2002), such that for any $i$,

where $u^{T}$ is the transpose of $u$. Since for all $x$, $\phi(x)$ is of dimension $d$, we see that $A$ is a $d\times d$ matrix and $b$ is a vector of size $d$. Under Assumption 1, it can be shown (Nedic and Bertsekas, 2002) that the matrix $A$ is invertible, and thus $v_{LSTD(\lambda)}=\Phi A^{-1}b$ is well defined.

The LSTD($\lambda$) algorithm that is the focus of this article is now precisely described. Given one trajectory $X_{1},....,X_{n}$ generated by the Markov chain, the expectation-based expressions of $A$ and $b$ in Equations (3)-(4) suggest to compute the following estimates:

is the so-called eligibility trace. The algorithm then returns $\hat{v}_{LSTD(\lambda)}=\Phi\hat{\theta}$ withWe will see in Theorem 1 that $\hat{A}$ is invertible with high probability for a sufficiently big $n$. $\hat{\theta}=\hat{A}^{-1}\hat{b}$, which is a (finite sample) approximation of $v_{LSTD(\lambda)}$. Using a variation of the law of large numbers, Nedic and Bertsekas (2002) showed that both $\hat{A}$ and $\hat{b}$ converge almost surely respectively to $A$ and $b$, which implies that $\hat{v}_{LSTD(\lambda)}$ tends to $v_{LSTD(\lambda)}$. The main goal of the remaining of the paper is to deepen this analysis: we shall estimate the rate of convergence of $\hat{v}_{LSTD(\lambda)}$ to $v_{LSTD(\lambda)}$, and bound the approximation error $\|\hat{v}_{LSTD(\lambda)}-v\|_{\mu}$ of the overall algorithm.

Main results

This section contains our main results. Our key assumption for the analysis is that the Markov chain process that generates the states has some mixing propertyA stationary ergodic Markov chain is always $\beta$-mixing..

The process ${(X_{n})}_{n\geq 1}$ is $\beta$-mixing, in the sense that its $i^{\text{th}}$ coefficient

tends to when $i$ tends to infinity, where $X^{j}_{l}=\{X_{l},...,X_{j}\}$ for $j\geq l$ and $\sigma(X^{j}_{l})$ is the sigma algebra generated by $X^{j}_{l}$ . Furthermore, ${(X_{n})}_{n\geq 1}$ mixes at an exponential decay rate with parameters $\overline{\beta}>0$, $b>0$, and $\kappa>0$ in the sense that $\beta_{i}\leq\overline{\beta}e^{-bi^{\kappa}}$.

Intuitively the $\beta_{i}$ coefficients measure the degree of dependence of samples separated by $i$ times step (the smaller the coefficient the more independence). We are now ready to state the main result of the paper, that provides a rate of convergence of LSTD($\lambda$).

Let Assumptions 1 and 2 hold and let $X_{1}\sim\mu$. For any $n\geq 1$ and $\delta\in(0,1)$, define:

Let $n_{0}(\delta)$ be the smallest integer such that

where $\nu$ is the smallest eigenvalue of the Gram matrix $\Phi^{T}D_{\mu}\Phi$. Then, for all $\delta$, with probability at least $1-\delta$, for all $n\geq n_{0}(\delta)$, $\hat{A}$ is invertible and we have:

The approximation error satisfiesAs suggested by V. Papavassilou (Tsitsiklis and Roy, 1997), this bound can in fact be improved by using the Pythagorean theorem to $\|v-v_{LSTD(\lambda)}\|_{\mu}\leq\frac{1-\lambda\gamma}{\sqrt{(1-\gamma)(1+\gamma-2\lambda\gamma)}}\|v-\Pi v\|_{\mu}.$ We keep the simple form of Theorem 2 for simplicity.:

Since the constant equals $1$ when $\lambda=1$, one recovers the well-known fact that LSTD(1) computes the orthogonal projection $\Pi v$ of $v$. By using the triangle inequality, one deduces from Theorems 1 and 2 the following global error bound.

Let the assumptions and notations of Theorem 1 hold. For all $\delta$, with probability $1-\delta$, for all $n\geq n_{0}(\delta)$, the global error of LSTD($\lambda$) satisfies:

The form of the result stated in Corollary 1 is slightly stronger than the one of Lazaric et al. (2012): for some property $P(n)$, our result if of the form “$\forall\delta,~{}\exists n_{0}(\delta),\text{such that}~{}\forall n>n_{0}(\delta),~{}P(n)$ holds with probability $1-\delta$” while theirs is of the form “$\forall n,~{}\forall\delta,~{}P(n)$ holds with probability $1-\delta$”. Furthermore, under the same assumptions, the global error bound obtained by Lazaric et al. (2012), in the restricted case where $\lambda=0$, has the following form:

The term corresponding to the approximation error is a factor $4\sqrt{2}$ better with our analysis. Moreover, contrary to what we do here, the analysis of Lazaric et al. (2012) does not imply a rate of convergence for LSTD($\lambda$) (a bound on $\|v_{LSTD(0)}-\hat{v}_{LSTD(0)}\|_{\mu}$). Their arguments, based on a model of regression with Markov design, consists in directly bounding the global error. Our two-step argument (bounding the estimation error with respect to $\|\cdot\|_{\mu}$, and then the approximation error with respect to $\|\cdot\|_{\mu}$) allows us to get a tighter result.

As we have already mentioned, $\lambda=1$ minimizes the bound on the approximation error $\|v-v_{LSTD(\lambda)}\|$ (the first term in the r.h.s. in Corollary 1) while $\lambda=0$ minimizes the bound on the estimation error $\|v_{LSTD(\lambda)}-\hat{v}_{LSTD(\lambda)}\|$ (the second term). For any $n$, and for any $\delta$, there exists hence a value $\lambda^{*}$ that minimizes the global error bound by making an optimal compromise between the approximation and estimation errors. Figure 1 illustrates through simulations the interplay between $\lambda$ and $n$.

The optimal value $\lambda^{*}$ depends on the process mixing parameters ($b$, $\kappa$ and $\overline{\beta}$) as well as on the quality of the policy space $\|v-\Pi v\|_{\mu}$, which are quantities that are usually unknown in practice. However, when the number of samples $n$ tends to infinity, it is clear that this optimal value $\lambda^{*}$ tends to $1$.

The next section contains a detailed proof of Theorem 1.

Proof of Theorem 1

In this section, we develop the arguments underlying the results of the previous section. The proof is organized in two parts. In a first preliminary part, we prove a concentration inequality for vector processes: a general result that is based on infinitely-long eligibility traces. Then, in a second part, we actually prove Theorem 1: we apply this result to the error on estimating $A$ and $b$, and relate these errors with that on $v_{LSTD(\lambda)}$.

One of the first difficulties for the analysis of LSTD($\lambda$) is that the variables $A_{i}=z_{i}(\phi(X_{i})-\gamma\phi(X_{i+1}))^{T}$ (respectively $b_{i}=z_{i}r(X_{i})$) are not independent. Thus standard concentration results (like Lemma 6 we will describe in the Appendix A) for quantifying the speed at which the estimates converge to their limit cannot be used. As both terms $\hat{A}$ and $\hat{b}$ have the same structure, we will consider here a matrix that has the following general form:

Since the function $\phi$ is bounded by some constant $L$ and the influence of the old events are controlled by some power of $\lambda\gamma<1$, it is easy to check that $\|z_{i}-z^{m}_{i}\|_{\infty}\leq\frac{L}{1-\lambda\gamma}(\lambda\gamma)^{m}$. If we choose $m$ such that $m>\frac{\log(n-1)}{\log\frac{1}{\lambda\gamma}}$, we obtain $\|z_{i}-z^{m}_{i}\|_{2}=O\left(\frac{1}{n}\right)$. Therefore it seems reasonable to approximate $\hat{G}$ with the process $\hat{G}^{m}$ satisfying

For all $i\geq m$, $G_{i}^{m}$ is a $\sigma({\cal X}^{m+1})$ measurable function of the stationary vector $Z_{i}=(X_{i-m+1},X_{i-m+2}$ $,\dots,X_{i+1})$. So we can apply the blocking technique of Yu (1994) to $G^{m}_{i}$, but before to do so we have to check out whether $G^{m}_{i}$ well defines a $\beta$-mixing process. It can be shown (Yu, 1994) that any mesurable function $f$ of a $\beta$-mixing process is a $\beta^{f}$-mixing process with $\beta^{f}\leq\beta$, so we only have to prove that the process $Z_{i}$ is a $\beta$-mixing process. For that we need to relate its $\beta$ coefficients to those of $(X_{i})_{i\geq 1}$ on which Assumption 2 is made. This is the purpose of the following Lemma.

Let $(X_{n})_{n\geq 1}$ be a $\beta$-mixing process, then $(Z_{n})_{n\geq 1}=(X_{n-m+1},X_{n-m+2}$ $,\dots,X_{n+1})_{n\geq 1}$ is a $\beta$-mixing process such that its $i^{th}$ $\beta$ mixing coefficient $\beta^{Z}_{i}$ satisfies $\beta^{Z}_{i}\leq\beta^{X}_{i-m}$.

Let $\Gamma=\sigma(Z_{1},...,Z_{t})$, by definition we have

For $B=B_{0}\times...\times B_{m}$, we observe that

Similarly we can prove that $\sigma(Z^{\infty}_{t+i})=\sigma(X^{\infty}_{t+i})$. Then let $\beta^{X}_{i}$ be the $i^{th}$ $\beta$-mixing coefficient of the process $(X_{n})_{n\geq 1}$, we have

Similarly for the process $(Z_{n})_{n\geq 1}$ we can see that

By applying what we developped above we obtain

Denote $t^{\prime}=t+m$ then for $i>m$ we have

Let Assumptions 1 and 2 hold and let $X_{1}\sim\mu$. Define the $d\times k$ matrix $G_{i}$ such that

Recall that $\phi=(\phi_{1},\dots,\phi_{d})$ is such that for all $j$, $\phi_{j}\in{\cal B}({\cal X},L)$, and that $\tau\in{\cal B}({\cal X}^{2},L^{\prime})$. Then for all $\delta$ in $(0,1)$, with probability $1-\delta$,

Note that with respect to the quantities $I$ and $\Lambda$ introduced in Theorem 1, the quantities we introduce here are such that $J(n,\delta)=I(n,4n^{2}\delta)$ and $\Gamma(n,\delta)=\Lambda(n,4n^{2}\delta)$.

The proof amounts to show that i) the approximation due to considering the estimate $\hat{G}^{m}$ with truncated traces instead of $\hat{G}$ is bounded by $\epsilon(n)$, and then ii) to apply the block technique of Yu (1994) in a way somewhat similar to—but technically slightly more involved than—what Lazaric et al. (2012) did for LSTD(0). We defer the technical arguments to Appendix A for readability. ∎

Using a very similar proof, we can derive a (simpler) general concentration inequality for $\beta$-mixing processes:

where $J(n,\delta)$ is defined as in Lemma 2.

2 Proof of Theorem 1

After having introduced the corresponding concentration inequality for infinitely-long trace-based estimates we are ready to prove Theorem 1. The first important step to Theorem 1 proof consists in deriving the following lemma.

Write $\epsilon_{A}=\hat{A}-A$, $\epsilon_{b}=\hat{b}-b$ and $\nu$ the smallest eigenvalue of the matrix $\Phi^{T}D_{\mu}\Phi$. For all $\lambda\in(0,1)$, the estimate $\hat{v}_{LSTD(\lambda)}$ satisfiesWhen $\hat{A}$ is not invertible, we take $\hat{v}_{LSTD(\lambda)}=\infty$ and the inequality is always satisfied since, as we will see shortly, the invertiblity of $\hat{A}$ is equivalent to that of $(I+\epsilon_{A}A^{-1}).$:

Furthermore, if for some $\epsilon$ and $C$, $\|\epsilon_{A}\|_{2}\leq\epsilon<C\leq\frac{1}{\|A^{-1}\|_{2}}$, then $\hat{A}$ is invertible and

Starting from the definitions of $v_{LSTD(\lambda)}$ and $\hat{v}_{LSTD(\lambda)}$, we have

On the one hand, with the expression of $A$ in Equation (3), writing $M=(1-\lambda)\gamma P(I-\lambda\gamma P)^{-1}$ and $M_{\mu}=\Phi^{T}D_{\mu}\Phi$, and using some linear algebra arguments, we can observe that

Since the matrices $A$ and $M_{\mu}$ are invertible, the matrix $(I-M^{-1}_{\mu}\Phi^{T}D_{\mu}M\Phi)$ is also invertible, then

We know from Tsitsiklis and Roy (1997) that $\|\Pi\|_{\mu}=1$—the projection matrix $\Pi$ is defined in Equation (1)—and $\|P\|_{\mu}=1$. Hence, we have $\|\Pi M\|_{\mu}=\frac{(1-\lambda)\gamma}{1-\lambda\gamma}<1$ and the matrix $(I-\Pi M)$ is invertible. We can use the identity $X(I-YX)^{-1}=(I-XY)^{-1}X$ with $X=\Phi$ and $Y=M_{\mu}^{-1}\Phi^{T}D_{\mu}M$, and obtain

On the other hand, using the facts that $A\theta=b$ and $\hat{A}\hat{\theta}=\hat{b}$, we can see that:

where the last equality follows from the identity $A\theta=b$. Using Equations (13) and (14), Equation (12) can be rewritten as follows:

Now we will try to bound $\|\Phi M^{-1}_{\mu}(I+\epsilon_{A}A^{-1})^{-1}(\epsilon_{b}-\epsilon_{A}\theta)\|_{\mu}$. Notice that for all $x$,

where $\nu$ is the smallest (real) eigenvalue of the Gram matrix $M_{\mu}$. By taking the norm in Equation (15) and using the above relation, we get

The first part of the lemma is obtained by using the fact that $\|\Pi M\|_{\mu}=\frac{(1-\lambda)\gamma}{1-\lambda\gamma}<1$, which imply that

We are going now to prove the second part of the Lemma. Since $A$ is invertible, the matrix $\hat{A}$ is invertible if and only if the matrix $\hat{A}A^{-1}=(A+\epsilon_{A})A^{-1}=I+\epsilon_{A}A^{-1}$ is invertible. Let us denote $\rho(\epsilon_{A}A^{-1})$ the spectral radius of the matrix $\epsilon_{A}A^{-1}$. A sufficient condition for $\hat{A}A^{-1}$ to be invertible is that $\rho(\epsilon_{A}A^{-1})<1$. From the inequality $\rho(M)\leq\|M\|_{2}$ for any square matrix $M$, we can see that for any $C$ and $\epsilon$ that satisfy $\|\epsilon_{A}\|_{2}\leq\epsilon<C<\frac{1}{\|A^{-1}\|_{2}}$, we have

It follows that the matrix $\hat{A}$ is invertible and

To finish the proof of Theorem 1, Lemma 4 suggests that we should control both terms $\|\epsilon_{A}\|_{2}$ and $\|\epsilon_{A}\theta-\epsilon_{b}\|_{2}$ with high probability. This is what we do now.

By the triangle inequality, we can see that

Write $\hat{A}_{n,k}=\phi(X_{k})(\phi(X_{n})-\gamma\phi(X_{n+1}))^{T}$. For all $n$ and $k$, we have $\|\hat{A}_{n,k}\|_{2}\leq 2dL^{2}$. We can bound the first term of the r.h.s. of Equation (18) as follows, by replacing $A$ with its expression in (3):

Let $(\delta_{n})$ a parameter in $(0,1)$ depending on $n$, that we will fix later, a consequence of Equation (18) and the just derived bound is that:

if we choose $\epsilon_{1}(n,\delta_{n})$ such that (cf. Lemma 2)

where $\epsilon(n)=\frac{4mdL^{2}}{(n-1)(1-\lambda\gamma)}$, that is if

By using the fact that $A\theta=b$, the definitions of $\hat{A}$ and $\hat{b}$, and the fact that $\phi(x)^{T}\theta=[\phi\theta](x)$, we have

where, since $v_{LSTD(\lambda)}=\Phi\theta$, $\Delta_{i}$ is the following number:

We can control $\|\epsilon_{A}\theta-\epsilon_{b}\|_{2}$ by following the same proof steps as above. In fact we have

As a consequence of Equation (20) and the just derived bound we have

if we choose $\epsilon_{2}(\delta_{n})$ such that (cf Lemma 2)

It remains to compute a bound on $\|\Delta_{i}\|_{\infty}$. To do so, it suffices to bound $v_{LSTD(\lambda)}$. For all $x\in{\cal X}$, we have

where the first inequality is obtained from the Cauchy-Schwarz inequality. We thus need to bound $\|\theta\|_{2}$. On the one hand, we have

Since $\Phi^{T}D_{\mu}\Phi$ is a symmetric matrix, we have $\nu\leq\|\Phi^{T}D_{\mu}\Phi\|_{2}$. We can see that

so that $\nu\leq dL^{2}$. It follows that, for all $i$

Conclusion of the proof.

We are ready to conclude the proof. Now that we know how to control both terms $\|\epsilon_{A}\|_{2}$ and $\|\epsilon_{A}\theta-\epsilon_{b}\|_{2}$, we can see that

if we choose $\delta_{n}=\frac{1}{4n^{2}}\delta$. By the second part of Lemma 4, for all $\delta$, with probability at least $1-\delta$, for all $n$ such that $\epsilon_{1}(n,\delta_{n})<C$, $\hat{A}$ is invertible and

We get the bound of the Theorem by replacing $\epsilon_{1}(n,\delta_{n})$ and $\epsilon_{2}(n,\delta_{n})$ with their definitions in Equations (19) and (21).

To complete the proof of Theorem 1, we now need to show how to pick $C$, which will allow to show that the condition $\epsilon_{1}(n,\delta_{n})<C\leq\frac{1}{\|A^{-1}\|_{2}}$ is equivalent to the one that characterizes the index $n_{0}(\delta)$ in the Theorem. Indeed we have

where the last inequality is obtained from Equation (16). Then

and consequently we can take $C=\frac{(1-\gamma)\nu}{1-\lambda\gamma}$. This concludes the proof of Theorem 1.

Conclusion and Future Work

The performance bound that we deduced is more accurate than the one from Lazaric et al. (2012), restricted to the case $\lambda=0$. The analysis that they proposed was based on a Markov design regression model. By using the trace truncation technique we have employed, we believe it is possible to extend the proof of Lazaric et al. (2012) to the general case $\lambda$ in $(0,1)$. However we would still pay a $4\sqrt{2}$ extra factor in the final bound.

In the future, we plan to instantiate our new bound in a Policy Iteration context like Lazaric et al. (2012) did for LSTD(0). An interesting follow-up work would also be to extend our analysis of LSTD($\lambda$) to the situation where one considers non-stationary policies, as Scherrer and Lesner (2012) showed that it allows to improve the overall performance of the Policy Iteration Scheme. Finally, a challenging question would be to consider LSTD($\lambda$) in the off-policy case, for which the convergence has recently been proved by Yu (2010).

Appendix A Proof of Lemma 2

By concatenating all its columns, the $d\times k$ matrix $G^{m}_{i}$ may be seen a single vector $U^{m}_{i}$ of size $dk$. Then, for all $\epsilon>0$,

The variables $U^{m}_{i}$ define a stationary $\beta$-mixing process (Lemma 1). To deal with the $\beta$-mixing assumption, we use the decomposition technique proposed by Yu (1994) that consists in dividing the stationary sequence $U^{m}_{m},\dots,U^{m}_{n-1}$ into $2\mu_{n-m}$ blocks of length $a_{n-m}$ (we assume here that $n-m=2a_{n-m}\mu_{n-m}$). The blocks are of two kinds: those which contains the even indexes $E=\cup^{\mu_{n-m}}_{l=1}E_{l}$ and those with odd indexes $H=\cup^{\mu_{n-m}}_{l=1}H_{l}$. Thus, by grouping the variables into blocks we get

where Equation (25) follows from the triangle inequality, Equation (26) from the fact that the event $\{X+Y\geq a\}$ implies $\{X\geq\frac{a}{2}\}$ or $\{Y\geq\frac{a}{2}\}$, and Equation (27) from the assumption that the process is stationary. Since $H=\cup^{\mu_{n-m}}_{l=1}H_{l}$ we have

where we defined $U(H_{l})=\sum_{i\in H_{l}}U^{m}_{i}$. Now consider the sequence of identically distributed independent blocks $(U^{\prime}(H_{l}))_{l=1,\dots,\mu_{n-m}}$ such that each block $U^{\prime}(H_{l})$ has the same distribution as $U(H_{l})$. We are going to use the following technical result.

By applying Lemma 5, Equation (28) leads to:

We can now use the following concentration result for martingales.

Let $X=(X_{0},\dots,X_{n})$ be a discrete time martingale taking values in an Euclidean space such that $X_{0}=0$ and for all $i$, $\|X_{i}-X_{i-1}\|_{2}\leq B_{2}$ almost surely. Then for all $\epsilon$,

where the second line is obtained by using the fact that $2a_{n-m}\mu_{n-m}=n-m$. With Equations (28) and (29), we finally obtain

The vector $U^{m}_{i}$ is a function of $Z_{i}=(X_{i-m+1},\dots,X_{i+1})$, and Lemma 1 tells us that for all $j>m$,

So the equation above may be re-written as

We now follow a reasoning similar to that of Lazaric et al. (2012) in order to get the same exponent in both of the above exponentials. Taking $a_{n-m}-m=\left\lceil\frac{C_{2}(n-m)\epsilon^{2}}{b}\right\rceil^{\frac{1}{\kappa+1}}$ with $C_{2}=(16C^{2}\zeta)^{-1}$, and $\zeta=\frac{a_{n-m}}{a_{n-m}-m}$, we have

IndeedThis inequality exists in Lazaric et al. (2012), and is developped here for completeness., there are two cases:

Suppose that $\min\left\{\left(\frac{b}{(n-m)(\epsilon(\delta))^{2}C_{2}}\right),1\right\}=1$. Then

Suppose now that $\min\left\{\left(\frac{b}{(n-m)(\epsilon(\delta))^{2}C_{2}}\right),1\right\}=\left(\frac{b}{(n-m)(\epsilon(\delta))^{2}C_{2}}\right)$. Then

By combining Equations (31) and (32), we get

If we replace $\Lambda(n-m,\delta)$ with its expression, we obtain

Since $4e^{2}\max\{4e^{2},(n-m)\overline{\beta}\}^{-1}\leq 1$ and $(n-m)\overline{\beta}\max\{4e^{2},(n-m)\overline{\beta}\}^{-1}\leq 1$, we consequently have

Now, note that since $a_{n-m}-m\geq 1$, we have

Let $J(n,\delta)=32\Lambda(n,\delta)\max\left\{\frac{\Lambda(n,\delta)}{b},1\right\}^{\frac{1}{\kappa}}$. Then Equation (30) is reduced to

Since $J(n,\delta)$ is an increasing function on $n$, and $\frac{n-1}{\sqrt{n-1}(n-m)}=\frac{1}{\sqrt{n-m}}\sqrt{\frac{n-1}{n-m}}\geq\frac{1}{\sqrt{n-m}}$, we have

By using Equations (24) and (33), we deduce that

By combining Equations (22), (23),(34), plugging the value of $C=\frac{2\sqrt{dk}LL^{\prime}}{1-\lambda\gamma}$, and taking $m=\left\lceil\frac{\log{(n-1)}}{\log\frac{1}{\lambda\gamma}}\right\rceil$, we get the announced result.

References