We study the nonhomogeneous Markov decision process with an objective of developing theory and both optimal and heuristic algorithms capable of solving moderately sized problems. Our approach is to identify forecast horizons by exploiting problem structure. Truncating the problem at a specific horizon, we can search a set of potential salvage values to determine if we have a forecast horizon. The approach developed combines genetic algorithms to do a quick search, and a mixed integer program to verify optimality. This approach is generalized to any model of sequential decision-making for which a successive approximation step is closed with respect to the set of all piecewise affine and convex functions. Such models include many parametrized Markov decision processes (e.g., the multi-objective Markov decision process and the partially observed Markov decision process).
展开▼
