C7 值函数方法

值表示：从表格到函数

在前面各章中，状态值和动作值都是用表格（tabular）来表示的。表格方法直观易懂，但在处理大规模状态空间或动作空间时效率低下。本章引入值函数方法（value function method），使用函数来近似表示状态值或动作值，这已成为表示价值的标准方法，也是将人工神经网络引入强化学习作为函数近似器的切入点。

基本思想

假设有 $n$ 个状态 $\{s_i\}_{i=1}^n$，其真实状态值为 $\{v_\pi(s_i)\}_{i=1}^n$。

若采用表格方法，估计值 $\{\hat{v}(s_i)\}_{i=1}^n$ 存储在一个表中，可以直接读取或修改：

如果采用函数近似，则用函数 $\hat{v}(s,w)$ 来近似 $v_\pi(s)$，其中 $w$ 是参数向量，$\hat{v}(s,w)$ 有时被简写为 $\hat{v}_w(s)$。最简单的例子是线性函数：

$$\hat {v} (s, w) = a s + b = \underbrace {[ s , 1 ]} _ {\phi^ {T} (s)} \underbrace {\left[ \begin{array}{c} a \\ b \end{array} \right]} _ {w} = \phi^ {T} (s) w.$$

其中 $\phi(s)\in\mathbb{R}^2$ 称为状态 $s$ 的特征向量（feature vector）。

注意这里的特征向量（feature vector）并不是线性代数中 $A\mathbf{x}=\lambda\mathbf{x}$ 的特征向量（eigenvector），前者是输入数据的数值化表示，用于描述状态 $s$ 的属性；后者是矩阵运算的固有属性。

在线性函数近似的应用中，需要选取合适的 feature vector，这往往需要拥有对目标任务的先验知识。但是先验知识在实际应用中通常是未知的，在这种情况下比较流行的解决方法是用神经网络去代替线性函数近似。

更一般的，我们可以使用更高阶的多项式：

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

注意：$\hat{v}(s,w)$ 在 $w$ 上是线性的（尽管在 $s$ 上可能是非线性的），这类方法称为线性函数近似（linear function approximation）。

表格方法与函数方法的对比

值的读取（Retrieve）

表格方法	函数近似方法
直接读取表中对应条目	将状态 $s$ 输入函数，计算函数值（如上图所示）
时间复杂度 $O(1)$	需要前向传播（神经网络）或计算 $\phi^T(s)w$

值的更新（Update）

表格方法	函数近似方法
直接重写表中对应条目	必须更新参数 $w$ 来间接改变值
只更新被访问状态的值	更新 $w$ 会影响所有状态的值

对于值函数近似方法，一个状态的经验样本可以泛化到帮助估计其他状态的值，因此其具有更强的泛化能力。

存储效率

• 表格方法：需要存储 $n$ 个值
• 函数近似方法：只需存储低维参数向量 $w$

值函数近似方法通过低维向量去表示高维数据，必然会丢失一些信息，导致其会牺牲一定的精度——这是称为"近似"的原因。上图是通过二维的特征向量去拟合 $n$ 维数据的例子。

最小二乘问题

如果已知 $\{v_\pi(s_i)\}_{i=1}^n$，则寻找最优的参数向量 $w$ 转变成了一个最小二乘问题。可以通过最小化目标函数来求解最优参数：

$$\begin{align} J _ {1} = \sum_ {i = 1} ^ {n} \left(\hat {v} \left(s _ {i}, w\right) - v _ {\pi} \left(s _ {i}\right)\right) ^ {2} = \sum_ {i = 1} ^ {n} \left(\phi^ {T} \left(s _ {i}\right) w - v _ {\pi} \left(s _ {i}\right)\right) ^ {2} \\ = \left\| \left[ \begin{array}{c} \phi^ {T} \left(s _ {1}\right) \\ \vdots \\ \phi^ {T} \left(s _ {n}\right) \end{array} \right] w - \left[ \begin{array}{c} v _ {\pi} \left(s _ {1}\right) \\ \vdots \\ v _ {\pi} \left(s _ {n}\right) \end{array} \right] \right\| ^ {2} \doteq \| \Phi w - v _ {\pi} \| ^ {2}, \\ \end{align}$$

