# DQN - breaking correlation between consecutive samples and random sampling

I was reading through some blogs about Deep Q-Learning (DQN), and I have 2 questions:

1- I didn't understand how breaking the correlation between consecutive samples (i.e. train the network with random samples from Replay Memory, rather than providing it with the sequential experiences as they occur) would be a better learning process for the network!! Everywhere explains this in a very high level vague explanation. What I need to understand is how this affect the Backpropogation, Gradient decent, Weights or Loss calculation so that it makes learning inefficient. Perhaps mathematically or in a more evident way. I couldn't find a source that explains how and in what way the correlation of consecutive samples would decrease learning efficiency.

2- In one of the DQN blogs, in the Wrapping up section, it explains the list of high level steps for the DQN process. What I don't understand is, after taking the first action from the initial state, I didn’t understand why we sample random batch from Replay Memory! Shouldn’t we continue from the next state where the agent ended up after taking the first action, as it is the natural progression in the game? I know Markov Property dictates that given the current state you can "ignore" all the past states and still be able to learn. But it doesn't make sense in an action/adventure/strategy real time game where the gameplay is continuous and sometimes require long term planning to end up in a better position. Say if it’s Super Mario game where the first action is a move forward. This will bring Mario closer to the first enemy Mashroom (Goomba) approaching. Shouldn’t we continue from the new state, by jumping over the enemy and then continue from there on? It doesn't make sense to suddenly sample some completely random batch state from the Replay Memory, which would make the agent end up in another part of the game, when the agent should continue progressing through the game as a human player would. I hope my question makes sense. To mention another example, the DeepMind Alphastar AI agent that played against human players in the StarCraft 2 RTS game. This agent required to continue playing from the previous sequences of states to take new actions. So I don't understand where the random sampling of completely different states from the Replay Memory would come into play here. Maybe I'm missing something.

Many thanks in advance for any clarifications.

1. question:

The necessity of breaking correlation between consecutive samples comes from theory of reinforcement learning. Q-learning algorithm when used with function approximation is known to diverge quite easily, to stop that we need to break correlation between samples. Divergence of Q-learning algorithm with function approximation is not directly connected with neural networks it can happen even with linear approximator. This is quite large topic so if you want to know more you can read chapter 9 of this book (or you can read it all if you want to know more about RL).

There is also part where neural networks learn better by providing samples that are not correlated. This was already ask and you can find few good answers here.

1. question:

Your understanding of how experience replay works is incorrect. Our agent plays the game "normally", that is sequentially. When you sample batch of experiences from experience replay you don't actually transfer your agent or your game state to the state that you sampled, you keep playing from the state where you were. We sample experiences from experience replay in order to use them for learning process. To make it more clear I will list the general steps that are used for learning from experience replay and playing the game.

1) We run some dummy moves in the environment to fill part of our experience replay buffer. For example you can run 1000 steps randomly in a game and store all the states you visited during that time in a buffer. We do that so that at the begging we have enough samples to sample from the buffer.

2) You start playing the game "for real", you make a single step in the environment, you store your transition in the buffer.

3) Now you sample a batch of transitions from experience replay, for example 32 of them and you use that to train the network. Your agent is still at the same state were it stopped at step 2) we don't move anywhere, we only sampled 32 previous transitions from the past to learn from them.

4) Now you start again from step 2), that is, we make a move in the environment, store the transition and again sample transitions to learn from like in step 3).

• Great explanation, thank you so much Brale for the step by step explanation. It helped a lot to demystify this point. So just to be clear about the training steps, when you start playing the game "for real" - the agent make a first single step/action in the environment, and store the Experience in the Replay Memory buffer. We then sample a random batch of “Experiences” from the Replay Memory buffer. Ok so when we do this: May 2, 2019 at 18:31
• 1- So we actually take the (St) state from that Experience tuple Et = (St, At, Rt+1, St+1). This is a random state sample, completely different from the one the agent is at in the game right now. But we’re just using this state sample to train the network. Correct? 2- We then pre-process this state, by doing normal grey-scale conversion, cropping, scaling ..etc. We then pass this pre-processed state to the Policy Network (CNN) as input, to forward-propagate. May 2, 2019 at 18:31
• 3- The Network outputs an estimated Q-value for each possible action from the given input state. May 2, 2019 at 18:32
• 4- The Loss is then calculated. We do this by comparing (subtracting) the Q-value output from the Network for the action in the Experience tuple we sampled in the corresponding Optimal/Target. Here, say if our action space is 4 (up, left, right, down). In the Network Output, do we choose the action with the highest Q-value or choose the action that is the same as the one we choose in the Experience tuple for that state, and then subtract the Q-value of the Output action from the Optimal Q-value in the Experience tuple? May 2, 2019 at 18:33
• My understanding is it’s the latter (i.e. choose the same action from the output as the one chosen in the Experience tuple), but just want to make sure. May 2, 2019 at 18:33

Another reason for breaking up the temporal sequence of the training data, which I have oddly never seen in the modern literature, is due to the stiffness of the continuous neural network: if you train on nearby successive states, this may significantly distort the already learned mapping across huge regions of the training data space that are quite far from the current data. This is why in the old days we used radial basis functions: new data only affected the mapping fairly locally.