MDPs with Energy-Parity Objectives

Richard Mayr, Patrick Totzke, Sven Schewe, Dominik Wojtczak

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Energy-parity objectives combine ω-regular with quantitative objectives of reward MDPs. The controller needs to avoid to run out of energy while satisfying a parity objective.
We refute the common belief that, if an energy-parity objective holds almost-surely, then this can be realised by some finite memory strategy. We provide a surprisingly simple counterexample that only uses coB\"uchi conditions.
We introduce the new class of bounded (energy) storage objectives that, when combined with parity objectives, preserve the finite memory property. Based on these, we show that almost-sure and limit-sure energy-parity objectives, as well as almost-sure and limit-sure storage parity objectives, are in NP∩coNP and can be solved in pseudo-polynomial time for energy-parity MDPs.
Original languageEnglish
Title of host publication2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages14
ISBN (Electronic)978-1-5090-3018-7
Publication statusPublished - 18 Aug 2017
Event2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science - Reykjavik, Reykjavik, Iceland
Duration: 20 Jun 201723 Jun 2017


Conference2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science
Abbreviated titleLICS 2017
Internet address


  • MDP
  • energy-parity


Dive into the research topics of 'MDPs with Energy-Parity Objectives'. Together they form a unique fingerprint.
  • Energy Efficient Control

    Mayr, R.



    Project: Research

Cite this