Containing a spread through sequential learning: to exploit or to explore?
Authors: Xingran Chen
Hesam Nikpey
Jungyeol Kim
Saswati Sarkar
Shirin Saeedi Bidokhti
Venue: Accepted by TMLR ()

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, 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.

Published in Transactions on Machine Learning Research (March/200)
Containing a spread through sequential learning: to exploit or to explore?
Xingran Chen
zingranc@seas. wpw.ee..as.eeenneeeeeee
Electrical and Systems Engineering Department University of Pennsyloania
Hesam Nikpey
hesam Selcam@sccs.uupeeeee edu
Computer and Information Science Department University of Pennsylania
Jungyeol Kim JPMorgan Chase Co.
jungyeol@alunnni.coo wpwnn edu
Saswati Sarkar
vwati@scass.c www.uss.seeemm.ccmmm edu
Electrical and Systems Engineering Department University of Pennsyloania
Shirin Saeedi-Bidoklle
sacedi upenn. edu
Computer and Information Science Department University of Pennsyloania
Reviewed on OpenReview: https: // net/ pet/pdf? id- quRWcDDBann
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 ovolution of the process (along with containment through isolation) render such detection as fundamentally different from aclive search detection strategies. this work, through an active learning approach, we design testing and isolation strategies contain the spread and minimize the cumulative infections under given test budget. We prove that the objective can be optimized, with performance guaranlees, 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 carefully designed probabilistic testing. The tradeoffs fundamentally distinct from the classical counterparts under active scarch 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 the network and the spread.
1 Introduction
We consider learning and decision making in networked systems for processes that evolve both temporally and spatially. An important example in this class of processes COVID-19 infection. It evolves time (e.g. through different stages of the disease for an infected individual) and over contact network and its spread can be contained by testing and isolation. Public health systems need to judiciously decide who should be

---

Published in Transactions on Machine Learning Research (March/2022
tested and isolated in presence of limitations on the number of individuals who can be tested and isolated on a given day.
Most existing works on this topic have investigated the spread of COVID-19 through dynamic systems such STR models and their variants [ 2
These models are made more complex to fit the real 10 TT 12. Estimation of the model parameters by learning-based methods are considered and verified by real data in 13
g
5
G..
data in 7 8
9
TG Ir 18]
Other attributes such as lockdown policy 19, multi-
wave prediction 20, herd immunity threshold 2T are also considered by data-driven experiments. These works mostly focus on the estimation of model parameters thorough real data, and aim to make a. more accurate prediction of the spread. None of them, however, consider testing and isolation policies. Our work complements these investigations by designing sequential testing and isolation policies in order to minimize the cumulative infections. For this purpose, we have assumed full statistical knowledge of the spread model and the underlying contact network and we are not concerned with prediction and estimation of model parameters.
Designing optimal testing and control policies in dynamic networked systems often involves computational challenges. These challenges have been alleviated in control literature by capturing the spread through dif- ferential equations [22] 28 24 25 26]. The differential equations rely on classical mean-field approximations, considcring neighbors of cach node as "socially averaged hypothetical neighbors". Refinements of the mcan- field approximations such as pair approximation [21, degree-based approximation [ meta-population approximation [20 etc, all resort to some form of averaging of neighborhoods or more generally groups of
nodes. The averaging does not capture the heterogeneity of real-world complex social network and in effect disregards the contact network topology. But, in practice, the contact network topologies are often partially known, for example, from contact tracing apps that individuals launch on their phones. Thus test- ing and control strategics must exploit the partial topological information to control the spread. The most widely deployed testing and control policy, the (forward and backward) contact tracing (and its variants) 30
36 37 38 relies on partial knowledge of the network topology (ie, the neighbors of infectious nodes who have been detected), and therefore does not lend itself to mean-field analysis. Our proposed framework considers both the SIR evolution of the disease for each node and the spread of the disease through given network.
The following challenges arise in the design of intelligent testing strategies if one seeks to exploit the spatio- temporal evolution of the disease process and comply with limited lesting budget. Observing the state of a node at time t will provide information about the state of (i) the node in time + 1 and (ii) the neighbors of the node at time t, +, This is duc to the inherent correlation that exists between states of neighboring nodes because an infectious disease spreads through contact. Thus, testing has a dual role. It has to both detect/isolate infected nodes and learn the spread in various localities of the network. The spread can often be silent: an undetected node (that may not be particularly likely to be infected based on previous observations) can infect its neighbors. Thus, testing nodes that do not necessarily appear to be infected may lead to timely discovery of even larger clusters of infected nodes waiting to explode. In other words, there is on ântrinsic trudeoff' between ecploitation of knowledge us. exploration of the unknown. Exploration vs. exploitation tradeoffs were originally studied in classical multi-armed bandit (MAB) problems where there is the notion of a single optimal arm that can be found by repeating a set of fixed actions 39
40
41
MAB testing
strategies have also been designed for exploring partially observable networks +2 Our problem differs from what is mainly studied in the MAB literature because (i) the number of arms (potential infected nodes) is time-variant and actions cannot be repeated; (ii) the exploration vs. exploitation tradeoff in our context arises due to lack of knowledge about the time-evolving set of infected nodes, rather than lack of knowledge about the network or the process model and its parameters.
Note that contact tracing policies are in sense exploitation policies: upon finding positive nodes, they exploit that knowledge and trace the contacts. While relatively practical, they have two main shortcomings, as implemented loday: (i) They are not able to prioritize nodes based on their likelihood of being infected (beyond the coarse notion of contact or lack thereof). For example, consider an infectious node that has two noighbors, with different degrees. Under current contact tracing stratogics, both neighbors have the same status. But in order to contain the spread as soon as possible, the node with large degree should be prioritized for testing. A similar drawback becomes apparent if the neighbors themselves have different
2

---

Published in Transactions on Machine Learning Research (March/2023)
number of infectious neighbors; one with larger mumber of infectious neighbors should be prioritized for testing, but current contact tracing strategies accord both the same priority. (ii) Contact tracing strategies do not incorporate any type of exploration. This may be a fundamental limitation of contact tracing. [S] has shown that, with high cost, contact tracing policies perform better when they incorporate exploration (active case finding). In contrast, our work provides a probabilistic framework to not only allow for exploitation in a fundamental manner but also to incorporate exploration in order to minimize the number of infections.
Finally, our problem is also related to active search in graphs where the goal is to test pest/search for a set of (fixed) target nodes under a set of given (static) similarity values between pairs of nodes 43 the target nodes in these works are assumed fixed, whereas the target is dynamic in our setting because the infection spreads over time and space (i.e, over the contact nelwork). Thus, node may need to be tested multiple times. The importance of exploitation/explle /exploration is also known, implicitly and/or explicitly, in various reinforcement learning literature
45
40d But
We now distinguish our work from testing strategies that combine exploitation and exploration in some form 50 51 52). Through a theoretical approach, b0] models the testing problem as a partially observable Markov decision process (POMDP). An optimal policy can, in principle, be formulated through POMDP, but such strategies are intractable in their general form (and heuristics are often far from optimal) devises tractable approximate algorithms with significant caveat: In the design, analysis, and evaluation of the proposed algorithms, it is assumed that at each time the process can spread only on single random edge of the network. This is a very special case that is hard to justify in practice and it is not clear how one could go beyond this assumption. On the other hand, [5 proposes a heuristic by implementing classical learning mothods such as Lincar support vector machine (SVM) and Polynomial SVM to rank nodes basod on a notion of risk score (constructed by real-data) while reserving a portion of the test budget for random testing which can be understood as exploration. No spread model or contact network is assumed. 52 and this work were done concurrently. In 62, a tractable scheme to control dynamical processes temporal graphs was proposed, through a POMDP solution with a combination of Graph Neural Networks (GNN) and Reinforcement Learning (RI.) algorithm. Nodes are tested based on some scores obtained by the sequential learning framework, but no fundamental probabilities of the states of nodes were revealed. Different from our approach is model- based and we observe novel exploration-exploitttiie
[X 5e 60
51 52 due to a lack of knowledge about the model or network, but rather because the set of infected nodes is unknown and evolves with time. We can also utilize knowledge about both the model and the contact network to devise probabilistic framework for decision making.
tradcoffs that arise not
We now summarize the contribution of some significant works that consider only exploitation and do not 38
37 have considered combination of isolation and contact tracing sequential policies, and B6 has shown that the sequential strategies would reduce transmission more than mass testing or self-isolation alone, while 37 has shown that the sequential strategies can reduce the amount of quarantine time served and cost, honce individuals may increase participation in contact tracing, enabling less frequent and severe lockdown measures. 38 have proposed a novel approach to modeling multi-round tracing under uncertainty.
utilize any exploration 36
37
36
network-based screening/conteee
Our Contributions In this work, we study a spread process such as Covid-19 and design sequential testing and isolation policies to contain the spread. Our contributions are as follows.
Formulating the spread process through a compartmental model and a given contact network, we show that the problem of minimizing the total cunulative infections under given test budget reduces to minimizing supermodular function expressed in terms of nodes' probabilities of infection and it thus admits a near-optimal greedy policy. We further design reward-based algorithms that minimize an upper bound on the cumulative infections and are computationally more tractable in large networks.
The greedy policy and its reward-based derivatives are applicable if nodes" probabilities of infec- tion were known. However, since the set of infected nodes are unknown, these probabilities are unknown and can only be learned through sequential testing. We provide message-passing frame- work for sequential estimation of nodes' posterior probabilities of infection given the history of test observations.
3

---

Published in Transactions on Machine Learning Research (larch/202])
14
13
B
h
7 1
40
S
L
R
15
Figure 1: Left: Time evolution of the process per individual nodes. Right: A contact network with nodes in states susceptible (bluc), latency (pink), infectious (red), recovered (yellow).
We argue that testing has dual role: (i) discovering and isolating the infected nodes to contain the spread, and (ii) providing more accurate estimates for nodes' infection probabilities which are used for decision making. In this sense, exploilation policies in which decision making only largets (i) can be suboptimal. We prove in a stylized network that when the belief about the probabilities wrong, exploitation can be arbitrarily bad, while a policy that combines exploitation with random testing can contain the spread. This points novel exploitation-ccpllottio tradeoffs that stem from the lack of knowledge about the location of infected nodes, rather than the network spread process.
Following these findings, we propose exploration policies that test each node probabilisticall ac- cording to its reward. The core idea is to balance exploitation of knowledge (about the nodes' infection probabilities and the resulting rewards) and exploration of the unknown (to get more ac- curate estimates of the infection probabilitie). Through simulations, compare the performance of exploration and exploitation policies in several synthetic and real-data networks. In particular, we invostigate the role of three paramcters on when exploration outperforms exploitation: (i) the unregulated delay, i.e., the time period when the disease spreads without intervention; (ii) the global clustering coefficient of the network, and (iii) the average shortest path length of the network. We show that when the above parameters increase, exploration becomes more beneficial as it provides better estimates of the nodes' probabilities of infection.
2 Modeling
To describe spread process, we use a discrete time compurtmental model 5 Over decades, compartmental models have been key in the study of epidemies and opinion dynamics, albeit often disregarding the network topology. In this work, capture the spread focus model for the spread of COVID-19, The ideas can naturally be generalized to other applications. The main notations in the full paper are given in Table
given contact network. For clarity of presentation, we
We model the progression of Covid-19 per individual, in time, through four stages states: Susceptible (S), Latent (L), Infectious (I), and Recovered (R). Per contact, infections individual infects susceptible individual with transmission probability 3. An infected individual is initially in the latent state L, subse- quently he becomes infections (state I), finally he recovers (state R). Fig. durations in the latent and infectious states are geometrically distributed, with means 1/X, 1/7 respectively. We represent the state of node at time by random variable (1) and its support set X' = {S, L, 1, R). We assume that the parameters 8, X and y are known to the public health authority. This a practical assumption because the parameters can be estimated by the public health authority based on the pandenmic data collected 56 58
[ (left) depicts the evolution. The
Let G(t) = ((t)) denote the contact network at time t, where Vtt) is the of nodcs/individue of cardinality (t), and E(t) is the set of edges between the nodes, describing interactions/contacct on day t. Let. V V(0), & E()), g (()), and N N(O). The network is time-dependent not only because
4

---

Published in Transactions on Machine Learning Research (larch/2023)
Notations
Definitions
B
transmission probability mcan duration in the latent state mean duration in the infectious state state of node i at time t, o,(t) {4, S, L, R} contact network at time
1/7
1/X
(,(t)
G(t)
((t)
set of nodes at time
E(t)
set of edges at time cardinality of V(()
N(1)
N
N (()
0,(1)
neighbors of node time f
(t)()
{i} U a,(t)
Y((t)
testing result of node i at time
O(t)
set of nodes tested at time
Y())
(t)(t)) testing budget at time lesting and isolation policy
B(t)
m
(t(()
cumulative infections at time
KT (1)
set of nodes tested at time (under policy m)
k*(()
(1) K²(1)
K
T
time horizon
(1)
Irue probability vector of node prior probability vector of node i
(t)
(1)
posterior probability vector of node updated posterior probability vector of node i
(()
(t())
rewards of selecting node at time t estimated rewards of node at time /
((())
V+(1)
v (() = O(1) (0) (t 1)
2.(1)
(,(() Di E 0, 1), (.
(t)
(t()) a, (f) (t) (1,S,L, R}
(tt))
(((t) (t))) G(t) (I,
Table Summary of main notations

---

Published in Transactions on Machine Learning Research MMarch/2023)
interactions change daily basis, but also because nodes may be tested and isolated. If node is tested positive any day it will be isolated immediately. If a node is isolated any day 4, we assume that it remains in isolation until he recovers. We assume that a recovered node can not be reinfected again. Thus a node that isolated on any day t has no impact on the network from then onwards. Such nodes can be regarded as "removed". Therefore, Fig. | (right) depicts a contact network at given time t. We assume that a public health authority knows the entire contact network and decides who to test based on this information. This assumption has been made in several other works in this genre eg in 38
removed from the contact network for all subsequent times I, 1,I+1.....
Denote the set of neighbors of node i, in day i, by dt(t). The state of cach node at time t+ 1 depends on the state of its neighbors (I), as well as its own state in day 6, as given by the following conditional probability:
Pr Pr(
where (1) 0;)))
Node i tested positive on day if it is the infectious state ( Let (t()) denote the test result:
o,(t)=1 =1 Y(()) - f o,(1) E RR.
(1)
We do not assume any type of error in testing and (t) is hence deterministic function of (t).) Let O(t)
be the set of nodes that have been tested (observed) in day and denote the network observations at time by ((t) (Y(()))
Our goal in this paper is to design lesting and isolation strategies in order to contain the spread and minimize the cumulative infections. Naturally, testing resources (and hence observations) are often limited and such constraints make decision making challenging. Let Bt)) be the maximum number of tests that could be performed on day I, called the lesting budgel. B() can evolve based on the system necessities, e.g. in contact tracing that is widely deployed for COVID-19, the number of tests chosen based on the history of observations Also, governments often upgrade testing infrastructure the number of cases increase. Our framework captures both fixed and time-dependent budget Btt), but focus time-dependent B(t) for simulations.
Define the cumulative infections on day t, denoted by (t))), as the number of nodes who have been infected before and including day t, where æ is the testing and isolation policy. Let (C*(t) denote the set of tests π performs on day t. Given large time horizon T, our objective is:
min s.L.
(T))
(2)
B()
Recall that (t), the state of node on day t, random variable and unknown. For each node i, define a probability vector g (t) of size (X'), where each coordinate is the probability of the node being in particular state at the end of time I. The coordinates of (1) follow the order (7, L, R) and have
e (t) = = (0)))))))))))))))))))))))) (1)
(1) Pr (a:(1) = =))
(3)
For example, u (1) represents the probability of node being in state in time t. We now define (D( to be the conditional probability of node being infected by nodes in (for the first time) at day t, as a function of the nodes' states (or(())vvv()) We have
F,(D;t) (o.(0==))
II (1-((10()))))) (1- II (1 (1 (1-B1 (1-31(o,(0=))) (E)D
(4)
jeDna.(t)
1 We assume that node in the latent state infected, but not infoctious. We further assume that latent nodes test negative.
In practical implementations, scheduling constraints play role but we disregard that this work.

---

Published in Transactions on Machine Learning Research MMrch/2022,
Equation captures the impact that the nodes in D have on infecting node i at day t. In this equation we assume that the infections from different. nodes are independent. The same assumption has also been Then, we find the expectation (with respect to
made in several other papers in this genre, eg in 27 28 29
(ov(t)) of (4) as follows:
B(o,()))evco (B((;())= = (1) II (1 (1- B0)
II (1 (0-Bo)(()) (EDDA,()
(5)
jEO,00)D
It is worth noting that 44 is probability conditioned on (a.(1) while 5 is an unconditional proba- bility. To obtain (5), we have indeed assumed that the states of the nodes are independent. This assumption does not hold in general and we only utilize it here to obtain simple expression in (5) in terms of the infection probabilities. We do not use this independence assumption in the rest of the paper. Define
S(D:t)=
E [DF(() iEV(E)
(6)
Here, S(D;t) represents the (expected) number of newly infectious nodes incurred by nodes in D at day t. Recall that (t)(t) be the set of nodes that are tested at time t. We show the following result in Appendix A
Lemma ((C"((1)-0*00)) = = S(V(0V<" (1)
2.1 Supermodularity
It complex to solve (2) globally, especially one secks to find solutions that are optimal looking into the future. We thus simplily the optimization (2) for policies that are myopic time as follows. First, note that C (I) can be re-written as follows through telescopic sum:
T-1 (T( = - c(( 1=
(7)
Then, we restrict attention to myopic policies that at each time minimize E [CC*(t+ CT()))
We then
show how [CT (1 + (*(() can be expressed in terms of supermodular function.
Using ( along with Lemma we seck to solve the following optimization sequentially in time for 0 0st5 T-1:
min (C)
(()())(((())))
(8)
We now prove some desired properties for the set function (f);t) (see Appendix B
Theorem 1. (()))))) defined in 6 is supermodulas and increasing monotone function KCT (l).
On day 4, and given the network, the probability vectors of all nodes, and (T) C (1), for any node & (t), node will incur larger increment of newly infections nodes under IC3 (t) than that under (TT(t), (t). This because node i may have common neighbors with nodes in 10 (1). So, supermodularity holds
Theorem [
The optimization
However, using the supermodularity of ((V(t) (f);t), propose Algorithm based on 60 Algorithm A] to greedily optimize (8) in every day L. Denote the optimum solution of B as ОPT. As proved in 60,, on every day t, Algorithm attains solution, denoted by R*)t), such that (V(E) < ((t) OPT, iee. the solution (C*(t) is an e(t)-approximation of the optimum solution. Here, on day f, the constant <(t), which is the steepness of the set function S(:;t) as described in 60 can be calculated as follows, c(t) 4(1-2) and c' c' maxaev(e)
8 is NP-hard 59
-(V()))))((())(a))) ((()))))
-(V(0)))
In Algorithm|
every day in every step, choose the node who provides the minimum increment on ((; based on the results in the previous step, and then remove the node from the current node set. Algorithm D is stopped when (*(() nodes have been chosen. The complexity of this algorithm is discussed in Appendix
3r.tt X finite set. function f: 2 supermodular any C and xE XBB ((AU))) -(A) J(BU (x)) S(B).

---

Published in Transactions on Machine Learning Research (larch/2023)
Algorithm Greedy Algorithm
Step O: On day t, imput (e)(t))) set Au V(t).
repeat
Step i: Let A; = Aa-h where
0: arg min S((a) fai... a0-11:t). (4-)))))))))))) aeA:-1
until = (tt) - (t), and return (t) A.,
3 Exploitation and Exploration
In Section 2.1 we proposed near-optimal greedy algorithm sequentially (in time) select the nodes to lest. However, Algorithm [ has two shortcomings. (i) The computation is costly when N and/or or T are large (see Appendix Cp. (ii) The objective function ((V(t)(CCT(t) is dependent on Rev()) which is unknown, even though the network and the process are stochastically fully given (sce Section 2 This is because the set of infected nodes are unknown and time-evolving.
To overcome the first shortcoming, we propose a simpler reward maximization policy by minimizing an upper bound on the objective function in (8). To overcome the second shortcoming, we estimate Nev))) using the history of test observations {Y(()) (as presented in Section 4 we refer the estimates (u)(e))))()) Both the greedy policy and its reward-based variant that will propose in this section thus need to perform decision making based on the estimates {u, (t))ve and refer to them as "exploitation" policies.
Tt now becomes clear that testing has two roles: to find the infected in order to isolate them and contain the spread, and to provide better estimates of (2,(t)) This leads to interesting tradeoffs between exploitation and exploration as we will discuss next. Under exploitation policies, we test nodes determinis- tically based on function of (e)(t))) (which is called "reward", and will be defined later); while under exploration policies, nodes are tested according to probabilistic framework (based rewards of all nodes).
To simplify the decision making into reward maxinization, we first derive upper bound on (()())(((()))) Define
ri(t) = t{f)]t).
(9)
Using the supermodularity of the function S(-), we prove the following lemma in Appendix Lemma ((V())(CT(t:t) s ((((t):)) (i rt)..
Remark 1. Recall that S(;t) is supermodular function, then the amount of newly infectious nodes incurred by the set (I),1, (I)) larger than the sum of the amount of newly infectious nodes by every individual node in (t), i.e., EiERstori(f) Thus, ((V())(T(()tt) upper bounded by S(V(t):t) Evers re(t).
We propose to minimize the upper bound in Lemma 2 instead of (t):t) Since V(t) is known and s s((()):) hence constant, the problem reduces to solving:
Σ Tl)))
max ICT (8) (B())
(10)
(E)
Given probabilities (t))too)) the solution to 10 is to pick the nodes associated with the B(t) largest values (t). We thus refer (t) as the reward of selecting node i.
Let (e)oo be an estimate for (v:(())vv()) found by estimating the conditional probability of the state of node given the history of observations (Y(r))==)- Our proposed reward-basod Exploitation (RbEx) policy follows the same idea of selecting the nodes with the highest rewards. Note that (v.(t))ev() is unknown to all nodes. Instead of using the true probabilities (n,())))))) consider the estimates of it which
8

