Achievable Resolution Limits of Noisy Adaptive 20 Questions Estimation for Multiple Targets
Chunsong Sun, Lin Yong Zhou · 2023
We study the problem of adaptive search for multiple targets using the framework of 20 questions estimation under the query-dependent noise channel. Specifically, we propose an adaptive query strategy that combines the ideas of non-adaptive search for multiple targets using random coding by Zhou, Bai and Hero (TIT, 2022) and adaptive search for one target using variable-length coding with feedback by Zhou and Hero (ISIT, 2021). Our main contribution is the derivation of the non-asymptotic and second-order asymptotic performance of our adaptive query procedure. Furthermore, we discuss the benefit of adaptivity, analytically and numerically, by comparing our results with the non-adaptive counterparts.