Lesson · Dynamic Programming and Sequential Decisions · The recursion, backwards

The State Is What Is Left

Nobody hands you the stages. Here the data are a table — what each activity returns for nothing, one unit, two units and so on — and before anything can be solved a network has to be invented from it. The invention is the lesson: a node is how much is still unspent when an activity has to decide, which is a statement about what the future needs to know. Once that is settled the arithmetic is the previous page again.

Open the interactive lesson Practice

a state is what the FUTURE needs to know, not a record of what has happened here that is: how many units are still unspent when this activity decides stage = the activity deciding; node = units left; arc = units this one takes P 0 2 4 15 16 ; Q 0 6 8 9 10 ; R 0 3 7 8 9, four units: best return 21 20 state values against 35 splits, and the two agree exactly taking the best NEXT unit each time gives 15, and it is not an arithmetic error

The table, the network built from it, and the two numbers that must agree

Core ideas

What this lesson establishes

Three ideas. The first is a definition, the second is a construction, and the third is the failure the construction exists to avoid.

A state is a claim that two situations can be finished identically

Saying “the state is the number of units left” asserts that any two histories leaving the same number unspent have exactly the same future open to them. Here that is true, because the activities that remain do not care which of the earlier ones took what. If the return of a later activity depended on an earlier choice, the claim would be false and the table would be answering a different question — correctly, and about the wrong problem.

The network is built, not typed

There is no picture in the data. One stage per activity plus a finish; one node in each stage for each amount that could still be unspent; and one arc for each amount this activity could take, carrying that amount's return. With three activities and four units that is 20 nodes, and the lab draws them as a grid so that the state space is a thing you can see rather than a phrase.

A rule that looks one unit ahead is solving a smaller problem

The tempting shortcut is to hand out units one at a time, each to whichever activity gains most from the next one. It is fast, it is what a marginal argument suggests, and on the instance in the lab it returns 15 against the recursion's 21. Nothing about its arithmetic is wrong. It is choosing among the wrong set of plans, because it cannot pay for two poor units in order to reach a third good one.

The material

Inventing the nodes, and then solving the thing you invented

The data, the state, the network it forces, and the rule that gets this wrong for a reason worth understanding.

Definition · An allocation problem, and its state

Given activities 1 to n, a whole number u of indivisible units to hand out, and a return table giving rᵢ(x) for each activity i and each whole x from 0 up, choose x₁, ..., xₙ with Σ xᵢ ≤ u maximising Σ rᵢ(xᵢ).

The state before activity i decides is the number of units still unspent. The value function is g(i, s) = max over x from 0 to s of rᵢ(x) + g(i+1, s−x), with g(n+1, s) = 0 for every s: once there are no activities left, what remains is worth nothing.

Two things about that definition are worth saying out loud. The first is that rᵢ(0) must be 0 — a table whose first column is not zero is measuring something other than a return, and the lab refuses it by name. The second is that nothing anywhere records which activity took what; the state is a single number. That is not an economy, it is the modelling claim, and it is the thing to check before trusting any answer the table produces.

the table units: 0 1 2 3 4 P 0 2 4 15 16 Q 0 6 8 9 10 R 0 3 7 8 9 the network it forces, with four units to hand out: stage P stage Q stage R done 4 left --2u-> 2 left --1u-> 1 left --1u-> 0 left 3 left 1 left 0 left 2 left 0 left 1 left 0 left an arc from s left to s-x left carries the return of x units 5 nodes per stage, 4 stages: 20 state values in all

Filled from the finish back, the last column is zero everywhere, R's column is just its own returns, Q's column combines its returns with R's, and P's column combines all three. The value at the node marked 4 left in P’s column is 21, attained by P taking 3, Q taking 1 and R taking none. The lab prices all 35 ways of splitting four units across three activities and finds 21 as well, attained by exactly that split and no other.

The rule that looks at the next unit

Hand out the units one at a time. The first unit goes to Q, which gains 6 against P's 2 and R's 3. The second goes to R at 3, since Q's next unit gains only 2 and P's still gains 2. The third goes to R again at 4. The fourth is a tie among gains of 2, and whichever way it falls the total is 15. Every one of those comparisons is correct and the answer is six short.

Example · Why it loses, in one line

P's returns are 0, 2, 4, 15, 16, so its first two units gain 2 each and its third gains 11. A rule that asks only what the next unit is worth never sees the 11, because it never gets past the two units of 2 that stand in front of it.

The recursion sees it because it never asks about a unit at all: it asks what P should take given how much is left, and 3 is one of the options it prices. That is the difference between choosing a decision and choosing an increment, and the table's jump is there to make it visible rather than arguable.

Diminishing returns, and the tie that appears

Switch to the example whose three activities all have non-increasing marginal returns and the shortcut stops losing: the greedy split and the recursion both reach 19. But look at what the enumeration says about that 19. There are two splits attaining it — one unit to P, two to Q, one to R, and two to P, one to Q, one to R — so even in the friendly case the answer is a set, and a page printing one of them would be printing a choice the model never made.

That is the same point as the ties on the previous page, arriving from a different direction, and it is why the lab prints both the route the recursion reconstructed and every split the enumeration found. Where the two examples differ is in what the tie costs you. A tie among optimal routes is a free choice; the shortcut's failure is not a tie at all, it is a worse answer that looks like a method.

What the state left out

The model here says that four units handed to P, Q and R in any order are worth the sum of three table lookups. That rules out a great deal: no activity can make another cheaper, no unit can be split, no combination can be forbidden, and nothing costs anything to set up. Each of those, if true of the situation, is a state the model does not carry — and the recursion would still return an exact optimum, of the problem it was given.

