西湖大学 RL 第七课：时序差分学习

强化学习的数学原理 - 第七课：时序差分学习 (Temporal-Difference Learning)

课程内容地图回顾

• 当前位置: 第七章 - 时序差分算法 (Temporal-Difference Learning, TD Learning)
• 与之前章节的关系:
  • 第五章 (蒙特卡洛方法, MC): 介绍了第一种无模型 (model-free) 的强化学习方法。MC 方法是 非增量式 (non-incremental) 的。
  • 第六章 (随机近似, Stochastic Approximation, SA): 介绍了 SA、随机梯度下降 (SGD) 和 Robbins-Monro (RM) 算法，这些是本节课TD算法的数学基础，有助于理解TD算法的形式和解决的问题。
  • TD Learning 是第二种介绍的 model-free 方法，与MC不同，TD是 增量式 (incremental) 或迭代式的方法。
• 与之后章节的关系:
  • 第八章 (价值函数近似, Value Function Approximation): 将基于本节课介绍的TD方法，从表格表示 (tabular representation) 扩展到函数表示 (function representation)，例如经典的 Deep Q-Learning。

本次课大纲

1. 启发性示例 (Motivating Examples): 通过几个例子建立与上一课RM算法的联系。
2. 状态价值的TD学习 (TD Learning of State Values): 介绍最基础的TD算法，用于估计状态价值 $v_\pi(s)$。
3. 动作价值的TD学习：Sarsa: 介绍Sarsa算法及其变种，用于估计动作价值 $q_\pi(s,a)$。
4. 动作价值的TD学习：Expected Sarsa & n-步Sarsa: Sarsa的进一步改进和推广。
5. 最优动作价值的TD学习：Q-Learning: 介绍大名鼎鼎的Q-Learning算法，直接估计最优动作价值 $q_\*(s,a)$。
6. 算法比较与统一观点 (Comparison and Unified View): 总结各类TD算法的异同。
7. 总结 (Summary)

1. 启发性示例 (Motivating Examples)

目的: 通过具体例子展示如何使用上一课学习的Robbins-Monro (RM)算法求解问题，从而自然地引出TD算法的形式，理解其数学渊源。

示例1: 均值估计 (Mean Estimation)

• 问题: 估计随机变量 $X$ 的期望 $w = E[X]$，已知 $X$ 的独立同分布 (i.i.d.) 样本 $\{x\_k\}$。
• RM算法求解:
  1. 定义函数 $g(w) = w - E[X]$。求解 $g(w) = 0$ 即可得到 $w^\* = E[X]$。
  2. 由于只能获得 $X$ 的样本 $x\_k$，我们得到的是 $g(w)$ 的带噪声观测： $$ \tilde{g}(w, \eta\_k) = w - x\_k = (w - E[X]) + (E[X] - x\_k) = g(w) + \eta\_k $$ 其中 $\eta\_k = E[X] - x\_k$ 是噪声。
  3. 根据RM算法的迭代公式 $w\_{k+1} = w\_k - \alpha\_k \tilde{g}(w\_k, \eta\_k)$： $$ w\_{k+1} = w\_k - \alpha\_k (w\_k - x\_k) $$ 这就是我们熟悉的样本均值的增量式更新方法。

示例2: 函数均值估计 (Mean Estimation of a Function)

• 问题: 估计函数 $v(X)$ 的期望 $w = E[v(X)]$，已知 $X$ 的 i.i.d. 样本 $\{x\_k\}$。
• RM算法求解:
  1. 定义 $g(w) = w - E[v(X)]$。
  2. 带噪声观测： $$ \tilde{g}(w, \eta\_k) = w - v(x\_k) = (w - E[v(X)]) + (E[v(X)] - v(x\_k)) = g(w) + \eta\_k $$
  3. RM算法更新： $$ w\_{k+1} = w\_k - \alpha\_k [w\_k - v(x\_k)] $$

示例3: 更复杂的期望估计

• 问题: 估计 $w = E[R + \gamma v(X)]$，其中 $R, X$ 是随机变量，$\gamma$ 是常数，$v(\cdot)$ 是函数。已知 $R, X$ 的样本对 $\{r\_k, x\_k\}$。
  • 这里的 $R$ 可以联想为奖励 (Reward)，$\gamma$ 为折扣率 (Discount Rate)，$v(X)$ 为状态价值 (State Value)，$X$ 为状态 (State)。
