Learning to Ask: Decision Transformers for Adaptive Quantitative Group Testing
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Reinforcement LearningSimilar Papers 제목 키워드 기반
AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing
The first part of the paper presents a review of the gold-standard testing protocol for Covid-19, real-time, reverse transcriptase PCR, and its properties and associated measurement data such as amplification curves that…
Semi-Quantitative Group Testing for Efficient and Accurate qPCR Screening of Pathogens with a Wide Range of Loads
Pathogenic infections pose a significant threat to global health, affecting millions of people every year and presenting substantial challenges to healthcare systems worldwide. Efficient and timely testing plays a critic…
Tropical Group Testing
Polymerase chain reaction (PCR) testing is the gold standard for diagnosing COVID-19. PCR amplifies the virus DNA 40 times to produce measurements of viral loads that span seven orders of magnitude. Unfortunately, the ou…
compressed sensingSize-adaptive Hypothesis Testing for Fairness
Determining whether an algorithmic decision-making system discriminates against a specific demographic typically involves comparing a single point estimate of a fairness metric against a predefined threshold. This practi…
FairnessAdaViT: Adaptive Vision Transformers for Efficient Image Recognition
Built on top of self-attention mechanisms, vision transformers have demonstrated remarkable performance on a variety of vision tasks recently. While achieving excellent performance, they still require relatively intensiv…