What is "experience replay" and what are its benefits?

Question

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?

Answer 1

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.

Advantages of experience replay:

• 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.

Disadvantage of experience replay:

• 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.

Answer 2

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

Answer 3

We need a replay buffer for 2 reasons

1. Q-Learning updates are incremental and slow to converge. Multiple passes through the Q-function are needed for convergence.
2. When the input is highly correlated in a neural network, the gradient is high in one direction, causing the network to overcorrect.