强化学习的数学基础 - Chapter 7

赵老师开源的 Github 仓库、赵老师的 B站 课程视频

背景来自 XHS azzurra

Overview

时序差分方法（Temporal-Difference Learning，TD）是继 Monte Carlo 方法后的第二种 model-free 方法——但 Monte Carlo 方法是非增量式（non-incremental）的，TD 方法是 增量式（incremental）的。

Outline：

• 引入
• state-value 的 TD Learning
• action-value 的 TD Learning
  • Sarsa 算法
  • Expected Sarsa
  • n-step Sarsa
• optimal action-value 的 TD Learning：Q-Learning
  • 同策略 vs 异策略（On-policy vs Off-policy）
  • Q-Learning：伪代码与示例
• 统一视角与总结

TD learning 大部分是指一类 RL 算法，但有时候特指专门用于估计 state-value 的方法（Outline 中第二部分）

---

引入：RM 算法的应用

Lec 27

简单回顾一下上节课的内容。

示例1：简单均值估计

计算 $w = \mathbb{E}[X]$，基于 i.i.d. 样本 $\{x\}$。

• 改写为方程 $g(w) = w - \mathbb{E}[X] = 0$
• 带噪声的观测 $\tilde{g}(w, \eta) = w - x = (w - \mathbb{E}[X]) \ + (\mathbb{E}[X] - x) = g(w) + \eta$
• RM 算法：$w_{k+1} = w_k - \alpha_k \tilde{g}(w, \eta) = w_k - \alpha_k(w_k - x_k)$

示例2：函数的均值估计

计算 $w = \mathbb{E}[v(X)]$，基于 i.i.d. 样本 $\{x\}$。

• 构造 $g(w) = w - \mathbb{E}[v(X)]$
• $\tilde{g}(w, \eta) = w - v(x) = (w - \mathbb{E}[v(X)]) \ + (\mathbb{E}[v(X)] - v(x)) = g(w) + \eta$
• RM 算法：$w_{k+1} = w_k - \alpha_k \tilde{g}(w, \eta) = w_k - \alpha_k[w_k - v(x_k)]$

示例3：更复杂的均值估计

图穷匕见：R 即 return，v 为 state-value，$\gamma$ 为折扣因子。

计算 $w = \mathbb{E}[R + \gamma v(X)]$，其中 $R, X$ 是随机变量。

• 构造 $g(w) = w - \mathbb{E}[R + \gamma v(X)]$
• 仿上计算

  $$\begin{align*} \tilde{g}(w, \eta) &= w - [r + \gamma v(x)] \\ &= (w - \mathbb{E}[R+ \gamma v(X)]) + (\mathbb{E}[R+\gamma v(X)] - [r + \gamma v(x)]) \\ &= g(w) + \eta \end{align*}$$

• RM 算法：$w_{k+1} = w_k - \alpha_k[w_k - (r_k + \gamma v(x_k))]$

上述三个例子越来越复杂，但都可以用 RM 算法求解。我们将看到 TD 算法具有类似的表达式。

---

状态价值的 TD

Lec 28 & 29

算法描述

TD learning 不需要模型，但需要数据/经验：$\{(s_t, r_{t+1}, s_{t+1})\}^{\infty}_{t=0}$，这些数据由给定策略 $\pi$ 生成。

TD Learning Algorithm：

$$\begin{align*} v_{t+1}(s_t) &= v_t(s_t) - \alpha_t(s_t) \big[v_t(s_t) - [r_{t+1} + \gamma v_t(s_{t+1})] \big] \tag{1}\\ v_{t+1}(s) &= v_t(s),\quad \forall s \neq s_t \tag{2} \end{align*}$$

其中，$v_t(s_t)$ 是在 $t$ 时刻 $v_\pi(s_t)$ 的估计值，$\alpha_t(s_t)$ 是一个比较小的正数。

• 在时刻 $t$，只更新被访问状态 $s_t$ 的值，未访问状态 $s \neq s_t$ 的值保持不变。

算法特性

第一个式子可以重写为：

$$\underbrace{v_{t+1}(s_t)}_{\text{新估计值}} = \underbrace{v_t(s_t)}_{\text{当前估计值}} - \alpha_t(s_t)\underbrace{\color{red}{\left[v_t(s_t) - \color{lightblue}{\underbrace{[r_{t+1} + \gamma v_t(s_{t+1})]}_{\text{TD 目标 } \bar{v}_t}} \right]}}_{\text{TD 误差 } \delta_t} \tag{3}$$

• TD target：$\bar{v}_t \coloneqq r_{t+1} + \gamma v(s_{t+1})$，算法会驱动 $v(s_t)$ 趋向 $\bar{v}_t$。
• TD error：$\delta_t \coloneqq v(s_t) - [r_{t+1} + \gamma v(s_{t+1})] = v(s_t) - \bar{v}_t$

为何 $\bar{v}_t$ 称为 TD 目标？

因为算法驱动 $v(s_t)$ 趋向 $\bar{v}_t$：

$$\begin{align*} |v_{t+1}(s_t) - \bar{v}_t| &= \big| \big[v(s_t) - \alpha_t(s_t) \big(v_t(s_t) - \bar{v}_t \big) \big] - \bar{v}_t \big| \\ &= |1 - \alpha_t(s_t)||v_t(s_t) - \bar{v}_t| \\ &\leq |v_t(s_t) - \bar{v}_t| \end{align*}$$

