対数バリア関数によるマルコフ決定問題の近似線形計画法解の分析
なぜ重要か: 企業や社会への影響が見込まれ、一般メディアにも波及する可能性があります。
arXiv:2509.19800v1 発表種別: 新規
要旨: マルコフ決定過程(MDP)を解くには、ベルマン方程式に基づく動的計画法と線形計画法(LP)の2つの主要なアプローチが存在する。動的計画法は最も広く用いられており、古典的および現代的な強化学習(RL)の基礎を形成する。対照的に、LPに基づく方法はあまり用いられてこなかったが、近年、オフラインRLなどの文脈で注目を集めている。LPに基づく方法の相対的な利用不足は、不等式制約最適化問題につながるという事実によるものであり、これは一般にベルマン方程式に基づく方法と比較して効果的に解くことがより困難である。本論文の目的は、LPに基づくMDPをより効果的かつ実践的な方法で解くための理論的基礎を確立することである。我々の主要なアイデアは、不等式制約最適化で広く用いられている対数バリア関数を活用し、MDPのLP定式化を無制約最適化問題に変換することである。この定式化により、勾配降下法を用いて近似解を容易に得ることができる。この方法は単純に見えるかもしれないが、我々の知る限り、このアプローチの徹底的な理論的解釈はまだ開発されていない。本論文は、このギャップを埋めることを目的とする。
原文（英語）を表示
Title (EN): Analysis of approximate linear programming solution to Markov decision problem with log barrier function
arXiv:2509.19800v1 Announce Type: new
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.
Published: 2025-09-24 19:00 UTC