强化学习dqn系列梳理--从入门到进坑

标签：强化学习 深度学习 机器学习 Deep Qlearning DQN 人工智能

一、基础知识

强化学习可以划分为基于价值函数的方法，策略梯度方法，和结合策略梯度以及价值函数的actor-critic方法；其中基于价值函数的典型算法是Q-learning，Q-learning是使用时序差分的off-policy的方法。

Q-learning：基础知识

或者写成渐进式的形式

借助贝尔曼公式公式，上式迭代收敛后右侧方括号内的式子将收敛至0。考虑到使用非线性近似，可以把损失函数定为：

其中

求导可得：

接下来就可以使用梯度下降算法来进行优化了。

Q-learning是一种时序差分算法，因为它使用了当前对Q的估计值代替了真实的Q值；同时它又是一种off-policy的算法，因为其中max的操作使得它对回报的估计始终是基于greedy策略的，而实际动作的选择可以依据与对回报的估计无关，可以选用ξ-greedy策略。

二、相关论文

1、深度强化学习开山之作DQN

DeepMind《Playing Atari with Deep Reinforcement Learning》提出了DQN ，DQN使用卷积神经网络作为价值函数来拟合Q-learning中的动作价值，这是第一个直接从原始像素中成功学习到控制策略的深度强化学习算法。DQN 模型的核心就是卷积神经网络，使用Q-learning 来训练，其输入为原始像素，输出为价值函数。在不改变模型的架构和参数的情况下，DQN在七个Atari2600游戏上，击败了之前所有的算法，并在其中三个游戏上，击败了人类最佳水平。

