論文の概要: Policy-based Primal-Dual Methods for Convex Constrained Markov Decision
Processes
- arxiv url: http://arxiv.org/abs/2205.10715v1
- Date: Sun, 22 May 2022 02:50:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-30 05:26:49.486916
- Title: Policy-based Primal-Dual Methods for Convex Constrained Markov Decision
Processes
- Title(参考訳): Convex Constrained Markov Decision Processsのポリシーに基づくPrimal-Dual法
- Authors: Donghao Ying, Mengzi Guo, Yuhao Ding, Javad Lavaei, Zuo-Jun (Max) Shen
- Abstract要約: 本稿では, 目標を凹凸とし, 速度-作用分布の制約を凸凸とする改良された凸拘束決定(CMDP)を導入する。
本研究では,訪問分布に強い目的がある場合に,悲観的状態制約違反が達成可能であることを示す。
- 参考スコア(独自算出の注目度): 9.262157005505221
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We study convex Constrained Markov Decision Processes (CMDPs) in which the
objective is concave and the constraints are convex in the state-action
visitation distribution. We propose a policy-based primal-dual algorithm that
updates the primal variable via policy gradient ascent and updates the dual
variable via projected sub-gradient descent. Despite the loss of additivity
structure and the nonconvex nature, we establish the global convergence of the
proposed algorithm by leveraging a hidden convexity in the problem under the
general soft-max parameterization, and prove the
$\mathcal{O}\left(T^{-1/3}\right)$ convergence rate in terms of both optimality
gap and constraint violation. When the objective is strongly concave in the
visitation distribution, we prove an improved convergence rate of
$\mathcal{O}\left(T^{-1/2}\right)$. By introducing a pessimistic term to the
constraint, we further show that a zero constraint violation can be achieved
while preserving the same convergence rate for the optimality gap. This work is
the first one in the literature that establishes non-asymptotic convergence
guarantees for policy-based primal-dual methods for solving infinite-horizon
discounted convex CMDPs.
- Abstract(参考訳): 本研究では,目的が凹凸であり,制約が状態行動訪問分布において凸となる凸拘束マルコフ決定過程(cmdps)について検討する。
本稿では,ポリシー勾配上昇によるプライマリ変数の更新と,予測されたサブ段階降下によるデュアル変数の更新を提案する。
加法構造と非凸性が失われているにもかかわらず、一般のソフトマックスパラメータ化の下で問題内の隠れ凸性を利用して提案アルゴリズムのグローバル収束を確立し、最適性ギャップと制約違反の両方の観点から$\mathcal{O}\left(T^{-1/3}\right)$収束率を証明した。
目的が訪問分布において強凹であるとき、改善された収束率を$\mathcal{O}\left(T^{-1/2}\right)$とする。
制約に悲観的項を導入することにより、最適性ギャップに対して同じ収束率を維持しながら、ゼロ制約違反が達成可能であることを示す。
この研究は、無限ホリゾンディスカウント凸cmdpを解くためのポリシーに基づく原始的手法に対する非漸近収束保証を確立する最初の文献である。
関連論文リスト
- Double Duality: Variational Primal-Dual Policy Optimization for
Constrained Reinforcement Learning [132.7040981721302]
本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。
制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
論文 参考訳(メタデータ) (2024-02-16T16:35:18Z) - Last-Iterate Convergent Policy Gradient Primal-Dual Methods for
Constrained MDPs [107.28031292946774]
無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。
我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。
我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
論文 参考訳(メタデータ) (2023-06-20T17:27:31Z) - Convergence and sample complexity of natural policy gradient primal-dual
methods for constrained MDPs [24.582720609592464]
我々は、割引された最適レート問題を解くために、自然政策勾配法を用いる。
また、2つのサンプルベースNPG-PDアルゴリズムに対して収束と有限サンプル保証を提供する。
論文 参考訳(メタデータ) (2022-06-06T04:28:04Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳(メタデータ) (2022-06-03T16:26:38Z) - Fast Global Convergence of Policy Optimization for Constrained MDPs [17.825031573375725]
勾配法は最適性ギャップと制約違反の両方に対して$mathcalO(log(T)/T)$大域収束率が得られることを示す。
スレーターの条件が満たされ、事前条件が知られているとき、十分大きなT$に対してゼロ制約違反がさらに保証される。
論文 参考訳(メタデータ) (2021-10-31T17:46:26Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - A Dual Approach to Constrained Markov Decision Processes with Entropy
Regularization [7.483040617090451]
本研究では,ソフトマックスパラメータ化の下で,エントロピー規則化制約付きマルコフ決定過程(CMDP)について検討する。
我々の理論的解析は、ラグランジアン双対函数は滑らかであり、ラグランジアン双対性ギャップは原始性ギャップと制約違反に分解できることを示している。
論文 参考訳(メタデータ) (2021-10-17T21:26:40Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳(メタデータ) (2021-06-30T18:32:46Z) - Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。
ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
論文 参考訳(メタデータ) (2021-02-22T18:56:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。