如何理解 TD error？

$$\delta_t \coloneqq v(s_t) - [r_{t+1} + \gamma v(s_{t+1})] = v(s_t) - \bar{v}_t$$

• $\delta_t$ 是两个连续时间步之间的差异（一个是 $t$ 时刻，另一个是 $t+1$ 时刻）
• 它反映了 $v_t$ 与 $v_\pi$ 之间的差距：
  • 若 $v_t = v_\pi$，则 $\delta_t$ 应为零（在期望意义上）。
  • 反之，如果 $\delta_t$ 应为非零，则 $v_t \neq v_\pi.$

定义 $\delta_{\pi,t} = v_\pi(s_t) - [r_{t+1} + \gamma v_\pi (s_{t+1})]$，计算期望，

$$\mathbb{E}[\delta_{\pi,t} \mid S_t = s_t] = v_\pi(s_t) - \mathbb{E}\left[ R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s_t \right] = 0.$$

• TD 误差可解释为 新息（innovation），即从经验 experience $(s_t, r_{t+1}, s_{t+1})$ 中获得的新信息。

其他性质

• 式 (3) 中的 TD 算法仅估计给定策略的状态价值。
  • 它不估计动作价值。
  • 它不搜索最优策略。
• 稍后，我们将看到如何估计动作价值并进而搜索最优策略。
• 尽管如此，式 (3) 中的 TD 算法对于理解核心思想仍是根本性的。

TD 算法的数学本质

• Q： 该 TD 算法在数学上的作用是什么？
• A： 它在求解给定策略 $\pi$ 的贝尔曼方程。

之前我们学习的 Bellman 方程是 model-based 的，此处我们应该构造一个 model-free 的新形式。策略 $\pi$ 的 state-value 定义为

$$v_\pi(s) = \mathbb{E}[R + \gamma G \mid S = s], \quad s \in \mathcal{S} \tag{4}$$

其中，$G$ 为折扣回报。由于

$$\mathbb{E}[G \mid S = s] = \sum_a \pi(a|s) \sum_{s^\prime} p(s^\prime|s,a) v_\pi(s^\prime) = \mathbb{E}[v_\pi(S^\prime) \mid S = s],$$

其中，$S^\prime$ 为下一状态，我们可将 (4) 重写为

$$\color{lightblue}{v_\pi(s) = \mathbb{E}[R + \gamma v_\pi(S^\prime) \mid S = s], \quad s \in \mathcal{S}.} \tag{5}$$

式 (5) 是贝尔曼方程的另一种表达形式。它有时被称为 贝尔曼期望方程（Bellman expectation equation），是设计与分析 TD 算法的重要工具。

利用 RM（Robbins–Monro）算法可以求解式 (5) 中的贝尔曼方程。具体而言，通过构造

$$g(v(s)) = v(s) - \mathbb{E}[R + \gamma v_\pi(S^\prime) \mid s],$$

我们可将 (5) 重写为

$$g(v(s)) = 0.$$

$v_\pi(s)$ 就是上式的解！由于我们只能获得 $R$ 和 $S^\prime$ 的样本 $r$ 和 $s^\prime$，我们所拥有的带噪观测为

$$\begin{align*} \tilde{g}(v(s)) &= v(s) - \left[r + \gamma v_\pi(s^\prime)\right] \\[4pt] &= \underbrace{\left(v(s) - \mathbb{E}[R + \gamma v_\pi(S^\prime) \mid s]\right)}_{g(v(s))} + \underbrace{\left(\mathbb{E}[R + \gamma v_\pi(S^\prime) \mid s] - \left[r + \gamma v_\pi(s^\prime)\right]\right)}_{\eta}. \end{align*}$$

因此，求解 $g(v(s)) = 0$ 的 RM 算法为

$$\begin{align*} v_{k+1}(s) &= v_k(s) - \alpha_k \tilde{g}(v_k(s)) \\[4pt] &= v_k(s) - \alpha_k \left(v_k(s) - \left[r_k + \gamma v_\pi(s_k^\prime)\right]\right), \quad k = 1, 2, 3, \ldots \end{align*} \tag{6}$$

• $v_k(s)$ 为第 $k$ 步对 $v_\pi(s)$ 的估计
• $r_k, s_k^\prime$ 为第 $k$ 步获得的 $R, S^\prime$ 样本。

式 (6) 中的 RM 算法有两个值得特别关注的假设：

• 我们必须拥有经验集 $\{(s, r, s^\prime)\}$，其中 $k = 1, 2, 3, \ldots$。
• 我们假设对于任意 $s^\prime$，$v_\pi(s^\prime)$ 均已知，但实际上我们是不清楚 $v_\pi(s^\prime)$ 的。

为消除 RM 算法中的上述两个假设，我们可以对其进行修正：

• 对第一个问题：可以利用 trajectory 来解决。
  • 构造一个 trajectory，如果沿着 trajectory 恰好访问到 $s$，则更新之；否则，$s$ 所对应的估计值保持不动。
  • 将 $\{(s, r, s^\prime)\}$ 改为 $\{(s_t, r_{t+1}, s_{t+1})\}$，从而使算法能够利用一个回合（episode）中的序列样本。