• RM算法求解:
  1. 定义 $g(w) = w - E[R + \gamma v(X)]$。
  2. 带噪声观测： $$ \tilde{g}(w, \eta\_k) = w - [r\_k + \gamma v(x\_k)] = (w - E[R + \gamma v(X)]) + (E[R + \gamma v(X)] - [r\_k + \gamma v(x\_k)]) = g(w) + \eta\_k $$
  3. RM算法更新： $$ w\_{k+1} = w\_k - \alpha\_k [w\_k - (r\_k + \gamma v(x\_k))] $$ 这个表达式与即将介绍的TD算法非常相似。

总结: 这三个例子层层递进，都利用RM算法求解。最后一个例子的形式为理解TD算法奠定了基础。

2. 状态价值的TD学习 (TD Learning of State Values)

这是最基础、最经典的TD算法，用于 策略评估 (Policy Evaluation)，即估计给定策略 $\pi$ 下的状态价值 $v_\pi(s)$。

算法描述

• 目标: 给定策略 $\pi$，估计其状态价值 $\{v_\pi(s)\}\_{s \in S}$。
• 数据/经验 (Experience): 由策略 $\pi$ 与环境交互产生的序列：$(s\_0, r\_1, s\_1, r\_2, s\_2, \dots, s\_t, r\_{t+1}, s\_{t+1}, \dots)$，或者可以看作一系列的转移元组 $\{(s\_t, r\_{t+1}, s\_{t+1})\}\_t$。
• 符号:
  • $v(s)$: 对真实状态价值 $v_\pi(s)$ 的估计。
  • $v\_t(s)$: 在时刻 $t$ 对状态 $s$ 的价值估计。
• TD(0) 算法 / 基本TD算法: 在每个时间步 $t$，观察到状态 $s\_t$，采取动作（根据策略 $\pi$），得到奖励 $r\_{t+1}$ 和下一个状态 $s\_{t+1}$。然后更新 $v(s\_t)$： $$ v\_{t+1}(s\_t) = v\_t(s\_t) + \alpha\_t(s\_t) [ \underbrace{r\_{t+1} + \gamma v\_t(s\_{t+1})}\_{\text{TD Target}} - v\_t(s\_t) ] \quad (1) $$ 对于所有其他未被访问的状态 $s \neq s\_t$： $$ v\_{t+1}(s) = v\_t(s) \quad (2) $$ 其中：
  • $\alpha\_t(s\_t)$ 是学习率 (learning rate)，通常是一个小的正数，可以随时间变化，也可以是状态相关的。
  • $\gamma$ 是折扣因子。
  • TD Target (TD目标值): $\bar{v}\_t \doteq r\_{t+1} + \gamma v\_t(s\_{t+1})$。这是当前对 $v_\pi(s\_t)$ 的一个更好的估计，因为它用到了真实的即时奖励 $r\_{t+1}$ 和对下一状态价值的当前估计 $v\_t(s\_{t+1})$。
  • TD Error (TD误差): $\delta\_t \doteq (r\_{t+1} + \gamma v\_t(s\_{t+1})) - v\_t(s\_t)$。它表示TD目标与当前价值估计之间的差异。
  • 更新规则可以理解为：新估计 = 旧估计 + 学习率 * TD误差。

TD算法性质

1. TD目标 (TD Target):

   • 算法的目标是让 $v\_t(s\_t)$ 朝着TD目标 $\bar{v}\_t$ 移动。
   • 推导： $v\_{t+1}(s\_t) - \bar{v}\_t = v\_t(s\_t) - \bar{v}\_t + \alpha\_t(s\_t) [\bar{v}\_t - v\_t(s\_t)]$ $v\_{t+1}(s\_t) - \bar{v}\_t = (1 - \alpha\_t(s\_t)) [v\_t(s\_t) - \bar{v}\_t]$ 由于 $0 < \alpha\_t(s\_t) < 1$ (通常情况下)，所以 $0 < 1 - \alpha\_t(s\_t) < 1$。 因此， $|v\_{t+1}(s\_t) - \bar{v}\_t| < |v\_t(s\_t) - \bar{v}\_t|$ （如果 $v\_t(s\_t) \neq \bar{v}\_t$）。这表明新的估计 $v\_{t+1}(s\_t)$ 比旧的估计 $v\_t(s\_t)$ 更接近TD目标 $\bar{v}\_t$。

