【强化学习】#5 时序差分学习

主要参考学习资料：《强化学习（第2版）》[加]Richard S.Suttion [美]Andrew G.Barto 著

文章源文件：https://github.com/INKEM/Knowledge_Base

缩写说明

• DP：动态规划
• GPI：广义策略迭代
• MC：蒙特卡洛
• MDP：马尔可夫决策决策过程
• TD：时序差分

概述

• 时序差分是一种在状态的下一个时刻就能更新其价估计的无模型算法。
• Sarsa是同轨策略下的时序差分控制方法。
• Q学习是离轨策略下的时序差分控制方法。
• 期望Sarsa综合并推广了Sarsa和Q学习，具有更优的表现。
• 双学习思想用于解决最大化操作导致的最大化偏差问题。

时序差分（TD）学习结合了蒙特卡洛方法和动态规划方法的思想。与蒙特卡洛方法一致，时序差分方法可以直接从与环境互动的经验中学习策略，而不需要构件关于环境动态特性的模型；与动态规划一致，时序差分方法无需等待交互的最终结果，而可以基于已得到的其他状态的估计值来更新当前状态的价值函数。

时序差分预测

我们先回顾一下，蒙特卡洛方法需要一直等到计算出一次访问后的回报之后（也就是到达该次访问所在幕的终点），再用这个回报作为$V(S_t)$的目标进行估计。一个适用于非平稳环境（参见多臂赌博机一章）的简单的每次访问型蒙特卡洛方法可以表示成

$$V(S_t)\leftarrow V(S_t)+\alpha [G_t-V(S_t)]$$

其中$\alpha$是常量步长参数，该方法称为常量αMC。蒙特卡洛方法的估计是无偏的，因为

$$v_{\pi }(s)\dot{=}{\mathbb{E}}_{\pi }[G_t|S_t=s]$$

而TD方法只需要等到一次访问的下一个时刻，就能用观察到的收益$R_{t+1}$和已有的估计值$V(S_{t+1})$来进行一次更新

$$V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$$

这种方法被称为TD(0)或单步TD，它是在多步TD方法TD(λ)（将在后续章节讨论）的一个特例。TD方法的估计是有偏的，尽管

$$\begin{array}{rl}{v}_{\pi }(s)& \dot{=}{\mathbb{E}}_{\pi }[G_t|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s]\end{array}$$

而在估计中我们用于替代$v_{\pi }(S_{t+1})$的$V(S_{t+1})$本身也是一个估计，因此存在偏差，但随着样本量的增加，TD方法会趋于无偏。

以下是使用TD(0)进行策略估计的算法伪代码：

在常量αMC和TD(0)中，我们都可以把$\alpha$后的括号部分视为一种现有估计值与估计目标的误差，即蒙特卡洛误差为$G_t-V(S_t)$，而TD误差为

$${\delta }_t\dot{=}{R}_{t+1}+\gamma V(S_{t+1})-V(S_t)$$

如果状态价值函数估计$V$在遍历一幕的过程中不会更新（即蒙特卡洛方法采用的过程），则蒙特卡洛误差可以写为TD误差之和

$$\begin{array}{rl}{G}_t-V(S_t)& =R_{t+1}+\gamma G_{t+1}-V(S_t)+\gamma V(S_{t+1})-\gamma V(S_{t+1})\\ & ={\delta }_t+\gamma (G_{t+1}-V(S_{t+1}))\\ & ={\delta }_t+\gamma {\delta }_{t+1}+{\gamma }^2{\delta }_{t+2}+\cdots +{\gamma }^{T-t-1}{\delta }_{T-1}+{\gamma }^{T-t}(G_T-V(S_T))\\ & ={\delta }_t+\gamma {\delta }_{t+1}+{\gamma }^2{\delta }_{t+2}+\cdots +{\gamma }^{T-t-1}{\delta }_{T-1}+{\gamma }^{T-t}(0-0)\\ & =\sum _{k=t}^{T-1}{\gamma }^{k-t}{\delta }_k\end{array}$$

而在TD(0)中，$V$在一次遍历中会不断更新，使这个等式并不准确。但在时间步长较小的情况下，该等式仍能近似成立，这种泛化在TD学习的理论和算法中很重要。

时序差分预测方法具有如下优势：

• 相比DP方法，TD方法不需要一个描述收益和下一状态联合概率分布的模型。
• 相比MC方法，TD方法的更新只需等到下一个时刻即可，这对于持续性任务和幕非常长的分幕式任务是很实用的。

同时，对于任何固定的策略$\pi$，TD(0)都已被证明能够收敛到$v_{\pi }$。但是关于TD和MC哪种方法收敛得更快、数据利用更有效，这些仍未被严格证明。不过在实践中，TD方法在随机任务上通常比常量αMC方法收敛得更快。

Sarsa

现在，我们使用时序差分方法来解决控制问题。GPI模式下的时序差分方法仍然可以分为同轨策略和离轨策略，本节介绍一种同轨策略下的时序差分控制方法。

