增强学习 Reinforcement learning part 4 - Model-Free Prediction

本文是在学习David Silver所教授的Reinforcement learning课程过程中所记录的笔记。因为个人知识的不足以及全程啃生肉，难免会有理解偏差的地方，欢迎一起交流。

课程资料：http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Teaching.html

1、Introduction

上一节讲的东西是基于已知的MPD，也就是有模型学习，而实际中很多情况下MDP是未知的，各个状态之间的转移概率以及reward很难得知，所以这种环境称为model free。

首先先讲model free prediction，类似于DP中的policy evaluation，去估计这个未知的MDP中各个状态的value function。]

下一节会讲model free control，类似于DP中的policy iteration，去最优化这个未知的MDP中各个状态的value function。

2、Monte-Carlo Learning

在有模型的时候给定一个policy pi后对这个policy进行评估很简单，但是在model free的情况下，不知道MDP的状态转移概率及reward（但是知道state），就无法用原来的公式进行计算。所以MC采用的学习方式是learn directly from episodes of experience。这里episode理解为MDP中的某个序列，比如在之前的student例子中，C1 C2 C3 Pass Sleep就可理解为一个episode。MC的思想就是在MDP中，依据给定的policy pi去行动，会依次经过一些state并且得到reward。如果不断的尝试（尝试一次就是一个episode），那么就可以大体估计出MDP的状态转移概率和reward。

需要注意的是MC学习用的episode必须是完整的和有终止状态的。（完整可以这么理解，假如从C1 state开始，在policy pi下会依次经过C2 C3 Pass Sleep这些state，其中sleep是终止状态，那么C1到sleep就被称为一个完整的episode，要使用MC方法来计算C1的state value function，那必须使用这个完整的episode。与之相对的是下面要讲的TD方法是使用不完整的episode，比如计算C1的state value function ，只需使用C1 C2就可以）

使用Monte-Carlo进行policy evaluation。回忆下原来计算state value function的时候是求从状态s开始对未来的期望收益，而在MC中，收益的计算方法依旧一样，因为MC使用完整的episode，所以对于状态s后面的reward都知道。但是不再是对未来的收益求期望了（因为转移概率不知道），我们采用最简单的方法，求平均value = mean return

在一个episode，如果经过了状态s，那么N(s)就累加一，S(s)累加上这次的return。然后状态s的V(s)就等于S/N，如果尝试的episode次数足够多，那么求出来的V(s)就是Vpi(s)。（原因是尝试的次数足够多后，整个policy的所有情况都会遍历到，从状态s往后的各种情况的return的概率用频率逼近，所以也就和求期望是一样的了）

可以看到first标记为红色，意思是在一个episode中，第一次经过状态s才计数，如果一个episode中经过了状态s好几次（循环），那么后面几次都不算的。与之相对的是every，就是每次经过状态s都计数。

下面讲了一个例子，玩blackjack 21点

简单描述下建模过程，每个state由三个因素构成，agent手中牌的点数和，dealer显示的一张牌的点数，agent手中有没有ace（也就是A，这张牌既可以当1点，也可以当10点），这是agent能观察到的environment。agent的action有两种，stick和twist。reward按照胜负来表示，赢了+1，平手为0，输了-1

后面是使用MC来评估value function，在经过10000次episode（也就是10000局比赛），可以发现图像并不平整还有起伏，说明还有噪声，也就是还没收敛到Vpi，在经过50000局比才后，图像很平整，就可以认为已经收敛到Vpi了

有个问题可以改进，那就是求平均值那里，原来是把所有的值都累加完再求，而其实均值是可以增量求的。k个值的均值等于前k-1值的均值加上后面那部分，后面那部分可以看作是一个误差，什么与什么的误差呢，就是前k-1个求出来的均值是uk-1，预计下一个值也是uk-1，但实际上第k个值是xk，所以就产生了个误差，所以就要把这部分误差加上去修正平均值。

所以在MC中更新V(s)可以用增量的方式，每完成一个episode，便可以用Gt去增量更新V(s)

后面误差前的系数虽然是跟次数有关，但实际上也可以用一个固定值代替，因为在实际情况中，记录次数需要额外开销，并且如果是一个动态的系统，也没法从头到尾一直记录次数。可以证明的是，用固定值代替也不影响结果。

