論文の概要: 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}})を達成することを示す。
我々は理論結果を数値実験で裏付ける。
関連論文リスト
- Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization
Problems [61.002740957716156]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳(メタデータ) (2023-11-07T17:39:17Z) - Demonstration-Regularized RL [41.465567768628794]
専門的な実証から,次数$widetildemathcalO(mathrmPoly(S,A,H)/(varepsilon2 NmathrmE)$の有限および$widetildemathcalO(mathrmPoly(d,H)/(varepsilon2 NmathrmE)$の線形マルコフ決定過程における最適ポリシを同定する。
論文 参考訳(メタデータ) (2023-10-26T10:54:47Z) - Variance-reduced Clipping for Non-convex Optimization [24.765794811146144]
グラディエント・クリッピング(Gradient clipping)は、大規模言語モデリングのようなディープラーニングアプリケーションで用いられる技法である。
最近の実験的な訓練は、秩序の複雑さを緩和する、非常に特別な振る舞いを持っている。
論文 参考訳(メタデータ) (2023-03-02T00:57:38Z) - A Finite Sample Complexity Bound for Distributionally Robust Q-learning [16.88062487980405]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。
ロバストなマルコフ決定プロセスの定式化を適用することで、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) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳(メタデータ) (2021-02-20T13:45:11Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。