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

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

背景来自 XHS 像素点 Z（如有问题，请在下方评论区留言，侵删）

Overview

之前我们的 TD Learning 所用数据是基于表格（tabular representation）的。本章的 主要想法 是：

• 将 tabular representation 拓展为 function representation
• 将神经网络与强化学习相结合
  • 例如，把神经网络引入 Q-learning，产生出经典的 DQN 算法

Outline

1. 动机示例：曲线拟合
2. state value 估计算法：如何建立目标函数、优化算法、用什么去近似
3. action value 的估计算法：
   1. 值函数近似的 Sarsa
   2. 值函数近似的 Q-learning
4. optimal action value 的估计算法：DQN
5. 总结

---

动机示例：曲线拟合

Lec 35

到目前为止，本书中的状态和动作值都是用表格来表示的。

• 例如，动作值：

	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$
$s_1$	$q_\pi(s_1,a_1)$	$q_\pi(s_1,a_2)$	$q_\pi(s_1,a_3)$	$q_\pi(s_1,a_4)$	$q_\pi(s_1,a_5)$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$s_9$	$q_\pi(s_9,a_1)$	$q_\pi(s_9,a_2)$	$q_\pi(s_9,a_3)$	$q_\pi(s_9,a_4)$	$q_\pi(s_9,a_5)$

• 优点：直观且易于分析
• 缺点：难以处理大规模或连续的状态或动作空间。
  • 主要体现在两个方面：
    1. 存储：如果将连续空间离散化时，网格很稀疏，那么会难以精确近似连续空间；如果很密，则数据量过大，在计算方面会面临困难。
    2. 泛化能力：当有许多 state-action pair 存在，而且必须全部访问到才能估计出其值——但在实践中我们很可能无法访问到所有 pairs，这就导致难以估计出其值。

从表格到函数

假设有一维状态 $s_1, \ldots, s_{|\mathcal{S}|}$，状态值为 $v_\pi(s_1), \ldots, v_\pi(s_{|\mathcal{S}|})$。假设 $|\mathcal{S}|$ 非常大，我会希望用简单曲线近似这些点以节省存储。

以函数来节省存储

首先，我们使用最简单的直线来拟合这些点。假设该直线的方程为

$$\hat{v}(s, w) = as + b = \underbrace{[s, 1]}_{\phi^T(s)} \underbrace{\begin{bmatrix} a \\ b \end{bmatrix}}_{w} = \phi^T(s)w$$

其中

• $w$ 是参数向量
• $\phi(s)$ 是 $s$ 的特征向量
• $\hat{v}(s, w)$ 关于 $w$ 是线性的

函数表示的优点

• 表格表示需要存储 $|\mathcal{S}|$ 个状态值。而现在，我们只需存储两个参数 $a$ 和 $b$。
• 每当我们想要使用状态 $s$ 的值时，都可以通过计算 $\phi^T(s)w$ 得到。
• 然而，这种好处并非免费的。它是有代价的：状态值无法被精确表示。这就是为什么这种方法被称为 值函数近似（value function approximation）。

其次，我们也可以使用二阶曲线来拟合这些点：

$$\hat{v}(s, w) = as^2 + bs + c = \underbrace{[s^2, s, 1]}_{\phi^T(s)} \underbrace{\begin{bmatrix} a \\ b \\ c \end{bmatrix}}_{w} = \phi^T(s)w$$

在这种情况下，

• $w$ 和 $\phi(s)$ 的维度增加了，但值可能被拟合得更加精确。
• 尽管 $\hat{v}(s, w)$ 关于 $s$ 是 非线性 的，但它关于 $w$ 是 线性 的。非线性被包含在 $\phi(s)$ 中。

第三，我们可以使用甚至更高阶的多项式曲线或其他复杂曲线来拟合这些点。

• 优点：可以更好地近似。
• 缺点：需要更多的参数。

小结

