3. 动态规划

动态规划是一种用于解决复杂问题的数学方法，广泛应用于计算机科学、经济学等领域，其核心思想是将问题分解为更小的子问题，并存储这些子问题的解决方案，以避免重复计算，从而提高效率。

在强化学习中，动态规划被用于求解值函数和最优策略，核心概念是贝尔曼方程，它描述了状态价值函数和动作价值函数的递归关系。

具身智能视角：动态规划是理解强化学习算法的理论基石。虽然在实际机器人控制中很少直接使用（因为需要完整的环境模型），但策略迭代和价值迭代的思想贯穿了后续所有 RL 算法——从 DQN 的 Q 值更新到 PPO 的策略优化，都能看到贝尔曼方程的影子。

基于动态规划的强化学习算法主要包括策略迭代和价值迭代等，这些算法依赖于对环境的完全了解，即需要知道状态转移概率和奖励函数，即属于有模型的方法。这两种算法虽然现在很少直接应用于实际问题，但它们为理解更复杂的强化学习算法奠定了基础。

3.1 动态规划

动态规划（ ）是一种用于解决复杂问题的数学优化方法，在计算机科学、管理科学和经济学等领域都有着广泛的应用。它通过将问题分解为更小的子问题，并存储这些子问题的解决方案，以避免重复计算，从而提高效率。

动态规划能够解决的问题通常具备三个性质：重叠子问题（）、最优化原理（）和无后效性（）。重叠子问题指的是子问题在求解过程中会被多次计算，而最优子结构则意味着一个问题的最优解可以通过其子问题的最优解来构建。无后效性则表示未来只依赖于当前状态，不依赖于过去，即未来的独立性，这与马尔可夫性质相契合。

动态规划通常采用自底向上的方法，通过迭代地解决子问题，最终得到原始问题的解决方案。常见的动态规划算法包括斐波那契数列、背包问题和路径规划问题等。

为帮助理解动态规划的思想，这里以一个路径规划问题为例进行说明。如图 1 所示，在一个 的网格世界中，机器人以左上角为起点，右下角为终点，每次只能向右或向下移动一步，这里的问题是需要计算出从起点到终点的不同路径数量。

路径之和

使用动态规划的方法来解决这个问题的话，主要包含几个步骤：确定状态，写出状态转移方程和寻找边界条件。

首先可以将状态定义为 ，表示从左上角即坐标为 到坐标 的路径数量，其中 以及。由于机器人只能向右或者向下走，所以当机器人处于 的位置时，它的前一个坐标只能是上边一格 或者左边一格 ，这样一来就能建立出一个状态之间的关系，如式 所示。

即走到当前位置 的路径数量等于走到前一个位置 和 的所有路径之和，这个就是状态转移方程。

然后再考虑一些边界条件。上面的状态转移方程只适用于内部位置，即 且 的情形；如果直接代入边界点，就会出现 或者 这类没有意义的项。换句话说， 就是该题的一个边界，在这种情况下机器人位于起始点，从起始点到起始点 对应的路径数量 必然是 ；对于 ，此时机器人会一直沿着网格左边沿往下走，这条路径上的所有 也都会是 ， 的情况同理。

代入边界条件后，状态转移方程可以完善如式 所示。

实现如代码 1 所示。

代码 1: 路径问题求解

def solve(m,n):
    # 初始化边界条件
    f = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
    # 状态转移
    for i in range(1, m):
        for j in range(1, n):
            f[i][j] = f[i - 1][j] + f[i][j - 1]
    return f[m - 1][n - 1]

输入 时，最终输出结果为 ，表示从起点到终点一共有 种不同的路径，对应的解析流程如图 2 所示。

路径之和解析

在强化学习中，基于动态规划的算法主要有两种，一是策略迭代（），二是价值迭代（）。其中策略迭代由两部分组成，分别是策略评估（）和策略改进（）。

价值迭代则是将策略评估和策略改进合并在一起进行。这两种算法都依赖于对环境的完全了解，即需要知道状态转移概率和奖励函数，因此在实际应用中受到了一定的限制。然而，它们为理解更复杂的强化学习算法奠定了基础。

3.2 贝尔曼方程

3.2.1 状态价值形式

类比于回报公式 ，状态价值也有类似的递归公式，如式 所示。

其中 是状态转移概率，即在状态 下采取动作 后转移到状态 并获得奖励 的概率，这就是贝尔曼方程的状态价值函数形式。

贝尔曼方程相当于动态规划中的状态转移方程，将整体期望拆分"当前+未来"两部分递归地计算。它也进一步表示了当智能体在环境中处于某个状态时，它未来的"好坏"（即回报 ）不仅取决于当前获得的奖励，还取决于之后的状态中能获得的所有未来奖励。

3.2.2 动作价值形式

类似地，贝尔曼方程的动作价值形式如式 所示。

3.2.3 贝尔曼最优方程

