OPTIMAL SEARCH STRATEGIES IN DYNAMIC HYPOTHESIS-TESTING

In this paper, we formulate and solve a class of dynamic search problems for obtaining the closed-loop sequence of measurements which, under a symmetry condition on the probability distribution of the measurements, optimally selects among many candidate hypotheses. Under this condition, the optimal strategy is characterized by a simple index rule which depends only on the ordering of the conditional probabilities of the hyotheses given the past measurements, We prove that this index rule is optimal independent of the number of measurements to be taken, We illustrate with numerical examples that, when the symmetry conditions are relaxed, the index policies are suboptimal, but achieve performance which is close to optimal. The results can be applied to solve complex problems in fault diagnosis and search with unreliable tests.