策略迭代

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

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

此步骤的目标是：对于当前给定的策略 $\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)$ :

V_{k+1}^{\pi}(s) \leftarrow \sum_{s'} T(s, \pi(s), s') [R(s, \pi(s), s') + \gamma V_k^{\pi}(s')]

在实践中，迭代更新的方法通常更慢。

在计算出当前策略 $\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值最大的动作。

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