深度强化学习之基于值函数近似的方法

首页摘要：

2019年3月学习完强化学习基础之后，迟迟未能进一步了解深度强化学习方面的内容。虽然2020年开局就是如此严重的疫情，但对我而言，它也给了自我学习的时间。深度强化学习系列文章会从基于值函数近似的方法、基于策略梯度的方法、两者相结合的方法三个方面来进行介绍。本文介绍基于值函数近似的方法，包括Deep Q-learning及其各种改进体。

Deep Q-learning

从名字就可以看出来，Deep Q-learning是将深度学习应用在Q-learning中的方法。我们知道，Q-learning的值函数是通过将”动作-价值“对以表格的形式进行存储，因此其状态和值函数是离散的。这个特点造成了Q-learning使用的局限性——我们大多数场景的状态都是连续的，要应用Q-learning就必须进行离散化，而这很容易造成维数灾问题。为了解决这个问题，Deep Q-learning对Q-learning中的值函数用神经网络（也可以是其他机器学习方法，如决策树）进行近似表示，即输入为状态$S_{t}$、输出为”状态-动作“价值函数$q(S_{t},A_{t})$，其它步骤不变。这样，Deep Q-learning就可以对连续状态输出价值。

假设神经网络（后面也称Q网络）的参数为$w$，那么”状态-动作“价值函数$q(S_{t},A_{t})$可以表示成：

$$Q(S_{t},A_{t},w)$$

但是神经网络最大的问题是需要大量的数据来进行训练，为了解决这个问题，Deep Q-learning在部署之前必须与环境进行交互来产生大量训练数据，即五元组$\{\phi(s),a,r,\phi(s’),{isend_{j}} \}$ 集合$D$，其中$s’$是状态$s$下采取动作$a$ 后转到的下一状态，$\phi(\cdot)$是特征抽取或者特征选择函数，Deep Q-learning选择在与环境交互过程中同时对神经网络进行训练，因此使用了经验回放方式，即设置集合$D$的元素个数上限，如果与环境交互过程中$D$的元素还没充满，就添加新产生的五元组$\{\phi(s),a,r,\phi(s’),{isend_{j}} \}$ 进去，如果$D$的元素已经充满，新产生的五元组$\{\phi(s),a,r,\phi(s’),{isend_{j}} \}$ 就替换最老的五元组（类似队列弹出）。

下面给出Deep Q-learning的具体算法流程：

输入:迭代轮数 $T$、状态特征维度$n$、即时回报 $r$ 、衰减因子 $\gamma$ 、探索率 $\epsilon$ 、Q网络结构、批量梯度下降的样本数$m$；

输出:Q网络参数；

1.随机初始化Q网络的所有参数$w$，基于$w$初始化所有的状态和动作对应的价值$q$，清空经验回放的集合$D$；

2.for $i$ to $T$ ，进行迭代

（1）初始化$s$为当前状态序列的第一个状态, 拿到其特征向量$\phi(s)$

（2）在Q网络中使用$\phi(s)$作为输入，得到Q网络的所有动作对应的$q$值输出。用$\epsilon-greedy $贪婪法在当前$q$值输出中选择对应的动作$a$

（3） 在状态$s$执行当前动作$a$,得到新状态$s’$对应的特征向量$\phi(s’)$和奖励$r$,是否终止状态$is_end$

（4）将五元组$\{\phi(s),a,r,\phi(s’),isend \}$ 放入经验回放集合$D$

（5）$s=s’$

（6）从经验回放集合$D$中采样$m$个样本$\{ \phi(s_{j}),a_{j},r_{j},\phi(s’_{j}),isend_{j}\},j=1,2,…,m$ ，计算这些样本的目标$q_{j}$值：

