RL 学习笔记（6）：时序差分学习 • Axi's Blog

本内容暂时为 PPT 转述，后续会进行修编

时序差分学习 (Temporal-Difference Learning, TD Learning)#

TD 学习概述#

动机：结合 DP 和 MC (Page 3)
- DP (动态规划)：使用自举 (Bootstrapping)，即基于其他状态的估计值来更新当前状态的估计值。需要完整模型。更新基于期望。 $V(S_t) \leftarrow \mathbb{E}_\pi[R_{t+1} + \gamma V(S_{t+1})]$
- MC (蒙特卡洛)：无模型，直接从完整经验片段中学习。更新基于实际观测到的完整回报 $G_t$ 。不使用自举。 $V(S_t) \leftarrow V(S_t) + \alpha [G_t - V(S_t)]$
- TD 学习：目标是结合两者的优点：
  - 无模型：像 MC 一样，直接从经验中学习，不需要知道环境动态 $\mathcal{P}, \mathcal{R}$ 。
  - 自举：像 DP 一样，使用当前对后续状态价值的估计值来更新当前状态的价值估计，而不需要等待片段结束。
核心思想 (Page 6)：TD 学习在每一步之后，使用观测到的立即奖励 $R_{t+1}$ 和下一状态 $S_{t+1}$ 的当前价值估计 $V(S_{t+1})$ 来形成一个目标值 (TD Target)，然后用这个目标值来更新当前状态 $S_t$ 的价值估计 $V(S_t)$ 。
TD(0) 更新规则 (最简单的 TD 算法) (Page 6, 9)： $V(S_t) \leftarrow V(S_t) + \alpha \underbrace{[ \overbrace{R_{t+1} + \gamma V(S_{t+1})}^{\text{TD Target}} - V(S_t) ]}_{\text{TD Error } \delta_t}$
- TD 目标 (TD Target): $R_{t+1} + \gamma V(S_{t+1})$ 。这是对未来回报 $G_t$ 的估计，它只用了一步的真实奖励 $R_{t+1}$ 和一步的价值估计 $V(S_{t+1})$ 。
- TD 误差 (TD Error) $\delta_t$ : $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ 。它衡量了当前估计 $V(S_t)$ 与基于下一步信息的更好估计 (TD Target) 之间的差异。可以看作是价值估计的“预测误差”。
自举与采样 (Bootstrapping and Sampling) (Page 8)：TD 学习的特点：
- 采样 (Sampling)：像 MC 一样，更新是基于实际发生的转移 $(S_t, A_t, R_{t+1}, S_{t+1})$ ，而不是像 DP 那样考虑所有可能的转移。
- 自举 (Bootstrapping)：像 DP 一样，更新目标中包含了当前的价值估计 $V(S_{t+1})$ ，而不是像 MC 那样依赖最终的实际回报 $G_t$ 。

TD 预测 (TD Prediction)#

TD 预测的目标是：估计给定策略 $\pi$ 的状态价值函数 $v_\pi$ 。

TD(0) 算法 (用于估计 $v_\pi$ ) (Page 10, 11)：

输入: 策略 π
算法参数: 步长 α ∈ (0, 1]
初始化 V(s) 任意 (例如 V(s)=0), 对所有 s ∈ S⁺ (S⁺ 包括终止状态), V(终止状态)=0

