Efficient Strategy Iteration for Mean Payoff in Markov Decision\n Processes

2017/07/06 by Jan Křetínský, Křetínský, Jan, Tobias Meggendorfer +1
Computer Science · Decision Sciences · #Advanced Software Engineering Methodologies #Bayesian Modeling and Causal Inference #Data Quality and Management #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Performance (cs.PF) #Software Reliability and Analysis Research

paper · pdf · doi:10.48550/arxiv.1707.01859

openalex publication_date 2017/07/06 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Probabilistic Mobile Ambients

Related

• Value Iteration for Long-run Average Reward in Markov Decision Processes
• A Method for Speeding Up Value Iteration in Partially Observable Markov Decision Processes
• Learning and Planning in Average-Reward Markov Decision Processes
• Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs
• Mean-Variance Optimization in Markov Decision Processes