基于Prioritized Experience Replay优化抽样方法的经验回放机制。

Experience Replay

DQN中的经验回放机制，缓存池中的历史数据，学习时是均匀随机抽样的。
首先临近的某些数据本身就强相关，其次不同数据对梯度学习的贡献可能会不同，这些都会导致学习效率低，甚至过拟合。

prioritization

不同数据，需要有个指标，表示其被抽样的优先级。

rank-based

基于排名的优先级，以|TD-error|由大到小排名的倒数作为优先级指标。

代入到上面样本抽样分布的公式，分母是个求和，可以看作常量c，则整体抽样服从幂率分布，大致如下：

具体实现：

1. 按照学习mini-batch k的大小，将排名分成k段，利用抽样分布抽样某一段。
2. 选中某段之后，均匀抽样某条数据。

proportional

proportional prioritization：另外一种优先级经验回放方法，直接以|TD-error|作为优先级指标。
背后的直觉是误差越大，对梯度学习贡献越大，应该被优先抽样到。
一种常见的实现方式是采用sum-tree数据结构，如图：

各节点定义如下：

1. 整体是个二叉树结构，一个父节点只有两个子节点。
2. 叶子节点为每个样本的优先级指标，比如|TD-error|。
   叶子节点就是包含优先级指标的Experience Replay Buffer信息，训练数据从这里采样。
3. 中间节点为子节点优先级指标之和。
4. 根节点为所有样本优先级指标总和。

生成sum-tree的过程：

1. 叶节点即为Replay Buffer，与DQN一样，固定队列长度的循环更新，无需排序。
2. 中间节点及根节点按照上图Sum更新。
3. 注意上图中的每个叶子节点标注的括号内容表示叶子节点对应的查询区间，可知优先级大的节点，包含的区间更宽，被采样到的可能性更大。
   从这能看到sum-tree只是一种高效的数据存储结构。

具体抽样过程如下：

1. 按照学习mini-batch k的大小，将sum-tree根节点即总和分成k段，每一段均匀抽样查询优先级累计值，比如图中的24。
2. 针对每一段抽样的值，执行3~6，定位到需要采样的Experience。
3. 比如图中抽样到查询值24。
4. 左节点29大于查询值24，则沿着左节点接着遍历。
5. 29的左节点13小于查询值24，则沿着右节点16遍历，同时更新查询值11=24-13；
   注意这是一棵累加树，通过回溯的方式比较容易理解，回溯的时候，此处的查询值+13为父节点处查询值。
6. 16的左节点12大于查询值11，则最终选择优先级为12的叶子节点。

sum-tree 更新样本和采样样本的时间复杂度都是O(logn)。

importance sampling

对于梯度学习来说，每次从缓存池抽样minibatch size个数据进行学习，这些数据本身应该代表同一个分布，即最终要学习的分布。
但是引入优先级之后，这些不同的分布，和最终要学习的分布，是有偏差的，可以理解成这是一种削弱权衡，是一个实践trick，是一个需要调试的超参。
采用重要性采样方法纠错，重要性权重为：

DDQN proportional prioritization

总结

Prioritized Experience Replay是基于Experience Replay的一种off-policy学习的采样机制，尝试通过样本的抽样概率表达不同样本对梯度学习的贡献度。