Prioritized Experience Replay — part 1/4

Cleaned-text code points [0, 15323). Bibliography omitted here; source.md includes it.

# Prioritized Experience Replay

###### Abstract

Experience replay lets online reinforcement learning agents remember and reuse experiences from the past. In prior work, experience transitions were uniformly sampled from a replay memory. However, this approach simply replays transitions at the same frequency that they were originally experienced, regardless of their significance. In this paper we develop a framework for prioritizing experience, so as to replay important transitions more frequently, and therefore learn more efficiently. We use prioritized experience replay in Deep Q-Networks (DQN), a reinforcement learning algorithm that achieved human-level performance across many Atari games. DQN with prioritized experience replay achieves a new state-of-the-art, outperforming DQN with uniform replay on 41 out of 49 games.

## 1 Introduction

Online reinforcement learning (RL) agents incrementally update their parameters (of the policy, value function or model) while they observe a stream of experience. In their simplest form, they discard incoming data immediately, after a single update. Two issues with this are (a) strongly correlated updates that break the i.i.d. assumption of many popular stochastic gradient-based algorithms, and (b) the rapid forgetting of possibly rare experiences that would be useful later on.

Experience replay ( Lin, 1992 ) addresses both of these issues: with experience stored in a replay memory, it becomes possible to break the temporal correlations by mixing more and less recent experience for the updates, and rare experience will be used for more than just a single update. This was demonstrated in the Deep Q-Network (DQN) algorithm ( Mnih et al., 2013 ; Mnih et al., 2015 ) , which stabilized the training of a value function, represented by a deep neural network, by using experience replay. Specifically, DQN used a large sliding window replay memory, sampled from it uniformly at random, and revisited each transition 1 1 1 A transition is the atomic unit of interaction in RL, in our case a tuple of (state S t − 1 S_{t-1} , action A t − 1 A_{t-1} , reward R t R_{t} , discount γ t \gamma_{t} , next state S t S_{t} ). We choose this for simplicity, but most of the arguments in this paper also hold for a coarser ways of chunking experience, e.g. into sequences or episodes. eight times on average. In general, experience replay can reduce the amount of experience required to learn, and replace it with more computation and more memory – which are often cheaper resources than the RL agent’s interactions with its environment.

In this paper, we investigate how prioritizing which transitions are replayed can make experience replay more efficient and effective than if all transitions are replayed uniformly. The key idea is that an RL agent can learn more effectively from some transitions than from others. Transitions may be more or less surprising, redundant, or task-relevant. Some transitions may not be immediately useful to the agent, but might become so when the agent competence increases ( Schmidhuber, 1991 ) . Experience replay liberates online learning agents from processing transitions in the exact order they are experienced. Prioritized replay further liberates agents from considering transitions with the same frequency that they are experienced.

In particular, we propose to more frequently replay transitions with high expected learning progress, as measured by the magnitude of their temporal-difference (TD) error. This prioritization can lead to a loss of diversity, which we alleviate with stochastic prioritization, and introduce bias, which we correct with importance sampling. Our resulting algorithms are robust and scalable, which we demonstrate on the Atari 2600 benchmark suite, where we obtain faster learning and state-of-the-art performance.

## 2 Background

Numerous neuroscience studies have identified evidence of experience replay in the hippocampus of rodents, suggesting that sequences of prior experience are replayed, either during awake resting or sleep. Sequences associated with rewards appear to be replayed more frequently ( Atherton et al., 2015 ; Ólafsdóttir et al., 2015 ; Foster & Wilson, 2006 ) . Experiences with high magnitude TD error also appear to be replayed more often ( Singer & Frank, 2009 ; McNamara et al., 2014 ) .

It is well-known that planning algorithms such as value iteration can be made more efficient by prioritizing updates in an appropriate order. Prioritized sweeping ( Moore & Atkeson, 1993 ; Andre et al., 1998 ) selects which state to update next, prioritized according to the change in value, if that update was executed. The TD error provides one way to measure these priorities ( van Seijen & Sutton, 2013 ) . Our approach uses a similar prioritization method, but for model-free RL rather than model-based planning. Furthermore, we use a stochastic prioritization that is more robust when learning a function approximator from samples.

TD-errors have also been used as a prioritization mechanism for determining where to focus resources, for example when choosing where to explore ( White et al., 2014 ) or which features to select ( Geramifard et al., 2011 ; Sun et al., 2011 ) .

