Value Iteration and Policy Iteration

If you already know exactly how a Markov decision process works — every possible state, every possible action, every transition probability and reward — you don't need to learn anything from trial and error. You can just compute the best policy directly using dynamic programming. Value iteration and policy iteration are the two standard ways to do that.

Value iteration repeatedly applies the Bellman equation to update an estimate of each state's value: the value of a state is updated to be the best of "reward now plus discounted value of wherever this action leads," using the current value estimates for every other state. This is repeated over and over across all states until the values stop changing meaningfully. Once the values have converged, the best action in any state is simply whichever one led to the highest computed value — the policy falls out of the value function almost for free.

Policy iteration works the other way around: it starts with some arbitrary policy, then alternates between two steps. First, policy evaluation: compute the actual value of following the current policy everywhere (solving a system of equations, or iterating toward it). Second, policy improvement: in each state, check whether a different action would do better than what the current policy does, and switch to it wherever it would. Repeat evaluate-then-improve until the policy stops changing — at that point it's provably optimal.

A small grid-world illustrates the difference well. In value iteration, you'd sweep the whole grid updating every cell's value estimate using rough, still-improving estimates of its neighbors, many times, before ever committing to a policy. In policy iteration, you'd pick a starting policy — say, "always move right" — fully solve for its exact value everywhere, then improve it in each cell, fully re-solve, and repeat; each improvement step is a bigger commitment but there tend to be fewer of them overall.

What this means in practice

Neither algorithm scales to problems with huge or continuous state spaces — that's exactly why methods like Q-learning and policy gradients exist, to approximate what these exact algorithms compute when a full table of states is impossible. But value and policy iteration remain the reference point: when someone says a learned policy "converged to the Bellman-optimal solution," this is the ground truth they're being compared against, and small toy MDPs are still the standard way to sanity-check that a new reinforcement-learning algorithm is implemented correctly.