論文の概要: The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise
- arxiv url: http://arxiv.org/abs/2401.07844v3
- Date: Mon, 29 Apr 2024 02:34:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-30 23:55:37.296171
- Title: The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise
- Title(参考訳): マルコフ雑音による確率近似と強化学習のODE法
- Authors: Shuze Liu, Shuhang Chen, Shangtong Zhang,
- Abstract要約: 近似アルゴリズムを解析する根本的な課題は、その安定性を確立することである。
本稿では,マルティンゲール差分雑音設定からマルコフ雑音設定へ有界な安定に対するボルカー・メイン定理を拡張する。
我々の分析の中心は、少数の関数の変化の減少率であり、これは多量の強い法則の形式とよく用いられるV4 Lynovドリフト条件の両方によって示唆される。
- 参考スコア(独自算出の注目度): 17.493808856903303
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic approximation is a class of algorithms that update a vector iteratively, incrementally, and stochastically, including, e.g., stochastic gradient descent and temporal difference learning. One fundamental challenge in analyzing a stochastic approximation algorithm is to establish its stability, i.e., to show that the stochastic vector iterates are bounded almost surely. In this paper, we extend the celebrated Borkar-Meyn theorem for stability from the Martingale difference noise setting to the Markovian noise setting, which greatly improves its applicability in reinforcement learning, especially in those off-policy reinforcement learning algorithms with linear function approximation and eligibility traces. Central to our analysis is the diminishing asymptotic rate of change of a few functions, which is implied by both a form of strong law of large numbers and a commonly used V4 Lyapunov drift condition and trivially holds if the Markov chain is finite and irreducible.
- Abstract(参考訳): 確率近似(Stochastic approximation)は、ベクトルを反復的に、漸進的に、確率的に更新するアルゴリズムのクラスである。
確率近似アルゴリズムを解析する基本的な課題の1つは、その安定性、すなわち確率ベクトル反復がほぼ確実に有界であることを示すことである。
本稿では,マルティンゲール差音設定からマルコフ雑音設定への安定性に関するボルカール・メインの定理を拡張し,特に線形関数近似と可視性トレースを持つ非線形強化学習アルゴリズムにおける強化学習への適用性を大幅に向上させる。
我々の分析の中心は、少数の函数の変化の漸近速度の減少であり、これは大数の強い法則の形式とよく使われるV4リャプノフドリフト条件の両方によって示唆され、マルコフ鎖が有限で既約であれば自明に成り立つ。
関連論文リスト
- Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates [61.091122503406304]
勾配帯域幅アルゴリズムは, 経験的定値学習率を用いて, ほぼ確実にグローバルな最適ポリシーに収束することを示す。
この結果は、標準の滑らかさと騒音制御の仮定が崩壊するシナリオにおいても、勾配アルゴリズムが適切な探索と利用のバランスを保ち続けていることを証明している。
論文 参考訳(メタデータ) (2025-02-11T00:12:04Z) - A weak convergence approach to large deviations for stochastic approximations [0.9374652839580183]
我々は、状態依存マルコフ雑音とステップサイズを減少させる一般近似に対する大きな偏差原理を証明した。
学習アルゴリズムの例としては、勾配降下、コントラスト分岐、ワン・ランダウアルゴリズムがある。
論文 参考訳(メタデータ) (2025-02-04T17:50:30Z) - Byzantine-Robust Decentralized Stochastic Optimization with Stochastic
Gradient Noise-Independent Learning Error [25.15075119957447]
分散ネットワーク上でのビザンチン-ロバスト最適化について検討し、各エージェントが近隣のエージェントと定期的に通信して局所モデルを交換し、勾配降下(SGD)により独自の局所モデルを更新する。
このような手法の性能は、最適化プロセス中に逆向きに実行される未知数のビザンチンエージェントに影響される。
論文 参考訳(メタデータ) (2023-08-10T02:14:23Z) - First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳(メタデータ) (2023-05-25T11:11:31Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳(メタデータ) (2022-11-14T21:54:31Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳(メタデータ) (2022-04-20T07:14:21Z) - A Closed Loop Gradient Descent Algorithm applied to Rosenbrock's
function [0.0]
本稿では,非拘束慣性減衰の勾配降下アルゴリズムとして応用できる勾配系の新しい適応手法を提案する。
また、リアプノフ安定性解析を用いて、連続数値時間バージョンの性能を実証する。
論文 参考訳(メタデータ) (2021-08-29T17:25:24Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。
この回避は、非自明な常微分方程式のノイズ離散化として研究される。
論文 参考訳(メタデータ) (2020-12-07T19:14:49Z) - Stochastic Approximation with Markov Noise: Analysis and applications in
reinforcement learning [0.0]
マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。
両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。
ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
論文 参考訳(メタデータ) (2020-04-08T03:59:21Z) - A Distributional Analysis of Sampling-Based Reinforcement Learning
Algorithms [67.67377846416106]
定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。
本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
論文 参考訳(メタデータ) (2020-03-27T05:13:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。