Dueling Network Architectures for Deep Reinforcement Learning
ICML 2016 Best Paper
摘要：本文的贡献点主要是在 DQN 网络结构上，将卷积神经网络提出的特征，分为两路走，即：the state value function 和 the state-dependent action advantage function.
这个设计的主要特色在于 generalize learning across actions without imposing any change to the underlying reinforcement learning algorithm.
本文的结果表明，这种设计结构可以当出现许多相似值的 actions 的时候，得到更好的 策略评估（policy evaluation）。
引言：文章首先开始讲解了最近的关于 Deep Learning 网络结构上的快速发展，列举了一些成功的案例。并且提到了现有的 DRL 方面的发展，主要依赖于设计新的 RL 算法，而不是新的网络结果。本文则从网络结构方面入手，提出一种新的结构和现有的 RL 算法更好的结合在一起。
传统单流程的 Q-network 与 新提出的 dueling Q-network 的示意图如下：
可以看出，本文提出的 dueling network 将后续的输出分为了两个分支，来分别预测 state-value 和 the advantages for each actions ; 绿色的输出模块执行 下面提到的公式（9），来组合这两个输出。两个网络结构都是输出每一个 action 的 Q-values 。
直观上看，the dueling architecture 可以学习到哪一个状态是有价值的 （which states are (or are not) valuable），而不必学习每一个 action 对每一个 state 的影响。这个对于那些 actions 不影响环境的状态下特别有效。为了说明这一点，我们可以考虑图2 所展示的显著性图。
这个图展示了两个不同时间步骤的 the value and advantage saliency maps。在一个时间步骤上，the value network steam 注意到 the road，特别是 the horizon，因为这个地方出现了新的车辆。他也注意到 score。 the advantage stream 另一方面不关心视觉输入，因为当没有车辆出现时，你可以随意的选择 action，而对环境几乎没有影响。但是第二个图可以看出，the advantage stram 关注到一辆车的出现，使得做出的选择十分相关。
在实验当中，我们发现这个 dueling architecture 能够更快的做出正确的反应，选择出合适的 action，当策略评价冗余或者相似的 actions 被添加到学习过程中。
Background ：
作者刚开始介绍了一些基本的 RL 方面的知识，此处简答的回顾下，具体可以参考相关 RL 教材。
state-action pair (s, a) 的 value 定义 以及 the state s 的 value 定义为：
接下来的 state-action value function (简称 Q function) 可以通过 dynamic programming 动态的计算如下：
我们定义最优的 $Q^*(s, a)$。在决定性的策略 $a = arg max Q^*(s, a')$，其服从 $V^*(s) = max_a Q^*(s, a)$。在这里，最优 Q function 也满足 Bellman equation:
我们定义另一个重要的变量， the advantage function, relating the value and Q function :
注意到，$E_{a~\pi(s)} [A^{\pi}(s, a)]$ 。直观的来讲，the value function V 评价了在特定状态 s 下状态有多好 （measures the how good it is to be in a particular state s）。The Q function, 然而，衡量了在这个状态下选择特定 action 的价值（value）。The advantage function 从 Q function 中减去了 状态的值，得到了每一个 action 重要性的相对衡量。
Deep Q-network ：
在接下来的章节中，所涉及物体的 value function 都是高维度的。为了估计他们，我们利用一个 Deep Q-network: $Q(s, a; \theta)$，参数为 $\theta$ 。为了预测这个网络，我们优化下面的第 i 次迭代损失函数序列：
其中 $\theta^-$ 代表一个固定的，单独的 target network 的参数。我们可以尝试去利用标准的 Q-learning 算法来在线的学习网络 $Q(s, a; \theta)$ 的参数。然而，这个预测（estimator）执行起来却表现的很差劲（performs poorly in pracitce）。Nature 2015 Human level control 那个文章中的一个关键的创建点是：
freeze the parameters of the target network for a fixed number of iterations while updating the online network by gradient descent.
（在用梯度下降的进行网络更新的时候，固定一定次数的网络，保存为 target network）。
这一改进，极大的改善了该算法的稳定性。特定的梯度更新为：
这个方法之所以被称为： model free 因为 states and rewards are produced by the environment.
off-policy 因为 这些状态和奖赏 are obtained with a behavior policy different from the online policy that is being learned.
另一个关键的成功之处是： experience replay 。在学习的过程当中，the agent 积累了一个数据集 $D_t = {e_1, e_2, .., e_t}$ , 其中，每一个记录 $e_t = (s_t, a_t, r_t, s_{t+1})$称为一个 episode 。 当训练 Q-network 的时候，并非仅仅使用当前的 experience 来进行学习，而是随机的从这个数据集上采样出一个 mini-batch 的数据进行更新：
所以 这个序列的损失为：
经验回放 增强了数据的有效性，主要是使得数据服从了监督学习所要求的 独立同分布的前提。
上面一个小节主要讲了 Nature 2015 Human level control via deep reinforcement learning 的主要内容。
Double Deep Q-networks:
本文中我们采用改善的 Double DQN learning algorithm。在 Q-learning 和 DQN 中，the max operator uses the same values to both select and evaluate an action.
这个就会导致 value estimates 的过估计问题 （over estimation），为了改善这个问题，DDQN 采用下面的这个目标：
DDQN 和 DQN 是一样的，不同之处在于 目标被替换掉了，伪代码见下面。
Prioritized Replay :
优先级回放的一个关键点在于： increase the replay probability of experience tuples that have a high expected learning progress (as measured via the proxy of absolutely TD-error)。
这使得学习速度上有了较大的提升，在最后的策略质量上也有较好的改善。
The Dueling Network Architecture：
作者提到说，本文新的结构的关键的 motivation 在于：对于许多状态，根本没有必要进行预测每一个 actions choice 的 value 。
将两个模块的 fc layers 组合以输出一个 Q estimates 需要非常巧妙的设计。
从 advantage $ Q^{\pi}(s, a) = V^{\pi}(s) + A^{\pi}(s, a)} $ 和 state-value V(s) 的表达式可以看出，advantage A 的期望值是为 0 的。
此外，对于一个决定性的策略，$a^* = arg max Q(s, a')$，服从 $Q(s, a^*) = V(s)$，所以 也可以推断出 $A(s, a^*) = 0$.
所以，我们就考虑图1中所展示的 dueling network：我们输出一个 fc layer，输出一个 scalar V， 另一路 输出一个 |A|维的向量。
利用 advantage 的定义，我们可以尝试去构建 the aggregating module 如下：
注意到，这个表达式适用于所有的 (s, a) instances, 也就是说，为了以矩阵形式表达公式7，我们需要复制 |A|次 这个变量 scalar V 。
但是，我们需要注意的是，$Q(s, a; \theta, \alpha, \beta)$ 仅仅是 true Q-fuction 的一个参数化估计。
此外，如果我们得出结论：V 是 state-value function 的较好的估计；或者是 A 提供了 advantage function 的一个合理的估计，都是错误的！
公式 7 是 unidentifiable （无法辨别的） in the scese that given Q we can not recover V and A uniquely.
（公式 7 是无法辨别的，从某种意义上说，给定 Q，我们无法唯一的恢复出 V 和 A）。
所以 我们对 V 加一个常数，对应的 从 A 中减掉同样的常数。这个固定的撤销操作会得到相同的 Q value。当这个公式被直接应用时，缺乏 identifiablity 的问题就会在实际问题上被放大。
为了解决 可识别性的问题，我们强迫 advantage function estimator 在选择的 action 上具有 zero advantage。也就是说，我们让网络的最后一个模块执行下面的这个映射（mapping）：
现在，对于 $ a* = arg max Q(s, a'; \theta, \alpha, \beta) = arg max A(s, a'; \theta, \alpha) $, 我们得到：
$Q(s, a*; \theta, \alpha, \beta) = V（s; \theta, \beta）$
所以， the stream V 提供了 value function 的估计， 另一路提供了 the advantage function 的一个估计。
另一个模块用 an average 代替 the max operator：
另一方面，这就失去了 V 和 A 原本的意思，因为他们现在偏离目标 一个常数，但是从另一个角度来讲，他又增强了优化的稳定性。
有了公式 9，the advantage 仅仅需要和 mean 变得一样快就行了，而不需要弥补公式 8 中最优 actions advantage 的任何改变 （instead of having to compense any change to the optimal action's advantage in equation (8)）。我们也对公式 8 做了一个 softmax version的实验，发现实验结果和公式 9 得到的类似，但是明显 公式 9 就非常简洁。所以，本文中所有的结果都是基于公式 9 进行的。
虽然公式 9 减去了均值，帮助增强了可识别性。但是并没有改变 A values 的相对排序，所以保存了任何公式 7 的性质。当执行的时候，从 advantage streams 就足够可以做出决定。
至此，本文的算法部分，就讲解完毕了，接下来就是实验部分，这里 就不讲了，感兴趣的可以参考原文。
总结：从表面上来看，貌似理解了这个过程，但是实际上，闭上眼睛想一想这整个流程，我们还是会发现有一些问题，尚未理解清楚，例如：
1. 将 Q值 分解为 V + A 这种形式，再组合在一起，到底有什么优势？ 这样训练下来，为什么 agent 会得到更多的信息？是什么使得 agent 变得聪明了，做出了更好的选择？？？
---- My Answer：
第一点，相对于传统的 single stream 的流程来说，本文的设计使得收敛速度更快。由文章的实验可知，当 action 的选择是 5个时，两个结构的训练结果相当；但是当 action 的选择增加时，dueling network 的优势就展现出来了。因为 the stream $V(s; \theta, \beta)$ 学习到了许多类似 action 的共享的一个 general 的 value。这个就比较有新引力了，因为很多控制问题，都存在这个问题。
第二点：就像文章的 convolution 部分讲的那样，dueling 结构的主要优势在于：its ability to learn the state-value function efficiently. 在这个结构中，每次更新 Q value 的时候，都会随着更新 V --- 与此对应的是，single-stream architecture 仅仅更新其中的一个 action 对应的 value，其他 action 对应的 value 保持不变。这种更加频繁的更新 value stream 的做法分配了更多的资源给 V，所以可以更好的估计 state values，而对于 temporal-difference-based methods 像 Q-learning 需要准确的 state value。这种现象主要体现在：当 action 的个数增加的时候，dueling architecture 比 single-stream 的算法更有效。
第三点：the difference between Q-values for a given state are often very small relative to the magnitude of Q.
(相对于 Q 值的量级来说，Q 值之间的差异显得非常小，而不明显，如： Q1 = 501, Q2 = 500) 。
文章中也给出了一个例子，即：在用 DDQN 算法训练完毕 Seaquest 后，平均 action gap 大约是 0.04，而 the average state value 之间却是 15. 不同尺寸的差异会导致在更新的时候带来 noise，而影响 action 的 reordering，这使得贪婪策略的更新非常频繁。本文提出的算法则对这种 noise 是鲁棒的。
Reference ：
Torch 官网上提供的关于 dueling DDQN 的一个博客：
http://torch.ch/blog/2016/04/30/dueling_dqn.html
Dueling 网络结构上比 DQN 改动的代码部分：
不知道大家还有什么疑问 ？？？
欢迎积极留言。。。一起讨论。。。 谢谢 。。。