将深度学习应用在强化学习上，面临诸多挑战。第一个挑战，大多数成功的（有监督）深度学习算法都需要巨大的数据量，而强化学习算法通常只能提供稀疏的，有噪声的，以及延迟的奖励；同时强化学习的回报与相应的产生回报的动作之间可能有数千步的间隔，对比监督学习直截了当的输入输出映射，训练要难得多另一个挑战在于，深度学习通常假设数据样本独立同分布。而对于强化学习来讲，作为训练样本的状态是一个序列，而且通常状态之间高度相关。就是，随着训练的进程，价值函数对动作价值的估计不断得到优化。而随着价值函数的变化，其Q值输出（动作输出）也会跟着改变，继而产生的训练样本的分布也会改变。这与深度学习要求训练用的数据分布不变不符合;

       DQN最关键的技术，就是采用了经验回放。通过在经验回放中随机均匀采样，打破了训练样本之间的相关性；同时，采用过去的多个样本做平均，也平滑了训练样本分布，减缓了样本分布变化的问题。

       在经验回放中，将多个episode过程中，代理每一步使用ξ-greedy来选择动作，产生的经验e t = (st, at, rt, st+1)，存入一个经验记忆池D中，在算法的参数更新循环里，对记忆池里的样本进行随机采样或批量随机采样，通过Q-learning对模型进行参数更新。由于处理变长数据对神经网络来说有困难，所以DQN使用固定长度的历史数据来表征状态，具体来说，就是过去三帧或四帧图像的融合。

       这种方法对于传统的在线Q-learning来说，有很多优势。第一个优势是，每一步的数据都可以被多次采样，极大的提高了数据效率。第二个优势是，直接从连续的数据里学习效率低下，因为前后的样本之间高度相关。而随机采样打破了这些相关性，因此降低了参数更新的方差。第三个，在线的Q-learning下当前的参数决定了下一个参数更新所用到的数据样本。比如，当前的参数决定了最大动作是向左，那么接下来的样本多数也会是来自于左半边的样本，然后这些来自左半边的样本再用于训练。显然这样训练过程可能会陷入一个不好的循环，参数可能会收敛到局部极值，甚至发散。通过经验回放，数据分布会在过去多个状态下被平均，从而平滑了训练过程，避免了训练发散。由于使用了经验回放，算法必然是off-policy的，因为产生数据样本（动作选择）的网络参数与当前被训练的网络参数是不同的，也就是生成动作的policy与算法学习的policy是不同的。

       实际操作中，经验回放仅存储最近的N个样本点，当参数更新时均匀的从这些样本点中采样。这种方法也有其缺点，经验池不能区分哪些样本点更重要；同时，经验池的样本也会不断的被最近的数据所覆盖掉。均匀采样也赋予了每个样本同样的重要性，更聪明的采样策略应该是对那些能够学到更多的样本点赋予更多的权重，类似于Prioritized Sweeping。

       DQN对数据做了基本的预处理。如果直接使用原始的Atari 画面，每帧画面有210x160像素，色彩深度为128，那么计算量将会非常庞大。首先把输入DQN的图像从RGB转换为了灰度图，然后降采样到110x84像素，因为GPU的2D卷积神经网络要求方形输入，所以最终裁剪为包含主要动作区域的84x84像素大小。最后由一个函数将四副图像拼到一起。

       另外需要注意，DQN在每次参数更新之前，会固定上一次参数更新的网络参数，来产生本次更新的目标。注意这儿训练目标是随着训练过程在变化的，这一点与监督学习在训练前就确定训练目标也是不一样的。

       关于Q的处理，一种做法是将状态和（已经出现过的）动作值一起输入网络，然后输出对应的Q值。然而这样做的缺点是每一个动作值都需要重新前向计算一次。所以DQN采取的做法是，只将状态输入，然后每一个可能的动作对应一个Q值的输出，这样最主要的好处是只需要一次前向即可。最终的结构是，输入图像为84x84x4像素,第一个卷积层包含16个8x8 卷积核，以步长为4进行卷积，随后是整流非线性层；第二个卷积层为32个4x4卷积核，以步长为2卷积，再跟一个整流非线性层；接下来是全链接层和256个非线性单元；输出层则是一个全链接层产生动作个数个输出。在论文中，输出动作个数依据游戏不同为4-18个。

       DeepMind共在7个游戏上测试了DQN的性能。所有游戏使用了相同的超参，但是Rreward进行了裁剪。将所有的正的Reward归为1,将所有的负Rreward归为0，0值Reward保持不变。这样做控制了反向传播的误差的范围，同时保证了多个游戏间可以使用相同的学习率。与此同时，这样做可能降低算法的性能，因为限制了奖励的大小所带来的额外信息。训练DQN使用了RMSProp算法，批大小为32,ξ-greedy，ξ从1下降到0.1,一百万帧后固定到0.1。算法总共训练了1000万帧;为了减小计算量，训练过程使用了跳帧，每4帧选择一次动作，中间的3帧延续前一帧的动作。

2、DQN改进：

       DeepMind在Nature2015发表了《Human-level control through deep reinforcementlearnin》，进一步改进了DQN。当使用非线性近似例如神经网络来表征Q时，强化学习的过程并不稳定甚至会发散。这种不稳定性主要有几个原因：1、用于训练的状态是一个序列，该序列中的前后的状态高度相关；2、Q参数有微小更新就会导致策略发生巨大变化，并因此导致训练样本分布的巨大变化。3、目标函数中使用的Q函数（目标Q函数）和待优化Q函数（在线Q函数）之间的参数联系，每次更新的目标都是固定上次更新的参数得来，优化目标跟着优化过程一直在变。在DQN中，通过使用经验回放有效的解决了前两个问题，通过存储并随机采样经验来打破了样本之间的相关性，同时平滑了数据分布。第三个问题则是这次改进完成的。通过在在线Q函数参数更新一定周期之后再去更新目标Q函数的参数，从而降低了目标Q函数与在线Q函数之间的相关性。

       具体来看，算法通过引入了一个单独的网络（目标网络）来生成训练过程的目标。这个网络的结构与DQN的神经网络（在线网络）一致，每参数升级C步，将在线网络的参数复制给目标网络，然后再用更新后的目标网络来生成接下来C布参数更新的目标。由于函数近似的泛化性，当一次参数升级使得Q(st,at)提高经常会导致Q(st+1,a)下个状态所有动作的Q值提高，从而导致优化的目标随着优化过程而提高。显然优化目标随着优化过程变化不是什么好事，这种情况可能会导致训练陷入恶性循环或者发散。延迟更新参数网络在参数更新和参数更新对目标网络的影响之间增加了延迟，增加了训练的稳定性。

       另外，文章还对算法流程做了两个小的改进。第一个改进，在输入数据的预处理上，DQN是使用了之前的四帧数据做融合作为状态输入，而本文中则是使用了一个函数对之前所有的帧进行了融合作为状态输入。第二个改进，限制了参数更新的误差项在-1到1之间。由于绝对值损失函数在小于1的时候所有的梯度都是-1，大于1的时候所有的梯度都是1,所以可以视为参数更新的误差项绝对值大于1的时候训练使用了绝对值损失函数。数据预处理上，与前作DQN稍有不同，不再赘述，详情可参见论文。

