Reachability analysis in stochastic directed graphs by reinforcement learning
This work provides a novel approach for analyzing stochastic networks, which is incremental as it adapts reinforcement learning to a specific graph theory problem.
The authors tackled the problem of estimating reachability probabilities in stochastic directed graphs by modeling them as Markov decision processes and designing reward functions to compute bounds. They demonstrated the method's effectiveness on epidemic diffusion in time-varying contact networks, achieving bounds with up to 95% accuracy in simulations.
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.