价值迭代

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

图中的 $Q_k(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)v_k(s^{\prime })$ 是本轮由 $v_k$ 计算的一步动作评分，取最大值后才得到 $v_{k+1}(s)$。

压缩性保证数值函数最终忘掉初值。可是在 $\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 压缩证明覆盖。

按一次算术运算为常数代价计，稠密转移表的一轮完整备份耗时 $O(|S{|}^2|A|)$；若按非零转移枚举，则耗时与这些非零项的总数同阶。同步更新只需两张状态价值表，即模型之外的 $O(|S|)$ 工作空间；转移模型本身的存储分别为 $O(|S{|}^2|A|)$ 或非零项总数。若给定 $\epsilon >0$，要求贪心策略损失至多 $\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 网络继续替换函数表，却额外引入非线性逼近、相关样本和移动目标；经典价值迭代的压缩证明不能独自保证其稳定性。

离线拟合 Q 迭代公理库离线拟合 Q 迭代Fitted Q iteration · FQI · Batch fitted Q iteration在固定转移数据上交替冻结 Bellman 回归目标和拟合动作值，并将全域备份误差递推到最终贪心策略的性能界。把同一备份思想改写成固定转移集上的多轮回归。它复算两轮奖励传播，并证明全域备份误差怎样累积到策略损失；有限日志的训练拟合误差还需要额外条件才能接入该证明。