Communicating MDPs: Equivalence and LP properties

DOI10.1016/0167-6377(88)90062-4MaRDI QIDQ1112741zbMATH OpenOpenAlexFDO

Authors Jerzy Filar, Todd A. Schultz

Publication date 1988

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(88)90062-4

zbMATH Keywords

irreducible Markov chain

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Linear programming (90C05) Markov and semi-Markov decision processes (90C40)

Review text

The communicating property of Markov decision processes (MDP) is equivalent to the satisfaction of sets of linear equations. A mapping between ``multichain and ``unchain linear programs for undiscounted MDPs developed by using this equivalence is used to show that the simplex linear program solves communicating MDPs.

Recommendations

• scientific article; zbMATH DE number 2189775
• Linear programming formulations of Markov decision processes
• Linear programming with multiple choice constraints for single chain undiscounted Markov decision problems
• An improved algorithm for solving communicating average reward Markov decision processes
• scientific article; zbMATH DE number 2189770

Cites work

• Computing a Bias-Optimal Policy in a Discrete-Time Markov Decision Problem
• Discrete Dynamic Programming
• Finite state Markovian decision processes
• scientific article; zbMATH DE number 3793773 (Why is no real title available?)
• Linear Programming and Markov Decision Chains
• Linear programming and sequential decisions
• Multichain Markov Renewal Programs
• On Linear Programming in a Markov Decision Problem
• Optimal decision procedures for finite Markov chains. Part II: Communicating systems

Cited in

(10)

• Average cost Markov decision processes: Optimality conditions
• Finite state Markov decision models with average reward criteria
• A decomposition algorithm for limiting average Markov decision problems.
• An improved algorithm for solving communicating average reward Markov decision processes
• On some algorithms for limiting average Markov decision processes
• Derman's book as inspiration: some results on LP for MDPs
• Survey of linear programming for standard and nonstandard Markovian control problems. Part I: Theory
• Approximate equivalence of Markov decision processes.
• scientific article; zbMATH DE number 2189770 (Why is no real title available?)
• scientific article; zbMATH DE number 2189775 (Why is no real title available?)

This page was built for publication: Communicating MDPs: Equivalence and LP properties

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