2. TD误差 ($\delta\_t$):

   • 时序差分: 反映了两个连续时间步价值估计之间的差异（一个是基于当前估计 $v\_t(s\_t)$，另一个是基于一步实际观测和下一状态的估计 $r\_{t+1} + \gamma v\_t(s\_{t+1})$）。
   • 与真实价值的差异: TD误差也间接反映了当前估计 $v\_t$ 与真实价值 $v_\pi$ 之间的不一致性。
     • 定义 $\delta\_{\pi,t} \doteq r\_{t+1} + \gamma v\_{\pi}(s\_{t+1}) - v\_{\pi}(s\_t)$。
     • 根据贝尔曼方程，我们知道 $E[\delta\_{\pi,t} | S\_t = s\_t] = E[R\_{t+1} + \gamma v\_{\pi}(S\_{t+1}) | S\_t = s\_t] - v\_{\pi}(s\_t) = 0$。
     • 所以，如果 $v\_t = v_\pi$，那么期望意义上的TD误差 $E[\delta\_t]$ 应该为0。反之，如果TD误差不为0，说明 $v\_t \neq v_\pi$。
   • 创新 (Innovation): TD误差可以看作是从新经验 $(s\_t, r\_{t+1}, s\_{t+1})$ 中获得的，用于修正当前估计的“新信息”或“意外”。如果当前估计是准确的，TD误差的期望会很小。

3. 功能局限:

   • 这个基础TD算法仅用于 策略评估 (估计给定策略的状态价值)。
   • 它不能直接估计动作价值 $q_\pi(s,a)$。
   • 它不能直接搜索最优策略。
   • 但它是理解后续更复杂TD算法 (如Sarsa, Q-Learning) 的基石。

TD算法的数学思想

• 核心: TD算法是在 没有模型 (model-free) 的情况下，求解给定策略 $\pi$ 的 贝尔曼方程。

• 贝尔曼期望方程 (Bellman Expectation Equation): 状态价值的定义 $v\_{\pi}(s) = E_\pi[R\_{t+1} + \gamma G\_{t+1} | S\_t = s]$ 可以展开为：

  $$ v\_{\pi}(s) = E_\pi[R\_{t+1} + \gamma v\_{\pi}(S\_{t+1}) | S\_t = s] $$

  这是贝尔曼方程的另一种形式，不显式包含动作和状态转移概率，而是用期望来概括。这个形式是TD算法设计和分析的关键。

• 用RM算法求解贝尔曼期望方程:

  1. 对特定状态 $s$，令 $w = v_\pi(s)$。目标是找到 $w$ 使得 $w = E[R\_{t+1} + \gamma v\_{\pi}(S\_{t+1}) | S\_t=s]$。
  2. 定义 $g(w) = w - E[R\_{t+1} + \gamma v\_{\pi}(S\_{t+1}) | S\_t=s]$。求解 $g(w)=0$。
  3. 带噪声观测 (使用单次采样 $r\_{t+1}, s\_{t+1}$ 代替期望): $\tilde{g}(w\_t) = w\_t - [r\_{t+1} + \gamma v\_{\pi}(s\_{t+1})]$
  4. RM算法更新： $w\_{t+1} = w\_t - \alpha\_t [w\_t - (r\_{t+1} + \gamma v\_{\pi}(s\_{t+1}))]$
  5. 关键一步：自举 (Bootstrapping) 由于真实的 $v\_{\pi}(s\_{t+1})$ 未知，TD算法使用当前的估计 $v\_t(s\_{t+1})$ 来代替它 (即用估计值更新估计值)： $v\_{t+1}(s\_t) = v\_t(s\_t) - \alpha\_t [v\_t(s\_t) - (r\_{t+1} + \gamma v\_t(s\_{t+1}))]$ 这正是TD(0)算法的更新公式！
  • 与RM算法的区别:
    1. 样本来源: RM通常假设i.i.d.样本。TD利用马尔可夫决策过程 (MDP) 中的序列样本 $(s\_t, r\_{t+1}, s\_{t+1})$。
    2. 目标值: RM的理论推导中可能使用真实期望或真实函数值。TD使用当前对下一状态价值的估计 $v\_t(s\_{t+1})$ 作为TD目标的一部分，这是 自举 (bootstrapping) 的核心特征。

TD算法的收敛性

定理 (TD学习的收敛性): 如果学习率 $\alpha\_t(s)$ 满足以下条件 (Robbins-Monro条件)：

1. $\sum\_{t=0}^{\infty} \alpha\_t(s) = \infty$ (对于所有状态 $s$)
2. $\sum\_{t=0}^{\infty} \alpha\_t^2(s) < \infty$ (对于所有状态 $s$) 则 $v\_t(s)$ 将以概率1收敛到真实的 $v_\pi(s)$，对于所有状态 $s \in S$。

