强化学习：时序差分法【Temporal Difference Methods】

强化学习笔记

主要基于b站西湖大学赵世钰老师的【强化学习的数学原理】课程，个人觉得赵老师的课件深入浅出，很适合入门.

第一章 强化学习基本概念
第二章 贝尔曼方程
第三章 贝尔曼最优方程
第四章 值迭代和策略迭代
第五章 强化学习实例分析:GridWorld
第六章 蒙特卡洛方法
第七章 Robbins-Monro算法
第八章 多臂老虎机
第九章 强化学习实例分析:CartPole

---

---

在强化学习实例分析:CartPole中，我们通过实验发现了蒙特卡洛方法的一些缺点：

1. 每次更新需要等到一个episode结束；
2. 越到后面的episode，耗时越长，效率低.

本节介绍强化学习中经典的时序差分方法（Temporal Difference Methods，TD）。与蒙特卡洛(MC)学习类似，TD学习也是Model-free的，但由于其增量形式在效率上相较于MC方法具有一定的优势。

一、on-policy vs off-policy

在介绍时序差分算法之前，首先介绍一下on-policy 和 off-policy的概念：

• On-policy：我们把用于产生采样样本的策略称为behavior-policy，在policy-improvement步骤进行改进的策略称为target-policy.如果这两个策略相同，我们称之为On-policy算法。
• Off-policy：如果behavior-policy和target-policy不同，我们称之为Off-policy算法。

比如在Monte-Carlo算法中，我可以用一个给定策略${\pi }_a$来产生样本，这个策略可以是$ϵ$-greedy策略，以保证能够访问所有的$s$和$a$。而我们目标策略可以是greedy策略${\pi }_b$，在policy-imporvement阶段我们不断改进${\pi }_b$，最终得到一个最优的策略。这样我们最后得到的最优策略${\pi }_b^{\ast }$就是一个贪婪策略，不用去探索不是最优的动作，这样我们用${\pi }_b^{\ast }$可以得到更高的回报。

二、TD learning of state values

1 迭代格式

和蒙特卡洛方法一样，用TD learning来估计状态值$v(s)$，我们也需要采样的数据，假设给定策略$\pi$，某个episode采样得到的序列如下：
$$(s_0,r_1,s_1,...,s_t,r_{t+1},s_{t+1},...)$$
那么TD learning给出在第$t$步状态值$v(s)$的更新如下：
$$v(s_t)=v(s_t)+{\alpha }_t(s_t)[r_{t+1}+\gamma v(s_{t+1})-v(s_t)](1)$$
Note:

1. $s_t$是当前状态，$s_{t+1}$是跳转到的下一个状态，这里需要用到$v(s_{t+1})$(本身也是一个估计值)；
2. 我们可以看到，TD方法在每个时间步都会进行更新，不需要得到整个episode结束才更新;
3. 这个算法被称为TD(0)。

当$a_t(s_t)$取常量$\alpha$时，下面给出$v_{\pi }(s)$估计的伪代码：

2 推导

TD(0)的迭代格式为什么是这样的呢？和前面介绍随机近似中的RM算法似乎有点像，事实上它可以看作是求解Bellman方程的一种特殊的随机近似算法。我们回顾贝尔曼方程中介绍的：
$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[G_t|S_t=s]\\ & =\mathbb{E}[R_t+\gamma G_{t+1}|S_t=s]\\ & =\mathbb{E}[R_t+\gamma v_{\pi }(S_{t+1})|S_t=s]\end{array}(2)$$
下面我们用Robbins-Monro算法来求解方程（2）,对于状态$s_t, $，我们定义一个函数为
$$g(v_{\pi }(s_t))\doteq v_{\pi }(s_t)-\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t].$$
那么方程（2）等价于
$$g(v_{\pi }(s_t))=0.$$
显然我们可以用RM算法来求解上述方程的根，就能得到$v_{\pi }(s_t)$。因为我们可以通过采样获得$r_{t+1}$和$s_{t+1}$，它们是$R_{t+1}$和$S_{t+1}$的样本，我们可以获得的$g( v_\pi ( s_{t}) ) $的噪声观测是
$$\begin{array}{rl}\tilde{g}(v_{\pi }(s_t))& =v_{\pi }(s_t)-\left[\begin{array}{c}{r}_{t+1}+\gamma v_{\pi }(s_{t+1})\end{array}\right]\\ & =\underset{g(v_{\pi }(s_t))}{\underbrace{\left(v_{\pi }(s_t)-\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]\right)}}\\ & +\underset{\eta }{\underbrace{\left(\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]-[r_{t+1}+\gamma v_{\pi }(s_{t+1})]\right)}}.\end{array}$$
因此，求解$g(v_{\pi }(s_t))=0$的RM算法为
$$\begin{array}{rl}{v}_{t+1}(s_t)& =v_t(s_t)-{\alpha }_t(s_t)\tilde{g}(v_t(s_t))\\ & =v_t(s_t)-{\alpha }_t(s_t)(v_t(s_t)-[r_{t+1}+\gamma v_{\pi }(s_{t+1})\left]\right),\end{array}(3)$$
其中$v_t(s_t)$是$v_{\pi }(s_t)$在$t, $时间点的估计，$\alpha _t( s_t) $是学习率。

