Answers.Body: <p>The authors of that paper hypothesized that rank-based prioritization would be more robust to outliers. They suggested that rank-based sampling would be preferred for this reason. However, as they noted later, the fact that DQN clips rewards anyways weakens this argument.</p>
  
  <p>If you're going to use someone else's ready-made code for your prioritized experience replay, then you'll probably end up using proportional sampling. Every implementation I've been able to find, including OpenAI's <a href="https://github.com/openai/baselines/blob/master/baselines/deepq/replay_buffer.py" rel="noreferrer">baselines implementation</a>, uses proportional sampling. If you were going to write your own, proportional sampling might be preferred for being simpler to implement (so less error-prone).</p>
  
  <p>Comparing these two sampling methods is complicated by the fact that rank-based sampling involves a hyperparameter that determines how often you sort your replay buffer. The authors of the original PER paper only sorted every <span class="math-container">$n$</span> timesteps, giving the nice amortized time of <span class="math-container">$O(\log n)$</span>, where <span class="math-container">$n$</span> is the size of the replay buffer. Sampling takes constant time, so sampling a minibatch of size <span class="math-container">$k$</span> takes <span class="math-container">$O(k)$</span> time. </p>
  
  <p>Proportional sampling doesn't involve sorting, but it does need to maintain a <a href="https://www.fcodelabs.com/2019/03/18/Sum-Tree-Introduction/" rel="noreferrer">sum tree</a> structure, which takes <span class="math-container">$O(\log n)$</span> time each time we add to the buffer. Sampling also takes <span class="math-container">$O(\log n)$</span> time, so sampling a minibatch of size <span class="math-container">$k$</span> takes <span class="math-container">$O(k\log n)$</span> time. </p>
  
  <p>If we only sort our replay buffer every <span class="math-container">$n$</span> timesteps, then rank-based sampling is faster. However, because the buffer is almost always only approximately sorted, the distribution we sample from is only a rough estimate of the distribution we wanted. It's not clear that this estimation would be accurate enough to be performant when the replay buffer is scaled up in size past the <span class="math-container">$n=10^6$</span> transitions used in the paper. I haven't seen a study that compares performance for different frequencies of sorting and different buffer sizes.</p>
  
  <p>So, rank-based sampling might be faster, but it also might not work as well. Adjustment of the sorting frequency hyperparameter might be necessary. The simpler and surer approach would be to use proportional sampling with clipped TD-errors.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-05T10:05:47.557Z
Answers.LastActivityDate: 2019-05-05T10:11:18.867Z
Answers.LastEditDate: 2019-05-05T10:11:18.867Z
Answers.UserDisplayName: Philip Raeisghasem
Answers.Body: <p>It appears that the rank based method would be slightly better in terms of time complexity because you sort only once for k number of sampling operations. This article (not mine) explains in detail clearly. <a href="https://towardsdatascience.com/how-to-implement-prioritized-experience-replay-for-a-deep-q-network-a710beecd77b" rel="nofollow noreferrer">https://towardsdatascience.com/how-to-implement-prioritized-experience-replay-for-a-deep-q-network-a710beecd77b</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-26T02:06:51.080Z
Answers.LastActivityDate: 2020-11-26T02:06:51.080Z
Answers.UserDisplayName: being_aerys
Body: <p>The <a href="https://arxiv.org/pdf/1511.05952.pdf" rel="noreferrer">Prioritized Experience Replay</a> paper gives two different ways of sampling from the replay buffer. One, called "proportional prioritization", assigns each transition a priority proportional to its TD-error. 
  <span class="math-container">$$p_i = |\delta_i|+\epsilon$$</span></p>
  
  <p>The other, called "rank-based prioritization", assigns each transition a priority inversely proportional to its rank.
  <span class="math-container">$$p_i = 1/\text{rank}(i)$$</span>
  where <span class="math-container">$\text{rank}(i)$</span> is the rank of transition <span class="math-container">$i$</span> when the replay buffer is sorted according to <span class="math-container">$|\delta_i|$</span>. </p>
  
  <p>The paper goes on to show that the two methods give similar performance for certain problems.<br>
  Are there times when I should choose one sampling method over the other?</p>
  
Tags: <deep-learning><reinforcement-learning><dqn><experience-replay>
Title: Which kind of prioritized experience replay should I use?
UserDisplayName: Philip Raeisghasem
ThreadText: # Which kind of prioritized experience replay should I use?
  
  (Asked by: username_0 on 2019-05-05)
  
  The [Prioritized Experience Replay](https://arxiv.org/pdf/1511.05952.pdf) paper gives two different ways of sampling from the replay buffer. One, called "proportional prioritization", assigns each transition a priority proportional to its TD-error.
  $$p\_i = |\delta\_i|+\epsilon$$
  
  The other, called "rank-based prioritization", assigns each transition a priority inversely proportional to its rank.
  $$p\_i = 1/\text{rank}(i)$$
  where $\text{rank}(i)$ is the rank of transition $i$ when the replay buffer is sorted according to $|\delta\_i|$.
  
  The paper goes on to show that the two methods give similar performance for certain problems.  
  Are there times when I should choose one sampling method over the other?
  
  **Tags:** deep-learning, reinforcement-learning, dqn, experience-replay
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2019-05-05. Score: 6
  
  The authors of that paper hypothesized that rank-based prioritization would be more robust to outliers. They suggested that rank-based sampling would be preferred for this reason. However, as they noted later, the fact that DQN clips rewards anyways weakens this argument.
  
  If you're going to use someone else's ready-made code for your prioritized experience replay, then you'll probably end up using proportional sampling. Every implementation I've been able to find, including OpenAI's [baselines implementation](https://github.com/openai/baselines/blob/master/baselines/deepq/replay_buffer.py), uses proportional sampling. If you were going to write your own, proportional sampling might be preferred for being simpler to implement (so less error-prone).
  
  Comparing these two sampling methods is complicated by the fact that rank-based sampling involves a hyperparameter that determines how often you sort your replay buffer. The authors of the original PER paper only sorted every $n$ timesteps, giving the nice amortized time of $O(\log n)$, where $n$ is the size of the replay buffer. Sampling takes constant time, so sampling a minibatch of size $k$ takes $O(k)$ time.
  
  Proportional sampling doesn't involve sorting, but it does need to maintain a [sum tree](https://www.fcodelabs.com/2019/03/18/Sum-Tree-Introduction/) structure, which takes $O(\log n)$ time each time we add to the buffer. Sampling also takes $O(\log n)$ time, so sampling a minibatch of size $k$ takes $O(k\log n)$ time.
  
  If we only sort our replay buffer every $n$ timesteps, then rank-based sampling is faster. However, because the buffer is almost always only approximately sorted, the distribution we sample from is only a rough estimate of the distribution we wanted. It's not clear that this estimation would be accurate enough to be performant when the replay buffer is scaled up in size past the $n=10^6$ transitions used in the paper. I haven't seen a study that compares performance for different frequencies of sorting and different buffer sizes.
  
  So, rank-based sampling might be faster, but it also might not work as well. Adjustment of the sorting frequency hyperparameter might be necessary. The simpler and surer approach would be to use proportional sampling with clipped TD-errors.
  
  
  ---
  
  ### Answer by username_1 on 2020-11-26. Score: 1
  
  It appears that the rank based method would be slightly better in terms of time complexity because you sort only once for k number of sampling operations. This article (not mine) explains in detail clearly. <https://towardsdatascience.com/how-to-implement-prioritized-experience-replay-for-a-deep-q-network-a710beecd77b>
  
  
  ---
  
  