8. DRL中的Q-Function

1. Replay Bufffer

回顾下之前的Q-Learning算法，不管是离线的算法还是在线的算法，他们都是纯粹使用值函数的方法。他们都是通过去直接学些Q进行训练。这类方法抛开了一个显式的policy，直接去学习Q function，使我们知道在某个特定的stte下执行某一action效果有多好；也指出了如果我们使用神经网络来进行拟合所可能出现的不收敛现象.

image.png
问题在于在Q iteration的第一步我们是要收集很多的, 这样的经验越多越好，但是在online Q iteration算法中每一次只能收集一个然后进行一个简单的梯度步，但是这不是梯度更新。
image.png
因为它不是一个梯度下降算法，因此，梯度法的收敛性在这里不适用。第二步很关键的问题是，在普通的SGD中，我们常常认为每一次拿到的数据之间都有一定的不相关性；而在第一步收集的数据中，数据通常都是非常相关的：下一步的观察数据可能和这一步非常相关。因此，梯度也会非常相关。因此，我们会尝试去使用一些手段来缓解这些问题。我们考虑解决的问题主要有两个：sequential state的强相关性，以及目标值总是在变动。
序贯样本为什么会成为痛点？让我们先考虑一个简单的拟合sin函数的问题。一般我们希望数据是iid的，而我们在sequential问题中先得到了开始的几个样本，然后逐渐得到后面几组，每得到一组我们就走一个梯度步。这样我们就很难去学习整个正弦波，而更容易在局部形成过拟合的同时，忘掉了其他样本的信息。在actor-critic算法中，可以采用一些并行学习的方法，这里Q学习也可以：使用多个独立的agent进行独立的数据收集，然后使用synchronized parallel或者asynchronous parallel的方法进行梯度更新，这样可以使得样本的相关度减轻。
另一种策略是使用replay buffer。
replay buffer中，，我们构造一个样本池,然后每次从中抽取一批样本进行梯度更新。
image.png
这样的使得样本不再具有很强的相关性了，同时我们每次可以用的样本量也从1个变成了很多个，可以使用多样本来降低梯度的方差。现在的问题是，我们如何才能采集更多的数据去覆盖到维度比较大的state空间呢？这就要求我们在Q学习的过程中，还是需要同时去不断更新buffer，同时使用一些exploration的探索策略输出一些不同的策略，然后得到样本进入样本池。
这样的算法可以归纳如下：
image.png
其中，如果缓冲区足够大的话，那么新进入数据占权重其实是很小的，很可能不会被抽到。当然这不是个问题，新进数据只是为了让样本池的支撑集更广。另外在K选择为1就已经不错了，但是如果数据获取代价比较高的话（如需要与真实物理系统打交道），更大的K有时候会产生更高的数据使用效率。由此，回放缓冲池成功解决了数据的强相关性问题，但是目标值的变动问题还是没有解决。也就是如下部分： image.png

2.目标网络（Target network）

image.png

目标网络，这里在实践之中是为了提高稳定性，整体思想上和之前使用的放回replay Buffer的Q learning算法没有什么区别，只是在执行若干步（如10000步）整个算法迭代后，就把整个网络的参数存下来称为目标网络，然后我们每次做的梯度步变成了:

image.png
这样的方法让我们的目标在一段时间内保持确定不变。当我们和当前的目标足够接近了以后再变动目标。

3. DQN

结合了上两个方法就构成了经典的DQN算法。

image.png
其中第三第四步是可以并行的。
关于第五步更新目标参数的直觉如下：
image.png
我们在第一个绿色方块更新了目标网络，此后若干个步骤，我们都将以这个目标网络为基础进行迭代，然后逐渐误差越来越大，直到下一个目标网络更新点，就形成了一个断点。这样其实对于步骤和步骤之间并不公平，有些步骤访问的延迟很高，有的步骤则很低。为了使得延迟公平化，可以使用一个类似于指数平滑的方法（随机优化中的Polyak Averaging），不再是若干步执行更新而是每一步都做一个小变动：
image.png
一般来说较为合适。

4. Online Q-learning，DQN与Fitted Q-iteration的比较

先从宏观上来开三个步骤，步骤一、数据采集（data collection）；步骤二、更新目标网络(target uupdate)；步骤三、对Q-function做回归(Q-function regression)。

image.png
其中Online Q-learning会立刻丢弃掉之前的,三个步骤会以相同的效率运行。
DQN算法的步骤一和步骤三运行效率因为有replay buffer所以是一样的，但是步骤二会慢一点。
Fitted Q-iteration而言是一个嵌套结构，第三步是第二步的内循环，而第二步是第一步的内循环，频率指数降低。

5. overestimate问题。

从前面的分析我们知道，Q function的意义是在某个状态下，我们执行了某个action，期望reward是多少。但是再DQN算法的实际运行中，我们会发现Q function再实际运行中通常都不精确，他们都是被高估了。虽然高估的确是很离谱，但是也没有妨碍DQN确实是有效的，因为再我再执行动作与的时候，只要让估计的这个差值和真实值差不多就可以让DQN很好得运行。
overestimate问题是DQN中的系统性问题，原因出在目标值中的max部分：

image.png
其中变量都是由噪音的，但是max操作会扩大化这些噪音，在这种情况下我们是关于噪音取max，可能我们找到的是若干个数中噪音最大的那个。我们的Q都是从样本轨迹里学出来的，所以都含噪音，即便接近真实的Q值，但也都是不完美的，因此我们可能得到的只是噪音最高的选项而不是真正Q最大的选项。注意到一个简单的事实：
image.png
这里如果对于某一行动Q值过大了，因为我们有了max操作，那就会过高估计了接下来行动的值，然后继续传导到后续的迭代中去。

