Value Iteration and Policy Iteration: Many Small Steps or a Few Big Jumps

A small decision problem: three states, two actions each. Every value function is a point in this space, one coordinate per state, and the green star is the optimal value function.

Value iteration starts at zero and applies the Bellman optimality operator again and again. Each blue dot is one step, and each step closes the distance by a factor gamma.

Policy iteration alternates two moves. It evaluates the current policy exactly, by solving a linear system, and then improves the policy greedily, state by state.

So its orange path jumps from one policy's value straight to the next, and lands exactly on the star after a few jumps.

Because there are only finitely many deterministic policies, and each improvement strictly helps, policy iteration must stop after finitely many rounds. Value iteration only gets there in the limit.

Your turn. Change gamma. Find the smallest gamma at which value iteration needs more than fifty steps to get within one hundredth, while policy iteration still needs only a few rounds.

Value iteration takes cheap steps that shrink by gamma; policy iteration takes expensive steps, each a linear solve, but very few of them.