4 马尔可夫决策过程-中 | 自动驾驶小白说

4.8 动态规划求解MDP

4.8.1 简介

动态规划（dynamic programming）是程序设计算法中非常重要的内容，其核心思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到目标问题的解。动态规划会保存已解决的子问题的答案，在求解目标问题的过程中，直接利用这些子问题的答案，避免重复计算。

基于动态规划求解MDP的方式主要有两种：一是策略迭代（policy iteration），二是价值迭代（value iteration）。其中，策略迭代由两部分组成：策略评估（policy evaluation）和策略提升（policy improvement）。具体来说，策略迭代中的策略评估使用贝尔曼期望方程来得到一个策略的状态价值函数，这是一个动态规划的过程；而价值迭代直接使用贝尔曼最优方程来进行动态规划，得到最终的最优状态价值。

🌟Note: 基于动态规划的这两种方法要求事先知道环境的状态转移函数和奖励函数，也就是需要知道整个马尔可夫决策过程。在这样一个白盒环境中，不需要通过智能体和环境的大量交互来学习，可以直接使用动态规划求解状态价值函数。但是，现实中的白盒环境很少，这也是动态规划算法的局限之处，我们无法将其运用到很多实际场景中。另外，策略迭代和价值迭代通常只适用于有限马尔可夫决策过程，即状态空间和动作空间是离散且有限的。

4.8.2 MDP问题-迷宫寻宝

在迷宫寻宝问题中，有一个5*5的棋盘，超级玛丽位于棋盘的左上角，其可以朝上、下、左、右四个方位移动，每次最多移动一格，记为一步；宝藏位于棋盘最下层的中间格子内，在游戏中玩家控制超级玛丽进行移动，超级玛丽找到宝藏则游戏结束(即超级玛丽和宝藏位于同一个方格)，游戏的目标就是让超级玛丽以最少的步数找到宝藏。

我们将上述问题转成MDP的形式，分别定义它的状态空间，动作空间，奖励集合，状态转移和折扣因子。

状态空间

宝藏的位置是固定不变的，因此这里只需要定义超级玛丽的状态，我们将其可移动的所有方格进行编码（见下图）：

动作空间

在任意一个状态，超级玛丽有4个动作：向上、向下、向左、向右，分别用0、1、2、3表示。

奖励集合

我们将转移到终点状态22（宝藏位置）获得的奖励为0，转移到其余状态获得的奖励均记为-1（见下图）：

状态转移

给定一个动作，当前状态以概率1转移到下一个状态，例如状态12，选择向上动作，只能转移到状态7，选择向下动作，只能转移到状态17。

若执行某一动作会使超级玛丽碰撞棋盘边缘，则保持当前状态不变，并获得-1的奖励，例如状态20，选择向左动作，将继续停留在状态20，并获得-1的奖励。

折扣因子

在此问题中，我们将折扣因子设为0.9

4.8.3 策略迭代算法

策略迭代是策略评估和策略提升不断循环交替，直到最后得到最优策略的过程。

策略评估

策略评估用来计算一个策略的状态价值函数，贝尔曼期望方程为：

其中，是策略在状态下采取动作的概率。可以看到，当知道奖励函数和状态转移函数时，我们可以根据下一个状态的价值来计算当前状态的价值。因此，根据动态规划的思想，可以把计算下一个可能状态的价值当成一个子问题，把计算当前状态的价值看作当前问题。在得知子问题的解后，就可以求解当前问题。更一般的，考虑所有的状态，就变成了用上一轮的状态价值函数来计算当前这一轮的状态价值函数，即：

我们可以选定任意初始值，根据贝尔曼期望方程，可以得知是以上更新公式的一个不动点（fixed point）。并且我们可以证明时，序列会收敛到，所以可以据此来计算得到一个策略的状态价值函数。可以看到，由于需要不断做贝尔曼期望方程迭代，策略评估其实会耗费很大的计算代价。在实际的实现过程中，如果某一轮的值非常小，可以提前结束策略评估。这样做可以提升效率，并且得到的价值也非常接近真实的价值。

策略提升

