Prioritized Experience Replay — part 3/4

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

This paper introduced prioritized replay, a method that can make learning from experience replay more efficient. We studied a couple of variants, devised implementations that scale to large replay memories, and found that prioritized replay speeds up learning by a factor 2 and leads to a new state-of-the-art of performance on the Atari benchmark. We laid out further variants and extensions that hold promise, namely for class-imbalanced supervised learning.

#### Acknowledgments

We thank our Deepmind colleagues, in particular Hado van Hasselt, Joseph Modayil, Nicolas Heess, Marc Bellemare, Razvan Pascanu, Dharshan Kumaran, Daan Wierstra, Arthur Guez, Charles Blundell, Alex Pritzel, Alex Graves, Balaji Lakshminarayanan, Ziyu Wang, Nando de Freitas, Remi Munos and Geoff Hinton for insightful discussions and feedback.

## Appendix A Prioritization Variants

The absolute TD-error is only one possible proxy for the ideal priority measure of expected learning progress. While it captures the scale of potential improvement, it ignores inherent stochasticity in rewards or transitions, as well as possible limitations from partial observability or FA capacity; in other words, it is problematic when there are unlearnable transitions. In that case, its derivative – which could be approximated by the difference between a transition’s current | δ | |\delta| and the | δ | |\delta| when it was last replayed 3 3 3 Of course, more robust approximations would be a function of the history of all encountered δ \delta values. In particular, one could imagine an RProp-style update ( Riedmiller, 1994 ) to priorities that increase the priority while the signs match, and reduce it whenever consecutive errors (for the same transition) differ in sign. – may be more useful. This measure is less immediately available, however, and is influenced by whatever was replayed in the meanwhile, which increases its variance. In preliminary experiments, we found it did not outperform | δ | |\delta| , but this may say more about the class of (near-deterministic) environments we investigated, than about the measure itself.

An orthogonal variant is to consider the norm of the weight-change induced by replaying a transition – this can be effective if the underlying optimizer employs adaptive step-sizes that reduce gradients in high-noise directions ( Schaul et al., 2013 ; Kingma & Ba, 2014 ) , thus placing the burden of distinguishing between learnable and unlearnable transitions on the optimizer.

It is possible to modulate prioritization by not treating positive TD-errors the same than negative ones; we can for example invoke the Anna Karenina principle ( Diamond, 1994 ) , interpreted to mean that there are many ways in which a transition can be less good than expected, but only one in which can be better, to introduce an asymmetry and prioritize positive TD-errors more than negative ones of equal magnitude, because the former are more likely to be informative. Such an asymmetry in replay frequency was also observed in rat studies ( Singer & Frank, 2009 ) . Again, our preliminary experiments with such variants were inconclusive.

The evidence from neuroscience suggest that a prioritization based on episodic return rather than expected learning progress may be useful too Atherton et al. (2015) ; Ólafsdóttir et al. (2015) ; Foster & Wilson (2006) . For this case, we could boost the replay probabilities of entire episodes, instead of transitions, or boost individual transitions by their observed return-to-go (or even their value estimates).

For the issue of preserving sufficient diversity (to prevent overfitting, premature convergence or impoverished representations), there are alternative solutions to our choice of introducing stochasticity, for example, the priorities could be modulated by a novelty measure in observation space. Nothing prevents a hybrid approach where some fraction of the elements (of each minibatch) are sampled according to one priority measure and the rest according to another one, introducing additional diversity. An orthogonal idea is to increase priorities of transitions that have not been replayed for a while, by introducing an explicit staleness bonus that guarantees that every transition is revisited from time to time, with that chance increasing at the same rate as its last-seen TD-error becomes stale. In the simple case where this bonus grows linearly with time, this can be implemented at no additional cost by subtracting a quantity proportional to the global step-count from the new priority on any update. 4 4 4 If bootstrapping is used with policy iteration, such that the target values come from separate network (as is the case for DQN), then there is a large increase in uncertainty about the priorities when the target network is updated in the outer iteration. At these points, the staleness bonus is increased in proportion to the number of individual (low-level) updates that happened in-between.

In the particular case of RL with bootstrapping from value functions, it is possible to exploit the sequential structure of the replay memory using the following intuition: a transition that led to a large amount of learning (about its outgoing state) has the potential to change the bootstrapping target for all transitions leading into that state, and thus there is more to be learned about these. Of course we know at least one of these, namely the historic predecessor transition, and so boosting its priority makes it more likely to be revisited soon. Similarly to eligibility traces, this lets information trickle backward from a future outcome to the value estimates of the actions and states that led to it. In practice, we add | δ | |\delta| of the current transition to predecessor transition’s priority, but only if the predecessor transition is not a terminal one. This idea is related to ‘reverse replay’ observed in rodents Foster & Wilson (2006) , and to a recent extension of prioritized sweeping ( van Seijen & Sutton, 2013 ) .