3、Double Q-learning

       Q-learning算法会在特定状态下会高估某些动作的价值。Hasslt等人在《Deep Reinforcement Learning with Double Q-learning》证明，在实际中，这种高估是常见现象，而且它们会损害算法性能。Hasslt等人指出，通过将Double-Qlearning从表格方法扩展到非线性近似，不仅可以解决DQN下观察到的价值高估，并大幅提高了DQN在某些方面的性能。

       在早期的工作中，价值高估被归因为函数近似能力有限(Thrun and Schwartz, 1993)，或者是由噪声引起(van Hasselt, 2010, 2011)。在本篇文章中，Hasslt等人认为，只要动作价值估计不精确，就会引起价值高估，而不论引起估值不精确的原因。鉴于不精确的价值估计在训练过程中无法避免，所以价值高估要比之前认识到的普遍的多。

       价值高估是否会影响算法在实际中的表现呢？一方面，如果所有的高估均匀的发生在每一个动作上，实际上对最优策略是没有影响的；同时，价值高估所引起的不确定性也是一个广为人知的策略探索技巧(Kaelbling et al., 1996)。另一方面，如果价值高估并不是均匀发生的并且使得没有太高价值的动作价值偏高上，那么就会影响到策略的质量甚至生成次优策略(Thrun and Schwartz (1993))。

       出现价值高估的根源，是在标准的Q-learning以及DQN中，估计回报时选取最大动作值所使用的价值函数，和评估此动作值所用的价值函数，是同一个，也就是DQN中的卷积神经网络。正是这种操作，使得价值高估更容易出现。直觉来讲，如果一个动作被高估（不管是因为噪声还是训练过程中的正常误差），那么它就更有可能选中。而由于Q-learning的动作评估与动作选择用的是同一个网络，那么在后续估计这个动作的价值用于参数更新（的目标）时，动作的价值也必然会被高估。这样（用高估的价值函数估计被高估的动作）势必会影响学习的稳定性，甚至产生次优策略。数学上可以证明，即使某个状态下所有动作的价值估计在平均上是正确的，也仍然存在一个正的下界，高估是不可避免的。此下界在理论上随着动作的增加逐渐降低，然而在实际中，随着动作的增多，价值高估会变得更严重。同等条件下，Double Q-learning的价值高估下界为0。

采取的解决办法可以是将动作选择和动作价值评估解偶。通过对代理的经验随机采样来平等的训练两个价值函数，每一次的参数更新，使用其中的一个价值函数来做动作选择，而另外一个函数用于评估其价值。为了更清晰的展示这一过程，以DQN为例，可以将DQN的公式解偶。

1、Q-learing的优化目标函数：

2、将上式中动作选择和价值评估分离：

3、将动作选择和价值评估分别用两组参数表示：

