Answers.Body: <blockquote>
    <p>So, what is the purpose of the new index for <span class="math-container">$V$</span> in Chapter 7, and why is it more important at this particular chapter?</p>
  </blockquote>
  
  <p>My guess would be that your intuition is correct, and that it's mostly introduced just to clarify exactly which "version" of our value function approximator is going to be used in any particular equation. In previous chapters, which discuss single-step update rules, I guess the authors assumed there was less potential for confusion, and therefore no need to clarify this. Without the clarification, some people might for instance wonder if we should use <span class="math-container">$V_t$</span> for our value estimates of an <span class="math-container">$n$</span>-step return <span class="math-container">$G_{t+n}$</span>, regardless of how large <span class="math-container">$n$</span> is.</p>
  
  <hr>
  
  <blockquote>
    <p>However, I think this introduced a technical error, because suppose we just learned from an 10-step episode (<span class="math-container">$T=10$</span>), using <span class="math-container">$n = 3$</span>. Then the latest estimate of <span class="math-container">$v_\pi$</span> is <span class="math-container">$V_{T-1} = V_{10 - 1} = V_{9}$</span>. Then at the next episode, the first time <span class="math-container">$V_{t + n}$</span> is used to inform a target update, it will be for <span class="math-container">$\tau = 0$</span> (from the pseudo-code), which implies <span class="math-container">$t - n + 1 = 0$</span>, so <span class="math-container">$t = n - 1$</span>, that is, <span class="math-container">$V_{t+n}=V_{n-1+n}=V_{2n-1}=V_5$</span>, which is not the most up-to-date estimate <span class="math-container">$V_9$</span> of <span class="math-container">$v_\pi$</span>.</p>
  </blockquote>
  
  <p>Once we start considering a situation with more than a single episode, the <span class="math-container">$V_t$</span> notation becomes quite confusing. You should read <span class="math-container">$V_t$</span> as "the value function approximator that we have available <strong>at time <span class="math-container">$t$</span> of the current episode</strong>". So, if we were to use the symbol <span class="math-container">$V_0$</span> within the context of a second episode, that would be identical to what was referred to as <span class="math-container">$V_T$</span> in the context of the first episode. The <span class="math-container">$V_t$</span> notation can be convenient if we're thinking about our equations with our minds in "math-mode", but becomes highly confusing once we start thinking about practical implementations involving multiple episodes -- this is probably why they did not include it in the pseudocode.</p>
  
  <p>If you really wanted to use the subscript-notation in the pseudocode, you'd have to add an extra term in the subscript that adds up all the durations of all previous episodes. If we then try to work out your example situation, we'd run into another problem though... we'd want to use <span class="math-container">$V_{t+n+T} = V_{2n-1+T} = V_{15}$</span> at the first iteration where <span class="math-container">$\tau = 0$</span> in the second episode. But, across the two episodes, only <span class="math-container">$13$</span> steps have passed, so this does not yet exist! You run into the same issue if you try to work out what happened when <span class="math-container">$\tau = 0$</span> in the first episode: applying exactly the same reasoning as in your quote, we would have wanted to use <span class="math-container">$V_5$</span> after only <span class="math-container">$3$</span> time steps passed in the first episode.</p>
  
  <p>The problem here is that you're trying to use the variable named <span class="math-container">$t$</span> in the pseudocode as the subscript for <span class="math-container">$V$</span>. To get a better idea of what's going on here, let's loop back to the previous page and examine the definition of the <span class="math-container">$n$</span>-step return:</p>
  
  <p><span class="math-container">$$G_{t:t+n} \doteq R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^n V_{t+n-1} (S_{t+n}).$$</span></p>
  
  <p>Ok, we've got that. Now, let's take another look at the update rule in which we use this quantity:</p>
  
  <p><span class="math-container">$$V_{t+n}(S_t) \doteq V_{t+n-1}(S_t) + \alpha \left[ G_{t:t+n} - V_{t+n-1} (S_t) \right].$$</span></p>
  
  <p>Ok. So <span class="math-container">$V_{t+n-1}$</span> appears three times in the update rule. Two times explicitly, estimating the value of <span class="math-container">$S_t$</span>, and once more "hidden" in the definition of <span class="math-container">$G_{t:t+n}$</span>, where it is used to estimate the value of <span class="math-container">$S_{t+n}$</span>. Note very carefully what it is that this update rule is doing; <strong>it's updating the state estimate of <span class="math-container">$S_t$</span></strong>. If you now look at the pseudocode again, you'll see a comment on the line where <span class="math-container">$\tau$</span> is computed: <strong>(<span class="math-container">$\tau$</span> is the time whose state's estimate is being updated)</strong>!</p>
  
  <p>What this means, is that in the pseudocode, you should be using <span class="math-container">$\tau$</span> as the subscript for <span class="math-container">$V$</span>! If you do that, it'll at least be correct for the first episode. In the pseudocode, the update rule looks like:</p>
  
  <p><span class="math-container">$$V(S_{\tau}) \gets V(S_{\tau}) + \dots$$</span></p>
  
  <p>Plugging in the subscripts from the mathematical definition leads to:</p>
  
  <p><span class="math-container">$$V_{\tau + n}(S_{\tau}) \gets V_{\tau + n - 1}(S_{\tau}) + \dots$$</span></p>
  
  <p>Since the pseudocode defines <span class="math-container">$\tau = t - n + 1$</span>, we can substitute above:</p>
  
  <p><span class="math-container">$$
  \begin{aligned}
  V_{t - n + 1 + n}(S_{t - n + 1}) &amp;\gets V_{t - n + 1 + n - 1}(S_{t - n + 1}) + \dots\\
  V_{t + 1}(S_{t - n + 1}) &amp;\gets V_{t}(S_{t - n + 1}) + \dots
  \end{aligned}$$</span> </p>
  
  <p>and now it should make sense again from a practical point of view. At every time step <span class="math-container">$t$</span>, where <span class="math-container">$t$</span> measures number of steps of experience that we have simulated, we simply use the latest value function <span class="math-container">$V_t$</span> we have available at that time for bootstrapping in the update rule. When <span class="math-container">$t + 1 &lt; n$</span>, <span class="math-container">$S_{t - n + 1}$</span> is undefined. In these cases, the above update rule doesn't work, which makes sense intuitively because we have not yet progressed far enough into the episode to be capable of compute <span class="math-container">$n$</span>-step returns.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-08T00:10:16.237Z
Answers.Text: Yes, we are in agreement about this, it seems, thank you for your thoughtful answer!
Answers.UserDisplayName: user118967
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-07T18:17:51.000Z
Answers.LastActivityDate: 2019-11-07T18:17:51.000Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>Until Chapter 6 of <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Sutton &amp; Barto's book</a> on Reinforcement Learning, the authors use <span class="math-container">$V$</span> for the current estimate of a state value. Equation (6.1), for example, shows:</p>
  
  <p><span class="math-container">$$ V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)]\ \ \ \ \ \ (6.1)$$</span></p>
  
  <p>However, on Chapter 7 they add a subscript to <span class="math-container">$V$</span>. The first time this appears is on page 143 when they define the return from <span class="math-container">$t$</span> to <span class="math-container">$t+1$</span>:</p>
  
  <p><span class="math-container">$$ G_{t:t+1} \dot{=} R_{t+1} + \gamma V_t(S_{t+1})$$</span></p>
  
  <p>and say that <span class="math-container">$V_t : \mathcal{S} \rightarrow  \mathbb{R}$</span> is "the estimate at time <span class="math-container">$t$</span> of <span class="math-container">$v_\pi$</span>."</p>
  
  <p>At first I thought I understood this as a natural consequence of considering <span class="math-container">$n$</span> steps ahead in the future and needing an extra index to go over the <span class="math-container">$n$</span> steps. But then this stopped making sense when I realized that an estimate for a state must be consolidated, no matter at which of <span class="math-container">$n$</span> steps that is coming from. After all, a state <span class="math-container">$s$</span> has a single value to estimate, <span class="math-container">$v_\pi(s)$</span>, and that does not depend on <span class="math-container">$t$</span>.</p>
  
  <p>Then I thought that they are just taking into account that there are many successive estimates of <span class="math-container">$V$</span> as the algorithm progresses, so <span class="math-container">$V_t$</span> is just the estimate after processing the <span class="math-container">$n$</span> steps starting at time <span class="math-container">$t$</span>. In other words, the subscript would be a rigorous mathematical way of denoting the sequence of algorithmic updates. But this does not make sense either since even in Chapter 6 and before, the estimate is <em>also</em> successively updated. See Equation (6.1), for example. The <span class="math-container">$V$</span> on the left-hand side is a different variable from the one on the right-hand side (this is why they must use <span class="math-container">$\leftarrow$</span> indicating an assignment as opposed to a mathematical equality with <span class="math-container">$=$</span>). It could have easily been written with an index as well.</p>
  
  <p>So, what is the purpose of the new index for <span class="math-container">$V$</span> in Chapter 7, and why is it more important at this particular chapter?</p>
  
  <p><strong>Edit and elaboration</strong>: Going back to the text, it seems to me that the new subscript is indeed added as an attempt for greater clarity, even though the subscript-less notation <span class="math-container">$V$</span> from previous chapters might have been kept (and in fact it is still used in the pseudo-code in page 144).</p>
  
  <p>It seems the authors wanted to stress that the update of <span class="math-container">$V$</span> happens not only for every trace of <span class="math-container">$n$</span> steps, but also at <em>every one</em> of those steps.</p>
  
  <p>However, I think this introduced a technical error, because suppose we just learned from an 10-step episode (<span class="math-container">$T=10$</span>), using <span class="math-container">$n = 3$</span>. Then the latest estimate of <span class="math-container">$v_\pi$</span> is <span class="math-container">$V_{T-1} = V_{10 - 1} = V_{9}$</span>. Then at the next episode, the first time <span class="math-container">$V_{t + n}$</span> is used to inform a target update, it will be for <span class="math-container">$\tau = 0$</span> (from the pseudo-code), which implies <span class="math-container">$t - n + 1 = 0$</span>, so <span class="math-container">$t = n - 1$</span>, that is, <span class="math-container">$V_{t+n}=V_{n-1+n}=V_{2n-1}=V_5$</span>, which is not the most up-to-date estimate <span class="math-container">$V_9$</span> of <span class="math-container">$v_\pi$</span>.</p>
  
  <p>Of course the problem would be easily solved if we simply set the next used estimate <span class="math-container">$V_{2n + 1}$</span> to be equal to the last episode's <span class="math-container">$V_{T-1}$</span>, but to avoid confusion this would have to be explicitly stated somewhere.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-07T03:17:47.903Z
