On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes
From MaRDI portal
Publication:4302721
DOI10.1287/ijoc.6.2.188zbMath0807.90124OpenAlexW2162425318WikidataQ114967831 ScholiaQ114967831MaRDI QIDQ4302721
Mary Melekopoglou, Anne Condon
Publication date: 12 March 1995
Published in: ORSA Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/b3219edc2ce55b2d7f5d45cc014a0d2733ed3051
Abstract computational complexity for mathematical programming problems (90C60) Markov and semi-Markov decision processes (90C40)
Related Items
Improved and Generalized Upper Bounds on the Complexity of Policy Iteration, The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes, The stochastic shortest path problem: a polyhedral combinatorics perspective, On strategy improvement algorithms for simple stochastic games, Linear programming formulation for non-stationary, finite-horizon Markov decision process models, Variance minimization of parameterized Markov decision processes, A survey of computational complexity results in systems and control