Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes

DOI10.4230/LIPICS.ICALP.2017.121zbMATH Open1442.90199arXiv1702.05472OpenAlexW2963046256MaRDI QIDQ5111453FDOQ5111453

Raphaël Berthon, Jean-François Raskin, Mickael Randour

Publication date: 27 May 2020

Abstract: The beyond worst-case synthesis problem was introduced recently by Bruy`ere et al. [BFRR14]: it aims at building system controllers that provide strict worst-case performance guarantees against an antagonistic environment while ensuring higher expected performance against a stochastic model of the environment. Our work extends the framework of [BFRR14] and follow-up papers, which focused on quantitative objectives, by addressing the case of $omega$-regular conditions encoded as parity objectives, a natural way to represent functional requirements of systems. We build strategies that satisfy a main parity objective on all plays, while ensuring a secondary one with sufficient probability. This setting raises new challenges in comparison to quantitative objectives, as one cannot easily mix different strategies without endangering the functional properties of the system. We establish that, for all variants of this problem, deciding the existence of a strategy lies in $sfNPcapsfcoNP$, the same complexity class as classical parity games. Hence, our framework provides additional modeling power while staying in the same complexity class. [BFRR14] V'eronique Bruy`ere, Emmanuel Filiot, Mickael Randour, and Jean-Franc{c}ois Raskin. Meet your expectations with guarantees: Beyond worst-case synthesis in quantitative games. In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 199-213. Schloss Dagstuhl - Leibniz - Zentrum fuer Informatik, 2014.

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

zbMATH Keywords

Markov decision processesparity objectivesparity gamesbeyond worst-case synthesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Markov and semi-Markov decision processes (90C40) Games involving graphs (91A43)

Cited In (10)

• Title not available (Why is that?)
• Simple Strategies in Multi-Objective MDPs
• Timed games with bounded window parity objectives
• Combinations of Qualitative Winning for Stochastic Parity Games
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multi-cost bounded tradeoff analysis in MDP
• Different strokes in randomised strategies: revisiting Kuhn's theorem under finite-memory assumptions
• Title not available (Why is that?)
• Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints

This page was built for publication: Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes

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