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

层级：B｜建议先修：05-22、08-09

强化学习中估计价值函数有三条基本路线：已知环境模型时使用动态规划；等待完整回报后使用 Monte Carlo；每走一步就用当前估计更新的时序差分方法居于两者之间。

1. 策略评估问题

给定策略 $\pi$ ，目标是估计

V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s].

不同方法的差别主要在于：是否知道转移模型、更新目标使用多少步真实奖励、是否用已有估计进行自举（bootstrapping）。

2. 动态规划：已知模型

迭代策略评估反复应用 Bellman 期望更新：

V_{k+1}(s)= \sum_a\pi(a\mid s) \sum_{s',r}p(s',r\mid s,a) [r+\gamma V_k(s')].

每次使用完整的模型期望，并用 $V_k$ 估计未来价值，所以它是自举方法。

3. 策略迭代

策略迭代交替执行：

策略评估：求或近似求 $V^\pi$ ；
策略改进：

\pi'(s)\in\arg\max_a \sum_{s',r}p(s',r\mid s,a)[r+\gamma V^\pi(s')].

策略改进定理保证新策略不差于旧策略。有限 MDP 中重复过程最终到达最优策略。

4. 值迭代

值迭代把评估和改进压缩为一次 Bellman 最优更新：

V_{k+1}(s)=\max_a \sum_{s',r}p(s',r\mid s,a)[r+\gamma V_k(s')].

收敛后对 $V^*$ 贪心即可得到最优策略。

5. Monte Carlo 价值估计

MC 不需要转移模型，而是从实际或模拟轨迹中等待完整回报 $G_t$ ，再更新

V(S_t)\leftarrow V(S_t)+\alpha[G_t-V(S_t)].

若对所有观察到的回报取样本平均，就是对条件期望的经验估计。

MC 目标 $G_t$ 在给定状态下通常是无偏样本，但方差可能很大，而且必须等到回合结束，因而天然适合 episodic 任务。

6. 首次访问与每次访问 MC

首次访问 MC：一条轨迹中只用状态第一次出现后的回报；
每次访问 MC：使用该状态每次出现后的回报。

在常见条件下二者都可一致收敛，但有限样本行为不同。

7. TD(0)

时序差分一步后就更新：

V(S_t)\leftarrow V(S_t) +\alpha\underbrace{[R_{t+1}+\gamma V(S_{t+1})-V(S_t)]}_{\delta_t}.

$\delta_t$ 称为 TD 误差。目标

R_{t+1}+\gamma V(S_{t+1})

同时包含真实的一步奖励和下一状态的当前估计，因此 TD 是无模型、自举、在线方法。

8. n 步回报

n 步回报为

G_t^{(n)}= R_{t+1}+\gamma R_{t+2}+\cdots +\gamma^{n-1}R_{t+n}+\gamma^nV(S_{t+n}).

当 $n=1$ 时是 TD(0) 目标；当 $n$ 延伸到回合末且末端价值为 0 时，变成 MC 回报。 $n$ 控制偏差与方差的折中。

9. TD( $\lambda$ ) 与资格迹

$\lambda$ -回报把不同 n 步回报加权平均：

G_t^\lambda=(1-\lambda) \sum_{n=1}^{\infty}\lambda^{n-1}G_t^{(n)}.

前向视角使用多个 n 步目标；后向视角维护资格迹，把当前 TD 误差按衰减权重分配给近期访问的状态或参数。 $\lambda=0$ 接近一步 TD， $\lambda\to1$ 接近 MC。

10. SARSA

在动作价值上使用实际采取的下一个动作：

Q(S_t,A_t)\leftarrow Q(S_t,A_t) +\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)].

它评价并改进当前行为策略，属于 on-policy 方法。

11. Q-learning

Q-learning 更新为

Q(S_t,A_t)\leftarrow Q(S_t,A_t) +\alpha[R_{t+1}+\gamma\max_aQ(S_{t+1},a)-Q(S_t,A_t)].

数据可由探索策略生成，但目标使用贪心动作，因此是 off-policy 方法。在有限表格情形、充分探索和合适步长条件下可收敛到 $Q^*$ 。

12. 探索与利用

若总选择当前最优动作，可能永远发现不了更好的动作。 $\varepsilon$ -greedy 以 $1-\varepsilon$ 选择贪心动作，以 $\varepsilon$ 随机探索。探索策略、覆盖条件和数据分布都会影响收敛。

13. 函数逼近的风险

状态空间大时用参数函数 $V_\theta,Q_\theta$ 泛化。自举、off-policy 和函数逼近结合时可能不稳定，常称“致命三角”。深度 Q 网络使用经验回放、目标网络等技巧缓解目标相关和非平稳问题，但不提供普遍收敛保证。

14. 三类方法比较

方法	需要模型	自举	等待回合结束	典型特点
动态规划	是	是	否	使用完整期望，计算量大
Monte Carlo	否	否	通常是	目标偏差小、方差大
TD	否	是	否	在线、方差较低，但目标有偏

15. 易错点

这里的 Monte Carlo 指完整回报采样，不等同于 MCMC。
TD 误差是针对当前估计的暂时误差，不是环境奖励本身。
off-policy 不等于完全不需要探索或数据覆盖。
Q-learning 的更新目标是贪心的，但行为策略仍可探索。

常见问答

Q1：TD 的目标有偏，为什么还能有效？
它以一定偏差换取更低方差和在线更新；在表格及适当条件下，其随机近似仍可收敛到正确不动点。

Q2：MC 一定优于 TD 吗？
不一定。MC 无需自举但方差高、更新延迟；TD 能从不完整序列学习，常有更好的样本效率。

Q3：SARSA 为什么更“保守”？
它的目标包含行为策略实际可能采取的探索动作，因此学习到的价值考虑了探索风险；Q-learning 的目标假设后续贪心。

Q4：值迭代何时停止？
常在连续两次价值更新的最大差小于阈值时停止，再提取贪心策略；阈值可结合 $\gamma$ 给出误差界。

练习

写出 TD(0) 的目标和 TD 误差。
比较 SARSA 与 Q-learning 下一状态部分的差别。
当 $n$ 增大时，n 步回报的偏差与方差通常如何变化？
为什么 Q-learning 即使目标策略贪心，行为策略仍需探索？

答案与提示

目标为 $R_{t+1}+\gamma V(S_{t+1})$ ，误差为目标减 $V(S_t)$ 。
SARSA 使用实际下一动作 $A_{t+1}$ ；Q-learning 对下一状态所有动作取最大值。
通常自举减少，偏差下降，但累积随机奖励使方差上升。
未被访问的状态动作对无法获得可靠估计；充分覆盖是学习最优价值的前提。