MATH2070 Chap.11 Dynamic Programming by Backward Induction
Dynamic Programming by Backward Induction
Dynamic programming solves multistage decisions by summarising the past in a state and valuing future options recursively. The principle of optimality says that the remaining decisions of an optimal policy must themselves be optimal from the state they reach. Backward induction starts with terminal values, applies the Bellman recursion one stage at a time, and records the action attaining each optimum.
A forward trace then reconstructs the policy rather than merely reporting its value. A sufficient state retains all information affecting future feasibility and reward while discarding irrelevant history. Terminal conditions anchor the recursion, and infeasible actions must be excluded from each state-specific action set.
Storing only values is insufficient when the required output is a policy, so argmin or argmax choices, including ties, must be retained during the backward pass. Comparing the reconstructed path's accumulated contribution with the initial value provides a direct check on transitions, indexing and optimisation direction.
What this chapter covers
- 01
Stages, states and actions
- 02
State transitions
- 03
Terminal values
- 04
Bellman recursions
- 05
Backward induction
- 06
Policy reconstruction
- 07
State design and complexity
Worked example · free
Choose a two-stage policy
- 1Define the stage, state, admissible actions and transition rule.
- 1Record the terminal value for each reachable final state.
- 1Evaluate the final decision stage and store each maximising action.
- 1Apply the Bellman recursion at the initial stage.
- 1Trace stored actions forward to report the complete policy.
Key terms
- State
- A summary containing the information needed for future decisions.
- Bellman recursion
- A recurrence expressing current optimal value through immediate reward and future optimal value.
- Terminal value
- The value assigned when no decision stages remain.
- Policy
- A rule selecting an action for each relevant stage and state.
- Admissible action
- A decision permitted in a particular stage and state. Restricting the Bellman comparison to admissible actions prevents infeasible choices from receiving a continuation value and winning the optimisation accidentally.
- Continuation value
- The optimal future value associated with the next state after a current action. Backward induction reuses this stored quantity instead of enumerating every remaining decision path from the beginning.
Dynamic Programming by Backward Induction FAQ
Why does dynamic programming work backward?
The last decision can be valued directly from terminal outcomes. Once those values are known, the preceding stage treats them as future consequences, allowing the same reasoning to repeat until the initial state is reached.
What makes a good state variable?
A good state retains all information from the past that can affect feasible future actions or rewards, while discarding irrelevant history. Too little information gives incorrect transitions; too much creates unnecessary computational work.
Why must I reconstruct the policy after computing the value?
A maximum value alone does not identify which actions achieve it. Recording each argmax during the backward pass and tracing those choices forward produces the actual decision sequence requested by most applications.
Exam move
Define the model in four columns: stage, state, admissible action and transition. Explain in words why the proposed state retains everything that can affect future feasibility or reward. Test this by imagining two histories reaching the same state; if their remaining choices differ, the state is missing information. Remove history variables that make no future difference so the recursion remains compact enough to calculate.
Write terminal values before the Bellman equation. Clarify whether the problem minimises cost or maximises reward and preserve that direction at every stage. For each state, list feasible actions, immediate contribution, next state and continuation value in a small table. Circle both the best value and an attaining action.
Infeasible actions should be excluded explicitly rather than assigned an accidental finite value that might win the comparison. Work backward one stage at a time and perform a local audit after each layer. Every continuation value used at stage t must come from the already completed stage t plus one. Check state indices, resource balances and boundary cases such as zero remaining capacity.
When ties occur, record all attaining actions or state the tie-breaking convention. The principle of optimality justifies reuse of continuation values, but it does not excuse an insufficient state or an invalid transition. After computing the initial value, reconstruct the policy forward. Start from the given initial state, select the stored action, apply the transition and repeat until the terminal stage.
Sum the realised contributions and compare them with the initial Bellman value. Keep an error ledger for state design, terminal condition, direction of optimisation, transition indexing and policy recovery. Practise networks, resource allocation and a small inventory-style example so that backward induction is recognised as a general decision method rather than a single diagram pattern.
Working through Dynamic Programming by Backward Induction in MATH2070? Sia is AskSia’s AI Mathematics tutor — ask any MATH2070 Dynamic Programming by Backward Induction question and get a clear, step-by-step explanation grounded in how MATH2070 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