In non-stationary problems, it can be useful to track a running mean, i.e. forget old episodes.

In real world, don’t want to remember everything.

3、Temporal-Difference Learning

TD称为时序差分学习。MC因为要完成一个episode后才能更新V(s)，效率比较低，所以TD便改进了这一点，learn directly from incomplete episodes of experience，TD使用的是不完整的episode。

MC使用的是真实的return来更新V(s)，但是TD不是。TD使用一步真实的reward加上对下一个状态的state value function的猜测，所以TD updates a guess towards a guess。这种方法的好处就是走出一步就可以更新V(s)，而不用等整个episode完成。

下面举个例子，下班回家时对耗时的估计。可以看到MC要等整个路程都完成后才能更新各个状态的值，而TD在进行到下一状态后就可以更新上一状态的值。

所以MC与TD相比较

TD can learn before knowing the final outcome
TD在每步结束后就可以实时学习（learn online），也就是实时更新state value function。但是MC必须整个episode完成后才能求出Gt，从而更新state value function
TD can learn without the final outcome
TD可以使用不完整的episode学习，MC只能使用完整的episode学习。这样的话，TD可以用于continuing (non-terminating)的environment中，而MC只能用于episodic (terminating)的environment中

再来讨论下Bias/Variance平衡的问题

bias：MC中的Gt是属于无偏估计的，因为用到的reward都是真实的没有偏差的，但是TD target是有偏差的估计，因为V(st+1)是猜的，不是真实的。

variance：因为MC的Gt要加很多项，每一项都会存在随机的噪声，所以MC的variance会很高，而TD只有两项，所以受到的随机因素影响很小，从而TD的variance就小。

所以这是MC与TD第二个区别

MC has high variance, zero bias
- Good convergence properties
- (even with function approximation)
- Not very sensitive to initial value
- Very simple to understand and use
TD has low variance, some bias
- Usually more efficient than MC
- TD(0) converges to vpi(s)
- (but not always with function approximation)
- More sensitive to initial value

下面再讲个例子，有一条直线，左右两边是终止状态，中间是ABCDE五个状态，action是向左或者向右，只有在E向右的时候才会得到reward+1，左边是对各个状态的state value function的估计，可以看到经过100次episode后，已经比较接近真实的value了。右图是统计了估计的value与真实的value之间的RMS误差，上半部分是MC，下半部分是TD，分别使用了不同的alpha值，可以看到TD整体是优于MC的，并且随着episode次数的增加，误差逐渐减少并趋于稳定，在平稳部分还有波动那就是噪声引起的，这也可以看出TD的variance比MC的小很多。

之前说道MC和TD在experience趋向无穷的时候，V(s)才会收敛于Vpi(s)，那如果experience是有限的呢？

比如这个例子，总共只有八次episode，求AB两个状态的state value function。可以先求B的，8次中有两次得到的reward是0，6次得到的reward是1，所以V(B) = 6/8 = 0.75。那A的呢，如果以MC的角度去看，出现A的episode只有第一个，并且在AB收到的reward都为0，所以Gt = 0，从而V(A) = 0。但是从TD的角度看，我们先用得到的episode构建出MDP，所以V(A) = 0 + V(B) = 0.75

从这个例子中也可以看出在有限的experience下，MC和TD的计算方法是不一样的

MC：是求最小均方误差，就是使用出现过A的episode来的计算Gt，然后更新state value function

TD：是使用最大似然马尔可夫模型，根据所有的episode计算出状态转移概率和reward，从而求出state value function

通过这个例子可以看出MC与TD的第三点区别，TD能利用马尔可夫性，所以在马尔可夫环境下更有效率，而MC无法利用马尔可夫性，所以在非马尔可夫环境下更有效率

TD exploits Markov property
- Usually more efficient in Markov environments
MC does not exploit Markov property
- Usually more effiective in non-Markov environments

下面总结一下MC、TD、DP的区别，MC是使用一个完整的episode来更新V(s)，TD是使用不完整的episode来更新V(s)，而DP是使用状态s后面下一步所有的状态来计算V(s)

而且还有两个概念前面没有提及，bootstrapping和sampling

sampling可以理解成抽样，就是使用一个episode，可以看到MC和TD是使用sampling的，而DP是使用遍历下一层所有的情况，所以不使用sampling

