Deep Q-learning Algorithm

Posted on | Post modified: | In
Words count in article: 2.7k

这篇笔记用于记录自己对Deep Q-learning的理解、思考

主要参考了post from Intel

Deep Q-Learning Network

要解决什么问题？为什么要两者结合？

可以将问题的解决看成一个黑盒，深度学习解决的是一端到黑盒，而强化学习负责的就是黑盒到一端

深度学习的一大用处就是特征提取

1. 我们为什么需要深度学习？

对于Breakout游戏，如果单纯地使用RL，那么只有将灰度图设置为状态，因此状态的数量将会是巨大的，根本无法处理。而如果使用DL，就可以通过设置一个神经网络，输入灰度图，输出对应的奖励，因此能够很方便地实现RL中的reward function而不必担心维度多大。

需要注意的是，针对该游戏，仅仅使用一张灰度图是无法确定游戏所处的状态的。因为小球的弹射方向以及速度无法从一张图中得到，所以使用两个连续的灰度图，即可解决该问题。

由于我还没有实现过CNN，因此此处我决定产生一个中断，先去学习CNN。

1.1 CNN by Andrew Ng

1.1.1 Motivation

很主要的就是为了应对输入的图像规模过大，如果使用传统的全连接网络，那么根本无法处理。

所谓卷积，有两点好处

  • parameters sharing

    大大减少网络中的参数

  • sparsity of connections

    相当于输出中的一个值仅与输入中的局部值相关

    充分利用图像中的局部特征，而非通过全连接的方式使得输出受到图像中全部因素的影响

1.1.2 Calculation

一般而言，CNN的结构通常是三层结构，前两层是卷积层，最后一层是全连接层

而卷积层实际上包含两部分，卷积以及池化。这里记录一下对其中参数的思考：

  • convolution

    输入为 $H\times W \times C​$，表示共有C个通道，每个通道实际上就是一个灰度图矩阵，每个矩阵的规模为$H \times W​$

    假设filter的结构为f(filter size), s(stride), p(padding)，filter的个数为N，那么输出的规模为

    $[\frac{H - f + 2p}{s} +1] \times[ \frac{W - f + 2p}{s}+1]\times N$

    需要注意的是，其中参数的个数为$(f^{[l]} f^{[l]} n^{[l-1]}_c + 1) * c_n^{[l]}$，并且，一般而言，都使用该四元组，用于表示filter

  • pooling

    由于这只是一个提取图像中特征的方法，因此只含有初始化网络时规定的pooling矩阵的规模，这是一个超参数。

    关于pooling，Hinton提出，其意义在于突出局部的特征，而忽视其所处的具体位置。举个例子，当一只猫在图片的下面时，我们明确判断出这是猫；如果给出一张猫处于上方的图片，通过pooling，就可以抓住这个特征而忽视其所处的位置。

    但是同时，这又是不合理的。我们不仅关心这个特征的存在与否，同时还关心该特征的具体位置。

    What Hinton rightly points out is that a pooling operation throws away a lot of information about where a feature occurs. A pool over a small grid will detect a feature regardless of where in that grid that feature occurs. The reason for this is to make the detection translation-invariant (see Pooling - Ufldl)

    For example, if you want to do face recognition, it may be important to know exactly where the position of the mouth is relative to say, the nose. This can’t be done if the exact positional information is thrown away by repeated pooling operations.

2. 如何改进强化学习算法？

RL算法在使用一个非线性评估器作为Q值时，将会出现非常不稳定，甚至出现diverge的情况。这种情况出现的原因是：决策序列行为之间的关联性、Q值的小小改动可能会引起决策的巨大变动、数据分布的变动，进而导致实际Q值与估计Q值$\text{reward} + \gamma \max _\limits{a’}Q(s’, a’)​$差距过大。

为此，提出了两种机制来解决该矛盾：

  • experience replay

    通过将经验存储起来，随机采样以更新神经网络中的参数，以满足数据独立同分布的条件，避免决策之间的连带性和关联性。

  • iterative update

    迭代更新策略，周期性更新Q值，以防止关联性的产生

    实际上就是一个baseline

Deep Deterministic Policy Gradient

1. Policy Gradient

所有包含有通过对策略$\pi$设定参数$\theta$，从experience中直接学习策略的方法，统称为策略梯度方法，因此该类方法可以说是基于策略的。而同时学习策略以及值函数的方法，称为actor-critic方法，其中action表示学到的策略，critic表示学到的值函数。

PG相对基于值函数的优点是，该策略最终将会逼近一个确定策略，而不像$\epsilon-greedy$那样仍然会有$\epsilon$的可能随机选择。尽管后者可以通过在softmax中添加一个temperature，以保证随着时间的推进最终可以得到一个确定性策略，但是temperature衰减的过程很难把握，并且初值也很难选择。

