論文の概要: Provable Reinforcement Learning with a Short-Term Memory

• arxiv url: http://arxiv.org/abs/2202.03983v1
• Date: Tue, 8 Feb 2022 16:39:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-09 14:12:53.412114
• Title: Provable Reinforcement Learning with a Short-Term Memory
• Title（参考訳）: 短期記憶を用いた確率的強化学習
• Authors: Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, Sobhan Miryoosefi
• Abstract要約: 我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
• 参考スコア（独自算出の注目度）: 68.00677878812908
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Real-world sequential decision making problems commonly involve partial observability, which requires the agent to maintain a memory of history in order to infer the latent states, plan and make good decisions. Coping with partial observability in general is extremely challenging, as a number of worst-case statistical and computational barriers are known in learning Partially Observable Markov Decision Processes (POMDPs). Motivated by the problem structure in several physical applications, as well as a commonly used technique known as "frame stacking", this paper proposes to study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. We establish a set of upper and lower bounds on the sample complexity for learning near-optimal policies for this class of problems in both tabular and rich-observation settings (where the number of observations is enormous). In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially with the short length $m$ rather than the problem horizon, and is independent of the number of observations. Our results show that a short-term memory suffices for reinforcement learning in these environments.
• Abstract（参考訳）: 現実のシーケンシャルな意思決定問題は、一般に部分的な可観測性を伴うため、エージェントは潜伏状態や計画、適切な決定を行うために、履歴の記憶を維持する必要がある。 部分的に観測可能なマルコフ決定過程(POMDPs)の学習において、多くの最悪の統計的および計算上の障壁が知られているため、一般に部分観測可能性を伴う符号化は非常に難しい。 いくつかの物理応用における問題構造と「フレーム・スタックング」と呼ばれる一般的な手法によって動機づけられた本論文では,最新の短い長さ$m$の履歴から潜在状態が復号できるPMDPの新たなサブクラスを研究することを提案する。 表式およびリッチ観測設定(観測回数が巨大である場合)において、この種類の問題に対する最適に近いポリシーを学ぶために、サンプル複雑性の上限と下限を設定する。 特に,リッチ・オブザーブレーション・セッティングでは,問題地平線ではなく,短期の$m$で指数関数的にスケールし,観測数に依存しない,新しい「モーメントマッチング」手法を用いて新しいアルゴリズムを開発した。 これらの環境において,短期記憶が強化学習に十分であることを示す。

関連論文リスト

• Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
  この研究は、正則決定過程(RDP)と呼ばれる非マルコフ環境のクラスにおけるオフライン強化学習(RL)を研究する。 インスは、未来の観測と過去の相互作用からの報酬の未知の依存を実験的に捉えることができる。 多くのアルゴリズムは、まずこの未知の依存関係を自動学習技術を用いて再構築する。
  論文  参考訳（メタデータ） (2024-09-04T14:26:58Z)
• Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
  我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。 このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
  論文  参考訳（メタデータ） (2024-06-12T06:41:47Z)
• Trade-off Between Dependence and Complexity for Nonparametric Learning -- an Empirical Process Approach [10.27974860479791]
  データが時間的依存を示す多くのアプリケーションでは、対応する経験的プロセスは理解されていない。 標準的な$beta/rho$-mixingの仮定の下では、経験過程の期待上限に一般化する。 長距離依存下であっても、i.d.設定と同じ速度で達成できることが示される。
  論文  参考訳（メタデータ） (2024-01-17T05:08:37Z)
• Learning in POMDPs is Sample-Efficient with Hindsight Observability [36.66596305441365]
  POMDPは、幅広い意思決定問題を捉えているが、難易度の結果は、学習が本質的に部分観測可能であるため、単純な設定でも難易度が高いことを示唆している。 多くの現実的な問題では、より多くの情報が明らかにされるか、学習プロセスのどこかの時点で計算できる。 我々は、学習者が学習中にのみ潜伏状態を明らかにするPOMDPとして設定(setshort)を定式化する。
  論文  参考訳（メタデータ） (2023-01-31T18:54:36Z)
• Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making [48.87943416098096]
  本稿では,一般的な逐次決定のための簡単な学習アルゴリズムを提案する。 我々は,OMLEが極めて豊富な逐次的意思決定問題のクラスにおいて,ほぼ最適ポリシーを学習していることを証明する。
  論文  参考訳（メタデータ） (2022-09-29T17:56:25Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
  古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。 次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
  論文  参考訳（メタデータ） (2020-10-07T01:33:06Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)

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

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