贝尔曼方程矩阵形式与求解

矩阵形式的定义与对应关系

假设我们有一个有限状态空间 $\mathcal{S}$，大小为 $N=|\mathcal{S}|$。

1. 向量 $\mathbf{v}$ (Value Vector)

$\mathbf{v}$ 是一个 $N\times 1$ 的列向量，其第 $i$ 个元素对应于状态 $s_i$ 的状态值函数 $v_{\pi }(s_i)$。

$$\mathbf{v}=\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ ⋮\\ v_{\pi }(s_N)\end{array}\right]$$

2. 向量 $\mathbf{r}$ (Expected Immediate Reward Vector)

$\mathbf{r}$ 是一个 $N\times 1$ 的列向量，其第 $i$ 个元素对应于在状态 $s_i$ 下采取策略 $\pi$ 所获得的即时期望奖励。

根据我们前面推导的公式 (2.9) 的第一部分：

$$\mathbf{r}(s)\doteq \mathbb{E}[R_{t+1}|S_t=s]=\sum _{a\in \mathcal{A}}\pi (a|s)\sum _{r\in \mathcal{R}}p(r|s,a)r$$

3. 矩阵 $\mathbf{P}$ (State Transition Matrix under Policy $\pi$)

$\mathbf{P}$ 是一个 $N\times N$ 的方阵，称为策略转移矩阵。其元素 ${\mathbf{P}}_{ij}$ 表示从状态 $s_i$ 转移到状态 $s_j$ 的概率，前提是遵循策略 $\pi$。

${\mathbf{P}}_{ij}\doteq P_{\pi }(S_{t+1}=s_j|S_t=s_i)$

根据概率的加权求和， ${\mathbf{P}}_{ij}$ 可以从 MDP 动力学和策略 $\pi$ 中计算出来：

$${\mathbf{P}}_{ij}=\sum _{a\in \mathcal{A}}\pi (a|s_i)p(s_j|s_i,a)$$

其中 $p(s_j|s_i,a)={\sum }_{r\in \mathcal{R}}p(s_j,r|s_i,a)$ 是在状态 $s_i$ 采取动作 $a$ 转移到 $s_j$ 的（不依赖奖励的）概率。

4. 矩阵形式的推导

将公式 (2.9) 重新写回 $v_{\pi }(s)$：

$$v_{\pi }(s)=\underset{\mathbf{r}(s)}{\underbrace{\sum _{a\in \mathcal{A}}\pi (a|s)\sum _{r\in \mathcal{R}}p(r|s,a)r}}+\gamma \underset{\text{未来期望项}}{\underbrace{\sum _{a\in \mathcal{A}}\pi (a|s)\sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })}}$$

未来期望项可以写成矩阵乘法：

$$\sum _{a\in \mathcal{A}}\pi (a|s)\sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })=\sum _{s^{\prime }\in \mathcal{S}}\left(\sum _{a\in \mathcal{A}}\pi (a|s)p(s^{\prime }|s,a)\right)v_{\pi }(s^{\prime })$$

内层括号 ${\sum }_{a\in \mathcal{A}}\pi (a|s)p(s^{\prime }|s,a)$ 正是 ${\mathbf{P}}_{s,s^{\prime }}$。

因此，对于任意状态 $s$，我们有：

$$v_{\pi }(s)=\mathbf{r}(s)+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathbf{P}}_{s,s^{\prime }}{v}_{\pi }(s^{\prime })$$

将所有 $N$ 个状态写成联立方程组，即得到矩阵形式：

$$\mathbf{v}=\mathbf{r}+\gamma \mathbf{Pv}$$

---

贝尔曼方程的线性系统求解

我们希望求解 $\mathbf{v}$。将 $\mathbf{v}$ 项移到等式左侧：

$$\mathbf{v}-\gamma \mathbf{Pv}=\mathbf{r}$$ $$(\mathbf{I}-\gamma \mathbf{P})\mathbf{v}=\mathbf{r}(\text{其中 }\mathbf{I}\text{ 是 }N\times N\text{ 单位矩阵})$$

这是一个标准的线性代数系统 $\mathbf{Ax}=\mathbf{b}$，其中：

