Hierarchical label queries with data-dependent partitions

Given a joint distribution $P_{X, Y}$ over a space $\X$ and a label set $\Y=\braces{0, 1}$, we consider the problem of recovering the labels of an unlabeled sample with as few label queries as possibl