$$q_{j}=\left\{\begin{array}{ll} {r_{j}} & {isend_{j} \text { is true }} \\ {r_{j}+\gamma \max _{a_{j}^{\prime}} Q\left(\phi\left(s_{j}^{\prime}\right), a_{j}^{\prime}, w\right)} & {isend_{j} \text { is false }} \end{array}\right.$$

（7）使用均方差公式$\frac{1}{m} \sum_{j=1}^{m}\left(q_{j}-Q\left(\phi\left(s_{j}\right), a_{j}, w\right)\right)^{2}$作为损失函数来更新Q网络的参数$w$

（8）如果 $s$ 是终止状态，当前轮迭代完毕，否则转到步骤(2)

这里有一个要注意的是， $\epsilon$ 一般需要随着迭代的进行逐渐变小，这样才能保证Q网络可以收敛。然而，即使这样，Deep Q-learning的主要问题仍然是收敛问题，其主要解决办法包括Nature DQN、Double DQN (DDQN)、Prioritized Replay DQN、Dueling DQN。下面几节通过一步步改进来分别介绍。

Nature DQN

原始的Deep Q-learning经验回放中样本的目标$q_{j}$值计算公式为：

$$q_{j}=\left\{\begin{array}{ll}{r_{j}} & {isend_{j} \text { is true }} \\{r_{j}+\gamma \max _{a^{\prime}} Q\left(\phi\left(s_{j}^{\prime}\right), a_{j}^{\prime}, w\right)} & {isend_{j} \text { is false }}\end{array}\right.$$

可以看出，用来更新Q网络参数的目标$q_{j}$值是通过Q网络自身来进行计算的，这样造成的相关性会使得算法整体收敛性变慢。为了解决这个问题，Nature DQN增加了一个新的目标Q‘网络来计算目标$q_{j}$值，而这个网络参数$w’$和Q网络在若干时刻之前的参数一模一样，每隔一段时间，就将Q网络的参数覆盖Q’网络的参数。其它计算步骤和Deep Q-learning一致，具体算法流程如下：

输入:迭代轮数 $T$、状态特征维度$n$、即时回报 $r$ 、衰减因子 $\gamma$ 、探索率 $\epsilon$ 、Q网络结构、目标Q’网络结构（其实和Q网络一样，之所以叫这个名字是因为用来计算目标$q$值）、批量梯度下降的样本数$m$、更新目标Q’网络的频率$C$；

输出:Q网络参数；

1.随机初始化Q网络的所有参数$w$，目标Q’网络参数$w’=w$，基于$w$初始化所有的状态和动作对应的价值$q$，清空经验回放的集合$D$；

2.for $i$ to $T$ ，进行迭代

（1）初始化$s$为当前状态序列的第一个状态, 拿到其特征向量$\phi(s)$

（2）在Q网络中使用$\phi(s)$作为输入，得到Q网络的所有动作对应的$q$值输出。用$\epsilon-greedy $贪婪法在当前$q$值输出中选择对应的动作$a$

（3） 在状态$s$执行当前动作$a$,得到新状态$s’$对应的特征向量$\phi(s’)$和奖励$r$,是否终止状态$is_end$

（4）将五元组$\{\phi(s),a,r,\phi(s’),isend \}$ 放入经验回放集合$D$

（5）$s=s’$

（6）从经验回放集合$D$中采样$m$个样本$\{ \phi(s_{j}),a_{j},r_{j},\phi(s’_{j}),isend_{j}\},j=1,2,…,m$ ，计算这些样本的目标$q_{j}$值：

$$q_{j}=\left\{\begin{array}{ll}{r_{j}} & {isend_{j} \text { is true }} \\{r_{j}+\gamma \max _{a_{j}^{\prime}} Q'\left(\phi\left(s_{j}^{\prime}\right), a_{j}^{\prime}, w'\right)} & {isend_{j} \text { is false }}\end{array}\right.$$

（7）使用均方差公式$\frac{1}{m} \sum_{j=1}^{m}\left(q_{j}-Q\left(\phi\left(s_{j}\right), a_{j}, w\right)\right)^{2}$作为损失函数来更新Q网络的参数$w$

（8）如果$T\%C==1$，$w’=w$

（9）如果 $s$ 是终止状态，当前轮迭代完毕，否则转到步骤(2)

Double DQN (DDQN)

和Nature DQN相同的是，DDQN也创造了一个目标Q’网络。但是DDQN认为Nature DQN存在过度估计的问题，具体体现在计算目标$q$值中：

$$q_{j}=\left\{\begin{array}{ll}{r_{j}} & {isend_{j} \text { is true }} \\{r_{j}+\gamma \max _{a_{j}^{\prime}} Q'\left(\phi\left(s_{j}^{\prime}\right), a_{j}^{\prime}, w'\right)} & {isend_{j} \text { is false }}\end{array}\right.$$

为什么说它存在过度估计呢？从上面的公式可以看出，计算每个样本的目标$q$值时采用了贪婪法 ，即选取动作价值最大的动作。这样做的缺点是，它总是倾向选择过度估计的动作，这里理解起来可能会有一些绕口，用一张图来说明：

从上图可以看到，蓝色表示四个工作的真实$q$值，橙色部分为高估的值（算法不可能绝对准确得到某动作的$q$，因此存在高估或者低估的部分）。如果是Nature DQN算法，它会选择动作$a_{1}$，因为它的真实$q$值加上估计值最大，然而动作$a_{3}$的真实$q$值才是最大的。这样的后果是会使得最后选到动作$a_{3}$需要更多的算法迭代，因此不利于算法收敛。

DDQN的做法是使用通过贪婪法选择使得Q网络的$q$值最大的动作来作为Q’网络计算目标$q$值的动作，如下式所示：

$$q_{j}=r_{j}+\gamma \max _{a_{j}^{\prime}} Q'\left(\phi\left(s_{j}^{\prime}\right), \arg \max _{a_{j}^{\prime}} Q\left(\phi\left(s_{j}^{\prime}\right), a_{j}, w\right), w'\right),isend_{j} \text { is false }$$

DDQN其它步骤和Nature DQN一致，具体算法流程如下：

输入:迭代轮数 $T$、状态特征维度$n$、即时回报 $r$ 、衰减因子 $\gamma$ 、探索率 $\epsilon$ 、Q网络结构、目标Q’网络结构（其实和Q网络一样，之所以叫这个名字是因为用来计算目标$q$值）、批量梯度下降的样本数$m$、更新目标Q’网络的频率$C$；

输出:Q网络参数；

1.随机初始化Q网络的所有参数$w$，目标Q’网络参数$w’=w$，基于$w$初始化所有的状态和动作对应的价值$q$，清空经验回放的集合$D$；

2.for $i$ to $T$ ，进行迭代

（1）初始化$s$为当前状态序列的第一个状态, 拿到其特征向量$\phi(s)$

（2）在Q网络中使用$\phi(s)$作为输入，得到Q网络的所有动作对应的$q$值输出。用$\epsilon-greedy $贪婪法在当前$q$值输出中选择对应的动作$a$

（3） 在状态$s$执行当前动作$a$,得到新状态$s’$对应的特征向量$\phi(s’)$和奖励$r$,是否终止状态$is_end$

（4）将五元组$\{\phi(s),a,r,\phi(s’),isend \}$ 放入经验回放集合$D$

（5）$s=s’$

（6）从经验回放集合$D$中采样$m$个样本$\{ \phi(s_{j}),a_{j},r_{j},\phi(s’_{j}),isend_{j}\},j=1,2,…,m$ ，计算这些样本的目标$q_{j}$值：

$$q_{j}=\left\{\begin{array}{ll}{r_{j}} & {isend_{j} \text { is true }} \\{r_{j}+\gamma Q'\left(\phi\left(s_{j}^{\prime}\right), \arg \max _{a_{j}} Q\left(\phi\left(s_{j}^{\prime}\right), a_{j}, w\right), w'\right)} & {isend_{j} \text { is false }}\end{array}\right.$$

（7）使用均方差公式$\frac{1}{m} \sum_{j=1}^{m}\left(q_{j}-Q\left(\phi\left(s_{j}\right), a_{j}, w\right)\right)^{2}$作为损失函数来更新Q网络的参数$w$

（8）如果$T\%C==1$，$w’=w$

（9）如果 $s$ 是终止状态，当前轮迭代完毕，否则转到步骤(2)

Prioritized Replay DQN

DDQN中经验回放采样是采取随机的方式，通过改进采样方式也能加快算法收敛。怎么做呢？从Q网络损失函数我们知道，如果目标Q’网络计算的目标$q_{j}$值和Q网络计算的Q值的差越大，那么Q网络反向更新的梯度越大，收敛速度越快，这个也被称之为TD误差，因此Prioritized Replay DQN就利用对TD误差绝对值大的样本赋予优先级（表现形式是权重），这样它被采样的概率就大，优先级的赋予方式采取的是SumTree（不知道这个可以查资料了解）。同时损失函数也改进为：

$$\frac{1}{m} \sum_{j=1}^{m} w_{j}\left(q_{j}-Q\left(\phi\left(S_{j}\right), a_{j}, w\right)\right)^{2}$$

$w_{j}$就是优先级权重。Prioritized Replay DQN的其它步骤和DDQN一致，具体算法如下：

输入:迭代轮数 $T$、状态特征维度$n$、即时回报 $r$ 、衰减因子 $\gamma$ 、探索率 $\epsilon$ 、Q网络结构、目标Q’网络结构（其实和Q网络一样，之所以叫这个名字是因为用来计算目标$q$值）、批量梯度下降的样本数$m$、更新目标Q’网络的频率$C$、SumTree的叶子节点数$N$；

输出:Q网络参数；

1.随机初始化Q网络的所有参数$w$，目标Q’网络参数$w’=w$，基于$w$初始化所有的状态和动作对应的价值$q$，清空经验回放的集合$D$，初始化经验回放SumTree的默认数据结构，所有SumTree的$N$个叶子节点的优先级$p_{j}$为1；

2.for $i$ to $T$ ，进行迭代

（1）初始化$s$为当前状态序列的第一个状态, 拿到其特征向量$\phi(s)$

（2）在Q网络中使用$\phi(s)$作为输入，得到Q网络的所有动作对应的$q$值输出。用$\epsilon-greedy $贪婪法在当前$q$值输出中选择对应的动作$a$

（3） 在状态$s$执行当前动作$a$,得到新状态$s’$对应的特征向量$\phi(s’)$和奖励$r$,是否终止状态$is_end$

（4）将五元组$\{\phi(s),a,r,\phi(s’),isend \}$ 放入经验回放集合$D$

（5）$s=s’$

（6）从SumTree中采样$m$个样本$\{ \phi(s_{j}),a_{j},r_{j},\phi(s’_{j}),isend_{j}\},j=1,2,…,m$ ，每个样本被采样的概率基于是$P(j)=\frac{p_{j}}{\sum_{i}\left(p_{i}\right)}$，损失函数权重是$w_{j}=(N * P(j))^{-\beta} / \max _{i}\left(w_{i}\right)$，计算这些样本的目标$q_{j}$值：

$$q_{j}=\left\{\begin{array}{ll}{r_{j}} & {isend_{j} \text { is true }} \\{r_{j}+\gamma Q'\left(\phi\left(s_{j}^{\prime}\right), \arg \max _{a_{j}} Q\left(\phi\left(s_{j}^{\prime}\right), a_{j}, w\right), w'\right)} & {isend_{j} \text { is false }}\end{array}\right.$$

（7）使用均方差公式$\frac{1}{m} \sum_{j=1}^{m} w_{j}\left(q_{j}-Q\left(\phi\left(S_{j}\right), a_{j}, w\right)\right)^{2}$作为损失函数来更新Q网络的参数$w$

（8）如果$T\%C==1$，$w’=w$

（9）如果 $s$ 是终止状态，当前轮迭代完毕，否则转到步骤(2)

Dueling DQN

Dueling DQN在Prioritized Replay DQN的基础上改进了Q的网络，将其输出变成了价值$V(s)$和优势函数$H(s,a)$（reward减去其期望值，表明某个动作的优势），具体变化如图所示：

这样可以加快算法收敛速度，至于为什么，我也还没理解……其它步骤和Prioritized Replay DQN是一样的，区别在于Q网络的不同，具体算法如下：

输入:迭代轮数 $T$、状态特征维度$n$、即时回报 $r$ 、衰减因子 $\gamma$ 、探索率 $\epsilon$ 、Q网络结构、目标Q’网络结构（其实和Q网络一样，之所以叫这个名字是因为用来计算目标$q$值）、批量梯度下降的样本数$m$、更新目标Q’网络的频率$C$、SumTree的叶子节点数$N$；

输出:Q网络参数；

1.随机初始化Q网络的所有参数$w$，目标Q’网络参数$w’=w$，基于$w$初始化所有的状态和动作对应的价值$q$，清空经验回放的集合$D$，初始化经验回放SumTree的默认数据结构，所有SumTree的$N$个叶子节点的优先级$p_{j}$为1；

2.for $i$ to $T$ ，进行迭代

（1）初始化$s$为当前状态序列的第一个状态, 拿到其特征向量$\phi(s)$

（2）在Q网络中使用$\phi(s)$作为输入，得到Q网络的所有动作对应的$q$值输出。用$\epsilon-greedy $贪婪法在当前$q$值输出中选择对应的动作$a$

（3） 在状态$s$执行当前动作$a$,得到新状态$s’$对应的特征向量$\phi(s’)$和奖励$r$,是否终止状态$is_end$

（4）将五元组$\{\phi(s),a,r,\phi(s’),isend \}$ 放入经验回放集合$D$

（5）$s=s’$

（6）从SumTree中采样$m$个样本$\{ \phi(s_{j}),a_{j},r_{j},\phi(s’_{j}),isend_{j}\},j=1,2,…,m$ ，每个样本被采样的概率基于是$P(j)=\frac{p_{j}}{\sum_{i}\left(p_{i}\right)}$，损失函数权重是$w_{j}=(N * P(j))^{-\beta} / \max _{i}\left(w_{i}\right)$，计算这些样本的目标$q_{j}$值：

$$q_{j}=\left\{\begin{array}{ll}{r_{j}} & {isend_{j} \text { is true }} \\{r_{j}+\gamma Q'\left(\phi\left(s_{j}^{\prime}\right), \arg \max _{a_{j}} Q\left(\phi\left(s_{j}^{\prime}\right), a_{j}, w\right), w'\right)} & {isend_{j} \text { is false }}\end{array}\right.$$

（7）使用均方差公式$\frac{1}{m} \sum_{j=1}^{m} w_{j}\left(q_{j}-Q\left(\phi\left(S_{j}\right), a_{j}, w\right)\right)^{2}$作为损失函数来更新Q网络的参数$w$

（8）如果$T\%C==1$，$w’=w$

（9）如果 $s$ 是终止状态，当前轮迭代完毕，否则转到步骤(2)

结语

至此，我们介绍完了Q-learning及其变体的过程。但是Deep Q-learning还存在无法处理连续动作的问题（当然也有相应的改进，但是效果并不如人意，因此就视若无吧），基于策略梯度的方法可以很好地解决这个问题，这个我们在下一篇文章中介绍。