Note:

1. (3)中的算法与(1)中的TD(0)具有相似的表达式，唯一的区别是(3)的右侧包含$v_{\pi }(s_{t+1})$，而(1)包含$v_t(s_{t+1})$，这是因为(3)的设计是通过假设其他状态值已知来估计$s_t$的动作值。
2. 如果我们想估计所有状态的状态值，则右侧的$v_{\pi }(s_{t+1})$应替换为$v_t(s_{t+1})$，那么(3)与(1)完全相同。并且我们可以证明这样的替换能保证所有$v_t(s)$都收敛到$v_{\pi }(s)$，这里就不再展开。

3 分析

我们再来看一下TD(0)的迭代格式：
$$\underset{\text{new estimate}}{\underbrace{v_{t+1}(s_t)}}=\underset{\text{current estimate}}{\underbrace{v_t(s_t)}}-{\alpha }_t(s_t)\left[\stackrel{\text{TD error }{\delta }_t}{\overbrace{v_t(s_t)-\left(\underset{\text{TD target }{\bar{v}}_t}{\underbrace{r_{t+1}+\gamma v_t(s_{t+1})}}\right)}}\right],(4)$$
其中
$${\bar{v}}_t\doteq r_{t+1}+\gamma v_t(s_{t+1})(5)$$
被称为TD target，
$${\delta }_t\doteq v(s_t)-{\bar{v}}_t=v_t(s_t)-(r_{t+1}+\gamma v_t(s_{t+1}))(6)$$
被称为TD-error.

为什么（5）被称为TD target，因为迭代格式（4）是让$v_{t+1}$朝着${\bar{v}}_t$更新的，我们考察：
$$\begin{array}{rl}|v_{t+1}(s_t)-{\bar{v}}_t|& =|\left[\begin{array}{c}{v}_t(s_t)-{\bar{v}}_t\end{array}\right]-{\alpha }_t(s_t)[v_t(s_t)-{\bar{v}}_t]|\\ & =|[1-{\alpha }_t(s_t)]||[v_t(s_t)-{\bar{v}}_t]|\\ & \le |[v_t(s_t)-{\bar{v}}_t]|\end{array}$$
显然当$0<{\alpha }_t(s_t)<2$时，上式的不等式成立，这意味着$v_{t+1}$比$v_t$离${\bar{v}}_t$更近，所以${\bar{v}}_t$被称为TD target。

TD-error则衡量了在$t$时间步估计值$v_t$与${\bar{v}}_t$ 的差异，显然我们可以想象当$v_t$估计值是准确的$v_{\pi }$时，TD-error的期望值应该为0，事实上确实如此：
$$\begin{array}{rl}\mathbb{E}[{\delta }_t|S_t=s_t]& =\mathbb{E}[v_{\pi }(S_t)-(R_{t+1}+\gamma v_{\pi }(S_{t+1}))|S_t=s_t]\\ & =v_{\pi }(s_t)-\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]\\ & =v_{\pi }(s_t)-v_{\pi }(s_t)\\ & =0.\end{array}$$
当TD-error趋于0时， 那么(1)也得到不到什么新的信息了，迭代也就收敛了。

4 TD(0)与蒙特卡洛方法的对比

TD learning	Monte Carlo Methods
TD learning每得到一个样本就能更新$v(s)$或者$q(s,a)$，这种算法被称为online的.	MC每次更新必须等到一个epsisode结束，这种算法被称为offline的.
TD可以处理连续性任务和episodic任务.	MC只能处理episodic任务.
TD被称为bootstraping方法，因为$v(s)$/$q(s,a)$动作的更新依赖于其他状态值先前的估计值.因此，TD需要给定一个初始值.	MC是Non-Bootstraping的.

三、Sarsa

如果我们要得到最优策略，无论是用策略迭代还是值迭代算法，我们都需要$q(s,a)$，所以我们可以用TD learning直接来估计$q(s,a)$，给定策略$\pi$，假设某个episode采样得到如下序列：
$$(s_0,a_0,r_1,s_1,a_1,...,s_t,a_t,r_{t+1},s_{t+1},a_{t+1},...).$$
那么TD learning对$q(s,a)$的估计如下：
$$q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-(r_{t+1}+\gamma q_t(s_{t+1},a_{t+1}))],(7)$$
Note:

