論文の概要: Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning
- arxiv url: http://arxiv.org/abs/2102.06548v1
- Date: Fri, 12 Feb 2021 14:22:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-15 20:07:10.739193
- Title: Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning
- Title（参考訳）: Q-Learningのサンプル複雑度における水平依存性の強調
- Authors: Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, Yuejie Chi
- Abstract要約: この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
- 参考スコア（独自算出の注目度）: 59.71676469100807
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Q-learning, which seeks to learn the optimal Q-function of a Markov decision
process (MDP) in a model-free fashion, lies at the heart of reinforcement
learning. When it comes to the synchronous setting (such that independent
samples for all state-action pairs are drawn from a generative model in each
iteration), substantial progress has been made recently towards understanding
the sample efficiency of Q-learning. To yield an entrywise
$\varepsilon$-accurate estimate of the optimal Q-function, state-of-the-art
theory requires at least an order of
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^5\varepsilon^{2}}$ samples for a
$\gamma$-discounted infinite-horizon MDP with state space $\mathcal{S}$ and
action space $\mathcal{A}$. In this work, we sharpen the sample complexity of
synchronous Q-learning to an order of
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^4\varepsilon^2}$ (up to some
logarithmic factor) for any $0<\varepsilon <1$, leading to an order-wise
improvement in terms of the effective horizon $\frac{1}{1-\gamma}$. Analogous
results are derived for finite-horizon MDPs as well. Our finding unveils the
effectiveness of vanilla Q-learning, which matches that of speedy Q-learning
without requiring extra computation and storage. A key ingredient of our
analysis lies in the establishment of novel error decompositions and
recursions, which might shed light on how to analyze finite-sample performance
of other Q-learning variants.
- Abstract（参考訳）: モデルフリーの方法でマルコフ決定プロセス(MDP)の最適なQ機能を学ぶことを目指すQ-ラーニングは、強化学習の中心にあります。
同期設定(全ての状態-作用ペアの独立サンプルが各イテレーションで生成モデルから引き出されるような)に関しては、最近Q-ラーニングのサンプル効率を理解するためにかなりの進歩がなされている。
最適Q関数の射影 $\varepsilon$-accurate 推定を得るためには、最先端の理論では、$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^5\varepsilon^{2}}$ のサンプルを、状態空間 $\mathcal{S}$ とアクション空間 $\mathcal{A}$ を持つ $\gamma$-discounted infinite-horizon MDP の順に求める。
本研究では,任意の0<\varepsilon <1$ に対して,同期型q-ラーニングのサンプル複雑性を$\frac{|\mathcal{s}||\mathcal{a}|}{(1-\gamma)^4\varepsilon^2}$ (いくつかの対数係数まで) に鋭くし,実効的な地平線$\frac{1}{1-\gamma}$ の順に改善する。
解析結果は有限ホライゾン MDP にも導出される。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
我々の分析の重要な要素は、新しい誤り分解と再帰の確立であり、他のQ-ラーニングの有限サンプル性能の分析方法に光を当てる可能性がある。
関連論文リスト
- A finite time analysis of distributed Q-learning [6.663174194579773]
マルチエージェント強化学習(MARL)は、単一エージェント強化学習(RL)の適用において達成された経験的成功によって、目覚ましい関心の高まりを目撃している。
本研究では,多くのエージェントが局所報酬の平均値である中央報酬関数にアクセスせずに逐次意思決定問題を協調的に解決する分散Q-ラーニングシナリオについて考察する。
論文 参考訳（メタデータ） (2024-05-23T00:52:38Z) - 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) - Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。
一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
論文 参考訳（メタデータ） (2023-05-28T19:40:46Z) - A Finite Sample Complexity Bound for Distributionally Robust Q-learning [17.96094201655567]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。
ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。
これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
論文 参考訳（メタデータ） (2023-02-26T01:15:32Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。