由于DQN已经有了两个网络，所以可以利用现有的两个网络，稍作修改来实现DoubleQ learning。动作选择使用原来的在线网络，而价值评估使用原来的目标网络；在线网络使用经验回放训练，目标网络仍然每隔C步由在线网络复制而来。对比DQN，改动之处就是目标函数的动作选择变成了使用在线网络来完成。

1、DQN的优化目标函数，其中的价值评估使用θ的副本θ−来生成：

2、将上式重写为动作选择和价值分离的形式：

对比原始的DoubleQlearning，第二个网络由目标网络替代，对第二个网络的参数训练由随机采样变为了每隔一定周期从在线网络复制。这样做虽然没有将动作选择和价值评估完全分离，牺牲了一些DoubleQlearning的一些优势，然而可以已最小的改动嵌入现有的DQN框架。

4。Duaeling Network

       Duaeling的主要思想是，把之前的动作价值函数一分为二，分别分为状态价值函数和和优势函数，即：

对比于原始的DQN对动作进行估值（Q值）的一条数据流，现在变为估计价值函数和估计优势函数两条数据流。注意状态价值函数和优势函数最后相加，输出仍然是每个动作的价值（Q值）。状态价值估计和优势函数估计是通过构建网络结构分离的，其学习过程是无监督的。这使得这种双网络架构可以融入到现有的框架中。

       直觉上讲，这样做可以学习到一个状态的的价值，而不受这个状态下各个动作的影响。对于某些状态，其动作完全不会对环境产生影响，这种情况下Duealing Network尤其有用。引用论文中赛车的例子，观察赛车游戏的两个时间点，第一个时间点内，状态价值函数关注于路面特别是地平线的位置，因为这些地方可能会出现车辆，影响环境状态；优势函数则没有关注任何位置，因为前方没有车辆的时候，取什么动作都是无关紧要的。第二个时间点，价值函数仍然关注路面和地平线，而优势函数关注正前方的车辆，因为这个时候采取什么动作将直接影响到游戏得分。另外价值函数和优势函数同时关注记分牌。

       实验也证明，当冗余或者相似的动作加入时，得益于价值函数和优势函数的分离，模型也可以快速的学习这些新动作的价值，而不必重新学习状态的价值。对于自举的模型，对状态价值的估计极度重要，因为自举中用到了对Q的估计。

       注意本文的优势函数和策略梯度方法中的优势函数概念是一致的；优势函数在策略梯度中的应用已经有很久的历史(Sutton et al., 2000)，最近Schulman把它用在TRPO中用于减小参数更新的方差。

       文章混合价值估计和优势估计来产生Q的模块设计考虑巧妙。单独取Qπ (s, a) = V π (s)+Aπ (s, a)并不能保证二者的良好分离，比如可以V多一点而A少一点，Q还是相同的。为了限制分离出来的V就是理论意义上的V，考虑最优策略下的最大动作值, a*= argmaxa`∈A Q(s, a`), 可得 Q(s, a* ) = V (s) ，因此 A(s, a∗ ) = 0。可通过限制 A(s, a*) = 0来保证分离出来的V就是最优策略下的V*。所以取Q(s, a; θ, α, β) = V (s; θ, β) +(A(s, a; θ, α) − max a`∈A A(s, a` ; θ, α) )强制括号中的两项取值为0。

       这儿需要注意，依据优势函数的定义，有Qπ (s, a) = V π (s)+ Aπ (s, a)时；而公式Q(s, a; θ, α, β) = V (s; θ, β) +(A(s, a; θ, α) − max a`∈A  A(s, a` ; θ, α) )中，后面括号里的两项整体才跟Qπ (s, a) = V π (s)+ Aπ (s, a)中的A在意义上相对应。而文章后面说的所有的A，包括下面的A，都是指的括号里单独项的A，注意区分。

       文章中提出了减平均和减最大值两种分离方式。先看减最大动作的A值的方式，那么在动作取最大值的时候，只优化V*（括号中整体为0），也就是最优策略下的状态价值函数。这个限定条件限制了V具有状态价值函数的理论意义。由于所有动作共享V值，所以对于所有其他的动作，由于受到V*的限制，也会被拆分为在最优策略下的状态价值函数和该动作对应的优势函数（括号中两项整体）。这些动作的优势函数，相当于固定最优策略下的价值函数V*，然后根据各自的Q值，依据贝尔曼公式，在迭代中形成对括号内项整体的估计，即A(s, a; θ, α) − max a`∈A A(s,a`; θ, α) = Q - V*。最终A(s, a; θ, α) 需要与max a`∈A A(s, a`; θ, α) 形成平衡，这也就是文章中A需要补偿最大值的含义。这种方式下的V和A（指括号中两项的整体）的划分，是与其理论意义相符的。

       再看减平均。由于减平均，将优势函数（括号中两项整体）的值限定在一定范围内。而对于所有的动作，无论最优与否，他们的V值都是一样的（所有动作共用状态价值函数），所以无论优化哪一个动作的价值，都会优化到V，V值最终会稳定在一个平衡态上（贝尔曼公式）。而对于每一个动作，其优势函数（括号中两项整体）会在减掉统一的V的基础上，根据各自的Q值，依据贝尔曼公式，在迭代中形成对括号内项整体的估计，即A(s, a; θ, α) − Σa`∈A A(s,a`; θ, α)/|A| = Q – V，最终A，Σa`∈A A(s,a`; θ, α)/|A|,二者达到平衡，这也就是文章中A需要跟随平均的含义。由于A只需要跟随平均值，对比需要跟随最大值，提高了训练的稳定性。然而共用的V是依据贝尔曼公式迭代出来的，只是一个稳定值而已，不具备价值函数本身的意义，A也一样。其实有没有具体的意义并不重要，因为减去平均并不会改变动作值大小的排序，也就不影响greedy policy；同时，采用优势函数的精髓就在于价值和动作的分离。只要可以分离出一个不随动作而改变的V，就可以达到想要的效果，当然分离的方式和V的大小还是影响效果的（但是对于减平均，文章证明效果与减最大值基本没区别）。

       使用优势函数可以取得更好效果的原因之一是，由于V和A的分离，所有动作的A都对应于同一个V，任何一个动作得到训练，V都会同时被训练。而对于不分离状态价值函数和优势函数的情况，只有当前被训练的动作，其V才会被训练，与此同时其他所有动作的V都保持不变。分离状态价值函数和优势函数后，V得到更多的训练机会，就会更精确，Q也就会越精确。这种精确性对于Q-learning这种自举的时序差分算法是非常重要的。另外，在某个状态下，Q值之间的差异可能很小（在DDQN中，最大Q值与最小Q值的差大约是0.04），而对应状态的价值相对而言就大得多（平均15））。所以，相对于Q值的大小，很小的噪声就会引起可能引起greedy policy发生大的改变，而将V和A分离，这种情况就要鲁棒的多。