• 对第二个问题：我们将 $v_\pi(s^\prime)$ 替换为其估计值 $v_k(s^\prime)$

收敛性分析

定理（TD Learning 的收敛性） 对于 TD 算法 (1)，若对所有 $s \in \mathcal{S}$ 均有

$$\sum_t \alpha_t(s) = \infty \quad \text{且} \quad \sum_t \alpha_t^2(s) < \infty,$$

则当 $t \to \infty$ 时，$v_t(s)$ 以概率 1 收敛于 $v_\pi(s)$。

注记：

• 该定理表明，对于给定策略 $\pi$，state-value 可以通过 TD 算法求得。
• $\sum_t \alpha_t(s) = \infty$ 与 $\sum_t \alpha_t^2(s) < \infty$ 必须对所有 $s \in \mathcal{S}$ 成立。
  • 在时间步 $t$，若 $s = s_t$（即状态 $s$ 在时间 $t$ 被访问），则 $\alpha_t(s) > 0$；否则，对所有 $s \neq s_t$ 有 $\alpha_t(s) = 0$。
  • 这要求每个状态必须被访问无限（或充分多）次。
• 学习率 $\alpha$ 通常被选为一个较小的常数。
  • 在上一节的 RM 算法中也说到了这点，如果 $\alpha_t$ 越来越少，会导致模型越来越轻视新获得的经验。
  • 此时，条件 $\sum_t \alpha_t^2(s) < \infty$ 不再成立。
  • 当 $\alpha$ 为常数时，仍可证明该算法在期望意义下收敛。

该定理的证明见赵老师所著教材。

TD Learning 与 MC Learning 的比较

Sarsa 是马上要讲的算法

TD/Sarsa Learning	MC Learning
在线（Online）：收到 reward 后立即更新 state/action-value	离线（Offline）：必须等到整个 episode 收集完毕
持续性任务（Continuing tasks）：可处理回合制和持续性任务	回合制任务（Episodic tasks）：只能处理有终止状态的任务
自举（Boostrapping）：更新依赖之前的估计，需要初始猜测	非自举（Non-Boostrapping）：可直接估计，不需要初始猜测
估计方差低：涉及随机变量较少。例如，Sarsa 需要 $R_{t+},S_{t+1},A_{t+1}$）	估计方差高：涉及整条轨迹的计算。为了估计 $q_\pi(s_t, a_t)$，我们需要对整个回合的轨迹采样：$R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots$ 如果 episode 的长度为 $L$，总共会有 $| \mathcal{A} |^L$ 个可能的 episode——我们仅用其中一条进行估计，可想而知，方差会很大。
因为 Boostrapping（如果初始估计不准确，会对后续持续造成影响，需要很多步才能减小），所以对 mean/expectation 的估计存在 bias	不涉及到任何初始值，是无偏估计

---

动作价值的 TD

• 上面基于 state-value 的 TD 算法，只能用于估计 state-value。
• Sarsa 算法及其变形：给定一个策略，能够估计 action-value（policy evaluation），然后再结合 policy improvement 来找最优策略。
• Q-learning：直接求解 optimal action-value，从而直接找到最优策略。

Sarsa 算法

Lec 30

算法描述

Sarsa 的目标：直接估计 action-value

假设拥有经验 $\{(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})\}_t$：

$$\color{red}{ \begin{align*} q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t)\left[q_t(s_t, a_t) - [r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})]\right] \\ q_{t+1}(s, a) &= q_t(s, a),\quad \forall (s, a) \neq (s_t, a_t) \end{align*}}$$

• $q_t(s, a)$ 为第 $t$ 步对 $q_\pi (s, a)$ 的估计值
• $\alpha_t(s_t, a_t)$ 为关于 $(s_t, a_t)$ 的学习率

为何叫 Sarsa？

• Sarsa 是 State-Action-Reward-State-Action 的缩写，因为算法的每一步都会涉及 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$

Sarsa 和之前的 TD learning 之间有什么关系？

• 把 TD learning 公式中的 $v_t(s)$ 替换为 $q_t(s, a)$ 就变为了 Sarsa，所以 Sarsa 可以称为是基于 action-value 的 TD 算法。

数学原理

Sarsa 的数学原理：Sarsa 的本质是在求解下式的随机逼近算法：

$$q_\pi(s, a) = \mathbb{E}[R + \gamma q_\pi(S^\prime, A^\prime) | s, a], \quad \forall s, a$$

这是以 action-value 表达的贝尔曼方程。

以下证明来自赵老师的书

之前的章节中，我们介绍过基于 action-value 的 Bellman 方程，

$$\begin{aligned} q_\pi(s,a) &= \sum_r r p(r|s,a) + \gamma \sum_{s^\prime} \sum_{a^\prime} q_\pi(s^\prime,a^\prime) p(s^\prime|s,a) \pi(a^\prime|s^\prime) \\ &= \sum_r r p(r|s,a) + \gamma \sum_{s^\prime} p(s^\prime|s,a) \sum_{a^\prime} q_\pi(s^\prime,a^\prime) \pi(a^\prime|s^\prime). \tag{7.14} \end{aligned}$$

