論文の概要: Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation
- arxiv url: http://arxiv.org/abs/2402.01371v3
- Date: Mon, 16 Dec 2024 16:17:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-17 13:49:49.197426
- Title: Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation
- Title(参考訳): 関数近似を用いた平均逆MDPに対する2時間的批判アクタ
- Authors: Prashansa Panda, Shalabh Bhatnagar,
- Abstract要約: 本稿では,長期平均報酬設定における関数近似を用いた最初の2段階の批評家・アクターアルゴリズムを提案する。
また、そのようなスキームに対する収束解析と同様に、最初の有限時間非漸近アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 5.945710235932345
- License:
- Abstract: Several recent works have focused on carrying out non-asymptotic convergence analyses for AC algorithms. Recently, a two-timescale critic-actor algorithm has been presented for the discounted cost setting in the look-up table case where the timescales of the actor and the critic are reversed and only asymptotic convergence shown. In our work, we present the first two-timescale critic-actor algorithm with function approximation in the long-run average reward setting and present the first finite-time non-asymptotic as well as asymptotic convergence analysis for such a scheme. We obtain optimal learning rates and prove that our algorithm achieves a sample complexity of {$\mathcal{\tilde{O}}(\epsilon^{-(2+\delta)})$ with $\delta >0$ arbitrarily close to zero,} for the mean squared error of the critic to be upper bounded by $\epsilon$ which is better than the one obtained for two-timescale AC in a similar setting. A notable feature of our analysis is that we present the asymptotic convergence analysis of our scheme in addition to the finite-time bounds that we obtain and show the almost sure asymptotic convergence of the (slower) critic recursion to the attractor of an associated differential inclusion with actor parameters corresponding to local maxima of a perturbed average reward objective. We also show the results of numerical experiments on three benchmark settings and observe that our critic-actor algorithm performs the best amongst all algorithms.
- Abstract(参考訳): 最近のいくつかの研究は、ACアルゴリズムの非漸近収束解析の実行に焦点を当てている。
近年,アクターと批評家の時間スケールが逆転し,漸近収束のみを示すルックアップテーブルケースにおいて,2段階の批評家・アクターアルゴリズムがコスト設定の割引として提案されている。
本研究では,長期平均報酬設定に関数近似を付加した最初の2時間スケール批評家-アクターアルゴリズムを提案し,そのようなスキームに対する漸近的収束解析とともに,最初の有限時間非漸近的および漸近的収束解析を提示する。
我々は最適学習率を求め,このアルゴリズムが,2時間ACで得られた平均2乗の誤差に対して,$\mathcal{\tilde{O}}(\epsilon^{-(2+\delta)})$と$\delta >0$を任意に0に近づけた値のサンプル複雑性を達成することを証明した。
本分析の特筆すべき特徴は, 摂動平均報酬目標の局所的最大値に対応するアクターパラメータと関連する差分包有物に対する(より遅い)批判再帰のほぼ確実に漸近収束を示す有限時間境界に加えて, 提案手法の漸近収束解析を提示することである。
また、3つのベンチマーク設定に関する数値実験の結果を示し、我々の批評家・俳優アルゴリズムが全てのアルゴリズムの中で最高の性能を発揮することを観察する。
関連論文リスト
- Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms [49.19842488693726]
我々は,O(epsilon-3)$のサンプル複雑性を大幅に改善したアクター・クリティック・アルゴリズムのグローバル収束を確立した。
我々の発見は、一定のステップサイズに依存する多くのアルゴリズムに対する理論的支援を提供する。
論文 参考訳(メタデータ) (2024-10-11T14:46:29Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳(メタデータ) (2024-06-28T02:56:22Z) - Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation [18.77565744533582]
アクタークリティカル (AC) は、強化学習において最適な政策を学ぶための強力な方法である。
AC は $epsilon +varepsilon_textcritic$ 定常点の近傍に収束する。
本稿では,ACアルゴリズムとNACアルゴリズムのコンバージェンスを,相反する関数近似を用いて解析する。
論文 参考訳(メタデータ) (2024-06-03T20:05:04Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random
Perturbations for Stochastic Optimization [10.820943271350442]
本稿では,雑音の多いコストサンプルに対する期待値であるスムーズな目的関数を最小化するための凸勾配アルゴリズムを提案する。
また,本アルゴリズムは局所最小値への収束を示唆し,レートリリアを回避できることも示している。
論文 参考訳(メタデータ) (2022-07-30T18:50:36Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。