5、Prioritized Experience Replay

       经验回放让增强学习可以记住和重用样本。在之前的工作中，经验是从经验回放中均匀采样的，但是这种方式并不能区分样本的重要性。采用Prioritized Experience Replay，可以让重要的经验以更高频率进行回放，因而可以让代理更快更有效的学习。

       相对于某些经验，强化学习代理可以从另外一些经验中更有效的学习。对强化学习代理而言，有些经验更有用，而有些经验是冗余的；还有些经验在当前的训练阶段用处不大，但是随着代理能力的增强会变得有用。优先经验回放（Prioritized Experience Replay）可以让对学习过程更有用的样本以更高的频率回放，其中对学习过程的作用使用时序差分误差（TD-error）的大小来衡量。TD-error表示了当前价值函数输出的动作价值与对该动作价值的估计值之间的差异。越大的TD-error表示当前价值函数的输出越不准确，也就暗示可以从该样本中学到更多。由于新生成的样本不知道其TD-error，所以把它放在第一位，以保证至少回放一次，之后每次都回放TD-error最大的样本。这样单独的使用TD-error来做贪婪优先经验回放，存在许多问题，第一个是，为了避免在整个经验池上更新TD-error, 只有被重放的经验的TD-error被更新，这样就会导致TD-error较小的样本在第一次被回放之后很久都不会被重新回放（在参数更新之后此样本的TD-error可能会变大，然而由于不更新，它会一直被认为很小）；第二个是，对噪声敏感（例如奖励是随机的时候或者在噪声影响下，某些经验的TD-error可能始终不会减小，进而导致其不断被重放），自举会进一步加剧这个问题，因为在自举中近似函数的误差也是噪声的一种。最后，贪婪优先回放的样本会集中在一个小范围内，因为在非线性近似中，TD-error的缩小是很慢的，开始TD-error大的样本可能会被回放很多次，这种多样性的缺失容易导致过拟合的产生。

