論文の概要: Settling the Sample Complexity of Model-Based Offline Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2204.05275v1
• Date: Mon, 11 Apr 2022 17:26:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-12 16:02:30.083058
• Title: Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
• Title（参考訳）: モデルベースオフライン強化学習のサンプル複雑性の解消
• Authors: Gen Li and Laixi Shi and Yuxin Chen and Yuejie Chi and Yuting Wei
• Abstract要約: オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
• 参考スコア（独自算出の注目度）: 51.47633778534544
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper is concerned with offline reinforcement learning (RL), which learns using pre-collected data without further exploration. Effective offline RL would be able to accommodate distribution shift and limited data coverage. However, prior algorithms or analyses either suffer from suboptimal sample complexities or incur high burn-in cost to reach sample optimality, thus posing an impediment to efficient offline RL in sample-starved applications. We demonstrate that the model-based (or "plug-in") approach achieves minimax-optimal sample complexity without burn-in cost for tabular Markov decision processes (MDPs). Concretely, consider a finite-horizon (resp. $\gamma$-discounted infinite-horizon) MDP with $S$ states and horizon $H$ (resp. effective horizon $\frac{1}{1-\gamma}$), and suppose the distribution shift of data is reflected by some single-policy clipped concentrability coefficient $C^{\star}_{\text{clipped}}$. We prove that model-based offline RL yields $\varepsilon$-accuracy with a sample complexity of \[ \begin{cases} \frac{H^{4}SC_{\text{clipped}}^{\star}}{\varepsilon^{2}} & (\text{finite-horizon MDPs}) \frac{SC_{\text{clipped}}^{\star}}{(1-\gamma)^{3}\varepsilon^{2}} & (\text{infinite-horizon MDPs}) \end{cases} \] up to log factor, which is minimax optimal for the entire $\varepsilon$-range. Our algorithms are "pessimistic" variants of value iteration with Bernstein-style penalties, and do not require sophisticated variance reduction.
• Abstract（参考訳）: 本稿では,事前収集データを用いて学習するオフライン強化学習(RL)について検討する。 効果的なオフラインRLは、分散シフトと限られたデータカバレッジに対応できる。 しかしながら、以前のアルゴリズムや解析では、サンプルの最適性に到達するために、サブオプティカルなサンプルの複雑さや高いバーンインコストが伴うため、サンプルが飢えたアプリケーションでは、効率的なオフラインrlの障害となる。 モデルベース(もしくは「プラグイン」)アプローチは,表型マルコフ決定プロセス(MDP)のバーンインコストを伴わずに,最小限のサンプル複雑性を実現する。 具体的には有限水平(resp)を考える。 $\gamma$-discounted infinite-horizon) mdpには$s$ statesとhorizon $h$ (resp.com)がある。 有効地平線$\frac{1}{1-\gamma}$) と仮定すると、データの分散シフトは、ある単一ポリスクリッピングされた集中係数$C^{\star}_{\text{clipped}}$によって反映される。 モデルベースオフライン RL は \[ \begin{cases} \frac{H^{4}SC_{\text{clipped}}^{\star}}{\varepsilon^{2}} & (\text{finite-horizon MDPs}) \frac{SC_{\text{clipped}}^{\star}}{(1-\gamma)^{3}\varepsilon^{2}} & (\text{infinite-horizon MDPs}) \end{cases} \] のサンプル複雑性で $\varepsilon$-accuracy を得る。 我々のアルゴリズムは、ベルンシュタイン型のペナルティを持つ値反復の「悲観的」な変種であり、高度な分散還元を必要としない。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model [3.749193647980305]
  本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。 モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
  論文  参考訳（メタデータ） (2021-05-28T17:49:39Z)
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction [36.027428493021716]
  Off-Policy Double Variance Reductionは、オフラインRLのための分散化に基づく新しいアルゴリズムである。 OPDVRは$widetildeO(H2/d_mepsilon2)$ episodes of offline dataで$epsilon$-optimal Policyを確実に特定している。 また、OPDVRは、代替設定下でのレート最適化サンプルの複雑さも達成できることを示す。
  論文  参考訳（メタデータ） (2021-02-02T20:47:35Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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