Bellman Equation

For a discrete-time linear system, with dynamics in the form $$x_{k+1}=f(x_k,u_k,k),$$ let us assume we are trying to minimize the total cost $$J(x_0,u_{0:N-1},0)=\Phi (x_N)+\sum _{i=0}^{N-1}l(x_i,u_i,i).$$ of a trajectory $(x_{0:N},u_{0:N-1})$ where the initial state $x_0$ is prescribed. The concept of the total cost can be generalized for any $k\in ⟨0,N⟩$ to a cost-to-go $$J(x_k,u_{k:N-1},k)=\Phi (x_N)+\sum _{i=k}^{N-1}l(x_i,u_i,i),$$ for which we may define a value function $$V(x_k,k)=\underset{u_{k:N-1}}{\min }J(x_k,u_{k:N-1},k),$$ and an optimal control policy $$u_{k:N-1}^{\ast }=\underset{u_{k:N-1}}{\mathrm{argmin}}J(x_k,u_{k:N-1},k),$$ the application of which results in the system following the optimal sequence of states $x_{k+1:N}^{\ast }$.

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$. From its definition, it is apparent that $$V(x_k,k)=l(x_k,u_k^{\ast },k)+V(x_{k+1}^{\ast },k+1),x_{k+1}^{\ast }=f(x_k,u_k^{\ast },k),\text{\hspace{1em}(1)}$$ where $$V(x_N,N)=\Phi (x_N).$$ Assuming we don't know what the optimal input at step $k$ is, we may pose the right-hand side of (1) as an optimization problem $$V(x_k,k)=\underset{u_k}{\min }\left(l(x_k,u_k,k)+V(f(x_k,u_k,k),k+1)\right).\text{\hspace{1em}(2)}$$ Equation (2) is then referred to as the Bellman equation.