Approximate Policy Iteration with a Policy Language Bias: Solving Relational Markov Decision Processes

By Alan Fern, Robert Givan, Sung Wook Yoon. 2011

72 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Fitted Q-Learning for Relational Domains (2020, methodology): “We adopt the RMDP deﬁnition of Fern et al. (Fern, Yoon, and Givan 2006), where S and A of the original MDPs are represented by a set of objects O , a set of predicates P and set of action types Y .”
Analysis of Classification-based Policy Iteration Algorithms (2016, background): “Fern et al. (2006) and Dimitrakakis and Lagoudakis (2008a) provide a preliminary theoretical analysis of their algorithm.”
Training Deep Reactive Policies for Probabilistic Planning Problems (2018, methodology): “This idea of leveraging Q-values for supervised policy learning has been shown to be effective in prior work, e.g. (Fern, Yoon, and Givan 2006).”
Solving Relational and First-Order Logical Markov Decision Processes: A Survey (2012, methodology): “Related to guidance is the usage of behavioral cloning based on human generated traces, for example by (Morales, 2004) and Cocora et al (2006), the use of optimal plans by Yoon et al (2002), or the random walk approach by Fern et al (2006), which uses a guided exploration of domain instantiations.”
Learning Features and Abstract Actions for Computing Generalized Plans (2018, methodology): “…the work is different than action model learning (Yang, Wu, and Jiang 2007) and model-based reinforcement learning and closer in aims to work on learning general policies from examples or experience (Mart´ın and Geffner 2004; Fern, Yoon, and Givan 2006; Sukhbaatar et al. 2015; Zhang et al. 2018).”
First Order Decision Diagrams for Relational MDPs (2007, background): “Fern, Yoon, and Givan (2006) and Gretton and Thiebaux (2004) use inductive learning methods to learn a value map or policy from solutions or simulations of small instances.”
Approximate Dynamic Programming Finally Performs Well in the Game of Tetris (2013, unknown): “Fortunately a class of such ADP algorithms, called classification-based policy iteration (CbPI), have been recently developed and analyzed [12, 7, 13, 9, 17].”