DOI: 10.12677/PM.2024.141041, PDF, HTML, XML,  被引量   
作者: 朱亚楠：上海理工大学，理学院，上海
关键词: 线性二次最优控制；梯度下降；资格迹；Linear Quadratic Optimal Control； Gradient Descent； Eligibility Traces

文章引用：朱亚楠. 随机线性二次控制的资格迹方法[J]. 理论数学, 2024, 14(1): 416-432. https://doi.org/10.12677/PM.2024.141041

1. 引言

线性二次型控制(LQR)问题是最优控制理论中最基本的问题之一，系统下一时刻的状态由当前状态和控制决定，代价是关于状态和控制的二次函数 [1] 。问题的目标是找到最优的系统控制，使得代价函数达到最小值。在系统参数完全已知的情况下，LQR问题已经有广泛的研究，最优控制存在解析表达式 [2] ，被广泛应用在不同领域中。在实际应用中，获取系统所有参数时不现实的，当系统参数未知时，产生许多不确定性，无法直接求解得到最优控制，这促进了对学习方法的探索。

近年来使用强化学习和数据驱动方法解决不确定动力系统问题取得重要进展，强化学习方法成为解决此类不确定问题的有效手段。强化学习(RL) [3] 是交互式的学习方法，通过与环境交互积累经验(采样)，以最大化数值收益信号为导向，不断从经验中学习，最终得到最优策略(控制)。在已有的研究中，利用RL方法解决参数未知的LQR问题，有基于模型的方法 [4] [5] [6] 和无模型的方法 [7] [8] [9] 两种。基于模型的RL方法利用经验数据估计系统模型参数，将参数估计值视为真实值进而通过解析表达式求解最优控制 [10] [11] ；无模型的RL方法直接与系统环境交互，利用经验数据直接学习最优控制而不估计参数 [12] [13] 。LQR问题的最优控制是状态的线性函数，在学习方法的框架下，相当于优化矩阵形式的参数。自然的想法是在参数空间中使用梯度下降算法，将控制参数化，即RL中的策略梯度算法。这种方法基于代价函数对控制参数的梯度，对参数进行优化。有模型的RL方法在模型结构已知时具有更好的表现，无模型方法则更少依赖于模型假设，具有更好的泛化性能 [14] 。

RL方法在实践中效果突出，但理论理解较少，相比之下，控制理论已经有较为成熟的研究成果，具有可证明的保证。系统参数已知时，控制优化过程中需要的梯度项有明确的表达式，易于计算；参数未知时，用经验数据对梯度项进行近似，现有的梯度近似有零阶近似、二阶近似以及样条逼近等方法。Dhruv Malik等人给出了零阶近似方法在线性控制问题中的收敛保证 [15] 。Maryam Fazel等人研究了初始状态有噪声干扰的情况下，不同梯度优化方的全局收敛性 [16] 。Ben Hambly等人在有限时域和随机状态转移的设置下为零阶近似方法提供了全局收敛保证 [17] 。Mesbahi A等人将结果推广至连续时间的LQR问题 [18] [19] 。

LQR问题描述

有限时域T下的随机离散时间LQR问题，系统方程为：

$x_{t+1}=A{x}_t+B{u}_t+{\omega }_t$ (1)

其中， $x_t\in {ℝ}^d$ 和 $u_t\in {ℝ}^k$ 分别是系统在t时刻的状态向量和控制向量， $x_0$ 从分布 $\mathcal{D}$ 中随机抽样， ${\omega }_t\left(t\in \left[T\right]=0,1,\cdots ,T-1\right)$ 是独立同分布的零均值系统噪声序列，与 $x_0$ 独立。 $A\in {ℝ}^{d\times d}$ 和 $B\in {ℝ}^{d\times k}$ 是系统转移矩阵。系统(1)对应的代价函数为：

$C\left(K\right)=E\left[{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\left(x_t^T{Q}_t{x}_t+u_t^T{R}_t{u}_t\right)+x_T^T{Q}_T{x}_T}\right]$ (2)

其中， $Q_t\in {ℝ}^{d\times d}$ 是对称正定矩阵， $R_t\in {ℝ}^{k\times k}$ 是正定矩阵， $K=\left(K_0,K_1,\cdots ,K_{T-1}\right)$ 是控制序列。

离散时间LQR问题的目标是在可行控制空间 $\mathcal{U}$ 中找到使代价函数值最小的最优控制，在系统参数已知时，有限时域的离散时间LQR问题的最优控制有显式解，当 $\left(A,B\right)$ 可控时，根据最优控制理论 [20] ，t时刻的最优控制为当前状态的线性函数：

$\begin{array}{l}{u}_t^{*}=-K_t^{*}{x}_t\hfill \\ K_t^{*}={\left(B^T{P}_{t+1}^{*}B+R_t\right)}^{-1}{B}^T{P}_{t+1}^{*}A\hfill \end{array}\begin{array}{cc}& \forall t\in \left[T\right]\end{array}$ (3)

其中， $K_t^{*}\in {ℝ}^{k\times d}$ 是t时刻的最优控制， $P_t{}^{*}$ 是以下代数黎卡提方程的解：

$P_t{}^{*}=Q_t+A^T{P}_{t+1}^{*}A-A^T{P}_{t+1}^{*}B{\left(B^T{P}_{t+1}^{*}B+R_t\right)}^{-1}{B}^T{P}_{t+1}^{*}A$ (4)

黎卡提方程的求解通常令 $P_T=Q_T$ ，通过递推式(6)进行迭代求解，直到满足精度要求。此时，代价函数达到最小值

$C\left(K^{*}\right)=E\left[{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}{x}_t^T{P}_t^{*}{x}_t}\right]$ .

上述通过求解代数黎卡提方程进而得到最优控制的方法有以下缺点：1) 并不直接优化控制增益 $K_t$ ，也不直接优化代价函数；2) 在求解黎卡提方程时涉及高维矩阵的求逆运算，消耗的计算量在系统维度高时过大；3) 当系统参数 $\theta =\left(A,B,{\left\{Q_t\right\}}_{t=0}^{T-1},{\left\{R_t\right\}}_{t=0}^{T-1}\right)$ 未知时，这种方法并不适用。

本文研究有限时域下的离散时间随机线性二次控制(DLQR)问题，在策略梯度方法中引入资格迹方法，不求解代数黎卡提方程，直接优化控制增益。资格迹方法是强化学习的基本方法之一，在优化中引入与控制参数向量同维度的资格迹向量，衡量系统控制参数每个分量的重要性，在学习过程中影响参数向量的更新 [3] 。这种方法不仅适用于分幕式的情况，也适用于持续性问题。在实际效果方面，资格迹方法比策略梯度算法更快收敛，且方差更小，数值模拟结果证明了这一结论。

2. 理论

本文考虑折现的随机DLQR问题：

