Implementation and Comparison of Solution Methods for Decision Processes
  with Non-Markovian Rewards
  This paper examines a number of solution methods for decision processes with
non-Markovian rewards (NMRDPs). They all exploit a temporal logic specification
of the reward function to automatically translate the NMRDP into an equivalent
Markov decision process (MDP) amenable to well-known MDP solution methods. They
differ however in the representation of the target MDP and the class of MDP
solution methods to which they are suited. As a result, they adopt different
temporal logics and different translations. Unfortunately, no implementation of
these methods nor experimental let alone comparative results have ever been
reported. This paper is the first step towards filling this gap. We describe an
integrated system for solving NMRDPs which implements these methods and several
variants under a common interface; we use it to compare the various approaches
and identify the problem features favoring one over the other.
