論文の概要: On the Convergence Rates of Policy Gradient Methods

• arxiv url: http://arxiv.org/abs/2201.07443v1
• Date: Wed, 19 Jan 2022 07:03:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-20 14:52:36.416065
• Title: On the Convergence Rates of Policy Gradient Methods
• Title（参考訳）: 政策勾配法の収束率について
• Authors: Lin Xiao
• Abstract要約: 有限状態部分空間における幾何的に割引された支配問題を考える。 試料中の直交勾配のパラリゼーションにより、勾配の一般的な複雑さを解析できることが示される。
• 参考スコア（独自算出の注目度）: 9.74841674275568
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider infinite-horizon discounted Markov decision problems with finite state and action spaces. We show that with direct parametrization in the policy space, the weighted value function, although non-convex in general, is both quasi-convex and quasi-concave. While quasi-convexity helps explain the convergence of policy gradient methods to global optima, quasi-concavity hints at their convergence guarantees using arbitrarily large step sizes that are not dictated by the Lipschitz constant charactering smoothness of the value function. In particular, we show that when using geometrically increasing step sizes, a general class of policy mirror descent methods, including the natural policy gradient method and a projected Q-descent method, all enjoy a linear rate of convergence without relying on entropy or other strongly convex regularization. In addition, we develop a theory of weak gradient-mapping dominance and use it to prove sharper sublinear convergence rate of the projected policy gradient method. Finally, we also analyze the convergence rate of an inexact policy mirror descent method and estimate its sample complexity under a simple generative model.
• Abstract（参考訳）: 有限状態および作用空間を持つ無限水平割引マルコフ決定問題を考える。 政策空間における直接パラメトリゼーションでは、重み付き値関数は一般には非凸であるが、準凸と準凸の両方であることが示される。 準凸性は、政策勾配法のグローバルオプティマへの収束を説明するのに役立つが、準凸性は、値関数の滑らかさを特徴付けるリプシッツ定数によって引き起こされない任意の大きなステップサイズを用いて、それらの収束保証を示唆する。 特に, 幾何的に増加するステップサイズ, 自然方針勾配法, 投影Q-descent法などの一般的な方針ミラー降下法を用いることで, エントロピーや凸正則化に頼らずに収束率の線形化を享受できることが示される。 さらに,弱勾配行列支配理論を開発し,それを用いて予測された政策勾配法のよりシャープなサブ線形収束率を示す。 最後に,不正確なポリシーミラー降下法の収束率を解析し,そのサンプル複雑性を単純な生成モデルで推定する。

関連論文リスト

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• Elementary Analysis of Policy Gradient Methods [3.468656086349638]
  本稿では、割引MDPの設定に焦点をあて、前述の政策最適化手法の体系的研究を行う。 1)任意の一定のステップサイズに対する投影された方針勾配の大域的線形収束、2)任意の一定のステップサイズに対するソフトマックス方針勾配の大域的線形収束、3)任意の一定のステップサイズに対するソフトマックス自然政策勾配の大域的線形収束、4)既存の結果よりも広い一定のステップサイズに対するエントロピー正規化ソフトマックス方針勾配の大域的線形収束、5)エントロピー正規化自然政策勾配の厳密な局所的収束率、6)新しい局所的2次収束率。
  論文  参考訳（メタデータ） (2024-04-04T11:16:16Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。 我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。 我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
  論文  参考訳（メタデータ） (2023-06-20T17:27:31Z)
• Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies [115.86431674214282]
  我々は、無限水平割引マルコフ決定過程を考察し、自然政策勾配(NPG)とQ-NPG法の収束率を対数線形ポリシークラスで検討する。 両手法が線形収束率と $mathcalO (1/epsilon2)$サンプル複雑度を, 単純で非適応的な幾何的に増加するステップサイズを用いて達成できることを示す。
  論文  参考訳（メタデータ） (2022-10-04T06:17:52Z)
• Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization [18.072051868187934]
  正規化されていない自然政策アルゴリズムの収束速度を対数線形ポリシーパラメトリゼーションを用いて解析する。 このアルゴリズムは、決定論の場合と同じ線形保証を誤差項まで楽しむことを示す。
  論文  参考訳（メタデータ） (2022-09-30T11:17:44Z)
• Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs [21.347689976296834]
  我々は、割引された最適レート問題を解くために、自然政策勾配法を用いる。 また、2つのサンプルベースNPG-PDアルゴリズムに対して収束と有限サンプル保証を提供する。
  論文  参考訳（メタデータ） (2022-06-06T04:28:04Z)
• Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization [20.651913793555163]
  古典的エントロピー正規化政策勾配法をソフトマックス政策パラメトリゼーションで再検討する。 提案したアルゴリズムに対して,大域的最適収束結果と$widetildemathcalO(frac1epsilon2)$のサンプル複雑性を確立する。
  論文  参考訳（メタデータ） (2021-10-19T17:21:09Z)
• 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)
• Complexity Guarantees for Polyak Steps with Momentum [76.97851351276165]
  そこでは,この知識を最適な値である$f_*$で置き換える。 まず、Polyak ステップによる単純な勾配勾配の古典的な場合よりも若干改善された収束境界を示し、その後、収束保証とともに、Polyak ステップと運動量を持つ加速勾配法を導出する。
  論文  参考訳（メタデータ） (2020-02-03T17:50:28Z)
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization [80.03647903934723]
  我々は、勾配収束法を期待する適応勾配法を証明した。 解析では、非理解勾配境界の最適化において、より適応的な勾配法に光を当てた。
  論文  参考訳（メタデータ） (2018-08-16T20:25:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。