第六章：函数近似（function approximation）方法

在有些任务中，状态和动作对的数目非常大，甚至可能是无穷大，这时不可能对所有状态（或状态动作对）逐一进行更新。函数近似方法用参数化的模型来近似整个状态价值函数（或动作价值函数），并在每次学习时更新整个函数。

一、函数近似原理

函数近似（function approximation）方法用带参数 $\bold w$ 的函数来近似价值函数，如用 $v(s;\bold w),\; s \in \mathcal S$ 近似状态价值函数，用 $q(s,a;\bold w),\; s \in \mathcal S,a \in \mathcal A$ 近似动作价值函数。当动作集有限时，还能用矢量函数 $q(s;\bold w)=(q(s,a;\bold w):a \in \mathcal A),\; s \in \mathcal S$ 来近似动作价值，矢量函数 $q(s;\bold w)$ 的每一个元素对应着一个动作，而整个矢量函数除参数外只用状态作为输入。

函数近似方法可以使用随机梯度下降算法或者半梯度下降算法对价值函数进行更新。以动作价值更新为例，随机梯度下降（stochastic gradient-descent, SGD）算法就是在试图减小每一步的回报估计 $G_t$ 和动作价值 $q(S_t,A_t;\bold w)$ 的差别时，定义每一步损失为 $[G_t-q(S_t,A_t,\bold w)]^2$ ，那么对整个回合的损失函数为 $\displaystyle \sum_{t=0}^{T-1}[G_t-q(S_t,A_t;\bold w)]^2$ ，然后再沿着回合损失函数对 $\bold w$ 的梯度反方向更新策略参数 $\bold w$ 。

对于能够支持自动梯度计算的软件包，往往自带根据损失函数更新参数的功能。同样也可以自己计算梯度 $\nabla q(S_t,A_t;\bold w)$ ，然后利用下式更新：

对状态价值函数也可以类似的定义回合损失函数 $\displaystyle \sum_{t=0}^{T}[G_t-v(S_t;\bold w)]^2$ ，其对应的更新式为：

将同策回合更新价值估计与函数近似法相结合，并在更新价值函数时使用随机梯度下降算法，就能得到算法 6-1 ：

将策略改进引入算法 6-1 即可实现最优策略求解算法 6-2 ：

对于半梯度下降（semi-gradient descent）算法，就是在随机梯度下降算法的基础上，改用单步时序差分的回报估计 $U_t$ ，并在对回合损失函数 $\displaystyle \sum_{t=0}^{T-1}[U_t-q(S_t,A_t;\bold w)]^2$ 或 $\displaystyle \sum_{t=0}^{T}[U_t-v(S_t;\bold w)]^2$ 求梯度时，不对回报 $U_t=R_{t+1} + \gamma q(S_{t+1},A_{t+1};\bold w)$ 或 $U_t=R_{t+1} + \gamma v(S_{t+1};\bold w)$ 求梯度。将半梯度下降算法与第五章节的算法相结合可以得到以下两个算法：

需要注意的是，当采用自动计算微分并更新参数的软件包来减小损失时，则务必注意不能对回报的估计求梯度。

资格迹同样可以运用在函数近似算法中，实现回合更新和单步时序差分的折中。这时的资格迹参数 $\bold z$ 和价值参数 $\bold w$ 具有相同形状的大小，并且逐元素一一对应；也就是说资格迹参数表示了在更新价值参数时应当使用的权重乘以价值估计的梯度，那么价值参数的更新式应当如下：

当资格迹为累积迹时，其定义如下：

根据以上结果，即可得到结合资格迹的函数近似算法：

二、线性近似

线性近似是用许多特征向量的线性组合来近似价值函数，特征向量则依赖于输入（即状态或动作状态对），以动作价值近似为例，可以为每个状态动作对定义多个不同的特征 $\bold x(s,a)=(x_j(s,a):j \in \mathcal J)$ ，进而定义近似函数为这些特征的线性组合，即：

对于状态函数也有类似的近似方法：

第三到五章的查表法可看做是线性近似的特例，例如对动作价值而言，可认为有 $|\mathcal S| \times |\mathcal A|$ 个特征向量，每个向量形式为：

