策略改进

引理（策略改进）的形式化证明

引理内容：

如果新策略 ${\pi }_{k+1}$ 是通过对 $v_{{\pi }_k}$ 进行单步贪婪改进得到的：

${\pi }_{k+1}=\arg {\max }_{\pi }\left({\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{{\pi }_k}\right)$

则新策略的值函数 ${\mathbf{v}}_{{\pi }_{k+1}}$ 至少与旧策略的值函数 ${\mathbf{v}}_{{\pi }_k}$ 一样好（逐元素非负）：

${\mathbf{v}}_{{\pi }_{k+1}}\ge {\mathbf{v}}_{{\pi }_k}$

证明思路

证明的关键在于连续应用贪婪改进的定义和贝尔曼期望操作符，并利用矩阵的非负性性质。我们将证明 ${\mathbf{v}}_{{\pi }_k}$ 是 ${\mathcal{T}}_{{\pi }_{k+1}}$ 操作符下的一个下界，然后通过迭代证明 ${\mathbf{v}}_{{\pi }_k}\le {\mathbf{v}}_{{\pi }_{k+1}}$。

符号定义回顾

• ${\mathbf{v}}_{{\pi }_k}$: 策略 ${\pi }_k$ 的真实值函数。
• ${\mathbf{r}}_{\pi }$: 策略 $\pi$ 下的即时期望奖励向量。
• ${\mathbf{P}}_{\pi }$: 策略 $\pi$ 下的状态转移矩阵。
• ${\mathcal{T}}_{\pi }(\mathbf{v})={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }\mathbf{v}$: 贝尔曼期望操作符。

第一步：建立不等式基础（贪婪选择的直接结果）

根据新策略 ${\pi }_{k+1}$ 的定义（贪婪改进）： ${\pi }_{k+1}=\arg {\max }_{\pi }{\mathcal{T}}_{\pi }({\mathbf{v}}_{{\pi }_k})$

这意味着对于任何状态 $s$， ${\pi }_{k+1}$ 所选择的动作集合产生的单步期望价值，要大于或等于原策略 ${\pi }_k$ 产生的单步期望价值。

因此，我们有逐元素不等式：

$${\mathbf{r}}_{{\pi }_{k+1}}+\gamma {\mathbf{P}}_{{\pi }_{k+1}}{\mathbf{v}}_{{\pi }_k}\ge {\mathbf{r}}_{{\pi }_k}+\gamma {\mathbf{P}}_{{\pi }_k}{\mathbf{v}}_{{\pi }_k}$$

由于 ${\mathbf{v}}_{{\pi }_k}$ 是策略 ${\pi }_k$ 的真实值函数，它满足贝尔曼期望方程： ${\mathbf{v}}_{{\pi }_k}={\mathbf{r}}_{{\pi }_k}+\gamma {\mathbf{P}}_{{\pi }_k}{\mathbf{v}}_{{\pi }_k}$

将 ${\mathbf{v}}_{{\pi }_k}$ 代入上式右侧，得到：

$${\mathbf{r}}_{{\pi }_{k+1}}+\gamma {\mathbf{P}}_{{\pi }_{k+1}}{\mathbf{v}}_{{\pi }_k}\ge {\mathbf{v}}_{{\pi }_k}$$

这可以写成： ${\mathcal{T}}_{{\pi }_{k+1}}({\mathbf{v}}_{{\pi }_k})\ge {\mathbf{v}}_{{\pi }_k}(\ast )$

（ 这表示如果我们在状态 $s$ 下遵循新策略 ${\pi }_{k+1}$ 走一步，然后继续遵循旧策略 ${\pi }_k$，得到的期望回报比全程遵循旧策略 ${\pi }_k$ 得到的期望回报要高。）

第二步：利用贝尔曼操作符的单调性

我们知道新策略 ${\mathbf{v}}_{{\pi }_{k+1}}$ 是贝尔曼操作符 ${\mathcal{T}}_{{\pi }_{k+1}}$ 的不动点： ${\mathbf{v}}_{{\pi }_{k+1}}={\mathcal{T}}_{{\pi }_{k+1}}({\mathbf{v}}_{{\pi }_{k+1}})$

现在我们使用单调性：贝尔曼操作符 ${\mathcal{T}}_{\pi }$ 具有单调性 (monotonicity)，即如果 $\mathbf{u}\ge \mathbf{v}$，则 ${\mathcal{T}}_{\pi }(\mathbf{u})\ge {\mathcal{T}}_{\pi }(\mathbf{v})$。

证明单调性： ${\mathcal{T}}_{\pi }(\mathbf{u})-{\mathcal{T}}_{\pi }(\mathbf{v})=({\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }\mathbf{u})-({\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }\mathbf{v})=\gamma {\mathbf{P}}_{\pi }(\mathbf{u}-\mathbf{v})$ 因为 $\mathbf{u}-\mathbf{v}\ge 0$，且 $\gamma \ge 0$ 并且随机矩阵 ${\mathbf{P}}_{\pi }\ge 0$（所有元素非负）。 两个非负矩阵/向量相乘的结果是非负向量： $\gamma {\mathbf{P}}_{\pi }(\mathbf{u}-\mathbf{v})\ge 0$。 所以，${\mathcal{T}}_{\pi }(\mathbf{u})\ge {\mathcal{T}}_{\pi }(\mathbf{v})$。

第三步：通过迭代完成证明

我们从步骤一的基础不等式 $(\ast )$ 开始：

${\mathbf{v}}_{{\pi }_k}\le {\mathcal{T}}_{{\pi }_{k+1}}({\mathbf{v}}_{{\pi }_k})$

现在，我们对不等式两边应用 ${\mathcal{T}}_{{\pi }_{k+1}}$ 操作符。根据单调性，不等号方向不变：

${\mathcal{T}}_{{\pi }_{k+1}}({\mathbf{v}}_{{\pi }_k})\le {\mathcal{T}}_{{\pi }_{k+1}}({\mathcal{T}}_{{\pi }_{k+1}}({\mathbf{v}}_{{\pi }_k}))={\mathcal{T}}_{{\pi }_{k+1}}^2({\mathbf{v}}_{{\pi }_k})$

结合上述，我们得到： ${\mathbf{v}}_{{\pi }_k}\le {\mathcal{T}}_{{\pi }_{k+1}}({\mathbf{v}}_{{\pi }_k})\le {\mathcal{T}}_{{\pi }_{k+1}}^2({\mathbf{v}}_{{\pi }_k})$

我们可以无限迭代下去： ${\mathbf{v}}_{{\pi }_k}\le {\mathcal{T}}_{{\pi }_{k+1}}({\mathbf{v}}_{{\pi }_k})\le {\mathcal{T}}_{{\pi }_{k+1}}^2({\mathbf{v}}_{{\pi }_k})\le \cdots \le {\mathcal{T}}_{{\pi }_{k+1}}^m({\mathbf{v}}_{{\pi }_k})$

第四步：取极限

根据压缩映射定理，我们知道，对任意初始值 ${\mathbf{v}}_0$，迭代 ${\mathbf{v}}_{m+1}={\mathcal{T}}_{{\pi }_{k+1}}({\mathbf{v}}_m)$ 必然收敛到 ${\mathcal{T}}_{{\pi }_{k+1}}$ 的不动点，即 ${\mathbf{v}}_{{\pi }_{k+1}}$。

因此，当 $m\to \infty$ 时： ${\lim }_{m\to \infty }{\mathcal{T}}_{{\pi }_{k+1}}^m({\mathbf{v}}_{{\pi }_k})={\mathbf{v}}_{{\pi }_{k+1}}$

由于 ${\mathbf{v}}_{{\pi }_k}$ 逐元素小于或等于序列中的每一项： ${\mathbf{v}}_{{\pi }_k}\le {\lim }_{m\to \infty }{\mathcal{T}}_{{\pi }_{k+1}}^m({\mathbf{v}}_{{\pi }_k})$

最终证明结论：

$${\mathbf{v}}_{{\pi }_k}\le {\mathbf{v}}_{{\pi }_{k+1}}$$

这个证明严格证明了策略改进步骤保证了值函数的单调不减性 (monotonic non-decreasing)。 这是策略迭代算法能够收敛到最优策略 ${\pi }^{\ast }$ 的关键保证。由于状态和策略空间是有限的，值函数 $\mathbf{v}$ 的值域有界，因此单调不减的序列最终必须收敛，从而确保了策略迭代的收敛性。