Analysis of approximate linear programming solution to Markov decision problem with log barrier function
This work addresses a theoretical gap for researchers in reinforcement learning, particularly in offline RL, but is incremental as it builds on existing LP and barrier function methods.
The paper tackles the challenge of solving Markov decision problems (MDPs) using linear programming (LP) methods, which are less common due to inequality constraints, by reformulating the LP with a log-barrier function into an unconstrained optimization problem solvable via gradient descent, establishing a theoretical foundation for this approach.
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.