TD(0) Prediction Over a Transition Stream

Problem Statement

Run TD(0) over a recorded stream of transitions and return the updated value table.

Background

Monte Carlo prediction has to wait for the episode to end before it can update anything. TD(0) does not wait: after every single transition it forms a target from the reward it just received plus its own current estimate of where it landed.

$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \qquad V(S_t) \leftarrow V(S_t) + \alpha\, \delta_t$

$\delta_t$ is the TD error — the surprise, the gap between what you predicted and what one step of reality plus your own next prediction say. Using your own estimate inside the target is bootstrapping, and it is what makes TD biased early on but dramatically lower variance than waiting for a full return.

The detail that breaks implementations: at a terminal transition the target is just the reward. $V(\text{terminal}) = 0$ by definition, so bootstrapping off the state after termination is not merely wrong, it leaks value into episodes that already ended. Every real implementation gates the bootstrap term on a done flag.

The updates are online: each transition uses the table as updated by all previous transitions, so revisiting a state within the stream compounds.

Your Task

Implement:

def td0_prediction(v_init, transitions, alpha, gamma):
    ...

• v_init — a list of floats, the starting value table (do not mutate it).
• transitions — a list of (s, r, s_next, done) tuples, in order. done is a bool.
• alpha — step size.
• gamma — discount factor.

Return the final table as a list of floats.

Input / Output Format

A list of floats and a list of tuples in; a list of floats out, rounded to 4 decimals by the grader.

Sample

v = [0.0, 0.0, 0.0]
transitions = [(0, 1.0, 1, False), (1, 2.0, 2, True)]
print([round(x, 4) for x in td0_prediction(v, transitions, 0.5, 0.9)])

Output:

[0.5, 1.0, 0.0]

First transition: target 1.0 + 0.9*0.0 = 1.0, so V(0) = 0 + 0.5(1.0 - 0) = 0.5*. Second transition is terminal, so the target is just 2.0 and V(1) = 0 + 0.5(2.0 - 0) = 1.0*.