Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem

Abstract

We propose a non-adaptive unequal error protection (UEP) querying policy based on superposition coding for the noisy 20 questions problem. In this problem, a player wishes to successively refine an estimate of the value of a continuous random variable by posing binary queries and receiving noisy responses. When the queries are designed non-adaptively as a single block and the noisy responses are modeled as the outputs of a binary symmetric channel the 20 questions problem can be mapped to an equivalent problem of channel coding with UEP. A new non-adaptive querying strategy based on UEP superposition coding is introduced whose estimation error decreases with an exponential rate of convergence that is significantly better than that of the UEP repetition coding introduced by Variani et al. (2015). In fact, we show that the proposed non-adaptive UEP querying policy achieves the same order convergence rate as the adaptive policy.