The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes

DOI10.1007/BFB0029956MaRDI QIDQ4699290zbMATH OpenFDO

Authors Martin Mundhenk, J. Goldsmith, Eric Allender

Publication date 8 November 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0029956

zbMATH Keywords

complexityMarkov decision processstochastic process

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Management decision making, including multiple objectives (90B50) Markov and semi-Markov decision processes (90C40)

Recommendations

• The complexity of optimal small policies
• Complexity of finite-horizon Markov decision process problems
• Partially observable Markov decision processes: a geometric technique and analysis
• A survey of algorithmic methods for partially observed Markov decision processes

Cited in

(15)

• Reasoning and predicting POMDP planning complexity via covering numbers
• On the \(p\)-reinforcement and the complexity
• A survey of algorithmic methods for partially observed Markov decision processes
• Deciding the Value 1 Problem for \sharp -acyclic Partially Observable Markov Decision Processes
• On the Computational Complexity of Stochastic Controller Optimization in POMDPs
• Partially observable Markov decision processes: a geometric technique and analysis
• Exploiting symmetries for single- and multi-agent partially observable stochastic domains
• History-dependent evaluations in partially observable Markov decision process
• Task-aware verifiable RNN-based policies for partially observable Markov decision processes
• Polynomial-Time Computation of Strong and n-Present-Value Optimal Policies in Markov Decision Chains
• A New Policy Evaluation Algorithm for Markov Decision Processes with Quasi Birth-Death Structure
• scientific article; zbMATH DE number 2243354 (Why is no real title available?)
• Exact decomposition approaches for Markov decision processes: a survey
• Off-policy evaluation in partially observed Markov decision processes under sequential ignorability
• On the undecidability of probabilistic planning and related stochastic optimization problems

This page was built for publication: The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes

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