Which kind of prioritized experience replay should I use?

Question

The Prioritized Experience Replay paper gives two different ways of sampling from the replay buffer. One, called "proportional prioritization", assigns each transition a priority proportional to its TD-error. $$p_i = |\delta_i|+\epsilon$$

The other, called "rank-based prioritization", assigns each transition a priority inversely proportional to its rank. $$p_i = 1/\text{rank}(i)$$ where $\text{rank}(i)$ is the rank of transition $i$ when the replay buffer is sorted according to $|\delta_i|$.

The paper goes on to show that the two methods give similar performance for certain problems.
Are there times when I should choose one sampling method over the other?

Answer 1

The authors of that paper hypothesized that rank-based prioritization would be more robust to outliers. They suggested that rank-based sampling would be preferred for this reason. However, as they noted later, the fact that DQN clips rewards anyways weakens this argument.

If you're going to use someone else's ready-made code for your prioritized experience replay, then you'll probably end up using proportional sampling. Every implementation I've been able to find, including OpenAI's baselines implementation, uses proportional sampling. If you were going to write your own, proportional sampling might be preferred for being simpler to implement (so less error-prone).

Comparing these two sampling methods is complicated by the fact that rank-based sampling involves a hyperparameter that determines how often you sort your replay buffer. The authors of the original PER paper only sorted every $n$ timesteps, giving the nice amortized time of $O(\log n)$, where $n$ is the size of the replay buffer. Sampling takes constant time, so sampling a minibatch of size $k$ takes $O(k)$ time.

Proportional sampling doesn't involve sorting, but it does need to maintain a sum tree structure, which takes $O(\log n)$ time each time we add to the buffer. Sampling also takes $O(\log n)$ time, so sampling a minibatch of size $k$ takes $O(k\log n)$ time.

If we only sort our replay buffer every $n$ timesteps, then rank-based sampling is faster. However, because the buffer is almost always only approximately sorted, the distribution we sample from is only a rough estimate of the distribution we wanted. It's not clear that this estimation would be accurate enough to be performant when the replay buffer is scaled up in size past the $n=10^6$ transitions used in the paper. I haven't seen a study that compares performance for different frequencies of sorting and different buffer sizes.

So, rank-based sampling might be faster, but it also might not work as well. Adjustment of the sorting frequency hyperparameter might be necessary. The simpler and surer approach would be to use proportional sampling with clipped TD-errors.

Answer 2

It appears that the rank based method would be slightly better in terms of time complexity because you sort only once for k number of sampling operations. This article (not mine) explains in detail clearly. https://towardsdatascience.com/how-to-implement-prioritized-experience-replay-for-a-deep-q-network-a710beecd77b