• 待解向量 $\mathbf{x}=\mathbf{v}$
• 系数矩阵 $\mathbf{A}=(\mathbf{I}-\gamma \mathbf{P})$
• 常数向量 $\mathbf{b}=\mathbf{r}$

如果系数矩阵 $\mathbf{A}=(\mathbf{I}-\gamma \mathbf{P})$ 是可逆的 (invertible)，那么贝尔曼方程的解就是唯一的，并且可以通过矩阵求逆得到：

$$\mathbf{v}=(\mathbf{I}-\gamma \mathbf{P}{)}^{-1}\mathbf{r}$$

---

可逆性的证明与条件

要证明矩阵 $\mathbf{A}=(\mathbf{I}-\gamma \mathbf{P})$ 是可逆的，我们通常利用矩阵范数和收敛级数的理论，特别是诺伊曼级数 (Neumann Series)。

1. 关键条件：折扣因子 $\gamma <1$

在标准强化学习中，折扣因子 $\gamma$ 满足 $0\le \gamma <1$。这是保证可逆性的核心数学条件。

2. 性质：转移矩阵 $\mathbf{P}$

矩阵 $\mathbf{P}$ 是一个随机矩阵 (Stochastic Matrix)，因为其元素 ${\mathbf{P}}_{ij}$ 代表概率，且每一行的元素和为 1：

$$\sum _{j=1}^N{\mathbf{P}}_{ij}=\sum _{s^{\prime }\in \mathcal{S}}{P}_{\pi }(S_{t+1}=s^{\prime }|S_t=s_i)=1$$

3. 可逆性证明（基于 Neumann Series）

如果一个矩阵 $\mathbf{B}$ 满足 $\mathbf{B}$ 的某个矩阵范数 $\Vert \mathbf{B}\Vert$ 小于 1，那么 $(\mathbf{I}-\mathbf{B})$ 是可逆的，并且其逆可以表示为诺伊曼级数：

$$(\mathbf{I}-\mathbf{B}{)}^{-1}=\sum _{k=0}^{\infty }{\mathbf{B}}^k=\mathbf{I}+\mathbf{B}+{\mathbf{B}}^2+{\mathbf{B}}^3+\dots$$

在这个问题中，我们的矩阵 $\mathbf{B}=\gamma \mathbf{P}$。

我们选择无穷范数（行和范数） $\Vert \cdot {\Vert }_{\infty }$ 来评估 $\mathbf{B}$：

$\Vert \mathbf{B}{\Vert }_{\infty }=\Vert \gamma \mathbf{P}{\Vert }_{\infty }=\gamma \Vert \mathbf{P}{\Vert }_{\infty }$

对于任何随机矩阵 $\mathbf{P}$，其行和范数总是 1： $\Vert \mathbf{P}{\Vert }_{\infty }={\max }_i{\sum }_j|{\mathbf{P}}_{ij}|={\max }_i{\sum }_j{\mathbf{P}}_{ij}=1$

因此： $\Vert \mathbf{B}{\Vert }_{\infty }=\gamma \cdot 1=\gamma$

结论：

如果 $\gamma <1$，那么 $\Vert \mathbf{B}{\Vert }_{\infty }=\gamma <1$。

根据矩阵分析理论，当 $\Vert \gamma \mathbf{P}{\Vert }_{\infty }<1$ 时，矩阵 $(\mathbf{I}-\gamma \mathbf{P})$ 必然是可逆的。

4. 收敛性

矩阵求逆 $(\mathbf{I}-\gamma \mathbf{P}{)}^{-1}$ 实际上对应着对回报 $G_t$ 的长期计算：

$$\mathbf{v}=(\mathbf{I}-\gamma \mathbf{P}{)}^{-1}\mathbf{r}=\sum _{k=0}^{\infty }(\gamma \mathbf{P}{)}^k\mathbf{r}$$

展开这个级数： $\mathbf{v}=\mathbf{r}+\gamma \mathbf{Pr}+{\gamma }^2{\mathbf{P}}^2\mathbf{r}+\dots$

