論文の概要: Constant Stepsize Q-learning: Distributional Convergence, Bias and
Extrapolation
- arxiv url: http://arxiv.org/abs/2401.13884v1
- Date: Thu, 25 Jan 2024 02:01:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-26 15:58:01.351157
- Title: Constant Stepsize Q-learning: Distributional Convergence, Bias and
Extrapolation
- Title(参考訳): 定段階Q-ラーニング:分布収束,バイアス,外挿
- Authors: Yixuan Zhang and Qiaomin Xie
- Abstract要約: 本稿では,非同期Q-ラーニングを定常的なステップサイズで研究する。
一定段数Q-ラーニングを時間均質な連鎖に接続することにより、距離の反復の分布収束を示す。
また,Q-ラーニングイテレートに対する中心極限理論を確立し,平均的イテレートの正規性を示す。
具体的には、偏差は高次項までの段差に比例し、線形係数に対して明示的な表現を与える。
- 参考スコア(独自算出の注目度): 27.17913040244775
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic Approximation (SA) is a widely used algorithmic approach in
various fields, including optimization and reinforcement learning (RL). Among
RL algorithms, Q-learning is particularly popular due to its empirical success.
In this paper, we study asynchronous Q-learning with constant stepsize, which
is commonly used in practice for its fast convergence. By connecting the
constant stepsize Q-learning to a time-homogeneous Markov chain, we show the
distributional convergence of the iterates in Wasserstein distance and
establish its exponential convergence rate. We also establish a Central Limit
Theory for Q-learning iterates, demonstrating the asymptotic normality of the
averaged iterates. Moreover, we provide an explicit expansion of the asymptotic
bias of the averaged iterate in stepsize. Specifically, the bias is
proportional to the stepsize up to higher-order terms and we provide an
explicit expression for the linear coefficient. This precise characterization
of the bias allows the application of Richardson-Romberg (RR) extrapolation
technique to construct a new estimate that is provably closer to the optimal Q
function. Numerical results corroborate our theoretical finding on the
improvement of the RR extrapolation method.
- Abstract(参考訳): 確率近似(Stochastic Approximation、SA)は、最適化や強化学習(RL)など、様々な分野で広く使われているアルゴリズム手法である。
RLアルゴリズムの中で、Q学習は経験的成功のために特に人気がある。
本稿では,非同期Q-ラーニングを定常的なステップサイズで研究する。
定数ステップ化q-ラーニングを時間均質マルコフ連鎖に結びつけることで,イテレートの分布収束をwasserstein距離で示し,その指数収束速度を確立する。
また,q学習イテレートの中央極限理論を確立し,平均的なイテレートの漸近正規性を示す。
さらに、ステップ化における平均的な反復の漸近バイアスを明示的に拡張する。
具体的には、バイアスは高次項までの段差に比例し、線形係数に対して明示的な表現を与える。
このバイアスの正確な特徴づけは、最適Q関数に確実に近い新しい推定値を構築するためにリチャードソン・ロームバーグ外挿法(RR)の適用を可能にする。
数値計算はRR外挿法の改良に関する理論的知見を裏付けるものである。
関連論文リスト
- Stochastic Methods in Variational Inequalities: Ergodicity, Bias and
Refinements [19.524063429548278]
Extragradient (SEG) と Gradient Descent Ascent (SGDA) は min-max 最適化と変分不等式問題に対する優越アルゴリズムである。
これらのアルゴリズムに固有の本質的な構造を定量化し定量化するための我々の取り組み。
定数のステップサイズSEG/SGDAを時間同質マルコフ連鎖として再キャストすることにより、大数の第一種法則と中心極限定理を確立する。
論文 参考訳(メタデータ) (2023-06-28T18:50:07Z) - Exponential Concentration of Stochastic Approximation with Non-vanishing
Gradient [0.0]
近似アルゴリズムの振る舞いを分析し,各ステップで目標に向かって進行する。
非消滅マルコフを持つ射影勾配 Descent に対して、我々の結果は$O(t)$および線形収束率を証明するのに使うことができる。
論文 参考訳(メタデータ) (2022-08-15T14:57:26Z) - q-Learning in Continuous Time [1.4213973379473654]
エントロピー規則化探索拡散過程の定式化による強化学習(RL)におけるQ-ラーニングの連続的対応について検討した。
我々は、時間離散化とは無関係なq-函数に関するq-ラーニング理論を開発する。
我々は、根底にある問題を解決するために、異なるアクター批判アルゴリズムを考案する。
論文 参考訳(メタデータ) (2022-07-02T02:20:41Z) - Efficient CDF Approximations for Normalizing Flows [64.60846767084877]
正規化フローの微分同相性に基づいて、閉領域上の累積分布関数(CDF)を推定する。
一般的なフローアーキテクチャとUCIデータセットに関する実験は,従来の推定器と比較して,サンプル効率が著しく向上したことを示している。
論文 参考訳(メタデータ) (2022-02-23T06:11:49Z) - Regularized Q-learning [3.032364229481336]
本稿では,線形関数近似を用いて収束する新しいQ-ラーニングアルゴリズムを提案する。
線形関数近似を用いたQ-ラーニングが分散した環境に収束することが実験的に示された。
論文 参考訳(メタデータ) (2022-02-11T01:29:50Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and
Finite-Time Performance [1.52292571922932]
非線形2時間スケール近似の収束と有限時間解析について検討する。
特に,本手法は期待値の収束を$mathcalO (1/k2/3)$で達成し,$k$は反復数であることを示す。
論文 参考訳(メタデータ) (2020-11-03T17:43:39Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳(メタデータ) (2020-09-29T18:48:21Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳(メタデータ) (2020-04-09T17:54:18Z) - A Distributional Analysis of Sampling-Based Reinforcement Learning
Algorithms [67.67377846416106]
定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。
本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
論文 参考訳(メタデータ) (2020-03-27T05:13:29Z) - SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for
Gaussian Process Regression with Derivatives [86.01677297601624]
本稿では,2次フーリエ特徴に基づく導関数によるGP回帰のスケーリング手法を提案する。
我々は、近似されたカーネルと近似された後部の両方に適用される決定論的、非漸近的、指数関数的に高速な崩壊誤差境界を証明した。
論文 参考訳(メタデータ) (2020-03-05T14:33:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。