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

• arxiv url: http://arxiv.org/abs/2306.08762v3
• Date: Mon, 11 Mar 2024 19:13:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-14 02:04:07.855386
• Title: Theoretical Hardness and Tractability of POMDPs in RL with Partial Online State Information
• Title（参考訳）: 部分オンライン状態情報を用いたRLにおけるPMDPの理論的硬さとトラクタビリティ
• Authors: Ming Shi, Yingbin Liang, and Ness Shroff
• Abstract要約: トラクタビリティを実現するのにどの程度のオンライン状態情報(OSI)が十分かを検討する。 部分 OSI のみであっても,POMDP の重要な抽出可能なサブクラスを同定する。 部分OSIを持つ2種類のPOMDPに対して新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 44.72508370978005
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Partially observable Markov decision processes (POMDPs) have been widely applied in various real-world applications. However, existing theoretical results have shown that learning in POMDPs is intractable in the worst case, where the main challenge lies in the lack of latent state information. A key fundamental question here is: how much online state information (OSI) is sufficient to achieve tractability? In this paper, we establish a lower bound that reveals a surprising hardness result: unless we have full OSI, we need an exponentially scaling sample complexity to obtain an $\epsilon$-optimal policy solution for POMDPs. Nonetheless, inspired by the insights in our lower-bound design, we identify important tractable subclasses of POMDPs, even with only partial OSI. In particular, for two subclasses of POMDPs with partial OSI, we provide new algorithms that are proved to be near-optimal by establishing new regret upper and lower bounds. Both our algorithm design and regret analysis involve non-trivial developments for joint OSI query and action control.
• Abstract（参考訳）: 部分的に観測可能なマルコフ決定プロセス(POMDP)は、様々な現実世界の応用に広く応用されている。 しかし,PMDPの学習は,潜伏状態情報の欠如が主な課題である最悪の場合,難易度が高いことが示唆されている。 オンライン状態情報(OSI)がトラクタビリティを実現するのにどの程度の量が必要か? 完全なOSIがなければ,POMDPに対する$\epsilon$-Optimal Policy Solutionを得るには,指数関数的にスケールするサンプルの複雑さが必要である。 しかしながら、低バウンド設計の洞察に触発されて、部分OSIのみであっても、POMDPの重要な抽出可能なサブクラスを特定した。 特に、部分 OSI を持つ POMDP の2つのサブクラスに対して、新しい後悔の上と下の境界を確立することで、ほぼ最適であることが証明された新しいアルゴリズムを提供する。 我々のアルゴリズム設計と後悔分析は、osiクエリとアクション制御の非自明な開発を伴う。

関連論文リスト

• 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)

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

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