Note 12 数值时序差分学习 Numerical TD Learning

正如前两章所讨论的，TD学习是一种理论上很合理的基于抽样的算法机制，以解决模型的诅咒问题。在LFA设置下，DP的一个常见做法是采用策略迭代的框架来获得一个最优策略。也就是说，采用LFA的TD算法评估给定策略的总成本，然后采取策略改进步骤，完成基于抽样的PI框架的一次扫描。

12.1 Off-policy学习简述

基于抽样的PI算法与LFA的一个明显风险是，它可能根本无法收敛，或者无法迅速收敛到有用的范围。因此，RL的一个实际需求是通过遵循一个给定的策略来利用采样交互，以评估一个新策略的总成本，这可能无法被评估。这样的任务被称为Off-policy性学习。更具体地说，给定一个$\mathrm{MDP}(\mathcal{X},\mathcal{U},g,p,\gamma )$和一个所谓的行为策略${\pi }_b$，Off-policy学习的任务是评估另一个策略${\pi }_t$的总成本，被称为目标策略。作为off-policy学习的对应，所谓on-policy学习是指估计策略的总成本函数，生成样本的RL算法。

[强化学习（四） - 蒙特卡洛方法（Monte Carlo Methods）及实例]
…确保所有动作被无限频繁地选择的唯一一般方法是让智能体继续选择它们。有两种方法可以确保这一点，由此产生了我们所说的 on-policy(有些文章翻译成"同策") 方法和 off-policy(“异策”) 方法,在之后还是使用其原来的英语名称,即"on-policy"与"off-policy"。on-policy方法试图评估或改进用于决策的策略，而off-policy方法评估或改进与用于生成数据策略的不同…
…On-policy 的目标策略和行为策略是同一个策略，其好处就是简单粗暴，直接利用数据就可以优化其策略，但这样的处理会导致策略其实是在学习一个局部最优，因为On-policy的策略没办法很好的同时保持即探索又利用；而Off-policy将目标策略${\pi }_t$和行为策略${\pi }_b$分开，可以在保持探索的同时，更能求到全局最优值…

让我们回顾一下公式（3.4）中策略的总成本函数的定义。很明显，off-policy 学习可以被认为是一个分布不匹配的问题。也就是说，需要从目标策略${\pi }_t$的分布中采样相关的交互，并且从行为策略${\pi }_b$的分布中提取可用的轨迹。重要性抽样（importance sampling） 是处理分布不匹配的常规手段。让我们考虑通过从另一个分布${\mu }^{\prime }$中抽取的样本来估计按照$\mu$分布的随机变量$x$的期望值的任务。如果${\mu }^{\prime }(x)>0$对于所有$x$，很容易看出

$$\begin{array}{rl}\underset{x\sim \mu }{E}[x]& ={\int }_{\mathcal{X}}x\mu (x)dx\\ & ={\int }_{\mathcal{X}}x\frac{\mu (x)}{{\mu }^{\prime }(x)}{\mu }^{\prime }(x)dx\\ & =\underset{x\sim {\mu }^{\prime }}{E}\left[\frac{\mu (x)}{{\mu }^{\prime }(x)}x\right]\end{array}\text{\hspace{1em}(12.1)}$$

让我们把两个密度函数的比值表示为

$$\psi (x)=\frac{\mu (x)}{{\mu }^{\prime }(x)}\text{\hspace{1em}(12.2)}$$
对随机变量$x$的期望值可以用经验平均数近似为
$$\underset{x\sim \mu }{E}[x]\approx \frac{1}{N}\sum _{i=1}^N\psi \left(x_i\right)x_i\text{\hspace{1em}(12.3)}$$

显然，对于一个具有目标策略${\pi }_t$和行为策略${\pi }_b$的特定MDP，采用重要性抽样要求行为策略${\pi }_b$具有与目标策略相同的行动覆盖率。稍微滥用一下符号，如果我们将策略视为条件分布${\pi }_t(u\mid x)$ 与${\pi }_b(u\mid x)$，我们表示
$$\psi (x,u)=\frac{{\pi }_t(u\mid x)}{{\pi }_b(u\mid x)}\text{\hspace{1em}(12.4)}$$

然后，我们可以使用重要性抽样对目标策略的总成本函数进行近似，如下所示

