On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems

摘要: We investigate the computability of problems in probabilistic planning and partially observable infinite-horizon Markov decision processes. The undecidability string-existence problem for finite automata is adapted to show that following plan existence undecidable: given a problem, determine whether there exists with success probability exceeding desirable threshold. Analogous policy-existence processes under discounted undiscounted total reward models, average-reward state-avoidance models are all shown be undecidable. results apply corresponding approximation as well.