• 思想：使用 参数化函数（parameterized functions）来近似状态和动作值：$\hat{v}(s, w) \approx v_\pi(s)$，其中 $w \in \mathbb{R}^m$ 是参数向量。
• 优点：
  1. 存储：$w$ 的维度可能 远小于 $|\mathcal{S}|$。
  2. 泛化：当访问某个状态 $s$ 时，参数 $w$ 会被更新，从而使得一些其他 未访问过 的状态的值也能随之被更新。

---

状态值估计算法

Lec 36 & 37 & 38

设 $v_\pi(s)$ 为真实状态值，$\hat{v}(s, w)$ 为近似函数。目标：当函数结构确定的时候（已知 $\phi^T(s)$），找到最优 $w$ 使得 $\hat{v}(s, w)$ 最佳近似 $v_\pi(s)$。

因此这个问题本质上是一个 policy evaluation：给定一个 policy $\pi$，我们需要用 $\hat{v}(s, w)$ 去求真实的 $v_\pi(s)$。

上面的想法可以推广为求 action value，然后进一步推广为求 optimal policy。

想实现这一点，我们需要分两步进行：

1. 定义一个合适的目标函数
2. 对目标函数进行优化

目标函数

以下就是值函数近似方法（value function approximation）对应的 目标函数：

$$J(w) = \mathbb{E}[(v_\pi(S) - \hat{v}(S, w))^2]$$

其中的 $S$ 是一个随机变量，状态 $S$ 的概率分布有两种选择：

1. 均匀分布：所有状态同等重要。

   $$J(w) = \frac{1}{|\mathcal{S}|}\sum_s (v_\pi(s) - \hat{v}(s, w))^2$$

   缺点是不考虑策略下 Markov 过程的真实动态。
2. 平稳分布：更频繁访问的状态权重更高。

$$J(w) = \sum_s (v_\pi(s) - \hat{v}(s, w))^2 = \sum_{s \in \mathcal{S}} d_\pi(s)(v_\pi(s) - \hat{v}(s, w))^2$$

其中，$\{d_\pi(s)\}_{s \in \mathcal{S}}, \ d_\pi(s) \ge 0$ 描述策略 $\pi$ 下 Markov 过程的长期行为。

关于稳态分布的更多解释

• 平稳（Stationary）：长期行为
• 分布（Distribution）：状态的分布
• 稳态：当智能体按照某个策略运行很长时间后，智能体处于任意状态的概率都可以用这个分布来描述。

备注：

• 平稳分布也被称为 稳态分布（steady-state distribution） 或 极限分布（limiting distribution）。
• 理解它对掌握值函数近似方法至关重要。
• 它对下一讲中的策略梯度方法也很重要。

示例说明

• 给定图中所示的策略。
• $n_\pi(s)$ 表示在由策略 $\pi$ 生成的一个非常长的回合中，状态 $s$ 被访问的次数。
• 那么，$d_\pi(s)$ 可以近似为：

$$d_\pi(s) \approx \frac{n_\pi(s)}{\sum_{s^\prime \in \mathcal{S}} n_\pi(s^\prime)}$$

平稳分布的近似计算

事实上，上述例子的收敛值是可以预测的，因为它们就是 $d_\pi$ 的各个分量：

$$d_\pi^T = d_\pi^T P_\pi$$

对于本例，转移矩阵 $P_\pi$ 为：

$$P_\pi = \begin{bmatrix} 0.3 & 0.1 & 0.6 & 0 \\ 0.1 & 0.3 & 0 & 0.6 \\ 0.1 & 0 & 0.3 & 0.6 \\ 0 & 0.1 & 0.1 & 0.8 \end{bmatrix}$$

可以计算出，对应于特征值 1 的左特征向量为：

$$d_\pi = \begin{bmatrix} 0.0345, & 0.1084, & 0.1330, & 0.7241 \end{bmatrix}^T$$

更全面的介绍可以在赵老师的书中找到。

优化算法

既然我们有了目标函数，下一步就是对其进行优化。

• 为了最小化目标函数 $J(w)$，我们可以使用 梯度下降（gradient-descent）算法：

$$w_{k+1} = w_k - \alpha_k \nabla_w J(w_k)$$

梯度下降

真实梯度为：

