马尔可夫决策

会计学1马尔可夫决策马尔可夫决策2022-5-12设计一个回报函数设计一个回报函数，如果，如果learning agent在决定一步后，获在决定一步后，获得了较好的结果，那么我们给得了较好的结果，那么我们给agent一些回报（比如回报函数结一些回报（比如回报函数结果为正），若得到较差的结果，果为正），若得到较差的结果，那么回报函数为负。比如，四足那么回报函数为负。比如，四足机器人，如果他向前走了一步（机器人，如果他向前走了一步（接近目标），那么回报函数为正接近目标），那么回报函数为正，后退为负。如果我们能够对每，后退为负。如果我们能够对每一步进行评价，得到相应的回报一步进行评价，得到相应的回报函数，那么就好办了，我们只需函数，那么就好办了，我们只需要找到一条回报值最大的路径（要找到一条回报值最大的路径（每步的回报之和最大），就认为每步的回报之和最大），就认为是最佳的路径。是最佳的路径。第1页/共20页2022-5-12马尔可夫决策过程（MDP,Markov decision processes）是基于马尔可夫过程理论的随机动态系统的最优决策过程。它是马尔可夫过程与确定性的动态规划相结合的产物，又称马尔可夫型随机动态规划。研究一类可周期地或连续地进行观察的随机动态系统的最优化问题。在各个时刻根据观察到的状态，从它的马尔可夫决策相关书籍允许决策（控制、行动、措施等） 集合中选用一个决策而决定了系统下次的转移规律与相应的运行效果。并假设这两者都不依赖于系统过去的历史。在各个时刻选取决策的目的，是使系统运行的全过 程达到某种最优运行效果，即选取控制（影响）系统发展的最优策略。第2页/共20页2022-5-12S中一个状态到另一个状态的转变，需要A来参与。Psa表示在当前sS状态下，经过aA作用后，会转移到的其它状态的概率分布情况第3页/共20页2022-5-12+1-11234321S:11 statesA=N,S,W,E PSN(s)P(3,1)N(3,2)=0.8P(3,1)N(4,1)=0.1P(3,1)N(2,1)=0.1RR(4,3)=+1R(4,2)=-1R(s)=-0.02（S,A,Psa,，R）第4页/共20页2022-5-12循环S0S2S1S3a0a1a2. . . . . .R(S0)R(S1)R(S2)R(S3). . . . . .+R(S0)R(S1)2R(S2)3R(S3). . . . . . 0,1)+目标：目标：ER(S0)R(S1)2R(S2)3R(S3)+. . .+第5页/共20页2022-5-12V（s）= ER(S0)+R(S1)+2R(S2)+3R(S3)+. . . | s0=s , 值函数是回报的加权和期望，给定也就给定了一条未来的行动方案，这个行动方案会经过一个个状态，而到达每个状态都会有一定回报值，距离当前状态越近的其它状态对方案的影响越大，权重越高。第6页/共20页2022-5-12V（s）= ER(S0)+R(S1)+2R(S2)+3R(S3)+. . . V（s1）S)(s s s)()(VssVPRss）（）（下一个状态值函数的期望值然而我们需要注意的是：给定给定后，在给定状态后，在给定状态s下，下，a是唯一的，但是唯一的，但AS可能不是多到一的映射可能不是多到一的映射 立即回报= R(S0)+（ER(S1)+2R(S2)+3R(S3)+. . . ）= R(S0)+V（s）(s: 下一个状态)第7页/共20页2022-5-12S)(sss)()(VssVPRss）（）（)1 , 2(1 . 0)1 , 4(1 . 0)2 , 3(8 . 0 )1 , 3(R)1 , 3(VVVV(3,1)(3,2)(4,1)(2,1)0.80.10.1.|S|个方程，个方程，|S|个未知数个未知数第8页/共20页2022-5-12+1-112343210.520.330.37+1-0.09-0.82-1-0.88 -0.83-0.85-1.001234321对于给定的策略，我们可以写下这一策略的价值函数这是一个策略，但这不是一个伟大的策略V（策略的价值函数）第9页/共20页2022-5-12S)(s s s)()(VssVPRss）（）（目的：找到一个当前状态找到一个当前状态s下，最优的行动策略下，最优的行动策略。定义最优的V*如下：）（s)(Vmax*sVS*sA* s s)()(maxVsaaVPRss）（）（Bellman等式：（2） 第二项是一个就决定了每个状态s的下一步动作，执行a后，s按概率分布的回报概率和的期望第10页/共20页2022-5-12Ss*A*) () ( maxargssVsPsaa）（*：实际上是最佳策略，最大化我们的收益。 选择最优的*，也就确定了每个状态s的下一步动作a。（3）注意： 如果我们能够求得每一个如果我们能够求得每一个s下最优的下最优的a，那么从全局来看，那么从全局来看，SA的映射即可生成，并且是最优映射的映射即可生成，并且是最优映射*。*针对全局的针对全局的s，确定了每一个确定了每一个s的下一个行动的下一个行动a,不会因为初始状态不会因为初始状态s选取的不同选取的不同而不同。而不同。第11页/共20页2022-5-12A) () (max)(: )(ssaasVsPsRsVi）同步迭代法初始状态所有的v(s)都为0.对s都计算新的V(s)=R(s)+0=R(s)。在计算每一个状态时，得到V(s)后，先存下来，不立即更新。待所有s的新值v(s)都计算完后，再统一更新。ii)异步迭代法对于每一个状态s,得到新的v(s)后，不存储，直接更新。V(s)V*(s)第12页/共20页2022-5-120.860.900.93+10.820.69-10.780.750.710.711234321=0.9974. 071. 0*1 . 069. 0*1 . 075. 0*8 . 0) () (:*ssasVsPW676. 071. 0*1 . 075. 0*1 . 069. 0*8 . 0) () (:*ssasVsPNSs*A*) () ( maxargssVsPsaa）（第13页/共20页2022-5-12Aa) () (maxarg: )(ssasVsPsV可以通过之前的bellmand等式求得这一步会求出所有状态的V（s）根据（a）歩的结果挑选出当前状态s下最优的a,然后对a做更新。第14页/共20页2022-5-12S10S12S11S13a10a11a12. . . . . .S20S22S21S23a20a21a22. . . . . .aij是sij状态时要执行的动作12.第15页/共20页2022-5-12（）sstateinaactiontookwetimesstogotandsstateinaactionweotimessPsa#okt#) (（从s状态执行动作a后到达s的次数）（在状态s时，执行a的次数）如果分母为0，则令Psa(s)=1/|s|第16页/共20页2022-5-12V的初值衔接上次的结果第17页/共20页2022-5-12第18页/共20页Thank you!第19页/共20页