$$\begin{array}{rl}{J}^{{\pi }_t}(x)& ={\mathbb{E}}_{p_{{\pi }_b}\left(x^{\prime }\mid x\right)}\left[\psi (x,u)\left(g\left(x,{\pi }_b(x),x^{\prime }\right)+\gamma J^{{\pi }_b}\left(x^{\prime }\right)\right)\right]\\ & \approx \frac{1}{N}\sum _{i=1}^N\psi (x,u)\left(g\left(x,{\pi }_b(x),x^{\prime }\right)+\gamma J^{{\pi }_b}\left(x^{\prime }\right)\right)\end{array}\text{\hspace{1em}(12.5)}$$

通过遵循TD学习的相同的推导方法，一个off-policy 的TD$(0)$算法被赋予以下更新规则

$$J_{k+1}(x)=J_k(x)+{\alpha }_k\psi (x,u)\left(g\left(x,u,x^{\prime }\right)+\gamma J_k\left(x^{\prime }\right)-J_k(x)\right)\text{\hspace{1em}(12.6)}$$

尽管off-policy TD的发展遵循与原始TD算法完全相同的理念，但据观察，off-policy TD的实际用途相当有限。特别是，off-policy 的TD算法经常不能收敛。这种现象通常被称为致命的三要素，即函数逼近（function approximation）、自举（bootstrapping）和off-policy 学习。

一个真正的随机梯度下降算法最小化off-policy MSPBE是打破致命三部曲的第一次成功尝试。对于一个给定的具有目标策略${\pi }_t$和行为策略${\pi }_b$的遍历MDP，我们用${\xi }_t$和${\xi }_b$分别表示${\pi }_t$和${\pi }_b$的稳定状态分布。那么，off-policy MSPBE函数定义为

$$f_t(h)={\Vert {\Pi }_{{\pi }_t}{\mathrm{T}}_{{\pi }_t}{\Phi }^{\top }h-{\Phi }^{\top }h\Vert }_{{\xi }_t}^2,\text{\hspace{1em}(12.7)}$$

其中${\Xi }_t={\Xi }_b\Psi$，$\Psi =\mathrm{diag}\left(\psi \left(x_1\right),\dots ,\psi \left(x_K\right)\right)$，正交投影仪${\Pi }_{{\pi }_t}$可以表示如下

$$\begin{array}{rl}{\Pi }_{{\pi }_t}& ={\Phi }^{\top }{\left(\Phi {\Xi }_t{\Phi }^{\top }\right)}^{-1}\Phi {\Xi }_t\\ & ={\Phi }^{\top }{\left(\Phi {\Xi }_b\Psi {\Phi }^{\top }\right)}^{-1}\Phi {\Xi }_b\Psi \end{array}\text{\hspace{1em}(12.8)}$$

为了简单起见，我们推导出最小化原始策略上MSPBE函数的GTD算法。

12.2 Gradient TD Learning

定义$\delta (h):={\mathrm{T}}_{\pi }{\Phi }^{\top }h-{\Phi }^{\top }h$。 然后我们可以将 on-policy MSPBE函数改写如下
$$\begin{array}{rl}{\Vert {\Pi }_{\pi }{\mathrm{T}}_{\pi }{\Phi }^{\top }h-{\Phi }^{\top }h\Vert }_{\xi }& =(\delta (h){)}^{\top }{\Pi }_{\pi }\Xi {\Pi }_{\pi }\delta (h)\\ & =(\delta (h){)}^{\top }\Xi {\Phi }^{\top }{\left(\Phi \Xi {\Phi }^{\top }\right)}^{-1}\Phi \Xi \delta (h)\end{array}\text{\hspace{1em}(12.9)}$$

MSPBE函数的欧几里得梯度为
$$\begin{array}{rl}{\nabla }_{f_t}(h)& ={\left({\nabla }_{\delta }(h)\right)}^{\top }\Xi {\Phi }^{\top }{\left(\Phi \Xi {\Phi }^{\top }\right)}^{-1}\Phi \Xi \delta (h)\\ & ={\left(\gamma P_{\pi }{\Phi }^{\top }-{\Phi }^{\top }\right)}^{\top }\Xi {\Phi }^{\top }{\left(\Phi \Xi {\Phi }^{\top }\right)}^{-1}\Phi \Xi \delta (h)\\ & =\gamma \Phi P_{\pi }^{\top }\Xi {\Phi }^{\top }{\left(\Phi \Xi {\Phi }^{\top }\right)}^{-1}\Phi \Xi \delta (h)-\Phi \Xi \delta (h)\end{array}\text{\hspace{1em}(12.10)}$$

