18
$\begingroup$

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?

$\endgroup$
22
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Shamane Siriwardhana Nov 26 '17 at 16:40
  • 1
    $\begingroup$ @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. $\endgroup$ – Neil Slater Nov 26 '17 at 21:45
  • $\begingroup$ 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 . $\endgroup$ – Shamane Siriwardhana Nov 27 '17 at 4:17
  • $\begingroup$ @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? $\endgroup$ – StL Sep 26 '18 at 12:49
  • $\begingroup$ @NeilSlater Why is it "harder to use multi-step learning algorithms"? What did you mean? $\endgroup$ – Gulzar Jan 31 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.