用决策变压器实现自适应分组测试，首次突破非自适应查询下限。
Learning to Ask: Decision Transformers for Adaptive Quantitative Group Testing
- 将稀疏二值向量恢复转化为低维整数向量问题
- 自适应算法平均查询次数低于非自适应理论下限
- 适合需要高效检测稀疏信号的场景
我们研究定量分组测试（QGT）问题，目标是从子集和查询中恢复稀疏二值向量：每次查询选择一组索引并返回对应元素之和。信息论表明自适应方法可将查询总数减半，但现有算法均未突破非自适应上限，其实际效益尚不明确。本文将QGT问题转化为维度仅与稀疏度相关的整数向量恢复任务，并将其建模为离线强化学习问题，采用决策变压器（Decision Transformers）进行自适应求解。实验首次证明，该自适应方法在平均查询次数上低于经典非自适应信息论下限，证实了自适应策略的有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。