Markov and Partially Observable Decision Processes › Implementation: Planning a Gridworld with Value Iteration

We now make the first half of the chapter executable. Our running example is a $5\times5$ office gridworld: the delivery robot starts at the bottom-left corner, a charging goal sits at the top-right, and an open stairwell (a pit) sits at the center. Each move succeeds with probability 0.8 and slips to a perpendicular direction with probability 0.1 each, simulating the slippery floor. Reaching the goal earns 20, falling into the pit costs 20, and every other step costs 1, encouraging short routes.

First, the imports and the environment model. We represent the transition kernel and reward function as dense arrays, indexed as T[action, state, next_state].

The arrays encode everything the planner needs: dynamics, slip stochasticity, wall clamping, and rewards. Note that the reward is attached to transitions, so stepping into the goal collects 20 exactly once, and the absorbing self-loops at terminals carry zero reward to keep values finite. The += accumulation matters in the corners: an attempted move off the grid clamps back to the same cell, so several probability masses can land on a single successor and must be summed rather than overwritten. At the top-left corner under a leftward action, for example, the intended move contributes $0.8$ to the clamped self-transition and the upward perpendicular slip contributes another $0.1$, for total self-transition mass $0.9$.

Next, value iteration. We record the maximum change per sweep so we can inspect the contraction behavior predicted by the theory.

The contraction analysis supplies a conservative sweep bound: with $\gamma = 0.9$, successive Bellman-backup differences can shrink by at most a factor of 0.9. The first recorded change is $15.8$, attained by a goal-adjacent state whose best action enters the goal, so the envelope $15.8(0.9)^k < 10^{-12}$ first crosses the threshold at the zero-based envelope index $k=289$, corresponding to the 290th recorded sweep, or roughly three hundred sweeps. Executing the cell above reaches the stopping tolerance in 53 sweeps. The gap is expected: $0.9$ is a worst-case contraction factor, while this grid's transition structure yields faster realized shrinkage. There is a compact way to see the backup arithmetic in the code itself: the line computing Q first averages immediate expected rewards over successors, then adds the discounted value of successors, so a single matrix product performs one full Bellman backup for every state and action simultaneously. Let us compare the observed decline with the theoretical envelope.

The observed curve equals the $\gamma^k$ reference envelope at the initial sweep and stays strictly below it afterward, reaching the tolerance much sooner than the worst-case bound requires. Its near-straight descent on the logarithmic axis indicates geometric shrinkage, while its steeper slope shows that the realized rate is faster than $\gamma$. The Bellman operator's sup-norm Lipschitz constant is $\gamma$, so each successive difference contracts by at most that factor; an individual sweep need not attain the bound. This distinction matters: contraction theory guarantees convergence for the exact discounted Bellman operator, but it does not say every problem attains the worst-case rate. If a practical planner fails to converge, inspect whether its update is actually the same contraction mapping—for example, approximation, changing models, or optimization error can invalidate that premise.

Now the interesting output: the optimal value surface and the policy it induces.

Read the figure as a decision-making document. Color encodes $v^*$: bright near the goal, dark near the pit, with a visible valley of low value surrounding the hazard. The arrows use only up and right in this seeded grid, but their routing bends around the pit rather than taking the most direct diagonal corridor, because the greedy policy weighs the 0.2 total slip probability against a 20-unit penalty. This is exactly the kind of behavior that emerges from the Bellman backup without ever being programmed in: risk-aware routing is a consequence of expected-value arithmetic, not a hand-coded rule.

Finally, let us close the loop between theory and simulation. If $v^*$ really is the expected return of the greedy policy, then Monte Carlo rollouts of that policy should reproduce $v^*(\text{start})$ up to sampling noise. This is the chapter's first taste of validation practice: never trust a planned value until simulated experience confirms it.

The two numbers agree closely, which is the entire point of the exercise. The value function computed by iterating the Bellman operator is not an abstract score; it is a verifiable prediction about closed-loop performance. Discrepancies here would indicate a bug, a modeling mismatch between rollout and planner, or statistical noise, and telling those apart is a skill in its own right. When a learned world model's planned values diverge from realized returns in later chapters, this gridworld check is the minimal diagnostic you should reach for.

Beyond matching means, the shape of the return distribution itself carries diagnostic information. The next plot separates the rollouts into those that reached the goal and those that fell into the pit.

Two distinct lobes appear instead of a symmetric spread around the mean: a tall lobe of successful deliveries whose returns spread across the planned value, with unobstructed routes landing above it and early slip-induced detours landing below, and a thin but costly lobe of pit outcomes far below zero. All 4,000 seeded rollouts reached one of the two terminals within the 100-step cap; the code asserts that no timeout was silently discarded. The empirical mean differs slightly from the planned value because of finite-sample noise. The value-iteration approximation contributes at most about $10^{-11}$ here, negligible beside the Monte Carlo standard error. Within the two-lobe empirical decomposition, increasing the pre-change pit probability from $p$ to $2p$ while holding the conditional return distributions fixed would shift the population mean by $p$ times the gap between their conditional means. That is why the tail should be inspected separately from the average.