对 每个 episode 循环:
    初始化 S (该 episode 的第一个状态)
    对 episode 中的每一步循环:
        A ← 根据策略 π 在状态 S 选择的动作
        执行动作 A, 观察奖励 R 和下一状态 S'
        // TD 更新
        V(S) ← V(S) + α * [R + γ * V(S') - V(S)]
        S ← S' // 转移到下一状态
    直到 S 是终止状态

plaintext

特点：TD(0) 在每一步之后都更新价值函数，不需要等待 episode 结束。

TD 与 MC 的比较#

更新时机与数据需求 (Page 14)：
- TD 可以在线学习，每一步都更新。MC 需要等待 episode 结束。
- TD 可以从不完整的 episode 中学习。MC 必须从完整的 episode 学习。
- TD 可以应用于连续性任务（没有终止状态）。MC 通常用于分幕式任务。
偏差与方差 (Bias vs. Variance) (Page 15-18)：
- 回报 $G_t$ (MC Target)：是 $v_\pi(S_t)$ 的无偏 (Unbiased) 估计，但方差较高，因为它依赖于一个 episode 中从 $t$ 到结尾的所有随机因素（动作、状态转移、奖励）。
- TD 目标 $R_{t+1} + \gamma V(S_{t+1})$ (TD(0) Target)：是 $v_\pi(S_t)$ 的有偏 (Biased) 估计，因为 $V(S_{t+1})$ 是当前的估计值，可能不准确。但其方差较低，因为它只依赖于一步的随机性 ( $R_{t+1}, S_{t+1}$ )。
- 总结：
  - MC：高方差，零偏差。对初始值不敏感，理论性质好。
  - TD：低方差，有偏差。通常比 MC 更有效率（学习更快），对初始值敏感。
对马尔可夫性质的利用 (Page 23)：
- TD 隐式地利用了马尔可夫性质，因为它假设 $V(S_{t+1})$ 包含了预测未来所需的所有信息。在马尔可夫环境下，这通常使 TD 更高效。
- MC 不利用马尔可夫性质，它直接使用实际的完整回报。这使得 MC 在非马尔可夫环境下可能表现更好。
批量学习 (Batch Learning) (Page 19-23)：
- 如果给定一个固定的经验数据集（一批 episodes）：
- 批量 MC：找到最小化观测回报 $G_t$ 与估计值 $V(s_t)$ 之间均方误差的价值函数。
- 批量 TD(0)：找到与这批数据对应的最大似然马尔可夫模型 (Maximum Likelihood Markov Model) 的价值函数（即确定性等价估计 Certainty Equivalence Estimate）。
- 例子 (A-B Example) (Page 21-23)：给定 8 个 episodes (A,0,B,0; B,1; B,1; B,1; B,1; B,1; B,1; B,0)，假设 $\gamma=1$ $γ = 1$ 。
  - MC 结果： $V(B) = (6 \times 1 + 2 \times 0) / 8 = 6/8 = 0.75$ 。对于 A，只有 episode A,0,B,0，回报 $G_0 = R_1 + \gamma R_2 + \dots = 0 + 1 \times 0 = 0$ 。所以 $V(A)=0$ 。MC 结果是 $(V(A), V(B)) = (0, 0.75)$ 。
  - TD(0) 结果：TD(0) 收敛到的值满足贝尔曼方程，使用从数据估计出的最大似然模型。模型为：从 A 总是转移到 B，奖励为 0 ( $\hat{\mathcal{P}}_{AB}=1, \hat{\mathcal{R}}_A=0$ )；从 B 有 6/8 概率得到奖励 1 并终止，2/8 概率得到奖励 0 并终止。所以 $V(B) = \mathbb{E}[\text{Reward from B}] = 0.75 \times 1 + 0.25 \times 0 = 0.75$ 。对于 A， $V(A) = \hat{\mathcal{R}}_A + \gamma \hat{\mathcal{P}}_{AB} V(B) = 0 + 1 \times 1 \times 0.75 = 0.75$ 。TD(0) 结果是 $(V(A), V(B)) = (0.75, 0.75)$ 。
- 结论：TD(0) 的解反映了它认为环境是一个 A 状态必然导致 0.75 回报的 MDP，而 MC 的解直接反映了观测到的从 A 开始的平均回报。

同轨时序差分控制 (On-Policy TD Control)#

TD 控制的目标是：使用 TD 方法学习最优策略 $\pi_*$ 。

基本思想 (Page 25, 30)：在 GPI 框架中，用 TD 预测代替 MC 预测来进行策略评估。因为 TD 可以在线学习且效率更高。
需要动作价值 (Need Action Values) (Page 27, 33)：与 MC 控制类似，无模型控制需要估计动作价值 $Q(s, a)$ ，因为仅有 $V(s)$ 不足以在没有模型的情况下确定最优动作。
Sarsa：同轨 TD 控制算法 (On-Policy TD Control Algorithm) (Page 26, 28-32)：
- 名称来源：更新依赖于一个五元组 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ ，即 State, Action, Reward, State’, Action’。
- 核心：将 TD(0) 的思想应用于动作价值 $Q(s, a)$ 的更新。
- 更新规则 (Page 31, 36)：
  - TD 目标： $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$ （注意：这里使用的是下一个实际采取的动作 $A_{t+1}$ 的 Q 值）。
  - TD 误差： $\delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)$
  - Q 值更新： $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)]$
