論文の概要: Provably Efficient Gauss-Newton Temporal Difference Learning Method with
Function Approximation
- arxiv url: http://arxiv.org/abs/2302.13087v1
- Date: Sat, 25 Feb 2023 14:14:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-28 19:08:41.260684
- Title: Provably Efficient Gauss-Newton Temporal Difference Learning Method with
Function Approximation
- Title(参考訳): 関数近似を用いた確率効率の良いガウスニュートン時間差分学習法
- Authors: Zhifa Ke, Zaiwen Wen, Junyu Zhang
- Abstract要約: 関数近似を用いたQ値推定問題の解法としてガウスニュートン時間差分法(GNTD)を提案する。
本研究では, 線形, ニューラルネットワーク, 一般スムーズ関数近似の下でのGNTDの有限サンプル非漸近収束を導出した。
- 参考スコア(独自算出の注目度): 9.661245904728618
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, based on the spirit of Fitted Q-Iteration (FQI), we propose a
Gauss-Newton Temporal Difference (GNTD) method to solve the Q-value estimation
problem with function approximation. In each iteration, unlike the original FQI
that solves a nonlinear least square subproblem to fit the Q-iteration, the
GNTD method can be viewed as an \emph{inexact} FQI that takes only one
Gauss-Newton step to optimize this subproblem, which is much cheaper in
computation. Compared to the popular Temporal Difference (TD) learning, which
can be viewed as taking a single gradient descent step to FQI's subproblem per
iteration, the Gauss-Newton step of GNTD better retains the structure of FQI
and hence leads to better convergence. In our work, we derive the finite-sample
non-asymptotic convergence of GNTD under linear, neural network, and general
smooth function approximations. In particular, recent works on neural TD only
guarantee a suboptimal $\mathcal{\mathcal{O}}(\epsilon^{-4})$ sample
complexity, while GNTD obtains an improved complexity of
$\tilde{\mathcal{O}}(\epsilon^{-2})$. Finally, we validate our method via
extensive experiments in both online and offline RL problems. Our method
exhibits both higher rewards and faster convergence than TD-type methods,
including DQN.
- Abstract(参考訳): 本稿では,FQI(Fitted Q-Iteration)の精神に基づき,関数近似を用いたQ値推定問題の解法としてガウスニュートン時間差分法(GNTD)を提案する。
各イテレーションにおいて、q-イテレーションに適合する非線形最小二乗部分問題を解く元のfqiとは異なり、gntd法は、このサブプロブレムを最適化するのに1つのガウスニュートンステップしかかからない \emph{inexact} fqiと見なすことができる。
GNTDのガウス・ニュートンのステップは、FQIの構造をより良く維持し、結果としてより収束させる。
本研究では, 線形, ニューラルネットワーク, 一般スムーズ関数近似の下でGNTDの有限サンプル非漸近収束を導出した。
特に、ニューラル TD に関する最近の研究は、サブ最適 $\mathcal{\mathcal{O}}(\epsilon^{-4})$サンプル複雑性しか保証していないが、GNTD は $\tilde{\mathcal{O}}(\epsilon^{-2})$ の改善された複雑性を得る。
最後に、オンラインおよびオフラインのrl問題の両方において、広範囲な実験を通して、この手法を検証する。
提案手法は,DQNを含むTD型よりも高い報酬と高速収束を示す。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳(メタデータ) (2022-09-12T06:53:24Z) - Finite-Time Error Bounds for Greedy-GQ [25.655180037837766]
We show that Greedy-GQ algorithm converges under $1/s。
我々の分析は、実際の収束を早めるためのステップサイズの選択を提供し、貿易の複雑さと得られた政策の質を示唆する。
論文 参考訳(メタデータ) (2022-09-06T15:04:57Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳(メタデータ) (2021-02-15T07:10:33Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳(メタデータ) (2021-02-05T14:02:20Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳(メタデータ) (2020-09-29T18:48:21Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。