論文の概要: 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法などの一般的な方針ミラー降下法を用いることで, エントロピーや凸正則化に頼らずに収束率の線形化を享受できることが示される。
さらに,弱勾配行列支配理論を開発し,それを用いて予測された政策勾配法のよりシャープなサブ線形収束率を示す。
最後に,不正確なポリシーミラー降下法の収束率を解析し,そのサンプル複雑性を単純な生成モデルで推定する。
関連論文リスト
- Last-Iterate Convergent Policy Gradient Primal-Dual Methods for
Constrained MDPs [107.28031292946774]
無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。
我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。
我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
論文 参考訳(メタデータ) (2023-06-20T17:27:31Z) - Sharp high-probability sample complexities for policy evaluation with
linear function approximation [99.51752176624818]
本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。
高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
論文 参考訳(メタデータ) (2023-05-30T12:58:39Z) - Geometry and convergence of natural policy gradient methods [0.0]
規則的な政策パラメトリゼーションを伴う無限水平割引マルコフ決定過程におけるいくつかの自然政策勾配法(NPG)の収束について検討する。
様々なNPGや報酬関数に対して、状態作用空間の軌跡がヘッセン幾何学に関する勾配流の解であることを示す。
論文 参考訳(メタデータ) (2022-11-03T19:16:15Z) - 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 [24.582720609592464]
我々は、割引された最適レート問題を解くために、自然政策勾配法を用いる。
また、2つのサンプルベースNPG-PDアルゴリズムに対して収束と有限サンプル保証を提供する。
論文 参考訳(メタデータ) (2022-06-06T04:28:04Z) - Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy
Gradient Methods with Entropy Regularization [9.622367651590878]
古典的エントロピー正規化政策勾配法をソフトマックス政策パラメトリゼーションで再検討する。
エントロピー項によって導入された対数的ポリシー報酬により、推定子自身は一般に非有界であることが証明されるが、分散は一様有界である。
これにより、定常点と大域的最適ポリシーの両方に対するエントロピー正規化ポリシー勾配法の最初の収束結果の開発が可能となる。
論文 参考訳(メタデータ) (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) - Statistically Efficient Off-Policy Policy Gradients [80.42316902296832]
政治外のデータから政策勾配を統計的に効率的に推定する。
パラメトリックな仮定を伴わずに下界を実現するメタアルゴリズムを提案する。
我々は、新たな推定政策勾配の方向へ進む際に、定常点に近づく速度の保証を確立する。
論文 参考訳(メタデータ) (2020-02-10T18:41:25Z) - Complexity Guarantees for Polyak Steps with Momentum [76.97851351276165]
そこでは,この知識を最適な値である$f_*$で置き換える。
まず、Polyak ステップによる単純な勾配勾配の古典的な場合よりも若干改善された収束境界を示し、その後、収束保証とともに、Polyak ステップと運動量を持つ加速勾配法を導出する。
論文 参考訳(メタデータ) (2020-02-03T17:50:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。