A Linearly Relaxed Approximate Linear Program for Markov Decision Processes
Not on the map. Why?
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.
Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Apr 2017.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 2; 2023: 2; 2024: 0; 2025: 2; 2026: 1.
9 papers.
- 2022Proximal Point Imitation Learningcited by 25
- 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
- 2021Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrationscited by 9
- 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
- 2023Convex Q Learning in a Stochastic Environment: Extended Versioncited by 5
- 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 4
- 2025Analysis of approximate linear programming solution to Markov decision problem with log barrier functioncited by 1
- 2023Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processescited by 0
- 2026Lifted Bellman Linear Programming for Offline Reinforcement Learningcited by 0
- 2026Lifted Bellman Linear Programming for Offline Reinforcement Learning21 Sep 2026
- 2025Analysis of approximate linear programming solution to Markov decision problem with log barrier function24 Sep 2025
- 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation14 Feb 2025
- 2023Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processes20 Nov 2023
- 2023Convex Q Learning in a Stochastic Environment: Extended Version10 Sep 2023
- 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization21 Oct 2022
- 2022Proximal Point Imitation Learning22 Sep 2022
- 2021Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations28 Dec 2021
- 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function3 Feb 2021