RL COLLECTION / 03 / LEARNING FROM EXPERIENCE

DP、Monte Carlo 与 TD：
价值究竟从哪里学来？

Bellman 方程告诉我们正确的固定点是什么；这一课讨论三种到达它的路径：枚举模型、等完整回报，或用下一步估计提前更新。

FIRST TERMS · THREE ROUTES

这三个缩写分别在说什么？

缩写 / 全称一句话含义先记住的使用条件
DP
Dynamic Programming
动态规划		利用已知模型，把长期问题递归拆成更小的价值问题。你知道环境怎样响应动作。
MC
Monte Carlo
蒙特卡洛		跑完很多随机完整轨迹，用实际回报的平均逼近期望。你能等到一局结束。
TD
Temporal Difference
时序差分		看见一步反馈，就用“下一步估计”提前改正当前估计。你希望边交互边学习，不等终局。

完整解释可随时回到DP、MC、TD术语卡。后文不会默认你已懂这些英文。

LEARNING TARGET

学完后，你能从信息条件反推该用哪种价值学习方式。

完成目标直接应用它给后续什么能力
按“有无模型、能否等终局、是否可在线更新”区分 DP、MC、TD。面对仿真器、日志数据、持续在线服务时，知道它们各自适用的学习信号。理解 SARSA / Q-learning 的 TD target 与 PPO rollout 的 MC/GAE 取舍。
解释 bootstrap 的速度收益与误差传播代价。诊断长回合回报传播慢、target 抖动、采样方差过大等问题。为 n-step、eligibility trace、GAE、replay 和 target network 铺路。
你会联想到什么

模型已知的游戏规划偏向 DP；一段完整离线轨迹可以做 MC；实时控制与服务反馈通常需要 TD 式的边交互边更新。

ONE CASE, THREE UPDATES

同一条经验，三种方法到底喂给 value 什么？

考虑一条确定性轨迹：A ─(r=0)→ B ─(r=10)→ terminal，γ=0.9。当前 V(A)=0，V(B)=0。三种方法都想让 V(A) 最终接近 9、V(B) 接近 10，但更新时机和 target 不同。

方法给 A 的 target第一轮之后发生什么为什么
DP（模型已知）0+0.9V(B)同步 sweep 中 A 仍为 0；下一 sweep 才接到 B 的 10。使用完整模型和旧表做期望 backup。
MC（episode 完成）G(A)=0+0.9×10=9本局结束立刻把 A 推向 9。已经看到了真实完整未来。
TD(0)0+0.9V(B)=0看到 A→B 时 A 先不动；看到 B→terminal 后 B 先更新，后续访问才传回 A。只看一步真实 reward，剩余未来用当前估值 bootstrap。

这张表解释一个关键现象：TD 通常不需要等终局，但它传播远期奖励可能需要多次访问；MC 一次就能把整条轨迹的奖励分给早期状态，但需要等完整 episode。

ALGORITHM READING

三段伪代码：看 target，别先记名字。

1. Value Iteration（有模型、直接改善）

repeat:
    for each state s:
        V(s) = maxₐ Σₛ′,ᵣ p(s′,r|s,a)[r + γV(s′)]
until largest change < θ

2. First-visit Monte Carlo（无模型、等终局）

generate one full episode with policy π
for each state s first visited in this episode:
    G = discounted rewards from this visit to terminal
    V(s) = average of every recorded G for s

3. TD(0)（无模型、每步自举）

for every transition (s, a, r, s′):
    target = r + γV(s′)  # terminal 时 V(s′)=0
    V(s) = V(s) + α * (target - V(s))
    s = s′

三段程序的骨架极像，唯一核心差异是 target 从何而来。以后判断新算法，先找它的 target、数据来源、是否 bootstrap、是否要求模型。

PREREQUISITES

先把“方程正确”和“怎样从数据学到它”分开。

必须你应能回答去哪里补
MDP 与 trajectory一条 transition 里有什么：s、a、r、s′？Lesson 01
Value / Bellman / TD error为什么 r+γV(s′) 可以作为一步 target？Lesson 02
期望与样本平均“模型的完整期望”和“很多真实回报的平均”有什么不同？Lesson 00

ONE QUESTION, THREE ANSWERS

目标相同，信息来源不同。

三种方法都想估计某个策略的 Vπ，都围绕“当前价值应与未来回报一致”这件事。真正的分歧只有两个：你是否知道环境模型，以及 target 要不要等真实 episode 走完。