这个方程建立了不同动作值之间的关系。因为

$$\begin{aligned} p(s^\prime,a^\prime|s,a) &= p(s^\prime|s,a) p(a^\prime|s^\prime,s,a) \\ &= p(s^\prime|s,a) p(a^\prime|s^\prime) \quad \text{（由于马尔可夫性质）} \\ &\doteq p(s^\prime|s,a) \pi(a^\prime|s^\prime), \end{aligned}$$

所以 (7.14) 可以重写为

$$\begin{align*} q_\pi(s,a) &= \sum_r r p(r|s,a) + \gamma \sum_{s^\prime} \sum_{a^\prime} q_\pi(s^\prime,a^\prime) p(s^\prime,a^\prime|s,a) \\ & =\mathbb{E}[R + \gamma q_\pi(S^\prime, A^\prime) | s, a], \quad \forall s, a \end{align*}$$

定理（Sarsa 收敛性）： 若 $\sum_t \alpha_t(s, a) = \infty$ 且 $\sum_t \alpha_t^2(s, a) < \infty$ 对所有 $(s, a)$ 成立，则 $q_t(s, a)$ 以概率 1 收敛到 $q_\pi(s, a)$。

上面的过程就是 policy evaluation 过程，我们还需要 policy improvement 过程。这种组合算法也被称为 Sarsa。

伪代码

伪代码：基于 Sarsa 的策略搜索

• 对于每个 episode，执行
  • 如果当前状态 $s_t$ 不是目标状态，执行
    • 收集经验 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$：
      • 具体而言，根据 $\pi_t(s_t)$ 执行动作 $a_t$，产生 $r_{t+1}, s_{t+1}$，然后根据 $\pi_t(s_{t+1})$ 执行动作 $a_{t+1}$。
    • 更新 q 值：
      • $q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)\Big[q_t(s_t, a_t) - \big[r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})\big]\Big]$
    • 更新策略：
      • $\pi_{t+1}(a|s_t) = 1 - \frac{\epsilon}{|\mathcal{A}|}(|\mathcal{A}| - 1), \quad \text{if } a = \argmax_a q_{t+1}(s_t, a)$
      • $\pi_{t+1}(a|s_t) = \frac{\epsilon}{|\mathcal{A}|}, \quad \text{else}$

对第二行的说明：此处到达目标状态后，可以选择强制停止，也可以不停。算法只关心还未到达目标状态的做法。

关于该算法的说明：

• $s_t$ 的策略在 $q(s_t, a_t)$ 更新后立即更新。这是基于广义策略迭代（generalized policy iteration）的思想。
• 该策略采用 $\epsilon$-贪婪而非贪婪，以更好地平衡利用（exploitation）和探索（exploration）。

明确核心思想与复杂之处：

• 核心思想很简单：即使用一种算法来求解给定策略的 Bellman 方程。
• 复杂之处在于，当我们试图找到最优策略并高效地工作时，问题会变得复杂。

例子

任务描述：

• 任务是从一个特定的起始状态找到一条通往目标状态的良好路径。
• 这个任务与之前所有的任务不同！
  • 之前我们会关注每一个状态的 state-value 和最优策略；
  • 现在，我们只关注从某一个特定状态出发，如何到达目标。
• $r_{\text{target}} = 0$，$r_{\text{forbidden}} = r_{\text{boundary}} = -10$，且 $r_{\text{other}} = -1$。学习率为 $\alpha = 0.1$，$\epsilon=0.1$。

用 Sarsa 找到的策略

• 左图展示了 Sarsa 得到的最终策略。
  • 可以看到，并非所有状态都具有最优策略。
  • 这里的 reward 最后总会小于 0，这是因为我们采用的是 $\epsilon$-贪心策略，或多或少会有一些负的 reward 混进来。
• 右图展示了每个回合的总奖励和长度。
  • 横坐标是回合数，纵坐标是沿着该 index 下的回合所得总奖励。
  • 每个回合后，按照已更新的策略重新采回合
  • 右图之下图：策略在一开始是很差的，需要近 200 步才能到达目标，但随着策略的改进，几十步就能到达目标了。

  每个回合的总奖励这一指标将被频繁使用。

期望 Sarsa 算法

Lec 31

期望 Sarsa 是 Sarsa 的一种变体：

$$\color{red}{ \begin{align*} q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t)\left[q_t(s_t, a_t) - (r_{t+1} + \gamma \mathbb{E}[q_t(s_{t+1}, A)])\right] \\ q_{t+1}(s, a) &= q_t(s, a),\quad \forall (s, a) \neq (s_t, a_t) \end{align*}}$$

其中，$\mathbb{E}[q_t(s_{t+1}, A)] = \sum_a \pi_t(a|s_{t+1}) q_t(s_{t+1}, a) = v_t(s_{t+1})$ 是 $q_t(s_{t+1}, a)$ 在策略 $\pi_t$ 下的期望。

与 Sarsa 的比较：

• TD target：
  • 从 $r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})$ 变为 $r_{t+1} + \gamma \mathbb{E}[q_t(s_{t+1}, A)]$
  • 这里计算不再需要 $a_{t+1}$
