Automated State Abstraction for Options using the U-Tree Algorithm

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 accomplish theoverall task. In this paper, we study hierarchical learning using the framework of options. We argue that to take full advantage of hierarchical structure,one should perform option-specific state abstraction, and that if this is to scale to larger tasks, state abstraction should be automated. Weadapt McCallum's U-Tree algorithm to automatically build option-specific representations of the state feature space, and we illustrate theresulting 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.