其中 $\Phi \doteq \left[ \begin{array}{c} \phi^ {T} \left(s _ {1}\right) \\ \vdots \\ \phi^ {T} \left(s _ {n}\right) \end{array} \right] \in \mathbb {R} ^ {n \times m}$ 是特征矩阵，$v _ {\pi} \doteq \left[ \begin{array}{c} v _ {\pi} \left(s _ {1}\right) \\ \vdots \\ v _ {\pi} \left(s _ {n}\right) \end{array} \right] \in \mathbb {R} ^ {n}$ 是目标值。

最小二乘问题的最优解，也就是最优的参数为：

$$w^*=(\Phi^T\Phi)^{-1}\Phi v_\pi$$

基于函数近似的状态价值 TD 学习

本节展示如何将函数近似方法融入 TD 学习，以估计给定策略的状态值。

目标函数

设 $v_\pi(s)$ 和 $\hat{v}(s,w)$ 分别为状态 $s$ 的真实值和近似值。目标是找到最优的 $w$，使得 $\hat{v}(s,w)$ 能够最好地近似 $v_\pi(s)$。

目标函数为：

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

为了分析期望值，需要知道随机变量 $S$ 的概率分布。通常有两种定义方式：

方式一：均匀分布

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

将所有状态视为同等重要。但这种方式没有考虑策略下的实际动态——某些状态可能很少被访问。

方式二：平稳分布（Stationary Distribution）

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

其中 $d_\pi(s)$ 是策略 $\pi$ 下马尔可夫过程的平稳分布，表示长时间后智能体处于状态 $s$ 的概率。

平稳分布 $d_\pi$ 满足 $d_\pi^T=d_\pi^TP_\pi$，其中 $P_\pi$ 是策略 $\pi$ 下的状态转移矩阵。

直观理解：无论从哪个状态开始，经过足够长的时间后，智能体处于各状态的概率分布收敛到 $d_\pi$。

优化算法

内容

使用梯度下降最小化 $J(w)$：

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

计算梯度：

$$\begin{align} \nabla_ {w} J \left(w _ {k}\right) &= \nabla_ {w} \mathbb {E} \left[ \left(v _ {\pi} (S) - \hat {v} \left(S, w _ {k}\right)\right) ^ {2} \right] \\ &= \mathbb {E} \left[ \nabla_ {w} \left(v _ {\pi} (S) - \hat {v} \left(S, w _ {k}\right)\right) ^ {2} \right] \\ &= 2 \mathbb {E} \left[ \left(v _ {\pi} (S) - \hat {v} \left(S, w _ {k}\right)\right) \left(- \nabla_ {w} \hat {v} \left(S, w _ {k}\right)\right) \right] \\ &= - 2 \mathbb {E} \left[ \left(v _ {\pi} (S) - \hat {v} \left(S, w _ {k}\right)\right) \nabla_ {w} \hat {v} \left(S, w _ {k}\right) \right]. \\ \end{align}$$

因此梯度下降的迭代公式为：

$$w_{k+1}=w_k+2\alpha_k\mathbb{E}[(v_\pi(S)-\hat{v}(S,w_k))\nabla_w\hat{v}(S,w_k)]$$

不失一般性，可以将 $\alpha_k$ 前的系数 $2$ 视为 $\alpha_k$ 的一部分，即 $w_{k+1}=w_k+\alpha_k\mathbb{E}[(v_\pi(S)-\hat{v}(S,w_k))\nabla_w\hat{v}(S,w_k)]$。

使用随机梯度下降（SGD），用单个样本 $s_t$ 估计期望：

$$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)$$

但 $v_\pi(s_t)$ 是未知的，需要近似。有两种方法：

MC 方法：用回报 $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)$$

TD 方法：用 $r_{t+1}+\gamma\hat{v}(s_{t+1},w_t)$ 近似 $v_\pi(s_t)$

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

伪代码

使用值函数近似的 TD 方法的伪代码如下：

函数近似器的选择

为了能够应用值函数近似的 TD 方法，需要选择合适的函数近似器 $\hat{v}(s,w)$。通常有两种选择，第一种是用神经网络作为一个非线性函数近似器，第二种是用线性函数近似器 $\hat{v}(s,w)=\phi^T(s)w$。

线性函数近似

线性函数近似的表达式为

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

梯度为 $\nabla_w\hat{v}(s,w)=\phi(s)$，代入 TD 更新公式可以得到：

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

