An action no longer decides where you end up; it decides a distribution over where you end up. The recursion absorbs that with one change — the value of an action is its immediate reward plus the expected value of where it sends you — and everything else about filling the table backwards is unchanged. What is new is that the best action in a state can depend on how many periods remain, so a policy in a finite horizon carries a time index and a policy that does not is a special case rather than the norm.
Core ideas
Three ideas. The first is where the expectation goes, the second is what a policy now is, and the third is how the table is checked without using a value function.
max over a of E[...] says you choose the action and then chance resolves. E[max over a of ...] would say chance resolves first and you choose knowing the outcome, which is a completely different problem and a strictly better one — it is the perfect-information value that “Folding a Decision Tree Back” uses as an upper bound. Writing the two down side by side once is the cheapest way to stop confusing them.
The table has one column per period, and the argmax in a cell can differ from the argmax in the cell above it. In the instance here the small state harvests when one period is left and grows whenever two or more are, because growing pays almost nothing now and improves where you will be — and with nothing left to come, improving where you will be is worth nothing. A stationary policy is what you get when that never happens, which is a fact about an instance.
Fix a policy, put all the probability on a starting state, and push the distribution forward period by period, collecting the reward that policy earns in each state weighted by the probability of being there. No maximum is ever taken and no value is ever written, so this computation cannot repeat a mistake the recursion made. With two states, two actions and four periods there are 256 deterministic policies and the lab evaluates all of them.
The material
The recursion, the instance where the best action depends on the horizon, and the forward evaluation that checks the whole thing.
A set of states, a set of actions, a transition P(a, i, j) giving the probability of moving to state j when action a is taken in state i, a reward r(a, i) earned immediately, and a horizon of T periods. Every row of every transition table sums to 1 exactly.
A policy assigns an action to each state in each period. The value Vₜ(i) is the largest expected total reward obtainable from state i with T − t periods left, and satisfies Vₜ(i) = max over a of [ r(a,i) + Σⱼ P(a,i,j) · Vₜ₊₁(j) ] with V_T(i) = 0.
The lab refuses a transition row that does not sum to exactly 1, rather than normalising it. A distribution that does not add up is a modelling error and not a typing one: silently rescaling it would answer a question the reader did not ask, and every number on the page would be exactly right about it.
Read the small state down the table: harvest, grow, grow, grow. With one period left there is nothing to grow into, so the 3 that harvesting pays immediately wins; with two or more, growing pays 0 now and puts three quarters of the probability into the large state, which is worth 9 and then 27/2 and then 18. The large state harvests throughout, because harvesting there pays 9 and only knocks you back three times in four.
V₀(small) = 33/2 is a claim about a number. “The policy this table describes is worth 33/2 starting from the small state” is a different claim, and it is the one a reader can act on. The lab makes it separately: it takes the argmax in each cell, treats that as a fixed policy, and evaluates it by pushing a probability distribution forward from each starting state through four periods. Both come to 33/2 and 45/2.
Then it does the harder thing. There are two actions, two states and four periods, so a deterministic policy is eight independent choices and there are 256 of them. Every one is evaluated the same forward way, and the best starting from each state is recorded. The best from the small state is 33/2 and from the large state 45/2, which is what the table said. Three routes to the same pair of numbers, and only two of them involve a value function.
Switch to the example with an owned machine: keeping pays 3 a period and leaves it owned four times in five, selling pays 7 once and the sold state pays nothing ever again. With one period left the table sells, because 7 beats 3 and there is no future to protect. With two left it keeps, because keeping is worth 43/5; with three left it keeps again, at 247/25.
Same shape as the growing instance and a different story: here the action that pays best now is the one that destroys every future period, so it becomes correct only at the very end. An absorbing state is worth meeting because it is the cleanest case where a stationary policy is simply wrong.
The transition depends on the current state and the chosen action, and on nothing else. That is the Markov assumption, and it is doing a great deal of work: it says that how you arrived in the small state cannot matter, that the probabilities do not drift over the four periods, and that nothing outside the two named states influences anything. Each of those can be false, and each of them, if false, leaves every number in the table exactly right about a process that is not the one in front of you.
There is a second assumption hiding in the objective. Maximising expected total reward treats a certain 10 and a fifty-fifty gamble between 0 and 20 as the same thing. That is a choice about what the decision-maker cares about, it is not implied by anything in the model, and no amount of exact arithmetic on the expectation will reveal it. Say it out loud before quoting a policy.
Interactive
A value table is a claim; the policy it describes, evaluated forwards, is the evidence
Method
Five steps. The first is a check on the data and the last is a check on the answer, and skipping either produces confident nonsense.
One row per state per action. A row that does not sum to 1 is not a distribution and nothing downstream is meaningful; the lab refuses rather than normalising, because rescaling silently answers a different question.
V_T(i) = 0 for every state, unless the problem gives a terminal payoff. Every later column depends only on the column to its right, so one right-to-left pass fills the table.
r(a,i) plus the sum over j of P(a,i,j) times the value of j in the next column. Keep the arithmetic in fractions: the products and sums of rationals are rational, and a decimal here hides whether two actions are genuinely tied.
A state whose argmax is the same in every column has a stationary policy on this instance; a state where it changes does not, and the period where it changes is usually the interesting fact about the problem.
Put all the probability on a starting state, and for each period collect the reward the policy earns in each state weighted by the chance of being there, then push the distribution through that period's transitions. No maximum, no value function. The number that comes out should equal the table's first column.
The recursion, then the policy it describes evaluated by pushing a distribution forward, then the best of all 256 deterministic policies evaluated the same way.
The forward evaluation is worth doing once by hand because it makes the distribution concrete: after one period there is a three-quarters chance of being in the large state, and every reward from then on is weighted by where the process actually is rather than by where it was aimed. Nothing in that computation resembles the recursion, which is exactly why it is a check.
For a rehearsal, set the horizon to one period with the slider and read the policy: both states harvest, and the values are 3 and 9. Then raise it one period at a time and watch the small state flip to growing and stay there. The flip happens between one period and two, and the reason is visible in the arithmetic: growing is worth 15/2 against harvesting's 6.
The harder rehearsal: change the reward for harvesting in the small state from 3 to 8 and find the horizon at which the flip disappears altogether. Then ask what you would have concluded from a table filled at a single horizon, and what it would have taken to notice.
You should be able to write the recursion with the expectation inside the maximum and say why the other order is a different problem, check the transition rows before computing anything, identify the period at which an argmax changes and explain it from the arithmetic, and push a distribution forward through a fixed policy to reproduce the value independently.
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.