---

Published in Transactions on Machine Learning Research (March/20P)
sequentially update by computing the prior probabilities (e:(t)) and the posterior probabilities (w,(") Nev)())) In particular, (ev(o)) and (e)(0)))v are the prior probabilities and the posterior probabilities on the imitial day, respectively. Hence, we calculate the estimate of rewards, denoted by ft(t), by replacing (e)(t))ev()) with (veve))
6 and
Algorithm Reward-based Exploitation (RbEx) Policy
Input (w, (0))))))))) (O))e)())) Y(0), and I = 0.
Repeat for f = 1.2....,22.. .
Step 1: Calculate {f: (fr())) based on (()eee and (9)
Step 2: Re-arrange the sequence (f((t))ev()) in descending order, and test the first B(t) nodes. Get the new observations Y(t).
Step 3: Based on ((), update (t, + 1) (Ev(44)) by Algorithm (Step 0 Step 2) in Section
The shortcoming of Algorithm 2 is that it targets maximizing the estimated sum rewards, even though the estimates may be inaccurate. Tn this case, testing is heavily biased towards the history of testing and it does not provide opportunities for getting better estimates of the rewards. For example, consider a network with several clusters. one positive node is known by Algorithm 2 then it may get stuck in that cluster and fail to locate more positives in other clusters.
In Section 4.2 we will prove, in line network, that the exploitation policy described in Algorithm 2 can be improved by constant factor (in terms of the resulting cumulative infections) if a simple form of exploration is incorporated.
We next propose an exploration policy. Our proposed policy is probabilistic in the sense that the nodes are randomly tested with probabilities that are proportional to their corresponding estimated rewards. This approach has similarities and differences to Thompson sampling and more generally posterior sampling. The similarity lies in the probabilistic nature of testing using posterior probabilities. The difference is that in our setting decision making depends on the distributions of decision variables, but not samples of the decision variables.
More specifically, at time t, node tested with probability min(1, B(0A(()) Exevey (s()) }. which depends on the budget B(t). Note that each node is tested with probability at most 1; so if B(E):((t) i, then we would not fully utilize the budget. The unused budget is thus
for some node
Eeevc fy(()
B(I)A:(t) 1)*
c(t)
Σ
(11)
EjEroo (t)
tEV())
and can be used for further testing Exploration (REEr) policy.
Algorithm
3 outlines our proposed Reward- based Exploitation-
Algorithm 3 Reward-based Exploitation Explotaatin-EExploratio (REEr) Policy
Input (m (0)) (0))vvv))))) Y(0), and l 0.
Repeat for = 2, .
Step 1: Calculate (f)(te) based on (u.(t)) and 9
(()).(() Step 2: Test node i with probability min Eyevey (-) After that, randomly select c(t) (defined in
further nodes to test (see Footnote 4h. Get the new observations Y(t).
Step 3: Based on (t),, update (t,(t 1] by Algorithm (Step 0 ~ Step 2) in Section
Note that c(f) is not always an integer. Instead of c(t), we use Int (c(t) with probability [Int [Int(c(t)) - c(t)) where Int(-) E
[L-]- [-1].
9

---

Published in Transactions on Machine Learning Research (March/2023)
4 Message- Message-Passing Framework
As discussed in Section 3. the probabilities {t,( are unknown. In this section, we develop message passing framework to sequentially estimate {t)( based on the network observations and the dynamics of the spread process. We refer to these estimates as (1)).
When node is tested on day t, an observation (t) is provided about its state. Knowing the state of node provides two types of information: (i) it provides information about the state of the neighboring nodes in future time slots L 1,,+, 2... (because of the evolution of the spread in time and on the network); and (ii) it also provides information about the past of the spread, meaning that we can infer about the state of the (unobserved) nodes at previous time slots. For example, if node i is tested positive in time 4, we would know that (i) its neighbors are more likely to be infected in time + and (ii) some of its neighbors must have been infected in a previous time for node i to be infected now. This forms the basis for our backward-forwant message passing framework.
we first describe the forward propagation of belief. Suppose that time i, the probability vector (t) given for all i. The probability vector 2, 1) can be computed
Given the spread model of Section 2
follows (see Appendix B
(t+ = v,(t)
(((())(())))))))))))
(12)
where Ps Ps((2, (t) (n)) is local transition probability matrix given in Appendix E
Recall that (() denotes the collection of network observations on day t. The history of observations is then denoted by {T) Based on these observations, we wish to find an estimate of the probability vector
(t) for cach i E V(t). We denote this estimate by (t) = (8) (t), E X) and refer to it, in this section, as the prior probability of node i in time t. We further define the posterior probability w,( = (w (t), x E x)
of node i in time t (after obtaining new observations Y()).. In particular,
e (1) Pr (o: x (() w// (1) = Pr (a.(1) (0 ((())))
Here, the prior probability is defined at the beginning of evevyy day, and the posterior probability is defined at the end of every day. Conditioning all probabilitics in 12 on (Y(T)) we obtain the following forward- update rule (see Appendix F
= (t) x P. (122) (1))e
(13)
15). we need to utilize the observations (t) and the underlying dependency among modes' states to updale the posterior probabilities (w,(()},, and consequently update {u,(t + 1)}; based on the forward-update rule (1). This is however non-trivial. A Naive approach would be to locally incorporate node i's observation Yt(t) into wi(l) and oblain (1 using (3). This approuch, however, does not fully exploit the observations and it disregards the dependency among nodes' states, as caused by the nature of the spread (An example is provided in Appendix M..
Remark 2. Following
Backward Propagation of Belief To capture the dependency of nodes' states and thus best utilize the
observations, we proceed as follows. First, denote
(t 1) (t=),xEE)) el (1 1) =x
Vector (t-1) is the posterior probability of node i at time 1-1, after obtaining the history of observations up to and including time t. By computing (t-1,, we are effectively correcting our belief on the state of the nodes in the previous time slot by inference based on the obscrvations acquired at time t. This constitutes the backward step of our framework and we will expand on it shortly. The backward step can be repeated to correct our belief also in times t - 2, t 3, etc. For clarity of presentation and tractability of our analysis
10

---

Published in Transactions on Machine Learning Research (March/200)
and experiments, truncate the backward step at time t and present assumptions under which this truncation is theoretically justifiable. Considering larger truncation windows is straightforward but out of the scope of this paper.
Once our belief about nodes' states is updated in prior time slots (e.g., e, - 1) is obtained), it is propa- gated forward in time for prediction and to provide a more accurate estimate of the nodes' posterior and prior probabilities. More specifically, consider (22) written for time (rather than + 1) and condition all probabilities on {Y(T))==1- We oblain the following update rule (see Appendix
(t) = et - 1) (((ee((tt)))eott
(14)
where (((,, 1) jeot (1-1)) is given in Appendix F Note that the local transition matrix in 14 is not
the same as 15 This is because "future" observations were available in P. (fe,(t ge) (c-1)) The probability vectors (e,(t-1)); provide better estimates for (w,(t)} through (14) and the prior probabilities (t, 1) then computed using (13) to be used for decision making in time f+11. The block diagram
in Fig. 3 depicts the high-level idea of our framework. It is worth noting that P. P,(w,, (o)) in 13 and
P.
()) (1-1)) in 14 both depend on the observations, (Y(T))==
We next discuss how e,(t - 1) can be computed, starting with some notations. Denote by
citt) or (x)))))))))))) (t)
(15)
the state of the nodes in the posterior probability spaces conditioned on the observations (Y(r)) and (Y(r))==), respectively. We further define (,(() to be the set of those neighbors of node at time / 1, including node i, who are observed/ /eested at time t. This set consists of all nodes whose posterior probabilities will be updated at time --1 (given new observation Yı((). The set of all neighbors (except node i) of the nodes in (t) then defines (t). The set l,(t) consists of all nodes whose posterior probabilities at time is updated by the observation (t). More precisely, we have
(() n()) (1-1),
(1) [ili E of (1- 1), (.(O))).
(1) Gili e (1, O())((
where Ott) is the set of observed nodes at time t (see Figure? 2h. In Appendix
we show
2 (t- 1)= Pr (L(0)G((--)===
wr (t 1)
(16)
Pr (Y(1))
It suffices to find Pr (
The denominator Pr (Y(t)) is then found by normalization of the enumerator in 16. Let {rs)yoore) be a realization of (0,())eeo and (u)he be realization of {ti(t - 1))ee.()) (1). We prove the following in Appendix G under a simplifying truncation assumption (see
Assumption in Appendix Gl where the backward step is truncated in time t 1: 1:
Pr Pr (Y(()))) 1) 2) Pr ((Y(()))ev =x)
Σ
II Pr (t)
(syheva an (E))(t)
(17)
x
Σ
II
Pr (r x
II lE(O,())
w (t 1).
{en he JEV.())
We finally present our Backward- Forruadd-Foruard Algorithm to sequentially compute estimates (f,(t)) Algorithm The process of Algorithm is given in Fig and we also give simple example to show the process of A Agorithmm 4 in Appendix H
11

---

Published in Transactions on Machine Learning Research (larch/202))
21(1)
1 - 1)
An example of (t), (t) and (t).) Node is marked in red, and its neighborhood 0 (t 1) is shown by the red contour. Suppose that the gray nodes are tested day 1-1, then (t) is the set of nodes within the green contour, and (t) consists of the nodes in the purple contour. Finally, nodes in O, are marked with bold black border
Figure 2:
Decision making
Decision making
(u(t= 1));
lu(t));
(u(t + 1));
Equation (13)
Equation (13)
w(t 1));
[w()),
[w(t + 1));
Equation (14)
Y(r) Testing Result
Equation (16)
Le(t - 1));
Le(t);;
{e(1 + 1));
Figure 3: The process of Algorithm One example of complete process is given in unshaded blocks. Recall that u,(T), (T), and (T()), where 7 (t- 1}, are the prior probabilities, the postcrior probabilities, and the updated posterior probabilities, respectively.
4.1 Necessity of Backward Updating
Now we provide an example which illustrates the necessity of backward updating.
Algorithm Backward-Forwail Algorithm
Input (0), (0)) (w, (0) (0)kevo Repeat for 1, ....................... T
Step 0: Based Y(t), get V(L) from V(t 10--1 1).
Step 1: Backward step. Update gt by
16
17
and then compute (t) by
14
Step 2: Forward step. Compute ( 1) by 13
12

---

Published in Transactions on Machine Learning Research (larch/2023)
2
3
N
Figure The line network Example 1
Example 1. Consider a line network with the node set V (1.2....,NN) and the edge set & i(t, S N 11 (see Figure 4. On the initial day, we assume that each node is infected independently with and B() = We further assume that there is no isolation when
probability 1/N. Let 3 = 1, X 0, = 2=
a positive node is tested.
Based on Example [ we show that the naive approach of Remark (i.e., forward-only updating) will cause the estimated probabilities never converge to the true probabilities of infection. Nonetheless, if we use the Bockward-Forwald Algorithm f the estimated probabilities converge to the true probabilities after a certain number of steps. Formally, prove the following result in Appendix J
Theorem 2. For any testing policy that sequentially computes {t)(t)} based on 13 (see Remark 2 with probability (approzimately) 1, we have Σ (t), (t)l '000 O(N), for large N On the other hand, there exists a testing policy that sequentially updates (t){ based on Algorithm and attains E (t),(t) n(tt)ll 0, 12 2N.
Roadmap of proof: Consider a simple case where every node is susceptible. Since each node is infected with probability 1/N, then the case occurs with probability = -//E.
Under the case above, consider any testing policy based on the algorithm in Remark If a node is tested on day t, then the policy "clears" " the tested node. Since the updating rule of the algorithm can not go back to the in information on day 1-1, then can not "clear" anyy neighbors of the lesled node and ils probability of infection updates a non-zero value in the next day. Furthermore, we show that almost all nodes have an significantly large probability of infection when time horizon is sufficiently large, hence E (1,,(t)_,(tt))) 3330 ((N).
-
On the other hand, we propose specific testing policy, Note that there is no infection, if Algorithm A is used to update probabilities, then it can reveal the states of all nodes under the specific testing policy after at most 2N days. So we have E (t), 2, (t)ll = 0, t 2N.
In Theorem 2 we illustrate the necessity of backward updating when testing is limited. In essence, want to "clear" the graph and confirm that there are no infections. If the number of tests is limited, we have mathematically shown that no algorithu can correctly estimate the nodes' infection probabilities if it does not use the backward (inference) step. On the contrary, there is an algorithm that uses the backward step along with the forward step and the estimates that it provides for the nodes' infection probabilities converge to the true probabilities of the nodes after some finite steps. Even though the considered graph is simple but the phenomena. it captures is general.
As discussed in Theorem the backward updating is necessary. However, bacward updating can be compu- fationally expensive in large dense graphs. To trade off the impact of backward updating and the reduction of computation complexity, propose an a-linking backward updating algorithm in Appendix K where Algorithm
g is applied on random subgraph with fewer edges.
4.2 Necessity of Exploration
Note that in reality we have no information for (c,(1)), and only have the estimates (u,()), One may wonder if exploitation based on wrong initial estimated probability vectors, i.e., {u,(0)} misleads decision making by providing poorer and poorer estimates of the probabilities of infection. If so, exploration may be necessary.
3 Here, À= 0 implics there is no latent state, and 7 0 implics that nodes recover. 6Theorem holds for all kinds of noem due the equivalence norms. addition, the convergence is topological convergence.
13

---

Published in Transactions on Machine Learning Research (March/2023)
Example 2. Consider V = =1,, and edges & = ((i, i --1 (see Figure 4 Let N > 10, B = 1, x = 0, 7 0, and B(t) = 10. Suppose that on the initial day, node 1 is infected and all other modes are
susceptible. Consider a wrong initial estimate: w (0) = u (8) (0) if i To and w/ (8) (0) - uj / (0) N
ON
10c
otherwise, where >>> 0. With this initial belief, we have Σ w (0) 2, (0)1 0(1
Different from Example L here we consider the isolation of nodes that are tested positive. In Example 2 suppose that a specific exploration policy is applied: 1 (out of 10) tests is done randomly, and the other 9 tests are done following exploitation. Now, in Appendix L. we show that under the RbEx policy, the cunulative infection is at least a/V for a constant a, while under the exploration policy defined above, the cumulative infection is at most bN with very high probability, and the ratio a/b can be any constant for a large enough N. More formally, we have the following theorem. Let Po be large probability and consider a large time horizon T. Denote the cumulative infections under the RbEx policy by CRB (T) and under the specific exploration policy defined above by (T). We prove the necessity of exploration in the following Theorem.
Theorem 3. With probability po > on N and po-
99 100
CRB
2 p(N, where (N,po) is a consland only depending (TF(IT)
Rondmap of proof: Under the RbFx policy, we test nodes based on their predicted probabilities. Since the nodes that are located towards the end of the line (right side in Fig. 4 have non-zero probabilities, they are tested first while the disease spreads on the other end of the network fleft side in Fig. 4. Mathematically, suppose that for the first time, an infectious node is tested at day tayt=ann aN,, then there are at least min(aN, NY} infectious nodes before the spread con be contained.
Under the specific exploration policy described above, consider the event that, for the first time, an infectious mode is exploved on day i. = N (V' < <a). We aryue that with probabilily po, the exploration policy catches at least two new infections at each step after t = N. After 2t, the algoritim catches all the infections, and we have at most 2b infections. Let b b= 28/ This is an improvement by a factor of at least a in comparison b
to the RbEi strategy. Factor 5 depends on the values of N and po-
In Theorem 3 we show the necessity of exploration when our initial belief is slightly wrong, i.c., is slightly biased Loward the other end of the network (In general, this could be due to a wrong belief, prior test results, etc). We have formally proved that when the testing capacity is limited, exploration can significantly improve the cumulative infections, i.e., contain the spread. This motivates the design of exploration policies. Even though the setting is simple, the phenomena it captures is much more general.
5
Simulations
5.1 Overview
In this section, we use simulations study the performance of the proposed exploitation and exploration policies for various synthetic and real-data networks. Towards this end, we define some metrics that quantify how different metries perform and key network parameters and attributes that determine the values of these metrics and thereby how exploitation and exploration compare. We also identify benchmark policies which represent. the extreme ends of the tradeoff between exploration and exploitation to compare with the policies we propose and assess the performance enhancements brought about by judicious combinations of exploration and exploitation. Through our experiments, we aim to answer two main questions for various synthetic and real-data norworks: (i) Can exploration policies do better that exploitation policies and if so, when would that be the case? (ii) What parameters would affect the performance of exploration and exploitation policies? These are important questions to shed light on the role of exploration. These questions are particularly raised by Theorem 3 in which we prove that exploration can significantly outperform exploitation in some (stylized) networks. We design the experiments in order to shed light on the above questions and to understand the extent of the necessity of exploration in different network models and scenarios.
Network parameters We consider the following parameters: (i) The unregulated delay é which is the time from the initial start of the spread to the first time testing and intervention starts; (ii) The (global) clustering coefficient 61 Chapter 3), denoted by Ye, which is defined as measure of the degree to which nodes in graph tend to cluster together; (iii) The path-length, denoted by Tip, which measures the average
14

---

Published in Transactions on Machine Learning Research (larch/2023)
shortest distance between every possible pair of nodes. We consider attributes such as the initialization of the process, and the lack of knowledge about (m)(')
Performance metrics We consider the expected number of infected nodes in a time horizon [o, T] as the performance measure for various policies. Let C²(T) be the number of infected nodes if there is no testing and isolation, (T),x(T), CREEr (T) be the corresponding numbers respectively for the RbEr policy (Algorithm 2 and the REEr policy (Algorithm 3/. We consider a ratio between the expectations of these:
E R (T) E|C
Ratio
(18)
[[C((T)
We define the estimalion ervor ErI,(() (1) towards capturing the impact of the lack of knowledge about (u, (4)).
(t)
1
Σ ((())=,(t)1B
(19)
N())
(EG())
We consider the difference between the estimation errors of RbEx and REEr policies: Aer Err R6 (T) Err (ETREE-(T) (T).
-
Benchmark policies We will compare the proposed policies with 4 benchmark policies. (i) (Forward) Contact Tracing: we tested every day the nodes who have infectious neighbors (in a forward manner), denoted by candidate nodes. Only some candidate nodes are selected randomly due to testing resources being limited. Note that only exploitation is utilized under this benchmark. (ii) Random Testing: Every day, we randomly select nodes to test. Typical testing policies that could come out of SIR optimal control formulations for our problem would naturally reduce to random testing as they treat all nodes to be statistically identical and ignore the impact of network topology. One can interpret that random testing implements exploration to its full extent. (iii) Contact Tracing with Active Case Finding: A small portion of (for example, 5%) testing budget is utilized for active case finding [BS] This portion of the testing budget is used to test nodes by Random Testing. The remaining budget utilized for forward contact tracing. (iv) Logistic Regression: We use ideas presented in [51,, where simple classifiers were proposed based on the features of real data. In our setting, we choose the classifier to be based on logistic regression, and we define the feature of node as (t) (t) + o Here, (1(()) is the number of quarantined neighbors node i has contacted before and inchuding day t, and é # 0 is a superparameter aiming to avoid the case where n1(t) = O. In simulations, we set e = 0.1. Let the observation (t) be the testing result of node i. In particular, if node is not tested on day t, then we do not collect the data (X,(t), (.))). Thus, the probability of node i being infectious is defined the Sigmoid function
1
1 + exp((X,,f)) w²)'
where w is the parameter which should be learned.
Simulation Setting We consider a process as described in Section 2 with no randomly located initial infected nodes. The process evolved without any iesting/intervention for l days and we refer to as the unregulated delay. After that, one of the (initial) infectious nodes, denoted by node ig, is (randomly) provided to the policies. Subsequently, the initial estimated probability vector is set to "r, (f) (1, 0, 0). and v,(4) = (0, 0, 0, 1) when i # ig. We consider the budget to be equal to the expected number of infected nodes at time t, i..., B(t) = Σ N(1) (t).
We choose model parameters considering the particular application of COVID-19 spread. In particular, 1) the mean latency period is 1/A 1 2 days [60]; 2) the mean duration in the infectious state (I) is 1/y= 7 ~ 14 days 566 57 58 ; 3) we choose the transmission rate 3 in a specific network such that after a long time horizon, if no testing and isolation policies were applied, then around 60 ~ 90 percent individuals are infected. We did not consider the case where 100 percent individuals are infected because given the recovery rate (and the topology), the spread may not reach every node.
We consider both synthotic networks such as Wttts-Strogatz (WS) networks 62 Scale-free (SF) networks 03 Stochastic Block Models (SBM) [ and a variant of it (V-SBM), as well as real-data networks. De- scriptions and further results for the synthetic networks and real networks are presented in Appendix M
15

---

Published in Transactions on Machine Learning Research (March/2022
Watts-Strogate Networks. We consider network WS(N, d, 6) with N nodes, degree d, and rewiring probability 6. The transmission probability of the spread is set to B = 0.4 and the number of initial seed is Ro 3.
Scale free Networks. We consider a network SF(N, with N nodes, and the fraction of nodes with degree & follows power law k where a = 2.1, 2.3, 2.5, 2.7, 2.9. The transmission probability of the spread is set to B = 0.5 and the number of initial seeds is vig = 3.
Stochastic Block Models. The SBM is a generative model for random graphs. The graph is divided into several communities, and subsets of nodes are characterized by being connected with particular edge densities. The intra-connection probability is Pl; and the inter-connection probability is p2. We denote the SBM as SBM(N, M, PI,
p2. 7 The transmission probability of the spread is set to == 0.04 and the number of initial seed is no 3. The construction of SBM given in Appendix M.1
A Variant of Stochastic Block Models. Different from SBM, we only allow nodes in cluster i to connect to nodes in successive clusters (the neighbor clusters). Denote a variant of SBM as V-SBM(N, M, pi, p2). The transmission probability of the spread is set to B = 0.04 and the number of initial seed no = 3. The construction of V-SBM is given in Appendix M.1
Real-data Network I. We consider a contact network of university students in the Copenhagen Networks Study 05 The network built based on the proximity between participating students recorded by smart- phones, at 5 minute resolution. According to the definition of close contact by [58], we only used proximity events between individuals that lasted more than 15 minutes to construct the daily contact network. The contact network has 672 individuals spanning 28 days. To guarantee long time-horizon, we replicate the contact network 4 times so that the time-horizon is 112 days. We set 3 = 0.05 and nip = 5 to have a realistic simulation of the Covid-19 spread. Note that the network is relatively dense, so we choose a relatively small value of B to avoid the unrealistic case in which the disease spreads very fast (see Figure I (left)).
Real-data Network II. We consider a publicly available dataset on human social interactions collected specifically for modeling infectious disease dynamics [6, 67 C8 The data set consists of pairwise distances between users of the BBC Pandemic Haslemere app over time. The contact network has 469 individuals spanning 576 days. Since the network is very sparse, then we compress contacts among individuals during 4 successive days to one day. Then, we have 469 individuals spanning 144 days. We set / = 0.95 and no 30 to have a realistic simulation of the Covid-19 spread. Note that the network is relatively sparse, we choose a relatively large value of / to avoid the unrealistic case in which the disease spreads very slow (see Figure (left)).
5.2 Simulation Results in Synthetic networks
In this section, we compare the performances of our proposed policies and the benckmarks (defined in Scction 5.1 in synthotic networks. We start with some specific networks and parameters for this purpose (see Figure 5 Figure 0 Figure 7 and Figure 8 The figures reveal that our proposed policies, i.e., the RbEx and REEr policies, outperform the benchmarks. In particular, in Figure 5 and Figure 0 (i.e., the WS and SF networks), the REEr policy outperforms the RbEx policy, and the REEr policy provides more accurate estimation for (t) In Figure 7 and Figure g (i.c., the SBM and V-SBM networks), the RbEx policy outperforms the REFr policy, and the RbEx policy provides a more accurate estimation for (z)( Tn addition, in Figure 5 we show that Algorithm [ outperforms the RbEx policy but performs worse than the REEr policy (recall that the compuation time of Algorithu 1 is high, we therefore only plot the performance of Algorithm D in Figure 3 as an example). This implies that without exploration, the exploitation in a greedy manner can not perform well in WS networks.
From the discussions above, the advantages of exploration in distinct settings (different network topologies with variant parameters) are different. To investigate the advantages of exploration in distinct settings, it suffices to show how the main parameters affect the exploration. In this work, we consider three main parameters which are defined in Section 5.1 i.e., the unregulated delay E, the global clustering coefficient Ye: and the lanh- T.p Detailed discussions are later given in Section 5.2.1
Here, we assume that M is an exact divisor of N.
16

---

Published in Transactions on Machine Learning Research (larch/202])
W8(300,4,0003)
WS(300,4,0003)
300
1.4
Algerihm RaEx polloy polley
1.2
250
Cumulaativ Infectons EIC(0))
Estimation Enar Emtl
0.8
150
0.8
100
No
0.4
Random Testing
Contact
Ragression
Finding
0.2
policy
Algoriinen
REEr polioy
0
50
100
150
0
50
100
150
Day
Day
Figure 5: Performances and estimation errors of different policies in WS(300, 4, 0.03) when & 3.
SF(300, 2.5)
SF(300, 2.5)
250
0.7
poicy REE: Ecplyy
0.6
200
Curulative Infodions E|C(0]
0.5
Estimatioon nnntiioo Erar Em(()
No lests
150
Random Testing
0.4
Contact tracing
Active Case Finding
Logiste Regress on
RbEx policy
0.3
100
REEr policy
0.2
0.1
0
0
20
40
60
100
20
40
60
100
Dey 1
Day
Figure 6: Performances and estimation errors of different policies in SF 2.5) when e 2=3 3.
17

---

Published in Transactions on Machine Learning Research (larch/202])
SBM/300, .2736,
SBM(300, .ww.6776..00
300
1.4
polcy REE/ poliyy
250
Testing tracing
1.2
Logistic Regression
Curuuaaivv Infecions EIC())
Active Case Finding
RbEx policy
REEr poley
Eslimation Erro Emr))
0.8
150
0.6
100
0.4
0.2
0
50
100
150
50
100
150
Day
Day
Figure 7: Performances and estimation errors different policies in SBM(300, 10, .2736, .02) when
VSBM(300, 10, .4184,
VSBM(300, 10, .4184,
300
poicy REE: pollcy
1.2
250
Cumulativv Infecions E(C(0)
tracing
Finding
Logistic Regression
Eslimation Erar Em[)
REEr polioy
RbEx policy
0.8
150
0.6
100
0.4
0.2
0
0-
50
100
150
50
100
Dey
Day
Figure 8: Performances and estimation errors of different policies in VSBM(300, 10, .4184, .02) when l
18

---

Published in Transactions on Machine Learning Research (March/200)
5.2.1 Impact of Network Parameters
In this subsection, we consider the impact of network parameters on the tradeoff between exploration and exploitation.
Impact of & We first investigate the impact of the unregulated delay, &. Specifically, from Table 2 Table 3 Table 4 and Table 5 as é increases, so does Ratio and Agrr, implying that exploration becomes more effective. With increase in f, the infection continues in the network for longer, there are greater number of infoctious nodes in the network and they are scattered throughout the network, thus exploration better suited locate them. Thus, the REEr policy can contain the spread of the disease faster.
In particular, the REEr policy always better in WS networks. This is because exploitation may confine the tests in neighborhoods some infected nodes. While the SBM networks, the RbEx policy always outperforms the REEr policy. In both the SF and V-SBM networks, the RbEx policy better when & is small, and the REEr policy is better when L is large. One interesting observation is that in the V-SBM networks, the REEr policy performs better when l is large (= 11, 13), but the corresponding estimation errors are larger than those in the RbEx policy. In this specific network topology, it appears that smaller estimation error does not always correspond to better cumulative infections. One potential reason is that the REEr policy ive to l in this lopology, i.e., we can achieve smaller cunulative infections under the REEr policy even the estimation error larger.
WS, l
3
11
Ratio
0.097
0.128
0.177
0.207
0.297
A Err
0.553
0.814
1.092
1.197
1.449
Table 2: Role of the unregulated delay when 8 = 0.03.
SF, {
3
5
7
11
Ratio
-0.0009
0.0026
0.0033
0.0042
0.0059
Ager
0.0014
0.0237
0.0334
0.0434
0.1212
Table 3: Role of the unregulated delay & when a = 2.1.
SBM, !
5
7
11
13
Ratio
-0.092
-0.079
-0.042
0.035
-0.025
Agrr
-0.026
-0.015
-0.010
0.009
-0.099
Table 4: Role of the unregulated delay L when (P1.P2) (.274.
V-SBM,
11
13
Ratio -0.022
-0.016
-0.007
0.011
0.019
Agrr -0.08
-0.066
0.006
-0.033
-0.25
Table 5: Role of the unregulated delay & when (p1.P2) = (.418,.02).
Impact of %e and Ly. Then, we investigate the impact the global clustering coefficient, i.e., Tex and the average shortest path-length, ie., Lp. Table 6 both Te and Lp decrease as å increases. In Table 7 % decreases increases. For the SF networks, the graphs are often disconnected, we only calculate % in Table In Table 8 and Table g both Yo and Lp docrease Pa increases.
From these tables, Lp or Te decreases, the benefits of exploration compared exploitation decrease well. This confirms the intuition that exploration is particularly helpful in clustered networks with larger path lengths where undetected infection can spread wothout any intervention exploitation largely confines the tests in neighborhoods of the infections that were previously detected. This is also supported by the
fact that exploration lowers estimation error in such scenarios, as shown in Table G Table 7 Table and
Table Furthermore, we investigate the role of % and Lp individually in Appendix M.2
19

---

Published in Transactions on Machine Learning Research (aarch2022))
WS, 8
1p
Ratio
Ågrr
62.876
0.191
1.153
.0075
.489
21.264
0.182
1.423
.015
.473
14.253
0.174
0.991
.0225
.467
12.171
0.126
0.779
.03
.456
10.81
0.097
0.554
Table 6: Role of clustoring coefficient and path length when l == 3.
SF
Y
Ratio
AET
2.1
.5017
0.0080
0.0334
2.3
.3344
0.0057
0.0253
2.5
.2348
0.0032
0.0177
2.7
.1496
0.0019
0.0124
2.9
.0219
-..004
0.0081
Table 7: Role of clustering coelficient and path length e = 3.
SBM, (P1, P2)
%
Lp
Ratio
Agrr
(0.274, 0.02)
0.111
2.573
-0.092
0.026
(0.214, 0.026)
0.075
2.518
-0.103
0.023
(0.159, 0.032)
0.056
2.492
-0.113
0.026
(0.102, 0.039)
0.048
2.480
-0.118
0.023
(0.045, 0.045)
0.043
2.455
-0.124
00.07
Table 8: Role of clustering coefficient and path length e 5.
V-SBM, P2)
Ye
Lp
Ratio
Aerr
(0.418, 0.020)
0.3557
4.4264
0.022
0.081
(0.351, 0.052)
0.2365
3.6584
0.091
0.045
(0.284, 0.085)
0.1769
3.307
0.104
0.055
(0.217, 0.085)
0.1385
3. 3.1562
0.112
0.041
(0.150, 0.0150)
0.1170
3.0563
-0.13
0.042
Table 9: Role of clustering coefficient and path length
Real-data Network T,
5
8
Ratio
-0.0559
-0.0255
0.009
AErr
-0.061
-0.030
0.035
Table 10: Role of the unregulated delay &
Real-data Network II, L
5
8
11
Ratio
0.0808
0.1099
0.1208
Agrr
0.0317
0.0535
0.0615
Table 11: Role of the unregulated delay &
20

---

Published in Transactions on Machine Learning Research (larch/202])
Real-data Network
Real-data Network
500
1.4
poicy REE poleyy
1.2
400
Cumulative Infecions E|C(!)
350
Testing
Logisde Regression
Estimation Error Emrl)
Contact tracing
300
Active Case Finding
RbEx policy
0.8
250
REEr polkoy
0.6
150
0.4
100
0.2
0
0
40
60
80
100
120
40
60
80
100
120
Day
Day
Figure Performances and estimation errors of different policies in the real-data network when
Real-data Network
Real-data Network
250
polcc REB polay
1.2
200
Cumulative Infeciions E|C(0]
Eolimation Erar Em!]
150
Contact
0.8
policy
100
Logiati Regrassion
REEr palky
0.6
0.4
0
0.2
50
100
150
0
50
100
150
Dey
Day
Figure 10: Performances and estimation errors of different policies the real-data network when E f= 8.
21

---

Published in Transactions on Machine Learning Research (March/2023)
500
Real-data Network|
Real-ddta Network
Average Edges per Node
Real-data Network
The Number of Companents
450
Real-data Network II
400
350
300
250
200
150
50
100
150
50
100
150
Day
Day t
Figure 11: Left: The average number of edges per node on each day. Right: The number of components on each day.
5.3 Simulation Results in Real-data Networks
In this section, we verify our proposed policies in real data networks (Real-data Network I and Real-data Network II). In Figure D our proposed policies outperform the baselines, and the RbEx policy outperforms the RREr policy. In Figure I0] the REEr policy can contain the spread and outperform other baselines and RbEx, while the Logistic Regression policies outperforms RbFx. Comparing Figure 9 and Figure 10 we find that the RbEx policy performs well in Real-data Network 1 (better than the REEr policy), but performs not well in Real-data Network II (much worse than the REEr policy). In Figure 11 (left), we calculate the average edges per node on every day, and in Figure 11 (right), we calculate the number of components on every day. From Figure II (left), the Real-data Network is denser than the Real-data Network I1. However, from Figure 11 (right), the Real-data Network II often has more components (subgraphs) than the Real- data Network I. Thus, exploitation may become confined within some components (subgraphs), and fail to locate infectious nodes elsewhere, and exploration becomes more effective in presence of large number of components. This explains the relative performances of REEr and RBEx in these. Contact tracing policy employs only exploitation, while active case finding policy uses most of its test budget for exploitation (and the small amount of the residual test budget for exploration). From Figure 9 and Figure [0] the contact tracing and the active case finding policies perform relatively poorly in the Real-data Network II compared to that in the Real-data Network I; this may again be attributed to the presence of a large nunber of components in the former.
As increases, as we show in Table 10 and Table 11 that the benefit of exploitation decreases. In Table because of large number of components, exploration always outperforms exploitation. However, in Table 10 observe that exploration outperforms exploitation only for larger values of t. Our results are thus consistent with synthetic networks.
6 Conclusions and Future Work
In this paper, we studied the problem of containing a spread process (e.g. an infectious disease such as COVID-19) through sequential testing and isolation. We modeled the spread process by a compartmental model that evolves in time and stochastically spreads over given contact network. Given daily test budget, we aimed to minimize the cunulative infections. Under mild conditions, proved that the problem can be cast as minimizing a supermodular function expressed in terms of nodes' probabilities of infection and proposed a greedy testing policy that attains a constant factor approximation ratio. We subsequently designed a computationally tractable reward-based policy that preforentially tasts nodes that have higher rewards, where the reward of a node is defined as the expected number of new infections it induces in the next time slot. We showed that this policy effectively minimizes an upper bound on the cumulative infections.
These policies, however, need knowledge about nodes' infection probabilities which are unknown and evolving. Thus, they have to be actively learned by testing. We discussed how testing has dual role in this problem:
22

---

Published in Transactions on Machine Learning Research (March/2023)
(i) identifying the infected nodes and isolating them in order to contain the spread, and (it) providing better estimates for the nodes' infection probabilities. We proved that this dual role of testing makes decision making more challenging. In particular, we showed that reward based policies that make decisions based on nodes' estimated infection probabílities can be arbitrarily sub-optimal while incorporating simple forms of exploration can boost. their performance by a constant factor. Motivated by this finding, we devised exploration policies that probabilistcally test nodes according to their rewards and numerically showed that when (i) the unregulated delay, (ii) the global clustering coefficient, or (iii) the average shortest path length increase, exploration becomes more beneficial as it provides better estimates of the nodes' probabilities of infection.
Given the history of observations, computing nodes' estimated probabilities of infection is itself a core challenge in our problem. We developed a message-passingg framework to estimate these probabilities utilizing the obsorvations in form of the test results. This framework passes messages back and forth in time to iteratively predict the probabilities in future and correct the errors in the estimates in prior time instants. This framework can also be of independent interest.
We showed novel tradeoffs between exploration and exploitation, different from the ones commonly observed in multi-armed bandit settings: (i) in our setting, the number of arms is time-variant and actions cannot be repeated; (ii) the tradcoffs in our setting are not due to lack of knowledge about the network or the process model, but rather due to lack of knowledge about the time-evolving unknown set of infected nodes.
We now describe directions for future research.
Our framework can be extended to incorporate delay and/or error in test results in a relatively straightforward manner (an outline of the extension incorporating delay is given in Appendix [], but generalizing the performance guarantees for the proposed policies in these cases forms a direction of future research. This includes establishing fundamental lower bounds using genic-aided myopic policies.
6.1 Impact Statements
We have made several assumptions for the purpose of analytical and computational tractability which do not hold in practice: (1) the infections from different nodes are independent (2) given the entire history of testing results the states of nodes on the truncation day are independent (Assumption D (3) the symptoms need not be considered in deciding who should be tested and (4) the public health authority knows the entire network topology and uses it to determine who should be lested (5) independence of states of nodes (in one step). The first two assumptions were used to derive the message passing framework and to prove that the objective function super-modular which in turn led to a myopic testing strategy which is also optimal. The first assumption is reasonable as specific actions of infected individuals, eg, coughing, touching, spread the infection, which are undertaken independently.
We now consider the second assumption, ie, Assumption 1 in which we assune that the nodes' states ((1- g) (in the posterior probability space on day t t-g) g) are independent. Note that g is the truncation time for each backward step, that is, once we get the obscrvations Y(t), we do the backward step and truncate at time - g. This assumption does not impose independence on the state of the nodes, but only in the posterior space at a specific time. That is, in the process of propagating information back to time t - 9, we are assuming that there is no further correlation between time - g --1 and time t- g worthwhile to exploit given observations at time t. Naturally, as g gets larger and larger, our framework and calculations become more precise, the impact of the testing results at time / in inferring about the nodes' probabilities at time --g vanishes 9 gets large. But increase in g significantly increases the computation time. Therefore, for computational tractability, of the backward update equations, we use g = 1. In principle the derivations of the backward update equations can be generalized in a straightforward manner to > 1. But designing approximation strategies that ensure computational tractability for larger g constitutes a direction of future rescarch.
Consider the third assumption. We have not considered symptoms in determining who to test. But for some infectious discases, symptoms are a reliable manifostation of the discase (c.g., Ebola). In principle our testing framework can be generalized in a straightforward manner to consider symptoms by introducing additional states in the compartmental model for evolution of the disease. But introduction of additional
23

---

Published in Transactions on Machine Learning Research (March/202)
states significantly increases the computation time, for example of the forward and backward updates of the probabilities that individuals have the disease, which renders implementation of our framework challenging. Considering symptoms while retaining computational tractability constitutes a direction of future research.
Next, consider the fourth assumption. In practice, public health authoritics will not typically know contact networks in their entirety particularly when they are large, for example, as in large cities. However, small network topologies, for example, contact networks within community, may be observed by the public health authority. As specific example, the Government of China fully detected contact networks in many communities in Wuhan and tracked paths traversed by every individual 69 This tracking may also generate concerns about privacy which is beyond the scope of this paper. Nonetheless, the technology for lcarning contact networks in their entirety for small communities exists and our framework can be utilized for those. Generalizing our framework to obtain approximation guarantees when contact networks can only be partially observed constitutes a direction of future rescarch.
Finally consider the last assumption. Note that it is strong assumption and clearly does not hold in general but it has been resorted to for only step in the entire framework. Specifically to obtain Equation (5) we have assumed that the state of the nodes are independent. This allows us to obtain simple expression in 5 in terms of the infection probabilities. We do not use this independence assumption in the rest of the paper.
Acknowledgments
This work was supported by NSF CAREER Award 2047482, NSF Award 1909186, NSF Award 1910594, and NSF Award 2008284.
References
[1] B. Shulgin, L. Stone and Z. Agur. Pulse vaccination stralegy in the SIR epidemic model. Bulletin of Mathematical Biology, 60:1123 - 1148, 1998.
[2] P. Tapaswi and J. Chattopadhyay. Global stability results of a succeptible-iffeetie--mme susceptible" (STRS) epidemic model. Ecological Modelling, 87(223 226), 1996.
(3] L.Stone, B.Shulgin and Z.Agur. Theoretical examination of the pulse vaccination policy in the SIR epidemic model. Mothematical and Computer Modelling, 31:207 215, 2000.
[4] Y. Takeuchi, W. Ma and E. Beretta. Global asymptotic properties of delay SIR epidemic model with finite incubation times. Nonlinear Analysis: Theory, Methods & Applications, 42:931 947, 2000.
5 J. Aron. Acquired immunity dependent upon exposure in SIRS epidemic model. Mathematical Biosciences, 88:37 - 47, 1988.
6 I. Allen. Some discrete-time SI, SIR, and STS epidemic models. Mathemalical Biosciences, 124:83 105, 1994.
77] A. M. Ramos, M. R. Ferrandez, M. Vela-Peree and et al. simple but complex enough 0-SIR type model to be used with COVID-19 real data. Application to the case of Italy. Physica D, 421-132839, 2021.
[8] A. G. M. Neves and G. Guerrero. Predicting the evolution of the COVID-19 epidemic with the A-SIR model: Lombardy, Italy and Sao Paulo state, Brazil. Physica D, 413- 132693,,,, 2020.
99] A. Simha, R. Prasad and S. Narayana. A simple Stochastic SIR model for COVID-19 Infection Dynamics for Karnataka after interventions Learning from Europcan Trends. arXiv: 2003.11920, 2020.
100 B. Ndiaye, L. Tendeng and D. Seck. Analysis of the COVID-19 pandemic by STR model and machine learning technics for forecasting. arXiv: 2004.01574, 2020.
[11] J. Zhu, P. Ge, C. Jiang and et al. leep-igg artificial intelligence analysis of clinical variables predicts mortality in COVID-19 patients. Journal of the American College of Emergency Physicions Open, 1(6):1364-133 13733, 2020.
24

---

Published in Transactions on Machine Learning Research (March /2023)
[12] C. Mahanty, R. Kumar, B. K. Mishra, and et al. Prediction of COVID-19 active cases using exponential and non-linear growth models. Expert Systems, 39(3), 2020.
[13] E. B. Postnikov. Estimation of COVID-19 dynamics "on a back-of-envelope". Does the simplest SIR model provide quantitative parameters and predictions? Chaos, Solitons and Fractals, volume 135- 109841, 2020.
[14] B. Ndiayo, L. Tendeng and D. Seck. Comparative prodiction of confirmed cases with COVID-19 pan- demic by machine learning, deterministic and stochastic SIR models. arXiv: 2004.13489, 2020.
[15] I. Rahimi, A. H. Gandomi, P. G. Asteris and et al. Analysis and Prediction of COVID-19 Using SIR, SEIQR, and Machine Learning Models: Australia, Italy, and UK Cases. Information, 12(109), 2021.
[66 G. Hu and J. Geng. Heterogeneity learning for SIRS model: an application to the COVID-19. Stalistics and Its Interface, 14:73 81, 2021.
[17] R. Vega, L. Flores and R. Greiner. SIMLR: Machine Learning inside the SIR Model for COVID-19 Forccasting. Forecasting, 4(1):72 - 94, 2022.
188] H. Bastani, K. Drakopoulos, V. Gupta and et al. Efficient and targeted COVID-19 border testing via reinforcement learning. Nature, 599:108 113, 2021.
[19] S. A. Alanazi, M. M. Kamruzzaman, M. Alruwaili and et al. Measuring and Preventing COVID-19 Using the SIR Model and Machine Learning in Smart Health Care. Journal of Healthoure Engineering, 2020-8857346, 2020.
[20] G. Perakis, D. Singhvi, O. S. Lami, and et al. COVID-19: A multiwave SIR-based model for learning waves. Production and Operations Management, (13681), 2022.
[21] S. Chowdhury, S. Roychowdhury and I. Chaudhuri. Universality and herd immunity threshold Revis- iting the SIR model for COVID-19. International Journal of Modern Physics C, 36),, 2021.
[2]] W. Choi and E. Shim. Optimal strategies for social distancing and testing to control COVID-19. Journal of Theoretical Biology, 512(11)5 2021.
[23] D. Acemoglu, A. Pallah, A. Giometto and et al. Optimal adaptive testing for epidemic control: combining molecular and serology tests. 1:7777 2021.
[24] L. Abraham, G. Becigneul and B. Scholkopf. Crackovid: Optimizing Group Testing, arXiv:2005.06413, 2020.
[25) C. Tsay, F. Lejarza, M. Stadtherr and et al. Modeling, state estimation, and optimal control for the US COVID-19 outbreak. Scientific reports, 10(10711), 2020.
[26] F. Piguillem and L. Shi. Optimal COVID-19 quarantine and testing policies. Nature Communications, 12(356), 2021.
[27] M. Tanaka K. Kuga and Tanimoto. Pair approximation model for the vaccination game: predicting the dynamic process of epidemic spread and individual actions against contagion. Proceedings of the Royal Society A, (77(224 20000066,, 2021.
[28] K. Kuga K. Kabir and J. Tanimoto. The impact of information spreading on epidemic vaccination game dynamics in a heterogeneous complex network-a theoretical approach. Chaos, Solitons & Fractals, 132:109548, 2020.
[29] K. Kabir and J. Tanimoto. Evolutionary vaccination game approach in metapopulation migration model with information spreading on different graphs. Chaos, Solitons & Fractals, 120:41-55, 2019.
300 L. Willem, S. Abrams, P. J. K. Libin and et al. The impact of contact tracing and household bubbles on deconfinement strategies for COVID-19. Nature Communications, 12(1524), 2021.
25

---

Published in Transactions on Machine Learning Research (March/20P)
[31] J. Kim, X. Chen, H. Nikpey and et al. Tracing and testing multiple generations of contacts to COVID-19 cases:
cost-benefit tradeofIs. Royal Sociely Open Science, 9(10):1 - 20, 2022.
[32] A. Aleta, D. Mlartin-Corral A. Piontti and et al. Modelling the impact of testing, contact tracing and houschold quarantine on second waves of COVID-19. Nature Human Behaviour, 4:964-971, 2020.
[33] J. Hellewell, S. Abbott, A. Gimma and et al. Fcasibility of controlling COVID-19 outbreaks by isolation of cases and contacts. The Lancel Global Health, 8(4); 2020.
[34] A. Kucharski, P. Klepac, A. Conlan and et al. Effectiveness of isolation, testing, contact tracing, and physical distancing on reducing transmission of SARS-CoV.L in different settings: mathematical modelling study. The Lancet Infectious Diseases, 20(10), 2020.
355 S. Kojaku, L. Hebert-Dufresne, E. Mones, and et al. The effectiveness of backward contact tracing in networks. Nature Physics, 17:652 658, 2021.
(36] A. J. Kucharski, J. K. Conlan, S. M. Kissler, etc. Effectiveness isolation, testing, contact tracing, and physical distancing on roducing transmission of SARS-CoV-2 in different scttings: a mathematical modelling study. The Lancel Infectious Disenses, 20(10):1151 1160, 2020.
377 A. Perrault, M. Charpignon, J. Gruber, etc. Designing Efficient Contact Tracing Through Quarantining. Working Paper, National Bureau of Economic Research, Nov. 2020.
[38] H. Ou, A. Sinha, S. Suen, etc. Who and when to screen: Multi-round active screening for network recurrent infectious diseases under uncertainly. In Proceedings of 19th International Conference Autonomous Agents and Multiagent Systems (AAMAS), 2020.
[39] P. Auer, N. Cesa- Bianchi and Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47:235-256, 2002.
[40] Agrawal and Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 1-26, 2012.
[41] S. Agrawal and N. Goyal. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
[42] K. Madhana and T. Murata. A multi-armed bandit approch for exploring partially observed networks. Applied Network Science, 4(26):1-18, 2019.
[43] M. Bilgic, L. Mihalkova and L. Getoor. Active learning for networked data. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 79 86, 2010.
[44] X. Wang and R. Garnett and J. Schneider. Active search on graphs. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 731-738, 2013.
[45] Y. Ma and T. K. Huang and Schneider. Active search and bandits on graphs using sigma-optimalitt In Proceedings of the Thirty-First Conference on Uncertainly in Artificial Intelligence, pages 542 551, 2015.
[46] R. Garnett, Y. Krishnamurthy, D. Wang and et al. Bayesian optimal active search on graphs. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 843-858 83--550,44 2011.
[47] D. Zhao, J. Liu, R. Wu and et al. Data- Eaficefficient Reinforcement Learning Using Active Exploration Mothod. In International Conference on Neural Information Processing, pages 263-276, 2018.
48] Y. Burda, H. Edwards, A. Storkey and et al. Exploration by random network distillation. In Interna- lional Conference on Learning Representations, 2019.
26

---

Published in Transactions on Machine Learning Research MMarch/2023)
[99] M. Bellemare, S.Srinivasan, G. Ostrovski and et al. Unifying count-based exploration and intrinsic motivation. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1479 1487,48777-- 2016.
[0] R. Singh, F. Liu and N. Shroff. A Partially Observable MDP Approach for Sequential Testing for Infectious Discases such COVID-19. arXiv:2007.13023 2020.
[51] H. Grushka-Cohen Cohen, R. Cohen, B. Shapira and et al. A framework for optimizing COVID-19 testing policy using a Multi Armed Bandit approach. ar arXiv:2007. 14805, 2020.
[2] E. Meirom, H. Maron, S. Mannor, and G. Chechik. Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks. In Proceedings of the 38th International Conference on Machine Learning, number 139, pages 7565 7577, 2021.
[3] L. Kaclbling and M. Littman and A. Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99-13) 134, 1998.
[54] G. Monahan. State of the Art-A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms. Management Science, 28(1):1-16, 1982.
[55] G. Walter and M. Contreras. Compartmental Modeling with Networks. Birkhauser, Boston, MA, 1999.
[6]] S. Ma, J. Zhang, M. Zeng and al. Epidemiological parameters of coronavirus disease 2019: pooled analysis of publicly reported individual data of 1155 cases from seven countries. medRxiv: 1tt.://orrg/...111///1/11
21............2.... Feb 2020.
[7] A. Byrne, D. McEvoy, A. Collins and et al. Inferred duration of infectious period of SARS-CoV-2. rapid scoping review and analysis of available evidence for asymptomatic and symptomatic COVID-19 cases. BMJ Open, 10, 2020.
[8] CDC.
The U.S. Centers for Disease Control and Prevention (CDC). https://wwe wwtp:/pwwwwpp///wo//tppwppptpppp coooonaiirus/01991a. /php/ http///atatttaarinnggeeeeee// tracing.html, Sept 2020.
contact-
[9] D. Topkis. Supermodularity and Complementarity, Princcton University Press, 1998.
[60] V. nevv. An approximation guarantec of the greedy descent algorithm for minimizing supermodular set function. Discrete Applied Mathemalics, 114:131 146, 2001.
[6]] D. L. Hansen, B. Shneiderman, M. A. Smith and et al. Analyzing Social Media Networks with NodeXL (Second Edition). Morgan Kaufmann, 2020.
[62] D. J. Watts and H. Strogatz. Collective dynamics of world networks. Nature, 393(4):440 442, 1998.
[63] A. D. Broido and A. Clauset. Scale-free networks are rare. Nature Communications, 10(1017):1 - 10,
2019.
[64] C. Lee and D. J. Wilkinson. review of stochastic block models and extensions for graph clustering. Applied Network Science, 4(122), 2019.
(55 P. Sapiezynski, A. Stopezynski, D. D. Lassen and et al. Interaction data from the Copenhagen Networks Study. Scientific Data, 6(1):1 10, 2019.
[66] S. M. Kissler, P. Klepac, M. Tang, etc. Sparking "The BBC Four Pandemic": Leveraging citizen science and mobile phones to model the spread of discase. bioRxiv
2018.
[67] P. Klepac, S. Kissler and Gog. Contagion! The BBC Four Pandemic the model behind the documentary. Epidemics, 24:49 59, 2018.
27

---

Published in Transactions on Machine Learning Research MMachh2022,
[68] J. A. Firth, J. Hellewell, P. Klepac, etc. Using real-world network to model localized COVID-19 control strategies. Noture Medicine, 26:1616 1622, 2020.
[69] X. Yu and N. Li. How Did Chinese Government Implement Unconventional Measures Against COVID-19 Pneumonia. Risk Manag Healthe Policy, 13:491 499, 2020.
[70] R. D. Shachter. Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisitc Informa- Lion in Belief Networks and Influence Diagrams). arXiv: 1301.7412, 2013.
[71] M. Jordan. An Introduction to Probabilistic Graphical Models. https///poppl..ee..beeeeeeee jor- dan Sam/prelims, 2003.
A Proof of Lemma 1
Note that a node is counted in (t) once it has been infected. Then, on day t 1, (² + 1) increases (comparing to C" (t)) only because some susceptible nodes are infected by infectious nodes and are in the latent state for the first time.
After testing, positive nodes in (t) would not infect others because they are quarantined, and negative nodes would not infect others due to the model assumptions. Hence
C (1 1(++))=C((0) - E ((M())C(0)))))
(EV())
Taking the expectation on both sides, we obtain the desired result.
Proof of Theorem
To show (f) defined in is a supermodular function. It suffices show that for any A B c V(t), and for V())BB, have
S(AU(a):t) - ((B s(:t).
(20)
Then, it suffices show for any i Vtt),
(AU EEB [ (B))
(21)
Now, we consider three cases.
Case 1. If Ana 13 (t),,, then from the LHS and RHS in 21 are exactly the same. Hence, (1 holds.
Case 2. If At) C (t), and & 0 then from 5 f(AAU {z}) f((A) and f. U (x}) f.()).
Hence 21 holds.
Case 3. If Af c Bna((), and x E at),), let y (Bna())) Here x $ y. From 5 wo
can compute
E (=) -((((AA))
= (1)
II (1-Bo("(1))
(EL
x X1-
II
(1 (-B3o(((t) (1 - (0-
II (1- (of
jE8.(ON(AU(E))
JE8,0OAA
28

---

Published in Transactions on Machine Learning Research (larch/2023)
which implies
(t)
II
(1- (t)
(EAU(O)))((E))
(307 (1)
II
(1- (0-3
II
(1 Buy BuBP(()))
jE8(CON(A(())
(EOU())((AUE)))
(1) (1)
II
(1- (u Bo7)
-gg
(EOLO)((A(EO)
Similarly, note that (B) = (An uy. We have
EI (x);0) -E[[((())
=0 = (t)
II
(1- (f)
Thus,
E (A -EE(A
II (1 Bof 1 y
E E
which implies S(TP" (t) is supmodular.
To show (t)) is an increasing monotone function (t), it suffices to show (IC)(()) is increasing monotone function on (t) for any i.
For A C B, we have (B c V,()) and Ana(()
Then
II (1 (1- N (E)V
II JEa.INAA
(1 (o)
II (1- (1-)ot0(0)) S JEBN8.())
II (1- (t)
jEAna.()
and thus, from we have (AF(( s B. (B:1))
C Complexity of Algorithm 1
First of all, consider the complexity of 5 Suppose (u(())vv is given for every day t. For any K (T((),, the complexity of computing (5) is
+ 1F000000000001110000000000000010
2(a,
Then, for any (t), the complexity of computing (()C((t):) is
Σ (0)(1).
JEV())
From Algorithm in step i, the complexity is
(N(t) - i+ 2 Σ (0,(1).
jEV())
And in lotal we have (N(1) (1)) steps, therefore, on day L the complexity of Algorithm is
(()
2(N(t) 1i+1 Σ 10,(1).
JEV())
29

---

Published in Transactions on Machine Learning Research MMrch/2025
Recall that the time horizon is T, then the total complexity of Algorithm |
is
T-1 N(C (C)
Σ
Σ
2(N(1)ii+)
Σ (0)(1))
JEV(()
Note that
((0))11701
Σ
2(N(1) -(-1) 50(N((()))))
Σ |a.(1) SO()(())
IEV())
Then, the total complexity is bounded by
0 Σ (t))
D Proof of Lemma 2
As defined in 60 (an equivalent definition of footnote 3), consider finite set 1, : R is supermodular function if for all X,Y I,
f(X f(X)
(22)
Following the supermodularity of function S(-) as shown in Theorem set X V(t)(T(() and Y KCT
in 22 we have
((V(I)(((O)) < S(V()))) (1))))
(23)
Again, set. X = (OV(() and Y = (i} in 22 and use
22
repeatedly to obtain:
((K)(1);
Σ s(():t) Σ rt())
(24)
(EX
(EK
Substituting 24b in 23
we obtain
S(VOIVT():) & S(V():))
Σ ri(1)-
(EXT(()
E Local Transition Equations
In this section, we will describe the local transition matrix P. (((L)((t)) (e)) used in 112 The state of each node evolves as follows: (i) if node is susceptible on day t, then it might be infected by its neighbors in X, and changes state to the infectious state (I) with probability X; (iv) if node i is in state I, it will recover after geometric distribution with parameter y. Let (t) = - IImea, (1-u (1)))) In particular, define (t) = a,(t) = Ø. Then, the probabilitics of nodes being different states evolve in time as follows:
d,(t); (ii) an infectious node remains in the latent state with probability
= (0) - 7) + (f)
(25)
" (0)11 (1E(()
(26)
0 (1+11) (1)
(27)
()(())(())
(28)
30

---

Published in Transactions on Machine Learning Research March/2023)
Note that row vector (t) is defined in matrix as given below:
3
Collecting
25
28
define the local transition probability
(1
(1-?)
7
1-
0
0
P. )((02(())))0011)
(29)
0
(x(t)
0
1
-
(,(t)
and we obtain 12
F Proofs of 13 and (14)
First of all, we give the following definition.
Definition Let X be random variable and B be an event. Define X|s as the random variable X given
B; i.e.,
Pr (Xls = x) Pr (x ==
(30)
For brevity, let us define
(,(t) (f0()))))) (((t) = (((t))
We thus have
(t) = Pr (f)(t)= = z), (f) = Pr (si(t) = z²)
Recall that
- xex" (t) Pr (a,(t) = x).
Then,
12
can be re-wrilten as
Pr =)) (1,) (=)))eot
(31)
where vr,, (mg))eeat() E X. Conditioning both sides of 31 (Y(r))== state variables (1))) and oz(l in 31 can be replaced by (1) and (( 1), respectivell, to obtain
4 (1) (t (t 1) P. (Lw, ())
(32)
which gives
13 In addition, define
=.())=;(()) (2
and
e 1) (1- E
(33)
di 1) = Pr (0:(1 - 1) = x).
This notation implics
di 1) 0:(t 1)lx
(34)
Similarly, conditioning both sides of 132 on (()), we find
(t) = Ct 1) P, (Le, 1)a (--));
(35)
which gives 14
Pi(te, 1)} ()) is obtained in the following subsection.
31

---

Published in Transactions on Machine Learning Research (larch/2023)
F.1 Computing the transition probability matrix Pt(te,(t se0
Note that ((te,(t-1)) (t-1)) is not the same as (.(lm,(t)) (4)) This is becouse "future" observations we split the nodes V(t) into two classes of nodes: (i) nodes who do not get new observations and (ii) nodes who gel new observations. Pille,(t 1)) sea! (1-1)) is obtained by the following rules. For the first class of nodes, the local transition matrix in (35, i.e., P( (t-)))))))))))
were available in Pi(le,(t 1))
((tle)(t-)),eeftcce ((-()))))) To get (
the same as that in (32). However, for the second class of nodes, the local transition matrices are changed accordingly because of the new observations. Let [A] be the 7th row of matrix A, and gi be a 1 x 4 vector with the 7th element being one and the rest zero. For brevity, denote the local transition matrices in 32 and 35 by Pt ((f--) and Pt (ift-1] 1), respectively. We have the following three cases:
(i) If node i is not observed, then node does not have new observation and we have
P () 1) = Pt(t
(36)
(ii) If (()) = 0, then node i is not infectious in day t with probability 1. The local transition matrix is changed to
93
j=1
Pt 1)4
92 [P - ())
j --2 otherwisc
(37)
(ii) If Y:(1) = 1, then node is infectious in day with probability 1. The local transition matrix is changed to
41
j=
Pt(t 1)3
91
j j= 1)) otherwise
(38)
[P,(t
G Proofs of (16) and 17
Using new observations, we aim move backward in time and update belief (posterior probability) in previous lime slots. Define a trancation number y and suppose that (Y(()) affects the posterior probabilities from day t to day t We call day t t-g 9 the truncation day associated with day t. To get accurate posterior probabilitics in every day, we need to set = on every day t and track back to the initial time. However, the influence weakens as time elapses backwards, and for computation tractability, we continue under the following assumption where g = 1. Recall that (1) = o; (1) ky()s-
On the truncation day (t - 9), (t:(t g)}r independent over i. In the following, the truncation number is assumed to be g =1
Assumption 1.
Remark 3. In Assumption 1 we assume that the nodes' states ((t-g) g) (in the posterior probobility space on day 1- g) are independent. This assumption is only used at time of our probability updale in a moving window kind of way. It provides us with a truncation time for each backward step. In particular, under Assumption 1 once we get the observations Y(t), we do the backward step and truncate at time t- 9- For example, in the trivial case of o tt, the assumption holds. This assumption does not impose independence the state of the nodes, but only in the posterior space at specific time. In sense, in the process of propagating information back to time t- 9, t- 3- - and time t - 9 worthwhile to exploit given observations at time t. Naturally, as g gets larger and larger, our framework and calculations become more precise but this comes al a huge compulational cost. The idea behind truncating the backward step lies in the observation that the impact of the testing results time in inferring about the nodes' probabilities at time g vanishes as g gets large. For simplicity of derivations and to have manageable complezity, we set g == The idea and the derivations can be generalized in straightforward manner to larger g-
ossuming that there is no further correlation between time
32

---

Published in Transactions on Machine Learning Research (March/200)
Note that the posterior probabilities day t 1, w,(t 1), i E V(t 1), assumed known (and are conditioned on the history of observations (Y(r))==1) The probability vector (t is the new posterior probability at time t -- 1 which is updated (from (t- - 1)) based on new observations (t).. In other words, we infer about the previous state of the nodes given new observations at present time.
To obtain (w, kEv)o, it suffices to obtain (t and the corresponding local transition matrix (1 je (t-1),, see 14h. Note that the posterior probabilities me,(1 1), i E V( 1), which are calculated based on (( 1), are known. The vector e 1) is the new posterior probability which updated based (t) and (t 1).
Equation 16 which we aim to prove, simply follows from Definition
1
33
and Bayes rule
( P =x)=)))))) = (r( - 1) w (t-1)
(39)
Pr (Y(())
To find Pr (L()) -- -1) = =)), and establish
we now proceed as follows. We introduce (0,(0)
into
13 In particular, we have
Pr 11) 0,(,) JEO(()
E
Pr (10,0))) X() 1)
By the chain rule of conditional probability,
Pr (Y(t))sit =x)
Σ
Pr (0( =x) x Pr (105(0eeoolli( = x).
85(t), JEO())
(t)(t)) and (e)())) are variables defined by (ay(t))iev()) in posterior spaces of From 15
(Y(T)) 7=1 and [Y(T))==) respectively. Since Y(t) is deterministic function of (oy(t))seo()) and hence then Y(t) is independent of G(t - given (0)(())) In addition, the testing result Y₃()) (on day t) of node j only depends on its state, i.e., given (t), the testing results are determined. Therefore, we have
Pr (K))), Ci(t -1) =
=x)= = Pr (0)ee)))))))))) = II Pr (X)()))))))
jEO(()
The product above is an indicator which takes values on {0, 13. We can thus we-trite it as follows:
Pr (X())(0)())))m)) Ci(t - 1) = =) e (()(())))()))ss)))
where
((Y,(())),,()))beo)))))
if the pairs (t))))) consistent, and
(()3(())),)0)))so))
otherwise.
Next, define
O,(t) (ilj E (t
to represent the neighbors (in day - 1) of nodes in O(t) excluding node i. Then,
Pr (100(0)))00))) = =x) Σ
Pr (r(((())) (G(t-1) (((t=1))ee.olli(( x).
(40)
((-1)), 1E0,())
33

---

Published in Transactions on Machine Learning Research (March/2023)
By the chain rule of conditional probability,
Pr (10,(()) -1c 1)=
Σ Pr (00(000))sselll(((())eeeeo..oo (E0,()
=x) x Pr (r(GG(-1))ea =x).
Given (Gil - (G((L1))lee.)) 1e) U (cil - 1)), (0/(0)) are independent. We thus have
Pr
= x)
II Pr (0,(t))(Gi(t (e(()llG(tt-D)eeoooneeee Cilt 1) = z)
JEO())
Pr Pr(0(00(((((--)))))))))))- jEO())
= x.).
Based on Assumption
Pr 1eeett--))eeeiitttt 1) =2) II Pr (G((t-11
lE(O.(0)
Therefore,
Pr (Y -
Σ (1)))(t),,((t))3eo))
8,00, jEO())
(41)
II Pr (0j ( jEO(()
Σ
(1)) =)
II (E(((())
Pr (G(( 1)).
Denote (2, (eo)) as a realization of (f)(t)) and (uhee.00 as a realization {(i(t - 1)) Then,
Pr Pr((())) - 1)=
Σ (() (asbeo
x
Σ
II
Pr (c -(-- 1) x II (E(0.()))
Pr - 1) = v1).
(vr (1)
Denote
p((x,))Eow,
Σ
II
Pr (eylluhhe =
II Pr (G(t 1) v1). IEB(())
(42)
(wheero SEO(()
Then,
Pr (Y(t) =)= x))
Σ ((1330)-=)hooog))((e))ex))
(43)
JEEX)
Consider node i, Y(t) can be split into y,) and (!), where (!) is the observations of the set (() (1-1), and ()) the observations of the rest of the nodes. Note that (t) U UY,,)) (t)) ((t) and (t) = Ø.
Based on Assumption 1 we can further simplify 433
Lemma 3. Conditioned on (t), Ce(t 1) is independent of (t)
Proof. To show Lemma 3 we use the structured belief network as defined in 77 ()(t) is the random variable associated with node j. Note that (t) the test result of (t) on day t. Now, we consider (O(t))(O(t) n at - 1))). By 770 Theorems 1] and Bayes ball algorithm defined in 7I] Section 2), we investigate the following cases.
34