由于MSPBE函数是强凸的，因此只有一个全局最小值，它满足临界点条件，即${\nabla }_{f_t}(h)=0$。 等价地，全局最小值被描述为以下方程在$h$中的唯一解
$${\left(\gamma \Phi P_{\pi }^{\top }\Xi {\Phi }^{\top }\right)}^{-1}\Phi \Xi \delta (h)={\left(\Phi \Xi {\Phi }^{\top }\right)}^{-1}\Phi \Xi \delta (h)\text{\hspace{1em}(12.11)}$$

显然，由于要计算$\Phi P_{\pi }^{\top }\Xi {\Phi }^{\top }$ 与$\Phi \Xi {\Phi }^{\top }$的倒数，随机逼近的经典技巧在此失效。为了缓解这一困难，我们引入一个辅助变量$\omega$作为
$$\omega :={\left(\gamma \Phi P_{\pi }^{\top }\Xi {\Phi }^{\top }\right)}^{-1}\Phi \Xi \delta (h)\text{\hspace{1em}(12.12)}$$

直接的有
$$\Phi \Xi \delta (h)=\gamma \Phi P_{\pi }^{\top }\Xi {\Phi }^{\top }\omega =\Phi \Xi {\Phi }^{\top }\omega .\text{\hspace{1em}(12.13)}$$

