Analysis of approximate linear programming solution to Markov decision problem with log barrier function
Not on the map. Why?
Abstract (arXiv)
There are two primary approaches to solving Markov decision problems (MDPs): dynamic programming based on the Bellman equation and linear programming (LP). Dynamic programming methods are the most widely used and form the foundation of both classical and modern reinforcement learning (RL). By contrast, LP-based methods have been less commonly employed, although they have recently gained attention in contexts such as offline RL. The relative underuse of the LP-based methods stems from the fact that it leads to an inequality-constrained optimization problem, which is generally more challenging to solve effectively compared with Bellman-equation-based methods. The purpose of this paper is to establish a theoretical foundation for solving LP-based MDPs in a more effective and practical manner. Our key idea is to leverage the log-barrier function, widely used in inequality-constrained optimization, to transform the LP formulation of the MDP into an unconstrained optimization problem. This reformulation enables approximate solutions to be obtained easily via gradient descent. While the method may appear simple, to the best of our knowledge, a thorough theoretical interpretation of this approach has not yet been developed. This paper aims to bridge this gap.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 17 of its 32 references that are in the map. First posted on arXiv 24 Sep 2025.
Builds on
17 of 32 references.
References · 17
- 2015Continuous control with deep reinforcement learningcited by 3,407
- 2021Convex optimizationcited by 2,515
- 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 123
- 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
- 2023Dual RL: Unification and New Methods for Reinforcement and Imitation Learningcited by 48
- 2020Logistic Q-Learningcited by 34
- 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
- 2024Constrained Reinforcement Learning with Smoothed Log Barrier Functioncited by 15
- 2014Linear Programming for Large-Scale Markov Decision Problemscited by 12
- 2018Scalable Bilinear π Learning Using State and Action Featurescited by 10
- 2021Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrationscited by 10
- 2017A Linearly Relaxed Approximate Linear Program for Markov Decision Processescited by 9
5 more
- 2019Faster saddle-point optimization for solving large-scale Markov decision processescited by 8
- 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
- 2018Stochastic Primal-Dual Q-Learningcited by 7
- 2020A Note on Optimization Formulations of Markov Decision Processescited by 7
- 2024Constrained Reinforcement Learning for Safe Heat Pump Controlcited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.
Similar, not cited
Close in wording, no citation either way
- 2026Mathematical methods of reinforcement learning
- 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation
- 2024Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
- 2026End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions
- 2025Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective
- 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
- 2024Strongly-polynomial time and validation analysis of policy gradient methods
- 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs