A theory of searching for a target with partial information

Animals often need to find and navigate to distant targets, such as food, mates or prey, using partial information about their location. Search algorithms that deal with such scenarios have been proposed, but there is no theoretical framework that offers a standard baseline to compare the search efficiency of different algorithms. In this work, we propose a general theoretical framework to describe the task of a decision-making agent searching for a distant target emitting noisy cues. Within this framework, we define a notion of an `asymptotically optimal' search algorithm and show how its performance produces a lower bound to the expected cost of any other algorithm. We demonstrate how the optimal decision boundaries and the corresponding PDFs of search times can be computed in a simplified one-dimensional search task, and compare them to those of a previously proposed `Infotaxis' algorithm. Generic features of searching in higher dimensions are discussed.