2. Bellman Equation

发布于 2026 年 8 月 16 日

1. State Value

Definition:

Following policy $\pi$, we have a trajectory

$$S_t \xrightarrow{A_t} S_{t+1}, R_{t+1}$$ $$A_t \sim \pi(\cdot \mid S_t)$$ $$v_\pi (s) = E[G_t|S_t = s]$$ $$G_t = R_{t+1} + \gamma R_{t+2} + \gamma ^2R_{t+3} + \dots$$

从状态 $s$ 出发 能获得的回报期望 跟选取的策略 $\pi$ 有关

2. Calculate

假设我们有一个网格

要计算从每一个状态出发得到的 return

列出表达式：

$$\begin{aligned} v_1 &= r_1 + \gamma r_2 + \gamma^2 r_3 + \dots \\ v_2 &= r_2 + \gamma r_3 + \gamma^2 r_4 + \dots \\ v_3 &= r_3 + \gamma r_4 + \gamma^2 r_1 + \dots \\ v_4 &= r_4 + \gamma r_1 + \gamma^2 r_2 + \dots \end{aligned}$$

（此处简化了 $v$ 和 $r$ 的写法）

把后续的 return 提取出来，可以得到：

$$\begin{aligned} v_1 &= r_1 + \gamma(r_2 + \gamma r_3 + \dots) = r_1 + \gamma v_2 \\ v_2 &= r_2 + \gamma(r_3 + \gamma r_4 + \dots) = r_2 + \gamma v_3 \\ v_3 &= r_3 + \gamma(r_4 + \gamma r_1 + \dots) = r_3 + \gamma v_4 \\ v_4 &= r_4 + \gamma(r_1 + \gamma r_2 + \dots) = r_4 + \gamma v_1 \end{aligned}$$

矩阵形式

$$\begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \end{bmatrix} + \gamma \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \end{bmatrix}$$

其中转移顺序为 $s_1 \to s_2 \to s_3 \to s_4 \to s_1$，所以转移矩阵为：

$$P = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}$$

矩阵形式通解

$$\underbrace{ \begin{bmatrix} v_\pi(s_1) \\ v_\pi(s_2) \\ v_\pi(s_3) \\ v_\pi(s_4) \end{bmatrix} }_{\mathbf{v}_\pi} = \underbrace{ \begin{bmatrix} r_\pi(s_1) \\ r_\pi(s_2) \\ r_\pi(s_3) \\ r_\pi(s_4) \end{bmatrix} }_{\mathbf{r}_\pi} + \gamma \underbrace{ \begin{bmatrix} p_\pi(s_1 \mid s_1) & p_\pi(s_2 \mid s_1) & p_\pi(s_3 \mid s_1) & p_\pi(s_4 \mid s_1) \\ p_\pi(s_1 \mid s_2) & p_\pi(s_2 \mid s_2) & p_\pi(s_3 \mid s_2) & p_\pi(s_4 \mid s_2) \\ p_\pi(s_1 \mid s_3) & p_\pi(s_2 \mid s_3) & p_\pi(s_3 \mid s_3) & p_\pi(s_4 \mid s_3) \\ p_\pi(s_1 \mid s_4) & p_\pi(s_2 \mid s_4) & p_\pi(s_3 \mid s_4) & p_\pi(s_4 \mid s_4) \end{bmatrix} }_{P_\pi} \underbrace{ \begin{bmatrix} v_\pi(s_1) \\ v_\pi(s_2) \\ v_\pi(s_3) \\ v_\pi(s_4) \end{bmatrix} }_{\mathbf{v}_\pi}$$

再简写

$$\mathbf{v}_\pi = \mathbf{r}_\pi + \gamma P_\pi \mathbf{v}_\pi$$

将包含 $\mathbf{v}_\pi$ 的项移到左边：

$$\mathbf{v}_\pi - \gamma P_\pi \mathbf{v}_\pi = \mathbf{r}_\pi$$

提取 $\mathbf{v}_\pi$：

