We address decidability of several infinite horizon partially
observable Markov Decision Process (POMDP) model problems in this
work.

The undecidability of the emptiness problem for probabilistic finite
automata was established by Azaria Paz and later by Condon and Lipton.
In this paper, we briefly describe the latter work and show how their
reduction establishes the undecidability of the seemingly unambitious
problems of satisficing (success with a satisfactory probability) and
approximability for undiscounted POMDPs.  Connections with
probabilistic planning are also made.

We next move on to the discounted infinite horizon model.
Computability of approximations falls readily out of the problem
definition, but the decidability of satisficing remains an interesting
open problem.  Here, we investigate the structural properties of the
problem in some detail, and give an example and explain why an
intuitive property for unobservable MDPs, that optimal policies are
periodic, can fail for a 3 state model, and explain how this provides
some insight into the hardness of the problem.  This investigation
leads to several open problems with which we conclude.