• 条件解释:
  • 第一个条件确保有足够的总步长来克服初始误差和噪声。对于TD，$\alpha\_t(s)$ 仅在状态 $s$ 被访问时为正，所以这意味着 每个状态都必须被无限次（或足够多次）访问。
  • 第二个条件确保步长最终会减小，使得估计稳定下来。
• 实践中的学习率: 实际上，$\alpha\_t$ 常被设为一个小的常数 (如0.1, 0.01)。这种情况下，条件2不满足，但算法在期望意义上仍能收敛，并且对非平稳环境有更好的适应性（能持续学习）。

TD学习与蒙特卡洛(MC)学习的比较

总结: TD相比MC通常学习更快，方差更小，并且能处理持续性任务，但它是有偏的。MC无偏，但方差大，只能用于片段任务。

3. 动作价值的TD学习：Sarsa

Sarsa (State-Action-Reward-State-Action) 是一种TD控制算法，用于估计 动作价值函数 $q_\pi(s,a)$ 并在此基础上改进策略以找到最优策略。

Sarsa算法 (用于策略评估)

• 目标: 给定策略 $\pi$，估计其动作价值 $\{q_\pi(s,a)\}\_{\forall s,a}$。
• 经验: 序列 $(s\_0, a\_0, r\_1, s\_1, a\_1, r\_2, s\_2, a\_2, \dots)$。算法名字来源于更新时需要的五元组 $(s\_t, a\_t, r\_{t+1}, s\_{t+1}, a\_{t+1})$。
• Sarsa 更新规则: 在时刻 $t$，智能体处于状态 $s\_t$，执行动作 $a\_t$，观察到奖励 $r\_{t+1}$ 和下一状态 $s\_{t+1}$。然后，在 $s\_{t+1}$ 根据当前策略 $\pi$ 选择下一个动作 $a\_{t+1}$。使用这个五元组更新 $q(s\_t, a\_t)$： $$ q\_{t+1}(s\_t, a\_t) = q\_t(s\_t, a\_t) + \alpha\_t(s\_t, a\_t) [r\_{t+1} + \gamma q\_t(s\_{t+1}, a\_{t+1}) - q\_t(s\_t, a\_t)] $$ 对于所有其他未被访问的状态-动作对 $(s,a) \neq (s\_t, a\_t)$： $$ q\_{t+1}(s,a) = q\_t(s,a) $$
  • TD目标: $r\_{t+1} + \gamma q\_t(s\_{t+1}, a\_{t+1})$。注意这里用的是在 $s\_{t+1}$ 实际将要执行的动作 $a\_{t+1}$ 的q值。
  • 与基础TD算法的关系: 形式上非常相似，只是将状态价值 $v(s)$ 替换为动作价值 $q(s,a)$。
• 数学思想: Sarsa 算法是在求解用动作价值表示的贝尔曼期望方程： $$ q\_{\pi}(s,a) = E_\pi[R\_{t+1} + \gamma q\_{\pi}(S\_{t+1}, A\_{t+1}) | S\_t=s, A\_t=a] $$
• 收敛性: 与基础TD类似，在满足Robbins-Monro条件下， $q\_t(s,a)$ 会收敛到 $q_\pi(s,a)$。

Sarsa算法 (用于控制/策略搜索)

为了找到最优策略，Sarsa将策略评估和策略改进结合起来，遵循 广义策略迭代 (Generalized Policy Iteration, GPI) 的思想。

Sarsa 控制算法伪代码:

1. 初始化 $q(s,a)$ 对于所有 $s,a$ (例如，任意值，除了终止状态的 $q(\text{terminal}, \cdot)=0$)。
2. 对每个片段 (episode) 执行: a. 初始化状态 $s\_0$。 b. 根据当前 $q$ 值和探索策略 (如 $\epsilon$-greedy) 从 $s\_0$ 选择动作 $a\_0$。 c. 只要 $s\_t$ 不是终止状态: i. 执行动作 $a\_t$，观察奖励 $r\_{t+1}$ 和下一状态 $s\_{t+1}$。 ii. 根据当前 $q(s\_{t+1}, \cdot)$ 和探索策略 (如 $\epsilon$-greedy) 从 $s\_{t+1}$ 选择下一动作 $a\_{t+1}$。 iii. 更新 $q(s\_t, a\_t)$： $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)]$ iv. $s\_t \leftarrow s\_{t+1}$, $a\_t \leftarrow a\_{t+1}$。

