論文の概要: Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process

• arxiv url: http://arxiv.org/abs/2110.10351v1
• Date: Wed, 20 Oct 2021 02:57:21 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-24 02:19:13.899596
• Title: Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process
• Title（参考訳）: 制約付きマルコフ決定過程の高速アルゴリズムとシャープ解析
• Authors: Tianjiao Li, Ziwei Guan, Shaofeng Zou, Tengyu Xu, Yingbin Liang and Guanghui Lan
• Abstract要約: 制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
• 参考スコア（独自算出の注目度）: 56.55075925645864
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of constrained Markov decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its utilities/costs. A new primal-dual approach is proposed with a novel integration of three ingredients: entropy regularized policy optimizer, dual variable regularizer, and Nesterov's accelerated gradient descent dual optimizer, all of which are critical to achieve a faster convergence. The finite-time error bound of the proposed approach is characterized. Despite the challenge of the nonconcave objective subject to nonconcave constraints, the proposed approach is shown to converge to the global optimum with a complexity of $\tilde{\mathcal O}(1/\epsilon)$ in terms of the optimality gap and the constraint violation, which improves the complexity of the existing primal-dual approach by a factor of $\mathcal O(1/\epsilon)$ \citep{ding2020natural,paternain2019constrained}. This is the first demonstration that nonconcave CMDP problems can attain the complexity lower bound of $\mathcal O(1/\epsilon)$ for convex optimization subject to convex constraints. Our primal-dual approach and non-asymptotic analysis are agnostic to the RL optimizer used, and thus are more flexible for practical applications. More generally, our approach also serves as the first algorithm that provably accelerates constrained nonconvex optimization with zero duality gap by exploiting the geometries such as the gradient dominance condition, for which the existing acceleration methods for constrained convex optimization are not applicable.
• Abstract（参考訳）: 制約付きマルコフ決定プロセス(CMDP)の問題点を考察し、エージェントは、そのユーティリティやコストに対する複数の制約により、期待される累積割引報酬を最大化する。 エントロピー正則化ポリシーオプティマイザ, 双対変数正則化器, ネステロフ加速勾配降下双最適化器の3成分を新たに統合し, より高速な収束を達成するために重要な手法を提案する。 提案手法の有限時間誤差境界を特徴付ける。 非凹型制約を対象とする非凹型目標の挑戦にもかかわらず、提案されたアプローチは、最適性ギャップと制約違反の観点から、$\tilde{\mathcal o}(1/\epsilon)$の複雑性で大域的最適化に収束することを示し、既存の原始双対アプローチの複雑さを$\mathcal o(1/\epsilon)$ \citep{ding2020natural,paternain2019constrained}の係数によって改善する。 これは、非凸cmdp問題が凸制約を受ける凸最適化に対する$\mathcal o(1/\epsilon)$の複雑性下限を達成することができる最初の例である。 我々の原始双対アプローチと非漸近解析は、使用するRLオプティマイザに非依存であり、実用的な応用にはより柔軟である。 より一般に、本手法は、既存の制約付き凸最適化のための加速度法が適用できない勾配支配条件のようなジオメトリを利用して、ゼロ双対性ギャップで制約付き非凸最適化を確実に加速する最初のアルゴリズムとしても機能する。

関連論文リスト

• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
  この問題が低ランクの解を許容する高次元かつ高可算な設定に焦点をあてる。 これらの条件下では、よく知られた過次法が制約付き最適化問題の解に収束することを示す理論的結果がいくつか提示される。
  論文  参考訳（メタデータ） (2024-02-14T10:48:00Z)
• Online Non-convex Optimization with Long-term Non-convex Constraints [2.033434950296318]
  Follow-the-Perturbed-Leader型アルゴリズムを提案する。 提案アルゴリズムは,長期(極値)制約のある河川汚染源同定問題に対処するために適用された。
  論文  参考訳（メタデータ） (2023-11-04T15:08:36Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。 本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。 我々は,新しい数値スケール問題の有効性を実証する。
  論文  参考訳（メタデータ） (2020-10-23T05:24:05Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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