最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • MDP的动态规划算法

    在之前的学习中我们已经得到了引入了价值函数,认识了贝尔曼方程,现在我们将要开始讨论如何使用优化算法来将找到最优策略。本文将要介绍的是基于模型的动态规划(DP)算法,该算法是MDP求解的最简单的一种算法,是我们继续学习更复杂算法的基础,所以我们有必要好好学习下它。


    一、什么是动态规划?

    动态规划(Dynamic Programming)是算法领域一种非常常见和经典的算法,简称DP,它常用来解决“多阶段决策问题”。首先我们从名字入手,“动态”的意思就是变化的状态,即将如何决策这样的抽象问题定义为一个个的数据状态,这些状态是会随着问题的规模变化而变化的;“规划”在这里更加接近的意思是表格,就是把变化的状态放到一起形成一个表格,随着问题的推进,表格会不断的更新,即动态规划使用表格来存储中间结果。

    动态规划的核心思想就是利用各个阶段的递推关系,逐个确定每个阶段的最优决策,并最终得到原问题的最优决策。

    使用动态规划解决问题需要具备两个条件:

    1. 一个复杂问题的最优解由数个小问题的最优解构成,可以通过寻找子问题的最优解来得到复杂问题的最优解;
    2. 子问题在复杂问题内重复出现,使得子问题的解可以被存储起来重复利用。

    而我们通过将强化学习问题归纳为MDP问题,就具备了以上两个属性:

    1. Bellman方程把问题递归为求解子问题;
    2. 价值函数就相当于存储了一些可以复用子问题的解。

    不过使用动态规划来解决MDP是建立在我们知道MDP环境的模型的基础上,即在已知状态行为空间、状态转换的概率矩阵和奖励等,所以它这是一种基于模型的优化算法,在实际的强化学习问题中并不常见,不过依旧具有学习的必要性。

    二、策略评估和策略改进

    之前我们已经得到了价值函数的写法,这表明者我们实际已经掌握了进行策略评估的方法,即给定一个策略,我们可以知道它在任意一个状态的好坏程度。

    1.策略评估(Policy Evaluation)

    策略评估就是评估一个策略的好坏,在已知MDP模型的情况下,我们可以通过计算任意一个策略的状态值函数,这也叫做预测(Prediction):

    从上述这个式子可以看出,当前状态的价值依赖于下一个状态的价值,那么如何计算它呢?

    这里我们可以使用高斯-赛德尔迭代算法来求解,简单来说就是反向迭代应用贝尔曼期望方程:

    先在初始时刻k使用随机策略给所有状态的价值一个默认初始值,然后在下一时刻k+1通过下面的式子进行迭代求解,可以证明,只要迭代的次数足够多,最终一定可以得到一个收敛的解。

    需要指出的是,这种反向迭代是一种同步反向迭代,简单来说就是第k+1次的s的价值全部由第k次的下一所有状态

    来计算。

    具体做法就是将第k次迭代的各状态值函数[Vk(s1),Vk(s2),Vk(s3)..]保存在一个数组中,第k+1次的Vπ(s)采用第k次的Vπ(s’)来计算,并将结果保存在第二个数组中。

    与之相对应的就是异步反向迭代,即在第k次迭代使用当次迭代的状态价值来更新状态价值。

    即仅用一个数组保存各状态值函数,每当得到一个新值,就将旧的值覆盖,形如[Vk+1(s1),Vk+1(s2),Vk(s3)..],第k+1次迭代的Vπ(s)可能用到第k+1次迭代得到的Vπ(s’)。

    通常情况下,我们采用异步反向迭代更新数据,因为它及时利用了新值,能更快的收敛。整个策略估计算法如下图所示:

    2.策略改进(Policy Improvement)

    我们已经知道如何评价一个策略的好坏,那接下就可以根据策略的好坏来选择一个最好的策略。

    这其实就是策略改进,如何做到策略改进呢?

    每到一个状态,我们就想想需不需要改变一下策略,这样可能会使回报更大,其实就是选择一个

    然后在遵循策略

    我们可以使用动作价值函数来求:

    然后我们选择贪婪的方式来提升我们的策略,即选择使用那个能使动作值函数最大的动作:

    三、策略迭代和值迭代

    1.策略迭代(Policy Iteration)

    说完了策略评估和策略提升,策略迭代就简单了,就是反复使用策略评估和策略提升,最后会收敛到最优策略。

    其通用的算法流程如下:

    2.值迭代(Value Iteration)

    策略迭代有一个缺点,就是在得到最优策略前进行的每一步迭代都分为两个独立的步骤,一是策略评估,二是进行策略改进。当状态空间很大的时候策略评估的步骤将会非常耗费时间,而每次想要进行策略改进都必须要等策略评估结束才能进行。

    所以我们提出了一种值迭代的方式,简单说就是直接将贝尔曼最优化方程拿来迭代计算的,这一点是不同于策略迭代的。

    贝尔曼最优化方程如下:

    我们先来看一下值迭代的算法流程。

    我们继续看下策略迭代和值迭代的区别:

    • 在策略迭代中
      • 第一步 策略评估:一直迭代至收敛,获得准确的V(s)
      • 第二步 策略改进:根据准确的V(s),求解最好的Action
      • 在值迭代中
        • 第一步 策略评估:迭代只做一步,获得不太准确的V(s)
        • 第二步 策略改建:根据不太准确的V(s),求解最好的Action
      • 值迭代可以看做是一种简化的策略迭代,这两种迭代方式都是属于Model-based的强化学习方法,即假设我们知道Agent采取动作后带来的Reward和新状态等,这种方式的特点就是不需要直接的参与强化学习任务,根据状态转移矩阵等信息就可以计算出最优策略,这种方式只适合于标准的已知模型的有限MDP问题。

      • 两者如何选择呢?

      • 一般来说,策略迭代的收敛速度更快一些,在状态空间较小时,最好选用策略迭代方法;当状态空间较大时,值迭代的计算量更小一些。

      • 总结

      • 本文主要讲解了基于模型的有限MDP问题的策略迭代方法,它运用的就是动态规划的算法思想,下一步我们打算参考几篇博客的实践代码来更加深入的总结有限MDP问题的策略迭代方法。

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » MDP的动态规划算法

    发表评论

    • 52会员总数(位)
    • 307资源总数(个)
    • 40本周发布(个)
    • 3 今日发布(个)
    • 330稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情