# Which kind of prioritized experience replay should I use?

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?

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.