  The importance of hierarchically structured representations for tractable
planning has long been acknowledged. However, the questions of how people
discover such abstractions and how to define a set of optimal abstractions
remain open. This problem has been explored in cognitive science in the problem
solving literature and in computer science in hierarchical reinforcement
learning. Here, we emphasize an algorithmic perspective on learning
hierarchical representations in which the objective is to efficiently encode
the structure of the problem, or, equivalently, to learn an algorithm with
minimal length. We introduce a novel problem-solving paradigm that links
problem solving and program induction under the Markov Decision Process (MDP)
framework. Using this task, we target the question of whether humans discover
hierarchical solutions by maximizing efficiency in number of actions they
generate or by minimizing the complexity of the resulting representation and
find evidence for the primacy of representational efficiency.
