Proceedings of the Annual Meeting of the Cognitive Science Society

The importance of hierarchically structured representations fortractable planning has long been acknowledged. However, thequestions of how people discover such abstractions and how todefine a set of optimal abstractions remain open. This problemhas been explored in cognitive science in the problem solvingliterature and in computer science in hierarchical reinforce-ment learning. Here, we emphasize an algorithmic perspec-tive on learning hierarchical representations in which the ob-jective is to efficiently encode the structure of the problem, or,equivalently, to learn an algorithm with minimal length. Weintroduce a novel problem-solving paradigm that links prob-lem solving and program induction under the Markov Deci-sion Process (MDP) framework. Using this task, we target thequestion of whether humans discover hierarchical solutions bymaximizing efficiency in number of actions they generate or byminimizing the complexity of the resulting representation andfind evidence for the primacy of representational efficiency.