論文の概要: Efficient Strategy Synthesis for MDPs via Hierarchical Block Decomposition

• arxiv url: http://arxiv.org/abs/2506.17792v1
• Date: Sat, 21 Jun 2025 19:03:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-24 19:06:36.587564
• Title: Efficient Strategy Synthesis for MDPs via Hierarchical Block Decomposition
• Title（参考訳）: 階層的ブロック分解によるMDPの効率的な戦略合成
• Authors: Alexandros Evangelidis, Gricel Vázquez, Simos Gerasimou,
• Abstract要約: ソフトウェア製品ラインとロボティクスはマルコフ決定プロセス(MDP)を利用して不確実性を捉え、シーケンシャルな意思決定問題を解析する。 従来の政策合成法の有用性にもかかわらず、それらは大きな状態空間にスケールできない。 提案手法は, MDPを動的に精製し, 最も脆弱な MDP 領域を反復的に選択することにより, 大規模な MDP における政策合成を高速化する。
• 参考スコア（独自算出の注目度）: 47.123254940289726
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Software-intensive systems, such as software product lines and robotics, utilise Markov decision processes (MDPs) to capture uncertainty and analyse sequential decision-making problems. Despite the usefulness of conventional policy synthesis methods, they fail to scale to large state spaces. Our approach addresses this issue and accelerates policy synthesis in large MDPs by dynamically refining the MDP and iteratively selecting the most fragile MDP regions for refinement. This iterative procedure offers a balance between accuracy and efficiency, as refinement occurs only when necessary. Through a comprehensive empirical evaluation comprising diverse case studies and MDPs up to 1M states, we demonstrate significant performance improvements yielded by our approach compared to the leading probabilistic model checker PRISM (up to 2x), thus offering a very competitive solution for real-world policy synthesis tasks in larger MDPs.
• Abstract（参考訳）: ソフトウェア製品ラインやロボティクスなどのソフトウェア集約型システムは、不確実性を捉え、シーケンシャルな意思決定問題を解析するためにマルコフ決定プロセス(MDP)を利用する。 従来の政策合成法の有用性にもかかわらず、それらは大きな状態空間にスケールできない。 提案手法は, MDPを動的に精製し, 最も脆弱な MDP 領域を反復的に選択することにより, 大規模な MDP における政策合成を高速化する。 この反復的な手順は精度と効率のバランスを与える。 多様なケーススタディと最大100万状態のMDPからなる総合的な実証的評価を通じて、主要な確率モデルチェッカーであるPRISM(2倍)と比較して、我々のアプローチによって得られた顕著な性能改善を実証し、より大規模なMDPにおける実世界の政策合成タスクに対して非常に競争力のあるソリューションを提供する。

関連論文リスト

• Policy Gradient for Robust Markov Decision Processes [16.281897051782863]
  本稿では、ロバストなマルコフ決定過程(MDP)を解くために、新しいポリシー勾配法であるダブルループロバストポリシーミラーDescent(MD)を提案する。 MDは、イテレーション毎の適応耐性を持つポリシー最適化に一般的なミラー降下更新ルールを採用し、グローバルな最適ポリシーへの収束を保証する。 我々は,直接パラメータ化とソフトマックスパラメータ化の両方の下での新しい収束結果を含むMDの包括的解析を行い,トランジションミラー・アセンション(TMA)による内部問題の解に対する新たな洞察を提供する。
  論文  参考訳（メタデータ） (2024-10-29T15:16:02Z)
• Distributionally Robust Model-based Reinforcement Learning with Large State Spaces [55.14361269378122]
  強化学習における3つの大きな課題は、大きな状態空間を持つ複雑な力学系、コストのかかるデータ取得プロセス、トレーニング環境の展開から現実の力学を逸脱させることである。 広範に用いられているKullback-Leibler, chi-square, および全変分不確実性集合の下で, 連続状態空間を持つ分布ロバストなマルコフ決定過程について検討した。 本稿では,ガウス過程と最大分散削減アルゴリズムを用いて,多出力名目遷移力学を効率的に学習するモデルベースアプローチを提案する。
  論文  参考訳（メタデータ） (2023-09-05T13:42:11Z)
• Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity [7.57543767554282]
  本稿では,リスクに敏感なMDPの新たな定式化について紹介し,従来のマルコフリスク尺度と若干異なる方法でリスクを評価する。 両問題に対してポリシー勾配定理を導出し、厳密なポリシー勾配法の勾配支配と大域収束を証明した。 また、サンプルベースのオフライン学習アルゴリズム、すなわちロバスト適応Z反復(RFZI)を提案する。
  論文  参考訳（メタデータ） (2023-06-20T15:51:25Z)
• Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization [64.60253456266872]
  マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。 規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。 ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
  論文  参考訳（メタデータ） (2023-03-12T13:03:28Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• Robust Entropy-regularized Markov Decision Processes [23.719568076996662]
  本稿では,ER-MDPモデルのロバストバージョンについて検討する。 我々は, ER-MDPと頑健な非正規化MDPモデルに係わる重要な特性も設定に保たれることを示す。 私たちは、我々のフレームワークと結果を、価値や(修正された)ポリシーを含む異なるアルゴリズムのスキームに統合する方法を示します。
  論文  参考訳（メタデータ） (2021-12-31T09:50:46Z)
• Twice regularized MDPs and the equivalence between robustness and regularization [65.58188361659073]
  報酬を損なうMDPのポリシーイテレーションは、正規化MDPと同じ時間複雑性を持つことを示す。 正規化MDPを2倍の正規化MDPに一般化する。
  論文  参考訳（メタデータ） (2021-10-12T18:33:45Z)
• Risk-Averse Decision Making Under Uncertainty [18.467950783426947]
  不確実性条件下での意思決定は、マルコフ決定プロセス(MDP)または部分的に観測可能なMDP(POMDP)を介して記述することができる。 本稿では、動的コヒーレントリスク対策の観点から、MDPとPMDPのポリシーを目的と制約で設計する問題について考察する。
  論文  参考訳（メタデータ） (2021-09-09T07:52:35Z)
• Safe Exploration by Solving Early Terminated MDP [77.10563395197045]
  我々は、Early TerminatedP(ET-MDP)の枠組みの下で、安全なRL問題に対処する新しいアプローチを導入する。 まず、ET-MDPを対応するCMDPと同じ最適値関数を持つ非制約アルゴリズムとして定義する。 そこで,文脈モデルに基づく非政治アルゴリズムを提案し,ET-MDPを解き,それに対応するCMDPをより良い性能で解き,学習効率を向上する。
  論文  参考訳（メタデータ） (2021-07-09T04:24:40Z)

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

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