$\begin{array}{ll}\underset{K}{\min }\hfill & C\left(K\right)=E\left[{\displaystyle {\sum }_{t=0}^{T-1}{\gamma }^t{c}_t\left(x_t,u_t\right)+{\gamma }^T{c}_T\left(x_T\right)}\right]\hfill \\ \text{s}\text{.t}.\hfill & x_{t+1}=A{x}_t+B{u}_t+{\omega }_t\hfill \end{array}$ (5)

其中 $\gamma \in \left(0,1\right)$ 是折现因子，单步的代价 $c_t\left(x_t,u_t\right)=x_t^T{Q}_t{x}_t+u_t^T{R}_t{u}_t,t\in \left[T\right]$ ， $c_T\left(x_T\right)=x_T^T{Q}_T{x}_T$ 。控制增益遵循以下法则优化：

$\begin{array}{l}{K}^{n+1}=K^n-\alpha {\delta }^n\hfill \\ {\delta }^0=\nabla C\left(K^0\right)\hfill \\ {\delta }^n=\lambda {\delta }^{n-1}+\nabla C\left(K^n\right),n>0\hfill \end{array}\forall t\in \left[T\right]$ (6)

其中， $n\in \left[N\right]$ 是迭代次数， $\alpha$ 是步长参数， $\lambda$ 是衰减参数， $K^n=\left(K_0^n,K_1^n,\cdots ,K_{T-1}^n\right)$ 是第n次迭代时的控制序列， ${\delta }^n=\left({\delta }_0^n,{\delta }_1^n,\cdots ,{\delta }_{T-1}^n\right)$ 是与之对应的资格迹序列。

引理2.1 在策略参数的第n次迭代中，定义状态向量的协方差矩阵为：

${\Sigma }_t=E\left[x_t{x}_t^T\right]$ , ${\Sigma }_K={\displaystyle \underset{t=0}{\overset{T-1}{\sum }}{\Sigma }_t}$ (7)

则与 $K_t$ 对应的资格迹由以下表达式给出：

${\delta }_t^n=\{\begin{array}{ll}2{\gamma }^t{E}_t^n{\Sigma }_t^n\hfill & n=0\hfill \\ \lambda {\delta }_t^{n-1}+2{\gamma }^t{E}_t^n{\Sigma }_t^n\hfill & n>0\hfill \end{array},\forall t\in \left[T\right]$ (8)

其中， $E_t^n=\left(R_t+\gamma B^T{P}_{t+1}^{n}B\right)K_t-\gamma B^T{P}_{t+1}^{n}A$ 。

证明：根据资格迹的定义，

${\delta }_t^n=\lambda {\delta }_t^{n-1}+{\nabla }_{t}C\left(K^n\right),n>0$ (9)

随机DLQR问题(5)中，代价函数可拆分为初始状态项与噪声项：

$\begin{array}{c}C\left(K\right)=E\left[\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t{c}_t\left(x_t,u_t\right)+{\gamma }^T{c}_T\left(x_T\right)\right]\\ =E\left[\underset{t=0}{\overset{T-2}{{\displaystyle \sum }}}{\gamma }^t{c}_t\left(x_t,u_t\right)+{\gamma }^{T-1}{c}_{T-1}\left(x_{T-1},-K_{T-1}{x}_{T-1}\right)+{\gamma }^T{c}_T\left(x_T\right)\right]\\ =E\left[\underset{t=0}{\overset{T-2}{{\displaystyle \sum }}}{\gamma }^t{c}_t\left(x_t,u_t\right)+{\gamma }^{T-1}{x}_{{}_{T-1}}^T{P}_{T-1}{x}_{T-1}+{\gamma }^T{\omega }_{{}_{T-1}}^T{P}_T{\omega }_{T-1}\right]\\ =E\left[x_0^T{P}_0{x}_0+\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^{t+1}{\omega }_t^T{P}_{t+1}{\omega }_t\right]\end{array}$ (10)

上式对 $K_t$ 求偏导，

$\begin{array}{c}{\nabla }_{t}C\left(K\right)=\frac{\partial C\left(K\right)}{\partial K_t}\\ =\frac{\partial E\left[{\gamma }^t{x}_t^T\left(Q_t+K_t^T{R}_t{K}_t+\gamma {\left(A-B{K}_t\right)}^T{P}_{t+1}\left(A-B{K}_t\right)\right)x_t+K\left(-t\right)\right]}{\partial K_t}\\ =E\left[2{\gamma }^t{R}_t{K}_t{x}_t{x}_t^T-2{\gamma }^{t+1}{B}^T{P}_{t+1}\left(A-B{K}_t\right)x_t{x}_t^T\right]\\ =2{\gamma }^t{E}_t{\Sigma }_t\end{array}$ (11)

其中， $K\left(-t\right)=\underset{j=0}{\overset{t-1}{{\displaystyle \sum }}}{\gamma }^j{c}_j\left(x_j,u_j\right)+\underset{j=t+1}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^j{\omega }_j^T{P}_{j+1}{\omega }_j$ 证毕。

对衰减参数 $\lambda$ 的不同设置，是衡量历史信息对下一步决策的重要程度，当 $\lambda =0$ 时，不考虑历史信息，当 $\lambda =1$ 时，则认为历史信息与当前信息同样重要。资格迹方法考虑了当前的损失函数和历史策略梯度的关系，而梯度下降算法只考虑梯度更新的平滑度。资格迹方法能够减少参数更新过程中忽略影响较大的历史动量而造成的错误决策次数。

2.1. 参数已知的资格迹方法

本节讨论系统参数 $\theta$ 完全已知时的资格迹方法 [3] 。资格迹方法结合了蒙特卡洛方法和时序差分方法。算法的核心是定义一个维度与策略参数相同的短时记忆向量 $\delta$ ，衡量策略参数分量的重要性。随着迭代次数的增加，和参与更新的控制参数分量对应的资格迹分量逐渐衰减，直到这一分量再次参与更新。本文用资格迹代替参数更新中的梯度项，增强了算法的泛化性能。

在分析算法收敛性之前，首先研究不同控制序列下产生的代价函数的差异以及状态协方差矩阵间的差异上界，定义 $\Vert S\Vert$ 为矩阵S的谱范数。

引理2.2 [17] 假设 $K^{\prime }$ 与 $K$ 产生的代价函数均有界， ${\left\{x_t\right\}}_{t=0}^{T-1}$ ， ${\left\{u_t\right\}}_{t=0}^{T-1}$ ， ${\left\{{x^{\prime }}_t\right\}}_{t=0}^{T-1}$ ， ${\left\{{u^{\prime }}_t\right\}}_{t=0}^{T-1}$ 分别是由 $K^{\prime }$ ， $K$ 生成的序列，令 ${x^{\prime }}_0=x_0=x$ ，则代价差可表示为：

$\begin{array}{c}C\left(K^{\prime }\right)-C\left(K\right)=E\left[{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}2Tr\left({x^{\prime }}_t{\left({x^{\prime }}_t\right)}^T{\left({K^{\prime }}_t-K_t\right)}^T{E}_t\right)}\right]\\ +E\left[{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}Tr\left({x^{\prime }}_t{\left({x^{\prime }}_t\right)}^T{\left({K^{\prime }}_t-K_t\right)}^T\left(R_t+\gamma B^T{P}_{t+1}B\right)\left({K^{\prime }}_t-K_t\right)\right)}\right]\end{array}$ (12)

其中， $P_t$ 是下述方程的解：

$P_t=Q_t+K_t^T{R}_t{K}_t+\gamma {\left(A-B{K}_t\right)}^T{P}_{t+1}\left(A-B{K}_t\right),\forall t\in \left[T\right]$ (13)

引理2.3 令 $\rho =\max \left\{\underset{t}{\max }\Vert A-B{K}_t\Vert ,\underset{t}{\max }\Vert A-B{K^{\prime }}_t\Vert \right\}$ ， $\Delta =K_t-{K^{\prime }}_t$ ， $K^{\prime }$ 与 $K$ 是任意策略，系统状态向量的协方差满足下面的关系：

$\Vert {\Sigma }_K-{\Sigma }_{K^{\prime }}\Vert \le \frac{{\rho }^{2T}-1}{{\rho }^2-1}\left(2\rho \Vert B\Vert {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert \Delta \Vert +{\Vert B\Vert }^2{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}{\Vert \Delta \Vert }^2}}\right)\left(\frac{C\left(K\right)}{{\sigma }_{\min }Q}+T\Vert W\Vert \right)$ (14)

证明详见附录。

上面的分析为收敛保证奠定了基础，证明算法的收敛性之前，引理2.4的论证了控制序列经过一次迭代后对代价函数值的影响。

引理2.4 设 $K^{*}$ 是最优至序列， $K^{\prime }$ 由 $K$ 经一次迭代得到，当

$\alpha \le \min \left\{{\alpha }_1,\frac{{\sigma }_{\min }Q}{2C\left(K\right)T\underset{t}{\max }\Vert R_t+\gamma B^T{P}_{t+1}B\Vert }\right\}$

其中，

${\alpha }_1=\frac{{\rho }^2-1}{2\left({\rho }^{2T}-1\right)\left(2\rho +1\right)\Vert B\Vert }\cdot \frac{{\sigma }_{\min }Q{\sigma }_{\min }{\Sigma }_K}{C\left(K\right)+T\Vert W\Vert {\sigma }_{\min }Q}\cdot \frac{1}{\underset{t}{\max }\Vert {\delta }_t\Vert }$

则

$C\left(K^{\prime }\right)-C\left(K^{*}\right)\le \left(1-\frac{\text{4}\alpha {\sigma }_{\min }R{\sigma }_{{\min }^2}{\Sigma }_K}{\Vert {\Sigma }_{K^{*}}\Vert }\right)C\left(K\right)-C\left(K^{*}\right)$ (15)

证明详见附录。

经过以上分析，下面给出参数已知时，资格迹算法在DLQR问题中的全局收敛性保证。

定理2.4 (收敛性定理)假设 $C\left(K^0\right)$ 有界，步长 $\alpha$ 满足引理2.4的约束，对 $\forall \epsilon >0$ ，当迭代次数N满足下述条件：

$N\ge \frac{\Vert {\Sigma }_{K^{*}}\Vert }{4\alpha {\sigma }_{{\min }^2}{\Sigma }_K{\sigma }_{\min }R}\log \frac{C\left(K^0\right)-C\left(K^{*}\right)}{\epsilon }$

代价函数值收敛至最优值，即：

$C\left(K^N\right)-C\left(K^{*}\right)\le \epsilon$ (16)

证明：令，根据引理2.4的结论，

$C\left(K^1\right)-C\left(K^{*}\right)\le \left(1-\frac{4\alpha {\sigma }_{\min }R{\sigma }_{{\min }^2}{\Sigma }_K}{\Vert {\Sigma }_{K^{*}}\Vert }\right)\left(C\left(K^0\right)-C\left(K^{*}\right)\right)$

假设经 $n+1$ 次迭代后， $C\left(K^{n+1}\right)\le C\left(K^0\right)$ ，此时 $K_t^{n+1}=K_t^n-\alpha {\delta }_t^n$ ，根据Cauchy-Schwarz不等式，

$\begin{array}{c}\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\delta }_t^n=\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}\underset{i=0}{\overset{n}{{\displaystyle \sum }}}{\lambda }^{n-i}{\nabla }_{t}C\left(K^n\right)\le \underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}\sqrt{n\underset{i=0}{\overset{n}{{\displaystyle \sum }}}{\Vert {\nabla }_{t}C\left(K^n\right)\Vert }^2}\\ \le \underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}\sqrt{4n\underset{i=0}{\overset{n}{{\displaystyle \sum }}}Tr\left({\text{Σ}}_t^i{\left(E_t^i\right)}^T{E}_t^i{\text{Σ}}_t^i\right)}\\ \le \sqrt{T\cdot \underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}4n\underset{i=0}{\overset{n}{{\displaystyle \sum }}}{\Vert {\text{Σ}}_t^i\Vert }^{2}Tr\left({\left(E_t^i\right)}^T{E}_t^i\right)}\\ \le \left(\frac{2C\left(K\right)}{{\sigma }_{\min }Q}\right)\sqrt{nT\frac{\underset{t}{\max }\left(R_t+\gamma B^T{P}_{t}B\right)}{{\sigma }_{\min }{\text{Σ}}_K}\left(C\left(K\right)-C\left(K^{\ast }\right)\right)}\end{array}$

最后一个不等式成立基于下面的结果：

$\begin{array}{c}C\left(K\right)-C\left(K^{\ast }\right)\ge C\left(K\right)-C\left(K^{\prime }\right)\\ =E\left[\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}Tr\left(E_t^T{\left(R_t+\gamma B^T{P}_{t+1}B\right)}^{-1}{E}_t\right)\right]\\ \ge \frac{{\sigma }_{\min }{\text{Σ}}_K}{\underset{t}{\max }\left(R_t+\gamma B^T{P}_{t}B\right)}\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}Tr\left(E_t^T{E}_t\right)\end{array}$

结合引理2.3的分析，引理2.3中的结论仍然成立，即：

$C\left(K^{n+1}\right)-C\left(K^{*}\right)\le \left(1-\frac{4\alpha {\sigma }_{\min }R{\sigma }_{\min }^2{\Sigma }_K}{\Vert {\Sigma }_{K^{*}}\Vert }\right)\left(C\left(K^n\right)-C\left(K^{*}\right)\right)$ (17)

将 $n+1$ 次的结果进行累积，

$C\left(K^{n+1}\right)-C\left(K^{*}\right)\le {\left(1-\frac{4\alpha {\sigma }_{\min }R{\sigma }_{\min }^2{\Sigma }_K}{\Vert {\Sigma }_{K^{*}}\Vert }\right)}^{n+1}\left(C\left(K^0\right)-C\left(K^{*}\right)\right)$

对 $\forall \epsilon >0$ ，当

