MDPs with Energy-Parity Objectives

Richard Mayr; Patrick Totzke; Sven Schewe; Dominik Wojtczak

doi:10.1109/LICS.2017.8005131

MDPs with Energy-Parity Objectives

Richard Mayr, Patrick Totzke, Sven Schewe, Dominik Wojtczak

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

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 language	English
Title of host publication	2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Number of pages	14
ISBN (Electronic)	978-1-5090-3018-7
DOIs	https://doi.org/10.1109/LICS.2017.8005131
Publication status	Published - 18 Aug 2017
Event	2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science - Reykjavik, Reykjavik, Iceland Duration: 20 Jun 2017 → 23 Jun 2017 http://lics.siglog.org/lics17/

Conference

Conference	2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science
Abbreviated title	LICS 2017
Country/Territory	Iceland
City	Reykjavik
Period	20/06/17 → 23/06/17
Internet address	http://lics.siglog.org/lics17/

Keywords / Materials (for Non-textual outputs)

MDP
energy-parity

Access to Document

10.1109/LICS.2017.8005131

mainAccepted author manuscript, 343 KBLicence: Other

Energy Efficient Control
Mayr, R.
EPSRC
1/09/15 → 31/08/19
Project: Research

Richard Mayr
- Mayr36.teaching-admined.acuk
Person: Academic: Research Active

Cite this

@inproceedings{be7b3cf8db3c4155a4de8a937e80477e,

title = "MDPs with Energy-Parity Objectives",

abstract = "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. ",

keywords = "MDP, energy-parity",

author = "Richard Mayr and Patrick Totzke and Sven Schewe and Dominik Wojtczak",

year = "2017",

month = aug,

day = "18",

doi = "10.1109/LICS.2017.8005131",

language = "English",

booktitle = "2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017 ; Conference date: 20-06-2017 Through 23-06-2017",

url = "http://lics.siglog.org/lics17/",

}

TY - GEN

T1 - MDPs with Energy-Parity Objectives

AU - Mayr, Richard

AU - Totzke, Patrick

AU - Schewe, Sven

AU - Wojtczak, Dominik

PY - 2017/8/18

Y1 - 2017/8/18

N2 - 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.

AB - 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.

KW - MDP

KW - energy-parity

U2 - 10.1109/LICS.2017.8005131

DO - 10.1109/LICS.2017.8005131

M3 - Conference contribution

BT - 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science

Y2 - 20 June 2017 through 23 June 2017

ER -

MDPs with Energy-Parity Objectives

Abstract / Description of output

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Projects

Energy Efficient Control

Profiles

Richard Mayr

Cite this