論文の概要: On the Complexity Gap Between POMDPs and Multi-Environment POMDPs

• arxiv url: http://arxiv.org/abs/2610.15010v1
• Date: Sat, 10 Oct 2026 15:45:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.142462
• Title: On the Complexity Gap Between POMDPs and Multi-Environment POMDPs
• Title（参考訳）: POMDPとマルチ環境PMDPの複雑性ギャップについて
• Abstract要約: 我々は、ME-POMDPの複雑さの展望を、どのサブクラスが$mathsfPSPACE$-completenessを保持するかを識別することによって拡張する。 まず, ブラインドMDPと決定論的POMDPの$mathsfNP$-completenessを, ある閉包混合条件を用いて証明する。 次に、その閉包条件を満たさないサブクラスに対して$mathsfPSPACE$-completenessを証明する。
• 参考スコア（独自算出の注目度）: 29.63953552645502
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-environment POMDPs (ME-POMDPs) generalize POMDPs by encoding a finite set of possible environments, capturing model uncertainty. The finite-horizon robust reward maximization problem for a ME-POMDP asks for a policy that maximizes reward in the worst environment, and recent work has shown this problem to be $\mathsf{PSPACE}$-complete. We expand the complexity landscape of ME-POMDPs by identifying which subclasses retain this $\mathsf{PSPACE}$-completeness. In particular, we take subclasses of POMDPs that are tractable in the single-environment case, and investigate the computational complexity of these classes when extended to the multi-environment setting. We first prove the $\mathsf{NP}$-completeness of multi-environment blind MDPs and deterministic POMDPs using a certain closure-under-mixture condition. We then prove $\mathsf{PSPACE}$-completeness for a range of subclasses that do not satisfy that closure condition, yielding new complexity results for multi-observation POMDPs. Finally, we show existential theory of the reals ($\exists \mathbb{R}$)-completeness for numerous ME-POMDP problems under time-dependent Markovian policies or finite-state controllers that are $\mathsf{NP}$-complete for standard POMDPs. These results reveal a subtle relationship between POMDP and ME-POMDP complexity that depends heavily on the subclasses involved.
• Abstract（参考訳）: 多環境PMMDP (ME-POMDPs) は、可能な環境の有限セットを符号化し、モデルの不確実性を捉えることにより、POMDPsを一般化する。 ME-POMDPの有限水平ロバスト報酬最大化問題では、最悪の環境で報酬を最大化するポリシーが求められており、最近の研究でこの問題は$\mathsf{PSPACE}$-completeであることが示されている。 我々は、この$\mathsf{PSPACE}$-completenessをどのサブクラスが保持するかを特定することで、ME-POMDPの複雑さの展望を広げる。 特に, 単一環境の場合において抽出可能なPOMDPのサブクラスを取り上げ, 多環境設定に拡張した場合の計算複雑性について検討する。 まず,マルチ環境ブラインドMDPと決定論的POMDPの$\mathsf{NP}$完全性を,ある閉包混合条件を用いて証明する。 次に、閉包条件を満たさない一連のサブクラスに対して$\mathsf{PSPACE}$-completenessを証明し、多可観測POMDPに対する新しい複雑性結果を得る。 最後に、時間依存マルコフポリシーや標準POMDPに対して$\mathsf{NP}$-completeである有限状態コントローラの下で、多数の ME-POMDP 問題に対する実数 (\exists \mathbb{R}$)-完全性について存在理論を示す。 これらの結果から,POMDPとME-POMDPの複雑性の微妙な関係が明らかとなった。

関連論文リスト

• Multi-Environment POMDPs with Finite-Horizon Objectives [12.26940285300484]
  有限水平目標を用いたMEPOMDPにおける最適値とポリシーの計算に着目する。 本研究の主な成果は,(1) MEPOMDPのより一般的な設定ではPSPACE完全であること,(2)実用的アルゴリズムを提示し,古典的なベンチマークで評価し,これまでに知られていたアルゴリズムよりもはるかに優れていること,である。
  論文  参考訳（メタデータ） (2026-05-08T10:14:03Z)
• 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 Sample Complexity Bounds for Constrained Average-Reward MDPs [6.237808815887583]
  制約付き平均回帰MDPにおける$epsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。 本結果は,制約付き平均回帰MDPの複雑性の理解における理論的ギャップを埋めるものである。
  論文  参考訳（メタデータ） (2025-09-20T09:19:42Z)
• Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
  そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。 我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
  論文  参考訳（メタデータ） (2023-10-31T19:26:36Z)
• Optimality Guarantees for Particle Belief Approximation of POMDPs [55.83001584645448]
  部分的に観測可能なマルコフ決定プロセス(POMDP)は、現実の意思決定と制御の問題に対する柔軟な表現を提供する。 POMDPは、特に状態と観測空間が連続的またはハイブリッドである場合、解決するのが非常に難しい。 本稿では,これらのアルゴリズムが使用する粒子フィルタリング手法の近似誤差を特徴付ける理論を提案する。
  論文  参考訳（メタデータ） (2022-10-10T21:11:55Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。 我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-21T16:43:03Z)
• Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning [82.31436758872715]
  我々は,環境相互作用の$O(1)$のエピソードのみを用いて,同一のPAC保証を実現するアルゴリズムを開発した。 値関数と有限水平マルコフ決定過程の接続を確立する。
  論文  参考訳（メタデータ） (2021-11-01T00:21:24Z)

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

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