然后我们可以构建一个方程组为
$$\{\begin{array}{lll}\Phi \Xi \delta (h)-\gamma \Phi P_{\pi }^{\top }\Xi {\Phi }^{\top }\omega & =& 0\\ \Phi \Xi \delta (h)-\Phi \Xi {\Phi }^{\top }\omega & =& 0\end{array}\text{\hspace{1em}(12.14)}$$

我们将TD误差定义为
$${\delta }_h\left(x_k,u_k,x_k^{\prime }\right):=g\left(x_k,u_k,x_k^{\prime }\right)+\gamma h^{\top }\varphi \left(x_k^{\prime }\right)-h^{\top }\varphi \left(x_k\right)\text{\hspace{1em}(12.15)}$$

然后，我们可以构建一个SA算法，即
$$\{\begin{array}{l}{h}_{k+1}=h_k+{\alpha }_k\left({\delta }_h\left(x_k,u_k,x_k^{\prime }\right)\varphi \left(x_k\right)-{\omega }_k^{\top }\varphi \left(x_k\right)\varphi \left(x_k^{\prime }\right)\right)\\ {\omega }_{k+1}={\omega }_k+{\alpha }_k\left({\delta }_h\left(x_k,u_k,x_k^{\prime }\right)-{\omega }_k^{\top }\varphi \left(x_k\right)\right)\varphi \left(x_k\right)\end{array}\text{\hspace{1em}(12.16)}$$

注意，这种SA算法与TDC算法相吻合。

Theorem 12.1 带有LFA的$\mathrm{GTD}(0)$的收敛性 (Convergence of $\mathrm{GTD}(0)$ with LFA).

让步长${\alpha }_k$满足RobbinsMonro条件。那么，由带LFA的GTD(0)倾斜算法产生的向量$h_k$以1的概率收敛于投影贝尔曼算子的固定点。

Remark 12.1 实际收敛上的的困难 (Difficulty in practical convergence)

尽管渐进收敛定理在RL的理论分析中占主导地位，但随机逼近存在一个很大的问题。也就是说，收敛特性取决于权重序列的构造，而渐进收敛只在理论上达到无限大。在下一小节中，我们将讨论一种替代的数值方法，它可以同样好地解决PE问题。先进的数值方法，例如随机的Nesterov加速梯度算法已经得到发展。

12.3 Least Squares TD Learning

正如上一节所讨论的，TD或GTD学习算法的一个最具挑战性的技术问题是它们从SA方法继承的脆弱的渐进收敛性。让我们仔细看看LFA的PE问题，如图18所示。

图18：用LFA进行策略评估的几何学。

我们没有采用数值优化方法来寻找投影贝尔曼算子${\Pi }_{\pi }{T}_{\pi }$的固定点 ${\Phi }^{\top }{h}^{\ast }$ ，而是直接对固定点进行了定性。

如图18所示，残差向量${\mathrm{T}}_{pi}{\Phi }^{\top }{h}^{\ast }-{\Phi }^{\top }{h}^{\ast }$相对于内积$⟨\cdot ,\cdot {⟩}_{\xi }$，正交于近似空间$\mathcal{J}$。 换言之，我们有

$$\Phi \Xi \left({\mathrm{T}}_{\pi }{\Phi }^{\top }{h}^{\ast }-{\Phi }^{\top }{h}^{\ast }\right)=0\text{\hspace{1em}(12.17)}$$

并应用贝尔曼算子${\mathrm{T}}_{\pi }{\Phi }^{\top }h:=G_{\pi }+\gamma P_{\pi }{\Phi }^{\top }h$的紧凑表达，我们最终得出

$$\Phi \Xi \left(I_K-\gamma P_{\pi }\right){\Phi }^{\top }{h}^{\ast }=\Phi \Xi G_{\pi }.\text{\hspace{1em}(12.18)}$$

简单地说，现在的任务是解决上述$h$的线性方程组，即，$Ah=b$，有
$$\{\begin{array}{rl}A& =\Phi \Xi \left(I_K-\gamma P_{\pi }\right){\Phi }^{\top }\\ b& =\Phi \Xi G_{\pi }.\end{array}\text{\hspace{1em}(12.19)}$$

根据$\mathrm{rk}(\Phi )=m$的假设，很容易看到线性系统有一个唯一的解决方案，即：
$$h^{\ast }={\left(\Phi \Xi \left(I_K-\gamma P_{\pi }\right){\Phi }^{\top }\right)}^{-1}\Phi \Xi G_{\pi }.\text{\hspace{1em}(12.20)}$$

为了实现无模型的在线学习，我们采用期望形式为

$$\{\begin{array}{rl}A& ={\mathbb{E}}_{p_{\pi }\left(x^{\prime }\mid x\right)}\left[\varphi (x){\left(\varphi (x)-\gamma \varphi \left(x^{\prime }\right)\right)}^{\top }\right]\\ b& ={\mathbb{E}}_{p_{\pi }\left(x^{\prime }\mid x\right)}\left[g\left(x,u,x^{\prime }\right)\varphi (x)\right]\end{array}\text{\hspace{1em}(12.21)}$$

通过探索上述两个项的经验平均值，公式（12.20）中给出的$h^{\ast }$的解决方案的基于抽样的实现可以写为
$$h_{k+1}={\left(\sum _{i=1}^k\varphi \left(x_i\right){\left(\varphi \left(x_i\right)-\gamma \varphi \left(x_i^{\prime }\right)\right)}^{\top }\right)}^{-1}\left(\sum _{i=1}^{k}g\left(x_i,u_i,x_i^{\prime }\right)\varphi \left(x_i\right)\right)\text{\hspace{1em}(12.22)}$$

这种更新方案被称为最小二乘时间差（Least Squares Temporal Difference， LSTD）学习。很明显，LSTD算法的瓶颈是不断计算平方矩阵。为了减轻这一计算负担，我们可以使用Sherman-Morrison公式来计算矩阵的逆值，并进行秩1更新（rank-one update)。

Proposition 12.1 Sherman-Morrison公式

设$A$是一个可倒置的正方形矩阵，$u，v$是列向量。假设$1+v^{\top }{A}^{-1}u\ne 0$。那么秩1更新 $A+u{v}^{\top }$的逆如下所示
$${\left(A+u{v}^{\top }\right)}^{-1}=A^{-1}-\frac{A^{-1}u{v}^{\top }{A}^{-1}}{1+v^{\top }{A}^{-1}u}\text{\hspace{1em}(12.23)}$$

很明显，LSTD算法不是一种SA算法，而是一种纯粹的蒙特卡洛算法。由于计算$A$和$b$时的算术平均数被抵消了，公式（12.22）中的LSTD更新不需要调整任何超参数或学习率。尽管如此，LSTD算法的性能更多地受到第8.2节中讨论的LFA空间属性的影响。