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}} $$


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


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

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 :)


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.