# Prioritized Replay: How does the rank-based prioritization work out?

In the paper Prioritized Experience Replay, the authors introduced a rank-based way to compute the priority of a transition. They said:

For the rank-based variant, we can approximate the cumulative density function with a piecewise linear function with $$k$$ segments of equal probability. The segment boundaries can be precomputed (they change only when $$N$$ or $$α$$ change).

I don't very understand what they were trying to convey in this sentence: where does the cumulative density function come from?

I have a simple thought about the rank-based implementation based on what I can extract from the paper-- not so sure if it approaches what the authors talked about.

We set the range of a segment in inverse proportion to the priorities of transitions in it. For example, if one segment has the average priority of $$p$$ and another has $$2p$$, then the range of the first is two times more than that of the second.

There is an obvious deficiency in this method: I just assumed the priorities are uniformly distributed, things will be more tricky if they're not. For now, however, I cannot get any further.

I'm surprised that the words "cumulative density function" made it into this paper. They don't mean anything. I think they probably meant "probability mass function" (PMF).

In the paper, the probability of sampling transition $$i$$ from the replay buffer is $$P(i) = \frac{p_i^\alpha}{\sum_k p_k^\alpha}$$ where $$p_i$$ is the priority of transition $$i$$. With rank-based prioritization, $$p_i = 1/\text{rank}(i)$$, where $$\text{rank}(i)$$ is the rank of transition $$i$$ when the replay buffer is sorted by its TD-error $$|\delta_i|$$.

This is actually the zipf distribution. Be careful not to confuse this with the zeta distribution. The distinction is actually very important. We have a finite number of samples in the replay buffer, so the restricted support of $$i=1,\dots,N$$ is appropriate. Also, $$\alpha$$ is not restricted to values less than 1.

It looks something like this. In order to sample from (approximately) this distribution, the authors suggested finding ranges of $$i$$ such that the sum of $$P(i)$$ over each of these ranges is equal. By uniformly sampling the range and then uniformly sampling $$i$$ from within that range, you can approximate sampling from $$P(i)$$.

• Thank you for answering. But how do we compute $rank(i)$ in the rank-based variant? – Maybe May 5 '19 at 9:33
• Good question. By sorting the replay buffer by the TD error. I'll edit to add. – Philip Raeisghasem May 5 '19 at 9:38
• If we take the TD error as the rank, how can we precompute the segment boundaries as I cited in the question? – Maybe May 5 '19 at 9:51
• I think I answered that in my last paragraph. For more specifics, you can look at my implementation. – Philip Raeisghasem May 5 '19 at 10:02
• Hi, thanks. It seems to me that $rank(i)$ here is the index of its position in a sorted array, do I understand it right? – Maybe May 5 '19 at 11:50