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.

The explosion of data generated during human interactions on- line presents an opportunity for cognitive scientists to evaluate their models on popular real-world tasks outside the confines of the laboratory. We demonstrate this approach by evaluating two cognitive models of generalization against two machine learning approaches to recommendation on an online dataset of over 100K human playlist selections. Across two experiments we demonstrate that a model from cognitive science can both be efficiently implemented at scale and can capture generaliza- tion trends in human recommendation judgments which nei- ther machine learning model is capable of replicating. We use these results to illustrate the opportunity internet-scale datasets offer to cognitive scientists, as well as to underscore the impor- tance of using insights from cognitive modeling to supplement the standard predictive-analytic approach taken by many exist- ing machine learning approaches.