The Complexity of Markov Decision Processes
From MaRDI portal
Publication:3780028
DOI10.1287/moor.12.3.441zbMath0638.90099OpenAlexW2032100464WikidataQ29038896 ScholiaQ29038896MaRDI QIDQ3780028
John N. Tsitsiklis, Christos H. Papadimitriou
Publication date: 1987
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/2893
computational complexityinfinite horizonMarkov decision processesparallel computationfinite horizonNP-completePSPACE-completehighly parallel algorithmspartially observed statesoptimal policy computation
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40)
Related Items (84)
What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives ⋮ Meeting a deadline: shortest paths on stochastic directed acyclic graphs with information gathering ⋮ Probabilistic Timed Automata with One Clock and Initialised Clock-Dependent Probabilities ⋮ The Limitations of Optimization from Samples ⋮ A theory of strict P-completeness ⋮ Runtime monitors for Markov decision processes ⋮ PARTIALLY OBSERVABLE MARKOV DECISION PROCESSES AND PERIODIC POLICIES WITH APPLICATIONS ⋮ When is a pair of matrices mortal? ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ An Incremental Fast Policy Search Using a Single Sample Path ⋮ Reachability analysis of quantum Markov decision processes ⋮ Probabilistic planning with clear preferences on missing information ⋮ Myopic Bounds for Optimal Policy of POMDPs: An Extension of Lovejoy’s Structural Results ⋮ Graph Games and Reactive Synthesis ⋮ On the complexity of partially observed Markov decision processes ⋮ Solving H-horizon, stationary Markov decision problems in time proportional to log (H) ⋮ Concavely-Priced Probabilistic Timed Automata ⋮ Quantitative verification and strategy synthesis for stochastic games ⋮ A simulated annealing algorithm for the restricted stochastic traveling salesman problem with exponentially distributed arc lengths ⋮ Verifying Pufferfish privacy in hidden Markov models ⋮ The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes ⋮ Model Checking Linear-Time Properties of Probabilistic Systems ⋮ The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate ⋮ Cost-sensitive feature acquisition and classification ⋮ Remote state estimation with usage-dependent Markovian packet losses ⋮ On the control of discrete-event dynamical systems ⋮ Robotic manipulation of multiple objects as a POMDP ⋮ Exact decomposition approaches for Markov decision processes: a survey ⋮ Optimal eviction policies for stochastic address traces ⋮ A mean-variance optimization problem for discounted Markov decision processes ⋮ Hybrid answer set programming ⋮ Graph planning with expected finite horizon ⋮ Markov Decision Processes with Incomplete Information and Semiuniform Feller Transition Probabilities ⋮ Unnamed Item ⋮ k-Certainty Exploration Method: an action selector to identify the environment in reinforcement learning ⋮ Approximability and efficient algorithms for constrained fixed-horizon POMDPs with durative actions ⋮ A discrete-time optimal execution problem with market prices subject to random environments ⋮ Risk-aware shielding of partially observable Monte Carlo planning policies ⋮ The partially observable Markov decision processes in healthcare: an application to patients with ischemic heart disease (IHD) ⋮ Future memories are not needed for large classes of POMDPs ⋮ A survey of stochastic \(\omega \)-regular games ⋮ Optimal Switching Sequence for Switched Linear Systems ⋮ From Reinforcement Learning to Deep Reinforcement Learning: An Overview ⋮ Separation of learning and control for cyber-physical systems ⋮ On the complexity of computational problems associated with simple stochastic games ⋮ Partially observable Markov decision model for the treatment of early prostate cancer ⋮ On the computability of Solomonoff induction and AIXI ⋮ Using mathematical programming to solve factored Markov decision processes with imprecise probabilities ⋮ Exploiting symmetries for single- and multi-agent partially observable stochastic domains ⋮ Decentralized MDPs with sparse interactions ⋮ PageRank optimization by edge selection ⋮ Unnamed Item ⋮ A novel scheduling index rule proposal for QoE maximization in wireless networks ⋮ Linear programming formulation for non-stationary, finite-horizon Markov decision process models ⋮ New complexity results about Nash equilibria ⋮ Computation of weighted sums of rewards for concurrent MDPs ⋮ Strong planning under partial observability ⋮ On players with a bounded number of states ⋮ Algorithms and conditional lower bounds for planning problems ⋮ Randomization for robot tasks: using dynamic programming in the space of knowledge states ⋮ A survey of computational complexity results in systems and control ⋮ A fast approximation method for partially observable Markov decision processes ⋮ Partial-Observation Stochastic Games ⋮ Probabilistic Acceptors for Languages over Infinite Words ⋮ Unnamed Item ⋮ Model-based learning of interaction strategies in multi-agent systems ⋮ Unnamed Item ⋮ Empirical Dynamic Programming ⋮ The complexity of dynamic programming ⋮ Reasoning about uncertain parameters and agent behaviors through encoded experiences and belief planning ⋮ Game theory on attack graph for cyber deception ⋮ On the Complexity of Value Iteration ⋮ Partially observable Markov decision processes with imprecise parameters ⋮ Robust Control of Partially Observable Failing Systems ⋮ A theory of strict P-completeness ⋮ Unnamed Item ⋮ Bayesian Decision Making in Groups is Hard ⋮ Constrained Multiagent Markov Decision Processes: a Taxonomy of Problems and Algorithms ⋮ On probabilistic timed automata. ⋮ POMDPs under probabilistic semantics ⋮ Optimal decisions in stochastic graphs with uncorrelated and correlated edge weights ⋮ Optimal cost almost-sure reachability in POMDPs ⋮ On the undecidability of probabilistic planning and related stochastic optimization problems ⋮ Solving factored MDPs using non-homogeneous partitions
This page was built for publication: The Complexity of Markov Decision Processes
