A hybrid genetic/optimization algorithm for finite-horizon, partially observed Markov decision processes

The partially observed Markov decision process (POMDP) is a generalization of a Markov decision process that allows for noise-corrupted and costly observations of the underlying system state. The value function of the finite horizon POMDP is known to be piecewise affine and convex in the probability mass vector over the state space. Such a function can be represented by a finite set of affine functions. In this paper, we develop and evaluate an exact algorithm, GAMIP, which combines a genetic algorithm and a mixed integer program to construct the minimal set of affine functions that describes the value function. Numerical results indicate that GAMIP takes up to 60% less time to construct the minimal set than does the most efficient linear programming-based exact solution method in the literature.