Answers.Body: <blockquote>
    <p>Because the Q value is different, I don't see how the reward signal at time <span class="math-container">$t$</span> is of any relevance for <span class="math-container">$Q_{t+x}(s_t,a_t)$</span> at <span class="math-container">$t+x$</span>, the time of learning.</p>
  </blockquote>
  
  <p>The <span class="math-container">$r_t$</span> value for any single step is not dependent on <span class="math-container">$Q$</span> or the current policy. It is purely dependent on <span class="math-container">$(s_t,a_t)$</span>. That means you can use the Q update equation to use it to calculate <em>new</em> TD targets, by combining your knowledge of the old reward signal and the value functions of the latest policy.</p>
  
  <p>The value <span class="math-container">$r_t + \gamma \max_{a_{t+1}} Q(s_{t+1}, a_{t+1}; \theta_i^-)$</span> is the TD target in the loss function you show. There are many possible variations to calculate the TD target value in RL, with different properties. The one you are using is <em>biased</em> towards initial random values unrelated to the problem, and also deliberately biased towards older Q values to prevent runaway feedback. It is also low variance compared to other possibilities, and simpler to calculate.</p>
  
  <blockquote>
    <p>Also, it is likely that following a policy which is derived from <span class="math-container">$Q_t$</span> would lead to <span class="math-container">$a_{t}$</span>, whereas following a policy which is derived from <span class="math-container">$Q_{t+x}$</span> would not. </p>
  </blockquote>
  
  <p>Yes that is correct. However, you don't care about that for a single step, you just care about calculating a better estimate for <span class="math-container">$Q(s,a)$</span> regardless of whether you would choose <span class="math-container">$a$</span> in state <span class="math-container">$s$</span> with the current policy. That is what an action value measures - the utility of taking action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span> and <em>thereafter</em> following a given policy.</p>
  
  <p>This is a strength of experience replay, that you are constantly refining your estimates of off-policy action values to determine which is the best.</p>
  
  <p>This does become more of an issue when you want to use longer trajectories in the update step (which you may want to do to reduce bias of your TD target estimate). A series of steps in history <span class="math-container">$s_t,a_t,r_t ... s_{t+1}, a_{t+1},r_{t+1}...s_{t+n}$</span> may not have the same chance of occurring under the latest policy as it did when it was stored in memory. For the first step <span class="math-container">$s_t,a_t$</span> again you don't care if it is one you would currently take because the point is to refine your estimate of that action value. However, if you want to use <span class="math-container">$r_{t+1}, r_{t+2}$</span> etc plus <span class="math-container">$s_{t+n}$</span> to create a TD target, then you have to care whether your current policy and the one used to populate the history table would be different.</p>
  
  <p>It is a problem if you want to use more sophisticated estimates of TD target that use multiple sample steps along with experience replay. There are some approaches you can take to allow for this, such as <em>importance sampling</em>. For a single step update mechanism you don't need to worry about it.</p>
  
  <blockquote>
    <p>I don't see in the experience replay algorithm that the Q value <span class="math-container">$Q_t(s_t, a_t)$</span> is saved, so I must assume that is is not.</p>
  </blockquote>
  
  <p>This is correct. You must <em>re-calculate</em> the TD target from a more up-to-date policy to get better estimates of the action value. With experience replay, you are not interested in collecting a history of values of Q. Instead you are interested in the history of state transitions and rewards.</p>
  
  <blockquote>
    <p>Why does calculating the Q value again at a later time make sense FOR THE SAME SAVED REWARD AND ACTION?</p>
  </blockquote>
  
  <p>Because it <em>will</em> change, due to the learning process summarising effects of state transitions.</p>
  
  <p>As a toy example, consider a maze solver with traps (negative rewards) and treasures (positive rewards). At one point in history, the agent finds itself in a location and its policy told it to move into a trap on the next step. The agent would initially score location and steps leading up to it with negative Q values. Later it discovers through exploration that there is also some treasure if it takes a different turning towards the end of the the same series of steps. With experience replay, and re-calculating Q values each time, it can figure out which section of that path should be converted to high scores because they lead to treasure as well as the trap and now the agent has a better policy for the end of the path it has better estimates of value there.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-02T09:11:20.390Z
