📘

Value Iteration Bellman Error

MediumReinforcement Learning 📚 RL 1: Foundations

Problem Statement

Value iteration converges when the largest change across states drops below a threshold. Given the values before and after a sweep, compute the max-norm (sup-norm) difference:

$\|V_{new} - V_{old}\|_\infty = \max_s |V_{new}(s) - V_{old}(s)|$

Implement bellman_error(v_old, v_new) returning a float. An empty pair returns 0.0.

Example:

Input:

bellman_error([0.0, 0.0], [0.1, -0.3])

Output:

0.3

Reasoning:

Verify that the input lists are non-empty to ensure the calculation proceeds, as an empty state space would default the error to $0.0$ .
Pair the corresponding values from the old and new value functions to evaluate the change at each state: $(0.0, 0.1)$ and $(0.0, -0.3)$ .
Compute the absolute difference for the first state to measure the magnitude of change: $|0.1 - 0.0| = 0.1$ .
Compute the absolute difference for the second state: $|-0.3 - 0.0| = 0.3$ .
Determine the max-norm by selecting the largest of these differences, which represents the maximum convergence error: $\max(0.1, 0.3) = 0.3$ .
The final output is 0.3

Constraints:

len(v_old) == len(v_new).
Return the maximum absolute per-state difference.

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

In Reinforcement Learning, Value Iteration is a dynamic programming algorithm that repeatedly applies the Bellman optimality operator to update state values. At each iteration, the value of every state is revised based on the best expected return achievable from that state. The algorithm is guaranteed to converge to the optimal value function $V^*$ because the Bellman operator is a contraction mapping under the max-norm (sup-norm) metric.

The max-norm (or $\ell_\infty$ norm) of a vector $x$ is defined as $\|x\|_\infty = \max_i |x_i|$ . In the context of value iteration, the Bellman error measures the largest absolute change in any state's value between two consecutive sweeps. This single scalar tells you whether the value function has stabilized: if the error drops below a small threshold $\epsilon$ , the values are considered converged.

This problem is essentially a vector operation: given two arrays (or dictionaries) of equal length representing $V_{old}$ and $V_{new}$ , compute the maximum absolute element-wise difference. It is a foundational utility in RL implementations because convergence checks, early stopping, and logging all rely on this metric.

2. Algorithm Approach

The approach is a straightforward element-wise comparison followed by a reduction to a single maximum value:

Iterate over all states in parallel (zip the two collections).
For each state, compute the absolute difference $|V_{new}(s) - V_{old}(s)|$ .
Track the maximum of these differences across all states.
Return that maximum as a float.

This is a classic map-reduce pattern: map the absolute-difference function over paired elements, then reduce with a max operation. No sorting, recursion, or auxiliary data structures are needed.

3. Step-by-Step Strategy

👑

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.