• 策略改进: 通过 $\epsilon$-greedy 方式选择动作，隐式地改进了策略。随着 $q$ 值越来越接近 $q_\*$，$\epsilon$-greedy 策略也会越来越接近最优策略。
• $\epsilon$-greedy 策略: 以 $1-\epsilon$ 的概率选择当前估计的最优动作 (greedy)，以 $\epsilon$ 的概率随机选择一个动作（探索）。
• 核心思想: Sarsa通过不断地用 $(s\_t, a\_t, r\_{t+1}, s\_{t+1}, a\_{t+1})$ 这样的经验来迭代更新动作价值函数，并通过 $\epsilon$-greedy 策略来平衡探索和利用，最终趋向于最优策略。

Sarsa 示例 (网格世界)

• 任务: 从特定起始状态（如左上角）找到到达目标状态的路径。
  • 注意：这个任务目标是找到 一条 可行的路径，不一定要求所有状态都达到最优策略。
• 结果:
  • 最终策略图显示了一条从起点到终点的路径。
  • 学习曲线图：
    • 每个片段的总奖励 (Total Reward per Episode): 随着学习的进行，总奖励通常会上升（或减少惩罚）。
    • 每个片段的长度 (Episode Length): 随着策略的优化，到达目标的步数通常会减少。
  • Sarsa 的表现显示它能够学到解决任务的策略，即使在一些未充分探索的区域，策略可能不是最优的，但只要能完成指定任务（如从特定点出发到达目标）即可。

4. 动作价值的TD学习：Expected Sarsa 和 n-步Sarsa

这些是Sarsa算法的变种和推广。

Expected Sarsa (期望Sarsa)

