上海做企业网站浙江网站建设公司名单

上海做企业网站,浙江网站建设公司名单,专业网站制作企业,西安网站seo收费【强化学习】第四章#xff1a;动态规划(DP) 说明#xff1a;学习本篇时一定一定要认真学完 https://blog.csdn.net/friday1203/article/details/155533020?spm1001.2014.3001.5501 #xff0c;因为动态规划就是为了求解MDP问题的。所以你首先要非常清晰什么是MDP、MDP框架…【强化学习】第四章动态规划(DP)说明学习本篇时一定一定要认真学完 https://blog.csdn.net/friday1203/article/details/155533020?spm1001.2014.3001.5501 因为动态规划就是为了求解MDP问题的。所以你首先要非常清晰什么是MDP、MDP框架、贝尔曼期望方程、状态价值、动作价值等概念和它们之间的逻辑。其实在第三章的最后我已经完整的展示了学生例子的解是如何计算的。但是那种是显式地列出联立方程并直接求解的方法这种方法只对小问题有效。在实际问题中当状态和行动模式的数量非常多时联立很多方程就不太可行此时就需要动态规划法(dynamic programming, DP)来求解。本章介绍动态规划法。类似梯度下降算法就是为了求解损失函数的最小值一样动态规划法也只是求解价值函数的一种方法所以本篇重点讲怎么用动态规划求解价值函数而非动态规划法背后的理论和数学推导。一、动态规划简介1、什么是动态规划动态规划(Dynamic Programming, DP)是一类优化算法。动态规划将待求解问题分解成若干子问题先求解子问题然后从这些子问题的解得到目标问题的解。2、动态规划的核心特点1最优子结构————子问题的最优解是可以得到的。如果子问题都没有最优解那就别谈下文了。2重复子问题————子问题的解决方案可以存储和重用。3、动态规划与强化学习之间的关系在完备的马尔可夫决策过程中DP可用于计算价值函数有了价值函数就可以得到动作价值有了动作价值就可以得到智能体的策略。但是强化学习的最终目标是找到最优策略所以基于动态规划的强化学习可以分两种方法寻找最优策略策略迭代(policy Iteration)和价值迭代(Value Iteration)。下面针对这两种方法分别来讲。二、策略迭代(Policy Iteration)1、策略评估(Policy Evaluation)前后说过动态规划是实现对价值函数的评估的一种方法。那具体是如何评估的这里我先不绕理论和罗列数学推导我先用上一篇中的学生例子为例给大家展示一下是如何评估价值函数让大家先有一个直观的认识就是这么简单先初始化一组状态价值然后根据贝尔曼期望方程一轮轮的迭代最后就能收敛到策略π下的状态价值。策略π下的状态价值是指这组价值可以使系统在策略π下满足贝尔曼期望方程。或者说这组价值就是贝尔曼期望方程组的解。这就是动态规划。简单理解就是通过迭代求出状态价值。这个结果和silver课件中的结果是一样的说明迭代结果是正确的。很多资料是这样写的DP方法是从贝尔曼期望方程衍生出来的其思路是将贝尔曼期望方程变形为更新式用第k次的状态价值函数更新第k1次迭代的状态价值函数这个过程叫自举法bootstrapping方法也有说这是高斯-赛德尔迭代算法的求解过程。anyway不管怎样它就是一种求解线性方程组的一种方法。我们只要知道对于系统状态和行动模型的数量较大一些的场景这种方法是可以高效求解的即可。同步更新和异步更新上面求解状态价值的过程在算法的工程实现上叫同步更新(同步DP)意思就是迭代一轮就更新一次全部的状态价值。下一轮迭代时就依据这次的结果重新更新全部的状态价值。由于同步更新效率有点低所以在工程实现上还有一种更新方式叫就地更新也叫异步更新(异步DP)就是本轮迭代中只要算出了某个状态价值就地就直接更新了这个状态的价值当其他方程中用到这个状态的价值值就采用本轮更新的值来计算。这就是就地更新就地更新效率会更高一些。Sutton强化学习书中用的就是就地更新。然而异步更新对状态的顺序比较敏感因为顺序不一样更新的结果当然会不一样喽。下面我也用代码展示一下异步DP在强化学习中上面的用DP求解状态价值的过程叫策略评估。silver课件中叫迭代策略评估算法。现在回看它就是一个求解价值函数Vπ的迭代过程嘛。有了Vπ就可以得到Qπ有了Qπ就知道了策略π我想这就是为什么叫策略评估吧又因为它是通过迭代实现的所以叫迭代策略评估算法吧。2、策略提升(Policy Improvement)然而强化学习的目的是找到最优策略π*所以还得进行策略提升(policy improvement)。策略提升有的地方叫策略控制(policy control)就是控制策略并将其调整为最优策略。有的地方叫策略改进。anyway不管怎么叫都是指如何寻找最优策略π*。而寻找最优策略π*也是通过迭代来实现的所以本方法叫策略迭代(policy Iteration)。第三章讲最优策略时我们知道对所有的s如果vπ1(s) vπ2(s) vπ3(s)...,那么策略π2就比策略π1好,策略π3就比策略π2好...。所以策略提升(策略控制、策略改进、策略迭代)就是通过当已知当前策略π的价值函数时在每个状态采用贪婪方法来对当前策略进行改进用数学语言就是公式中的argmax a表示从局部候选行动中选择最佳行动来更新策略这种更新策略的做法叫“贪婪化”就是只看眼前眼前最优的动作是什么那我下次就按这个动作来计算新一轮的状态价值在新一轮的状态价值中我再找当下眼前的最优动作计算新新轮的状态价值...如此循环直到策略不会再被改进(或更新)那么这个策略就是最优策略。这种方法得到的策略也被称为贪婪策略如下图所示至此我们就得到策略迭代的基本范式、计算公式、算法实现策略迭代算法(policy Iteration)包括策略评估和策略改进两个步骤。在策略评估中给定策略π1用高斯-赛德尔迭代算法迭代计算π1策略下每个状态的价值函数vπ1。由于策略π1一般都是初始化的随机策略所以由vπ1算得的qπ1也是随机动作此时根据贪婪策略找到当下最好的qπ1(就是argmax a)当下最好的qπ1又对应着新策略π2用高斯-赛德尔迭代算法迭代计算π2策略下每个状态的价值函数vπ2-qπ1-贪婪化选择最好的qπ1-策略π2-....如此循环下去就是一个策略收敛的过程。直到价值函数不变、策略不变这个策略就是最优策略π*。上述迭代过程一般都能收敛到最优策略。下面我用代码继续展示学生的例子直观理解如何用策略迭代法得到最优策略π [[0.5, 0.5], [0.5, 0.5], [0.5, 0.5], [0.5, 0.5]] #这是初始化的策略π fb0 #这是初始化的状态价值 c10 c20 c30 for policy in range(5): #迭代5次策略 for i in range(20): #每个策略下循环20次寻找状态价值 fb π[0][0]*-1 π[0][1]*0 π[0][0]*1*fb π[0][1]*1*c1 c1 π[1][0]*-1 π[1][1]*-2 π[1][0]*1*fb π[1][1]*1*c2 c2 π[2][0]*0 π[2][1]*-2 π[2][1]*1*c3 c3 π[3][0]*10 π[3][1]*1 π[3][1]*0.2*c1 π[3][1]*0.4*c2 π[3][1]*0.4*c3 print(第{}个策略下的状态价值: .format(policy1), fb, c1, c2, c3) #计算动作价值 fb_dofb -1 fb fb_quit c1 c1_dofb -1 fb c1_study -2 c2 c2_dosp 0 c2_study -2 c3 c3_dosp 10 c3_pub 1 (0.2*c1 0.4*c2 0.4*c3) print(第{}个策略下的动作价值.format(policy1),fb_dofb, fb_quit, c1_dofb, c1_study, c2_dosp, c2_study, c3_dosp, c3_pub) #贪婪化提升策略 π[0] ([1, 0] if fb_dofb fb_quit else [0, 1]) π[1] ([1, 0] if c1_dofb c1_study else [0, 1]) π[2] ([1, 0] if c2_dosp c2_study else [0, 1]) π[3] ([1, 0] if c3_dosp c3_pub else [0, 1]) print(第{}个策略是.format(policy1), π) print(--------------------)从上面的运行结果看其实只需要迭代2轮策略就已经找到最优策略了。下面我重新设置一组初始化条件看看能不能迭代到最优π [[0.2, 0.8], [0.1, 0.9], [0.3, 0.7], [0.1, 0.9]] #策略重新初始化 fb10 #状态价值也重新初始化 c19 c28 c39 for policy in range(5): #迭代5次策略 for i in range(20): #每个策略下循环20次寻找状态价值 fb π[0][0]*-1 π[0][1]*0 π[0][0]*1*fb π[0][1]*1*c1 c1 π[1][0]*-1 π[1][1]*-2 π[1][0]*1*fb π[1][1]*1*c2 c2 π[2][0]*0 π[2][1]*-2 π[2][1]*1*c3 c3 π[3][0]*10 π[3][1]*1 π[3][1]*0.2*c1 π[3][1]*0.4*c2 π[3][1]*0.4*c3 print(第{}个策略下的状态价值: .format(policy1), fb, c1, c2, c3) #计算动作价值 fb_dofb -1 fb fb_quit c1 c1_dofb -1 fb c1_study -2 c2 c2_dosp 0 c2_study -2 c3 c3_dosp 10 c3_pub 1 (0.2*c1 0.4*c2 0.4*c3) print(第{}个策略下的动作价值.format(policy1),fb_dofb, fb_quit, c1_dofb, c1_study, c2_dosp, c2_study, c3_dosp, c3_pub) #贪婪化改进策略 π[0] ([1, 0] if fb_dofb fb_quit else [0, 1]) π[1] ([1, 0] if c1_dofb c1_study else [0, 1]) π[2] ([1, 0] if c2_dosp c2_study else [0, 1]) π[3] ([1, 0] if c3_dosp c3_pub else [0, 1]) print(第{}个策略是.format(policy1), π) print(--------------------)同样只需要迭代2次状态价值、动作价值、策略三个指标就都迭代到最优了。也所以其实很多时候我们不需要状态价值函数已经收敛了才去贪婪化的提升策略很多时候我们只要观察策略已经不更新了就不用管价值函数是否也收敛直接就认为这个策略是当下的最优策略然后继续循环策略也是可以的。对照上面的代码就是内部的i循环(也就是策略评估)可以不用达到收敛也是可以开始贪婪化的提升策略的但是外部的policy循环是必须要达到收敛才能得到最优策略的。这样在工程上可以节省内部循环的计算量。三、价值迭代(Value Iteration)价值迭代可以看作是策略迭代的一种特殊情况因为价值迭代是直接用贝尔曼最优方程来求解最优策略的。因为能满足贝尔曼最优方程的策略一定是最优策略所以利用贝尔曼最优方程进行价值迭代时我们是可以不用管策略只迭代最优价值函数即可所以有时价值迭代的效率会比策略迭代高一些。至于如何实现价值迭代我这里就不重复写了详情见第三章 https://blog.csdn.net/friday1203/article/details/155533020?spm1001.2014.3001.5501 中的五-3贝尔曼最优方程的求解。动态规划基本就是这些内容了重点和难点还是在第三章需要对第三章的深刻理解这里只是数学上的求解技巧而已。最后再说一下本章的DP算法是传统的DP算法也就是只针对完备的MDP就是假设环境模型是完备的此外计算复杂度也比较高。所以本章的DP算法作用是有限的但我们还是得好好去学一下因为它提供了必要的基础就是给我们了一个完整的解决方案。所有此后的其他方法都是对DP的近似其他方法要么是降低了计算复杂度要么是减弱对环境模型完备性的假设。