Efficient strategy iteration for mean payoff in Markov decision processes

DOI10.1007/978-3-319-68167-2_25zbMATH Open1495.68152arXiv1707.01859OpenAlexW2728937946MaRDI QIDQ5096097FDOQ5096097

Authors: Jan Křetínský, Tobias Meggendorfer 

Publication date: 12 August 2022

Published in: Automated Technology for Verification and Analysis (Search for Journal in Brave)

Abstract: 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.

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

Recommendations

• Value iteration for long-run average reward in Markov decision processes
• PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDP
• Optimizing the expected mean payoff in energy Markov decision processes
• Markov decision processes with multiple long-run average objectives
• Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Applications of game theory (91A80) Markov and semi-Markov decision processes (90C40)

Cited In (10)

• Title not available (Why is that?)
• Comparison of algorithms for simple stochastic games
• Comparison of algorithms for simple stochastic games
• Optimizing the expected mean payoff in energy Markov decision processes
• Multi-objective optimization of long-run average and total rewards
• Title not available (Why is that?)
• PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDP
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Symblicit algorithms for mean-payoff and shortest path in monotonic Markov decision processes
• Finite-memory strategy synthesis for robust multidimensional mean-payoff objectives

Uses Software

• PRISM

This page was built for publication: Efficient strategy iteration for mean payoff in Markov decision processes

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