論文の概要: Partially Observable RL with B-Stability: Unified Structural Condition
and Sharp Sample-Efficient Algorithms
- arxiv url: http://arxiv.org/abs/2209.14990v1
- Date: Thu, 29 Sep 2022 17:51:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-30 15:59:27.384850
- Title: Partially Observable RL with B-Stability: Unified Structural Condition
and Sharp Sample-Efficient Algorithms
- Title(参考訳): B安定性を持つ部分観測可能なRL:統一構造条件とシャープサンプル効率アルゴリズム
- Authors: Fan Chen, Yu Bai, Song Mei
- Abstract要約: 本稿では、予測状態表現(PSR)の一般設定における部分観測可能RLの3つの側面について述べる。
本稿では,emphB安定性(emphB-stability)と呼ばれるPSRの自然かつ統一的な構造条件を提案する。
本稿では,B-stable PSRが関連する問題パラメータのサンプルで学習できることを示し,上記のサブクラスをインスタンス化すると,サンプルの複雑さが向上することを示した。
- 参考スコア(独自算出の注目度): 25.658930892561735
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Partial Observability -- where agents can only observe partial information
about the true underlying state of the system -- is ubiquitous in real-world
applications of Reinforcement Learning (RL). Theoretically, learning a
near-optimal policy under partial observability is known to be hard in the
worst case due to an exponential sample complexity lower bound. Recent work has
identified several tractable subclasses that are learnable with polynomial
samples, such as Partially Observable Markov Decision Processes (POMDPs) with
certain revealing or decodability conditions. However, this line of research is
still in its infancy, where (1) unified structural conditions enabling
sample-efficient learning are lacking; (2) existing sample complexities for
known tractable subclasses are far from sharp; and (3) fewer sample-efficient
algorithms are available than in fully observable RL.
This paper advances all three aspects above for Partially Observable RL in
the general setting of Predictive State Representations (PSRs). First, we
propose a natural and unified structural condition for PSRs called
\emph{B-stability}. B-stable PSRs encompasses the vast majority of known
tractable subclasses such as weakly revealing POMDPs, low-rank
future-sufficient POMDPs, decodable POMDPs, and regular PSRs. Next, we show
that any B-stable PSR can be learned with polynomial samples in relevant
problem parameters. When instantiated in the aforementioned subclasses, our
sample complexities improve substantially over the current best ones. Finally,
our results are achieved by three algorithms simultaneously: Optimistic Maximum
Likelihood Estimation, Estimation-to-Decisions, and Model-Based Optimistic
Posterior Sampling. The latter two algorithms are new for sample-efficient
learning of POMDPs/PSRs.
- Abstract(参考訳): エージェントがシステムの真の基盤状態に関する部分的情報のみを観察できる部分的可観測性は、Reinforcement Learning (RL)の現実的な応用において、ユビキタスである。
理論的には、部分的可観測性の下での最適に近いポリシーの学習は、指数関数的なサンプルの複雑さにより最悪の場合、難しいことが知られている。
最近の研究では、多項式のサンプルで学習可能ないくつかの扱いやすいサブクラス、例えば部分可観測マルコフ決定プロセス(英語版)(pomdps)を特定している。
しかし,本研究はまだ初期段階であり,(1)サンプル効率の学習が可能な統一的な構造条件が欠如している,(2)既知の抽出可能なサブクラスに対する既存のサンプル複雑度は,十分に観測可能なRLよりも少ない,などの特徴がある。
本稿では, 予測状態表現(PSR)の一般設定における部分観測可能RLの3つの側面について述べる。
まず、自然かつ統一的なPSRの構造条件である「emph{B-stability}」を提案する。
B-stable PSRは、弱いPOMDP、低ランクの将来のPMDP、デオード可能なPOMDP、レギュラーPSRなどの、既知の抽出可能なサブクラスの大部分を含んでいる。
次に,任意のb-stable psrが関連する問題パラメータの多項式サンプルで学習可能であることを示す。
上記のサブクラスでインスタンス化されると、サンプルの複雑さは現在のベストクラスよりも大幅に向上する。
最後に, 最適最大次数推定, 推定対決定, モデルベース最適後サンプリングの3つのアルゴリズムを同時に実現した。
後者の2つのアルゴリズムは、POMDP/PSRのサンプル効率向上のための新しいアルゴリズムである。
関連論文リスト
- Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳(メタデータ) (2023-07-01T18:35:21Z) - GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP,
and Beyond [101.5329678997916]
対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。
本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。
低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
論文 参考訳(メタデータ) (2022-11-03T16:42:40Z) - Optimistic MLE -- A Generic Model-based Algorithm for Partially
Observable Sequential Decision Making [48.87943416098096]
本稿では,一般的な逐次決定のための簡単な学習アルゴリズムを提案する。
我々は,OMLEが極めて豊富な逐次的意思決定問題のクラスにおいて,ほぼ最適ポリシーを学習していることを証明する。
論文 参考訳(メタデータ) (2022-09-29T17:56:25Z) - PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
部分的に観察可能な力学系におけるオンライン強化学習(RL)について検討する。
我々は、他のよく知られたモデルをキャプチャする表現モデルである予測状態表現(PSR)モデルに焦点を当てる。
我々は,サンプル複雑性のスケーリングにおいて,ほぼ最適なポリシを学習可能な,PSRのための新しいモデルベースアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-07-12T17:57:17Z) - Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations [130.66193083412716]
本稿では,関数近似と部分観測可能性の緊張に対処する。
最適ポリシーと値関数は有限メモリヒルベルト・ベルマン作用素の列によって特徴づけられることを示す。
本稿では、カーネル空間(RKHS)の埋め込みを再現することで、これらの演算子の楽観的な推定値を構成するRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-20T21:15:38Z) - When Is Partially Observable Reinforcement Learning Not Scary? [30.754810416907123]
本研究は, 部分的に観測可能な決定過程(POMDP)を学習するには, 最悪の場合, 指数的なサンプル数を必要とすることを示す。
これは、オーバーコンプリートPOMDPの相互作用から学習するための、証明可能な最初の結果である。
論文 参考訳(メタデータ) (2022-04-19T16:08:28Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。
提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文 参考訳(メタデータ) (2020-06-22T17:58:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。