Answers.LastActivityDate: 2019-02-02T09:45:29.497Z
Answers.LastEditDate: 2019-02-02T09:45:29.497Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>Once the algorithm reaches a point where a reward (or penalty) is gained, then a slowly decaying amount of that reward is given to the Q-value of whichever action was derived from a particular state for each time step back through the game (or however far back you want to apply that reward).
  You will have stored the state and Q-values for each time step during the game, allowing you to update the appropriate Q-values with the new reward.
  These state / updated Q-values (from many runs) become your training data for the next iteration of your training algorithm. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-01T20:36:58.793Z
Answers.Text: So, to clarify, you are saying that i SHOULD save the Q values together with the rewards (at time t), and NOT calculate new Q values at the time (t+x) of learning?
Answers.UserDisplayName: Gulzar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-02T00:19:08.287Z
Answers.Text: @Gulzar Yeah, that's right. Don't update the Q-values immediately, but run a full set of simulations with the original values and then update them all when you have enough data. Once you have updated them, run your learning algorithm on the now updated state-action pairs.
Answers.UserDisplayName: DrMcCleod
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-02T11:21:38.060Z
Answers.Text: I believe we didn't understand each other, and i asked a question about something you didn't say, and you answered something I didn't ask. anyway, Neil Slater is here for the rescue, Problem solved.
Answers.UserDisplayName: Gulzar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-01T19:11:22.233Z
Answers.LastActivityDate: 2019-02-01T19:11:22.233Z
Answers.UserDisplayName: DrMcCleod
Body: <p>In <a href="https://datascience.stackexchange.com/q/20535/10640">experience replay</a>, the update rule follows the loss:</p>
  <blockquote>
  <p><span class="math-container">$$
  L_i(\theta_i) = \mathbb{E}_{(s_t, a_t, r_t, s_{t+1}) \sim U(D)} \left[ \left(r_t + \gamma \max_{a_{t+1}} Q(s_{t+1}, a_{t+1}; \theta_i^-) - Q(s_t, a_t; \theta_i)\right)^2 \right]
  $$</span></p>
  </blockquote>
  <p>I can't get my head around the order of calculation of the terms in that equation:</p>
  <p>An experience element is</p>
  <blockquote>
  <p><span class="math-container">$(s_t, a_t, r_t, s_{t+1} )$</span></p>
  </blockquote>
  <p>where</p>
  <blockquote>
  <p><span class="math-container">$s_t$</span> is the state at time <span class="math-container">$t$</span></p>
  <p><span class="math-container">$a_t$</span> is the action taken from <span class="math-container">$s_t$</span> at time <span class="math-container">$t$</span></p>
  <p><span class="math-container">$r_t$</span> is the reward received by taking that action from <span class="math-container">$s_t$</span> at time
  <span class="math-container">$t$</span></p>
  <p><span class="math-container">$s_{t+1}$</span> is the next state</p>
  </blockquote>
  <p>In <a href="https://qr.ae/pNb5Z7" rel="nofollow noreferrer">the on policy case</a>, <strong>as I understand it</strong>, Q of the equation above is the same Q, which is the only approximator.</p>
  <p>As I understand the algorithm, at time <span class="math-container">$t$</span> we save an experience</p>
  <blockquote>
  <p><span class="math-container">$(s_t, a_t, r_t, s_{t+1} )$</span>.</p>
  </blockquote>
  <p>Then, later, at time <span class="math-container">$t+x$</span>, we attempt to learn from that experience.</p>
  <p>However, at the time of saving the experience, <span class="math-container">$Q(s_t,a_t)$</span> was something different than at the time of attempting to learn from that experience, because the parameters <span class="math-container">$\theta$</span> of <span class="math-container">$Q$</span> have since changed. This could actually be written as</p>
  <blockquote>
  <p><span class="math-container">$Q_t(s_t, a_t) \neq Q_{t+x}(s_t,a_t)$</span></p>
  </blockquote>
  <p>Because the Q value is different, I don't see how the reward signal at time <span class="math-container">$t$</span> is of any relevance for <span class="math-container">$Q_{t+x}(s_t,a_t)$</span> at <span class="math-container">$t+x$</span>, the time of learning.</p>
  <p>Also, it is likely that following a policy that is derived from <span class="math-container">$Q_t$</span> would lead to <span class="math-container">$a_{t}$</span>, whereas following a policy that is derived from <span class="math-container">$Q_{t+x}$</span> would not.</p>
  <p>I don't see in the experience replay algorithm that the Q value <span class="math-container">$Q_t(s_t, a_t)$</span> is saved, so I must assume that is not.</p>
  <p><strong>Why does calculating the Q value again at a later time make sense FOR THE SAME SAVED REWARD AND ACTION?</strong></p>
  