这称为 TD-Linear 算法（上面伪代码中的 linear case）。

事实上，表格 TD 是 TD-Linear 的特例：

选择特征向量 $\phi(s)=e_s\in\mathbb{R}^n$，其中 $e_s$ 是仅在状态 $s$ 对应位置为 1、其余为 0 的向量。则 $\hat{v}(s,w)=e_s^Tw=w(s)$，代入 TD-Linear 更新公式：

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

这正是上一章节的表格 TD 算法。

特征向量的选择

• 多项式特征：

  • 一阶：$\phi(s)=[1,x,y]^T\in\mathbb{R}^3$；
  • 二阶：$\phi(s)=[1,x,y,x^2,y^2,xy]^T\in\mathbb{R}^6$
  • 三阶：$\phi(s)=[1,x,y,x^2,y^2,xy,x^3,y^3,x^2y,xy^2]^T\in\mathbb{R}^{10}$

• 傅里叶特征：

  $$\phi(s)=\begin{bmatrix}\vdots\\ \cos(\pi(c_1x+c_2y))\\ \vdots\end{bmatrix}\in\mathbb{R}^{(q+1)^2}$$

  其中 $c_1,c_2\in\{0,1,\ldots,q\}$，因此共有 $(q+1)^2$ 种组合，维数为 $(q+1)^2$。

  例如当 $q=1$ 时，特征向量 $\phi(s)$ 为

  $$\phi (s) = \left[ \begin{array}{c} \cos \left(\pi (0 x + 0 y)\right) \\ \cos \left(\pi (0 x + 1 y)\right) \\ \cos \left(\pi (1 x + 0 y)\right) \\ \cos \left(\pi (1 x + 1 y)\right) \end{array} \right] = \left[ \begin{array}{c} 1 \\ \cos (\pi y) \\ \cos (\pi x) \\ \cos (\pi (x + y)) \end{array} \right] \in \mathbb {R} ^ {4}.$$

• 瓦片编码（tile coding）

特征向量维度越高，近似能力越强，但存储和计算开销也越大。

示例

上图 (a) 是给定的当前策略，(b) 是该策略下的 state values（ground truth），© 是将 state values 通过 3D 面去具象表示。

下面通过使用不同的函数近似器，来估计当前策略下的 state values。样本为 500 条 episodes，每个 episode 步长为 500，并随机选取状态-动作对作为起点。在每个例子中 $w$ 的初始值服从 0-1 正态分布。

多项式特征

首先，尝试多项式特征向量。在当前的 grid world 情境中，一个状态 $s$ 对应一个 2D 坐标 $(x,y)$，为了避免数值问题（如梯度爆炸、特征失衡等），$x,y$ 都被归一化到 $[-1,+1]$ 之间。

最简单的特征向量是

$$\phi (s) = \left[ \begin{array}{c} x \\ y \end{array} \right] \in \mathbb {R} ^ {2}.$$

从而有

$$\hat {v} (s, w) = \phi^ {T} (s) w = [ x, y ] \left[ \begin{array}{c} w _ {1} \\ w _ {2} \end{array} \right] = w _ {1} x + w _ {2} y.$$

其中 $w_1x+w_2y$ 表示一个过原点的 2D 平面。由于 state values 的表面未必经过原点，因此需要为 $\hat{v}(s,w)$ 所表示的 2D 平面加上一个偏置，从而更好地近似 state values。因此考虑一个三维的特征向量

$$\phi (s) = \left[ \begin{array}{c} 1 \\ x \\ y \end{array} \right] \in \mathbb {R} ^ {3}$$

从而有

$$\hat {v} (s, w) = \phi^ {T} (s) w = [ 1, x, y ] \left[ \begin{array}{l} w _ {1} \\ w _ {2} \\ w _ {3} \end{array} \right] = w _ {1} + w _ {2} x + w _ {3} y$$

通过该函数近似器拟合得到的平面为下图中的 (a)。根据 state values 的误差曲线可以看到即使估计的误差逐渐收敛，但是由于 2D 平面近似能力的局限性，误差无法降到 0。

为了增强近似能力，可以提高多项式特征的维数。下面分别使用

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

和

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

作为特征向量。拟合的结果分别为下图中 (b) 和 ©。