6. Double Q-learning

Double Q-leanring的提出就是为了解决overestimate的问题。他的基本想法就是让选择动作（choose action）和评估值(evaluate value)两部分使用不同的网络：

image.png

当两个网络的噪音是独立的时候，overestimate的问题就会缓解一些。在实际的的应用中相对于标准的DQN，double Q-learning只是使用当前的网络（不是target网络）去评估action并确定我们选择哪个行动，然后使用target network去评估value。

7. Multi-step returns

我们使用Q学习，在回归中会设置训练的目标：

image.png
这个目标值来自于两个部分，一部分是当前的reward，另一部分是Q值代表的未来期望reward。如果训练还是在早期，通常Q就比较小（初始化为小的随机数），那么当前reward就会成为主要成分，Q值只是噪音。对于时间较长的情况，如果Q已经训练到比较后期了，从数值的量级上考虑，可能当前reward所占比就很小，Q值所占比较大。如果Q占比比较大，那么这个目标值可能不太好。在acor-critic算法中，我们已经提到了这样的bootstrap存在最低方差的好处，但是如果Q值不准确就会带来最大的偏差；而如果我们不使用bootstrap而直接看一条轨迹，那么将是无偏的，但是方差巨大。从而，我们介绍了一个折中的方法，就是使用N步reward后再把未来的bootstrap项加进去。转化到我们当前的问题中就是
image.png
使用N-step的好处就是当Q值不精确的情况下有更低的bias，并且通常学习效率更高，尤其是在训练初期。
但是它也带来严重的根本性问题，这样的训练只有在online训练的时候才是正确的为了解释这一问题，我们回忆我们的策略是由Q函数决定的：
image.png
我们在上面使用N步收益，估计的其实是,我们所有的transistion，对于的都是要从当前的策略而来，在N=1的时候不涉及到online transistio的问题。那么如何去处理这一问题呢？第一种做法是，直接忽略掉这个问题。在理论上这是不能接受的，但是实际中通常效果还不错。忽略能否可行，跟待解决问题本身是紧密相关的。第二种做法是切割trajectory以得到online数据。也就是说，我们可以把之前的片段拿过来，然后一步步看我们的policy是否支持这样的action，如果出现了分歧那么就直接切断：从而这个片段的前面部分是符合我们当前策略的，可以作为一个online数据使用。这样的做法当数据主要是online数据（我们需要及时淘汰旧数据）且行动空间很小（如pong弹球游戏只有上下和不动三种操作）时效果不错，而如果行动空间很大时则几乎不可能起到什么作用。此外，也可以考虑跟策略梯度法一样做重要性抽样重新加权，这样得到的估计总是无偏的，具体可以参考Munos et al. (2016)在NIPS上的文章：Safe and efficient off-policy reinforcement learning。

8. 连续空间下的Q-learning

在连续动作空间之下，我们要考虑的是如何去计算max。

image.png
第一种办法是直接做优化。在最内层循环做基于梯度的优化算法（如SGD）相对来说是比较慢的。注意到我们的行动空间通常都是比较低维的，不使用梯度信息的随机优化也许可行。最简单的方法是使用离散随机采样：
image.png
其中的action可以从类似均匀分布中采样。但是这样得到的结果是不准确的，尤其是在维度增加的情况下看起来就不像是能找到一个效果很好的解；不过有些时候，我们也不真正在乎优化求解的精度。此外，还有一些更好的方法，譬如交叉熵方法 (Cross-entropy Methods) 这样的迭代随机优化算法，或者如CMA-ES (Covariance Matrix Adaptation Evolutionary Strategies) 这样的进化算法。这些通常在不超过40维的决策问题中有效。
第二种那个办法是，我们选取一个比较容易优化的函数簇来拟合我们的Q函数。在此之前，我们适用的都是通用的神经网络来拟合Q，有些情况下我们不必要这么做。譬如在Q函数是二次函数的时候:
image.png
image.png
这种方法中我们训练一个NN,以state作为输入，然后输出,其中的和V都是向量，P是矩阵。这样的方法称为NAF (Normalized Advantage Function），它的天然特性就是：
image.png
这种办法在算法上不需要做任何改变，非常容易，而且和原来的Q学习一样高效。但是缺点就在于Q函数只能是固定的形式（如这里的二次函数），非常受限，Q函数的建模泛化能力将大大降低。
第三种方法比第二种方法更为广泛，是去新学习一个最大化器，在Lillicrap et al. (2016) 在ICLR上的一篇文章中被作为DDPG (Deep Deterministic Policy Gradient) 算法介绍。考虑到
image.png
可以想的是另外训练一个最大化器
image.png
作为最大化的算子。训练的方法是，让:
image.png
这可以使用GD算法实现，从而得到新的目标：
image.png
DDPG算法的完整算法如下：
image.png

9. 在应用上的一些建议

a. 从一些简单的可靠性高点的任务入手，先保证我们的算法实施的正确性。
b. replay buffer建议大一些
c. 算法运行效果通常需要较长时间
d. exploration程度建议开始高一些，后续慢慢降低。
e. Bellman error的梯度可能很大，适时切断过大的梯度。
f. Double Q-learning在实际中很有用并且没什么缺点
g. N-step returns的方法也很有用，但是如上文所述还是有一些问题。
h. 运行的时候随机种子需要考虑多一点。
i. 探索的程度，学习率的大小以及优化方法的选择都影响很大。