Learning to Ask: Decision Transformers for Adaptive Quantitative Group Testing
This addresses a long-standing open question in information theory and combinatorial optimization about the practical benefit of adaptivity in QGT, with potential applications in fields like medical testing and data compression.
The paper tackled the problem of quantitative group testing (QGT) by developing an adaptive algorithm that reduces the number of queries needed to recover sparse binary vectors, achieving for the first time an average query count below the non-adaptive information-theoretic bound.
We consider the problem of quantitative group testing (QGT), where the goal is to recover a sparse binary vector from aggregate subset-sum queries: each query selects a subset of indices and returns the sum of those entries. Information-theoretic results suggest that adaptivity could yield up to a twofold reduction in the total number of required queries, yet no algorithm has surpassed the non-adaptive bound, leaving its practical benefit an open question. In this paper, we reduce the QGT problem to an integer-vector recovery task whose dimension scales with the sparsity of the original problem rather than its full ambient size. We then formulate this reduced recovery task as an offline reinforcement learning problem and employ Decision Transformers to solve it adaptively. By combining these two steps, we obtain an effective end-to-end method for solving the QGT problem. Our experiments show that, for the first time in the literature, our adaptive algorithm reduces the average number of queries below the well-known non-adaptive information-theoretic bound, demonstrating that adaptivity can indeed reduce the number of queries.