We present a framework for learning to plan hierarchically in domains with unknown dynamics. We enhance planning performance by exploiting problem structure in several ways: First, we simplify the search over plans by leveraging knowledge of skill objectives; second, shorter plans are generated by enforcing aggressively hierarchical planning; and third, we learn transition dynamics with sparse local models for better generalization. Our framework decomposes transition dynamics into skill effects and success conditions, which allows fast planning by reasoning on effects, while learning conditions from interactions with the world. We propose a simple method for learning new abstract skills, using successful trajectories stemming from completing the goals of a curriculum. Learned skills are then refined to leverage other abstract skills and enhance subsequent planning. We show that both conditions and abstract skills can be learned simultaneously while planning, even in stochastic domains. Our method is validated in experiments of increasing complexity, with up to @math states, showing superior planning to classic non-hierarchical planners or reinforcement learning methods. Applicability to real-world problems is demonstrated in a simulation-to-real transfer experiment on a robotic manipulator.
Abstract Markov decision processes (MDPs) have proven to be popular models for decision-theoretic planning, but standard dynamic programming algorithms for solving MDPs rely on explicit, state-based specifications and computations. To alleviate the combinatorial problems associated with such methods, we propose new representational and computational techniques for MDPs that exploit certain types of problem structure. We use dynamic Bayesian networks (with decision trees representing the local families of conditional probability distributions) to represent stochastic actions in an MDP, together with a decision-tree representation of rewards. Based on this representation, we develop versions of standard dynamic programming algorithms that directly manipulate decision-tree representations of policies and value functions. This generally obviates the need for state-by-state computation, aggregating states at the leaves of these trees and requiring computations only for each aggregate state. The key to these algorithms is a decision-theoretic generalization of classic regression analysis, in which we determine the features relevant to predicting expected value. We demonstrate the method empirically on several planning problems, showing significant savings for certain types of domains. We also identify certain classes of problems for which this technique fails to perform well and suggest extensions and related ideas that may prove useful in such circumstances. We also briefly describe an approximation scheme based on this approach. Reinforcement learning has developed into a primary approach for learning control strategies for autonomous agents. However, most of the work has focused on the algorithmic aspect, i.e. various ways of computing value functions and policies. Usually the representational aspects were limited to the use of attribute-value or propositional languages to describe states, actions etc. A recent direction - under the general name of relational reinforcement learning - is concerned with upgrading the representation of reinforcement learning methods to the first-order case, being able to speak, reason and learn about objects and relations between objects. This survey aims at presenting an introduction to this new field, starting from the classical reinforcement learning framework. We will describe the main motivations and challenges, and give a comprehensive survey of methods that have been proposed in the literature. The aim is to give a complete survey of the available literature, of the underlying motivations and of the implications if the new methods for learning in large, relational and probabilistic environments.