Non-Adaptive Policies for 20 Questions Target Localization
This addresses localization under noise for scenarios like sensor networks, but it is incremental as it extends known adaptive methods to non-adaptive settings.
The paper tackles the problem of target localization with noisy queries in a non-adaptive 20-questions framework, deriving the asymptotic minimum achievable distortion and proposing a policy called Aurelian1 that achieves this bound.
The problem of target localization with noise is addressed. The target is a sample from a continuous random variable with known distribution and the goal is to locate it with minimum mean squared error distortion. The localization scheme or policy proceeds by queries, or questions, weather or not the target belongs to some subset as it is addressed in the 20-question framework. These subsets are not constrained to be intervals and the answers to the queries are noisy. While this situation is well studied for adaptive querying, this paper is focused on the non adaptive querying policies based on dyadic questions. The asymptotic minimum achievable distortion under such policies is derived. Furthermore, a policy named the Aurelian1 is exhibited which achieves asymptotically this distortion.