Automated State Abstraction for Options using the U-Tree Algorithm

Part of Advances in Neural Information Processing Systems 13 (NIPS 2000)

Bibtex Metadata Paper


Anders Jonsson, Andrew Barto


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.