Prioritized Experience Replay - why to approximate the Density Function?

Question

I am reading about Prioritized Experience Replay, and can't understand the following:

On page 4, every transition can be selected from the table with its own probability. Here is the cumulative density function (if I understood correctly):

$$P(i) = \frac{p_i}{\sum_k{p_k}} $$

where:

$$p_i = \frac{1}{index In Table}$$

Aterwards, the paper says:

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). At runtime, we sample a segment, and then sample uniformly among the transitions within it.

My question is, why do we have to approximate the density if it can be achieved with the following:

1. roll a dice between 1 and N (with a dice that is exponentially more likely to roll a '1' rather than a '2', etc)
2. select an item from index according to the dice.

In c++ we have std::exponential_distribution [source] so there is no need to approximate anything. ...If we maintain our table sorted in a descending order.

Answer 1

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). At runtime, we sample a segment, and then sample uniformly among the transitions within it.

Form my point of view, according to $p_i = \frac{1}{rank(i)}$ and $P(i) = \frac{p_i}{\sum_k{p_k}}$, the rank first experience will have the highest probability $P(i)$ to be sampled to form the next mini-batch. The easier method is use Roulette Wheel Selection.

While the quote above is the same thing, approximate the cumulative density function. Suppose the mini-batch size is $k$, and the sorted experiences should be splite to $k$ segments. Constrain is that sum of $P(i)$ for all experiences in each segments should be equal. So as formed by the experience with top rank(rank 1,2,3,...) which gets high $P(i)$, the first segment may only have very few experience like 2 or 3, but the last segment may have 20, 30 or even more experience.

This works particularly well in conjunction with a minibatchbased learning algorithm: choose $k$ to be the size of the minibatch, and sample exactly one transition from each segment – this is a form of stratified sampling that has the added advantage of balancing out the minibatch.

PER will select one experience from each segment, the experience in first segment will have high probability hit on as we expected.

While I think it's same with Roulette Wheel Selection, but experience in same segment has same probability to be select in PER.

Answer 2

That's because the probablity density function might not follow an exponential curve, especially if formula is not $p=1/rank$ but is instead proportional to the amount of error. This will be a byproduct of us not keeping the array sorted, because we want to simplify our life. The curve could then look like this:

Here, area under the curve is one, but the curve is not exponential or linear or linear-horizontal.

Roll a dice from 0.0 to 1.0, which by the way has the same probability to roll 0.71 as 0.92 etc. Select an element from the array (doesn't have to be sorted!), scanning the array from left to right.

Consider array with 4 numbers: {5, 15, 25, 10}. Each represents a portion from the total sum:

|0.1|     0.3     |           0.5           |0.2|
you got to be pretty lucky to land on 0.1 (within first 10% segment)

The likelyhood of selecting an element is dependant on its "height under the curve". The taller the element, the more likely for our 0-to-1 counter to land on it.

You can't represent such "landing probability mechanism" by the "exponential dice approach" mentioned in my original question.

However, selecting by the "exponential dice" - albeit not precise might nonetheless work. The only caveat is the array's would have to be kept ordered, which is a pain in the rear. So the benefit isn't really there, just keep the array unsorted and go with the "segmented tree" aka "sum tree" approach O(logn) cost on all operations. This would allow you to avoid scanning the array left-to-right, helping you get from O(N) to O(logn) sampling performance

Now please help me with this question instead :)