論文の概要: Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2302.11381v1
• Date: Wed, 22 Feb 2023 13:55:08 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-23 15:04:12.845240
• Title: Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes
• Title（参考訳）: 割引マルコフ決定過程における厳密な政策ミラー降下の最適収束率
• Authors: Emmeran Johnson, Ciara Pike-Burke, Patrick Rebeschini
• Abstract要約: 古典的強化学習アルゴリズムの次元自由線型$gamma$-rateは、適応的なステップサイズの下で、非正規化ポリシーミラーDescent(PMD)アルゴリズムの一般ファミリーによって達成可能であることを示す。 また、解析結果を不正確な設定にまで拡張し、生成モデルの下で非正規化されたPMDに対して、最初の次元自由な$varepsilon$-optimal sample complexityを確立する。
• 参考スコア（独自算出の注目度）: 20.647421751914464
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The classical algorithms used in tabular reinforcement learning (Value Iteration and Policy Iteration) have been shown to converge linearly with a rate given by the discount factor $\gamma$ of a discounted Markov Decision Process. Recently, there has been an increased interest in the study of gradient based methods. In this work, we show that the dimension-free linear $\gamma$-rate of classical reinforcement learning algorithms can be achieved by a general family of unregularised Policy Mirror Descent (PMD) algorithms under an adaptive step-size. We also provide a matching worst-case lower-bound that demonstrates that the $\gamma$-rate is optimal for PMD methods. Our work offers a novel perspective on the convergence of PMD. We avoid the use of the performance difference lemma beyond establishing the monotonic improvement of the iterates, which leads to a simple analysis that may be of independent interest. We also extend our analysis to the inexact setting and establish the first dimension-free $\varepsilon$-optimal sample complexity for unregularised PMD under a generative model, improving upon the best-known result.
• Abstract（参考訳）: グラフ型強化学習(値反復とポリシー反復)で使用される古典的アルゴリズムは、割引されたマルコフ決定過程の割引係数$\gamma$で与えられる速度で線形に収束することが示されている。 近年,勾配法の研究への関心が高まっている。 本研究では,古典的強化学習アルゴリズムの次元自由線型$\gamma$-rateが,適応的なステップサイズの下で,非正規化ポリシミラー・ディフレクション(PMD)アルゴリズムの一般ファミリーによって実現可能であることを示す。 また,pmd 法において$\gamma$-rate が最適であることを示す,最下位値のマッチングも提供する。 本研究はpmdの収束に関する新しい視点を提供する。 私たちは、イテレートの単調な改善を確立することよりも、パフォーマンスの違いの補題の使用を回避し、独立した関心を持つ可能性のある単純な分析へと繋がる。 非正規化pmdの非正規化pmdに対する最初の次元フリーな$\varepsilon$-optimalサンプル複雑性を生成モデルで確立し、最もよく知られた結果に基づいて改善する。

関連論文リスト

• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。 提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
  論文  参考訳（メタデータ） (2024-10-02T08:46:34Z)
• Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs [82.34567890576423]
  我々は,非漸近収束を伴う最適決定主義政策を求めるための決定主義的政策勾配原始双対法を開発した。 D-PGPDの一次-双対反復は、最適正則化原始-双対にサブ線形速度で収束することが証明された。 我々の知る限り、これは連続空間制約型MDPに対する決定論的ポリシー探索法を提案する最初の研究であると思われる。
  論文  参考訳（メタデータ） (2024-08-19T14:11:04Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。 過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。 報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
  論文  参考訳（メタデータ） (2024-05-26T05:38:50Z)
• Policy Mirror Descent with Lookahead [0.46040036610482665]
  Policy Mirror Descent (PMD) はソフトポリシー 正規化された1段階の欲求政策改善を実装するアルゴリズム。 我々は,多段階の欲求政策改善を取り入れた新しいPMDアルゴリズムである$h$-PMDを提案する。 我々は, 次元自由な$gammah$-linearコンバージェンスレートを, 多段階グリーディポリシの計算により, $h$-PMDがより高速な次元自由な$gammah$-linearコンバージェンスレートを享受できることを示す。
  論文  参考訳（メタデータ） (2024-03-21T06:10:51Z)
• On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes [50.68789924454235]
  我々は、平均報酬マルコフ決定過程(MDP)の文脈における政策勾配の最初の有限時間大域収束解析を示す。 我々の分析によると、ポリシー勾配は、$Oleft(frac1Tright)$のサブリニアレートで最適ポリシーに収束し、$Oleft(log(T)right)$ regretに変換され、$T$は反復数を表す。
  論文  参考訳（メタデータ） (2024-03-11T15:25:03Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。 我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。 我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
  論文  参考訳（メタデータ） (2023-06-20T17:27:31Z)
• A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes [13.466249082564213]
  本稿では,全情報フィードバックを用いた表層線形MDPに対するPPOの楽観的変種を提案する。 既存のポリシーベースのアルゴリズムと比較して, 線形MDPと逆線形MDPの双方において, 完全な情報付きで, 最先端の後悔点を達成している。
  論文  参考訳（メタデータ） (2023-05-15T17:55:24Z)
• First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
  我々はロバストマルコフ決定過程(MDP)の解法を考える。 MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。 $(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
  論文  参考訳（メタデータ） (2022-09-21T18:10:28Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Stochastic first-order methods for average-reward Markov decision processes [10.023632561462712]
  平均回帰マルコフ決定過程(AMDP)について検討し,政策最適化と政策評価の両面において理論的確証が強い新しい一階法を開発した。 政策評価と政策最適化の部分を組み合わせることで、生成的およびマルコフ的ノイズモデルの両方の下で、AMDPを解くためのサンプル複雑性結果を確立する。
  論文  参考訳（メタデータ） (2022-05-11T23:02:46Z)

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

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