• 涉及到求期望，因此需要更多计算；
• 但 Expected Sarsa 随机性下降（随机变量从 $\{s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}\}$ 减少为 $\{s_t, a_t, r_{t+1}, s_{t+1}\}$），这会有效减少估计方差

数学原理

期望 Sarsa（Expected Sarsa）是一种随机近似算法，用于求解以下方程：

$$q_\pi(s,a) = \mathbb{E}\left[R_{t+1} + \gamma \mathbb{E}_{A_{t+1}\sim\pi(S_{t+1})}\big[q_\pi(S_{t+1}, A_{t+1})\big] \,\middle|\, S_t=s, A_t=a\right], \quad \forall s,a.$$

上述方程本质上是贝尔曼方程的另一种表达形式。这是因为：将下式带入到上面的方程中

$$\mathbb{E}\big[q_\pi(S_{t+1}, A_{t+1}) \,\big|\, S_{t+1}\big] = \sum_{A^\prime} q_\pi(S_{t+1}, A^\prime) \pi(A^\prime|S_{t+1}) = v_\pi(S_{t+1})$$

可以得到，

$$q_\pi(s,a) = \mathbb{E}\left[R_{t+1} + \gamma v_\pi(S_{t+1}) \,\middle|\, S_t=s, A_t=a\right].$$

不难看出这就是贝尔曼方程。

伪代码

将上面的 policy evaluation 搭载 $\epsilon$-Greedy 策略，即可得到完整算法。

由 $\epsilon$-Greedy 策略，可以进一步将均值公式改写为，

$$\begin{align*} \mathbb{E}[q_t(s_{t+1}, A)] &= \sum_a \pi_t(a|s_{t+1}) q_t(s_{t+1}, a) \\ &= (1-\epsilon) q_t(s_{t+1}, a_{\max}) + \frac{\epsilon}{|\mathcal{A}|} \sum_{a^\prime} q_t(s_{t+1}, a^\prime) \end{align*}$$

其中，$a_{\max} = \argmax_a q_t(s_{t+1},a)$ 为最大的 $q_t$ 所对应的动作。

伪代码：基于 Expected Sarsa 的策略搜索

• 对于每个 episode，执行
  • 如果当前状态 $s_t$ 不是目标状态，执行
    • 收集经验 $(s_t, a_t, r_{t+1}, s_{t+1})$：
      • 具体而言，根据 $\pi_t(s_t)$ 执行动作 $a_t$，产生 $r_{t+1}, s_{t+1}$。
    • 计算期望：
      • $\mathbb{E}[q_t(s_{t+1}, A)] = (1-\epsilon) q_t(s_{t+1}, a_{\max}) + \frac{\epsilon}{|\mathcal{A}|} \sum_{a^\prime} q_t(s_{t+1}, a^\prime)$
    • 更新 q 值：
      • $q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)\left[q_t(s_t, a_t) - (r_{t+1} + \gamma \mathbb{E}[q_t(s_{t+1}, A)])\right]$
    • 更新策略：
      • $\pi_{t+1}(a|s_t) = 1 - \frac{\epsilon}{|\mathcal{A}|}(|\mathcal{A}| - 1), \quad \text{if } a = \argmax_a q_{t+1}(s_t, a)$
      • $\pi_{t+1}(a|s_t) = \frac{\epsilon}{|\mathcal{A}|}, \quad \text{else}$

例子

Expected Sarsa 的例子

n 步 Sarsa 算法

n-step Sarsa 可统一 Sarsa 和 Monte Carlo Learning

算法描述

按照定义：$q_\pi(s, a) = \mathbb{E}\left[ G_t \middle|\, S_t=s, A_t=a\right]$，其中的折扣回报 $G_t$，可以按不同形式分解！

• Sarsa：$G_t^{(1)} = R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1})$
• n-step Sarsa：$G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^n q_\pi(S_{t+n}, A_{t+n})$
• MC：$G_t^{(\infty)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$

注：上面的三种形式都是等价的，只是分解方式不同。

• Sarsa 旨在求解：
  • $q_\pi(s,a) = \mathbb{E}\big[G_t^{(1)} \,\big|\, s,a\big] = \mathbb{E}\big[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) \,\big|\, s,a\big].$
• Monte Carlo Learning 旨在求解：
  • $q_\pi(s,a) = \mathbb{E}\big[G_t^{(\infty)} \,\big|\, s,a\big] = \mathbb{E}\big[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \,\big|\, s,a\big].$
• $n$-step Sarsa 旨在求解：
  • $q_\pi(s,a) = \mathbb{E}\big[G_t^{(n)} \,\big|\, s,a\big] = \mathbb{E}\big[R_{t+1} + \gamma R_{t+2} + \dots + \gamma^n q_\pi(S_{t+n}, A_{t+n}) \,\big|\, s,a\big].$

因此，$n$-step Sarsa 更为一般，因为当 $n=1$ 时它退化为（单步）Sarsa 算法，当 $n=\infty$ 时它退化为 MC Learning 算法。

算法：

$$q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)\left[q_t(s_t, a_t) - [r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^n q_t(s_{t+n}, a_{t+n})]\right]$$

