What is the purpose of a replay/memory buffer in Deep Q-Learning networks?

Question

I'm trying to understand DQNs. There is one concept that I cannot really understand yet. In the book "Introduction to Reinforcement Learning" as well this tutorial online introduce the concept of a memory buffer (most of the time a Python deque) which must be filled with the following data:

$S_{t}, a_{t}, r_{t}, S_{t+1}$

where $S_{t}$ is the current state, $r_{t}$ is the reward, $S_{t+1}$ is the next status of the system given the action $a_{t}$.

Now, the buffer will be filled up to a point. Then a batch of data will be taken randomly from the buffer. A code representation can be seen here: link.

...
replay.append(exp) #H
state1 = state2
        
if len(replay) > batch_size:
    minibatch = random.sample(replay, batch_size)
    state1_batch = torch.cat([s1 for (s1,a,r,s2,d) in minibatch])
    action_batch = torch.Tensor([a for (s1,a,r,s2,d) in minibatch])
    reward_batch = torch.Tensor([r for (s1,a,r,s2,d) in minibatch])
    state2_batch = torch.cat([s2 for (s1,a,r,s2,d) in minibatch])
    done_batch = torch.Tensor([d for (s1,a,r,s2,d) in minibatch])
    Q1 = model(state1_batch)
...

The fact, that a batch is taken randomly is not intuitive for me for understanding the logic behind it. By taking the data randomly it would be very hard to figure out any possible pattern. It would be like going into a labyrinth marking the way and the directions choosen along the way. Then, after a while (an episode in our programming case), all those markings are randomly changing their direction/position.

Maybe I'm wrong with my example, but if the data is taken randomly, how can a DQN approximate a meaningful function?

UPDATE 17 October 2023

I really thanks @NeilSlater and @DeepQZero for their answers. But it seems, that probably my question was not really clear and/or lead to misinterpretations.

So I would present now an example. In many tutorials about DQN, the gymnasium (or gym) environment is going to be used. CartPole, FrozenLake and many more are simple application, where you can develop your DQN network and test it.

Let's take for instance the CartPole environment. In it you get a +1 as a reward, for every scene, in which the pole remains up within the +/- 12° range. So we can imagine to run one episode. In this episode the pole soon or later will definetly falls down leading to the end of the episode. In my tests, if my action is completely random, than an episode lasts about 20 steps, then it is over. But... it could be, that one episode is particular lucly and that pole will stay vertical for...let's say 50-60 steps (it is just an example). In other words, the sequence of actions led to a very high reward (+1 * number of steps). Which is good, because luckly or not, I got a sequence, which can be used to "solve" the next game.

But now, the problem. All those transistions are stored in one Python deque (or a long memory buffer). And now the surprise to me: one a small amount of those data taken from that buffer. Much worse, randomly. For my limited intuition capacity, this is hard to believe. Because due to the randomness of this batch, the sequence of actions played in one episode doesn't play any role anymore. And this is my question: How it is supposed to work?

Maybe I'm missing some important points here. But my thought were stronger after I read the book "Deep Reinforcement Learning" by Maxim Lapan. In the very first example, he does the following things:

1. run one episode of CartPole
2. collect action, state, new state and reward for every step
3. create a new deque for every new episode
4. take a batch of data containing only the most rewarded episodes (he used a percentile of 70%)
5. train the network
6. repeat

As you can see, he takes a batch based on the most successful episodes. That means, the sequence of actions is important. But for DQN, the batch is taken randomly as the sequence is no important anymore.

I hope, I explained my thoughts...

Answer 1

This question is asking about randomness in the data, so I will first clarify one of the comments in this question made about randomness.

---

If the data is taken randomly, how can a DQN approximate a meaningful function? It would be like going into a labyrinth marking the way and the directions chosen along the way. Then, after a while (an episode in our programming case), all those markings are randomly changing their direction/position.

