策略迭代

策略迭代是一种用于在马尔可夫决策过程中寻找最优策略 $\pi^*$ 的算法。与值迭代相比，策略迭代通常能够更快地收敛，因为它直接优化策略，而策略的收敛速度往往比值的收敛速度快得多。

该算法的核心思想是：从一个任意的初始策略开始，通过一个迭代循环不断优化它，直到策略不再发生变化为止。每一次迭代都包含两个核心步骤：策略评估和策略改进。

特性	价值迭代 (Value Iteration)	策略迭代 (Policy Iteration)
迭代目标	让价值函数收敛到最优值	让策略收敛到最优策略
迭代次数	多（需要很多次迭代来精确化数值）	少（策略通常很快就稳定不变了）
单次迭代成本	低（只做一次贝尔曼更新）	高（需要做一次完整的策略评估）
收敛速度	慢（受价值收敛速度的限制）	快（受策略收敛速度的限制）

1. 算法流程

$a.$ 策略评估

此步骤的目标是：对于当前给定的策略 $\pi_i$，计算出在该策略下每一个状态 $s$ 的期望效用，即值函数 $V^{\pi_i}(s)$。

当我们固定一个策略 $\pi$ 时，每个状态的价值由其后继状态的价值决定。这形成了一个由 $|S|$ 个线性方程组成的方程组，其中 $|S|$ 是状态的数量。其方程遵循贝尔曼期望方程：

$$V^{\pi}(s) = \sum_{s'} T(s, \pi(s), s') [R(s, \pi(s), s') + \gamma V^{\pi}(s')]$$

这里我们不再需要 $\max$ 算子，因为动作已经被策略 $\pi(s)$ 固定了。

有两种方法可以计算出 $V^{\pi}(s)$:

1. 求解线性方程组：直接解出这 $|S|$ 个方程，得到精确的 $V^{\pi}(s)$。
2. 迭代更新：像值迭代一样，通过重复应用以下更新规则，直到值收敛。这个过程也称为“贝尔曼更新”： $$V_{k+1}^{\pi}(s) \leftarrow \sum_{s'} T(s, \pi(s), s') [R(s, \pi(s), s') + \gamma V_k^{\pi}(s')]$$ 在实践中，迭代更新的方法通常更慢。

$b.$ 策略改进

在计算出当前策略 $\pi_i$ 的值函数 $V^{\pi_i}$ 后，我们利用这些值来寻找一个更好的新策略 $\pi_{i+1}$。

改进的方法是，对每个状态 $s$，我们进行一次单步前瞻 (one-step lookahead)，贪婪地选择在当前值函数 $V^{\pi_i}$ 下能带来最大期望效用的动作 $a$：

$$\pi_{i+1}(s) = \underset{a}{\operatorname{argmax}} \sum_{s'} T(s, a, s') [R(s, a, s') + \gamma V^{\pi_i}(s')]$$

这个过程实际上就是使用当前的 $V^{\pi_i}$ 来计算每个动作的Q值，并为每个状态选择Q值最大的动作。

$c.$ 收敛

我们重复执行“评估”和“改进”这两个步骤。当策略在一次迭代后不再发生任何变化时，即 $\pi_{i+1} = \pi_i$，算法就收敛了。此时的策略就是最优策略 $\pi^*$。