Tags: <machine-learning><reinforcement-learning><q-learning><experience-replay>
Title: When are Q values calculated in experience replay?
UserDisplayName: Gulzar
ThreadText: # When are Q values calculated in experience replay?
  
  (Asked by: username_0 on 2019-02-01)
  
  In [experience replay](https://datascience.stackexchange.com/q/20535/10640), the update rule follows the loss:
  
  > $$
  > L\_i(\theta\_i) = \mathbb{E}\_{(s\_t, a\_t, r\_t, s\_{t+1}) \sim U(D)} \left[ \left(r\_t + \gamma \max\_{a\_{t+1}} Q(s\_{t+1}, a\_{t+1}; \theta\_i^-) - Q(s\_t, a\_t; \theta\_i)\right)^2 \right]
  > $$
  
  I can't get my head around the order of calculation of the terms in that equation:
  
  An experience element is
  
  > $(s\_t, a\_t, r\_t, s\_{t+1} )$
  
  where
  
  > $s\_t$ is the state at time $t$
  >
  > $a\_t$ is the action taken from $s\_t$ at time $t$
  >
  > $r\_t$ is the reward received by taking that action from $s\_t$ at time
  > $t$
  >
  > $s\_{t+1}$ is the next state
  
  In [the on policy case](https://qr.ae/pNb5Z7), **as I understand it**, Q of the equation above is the same Q, which is the only approximator.
  
  As I understand the algorithm, at time $t$ we save an experience
  
  > $(s\_t, a\_t, r\_t, s\_{t+1} )$.
  
  Then, later, at time $t+x$, we attempt to learn from that experience.
  
  However, at the time of saving the experience, $Q(s\_t,a\_t)$ was something different than at the time of attempting to learn from that experience, because the parameters $\theta$ of $Q$ have since changed. This could actually be written as
  
  > $Q\_t(s\_t, a\_t) \neq Q\_{t+x}(s\_t,a\_t)$
  
  Because the Q value is different, I don't see how the reward signal at time $t$ is of any relevance for $Q\_{t+x}(s\_t,a\_t)$ at $t+x$, the time of learning.
  
  Also, it is likely that following a policy that is derived from $Q\_t$ would lead to $a\_{t}$, whereas following a policy that is derived from $Q\_{t+x}$ would not.
  
  I don't see in the experience replay algorithm that the Q value $Q\_t(s\_t, a\_t)$ is saved, so I must assume that is not.
  
  **Why does calculating the Q value again at a later time make sense FOR THE SAME SAVED REWARD AND ACTION?**
  
  **Tags:** machine-learning, reinforcement-learning, q-learning, experience-replay
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2019-02-02. Score: 2 | Accepted answer
  
  > Because the Q value is different, I don't see how the reward signal at time $t$ is of any relevance for $Q\_{t+x}(s\_t,a\_t)$ at $t+x$, the time of learning.
  
  The $r\_t$ value for any single step is not dependent on $Q$ or the current policy. It is purely dependent on $(s\_t,a\_t)$. That means you can use the Q update equation to use it to calculate *new* TD targets, by combining your knowledge of the old reward signal and the value functions of the latest policy.
  
  The value $r\_t + \gamma \max\_{a\_{t+1}} Q(s\_{t+1}, a\_{t+1}; \theta\_i^-)$ is the TD target in the loss function you show. There are many possible variations to calculate the TD target value in RL, with different properties. The one you are using is *biased* towards initial random values unrelated to the problem, and also deliberately biased towards older Q values to prevent runaway feedback. It is also low variance compared to other possibilities, and simpler to calculate.
  
  > Also, it is likely that following a policy which is derived from $Q\_t$ would lead to $a\_{t}$, whereas following a policy which is derived from $Q\_{t+x}$ would not.
  
  Yes that is correct. However, you don't care about that for a single step, you just care about calculating a better estimate for $Q(s,a)$ regardless of whether you would choose $a$ in state $s$ with the current policy. That is what an action value measures - the utility of taking action $a$ in state $s$ and *thereafter* following a given policy.
  
  This is a strength of experience replay, that you are constantly refining your estimates of off-policy action values to determine which is the best.
  
  This does become more of an issue when you want to use longer trajectories in the update step (which you may want to do to reduce bias of your TD target estimate). A series of steps in history $s\_t,a\_t,r\_t ... s\_{t+1}, a\_{t+1},r\_{t+1}...s\_{t+n}$ may not have the same chance of occurring under the latest policy as it did when it was stored in memory. For the first step $s\_t,a\_t$ again you don't care if it is one you would currently take because the point is to refine your estimate of that action value. However, if you want to use $r\_{t+1}, r\_{t+2}$ etc plus $s\_{t+n}$ to create a TD target, then you have to care whether your current policy and the one used to populate the history table would be different.
  
  It is a problem if you want to use more sophisticated estimates of TD target that use multiple sample steps along with experience replay. There are some approaches you can take to allow for this, such as *importance sampling*. For a single step update mechanism you don't need to worry about it.
  
  > I don't see in the experience replay algorithm that the Q value $Q\_t(s\_t, a\_t)$ is saved, so I must assume that is is not.
  
  This is correct. You must *re-calculate* the TD target from a more up-to-date policy to get better estimates of the action value. With experience replay, you are not interested in collecting a history of values of Q. Instead you are interested in the history of state transitions and rewards.
  
  > Why does calculating the Q value again at a later time make sense FOR THE SAME SAVED REWARD AND ACTION?
  
  Because it *will* change, due to the learning process summarising effects of state transitions.
  
  As a toy example, consider a maze solver with traps (negative rewards) and treasures (positive rewards). At one point in history, the agent finds itself in a location and its policy told it to move into a trap on the next step. The agent would initially score location and steps leading up to it with negative Q values. Later it discovers through exploration that there is also some treasure if it takes a different turning towards the end of the the same series of steps. With experience replay, and re-calculating Q values each time, it can figure out which section of that path should be converted to high scores because they lead to treasure as well as the trap and now the agent has a better policy for the end of the path it has better estimates of value there.
  
  
  ---
  
  ### Answer by username_2 on 2019-02-01. Score: 0
  
  Once the algorithm reaches a point where a reward (or penalty) is gained, then a slowly decaying amount of that reward is given to the Q-value of whichever action was derived from a particular state for each time step back through the game (or however far back you want to apply that reward).
  You will have stored the state and Q-values for each time step during the game, allowing you to update the appropriate Q-values with the new reward.
  These state / updated Q-values (from many runs) become your training data for the next iteration of your training algorithm.
  
  > **Comments:**
  > **username_0**: So, to clarify, you are saying that i SHOULD save the Q values together with the rewards (at time t), and NOT calculate new Q values at the time (t+x) of learning?  
  > **username_2**: @username_0 Yeah, that's right. Don't update the Q-values immediately, but run a full set of simulations with the original values and then update them all when you have enough data. Once you have updated them, run your learning algorithm on the now updated state-action pairs.  
  > **username_0**: I believe we didn't understand each other, and i asked a question about something you didn't say, and you answered something I didn't ask. anyway, username_1 username_1 is here for the rescue, Problem solved.  
  
  ---
  
  