This phenomenon is a fundamental consideration in the design of reinforcement learning algorithms as opposed to other learning algorithms. For example, supervised learning algorithms would learn to map states to actions solely through the state and corresponding action pairs provided in a fixed dataset. Like you mentioned, any randomness in the corresponding action will generally degrade the learning process.

In contrast, reinforcement learning algorithms do not not assume to have any knowledge of the desired actions beforehand and must learn the desired actions through interacting with the environment and receiving a reward signal and a next state signal. Consequently, randomness or variation in the actions is necessary to investigate the possible actions to see which actions will accrue the most reward; training on the data will increase the probability of taking actions that accrued more reward, and vice versa. In other words, the training process of reinforcement learning is meant to assess the data instead of imitate a fixed dataset as in supervised learning.

---

All those transitions are stored in one Python deque (or a long memory buffer). And now the surprise to me: one a small amount of those data taken from that buffer. Much worse, randomly. For my limited intuition capacity, this is hard to believe. Because due to the randomness of this batch, the sequence of actions played in one episode doesn't play any role anymore. And this is my question: How it is supposed to work?

To understand why training on sequences of actions is unnecessary, it helps to understand why it is possible to train on old data using the Q-learning update (see equation 6.8 of Sutton and Barto's book):

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\left[(R_{t+1} + \gamma \max_{a}Q(S_{t+1}, a)) - Q(S_t, A_t)\right].$$

Here, the approximate Q-function $Q(S_t, A_t)$ is being updated with the state, action, reward, next state tuples $(s, a, r, s')$. Importantly, these tuples were generated by a policy that takes random actions a small percentage of the time ($\epsilon$-greedy exploration). This policy that generates the data is the behavior policy. In contrast, the policy being learned is the policy that never explores (and only exploits) through using $\underset{a}{\max}Q(S_{t+1}, a)$ as an estimate of the return from the next state. This policy that only exploits is called the target policy that doesn't match the behavior policy of taking exploratory actions. Under certain conditions that I won't detail (e.g. reducing the exploration hyperparameter $\epsilon$), successively performing Q-learning updates is shown to converge to the optimal Q-function. Therefore, old data from previous behavior policies can be used during the Q-learning update to approximate the target policy.

The above paragraph should answer the question of why old data can be used in the buffer. Now we address the question of why the data can be sampled randomly without regard to its original sequence. In the Q-learning update presented above, only a single $(s, a, r, s')$ experience tuple is used to update a single $(s, a)$ pair of the Q-function. The Q-learning update does not need to process an entire sequence of actions in order because it only looks one time step into the future and approximates the return from all future time steps using the current Q-function, making it a one-step method or one-step update rule. This provides a great benefit over learning from sequences, as the Q-learning update can assess the best action at each individual time step. This is in contrast to training only on good episodes, since it provides much more flexibility when assigning credit to actions. For example, algorithms need to take exploratory actions in the beginning of training to find the most return. Regardless of how the remainder of the episode turns out, Q-learning can assess the goodness of a single experience tuple that took an exploratory action by determining if the sum of immediate reward and the expected return from the next state is better than the expected return from current state (via the update rule above). If so, Q-function will learn to take that action more frequently, and vice versa. In summary, Q-learning is able to assess the contribution of individual actions on a time step scale of length 1 through approximating the return from the next state, preventing it from needing to train on sequences of data.

The final question that remains is if there is any benefit to training with random data as opposed to sequentially experienced data. Taking a look at the DQN paper (see section 4, paragraph 4), the primary reason to randomly sample past data is to break correlations in the data. First, the high variance of strongly correlated experience hinders learning when using neural networks and associated optimizers. Randomizing the data makes it much closer to i.i.d. data, which generally enables much more efficient training. Second, note that the data used to train the current policy is also generated by the current policy when not using an experience replay buffer. Averaging the learning by randomly sampling data from many previous policies by using an experience replay buffer can help prevent major oscillations or even complete divergence in the learned policy (refer to the paper for a more detailed discussion).

If any of the terms used in this answer do not make sense and you cannot find a suitable reference online, please post another comment and I can update this answer.