Containing a spread through sequential learning: to exploit or to explore?
Containing a spread through sequential learning: to exploit or to explore?
复制标题
DOI：
10.48550/arxiv.2303.00141
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
Xingran Chen;Hesam Nikpey;Jungyeol Kim;S. Sarkar;S. S. Bidokhti-S.
中科院分区：
文献类型：
--
作者：
Xingran Chen;Hesam Nikpey;Jungyeol Kim;S. Sarkar;S. S. Bidokhti-S.
通过测试和隔离受感染的节点来遏制不良接触过程的传播，例如传染病（例如 COVID-19）。该过程的时间和空间演变（以及通过隔离进行的遏制）使得此类检测与主动搜索检测策略根本不同。在这项工作中，通过主动学习方法，我们设计了测试和隔离策略，以在给定的测试预算下遏制传播并最大程度地减少累积感染。我们证明，通过贪婪地选择要测试的节点，可以在保证性能的情况下优化目标。我们进一步设计了基于奖励的方法，该方法可以有效地最小化累积感染的上限，并且在大型网络中计算起来更容易处理。然而，这些策略需要了解节点的感染概率，这些概率是动态变化的，并且必须通过顺序测试来学习。我们为此开发了一个消息传递框架，并在此基础上展示了通过基于奖励的启发式知识利用和通过精心设计的概率测试探索未知之间的新颖权衡。这种权衡与主动搜索或多臂老虎机问题（MAB）下的经典对应方案有着根本的区别。我们证明了在程式化网络中进行探索的必要性，并通过模拟表明，根据网络参数和传播情况，在各种合成和真实数据网络中，探索可以优于利用。
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, through an active learning approach, 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 dynamically changing and have to be learned by sequential testing. We develop a message-passing framework for this purpose and, building on that, show novel tradeoffs between exploitation of knowledge through reward-based heuristics and exploration of the unknown through a carefully designed probabilistic testing. The tradeoffs are fundamentally distinct from the classical counterparts under active search or multi-armed bandit problems (MABs). 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.