11.1 The principle of optimality
A multistage decision problem has stages \(k = 1, \ldots , N\). At stage \(k\) the system is in a state \(s_k\); a decision \(x_k\) chosen from a set \(D_k(s_k)\) earns a return \(r_k(s_k, x_k)\) and moves the system to the state \(s_{k + 1} = T_k(s_k, x_k)\). The aim is to maximise the total return from a given \(s_1\).
Theorem 11.1.1 (Bellman’s principle of optimality). Define \(f_{N + 1}(s) = 0\) and, for \(k = N, N - 1, \ldots , 1\), \[ f_k(s) = \max _{x \in D_k(s)}\bigl \{r_k(s, x) + f_{k + 1}\bigl (T_k(s, x)\bigr )\bigr \} . \] Then \(f_k(s)\) is the largest total return obtainable from stage \(k\) onwards starting in state \(s\); in particular \(f_1(s_1)\) is the optimal value, and choosing at each stage a maximising decision gives an optimal policy.
Proof. By backward induction on \(k\). For \(k = N + 1\) there is nothing left to decide. Suppose the claim holds for \(k + 1\). Any sequence of decisions from stage \(k\) in state \(s\) starts with some \(x\), earning \(r_k(s, x)\), and continues from \(T_k(s, x)\), where by the hypothesis it earns at most \(f_{k + 1}(T_k(s, x))\), with equality for an optimal continuation. So the best total is the maximum over \(x\) of their sum, which is \(f_k(s)\). □
The value function \(f_k\) summarises the future: once it is known, the decision at stage \(k\) depends only on the current state, not on how the state was reached. The work is proportional to the number of stages times the number of states times the number of decisions per state, so dynamic programming is efficient when the state is small. When the state is a vector, the number of states grows exponentially with its dimension, Bellman’s curse of dimensionality, which limits exact dynamic programming to problems with a few state variables. The shortest-path recursion \(d_j = \min _i(d_i + c_{ij})\) of the section on networks is the same principle with nodes as states.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.