News and events archive
From the faculty
Informatics Colloquium 20. 11. Verification of Markov Decision Processes using Learning AlgorithmsInformatics Colloquium 20. 11. 2018, 14:00 lecture hall D2 doc. RNDr. Tomáš Brázdil, Ph.D., FI MU Verification of Markov Decision Processes using Learning Algorithms Abstract: I will present an application of machine-learning algorithms in the verification of Markov decision processes (MDPs). The primary goal of these techniques is to improve performance by avoiding an exhaustive exploration of the state space. I will concentrate on computation of maximum reachability probabilities in MDPs and present two methods based on a heuristic-driven partial exploration of the model. First, bounded real-time dynamic programming that yields precise lower and upper bounds on the maximum reachability probability. Second, Monte Carlo tree search, a method celebrated in various machine-learning settings, that combines exact computation using search trees with sampling methods. I will demonstrate usefulness of these methods in verification of resource access control protocols.