On the complexity of partially observed Markov decision processes

DOI10.1016/0304-3975(95)00158-1MaRDI QIDQ1351500zbMATH OpenOpenAlexFDO

Authors Michel de Rougemont, Anatol Slissenko, Dmitri Burago

Publication date 27 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0304-3975(95)00158-1

Mathematics Subject Classification ID

Markov processes (60J99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The Complexity of Markov Decision Processes
• Nonapproximability results for partially observable Markov decision processes
• The complexity of optimal small policies
• On the complexity of finite memory policies for Markov decision processes

Cites work

• Dynamic programming and stochastic control
• Finite Continuous Time Markov Chains
• Games against nature
• scientific article; zbMATH DE number 176526 (Why is no real title available?)
• scientific article; zbMATH DE number 192768 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 3793773 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Shortest paths without a map
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Markov Decision Processes

Cited in

(16)

• A tutorial on partially observable Markov decision processes
• Optimal decisions in stochastic graphs with uncorrelated and correlated edge weights
• On the \(p\)-reinforcement and the complexity
• On the construction of -optimal strategies in partially observed MDPs
• Nonapproximability results for partially observable Markov decision processes
• The complexity of optimal small policies
• Deciding the Value 1 Problem for \sharp -acyclic Partially Observable Markov Decision Processes
• On the complexity of finite memory policies for Markov decision processes
• Optimal control of infinite horizon partially observable decision processes modelled as generators of probabilistic regular languages
• The Complexity of Markov Decision Processes
• A Partially Observable Markov Decision Process with Lagged Information
• Probabilistic opacity for Markov decision processes
• Solution Procedures for Partially Observed Markov Decision Processes
• Planning and learning in partially observable systems via filter stability
• A survey of solution techniques for the partially observed Markov decision process
• On the undecidability of probabilistic planning and related stochastic optimization problems

This page was built for publication: On the complexity of partially observed Markov decision processes

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