論文の概要: 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)
• Online POMDP Planning with Anytime Deterministic Optimality Guarantees [13.824288326240927]
  近似解と最適解の間の離散POMDPに対する決定論的関係を導出する。 我々の導出は、新しいアルゴリズムセットの道を提供し、既存のアルゴリズムにアタッチできることを示します。
  論文  参考訳（メタデータ） (2023-10-03T04:40:38Z)
• Optimality Guarantees for Particle Belief Approximation of POMDPs [55.83001584645448]
  部分的に観測可能なマルコフ決定プロセス(POMDP)は、現実の意思決定と制御の問題に対する柔軟な表現を提供する。 POMDPは、特に状態と観測空間が連続的またはハイブリッドである場合、解決するのが非常に難しい。 本稿では,これらのアルゴリズムが使用する粒子フィルタリング手法の近似誤差を特徴付ける理論を提案する。
  論文  参考訳（メタデータ） (2022-10-10T21:11:55Z)
• 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)
• Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes [0.0]
  システム力学と測定チャネルモデルが知られていると仮定したPOMDPの計画問題について検討する。 軽度非線形フィルタ安定性条件下で近似的信念モデルに対する最適ポリシーを求める。 また、有限ウィンドウメモリサイズと近似誤差境界を関連づけた収束結果のレートを確立する。
  論文  参考訳（メタデータ） (2020-10-15T00:37:51Z)

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

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