44.08.01 · optimization-control / dynamic-programming

Finite-Horizon Dynamic Programming and the Principle of Optimality

shipped3 tiersLean: none

Anchor (Master): Bertsekas 2017 Dynamic Programming and Optimal Control 4e (Athena Scientific) Vol. 1 Ch. 1 (the full finite-horizon theory: perfect-state-information basic problem, the DP algorithm and its optimality proof, the deterministic shortest-path reduction, and state augmentation for delays and correlated disturbances); Puterman 1994 Markov Decision Processes (Wiley) Ch. 4 (finite-horizon MDPs and the optimality equations)

Intuition Beginner

Some decisions cannot be made one at a time in isolation, because each choice changes the situation you face next. A delivery driver picking the next street, a chess player choosing a move, a company deciding how much to produce this month — in every case a good choice now is good only if it sets up good choices later. Dynamic programming is the method for these staged problems. It asks not "what is the best single move?" but "what is the best whole plan, accounting for everything that follows?"

The core trick is to work backward. Imagine you are one step from the finish. There is no future left to worry about, so the best move is whatever costs the least right now. Now step back one stage. You do not need to re-plan the whole future, because you already know the best cost from every place the next stage could land you. You only weigh your current options against those already-computed future costs. Keep stepping backward, stage by stage, until you reach the start.

This is the principle of optimality, and it is almost a tautology once stated: any piece of a best plan must itself be a best plan for the situation it starts from. If some later stretch of your route could be improved, then your supposedly best plan was not best after all. Because of this, the enormous problem "find the best plan over all stages at once" breaks into a chain of small problems, one per stage, each solved by looking only one step ahead at a stored summary of the future.

The payoff is that a search which would otherwise explore an explosion of full plans collapses into a tidy backward sweep that visits each situation once.

Visual Beginner

Picture a small map laid out in columns, one column per stage, where you must travel from a start node on the left to a goal on the right, paying a labeled toll on each arrow you cross. Working backward, you write next to every node the cheapest total toll from that node to the goal.

The boxed number at a node is its cost-to-go: the best you can do from there onward. The rule that fills each box is to look one arrow ahead, add the arrow's cost to the box already written at the node it points to, and keep the smallest such sum. The bold arrow records which choice achieved it.

stage you are filling	what you already know	how you fill a box
the goal column	nothing left to pay	box = $0$
one stage before the goal	the goal boxes	box = cheapest arrow cost to the goal
any earlier stage	all later boxes	box = min over arrows of (arrow cost + next box)

Reading the bold arrows forward from the start spells out the best plan, even though every box was computed backward.

Worked example Beginner

A small factory plans production for $2$ months to meet a fixed demand, choosing each month how many units to make. The "state" is the units already in stock at the start of a month. To keep arithmetic clean, suppose the stock can be $0$ or $1$ unit, each month you may produce $0$ or $1$ unit, producing costs $3$ per unit, and holding leftover stock to the next month costs $2$ per unit. Demand is $1$ unit each month, and you must never run short. At the end (after month $2$ ) leftover stock is worthless but not penalized.

Stage labels: decisions are made at the start of month $1$ (call it $k = 0$ ) and month $2$ ( $k = 1$ ); $k = 2$ is the end.

End values ( $k = 2$ ). Whatever stock remains costs nothing more: $J_{2} (0) = 0$ and $J_{2} (1) = 0$ .

Month $2$ ( $k = 1$ ). You need $1$ unit to meet demand. If you start with stock $1$ , produce $0$ : cost $0$ , ending stock $0$ , so $J_{1} (1) = 0 + J_{2} (0) = 0$ . If you start with stock $0$ , you must produce $1$ : cost $3$ , ending stock $0$ , so $J_{1} (0) = 3 + J_{2} (0) = 3$ .

Month $1$ ( $k = 0$ ), starting from stock $0$ . Demand is $1$ , so you must have a unit this month. Option A: produce $1$ , use it, end with stock $0$ , carry nothing. Cost now $3$ , plus $J_{1} (0) = 3$ , total $6$ . Option B: produce $2$ — not allowed, the cap is $1$ . So with a start of $0$ you cannot stock ahead here; the only feasible plan costs $6$ . Suppose instead the start were stock $1$ : produce $0$ this month (cost $0$ ), use the unit, end at stock $0$ , then $J_{1} (0) = 3$ , total $3$ .

What this tells us: from an empty start the best two-month cost is $J_{0} (0) = 6$ , achieved by producing exactly to meet each month's demand. Each monthly choice was decided by adding its immediate cost to a future cost already computed and stored — never by re-examining the whole plan. That backward bookkeeping is the entire method.

Check your understanding Beginner

Exercise (easy, multiple-choice).

The principle of optimality says that:

The first decision in a plan is always the most important one.
Any tail end of an optimal plan is itself optimal for the situation it starts from.
Every stage of an optimal plan has the same cost.
The best plan never revisits the same state.

Hint

Think about why you could store one "best future cost" per situation and never need to re-plan the whole future.

Answer

B. If a later stretch of a best plan could be improved, swapping in the better stretch would improve the whole plan, contradicting that it was best. So each tail is best for where it starts, which is exactly what lets you store one cost-to-go per state. Feedback-correct: this is the property that turns one giant search into a backward chain of one-step problems. Feedback-wrong: A, C, and D each describe things that may or may not happen in a particular problem, but none is the principle.

Formal definition Intermediate+

A discrete-time controlled dynamical system over a horizon of $N$ stages is specified by, for each stage $k = 0, 1, \dots, N - 1$ : a state space $S_{k}$ , a control space $C_{k}$ , a nonempty admissible-control set $U_{k} (x) \subseteq C_{k}$ for each state $x \in S_{k}$ , a disturbance space $D_{k}$ , a system map $f_{k} : S_{k} \times C_{k} \times D_{k} \to S_{k + 1}$ , and a disturbance distribution $P_{k} (\cdot ∣ x, u)$ on $D_{k}$ that may depend on the current state $x$ and control $u$ but not on the past. The state evolves by

