Polynomial-Time Computation of Strong and n-Present-Value Optimal Policies in Markov Decision Chains

DOI10.1287/MOOR.2016.0812MaRDI QIDQ5359111zbMATH OpenOpenAlexFDO

Authors

Publication date 22 September 2017

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

Full work available at URL https://doi.org/10.1287/moor.2016.0812

zbMATH Keywords

computational complexitydynamic programminginfinite horizon

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
• scientific article; zbMATH DE number 1361472
• Generalized polynomial approximations in Markovian decision processes
• Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations
• Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations
• Optimal policies about discounted vector-valued Markovian decision programming and its algorithms
• Computation of optimal policies in discounted semi-Markov decision chains
• scientific article; zbMATH DE number 238320
• Strong 1-optimal stationary policies in denumerable Markov decision processes
• The simplex method is strongly polynomial for deterministic Markov decision processes

Cited in

(3)

• Valuing programs with deterministic and stochastic cycles
• Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems
• Markov branching decision chains with interest-rate-dependent rewards

This page was built for publication: Polynomial-Time Computation of Strong and n-Present-Value Optimal Policies in Markov Decision Chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5359111)