Associative dynamic programs

In this paper we consider finite-stage stochastic dynamic programs with associative reward systems. An invariant imbedding technique yields a dynamic program with a terminal reward system on an augmented state space. According to the associativity, we clarify the validity of three possible recursive equations-one parametrized equation and two non-parametrized ones. Each of the additive, multiplicative, and multiplicative-additive dynamic programs admits the three recursive equations. Further, the corresponding composite relations among three optimum value functions hold. However, minimum, maximum, and fractional dynamic programs admit only the parametrized recursive equation. They do not admit the two non-parametrized equations. Further, the corresponding relations among the three optimum value functions do not hold. (C) 1996 Academic Press, Inc.