Containing a spread through sequential learning: to exploit or to explore?
Xingran Chen
Abstract:
The spread of an undesirable contact process, such as an infectious disease (e.g. COVID-19), is contained through testing and isolation of infected nodes. The temporal and spatial evolution of the process (along with containment through isolation) render such detection as fundamentally different from active search detection strategies.
In this work, we design testing and isolation strategies to contain the spread and minimize the cumulative infections under a given test budget. We prove that the objective can be optimized, with performance guarantees, by greedily selecting the nodes to test. We further design reward-based methodologies that effectively minimize an upper bound on the cumulative infections and are computationally more tractable in large networks. These policies, however, need knowledge about the nodes’ infection probabilities which are unknown and have to be learned by sequential testing. We develop a message-passing framework for this purpose and, building on that, we show novel tradeoffs between exploitation of knowledge through reward-based heuristics and exploration of the unknown through a carefully design probabilistic testing. We provably show the necessity of exploration in a stylized network and show through simulations that exploration can outperform exploitation in various synthetic and real-data networks depending on the parameters of the network and the spread.