論文の概要: 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サンプル複雑性を生成モデルで確立し、最もよく知られた結果に基づいて改善する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。