强化学习五、时间差分（一）

男娘i 2021-09-25 09:20 514阅读 0赞

之前已经分享过基于模型的动态规划方法（DP）和基于免模型的蒙特卡罗法（MC），DP方法解决了在MDP框架下环境已知的情况下求解值函数和策略，而MC是在不知道环境的情况，通过与环境足够的交互来获得经验来进行学习值函数和策略。但是MC需要等到每次试验结束才更新，学习效率低，而本次分享的时间差分（TD）可以结合MC的采样和DP的bootstrapping。

我们先来回顾一下MC的特点：

![图片][5db7b09c107062e929a3eb3c5baf9cf5.png]

TD的特点如下：

![图片][5faaedaf6baa5867b1f58b6febff3c78.png]

下面把MC和TD的值函数更新作一个对比：

![图片][4904be9a4596bbf74920b48274050057.png]

如上所示，TD中才会把Gt写成递归的形式。这样，每走一步都可以更新一次V。而蒙特卡罗中，却需要走完整个样本，才能得到Gt，从而更新一次。蒙特卡罗学习方法的更新是这样的：

![图片][5954ad75af4d1732e5db86c16054fdd3.png]

在TD中，算法在估计某一个状态的价值时，用的是离开该状态时的即时奖励Rt+1与下一个状态t+1的预估状态价值乘以折扣因子γ组成，

![图片][be1eb763584ef12a527b1ff058d27749.png]

其中，bootstrapping指的就是TD目标值Rt+1+γV(St+1)代替Gt的过程。

显然，蒙特卡罗每次更新都需要等到agent到达终点之后再更新；而对于TD来说，agent每走一步它都可以更新一次，不需要等到到达终点之后才进行更新。

**下面我们从多个角度来对比一下****MC****和****TD****：**

**1****、方差与偏差**

我们在实际使用中发现MC和TD两种算法的表现却差别比较大，熟悉机器学习的朋友们都知道偏差和方差的概念，那我们先从这两个角度来分析一个这两个算法：

![图片][efecdcc32a18a3fc7b1bd0c6d0d8689a.png]

MC的期望是值函数的定义，因此MC是无偏估计，但是MC每次得到的累计回报Gt随机性很大，因此尽管期望等于真值，但是方差无穷大。TD中如果V(St+1)采用真实值，那么TD也是无偏估计，然而在实验中V(St+1)也是估计值，因此TD属于有偏估计。与MC方法相比，TD是用到了一步随机状态和动作，因此TD目标的随机性要比MC的Gt小，相应的方差也比MC小，具体对比如下：![图片][510d04d3f404e85dbf2bf188b55a1c92.png]

**AB example**

已知：有两个状态A和B，折扣因子为1，有8个完整的episodes。除了第一个episode有状态转移之外，其余7个均只有一个状态。如下图所示：

![图片][53855d9baebfa0dd79851406a4dc367c.png]

问题就是要求解出V(A)和V(B)。

解释：假如应用MC算法，由于需要完整的episode，因此，只有episode1 能够用来计算A的状态值，所以显然，V(A) = 0；同时B状态的价值为6/8。而对于TD算法来说，由于状态A的后继有状态B，所以状态A的价值是通过状态B的价值来计算的。所以根据上面TD的计算公式，V(A)=V(B) = 6/8.

![图片][2ddaa682e7d8af4113822cca5591c256.png]

**2****、收敛性对比**

![图片][70db14cad78e5d49a3eb9e65bfe30512.png]

**DP****、****MC****和****TD****对比**

**1****、值函数更新方式**

Monte-Carlo, Temporal-Difference 和Dynamic Programming这三种学习方法都是用来计算状态价值的。它们的区别在于，前两种是在不知道模型的情况下常用的方法，而MC方法又需要一个完整的episode来更新状态价值，TD则不需要完整的episode。DP方法则是基于Model(知道模型的运作方式)的计算状态价值的方法。它通过计算一个状态S所有可能的转移状态S’及其转移概率以及对应的即时奖励来计算这个状态S的价值。也正是因为它知道整个模型的情况(知道状态转移概率与即时奖励)，所以它才能够这样子计算全面的情况。下面的图可以直观地看出它们的区别：

