On the undecidability of probabilistic planning and related stochastic optimization problems
From MaRDI portal
Publication:814465
ComputabilityComputational complexityDiscountedInfinity-horizonMarkov decision processesPartial observabilityProbabilistic planningStochastic optimizationUndecidabilityUnobservability
Undecidability and degrees of sets of sentences (03D35) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Reasoning under uncertainty in the context of artificial intelligence (68T37) Stochastic programming (90C15)
Recommendations
Cites work
- A subexponential randomized algorithm for the simple stochastic game problem
- A survey of computational complexity results in systems and control
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Complexity of finite-horizon Markov decision process problems
- Finding Optimal Survey Policies via Adaptive Markov Decision Processes
- scientific article; zbMATH DE number 4061056 (Why is no real title available?)
- scientific article; zbMATH DE number 3765145 (Why is no real title available?)
- scientific article; zbMATH DE number 3513703 (Why is no real title available?)
- scientific article; zbMATH DE number 3572058 (Why is no real title available?)
- scientific article; zbMATH DE number 1216123 (Why is no real title available?)
- scientific article; zbMATH DE number 1263212 (Why is no real title available?)
- scientific article; zbMATH DE number 1315585 (Why is no real title available?)
- scientific article; zbMATH DE number 1335900 (Why is no real title available?)
- scientific article; zbMATH DE number 1361472 (Why is no real title available?)
- scientific article; zbMATH DE number 3305047 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3371972 (Why is no real title available?)
- Nonapproximability results for partially observable Markov decision processes
- On the complexity of partially observed Markov decision processes
- Optimal control of diffusion processes with reflection
- Optimal control of Markov processes with incomplete state information
- Optimal control of partially observable Markovian systems
- Planning for conjunctive goals
- Probabilistic automata
- Solving H-horizon, stationary Markov decision problems in time proportional to log (H)
- State of the Art—A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms
- STRIPS: A new approach to the application of theorem proving to problem solving
- The Complexity of Markov Decision Processes
- The complexity of stochastic games
- The computational complexity of propositional STRIPS planning
- The Optimal Control of Partially Observable Markov Processes over a Finite Horizon
- The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted Costs
- Undecidable problems for probabilistic automata of fixed dimension
Cited in
(43)- On stochastic dynamic programming for solving large-scale planning problems under uncertainty
- Verification and control of partially observable probabilistic systems
- On the computability of Solomonoff induction and AIXI
- The complexity of synchronizing Markov decision processes
- Bisimulation metrics and norms for real-weighted automata
- Decidability and complexity of action-based temporal planning over dense time
- Gradient-descent for randomized controllers under partial observability
- A survey of partial-observation stochastic parity games
- POMDPs under probabilistic semantics
- Distributed probabilistic input/output automata: expressiveness, (un)decidability and algorithms
- Optimal cost almost-sure reachability in POMDPs
- Optimal supervisory control with mean payoff objectives and under partial observation
- What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives
- Recursive Markov decision processes and recursive stochastic games
- Verification and control of partially observable probabilistic real-time systems
- Stochastization of weighted automata
- The problem of planning with three sources of uncertainty
- The Effect of Tossing Coins in Omega-Automata
- scientific article; zbMATH DE number 6519681 (Why is no real title available?)
- Probabilistic Acceptors for Languages over Infinite Words
- scientific article; zbMATH DE number 1315585 (Why is no real title available?)
- Exploiting symmetries for single- and multi-agent partially observable stochastic domains
- The frontier of decidability in partially observable recursive games
- Finite-memory strategies in POMDPs with long-run average objectives
- On Decision Problems for Probabilistic Büchi Automata
- Parameter-Independent Strategies for pMDPs via POMDPs
- Parameter synthesis in Markov models: a gentle survey
- Robust almost-sure reachability in multi-environment MDPs
- Under-approximating expected total rewards in POMDPs
- Search and explore: symbiotic policy synthesis in POMDPs
- Positivity-hardness results on Markov decision processes
- Regular decision processes
- Cyber vulnerability maintenance policies that address the incomplete nature of inspection
- Stochastic games with synchronizing objectives
- Process symmetry in probabilistic transducers
- Search and explore: symbiotic policy synthesis in POMDPs
- Inaproximability in weighted timed games
- A framework for belief-based programs and their verification
- The complexity of pure maxmin strategies in two-player extensive-form games
- Stochastic games with synchronization objectives
- Stochastic processes with expected stopping time
- Probabilistic finite automaton emptiness is undecidable for a fixed automaton
- Quantitative language automata
This page was built for publication: On the undecidability of probabilistic planning and related stochastic optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q814465)
