TY - JOUR AU - Ruan, Sherry AU - Comanici, Gheorghe AU - Panangaden, Prakash AU - Precup, Doina PY - 2015/03/04 Y2 - 2024/03/28 TI - Representation Discovery for MDPs Using Bisimulation Metrics JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 29 IS - 1 SE - Student Abstract Track DO - 10.1609/aaai.v29i1.9747 UR - https://ojs.aaai.org/index.php/AAAI/article/view/9747 SP - AB - <p> We provide a novel, flexible, iterative refinement algorithm to automatically construct an approximate statespace representation for Markov Decision Processes (MDPs). Our approach leverages bisimulation metrics, which have been used in prior work to generate features to represent the state space of MDPs.We address a drawback of this approach, which is the expensive computation of the bisimulation metrics. We propose an algorithm to generate an iteratively improving sequence of state space partitions. Partial metric computations guide the representation search and provide much lower space and computational complexity, while maintaining strong convergence properties. We provide theoretical results guaranteeing convergence as well as experimental illustrations of the accuracy and savings (in time and memory usage) of the new algorithm, compared to traditional bisimulation metric computation. </p> ER -