3
$\begingroup$

I've been re-reading the Playing Atari with Deep Reinforcement Learning (2013) paper. It lists three advantages of experience replay:

This approach has several advantages over standard online Q-learning [23]. First, each step of experience is potentially used in many weight updates, which allows for greater data efficiency. Second, learning directly from consecutive samples is inefficient, due to the strong correlations between the samples; randomizing the samples breaks these correlations and therefore reduces the variance of the updates. Third, when learning on-policy the current parameters determine the next data sample that the parameters are trained on. For example, if the maximizing action is to move left then the training samples will be dominated by samples from the left-hand side; if the maximizing action then switches to the right then the training distribution will also switch. It is easy to see how unwanted feedback loops may arise and the parameters could get stuck in a poor local minimum, or even diverge catastrophically [25]. By using experience replay the behavior distribution is averaged over many of its previous states, smoothing out learning and avoiding oscillations or divergence in the parameters. Note that when learning by experience replay, it is necessary to learn off-policy (because our current parameters are different to those used to generate the sample), which motivates the choice of Q-learning.

I am confused on how the second and third advantages differ. Isn't the third advantage just another case of breaking correlation?

Thank you in advance for your help!

$\endgroup$
3
$\begingroup$

Isn't the third advantage just another case of breaking correlation?

It could be viewed that way, but it is a different kind of correlation.

The second advantage is about breaking correlation due to samples being from adjacent time steps on the same trajectory. This is a more important problem when state vectors evolve slowly/incrementally per time step.

The third advantage is about breaking correlation due to samples being taken from the same policy. This is a more important problem when some actions have very similar reward and state progression independently of state, or may result in no change to state (e.g. an agent tries to move into a wall - agents getting stuck in corners due to runaway feedback of the direction being "best" is a thing you can sometimes observe whilst DQN is learning).

Both can also be a factor when an early event puts the remainder of a trajectory into a single part of the overall space, which can occur in environments where state history is important - in those cases, almost all of the time steps in a single episode could be correlated. Think of a resource management game, where expending or keeping a key resource early on in the game has a large influence on eventual success at a task. This is impacted by elements of second and third advantages - i.e. the states in the trajectory are correlated due to state of the resource throughout, and across multiple episodes the current policy might prefer expending or keeping that resource at a specific stage.

The correlations avoided by the second and third advantages typically occur over different scales of time, although that does depend strongly on the specific problem. The second advantage might be gained with a relatively small replay memory (depending on how the state evolves and lengths of episodes). The third advantage will usually require a larger memory, in order that it captures episodes with varying policies. In addition the replay memory should include exploratory actions which also help with this third issue.

$\endgroup$
  • $\begingroup$ Thanks for the nice explanation! The last paragraph about the sizes of the replay buffer helped me solidify the idea :) $\endgroup$ – seungjaeryanlee Aug 21 '18 at 0:27

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.