Reinforcement Learning——DP
Dynamic Programming
动态规划是用来求解MDP的方法之一，动态的含义是问题具有时间或顺序特性，规划的含义是用程序来优化程序，也就是指优化策略。动态规划算法就是两种思想的结合，它把一个复杂的问题分割成许多小的问题，在解决了这些小问题之后原本复杂的问题就随之迎刃而解。在增强学习中，它主要是利用value function来搜索最优策略，利用Bellman方程作为更新规则来计算近似的期望value function。只要我们找到了最优的value function，就不难找到最优策略。
传统的动态规划算法具有局限性，一是因为其需要运行在环境模型完全已知的条件下，二是因为其冗长的计算量，针对以上不足，下一趴将介绍相关的改进算法。
本文主要包含以下三方面的内容：Policy Evaluation，Policy Iteration，Value Iteration。
一、Condition
能用DP解决的问题需要满足以下两个特性：
1.具有最优化结构（把一个问题分解成许多子问题，由子问题的最优解可得出整个问题的最优解，即化整为零）
2.满足重叠子问题（分解成的子问题是不断重复的）
MDP满足以上两种特性，因此可以用DP来求解。
二、Policy Evaluation
简单概括就是，在已知MDP和已知策略的情况下，根据策略不断地进行状态的转移，一直向前走（move on），然后计算这条路上能得到的奖励大小，这就是策略评估。计算value function时，需要用到上一篇博文中介绍的Bellman期望方程。
V1，V2，V3，V4，……，Vπ 是一串由任意初始状态V1（一般可取0）开始的序列，利用Bellman期望方程进行迭代计算，可以由V1得V2，由V2得V3，以此类推直到得到最终的Vπ值。这是一个同步备份的过程（课本中称之为full backup），也就是说每当进行一次迭代，就对序列中每个状态进行一次重新评估。而且当k→∞时，Vk将收敛至Vπ。
■ Example——gridworld
这是一个方格游戏，大小为4×4，角落里的两个阴影方格是终止状态。在每一个方格S={1,2,3,……，14}，可以采取四种行动，分别是A={up，down，right，left }，并且每移动一步获得-1大小的奖励，若移动超出边界则保持原地不动。
写出一些简单的状态转移概率p(s＇| s,a)：比如p(6|5,right)=1，p(10|5,right)=0，p(7|7,right)=1……在这个例子中取γ=1，并且每次采取等概率的随机策略，即向上，向下，向左，向右的概率π（a|s）均为0.25。开始时，所有的V都取0。以下是迭代计算过程：
1
我就取k从2到3的迭代过程进行演示说明：
-2.4=0.25*（-1-0）+0.25*（-1-1.7）+0.25*（-1-2）+0.25*（-1-2）
-2.9=0.25*（-1-1.7）+0.25*（-1-1.7）+0.25*（-1-2）+0.25*（-1-2）
-3.0=0.25*（-1-2）+0.25*（-1-2）+0.25*（-1-2）+0.25*（-1-2）
其主要思想是，在每一个方格里，我们可以向四个方向进行随机移动，每个方向概率为0.25，而每移动一步，就获得-1的奖励，将立即获得的奖励与移动至的方格原来的value直接相加（因为γ为1），按此方法对四个不同方向求期望，每个方格将得到自己新的value值，它衡量了从该方格到达终止状态需要花费的步骤数，这是左边这列网格的计算过程和意义。而右边这列网格能告诉我们往哪个方向走是一个较好的策略。刚开始的时候，还没有进行任何迭代计算，因此对于每一个网格来说，往四个方向中的任意一个方向走都是一样好的，在左边网格的value值指导下，我们在右边网格中不再作随机移动，而是变得贪婪起来，往value值大的方向进行移动。可以看到当k=3的时候，最优策略已经浮现。因此有时候不需要迭代到最终的收敛状态，就可以获得最优策略。
这就是一个典型的用value function一步一步构建policy的例子。
三、Policy Iteration
当我们已经有了一个初始的policy后，怎么做才能使这个初始策略变得越来越好呢？答案是不断地运行该过程进行策略的迭代，具体做法是，首先，对目前已知的policy计算value function，也就是上面这一趴介绍的policy evaluation；然后根据value function 来improve policy，一般采用贪婪算法，选取具有最大的value function的policy。在不断地进行这两个步骤（策略评估和策略改进）后，结果会收敛至最优策略。
将迭代过程用形象图形表示如下：
向上的箭头是策略评估过程，向下的箭头是策略改进过程。贪心算法的具体表现是在每一步都选择q为最大的action。通过这样的迭达可以解决一个MDP问题，找到最优策略。
四、Modified Policy Iteration
Modified Policy Iteration的基本思想是"提前停止"。从前面方格游戏的例子中我们可以看到在第三次策略迭代之后已经出现了最优策略，第4次及以后的每一次迭代都只是更新了value function，而没有对我们的策略信息有任何的帮助，因此这些迭代步骤基本是无用的，为了提前停止迭代过程，有以下两种简单的方法：
1. 引入停止条件
在每一次迭代过程中，观察用贝尔曼方程更新的value function的变化大小，当value function更新非常小时说明已经很接近最优了，也就是可以停止该迭代过程了。（该方法仍有可能做无用功）
2.设定迭代次数
通过观察，设定迭代次数k，当进行了k次迭代之后就直接停下。
五、Value Iteration
value function的迭代过程可以看作是一个后向感应的算法。假如我们已经知道了某个状态s'的最优解v*(s')，通过向前走一步看的方法可以构建一个树，把树叶节点（s'）的信息储存起来，最大化这一步行动中的reward，在树根处（s）就可以得到根的最优解。value iteration其实就是不断地用下面的公式更新value function，用回退的方式搜寻找出最优的路径。
将第k次迭代得到的vk(s')作为树叶节点的值储存起来，并且向前看一步，用贝尔曼最优方程计算下一次迭代得到的值vk+1(s)，不断从S’进行回溯，最终可以收敛到v*(s)。
■ Example——Shortest Path
图中的阴影格子表示目标状态，假设开始时所有状态的value都为0，经过一次value iteration之后所有状态同步更新为-1，-1是怎么来的呢？是对于任意一个格子，做以下计算max{-1+0，-1+0，-1+0，-1+0}=-1得到的value值。同样地，对每个格子的状态进行循环迭代运算：
max{-1+(-1)，-1+(-1)，-1+(-1)，-1+(-2)}=-2;
max{-2+(-2)，-1+(-2)，-1+(-2)，-1+(-3)}=-3;
………………
进行多次迭代之后可以得出最后一个方格中每个状态不同的value function，可以看出离终点状态越远的方格，value值越小，也就是路程最远，按value不断增大的方向移动就可以找到移动到目标位置的最优策略。
六、Policy Iteration和Value Iteration的区别
（1）policy iteration中构造的每一个value function都是某个policy的确定的vπ，而value iteration中的value function只是某种迭代过程中产生的中间值，它有可能不属于任何的policy，即value iteration过程中并不创建具体的policy。
（2）policy iteration 是利用贝尔曼期望方程不断循环计算迭代得到最优解；value iteration 是利用贝尔曼最优方程不断循环计算迭代得到最优解。
七、总结
本文介绍了如何用动态规划算法解决MDP，其中包含三项主要的内容：policy evaluation，policy iteration，value iteration。这三个算法采用不同的贝尔曼方程解决不同的问题：策略评估主要解决预测问题，就是根据已知的策略对未来表现作一个评价，具体的用value function的数量关系来表示。另外两个算法主要解决控制问题，策略迭代算法是指我们不仅要知道当前策略的未来表现如何，而且要通过贪婪算法实时地改进当前策略，尽可能获得多的reward，不断创建新的策略，在重复的评价和改进中使策略逐渐收敛到最优，从而解决MDP问题。而value iteration是通过自我循环迭代，由某个状态s'采用贝尔曼最优方程，采取最大化的措施找到optimal value function——v*。
表格对比如下：
总而言之，动态规划是一种解决MDP问题的方法，但是由于它进行同步备份，对于有很多state和action的问题，其复杂程度会非常大，往往引起维度灾难，因此之后会介绍其他改进方法。