論文の概要: Statistical Efficiency of Distributional Temporal Difference Learning

• arxiv url: http://arxiv.org/abs/2403.05811v3
• Date: Wed, 23 Oct 2024 07:26:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-24 13:53:54.284265
• Title: Statistical Efficiency of Distributional Temporal Difference Learning
• Title（参考訳）: 分布時間差学習の統計的効率
• Authors: Yang Peng, Liangyu Zhang, Zhihua Zhang,
• Abstract要約: 我々は、分布時間差分学習(CTD)と量子時間差分学習(QTD)の有限サンプル性能を解析する。 $gamma$-discounted infinite-horizon decision process に対して、NTD では $tildeOleft(frac1varepsilon2p (1-gamma)2pright)$ が、高い確率で $varepsilon$-optimal estimator を達成するために必要であることを示す。 我々はヒルベルト空間における新しいフリードマンの不等式を確立し、これは独立な関心事である。
• 参考スコア（独自算出の注目度）: 24.03281329962804
• License:
• Abstract: Distributional reinforcement learning (DRL) has achieved empirical success in various domains. One core task in the field of DRL is distributional policy evaluation, which involves estimating the return distribution $\eta^\pi$ for a given policy $\pi$. The distributional temporal difference learning has been accordingly proposed, which is an extension of the temporal difference learning (TD) in the classic RL area. In the tabular case, \citet{rowland2018analysis} and \citet{rowland2023analysis} proved the asymptotic convergence of two instances of distributional TD, namely categorical temporal difference learning (CTD) and quantile temporal difference learning (QTD), respectively. In this paper, we go a step further and analyze the finite-sample performance of distributional TD. To facilitate theoretical analysis, we propose non-parametric distributional TD learning (NTD). For a $\gamma$-discounted infinite-horizon tabular Markov decision process, we show that for NTD we need $\tilde{O}\left(\frac{1}{\varepsilon^{2p}(1-\gamma)^{2p+1}}\right)$ iterations to achieve an $\varepsilon$-optimal estimator with high probability, when the estimation error is measured by the $p$-Wasserstein distance. This sample complexity bound is minimax optimal up to logarithmic factors in the case of the $1$-Wasserstein distance. To achieve this, we establish a novel Freedman's inequality in Hilbert spaces, which would be of independent interest. In addition, we revisit CTD, showing that the same non-asymptotic convergence bounds hold for CTD in the case of the $p$-Wasserstein distance for $p\geq 1$.
• Abstract（参考訳）: 分散強化学習(DRL)は様々な領域で実証的な成功を収めている。 DRL の分野におけるコアタスクの1つは、あるポリシーに対する戻り分布 $\eta^\pi$ を推定する分散ポリシー評価である。 従来のRL領域における時間差分学習(TD)の拡張である時間差分学習が提案されている。 表の例では, \citet{rowland2018analysis} と \citet{rowland2023analysis} は2つの分布的TD, すなわちカテゴリー的時間差学習 (CTD) と量子的時間差学習 (QTD) の漸近収束性を示した。 本稿では、さらに一歩進んで、分布性TDの有限サンプル性能を解析する。 理論的解析を容易にするため,Non-parametric distributional TD learning (NTD)を提案する。 $\gamma$-discounted infinite-horizon tabular Markov decision processでは、NTD に対して$\tilde{O}\left(\frac{1}{\varepsilon^{2p}(1-\gamma)^{2p+1}}\right)$ iterations to achieve a $\varepsilon$-optimal estimator with high probability, when the estimation error is measured by the $p-Wasserstein distance。 このサンプルの複雑性境界は、ワッサーシュタイン距離が1ドルである場合の対数係数まで極小に最適である。 これを達成するために、ヒルベルト空間における新しいフリードマンの不等式(英語版)(Freedman's inequality)を確立する。 さらに我々はCTDを再検討し、同じ非漸近収束境界が、$p$-Wasserstein 距離が$p\geq 1$ の場合、CTD に対して成り立つことを示した。

関連論文リスト

• Finite Time Analysis of Temporal Difference Learning for Mean-Variance in a Discounted MDP [1.0923877073891446]
  割引報酬マルコフ決定プロセスにおける分散政策評価の問題点を考察する。 本稿では,線形関数近似(LFA)を用いた時間差分型学習アルゴリズムについて述べる。 平均二乗の意味で(i) を保持する有限標本境界と、(ii) テールイテレート平均化を用いる場合の高い確率を導出する。
  論文  参考訳（メタデータ） (2024-06-12T05:49:53Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards [27.209606183563853]
  動的勾配クリッピング機構による時間差(TD)学習は,重み付き報酬分布に対して確実に堅牢化できることを確認した。 TD学習に基づくNACの頑健な変種が$tildemathcalO(varepsilon-frac1p)$サンプル複雑性を達成することを示す。
  論文  参考訳（メタデータ） (2023-06-20T11:12:21Z)
• Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions [9.953088581242845]
  2次モーメントを持つ任意のデータ分布に対して,コンバージェンス保証と複雑性を提供する。 我々の結果は、対数共空性や機能的不等式を前提としない。 我々の理論解析は、異なる離散近似の比較を提供し、実際の離散化点の選択を導くかもしれない。
  論文  参考訳（メタデータ） (2022-11-03T15:51:00Z)
• Limit Distribution Theory for the Smooth 1-Wasserstein Distance with Applications [18.618590805279187]
  スムーズな1-ワッサーシュタイン距離 (SWD) $W_1sigma$ は経験的近似における次元の呪いを軽減する手段として最近提案された。 この研究は、高次元の極限分布結果を含むSWDの詳細な統計的研究を行う。
  論文  参考訳（メタデータ） (2021-07-28T17:02:24Z)
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations [0.3553493344868413]
  エルゴード微分方程式のイン分布と強い対数凸の場合の分布との間のワッサースタイン距離について検討した。 これにより、過減衰および過減衰ランジュバン力学の文献で提案されている多くの異なる近似を統一的に研究することができる。
  論文  参考訳（メタデータ） (2021-04-26T07:50:04Z)
• 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)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。 我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
  論文  参考訳（メタデータ） (2020-10-19T15:23:18Z)
• 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)
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling [56.394284787780364]
  本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。 一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。 線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
  論文  参考訳（メタデータ） (2020-02-15T00:26:49Z)

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

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