論文の概要: 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に対して成り立つことを示した。
関連論文リスト
- A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models [45.60426164657739]
拡散型サンプリング器の非漸近収束理論を開発する。
我々は、$d/varepsilon$がターゲット分布を$varepsilon$トータル偏差距離に近似するのに十分であることを証明した。
我々の結果は、$ell$のスコア推定誤差がデータ生成プロセスの品質にどのように影響するかも特徴付ける。
論文 参考訳（メタデータ） (2024-08-05T09:02:24Z) - Convergence Analysis of Probability Flow ODE for Score-based Generative Models [5.939858158928473]
確率フローODEに基づく決定論的サンプリング器の収束特性を理論的・数値的両面から検討する。
連続時間レベルでは、ターゲットと生成されたデータ分布の総変動を$mathcalO(d3/4delta1/2)$で表すことができる。
論文 参考訳（メタデータ） (2024-04-15T12:29:28Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative
Models [49.81937966106691]
我々は拡散モデルのデータ生成過程を理解するための非漸近理論のスイートを開発する。
従来の研究とは対照的に,本理論は基本的だが多目的な非漸近的アプローチに基づいて開発されている。
論文 参考訳（メタデータ） (2023-06-15T16:30:08Z) - Policy evaluation from a single path: Multi-step methods, mixing and
mis-specification [45.88067550131531]
無限水平$gamma$-discounted Markov rewardプロセスの値関数の非パラメトリック推定について検討した。
カーネルベースの多段階時間差推定の一般的なファミリーに対して、漸近的でない保証を提供する。
論文 参考訳（メタデータ） (2022-11-07T23:15:25Z) - Improved Analysis of Score-based Generative Modeling: User-Friendly
Bounds under Minimal Smoothness Assumptions [9.953088581242845]
2次モーメントを持つ任意のデータ分布に対して,コンバージェンス保証と複雑性を提供する。
我々の結果は、対数共空性や機能的不等式を前提としない。
我々の理論解析は、異なる離散近似の比較を提供し、実際の離散化点の選択を導くかもしれない。
論文 参考訳（メタデータ） (2022-11-03T15:51:00Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳（メタデータ） (2022-04-06T13:50:33Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Limit Distribution Theory for the Smooth 1-Wasserstein Distance with
Applications [18.618590805279187]
スムーズな1-ワッサーシュタイン距離 (SWD) $W_1sigma$ は経験的近似における次元の呪いを軽減する手段として最近提案された。
この研究は、高次元の極限分布結果を含むSWDの詳細な統計的研究を行う。
論文 参考訳（メタデータ） (2021-07-28T17:02:24Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。