• $n$-step Sarsa 需要 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}, \dots, r_{t+n}, s_{t+n}, a_{t+n})$
• 由于 $(r_{t+n}, s_{t+n}, a_{t+n})$ 在时刻 $t$ 尚未被收集，因此我们无法在步骤 $t$ 实现 $n$-step Sarsa。
  • 然而，我们可以等到时刻 $t+n$ 再更新 $(s_t, a_t)$ 的 $q$ 值：

  $$q_{t+n}(s_t, a_t) = q_{t+n-1}(s_t, a_t)-\alpha_{t+n-1}(s_t, a_t)\Big[q_{t+n-1}(s_t, a_t) - \big[r_{t+1} + \gamma r_{t+2} + \dots + \gamma^n q_{t+n-1}(s_{t+n}, a_{t+n})\big]\Big].$$

• 由于 $n$-step Sarsa 将 Sarsa 和 MC Learning 作为两个极端情况包含在内，其性能是 Sarsa 和 MC Learning 的折中：
  • 如果 $n$ 很大，其性能接近 MC Learning，因此方差大但偏差小。
  • 如果 $n$ 很小，其性能接近 Sarsa，因此由于初始猜测而有相对较大的偏差，且方差相对较低。
• 最后，$n$-step Sarsa 也可用于策略评估。它可以与策略改进步骤相结合，以搜索最优策略。

伪代码

符号说明：

• $\tau$：历史时刻；$t$：当前时刻；$T$：episode 结束时刻（长度）
• n 步回报：$G_{\tau:\tau+n} = r_{\tau+1} + \gamma r_{\tau+2} + \dots + \gamma^{n-1} r_{\tau+n} + \gamma^n q(s_{\tau+n}, a_{\tau+n})$
• 若 $\tau+n$ 超出终止时刻，则去掉自举项，仅保留真实奖励
• 更新公式：$q(s_\tau,a_\tau) \leftarrow q(s_\tau,a_\tau) - \alpha(s_\tau,a_\tau)\big[q(s_\tau,a_\tau) - G_{\tau:\tau+n}\big]$

伪代码：基于 n-step Sarsa 的策略搜索

• 对于每个 episode，执行
  • 初始化 $t \leftarrow 0$，起始状态 $s_0$
  • 根据当前策略 $\pi$，在 $s_0$ 处选择动作 $a_0$
  • 当 $s_t$ 不是终止状态，执行
    • 执行动作 $a_t$，观测奖励 $r_{t+1}$ 和下一状态 $s_{t+1}$
    • 如果 $s_{t+1}$ 是终止状态：
      • 直接跳出当前循环，进入尾部更新
    • 否则：
      • 根据当前策略 $\pi$，在 $s_{t+1}$ 处选择动作 $a_{t+1}$
    • 如果 时刻 $t \ge n-1$（说明在 $t$ 之前，已收集够 $n$ 步数据，可以更新 $n$ 步之前的历史状态）：
      • 令待更新的历史时刻 $\tau \leftarrow t - n + 1$
      • 计算 n 步回报 G：（$\tau : t = \tau+n-1$）
        • $G = r_{\tau+1} + \gamma r_{\tau+2} + \dots + \gamma^{n-1} r_{t+1} + \gamma^n q(s_{t+1}, a_{t+1})$
      • 更新 Q 值：$q(s_\tau, a_\tau) = q(s_\tau, a_\tau) - \alpha(s_\tau, a_\tau)\Big[q(s_\tau, a_\tau) - G\Big]$
      • 策略改进：对状态 $s_\tau$ 更新 $\varepsilon$-贪心策略
        • $\pi(a|s_\tau) = 1 - \frac{\epsilon}{|\mathcal{A}|}(|\mathcal{A}| - 1), \quad \text{if } a = \arg\max_a q(s_\tau, a)$
        • $\pi(a|s_\tau) = \frac{\epsilon}{|\mathcal{A}|}, \quad \text{else}$
    • $t \leftarrow t + 1$
  • 尾部更新：遍历 episode 末尾不足 n 步、尚未更新的所有历史状态
    • 对于 $\tau = T-n+2,\ \dots,\ T$，执行
      • 计算截断回报 G（从 $\tau$ 到终止的全部真实奖励，无自举项）：
        • $G = r_{\tau+1} + \gamma r_{\tau+2} + \dots + \gamma^{t-\tau} r_{t+1}$
      • 更新 Q 值：$q(s_\tau, a_\tau) = q(s_\tau, a_\tau) - \alpha(s_\tau, a_\tau)\Big[q(s_\tau, a_\tau) - G\Big]$
      • 策略改进：对状态 $s_\tau$ 更新$\varepsilon$-贪心策略
        • $\pi(a|s_\tau) = 1 - \frac{\epsilon}{|\mathcal{A}|}(|\mathcal{A}| - 1), \quad \text{if } a = \arg\max_a q(s_\tau, a)$
        • $\pi(a|s_\tau) = \frac{\epsilon}{|\mathcal{A}|}, \quad \text{else}$

Q-Learning

Lec 32 & 33

Q-learning 是最广泛使用的 RL 算法之一，DQN（Deep Q-Learning）就是其变形。

从数学上来讲的区别：

