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.

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.