$$\begin{align*} \nabla_w J(w) &= \nabla_w \mathbb{E}\left[(v_\pi(S) - \hat{v}(S, w))^2\right] \\ &= \mathbb{E}\left[\nabla_w (v_\pi(S) - \hat{v}(S, w))^2\right] \\ &= 2\mathbb{E}\left[(v_\pi(S) - \hat{v}(S, w))(-\nabla_w \hat{v}(S, w))\right] \\ &= -2\mathbb{E}\left[(v_\pi(S) - \hat{v}(S, w))\nabla_w \hat{v}(S, w)\right] \end{align*}$$

但上述真实梯度涉及期望的计算，很自然地想到使用 SGD 来进行优化。

随机梯度下降

我们可以用 随机梯度 来替代真实梯度：

$$w_{t+1} = w_t + \alpha_t (v_\pi(s_t) - \hat{v}(s_t, w_t)) \nabla_w \hat{v}(s_t, w_t),$$

其中 $s_t$ 是 $S$ 的一个样本。

• 此处，$2\alpha_k$ 被合并到 $\alpha_k$ 中。
• 该算法 不可实现，因为它需要真实的状态值 $v_\pi$，而这正是我们需要估计的未知量。
• 我们可以用一个 近似值 来替换 $v_\pi(s_t)$，从而使算法变得可实现。

具体实现方法：

1. 基于函数近似的 MC Learning
   • 令 $g_t$ 为从回合中状态 $s_t$ 开始的折扣回报。那么，$g_t$ 可以用来近似 $v_\pi(s_t)$。算法变为：

   $$w_{t+1} = w_t + \alpha_t (g_t - \hat{v}(s_t, w_t)) \nabla_w \hat{v}(s_t, w_t).$$

2. 基于函数近似的 TD Learning
   • 根据 TD 学习的思想，$r_{t+1} + \gamma \hat{v}(s_{t+1}, w_t)$ 可以被视为 $v_\pi(s_t)$ 的一个近似。那么，算法变为：

   $$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \hat{v}(s_{t+1}, w_t) - \hat{v}(s_t, w_t)\right] \nabla_w \hat{v}(s_t, w_t).$$

伪代码：基于函数近似的 TD Learning

初始化： 一个关于 $w$ 可微的函数 $\hat{v}(s, w)$，初始参数 $w_0$。

目标： 近似给定策略 $\pi$ 的真实状态值。

• 对于按照策略 $\pi$ 生成的每个 episode，执行：
  • 对于每一步 $(s_t, r_{t+1}, s_{t+1})$，执行：
    • 在一般情况下，

      $$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \hat{v}(s_{t+1}, w_t) - \hat{v}(s_t, w_t)\right] \nabla_w \hat{v}(s_t, w_t)$$

    • 在线性情况下，

      $$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \phi^T(s_{t+1})w_t - \phi^T(s_t)w_t\right] \phi(s_t)$$

它只能估计给定策略的状态值，但理解它对后续介绍的其他算法非常重要。

函数逼近器的选择

一个尚未回答的重要问题是：如何选择函数 $\hat{v}(s, w)$？

• 第一种方法，也是以前广泛使用的方法，是使用线性函数：

  $$\hat{v}(s, w) = \phi^T(s)w$$

  这里，$\phi(s)$ 是特征向量，可以是 多项式基（polynomial basis）、傅里叶基（Fourier basis）、……（详见教材）
• 第二种方法，也是 当今广泛使用 的方法，是使用神经网络作为 非线性 函数近似器。
  • 神经网络的输入是状态，输出是 $\hat{v}(s, w)$，网络参数是 $w$

线性情况下的 TD 算法

在线性情况下，其中 $\hat{v}(s, w) = \phi^T(s)w$，我们有：

$$\nabla_w \hat{v}(s, w) = \phi(s)$$

将该梯度代入 TD 算法：

$$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \hat{v}(s_{t+1}, w_t) - \hat{v}(s_t, w_t)\right] \nabla_w \hat{v}(s_t, w_t)$$

得到：

$$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \phi^T(s_{t+1})w_t - \phi^T(s_t)w_t\right]\phi(s_t),$$

