Planning with value iteration

From evaluating to planning

Step 1 measured one policy. Value iteration finds the best one. The optimal value $V^*(s)$, the best expected return from $s$, obeys the Bellman optimality equation

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

The bracket is the action value $Q(s, a)$: take $a$ now and act optimally afterwards. A backup applies the right-hand side to every state at once. P @ V sums over $s'$ for every state and action, so Q = R + gamma * (P @ V) is (S, A); Q.max(axis=1) gives the new values and Q.argmax(axis=1) the greedy policy, the best action in each state. Value iteration starts from $V = 0$ and backs up until no value changes by more than a tolerance.

Why it settles

A backup is a contraction: it brings any two value functions $V$ and $W$ at least $\gamma$ times closer, $\max_s |BV(s) - BW(s)| \le \gamma \max_s |V(s) - W(s)|$, where $B$ is one backup. So the largest change in each sweep shrinks by a factor of $\gamma$ or better, and its $\log_{10}$ in the Plots tab falls along a straight line, or faster.

A wave from the goal

After $k$ sweeps, $V_k(s)$ is the best return within $k$ moves. A state more than $k$ moves from the goal hasn't heard of it yet, and its greedy action is no better than a guess. The Images tab shows the values after 5, 10 and 20 sweeps: they spread out from the goal one move per sweep. Start 1 is 21 moves away, so its greedy path only works after about 19 sweeps.

Your task

1. Write backup(P, R, gamma, V), one sweep, returning (V_new, policy).
2. Write value_iteration(P, R, gamma, tol). From $V = 0$, back up until a sweep changes no value by more than tol. Return (V, policy, changes), where changes lists each sweep's largest change $\max_s |V_{\text{new}}(s) - V(s)|$, in order.

The program compares $V^*$ with your step-1 policy, then drives the arm from four starts, one of them on the cup's side of the wall. Each drive must end within 1 cm of the goal and touch nothing.