Optimal sequential allocation problem with imperfect feedback information

Abstract

A given number of bullets can be fired in an attempt to destroy a fixed number of targets. The probability of successfully destroying a target at each shot is known. The bullets will be fired in sequence and, after each shot is fired, there is a report on the state for the target just fired at. The reports are subject to the usual two types of errors: falsely claiming an intact target as destroyed and falsely claiming destroyed target as intact. The probabilities of these two types of errors are also known. The goal is to destroy as many targets as possible. This paper shows that the myopic decision strategy that picks the next target to be the one with the highest intact posterior probability is the optimal strategy. This strategy is also optimal if the criterion is to maximize the probability of destroying all targets, or a weighted sum of the destroyed targets when the targets are weighted by their importance. (This is joint work with CTC Mo, S Wu and MCK Yang.)