这就是基于线性函数近似的 TD 学习算法。在本课程中，我们简称为 TD-Linear。

线性函数近似的优缺点：

• 缺点：
  • 难以选择合适的特征向量。
• 优点：
  • 线性情况下 TD 算法的理论性质比非线性情况更容易理解。
  • 线性函数近似仍然很强大，因为表格表示仅仅是线性函数近似的一个特例。

表格是线性近似的特例

接下来我们证明，表格表示是线性函数近似的一个特例。

首先，考虑状态 $s$ 的特殊特征向量：

$$\phi(s) = e_s \in \mathbb{R}^{|\mathcal{S}|},$$

其中 $e_s$ 是一个向量，其第 $s$ 个元素为 1，其余元素为 0。

在这种情况下，

$$\hat{v}(s, w) = e_s^T w = w(s),$$

其中 $w(s)$ 是 $w$ 的第 $s$ 个元素。

回顾 TD-Linear 算法：

$$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \phi^T(s_{t+1})w_t - \phi^T(s_t)w_t\right]\phi(s_t),$$

• 当 $\phi(s_t) = e_s$ 时，上述算法变为：

$$w_{t+1} = w_t + \alpha_t \left(r_{t+1} + \gamma w_t(s_{t+1}) - w_t(s_t)\right) e_{s_t}.$$

这是一个向量方程，它仅仅更新了 $w_t$ 的第 $s_t$ 个元素。

• 在方程两边同时乘以 $e_{s_t}^T$，得到：

$$w_{t+1}(s_t) = w_t(s_t) + \alpha_t \left(r_{t+1} + \gamma w_t(s_{t+1}) - w_t(s_t)\right),$$

这正是表格 TD 算法。

例子

考虑一个 5 $\times$ 5 的网格世界示例：

• 给定一个策略：对于任意 $s, a$，有 $\pi(a|s) = 0.2$。
• 我们的目标是估计该策略的状态值（策略评估问题）。
• 总共有 25 个状态值。接下来我们将展示，可以用少于 25 个参数来近似这些状态值。
• 设定 $r_{\text{forbidden}} = r_{\text{boundary}} = -1$，$r_{\text{target}} = 1$，折扣因子 $\gamma = 0.9$。

Ground Truth 与 state value 的 3D 可视化

经验样本：

• 按照给定策略生成了 500 个回合（episodes）。
• 每个回合包含 500 步，并从按照均匀分布随机选取的状态-动作对开始。

作为对比，下面给出表格 TD 算法（简称为 TD-Table）的结果：

TD-Table 的结果

接下来展示 TD-Linear 算法的结果。

特征向量选择：此处我们先选择用平面表示，

$$\phi(s) = \begin{bmatrix} 1 \\ x \\ y \end{bmatrix} \in \mathbb{R}^3$$

在这种情况下，近似状态值为：

$$\hat{v}(s, w) = \phi^T(s)w = [1, x, y] \begin{bmatrix} w_1 \\ w_2 \\ w_3 \end{bmatrix} = w_1 + w_2 x + w_3 y$$

值得注意的是，$\phi(s)$ 也可以定义为 $\phi(s) = [x, y, 1]^T$，元素的顺序并不重要。

TD-Linear 的结果

• 我们正试图用一个平面去近似一个非平面的曲面！
• 趋势是正确的，但由于近似能力有限，存在误差！

为了增强近似能力，我们可以使用高阶特征向量，从而引入更多参数。

例如，我们可以考虑：

$$\phi(s) = [1, x, y, x^2, y^2, xy]^T \in \mathbb{R}^6$$

在这种情况下，

$$\hat{v}(s, w) = \phi^T(s)w = w_1 + w_2 x + w_3 y + w_4 x^2 + w_5 y^2 + w_6 xy$$

这对应于一个二次曲面。

我们还可以进一步增加特征向量的维度：

$$\phi(s) = [1, x, y, x^2, y^2, xy, x^3, y^3, x^2y, xy^2]^T \in \mathbb{R}^{10}$$

使用高阶特征向量的 TD-Linear 算法结果

回顾

