Bellman Equation

Let us assume we are trying to minimize the total cost $$J({\mathbf{x}}_0,\{{\mathbf{u}}_i{\}}_{i=0}^{N-1},0)=\Phi ({\mathbf{x}}_N)+\sum _{i=0}^{N-1}l({\mathbf{x}}_i,{\mathbf{u}}_i,i).$$ of a discrete-time system's trajectory $\{{\mathbf{x}}_i{\}}_{i=0}^N$ with dynamics in the form $$x_{k+1}=\mathbf{f}({\mathbf{x}}_k,{\mathbf{u}}_k,k),$$ starting from the state ${\mathbf{x}}_0={\tilde{\mathbf{x}}}_0$.

The concept of the total cost can be generalized for any $k\in ⟨0,N⟩$ to a cost-to-go $$J({\mathbf{x}}_k,\{{\mathbf{u}}_i{\}}_{i=k}^{N-1},k)=\Phi ({\mathbf{x}}_N)+\sum _{i=k}^{N-1}l({\mathbf{x}}_i,{\mathbf{u}}_i,i),$$ for which we may define a value function $$V({\mathbf{x}}_k,k)=\underset{\{{\mathbf{u}}_i{\}}_{i=k}^{N-1}}{\min }J({\mathbf{x}}_k,\{{\mathbf{u}}_i{\}}_{i=k}^{N-1},k),$$ and an optimal control policy $$\{{\mathbf{u}}_i^{\ast }{\}}_{i=k}^{N-1}=\underset{\{{\mathbf{u}}_i{\}}_{i=k}^{N-1}}{\mathrm{argmin}}J({\mathbf{x}}_k,\{{\mathbf{u}}_i{\}}_{i=k}^{N-1},k),$$ the application of which results in the system following an optimal trajectory $\{{\mathbf{x}}_i^{\ast }{\}}_{i=k}^N$.

The so-called Bellman equation can then be derived by formulating the value function for step $k$ recursively (using the value function for step $k+1$) as $$V({\mathbf{x}}_k,k)=\underset{{\mathbf{u}}_k}{\min }\left(l({\mathbf{x}}_k,{\mathbf{u}}_k,k)+V({\mathbf{x}}_{k+1},k+1)\right)$$ and substituting ${\mathbf{x}}_{k+1}$ using the system's dynamics to attain the final form $$V({\mathbf{x}}_k,k)=\underset{{\mathbf{u}}_k}{\min }\left(l({\mathbf{x}}_k,{\mathbf{u}}_k,k)+V(\mathbf{f}({\mathbf{x}}_k,{\mathbf{u}}_k,k),k+1)\right).$$