論文の概要: On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2403.06806v1
• Date: Mon, 11 Mar 2024 15:25:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-12 18:34:07.104088
• Title: On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
• Title（参考訳）: 平均報酬マルコフ決定過程における政策勾配のグローバル収束について
• Authors: Navdeep Kumar, Yashaswini Murthy, Itai Shufaro, Kfir Y. Levy, R. Srikant and Shie Mannor
• Abstract要約: 我々は、平均報酬マルコフ決定過程(MDP)の文脈における政策勾配の最初の有限時間大域収束解析を示す。 我々の分析によると、ポリシー勾配は、$Oleft(frac1Tright)$のサブリニアレートで最適ポリシーに収束し、$Oleft(log(T)right)$ regretに変換され、$T$は反復数を表す。
• 参考スコア（独自算出の注目度）: 50.68789924454235
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the first finite time global convergence analysis of policy gradient in the context of infinite horizon average reward Markov decision processes (MDPs). Specifically, we focus on ergodic tabular MDPs with finite state and action spaces. Our analysis shows that the policy gradient iterates converge to the optimal policy at a sublinear rate of $O\left({\frac{1}{T}}\right),$ which translates to $O\left({\log(T)}\right)$ regret, where $T$ represents the number of iterations. Prior work on performance bounds for discounted reward MDPs cannot be extended to average reward MDPs because the bounds grow proportional to the fifth power of the effective horizon. Thus, our primary contribution is in proving that the policy gradient algorithm converges for average-reward MDPs and in obtaining finite-time performance guarantees. In contrast to the existing discounted reward performance bounds, our performance bounds have an explicit dependence on constants that capture the complexity of the underlying MDP. Motivated by this observation, we reexamine and improve the existing performance bounds for discounted reward MDPs. We also present simulations to empirically evaluate the performance of average reward policy gradient algorithm.
• Abstract（参考訳）: 無限水平平均報酬マルコフ決定過程(MDP)の文脈における政策勾配の有限時間大域収束解析について述べる。 具体的には,有限状態および作用空間を持つエルゴード表型MDPに着目した。 我々の分析によれば、ポリシー勾配は、$O\left({\frac{1}{T}}\right) のサブラインレートで最適ポリシーに収束し、$O\left({\log(T)}\right) に変換され、$T$ は反復数を表す。 割引報酬MDPの性能限界に関する以前の研究は、有効地平線の5番目のパワーに比例して増大するため、平均報酬MDPにまで拡張することはできない。 したがって、ポリシー勾配アルゴリズムが平均逆 MDP に対して収束し、有限時間の性能保証を得ることを示すのが主な貢献である。 既存の割引報酬性能バウンダリとは対照的に、我々の性能バウンダリは、基礎となるMDPの複雑さを捉える定数に明示的に依存する。 この観察に感銘を受けて、割引報酬MDPの既存の性能限界を再検討し、改善する。 また,平均報酬政策勾配アルゴリズムの性能を実証的に評価するシミュレーションを行った。

関連論文リスト

• Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs [82.34567890576423]
  我々は,非漸近収束を伴う最適決定主義政策を求めるための決定主義的政策勾配原始双対法を開発した。 D-PGPDの一次-双対反復は、最適正則化原始-双対にサブ線形速度で収束することが証明された。 我々の知る限り、これは連続空間制約型MDPに対する決定論的ポリシー探索法を提案する最初の研究であると思われる。
  論文  参考訳（メタデータ） (2024-08-19T14:11:04Z)
• Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm [34.593772931446125]
  本稿では, 制約を適切に管理し, グローバルな最適政策の実現に向けて, 後悔の少ない保証を確実にする主元的二元的ポリシー勾配アルゴリズムを提案する。 提案アルゴリズムは, 目的的後悔に対して$tildemathcalO(T4/5) $tildemathcalO(T4/5)$ 制約違反境界を達成する。
  論文  参考訳（メタデータ） (2024-02-03T05:35:58Z)
• Score-Aware Policy-Gradient Methods and Performance Guarantees using Local Lyapunov Conditions: Applications to Product-Form Stochastic Networks and Queueing Systems [1.747623282473278]
  本稿では,ネットワーク上の決定過程(MDP)から得られる定常分布のタイプを利用したモデル強化学習(RL)のポリシー段階的手法を提案する。 具体的には、政策パラメータによってMDPの定常分布がパラメータ化されている場合、平均回帰推定のための既存の政策手法を改善することができる。
  論文  参考訳（メタデータ） (2023-12-05T14:44:58Z)
• Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes [38.879933964474326]
  我々は、無限水平平均報酬マルコフ決定過程(MDP)を考える。 政策勾配に基づくアルゴリズムを提案し,その大域収束特性を示す。 提案アルゴリズムが $tildemathcalO(T3/4)$ regret であることを示す。
  論文  参考訳（メタデータ） (2023-09-05T03:22:46Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。 我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。 我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
  論文  参考訳（メタデータ） (2023-06-20T17:27:31Z)
• Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms [11.013390624382259]
  多くのポリシーベース強化学習(RL)アルゴリズムは、近似ポリシー反復(PI)のインスタンス化と見なすことができる。 平均報酬目標が有意義なパフォーマンス指標であるアプリケーションでは、割引された報酬の定式化がしばしば使用され、割引係数は1,$近くで、期待される地平線を非常に大きくするのと同等である。 本稿では、この開放的な問題を、平均逆 MDP に対する最初の有限時間誤差境界を求めることで解決し、政策評価や政策改善の誤差がゼロになるにつれて、その誤差が極限でゼロとなることを示す。
  論文  参考訳（メタデータ） (2023-02-02T22:37:47Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• Convergence of policy gradient for entropy regularized MDPs with neural network approximation in the mean-field regime [0.0]
  無限水平連続状態および行動空間,エントロピー規則化マルコフ決定過程(MDPs)に対する政策勾配のグローバル収束性について検討する。 結果は非線形フォッカー-プランク-コルモゴロフ方程式の慎重な解析に依存する。
  論文  参考訳（メタデータ） (2022-01-18T20:17:16Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  本稿では、時間差学習(TD)による政策評価の世代的視点について考察する。 OS-GPTDアプローチは、状態-逆ペアのシーケンスを観測することにより、与えられたポリシーの値関数を推定するために開発された。 1つの固定カーネルに関連する限られた表現性を緩和するために、GP前の重み付けアンサンブル(E)を用いて代替のスキームを生成する。
  論文  参考訳（メタデータ） (2021-12-01T23:15: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)

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

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