Dynamic programming solves a multistage optimization problem backwards by expressing each remaining-horizon value in terms of the next-stage value.
If a successful step in action has expected reward and survival probability , a finite-horizon retirement problem with zero wealth after capture has threshold . Above it, induction makes retirement optimal; below it, a single further step already beats retirement. The threshold does not depend on the remaining positive horizon.
A Bellman equation is the recursive optimality relation for the value function of a dynamic programming problem.
For nonnegative rewards, a nonnegative value satisfying the maximizing Bellman equation dominates every competing policy, even for . Iterate the one-step inequality, discard the nonnegative terminal value, then apply the monotone convergence theorem to the accumulated reward.
The Hamilton--Jacobi--Bellman equation is the continuous-time Bellman equation. For state dynamics , running cost and terminal cost , a smooth value function satisfies
A linear-quadratic optimal-control problem has linear state dynamics and running and terminal costs defined by quadratic forms. Its value function is quadratic in the state, the optimal feedback is linear, and its coefficient obeys a Riccati equation.
A backward scalar or matrix recurrence for the quadratic coefficients in a value function for a linear-quadratic optimal control problem. It results from completing the control square in the Bellman equation. Multiplicative noise modifies the quadratic coefficients through its second moments.
A value function assigns each state and time the best objective attainable from that state over the remaining decisions.
A hidden object lies in box with posterior probability . Searching box costs and, conditional on the object being there, detects it with probability . After an unsuccessful search of box , Bayes theorem updates the probabilities to
When search continues until discovery, expected search cost is minimized by searching at each step a box maximizing . An adjacent-interchange argument compares two searches: placing before costs less exactly when .
If discovery in box earns reward and stopping earns zero, the Bellman equation isIf , every posterior state has some with , so stopping is never optimal.
Articles by others on the same topic
Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems in a recursive manner. It is particularly useful for optimization problems where the solution can be constructed from solutions to smaller instances of the same problem. The key idea behind dynamic programming is to store the results of subproblems to avoid redundant computations, a technique known as "memoization.