1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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. enter image description here

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

$\endgroup$
  • $\begingroup$ Thank you for answering. But how do we compute $rank(i)$ in the rank-based variant? $\endgroup$ – Maybe May 5 '19 at 9:33
  • $\begingroup$ Good question. By sorting the replay buffer by the TD error. I'll edit to add. $\endgroup$ – Philip Raeisghasem May 5 '19 at 9:38
  • $\begingroup$ If we take the TD error as the rank, how can we precompute the segment boundaries as I cited in the question? $\endgroup$ – Maybe May 5 '19 at 9:51
  • $\begingroup$ I think I answered that in my last paragraph. For more specifics, you can look at my implementation. $\endgroup$ – Philip Raeisghasem May 5 '19 at 10:02
  • $\begingroup$ 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? $\endgroup$ – Maybe May 5 '19 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.