論文の概要: Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation
- arxiv url: http://arxiv.org/abs/2406.01762v1
- Date: Mon, 3 Jun 2024 20:05:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-05 21:02:09.572908
- Title: Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation
- Title(参考訳): コンパチブル関数近似を用いた単一ループ(Natural Actor-Critic)の非漸近解析
- Authors: Yudan Wang, Yue Wang, Yi Zhou, Shaofeng Zou,
- Abstract要約: アクタークリティカル (AC) は、強化学習において最適な政策を学ぶための強力な方法である。
AC は $epsilon +varepsilon_textcritic$ 定常点の近傍に収束する。
本稿では,ACアルゴリズムとNACアルゴリズムのコンバージェンスを,相反する関数近似を用いて解析する。
- 参考スコア(独自算出の注目度): 18.77565744533582
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Actor-critic (AC) is a powerful method for learning an optimal policy in reinforcement learning, where the critic uses algorithms, e.g., temporal difference (TD) learning with function approximation, to evaluate the current policy and the actor updates the policy along an approximate gradient direction using information from the critic. This paper provides the \textit{tightest} non-asymptotic convergence bounds for both the AC and natural AC (NAC) algorithms. Specifically, existing studies show that AC converges to an $\epsilon+\varepsilon_{\text{critic}}$ neighborhood of stationary points with the best known sample complexity of $\mathcal{O}(\epsilon^{-2})$ (up to a log factor), and NAC converges to an $\epsilon+\varepsilon_{\text{critic}}+\sqrt{\varepsilon_{\text{actor}}}$ neighborhood of the global optimum with the best known sample complexity of $\mathcal{O}(\epsilon^{-3})$, where $\varepsilon_{\text{critic}}$ is the approximation error of the critic and $\varepsilon_{\text{actor}}$ is the approximation error induced by the insufficient expressive power of the parameterized policy class. This paper analyzes the convergence of both AC and NAC algorithms with compatible function approximation. Our analysis eliminates the term $\varepsilon_{\text{critic}}$ from the error bounds while still achieving the best known sample complexities. Moreover, we focus on the challenging single-loop setting with a single Markovian sample trajectory. Our major technical novelty lies in analyzing the stochastic bias due to policy-dependent and time-varying compatible function approximation in the critic, and handling the non-ergodicity of the MDP due to the single Markovian sample trajectory. Numerical results are also provided in the appendix.
- Abstract(参考訳): アクター批判 (AC) は強化学習において最適な政策を学習する強力な方法であり、例えば、時間差(TD)学習を関数近似で用い、現在の方針を評価し、アクターは評論家の情報を用いて近似勾配方向に沿ってポリシーを更新する。
本稿では、ACアルゴリズムとNACアルゴリズムの両方に対して、textit{tightest}非漸近収束境界を提供する。
具体的には、AC は $\epsilon +\varepsilon_{\text{critic}}$ 定常点近傍に収束し、NAC は $\epsilon +\varepsilon_{\text{critic}}+\sqrt{\varepsilon_{\text{actor}}} グローバル最適点近傍に収束し、最も知られている $\mathcal{O}(\epsilon^{-3})$ は、批評家の近似誤差である。
本稿では,ACアルゴリズムとNACアルゴリズムのコンバージェンスを,相反する関数近似を用いて解析する。
私たちの分析では、最もよく知られたサンプルの複雑さを達成しながら、エラー境界から$\varepsilon_{\text{critic}}$という用語を排除しています。
さらに,1つのマルコフサンプル軌道を用いた単一ループ設定に着目する。
我々の主要な技術的新奇性は、批判者における政策依存的かつ時間変化の相反する関数近似による確率的バイアスの分析と、マルコフ標本軌道によるMDPの非エルゴード性を扱うことである。
付録にも数値結果が記載されている。
関連論文リスト
- Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Provably Efficient Convergence of Primal-Dual Actor-Critic with
Nonlinear Function Approximation [15.319335698574932]
The first efficient convergence result with primal-dual actor-critic with a convergence of $mathcalOleft ascent(Nright)Nright)$ under Polyian sample。
Open GymAI連続制御タスクの結果。
論文 参考訳(メタデータ) (2022-02-28T15:16:23Z) - Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear
Function Approximation [5.543220407902113]
我々は,線形関数近似を用いた非政治的自然なアクター批判アルゴリズムの新たな変種を開発する。
我々は$mathcalO(epsilon-3)$のサンプル複雑性を確立し、そのようなアルゴリズムの既知収束境界を全て上回る。
論文 参考訳(メタデータ) (2021-05-26T13:35:42Z) - Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。
DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。
有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
論文 参考訳(メタデータ) (2021-02-23T18:56:13Z) - 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) - Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms [58.57004511121862]
本稿では, マルコフサンプリングにおけるACおよびNACの収束速度とサンプリング複雑性を特徴付ける。
本稿では,ACとNACがPGおよびNPGに対して,批判の組み合わさりにより,無限の地平線下での順に性能改善を実現していることを示す。
論文 参考訳(メタデータ) (2020-04-27T17:11:06Z) - Non-asymptotic Convergence of Adam-type Reinforcement Learning
Algorithms under Markovian Sampling [56.394284787780364]
本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。
一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。
線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
論文 参考訳(メタデータ) (2020-02-15T00:26:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。