論文の概要: Strongly-Polynomial Time and Validation Analysis of Policy Gradient Methods

• arxiv url: http://arxiv.org/abs/2409.19437v1
• Date: Wed, 23 Oct 2024 19:40:50 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-05 23:19:24.919024
• Title: Strongly-Polynomial Time and Validation Analysis of Policy Gradient Methods
• Title（参考訳）: 政策グラディエント手法の強ポリノミカル時間と検証分析
• Authors: Caleb Ju, Guanghui Lan,
• Abstract要約: 最適性ギャップ上の上界と下界の両方を提供する、単純で計算可能なギャップ関数を開発する。 ギャップ関数の収束は、最適性ギャップの収束よりも強い収束モードである。 基本方針ミラー降下は, 決定論的およびMDP的設定の両方において, 高速な分布自由収束を示すことを示す。
• 参考スコア（独自算出の注目度）: 3.722665817361884
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement learning lacks a principled measure of optimality, causing research to rely on algorithm-to-algorithm or baselines comparisons with no certificate of optimality. Focusing on finite state and action Markov decision processes (MDP), we develop a simple, computable gap function that provides both upper and lower bounds on the optimality gap. Therefore, convergence of the gap function is a stronger mode of convergence than convergence of the optimality gap, and it is equivalent to a new notion we call distribution-free convergence, where convergence is independent of any problem-dependent distribution. We show the basic policy mirror descent exhibits fast distribution-free convergence for both the deterministic and stochastic setting. We leverage the distribution-free convergence to a uncover a couple new results. First, the deterministic policy mirror descent can solve unregularized MDPs in strongly-polynomial time. Second, accuracy estimates can be obtained with no additional samples while running stochastic policy mirror descent and can be used as a termination criteria, which can be verified in the validation step.
• Abstract（参考訳）: 強化学習(Reinforcement learning)は、最適性の原則的な尺度を欠き、最適性の証明を持たないアルゴリズムからアルゴリズム、あるいはベースラインの比較に頼らざるを得ない。 有限状態および作用マルコフ決定過程(MDP)に着目し、最適性ギャップ上の上界と下界の両方を提供する単純な計算可能なギャップ関数を開発する。 したがって、ギャップ関数の収束は最適性ギャップの収束よりも強い収束モードであり、収束が任意の問題依存分布から独立であるような分布自由収束と呼ばれる新しい概念と同値である。 基本方針ミラー降下は決定論的および確率的条件の両方に対して高速な分布自由収束を示す。 分布自由収束を利用して、いくつかの新しい結果を明らかにする。 第一に、決定論的政策ミラー降下は、強いポリノミアル時間で非正規化されたMDPを解くことができる。 第2に、確率的ポリシーミラー降下の実行中に追加のサンプルなしで精度推定が得られ、検証ステップで検証できる終了基準として使用できる。

関連論文リスト

• Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs [82.34567890576423]
  我々は,非漸近収束を伴う最適決定主義政策を求めるための決定主義的政策勾配原始双対法を開発した。 D-PGPDの一次-双対反復は、最適正則化原始-双対にサブ線形速度で収束することが証明された。 我々の知る限り、これは連続空間制約型MDPに対する決定論的ポリシー探索法を提案する最初の研究であると思われる。
  論文  参考訳（メタデータ） (2024-08-19T14:11:04Z)
• 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)
• Fast Policy Learning for Linear Quadratic Control with Entropy Regularization [10.771650397337366]
  本稿では,レギュラー化政策勾配 (RPG) と反復政策最適化 (IPO) の2つの新しい政策学習手法を提案し,分析する。 正確な政策評価にアクセスできると仮定すると、どちらの手法も正規化されたLQCの最適ポリシーを見つける際に線形に収束することが証明される。
  論文  参考訳（メタデータ） (2023-11-23T19:08:39Z)
• Optimization Landscape of Policy Gradient Methods for Discrete-time Static Output Feedback [22.21598324895312]
  本稿では,静的な出力フィードバック制御に適用した場合に,ポリシー勾配法に固有の最適化環境を解析する。 3つの政策勾配法に対する定常点への収束(およびほぼ次元自由率)に関する新しい知見を導出する。 我々は,バニラポリシー勾配法が,そのようなミニマに近づいた場合,局所最小マに対して線形収束を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-29T14:25:57Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。 我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。 我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
  論文  参考訳（メタデータ） (2023-06-20T17:27:31Z)
• High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
  本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。 高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
  論文  参考訳（メタデータ） (2023-05-30T12:58:39Z)
• Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies [115.86431674214282]
  我々は、無限水平割引マルコフ決定過程を考察し、自然政策勾配(NPG)とQ-NPG法の収束率を対数線形ポリシークラスで検討する。 両手法が線形収束率と $mathcalO (1/epsilon2)$サンプル複雑度を, 単純で非適応的な幾何的に増加するステップサイズを用いて達成できることを示す。
  論文  参考訳（メタデータ） (2022-10-04T06:17:52Z)
• Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
  最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。 次に,政策最適化におけるコミット率の概念を紹介する。 第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
  論文  参考訳（メタデータ） (2021-10-29T06:35:44Z)
• Near Optimal Policy Optimization via REPS [33.992374484681704]
  emphrelative entropy policy search (reps) は多くのシミュレーションと実世界のロボットドメインでポリシー学習に成功した。 勾配に基づく解法を用いる場合、REPSの性能には保証がない。 最適規則化ポリシーに好適な収束を維持するためのパラメータ更新を計算するために,基礎となる決定プロセスへの表現的アクセスを利用する手法を提案する。
  論文  参考訳（メタデータ） (2021-03-17T16:22:59Z)
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization [44.24881971917951]
  自然政策勾配法(NPG)は、最も広く使われている政策最適化アルゴリズムの一つである。 我々は,ソフトマックスパラメータ化の下で,エントロピー規則化NPG法に対する収束保証を開発する。 この結果から, エントロピー正則化の役割を浮き彫りにした。
  論文  参考訳（メタデータ） (2020-07-13T17:58:41Z)
• Stable Policy Optimization via Off-Policy Divergence Regularization [50.98542111236381]
  信頼地域政策最適化(TRPO)とPPO(Pximal Policy Optimization)は、深層強化学習(RL)において最も成功した政策勾配アプローチの一つである。 本稿では, 連続的な政策によって引き起こされる割引状態-行動訪問分布を, 近接項で抑制し, 政策改善を安定化させる新しいアルゴリズムを提案する。 提案手法は, ベンチマーク高次元制御タスクの安定性と最終的な性能向上に有効である。
  論文  参考訳（メタデータ） (2020-03-09T13:05:47Z)

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

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