Abstract
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.
Abstract (translated)
解决马尔可夫决策问题（MDPs）主要有两种方法：基于贝尔曼方程的动态规划和线性规划（LP）。动态规划方法是最广泛使用的方法，构成了经典和现代强化学习（RL）的基础。相比之下，虽然线性规划方法被采用得较少，但它们最近在离线强化学习等领域引起了关注。线性规划方法相对较少被使用的部分原因在于，它会导致一个带有不等式约束的优化问题，而相对于基于贝尔曼方程的方法而言，这类问题通常更难有效解决。 本文旨在为以更加有效和实用的方式解决基于LP的MDPs提供理论基础。我们的核心思想是利用广泛用于处理不等式约束优化问题中的对数障碍函数，将MDP的线性规划表示转换为无约束优化问题。这种重述使得通过梯度下降方法可以轻松获得近似解。虽然这种方法可能看似简单，据我们所知，迄今为止还没有对其进行全面的理论解释。本文旨在填补这一空白。
URL
https://arxiv.org/abs/2509.19800
