Approximate Equivalence of Markov Decision Processes
Abstract
We consider the problem of finding the minimal ε -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 ε -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.
Cite
Text
Even-Dar and Mansour. "Approximate Equivalence of Markov Decision Processes." Annual Conference on Computational Learning Theory, 2003. doi:10.1007/978-3-540-45167-9_42Markdown
[Even-Dar and Mansour. "Approximate Equivalence of Markov Decision Processes." Annual Conference on Computational Learning Theory, 2003.](https://mlanthology.org/colt/2003/evendar2003colt-approximate/) doi:10.1007/978-3-540-45167-9_42BibTeX
@inproceedings{evendar2003colt-approximate,
title = {{Approximate Equivalence of Markov Decision Processes}},
author = {Even-Dar, Eyal and Mansour, Yishay},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2003},
pages = {581-594},
doi = {10.1007/978-3-540-45167-9_42},
url = {https://mlanthology.org/colt/2003/evendar2003colt-approximate/}
}