# MDPs with Energy-Parity Objectives

arXiv: https://arxiv.org/abs/1701.02546 · HTML: https://mlsanity.com/paper/1701.02546/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2017.

## Built on by (most cited first, 1 of 1)

- [Shielding in Resource-Constrained Goal POMDPs](https://mlsanity.com/paper/2211.15349/) (2022)

## Abstract (arXiv)

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 mathitNPcap mathitcoNP and can be solved in pseudo-polynomial time for energy-parity MDPs.