Causally Deterministic Markov Decision Processes
Abstract: Probabilistic systems are often modeled using factored versions of Markov decision processes (FMDPs), where the states are composed out of the local states of components and each transition involves only a small subset of the components. Concurrency arises naturally in such systems. To exploit this fundamental feature of FMDPs, we provide concurrent semantics for FMDPs based on the classical notion of event structures, thereby cleanly separating causality, concurrency, and conflicts that arise from stochastic choices. We further identify the subclass of causally deterministic FMDPs (CMDPs), where non-determinism arises solely due to concurrency. We show that in CMDPs, local reachability properties can be computed using a “greedy” strategy. Finally, we implement our ideas in a prototype and apply it to four models, confirming the potential for substantial improvements over state-of-the-art methods.
Bio
P. S. Thiagarajan received a B.Tech degree from IIT, Madras, India, and a PhD from Rice University. Over the years he has held multiple academic positions in the USA, Germany, Denmark, India, and Singapore (at the dear old NUS). He is currently a Research Professor at the University of North Carolina, Chapel Hill, USA. His research interests span a broad range of topics involving the modeling and analysis of distributed, real-time, hybrid, and probabilistic computing systems as well as computational systems biology.