論文の概要: Computing the Reachability Value of Posterior-Deterministic POMDPs

• arxiv url: http://arxiv.org/abs/2602.07473v1
• Date: Sat, 07 Feb 2026 10:09:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.641081
• Title: Computing the Reachability Value of Posterior-Deterministic POMDPs
• Title（参考訳）: 後決定論的POMDPの到達可能性値の計算
• Authors: Nathanaël Fijalkow, Arka Ghosh, Roman Kniazev, Guillermo A. Pérez, Pierre Vandenhove,
• Abstract要約: 後決定性POMDPは,新しいPOMDPのクラスである。 後決定論的POMDPに対して、与えられた状態に到達する最大確率は任意の精度で近似できることを示す。
• 参考スコア（独自算出の注目度）: 10.025098857952628
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Partially observable Markov decision processes (POMDPs) are a fundamental model for sequential decision-making under uncertainty. However, many verification and synthesis problems for POMDPs are undecidable or intractable. Most prominently, the seminal result of Madani et al. (2003) states that there is no algorithm that, given a POMDP and a set of target states, can compute the maximal probability of reaching the target states, or even approximate it up to a non-trivial constant. This is in stark contrast to fully observable Markov decision processes (MDPs), where the reachability value can be computed in polynomial time. In this work, we introduce posterior-deterministic POMDPs, a novel class of POMDPs. Our main technical contribution is to show that for posterior-deterministic POMDPs, the maximal probability of reaching a given set of states can be approximated up to arbitrary precision. A POMDP is posterior-deterministic if the next state can be uniquely determined by the current state, the action taken, and the observation received. While the actual state is generally uncertain in POMDPs, the posterior-deterministic property tells us that once the true state is known it remains known forever. This simple and natural definition includes all MDPs and captures classical non-trivial examples such as the Tiger POMDP (Kaelbling et al. 1998), making it one of the largest known classes of POMDPs for which the reachability value can be approximated.
• Abstract（参考訳）: 部分的に観測可能なマルコフ決定プロセス(POMDP)は、不確実性の下でのシーケンシャルな意思決定の基本的なモデルである。 しかし、POMDPの検証と合成の問題は決定不可能または難解である。 最も顕著なことに、Madani et al (2003) のセミナルな結果は、POMDP とターゲット状態の集合が与えられたとき、ターゲット状態に達する最大確率を計算したり、あるいは非自明な定数まで近似するアルゴリズムが存在しないことを述べている。 これは完全に観測可能なマルコフ決定過程 (MDP) とは対照的であり、到達可能性値は多項式時間で計算できる。 本稿では,新しいPOMDPのクラスである後決定論的POMDPを紹介する。 我々の主な技術的貢献は、後決定論的POMDPに対して、与えられた状態に到達する最大確率を任意の精度で近似できることを示すことである。 POMDPは、次の状態が現在の状態、取られたアクション、受信された観察によって一意に決定できる場合、後決定的である。 実際の状態は一般にPOMDPでは不確実であるが、後決定論的な性質から、真の状態が知られると、それが永久に知られていることが分かる。 この単純で自然な定義は全ての MDP を含み、Tiger POMDP (Kaelbling et al 1998) のような古典的な非自明な例を捉え、到達可能性値が近似できるPOMDPのクラスの中では最大である。

関連論文リスト

• Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability [29.63953552645502]
  多環境POMDP(ME-POMDP)は、標準POMDPを離散モデル不確実性で拡張する。 本稿では, ME-POMDP を初期信念の集合を用いて POMDP に一般化可能であることを示す。 次に、AB-POMDPのロバストなポリシーを計算するために、正確で近似的な(ポイントベース)アルゴリズムを考案する。
  論文  参考訳（メタデータ） (2025-10-27T18:24:11Z)
• Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
  我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。 このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
  論文  参考訳（メタデータ） (2024-06-12T06:41:47Z)
• Online POMDP Planning with Anytime Deterministic Optimality Guarantees [13.824288326240927]
  近似解と最適解の間の離散POMDPに対する決定論的関係を導出する。 我々の導出は、新しいアルゴリズムセットの道を提供し、既存のアルゴリズムにアタッチできることを示します。
  論文  参考訳（メタデータ） (2023-10-03T04:40:38Z)
• 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)
• PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDP [0.34410212782758043]
  我々は,未知のMDPにおいて,平均ペイオフをほぼ正確に計算する最初のアルゴリズムを提供する。 状態空間に関する知識は一切必要とせず、最小遷移確率の低い境界のみである。 提案アルゴリズムは, ほぼ正しいPAC境界を提供するだけでなく, 標準ベンチマークで実験を行うことにより, その実用性を実証する。
  論文  参考訳（メタデータ） (2022-06-03T09:13:27Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• A Fully Polynomial Time Approximation Scheme for Constrained MDPs and Stochastic Shortest Path under Local Transitions [2.512827436728378]
  我々は,(C)C-MDPの構造,特に局所遷移を伴う重要な変種について検討した。 本研究では,(C)C-MDPの最適決定性ポリシを(ほぼ)計算する完全時間近似手法を提案する。
  論文  参考訳（メタデータ） (2022-04-10T22:08:33Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。 我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-21T16:43:03Z)
• Planning in Observable POMDPs in Quasipolynomial Time [21.03037504572896]
  我々は観測可能なPOMDPの計画のための準ポリノミカル時間アルゴリズムを開発した。 我々は、状態上のよく分断された分布が観察上のよく分断された分布をもたらすと仮定する。 観測可能なPOMDPの指数時間仮説の下での計画に適合する硬さを実証する。
  論文  参考訳（メタデータ） (2022-01-12T23:16:37Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討 LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。 鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
  論文  参考訳（メタデータ） (2021-02-09T16:49:58Z)
• Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes [0.0]
  システム力学と測定チャネルモデルが知られていると仮定したPOMDPの計画問題について検討する。 軽度非線形フィルタ安定性条件下で近似的信念モデルに対する最適ポリシーを求める。 また、有限ウィンドウメモリサイズと近似誤差境界を関連づけた収束結果のレートを確立する。
  論文  参考訳（メタデータ） (2020-10-15T00:37:51Z)

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

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