Bootstrapping: learn before the reward arrives

Let $t$ be the current step, $S_t$ its state and $R_{t+1}$ the reward after the action taken there. The episode ends at step $T$, $\gamma$ is the discount between 0 and 1, and $k$ counts steps ahead. The return adds the discounted rewards, and a fixed policy's value is the expected return (Sutton and Barto, Chapter 3):

$$G_t=\sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1},\qquad v_\pi(s)=\mathbb E_\pi[G_t\mid S_t=s].$$

With no discount, every nonterminal room in the deterministic corridor is worth 1.

Monte Carlo. Move each visited state toward its completed return, with step size $0<\alpha\le1$. With a fixed policy, finite-variance returns, enough visits and suitably shrinking step sizes, the estimate settles toward the expected return (Section 5.1).

$$V(S_t)\leftarrow V(S_t)+\alpha[G_t-V(S_t)]$$

TD(0). Split the return as $G_t=R_{t+1}+\gamma G_{t+1}$ and replace $G_{t+1}$ by the current estimate of the next state. The terminal state's value is 0. For a finite discounted task, or an episodic task with bounded expected episode length, suitable on-policy visits and step sizes give convergence in the tabular case (Sections 6.1 and 6.2).

$$\begin{aligned} Y_t&=R_{t+1}+\gamma V(S_{t+1}),\\ V(S_t)&\leftarrow V(S_t)+\alpha\,[Y_t-V(S_t)]. \end{aligned}$$

n-step TD. Let $h=\min(n,T-t)$ be the number of real rewards available before the episode ends. The target uses those rewards and borrows only at the endpoint, unless the endpoint is terminal (Section 7.1):

$$Y_t^{(n)}=\sum_{k=0}^{h-1}\gamma^kR_{t+k+1}+\begin{cases}\gamma^hV(S_{t+h}),&t+h<T,\\0,&t+h=T.\end{cases}$$

Corridor counts. Zero initial values, $\alpha=\gamma=1$, online updates in forward order. Monte Carlo credits all eight rooms after walk 1. Forward TD(0) credits the last $m$ rooms after walk $m$, so room 1 needs 8 walks. Three-step TD with the usual delayed updates and a terminal flush credits rooms 6 to 8 on walk 1, rooms 3 to 5 on walk 2 and rooms 1 and 2 on walk 3. These counts come from the update order and settings. They don't rank the methods in general, and backward replay would credit the whole corridor in one pass.

Choosing the horizon. Let $\varepsilon(s)=V(s)-v_\pi(s)$ be the estimation error. Before termination, the borrowed tail adds $\gamma^n\varepsilon(S_{t+n})$ to the target's error. The discount shrinks a given endpoint error as $n$ grows, but the endpoint itself changes with $n$, so this doesn't guarantee that bias or variance always rises or falls with the horizon. Noisy rewards, correlated transitions and the accuracy of different endpoint estimates all matter (Chapters 6 and 7).

So far we estimated values under a fixed policy. To improve the policy, a good outcome alone doesn't tell you whether an action helped, because the starting state may already have been promising. The advantage compares an action's expected return with the policy's usual return from that state:

$$A_\pi(s,a)=Q_\pi(s,a)-V_\pi(s).$$

Here $Q_\pi$ means taking $a$ first and then following $\pi$, and $V_\pi$ also averages over the first action. Generalized Advantage Estimation (GAE) estimates this credit from experience and an approximate state value $V$. Collect a rollout with a fixed policy, keep the data and $V$ fixed, and take one segment ending at $S_H$, with $\ell$ counting steps ahead:

$$\begin{aligned} \delta_t&=R_{t+1}+\gamma V(S_{t+1})-V(S_t),\\ \hat A_t&=\sum_{\ell=0}^{H-t-1}(\gamma\lambda)^\ell\delta_{t+\ell}. \end{aligned}$$

The parameter $\lambda$, between 0 and 1, sets how much later errors count. Adding the TD errors of one return length makes the intermediate values cancel, leaving that return minus the starting value, and GAE is a geometrically weighted mix of those return lengths (Schulman et al., Section 3, equations 14 to 16). It brings the same horizon tradeoff to action credit, and changing $\lambda$ doesn't guarantee a particular change in variance.

A small example: three transitions ending at a terminal state, $\gamma=1$, rewards $(0,0,4)$ and frozen values $(V(S_0),V(S_1),V(S_2),V(S_3))=(2,2,1,0)$. The errors are $(0,-1,3)$. With $\lambda=0.5$, the credit for $A_0$ is

At $\lambda=0$ only $\delta_0$ remains, so the credit is 0. At $\lambda=1$ the sum is $4-2=2$, the completed return minus the starting value. A value like $\lambda=0.95$ is a decay factor, not a 95% and 5% mixture.

The same sum has a backward recurrence, $\hat A_H=0$ and $\hat A_t=\delta_t+\gamma\lambda\hat A_{t+1}$. To apply it to a batch, split at every episode reset and use the last actual observation as $S_H$. Set $V(S_H)=0$ only at a true terminal state. A time limit that cuts an ongoing task, or a rollout cutoff, keeps its bootstrap value, and the trace still stops at the boundary, as in Spinning Up's finish_path.

# One segment, with frozen values and no episode reset inside it.
endpoint = 0 if true_terminal else V(last_actual_observation)
v[H] = endpoint
advantage[H] = 0
for t = H-1 down to 0:
    delta = R_(t+1) + gamma * v[t+1] - v[t]
    advantage[t] = delta + gamma * lambda * advantage[t+1]

That rule assumes you know whether an ending is real. Training runs usually stop every episode after a fixed number of steps, and that cutoff can mean two different things. Pardo et al. (2018) separate them.

The time limit is part of the task. Say the robot really has 14 moves to reach a goal. Then a state's value depends on how many moves are left, and if the state doesn't include the remaining time, two different situations look identical and the learner averages targets that disagree. Their fix is to put the remaining time in the input. In their Last Moment example, the agent can stay for reward 0 or jump into a trap that pays +1 once and then −1 on every step until the end. The best plan is to stay and jump on the very last step. An agent that can't see the clock can't tell when the last step is, and the paper notes that even Monte Carlo methods, which don't bootstrap, can't learn the right plan without the time input.

The time limit is only for training. If the task would really go on, the cutoff isn't an end. Treating it as terminal teaches the learner that states near the cutoff have less future ahead, so their values come out wrong even though nothing about them changed. Their fix is partial-episode bootstrapping: at the cutoff, use $R+\gamma V(S')$ instead of $R$.

My game Breaking Bellman has a pass-or-fail goal grid where this seems to happen: 14 moves, reward 1 at the goal and 0 otherwise, no discount. PPO with a learned value and GAE solved 13.3% of the tasks, and its value estimate at the start was about 1.44, above the largest possible return of 1. Scoring actions with real completed returns instead solved 95%, and with no baseline at all, 100% (3 seeds, simulation). The game's own reading is that the value bootstraps through the time limit and can't see the clock. Those are two different problems. The start value above 1 fits bootstrapping past a real ending, since no return in this task can exceed 1. Failing on the timed task also fits a missing clock, as in the Last Moment example, but the log has no run with the remaining time in the input, so that part is unconfirmed.