論文の概要: Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic
Algorithm for Constrained Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2110.11383v1
- Date: Thu, 21 Oct 2021 18:05:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-25 15:24:56.727000
- Title: Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic
Algorithm for Constrained Markov Decision Processes
- Title（参考訳）: 制約マルコフ決定過程に対するオンライン原始的自然アクター臨界アルゴリズムの有限時間複素性
- Authors: Sihan Zeng, Thinh T. Doan, Justin Romberg
- Abstract要約: そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
- 参考スコア（独自算出の注目度）: 22.07834608976826
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a discounted cost constrained Markov decision process (CMDP)
policy optimization problem, in which an agent seeks to maximize a discounted
cumulative reward subject to a number of constraints on discounted cumulative
utilities. To solve this constrained optimization program, we study an online
actor-critic variant of a classic primal-dual method where the gradients of
both the primal and dual functions are estimated using samples from a single
trajectory generated by the underlying time-varying Markov processes. This
online primal-dual natural actor-critic algorithm maintains and iteratively
updates three variables: a dual variable (or Lagrangian multiplier), a primal
variable (or actor), and a critic variable used to estimate the gradients of
both primal and dual variables. These variables are updated simultaneously but
on different time scales (using different step sizes) and they are all
intertwined with each other. Our main contribution is to derive a finite-time
analysis for the convergence of this algorithm to the global optimum of a CMDP
problem. Specifically, we show that with a proper choice of step sizes the
optimality gap and constraint violation converge to zero in expectation at a
rate $\mathcal{O}(1/K^{1/6})$, where K is the number of iterations. To our
knowledge, this paper is the first to study the finite-time complexity of an
online primal-dual actor-critic method for solving a CMDP problem. We also
validate the effectiveness of this algorithm through numerical simulations.
- Abstract（参考訳）: 本稿では,割引コスト制約付きマルコフ決定プロセス (CMDP) の政策最適化問題について考察する。
この制約付き最適化プログラムでは, 基本関数と双対関数の両方の勾配を, 時間変化マルコフ過程によって生成される単一の軌道からのサンプルを用いて推定する, 古典的な原始双対法のオンラインアクタ-クリティック変種について検討する。
このオンラインプライマル・デュアル・ナチュラル・アクタ-クリティックアルゴリズムは、3つの変数(双対変数(ラグランジアン乗算器)、プリマル変数(またはアクタ)、およびプリマル変数と双対変数の両方の勾配を推定するために使用される批判変数)を維持および反復的に更新する。
これらの変数は同時に更新されるが、異なる時間スケールで更新される(異なるステップサイズを使用する)。
我々の主な貢献は、このアルゴリズムの収束に関する有限時間解析をCMDP問題の大域的最適に導くことである。
具体的には、ステップサイズを適切に選択することで、最適性ギャップと制約違反は、K が反復数であるような $\mathcal{O}(1/K^{1/6})$ の確率でゼロに収束することを示す。
そこで本研究では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティック手法の有限時間複雑性を初めて研究した。
また,このアルゴリズムの有効性を数値シミュレーションにより検証する。
関連論文リスト
- Performative Reinforcement Learning with Linear Markov Decision Process [14.75815792682734]
提案手法がマルコフ決定過程の報酬と遷移の両方に影響を及ぼすような表現的強化学習の設定について検討する。
大規模MDPの主要な理論モデルであるEmphlinear Markov決定過程を一般化する。
論文 参考訳（メタデータ） (2024-11-07T23:04:48Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - 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 Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning [13.908826484332282]
最適化問題の解法として,新しい2段階勾配法を提案する。
最初の貢献は、提案した2時間スケール勾配アルゴリズムの有限時間複雑性を特徴づけることである。
我々は、強化学習における勾配に基づく政策評価アルゴリズムに適用する。
論文 参考訳（メタデータ） (2021-09-29T23:15:23Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Non-asymptotic Convergence Analysis of Two Time-scale (Natural)
Actor-Critic Algorithms [58.57004511121862]
アクタークリティカル(AC)とナチュラルアクタークリティカル(NAC)のアルゴリズムは、最適なポリシーを見つけるために2つの方法で実行されることが多い。
2つの時間スケールACは、$mathcalO(epsilon-2.5log3(epsilon-1))$で、$epsilon$-accurateの定常点に達するために、全体のサンプルの複雑さを必要とすることを示す。
我々は,動的にマルコフサンプリングが変化するため,アクターのバイアス誤差をバウンドする新しい手法を開発した。
論文 参考訳（メタデータ） (2020-05-07T15:42:31Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z) - A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates [16.54912614895861]
我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。
我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。
その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
論文 参考訳（メタデータ） (2020-03-03T03:59:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。