• 核心思想: 在计算TD目标时，对下一个状态 $s\_{t+1}$ 之后所有可能的动作 $a'$ 的Q值，按照当前策略 $\pi$ 的概率分布求期望，而不是像Sarsa那样只使用实际采样到的下一个动作 $a\_{t+1}$。
• Expected Sarsa 更新规则: $$ q\_{t+1}(s\_t, a\_t) = q\_t(s\_t, a\_t) + \alpha\_t [r\_{t+1} + \gamma \underbrace{E\_{A' \sim \pi(S\_{t+1})}[q\_t(s\_{t+1}, A')]}\_{\text{期望Q值}} - q\_t(s\_t, a\_t)] $$ 其中 $E\_{A' \sim \pi(S\_{t+1})}[q\_t(s\_{t+1}, A')] = \sum\_{a'} \pi(a'|s\_{t+1}) q\_t(s\_{t+1}, a')$。 这实际上就是 $r\_{t+1} + \gamma v\_t(s\_{t+1})$ （如果用当前Q值和策略计算状态价值）。
• 与Sarsa的区别:
  • Sarsa的TD目标: $r\_{t+1} + \gamma q\_t(s\_{t+1}, a\_{t+1})$ (依赖于 $a\_{t+1}$ 的采样)
  • Expected Sarsa的TD目标: $r\_{t+1} + \gamma \sum\_{a'} \pi(a'|s\_{t+1}) q\_t(s\_{t+1}, a')$ (不依赖于 $a\_{t+1}$ 的采样)
• 优缺点:
  • 优点: 方差通常比Sarsa小，因为它消除了对 $A\_{t+1}$ 采样的随机性。性能可能更稳定。
  • 缺点: 计算量稍大，因为需要对所有可能的下一个动作求和（或积分）。
• 数学思想: Expected Sarsa 求解的贝尔曼方程为： $$ q\_{\pi}(s,a) = E_\pi[R\_{t+1} + \gamma E\_{A' \sim \pi(S\_{t+1})}[q\_{\pi}(S\_{t+1}, A')] | S\_t=s, A\_t=a] $$ 即 $q\_{\pi}(s,a) = E_\pi[R\_{t+1} + \gamma v\_{\pi}(S\_{t+1}) | S\_t=s, A\_t=a]$。
• 示例: 在同样的网格世界路径寻找任务中，Expected Sarsa 也能找到解决方案，其学习曲线可能比Sarsa更平滑。

n-步Sarsa (n-step Sarsa)

• 核心思想: n-步Sarsa是Sarsa (1-步TD) 和蒙特卡洛方法 (MC, $\infty$-步TD) 的一种折中和推广。它向前看 $n$ 步的实际奖励，然后使用第 $n$ 步之后的价值估计来构建TD目标。
• n-步回报 ($G\_t^{(n)}$): $G\_t^{(1)} = R\_{t+1} + \gamma q\_{\pi}(S\_{t+1}, A\_{t+1})$ (Sarsa的目标基础) $G\_t^{(2)} = R\_{t+1} + \gamma R\_{t+2} + \gamma^2 q\_{\pi}(S\_{t+2}, A\_{t+2})$ $\dots$ $G\_t^{(n)} = R\_{t+1} + \gamma R\_{t+2} + \dots + \gamma^{n-1} R\_{t+n} + \gamma^n q\_{\pi}(S\_{t+n}, A\_{t+n})$ $G\_t^{(\infty)} = R\_{t+1} + \gamma R\_{t+2} + \gamma^2 R\_{t+3} + \dots$ (MC的回报) 注意：这些不同的 $G\_t^{(k)}$ 在期望意义上都等于 $q_\pi(S\_t,A\_t)$，只是分解方式不同。
• n-步Sarsa 更新规则: TD目标为 $n$-步回报的样本： $r\_{t+1} + \gamma r\_{t+2} + \dots + \gamma^{n-1}r\_{t+n} + \gamma^n q\_t(s\_{t+n}, a\_{t+n})$ $$ q\_{t+1}(s\_t, a\_t) = q\_t(s\_t, a\_t) + \alpha\_t [ (r\_{t+1} + \dots + \gamma^{n-1}r\_{t+n} + \gamma^n q\_t(s\_{t+n}, a\_{t+n})) - q\_t(s\_t, a\_t) ] $$
• 数据需求与更新时机:
  • 为了更新 $q(s\_t, a\_t)$，需要收集到 $(s\_t, a\_t, r\_{t+1}, s\_{t+1}, a\_{t+1}, \dots, r\_{t+n}, s\_{t+n}, a\_{t+n})$。
  • 这意味着对 $q(s\_t,a\_t)$ 的更新实际上发生在时间步 $t+n$ 之后，当所有需要的 $n$ 步信息都可用时。
  • 例如，在 $t+n$ 时刻，我们可以用收集到的 $r\_{t+1}, \dots, r\_{t+n}$ 和 $q\_{t+n-1}(s\_{t+n}, a\_{t+n})$ 来更新 $q\_{t+n}(s\_t, a\_t)$。
• 性质 (Bias-Variance Trade-off):
  • $n=1$: 即为Sarsa，偏差较大（依赖于初始估计），方差较小。
  • $n=\infty$: (如果片段结束前达到) 即为MC，偏差小（无偏），方差较大。
  • $1 < n < \infty$: n-步Sarsa在偏差和方差之间进行权衡。较大的 $n$ 通常导致较小的偏差但较大的方差。
• 与控制结合: n-步Sarsa同样可以用于策略评估，并与策略改进步骤（如 $\epsilon$-greedy）结合以搜索最优策略。

5. 最优动作价值的TD学习：Q-Learning

Q-Learning是一种非常经典且重要的 离策略 (off-policy) TD控制算法。它直接学习最优动作价值函数 $q_\*(s,a)$。

Q-Learning 算法

• 核心思想: Q-Learning的更新不依赖于实际采取的下一个动作 $a\_{t+1}$，而是使用在下一个状态 $s\_{t+1}$ 上可能的最优动作的Q值（即 $\max\_{a'} q\_t(s\_{t+1}, a')$）来构建TD目标。
• Q-Learning 更新规则: 在时刻 $t$，智能体处于状态 $s\_t$，执行动作 $a\_t$（可以由任何策略产生，包括探索性策略），观察到奖励 $r\_{t+1}$ 和下一状态 $s\_{t+1}$。 $$ q\_{t+1}(s\_t, a\_t) = q\_t(s\_t, a\_t) + \alpha\_t [r\_{t+1} + \gamma \max\_{a'} q\_t(s\_{t+1}, a') - q\_t(s\_t, a\_t)] $$ 对于所有其他未被访问的状态-动作对 $(s,a) \neq (s\_t, a\_t)$： $$ q\_{t+1}(s,a) = q\_t(s,a) $$
• TD目标: $r\_{t+1} + \gamma \max\_{a'} q\_t(s\_{t+1}, a')$
• 与Sarsa的TD目标对比:
  • Sarsa: $r\_{t+1} + \gamma q\_t(s\_{t+1}, a\_{t+1})$ (依赖于实际选的 $a\_{t+1}$)
  • Q-Learning: $r\_{t+1} + \gamma \max\_{a'} q\_t(s\_{t+1}, a')$ (不依赖于实际选的 $a\_{t+1}$，而是贪婪地选择使 $q\_t(s\_{t+1}, \cdot)$ 最大化的动作)
• 数学思想: Q-Learning 是在求解用动作价值表示的 贝尔曼最优方程 (Bellman Optimality Equation): $$ q_\*(s,a) = E[R\_{t+1} + \gamma \max\_{a'} q_\*(S\_{t+1}, a') | S\_t=s, A\_t=a] $$ 因此，Q-Learning直接逼近最优动作价值函数 $q_\*$，而不需要显式的策略评估和策略改进交替进行（指其核心更新机制是直接面向最优价值的）。

离策略 (Off-policy) vs. 同策略 (On-policy)

• 背景: 在TD学习中，通常涉及两个策略：
  1. 行为策略 (Behavior Policy, $\pi\_b$): 用于与环境交互、生成经验样本的策略。
  2. 目标策略 (Target Policy, $\pi\_T$): 我们希望学习和评估并最终优化的策略。
• 定义:
  • 同策略 (On-policy): 行为策略和目标策略是同一个策略。即用当前正在学习和改进的策略去收集数据。
    • 例如：Sarsa。它用当前策略 $\pi\_t$ 选择 $a\_t$ 和 $a\_{t+1}$，并用此经验更新 $q\_{\pi\_t}$。
  • 离策略 (Off-policy): 行为策略和目标策略可以不同。即可以用一个固定的、探索性的策略收集数据，来学习另一个（可能是确定性的、最优的）目标策略。
    • 例如：Q-Learning。它的TD目标中的 $\max\_{a'} q\_t(s\_{t+1}, a')$ 隐含了一个贪婪的目标策略，而产生 $(s\_t, a\_t, r\_{t+1}, s\_{t+1})$ 的行为策略可以是任意的（例如 $\epsilon$-greedy 或完全随机）。
• 离策略的优势:
  • 更强的探索能力: 可以使用一个充分探索的行为策略（如随机策略）来收集覆盖状态-动作空间的数据，同时学习一个确定性的最优目标策略。
  • 学习历史数据: 可以利用过去收集到的数据进行学习，即使这些数据是由旧的或不同的策略产生的。
  • 学习人类经验: 可以学习人类演示者或其他智能体的经验。
• 判断算法是同策略还是离策略:
  1. 检查算法解决的数学问题:
     • Sarsa解的是 $q_\pi(s,a)$ 的贝尔曼方程，$\pi$ 是当前策略。
     • Q-Learning解的是 $q_\*(s,a)$ 的贝尔曼最优方程，这个方程本身不依赖于某个特定策略。
  2. 检查算法实施所需的数据:
     • Sarsa 需要 $(s\_t, a\_t, r\_{t+1}, s\_{t+1}, a\_{t+1})$，其中 $a\_{t+1}$ 必须由当前的目标/行为策略在 $s\_{t+1}$ 产生。
     • Q-Learning 只需要 $(s\_t, a\_t, r\_{t+1}, s\_{t+1})$ 来进行更新。$a\_t$ 可以由任意行为策略产生。

Q-Learning 实现

Q-Learning本身是离策略的，但其行为策略可以有不同选择：

1. Q-Learning (同策略版本 - 行为策略与目标策略相关联):

   • 行为策略通常是基于当前Q值的 $\epsilon$-greedy 策略。
   • 伪代码与Sarsa控制类似，主要区别在于Q值更新公式使用 $\max$ 操作。
   • 这里“同策略版本”是指行为策略是根据正在学习的Q值（目标）导出的，尽管Q-learning的更新机制本质上是离策略的。

   1对于每个片段 (episode)，执行：
   2  初始化 s_t
   3  只要 s_t 不是目标状态，则执行：
   4    根据 q_t 和 ε-greedy 策略选择 a_t  (行为策略)
   5    执行 a_t，得到 r_{t+1}, s_{t+1}
   6    更新 q 值 (目标策略是贪婪的)：
   7      q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - α_t [q_t(s_t, a_t) - (r_{t+1} + γmax_a' q_t(s_{t+1}, a'))]
   8    s_t ← s_{t+1}
   