x_{k + 1} = f_{k} (x_{k}, u_{k}, w_{k}), w_{k} \sim P_{k} (\cdot ∣ x_{k}, u_{k}), k = 0, \dots, N - 1,

with initial state $x_{0} \in S_{0}$ . The dependence of the disturbance law on only $(x_{k}, u_{k})$ is the controlled-Markov structure of 37.05.01; expectations below are over the disturbances $w_{0}, \dots, w_{N - 1}$ on a probability space 37.01.01.

A (deterministic Markov) policy is a tuple $π = (μ_{0}, \dots, μ_{N - 1})$ of functions $μ_{k} : S_{k} \to C_{k}$ with $μ_{k} (x) \in U_{k} (x)$ for all $x$ ; such a $π$ is admissible, and $Π$ denotes the set of admissible policies. Under $π$ the controlled system is a Markov chain with $x_{k + 1} = f_{k} (x_{k}, μ_{k} (x_{k}), w_{k})$ .

Given stage-cost functions $g_{k} : S_{k} \times C_{k} \times D_{k} \to R$ for $k = 0, \dots, N - 1$ and a terminal cost $g_{N} : S_{N} \to R$ , the expected cost of $π$ from $x_{0}$ is

J_{π} (x_{0}) = E [g_{N} (x_{N}) + k = 0 \sum N - 1 g_{k} (x_{k}, μ_{k} (x_{k}), w_{k})],

the expectation taken over $w_{0}, \dots, w_{N - 1}$ with $x_{k + 1} = f_{k} (x_{k}, μ_{k} (x_{k}), w_{k})$ . The basic problem (perfect state information) is to minimize $J_{π} (x_{0})$ over $π \in Π$ ; the optimal cost is

J^{*} (x_{0}) = π \in Π in f J_{π} (x_{0}),

and a $π^{*}$ attaining it is an optimal policy. The deterministic problem is the special case where each $P_{k}$ is a point mass, so $w_{k}$ drops out and $J_{π} (x_{0}) = g_{N} (x_{N}) + \sum_{k} g_{k} (x_{k}, μ_{k} (x_{k}))$ along the deterministic trajectory.

The cost-to-go (value) functions $J_{k} : S_{k} \to R$ , $k = 0, \dots, N$ , are defined by the backward recursion

J_{N} (x) = g_{N} (x), J_{k} (x) = u \in U_{k} (x) in f E_{w_{k} \sim P_{k} (\cdot ∣ x, u)} [g_{k} (x, u, w_{k}) + J_{k + 1} (f_{k} (x, u, w_{k}))] .

This recursion is the DP algorithm; the right-hand side is the stage- $k$ Bellman operator applied to $J_{k + 1}$ . The symbols $x_{k}$ (state), $u_{k}$ (control), $w_{k}$ (disturbance), $J_{k}$ (cost-to-go), $J_{π}$ (policy cost), $J^{*}$ (optimal cost), and $U_{k} (x)$ (admissible set) are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"Optimizing each stage's immediate cost separately gives the optimal policy." Greedy stage-wise minimization of $g_{k}$ alone ignores how a control reshapes the future state. In the worked factory example, producing the cheapest amount each month locally would fail to stock ahead when stocking ahead lowers total cost; only the cost-to-go $J_{k + 1}$ , not $g_{k}$ alone, carries that future information.
"The cost-to-go $J_{k}$ depends on how the chain reached state $x$ ." It does not. Because the disturbance law depends only on $(x_{k}, u_{k})$ — the controlled-Markov property 37.05.01 — the optimal remaining cost from $x$ at stage $k$ is a function of $(x, k)$ alone. A policy that tried to use past states could not beat the state-feedback optimum; this is what makes Markov policies suffice for the perfect-information problem.
" $J^{*} (x_{0}) = J_{0} (x_{0})$ is the definition, not a theorem." The function $J_{0}$ is built by the backward recursion above, while $J^{*}$ is an infimum over all policies of an expectation. That these coincide is the content of the optimality theorem; equating them by fiat skips the interchange of the policy-infimum with the staged expectation.
"State augmentation changes the problem." When the disturbance is correlated or the dynamics involve a delay, one enlarges the state (e.g. $\tilde{x}_{k} = (x_{k}, x_{k - 1})$ ) so that the augmented system is again controlled-Markov. The augmented problem has the same optimal cost and policy as the original; augmentation is a reformulation that restores the Markov structure the DP algorithm requires, not a different optimization.

Key theorem with proof Intermediate+

The signature result is that the DP algorithm solves the basic problem: the backward recursion computes the optimal cost and a greedy policy read from it is optimal. It is the single statement that justifies replacing one optimization over all policies by $N$ separable one-stage optimizations.

Theorem (principle of optimality and optimality of the DP algorithm). Let $J_{0}, \dots, J_{N}$ be generated by the DP algorithm, and assume that for each $k$ and each $x \in S_{k}$ the infimum defining $J_{k} (x)$ is attained by some $μ_{k}^{*} (x) \in U_{k} (x)$ (e.g. when each $U_{k} (x)$ is finite). Then for every $x_{0} \in S_{0}$ ,

J^{*} (x_{0}) = J_{0} (x_{0}),

and the policy $π^{*} = (μ_{0}^{*}, \dots, μ_{N - 1}^{*})$ is optimal: $J_{π^{*}} (x_{0}) = J_{0} (x_{0})$ .

Proof. For an admissible policy $π = (μ_{0}, \dots, μ_{N - 1})$ define its tail cost-to-go from stage $k$ ,

J_{π, k} (x) = E [g_{N} (x_{N}) + r = k \sum N - 1 g_{r} (x_{r}, μ_{r} (x_{r}), w_{r}) x_{k} = x],

