Model Repair for Markov Decision Processes
Authors:
- Taolue ChenTCTaolue Chen
- Ernst Moritz HahnEHErnst Moritz Hahn
- Tingting HanTHTingting Han
- Marta KwiatkowskaMKMarta Kwiatkowska
- Hongyang QuHQHongyang Qu
- Lijun ZhangLZLijun Zhang
- 1 July 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 85-92
Abstract
Markov decision processes (MDPs) are often used for modelling distributed systems with probabilistic failure or randomisation. We consider the problem of model repair for MDPs defined as follows: if the MDP fails to satisfy a property, we aim to find new values for the transition probabilities so that the property is guaranteed to hold, while at the same time the cost of repair is minimised. Because solving the MDP repair problem exactly is infeasible, in this paper we focus on approximate solution methods. We first formulate a region-based approach, which yields an interval in which the minimal repair cost is contained. As an alternative, we also consider sampling based approaches, which are faster but unable to provide lower bounds on the repair cost. We have integrated both methods into the probabilistic model checker PRISM and demonstrated their usefulness in practice using a computer virus case study.Keywords
This publication has 14 references indexed in Scilit:
- Synthesis for PCTL in Parametric Markov Decision Processes2011
- An Inverse Method for Policy-Iteration Based AlgorithmsElectronic Proceedings in Theoretical Computer Science, 2009
- Probabilistic Mobile AmbientsTheoretical Computer Science, 2009
- Combined Decision Techniques for the Existential Theory of the RealsLecture Notes in Computer Science, 2009
- Stochastic Model Checking2007
- Efficient solving of quantified inequality constraints over the real numbersACM Transactions on Computational Logic, 2006
- Towards a Logic for Performance and MobilityElectronic Notes in Theoretical Computer Science, 2006
- Faster mixing via average conductance1999
- Understanding the Metropolis-Hastings AlgorithmThe American Statistician, 1995
- Monte Carlo sampling methods using Markov chains and their applicationsBiometrika, 1970