Value iteration

What it computes

A Markov decision process (MDP) has states $s$, actions $a$, transition probabilities $P(s' \mid s, a)$, expected rewards $R(s, a)$ and a discount $\gamma < 1$: a reward $k$ moves away is worth $\gamma^k$ now. Value iteration computes the optimal value $V^*(s)$, the best expected discounted reward from $s$, and a policy that earns it. It plans with a known model $P$. Q-learning, the next problem, learns the same policy from trial moves alone.

The Bellman equation

$V^*$ is the only solution of

$$V(s) = \max_a \Big[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V(s') \Big]$$

Value iteration applies the right-hand side to every state (a backup) until nothing changes:

V = zeros(S)
repeat:
    Q[s, a] = R[s, a] + gamma * sum over s2 of P[s, a, s2] * V[s2]
    V_new[s] = max over a of Q[s, a]
    if max |V_new - V| < tol: return V_new, argmax over a of Q
    V = V_new

It converges because a backup is a contraction: it brings any two value functions at least $\gamma$ times closer. So from any start, the error shrinks by a factor of $\gamma$ or better every sweep.

The grid

A 24 × 24 slice of the arm's C-space: rows are the shoulder angle (the hand's height), columns the base angle, with the elbow and wrist fixed. Each of the 8 actions moves one cell (diagonals too), but slips 90° sideways with probability 0.1. Moves earn −1, blocked moves −10 (the arm stays put), and the goal above the cup is absorbing ($V = 0$). $\gamma = 0.95$. The wall separates the three starts from the goal, so the best route lifts the hand over it. The Images tab shows your $V$ (blue low, yellow high), the greedy paths in orange, and blocked cells in black.

Tools

mdp.P is (S, A, S) and mdp.R is (S, A). P @ V sums over $s'$ for every state and action at once; Python loops over its 2.6 million entries would take seconds per sweep.

See it in context

Motion Planning maps slices of this C-space around the same wall, and its bonus step searches a roadmap with Dijkstra's algorithm. LaValle's Planning Algorithms presents Dijkstra as a form of value iteration: with no slip and no discount, $-V$ is the shortest-path cost.

Your task

Implement value_iteration(P, R, gamma, tol), returning (V, policy). The grader tests it on random MDPs and on the grid. Then the arm follows your policy from each start: it must end within 1 cm of the goal and touch nothing.