Dynamic programming is optimal for certain sequential decision processes

Abstract

A lower bound on the work to find a minimum-cost path in a monotone loop-free sequential decision process is proved. We show that dynamic programming always performs the smallest possible number of function evaluations. This is no more than the number required simply to prove that the chosen path is of minimum cost.