same question: how good is state s under policy π?Dynamic Programmingneed: full model P, Rtarget = Σ p[r + γV(s′)]对所有状态做期望 backup没有采样噪声，成本高Monte Carloneed: completed episodetarget = observed Gₜ用完整样本回报做平均无 bootstrap，方差高TD(0)need: one transitiontarget = r + γV(s′)从下一步估计立即更新有 bootstrap，方差低more sampled experience / less exact model knowledge
先记住这句

DP 是“已知世界，做期望”；MC 是“走完整局，做平均”；TD 是“走一步，用估计补未来”。后续控制算法只是把它们的 value evaluation 接到“改策略”循环中。

ROUTE 1 · MODEL KNOWN

动态规划：在模型里反复做 backup。

动态规划（DP）不是一个神秘算法名，而是一类利用递归结构解决子问题的方法。在 tabular MDP 中，如果你知道每个 (s,a) 的转移概率 P 和奖励 R，就不必真的去环境中采样；可以对每个可能后继做精确期望。

Policy evaluation：固定 π，把 Vπ 算出来。

Vk+1(s) ← Σₐ π(a|s) Σs′,r p(s′,r|s,a)[r + γVk(s′)]一次 sweep 是遍历所有状态各更新一次。反复 sweep，直到最大改变量 maxs|Vk+1(s)−Vk(s)| 小于阈值 θ。

这里的“←”不是等号：右侧是旧估计，左侧写回新估计。同步更新会等整轮结束再覆盖；in-place 更新可立即用新值，通常更快但计算顺序会影响中间过程。二者的固定点相同。

Value iteration：评估与改进揉成一步。

Vk+1(s) ← maxₐ Σs′,r p(s′,r|s,a)[r + γVk(s′)]把固定策略下的加权平均换成最大化，表示每一步都假设接下来会继续最优地选动作。
DP 的优点DP 的限制它仍然重要的原因
使用完整期望，无采样方差；在小型 tabular 问题可得到精确基准。需要知道模型且要遍历整个状态空间；大状态空间很快不可承受。它提供最干净的“正确答案”和 Bellman backup 原型，是理解后续方法的参照物。

ROUTE 2 · FULL EPISODE

Monte Carlo：不用模型，等结果真的发生。

MC 不问 P 是什么。它先用当前策略跑完一局，再把每个访问过状态之后的真实折扣回报 Gₜ 当作训练目标。因此最朴素的 first-visit MC 价值估计就是样本均值：

V(s) ← V(s) + (1 / N(s)) [Gₜ − V(s)]N(s) 是状态 s 被用于更新的次数。这个递推式等价于保存所有 Gₜ 后取平均，但不需要保存全部历史。

例如同一状态 s 在三局之后分别获得 G=2、8、5，则当前估计为 (2+8+5)/3=5。它的 target 是完整真实 return，不依赖 V(s′)，所以不会把“后继估计错了”的 bootstrap bias 直接写进 target。

First-visit MC

一条 episode 内，状态 s 第一次出现时才更新一次。便于分析，也避免同一局内强相关重复计数。

Every-visit MC

一条 episode 中每次遇到 s 都更新。两者在常规条件下都能收敛到正确期望，有限样本时路径不同。

MC 的代价

必须等 episode 终止。对于对话、持续控制等极长或没有自然终点的任务，这会让 credit assignment 很慢；而随机环境中完整 Gₜ 可能波动很大，导致更新高方差。

ROUTE 3 · ONE STEP

TD(0)：还没看到结局，就先校正今天。

TD 是 Temporal-Difference 的缩写。它看到一条 transition (sₜ,aₜ,rₜ₊₁,sₜ₊₁) 立刻构造 target，而不是等待 Gₜ：

V(sₜ) ← V(sₜ) + α[rₜ₊₁ + γV(sₜ₊₁) − V(sₜ)]方括号就是 TD error δₜ。它比较“当前预测”与“一步奖励加后继预测”。

关键动词是bootstrap（自举）：目标的一部分来自自己当前的估计 V(sₜ₊₁)。这使 TD 能在线更新，也让一个值函数的错误可能影响别处。

same trajectory: sₜ → sₜ₊₁ → sₜ₊₂ → terminalsₜsₜ₊₁sₜ₊₂terminalrₜ₊₁rₜ₊₂rₜ₊₃MC target for sₜ uses every future reward: GₜTD target stops after one reward, then uses V(sₜ₊₁)

TD(0) 的 “0” 表示只展开 0 个额外真实奖励后立刻 bootstrap。下一层 n-step TD 会在真实样本和 bootstrap 之间调节；这条连续谱最终会通往 eligibility traces 与 GAE。

