本文是在学习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)

而当λ=1时,是与MC是等价的,下面几张图就说的是这件事

  • When λ = 1, credit is deferred until end of episode
  • Consider episodic environments with offline updates
  • Over the course of an episode, total update for TD(1) is the
  • same as total update for MC
  • TD(1) is roughly equivalent to every-visit Monte-Carlo
  • Error is accumulated online, step-by-step
  • If value function is only updated offline at end of episode
  • Then total update is exactly the same as MC

实质上forward-view TD(λ)和backward view TD(λ)是等价的,是一个算法从两个角度去看

Offline updates

  • Updates are accumulated within episode
  • but applied in batch at the end of episode

Online updates

  • TD(λ) updates are applied online at each step within episode
  • Forward and backward-view TD(λ) are slightly different
  • NEW: Exact online TD(λ) achieves perfect equivalence
  • By using a slightly dierent form of eligibility trace
  • Sutton and von Seijen, ICML 2014

总结: