RL 数学 Note 2：贝尔曼最优方程、值迭代与策略迭代

在 Note 1 中，我们讨论了固定策略下的值函数与贝尔曼期望方程。本篇进入强化学习中真正的控制问题：不是评估某条给定策略，而是在所有策略中找到最优策略。

仍然固定在有限状态、有限动作、折扣因子 $\gamma\in(0,1)$ 的 MDP 框架下。

1. 最优值函数

定义最优状态值函数与最优动作值函数：

v^*(s):=\sup_{\pi}V^{\pi}(s),

q^*(s,a):=\sup_{\pi}Q^{\pi}(s,a).

它们分别表示：

在状态 $s$ 出发时，理论上能达到的最大长期回报；
在状态 $s$ 先做动作 $a$ 之后，理论上能达到的最大长期回报。

如果一条策略 $\pi^*$ 满足

V^{\pi^*}(s)=v^*(s),\qquad \forall s\in\mathcal{S},

那么它就是最优策略。

2. 贝尔曼最优方程

对于最优值函数，下一步不再是“按既定策略求平均”，而是“在所有动作里取最大”。因此有

v^*(s)=\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v^*(s')\right].

这就是贝尔曼最优方程。

对应的动作值形式为

q^*(s,a)=r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\max_{a'}q^*(s',a').

定义最优贝尔曼算子

(Tv)(s):=\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v(s')\right].

于是贝尔曼最优方程可以简洁地写成

v^*=Tv^*.

所以最优控制问题再次被转化成了一个不动点问题，只不过这次算子从 $T^{\pi}$ 变成了“带最大化”的 $T$ 。

3. 值迭代

最直接的做法就是从任意初值出发反复套用最优算子：

v_{k+1}=Tv_k.

这就是值迭代。

写成分量形式就是

v_{k+1}(s)=\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v_k(s')\right].

直观上，它在做一件很朴素的事情：

当前先假设自己已经知道“未来状态的价值”是 $v_k$ ；
再基于这个假设，对每个状态挑一个当前最优动作；
更新得到新的价值估计 $v_{k+1}$ 。

随着迭代继续，这个“对未来价值的估计”会逐渐自洽，最终收敛到真正的最优值函数。

4. 为什么值迭代会收敛

关键结论是：最优贝尔曼算子 $T$ 在无穷范数下依然是 $\gamma$ -压缩映射。

给定任意两个向量 $v,w$ ，对每个状态 $s$ ，有

(Tv)(s)=\max_a F_a(v),\qquad (Tw)(s)=\max_a F_a(w),

其中

F_a(v):=r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v(s').

由于最大值算子是 1-Lipschitz 的，

|(Tv)(s)-(Tw)(s)|\le \max_a |F_a(v)-F_a(w)|.

于是

|(Tv)(s)-(Tw)(s)| \le \gamma\max_a\sum_{s'}P(s'\mid s,a)|v(s')-w(s')| \le \gamma\|v-w\|_{\infty}.

再对所有状态取上确界，就得到

\|Tv-Tw\|_{\infty}\le \gamma\|v-w\|_{\infty}.

因此由 Banach 不动点定理可知：

$T$ 有唯一不动点；
这个不动点就是某个向量 $v^*$ ；
从任意初值出发，值迭代都收敛到 $v^*$ 。

也就是说，值迭代并不是经验上的“常常有效”，而是严格收敛到唯一解。

5. 为什么这个不动点就是“最优”的

收敛到某个不动点还不够，我们还需要证明这个不动点确实对应最优策略。

5.1 先证明它至少不差于任何固定策略

对于任意策略 $\pi$ ，定义

(T^{\pi}v)(s):=\sum_a\pi(a\mid s)\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v(s')\right].

显然对任意 $v$ 都有

T^{\pi}v\le Tv,

因为“按策略取加权平均”不可能超过“直接取最大值”。

令 $v^*=Tv^*$ ，则

T^{\pi}v^*\le Tv^*=v^*.

又由于 $T^{\pi}$ 单调，反复作用可得

(T^{\pi})^k v^*\le v^*.

令 $k\to\infty$ ，左边收敛到策略值函数 $v^{\pi}$ ，所以

v^{\pi}\le v^*.

这说明 $v^*$ 至少是一个对所有策略都成立的上界。

5.2 再证明有策略能真正达到它

对每个状态选取一个贪心动作

\pi^*(s)\in\arg\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v^*(s')\right].

那么按照定义，

T^{\pi^*}v^*=Tv^*=v^*.

但对于固定策略 $\pi^*$ ，贝尔曼算子 $T^{\pi^*}$ 的不动点唯一，因此

v^*=v^{\pi^*}.

结合上一步的 $v^{\pi}\le v^*$ ，可知

v^{\pi}\le v^{\pi^*},\qquad \forall \pi.

所以 $\pi^*$ 就是最优策略，而 $v^*$ 确实是最优值函数。

这一步非常重要：贝尔曼最优方程的解，不只是一个形式上的不动点，而是真正的最优控制解。

6. 策略迭代

值迭代是直接对最优算子做不动点迭代。另一条更结构化的路线是：

先固定一条策略，精确评估它；
再基于当前值函数做一次贪心改进；
重复这个过程。

这就是策略迭代。

6.1 算法步骤

给定初始策略 $\pi_0$ ，重复以下两步：

策略评估：求解

v^{\pi_k}=T^{\pi_k}v^{\pi_k}.

也就是解线性方程

(I-\gamma P^{\pi_k})v^{\pi_k}=r^{\pi_k}.

策略改进：定义新策略

\pi_{k+1}(s)\in\arg\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v^{\pi_k}(s')\right].

如果某次改进后策略不再变化，那么算法停止。

6.2 为什么策略改进是有效的

令

\pi'(s)\in\arg\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v^{\pi}(s')\right].

则按定义有

T^{\pi'}v^{\pi}=Tv^{\pi}\ge T^{\pi}v^{\pi}=v^{\pi}.

由于 $T^{\pi'}$ 单调，继续迭代得到

(T^{\pi'})^k v^{\pi}\ge v^{\pi}.

令 $k\to\infty$ ，左边收敛到 $v^{\pi'}$ ，因此

v^{\pi'}\ge v^{\pi}.

这就是策略改进定理：对当前值函数做贪心，不会让策略变差。

如果某个状态上的贪心选择严格变好，那么通常会得到严格改进；如果所有状态上都没有改进空间，那么当前策略已经是最优策略。

6.3 为什么策略迭代能找到最优策略

因为有限 MDP 中策略总数有限，而每一次真正发生变化的策略改进都会带来不下降的值函数序列

v^{\pi_0}\le v^{\pi_1}\le v^{\pi_2}\le \cdots

所以它不可能无限严格改进下去。算法最终停在某条策略 $\bar\pi$ 上，而“停止”意味着

\bar\pi(s)\in\arg\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v^{\bar\pi}(s')\right],\qquad \forall s.

等价地，

T^{\bar\pi}v^{\bar\pi}=Tv^{\bar\pi}=v^{\bar\pi}.

于是 $v^{\bar\pi}$ 同时满足策略贝尔曼方程和最优贝尔曼方程，因此 $\bar\pi$ 必为最优策略。

7. 值迭代与策略迭代的区别

这两个算法都建立在贝尔曼理论上，但思路略有不同。

7.1 值迭代

每一步直接对最优算子做更新；
单步成本较低；
需要多次迭代才能把值函数逼近到足够精确；
常用于状态空间较大、不能每轮都精确做策略评估的情形。

7.2 策略迭代

每轮先精确评估当前策略，再整体改进；
单轮代价较大，因为要求解线性方程或做充分的策略评估；
但往往轮数较少；
在中小规模问题里常常收敛得很快。

从本质上说，值迭代是在“值函数空间”里做压缩映射的不动点迭代；策略迭代则是在“策略空间”和“值函数空间”之间交替前进。

8. 小结

这一篇的核心结论是：

最优值函数满足贝尔曼最优方程 $v^*=Tv^*.$
最优贝尔曼算子 $T$ 是压缩映射，因此值迭代 $v_{k+1}=Tv_k$ 从任意初值都收敛到唯一不动点。
这个唯一不动点不只是“某个解”，而是所有策略值函数的上界，并且能被贪心策略达到，所以它就是最优值函数。
策略迭代通过“评估 + 贪心改进”反复进行，依靠策略改进定理最终收敛到最优策略。

到这里，经典动态规划视角下的 RL 数学骨架就很清楚了：

固定策略时，问题是贝尔曼期望方程；
优化策略时，问题是贝尔曼最优方程；
算法层面则对应值迭代与策略迭代。

这也是之后理解 Q-learning、DQN、Actor-Critic 等方法的起点。