"""Value iteration: solve a known MDP with the Bellman optimality equation.""" from __future__ import annotations import numpy as np from gridworld import GridWorld def q_from_v(env: GridWorld, v: np.ndarray, gamma: float) -> np.ndarray: """One Bellman backup: Q(s,a) = sum over s' of p * (r + gamma * V(s') * (not done)).""" q = np.zeros((env.n_states, env.n_actions)) for s in range(env.n_states): for a in range(env.n_actions): q[s, a] = sum(p * (r + (0.0 if done else gamma * v[s2])) for p, s2, r, done in env.transitions(s, a)) return q def value_iteration(env: GridWorld, gamma: float = 0.95, tol: float = 1e-10, max_iter: int = 10_000) -> tuple[np.ndarray, np.ndarray, int]: """Return (V*, Q*, iterations). Terminal states have value 0.""" if not 0.0 <= gamma < 1.0: raise ValueError("gamma must be in [0, 1)") v = np.zeros(env.n_states) for it in range(1, max_iter + 1): q = q_from_v(env, v, gamma) v_new = q.max(axis=1) delta = float(np.max(np.abs(v_new - v))) v = v_new if delta < tol: break return v, q_from_v(env, v, gamma), it def greedy_policy(q: np.ndarray) -> np.ndarray: return np.argmax(q, axis=1) if __name__ == "__main__": env = GridWorld() v, q, iters = value_iteration(env, gamma=0.95) print(f"converged in {iters} sweeps; V*(start) = {v[env.start]:.4f}") print(env.render_policy(greedy_policy(q)))