## Appendix B Experimental Details

### B.1 Blind Cliffwalk

For the Blind Cliffwalk experiments (Section 3.1 and following), we use a straight-forward Q-learning ( Watkins & Dayan, 1992 ) setup. The Q-values are represented using either a tabular look-up table, or a linear function approximator, in both cases represented Q ⁡ ( s , a ) := θ ⊤ ​ ϕ ​ ( s , a ) Q(s,a):=\theta^{\top}\phi(s,a) . For each transition, we compute its TD-error using: δ t \displaystyle\delta_{t} : ⁣ = \displaystyle:= R t + γ t ​ max a ⁡ Q ⁡ ( S t , a ) − Q ⁡ ( S t − 1 , A t − 1 ) \displaystyle R_{t}+\gamma_{t}\max_{a}Q(S_{t},a)-Q(S_{t-1},A_{t-1}) (2) and update the parameters using stochastic gradient ascent: θ \displaystyle\theta ← \displaystyle\leftarrow θ + η ⋅ δ t ⋅ ∇ θ Q | S t − 1 , A t − 1 = θ + η ⋅ δ t ⋅ ϕ ⁡ ( S t − 1 , A t − 1 ) \displaystyle\theta+\eta\cdot\delta_{t}\cdot\nabla_{\theta}Q\bigr|_{S_{t-1},A_{t-1}}=\theta+\eta\cdot\delta_{t}\cdot\phi(S_{t-1},A_{t-1}) (3) For the linear FA case we use a very simple encoding of state as a 1-hot vector (as for tabular), but concatenated with a constant bias feature of value 1. To make generalization across actions impossible, we alternate which action is ‘right’ and which one is ‘wrong’ for each state. All elements are initialized with small values near zero, θ i ∼ 𝒩 ⁡ ( 0 , 0.1 ) \theta_{i}\sim\mathcal{N}(0,0.1) .

We vary the size of the problem (number of states n n ) from 2 to 16. The discount factor is set to γ = 1 − 1 n \gamma=1-\frac{1}{n} which keeps values on approximately the same scale independently of n n . This allows us to used a fixed step-size of η = 1 4 \eta=\frac{1}{4} in all experiments.

The replay memory is filled by exhaustively executing all 2 n 2^{n} possible sequences of actions until termination (in random order). This guarantees that exactly one sequence will succeed and hit the final reward, and all others will fail with zero reward. The replay memory contains all the relevant experience (the total number of transitions is 2 n + 1 − 2 2^{n+1}-2 ), at the frequency that it would be encountered when acting online with a random behavior policy. Given this, we can in principle learn until convergence by just increasing the amount of computation; here, convergence is defined as a mean-squared error (MSE) between the Q-value estimates and the ground truth below 10 − 3 10^{-3} .

### B.2 Atari Experiments

#### B.2.1 Implementation Details

Prioritizing using a replay memory with N = 10 6 N=10^{6} transitions introduced some performance challenges. Here we describe a number of things we did to minimize additional run-time and memory overhead, extending the discussion in Section 3 .

##### Rank-based prioritization

Early experiments with Atari showed that maintaining a sorted data structure of 10 6 10^{6} transitions with constantly changing TD-errors dominated running time. Our final solution was to store transitions in a priority queue implemented with an array-based binary heap. The heap array was then directly used as an approximation of a sorted array, which is infrequently sorted once every 10 6 10^{6} steps to prevent the heap becoming too unbalanced. This is an unconventional use of a binary heap, however our tests on smaller environments showed learning was unaffected compared to using a perfectly sorted array. This is likely due to the last-seen TD-error only being a proxy for the usefulness of a transition and our use of stochastic prioritized sampling. A small improvement in running time came from avoiding excessive recalculation of partitions for the sampling distribution. We reused the same partition for values of N N that are close together and by updating α \alpha and β \beta infrequently. Our final implementation for rank-based prioritization produced an additional 2%-4% increase in running time and negligible additional memory usage. This could be reduced further in a number of ways, e.g. with a more efficient heap implementation, but it was good enough for our experiments.

##### Proportional prioritization

The ‘sum-tree’ data structure used here is very similar in spirit to the array representation of a binary heap. However, instead of the usual heap property, the value of a parent node is the sum of its children. Leaf nodes store the transition priorities and the internal nodes are intermediate sums, with the parent node containing the sum over all priorities, p total p_{\text{total}} . This provides a efficient way of calculating the cumulative sum of priorities, allowing O ⁡ ( log ⁡ N ) O(\log N) updates and sampling. To sample a minibatch of size k k , the range [ 0 , p total ] [0,p_{\text{total}}] is divided equally into k k ranges. Next, a value is uniformly sampled from each range. Finally the transitions that correspond to each of these sampled values are retrieved from the tree. Overhead is similar to rank-based prioritization.

