Prioritized Experience Replay

Topics: Reinforcement Learning

Motivation

In online, off-policy reinforcement learning algorithms with experience replay, the common practice is to sample uniformly from the replay buffer. This poses the following issues:

• the experiences that have been in the replay buffer for a longer time get sampled more often than the new experiences. Even though uniform sampling is used, it is naturally biased towards older samples
• lots of experiences in the replay buffer could be very similar, or the model could have learned them really well, while others are not very common
  Therefore, there is a need for sampling methods that prioritize certain experiences over others, in such a way to maximize the agent's learning from the buffer.

TD Error Prioritized Replay

One method of performing prioritized replay is to sample the experiences with a larger TD error more often (1). The rationale is that, a higher TD error indicates a higher potential for the critic to learn, while a lower TD error shows that the critic already has a good approximation of the Q-value.

A naive/greedy approach is to rank the replay buffer in terms of TD error and select the top $n$ samples ($n$ being the batch size). This does not work well because the network parameters change slowly, therefore, the same experiences would be sampled repeatedly, leading to overfitting.

To overcome this issue, a stochastic sampling method is introduced. Every transition in the replay buffer is assigned a weight based on its TD error priority, and weighted sampling is performed. The method guarantees 2 elements:

• the probability of being sampled is monotonic with respect to the experience's priority/weight. In other words, the higher the priority, the higher the probability of being sampled
• all the samples have a non-zero probability, even the lowest-priority sample
  It basically alters the uniform probability distribution into a biased distribution based on the weights.

Mathematically, the probability of sampling a transition $i$ is defined as

$$P(i) = \frac{p_i^{\alpha}}{\sum_k p_k^{\alpha}}$$

where $p_i$ is the priority of transition $i$, and $\alpha$ is a hyperparameter that controls the degree of prioritization. $\alpha=0$ corresponds to the uniform sampling case.

The priority or weight is computed based on one of two variants:

• proportional prioritization where $p_i=|\delta_i|+\epsilon$
  where $\epsilon$ is a small positive constant that prevents the edge-case of zero weight once the error is zero
• rank-based prioritization where the experiences are sorted in ascending order based on the TD error and $p_i=\frac{1}{rank(i)}$

Both prioritization variants are monotonic in the TD error, but the latter is less susceptible to outliers.

Implementation Notes

The core of the algorithm is to implement the weighted sampling algorithm. The approach is to perform the cumulative sum of the weights and then sample uniformly over the range. A more efficient implementation is to use a SumTree. All the details about weighted sampling implementation are in Weighted Sampling.

(2) presents an implementation of PER for the DDPG algorithm. The same can be used for any continuous control algorithm with a replay buffer (TD3, SAC...)

References

1. T. Schaul, J. Quan, I. Antonoglou, and D. Silver, “Prioritized Experience Replay,” Feb. 25, 2016, arXiv: arXiv:1511.05952. doi: 10.48550/arXiv.1511.05952.
2. https://github.com/Jonathan-Pearce/DDPG_PER/blob/master/ddpg_per/utils.py