research36 min studyLesson 682 in Mathematics

The dynamic programming principle

Restart an optimization consistently and compute a two-stage policy with action-dependent transitions.

Before you begin

On this page

The question for today

What you’ll understand

State the dynamic programming identity with its continuation value.
Explain why conditional restart, admissible pasting, and measurable selection matter.
Compute a finite-horizon policy whose optimal action changes with remaining time.

A policy that is optimal from today must use optimal continuation decisions after the information available tomorrow is revealed. Dynamic programming turns that statement into a recursion, but it relies on being able to join admissible pieces of policies. A state-by-state list of favorable future actions is not enough if it cannot be selected measurably. A two-state, two-stage model makes the recursion exact and shows why the best first action can differ from the best last action.

Split cost at a permissible restart time

For a Markov controlled diffusion and a stopping time between the start and the fixed terminal horizon, the dynamic programming principle replaces future cost by the value at the restart state and time. The running cost before the restart remains inside the expectation. The equality uses the same control convention, filtration, state constraints, and horizon on both sides. If the problem contains path-dependent information not included in the state, the state must first be enlarged or the simple Markov formula must be replaced.

One inequality follows by conditioning the remaining cost of any admissible policy and comparing that continuation with the infimum defining the value. The reverse inequality requires joining the initial policy to nearly optimal continuation policies chosen according to the restart outcome. Exact optimizers are not needed for the value identity; epsilon-optimal controls can suffice. A rigorous proof must keep track of which information the continuation selection may use.

V(t,x)=\inf_u\mathbb E\left[\int_t^\tau\ell(s,X_s,u_s)\,ds+V(\tau,X_\tau)\right].

The restart time is a stopping time in the admissible information structure, not a time chosen with future knowledge.↔ Scroll wide equations horizontally.

Pasting and selection are genuine hypotheses

A standard finite-horizon setting uses a compact metric action set, continuous state-action data, uniformly Lipschitz state coefficients, and bounded uniformly continuous costs. On a canonical Brownian framework with shifted nonanticipating controls, admissible classes must be stable under conditioning and concatenation. These properties, together with an appropriate measurable-selection argument or a countable approximation construction, justify the dynamic programming identity. We use it in that setting rather than asserting the identity for every imaginable family of controls.

In a finite state and finite action model, measurability is automatic and a minimizing continuation can be chosen at each state by a finite comparison. The same reasoning can fail for an artificially restricted policy family that disallows switching after observed events. Partial observation also requires a sufficient information state, often a conditional distribution rather than the hidden state itself. Dynamic programming is therefore a theorem about a well-specified decision model, not only an algebraic rearrangement of an infimum and an expectation.

V_n(i)=\min_a\left\{c(i,a)+\sum_jP^a_{ij}V_{n+1}(j)\right\},\qquad V_N=g.

Finite sums and a finite minimum make the conditional restart and continuation choice explicit.↔ Scroll wide equations horizontally.

Expectation comes before the current decision is optimized

At a current state, the chosen action determines a distribution of next states. The controller minimizes the expected continuation value under that distribution; it cannot minimize separately after secretly observing an unrevealed next state. At the next decision time, however, the realized next state is known, so its own action may be selected accordingly. This order of conditioning explains both the power of feedback and the difference between dynamic programming and clairvoyant pathwise optimization.

Backward induction also distinguishes the number of remaining decisions from the physical state. A service action may be worthwhile near the terminal penalty and unnecessary earlier, when the system has another chance to correct itself. Stationary transitions do not imply a stationary finite-horizon optimal policy. Recording both action values at each step reveals whether a change comes from immediate effort cost, transition probabilities, or the shape of the continuation value.

\min_a\mathbb E[V_{n+1}(X_{n+1})\mid X_n=i,a]\ne\mathbb E[\min_a V_{n+1}(X_{n+1}^{a})\mid X_n=i]\quad\text{in general}.

The right-hand expression can give the current controller information that is not available when it must choose.↔ Scroll wide equations horizontally.

Work it through

Wait first, service near the terminal penalty

Use states calm C and hot H, with terminal costs zero and six after two decisions. Waiting costs zero and has transition probabilities $P(C\to H)=0.4$ , $P(H\to C)=0.2$ . Service costs one and has probabilities $P(C\to H)=0.1$ , $P(H\to C)=0.7$ . Find both stages of the optimal policy.

One decision before the end, waiting gives costs 2.4 in C and 4.8 in H. Service gives 1.6 in C and 2.8 in H, including its unit cost. Therefore the last-stage values are $(1.6,2.8)$ and service is optimal in either state.
At the first stage in C, waiting gives $0.6(1.6)+0.4(2.8)=2.08$ , while service gives $1+0.9(1.6)+0.1(2.8)=2.72$ . In H, waiting gives $0.2(1.6)+0.8(2.8)=2.56$ , while service gives $1+0.7(1.6)+0.3(2.8)=2.96$ .
Choose waiting at the first stage in both states, then service at the last stage in the observed state. Every decision uses current information. The resulting value is lower than either alternative first action paired with its already optimized continuation.

V_1=(1.6,2.8),\qquad V_0=(2.08,2.56).

The vectors list values in calm, hot order and already include all future service costs.↔ Scroll wide equations horizontally.

The result

The two-decision values are 2.08 from calm and 2.56 from hot. The optimal action changes from wait to service as the horizon approaches.

The living notebook

Explore the model

Interactive lab

Interactive lab · markov

Compare fixed actions before optimizing a policy

Pause and Reset, then set transition p to 0.4 and q to 0.2. Starting from state zero, predict state-one probabilities 0.4 after one Step and 0.56 after two; these describe waiting twice. For a fresh comparison, Pause and Reset, then set p to 0.1 and q to 0.7; predict 0.1 and 0.12 for service twice. Multiply the final probability by six and separately add service costs. The instrument does not switch actions or solve the Bellman recursion. Editing a control retains elapsed time, so each comparison needs Reset and both settings.

P(state 0)P(state 1)Stationary distribution

P(state 1) at step 0: 0%
Stationary P(state 1): 60%
Chain behavior: Monotone convergence

Transition p · 0 → 10.3Transition q · 1 → 00.2

t = 0 s

Exact finite-step probabilities for a two-state chain starting in state 0, not sampled trajectories. Playback advances two transitions per second. When p = q = 0 every distribution is stationary; when p = q = 1 the chain alternates forever. A single zero transition creates an absorbing state. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forTransition probabilities evaluate a fixed policy; dynamic programming additionally selects continuation actions and accounts for their costs.

Pause & reason

Check your understanding

Interactive checks need JavaScript. You can still read the explanation.

Read the checkpoint explanation

The reverse inequality constructs a nearly optimal full policy from initial and continuation pieces. Admissibility, nonanticipation, pasting, and measurable selection justify that construction; none of the other conditions supplies it.

Your turn

Try it yourself

Repeat the two-stage model when service costs 0.5 instead of one. Determine the last-stage values and both first-stage optimal actions.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

The transition probabilities stay fixed. First recompute the last-stage minimum, then use that entire value vector in each first-stage comparison.

Compare with the solution

The last-stage service values are 1.1 in C and 2.3 in H, both below waiting. At the first stage, C gives wait 1.58 versus service 1.72, so wait is best. H gives wait 2.06 versus service 1.96, so service is best. The initial value vector is therefore (1.58,1.96); reducing service cost changes the initial hot-state decision.

Keep the idea

Take it with you

Dynamic programming uses an optimized continuation value at a valid restart time.
Admissible pasting and measurable selection justify joining future decisions.
Stationary dynamics can produce a time-dependent finite-horizon policy.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.