PRIORITIZED EXPERIENCE REPLAY
ICLR 2016
经验回放使得 online reinforcement learning agent 能够记住并且回放过去的经验。在先前的工作中，从回放记忆中随机的采样 experience transitions。但是，这种方法简单的在同一频率 回放 transitions，而不管其意义。本文提出了一种方法能够实现优先回放，能够更加高频的回放重要的 transitions，从而实现更加高校的学习。我们在 DQN 上使用优先经验回放，取得了更加有效的结果。
online RL agent 当观察到一系列的经验时，增量的更新其参数。最简单的形式，即：在更新之后，他们立刻扔掉到来的数据。这种做法有两个问题：
a. 强烈的相关更新操作破坏了许多流行的 基于随机梯度的算法；
b. 快速的忘记可能稀缺的经验，但是后面可能还要用得上这个经验。
Experience Replay 解决了上述问题：在一个 回放单元中存储 experience，通过混合或多或少的最近的经验来更新就有可能破坏 temporal correlation，rare experience 将会被用来不止一次更新。这就被用在 NIPS2013 和 Nature 2015的论文中，特别地，DQN 利用一个大的滑动窗口回放单元，随机的从中均匀采样，平均重复访问一个 transition 8次。总的来讲，experience replay 可以大量的降低需要去学习的经验，而是用更多的计算和更多的memory来替换--- which are often cheaper resources than the RL agent's interactions with its environment.
注： a transition 是 agent在环境中的一次交互的原子操作，即：$ (state S_{t-1}, action A_{t-1}, reward R_t, discount t, next state S_t)$.
Prioritized Replay
1. A Motivating Example
设计这么一个优先回放功能，涉及到两个层次，即：选择哪些进行存储，另外就是选择哪些进行回放？本文主要是研究后者的，如何最有效的利用回放功能进行学习？
如上图所示，本文给出了一个例子来充分的说明优先的潜在好处。引入了称为“Blind Cliffwalk”的环境，来示例说明当奖赏非常 rare的时候，探索所遇到的挑战。假设仅有 n 个状态，这个环境就要求足够的随机步骤知道得到第一个非零奖励；确切的讲，随机的选择动作序列就会有 $2^{-n}$的概率才能得到第一个非零奖赏。此外，最相关的 transitions 却藏在大量的失败的尝试当中。
本文利用这个例子来 highlight 两个 agents的学习次数的不同。可以看到这两个 agent 都从同一个 回放单元中去获取Q-learning的更新，第一个agent 随机均匀的回放 transitions，第二个唤醒一个 oracle 来进行优先转移。这个 oracle 贪婪的选择使得在当前状态下最大化的降低全局损失的 transitions。从上图右侧的图可以看出，按照一定优化序列得到的转移 比 随机均匀采样要花费很少的尝试步骤，这明显的提升了训练的速度。
2. Prioritizing TD-Error
优先回放的一个中心成分是评判优先的准则：衡量每一个转移 transitions 的重要性。一个理想的标准是当前状态下，RL agent 能够学习到的量，也就是期望的学习过程。但是这个标准并不能直接访问到，一个比较合理的代理，能够表示重要性的另一个衡量是：一个 transitions 的 TD error $\delta$ 的规模，来表示该转移的惊奇度 或者 出乎意料的程度：How far the value is from its next-step bootstrap estimation. 这非常适合增量的，在线 RL 算法，比如：SARSA 或者 Q-learning，已经计算 TD-error 并且 更新和 $\delta$成比例的参数。但是有些情况下， TD-error 仍然是非常差的预测，例如：当奖励非常 noisy的时候。
为了说明通过 TD-error 优先回放的有效性，我们对比了 uniform 和 oracle baselines 在 Blind Cliffwalk 上的“贪婪 TD-error prioritization”算法。该算法存储了在回放单元中每次转移之后，最后遇到的 TD error 。将最大绝对值 TD误差的转移从 memory 中进行回放。然后对该转移进行 Q-learning的更新，更新和 TD error 的权重。新的转移到来之后，没有已知的 TD-error，所以我们将其放到最大优先级的行列，确保所有的 experience 至少回放一次。
关于这样做的好处，从下图可以看出， oracle 的做法可以极大的降低无用的尝试，加速了算法的执行速度。
3. Stochastic Priorization
然而，贪婪的 TD-error 优先 有几个问题：
首先，为了避免在整个回放单元中扫描而带来的计算代价，TD 误差仅仅更新被回放的转移。这个带来的一个后果就是：带有低 TD error的转移在第一次访问时可能很长时间不会被回放（which means effectively never with a sliding window replay memory）。
此外，对 noise spikes 非常敏感，bootstrapping 会加剧该现象，估计误差又会成为另一个噪声的来源。
最终，贪婪优先集中于 一个小的经验子集，误差收缩的很慢，特别是使用函数估计的时候，意味着初始的高误差转移被经常回放。缺乏多样性使得该系统倾向于 over-fitting。
为了解决上述问题，我们引入了一个随机采样的方法，该方法结合了 纯粹的贪婪优先 和 均匀随机采样。我们确保被采样的概率在转移优先级上是单调的，与此同时，确保最低优先级的转移的概率也是非零的。具体的，我们定义采样转移 i 的概率为：
其中，pi 是转移 i 的优先级。指数 $\alpha$ 决定了使用多少优先级，当 $\alpha$ 等于 0 的时候是均匀的情况。
第一种变体就是直接的，成比例的优先；
第二种是间接的，基于排行的优先级，pi = 1/rank(i)，其中 rank（i）是回放单元根据误差排行的转移 i 的排行。
两个分布都是随着误差单调的，但是后者更鲁棒，因为其对离群点不敏感。两个变体相对均匀的baseline来讲都是有很大优势的，如上图右侧所示。
4. Annealing The Bias
利用随机更新得来的期望值的预测依赖于这些更新，对应其期望的同样的分布。优先回放引入了误差，因为它以一种不受控的形式改变了分布，从而改变了预测会收敛到的 solution（即使 policy 和 状态分布都固定）。我们可以用下面的重要性采样权重来修正该误差：
在经典的强化学习的场景下，更新的无偏性是训练最后接近收敛最重要的部分，因为这个过程是高度非静态，由于变化的策略，状态分布和引导目标；我们假设小的偏差可以忽略。
本文将优先回放和 Double Q-learning 相结合，就是将 均匀随机采样 替换为 本文提出的 随机优先和重要性采样方法，具体算法见下图：
