Real-time Sampling and Estimation: From IoT Markov Processes to Disease Spread Processes
Shirin Saeedi Bidokhti, Assistant Professor, University of Pennsylvania
Abstract: The Internet of Things (IoT) and social networks have provided unprecedented information platforms. The information is often governed by processes that evolve over time and/or space (e.g., on an underlying graph) and they may not be stationary or stable. We seek to devise efficient strategies to collect real-time information for timely estimation and inference. This is critical for learning and control.
In the first part of the talk, we focus on the problem of real-time sampling and estimation of autoregressive Markov processes over random access channels. For the class of policies in which decision making has to be independent of the source realizations, we make a bridge with the recent notion of Age of Information (AoI) to devise novel distributed policies that utilize local AoI for decision making. We also provide strong guarantees for the performance of the proposed policies. More generally, allowing decision making to be dependent on the source realizations, we propose distributed policies that improve upon the state of the art by a factor of approximately six. Furthermore, we numerically show the surprising result that despite being decentralized, our proposed policy has a performance very close to that of centralized scheduling.
In the second part of the talk, we go beyond time-evolving processes by looking at spread processes that are defined over time as well as an underlying network. We consider the spread of an infectious disease such as COVID-19 in a network of people and design sequential testing (and isolation) strategies to contain the spread. To this end, we develop a probabilistic framework to sequentially learn nodes’ probabilities of infection (using test observations) by an efficient backward-forward update algorithm that first infers about the state of the relevant nodes in the past before propagating that forward into future. We further argue that if nodes’ probabilities of infection were accurately known at each time, exploitation-based policies that test the most likely nodes are myopically optimal in a relevant class of policies. However, when our belief about the probabilities is wrong, exploitation can be arbitrarily bad, as we provably show, while a policy that combines exploitation with random testing can contain the spread faster. Accordingly, we propose exploration policies in which nodes are tested probabilistically based on our estimated probabilities of infection Using simulations, we show in several interesting settings how exploration helps contain the spread by detecting more infected nodes, in a timely manner, and by providing a more accurate estimate of the nodes’ probabilities of infection.