Optimizing the expected mean payoff in energy Markov decision processes

DOI10.1007/978-3-319-46520-3_3MaRDI QIDQ1990496zbMATH OpenOpenAlexFDO

Authors Tomáš Brázdil, Antonin Kučera, Petr Novotný

Publication date 25 October 2018

Full work available at URL https://arxiv.org/abs/1607.00678

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Markov and semi-Markov decision processes (90C40) Computer system organization (68M99)

Abstract: Energy Markov Decision Processes (EMDPs) are finite-state Markov decision processes where each transition is assigned an integer counter update and a rational payoff. An EMDP configuration is a pair s(n), where s is a control state and n is the current counter value. The configurations are changed by performing transitions in the standard way. We consider the problem of computing a safe strategy (i.e., a strategy that keeps the counter non-negative) which maximizes the expected mean payoff.

Recommendations

• Energy and Mean-Payoff Parity Markov Decision Processes
• Efficient strategy iteration for mean payoff in Markov decision processes
• Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes
• Unifying two views on multiple mean-payoff objectives in Markov decision processes
• Maximizing the conditional expected reward for reaching the goal

Cited in

(5)

• Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
• Energy mean-payoff games
• Efficient strategy iteration for mean payoff in Markov decision processes
• Positivity-hardness results on Markov decision processes
• Energy and Mean-Payoff Parity Markov Decision Processes

This page was built for publication: Optimizing the expected mean payoff in energy Markov decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1990496)