到目前为止，我们已经讲完了基于值函数近似的 TD 学习的故事。

1. 这个故事从目标函数开始：

$$J(w) = \mathbb{E}\left[(v_\pi(S) - \hat{v}(S, w))^2\right]$$

该目标函数表明，这是一个策略评估问题。

2. 梯度下降算法为：

$$w_{t+1} = w_t + \alpha_t (v_\pi(s_t) - \hat{v}(s_t, w_t)) \nabla_w \hat{v}(s_t, w_t),$$

3. 算法中未知的真实值函数被一个近似值替代，从而得到算法：

$$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \hat{v}(s_{t+1}, w_t) - \hat{v}(s_t, w_t)\right] \nabla_w \hat{v}(s_t, w_t).$$

虽然这个故事有助于理解基本思想，但它在数学上并不严谨。

算法

$$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \hat{v}(s_{t+1}, w_t) - \hat{v}(s_t, w_t)\right] \nabla_w \hat{v}(s_t, w_t)$$

并不最小化以下目标函数：

$$J(w) = \mathbb{E}\left[(v_\pi(S) - \hat{v}(S, w))^2\right]$$

不同的目标函数

• 目标函数 1：真实值误差（True value error）

$$J_E(w) = \mathbb{E}\left[(v_\pi(S) - \hat{v}(S, w))^2\right] = \|\hat{v}(w) - v_\pi\|_D^2$$

• 目标函数 2：贝尔曼误差（Bellman error）

$$J_{BE}(w) = \|\hat{v}(w) - (r_\pi + \gamma P_\pi \hat{v}(w))\|_D^2 \doteq \|\hat{v}(w) - T_\pi(\hat{v}(w))\|_D^2,$$

其中 $T_\pi(x) \doteq r_\pi + \gamma P_\pi x$

• 目标函数 3：投影贝尔曼误差（Projected Bellman error）

$$J_{PBE}(w) = \|\hat{v}(w) - MT_\pi(\hat{v}(w))\|_D^2,$$

其中 $M$ 是一个投影矩阵。

TD-Linear 算法最小化的实际上是投影贝尔曼误差！

---

值函数近似的 Sarsa

Lec 39

到目前为止，我们仅考虑了状态值估计的问题。即我们希望

$$\hat{v} \approx v_\pi$$

为了寻找最优策略，我们需要估计 action value。

基于值函数近似的 Sarsa 算法为：

$$\color{red}{w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \hat{q}(s_{t+1}, a_{t+1}, w_t) - \hat{q}(s_t, a_t, w_t)\right] \nabla_w \hat{q}(s_t, a_t, w_t).}$$

这与我们本讲前面介绍的算法相同，只是将 $\hat{v}$ 替换为了 $\hat{q}$.

伪代码：基于函数近似的 Sarsa

为了寻找最优策略，我们可以结合 policy evaluation 和 policy improvement 来完成。

目标： 寻找一个策略，使得 agent 从初始状态-动作对 $(s_0, a_0)$ 出发能够到达目标。

• 对于每个回合，执行：
  • 如果当前 $s_t$ 不是目标状态，则执行：
    • 按照 $\pi_t(s_t)$ 执行动作 $a_t$，产生 $r_{t+1}, s_{t+1}$，然后按照 $\pi_t(s_{t+1})$ 执行动作 $a_{t+1}$
    • 值更新（参数更新）：

      $$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \hat{q}(s_{t+1}, a_{t+1}, w_t) - \hat{q}(s_t, a_t, w_t)\right] \nabla_w \hat{q}(s_t, a_t, w_t)$$

    • 策略更新：
      • $\pi_{t+1}(a|s_t) = 1 - \frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)| - 1), \quad \text{if } \ a = \argmax_{a \in \mathcal{A}(s_t)} \hat{q}(s_t, a, w_{t+1})$
      • $\pi_{t+1}(a|s_t) = \frac{\varepsilon}{|\mathcal{A}(s)|} \quad \text{otherwise}$

注：不像 tabular 情形下直接取最大即可，这里的 policy improvement 步需要算一下具体的 $a$。

