值迭代的收敛性

定义与预备知识

1. 贝尔曼方程的定义

我们已经知道，策略 $\pi$ 下的真实状态值函数 ${\mathbf{v}}_{\pi }$ 满足贝尔曼期望方程（即不动点方程）：

${\mathbf{v}}_{\pi }={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{\pi }\text{(真实解)}$

其中：

• ${\mathbf{v}}_{\pi }$：真实值函数向量。
• ${\mathbf{r}}_{\pi }$：即时期望奖励向量 (此处记为 ${\mathbf{r}}_{\pi }$ 以强调对策略 $\pi$ 的依赖)。
• ${\mathbf{P}}_{\pi }$：策略 $\pi$ 下的转移矩阵。
• $\gamma$：折扣因子，满足 $0\le \gamma <1$。

2. 迭代过程的定义（值迭代）

我们考虑一个迭代过程，比如策略评估中的值迭代：从一个任意初始值 ${\mathbf{v}}_0$ 开始，序列 ${\mathbf{v}}_k$ 由以下公式生成：

${\mathbf{v}}_{k+1}={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_k\text{(迭代更新)}$

3. 误差的定义

我们定义第 $k$ 步的误差 ${\mathbf{\delta }}_k$ 为当前估计值 ${\mathbf{v}}_k$ 与真实值 ${\mathbf{v}}_{\pi }$ 之间的差异：

${\mathbf{\delta }}_k={\mathbf{v}}_k-{\mathbf{v}}_{\pi }$

为了证明收敛性，我们需要证明 ${\lim }_{k\to \infty }{\mathbf{\delta }}_k=0$。

---

误差项的递归关系推导

1. 代入误差定义

将 ${\mathbf{v}}_{k+1}={\mathbf{\delta }}_{k+1}+{\mathbf{v}}_{\pi }$ 和 ${\mathbf{v}}_k={\mathbf{\delta }}_k+{\mathbf{v}}_{\pi }$ 代入迭代更新公式：

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

$${\mathbf{\delta }}_{k+1}+{\mathbf{v}}_{\pi }={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }({\mathbf{\delta }}_k+{\mathbf{v}}_{\pi })$$

2. 展开与化简

展开右侧的乘积项：

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

目标是孤立出 ${\mathbf{\delta }}_{k+1}$，将 ${\mathbf{v}}_{\pi }$ 移到右侧：

$${\mathbf{\delta }}_{k+1}={\mathbf{r}}_{\pi }-{\mathbf{v}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{\delta }}_k+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{\pi }$$

3. 利用贝尔曼方程的真实解

我们知道真实解 ${\mathbf{v}}_{\pi }$ 满足： ${\mathbf{v}}_{\pi }={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{\pi }$

将此等式改写为： ${\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{\pi }-{\mathbf{v}}_{\pi }=0$

将这个零向量项代入 ${\mathbf{\delta }}_{k+1}$ 的表达式中：

$${\mathbf{\delta }}_{k+1}=({\mathbf{r}}_{\pi }-{\mathbf{v}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{\pi })+\gamma {\mathbf{P}}_{\pi }{\mathbf{\delta }}_k$$ $${\mathbf{\delta }}_{k+1}=0+\gamma {\mathbf{P}}_{\pi }{\mathbf{\delta }}_k$$

我们得到了误差项的简洁递归关系：

$${\mathbf{\delta }}_{k+1}=\gamma {\mathbf{P}}_{\pi }{\mathbf{\delta }}_k$$

---

收敛性证明

1. 递归展开

利用上述递归关系，我们可以将 ${\mathbf{\delta }}_{k+1}$ 展开，直到初始误差 ${\mathbf{\delta }}_0={\mathbf{v}}_0-{\mathbf{v}}_{\pi }$：

${\mathbf{\delta }}_{k+1}=(\gamma {\mathbf{P}}_{\pi }){\mathbf{\delta }}_k$ ${\mathbf{\delta }}_{k+1}=(\gamma {\mathbf{P}}_{\pi })(\gamma {\mathbf{P}}_{\pi }){\mathbf{\delta }}_{k-1}={\gamma }^2{\mathbf{P}}_{\pi }^2{\mathbf{\delta }}_{k-1}$ $\dots$

$${\mathbf{\delta }}_{k+1}={\gamma }^{k+1}{\mathbf{P}}_{\pi }^{k+1}{\mathbf{\delta }}_0$$

2. 利用矩阵范数证明收敛

为了证明 ${\mathbf{\delta }}_{k+1}\to 0$，我们需要取范数：

$\Vert {\mathbf{\delta }}_{k+1}\Vert =\Vert {\gamma }^{k+1}{\mathbf{P}}_{\pi }^{k+1}{\mathbf{\delta }}_0\Vert$

利用矩阵范数与向量范数的关系：$\Vert \mathbf{Ax}\Vert \le \Vert \mathbf{A}\Vert \Vert \mathbf{x}\Vert$，以及常数提取性质：

$\Vert {\mathbf{\delta }}_{k+1}\Vert ={\gamma }^{k+1}\Vert {\mathbf{P}}_{\pi }^{k+1}{\mathbf{\delta }}_0\Vert \le {\gamma }^{k+1}\Vert {\mathbf{P}}_{\pi }^{k+1}\Vert \Vert {\mathbf{\delta }}_0\Vert$

在前面我们讨论过，策略转移矩阵 ${\mathbf{P}}_{\pi }$ 是一个随机矩阵，其无穷范数 $\Vert {\mathbf{P}}_{\pi }{\Vert }_{\infty }=1$。更一般地，矩阵的幂 ${\mathbf{P}}_{\pi }^{k+1}$ 也是一个随机矩阵，因此其无穷范数也是 1： $\Vert {\mathbf{P}}_{\pi }^{k+1}{\Vert }_{\infty }=1$

选择无穷范数（这是最常用的范数，因为它对应于向量中元素的最大绝对值）：

$\Vert {\mathbf{\delta }}_{k+1}{\Vert }_{\infty }\le {\gamma }^{k+1}\Vert {\mathbf{P}}_{\pi }^{k+1}{\Vert }_{\infty }\Vert {\mathbf{\delta }}_0{\Vert }_{\infty }={\gamma }^{k+1}\cdot 1\cdot \Vert {\mathbf{\delta }}_0{\Vert }_{\infty }$ $\Vert {\mathbf{\delta }}_{k+1}{\Vert }_{\infty }\le {\gamma }^{k+1}\Vert {\mathbf{\delta }}_0{\Vert }_{\infty }$

3. 最终结论

由于 ${\mathbf{\delta }}_0={\mathbf{v}}_0-{\mathbf{v}}_{\pi }$ 是一个固定的初始误差向量，其范数 $\Vert {\mathbf{\delta }}_0{\Vert }_{\infty }$ 是一个常数。

关键在于折扣因子 $\gamma$:

因为我们假设 $\gamma <1$，所以当 $k\to \infty$ 时，${\gamma }^{k+1}\to 0$。

因此：

$$\underset{k\to \infty }{\lim }\Vert {\mathbf{\delta }}_{k+1}{\Vert }_{\infty }\le \underset{k\to \infty }{\lim }{\gamma }^{k+1}\Vert {\mathbf{\delta }}_0{\Vert }_{\infty }=0$$

由于向量的范数趋于零，其向量本身也趋于零：

$$\underset{k\to \infty }{\lim }{\mathbf{\delta }}_{k+1}=0$$

即 ${\lim }_{k\to \infty }{\mathbf{v}}_k={\mathbf{v}}_{\pi }$。

《强化学习的数学原理》中提到：“Note that $0\le {\mathbf{P}}_{\pi }^k\le 1$, which means every entry of ${\mathbf{P}}_{\pi }^k$ is no greater than 1 for any $k=0,1,2,\dots$. That is because ${\mathbf{P}}_{\pi }^{k}1=1$, where $1=[1,\dots ,1{]}^T$.”

• ${\mathbf{P}}_{\pi }^k$ 的物理意义： ${\mathbf{P}}_{\pi }^k$ 是 $k$ 步转移概率矩阵。其元素 $({\mathbf{P}}_{\pi }^k{)}_{ij}$ 表示从状态 $s_i$ 经过 $k$ 步转移到状态 $s_j$ 的概率。因此，所有元素都必须在 $[0,1]$ 之间。
• ${\mathbf{P}}_{\pi }^{k}1=1$ 的意义： 矩阵 ${\mathbf{P}}_{\pi }^k$ 乘以全 1 向量 $1$ 得到 $1$ 向量，这等价于说 ${\mathbf{P}}_{\pi }^k$ 的每一行元素之和为 1。这再次确认了 ${\mathbf{P}}_{\pi }^k$ 是一个随机矩阵，从而保证了 $\Vert {\mathbf{P}}_{\pi }^k{\Vert }_{\infty }=1$。

这个证明严谨地确立了在 $\gamma <1$ 的条件下，通过迭代更新，我们可以收敛到策略 $\pi$ 下的真实值函数 ${\mathbf{v}}_{\pi }$。这不仅是策略评估的基础，也是后续贝尔曼最优方程 (Bellman Optimality Equation) 收敛性的关键原理。