Complexity of finite-horizon Markov decision process problems

DOI10.1145/347476.347480zbMath1327.68136OpenAlexW1981691276WikidataQ60016244 ScholiaQ60016244MaRDI QIDQ3457753

Christopher Lusena, Martin Mundhenk, Judy Goldsmith, Eric W. Allender

Publication date: 17 December 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/347476.347480

zbMATH Keywords

computational complexityMarkov decision processespartially observable Markov decision processesPSPACEsuccinct representationsPLNP, \(\mathrm{NP}^{\mathrm{PP}}\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Markov and semi-Markov decision processes (90C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Decidability and complexity of action-based temporal planning over dense time, Temporal concatenation for Markov decision processes, A mean-variance optimization problem for discounted Markov decision processes, Hybrid answer set programming, Approximability and efficient algorithms for constrained fixed-horizon POMDPs with durative actions, On the complexity of bribery and manipulation in tournaments with uncertain information, On the computability of Solomonoff induction and AIXI, Approximate receding horizon approach for Markov decision processes: average reward case, A survey of computational complexity results in systems and control, I <scp>ndemics</scp>, On the Complexity of Value Iteration, POMDPs under probabilistic semantics, Monomials in arithmetic circuits: complete problems in the counting hierarchy, On the undecidability of probabilistic planning and related stochastic optimization problems