Answers.Body: <p>In reinforcement learning (RL), an <em>agent</em> interacts with an <em>environment</em> in time steps. At each time step <span class="math-container">$t$</span>, the agent and the environment are in some state <span class="math-container">$s_t$</span>. From that state <span class="math-container">$s_t$</span>, the agent chooses and executes an action <span class="math-container">$a_t$</span> and the environment emits a reward <span class="math-container">$r_t$</span> (which values the just taken action <span class="math-container">$a_t$</span>). Finally, the agent and the environment move to the next state, <span class="math-container">$s_{t+1}$</span>. This interaction proceeds until either the agent dies or some other termination criterion is met. </p>
  
  <p>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.</p>
  
  <p>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 <span class="math-container">$$(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}),$$</span> where <span class="math-container">$T$</span> 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).</p>
  
  <p>The elements of this type of sequences are often temporally <em>correlated</em>. 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 <em>similar</em> to each other, which mathematically means that they are correlated. </p>
  
  <p>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 <a href="https://ai.stackexchange.com/q/12274/2444">probability distribution over actions</a>). So, we can represent a policy using a NN. (Deep RL is essentially a combination of traditional RL algorithms, like Q-learning, with NNs). </p>
  
  <p>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. <span class="math-container">$Q(s, a)$</span>, used later to retrieve the policy). In such cases, we often say that the training of the NN is not stable. </p>
  
  <p>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 <span class="math-container">$\langle s_h, a_h, r_h, s_{h+1} \rangle$</span> from the rollout (where <span class="math-container">$h$</span> is some time step between <span class="math-container">$t$</span> and <span class="math-container">$T$</span>). For example, suppose we take (or "sample") <span class="math-container">$3$</span> tuples <span class="math-container">$\langle s_7, a_7, r_7, s_{8} \rangle$</span>, <span class="math-container">$\langle s_{97}, a_{97}, r_{97}, s_{98} \rangle$</span> and <span class="math-container">$\langle s_{2}, a_{2}, r_{2}, s_{3} \rangle$</span>. Given that these elements have been observed at quite different points in time, they are likely to be less correlated than e.g. <span class="math-container">$\langle s_7, a_7, r_7, s_{8} \rangle$</span>, <span class="math-container">$\langle s_{8}, a_{8}, r_{8}, s_{9} \rangle$</span> and <span class="math-container">$\langle s_{9}, a_{9}, r_{9}, s_{10} \rangle$</span> (which are successive "tuples of experience").</p>
  
  <p>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.</p>
  
  <p>See also this question <a href="https://ai.stackexchange.com/q/10839/2444">Why exactly do neural networks require i.i.d. data?</a> regarding the fact that NNs often require i.i.d. data.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-04T15:41:13.910Z
Answers.LastActivityDate: 2019-06-10T20:43:54.363Z
Answers.LastEditDate: 2019-06-10T20:43:54.363Z
Answers.UserDisplayName: nbro
Answers.Body: <h3>What is it?</h3>
  <p>An experience replay (ER) buffer is an array/list (or buffer) <span class="math-container">$D = [e_1, \dots, e_N ]$</span> where you store the transitions that the agent collects while interacting with the environment. These transitions are usually represented as tuples of the form <span class="math-container">$e_t = (s_t, a_t, r_t, s_{t+1})$</span>, where</p>
  <ul>
  <li><span class="math-container">$s_t$</span> is the state of the agent at time step <span class="math-container">$t$</span>,</li>
  <li><span class="math-container">$a_t$</span> is the action taken by the agent when in state <span class="math-container">$s_t$</span>,</li>
  <li><span class="math-container">$r_t$</span> is the reward received by the environment after having taken action <span class="math-container">$a_t$</span> in <span class="math-container">$s_t$</span></li>
  <li><span class="math-container">$s_{t+1}$</span> is the next state the agent ended up in after that action</li>
  </ul>
  <p>The agent then samples (e.g. uniformly) transitions from this ER buffer <span class="math-container">$D$</span> to perform an update of the value function <span class="math-container">$\hat{q}(s, a)$</span>. The ER buffer <span class="math-container">$D$</span> can thus be thought of as a dataset.</p>
  <h3>Why do we need it?</h3>
  <p>The motivation for experience replay (in the <a href="https://www.cs.toronto.edu/%7Evmnih/docs/dqn.pdf" rel="nofollow noreferrer">DQN paper</a> that popularized this technique) is that learning becomes more stable. In fact, the authors of the DQN paper write</p>
  <blockquote>
  <p>To alleviate the problems of correlated data and non-stationary distributions, we use an experience replay mechanism [<a href="http://isl.anthropomatik.kit.edu/pdf/Lin1993.pdf" rel="nofollow noreferrer">13</a>] which randomly samples previous transitions, and thereby smooths the training distribution over many past behaviors.</p>
  </blockquote>
  <p>or</p>
  <blockquote>
  <p>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.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-01T11:30:23.433Z
