Algorithm selection by rational metareasoning as a model of human strategy selection
Selecting the right algorithm is an important problem in computer science, because the algorithm often has to exploit the structure of the input to be efficient. The human mind faces the same challenge. Therefore, solutions to the algorithm selection problem can inspire models of human strategy selection and vice versa. Here, we view the algorithm selection problem as a special case of metareasoning and derive a solution that outperforms existing methods in sorting algorithm selection. We apply our theory to model how people choose between cognitive strategies and test its prediction in a behavioral experiment. We find that people quickly learn to adaptively choose between cognitive strategies. People's choices in our experiment are consistent with our model but inconsistent with previous theories of human strategy selection. Rational metareasoning appears to be a promising framework for reverse-engineering how people choose among cognitive strategies and translating the results into better solutions to the algorithm selection problem.
This paper is refreshing in its scope and ambition; I've reviewed and read many NIPS papers that are just one tiny idea explored in excruciating detail. However, despite the paper's considerable breadth and the effort placed into evaluation, I feel this paper may walk the line too far to the side of broad and shallow, versus narrow and deep. I lay out specific concerns below that limit the impact of the results presented.The area of algorithm selection / metareasoning is key in both AI and cog sci. I am surprised that more work hasn't been done in this important area. (I don't know the literature, but I am trusting the authors' review which mostly consists of decade-old work. They do fail to cite work in cognitivearchitectures like SOAR and ACT-R which probably doesn't have a lot tooffer in terms of how people learn metastrategies.)I am confused by the authors' decision to focus on the domain of sortingalgorthms because this domain doesn't lend itself well to the rationalmetareasoning (RM) model. RM attempts to optimize a combined measure ofalgorithm accuracy and algorithm time/opportunity cost. However, for sortingalgorithms, don't all algorithms achieve perfect accuracy? And as a result,isn't the modeling of scoring (Equations 3, 8, 9, and 10) irrelevant?I also wonder whether there is much benefit of a Bayesian linear regressionapproach over simple ridge regression, given that only parameter means arebeing utilized (Equation 12)?  That said, the representation selected seemsvery sensible (using the two features, their logs, and 2nd order polynomialterms involving these features and their logs).The work claims to contribute both to state-of-the-art AI approaches toalgorithm selection and to the psychological theory of metareasoning. I havequestions about its contributions to each, which I'll address separately.With regard to AI, the authors compare their results to two existing models.The Lagoudakis method doesn't appear to utilize presortedness. As a result,it seems more like a straw man than a serious contender. With regard tothe comparison to Guo, I had some concern that (based on the text on line 160)a different measure of presortedness was being used by Guo, but the authorsassure me in their rebuttal that they use the same representation as Guo.With regard to the work's contribution to cognitive science:  In human strategyselection, the trade off between accuracy and opportunity cost is key, and theopportunity cost involved is not only the run time of an algorithm, but thecost of selecting an algorithm, as reflected in Simon's notion of satisficing.Thus, I question selection of sorting algorithms as the most suitable domainfor studying human strategy selection.  Although the experimental set upin Section 5 is elaborate and impressive, the coarse performance statistics(proportion of merge sort selection and overall quality of selection)hardly make a compelling argument that the RM model is correct.  All weknow from the experiment is that both the RM model and people are pretty good at selecting strategies, whereas the other models are not. This result gives us little insight as to whether the RM model is a good cognitive model.I couldn't find much detail about training the models used in Section 5, but ifthese are really meant to be cognitive models they should be trained on thesame data that people had available during practice, and the same total numberof trials.  The author rebuttal assures me that the training data is identical.MINOR COMMENTS:[093]: A Gaussian distribution may be acceptable for sorting algorithm runtimes, but it's probably not the best choice for modeling human responsetimes.  On a range of tasks from simple button presses to memory retrieval tocomplex problem solving, reaction times tend to have a long-tailed asymmetricdistribution.[091]: The standard deviation does not appear to be a polynomial in theextended features (Equation 7)[168]: The table caption should explain the performance measure. I believeit is the percentage of runs in which the optimal sorting algorithm wasselected.[295]: The text says that Equations 13 and 14 suggest the conditionsunder which merge sort will be chosen over cocktail sort. However, thecoefficients on n_comparisons and n_moves in Equation 13 are both smallerthan the corresponding coefficients in Equation 14, so it seems to methat cocktail sort should be chosen for all but the very shortest lists.