論文の概要: A Gradient-Aware Search Algorithm for Constrained Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2005.03718v1
• Date: Thu, 7 May 2020 19:38:09 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-05 23:08:00.975620
• Title: A Gradient-Aware Search Algorithm for Constrained Markov Decision Processes
• Title（参考訳）: 制約マルコフ決定過程に対する勾配認識探索アルゴリズム
• Authors: Sami Khairy, Prasanna Balaprakash, Lin X. Cai
• Abstract要約: まず,有限CMDPの双対線型計画における最適化目標が,ラグランジュのペナルティ乗算器に対する一方向線型凸関数であることを証明した。 有限CMDPの最適状態値関数とラグランジュペナルティ乗算器を求めるために,PWLC構造を利用した2レベルグラディエント・アウェア・サーチ(GAS)アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 9.728259735794987
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The canonical solution methodology for finite constrained Markov decision processes (CMDPs), where the objective is to maximize the expected infinite-horizon discounted rewards subject to the expected infinite-horizon discounted costs constraints, is based on convex linear programming. In this brief, we first prove that the optimization objective in the dual linear program of a finite CMDP is a piece-wise linear convex function (PWLC) with respect to the Lagrange penalty multipliers. Next, we propose a novel two-level Gradient-Aware Search (GAS) algorithm which exploits the PWLC structure to find the optimal state-value function and Lagrange penalty multipliers of a finite CMDP. The proposed algorithm is applied in two stochastic control problems with constraints: robot navigation in a grid world and solar-powered unmanned aerial vehicle (UAV)-based wireless network management. We empirically compare the convergence performance of the proposed GAS algorithm with binary search (BS), Lagrangian primal-dual optimization (PDO), and Linear Programming (LP). Compared with benchmark algorithms, it is shown that the proposed GAS algorithm converges to the optimal solution faster, does not require hyper-parameter tuning, and is not sensitive to initialization of the Lagrange penalty multiplier.
• Abstract（参考訳）: 有限制約マルコフ決定過程(CMDP)の標準解法は、期待される無限水平割引コスト制約の対象となる無限水平割引報酬を最大化することを目的としており、凸線形プログラミングに基づいている。 本稿では,有限CMDPの双対線形プログラムにおける最適化の目的が,ラグランジュペナルティ乗算器に関して,ピースワイズ線形凸関数(PWLC)であることを最初に証明する。 次に、PWLC構造を利用して、有限CMDPの最適状態値関数とラグランジュペナルティ乗算器を求める2レベルグラディエント・アウェア・サーチ(GAS)アルゴリズムを提案する。 提案アルゴリズムは,グリッド環境におけるロボットナビゲーションと,ソーラーパワーの無人航空機(UAV)による無線ネットワーク管理の2つの制約付き確率制御問題に適用される。 本稿では,提案したGASアルゴリズムの収束性能を,二進探索(BS),ラグランジアン原始双対最適化(PDO),線形計画法(LP)と比較した。 ベンチマークアルゴリズムと比較すると,提案手法は最適解に高速に収束し,超パラメータチューニングを必要とせず,ラグランジュペナルティ乗算器の初期化に敏感でないことが示された。

関連論文リスト

• A Learned Proximal Alternating Minimization Algorithm and Its Induced Network for a Class of Two-block Nonconvex and Nonsmooth Optimization [4.975853671529418]
  本研究では,学習可能な2ブロック非平滑問題の解法として,一般学習型交互最小化アルゴリズムLPAMを提案する。 提案するLPAM-netはパラメータ効率が高く,いくつかの最先端手法と比較して良好な性能を示す。
  論文  参考訳（メタデータ） (2024-11-10T02:02:32Z)
• Two-Stage ML-Guided Decision Rules for Sequential Decision Making under Uncertainty [55.06411438416805]
  SDMU (Sequential Decision Making Under Uncertainty) は、エネルギー、金融、サプライチェーンといった多くの領域において、ユビキタスである。 いくつかのSDMUは、自然にマルチステージ問題(MSP)としてモデル化されているが、結果として得られる最適化は、計算の観点からは明らかに困難である。 本稿では,2段階の一般決定規則(TS-GDR)を導入し,線形関数を超えて政策空間を一般化する手法を提案する。 TS-GDRの有効性は、TS-LDR(Two-Stage Deep Decision Rules)と呼ばれるディープリカレントニューラルネットワークを用いたインスタンス化によって実証される。
  論文  参考訳（メタデータ） (2024-05-23T18:19:47Z)
• Floorplanning of VLSI by Mixed-Variable Optimization [42.82770651937298]
  本稿では,混合変数のフロアプランニング問題を解くためのメメティックアルゴリズムを提案する。 提案アルゴリズムは、著名なB*木に基づくフロアプランニングアルゴリズムよりも優れている。
  論文  参考訳（メタデータ） (2024-01-27T06:34:16Z)
• On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality [5.35599092568615]
  本稿では,ピアツーピアマルチエージェントネットワークにおける分散最適化問題について考察する。 比例積分 (PI) 制御戦略を用いることで, 固定段数をもつ様々なアルゴリズムが開発されている。
  論文  参考訳（メタデータ） (2023-09-30T15:54:52Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Functional Constrained Optimization for Risk Aversion and Sparsity Control [7.561780884831967]
  リスクとスパーシリティの要件は、ポートフォリオ最適化、アソート計画、放射線計画など、多くのアプリケーションで同時に実施する必要がある。 本稿では,これらの課題に対して凸あるいはスパース軌道を生成するレベル条件勾配(LCG)法を提案する。 提案手法は,極小勾配を解くための内部条件近似(CGO)を最適値のレベル1セット投影することを示す。
  論文  参考訳（メタデータ） (2022-10-11T02:51:51Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
  深層強化学習のための線形プログラミング(LP)の定式化について検討する。 拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。 深層パラメタライズされたラグランジアン法を提案する。
  論文  参考訳（メタデータ） (2021-05-20T13:08:06Z)

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

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