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

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

## Key facts

- Cited by 1 papers 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 (most cited first, 17 of 17)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Reinforcement Learning via Fenchel-Rockafellar Duality](https://mlsanity.com/paper/2001.01866/) (2020)
- [Dual RL: Unification and New Methods for Reinforcement and Imitation Learning](https://mlsanity.com/paper/2302.08560/) (2023)
- [Logistic Q-Learning](https://mlsanity.com/paper/2010.11151/) (2020)
- [Offline Primal-Dual Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2305.12944/) (2023)
- [Constrained Reinforcement Learning with Smoothed Log Barrier Function](https://mlsanity.com/paper/2403.14508/) (2024)
- [Linear Programming for Large-Scale Markov Decision Problems](https://mlsanity.com/paper/1402.6763/) (2014)
- [Scalable Bilinear π Learning Using State and Action Features](https://mlsanity.com/paper/1804.10328/) (2018)
- [Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations](https://mlsanity.com/paper/2112.14004/) (2021)
- [A Linearly Relaxed Approximate Linear Program for Markov Decision Processes](https://mlsanity.com/paper/1704.02544/) (2017)
- [Faster saddle-point optimization for solving large-scale Markov decision processes](https://mlsanity.com/paper/1909.10904/) (2019)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [Stochastic Primal-Dual Q-Learning](https://mlsanity.com/paper/1810.08298/) (2018)
- [A Note on Optimization Formulations of Markov Decision Processes](https://mlsanity.com/paper/2012.09417/) (2020)
- [Constrained Reinforcement Learning for Safe Heat Pump Control](https://mlsanity.com/paper/2409.19716/) (2024)

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

- [Lifted Bellman Linear Programming for Offline Reinforcement Learning](https://mlsanity.com/paper/2609.24489/) (2026)

## 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.