Put an action in every state and a reward on every state-action pair, and the chain becomes a decision problem. A policy picks one action per state, and it induces an ordinary Markov chain whose discounted value solves v = r + γPᵈv — n linear equations in n unknowns, solved exactly. Policy iteration alternates that solve with a greedy improvement and stops because there are finitely many policies and the value never decreases: a termination proof rather than a tolerance. Beside it the page runs value iteration, which approaches the same numbers from below and is still 7.06 short after twelve steps.
Core ideas
Three ideas. The first turns a decision problem into a chain, the second is the solve that was already built, and the third is why the loop is guaranteed to end.
Fix one action per state and the transition matrix is determined: row s is the row that action gives. So a policy is an ordinary Markov chain with a reward attached, and everything already built applies to it. The decision problem is the question of which of the finitely many chains to be.
v(s) = r(s) + γ Σ P(s′|s) v(s′) is n equations in n unknowns, and it is solved by the same exact elimination that produced the steady state. So the value of a policy is 265/11 and 285/11 rather than a decimal near them, and a comparison between two policies is a comparison of fractions. Iterating that equation would also work and would never finish.
Greedy improvement never decreases the value of any state, and there are finitely many policies — 2ⁿ with two actions — so a policy cannot recur without the value having stayed put, which is the stopping condition. That is a proof of termination. Value iteration below it stops when you stop looking, and the page prints how far short it is when you do.
The material
The model, the evaluation solve, the greedy improvement, the finiteness argument, and value iteration approaching a number the solve already has.
States 1, …, n, a finite set of actions, a transition matrix P(· | s, a) for each action, a reward r(s, a), and a discount γ with 0 ≤ γ < 1.
A policy d assigns one action to each state. Its value v_d is the unique solution of v = r_d + γ P_d v, where P_d and r_d are the matrix and the reward vector the policy selects. The unique solution exists because I − γP_d is invertible for γ < 1.
The lab takes two transition matrices and two reward vectors, one pair per action, and validates each matrix as a chain before anything else. The discount is set in twentieths so that it stays a fraction: at γ = 18/20 every value on the page is a rational with a small denominator, which is what makes the comparison between two policies decidable rather than approximate. The page heads its two action columns simply “action 1” and “action 2”; which real-world choice each stands for is in the matrices and the rewards you typed.
A round does two things. It evaluates the current policy by solving v = r_d + γP_d v exactly — the lab reports how many elimination operations that took — and then it improves: for each state it computes q(s, a) = r(s, a) + γ Σ P(s′|s, a) v(s′) for every action, using the v it just solved for, and switches to the best. If no state switched, the policy is optimal and the loop stops.
Look at the last comparison. 265/11 and 47/2 differ by 13/22, which is about 0.591. Both routes to it are exact, so the decision is decided; a floating-point evaluation would also have got it right here, and on a problem with a near-tie it would be choosing between two roundings and reporting a policy. That is the case exactness is insurance against, and it is not a rare one at discounts close to 1, where the values of neighbouring policies crowd together.
Greedy improvement produces a policy whose value is at least as large as the current one in every state. Since there are finitely many policies and the loop only stops when no state changes, the loop cannot run for ever, and the policy it stops at satisfies the optimality condition for every state.
Let d be the current policy with value v, and d′ the greedy policy. By construction r_{d′} + γP_{d′}v ≥ v entrywise, since the greedy choice is at least as good as the current action, whose value is exactly v.
Applying r_{d′} + γP_{d′}(·) repeatedly preserves that inequality, because P_{d′} has non-negative entries and γ > 0; the iterates converge to v_{d′}, so v_{d′} ≥ v. If the values are equal in every state, no state changed and the loop has stopped. Otherwise the value has strictly increased somewhere, so the policy is new. With finitely many policies the loop can only strictly increase finitely often.
□
That is worth contrasting with the other way of solving the same problem. Value iteration starts at zero and applies the improvement operator over and over; it converges, and there is no step at which anything tells you it has arrived. What people do instead is stop when the change between steps falls below a number they chose, which is a statement about the increments and not about the distance to the answer.
Because the exact value is on the same page, the lab can print what value iteration is actually short by rather than how much it moved last step. On the two-state example at γ = 9/10 the iterates start at (0, 0) and climb — 2.00000, 4.02500, 5.94875, 7.72569 — reaching 17.03023 at step twelve against an exact 265/11 = 24.09…. It is short by 7.06068 and 7.06080, and it approaches from underneath and never arrives.
Two things in that table are worth naming. The shortfall shrinks by a factor of about γ per step, which is why raising the discount towards 1 slows it down sharply while policy iteration takes the same two or three rounds. And the denominators grow by one power of the discount's denominator every step, from one digit to fifteen by step twelve, while the exact answer has a two-digit denominator — the iteration is accumulating complexity as it approaches a number that was simple all along.
At γ = 9/20 the two-state problem still stops in 2 rounds, with value (1330/341, 1770/341), and value iteration is within 0.0003 after twelve steps. At γ = 19/20 it still stops in 2 rounds, with value (1030/21, 1070/21), and value iteration is 27.02 short after twelve.
The number of rounds is a property of how many policies there are and how quickly the greedy step finds the best one; the iteration's progress is a property of γ. Those are different mechanisms, and the slider makes the difference visible in a few seconds.
The stock-control example has three states and rewards (4, 1, −3) under one action and (1, 0, −1) under the other. At γ = 9/10 policy iteration takes 3 rounds over 8 policies and settles on (1640/59, 1440/59, 1345/59).
The middle round is the instructive one: the greedy step swings the policy from all-hold to all-restock, values it at (10, 360/41, 310/41), and then swings the first state back. A method that stopped at the first improvement would have taken that middle policy and been wrong by between fifteen and eighteen in every state.
Interactive
each round is an exact linear solve, and the stopping argument is finiteness
Method
Four steps and a loop. The first is the one people skip, and it is what makes the comparison in the third meaningful.
Each action needs its own transition matrix and each of those has to be a chain in its own right: every row summing to 1. A single bad row anywhere means one of the policies being compared is not a chain, and the comparison will still produce a winner.
Solve v = r_d + γP_d v. Any starting policy will do — the loop is not sensitive to it — so take the obvious one. Solve rather than iterate: this is n equations in n unknowns and the elimination is short.
For each state compute q(s, a) for every action and take the best. Use the same v throughout the sweep; recomputing it mid-sweep is a different algorithm with different guarantees.
No change means the policy is greedy with respect to its own value, which is the optimality condition. Combined with finiteness and monotonicity, the loop terminates. This is a reason to stop; “the numbers stopped moving” is not, and on value iteration it is never even true.
Two states and two actions. Under one action the state decays faster and pays more when worn; under the other it holds better and pays more when good. Discount γ = 9/10, so there are four policies in total.
Round 1 is where the method earns its name. The policy being evaluated is not optimal, and the q values computed from its own value function still point at the better action: 683/31 beats 670/31 at the first state. That is the improvement theorem in one comparison — you do not need the optimal value function to find a better policy, only the current one's.
Round 2 stops, and it stops for a reason you can state: both states are already choosing the action their own value function prefers, so the policy is greedy with respect to itself. No tolerance was involved and no number had to be compared against a threshold.
The value-iteration block underneath is the comparison the whole page exists for. It is converging to 265/11, it is monotone from below, and after forty steps it is still 0.36952 short of a number the solve produced in four elimination operations. Its denominators have gone from one digit to fifteen on the way to a number whose denominator is 11.
For a rehearsal, set the discount to its lowest setting and predict what happens to both methods before looking. The supplied first move is that at a small γ the future barely counts, so the greedy one-step reward nearly decides the policy. Say what you expect of the round count and of the iteration's shortfall, then check: the rounds stay at 2 and the shortfall at twelve steps collapses to about 0.0003.
You should be able to build P_d and r_d from a policy, solve v = r_d + γP_d v as a linear system, compute q(s, a) for each action from that v and improve greedily, give the finiteness-and-monotonicity argument for termination, and say what value iteration's shortfall depends on and why its stopping rule measures the wrong thing.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.