2. Q-Learning (离策略版本 - 行为策略与目标策略分离):

   • 行为策略 $\pi\_b$ (例如，一个探索性强的策略，如均匀随机或固定的 $\epsilon$-greedy) 用于生成经验。
   • 目标策略 $\pi\_T$ 是基于当前Q值的贪婪策略 (deterministic greedy)。
   • 伪代码:

     1目标：从行为策略 πb 生成的经验样本中，学习最优目标策略 πT (通过学习q*)。
     2
     3对于由 πb 生成的每个片段 {s0, a0, r1, s1, a1, r2, ...}，执行：
     4  对于片段的每一步 t = 0, 1, 2, ...，执行：
     5    // (st, at) 来自 πb 的交互，rt+1, st+1 是环境反馈
     6    更新 (st, at) 的 q 值：
     7      q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - α_t [q_t(s_t, a_t) - (r_{t+1} + γmax_a' q_t(s_{t+1}, a'))]
     8    // 目标策略 πT (隐式地) 是 q_{t+1} 的贪婪策略
     9    // π_{T,t+1}(a|s_t) = 1 if a = argmax_a' q_{t+1}(s_t, a'), else 0
     

Q-Learning 示例 (网格世界)

• 任务: 为所有状态找到最优策略。
• 奖励设置: $r\_{\text{boundary}} = r\_{\text{forbidden}} = -1$, $r\_{\text{target}} = 1$, $\gamma=0.9$, $\alpha=0.1$。
• Ground Truth: 先展示该网格世界的最优策略和最优状态价值。
• 实验:
  1. 充分探索的行为策略: 使用均匀随机策略 (每个动作概率0.2) 作为行为策略 $\pi\_b$。
     • 结果: 离策略Q-Learning能够学到接近最优的策略。状态价值误差图显示误差随学习步数增加而减小。
  2. 探索不足的行为策略:
     • 行为策略 $\pi\_b$ 倾向于向右走 ($\epsilon=0.5$ 或 $\epsilon=0.1$ 的 $\epsilon$-greedy，但有固定偏好)。
     • 结果: 由于行为策略探索性不足，很多状态-动作对未被充分访问，导致Q-Learning学到的策略与最优策略有较大差距，状态价值误差也较大。
