Reachability Analysis in Stochastic Directed Graphs by Reinforcement Learning

• 成果类型: Article
• 署名作者: Possieri, Corrado; Frasca, Mattia; Rizzo, Alessandro
• 署名单位: Consiglio Nazionale delle Ricerche (CNR); Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti (IASI-CNR); University of Catania; Polytechnic University of Turin; New York University; New York University Tandon School of Engineering
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3143080
• 发表日期: 2023
• 页码: 462-469
• 关键词: Reachability analysis; Reinforcement Learning; stochastic digraphs

摘要

We characterize the reachability probabilities in stochastic directed graphs by means of reinforcement learning methods. In particular, we show that the dynamics of the transition probabilities in a stochastic digraph can be modeled via a difference inclusion, which, in turn, can be interpreted as a Markov decision process. Using the latter framework, we offer a methodology to design reward functions to provide upper and lower bounds on the reachability probabilities of a set of nodes for stochastic digraphs. The effectiveness of the proposed technique is demonstrated by application to the diffusion of epidemic diseases over time-varying contact networks generated by the proximity patterns of mobile agents.