动态规划：策略迭代

贝尔曼方程提供了价值函数的递归关系。特别是贝尔曼最优方程，定义了最佳可能价值函数（$V^*$ 或 $Q^*$）。那么，如何找到那个最优价值函数及其对应的最优策略 $\pi^*$ 呢？

动态规划（DP）提供了一类算法，可以在我们拥有环境的完整模型的前提下，计算出最优策略。这意味着我们需要了解所有状态 $s$、动作 $a$、下一个状态 $s'$ 和奖励 $r$ 的转移概率 $p(s', r | s, a)$。这是一个很强的假设，在实践中通常不满足（这就是为什么我们稍后会学习无模型方法！），但DP提供了一个坚实的理论依据。

一个基本的DP方法是策略迭代。它通过在评估当前策略和改进策略这两个主要步骤之间交替进行，来找到最优策略。我们来详细分析一下。

假设您从某个任意策略开始，我们称之为 $\pi_0$。它可能是完全随机的，也可能是基于某种简单的启发式方法。策略迭代旨在迭代地改进此策略，直到它收敛到最优策略 $\pi^*$。过程如下所示：

$\pi_0 \xrightarrow{\text{评估}} V^{\pi_0} \xrightarrow{\text{改进}} \pi_1 \xrightarrow{\text{评估}} V^{\pi_1} \xrightarrow{\text{改进}} \pi_2 \xrightarrow{\text{评估}} \dots \xrightarrow{\text{改进}} \pi^* \xrightarrow{\text{评估}} V^*$

这包括在循环中重复的两个核心组成部分：

1. 策略评估： 给定一个策略 $\pi$，计算其状态价值函数 $V^\pi$。
2. 策略改进： 使用计算出的 $V^\pi$，通过相对于 $V^\pi$ 贪婪地采取行动，生成一个新的、可能更好的策略 $\pi'$。

这个循环持续进行，直到策略在迭代之间不再改变，表明我们已经找到了最优策略。

策略评估：当前策略有多好？

在此步骤中，我们采用当前策略 $\pi$ 并计算所有状态 $s$ 的状态价值函数 $V^\pi(s)$。回想一下 $V^\pi$ 的贝尔曼期望方程：

