What is the difference between value iteration and policy iteration on the same MDP?

## The two algorithms side by side **Policy iteration** ``` repeat: evaluate: v(s) <- sum_s' P(s'|s, pi(s)) [ r + gamma v(s') ] # sweep until settled improve: pi(s) <- argmax_a sum_s' P(s'|s,a) [ r + gamma v(s') ] # one pass until pi stops changing ``` **Value iteration** ``` repeat: v(s) <- max_a sum_s' P(s'|s,a) [ r + gamma v(s') ] # one sweep, maximum inside until the largest change < theta then read off pi(s) = argmax_a ... once at the end ``` The structural difference is *where the maximum sits*. In policy iteration it appears only in the improvement pass, and the evaluation sweeps use the policy's own action. In value iteration it is inside every update, so the values being computed are never the values of any particular policy along the way — they are estimates of the optimal values. ## Cost analysis With dense transitions, one full backup of one state costs about `|S|` operations (summing over successors). - A **value-iteration sweep** does that for every state and every action: about `|S| * |A| * |S|`. - A **policy-evaluation sweep** does it for every state and only the policy's action: about `|S| * |S|`, that is `|A|` times cheaper — but you run many of them per round. - A **policy-improvement pass** costs the same as one value-iteration sweep. So the trade is: policy iteration needs far fewer outer rounds (each improvement uses fully converged values, so it takes bigger jumps), while value iteration needs many more sweeps, each cheaper and simpler. There is no universal winner; the crossover depends on `|A|`, on `gamma` (a discount close to one slows value iteration badly, because the number of sweeps needed grows with the effective horizon `1/(1-gamma)`), and on how exactly the evaluation is done. **The linear-solve option.** Because `v_pi` satisfies a linear system of `|S|` equations, policy iteration can solve evaluation exactly in roughly `|S|^3` work instead of sweeping. For a few thousand states this is often the fastest route to an exactly optimal policy, and it is a strong argument for policy iteration on small, dense problems such as a machine replace-or-repair MDP with a few hundred condition states. ## Same destination Both converge to the same optimal value function and an optimal policy. The optimal values are the unique fixed point of the maximising backup, and both methods are driving towards that fixed point — one by contracting directly, the other by climbing through a finite sequence of improving policies. Neither is an approximation of the other in terms of the answer; they differ only in the path and the cost. ## A practical fact about value iteration The greedy policy implied by the values usually becomes optimal **long before the values themselves converge**. The values keep creeping toward their fixed point while the ranking of actions in each state has already stabilised. If you only need the policy, you can often stop far earlier than a tight value tolerance suggests — and a common practical check is to watch whether the greedy policy has changed over the last several sweeps rather than watching the value delta alone. When you do stop on a value tolerance, the useful guarantee is: if the largest change over a sweep is below `theta`, the greedy policy's value is within about `2 * gamma * theta / (1 - gamma)` of optimal. That factor blows up as `gamma` approaches one, which is the quantitative reason long-horizon problems are hard to plan precisely. ## The spectrum between them Nothing forces evaluation to be either "one sweep" or "run to convergence". **Modified policy iteration** runs `k` evaluation sweeps per improvement: - `k = 1` is value iteration, - `k -> infinity` is policy iteration, - moderate `k` is often the fastest of the three in practice. The umbrella term for the pattern — evaluation and improvement chasing each other at any granularity — is **generalized policy iteration**, and seeing the two named algorithms as endpoints of one idea is exactly the insight an interviewer is checking for. ## How to choose Ask three questions. How many actions per state? Many actions make value-iteration sweeps expensive relative to evaluation sweeps, favouring policy iteration. How large is the state space? A small one lets policy iteration solve evaluation exactly; a large one makes cheap, simple value-iteration sweeps attractive and easier to parallelise. How close is `gamma` to one? A long effective horizon punishes value iteration's sweep count more than it punishes policy iteration's round count.