論文の概要: Algorithm for Constrained Markov Decision Process with Linear
Convergence
- arxiv url: http://arxiv.org/abs/2206.01666v1
- Date: Fri, 3 Jun 2022 16:26:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-06 15:20:58.973060
- Title: Algorithm for Constrained Markov Decision Process with Linear
Convergence
- Title(参考訳): 線形収束を伴うマルコフ決定過程の制約アルゴリズム
- Authors: Egor Gladin, Maksim Lavrik-Karmazin, Karina Zainullina, Varvara
Rudenko, Alexander Gasnikov, Martin Tak\'a\v{c}
- Abstract要約: エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
- 参考スコア(独自算出の注目度): 55.41644538483948
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of constrained Markov decision process is considered. An agent
aims to maximize the expected accumulated discounted reward subject to multiple
constraints on its costs (the number of constraints is relatively small). A new
dual approach is proposed with the integration of two ingredients: entropy
regularized policy optimizer and Vaidya's dual optimizer, both of which are
critical to achieve faster convergence. The finite-time error bound of the
proposed approach is provided. Despite the challenge of the nonconcave
objective subject to nonconcave constraints, the proposed approach is shown to
converge (with linear rate) to the global optimum. The complexity expressed in
terms of the optimality gap and the constraint violation significantly improves
upon the existing primal-dual approaches.
- Abstract(参考訳): 拘束されたマルコフ決定過程の問題は考慮される。
エージェントは、そのコストに対する複数の制約(制約の数は比較的少ない)の対象となる期待の累積割引報酬を最大化する。
エントロピー正規化ポリシーオプティマイザ(entropy regularized policy optimizer)とvaidyaのデュアルオプティマイザ(dual optimizer)の2つの要素を統合した新しいデュアルアプローチが提案されている。
提案手法の有限時間誤差境界について述べる。
非凹面対象の非凹面制約に対する挑戦にもかかわらず、提案手法は(線形速度で)大域的最適値に収束することが示されている。
最適性ギャップと制約違反の観点から表される複雑さは、既存の原始双対アプローチによって大幅に改善される。
関連論文リスト
- The inexact power augmented Lagrangian method for constrained nonconvex optimization [44.516958213972885]
この研究は、強大な拡張ラグランジアン用語を導入し、拡大項はユークリッドのノルムを権力へと引き上げる。
その結果, 長期化に低消費電力を用いると, 残余の減少が遅くなるにもかかわらず, より高速な成長が期待できることがわかった。
以上の結果より, 持続時間の短縮には低消費電力が有効であるが, 残留率が低下する傾向が示唆された。
論文 参考訳(メタデータ) (2024-10-26T11:31:56Z) - A Double Tracking Method for Optimization with Decentralized Generalized Orthogonality Constraints [4.6796315389639815]
分散最適化問題は分散制約の存在下では解決できない。
目的関数の勾配と制約写像のヤコビアンを同時に追跡する新しいアルゴリズムを導入する。
合成と実世界の両方のデータセットに数値的な結果を示す。
論文 参考訳(メタデータ) (2024-09-08T06:57:35Z) - Two-Step QAOA: Enhancing Quantum Optimization by Decomposing One-Hot Constraints in QUBO Formulations [0.0]
本稿では,QAOAの有効性を向上させるための簡単なアプローチであるTwo-Step QAOAを提案する。
問題を2段階に分けて,ソフト制約をハード制約に変換する。
論文 参考訳(メタデータ) (2024-08-09T23:38:28Z) - Double Duality: Variational Primal-Dual Policy Optimization for
Constrained Reinforcement Learning [132.7040981721302]
本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。
制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
論文 参考訳(メタデータ) (2024-02-16T16:35:18Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳(メタデータ) (2022-11-14T21:54:31Z) - 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) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳(メタデータ) (2020-10-31T21:35:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。