Approximate Policy Iteration with a Policy Language Bias: Solving Relational Markov Decision Processes
Open Access
- 29 January 2006
- journal article
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 25, 75-118
Abstract
We study an approach to policy selection for large relational Markov Decision Processes (MDPs). We consider a variant of approximate policy iteration (API) that replaces the usual value-function learning step with a learning step in policy space. This is advantageous in domains where good policies are easier to represent and learn than the corresponding value functions, which is often the case for the relational MDPs we are interested in. In order to apply API to such problems, we introduce a relational policy language and corresponding learner. In addition, we introduce a new bootstrapping routine for goal-based planning domains, based on random walks. Such bootstrapping is necessary for many large relational MDPs, where reward is extremely sparse, as API is ineffective in such domains when initialized with an uninformed policy. Our experiments show that the resulting system is able to find good policies for a number of classical planning domains and their stochastic variants by solving them as extremely large relational MDPs. The experiments also point to some limitations of our approach, suggesting future work.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Equivalence notions and model minimization in Markov decision processesArtificial Intelligence, 2003
- Congestion control via online sampling2002
- A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision ProcessesMachine Learning, 2002
- Using genetic programming to learn and improve control knowledgeArtificial Intelligence, 2002
- Stochastic dynamic programming with factored representationsArtificial Intelligence, 2000
- Using temporal logics to express search control knowledge for planningArtificial Intelligence, 2000
- Learning action strategies for planning domainsArtificial Intelligence, 1999
- Integrating planning and learning: the PRODIGY architectureJournal of Experimental & Theoretical Artificial Intelligence, 1995
- Taxonomic syntax for first order inferenceJournal of the ACM, 1993
- Explanation-based learning:A problem solving perspectiveArtificial Intelligence, 1989