Multi-objective Robust Strategy Synthesis for Interval Markov Decision Processes

DOI10.1007/978-3-319-66335-7_13MaRDI QIDQ5194931zbMATH OpenOpenAlexFDO

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

Publication date 17 September 2019

Published in Quantitative Evaluation of Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.06875

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Markov and semi-Markov decision processes (90C40)

Abstract: 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 proposed approaches by applying them on several case studies using a prototypical tool.

Recommendations

• Robust optimal strategies in Markov decision problems
• Publication:3486378
• Solution procedures for multi-objective markov decision processes
• Finite-memory strategy synthesis for robust multidimensional mean-payoff objectives
• Markov Decision Processes with Multiple Objectives
• scientific article; zbMATH DE number 3852821
• Robust multiobjective dynamic programming: Minimax envelopes for efficient decisionmaking under scenario uncertainty
• Multi-objective discounted Markov decision processes with expectation and variance criteria
• Multi-weighted Markov decision processes with reachability objectives

Cited in

(10)

• Compositional strategy synthesis for stochastic games with multiple objectives
• Multi-cost bounded tradeoff analysis in MDP
• A survey of decision making and optimization under uncertainty
• Finite-memory strategy synthesis for robust multidimensional mean-payoff objectives
• Polynomial-time alternating probabilistic bisimulation for interval MDPs
• Robust Control for Dynamical Systems with Non-Gaussian Noise via Formal Abstractions
• Strategy synthesis for partially-known switched stochastic systems
• Robust almost-sure reachability in multi-environment MDPs
• Parameter synthesis for Markov models: covering the parameter space
• Interval Markov decision processes with multiple objectives: from robust strategies to Pareto curves

This page was built for publication: Multi-objective Robust Strategy Synthesis for Interval Markov Decision Processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5194931)