論文の概要: Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient

• arxiv url: http://arxiv.org/abs/2112.14582v1
• Date: Wed, 29 Dec 2021 14:47:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-30 14:44:21.907680
• Title: Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient
• Title（参考訳）: Polyak-Ruppert平均Q-Leaningは統計的に効率的である
• Authors: Xiang Li, Wenhao Yang, Zhihua Zhang, Michael I. Jordan
• Abstract要約: 我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。 繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。 要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
• 参考スコア（独自算出の注目度）: 90.14768299744792
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study synchronous Q-learning with Polyak-Ruppert averaging (a.k.a., averaged Q-leaning) in a $\gamma$-discounted MDP. We establish asymptotic normality for the averaged iteration $\bar{\boldsymbol{Q}}_T$. Furthermore, we show that $\bar{\boldsymbol{Q}}_T$ is actually a regular asymptotically linear (RAL) estimator for the optimal Q-value function $\boldsymbol{Q}^*$ with the most efficient influence function. It implies the averaged Q-learning iteration has the smallest asymptotic variance among all RAL estimators. In addition, we present a non-asymptotic analysis for the $\ell_{\infty}$ error $\mathbb{E}\|\bar{\boldsymbol{Q}}_T-\boldsymbol{Q}^*\|_{\infty}$, showing it matches the instance-dependent lower bound as well as the optimal minimax complexity lower bound. As a byproduct, we find the Bellman noise has sub-Gaussian coordinates with variance $\mathcal{O}((1-\gamma)^{-1})$ instead of the prevailing $\mathcal{O}((1-\gamma)^{-2})$ under the standard bounded reward assumption. The sub-Gaussian result has potential to improve the sample complexity of many RL algorithms. In short, our theoretical analysis shows averaged Q-Leaning is statistically efficient.
• Abstract（参考訳）: 我々はPolyak-Ruppert平均Q-leaning(平均Q-leaning)を用いた同期Q-learningを$\gamma$-discounted MDPで検討した。 平均的な反復 $\bar{\boldsymbol{q}}_t$ に対する漸近正規性を確立する。 さらに、$\bar{\boldsymbol{Q}}_T$ は、最も効率的な影響関数を持つ最適な Q-値関数 $\boldsymbol{Q}^*$ に対する正則漸近線型(水平)推定器であることを示す。 つまり、平均的なq-learningイテレーションは、すべてのral推定値の中で最小の漸近的分散を持つ。 さらに、$\ell_{\infty}$ error $\mathbb{E}\|\bar{\boldsymbol{Q}}_T-\boldsymbol{Q}^*\|_{\infty}$に対して非漸近解析を行い、インスタンス依存の下界と最適ミニマックス複雑性の下界とを一致させることを示した。 副生成物として、ベルマンノイズは、標準有界報酬仮定の下では、よく見られる$\mathcal{O}((1-\gamma)^{-1})$の代わりに、分散 $\mathcal{O}((1-\gamma)^{-1})$ のガウス座標を持つ。 サブガウスの結果は多くのrlアルゴリズムのサンプル複雑性を改善する可能性がある。 つまり, 平均q-leaningは統計的に効率的である。

関連論文リスト

• Multiple-policy Evaluation via Density Estimation [30.914344538340412]
  本稿では,この問題に対して$mathrmCAESAR$というアルゴリズムを提案する。 低次かつ対数的な$mathrmCAESAR$は、$tildeOleft(fracH4epsilon2sum_h=1Hmax_kin[K]sum_s,afrac(d_hpik(s,a))2mu*_h(s,a)right)$である。
  論文  参考訳（メタデータ） (2024-03-29T23:55:25Z)
• Optimal score estimation via empirical Bayes smoothing [13.685846094715364]
  未知確率分布$rho*$のスコア関数を$n$独立分布および$d$次元における同一分布観測から推定する問題について検討する。 ガウスカーネルに基づく正規化スコア推定器は、一致するミニマックス下界によって最適に示され、この値が得られることを示す。
  論文  参考訳（メタデータ） (2024-02-12T16:17:40Z)
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation [22.51165277694864]
  本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。 LSAは$d$次元線形系の近似解を計算するために用いられる。
  論文  参考訳（メタデータ） (2022-07-10T14:36:04Z)
• Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
  本稿では,リスト復号化可能な線形回帰問題について考察する。 我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
  論文  参考訳（メタデータ） (2021-06-17T17:45:21Z)
• 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)
• Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximation [2.294014185517203]
  本稿では、収束理論を準確率近似に拡張することを目的とする。 強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
  論文  参考訳（メタデータ） (2020-09-30T04:44:45Z)
• 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)
• 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)
• Differentially Quantized Gradient Methods [53.3186247068836]
  微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。 あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
  論文  参考訳（メタデータ） (2020-02-06T20:40:53Z)

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

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