論文の概要: 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.
特に、大きなグリッドサイズの場合、制約付き自然アクター批評家は、制約付きアクター批評家よりわずかに良い結果を示し、後者は小さなグリッドサイズではわずかに良い結果を示す。
関連論文リスト
- Critic-Actor for Average Reward MDPs with Function Approximation: A
Finite-Time Analysis [6.682382456607199]
本稿では,関数近似と長期平均報酬設定を併用した最初の批評家・アクターアルゴリズムを提案する。
我々は最適学習率を求め,このアルゴリズムが平均二乗誤差に対して$mathcaltildeO(eps-2.08)$のサンプル複雑性を実現することを証明した。
また、3つのベンチマーク設定に関する数値実験の結果を示し、アクター・アクター・アルゴリズムがアクター・アクター・アクターとよく競合することを示した。
論文 参考訳(メタデータ) (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) - A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian
Process Bandits [118.22458816174144]
そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。
我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。
GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
論文 参考訳(メタデータ) (2022-02-03T21:19:36Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic
Algorithm for Constrained Markov Decision Processes [22.07834608976826]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳(メタデータ) (2021-10-21T18:05:40Z) - Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm [4.932130498861987]
重要度サンプリングに基づく自然アクタ-クリティック(nac)アルゴリズムのオフポリシー変種に対する有限サンプル収束保証を提供する。
このアルゴリズムは、ステップの適切な選択の下で$mathcalo(epsilon-3log2(1/epsilon)$のサンプル複雑性を持つ大域的最適ポリシーに収束する。
論文 参考訳(メタデータ) (2021-02-18T13:22:59Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。