用对数障碍函数让马尔可夫决策问题的线性规划求解更高效。
Analysis of approximate linear programming solution to Markov decision problem with log barrier function
- 引入对数障碍函数将不等式约束转为无约束优化。
- 可通过梯度下降快速获得近似解，提升求解效率。
- 理论分析填补了该方法的学术空白，适合优化与强化学习研究者。
求解马尔可夫决策问题（MDP）主要有两种方法：基于贝尔曼方程的动态规划和线性规划（LP）。尽管动态规划方法应用广泛，是经典与现代强化学习的基础，但基于线性规划的方法因面临不等式约束优化问题，求解难度较大，应用较少。近年来，该方法在离线强化学习中重新受到关注。本文旨在建立一种更有效、实用的线性规划求解框架。核心思路是利用在不等式约束优化中广泛应用的对数障碍函数，将MDP的线性规划形式转化为无约束优化问题。这一重构使通过梯度下降获取近似解成为可能。虽然方法看似简单，但据我们所知，其理论基础尚不完善。本文致力于填补这一空白。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。