Why replay memory store old states and action rather than Q-value (Deep Q-learning)

Question

Here is the algorithm use in Google's DeepMind Atari paper

The replay memory D store transition (old_state, action performed, reward, new_state)

The old_state and the performed action a are needed to compute the Q-value of this action in this state. But since we already compute the Q-value of action a in state old_state in order to choose a as the best action, why don't we simply store directly the Q-value ?

Answer 1

But since we already compute the Q-value of action a in state old_state in order to choose a as the best action, why don't we simply store directly the Q-value ?

That is because calculating a relevant TD Target e.g. $R + \gamma \text{max}_{a'}Q(S', a')$ requires the current target policy estimates for action value $Q$. The action value at the time of making the step can be out of date for two reasons:

1. The estimates have changed due to other updates, since the experience was stored

2. The target policy has changed due to other updates, since the experience was stored

Storing the $Q$ value at the time the experience was made should still work to some degree, provided you don't keep the experience for so long that the values are radically different. However, it will usually be a lot less efficient, as updates will be biased towards older less accurate values.

There is a similar, but less damaging, effect from the experience replay table even with $Q$ recalculations. That is because the distribution of experience may not match what the current policy generates - something that most function approximators (e.g. neural networks used in DQN) are sensitive to. However, there are other factors in play here too, and it can be beneficial to train on a deliberately different distribution of experience - for instance prioritising experiences with larger update steps can speed learning and keeping older experiences available can reduce instances of catastrophic forgetting.

Note that if you were using an off-policy Monte Carlo method, you could store the Monte Carlo return in the experience replay table, since it does not bootstrap by using current value estimates. However, the early parts of older less relevant trajectories would stop contributing to updates in that case once the target policy had changed significantly during learning.