• Sarsa 系列算法只能进行 policy evaluation，因此必须与 policy improvement 结合才能找到最优策略，
• 而 Q-learning 可直接估计 optimal action-value，因此可以直接找到最优策略。

算法描述

Q-learning 算法：

$$\color{red}{ \begin{align*} q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t)\left[q_t(s_t, a_t) - [r_{t+1} + \gamma \max_{a \in \mathcal{A}} q_t(s_{t+1}, a)]\right] \\ q_{t+1}(s,a) &= q_t(s,a), \quad \forall (s, a) \neq (s_t, a_t) \end{align*} }$$

与 Sarsa 的唯一区别是 TD 目标：

• Q-learning：$r_{t+1} + \gamma \max_{a \in \mathcal{A}} q_t(s_{t+1}, a)$
• Sarsa：$r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})$

数学原理

Q-learning 是在求解基于 action-value 的 贝尔曼最优方程：

$$q(s, a) = \mathbb{E}\left[R_{t+1} + \gamma \max_a q(S_{t+1}, a) \;\Big|\; S_t = s, A_t = a\right], \quad \forall (s, a)$$

这是因为：根据期望的定义，上式可重写为

$$q(s,a) = \sum_r p(r|s,a) r + \gamma \sum_{s^\prime} p(s^\prime|s,a) \max_{a \in \mathcal{A}(s^\prime)} q(s^\prime,a).$$

对方程的两边取最大可得

$$\max_{a \in \mathcal{A}(s)} q(s,a) = \max_{a \in \mathcal{A}(s)} \left[ \sum_r p(r|s,a) r + \gamma \sum_{s^\prime} p(s^\prime|s,a) \max_{a \in \mathcal{A}(s^\prime)} q(s^\prime,a) \right].$$

通过定义 $v(s) \doteq \max_{a \in \mathcal{A}(s)} q(s,a)$，上面的方程可重写为

$$\begin{aligned} v(s) &= \max_{a \in \mathcal{A}(s)} \left[ \sum_r p(r|s,a) r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v(s^\prime) \right] \\ &= \max_{\pi} \sum_{a \in \mathcal{A}(s)} \pi(a|s) \left[ \sum_r p(r|s,a) r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v(s^\prime) \right]. \end{aligned}$$

上式就是用 state-value 表示的贝尔曼最优方程，这已经在第3章有详细讨论。

因此，Q-Learning 最后会求出最优 action-value，从而得到最优策略。

同策略与异策略

根据上面的这些算法，我们可以注意到，在 TD learning 任务中，往往存在两种策略：

• 行为策略（behavior policy）：用于生成经验样本的策略。
• 目标策略（target policy）：不断更新朝向最优策略的策略。

根据上面两种策略，我们就能定义两大类的强化学习算法：

• 同策略（On-policy）：行为策略与目标策略相同。
  • 例如，我用策略与环境交互得到 experience，再用 experience 改进策略；改进之后，再交互，再改进……
• 异策略（Off-policy）：行为策略与目标策略不同。
  • 例如，我用一个策略与环境大量交互得到大量 experience，再拿这一批 experience 对策略改进；改进之后，再交互再改进……

off-policy的优势：

• 可以基于其他探索性较强的策略得到的 experience samples 来搜索最优策略（站在巨人的肩膀上）
  • 例如，behavior policy 可选为探索性策略，生成访问每个 state-action 对的 episode，进而得到 action-value
  • 否则，如果 target policy = behavior policy，此时我需要把 target policy 作为 behavior policy 生成经验。而 target policy 可能是 Greedy/$\epsilon$-Greedy 的，这就会导致策略的探索性不足。

如何判断一个算法是 On-policy 还是 Off-policy ？

• 从数学原理上看
• 算法在实现过程中，需要哪些数据

Sarsa 是 on-policy 的

• 首先，Sarsa 旨在求解给定策略 $\pi$ 的贝尔曼方程：$q_{\pi}(s, a) = \mathbb{E}\left[R + \gamma q_{\pi}(S^\prime, A^\prime) \mid s, a\right], \quad \forall s, a.$
  • 其中，$R \sim p(R \mid s, a)$，$S^\prime \sim p(S^\prime \mid s, a)$，$A^\prime \sim \pi(A^\prime \mid S^\prime)$。
• 其次，算法为：$q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)\left[q_t(s_t, a_t) - \left[r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})\right]\right],$
  • 这需要 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$：
    • 若 $(s_t, a_t)$ 已给定，则 $r_{t+1}$ 和 $s_{t+1}$ 不依赖于任何策略！
    • $a_{t+1}$ 是按照 $\pi_t(s_{t+1})$ 生成的！
• $\pi_t$ 既是目标策略（target policy），也是行为策略（behavior policy）。

Monte Carlo Learning 是 on-policy 的

• 首先，MC 方法旨在求解：$q_{\pi}(s, a) = \mathbb{E}\left[R_{t+1} + \gamma R_{t+2} + \ldots \mid S_t = s, A_t = a\right], \quad \forall s, a.$
  • 其中样本是按照给定策略 $\pi$ 生成的。
• 其次，MC 方法的实现为：$q(s, a) \approx r_{t+1} + \gamma r_{t+2} + \ldots$
  • 一个策略被用来生成样本，这些样本进一步被用于估计该策略的动作值。基于动作值，我们可以改进策略。