$N\ge \frac{\Vert {\Sigma }_{K^{*}}\Vert }{4\alpha {\sigma }_{\min }^2{\Sigma }_K{\sigma }_{\min }R}\log \frac{C\left(K^0\right)-C\left(K^{*}\right)}{\epsilon }$

时， $C\left(K^N\right)-C\left(K^{*}\right)<\epsilon$ 。证毕。

2.2. 参数未知的资格迹方法

当系统参数θ未知时，式(13)中对梯度项的表达无效，在控制增益的更新中，性能指标的资格迹无法以解析式精确表达，只能对模型进行仿真得到训练数据。本文使用零阶优化方法 [6] 近似资格迹，无无需估计系统参数，直接利用目标函数的值优化控制增益。并且零阶优化方法对目标函数的凸性没有要求，直接用函数值估计函数梯度，这大大降低了算法的复杂度。本节首先分析零阶优化方法在随机最优化问题上的拓展 [11] [18] ，在DLQR问题中，参数未知时，在每一步的控制上加入随机噪声进行采样来估计代价函数值。目标函数可表示为

$C\left(K\right)=E_{\omega }\left[C\left(K;\omega \right)\right]$ (18)

这里利用带噪声的代价函数值构造梯度的近似无偏估计。令 ${\mathbb{U}}^r=\left\{U\in {ℝ}^{k\times d}:{\Vert U\Vert }_F=r\right\}$ ，设 ${\mathcal{P}}_{\mathbb{U}}$ 是 ${\mathbb{U}}^r$ 上的均匀分布。任意给一个度量 $r>0$ ，以及 $U\sim {\mathcal{P}}_{\mathbb{U}}$ 与 $\omega$ 独立，则零阶优化方法对 $C\left(K\right)$ 的梯度估计为：

$\nabla C\left(K\right)=\frac{k\times d}{r}C\left(K+rU\right)U$ (19)

随着r越来越小，近似值越来越精确 [11] ，但r过小可能导致估计值有较大的方差。表1给出了算法的框架。

引理2.5 对给定的 $r>0$ 以及从 ${\upsilon }^r=\left\{U\in {ℝ}^d:{\Vert U\Vert }_F=r\right\}$ 中随机抽取的随机向量 $U$ ，I为采样幕数， $\lambda$ 是折扣系数，资格迹的经验近似为：

${\hat{\delta }}_t^n=\{\begin{array}{ll}\frac{1}{I}{\displaystyle \underset{i=0}{\overset{I-1}{\sum }}\frac{D}{r^2}{\hat{c}}_t^i{U}_t^i}\hfill & n=0\hfill \\ \lambda {\hat{\delta }}_t^{n-1}+\frac{1}{I}{\displaystyle \underset{i=0}{\overset{I-1}{\sum }}\frac{D}{r^2}{\hat{c}}_t^i{U}_t^i}\hfill & n>0\hfill \end{array}$ (20)

其中，

${\hat{c}}_t^i={\displaystyle \underset{t=0}{\overset{T-1}{\sum }}{\gamma }^t\left({\left(x_t^i\right)}^T{Q}_t{x}_t^i+{\left(u_t^i\right)}^T{R}_t{u}_t^i\right)+{\left(x_T^i\right)}^T{Q}_T{x}_T^i}$

引理2.6 假设任意不同控制 $K^{\prime }$ 与 $K$ 的分量满足：

$\Vert {K^{\prime }}_t-K_t\Vert \le \min \left\{\Vert K_t\Vert ,\frac{\left({\rho }^2-1\right){\sigma }_{\min }Q{\sigma }_{\min }{\Sigma }_K}{2T\left({\rho }^{2T}-1\right)\left(2\rho +1\right)\left(C\left(K\right)+{\sigma }_{\min }QT\Vert W\Vert \right)\Vert B\Vert }\right\}$ (21)

则存在

$h_C\le \left\{\frac{{\rho }^2-1}{\left(2\rho +1\right)\left({\rho }^{2T}-1\right)}\cdot \frac{1}{\Vert B\Vert }\cdot \frac{1}{\Vert W\Vert }\cdot \frac{1}{C\left(K^0\right)}\right\}$ , $h_g\le \left\{\frac{{\rho }^2-1}{\left(2\rho +1\right)\left({\rho }^{2T}-1\right)}\cdot \frac{1}{\Vert B\Vert }\cdot \frac{1}{\Vert W\Vert }\cdot \frac{{\sigma }_{\min }Q}{C\left(K^0\right)}\frac{1}{\Vert {\Sigma }_{K^0}\Vert }\right\}$

使得，

$\left|C\left(K^{\prime }\right)-C\left(K\right)\right|\le h_C\underset{t=0}{\stackrel{T-1}{\sum }}\Vert {K^{\prime }}_t-K_t\Vert$ , $\Vert {\nabla }_{t}C\left(K^{\prime }\right)-{\nabla }_{t}C\left(K\right)\Vert \le h_g\underset{t=0}{\stackrel{T-1}{\sum }}\Vert {K^{\prime }}_t-K_t\Vert$

证明详见附录。

引理2.7 对 $\forall \epsilon >0$ ，当 $r\le \frac{\epsilon }{4h_g}$ 时，资格迹的经验近似满足：

${\Vert {\hat{\delta }}_t^n-{\delta }_t^n\Vert }_F\le \epsilon$ , $\forall t\in \left[T\right]$

证明详见附录。

定理2.8 (收敛性定理)假设 $C\left(K^0\right)$ 有界，步长 $\alpha$ 满足引理2.3的约束，对 $\forall \epsilon >0$ ，当迭代次数N满足

$N\ge \frac{\Vert {\Sigma }_{K^{*}}\Vert }{2\alpha {\sigma }_{{\min }^2}{\Sigma }_K{\sigma }_{\min }R}\log \frac{C\left(K^0\right)-C\left(K^{*}\right)}{\epsilon }$

代价函数值收敛至最优值，即：

$C\left(K^N\right)-C\left(K^{*}\right)\le \epsilon$ (22)

证明：令 ${K^{\prime }}_t=K_t-\alpha {\delta }_t$ ，根据引理2.4，有

$C\left(K^{\prime }\right)-C\left(K^{*}\right)\le \left(1-\frac{4\alpha {\sigma }_{\min }R{\sigma }_{\min }^2{\Sigma }_K}{\Vert {\Sigma }_{K^{*}}\Vert }\right)\left(C\left(K\right)-C\left(K^{*}\right)\right)$ (23)

令 ${{\hat{K}}^{\prime }}_t=K_t-\alpha {\hat{\delta }}_t$ ，当样本数足够多时，只要 $C\left(K\right)-C\left(K^{*}\right)\ge \epsilon$ 时，

$C\left({\hat{K}}^{\prime }\right)-C\left(K^{*}\right)\le \left(1-\frac{4\alpha {\sigma }_{\min }R{\sigma }_{\min }^2{\Sigma }_K}{\Vert {\Sigma }_{K^{*}}\Vert }\right)\left(C\left(K\right)-C\left(K^{*}\right)\right)$ (24)

因为

$C\left({\hat{K}}^{\prime }\right)-C\left(K^{*}\right)=C\left({\hat{K}}^{\prime }\right)-C\left(K^{\prime }\right)+C\left(K^{\prime }\right)-C(\; K\; *\; )$

首先讨论右式第一项，根据引理2.6，当 $\forall t\in T$ ，若

$\Vert {\widehat{K^{\prime }}}_t-{K^{\prime }}_t\Vert \le \frac{\alpha {\sigma }_{\min }R{\sigma }_{\min }^2{\Sigma }_K}{T\Vert {\Sigma }_{K^{*}}\Vert h_C}\epsilon$

成立，则有

$\left|C\left({\hat{K}}^{\prime }\right)-C\left(K^{\prime }\right)\right|\le \frac{\alpha {\sigma }_{\min }R{\sigma }_{\min }^2{\Sigma }_K}{\Vert {\Sigma }_{K^{*}}\Vert }\epsilon$

因为 ${\widehat{K^{\prime }}}_t-{K^{\prime }}_t=\alpha \left({\delta }_t-{\hat{\delta }}_t\right)$ ，所以只需证明

$\Vert {\delta }_t-{\hat{\delta }}_t\Vert \le \frac{{\sigma }_{\min }R{\sigma }_{\min }^2{\Sigma }_K}{T\Vert {\Sigma }_{K^{*}}\Vert h_C}\epsilon$ (25)

根据引理2.7，上式成立。综上所述

$C\left({\hat{K}}^{\prime }\right)-C\left(K^{*}\right)\le \left(1-\frac{3\alpha {\sigma }_{\min }R{\sigma }_{\min }^2{\Sigma }_K}{\Vert {\Sigma }_{K^{*}}\Vert }\right)\left(C\left(K\right)-C\left(K^{*}\right)\right)$ (26)

基于以上结论，与定理2.4相同的证明保证了收敛性。

3. 数值模拟

当状态维度d = 2时，设定系统参数为

$A=\left(\begin{array}{cc}0.9& -1.1\\ 1.0& 0.8\end{array}\right),B=\left(\begin{array}{c}0.8\\ 1\end{array}\right),Q=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),R=1$

