On the undecidability of probabilistic planning and related stochastic optimization problems

DOI10.1016/S0004-3702(02)00378-8zbMath1082.68806OpenAlexW1977070092MaRDI QIDQ814465

Steve Hanks, Anne Condon, Omid Madani

Publication date: 7 February 2006

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0004-3702(02)00378-8

zbMATH Keywords

Markov decision processesStochastic optimizationComputabilityComputational complexityUndecidabilityDiscountedInfinity-horizonPartial observabilityProbabilistic planningUnobservability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic programming (90C15) Undecidability and degrees of sets of sentences (03D35) Reasoning under uncertainty in the context of artificial intelligence (68T37) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (23)

What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives ⋮ Decidability and complexity of action-based temporal planning over dense time ⋮ The Effect of Tossing Coins in Omega-Automata ⋮ Gradient-descent for randomized controllers under partial observability ⋮ Finite-Memory Strategies in POMDPs with Long-Run Average Objectives ⋮ Optimal supervisory control with mean payoff objectives and under partial observation ⋮ Verification and Control of Partially Observable Probabilistic Real-Time Systems ⋮ Stochastization of Weighted Automata ⋮ Parameter-Independent Strategies for pMDPs via POMDPs ⋮ Parameter synthesis in Markov models: a gentle survey ⋮ Verification and control of partially observable probabilistic systems ⋮ On the computability of Solomonoff induction and AIXI ⋮ Exploiting symmetries for single- and multi-agent partially observable stochastic domains ⋮ Distributed probabilistic input/output automata: expressiveness, (un)decidability and algorithms ⋮ The complexity of synchronizing Markov decision processes ⋮ A survey of partial-observation stochastic parity games ⋮ THE FRONTIER OF DECIDABILITY IN PARTIALLY OBSERVABLE RECURSIVE GAMES ⋮ Probabilistic Acceptors for Languages over Infinite Words ⋮ Recursive Markov Decision Processes and Recursive Stochastic Games ⋮ On Decision Problems for Probabilistic Büchi Automata ⋮ Bisimulation metrics and norms for real-weighted automata ⋮ POMDPs under probabilistic semantics ⋮ Optimal cost almost-sure reachability in POMDPs

Cites Work

• Planning for conjunctive goals
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The complexity of stochastic games
• Optimal control of diffusion processes with reflection
• The computational complexity of propositional STRIPS planning
• On the complexity of partially observed Markov decision processes
• Undecidable problems for probabilistic automata of fixed dimension
• A subexponential randomized algorithm for the simple stochastic game problem
• Optimal control of Markov processes with incomplete state information
• Optimal control of partially observable Markovian systems
• STRIPS: A new approach to the application of theorem proving to problem solving
• Solving H-horizon, stationary Markov decision problems in time proportional to log (H)
• Complexity of finite-horizon Markov decision process problems
• The Complexity of Markov Decision Processes
• State of the Art—A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms
• The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted Costs
• Finding Optimal Survey Policies via Adaptive Markov Decision Processes
• The Optimal Control of Partially Observable Markov Processes over a Finite Horizon
• Probabilistic automata
• A survey of computational complexity results in systems and control
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the undecidability of probabilistic planning and related stochastic optimization problems