DIMACS TR: 97-47
Encyclopaedia of Complexity Results for Finite-Horizon Markov Decision Process Problems
Authors: Martin Mundhenk,
Judy Goldsmith,
Christopher Lusena and
Eric Allender
ABSTRACT
The computational complexity of finite horizon
policy evaluation and policy existence problems
are studied for several policy types and representations
of Markov decision processes. In almost all cases, the
problems are shown to be complete for their complexity classes;
classes range from nondeterministic logarithmic space and
probabilistic logarithmic space (highly parallelizable classes) to
exponential space. In many cases, this work shows that problems
that already were widely believed to be hard to compute are
probably intractable (complete for NP, NP^PP , or PSPACE),
or provably intractable (EXPTIME-complete or worse).
The major contributions of the paper are to pinpoint the complexity
of these problems; to isolate the factors that make these problems
computationally complex; to show that even problems such as
median-policy or average-policy evaluation may be intractable; and the
introduction of natural NP^PP-complete problems.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-47.ps.gz
DIMACS Home Page