論文の概要: Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted
Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2302.11381v2
- Date: Tue, 30 May 2023 14:30:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 01:30:11.521582
- Title: Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted
Markov Decision Processes
- Title（参考訳）: 割引マルコフ決定過程における厳密な政策ミラー降下の最適収束率
- Authors: Emmeran Johnson, Ciara Pike-Burke, Patrick Rebeschini
- Abstract要約: Policy Mirror Descentは、強化学習における様々な新しい基本的な手法を網羅するアルゴリズムのファミリーである。
不正確な政策評価を伴う政策反復の不安定性により、不規則なPMDは、目的関数を正規化することなく、PIの政策改善ステップをアルゴリズム的に規則化する。
我々は,適応的なステップサイズの下で,非正規化PSDアルゴリズムの一般ファミリーによって,PIの次元自由な$gamma$-rateが達成可能であることを示す。
- 参考スコア（独自算出の注目度）: 20.647421751914464
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Policy Mirror Descent (PMD) is a general family of algorithms that covers a
wide range of novel and fundamental methods in reinforcement learning.
Motivated by the instability of policy iteration (PI) with inexact policy
evaluation, unregularised PMD algorithmically regularises the policy
improvement step of PI without regularising the objective function. With exact
policy evaluation, PI is known to converge linearly with a rate given by the
discount factor $\gamma$ of a Markov Decision Process. In this work, we bridge
the gap between PI and PMD with exact policy evaluation and show that the
dimension-free $\gamma$-rate of PI can be achieved by the general family of
unregularised PMD algorithms under an adaptive step-size. We show that both the
rate and step-size are unimprovable for PMD: we provide matching lower bounds
that demonstrate that the $\gamma$-rate is optimal for PMD methods as well as
PI and that the adaptive step-size is necessary to achieve it. Our work is the
first to relate PMD to rate-optimality and step-size necessity. Our study of
the convergence of PMD avoids the use of the performance difference lemma,
which leads to a direct analysis of independent interest. We also extend the
analysis to the inexact setting and establish the first dimension-optimal
sample complexity for unregularised PMD under a generative model, improving
upon the best-known result.
- Abstract（参考訳）: Policy Mirror Descent (PMD) は、強化学習における様々な新しい基本的な手法を網羅するアルゴリズムの一般的なファミリーである。
不正確な政策評価を伴う政策反復(PI)の不安定性により、不規則なPMDは、目的関数を正規化することなく、PIの政策改善ステップをアルゴリズム的に規則化する。
正確な政策評価では、PIはマルコフ決定過程の割引係数$\gamma$によって与えられるレートで線形収束することが知られている。
本研究では, PI と PMD のギャップを厳密なポリシー評価で埋めるとともに, 適応的なステップサイズで非正規化 PMD アルゴリズムの一般ファミリーによって, PI の次元自由な$\gamma$-rate が達成可能であることを示す。
我々は,PSD法およびPI法において,$\gamma$-rateが最適であること,それを実現するためには適応的なステップサイズが必要であることを示す,一致した下界を提供する。
我々の研究は、PMDを利率最適化とステップサイズの必要性に関連付ける最初のものである。
PMDの収束に関する我々の研究は、性能差補題の使用を回避し、独立利害の直接的な分析に繋がる。
また,解析を不正確な設定にまで拡張し,非正規化PMDに対する第1次元最適サンプル複雑性を生成モデルで確立し,最もよく知られた結果を改善する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。