在一个马尔可夫决策过程中，我们可以找到一个最优策略 ，使得从任意状态 出发，获得的期望回报最大，如式 所示。

这个公式就是贝尔曼最优方程（Bellman optimality equation），它对于后面要讲的策略迭代算法具有一定的指导意义。同理，对应的动作价值函数形式如式 所示。

3.3 策略迭代

策略迭代算法是一种用于求解最优策略的动态规划方法。它通过交替进行策略评估和策略改进两个步骤，逐步逼近最优策略。

在策略评估步骤中，固定当前策略 ，并计算对应的状态价值函数 。这一步骤通过迭代更新状态价值函数，直到收敛为止。而在策略改进步骤中，利用当前的状态价值函数 来更新策略 ，选择在每个状态下能够最大化预期回报的动作，从而得到一个新的策略 ，如式 所示。

如图 3 所示，（a）描述了上面所说的策略评估和改进持续迭代的过程，（b）则描述了在交替迭代过程中策略和状态价值函数最后会同时收敛到最优。

策略迭代的收敛过程

策略迭代的算法流程如图 4 所示。

策略迭代算法流程

在这个过程中，每一步需要遍历所有状态和动作，因此计算复杂度较高。然而，由于策略迭代能够有效地利用当前策略的信息来改进策略，通常需要的迭代次数会更少些。策略迭代就好像一个喜欢深思熟虑的人，每次都会花充分的时间来评估当前的策略，想通了再迈步改进。

3.4 价值迭代

价值迭代算法的核心思想是将策略评估和策略改进合并在一起进行。它通过直接更新状态价值函数 来逼近最优价值函数 ，如式 所示。

价值迭代的算法流程如图 5 所示。

价值迭代算法伪代码

在这个过程中，首先将所有的状态价值初始化，然后不停地对每个状态迭代，直到收敛到最优价值，并且根据最优价值推算出最优策略。价值迭代就好像一个行动迅速果断的人，每次都直接根据当前的情况做出最优决策，而不花太多时间去评估当前的策略。

如图 6 所示，策略迭代是不停地在 和 这两条线之间"跳变"直到收敛到 ，而价值迭代则是直接沿着 这条线不断逼近 。由于价值迭代每次只更新状态价值函数，因此每次迭代的计算量较小，然而，由于它没有充分利用当前策略的信息，通常需要更多的迭代次数才能收敛到最优策略。

策略迭代与价值迭代收敛过程的区别

与策略迭代相比，价值迭代更像是一个急功近利的人，喜欢快速做出决策并迭代，而不是花时间去深思熟虑当前的策略再做改进。

换句话说，策略迭代每一步都需要花费较多时间去评估和改进策略，但通常需要的迭代次数较少；而价值迭代每一步计算量较小，但通常需要更多的迭代次数才能收敛到最优策略。如果环境模型简单，状态空间较小，策略迭代更加高效；而如果环境模型复杂，状态空间较大，价值迭代可能更适合。在现代实际应用中，我们几乎总是选择价值迭代作为首选思路，因为它每次迭代的计算量较小，更适合处理大规模问题。

3.5 思考

动态规划问题的主要性质有哪些？

动态规划主要性质包括最优化原理、无后效性和有重叠子问题，其中无后效性指的是某状态以后的过程不会影响以前的状态，这十分契合马尔可夫性质，因此动态规划问题可以看作是马尔可夫决策过程的一种特殊情况。

动态规划为什么通常采用自底向上的方法而不是自顶向下的方法？

动态规划通常采用自底向上的方法，因为这种方法可以避免重复计算子问题，从而提高效率。自底向上的方法通过迭代地解决子问题，逐步构建出原始问题的解决方案，而自顶向下的方法则可能会多次计算相同的子问题，导致计算量增加。此外，自底向上的方法更容易实现和理解，因为它直接从最简单的子问题开始，逐步扩展到更复杂的问题。

状态价值函数和动作价值函数之间的关系是什么？

一般来说，状态价值函数是动作价值函数在当前策略 下的期望。也就是说，对于一个状态 ，有 。只有在策略对所有动作等概率选择时，这个式子才会退化成对所有动作价值的简单平均。

策略迭代和价值迭代是有模型还是无模型的方法？

策略迭代和价值迭代都是有模型的方法，因为它们都需要知道环境的状态转移概率和奖励函数，以便进行状态价值函数和动作价值函数的计算和更新。

策略迭代和价值迭代哪个算法速度会更快？

策略迭代每一步需要花费较多时间去评估和改进策略，但通常需要的迭代次数较少；而价值迭代每一步计算量较小，但通常需要更多的迭代次数才能收敛到最优策略。因此，具体哪个算法速度更快取决于问题的具体情况。如果环境模型简单，状态空间较小，策略迭代可能更高效；而如果环境模型复杂，状态空间较大，价值迭代可能更适合。