# A Linearly Relaxed Approximate Linear Program for Markov Decision Processes

arXiv: https://arxiv.org/abs/1704.02544 · HTML: https://mlsanity.com/paper/1704.02544/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2017.

## Built on by (most cited first, 9 of 9)

- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function](https://mlsanity.com/paper/2102.02049/) (2021)
- [Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations](https://mlsanity.com/paper/2112.14004/) (2021)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Convex Q Learning in a Stochastic Environment: Extended Version](https://mlsanity.com/paper/2309.05105/) (2023)
- [Analysis of approximate linear programming solution to Markov decision problem with log barrier function](https://mlsanity.com/paper/2509.19800/) (2025)
- [Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processes](https://mlsanity.com/paper/2311.11789/) (2023)
- [Lifted Bellman Linear Programming for Offline Reinforcement Learning](https://mlsanity.com/paper/2609.24489/) (2026)

## Abstract (arXiv)

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.