6
$\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 (I've taken a screenshot, since there are a lot of mathematical symbols that are difficult to reproduce):

enter image description here

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

$\endgroup$
  • 1
    $\begingroup$ Could you explain which of the symbols/terms you understand from the paper? The part "we store the agent's experiences $e_t = (s_t, a_t, r_t, s_{t+1})$ at each time step $t$" is a straightforward explanation if you know what $s_t, a_t, r_t$ stand for . . . but perhaps the whole thing would be too dense to understand if you were not aware of conventions for these symbols in RL $\endgroup$ – Neil Slater Aug 30 '18 at 19:40
3
$\begingroup$

An agent stores plans in "episodic memory". A plan is a symbolic trajectory through the game for example, “left”, “grasp”, “right”, “ungrasp”. Such experience can be generated by actions of the agent itself or by a "learning from demonstration". The later one are the stored plans of a human-operator. “Experience Replay” is the aim of using game-logs from the past to speed up the search process. It depends on the domain model, that means a plan has a semantic meaning which is domain-dependent.

Using a mathematical and/or a biological terminology to describe “experience replay” is not the best idea. In reality the concept can be understand better as a data-driven planner with heuristics. Usually the concept is borrowed from agent philosophy which has it's roots in cognitive computing better known as SOAR. A concrete realization of "experience replay" works with Dynamic movement primitives. Instead of playback the actions itself, the planner's goal is to emulate the recorded features, for example the hip-angle of an robot over time.

$\endgroup$
2
$\begingroup$

In reinforcement learning (RL), an agent interacts with an environment in time steps. At each time step $t$, the agent and the environment are in some state $s_t$. From that state $s_t$, the agent chooses and executes an action $a_t$ and the environment emits a reward $r_t$ (which values the just taken action $a_t$). Finally, the agent and the environment move to the next state, $s_{t+1}$. This interaction proceeds until either the agent dies or some other termination criterion is met.

The goal of the agent is to obtain the highest amount of reward in the long run (that is, not just in the next time step, but in all successive time steps). To do that, ideally, the agent needs to find a way of behaving "optimally". In RL, the behaviour of the agent is called a "policy". An optimal policy is a policy that allows the agent to obtain the (expected) highest amount of reward in the long run.

In this context, we can describe a full and finite (in terms of time steps) interaction between an agent and an environment as a sequence (sometimes called a "rollout" or a "trajectory") of states, actions, rewards and next states. So, a rollout might look like this $$(s_t, a_t, r_t, s_{t+1}, a_{t+1}, r_{t+1}, s_{t+2}, \dots, s_{T-1}, a_{T-1}, r_{T-1}, a_{T}),$$ where $T$ is the last time step of the interaction between the agent and the environment. During the interaction between the agent and the environment, the agent might decide to store this "experience" in a "buffer" (e.g. an array), so that it can use it later (you will see below a use case).

The elements of this type of sequences are often temporally correlated. What does this mean? For example, suppose that states are frames of a video game (that is, each frame is a different state). In this context, successive frames (or states) are similar to each other, which mathematically means that they are correlated.

It turns out that neural networks (NNs) are able to approximate (almost) any function. In RL, a policy is also a function: it is a function from a state to an action (or probability distribution over actions). So, we can represent a policy using a NN. (Deep RL is essentially a combination of traditional RL algorithms, like Q-learning, with NNs).

Moreover, it also turns out that training a NN using back-propagation with data that is temporally correlated might lead the NN not to capture the essential characteristics of the data, which, in practice (during training), means that we are not able to find the NN that represents the optimal policy (or another function, e.g. $Q(s, a)$, used later to retrieve the policy). In such cases, we often say that the training of the NN is not stable.

In the case of RL, the data used to train such types of neural networks (which represent the policy, or other functions that are used in RL) are the "rollouts", which contain elements that are often temporally correlated. Hence, we can't just feed the NN with a rollout, in the same order that the elements (states, actions, rewards and next states) are collected. So, in order to use uncorrelated data to train an NN, we can randomly take tuples of the form $\langle s_h, a_h, r_h, s_{h+1} \rangle$ from the rollout (where $h$ is some time step between $t$ and $T$). For example, suppose we take (or "sample") $3$ tuples $\langle s_7, a_7, r_7, s_{8} \rangle$, $\langle s_{97}, a_{97}, r_{97}, s_{98} \rangle$ and $\langle s_{2}, a_{2}, r_{2}, s_{3} \rangle$. Given that these elements have been observed at quite different points in time, they are likely to be less correlated than e.g. $\langle s_7, a_7, r_7, s_{8} \rangle$, $\langle s_{8}, a_{8}, r_{8}, s_{9} \rangle$ and $\langle s_{9}, a_{9}, r_{9}, s_{10} \rangle$ (which are successive "tuples of experience").

In this context, "experience replay" (or "replay buffer", or "experience replay buffer") refers to this technique of feeding a neural network using tuples (of "experience") which are less likely to be correlated (given that "random sampling" procedure). The "buffer" part refers to a data structure (e.g. an array or list) that stores the trajectory (or rollout), that is, it stores the "experience" of the agent (hence the name "experience"). The "replay" refers to the fact that this "experience" is reused (or "replayed") by randomly sampling from it to train the NN.

See also this question Why exactly do neural networks require i.i.d. data? regarding the fact that NNs often require i.i.d. data.

$\endgroup$

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.