論文の概要: Statistical Efficiency of Distributional Temporal Difference
- arxiv url: http://arxiv.org/abs/2403.05811v1
- Date: Sat, 9 Mar 2024 06:19:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 12:11:14.720128
- Title: Statistical Efficiency of Distributional Temporal Difference
- Title(参考訳): 分布時間差の統計的効率
- Authors: Yang Peng, Liangyu Zhang, Zhihua Zhang
- Abstract要約: 古典的RL文学における時間差分アルゴリズムの拡張である分布時間差(TD)が提案されている。
NTD の場合、高い確率で $varepsilon-Wasserstein 推定器を達成するためには $wtilde Oprnfrac1vareps2p (1-gamma)2p+2$ 反復が必要である。
そして我々はCTDを再考し、同じ非漸近収束境界が$p$-Wasserstein 距離でCTDに保たれることを示した。
- 参考スコア(独自算出の注目度): 27.010473703511643
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Distributional reinforcement learning (DRL), which cares about the full
distribution of returns instead of just the mean, has achieved empirical
success in various domains. One of the core tasks in the field of DRL is
distributional policy evaluation, which involves estimating the return
distribution $\eta^\pi$ for a given policy $\pi$. A distributional temporal
difference (TD) algorithm has been accordingly proposed, which is an extension
of the temporal difference algorithm in the classic RL literature. In the
tabular case, \citet{rowland2018analysis} and \citet{rowland2023analysis}
proved the asymptotic convergence of two instances of distributional TD, namely
categorical temporal difference algorithm (CTD) and quantile temporal
difference algorithm (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 algorithm
(NTD). For a $\gamma$-discounted infinite-horizon tabular Markov decision
process with state space $S$ and action space $A$, we show that in the case of
NTD we need $\wtilde O\prn{\frac{1}{\varepsilon^{2p}(1-\gamma)^{2p+2}}}$
iterations to achieve an $\varepsilon$-optimal estimator with high probability,
when the estimation error is measured by the $p$-Wasserstein distance. Under
some mild assumptions, $\wtilde O\prn{\frac{1}{\varepsilon^{2}(1-\gamma)^{4}}}$
iterations suffices to ensure the Kolmogorov-Smirnov distance between the NTD
estimator $\hat\eta^\pi$ and $\eta^\pi$ less than $\varepsilon$ with high
probability. And we revisit CTD, showing that the same non-asymptotic
convergence bounds hold for CTD in the case of the $p$-Wasserstein distance.
- Abstract(参考訳): 分布強化学習(distributional reinforcement learning, drl)は、平均ではなくリターンの完全な分配に関心を持ち、様々な領域で実証的な成功を収めている。
DRL の分野における中核的なタスクの1つは、あるポリシーに対する戻り分布 $\eta^\pi$ を推定する分散ポリシー評価である。
そのため,古典的rl文献における時間差アルゴリズムの拡張として,分布時間差アルゴリズム(td)が提案されている。
表式の場合、 \citet{rowland2018 analysis} と \citet{rowland2023 analytic} はそれぞれ分布的tdの2つの例、すなわちカテゴリー的時間差アルゴリズム(ctd)と分位時差アルゴリズム(qtd)の漸近収束を証明した。
本稿では、さらに一歩進んで、分布性TDの有限サンプル性能を解析する。
理論的解析を容易にするため,非パラメトリック分布型TDアルゴリズム(NTD)を提案する。
状態空間 $S$ と作用空間 $A$ を持つ$\gamma$-discounted infinite-horizon tabular Markov decision process に対して、NTD の場合、$\wtilde O\prn{\frac{1}{\varepsilon^{2p}(1-\gamma)^{2p+2}}} が$\varepsilon$-optimal estimator を高い確率で達成するためには、推定誤差が$p$-ワッサーシュタイン距離で測定される場合、$\wtilde O\prn{\frac{1}{\varepsilon^{2p}(1-\gamma)^{2p+2}}} が必要であることを示す。
いくつかの穏やかな仮定の下で、$\wtilde o\prn{\frac{1}{\varepsilon^{2}(1-\gamma)^{4}}}$ 反復は、高い確率で$\hat\eta^\pi$ と$\eta^\pi$ と$\varepsilon$ の間のコルモゴロフ-スミルノフ距離を保証するのに十分である。
我々はCTDを再検討し、同じ非漸近収束境界が$p$-Wasserstein距離の場合、CTDに対して成り立つことを示した。
関連論文リスト
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネル空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
我々は、$epsilon$-covering up $mathcalO(epsilon-frac2dd+2)$に対する計量エントロピーの改善結果を得る。
論文 参考訳(メタデータ) (2024-04-29T15:04:07Z) - Robust Estimation under the Wasserstein Distance [28.792608997509376]
出力分布から外周質量が$varepsilon$を除去できる新しい外周ローバストワッサーシュタイン距離$mathsfW_pvarepsilon$を導入する。
我々は,$mathsfW_pvarepsilon$で最小距離推定を行うことで,最小限のロバスト推定リスクが得られることを示した。
論文 参考訳(メタデータ) (2023-02-02T17:20:25Z) - Scaling up Stochastic Gradient Descent for Non-convex Optimisation [5.908471365011942]
本稿では,共有並列計算問題に対する新しいアプローチを提案する。
2つの戦略を統一されたフレームワークに組み合わせることで、DPSGDはより良い取引計算フレームワークになります。
深層学習(DRL)問題と深層学習(DRL)問題(アドバンテージアクター - A2C)についてDPSGDにより潜在ゲインを達成できる。
論文 参考訳(メタデータ) (2022-10-06T13:06:08Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳(メタデータ) (2021-09-24T14:48:20Z) - Wasserstein distance estimates for the distributions of numerical
approximations to ergodic stochastic differential equations [0.3553493344868413]
エルゴード微分方程式のイン分布と強い対数凸の場合の分布との間のワッサースタイン距離について検討した。
これにより、過減衰および過減衰ランジュバン力学の文献で提案されている多くの異なる近似を統一的に研究することができる。
論文 参考訳(メタデータ) (2021-04-26T07:50:04Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳(メタデータ) (2020-12-21T03:10:21Z) - Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence
Analysis [27.679514676804057]
オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。
実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
論文 参考訳(メタデータ) (2020-10-26T01:33:05Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳(メタデータ) (2020-10-19T15:23:18Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳(メタデータ) (2020-06-19T14:11:26Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。