---

Published in Transactions on Machine Learning Research (larch/2023)
(i) For any j E (OO)))(O(() n (t 1))) with Y,(t) = 1, the corresponding state (y(t) is determined (which is l). Then, probabilities conditioning on (2) is equivalent to (equal to) probabilities conditioning on (t).. By Bayes ball algorithm 71, the information (the ball) is blocked at ()(t) when the information (the ball) reaches (tt),, which implics the information (the ball) can not reach C1(1 1).
(ii) For any j E (O())((E)) n (t with (t(1) O, (,(t) is not determined. By Bayes ball algorithm 70 7i, when the information (the ball) reaches (,)), can traverse Y,(() when blocking Y,(t)- However, by Assumption 1 ((t- and Gj(t 1) are independent, any path between (z(t-1) 1) and ((t 1) is blocked, including the path ((t- - 1) + (i(t) (t ++
(t) (conditioning
(t) + Ci(t 1). Thus, the information (the ball) can not reach Çe(t - 1).
A simple example is given in Figure independent (i - 1).
12
Let (1()) 0 and Y2(t) 1. Given (t) and 12(t), Ys(t) is
Assumption
Yit0
Y.U
G(--1 1)
9,69
Y200
G(l
4,00
G 1)
600
Figure 12: Bayes ball algorithm in the network of 3 nodes. The terms on which we have conditioning are shaded gray and are equivalently blocked.
From Lemma 3
xx(((t)) Pr (ci(t- - xf)..(()).
(44)
We simplify
44 denote the observations of nodes in a (1 1) ()) is independent of (i( 1). Denote (t) O(t) not (t (t-1). Then, We can replace O(t) by
43
based Lemma 44
From
Ya! (t), Y.
(t)
16
Subsequently, denote (t) = (ilj E at (t 1), E (.(())((),, and we can replace +t))) by
(1()) in 40
Thus, from (22 and
43 we respectively have
( ((0g))ew.(0))))
Σ
II
Pr (cy]kuhhee -(t-1)(++))) x) x II (EO,())
Pr (Gi(t - 1) vi) (45)
(wlheege JEV((()
and
Pr ((Y30))e..l((((111)--
Σ
(46)
which give the desired result
17
35

---

Published in Transactions on Machine Learning Research (larch/202])
9/-1 1)
6
Node
ogC-
Ojit
Node
(t- da
1 day
Figure 13: The original graph (left). The graphical model of states and observations (right)
A Simple Example for Algorithm
In this section, give a simple example to illustrate the idcas and steps of Algorithm Besides, compare our proposed algorithm (Algorithm 4 with the Naive approach discussed in Remark 2 Consider simple network with three nodes. Node has an edge with node 2, node 2 has an edge with node 3 (see Fig Nodes 1 and 3 are symmetric and statistically identical, and node 2 has higher degree.
the initial day (day 0), assume that nodes and susceptible, and node 2 is infectious. On day 1, let node 2 be tested. Recall that define the posterior probability vectors at the end of every day, and the prior probability vectors at the beginning of every day. Nodes' states change in the beginning every day and testing is also done in the beginning of every day. Let the initial belief, i.., the posterior probability w. (0) and the prior probability u, (0) on day 0, of the nodes
Consider the following situation:
m7 (0) (1/3,0,022/3,
i= 1,2,3
(0) = [13,,0,,2//3]
i= 1, 2,
Day 0: No tests day the prior probabilities updated by the forward step (Step 2 in Algorithm 4
Day 1: By Step 2 in Algorithm
we have
2 (1) [0.3144, 0.0373, 0.0633, 0.5849)
22(1) [0.3559, 0.0676, 0.0633, 0.5131]
Ug (1) = [0.3144, 0.0373, 0.0633, 0.5849).
After testing node 2, we know that node 2 is positive. use the test result to infer about the state of the nodes in prior times. particular, we update the posterior probability on day (w,(0)). Denoting the updated posterior probability as g, (0), by Step in Algorithm we find
(0) = [0.3144, 0.0373, 0.0633, 0.5849]
(0) [0.9615, 0.0385, 0.0, 0.0.0.0)
(0) = [0.3144, 0.0373, 0.0633, 0.5849).
We say that the end of day 0, node 2 was infectious with probability 0.9615 and it was in the latent state with probability 0.0385. Moreover, and 3 on day have increased since they may have infected node 2 on day 0, i.e. 0.3517 = e (0) +e (0) (0) 1 (0) with 1,3. Next, we obtain the posterior probability on day 1. Recall that w. (1)
that the (posterior) infection probabilities of nodes 1
1/3 (0) ff
36

---

Published in Transactions on Machine Learning Research MMrchh2022,
describes the posterior probability vector of node i at the end of day t. By Step in Algorithm
Wi (1) [0.4008, 0.0, w.w.....2...... 0.4724]
"2 (1) = [0.90, 0.0,0.10,0,. 0.0]
W3 (1) = [0.4008, 0.0, 0. 0.12 0.4724].
One may wonder why the posterior probability is [0.9, 0.1, rather than 0,, This is because testing is done in the beginning of time and the posterior probabilities are defined the end of time slots t. The infected node may have recovered by the end of time = 1 and this is reflected in the posterior probabilities computed.
Day 2: We can get the prior probability vectors on day 2 by our forward update (making predictions):
" (2) = [0.2883 0.0, 0.1268, 0.5849)
"1 (2) = [0.8135, 0.0, 0. 1815 0.0] Ug (2) [0.2883, 0.0, 0. 1268, 0.5849].
On the other hand, if we apply the naive updating rule defined in Remark on day 2, find
(2) = [0.4074, 0.0896, 0.0948, 0.4082)
22(2) = [0.81, 0.0, 0.19, 0.0]
u/g (2) = [0.4074, 0.0896, 0.0948, 0.4082).
Recall that we use Assumption in the proposed algorithm (Algorithm 4) and the Naive approach Remark 2 does not have the backward step, so both approaches do not capture the correlations among nodes. By Monte Carlo simulations, the correlations among nodes are captured, and the nodes' probability vectors are approximated on day 2 as follows:
2 (2) = [0.3235, 0.0976, 0.0196, 0.5593]
"1 (2) = [0.7244, O, 0.27..,766. 0j
2/ (2) [0.3158, 0.1072, 0.019, 0.558]
which yields the following comparison for the incurred estimation errors:
0.4342 Σ (2) (2)1 < (2) (2)l 0.5018.
The left. hand side shows the estimation error under our proposed backward-forwarl update and the right hand side shows the estimation error under the naive approach.
Delay of Testing Results
One can extend the framework to a more realistic case where testing results are not able to be obtained on the same day, but will be obtained after a delay a. other words, nodes are tested on day - a, the test results are provided on day I. The exlended framework is summarized as follows.
On day t, before getting the test results of day t a, the algorithm knows the following information: (i) the network topology from day - - to day t, i.c., G(t 1, {m, (1 a- a1 -)) and (ii)) and the prior
1).... .g(() (it is affected by the past actions);
(ii) the posterior probability of nodes on day [ probability vectors of nodes from day t - to day t, i.e., [ - a)} (este-a)" {u,(t) sesty
After getting the test results day a, can obtain the updated posterior probability vectors day t - a 1, and the posterior probability vectors day t - a, i.e., {e,(t 1)] =e and { (w, (1 a) (e) by Step 1 in Algorithm 4
37

---

Published in Transactions on Machine Learning Research March/2025
Based on (w(t - at) by Step 2 in Algorithm 4 update the prior probability from day - to day 1, and obtain the prior probability on day / + 1, l.e., (1, 1))
Repeating the process, we can compute the estimated probability vectors of nodes and apply the exploration and exploitation policies.
J Proof of Theorem 2
Step 1: Preliminarics.
We divide the distributions of initial infectious nodes into two complementary events:
I = (No node is infectious)
I2 =
Let N be sufficiently large,
Pr[Zi] = (1 11-1/N)" マ 1/e Pr[Z2] = 1--1-11 1/ee
In event I, since there is no infection on the initial day, then no node is infectious in the future, i.e., the true probability of nodes (1) for all i E V() and 1
Note that in Example D each node can be in one of two states, S and 1. The transmission probability B 1. So, on day t, the probability of node being in state I includes the infection of node i on day t - 1, and the infection from its neighbors. Then, based on 13 we have
1 (w) 11 1) (1
w/ (9 (t 11)--1111-1---- (1
(( 1)) (1
(47)
=1 =1 [1 w - ( 1)} w ( 1)H1 w/ 1(
1)}. (t)
For convention, we assume that nodes 0 and N + I are two virtual nodes with no probability of infection, ie., // (t) dj (N+ (t) for all and no tests applied to these two nodes all the time.
Since w/ + 1), w (6 1) (t + 1), w/ w((+)) (t + E [0, 1], then from 47
(1) 2 1 1 (1 u ( - 1)) x 1 (1) 1).
(48)
Thus, by symmetry over w w/ (f-2) - 1), w (t - 1). and wi (t) u (1) z max
(5)
(++1) (t - 1) we get the inequality
( - 1) 1), ( (t- - 1), w 1 (t-
(49)
Step Consider the computation of {n (t)}, based on 13 (equivalently
under event IT.
Recall that B(t) for all On any day t, if node in is tested, then the result is negative, and (46) (t) 0, and
( = u/ (1) for all i i in.
(50)
In 19 most one of 1 (i-1) (t 1), w 10 (t 1), and w ((+1) (t 1) is updated to 0. We first prove the following facts.
Fact 1. ( (1) 1 for all On any day I, w (1)) 2 1 with + in. where in is the index of node lested on
day t.
Proof. We prove Fact by mathematical induction. On the initial day, by model assumption in Example 1
u (4) (0) N. for all Then, if node in is tested, then as mentioned above, w (0) 0, and by 50
(6) (0()) 1z (0) 1/N for all i + io-
w1
38

---

Published in Transactions on Machine Learning Research (March/200 /2023)
Suppose Fact 1 holds for all T S 1-1. Now, we consider T l. From (49), we have (2) 2 max (w) (i-1)
(8o) 1). w (0) (t- 1), w] (f+1) (t- 1)} 2 1/N. Then, if node in is tested, we have wi (t) = 0, and then by (50
w (t) = u (1) 2 I/N for all i + i0-
Fact 2. If node i has not been tested up to day then //2(t) (t) tends to 1 as + co.
Proof. Since node is not tested from the initial day to day t, then
(6) (T), T t. " (9) (T) = u
(51)
Note that at most one of its neighbors is tested on day t. By 47 and Fact 1,
(t) 2 1 - w/ (t (f 1)) = = - (1 1/N)(1 2 1)).
which implies
(1-1/N)(1-w)) - -|
which implies
1 1- (t) - (1-1y = (1- -1-1/N))
Letting + oo completes the proof.
Fact 3. If node i is not tested day t 1, then
( (t) w/ (t- 1) + u
1 N
(t- (1
wf
1))
(0(( (t- 1).
(1) (1 1) > 0. From 47 by some algebra,
Proof. By Fact 3, if node i is not tested on day / -- 1, then w/
u (t) = (1) (t- - 1) + +1 w 1) 1 1) + w
(++ (t 1) w i ( (t 1) 1) ( 1))
-11 <))u( (8) (1 1)
where
1- w/ (t 1)
(w) () 1)+ + wf(tt))( 1) -wit (t 1)w (i 1)).
w/ (1) (t 10-11 1)
Note that at most one of the neighbors of node i is tested on day t - 1, then
1- w/ (t - 1)
>1 w/ (t -0-1) 1)
w 1)
-w From Fact 1, maxfw (6-1) 1),
w1 (i - 1) + w/ (((tt) (t - 1) - wi (1-1) (t 1) ((+1)
(t- 1)
1) 2 maxf y (6-1) 1) (t - 1), w/ w/tttt/// (6641 (t (1)).
w (6+1) (t 1)} 2 1/N. Thus, c 2 (1 - w/ (t - 1)) x 1/N. Honce,
(f(1) 2 w/ 10 1) 1/ (1 (t) (t- 1)) (00 (t-
Since we consider all possible sequential lesting policies, then we divide all nodes into two sets
(t) = {nodes that have not been tested up to day t}
S2()) (t).
Tn the following proof, let - co. By Fact 2, (1) - 1 if Si()) Next, we focus on the set S2(t). Denote the index of node which is tested on day t- 1 as io( By Fact 1, wi (8) Then, we define
(t (t- 1) 2 1/N for all i & io()).
S21(t) -i|1/N < w/ (t 1) 1/11
(22(1) - - 1// < w/ ( (t)
Thus, we have S2(t) (t) (t) U (tt(t)) Due to the equivalence of norms, without loss of generality, we consider Ln norm in the rest of the proof.
39

---

Published in Transactions on Machine Learning Research March/2023
(i) i E Si(), then uj (1) + 1. Thus (l,,()) - (1]l + 2.
(ii) If i E (t). then (t) 2. (t)ll 2 1|u,(t- 1) - 0,(t- - 1)1l2 + 2(N-1)
In fact, since i E S21 (t), then
No
i + io()) thus by 50 and Fact 3,
(t) 2 "
(6) (t - 1) + N (1 - w/ (t- 1)) (t- 1).
N
Note that N is sufficiently large, so 1/N < 1/2 < - 1/N. If E [1/N, 10,11-10 1021--140 1/N), then the fuction f(z) = x(1 - z) has the minimum value N-1 when x = 1/N. Thus, N²
19 (1) u1 (t- 1) N "
(52)
N3
Recall that (t) 0 and (t) 1 for all and u/ (t) us
(10 (t) 1, then
(t,(t) - 2, (t) (0) (0) 2|u (t) u) (t)
(53)
From 52
(t) (t)l = - of of 2/u, (t-
N - (1) 1)1
N3 01
2 2/10 (3) (t- 1) - 1/ 1)1 N(N - 1) = 1|u, 1) 22 1)1| + 2(N - 1)
N3
N3
(iii) i E S22 then node i is not tested on day 4, thus from 49 (1) 2 w/ / (1-1) 1 1-/N.
2(N-1) Thus, by 53 [lu,(t) - (t)l1 2 N
Since we consider N sufficiently large, then we can prove the following lemma. Lemma 4. lim (t) = Ø.
Proof. We first prove the following Claims.
Claim 1. If (i) / (1-1) (t) 2 1 - 1/N and node i i-1 1 is not tested on day t, or (ii) ij ((t
(t) 2 1- 1/N and node
(1-1) {+1 is not tested on day t, or (iii) u (t) 2 1 - 1 /N and ((+1 w (t) 1- 1/N, then (0) (t + 1) 2 1 - 1/N.
Proof. By (7 and (50 we can derive uj (t + 1) 2 1/N directly.
Claim 2. No node can stay in (t) for successive / - 1)] days.
Proof. if node i stays in (t) for successive [N3/(N - 1)] days, i.c., from day to day + [N3/(N -]]] then by 52 u7 (0) (T+ + [N - 1))) 1, which contradicts with u/ v/((()) < 1 for all t.
Now, we prove the lemma by contradiction. Based on Claim 2, assume there exists at least one j and an increasing sequence (4: with lim In = xc, such that j E E2)(14) for all {4]
For some i, node j is in S22(1, - 1) on day 4 - 1, and node j is in S21 (t,) on day 4, In other words, uf2 (t.) < 1-1NN~ I v1/)) (4: 1). From (4 and Calim u, ((2((()))) (t,) < 1 1/N S u. uf2((, (t;-1) holds only because
node j is tested on day t4 - 1, and all of its neighbors (i.e., nodes j - 1, j have -f--"( (t. 1) < - 1/N and uf ((+1)((, (4, 1) < 1 - 1/N. However, since uf5 (4 - 1) 2 1/N and node j is tested on day 4; 1, then by Claim 1, u / (t.) 2 1 - 1/N and uf ul/t") (4) 2 1 - 1/N. Subsequently, by Claim 1, we have ( (t, (f:+1)= 2 1-N.. Thus, on day 11, at least one of its neighbors, say j-1, has uff-") (1, +1) 2 1- 1/N. By Claim 1, node j never fall into Sz1(t) (t) for i (441,,442."" }, which contradicts with the assumption. ]
From Lemma when t + 0c, we have (t) = @(N) or [Sx((t) = O(N). Thus, ΣN (l2, - =t(ll = O(N).
Step 3: Consider the computation of (u, (1)) based Algorithm
40

---

Published in Transactions on Machine Learning Research (March/200)
In this step, consider specific testing policy: We test node on day k, where k 1(mod M) for all < < M.
In event I2, since the transmission probability B = 1, then all nodes are infected at most N days because there is no recovery. Thus, no node with positive testing result is repeatedly tested. So in al most 2N days, all nodes are infectious, and the algorithm finds all infected nodes, so (,(t) = 2, (t), t 2N.
In event I, whenever node tested, it is negative. Node is tested on day 0, the result negative. On day 1, node 2 is lested and the result is negative. By backward updating, since 8 = 1 and recovery, then nodes 1&3 are inferred to be in state S on day Since node is in state S on day 1. Then, node is inferred in state S on days 0 and 1.
Assume that nodes 1, 2, K - are inferred to be in state S by day k- 1. Now, we day k, where & s N. On day k, node k is tested negative, hence by backward updating, nodes k --2 2 and is are inferred to be in state S on day state S by day k. By induction, after N days, it clears every node, so 21) = 2, 2,(4), t N.
1. By the testing result node on day k, nodes 1,2, ... k- - 1 are inferred in
From Steps 1~3, we complete the proof.
K a-linking Backward Updating
K.1 Complexity Reduction
Let {1y))εо()) be a realization of {0,(O)) and (wheee() be a realization of {G(t - 1))e,..()- Let node i have state x in day t 1. Consider one node & E E0 (t 1) and the probability
Pr (-1x)
(t()).
Since node & is not infectious yb L, yv = R or yt = S, then the probability above remians the same no malter whether y/ = L, Ms = R or y/ S.
Thus, we introduce new state, denoted by E, be replacement of {L, R, S}, and
Pr (yk E)
E
Pr (r = z).
2E(LR,
Next, denote X' = E}, Equation 17 can be re-written follows:
Pr (1 (el coll 1) =))
Σ
II
Pr (Y)((())))())
Σ II
P, (1
(1ihse,s0) (EV.())
(uheem, JEV.())
(54)
II
(G 1) =)),
(EB(()
with reduces the computation complexity. Subsequently, e,(t- (((t-) 1) in (16 can be calculated by 54
directly.
K.2 a-linking Backward Updating
In the backward step, the computation complexity is large even in in (54), one way is to update the posterior probability e,) in sparser network. Now, we define a-linking Backward Updating follows:
54 To further reduce the complexity
(i) We generate subgraph (1) based on the pre-determined graph (()): Suppose that each edge (in (())) exists with probability a, 0 S < 1. If a = 1, then Gt(t) = ((t); if a = 0, then (t is a graph with no edges.
(ii) Backward updating (t): Similar with (t), v,(1), (t) and et(t), we define o,a((), (t), V (t) (t) and Or,a (t) on graph Ga (t), respectively. Subsoquently, replace at),), V, (t) and O,(t) by Or,a (t), V. (t), (t) and (t) in (54). respectively.
41

---

Published in Transactions on Machine Learning Research (March/2023)
L Proof of Theorem 3
Step 1. Preliminaries.
In Example 2 B = 1, A = O, and 7 = O, there is no recovery and we assume no latent state. Based on
the expression of rewards Pt(() for every node is given as follows. If node i has two neighbors (without quarantine)
P.(() - i - (0)1 - ( (1))a))) (1) + ug
(( (9 - (1))
(55)
If node only has one neighbor, then
(0, f:(1) u (1+d) (0(1-u) - 41 (1-2d) (1) (0, dE (-1-1
(56)
For simplicity, we introduce artificial nodes -1, 1, + 1,N + 2 with (t) = =u (1) = dj ((+1)(
(t) =
(N++) (t) 0 for all t, and these 4 nodes are never tested.
uy
Step 2. The RbEx policy.
Under the RbFx policy, the algorithm always tests the nodes with maximum rewards. Let an infectious node be found, for the first time, on day aN, where a is positive real number. Note that until the first infected node is found, in any application of the RbEx policy, 4i (3) (t) is the same for any given i, and hence (t) is also the same. So, a is the same for any application of the RbEx policy. Recall that in Example 2 nodes that are tested positive will be isolated. The cumulative infections is at least min N} in the end.
Step 3. Consider the exploration process of the specific exploration policy.
Recall that from Step 2, an infectious node is found, for the first time, by the RbEx policy with budget 10 lests on day a... Under the specifie defined exploration policy, we can choose a specific D' with V/ < a, such that no infectious node is tested by the RbEx policy with budget 9 tests before and including day D'N.
We know that on day nodes 1,2, ... t are infectious since 3 = 1. Note that one test is applicd to exploration (randomly choice) on every day, so with probability
N 7.
(57)
infections node is explored from the initial day to day Then, with probability
-
N'
r==1
one infectious node is detected on day r. Thus, with probability
EIa-
T-1 N N
(58)
one infectious node is tested by exploration process on day (r < t), and this node is not the new infectious one on day т, i.c., has index т. The probability defined in 158 increases with t when N is fixed, and it can be close to 1 when 1 close to N. Therefore, We can choose proper parameters 1/ and such that the probability defined in (58) is larger than or equal to Po- In particular, if N is large, we can choose relatively small b. In Theorem
we set po 2 99/99///
Let the infectious node detected (for the first time) by the exploration process have index j on day I' where t' < f. As discussed above, node j is not the new infectious node on day t', so we have < t'. In other words. node j+ ++ must be infecitous on day t' with a positive test result, ie.. Yy(t) = 1. By Step 1 in Algorithm the updated posterior probability of node j
ee 0.
(59)
42

---

Published in Transactions on Machine Learning Research (larch/2023)
Again, by Step 1 in Algorithm
w w = (()) 1.
(60)
Then, by Step 2 in Algorithm 1
2) (1' +1 =)= + = + =1 1(+1) 11) 1)= -u (1' + +1) 1.
(61)
Since j is detected and isolated on day t', then,
F2(t' + 1) =0
(62)
By 56 and 61
8z 1--1(t + = L (1' + 11 3 (t + +1) = 0
(63)
(t +1) = ug (0++) (t' + 1) 4 3 (t' + 1)) = 0.
By
55 and
61
f-- 1) u - 31 (1' + 1)(1 (1' + +1)
(64)
2)2 + 1) = u (1+3) (t' + 1)( - - - (t' + 1)).
Step The exploitation process of the specific exploration policy.
We first study extreme case where no tests are applicd. In this case, denote the prior probability of node on day T as U (T), which can be calculated by the following recursion:
up (T+))
(F) (F) U. (T)
(1 U--
(T)+
(65)
Based on 65
9N and U/ = 10c if 9N recall that ()) = 0 if
10 <is N. then (f) increases
10
over 7 and is function of e. Then, given b', N and t= UNN, we can choose small enough e, denoted by E(b,,) such that (2t) < 1 for all i. Since (T)(() increases over T, then (/(( < < T 2t.
Now, we introduce the exploitation process. Let t VN min 9 a..V. There are at most 2t infectious 9
nodes day 2t, Le., nodes 1,2, ,t. Since < min 40 N, then nodes with index from 9N/10-22 21 to N are in state S, which implies nodes with index from 9.N/10 2t to N can never be tested positive before day 2t. Thus, on any day T << 2t, for 9N/10- 2t < N, if node is tested, and the testing result is negative. Recall that (r) in (65) is calculated without any negative testing results. Hence, ( (r) S (T). Furthermore, with the condition / = UN m we can find small enough e(b', N), such that under the specific exploration policy,
"
(+)
T T 21, 9N/10 21 SisN.
(66)
In the rest, we divide the nodes in to 3 sets: Q = {ili < 2t}, Q2 = (il2t < i < 9N/10 -2t), and
O = (1/9N/10 2t S < N).
( (T) = 0. Fact 1. For i E O and 5 S 2t, ui (7) = 1 or u
Proof. If no test is applied Q1, then // (7) = for all E Q1.
On some day 7 < 21, if one node with index E Q is tested positive on day r 1, then by 66 uf (T) (F) = (F) = uf)+"(r) u ( (7) = 1. In other words, if node j is tested positive on day - 1, then node j, its neighbors and neighbors of neighbors have probability of infection equal to on day т.
On some day T, if node j is not tested positive on day 7- 1, and neither of its neighbors and neighbors of
neighbors are is not tested positive, then ( (7) = 1 only when ( (T - 1) = 1, or uf (T - 1) = 1 or uf (++1) (T- 1) since 3 1. Otherwise // (7) 0.
(T-
43

---

Published in Transactions on Machine Learning Research (larch/2023)
Fact 2. For i E Q1 and T S 2t, (T()) = 1 or (T( O.
Proof. If (T) (T) = O, then (T( = 0 by 55 and (56).
Now, we consider of) = in the following cases: (i) If both neighbors of node are isolated, then
(((T) = O. (ii) If one of neighbors of node i (for example, node i - 1) is isolated, then by (56). (((7) = 0 when uf af+ = 1, and (T)
1 when uj ufft"(()) (T) 0. (iii) If both neighbors are not isolated, then
(1-1) (T -1) =1 or un (6+1) (T - 1) = 1, otherwise, uy (T) - O. Since there is no recovery, then ui (i-1) (7) = 1
or u ( (r)= 1. By Fact 1, "I (T)
or uz (r) (T)
when j E Q1. If uj ( = " (6-1) (T) 1, then
(T( = 0. If uy (T) = 1, then by p5p, (x(T) 0 when (r) = 1, f((T) =1 when uy
(1-2) 2) (T) = 0. If
((+2) (T) = 1, f((T) = 1 when uf 2 (T) = 0. " (T) = 1, then by 55 (T( = when uy
From 660, for all r s 21 and E 23, we have
(T( S 2u, (9) (T) <1
(67)
Note that only nodes in Q and 23 may have positive probability of infection. For all T S 21 and i E Q2. since uf2 (7) = O, then (T( = Therefore, a node with reward equal to 1 has the largest reward.
Recall that on day 1', node j is tested positive. From (44, nodes j - 2 and j + have largest rewards (= 1) on day t' + 1, which are exploited on day t' + 1, and all other nodes in Q have rewards 0. This is because t' is the first day when a positive node is found. Since node j tested positive and isolated on day t', then all infectious nodes with index less than j can no longer infect other nodes in the line network. Now, we consider the nodes with index larger than j. Recall that j < t', so node j + 1 must be infectious on day f' and node j + 2 must be infectious on day L' 1'+1 since 3 1. Thus, node j + 2 is tested positive and is isolated. Since the network is a line, both nodes j +1 and j + 2 can no longer infect other nodes once node j ++2 2 is isolated. Note that nodes in 23 have positive rewards. When N is sufficiently large, in the rest of the exploitation process, nodes in 2s are tested. Recall that we have one test for exploration, and we can isolate at least 2 infectious nodes with index larger than j.
Repeat the process, we exploit nodes j + 4.j + 6, on day 2'+ respectively. Consider the direction from node to node N. On every day, there is at most one new infectious node, but at least two infectious nodes can be isolated. On some day, denote as day t' + xr the exploitation process can progress beyond the infections (exceeding by one node) for the first time. In other words, node j+2r is tested negative
+
(1+2z) (t' + x - 1) = O. However, since w) w/ (it2a-) 1) (t' + x) = 1
on day t' + x. By Step 2 in Algorithm e7
becuase node j + 2x -2 tested positive on day +' 1. By Step in Algorithm 4 uy (+22)) (t' +2++1) 1, hence by (64), fy+2x (t' + x + +1) == 1, which implics node j + 2x has the largest reward and is exploited on day L' + x + 1, and it will be tested positive. On day l' + x + 1, all infectious nodes are isolated.
Finally, we can calculate the total number of infections to be
j ++ 2(t' -) = 2t' - 28 28'N.
Let b 25'. This is an improvement by factor of at least y in comparison to the RbEx strategy, where o. can be as large as desired by increasing the value of N or decrcasing Po-
M Construction of Networks and Further Results
M.1 Constructions of SBM and V-SBM
In this section, we construct SBMs and its variants.
SBM The SBM is a generative model for random graphs. The graph is divided into several communitios, and subsets of nodes are characterized by being connected with one another with particular edge densities The intra-conuection probability is Pl, and inter-comnection probability is p2. We denote the SBM as
8 Here, we assume that M is an exact divisor of N.
44

---

Published in Transactions on Machine Learning Research March/2025
WS, (d,
Lp
Ratio
(6, 0.05)
0.504
4.952
.0003
(4, 0)
0.500
62.876
0.191
(6, 0.1)
0.456
5.718
0.027
(4, 0.03)
0.456
10.810
0.097
Table 12: Clustering coefficients of WS networks
WS, (d,6)
Tpp
Ratio
.001)
0.599
21,188
0.209
.0075)
0.489
21.264
0.182
(6, .005)
0.592
14.310
0.211
(4, .015)
0.473
14.253
0.174
(6, .009)
0.585
12.081
0.137
.0255)
0.467
12.171
0.125
Table 13: Clustering coefficients of WS networks
SBM(N, P1,11))). Note that the (expected) number of edges, denoted by [ε], is
P2 N
E
2 N M 1)
(M 1).
(68)
2 M
Now, we fix |8) and choose the pair (2I,P2) under fixed |&| in 68 The aim of fixing |8| is to guarantee that the transmission of the disease would not be affected by edges.
V-SBM Now, we consider a variant of SBM, denoted by V-SBM. Different from SBM, we only allow nodes in cluster to connect to nodes in successive clusters (the neighbor clusters). Denote the V-SBM as V-SBM(N, M, P2)). Similarly, the expected number of edges, denoted by [E],
P1 N 2 M
N
N2
|3]
1) + P2
(69)
M
Now, we fix [8), and choose the pair (2),22) under a fixed |&| in 69 The aim of fixing |8| is to guarantee that the transmission of the discase would not be affected by edges.
M.2 The impact of To and Lp individually
In this subsection, investigate the role of Yo and Lp individually, not through the common factor d. We consider different WS networks with degrees = 4, 6, and then adjust the rewiring probability 6, such that one of (Te, Ip)) is almost constant, and the other varying. We can see that the trend is similar to what we observed by varying 8 in Table 6
45


Reviews:
[{"review_id": "V25RsCIOju", "reviewer": "Reviewer_9us1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is thematically relevant to the times, and studies an important problem. It also proposes some interesting first-order approaches. In particular, I like the Thompson Sampling-esque idea used in Algorithm 3 to probabilistically test nodes that are most likely to be infected.\n\nMy grouse is that the paper is not written in a formal manner and lacks technical results (at least in the main text). The paper (to my mind) is positioned as a theory work, yet lacks any formal statements of performance guarantees, etc. I have listed my major concerns, errors and typos spotted in the next section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper uses a discrete-time compartmental model with type space S-L-I-R (Susceptible-Latent-Infected-Recovered) to model the spread of an epidemic (e.g., Covid-19) over a graph. The objective is to come up with a testing policy to minimize the expected number of infected nodes after $T$ rounds of propagation, subject to testing budget constraints at each $0 \\leqslant t \\leqslant T-1$. A node that tests positive is isolated and pruned from the graph. Instead of studying the global optimization problem over T periods, the authors instead focus on solving single period problems myopically where the objective is to minimize the number of new infections spawned in the next period. The rest of the paper is focused on the analysis of and approaches to the single period problem. Numerical experiments are provided at the end.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Figure 1 should be S-L-I-R.\n2. That the states of the nodes are independent is a very critical assumption that underlies everything else. In my opinion, this warrants a detailed discussion -- something that is currently lacking.\n3. On page 8, where is \"OPT\" defined? I understand from the context what this might be, but please define it formally.\n4. Please state the performance guarantee of Algorithm 1 formally. Clearly state what constant factor approximation is achieved by this algorithm.\n4. Footnote 3 should be $x\\in\\mathcal{X}\\backslash \\mathcal{B}$ (please correct the typo)\n5. As far as I understand, the set returned by Algorithm 1 should be $\\mathcal{K}^\\pi(t) = \\mathcal{A}_i$ (not its complement). Please fix this.\n6. In Algorithm 2, $\\underline{w}(0)$'s and $\\hat{r}_i(t)$'s haven't appeared before. Please state and describe everything clearly.\n7. How is $\\hat{r}_i(t)$ computed? I could not find this anywhere.\n8. Step 2 of Algorithm 2: K(t) should be B(t).\n9. Where are the performance guarantees of Algorithms 2 and 3?\n10. Typo in Algorithm 4 first line: $\\in$ is missing.\n11. Theorem 2: What does with probability approximately 1/e mean? What is the norm? What is the mode of convergence?\n12. Theorem 3: The result basically intends to convey that by injecting a small amount of randomness (exploration) in the testing policy, one can reduce cumulative infections by a constant factor. But this needs to be stated in a \"formal\" language.\n13. In Section 7 (Conclusions and Future Work), first paragraph, the authors claim that they propose a \"near-optimal\" testing policy. This is not true. Their policy (Algorithm 1) is based on reference [52] and only provides a constant factor approximation to a supermodular minimization problem (known to be NP-hard). What am I missing here? Is the approximation ratio best possible? This line appears to be an unsubstantiated claim. \n\nUnfortunately, this paper, in my opinion, is below the bar in its current form, and needs substantial work.\n", "broader_impact_concerns": "Since the paper is anchored around Covid-19, I believe an impact statement is warranted. The authors ought to clearly state the limitations of their work, the assumptions that go into it, and potential risks and pitfalls of their algorithms in a separate section.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zkFFcRXIkB", "reviewer": "Reviewer_PytJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe model is natural and practically relevant.  The algorithms and the message-passing subroutine are simple and intuitive (which is good).  The authors provide justifications for their approach by analyzing several stylized networks.  The experimental results look promising and align with intuition.\n\n\nWeaknesses:\n\nNone of the algorithms have a real theoretical guarantee.  The model is never fully defined, and the mathematical reasoning sometimes depends on implicit assumptions that are either vaguely mentioned or never mentioned (see detailed comments).  In terms of empirical results, I'd like to see the algorithm tested on different models of synthetic networks and other real networks.\n\n\nJustification of evaluation:\n\nI don't think \"whether the claims are supported by evidence\" always has a clear binary answer.  Here I'm interpreting it in a strict sense since it's the main evaluation criterion of TMLR.  Given the weaknesses mentioned above, I'm reluctant to say that all the claims (in particular, those in the abstract) are supported by accurate, clear and convincing evidence.  In particular I'd tone down any claim that involves \"theoretical guarantees\" or things like that.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies \"testing and controlling\" a disease (or any other harmful entity) spreading in a network.  The authors consider an indepdent spread model similar to \"independent cascade\", where each infected node independently attempts to infect its neighbors with a certain probability.  At each time, the algorithm may choose a given number of nodes to test.  If a node tests positive, then that node is immediately isolated and stops infecting its neighbors.  The goal is to minimize the cumulative number of infected nodes.\n\nThe authors present a family of heuristic methods (guided by theoretical insights) for the problem.  The authors observe that at each time, the number of newly infected nodes is supermodular in the set tested at the current time.  Based on this observation, the authors propose an algorithm which greedily chooses the set of nodes to test based on the marginal gain of each node.  This gives an approximation guarantee for each time step, but not over the entire process (which is why the algorithm is heuristic).  The authors further give an relaxation of the greedy algorithm, where an upper bound (the \"reward\") of the marginal gain of each node is computed before hand, and the ones with the highest rewards are tested.  The authors call this \"exploitation\".  Taking one more step forward, the authors propose an algorithm where each node is tested with probability proportional to the above reward.  The authors call this \"exploration\".  When implementing these algorithms, the authors propose a heuristic method (\"message-passing\") for estimating the posterior belief of the states of all nodes at each time.  The estimation method disregards any correlation between nodes.\n\nThe authors then test their algorithms on synthetic and real networks.  The results suggest that \"exploitation\" and \"exploration\" tend to outperform the 3 baseline methods.  The authors also vary parameters of the environment and study how that affects the performance of different algorithms.  The results roughly align with intuition.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(Also including detailed comments here.  The authors can use their judgment regarding the more subjective suggestions.)\n\nSec 1, second paragraph: \"... such SIR models ...\"\n\nLast paragraph on page 2, \"... knowledge vs. exploration ...\" (and later \"exploration vs. explotation ...\"): Extra space after \"vs.\" (consider using, e.g., \"vs.{}\").\n\n\"Covid-19\" vs \"COVID-19\"\n\nEq (2), problem formulation: So the budget constraint is in-expectation.  Any justification for this?  Do you know anything (e.g., hardness results) when the constraint must hold with probability 1?\n\nRelatedly: What does the algorithm know about how the network evolves?  I guess complete knowledge is a bit impractical, but you have to know something?  Overall I feel there's not enough information in the modeling section, and many important details of the model are only introduced later when they are referred to (see comments below).\n\nEq (5): So you assume infections happen independently even restricted to a single node.  This is fine (cf. the independent cascade model in influence maximization) but it might be helpful to also explain in words.\n\nLem 1: This should be trivial given all relevant details of the model.  In particular it looks like you assume any node which tested positive at time t is immediately isolated, which I would put in the modeling section (since it's not something that you prove).  What about nodes that tested positive before t?  Are they removed from the network?  I'd also discuss this more formally in the modeling section.\n\nAlgo 1: So this has some approximation guarantee for the single-stage problem, but can you say anything about how good it is for the actual objective in Eq (2)?  I wouldn't say it's \"near-optimal\" without such a guarantee.\n\nAlgo 3: Well I guess this is where you need the budget constraint to be in-expectation...  Still I feel a hard constraint would be more natural.\n\nEq (13): It looks like you are assuming quite strong independence over nodes, which in principle is incompatible with the belief updating process.  I'd remark somewhere that this is just a heuristic estimation.  (Remark 2 sort of touches on this but that remark is more about the update caused by observations at time t, and that's not the only source of dependency.  In particular, spreading also introduces dependency.)\n\nAlgo 3: I wouldn't call this \"exploration\" since (as the authors also say in the paper) the algorithm sort of balances between exploration and exploitation, with respect to estimated rewards.\n\nFig 5: What is Greedy?  Algo 1 I guess?  Also, why is Greedy not in Fig 6?", "broader_impact_concerns": "I don't have concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bPGtk7Ngmr", "reviewer": "Reviewer_WZi5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- To my knowledge, this particular model has not been studied before and the supermodular formulation and the message-passing algorithm are novel.\n- I liked the discussion of exploration and exploitation. It is cool that you can explicitly \"see\" the impact of exploration.\n- I found the paper to be well-written overall. Clear about contributions, with a clear mathematical exposition—enough detail so that the argument can be followed in the main body and lots of detail in the appendix.\n\nWeaknesses:\n- I have some complaints with the intro, both in terms of definitions and related work, see requested changes. I believe that the related work could be improved (and the authors make some unsupported claims here), but the authors' central contributions are supported.\n- There are other baselines that could be compared, particularly those that use reinforcement learning, see requested changes. I'm not sure that is fair to ask the authors to do all these comparisons, but I believe that they would likely outperform the authors' methods.\n- There is a central simplifying assumption being made that the entire contact network is acquired at each step. I think it is OK for the authors to make this simplification, but it is important to recognize that there is no real-world setting (that I know of) where the entire contact network is available. Usually, specific queries have to be made to get existence of any edges.\n- The paper is centered around COVID-19 in a way that is somewhat unsatisfying, given that the applications of this kind of method are likely to be around other infectious diseases. (The mutations of SARS-CoV-2 mean that the spread is very hard to stop in the way the authors propose.)\n- Symptoms do not appear anywhere. For some infectious diseases, symptoms are a very reliable signal of infectiousness (e.g., Ebola). Many contact tracing policies use symptoms in some central way.\n\nPost-response update:\nI understand the criticisms of the other authors, but I still think there is enough to justify acceptance.\n\nThe authors gave a thorough response that fixes substantial issues with the framing (the original version suffered from overclaiming in several areas). I am OK with the fact that there is not a fully precise theoretical advance here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study interventions to prevent the spread of a process through a network, motivated by contact tracing of infectious disease. They consider a setting where the network structure is known, but the individual state of nodes, which follow a Susceptible Latent Infectious Recovered discrete time compartmental model, is unknown. The decision maker has a budget of tests per time period. The decision-maker must decide which nodes to test at each time step. If a node tests positive, they are isolated until they are recovered.\n\nThe authors show that, under the simplifying assumption of myopic (one-step) minimization of infection, the optimization problem is supermodular, increasing and monotone. The resulting optimization is still expensive for large graphs. They consider further simplifications, deriving an upper bound for the objective and estimating the node state distribution using past test results. This is, however, a pure exploitation policy. The authors add an exploration component and prove that this results in an improvement of a constant factory in a line network.\n\nThe last methodological contribution is a message-passing framework that is used to estimate the state of nodes based on test observations in a computationally efficient way and will provable converge to the true probabilities.\n\nIn simulations, they compare their new methods with baselines, such as random testing, contact tracing subject to a test budget and a logistic regression-based predictor of infection on both synthetic and and a real data network (Copenhagen Networks Study). Their policies appear to outperform baselines. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not think it is accurate to say that contact tracing depends on knowledge of the network topology. I believe that the “practical” contact tracing methods cited depend only on the neighbors of cases that are to be traced, not that the _entire_ network topology (certainly Kucharski et al. is in that category). They are not “network-aware” in some sense. This is in contrast to the authors proposed policies, which require the entire network (see weakness #3).\n\nThere are some papers that consider sequential testing and isolation policies. In addition, the authors make a claim that there are \"only two relevant papers\". It depends exactly what you consider relevant, but other papers the authors could consider.\n- Meirom et al., ICML 2021. https://icml.cc/virtual/2021/spotlight/9910. This seems closest to the authors' setting, and I believe could serve as a direct comparison. Unfortunately, there is no publicly available code, as far as I know, and the published experiments don't look comparable.\n- Kucharski et al., Lancet Infectious Diseases 2020 does consider what happens if you test n% of the population every day.\n- Perrault et al., https://www.medrxiv.org/content/10.1101/2020.11.16.20227389v2\n- Also potentially related is work by Ou et al. in active case finding: https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=6148&context=sis_research. (see below)\n\nDefinitions:\n- Contact tracing may trace contacts either forward in time from an index case (forward contact tracing) or backward in time (i.e., finding the individuals who were contacts of the index case in the period before they developed symptoms, e.g., https://www.nature.com/articles/s41567-021-01187-2). It is unclear whether the authors’ statements in the intro are referring to both forward and backward contact tracing or just forward.\n- The authors identify shortcoming of contact tracing:\n“(i) They are not able to prioritize nodes based on their likelihood of being infected (beyond the coarse notion of contact or lack thereof)\n(ii) they do not incorporate any type of exploration”\nIt is not clear to me that (i) is a shortcoming of contact tracing—it might be a shortcoming of particular contact tracing policies, but it’s not an inherent shortcoming of contact tracing.\n(ii) is a shortcoming of contact tracing in the sense that it would fall under the term “active case finding” instead. See, e.g., thelancet.com/journals/lanpub/article/PIIS2468-2667(21)00033-5/fulltext\n\nDomains would be helpful in the notation table, e.g., \\sigma \\in {I, S, L, R}\n\nBenchmark policies “Logistics regression” -> \"Logistic regression\"\n\nIt is advisable to remove grant numbers from Acknowledgments to protect the authors' anonymity.", "broader_impact_concerns": "I do not have broader impact concerns for this paper. (I disagree that a broader impact statement is needed for this paper.)", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of stopping the spread of a disease in a network. The key idea is to greedily minimize the number of newly infected nodes in the next round by testing and isolating the nodes in the current round. The authors propose two notable variants of their main algorithm, which optimize a more tractable objective and estimate the unknown distribution of the states of the nodes. The proposed algorithms are evaluated empirically.

This work is on a good topic, which became highly relevant recently due to COVID. The original paper suffered from several issues, such as over-claimed contributions and imprecise writing given that this paper tries to make theory contributions. These were addressed in the updated paper. I agree with the reviewers that the theory contribution of this paper is limited. On the other hand, it is a hard problem and the algorithmic contributions partially make up for it.
Decision: Accept (poster)