Skip to main content

7. Temporal-Difference Learning

Temporal-Difference（TD）学习同时吸收了动态规划和 Monte Carlo 的特点：它像 MC 一样不需要环境模型（Model-Free），又像动态规划一样使用已有价值估计进行自举（bootstrapping）。

1. TD(0) 更新​

随机初始化 VV

在固定策略 π\pi 下观察一条单步转移（即主动采样一次）：

(St,Rt+1,St+1).(S_t,R_{t+1},S_{t+1}).

TD(0) 只更新当前访问的状态：

V(St)←V(St)+αt(St)[Rt+1+γV(St+1)−V(St)].\boxed{ V(S_t)\leftarrow V(S_t) +\alpha_t(S_t) \left[R_{t+1}+\gamma V(S_{t+1})-V(S_t)\right] }.

这里的 αt(St)\alpha_t(S_t) 意味着我们可以根据不同状态设置对应学习率，虽然一般不这么做

定义：

Rt+1+γV(St+1)⏟TD target,\underbrace{R_{t+1}+\gamma V(S_{t+1})}_{\text{TD target}},

以及

δt=Rt+1+γV(St+1)−V(St)\boxed{ \delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t) }

为 TD error，则更新可以简写为：

V(St)←V(St)+αt(St)δt.V(S_t)\leftarrow V(S_t)+\alpha_t(S_t)\delta_t.

2. 为什么它会被目标值拉近​

记 TD target 为 vˉt\bar v_t，更新后：

Vt+1(St)=(1−αt)Vt(St)+αtvˉt.V_{t+1}(S_t) =(1-\alpha_t)V_t(S_t)+\alpha_t\bar v_t.

当 0<αt<10<\alpha_t<1 时，这是旧估计与目标的凸组合，并且：

Vt+1(St)−vˉt=(1−αt)(Vt(St)−vˉt).V_{t+1}(S_t)-\bar v_t =(1-\alpha_t)\bigl(V_t(S_t)-\bar v_t\bigr).

所以本次更新后，V(St)V(S_t) 与当前 TD target 的距离缩小了。但要注意，vˉt\bar v_t 自身含有随训练变化的 V(St+1)V(S_{t+1})，它不是固定不动的监督标签。所以这里不能说差距严格缩小，因为 V(St)V(S_t) 与原来 vˉt\bar v_t 距离缩小的同时，vˉt\bar v_t 自己又会变化。

当 V=vπV=v_\pi 时，Bellman 期望方程给出：

vπ(s)=Eπ[Rt+1+γvπ(St+1)∣St=s],v_\pi(s)=\mathbb E_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})\mid S_t=s],

因此 TD error 的条件期望为零，而不是每一个样本的 δt\delta_t 都等于零。

3. 从随机近似理解 TD​

策略价值是 Bellman 方程的根：

g(v;s)=v(s)−Eπ[Rt+1+γv(St+1)∣St=s]=0.g(v;s)=v(s)- \mathbb E_\pi[R_{t+1}+\gamma v(S_{t+1})\mid S_t=s]=0.

环境模型未知时，用一次采样构造随机估计：

g~(v;s)=v(s)−[Rt+1+γv(St+1)].\tilde g(v;s) =v(s)-\left[R_{t+1}+\gamma v(S_{t+1})\right].

然后做随机近似更新：

V(St)←V(St)−αtg~(V;St),V(S_t)\leftarrow V(S_t)-\alpha_t\tilde g(V;S_t),

这正是 TD(0)。因此 TD 可以理解为：用无偏的单步样本近似 Bellman 期望，并不断寻找上述方程的根。

4. TD(0) 的收敛定理​

考虑有限 MDP 上的表格型 on-policy TD(0)。假设策略 π\pi 固定、奖励有界且 0≤γ<10\leq\gamma<1。再假设在策略 π\pi 下，每个待估计状态都会被访问无穷多次（几乎必然）。

对每个状态 ss，将它在时刻 tt 实际使用的步长记为：

