MDPs as distribution transformers: Affine invariant synthesis for safety objectives

• Main Authors: AKSHAY, S., CHATTERJEE, Krishnendu, MEGGENDORFER, Tobias, ZIKELIC, Dorde
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Markov decision processes; invariant synthesis; distribution transformers; Skolem hardness; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/9068; https://ink.library.smu.edu.sg/context/sis_research/article/10071/viewcontent/Computer_Aided_Verification.pdf
• Institution: Singapore Management University

Markov decision processes can be viewed as transformers of probability distributions. While this view is useful from a practical standpoint to reason about trajectories of distributions, basic reachability and safety problems are known to be computationally intractable (i.e., Skolem-hard) to solve i...