Informatics Colloquium 20. 11. Verification of Markov Decision Processes using Learning Algorithms
Informatics 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.