# Why experience replay requires off-policy algorithm?

In the paper introducing DQN "Playing Atari with Deep Reinforcement Learning", it mentioned:

Note that when learning by experience replay, it is necessary to learn off-policy (because our current parameters are different to those used to generate the sample), which motivates the choice of Q-learning.

I didn't quite understand what it means. What if we use SARSA and remember the action a' for the action we are to take in s' in our memory, and then sample batches from it and update Q like we did in DQN? And, can actor-critic methods (A3C, for specific) use experience replay? If not, why?

The on-policy methods, like SARSA, expects that the actions in every state are chosen based on the current policy of the agent, that usually tends to exploit rewards.

Doing so, the policy gets better when we update our policy based on the last rewards. Here in particular, they update the parameters of the NN that predicts the value of a certain state/action).

But, if we update our policy based on stored transitions, like in experience replay, we are actually evaluating actions from a policy that is no longer the current one, since it evolved in time, thus making it no longer on-policy.

The Q values are evaluated based on the future rewards that you will get from a state following the current agent policy.

However, that is no longer true since you are now following a different policy. So they use a common off-policy method that explores based on an epsilon-greedy approach.

• Thank you, but I still don't understand this: if I use TD(0) update rule, remembered a transition (s, a, r, s'), and draw this experience out for replaying; Now suppose my current policy says you should take a' on s', then I mark Q(s, a) should be r + Q(s', a') and do gradient descent. I think I'm doing experience replaying on-policy. Is there problem with the process? – DarkZero Mar 3 '17 at 3:47
• I believe that the problem is that, since you are now using a different policy than before, and that action is chosen using the old policy, you can't really say that it is on policy: to evaluate correcty the Q value of a policy you should do many actions with that same one. Here you try to evaluate a current policy using an action that that policy could not choose. – dante Mar 3 '17 at 18:41
• So can I say that I'm doing it off-policy here? What will be the result of doing so, in theory? – DarkZero Mar 4 '17 at 2:58
• So if I get you right, one should either use off-policy methods like Q-learning, always choose the max Q to be the future expected reward. It does not matter what the current action is, because it is a property of Q learning that if you always choose the max Q for future then Q will converge to Q under optimal policy; Or he should frankly follow one policy, choose every action including the future ones via this policy, and do on-policy update. Is that right? – DarkZero Mar 5 '17 at 2:29
• Till now, I cannot understand why on-policy methods are good. Off-policy methods seems to have more freedom and it can discover the optimal policy by itself. Would you mind also answering stats.stackexchange.com/questions/265354/… ? Thank you very much for all the discussions. – DarkZero Mar 5 '17 at 2:34

David Silver addresses this in this video lecture at 46:10 http://videolectures.net/rldm2015_silver_reinforcement_learning/: Experience replay chooses $a$ from $s$ using the policy prevailing at the time, and this is one of its advantages - it allows the Q function to learn from previous policies, which breaks up the correlation of recent states and policies and prevents the network from getting "locked in" to a certain behaviour mode.

TL;DR: It isn't necessary to have an off-policy method when using experience replay, but it makes your life a lot easier.

When following a given policy $$\pi$$, an on-policy method (for value function estimation) estimates $$V^\pi$$ or $$Q^\pi$$ (respectively), whereas an off-policy method estimates $$V^*$$ or $$Q^*$$.

The off-policy case is desirable because it guarantees that the estimate of $$V^*$$ or $$Q^*$$ will keep getting more accurate even if the policy being followed changes, i.e., following $$\pi_1$$ will yield $$V^*$$, following $$\pi_2$$ will yield $$V^*$$ and randomly choosing between $$\pi_1$$ and $$\pi_2$$ for each step will still yield $$V^*$$. (If all state-action pairs are seen often enough, ofc.)

In the on-policy case, however, following $$\pi_1$$ will yield $$V^{\pi_1}$$, following $$\pi_2$$ will yield $$V^{\pi_2}$$ and randomly choosing between the two policies at each step will yield something that is not immediately obvious - at least to me.

In experience replay, the replay buffer is an amalgamation of experiences gathered by the agent following different policies $$\pi_1, \dots, \pi_n$$ at different times from which a random subset is drawn and used to improve the function approximation in a batch RL / supervised learning style.

Off-policy methods won't have a problem with this; they will happily take the samples and improve the estimate of $$V^*$$.

However, as we can see from the above, this scenario is very much not ideal for on-policy methods. The policy represented by $$V$$ or $$Q$$ will be a (random) combination of the policies in the replay buffer, and who knows if that policy is at least as good as the previous policy. If it isn't we can't guarantee an improvement once we act $$\epsilon$$-greedy on it.

Saving and using the $$(s_t, a_t, r_{t+1})$$-sequence, as you suggest, is being done by algorithms like A3C or PPO. You actually have to do this for on-policy methods, because they won't converge to $$V^\pi$$ or $$Q^\pi$$ otherwise. The problem here isn't if on-policy methods will converge when using experience replay, but rather what it is that they converge to, and if that what is still an improvement over the previous iteration.

One way of addressing this problem is to stick to off-policy methods; another is to use on-policy methods, a rolling replay buffer (to "keep the experience fresh"), and carefully tuning parameters (making very small steps). Essentially, we aim to make sure that the $$V^\pi$$ or $$Q^\pi$$ we actually learn is close enough to $$V^{\pi_n}$$ or $$Q^{\pi_n}$$ (from the latest iteration's $$\pi_n$$) so that we can guarantee an improvement when acting greedily wrt. $$V^\pi$$ or $$Q^\pi$$.