Concurrent discovery of task hierarchies

Task hierarchies can be used to decompose an intractable problem into smaller more manageable tasks. This paper ex-plores how task hierarchies can model a domain for control purposes, and examines an existing algorithm (HEXQ) that automatically discovers a task hierarchy through interaction with the environment. The initial performance of the algo-rithm can be limited because it must adequately explore each level of the hierarchy before starting construction of the next, and it cannot adapt to a dynamic environment. The contribu-tion of this paper is to present an algorithm that avoids any protracted period of initial exploration by discovering multi-ple levels of the hierarchy simultaneously. This can signi-cantly improve initial performance as the agent takes advan-tage of all hierarchical levels early on in its development. Ro-bustness is also improved because undiscovered features and environment changes can be incorporated later into the hierar-chy. Empirical results show the new algorithm to signicantly outperform HEXQ