論文の概要: Good-for-MDP State Reduction for Stochastic LTL Planning
- arxiv url: http://arxiv.org/abs/2511.09073v1
- Date: Thu, 13 Nov 2025 01:30:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-13 22:34:54.398473
- Title: Good-for-MDP State Reduction for Stochastic LTL Planning
- Title（参考訳）: 確率的LTL計画のためのMDP状態の良質化
- Authors: Christoph Weinhuber, Giuseppe De Giacomo, Yong Li, Sven Schewe, Qiyi Tang,
- Abstract要約: 線形時間論理(LTL)で指定された目標を持つ決定過程(MDP)の計画問題について検討する。
最先端のアプローチはマルコフの公式をグッド・フォー・MDP(GFM)オートマトンに変換し、非決定論の制限形式を特徴とする。
本稿では,オートマチック状態の数を大幅に削減する新しいGCM状態空間削減手法を提案する。
- 参考スコア（独自算出の注目度）: 24.94465882530628
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study stochastic planning problems in Markov Decision Processes (MDPs) with goals specified in Linear Temporal Logic (LTL). The state-of-the-art approach transforms LTL formulas into good-for-MDP (GFM) automata, which feature a restricted form of nondeterminism. These automata are then composed with the MDP, allowing the agent to resolve the nondeterminism during policy synthesis. A major factor affecting the scalability of this approach is the size of the generated automata. In this paper, we propose a novel GFM state-space reduction technique that significantly reduces the number of automata states. Our method employs a sophisticated chain of transformations, leveraging recent advances in good-for-games minimisation developed for adversarial settings. In addition to our theoretical contributions, we present empirical results demonstrating the practical effectiveness of our state-reduction technique. Furthermore, we introduce a direct construction method for formulas of the form $\mathsf{G}\mathsf{F}\varphi$, where $\varphi$ is a co-safety formula. This construction is provably single-exponential in the worst case, in contrast to the general doubly-exponential complexity. Our experiments confirm the scalability advantages of this specialised construction.
- Abstract（参考訳）: マルコフ決定過程(MDP)における確率的計画問題について,LTL(Linear Temporal Logic)で指定された目標を用いて検討する。
State-of-the-artアプローチはLTLの公式を、非決定性の制限形式を特徴とするGood-for-MDP(GFM)オートマトンに変換する。
これらのオートマトンはMDPで構成され、エージェントはポリシー合成中に非決定性を解決することができる。
このアプローチのスケーラビリティに影響を与える大きな要因は、生成されたオートマトンのサイズである。
本稿では, オートマチック状態の数を大幅に削減する新しい GFM 状態空間削減手法を提案する。
提案手法は,対戦型設定のために開発されたゲーム用ゲーム最小化の最近の進歩を生かして,高度な変換の連鎖を用いる。
提案手法の有効性を実証し,提案手法の有効性を実証した。
さらに、$\mathsf{G}\mathsf{F}\varphi$, ここでは$\varphi$は共安全公式である。
この構成は、最悪の場合において、一般的な二重指数複雑性とは対照的に、確実に単指数である。
本実験は, この特化工事のスケーラビリティの利点を実証するものである。
関連論文リスト
- Efficient Solving of Large Single Input Superstate Decomposable Markovian Decision Process [1.17431678544333]
ベルマン動的プログラミングアルゴリズムの重要なステップはポリシー評価である。
我々は,この構造に基づく,正確かつ効率的な政策評価手法を開発した。
これにより、平均値と割引値の両方の報酬 MDP に適用可能なスケーラブルなソリューションが得られる。
論文 参考訳（メタデータ） (2025-08-01T17:49:27Z) - Semiparametric Double Reinforcement Learning with Applications to Long-Term Causal Inference [33.14076284663493]
短期的なデータから長期的な因果効果を推定しなければならない。
MDPはこのような長期的ダイナミクスを捉えるための自然なフレームワークを提供する。
非パラメトリックな実装は時間間重なりの強い仮定を必要とする。
アイソトニックベルマンキャリブレーションに基づく新しいプラグイン推定器を提案する。
論文 参考訳（メタデータ） (2025-01-12T20:35:28Z) - Bellman Diffusion: Generative Modeling as Learning a Linear Operator in the Distribution Space [72.52365911990935]
本稿では,MDPの線形性を維持する新しいDGMフレームワークであるBellman Diffusionを紹介する。
この結果から,ベルマン拡散は分布RLタスクにおける従来のヒストグラムベースベースラインよりも1.5倍高速に収束し,精度の高い画像生成装置であることがわかった。
論文 参考訳（メタデータ） (2024-10-02T17:53:23Z) - Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs [16.49229317664822]
線形決定過程(MDP)を用いた無限水平平均逆強化学習の問題点について検討する。
提案手法は, 平均再帰設定を割引係数で近似し, 楽観的な値反復を適用した。
論文 参考訳（メタデータ） (2024-05-23T20:58:33Z) - Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Twice Regularized Markov Decision Processes: The Equivalence between
Robustness and Regularization [64.60253456266872]
マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。
規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。
ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
論文 参考訳（メタデータ） (2023-03-12T13:03:28Z) - Robust Markov Decision Processes without Model Estimation [32.16801929347098]
堅牢なMDPの適用には,2つの大きな障壁がある。
第一に、ほとんどの研究はモデルベース体制における堅牢なMDPを研究している。
第二に、先行研究は通常、最適な解を得るために強いオラクルを仮定する。
論文 参考訳（メタデータ） (2023-02-02T17:29:10Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-24T13:46:09Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - A conditional one-output likelihood formulation for multitask Gaussian
processes [0.0]
マルチタスクガウス過程(MTGP)は多出力回帰問題に対するガウスプロセスフレームワークの解である。
本稿では,マルチタスク学習を簡略化する新しい手法を提案する。
現状の美術品と計算的に競合していることが示される。
論文 参考訳（メタデータ） (2020-06-05T14:59:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。