Scalable Verification of Markov Decision Processes

TitleScalable Verification of Markov Decision Processes
Publication TypeConference Paper
Year of Publication2014
AuthorsLegay, A, Sedwards, S, Traonouez, L-M
Conference Name4th Workshop on Formal Methods in the Development of Software (FMDS 2014)
Conference LocationGrenoble
AbstractMarkov decision processes (MDP) are useful to model concurrent process optimisation problems, but verifying them with numerical methods is often intractable. Existing approximative approaches do not scale well and are limited to memoryless schedulers. Here we present the basis of scalable verification for MDPSs, using an O(1) memory representation of history-dependent schedulers. We thus facilitate scalable learning techniques and the use of massively parallel verification.
PDF (Full text): 
Work Package: