Efficient Strategy Iteration for Mean Payoff in Markov Decision Processes

KŘETÍNSKÝ, Jan a Tobias MEGGENDORFER. Efficient Strategy Iteration for Mean Payoff in Markov Decision Processes. In Automated Technology for Verification and Analysis - 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings. Springer, 2017, s. 380-399. ISBN 9783319681665. Dostupné z: https://doi.org/10.1007/978-3-319-68167-2_25.

Základní údaje

Originální název

Efficient Strategy Iteration for Mean Payoff in Markov Decision Processes

Autoři

KŘETÍNSKÝ, Jan a Tobias MEGGENDORFER

Vydání

Automated Technology for Verification and Analysis - 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings, od s. 380-399, 20 s. 2017

Nakladatel

Springer

---

Další údaje

Typ výsledku

Stať ve sborníku

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

ISBN

9783319681665

ISSN

DOI

https://doi.org/10.1007/978-3-319-68167-2_25

---

Anotace

V originále

Markov decision processes (MDPs) are standard models for probabilistic systems with non-deterministic behaviours. Mean payoff (or long-run average reward) provides a mathematically elegant formalism to express performance related properties. Strategy iteration is one of the solution techniques applicable in this context. While in many other contexts it is the technique of choice due to advantages over e.g. value iteration, such as precision or possibility of domain-knowledge-aware initialization, it is rarely used for MDPs, since there it scales worse than value iteration. We provide several techniques that speed up strategy iteration by orders of magnitude for many MDPs, eliminating the performance disadvantage while preserving all its advantages.