Decisions change future opportunities
A repair has an immediate cost but can change the condition in which the next decision is made. Comparing only this period's cost misses that consequence. A finite-horizon Markov decision model records the current condition, the available action, the cost, and the distribution of the next condition.
Definition 8.4.1
(Finite-horizon Markov decision model)
Let be a finite nonempty state set, a finite nonempty action set for every state , and a fixed horizon with decision stages . At each stage, observe the current state , choose an available action , pay a deterministic finite cost , and draw the next state with probabilities . Each probability is nonnegative and sums to one over . After stage , pay a finite terminal cost . The model is known, and there is no discounting in this note.
The Markov assumption says that, conditional on current state and action, the next-state distribution is regardless of earlier history. An admissible policy may use all previously observed states and actions and may randomize, but cannot use future observations or future random outcomes.
If a worn component's future also depends on age, age must be included in the state before using this model. We minimize expected total cost, not the worst possible realized cost.
Backward recursion
Definition 8.4.2
(Optimal cost-to-go)
is the least expected cost, over admissible policies, from stage through the terminal cost when the current state is . At the horizon .
Theorem 8.4.3
(Bellman's backward recursion)
For and every ,
Recording, for every stage and state, any action attaining the minimum gives a deterministic time-dependent policy that is optimal from every starting state.
The immediate cost is paid now; the sum averages the optimal continuation costs using the next-state probabilities. Finiteness of ensures the minimum is attained.
Proof
(Backward induction on the stage)
At stage the statement is the definition. Assume that is the optimal cost-to-go at stage and that the recorded actions from stage on attain it from every state. Write for the bracket in the recursion.
Lower bound. Fix any admissible policy and any history ending in state at stage . The policy chooses with some probabilities . Given , the next state has law by the Markov assumption. After observing , what the policy does from stage is an admissible policy started at , so its expected cost is at least . Hence the expected cost is at least
Attainment. Choose an action attaining the minimum and, after observing each possible next state, follow the recorded policy. Its expected cost is exactly . So equals the minimum and the recorded policy is optimal from stage . Ties can be broken arbitrarily.
Proof X-ray
What the Markov assumption and finiteness do in the induction
The key move is to condition on the next state: once s prime is observed, the remaining problem is again a problem of the same form, started at stage t+1. That step needs the Markov assumption. If the transition law depended on earlier history, the continuation from s prime would depend on how s prime was reached, and V at stage t+1 would not be a function of s prime alone.
Randomization is handled by a single averaging inequality: an average of the brackets is never below their minimum, so a deterministic choice loses nothing. Finiteness of the action sets is used only to make the minimum attained; with infinitely many actions the infimum need not be reached by any action. The induction runs backward because each stage needs the next stage's values, and the base case is supplied by the terminal cost.
Two stages of maintenance
Worked example 8.4.4
(A time-dependent maintenance policy)
Take for good and bad condition, and . At , maintain costs and keeps surely; wait costs and leads to or with probability each. At , repair costs and makes the next state surely; wait costs and leaves surely. These rules are the same at both stages. Terminal costs are , .
At stage , , so maintain. Also , so repair. At stage , , so wait. Finally , so wait. Waiting at now is optimal even though maintaining at is optimal one stage later: the continuation horizon matters.
Counterexample mode
The cheapest immediate action need not be best
At stage 1 in state B, waiting costs zero immediately, but leaves terminal cost four. Repair costs two and reaches terminal cost zero, for a smaller total of two. An immediate-cost rule chooses wait and is suboptimal here. This is an expected-cost comparison; a different transition model can change the policy.
Worked example 8.4.5
(Evaluating the myopic policy)
The policy that always waits is evaluated by the same recursion with the minimum replaced by its single action. At stage : from the expected terminal cost is , and from it is . At stage from : . The optimal value is half of this, so ignoring the future doubles the expected cost here. From the myopic policy costs , against .
Worked example 8.4.6
(Adding a third stage)
Keep the same rules with . The last two stages see the same values as before, now called and , so the new first stage uses and :
Both states wait at stage . In state the repair is postponed to the last stage: repairing at stage costs , because the restored good state must still be looked after for two more stages. Check: wait, wait, repair from costs .
Common mistakes
Common mistake
(Reusing one stage's decision rule at every stage)
The optimal action depends on the stage, not only on the state. In the two-stage example the best action at is wait at stage and maintain at stage . A policy written as a single map from states to actions cannot represent this optimal plan.
Common mistake
(Omitting the terminal cost)
The recursion starts from , not from . With , waiting in at stage would appear to cost and repair , reversing the correct decision.
Scope and interpretation
A policy specifies an action for each reachable state and stage, including states not realized on one sample path. An optimal expected cost is not a guarantee that every realized path has that cost. Finite horizon and finite actions support the backward proof above; infinite-horizon limits, unknown transition probabilities, partial observation, risk constraints, and continuous state spaces require additional assumptions and are not implied here.
Exercises
Quick check
(Recompute in the two-stage example and identify the action attaining it.)
Solution · Answer
Maintaining costs . Waiting costs . So and maintain is optimal.
Quick check
(In state at stage , what is the expected continuation cost after waiting, before adding the immediate cost?)
Solution · Answer
The next state is equally likely to be or , so the continuation is . Waiting costs zero immediately, so the total is also .
Quick check
(What is if waiting at at stage costs instead of , with all other rules unchanged?)
Solution · Answer
The modified wait costs ; repair costs . Thus and both actions tie.
Quick check
(Why is the terminal cost needed in the last-stage comparison?)
Solution · Answer
The state reached after the last decision still incurs . Omitting it changes the objective and would incorrectly treat waiting in as costing zero overall.