Achievable Resolution Limits for the Noisy Adaptive 20 Questions Problem
Author：Lin Zhou Time：July 14, 2021 Number of clicks：
Language：English
Conference：2021 IEEE International Symposium on Information Theory (ISIT)
Date of Publication：2021年7月14日
Abstract：
We study the achievable performance of adaptive query procedures for the noisy 20 questions problem with measurement-dependent noise over a unit cube of finite dimension. The performance criterion that we consider is the minimal resolution, defined as the
L
∞
norm between the estimated and the true values of the random location vector of a target, given a finite number of queries constrained by an excess-resolution probability. Specifically, we derive the achievable resolution of an adaptive query procedure based on the variable length feedback code by Polyanskiy et al. (TIT 2011). Furthermore, we verify our theoretical results with numerical simulations and compare the performance of our considered adaptive query procedure with that of certain state-of-the-art algorithms, such as the sorted posterior matching algorithm by Chiu and Javadi (ITW 2016). In particular, we demonstrate that the termination strategy adopted in our adaptive query procedure can significantly enhance the asymptotic performance of adaptive query procedures, especially at moderate to large excess-resolution probability constraints.
Original Link
