論文の概要: 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 Q-learning for Large Discrete Action Spaces [79.1700188160944]
離散的な行動空間を持つ複雑な環境では、強化学習(RL)において効果的な意思決定が重要である
我々は、$n$アクションの集合全体を最適化するのとは対照的に、おそらく$mathcalO(log(n)$)$のような変数の集合のみを考える。
提示された値ベースのRL手法には、Q-learning、StochDQN、StochDDQNなどが含まれる。
論文 参考訳（メタデータ） (2024-05-16T17:58:44Z) - Last Iterate Convergence of Incremental Methods and Applications in Continual Learning [10.811735264028348]
連続学習における応用により、漸進的勾配法と漸進的近位法の両方の最後の繰り返しに対する収束保証を得る。
一般化を伴う連続学習のモデルとしての漸進的近位法について検討し,大惨な忘れ込みを防ぐために大量の正規化が不可欠であると主張している。
論文 参考訳（メタデータ） (2024-03-11T16:24:26Z) - 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) - Non-Parametric Learning of Stochastic Differential Equations with Non-asymptotic Fast Rates of Convergence [65.63201894457404]
非線形微分方程式のドリフトと拡散係数の同定のための新しい非パラメトリック学習パラダイムを提案する。
鍵となる考え方は、基本的には、対応するフォッカー・プランク方程式のRKHSに基づく近似をそのような観測に適合させることである。
論文 参考訳（メタデータ） (2023-05-24T20:43:47Z) - 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 [6.663174194579773]
本稿では,線形関数近似を用いて収束する新しい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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。