Two activities rather than three is worth a minute, because the whole table fits on one line: with P at 0, 7, 11, 14, 15 and Q at 0, 5, 10, 13, 16, four units split two and two return 21, out of 15 possible splits. Small enough to check every one of them by hand, which is the only way to be sure the recursion is not being believed rather than checked.

Interactive

Allocating indivisible units

The state is what is left, and the network has to be built before it can be solved

Build the network from the table, and check the split against every other split

There is nothing to draw here until the state is chosen. A node is how many units are still unspent when an activity has to decide, an arc is how many that activity takes, and the drawing is what those two sentences produce. The recursion fills it backwards; every possible split is then priced directly from the table, with no network involved, and both numbers are shown. This example is the one where an activity is nearly worthless until its third unit.

Worked example

Each activity and what it returns for 0, 1, 2, ... units

Units to allocate4

The best total return—

By enumerating every split—

Do the two agree?—

The allocation it chose—

States the recursion visited—

Splits there are—

There is no network to type here: the nodes are the amounts that could still be unspent when an activity has to decide, and the arcs are the amounts it could take. Building that network is the lesson — once it exists, this is the previous page again.

Method

Turning a table into a network you can solve

The first two steps are the whole of the difficulty, and neither of them is arithmetic.

Say what the future needs to know, in a sentence

Not what has happened — what still matters. Here: how much is left. Then test the sentence by finding two different histories it calls the same state, and asking whether they really do have the same options from here on.

Make the stages the decisions, in any fixed order

One stage per activity. The order is yours to choose and the answer does not depend on it, which is itself worth checking on a small instance: reorder the activities in the lab and the optimum does not move, though the table does.

Draw one node per reachable state and one arc per decision

From s left in stage i there is an arc to s−x left in stage i+1 for every x from 0 to s, carrying rᵢ(x). Every arc runs forward by construction, so the recursion applies unchanged.

Fill from the last stage back, maximising rather than minimising

The finish is worth zero in every state. Nothing else about the method changes: the direction of the comparison is a parameter, not a different algorithm.

Check the value against the enumeration before reading the split

There are C(u+n, n) splits — the units need not all be spent — which is 35 here, and the lab prices all of them. If the two numbers agree, read the split off the argmins; if they do not, the network you built is not the problem you meant.

States, networks and marginal rules

Score 0 / 0

Choose the answer you can justify.

The recursion, and the rule that looks one unit ahead

Four units, three activities, the table with the jump in it. The left column is the recursion filled from R back; the right is the marginal rule, step by step.

table 0 1 2 3 4 marginal gains P 0 2 4 15 16 2 2 11 1 Q 0 6 8 9 10 6 2 1 1 R 0 3 7 8 9 3 4 1 1 THE RECURSION, filled from the end stage R 0 left 0 1 left 3 2 left 7 3 left 8 4 left 9 stage Q 0 left 0 1 left 6 2 left 9 3 left 13 4 left 15 take 1 take 1 take 1 take 2 stage P 4 left max( 0+15 , 2+13 , 4+9 , 15+6 , 16+0 ) = 21 ^^^^^^ P takes 3 best return 21 split P=3 Q=1 R=0 35 splits priced directly from the table: best 21, the same split, only one THE MARGINAL RULE, one unit at a time unit 1 gains P 2 Q 6 R 3 -> Q running total 6 unit 2 gains P 2 Q 2 R 3 -> R running total 9 unit 3 gains P 2 Q 2 R 4 -> R running total 13 unit 4 gains P 2 Q 2 R 1 -> P running total 15 its answer 15 the optimum 21 every comparison correct

The fourth line of the marginal rule is the one to stare at. P's next unit is worth 2 and the rule duly treats P as the weakest of the three, at the exact moment when P holding three units would be worth 15. The rule is not approximating the optimum; it is optimising over a smaller set of plans, the ones reachable by never regretting a unit.

For a rehearsal, change P's table to 0, 2, 4, 6, 16 — a jump at the fourth unit instead of the third — and predict both answers before running anything. The recursion has to be willing to give P everything, and the marginal rule never will.

The harder rehearsal: build a table on which the marginal rule and the recursion agree at four units and disagree at five. It exists, it is not hard to find once you look for the jump, and constructing one is a better test of whether the failure is understood than any number of instances where the rule happens to win.

Common mistakes

Making the state a record of the past“Activity P has been given two units” is history, not state. It is sometimes necessary — if a later return depends on it, it belongs in the state — but reaching for it by default makes the state space explode for no reason, and it hides the question you should be asking, which is whether the future really depends on it. Write the sentence about the future first.

Reading a marginal rule as an approximationIt is not solving this problem slightly worse; it is solving a different problem exactly. The set of plans reachable by handing out units one at a time, never revisiting, is a strict subset of all splits, and it excludes exactly the ones that pay upfront. Calling the gap an approximation error suggests it shrinks with care, and it does not.

Trusting the reconstruction without the enumerationThe recursion's value and the split it reconstructs are two different pieces of arithmetic, and the second one involves walking argmins through a network that was itself generated. The lab prices every split directly from the table for exactly this reason, and shows nothing as an answer until the two agree. At 35 splits that check is free; the habit is what has to survive to larger instances.

Check your understanding

✓

Finish when you can take a return table, state what a node means in one sentence, build the network, and say why a rule that looks at the next unit is not an approximation.

You should be able to justify the state as a claim about the future, construct the stages and arcs from the table alone, fill the values backwards while maximising, reconstruct every optimal split, and reproduce the instance on which a marginal rule returns 15 where the optimum is 21.

Note: The state here was a single number and the choice of it was almost forced. That will not last. The next lesson, “Wagner-Whitin and the Order Intervals”, has a state that is genuinely surprising the first time — not the stock on hand, which is what everybody reaches for, but the period the last order was placed in — and the reason that works is a small theorem about what an optimal plan never does.