Dynamic Programming is Optimal for Certain Sequential Decision Processes

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 pro-gramming 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. 1. A loop-free monotone sequential decision process, considered in [I], can be defined as an acyclic directed graph, G = (V, E), where each edge e has an associated nondecreasing function h,: R--f R. It will be convenient to assume that G has only a single vertex (denoted s) with no entering edges, and only a single vertex (denoted t) with no edges leaving. Parallel edges with different functions may exist between the same pair of vertices. The functions h, can be extended to give path costs by the rule: 0 if P is the path containing no edges ‘Ost(‘) = /h,(cost(P’)) if P consists of P ’ followed by e ’ This is a generalization of the usual shortest path problem, in which cost(P) = cost(P’) + length(e). The above definition is equivalent to the definition in [I], and the minimum-cost path problem is to find a minimum cost path from s to t. (This is identical to the optimal policy problem of [I]). Th p e ro bl em can be solved by an algorithm essentially the same as the familiar algorithm for solving ordinary shortest path problems on acyclic graphs [2, Section 61. (For brevity, the algorithm will not be presented here.