論文の概要: Sample-Efficient Reinforcement Learning Is Feasible for Linearly
Realizable MDPs with Limited Revisiting
- arxiv url: http://arxiv.org/abs/2105.08024v1
- Date: Mon, 17 May 2021 17:22:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-18 17:18:16.619283
- Title: Sample-Efficient Reinforcement Learning Is Feasible for Linearly
Realizable MDPs with Limited Revisiting
- Title（参考訳）: 限定再考を伴う線形実現可能なMDPのためのサンプル効率の良い強化学習
- Authors: Gen Li, Yuxin Chen, Yuejie Chi, Yuantao Gu, Yuting Wei
- Abstract要約: 線形関数表現のような低複雑度モデルがサンプル効率のよい強化学習を可能にする上で重要な役割を果たしている。
本稿では,オンライン/探索的な方法でサンプルを描画するが,制御不能な方法で以前の状態をバックトラックし,再訪することができる新しいサンプリングプロトコルについて検討する。
この設定に合わせたアルゴリズムを開発し、特徴次元、地平線、逆の準最適ギャップと実際にスケールするサンプル複雑性を実現するが、状態/作用空間のサイズではない。
- 参考スコア（独自算出の注目度）: 60.98700344526674
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Low-complexity models such as linear function representation play a pivotal
role in enabling sample-efficient reinforcement learning (RL). The current
paper pertains to a scenario with value-based linear representation, which
postulates the linear realizability of the optimal Q-function (also called the
"linear $Q^{\star}$ problem"). While linear realizability alone does not allow
for sample-efficient solutions in general, the presence of a large
sub-optimality gap is a potential game changer, depending on the sampling
mechanism in use. Informally, sample efficiency is achievable with a large
sub-optimality gap when a generative model is available but is unfortunately
infeasible when we turn to standard online RL settings.
In this paper, we make progress towards understanding this linear $Q^{\star}$
problem by investigating a new sampling protocol, which draws samples in an
online/exploratory fashion but allows one to backtrack and revisit previous
states in a controlled and infrequent manner. This protocol is more flexible
than the standard online RL setting, while being practically relevant and far
more restrictive than the generative model. We develop an algorithm tailored to
this setting, achieving a sample complexity that scales polynomially with the
feature dimension, the horizon, and the inverse sub-optimality gap, but not the
size of the state/action space. Our findings underscore the fundamental
interplay between sampling protocols and low-complexity structural
representation in RL.
- Abstract（参考訳）: 線形関数表現などの低複雑さモデルは、サンプル効率強化学習(RL)の実現に重要な役割を果たしている。
現在の論文は、最適q関数の線形実現可能性("linear $q^{\star}$ problem")を仮定した値に基づく線形表現のシナリオに関するものである。
線形実現可能性だけではサンプリング効率のよい解は認められないが、大規模な準最適ギャップの存在は、使用中のサンプリング機構に依存する潜在的なゲームチェンジャーである。
形式的には、サンプル効率は、生成モデルが利用可能である場合、大きなサブ最適ギャップで達成できるが、標準のオンラインRL設定に切り替える場合、残念ながら実現不可能である。
本稿では,オンライン/探索的な方法でサンプルを描画するが,制御不能な方法で以前の状態をバックトラックし,再訪することが可能な新しいサンプリングプロトコルを検討することにより,この線形な$q^{\star}$ 問題を理解するための進展について述べる。
このプロトコルは、標準のオンラインRL設定よりも柔軟であり、生成モデルよりも事実上関連性があり、はるかに制限的である。
この設定に合わせたアルゴリズムを開発し, 特徴次元, 地平線, 逆部分最適化ギャップと多項式的にスケールする, 状態/動作空間のサイズではなく, サンプル複雑性を達成する。
本研究は,RLにおけるサンプリングプロトコルと低複素構造表現の基本的な相互作用を裏付けるものである。
関連論文リスト
- Offline RL via Feature-Occupancy Gradient Ascent [9.983014605039658]
大規模無限水平割引マルコフ決定過程(MDP)におけるオフライン強化学習の研究
我々は,特徴占有空間における勾配上昇の形式を実行する新しいアルゴリズムを開発した。
結果として得られた単純なアルゴリズムは、強い計算とサンプルの複雑さの保証を満たすことを示す。
論文 参考訳（メタデータ） (2024-05-22T15:39:05Z) - Sample Complexity of Kernel-Based Q-Learning [11.32718794195643]
任意に大規模に割引されたMDPにおいて,$epsilon$-optimal Policyを求める非パラメトリックQ-ラーニングアルゴリズムを提案する。
我々の知る限りでは、このような一般モデルの下では、有限サンプルの複雑さを示す最初の結果である。
論文 参考訳（メタデータ） (2023-02-01T19:46:25Z) - Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling [28.371541697552928]
一般作用空間を線形埋め込み性条件下で保持する非線形関数近似の最初の結果を示す。
最悪の場合,RL問題のランクパラメータでスケールが保証される。
論文 参考訳（メタデータ） (2022-03-15T20:50:26Z) - 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) - An Exponential Lower Bound for Linearly-Realizable MDPs with Constant
Suboptimality Gap [66.75488143823337]
また, 指数的標本複雑度は, 一定の準最適ギャップを仮定しても, 未だに保持していることを示した。
おそらく驚くことに、これはオンラインrl設定と生成モデル設定の指数関数的な分離を意味する。
論文 参考訳（メタデータ） (2021-03-23T17:05:54Z) - Bilinear Classes: A Structural Framework for Provable Generalization in
RL [119.42509700822484]
Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。
このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。
我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
論文 参考訳（メタデータ） (2021-03-19T16:34:20Z) - Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve
Optimism, Embrace Virtual Curvature [61.22680308681648]
決定論的報酬を有する1層ニューラルネットバンディットにおいても,グローバル収束は統計的に難解であることを示す。
非線形バンディットとRLの両方に対して,オンラインモデル学習者による仮想アセンジ(Virtual Ascent with Online Model Learner)というモデルベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-08T12:41:56Z) - Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement
Learning? [30.065091907118827]
本研究は,マルコフ決定過程(MDP)における$epsilon$-optimal Policyの発見の複雑さについて考察する。
実験モデルを構築し,任意のプラグインソルバを用いて実験モデルを計画するプラグインソルバ手法を用いてこの問題を解決する。
プラグインアプローチはサンプル効率も向上し,強化学習のためのモデルベースアルゴリズムを設計するための柔軟なアプローチを提供する。
論文 参考訳（メタデータ） (2020-10-12T13:13:01Z) - Learning the Linear Quadratic Regulator from Nonlinear Observations [135.66883119468707]
我々は、LQR with Rich Observations(RichLQR)と呼ばれる連続制御のための新しい問題設定を導入する。
本設定では, 線形力学と二次的コストを有する低次元連続潜伏状態によって環境を要約する。
本結果は,システムモデルと一般関数近似における未知の非線形性を持つ連続制御のための,最初の証明可能なサンプル複雑性保証である。
論文 参考訳（メタデータ） (2020-10-08T07:02:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。