論文の概要: Efficient Solving of Large Single Input Superstate Decomposable Markovian Decision Process

• arxiv url: http://arxiv.org/abs/2508.00816v1
• Date: Fri, 01 Aug 2025 17:49:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-04 18:08:53.977779
• Title: Efficient Solving of Large Single Input Superstate Decomposable Markovian Decision Process
• Title（参考訳）: 大入力超状態分解型マルコフ決定過程の効率的な解法
• Authors: Youssef Ait El Mahjoub, Jean-Michel Fourneau, Salma Alouah,
• Abstract要約: ベルマン動的プログラミングアルゴリズムの重要なステップはポリシー評価である。 我々は,この構造に基づく,正確かつ効率的な政策評価手法を開発した。 これにより、平均値と割引値の両方の報酬 MDP に適用可能なスケーラブルなソリューションが得られる。
• 参考スコア（独自算出の注目度）: 1.17431678544333
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Solving Markov Decision Processes (MDPs) remains a central challenge in sequential decision-making, especially when dealing with large state spaces and long-term optimization criteria. A key step in Bellman dynamic programming algorithms is the policy evaluation, which becomes computationally demanding in infinite-horizon settings such as average-reward or discounted-reward formulations. In the context of Markov chains, aggregation and disaggregation techniques have for a long time been used to reduce complexity by exploiting structural decompositions. In this work, we extend these principles to a structured class of MDPs. We define the Single-Input Superstate Decomposable Markov Decision Process (SISDMDP), which combines Chiu's single-input decomposition with Robertazzi's single-cycle recurrence property. When a policy induces this structure, the resulting transition graph can be decomposed into interacting components with centralized recurrence. We develop an exact and efficient policy evaluation method based on this structure. This yields a scalable solution applicable to both average and discounted reward MDPs.
• Abstract（参考訳）: マルコフ決定プロセス(MDP)の解決は、特に大きな状態空間と長期最適化基準を扱う場合、シーケンシャルな意思決定において中心的な課題である。 ベルマン動的プログラミングアルゴリズムの重要なステップはポリシー評価であり、これは平均逆数や割引逆数のような無限水平設定で計算的に要求される。 マルコフ連鎖の文脈では、凝集と分解技術は構造的分解を利用して複雑さを減らすために長い間使われてきた。 本研究では,これらの原則をMDPの構造化クラスに拡張する。 我々は,Chiuの単一インプット分解とRobertazziの単一サイクル再帰特性を組み合わせた,単一入力状態分解可能マルコフ決定過程(SISDMDP)を定義する。 ポリシーがこの構造を誘導すると、結果として生じる遷移グラフは、集中的な再帰を伴う相互作用するコンポーネントに分解される。 我々は,この構造に基づく,正確かつ効率的な政策評価手法を開発した。 これにより、平均値と割引値の両方の報酬 MDP に適用可能なスケーラブルなソリューションが得られる。

関連論文リスト

• Efficient Strategy Synthesis for MDPs via Hierarchical Block Decomposition [47.123254940289726]
  ソフトウェア製品ラインとロボティクスはマルコフ決定プロセス(MDP)を利用して不確実性を捉え、シーケンシャルな意思決定問題を解析する。 従来の政策合成法の有用性にもかかわらず、それらは大きな状態空間にスケールできない。 提案手法は, MDPを動的に精製し, 最も脆弱な MDP 領域を反復的に選択することにより, 大規模な MDP における政策合成を高速化する。
  論文  参考訳（メタデータ） (2025-06-21T19:03:03Z)
• Recursively-Constrained Partially Observable Markov Decision Processes [13.8724466775267]
  C-POMDPは連続的な決定ステップに対して最適なサブ構造特性に反することを示す。 C-POMDPのオンライン再計画は、この違反による不整合のため、しばしば効果がない。 本稿では,C-POMDPに履歴に依存したコスト制約を課す再帰的制約付きPOMDPを提案する。
  論文  参考訳（メタデータ） (2023-10-15T00:25:07Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization [64.60253456266872]
  マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。 規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。 ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
  論文  参考訳（メタデータ） (2023-03-12T13:03:28Z)
• Policy Gradient for Rectangular Robust Markov Decision Processes [62.397882389472564]
  我々は,長方形ロバストなマルコフ決定過程(MDP)を効率的に解く政策ベース手法であるロバストなポリシー勾配(RPG)を導入する。 結果のRPGは、非ロバストな等価値と同じ時間のデータから推定することができる。
  論文  参考訳（メタデータ） (2023-01-31T12:40:50Z)
• First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
  我々はロバストマルコフ決定過程(MDP)の解法を考える。 MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。 $(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
  論文  参考訳（メタデータ） (2022-09-21T18:10:28Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Twice regularized MDPs and the equivalence between robustness and regularization [65.58188361659073]
  報酬を損なうMDPのポリシーイテレーションは、正規化MDPと同じ時間複雑性を持つことを示す。 正規化MDPを2倍の正規化MDPに一般化する。
  論文  参考訳（メタデータ） (2021-10-12T18:33:45Z)
• Goal Kernel Planning: Linearly-Solvable Non-Markovian Policies for Logical Tasks with Goal-Conditioned Options [54.40780660868349]
  我々はLinearly-Solvable Goal Kernel Dynamic Programming (LS-GKDP)と呼ばれる合成フレームワークを導入する。 LS-GKDPは、Linearly-Solvable Markov Decision Process (LMDP)形式とOptions Framework of Reinforcement Learningを組み合わせたものである。 本稿では,目標カーネルを持つLMDPが,タスク接地によって定義された低次元部分空間におけるメタポリティシの効率的な最適化を実現する方法を示す。
  論文  参考訳（メタデータ） (2020-07-06T05:13:20Z)
• Partial Policy Iteration for L1-Robust Markov Decision Processes [13.555107578858307]
  本稿では、ロバストなMDPの共通クラスを解くための新しい効率的なアルゴリズムについて述べる。 我々は、ロバストなMDPのための部分ポリシーイテレーション、新しい、効率的で柔軟な、一般的なポリシーイテレーションスキームを提案する。 実験結果から,提案手法は最先端手法よりも桁違いに高速であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-16T19:50:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。