马尔可夫决策(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,*,Markov Decision,马 尔 可 夫 决 策,第九组：史文祥,曹海歌,1,2,2,设计一个回报函数,，如果,learning agent,在决定一步后，获得了较好的结果，那么我们给,agent,一些回报（比如回报函数结果为正），若得到较差的结果，那么回报函数为负。比如，四足机器人，如果他向前走了一步（接近目标），那么回报函数为正，后退为负。如果我们能够对每一步进行评价，得到相应的回报函数，那么就好办了，我们只需要找到一条回报值最大的路径（每步的回报之和最大），就认为是最佳的路径。,2,2,马尔可夫决策过程（MDP,Markov decision processes）是基于马尔可夫过程理论的随机动态系统的最优决策过程。它是马尔可夫过程与确定性的动态规划相结合的产物，又称马尔可夫型随机动态规划。,研究一类可周期地或连续地进行观察的随机动态系统的最优化,问题,。在各个时刻根据观察到的状态，从它的马尔可夫决策相关书籍允许决策（,控制,、,行动,、,措施,等）集合中选用一个决策而决定了系统下次的转移规律与相应的运行效果。并假设这两者都不依赖于系统过去的历史。在各个时刻选取决策的目的，是使系统运行的全过 程达到某种最优运行效果，即选取控制（影响）系统发展的最优策略,。,3,2,MDP,五元组（S,A,P,sa,，R）,S:状态集（states）,A:一组动作（actions）,P,sa,:状态转移概率,：阻尼系数（discount factor）,R:回报函数（reward function）,S中一个状态到另一个状态的转变，需要A来,参与。P,sa,表示在当前sS状态下，经过aA,作用后，会转移到的其它状态的概率分布情况,4,2,一个较小的MDP模型,（机器人导航任务）,+1,-1,1,2,3,4,3,2,1,S:11 states,A=N,S,W,E,P,SN,(s),P,(3,1)N,(3,2)=0.8,P,(3,1)N,(4,1)=0.1,P,(3,1)N,(2,1)=0.1,R,R(4,3)=+1,R(4,2)=-1,R(s)=-0.02,（S,A,P,sa,，R）,5,2,MDP是如何工作的,时间0，从状态S,0,出发.,取出你在哪个地方at state S,0,选择一个动作A,0,决定action a,0,得到一个新状态S,1,P,S0a0,循环,S,0,S,2,S,1,S,3,a,0,a,1,a,2,.,R(S,0,),R(S,1,),R(S,2,),R(S,3,),.,+,+,+,R(S,0,),R(S,1,),2,R(S,2,),3,R(S,3,),.0,1),+,+,+,目标：,ER(S,0,),R(S,1,),2,R(S,2,),3,R(S,3,)+.,+,+,+,6,2,Policy(策略),已经处于某个状态s时,我们会以一定的策略来选择下一个动作a的执行，然后转换到另一个状态。,：SA,a=（s）,值函数（value function）,V,（s）=ER(S,0,)+R(S,1,)+,2,R(S,2,)+,3,R(S,3,)+.|s,0,=s,值函数是回报的加权和期望，给定也就给定了一条未来,的行动方案，这个行动方案会经过一个个状态，而到达每,个状态都会有一定回报值，距离当前状态越近的其它状态,对方案的影响越大，权重越高。,7,2,递推,V,（s）=ER(S,0,)+R(S,1,)+,2,R(S,2,)+,3,R(S,3,)+.,V,（s,1,）,下一个状态值函数的期望值,然而我们需要注意的是：,给定后，在给定状态s下，a是唯一的，但AS可能不是多到一的映射,立即回报,=R(S,0,)+（ER(S,1,)+,2,R(S,2,)+,3,R(S,3,)+.）,=R(S,0,)+V,（s）(s:下一个状态),8,2,给定一个固定的策略，我们怎么解这个等式 V,（s）=？,(3,1),(3,2),(4,1),(2,1),0.8,0.1,0.1,.,.,.,.,.,|S|个方程，|S|个未知数,9,2,+1,-1,1,2,3,4,3,2,1,0.52,0.33,0.37,+1,-0.09,-0.82,-1,-0.88,-0.83,-0.85,-1.00,1,2,3,4,3,2,1,一个具体的例子,对于给定的策略，我们可以写下这一策略的价值函数,这是一个策略，但这不是一个伟大的策略,V,（策略的价值函数）,10,2,目的：,找到一个当前状态s下，最优的行动策略。,定义最优的V*如下：,Bellman等式：,（2）,第二项是一个就决定了每个状态s的下一步动,作，执行a后，s按概率分布的回报概率和的期望,11,2,定义了最优的V*，我们再定义最优的策略*：SA,*：实际上是最佳策略，最大化我们的收益。,选择最优的*，也就确定了每个状态s的下一步动作a。,（3）,注意：,如果我们能够求得每一个s下最优的a，那么从全局来看，,SA的映射即可生成，并且是最优映射*。*针对全局的s，,确定了每一个s的下一个行动a,不会因为初始状态s选取的不同,而不同。,12,2,如何计算最优策略？,（MDP是有限状态，有限动作时）,值迭代法,1、将每一个s的V(s)初始化为0,2、循环直到收敛,对于每一个状态s,对V(s)做更新,i）同步迭代法,初始状态所有的v(s)都为0.,对s都计算新的V(s)=R(s)+0=R(s)。在计算每一个状态时，得到V(s)后，先存下来，不立即更新。待所有s的新值v(s)都计算完后，再统一更新。,ii)异步迭代法,对于每一个状态s,得到新的,v(s)后，不存储，直接更新。,V(s)V*(s),13,2,知道了V*(s)后，再用（3）求出相应的最优策略,0.86,0.90,0.93,+1,0.82,0.69,-1,0.78,0.75,0.71,0.71,1,2,3,4,3,2,1,=0.99,14,2,策略迭代法（*）,1、随机指定一个S到A的映射。,2、循环直到收敛,（a）令V:=V,（b）对于每一个状态s,对（s）做更新,V可以通过之前的bellmand等式求得,这一步会求出所有状态的V,（s）,根据（a）歩的结果挑选出当前状态,s下最优的a,然后对a做更新。,15,2,MDP中的参数估计,之前讨论的MDP中，状态转移概率P,sa,和回报函数R(s)是已知的。,实际中，我们需要从数据中估计出这些参数（S,A,已知）,S,10,S,12,S,11,S,13,a,10,a,11,a,12,.,S,20,S,22,S,21,S,23,a,20,a,21,a,22,.,a,ij,是s,ij,状态时要执行的动作,1,2,.,.,.,16,2,最大似然估计来估计状态转移概率,（从s状态执行动作a后到达s的次数）,（在状态s时，执行a的次数）,如果分母为0，则令P,sa,(s)=1/|s|,17,2,将参数估计和值迭代结合起来,（在不知道状态转移概率的情况下）,1、随机初始化,2、循环直到收敛,(a)在样本上统计中每个状态转移次数，更新P,sa,和R,(b)使用估计到的参数来更新V(值迭代),(c)根据跟新的V来重新得出,V的初值衔接上次的结果,18,2,总结,这里讨论的MDP是非确定的马尔科夫决策过程，也就是说回报函数和动作转换函数是有概率的。,在增强学习里有一个重要的概念是Q学习，本质是将与状态s有关的V(s)转换为与a有关的Q。,里面提到的Bellman等式，在算法导论中有Bellman-Ford动态规划算法，有值得探讨的收敛性的证明。,19,Thank you!,20,2,