动态规划、Monte Carlo 与时序差分

三类方法使用的信息不同

动态规划、Monte Carlo 和时序差分都估计价值，却不能只看更新公式的外形。动态规划假设已知完整环境模型 $p(s',r\mid s,a)$，对所有可能下一结果求期望；Monte Carlo 不需要模型，等待一条回合结束后使用实际完整回报；时序差分也不需要模型，只观察一步转移，并用当前价值估计自举未观察的未来。

三者对应不同误差来源。动态规划没有环境采样造成的更新方差，但若使用的是估计模型，会有模型偏差；Monte Carlo 目标来自真实轨迹，回合式同策略评价中不依赖当前价值自举，但长回报方差可能很大；TD 目标更短、可在线更新，却把尚未准确的价值估计放入目标，产生自举偏差和耦合。哪一种更好取决于模型可用性、回合长度、随机性和函数逼近，不能由一句“无偏”或“低方差”普遍排序。

本章先用表格有限 MDP 说明基本算法。大状态空间中的函数逼近会引入泛化、优化与稳定性问题，尤其离策略加自举时，经典表格收敛结论不能直接搬用。

已知模型下的迭代策略评估

给定策略 $\pi$，Bellman 期望算子为

迭代策略评估从任意有限初值 $V_0$ 开始，重复

有限折扣 MDP 中，$T^\pi$ 是 $\gamma$ 压缩，迭代收敛到唯一固定点 $V^\pi$。也可把 Bellman 方程写成线性方程直接求解，但矩阵分解在状态很多时成本高。迭代版本可以同步使用整张旧表，也可原地使用本轮已更新值；两者中间轨迹不同，更新顺序和停止规则必须记录。

策略改进与策略迭代

评估出 $V^\pi$ 后，对每个状态计算一步动作价值

若新策略在每个状态选择最大 $q_\pi(s,a)$ 的动作，策略改进定理保证新策略价值不低于旧策略。策略迭代交替进行策略评估和贪心改进，直到策略稳定。有限 MDP 中，精确评估与确定的并列动作规则会在有限策略集合中到达最优策略。

实际可在评估尚未完全收敛时改进，这称为广义策略迭代思想的一种形式。评估试图让价值适配当前策略，改进试图让策略对当前价值更贪心，两者交错推进。近似评估误差可能让动作反复切换；应固定 tie-breaking、残差阈值和最大 sweep 数，不能只以策略文字“看起来稳定”终止。

价值迭代直接逼近最优固定点

Bellman 最优算子为

价值迭代重复 $V_{k+1}=T^*V_k$，相当于把截断的策略评估与贪心改进合并。在有限、$\gamma<1$ 的情形，$T^*$ 也是压缩映射，迭代收敛到 $V^*$；最终策略从 $V^*$ 的一步贪心动作取得。若当前 Bellman 残差为 $\lVert T^*V-V\rVert_\infty$，可用残差与 $1-\gamma$ 控制价值误差，但高折扣时同样残差对应更松的界。

动态规划每次需要枚举相关状态、动作和下一结果。若模型未知，不能直接算这些期望；若状态巨大，即使模型已知也可能计算不可承受。用采样替代完整期望正是后续方法的入口。

Monte Carlo 用完整回报作目标

对同策略 $\pi$ 生成的一条完整回合，时刻 $t$ 的实际回报为

常数步长更新为

若对每个状态保存所有访问后的回报并取样本均值，在适当独立性或遍历、有限方差和访问充分条件下，均值可趋近 $V^\pi(s)$。first-visit 只用每回合首次访问，every-visit 使用所有访问；同一回合内样本相关，二者统计性质和计数规则不同。

Monte Carlo 不在目标中使用当前 $V$，所以称为不自举。代价是必须知道回合如何结束，较早状态的目标包含许多随机奖励，方差通常随跨度增大。持续任务若没有回合边界，不能直接等待“完整无穷回报”；需截断、改变目标或使用自举，而这些都会改变估计性质。

TD(0) 用一步样本和当前价值自举

Bellman 期望关系提示一步目标

TD error 与更新为

TD 可在每一步到达后立即更新，不必等待回合结束。目标中的下一状态价值由同一估计器给出，所以它会传播已有信息，也会传播估计误差。表格同策略 TD(0) 在适当访问与步长条件下可收敛到 $V^\pi$；这不表示每次随机 TD target 都等于真实回报。

同一轨迹上的 Monte Carlo 与 TD 目标

两者差异可在短轨迹中直接看到。Monte Carlo 把实际后续奖励全部纳入，TD(0) 用一步奖励加当前下一状态估计。若下一价值很准，TD 可以提前传播低方差信息；若它偏差很大，更新也会被带偏。

n-step 在完整回报与一步自举之间连续过渡

n-step target 为

若回合在 $n$ 步前真正终止，求和在终止处停止并删除 bootstrap 项。$n=1$ 是 TD(0)；$n$ 延伸到回合末就接近 Monte Carlo 回报。增大 $n$ 通常减少对当前价值的依赖，却纳入更多随机奖励；“偏差降低、方差升高”是常见趋势，不是对所有 MDP 和估计器的绝对定律。

前向 $\lambda$-return 把不同 $n$ 的 target 按几何权重组合。表格累积资格迹给出相应的在线后向视角：

$\lambda=0$ 退化为一步 TD；$\lambda$ 接近一会让一次 TD error 更广地分配给近期访问状态。累积迹、替换迹和函数逼近下的实现并不完全相同。本章只给出表格导论：每个新回合要重置迹，真实终止不再自举，时间截断则按声明目标决定。

同策略与离策略要区分数据来源

同策略评价中，生成数据的行为策略与被评价的目标策略相同。离策略评价则由行为策略 $\mu$ 收集轨迹，却希望估计目标策略 $\pi$。如果某状态动作满足 $\pi(a\mid s)>0$ 而 $\mu(a\mid s)=0$，数据中永远没有该动作，普通重要性修正也无法恢复，称为覆盖不足。

对完整轨迹，重要性比率会乘上若干项 $\pi(A_t\mid S_t)/\mu(A_t\mid S_t)$；长乘积可能产生极高方差。一步表格 TD 可使用当步比率修正更新，但仍需覆盖和合适步长。自归一化或截断比率可以降低方差，却引入偏差。离策略、函数逼近与自举结合时可能不稳定，不能把表格 TD 收敛结论无条件推广。

步长、访问与终止决定收敛边界

表格随机近似常要求每个相关状态被充分访问，并对状态相关步长满足 $\sum_t\alpha_t=\infty$、$\sum_t\alpha_t^2<\infty$ 等条件，才能在平稳环境中衰减噪声而持续修正。用访问次数倒数对应样本平均的一种形式。恒定步长不会精确消除随机波动，却能在环境缓慢变化时持续跟踪；过大容易振荡，过小会让早期误差长期残留。

终止处理必须来自任务语义。真正终止后的价值设为零；时间限制若只是观测截断，应从最后非终止状态继续 bootstrap，除非评价目标明确只计固定时长。批次填充、丢帧和采集停止都不是环境终止。MC 需要完整回报，缺失尾部不能静默当零；TD 可以自举，但估计质量取决于末状态价值。

在函数逼近下，同一参数同时影响多个状态，更新不再是独立表格平均。特征尺度、优化器、目标漂移与数据相关都会改变稳定性。应同时记录 TD error 分布、价值范围、Bellman 残差、访问计数和回报，而不是把损失下降等同策略更好。

评价必须锁定奖励和数据协议

算法比较应使用同一 MDP、折扣、初始分布、终止规则和奖励定义。动态规划若使用真实模型，应单列模型查询成本；若使用学习模型，则结果包含模型误差。MC 与 TD 应报告环境交互量、访问覆盖、多个随机种子、价值误差和最终策略回报，不能只比较一次平滑曲线。

奖励仍是任务代理，不代表未编码的安全或社会价值。即使价值估计完全准确，它也只准确回答当前奖励与约束下的问题。策略评价还应单列违规率、尾部风险和分布外状态，并核查策略是否通过奖励漏洞获得高回报。本章不提供虚构实验数值，所有数值例题均为明确给定的小型 MDP 手算。

三个常见误区

第一，“动态规划不用数据，所以不需要模型”。它不需要采样轨迹，却需要能枚举或计算转移—奖励期望的已知模型。

第二，“TD 一步目标方差低，所以一定优于 Monte Carlo”。TD 引入当前估计偏差与耦合；实际权衡取决于问题、步长、访问和函数逼近。

第三，“日志结束就把下一状态价值设为零”。只有真实任务终止才如此；采集截断和时间限制需要按继续任务的目标处理。

练习

关系与资源

• Markov 决策过程 提供价值、回报与 Bellman 方程。
• 大数定律 支持重复回报平均的收敛理解。
• 动态规划 提供固定点迭代与分阶段求解思想。
• Q-learning 将离策略 TD 目标用于动作价值控制。
• 强化学习综合复习 汇总估计、控制和评价边界。