Year
2021
Location
Halıcıoğlu Data Science Institute, UC San Diego
Category
Research
Duration
7 Months
Group testing is a combinatorial strategy to identify a small number of "infected" individuals in a large population by grouping samples rather than testing each one individually.
Adaptive group testing refines test design based on prior results (Markov process), unlike non-adaptive methods where tests are predetermined.
The infected population is modeled as a sparse binary vector
xof lengthN, withKones.Measurements are made using selected rows from the Walsh-Hadamard matrix
W, which is orthogonal and binary-structured. Each test computesy_t = W_t x. The goal is to identify the positions of the 1’s inxwith as few tests as possible.
We propose a faster, deterministic approach leveraging properties of the Walsh-Hadamard matrix:
Use initial
log(N)rows to compute a scalar sumSof the infected indices.Instead of solving a massive linear system (with up to
nCksolutions), they reduce the problem to findingKvalues that sum toS, significantly speeding up computation.Achieves better performance (e.g., works for
K=5,N=32), while prior work was limited toK=2.
An RL agent is trained to choose matrix rows to include in the test set:
State: Current subset of sampled rows
W_hatand corresponding measurementsy.Action: Pick a new row (without replacement) from
W.Reward: Encourages fewer candidate solutions (best case: 1), penalizes repetition or no improvement.
Training details: Uses experience replay, dynamic epsilon-greedy strategy, padded matrix representations, and custom episode termination conditions to cope with changing state/action space.
Ground-truth approach showed significant improvements in speed and scalability.
DQN method struggled to converge efficiently—especially for larger
N,K.Training became unstable or ineffective as episode lengths and action/state space complexity increased.
Conclusion: While the deterministic method outperforms prior research, the RL approach requires major tuning and enhancements to match or surpass traditional algorithms.
