Why is sampling non-uniformly from the replay memory an issue? (Prioritized experience replay)

Question

I can't seem to understand why we need importance sampling in prioritized experience replay (PER). The authors of the paper write on page 5:

The estimation of the expected value with stochastic updates relies on those updates corresponding to the same distribution as its expectation. Prioritized replay introduces bias because it changes this distribution in an uncontrolled fashion, and therefore changes the solution that the estimates will converge to (even if the policy and state distribution are fixed).

My understanding of this statement is that sampling non-uniformly from the replay memory is an issue.

So, my question is: Since we are working 1-step off-policy, why is it an issue? I thought that in an off-policy setting we don't care how transitions are sampled (at least in the 1-step case).

The one possibility for an issue that came to my mind is that in the particular case of PER, we are sampling transitions according to the errors and rewards, which does seem a little fishy.

A somewhat related question was asked here, but I don't think it answers my question.

Answer 1

The problem is not that we need importance sampling because the learning is off-policy -- you are correct in that for one step off-policy algorithms such as $Q$-learning we don't need importance sampling, see e.g. here for an explanation why. The reason we need the importance sampling is due to the loss used to train the network.

In the original DQN paper, the loss is defined as $$L_i(\theta_a) = \mathbb{E}_{(s,a,r,s') \sim \mbox{U}(D)} \left[ \left( r + \gamma \max_{a'} Q(s',a' ; \theta_i^-) - Q(s,a;\theta_i) \right)^2 \right ]\;.$$ You can see here the expectation over the loss is taken according to a uniform distribution over the replayed buffer $D$. If we started randomly sampling non-uniformly, as is the case in PER, then the expectation wouldn't be satisfied and would introduce bias. Importance sampling is used to correct this bias. Note that the main reason that we sample uniformly at random is that gradient descent usually assumes that the data is i.i.d. You can argue that in an RL problem the data will never be fully i.i.d, but you can probably tell that sampling uniformly at random from a large buffer of experience is 'closer' to being i.i.d, whereas using a priority without importance sampling will likely lead to non-i.i.d. data (e.g. there is probably high correlation between experience that has high TD error, if the priority is chosen according to this).

Note that in the paper they mention that the bias isn't as much of an issue at the start of learning and hence they use a decaying $\beta$ that only makes the importance sampling weights the 'correct' weights to use at the end of learning - this means that the estimate of the loss is asymptotically unbiased.