折现因子 $\gamma =0.99$ ，比较资格迹方法与梯度下降算法的收敛情况。在折扣系数 $\lambda =0.1$ 的条件下，设定指数衰减的步长参数，分别令时域T = 20，迭代次数N = 40；时域T = 50，迭代次数N = 70，代价函数的收敛情况见见图1和图2：

图1和图2的结果说明，资格迹算法比梯度下降算法具有更快的收敛速度。资格迹方法中折扣系数的取值对最终结果有显著影响，图3展示了T = 50，N = 70时不同的折扣系数对算法性能的影响：

在本节设定的系统参数下，图3的结果显示，折扣系数 $\lambda <0.3$ 时，资格迹算法表现优于策略梯度算法，当 $\lambda >0.3$ 后，结果出现不收敛的情况，随λ的增大，结果偏离越大。λ是过去梯度信息的权重，说明在这一数值范例中，过去梯度信息对问题求解只能提供少量信息。

当状态维度d = 4时，设定系统参数为

$A=\left(\begin{array}{cccc}0.3& 0.3& 0.1& 0.2\\ 0.2& 0.2& 0.3& 0.1\\ 0.3& 0.1& 0.3& 0.4\\ 0.3& 0.2& 0.15& 0.1\end{array}\right),B=\left(\begin{array}{cc}0.4& 0.3\\ -0.5& 0.1\\ 1.0& 0.2\\ 0.2& 0.9\end{array}\right)$

$Q=\left(\begin{array}{cccc}0.9& 0.2& -0.5& 0.15\\ 0.2& 1.1& 0.15& 0.1\\ -0.5& 0.15& 0.9& -0.8\\ 0.15& 0.1& -0.8& 0.88\end{array}\right),R=\left(\begin{array}{cc}0.9& -0.5\\ -0.5& 0.8\end{array}\right)$

设定T = 50，N = 100，其余参数与二维系统相同，代价函数收敛情况如图4所示：

上述数值结果说明资格迹方法的收敛效果优于传统的资格梯度方法，并且在算法初期方差更小。

4. 结论

本文研究了无模型强化学习方法在有限时域离散LQR问题中的应用，不同于通过解代数黎卡提方程得到最优控制的方法，本文直接优化控制增益，在梯度下降算法的基础上引入资格迹方法，并给出在参数已知和参数未知两种情况下算法的收敛保证。在初始代价函数有界的条件下，算法可以扩展至无限时域。数值模拟验证了算法的收敛性，展示了不同参数设置对结果的影响。另一个方向是基于有模型的强化学习方法，在更少样本量的基础上，进一步达到更好的收敛结果。

致谢

感谢张老师在论文写作过程中给出的指导和建议。

附录

引理2.3证明：

在对 ${\Sigma }_K$ 进行分析前，定义以下线性算子以方便证明。令

${\mathcal{F}}_{K_t}\left(\Sigma \right)=\left(A-B{K}_t\right)\Sigma {\left(A-B{K}_t\right)}^T$ , ${\mathcal{G}}_t\left(\Sigma \right)={\mathcal{F}}_{K_t}\circ {\mathcal{F}}_{K_{t-1}}\circ \cdots \circ {\mathcal{F}}_{K_0}$

$\begin{array}{c}{\Sigma }_{t+1}=E\left(\left(\left(A-B{K}_t\right)x_t+{\omega }_t\right){\left(\left(A-B{K}_t\right)x_t+{\omega }_t\right)}^T\right)\\ =\left(A-B{K}_t\right){\Sigma }_t{\left(A-B{K}_t\right)}^T+W={\mathcal{F}}_{K_t}\left({\Sigma }_t\right)+W\\ =\left(A-B{K}_t\right)\left({\mathcal{F}}_{K_{t-1}}\left({\Sigma }_{t-1}\right)+W\right){\left(A-B{K}_{t-1}\right)}^T+W\\ ={\mathcal{F}}_{K_t}\circ {\mathcal{F}}_{K_{t-1}}\left({\Sigma }_{t-1}\right)+{\mathcal{F}}_{K_t}\left(W\right)+W\\ ={\mathcal{F}}_{K_t}\circ {\mathcal{F}}_{K_{t-1}}\circ {\mathcal{F}}_{K_{t-2}}\left({\Sigma }_{t-2}\right)+{\mathcal{F}}_{K_t}\circ {\mathcal{F}}_{K_{t-1}}\left(W\right)+{\mathcal{F}}_{K_t}\left(W\right)+W\\ ={\mathcal{G}}_t\left({\Sigma }_0\right)+{\displaystyle \underset{s=0}{\overset{t}{\sum }}{\displaystyle \underset{u=0}{\overset{s}{\prod }}{\mathcal{F}}_{K_t}\circ \cdots \circ {\mathcal{F}}_{K_{t-u}}\left(W\right)}}+W\end{array}$

