David Silver 强化学习 第四讲

Model-Free 的预测

Posted by Pelhans on January 16, 2018

在之前的学习中,我们学习的都是在清楚MDP细节时的策略评估和优化,在本讲以及下讲,我们讲学习解决一个可以被认为时MDP但是不掌握MDP具体细节的问题。此时Agent直接通过与环境的交互来进行控制和预测。本讲集中与预测部分,即策略评估。并介绍三种处理方法:蒙特卡罗强化学习、时序差分强化学习和时序差分强化学习。

蒙特卡罗强化学习(Monte-Carlo Reinforcement Learning)

总结自叶强的David Silver强化学习公开课中文讲解及实践专栏

蒙特卡罗强化学习指的是在不清楚MDP状态及即时奖励的情况下,直接中完整的Episode来学习状态价值,通常情况下某个状态的价值等于多个Epiode中该状态算得到的所有收获的平均。它的特点有:不基于模型本身、直接从经历过的Episode中学习、使用的思想是用平均收获代替价值,理论上来说,经历的Episode越多,结果就越准确。

蒙特卡罗策略评估(Mone-Carlo Policy Evaluation)

该策略评估的目标是在给定的策略下,从一系列完整的Episode经历中学习得到该策略下的状态价值函数。它需要使用的信息包含状态的转移、使用的行为序列、中间状态获得的即时奖励以及到达终止状态时获得的即时奖励。它们可以从完整的Episode中获取。数学描述为:

基于给定策略的一个Episode信息可以表示为如下的一个序列:

t时刻的状态的收获:

其中T为终止时刻。该策略下某一状态s的价值:

即该状态下收获的期望。

在状态转移过程中,会出现一个状态又一次或多次返回自身的情况,此时的状态次数计算和Episode的收获计算为:

1) 首次访问蒙特卡罗策略评估

即对于每一个Episode,仅当该状态第一次出现时列入计算:

状态出现的次数加1:

总的收获值更新:

状态s的价值:

时,

2) 每次访问蒙特卡罗策略的评估

状态s每次出现在状态转移链时,计算的具体公式和上面的一样,但具体意义不一样原文是这么写的,但我也不知道为啥会一样。。。按道理上面的第一步不应该计算状态出现的次数啊

状态出现的次数加1:

总的收获值更新:

状态s的价值:

时,

累进更新平均值(Incremental Mean)

前面我们提到需要用蒙特卡罗方法求解平均收获时,需要计算平均值,通常需要现存储所有数据然后计算,但这样存储起来就很麻烦,因此下面给出一种实时更新平均值的方法。理论公式如下:

公式推到比较简单,把该方法用于蒙特卡罗策略评估就可以得到实时更新方案了。

蒙特卡罗累进更新

对于每个Episode中的每一个:

对于Episode中的每一个状态有一个收获,每一次碰到,使用上述方法对状态的平均价值进行更新:

其中:

在处理非静态问题时,使用累进更新可以扔掉过往Episode的信息。此时引入参数来更新状态价值:

以上就是蒙特卡罗学习方法,但由于该方法必须经历完整的Episode,因此在实际中使用的不多,接下来介绍实际中常用的时序差分学习方法(TD方法).

时序差分学习 (Temporal-Difference Learning)

时序差分学习简称TD学习,它和MC学习一样,也从Episode中学习,不需要了解模型本身,但它的不需要学习完整的Episode,通过自身的引导(Bootstrapping),猜测Episode的结果,同时持续更新这个猜测.这个Bootstrapping指的是TD目标值代替前面MC学习中收获的过程.

根据上面描述的TF学习,其算法在估计某一个状态价值时,利用离开该状态的即时奖励和下一时刻状态的预估价值与衰减系数的乘积两项.这符合Bellman方程的描述:

其中 称为TD目标值;

称为TD误差;

简单来说,TD算法就相当于在一个Episode中,它会根据下一时刻的奖励,及时的更新该状态的价值.而MC学习则必须在经过一个完整的Episode后才能对其进行更新.

MC学习和TD学习的对比

1) TD 在知道结果之前可以学习,MC必须等到最后结果才能学习.

2) MC基于实际收获G,它是基于某一策略的状态价值的无偏估计,因此MC没有bias,但有着较高的Variance,且对初始值不敏感.TD目标值是基于下一状态预估价值计算的当前预估收获,是当前状态实际价值的有偏估计,因此TD具有低Variance,对初值较敏感,通常比MC更高效.

3) TD算法使用了MDP问题的马尔科夫属性,在马尔科夫环境下更有效,但是MC算法并不利用它,通常在非Markov环境下更有效.

对比Monte-Carlo / Temporal-Difference / Dynamic Programming

1) 他们三个都是计算状态价值的方法,区别在于前两种是不再到Model情况下的常用方法,其中MC需要完整的Episode而TD则不需要.DP方法则基于Model来计算状态价值,它通过计算一个状态S的所有可能的转移状态及其转移概率以及对应的即时奖励来计算这个状态S的价值.

2) MC不需要Bootstrapping,只使用实际收获;DP和TD则需要.

3) MC和TD都是应用样本来估计实际的价值函数,而DP则是利用模型直接计算的到实际价值函数,没有样本或采样.

TD()

前面我们介绍了TD算法实际上相当于TD(0)算法,括号内的0表示在当前状态下考虑下几步状态,如0则表示多看1步,一次类推到n-step.

在当前状态向前行动n步,计算n步的收获.因此TD目标由两部分组成: 已走的步数用确定的即时奖励,剩下的使用预估计的状态价值.

TD(0)或TD是基于1-step预测额,MC是基于预测的.如下表所示:

由此定义n-step收获:

对应的,n-step的TD学习状态价值函数的更新公式就变成:

既然有n-step,那n等于多少时最好呢?它有具体的问题来决定,因此引入这个参数.通过引入这个参数,可以在不增加计算复杂度的情况下综合考虑所有步数的预测.这就是预测和收获.

-收获

-收获综合考虑了从1到的所有步收获,它给其中的任意一个n-step收获施加一定的权重.通过设计这样的权重,得到如下公式:

对应的-预测可以写成:

下图给出各步收获的权重分配图,图中最后一列的指数是T-t-1.T为终止状态的时刻步数,t为当前状态的时刻步数,所有权重加起来为1.

下图为不同时刻的权重示意图,所有权重加起来为1:

我们发现,在引入了后,要更新一个状态的状态价值,必须走完要完整的Episode来获得每一个状态的即时奖励.这就变得和MC算法要求一样了,当时就变成MC算法,给实际计算带来不便.

TD()从另一个方面提供了一个单步更新的机制,即引入效用追踪(Eligibility Traces, ES),结合频率启发和就近启发定义:

下图给出了对于t的一个可能的曲线图:

该图横坐标是时间,横坐标下的竖线代表当前进入了状态s,纵坐标是ES的值.可以看出,当某一状态连续出现时,E值在一定衰减的基础上提高,此时将增加该状态对于最终收获贡献的比重,因而在更新该状态价值的时候可以较多地考虑最终收获的影响。同时如果该状态距离最终状态较远,则其对最终收获的贡献越小,在更新该状态时也不需要太多的考虑最终收获。

特别的,E值不需要等到完整的Episode结束时才能计算出来,它可以每经过一个时刻就得到更新.将刚才的描述体现在公式里更新状态价值:

需要注意的是每个状态都有一个E值,它随时间而变化.当时等同于TD(0)算法,当时,在线更新的状态价值每一步都会有积累,离线更新时TD(1)算法等同于MC算法.

下图给出各种取值时,不算算法在不同情况下的关系: