mathematics//decision theory//Markov decision process//Bellman equation

The Bellman equation is the recursive condition that the optimal value of every state must satisfy in a sequential decision problem: what it is worth to be here equals the best reward available now plus the discounted, expected value of wherever that action leaves you. It is the equation that dynamic programming, reinforcement learning, LQR and MPC all solve in different ways, and it is how a sequence of decisions is turned into one decision at a time. For a Markov decision process,

The Bellman equation is the recursive condition that the optimal value of every state must satisfy in a sequential decision problem: what it is worth to be here equals the best reward available now plus the discounted, expected value of wherever that action leaves you. It is the equation that dynamic programming, reinforcement learning, LQR and MPC all solve in different ways, and it is how a sequence of decisions is turned into one decision at a time. For a Markov decision process,

V∗(s)=max⁡a[ R(s,a)+γ∑s′P(s′∣s,a) V∗(s′) ].V^{*}(s) = \max_{a}\Big[\, R(s,a) + \gamma \sum_{s'} P(s'\mid s,a)\, V^{*}(s') \,\Big].V∗(s)=amax​[R(s,a)+γs′∑​P(s′∣s,a)V∗(s′)].

Inside the bracket, R(s,a)R(s,a)R(s,a) is what the action pays now and the sum is the value of the next state averaged over where the action may land, discounted by γ\gammaγ. The optimal policy needs no separate search: in each state it takes the action that reaches the maximum.

It rests on the principle of optimality. Whatever the first step of an optimal path, the rest of the path must be optimal from wherever that step lands; otherwise swapping in the better remainder would improve the whole. A delivery drone's best route from the depot to the last customer, cut at its second stop, is also the best route from that stop. So the problem of planning a whole sequence becomes a relation between the values of neighbouring states, which can be solved by sweeping it (value iteration, dynamic programming) or by learning it from samples (Q-learning, whose temporal-difference error is the gap between the two sides).

Control and decision are the same equation in different clothes.

With linear dynamics and quadratic cost the value is a quadratic form, and Bellman becomes the Riccati equation of LQR; MPC solves the same problem over a finite horizon, online, at every step; value iteration solves it on a grid of states.

The equation is exact; solving it is the problem. Each sweep costs about states times actions times successors, so it is tractable for hundreds or thousands of states and hopeless for a 10-variable robot (curse of dimensionality). Everything practical (a quadratic form in LQR, a finite horizon in MPC, a neural network in deep RL) is a way of not representing the value everywhere.

It assumes the state is seen. When it is not, the same equation holds over beliefs instead of states (POMDP), and becomes far harder.