Exercises — Temporal Difference learning

• $\alpha$ = learning rate — the fraction of the error we actually apply. Small $\alpha$ = timid nudges; $\alpha =1$ = throw away the old guess entirely.
• $\gamma$ = discount factor — how much a reward one step in the future is worth now. $\gamma =1$ means future rewards count fully; $\gamma =0$ means only the immediate reward matters.
• ${\delta }_t$ = TD error = $R_{t+1}+\gamma V(S_{t+1})-V(S_t)$ — the surprise: target minus old estimate.
• $V(S_t)$ = value estimate of the state we are currently leaving — our best guess of total future (discounted) reward from that state.

The TD target is reward + discounted next-state value — that is keystroke (1) of the workhorse update, stopped before we subtract or step: $\text{target}=R_{t+1}+\gamma V(S_{t+1})=2+0.9\times 10=2+9=11.$ We stop here — the target is just the "improved estimate" we will later chase.

Only (c). TD is model-free like Monte Carlo, so (a) is false. And it bootstraps like Dynamic Programming, updating every step, so it does not need complete episodes — (b) is false.

We are just running the three keystrokes of the workhorse update, so first write it down and then substitute — never plug numbers blind. (1) Build the target (reward + discounted next value): $\text{target}=R_{t+1}+\gamma V(S_{t+1})=-1+0.9\times 0=-1.$ (2) Subtract the old guess to get the error — this is why we compute a target at all: to measure how wrong we were: ${\delta }_t=\text{target}-V(S_t)=-1-0=-1.$ (3) Step a fraction $\alpha$ along ${\delta }_t$ — why only a fraction? so one noisy sample never overwrites everything we knew: $V(S_t)\leftarrow V(S_t)+\alpha {\delta }_t=0+0.1\times (-1)=-\mathrm{0.1.}$ We were too optimistic (guessed $0$); the step actually cost $-1$, so we lower the estimate.

Note $V(C)=0$ because $C$ is terminal (see the definition above). Each transition runs the same three keystrokes: build target, subtract old guess, step by $\alpha$.

$A\to B$ (reward $0$):

• (1) target $=R+\gamma V(B)=0+1\times 0.8=0.8$ — why $V(B)$ and not the true future? because bootstrapping means we trust our current best guess of what follows.
• (2) error $\delta =\text{target}-V(A)=0.8-0.5=0.3$ (positive — good news, $A$ leads somewhere better than we thought).
• (3) step $V(A)\leftarrow 0.5+0.1\times 0.3=\mathrm{0.53.}$

$B\to C$ (reward $+1$):

• (1) target $=R+\gamma V(C)=1+1\times 0=1$ (the $\gamma V(C)$ term vanishes because $C$ is terminal).
• (2) error $\delta =1-0.8=\mathrm{0.2.}$
• (3) step $V(B)\leftarrow 0.8+0.1\times 0.2=\mathrm{0.82.}$

The picture in words (no figure needed): for $V(A)$, the old guess $0.5$ sits below the target $0.8$; the update carries it only up to $0.53$ — one-tenth of the $0.3$ gap. For $V(B)$, old $0.8$ vs target $1.0$; the step reaches just $0.82$. In both cases the new value never touches the target, because $\alpha =0.1$ crosses only a tenth of the distance each time. That "always fall short of the target" behaviour is exactly what keeps a single noisy sample from hijacking the estimate.

Target every time is $R+\gamma V(\text{terminal})=1+1\times 0=1$ (the next state is terminal, so its value is $0$). Substituting the fixed target $1$ into the workhorse update collapses it to $V\leftarrow V+0.5(1-V)$, which closes half the remaining gap each visit — why half? because $\alpha =0.5$ is literally "step half-way to the target."

• Visit 1: $V=0+0.5(1-0)=\mathrm{0.5.}$
• Visit 2: $V=0.5+0.5(1-0.5)=\mathrm{0.75.}$
• Visit 3: $V=0.75+0.5(1-0.75)=\mathrm{0.875.}$ Notice it approaches the true value $1$ geometrically but never overshoots — the hallmark of a fixed target with $\alpha <1$.

Recall $G_t$ is the return: the actual total discounted reward collected from a state to episode end. Here every path ends in the single reward $+10$, and with $\gamma =1$ nothing is shrunk, so the return from any state on the corridor is $G=10$.

Monte Carlo: waits for the full return $G=10$, then updates every visited state once: $V(s_0)\leftarrow 0+0.5(G-0)=0.5(10)=5$ after episode 1. MC reaches $s_0$ immediately (only because $\gamma =1$ carried the raw return back).