WHY THE UPDATES CAN WORK

三种算法不是“反复试试”，而是在用不同证据逼近同一个固定点。

方法它相信的数学机制需要的关键条件条件被破坏时
DPBellman 算子 T 把任意价值函数映射到新的 backup；当 0≤γ<1 时，T 会把两个价值估计的最大差距至少缩小 γ 倍（压缩映射）。持续 sweep 因而走向唯一固定点 V=T(V)。模型 P、R 正确；遍历所有相关状态；折扣 γ<1（或有合适的 episodic 条件）。模型错时，算法会稳定地收敛到“错误模型”的答案；状态空间太大时无法完整 sweep。
MC固定策略下，同一状态之后的完整回报 G 是真实 return 的随机样本；访问次数趋多时，样本均值按大数定律逼近期望 Vπ(s)。能产生完整 episode；状态被反复访问；策略与环境足够稳定。超长／不终止任务不能及时更新；稀疏或高随机回报会使有限样本方差很大。
TD每一步用带噪的一步 Bellman target 做随机逼近；单次 target 不等于完整期望，但在合适访问与步长下，平均更新可逼近 Bellman 固定点。足够覆盖、适当步长、固定策略的表格设定；数据相关性不能无限放大误差。bootstrap 会传播错误；再叠加函数近似与 off-policy 学习时可能不稳定。
DP：Vk+1 = T(Vk)，且 ||T(V)−T(W)||∞ ≤ γ||V−W||∞
MC：V(s) ≈ (1/N) Σi=1N G(i)
TD：V(s) ← V(s)+α[ sample of T(V)(s) − V(s) ]三行看似不同：DP 直接算期望；MC 等完整样本后平均；TD 用一步样本近似期望。但它们都围绕同一个“当前价值应与 Bellman 定义一致”的目标。
这里最重要的边界

“方程有固定点”与“某段代码能在有限数据上稳定到它”是两件事。前者是算法目标，后者需要检查模型、覆盖、步长、函数表示和数据分布。后面的 DQN、PPO 并没有逃离这个问题，只是在更复杂的设置中控制它。

THE TRADE-OFF

不是“谁更先进”，而是偏差、方差与可用信息的取舍。

方法target模型需求bootstrap典型统计特征可何时更新
DP完整期望 backup需要通常是无环境采样方差；模型错则系统性偏差。有模型即可。
MC完整 Gₜ不需要否无 bootstrap 偏差；完整回报方差往往大。episode 结束后。
TD(0)r+γV(s′)不需要是通常方差更低；target 带当前估计偏差。每一条 transition 后。

“TD 低方差、MC 无偏”是非常有用的入门心智模型，但不是脱离条件的绝对承诺：函数逼近、off-policy 数据、有限样本和不收敛训练都会改变实际表现。我们用它来判断算法设计，而不是替代实验验证。

CHECK YOUR UNDERSTANDING

先判断信息条件，再选学习路线。

01 · 已知一个小型棋盘游戏全部转移规则，但还没有采集轨迹。三种方法中哪种可以立即更新所有状态？

DP。因为它有 P 和 R，可以直接对每个状态的后继做期望 backup，不需要等真实 episode 产生。

02 · MC 为什么不需要 V(s′)，却要等待终局？

MC 的 target 是已实现的 Gₜ。只有所有未来 reward 都发生后，Gₜ 才可知；因此它不依赖后继价值估计，也就不能在中途完成完整 target。

03 · TD(0) 中 r=−1、γ=0.9、V(s′)=8、V(s)=4，α=0.5。更新后 V(s) 是多少？

target=−1+0.9×8=6.2，δ=6.2−4=2.2。更新后 V(s)=4+0.5×2.2=5.1。

ALGORITHM DEEP DIVES

不要只在一张对比表里认识算法；逐个打开它们的推导链。

Value Iteration 深潜 →模型、最优 Bellman 算子、压缩映射、sweep、收敛与模型偏差边界。Monte Carlo 深潜 →完整 return、增量样本均值、首次访问、MC control 与重要性采样。TD(0) 深潜 →bootstrap、TD error、n-step 谱、收敛条件和函数近似前的边界。

READ BEFORE NEXT LESSON

下一课：从“评估”走向“控制”。

Sutton & Barto · Chapter 4–6 ↗阅读关键词：policy iteration、value iteration、first-visit MC、TD(0)。回看 Lesson 02：价值与 Bellman若 target、TD error 或 optimality equation 还不熟，先回到上一课。