即在某个的状态动作对处为 1 ，其他都为 0 。这样所有向量的线性组合就是整个动作价值函数，线性组合系数的值就是动作价值函数的值。

在使用线性近似的情况下，还可以使用线性最小二乘来进行策略评估。线性最小二乘是一种批处理（batch）方法，它每次针对多个经验样本，试图找到在整个样本集上最优的估计。将线性最小二乘用于回合更新，可以得到线性最小二乘回合更新（Linear Least Square Monte Carlo, Linear LSMC），它试图最小化目标：

在线性近似的情况下，其梯度为：

将待求权重 $\bold w_{LSMC}$ 代入上式并令其等于零，则有：

求解该线性方程组可得：

直接使用上式更新权重，就实现了线性最小二乘回合更新。

将线性最小二乘用于时序差分，可以有线性最小二乘时序差分更新（Linear Least Square Temporal Difference, Linear LSTD）。对于单步时序差分，它试图最小化 $\displaystyle L(\bold w) = \sum_t[U_t - q(S_t,A_t;\bold w)]^2$ ，其中 $U_t = R_{t+1} + \gamma q(S_{t+1},A_{t+1};\bold w)$ ；与回合更新类似，但这里是对 $L(\bold w)$ 求半梯度，最后可以求解得到：

最小二乘也能用于最优策略求解。相对于单步时序差分，Q 学习只修改了回报估计为 $\displaystyle U_t = R_{t+1} + \gamma \max_{a\in \mathcal A(S+1)} q(S_{t+1},a;\bold w)$ ，并不影响对单步时序差分的最小化目标 $L(\bold w)$ 求半梯度，所以将 $\eqref{eq:10}$ 中的 $A_{t+1}$ 改为 $\displaystyle A_{t+1}^* = \underset{a}{\arg\max}\; q(S_{t+1},a;\bold w)$ 即可得到解为：

那么有基于 Q 学习的最小二乘最优策略求解算法：

三、函数近似的收敛性

线性近似具有简单的线性叠加结构，这使得线性近似可以获得额外的收敛性；对于函数近似算法，收敛性往往只在采用梯度下降的回合更新时有保证，而在采用半梯度下降的时序差分方法时是没有保证的。各种收敛情况在下列表中给出，其中查表法是指不采用函数近似的方法；所有的收敛性都是在学习率满足 Robbins-Monro 序列下才具有的，且一般都可以通过验证随机近似 Robbins-Monro 算法的条件证明，对于最优策略求解的收敛性证明，则需要用到了其随机优化的版本。

值得一提的是，对于异策 Q 学习，即使采用了线性近似，仍然不能保证收敛。研究人员发现，只要异策、自益、函数近似这三者同时出现，就不能保证收敛性，但有一个著名的反例叫做 Baird 反例（Baird's counterexample）。

四、深度 Q 学习

深度 Q 学习是目前非常热门的函数近似方法，为了解决无法保证收敛性而导致的训练不稳定或训练困难的问题，研究人员主要从以下两个方面进行了改进：

• 经验回放（experience replay）：将经验（即历史的状态、动作、奖励等）存储起来，再按一定规则采样存储的经验。
• 目标网络（target network）：修改网络的更新方式，例如不把刚学习的网络权重马上用于后续的自益过程。

V. Mnih 等在 2013 年发表的《Playing Atari with deep reinforcement learning》提出了基于经验回放的深度 Q 网络，标志着深度 Q 网络的诞生，也标志着深度强化学习的诞生。经验回放就是一种让经验的概率分布变得稳定的技术，它能提高训练的稳定性，其主要步骤为：

1. 存储：将轨迹以 $(S_t,A_t,R_{t+1},S_{t+1})$ 等形式存储起来；
2. 采样回放：使用某种规则从存储的 $(S_t,A_t,R_{t+1},S_{t+1})$ 中随机取出一条或多条经验。

下面给出了带经验回放的 Q 学习最优策略求解算法：

经验回放的好处有以下两点：

