A Linearly Relaxed Approximate Linear Program for Markov Decision\n Processes

2017/04/08 by Chandrashekar Lakshminarayanan, Shalabh Bhatnagar, Lakshminarayanan, Chandrashekar +3 · 1 citation
Computer Science · Engineering · #Advanced Control Systems Optimization #Constraint Satisfaction and Optimization #FOS: Electrical engineering #Reinforcement Learning in Robotics #Scheduling and Optimization Algorithms #Systems and Control (eess.SY) #Vehicle Routing Optimization Methods #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.1704.02544

openalex publication_date 2017/04/08 · openalex created_date 2022/09/24 · openalex updated_date 2026/07/28

Abstract

Approximate linear programming (ALP) and its variants have been widely\napplied to Markov Decision Processes (MDPs) with a large number of states. A\nserious limitation of ALP is that it has an intractable number of constraints,\nas a result of which constraint approximations are of interest. In this paper,\nwe define a linearly relaxed approximation linear program (LRALP) that has a\ntractable number of constraints, obtained as positive linear combinations of\nthe original constraints of the ALP. The main contribution is a novel\nperformance bound for LRALP.\n

Citations

• Feature Selection Using Regularization in Approximate Linear Programs\n for Markov Decision Processes
• Linear Programming for Large-Scale Markov Decision Problems

Cited by

• Analysis of approximate linear programming solution to Markov decision problem with log barrier function

Related

• A Generalized Reduced Linear Program for Markov Decision Processes
• Partitioned Linear Programming Approximations for MDPs
• Analysis of approximate linear programming solution to Markov decision problem with log barrier function
• Practical Linear Value-approximation Techniques for First-order MDPs
• Approximate Linear Programming for First-order MDPs