📘

Async In-Place Value Iteration Sweep

MediumReinforcement Learning 📚 RL 1: Foundations

Problem Statement

Perform one in-place (asynchronous) value-iteration sweep: states are updated left to right, and each update immediately uses the freshest values of earlier states. For each state you are given a list of actions, each {"reward": r, "probs": [...], "next": [...]} where next are next-state indices aligned with probs.

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

Mutate and return the values list. Implement vi_sweep_inplace(states, gamma, V).

Example:

Input:

vi_sweep_inplace([[{"reward":0.0,"probs":[1.0],"next":[1]}],[{"reward":1.0,"probs":[1.0],"next":[1]}]], 0.9, [0.0, 0.0])

Output:

[0.0, 1.0]

Reasoning:

Initialize State 0: The sweep begins with state $s=0$ . It has one action with reward $r=0.0$ , probability $1.0$ , and next state $1$ . Since the update is in-place, it uses the current value of state 1, which is initially $V[1] = 0.0$ .
Compute Value for State 0: Calculate the Q-value for the single action: $Q = 0.0 + 0.9 \times (1.0 \times 0.0) = 0.0$ . This becomes the new value for state 0, so $V[0]$ is updated to $0.0$ .
Process State 1: Move to state $s=1$ . It has one action with reward $r=1.0$ , probability $1.0$ , and next state $1$ (a self-loop). The calculation uses the current value of state 1, which is still $V[1] = 0.0$ because state 1 has not been updated yet in this sweep.
Compute Value for State 1: Calculate the Q-value: $Q = 1.0 + 0.9 \times (1.0 \times 0.0) = 1.0$ . This becomes the new value for state 1, so $V[1]$ is updated to $1.0$ .
The final output is [0.0, 1.0]

Constraints:

len(states) == len(V); update states 0..n-1 in order, in place.
Later states in the same sweep see earlier states' new values.
Return the same (mutated) 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

Value Iteration is a core algorithm in Reinforcement Learning for solving Markov Decision Processes (MDPs). It iteratively refines a value function $V(s)$ , which estimates the expected cumulative reward starting from state $s$ . The update rule is derived from the Bellman optimality equation:

$V(s) \leftarrow \max_a \left[ r_a + \gamma \sum_i p_i \, V(s_i) \right]$

Here, $r_a$ is the immediate reward for action $a$ , $\gamma$ is the discount factor, $p_i$ is the probability of transitioning to next state $s_i$ , and $V(s_i)$ is the value of that next state. The $\max_a$ term selects the action that yields the highest expected return.

In standard (synchronous) value iteration, all states are updated simultaneously using the previous iteration's values. This requires two arrays: one for old values and one for new values. Asynchronous (in-place) value iteration differs by updating states sequentially (e.g., left to right) and immediately using the freshest available values. If state $j < i$ has already been updated in the current sweep, state $i$ uses the new $V(j)$ ; otherwise, it uses the old value. This can accelerate convergence because information propagates faster through the state space.

The key distinction here is in-place mutation: you must modify the input list V directly rather than creating a new list. This is both a memory optimization and a semantic requirement of the problem.

2. Algorithm Approach

The approach is a single pass over all states in order:

Iterate through each state index $s$ from $0$ to $n-1$ .
For each state, evaluate every available action.
For each action, compute the expected return: immediate reward plus $\gamma$ times the weighted sum of next-state values.
Select the action with the maximum expected return.
Update $V[s]$ in place with this maximum value.

Because updates happen left to right, when computing the expected return for state $s$ , any next state with index $< s$ will already reflect the current sweep's updates, while next states with index $\geq s$ will still hold values from the previous sweep (or initial values). This is the defining characteristic of asynchronous in-place updates.

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.