Approximate Equivalence of Markov Decision Processes
We consider the problem of finding the minimal e-equivalent MDP for an MDP given in its tabular form. We show that the problem is NP-Hard and then give a bicriteria approximation algorithm to the problem. We suggest that the right measure for finding minimal e-equivalent model is L 1 rather than L ∞ by giving both an example, which demonstrates the drawback of using L ∞ , and performance guarantees for using L 1. In addition, we give a polynomial algorithm that decides whether two MDPs are equivalent.