so $J_{π, N} = g_{N}$ and $J_{π, 0} = J_{π}$ . Conditioning on the stage- $k$ disturbance and using that, given $x_{k} = x$ and $u_{k} = μ_{k} (x)$ , the future evolves as the chain started from $x_{k + 1} = f_{k} (x, μ_{k} (x), w_{k})$ under $(μ_{k + 1}, \dots)$ — the controlled-Markov property 37.05.01 — the tower property of conditional expectation 37.01.01 gives the one-step identity

J_{π, k} (x) = E_{w_{k}} [g_{k} (x, μ_{k} (x), w_{k}) + J_{π, k + 1} (f_{k} (x, μ_{k} (x), w_{k}))] .

Lower bound: $J_{π, k} \geq J_{k}$ for every admissible $π$ and all $k$ , by downward induction on $k$ . At $k = N$ , $J_{π, N} = g_{N} = J_{N}$ . Assume $J_{π, k + 1} \geq J_{k + 1}$ pointwise. Then for any $x$ , monotonicity of expectation in the integrand gives

J_{π, k} (x) = E_{w_{k}} [g_{k} (x, μ_{k} (x), w_{k}) + J_{π, k + 1} (\cdot)] \geq E_{w_{k}} [g_{k} (x, μ_{k} (x), w_{k}) + J_{k + 1} (\cdot)] \geq u \in U_{k} (x) in f E_{w_{k}} [g_{k} (x, u, w_{k}) + J_{k + 1} (f_{k} (x, u, w_{k}))] = J_{k} (x),

the last inequality because $μ_{k} (x) \in U_{k} (x)$ is one admissible choice in the infimum. This closes the induction, so in particular $J_{π} (x_{0}) = J_{π, 0} (x_{0}) \geq J_{0} (x_{0})$ for every $π$ , whence $J^{*} (x_{0}) = in f_{π} J_{π} (x_{0}) \geq J_{0} (x_{0})$ .

Attainment: for the greedy policy $π^{*}$ , $J_{π^{*}, k} = J_{k}$ for all $k$ , again by downward induction. At $k = N$ both equal $g_{N}$ . If $J_{π^{*}, k + 1} = J_{k + 1}$ , then by the one-step identity with $μ_{k} = μ_{k}^{*}$ ,

J_{π^{*}, k} (x) = E_{w_{k}} [g_{k} (x, μ_{k}^{*} (x), w_{k}) + J_{k + 1} (f_{k} (x, μ_{k}^{*} (x), w_{k}))] = J_{k} (x),

the second equality because $μ_{k}^{*} (x)$ attains the infimum defining $J_{k} (x)$ . Hence $J_{π^{*}} (x_{0}) = J_{π^{*}, 0} (x_{0}) = J_{0} (x_{0})$ . Combining, $J_{0} (x_{0}) = J_{π^{*}} (x_{0}) \geq J^{*} (x_{0}) \geq J_{0} (x_{0})$ , so all three coincide and $π^{*}$ is optimal. $□$

Bridge. This theorem is the foundational reason finite-horizon control is computationally tractable: the lower-bound induction is exactly the principle of optimality made quantitative — any tail of any policy costs at least the cost-to-go $J_{k}$ , so a best plan's tail must itself be best — and the attainment induction shows the backward recursion not only bounds but realizes the optimum. The central insight is that the policy-infimum and the staged expectation can be interchanged stage by stage, which is what collapses one optimization over $\prod_{k} ∣ U_{k} ∣^{∣ S_{k} ∣}$ policies into $N$ separate per-state minimizations. This builds toward the infinite-horizon theory 44.08.02, where the same Bellman operator is iterated to a fixed point rather than run for $N$ stages, and it appears again in the Markov decision process formulation 44.08.03, where $J_{k}$ becomes the finite-horizon value function and $μ_{k}^{*}$ a greedy policy with respect to it. The deterministic case is dual to a shortest-path computation on a layered graph, and putting these together, the DP algorithm is the discrete-time, stochastic generalization of the Hamilton–Jacobi backward sweep — the bridge from the Pontryagin co-state of 44.07.01 to the value-function gradient.

Exercises Intermediate+

Exercise 3 (medium, numeric).

A machine is either working ( $W$ ) or broken ( $B$ ) over $2$ stages. Each stage you choose to run (cost $0$ ) or service (cost $3$ ). If working and you run, it stays $W$ with probability $0.8$ , else goes to $B$ . If working and you service, it stays $W$ with probability $1$ . If broken, only servicing is allowed (cost $3$ ) and it becomes $W$ next stage with probability $1$ . A broken machine at the end incurs terminal cost $g_{2} (B) = 10$ , and $g_{2} (W) = 0$ . Starting in $W$ , compute $J_{1} (W)$ and decide whether to run or service at stage $1$ .

Hint

$J_{2} (W) = 0$ , $J_{2} (B) = 10$ . For "run" at stage $1$ from $W$ : expected next cost $0.8 J_{2} (W) + 0.2 J_{2} (B)$ . For "service": $3 + J_{2} (W)$ . Take the min.

Answer

$J_{1} (W) = 2$ , run. Running from $W$ : immediate $0$ , plus $0.8 \cdot 0 + 0.2 \cdot 10 = 2$ , total $2$ . Servicing from $W$ : immediate $3$ , plus $1 \cdot 0 = 0$ , total $3$ . The minimum is $min {2, 3} = 2$ , attained by run, so $J_{1} (W) = 2$ with optimal action "run". The expected breakdown penalty $2$ is cheaper than paying $3$ to prevent it on the last stage. Full credit for $J_{1} (W) = 2$ and the "run" choice.

Exercise 4 (medium, symbolic).

Prove the one-step tail identity used in the optimality proof: for any admissible policy $π$ and any stage $k < N$ ,

