Fugu-MT 論文翻訳(概要): Almost Sure Convergence of Average Reward Temporal Difference Learning

論文の概要: Almost Sure Convergence of Average Reward Temporal Difference Learning

arxiv url: http://arxiv.org/abs/2409.19546v2
Date: Wed, 2 Oct 2024 15:57:57 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-05 22:38:15.017890
Title: Almost Sure Convergence of Average Reward Temporal Difference Learning
Title（参考訳）: 平均逆時間差学習のほぼ確実な収束性
Authors: Ethan Blaser, Shangtong Zhang,
Abstract要約: タブラル平均報酬一時学習(TD)はおそらく最も単純かつ最も基本的な政策評価アルゴリズムである。非常に穏やかな条件下では、平均報酬 TD はサンプルパス依存の固定点にほぼ確実に収束することを示すのはこれが初めてである。この成功の鍵となるのは、マルコフ的および加法的雑音を伴う非拡大写像に関する新しい一般差分近似結果である。
参考スコア（独自算出の注目度）: 20.474661995490365
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Tabular average reward Temporal Difference (TD) learning is perhaps the simplest and the most fundamental policy evaluation algorithm in average reward reinforcement learning. After at least 25 years since its discovery, we are finally able to provide a long-awaited almost sure convergence analysis. Namely, we are the first to prove that, under very mild conditions, tabular average reward TD converges almost surely to a sample path dependent fixed point. Key to this success is a new general stochastic approximation result concerning nonexpansive mappings with Markovian and additive noise, built on recent advances in stochastic Krasnoselskii-Mann iterations.
Abstract（参考訳）: タブラル平均報酬差分法(TD)学習は、おそらく平均報酬強化学習において最も単純かつ最も基本的な政策評価アルゴリズムである。発見から少なくとも25年が経ち、私たちはついに、待ち望まれていたほぼ確実に収束分析を提供することができた。すなわち、非常に穏やかな条件下では、表平均報酬 TD が標本パス依存の固定点にほぼ確実に収束することを初めて証明する。この成功の鍵となるのは、マルコフ的でない写像と加法的雑音に関する新しい一般確率的近似結果である。

関連論文リスト

Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise [31.241889735283166]
カウントベース学習率を使わずにMarkovianサンプルを用いてQ$-learningの収束率を示す。また、マルコフサンプルを用いた非政治時間差学習のための第1の集中度も提供する。
論文参考訳（メタデータ） (2024-11-20T21:09:09Z)
Finite Sample and Large Deviations Analysis of Stochastic Gradient Algorithm with Correlated Noise [15.724207170366846]
我々は,ステップサイズ勾配アルゴリズムの有限標本残差を解析した。相関雑音を仮定し,解析の体系的アプローチとして摂動リアプノフ関数を用いる。
論文参考訳（メタデータ） (2024-10-11T01:38:27Z)
Almost sure convergence rates of stochastic gradient methods under gradient domination [2.96614015844317]
大域的および局所的な勾配支配特性は、強い凸性のより現実的な置き換えであることが示されている。収束率 $f(X_n)-f*in obig(n-frac14beta-1+epsilonbig)$ は勾配降下の最終反復である。教師付き学習と強化学習の両方において,本研究結果をトレーニングタスクに適用する方法を示す。
論文参考訳（メタデータ） (2024-05-22T12:40:57Z)
On the Last-Iterate Convergence of Shuffling Gradient Methods [21.865728815935665]
対象値に関して勾配法をシャッフルする際の最終点収束率を初めて証明する。我々の結果は、(ほぼ)既存のラストイテレートの下限と一致するか、あるいは、平均的なイテレートの前の最高の上限と同速である。
論文参考訳（メタデータ） (2024-03-12T15:01:17Z)
Stochastic Gradient Succeeds for Bandits [64.17904367852563]
エンフィスト確率勾配帯域幅アルゴリズムは,O (1/t)$レートで,エンフィグロブな最適ポリシに収束することを示す。興味深いことに、勾配帯域アルゴリズムのグローバル収束は以前に確立されていない。
論文参考訳（メタデータ） (2024-02-27T06:05:01Z)
High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
論文参考訳（メタデータ） (2023-10-03T07:49:17Z)
First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文参考訳（メタデータ） (2023-05-25T11:11:31Z)
Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers [90.45898746733397]
本研究では拡散生成モデルに用いる決定論的サンプリング器の非漸近解析のためのフレームワークを開発する。確率フローODEに沿った1ステップは,1) 条件付き対数線上を無限に先行して上昇する回復ステップ,2) 雑音を現在の勾配に向けて前向きに進行する劣化ステップの2段階で表すことができる。
論文参考訳（メタデータ） (2023-03-06T18:59:19Z)
Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文参考訳（メタデータ） (2023-01-10T12:18:47Z)
Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文参考訳（メタデータ） (2022-06-02T15:21:55Z)
Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文参考訳（メタデータ） (2022-04-20T07:14:21Z)
Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文参考訳（メタデータ） (2022-01-21T02:46:57Z)
Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文参考訳（メタデータ） (2021-12-29T18:46:52Z)
High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文参考訳（メタデータ） (2021-06-28T00:17:01Z)
Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency [83.02999769628593]
強化学習におけるオフ・ポリティィ・アセスメント(OPE)の理論的特徴について述べる。ミニマックス法により、重みと品質関数の高速収束を実現することができることを示す。非タブラル環境における1次効率を持つ最初の有限サンプル結果を示す。
論文参考訳（メタデータ） (2021-02-05T03:20:39Z)
Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning [9.359939442911127]
本稿ではマルコフ雑音下での変分不等式(VI)のリセットに着目する。我々のアルゴリズム開発における顕著な応用は、強化学習における政策評価問題である。
論文参考訳（メタデータ） (2020-11-15T04:05:22Z)
Proximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity [40.73281056650241]
本稿では,真の勾配時間差学習アルゴリズムを設計・解析する原理的な方法として,近位勾配時間差学習を導入する。本研究では, 従来の目的関数からではなく, 主目的関数から始めることによって, 勾配性TD強化学習法を公式に導出する方法を示す。
論文参考訳（メタデータ） (2020-06-06T21:04:21Z)
Convergence rates and approximation results for SGD and its continuous-time counterpart [16.70533901524849]
本稿では,非増加ステップサイズを有する凸勾配Descent (SGD) の完全理論的解析を提案する。まず、結合を用いた不均一微分方程式(SDE)の解により、SGDを確実に近似できることを示す。連続的手法による決定論的および最適化手法の最近の分析において, 連続過程の長期的挙動と非漸近的境界について検討する。
論文参考訳（メタデータ） (2020-04-08T18:31:34Z)
Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
論文参考訳（メタデータ） (2020-04-08T03:59:21Z)
Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文参考訳（メタデータ） (2020-03-16T17:15:28Z)

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