論文の概要: Non-Asymptotic Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes
- arxiv url: http://arxiv.org/abs/2504.18743v1
- Date: Fri, 25 Apr 2025 23:41:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-02 19:15:53.968253
- Title: Non-Asymptotic Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes
- Title（参考訳）: 適応的なステップサイズをもつ平均逆Q-Learningのための非漸近的保証
- Authors: Zaiwei Chen,
- Abstract要約: 本研究は,非同期実装を用いたQ-Learningの平均逆Q-Learningの最終項目収束に対する最初の有限時間解析である。
私たちが研究しているアルゴリズムの重要な特徴は、各状態-作用ペアの局所クロックとして機能する適応的なステップサイズの使用である。
- 参考スコア（独自算出の注目度）: 4.169915659794567
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work presents the first finite-time analysis for the last-iterate convergence of average-reward Q-learning with an asynchronous implementation. A key feature of the algorithm we study is the use of adaptive stepsizes, which serve as local clocks for each state-action pair. We show that the iterates generated by this Q-learning algorithm converge at a rate of $O(1/k)$ (in the mean-square sense) to the optimal relative Q-function in the span seminorm. Moreover, by adding a centering step to the algorithm, we further establish pointwise mean-square convergence to a centered optimal relative Q-function, also at a rate of $O(1/k)$. To prove these results, we show that adaptive stepsizes are necessary, as without them, the algorithm fails to converge to the correct target. In addition, adaptive stepsizes can be interpreted as a form of implicit importance sampling that counteracts the effects of asynchronous updates. Technically, the use of adaptive stepsizes makes each Q-learning update depend on the entire sample history, introducing strong correlations and making the algorithm a non-Markovian stochastic approximation (SA) scheme. Our approach to overcoming this challenge involves (1) a time-inhomogeneous Markovian reformulation of non-Markovian SA, and (2) a combination of almost-sure time-varying bounds, conditioning arguments, and Markov chain concentration inequalities to break the strong correlations between the adaptive stepsizes and the iterates. The tools developed in this work are likely to be broadly applicable to the analysis of general SA algorithms with adaptive stepsizes.
- Abstract（参考訳）: 本研究は,非同期実装を用いたQ-Learningの平均逆Q-Learningの最終項目収束に対する最初の有限時間解析である。
私たちが研究しているアルゴリズムの重要な特徴は、各状態-作用ペアの局所クロックとして機能する適応的なステップサイズの使用である。
このQ-ラーニングアルゴリズムによって生成された反復は、平均平方意味でのO(1/k)$の速度で、スパンセミノルムの最適相対Q-関数に収束することを示す。
さらに、アルゴリズムに中心的なステップを加えることにより、中心となる最適相対的Q-函数に対する点平均二乗収束を、O(1/k)$の速度でさらに確立する。
これらの結果を証明するために、適応的な段階化が必要であり、アルゴリズムが正しい目標に収束しないことを示す。
さらに、適応的なステップサイズは、非同期更新の効果に反する暗黙の重要度サンプリングの形式として解釈することができる。
技術的には、適応的なステップサイズを用いることで、各Q-ラーニング更新はサンプル履歴全体に依存し、強い相関を導入し、アルゴリズムを非マルコフ確率近似(SA)スキームにする。
この課題を克服するためのアプローチは,(1)非マルコフ的SAの時間的不均一なマルコフ的再構成,(2)適応段差と繰り返しの強い相関を断ち切るために,ほぼ確実な時間変化境界,条件付き引数,マルコフ連鎖濃度の不等式の組み合わせである。
この研究で開発されたツールは、適応的なステップサイズを持つ一般的なSAアルゴリズムの分析に広く適用される可能性が高い。
関連論文リスト
- Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysis [32.8453673919231]
ペアワイズ学習モデルの学習のためのデータ適応型サンプリング手法を用いて最適化について検討する。
ポイントワイズ学習とペアワイズ学習の顕著な違いは、入力ペア間の統計的上昇である。
論文 参考訳（メタデータ） (2025-04-03T18:24:01Z) - Towards Hyper-parameter-free Federated Learning [1.3682156035049038]
グローバルモデル更新の自動スケーリングのためのアルゴリズムを導入する。
第1のアルゴリズムでは、クライアントにおける降下検知ステップサイズ体制が、サーバの目的に対して降下を保証することが保証される。
第2のアルゴリズムは、サンプリングされたクライアントの目的値の平均値が、スケーリング係数を計算するのに必要な値サーバの実用的で効果的な代用であることを示している。
論文 参考訳（メタデータ） (2024-08-30T09:35:36Z) - Two-Step Q-Learning [0.0]
そこで本研究では,重要でない2段階のQ-ラーニングアルゴリズムを提案する。
数値実験により、2段階のQ-ラーニングとそのスムーズな変形の優れた性能が示された。
論文 参考訳（メタデータ） (2024-07-02T15:39:00Z) - Regularized Q-Learning with Linear Function Approximation [2.765106384328772]
線形汎関数近似を用いた正規化Q-ラーニングの2段階最適化について検討する。
特定の仮定の下では、提案アルゴリズムはマルコフ雑音の存在下で定常点に収束することを示す。
論文 参考訳（メタデータ） (2024-01-26T20:45:40Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - Continuation Path with Linear Convergence Rate [18.405645120971496]
経路追従アルゴリズムは、一連のサブプロブレムを順次解決する合成最適化問題によく用いられる。
本稿では,経路追従アルゴリズムの一次双対解析と,対象問題に対する線形収束率を保証するために,各サブプロブレムがどの程度正確に解けるかを決定する。
スパーシリティ誘導ペナルティによる最適化を考慮し、正規化パラメータに対するアクティブセットの変化を分析する。
論文 参考訳（メタデータ） (2021-12-09T18:42:13Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - Non-asymptotic Convergence Analysis of Two Time-scale (Natural)
Actor-Critic Algorithms [58.57004511121862]
アクタークリティカル(AC)とナチュラルアクタークリティカル(NAC)のアルゴリズムは、最適なポリシーを見つけるために2つの方法で実行されることが多い。
2つの時間スケールACは、$mathcalO(epsilon-2.5log3(epsilon-1))$で、$epsilon$-accurateの定常点に達するために、全体のサンプルの複雑さを必要とすることを示す。
我々は,動的にマルコフサンプリングが変化するため,アクターのバイアス誤差をバウンドする新しい手法を開発した。
論文 参考訳（メタデータ） (2020-05-07T15:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。