Complexity of finite-horizon Markov decision process problems

DOI10.1145/347476.347480MaRDI QIDQ3457753zbMATH OpenOpenAlexWikidataFDO

Authors Martin Mundhenk, J. Goldsmith, C. Lusena, Eric 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 processesNP, \(\mathrm{NP}^{\mathrm{PP}}\)partially observable Markov decision processesPLPSPACEsuccinct representations

Mathematics Subject Classification ID

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

Recommendations

• The Complexity of Markov Decision Processes
• The complexity of optimal small policies
• On the Computational Complexity of Stochastic Controller Optimization in POMDPs
• Computational complexity in Markov decision theory
• The Complexity of Decentralized Control of Markov Decision Processes

Cited in

(24)

• Approximate receding horizon approach for Markov decision processes: average reward case
• On the computability of Solomonoff induction and AIXI
• A mean-variance optimization problem for discounted Markov decision processes
• Decidability and complexity of action-based temporal planning over dense time
• POMDPs under probabilistic semantics
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• The complexity of optimal small policies
• Computational complexity in Markov decision theory
• On the complexity of finite memory policies for Markov decision processes
• The Complexity of Markov Decision Processes
• Hybrid answer set programming
• scientific article; zbMATH DE number 1361472 (Why is no real title available?)
• Temporal concatenation for Markov decision processes
• On the Complexity of Value Iteration
• INDEMICS: an interactive high-performance computing framework for data-intensive epidemic modeling
• A survey of computational complexity results in systems and control
• Approximability and efficient algorithms for constrained fixed-horizon POMDPs with durative actions
• Optimistic MLE: a generic model-based algorithm for partially observable sequential decision making
• The complexity of uncertainty in Markov decision processes
• A new parallelized of hierarchical value iteration algorithm for discounted Markov decision processes
• Partially observable RL: benign structures and simple generic algorithms
• The complexity of pure maxmin strategies in two-player extensive-form games
• On the undecidability of probabilistic planning and related stochastic optimization problems
• On the complexity of bribery and manipulation in tournaments with uncertain information

This page was built for publication: Complexity of finite-horizon Markov decision process problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3457753)