bootstrapping可以理解成是不是需要使用完整的episode，像TD和DP都是使用下一层来计算上一层的，而MC是使用一个完整的episode，一直到terminate

下面这张图从bootstrapping和sampling两个维度把之前讲的方法进行了分类，一目了然

4、TD(λ)

之前讲的TD都是只考虑了未来的一步，那可不可以考虑未来的两步呢，甚至是三步四步？当然可以，见下图，这就称作n-step TD，如果n无穷，那么就是MC方法了

在n-step TD中Gt的计算方法如下

那么n-step TD的V(s)更新公式变为

下图是Large Random Walk Example，统计了经过10次episode后的RMS误差，横坐标为选择不同的alpha，图中不同的曲线代表了n的不同取值。

上面的是online的，immediately update value function。下面的是offline，delay update until the end of episode

可以看到online与offline误差最小的位置不一样，如果我们换了一个MDP或者做了一些其他的变化，那这个最优点就会变化，选的n就会变，如果每次都要画这种图来比较的话就太麻烦了，有没有什么办法可以解决一下？

答案是有的，那就是把不同的n-step组合一下，比如把n=4和n=2按照一半一半的比例组合一下。但是这么组合很傻瓜，有没有什么更有效的组合方法？

答案也是有的，把所有的n-step都综合起来，各自的比例分别是(1-λ)λn-1，所以新的Gtλ就是把Gt(n)按照各自的比例加起来，然后用Gtλ来更新V(s)，所以这种TD称作Forward-view TD(λ)

关于n-step各自的比例(1-λ)λn-1是服从指数分布的

Forward-view TD(λ)如下图所示，在更新状态St时需要用到未来的值，所以被称作像前看forward view。但是需要注意的是，因为需要用到所有的n-step，所以它也需要完整的episode的才能计算，这一点与MC一样

这是Forward-view TD(λ) on Large Random Walk，图中不同的曲线代表着选择了不同的λ

既然有forward view，那么肯定有backward view

Forward view provides theory
Backward view provides mechanism
Update online, every step, from incomplete sequences

讲述一个新概念，Eligibility Traces，字面理解是资格迹或者传导径迹，其实质是判断过去经历过的状态中哪些对现在的状态有影响。比如依次经过了三次响铃，一次灯亮后，你遭到了电击，那么是三次响铃导致了电击，还是说灯亮后会导致电击。当然都有可能，所以我们从把这两方面都考虑进去，考虑频率的称为frequency heuristic，考虑最近的称为recency heuristic，然后把它们俩结合起来。

下面是backward view TD(λ)的主要含义，对于每个state来说都有自己的eligibility trace E(s)，在更新V(s)的时候把E(s)也考虑进去了，乘在TD error部分

E(s)初始化为0，在第一次经过状态s的时候便会+1，并且每一时刻E(s)都会按照

进行指数级衰减，如果再次经过了状态s，那么再+1。这个+1就是下图中突然向上的那一下。

假设下图描述的就是状态s的eligibility trace，在最一开始的时候为0，然后第一次经过状态s后+1，然后开始衰减，但是过了很短的时间又经过了状态s，所以又向上冲了一下。所以图中前面一部分就是很短的时间内经过了状态s四次，所以此时E(s)就很高，但是在接下来很长的时间内没有在经过状态s，所以E(s)快速衰减，接近于0。此时再次连续两次经过状态s，又很长时间没经过，然后再次经过状态s，然后就结束了。所以图片就是状态s的E(s)的值的变化情况。

backward view TD(λ)的伪代码，看着比较容易理解这个算法是怎么样的，以及eligibility trace是如何更新的

Forward view和backward view的本质是一样的，只是从两个角度去描述了同一件事情。Forward view是向未来看，用未来的reward来更新当前状态，而backward view是向过去看，在当前状态收到reward了以后，它会把reward传递回过去，去更新过去的点（以过去状态的角度看来，这不也就是用未来的reward来更新自己吗）。并且forward view和backward view都是离当前状态近的占的比例高，如果两个状态离的很远（假设为A,B，以时间为顺序A在过去B在未来），从forward view的角度看，B对A的影响很小，从backward view的角度看，B往回传递给A的影响也很小，是统一的。

当λ=0时，便是最一开始讲的TD(0)