論文の概要: Stochastic Policy Gradient Methods: Improved Sample Complexity for
Fisher-non-degenerate Policies
- arxiv url: http://arxiv.org/abs/2302.01734v1
- Date: Fri, 3 Feb 2023 13:50:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-06 16:20:49.275980
- Title: Stochastic Policy Gradient Methods: Improved Sample Complexity for
Fisher-non-degenerate Policies
- Title（参考訳）: 確率的政策勾配法:漁業非退化政策におけるサンプル複素性の改善
- Authors: Ilyas Fatkhullin and Anas Barakat and Anastasia Kireeva and Niao He
- Abstract要約: 我々は、フィッシャー非退化パラメタライズドポリシーの一般クラスに対する改善されたグローバルコンバージェンス保証を開発する。
本研究では,Implicit Gradient Transport (N-PG-IGT) を用いた正規化政策勾配法を提案し,この手法のサンプル複雑性を$tildemathcalO(varepsilon-2.5)$とする。
我々はこの複雑さをさらに改善し、ヘッセン支援再帰政策勾配を考慮し、$tilde MathcalmathcalO (varepsilon-2)$に改善する。
- 参考スコア（独自算出の注目度）: 15.452370314873143
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, the impressive empirical success of policy gradient (PG) methods
has catalyzed the development of their theoretical foundations. Despite the
huge efforts directed at the design of efficient stochastic PG-type algorithms,
the understanding of their convergence to a globally optimal policy is still
limited. In this work, we develop improved global convergence guarantees for a
general class of Fisher-non-degenerate parameterized policies which allows to
address the case of continuous state action spaces. First, we propose a
Normalized Policy Gradient method with Implicit Gradient Transport (N-PG-IGT)
and derive a $\tilde{\mathcal{O}}(\varepsilon^{-2.5})$ sample complexity of
this method for finding a global $\varepsilon$-optimal policy. Improving over
the previously known $\tilde{\mathcal{O}}(\varepsilon^{-3})$ complexity, this
algorithm does not require the use of importance sampling or second-order
information and samples only one trajectory per iteration. Second, we further
improve this complexity to $\tilde{ \mathcal{\mathcal{O}} }(\varepsilon^{-2})$
by considering a Hessian-Aided Recursive Policy Gradient ((N)-HARPG) algorithm
enhanced with a correction based on a Hessian-vector product. Interestingly,
both algorithms are $(i)$ simple and easy to implement: single-loop, do not
require large batches of trajectories and sample at most two trajectories per
iteration; $(ii)$ computationally and memory efficient: they do not require
expensive subroutines at each iteration and can be implemented with memory
linear in the dimension of parameters.
- Abstract（参考訳）: 近年,政策勾配法(PG法)の実証的成功により,理論基盤の発達が促進された。
効率的な確率的pg型アルゴリズムの設計に向けられた膨大な努力にもかかわらず、世界的最適方針への収束の理解は依然として限られている。
本研究では,連続状態動作空間の場合に対処可能な,フィッシャー非退化パラメータ化ポリシーの一般クラスに対するグローバル収束保証を改良した。
まず,Implicit Gradient Transport (N-PG-IGT) を用いた正規化政策勾配法を提案し,大域的な$\varepsilon$-optimal Policyを求めるために,この手法のサンプル複雑性を$\tilde{\mathcal{O}}(\varepsilon^{-2.5})$とする。
以前知られていた$\tilde{\mathcal{O}}(\varepsilon^{-3})$複雑さよりも改善されているため、このアルゴリズムは重要サンプリングや2階情報の使用を必要とせず、イテレーション毎に1つの軌道のみをサンプリングする。
第二に、この複雑さをさらに改善するために、Hessian-Aided Recursive Policy Gradient ((N)-HARPG) アルゴリズムを Hessian-vector product に基づく補正で拡張することにより、$\tilde{ \mathcal{\mathcal{O}} }(\varepsilon^{-2})$ となる。
興味深いことに、どちらのアルゴリズムも$である。
(i) 単純で簡単に実装できる: シングルループ、大きなトラジェクトリとサンプルのバッチをイテレーション毎に2つのトラジェクトリで必要としない。
(ii)$計算量とメモリ効率:各イテレーションで高価なサブルーチンを必要とせず、パラメータの次元で線形にメモリを実装することができる。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Provable Policy Gradient Methods for Average-Reward Markov Potential
Games [15.136494705127564]
無限水平平均報酬基準の下でマルコフポテンシャルゲームを研究する。
我々は、独立政策勾配と独立自然政策勾配に基づくアルゴリズムが、平均報酬基準に対するナッシュ均衡にグローバルに収束することを証明した。
論文 参考訳（メタデータ） (2024-03-09T00:20:33Z) - Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm
with General Parameterization for Infinite Horizon Discounted Reward Markov
Decision Processes [41.61653528766776]
本稿では, 自然政策勾配を求めるために, 加速勾配降下過程を利用する自然促進政策勾配(PGAN)アルゴリズムを提案する。
繰り返しは$mathcalO(epsilon-2)$サンプル複雑性と$mathcalO(epsilon-1)$複雑さを達成する。
Hessian-free および IS-free アルゴリズムのクラスでは、ANPG は $mathcalO(epsilon-frac12)$ の係数で最もよく知られたサンプルの複雑さを破り、それらの状態と同時に一致する。
論文 参考訳（メタデータ） (2023-10-18T03:00:15Z) - Low-Switching Policy Gradient with Exploration via Online Sensitivity
Sampling [23.989009116398208]
一般非線形関数近似を用いた低スイッチングサンプリング効率ポリシ最適化アルゴリズム LPO を設計する。
提案アルゴリズムは,$widetildeO(fractextpoly(d)varepsilon3)$サンプルのみを用いて,$varepsilon$-optimal Policyを得る。
論文 参考訳（メタデータ） (2023-06-15T23:51:46Z) - A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning [9.628032156001073]
立方正則化を取り入れた2つのポリシーニュートンアルゴリズムを提案する。
どちらのアルゴリズムも確率比法を用いて値関数の勾配とヘシアンを推定する。
特に、我々のアルゴリズムのサンプル複雑さが$epsilon$-SOSPを見つけるのに$O(epsilon-3.5)$であり、これは最先端のサンプル複雑性の$O(epsilon-4.5)$よりも改善されている。
論文 参考訳（メタデータ） (2023-04-21T13:43:06Z) - Stochastic Dimension-reduced Second-order Methods for Policy
Optimization [11.19708535159457]
各イテレーションにおいて勾配とヘシアンベクトル積のみを必要とするポリシー最適化のための新しい2次アルゴリズムを提案する。
具体的には、投影された2次元信頼領域のサブプロブレムを繰り返す次元還元二階法(DR-SOPO)を提案する。
DR-SOPOはおよそ1次定常状態に到達するために$mathcalO(epsilon-3.5)$の複雑さが得られることを示す。
さらに,拡張アルゴリズム (DVR-SOPO) を提案する。
論文 参考訳（メタデータ） (2023-01-28T12:09:58Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。
ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
論文 参考訳（メタデータ） (2021-02-22T18:56:26Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳（メタデータ） (2020-11-10T11:36:30Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。