Answers.Text: Yes, I know I had already given [an answer to this question](https://ai.stackexchange.com/a/11644/2444), but this is a slightly shorter and alternative answer that some people may like more.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-01T11:29:44.787Z
Answers.LastActivityDate: 2020-11-01T15:16:15.973Z
Answers.LastEditDate: 2020-11-01T15:16:15.973Z
Answers.UserDisplayName: nbro
Body: <p>I've been reading Google's DeepMind Atari <a href="http://web.stanford.edu/class/psych209/Readings/MnihEtAlHassibis15NatureControlDeepRL.pdf" rel="noreferrer" title="RL">paper</a> 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.</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>The paper then elaborates as follows (I've taken a screenshot, since there are a lot of mathematical symbols that are difficult to reproduce):</p>
  
  <p><a href="https://i.sstatic.net/eOOTH.png" rel="noreferrer"><img src="https://i.sstatic.net/eOOTH.png" alt="enter image description here"></a></p>
  
  <p>What is experience replay and what are its benefits in laymen's terms?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-30T19:40:45.880Z
Comments.Text: 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
Comments.UserDisplayName: Neil Slater
Tags: <deep-learning><reinforcement-learning><deep-rl><experience-replay>
Title: What is experience replay in laymen's terms?
UserDisplayName: user491626
ThreadText: # What is experience replay in laymen's terms?
  
  (Asked by: username_0 on 2018-05-30)
  
  I've been reading Google's DeepMind Atari [paper](http://web.stanford.edu/class/psych209/Readings/MnihEtAlHassibis15NatureControlDeepRL.pdf "RL") 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](https://i.sstatic.net/eOOTH.png)](https://i.sstatic.net/eOOTH.png)
  
  What is experience replay and what are its benefits in laymen's terms?
  
  **Tags:** deep-learning, reinforcement-learning, deep-rl, experience-replay
  
  > **Comments:**
  > **username_1**: 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  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2019-04-04. Score: 4
  
  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](https://ai.stackexchange.com/q/12274/2444)). 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?](https://ai.stackexchange.com/q/10839/2444) regarding the fact that NNs often require i.i.d. data.
  
  
  ---
  
  ### Answer by username_2 on 2020-11-01. Score: 0
  
  ### What is it?
  
  An experience replay (ER) buffer is an array/list (or buffer) $D = [e\_1, \dots, e\_N ]$ where you store the transitions that the agent collects while interacting with the environment. These transitions are usually represented as tuples of the form $e\_t = (s\_t, a\_t, r\_t, s\_{t+1})$, where
  
  * $s\_t$ is the state of the agent at time step $t$,
  * $a\_t$ is the action taken by the agent when in state $s\_t$,
  * $r\_t$ is the reward received by the environment after having taken action $a\_t$ in $s\_t$
  * $s\_{t+1}$ is the next state the agent ended up in after that action
  
  The agent then samples (e.g. uniformly) transitions from this ER buffer $D$ to perform an update of the value function $\hat{q}(s, a)$. The ER buffer $D$ can thus be thought of as a dataset.
  
  ### Why do we need it?
  
  The motivation for experience replay (in the [DQN paper](https://www.cs.toronto.edu/%7Evmnih/docs/dqn.pdf) that popularized this technique) is that learning becomes more stable. In fact, the authors of the DQN paper write
  
  > To alleviate the problems of correlated data and non-stationary distributions, we use an experience replay mechanism [[13](http://isl.anthropomatik.kit.edu/pdf/Lin1993.pdf)] which randomly samples previous transitions, and thereby smooths the training distribution over many past behaviors.
  
  or
  
  > 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.
  
  > **Comments:**
  > **username_2**: Yes, I know I had already given [an answer to this question](https://ai.stackexchange.com/a/11644/2444), but this is a slightly shorter and alternative answer that some people may like more.  
  
  ---
  
  