TARGET
学完后，你能从 MDP 模型推到 value iteration，并判断何时它根本不适用。
| 要掌握 | 原理本体 | 工程判断 |
|---|---|---|
| 最优 Bellman backup | 枚举模型的所有后继，对每个动作算期望后取最大。 | 有 P、R 才能直接做；只有日志／交互数据不行。 |
| 固定点与压缩 | V*=T*V*；γ<1 时 T* 会缩小任意两张 value 表的最大距离。 | 迭代阈值不是“训练 loss”，而是对固定点残差的近似控制。 |
| 策略提取 | 收敛后按 one-step lookahead 对每个状态 argmax。 | 价值表收敛与策略稳定应分别检查。 |
1 · START WITH THE MODEL
Value Iteration 的输入不是轨迹，是完整的 MDP 说明书。
设有限状态集合 S、动作集合 A，已知转移奖励联合分布 P(s′,r|s,a)。如果今天处于 s 并选 a，我们能列出所有可能 s′、r；若随后每步均采取最优动作，则：
Value Iteration 求的是“模型正确时的最优规划解”。它不从真实 interaction 学模型，也不处理未知 reward；若 P 错了，它会非常高效地得到错误答案。
2 · OPERATOR AND FIXED POINT
把右侧看成一个函数 T*，算法就有了精确目标。
V* = T*V*T* 接收任意猜测 V，产出一次“如果未来按该猜测估值、当前却做最优选择”的新猜测。真正的最优价值放进去后不再改变，因而是固定点。
关键定理不是“多迭代总会好”：在最大范数下，T* 满足 ||T*V−T*W||∞≤γ||V−W||∞。γ<1 时，每次应用最多把两份猜测的最大差距保留 γ 倍；因此只有一个固定点，且从任意初值持续迭代都向它靠近。
3 · ONE SWEEP, BY HAND
同步更新时，奖励如何一轮一轮向前传播？
有状态 A、B 和 terminal。A 只有 go：r=0 到 B；B 只有 finish：r=+10 到 terminal。γ=0.9，初始 V₀(A)=V₀(B)=0。同步 sweep 意味着第 k+1 轮所有右侧都读取旧的 Vk：
| sweep | B 的 backup | A 的 backup | 为什么 |
|---|---|---|---|
| V₁ | 10+0.9×0=10 | 0+0.9×V₀(B)=0 | A 读取旧表中的 B=0。 |
| V₂ | 仍为 10 | 0+0.9×V₁(B)=9 | 终点 reward 经 B 向前传播一跳。 |
| V₃ | 10 | 9 | 已经到达固定点。 |
若改为 in-place（异步）更新，先更新 B 再更新 A 时同一轮就可得到 A=9；这通常更快，但中间路径依赖遍历顺序。只要每个状态持续被更新，固定点不变。
4 · THE ALGORITHM
伪代码的每一行都是 T* 的一个实现细节。
V[s] = 0 for every state s
repeat:
delta = 0
for each nonterminal state s:
old = V[s]
action_values = []
for each action a:
q = sum(P[s_next, r | s, a] * (r + gamma * V[s_next]))
action_values.append(q)
V[s] = max(action_values) # (T*V)(s)
delta = max(delta, abs(old - V[s]))
until delta < theta
policy[s] = argmax_a expected_backup(s, a)
| 变量 | 真正含义 | 常见误用 |
|---|---|---|
q | 在当前 value 猜测下，先做固定动作 a 的 one-step lookahead。 | 把 q 当成环境采到的一条 reward；这里它是完整模型期望。 |
delta | 本轮中 V 改变的最大幅度，是近似停止信号。 | 把它当 TD error 或最优性缺口；它们相关但不相同。 |
theta | 计算预算与近似精度的选择。 | 认为小于 θ 就自动代表策略已在所有业务指标上最优。 |
5 · BOUNDARIES
它在什么地方被更现实的算法取代？
| 限制 | 原理原因 | 后续路线 |
|---|---|---|
| 模型未知 | ΣP 无法计算。 | MC / TD：用轨迹样本估计 backup。 |
| 状态极大或连续 | 无法枚举／存储每个 V(s)，完整 sweep 成本爆炸。 | 函数近似、DQN、actor-critic。 |
| 模型有偏差 | 精确规划会放大错误模型的系统偏差。 | 模型学习 + 不确定性、model-free 校正、MPC。 |
| γ 接近 1 | 压缩很弱，远期信息传播慢，数值尺度大。 | 更谨慎的归一化、终止设计与迭代容差。 |
SELF-CHECK
把算法读成因果，而不是名词。
01 · 为什么 max 要放在对后继环境随机性求和之外？
Agent 在环境随机响应前选动作，因此先为每个动作求其随机后果的期望，再从动作中选最好者。把 max 放进求和等于假设观察到环境随机结果后才可回头选当前动作。
02 · Value Iteration 与 Q-learning 最根本的差别是什么？
前者直接用已知 P、R 计算完整期望 T*；后者只拿到一次 (r,s′) 样本，用随机更新长期逼近同一最优 Bellman 固定点。
03 · 模型错误但迭代 delta→0，说明什么？
只说明已接近“错误模型”对应的固定点，并不证明真实环境表现好。必须区分规划收敛与模型正确性。
NEXT