論文の概要: Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to $Q$-Learning
- arxiv url: http://arxiv.org/abs/2508.05984v1
- Date: Fri, 08 Aug 2025 03:35:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-11 20:39:06.063591
- Title: Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to $Q$-Learning
- Title(参考訳): 非線形セミノルム縮約に対するパラメータフリー最適レートと$Q$-Learningへの応用
- Authors: Ankur Naskar, Gugan Thoppe, Vijay Gupta,
- Abstract要約: 平均逆テキストit$Q$-learningとtextitTD-learningを解くアルゴリズムは、半ノルムの収縮を伴うことが多い。
本研究では, 非線形摂動を含む線形再帰として平均誤差をリキャストし, 半ノルムの縮約と好ましく誘導されるノルムの単調性とを結合することにより非線形性をテームする。
パラメータフリーな$tildeO (1/sqrtt)$$Q$学習の最適レートは、平均逆および指数関数的に割引された設定の両方で得られる。
- 参考スコア(独自算出の注目度): 3.686808512438363
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Algorithms for solving \textit{nonlinear} fixed-point equations -- such as average-reward \textit{$Q$-learning} and \textit{TD-learning} -- often involve semi-norm contractions. Achieving parameter-free optimal convergence rates for these methods via Polyak--Ruppert averaging has remained elusive, largely due to the non-monotonicity of such semi-norms. We close this gap by (i.) recasting the averaged error as a linear recursion involving a nonlinear perturbation, and (ii.) taming the nonlinearity by coupling the semi-norm's contraction with the monotonicity of a suitably induced norm. Our main result yields the first parameter-free $\tilde{O}(1/\sqrt{t})$ optimal rates for $Q$-learning in both average-reward and exponentially discounted settings, where $t$ denotes the iteration index. The result applies within a broad framework that accommodates synchronous and asynchronous updates, single-agent and distributed deployments, and data streams obtained either from simulators or along Markovian trajectories.
- Abstract(参考訳): 固定点方程式(例えば average-reward \textit{$Q$-learning} や \textit{TD-learning} など)を解くアルゴリズムは、半ノルムの収縮を伴うことが多い。
Polyak--Ruppert平均化によるこれらの手法のパラメータフリー最適収束率の達成は、主にそのような半ノルムの非単調性のために、解明され続けている。
このギャップを、(i) 非線形摂動を含む線形再帰として平均誤差を再キャストし、(ii) 半ノルムの縮約と好ましく誘導されるノルムの単調性とを結合することにより非線形性を利用する。
パラメータフリーの$\tilde{O}(1/\sqrt{t})$Optimative rate for $Q$-learning for average-reward and indexly discounted settings, ここで$t$は反復指数を表す。
その結果は、同期と非同期の更新、単一エージェントと分散デプロイメント、シミュレータから得たデータストリーム、あるいはMarkovianのトラジェクトリに沿ったデータストリームに対応する広範なフレームワークに適用される。
関連論文リスト
- Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。
これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
論文 参考訳(メタデータ) (2024-10-03T16:08:16Z) - High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。
解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
論文 参考訳(メタデータ) (2023-10-28T18:53:41Z) - Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。
また、勾配法のようなベースラインよりも2~3$times$早く収束できることも示している。
論文 参考訳(メタデータ) (2023-10-21T00:03:54Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - To Each Optimizer a Norm, To Each Norm its Generalization [31.682969645989512]
過度なパラメータ化と過度なパラメータ化の条件下でのトレーニングデータを補間する線形モデルに対する最適化手法の暗黙的な正規化について検討する。
我々は、標準最大値 l2-margin への収束解析は任意であり、データによって誘導されるノルムの最小化がより良い一般化をもたらすことを示す。
論文 参考訳(メタデータ) (2020-06-11T21:07:38Z) - Support recovery and sup-norm convergence rates for sparse pivotal
estimation [79.13844065776928]
高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。
非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
論文 参考訳(メタデータ) (2020-01-15T16:11:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。