J_{π, k} (x) = E_{w_{k}} [g_{k} (x, μ_{k} (x), w_{k}) + J_{π, k + 1} (f_{k} (x, μ_{k} (x), w_{k}))] .

Hint

Split the sum defining $J_{π, k}$ into the stage- $k$ term and the rest, condition on $w_{k}$ , and use the controlled-Markov property so that the conditional law of the future given $x_{k} = x$ , $u_{k} = μ_{k} (x)$ , $w_{k}$ is that of the chain started at $f_{k} (x, μ_{k} (x), w_{k})$ .

Answer

Write $J_{π, k} (x) = E [g_{k} (x, μ_{k} (x), w_{k}) + R ∣ x_{k} = x]$ where $R = g_{N} (x_{N}) + \sum_{r = k + 1}^{N - 1} g_{r} (x_{r}, μ_{r} (x_{r}), w_{r})$ is the cost from stage $k + 1$ on. By the tower property 37.01.01, condition first on $(x_{k} = x, w_{k})$ , which determines $x_{k + 1} = f_{k} (x, μ_{k} (x), w_{k}) =: y$ . Given $x_{k + 1} = y$ , the controlled-Markov property 37.05.01 makes the conditional law of $(x_{k + 1}, x_{k + 2}, \dots)$ under $π$ equal to the law of the chain started at $y$ under $(μ_{k + 1}, \dots)$ , which is independent of how $y$ was reached; hence $E [R ∣ x_{k} = x, w_{k}] = J_{π, k + 1} (y) = J_{π, k + 1} (f_{k} (x, μ_{k} (x), w_{k}))$ . The stage- $k$ cost $g_{k} (x, μ_{k} (x), w_{k})$ is measurable with respect to $w_{k}$ , so taking the outer expectation over $w_{k} \sim P_{k} (\cdot ∣ x, μ_{k} (x))$ yields the claimed identity. Full credit for the conditioning split, the controlled-Markov reduction of the tail, and the outer expectation over $w_{k}$ .

Exercise 5 (medium, numeric).

Solve a deterministic shortest path on a layered graph. Nodes by stage: ${s}$ , ${a, b}$ , ${c, d}$ , ${e}$ . Arc costs: $s \to a = 1$ , $s \to b = 4$ ; $a \to c = 2$ , $a \to d = 7$ ; $b \to c = 1$ , $b \to d = 2$ ; $c \to e = 3$ , $d \to e = 1$ . Terminal cost $0$ at $e$ . Find the optimal cost $J (s)$ and the optimal path by backward induction.

Hint

$J (e) = 0$ . $J (c) = 3$ , $J (d) = 1$ . Then $J (a) = min {2 + J (c), 7 + J (d)}$ , $J (b) = min {1 + J (c), 2 + J (d)}$ , then $J (s)$ .

Answer

$J (s) = 6$ , path $s \to a \to c \to e$ . Backward: $J (e) = 0$ ; $J (c) = 3 + 0 = 3$ , $J (d) = 1 + 0 = 1$ . Then $J (a) = min {2 + 3, 7 + 1} = min {5, 8} = 5$ (via $c$ ); $J (b) = min {1 + 3, 2 + 1} = min {4, 3} = 3$ (via $d$ ). Finally $J (s) = min {1 + J (a), 4 + J (b)} = min {1 + 5, 4 + 3} = min {6, 7} = 6$ , the minimizing first arc being $s \to a$ . Following the recorded minimizers forward, the optimal path is $s \to a \to c \to e$ with total $1 + 2 + 3 = 6$ . Full credit for $J (s) = 6$ and the path $s \to a \to c \to e$ obtained from the backward labels.

Exercise 6 (hard, symbolic).

Show that allowing history-dependent policies $u_{k} = γ_{k} (x_{0}, u_{0}, \dots, x_{k})$ does not lower the optimal cost below $J_{0} (x_{0})$ in the perfect-state-information basic problem; that is, the optimal Markov cost $J_{0}$ is also optimal over the larger class of history-dependent policies.

Hint

Repeat the lower-bound induction. The key point is that the cost-to-go bound $J_{γ, k} \geq J_{k}$ uses only that $γ_{k}$ picks some admissible control in $U_{k} (x_{k})$ , and that the future law given the present state does not depend on the history.

Answer

Fix a history-dependent admissible policy $γ$ . Define its tail cost-to-go conditioned on the full history $h_{k} = (x_{0}, u_{0}, \dots, x_{k})$ ending in $x_{k} = x$ : $J_{γ} (h_{k}) = E [g_{N} (x_{N}) + \sum_{r = k}^{N - 1} g_{r} (x_{r}, u_{r}, w_{r}) ∣ h_{k}]$ . Claim $J_{γ} (h_{k}) \geq J_{k} (x_{k})$ for every history $h_{k}$ , by downward induction on $k$ . At $k = N$ , $J_{γ} (h_{N}) = g_{N} (x_{N}) = J_{N} (x_{N})$ . Assume the bound at $k + 1$ . The control $u_{k} = γ_{k} (h_{k})$ lies in $U_{k} (x_{k})$ . By the controlled-Markov property 37.05.01, the conditional law of $w_{k}$ given $h_{k}$ depends only on $(x_{k}, u_{k})$ , and given $(h_{k}, w_{k})$ the next history is $h_{k + 1} = (h_{k}, u_{k}, x_{k + 1})$ with $x_{k + 1} = f_{k} (x_{k}, u_{k}, w_{k})$ . Conditioning, $J_{γ} (h_{k}) = E_{w_{k}} [g_{k} (x_{k}, u_{k}, w_{k}) + J_{γ} (h_{k + 1})] \geq E_{w_{k}} [g_{k} (x_{k}, u_{k}, w_{k}) + J_{k + 1} (x_{k + 1})] \geq in f_{u \in U_{k} (x_{k})} E_{w_{k}} [g_{k} (x_{k}, u, w_{k}) + J_{k + 1} (f_{k} (x_{k}, u, w_{k}))] = J_{k} (x_{k})$ , using the induction hypothesis and that $u_{k}$ is one admissible choice. At $k = 0$ the history is $h_{0} = (x_{0})$ , giving $J_{γ} (x_{0}) \geq J_{0} (x_{0})$ . Since the greedy Markov policy attains $J_{0} (x_{0})$ , no history-dependent policy beats it: the perfect-information optimum is achieved within Markov policies. Full credit for the history-indexed induction and the observation that only membership $u_{k} \in U_{k} (x_{k})$ and the Markov future law are used.