In supervised learning, there are numerous techniques to deal with imbalanced datasets when class identities are known, including re-sampling, under-sampling and over-sampling techniques, possibly combined with ensemble methods ( Galar et al., 2012 , for a review, see) . A recent paper introduced a form of re-sampling in the context of deep RL with experience replay ( Narasimhan et al., 2015 ) ; the method separates experience into two buckets, one for positive and one for negative rewards, and then picks a fixed fraction from each to replay. This is only applicable in domains that (unlike ours) have a natural notion of ‘positive/negative’ experience. Furthermore, Hinton (2007) introduced a form of non-uniform sampling based on error, with an importance sampling correction, which led to a 3x speed-up on MNIST digit classification.

There have been several proposed methods for playing Atari with deep reinforcement learning, including deep Q-networks (DQN) ( Mnih et al., 2013 ; Mnih et al., 2015 ; Guo et al., 2014 ; Stadie et al., 2015 ; Nair et al., 2015 ; Bellemare et al., 2016 ) , and the Double DQN algorithm ( van Hasselt et al., 2016 ) , which is the current published state-of-the-art. Simultaneously with our work, an architectural innovation that separates advantages from the value function (see the co-submission by Wang et al., 2015 ) has also led to substantial improvements on the Atari benchmark.

## 3 Prioritized Replay

Using a replay memory leads to design choices at two levels: which experiences to store, and which experiences to replay (and how to do so). This paper addresses only the latter: making the most effective use of the replay memory for learning, assuming that its contents are outside of our control (but see also Section 6 ).

### 3.1 A Motivating Example

To understand the potential gains of prioritization, we introduce an artificial ‘Blind Cliffwalk’ environment (described in Figure 1 , left) that exemplifies the challenge of exploration when rewards are rare. With only n n states, the environment requires an exponential number of random steps until the first non-zero reward; to be precise, the chance that a random sequence of actions will lead to the reward is 2 − n 2^{-n} . Furthermore, the most relevant transitions (from rare successes) are hidden in a mass of highly redundant failure cases (similar to a bipedal robot falling over repeatedly, before it discovers how to walk).

We use this example to highlight the difference between the learning times of two agents. Both agents perform Q-learning updates on transitions drawn from the same replay memory. The first agent replays transitions uniformly at random, while the second agent invokes an oracle to prioritize transitions. This oracle greedily selects the transition that maximally reduces the global loss in its current state (in hindsight, after the parameter update). For the details of the setup, see Appendix B.1 . Figure 1 (right) shows that picking the transitions in a good order can lead to exponential speed-ups over uniform choice. Such an oracle is of course not realistic, yet the large gap motivates our search for a practical approach that improves on uniform random replay.

### 3.2 Prioritizing with TD-error

The central component of prioritized replay is the criterion by which the importance of each transition is measured. One idealised criterion would be the amount the RL agent can learn from a transition in its current state (expected learning progress). While this measure is not directly accessible, a reasonable proxy is the magnitude of a transition’s TD error δ \delta , which indicates how ‘surprising’ or unexpected the transition is: specifically, how far the value is from its next-step bootstrap estimate ( Andre et al., 1998 ) . This is particularly suitable for incremental, online RL algorithms, such as SARSA or Q-learning, that already compute the TD-error and update the parameters in proportion to δ \delta . The TD-error can be a poor estimate in some circumstances as well, e.g. when rewards are noisy; see Appendix A for a discussion of alternatives.

To demonstrate the potential effectiveness of prioritizing replay by TD error, we compare the uniform and oracle baselines in the Blind Cliffwalk to a ‘greedy TD-error prioritization’ algorithm. This algorithm stores the last encountered TD error along with each transition in the replay memory. The transition with the largest absolute TD error is replayed from the memory. A Q-learning update is applied to this transition, which updates the weights in proportion to the TD error. New transitions arrive without a known TD-error, so we put them at maximal priority in order to guarantee that all experience is seen at least once. Figure 2 (left), shows that this algorithm results in a substantial reduction in the effort required to solve the Blind Cliffwalk task. 2 2 2 Note that a random (or optimistic) initialization of the Q-values is necessary with greedy prioritization. If initializing with zero instead, unrewarded transitions would appear to have zero error initially, be placed at the bottom of the queue, and not be revisited until the error on other transitions drops below numerical precision.

