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. 
 A: 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)$.