Exercise 7 (hard, symbolic).

A scalar linear-quadratic problem: $x_{k + 1} = a x_{k} + b u_{k}$ (deterministic), stage cost $g_{k} (x, u) = q x^{2} + r u^{2}$ with $q \geq 0$ , $r > 0$ , terminal cost $g_{N} (x) = q_{N} x^{2}$ . Show by backward induction that $J_{k} (x) = K_{k} x^{2}$ for scalars $K_{k} \geq 0$ , and derive the Riccati recursion for $K_{k}$ and the optimal control $μ_{k}^{*} (x) = - L_{k} x$ .

Hint

Guess $J_{k + 1} (x) = K_{k + 1} x^{2}$ and minimize $q x^{2} + r u^{2} + K_{k + 1} (a x + b u)^{2}$ over $u$ by setting the derivative to zero; the minimized value is again a multiple of $x^{2}$ .

Answer

Base case $J_{N} (x) = q_{N} x^{2}$ , so $K_{N} = q_{N} \geq 0$ . Inductive step: assume $J_{k + 1} (x) = K_{k + 1} x^{2}$ with $K_{k + 1} \geq 0$ . Then

J_{k} (x) = u min [q x^{2} + r u^{2} + K_{k + 1} (a x + b u)^{2}] .

The bracket is quadratic and strictly convex in $u$ (coefficient $r + K_{k + 1} b^{2} > 0$ ). Setting the $u$ -derivative to zero: $2 r u + 2 K_{k + 1} b (a x + b u) = 0$ , so $u^{*} = - \frac{ab K _{k + 1}}{r + b ^{2} K _{k + 1}} x =: - L_{k} x$ with $L_{k} = \frac{ab K _{k + 1}}{r + b ^{2} K _{k + 1}}$ . Substituting $u^{*}$ and simplifying,

J_{k} (x) = [q + \frac{a ^{2} r K _{k + 1}}{r + b ^{2} K _{k + 1}}] x^{2} =: K_{k} x^{2}, K_{k} = q + \frac{a ^{2} r K _{k + 1}}{r + b ^{2} K _{k + 1}},

the (scalar, discrete) Riccati recursion, run backward from $K_{N} = q_{N}$ . Each $K_{k} \geq 0$ since $q \geq 0$ and the added fraction is nonnegative, closing the induction. The optimal policy is the linear state feedback $μ_{k}^{*} (x) = - L_{k} x$ . Full credit for the quadratic ansatz preserved by the recursion, the Riccati update for $K_{k}$ , and the gain $L_{k}$ .

Advanced results Master

The finite-horizon theory extends in four directions: the exact equivalence between deterministic DP and shortest paths, the reverse reduction that lets shortest-path algorithms inherit the DP optimality proof, the state-augmentation construction that restores the Markov structure when it is broken by delays or correlation, and the measurable-selection refinement that secures attainment of the per-stage minima beyond the finite case.

Theorem 1 (deterministic DP equals shortest path). A deterministic finite-state finite-horizon problem with stages $k = 0, \dots, N$ , state sets $S_{k}$ , transition costs $g_{k} (x, u)$ for moves $x \to f_{k} (x, u)$ , and terminal cost $g_{N}$ is equivalent to a shortest-path problem on the layered directed graph with node set $⨆_{k} S_{k}$ , an arc $x \to f_{k} (x, u)$ of weight $g_{k} (x, u)$ for each admissible $u$ , and an artificial terminal node reached from each $x \in S_{N}$ at cost $g_{N} (x)$ . The DP cost-to-go $J_{k} (x)$ equals the shortest-path distance from node $(x, k)$ to the terminal node, and the DP backward recursion is precisely backward dynamic-programming on this acyclic graph; conversely any shortest-path problem on an acyclic graph with a topological layering is a deterministic DP. The acyclicity of the layered graph is what makes the single backward sweep exact, in contrast with the iterative relaxation needed on graphs with cycles ^{[Bertsekas Vol. 1 §1.3]}.

Theorem 2 (forward–backward symmetry and the reverse DP). For a deterministic problem the cost-to-go admits a forward dual: define the cost-to-arrive $A_{k} (x)$ as the least cost to reach state $x$ at stage $k$ from $x_{0}$ , by the forward recursion $A_{0} (x_{0}) = 0$ , $A_{k + 1} (y) = min_{(x, u) : f_{k} (x, u) = y} {A_{k} (x) + g_{k} (x, u)}$ . Then for every $k$ and reachable $x$ , $A_{k} (x) + J_{k} (x)$ is constant along any optimal trajectory and equals $J^{*} (x_{0})$ , and $min_{x} {A_{k} (x) + J_{k} (x)} = J^{*} (x_{0})$ at every stage. This forward/backward decomposition is the discrete shadow of the Hamilton–Jacobi value-function symmetry and underlies bidirectional shortest-path search and the label-correcting reinterpretation of the DP sweep ^{[Bertsekas Vol. 1 §2.3]}.

