Linear programming for decision processes with partial information

Markov Decision Processes are stochastic optimization problems that model situations where a decision maker controls a system based on its state. Partially observed Markov decision processes (POMDPs) are generalizations of Markov Decision Processes where the decision maker has only partial information on the state of the system. Such problems naturally model a wide range of applications such as predictive maintenance. Finding an optimal policy for a POMDP is PSPACE-hard and practically challenging. We introduce a mixed integer linear programming version for POMDPs where decisions are taken based only on the current observation, as well as valid inequalities that are based on a probabilistic interpretation of the dependence between variables. The linear relaxation provides a good bound for the usual POMDPs where the policies depend on the full history of observations and actions. POMDPs suffer from the curse of dimensionality, and systems composed of multiple components evolving independently but linked by a common action, which are relevant in the context of predictive maintenance, are typically intractable. We introduce decomposable POMDPs and a heuristic to solve them to be able to deal with such system. Numerical experiments show the efficiency of our approach.