$$(I - \gamma P_\pi)\mathbf{v}_\pi = \mathbf{r}_\pi$$

两边左乘 $(I - \gamma P_\pi)^{-1}$，得到：

$$\boxed{ \mathbf{v}_\pi = (I - \gamma P_\pi)^{-1}\mathbf{r}_\pi }$$

当 $P_\pi$ 是合法的转移概率矩阵，并且 $0 \leq \gamma < 1$ 时，$I - \gamma P_\pi$ 可逆。

$(I - \gamma P_\pi)^{-1}$ 一定存在？证明折叠

证明

因为 $P_\pi$ 是转移概率矩阵，所以它的元素满足：

$$p_{ij} \geq 0, \qquad \sum_j p_{ij} = 1$$

对任意向量 $\mathbf{x}$，使用无穷范数 $\|\mathbf{x}\|_\infty = \max_j |x_j|$，有：

$$\begin{aligned} \|P_\pi \mathbf{x}\|_\infty &= \max_i \left|\sum_j p_{ij}x_j\right| \\ &\leq \max_i \sum_j p_{ij}|x_j| \\ &\leq \max_i \sum_j p_{ij}\|\mathbf{x}\|_\infty \\ &= \|\mathbf{x}\|_\infty \end{aligned}$$

假设 $I - \gamma P_\pi$ 不可逆，则一定存在非零向量 $\mathbf{x}$，使得：

$$(I - \gamma P_\pi)\mathbf{x} = \mathbf{0}$$

于是：

$$\mathbf{x} = \gamma P_\pi \mathbf{x}$$

两边取无穷范数：

$$\|\mathbf{x}\|_\infty = \gamma\|P_\pi\mathbf{x}\|_\infty \leq \gamma\|\mathbf{x}\|_\infty$$

由于 $0 \leq \gamma < 1$，上式对于非零的 $\mathbf{x}$ 不可能成立。因此假设不成立，$I - \gamma P_\pi$ 的零空间中只有零向量，所以它是非奇异矩阵，其逆矩阵一定存在：

$$\boxed{(I - \gamma P_\pi)^{-1}\ \text{存在}}$$

这个逆矩阵还可以表示成收敛的 Neumann 级数：

$$(I - \gamma P_\pi)^{-1} = I + \gamma P_\pi + \gamma^2 P_\pi^2 + \cdots$$

可以知道 $P$ 这个转移矩阵实际上是对特征向量中的数值进行“加权平均”。加权平均不会让最大绝对值变得更大，因此矩阵的特征值模长不会超过 1。再加上 $\gamma <1$, 这个级数显然可以收敛

可知 我们能够直接解这个方程 得到 state value

然而 现实情况 这种计算复杂度过高 为 $O(n^3)$ (即高斯消元的复杂度) 难以使用

证明

以高斯消元为例，第 $k$ 轮消元需要更新右下角大约

$$(n-k)\times(n-k)$$

个元素。

因此，总计算量大致为：

$$\sum_{k=1}^{n-1}(n-k)^2$$

令 $m=n-k$。当 $k$ 从 $1$ 变化到 $n-1$ 时，$m$ 从 $n-1$ 变化到 $1$，因此：

$$\begin{aligned} \sum_{k=1}^{n-1}(n-k)^2 &=\sum_{m=1}^{n-1}m^2 \\ &=\frac{(n-1)n(2n-1)}{6} \\ &=\frac{2n^3-3n^2+n}{6} \\ &=\frac{1}{3}n^3-\frac{1}{2}n^2+\frac{1}{6}n \end{aligned}$$

当 $n$ 足够大时，最高次项 $\frac{1}{3}n^3$ 起主导作用，所以高斯消元的时间复杂度为：

$$\boxed{O(n^3)}$$

Bellman 公式推导

从状态价值函数的定义出发：

$$\begin{aligned} v_\pi(s) &= \mathbb{E}_\pi[G_t \mid S_t=s] \\ &= \mathbb{E}_\pi[R_{t+1}+\gamma G_{t+1} \mid S_t=s] \\ &= \mathbb{E}_\pi[R_{t+1} \mid S_t=s] + \gamma\mathbb{E}_\pi[G_{t+1} \mid S_t=s] \end{aligned}$$

