論文の概要: Momentum Q-learning with Finite-Sample Convergence Guarantee
- arxiv url: http://arxiv.org/abs/2007.15418v1
- Date: Thu, 30 Jul 2020 12:27:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-05 13:50:32.841337
- Title: Momentum Q-learning with Finite-Sample Convergence Guarantee
- Title(参考訳): 有限サンプル収束保証による運動量q学習
- Authors: Bowen Weng, Huaqing Xiong, Lin Zhao, Yingbin Liang, Wei Zhang
- Abstract要約: 本稿では,有限サンプル保証を用いたモーメントに基づくQ-ラーニングアルゴリズムのクラスを解析する。
線形関数近似とマルコフサンプリングによるMomentumQの収束保証を確立する。
提案したMomentumQが他のモーメントベースのQ-ラーニングアルゴリズムより優れていることを示す。
- 参考スコア(独自算出の注目度): 49.38471009162477
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Existing studies indicate that momentum ideas in conventional optimization
can be used to improve the performance of Q-learning algorithms. However, the
finite-sample analysis for momentum-based Q-learning algorithms is only
available for the tabular case without function approximations. This paper
analyzes a class of momentum-based Q-learning algorithms with finite-sample
guarantee. Specifically, we propose the MomentumQ algorithm, which integrates
the Nesterov's and Polyak's momentum schemes, and generalizes the existing
momentum-based Q-learning algorithms. For the infinite state-action space case,
we establish the convergence guarantee for MomentumQ with linear function
approximations and Markovian sampling. In particular, we characterize the
finite-sample convergence rate which is provably faster than the vanilla
Q-learning. This is the first finite-sample analysis for momentum-based
Q-learning algorithms with function approximations. For the tabular case under
synchronous sampling, we also obtain a finite-sample convergence rate that is
slightly better than the SpeedyQ \citep{azar2011speedy} when choosing a special
family of step sizes. Finally, we demonstrate through various experiments that
the proposed MomentumQ outperforms other momentum-based Q-learning algorithms.
- Abstract(参考訳): 既存の研究によると、従来の最適化における運動量の概念は、q学習アルゴリズムの性能を改善するのに使うことができる。
しかし、運動量に基づくq学習アルゴリズムの有限サンプル解析は、関数近似を伴わない表ケースでのみ利用可能である。
本稿では,有限サンプル保証を持つ運動量ベースのq学習アルゴリズムのクラスを解析する。
具体的には、NesterovとPolyakのモーメントスキームを統合したMomentumQアルゴリズムを提案し、既存のモーメントベースのQ-ラーニングアルゴリズムを一般化する。
無限の状態-作用空間の場合、線形関数近似とマルコフサンプリングによる MomentumQ の収束保証を確立する。
特に、バニラQ学習よりも確実に速い有限サンプル収束率を特徴付ける。
これは運動量に基づくQ-ラーニングアルゴリズムの関数近似を用いた最初の有限サンプル解析である。
同期サンプリング下での表式の場合、ステップサイズの特別な族を選択する場合、speedyq \citep{azar2011speedy} よりもわずかに良い有限サンプル収束率が得られる。
最後に,提案するmomentumqが他のmomentumベースのq-learningアルゴリズムよりも優れていることを示す。
関連論文リスト
- Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。
評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
論文 参考訳(メタデータ) (2023-10-26T18:23:21Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash
Equilibrium [62.51015395213579]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
提案アルゴリズムは粒子の動きを利用して$ilon$-mixed Nash平衡のランダム戦略の更新を表現する。
論文 参考訳(メタデータ) (2023-03-02T05:08:15Z) - A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
本稿では,ギブス分割関数を線形時間で推定する新しい量子アルゴリズムを提案する。
これは、vStefankovivc, Vempala, Vigodaの半周期的なほぼ直線時間で得られる最初のスピードアップである。
論文 参考訳(メタデータ) (2022-07-18T14:41:48Z) - Finite Horizon Q-learning: Stability, Convergence and Simulations [0.0]
有限地平面マルコフ決定過程(MDP)のためのQ-ラーニングアルゴリズムのバージョンを開発する。
有限地平線Q-ラーニングの安定性と収束に関する解析は、常微分方程式(O.D.E)法に基づいている。
論文 参考訳(メタデータ) (2021-10-27T16:18:44Z) - Efficient measure for the expressivity of variational quantum algorithms [72.59790225766777]
我々は、変分量子アルゴリズムの表現率を研究するために、統計学習理論、すなわち被覆数に関する高度なツールを利用する。
まず、任意のアンサーゼを持つVQAの表現性は、量子ゲートの数と観測可能な測定値によって上限づけられていることを示す。
次に,システムノイズを考慮した量子チップ上でのVQAの表現性について検討する。
論文 参考訳(メタデータ) (2021-04-20T13:51:08Z) - An optimal quantum sampling regression algorithm for variational
eigensolving in the low qubit number regime [0.0]
量子サンプリング回帰(QSR)は、代替の量子古典的アルゴリズムである。
低量子ビット数構造における時間的複雑さに基づいて,その利用事例を分析した。
ベンチマーク問題に対するアルゴリズムの有効性を示す。
論文 参考訳(メタデータ) (2020-12-04T00:01:15Z) - Hamilton-Jacobi Deep Q-Learning for Deterministic Continuous-Time
Systems with Lipschitz Continuous Controls [2.922007656878633]
リプシッツ連続制御を用いた連続時間決定論的最適制御問題に対するQ-learningアルゴリズムを提案する。
HJB方程式の新たな半離散バージョンが提案され、離散時間で収集されたデータを用いて、システムの力学を離散化したり近似したりすることなく、Q-ラーニングアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-10-27T06:11:04Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳(メタデータ) (2020-09-29T18:48:21Z) - K-spin Hamiltonian for quantum-resolvable Markov decision processes [0.0]
離散的、有限な割引マルコフ決定過程のKスピンハミルトン表現と等価な擬ブールコスト関数を導出する。
このKスピンハミルトニアンは、量子アルゴリズムを用いて最適なポリシーを解くための出発点を与える。
論文 参考訳(メタデータ) (2020-04-13T16:15:25Z) - Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic
Perspectives [97.16266088683061]
この論文は、運動量に基づく最適化アルゴリズムにおいてシンプレクティックな離散化スキームが重要であることを厳格に証明している。
これは加速収束を示すアルゴリズムの特性を提供する。
論文 参考訳(メタデータ) (2020-02-28T00:32:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。