【强化学习】第二篇--基于模型的动态规划法
作者：王小草
笔记时间：2019年1月21日
1 价值函数的计算困难
1.1 最优值函数的递归定义
先来回忆一下最优状态值函数和最优状态-行为值函数。
-
最优状态价值函数：考虑这个状态下，可能发生的所有后续动作，并且挑最好的动作来执行的情况下，这个状态的价值。
-
最优状态-动作值函数：在这个状态下执行了一个特定的动作，并且该动作的后续状态总能选取最好的动作来执行，所得到的长期价值
以上两个价值函数，对应马尔科夫过程中的两个概率转移矩阵：状态-动作转移和动作-状态转移。
状态-动作转移是指在一个状态下有多个动作，也就是策略，每个动作有一个概率，所有动作相加概率为1，这个过程对应状态价值函数，其中最优的动作带来的价值就是最优状态价值。
动作-状态概率矩阵是指在做了某个动作a之后，下一个状态是不确定的，有多重可能，会有状态s转到状态s’的概率（比如给花浇水这个动作，有0.9的可能它会到茁壮成长的状态，0.1的可能还是会到死掉的状态），这个过程对应的是状态-动作值函数。
1.2 价值函数的计算困难
用bellman方程来直接求价值函数是比较困难的。
bellman方程：
忽略策略的随机性，即π=1，bellman方程可简化为：
对V求解：
以上求解，复杂度为O(n^3),真实场景中，P和R规模都太大，很难直接求解.
1.3 迭代计算价值函数
直接使用bellman方程求解价值函数显得不现实了，于是需要使用其他更优的方法去求解：
-
动态规划：已知环境P和R，对每步进行迭代（实际应用中很少使用动态规划来解决大规模强化学习问题）
-
Monte Carlo法：没有经验学习，但必须有终止任务，任务结束后对所有回报进行平均。
-
时序差分法：没有环境模型，根据经验学习。每步进行迭代，不需要等任务完成。
本文先对动态规划法进行价值函数的计算进行详细讲述。在第三篇，和第四篇，会分别对蒙特卡洛和时序差分法做详细介绍。
2 动态规划法
-
思想
把复杂的问题分阶段进行简化，迭代进行中，每次迭代过程中只保留之前的两个状态，就可以推导出新的状态，而不需要保留全部子状态，实现了时间和空间上的最优化。动态是指该问题的事件序列部分；规划指去优化一个计划，即优化一个策略。 -
性质
- 最优子结构：保证问题能够使用最优性准则，从而问题的最优解可以分解为子问题最优。
- 重叠子问题：子问题重复出现多次，因而我们可以缓存并重用子问题的解
-
步骤
- （1）将问题分为子问题
- （2）求解子问题
- （3）合并子问题的解
3 动态规划求解MDP问题
MDP满足动态规划的性质：
（1）贝尔曼方程给出了问题的迭代分解
（2）值函数保存和重用问题的解
因此，可以用动态规划方法来求解MDP问题。
强化学习的目标是找到最优策略，即MDP的最优解，要求解这个最优策略一般会分成两个步骤：
（1）预测：给定策略，评估相应的状态价值函数和状态-行为价值函数
（2）控制：状态价值函数和状态-行为价值函数求出后，求得当前状态对应的最优动作
预测与控制两个步骤都可以通过动态规划方法来求解得到。
动态规划法中有2个方法可以求解马尔科夫过程的最优解：策略迭代与价值迭代
3.1 策略迭代
现在来看看预测这一步具体是怎么走的。
首先要依赖的仍然是bellman期望方程：
用上一轮计算得到的状态价值来迭代求当前轮的状态价值，反复迭代后直到状态价值收敛。
用一个具体的例子来描述这个过程。
3.1.1 策略迭代例子
问题描述：
有这样一个格子：
- 状态空间S:是每个格子，用s1-s14标注，其中灰色的s1,s14是终止状态
- 行为空间A:对于任意非终止状态可以有走向东西南北四个行为
- 转移概率P:任意师徒离开格子世界的动作其位置将不会发生改变，并且这里假设在某个状态下，做出了某个动作后，会100%到达动作指向的状态，即确定性行为。
- 即时奖励R:任何在非终止状态得到的即时奖励都为-1，进入终止状态奖励为0
- 折扣因子γ：1
- 当前策略π:在任意非终止状态下有均等的几率采取任意移动方向
现在给出问题：在该方格世界中，给定π策略下，求状态价值函数，即该方格世界里每一个状态的价值。
求解过程：
k=0,初始情况，所有状态价值=0， 无法得到比随机策略更好的策略
第1次迭代
基于bellman方程，根据k=0的状态价值，计算当前k=1时的状态价值，
下图中给出了一个计算例子，以及所有状态价值的更新方格：
第2次迭代
继续用同样的方法更新状态价值，有了新的状态价值，就能得到新的最优动作
以此类推，一直迭代：
直到最终收敛，得到了最优状态价值，和最优动作
3.1.2 策略迭代原理
以上，通过算法构建值函数来评估策略，然后利用这些值函数，寻找新的，改进的策略的过程叫做策略迭代。总结起来是分成两部：
（1）第一步，任意假设一个策略π，使用这个策略迭代价值函数直到收敛
最后得到的状态价值，就是最优策略π所能得到的最优价值函数了，而这其实是对策略的一种评估。
（2）第二步，重新审视每个状态所有可能的行动action，优化策略π， 看看有没有更好的action可以提到老的action
策略迭代到最后会的大量每个状态应有的最佳策略。画成图可以如下：
也可以如下：
总结两大步骤如下：
3.1.3 改进的策略迭代
有时候不需要持续迭代至最优价值函数，可以设置一些条件提前终止迭代，如
- 设定一个Ɛ值，比较两次迭代的价值函数的平方差
- 直接设置迭代次数
- 每迭代一次，就更新一次策略，下一次迭代用新的策略去迭代价值函数
3.1.4 策略迭代的伪代码
3.2 价值迭代
先回顾一下最优价值函数，
-
最优状态值函数：是从所有策略产生的状态价值函数中，选取使状态s价值最大的函数
用bellman最优公式表示： -
最优状态-行为值函数：所有策略产生的行为价值函数中，选取使状态行为对< s,a >价值最大的函数
用bellman最优公式表示：
3.2.1 价值迭代的过程
- 首先，初始化所有状态V(s)
- step1：找到最优的价值函数
- 对每一个当前状态s,对每一个动作a，都计算采取这个动作后到达下一个状态的期望价值
- 将期望价值最大的那个动作的价值函数作为当前状态的价值V(s)
- 循环以上2步，直到价值函数收敛，得到最优的价值函数
- step2：策略制定
- 利用step1得到的最优价值函数，和状态转移概率，计算每个状态应该采取的最优动作（注意，这个最优动作是确定性的）
3.2.2 价值迭代伪代码
3.2.3 值迭代示例
仍然是格子世界，终止状态是灰色格子，其reward=0,其余格子的reward=-1
首先对A来说，有3个方向的走法，但是向左走的reward最大，即V(s)最大，因此第一次迭代它已经有了最大值。
对于B，第一次迭代中，向左向右都是一样的，但是在第二次迭代中，两次向左就可以达到最大值。
以此类推，如下图般可以通过迭代计算得到每个状态下的最优状态值了：
3.3 策略迭代和值迭代的异同
先把两个的伪代码摆在一起对照：
- 策略迭代:使用bellman方程来更新每个状态下的value，收敛得到策略下的value期望值；再通过value值来更新策略。
- 值迭代:使用bellman最优方程来更新每个状态下的value，收敛得到当前状态下的最优value值，一旦收敛，那么最优的policy也得到了。
注意，在求状态值的时候，策略迭代求的是期望value, 而值迭代求的是最大value
- 当状态空间较小时， 最好选用策略迭代；当状态空间较大时，选用之迭代的计算量更小。
4 异步动态规划
4.1 inplace动态规划
不对上一周期的value进行备份，直接使用这一周期的value
4.2 prioritised sweeoing
计算优化目标值和现实值之差（Bellmanerror），对多个S计算后排序，差值大的在前，依次优化对应的s的value。
4.3 real-time动态规划
应该可以翻译为实时动态规划，但是real-time 实际上指的是real time step，意思是真正经历的时间步，也就是真正经历的S，只更新经历过的S
5 动态规划的不足
- 必须知道状态转移概率才能进行最优策略的计算，实际场景中无法时间
- DP的推演是整个树状散开，属于full-width backup
- 对于每一次backup来说，所有后继的状态和动作都要被考虑在内，并且需要一直的转移矩阵和奖励函数，面临维数灾难问题
参考资料：
小象学院强化学习课程
https://blog.csdn.net/u012151283/article/details/54926888
https://blog.csdn.net/songrotek/article/details/51378582
https://blog.csdn.net/panglinzhuo/article/details/77752574 https://blog.csdn.net/liweibin1994/article/details/79093453
https://blog.csdn.net/u013745804/article/details/78218140