${\Sigma }_K={\Sigma }_0+{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\left[{\mathcal{G}}_t\left({\Sigma }_0\right)+{\displaystyle \underset{s=0}{\overset{t}{\sum }}{\displaystyle \underset{u=0}{\overset{s}{\prod }}{\mathcal{F}}_{K_t}\circ \cdots \circ {\mathcal{F}}_{K_{t-u}}\left(W\right)}}\right]+TW}$

$\begin{array}{c}{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert \left({{\mathcal{G}}^{\prime }}_t-{\mathcal{G}}_t\right)\left({\Sigma }_0\right)\Vert }\le {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert \left({\mathcal{F}}_{{K^{\prime }}_t}\circ {{\mathcal{G}}^{\prime }}_{t-1}-{\mathcal{F}}_{{K^{\prime }}_t}\circ {\mathcal{G}}_{t-1}+{\mathcal{F}}_{{K^{\prime }}_t}\circ {\mathcal{G}}_{t-1}-{\mathcal{F}}_{K_t}\circ {\mathcal{G}}_{t-1}\right)\left({\Sigma }_0\right)\Vert }\\ \le {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert {\mathcal{F}}_{{K^{\prime }}_t}\Vert \Vert \left({{\mathcal{G}}^{\prime }}_{t-1}-{\mathcal{G}}_{t-1}\right)\left({\Sigma }_0\right)\Vert }+\Vert {\mathcal{G}}_{t-1}\Vert \Vert \left({\mathcal{F}}_{{K^{\prime }}_t}-{\mathcal{F}}_{K_t}\right)\left({\Sigma }_0\right)\Vert \\ \le {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}{\rho }^2\Vert \left({{\mathcal{G}}^{\prime }}_{t-1}-{\mathcal{G}}_{t-1}\right)\left({\Sigma }_0\right)\Vert }+{\rho }^{2\left(t+1\right)}\Vert \left({\mathcal{F}}_{{K^{\prime }}_t}-{\mathcal{F}}_{K_t}\right)\left({\Sigma }_0\right)\Vert \\ \le \frac{{\rho }^{2T}-1}{{\rho }^2-1}{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert \left({\mathcal{F}}_{{K^{\prime }}_t}-{\mathcal{F}}_{K_t}\right)\left({\Sigma }_0\right)\Vert }\end{array}$

$\begin{array}{c}{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert \left({\mathcal{F}}_{K_t}-{\mathcal{F}}_{{K^{\prime }}_t}\right)\left({\Sigma }_0\right)\Vert }={\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert \left(A-B{K}_t\right){\Sigma }_0{\left(A-B{K}_t\right)}^T-\left(A-B{K^{\prime }}_t\right){\Sigma }_0{\left(A-B{K^{\prime }}_t\right)}^T\Vert }\\ ={\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert \left(A-B{K}_t\right){\Sigma }_0{\left(B\Delta \right)}^T+\left(B\Delta \right){\Sigma }_0{\left(A-B{K}_t\right)}^T-\left(B\Delta \right){\Sigma }_0{\left(B\Delta \right)}^T\Vert }\\ \le {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert {\Sigma }_0\Vert \left(2\Vert A-B{K}_t\Vert \Vert B\Vert \Vert K_t-{K^{\prime }}_t\Vert +{\Vert B\Vert }^2{\Vert K_t-{K^{\prime }}_t\Vert }^2\right)}\\ \le \left(2\rho \Vert B\Vert {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert K_t-{K^{\prime }}_t\Vert +{\Vert B\Vert }^2{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}{\Vert K_t-{K^{\prime }}_t\Vert }^2}}\right)\Vert {\Sigma }_0\Vert \end{array}$

同理可得，

$\begin{array}{l}{\displaystyle {\sum }_{t=0}^{T-1}\Vert {\displaystyle {\sum }_{s=0}^t{\displaystyle {\prod }_{u=0}^s\left({\mathcal{F}}_{{K^{\prime }}_t}\circ \cdots \circ {\mathcal{F}}_{{K^{\prime }}_{t-u}}-{\mathcal{F}}_{K_t}\circ \cdots \circ {\mathcal{F}}_{K_{t-u}}\right)\left(W\right)}}\Vert }\\ \le \frac{{\rho }^{2T}-1}{{\rho }^2-1}{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert {\displaystyle \underset{s=0}{\overset{t}{\sum }}\left({\mathcal{F}}_{{K^{\prime }}_t}-{\mathcal{F}}_{K_t}\right)\left(W\right)}\Vert }\end{array}$

综上所述，

$\begin{array}{c}\Vert {\Sigma }_K-{\Sigma }_{K^{\prime }}\Vert \le {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert \left({{\mathcal{G}}^{\prime }}_t-{\mathcal{G}}_t\right)\left({\Sigma }_0\right)\Vert }+\Vert {\displaystyle \underset{s=0}{\overset{t}{\sum }}{\displaystyle \underset{u=0}{\overset{s}{\prod }}\left({\mathcal{F}}_{{K^{\prime }}_t}\circ \cdots \circ {\mathcal{F}}_{{K^{\prime }}_{t-u}}-{\mathcal{F}}_{K_t}\circ \cdots \circ {\mathcal{F}}_{K_{t-u}}\right)\left(W\right)}}\Vert \\ \le \frac{{\rho }^{2T}-1}{{\rho }^2-1}\left({\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert \left({\mathcal{F}}_{{K^{\prime }}_t}-{\mathcal{F}}_{K_t}\right)\left({\Sigma }_0\right)\Vert }+{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert {\displaystyle \underset{s=0}{\overset{t}{\sum }}\left({\mathcal{F}}_{{K^{\prime }}_t}-{\mathcal{F}}_{K_t}\right)\left(W\right)}\Vert }\right)\\ \le \frac{{\rho }^{2T}-1}{{\rho }^2-1}\left({\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert {\mathcal{F}}_{{K^{\prime }}_t}-{\mathcal{F}}_{K_t}\Vert }\right)\left(\Vert {\Sigma }_0\Vert +T\Vert W\Vert \right)\\ \le \frac{{\rho }^{2T}-1}{{\rho }^2-1}\left({\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert {\mathcal{F}}_{{K^{\prime }}_t}-{\mathcal{F}}_{K_t}\Vert }\right)\left(\Vert {\Sigma }_0\Vert +T\Vert W\Vert \right)\\ \le \frac{{\rho }^{2T}-1}{{\rho }^2-1}\left(2\rho \Vert B\Vert {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert \Delta \Vert }+{\Vert B\Vert }^2{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}{\Vert \Delta \Vert }^2}\right)\left(\frac{C\left(K\right)}{{\sigma }_{\min }Q}+T\Vert W\Vert \right)\end{array}$

引理2.6证明：

令 ${\varphi }_t=Q_t+K_t^T{R}_t{K}_t$