基于策略的方法的一个最显而易见的好处，就是可以在初始化阶段，在策略中加入自己的知识(偏好)，以得到一个很好的起始状态。

关于PG的证明可以看这里，其中的解释非常棒，并且给出了推导出来的式子的一个直观解释。

观察该式，可以发现下面划线的项其实是一个极大似然估计，表示在给定策略下得到这条状态转移路线的可能性，之后乘以了reward值，以对策略进行更新。直观来看，可以十分确定的是$\nabla_\theta J(\theta) \sim \Epsilon (r(s, a))$，但是具体应该按照什么样的比例更新多少是未知的。而极大似然估计正是一个十分合适的比例。

In Deep Learning, a long sequence of multiplication with factors that are strongly correlated can trigger vanishing or exploding gradient easily. However, the policy gradient only sums up the gradient which breaks the curse of multiplying a long sequence of numbers.

高方差问题：对于某个问题，可能存在多个完美的policy，使得期望的奖励值达到最大。再加上这是非确定性策略问题，因此对于目前已学到的参数，可能它正在接近某个最优解，但是当探索出一条到达另外某个最优解的情况时，将会偏离当前的方向向另外一个最优解靠近，因此导致难以收敛，也就是高方差问题。

通过两个trick来解决高方差问题

  • Reward to go

    通过观察梯度更新的式子，可以发现t-1时刻的奖励竟然会与未来的t时刻的策略梯度相乘。这是不符合马克多夫性质的。因此可以将原式修改为
    $$
    \nabla_\theta J(\theta) =\cfrac{1}{N}\sum_{i=1}^N [ \sum_{t=1}^T [ \nabla_\theta\log \pi_\theta(a_{i,t}|s_{i,t}) \sum_{t’=t}^T r(s_{i,t’}, a_{i,t’}) ]]
    $$

  • Baseline

    对于后面的激励，可以使其减去一个常数，以达到减少方差并且不改变无偏性

    关于该常数的选取，在教材中有指明，可以是任意的函数、变量，只要不是a的函数即可。一般而言，对于MDP，baseline应该是关于状态的函数。下面这段话对baseline如何加快收敛的过程，作了一个直观的解释：

    In some states all actions have high values and we need a high baseline to differentiate the higher valued actions from the less highly valued ones; in other states all actions will have low values and a low baseline is appropriate.

    也正因如此，一般选择

    • 当前episode的平均reward

      $b = \frac{1}{N}\sum_{i=1}^N r(\tau)$

    • 使用一个神经网络来拟合该值

      将原式中的轨迹上奖励总和替换为$A^{\pi}(s_t, a_t) = Q^{\pi}(s_t, a_t) - V^{\pi}(s_t)$

      这个变形感觉很费解，是否会影响无偏性呢？

上述描述的算法，称之为REINFORCE-with-baseline算法，对于policy以及state-value function分别使用一个神经网络进行学习。但是它仍然不属于actor-critic算法，因为其中的baseline并没有涉及利用之后的行为状态更新当前的参数，而仅仅是加快收敛速度的作用，所以这并不能称之为批评家。

正如我们在TD方法中看到的，当批评家对参数进行单步更新的时候，这些偏差以及对状态的依赖都是有益的。

2. “CONTINUOUS CONTROL WITH DEEP REINFORCEMENT LEARNING”

拜读DDPG论文

其中给出的论文提出背景感觉非常实在有用，尤其是关于policy gradient算法发明出来的路线，1997-2011-2014，如今想来真是令人振奋。

为了解决使用非线性评估器近似Q值不稳定的问题，这里使用了DQN中的两个trick

  • replay buffer

  • soft update

    相对于DQN中在某个给定的步长范围之内更新，这里是类似于多臂赌博机中的soft update，也就是给出一个参数，只更新部分

为了提高模型的泛化能力，使得同一种网络架构能够处理多种不同的情景(不同的游戏可坑存在不同的状态，并且每个状态下的取值范围也可能有很大的波动性)，这里对数据进行了正则化。

正如模型中的第二个单词deterministic的含义，DDPG学得的是确定性策略，也就是说给定网络中的参数以及当前的状态，可以唯一确定出下一个状态。因此必须同经典的RL算法一样，平衡exploring & exploiting，论文中的做法是对确定性策略的输出加上一个噪声，以进行exploiting。

下面对算法流程进行分析

大体上是一个actor-critic框架，每个角色都由两个神经网络构成，一个是evaluation网络，一个是target网络，用于减少关联性，加快收敛速度。

对于更新式J，这里记录一下对其的理解

  • 首先看求和号后面的第二项，这是对策略求梯度，表示当前行为的变化，也就是actor这一步相对于上一步的梯度，actor只是作出这一步，而且不知道当前策略的变化将会带来的影响
  • 现在看求和号后面的第一项， 对当前的state-action function求梯度，以得知actor作出的改变究竟是好是坏

关于更新式的证明留待将来研究

0%