As mentioned in Section 3.4 , whenever importance sampling is used, all weights w i w_{i} were scaled so that max i ⁡ w i = 1 \max_{i}w_{i}=1 . We found that this worked better in practice as it kept all weights within a reasonable range, avoiding the possibility of extremely large updates. It is worth mentioning that this normalization interacts with annealing on β \beta : as β \beta approaches 1, the normalization constant grows, which reduces the effective average update in a similar way to annealing the step-size η \eta .

#### B.2.2 Hyperparameters

Throughout this paper our baseline was DQN and the tuned version of Double DQN. We tuned hyperparameters over a subset of Atari games: Breakout, Pong, Ms. Pac-Man, Q*bert, Alien, Battlezone, Asterix. Table 2 lists the values tried and Table 3 lists the chosen parameters.

Hyperparameter Range of values α \alpha 0, 0.4, 0.5, 0.6, 0.7, 0.8 β \beta 0, 0.4, 0.5, 0.6, 1 η \eta η baseline , η baseline / 2 , η baseline / 4 , η baseline / 8 \eta_{\text{baseline}},\eta_{\text{baseline}}/2,\eta_{\text{baseline}}/4,\eta_{\text{baseline}}/8

DQN Double DQN (tuned) Hyperparameter baseline rank-based baseline rank-based proportional α \alpha (priority) 0 0.5 → 0 0.5\rightarrow 0 0 0.7 0.6 β \beta (IS) 0 0 0 0.5 → 1 0.5\rightarrow 1 0.4 → 1 0.4\rightarrow 1 η \eta (step-size) 0.00025 η baseline / 4 \eta_{\text{baseline}}/4 0.00025 η baseline / 4 \eta_{\text{baseline}}/4 η baseline / 4 \eta_{\text{baseline}}/4

#### B.2.3 Evaluation

We evaluate our agents using the human starts evaluation method described in ( van Hasselt et al., 2016 ) . Human starts evaluation uses start states sampled randomly from human traces. The test evaluation that agents periodically undergo during training uses start states that are randomized by doing a random number of no-ops at the beginning of each episode. Human starts evaluation averages the score over 100 evaluations of 30 minutes of game time. All learning curve plots show scores under the test evaluation and were generated using the same code base, with the same random seed initializations.

Table 4 and Table 5 show evaluation method differences and the ϵ \epsilon used in the ϵ \epsilon -greedy policy for each agent during evaluation. The agent evaluated with the human starts evaluation is the best agent found during training as in ( van Hasselt et al., 2016 ) .

Evaluation method Frames Emulator time Number of evaluations Agent start point Human starts 108,000 30 mins 100 human starts Test 500,000 139 mins 1 up to 30 random no-ops

DQN Double DQN (tuned) Evaluation method baseline rank-based baseline rank-based proportional Human starts 0.05 0.01 0.001 0.001 0.001 Test 0.05 0.05 0.01 0.01 0.01

Normalized score is calculated as in ( van Hasselt et al., 2016 ) : score normalized = score agent − score random | score human − score random | \text{score}_{\text{normalized}}=\frac{\text{score}_{\text{agent}}-\text{score}_{\text{random}}}{\left|\text{score}_{\text{human}}-\text{score}_{\text{random}}\right|} (4)

Note the absolute value of the denominator is taken. This only affects Video Pinball where the random score is higher than the human score. Combined with a high agent score, Video Pinball has a large effect on the mean normalized score. We continue to use this so our normalized scores are comparable.

### B.3 Class-imbalanced MNIST

#### B.3.1 Dataset Setup

In our supervised learning setting we modified MNIST to obtain a new training dataset with a significant label imbalance. This new dataset was obtained by considering a small subset of the samples that correspond to the first 5 digits (0, 1, 2, 3, 4) and all of the samples that correspond to the remaining 5 labels (5, 6, 7, 8, 9). For each of the first 5 digits we randomly sampled 1% of the available examples, i.e., 1% of the available 0s, 1% of the available 1s etc. In the resulting dataset there are examples of all 10 different classes but it is highly imbalanced since there are 100 times more examples that correspond to the 5, 6, 7, 8, 9 classes than to the 0, 1, 2, 3, 4 ones. In all our experiments we used the original MNIST test dataset without removing any samples.

The architecture of the feed-forward network used in the Prioritized Supervised Learning experiments.

#### B.3.2 Training Setup