論文の概要: A Fully Polynomial Time Approximation Scheme for Constrained MDPs and
Stochastic Shortest Path under Local Transitions
- arxiv url: http://arxiv.org/abs/2204.04780v2
- Date: Tue, 18 Apr 2023 17:16:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-19 18:59:42.655089
- Title: A Fully Polynomial Time Approximation Scheme for Constrained MDPs and
Stochastic Shortest Path under Local Transitions
- Title（参考訳）: 局所遷移下における制約付きMDPと確率的最短経路の完全多項式時間近似法
- Authors: Majid Khonji
- Abstract要約: 我々は,(C)C-MDPの構造,特に局所遷移を伴う重要な変種について検討した。
本研究では,(C)C-MDPの最適決定性ポリシを(ほぼ)計算する完全時間近似手法を提案する。
- 参考スコア（独自算出の注目度）: 2.512827436728378
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The fixed-horizon constrained Markov Decision Process (C-MDP) is a well-known
model for planning in stochastic environments under operating constraints.
Chance-Constrained MDP (CC-MDP) is a variant that allows bounding the
probability of constraint violation, which is desired in many safety-critical
applications. CC-MDP can also model a class of MDPs, called Stochastic Shortest
Path (SSP), under dead-ends, where there is a trade-off between the
probability-to-goal and cost-to-goal. This work studies the structure of
(C)C-MDP, particularly an important variant that involves local transition. In
this variant, the state reachability exhibits a certain degree of locality and
independence from the remaining states. More precisely, the number of states,
at a given time, that share some reachable future states is always constant.
(C)C-MDP under local transition is NP-Hard even for a planning horizon of two.
In this work, we propose a fully polynomial-time approximation scheme for
(C)C-MDP that computes (near) optimal deterministic policies. Such an algorithm
is among the best approximation algorithm attainable in theory and gives
insights into the approximability of constrained MDP and its variants.
- Abstract（参考訳）: 固定水平制約マルコフ決定過程 (C-MDP) は, 動作制約下での確率環境における計画モデルとしてよく知られている。
Chance-Constrained MDP (CC-MDP) は、多くの安全クリティカルなアプリケーションで望まれる制約違反の確率を制限できる変種である。
CC-MDPはまた、Stochastic Shortest Path (SSP)と呼ばれるMDPのクラスをデッドエンドの下でモデル化することができる。
この研究は(C)C-MDPの構造、特に局所遷移を伴う重要な変種を研究する。
この変種では、州の到達性は、残りの州からある程度の局所性と独立性を示す。
より正確には、ある時点で到達可能な将来の状態を共有する状態の数は、常に一定である。
(C)C-MDPは2の計画地平線であってもNP-Hardである。
そこで本研究では, (c)c-mdp に対する多項式時間近似スキームを提案する。
このようなアルゴリズムは理論上最良の近似アルゴリズムの一つであり、制約付きmdpとその変異の近似可能性に関する洞察を与える。
関連論文リスト
- Robust Counterfactual Inference in Markov Decision Processes [1.5197843979051473]
現在のアプローチでは、カウンターファクトを識別するために特定の因果モデルを想定している。
反実遷移確率の厳密な境界を計算できる新しい非パラメトリック手法を提案する。
論文 参考訳（メタデータ） (2025-02-19T13:56:20Z) - Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。
このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
論文 参考訳（メタデータ） (2024-06-12T06:41:47Z) - Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。
我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
論文 参考訳（メタデータ） (2023-10-31T19:26:36Z) - Twice Regularized Markov Decision Processes: The Equivalence between
Robustness and Regularization [64.60253456266872]
マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。
規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。
ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
論文 参考訳（メタデータ） (2023-03-12T13:03:28Z) - Optimality Guarantees for Particle Belief Approximation of POMDPs [55.83001584645448]
部分的に観測可能なマルコフ決定プロセス(POMDP)は、現実の意思決定と制御の問題に対する柔軟な表現を提供する。
POMDPは、特に状態と観測空間が連続的またはハイブリッドである場合、解決するのが非常に難しい。
本稿では,これらのアルゴリズムが使用する粒子フィルタリング手法の近似誤差を特徴付ける理論を提案する。
論文 参考訳（メタデータ） (2022-10-10T21:11:55Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳（メタデータ） (2022-09-15T07:22:58Z) - Common Information based Approximate State Representations in
Multi-Agent Reinforcement Learning [3.086462790971422]
我々は、分散化されたポリシーを構築可能な共通およびプライベートな状態表現を近似した汎用的な圧縮フレームワークを開発する。
その結果,「分散分散実行の分散学習」方式で,実用的に有用なディープMARLネットワーク構造の設計に光を当てた。
論文 参考訳（メタデータ） (2021-10-25T02:32:06Z) - Twice regularized MDPs and the equivalence between robustness and
regularization [65.58188361659073]
報酬を損なうMDPのポリシーイテレーションは、正規化MDPと同じ時間複雑性を持つことを示す。
正規化MDPを2倍の正規化MDPに一般化する。
論文 参考訳（メタデータ） (2021-10-12T18:33:45Z) - Modular Deep Reinforcement Learning for Continuous Motion Planning with
Temporal Logic [59.94347858883343]
本稿では,マルコフ決定過程(MDP)をモデルとした自律動的システムの運動計画について検討する。
LDGBA と MDP の間に組込み製品 MDP (EP-MDP) を設計することである。
モデルフリー強化学習(RL)のためのLDGBAベースの報酬形成と割引スキームは、EP-MDP状態にのみ依存する。
論文 参考訳（メタデータ） (2021-02-24T01:11:25Z) - Efficient Planning in Large MDPs with Weak Linear Function Approximation [4.56877715768796]
大規模意思決定プロセス(MDP)は、MDPの状態を独立して計画アルゴリズムを必要とする。
線形値関数近似を用いたMDPの計画問題を考える。
論文 参考訳（メタデータ） (2020-07-13T04:40:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。