傅里叶特征

下面用傅里叶特征作为线性函数近似的特征向量。$x,y$ 被归一化到 $[0,1]$ 之间。产生的特征向量为

$$\phi(s)=\begin{bmatrix}\vdots\\ \cos(\pi(c_1x+c_2y))\\ \vdots\end{bmatrix}\in\mathbb{R}^{(q+1)^2}$$

其中 $c_1,c_2\in\{0,1,\ldots,q\}$。

下图分别展示了 $q=1,2,3$ 时的近似结果。同样可以发现特征向量维数越高，近似效果越好。

理论分析

待补充

基于函数近似的动作价值 TD 学习

上一届展示了 state values 估计，下面扩展到 action values 估计。

使用值函数近似的 Sarsa

迭代公式

用 $\hat{q}(s,a,w)$ 近似 $q_\pi(s,a)$，将状态值 TD 更新中的 $\hat{v}$ 替换为 $\hat{q}$：

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

线性情况下：$\hat{q}(s,a,w)=\phi^T(s,a)w$，$\nabla_w\hat{q}(s,a,w)=\phi(s,a)$。

伪代码

当值函数近似的 Sarsa 与 policy improvement 结合时，能够找到最优策略。

下面的算法是找到从特定起点到特定终点的最优路径。

例子

上面的例子是使用值函数近似的 Sarsa 找到从特定起点到特定终点的最优路径，采用的线性函数近似器是 5 阶的傅里叶函数。

使用值函数近似的 Q-learning

迭代公式

将表格 Q-learning 扩展到函数近似：

$$w_{t+1}=w_t+\alpha_t[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)]\nabla_w\hat{q}(s_t,a_t,w_t)$$

与 Sarsa 的关键区别：用 $\max_{a}\hat{q}(s_{t+1},a,w_t)$ 代替 Sarsa 中的 $\hat{q}(s_{t+1},a_{t+1},w_t)$。

与表格 Q-learning 一样，使用值函数近似的 Q-learning 既可以使用 on-policy 也可以使用 off-policy 方式实现。

伪代码

下面的 Q-learning 算法使用 on-policy 实现，目的是找到从特定起点到特定终点的最优路径。

例子

上面的例子是使用 on-policy 的值函数近似的 Q-learning 找到从特定起点到特定终点的最优路径，采用的线性函数近似器是 5 阶的傅里叶函数。

到目前为止，尽管价值是用函数表示的，但是策略 $\pi(a\mid s)$ 仍然通过表格表示。因此目前的假设仍然是有限的状态和有限的动作。

Deep Q-learning（DQN）

将深度神经网络与 Q-learning 结合，得到 deep Q-learning 或 deep Q-network（DQN）。这是最早且最成功的深度强化学习算法之一。

算法描述

DQN 的目标是最小化目标函数

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