Theorem 3 (state augmentation for delays and correlated disturbances). Suppose the dynamics involve a one-step control delay, $x_{k + 1} = f_{k} (x_{k}, u_{k - 1}, w_{k})$ , or the disturbances are correlated through an exogenous driving chain $ξ_{k + 1} = h_{k} (ξ_{k}, η_{k})$ with $w_{k} = c_{k} (ξ_{k})$ . Define the augmented state $\tilde{x}_{k} = (x_{k}, u_{k - 1})$ in the first case, $\tilde{x}_{k} = (x_{k}, ξ_{k})$ in the second. The augmented system $\tilde{x}_{k + 1} = \tilde{f}_{k} (\tilde{x}_{k}, u_{k}, \tilde{w}_{k})$ is controlled-Markov 37.05.01, its disturbance law depending only on $(\tilde{x}_{k}, u_{k})$ , and the DP algorithm applied to $\tilde{x}_{k}$ returns the optimal cost and policy of the original problem. The reformulation has the same optimal value; its cost is a larger state space, the generic price of restoring memorylessness ^{[Bertsekas Vol. 1 §1.4]}.

Theorem 4 (existence and measurable selection of an optimal policy). When state and control spaces are uncountable, the per-stage infimum $J_{k} (x) = in f_{u \in U_{k} (x)} Q_{k} (x, u)$ , with $Q_{k} (x, u) = E_{w} [g_{k} (x, u, w) + J_{k + 1} (f_{k} (x, u, w))]$ , need not be attained, and even when attained the minimizer need not depend measurably on $x$ . Under standard regularity — $S_{k}, C_{k}$ Borel spaces, $U_{k}$ a measurable set-valued map with compact values, $Q_{k}$ lower semicontinuous in $u$ and measurable in $x$ , and the recursion preserving measurability and lower boundedness of $J_{k + 1}$ — the Kuratowski–Ryll-Nardzewski measurable-selection theorem yields a measurable minimizer $μ_{k}^{*} (x)$ , so $J_{k}$ is measurable and an optimal deterministic Markov policy exists. For finite or countable $U_{k} (x)$ the selection is automatic and the optimality theorem holds verbatim ^{[Puterman Ch. 4]}.

Synthesis. The foundational reason finite-horizon control reduces to arithmetic is that one stochastic optimization over all policies factors, by the principle of optimality, into $N$ per-state minimizations linked only through the cost-to-go $J_{k}$ . The central insight is the interchange of the policy-infimum with the staged expectation: the lower-bound induction shows every policy tail costs at least $J_{k}$ , and the greedy attainment induction shows the backward recursion realizes that bound, so $J^{*} = J_{0}$ is a theorem, not a definition. This is dual to the forward cost-to-arrive recursion, the two meeting at $A_{k} + J_{k} = J^{*}$ exactly as the Hamilton–Jacobi value meets its characteristics, and it generalises the Pontryagin backward co-state sweep 44.07.01. State augmentation makes the framework universal — whatever breaks the Markov structure, delays or correlation, is absorbed into a larger state so the same recursion applies — and putting these together with the measurable-selection refinement gives an optimal Markov policy in full generality. The deterministic case is the bridge to combinatorial optimization, where the DP sweep is shortest path on an acyclic graph; the stochastic case builds toward the infinite-horizon fixed-point theory 44.08.02 and the Markov decision process 44.08.03, where the finite stage index gives way to iteration of one Bellman operator to its fixed point. The same algebraic move — collapsing an integral over all futures into a one-step optimization against a stored summary — appears again across value-function-based control and reinforcement learning.

Full proof set Master

Proposition 1 (one-step tail identity). For any admissible Markov policy $π = (μ_{0}, \dots, μ_{N - 1})$ and $0 \leq k < N$ , $J_{π, k} (x) = E_{w_{k}} [g_{k} (x, μ_{k} (x), w_{k}) + J_{π, k + 1} (f_{k} (x, μ_{k} (x), w_{k}))]$ , where $J_{π, k}$ is the tail cost-to-go from stage $k$ .

Proof. Split the cost in $J_{π, k} (x) = E [g_{N} (x_{N}) + \sum_{r = k}^{N - 1} g_{r} (x_{r}, μ_{r} (x_{r}), w_{r}) ∣ x_{k} = x]$ into the $r = k$ term and the remainder $R$ . Condition on $w_{k}$ via the tower property 37.01.01; this fixes $x_{k + 1} = f_{k} (x, μ_{k} (x), w_{k}) =: y$ . By the controlled-Markov property 37.05.01 the conditional law of the post- $(k + 1)$ trajectory given $x_{k} = x, w_{k}$ equals that of the chain started at $y$ under $(μ_{k + 1}, \dots)$ , so $E [R ∣ x_{k} = x, w_{k}] = J_{π, k + 1} (y)$ . Taking the outer expectation over $w_{k} \sim P_{k} (\cdot ∣ x, μ_{k} (x))$ and adding the $E_{w_{k}} [g_{k} (x, μ_{k} (x), w_{k})]$ term gives the identity. $□$

Proposition 2 (lower bound: $J_{π, k} \geq J_{k}$ ). For every admissible $π$ and every $k$ , $J_{π, k} (x) \geq J_{k} (x)$ for all $x$ .

Proof. Downward induction on $k$ . At $k = N$ , $J_{π, N} = g_{N} = J_{N}$ . Assume $J_{π, k + 1} \geq J_{k + 1}$ pointwise. By Proposition 1 and monotonicity of expectation, $J_{π, k} (x) = E_{w_{k}} [g_{k} (x, μ_{k} (x), w_{k}) + J_{π, k + 1} (\cdot)] \geq E_{w_{k}} [g_{k} (x, μ_{k} (x), w_{k}) + J_{k + 1} (\cdot)] \geq in f_{u \in U_{k} (x)} E_{w_{k}} [g_{k} (x, u, w_{k}) + J_{k + 1} (f_{k} (x, u, w_{k}))] = J_{k} (x)$ , since $μ_{k} (x) \in U_{k} (x)$ is one feasible choice in the infimum. $□$

