Every table on this course has been filled from the end. Take the end away and the recursion has no base case — but the value still satisfies an equation: what a state is worth is its reward plus a discounted average of what the states it leads to are worth. That is v = r + γPv, and it is a linear system. Row reduction solves it exactly. Value iteration, which is the same map applied over and over from zero, approaches it and never gets there, and the denominators make the difference visible in a way that decimals cannot.
Core ideas
Three ideas: why the recursion stops working, what replaces it, and what the iteration is actually doing while it fails to arrive.
Vₜ was always defined from Vₜ₊₁, and the chain terminated at V_T = 0. Remove the horizon and that chain has no end to hang from. What survives is the self-consistency the values must satisfy: v(i) = r(i) + γ Σⱼ P(i,j) v(j) for every state at once. That is not a rule for computing v; it is a condition v obeys, and finding v means solving it.
With γ = 1 the totals would generally be infinite and the equation would have many solutions or none. With 0 ≤ γ < 1 the matrix I − γP is invertible for every stochastic P, so there is exactly one v. The discount is doing mathematical work as well as modelling work, and a reader who treats it purely as a preference about the future is missing why it is there.
Start at v₀ = 0 and apply v ← r + γPv. Each step replaces the error vector by γP times itself, so the error shrinks by a factor tending to γ a step and the values reach the fixed point at no finite step. In exact arithmetic this is not a rounding story: every iterate is a rational with a denominator one power of γ's denominator larger than the last, and the fixed point 22/7 is not among them.
The material
Where the base case went, what the equation is, and what the iteration is accumulating while it approaches the answer.
Fix a transition matrix P with rows summing to 1, a reward r(i) earned on each visit to state i, and a discount factor γ with 0 ≤ γ < 1. The value v(i) is the expected total of r earned from state i onward, with a reward k steps away counted at γᵏ of its face value.
It satisfies v = r + γPv, equivalently (I − γP)v = r. Since I − γP is invertible for every stochastic P when γ < 1, that system has exactly one solution.
Two states will do. Let P send the first state to each of the two with probability one half, and the second to the first with probability one quarter and to itself with three quarters; let the rewards be 1 and 3, and let the discount be one half. Writing (I − γP)v = r out gives two equations in two unknowns, and row reduction solves them in four operations.
That last line is the whole reason for exact arithmetic on this page. A decimal solution would give a residual of something like 1e−16, which is indistinguishable from a small error in the solve, and the claim “this is the fixed point” would be unverifiable on the page. As fractions the residual is zero, and the reader can check the two lines above by hand.
Start at zero and apply the map. v₁ is just r, which is (1, 3). v₂ is (2, 17/4). Then (41/16, 155/32), then (365/128, 1315/256), and so on. Each step replaces the gap by γP times itself, so the ratio settles to γ a step — a half here, so the gap heads towards quartering every two steps: 1.14285714, then 0.29129464, then 0.07291085, then 0.01822908, then 0.00455729, then 0.00113932.
The denominator column is the part a decimal cannot show. Every iterate is a rational whose denominator carries one more power of two than the last, so the iteration is not slowly approaching 22/7 through numbers that are nearly it — it is walking through an infinite sequence of rationals none of which is 22/7, and getting more expensive to write down at every step. Ten digits after twelve steps, and nothing stops it.
Keep the same chain and the same rewards and set the discount to nine tenths. The fixed point becomes 670/31 and 750/31, about 21.6 and 24.2, which is far larger — a patient decision-maker values the same stream much more highly. Row reduction still takes four operations.
Value iteration, on the other hand, is now multiplying the gap by 9/10 rather than 1/2 at each step, so after twelve steps it is nowhere near. The two methods have not changed. What has changed is that one of them is sensitive to a parameter the other is indifferent to, and that is the argument for solving rather than iterating.
A three-state chain with rewards 2, 0 and 5 and a discount of three quarters gives 1508/163, 1096/163 and 2192/163. The system is 3 by 3, row reduction handles it in one pass, and the residual is again exactly zero in every row.
The denominators of the iterates are worse here, not better: at twelve steps they run to eighteen digits. Nothing about the exact solve has got harder, and everything about the iteration has — which is the pattern rather than a feature of this instance.
None of this makes the iteration useless, and the page is careful not to say so. It needs no matrix inverse and no elimination, it works when the state space is far too large to write I − γP down, and it extends directly to the case where an action has to be chosen in each state, where the map has a maximum in it and the system stops being linear. On a chain this small, with no action to choose, it is the slow way round — and seeing it be the slow way round on a small instance is how you learn what it is buying you on a large one.
There is no decision here. Fix a policy and its value is a linear system; ask for the best policy and you need the maximum back inside the map, at which point the equation is no longer linear and the method that solves it alternates between evaluating a policy and improving it. That method needs a chain with a class structure and a steady state already in hand, which is Markov Chains, Decisions and Queues, and it is deliberately not attempted here.
And the discount itself is a modelling choice standing in for several different things — an interest rate, a probability of the process ending, an impatience — which happen to have the same arithmetic and quite different justifications. The value 22/7 is exactly right for γ = 1/2, and the question of whether 1/2 is the right number is not one the residual can answer.
Interactive
One method approaches the answer and the other lands on it; both are exact here
Method
Four steps. The third is the one that makes the answer checkable, and it costs almost nothing.
v(i) = r(i) + γ Σⱼ P(i,j) v(j). Resist the urge to read it as an assignment: it is a condition on the whole vector at once, and every state's equation mentions every other state's value.
Move the γPv across. If γ = 1 the matrix is singular for any stochastic P — the all-ones vector is in its kernel — and there is no unique solution to find. No such discount appears in the selector, and the solver behind it refuses a singular system by name rather than returning a number.
The same elimination used everywhere else on this path. For two or three states it is a handful of operations and the entries stay rational throughout, because the data are rational.
Compute r + γPv − v row by row. In exact arithmetic it is 0, not nearly zero, and that is a check a floating-point solve cannot offer. It takes one pass and it converts a claim into something the reader can verify.
Run the map from zero and watch two things: the gap shrinking towards a factor of γ a step, and the denominator growing by one power of γ's denominator each step. The second is the honest picture of what “never arrives” means.
The same two-state chain twice: once as a linear system with the answer checked by substitution, and once as a sequence of iterates with their denominators.
The gap column is geometric in the limit, with ratio γ per step, which is a quarter per two steps at γ = 1/2; the early ratios sit a little above it because each step multiplies the gap by γP and P mixes the two states. Extrapolating it says the iteration needs about ten more steps per three decimal places and never terminates, and the denominator column says what those steps cost: one more digit each, forever.
For a rehearsal, set the discount to 99/100 in the selector and read the fixed point. Row reduction still does four operations and the residual is still exactly zero. Then look at the plot: after twenty-four steps, the most the slider allows, the iteration has barely left the axis. One method noticed the parameter and the other did not.
The harder rehearsal: set γ to 1/2 and change the rewards to (1, 1). Predict the fixed point before solving — every state pays 1 forever, discounted at a half, so the value should be 1/(1 − 1/2) = 2 in both states regardless of P. Check it, then perturb one entry of P and confirm that the value does not move at all. That invariance is a property of the equation, and it is a good test of whether the equation is understood rather than merely solved.
You should be able to say why an infinite horizon has no base case, rearrange the self-consistency condition into (I − γP)v = r, justify invertibility from γ < 1, solve a two-state or three-state system by row reduction, substitute back to get a zero residual, and describe value iteration as a sequence of exact rationals that approaches the answer without reaching it.
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.