1. 和对状态值的估计（1）对比，我们发现（7）就是把（1）中的$v(s)$替换为$q(s,a)$，其实就是用RM算法求解关于$q(s,a)$的贝尔曼方程，所以得到的迭代格式类似.
2. 其中$s_{t+1}$为转移的下一个状态，$a_{t+1}$是在状态$s_{t+1}$下采取的动作，这里是根据策略$\pi$得到.（因为我们采样的序列就是根据$\pi$得到的）
3. 所以如果$s_{t+1}$是终止状态，显然就没有$a_{t+1}$，此时我们定义$q(s_{t+1},a_{t+1})=0$.
4. 这个算法每次更新会用到$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$(SARSA)，所以这个算法被称为SARSA.
5. 当我们有$q(s,a)$的估计值后，我们可以使用greedy或者$\epsilon$-greedy来更新策略。可以证明如果步长$a_t(s_t,a_t)$满足RM算法收敛的条件要求，只要所有的状态-动作对被访问无限次，Sarsa以概率1收敛到最优的策略${\pi }^{\ast }$和最优的动作-价值函数$q^{\ast }(s,a)$.

同TD(0)类似，Sarsa可以看作是用RM算法求解如下贝尔曼方程得到的迭代格式：
$$q_{\pi }(s,a)=\mathbb{E}\left[R+\gamma q_{\pi }(S^{\prime },A^{\prime })|s,a\right],\text{for all }(s,a).$$

下面给出Sarsa完整的伪代码：

Sarsa是一种on-policy算法，因为在估计$q_t$值时，会用到依据${\pi }_t$产生的样本，更新$q_t$后，我们又会依据新的$q_t$来更新策略得到${\pi }_{t+1}$，然后用${\pi }_{t+1}$产生样本继续更新$q_{t+1}$，这样交替进行，最后得到最优策略。在这个过程中我们发现产生样本的策略和得到的最优策略是同一个策略，所以是on-policy算法。

四、Expected Sarsa

给定策略$\pi$，其动作值可以用Sarsa的一种变体Expected-Sarsa来估计。Expected-Sarsa的迭代格式如下：
$$\begin{array}{rl}{q}_{t+1}(s_t,a_t)& =q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-(r_{t+1}+\gamma \mathbb{E}[q_t(s_{t+1},A)])]\\ & =q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-(r_{t+1}+\gamma \sum _a\pi (a|s_{t+1})q_t(s_{t+1}),a)]\end{array}$$
同Sarsa类似，Expected-Sarsa可以看作是用RM算法求解如下贝尔曼方程得到的迭代格式：
$$\begin{array}{rl}{q}_{\pi }(s,a)& =\mathbb{E}[R_{t+1}+\gamma \mathbb{E}[q_{\pi }(S_{t+1},A_{t+1})|S_{t+1}]|S_t=s,A_t=a]\\ & =\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s,A_t=a].\end{array}$$
虽然Expected Sarsa的计算复杂度比Sarsa高，但它消除了随机选择$a_{t+1}$所带来的方差。在相同的采样样本条件下，Expected Sarsa的表现通常比Sarsa更好。

五、Q-learning

接下来我们介绍强化学习中经典的Q-learning算法，Sarsa算法和Expected-Sarsa都是估计$q(s,a)$，如果我们想要得到最优策略还需要policy-improvement，而Q-learning算法则是直接估计$q^{\ast }(s,a)$，如果我们能得到$q^{\ast }(s,a)$就不用每一步还执行policy-improvement了。Q-learning的迭代格式如下：
$$q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)\left[q_t(s_t,a_t)-\left(r_{t+1}+\gamma \underset{a\in \mathcal{A}(s_{t+1})}{\max }{q}_t(s_{t+1},a)\right)\right],(7.18)$$
Q-learning也是一种随机近似算法，用于求解以下方程:
$$q(s,a)=\mathbb{E}\left[R_{t+1}+\gamma \underset{a}{\max }q(S_{t+1},a)|S_t=s,A_t=a\right].$$
这是$q(s,a)$贝尔曼最优方程，所以Q-learning本质就是求解贝尔曼最优方程的随机近似算法，其伪代码如下：

显然Q-learning是一种Off-policy算法，因为$q_t(s,a)$在更新的时候，用的数据可以是一个给定$ϵ$-greedy策略${\pi }_a$产生的，但是直接学习到$q^{\ast }(s,a)$，我们可以通过$q^{\ast }(s,a)$得到一个greedy策略${\pi }_b^{\ast }$.

即使Q-learning是off-policy的，但我们也可以按on-policy的方式来实现，下面给出这两种实现，我们可以更清楚地看到off-policy和on-policy的区别：

六、参考资料

1. Zhao, S… Mathematical Foundations of Reinforcement Learning. Springer Nature Press and Tsinghua University Press.
2. Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.