Multiple-environment Markov decision processes

DOI10.4230/LIPICS.FSTTCS.2014.531MaRDI QIDQ2978542zbMATH OpenOpenAlexFDO

Authors Ocan Sankur, Jean-François Raskin

Publication date 25 April 2017

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

zbMATH Keywords

Markov decision processesmultiple objectivesprobabilistic systems

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Specification and verification (program logics, model checking, etc.) (68Q60) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Markov and semi-Markov decision processes (90C40)

Abstract: We introduce Multi-Environment Markov Decision Processes (MEMDPs) which are MDPs with a set of probabilistic transition functions. The goal in a MEMDP is to synthesize a single controller with guaranteed performances against all environments even though the environment is unknown a priori. While MEMDPs can be seen as a special class of partially observable MDPs, we show that several verification problems that are undecidable for partially observable MDPs, are decidable for MEMDPs and sometimes have even efficient solutions.

Recommendations

• Multi-Objective Model Checking of Markov Decision Processes
• Multi-objective Model Checking of Markov Decision Processes
• POMDPs under probabilistic semantics
• Markov Decision Processes with Multiple Objectives
• Simple strategies in multi-objective MDPs

Cited in

(6)

• Tableaux for policy synthesis for MDPs with PCTL* constraints
• Computation of weighted sums of rewards for concurrent MDPs
• Multi-Actor Markov Decision Processes
• Robust almost-sure reachability in multi-environment MDPs
• A PSPACE algorithm for almost-sure rabin objectives in multi-environment MDPs
• The value problem for multiple-environment MDPs with parity objective

This page was built for publication: Multiple-environment Markov decision processes

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