📘

Full Value Iteration to Convergence

HardReinforcement Learning 📚 RL 1: Foundations

Problem Statement

Run value iteration to convergence on a finite MDP and return the optimal values. The MDP is given as mdp[s] = list of actions, each {"reward": r, "probs": [...], "next": [...]}. Start from all-zero values and repeat synchronous optimality sweeps until the max-norm change is below theta, or max_iters is reached.

$V(s) = \max_a \left[ r + \gamma \sum_i probs_i\, V(next_i) \right]$

Implement value_iteration(mdp, gamma, theta, max_iters) returning the optimal values (list of floats, rounded is not required).

Example:

Input:

value_iteration([[{"reward":0.0,"probs":[1.0],"next":[0]}]], 0.9, 1e-9, 1000)

Output:

[0.0]

Reasoning:

Initialization: The MDP contains a single state ( $n=1$ ). The value function $V$ is initialized to all zeros, so $V[0] = 0.0$ .
First Iteration (Sweep): For state 0, the only available action has a reward of $0.0$ and transitions to state 0 with probability $1.0$ . The Q-value is calculated as $Q = 0.0 + 0.9 \times (1.0 \times V[0]) = 0.0 + 0.9 \times 0.0 = 0.0$ . Since this is the only action, the new value for state 0 is $\text{new\_V}[0] = 0.0$ .
Convergence Check: The maximum change in values is $\Delta = |0.0 - 0.0| = 0.0$ . This change is compared against the threshold $\theta = 10^{-9}$ . Since $0.0 < 10^{-9}$ , the convergence criterion is met immediately after the first iteration.
Termination: The loop breaks because the values have stabilized (the change is below the threshold). The algorithm does not need to perform further iterations.
The final output is [0.0]

Constraints:

Synchronous updates (a full sweep uses the previous sweep's values).
Stop when max_s |V_new - V_old| < theta or after max_iters sweeps.
0 <= gamma < 1 guarantees convergence.

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

Value Iteration is a dynamic programming algorithm for solving Markov Decision Processes (MDPs). It computes the optimal state-value function $V^*(s)$ , which represents the maximum expected cumulative discounted reward obtainable from state $s$ under the optimal policy. The core idea is to iteratively apply the Bellman optimality equation:

V_{k+1}(s) = \max_a \left[ r(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V_k(s') \right]

where $\gamma \in [0,1)$ is the discount factor, $r(s,a)$ is the immediate reward, and $P(s'|s,a)$ is the transition probability to next state $s'$ . Because $\gamma < 1$ , the sequence $\{V_k\}$ is a contraction mapping in the max-norm, guaranteeing convergence to $V^*$ as $k \to \infty$ .

The algorithm starts from an arbitrary initialization (here, all zeros) and performs synchronous updates: all states are updated simultaneously using the previous iteration's values. After each full sweep, you check whether the maximum absolute change across all states falls below a tolerance $\theta$ . If so, the values have converged to within $\theta$ of the true optimal values. The number of iterations needed is bounded by $\frac{\log(1/\theta)}{1-\gamma}$ , which can be large when $\gamma$ is close to 1.

In this problem, the MDP is provided in a structured dictionary format where each state maps to a list of actions, and each action specifies its reward, transition probabilities, and corresponding next states. Your task is to faithfully implement the iterative sweep and convergence check.

2. Algorithm Approach

The approach is a straightforward iterative fixed-point method:

Initialize $V(s) = 0$ for all states $s$ .
Repeat up to max_iters times:
For each state $s$ , compute the Bellman optimality update by taking the max over all actions of the immediate reward plus the discounted expected next-state value.
Track the maximum absolute difference between the new and old values across all states.
If this max difference is below theta, break early (convergence reached).
Return the final value array.

This is a synchronous (Jacobi-style) update: you must use the values from the previous iteration when computing all new values, not partially updated values from the current sweep.

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.