論文の概要: Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction
- arxiv url: http://arxiv.org/abs/2006.03041v3
- Date: Sun, 8 Aug 2021 03:42:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 10:02:16.744861
- Title: Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction
- Title（参考訳）: 非同期Q-Learningのサンプル複雑性:シャーパ解析とばらつき低減
- Authors: Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, Yuxin Chen
- Abstract要約: 非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
- 参考スコア（独自算出の注目度）: 63.41789556777387
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Asynchronous Q-learning aims to learn the optimal action-value function (or
Q-function) of a Markov decision process (MDP), based on a single trajectory of
Markovian samples induced by a behavior policy. Focusing on a
$\gamma$-discounted MDP with state space $\mathcal{S}$ and action space
$\mathcal{A}$, we demonstrate that the $\ell_{\infty}$-based sample complexity
of classical asynchronous Q-learning --- namely, the number of samples needed
to yield an entrywise $\varepsilon$-accurate estimate of the Q-function --- is
at most on the order of $\frac{1}{\mu_{\min}(1-\gamma)^5\varepsilon^2}+
\frac{t_{mix}}{\mu_{\min}(1-\gamma)}$ up to some logarithmic factor, provided
that a proper constant learning rate is adopted. Here, $t_{mix}$ and
$\mu_{\min}$ denote respectively the mixing time and the minimum state-action
occupancy probability of the sample trajectory. The first term of this bound
matches the sample complexity in the synchronous case with independent samples
drawn from the stationary distribution of the trajectory. The second term
reflects the cost taken for the empirical distribution of the Markovian
trajectory to reach a steady state, which is incurred at the very beginning and
becomes amortized as the algorithm runs. Encouragingly, the above bound
improves upon the state-of-the-art result \cite{qu2020finite} by a factor of at
least $|\mathcal{S}||\mathcal{A}|$ for all scenarios, and by a factor of at
least $t_{mix}|\mathcal{S}||\mathcal{A}|$ for any sufficiently small accuracy
level $\varepsilon$. Further, we demonstrate that the scaling on the effective
horizon $\frac{1}{1-\gamma}$ can be improved by means of variance reduction.
- Abstract（参考訳）: 非同期Q-ラーニングは、行動ポリシーによって誘導されるマルコフサンプルの1つの軌道に基づいて、マルコフ決定過程(MDP)の最適アクション値関数(またはQ-関数)を学習することを目的としている。
Focusing on a $\gamma$-discounted MDP with state space $\mathcal{S}$ and action space $\mathcal{A}$, we demonstrate that the $\ell_{\infty}$-based sample complexity of classical asynchronous Q-learning --- namely, the number of samples needed to yield an entrywise $\varepsilon$-accurate estimate of the Q-function --- is at most on the order of $\frac{1}{\mu_{\min}(1-\gamma)^5\varepsilon^2}+ \frac{t_{mix}}{\mu_{\min}(1-\gamma)}$ up to some logarithmic factor, provided that a proper constant learning rate is adopted.
ここで、$t_{mix}$ と $\mu_{\min}$ はそれぞれ標本軌道の混合時間と最小状態-作用占有確率を表す。
この境界の第一項は、軌道の定常分布から独立したサンプルが引き出される同期の場合のサンプル複雑性と一致する。
第2の用語は、マルコフ軌道が定常状態に達するための経験的分布に要するコストを反映している。
上記の境界は、すべてのシナリオに対して少なくとも$|\mathcal{S}||\mathcal{A}|$の係数と、少なくとも$t_{mix}|\mathcal{S}|||\mathcal{A}|$の係数により、任意の十分小さな精度レベルで$\varepsilon$の係数によって、最先端の結果 \cite{qu2020finite} により改善される。
さらに,実効的なhorizon $\frac{1}{1-\gamma}$のスケーリングが分散還元によって改善できることを実証する。
関連論文リスト
- Optimal Sample Complexity of Reinforcement Learning for Uniformly
Ergodic Discounted Markov Decision Processes [0.0]
マルコフ決定過程(MDP)における無限地平線割引報酬を制御するための最適なサンプル複雑性理論を考える。
多くの興味ある応用において、最適政策(または全ての政策)は混合を誘導する。
我々の分析は、一般状態空間 MDP の関連問題の研究に使用できるため、独立した関心を持つ再生型アイデアに基づいている。
論文 参考訳（メタデータ） (2023-02-15T05:43:17Z) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳（メタデータ） (2021-12-29T14:47:56Z) - 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) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳（メタデータ） (2021-02-12T14:22:05Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳（メタデータ） (2020-12-21T03:10:21Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。