Q-learning 是 off-policy 的

• 首先，Q-learning 旨在求解贝尔曼最优性方程：$q(s, a) = \mathbb{E}\left[R_{t+1} + \gamma \max_{a} q(S_{t+1}, a) \,\middle|\, S_t = s, A_t = a\right], \quad \forall s, a.$
• 其次，算法为：$q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)\left[q_t(s_t, a_t) - \left[r_{t+1} + \gamma \max_{a \in \mathcal{A}} q_t(s_{t+1}, a)\right]\right]$
  • 这需要 $(s_t, a_t, r_{t+1}, s_{t+1})$。
    • 若 $(s_t, a_t)$ 已给定，则 $r_{t+1}$ 和 $s_{t+1}$ 不依赖于任何策略！
    • 从 $s_t$ 生成 $a_t$ 的行为策略（behavior policy）可以是任意的。目标策略将收敛到最优策略。

伪代码

由于 Q-learning 是 off-policy（异策略）的，它完全可以按 off-policy 或 on-policy 两种方式实现，只需要调整 behavior policy 和 target policy 即可。

伪代码：通过 Q-learning 进行策略搜索（on-policy 版本）

• 对于每个 episode，执行
  • 如果当前状态 $s_t$ 不是目标状态，执行
    • 收集经验 $(s_t, a_t, r_{t+1}, s_{t+1})$：
      • 具体而言，根据 $\pi_t(s_t)$ 执行动作 $a_t$，产生 $r_{t+1}, s_{t+1}$。
    • 更新 q 值：
      • $q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)\left[q_t(s_t, a_t) - \left[r_{t+1} + \gamma \max_a q_t(s_{t+1}, a)\right]\right]$
    • 更新策略：
      • $\pi_{t+1}(a|s_t) = 1 - \frac{\epsilon}{|\mathcal{A}|}(|\mathcal{A}| - 1), \quad \text{if } a = \arg\max_a q_{t+1}(s_t, a)$
      • $\pi_{t+1}(a|s_t) = \frac{\epsilon}{|\mathcal{A}|}, \quad \text{otherwise}$

注：和 Sarsa 系列的结构一样，只是修改了更新 q 值的公式。

伪代码：通过 Q-learning 进行最优策略搜索（off-policy 版本）

• 对于每个由 $\pi_b$ 生成的 episode $\{s_0, a_0, r_1, s_1, a_1, r_2, \ldots\}$，执行
  • 对于 episode 中的每一步 $t = 0, 1, 2, \ldots$，执行
    • 更新 q 值：
      • $q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)\left[q(s_t, a_t) - \left[r_{t+1} + \gamma \max_a q_t(s_{t+1}, a)\right]\right]$
    • 更新目标策略：
      • $\pi_{T,t+1}(a|s_t) = 1, \quad \text{if } a = \arg\max_a q_{t+1}(s_t, a)$
      • $\pi_{T,t+1}(a|s_t) = 0, \quad \text{otherwise}$

注：上面的 $\pi_b$ 表示 behavior policy，$t+1$ 时刻的目标策略为 $\pi_{T,t+1}$。

在 off-policy Q-learning 中我们使用的是 $\epsilon$-Greedy 策略，而在 on-policy Q-learning 中我们使用 Greedy 策略，这是为什么？

• 因为 offf-policy Q-learning 需要藉由改进后的策略来生成下一步所用数据，所以需要 $\epsilon$-Greedy 来提供一定的随机性（探索性）；on-policy Q-learning 是用 $\pi_b$ 生成数据的，所以我们可以放心地直接使用最优的 Greedy 策略。

例子

任务描述：

• 以下示例的任务是为所有状态找到一个最优策略。
• 奖励设置为 $r_{\text{boundary}} = r_{\text{forbidden}} = -1$，且 $r_{\text{target}} = 1$。折扣因子为 $\gamma = 0.9$。学习率为 $\alpha = 0.1$。
• 此处的 Behavior Policy 为均匀采样策略：5 个 action 各自概率为 0.2
  • 探索性较强！

Ground Truth

左图：行为策略为均匀采样；走 100w 步所生成的 episode
右图：使用 off-policy Q-learning 找到的策略；纵轴为当前步 state-value 与 optimal state-value 之间的 error，可以看到，error 是单调下降的。

若策略探索不充分，样本质量差，导致学习效果不佳。使用 $\varepsilon$-贪心策略时，$\varepsilon$ 越大探索能力越强，但过大会影响最优性。

如果 Behavior policy 的探索性较弱，会导致难以收敛到最优策略

统一视角与总结

Lec 34

本章所有算法可用统一表达式表示：

$$q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)[q_t(s_t, a_t) - \bar{q}_t]$$

其中，$\bar{q}_t$ 是 TD target.

• 如果取 $\alpha_t = 1$，则可以表示 Monte Carlo Learning

不同算法对应的 TD target

本章的算法都可以视作是用于求解 Bellman 方程/Bellman 最优方程的随即近似算法。

不同算法对应的数学本质

下节课会介绍 DQN 算法：在若干 TD 算法中选用 Q-learning 和神经网络相结合，是因为其 Off-policy 的性质！