2012/06/20 by Chenggang Wang, Wang, Chenggang, Roni Khardon +1
Computer Science · #Advanced Software Engineering Methodologies #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Formal Methods in Verification #Reinforcement Learning in Robotics #cs.AI
paper · pdf · doi:10.48550/arxiv.1206.5287
Appears in Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence (UAI2007)
arxiv created 2012/06/20 · openalex publication_date 2012/06/20 · arxiv updated 2012/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Relational Markov Decision Processes are a useful abstraction for complex reinforcement learning problems and stochastic planning problems. Recent work developed representation schemes and algorithms for planning in such problems using the value iteration algorithm. However, exact versions of more complex algorithms, including policy iteration, have not been developed or analyzed. The paper investigates this potential and makes several contributions. First we observe two anomalies for relational representations showing that the value of some policies is not well defined or cannot be calculated for restricted representation schemes used in the literature. On the other hand, we develop a variant of policy iteration that can get around these anomalies. The algorithm includes an aspect of policy improvement in the process of policy evaluation and thus differs from the original algorithm. We show that despite this difference the algorithm converges to the optimal policy.