# What is “experience replay” and what are its benefits?

I've been reading Google's DeepMind Atari paper and I'm trying to understand the concept of "experience replay". Experience replay comes up in a lot of other reinforcement learning papers (particularly, the AlphaGo paper), so I want to understand how it works. Below are some excerpts.

First, we used a biologically inspired mechanism termed experience replay that randomizes over the data, thereby removing correlations in the observation sequence and smoothing over changes in the data distribution.

The paper then elaborates as follows:

While other stable methods exist for training neural networks in the reinforcement learning setting, such as neural fitted Q-iteration, these methods involve the repeated training of networks de novo hundreds of iterations. Consequently, these methods, unlike our algorithm, are too inefficient to be used successfully with large neural networks. We parameterize an approximate value function $$Q(s, a; \theta_i)$$ using the deep convolutional neural network shown in Fig. 1, in which $$\theta_i$$ are the parameters (that is, weights) of the Q-network at iteration $$i$$. To perform experience replay, we store the agent's experiences $$e_t = (s_t, a_t, r_t, s_{t+1})$$ at each time-step $$t$$ in a data set $$D_t = \{e_1, \dots, e_t \}$$. During learning, we apply Q-learning updates, on samples (or mini-batches) of experience $$(s, a, r, s') \sim U(D)$$, drawn uniformly at random from the pool of stored samples. The Q-learning update at iteration $$i$$ uses the following loss function:

$$L_i(\theta_i) = \mathbb{E}_{(s, a, r, s') \sim U(D)} \left[ \left(r + \gamma \max_{a'} Q(s', a'; \theta_i^-) - Q(s, a; \theta_i)\right)^2 \right]$$

What is experience replay, and what are its benefits, in laymen's terms?

The key part of the quoted text is:

To perform experience replay we store the agent's experiences $e_t = (s_t,a_t,r_t,s_{t+1})$

This means instead of running Q-learning on state/action pairs as they occur during simulation or actual experience, the system stores the data discovered for [state, action, reward, next_state] - typically in a large table. Note this does not store associated values - this is the raw data to feed into action-value calculations later.

The learning phase is then logically separate from gaining experience, and based on taking random samples from this table. You still want to interleave the two processes - acting and learning - because improving the policy will lead to different behaviour that should explore actions closer to optimal ones, and you want to learn from those. However, you can split this how you like - e.g. take one step, learn from three random prior steps etc. The Q-Learning targets when using experience replay use the same targets as the online version, so there is no new formula for that. The loss formula given is also the one you would use for DQN without experience replay. The difference is only which s, a, r, s', a' you feed into it.

In DQN, the DeepMind team also maintained two networks and switched which one was learning and which one feeding in current action-value estimates as "bootstraps". This helped with stability of the algorithm when using a non-linear function approximator. That's what the bar stands for in ${\theta}^{\overline{\space}}_i$ - it denotes the alternate frozen version of the weights.

• More efficient use of previous experience, by learning with it multiple times. This is key when gaining real-world experience is costly, you can get full use of it. The Q-learning updates are incremental and do not converge quickly, so multiple passes with the same data is beneficial, especially when there is low variance in immediate outcomes (reward, next state) given the same state, action pair.

• Better convergence behaviour when training a function approximator. Partly this is because the data is more like i.i.d. data assumed in most supervised learning convergence proofs.

• It is harder to use multi-step learning algorithms, such as Q($\lambda$), which can be tuned to give better learning curves by balancing between bias (due to bootstrapping) and variance (due to delays and randomness in long-term outcomes). Multi-step DQN with experience-replay DQN is one of the extensions explored in the paper Rainbow: Combining Improvements in Deep Reinforcement Learning.

The approach used in DQN is briefly outlined by David Silver in parts of this video lecture (around 01:17:00, but worth seeing sections before it). I recommend watching the whole series, which is a graduate level course on reinforcement learning, if you have time.

