强化学习(十一) Prioritized Replay DQN 强化学习（十）Double DQN (DDQN)
在强化学习（十）Double DQN (DDQN)中，咱们讲到了DDQN使用两个Q网络，用当前Q网络计算最大Q值对应的动做，用目标Q网络计算这个最大动做对应的目标Q值，进而消除贪婪法带来的误差。今天咱们在DDQN的基础上，对经验回放部分的逻辑作优化。对应的算法是Prioritized Replay DQN。html
本章内容主要参考了ICML 2016的deep RL tutorial和Prioritized Replay DQN的论文<Prioritized Experience Replay>(ICLR 2016)。node
1. Prioritized Replay DQN以前算法的问题
在Prioritized Replay DQN以前，咱们已经讨论了不少种DQN，好比Nature DQN， DDQN等，他们都是经过经验回放来采样，进而作目标Q值的计算的。在采样的时候，咱们是一视同仁，在经验回放池里面的全部的样本都有相同的被采样到的几率。git
可是注意到在经验回放池里面的不一样的样本因为TD偏差的不一样，对咱们反向传播的做用是不同的。TD偏差越大，那么对咱们反向传播的做用越大。而TD偏差小的样本，因为TD偏差小，对反向梯度的计算影响不大。在Q网络中，TD偏差就是目标Q网络计算的目标Q值和当前Q网络计算的Q值之间的差距。github
这样若是TD偏差的绝对值$|\delta(t)|$较大的样本更容易被采样，则咱们的算法会比较容易收敛。下面咱们看看Prioritized Replay DQN的算法思路。算法
2. Prioritized Replay DQN算法的建模
Prioritized Replay DQN根据每一个样本的TD偏差绝对值$|\delta(t)|$，给定该样本的优先级正比于$|\delta(t)|$，将这个优先级的值存入经验回放池。回忆下以前的DQN算法，咱们仅仅只保存和环境交互获得的样本状态，动做，奖励等数据，没有优先级这个说法。网络
因为引入了经验回放的优先级，那么Prioritized Replay DQN的经验回放池和以前的其余DQN算法的经验回放池就不同了。由于这个优先级大小会影响它被采样的几率。在实际使用中，咱们一般使用SumTree这样的二叉树结构来作咱们的带优先级的经验回放池样本的存储。数据结构
具体的SumTree树结构以下图：dom
全部的经验回放样本只保存在最下面的叶子节点上面，一个节点一个样本。内部节点不保存样本数据。而叶子节点除了保存数据之外，还要保存该样本的优先级，就是图中的显示的数字。对于内部节点每一个节点只保存本身的儿子节点的优先级值之和，如图中内部节点上显示的数字。函数
这样保存有什么好处呢？主要是方便采样。以上面的树结构为例，根节点是42，若是要采样一个样本，那么咱们能够在[0,42]之间作均匀采样，采样到哪一个区间，就是哪一个样本。好比咱们采样到了26， 在（25-29）这个区间，那么就是第四个叶子节点被采样到。而注意到第三个叶子节点优先级最高，是12，它的区间13-25也是最长的，会比其余节点更容易被采样到。oop
若是要采样两个样本，咱们能够在[0,21],[21,42]两个区间作均匀采样，方法和上面采样一个样本相似。
相似的采样算法思想咱们在word2vec原理(三) 基于Negative Sampling的模型第四节中也有讲到。
除了经验回放池，如今咱们的Q网络的算法损失函数也有优化，以前咱们的损失函数是：$$\frac{1}{m}\sum\limits_{j=1}^m(y_j-Q(\phi(S_j),A_j,w))^2$$
如今咱们新的考虑了样本优先级的损失函数是$$\frac{1}{m}\sum\limits_{j=1}^mw_j(y_j-Q(\phi(S_j),A_j,w))^2$$
其中$w_j$是第j个样本的优先级权重，由TD偏差$|\delta(t)|$归一化获得。
第三个要注意的点就是当咱们对Q网络参数进行了梯度更新后，须要从新计算TD偏差，并将TD偏差更新到SunTree上面。
除了以上三个部分，Prioritized Replay DQN和DDQN的算法流程相同。
3. Prioritized Replay DQN算法流程
下面咱们总结下Prioritized Replay DQN的算法流程，基于上一节的DDQN，所以这个算法咱们应该叫作Prioritized Replay DDQN。主流程参考论文<Prioritized Experience Replay>(ICLR 2016)。
算法输入：迭代轮数$T$，状态特征维度$n$, 动做集$A$, 步长$\alpha$，采样权重系数$\beta$，衰减因子$\gamma$, 探索率$\epsilon$, 当前Q网络$Q$，目标Q网络$Q'$, 批量梯度降低的样本数$m$,目标Q网络参数更新频率$C$, SumTree的叶子节点数$S$。
输出：Q网络参数。
1. 随机初始化全部的状态和动做对应的价值$Q$. 随机初始化当前Q网络的全部参数$w$,初始化目标Q网络$Q'$的参数$w' = w$。初始化经验回放SumTree的默认数据结构，全部SumTree的S个叶子节点的优先级$p_j$为1。
2. for i from 1 to T，进行迭代。
a) 初始化S为当前状态序列的第一个状态, 拿到其特征向量$\phi(S)$
b) 在Q网络中使用$\phi(S)$做为输入，获得Q网络的全部动做对应的Q值输出。用$\epsilon-$贪婪法在当前Q值输出中选择对应的动做$A$
c) 在状态$S$执行当前动做$A$,获得新状态$S'$对应的特征向量$\phi(S')$和奖励$R$,是否终止状态is_end
d) 将$\{\phi(S),A,R,\phi(S'),is\_end\}$这个五元组存入SumTree
e) $S=S'$
f) 从SumTree中采样$m$个样本$\{\phi(S_j),A_j,R_j,\phi(S'_j),is\_end_j\}, j=1,2.,,,m$，每一个样本被采样的几率基于$P(j) = \frac{p_j}{\sum\limits_i(p_i)}$，损失函数权重$w_j = (N*P(j))^{-\beta}/\max_i(w_i)$，计算当前目标Q值$y_j$：$$y_j= \begin{cases} R_j& {is\_end_j\; is \;true}\\ R_j + \gamma Q'(\phi(S'_j),\arg\max_{a'}Q(\phi(S'_j),a,w),w')& {is\_end_j\; is \;false} \end{cases}$$
g) 使用均方差损失函数$\frac{1}{m}\sum\limits_{j=1}^mw_j(y_j-Q(\phi(S_j),A_j,w))^2$，经过神经网络的梯度反向传播来更新Q网络的全部参数$w$
h) 从新计算全部样本的TD偏差$\delta_j = y_j- Q(\phi(S_j),A_j,w)$，更新SumTree中全部节点的优先级$p_j = |\delta_j|$
i) 若是T%C=1,则更新目标Q网络参数$w'=w$
j) 若是$S'$是终止状态，当前轮迭代完毕，不然转到步骤b)
注意，上述第二步的f步和g步的Q值计算也都须要经过Q网络计算获得。另外，实际应用中，为了算法较好的收敛，探索率$\epsilon$须要随着迭代的进行而变小。
4. Prioritized Replay DDQN算法流程
下面咱们给出Prioritized Replay DDQN算法的实例代码。仍然使用了OpenAI Gym中的CartPole-v0游戏来做为咱们算法应用。CartPole-v0游戏的介绍参见这里。它比较简单，基本要求就是控制下面的cart移动使链接在上面的pole保持垂直不倒。这个任务只有两个离散动做，要么向左用力，要么向右用力。而state状态就是这个cart的位置和速度， pole的角度和角速度，4维的特征。坚持到200分的奖励则为过关。
完整的代码参见个人github: https://github.com/ljpzzz/machinelearning/blob/master/reinforcement-learning/ddqn_prioritised_replay.py， 代码中的SumTree的结构和经验回放池的结构参考了morvanzhou的github代码。
这里重点讲下和第三节中算法描述不一样的地方，主要是$w_j$的计算。注意到：$$w_j = \frac{ (N*P(j))^{-\beta}}{\max_i(w_i)} = \frac{ (N*P(j))^{-\beta}}{\max_i((N*P(i))^{-\beta})} = \frac{ (P(j))^{-\beta}}{\max_i((P(i))^{-\beta})} =( \frac{p_j}{\min_iP(i)})^{-\beta}$$
所以代码里面$w_j$，即ISWeights的计算代码是这样的：
def sample(self, n): b_idx, b_memory, ISWeights = np.empty((n,), dtype=np.int32), np.empty((n, self.tree.data[0].size)), np.empty((n, 1)) pri_seg = self.tree.total_p / n # priority segment self.beta = np.min([1., self.beta + self.beta_increment_per_sampling]) # max = 1 min_prob = np.min(self.tree.tree[-self.tree.capacity:]) / self.tree.total_p # for later calculate ISweight if min_prob == 0: min_prob = 0.00001 for i in range(n): a, b = pri_seg * i, pri_seg * (i + 1) v = np.random.uniform(a, b) idx, p, data = self.tree.get_leaf(v) prob = p / self.tree.total_p ISWeights[i, 0] = np.power(prob/min_prob, -self.beta) b_idx[i], b_memory[i, :] = idx, data return b_idx, b_memory, ISWeights
上述代码的采样在第二节已经讲到。根据树的优先级的和total_p和采样数n，将要采样的区间划分为n段，每段来进行均匀采样，根据采样到的值落到的区间，决定被采样到的叶子节点。当咱们拿到第i段的均匀采样值v之后，就能够去SumTree中找对应的叶子节点拿样本数据，样本叶子节点序号以及样本优先级了。代码以下：
def get_leaf(self, v): """ Tree structure and array storage: Tree index: 0 -> storing priority sum / \ 1 2 / \ / \ 3 4 5 6 -> storing priority for transitions Array type for storing: [0,1,2,3,4,5,6] """ parent_idx = 0 while True: # the while loop is faster than the method in the reference code cl_idx = 2 * parent_idx + 1 # this leaf's left and right kids cr_idx = cl_idx + 1 if cl_idx >= len(self.tree): # reach bottom, end search leaf_idx = parent_idx break else: # downward search, always search for a higher priority node if v <= self.tree[cl_idx]: parent_idx = cl_idx else: v -= self.tree[cl_idx] parent_idx = cr_idx data_idx = leaf_idx - self.capacity + 1 return leaf_idx, self.tree[leaf_idx], self.data[data_idx]
除了采样部分，要注意的就是当梯度更新完毕后，咱们要去更新SumTree的权重，代码以下，注意叶子节点的权重更新后，要向上回溯，更新全部祖先节点的权重。
self.memory.batch_update(tree_idx, abs_errors) # update priority
def batch_update(self, tree_idx, abs_errors): abs_errors += self.epsilon # convert to abs and avoid 0 clipped_errors = np.minimum(abs_errors, self.abs_err_upper) ps = np.power(clipped_errors, self.alpha) for ti, p in zip(tree_idx, ps): self.tree.update(ti, p)
def update(self, tree_idx, p): change = p - self.tree[tree_idx] self.tree[tree_idx] = p # then propagate the change through tree while tree_idx != 0: # this method is faster than the recursive loop in the reference code tree_idx = (tree_idx - 1) // 2 self.tree[tree_idx] += change
除了上面这部分的区别，和DDQN比，TensorFlow的网络结构流程中多了一个TD偏差的计算节点，以及损失函数多了一个ISWeights系数。此外，区别不大。
5. Prioritized Replay DQN小结
Prioritized Replay DQN和DDQN相比，收敛速度有了很大的提升，避免了一些没有价值的迭代，所以是一个不错的优化点。同时它也能够直接集成DDQN算法，因此是一个比较经常使用的DQN算法。
下一篇咱们讨论DQN家族的另外一个优化算法Duel DQN，它将价值Q分解为两部分，第一部分是仅仅受状态但不受动做影响的部分，第二部分才是同时受状态和动做影响的部分，算法的效果也很好。
（欢迎转载，转载请注明出处。欢迎沟通交流： liujianping-ok@163.com）