10.15479/AT:IST-2011-0001
Chatterjee, Krishnendu
Krishnendu
Chatterjee0000-0002-4561-241X
Doyen, Laurent
Laurent
Doyen
Energy and mean-payoff parity Markov decision processes
IST Austria Technical Report
IST Austria
2011
2018-12-12T11:39:02Z
2020-01-17T09:46:02Z
technical_report
/record/5387
/record/5387.json
2664-1690
329976 bytes
application/pdf
We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode ω-regular specifications, and the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition re- quires that the resource level never drops below 0, and the mean-payoff condi- tion requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i.e., winning with probability 1) in energy parity MDPs is in NP ∩ coNP, while for mean- payoff parity MDPs, the problem is solvable in polynomial time, improving a recent PSPACE bound.