Piecewise linear approximations for partially observable Markov decision processes with finite horizons

This paper considers a finite horizon Markov decision process in which the state at any time is only known in terms of its probability vector at that time, which changes as additional information is required. The value function is known to be a piecewise linear function of the vector components. The paper considers procedures for finding an approximating set of linear forms, using linear programming and contraction and expansion heuristics.