系列论文阅读——DQN及其改进

DQN

作为DRL的开山之作，DeepMind的DQN可以说是每一个入坑深度增强学习的同学必了解的第一个算法了吧。先前，将RL和DL结合存在以下挑战：1.deep learning算法需要大量的labeled data，RL学到的reward 大都是稀疏、带噪声并且有延迟的（延迟是指action 和导致的reward之间）；2.DL假设样本独立；而RL前后state状态相关；3.DL假设分布固定，而RL在学习新的行为时，数据分布会变化。DQN通过Q-Learning使用reward来构造标签、使用经验池等方法解决了这些问题。

基于Q-learning 确定Loss Function

Q-learning 更新公式为：
$Q^∗(s,a)=Q(s,a)+α(r+\gamma \max_{a′} Q(s′,a′)−Q(s,a))$
DQN 的 loss function：
$L(\theta) = \mathbb E[targetnet- Q(s,a;\theta)]^2$
$targetnet = r + \gamma \max_{a′} Q(s′,a′;\theta)$
DQN使用随机梯度下降更新参数,为啥要把targetnet单独拎出来呢，后续会说的。

experience replay

DQN 使用exprience replay解决instablity的问题，把每个时间步agent与环境交互得到的转移样本 $(s_t,a_t,r_t,s_{t+1})$ 存储在buffer中，并被随机抽取。通过这种方式，去除了数据之前的相关性，并且缓和了数据分布的差异。

TargetNet