$\begin{array}{c}C\left(K^{\prime }\right)-C\left(K\right)=\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t\left[Tr\left({\text{<msup> Σ <mo> ′ </mo> </msup>}}_t\left(Q_t+{\left({K^{\prime }}_t\right)}^T{R}_t{K^{\prime }}_t\right)\right)-Tr\left({\text{Σ}}_t\left(Q_t+K_t^T{R}_t{K}_t\right)\right)\right]\\ =\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t\left[Tr\left({{\mathcal{G}}^{\prime }}_t\left({\text{Σ}}_0\right){{\varphi }^{\prime }}_t-{\mathcal{G}}_t\left({\text{Σ}}_0\right){\varphi }_t\right)+Tr\left(\left({{\varphi }^{\prime }}_t-{\varphi }_t\right)W\right)\right]\\ +\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t\left[Tr\left(\underset{s=0}{\overset{t}{{\displaystyle \sum }}}\underset{u=0}{\overset{s}{{\displaystyle \prod }}}{{\mathcal{F}}^{\prime }}_{K_t}\circ \cdots \circ {{\mathcal{F}}^{\prime }}_{K_{t-u}}\left(W\right){{\varphi }^{\prime }}_t-\underset{s=0}{\overset{t}{{\displaystyle \sum }}}\underset{u=0}{\overset{s}{{\displaystyle \prod }}}{\mathcal{F}}_{K_t}\circ \cdots \circ {\mathcal{F}}_{K_{t-u}}\left(W\right){\varphi }_t\right)\right]\end{array}$

首先看右边第一项，

$\Vert {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}{\gamma }^{t}Tr\left({{\mathcal{G}}^{\prime }}_t\left({\Sigma }_0\right){{\varphi }^{\prime }}_t-{\mathcal{G}}_t\left({\Sigma }_0\right){\varphi }_t\right)}\Vert \le Tr\left({\Sigma }_0\right){\displaystyle \underset{t=0}{\overset{T-1}{\sum }}{\gamma }^t\Vert Tr\left({{\mathcal{G}}^{\prime }}_t\left({{\varphi }^{\prime }}_t\right)-{\mathcal{G}}_t\left({\varphi }_t\right)\right)\Vert }$

根据引理2.3证明中的定义，

第二项，

第三项，

其中，

$\begin{array}{c}\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t\Vert {\left({K^{\prime }}_t\right)}^T{R}_t{K^{\prime }}_t-K_t^T{R}_t{K}_t\Vert =\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t\Vert {\left({K^{\prime }}_t-K_t+K_t\right)}^T{R}_t\left({K^{\prime }}_t-K_t+K_t\right)-K_t^T{R}_t{K}_t\Vert \\ \le \underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t{\Vert K_t-{K^{\prime }}_t\Vert }^2\Vert R_t\Vert +2{\gamma }^t\Vert K_t\Vert \Vert R_t\Vert \Vert K_t-{K^{\prime }}_t\Vert \\ \le \underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}3{\gamma }^t\Vert K_t\Vert \Vert R_t\Vert \Vert K_t-{K^{\prime }}_t\Vert \end{array}$

根据假设 $\Vert K_t-{K^{\prime }}_t\Vert \le \Vert K_t\Vert$ ，倒数第二个不等式成立，综上所述，

$\begin{array}{c}C\left(K^{\prime }\right)-C\left(K\right)\le \left\{\frac{{\rho }^{2T}-1}{{\rho }^2-1}\left[Tr\left({\Sigma }_0\right)\left(2\rho +1\right)\Vert B\Vert \underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}\Vert K_t-{K^{\prime }}_t\Vert +1+Tr\left(W\right)\right]+Tr\left(W\right)\right\}\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}3{\gamma }^t\Vert K_t\Vert \Vert R_t\Vert \Vert K_t-{K^{\prime }}_t\Vert \\ +\frac{\left(T-1\right)\left({\rho }^{4\left(T-1\right)}-1\right)}{{\rho }^4-1}Tr\left(W\right)\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}3{\gamma }^t\Vert K_t\Vert \Vert R_t\Vert \Vert K_t-{K^{\prime }}_t\Vert \\ +\frac{{\rho }^{2T}-1}{{\rho }^2-1}\left(2\rho +1\right)\Vert B\Vert \left(T\Vert W\Vert +\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}\Vert Q_t+K_t^T{R}_t{K}_t\Vert \right)\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t\Vert K_t-{K^{\prime }}_t\Vert \\ \le h_1\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}\Vert K_t-{K^{\prime }}_t\Vert +h_2{\left[\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}\Vert K_t-{K^{\prime }}_t\Vert \right]}^2\\ \le h_C\underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}\Vert K_t-{K^{\prime }}_t\Vert \end{array}$

下面证明梯度项，

$\Vert {\nabla }_{t}C\left(K^{\prime }\right)-{\nabla }_{t}C\left(K\right)\Vert =2\Vert {E^{\prime }}_t{{\Sigma }^{\prime }}_t-E_t{\Sigma }_t\Vert \le 2\Vert {E^{\prime }}_t-E_t\Vert \Vert {{\Sigma }^{\prime }}_t\Vert +2\Vert E_t\Vert \Vert {{\Sigma }^{\prime }}_t-{\Sigma }_t\Vert$

$\Vert {{\Sigma }^{\prime }}_t\Vert \le \Vert {\Sigma }_{K^{\prime }}\Vert \le \Vert {\Sigma }_{K^{\prime }}-{\Sigma }_K\Vert +\Vert {\Sigma }_K\Vert \le \frac{C\left(K\right)}{{\sigma }_{\min }Q}+\Vert {\Sigma }_K\Vert$

$\begin{array}{c}\Vert {E^{\prime }}_t-E_t\Vert =\Vert R_t\left({K^{\prime }}_t-K_t\right)-B^T\left({P^{\prime }}_{t+1}-P_{t+1}\right)A+B^T\left({P^{\prime }}_{t+1}-P_{t+1}\right)B{K^{\prime }}_t+B^T{P}_{t+1}B\left({K^{\prime }}_t-K_t\right)\Vert \\ \le \left(\Vert R_t\Vert +{\Vert B\Vert }^2\Vert P_0\Vert \right)\underset{t=0}{\stackrel{T-1}{\sum }}\Vert K_t-{K^{\prime }}_t\Vert +\Vert B\Vert \Vert {P^{\prime }}_0-P_0\Vert \Vert A\Vert +2{\Vert B\Vert }^2\Vert {P^{\prime }}_0-P_0\Vert \underset{t=0}{\stackrel{T-1}{\sum }}\Vert K_t\Vert \end{array}$

$\begin{array}{c}\Vert {P^{\prime }}_0-P_0\Vert \le 3\Vert K_0\Vert \Vert R_0\Vert \Vert {K^{\prime }}_0-K_0\Vert +\Vert {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}{\gamma }^{t}Tr\left({{\mathcal{G}}^{\prime }}_t\left({\Sigma }_0\right){{\varphi }^{\prime }}_t-{\mathcal{G}}_t\left({\Sigma }_0\right){\varphi }_t\right)}\Vert \\ +\frac{{\rho }^{2T}-1}{{\rho }^2-1}\left[\left(2\rho +1\right)\Vert B\Vert \Vert Q_T\Vert \underset{t=0}{\stackrel{T-1}{\sum }}\Vert K_t-{K^{\prime }}_t\Vert \right]\end{array}$