使用策略评估计算得到当前策略的状态价值函数之后，我们可以据此来改进该策略。假设此时对于策略，我们已经知道其价值为，也就是知道了在策略下从每一个状态出发最终得到的期望回报。此时我们需要考虑如何改变策略来获得在状态下更高的期望回报呢？假设智能体在状态下采取动作，之后的动作依旧遵循策略，此时得到的期望回报其实就是动作价值。如果我们有，则说明在状态下采取动作会比原来的策略得到更高的期望回报。以上假设只是针对一个状态，如果存在一个确定性策略，在任意一个状态下，都满足：

于是在任意状态下，我们都存在以下不等式：

这个过程就是策略提升定理（policy improvement theorem）。于是我们可以直接贪心地在每个状态选择价值最大的动作，即：

可以清楚的看到构造贪心策略满足策略提升定理，所以策略能够比策略更好或者一样好。这个根据贪心法选取动作从而得到新的策略的过程称为策略提升。当策略提升之后得到的策略和之前的策略一样时，说明策略迭代达到了收敛，此时和就是最优策略。

策略提升定理的证明通过以下推导过程可以证明，使用上述提升公式得到的新策略在每个状态的价值不低于原策略在该状态的价值。

可以看到，推导过程中的每一个时间步都用到局部动作价值优势，累积到无穷步或者终止状态时，我们就得到了整个策略价值提升的不等式。

策略迭代过程

策略迭代算法的过程如下：对当前策略进行策略评估，得到其状态价值函数，然后根据该状态价值函数进行策略提升以得到一个更好的新策略，接着继续评估新策略、提升策略……直至最后收敛到最优策略。

结合策略评估和策略提升，我们可以得到以下策略迭代过程：

代码实现

根据以上方法实现策略迭代，首先初始化一个策略，所有状态都选择向下动作，并设置迭代次数为1000。

策略评估：首先初始化在当前策略下每个状态的价值为0，并设定一个阈值，用于判断策略下价值的更新程度，以便在收敛时及时停止循环，然后构建一个列表保存每次迭代中更新的策略下的价值，最后遍历所有状态，根据策略下价值的计算公式迭代求解。

策略提升：更新策略，先创建空数组保存改进的策略，接着遍历所有状态，计算每个状态下执行不同动作的价值，最后选取价值最大的动作更新策略。

策略迭代：进行1000次迭代，在每次迭代中，首先进行策略评估，然后进行策略提升，最后判断更新的策略与之前是否有变化，若没有变化，则迭代结束。

最后基于最佳策略，我们便可以得到最佳行动路线：[0，1，2，7，12，17，22]，并且步数为6。

4.8.3 价值迭代算法

策略迭代中的策略评估需要进行很多轮才能收敛到某一策略的状态函数，这需要很大的计算量，尤其是在状态和动作空间比较大的情况下。而价值迭代是被认为是一种策略评估只进行了一轮更新的策略迭代算法。需要注意的是，价值迭代中不存在显式的策略，我们只维护一个状态价值函数。

确定的说，价值迭代可以看成一种动态规划过程，它利用的是贝尔曼最优方程：

将其写成迭代更新的方式为：

价值迭代便是按照以上更新方式进行的。等到和相同时，他就是贝尔曼最优方程的不动点，此时对应着最优状态价值函数，然后我们利用以下方程，便可得到最优策略。

价值迭代算法流程如下：

代码实现

首先初始化状态价值表，设每个状态的价值为0，之后创建空数组保存最佳策略，接着利用雅克比迭代法进行1000次值迭代，每次迭代中判断价值表前后两次更新之差是否小于阈值，若小于则认为迭代收敛，停止迭代，最后利用求出的每个状态的价值得到最佳策略。

最后基于最佳策略，我们便可以得到最佳行动路线：[0，1，2，7，12，17，22]，并且步数为6。

4.8.4 参考文献

[1] GERAMIFARD A, WALSN T J, TELLEX S, et al. A tutorial on linear function approximators for dynamic programming and reinforcement learning [J]. Foundations and Trends®in Machine Learning, 2013, 6 (4): 375-451.

[2] SZEPESVÁRI C, LITTMAN M L. Generalized markov decision processes: dynamic-programming and reinforcement-learning algorithms [C]//International Conference of Machine Learning, 1996: 96.