TD: in episode 1 only the last state $s_{99}$ sees the reward; $V(s_{99})\leftarrow 0+0.5(10-0)=5$. All earlier states still update toward next states that are still $0$, so they stay $0$. Value crawls back one state per episode.

Inline mini-derivation of "one state per episode": let $s_k$ mean the state $k$ steps before the goal, so $s_1$ is adjacent to the goal. The reward only enters through a non-zero next-state value. In the TD update $V(s_k)\leftarrow V(s_k)+\alpha [R+\gamma V(s_{k-1})-V(s_k)]$ (here every step-reward on the corridor is $0$ except the final one), the term $\gamma V(s_{k-1})$ can only be non-zero once $s_{k-1}$ itself has already become non-zero. So:

• Episode 1: only $s_1$ (next to the goal) sees the $+10$ reward → $V(s_1)$ becomes non-zero, all others stay $0$.
• Episode 2: $s_2$ now finds $V(s_1)\ne 0$ in its target → $V(s_2)$ becomes non-zero.
• Episode $n$: exactly $V(s_n)$ turns non-zero for the first time — the "wavefront" of learning advances one state per episode.

Counting from the goal, the start $s_0$ is the state $100$ steps away, so $V(s_0)$ first becomes non-zero at episode 100. The figure below draws this wavefront: after each episode the shaded (learned) region extends one cell further back from the green goal.

Reading it: MC propagates in one shot here but pays with high variance (the whole noisy return); TD is slower to reach far states in this deterministic chain but each update uses low-variance one-step information. TD(λ) blends the two speeds.

The next state after a pull is terminal, so $V(S_{t+1})=0$ (terminal-value definition).

• Pays 10: $\delta =10+\gamma \cdot 0-5=10-5=+5.$
• Pays 0: $\delta =0-5=-5.$ Even with a perfect estimate the individual errors are $\pm 5$ — they never vanish, because the environment is random. What vanishes is the expected error: $\mathbb{E}[\delta ]=0.5(+5)+0.5(-5)=0.$ So convergence means $\mathbb{E}[{\delta }_t]\to 0$, not ${\delta }_t\to 0$.

$\alpha =1$ means $V\leftarrow V+1\cdot \delta =V+\delta =$ target. The old value is thrown away.

• After "pays 10": $V\leftarrow 10+0=10.$
• Then "pays 0": $V\leftarrow 0+0=0.$ A perfectly-known value of $5$ ping-pongs between $10$ and $0$ — pure noise, no memory. Small $\alpha$ instead averages samples, so the estimate stays near $5$.

$C$ is terminal so $V(C)=0$ throughout.

Episode 1

• $A\to B$: target $=0+V(B)=0$; $\delta =0-0=0$; $V(A)=0$.
• $B\to C$: target $=1+V(C)=1$; $\delta =1-0=1$; $V(B)=0+0.1\cdot 1=0.1$.
• End of ep 1: $V(A)=0,V(B)=0.1$.

Episode 2

• $A\to B$: target $=0+V(B)=0.1$; $\delta =0.1-0=0.1$; $V(A)=0+0.1\cdot 0.1=0.01$.
• $B\to C$: target $=1+0=1$; $\delta =1-0.1=0.9$; $V(B)=0.1+0.1\cdot 0.9=0.19$.
• End of ep 2: $V(A)=0.01,V(B)=0.19$.

Watch the cascade: $B$ had to learn about the reward first (ep 1); only then could $A$ inherit value from $B$ (ep 2). This backward "teaching" is bootstrapping in action.

Recall $G_A$ is the return from state $A$ — the actual total (here undiscounted, $\gamma =1$) reward collected from $A$ to the end — and $G_B$ likewise from $B$: $G_A=r_{AB}+r_{BC}=0+1=1,G_B=r_{BC}=1.$

Episode 1 (both start at 0):

• $V(A)\leftarrow 0+0.1(G_A-0)=0.1(1)=\mathrm{0.1.}$
• $V(B)\leftarrow 0+0.1(G_B-0)=0.1(1)=\mathrm{0.1.}$

Episode 2:

• $V(A)\leftarrow 0.1+0.1(1-0.1)=0.1+0.09=\mathrm{0.19.}$
• $V(B)\leftarrow 0.1+0.1(1-0.1)=\mathrm{0.19.}$

Comparison: After 2 episodes MC gives $V(A)=0.19$ vs TD's $0.01$. MC pushed value to $A$ immediately (it used the whole return $G_A=1$), while TD needed the signal to walk back through $B$ first. In a noisy environment this MC speed would come bundled with higher variance — that is the Bias-Variance Tradeoff TD is designed to soften.

