底层 03 / 11 · 值函数
贝尔曼方程:为什么 V 是不动点,为什么迭代一定能收敛
从线性方程组的解析解,到压缩映射的收敛保证,再到 max 带来的那一处非线性——以及它引起的系统性过估计
一句话结论
贝尔曼方程是一组线性方程,它的解就是值函数;因为 γ<1 让它成为压缩映射,所以随便初始化、反复迭代,一定收敛到唯一解。一旦把 ∑_a π 换成 max_a,线性就没了,这才是后面必须用近似方法的真正原因。
这一篇是「为什么能算」的证明。看完你会明白三件事:值迭代为什么一定收敛、γ=1 为什么会出事、以及为什么所有 Q-learning 类算法都有过估计——后者直接决定了 SAC 为什么要取两个 Q 的最小值。
符号表
| 符号 | 含义 |
|---|---|
P^π | 策略 π 下的状态转移矩阵,第 s 行是「从 s 出发到各处的概率」 |
R^π | 策略 π 下的期望即时奖励,一个向量 |
T | 贝尔曼算子,作用在一个值向量上,输出一个新的值向量 |
||·||_∞ | 最大绝对值范数,也就是「差得最远的那个状态差多少」 |
A w = b | 线性逼近下的固定点方程,A 是特征协方差矩阵 |
推导
- 矩阵形式:贝尔曼方程其实是线性方程组
- 压缩映射:为什么迭代一定会收敛
- 一旦换成 max,线性就没了
- 策略迭代与值迭代,其实是一回事
- max 引起的系统性过估计(这一条决定了 SAC 的写法)
- 为什么 γ=1 会麻烦,而不只是「不收敛」
1. 矩阵形式:贝尔曼方程其实是线性方程组
把每个状态的方程排成一行,就得到一个 n 元线性方程组。n 是状态数。既然线性,就可以直接解。
为什么能这么写状态数小的时候这是最优解——一步到位、没有迭代误差。深度 RL 用它做不了,是因为 n 不可数(连续状态),而且 (I-γP)^{-1} 是 O(n³)。注意这个式子也说明:只要 γ<1,(I-γP) 一定可逆。
2. 压缩映射:为什么迭代一定会收敛
定义贝尔曼算子 T:给它一个值向量,按贝尔曼右边算出一个新向量。要证的是 T 把任意两个向量的距离缩短到 γ 倍以内。
为什么能这么写第二步能这么放,是因为 P 是随机矩阵(每行和为 1),所以它不会放大任何向量的最大绝对值。γ<1 时 T 是压缩映射,由巴拿赫不动点定理:存在唯一不动点,且从任意初值迭代都收敛到它。这就是值迭代的合法性证明,一行都不多。
3. 一旦换成 max,线性就没了
最优贝尔曼方程把「按策略加权」换成了「取最好的动作」。这一步让方程从线性变成分段线性。
为什么能这么写后果有三:① 不能写成 (I-γP)^{-1} 求逆;② 但 T 仍然是压缩的(max 也不放大距离),所以值迭代照样收敛;③ 解不再是「V 的线性函数」,而是「一族线性函数的上包络」——这就是为什么最优值函数有折点,也是为什么用平滑函数逼近它会有系统误差。
4. 策略迭代与值迭代,其实是一回事
策略迭代是「评估到底 → 改进一次」,值迭代是「评估一步 → 改进一次」。后者能行,靠的是策略改进定理:按 Q 的贪心选动作,新策略一定不比旧的差。
为什么能这么写证明思路:V^π(s) ≤ max_a Q^π(s,a) = Q^π(s,π'(s)) ≤ V^{π'}(s)。第一处是 max 的定义,第二处是对 π' 做一次贝尔曼展开再递归。所以「改进」这一步不会回退,循环必然停在最优。
5. max 引起的系统性过估计(这一条决定了 SAC 的写法)
当 Q 的估计有噪声时,max 会挑到「被高估得最厉害」的那个动作。所以估计的期望不是真值的 max,而是比它大。
为什么能这么写Jensen 不等式:max 是凸函数,凸函数的期望不小于期望的函数。偏多少取决于动作数和噪声:真值全为 0、10 个动作、噪声 σ=1 时,实测 E[max]=1.539(σ=0.5 时 0.769,σ=2 时 3.087,基本线性)。这就是 double Q 的动机:用两个独立估计,取小的那个把正偏压回去。
6. 为什么 γ=1 会麻烦,而不只是「不收敛」
γ=1 时 T 只是「非扩张」,不是「压缩」,不动点可能不唯一,迭代会停在一个平台上来回晃。
为什么能这么写有些任务 γ=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)。
- 从终点往回算:V(s2) = 1(终止状态,只拿即时奖励,没有后续)
- V(s1) = 0 + 0.9 × V(s2) = 0.9
- 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 轮,就变成了值迭代,运行结果一样,你可以自己验证这一点。
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 贪心得到的新策略逐状态不差于旧策略。因为改进的证明只用了一次贝尔曼展开,不需要评估收敛——所以评估一步也能改进,只是改进得少一点,这就是值迭代。