首先展开即时奖励项。根据全期望公式，对策略可能选取的动作求和：

$$\begin{aligned} \mathbb{E}_\pi[R_{t+1} \mid S_t=s] &= \sum_a \pi(a \mid s) \mathbb{E}[R_{t+1} \mid S_t=s,A_t=a] \\ &= \sum_a \pi(a \mid s) \sum_r p(r \mid s,a)r \end{aligned}$$

接着展开未来回报项：

$$\begin{aligned} \mathbb{E}_\pi[G_{t+1} \mid S_t=s] &= \sum_{s'} \mathbb{E}_\pi[G_{t+1} \mid S_t=s,S_{t+1}=s'] p_\pi(s' \mid s) \\ &= \sum_{s'} \mathbb{E}_\pi[G_{t+1} \mid S_{t+1}=s'] p_\pi(s' \mid s) \\ &= \sum_{s'} v_\pi(s')p_\pi(s' \mid s) \\ &= \sum_{s'} v_\pi(s') \sum_a p(s' \mid s,a)\pi(a \mid s) \end{aligned}$$

这里使用了马尔可夫性质：给定下一状态 $S_{t+1}=s'$ 后，未来回报不再依赖之前的状态 $S_t$。

其中，策略 $\pi$ 下的状态转移概率为：

$$p_\pi(s' \mid s) = \sum_a p(s' \mid s,a)\pi(a \mid s)$$

将即时奖励项和未来回报项代回状态价值函数：

$$\begin{aligned} v_\pi(s) &= \sum_a \pi(a \mid s) \sum_r p(r \mid s,a)r \\ &\quad + \gamma\sum_{s'}v_\pi(s') \sum_a p(s' \mid s,a)\pi(a \mid s) \\ &= \sum_a \pi(a \mid s) \left[ \sum_r p(r \mid s,a)r + \gamma\sum_{s'}p(s' \mid s,a)v_\pi(s') \right], \qquad \forall s \in \mathcal{S} \end{aligned}$$

因此，Bellman 期望方程为：

$$\boxed{ v_\pi(s) = \sum_a \pi(a \mid s) \left[ \sum_r p(r \mid s,a)r + \gamma\sum_{s'}p(s' \mid s,a)v_\pi(s') \right] }$$

也可以写作

$$\boxed{ v_\pi(s)=\mathbb E_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})\mid S_t=s] }$$

前者只是把 Bellman“期望”的过程，按随机性的来源展开了。

Bellman 迭代解法

Bellman 期望方程的矩阵形式为：

$$\mathbf{v}_\pi = \mathbf{r}_\pi + \gamma P_\pi\mathbf{v}_\pi$$

它的闭式解为：

$$\mathbf{v}_\pi = (I-\gamma P_\pi)^{-1}\mathbf{r}_\pi$$

直接求逆的计算开销较大。为了避免计算 $(I-\gamma P_\pi)^{-1}$，可以使用迭代算法：

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

从任意初始向量 $\mathbf{v}_0$ 出发，这个算法会产生序列：

$$\mathbf{v}_0,\mathbf{v}_1,\mathbf{v}_2,\dots$$

下面证明当 $0\leq\gamma<1$ 时，该序列收敛到 $\mathbf{v}_\pi$。

定义 Bellman 算子：

$$T_\pi(\mathbf{v}) = \mathbf{r}_\pi + \gamma P_\pi\mathbf{v}$$

$\mathbf{v}_\pi$ 是这个算子的不动点，因为：

$$T_\pi(\mathbf{v}_\pi)=\mathbf{v}_\pi$$

定义第 $k$ 次迭代的误差：

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

根据迭代公式和 Bellman 方程：

$$\begin{cases} \mathbf{v}_{k+1} = \mathbf{r}_\pi+\gamma P_\pi\mathbf{v}_k \\ \mathbf{v}_\pi = \mathbf{r}_\pi+\gamma P_\pi\mathbf{v}_\pi \end{cases}$$