The goal $(2,2)$ is terminal, so $V(2,2)=0$. Every transition runs the three keystrokes; because all next-state values are still $0$ in this first episode, every target is the same: $\text{target}=-1+0.9V(\text{next})=-1+0.9\times 0=-1,\delta =-1-0=-1,\text{step}=0.1\times (-1)=-\mathrm{0.1.}$ Applying that to each visited state in turn:

• $(0,0)\to (0,1)$: $V(0,0)\leftarrow 0+0.1(-1)=-0.1.$
• $(0,1)\to (0,2)$: $V(0,1)\leftarrow 0+0.1(-1)=-0.1.$
• $(0,2)\to (1,2)$: $V(0,2)\leftarrow 0+0.1(-1)=-0.1.$
• $(1,2)\to (2,2)$: next state $(2,2)$ is terminal ($V=0$), so still target $=-1$; $V(1,2)\leftarrow 0+0.1(-1)=-0.1.$

Final answer: all four visited non-terminal states end episode 1 at $V=-0.1$; the terminal goal stays at $V=0$.

The figure below shows the grid: the four visited cells are shaded blue and each carries the label $V=-0.1$, the red arrows trace the path $(0,0)\to (0,1)\to (0,2)\to (1,2)\to (2,2)$, and the green goal cell is marked $V=0$. Visually, the whole path is flat at $-0.1$ — the true landscape (states nearer the goal should be less negative) has not appeared yet; it only emerges over many episodes as these $-0.1$ values feed back into future targets.

Start ep 2 with $V=-0.1$ at each of $(0,0),(0,1),(0,2),(1,2)$.

$(0,0)\to (0,1)$: target $=-1+0.9V(0,1)=-1+0.9(-0.1)=-1-0.09=-\mathrm{1.09.}$ $\delta =-1.09-(-0.1)=-\mathrm{0.99.}$ $V(0,0)\leftarrow -0.1+0.1(-0.99)=-0.1-0.099=-\mathrm{0.199.}$

$(0,1)\to (0,2)$: ($V(0,1)$ is still $-0.1$ when we leave it, next is $(0,2)=-0.1$) target $=-1+0.9(-0.1)=-\mathrm{1.09.}$ $\delta =-1.09-(-0.1)=-\mathrm{0.99.}$ $V(0,1)\leftarrow -0.1+0.1(-0.99)=-\mathrm{0.199.}$

Now the values are drifting more negative because the bootstrapped future value has itself become negative — the true cost-to-go is genuinely below $-0.1$. This is the value landscape sinking toward its correct (negative) fixed point given by the Bellman Equations.

An action-value $Q(s,a)$ is "the value of being in state $s$ and taking action $a$" — same idea as $V(s)$ but pinned to a chosen action. Replace $V(S_t)$ by $Q(S_t,A_t)$ in the workhorse update and it still has the exact TD skeleton — old guess, reward, discounted next value, step $\alpha$: $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma Q(S_{t+1},a^{\star })-Q(S_t,A_t)].$ So both are TD; the only thing that differs between them is which next action $a^{\star }$ goes into the bootstrapped term:

• SARSA uses $a^{\star }=A_{t+1}$, the action actually taken next (on-policy). Written out: $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)].$
• Q-Learning uses $a^{\star }=\arg {\max }_{a}Q(S_{t+1},a)$, the greedy best action (off-policy): $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma {\max }_{a}Q(S_{t+1},a)-Q(S_t,A_t)].$ The single differing symbol: ${\max }_a$ (Q-Learning) versus the chosen action $A_{t+1}$ (SARSA) inside the bootstrap. Everything else — the online-per-step update, the bootstrapping, the $R+\gamma (\cdots )-Q$ shape — is inherited straight from TD(0). For large state spaces the lookup table $Q$ is swapped for a learned function, giving Value Function Approximation.

TD target is R plus what, times gamma? ::: The next-state value $V(S_{t+1})$ (only the future term is discounted). Does a perfect estimate give zero TD error every step? ::: No — only the expected error is zero; single steps fluctuate with environment noise. What does $\alpha =1$ do to a good estimate? ::: Overwrites it with a single noisy target, destroying memory. Why does value crawl back one state per episode in a deterministic chain? ::: Because each state can only learn from a next state that has already learned — the bootstrap chain. Which symbol separates Q-Learning from SARSA in the target? ::: The next action used — greedy ${\max }_a$ (Q-Learning) vs actual $A_{t+1}$ (SARSA).