αt(s)={αt,St=s,0,St≠s.\alpha_t(s)= \begin{cases} \alpha_t,&S_t=s,\\ 0,&S_t\neq s. \end{cases}

要求对每个状态 ss 都有：

0≤αt(s)≤1,∑t=0∞αt(s)=∞,∑t=0∞αt2(s)<∞,∀s,0\leq\alpha_t(s)\leq1, \qquad \sum_{t=0}^{\infty}\alpha_t(s)=\infty, \qquad \sum_{t=0}^{\infty}\alpha_t^2(s)<\infty, \qquad \forall s,

那么 TD(0) 的估计几乎必然收敛到真实策略价值：

vt(s)→t→∞a.s.vπ(s),∀s.\boxed{ v_t(s)\xrightarrow[t\to\infty]{\text{a.s.}}v_\pi(s), \qquad \forall s }.

注意，∑tαt(s)=∞\sum_t\alpha_t(s)=\infty 本身也要求状态 ss 被更新无穷多次：若只访问有限次，则只有有限个非零步长，该级数不可能发散。

随机迭代收敛引理（直接使用）​

下面给出 TD(0) 收敛性所需的有限维、异步更新版本；这里直接使用它，不证明。

设误差向量 Δt∈Rn\Delta_t\in\mathbb R^n 的第 ii 个分量按下式更新：

Δt+1(i)=(1−αt(i))Δt(i)+αt(i)Ft(i).\Delta_{t+1}(i) =\bigl(1-\alpha_t(i)\bigr)\Delta_t(i) +\alpha_t(i)F_t(i).

其中 Ht\mathcal H_t 表示第 tt 次更新前已经观测到的全部历史信息。步长 αt(i)\alpha_t(i) 必须在更新前就已经确定，即它是 Ht\mathcal H_t 可测的，不能依赖这一步随后才采到的随机结果。

如果对每个分量 ii 满足：

  1. 步长足够小，但累计更新不停止

    0≤αt(i)≤1,∑t=0∞αt(i)=∞,∑t=0∞αt2(i)<∞;0\leq\alpha_t(i)\leq1, \qquad \sum_{t=0}^{\infty}\alpha_t(i)=\infty, \qquad \sum_{t=0}^{\infty}\alpha_t^2(i)<\infty;

  2. 平均更新会收缩误差：存在常数 0≤ρ<10\leq\rho<1，使得

    ∥E[Ft∣Ht]∥∞≤ρ∥Δt∥∞;\left\| \mathbb E[F_t\mid\mathcal H_t] \right\|_\infty \leq \rho\|\Delta_t\|_\infty;

  3. 随机波动受控：存在与 tt 无关的常数 C>0C>0，使得

    Var⁡(Ft(i)∣Ht)≤C(1+∥Δt∥∞2);\operatorname{Var} \left(F_t(i)\mid\mathcal H_t\right) \leq C\left(1+\|\Delta_t\|_\infty^2\right);

那么误差几乎必然收敛到零：

∥Δt∥∞→t→∞a.s.0.\boxed{ \|\Delta_t\|_\infty \xrightarrow[t\to\infty]{\mathrm{a.s.}}0 }.

直观上，第一条保证算法既不会过早停止学习，也会逐渐压低噪声；第二条表示平均更新把误差往零拉；第三条排除过大的随机扰动。

将 TD(0) 代入引理​

将引理中的分量 ii 看成一个状态 ss，各项对应为：

随机迭代引理TD(0)i状态 sΔt(i)Δt(s)=vt(s)−vπ(s)αt(i)αt(s)={αt,St=s,0,St≠sFt(i)ηt(s)=Rt+1+γvt(St+1)−vπ(s)\begin{array}{c|c} \text{随机迭代引理} & \text{TD(0)} \\ \hline i & \text{状态 }s \\ \Delta_t(i) & \Delta_t(s)=v_t(s)-v_\pi(s) \\ \alpha_t(i) & \alpha_t(s)=\begin{cases}\alpha_t,&S_t=s,\\0,&S_t\ne s\end{cases} \\ F_t(i) & \eta_t(s)=R_{t+1}+\gamma v_t(S_{t+1})-v_\pi(s) \end{array}

也就是说，Δt(s)\Delta_t(s) 是状态 ss 的价值估计误差，αt(s)\alpha_t(s) 表示这一步是否更新状态 ss，而 ηt(s)\eta_t(s) 是随机 TD 目标相对真实价值的偏差。

先看访问到状态 ss 的一次 TD(0) 更新：

vt+1(s)=vt(s)+αt(s)[Rt+1+γvt(St+1)−vt(s)].v_{t+1}(s) =v_t(s)+\alpha_t(s) \left[R_{t+1}+\gamma v_t(S_{t+1})-v_t(s)\right].

在等式两边减去真实价值 vπ(s)v_\pi(s)，再记 Δt(s)=vt(s)−vπ(s)\Delta_t(s)=v_t(s)-v_\pi(s)，便有：

Δt+1(s)=(1−αt(s))Δt(s)+αt(s)[Rt+1+γvt(St+1)−vπ(s)]=(1−αt(s))Δt(s)+αt(s)ηt(s).\begin{aligned} \Delta_{t+1}(s) &=\bigl(1-\alpha_t(s)\bigr)\Delta_t(s)\\ &\quad+\alpha_t(s) \left[R_{t+1}+\gamma v_t(S_{t+1})-v_\pi(s)\right]\\ &=\bigl(1-\alpha_t(s)\bigr)\Delta_t(s) +\alpha_t(s)\eta_t(s). \end{aligned}

这正是引理的迭代形式。若没有访问到 ss，就有 αt(s)=0\alpha_t(s)=0；此时该分量保持不变，令 ηt(s)=0\eta_t(s)=0 即可。

接下来验证引理中的两个随机条件；细节可展开查看。

展开：验证平均收缩与随机波动条件

1. 平均更新会收缩误差​

当 St=sS_t=s 时，vtv_t 已由历史 Ht\mathcal H_t 决定。根据 ηt(s)\eta_t(s) 的定义：

E[ηt(s)∣Ht]=E[Rt+1+γvt(St+1)−vπ(s)∣St=s]=E[Rt+1+γvt(St+1)∣St=s]−vπ(s).\begin{aligned} \mathbb E[\eta_t(s)\mid\mathcal H_t] &=\mathbb E\left[ R_{t+1}+\gamma v_t(S_{t+1})-v_\pi(s) \mid S_t=s \right]\\ &=\mathbb E\left[ R_{t+1}+\gamma v_t(S_{t+1}) \mid S_t=s \right]-v_\pi(s). \end{aligned}

Bellman 期望方程为：

vπ(s)=E[Rt+1+γvπ(St+1)∣St=s].v_\pi(s) =\mathbb E\left[ R_{t+1}+\gamma v_\pi(S_{t+1}) \mid S_t=s \right].

两式相减，奖励项抵消：

E[ηt(s)∣Ht]=γ E[vt(St+1)−vπ(St+1)∣St=s]=γ∑s′Pπ(s,s′)Δt(s′).\begin{aligned} \mathbb E[\eta_t(s)\mid\mathcal H_t] &=\gamma\, \mathbb E\left[ v_t(S_{t+1})-v_\pi(S_{t+1}) \mid S_t=s \right]\\ &=\gamma\sum_{s'}P_\pi(s,s')\Delta_t(s'). \end{aligned}

由于 Pπ(s,s′)≥0P_\pi(s,s')\geq0 且 ∑s′Pπ(s,s′)=1\sum_{s'}P_\pi(s,s')=1，

∣E[ηt(s)∣Ht]∣≤γ∑s′Pπ(s,s′)∣Δt(s′)∣≤γ∥Δt∥∞.\begin{aligned} \left|\mathbb E[\eta_t(s)\mid\mathcal H_t]\right| &\leq\gamma\sum_{s'}P_\pi(s,s')|\Delta_t(s')|\\ &\leq\gamma\|\Delta_t\|_\infty. \end{aligned}

未访问 ss 时我们令 ηt(s)=0\eta_t(s)=0，同样满足上界。因此

∥E[ηt∣Ht]∥∞≤γ∥Δt∥∞.\left\| \mathbb E[\eta_t\mid\mathcal H_t] \right\|_\infty \leq\gamma\|\Delta_t\|_\infty.

这就是引理的平均收缩条件，其中 ρ=γ<1\rho=\gamma<1。

2. 随机波动的二阶矩受控​

奖励有界意味着存在常数 BR>0B_R>0，使得

∣Rt+1∣≤BR.|R_{t+1}|\leq B_R.

又因为 0≤γ<10\leq\gamma<1，真实价值有界：

∥vπ∥∞≤BR1−γ.\|v_\pi\|_\infty\leq\frac{B_R}{1-\gamma}.

利用 vt=vπ+Δtv_t=v_\pi+\Delta_t，有

∣ηt(s)∣=∣Rt+1+γvt(St+1)−vπ(s)∣≤BR+(1+γ)∥vπ∥∞+γ∥Δt∥∞.\begin{aligned} |\eta_t(s)| &=\left| R_{t+1}+\gamma v_t(S_{t+1})-v_\pi(s) \right|\\ &\leq B_R+(1+\gamma)\|v_\pi\|_\infty +\gamma\|\Delta_t\|_\infty. \end{aligned}

令 A=BR+(1+γ)∥vπ∥∞A=B_R+(1+\gamma)\|v_\pi\|_\infty。由 (x+y)2≤2x2+2y2(x+y)^2\leq2x^2+2y^2，得到

ηt(s)2≤(A+γ∥Δt∥∞)2≤2A2+2γ2∥Δt∥∞2.\eta_t(s)^2 \leq \left(A+\gamma\|\Delta_t\|_\infty\right)^2 \leq 2A^2+2\gamma^2\|\Delta_t\|_\infty^2.

因此可以选取一个与 tt 无关的常数 C>0C>0，使得

E[ηt(s)2∣Ht]≤C(1+∥Δt∥∞2).\mathbb E[\eta_t(s)^2\mid\mathcal H_t] \leq C\left(1+\|\Delta_t\|_\infty^2\right).

最后利用“方差不超过二阶矩”：

Var⁡(ηt(s)∣Ht)≤E[ηt(s)2∣Ht]≤C(1+∥Δt∥∞2).\operatorname{Var}(\eta_t(s)\mid\mathcal H_t) \leq \mathbb E[\eta_t(s)^2\mid\mathcal H_t] \leq C\left(1+\|\Delta_t\|_\infty^2\right).

故引理的随机波动条件也成立。

现在三个条件都已经满足：逐状态步长满足 Robbins--Monro 条件，平均更新以 γ<1\gamma<1 收缩误差，随机波动也受控。因此由随机迭代收敛引理，vt→vπv_t\to v_\pi（几乎必然）。

关于常数步长： 如果始终使用常数 α>0\alpha>0，则 ∑tαt2(s)<∞\sum_t\alpha_t^2(s)<\infty 不再成立，上述几乎必然收敛证明不能直接使用。此时估计通常会在 vπv_\pi 附近持续波动，而不是精确收敛到一个固定值。

5. TD 与 Monte Carlo​

特征TDMonte Carlo
更新时机每一步即可在线更新通常等待 episode 结束
任务类型episodic 与 continuing主要是 episodic
目标Rt+1+γV(St+1)R_{t+1}+\gamma V(S_{t+1})完整回报 GtG_t
自举是否
典型偏差目标依赖当前估计，可能有偏完整回报通常是无偏样本
典型方差较低较高

一句话概括：MC 等到结局后用“真实完整回报”，TD 走一步就用“真实奖励 + 后继估计”。

6. Sarsa：on-policy TD 控制​

为了控制，需要估计动作价值。Sarsa 使用五元组：

(St,At,Rt+1,St+1,At+1).(S_t,A_t,R_{t+1},S_{t+1},A_{t+1}).

更新为：

Q(St,At)←Q(St,At)+α[Rt+1+γQ(St+1,At+1)−Q(St,At)].\boxed{ Q(S_t,A_t)\leftarrow Q(S_t,A_t) +\alpha\left[ R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t) \right] }.

At+1A_{t+1} 由当前行为策略实际选出。因此，如果行为策略是 ε\varepsilon-greedy，目标中也包含探索动作的后果。行为策略和目标策略是同一个，故 Sarsa 是 on-policy 方法。

q_value = initialize_action_values()

for _ in range(num_episodes):
    state = env.reset()
    action = epsilon_greedy(q_value[state], epsilon)

    while True:
        next_state, reward, terminated, truncated, _ = env.step(action)
        done = terminated or truncated
        next_action = epsilon_greedy(q_value[next_state], epsilon)

        target = reward + gamma * (1 - done) * q_value[next_state, next_action]
        q_value[state, action] += alpha * (target - q_value[state, action])

        if done:
            break
        state, action = next_state, next_action

7. Expected Sarsa​

Sarsa 对下一动作 At+1A_{t+1} 采样。Expected Sarsa 则对策略下的所有下一动作取期望：

Q(St,At)←Q(St,At)+α[Rt+1+γ∑aπ(a∣St+1)Q(St+1,a)−Q(St,At)].\boxed{ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left[ R_{t+1} +\gamma\sum_a\pi(a\mid S_{t+1})Q(S_{t+1},a) -Q(S_t,A_t) \right] }.

它消除了“下一动作采样”带来的一部分方差，但每次更新要计算动作期望。

8. n-step Sarsa​

一步 Sarsa 的目标为：

Gt(1)=Rt+1+γQ(St+1,At+1).G_t^{(1)}=R_{t+1}+\gamma Q(S_{t+1},A_{t+1}).

n-step Sarsa 先使用 nn 个真实奖励，再在第 nn 步自举：

Gt(n)=Rt+1+γRt+2+⋯+γn−1Rt+n+γnQ(St+n,At+n).\boxed{ G_t^{(n)} =R_{t+1}+\gamma R_{t+2}+\cdots +\gamma^{n-1}R_{t+n} +\gamma^nQ(S_{t+n},A_{t+n}) }.

当 n=1n=1 时得到 Sarsa；当 nn 延伸到 episode 终点时，自举项消失，得到 MC 回报。因此 n-step 方法连接了 TD 与 MC。

9. Q-learning：off-policy TD 控制​

Q-learning 使用下一状态的最大动作价值作为目标：

Q(St,At)←Q(St,At)+α[Rt+1+γmax⁡aQ(St+1,a)−Q(St,At)].\boxed{ Q(S_t,A_t)\leftarrow Q(S_t,A_t) +\alpha\left[ R_{t+1} +\gamma\max_aQ(S_{t+1},a) -Q(S_t,A_t) \right] }.

这里存在两个策略：

  • 行为策略 μ\mu：实际收集数据，常用 ε\varepsilon-greedy；
  • 目标策略 π\pi：目标中的 max⁡\max 所代表的贪心策略。

数据可以由带探索的 μ\mu 产生，而更新目标假设下一步采用贪心动作，所以 Q-learning 是 off-policy 方法。

9.1 Sarsa 与 Q-learning 的核心区别​

Sarsa target=Rt+1+γQ(St+1,At+1),Q-learning target=Rt+1+γmax⁡aQ(St+1,a).\begin{aligned} \text{Sarsa target} &=R_{t+1}+\gamma Q(S_{t+1},A_{t+1}),\\ \text{Q-learning target} &=R_{t+1}+\gamma\max_aQ(S_{t+1},a). \end{aligned}

At+1A_{t+1} 是按行为策略采样得到，aa 是在所有动作中贪心找最大，这就是核心区别

Sarsa 学习当前探索策略本身的价值；Q-learning 在探索产生的数据上学习贪心目标策略的价值。

10. 统一看待各种 target​

算法更新目标
SarsaRt+1+γQ(St+1,At+1)R_{t+1}+\gamma Q(S_{t+1},A_{t+1})
Expected SarsaRt+1+γ∑aπ(a∣St+1)Q(St+1,a)R_{t+1}+\gamma\sum_a\pi(a\mid S_{t+1})Q(S_{t+1},a)
Q-learningRt+1+γmax⁡aQ(St+1,a)R_{t+1}+\gamma\max_aQ(S_{t+1},a)
n-step Sarsa前 nn 步真实奖励 +γnQ(St+n,At+n)+\gamma^nQ(S_{t+n},A_{t+n})
Monte Carlo直到终点的完整回报 GtG_t

这些方法的主要差异不在“都更新了一个 QQ”，而在于如何构造 target：采样下一动作、计算策略期望、取最大值，或一直等待真实回报。