論文の概要: Theoretical Hardness and Tractability of POMDPs in RL with Partial
Online State Information
- arxiv url: http://arxiv.org/abs/2306.08762v2
- Date: Thu, 12 Oct 2023 00:07:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-14 15:11:49.557436
- 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 のみであっても,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 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 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 key insights in our lower
bound design, we find that there exist important tractable classes of POMDPs
even with only partial OSI. In particular, for two novel classes of POMDPs with
partial OSI, we provide new algorithms that are proved to be near-optimal by
establishing new regret upper and lower bounds.
- Abstract（参考訳）: 部分可観測マルコフ決定プロセス(pomdps)は多くの実世界のアプリケーションを取り込むために広く適用されてきた。
しかし、既存の理論的な結果から、一般的なpomdpsでの学習は難解であり、主な課題は潜在状態情報がないことである。
ここでの基本的な問題は、トラクタビリティを実現するのに、オンライン状態情報(OSI)がどの程度十分なのかということだ。
完全なOSIがなければ,POMDPに対する$\epsilon$-Optimal Policy Solutionを得るには,指数関数的にスケールするサンプルの複雑さが必要である。
しかしながら、低境界設計における重要な洞察に触発されて、部分的OSIのみであっても、PMDPの重要な抽出可能なクラスが存在することが判明した。
特に、部分 OSI を持つ 2 つの新しい POMDP クラスに対して、新しい後悔の上と下の境界を確立することで、ほぼ最適であることが証明された新しいアルゴリズムを提供する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。