• $\mathbf{r}$: 即时期望奖励（$k=0$）。
• $\gamma \mathbf{Pr}$: 走一步后获得的期望奖励的折扣值（$k=1$）。
• ${\gamma }^k{\mathbf{P}}^k\mathbf{r}$: 走 $k$ 步后获得的期望奖励的折扣值。

这个级数求和 ${\sum }_{k=0}^{\infty }(\gamma \mathbf{P}{)}^k\mathbf{r}$ 正是回报 $G_t$ 的定义。因为 $\gamma <1$，级数是绝对收敛 (absolutely convergent) 的，保证了值函数 $\mathbf{v}$ 存在且唯一。

总结可逆条件

在有限状态空间 MDP 中，贝尔曼期望方程的矩阵 $(\mathbf{I}-\gamma \mathbf{P})$ 可逆的充要条件是：

1. 折扣因子 $\gamma \in [0,1)$。 (即必须严格小于 1)。

如果 $\gamma =1$（非折扣任务，如平均奖励），除非 MDP 满足特定的遍历性和奖励结构（例如，存在吸收态且所有状态都能到达），否则矩阵 $(\mathbf{I}-\mathbf{P})$ 通常是不可逆的（因为 $\mathbf{P}$ 是随机矩阵，其特征值 1 对应的左特征向量为 $1^T$，意味着 $(\mathbf{I}-\mathbf{P})$ 的行列式为零）。因此，$\gamma <1$ 是保证解唯一性和矩阵可逆性的关键数学要求。

---

盖尔什戈林圆盘定理回顾

1. 理论定义

盖尔什戈林圆盘定理 (Gershgorin Circle Theorem) 是线性代数中用于估计矩阵特征值位置的重要工具。

对于一个 $N\times N$ 矩阵 $\mathbf{A}$，我们定义第 $i$ 个盖尔什戈林圆盘 (Gershgorin Disk) $D_i$ 如下：

$$D_i=\{z\in \mathbb{C}:|z-{\mathbf{A}}_{ii}|\le R_i\}$$

其中：

• ${\mathbf{A}}_{ii}$ 是圆盘的中心（矩阵的第 $i$ 个对角线元素）。
• $R_i$ 是圆盘的半径，等于第 $i$ 行非对角线元素的绝对值之和： $R_i={\sum }_{j\ne i}|{\mathbf{A}}_{ij}|$

定理内容： 矩阵 $\mathbf{A}$ 的所有特征值 $\lambda$ 都位于这些圆盘 $D_i$ 的并集 ${\bigcup }_{i=1}^N{D}_i$ 之内。

2. 可逆性判据

如果矩阵 $\mathbf{A}$ 的所有盖尔什戈林圆盘都不包含复平面上的原点 $z=0$，那么矩阵 $\mathbf{A}$ 一定是可逆的。

判据： 对于所有 $i$，圆盘中心 ${\mathbf{A}}_{ii}$ 到原点 $0$ 的距离（即 $|{\mathbf{A}}_{ii}|$）必须严格大于圆盘的半径 $R_i$。

$$|{\mathbf{A}}_{ii}|>R_i=\sum _{j\ne i}|{\mathbf{A}}_{ij}|$$

这被称为严格对角占优 (Strictly Diagonally Dominant) 条件。

---

应用于贝尔曼方程矩阵

我们的目标矩阵是 $\mathbf{A}=\mathbf{I}-\gamma {\mathbf{P}}_{\pi }$。我们分析其元素。

1. 矩阵 $\mathbf{A}$ 的元素

$\mathbf{A}$ 是 $N\times N$ 矩阵。由于 $\mathbf{I}$ 是单位矩阵：

${\mathbf{A}}_{ij}=(\mathbf{I}-\gamma {\mathbf{P}}_{\pi }{)}_{ij}={\mathbf{I}}_{ij}-\gamma ({\mathbf{P}}_{\pi }{)}_{ij}$

• 对角线元素 ($i=j$)： ${\mathbf{A}}_{ii}={\mathbf{I}}_{ii}-\gamma ({\mathbf{P}}_{\pi }{)}_{ii}=1-\gamma p_{\pi }(s_i|s_i)$