Proposition 3 (attainment: greedy policy realizes $J_{k}$ ). Assume each infimum defining $J_{k} (x)$ is attained by $μ_{k}^{*} (x) \in U_{k} (x)$ . Then for the greedy policy $π^{*} = (μ_{0}^{*}, \dots, μ_{N - 1}^{*})$ , $J_{π^{*}, k} = J_{k}$ for all $k$ ; in particular $J_{π^{*}} (x_{0}) = J_{0} (x_{0})$ .

Proof. Downward induction. At $k = N$ , $J_{π^{*}, N} = g_{N} = J_{N}$ . Assume $J_{π^{*}, k + 1} = J_{k + 1}$ . By Proposition 1 with $μ_{k} = μ_{k}^{*}$ , $J_{π^{*}, k} (x) = E_{w_{k}} [g_{k} (x, μ_{k}^{*} (x), w_{k}) + J_{k + 1} (f_{k} (x, μ_{k}^{*} (x), w_{k}))]$ , which equals $J_{k} (x)$ because $μ_{k}^{*} (x)$ attains the defining infimum. Hence $J_{π^{*}, 0} = J_{0}$ , i.e. $J_{π^{*}} (x_{0}) = J_{0} (x_{0})$ . $□$

Proposition 4 (optimality of the DP algorithm). Under the attainment hypothesis, $J^{*} (x_{0}) = J_{0} (x_{0})$ and $π^{*}$ is optimal.

Proof. Proposition 2 at $k = 0$ gives $J_{π} (x_{0}) = J_{π, 0} (x_{0}) \geq J_{0} (x_{0})$ for every admissible $π$ , so $J^{*} (x_{0}) = in f_{π} J_{π} (x_{0}) \geq J_{0} (x_{0})$ . Proposition 3 gives an admissible $π^{*}$ with $J_{π^{*}} (x_{0}) = J_{0} (x_{0})$ , so $J^{*} (x_{0}) \leq J_{0} (x_{0})$ . The two inequalities force $J^{*} (x_{0}) = J_{0} (x_{0}) = J_{π^{*}} (x_{0})$ , so $π^{*}$ is optimal. $□$

Proposition 5 (cost-to-arrive/cost-to-go decomposition). In the deterministic case, with $A_{k}$ the cost-to-arrive and $J_{k}$ the cost-to-go, $min_{x \in S_{k}} {A_{k} (x) + J_{k} (x)} = J^{*} (x_{0})$ for every $0 \leq k \leq N$ , and the minimizing $x$ are exactly the states lying on some optimal trajectory at stage $k$ .

Proof. For any state $x$ reachable at stage $k$ , $A_{k} (x)$ is the least cost of a prefix $x_{0} ⇝ x$ and $J_{k} (x)$ the least cost of a suffix $x ⇝$ terminal; concatenating a least prefix and a least suffix through $x$ gives a full trajectory of cost $A_{k} (x) + J_{k} (x) \geq J^{*} (x_{0})$ , so the minimum over $x$ is $\geq J^{*} (x_{0})$ . Conversely an optimal full trajectory passes through some state $x^{†}$ at stage $k$ ; its prefix and suffix costs are $\geq A_{k} (x^{†})$ and $\geq J_{k} (x^{†})$ respectively, while their sum is $J^{*} (x_{0})$ , forcing prefix $= A_{k} (x^{†})$ , suffix $= J_{k} (x^{†})$ , and $A_{k} (x^{†}) + J_{k} (x^{†}) = J^{*} (x_{0})$ . Hence the minimum is attained and equals $J^{*} (x_{0})$ , with minimizers the on-optimal-path states. $□$

Connections Master

The infinite-horizon discounted theory 44.08.02 replaces the finite backward recursion with iteration of the single Bellman operator $(T J) (x) = in f_{u} E [g (x, u, w) + α J (f (x, u, w))]$ to its fixed point. The finite-horizon $J_{k}$ computed here are exactly the iterates $T^{N - k} J_{N}$ of that operator, so the present unit is the truncated, non-stationary precursor whose limit (as the horizon grows and a discount stabilizes it) is the stationary value function; the contraction that makes the infinite-horizon fixed point unique is the asymptotic version of the finite-stage monotonicity used in the optimality proof here.
The Markov decision process formulation 44.08.03 is this unit's stochastic problem with the controlled-Markov disturbance 37.05.01 made the primitive: states, actions, transition kernels, and stage rewards, with the finite-horizon value functions $J_{k}$ and greedy policies $μ_{k}^{*}$ becoming the MDP optimality equations and optimal decision rules. The optimality theorem proved here is the finite-horizon MDP optimality theorem; policy evaluation and the backward induction are the same recursion read in reward-maximization rather than cost-minimization form.
The Pontryagin maximum principle 44.07.01 is the continuous-time, calculus-of-variations counterpart: where DP computes a global value function $J_{k} (x)$ over the whole state space by backward recursion, Pontryagin computes a co-state (adjoint) trajectory along a single candidate optimum by a backward differential equation. The co-state is the gradient of the value function, $p_{k} = \nabla_{x} J_{k} (x_{k}^{*})$ , so the discrete DP backward sweep and the Pontryagin backward adjoint are two readings of the same Hamilton–Jacobi backward flow, DP giving the field of values and Pontryagin its directional derivative along the optimal path.
The controlled-Markov disturbance model rests on the Markov property and transition matrices 37.05.01: under a fixed policy the closed-loop system is an ordinary time-inhomogeneous Markov chain, the disturbance law $P_{k} (\cdot ∣ x, u)$ composing with the feedback $μ_{k}$ into a stochastic transition kernel. The tower property of conditional expectation on the underlying probability space 37.01.01 is what licenses the one-step tail identity that drives the entire optimality proof.

Historical & philosophical context Master

