A Linearly Relaxed Approximate Linear Program for Markov Decision Processes

DOI10.1109/TAC.2017.2743163MaRDI QIDQ4567182zbMATH OpenOpenAlexFDO

Authors Chandrashekar Lakshminarayanan, Shalabh Bhatnagar, Csaba Szepesvári

Publication date 27 June 2018

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.02544

Mathematics Subject Classification ID

Linear programming (90C05) Markov and semi-Markov decision processes (90C40)

Abstract: Approximate linear programming (ALP) and its variants have been widely applied to Markov Decision Processes (MDPs) with a large number of states. A serious limitation of ALP is that it has an intractable number of constraints, as a result of which constraint approximations are of interest. In this paper, we define a linearly relaxed approximation linear program (LRALP) that has a tractable number of constraints, obtained as positive linear combinations of the original constraints of the ALP. The main contribution is a novel performance bound for LRALP.

Recommendations

• scientific article; zbMATH DE number 3885681
• Finite linear programming approximations of constrained discounted Markov decision processes
• Linear programming formulations of Markov decision processes
• The linear programming approach to reach-avoid problems for Markov decision processes
• The Linear Program approach in multi-chain Markov Decision Processes revisited
• A linear programming approach to nonstationary infinite-horizon Markov decision processes
• On efficiency of linear programming applied to discounted Markovian decision problems
• Linear programming formulation for non-stationary, finite-horizon Markov decision process models
• Linear programming in tector criterion markov and semi-Markov decision processes
• Approximate linear programming for first-order MDPs

Cited in

(6)

• Separable Markovian decision problems. The linear programming method in the multichain case
• Simple and fast algorithm for binary integer and online linear programming
• Modelling and solving resource allocation problems via a dynamic programming approach
• Linear programming formulation for non-stationary, finite-horizon Markov decision process models
• Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
• A linear programming based approach for composite-action Markov decision processes

This page was built for publication: A Linearly Relaxed Approximate Linear Program for Markov Decision Processes

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