为了减少 $action \ values \ Q$ 和目标 $r + \gamma \max_{a'} Q(s′ , a′ )$ 之间的相关性，从而提高稳定性.2015年版的DQN加入了另一个网络—— $\hat Q$ 作为targetnet,它和 $Q$ 参数分离，每次参数更新只更新 $Q$ ，而 $\hat Q$ 的参数 $\theta'$ 保持不变,并且周期性的将 $Q$ 的参数复制给 $\hat Q$ 。此时，loss function变为：
$L(\theta) = \mathbb E[r + \gamma \max_{a′} Q(s′,a′;\theta')- Q(s,a;\theta)]^2$

DQN算法伪代码

double DQN

在标准的Q-learning,和DQN中，参数是这么更新的：
$\theta_{t+1}=\theta_t+\alpha(y_t^Q - Q(s_t,a_t;\mathbf{\theta_t}))∇_{\theta_t}Q(s_t,a_t;\mathbf{\theta_t})$
$y_t^Q = r_{t+1}+\gamma \max_a Q(s_{t+1},a;\mathbf{{\theta^-_t}})$
max操作使得估计的值函数比值函数的真实值大。如果是均匀的过估计，找到的最优策略是不会变的，不会对我们的目标造成影响。但实际上，过估计的误差在不同的states和actions下是不同的，这就会影响到我们找到最佳策略了。为了减少overestimation，van Hasselt et al.(2016)提出Double DQN(D-DQN)。利用DQN中的target network,将selection 和 evelation 解藕。使用Behavior Network选择出value最大的action，用target network来估计它的值 $y_t^Q$ 被更改为：
$y_t^{DDQN} = r_{t+1} + \gamma Q(s_{t+1},\arg\max_a(s_{t+1},a;\mathbf{\theta_t});\mathbf{\theta_t^-})$
PS 论文中有对两个数学定理的详细证明，感兴趣的同学可以看哦

Prioritized Experience Replay

在前面的方法中，experience replay都是均匀随机采样，但实际上不同样本的重要性显然是不同的。举个例子，在强化学习初期，replay memory中，除了直接和目标相关的state-action pair 有正值，大部分的value都为0，大量的从zero-value state 到另一个 zero-value state 的transitions更新导致很低效。Moore & Atkeson, 1993 提出Prioritized Sweeping，优先选择value改变了的state。具体算法如下：

prioritized sweeping

但Prioritized sweeping 主要用在model based planning。Schaul et al. (2016) 提出了Prioritized Experience Replay。

Prioritizing TD-Error
用 TD-error来规定优先学习的程度. 如果 $\delta$ 越大, 就代表我们的预测精度还有很多上升空间, 那么这个样本就越需要被学习, 也就是优先级越高。通过存储transition,及其每次回放更新得到的最新的TD-error，将TD-error绝对值最大的transition从 memory 中进行回放。然后对该transition进行Q-learning的更新，并根据TD-error,更新其优先级。而对于没有已知TD-error的新进入memory的transition，将其放到最大优先级的行列，以确保所有的经验至少被回放一次。
Stochastic Prioritization
greedy TD-error prioritization有以下问题：1.那些TD-error很小的transition 将很长时间不被replay.2.对noise spikes 敏感。最终算法会集中在一个小子集里面。初始TD-error很高的transitions会经常被重放，缺失多样性会导致over-fitting。作者提出了一种介于均匀随机采样和贪心优先之间的随机采样方法，transition $i$ 的采样概率为：
$P(i) = \frac{p^\alpha_i}{\sum_kp^\alpha_k}$
其中， $p_i$ 是 $i$ 的优先级。这样，即使是最低优先级的transition被采样到的概率也不为0. $p_i$ 的设定有多种方法。
第一种是成比例优先。 $p_i = |\delta| + \varepsilon$ . $\varepsilon$ 用来防止transitions的TD-error为0后不再被回放。具体实现中，使用名为sum-tree的树型数据结构。它的每个叶子节点保存了 transition priorities，父节点存储了孩子节点值之和，这样，头节点的值就是所有叶子结点的总和 $p_{total}$ 。采样一个大小为 $k$ 的minibatch时，range $[0,p_{total}]$ 被均分为 $k$ 个ranges，每个ranges均匀采样，这样，各种 $|\delta|$ 的transitions都有被采样到。
第二种是 $p_i = \frac{1}{rank(i)}$ 。 $rank(i)$ 是transition $i$ 根据它的 $|\delta|$ 在replay memory中的rank。这种方法对异常值更加不敏感，因此更为鲁棒。作者最终使用了基于array的二叉堆实现的优先队列来存储transitions。
Importance Sampling
Prioritized replay 改变了分布，因此引入了bias。为了消除bias，作者使用了importance-sampling(IS) weights：
$w_i = ({\frac{1}{N}} \cdot {\frac{1}{P(i)}})^ \beta$
Q-learning更新中的 $\delta_i$ 替换为 $w_i\delta_i$ ，并出于stability的原因，用 $\frac{1}{\max_iw_i}$ 将权值正则化。

Prioritized Sweeping

Dueling Network Architectures for Deep Reinforcement Learning

Wang et al. (2016b)在网络结构上做了创新，这种新的网络结构能够更容易的与当前和未来的RL算法相结合。
作者引入了advantage function。 $A^π (s, a) = Q^π (s, a) − V^ π (s).$
$Vi$ 关注的是state的值， $Ai$ 关注的是这个状态下，动作的重要性。 $Q$ 估计的是在这一状态下选择某一动作的价值。因为在某些状态下，无论做什么动作对下一个状态都没有太大影响，而这种方法，可以单独学习状态本身的价值。

dueling network architecture.png

如上图，作者将原来的DQN最后的一条全联接层一分为二，一个用来估计value functions,一个用来估计advantage function。最后将两条流聚合成输出Q function。
相应的Q function变为：

Q(s,a;\theta,\alpha,\beta) = V(s;\theta,\beta) + （A(s,a;\theta,\alpha) - \max_{a'\in{|A|}}A(s,a';\theta,\alpha)）

$\alpha$ 和 $\beta$ 是两个全联接层分支的参数，那为什么要减去 $\max_{a'\in{|A|}}A(s,a';\theta,\alpha)$ 呢。这是因为给定一个Q，我们无法给出一个唯一的V和A（拥有两个变量的一个方程式，当然有无穷多解）。为了解决这一问题，作者强制让被选择的动作的advantage为0，即 $A(s,a;\theta,\alpha) - \max_{a'\in{|A|}}A(s,a';\theta,\alpha)$ 。
这样， $a^* = arg\max_{a'}Q(s,a';\theta,\alpha,\beta) = arg\max_{a'}A(s,a';\theta,\alpha)$
$Q(s,a*,\theta,\alpha,\beta) = V(s;\theta,\beta)$
在实际应用中，作者用均值代替了最大值操作，即：
$Q(s,a;\theta,\alpha,\mathbf{\beta}) = V(s;\theta,\beta)+(A(s,a;\theta,\alpha)-\frac{1}{|A|}\sum_{a'}A(s,a';\theta,\alpha))$
这样，可以缩小 Q 值的范围，去除多余的自由度，且期望值为0,提高算法稳定性

Distributional value function

强化学习一般是对智体收到的随机return的期望进行建模，但实际上，这些随机return的分布——value distribution是非常有用的。

It’s already evident from our empirical results that the distributional perspective leads to better, more stable reinforcement learning

Bellemare et al. (2017)提出贝尔曼方程的一个变体，实际上可以预测所有可能的结果，而不用对它们进行平均 —— distributional Bellman’s equation
$Z(x,a)=R(x,a)+\gamma Z(X′,A′)$
具体算法如下：

categorical algorithm

网络结构上的改变：
传统的DQN最后一层全联接层输出的是 $N$ 维向量，表示当前状态下，每一个动作的价值的估计。Categorical DQN 输出的是 $N \times M$ 维，表示的是表示的是 N 个动作在 M 个价值分布的支撑上的概率。


  def _network_template(self, state):
    """Builds a convolutional network that outputs Q-value distributions.
    Args:
      state: `tf.Tensor`, contains the agent's current state.
    Returns:
      net: _network_type object containing the tensors output by the network.
    """
    weights_initializer = slim.variance_scaling_initializer(
        factor=1.0 / np.sqrt(3.0), mode='FAN_IN', uniform=True)

    net = tf.cast(state, tf.float32)
    net = tf.div(net, 255.)
    net = slim.conv2d(
        net, 32, [8, 8], stride=4, weights_initializer=weights_initializer)
    net = slim.conv2d(
        net, 64, [4, 4], stride=2, weights_initializer=weights_initializer)
    net = slim.conv2d(
        net, 64, [3, 3], stride=1, weights_initializer=weights_initializer)
    net = slim.flatten(net)
    net = slim.fully_connected(
        net, 512, weights_initializer=weights_initializer)
    net = slim.fully_connected(
        net,
        self.num_actions * self._num_atoms,
        activation_fn=None,
        weights_initializer=weights_initializer)

    logits = tf.reshape(net, [-1, self.num_actions, self._num_atoms])
    probabilities = tf.contrib.layers.softmax(logits)
    q_values = tf.reduce_sum(self._support * probabilities, axis=2)
    return self._get_network_type()(q_values, logits, probabilities)

orz其实这篇论文我看了代码才懂了算法流程，但是并不能完全理解，有大佬可以解释一哈吗??
未完待续

A3C

asynchronous advantage actor-critic (A3C) [Mnih et al.(2016)] (https://arxiv.org/pdf/1602.01783.pdf)并不属于value-based算法，这里提到它一是因为DeepMind 在投给AAAI 2018的论文Rainbow: Combining Improvements in Deep Reinforcement Learning
中使用了A3C中的multi-step learning。

论文中最为出彩的地方在于：在多个环境副本上并行地异步执行多个agent，不同的agent采用不同的策略，经历不同的state，有不同的transition,不但有助于探索，加快速度，而且使得时间上数据的相关性很小，起到稳定学习过程的作用。因此不需要使用又费计算又费资源的experience replay，这样就可以使用on-policy RL 方法。
算法有一个global network,和若干个agent，大概的步骤过程是：
1.agent 将global network的参数pull过来
2.agent与环境互动n-step或遇到terminal state 提前终止
3.agent计算loss，得到梯度
4.把梯度 push 给global network，用梯度更新global network的参数，然后reset自己，回到第一步

A3C, each actor-learner thread, based on Mnih et al. (2016)

Noisy DQN

Fortunato et al. (2018)提出在参数中加入噪声，代替 $\epsilon$ -greedy，增加模型的探索能力。

Noisynet

举个例子，设神经网络的一个linear layer 为：
$y = w x + b$
那么加入噪声后为：
$y = (μ^w+σ^w⊙ε^w)x+μ^b+σ^b⊙ε^b$
$ε$ 是均值为0的噪声， $μ$ 和 $σ$ 都是可学习的参数。设 $ζ$ 为 $(\mu,σ)$
有两种噪声产生方法：
a.Independent Gaussian noise：为每一个权值和偏差都设定一个独立噪声。在这种情况下，若输入x是q维、输出y是p维，那么就需要p*q+q个 $\epsilon$ ，

b. Factorised Gaussian noise:通过将 $ε^w_{i,j}$ 分解，大大减少了需要的噪声数量，只需要q+p个 $\epsilon$ 即可。
$ε^w_{i,j}$ 和 $ε^b_{j}$ 的计算公式为：
$ε^w_{i,j} = f(ε_i)f(ε_j)$
$ε^b_{j} = f(ε_j)$
这里，作者将 $f(x)$ 设为 $f(x) = sgn(x)\sqrt{|x|}$

NoisyNet 的loss function 为
$\overline L(\theta) = E(L(\xi))$
梯度为
$∇\overline L (ζ) = ∇E [L(θ)] = E [∇_{μ,σ}L(μ + σ ⊙ ε)] .$
作者使用蒙特卡洛方法近似上面的梯度，得到
$∇\overline L (ζ) \approx ∇_{μ,σ}L(μ + σ ⊙ ε)$

参考资料：
增强学习——周莫烦
 论文阅读之：PRIORITIZED EXPERIENCE REPLAY
DQN从入门到放弃
 reinforcement learning:an introduction
deep reinforcement learning:An overview
spinning up
DeepMind为明年的AAAI，准备了一份各种DQN的混血
 Going beyond average for reinforcement learning
Distributional Reinforcement Learning
深度强化学习系列之（8）----- A3C算法原理及Tensorflow实现
 一文读懂深度强化学习算法 A3C （Actor-Critic Algorithm