Faster Algorithms for Markov Decision Processes with Low Treewidth

2013/03/30 by Krishnendu Chatterjee, Chatterjee, Krishnendu, Jakub Łącki +1 · 1 citation
Computer Science · #Bayesian Modeling and Causal Inference #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.1304.0084

openalex publication_date 2013/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider two core algorithmic problems for probabilistic verification: the maximal end-component decomposition and the almost-sure reachability set computation for Markov decision processes (MDPs). For MDPs with treewidth k, we present two improved static algorithms for both the problems that run in time O(n ⋅ k^2.38 ⋅ 2^k) and O(m ⋅ log n ⋅ k), respectively, where n is the number of states and m is the number of edges, significantly improving the previous known O(n⋅ k ⋅ √(n⋅ k)) bound for low treewidth. We also present decremental algorithms for both problems for MDPs with constant treewidth that run in amortized logarithmic time, which is a huge improvement over the previously known algorithms that require amortized linear time.

Cited by

• Value Iteration for Long-run Average Reward in Markov Decision Processes

Related

• Faster Algorithms for Quantitative Analysis of Markov Chains and Markov\n Decision Processes with Small Treewidth
• Symbolic Time and Space Tradeoffs for Probabilistic Verification
• Monte Carlo Tree Search for Verifying Reachability in Markov Decision\n Processes
• Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths
• Verification of Markov Decision Processes using Learning Algorithms