論文の概要: Finite Time Analysis of Constrained Actor Critic and Constrained Natural
Actor Critic Algorithms
- arxiv url: http://arxiv.org/abs/2310.16363v1
- Date: Wed, 25 Oct 2023 05:04:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-26 16:48:35.523566
- Title: Finite Time Analysis of Constrained Actor Critic and Constrained Natural
Actor Critic Algorithms
- Title（参考訳）: 制約付きアクター批判アルゴリズムと制約付き自然アクター批判アルゴリズムの有限時間解析
- Authors: Prashansa Panda, Shalabh Bhatnagar
- Abstract要約: 我々は,制約付きマルコフ決定過程の関数近似を用いた,アクター批判と自然なアクター批判アルゴリズムについて検討する。
また,いくつかのグリッド・ワールド・セッティングの実験結果を示すとともに,この2つのアルゴリズムを用いて良好な実験性能を示す。
- 参考スコア（独自算出の注目度）: 6.682382456607199
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Actor Critic methods have found immense applications on a wide range of
Reinforcement Learning tasks especially when the state-action space is large.
In this paper, we consider actor critic and natural actor critic algorithms
with function approximation for constrained Markov decision processes (C-MDP)
involving inequality constraints and carry out a non-asymptotic analysis for
both of these algorithms in a non-i.i.d (Markovian) setting. We consider the
long-run average cost criterion where both the objective and the constraint
functions are suitable policy-dependent long-run averages of certain prescribed
cost functions. We handle the inequality constraints using the Lagrange
multiplier method. We prove that these algorithms are guaranteed to find a
first-order stationary point (i.e., $\Vert \nabla L(\theta,\gamma)\Vert_2^2
\leq \epsilon$) of the performance (Lagrange) function $L(\theta,\gamma)$, with
a sample complexity of $\mathcal{\tilde{O}}(\epsilon^{-2.5})$ in the case of
both Constrained Actor Critic (C-AC) and Constrained Natural Actor Critic
(C-NAC) algorithms.We also show the results of experiments on a few different
grid world settings and observe good empirical performance using both of these
algorithms. In particular, for large grid sizes, Constrained Natural Actor
Critic shows slightly better results than Constrained Actor Critic while the
latter is slightly better for a small grid size.
- Abstract（参考訳）: アクターの批判手法は、特に状態-アクション空間が大きい場合、幅広い強化学習タスクで膨大な応用を見出している。
本稿では,不等式制約を含む制約付きマルコフ決定過程(C-MDP)の関数近似を用いたアクター評論家および自然なアクター評論家アルゴリズムについて考察し,これらのアルゴリズムを非i.d(マルコフアン)環境で非漸近解析する。
目的関数と制約関数の両方が所定コスト関数の政策依存の長期平均となるような長期平均コスト基準を考察する。
我々はラグランジュ乗算法を用いて不等式制約を扱う。
We prove that these algorithms are guaranteed to find a first-order stationary point (i.e., $\Vert \nabla L(\theta,\gamma)\Vert_2^2 \leq \epsilon$) of the performance (Lagrange) function $L(\theta,\gamma)$, with a sample complexity of $\mathcal{\tilde{O}}(\epsilon^{-2.5})$ in the case of both Constrained Actor Critic (C-AC) and Constrained Natural Actor Critic (C-NAC) algorithms.We also show the results of experiments on a few different grid world settings and observe good empirical performance using both of these algorithms.
特に、大きなグリッドサイズの場合、制約付き自然アクター批評家は、制約付きアクター批評家よりわずかに良い結果を示し、後者は小さなグリッドサイズではわずかに良い結果を示す。
関連論文リスト
- Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation [5.945710235932345]
本稿では,長期平均報酬設定における関数近似を用いた最初の2段階の批評家・アクターアルゴリズムを提案する。
我々の分析の特筆すべき特徴は、最近のシングルタイムスケールアクター批判アルゴリズムとは異なり、我々のスキームの完全な収束解析を提示することである。
論文 参考訳（メタデータ） (2024-02-02T12:48:49Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes [13.908826484332282]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳（メタデータ） (2021-10-21T18:05:40Z) - Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear
Function Approximation [5.543220407902113]
我々は,線形関数近似を用いた非政治的自然なアクター批判アルゴリズムの新たな変種を開発する。
我々は$mathcalO(epsilon-3)$のサンプル複雑性を確立し、そのようなアルゴリズムの既知収束境界を全て上回る。
論文 参考訳（メタデータ） (2021-05-26T13:35:42Z) - Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm [4.932130498861987]
重要度サンプリングに基づく自然アクタ-クリティック(nac)アルゴリズムのオフポリシー変種に対する有限サンプル収束保証を提供する。
このアルゴリズムは、ステップの適切な選択の下で$mathcalo(epsilon-3log2(1/epsilon)$のサンプル複雑性を持つ大域的最適ポリシーに収束する。
論文 参考訳（メタデータ） (2021-02-18T13:22:59Z) - Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。
ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。
そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-08T00:43:04Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - 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) - A Finite Time Analysis of Two Time-Scale Actor Critic Methods [87.69128666220016]
我々は,2つの時間スケールのアクター批判的手法に対する非漸近的解析を行う。
本研究では,アクター批判法が一階定常点を見つけることが保証されていることを証明した。
有限時間解析とサンプルの複雑さを2つの時間スケールアクター批判的手法に限定した最初の作品である。
論文 参考訳（メタデータ） (2020-05-04T09:45:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。