Optimal Policies for a Class of Search and Evaluation Problems

A person searches through a population of possible actions, looking for one with high value. He discovers these actions one after another, paying a certain cost each time. On his first encounter with a possible action, the person obtains some preliminary information about its actual value, and at this point he can take the action, he can continue looking, or, at a certain cost, he can perform a test and obtain some more information about its actual value. If he decides to test, then having obtained the additional information he can again either take the action or continue looking. The problem is to conduct this process in such a manner as to maximize expected net value, that is, the expected value of the action finally taken minus the expected total cost of searching and testing. This problem is analyzed and optimal policies are given in the case where the possible actions are regarded as independent selections from a large population. The joint distribution in this population of the actual value, the preliminary information, and the additional information gained from testing, is assumed to be known. The situation where many possibilities are to be selected, subject to a budget constraint on total search and testing cost, is also treated. For this problem asymptotically optimal results are given for large budgets.