1）MC

![图片][7a77ee6c4deec9fd1f58dde6b561f881.png]

上图中的这颗树，代表了整个状态与动作空间。对于蒙特卡罗方法来说，要更新一次V值，需要有一个完整的样本(即图中红色部分就是一个样本)。这条路径经过了三个状态，所以可以更新三个状态的V值。由于不知道模型情况，所以无法计算从St到下面四个节点的概率以及即时奖励，所以一次只能更新一条路径。如果重复次数够多了，就能覆盖所有的路径，最后的结果才能跟动态规划那样。

2）TD

![图片][a797184d1e4c4ba89c2019ee80e360a8.png]

上图的红色部分是TD每次更新所需要的，每次更新只考虑下一步的状态值函数。对于MC和TD来说，它们都是模型不可知的，所以它们只能通过尝试来近似真实值

3）DP

![图片][0cde66b06dd6d99a6105699c7fcbbeaa.png]

这是动态规划的V值计算，由于知道了模型，所以可以直接使用贝尔曼公式计算期望V值。

**2****、****Bootstrapping and Sampling**

![图片][35b143f9f6c01b034f7e70a5a5bc102a.png]

综上所述，时间差分TD算法和蒙特卡罗算法MC以及动态规划DP有千丝万缕的联系。首先MC与TD都是免模型的方法，但是他们的目标是不一样的，值函数的更新公式不同，导致他们的效果差别还是比较大的，MC的方差比较大，TD的偏差比较大，这时候很容易想到梯度下降，可以通过batch来改进。本文只介绍了TD的基本思想和原理，下面会介绍两种经典的算法Sarsa和Qlearning算法，以及TD(λ)，敬请期待。

[5db7b09c107062e929a3eb3c5baf9cf5.png]: /images/20210923/05e7faeb24194f10ab548e99458324c5.png
[5faaedaf6baa5867b1f58b6febff3c78.png]: /images/20210923/c33e17d3a8474d91a690ec99821bbf60.png
[4904be9a4596bbf74920b48274050057.png]: /images/20210923/7497b2f4b32f46cd8652653aa626a276.png
[5954ad75af4d1732e5db86c16054fdd3.png]: /images/20210923/68d66ca2ef5d4d03899fcfd596b1e018.png
[be1eb763584ef12a527b1ff058d27749.png]: /images/20210923/6cf367383331492e8ed32d2ac61d2862.png
[efecdcc32a18a3fc7b1bd0c6d0d8689a.png]: /images/20210923/dae6f68142444f6eba863965e3d0a220.png
[510d04d3f404e85dbf2bf188b55a1c92.png]: /images/20210923/f46d0cef93094222b22ff857b2df52aa.png
[53855d9baebfa0dd79851406a4dc367c.png]: /images/20210923/2c1076e17488447c9a25b51aae6dd9f7.png
[2ddaa682e7d8af4113822cca5591c256.png]: /images/20210923/fcfeb6440f3842b8afa2e3b8f7154d9a.png
[70db14cad78e5d49a3eb9e65bfe30512.png]: /images/20210923/c592349452b14464868471f048d2f8c7.png
[7a77ee6c4deec9fd1f58dde6b561f881.png]: /images/20210923/7b819bf099124f01bd8ead478ced950a.png
[a797184d1e4c4ba89c2019ee80e360a8.png]: /images/20210923/5a832abc49ad44178535371e36284f3d.png
[0cde66b06dd6d99a6105699c7fcbbeaa.png]: /images/20210923/da96b4e151384e5daf9386e44cf880f4.png
[35b143f9f6c01b034f7e70a5a5bc102a.png]: /images/20210923/45ca3ce7fcfd4283a1a8b4960e6f97e2.png