Automated State Abstraction for Options Using the U-Tree Algorithm

Abstract

Learning a complex task can be significantly facilitated by defining a hierarchy of subtasks. An agent can learn to choose between various temporally abstract actions, each solving an assigned subtask, to accom(cid:173) plish the overall task. In this paper, we study hierarchical learning using the framework of options. We argue that to take full advantage of hier(cid:173) archical structure, one should perform option-specific state abstraction, and that if this is to scale to larger tasks, state abstraction should be au(cid:173) tomated. We adapt McCallum's U-Tree algorithm to automatically build option-specific representations of the state feature space, and we illus(cid:173) trate the resulting algorithm using a simple hierarchical task. Results suggest that automated option-specific state abstraction is an attractive approach to making hierarchical learning systems more effective.