論文の概要: Stochastic Approximation with Markov Noise: Analysis and applications in
reinforcement learning
- arxiv url: http://arxiv.org/abs/2012.00805v1
- Date: Wed, 8 Apr 2020 03:59:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-15 08:36:56.696221
- Title: Stochastic Approximation with Markov Noise: Analysis and applications in
reinforcement learning
- Title（参考訳）: マルコフ雑音による確率近似:強化学習における解析と応用
- Authors: Prasenjit Karmakar
- Abstract要約: マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。
両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。
ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present for the first time an asymptotic convergence analysis of two
time-scale stochastic approximation driven by "controlled" Markov noise. In
particular, the faster and slower recursions have non-additive controlled
Markov noise components in addition to martingale difference noise. We analyze
the asymptotic behavior of our framework by relating it to limiting
differential inclusions in both time scales that are defined in terms of the
ergodic occupation measures associated with the controlled Markov processes.
Using a special case of our results, we present a solution to the off-policy
convergence problem for temporal-difference learning with linear function
approximation. We compile several aspects of the dynamics of stochastic
approximation algorithms with Markov iterate-dependent noise when the iterates
are not known to be stable beforehand. We achieve the same by extending the
lock-in probability (i.e. the probability of convergence to a specific
attractor of the limiting o.d.e. given that the iterates are in its domain of
attraction after a sufficiently large number of iterations (say) n_0) framework
to such recursions. We use these results to prove almost sure convergence of
the iterates to the specified attractor when the iterates satisfy an
"asymptotic tightness" condition. This, in turn, is shown to be useful in
analyzing the tracking ability of general "adaptive" algorithms. Finally, we
obtain the first informative error bounds on function approximation for the
policy evaluation algorithm proposed by Basu et al. when the aim is to find the
risk-sensitive cost represented using exponential utility. We show that this
happens due to the absence of difference term in the earlier bound which is
always present in all our bounds when the state space is large.
- Abstract（参考訳）: マルコフ雑音によって駆動される2つの時間スケール確率近似の漸近収束解析を初めて行った。
特に、より高速で遅い再帰は、マルティンゲール差分ノイズに加えて、非加法的に制御されたマルコフノイズ成分を持つ。
我々は,制御されたマルコフ過程に関連するエルゴード的職業措置の観点で定義される両時間尺度における差動包含物を制限することにより,枠組みの漸近的挙動を解析した。
結果の特殊な場合を用いて,線形関数近似を用いた時間差学習における非政治収束問題の解法を提案する。
確率近似アルゴリズムの力学のいくつかの側面をマルコフに依存した雑音でコンパイルする。
ロックイン確率(すなわち制限o.d.の特定のアトラクタへの収束確率)を十分に多くのイテレーション(例えば、n_0)フレームワークの後にイテレートがそのアトラクション領域内にあることを考慮し、同じことを達成する。
これらの結果を用いて,反復条件が「漸近的タイトネス」条件を満たす場合,反復条件が指定されたアトラクタにほぼ確実に収束することを証明する。
これは、一般的な「適応的」アルゴリズムの追跡能力を分析するのに有用であることが示されている。
最後に,basuらによって提案された政策評価アルゴリズムの関数近似に関する最初の情報的誤差境界を求める。
これは、状態空間が大きい場合、常にすべての境界に存在する前の境界における差分項の欠如によって起こることを示している。
関連論文リスト
- The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise [17.493808856903303]
近似アルゴリズムを解析する根本的な課題は、その安定性を確立することである。
本稿では,マルティンゲール差分雑音設定からマルコフ雑音設定へ有界な安定に対するボルカー・メイン定理を拡張する。
我々の分析の中心は、少数の関数の変化の減少率であり、これは多量の強い法則の形式とよく用いられるV4 Lynovドリフト条件の両方によって示唆される。
論文 参考訳（メタデータ） (2024-01-15T17:20:17Z) - Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic
Gradient Descent [30.84181129503133]
この10年で、異なる損失関数に適用された異なるアルゴリズムに対する安定性の増大が見られた。
本稿では,最適化アルゴリズムの安定性を証明するための統一的なガイドラインを導入する。
私たちのアプローチは柔軟で、他の一般的な学習クラスにも容易に適用できます。
論文 参考訳（メタデータ） (2023-05-20T01:49:58Z) - Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal
Leakage [24.40306100502023]
我々は,雑音学習アルゴリズムのクラスにおける一般化挙動を解析するために,情報理論の枠組みを採用する。
更新関数の仮定が雑音の最適選択にどのように影響するかを示す。
論文 参考訳（メタデータ） (2023-02-28T12:13:57Z) - 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 Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic
Approximation under Markovian Noise [2.0305676256390934]
2つの連結非線形作用素の根を探すためのシミュレーションベースアプローチである,いわゆる2時間スケール近似について検討する。
特に、マルコフプロセスによってメソッド内のデータが生成されるシナリオを考える。
演算子とマルコフ過程に関するかなり標準的な仮定の下で、この方法によって生成される平均二乗誤差の収束率を 0 に特徴づける公式を提供する。
論文 参考訳（メタデータ） (2021-04-04T15:19:19Z) - Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and
Finite-Time Performance [1.52292571922932]
非線形2時間スケール近似の収束と有限時間解析について検討する。
特に,本手法は期待値の収束を$mathcalO (1/k2/3)$で達成し,$k$は反復数であることを示す。
論文 参考訳（メタデータ） (2020-11-03T17:43:39Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳（メタデータ） (2020-03-16T17:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。