Collaborative 20 Questions for Target Localization
From MaRDI portal
Abstract: We consider the problem of 20 questions with noise for multiple players under the minimum entropy criterion in the setting of stochastic search, with application to target localization. Each player yields a noisy response to a binary query governed by a certain error probability. First, we propose a sequential policy for constructing questions that queries each player in sequence and refines the posterior of the target location. Second, we consider a joint policy that asks all players questions in parallel at each time instant and characterize the structure of the optimal policy for constructing the sequence of questions. This generalizes the single player probabilistic bisection method for stochastic search problems. Third, we prove an equivalence between the two schemes showing that, despite the fact that the sequential scheme has access to a more refined filtration, the joint scheme performs just as well on average. Fourth, we establish convergence rates of the mean-square error (MSE) and derive error exponents. Lastly, we obtain an extension to the case of unknown error probabilities. This framework provides a mathematical model for incorporating a human in the loop for active machine learning systems.
Cited in
(4)- A novel technique for stochastic root-finding: enhancing the search with adaptive d-ary search
- Probabilistic bisection converges almost as quickly as stochastic approximation
- Twenty questions with random error
- The ignorant led by the blind: a hybrid human-machine vision system for fine-grained categorization
This page was built for publication: Collaborative 20 Questions for Target Localization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986444)
