Multi-objective robust strategy synthesis for Interval Markov decision processes

Ernst Moritz Hahn, Vahid Hashemi, Holger Hermanns, Morteza Lahijanian, Andrea Turrini*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

23 Citations (Scopus)


Interval Markov decision processes (IMDPs) generalise classical MDPs by having interval-valued transition probabilities. They provide a powerful modelling tool for probabilistic systems with an additional variation or uncertainty that prevents the knowledge of the exact transition probabilities. In this paper, we consider the problem of multi-objective robust strategy synthesis for interval MDPs, where the aim is to find a robust strategy that guarantees the satisfaction of multiple properties at the same time in face of the transition probability uncertainty. We first show that this problem is PSPACE-hard. Then, we provide a value iteration-based decision algorithm to approximate the Pareto set of achievable points. We finally demonstrate the practical effectiveness of our proposals by applying them on several real-world case studies.

Original languageEnglish
Title of host publicationQuantitative Evaluation of Systems
Subtitle of host publication14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings
EditorsNathalie Bertrand, Luca Bortolussi
Place of PublicationCham
Number of pages17
ISBN (Electronic)978-3-319-66335-7
ISBN (Print)978-3-319-66334-0
Publication statusPublished - 2017
Externally publishedYes
Event14th International Conference on Quantitative Evaluation of Systems, QEST 2017 - Berlin, Germany
Duration: 5 Sept 20177 Sept 2017
Conference number: 14

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th International Conference on Quantitative Evaluation of Systems, QEST 2017
Abbreviated titleQEST
Internet address


Dive into the research topics of 'Multi-objective robust strategy synthesis for Interval Markov decision processes'. Together they form a unique fingerprint.

Cite this