論文の概要: Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model

• arxiv url: http://arxiv.org/abs/2005.12900v6
• Date: Fri, 16 Sep 2022 00:48:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-29 00:07:49.607480
• Title: Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Title（参考訳）: 生成モデルを用いたモデルベース強化学習におけるサンプルサイズ障壁の破断
• Authors: Gen Li, Yuting Wei, Yuejie Chi, Yuxin Chen
• Abstract要約: 本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
• 参考スコア（独自算出の注目度）: 50.38446482252857
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator). We first consider $\gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $\mathcal{S}$ and action space $\mathcal{A}$. Despite a number of prior works tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy is yet to be determined. In particular, all prior results suffer from a severe sample size barrier, in the sense that their claimed statistical guarantees hold only when the sample size exceeds at least $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^2}$. The current paper overcomes this barrier by certifying the minimax optimality of two algorithms -- a perturbed model-based algorithm and a conservative model-based algorithm -- as soon as the sample size exceeds the order of $\frac{|\mathcal{S}||\mathcal{A}|}{1-\gamma}$ (modulo some log factor). Moving beyond infinite-horizon MDPs, we further study time-inhomogeneous finite-horizon MDPs, and prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level. To the best of our knowledge, this work delivers the first minimax-optimal guarantees that accommodate the entire range of sample sizes (beyond which finding a meaningful policy is information theoretically infeasible).
• Abstract（参考訳）: 本稿では,生成モデル(あるいはシミュレータ)へのアクセスを想定した強化学習のサンプル効率について述べる。 まず、状態空間 $\mathcal{S}$ および作用空間 $\mathcal{A}$ で、$\gamma$-discounted infinite-horizon Markov decision process (MDPs) を考える。 この問題に取り組む多くの先行研究にもかかわらず、サンプルの複雑さと統計的正確性の間のトレードオフの完全な図はまだ決定されていない。 特に、全ての先行結果は、それらの主張する統計的保証が少なくとも$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^2}$を超える場合にのみ保持されるという意味で、厳しいサンプルサイズ障壁に悩まされる。 現在の論文では、サンプルサイズが$\frac{|\mathcal{s}|||\mathcal{a}|}{1-\gamma}$ (modulo some log factor) のオーダーを超えると、2つのアルゴリズム -- 摂動モデルベースアルゴリズムと保守モデルベースアルゴリズム -- の最小最適性を確認することで、この障壁を克服している。 無限水平 MDP を超えて、時間的不均一な有限水平 MDP を更に研究し、モデルに基づく計画アルゴリズムが目的の精度レベルから最小値-最適サンプル複雑性を達成するのに十分であることを示す。 私たちの知る限りでは、この研究はサンプルサイズの範囲全体に対応する最初のミニマックス最適保証を提供する(意味のあるポリシーを見つけることは理論的には不可能である)。

関連論文リスト

• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• 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)
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning? [30.065091907118827]
  本研究は,マルコフ決定過程(MDP)における$epsilon$-optimal Policyの発見の複雑さについて考察する。 実験モデルを構築し,任意のプラグインソルバを用いて実験モデルを計画するプラグインソルバ手法を用いてこの問題を解決する。 プラグインアプローチはサンプル効率も向上し,強化学習のためのモデルベースアルゴリズムを設計するための柔軟なアプローチを提供する。
  論文  参考訳（メタデータ） (2020-10-12T13:13:01Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• 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)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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