• 非对角线元素 ($i\ne j$)： ${\mathbf{A}}_{ij}={\mathbf{I}}_{ij}-\gamma ({\mathbf{P}}_{\pi }{)}_{ij}=0-\gamma p_{\pi }(s_j|s_i)=-\gamma p_{\pi }(s_j|s_i)$

2. 盖尔什戈林圆盘的参数计算

对于第 $i$ 个状态 $s_i$，我们计算其圆盘的中心和半径：

A. 圆盘中心 $C_i$

中心 $C_i$ 是对角线元素 ${\mathbf{A}}_{ii}$: $C_i=1-\gamma p_{\pi }(s_i|s_i)$

B. 圆盘半径 $R_i$

半径 $R_i$ 是第 $i$ 行非对角线元素的绝对值之和:

$$R_i=\sum _{j\ne i}|{\mathbf{A}}_{ij}|=\sum _{j\ne i}|-\gamma p_{\pi }(s_j|s_i)|$$

由于 $\gamma >0$ 且概率 $p_{\pi }(s_j|s_i)\ge 0$:

$$R_i=\sum _{j\ne i}\gamma p_{\pi }(s_j|s_i)=\gamma \sum _{j\ne i}{p}_{\pi }(s_j|s_i)$$

3. 证明圆盘不包含原点

根据可逆性判据，我们必须证明 $|C_i|>R_i$。

首先，分析 $C_i$ 的符号：由于 $0\le p_{\pi }(s_i|s_i)\le 1$ 且 $0\le \gamma <1$，所以 $1-\gamma p_{\pi }(s_i|s_i)>0$。 因此，中心 $C_i$ 是正实数，我们只需要证明 $C_i>R_i$:

$$1-\gamma p_{\pi }(s_i|s_i)\text{vs.}\gamma \sum _{j\ne i}{p}_{\pi }(s_j|s_i)$$

我们需要证明：

$$1-\gamma p_{\pi }(s_i|s_i)>\gamma \sum _{j\ne i}{p}_{\pi }(s_j|s_i)$$

将所有 $\gamma$ 项移到右边：

$$1>\gamma p_{\pi }(s_i|s_i)+\gamma \sum _{j\ne i}{p}_{\pi }(s_j|s_i)$$

提取 $\gamma$：

$$1>\gamma \left[p_{\pi }(s_i|s_i)+\sum _{j\ne i}{p}_{\pi }(s_j|s_i)\right]$$

回顾 ${\mathbf{P}}_{\pi }$ 的性质：它是随机矩阵，每一行元素的和为 1。第 $i$ 行元素的总和为：

$$p_{\pi }(s_i|s_i)+\sum _{j\ne i}{p}_{\pi }(s_j|s_i)=\sum _{j\in \mathcal{S}}{p}_{\pi }(s_j|s_i)=1$$

因此，不等式简化为：

$$1>\gamma \cdot 1$$ $$1>\gamma$$

4. 最终结论

由于我们在强化学习中始终假设折扣因子 $\gamma <1$，因此不等式 $C_i>R_i$ 总是成立。

几何意义： 对于每一个状态 $s_i$，矩阵 $\mathbf{A}=\mathbf{I}-\gamma {\mathbf{P}}_{\pi }$ 对应的盖尔什戈林圆盘的中心 $C_i$ 位于正实轴上。中心到原点的距离 $|C_i|$ 严格大于半径 $R_i$。 $|C_i|>R_i$ 这意味着每一个圆盘 $D_i$ 都完全位于右半平面，并且不包含原点 $z=0$。

代数结论： 根据盖尔什戈林圆盘定理，矩阵 $\mathbf{A}=\mathbf{I}-\gamma {\mathbf{P}}_{\pi }$ 的所有特征值 $\lambda$ 都不可能为 $0$。 因此，矩阵 $(\mathbf{I}-\gamma {\mathbf{P}}_{\pi })$ 是可逆的。

总结： 这种基于特征值的方法，与之前基于范数和诺伊曼级数的证明，殊途同归，都严谨地证明了在折扣因子 $\gamma <1$ 的前提下，贝尔曼期望方程的线性系统解是唯一且存在的。