論文の概要: Settling the Sample Complexity of Online Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2307.13586v3
• Date: Thu, 23 May 2024 16:31:50 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-26 21:02:52.477823
• Title: Settling the Sample Complexity of Online Reinforcement Learning
• Title（参考訳）: オンライン強化学習におけるサンプル複雑度の設定
• Authors: Zihan Zhang, Yuxin Chen, Jason D. Lee, Simon S. Du,
• Abstract要約: バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
• 参考スコア（独自算出の注目度）: 92.02082223856479
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A central issue lying at the heart of online reinforcement learning (RL) is data efficiency. While a number of recent works achieved asymptotically minimal regret in online RL, the optimality of these results is only guaranteed in a ``large-sample'' regime, imposing enormous burn-in cost in order for their algorithms to operate optimally. How to achieve minimax-optimal regret without incurring any burn-in cost has been an open problem in RL theory. We settle this problem for the context of finite-horizon inhomogeneous Markov decision processes. Specifically, we prove that a modified version of Monotonic Value Propagation (MVP), a model-based algorithm proposed by \cite{zhang2020reinforcement}, achieves a regret on the order of (modulo log factors) \begin{equation*} \min\big\{ \sqrt{SAH^3K}, \,HK \big\}, \end{equation*} where $S$ is the number of states, $A$ is the number of actions, $H$ is the planning horizon, and $K$ is the total number of episodes. This regret matches the minimax lower bound for the entire range of sample size $K\geq 1$, essentially eliminating any burn-in requirement. It also translates to a PAC sample complexity (i.e., the number of episodes needed to yield $\varepsilon$-accuracy) of $\frac{SAH^3}{\varepsilon^2}$ up to log factor, which is minimax-optimal for the full $\varepsilon$-range. Further, we extend our theory to unveil the influences of problem-dependent quantities like the optimal value/cost and certain variances. The key technical innovation lies in the development of a new regret decomposition strategy and a novel analysis paradigm to decouple complicated statistical dependency -- a long-standing challenge facing the analysis of online RL in the sample-hungry regime.
• Abstract（参考訳）: オンライン強化学習(RL)の中心にある問題は、データ効率である。 オンラインRLにおいて、最近の多くの研究は漸近的に最小限の後悔を達成したが、これらの結果の最適性は 'large-sample'' 体制でのみ保証され、アルゴリズムが最適に動作するために膨大なバーンインコストが課される。 バーンインコストを発生させることなく、最小限の最適後悔をいかに達成するかは、RL理論において未解決の問題である。 この問題を有限水平不均一マルコフ決定過程の文脈で解決する。 具体的には,modulo log factor) \begin{equation*} \min\big\{ \sqrt{SAH^3K}, \,HK \big\}, \end{equation*} ここで$S$は状態数であり,$A$は行動数であり,$H$は計画的地平線である。 この後悔は、サンプルサイズの全範囲で$K\geq 1$のminimaxローバウンドと一致し、本質的にはバーンイン要件を排除している。 また、PACサンプルの複雑さ(すなわち$\varepsilon$-accuracy)を$\frac{SAH^3}{\varepsilon^2}$に変換する。 さらに、最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張した。 重要な技術的革新は、新しい後悔の分解戦略と、複雑な統計的依存を分離するための新しい分析パラダイムの開発にある。

関連論文リスト

• Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds [24.571530193140916]
  エントロピーリスク尺度(EntRM)が目的である有限エピソードマルコフ決定過程を考察する。 モデルフリーとモデルベースを含む2つの異なるスキームを用いて最適化を実装する2つの新しいDRLアルゴリズムを提案する。 いずれも$tildemathcalO(fracexp(|beta|H)-1|beta|HsqrtS2AK)$ regret upper bound, where $S$, $A$, $K$, $H$は数値を表す。
  論文  参考訳（メタデータ） (2022-10-25T14:30:48Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees [43.13918072870693]
  強化学習(OPSRL)のための楽観的後部サンプリングアルゴリズムを提案する。 殆どの$widetildemathcalO(sqrtH3SAT)$ ignoring $textpolylog(HSAT)$ termsにおいて、高い確率で再帰的な順序境界を保証する。 我々の境界は位数$Omega(sqrtH3SAT)$の下位境界と一致し、Agrawal と Jia が提起した開問題に答える。
  論文  参考訳（メタデータ） (2022-09-28T20:49:34Z)
• 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)
• 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)

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

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