A New Complexity Result on Solving the Markov Decision Problem

DOI10.1287/moor.1050.0149zbMath1082.90132OpenAlexW2167471538WikidataQ92950991 ScholiaQ92950991MaRDI QIDQ5704247

Yinyu Ye

Publication date: 11 November 2005

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/1c2b44a27a54596eccaf1c807b50bf503824fcee

zbMATH Keywords

complexitylinear programmingMarkov decision problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40)

Related Items (11)

The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes ⋮ Reformulation of the linear program for completely ergodic MDPs with average cost criteria ⋮ The stochastic shortest path problem: a polyhedral combinatorics perspective ⋮ Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks ⋮ Randomized Linear Programming Solves the Markov Decision Problem in Nearly Linear (Sometimes Sublinear) Time ⋮ Towards solving 2-TBSG efficiently ⋮ Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems ⋮ Dynamic mechanism design with interdependent valuations ⋮ Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes ⋮ Efficient computation of a canonical form for a matrix with the generalized P-property ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

This page was built for publication: A New Complexity Result on Solving the Markov Decision Problem