Implementation : To scale to large memory sizes N N , we use a binary heap data structure for the priority queue, for which finding the maximum priority transition when sampling is O ⁡ ( 1 ) O(1) and updating priorities (with the new TD-error after a learning step) is O ⁡ ( log ⁡ N ) O(\log N) . See Appendix B.2.1 for more details.

### 3.3 Stochastic Prioritization

However, greedy TD-error prioritization has several issues. First, to avoid expensive sweeps over the entire replay memory, TD errors are only updated for the transitions that are replayed. One consequence is that transitions that have a low TD error on first visit may not be replayed for a long time (which means effectively never with a sliding window replay memory). Further, it is sensitive to noise spikes (e.g. when rewards are stochastic), which can be exacerbated by bootstrapping, where approximation errors appear as another source of noise. Finally, greedy prioritization focuses on a small subset of the experience: errors shrink slowly, especially when using function approximation, meaning that the initially high error transitions get replayed frequently. This lack of diversity that makes the system prone to over-fitting.

To overcome these issues, we introduce a stochastic sampling method that interpolates between pure greedy prioritization and uniform random sampling. We ensure that the probability of being sampled is monotonic in a transition’s priority, while guaranteeing a non-zero probability even for the lowest-priority transition. Concretely, we define the probability of sampling transition i i as P ⁡ ( i ) = p i α ∑ k p k α P(i)=\frac{p_{i}^{\alpha}}{\sum_{k}p_{k}^{\alpha}} (1) where p i > 0 p_{i}>0 is the priority of transition i i . The exponent α \alpha determines how much prioritization is used, with α = 0 \alpha=0 corresponding to the uniform case.

The first variant we consider is the direct, proportional prioritization where p i = | δ i | + ϵ p_{i}=|\delta_{i}|+\epsilon , where ϵ \epsilon is a small positive constant that prevents the edge-case of transitions not being revisited once their error is zero. The second variant is an indirect, rank-based prioritization where p i = 1 rank ⁡ ( i ) p_{i}=\frac{1}{\operatorname{rank}(i)} , where rank ⁡ ( i ) \operatorname{rank}(i) is the rank of transition i i when the replay memory is sorted according to | δ i | |\delta_{i}| . In this case, P P becomes a power-law distribution with exponent α \alpha . Both distributions are monotonic in | δ | |\delta| , but the latter is likely to be more robust, as it is insensitive to outliers. Both variants of stochastic prioritization lead to large speed-ups over the uniform baseline on the Cliffwalk task, as shown on Figure 2 (right).

Implementation : To efficiently sample from distribution ( 1 ), the complexity cannot depend on N N . For the rank-based variant, we can approximate the cumulative density function with a piecewise linear function with k k segments of equal probability. The segment boundaries can be precomputed (they change only when N N or α \alpha change). At runtime, we sample a segment, and then sample uniformly among the transitions within it. This works particularly well in conjunction with a minibatch-based learning algorithm: choose k k to be the size of the minibatch, and sample exactly one transition from each segment – this is a form of stratified sampling that has the added advantage of balancing out the minibatch (there will always be exactly one transition with high magnitude δ \delta , one with medium magnitude, etc). The proportional variant is different, also admits an efficient implementation based on a ‘sum-tree’ data structure (where every node is the sum of its children, with the priorities as the leaf nodes), which can be efficiently updated and sampled from. See Appendix B.2.1 for more additional details.

### 3.4 Annealing the Bias

The estimation of the expected value with stochastic updates relies on those updates corresponding to the same distribution as its expectation. Prioritized replay introduces bias because it changes this distribution in an uncontrolled fashion, and therefore changes the solution that the estimates will converge to (even if the policy and state distribution are fixed). We can correct this bias by using importance-sampling (IS) weights w i = ( 1 N ⋅ 1 P ⁡ ( i ) ) β w_{i}=\left(\frac{1}{N}\cdot\frac{1}{P(i)}\right)^{\beta} that fully compensates for the non-uniform probabilities P ⁡ ( i ) P(i) if β = 1 \beta=1 . These weights can be folded into the Q-learning update by using w i ​ δ i w_{i}\delta_{i} instead of δ i \delta_{i} (this is thus weighted IS, not ordinary IS, see e.g. Mahmood et al., 2014 ). For stability reasons, we always normalize weights by 1 / max i ⁡ w i 1/\max_{i}w_{i} so that they only scale the update downwards.