采用线性函数逼近的 Sarsa

• $\gamma = 0.9, \epsilon = 0.1, r_{\text{boundary}} = r_{\text{forbidden}} = -10, r_{\text{target}} = 1, \alpha = 0.001$。

值函数近似的 Q-learning

Lec 39

与 Sarsa 类似，表格型 Q-Learning 也可以扩展到值函数近似的情况。

Q 值更新规则为：

$$\color{red}{w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \max_{a \in \mathcal{A}(s_{t+1})} \hat{q}(s_{t+1}, a, w_t) - \hat{q}(s_t, a_t, w_t)\right] \nabla_w \hat{q}(s_t, a_t, w_t)},$$

这与 Sarsa 相同，只是将 $\hat{q}(s_{t+1}, a_{t+1}, w_t)$ 替换为了 $\max_{a \in \mathcal{A}(s_{t+1})} \hat{q}(s_{t+1}, a, w_t)$。

伪代码：基于函数近似的 Q-Learning（同策略版本）

DQN 处会给出 Off-policy 版本。

初始化： 初始参数向量 $w_0$，初始策略 $\pi_0$，较小的 $\varepsilon > 0$.

目标： 寻找一个好的策略，使得 agent 从初始状态-动作对 $(s_0, a_0)$ 出发能够到达目标。

• 对于每个回合，执行：
  • 如果当前 $s_t$ 不是目标状态，则执行：
    • 按照 $\pi_t(s_t)$ 执行动作 $a_t$，并产生 $r_{t+1}, s_{t+1}$
    • 值更新（参数更新）：

      $$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \max_{a \in \mathcal{A}(s_{t+1})} \hat{q}(s_{t+1}, a, w_t) - \hat{q}(s_t, a_t, w_t)\right] \nabla_w \hat{q}(s_t, a_t, w_t)$$

    • 策略更新：
      • $\pi_{t+1}(a|s_t) = 1 - \frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)| - 1), \quad \text{if } \ a = \argmax_{a \in \mathcal{A}(s_t)} \hat{q}(s_t, a, w_{t+1})$
      • $\pi_{t+1}(a|s_t) = \frac{\varepsilon}{|\mathcal{A}(s)|} \quad \text{otherwise}$

采用线性函数逼近的 Q-Learning

• $\gamma = 0.9, \epsilon = 0.1, r_{\text{boundary}} = r_{\text{forbidden}} = -10, r_{\text{target}} = 1, \alpha = 0.001$。

---

DQN

Lec 40 & 41 & 42

• 它是将深度神经网络引入强化学习的最早且最成功的算法之一。
• 神经网络的作用是作为一个非线性函数近似器。
• 它与下面的算法不同：

$$w_{t+1} = w_t + \alpha_t \left[r_{t+1} + \gamma \max_{a \in \mathcal{A}(s_{t+1})} \hat{q}(s_{t+1}, a, w_t) - \hat{q}(s_t, a_t, w_t)\right] \nabla_w \hat{q}(s_t, a_t, w_t)$$

原因在于：训练网络的方式不同。

DQN 的目标函数

深度 Q 学习旨在最小化以下目标函数/损失函数：

$$J(w) = \mathbb{E}\left[\left(R + \gamma \max_{a \in \mathcal{A}(S^\prime)} \hat{q}(S^\prime, a, w) - \hat{q}(S, A, w)\right)^2\right],$$

其中 $(S, A, R, S^\prime)$ 是随机变量。

• 这实际上是 贝尔曼最优误差（Bellman optimality error）。因为：

$$q(s, a) = \mathbb{E}\left[R_{t+1} + \gamma \max_{a \in \mathcal{A}(S_{t+1})} q(S_{t+1}, a) \middle| S_t = s, A_t = a\right], \quad \forall s, a$$

因此，$R + \gamma \max_{a \in \mathcal{A}(S^\prime)} \hat{q}(S^\prime, a, w) - \hat{q}(S, A, w)$ 的值在期望意义下应该为零。

如何最小化目标函数？梯度下降！

• 如何计算目标函数的梯度？这很棘手！
• 这是因为，在该目标函数