• Let's say during the training we are in one state and we take an action according to epsilon-greedy policy and you end up in another state . So you get rewards , and the next state . Here the reward can be the score of the game and the states can be the pixel patterns in the screen . And then we take the error between our function aproximator and the value we got from the greedy policy again using already frozen function approximator . But with the experience replay when optimizing the approximator we take some random state action data set . Am I right ? – Shamane Siriwardhana Nov 26 '17 at 16:40
• @ShamaneSiriwardhana: Yes I think you are right. It is the exact same data from the real trajectory, but instead of learning only from the most recent step, you save it in a big table and sample from that table (usually multiple samples, with a store of 1000s of previous steps to choose from). If you need more clarification, then maybe ask a question on the site. – Neil Slater Nov 26 '17 at 21:45
• Yeah I went through the paper again. It also says this method can improve the off policy learning also . Because in Q learning with act according to epsilon-greedy policy but update values functions according to greedy policy. So when every time step our neural net parameters get updated by mini batch statistics which is more importantly not related to exact time step statistics but what happened before this also help to uncorrelated the data . – Shamane Siriwardhana Nov 27 '17 at 4:17
• @Neil Slater, I've went through the Rainbow paper and I didn't see any special comments on using a special trick for combining experience replay and multi-step method. Also I've heard that multi-step method is originally impossible to combine with experience replay but why not just randomly pick n-consecutive experiences instead of 1 from experience replay but from the replay so that between each n-experiences, no correlations found? Isn't this multi-step experience replay? – StL Sep 26 '18 at 12:49
• @NeilSlater Why is it "harder to use multi-step learning algorithms"? What did you mean? – Gulzar Jan 31 '19 at 23:24

The algorithm (or at least a version of it, as implemented in the Coursera RL capstone project) is as follows:

1. Create a Replay "Buffer" that stores the last #buffer_size S.A.R.S. (State, Action, Reward, New State) experiences.

2. Run your agent, and let it accumulate experiences in the replay-buffer until it (the buffer) has at least #batch_size experiences.

• You can select actions according to a certain policy (e.g. soft-max for discrete action space, Gaussian for continuous, etc.) over your $$\hat{Q}(s,a ; \theta)$$ function estimator.
3. Once it reaches #batch_size, or more:

• make a copy of the function estimator ($$\hat{Q}(s,a; \theta)$$) at the current time, i.e. a copy of the weights $$\theta$$ - which you "freeze" and don't update, and use to calculate the "true" states $$\hat{Q}(s', a'; \theta)$$. Run for num_replay updates:

1. sample #batch_size experiences from the replay buffer.

2. Use the sampled experiences to preform a batched update to your function estimator (e.g. in Q-Learning where $$\hat{Q}(s,a) =$$ Neural network - update the weights of the network). Use the frozen weights as the "true" action-values function, but continue to improve the non-frozen function.

• do this until you reach a terminal state.

• don't forget to constantly append the new experiences to the Replay Buffer

4. Run for as many episodes as you need.

What I mean by "true": each experience can be thought of as a "supervised" learning duo, where you have a true value function $$Q(s,a)$$ and a function estimator $$\hat{Q}(s,a)$$. Your aim is to reduce the Value-Error, e.g. $$\sum(Q(s,a) - \hat{Q}(s,a))^2$$. Since you probably don't have access to the true action-values, you instead use a bootstrapped improved version of the last estimator, taking into account the new experience and reward given. In Q-learning, the "true" action value is $$Q(s,a) = R_{t+1} + \gamma \max_{a'}\hat{Q}(s', a'; \theta)$$ where $$R$$ is the reward and $$\gamma$$ is the discount factor.

Here's an excerpt of the code:

def agent_step(self, reward, state):
action = self.policy(state)
terminal = 0
self.replay_buffer.append(self.last_state, self.last_action, reward, terminal, state)
if self.replay_buffer.size() > self.replay_buffer.minibatch_size:
current_q = deepcopy(self.network)
for _ in range(self.num_replay):
experiences = self.replay_buffer.sample()
optimize_network(experiences, self.discount, self.optimizer, self.network, current_q, self.tau)
self.last_state = state
self.last_action = action
return action