其中 $(S,A,R,S')$ 是随机变量，分别表示状态、动作、即时奖励和下一个状态。

上述的目标函数可以看作是平方贝尔曼最优性误差，因为

$$q ( s, a )=\mathbb{E}\left[ R_{t+1}+\gamma \max_{a\in \mathcal{A} \left( S_{t+1} \right)} q \left( S_{t+1}, a \right) \Big| S_{t}=s, A_{t}=a \right],\text{ for all s,a}$$

是 BOE，证明见上一章 Q-learning 部分。因此若 $\hat{q}(S,A,w)$ 能够精确近似 optimal state values，目标函数应该为 0。

为了最小化目标函数，可以使用梯度下降法，这需要计算 $J$ 关于 $w$ 的梯度。$J$ 中 $w$ 出现在两处，分别是 $R+\gamma\max_{a\in\mathcal{A}(S')}\hat{q}(S',a,w)$ 和 $\hat{q}(S,A,w)$，而前者很难计算出 $w$ 梯度。因此，为了简便性，前者的 $w$ 值在短期内视为定值 $w_T$，由此得到新的目标函数

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

其中 $\hat{q}(S,A,w)$ 称为 main network（主网络），而 $\hat {q} \left(S ^ {\prime}, a, w _ {T}\right)$ 称为 target network（目标网络），$w_T$ 为 target network 的参数。

此时 $J$ 对 $w$ 的梯度为

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

不失一般性，这里忽略了求导得到的系数大小。

算法步骤

下面具体展示如何利用修改后的 $J$ 对 $w$ 的梯度公式来最小化目标函数。

两个网络

这里涉及两个网络，分别是 main network 和 target network，参数分别是 $w$ 和 $w_T$，两者初始值一样。

每一轮迭代中，从 replay buffer（后面会提到）中抽取 mini-batch 样本 $\{(s,a,r,s')\}$。main network 的输入是 $s,a$，输出是估计的 q 值 $y=\hat{q}(s,a,w)$，目标是 $y_T=r+\gamma \max _ {a \in \mathcal {A} \left(s ^ {\prime}\right)}\hat{q}(s',a,w_T)$；随后通过反向传播更新 main network 的参数 $w$ 来最小化 TD-error $\sum(y-y_T)^2$。

main network 每一轮迭代都更新参数 $w$，target network 每过固定的轮数才会将参数 $w_T$ 同步为 $w$。

这样做是为了让 TD-target 在一段时间内保持稳定，避免"追逐移动目标"的问题。

经验回放

经验回放（Experience Replay） 的核心思想是：采样得到样本后，不立即按采集顺序更新参数，而是将其存储起来供后续复用。具体而言，每采集到一个四元组样本 $(s,a,r,s')$，就将其存入回放缓冲区 $\mathcal{B}\doteq\{(s,a,r,s')\}$。在 DQN 中，每次更新主网络（main network）时，都从 $\mathcal{B}$ 中均匀随机采样一个小批量（mini-batch）样本用于训练，这一过程即称为经验回放。

需要特别注意的是，标准 DQN 要求经验回放的采样服从均匀分布。其理论依据在于：只有假设状态-动作对 $(S,A)$ 服从均匀分布，才能正确定义目标函数中的数学期望。而按时间顺序采集的样本存在强烈的序列相关性，若不通过均匀采样加以打破，梯度更新将带有偏置，无法保证收敛到贝尔曼最优性方程的解。

注：后续改进算法如**优先经验回放（Prioritized Experience Replay）**采用非均匀采样策略，通过 TD 误差大小赋予样本不同优先级，以进一步提升学习效率。这属于对均匀回放的扩展与优化，并不否定标准 DQN 中均匀采样的理论基础。

此外，experience replay 的每个样本可以被多次使用，能够提高数据利用效率。

伪代码

例子

例1

上面的例子是使用 DQN 直接估计所有状态-动作对的 optimal action values。所用的样本只有一个 episode，并且只采样 1000 步，从而 replay buffer 只有 1000 个经验样本。behavior policy 为上图 (a)，访问到的状态-动作对为 (b)。DQN 每轮迭代时从 replay buffer 中均匀抽取的 mini-batch 样本的批大小为 100。图 © 是根据 main network 对 action values 的近似结果转变得到的 greedy policy。

改例中，main network 和 target network 结构一样，都是隐藏层为一层 100 个神经元的神经网络。输入是状态 $s$ 的归一化坐标 $(x,y)$ 和动作 $a$，输出值是相应的近似 action value。

神经网络的输入输出结构也可以改为：输入是状态 $s$ 的归一化坐标 $(x,y)$，输出是所有 action 对应的近似 action values，即输出向量的维数是动作的个数。

由上图 (d) 和 (e) 可以发现，损失函数和 state values 误差都收敛到了 0，说明神经网络近似的效果非常好。本例仅仅使用一个 1000 步的 episode 就能得到如此好的拟合效果，既得益于神经网络极强的近似的泛化能力，由因为经验样本可以被重复使用。

例2

上面的例子使用的样本更少：仅使用一个步长为 100 的 episode。通过上图的结果可以发现，尽管神经网络能够在少量样本下得到很好的训练，损失函数降为 0，但是 state values 的误差并没有收敛到 0。这说明在样本非常少的情况下，神经网络也能够正确地拟合给定的经验样本，但是经验样本本身并不能够充分体现环境本身。

该例子深刻揭示了 DQN 中 “损失函数收敛” 与 “策略最优” 并非充要条件：前者仅代表神经网络对已有经验样本的拟合程度，后者依赖于经验样本对全状态空间的代表性。当样本极少时，过拟合经验样本极易，但泛化至全局最优极难，这凸显了高效探索（Exploration） 在深度强化学习中的关键地位。