Optimal sequential file search: A reduced-state dynamic programming approach

This paper continues the study of a file search problem in 1994 by Monahan. The objective is to determine whether or not a record is in a sequential file whose contents are initially unknown. Costly information regarding the contents of positions within the file can be purchased. The problem of determining an optimal search and disposition strategy is formulated as a Markov decision process whose state space is polynomial in the number of possible records in the file. As a result, the computational effort required to determine transition probabilities and expected payoffs is also polynomial.