論文の概要: Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted
Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2302.11381v3
- Date: Tue, 21 Nov 2023 20:17:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 19:33:38.443253
- 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が達成可能であることを示す。
- 参考スコア(独自算出の注目度): 18.35462792871242
- 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, PMD algorithmically regularises the policy improvement step of PI.
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 for PMD 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 が達成可能であることを示す。
我々は,PMD法およびPI法において,$\gamma$-rateが最適であること,およびそれを実現するためには適応的なステップサイズが必要であることを示す,一致した下界を提供する。
我々の研究は、PMDを利率最適化とステップサイズの必要性に関連付ける最初のものである。
PMDの収束に関する我々の研究は、性能差補題の使用を回避し、独立利害の直接的な分析に繋がる。
また,解析を不正確な設定にまで拡張し,非正規化PMDに対する第1次元最適サンプル複雑性を生成モデルで確立し,最もよく知られた結果を改善する。
関連論文リスト
- 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) - Convergence for Natural Policy Gradient on Infinite-State Average-Reward
Markov Decision Processes [15.89915930948668]
無限状態平均逆 MDP に対する NPG アルゴリズムの第一収束率を証明した。
大規模な待ち行列型MDPの文脈では、MaxWeightポリシーは私たちの初期政治要件を満たすのに十分であることを示す。
論文 参考訳(メタデータ) (2024-02-07T21:43:57Z) - Last-Iterate Convergent Policy Gradient Primal-Dual Methods for
Constrained MDPs [107.28031292946774]
無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。
我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。
我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
論文 参考訳(メタデータ) (2023-06-20T17:27:31Z) - Sharp high-probability sample complexities for policy evaluation with
linear function approximation [99.51752176624818]
本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。
高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
論文 参考訳(メタデータ) (2023-05-30T12:58:39Z) - 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) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳(メタデータ) (2022-08-17T18:49:53Z) - 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.483316336206903]
平均回帰マルコフ決定過程(AMDP)の問題点について検討する。
我々は,政策評価と最適化の両面において,強力な理論的保証を持つ新しい一階法を開発した。
論文 参考訳(メタデータ) (2022-05-11T23:02:46Z) - Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。
ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。
そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-08T00:43:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。