Towards a theory of heuristic and optimal planning for sequential information search


How should tests (or queries, questions, or experiments) be selected? Does it matter if only a single test is allowed, or if a sequential test strategy can be planned in advance? This article contributes two sets of theoretical results bearing on these questions. First, for selecting a single test, several Optimal Experimental Design (OED) ideas have been proposed in statistics and other disciplines. The OED models are mathematically nontrivial. How is it that they often predict human behavior well? One possibility is that simple heuristics can approximate or exactly implement OED models. We prove that heuristics can identify the highest information value queries (as quantified by OED models) in several situations, thus providing a possible algorithmic-level theory of human behavior. Second, we address whether OED models are optimal for sequential search, as is frequently presumed. We consider the Person Game, a 20-questions scenario, as well as a two-category, binary feature scenario, both of which have been widely used in psychological research. In each task, we demonstrate via specific examples and extended computational simulations that neither the OED models nor the heuristics considered in the literature are optimal. Little research addresses human behavior in such situations. We call for experimental research into how people approach the sequential planning of tests, and theoretical research on what sequential planning procedures are most successful, and we offer a number of testable predictions for discriminating among candidate models.