$$J(w) = \mathbb{E}\left[\left(R + \gamma \max_{a \in \mathcal{A}(S^\prime)} \hat{q}(S^\prime, a, w) - \hat{q}(S, A, w)\right)^2\right],$$

参数 $w$ 不仅出现在 $\hat{q}(S, A, w)$ 中，还出现于

$$y \doteq R + \gamma \max_{a \in \mathcal{A}(S^\prime)} \hat{q}(S^\prime, a, w)$$

• 为了简化，我们可以假设在计算梯度时，$y$ 中的 $w$ 是固定的（至少在一段时间内固定）。

主网络与目标网络

为此，我们可以引入两个网络：

• 一个是主网络（main network），表示 $\hat{q}(s, a, w)$；
• 另一个是目标网络（target network） $\hat{q}(s, a, w_T)$。
• main network 的参数一直在更新，而 target network 的参数每隔一段时间更新一次。

在这种情况下，目标函数退化为：

$$J = \mathbb{E}\left[\left(R + \gamma \max_{a \in \mathcal{A}(S^\prime)} \hat{q}(S^\prime, a, w_T) - \hat{q}(S, A, w)\right)^2\right],$$

其中 $w_T$ 是目标网络的参数。

梯度计算

当 $w_T$ 固定时，$J$ 的梯度可以很容易地得到：

$$\nabla_w J = -2\mathbb{E}\left[\left(R + \gamma \max_{a \in \mathcal{A}(S^\prime)} \hat{q}(S^\prime, a, w_T) - \hat{q}(S, A, w)\right) \nabla_w \hat{q}(S, A, w)\right].$$

• DQN 的基本思想是使用梯度下降算法来最小化目标函数。
• 然而，这样的优化过程涉及一些重要的技术，值得特别关注。

DQN 的实现用到了两个关键技术：

• 第一个关键技术
  • 双网络：一个主网络（main network）和一个目标网络（target network）。
• 为什么使用它？
  • 数学原因在我们计算梯度时已经解释过了。

实现细节

• 令 $w$ 和 $w_T$ 分别表示主网络和目标网络的参数。它们最初被设置为相同参数。
• 在每次迭代中，我们从经验回放池（replay buffer）（稍后解释）中抽取一个小批量（mini-batch）样本 $\{(s, a, r, s^\prime)\}$。
• 网络的输入包括状态 $s$ 和动作 $a$。
  • 目标输出为 $y_T \doteq r + \gamma \max_{a \in \mathcal{A}(s^\prime)} \hat{q}(s^\prime, a, w_T)$。
  • 然后，我们直接在小批量 $\{(s, a, y_T)\}$ 上最小化 TD 误差（也称为损失函数）$(y_T - \hat{q}(s, a, w))^2$。

经验回放

实现 DQN 的另一个关键技术是 经验回放（Experience replay）

• 问题：什么是经验回放？
• 回答：
  • 在收集了一些经验样本后，我们不按它们被收集的顺序使用这些样本。
  • 相反，我们将它们存储在一个集合中，称为经验回放池（replay buffer） $\mathcal{B} \doteq \{(s, a, r, s^\prime)\}$。
  • 每次训练神经网络时，我们可以从经验回放池中随机抽取一个小批量样本。
  • 抽取样本（称为经验回放）应该遵循均匀分布（为什么？）。

经验回放的必要性：

• 问题： 为什么经验回放在深度 Q 学习中是必要的？为什么回放必须遵循均匀分布？
• 答案在于目标函数!

考察目标函数：

$$J = \mathbb{E}\left[\left(R + \gamma \max_{a \in \mathcal{A}(S^\prime)} \hat{q}(S^\prime, a, w) - \hat{q}(S, A, w)\right)^2\right]$$

• $(S, A) \sim d$：$(S, A)$ 是一个索引，被视为单个随机变量。
• $R \sim p(R|S, A), S^\prime \sim p(S^\prime|S, A)$：$R$ 和 $S^\prime$ 由系统模型决定。
• 状态-动作对 $(S, A)$ 的分布被假定为均匀的。
  • 然而，样本并非均匀收集的，因为它们是由特定策略连续生成的。
  • 为了打破连续样本之间的相关性，我们可以使用经验回放技术，从经验回放池中均匀抽取样本。