• 在训练 Q 网络时，可以消除数据的关联，使得数据更像是独立同分布的（独立同分布是很多有监督学习的证明条件）；这样可以减小参数更新的方差，加快收敛。
• 能够重复使用经验，对于数据获取困难的情况尤其有用。

从存储的角度，经验回放可以分为以下两种：

• 集中式回放：智能体在一个环境中运行，把经验同意存储在经验池中。
• 分布式回放：智能体的多份拷贝（worker）同时在多个环境中运行，并将经验统一存储于经验池中。

从采样的角度，经验回放又能分为以下两种：

• 均匀回放：等概率的从经验集中取经验。
• 优先回放（Prioritized Experience Replay, PER）：为经验池里的每个经验指定一个优先级，在选取时更倾向于选取优先级高的经验。

T. Schaul 等于 2016 年发表文字《Prioritized experience replay》提出了优先回放，其基本思想如上介绍，一般做法是，如果某个经验 $i$ 的优先级为 $p_i$ ，那么选取该经验的概率为 $\displaystyle \frac{p_i}{\sum_k p_k}$ 。

经验值的选取方法也有许多种，最常见的有：

• 成比例优先（Proportional priority）：第 $i$ 个经验优先级为 $p_i = (\delta_i + \varepsilon)^\alpha$ ，其中 $\delta_i$ 是时序差分误差 $\delta_i = U_t - q(S_t,A_t;\bold w)$ 或 $\delta_i = U_t - v(S_t;\bold w)$ ，$\varepsilon$ 是预先选择的一个小正数，$\alpha$ 是正参数。
• 基于排序优先（rank-based priority）：第 $i$ 个经验的优先级为 $\displaystyle p_i=\left(\frac{1}{rank_i}\right)^\alpha$ 其中 $rank_i$ 是第 $i$ 个经验从大到小排序的排名，排名从 1 开始。

D. Horgan 等在 2018 发表文章《Distributed prioritized experience replay》，将分布式经验回放和优先经验回放相结合，得到了分布式优先经验回放（distributed prioritized experience replay）。另外，由于经验回放会导致回合更新和多步学习算法无法使用，所以一般情况下是将经验回放用于 Q 学习。

对于基于自益的 Q 学习，其回报估计和动作价值的估计都和权重 $\bold w$ 有关，当权重值变化时它们也会随着改变，而在学习的过程中，动作价值试图追逐一个变化的回报，也容易出现不稳定的情况。半梯度下降算法阻止对 $U_t$ 求梯度能够解决该问题，其中一种阻止方法是将价值参数复制一份 $\bold w_{目标}$ ，在计算 $U_t$ 时用 $\bold w_{目标}$ 计算；基于这一方法，V. Mnih 等在 2015 年发表论文《Human-level control through deep reinforcement learning》提出了目标网络（target network）这一概念，它是在原有的神经网络之外再搭建一份结构完全相同的网络，并将原先的网络称为评估网络（evaluation network）。

在学习过程中，目标网络用于自益求得回报估计作为学习目标；在权重更新过程中，先只更新评估网络的权重，在完成一定次数的更新后，再将评估网络的权重赋值给目标网络。这样由于使用目标网络得到的回报估计在一段时间内是相对稳定的，因此增加了学习的稳定性；目前目标网络也已经成为深度 Q 学习的主流做法。算法 6-9 为带目标网络的深度 Q 学习算法：

在更新目标网络时，还可以引入一个学习率 $\alpha_{目标}$ ，然后使用加权平均更新：$\bold w_{目标} \leftarrow (1-\alpha_{目标})\bold w_{目标} + \alpha_{目标}\bold w$ 。对于分布式学习的情况，有很多独立拷贝（worker）同时会修改目标网络，则就更常用学习率 $\alpha_{目标} \in (0,1)$ 。

Deepmind 于 2015 年发表论文《Deep reinforcement learning with double Q_learning》，将双重 Q 学习用于深度 Q 网络，得到了双重深度 Q 网络（Double Deep Q Network, Double DQN）。由于深度 Q 网络已经有了评估网络和目标网络，所以双重深度 Q 学习在估计回报时只需要用评估网络确定动作，用目标网络确定回报的估计即可，那么将算法 6-9 中的计算回报的估计值部分改为：

