Sequential item selection: Optimal and heuristic policies

This paper considers testing in which the goal is to minimize the number of test items required to establish a learner's state of ability. Focus is on optimal or near optimal selection over a well-defined universe of items or stimuli. Selection policies are determined for the case in which the items have hierarchical or partial hierarchical relationships. Derivation of an optimal policy rests upon techniques from dynamic programming. For situations in which an optimal policy may be too costly to compute, two heuristic approximations are offered. One heuristic counts the hypothetical estimates of ability that remain tenable following a response to each item and chooses the item that minimizes the expectation of that number. The other selects the item that maximizes the statistic of information.