这就是经验回放必要以及经验回放必须均匀的数学原因！

重新审视表格型情况

• 问题： 为什么表格型 Q-Learning 不需要经验回放？
  • 因为之前没有涉及到 $(s,a)$ 分布的要求。
• 问题： 为什么 DQN 涉及分布？
  • 深度网络情况下的目标函数是所有 $(S, A)$ 上的标量平均。表格型情况不涉及 $S$ 或 $A$ 的任何分布。表格型情况的算法旨在为所有 $(s, a)$ 求解一组方程（贝尔曼最优方程）。
  • 一个是在优化目标函数，一个是在求解方程。
• 问题： 我们可以在表格型 Q-Learning 中使用经验回放吗？
  • 可以。而且这样更具样本效率（为什么？）。
    • 因为 tabular 形式的 Q-learning 也是 off-policy 的，所以可以复用技巧。
    • 此外，经验回放可以提升样本利用效率——同一个 sample 可以用多次。
      • 例如：之前 tabular Q-learning 中，为了达到较好的效果，我们一个 episode 需要运行 10w 步，实际上根本不需要这么多步！只需要保证每个 state-action pair 被访问一次就行了，以前是按照时序来采的，使用完数据即丢弃的做法其实很浪费。

伪代码：Deep Q-learning（异策略版本）

目标： 学习一个最优目标网络，以根据由行为策略 $\pi_b$ 生成的经验样本近似最优动作值。

• 将由 $\pi_b$ 生成的经验样本存储在经验回放池 $\mathcal{B} = \{(s, a, r, s^\prime)\}$ 中。
  • 对于每次迭代，执行：
    • 从 $\mathcal{B}$ 中均匀抽取一个小批量样本
    • 对于每个样本 $(s, a, r, s^\prime)$，计算目标值：
      • $y_T = r + \gamma \max_{a \in \mathcal{A}(s^\prime)} \hat{q}(s^\prime, a, w_T)$
      • 其中 $w_T$ 是目标网络的参数
    • 使用小批量 $\{(s, a, y_T)\}$ 更新主网络以最小化 $(y_T - \hat{q}(s, a, w))^2$
  • 每 $C$ 次迭代设置 $w_T = w$

备注：

• 为什么没有策略更新？
  • 因为我们是 off-policy 的，因此不需要每步的策略更新——只需要在最后一次迭代之后一步算出 optimal policy。
  • 如果是 on-policy 的，那么每步迭代必须有 policy improvement。
• 为什么不使用我们推导出的策略更新方程？
  • 这是为了适配当前神经网络的特性，用于高效训练。
• 网络的输入和输出与 DQN 论文中的不同。
  • DQN 原文中是 on-policy 的，这里是 off-policy 的，但二者本质相同。

示例说明

• 本示例旨在学习每个状态-动作对的最优动作值。
• 一旦获得最优动作值，就可以立即得到最优贪婪策略。

实验设置：

• 使用 单个回合（episode） 来训练网络。
• 该回合由图 (a) 所示的探索性**行为策略（behavior policy）**生成。
• 该回合仅有 1,000 步！而表格型 Q-Learning 需要 100,000 步。
• 使用一个具有单个隐藏层的浅层神经网络作为 $\hat{q}(s, a, w)$ 的非线性近似器。隐藏层有 100 个神经元。
  • 输入层-隐藏层-输出层

使用 1000 步的单回合

可以看到：

• TD error 收敛到零
• state value 误差无法收敛到零

这说明 DQN 使用很少的数据量就能达到 tabular Q-learning 的效果。

这有两个原因：

1. value function approximation 本身就具有比较强的泛化能力
2. experience replay 可以让经验被反复用到，效率会比较高

只使用 100 步的单回合

• TD error 收敛到零
• state value 误差没有收敛到零

再强大的算法也需要好的数据来支撑！巧妇难为无米之炊！