$$V^\pi(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma V^\pi(s')]$$

对于一个有限MDP，此方程为我们提供了一个线性方程组，每个状态对应一个方程。如果存在 $|S|$ 个状态，我们就有 $|S|$ 个方程和 $|S|$ 个未知数（每个 $s$ 的 $V^\pi(s)$）。我们可以直接求解此系统。

然而，一个通常更简单且更普适的方法，尤其是在策略迭代的迭代性质中，是迭代地计算 $V^\pi$。我们从一个任意价值函数 $V_0$（例如，全零）开始，并重复应用贝尔曼期望方程作为更新规则：

$$V_{k+1}(s) \leftarrow \sum_a \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma V_k(s')] \quad \text{对于所有 } s \in S$$

我们遍历所有状态，根据上一次迭代的值（$V_k$）更新它们的值。当 $k \to \infty$ 时，此过程保证收敛到真实的 $V^\pi$。在实践中，当价值函数在迭代之间的变化变得非常小（即当 $\|V_{k+1} - V_k\|_{\infty} < \theta$ 对于某个小阈值 $\theta$）时，我们停止。这种迭代方法本质上是重复应用贝尔曼算子。

策略改进：我们能做得更好吗？

一旦我们对当前策略 $\pi$ 的 $V^\pi$ 有了相当准确的估计，我们就会问：“我们能改进这个策略吗？” 策略改进定理为我们提供了实现此目的的方法。

对于给定状态 $s$，我们可以向前看一步，并考虑如果我们选择一个动作 $a$（可能不同于 $\pi(a|s)$），然后遵循现有策略 $\pi$ 之后的预期回报。这正是动作价值函数 $Q^\pi(s, a)$ 的定义：

$$Q^\pi(s, a) = \sum_{s', r} p(s', r | s, a) [r + \gamma V^\pi(s')]$$

现在，假设对于某个状态 $s$，我们发现一个动作 $a$，使得 $Q^\pi(s, a) > V^\pi(s)$。这意味着在状态 $s$ 中只采取动作 $a$，然后遵循 $\pi$，比从一开始就只遵循 $\pi$ 要好。策略改进定理指出，如果我们构建一个新策略 $\pi'$，它在状态 $s$ 中选择这个“更好”的动作 $a$（并在其他地方遵循 $\pi$，或者更好的是，在任何地方都贪婪地采取行动），那么新策略 $\pi'$ 将严格优于或等于 $\pi$。

改进策略最常用的方法是使其相对于 $V^\pi$ 是贪婪的。也就是说，对于每个状态 $s$，新策略 $\pi'(s)$ 确定性地选择使 $Q^\pi(s, a)$ 最大化的动作 $a$：

$$\pi'(s) \leftarrow \underset{a}{\mathrm{argmax}} \, Q^\pi(s, a) = \underset{a}{\mathrm{argmax}} \sum_{s', r} p(s', r | s, a) [r + \gamma V^\pi(s')]$$

这个新的贪婪策略 $\pi'$ 保证至少和 $\pi$ 一样好。如果 $V^{\pi'} = V^\pi$，那么我们已经达到了最优价值函数 $V^*$ 和最优策略 $\pi^*$，因为我们满足贝尔曼最优方程。如果 $V^{\pi'} \neq V^\pi$，那么 $\pi'$ 严格更好，我们循环回评估这个改进后的策略。

策略迭代算法

综合起来，策略迭代算法步骤如下：

1. 初始化：
   • 选择一个任意的初始策略 $\pi(s)$，对于所有 $s \in S$。
   • 选择一个任意的初始价值函数 $V(s)$，对于所有 $s \in S$（例如，$V(s)=0$）。
2. 策略评估循环：
   • 重复直到 $V$ 收敛：
     • $\Delta \leftarrow 0$
     • 对于每个状态 $s \in S$：
       • $v \leftarrow V(s)$
       • $V(s) \leftarrow \sum_a \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma V(s')]$ （右侧使用前一次迭代的 $V$ 值，如果原地更新则使用最新可用值）
       • $\Delta \leftarrow \max(\Delta, |v - V(s)|)$
     • 如果 $\Delta < \theta$（一个小的正阈值）：跳出评估循环。
3. 策略改进：
   • policy_stable $\leftarrow$ true
   • 对于每个状态 $s \in S$：
     • old_action $\leftarrow \pi(s)$ （为简化起见，假设是确定性策略）
     • $\pi(s) \leftarrow \underset{a}{\mathrm{argmax}} \sum_{s', r} p(s', r | s, a) [r + \gamma V(s')]$
     • 如果 old_action $\neq \pi(s)$：policy_stable $\leftarrow$ false
4. 重复或终止：
   • 如果 policy_stable 为真：停止。当前策略 $\pi$ 和价值函数 $V$ 是最优的（$\pi^*$ 和 $V^*$）。
   • 否则：返回步骤2（策略评估）。

策略迭代中策略评估和策略改进的循环。该过程持续进行，直到在改进步骤后策略不再改变。

策略迭代保证在有限MDP中通过有限次数的迭代收敛到最优策略 $\pi^*$。这是因为只有有限数量的可能策略，并且每个策略改进步骤都会产生一个严格更好的策略（除非它已经是最优的）。由于与每个策略相关的价值函数增加或保持不变，并且值是有界的，因此该过程必须终止。

“主要缺点是什么？每一步，特别是策略评估，计算成本可能很高，可能需要多次遍历整个状态空间。此外，它严重依赖于拥有完整的MDP模型（$p(s', r | s, a)$），这在实际问题中通常不可用。这个限制促使我们在后续章节中讨论无模型方法。”