机器人入行指南
底层/贝尔曼方程:为什么 V 是不动点,为什么迭代一定能收敛

底层 03 / 11 · 值函数

贝尔曼方程:为什么 V 是不动点,为什么迭代一定能收敛

从线性方程组的解析解,到压缩映射的收敛保证,再到 max 带来的那一处非线性——以及它引起的系统性过估计

约 60 分钟基础6 段推导4 题自测

一句话结论

贝尔曼方程是一组线性方程,它的解就是值函数;因为 γ<1 让它成为压缩映射,所以随便初始化、反复迭代,一定收敛到唯一解。一旦把 ∑_a π 换成 max_a,线性就没了,这才是后面必须用近似方法的真正原因。

这一篇是「为什么能算」的证明。看完你会明白三件事:值迭代为什么一定收敛、γ=1 为什么会出事、以及为什么所有 Q-learning 类算法都有过估计——后者直接决定了 SAC 为什么要取两个 Q 的最小值。

符号表

符号含义
P^π策略 π 下的状态转移矩阵,第 s 行是「从 s 出发到各处的概率」
R^π策略 π 下的期望即时奖励,一个向量
T贝尔曼算子,作用在一个值向量上,输出一个新的值向量
||·||_∞最大绝对值范数,也就是「差得最远的那个状态差多少」
A w = b线性逼近下的固定点方程,A 是特征协方差矩阵

推导

  1. 矩阵形式:贝尔曼方程其实是线性方程组
  2. 压缩映射:为什么迭代一定会收敛
  3. 一旦换成 max,线性就没了
  4. 策略迭代与值迭代,其实是一回事
  5. max 引起的系统性过估计(这一条决定了 SAC 的写法)
  6. 为什么 γ=1 会麻烦,而不只是「不收敛」

1. 矩阵形式:贝尔曼方程其实是线性方程组

把每个状态的方程排成一行,就得到一个 n 元线性方程组。n 是状态数。既然线性,就可以直接解。

V^π = R^π + γ P^π V^π ⟹ V^π = (I - γP^π)-1 R^π

为什么能这么写状态数小的时候这是最优解——一步到位、没有迭代误差。深度 RL 用它做不了,是因为 n 不可数(连续状态),而且 (I-γP)^{-1} 是 O(n³)。注意这个式子也说明:只要 γ<1,(I-γP) 一定可逆。

值函数V(s) 或 Q(s,a)贪心改进argmax 下一步环境转移 + 奖励自举用估计更新估计贝尔曼值=即时奖励+折扣后继值「用估计更新估计」是值方法的心脏,也是不收敛风险的全部来源

2. 压缩映射:为什么迭代一定会收敛

定义贝尔曼算子 T:给它一个值向量,按贝尔曼右边算出一个新向量。要证的是 T 把任意两个向量的距离缩短到 γ 倍以内。

||T V - T V'||_∞ = γ||P(V - V')||_∞ ≤ γ||V - V'||_∞

为什么能这么写第二步能这么放,是因为 P 是随机矩阵(每行和为 1),所以它不会放大任何向量的最大绝对值。γ<1 时 T 是压缩映射,由巴拿赫不动点定理:存在唯一不动点,且从任意初值迭代都收敛到它。这就是值迭代的合法性证明,一行都不多。

3. 一旦换成 max,线性就没了

最优贝尔曼方程把「按策略加权」换成了「取最好的动作」。这一步让方程从线性变成分段线性。

