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
computational complexityMarkov decision processespartially observable Markov decision processesPSPACEsuccinct representationsPLNP, \(\mathrm{NP}^{\mathrm{PP}}\)
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