MDP 与 Bellman：把未来拆成下一步

一个机器人有两个选择：现在结束，拿 2 分；或者先充电，这一步 0 分，下一步可以拿 4 分。哪个好？取决于我们怎么计算“以后”。这个小问题已经包含了 RL 最重要的一层结构。

先说清环境给了什么

马尔可夫决策过程（MDP）包含状态、动作、转移分布、奖励（reward）和折扣。Markov 不是“过去没用”，而是给定当前状态和动作，下一状态与奖励的分布不再需要额外历史。

只看一张照片，可能分不清物体在靠近还是远离。连续几帧、历史记忆，或表示隐藏状态（hidden state）概率的信念状态（belief state），才能补足这些信息。

观测（observation）不自动等于完整状态。有限时域任务中，同一位置在“还剩 10 步”和“只剩 1 步”时价值可能不同；下面默认把剩余时间也放进状态，否则就应写成 $V_t^\pi(s)$。

下面默认转移规律不随时间改变，$\pi(a\mid s)$ 是仅依赖当前状态的平稳策略（policy）；若时间或策略记忆会影响后续决策，也须把它们纳入状态。

定义从现在开始的折扣回报（return）：

$$ G_t=\sum_{k=0}^{T-t-1}\gamma^k r_{t+k},\qquad V^\pi(s)=\mathbb E_\pi[G_t\mid s_t=s]. $$

这里 $T$ 是任务的真实终点，不是外部采样截止；约定 $G_T=V^\pi(s_T)=0$，终止奖励已计入最后一次转移。持续任务则令 $T=\infty$；奖励有界且 $\gamma<1$ 时，无穷和绝对收敛。$\gamma=1$ 可用于有限时域，但不能直接用于任意持续任务。

$Q^\pi(s,a)$ 固定第一步动作，后面继续按 $\pi$ 走；$V^\pi$ 还会对第一步动作取平均。因此 $V^\pi(s)=\mathbb E_{a\sim\pi}[Q^\pi(s,a)]$。

下面的 $r(s,a,s')$ 表示给定这次转移后的期望即时奖励；奖励本身也可以是随机的。

Bellman 不是新目标，只是拆开同一笔账

把 $G_t$ 的第一项拿出来：$G_t=r_t+\gamma G_{t+1}$。再用全期望公式（law of total expectation），先条件于下一状态：

$$ V^\pi(s)=\mathbb E_{a\sim\pi,\,s'\sim P} \left[r(s,a,s')+\gamma V^\pi(s')\right]. $$

这叫策略评估（policy evaluation）：评价一个给定策略。寻找最优策略时，动作不再按已有策略平均，而是选择最大的那个：

$$ V^*(s)=\max_a\mathbb E_{s'\sim P}[r+\gamma V^*(s')]. $$

$\max_a\mathbb E[\cdot]$ 不能随便写成 $\mathbb E[\max_a\cdot]$。后者仿佛先看见随机未来再选动作，给了决策者不该有的信息。

手算两次 value iteration

价值迭代（value iteration）从一张估值表开始：给“起点”和“充好电”都初始化为 0。每轮用上一轮的整张表更新：

奖励先传到离终点近的位置，再往前传。若 $\gamma=0.4$，充电路线只值 1.6，立即拿 2 分反而更好。这不是算法变笨了，而是目标改变了。

为什么表格版本能收敛

有限状态和动作、奖励有界、$0\le\gamma<1$ 时，最优 Bellman 算子是无穷范数下的压缩映射（contraction mapping）：

$$ \|TV-TW\|_\infty\le\gamma\|V-W\|_\infty. $$

理由只有两步：最大值的差不超过各项差的最大值；概率加权平均不放大最大误差。每更新一轮，两个估值表的距离最多剩原来的 $\gamma$ 倍，因此反复更新会靠近同一个固定点。

这个结论不是神经网络 DQN 的收敛证明。 采样误差、函数逼近（function approximation）和参数更新改变了问题。$\gamma=1$ 的有限时域可以用 backward induction；不能照搬上面的严格压缩结论。

Policy iteration：先评价，再换更好的动作

价值迭代每轮直接做最优 Bellman 更新。策略迭代（policy iteration）则先把当前策略的 $V^\pi$ 算好，再在每个状态选让 $Q^\pi(s,a)$ 最大的动作，得到新策略 $\pi'$。

为什么这一步不会变差？因为按原策略平均，不可能大于直接选最大值：

$$ T_{\pi'}V^\pi(s)=\max_aQ^\pi(s,a)\ge V^\pi(s). $$

利用 Bellman 算子的单调性，继续作用 $T_{\pi'}$，估值不会下降；在前述折扣条件下，极限是 $V^{\pi'}$，所以 $V^{\pi'}\ge V^\pi$。这就是精确策略改进（policy improvement）的理由。只做有限次估值更新、再用神经网络近似时，需要重新考虑误差，不能无条件照搬保证。

有环路时，为什么不是把奖励一直加下去？

前面的充电例子两步就结束。现在固定一个策略：在 A 每步得 1 分，有一半概率留在 A，一半到 B；在 B 每步得 2 分，下一步回到 A。令 $\gamma=0.5$，价值方程是：

$$ V_A=1+0.5(0.5V_A+0.5V_B),\qquad V_B=2+0.5V_A. $$

把第二式代入第一式，得到 $0.625V_A=1.5$，所以 $V_A=2.4,V_B=3.2$。这里评价的是一个固定策略，没有再对动作取最大值。

           50% 留在 A
               ↺
        A，奖励 1 ──50%──→ B，奖励 2
             ↑_________________|
                 100% 回到 A

写成矩阵就是 $V=r+\gamma P_\pi V$，即 $(I-\gamma P_\pi)V=r$。求解线性方程和反复应用 Bellman 更新，是解决同一个固定策略估值问题的两种办法。状态多时，显式存储和求解这个矩阵可能很贵；这也是采样更新有意义的原因。用线性特征时，也可以只解一个特征维度大小的小方程，见 LSTD。

残差小，到底能保证多少？

假设你已经算到某张表 $V$，检查发现 $\|TV-V\|_\infty\le\varepsilon$。利用压缩性和三角不等式：

$$ \|V-V^*\|_\infty\le\|V-TV\|_\infty+\|TV-TV^*\|_\infty \le\varepsilon+\gamma\|V-V^*\|_\infty. $$

移项得到 $\|V-V^*\|_\infty\le\varepsilon/(1-\gamma)$。当 $\gamma=0.9$、残差是 0.01，界为 0.1；$\gamma=0.99$ 时变成 1。折扣越接近 1，远期越重要，允许同样价值误差时就需要更小残差。

这个界要求整个状态空间上的真实 Bellman 残差。训练 batch 上 MSE 很小，不等于已经满足无穷范数条件；采样噪声和未覆盖状态都可能让这个检查失效。

试着换个前提

参考：RL 基础与 value 定义、Ernst 等（2005），§2：有限与无限时域。下一篇：不知道转移概率时，怎样从样本学 value？