論文の概要: Analysis of approximate linear programming solution to Markov decision problem with log barrier function
- arxiv url: http://arxiv.org/abs/2509.19800v1
- Date: Wed, 24 Sep 2025 06:36:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-25 20:53:19.706856
- Title: Analysis of approximate linear programming solution to Markov decision problem with log barrier function
- Title（参考訳）: ログバリア関数を持つマルコフ決定問題に対する近似線形計画解の解析
- Authors: Donghwan Lee, Hyukjun Yang, Bum Geun Park,
- Abstract要約: マルコフ決定問題(MDP)の解決には2つの主要なアプローチがある。
動的プログラミング法は最も広く用いられ、古典的・近代的な強化学習(RL)の基礎を形成している。
本稿では,LPベースのMDPをより効果的かつ実用的な方法で解くための理論的基盤を確立する。
- 参考スコア（独自算出の注目度）: 6.752424962104772
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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（参考訳）: マルコフ決定問題(MDP)の解法にはベルマン方程式に基づく動的プログラミングと線形プログラミング(LP)の2つの主要なアプローチがある。
動的プログラミング法は最も広く用いられ、古典的・近代的な強化学習(RL)の基礎を形成している。
対照的に、LPベースの手法は一般的には採用されていないが、最近オフラインのRLのような文脈で注目されている。
LPに基づく手法の相対的な悪用は、それが不等式制約付き最適化問題に繋がるという事実に起因しており、一般にベルマン方程式に基づく手法と比較して効果的に解決することが困難である。
本研究の目的は,LPベースのMDPをより効果的かつ実用的な方法で解くための理論的基盤を確立することである。
我々のキーとなる考え方は、不等式制約付き最適化で広く使われているログバリア関数を利用して、MPPのLP定式化を制約なし最適化問題に変換することである。
この改質により、勾配降下により近似解を容易に得ることができる。
手法は単純に見えるかもしれないが、私たちの知識の最も良いところは、このアプローチの完全な理論的解釈がまだ開発されていないことである。
この論文は、このギャップを埋めることを目的としている。
関連論文リスト
- Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳（メタデータ） (2024-03-06T04:43:22Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Adaptive pruning-based Newton's method for distributed learning [14.885388389215587]
本稿では,分散適応ニュートン学習(textttDANL)という,新規で効率的なアルゴリズムを提案する。
textttDANLは、利用可能なリソースに効率よく適応し、高い効率を維持しながら、線形収束率を達成する。
実験により、textttDANLは、効率的な通信と異なるデータセット間の強い性能で線形収束を実現することが示された。
論文 参考訳（メタデータ） (2023-08-20T04:01:30Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳（メタデータ） (2022-09-15T07:22:58Z) - Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
マルコフ決定過程(MDP)における次元性の呪いに、低ランク表現を利用することで対処することが一般的である。
本稿では,効率的な表現学習を可能にしつつ,正規化を自動的に保証する線形MDPの代替的定義について考察する。
いくつかのベンチマークにおいて、既存の最先端モデルベースおよびモデルフリーアルゴリズムよりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-07-14T18:18:02Z) - Learning to Reformulate for Linear Programming [11.628932152805724]
本稿では,リニアプログラミング(LP)の強化学習に基づく再構成手法を提案する。
本研究では,2つの公共研究用LPデータセットと,実運用シナリオから収集した大規模LPデータセットに対して提案手法を実装した。
論文 参考訳（メタデータ） (2022-01-17T04:58:46Z) - Logistic Q-Learning [87.00813469969167]
MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。
提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
論文 参考訳（メタデータ） (2020-10-21T17:14:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。