Let $\{ (x_{t},u_{t}) \}$ be a controlled Markov chain. Consider the Finite Horizon Optimization problem: $$J_{N}(X,\gamma)=E_{x}^{\gamma}\left[ \sum_{k=0}^{N-1}c(X_{k},U_{k})+c_{N}(X_{N}) \right]$$where we seek to minimize the cost over all admissible policies. Any such policy can be replaced with one which is Markov and which is at least as good as the original policy. i.e. there is no loss in restricting policies to be Markov.