A Linearly Relaxed Approximate Linear Program for Markov Decision Processes

DOI10.1109/TAC.2017.2743163zbMATH Open1390.90562arXiv1704.02544OpenAlexW2605818517MaRDI QIDQ4567182FDOQ4567182

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)

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.

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

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

Mathematics Subject Classification ID

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

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)