Dynamic programming can only be applied to problems with optimal substructure.

The Markov property (e.g. in Markov Decision Processes, MDPs) means that the distribution of one state $x_{k+1}$ only depends on the state directly before ($x_k$, and the action $a_k$), not on more steps before. (commonly expressed as $P(X_{k+1} = x_{k+1} | X_k = x_k, X_{k-1} = x_{k-1}, \dots, X_0 = x_0) = P(X_{k+1} = x_{k+1}| X_k = x_k )$)

What is the relationship between optimal substructure and the Markov property? Does every MDP have optimal substructure? What are examples of stochastic problems which have optimal substructure but do not have the Markov property? Or is there no such relationship?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.