Searching for multiple targets with measurement dependent noise

We consider a search problem in which multiple targets are uniformly placed on the unit interval. An agent, who might not know the number of targets in advance, is interested in acquiring all targets to within some resolution δ as quickly as possible. To that end, at each time unit, the agent can probe any region of the unit interval for the presence of targets but the associated measurement noise increases with the size of the probed region. We characterize the maximal targeting rate, the optimal tradeoff between resolution and expected search time, with adaptive and non-adaptive search strategies, highlighting the advantage of adaptive strategies. We show that even when the number of targets is known, in contrast to the case of constant measurement noise, there is a multiplicative gap between the performance of adaptive and non-adaptive search. This gap, however, diminishes as the number of targets grow.