注意这儿优先回放赋予新生成的样本最高的优先级。在均匀采样的经验回放中，有的经验始终得不到被回放，而有些经验在生成很久后才第一次被回放；另外，均匀采样引入了偏差，因为有些样本是由成千万步之前的policy生成的，样本分布偏离当前的policy产生的样本分布。赋予新生成的样本最高的优先级解决了前面一个问题，同时缓解了第二个问题----旧的样本有更大的机会已经被训练过，TD-error较小，从而被回放的概率更小。

       文章引入了一种随机优先回放的机制，通过调节超参，可以控制贪婪优先回放采样和随机均匀采样所占的比例，这样既保证了样本采样的概率与它的优先级一致，同时即使是优先级最低的样本也有一定概率被采样到。

其中pi有两种定义方式，分别是取时序差分误差和根据时序差分误差对样本排序后序号的倒数。当上式中α取0的时候，样本分布退化为均匀分布。

       对这两种pi的定义方式进行对比，文章认为基于排序的方式更加鲁棒。因为第一，基于排序不会受到异常值和时序差分误差大小的影响；第二，这种方式排序尾部的样本也有相对较大的概率被采样，有助于保持样本多样性；第三，基于这种方式的批量采样可以保持总的样本梯度在整个训练过程中幅值保持稳定。但是基于排序的方式使得算法忽略了时序差分误差大小的幅度，这在误差呈现结构化分布时，会降低算法性能。不过实际中两种pi的定义方式并没有大的区别，可能因为DQN的梯度裁剪已经去掉了异常值，而且在许多游戏本身的时序差分误差分布下，尾部的经验样本概率就较大。这样就抵消了基于排序的定义方式的前两条优势。

       对价值函数的正确估计，依赖于参数更新中所使用的样本分布与价值函数的期望一致，训练样本的期望要与样本本身所服从的真实分布的期望一致，随机梯度下降的结果才是无偏的。然而引入优先经验回放改变了样本回放的频率，因而改变了样本的分布，这样就使得对价值的估计有偏差。通过重要性采样可以纠正这个问题。

       取β为1 的时候，通过用wi*δ 替代掉Q-learning更新中的δ，可以完全补偿优先经验回放所带来的分布改变(Mahmood et al., 2014)。所有的wi使用maxi(wi)做归一化，以保证δ只会被向下缩放，以增加稳定性。

       在典型的增强学习过程中，虽然训练过程高度不稳定，受到不断变化的策略和状态分布，还有自举下目标函数的变化和误差的影响，最终仍会收敛到无偏估计的状态。因此文章假设训练过程中微小的偏差可以忽略不计，并让重要性采样对样本分布的纠正作用由小变大，即β线性的从0开始增长，直到训练接近结束才收敛到1，达到对分布变化的完全补偿。注意参数β的变化与确定样本概率的参数α是联动的，效果就是优先采样对比均匀采样的比例越来越大，同时重要性采样对由此带来的概率分布改变的校正也越来越强势。

水平所限，难免有误。如有纰漏敬请指出，不胜感激。

扫描二维码关注微信，接收最新推送