Value Iteration streamlines the search for optimal state values by alternating between two operations: optimizing the policy relative to current value estimates, and updating those estimates using the newly identified greedy actions. Unlike standard Bellmen expectation equations, the optimality variant incorporates a maximization operator across the entire action space:

v<sub>*</sub>(s) = max<sub>a ∈ A</sub> Σ<sub>s', r</sub> p(s', r | s, a) [r + γ v<sub>*</sub>(s')]

A frequent conceptual hurdle involves the iterative sequence V<sub>k</sub>. Prior to convergence, V<sub>k</sub> functions merely as an uninitialized vector of scalar approximations rather than a formally defined state-value distribution. The algorithm derives its name from this progressive refinement process, which transforms arbitrary initial guesses into the true optimal value function through successive backups.

The component-wise update procedure operates in two synchronized steps:

1. Greedy Policy Extraction: Identify the action maximizing expected return for each state based on current value estimates.
2. Value Function Backup: Assign each state the maximum discounted reward attainable from its successor states.

The following implementation demonstrates this mechanism applied to a constrained grid-navigation environment.

Python Implementation

import numpy as np
import os
import time

# Environment constants
MOVE_UP, MOVE_DOWN, MOVE_LEFT, MOVE_RIGHT = 0, 1, 2, 3
ACTION_MAP = {0: '↑', 1: '↓', 2: '←', 3: '→', 4: 'Stay'}
OBSTACLE_MARKER = '×'
GOAL_MARKER = '●'
FREE_SPACE = '□'
DEFAULT_STEP_PENALTY = -1.0
OBSTACLE_PENALTY = -100.0
GOAL_REWARD = 20.0


def compute_transition(grid_state, action_idx, map_layout):
    rows, cols = len(map_layout), len(map_layout[0])
    curr_r, curr_c = grid_state
    next_r, next_c = curr_r, curr_c
    penalty = DEFAULT_STEP_PENALTY

    if action_idx == MOVE_UP: next_r -= 1
    elif action_idx == MOVE_DOWN: next_r += 1
    elif action_idx == MOVE_LEFT: next_c -= 1
    elif action_idx == MOVE_RIGHT: next_c += 1

    # Boundary enforcement and obstacle handling
    if not (0 <= next_r < rows and 0 <= next_c < cols):
        pass  
    elif map_layout[next_r][next_c] == OBSTACLE_MARKER:
        penalty = OBSTACLE_PENALTY
    elif map_layout[next_r][next_c] == GOAL_MARKER:
        penalty = GOAL_REWARD

    # Coordinate clamping
    next_r = max(0, min(rows - 1, next_r))
    next_c = max(0, min(cols - 1, next_c))

    return (next_r, next_c), penalty


class DPGridSolver:
    def __init__(self, height: int, width: int, num_actions: int = 5):
        self.height, self.width, self.n_actions = height, width, num_actions
        self.action_symbols = {i: sym for i, sym in ACTION_MAP.items() if i < num_actions}
        
        # Initialize value estimates and Q-tables randomly
        self.value_estimates = np.random.randn(height, width)
        self.q_tables = np.random.randn(height, width, num_actions)
        self.greedy_policy = np.random.randint(num_actions, size=(height, width))

    def render_policy(self):
        for row in self.greedy_policy.tolist():
            print(' '.join(self.action_symbols[idx] for idx in row))

    def visualize_path(self, start_pos, end_pos, layout):
        assert all(0 <= x < n for x, n in zip(start_pos, (self.height, self.width)))
        assert all(0 <= x < n for x, n in zip(end_pos, (self.height, self.width)))
        
        r, c = start_pos
        steps = 0
        while (r, c) != end_pos and steps < self.height * self.width:
            layout[r][c] = self.action_symbols[self.greedy_policy[r, c]]
            
            os.system('cls' if os.name == 'nt' else 'clear')
            for line in layout:
                print(*line)
            time.sleep(0.5)
            
            (r, c), _ = compute_transition((r, c), self.greedy_policy[r, c], layout)
            steps += 1

    def clear_screen(self):
        os.system('cls' if os.name == 'nt' else 'clear')


class ValueIterationAgent(DPGridSolver):
    def optimize(self, environment_map, discount_factor=0.9, tolerance=1e-5):
        previous_values = np.ones_like(self.value_estimates)
        
        while np.sum(np.abs(previous_values - self.value_estimates)) > tolerance:
            previous_values = self.value_estimates.copy()
            
            for r in range(self.height):
                for c in range(self.width):
                    # Evaluate Q-values for all feasible actions
                    for act in range(self.n_actions):
                        next_state, reward = compute_transition((r, c), act, environment_map)
                        self.q_tables[r, c, act] = reward + discount_factor * self.value_estimates[next_state]
                    
                    # Extract greedy action index
                    self.greedy_policy[r, c] = np.argmax(self.q_tables[r, c])
                    # Apply hard max backup
                    self.value_estimates[r, c] = np.max(self.q_tables[r, c])


if __name__ == "__main__":
    world_map = [
        ['□', '□', '□', '□', '□'],
        ['□', '×', '×', '□', '□'],
        ['□', '□', '×', '□', '□'],
        ['□', '×', '●', '×', '□'],
        ['□', '×', '□', '□', '□']
    ]
    
    agent = ValueIterationAgent(len(world_map), len(world_map[0]))
    agent.optimize(world_map)
    agent.visualize_path((0, 0), (3, 2), world_map)

The computational pipeline mirrors the mathematical derivation. Initialization assigns scalar placeholders to each coordinate pair, establishing preliminary value estimates. The algorithm then calculates immediate rewards augmented by the discounted future value for every permissible transition. Once all action-conditioned returns populate the Q-table, the procedure extracts the index corresponding to the highest metric to lock in a deterministic policy. Concurrently, the state-value matrix receives a hard-max assignment across that row, strictly enforcing the max<sub>a</sub> constraint. This spatial sweep repeats until the L1 norm of value deltas drops beneath the convergence threshold.

Policy Iteration Algorithm

Whereas Value Iteration tightly couples policy approximation with value correction, Policy Iteration disentangles these operations into sequential phases:

1. Policy Evaluation: Solve explicitly for v<sub>π</sub>(s) assuming the current stationary policy π remains fixed.
2. Policy Improvement: Redefine π(s) to act greedily with respect to the freshly resolved value landscape.

This dual-loop architecture typically achieves target precision in fewer outer cycles than Value Iteration, though each evaluation phase demands substantial computational overhead due to repeated state-space sweeps. In practice, exact linear-system resolution is prohibitively expensive, motivating the adoption of evaluation step limits.

The underlying mechanics remain anchored in dynamic programming recursion. By fully stabilizing value predictions under a fixed behavioral rule, the algorithm guarantees non-decreasing performance improvements at every policy refresh.

Implementation

class PolicyIterationAgent(DPGridSolver):
    def optimize(self, environment_map, discount_factor=0.9, tolerance=1e-5, max_eval_steps=20):
        prev_policy = np.ones((self.height, self.width), dtype=int)
        eval_stalls = 0
        
        while not np.array_equal(prev_policy, self.greedy_policy) or eval_stalls < max_eval_steps:
            # --- Policy Evaluation Phase ---
            last_values = np.ones_like(self.value_estimates)
            sweep_counter = 0
            
            while np.sum(np.abs(last_values - self.value_estimates)) > tolerance and sweep_counter < max_eval_steps:
                last_values = self.value_estimates.copy()
                sweep_counter += 1
                
                for r in range(self.height):
                    for c in range(self.width):
                        current_move = self.greedy_policy[r, c]
                        next_state, reward = compute_transition((r, c), current_move, environment_map)
                        self.value_estimates[r, c] = reward + discount_factor * self.value_estimates[next_state]
            
            # --- Policy Improvement Phase ---
            prev_policy = self.greedy_policy.copy()
            for r in range(self.height):
                for c in range(self.width):
                    for act in range(self.n_actions):
                        next_state, reward = compute_transition((r, c), act, environment_map)
                        self.q_tables[r, c, act] = reward + discount_factor * self.value_estimates[next_state]
                    self.greedy_policy[r, c] = np.argmax(self.q_tables[r, c])
            
            # Monitor convergence stability
            if not np.array_equal(prev_policy, self.greedy_policy):
                eval_stalls = 0
            else:
                eval_stalls += 1

if __name__ == "__main__":
    # Reuse world_map definition
    policy_agent = PolicyIterationAgent(len(world_map), len(world_map[0]))
    policy_agent.optimize(world_map)
    policy_agent.visualize_path((2, 1), (3, 2), world_map)

This architecture isolates value stabilization inside the inner loop. Rather than inverting the transition probability matrix, iterative backups approximate v<sub>π</sub> until numerical equilibrium or a predefined sweep cap triggers. Following stabilization, the greedy revision step exhaustively scans every cell, projects future returns, and commits the updated deterministic behavior. Convergence detection relies on monitoring policy array invariance across consecutive improvement epochs.

Truncated Policy Iteration

Value Iteration and Policy Iteration represent limiting cases within a unified framework known as Truncated Policy Iteration. Standard Policy Iteration theoretically necessitates infinite evaluation sweeps to achieve exact convergence—an execution requirement incompatible with finite-horizon computing architectures. Conversely, Value Iteration restricts itself to a single evaluation sweep per outer cycle. Truncated Policy Iteration interpolates between these extremes by executing a bounded number of evaluation passes (k) before invoking greedy refinement.

Setting k = 1 collapses the framework into pure Value Iteration. Pushing k → ∞ asymptotically approaches classical Policy Iteration. Constraining evaluation depth drastically lowers per-iteration latency while retaining accelerated convergence trajectories, establishing truncated variants as the default implementation strategy in contemporary reinforcement learning toolchains.