$\Vert E_t\Vert \le {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert E_t\Vert }\le {\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\sqrt{Tr\left(E_t^T{E}_t\right)}}\le \sqrt{T\cdot \frac{\underset{t}{\max }\Vert R_t+\gamma B^T{P}_{t+1}B\Vert }{{\sigma }_{\min }{\Sigma }_K}\left(C\left(K\right)-C\left(K^{*}\right)\right)}$

$\begin{array}{c}\Vert {{\Sigma }^{\prime }}_t-{\Sigma }_t\Vert \le \Vert \left({{\mathcal{G}}^{\prime }}_t-{\mathcal{G}}_t\right)\left({\Sigma }_0\right)\Vert +\Vert {\displaystyle \underset{s=0}{\overset{t}{\sum }}{\displaystyle \underset{u=0}{\overset{s}{\prod }}\left({\mathcal{F}}_{{K^{\prime }}_t}\circ \cdots \circ {\mathcal{F}}_{{K^{\prime }}_{t-u}}-{\mathcal{F}}_{K_t}\circ \cdots \circ {\mathcal{F}}_{K_{t-u}}\right)\left(W\right)}}\Vert \\ \le \left[{\rho }^{2t}\left(2\rho +1\right)\Vert B\Vert \Vert {\Sigma }_0\Vert +\frac{{\rho }^{2T}-1}{{\rho }^2-1}\left(2\rho +1\right)\Vert B\Vert \Vert W\Vert \right]{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert K_t-{K^{\prime }}_t\Vert }\end{array}$

$\Vert {\nabla }_{t}C\left(K^{\prime }\right)-{\nabla }_{t}C\left(K\right)\Vert \le h_g{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\Vert {K^{\prime }}_t-K_t\Vert }$

引理2.7证明过程

定义

${\tilde{\nabla }}_{t}C\left(K\right)\triangleq \frac{1}{I}{\displaystyle \underset{i=0}{\overset{I-1}{\sum }}\frac{D}{r^2}}\left(C\left(K+U^i\right)U_t^i\right)$

则

${\hat{\nabla }}_{t}C\left(K\right)-{\nabla }_{t}C\left(K\right)={\hat{\nabla }}_{t}C\left(K\right)-{\tilde{\nabla }}_{t}C\left(K\right)+{\tilde{\nabla }}_{t}C\left(K\right)-{\nabla }_{t}C(\; K\; )$

因为 $E_{x_0,\omega }\left[{\hat{\nabla }}_{t}C\left(K\right)\right]={\tilde{\nabla }}_{t}C\left(K\right)$ ，根据霍夫丁不等式，对 $\forall \varsigma >0$ ，

$P\left\{\Vert {\hat{\nabla }}_{t}C\left(K\right)-{\tilde{\nabla }}_{t}C\left(K\right)\Vert \le \varsigma \right\}\ge 1-2\exp \left(-\frac{2I{\varsigma }^2}{L^2}\right)$

因为

$\begin{array}{c}\Vert {\hat{c}}_t^i\Vert \le \underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t\Vert \left({\left(x_t^i\right)}^T{Q}_t{x}_t^i+{\left(u_t^i\right)}^T{R}_t{u}_t^i\right)+{\left(x_T^i\right)}^T{Q}_T{x}_T^i\Vert \\ \le \underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t{\Vert x_t^i\Vert }^2\Vert Q_t+{\left(K_t^i\right)}^T{R}_t{K}_t^i\Vert \\ \le \underset{t}{\max }\Vert Q_t+{\left(K_t^i\right)}^T{R}_t{K}_t^i\Vert \underset{t=0}{\overset{T-1}{{\displaystyle \sum }}}{\gamma }^t\Vert {\text{Σ}}_t^i\Vert \\ \le \underset{t}{\max }\Vert Q_t+{\left(K_t^i\right)}^T{R}_t{K}_t^i\Vert \left(\frac{C\left(K\right)}{{\sigma }_{\min }Q}+\Vert {\text{Σ}}_{K^0}\Vert \right)\triangleq L\end{array}$

所以， ${\Vert {\hat{\nabla }}_{t}C\left(K\right)-{\tilde{\nabla }}_{t}C\left(K\right)\Vert }_F\le \frac{\epsilon }{2}$ 。

又 ${\nabla }_t{C}^r\left(K\right)=\frac{D}{r^2}{E}_{U\text{<mover accent="true"> <mo> ˜ </mo> </mover>}{\mathbb{B}}_r}\left[C\left(K+U_t\right)U_t\right]$ ， ${\tilde{\nabla }}_{t}C\left(K\right)\triangleq \frac{1}{I}{\displaystyle \underset{i=0}{\overset{I-1}{\sum }}\frac{D}{r^2}}\left(C\left(K+U^i\right)U_t^i\right)$

所以， $E\left[{\tilde{\nabla }}_{t}C\left(K\right)\right]={\nabla }_t{C}^r\left(K\right)$ ， ${\Vert {\tilde{\nabla }}_{t}C\left(K\right)-{\nabla }_t{C}^r\left(K\right)\Vert }_F\le \frac{\epsilon }{4}$

${\Vert {\nabla }_t{C}^r\left(K\right)-{\nabla }_{t}C\left(K\right)\Vert }_F\le {\Vert {\nabla }_t{C}^r\left(K\right)-{\nabla }_{t}C\left(K+U_t\right)\Vert }_F+{\Vert {\nabla }_{t}C\left(K+U_t\right)-{\nabla }_{t}C\left(K\right)\Vert }_F$

根据引理2.9，当 $r\le \frac{\epsilon }{4h_g}$ 时， ${\Vert {\nabla }_{t}C\left(K+U_t\right)-{\nabla }_{t}C\left(K\right)\Vert }_F\le h_g{\Vert U_t\Vert }_F\le \frac{\epsilon }{8}$

所以， ${\Vert {\nabla }_t{C}^r\left(K\right)-{\nabla }_{t}C\left(K\right)\Vert }_F\le \frac{\epsilon }{4}$

综上所述， $\Vert {\hat{\nabla }}_{t}C\left(K\right)-{\nabla }_{t}C\left(K\right)\Vert \le \epsilon$ 。根据资格迹与梯度的关系，

${\Vert {\hat{\delta }}_t^n-{\delta }_t^n\Vert }_F={\displaystyle \underset{i=0}{\overset{n}{\sum }}{\lambda }^{n-i}{\Vert {\hat{\nabla }}_{t}C\left(K^n\right)-{\nabla }_{t}C\left(K^n\right)\Vert }_F\le }{\displaystyle \underset{i=0}{\overset{n}{\sum }}{\lambda }^{n-i}\epsilon }$

因为 $\lambda \in \left(0,1\right)$ ，由 $\epsilon$ 的任意性可知结论成立。