7a:T435,Imagine you're designing an autonomous navigation system. Your robot stands at the entrance of an unfamiliar building, tasked with finding the shortest path to a specific room while avoiding obstacles and minimizing energy consumption. How should it decide which direction to move at each intersection? What makes one policy—a mapping from situations to actions—better than another? **Value iteration** answers these questions by computing the *optimal value* of every possible state: the maximum expected cumulative reward an agent can achieve starting from that state and acting optimally thereafter. Once we know these optimal values, the optimal policy falls out naturally—simply choose actions that lead to states with the highest values. This elegant algorithm, rooted in the principle of **dynamic programming**, was formalized by Richard Bellman in the 1950s and remains foundational to modern reinforcement learning. It provides both a theoretical cornerstone and a practical algorithm that, under the right conditions, provably converges to optimal solutions.7b:T474,The Bellman optimality equation defines $V^*$ implicitly—but how do we actually *compute* it? **Value iteration** is the answer: an iterative algorithm that repeatedly applies the Bellman optimality operator until convergence. ### The Bellman Optimality Operator Define the **Bellman optimality operator** $T^*$ that maps a value function $V$ to a new value function: $$(T^* V)(s) = \max_{a \in A(s)} \left[ R(s, a) + \gamma \sum_{s' \in S} P(s' | s, a) V(s') \right]$$ The optimal value function $V^*$ is a **fixed point** of this operator: $T^* V^* = V^*$. ### The Algorithm Value iteration repeatedly applies $T^*$ starting from an arbitrary initialization: 1. **Initialize** $V_0(s)$ arbitrarily for all states (commonly to 0) 2. **Repeat** for $k = 0, 1, 2, \ldots$: - For each state $s \in S$: $$V_{k+1}(s) = \max_{a \in A(s)} \left[ R(s, a) + \gamma \sum_{s' \in S} P(s' | s, a) V_k(s') \right]$$ - Compute $\delta = \max_s |V_{k+1}(s) - V_k(s)|$ 3. **Until** $\delta < \theta$ (convergence threshold) 4. **Extract policy**: $\pi^*(s) = \arg\max_{a} \left[ R(s, a) + \gamma \sum_{s'} P(s' | s, a) V^*(s') \right]$7c:Taa5,import numpy as np from typing import Tuple, Callable def value_iteration( num_states: int, num_actions: int, transition_probs: np.ndarray, # Shape: (S, A, S) rewards: np.ndarray, # Shape: (S, A) or (S, A, S) gamma: float = 0.99, theta: float = 1e-8, max_iterations: int = 10000 ) -> Tuple[np.ndarray, np.ndarray, list]: """ Value Iteration Algorithm for finite MDPs. Args: num_states: Number of states |S| num_actions: Number of actions |A| transition_probs: P(s'|s,a) transition probability matrix rewards: R(s,a) or R(s,a,s') reward function gamma: Discount factor (0 <= gamma < 1) theta: Convergence threshold max_iterations: Maximum iterations to prevent infinite loops Returns: V: Optimal value function, shape (S,) policy: Optimal policy, shape (S,) deltas: History of max value changes per iteration """ # Initialize value function arbitrarily (zeros is common) V = np.zeros(num_states) deltas = [] # Handle different reward formats if rewards.ndim == 2: # R(s, a) format - expand to expected reward R_sa = rewards else: # R(s, a, s') format - compute expected reward R_sa = np.sum(transition_probs * rewards, axis=2) for iteration in range(max_iterations): V_new = np.zeros(num_states) for s in range(num_states): # Compute Q(s, a) for all actions Q_values = np.zeros(num_actions) for a in range(num_actions): # Bellman backup: R(s,a) + gamma * sum_s' P(s'|s,a) * V(s') expected_future_value = np.dot(transition_probs[s, a, :], V) Q_values[a] = R_sa[s, a] + gamma * expected_future_value # Max over actions (Bellman optimality) V_new[s] = np.max(Q_values) # Check for convergence delta = np.max(np.abs(V_new - V)) deltas.append(delta) V = V_new.copy() if delta < theta: print(f"Converged in {iteration + 1} iterations (delta = {delta:.2e})") break else: print(f"Warning: Did not converge within {max_iterations} iterations") # Extract greedy policy from optimal value function policy = np.zeros(num_states, dtype=int) for s in range(num_states): Q_values = np.zeros(num_actions) for a in range(num_actions): expected_future_value = np.dot(transition_probs[s, a, :], V) Q_values[a] = R_sa[s, a] + gamma * expected_future_value policy[s] = np.argmax(Q_values) return V, policy, deltas7d:T43d,A critical question: does value iteration actually converge to $V^*$? The answer is yes, and the proof relies on the **contraction mapping theorem**. ### The Bellman Operator is a Contraction **Definition (Contraction Mapping)**: A mapping $T: X \to X$ on a metric space $(X, d)$ is a **contraction** if there exists $\gamma \in [0, 1)$ such that for all $x, y \in X$: $$d(Tx, Ty) \leq \gamma \cdot d(x, y)$$ **Theorem**: The Bellman optimality operator $T^*$ is a $\gamma$-contraction under the sup-norm (infinity norm): $$\|T^* V_1 - T^* V_2\|_\infty \leq \gamma \|V_1 - V_2\|_\infty$$ **Proof**: For any state $s$, $$ \begin{aligned} |(T^* V_1)(s) - (T^* V_2)(s)| &= \left| \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_1(s') \right] - \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_2(s') \right] \right| &\leq \max_a \gamma \left| \sum_{s'} P(s'|s,a) (V_1(s') - V_2(s')) \right| &\leq \gamma \max_a \sum_{s'} P(s'|s,a) |V_1(s') - V_2(s')| &\leq \gamma \|V_1 - V_2\|_\infty \end{aligned} $$ The second step uses the property $|\max f - \max g| \leq \max |f - g|$.7e:T852,import numpy as np class Gridworld: """4x4 Gridworld environment for value iteration demonstration.""" def __init__(self, size=4): self.size = size self.num_states = size * size self.num_actions = 4 # N, S, E, W self.terminal_states = {0, self.num_states - 1} # Action effects: (row_delta, col_delta) self.action_effects = { 0: (-1, 0), # North 1: (1, 0), # South 2: (0, 1), # East 3: (0, -1), # West } # Build transition matrix P[s, a, s'] and reward R[s, a] self.P = np.zeros((self.num_states, self.num_actions, self.num_states)) self.R = np.zeros((self.num_states, self.num_actions)) self._build_dynamics() def _state_to_coord(self, s): return s // self.size, s % self.size def _coord_to_state(self, row, col): return row * self.size + col def _build_dynamics(self): for s in range(self.num_states): if s in self.terminal_states: # Terminal states: all actions lead to same state, zero reward for a in range(self.num_actions): self.P[s, a, s] = 1.0 self.R[s, a] = 0.0 continue row, col = self._state_to_coord(s) for a, (dr, dc) in self.action_effects.items(): new_row = np.clip(row + dr, 0, self.size - 1) new_col = np.clip(col + dc, 0, self.size - 1) next_s = self._coord_to_state(new_row, new_col) self.P[s, a, next_s] = 1.0 self.R[s, a] = -1.0 # -1 reward for each step # Run value iteration on gridworld env = Gridworld(size=4) V, policy, deltas = value_iteration( env.num_states, env.num_actions, env.P, env.R, gamma=1.0, # No discounting (episodic) theta=1e-10 ) # Display results print(" Optimal Value Function (4x4 grid):") print(V.reshape(4, 4).round(2)) print(" Optimal Policy (0=N, 1=S, 2=E, 3=W):") print(policy.reshape(4, 4))7f:T7de,import heapq from collections import defaultdict def prioritized_value_iteration( num_states, num_actions, P, R, gamma=0.99, theta=1e-8, max_updates=1000000 ): """ Prioritized Sweeping variant of Value Iteration. Updates states in order of their Bellman error magnitude. """ V = np.zeros(num_states) # Build predecessor model: pred[s'] = [(s, a, prob), ...] predecessors = defaultdict(list) for s in range(num_states): for a in range(num_actions): for s_next in range(num_states): if P[s, a, s_next] > 0: predecessors[s_next].append((s, a, P[s, a, s_next])) # Initialize priority queue with all states # Priority is negative Bellman error (heapq is min-heap) pq = [] bellman_errors = np.zeros(num_states) for s in range(num_states): Q_max = max(R[s, a] + gamma * np.dot(P[s, a, :], V) for a in range(num_actions)) bellman_errors[s] = abs(Q_max - V[s]) if bellman_errors[s] > theta: heapq.heappush(pq, (-bellman_errors[s], s)) in_queue = set(s for _, s in pq) updates = 0 while pq and updates < max_updates: # Pop state with largest error neg_priority, s = heapq.heappop(pq) in_queue.discard(s) # Bellman update old_V = V[s] V[s] = max(R[s, a] + gamma * np.dot(P[s, a, :], V) for a in range(num_actions)) updates += 1 # Update predecessors' priorities if abs(V[s] - old_V) > theta: for s_pred, a_pred, prob in predecessors[s]: # Change in predecessor's value could be up to gamma * prob * |delta| potential_change = gamma * prob * abs(V[s] - old_V) if potential_change > theta and s_pred not in in_queue: heapq.heappush(pq, (-potential_change, s_pred)) in_queue.add(s_pred) return V, updates72:{"json":{"id":"seed_c6a063047737edb34071bcbfab9bd1dd","slug":"value-based-methods","category":"Machine Learning","topic":"Reinforcement Learning","title":"Value-Based Methods","description":"Master the foundational value-based approaches to reinforcement learning, from classical dynamic programming algorithms like value iteration to modern temporal-difference methods including Q-learning, SARSA, and eligibility traces. Understand how agents learn optimal behavior by estimating value functions.","difficulty":"ADVANCED","estimatedMinutes":180,"pages":[{"id":"seed_a44800bd57e063c3c12bd7e79070846a","title":"Value Iteration","order":0,"content":[{"id":"value-iteration-opening","title":"Computing Optimal Behavior from First Principles","content":[{"data":{"content":"$7a"},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will master the complete theory and practice of value iteration: the Bellman optimality principle, the algorithm derivation, rigorous convergence proofs, implementation in code, computational complexity analysis, and practical considerations for applying value iteration to real problems.","variant":"info"},"type":"callout"}]},{"id":"bellman-optimality-principle","title":"The Bellman Optimality Principle","content":[{"data":{"content":"Value iteration is built upon one of the most profound insights in sequential decision-making: **Bellman's Principle of Optimality**.\n\n> *\"An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.\"*\n> — Richard Bellman, 1957\n\nThis principle states that optimal behavior decomposes recursively. If you're taking the optimal path from A to C through B, then the segment from B to C must also be optimal. This self-consistency is captured mathematically by the **Bellman equations**."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Why Bellman's Insight Matters","content":"The recursive structure of optimal decisions transforms an exponentially complex search problem into a tractable computation. Instead of considering all possible action sequences (exponential in horizon), we can compute optimal values incrementally by leveraging the solution to smaller subproblems.","variant":"tip"},"type":"callout"},{"data":{"content":"### Formal Definition of Optimal Value Functions\n\nRecall from the MDP framework that a **policy** $\\pi: S \\to A$ (or more generally $\\pi: S \\to \\Delta(A)$ for stochastic policies) specifies how an agent selects actions. The **state-value function** under policy $\\pi$ is:\n\n$$V^\\pi(s) = \\mathbb{E}_\\pi \\left[ \\sum_{t=0}^{\\infty} \\gamma^t R_{t+1} \\mid S_0 = s \\right]$$\n\nThis measures the expected cumulative discounted reward starting from state $s$ and following policy $\\pi$ thereafter.\n\nThe **optimal value function** $V^*$ represents the best achievable value:\n\n$$V^*(s) = \\max_\\pi V^\\pi(s) \\quad \\text{for all } s \\in S$$\n\nSimilarly, the **optimal action-value (Q) function** is:\n\n$$Q^*(s, a) = \\max_\\pi Q^\\pi(s, a)$$\n\nwhere $Q^\\pi(s, a)$ denotes the expected return when taking action $a$ in state $s$ and following $\\pi$ thereafter."},"type":"text"},{"data":{"content":"### The Bellman Optimality Equations\n\nThe optimal value function satisfies a remarkable self-consistency condition—the **Bellman optimality equation**:\n\n$$V^*(s) = \\max_{a \\in A(s)} \\left[ R(s, a) + \\gamma \\sum_{s' \\in S} P(s' | s, a) V^*(s') \\right]$$\n\nLet's unpack each component:"},"type":"text"},{"data":{"rows":[["$$V^*(s)$","Optimal value of state $s$—best achievable expected return"],["$$\\max_{a \\in A(s)}$","Choose the action that maximizes value (greedy selection)"],["$$R(s, a)$","Immediate reward for taking action $a$ in state $s$"],["$$\\gamma$","Discount factor, $0 \\leq \\gamma < 1$"],["$$P(s' \\mid s, a)$","Transition probability to state $s'$"],["$$\\sum_{s'} P(s' \\mid s, a) V^*(s')$","Expected optimal future value"]],"headers":["Component","Meaning"]},"type":"table"},{"data":{"content":"The equation says: the optimal value of a state equals the immediate reward plus the discounted expected optimal value of the next state, maximized over all possible actions."},"type":"text"},{"data":{"icon":"Info","title":"The Q-Function Form","content":"The Bellman optimality equation for Q-values is: $Q^*(s, a) = R(s, a) + \\gamma \\sum_{s'} P(s' | s, a) \\max_{a'} Q^*(s', a')$. This form is crucial for Q-learning, which we'll cover in the next page. Note that $V^*(s) = \\max_a Q^*(s, a)$.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"value-iteration-algorithm","title":"The Value Iteration Algorithm","content":[{"data":{"content":"$7b"},"type":"text"},{"data":{"fileName":"value_iteration.py","languages":[{"code":"$7c","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"Synchronous vs Asynchronous Updates","content":"The algorithm above uses synchronous updates: all states are updated using the same previous value function V_k before any V_{k+1} values are used. Asynchronous variants update states one at a time, immediately using new values. Both converge, but asynchronous updates can sometimes be faster in practice.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"convergence-theory","title":"Convergence Theory","content":[{"data":{"content":"$7d"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Banach Fixed-Point Theorem","content":"The Banach fixed-point theorem guarantees that a contraction mapping on a complete metric space has a unique fixed point, and iterative application of the mapping converges to it from any starting point. Since the space of bounded value functions with the sup-norm is complete, value iteration converges to the unique V*.","variant":"tip"},"type":"callout"},{"data":{"content":"### Convergence Rate Analysis\n\nSince $T^*$ is a $\\gamma$-contraction, we have:\n$$\\|V_k - V^*\\|_\\infty \\leq \\gamma^k \\|V_0 - V^*\\|_\\infty$$\n\nThis gives us **linear convergence** with rate $\\gamma$. The number of iterations needed to achieve $\\epsilon$-accuracy is:\n\n$$k \\geq \\frac{\\log(\\|V_0 - V^*\\|_\\infty / \\epsilon)}{\\log(1/\\gamma)}$$\n\n**Practical implication**: When $\\gamma$ is close to 1 (e.g., 0.99 for long-horizon problems), convergence is slow. Each iteration multiplies the error by $\\gamma$, so at $\\gamma = 0.99$, we need approximately $\\log(1/\\epsilon) / 0.01 \\approx 460$ iterations to reduce error by a factor of 100."},"type":"text"},{"data":{"rows":[["0.9","~66"],["0.95","~133"],["0.99","~688"],["0.999","~6,905"]],"caption":"Iterations to Reduce Error by Factor of 1000","headers":["Discount Factor γ","Approximate Iterations Needed"]},"type":"table"},{"data":{"icon":"Info","title":"Stopping Criteria in Practice","content":"Instead of computing ||V - V*||, which requires knowing V*, we use ||V_{k+1} - V_k|| < θ. The relationship is: ||V_k - V*|| ≤ ||V_{k+1} - V_k|| / (1 - γ). So for θ = 0.01 and γ = 0.99, we guarantee ||V_k - V*|| ≤ 1.0.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"worked-example-gridworld","title":"Worked Example: Gridworld","content":[{"data":{"content":"Let's apply value iteration to a concrete problem: the classic **Gridworld** environment. This example illuminates how value iteration propagates value information through the state space.\n\n### Problem Setup\n\nConsider a 4×4 grid with:\n- **States**: 16 cells, numbered 0–15 (row-major order)\n- **Actions**: North, South, East, West (deterministic movement)\n- **Terminal states**: Cell 0 (top-left) and Cell 15 (bottom-right)\n- **Rewards**: -1 for each step (incentivizes reaching terminal states quickly)\n- **Boundaries**: Moving into a wall keeps the agent in place\n\nThis is an **episodic task**: episodes end when reaching a terminal state."},"type":"text"},{"data":{"fileName":"gridworld.py","languages":[{"code":"$7e","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"### Iteration-by-Iteration Analysis\n\nLet's trace value propagation through iterations:\n\n**Iteration 0** (Initial $V_0 = 0$ everywhere):\n- All non-terminal states update to $V_1(s) = -1$ (immediate reward)\n- Terminal states remain $V(0) = V(15) = 0$\n\n**Iteration 1**:\n- States adjacent to terminals: $V_2(1) = V_2(4) = -1 + 1 \\cdot 0 = -1$ (can reach terminal)\n- States two steps away: $V_2(5) = -1 + 1 \\cdot (-1) = -2$\n\n**Subsequent iterations**:\n- Value propagates outward from terminal states\n- Each iteration extends the \"horizon\" of foresight by one step\n- States learn their true distance (in expected steps) to terminals"},"type":"text"},{"data":{"rows":[["**Row 0**","0.0","-1.0","-2.0","-3.0"],["**Row 1**","-1.0","-2.0","-3.0","-2.0"],["**Row 2**","-2.0","-3.0","-2.0","-1.0"],["**Row 3**","-3.0","-2.0","-1.0","0.0"]],"caption":"Converged Optimal Value Function (4×4 Gridworld, γ=1.0)","headers":["","Col 0","Col 1","Col 2","Col 3"]},"type":"table"},{"data":{"icon":"CheckCircle","title":"Interpreting the Result","content":"The optimal value at each cell equals the negative of the Manhattan distance to the nearest terminal state. Cell (1,1) has value -2 because the shortest path to either terminal requires 2 steps. The optimal policy points toward the nearest terminal—beautiful emergent behavior from a simple recursive update!","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"computational-complexity","title":"Computational Complexity","content":[{"data":{"content":"Understanding the computational requirements of value iteration is essential for practical deployment. Let's analyze time and space complexity rigorously.\n\n### Time Complexity\n\n**Per-iteration cost**: For each state $s$, we compute:\n$$V_{k+1}(s) = \\max_{a} \\left[ R(s,a) + \\gamma \\sum_{s'} P(s'|s,a) V_k(s') \\right]$$\n\n- Inner sum over $s'$: $O(|S|)$ per action\n- Max over actions: $O(|A|)$\n- Total per state: $O(|A| \\cdot |S|)$\n- Total per iteration: $O(|S| \\cdot |A| \\cdot |S|) = O(|S|^2 \\cdot |A|)$\n\n**Number of iterations**: From convergence analysis, approximately $O\\left(\\frac{1}{1-\\gamma} \\log\\frac{1}{\\epsilon}\\right)$ iterations.\n\n**Total time complexity**:\n$$O\\left(\\frac{|S|^2 \\cdot |A|}{1-\\gamma} \\log\\frac{1}{\\epsilon}\\right)$$"},"type":"text"},{"data":{"rows":[["Per-iteration time","O(|S|² · |A|)","Quadratic in states—limits scalability"],["Number of iterations","O(log(1/ε) / (1-γ))","Slow for γ near 1"],["Space","O(|S|)","Linear—value function storage only"],["Transition model","O(|S|² · |A|)","Must store or compute P(s'|s,a)"]],"caption":"Value Iteration Complexity Summary","headers":["Aspect","Complexity","Practical Implication"]},"type":"table"},{"data":{"content":"### Space Complexity\n\nValue iteration is remarkably space-efficient:\n- Value function storage: $O(|S|)$\n- Transition model: $O(|S|^2 \\cdot |A|)$ if stored explicitly\n- Total: $O(|S|^2 \\cdot |A|)$ dominated by the MDP model\n\n**Sparse transitions**: Many real MDPs have sparse transitions—each action leads to only a few possible next states. With sparsity factor $k$ (average non-zero transitions per state-action):\n- Per-iteration: $O(|S| \\cdot |A| \\cdot k)$\n- Model storage: $O(|S| \\cdot |A| \\cdot k)$\n\nThis makes value iteration practical for much larger state spaces when dynamics are sparse."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Curse of Dimensionality","content":"The $O(|S|^2)$ per-iteration cost is the Achilles' heel of value iteration. If your state space is a product of d dimensions each with n values, |S| = n^d. For a robot with 10 joints, each discretized to 100 positions, |S| = 100^10 = 10^20. This is why we need function approximation and model-free methods for realistic problems.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"optimizations-variants","title":"Optimizations and Variants","content":[{"data":{"content":"Several techniques can accelerate value iteration or improve its practicality:\n\n### 1. Gauss-Seidel (In-Place) Updates\n\nInstead of computing all new values before any update, use new values immediately:\n\n```python\nfor s in range(num_states):\n V[s] = max_a [R(s,a) + gamma * sum_s' P(s'|s,a) * V[s']]\n```\n\nThis **in-place** variant often converges faster because updates propagate immediately. The convergence guarantee still holds (asynchronous DP), though the convergence rate analysis differs."},"type":"text"},{"data":{"content":"### 2. Prioritized Sweeping\n\nNot all states need equal attention. **Prioritized sweeping** maintains a priority queue based on the magnitude of the last update (Bellman error):\n\n1. Update the state with the highest priority\n2. For states that could be affected (predecessors), update their priority based on how much the current update could change them\n3. Repeat\n\nThis focuses computation where it matters most—states with large value changes that will propagate to others."},"type":"text"},{"data":{"fileName":"prioritized_sweeping.py","languages":[{"code":"$7f","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"### 3. Policy Iteration vs Value Iteration\n\nAn alternative algorithm, **policy iteration**, separates policy evaluation (computing $V^\\pi$ for fixed $\\pi$) from policy improvement (finding a better policy)."},"type":"text"},{"data":{"rows":[["Update","One Bellman backup per sweep","Full policy evaluation between improvements"],["Iterations","Many (slow per-sweep)","Few (expensive per-sweep)"],["Per-iteration cost","$$O(|S|^2 \\cdot |A|)$","$$O(|S|^3)$ for exact evaluation"],["Memory","Single value function","Value function per evaluation"],["When to prefer","Small actions, large states","Policies stabilize quickly"]],"headers":["Aspect","Value Iteration","Policy Iteration"]},"type":"table"},{"data":{"content":"Policy iteration often converges in fewer iterations but each iteration is more expensive."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Modified Policy Iteration","content":"A hybrid approach: instead of full policy evaluation, perform k Bellman backups (k << convergence) before policy improvement. This combines the fast convergence of policy iteration with the cheap iterations of value iteration. Choosing k dynamically based on the improvement rate can be particularly effective.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"practical-considerations","title":"Practical Considerations","content":[{"data":{"content":"Deploying value iteration in practice requires attention to implementation details that theory often glosses over.\n\n### Numerical Stability\n\n**Reward scaling**: If rewards are very large or very small, numerical precision issues can arise. Normalize rewards to a reasonable range (e.g., [-1, 1] or [0, 1]).\n\n**Discount factor near 1**: When $\\gamma \\approx 1$, values can grow very large. Consider using undiscounted episodic formulations where possible, or track value differences rather than absolute values.\n\n**Initialization**: While any initialization converges, starting close to the true values (if you have a heuristic) speeds convergence."},"type":"text"},{"data":{"items":["**Confusing indices**: Mixing up s, a, s' indices in transition matrices is the #1 bug. Use explicit variable names and verify with small examples.","**Terminal state handling**: Terminal states should have zero value and self-loops. Forgetting to handle them correctly causes divergence.","**Synchronous update error**: Using V_new[s'] instead of V[s'] in the Bellman backup breaks synchronous semantics (though still converges).","**Convergence check placement**: Check convergence after the full sweep, not after each state update.","**Policy extraction before convergence**: Extracting greedy policy from an unconverged value function can give suboptimal policies."],"title":{"icon":"AlertCircle","text":"Common Implementation Pitfalls","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"### When to Use Value Iteration\n\n**Good fit**:\n- Small to medium state spaces (< 10^6 states)\n- Known, tabular MDP model (P and R available)\n- High accuracy required\n- Offline planning (compute once, execute many times)\n\n**Poor fit**:\n- Large/continuous state spaces → function approximation needed\n- Unknown dynamics → model-free methods (Q-learning, policy gradient)\n- Online learning → sample-based methods\n- Continuous actions → policy-based methods"},"type":"text"},{"data":{"icon":"Info","title":"Value Iteration as a Building Block","content":"Even when value iteration isn't directly applicable, understanding it is crucial. Many advanced algorithms (fitted value iteration, DQN, model-based RL) are built on value iteration principles with function approximation. The Bellman optimality equation remains the north star of RL, regardless of how we approximate its solution.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"value-iteration-summary","title":"Summary: Value Iteration","content":[{"data":{"content":"Value iteration is the cornerstone algorithm for computing optimal value functions in Markov Decision Processes. Let's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**Bellman optimality principle**: Optimal decisions decompose recursively—if the whole path is optimal, every suffix must also be optimal.","**The algorithm**: Repeatedly apply Bellman backups V_{k+1}(s) = max_a [R(s,a) + γ Σ P(s'|s,a) V_k(s')] until convergence.","**Convergence guarantee**: The Bellman operator is a γ-contraction, guaranteeing convergence to unique V* from any starting point.","**Convergence rate**: Linear convergence at rate γ—slow when γ ≈ 1, requiring O(1/(1-γ)) iterations.","**Complexity**: O(|S|² · |A|) per iteration—the curse of dimensionality limits scalability.","**Optimizations**: Gauss-Seidel updates, prioritized sweeping, and modified policy iteration can accelerate convergence.","**Practical scope**: Best for offline planning with known models and tabular state spaces."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next**: Value iteration requires a complete model of the environment—transition probabilities and rewards. But what if we don't have this model and must learn from experience? The next page introduces **Q-learning**, a model-free algorithm that learns optimal action-values directly from observed transitions."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a comprehensive understanding of value iteration: its theoretical foundations in dynamic programming, convergence properties, practical implementation, and computational limitations. This knowledge forms the bedrock for understanding all value-based RL methods that follow.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_685fc314c322a031b19ad648f93d3075","title":"Q-Learning","order":1,"content":null,"isLocked":true},{"id":"seed_4d933693440da6c2e6f3330f54017806","title":"SARSA","order":2,"content":null,"isLocked":true},{"id":"seed_424dd68e1f950f15aa7d6c32f26c8d11","title":"Temporal Difference Learning","order":3,"content":null,"isLocked":true},{"id":"seed_c6be6c35bde2b317180927321e534a83","title":"Eligibility Traces","order":4,"content":null,"isLocked":true}]}}