- 算法流程 (Sarsa) (Page 32)：
```
算法参数: 步长 α ∈ (0, 1], 小的 ε > 0
初始化 Q(s, a) 任意, 对所有 s ∈ S⁺, a ∈ A(s), Q(终止状态, ·) = 0

对 每个 episode 循环:
    初始化 S
    使用从 Q 推导出的策略 (例如 ε-greedy) 在 S 处选择动作 A
    对 episode 中的每一步循环:
        执行动作 A, 观察奖励 R, 下一状态 S'
        使用从 Q 推导出的策略 (例如 ε-greedy) 在 S' 处选择动作 A' // 选择下一个动作
        // Sarsa 更新
        Q(S, A) ← Q(S, A) + α * [R + γ * Q(S', A') - Q(S, A)]
        S ← S'; A ← A' // 更新当前状态和当前动作
    直到 S 是终止状态
```
  plaintext
- 同轨特性 (On-Policy)：Sarsa 学习的是它当前正在执行的策略（例如 $\epsilon$ -greedy 策略）的动作价值。更新目标 $Q(S', A')$ 使用的是下一步实际选择的动作 $A'$ 。
例子：有风的网格世界 (Windy Gridworld) (Page 33-34)：展示了 Sarsa 算法如何学会在有侧风影响的环境中导航到目标。
Sarsa 收敛性 (Page 35)：
- Sarsa 算法会收敛到最优动作价值函数 $q_*$ $q_{*}$ ，前提条件是：
  1. 遵循的策略序列满足 GLIE (Greedy in the Limit with Infinite Exploration) 条件：
    - 所有状态-动作对被无限次访问。
    - 策略最终收敛到贪心策略（例如， $\epsilon$ -greedy 中 $\epsilon$ 随时间趋于 0）。
  2. 步长 $\alpha_t$ $α_{t}$ 满足 Robbins-Monro 随机逼近条件：
    - $\sum_{t=1}^\infty \alpha_t = \infty$
    - $\sum_{t=1}^\infty \alpha_t^2 < \infty$

小结 (Summary) (Page 36)#

TD 学习是 MC 和 DP 思想的结合，利用自举和采样。
TD 方法可以直接从经验中学习，无需模型，且可以在每一步之后更新，适用于不完整的序列和连续性任务。
TD(0) 是基本的 TD 预测算法。
Sarsa 是基本的同轨 (On-Policy) TD 控制算法，学习 $\epsilon$ -greedy 策略下的动作价值。
TD 相较于 MC 通常具有更低的方差和更高的学习效率（在马尔可夫环境下）。

DP 与 TD 方法比较总结 (Page 37-38)#

这两页以图表和公式的形式清晰地总结和对比了 DP 和 TD 方法的核心更新规则（备份操作）：

DP (Full Backup)：基于期望，需要完整模型。
- Iterative Policy Evaluation (V) -> Q-Policy Iteration (Q) -> Q-Value Iteration (Q)
TD (Sample Backup)：基于样本转移和自举，无模型。
- TD Learning (V) -> Sarsa (Q) -> Q-Learning (Q) (Q-Learning 是下一步要讲的离轨 TD 控制方法)

这清晰地展示了从预测到控制，从基于状态值到基于动作值，从 DP 到 TD 的逻辑演进。