《增强学习ReinforcementLearning经典算法梳理》由会员分享,可在线阅读,更多相关《增强学习ReinforcementLearning经典算法梳理(13页珍藏版)》请在金锄头文库上搜索。
1、增强学习Reinforcement Learning经典算法梳理1:policy and value iteration前言就目前来看,深度增强学习(Deep Reinforcement Learning)中的很多方法都是基于以前的增强学习算法,将其中的value function价值函数或者Policy function策略函数用深度神经网络替代而实现。因此,本文尝试总结增强学习中的经典算法。本文主要参考:1Reinforcement Learning: An Introduction;2Reinforcement Learning Course by David Silver1 预备知识对
2、增强学习有所理解,知道MDP,Bellman方程详细可见:Deep Reinforcement Learning 基础知识(DQN方面)很多算法都是基于求解Bellman方程而形成:Value IterationPolicy IterationQ-LearningSARSA2 Policy Iteration 策略迭代Policy Iteration的目的是通过迭代计算value function 价值函数的方式来使policy收敛到最优。Policy Iteration本质上就是直接使用Bellman方程而得到的:那么Policy Iteration一般分成两步:Policy Evaluat
3、ion 策略评估。目的是 更新Value FunctionPolicy Improvement 策略改进。 使用 greedy policy 产生新的样本用于第一步的策略评估。本质上就是使用当前策略产生新的样本,然后使用新的样本更新当前的策略,然后不断反复。理论可以证明最终策略将收敛到最优。具体算法: 那么这里要注意的是policy evaluation部分。这里的迭代很重要的一点是需要知道state状态转移概率p。也就是说依赖于model模型。而且按照算法要反复迭代直到收敛为止。所以一般需要做限制。比如到某一个比率或者次数就停止迭代。3 Value Iteration 价值迭代Value I
4、teration则是使用Bellman 最优方程得到然后改变成迭代形式value iteration的算法如下: 那么问题来了:Policy Iteration和Value Iteration有什么本质区别?为什么一个叫policy iteration,一个叫value iteration呢?原因其实很好理解,policy iteration使用bellman方程来更新value,最后收敛的value 即v是当前policy下的value值(所以叫做对policy进行评估),目的是为了后面的policy improvement得到新的policy。而value iteration是使用bell
5、man 最优方程来更新value,最后收敛得到的value即v就是当前state状态下的最优的value值。因此,只要最后收敛,那么最优的policy也就得到的。因此这个方法是基于更新value的,所以叫value iteration。从上面的分析看,value iteration较之policy iteration更直接。不过问题也都是一样,需要知道状态转移函数p才能计算。本质上依赖于模型,而且理想条件下需要遍历所有的状态,这在稍微复杂一点的问题上就基本不可能了。4 异步更新问题那么上面的算法的核心是更新每个状态的value值。那么可以通过运行多个实例同时采集样本来实现异步更新。而基于异步更
6、新的思想,DeepMind出了一篇不错的paper:Asynchronous Methods for Deep Reinforcement Learning。该文对于Atari游戏的效果得到大幅提升。5 小结Reinforcement Learning有很多经典算法,很多算法都基于以上衍生。鉴于篇幅问题,下一个blog再分析基于蒙特卡洛的算法。增强学习Reinforcement Learning经典算法梳理2:蒙特卡洛方法1 前言在上一篇文章中,我们介绍了基于Bellman方程而得到的Policy Iteration和Value Iteration两种基本的算法,但是这两种算法实际上很难直接应
7、用,原因在于依然是偏于理想化的两个算法,需要知道状态转移概率,也需要遍历所有的状态。对于遍历状态这个事,我们当然可以不用做到完全遍历,而只需要尽可能的通过探索来遍及各种状态即可。而对于状态转移概率,也就是依赖于模型Model,这是比较困难的事情。什么是状态转移?就比如一颗子弹,如果我知道它的运动速度,运动的当前位置,空气阻力等等,我就可以用牛顿运动定律来描述它的运动,进而知道子弹下一个时刻会大概在哪个位置出现。那么这个基于牛顿运动定律来描述其运动就是一个模型Model,我们也就可以知道其状态(空间位置,速度)的变化概率。那么基本上所以的增强学习问题都需要有一定的模型的先验知识,至少根据先验知识
8、我们可以来确定需要多少输入可以导致多少输出。比如说玩Atari这个游戏,如果输入只有屏幕的一半,那么我们知道不管算法多么好,也无法训练出来。因为输入被限制了,而且即使是人类也是做不到的。但是以此同时,人类是无需精确的知道具体的模型应该是怎样的,人类可以完全根据观察来推算出相应的结果。所以,对于增强学习的问题,或者说对于任意的决策与控制问题。输入输出是由基本的模型或者说先验知识决定的,而具体的模型则可以不用考虑。所以,为了更好的求解增强学习问题,我们更关注Model Free的做法。简单的讲就是如果完全不知道状态转移概率(就像人类一样),我们该如何求得最优的策略呢?本文介绍蒙特卡洛方法。2 蒙特
9、卡洛方法蒙特卡洛方法只面向具有阶段episode的问题。比如玩一局游戏,下一盘棋,是有步骤,会结束的。而有些问题则不一定有结束,比如开赛车,可以无限的开下去,或者说需要特别特别久才能结束。能不能结束是一个关键。因为只要能结束,那么每一步的reward都是可以确定的,也就是可以因此来计算value。比如说下棋,最后赢了就是赢了,输了就是输了。而对于结束不了的问题,我们只能对于value进行估计。那么蒙特卡洛方法只关心这种能够较快结束的问题。蒙特卡洛的思想很简单,就是反复测试求平均。如果大家知道在地上投球计算圆周率的事情就比较好理解了。不清楚的童鞋可以网上找找看。那么如何用在增强学习上呢?既然每一
10、次的episode都可以到结束,那么意味着根据:每一步的reward都知道,也就意味着每一步的return Gt都可以计算出来。这就好了。我们反复做测试,这样很多状态会被遍历到,而且不止一次,那么每次就可以把在状态下的return求和取平均。当episode无限大时,得到的数据也就接近于真实的数据。蒙特卡洛方法就是使用统计学的方法来取代Bellman方法的计算方法。上面的算法叫first-visit MC。也就是每一次的episode中state只使用第一次到达的t来计算return。另一种方法就是every-visit,就是每一次的episode中state只要访问到就计算return求平均
11、。所以可以看到蒙特卡洛方法是极其简单的。但是缺点也是很明显的,需要尽可能多的反复测试,而且需要到每一次测试结束后才来计算,需要耗费大量时间。但是,大家知道吗?AlphaGo就是使用蒙特卡洛的思想。不是蒙特卡洛树搜索,而是说在增强学习中使用蒙特卡洛方法的思想。AlphaGo每次也是到下棋结束,而且只使用最后的输赢作为return。所以这也是非常神奇的事,只使用最后的输赢结果,竟然能够优化每一步的走法。3 使用蒙特卡洛方法来控制上面说的蒙特卡洛方法只是能够对当前的policy进行评估。那么大家记得上一个blog说的policy iteration方法吗?我们可以在policy iteration中
12、使用蒙特卡洛方法进行评估,然后使用greedy policy更新。那么依然是有两种做法。一种就是在一个policy下测试多次,评估完全,然后更新policy,然后再做很多测试。另一种就是不完全评估,每次测试一次完就评估,评估完就更新:第一种做法:第二种做法:两种做法都能够收敛,那么显然第二种做法的速度更快。那么再改进一点,就是改变greedy policy中的值,使得不断变小趋于0,这个时候最后得到的policy就是完全的最优policy了。这个算法就叫做GLIE Monte-Carlo Control:其他变种:Monte Carlo with Exploring Starts,使用Q(s,
13、a),然后使用上面说的第二种做法,一次episod就更新一次policy,而且policy直接使用Q值。policy的更新使用了greedy,目的就是能够更好的探索整个状态空间。4 Off Policy Learning那么上面的方法一直是基于当前的policy,为了探索状态空间,采用一个次优的策略greedy policy来探索。那么是不是可以更直接的使用两个policy。一个policy用来探索空间,也就是behavior policy,另一个policy就是为了达到最优policy,叫做target policy。那么这种方法就叫做off policy learning。On-polic
14、y的方法比较简单,off-policy 方法需要更多的概念和标记,比较不好理解,而且,由于behaviour policy和target policy不相关,这种方法比较不容易收敛。但是off-policy更强大,更通用,实际上的on-policy方法就是off-policy方法的一个子集。比如,就可以使用off-policy从人类专家或者传统的控制算法来学习一个增强学习模型。关键是要找到两个policy之间的权重关系,从而更新Q值。关于off-policy learning的部分,之后结合TD方法再做分析。小结本次blog分析了一下蒙特卡洛方法。这种基于统计学的方法算法简单,但是更多的只能用
15、于虚拟环境能进行无限测试的情况。并且state 状态比较有限,离散的最好。基于这个方法,比如简单的五子棋(棋盘最好小一点),就可以用这个方法来玩玩了。增强学习Reinforcement Learning经典算法梳理3:TD方法1 前言在上一篇blog中,我们分析了蒙特卡洛方法,这个方法的一个特点就是需要运行完整个episode从而获得准确的result。但是往往很多场景下要运行完整个episode是很费时间的,因此,能不能还是沿着bellman方程的路子,估计一下result呢?并且,注意这里,依然model free。那么什么方法可以做到呢?就是TD(temporal-difference时
16、间差分)方法。有个名词注意一下:boostraping。所谓boostraping就是有没有通过估计的方法来引导计算。那么蒙特卡洛不使用boostraping,而TD使用boostraping。接下来具体分析一下TD方法2 TD与MC的不同MC使用准确的return来更新value,而TD则使用Bellman方程中对value的估计方法来估计value,然后将估计值作为value的目标值进行更新。也因此,估计的目标值的设定将衍生出各种TD下的算法。那么TD方法的优势有什么呢?每一步都可以更新,这是显然,也就是online learning,学习快;可以面对没有结果的场景,应用范围广不足之处也是显而易见的,就是因为TD target