論文の概要: A Fully Polynomial Time Approximation Scheme for Fixed-Horizon
Constrained Stochastic Shortest Path Problem under Local Transitions
- arxiv url: http://arxiv.org/abs/2204.04780v1
- Date: Sun, 10 Apr 2022 22:08:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-13 08:02:27.493381
- Title: A Fully Polynomial Time Approximation Scheme for Fixed-Horizon
Constrained Stochastic Shortest Path Problem under Local Transitions
- Title（参考訳）: 局所遷移下における固定水平拘束確率的最短経路問題の完全多項式時間近似法
- Authors: Majid Khonji
- Abstract要約: 固定水平制約最短経路問題 (C-SSP) は、特定の運用制約下での環境における計画の定式化である。
この研究は、(C)C-SSPの重要な変種を局所遷移の下で考慮し、状態到達性が特定の局所性を示すような幅広いSSP問題を捉えている。
- 参考スコア（独自算出の注目度）: 2.512827436728378
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The fixed-horizon constrained stochastic shortest path problem (C-SSP) is a
formalism for planning in stochastic environments under certain operating
constraints. Chance-Constrained SSP (CC-SSP) is a variant that allows bounding
the probability of constraint violation, which is desired in many
safety-critical applications. This work considers an important variant of
(C)C-SSP under local transition, capturing a broad class of SSP problems where
state reachability exhibit a certain locality. Only a constant number of states
can share some subsequent states. (C)C-SSP 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-SSP that computes (near) optimal
deterministic policies. Such an algorithm is the best approximation algorithm
attainable in theory
- Abstract（参考訳）: 固定水平制約付き確率的最短経路問題 (C-SSP) は、特定の操作制約の下で確率的環境を計画するための形式主義である。
Chance-Constrained SSP (CC-SSP) は、多くの安全クリティカルなアプリケーションで望まれる制約違反の確率を制限できる変種である。
この研究は、(C)C-SSPの重要な変種を局所遷移の下で考慮し、状態到達性が特定の局所性を示すような幅広いSSP問題を捉える。
一定の数の州だけがその後の州を共有できる。
(C)C-SSPは2の計画地平線であってもNP-Hardである。
そこで本研究では, (c)c-ssp に対する多項式時間近似スキームを提案する。
このようなアルゴリズムは理論上達成可能な最善の近似アルゴリズムである
関連論文リスト
- 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) - Recursively-Constrained Partially Observable Markov Decision Processes [13.8724466775267]
C-POMDPは連続的な決定ステップに対して最適なサブ構造特性に反することを示す。
C-POMDPのオンライン再計画は、この違反による不整合のため、しばしば効果がない。
本稿では,C-POMDPに履歴に依存したコスト制約を課す再帰的制約付きPOMDPを提案する。
論文 参考訳（メタデータ） (2023-10-15T00:25:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。