两式相减可得：

$$\begin{aligned} \boldsymbol{\delta}_{k+1} &= \mathbf{v}_{k+1}-\mathbf{v}_\pi \\ &= \gamma P_\pi (\mathbf{v}_k-\mathbf{v}_\pi) \\ &= \gamma P_\pi\boldsymbol{\delta}_k \end{aligned}$$

不断展开误差递推式：

$$\boldsymbol{\delta}_k = (\gamma P_\pi)^k\boldsymbol{\delta}_0$$

因为 $P_\pi$ 是合法的转移概率矩阵，所以：

$$\|P_\pi\mathbf{x}\|_\infty \leq \|\mathbf{x}\|_\infty$$

因此：

$$\begin{aligned} \|\boldsymbol{\delta}_k\|_\infty &= \|(\gamma P_\pi)^k \boldsymbol{\delta}_0\|_\infty \\ &\leq \gamma^k \|\boldsymbol{\delta}_0\|_\infty \\ &\longrightarrow 0, \qquad k\to\infty \end{aligned}$$

所以无论初始向量 $\mathbf{v}_0$ 如何选择，都有：

$$\boxed{ \mathbf{v}_k \longrightarrow \mathbf{v}_\pi =(I-\gamma P_\pi)^{-1}\mathbf{r}_\pi, \qquad k\to\infty }$$

因此，Bellman 迭代可以在不显式计算矩阵逆的情况下求出策略 $\pi$ 的状态价值。

Action Value（动作价值）

状态价值和动作价值分别定义为：

$$\begin{aligned} v_\pi(s) &= \mathbb{E}_\pi[G_t \mid S_t=s] \\ q_\pi(s,a) &= \mathbb{E}_\pi[G_t \mid S_t=s,A_t=a] \end{aligned}$$

$v_\pi(s)$ 表示从状态 $s$ 出发并遵循策略 $\pi$ 时的期望回报；$q_\pi(s,a)$ 表示在状态 $s$ 先执行动作 $a$，随后遵循策略 $\pi$ 时的期望回报。

根据全期望公式，可以按照策略 $\pi$ 对动作价值加权求和：

$$\begin{aligned} v_\pi(s) &= \mathbb{E}_\pi[G_t \mid S_t=s] \\ &= \sum_a \mathbb{E}_\pi[G_t \mid S_t=s,A_t=a] \pi(a \mid s) \\ &= \sum_a \pi(a \mid s)q_\pi(s,a) \end{aligned}$$

因此，状态价值等于当前状态下所有动作价值关于策略的期望：

$$\boxed{ v_\pi(s)=\sum_a\pi(a \mid s)q_\pi(s,a) }$$

前面已经得到状态价值的 Bellman 期望方程：

$$\begin{aligned} v_\pi(s) &= \sum_a \pi(a \mid s) \sum_r p(r \mid s,a)r \\ &\quad + \gamma\sum_{s'}v_\pi(s') \sum_a p(s' \mid s,a)\pi(a \mid s) \\ &= \sum_a\pi(a \mid s) \left[ \sum_r p(r \mid s,a)r + \gamma\sum_{s'}p(s' \mid s,a)v_\pi(s') \right] \end{aligned}$$

与 $v_\pi(s)=\sum_a\pi(a \mid s)q_\pi(s,a)$ 对比，可以得到：

$$\boxed{ q_\pi(s,a) = \sum_r p(r \mid s,a)r + \gamma\sum_{s'}p(s' \mid s,a)v_\pi(s') }$$

也就是说，动作价值由两部分组成：

$$\underbrace{ \sum_r p(r \mid s,a)r }_{\text{即时奖励的期望}} + \underbrace{ \gamma\sum_{s'}p(s' \mid s,a)v_\pi(s') }_{\text{折扣后的未来状态价值}}$$

Summary

对固定策略 我们使用迭代法求解 $v_\pi$