价值迭代

一次更新允许看一步并假定之后按旧估计行事；两次更新允许最优选择向前传播两步。最大化和期望在每轮被完整执行，远处奖励逐层传回上游。与策略迭代不同，价值迭代不先把任何一张策略评估到底，而是每轮同时推进求值与改进。

压缩性保证数值函数最终忘掉初值。可是在 $\gamma$ 接近一时，忘记得很慢，而且小残差对应的价值误差会被 $1/(1-\gamma )$ 放大；这解释了长时域控制为何比公式表面更难。

考虑状态 $s_0,s_1$ 和终止态。$s_0$ 可收割得 $5$ 后终止，或培育得 $0$ 后到 $s_1$；$s_1$ 出售得 $8$ 后终止。取 $\gamma =4/5$、$v_0=0$。第一次更新只看即时奖励：

第二次更新把出售价值传回 $s_0$：

此后数值不变，贪心策略选择培育。这里两轮恰好收敛是无环有限时域结构造成的；含自环的一般折扣 MDP 通常只渐近收敛。

若更新只覆盖一部分状态，必须保证每个相关状态被无限次更新且陈旧信息受控，才能引用异步价值迭代结论。若把期望换成单个样本，得到的是随机算法而非同一确定性迭代。$\gamma =1$、奖励无界或平均奖励目标也不由上述 sup-norm 压缩证明覆盖。

价值迭代每轮的主要代价是对所有状态—动作—下一状态做 Bellman backup；稀疏转移、优先队列或异步更新可减少无效计算。若要求贪心策略损失至多 $\epsilon$ 且 $\gamma >0$，充分的停止条件是 ${\delta }_k\le \epsilon (1-\gamma )/(2\gamma )$，而不是凭数值“看起来稳定”停止；$\gamma =0$ 时贪心即时奖励本已最优。

在模型未知的表格控制中，Q-learning公理库Q-learning 算法Q-learning · Watkins Q-learning · Q 学习用下一状态动作值的最大值构造离策略 TD 目标，随机近似最优动作值 Bellman 不动点。用观测转移构造最优 Bellman 更新的随机近似。深度 Q 网络继续替换函数表，却额外引入非线性逼近、相关样本和移动目标；经典价值迭代的压缩证明不能独自保证其稳定性。