马尔可夫决策

MarkovDecision马尔可夫决策第九组：史文祥曹海歌2019/12/15设计一个回报函数，如果learningagent在决定一步后，获得了较好的结果，那么我们给agent一些回报（比如回报函数结果为正），若得到较差的结果，那么回报函数为负。比如，四足机器人，如果他向前走了一步（接近目标），那么回报函数为正，后退为负。如果我们能够对每一步进行评价，得到相应的回报函数，那么就好办了，我们只需要找到一条回报值最大的路径（每步的回报之和最大），就认为是最佳的路径。2019/12/15马尔可夫决策过程（MDP,Markovdecisionprocesses）是基于马尔可夫过程理论的随机动态系统的最优决策过程。它是马尔可夫过程与确定性的动态规划相结合的产物，又称马尔可夫型随机动态规划。研究一类可周期地或连续地进行观察的随机动态系统的最优化问题。在各个时刻根据观察到的状态，从它的马尔可夫决策相关书籍允许决策（控制、行动、措施等）集合中选用一个决策而决定了系统下次的转移规律与相应的运行效果。并假设这两者都不依赖于系统过去的历史。在各个时刻选取决策的目的，是使系统运行的全过程达到某种最优运行效果，即选取控制（影响）系统发展的最优策略。2019/12/15MDP五元组（S,A,{Psa},γ，R）•S:状态集（states）•A:一组动作（actions）•Psa:状态转移概率•γ：阻尼系数（discountfactor）•R:回报函数（rewardfunction）S中一个状态到另一个状态的转变，需要A来参与。Psa表示在当前s∈S状态下，经过a∈A作用后，会转移到的其它状态的概率分布情况2019/12/15一个较小的MDP模型（机器人导航任务）[phone]•S:11states•A={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）2019/12/15MDP是如何工作的时间0，从状态S0出发...取出你在哪个地方atstateS0选择一个动作A0决定actiona0得到一个新状态S1~PS0a0循环S0S2S1S3a0a1a2......R(S0)R(S1)R(S2)R(S3)......+++R(S0)γR(S1)γ2R(S2)γ3R(S3)......γ∈[0,1)+++目标：E[R(S0)γR(S1)γ2R(S2)γ3R(S3)+...]+++2019/12/15Policy(策略)已经处于某个状态s时,我们会以一定的策略π来选择下一个动作a的执行，然后转换到另一个状态。π：S→Aa=π（s）值函数（valuefunction）Vπ（s）=E[R(S0)+γR(S1)+γ2R(S2)+γ3R(S3)+...|s0=s,π]值函数是回报的加权和期望，给定π也就给定了一条未来的行动方案，这个行动方案会经过一个个状态，而到达每个状态都会有一定回报值，距离当前状态越近的其它状态对方案的影响越大，权重越高。2019/12/15递推Vπ（s）=E[R(S0)+γR(S1)+γ2R(S2)+γ3R(S3)+...]Vπ（s1）下一个状态值函数的期望值然而我们需要注意的是：给定π后，在给定状态s下，a是唯一的，但A→S可能不是多到一的映射立即回报=R(S0)+γ（E[R(S1)+γ2R(S2)+γ3R(S3)+...]）=R(S0)+γVπ（s'）(s':下一个状态)2019/12/15给定一个固定的策略π，我们怎么解这个等式Vπ（s）=？(3,1)(3,2)(4,1)(2,1)0.80.10.1.....|S|个方程，|S|个未知数2019/12/15+1-112343210.520.330.37+1-0.09-0.82-1-0.88-0.83-0.85-1.001234321一个具体的例子对于给定的策略，我们可以写下这一策略的价值函数这是一个策略，但这不是一个伟大的策略Vπ（策略的价值函数）2019/12/15目的：找到一个当前状态s下，最优的行动策略π。定义最优的V*如下：Bellman等式：（2）第二项是一个π就决定了每个状态s的下一步动作，执行a后，s'按概率分布的回报概率和的期望2019/12/15•定义了最优的V*，我们再定义最优的策略π*：S→Aπ*：实际上是最佳策略，最大化我们的收益。选择最优的π*，也就确定了每个状态s的下一步动作a。（3）注意：如果我们能够求得每一个s下最优的a，那么从全局来看，S→A的映射即可生成，并且是最优映射π*。π*针对全局的s，确定了每一个s的下一个行动a,不会因为初始状态s选取的不同而不同。2019/12/15如何计算最优策略？（MDP是有限状态，有限动作时）•值迭代法1、将每一个s的V(s)初始化为02、循环直到收敛{对于每一个状态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)2019/12/15知道了V*(s)后，再用（3）求出相应的最优策略0.860.900.93+10.820.69-10.780.750.710.711234321γ=0.992019/12/15•策略迭代法（π→π*）1、随机指定一个S到A的映射π。2、循环直到收敛{（a）令V:=Vπ（b）对于每一个状态s,对π（s）做更新}V可以通过之前的bellmand等式求得这一步会求出所有状态的Vπ（s）根据（a）歩的结果挑选出当前状态s下最优的a,然后对a做更新。2019/12/15MDP中的参数估计•之前讨论的MDP中，状态转移概率Psa和回报函数R(s)是已知的。•实际中，我们需要从数据中估计出这些参数（S,A,γ已知）S10S12S11S13a10a11a12......S20S22S21S23a20a21a22......aij是sij状态时要执行的动作12...2019/12/15最大似然估计来估计状态转移概率（从s状态执行动作a后到达s'的次数）（在状态s时，执行a的次数）如果分母为0，则令Psa(s')=1/|s|2019/12/15将参数估计和值迭代结合起来（在不知道状态转移概率的情况下）•1、随机初始化π•2、循环直到收敛{(a)在样本上统计π中每个状态转移次数，更新Psa和R(b)使用估计到的参数来更新V(值迭代)(c)根据跟新的V来重新得出π}V的初值衔接上次的结果2019/12/15总结•这里讨论的MDP是非确定的马尔科夫决策过程，也就是说回报函数和动作转换函数是有概率的。•在增强学习里有一个重要的概念是Q学习，本质是将与状态s有关的V(s)转换为与a有关的Q。•里面提到的Bellman等式，在《算法导论》中有Bellman-Ford动态规划算法，有值得探讨的收敛性的证明。Thankyou!