Approximate Equivalence of Markov Decision Processes
Lists
Only you see this
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.
BibTeX
@inproceedings{evendar2003approximate,
author = {Eyal Even-Dar and Yishay Mansour},
title = {{Approximate Equivalence of Markov Decision Processes}},
booktitle = {Conference on Learning Theory},
year = {2003},
url = {https://openreview.net/forum?id=pE0VPdildNy},
}Loading related content...