論文の概要: Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise
- arxiv url: http://arxiv.org/abs/2411.13711v1
- Date: Wed, 20 Nov 2024 21:09:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-22 15:20:01.020188
- Title: Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise
- Title(参考訳): マルコフ雑音による確率近似と強化学習のほぼ確実に収束率と濃度
- Authors: Xiaochi Qian, Zixuan Xie, Xinyu Liu, Shangtong Zhang,
- Abstract要約: カウントベース学習率を使わずにMarkovianサンプルを用いてQ$-learningの収束率を示す。
また、マルコフサンプルを用いた非政治時間差学習のための第1の集中度も提供する。
- 参考スコア(独自算出の注目度): 31.241889735283166
- License:
- Abstract: This paper establishes the first almost sure convergence rate and the first maximal concentration bound with exponential tails for general contractive stochastic approximation algorithms with Markovian noise. As a corollary, we also obtain convergence rates in $L^p$. Key to our successes is a novel discretization of the mean ODE of stochastic approximation algorithms using intervals with diminishing (instead of constant) length. As applications, we provide the first almost sure convergence rate for $Q$-learning with Markovian samples without count-based learning rates. We also provide the first concentration bound for off-policy temporal difference learning with Markovian samples.
- Abstract(参考訳): 本稿では,マルコフ雑音を伴う一般縮約確率近似アルゴリズムにおいて,ほぼ確実に収束する最初の収束速度と指数的尾に束縛された第1の最大濃度を確立する。
座標系として、$L^p$の収束率も得られる。
我々の成功の鍵は、(一定ではなく)長さを減少させる間隔を用いた確率近似アルゴリズムの平均ODEの新たな離散化である。
アプリケーションとして、カウントベース学習率を使わずにMarkovianサンプルを用いてQ$ラーニングを行うための、ほぼ確実な収束率を提供する。
また、マルコフサンプルを用いた非政治時間差学習のための第1の集中度も提供する。
関連論文リスト
- Uncertainty quantification for Markov chains with application to temporal difference learning [63.49764856675643]
マルコフ連鎖のベクトル値および行列値関数に対する新しい高次元濃度不等式とベリー・エッシー境界を開発する。
我々は、強化学習における政策評価に広く用いられているTD学習アルゴリズムを解析する。
論文 参考訳(メタデータ) (2025-02-19T15:33:55Z) - Statistical guarantees for continuous-time policy evaluation: blessing of ellipticity and new tradeoffs [2.926192989090622]
連続時間マルコフ拡散過程における値関数の推定について検討する。
我々の研究は、最小二乗時間差法に対して漸近的でない統計的保証を提供する。
論文 参考訳(メタデータ) (2025-02-06T18:39:03Z) - Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise [20.474661995490365]
本研究は、単に拡張的でない作用素との近似を研究する。
特にマルコフ雑音による非拡張近似について検討する。
応用として、古典的な平均報酬時間差学習が標本経路依存の固定点に収束することを初めて証明する。
論文 参考訳(メタデータ) (2024-09-29T04:16:24Z) - On diffusion-based generative models and their error bounds: The log-concave case with full convergence estimates [5.13323375365494]
我々は,強い対数対数データの下での拡散に基づく生成モデルの収束挙動を理論的に保証する。
スコア推定に使用される関数のクラスは、スコア関数上のリプシッツネスの仮定を避けるために、リプシッツ連続関数からなる。
この手法はサンプリングアルゴリズムにおいて最もよく知られた収束率をもたらす。
論文 参考訳(メタデータ) (2023-11-22T18:40:45Z) - First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳(メタデータ) (2023-05-25T11:11:31Z) - Density Ratio Estimation via Infinitesimal Classification [85.08255198145304]
そこで我々は, DRE-inftyを提案する。 DRE-inftyは, 密度比推定(DRE)を, より簡単なサブプロブレムに還元する手法である。
モンテカルロ法にインスパイアされ、中間ブリッジ分布の無限連続体を介して2つの分布の間を滑らかに補間する。
提案手法は,複雑な高次元データセット上での相互情報推定やエネルギーベースモデリングなどの下流タスクにおいて良好に動作することを示す。
論文 参考訳(メタデータ) (2021-11-22T06:26:29Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳(メタデータ) (2020-09-29T18:48:21Z) - Stochastic Approximation with Markov Noise: Analysis and applications in
reinforcement learning [0.0]
マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。
両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。
ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
論文 参考訳(メタデータ) (2020-04-08T03:59:21Z) - Finite Time Analysis of Linear Two-timescale Stochastic Approximation
with Markovian Noise [28.891930079358954]
線形2時間スケールSAスキームに対して有限時間解析を行う。
我々の境界はマルコフ音とマルティンゲール音の収束速度に差がないことを示している。
一致した下界を持つ予測誤差の拡張を示す。
論文 参考訳(メタデータ) (2020-02-04T13:03:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。