Dynamic programming was created by Richard Bellman at the RAND Corporation in the early 1950s, consolidated in the 1957 monograph Dynamic Programming ^{[Bellman 1957]}. Bellman's principle of optimality — that an optimal policy has the property that, whatever the initial state and first decision, the remaining decisions form an optimal policy for the resulting state — recast a multistage optimization as a functional equation in the value function, the recursion this unit calls the DP algorithm. Bellman's recollection that he chose the name "dynamic programming" partly to be politically palatable to a research-averse Secretary of Defense is a frequently retold piece of the method's origin; the mathematical substance is the functional-equation technique and the identification of the curse of dimensionality, the exponential growth of the state space that limits exact DP.

The stochastic, measure-theoretic formulation of the finite-horizon problem under perfect state information, with the controlled system $x_{k + 1} = f_{k} (x_{k}, u_{k}, w_{k})$ , additive cost, and the optimality proof by backward induction, is the modern treatment systematized by Dimitri Bertsekas in Dynamic Programming and Optimal Control ^{[Bertsekas Vol. 1 Ch. 1]}, whose Volume 1 Chapter 1 is the anchor for this unit. The measurable-selection difficulties in the uncountable case, and the conditions guaranteeing an optimal measurable Markov policy, were treated rigorously in the Markov-decision-process literature, with Martin Puterman's 1994 monograph ^{[Puterman Ch. 4]} giving the standard finite-horizon optimality-equation account. The deterministic reduction to shortest paths connects the method to the contemporaneous algorithmic work of Bellman, Ford, and Dijkstra on network optimization.

Bibliography Master

@book{bertsekas2017dp,
  author    = {Bertsekas, Dimitri P.},
  title     = {Dynamic Programming and Optimal Control, Volume 1},
  edition   = {4},
  publisher = {Athena Scientific},
  year      = {2017}
}

@book{bellman1957dp,
  author    = {Bellman, Richard},
  title     = {Dynamic Programming},
  publisher = {Princeton University Press},
  year      = {1957}
}

@book{puterman1994mdp,
  author    = {Puterman, Martin L.},
  title     = {Markov Decision Processes: Discrete Stochastic Dynamic Programming},
  publisher = {John Wiley \& Sons},
  year      = {1994}
}

@article{bellman1954theory,
  author  = {Bellman, Richard},
  title   = {The theory of dynamic programming},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {60},
  number  = {6},
  year    = {1954},
  pages   = {503--515}
}

@book{bertsekas2012dpvol2,
  author    = {Bertsekas, Dimitri P.},
  title     = {Dynamic Programming and Optimal Control, Volume 2: Approximate Dynamic Programming},
  edition   = {4},
  publisher = {Athena Scientific},
  year      = {2012}
}

Prerequisites

37.01.01
37.05.01

Tier anchors

beginner: Bertsekas 2017 Dynamic Programming and Optimal Control 4e (Athena Scientific) Vol. 1 §1.1-1.3 (the basic problem, the spreading of a decision over stages, and the shortest-path-through-a-grid picture of working backward from the goal)
intermediate: Bertsekas 2017 Dynamic Programming and Optimal Control 4e (Athena Scientific) Vol. 1 §1.3-1.4 (the principle of optimality and the DP algorithm: backward recursion for the cost-to-go functions $J_{k}$ and the optimality proof); Bellman 1957 Dynamic Programming (Princeton) Ch. III
master: Bertsekas 2017 Dynamic Programming and Optimal Control 4e (Athena Scientific) Vol. 1 Ch. 1 (the full finite-horizon theory: perfect-state-information basic problem, the DP algorithm and its optimality proof, the deterministic shortest-path reduction, and state augmentation for delays and correlated disturbances); Puterman 1994 Markov Decision Processes (Wiley) Ch. 4 (finite-horizon MDPs and the optimality equations)

References

Bertsekas, D. P. — Dynamic Programming and Optimal Control, Vol. 1 · Athena Scientific, 4th edition (2017). Chapter 1 sets up the basic problem of finite-horizon sequential decision-making under perfect state information: a discrete-time controlled dynamical system $x_{k + 1} = f_{k} (x_{k}, u_{k}, w_{k})$ with state $x_{k}$ , control $u_{k} \in U_{k} (x_{k})$ , and random disturbance $w_{k}$ distributed according to $P_{k} (\cdot ∣ x_{k}, u_{k})$ , and an additive cost $g_{N} (x_{N}) + \sum_{k = 0}^{N - 1} g_{k} (x_{k}, u_{k}, w_{k})$ to be minimized in expectation over admissible policies $π = (μ_{0}, \dots, μ_{N - 1})$ with $u_{k} = μ_{k} (x_{k})$ . §1.3 states Bellman's principle of optimality and derives the DP algorithm: $J_{N} (x_{N}) = g_{N} (x_{N})$ and, by backward recursion, $J_{k} (x_{k}) = min_{u_{k} \in U_{k} (x_{k})} E_{w_{k}} {g_{k} (x_{k}, u_{k}, w_{k}) + J_{k + 1} (f_{k} (x_{k}, u_{k}, w_{k}))}$ , with the optimal cost $J^{*} (x_{0}) = J_{0} (x_{0})$ and an optimal policy read off from the minimizing controls. §1.3 proves that the policy so constructed is optimal. §1.4 treats the deterministic finite-state case as a shortest-path problem and the converse, and the state-augmentation device for time delays and correlated disturbances.
Bellman, R. — Dynamic Programming · Princeton University Press (1957). The founding monograph; Chapter III articulates the principle of optimality ('An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision') and the functional-equation technique for multistage decision processes.
Puterman, M. L. — Markov Decision Processes: Discrete Stochastic Dynamic Programming · Wiley (1994). Chapter 4 develops the finite-horizon Markov decision process: the optimality equations, the backward-induction algorithm, existence of an optimal deterministic Markov policy, and the measurable-selection conditions under which the minimum in the optimality equation is attained.

Estimated time

beginner: 20m
intermediate: 55m
master: 90m