Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem

In this paper, we propose an open-loop unequal-error-protection 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 output of a binary symmetric channel, the 20 questions problem can be mapped to an equivalent problem of channel coding with unequal error protection (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). With the proposed querying strategy, the rate of exponential decrease in the number of queries matches the rate of a closed-loop adaptive scheme, where queries are sequentially designed with the benefit of feedback. Furthermore, the achievable error exponent is significantly better than that of random block codes employing equal error protection.

I. Introduction

Consider a noisy 20 questions game between a player and an oracle. The objective of the player is to estimate the value of a continuous target variable . The player asks binary queries to the oracle who knows the value of , and receives a noisy version of the oracle’s correct answers transmitted through a binary symmetric channel with flipping probability , denoted BSC(). The central question addressed here is: What is the optimal sequence of queries to estimate the value of with a minimum estimation error at a fixed number of querying? This general setup of noisy 20 questions game and the optimal query design problem is of broad interest, arising in various areas, including active learning [3], [4], optimal sensing [5] and experimental design [6], [7], with diverse applications. For example, a target localization problem in a sensor network [8] can be modeled as a noisy 20 questions game where a player (agency) aims to locate a target by receiving query responses from sensors probing the region of interest.