• 结论: Q-Learning作为离策略算法，其学习效果（尤其是能否找到全局最优）仍然依赖于行为策略能否提供足够覆盖度的经验数据。探索非常重要。

6. 统一的观点 (A Unified Point of View)

本讲介绍的多种TD算法，包括Sarsa, n-步Sarsa, Q-Learning, 甚至MC，都可以从一个统一的视角来看待。

统一的更新表达式

所有这些算法的动作价值更新都可以写成类似的形式：

或者

其中 $\bar{q}\_t$ 是不同算法中定义的 TD目标 (TD Target)。

统一的数学目标

所有这些算法都可以看作是求解相应 贝尔曼方程 (BE) 或 贝尔曼最优方程 (BOE) 的 随机近似 (Stochastic Approximation) 算法。

• Sarsa及其变种（Expected Sarsa, n-step Sarsa）以及MC，在用于控制时，通常与策略改进步骤（如 $\epsilon$-greedy）结合，通过GPI框架来搜索最优策略。
• Q-Learning直接求解贝尔曼最优方程，其目标 $q_*$ 已经对应最优策略。

与基于模型的算法对比:

• 价值迭代 (Value Iteration) 和 策略迭代 (Policy Iteration) 是 基于模型 (model-based) 的方法，它们也求解贝尔曼（最优）方程，但需要知道环境模型 $p(s',r|s,a)$。
• TD学习方法是 无模型 (model-free) 的方法，它们通过与环境交互采样经验来求解这些方程。

7. 总结 (Summary of Lecture)

1. 启发性示例: 展示了RM算法与TD算法的联系。
2. 基础TD算法 (状态价值): 介绍了TD(0)用于策略评估，核心概念是TD目标、TD误差和自举。
3. Sarsa (动作价值): 将TD思想扩展到动作价值，是同策略的控制算法。
4. Sarsa变种:
   • Expected Sarsa: 降低了Sarsa的方差。
   • n-step Sarsa: 统一了Sarsa和MC方法，提供了偏差-方差的权衡。
5. Q-Learning: 非常重要的离策略控制算法，直接学习最优动作价值函数。
   • On-policy vs. Off-policy: 是强化学习中的重要概念。Sarsa, MC (典型控制) 是on-policy，Q-Learning是off-policy。
   • 离策略性质使得Q-Learning在与神经网络结合（如Deep Q-Learning, DQN）时非常关键，因为可以利用经验回放 (experience replay) 等技术。
6. 统一视角: 所有TD算法共享相似的更新结构，区别在于TD目标的定义；它们都是求解贝尔曼（最优）方程的随机近似方法。
7. 展望: 下节课将介绍价值函数近似，将TD方法从表格形式推广到函数形式，引入神经网络，讲解经典的Deep Q-Learning。

核心要点:

• TD学习是强化学习中非常核心和实用的一类无模型方法。
• 理解TD目标、TD误差和自举是掌握TD算法的关键。
• Sarsa (on-policy) 和 Q-Learning (off-policy) 是两种基本且重要的TD控制算法。
• 选择合适的TD算法及参数 (如 $n$ in n-step Sarsa, $\alpha, \epsilon$) 对学习效果至关重要。
• 探索与利用的平衡对于所有控制算法都是核心问题。