論文の概要: Statistical Efficiency of Distributional Temporal Difference Learning and Freedman's Inequality in Hilbert Spaces

• arxiv url: http://arxiv.org/abs/2403.05811v4
• Date: Thu, 16 Jan 2025 03:31:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-17 15:08:19.125590
• Title: Statistical Efficiency of Distributional Temporal Difference Learning and Freedman's Inequality in Hilbert Spaces
• Title（参考訳）: ヒルベルト空間における分布時間差学習の統計的効率と自由マンの不等式
• Authors: Yang Peng, Liangyu Zhang, Zhihua Zhang,
• Abstract要約: 本稿では,分布時間差学習における非漸近的統計率に着目した。 生成モデルを用いたNTDの場合、$tildeO(varepsilon-2 mu_pi,min-1 (1-gamma)-3+t_mixmu_pi,min-1 (1-gamma)-1)$サンプル複雑性境界はワッサーシュタイン距離が1ドルである場合に必要である。 我々は新しいフリードマンの不平等を樹立する
• 参考スコア（独自算出の注目度）: 24.03281329962804
• License:
• Abstract: Distributional reinforcement learning (DRL) has achieved empirical success in various domains. One core task in DRL is distributional policy evaluation, which involves estimating the return distribution $\eta^\pi$ for a given policy $\pi$. Distributional temporal difference learning has been accordingly proposed, which extends the classic temporal difference learning (TD) in RL. In this paper, we focus on the non-asymptotic statistical rates of distributional TD. To facilitate theoretical analysis, we propose non-parametric distributional TD (NTD). For a $\gamma$-discounted infinite-horizon tabular Markov decision process, we show that for NTD with a generative model, we need $\tilde{O}(\varepsilon^{-2}\mu_{\min}^{-1}(1-\gamma)^{-3})$ interactions with the environment to achieve an $\varepsilon$-optimal estimator with high probability, when the estimation error is measured by the $1$-Wasserstein. This sample complexity bound is minimax optimal up to logarithmic factors. In addition, we revisit categorical distributional TD (CTD), showing that the same non-asymptotic convergence bounds hold for CTD in the case of the $1$-Wasserstein distance. We also extend our analysis to the more general setting where the data generating process is Markovian. In the Markovian setting, we propose variance-reduced variants of NTD and CTD, and show that both can achieve a $\tilde{O}(\varepsilon^{-2} \mu_{\pi,\min}^{-1}(1-\gamma)^{-3}+t_{mix}\mu_{\pi,\min}^{-1}(1-\gamma)^{-1})$ sample complexity bounds in the case of the $1$-Wasserstein distance, which matches the state-of-the-art statistical results for classic policy evaluation. To achieve the sharp statistical rates, we establish a novel Freedman's inequality in Hilbert spaces. This new Freedman's inequality would be of independent interest for statistical analysis of various infinite-dimensional online learning problems.
• Abstract（参考訳）: 分散強化学習(DRL)は様々な領域で実証的な成功を収めている。 DRLのコアタスクの1つは、あるポリシーに対する戻り値の分布を$\eta^\pi$と見積もる分散ポリシー評価である。 RLにおける古典的時間差分学習(TD)を拡張した分布時間差分学習法が提案されている。 本稿では,分布性TDの非漸近統計率に着目した。 理論的解析を容易にするため,非パラメトリック分布TD(NTD)を提案する。 生成モデルを持つNTDに対して、$\tilde{O}(\varepsilon^{-2}\mu_{\min}^{-1}(1-\gamma)^{-3})$と環境との相互作用が$\varepsilon$-Optimal estimatorを高い確率で達成するためには、推定誤差が1-Wassersteinによって測定される。 このサンプル複雑性境界は対数係数まで最小限の最適値である。 さらに分類的分布TD (CTD) を再検討し, ワッサーシュタイン距離が1ドルである場合, 同様の非漸近収束境界がCTDに対して成り立つことを示した。 また、データ生成プロセスがマルコビアンであるより一般的な設定まで分析を拡張します。 マルコビアン・セッティングではNTDとCTDの分散還元変種を提案し、古典的政策評価の最先端統計結果と一致する1ドル=ワッサーシュタイン距離の場合のサンプル複雑性を$\tilde{O}(\varepsilon^{-2} \mu_{\pi,\min}^{-1}(1-\gamma)^{-3}+t_{mix}\mu_{\pi,\min}^{-1}(1-\gamma)^{-1})で得ることを示す。 急激な統計率を達成するために、ヒルベルト空間において新しいフリードマンの不等式を確立する。 この新たなフリードマンの不等式は、様々な無限次元オンライン学習問題の統計解析に独立した関心を持つ。

関連論文リスト

• 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)

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

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