mathematics//optimization//dynamic programming

Dynamic programming is a method for solving sequential decision problems by computing the value of every state once, working backwards over stages or iterating to a fixed point with the Bellman equation, and reusing those values instead of enumerating whole sequences of decisions; it is how optimal maintenance policies, inventory rules, shortest paths and LQR gains are computed when a model of the system is available. It rests on the principle of optimality: whatever the first decision, the rest of an optimal plan must be optimal from wherever that decision lands.

Dynamic programming is a method for solving sequential decision problems by computing the value of every state once, working backwards over stages or iterating to a fixed point with the Bellman equation, and reusing those values instead of enumerating whole sequences of decisions; it is how optimal maintenance policies, inventory rules, shortest paths and LQR gains are computed when a model of the system is available. It rests on the principle of optimality: whatever the first decision, the rest of an optimal plan must be optimal from wherever that decision lands.

The saving is the whole point. With AAA actions and NNN stages there are ANA^NAN sequences to compare, but with SSS states the stage-by-stage computation costs about N⋅S⋅AN\cdot S\cdot AN⋅S⋅A evaluations of the next state's value. A machine with five wear levels, decided shift by shift (keep producing, which pays less as wear grows and risks breaking, or repair, which costs and restores it), is solved in a few lines: iterating the Bellman equation finds the policy repair at level 3, before it breaks, the book's link between decision and predictive maintenance.

With a model, dynamic programming wins: it solves the same equation reinforcement learning approximates, with the transitions known, no exploration and no millions of episodes. Its limit is the size of the state space, which Bellman himself named the curse of dimensionality: ten variables of a hundred values each make 102010^{20}1020 states.

It comes in a few shapes. A finite horizon is solved backwards from the last stage (backward induction); an infinite discounted horizon by value iteration or by policy iteration, which alternates evaluating a policy and improving it; and the continuous linear-quadratic case collapses to the Riccati equation of the LQR, whose value is a quadratic form.

Classic algorithms are dynamic programming in disguise. Dijkstra's algorithm computes the cost-to-come of every node in order, and the Viterbi decoder of a hidden Markov model runs the same recursion forward over time to find the likeliest sequence of hidden states.

When the state space is too large, three routes remain: approximate the value function with a network (RL and approximate dynamic programming), solve only from the current state over a short horizon at every step (MPC), or simplify the model until the table fits.