动态规划：值迭代

策略迭代通过在评估当前策略和改进策略之间交替来找到最优策略 $\pi^*$ 。另一种动态规划算法是值迭代 (VI)。值迭代提供了一种不同的、通常计算效率更高的方法，可以直接找到最优值函数 $V^*$ ，从而避免了在主循环中进行显式策略评估的步骤。

回顾 $V^*(s)$ 的贝尔曼最优方程：

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

这个方程表明，状态 $s$ 的最优值是通过从该状态采取最优可能动作 $a$ ，然后遵循最优策略所获得的期望回报。

值迭代直接使用此方程作为更新规则。它首先为所有状态设置一个值函数 $V_0(s)$ 的初始估计（通常初始化为零）。然后，它通过对所有状态应用贝尔曼最优更新来迭代地完善这个估计，直到值函数收敛。

以下是详细步骤：

初始化： 为所有 $s \in S$ 选择一个任意的初始值函数 $V_0(s)$ 。同时设置一个小的容忍阈值 $\theta > 0$ 用于检查收敛性。
迭代循环： 重复以下步骤，对于 $k = 0, 1, 2, ...$ $k = 0, 1, 2, ...$ ：
- 初始化一个变量来跟踪本次迭代中的最大变化： $\Delta \leftarrow 0$ 。
- 对于每个状态 $s \in S$ $s \in S$ ：
  - 保存当前值： $v \leftarrow V_k(s)$ 。
  - 通过使用后继状态的当前值函数 $V_k$ 找到最佳动作的期望回报，从而计算新的潜在值： $V_{k+1}(s) \leftarrow \max_{a} \sum_{s', r} p(s', r | s, a) [r + \gamma V_k(s')]$
  - 更新目前为止看到的最大变化： $\Delta \leftarrow \max(\Delta, |v - V_{k+1}(s)|)$ 。
- 收敛检查： 如果 $\Delta < \theta$ ，则停止循环。值函数 $V_{k+1}$ 被认为是最优值函数 $V^*$ 的一个良好近似。

实质上，每次迭代都包含对状态空间的一次遍历，根据其潜在后继状态的当前值来更新每个状态的值，并使用贝尔曼最优方程中的动作最大化。此更新有时被称为“贝尔曼备份”或“最优性备份”。

此图说明了如何根据从状态 $s$ 获得的最大期望未来奖励来计算值 $V_{k+1}(s)$ ，计算中用到前一次迭代中后继状态 $s'$ 的值 $V_k(s')$ 。

为什么这样做有效？更新步骤中使用的贝尔曼最优算子是一个压缩映射。这种数学特性保证了重复应用更新将使值函数 $V_k$ 收敛到一个独特的固定点，这正是最优值函数 $V^*$ 。我们在此不进行正式证明，但直观的理解是每次迭代都使估计值更接近真实的最优值。

一旦值迭代收敛（即值函数 $\Delta$ 的变化变得非常小），我们就能得到 $V^*$ 的良好近似。我们如何从 $V^*$ 中获得最优策略 $\pi^*$ ？我们可以通过选择使每个状态的期望回报最大化的动作来直接提取它，方法是使用收敛的 $V^*$ 向前看一步：

对于每个状态 $s$ ：

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

这个步骤涉及到使用最终值函数 $V^*$ 计算每个状态中每个动作的期望值，并选择产生最高值的动作。请注意，这个策略提取步骤只在值函数收敛后执行一次。

策略迭代： 在完整的策略评估（计算当前 $\pi$ 的 $V^{\pi}$ ）和策略改进（使 $\pi$ 对 $V^{\pi}$ 贪婪）之间交替进行。每次迭代需要多次遍历进行评估。
值迭代： 使用贝尔曼最优方程直接迭代逼近 $V^*$ 。每次迭代包含一次应用最优更新的遍历。它隐含地结合了评估和改进。

在实践中，值迭代通常比策略迭代收敛得更快，特别是在 PI 中策略评估所需的迭代次数较多时。然而，每次 VI 迭代都需要计算动作的最大值，如果动作空间很大，这可能会计算密集。

像策略迭代一样，值迭代也属于动态规划方法的范畴。它找到了最优解，但严重依赖于拥有环境动力学（ $p(s', r | s, a)$ ）的完整且准确的模型。这一要求是一个重要局限，我们将在后续章节转向无模型学习方法时处理这个问题。

这部分内容有帮助吗？