就得到了带经验回放的双重深度 Q 网络算法。

Z. Wang 等在 2015 年发表的论文《Dueling network architectures for deep reinforcement learning》提出了一种神经网络的结构——对偶网络（duel network）。对偶网络理论利用动作价值函数和状态价值函数之差定义了一个新的函数——优势函数（advantage function）：

对偶 Q 网络仍然用 $q(\bold w)$ 来估计动作价值，只不过此时其表达式为 $q(s,a;\bold w) = v(s; \bold w) + a(s,a;\bold w)$ ，训练过程中 $v(\bold w)$ 和 $a(\bold w)$ 是共同训练的，和单独训练普通深度 Q 网络并无不同之处。

由于同一个 $q(\bold w)$ 存在着无穷多种分解为 $v(\bold w)$ 和 $a(\bold w)$ 的方式，那么可以通过增加一个由优势函数导出的量，使得等效的优势函数满足固定的特征，使得分解唯一。常见的方法由以下两种：

• 考虑优势函数的最大值，令

  $$q(s,a;\bold w) = v(s;\bold w) + a(s,a;\bold w) - \max_{a \in \mathcal A} a(s,a;\bold w)$$

  使得等效优势函数 $\displaystyle a_{等效}(s,a;\bold w) = a(s,a;\bold w) - \max_{a\in\mathcal A}a(s,a;\bold w)$ 满足 $\displaystyle \max_{a \in \mathcal A}a_{等效}(s,a;\bold w)=0,\;s \in \mathcal S$ 。

• 考虑优势函数的平均值，令

  $$q(s,a;\bold w) = v(s;\bold w) + a(s,a;\bold w) - \frac{1}{|\mathcal A|}\sum_{a \in \mathcal A} a(s,a;\bold w)$$

  使得等效优势函数 $\displaystyle a_{等效}(s,a;\bold w) = a(s,a;\bold w) - \frac{1}{|\mathcal A|}\sum_{a\in\mathcal A}a(s,a;\bold w)$ 满足 $\displaystyle \sum_{a \in \mathcal A}a_{等效}(s,a;\bold w)=0,\;s \in \mathcal S$ 。

（对偶深度 Q 网络这部分书中描述太少，没怎么看明白，可能不怎么重要，后续有空再查资料补充。）

五、案例：小车上山（MountainCar-v0）

本节使用一个经典控制问题：小车上山（MountainCar-v0），gym 库中该环境的相关属性设置可查看其源代码。该问题的控制目标是让小车以尽肯能少的步骤在连续 100 个回合中的平均步数小于等于 110 步，就认为问题解决了。由于智能体施力的大小有限，在所以绝大多数情况下，智能体简单向右施力并不足以让小车成功到达目标位置。

该问题的状态空间是连续的，可以将其离散化，然后用形如 $q(s,a)=[\bold x(s,a)]^T\bold w$ 的线性组合来近似动作价值函数，求解最优策略。要从连续空间中导出数目有限的特征最简单的方法是采用独热编码（one-hot coding），砖瓦编码（tile coding）可以在与独热编码精度相同的情况下减少数目特征，具体内容可查阅相关资料，此处略。

代码中的 TileCoder 实现了砖瓦编码，并将其使用在了智能体类 SARSA 和 SARSALambda 中，然后将编码后的特征配合形如 $q(s,a)=[\bold x(s,a)]^T\bold w$ 的线性近似方法进行迭代求解；经验回放类 Replayer 实现了经验的存储与均匀回放，并将其使用在了智能体类 DQN 和 DoubleDQN 中，然后再配合神经网络近似方法进行迭代求解；这章内容的代码与书中基本一致，此处略。另外值得一提的是，SARSA($\lambda$) 算法是针对该问题最有效的方法之一。

（书上源代码的 DQN 和 DoubleDQN 智能体类运行时似乎有些问题，开始的回合很难到达终点结束回合，有时候甚至在第一回合就陷入死循环，目前还没有较好的解决方法，后续有空了再去研究。）