如蒙特卡洛方法一节中所讲，在没有环境模型的情况下，估计动作价值函数比估计状态价值函数更有效。我们只需将状态的价值替换为“状态-动作”二元组的价值就能得到对应的更新方法

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]$$

每当从非终止状态的$S_t$进行一次状态转移之后，我们就进行一次更新。如果$S_{t+1}$为终止状态，则定义$Q(S_t,A_t)=0$。上述更新规则利用了五元组$(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$的元素，因此被命名为Sarsa。

同样地，为了保证试探性，我们可以用$ϵ$-软性策略和$ϵ$-贪心策略来进行策略改进，或者其他保证所有“状态-动作”二元组都能被访问到的方式，来使其最终收敛到最优策略。Sarsa算法的伪代码如下：

Q学习

Q学习是一种离轨策略下的时序差分控制，它直接以对最优动作价值函数$q_{\ast }$的估计为目标

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma \underset{a}{\max }Q(S_{t+1},a)-Q(S_t,A_t)]$$

当该更新公式收敛时，有

$$Q(S_t,A_t)=R_{t+1}+\gamma \underset{a}{\max }Q(S_{t+1},a)$$

而这正是贝尔曼最优方程的动作价值函数表示形式。因此Q学习可以视为无环境模型的价值迭代（参见动态规划一章），只是Q学习的价值函数需要通过行动策略与环境交互采样获得，而不是直接由环境动态特性计算得出。

需要注意的是，同轨策略和离轨策略仅仅针对需要采取策略与环境交互的方法，价值迭代既不是同轨策略也不是离轨策略。

Q学习的伪代码如下：

但是在一些高风险环境、要求策略包含一定随机性（例如非平稳问题）的情况下，Q学习可能表现得不如Sarsa。考虑一个带悬崖的网格世界问题，贴着悬崖走能以最短路径到达终点，但也靠近危险，远离悬崖需要绕路，但更安全。在走到悬崖边的一个格子时，对Q学习来说，它会通过贪心直接选择出下一个贴着悬崖的格子，因而能很快收敛到最短但靠近危险路径；对Sarsa学习来说，它的软性策略还会随机采样下一个动作，这使得其有一定几率掉下悬崖受到惩罚，因而会逐渐收敛到一个绕路但安全的路径。此时如果分别基于Q学习和Sarsa收敛的价值估计采用同样的$ϵ$-贪心策略，则Sarsa会因为不易掉下悬崖而表现得更好。

期望Sarsa

期望Sarsa是一种介于Sarsa和Q学习之间的算法，它采用如下更新公式

$$\begin{array}{rl}Q(S_t,A_t)& \leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma \mathbb{E}[Q(S_{t+1},A_{t+1})|S_{t+1}]-Q(S_t,A_t)]\\ & \leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma \sum _a\pi (a|S_{t+1})Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]\end{array}$$

在Sarsa的基础上，期望Sarsa通过期望消除了使用随机选择的$A_{t+1}$更新$Q(S_t,A_t)$带来的方差，在相同数量的经验下，它表现得比Sarsa更好。而相较于Q学习，它又不那么激进，会更综合地考虑下一个状态的价值，更加适用于高风险环境。

期望Sarsa既可以是同轨策略也可以是离轨策略，这取决于其用于采样估计$Q$的策略${\pi }^{\prime }$是否不同于用于计算期望的策略$\pi$。在离轨策略下，如果$\pi$是贪心策略，则期望Sarsa就是Q学习，因此其可以视为Q学习的推广。

最大化偏差与双学习

由于最优策略的贪心性质，我们目前讨论的所有控制算法在构建目标策略时都包含了最大化操作。但考虑一种情况，在状态$s$下，所有动作的真实价值$q(s,a)$全为零，但它们的估计值$Q(s,a)$是不确定的，可能有些大于零，有些小于零。此时我们如果对估计值采用最大化操作，反而产生了最大的正偏差，我们将其称为最大化偏差。

避免最大化偏差的一个方法是双学习。既然估计值$Q$可能高估也可能低估，那么如果采用两组独立更新的估计$Q_1$和$Q_2$，从期望上来看，二者的误差会相互抵消。

双学习的关键在于解耦了选择和评估动作的过程，在更新$Q_1$时，我们仍基于$Q_1$选择贪心动作，但是不会使用$Q_1$作为其更新基准，而是让$Q_2$重新给出对这一动作的评估。这相当于在复习时，自己抽查自己往往检验不出薄弱的地方，而两个人相互抽查则更容易发现对方的漏洞。

双学习的思想可以推广到为完备MDP设计的算法中，在Q学习中的推广则被称为双Q学习。双Q学习在每次状态转移随机对$Q_1$或$Q_2$进行更新，其中$Q_1$的更新公式如下

$$Q_1(S_t,A_t)\leftarrow Q_1(S_t,A_t)+\alpha [R_{t+1}+\gamma Q_2(S_{t+1},\underset{a}{\mathrm{argmax}}{Q}_1(S_{t+1},a))-Q_1(S_t,A_t)]$$

$Q_2$的更新只需将上式二者的地位互换即可。

双$Q$学习的伪代码如下：