强化学习读书笔记（4）| 动态规划（Dynamic Programming）

动态规划（DP）是指可以用于在给定完整的环境模型作为马尔可夫决策过程（MDP）的情况下计算最优策略的算法集合。DP的核心思想就是使用value function作为依据，指导policies的搜索过程。上一次我们讨论到，一旦找到满足Bellman最优方程的最优值函数v*或q* 我们就可以获得最优策略，而DP算法做的事情就是把这些bellman functions转变成优化value functions近似值的更新规则。

回顾一下Bellman最优性方程：

策略评估

Policy Evaluation

首先，我们考虑如何计算任意策略的value function，这称为策略评估，也称为预测问题。

π(a|s)表示在policy为π，状态为s的情况下，action为a的概率。如果可以完全知道环境的动态，那么对每个状态s都可以列出一条上式的方程，联立即可解出vπ(s)。此外，我们也可以使用迭代法求解。首先，随机在每个状态上给定一个初始值函数v0(s)，然后按照如下的迭代进行：

随着迭代的进行，最终vk可以收敛到vπ。此算法被称为迭代策略评估(Iterative Policy Evaluation) 。为了从vk得到后续的vk+1 , 迭代策略评估针对每个状态s进行相同的操作如下：把当前状态s的value更新成一个新的value，这个新的value是由之后一个状态的旧的value和瞬时期望奖励，沿着所有可能的状态转移概率求和得到。我们把这个迭代操作叫做预期更新（expected update）。这个算法中的每一轮迭代操作都反向把所有状态的value值都推算（更新）一次，最后产生新的下一个vk+1。在DP算法中完成的所有更新都称为预期更新，因为它们基于对所有可能的下一个状态的期望而不是对下一个样本状态的期望。

想要写一个描述iterative policy evaluation算法的程序，那么应该有两个数组，其中一个保存vk(s)，另一个保存vk+1(s)。这样的话，新的value就可以在不改变旧value值的情况下被一个个计算出来。当然只使用一个数组更容易，在这里我们介绍了“in place”，即某个状态更新后的value就会实时的覆盖掉旧的value。好处是收敛速度相对快，但对于in place方法，状态被涉及到的顺序对收敛速度有着很大的影响。伪代码如下图：

策略改良

Policy Improvement

我们之所以要在某个policy下计算value function，是因为我们想要评估policy的好坏。假定我们已经确定了某一个policy下的value function。那么对于一些状态s，我们想要进一步知道是不是可以改变一下policy来选择另外一个和当前policy的决定不一样的动作，一个方法就是在当前s下选择你想选的a，然后继续按照已有的policy走下去。这时的value迭代公式如下:

这里的关键点就在于上式和vπ(s)的大小比较。如果上式比vπ(s)大，那么就是说在状态为s的时候选择a，然后继续按照policy走下去，比一直按照policy 走下去好，那么当我每次遇到状态s的时候，最好还是选择a。这就是策略改良(Policy Improvement) 的方法，在状态s下，如果每个行为都固定地指向唯一的下一个状态s′，那么基于贪心算法，直接选择v(s′)最大的行为即可。更一般地，如果每个行为都符合一个概率分布到下一个状态St+1，得到奖励Rt+1，那么也基于贪心算法，选择一个期望最大的行为作为策略即可。它的数学描述如下：

假设贪心策略和原有的policy一样好，也就是满足下式：

那么，这个方程看起来和bellman 最优性等式是一模一样的，也就是说原有的policy一定是最优policy。换句话说，policy improvment一定会给我们一个更好的policy，除非我们当前的policy已经是最优的了。

策略迭代

Policy Iteration

首先随机给出一个策略π0，然后进行policy evaluation得到一组value function vπ0(s)，再policy improvement得到一个更优的策略，反复迭代即可使策略越来越优，趋向于最优策略，如下图所示：

其中带有E的箭头表示policy evaluation，带有I的箭头表示policy improvement。此过程保证每个策略都是对前一项策略的严格改进（除非已经是最优的）。由于有限马尔可夫过程的policy是有限的，那么这个过程一定会在有限的迭代次数后收敛于最优的policy。此过程称为策略迭代，伪代码如下：

值迭代

Value Iteration

policy iteration算法的一个缺点是其迭代过程每次都包含一次policy evaluation，而这个policy evalution过程本身就是一遍遍的迭代。那么，我们能不能在中间就停止evaluation过程以加快收敛速度呢？我们可以通过某些方式来缩短evaluation的过程，同时又不会损失收敛性。其中一个特别的方式就是当所有状态都遍历一遍后，停止evaluation过程。这个算法就叫做value iteration。过程如下：

另一种理解value iteration的方法是参考Bellman最优性方程。通过将Bellman最优性方程转化为更新规则，可以获得值迭代。值迭代更新与策略评估更新相似，不同之处在于它要求所有行动最大化。value iteration的伪代码如下：

实例：Jack’s Car Rental

Jack有两个租车点，1号租车点和2号租车点，每个租车点最多可以停放20辆车。Jack每租车出一辆车可以获利10美金，每天租出去的车与收回的车的数量服从泊松分布。每天夜里，Jack可以在两个租车点间进行车辆调配，每晚最多调配5辆车，且每辆车花费2美金。我们假设在每个位置租车和回收的汽车数量是泊松随机变量，即数量为n的概率是，其中是期望数量。假设1号租车点租车数量服从λ=3的泊松分布，回收数量λ=3。二号租车点的租车数量和回收数量的λ分别为4和2。问使用什么样的调配策略可以使得收益最优化？

1、定义初始值及泊松分布

2、计算expected return

3、策略迭代并可视化

结果：

下面这幅图表示出了策略迭代的过程，直到第5次迭代，动作策略最终稳定为最优策略。图中，横轴表示2号租车点的车辆数，纵轴表示1号租车点的车辆数，图上的颜色由蓝到绿到黄表示了车辆调配的策略，正负号分别表示从1号调出车辆到2号，从2号调出车辆到1号。

小结

本次我们讨论了用以解决MDP类问题的动态规划算法的基本概念。Policy evaluation指的是按照给定policy进行value function的迭代计算；policy improvement指的是按照当前的value function进行policy的改进。把这两部分合并在一个过程里，我们得到了policy iteration和value iteration。它俩之中任何一个都可以高效解决finite MDP问题。经典DP算法对整个状态集进行遍历，对每一个状态进行“反向更新”（full backup）计算。每一次backup依据所有可能的后续状态和转移概率来更新状态的value。Full backup过程和贝尔曼方程很像：只不过是把贝尔曼方程转化成了赋值规则。当backup计算不再变化时，说明这个时候的values已经收敛到可以满足贝尔曼方程了。最后，我们注意到DP算法的最后一个重要性质：它们都在其他estimates的基础上更新某个estimates，我们把这种思想叫做：bootstrapping。下一次我们会讨论既不需要model也不需要bootstrapping的算法。

参考资料：

[1]R.Sutton et al. Reinforcement learning:An introduction,1998

[2]https://zhuanlan.zhihu.com/p/27659382

[3]https://www.cnblogs.com/Jinyublog/p/9319484.html