Sutton & Barto's notation $V_{t+n}$ in Chapter 7: $n$-step Bootstrapping

Question

Until Chapter 6 of Sutton & Barto's book 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.

Answer 1

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.