Earlier Version

Energy and mean-payoff parity Markov decision processes

K. Chatterjee, L. Doyen, Energy and Mean-Payoff Parity Markov Decision Processes, IST Austria, 2011.

Download
OA 329.98 KB

Technical Report | Published | English
Author
Department
Series Title
IST Austria Technical Report
Abstract
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.
Publishing Year
Date Published
2011-02-16
Page
20
ISSN
IST-REx-ID

Cite this

Chatterjee K, Doyen L. Energy and Mean-Payoff Parity Markov Decision Processes. IST Austria; 2011. doi:10.15479/AT:IST-2011-0001
Chatterjee, K., & Doyen, L. (2011). Energy and mean-payoff parity Markov decision processes. IST Austria. https://doi.org/10.15479/AT:IST-2011-0001
Chatterjee, Krishnendu, and Laurent Doyen. Energy and Mean-Payoff Parity Markov Decision Processes. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0001.
K. Chatterjee and L. Doyen, Energy and mean-payoff parity Markov decision processes. IST Austria, 2011.
Chatterjee K, Doyen L. 2011. Energy and mean-payoff parity Markov decision processes, IST Austria, 20p.
Chatterjee, Krishnendu, and Laurent Doyen. Energy and Mean-Payoff Parity Markov Decision Processes. IST Austria, 2011, doi:10.15479/AT:IST-2011-0001.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T11:52:57Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar