論文の概要: Theoretical Hardness and Tractability of POMDPs in RL with Partial Hindsight State Information

• arxiv url: http://arxiv.org/abs/2306.08762v1
• Date: Wed, 14 Jun 2023 22:20:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-16 17:13:10.554139
• Title: Theoretical Hardness and Tractability of POMDPs in RL with Partial Hindsight State Information
• Title（参考訳）: 部分的後視状態情報を持つRLにおけるPMDPの理論的硬さとトラクタビリティ
• Authors: Ming Shi, Yingbin Liang, and Ness Shroff
• Abstract要約: 部分的HSIにおいても,POMDPの重要な抽出可能なクラスが存在することがわかった。 部分的HSIを持つPOMDPの2つの新しいクラスに対して、我々はほぼ最適であることを示す新しいアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 39.05668389613778
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Partially observable Markov decision processes (POMDPs) have been widely applied to capture many real-world applications. However, existing theoretical results have shown that learning in general POMDPs could be intractable, where the main challenge lies in the lack of latent state information. A key fundamental question here is how much hindsight state information (HSI) is sufficient to achieve tractability. In this paper, we establish a lower bound that reveals a surprising hardness result: unless we have full HSI, we need an exponentially scaling sample complexity to obtain an $\epsilon$-optimal policy solution for POMDPs. Nonetheless, from the key insights in our lower-bound construction, we find that there exist important tractable classes of POMDPs even with partial HSI. In particular, for two novel classes of POMDPs with partial HSI, we provide new algorithms that are shown to be near-optimal by establishing new upper and lower bounds.
• Abstract（参考訳）: 部分可観測マルコフ決定プロセス(pomdps)は多くの実世界のアプリケーションを取り込むために広く適用されてきた。 しかし、既存の理論的な結果から、一般的なpomdpsでの学習は難解であり、主な課題は潜在状態情報がないことである。 ここでの基本的な問題は、トラクタビリティを実現するのに、どれくらいの後方状態情報(HSI)が十分かということだ。 完全HSIがなければ,POMDPに対する$\epsilon$-Optimal Policy Solutionを得るためには,指数関数的にスケールするサンプルの複雑さが必要である。 それでも、下界構造における重要な知見から、部分的HSIであっても、PMDPの重要な抽出可能なクラスが存在することが分かる。 特に、部分的HSIを持つPOMDPの2つの新しいクラスに対して、新しい上界と下界を確立することにより、ほぼ最適であることを示す新しいアルゴリズムを提供する。

関連論文リスト

• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  我々は任意の解法によって生成されるPOMDP実行から高品質なトレースを学習する。 我々は、データと時間効率のIndu Logic Programming(ILP)を利用して、解釈可能な信念に基づくポリシー仕様を生成する。 ASP(Answer Set Programming)で表現された学習は、ニューラルネットワークよりも優れた性能を示し、より少ない計算時間で最適な手作りタスクに類似していることを示す。
  論文  参考訳（メタデータ） (2024-02-29T15:36:01Z)
• Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
  そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。 我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
  論文  参考訳（メタデータ） (2023-10-31T19:26:36Z)
• Posterior Sampling-based Online Learning for Episodic POMDPs [5.797837329787459]
  本研究では,遷移モデルと観測モデルが未知のエピソードPOMDPに対するオンライン学習問題を考察する。 ポストリアサンプリングに基づくPOMDPのための強化学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-16T06:41:13Z)
• Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms [25.658930892561735]
  本稿では、予測状態表現(PSR)の一般設定における部分観測可能RLの3つの側面について述べる。 本稿では,emphB安定性(emphB-stability)と呼ばれるPSRの自然かつ統一的な構造条件を提案する。 本稿では,B-stable PSRが関連する問題パラメータのサンプルで学習できることを示し,上記のサブクラスをインスタンス化すると,サンプルの複雑さが向上することを示した。
  論文  参考訳（メタデータ） (2022-09-29T17:51:51Z)
• Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency [105.17746223041954]
  部分的に観察されたマルコフ決定過程(POMDP)における強化学習は2つの課題に直面している。 しばしば、未来を予測するのに完全な歴史を要し、地平線と指数関数的にスケールするサンプルの複雑さを誘導する。 本稿では,2段階の表現を最適化しながら学習するETC(Embed to Control)という強化学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-26T16:34:46Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity [50.38337893712897]
  線形性を仮定しないMDP上の構造条件であるEPW(Effective Planning Window)条件を導入する。 EPW条件は、この条件を満たすMDPを確実に解くアルゴリズムを提供することで、サンプル効率のよいRLを許容することを示した。 また, EPW のような条件の必要性も示し, わずかに非線形な単純な MDP を効率的にサンプリングできないことを示した。
  論文  参考訳（メタデータ） (2021-06-15T00:06:59Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)

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

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