📘

TD(0) Over a Transition Stream

MediumReinforcement Learning 📚 RL 1: Foundations

Problem Statement

Run TD(0) prediction for a single state over a stream of (reward, v_next) transitions, starting from value v0, learning rate alpha, discount gamma. Apply updates sequentially and return the final value.

$V \leftarrow V + \alpha\,[\, r + \gamma\, v_{next} - V\,]$

Implement td0_stream(v0, transitions, gamma, alpha) where transitions is a list of (reward, v_next) pairs.

Example:

Input:

td0_stream(0.0, [(1.0, 0.0), (1.0, 0.0)], 0.9, 0.5)

Output:

0.75

Reasoning:

Initialize the value estimate $V$ to the starting value $v_0 = 0.0$ .
Process the first transition $(r=1.0, v_{next}=0.0)$ : calculate the TD error as $1.0 + 0.9 \cdot 0.0 - 0.0 = 1.0$ , then update $V$ by adding $\alpha \cdot \text{error} = 0.5 \cdot 1.0$ , resulting in $V = 0.0 + 0.5 = 0.5$ .
Process the second transition $(r=1.0, v_{next}=0.0)$ : calculate the new TD error as $1.0 + 0.9 \cdot 0.0 - 0.5 = 0.5$ , then update $V$ by adding $\alpha \cdot \text{error} = 0.5 \cdot 0.5 = 0.25$ , resulting in $V = 0.5 + 0.25 = 0.75$ .
The final output is 0.75

Constraints:

Apply transitions in order.
Empty stream returns v0 unchanged.
Return a float.

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 family of reinforcement learning methods that update value estimates using a "bootstrapping" principle: the current estimate is nudged toward a target that combines the immediate reward with the next state's value estimate, rather than waiting for a full episode to finish. TD(0) is the simplest member of this family. Its update rule is

V \leftarrow V + \alpha\,[\, r + \gamma\, v_{next} - V\,]

where $r$ is the observed reward, $v_{next}$ is the value of the successor state, $\gamma \in [0,1]$ is the discount factor, and $\alpha \in (0,1]$ is the learning rate. The term $r + \gamma\, v_{next} - V$ is called the TD error; it measures the surprise between what the current value predicts and what the environment actually delivered plus the discounted future.

In a streaming setting, transitions arrive one at a time and the agent must update its value estimate immediately after each transition. This is different from batch learning, where you might average over many samples. Here, the order of updates matters because each new value becomes the starting point for the next update. The discount factor $\gamma$ controls how much future rewards are valued relative to immediate ones: $\gamma = 0$ makes the agent myopic, while $\gamma \to 1$ makes it far-sighted.

The key insight is that TD(0) is an online, stochastic approximation algorithm. It does not require knowledge of the full transition dynamics or a complete trajectory; it only needs the current state's value, the immediate reward, and the next state's value. This makes it suitable for large or infinite-horizon problems where storing entire episodes is impractical.

2. Algorithm Approach

The problem is a straightforward sequential update loop. You maintain a single scalar value estimate $V$ that starts at $v0$ . For each transition in the stream, you:

Extract the reward $r$ and the next-state value $v_{next}$ .
Compute the TD error: $\delta = r + \gamma\, v_{next} - V$ .
Update the value: $V \leftarrow V + \alpha\, \delta$ .

After processing all transitions, return the final $V$ . There is no need for additional data structures, bookkeeping, or convergence checks—the problem asks for the exact result of applying the updates in order.

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.