上一章了解了投影误差后，我们可以将所有的误差、所有的措施放在一起看，分析DQN中所做的那些措施对哪些误差是有减少的。Diagnosing Bottlenecks in Deep Q-learning Algorithms 这篇论文很好的满足了我们的需求，这篇文章是真正的“重实操轻理论”，既然理论难以分析，先用实验找出问题也很好啊。
我们在意的几个问题
1.Function approximation 对收敛性的影响是什么？
结合上一章中所讲的投影算子和Bellman算子，函数近似会造成Value Error(VE)，论文中叫做投影误差，并且经过实验发现，模型容量越大，VE会越小，并且在DQN中，很少出现不收敛的情况，大概只有0.9%的实验不收敛。
2.采样误差(sampling error)和过拟合对模型的影响是什么？
Q-learning是要用样本去评估Q函数的，既然采样就会有采样误差，论文认为采样误差会导致过拟合，这个观点和第二章中experience replay的作用中所说的有些相似，当采样和训练的样本过于集中在某个状态或邻域的时候，会引起过拟合。怎么量化过拟合程度呢？论文使用了两个指标，一个是最后学习出来的模型的效果:在学习好的策略下，得到的归一化总收益。二个是学习模型迭代过程中的验证集损失(validation losses)，因为验证集损失和过拟合是存在关联关系的。
3.分布漂移(distribution shift)和moving target对模型的影响是什么？
这个问题直接对应DQN的两个措施，Target Net和experience replay。在DQN2015论文中，作者认为采样分布的变化和moving target是训练不稳定的来源之一。但令人惊奇的的是，这篇文章的实验结果表明，分布漂移和moving target与模型的性能降低无关，甚至有些漂移很大的模型表现常常很好。
4. 最好的采样分布是什么? (What is the best sampling or weighting distribution?)
既然分布漂移和性能有关，那么另一问题就是，选择什么分布是最好的，这里最好不仅包括收敛性，也包括最大化学习速率。结论同样令人惊奇，在之前的研究中认为，on-policy产生的样本要优于off-policy产生的样本，因为on-policy的采样分布漂移更小，但是这篇论文通过实验说明了on-policy产生的采样分布并不总是合适，表现最好的采样分布是high-entropy的，就是宽边界，能够覆盖尽可能广的状态。
这篇文章围绕这四个问题进行实验，总的看来，涉及到函数近似、过拟合、采样分布、moving target、分布漂移这几个因素，考虑还是比较全面的。
Preliminaries
论文在这写了些基本的符号说明，我觉得比较有意思的是作者对函数近似不保证收敛的解释，促使我去找了关于值迭代收敛的证明，受益匪浅。论文中用$\cal T$表示针对Q函数的Bellman算子。
我们首先看看动态规划的值迭代方程:
论文说Bellman backup算子$\cal T$ 在无限范数($L-\infty$)下是 $\gamma$-contraction的，可以保证收敛到不动点$Q^*$ 。我查找了一些资料，只找到了关于值函数V(s)的收敛证明，虽然也是用无穷范数下的$\gamma$-contraction证明的，但还是差点意思，知道的朋友可以不吝赐教。
表格型的值迭代是可以收敛的，$Q^{t+1}\leftarrow{\cal T }Q^t$，如果加上投影算子：$Q^{t+1}\leftarrow \Pi_\pi({\cal T }Q^t)$ 就没有保证了，作者理由是投影算子是$L-2$范数，原来在无穷范数下成立的结论不一定成立。
这里算是挖个坑，后面有空能详细讲讲就再写一章。
实验步骤
论文要验证这么多因素带来的影响，一定要控制变量，比如比较分布漂移影响时，就要去除采样误差。论文中使用了三种FQI(fitted Q-iteration)，每一种都控制了一些变化因素。三种算法如下所示：
三种算法都是Q-iteration，只不过控制了一些条件而已。其中Exact-FQI计算$\cal TQ$用的就是值函数的真实期望，因为Exact-FQI前提是已知了转移概率$p(s’|s,a)$，所以图中说的是在所有状态下去计算，就是期望。由于使用真实期望计算，因此这个算法完全消除了采样误差，我们可以用这个算法来探索分布漂移、函数近似、收敛性等指标。
既然完全不采样了，那如何比较采样分布漂移呢?论文使用的方法是在损失函数那使用采样分布加权，通过这种方法影响模型的训练，使用不同的分布得到不同的训练结果进行比较。
另外两个FQI算法更具体更简单一些，看论文即可，主要用来评价采样误差、过拟合、还有replay buffer的容量等因素的影响。
实验涉及到的采样分布列出了几种领域中常用的，Uniform、Random、Prioritized Replay、Replay、by on-Policy、by Optimal Policy。
实验用的领域模型是常见的Cliffwalk、 discretized Pendulum 、 Mountain Car等，这里没有什么特别要说的。
函数近似使用的是两层ReLu神经网络，参数(N,N)表示它的容量。
实验结果分析
论文一共做了十来个实验，详细的可以看论文的描述，我有几个比较感兴趣的实验和大家一起讨论下。
1.Function Approximation and Convergence
首先是我们最关心的函数近似对收敛性的影响，也就是我们上一章详细讲的投影误差相关的内容。这个实验使用Exact-FQI算法，在固定采样分布(均匀分布)的情况下，测试了不同容量的模型的Project $Q^*$ Error 和 FQI $Q^*$ Error。
第三章做的铺垫，就是为了这个图。Project $Q^*$ Error就是对应上一章里我们说的VE($\Pi v_\pi$ 和 $v_\pi$ 之间的距离)，FQI $Q^*$ Error对应上一章里的TD固定点 $w_{TD}$ 和 $v_\pi$ 之间的距离。
Project $Q^*$ Error反映了模型本身的近似能力，如果这个值很大，说明模型容量不够。如果模型理论上能找到的最好的点与真实值函数的距离都很大，模型最后一定是欠拟合的，不收敛。
FQI $Q^*$ Error反映的是模型使用FQI算法得到的解与真实值间的距离，上一章中说过，这点是使用Bellman算子迭代得到的不动点，它很有可能不是平面内最优的。这个误差一定大于VE。
图中用于对比的Tabular是表格型模型，完全没有误差。很明显，容量越大的模型，两个误差都越小，并且模型的效果也越好。现象很容易解释，在没有过拟合的风险(使用均匀采样加权)的情况下，模型的拟合能力变强了。
2.Sampling Error and Overfitting
这个实验比较易懂，我们固定模型，如果每次迭代使用的样本过少，那么就会引起模型的过拟合，现象就是验证集误差变大，模型效果变差。另外使用replay和early stop方法可以减缓过拟合现象。
3.Non-Stationarity(moving target and distribution shift)
这个也是我们重点关注的实验，在第二章我们讨论了Target Net和Experience replay这两个措施的作用，这里的实验更直观一些，得到的结论也和我们想象的不太一样。
首先看moving target 的影响实验。怎么控制moving target呢，论文使用$\alpha-smoothed$ Bellman backup，来控制:
每次更新不再以整个${\cal T}Q$为目标，而是加入了平滑参数$\alpha$，当$\alpha=1$时，就是”hard”更新，当$\alpha=0$时是完全不更新。试图用这种方式削弱moving target的影响，$\alpha$越小，每次更新的幅度越小，moving target的影响也就越小。
论文对比了不同容量的模型在不同平滑参数下的误差和性能，结果图如下：
在模型容量比较大的情况下，moving target基本没有影响，直接用hard更新就可以了，学习还效率更高。在模型容量小的时候（或者说问题较为困难的时候），soft更新优势更明显，可以说这种情况下moving target的影响较大。另一个角度是，当bellman error明显很大的时候，就需要减缓更新速率。
接着我们看distribution-shift带来的影响。这次实验使用Exact-FQI，在其他条件相同的情况下，替换采样分布$\mu$，并且统计每次迭代之后$\mu^t$和$\mu^{t+1}$之间差异。可以用TV散度和”loss shift”等指标来量化它。实验结果如下图：
可以看见有几个分布的偏移量一定0的，因为他们就是固定不变的。具有偏移量的只有Replay(两个)、on-policy、prioritized四个分布。在图中我们看不出偏移量和模型性能之间有什么关系，尤其是prioritized偏移量这么巨大，仍然效果很好，而偏移量为0的random、pi* 则效果较差。
从这个结果得到的结论是，分布漂移并不是影响模型性能的主要指标，虽然Replay确实相对于on-policy减小了偏移量，但是效果差异并不是很大，而且有异常点prioritized的存在。
总的来说，moving target 和 distribution-shift对于模型性能的影响不大，至少没有我们想象中那么大，起主导作用的仍然是采样误差和函数近似。
4.Sampling Distributions
既然分布偏移对性能影响不大，那么采样分布的什么特征会影响模型性能呢？这个实验是探索性的，作者猜想是分布越宽，能覆盖越多的state-action，那么模型性能就越好。换而言之，熵越高的分布，模型性能可能会越好。探索实验的结果如下：
可以看见还是有点正相关的关系。Uniform、Prioritized都属于熵高的分布，他们的效果也是排在前两个的。
总结
相信上面实验已经很清楚了，总结一下：
- 函数近似影响和采样误差导致的过拟合是占主导作用的。
- 模型容量越大，函数近似造成的影响越小；每个幕采样样本越多，过拟合影响越小。
- distribution shift 和target moving 的影响没有那么大，尤其是前者，几乎和模型性能没有关系。
- 采样分布的熵越高，覆盖的state-action越广，模型的效果似乎越好。我个人认为间接印证了第一条。
- target net 作用不大，replay buffer作用很大，但这个作用不体现在分布漂移中，而是体现在减轻过拟合的影响上。
那么我们已经差不多弄清了这些误差到底来源是什么，采取什么措施可以削弱误差的影响，最重要的是通过实验更进一步了解了target net 和replay这两个看似难解释的问题，可以说，我们前四章一直在围绕着这两个点在讨论，已经够详细了。
那么DQN的讨论可以暂时告一段落了，虽然坑还没填完…至少还会有一篇关于Double DQN和Dual DQN的文章，如果疫情逼着我在家办公时间持续到2月底的话，也许能把坑填上…
可以参考的资料
Diagnosing Bottlenecks in Deep Q-learning Algorithms
关于值迭代收敛性证明 CMU 15-781 Lecture 11:Markov Decision Processes II