Optimizing the expected mean payoff in energy Markov decision processes

DOI10.1007/978-3-319-46520-3_3zbMATH Open1398.68078arXiv1607.00678OpenAlexW2472051997MaRDI QIDQ1990496FDOQ1990496

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

Publication date: 25 October 2018

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.

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

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

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)

Cited In (5)

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

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)