論文の概要: Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards
- arxiv url: http://arxiv.org/abs/2306.11455v1
- Date: Tue, 20 Jun 2023 11:12:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-21 14:44:39.927355
- Title: Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards
- Title（参考訳）: 重み付き報酬に対する頑健な時間差学習
- Authors: Semih Cayci and Atilla Eryilmaz
- Abstract要約: 動的勾配クリッピング機構による時間差(TD)学習は,重み付き報酬分布に対して確実に堅牢化できることを確認した。
TD学習に基づくNACの頑健な変種が$tildemathcalO(varepsilon-frac1p)$サンプル複雑性を達成することを示す。
- 参考スコア（独自算出の注目度）: 27.209606183563853
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In a broad class of reinforcement learning applications, stochastic rewards
have heavy-tailed distributions, which lead to infinite second-order moments
for stochastic (semi)gradients in policy evaluation and direct policy
optimization. In such instances, the existing RL methods may fail miserably due
to frequent statistical outliers. In this work, we establish that temporal
difference (TD) learning with a dynamic gradient clipping mechanism, and
correspondingly operated natural actor-critic (NAC), can be provably
robustified against heavy-tailed reward distributions. It is shown in the
framework of linear function approximation that a favorable tradeoff between
bias and variability of the stochastic gradients can be achieved with this
dynamic gradient clipping mechanism. In particular, we prove that robust
versions of TD learning achieve sample complexities of order
$\mathcal{O}(\varepsilon^{-\frac{1}{p}})$ and
$\mathcal{O}(\varepsilon^{-1-\frac{1}{p}})$ with and without the full-rank
assumption on the feature matrix, respectively, under heavy-tailed rewards with
finite moments of order $(1+p)$ for some $p\in(0,1]$, both in expectation and
with high probability. We show that a robust variant of NAC based on Robust TD
learning achieves $\tilde{\mathcal{O}}(\varepsilon^{-4-\frac{2}{p}})$ sample
complexity. We corroborate our theoretical results with numerical experiments.
- Abstract（参考訳）: 広範な強化学習アプリケーションでは、確率的報酬は重み付き分布を持ち、政策評価と直接政策最適化における確率的(半)段階の無限二階モーメントをもたらす。
そのような場合、既存のRL法は、しばしば統計的外れ値によって不運に失敗することがある。
本研究では,動的勾配クリッピング機構による時間差(TD)学習と,それに対応する自然なアクター・クリティカル(NAC)学習を,重み付き報酬分布に対して確実に堅牢化できることを示す。
線形関数近似の枠組みにおいて, この動的勾配クリッピング機構により, バイアスと確率勾配の変動性との間に好適なトレードオフが得られることを示した。
特に、td学習の頑健なバージョンは、$\mathcal{o}(\varepsilon^{-\frac{1}{p}})$ と$\mathcal{o}(\varepsilon^{-1-\frac{1}{p}})$ という順序のサンプル複素性を達成することを証明している。
我々は、ロバストなTD学習に基づくNACの堅牢な変種が、サンプルの複雑さに対して$\tilde{\mathcal{O}}(\varepsilon^{-4-\frac{2}{p}})を達成することを示す。
我々は理論結果を数値実験で裏付ける。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Convergence of a model-free entropy-regularized inverse reinforcement learning algorithm [6.481009996429766]
逆強化学習(IRL)は、専門家が最適である報酬を回復することを目的としている。
本研究では,エントロピー規則化IRL問題を解くためのモデルフリーアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-25T14:54:42Z) - Statistical Efficiency of Distributional Temporal Difference Learning [24.03281329962804]
我々は、分布時間差分学習(CTD)と量子時間差分学習(QTD)の有限サンプル性能を解析する。
$gamma$-discounted infinite-horizon decision process に対して、NTD では $tildeOleft(frac1varepsilon2p (1-gamma)2pright)$ が、高い確率で $varepsilon$-optimal estimator を達成するために必要であることを示す。
我々はヒルベルト空間における新しいフリードマンの不等式を確立し、これは独立な関心事である。
論文 参考訳（メタデータ） (2024-03-09T06:19:53Z) - Demonstration-Regularized RL [39.96273388393764]
専門的な実証から,次数$widetildeO(mathrmPoly(S,A,H)/(varepsilon2 NmathrmE)$および$widetildeO(mathrmPoly(d,H)/(varepsilon2 NmathrmE)$の線形マルコフ決定過程における最適ポリシを同定した。
実演規則化手法が人間のフィードバックからの強化学習に有効であることを示す。
論文 参考訳（メタデータ） (2023-10-26T10:54:47Z) - A Finite Sample Complexity Bound for Distributionally Robust Q-learning [17.96094201655567]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。
ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。
これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
論文 参考訳（メタデータ） (2023-02-26T01:15:32Z) - Stochastic Second-Order Methods Provably Beat SGD For Gradient-Dominated
Functions [42.57892322514602]
SCRNは,最もよく知られた勾配勾配勾配勾配の複雑さを$mathcalO(epsilon-1/2)$で改善することを示した。
また, SCRNのサンプルの複雑さは, バッチサイズが異なる分散還元法を用いて$mathcalO(epsilon-1/2)$で改善できることを示した。
論文 参考訳（メタデータ） (2022-05-25T15:33:00Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - 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) - 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) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。