V*(s) = max_a ∑s' P(s'|s,a)[ r + γ V*(s') ]

为什么能这么写后果有三:① 不能写成 (I-γP)^{-1} 求逆;② 但 T 仍然是压缩的(max 也不放大距离),所以值迭代照样收敛;③ 解不再是「V 的线性函数」,而是「一族线性函数的上包络」——这就是为什么最优值函数有折点,也是为什么用平滑函数逼近它会有系统误差。

4. 策略迭代与值迭代,其实是一回事

策略迭代是「评估到底 → 改进一次」,值迭代是「评估一步 → 改进一次」。后者能行,靠的是策略改进定理:按 Q 的贪心选动作,新策略一定不比旧的差。

π'(s) = argmax_a Q^π(s,a) ⟹ Vπ' ≥ V^π(逐状态)

为什么能这么写证明思路:V^π(s) ≤ max_a Q^π(s,a) = Q^π(s,π'(s)) ≤ V^{π'}(s)。第一处是 max 的定义,第二处是对 π' 做一次贝尔曼展开再递归。所以「改进」这一步不会回退,循环必然停在最优。

5. max 引起的系统性过估计(这一条决定了 SAC 的写法)

当 Q 的估计有噪声时,max 会挑到「被高估得最厉害」的那个动作。所以估计的期望不是真值的 max,而是比它大。

E[ max_a Q̂_a ] ≥ max_a E[ Q̂_a ]

为什么能这么写Jensen 不等式:max 是凸函数,凸函数的期望不小于期望的函数。偏多少取决于动作数和噪声:真值全为 0、10 个动作、噪声 σ=1 时,实测 E[max]=1.539(σ=0.5 时 0.769,σ=2 时 3.087,基本线性)。这就是 double Q 的动机:用两个独立估计,取小的那个把正偏压回去。

6. 为什么 γ=1 会麻烦,而不只是「不收敛」

γ=1 时 T 只是「非扩张」,不是「压缩」,不动点可能不唯一,迭代会停在一个平台上来回晃。

γ=1:||TV - TV'||_∞ ≤ ||V - V'||_∞(可能相等)

为什么能这么写有些任务 γ=1 也能解(有吸收终止态时回报有限),但收敛速度没有任何保证,且值函数的尺度可以任意平移。实践建议:连续控制默认 γ=0.99;episode 很长或奖励稀疏时升到 0.995~0.999,并同步检查有效视野是否够覆盖一次完整动作。

手算一遍

三状态链:s0 →(r=0)→ s1 →(r=0)→ s2,s2 是终止状态且到达时得 1 分。γ=0.9。用贝尔曼方程手算 V(s0)、V(s1)、V(s2)。

  1. 从终点往回算:V(s2) = 1(终止状态,只拿即时奖励,没有后续)
  2. V(s1) = 0 + 0.9 × V(s2) = 0.9
  3. V(s0) = 0 + 0.9 × V(s1) = 0.81
答

V = [0.81, 0.90, 1.00]。这类「一条链」的 MDP 是检验贝尔曼实现的标准件:答案唯一、能心算、而且能立刻暴露「终止状态多算了一步」的错误(错写成 V(s2)=1+0.9×1=1.9 时,全都是错的)。实测值迭代 200 轮收敛到 [0.81, 0.9, 1.0],误差 1e-12。

跑一遍

策略迭代的完整实现,25 行。重点是内层「评估要跑几轮」——把它改成 1 轮,就变成了值迭代,运行结果一样,你可以自己验证这一点。

python · 只要 numpy
import numpy as np
n, G = 3, 0.9
P = np.zeros((n, n)); R = np.zeros(n)
P[0,1] = 1.0; P[1,2] = 1.0; P[2,2] = 1.0; R[2] = 1.0

def eval_pi(pi, iters=100):
    V = np.zeros(n)
    for _ in range(iters):
        V = R + G * P.dot(V)
    return V

pi = np.zeros(n, dtype=int)
for k in range(20):
    V = eval_pi(pi)
    Q = np.stack([R + G * P.dot(V)] * 1, 0)  # 单动作环境,Q 即 V
    new = Q.argmax(0)
    if (new == pi).all():
        break
    pi = new
print('V =', V, ' 迭代轮数 =', k+1)
print('解析解 =', np.linalg.solve(np.eye(n) - G*P, R))

看到这个就算过

两行输出一致:V = [0.81 0.9 1.0],且与 np.linalg.solve 的结果逐位相同。如果两者不同,你的 P 里某行没归一(行和不为 1),压缩映射的前提就不成立了。

自测 4 题

先自己答,再展开。答不上来就回到对应的那一节——每道题都能在推导里找到出处。

01为什么最优贝尔曼方程不能写成 (I-γP)-1R 的形式?

因为里面有 max_a,它不是 P 的线性组合——不同的状态会选不同的动作,等效的「转移矩阵」依赖于 V 本身。解是一族线性函数的上包络,只能迭代求。

02γ=1 时值迭代一定会发散吗?

不一定发散,但一定没有收敛速率保证,且不动点可能不唯一(值可以整体平移)。有终止状态时回报有界,仍可能收敛;但工程上不要赌这个。

03E[max_a Q̂] ≥ max_a E[Q̂] 这个不等式的方向,为什么会导致「越训越差」?

因为目标值被系统性高估,而高估又会通过 bootstrap 传回下一步,形成正反馈。动作数越多、噪声越大,偏得越多,最后策略去追那些根本不存在的收益。

04策略改进定理保证了什么?它为什么让「评估一步就改进」也成立?

保证按 Q 贪心得到的新策略逐状态不差于旧策略。因为改进的证明只用了一次贝尔曼展开,不需要评估收敛——所以评估一步也能改进,只是改进得少一点,这就是值迭代。

接着看

全系列 11 篇