論文の概要: Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2607.22982v1
• Date: Sat, 25 Jul 2026 01:37:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-28 22:34:14.955075
• Title: Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes
• Title（参考訳）: 有限-水平マルコフ決定過程における自然政策勾配の有限時間解析
• Abstract要約: 有限水平マルコフ決定過程におけるNPG(Natural Policy Gradient)について検討する。 この設定において、このアルゴリズムに対する最初の有限時間収束保証を提供する。 我々は、この定数ステップサイズ解析を、正確な集団投影オラクルにおける線形MDPに拡張する。
• 参考スコア（独自算出の注目度）: 1.217503190366097
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Natural Policy Gradient (NPG) is a well-established Reinforcement Learning algorithm that underlies widely used methods such as Trust Region Policy Optimization and Proximal Policy Optimization, both of which have demonstrated strong empirical success. In this paper, we study exact NPG in finite-horizon Markov Decision Processes with known dynamics and horizon-dependent transition kernels. We provide the first finite-time convergence guarantees for this algorithm in this setting, for which we consider both constant and increasing step size regimes. With a constant step size $η_t=η$, we prove that NPG converges sublinearly with a rate of $\mathcal{O}(H^{2}/t)$ after $t$ iterations, where $H$ is the horizon length. We also extend this constant step size analysis to linear MDPs in an exact population-projection oracle under a full support projection distribution, recovering the same sublinear rate as in the tabular setting. Furthermore, with increasing step sizes, we prove that this algorithm achieves a linear convergence rate of $\mathcal{O}\left(\left(1-\frac{1}{\vartheta_ρ}\right)^t\right)$ for a problem-dependent constant $\vartheta_ρ> 1$, and the horizon-only robust schedule of the form $η_t=η_0(H/(H-1))^t$ where $η_0>0$ and $H \geq 2$, attains this same geometric rate.
• Abstract（参考訳）: NPG(Natural Policy Gradient)は、信頼地域政策最適化(Trust Region Policy Optimization)や近親政策最適化(Proximal Policy Optimization)などの広く使われている手法を基礎として、確立された強化学習アルゴリズムである。 本稿では,有限水平マルコフ決定過程における正確なNPGについて検討する。 この設定において、このアルゴリズムに対する最初の有限時間収束保証を提供する。 定数のステップサイズが $η_t=η$ であれば、NPG は$\mathcal{O}(H^{2}/t)$ の速度で直交収束することを証明し、$H$ は地平線長である。 また、この定数ステップサイズ解析を、完全な支持射影分布の下で、正確な集団投射オラクルの線形MDPに拡張し、表の設定と同じサブリニアレートを回復する。 さらに、ステップサイズが大きくなるにつれて、このアルゴリズムは、問題依存定数 $\vartheta_ρ> 1$ に対して$\mathcal{O}\left(\left(1-\frac{1}{\vartheta_ρ}\right)^t\right)$ の線形収束率と、$η_0>0$ と $H \geq 2$ という形の地平線のみの頑健なスケジュールを達成することを証明している。

関連論文リスト

• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• $k$-SVD with Gradient Descent [18.260910876411973]
  任意の階数 $d geq 1$ の行列に対して、$k$-SVD を証明できるような、ステップサイズ選択のための単純で普遍的な規則を持つ勾配退化法を提案する。 我々の収束解析により、勾配法は魅力的な領域を持ち、この領域ではヘロン法のように振る舞う(バビロニア法)。 解析結果から,ネステロフの運動量に基づく加速度法により勾配法を拡張できることが示唆された。
  論文  参考訳（メタデータ） (2025-02-01T05:00:28Z)
• Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning [12.987019067098412]
  我々は、強化学習(RL)における政策最適化に、祝福されたネステロフの加速勾配(NAG)法を適応する。 i) $tildeO (1/t2)$, (ii) $O(e-ct)$, (ii) $O(e-ct)$。
  論文  参考訳（メタデータ） (2023-10-18T11:33:22Z)
• On the Linear Convergence of Policy Gradient under Hadamard Parameterization [4.182089296199263]
  本研究では,アダマールパラメータ化に基づく決定論的政策勾配の収束性について検討する。 すべてのイテレーションに対して$O(frac1k)$レートでエラーが減少することを示す。
  論文  参考訳（メタデータ） (2023-05-31T05:51: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)
• 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)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling [56.394284787780364]
  本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。 一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。 線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
  論文  参考訳（メタデータ） (2020-02-15T00:26:49Z)

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

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