Comments.Text: Welcome to SE:AI!
Comments.UserDisplayName: DukeZhou
Tags: <reinforcement-learning><sutton-barto><notation>
Title: Sutton & Barto's notation $V_{t+n}$ in Chapter 7: $n$-step Bootstrapping
UserDisplayName: user118967
ThreadText: # Sutton & Barto's notation $V_{t+n}$ in Chapter 7: $n$-step Bootstrapping
  
  (Asked by: username_0 on 2019-11-07)
  
  Until Chapter 6 of [Sutton & Barto's book](http://incompleteideas.net/book/the-book-2nd.html) on Reinforcement Learning, the authors use $V$ for the current estimate of a state value. Equation (6.1), for example, shows:
  
  $$ V(S\_t) \leftarrow V(S\_t) + \alpha[G\_t - V(S\_t)]\ \ \ \ \ \ (6.1)$$
  
  However, on Chapter 7 they add a subscript to $V$. The first time this appears is on page 143 when they define the return from $t$ to $t+1$:
  
  $$ G\_{t:t+1} \dot{=} R\_{t+1} + \gamma V\_t(S\_{t+1})$$
  
  and say that $V\_t : \mathcal{S} \rightarrow \mathbb{R}$ is "the estimate at time $t$ of $v\_\pi$."
  
  At first I thought I understood this as a natural consequence of considering $n$ steps ahead in the future and needing an extra index to go over the $n$ steps. But then this stopped making sense when I realized that an estimate for a state must be consolidated, no matter at which of $n$ steps that is coming from. After all, a state $s$ has a single value to estimate, $v\_\pi(s)$, and that does not depend on $t$.
  
  Then I thought that they are just taking into account that there are many successive estimates of $V$ as the algorithm progresses, so $V\_t$ is just the estimate after processing the $n$ steps starting at time $t$. In other words, the subscript would be a rigorous mathematical way of denoting the sequence of algorithmic updates. But this does not make sense either since even in Chapter 6 and before, the estimate is *also* successively updated. See Equation (6.1), for example. The $V$ on the left-hand side is a different variable from the one on the right-hand side (this is why they must use $\leftarrow$ indicating an assignment as opposed to a mathematical equality with $=$). It could have easily been written with an index as well.
  
  So, what is the purpose of the new index for $V$ in Chapter 7, and why is it more important at this particular chapter?
  
  **Edit and elaboration**: Going back to the text, it seems to me that the new subscript is indeed added as an attempt for greater clarity, even though the subscript-less notation $V$ from previous chapters might have been kept (and in fact it is still used in the pseudo-code in page 144).
  
  It seems the authors wanted to stress that the update of $V$ happens not only for every trace of $n$ steps, but also at *every one* of those steps.
  
  However, I think this introduced a technical error, because suppose we just learned from an 10-step episode ($T=10$), using $n = 3$. Then the latest estimate of $v\_\pi$ is $V\_{T-1} = V\_{10 - 1} = V\_{9}$. Then at the next episode, the first time $V\_{t + n}$ is used to inform a target update, it will be for $\tau = 0$ (from the pseudo-code), which implies $t - n + 1 = 0$, so $t = n - 1$, that is, $V\_{t+n}=V\_{n-1+n}=V\_{2n-1}=V\_5$, which is not the most up-to-date estimate $V\_9$ of $v\_\pi$.
  
  Of course the problem would be easily solved if we simply set the next used estimate $V\_{2n + 1}$ to be equal to the last episode's $V\_{T-1}$, but to avoid confusion this would have to be explicitly stated somewhere.
  
  **Tags:** reinforcement-learning, sutton-barto, notation
  > **Comments:**
  > **username_1**: Welcome to SE:AI!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-11-07. Score: 2 | Accepted answer
  
  > So, what is the purpose of the new index for $V$ in Chapter 7, and why is it more important at this particular chapter?
  
  My guess would be that your intuition is correct, and that it's mostly introduced just to clarify exactly which "version" of our value function approximator is going to be used in any particular equation. In previous chapters, which discuss single-step update rules, I guess the authors assumed there was less potential for confusion, and therefore no need to clarify this. Without the clarification, some people might for instance wonder if we should use $V\_t$ for our value estimates of an $n$-step return $G\_{t+n}$, regardless of how large $n$ is.
  
  ---
  
  > However, I think this introduced a technical error, because suppose we just learned from an 10-step episode ($T=10$), using $n = 3$. Then the latest estimate of $v\_\pi$ is $V\_{T-1} = V\_{10 - 1} = V\_{9}$. Then at the next episode, the first time $V\_{t + n}$ is used to inform a target update, it will be for $\tau = 0$ (from the pseudo-code), which implies $t - n + 1 = 0$, so $t = n - 1$, that is, $V\_{t+n}=V\_{n-1+n}=V\_{2n-1}=V\_5$, which is not the most up-to-date estimate $V\_9$ of $v\_\pi$.
  
  Once we start considering a situation with more than a single episode, the $V\_t$ notation becomes quite confusing. You should read $V\_t$ as "the value function approximator that we have available **at time $t$ of the current episode**". So, if we were to use the symbol $V\_0$ within the context of a second episode, that would be identical to what was referred to as $V\_T$ in the context of the first episode. The $V\_t$ notation can be convenient if we're thinking about our equations with our minds in "math-mode", but becomes highly confusing once we start thinking about practical implementations involving multiple episodes -- this is probably why they did not include it in the pseudocode.
  
  If you really wanted to use the subscript-notation in the pseudocode, you'd have to add an extra term in the subscript that adds up all the durations of all previous episodes. If we then try to work out your example situation, we'd run into another problem though... we'd want to use $V\_{t+n+T} = V\_{2n-1+T} = V\_{15}$ at the first iteration where $\tau = 0$ in the second episode. But, across the two episodes, only $13$ steps have passed, so this does not yet exist! You run into the same issue if you try to work out what happened when $\tau = 0$ in the first episode: applying exactly the same reasoning as in your quote, we would have wanted to use $V\_5$ after only $3$ time steps passed in the first episode.
  
  The problem here is that you're trying to use the variable named $t$ in the pseudocode as the subscript for $V$. To get a better idea of what's going on here, let's loop back to the previous page and examine the definition of the $n$-step return:
  
  $$G\_{t:t+n} \doteq R\_{t+1} + \gamma R\_{t+2} + \dots + \gamma^{n-1} R\_{t+n} + \gamma^n V\_{t+n-1} (S\_{t+n}).$$
  
  Ok, we've got that. Now, let's take another look at the update rule in which we use this quantity:
  
  $$V\_{t+n}(S\_t) \doteq V\_{t+n-1}(S\_t) + \alpha \left[ G\_{t:t+n} - V\_{t+n-1} (S\_t) \right].$$
  
  Ok. So $V\_{t+n-1}$ appears three times in the update rule. Two times explicitly, estimating the value of $S\_t$, and once more "hidden" in the definition of $G\_{t:t+n}$, where it is used to estimate the value of $S\_{t+n}$. Note very carefully what it is that this update rule is doing; **it's updating the state estimate of $S\_t$**. If you now look at the pseudocode again, you'll see a comment on the line where $\tau$ is computed: **($\tau$ is the time whose state's estimate is being updated)**!
  
  What this means, is that in the pseudocode, you should be using $\tau$ as the subscript for $V$! If you do that, it'll at least be correct for the first episode. In the pseudocode, the update rule looks like:
  
  $$V(S\_{\tau}) \gets V(S\_{\tau}) + \dots$$
  
  Plugging in the subscripts from the mathematical definition leads to:
  
  $$V\_{\tau + n}(S\_{\tau}) \gets V\_{\tau + n - 1}(S\_{\tau}) + \dots$$
  
  Since the pseudocode defines $\tau = t - n + 1$, we can substitute above:
  
  $$
  \begin{aligned}
  V\_{t - n + 1 + n}(S\_{t - n + 1}) &\gets V\_{t - n + 1 + n - 1}(S\_{t - n + 1}) + \dots\\
  V\_{t + 1}(S\_{t - n + 1}) &\gets V\_{t}(S\_{t - n + 1}) + \dots
  \end{aligned}$$
  
  and now it should make sense again from a practical point of view. At every time step $t$, where $t$ measures number of steps of experience that we have simulated, we simply use the latest value function $V\_t$ we have available at that time for bootstrapping in the update rule. When $t + 1 < n$, $S\_{t - n + 1}$ is undefined. In these cases, the above update rule doesn't work, which makes sense intuitively because we have not yet progressed far enough into the episode to be capable of compute $n$-step returns.
  
  > **Comments:**
  > **username_0**: Yes, we are in agreement about this, it seems, thank you for your thoughtful answer!  
  
  ---
  
  