📘

TD(0) Prediction Over a Transition Stream

EasyReinforcement Learning 📚 RL 1: Foundations

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*.

Example:

Input:

td0_prediction([0.0, 0.0, 0.0], [(0, 1.0, 1, False), (1, 2.0, 2, True)], 0.5, 0.9)

Output:

[0.5, 1.0, 0.0]

Reasoning:

The first transition is non-terminal so the target is 1.0 + 0.9V(1) = 1.0, giving V(0) = 0 + 0.5(1.0 - 0) = 0.5. The second is terminal so the target is just the reward 2.0, giving V(1) = 0 + 0.5*(2.0 - 0) = 1.0. V(2) is never the source state of a transition, so it stays 0.

Constraints:

1 <= len(v_init) <= 1000, 0 <= len(transitions) <= 100000
0.0 <= alpha <= 1.0, 0.0 <= gamma <= 1.0
When done is True the target is r alone — do not add gamma * v[s_next].
Updates are applied online, in the order given.
v_init must not be modified; return a new list.

More from RL 1: Foundations

GAE Over a Full TrajectoryHard PPO Clipped Objective (Single Sample)Medium TD Residuals for GAEMedium Return Standardization BaselineMedium REINFORCE Loss TermMedium

1. Background Knowledge

Temporal-Difference (TD) learning is a fundamental method in reinforcement learning that combines ideas from Monte Carlo methods and dynamic programming. Unlike Monte Carlo methods, which wait until the end of an episode to update value estimates based on the total return, TD methods update estimates after every single step. This is achieved through bootstrapping, where the estimate of a state is updated based on the estimate of the next state. The core mechanism is the TD error ( $\delta$ ), which measures the difference between the predicted value and the observed outcome.

The TD(0) update rule for a state $S_t$ is defined as:

V(S_t) \leftarrow V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]

Here, $\alpha$ is the learning rate (step size), $\gamma$ is the discount factor, $R_{t+1}$ is the immediate reward, and $V(S_{t+1})$ is the current estimate of the next state's value. The term in the brackets is the TD error. This update is online, meaning the value table is modified immediately after each transition, and subsequent transitions in the same stream will use these updated values.

A critical distinction in TD learning is handling terminal states. When a transition leads to a terminal state (indicated by done=True), the episode ends. By definition, the value of a terminal state is zero ( $V(\text{terminal}) = 0$ ). Therefore, the target for a terminal transition is simply the immediate reward $R_{t+1}$ , not $R_{t+1} + \gamma V(S_{t+1})$ . Failing to account for this leads to incorrect value propagation, as it would incorrectly bootstrap from a non-existent next state.

2. Algorithm Approach

The problem requires implementing an online TD(0) prediction algorithm over a stream of transitions. The approach is iterative and stateful:

Initialize: Create a copy of the initial value table v_init to avoid mutating the input. This copy will be updated in-place.
Iterate: Loop through each transition in the transitions list sequentially.
Compute Target: For each transition $(s, r, s_{next}, done)$ , calculate the TD target.

If done is False, the target is $r + \gamma \cdot V(s_{next})$ .
If done is True, the target is just $r$ .

Update Value: Calculate the TD error $\delta = \text{target} - V(s)$ and update $V(s)$ using the learning rate $\alpha$ .
Return: After processing all transitions, return the updated value table.

This approach leverages the online nature of TD learning, where each update affects future updates within the same stream.

3. Step-by-Step Strategy

Copy Input: Start by creating a mutable copy of v_init. Do not modify the original list.

v = list(v_init)

Loop Through Transitions: Iterate over each tuple (s, r, s_next, done) in transitions.
Determine Target:

Check the done flag.
If done is True, set target = r.
If done is False, set target = r + gamma * v[s_next]. Note that v[s_next] is the current value from the table, which may have been updated by previous transitions.

Calculate TD Error: Compute $\delta = \text{target} - v[s]$ .
Update State Value: Update the value of state s using the formula:

v[s] = v[s] + alpha * delta

Return Result: After the loop completes, return the list v.

4. Common Pitfalls

Mutating Input: Modifying v_init directly instead of working on a copy. This can cause side effects and fail tests that check for input immutability.
Ignoring done Flag: Using the bootstrap term $\gamma V(S_{t+1})$ even when done is True. This incorrectly adds value from a terminal state, leading to inflated value estimates.
Using Old Values: Forgetting that the update is online. If you calculate all targets first and then update, you are implementing batch TD, not online TD. The update to $V(s)$ must happen immediately so that subsequent transitions see the new value.
Index Errors: Ensuring that s and s_next are valid indices for the value table v. The problem statement implies valid inputs, but defensive coding is good practice.
Rounding: The problem states the grader rounds to 4 decimals. Do not round intermediate values; only the final output is rounded by the grader. Rounding during updates can accumulate errors.

5. Time & Space Complexity

Time Complexity: $O(N)$ , where $N$ is the number of transitions. Each transition is processed in constant time $O(1)$ , involving a few arithmetic operations and list accesses.
Space Complexity: $O(S)$ , where $S$ is the number of states (length of v_init). We create a copy of the value table, which requires space proportional to the number of states. The input transitions list is not copied, so its space is not counted in the auxiliary space complexity.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.